[Xen-devel] [PATCH V2 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>
---
 xen/arch/arm/io.c | 50 +++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 39 insertions(+), 11 deletions(-)

diff --git a/xen/arch/arm/io.c b/xen/arch/arm/io.c
index a5b2c2d..abf49fb 100644
--- a/xen/arch/arm/io.c
+++ b/xen/arch/arm/io.c
@@ -20,6 +20,7 @@
 #include <xen/lib.h>
 #include <xen/spinlock.h>
 #include <xen/sched.h>
+#include <xen/sort.h>
 #include <asm/current.h>
 #include <asm/mmio.h>
 
@@ -70,23 +71,38 @@ static int handle_write(const struct mmio_handler *handler, 
struct vcpu *v,
                                handler->priv);
 }
 
-int handle_mmio(mmio_info_t *info)
+const struct mmio_handler *find_mmio_handler(struct vcpu *v, paddr_t addr)
 {
-    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 = vmmio->handlers;
+    unsigned int eidx = vmmio->num_entries;
+    unsigned int midx = eidx / 2;
+    unsigned int sidx = 0;
 
-    for ( i = 0; i < vmmio->num_entries; i++ )
+    /* Do binary search for matching mmio handler */
+    while ( sidx != midx )
     {
-        handler = &vmmio->handlers[i];
-
-        if ( (info->gpa >= handler->addr) &&
-             (info->gpa < (handler->addr + handler->size)) )
-            break;
+        if ( addr < handler[midx].addr )
+            eidx = midx;
+        else
+            sidx = midx;
+        midx = sidx + (eidx - sidx) / 2;
     }
 
-    if ( i == vmmio->num_entries )
+    if ( (addr >= handler[sidx].addr) &&
+         (addr < (handler[sidx].addr + handler[sidx].size)) )
+        return handler + sidx;
+
+    return NULL;
+}
+
+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 +111,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 +146,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