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

[Shanker Donthineni <shankerd@xxxxxxxxxxxxxx>]

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))
+{
+    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,
+                      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);
 }
 
-- 
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