Re: [Xen-devel] [PATCH v4 2/2] Refactor rangeset structure for better performance.

[Paul Durrant <Paul.Durrant@xxxxxxxxxx>]

> -----Original Message-----
> From: Yu Zhang [mailto:yu.c.zhang@xxxxxxxxxxxxxxx]
> Sent: 13 August 2015 11:06
> To: xen-devel@xxxxxxxxxxxxx; Paul Durrant; Ian Jackson; Stefano Stabellini; 
> Ian
> Campbell; Wei Liu; Keir (Xen.org); jbeulich@xxxxxxxx; Andrew Cooper
> Cc: Kevin Tian; zhiyuan.lv@xxxxxxxxx
> Subject: [PATCH v4 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 <yu.c.zhang@xxxxxxxxxxxxxxx>
> ---
>  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..87b6aab 100644
> --- a/xen/common/rangeset.c
> +++ b/xen/common/rangeset.c
> @@ -10,11 +10,12 @@
>  #include <xen/sched.h>
>  #include <xen/errno.h>
>  #include <xen/rangeset.h>
> +#include <xen/rbtree.h>
>  #include <xsm/xsm.h>
> 
>  /* 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 if ( s > x->s )

Do you need else if there? I think else would do. s either has to be < x->s or 
> x->e to get to this point.

> +        {
> +            prev = x;
> +            node = node->rb_right;
> +        }
>      }
> 
> -    return x;
> +    return prev;

Do you not want to return NULL here? It looks like you'd only get here if there 
was no matching range.

  Paul

>  }
> 
>  /* 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);
>      write_unlock(&b->lock);
> --
> 1.9.1


_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
http://lists.xen.org/xen-devel