From: Shanker Donthineni <shankerd@codeaurora.org>
To: xen-devel <xen-devel@lists.xensource.com>,
Julien Grall <julien.grall@arm.com>,
Stefano Stabellini <sstabellini@kernel.org>
Cc: Philip Elcan <pelcan@codeaurora.org>,
Wei Liu <wei.liu2@citrix.com>,
Vikram Sethi <vikrams@codeaurora.org>,
George Dunlap <George.Dunlap@eu.citrix.com>,
Andrew Cooper <andrew.cooper3@citrix.com>,
Ian Jackson <ian.jackson@eu.citrix.com>, Tim Deegan <tim@xen.org>,
Jan Beulich <jbeulich@suse.com>,
Shanker Donthineni <shankerd@codeaurora.org>
Subject: [PATCH V2 3/4] xen/arm: io: Use binary search for mmio handler lookup
Date: Sun, 17 Jul 2016 18:26:31 -0500 [thread overview]
Message-ID: <1468797992-5141-4-git-send-email-shankerd@codeaurora.org> (raw)
In-Reply-To: <1468797992-5141-1-git-send-email-shankerd@codeaurora.org>
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@codeaurora.org>
---
xen/arch/arm/io.c | 39 ++++++++++++++++++++++++---------------
1 file changed, 24 insertions(+), 15 deletions(-)
diff --git a/xen/arch/arm/io.c b/xen/arch/arm/io.c
index 40330f0..e8aa7fa 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,27 +71,31 @@ 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)
+/* This function assumes that mmio regions are not overlapped */
+static int cmp_mmio_handler(const void *key, const void *elem)
{
- 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 domain *d,
+ paddr_t gpa)
+{
+ struct vmmio *vmmio = &d->arch.vmmio;
+ struct mmio_handler key = {.addr = gpa};
+ 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;
@@ -131,6 +136,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);
+
write_unlock(&vmmio->lock);
}
--
Qualcomm Datacenter Technologies, Inc. on behalf of the 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@lists.xen.org
https://lists.xen.org/xen-devel
next prev parent reply other threads:[~2016-07-17 23:26 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-07-17 23:26 [PATCH V2 0/4] Change fixed mmio handlers to a variable number Shanker Donthineni
2016-07-17 23:26 ` [PATCH V2 1/4] arm/io: Use separate memory allocation for mmio handlers Shanker Donthineni
2016-07-17 23:26 ` [PATCH V2 2/4] xen: Add generic implementation of binary search Shanker Donthineni
2016-07-20 11:25 ` Julien Grall
2016-07-20 11:33 ` Julien Grall
2016-07-17 23:26 ` Shanker Donthineni [this message]
2016-07-17 23:26 ` [PATCH V2 4/4] arm/vgic: Change fixed number of mmio handlers to variable number Shanker Donthineni
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=1468797992-5141-4-git-send-email-shankerd@codeaurora.org \
--to=shankerd@codeaurora.org \
--cc=George.Dunlap@eu.citrix.com \
--cc=andrew.cooper3@citrix.com \
--cc=ian.jackson@eu.citrix.com \
--cc=jbeulich@suse.com \
--cc=julien.grall@arm.com \
--cc=pelcan@codeaurora.org \
--cc=sstabellini@kernel.org \
--cc=tim@xen.org \
--cc=vikrams@codeaurora.org \
--cc=wei.liu2@citrix.com \
--cc=xen-devel@lists.xensource.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).