adding into middle of RCU list
Subsystems (2)
A message that is not in the archive (sent off-list or not yet received): [email protected]
Mathieu Desnoyers
reviewerHi Stephen,
Quoted 2 lines · * Stephen Hemminger ([email protected]) 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,
Quoted 17 lines
From
a45892b0d49ac5fe449ba7e19c646cb17f7cee57Mon Sep 17 00:00:00 2001
From: Stephen Hemminger <[email protected]>
Date: Thu, 22 Aug 2013 21:27:04 -0700
Subject: [PATCH] Addlist_splice_init_rcuto allow insertion into a RCU listSimplified version of the version in kernel.
--- urcu/rculist.h | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+)urcu/rculist.h +0
-0
urcu/rculist.h void cds_list_del_rcu(struct cds_list_head *elem) · line 81
Quoted 10 lines
urcu/rculist.h +7
-0@@ -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
urcu/rculist.h void cds_list_del_rcu(struct cds_list_head *elem) · line 82
Quoted 1 line
urcu/rculist.h +1
-0+* 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.
Quoted 13 lines
urcu/rculist.h +13
-0+*/ +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);
urcu/rculist.h void cds_list_del_rcu(struct cds_list_head *elem) · line 105
Quoted 10 lines
urcu/rculist.h +10
-0+ +/* 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
Quoted 7 lines
urcu/rculist.h +1
-0+/* * Iteration through all elements of the list must be done while rcu_read_lock() * is held. Signature · 1 line
1.7.10.4
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
Quoted 33 lines · Stephen Hemminger
I needed to add into the middle of an RCU list, does this make sense.
From
a45892b0d49ac5fe449ba7e19c646cb17f7cee57Mon Sep 17 00:00:00 2001
From: Stephen Hemminger <[email protected]>
Date: Thu, 22 Aug 2013 21:27:04 -0700
Subject: [PATCH] Addlist_splice_init_rcuto allow insertion into a RCU listSimplified version of the version in kernel.
--- urcu/rculist.h | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+)urcu/rculist.h +11
-0@@ -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)
urcu/rculist.h void cds_list_del_rcu(struct cds_list_head *elem) · line 95
Quoted 10 lines
urcu/rculist.h +10
-0+{ +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
Quoted 16 lines
urcu/rculist.h +11
-0+ +/* 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. Signature · 1 line
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.
include/linux/rculist.h +21 -2
@@ -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.
A message that is not in the archive (sent off-list or not yet received): [email protected]
Mathieu Desnoyers
reviewerQuoted 41 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 40 lines · Stephen Hemminger
I needed to add into the middle of an RCU list, does this make sense.
From
a45892b0d49ac5fe449ba7e19c646cb17f7cee57Mon Sep 17 00:00:00 2001
From: Stephen Hemminger <[email protected]>
Date: Thu, 22 Aug 2013 21:27:04 -0700
Subject: [PATCH] Addlist_splice_init_rcuto allow insertion into a RCU listSimplified version of the version in kernel.
--- urcu/rculist.h | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+)urcu/rculist.h +18
-0@@ -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 ;
Quoted 8 lines
urcu/rculist.h void cds_list_del_rcu(struct cds_list_head *elem) · line 95
Quoted 3 lines
urcu/rculist.h +3
-0+ +/* "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 useCMM_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.
Quoted 2 lines
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
Quoted 82 lines
Patch below, FWIW.
Thanx, Paul
Quoted 16 lines
urcu/rculist.h +11
-0+ +/* 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. Signature · 1 line
1.7.10.4rcu: Make
list_splice_init_rcu()account for RCU readersThe
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 ofINIT_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 anINIT_LIST_HEAD_RCU()that usesACCESS_ONCE()to make the updates reader-safe. The reason that we can useACCESS_ONCE()instead of the more typicalrcu_assign_pointer()is thatlist_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 <[email protected]>include/linux/rculist.h +21
-2@@ -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.
Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
A message that is not in the archive (sent off-list or not yet received): 20130823171653.GA16558@Krystal
Quoted 157 lines · On Fri, 23 Aug 2013 13:16:53 -0400 Mathieu Desnoyers…
Quoted 41 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 40 lines · Stephen Hemminger
I needed to add into the middle of an RCU list, does this make sense.
From
a45892b0d49ac5fe449ba7e19c646cb17f7cee57Mon Sep 17 00:00:00 2001
From: Stephen Hemminger <[email protected]>
Date: Thu, 22 Aug 2013 21:27:04 -0700
Subject: [PATCH] Addlist_splice_init_rcuto allow insertion into a RCU listSimplified version of the version in kernel.
--- urcu/rculist.h | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+)urcu/rculist.h +18
-0@@ -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 ;Quoted 8 lines
urcu/rculist.h void cds_list_del_rcu(struct cds_list_head *elem) · line 95
Quoted 3 lines
urcu/rculist.h +3
-0+ +/* "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 useCMM_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.
Quoted 2 lines
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()withCMM_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
Quoted 76 lines
Patch below, FWIW.
Thanx, Paul
Quoted 16 lines
urcu/rculist.h +11
-0+ +/* 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. Signature · 1 line
1.7.10.4rcu: Make
list_splice_init_rcu()account for RCU readersThe
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 ofINIT_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 anINIT_LIST_HEAD_RCU()that usesACCESS_ONCE()to make the updates reader-safe. The reason that we can useACCESS_ONCE()instead of the more typicalrcu_assign_pointer()is thatlist_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 <[email protected]>include/linux/rculist.h +20
-1@@ -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(). +*/
Quoted 7 lines
include/linux/rculist.h static inline void list_splice_init_rcu(struct list_head *list, · line 218
Quoted 6 lines
include/linux/rculist.h +1
-1-INIT_LIST_HEAD (list); +INIT_LIST_HEAD_RCU (list);/* * At this point, the list body still points to the source list.
For what I need, it is probably simpler to do "insert in middle" rather than a full splice, so I am checking how to do that.
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 163 lines · Stephen Hemminger
Quoted 160 lines · On Fri, 23 Aug 2013 13:16:53 -0400 Mathieu Desnoyers…
Quoted 41 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 40 lines · Stephen Hemminger
I needed to add into the middle of an RCU list, does this make sense.
From
a45892b0d49ac5fe449ba7e19c646cb17f7cee57Mon Sep 17 00:00:00 2001
From: Stephen Hemminger <[email protected]>
Date: Thu, 22 Aug 2013 21:27:04 -0700
Subject: [PATCH] Addlist_splice_init_rcuto allow insertion into a RCU listSimplified version of the version in kernel.
--- urcu/rculist.h | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+)urcu/rculist.h +18
-0@@ -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 ;Quoted 8 lines
urcu/rculist.h void cds_list_del_rcu(struct cds_list_head *elem) · line 95
Quoted 3 lines
urcu/rculist.h +3
-0+ +/* "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 useCMM_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.
Quoted 2 lines
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()withCMM_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
Quoted 79 lines
Patch below, FWIW.
Thanx, Paul
Quoted 16 lines
urcu/rculist.h +11
-0+ +/* 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. Signature · 1 line
1.7.10.4rcu: Make
list_splice_init_rcu()account for RCU readersThe
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 ofINIT_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 anINIT_LIST_HEAD_RCU()that usesACCESS_ONCE()to make the updates reader-safe. The reason that we can useACCESS_ONCE()instead of the more typicalrcu_assign_pointer()is thatlist_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 <[email protected]>include/linux/rculist.h +21
-2@@ -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);
Quoted 7 lines
Quoted 4 lines
include/linux/rculist.h static inline void list_splice_init_rcu(struct list_head *list, · line 218
Quoted 3 lines
include/linux/rculist.h +0
-0/* * At this point, the list body still points to the source list. For what I need, it is probably simpler to do "insert in middle" rather than a full splice, so I am checking how to do that.
If you are inserting a new element not accessible to readers in the middle of the list, you should be able to use cds_list_add_rcu() treating the predecessor cds_list_head as the list header. Or am I missing something here?
Thanx, Paul
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 169 lines · On Fri, 23 Aug 2013 14:05:51 -0700 "Paul E. McKenney"…
Quoted 168 lines · Stephen Hemminger
Quoted 164 lines · On Fri, 23 Aug 2013 13:16:53 -0400 Mathieu Desnoyers…
Quoted 41 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 40 lines · Stephen Hemminger
I needed to add into the middle of an RCU list, does this make sense.
From
a45892b0d49ac5fe449ba7e19c646cb17f7cee57Mon Sep 17 00:00:00 2001
From: Stephen Hemminger <[email protected]>
Date: Thu, 22 Aug 2013 21:27:04 -0700
Subject: [PATCH] Addlist_splice_init_rcuto allow insertion into a RCU listSimplified version of the version in kernel.
--- urcu/rculist.h | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+)urcu/rculist.h +18
-0@@ -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 ;Quoted 8 lines
urcu/rculist.h void cds_list_del_rcu(struct cds_list_head *elem) · line 95
Quoted 3 lines
urcu/rculist.h +3
-0+ +/* "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 useCMM_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.
Quoted 2 lines
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()withCMM_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
Quoted 82 lines
Patch below, FWIW.
Thanx, Paul
Quoted 16 lines
urcu/rculist.h +11
-0+ +/* 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. Signature · 1 line
1.7.10.4rcu: Make
list_splice_init_rcu()account for RCU readersThe
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 ofINIT_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 anINIT_LIST_HEAD_RCU()that usesACCESS_ONCE()to make the updates reader-safe. The reason that we can useACCESS_ONCE()instead of the more typicalrcu_assign_pointer()is thatlist_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 <[email protected]>include/linux/rculist.h +21
-2@@ -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.
Quoted 7 lines
Quoted 2 lines
For what I need, it is probably simpler to do "insert in middle" rather than a full splice, so I am checking how to do that.
If you are inserting a new element not accessible to readers in the middle of the list, you should be able to use
cds_list_add_rcu()treating the predecessorcds_list_headas the list header. Or am I missing something here?
Yeah, that is what I was thinking, as long as the ordering is correct.
Quoted 61 lines · Mathieu Desnoyers
Quoted 41 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 40 lines · Stephen Hemminger
I needed to add into the middle of an RCU list, does this make sense.
From
a45892b0d49ac5fe449ba7e19c646cb17f7cee57Mon Sep 17 00:00:00 2001
From: Stephen Hemminger <[email protected]>
Date: Thu, 22 Aug 2013 21:27:04 -0700
Subject: [PATCH] Addlist_splice_init_rcuto allow insertion into a RCU listSimplified version of the version in kernel.
--- urcu/rculist.h | 32 ++++++++++++++++++++++++++++++++ 1 file changed, 32 insertions(+)urcu/rculist.h +18
-0@@ -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 ;Quoted 8 lines
urcu/rculist.h void cds_list_del_rcu(struct cds_list_head *elem) · line 95
Quoted 3 lines
urcu/rculist.h +3
-0+ +/* "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 useCMM_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.
Quoted 2 lines
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:
Quoted 5 lines
#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. ;-)
Quoted 8 lines
In userspace RCU, we require to match
CMM_LOAD_SHARED()withCMM_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
Quoted 93 lines
Thanks,
Mathieu
Quoted 82 lines
Patch below, FWIW.
Thanx, Paul
Quoted 16 lines
urcu/rculist.h +11
-0+ +/* 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. Signature · 1 line
1.7.10.4rcu: Make
list_splice_init_rcu()account for RCU readersThe
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 ofINIT_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 anINIT_LIST_HEAD_RCU()that usesACCESS_ONCE()to make the updates reader-safe. The reason that we can useACCESS_ONCE()instead of the more typicalrcu_assign_pointer()is thatlist_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 <[email protected]>include/linux/rculist.h +21
-2@@ -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. Signature · 3 lines
Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 3 lines · Paul E. McKenney
Quoted 2 lines · Mathieu Desnoyers
Quoted 1 line · * Paul E. McKenney ([email protected]) wrote:
On Thu, Aug 22, 2013 at 09:33:18PM -0700, Stephen Hemminger wrote:
[ . . . ]
Quoted 36 lines
Quoted 36 lines
Quoted 18 lines
Quoted 18 lines
(quoted diff) +18
-0+ +/** + * 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;Quoted 8 lines
Review
Quoted 3 lines
(quoted diff) +3
-0+ + /* "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 useCMM_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.
Quoted 1 line
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:
Quoted 7 lines
Quoted 5 lines
#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
Josh Triplett
maintainerQuoted 8 lines · Paul E. McKenney
Quoted 7 lines · Paul E. McKenney
Quoted 5 lines · Mathieu Desnoyers
#define __rcu_assign_pointer(p, v, space) \ do { \ smp_wmb(); \ (p) = (typeof(*v) __force space *)(v); \ } while (0)
Quoted 5 lines
Quoted 1 line
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 anACCESS_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) *) ⌖
typeof(foo) bar = foo;
return *bar;
}
$ sparse test.c
test.c:9:13: warning: dereference of noderef expressionNotice 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
Quoted 32 lines · Josh Triplett
Quoted 8 lines · Paul E. McKenney
Quoted 7 lines · Paul E. McKenney
Quoted 5 lines · Mathieu Desnoyers
#define __rcu_assign_pointer(p, v, space) \ do { \ smp_wmb(); \ (p) = (typeof(*v) __force space *)(v); \ } while (0)Quoted 5 lines
Quoted 1 line
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 anACCESS_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), nottypeof(*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) *) ⌖ typeof(foo) bar = foo; return *bar; } $ sparse test.c test.c:9:13: warning: dereference of noderef expression
Quoted 3 lines
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
Josh Triplett
maintainerQuoted 47 lines · Paul E. McKenney
Quoted 32 lines · Josh Triplett
Quoted 8 lines · Paul E. McKenney
Quoted 7 lines · Paul E. McKenney
Quoted 5 lines · Mathieu Desnoyers
#define __rcu_assign_pointer(p, v, space) \ do { \ smp_wmb(); \ (p) = (typeof(*v) __force space *)(v); \ } while (0)Quoted 5 lines
Quoted 1 line
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 anACCESS_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), nottypeof(*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) *) ⌖ typeof(foo) bar = foo; return *bar; } $ sparse test.c test.c:9:13: warning: dereference of noderef expressionQuoted 3 lines
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)
Quoted 6 lines
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 __force __attribute__((force))
#define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x)) extern void __chk_kernel_ptr(const volatile void *); extern void smp_wmb(void);
#define rcu_assign_pointer(p, v) \
do { \
smp_wmb(); \
__chk_kernel_ptr(v); \
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;
struct foo __user *badsrc = (void *)0;
rcu_assign_pointer(dest, src);
rcu_assign_pointer(dest, badsrc);
return 0;
}This produces a somewhat better warning:
test.c:25:5: warning: incorrect type in argument 1 (different address spaces)
test.c:25:5: expected void const volatile *<noident>
test.c:25:5: got struct foo [noderef] <asn:1>*badsrc
That at least shows the full type of badsrc, but it still seems suboptimal for two reasons: it says it expects "void const volatile *" rather than the actual type it wants, and it says "in argument 1" (of __chk_kernel_ptr), which seems unnecessarily confusing when the type error actually applies to argument 2 of rcu_assign_pointer. We can do better by declaring a fake local function for checking, instead:
#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(); \
extern void __rcu_assign_pointer_typecheck(int, typeof(*(v)) __kernel *); \
__rcu_assign_pointer_typecheck(0, v); \
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;
struct foo __user *badsrc = (void *)0;
rcu_assign_pointer(dest, src);
rcu_assign_pointer(dest, badsrc);
return 0;
}This last approach produces a very clear warning:
test.c:25:5: warning: incorrect type in argument 2 (different address spaces)
test.c:25:5: expected struct foo *<noident>
test.c:25:5: got struct foo [noderef] <asn:1>*badsrc
If you want, you can even add an argument name for the second argument of __rcu_assign_pointer_typecheck, and it'll replace the <noident> in the second line of the warning.
So, that last approach meets all the criteria you mentioned:
Quoted 2 lines
something that (1) does sparse address-space checking, (2) does C type checking, and (3) forces the assignment to be volatile.
Will that work for all the use cases you have in mind? If so, I'll submit a patch changing rcu_assign_pointer to use that approach.
- Josh Triplett
Quoted 240 lines · Josh Triplett
Quoted 47 lines · Paul E. McKenney
Quoted 32 lines · Josh Triplett
Quoted 8 lines · Paul E. McKenney
Quoted 7 lines · Paul E. McKenney
Quoted 5 lines · Mathieu Desnoyers
#define __rcu_assign_pointer(p, v, space) \ do { \ smp_wmb(); \ (p) = (typeof(*v) __force space *)(v); \ } while (0)Quoted 5 lines
Quoted 1 line
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 anACCESS_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), nottypeof(*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) *) ⌖ typeof(foo) bar = foo; return *bar; } $ sparse test.c test.c:9:13: warning: dereference of noderef expressionQuoted 3 lines
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)Quoted 6 lines
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))
#defineACCESS_ONCE(x)(*(volatile typeof(x) *)&(x)) extern voidsmp_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
__rcuaddress 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))
#defineACCESS_ONCE(x)(*(volatile typeof(x) *)&(x)) extern voidsmp_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
__rcuaddress 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))
#defineACCESS_ONCE(x)(*(volatile typeof(x) *)&(x)) extern voidsmp_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_pointerdoesn'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_ptrfunction, similar to__chk_user_ptrincompiler.h:#define
__kernel__attribute__((address_space(0))) #define__user__attribute__((address_space(1),noderef)) #define__rcu__attribute__((address_space(4),noderef)) #define__force__attribute__((force))
#defineACCESS_ONCE(x)(*(volatile typeof(x) *)&(x)) extern void__chk_kernel_ptr(const volatile void *); extern voidsmp_wmb(void);#define rcu_assign_pointer(p, v) \ do { \ smp_wmb(); \ __chk_kernel_ptr(v); \ 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; struct foo __user *badsrc = (void *)0; rcu_assign_pointer(dest, src); rcu_assign_pointer(dest, badsrc); return 0; }This produces a somewhat better warning:
test.c:25:5: warning: incorrect type in argument 1 (different address spaces)
test.c:25:5: expected void const volatile *<noident>
test.c:25:5: got struct foo [noderef] <asn:1>*badsrcThat at least shows the full type of badsrc, but it still seems suboptimal for two reasons: it says it expects "void const volatile *" rather than the actual type it wants, and it says "in argument 1" (of
__chk_kernel_ptr), which seems unnecessarily confusing when the type error actually applies to argument 2 ofrcu_assign_pointer. We can do better by declaring a fake local function for checking, instead:#define
__kernel__attribute__((address_space(0))) #define__user__attribute__((address_space(1),noderef)) #define__rcu__attribute__((address_space(4),noderef)) #define__force__attribute__((force))
#defineACCESS_ONCE(x)(*(volatile typeof(x) *)&(x)) extern voidsmp_wmb(void);#define rcu_assign_pointer(p, v) \ do { \ smp_wmb(); \ extern void __rcu_assign_pointer_typecheck(int, typeof(*(v)) __kernel *); \ __rcu_assign_pointer_typecheck(0, v); \ 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; struct foo __user *badsrc = (void *)0; rcu_assign_pointer(dest, src); rcu_assign_pointer(dest, badsrc); return 0; }This last approach produces a very clear warning:
test.c:25:5: warning: incorrect type in argument 2 (different address spaces)
test.c:25:5: expected struct foo *<noident>
test.c:25:5: got struct foo [noderef] <asn:1>*badsrcIf you want, you can even add an argument name for the second argument of
__rcu_assign_pointer_typecheck, and it'll replace the <noident> in the second line of the warning.
Quoted 6 lines
So, that last approach meets all the criteria you mentioned:
Quoted 2 lines
something that (1) does sparse address-space checking, (2) does C type checking, and (3) forces the assignment to be volatile.
Will that work for all the use cases you have in mind? If so, I'll submit a patch changing
rcu_assign_pointerto use that approach.
Looks like it does the right thing, thank you!
Would it also be possible for the call to __rcu_assign_pointer_typecheck() to be only present when building under sparse?
Thanx, Paul
Josh Triplett
maintainerQuoted 245 lines · Paul E. McKenney
Quoted 244 lines · Josh Triplett
Quoted 47 lines · Paul E. McKenney
Quoted 32 lines · Josh Triplett
Quoted 8 lines · Paul E. McKenney
Quoted 7 lines · Paul E. McKenney
Quoted 5 lines · Mathieu Desnoyers
#define __rcu_assign_pointer(p, v, space) \ do { \ smp_wmb(); \ (p) = (typeof(*v) __force space *)(v); \ } while (0)Quoted 5 lines
Quoted 1 line
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 anACCESS_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), nottypeof(*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) *) ⌖ typeof(foo) bar = foo; return *bar; } $ sparse test.c test.c:9:13: warning: dereference of noderef expressionQuoted 3 lines
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)Quoted 6 lines
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))
#defineACCESS_ONCE(x)(*(volatile typeof(x) *)&(x)) extern voidsmp_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
__rcuaddress 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))
#defineACCESS_ONCE(x)(*(volatile typeof(x) *)&(x)) extern voidsmp_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
__rcuaddress 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))
#defineACCESS_ONCE(x)(*(volatile typeof(x) *)&(x)) extern voidsmp_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_pointerdoesn'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_ptrfunction, similar to__chk_user_ptrincompiler.h:#define
__kernel__attribute__((address_space(0))) #define__user__attribute__((address_space(1),noderef)) #define__rcu__attribute__((address_space(4),noderef)) #define__force__attribute__((force))
#defineACCESS_ONCE(x)(*(volatile typeof(x) *)&(x)) extern void__chk_kernel_ptr(const volatile void *); extern voidsmp_wmb(void);#define rcu_assign_pointer(p, v) \ do { \ smp_wmb(); \ __chk_kernel_ptr(v); \ 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; struct foo __user *badsrc = (void *)0; rcu_assign_pointer(dest, src); rcu_assign_pointer(dest, badsrc); return 0; }This produces a somewhat better warning:
test.c:25:5: warning: incorrect type in argument 1 (different address spaces)
test.c:25:5: expected void const volatile *<noident>
test.c:25:5: got struct foo [noderef] <asn:1>*badsrcThat at least shows the full type of badsrc, but it still seems suboptimal for two reasons: it says it expects "void const volatile *" rather than the actual type it wants, and it says "in argument 1" (of
__chk_kernel_ptr), which seems unnecessarily confusing when the type error actually applies to argument 2 ofrcu_assign_pointer. We can do better by declaring a fake local function for checking, instead:#define
__kernel__attribute__((address_space(0))) #define__user__attribute__((address_space(1),noderef)) #define__rcu__attribute__((address_space(4),noderef)) #define__force__attribute__((force))
#defineACCESS_ONCE(x)(*(volatile typeof(x) *)&(x)) extern voidsmp_wmb(void);#define rcu_assign_pointer(p, v) \ do { \ smp_wmb(); \ extern void __rcu_assign_pointer_typecheck(int, typeof(*(v)) __kernel *); \ __rcu_assign_pointer_typecheck(0, v); \ 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; struct foo __user *badsrc = (void *)0; rcu_assign_pointer(dest, src); rcu_assign_pointer(dest, badsrc); return 0; }This last approach produces a very clear warning:
test.c:25:5: warning: incorrect type in argument 2 (different address spaces)
test.c:25:5: expected struct foo *<noident>
test.c:25:5: got struct foo [noderef] <asn:1>*badsrcIf you want, you can even add an argument name for the second argument of
__rcu_assign_pointer_typecheck, and it'll replace the <noident> in the second line of the warning.So, that last approach meets all the criteria you mentioned:
Quoted 2 lines
something that (1) does sparse address-space checking, (2) does C type checking, and (3) forces the assignment to be volatile.
Quoted 7 lines
Quoted 2 lines
Will that work for all the use cases you have in mind? If so, I'll submit a patch changing
rcu_assign_pointerto use that approach.Looks like it does the right thing, thank you!
Would it also be possible for the call to
__rcu_assign_pointer_typecheck()to be only present when building under sparse?
Sure; it just needs to go in a separate macro that only gets a non-empty definition ifdef __CHECKER__.
Patch momentarily.
- Josh Triplett
Josh Triplett
maintainerPATCH 1/1 rcu: Make rcu_assign_pointer's assignment volatile and type-safe
rcu_assign_pointer needs to use ACCESS_ONCE to make the assignment to the destination pointer volatile, to protect against compilers too clever for their own good.
In addition, since rcu_assign_pointer force-casts the source pointer to add the __rcu address space (overriding any existing address space), add an explicit check that the source pointer has the __kernel address space to start with.
This new check produces warnings like this, when attempting to assign from a __user pointer:
test.c:25:9: warning: incorrect type in argument 2 (different address spaces)
test.c:25:9: expected struct foo *<noident>
test.c:25:9: got struct foo [noderef] <asn:1>*badsrc
--- include/linux/rcupdate.h | 12 +++++++++++- 1 file changed, 11 insertions(+), 1 deletion(-)
include/linux/rcupdate.h +11 -1
@@ -510,8 +510,17 @@ static inline void rcu_preempt_sleep_check(void)#ifdef __CHECKER__#define rcu_dereference_sparse (p, space) \ ((void)(((typeof(*p) space *)p) == p)) +/* The dummy first argument in __rcu_assign_pointer_typecheck makes the +* typechecked pointer the second argument, matching rcu_assign_pointer itself; +* this avoids confusion about argument numbers in warning messages. */ +#define __rcu_assign_pointer_check_kernel (v) \ + do { \ + extern void __rcu_assign_pointer_typecheck(int, typeof(*(v)) __kernel *); \ + __rcu_assign_pointer_typecheck(0, v); \ + } while (0)#else /* #ifdef __CHECKER__ */ #define rcu_dereference_sparse (p, space) +#define __rcu_assign_pointer_check_kernel (v) do { } while (0)#endif /* #else #ifdef __CHECKER__ */ #define __rcu_access_pointer (p, space) \
@@ -555,7 +564,8 @@ static inline void rcu_preempt_sleep_check(void)#define __rcu_assign_pointer (p, v, space) \ do { \ smp_wmb(); \ - (p) = (typeof(*v) __force space *)(v); \ + __rcu_assign_pointer_check_kernel(v); \ + ACCESS_ONCE(p) = (typeof(*(v)) __force space *)(v); \ } while (0)
Paul E. McKenney
AppliedRe: [PATCH] rcu: Make rcu_assign_pointer's assignment volatile and type-safe
Quoted 9 lines · Josh Triplett
rcu_assign_pointerneeds to useACCESS_ONCEto make the assignment to the destination pointer volatile, to protect against compilers too clever for their own good.In addition, since
rcu_assign_pointerforce-casts the source pointer to add the__rcuaddress space (overriding any existing address space), add an explicit check that the source pointer has the__kerneladdress space to start with.
Quoted 8 lines
This new check produces warnings like this, when attempting to assign from a
__userpointer:test.c:25:9: warning: incorrect type in argument 2 (different address spaces)
test.c:25:9: expected struct foo *<noident>
test.c:25:9: got struct foo [noderef] <asn:1>*badsrcSigned-off-by Josh Triplett <[email protected]>
Queued for 3.13, thank you very much!
Thanx, Paul
Quoted 42 lines
--- include/linux/rcupdate.h | 12 +++++++++++- 1 file changed, 11 insertions(+), 1 deletion(-)include/linux/rcupdate.h +11
-2@@ -510,8 +510,17 @@ static inline void rcu_preempt_sleep_check(void)#ifdef __CHECKER__#define rcu_dereference_sparse (p, space) \ ((void)(((typeof(*p) space *)p) == p)) +/* The dummy first argument in __rcu_assign_pointer_typecheck makes the +* typechecked pointer the second argument, matching rcu_assign_pointer itself; +* this avoids confusion about argument numbers in warning messages. */ +#define __rcu_assign_pointer_check_kernel (v) \ + do { \ + extern void __rcu_assign_pointer_typecheck(int, typeof(*(v)) __kernel *); \ + __rcu_assign_pointer_typecheck(0, v); \ + } while (0)#else /* #ifdef __CHECKER__ */ #define rcu_dereference_sparse (p, space) +#define __rcu_assign_pointer_check_kernel (v) do { } while (0)#endif /* #else #ifdef __CHECKER__ */ #define __rcu_access_pointer (p, space) \@@ -555,7 +564,8 @@ static inline void rcu_preempt_sleep_check(void)#define __rcu_assign_pointer (p, v, space) \ do { \ smp_wmb(); \ - (p) = (typeof(*v) __force space *)(v); \ + __rcu_assign_pointer_check_kernel(v); \ + ACCESS_ONCE(p) = (typeof(*(v)) __force space *)(v); \ } while (0) --To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Josh Triplett
maintainerQuoted 8 lines · Paul E. McKenney
Quoted 7 lines · Paul E. McKenney
Quoted 5 lines · Mathieu Desnoyers
#define __rcu_assign_pointer(p, v, space) \ do { \ smp_wmb(); \ (p) = (typeof(*v) __force space *)(v); \ } while (0)
Quoted 5 lines
Quoted 1 line
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 anACCESS_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) *) ⌖
typeof(foo) bar = foo;
return *bar;
}
$ sparse test.c
test.c:9:13: warning: dereference of noderef expressionNotice 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