[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Xen-devel] [PATCH V4 10/11] xen/arm: io: Use binary search for mmio handler lookup



Hi Julien,

On 07/14/2016 11:46 AM, Julien Grall wrote:
Hi Shanker,

On 14/07/16 17:18, Shanker Donthineni wrote:
As the number of I/O handlers increase, the overhead associated with
linear lookup also increases. The system might have maximum of 144
(assuming CONFIG_NR_CPUS=128) mmio handlers. In worst case scenario,
it would require 144 iterations for finding a matching handler. Now
it is time for us to change from linear (complexity O(n)) to a binary
search (complexity O(log n) for reducing mmio handler lookup overhead.

Signed-off-by: Shanker Donthineni <shankerd@xxxxxxxxxxxxxx>
---
Changes since v3:
   Moved the function bsearch() to common file xen/common/bsearch.c.

Changes since v2:
   Converted mmio lookup code to a critical section.
   Copied the function bsreach() from Linux kernel.

  xen/arch/arm/io.c | 42 +++++++++++++++++++++++++-----------------
  1 file changed, 25 insertions(+), 17 deletions(-)

diff --git a/xen/arch/arm/io.c b/xen/arch/arm/io.c
index 40330f0..0471ba8 100644
--- a/xen/arch/arm/io.c
+++ b/xen/arch/arm/io.c
@@ -20,6 +20,8 @@
  #include <xen/lib.h>
  #include <xen/spinlock.h>
  #include <xen/sched.h>
+#include <xen/sort.h>
+#include <xen/bsearch.h>
  #include <asm/current.h>
  #include <asm/mmio.h>

@@ -70,27 +72,29 @@ static int handle_write(const struct mmio_handler *handler, struct vcpu *v,
                                 handler->priv);
  }

-static const struct mmio_handler *find_mmio_handler(struct domain *d,
-                                                    paddr_t gpa)
+static int cmp_mmio_handler(const void *key, const void *elem)

Would it be worth to mention in a comment that we don't support overlapping?


Sure, I'll do.

  {
-    const struct mmio_handler *handler;
-    unsigned int i;
-    struct vmmio *vmmio = &d->arch.vmmio;
+    const struct mmio_handler *handler0 = key;
+    const struct mmio_handler *handler1 = elem;

-    read_lock(&vmmio->lock);
+    if ( handler0->addr < handler1->addr )
+        return -1;

-    for ( i = 0; i < vmmio->num_entries; i++ )
-    {
-        handler = &vmmio->handlers[i];
+    if ( handler0->addr > (handler1->addr + handler1->size) )
+        return 1;

-        if ( (gpa >= handler->addr) &&
-             (gpa < (handler->addr + handler->size)) )
-            break;
-    }
+    return 0;
+}

-    if ( i == vmmio->num_entries )
-        handler = NULL;
+static const struct mmio_handler *find_mmio_handler(struct vcpu *v, paddr_t gpa)

Why have you changed the prototype of find_mmio_handler?


As such there is no reason for this change, I'll revert this change in next patchset.
+{
+    struct vmmio *vmmio = &v->domain->arch.vmmio;
+    struct mmio_handler key = {.addr = gpa};

I know it is not currently the case, but should not we take into account the size of the access?


I agree with you, we definitely need to consider size of the access for traps/emulation drivers similar to what Linux KVM code does currently. Do you know which emulation drivers are using non aligned accesses?


+    const struct mmio_handler *handler;

+    read_lock(&vmmio->lock);
+    handler = bsearch(&key, vmmio->handlers, vmmio->num_entries,
+                      sizeof(*handler), cmp_mmio_handler);
      read_unlock(&vmmio->lock);

      return handler;
@@ -99,9 +103,9 @@ static const struct mmio_handler *find_mmio_handler(struct domain *d,
  int handle_mmio(mmio_info_t *info)
  {
      struct vcpu *v = current;
-    const struct mmio_handler *handler = NULL;
+    const struct mmio_handler *handler;

Why this change?


No need to initialize this local variable because the following line always initializes it. I'll revert this change anyway to avoid confusion.


-    handler = find_mmio_handler(v->domain, info->gpa);
+    handler = find_mmio_handler(v, info->gpa);

ditto.

      if ( !handler )
          return 0;

@@ -131,6 +135,10 @@ void register_mmio_handler(struct domain *d,

      vmmio->num_entries++;

+    /* Sort mmio handlers in ascending order based on base address */
+ sort(vmmio->handlers, vmmio->num_entries, sizeof(struct mmio_handler),
+        cmp_mmio_handler, NULL);

The indentation looks wrong here.


I don't quite understand what you mean. It has 8 spaces, do I need more than 8 spaces or something else?
+
      write_unlock(&vmmio->lock);
  }




--
Shanker Donthineni
Qualcomm Datacenter Technologies, Inc. as an affiliate of Qualcomm 
Technologies, Inc.
Qualcomm Technologies, Inc. is a member of the Code Aurora Forum, a Linux 
Foundation Collaborative Project.


_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
https://lists.xen.org/xen-devel

 


Rackspace

Lists.xenproject.org is hosted with RackSpace, monitoring our
servers 24x7x365 and backed by RackSpace's Fanatical Support®.