rculist: add list_splice_rcu() for private lists
Pablo Neira Ayuso
maintainerPATCH 1/3 rculist: add list_splice_rcu() for private lists
This patch adds a helper function, list_splice_rcu(), to safely splice a private (non-RCU-protected) list into an RCU-protected list.
The function ensures that only the pointer visible to RCU readers (prev->next) is updated using rcu_assign_pointer(), while the rest of the list manipulations are performed with regular assignments, as the source list is private and not visible to concurrent RCU readers.
This is useful for moving elements from a private list into a global RCU-protected list, ensuring safe publication for RCU readers. Subsystems with some sort of batching mechanism from userspace can benefit from this new function.
---
@I need this to fix a unsafe list_splice() of a private list to an existing RCU-protected list. This is based on an existing idiom in __list_splice_init_rcu().
include/linux/rculist.h | 35 +++++++++++++++++++++++++++++++++++ 1 file changed, 35 insertions(+)
include/linux/rculist.h +35 -0
@@ -261,6 +261,41 @@ static inline void list_replace_rcu(struct list_head *old, old->prev =LIST_POISON2 ; } +/** +* __list_splice_rcu - join a non-RCU list into an existing list. +* @list: the RCU-protected list to splice +* @prev: points to the last element of the existing list +* @next: points to the first element of the existing list +* +* The list pointed to by @prev and @next can be RCU-read traversed +* concurrently with this function. +*/ +static inline void __list_splice_rcu (struct list_head *list, +struct list_head *prev, +struct list_head *next) +{ +struct list_head *first = list->next; +struct list_head *last = list->prev; + + last->next = next; +rcu_assign_pointer (list_next_rcu (prev), first); + first->prev = prev; + next->prev = last; +} + +/** +* list_splice_rcu - splice a non-RCU list into an RCU-protected list, +* designed for stacks. +* @list: the non RCU-protected list to splice +* @head: the place in the existing list to splice the first list into +*/ +static inline void list_splice_rcu (struct list_head *list, +struct list_head *head) +{ +if (!list_empty (list)) +__list_splice_rcu (list, head, head->next); +} +/** * __list_splice_init_rcu - join an RCU-protected list into an existing list. * @list: the RCU-protected list to splice
Signature · 1 line
2.47.3
Paul E. McKenney
maintainerQuoted 8 lines · Pablo Neira Ayuso
This patch adds a helper function,
list_splice_rcu(), to safely splice a private (non-RCU-protected) list into an RCU-protected list.The function ensures that only the pointer visible to RCU readers (
prev->next) is updated usingrcu_assign_pointer(), while the rest of the list manipulations are performed with regular assignments, as the source list is private and not visible to concurrent RCU readers.
Quoted 6 lines
This is useful for moving elements from a private list into a global RCU-protected list, ensuring safe publication for RCU readers. Subsystems with some sort of batching mechanism from userspace can benefit from this new function.
Signed-off-by Pablo Neira Ayuso <[email protected]>
Looks plausible and useful. Please see some comments inline below.
Quoted 13 lines
---
@I need this to fix a unsafelist_splice()of a private list to an existing RCU-protected list. This is based on an existing idiom in__list_splice_init_rcu().include/linux/rculist.h | 35 +++++++++++++++++++++++++++++++++++ 1 file changed, 35 insertions(+)include/linux/rculist.h +0
-0
include/linux/rculist.h static inline void list_replace_rcu(struct list_head *old, · line 266
Quoted 6 lines
include/linux/rculist.h +3
-0@@ -261,6 +261,41 @@ static inline void list_replace_rcu(struct list_head *old, old->prev =LIST_POISON2 ; } +/** +* __list_splice_rcu - join a non-RCU list into an existing list. +* @list: the RCU-protected list to splice
This is actually not RCU-protected, correct? Sure, its elements (aside from the list header) are RCU-protected upon exit from this function, but by then they are in the {@prev,@next} list, not in this @list.
include/linux/rculist.h static inline void list_replace_rcu(struct list_head *old, · line 271
Quoted 5 lines
include/linux/rculist.h +5
-0+* @prev: points to the last element of the existing list +* @next: points to the first element of the existing list +* +* The list pointed to by @prev and @next can be RCU-read traversed +* concurrently with this function.
Doesn't this last sentence also need to go into the list_splice_rcu() function's kernel-doc header? But please see below.
include/linux/rculist.h static inline void list_replace_rcu(struct list_head *old, · line 283
Quoted 12 lines
include/linux/rculist.h +12
-0+*/ +static inline void __list_splice_rcu (struct list_head *list, +struct list_head *prev, +struct list_head *next) +{ +struct list_head *first = list->next; +struct list_head *last = list->prev; + + last->next = next; +rcu_assign_pointer (list_next_rcu (prev), first); + first->prev = prev; + next->prev = last;
Although putting these last two after the rcu_assign_pointer() is safe, given that RCU readers do not traverse ->prev pointers, it would be better to place them before the rcu_assign_pointer() in order to avoid false sharing between this code path and any concurrent RCU readers.
include/linux/rculist.h static inline void list_replace_rcu(struct list_head *old, · line 290
Quoted 7 lines
include/linux/rculist.h +7
-0+} + +/** +* list_splice_rcu - splice a non-RCU list into an RCU-protected list, +* designed for stacks. +* @list: the non RCU-protected list to splice +* @head: the place in the existing list to splice the first list into
Please add something about @head being RCU-protected.
include/linux/rculist.h static inline void list_replace_rcu(struct list_head *old, · line 297
Quoted 7 lines
include/linux/rculist.h +7
-0+*/ +static inline void list_splice_rcu (struct list_head *list, +struct list_head *head) +{ +if (!list_empty (list)) +__list_splice_rcu (list, head, head->next); +}
I don't understand the purpose of having __list_splice_rcu() split out from list_splice_rcu(). If you are planning to add more callers of __list_splice_rcu(), you can always do the split when you add the first such caller. In the meantime, why the extra code?
Yes, we do have __list_splice_init_rcu(), but that is because it is called from both list_splice_init_rcu() and list_splice_tail_init_rcu().
Quoted 7 lines
include/linux/rculist.h +1
-0+/** * __list_splice_init_rcu - join an RCU-protected list into an existing list. * @list: the RCU-protected list to splice Signature · 1 line
2.47.3
Pablo Neira Ayuso
maintainerHi Paul,
Thanks for your review.
Quoted 9 lines · Paul E. McKenney
Quoted 8 lines · Pablo Neira Ayuso
This patch adds a helper function,
list_splice_rcu(), to safely splice a private (non-RCU-protected) list into an RCU-protected list.The function ensures that only the pointer visible to RCU readers (
prev->next) is updated usingrcu_assign_pointer(), while the rest of the list manipulations are performed with regular assignments, as the source list is private and not visible to concurrent RCU readers.
Quoted 8 lines
Quoted 6 lines
This is useful for moving elements from a private list into a global RCU-protected list, ensuring safe publication for RCU readers. Subsystems with some sort of batching mechanism from userspace can benefit from this new function.
Signed-off-by Pablo Neira Ayuso <[email protected]>Looks plausible and useful. Please see some comments inline below.
Thanks, see below.
Quoted 16 lines
Quoted 16 lines
---
@I need this to fix a unsafelist_splice()of a private list to an existing RCU-protected list. This is based on an existing idiom in__list_splice_init_rcu().include/linux/rculist.h | 35 +++++++++++++++++++++++++++++++++++ 1 file changed, 35 insertions(+)include/linux/rculist.h +0
-0@@ -261,6 +261,41 @@ static inline void list_replace_rcu(struct list_head *old, old->prev =LIST_POISON2 ; }
Quoted 8 lines
include/linux/rculist.h static inline void list_replace_rcu(struct list_head *old, · line 266
Quoted 3 lines
include/linux/rculist.h +3
-0+/** +* __list_splice_rcu - join a non-RCU list into an existing list. +* @list: the RCU-protected list to splice This is actually not RCU-protected, correct? Sure, its elements (aside from the list header) are RCU-protected upon exit from this function, but by then they are in the {@prev,@next} list, not in this @list.
Correct, I can fix this.
Quoted 8 lines
include/linux/rculist.h static inline void list_replace_rcu(struct list_head *old, · line 271
Quoted 5 lines
include/linux/rculist.h +5
-0+* @prev: points to the last element of the existing list +* @next: points to the first element of the existing list +* +* The list pointed to by @prev and @next can be RCU-read traversed +* concurrently with this function. Doesn't this last sentence also need to go into the
list_splice_rcu()function's kernel-doc header? But please see below.
OK.
Quoted 9 lines
Quoted 9 lines
include/linux/rculist.h +9
-0+*/ +static inline void __list_splice_rcu (struct list_head *list, +struct list_head *prev, +struct list_head *next) +{ +struct list_head *first = list->next; +struct list_head *last = list->prev; + + last->next = next;
Quoted 8 lines
include/linux/rculist.h static inline void list_replace_rcu(struct list_head *old, · line 283
Quoted 3 lines
include/linux/rculist.h +3
-0+rcu_assign_pointer (list_next_rcu (prev), first); + first->prev = prev; + next->prev = last;Although putting these last two after the
rcu_assign_pointer()is safe, given that RCU readers do not traverse ->prev pointers, it would be better to place them before thercu_assign_pointer()in order to avoid false sharing between this code path and any concurrent RCU readers.
I can do that.
Quoted 9 lines
include/linux/rculist.h static inline void list_replace_rcu(struct list_head *old, · line 290
Quoted 7 lines
include/linux/rculist.h +7
-0+} + +/** +* list_splice_rcu - splice a non-RCU list into an RCU-protected list, +* designed for stacks. +* @list: the non RCU-protected list to splice +* @head: the place in the existing list to splice the first list into Please add something about @head being RCU-protected.
Will do.
Quoted 4 lines
Quoted 4 lines
include/linux/rculist.h +4
-0+*/ +static inline void list_splice_rcu (struct list_head *list, +struct list_head *head) +{
Quoted 8 lines
include/linux/rculist.h static inline void list_replace_rcu(struct list_head *old, · line 297
Quoted 3 lines
include/linux/rculist.h +3
-0+if (!list_empty (list)) +__list_splice_rcu (list, head, head->next); +}I don't understand the purpose of having
__list_splice_rcu()split out fromlist_splice_rcu(). If you are planning to add more callers of__list_splice_rcu(), you can always do the split when you add the first such caller. In the meantime, why the extra code?
I only have a use-case for list_splice_rcu(), so OK, single function is fine with.
Quoted 2 lines
Yes, we do have
__list_splice_init_rcu(), but that is because it is called from bothlist_splice_init_rcu()andlist_splice_tail_init_rcu().
Understood.
I will be posting a v2 asap.
Thanks!
Quoted 7 lines
Quoted 7 lines
include/linux/rculist.h +1
-0+/** * __list_splice_init_rcu - join an RCU-protected list into an existing list. * @list: the RCU-protected list to splice Signature · 1 line
2.47.3