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

["Yu, Zhang" <yu.c.zhang@linux.intel.com>]

On 8/13/2015 6:33 PM, Paul Durrant wrote:
>> -----Original Message-----
>> From: Yu Zhang [mailto:yu.c.zhang@linux.intel.com]
>> Sent: 13 August 2015 11:06
>> To: xen-devel@lists.xen.org; Paul Durrant; Ian Jackson; Stefano Stabellini; Ian
>> Campbell; Wei Liu; Keir (Xen.org); jbeulich@suse.com; Andrew Cooper
>> Cc: Kevin Tian; zhiyuan.lv@intel.com
>> 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@linux.intel.com>
>> ---
>>   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.

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@lists.xen.org
> http://lists.xen.org/xen-devel
>
>