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:47
> To: Paul Durrant; xen-devel@xxxxxxxxxxxxx; Ian Jackson; Stefano Stabellini; 
> Ian
> Campbell; Wei Liu; Keir (Xen.org); jbeulich@xxxxxxxx; Andrew Cooper
> Cc: Kevin Tian; zhiyuan.lv@xxxxxxxxx
> Subject: Re: [Xen-devel] [PATCH v4 2/2] Refactor rangeset structure for
> better performance.
> 
> 
> 
> On 8/13/2015 6:33 PM, Paul Durrant wrote:
> >> -----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.
> Thanks. You are right. :)
> >
> >> +        {
> >> +            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.
> Well, prev can either be NULL(like its initial value), or pointing to
> the previous node of the range. It's to keep the original intention of
> routine find_range() - to return the range if found, or return the
> previous one, or NULL.

If that's the correct semantic then that's fine.

  Paul

> 
> B.R.
> Yu
> >
> >    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
> >
> >

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