Re: [lttng-dev] [RFC] adding into middle of RCU list
On Sat, Aug 31, 2013 at 02:32:28PM -0700, Paul E. McKenney wrote: On Thu, Aug 29, 2013 at 07:16:37PM -0700, Josh Triplett wrote: On Thu, Aug 29, 2013 at 05:57:33PM -0700, Paul E. McKenney wrote: On Fri, Aug 23, 2013 at 02:08:22PM -0700, Paul E. McKenney wrote: On Fri, Aug 23, 2013 at 01:16:53PM -0400, Mathieu Desnoyers wrote: #define __rcu_assign_pointer(p, v, space) \ do { \ smp_wmb(); \ (p) = (typeof(*v) __force space *)(v); \ } while (0) Or I need to fix this one as well. ;-) In that vein... Is there anything like typeof() that also preserves sparse's notion of address space? Wrapping an ACCESS_ONCE() around p in the assignment above results in sparse errors. typeof() will preserve sparse's notion of address space as long as you do typeof(p), not typeof(*p): $ cat test.c #define as(n) __attribute__((address_space(n),noderef)) #define __force __attribute__((force)) int main(void) { int target = 0; int as(1) *foo = (__force typeof(target) as(1) *) target; typeof(foo) bar = foo; return *bar; } $ sparse test.c test.c:9:13: warning: dereference of noderef expression Notice that sparse didn't warn on the assignment of foo to bar (because typeof propagated the address space of 1), and warned on the dereference of bar (because typeof propagated noderef). Thank you for the info! Suppose that I want to do something like this: #define __rcu_assign_pointer(p, v, space) \ do { \ smp_wmb(); \ ACCESS_ONCE(p) = (typeof(*v) __force space *)(v); \ } while (0) Now, this does typeof(*p), so as you noted above sparse complains about address-space mismatches. Thus far, I haven't been able to come up with something that (1) does sparse address-space checking, (2) does C type checking, and (3) forces the assignment to be volatile. Any thoughts on how to do this? First of all, if p and v had compatible types *including* address spaces, you wouldn't need the space argument; the following self-contained test case passes both sparse and GCC typechecking: #define as(n) __attribute__((address_space(n),noderef)) #define __force __attribute__((force)) #define ACCESS_ONCE(x) (*(volatile typeof(x) *)(x)) extern void smp_wmb(void); #define rcu_assign_pointer(p, v) \ do { \ smp_wmb(); \ ACCESS_ONCE(p) = (v); \ } while (0) struct foo; int main(void) { struct foo as(1) *dest; struct foo as(1) *src = (void *)0; rcu_assign_pointer(dest, src); return 0; } But in this case, you want dest and src to have compatible types except that dest must have the __rcu address space and src might not. So, let's change the types of dest and src, and add the appropriate cast. The following also passes both GCC and sparse: #define __rcu __attribute__((address_space(4),noderef)) #define __force __attribute__((force)) #define ACCESS_ONCE(x) (*(volatile typeof(x) *)(x)) extern void smp_wmb(void); #define rcu_assign_pointer(p, v) \ do { \ smp_wmb(); \ ACCESS_ONCE(p) = (typeof(*(v)) __rcu __force *)(v); \ } while (0) struct foo { int x; }; int main(void) { struct foo __rcu *dest; struct foo *src = (void *)0; rcu_assign_pointer(dest, src); return 0; } However, that cast forces the source to have the __rcu address space without checking what address space it started out with. If you want to verify that the source has the kernel address space, you can cast to that address space first, *without* __force, which will warn if the source doesn't start out with that address space: #define __kernel __attribute__((address_space(0))) #define __user __attribute__((address_space(1),noderef)) #define __rcu __attribute__((address_space(4),noderef)) #define __force __attribute__((force)) #define ACCESS_ONCE(x) (*(volatile typeof(x) *)(x)) extern void smp_wmb(void); #define rcu_assign_pointer(p, v) \ do { \ smp_wmb(); \ ACCESS_ONCE(p) = (typeof(*(v)) __rcu __force *)(typeof(*(v)) __kernel *)(v); \ } while (0) struct foo { int x; }; int main(void) { struct foo __rcu *dest; struct foo *src = (void *)0; struct foo __user *badsrc = (void *)0; rcu_assign_pointer(dest, src); rcu_assign_pointer(dest, badsrc); return 0; } This produces a warning on the line using badsrc: test.c:23:5: warning: cast removes address space of expression However, that doesn't seem like the most obvious warning, since rcu_assign_pointer doesn't look like a cast, and since it doesn't print the full types involved like most address space warnings do. So, instead, let's add and use a __chk_kernel_ptr function, similar to __chk_user_ptr in compiler.h: #define __kernel __attribute__((address_space(0))) #define __user __attribute__((address_space(1),noderef)) #define __rcu __attribute__((address_space(4),noderef)) #define
Re: [lttng-dev] [RFC] adding into middle of RCU list
On Sun, Sep 01, 2013 at 01:42:10PM -0700, Josh Triplett wrote: On Sat, Aug 31, 2013 at 02:32:28PM -0700, Paul E. McKenney wrote: On Thu, Aug 29, 2013 at 07:16:37PM -0700, Josh Triplett wrote: On Thu, Aug 29, 2013 at 05:57:33PM -0700, Paul E. McKenney wrote: On Fri, Aug 23, 2013 at 02:08:22PM -0700, Paul E. McKenney wrote: On Fri, Aug 23, 2013 at 01:16:53PM -0400, Mathieu Desnoyers wrote: #define __rcu_assign_pointer(p, v, space) \ do { \ smp_wmb(); \ (p) = (typeof(*v) __force space *)(v); \ } while (0) Or I need to fix this one as well. ;-) In that vein... Is there anything like typeof() that also preserves sparse's notion of address space? Wrapping an ACCESS_ONCE() around p in the assignment above results in sparse errors. typeof() will preserve sparse's notion of address space as long as you do typeof(p), not typeof(*p): $ cat test.c #define as(n) __attribute__((address_space(n),noderef)) #define __force __attribute__((force)) int main(void) { int target = 0; int as(1) *foo = (__force typeof(target) as(1) *) target; typeof(foo) bar = foo; return *bar; } $ sparse test.c test.c:9:13: warning: dereference of noderef expression Notice that sparse didn't warn on the assignment of foo to bar (because typeof propagated the address space of 1), and warned on the dereference of bar (because typeof propagated noderef). Thank you for the info! Suppose that I want to do something like this: #define __rcu_assign_pointer(p, v, space) \ do { \ smp_wmb(); \ ACCESS_ONCE(p) = (typeof(*v) __force space *)(v); \ } while (0) Now, this does typeof(*p), so as you noted above sparse complains about address-space mismatches. Thus far, I haven't been able to come up with something that (1) does sparse address-space checking, (2) does C type checking, and (3) forces the assignment to be volatile. Any thoughts on how to do this? First of all, if p and v had compatible types *including* address spaces, you wouldn't need the space argument; the following self-contained test case passes both sparse and GCC typechecking: #define as(n) __attribute__((address_space(n),noderef)) #define __force __attribute__((force)) #define ACCESS_ONCE(x) (*(volatile typeof(x) *)(x)) extern void smp_wmb(void); #define rcu_assign_pointer(p, v) \ do { \ smp_wmb(); \ ACCESS_ONCE(p) = (v); \ } while (0) struct foo; int main(void) { struct foo as(1) *dest; struct foo as(1) *src = (void *)0; rcu_assign_pointer(dest, src); return 0; } But in this case, you want dest and src to have compatible types except that dest must have the __rcu address space and src might not. So, let's change the types of dest and src, and add the appropriate cast. The following also passes both GCC and sparse: #define __rcu __attribute__((address_space(4),noderef)) #define __force __attribute__((force)) #define ACCESS_ONCE(x) (*(volatile typeof(x) *)(x)) extern void smp_wmb(void); #define rcu_assign_pointer(p, v) \ do { \ smp_wmb(); \ ACCESS_ONCE(p) = (typeof(*(v)) __rcu __force *)(v); \ } while (0) struct foo { int x; }; int main(void) { struct foo __rcu *dest; struct foo *src = (void *)0; rcu_assign_pointer(dest, src); return 0; } However, that cast forces the source to have the __rcu address space without checking what address space it started out with. If you want to verify that the source has the kernel address space, you can cast to that address space first, *without* __force, which will warn if the source doesn't start out with that address space: #define __kernel __attribute__((address_space(0))) #define __user __attribute__((address_space(1),noderef)) #define __rcu __attribute__((address_space(4),noderef)) #define __force __attribute__((force)) #define ACCESS_ONCE(x) (*(volatile typeof(x) *)(x)) extern void smp_wmb(void); #define rcu_assign_pointer(p, v) \ do { \ smp_wmb(); \ ACCESS_ONCE(p) = (typeof(*(v)) __rcu __force *)(typeof(*(v)) __kernel *)(v); \ } while (0) struct foo { int x; }; int main(void) { struct foo __rcu *dest; struct foo *src = (void *)0; struct foo __user *badsrc = (void *)0; rcu_assign_pointer(dest, src); rcu_assign_pointer(dest, badsrc); return 0; } This produces a warning on the line using badsrc: test.c:23:5: warning: cast removes address space of expression However, that doesn't seem like the most obvious warning, since rcu_assign_pointer doesn't look like a cast, and since it doesn't print the full types involved like most address space warnings do. So, instead, let's add and use a __chk_kernel_ptr
Re: [lttng-dev] [RFC] adding into middle of RCU list
On Sun, Sep 01, 2013 at 03:26:19PM -0700, Paul E. McKenney wrote: On Sun, Sep 01, 2013 at 01:42:10PM -0700, Josh Triplett wrote: On Sat, Aug 31, 2013 at 02:32:28PM -0700, Paul E. McKenney wrote: On Thu, Aug 29, 2013 at 07:16:37PM -0700, Josh Triplett wrote: On Thu, Aug 29, 2013 at 05:57:33PM -0700, Paul E. McKenney wrote: On Fri, Aug 23, 2013 at 02:08:22PM -0700, Paul E. McKenney wrote: On Fri, Aug 23, 2013 at 01:16:53PM -0400, Mathieu Desnoyers wrote: #define __rcu_assign_pointer(p, v, space) \ do { \ smp_wmb(); \ (p) = (typeof(*v) __force space *)(v); \ } while (0) Or I need to fix this one as well. ;-) In that vein... Is there anything like typeof() that also preserves sparse's notion of address space? Wrapping an ACCESS_ONCE() around p in the assignment above results in sparse errors. typeof() will preserve sparse's notion of address space as long as you do typeof(p), not typeof(*p): $ cat test.c #define as(n) __attribute__((address_space(n),noderef)) #define __force __attribute__((force)) int main(void) { int target = 0; int as(1) *foo = (__force typeof(target) as(1) *) target; typeof(foo) bar = foo; return *bar; } $ sparse test.c test.c:9:13: warning: dereference of noderef expression Notice that sparse didn't warn on the assignment of foo to bar (because typeof propagated the address space of 1), and warned on the dereference of bar (because typeof propagated noderef). Thank you for the info! Suppose that I want to do something like this: #define __rcu_assign_pointer(p, v, space) \ do { \ smp_wmb(); \ ACCESS_ONCE(p) = (typeof(*v) __force space *)(v); \ } while (0) Now, this does typeof(*p), so as you noted above sparse complains about address-space mismatches. Thus far, I haven't been able to come up with something that (1) does sparse address-space checking, (2) does C type checking, and (3) forces the assignment to be volatile. Any thoughts on how to do this? First of all, if p and v had compatible types *including* address spaces, you wouldn't need the space argument; the following self-contained test case passes both sparse and GCC typechecking: #define as(n) __attribute__((address_space(n),noderef)) #define __force __attribute__((force)) #define ACCESS_ONCE(x) (*(volatile typeof(x) *)(x)) extern void smp_wmb(void); #define rcu_assign_pointer(p, v) \ do { \ smp_wmb(); \ ACCESS_ONCE(p) = (v); \ } while (0) struct foo; int main(void) { struct foo as(1) *dest; struct foo as(1) *src = (void *)0; rcu_assign_pointer(dest, src); return 0; } But in this case, you want dest and src to have compatible types except that dest must have the __rcu address space and src might not. So, let's change the types of dest and src, and add the appropriate cast. The following also passes both GCC and sparse: #define __rcu __attribute__((address_space(4),noderef)) #define __force __attribute__((force)) #define ACCESS_ONCE(x) (*(volatile typeof(x) *)(x)) extern void smp_wmb(void); #define rcu_assign_pointer(p, v) \ do { \ smp_wmb(); \ ACCESS_ONCE(p) = (typeof(*(v)) __rcu __force *)(v); \ } while (0) struct foo { int x; }; int main(void) { struct foo __rcu *dest; struct foo *src = (void *)0; rcu_assign_pointer(dest, src); return 0; } However, that cast forces the source to have the __rcu address space without checking what address space it started out with. If you want to verify that the source has the kernel address space, you can cast to that address space first, *without* __force, which will warn if the source doesn't start out with that address space: #define __kernel __attribute__((address_space(0))) #define __user __attribute__((address_space(1),noderef)) #define __rcu __attribute__((address_space(4),noderef)) #define __force __attribute__((force)) #define ACCESS_ONCE(x) (*(volatile typeof(x) *)(x)) extern void smp_wmb(void); #define rcu_assign_pointer(p, v) \ do { \ smp_wmb(); \ ACCESS_ONCE(p) = (typeof(*(v)) __rcu __force *)(typeof(*(v)) __kernel *)(v); \ } while (0) struct foo { int x; }; int main(void) { struct foo __rcu *dest; struct foo *src = (void *)0; struct foo __user *badsrc = (void *)0; rcu_assign_pointer(dest, src); rcu_assign_pointer(dest, badsrc); return 0; } This produces a warning on the line using badsrc: test.c:23:5: warning: cast removes address space of expression However, that doesn't seem like the
Re: [lttng-dev] [RFC] adding into middle of RCU list
On Thu, Aug 29, 2013 at 07:16:37PM -0700, Josh Triplett wrote: On Thu, Aug 29, 2013 at 05:57:33PM -0700, Paul E. McKenney wrote: On Fri, Aug 23, 2013 at 02:08:22PM -0700, Paul E. McKenney wrote: On Fri, Aug 23, 2013 at 01:16:53PM -0400, Mathieu Desnoyers wrote: #define __rcu_assign_pointer(p, v, space) \ do { \ smp_wmb(); \ (p) = (typeof(*v) __force space *)(v); \ } while (0) Or I need to fix this one as well. ;-) In that vein... Is there anything like typeof() that also preserves sparse's notion of address space? Wrapping an ACCESS_ONCE() around p in the assignment above results in sparse errors. typeof() will preserve sparse's notion of address space as long as you do typeof(p), not typeof(*p): $ cat test.c #define as(n) __attribute__((address_space(n),noderef)) #define __force __attribute__((force)) int main(void) { int target = 0; int as(1) *foo = (__force typeof(target) as(1) *) target; typeof(foo) bar = foo; return *bar; } $ sparse test.c test.c:9:13: warning: dereference of noderef expression Notice that sparse didn't warn on the assignment of foo to bar (because typeof propagated the address space of 1), and warned on the dereference of bar (because typeof propagated noderef). Thank you for the info! Suppose that I want to do something like this: #define __rcu_assign_pointer(p, v, space) \ do { \ smp_wmb(); \ ACCESS_ONCE(p) = (typeof(*v) __force space *)(v); \ } while (0) Now, this does typeof(*p), so as you noted above sparse complains about address-space mismatches. Thus far, I haven't been able to come up with something that (1) does sparse address-space checking, (2) does C type checking, and (3) forces the assignment to be volatile. Any thoughts on how to do this? Thanx, Paul ___ lttng-dev mailing list lttng-dev@lists.lttng.org http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
Re: [lttng-dev] [RFC] adding into middle of RCU list
On Fri, Aug 23, 2013 at 02:08:22PM -0700, Paul E. McKenney wrote: On Fri, Aug 23, 2013 at 01:16:53PM -0400, Mathieu Desnoyers wrote: * Paul E. McKenney (paul...@linux.vnet.ibm.com) wrote: On Thu, Aug 22, 2013 at 09:33:18PM -0700, Stephen Hemminger wrote: [ . . . ] + +/** + * Splice an RCU-protected list into an existing list. + * + * Note that this function blocks in synchronize_rcu() + * + * Important note: this function is not called concurrently + * with other updates to the list. + */ +static inline void caa_list_splice_init_rcu(struct cds_list_head *list, + struct cds_list_head *head) +{ + struct cds_list_head *first = list-next; + struct cds_list_head *last = list-prev; + struct cds_list_head *at = head-next; + + if (cds_list_empty(list)) + return; + + /* first and last tracking list, so initialize it. */ + CDS_INIT_LIST_HEAD(list); This change is happening in the presence of readers on the list, right? For this to work reliably in the presence of mischievous compilers, wouldn't CDS_INIT_LIST_HEAD() need to use CMM_ACCESS_ONCE() for its pointer accesses? Actually, we have rcu_assign_pointer()/rcu_set_pointer() exactly for this. They even skip the memory barrier if they store a NULL pointer. Hmmm... The kernel version seems to have the same issue... The compiler memory model of the Linux kernel AFAIK does not require an ACCESS_ONCE() for stores to word-aligned, word-sized integers/pointers, even if those are expected to be read concurrently. For reference, see: #define __rcu_assign_pointer(p, v, space) \ do { \ smp_wmb(); \ (p) = (typeof(*v) __force space *)(v); \ } while (0) Or I need to fix this one as well. ;-) In that vein... Is there anything like typeof() that also preserves sparse's notion of address space? Wrapping an ACCESS_ONCE() around p in the assignment above results in sparse errors. Thanx, Paul Thanx, Paul ___ lttng-dev mailing list lttng-dev@lists.lttng.org http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
Re: [lttng-dev] [RFC] adding into middle of RCU list
On Thu, Aug 29, 2013 at 05:57:33PM -0700, Paul E. McKenney wrote: On Fri, Aug 23, 2013 at 02:08:22PM -0700, Paul E. McKenney wrote: On Fri, Aug 23, 2013 at 01:16:53PM -0400, Mathieu Desnoyers wrote: #define __rcu_assign_pointer(p, v, space) \ do { \ smp_wmb(); \ (p) = (typeof(*v) __force space *)(v); \ } while (0) Or I need to fix this one as well. ;-) In that vein... Is there anything like typeof() that also preserves sparse's notion of address space? Wrapping an ACCESS_ONCE() around p in the assignment above results in sparse errors. typeof() will preserve sparse's notion of address space as long as you do typeof(p), not typeof(*p): $ cat test.c #define as(n) __attribute__((address_space(n),noderef)) #define __force __attribute__((force)) int main(void) { int target = 0; int as(1) *foo = (__force typeof(target) as(1) *) target; typeof(foo) bar = foo; return *bar; } $ sparse test.c test.c:9:13: warning: dereference of noderef expression Notice that sparse didn't warn on the assignment of foo to bar (because typeof propagated the address space of 1), and warned on the dereference of bar (because typeof propagated noderef). - Josh Triplett ___ lttng-dev mailing list lttng-dev@lists.lttng.org http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
Re: [lttng-dev] [RFC] adding into middle of RCU list
Hi Stephen, * Stephen Hemminger (step...@networkplumber.org) wrote: I needed to add into the middle of an RCU list, does this make sense. Yes, it makes sense. I'm adding a couple of comments below, From a45892b0d49ac5fe449ba7e19c646cb17f7cee57 Mon Sep 17 00:00:00 2001 From: Stephen Hemminger step...@networkplumber.org Date: Thu, 22 Aug 2013 21:27:04 -0700 Subject: [PATCH] Add list_splice_init_rcu to allow insertion into a RCU list Simplified version of the version in kernel. --- urcu/rculist.h | 32 1 file changed, 32 insertions(+) diff --git a/urcu/rculist.h b/urcu/rculist.h index 1fd2df3..2e8a5a0 100644 --- a/urcu/rculist.h +++ b/urcu/rculist.h @@ -72,6 +72,38 @@ void cds_list_del_rcu(struct cds_list_head *elem) CMM_STORE_SHARED(elem-prev-next, elem-next); } + +/** + * Splice an RCU-protected list into an existing list. + * + * Note that this function blocks in synchronize_rcu() + * + * Important note: this function is not called concurrently is not - should not be + * with other updates to the list. We might also want to start documenting the parameters in the list headers, since it's unclear to someone who want to use the API which of list and head is the list we want to splice, and which is the target, e.g.: * @list: RCU-protected list to splice into @head. * @head: existing and initialized list to splice into. We might want to state more clearly that @head can be any node within a target list, including the list head. + */ +static inline void caa_list_splice_init_rcu(struct cds_list_head *list, + struct cds_list_head *head) +{ + struct cds_list_head *first = list-next; + struct cds_list_head *last = list-prev; + struct cds_list_head *at = head-next; + + if (cds_list_empty(list)) + return; + + /* first and last tracking list, so initialize it. */ + CDS_INIT_LIST_HEAD(list); + + /* Wait for any readers to finish using the list before splicing */ + synchronize_rcu(); + + /* Readers are finished with the source list, so perform splice. */ + last-next = at; + rcu_assign_pointer(head-next, first); + first-prev = head; + at-prev = last; +} Comment about style for LGPL headers: we really want to keep the functions at 10 lines or less, otherwise they will need to be moved into a library call or split into two static inline functions. So here, I recommend moving the comments into the comment above the function, and split the part starting at last-next = at; (4 lines) into a helper function. Along with merging the 3 lines of local variables declaration into 2, and removing empty white spaces and comments, we should be able to fit this in 10 lines for caa_list_splice_init_rcu(). Thoughts ? Thanks, Mathieu + /* * Iteration through all elements of the list must be done while rcu_read_lock() * is held. -- 1.7.10.4 -- Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com ___ lttng-dev mailing list lttng-dev@lists.lttng.org http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
Re: [lttng-dev] [RFC] adding into middle of RCU list
On Thu, Aug 22, 2013 at 09:33:18PM -0700, Stephen Hemminger wrote: I needed to add into the middle of an RCU list, does this make sense. From a45892b0d49ac5fe449ba7e19c646cb17f7cee57 Mon Sep 17 00:00:00 2001 From: Stephen Hemminger step...@networkplumber.org Date: Thu, 22 Aug 2013 21:27:04 -0700 Subject: [PATCH] Add list_splice_init_rcu to allow insertion into a RCU list Simplified version of the version in kernel. --- urcu/rculist.h | 32 1 file changed, 32 insertions(+) diff --git a/urcu/rculist.h b/urcu/rculist.h index 1fd2df3..2e8a5a0 100644 --- a/urcu/rculist.h +++ b/urcu/rculist.h @@ -72,6 +72,38 @@ void cds_list_del_rcu(struct cds_list_head *elem) CMM_STORE_SHARED(elem-prev-next, elem-next); } + +/** + * Splice an RCU-protected list into an existing list. + * + * Note that this function blocks in synchronize_rcu() + * + * Important note: this function is not called concurrently + * with other updates to the list. + */ +static inline void caa_list_splice_init_rcu(struct cds_list_head *list, + struct cds_list_head *head) +{ + struct cds_list_head *first = list-next; + struct cds_list_head *last = list-prev; + struct cds_list_head *at = head-next; + + if (cds_list_empty(list)) + return; + + /* first and last tracking list, so initialize it. */ + CDS_INIT_LIST_HEAD(list); This change is happening in the presence of readers on the list, right? For this to work reliably in the presence of mischievous compilers, wouldn't CDS_INIT_LIST_HEAD() need to use CMM_ACCESS_ONCE() for its pointer accesses? Hmmm... The kernel version seems to have the same issue... Patch below, FWIW. Thanx, Paul + + /* Wait for any readers to finish using the list before splicing */ + synchronize_rcu(); + + /* Readers are finished with the source list, so perform splice. */ + last-next = at; + rcu_assign_pointer(head-next, first); + first-prev = head; + at-prev = last; +} + /* * Iteration through all elements of the list must be done while rcu_read_lock() * is held. -- 1.7.10.4 rcu: Make list_splice_init_rcu() account for RCU readers The list_splice_init_rcu() function allows a list visible to RCU readers to be spliced into another list visible to RCU readers. This is OK, except for the use of INIT_LIST_HEAD(), which does pointer updates without doing anything to make those updates safe for concurrent readers. Of course, most of the time INIT_LIST_HEAD() is being used in reader-free contexts, such as initialization or cleanup, so it is OK for it to update pointers in an unsafe-for-RCU-readers manner. This commit therefore creates an INIT_LIST_HEAD_RCU() that uses ACCESS_ONCE() to make the updates reader-safe. The reason that we can use ACCESS_ONCE() instead of the more typical rcu_assign_pointer() is that list_splice_init_rcu() is updating the pointers to reference something that is already visible to readers, so that there is no problem with pre-initialized values. Signed-off-by: Paul E. McKenney paul...@linux.vnet.ibm.com diff --git a/include/linux/rculist.h b/include/linux/rculist.h index 4106721..45a0a9e 100644 --- a/include/linux/rculist.h +++ b/include/linux/rculist.h @@ -19,6 +19,21 @@ */ /* + * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers + * @list: list to be initialized + * + * You should instead use INIT_LIST_HEAD() for normal initialization and + * cleanup tasks, when readers have no access to the list being initialized. + * However, if the list being initialized is visible to readers, you + * need to keep the compiler from being too mischievous. + */ +static inline void INIT_LIST_HEAD_RCU(struct list_head *list) +{ + ACCESS_ONCE(list-next) = list; + ACCESS_ONCE(list-prev) = list; +} + +/* * return the -next pointer of a list_head in an rcu safe * way, we must not access it directly */ @@ -191,9 +206,13 @@ static inline void list_splice_init_rcu(struct list_head *list, if (list_empty(list)) return; - /* first and last tracking list, so initialize it. */ + /* +* first and last tracking list, so initialize it. RCU readers +* have access to this list, so we must use INIT_LIST_HEAD_RCU() +* instead of INIT_LIST_HEAD(). +*/ - INIT_LIST_HEAD(list); + INIT_LIST_HEAD_RCU(list); /* * At this point, the list body still points to the source list. ___ lttng-dev mailing list lttng-dev@lists.lttng.org http://lists.lttng.org/cgi-bin/mailman/listinfo/lttng-dev
Re: [lttng-dev] [RFC] adding into middle of RCU list
* Paul E. McKenney (paul...@linux.vnet.ibm.com) wrote: On Thu, Aug 22, 2013 at 09:33:18PM -0700, Stephen Hemminger wrote: I needed to add into the middle of an RCU list, does this make sense. From a45892b0d49ac5fe449ba7e19c646cb17f7cee57 Mon Sep 17 00:00:00 2001 From: Stephen Hemminger step...@networkplumber.org Date: Thu, 22 Aug 2013 21:27:04 -0700 Subject: [PATCH] Add list_splice_init_rcu to allow insertion into a RCU list Simplified version of the version in kernel. --- urcu/rculist.h | 32 1 file changed, 32 insertions(+) diff --git a/urcu/rculist.h b/urcu/rculist.h index 1fd2df3..2e8a5a0 100644 --- a/urcu/rculist.h +++ b/urcu/rculist.h @@ -72,6 +72,38 @@ void cds_list_del_rcu(struct cds_list_head *elem) CMM_STORE_SHARED(elem-prev-next, elem-next); } + +/** + * Splice an RCU-protected list into an existing list. + * + * Note that this function blocks in synchronize_rcu() + * + * Important note: this function is not called concurrently + * with other updates to the list. + */ +static inline void caa_list_splice_init_rcu(struct cds_list_head *list, + struct cds_list_head *head) +{ + struct cds_list_head *first = list-next; + struct cds_list_head *last = list-prev; + struct cds_list_head *at = head-next; + + if (cds_list_empty(list)) + return; + + /* first and last tracking list, so initialize it. */ + CDS_INIT_LIST_HEAD(list); This change is happening in the presence of readers on the list, right? For this to work reliably in the presence of mischievous compilers, wouldn't CDS_INIT_LIST_HEAD() need to use CMM_ACCESS_ONCE() for its pointer accesses? Actually, we have rcu_assign_pointer()/rcu_set_pointer() exactly for this. They even skip the memory barrier if they store a NULL pointer. Hmmm... The kernel version seems to have the same issue... The compiler memory model of the Linux kernel AFAIK does not require an ACCESS_ONCE() for stores to word-aligned, word-sized integers/pointers, even if those are expected to be read concurrently. For reference, see: #define __rcu_assign_pointer(p, v, space) \ do { \ smp_wmb(); \ (p) = (typeof(*v) __force space *)(v); \ } while (0) In userspace RCU, we require to match CMM_LOAD_SHARED() with CMM_STORE_SHARED() (which are used by rcu_dereference()/rcu_{set,assign}_pointer) whenever we concurrently access a variable shared between threads. So I recommend using rcu_set_pointer() in userspace RCU, but I don't think your patch is needed for Linux, given the Linux kernel compiler memory model that is less strict than userspace RCU's model. Thanks, Mathieu Patch below, FWIW. Thanx, Paul + + /* Wait for any readers to finish using the list before splicing */ + synchronize_rcu(); + + /* Readers are finished with the source list, so perform splice. */ + last-next = at; + rcu_assign_pointer(head-next, first); + first-prev = head; + at-prev = last; +} + /* * Iteration through all elements of the list must be done while rcu_read_lock() * is held. -- 1.7.10.4 rcu: Make list_splice_init_rcu() account for RCU readers The list_splice_init_rcu() function allows a list visible to RCU readers to be spliced into another list visible to RCU readers. This is OK, except for the use of INIT_LIST_HEAD(), which does pointer updates without doing anything to make those updates safe for concurrent readers. Of course, most of the time INIT_LIST_HEAD() is being used in reader-free contexts, such as initialization or cleanup, so it is OK for it to update pointers in an unsafe-for-RCU-readers manner. This commit therefore creates an INIT_LIST_HEAD_RCU() that uses ACCESS_ONCE() to make the updates reader-safe. The reason that we can use ACCESS_ONCE() instead of the more typical rcu_assign_pointer() is that list_splice_init_rcu() is updating the pointers to reference something that is already visible to readers, so that there is no problem with pre-initialized values. Signed-off-by: Paul E. McKenney paul...@linux.vnet.ibm.com diff --git a/include/linux/rculist.h b/include/linux/rculist.h index 4106721..45a0a9e 100644 --- a/include/linux/rculist.h +++ b/include/linux/rculist.h @@ -19,6 +19,21 @@ */ /* + * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers + * @list: list to be initialized + * + * You should instead use INIT_LIST_HEAD() for normal initialization and + * cleanup tasks, when readers have no access to the list being initialized. + * However, if the list being initialized is visible to readers, you + * need to keep the compiler from being too mischievous. + */ +static inline void INIT_LIST_HEAD_RCU(struct list_head *list) +{ +
Re: [lttng-dev] [RFC] adding into middle of RCU list
On Fri, 23 Aug 2013 13:16:53 -0400 Mathieu Desnoyers mathieu.desnoy...@efficios.com wrote: * Paul E. McKenney (paul...@linux.vnet.ibm.com) wrote: On Thu, Aug 22, 2013 at 09:33:18PM -0700, Stephen Hemminger wrote: I needed to add into the middle of an RCU list, does this make sense. From a45892b0d49ac5fe449ba7e19c646cb17f7cee57 Mon Sep 17 00:00:00 2001 From: Stephen Hemminger step...@networkplumber.org Date: Thu, 22 Aug 2013 21:27:04 -0700 Subject: [PATCH] Add list_splice_init_rcu to allow insertion into a RCU list Simplified version of the version in kernel. --- urcu/rculist.h | 32 1 file changed, 32 insertions(+) diff --git a/urcu/rculist.h b/urcu/rculist.h index 1fd2df3..2e8a5a0 100644 --- a/urcu/rculist.h +++ b/urcu/rculist.h @@ -72,6 +72,38 @@ void cds_list_del_rcu(struct cds_list_head *elem) CMM_STORE_SHARED(elem-prev-next, elem-next); } + +/** + * Splice an RCU-protected list into an existing list. + * + * Note that this function blocks in synchronize_rcu() + * + * Important note: this function is not called concurrently + * with other updates to the list. + */ +static inline void caa_list_splice_init_rcu(struct cds_list_head *list, + struct cds_list_head *head) +{ + struct cds_list_head *first = list-next; + struct cds_list_head *last = list-prev; + struct cds_list_head *at = head-next; + + if (cds_list_empty(list)) + return; + + /* first and last tracking list, so initialize it. */ + CDS_INIT_LIST_HEAD(list); This change is happening in the presence of readers on the list, right? For this to work reliably in the presence of mischievous compilers, wouldn't CDS_INIT_LIST_HEAD() need to use CMM_ACCESS_ONCE() for its pointer accesses? Actually, we have rcu_assign_pointer()/rcu_set_pointer() exactly for this. They even skip the memory barrier if they store a NULL pointer. Hmmm... The kernel version seems to have the same issue... The compiler memory model of the Linux kernel AFAIK does not require an ACCESS_ONCE() for stores to word-aligned, word-sized integers/pointers, even if those are expected to be read concurrently. For reference, see: #define __rcu_assign_pointer(p, v, space) \ do { \ smp_wmb(); \ (p) = (typeof(*v) __force space *)(v); \ } while (0) In userspace RCU, we require to match CMM_LOAD_SHARED() with CMM_STORE_SHARED() (which are used by rcu_dereference()/rcu_{set,assign}_pointer) whenever we concurrently access a variable shared between threads. So I recommend using rcu_set_pointer() in userspace RCU, but I don't think your patch is needed for Linux, given the Linux kernel compiler memory model that is less strict than userspace RCU's model. Thanks, Mathieu Patch below, FWIW. Thanx, Paul + + /* Wait for any readers to finish using the list before splicing */ + synchronize_rcu(); + + /* Readers are finished with the source list, so perform splice. */ + last-next = at; + rcu_assign_pointer(head-next, first); + first-prev = head; + at-prev = last; +} + /* * Iteration through all elements of the list must be done while rcu_read_lock() * is held. -- 1.7.10.4 rcu: Make list_splice_init_rcu() account for RCU readers The list_splice_init_rcu() function allows a list visible to RCU readers to be spliced into another list visible to RCU readers. This is OK, except for the use of INIT_LIST_HEAD(), which does pointer updates without doing anything to make those updates safe for concurrent readers. Of course, most of the time INIT_LIST_HEAD() is being used in reader-free contexts, such as initialization or cleanup, so it is OK for it to update pointers in an unsafe-for-RCU-readers manner. This commit therefore creates an INIT_LIST_HEAD_RCU() that uses ACCESS_ONCE() to make the updates reader-safe. The reason that we can use ACCESS_ONCE() instead of the more typical rcu_assign_pointer() is that list_splice_init_rcu() is updating the pointers to reference something that is already visible to readers, so that there is no problem with pre-initialized values. Signed-off-by: Paul E. McKenney paul...@linux.vnet.ibm.com diff --git a/include/linux/rculist.h b/include/linux/rculist.h index 4106721..45a0a9e 100644 --- a/include/linux/rculist.h +++ b/include/linux/rculist.h @@ -19,6 +19,21 @@ */ /* + * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers + * @list: list to be initialized + * + * You should instead use INIT_LIST_HEAD() for normal initialization and + * cleanup tasks, when readers have no access to the list being initialized. + * However, if the list
Re: [lttng-dev] [RFC] adding into middle of RCU list
On Fri, Aug 23, 2013 at 12:09:56PM -0700, Stephen Hemminger wrote: On Fri, 23 Aug 2013 13:16:53 -0400 Mathieu Desnoyers mathieu.desnoy...@efficios.com wrote: * Paul E. McKenney (paul...@linux.vnet.ibm.com) wrote: On Thu, Aug 22, 2013 at 09:33:18PM -0700, Stephen Hemminger wrote: I needed to add into the middle of an RCU list, does this make sense. From a45892b0d49ac5fe449ba7e19c646cb17f7cee57 Mon Sep 17 00:00:00 2001 From: Stephen Hemminger step...@networkplumber.org Date: Thu, 22 Aug 2013 21:27:04 -0700 Subject: [PATCH] Add list_splice_init_rcu to allow insertion into a RCU list Simplified version of the version in kernel. --- urcu/rculist.h | 32 1 file changed, 32 insertions(+) diff --git a/urcu/rculist.h b/urcu/rculist.h index 1fd2df3..2e8a5a0 100644 --- a/urcu/rculist.h +++ b/urcu/rculist.h @@ -72,6 +72,38 @@ void cds_list_del_rcu(struct cds_list_head *elem) CMM_STORE_SHARED(elem-prev-next, elem-next); } + +/** + * Splice an RCU-protected list into an existing list. + * + * Note that this function blocks in synchronize_rcu() + * + * Important note: this function is not called concurrently + * with other updates to the list. + */ +static inline void caa_list_splice_init_rcu(struct cds_list_head *list, + struct cds_list_head *head) +{ + struct cds_list_head *first = list-next; + struct cds_list_head *last = list-prev; + struct cds_list_head *at = head-next; + + if (cds_list_empty(list)) + return; + + /* first and last tracking list, so initialize it. */ + CDS_INIT_LIST_HEAD(list); This change is happening in the presence of readers on the list, right? For this to work reliably in the presence of mischievous compilers, wouldn't CDS_INIT_LIST_HEAD() need to use CMM_ACCESS_ONCE() for its pointer accesses? Actually, we have rcu_assign_pointer()/rcu_set_pointer() exactly for this. They even skip the memory barrier if they store a NULL pointer. Hmmm... The kernel version seems to have the same issue... The compiler memory model of the Linux kernel AFAIK does not require an ACCESS_ONCE() for stores to word-aligned, word-sized integers/pointers, even if those are expected to be read concurrently. For reference, see: #define __rcu_assign_pointer(p, v, space) \ do { \ smp_wmb(); \ (p) = (typeof(*v) __force space *)(v); \ } while (0) In userspace RCU, we require to match CMM_LOAD_SHARED() with CMM_STORE_SHARED() (which are used by rcu_dereference()/rcu_{set,assign}_pointer) whenever we concurrently access a variable shared between threads. So I recommend using rcu_set_pointer() in userspace RCU, but I don't think your patch is needed for Linux, given the Linux kernel compiler memory model that is less strict than userspace RCU's model. Thanks, Mathieu Patch below, FWIW. Thanx, Paul + + /* Wait for any readers to finish using the list before splicing */ + synchronize_rcu(); + + /* Readers are finished with the source list, so perform splice. */ + last-next = at; + rcu_assign_pointer(head-next, first); + first-prev = head; + at-prev = last; +} + /* * Iteration through all elements of the list must be done while rcu_read_lock() * is held. -- 1.7.10.4 rcu: Make list_splice_init_rcu() account for RCU readers The list_splice_init_rcu() function allows a list visible to RCU readers to be spliced into another list visible to RCU readers. This is OK, except for the use of INIT_LIST_HEAD(), which does pointer updates without doing anything to make those updates safe for concurrent readers. Of course, most of the time INIT_LIST_HEAD() is being used in reader-free contexts, such as initialization or cleanup, so it is OK for it to update pointers in an unsafe-for-RCU-readers manner. This commit therefore creates an INIT_LIST_HEAD_RCU() that uses ACCESS_ONCE() to make the updates reader-safe. The reason that we can use ACCESS_ONCE() instead of the more typical rcu_assign_pointer() is that list_splice_init_rcu() is updating the pointers to reference something that is already visible to readers, so that there is no problem with pre-initialized values. Signed-off-by: Paul E. McKenney paul...@linux.vnet.ibm.com diff --git a/include/linux/rculist.h b/include/linux/rculist.h index 4106721..45a0a9e 100644 --- a/include/linux/rculist.h +++ b/include/linux/rculist.h @@ -19,6 +19,21 @@ */
Re: [lttng-dev] [RFC] adding into middle of RCU list
On Fri, Aug 23, 2013 at 01:16:53PM -0400, Mathieu Desnoyers wrote: * Paul E. McKenney (paul...@linux.vnet.ibm.com) wrote: On Thu, Aug 22, 2013 at 09:33:18PM -0700, Stephen Hemminger wrote: I needed to add into the middle of an RCU list, does this make sense. From a45892b0d49ac5fe449ba7e19c646cb17f7cee57 Mon Sep 17 00:00:00 2001 From: Stephen Hemminger step...@networkplumber.org Date: Thu, 22 Aug 2013 21:27:04 -0700 Subject: [PATCH] Add list_splice_init_rcu to allow insertion into a RCU list Simplified version of the version in kernel. --- urcu/rculist.h | 32 1 file changed, 32 insertions(+) diff --git a/urcu/rculist.h b/urcu/rculist.h index 1fd2df3..2e8a5a0 100644 --- a/urcu/rculist.h +++ b/urcu/rculist.h @@ -72,6 +72,38 @@ void cds_list_del_rcu(struct cds_list_head *elem) CMM_STORE_SHARED(elem-prev-next, elem-next); } + +/** + * Splice an RCU-protected list into an existing list. + * + * Note that this function blocks in synchronize_rcu() + * + * Important note: this function is not called concurrently + * with other updates to the list. + */ +static inline void caa_list_splice_init_rcu(struct cds_list_head *list, + struct cds_list_head *head) +{ + struct cds_list_head *first = list-next; + struct cds_list_head *last = list-prev; + struct cds_list_head *at = head-next; + + if (cds_list_empty(list)) + return; + + /* first and last tracking list, so initialize it. */ + CDS_INIT_LIST_HEAD(list); This change is happening in the presence of readers on the list, right? For this to work reliably in the presence of mischievous compilers, wouldn't CDS_INIT_LIST_HEAD() need to use CMM_ACCESS_ONCE() for its pointer accesses? Actually, we have rcu_assign_pointer()/rcu_set_pointer() exactly for this. They even skip the memory barrier if they store a NULL pointer. Hmmm... The kernel version seems to have the same issue... The compiler memory model of the Linux kernel AFAIK does not require an ACCESS_ONCE() for stores to word-aligned, word-sized integers/pointers, even if those are expected to be read concurrently. For reference, see: #define __rcu_assign_pointer(p, v, space) \ do { \ smp_wmb(); \ (p) = (typeof(*v) __force space *)(v); \ } while (0) Or I need to fix this one as well. ;-) In userspace RCU, we require to match CMM_LOAD_SHARED() with CMM_STORE_SHARED() (which are used by rcu_dereference()/rcu_{set,assign}_pointer) whenever we concurrently access a variable shared between threads. So I recommend using rcu_set_pointer() in userspace RCU, but I don't think your patch is needed for Linux, given the Linux kernel compiler memory model that is less strict than userspace RCU's model. Me, I trust compilers a lot less than I did some years back. ;-) Thanx, Paul Thanks, Mathieu Patch below, FWIW. Thanx, Paul + + /* Wait for any readers to finish using the list before splicing */ + synchronize_rcu(); + + /* Readers are finished with the source list, so perform splice. */ + last-next = at; + rcu_assign_pointer(head-next, first); + first-prev = head; + at-prev = last; +} + /* * Iteration through all elements of the list must be done while rcu_read_lock() * is held. -- 1.7.10.4 rcu: Make list_splice_init_rcu() account for RCU readers The list_splice_init_rcu() function allows a list visible to RCU readers to be spliced into another list visible to RCU readers. This is OK, except for the use of INIT_LIST_HEAD(), which does pointer updates without doing anything to make those updates safe for concurrent readers. Of course, most of the time INIT_LIST_HEAD() is being used in reader-free contexts, such as initialization or cleanup, so it is OK for it to update pointers in an unsafe-for-RCU-readers manner. This commit therefore creates an INIT_LIST_HEAD_RCU() that uses ACCESS_ONCE() to make the updates reader-safe. The reason that we can use ACCESS_ONCE() instead of the more typical rcu_assign_pointer() is that list_splice_init_rcu() is updating the pointers to reference something that is already visible to readers, so that there is no problem with pre-initialized values. Signed-off-by: Paul E. McKenney paul...@linux.vnet.ibm.com diff --git a/include/linux/rculist.h b/include/linux/rculist.h index 4106721..45a0a9e 100644 --- a/include/linux/rculist.h +++ b/include/linux/rculist.h @@ -19,6 +19,21 @@ */ /* + * INIT_LIST_HEAD_RCU - Initialize a list_head visible to RCU readers + * @list: list to be initialized + * + * You should instead use
Re: [lttng-dev] [RFC] adding into middle of RCU list
On Fri, 23 Aug 2013 14:05:51 -0700 Paul E. McKenney paul...@linux.vnet.ibm.com wrote: On Fri, Aug 23, 2013 at 12:09:56PM -0700, Stephen Hemminger wrote: On Fri, 23 Aug 2013 13:16:53 -0400 Mathieu Desnoyers mathieu.desnoy...@efficios.com wrote: * Paul E. McKenney (paul...@linux.vnet.ibm.com) wrote: On Thu, Aug 22, 2013 at 09:33:18PM -0700, Stephen Hemminger wrote: I needed to add into the middle of an RCU list, does this make sense. From a45892b0d49ac5fe449ba7e19c646cb17f7cee57 Mon Sep 17 00:00:00 2001 From: Stephen Hemminger step...@networkplumber.org Date: Thu, 22 Aug 2013 21:27:04 -0700 Subject: [PATCH] Add list_splice_init_rcu to allow insertion into a RCU list Simplified version of the version in kernel. --- urcu/rculist.h | 32 1 file changed, 32 insertions(+) diff --git a/urcu/rculist.h b/urcu/rculist.h index 1fd2df3..2e8a5a0 100644 --- a/urcu/rculist.h +++ b/urcu/rculist.h @@ -72,6 +72,38 @@ void cds_list_del_rcu(struct cds_list_head *elem) CMM_STORE_SHARED(elem-prev-next, elem-next); } + +/** + * Splice an RCU-protected list into an existing list. + * + * Note that this function blocks in synchronize_rcu() + * + * Important note: this function is not called concurrently + * with other updates to the list. + */ +static inline void caa_list_splice_init_rcu(struct cds_list_head *list, + struct cds_list_head *head) +{ + struct cds_list_head *first = list-next; + struct cds_list_head *last = list-prev; + struct cds_list_head *at = head-next; + + if (cds_list_empty(list)) + return; + + /* first and last tracking list, so initialize it. */ + CDS_INIT_LIST_HEAD(list); This change is happening in the presence of readers on the list, right? For this to work reliably in the presence of mischievous compilers, wouldn't CDS_INIT_LIST_HEAD() need to use CMM_ACCESS_ONCE() for its pointer accesses? Actually, we have rcu_assign_pointer()/rcu_set_pointer() exactly for this. They even skip the memory barrier if they store a NULL pointer. Hmmm... The kernel version seems to have the same issue... The compiler memory model of the Linux kernel AFAIK does not require an ACCESS_ONCE() for stores to word-aligned, word-sized integers/pointers, even if those are expected to be read concurrently. For reference, see: #define __rcu_assign_pointer(p, v, space) \ do { \ smp_wmb(); \ (p) = (typeof(*v) __force space *)(v); \ } while (0) In userspace RCU, we require to match CMM_LOAD_SHARED() with CMM_STORE_SHARED() (which are used by rcu_dereference()/rcu_{set,assign}_pointer) whenever we concurrently access a variable shared between threads. So I recommend using rcu_set_pointer() in userspace RCU, but I don't think your patch is needed for Linux, given the Linux kernel compiler memory model that is less strict than userspace RCU's model. Thanks, Mathieu Patch below, FWIW. Thanx, Paul + + /* Wait for any readers to finish using the list before splicing */ + synchronize_rcu(); + + /* Readers are finished with the source list, so perform splice. */ + last-next = at; + rcu_assign_pointer(head-next, first); + first-prev = head; + at-prev = last; +} + /* * Iteration through all elements of the list must be done while rcu_read_lock() * is held. -- 1.7.10.4 rcu: Make list_splice_init_rcu() account for RCU readers The list_splice_init_rcu() function allows a list visible to RCU readers to be spliced into another list visible to RCU readers. This is OK, except for the use of INIT_LIST_HEAD(), which does pointer updates without doing anything to make those updates safe for concurrent readers. Of course, most of the time INIT_LIST_HEAD() is being used in reader-free contexts, such as initialization or cleanup, so it is OK for it to update pointers in an unsafe-for-RCU-readers manner. This commit therefore creates an INIT_LIST_HEAD_RCU() that uses ACCESS_ONCE() to make the updates reader-safe. The reason that we can use ACCESS_ONCE() instead of the more typical rcu_assign_pointer() is that list_splice_init_rcu() is updating the pointers to reference something that is already visible to readers, so that there is no problem with pre-initialized values. Signed-off-by: Paul E. McKenney