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

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




Hi Julien,

On 06/28/2016 05:49 AM, Julien Grall wrote:
Hi Shanker,

On 27/06/16 21:33, 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 v2:
   Converted mmio lookup code to a critical section.
   Copied the function bsreach() from Linux kernel.

  xen/arch/arm/io.c | 97
+++++++++++++++++++++++++++++++++++++++++++++++--------
  1 file changed, 84 insertions(+), 13 deletions(-)

diff --git a/xen/arch/arm/io.c b/xen/arch/arm/io.c
index a5b2c2d..c31fdf3 100644
--- a/xen/arch/arm/io.c
+++ b/xen/arch/arm/io.c
@@ -20,9 +20,50 @@
  #include <xen/lib.h>
  #include <xen/spinlock.h>
  #include <xen/sched.h>
+#include <xen/sort.h>
  #include <asm/current.h>
  #include <asm/mmio.h>

+/*
+ * bsearch - binary search an array of elements
+ * @key: pointer to item being searched for
+ * @base: pointer to first element to search
+ * @num: number of elements
+ * @size: size of each element
+ * @cmp: pointer to comparison function
+ *
+ * This function does a binary search on the given array.  The
+ * contents of the array should already be in ascending sorted order
+ * under the provided comparison function.
+ *
+ * Note that the key need not have the same type as the elements in
+ * the array, e.g. key could be a string and the comparison function
+ * could compare the string with the struct's name field. However, if
+ * the key and elements in the array are of the same type, you can use
+ * the same comparison function for both sort() and bsearch().
+ */
+static void *bsearch(const void *key, const void *base, size_t num,
size_t size,
+                     int (*cmp)(const void *key, const void *elt))

This function is not specific to I/O handlers. So this should be moved to common code. Also please mention in the commit message where the code came from.


Should I move to xen/arch/arm folder?

+{
+    size_t start = 0, end = num;
+    int result;
+
+    while ( start < end )
+    {
+        size_t mid = start + (end - start) / 2;
+
+        result = cmp(key, base + mid * size);
+        if ( result < 0 )
+            end = mid;
+        else if ( result > 0 )
+            start = mid + 1;
+        else
+            return (void *)base + mid * size;
+    }
+
+    return NULL;
+}
+
  static int handle_read(const struct mmio_handler *handler, struct vcpu
*v,
                         mmio_info_t *info)
  {
@@ -70,23 +111,41 @@ static int handle_write(const struct mmio_handler
*handler, struct vcpu *v,
handler->priv);
  }

-int handle_mmio(mmio_info_t *info)
+static int match_mmio_handler(const void *key, const void *elem)
  {
-    struct vcpu *v = current;
-    int i;
-    const struct mmio_handler *handler = NULL;
-    const struct vmmio *vmmio = &v->domain->arch.vmmio;
+    const struct mmio_handler *handler = elem;
+    paddr_t addr = (paddr_t)key;

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

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

-    if ( i == vmmio->num_entries )
+static const struct mmio_handler *
+find_mmio_handler(struct vcpu *v, paddr_t addr)
+{
+    struct vmmio *vmmio = &v->domain->arch.vmmio;
+    const struct mmio_handler *handler;
+
+    spin_lock(&vmmio->lock);
+    handler = bsearch((const void *)addr, vmmio->handlers,
vmmio->num_entries,

paddr_t is always 64-bit regardless the architecture (ARM64 vs ARM32). So the cast will lead to a compilation error on ARM32.


I'll fix.

Please try to at least compile test your patch with ARM64, ARM32 and x86 (when you touch common code).


Thanks, I'll follow next time.

Anyway, I would try to merge the two compare functions (match_mmio_handler, cmp_mmio_handler) which have very similar behavior.


Yes, they are not exactly same. One compares only start address and other one compares the range.

+                      sizeof(*handler), match_mmio_handler);
+    spin_unlock(&vmmio->lock);
+
+    return handler;
+}
+
+int handle_mmio(mmio_info_t *info)
+{
+    const struct mmio_handler *handler;
+    struct vcpu *v = current;
+
+    handler = find_mmio_handler(v, info->gpa);
+    if ( !handler )
          return 0;

      if ( info->dabt.write )
@@ -95,6 +154,14 @@ int handle_mmio(mmio_info_t *info)
          return handle_read(handler, v, info);
  }

+static int cmp_mmio_handler(const void *key, const void *elem)
+{
+    const struct mmio_handler *handler0 = key;
+    const struct mmio_handler *handler1 = elem;
+
+    return (handler0->addr < handler1->addr) ? -1 : 0;
+}
+
  void register_mmio_handler(struct domain *d,
                             const struct mmio_handler_ops *ops,
                             paddr_t addr, paddr_t size, void *priv)
@@ -122,6 +189,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);
+
      spin_unlock(&vmmio->lock);
  }



Regards,


--
Shanker Donthineni
Qualcomm Technologies, Inc. on behalf of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux 
Foundation Collaborative Project


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

 


Rackspace

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