From patchwork Tue Jan 19 09:27:56 2016 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Yu Zhang X-Patchwork-Id: 8059381 Return-Path: X-Original-To: patchwork-xen-devel@patchwork.kernel.org Delivered-To: patchwork-parsemail@patchwork2.web.kernel.org Received: from mail.kernel.org (mail.kernel.org [198.145.29.136]) by patchwork2.web.kernel.org (Postfix) with ESMTP id C81A6BEEE5 for ; Tue, 19 Jan 2016 09:39:46 +0000 (UTC) Received: from mail.kernel.org (localhost [127.0.0.1]) by mail.kernel.org (Postfix) with ESMTP id C56AC203A1 for ; Tue, 19 Jan 2016 09:39:45 +0000 (UTC) Received: from lists.xen.org (lists.xenproject.org [50.57.142.19]) (using TLSv1 with cipher AES256-SHA (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPS id B382E20225 for ; Tue, 19 Jan 2016 09:39:44 +0000 (UTC) Received: from localhost ([127.0.0.1] helo=lists.xen.org) by lists.xen.org with esmtp (Exim 4.72) (envelope-from ) id 1aLSiW-0004Rz-05; Tue, 19 Jan 2016 09:36:48 +0000 Received: from mail6.bemta5.messagelabs.com ([195.245.231.135]) by lists.xen.org with esmtp (Exim 4.72) (envelope-from ) id 1aLSiU-0004Ru-5W for xen-devel@lists.xen.org; Tue, 19 Jan 2016 09:36:46 +0000 Received: from [85.158.139.211] by server-9.bemta-5.messagelabs.com id 27/04-30270-DA30E965; Tue, 19 Jan 2016 09:36:45 +0000 X-Env-Sender: yu.c.zhang@linux.intel.com X-Msg-Ref: server-15.tower-206.messagelabs.com!1453196201!8292738!2 X-Originating-IP: [192.55.52.93] X-SpamReason: No, hits=0.0 required=7.0 tests=sa_preprocessor: VHJ1c3RlZCBJUDogMTkyLjU1LjUyLjkzID0+IDMyNDY2NQ==\n X-StarScan-Received: X-StarScan-Version: 7.35.1; banners=-,-,- X-VirusChecked: Checked Received: (qmail 44484 invoked from network); 19 Jan 2016 09:36:44 -0000 Received: from mga11.intel.com (HELO mga11.intel.com) (192.55.52.93) by server-15.tower-206.messagelabs.com with SMTP; 19 Jan 2016 09:36:44 -0000 Received: from orsmga003.jf.intel.com ([10.7.209.27]) by fmsmga102.fm.intel.com with ESMTP; 19 Jan 2016 01:36:44 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.22,316,1449561600"; d="scan'208";a="730085622" Received: from zhangyu-optiplex-9020.bj.intel.com ([10.238.144.104]) by orsmga003.jf.intel.com with ESMTP; 19 Jan 2016 01:36:41 -0800 From: Yu Zhang To: xen-devel@lists.xen.org Date: Tue, 19 Jan 2016 17:27:56 +0800 Message-Id: <1453195678-25944-2-git-send-email-yu.c.zhang@linux.intel.com> X-Mailer: git-send-email 1.9.1 In-Reply-To: <1453195678-25944-1-git-send-email-yu.c.zhang@linux.intel.com> References: <1453195678-25944-1-git-send-email-yu.c.zhang@linux.intel.com> Cc: kevin.tian@intel.com, keir@xen.org, stefano.stabellini@eu.citrix.com, andrew.cooper3@citrix.com, Paul.Durrant@citrix.com, zhiyuan.lv@intel.com, jbeulich@suse.com, wei.liu2@citrix.com Subject: [Xen-devel] [PATCH v10 1/3] Refactor rangeset structure for better performance. X-BeenThere: xen-devel@lists.xen.org X-Mailman-Version: 2.1.13 Precedence: list List-Id: Xen developer discussion List-Unsubscribe: , List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Sender: xen-devel-bounces@lists.xen.org Errors-To: xen-devel-bounces@lists.xen.org X-Spam-Status: No, score=-4.2 required=5.0 tests=BAYES_00, RCVD_IN_DNSWL_MED, UNPARSEABLE_RELAY autolearn=unavailable version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on mail.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP This patch refactors struct rangeset to base it on the red-black tree structure, instead of on the current doubly linked list. By now, ioreq leverages rangeset to keep track of the IO/memory resources to be emulated. Yet when number of ranges inside one ioreq server is very high, traversing a doubly linked list could be time consuming. With this patch, the time complexity for searching a rangeset can be improved from O(n) to O(log(n)). Interfaces of rangeset still remain the same, and no new APIs introduced. Reviewed-by: Paul Durrant Signed-off-by: Shuai Ruan Signed-off-by: Yu Zhang --- xen/common/rangeset.c | 82 +++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 60 insertions(+), 22 deletions(-) diff --git a/xen/common/rangeset.c b/xen/common/rangeset.c index 6c6293c..d15d8d5 100644 --- a/xen/common/rangeset.c +++ b/xen/common/rangeset.c @@ -10,11 +10,12 @@ #include #include #include +#include #include /* An inclusive range [s,e] and pointer to next range in ascending order. */ struct range { - struct list_head list; + struct rb_node node; unsigned long s, e; }; @@ -24,7 +25,7 @@ struct rangeset { struct domain *domain; /* Ordered list of ranges contained in this set, and protecting lock. */ - struct list_head range_list; + struct rb_root range_tree; /* Number of ranges that can be allocated */ long nr_ranges; @@ -45,41 +46,78 @@ struct rangeset { static struct range *find_range( struct rangeset *r, unsigned long s) { - struct range *x = NULL, *y; + struct rb_node *node; + struct range *x; + struct range *prev = NULL; - list_for_each_entry ( y, &r->range_list, list ) + node = r->range_tree.rb_node; + while ( node != NULL ) { - if ( y->s > s ) - break; - x = y; + x = container_of(node, struct range, node); + if ( (s >= x->s) && (s <= x->e) ) + return x; + if ( s < x->s ) + node = node->rb_left; + else + { + prev = x; + node = node->rb_right; + } } - return x; + return prev; } /* Return the lowest range in the set r, or NULL if r is empty. */ static struct range *first_range( struct rangeset *r) { - if ( list_empty(&r->range_list) ) - return NULL; - return list_entry(r->range_list.next, struct range, list); + struct rb_node *node; + + node = rb_first(&r->range_tree); + if ( node != NULL ) + return container_of(node, struct range, node); + + return NULL; } /* Return range following x in ascending order, or NULL if x is the highest. */ static struct range *next_range( struct rangeset *r, struct range *x) { - if ( x->list.next == &r->range_list ) - return NULL; - return list_entry(x->list.next, struct range, list); + struct rb_node *node; + + node = rb_next(&x->node); + if ( node != NULL ) + return container_of(node, struct range, node); + + return NULL; } /* Insert range y after range x in r. Insert as first range if x is NULL. */ static void insert_range( struct rangeset *r, struct range *x, struct range *y) { - list_add(&y->list, (x != NULL) ? &x->list : &r->range_list); + struct rb_node **node; + struct rb_node *parent = NULL; + + if ( x == NULL ) + node = &r->range_tree.rb_node; + else + { + node = &x->node.rb_right; + parent = &x->node; + } + + while ( *node != NULL ) + { + parent = *node; + node = &parent->rb_left; + } + + /* Add new node and rebalance the red-black tree. */ + rb_link_node(&y->node, parent, node); + rb_insert_color(&y->node, &r->range_tree); } /* Remove a range from its list and free it. */ @@ -88,7 +126,7 @@ static void destroy_range( { r->nr_ranges++; - list_del(&x->list); + rb_erase(&x->node, &r->range_tree); xfree(x); } @@ -319,7 +357,7 @@ bool_t rangeset_contains_singleton( bool_t rangeset_is_empty( const struct rangeset *r) { - return ((r == NULL) || list_empty(&r->range_list)); + return ((r == NULL) || RB_EMPTY_ROOT(&r->range_tree)); } struct rangeset *rangeset_new( @@ -332,7 +370,7 @@ struct rangeset *rangeset_new( return NULL; rwlock_init(&r->lock); - INIT_LIST_HEAD(&r->range_list); + r->range_tree = RB_ROOT; r->nr_ranges = -1; BUG_ON(flags & ~RANGESETF_prettyprint_hex); @@ -410,7 +448,7 @@ void rangeset_domain_destroy( void rangeset_swap(struct rangeset *a, struct rangeset *b) { - LIST_HEAD(tmp); + struct rb_node *tmp; if ( a < b ) { @@ -423,9 +461,9 @@ void rangeset_swap(struct rangeset *a, struct rangeset *b) write_lock(&a->lock); } - list_splice_init(&a->range_list, &tmp); - list_splice_init(&b->range_list, &a->range_list); - list_splice(&tmp, &b->range_list); + tmp = a->range_tree.rb_node; + a->range_tree.rb_node = b->range_tree.rb_node; + b->range_tree.rb_node = tmp; write_unlock(&a->lock); write_unlock(&b->lock);