Skip to contentSkip to conversation

rculist: add list_splice_rcu() for private lists

PATCH Superseded Pablo Neira Ayuso 2 participants 3 messages Apr 13 – Apr 15

Subsystems (2)

v1 of 5 Superseded Latest is v5 →

lore
Share & tools
lore

Pablo Neira Ayuso

author maintainer
#0 lore raw

PATCH 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
index 2abba7552605..3c18c3336459 100644
@@ -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
maintainer
#1 lore raw
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 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.

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.

Looks plausible and useful. Please see some comments inline below.

Quoted 13 lines

---
@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 +0 -0
index 2abba7552605..3c18c3336459 100644

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
author maintainer
#2 lore raw

Hi 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 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.

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.

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 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 +0 -0
index 2abba7552605..3c18c3336459 100644
@@ -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 the rcu_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 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?

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 both list_splice_init_rcu() and list_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