[Top] [All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [Xen-devel] [PATCH] switch rangeset's lock to rwlock

Do the searches ever get long enough that a read lock helps? If any of the rangesets is getting large and making the searches slow then it would be quite easy to switch from linked list to red-black tree?

I don't mind using a rwlock here though.
Acked-by: Keir Fraser <keir@xxxxxxx>

 -- Keir
30 September 2014 13:01

If Konrad's happy I am too. :)
Acked-by: Tim Deegan <tim@xxxxxxx>

Tim.

30 September 2014 09:50
On 19.09.14 at 18:32, <konrad.wilk@xxxxxxxxxx> wrote:

On Fri, Sep 12, 2014 at 01:55:07PM +0100, Jan Beulich wrote:

As a general library routine, it should behave as efficiently as
possible, even if at present no significant contention is known here.


Reviewed-by: Konrad Rzeszutek Wilk <konrad.wilk@xxxxxxxxxx>

I am comfortable with this going to Xen 4.5.


Anyone of you wanting to ack this then, or should I nevertheless
postpone it until after 4.5?

Jan


Signed-off-by: Jan Beulich <jbeulich@xxxxxxxx>
---
With the widened use of rangesets I'd like to re-suggest this change
which I had posted already a couple of years back.

--- a/xen/common/rangeset.c
+++ b/xen/common/rangeset.c
@@ -28,7 +28,7 @@ struct rangeset {
 
     /* Number of ranges that can be allocated */
     long             nr_ranges;
-    spinlock_t       lock;
+    rwlock_t         lock;
 
     /* Pretty-printing name. */
     char             name[32];
@@ -120,7 +120,7 @@ int rangeset_add_range(
 
     ASSERT(s <= e);
 
-    spin_lock(&r->lock);
+    write_lock(&r->lock);
 
     x = find_range(r, s);
     y = find_range(r, e);
@@ -176,7 +176,7 @@ int rangeset_add_range(
     }
 
  out:
-    spin_unlock(&r->lock);
+    write_unlock(&r->lock);
     return rc;
 }
 
@@ -188,7 +188,7 @@ int rangeset_remove_range(
 
     ASSERT(s <= e);
 
-    spin_lock(&r->lock);
+    write_lock(&r->lock);
 
     x = find_range(r, s);
     y = find_range(r, e);
@@ -244,7 +244,7 @@ int rangeset_remove_range(
     }
 
  out:
-    spin_unlock(&r->lock);
+    write_unlock(&r->lock);
     return rc;
 }
 
@@ -256,10 +256,10 @@ int rangeset_contains_range(
 
     ASSERT(s <= e);
 
-    spin_lock(&r->lock);
+    read_lock(&r->lock);
     x = find_range(r, s);
     contains = (x && (x->e >= e));
-    spin_unlock(&r->lock);
+    read_unlock(&r->lock);
 
     return contains;
 }
@@ -272,10 +272,10 @@ int rangeset_overlaps_range(
 
     ASSERT(s <= e);
 
-    spin_lock(&r->lock);
+    read_lock(&r->lock);
     x = find_range(r, e);
     overlaps = (x && (s <= x->e));
-    spin_unlock(&r->lock);
+    read_unlock(&r->lock);
 
     return overlaps;
 }
@@ -287,13 +287,13 @@ int rangeset_report_ranges(
     struct range *x;
     int rc = 0;
 
-    spin_lock(&r->lock);
+    read_lock(&r->lock);
 
     for ( x = find_range(r, s); x && (x->s <= e) && !rc; x = next_range(r, x) )
         if ( x->e >= s )
             rc = cb(max(x->s, s), min(x->e, e), ctxt);
 
-    spin_unlock(&r->lock);
+    read_unlock(&r->lock);
 
     return rc;
 }
@@ -331,7 +331,7 @@ struct rangeset *rangeset_new(
     if ( r == NULL )
         return NULL;
 
-    spin_lock_init(&r->lock);
+    rwlock_init(&r->lock);
     INIT_LIST_HEAD(&r->range_list);
     r->nr_ranges = -1;
 
@@ -414,21 +414,21 @@ void rangeset_swap(struct rangeset *a, s
 
     if ( a < b )
     {
-        spin_lock(&a->lock);
-        spin_lock(&b->lock);
+        write_lock(&a->lock);
+        write_lock(&b->lock);
     }
     else
     {
-        spin_lock(&b->lock);
-        spin_lock(&a->lock);
+        write_lock(&b->lock);
+        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);
 
-    spin_unlock(&a->lock);
-    spin_unlock(&b->lock);
+    write_unlock(&a->lock);
+    write_unlock(&b->lock);
 }
 
 /*****************************
@@ -446,7 +446,7 @@ void rangeset_printk(
     int nr_printed = 0;
     struct range *x;
 
-    spin_lock(&r->lock);
+    read_lock(&r->lock);
 
     printk("%-10s {", r->name);
 
@@ -465,7 +465,7 @@ void rangeset_printk(
 
     printk(" }");
 
-    spin_unlock(&r->lock);
+    read_unlock(&r->lock);
 }
 
 void rangeset_domain_printk(




switch rangeset's lock to rwlock

As a general library routine, it should behave as efficiently as
possible, even if at present no significant contention is known here.

Signed-off-by: Jan Beulich <jbeulich@xxxxxxxx>
---
With the widened use of rangesets I'd like to re-suggest this change
which I had posted already a couple of years back.

--- a/xen/common/rangeset.c
+++ b/xen/common/rangeset.c
@@ -28,7 +28,7 @@ struct rangeset {
 
     /* Number of ranges that can be allocated */
     long             nr_ranges;
-    spinlock_t       lock;
+    rwlock_t         lock;
 
     /* Pretty-printing name. */
     char             name[32];
@@ -120,7 +120,7 @@ int rangeset_add_range(
 
     ASSERT(s <= e);
 
-    spin_lock(&r->lock);
+    write_lock(&r->lock);
 
     x = find_range(r, s);
     y = find_range(r, e);
@@ -176,7 +176,7 @@ int rangeset_add_range(
     }
 
  out:
-    spin_unlock(&r->lock);
+    write_unlock(&r->lock);
     return rc;
 }
 
@@ -188,7 +188,7 @@ int rangeset_remove_range(
 
     ASSERT(s <= e);
 
-    spin_lock(&r->lock);
+    write_lock(&r->lock);
 
     x = find_range(r, s);
     y = find_range(r, e);
@@ -244,7 +244,7 @@ int rangeset_remove_range(
     }
 
  out:
-    spin_unlock(&r->lock);
+    write_unlock(&r->lock);
     return rc;
 }
 
@@ -256,10 +256,10 @@ int rangeset_contains_range(
 
     ASSERT(s <= e);
 
-    spin_lock(&r->lock);
+    read_lock(&r->lock);
     x = find_range(r, s);
     contains = (x && (x->e >= e));
-    spin_unlock(&r->lock);
+    read_unlock(&r->lock);
 
     return contains;
 }
@@ -272,10 +272,10 @@ int rangeset_overlaps_range(
 
     ASSERT(s <= e);
 
-    spin_lock(&r->lock);
+    read_lock(&r->lock);
     x = find_range(r, e);
     overlaps = (x && (s <= x->e));
-    spin_unlock(&r->lock);
+    read_unlock(&r->lock);
 
     return overlaps;
 }
@@ -287,13 +287,13 @@ int rangeset_report_ranges(
     struct range *x;
     int rc = 0;
 
-    spin_lock(&r->lock);
+    read_lock(&r->lock);
 
     for ( x = find_range(r, s); x && (x->s <= e) && !rc; x = next_range(r, x) )
         if ( x->e >= s )
             rc = cb(max(x->s, s), min(x->e, e), ctxt);
 
-    spin_unlock(&r->lock);
+    read_unlock(&r->lock);
 
     return rc;
 }
@@ -331,7 +331,7 @@ struct rangeset *rangeset_new(
     if ( r == NULL )
         return NULL;
 
-    spin_lock_init(&r->lock);
+    rwlock_init(&r->lock);
     INIT_LIST_HEAD(&r->range_list);
     r->nr_ranges = -1;
 
@@ -414,21 +414,21 @@ void rangeset_swap(struct rangeset *a, s
 
     if ( a < b )
     {
-        spin_lock(&a->lock);
-        spin_lock(&b->lock);
+        write_lock(&a->lock);
+        write_lock(&b->lock);
     }
     else
     {
-        spin_lock(&b->lock);
-        spin_lock(&a->lock);
+        write_lock(&b->lock);
+        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);
 
-    spin_unlock(&a->lock);
-    spin_unlock(&b->lock);
+    write_unlock(&a->lock);
+    write_unlock(&b->lock);
 }
 
 /*****************************
@@ -446,7 +446,7 @@ void rangeset_printk(
     int nr_printed = 0;
     struct range *x;
 
-    spin_lock(&r->lock);
+    read_lock(&r->lock);
 
     printk("%-10s {", r->name);
 
@@ -465,7 +465,7 @@ void rangeset_printk(
 
     printk(" }");
 
-    spin_unlock(&r->lock);
+    read_unlock(&r->lock);
 }
 
 void rangeset_domain_printk(

_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx 
http://lists.xen.org/xen-devel
19 September 2014 17:32
On Fri, Sep 12, 2014 at 01:55:07PM +0100, Jan Beulich wrote:

As a general library routine, it should behave as efficiently as
possible, even if at present no significant contention is known here.



Reviewed-by: Konrad Rzeszutek Wilk <konrad.wilk@xxxxxxxxxx>

I am comfortable with this going to Xen 4.5.


Signed-off-by: Jan Beulich <jbeulich@xxxxxxxx>
---
With the widened use of rangesets I'd like to re-suggest this change
which I had posted already a couple of years back.

--- a/xen/common/rangeset.c
+++ b/xen/common/rangeset.c
@@ -28,7 +28,7 @@ struct rangeset {
 
     /* Number of ranges that can be allocated */
     long             nr_ranges;
-    spinlock_t       lock;
+    rwlock_t         lock;
 
     /* Pretty-printing name. */
     char             name[32];
@@ -120,7 +120,7 @@ int rangeset_add_range(
 
     ASSERT(s <= e);
 
-    spin_lock(&r->lock);
+    write_lock(&r->lock);
 
     x = find_range(r, s);
     y = find_range(r, e);
@@ -176,7 +176,7 @@ int rangeset_add_range(
     }
 
  out:
-    spin_unlock(&r->lock);
+    write_unlock(&r->lock);
     return rc;
 }
 
@@ -188,7 +188,7 @@ int rangeset_remove_range(
 
     ASSERT(s <= e);
 
-    spin_lock(&r->lock);
+    write_lock(&r->lock);
 
     x = find_range(r, s);
     y = find_range(r, e);
@@ -244,7 +244,7 @@ int rangeset_remove_range(
     }
 
  out:
-    spin_unlock(&r->lock);
+    write_unlock(&r->lock);
     return rc;
 }
 
@@ -256,10 +256,10 @@ int rangeset_contains_range(
 
     ASSERT(s <= e);
 
-    spin_lock(&r->lock);
+    read_lock(&r->lock);
     x = find_range(r, s);
     contains = (x && (x->e >= e));
-    spin_unlock(&r->lock);
+    read_unlock(&r->lock);
 
     return contains;
 }
@@ -272,10 +272,10 @@ int rangeset_overlaps_range(
 
     ASSERT(s <= e);
 
-    spin_lock(&r->lock);
+    read_lock(&r->lock);
     x = find_range(r, e);
     overlaps = (x && (s <= x->e));
-    spin_unlock(&r->lock);
+    read_unlock(&r->lock);
 
     return overlaps;
 }
@@ -287,13 +287,13 @@ int rangeset_report_ranges(
     struct range *x;
     int rc = 0;
 
-    spin_lock(&r->lock);
+    read_lock(&r->lock);
 
     for ( x = find_range(r, s); x && (x->s <= e) && !rc; x = next_range(r, x) )
         if ( x->e >= s )
             rc = cb(max(x->s, s), min(x->e, e), ctxt);
 
-    spin_unlock(&r->lock);
+    read_unlock(&r->lock);
 
     return rc;
 }
@@ -331,7 +331,7 @@ struct rangeset *rangeset_new(
     if ( r == NULL )
         return NULL;
 
-    spin_lock_init(&r->lock);
+    rwlock_init(&r->lock);
     INIT_LIST_HEAD(&r->range_list);
     r->nr_ranges = -1;
 
@@ -414,21 +414,21 @@ void rangeset_swap(struct rangeset *a, s
 
     if ( a < b )
     {
-        spin_lock(&a->lock);
-        spin_lock(&b->lock);
+        write_lock(&a->lock);
+        write_lock(&b->lock);
     }
     else
     {
-        spin_lock(&b->lock);
-        spin_lock(&a->lock);
+        write_lock(&b->lock);
+        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);
 
-    spin_unlock(&a->lock);
-    spin_unlock(&b->lock);
+    write_unlock(&a->lock);
+    write_unlock(&b->lock);
 }
 
 /*****************************
@@ -446,7 +446,7 @@ void rangeset_printk(
     int nr_printed = 0;
     struct range *x;
 
-    spin_lock(&r->lock);
+    read_lock(&r->lock);
 
     printk("%-10s {", r->name);
 
@@ -465,7 +465,7 @@ void rangeset_printk(
 
     printk(" }");
 
-    spin_unlock(&r->lock);
+    read_unlock(&r->lock);
 }
 
 void rangeset_domain_printk(






switch rangeset's lock to rwlock

As a general library routine, it should behave as efficiently as
possible, even if at present no significant contention is known here.

Signed-off-by: Jan Beulich <jbeulich@xxxxxxxx>
---
With the widened use of rangesets I'd like to re-suggest this change
which I had posted already a couple of years back.

--- a/xen/common/rangeset.c
+++ b/xen/common/rangeset.c
@@ -28,7 +28,7 @@ struct rangeset {
 
     /* Number of ranges that can be allocated */
     long             nr_ranges;
-    spinlock_t       lock;
+    rwlock_t         lock;
 
     /* Pretty-printing name. */
     char             name[32];
@@ -120,7 +120,7 @@ int rangeset_add_range(
 
     ASSERT(s <= e);
 
-    spin_lock(&r->lock);
+    write_lock(&r->lock);
 
     x = find_range(r, s);
     y = find_range(r, e);
@@ -176,7 +176,7 @@ int rangeset_add_range(
     }
 
  out:
-    spin_unlock(&r->lock);
+    write_unlock(&r->lock);
     return rc;
 }
 
@@ -188,7 +188,7 @@ int rangeset_remove_range(
 
     ASSERT(s <= e);
 
-    spin_lock(&r->lock);
+    write_lock(&r->lock);
 
     x = find_range(r, s);
     y = find_range(r, e);
@@ -244,7 +244,7 @@ int rangeset_remove_range(
     }
 
  out:
-    spin_unlock(&r->lock);
+    write_unlock(&r->lock);
     return rc;
 }
 
@@ -256,10 +256,10 @@ int rangeset_contains_range(
 
     ASSERT(s <= e);
 
-    spin_lock(&r->lock);
+    read_lock(&r->lock);
     x = find_range(r, s);
     contains = (x && (x->e >= e));
-    spin_unlock(&r->lock);
+    read_unlock(&r->lock);
 
     return contains;
 }
@@ -272,10 +272,10 @@ int rangeset_overlaps_range(
 
     ASSERT(s <= e);
 
-    spin_lock(&r->lock);
+    read_lock(&r->lock);
     x = find_range(r, e);
     overlaps = (x && (s <= x->e));
-    spin_unlock(&r->lock);
+    read_unlock(&r->lock);
 
     return overlaps;
 }
@@ -287,13 +287,13 @@ int rangeset_report_ranges(
     struct range *x;
     int rc = 0;
 
-    spin_lock(&r->lock);
+    read_lock(&r->lock);
 
     for ( x = find_range(r, s); x && (x->s <= e) && !rc; x = next_range(r, x) )
         if ( x->e >= s )
             rc = cb(max(x->s, s), min(x->e, e), ctxt);
 
-    spin_unlock(&r->lock);
+    read_unlock(&r->lock);
 
     return rc;
 }
@@ -331,7 +331,7 @@ struct rangeset *rangeset_new(
     if ( r == NULL )
         return NULL;
 
-    spin_lock_init(&r->lock);
+    rwlock_init(&r->lock);
     INIT_LIST_HEAD(&r->range_list);
     r->nr_ranges = -1;
 
@@ -414,21 +414,21 @@ void rangeset_swap(struct rangeset *a, s
 
     if ( a < b )
     {
-        spin_lock(&a->lock);
-        spin_lock(&b->lock);
+        write_lock(&a->lock);
+        write_lock(&b->lock);
     }
     else
     {
-        spin_lock(&b->lock);
-        spin_lock(&a->lock);
+        write_lock(&b->lock);
+        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);
 
-    spin_unlock(&a->lock);
-    spin_unlock(&b->lock);
+    write_unlock(&a->lock);
+    write_unlock(&b->lock);
 }
 
 /*****************************
@@ -446,7 +446,7 @@ void rangeset_printk(
     int nr_printed = 0;
     struct range *x;
 
-    spin_lock(&r->lock);
+    read_lock(&r->lock);
 
     printk("%-10s {", r->name);
 
@@ -465,7 +465,7 @@ void rangeset_printk(
 
     printk(" }");
 
-    spin_unlock(&r->lock);
+    read_unlock(&r->lock);
 }
 
 void rangeset_domain_printk(



_______________________________________________
Xen-devel mailing list
Xen-devel@xxxxxxxxxxxxx
http://lists.xen.org/xen-devel
12 September 2014 13:55
As a general library routine, it should behave as efficiently as
possible, even if at present no significant contention is known here.

Signed-off-by: Jan Beulich <jbeulich@xxxxxxxx>
---
With the widened use of rangesets I'd like to re-suggest this change
which I had posted already a couple of years back.

--- a/xen/common/rangeset.c
+++ b/xen/common/rangeset.c
@@ -28,7 +28,7 @@ struct rangeset {

/* Number of ranges that can be allocated */
long nr_ranges;
- spinlock_t lock;
+ rwlock_t lock;

/* Pretty-printing name. */
char name[32];
@@ -120,7 +120,7 @@ int rangeset_add_range(

ASSERT(s <= e);

- spin_lock(&r->lock);
+ write_lock(&r->lock);

x = find_range(r, s);
y = find_range(r, e);
@@ -176,7 +176,7 @@ int rangeset_add_range(
}

out:
- spin_unlock(&r->lock);
+ write_unlock(&r->lock);
return rc;
}

@@ -188,7 +188,7 @@ int rangeset_remove_range(

ASSERT(s <= e);

- spin_lock(&r->lock);
+ write_lock(&r->lock);

x = find_range(r, s);
y = find_range(r, e);
@@ -244,7 +244,7 @@ int rangeset_remove_range(
}

out:
- spin_unlock(&r->lock);
+ write_unlock(&r->lock);
return rc;
}

@@ -256,10 +256,10 @@ int rangeset_contains_range(

ASSERT(s <= e);

- spin_lock(&r->lock);
+ read_lock(&r->lock);
x = find_range(r, s);
contains = (x && (x->e >= e));
- spin_unlock(&r->lock);
+ read_unlock(&r->lock);

return contains;
}
@@ -272,10 +272,10 @@ int rangeset_overlaps_range(

ASSERT(s <= e);

- spin_lock(&r->lock);
+ read_lock(&r->lock);
x = find_range(r, e);
overlaps = (x && (s <= x->e));
- spin_unlock(&r->lock);
+ read_unlock(&r->lock);

return overlaps;
}
@@ -287,13 +287,13 @@ int rangeset_report_ranges(
struct range *x;
int rc = 0;

- spin_lock(&r->lock);
+ read_lock(&r->lock);

for ( x = find_range(r, s); x && (x->s <= e) && !rc; x = next_range(r, x) )
if ( x->e >= s )
rc = cb(max(x->s, s), min(x->e, e), ctxt);

- spin_unlock(&r->lock);
+ read_unlock(&r->lock);

return rc;
}
@@ -331,7 +331,7 @@ struct rangeset *rangeset_new(
if ( r == NULL )
return NULL;

- spin_lock_init(&r->lock);
+ rwlock_init(&r->lock);
INIT_LIST_HEAD(&r->range_list);
r->nr_ranges = -1;

@@ -414,21 +414,21 @@ void rangeset_swap(struct rangeset *a, s

if ( a < b )
{
- spin_lock(&a->lock);
- spin_lock(&b->lock);
+ write_lock(&a->lock);
+ write_lock(&b->lock);
}
else
{
- spin_lock(&b->lock);
- spin_lock(&a->lock);
+ write_lock(&b->lock);
+ 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);

- spin_unlock(&a->lock);
- spin_unlock(&b->lock);
+ write_unlock(&a->lock);
+ write_unlock(&b->lock);
}

/*****************************
@@ -446,7 +446,7 @@ void rangeset_printk(
int nr_printed = 0;
struct range *x;

- spin_lock(&r->lock);
+ read_lock(&r->lock);

printk("%-10s {", r->name);

@@ -465,7 +465,7 @@ void rangeset_printk(

printk(" }");

- spin_unlock(&r->lock);
+ read_unlock(&r->lock);
}

void rangeset_domain_printk(



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

 

©2013 Xen Project, A Linux Foundation Collaborative Project. All Rights Reserved.
Linux Foundation is a registered trademark of The Linux Foundation.
Xen Project is a trademark of The Linux Foundation.

Rackspace

Lists.xenproject.org is hosted with RackSpace, monitoring our
servers 24x7x365 and backed by RackSpace's Fanatical Support®.