[Xen-devel] [PATCH v5 2/2] Refactor rangeset structure for better performance.
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.
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..cde0d06 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 )
{
-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 )
+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 )
+{
+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
Re: [Xen-devel] [PATCH v5 2/2] Refactor rangeset structure for better performance.
> -Original Message-
> From: Yu Zhang [mailto:yu.c.zh...@linux.intel.com]
> Sent: 14 August 2015 13:03
> To: xen-devel@lists.xen.org; Paul Durrant; Ian Jackson; Stefano Stabellini;
> Ian
> Campbell; Wei Liu; Keir (Xen.org); jbeul...@suse.com; Andrew Cooper
> Cc: Kevin Tian; zhiyuan...@intel.com
> Subject: [PATCH v5 2/2] Refactor rangeset structure for better performance.
>
> 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.
>
> Signed-off-by: Yu Zhang
Looks ok to me :-)
Reviewed-by: Paul Durrant
> ---
> 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..cde0d06 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 )
> {
> -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 )
> +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 )
> +{
> +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);
