From patchwork Thu Jul 14 16:18:00 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Shanker Donthineni X-Patchwork-Id: 9230113 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 9AEA1607D0 for ; Thu, 14 Jul 2016 16:21:00 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 8BCD127F96 for ; Thu, 14 Jul 2016 16:21:00 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 7FF9E28285; Thu, 14 Jul 2016 16:21:00 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-4.2 required=2.0 tests=BAYES_00, RCVD_IN_DNSWL_MED autolearn=ham version=3.3.1 Received: from lists.xenproject.org (lists.xenproject.org [192.237.175.120]) (using TLSv1.2 with cipher AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by mail.wl.linuxfoundation.org (Postfix) with ESMTPS id CF3F027F96 for ; Thu, 14 Jul 2016 16:20:59 +0000 (UTC) Received: from localhost ([127.0.0.1] helo=lists.xenproject.org) by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bNjLe-0002Lq-DX; Thu, 14 Jul 2016 16:18:50 +0000 Received: from mail6.bemta6.messagelabs.com ([85.158.143.247]) by lists.xenproject.org with esmtp (Exim 4.84_2) (envelope-from ) id 1bNjLc-0002Jk-CL for xen-devel@lists.xensource.com; Thu, 14 Jul 2016 16:18:48 +0000 Received: from [85.158.143.35] by server-3.bemta-6.messagelabs.com id FB/CB-22092-76BB7875; Thu, 14 Jul 2016 16:18:47 +0000 X-Brightmail-Tracker: H4sIAAAAAAAAA+NgFmphkeJIrShJLcpLzFFi42I5NlE2QTd9d3u 4wa9PAhb3prxnd2D02N63iz2AMYo1My8pvyKBNePEjga2gnXSFWfPPmduYNwu2sXIySEkUCQx f955FhBbQiBaYt2GY+wQNp/ExRc/mCDsWomHp58ydjFyAdXfYpKYs3ADWxcjBwebgJHEv95ck BoRgUZGib5ONxCbWaBeYmPvGrBeYYEAiZ+vb4LZLAKqEodntTOC2LwC7hLd86YyQsyXkzh5bD IriM0p4CHxpK+PGeI2d4l7r/rZJzDyLWBkWMWoXpxaVJZapGuol1SUmZ5RkpuYmaNraGCml5t aXJyYnpqTmFSsl5yfu4kRGCIMQLCDcedzp0OMkhxMSqK82v1t4UJ8SfkplRmJxRnxRaU5qcWH GDU4OAR616y+wCjFkpefl6okwWu6qz1cSLAoNT21Ii0zBxjEMKUSHDxKIryGIGne4oLE3OLMd IjUKUZFKXFeTpCEAEgiozQPrg0WOZcYZaWEeRmBjhLiKUgtys0sQZV/xSjOwagkzGsDMoUnM6 8EbvoroMVMQIutzcEWlyQipKQaGOWam3yuXQgNqXnMEBVovm6LLme9/8PH/59eZDrONG/L+cc hizU6jIqMJrh/69owe25v1p5u46iSs2cvTw8xUAmK7j8WeavvudVCoerY7ln+X2JEZvMfLXHw 8j1003rp7CuFX2V0Iq+qx0YVXmFOPrLy/t2b+a+5QjxbuJwCFjVs3fBhT8XBJiWW4oxEQy3mo uJEAOZNFfSXAgAA X-Env-Sender: shankerd@codeaurora.org X-Msg-Ref: server-16.tower-21.messagelabs.com!1468513125!19547246!1 X-Originating-IP: [198.145.29.96] X-SpamReason: No, hits=0.0 required=7.0 tests= X-StarScan-Received: X-StarScan-Version: 8.77; banners=-,-,- X-VirusChecked: Checked Received: (qmail 48634 invoked from network); 14 Jul 2016 16:18:47 -0000 Received: from smtp.codeaurora.org (HELO smtp.codeaurora.org) (198.145.29.96) by server-16.tower-21.messagelabs.com with DHE-RSA-AES256-GCM-SHA384 encrypted SMTP; 14 Jul 2016 16:18:47 -0000 Received: by smtp.codeaurora.org (Postfix, from userid 1000) id 7787C611DE; Thu, 14 Jul 2016 16:18:44 +0000 (UTC) Received: from shankerd-ubuntu.qualcomm.com (i-global254.qualcomm.com [199.106.103.254]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-SHA256 (128/128 bits)) (No client certificate requested) (Authenticated sender: shankerd@smtp.codeaurora.org) by smtp.codeaurora.org (Postfix) with ESMTPSA id 43D6860F78; Thu, 14 Jul 2016 16:18:43 +0000 (UTC) From: Shanker Donthineni To: xen-devel , Julien Grall , Stefano Stabellini Date: Thu, 14 Jul 2016 11:18:00 -0500 Message-Id: <1468513081-12002-2-git-send-email-shankerd@codeaurora.org> X-Mailer: git-send-email 1.9.1 In-Reply-To: <1468513081-12002-1-git-send-email-shankerd@codeaurora.org> References: <1468513081-12002-1-git-send-email-shankerd@codeaurora.org> Cc: Philip Elcan , Shanker Donthineni , Vikram Sethi Subject: [Xen-devel] [PATCH V4 10/11] xen/arm: io: Use binary search for mmio handler lookup X-BeenThere: xen-devel@lists.xen.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: xen-devel-bounces@lists.xen.org Sender: "Xen-devel" X-Virus-Scanned: ClamAV using ClamSMTP 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 --- 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 #include #include +#include +#include #include #include @@ -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) { - 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) +{ + struct vmmio *vmmio = &v->domain->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; @@ -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; - handler = find_mmio_handler(v->domain, info->gpa); + handler = find_mmio_handler(v, info->gpa); 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); + write_unlock(&vmmio->lock); }