Skip to contentSkip to conversation

rcu: Fix rculist_nulls and doc

PATCH In review Alan Huang 3 participants 11 messages Jul 6, 2023 – Jul 11, 2023

Subsystems (2)
lore
Share & tools
lore

Alan Huang

author
#0 lore raw

cover rcu: Fix rculist_nulls and doc

Fix cases where using rculist_nulls combined with SLAB_TYPESAFE_BY_RCU.

Alan Huang (2):
rcu: Use WRITE_ONCE() for assignments to ->next for rculist_nulls docs/RCU: Bring back smp_wmb()

 Documentation/RCU/rculist_nulls.rst | 9 +++++++--
 include/linux/rculist_nulls.h       | 4 ++--
 2 files changed, 9 insertions(+), 4 deletions(-)
Signature · 1 line
2.34.1
author
#1 lore raw

PATCH 1/2 rcu: Use WRITE_ONCE() for assignments to ->next for rculist_nulls

When the objects managed by rculist_nulls are allocated with SLAB_TYPESAFE_BY_RCU, readers may still hold references to this object that is being added, which means the modification of ->next is visible to readers. So, this patch uses WRITE_ONCE() for assignments to ->next.

---
 include/linux/rculist_nulls.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
include/linux/rculist_nulls.h +2 -2
index ba4c00dd8005..89186c499dd4 100644
@@ -101,7 +101,7 @@ static inline void hlist_nulls_add_head_rcu(struct hlist_nulls_node *n,
 {
 	struct hlist_nulls_node *first = h->first;
 
-	n->next = first;
+	WRITE_ONCE(n->next, first);
 	WRITE_ONCE(n->pprev, &h->first);
 	rcu_assign_pointer(hlist_nulls_first_rcu(h), n);
 	if (!is_a_nulls(first))
@@ -137,7 +137,7 @@ static inline void hlist_nulls_add_tail_rcu(struct hlist_nulls_node *n,
 		last = i;
 
 	if (last) {
-		n->next = last->next;
+		WRITE_ONCE(n->next, last->next);
 		n->pprev = &last->next;
 		rcu_assign_pointer(hlist_nulls_next_rcu(last), n);
 	} else {
Signature · 1 line
2.34.1
maintainer
#2 lore raw

Re: [PATCH 1/2] rcu: Use WRITE_ONCE() for assignments to ->next for rculist_nulls

Quoted 7 lines · Alan Huang

When the objects managed by rculist_nulls are allocated with SLAB_TYPESAFE_BY_RCU, readers may still hold references to this object that is being added, which means the modification of ->next is visible to readers. So, this patch uses WRITE_ONCE() for assignments to ->next.

Very good, queued for the v6.6 merge window, thank you!

Thanx, Paul

Quoted 29 lines
---
 include/linux/rculist_nulls.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
include/linux/rculist_nulls.h +2 -2
index ba4c00dd8005..89186c499dd4 100644
@@ -101,7 +101,7 @@ static inline void hlist_nulls_add_head_rcu(struct hlist_nulls_node *n,
 {
 	struct hlist_nulls_node *first = h->first;
 
-	n->next = first;
+	WRITE_ONCE(n->next, first);
 	WRITE_ONCE(n->pprev, &h->first);
 	rcu_assign_pointer(hlist_nulls_first_rcu(h), n);
 	if (!is_a_nulls(first))
@@ -137,7 +137,7 @@ static inline void hlist_nulls_add_tail_rcu(struct hlist_nulls_node *n,
 		last = i;
 
 	if (last) {
-		n->next = last->next;
+		WRITE_ONCE(n->next, last->next);
 		n->pprev = &last->next;
 		rcu_assign_pointer(hlist_nulls_next_rcu(last), n);
 	} else {
Signature · 1 line
2.34.1
#3 lore raw

Re: [PATCH 1/2] rcu: Use WRITE_ONCE() for assignments to ->next for rculist_nulls

In reply to Alan Huang
Quoted 26 lines · Alan Huang

When the objects managed by rculist_nulls are allocated with SLAB_TYPESAFE_BY_RCU, readers may still hold references to this object that is being added, which means the modification of ->next is visible to readers. So, this patch uses WRITE_ONCE() for assignments to ->next.

---
 include/linux/rculist_nulls.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
include/linux/rculist_nulls.h +1 -1
index ba4c00dd8005..89186c499dd4 100644
@@ -101,7 +101,7 @@ static inline void hlist_nulls_add_head_rcu(struct hlist_nulls_node *n,
 {
        struct hlist_nulls_node *first = h->first;
 
-       n->next = first;
+       WRITE_ONCE(n->next, first);
        WRITE_ONCE(n->pprev, &h->first);
        rcu_assign_pointer(hlist_nulls_first_rcu(h), n);
        if (!is_a_nulls(first))

include/linux/rculist_nulls.h static inline void hlist_nulls_add_tail_rcu(struct hlist_nulls_node *n, · line 143

Quoted 8 lines
include/linux/rculist_nulls.h +1 -1
@@ -137,7 +137,7 @@ static inline void hlist_nulls_add_tail_rcu(struct hlist_nulls_node *n,
                last = i;
 
        if (last) {
-               n->next = last->next;
+               WRITE_ONCE(n->next, last->next);
                n->pprev = &last->next;
                rcu_assign_pointer(hlist_nulls_next_rcu(last), n);
        } else {

Don't you need READ_ONCE() for the read-side accesses as well?

thanks,

- Joel

maintainer
#4 lore raw

Re: [PATCH 1/2] rcu: Use WRITE_ONCE() for assignments to ->next for rculist_nulls

Quoted 29 lines · Joel Fernandes
Quoted 28 lines · Alan Huang

When the objects managed by rculist_nulls are allocated with SLAB_TYPESAFE_BY_RCU, readers may still hold references to this object that is being added, which means the modification of ->next is visible to readers. So, this patch uses WRITE_ONCE() for assignments to ->next.

---
 include/linux/rculist_nulls.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
include/linux/rculist_nulls.h +1 -1
index ba4c00dd8005..89186c499dd4 100644
@@ -101,7 +101,7 @@ static inline void hlist_nulls_add_head_rcu(struct hlist_nulls_node *n,
 {
        struct hlist_nulls_node *first = h->first;
 
-       n->next = first;
+       WRITE_ONCE(n->next, first);
        WRITE_ONCE(n->pprev, &h->first);
        rcu_assign_pointer(hlist_nulls_first_rcu(h), n);
        if (!is_a_nulls(first))
@@ -137,7 +137,7 @@ static inline void hlist_nulls_add_tail_rcu(struct hlist_nulls_node *n,
                last = i;
 
Quoted 8 lines

include/linux/rculist_nulls.h static inline void hlist_nulls_add_tail_rcu(struct hlist_nulls_node *n, · line 143

Quoted 6 lines
include/linux/rculist_nulls.h +1 -1
        if (last) {
-               n->next = last->next;
+               WRITE_ONCE(n->next, last->next);
                n->pprev = &last->next;
                rcu_assign_pointer(hlist_nulls_next_rcu(last), n);
        } else {

Don't you need READ_ONCE() for the read-side accesses as well?

Both hlist_nulls_for_each_entry_rcu() and hlist_nulls_for_each_entry_safe() use rcu_dereference_raw(). To your point, both hlist_nulls_first_rcu() and hlist_nulls_next_rcu() look rather strange. I would have expected them to also use rcu_dereference_raw().

Thanx, Paul

author
#5 lore raw

Re: [PATCH 1/2] rcu: Use WRITE_ONCE() for assignments to ->next for rculist_nulls

Quoted 42 lines

2023年7月11日 04:30,Paul E. McKenney <[email protected]> 写道:

Quoted 29 lines · Joel Fernandes
Quoted 28 lines · Alan Huang

When the objects managed by rculist_nulls are allocated with SLAB_TYPESAFE_BY_RCU, readers may still hold references to this object that is being added, which means the modification of ->next is visible to readers. So, this patch uses WRITE_ONCE() for assignments to ->next.

---
include/linux/rculist_nulls.h | 4 ++--

1 file changed, 2 insertions(+), 2 deletions(-)
include/linux/rculist_nulls.h +1 -1
index ba4c00dd8005..89186c499dd4 100644
@@ -101,7 +101,7 @@ static inline void hlist_nulls_add_head_rcu(struct hlist_nulls_node *n,
 {
       struct hlist_nulls_node *first = h->first;
 
-       n->next = first;
+       WRITE_ONCE(n->next, first);
       WRITE_ONCE(n->pprev, &h->first);
       rcu_assign_pointer(hlist_nulls_first_rcu(h), n);
       if (!is_a_nulls(first))
@@ -137,7 +137,7 @@ static inline void hlist_nulls_add_tail_rcu(struct hlist_nulls_node *n,
               last = i;
 
Quoted 8 lines

include/linux/rculist_nulls.h static inline void hlist_nulls_add_tail_rcu(struct hlist_nulls_node *n, · line 143

Quoted 6 lines
include/linux/rculist_nulls.h +1 -1
       if (last) {
-               n->next = last->next;
+               WRITE_ONCE(n->next, last->next);
               n->pprev = &last->next;
               rcu_assign_pointer(hlist_nulls_next_rcu(last), n);
       } else {

Don't you need READ_ONCE() for the read-side accesses as well?

Quoted 4 lines

Both hlist_nulls_for_each_entry_rcu() and hlist_nulls_for_each_entry_safe() use rcu_dereference_raw(). To your point, both hlist_nulls_first_rcu() and hlist_nulls_next_rcu() look rather strange. I would have expected them to also use rcu_dereference_raw().

hlist_nulls_first_rcu() and hlist_nulls_next_rcu() were added in commit:

67bdbffd696f(“rculist: avoid __rcu annotations”)

According to the commit message, this avoids warnings from missing __rcu annotations.

Quoted 2 lines

Thanx, Paul

maintainer
#6 lore raw

Re: [PATCH 1/2] rcu: Use WRITE_ONCE() for assignments to ->next for rculist_nulls

Quoted 47 lines · Alan Huang
Quoted 42 lines

2023年7月11日 04:30,Paul E. McKenney <[email protected]> 写道:

Quoted 29 lines · Joel Fernandes
Quoted 28 lines · Alan Huang

When the objects managed by rculist_nulls are allocated with SLAB_TYPESAFE_BY_RCU, readers may still hold references to this object that is being added, which means the modification of ->next is visible to readers. So, this patch uses WRITE_ONCE() for assignments to ->next.

---
include/linux/rculist_nulls.h | 4 ++--

1 file changed, 2 insertions(+), 2 deletions(-)
include/linux/rculist_nulls.h +1 -1
index ba4c00dd8005..89186c499dd4 100644
@@ -101,7 +101,7 @@ static inline void hlist_nulls_add_head_rcu(struct hlist_nulls_node *n,
 {
       struct hlist_nulls_node *first = h->first;
 
-       n->next = first;
+       WRITE_ONCE(n->next, first);
       WRITE_ONCE(n->pprev, &h->first);
       rcu_assign_pointer(hlist_nulls_first_rcu(h), n);
       if (!is_a_nulls(first))
@@ -137,7 +137,7 @@ static inline void hlist_nulls_add_tail_rcu(struct hlist_nulls_node *n,
               last = i;
 
Quoted 8 lines

include/linux/rculist_nulls.h static inline void hlist_nulls_add_tail_rcu(struct hlist_nulls_node *n, · line 143

Quoted 6 lines
include/linux/rculist_nulls.h +1 -1
       if (last) {
-               n->next = last->next;
+               WRITE_ONCE(n->next, last->next);
               n->pprev = &last->next;
               rcu_assign_pointer(hlist_nulls_next_rcu(last), n);
       } else {

Don't you need READ_ONCE() for the read-side accesses as well?

Quoted 4 lines

Both hlist_nulls_for_each_entry_rcu() and hlist_nulls_for_each_entry_safe() use rcu_dereference_raw(). To your point, both hlist_nulls_first_rcu() and hlist_nulls_next_rcu() look rather strange. I would have expected them to also use rcu_dereference_raw().

Quoted 5 lines

hlist_nulls_first_rcu() and hlist_nulls_next_rcu() were added in commit:

67bdbffd696f(“rculist: avoid __rcu annotations”)

According to the commit message, this avoids warnings from missing __rcu annotations.

Indeed it does, apologies for the noise!

Thanx, Paul

author
#7 lore raw

Re: [PATCH 1/2] rcu: Use WRITE_ONCE() for assignments to ->next for rculist_nulls

In reply to Joel Fernandes
Quoted 32 lines

2023年7月11日 04:01,Joel Fernandes <[email protected]> 写道:

Quoted 28 lines · Alan Huang

When the objects managed by rculist_nulls are allocated with SLAB_TYPESAFE_BY_RCU, readers may still hold references to this object that is being added, which means the modification of ->next is visible to readers. So, this patch uses WRITE_ONCE() for assignments to ->next.

---
include/linux/rculist_nulls.h | 4 ++--

1 file changed, 2 insertions(+), 2 deletions(-)
include/linux/rculist_nulls.h +1 -1
index ba4c00dd8005..89186c499dd4 100644
@@ -101,7 +101,7 @@ static inline void hlist_nulls_add_head_rcu(struct hlist_nulls_node *n,
 {
       struct hlist_nulls_node *first = h->first;
 
-       n->next = first;
+       WRITE_ONCE(n->next, first);
       WRITE_ONCE(n->pprev, &h->first);
       rcu_assign_pointer(hlist_nulls_first_rcu(h), n);
       if (!is_a_nulls(first))
@@ -137,7 +137,7 @@ static inline void hlist_nulls_add_tail_rcu(struct hlist_nulls_node *n,
               last = i;
 
Quoted 8 lines

include/linux/rculist_nulls.h static inline void hlist_nulls_add_tail_rcu(struct hlist_nulls_node *n, · line 143

Quoted 6 lines
include/linux/rculist_nulls.h +1 -1
       if (last) {
-               n->next = last->next;
+               WRITE_ONCE(n->next, last->next);
               n->pprev = &last->next;
               rcu_assign_pointer(hlist_nulls_next_rcu(last), n);
       } else {

Don't you need READ_ONCE() for the read-side accesses as well?

Like Paul said, read-side uses rcu_dereference_raw()

Quoted 4 lines

thanks,

- Joel

author
#8 lore raw

PATCH 2/2 docs/RCU: Bring back smp_wmb()

In reply to Alan Huang

The objects are allocated with SLAB_TYPESAFE_BY_RCU, and there is n->next = first within hlist_add_head_rcu() before rcu_assign_pointer(), which modifies obj->obj_node.next. There may be readers holding the reference of obj in lockless_lookup, and when updater modifies ->next, readers can see the change immediately because of SLAB_TYPESAFE_BY_RCU.

There are two memory ordering required in the insertion algorithm, we need to make sure obj->key is updated before obj->obj_node.next and obj->refcnt, atomic_set_release is not enough to provide the required memory barrier.

---
 Documentation/RCU/rculist_nulls.rst | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)
Documentation/RCU/rculist_nulls.rst +7 -2
index 21e40fcc08de..fa3729dc7e74 100644
@@ -64,7 +64,7 @@ but a version with an additional memory barrier (smp_rmb())
   {
     struct hlist_node *node, *next;
     for (pos = rcu_dereference((head)->first);
-         pos && ({ next = pos->next; smp_rmb(); prefetch(next); 1; }) &&
+         pos && ({ next = READ_ONCE(pos->next); smp_rmb(); prefetch(next); 1; }) &&
          ({ obj = hlist_entry(pos, typeof(*obj), obj_node); 1; });
          pos = rcu_dereference(next))
       if (obj->key == key)
@@ -112,7 +112,12 @@ detect the fact that it missed following items in original chain.
   obj = kmem_cache_alloc(...);
   lock_chain(); // typically a spin_lock()
   obj->key = key;
-  atomic_set_release(&obj->refcnt, 1); // key before refcnt
+  /*
+   * We need to make sure obj->key is updated before obj->obj_node.next
+   * and obj->refcnt.
+   */
+  smp_wmb();
+  atomic_set(&obj->refcnt, 1);
   hlist_add_head_rcu(&obj->obj_node, list);
   unlock_chain(); // typically a spin_unlock()
 
Signature · 1 line
2.34.1
maintainer
#9 lore raw

Re: [PATCH 2/2] docs/RCU: Bring back smp_wmb()

Quoted 21 lines · Alan Huang

The objects are allocated with SLAB_TYPESAFE_BY_RCU, and there is n->next = first within hlist_add_head_rcu() before rcu_assign_pointer(), which modifies obj->obj_node.next. There may be readers holding the reference of obj in lockless_lookup, and when updater modifies ->next, readers can see the change immediately because of SLAB_TYPESAFE_BY_RCU.

There are two memory ordering required in the insertion algorithm, we need to make sure obj->key is updated before obj->obj_node.next and obj->refcnt, atomic_set_release is not enough to provide the required memory barrier.

---
 Documentation/RCU/rculist_nulls.rst | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)
Documentation/RCU/rculist_nulls.rst +0 -0
index 21e40fcc08de..fa3729dc7e74 100644

Documentation/RCU/rculist_nulls.rst but a version with an additional memory barrier (smp_rmb()) · line 67

Quoted 5 lines
Documentation/RCU/rculist_nulls.rst +1 -1
@@ -64,7 +64,7 @@ but a version with an additional memory barrier (smp_rmb())
   {
     struct hlist_node *node, *next;
     for (pos = rcu_dereference((head)->first);
-         pos && ({ next = pos->next; smp_rmb(); prefetch(next); 1; }) &&
+         pos && ({ next = READ_ONCE(pos->next); smp_rmb(); prefetch(next); 1; }) &&

This one looks good, though the READ_ONCE() becoming rcu_dereference() would allow the smp_rmb() to be dropped, correct?

Quoted 4 lines
Documentation/RCU/rculist_nulls.rst +0 -0
          ({ obj = hlist_entry(pos, typeof(*obj), obj_node); 1; });
          pos = rcu_dereference(next))
       if (obj->key == key)

Documentation/RCU/rculist_nulls.rst detect the fact that it missed following items in original chain. · line 120

Quoted 10 lines
Documentation/RCU/rculist_nulls.rst +6 -1
@@ -112,7 +112,12 @@ detect the fact that it missed following items in original chain.
   obj = kmem_cache_alloc(...);
   lock_chain(); // typically a spin_lock()
   obj->key = key;
-  atomic_set_release(&obj->refcnt, 1); // key before refcnt
+  /*
+   * We need to make sure obj->key is updated before obj->obj_node.next
+   * and obj->refcnt.
+   */
+  smp_wmb();
+  atomic_set(&obj->refcnt, 1);

...but what is smp_wmb() doing that the combination of atomic_set_release() and hlist_add_head_rcu() was not already doing? What am I missing?

Thanx, Paul

Quoted 6 lines
Documentation/RCU/rculist_nulls.rst +0 -0
   hlist_add_head_rcu(&obj->obj_node, list);
   unlock_chain(); // typically a spin_unlock()
 
Signature · 1 line
2.34.1
author
#10 lore raw

Re: [PATCH 2/2] docs/RCU: Bring back smp_wmb()

Quoted 20 lines

2023年7月11日 03:11,Paul E. McKenney <[email protected]> 写道:

Quoted 16 lines · Alan Huang

The objects are allocated with SLAB_TYPESAFE_BY_RCU, and there is n->next = first within hlist_add_head_rcu() before rcu_assign_pointer(), which modifies obj->obj_node.next. There may be readers holding the reference of obj in lockless_lookup, and when updater modifies ->next, readers can see the change immediately because of SLAB_TYPESAFE_BY_RCU.

There are two memory ordering required in the insertion algorithm, we need to make sure obj->key is updated before obj->obj_node.next and obj->refcnt, atomic_set_release is not enough to provide the required memory barrier.

---
Documentation/RCU/rculist_nulls.rst | 9 +++++++--

1 file changed, 7 insertions(+), 2 deletions(-)
Quoted 13 lines

Documentation/RCU/rculist_nulls.rst but a version with an additional memory barrier (smp_rmb()) · line 67

Quoted 10 lines
Documentation/RCU/rculist_nulls.rst +1 -1
index 21e40fcc08de..fa3729dc7e74 100644
@@ -64,7 +64,7 @@ but a version with an additional memory barrier (smp_rmb())
  {
    struct hlist_node *node, *next;
    for (pos = rcu_dereference((head)->first);
-         pos && ({ next = pos->next; smp_rmb(); prefetch(next); 1; }) &&
+         pos && ({ next = READ_ONCE(pos->next); smp_rmb(); prefetch(next); 1; }) &&

This one looks good, though the READ_ONCE() becoming rcu_dereference() would allow the smp_rmb() to be dropped, correct?

The pattern here is:

reader updater

// pos->next is also obj->obj_node.next
READ_ONCE(pos->next); WRITE_ONCE(obj->key, key);

smp_rmb();										smp_wmb();
												// this is n->next = first; within hlist_add_head_rcu

READ_ONCE(obj->key); WRITE_ONCE(obj->obj_node.next, h->first);

The point here is that the objects are allocated with SLAB_TYPESAFE_BY_RCU, and there is

	 n->next = first;

within hlist_add_head_rcu, the modification is visible to readers immediately (before the invocation of rcu_assign_pointer)

Therefore, the smp_rmb() is necessary to ensure that we won’t get the new value of ->next and the old ->key. (If we get the new ->next and old ->key, we can not detect movement of the object.)

But in this patch, I forgot to add READ_ONCE to obj->key, will send v2.

Quoted 10 lines
Quoted 10 lines
Documentation/RCU/rculist_nulls.rst +1 -1
         ({ obj = hlist_entry(pos, typeof(*obj), obj_node); 1; });
         pos = rcu_dereference(next))
      if (obj->key == key)
@@ -112,7 +112,12 @@ detect the fact that it missed following items in original chain.
  obj = kmem_cache_alloc(...);
  lock_chain(); // typically a spin_lock()
  obj->key = key;
-  atomic_set_release(&obj->refcnt, 1); // key before refcnt
+  /*
Quoted 8 lines

Documentation/RCU/rculist_nulls.rst detect the fact that it missed following items in original chain. · line 120

Quoted 5 lines
Documentation/RCU/rculist_nulls.rst +5 -0
+   * We need to make sure obj->key is updated before obj->obj_node.next
+   * and obj->refcnt.
+   */
+  smp_wmb();
+  atomic_set(&obj->refcnt, 1);

...but what is smp_wmb() doing that the combination of atomic_set_release() and hlist_add_head_rcu() was not already doing? What am I missing?

Like above.

Quoted 8 lines

Thanx, Paul

Quoted 5 lines
Documentation/RCU/rculist_nulls.rst +0 -0
  hlist_add_head_rcu(&obj->obj_node, list);
  unlock_chain(); // typically a spin_unlock()
 
Signature · 1 line
2.34.1