Skip to contentSkip to conversation

Docs/RCU/rculist_nulls: Minor fixups

PATCH Superseded SeongJae Park 4 participants 12 messages May 18, 2023 – Jun 10, 2023

Subsystems (2)

v1 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

cover Docs/RCU/rculist_nulls: Minor fixups

This patchset fixes minor problems in example code snippets of rculist_nulls.rst file.

SeongJae Park (4):
Docs/RCU/rculist_nulls: Fix trivial coding style Docs/RCU/rculist_nulls: Assign 'obj' before use from the examples Docs/RCU/rculist_nulls: Fix hlist_head field name of 'obj' Docs/RCU/rculist_nulls: Drop unnecessary '_release' in insert function

 Documentation/RCU/rculist_nulls.rst | 14 +++++++-------
 1 file changed, 7 insertions(+), 7 deletions(-)
Signature · 1 line
2.25.1
#1 lore raw

PATCH 1/4 Docs/RCU/rculist_nulls: Fix trivial coding style

Lookup example of non-hlist_nulls management is missing a semicolon, and having inconsistent indentation (one line is using single space indentation while others are using two spaces indentation). Fix the trivial issues.

---
 Documentation/RCU/rculist_nulls.rst | 6 +++---
 1 file changed, 3 insertions(+), 3 deletions(-)
Documentation/RCU/rculist_nulls.rst +3 -3
index 9a734bf54b76..253ecd869fc2 100644
@@ -26,7 +26,7 @@ algorithms:
 ::
 
   begin:
-  rcu_read_lock()
+  rcu_read_lock();
   obj = lockless_lookup(key);
   if (obj) {
     if (!try_get_ref(obj)) // might fail for free objects
@@ -68,8 +68,8 @@ And note the traditional hlist_for_each_entry_rcu() misses this smp_rmb()::
        pos && ({ prefetch(pos->next); 1; }) &&
        ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; });
        pos = rcu_dereference(pos->next))
-   if (obj->key == key)
-     return obj;
+    if (obj->key == key)
+      return obj;
   return NULL;
 
 Quoting Corey Minyard::
Signature · 1 line
2.25.1
#2 lore raw

PATCH 2/4 Docs/RCU/rculist_nulls: Assign 'obj' before use from the examples

In reply to SeongJae Park

Lookup example code snippets in rculist_nulls.rst are using 'obj' without assignment. Fix the code to assign it properly.

---
 Documentation/RCU/rculist_nulls.rst | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)
Documentation/RCU/rculist_nulls.rst +2 -2
index 253ecd869fc2..94a8bfe9f560 100644
@@ -54,7 +54,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; }) &&
-         ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; });
+         ({ obj = hlist_entry(pos, typeof(*obj), member); 1; });
          pos = rcu_dereference(next))
       if (obj->key == key)
         return obj;
@@ -66,7 +66,7 @@ And note the traditional hlist_for_each_entry_rcu() misses this smp_rmb()::
   struct hlist_node *node;
   for (pos = rcu_dereference((head)->first);
        pos && ({ prefetch(pos->next); 1; }) &&
-       ({ tpos = hlist_entry(pos, typeof(*tpos), member); 1; });
+       ({ obj = hlist_entry(pos, typeof(*obj), member); 1; });
        pos = rcu_dereference(pos->next))
     if (obj->key == key)
       return obj;
Signature · 1 line
2.25.1
#4 lore raw

PATCH 4/4 Docs/RCU/rculist_nulls: Drop unnecessary '_release' in insert function

In reply to SeongJae Park

The document says we can avoid extra smp_rmb() in lockless_lookup() and extra _release() in insert function when hlist_nulls is used. However, the example code snippet for the insert function is still using the extra _release(). Drop it.

---
 Documentation/RCU/rculist_nulls.rst | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
Documentation/RCU/rculist_nulls.rst +1 -1
index 5cd6f3f8810f..463270273d89 100644
@@ -191,7 +191,7 @@ scan the list again without harm.
   obj = kmem_cache_alloc(cachep);
   lock_chain(); // typically a spin_lock()
   obj->key = key;
-  atomic_set_release(&obj->refcnt, 1); // key before refcnt
+  atomic_set(&obj->refcnt, 1);
   /*
    * insert obj in RCU way (readers might be traversing chain)
    */
Signature · 1 line
2.25.1
#3 lore raw

PATCH 3/4 Docs/RCU/rculist_nulls: Fix hlist_head field name of 'obj'

In reply to SeongJae Park

The example code snippets on rculist_nulls.rst are assuming 'obj' to have the 'hlist_head' field named 'obj_node', but a sentence is wrongly mentioning 'obj->obj_node.next' as 'obj->obj_next'. Fix it.

---
 Documentation/RCU/rculist_nulls.rst | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
Documentation/RCU/rculist_nulls.rst +1 -1
index 94a8bfe9f560..5cd6f3f8810f 100644
@@ -86,7 +86,7 @@ Quoting Corey Minyard::
 2) Insertion algorithm
 ----------------------
 
-We need to make sure a reader cannot read the new 'obj->obj_next' value
+We need to make sure a reader cannot read the new 'obj->obj_node.next' value
 and previous value of 'obj->key'. Otherwise, an item could be deleted
 from a chain, and inserted into another chain. If new chain was empty
 before the move, 'next' pointer is NULL, and lockless reader can not
Signature · 1 line
2.25.1
Reviewed-by on v1 4/4
#5 lore raw

Re: [PATCH 4/4] Docs/RCU/rculist_nulls: Drop unnecessary '_release' in insert function

In reply to SeongJae Park
Quoted 16 lines · SeongJae Park

The document says we can avoid extra smp_rmb() in lockless_lookup() and extra _release() in insert function when hlist_nulls is used. However, the example code snippet for the insert function is still using the extra _release(). Drop it.

---
 Documentation/RCU/rculist_nulls.rst | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
Documentation/RCU/rculist_nulls.rst +0 -0
index 5cd6f3f8810f..463270273d89 100644

Documentation/RCU/rculist_nulls.rst scan the list again without harm. · line 197

Quoted 8 lines
Documentation/RCU/rculist_nulls.rst +1 -1
@@ -191,7 +191,7 @@ scan the list again without harm.
   obj = kmem_cache_alloc(cachep);
   lock_chain(); // typically a spin_lock()
   obj->key = key;
-  atomic_set_release(&obj->refcnt, 1); // key before refcnt
+  atomic_set(&obj->refcnt, 1);
   /*
    * insert obj in RCU way (readers might be traversing chain)
    */

If write to ->refcnt of 1 is reordered with setting of ->key, what prevents the 'lookup algorithm' from doing a key match (obj->key == key) before the refcount has been initialized?

Are we sure the reordering mentioned in the document is the same as the reordering prevented by the atomic_set_release()?

For the other 3 patches, feel free to add:

thanks,

- Joel

#6 lore raw

Re: [PATCH 4/4] Docs/RCU/rculist_nulls: Drop unnecessary '_release' in insert function

Quoted 30 lines · On Fri, 19 May 2023 14:52:50 -0400 Joel Fernandes <[email protected]>…
Quoted 16 lines · SeongJae Park

The document says we can avoid extra smp_rmb() in lockless_lookup() and extra _release() in insert function when hlist_nulls is used. However, the example code snippet for the insert function is still using the extra _release(). Drop it.

---
 Documentation/RCU/rculist_nulls.rst | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
Documentation/RCU/rculist_nulls.rst +0 -0
index 5cd6f3f8810f..463270273d89 100644

Documentation/RCU/rculist_nulls.rst scan the list again without harm. · line 197

Quoted 8 lines
Documentation/RCU/rculist_nulls.rst +1 -1
@@ -191,7 +191,7 @@ scan the list again without harm.
   obj = kmem_cache_alloc(cachep);
   lock_chain(); // typically a spin_lock()
   obj->key = key;
-  atomic_set_release(&obj->refcnt, 1); // key before refcnt
+  atomic_set(&obj->refcnt, 1);
   /*
    * insert obj in RCU way (readers might be traversing chain)
    */

If write to ->refcnt of 1 is reordered with setting of ->key, what prevents the 'lookup algorithm' from doing a key match (obj->key == key) before the refcount has been initialized?

Quoted 2 lines

Are we sure the reordering mentioned in the document is the same as the reordering prevented by the atomic_set_release()?

Paul, may I ask your opinion?

Thanks,
SJ

Quoted 7 lines

For the other 3 patches, feel free to add:

thanks,

- Joel

maintainer
#7 lore raw

Re: [PATCH 4/4] Docs/RCU/rculist_nulls: Drop unnecessary '_release' in insert function

Quoted 32 lines · SeongJae Park
Quoted 30 lines · On Fri, 19 May 2023 14:52:50 -0400 Joel Fernandes <[email protected]>…
Quoted 16 lines · SeongJae Park

The document says we can avoid extra smp_rmb() in lockless_lookup() and extra _release() in insert function when hlist_nulls is used. However, the example code snippet for the insert function is still using the extra _release(). Drop it.

---
 Documentation/RCU/rculist_nulls.rst | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
Documentation/RCU/rculist_nulls.rst +0 -0
index 5cd6f3f8810f..463270273d89 100644

Documentation/RCU/rculist_nulls.rst scan the list again without harm. · line 197

Quoted 8 lines
Documentation/RCU/rculist_nulls.rst +1 -1
@@ -191,7 +191,7 @@ scan the list again without harm.
   obj = kmem_cache_alloc(cachep);
   lock_chain(); // typically a spin_lock()
   obj->key = key;
-  atomic_set_release(&obj->refcnt, 1); // key before refcnt
+  atomic_set(&obj->refcnt, 1);
   /*
    * insert obj in RCU way (readers might be traversing chain)
    */

If write to ->refcnt of 1 is reordered with setting of ->key, what prevents the 'lookup algorithm' from doing a key match (obj->key == key) before the refcount has been initialized?

Quoted 4 lines
Quoted 2 lines

Are we sure the reordering mentioned in the document is the same as the reordering prevented by the atomic_set_release()?

Paul, may I ask your opinion?

The next line of code is this:

	hlist_nulls_add_head_rcu(&obj->obj_node, list);

If I understand the code correctly, obj (and thus *obj) are not visible to readers before the hlist_nulls_add_head_rcu(). And hlist_nulls_add_head_rcu() uses rcu_assign_pointer() to ensure that initialization (including both ->key and ->refcnt) is ordered before list insertion.

Except that this memory is being allocated from a slab cache that was created with SLAB_TYPESAFE_BY_RCU. This means that there can be readers who gained a reference before this object was freed, and who still hold their references.

Unfortunately, the implementation of try_get_ref() is not shown. However, if ->refcnt is non-zero, this can succeed, and if it succeeds, we need the subsequent check of obj->key with key in the lookup algorithm to be stable. For this check to be stable, try_get_ref() needs to use an atomic operation with at least acquire semantics (kref_get_unless_zero() would work), and this must pair with something in the initialization.

So I don't see how it is safe to weaken that atomic_set_release() to atomic_set(), even on x86.

Or am I missing something subtle here?

Thanx, Paul

Quoted 10 lines

Thanks,
SJ

Quoted 7 lines

For the other 3 patches, feel free to add:

thanks,

- Joel

#8 lore raw

Re: [PATCH 4/4] Docs/RCU/rculist_nulls: Drop unnecessary '_release' in insert function

Quoted 60 lines · On Fri, 9 Jun 2023 16:42:59 -0700 "Paul E. McKenney" <[email protected]> wrote:
Quoted 32 lines · SeongJae Park
Quoted 30 lines · On Fri, 19 May 2023 14:52:50 -0400 Joel Fernandes <[email protected]>…
Quoted 16 lines · SeongJae Park

The document says we can avoid extra smp_rmb() in lockless_lookup() and extra _release() in insert function when hlist_nulls is used. However, the example code snippet for the insert function is still using the extra _release(). Drop it.

---
 Documentation/RCU/rculist_nulls.rst | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
Documentation/RCU/rculist_nulls.rst +0 -0
index 5cd6f3f8810f..463270273d89 100644

Documentation/RCU/rculist_nulls.rst scan the list again without harm. · line 197

Quoted 8 lines
Documentation/RCU/rculist_nulls.rst +1 -1
@@ -191,7 +191,7 @@ scan the list again without harm.
   obj = kmem_cache_alloc(cachep);
   lock_chain(); // typically a spin_lock()
   obj->key = key;
-  atomic_set_release(&obj->refcnt, 1); // key before refcnt
+  atomic_set(&obj->refcnt, 1);
   /*
    * insert obj in RCU way (readers might be traversing chain)
    */

If write to ->refcnt of 1 is reordered with setting of ->key, what prevents the 'lookup algorithm' from doing a key match (obj->key == key) before the refcount has been initialized?

Quoted 4 lines
Quoted 2 lines

Are we sure the reordering mentioned in the document is the same as the reordering prevented by the atomic_set_release()?

Paul, may I ask your opinion?

The next line of code is this:

	hlist_nulls_add_head_rcu(&obj->obj_node, list);

If I understand the code correctly, obj (and thus *obj) are not visible to readers before the hlist_nulls_add_head_rcu(). And hlist_nulls_add_head_rcu() uses rcu_assign_pointer() to ensure that initialization (including both ->key and ->refcnt) is ordered before list insertion.

Except that this memory is being allocated from a slab cache that was created with SLAB_TYPESAFE_BY_RCU. This means that there can be readers who gained a reference before this object was freed, and who still hold their references.

Unfortunately, the implementation of try_get_ref() is not shown. However, if ->refcnt is non-zero, this can succeed, and if it succeeds, we need the subsequent check of obj->key with key in the lookup algorithm to be stable. For this check to be stable, try_get_ref() needs to use an atomic operation with at least acquire semantics (kref_get_unless_zero() would work), and this must pair with something in the initialization.

Quoted 2 lines

So I don't see how it is safe to weaken that atomic_set_release() to atomic_set(), even on x86.

Thank you for the nice explanation, and I agree.

Quoted 2 lines

Or am I missing something subtle here?

I found the text is saying extra _release() in insert function is not needed[1], and I thought it means the atomic_set_release(). Am I misreading it? If not, would it be better to fix the text, for example, like below?

```
--- a/Documentation/RCU/rculist_nulls.rst
+++ b/Documentation/RCU/rculist_nulls.rst
@@ -129,8 +129,7 @@ very very fast (before the end of RCU grace period)
 Avoiding extra smp_rmb()
 ========================

-With hlist_nulls we can avoid extra smp_rmb() in lockless_lookup()
-and extra _release() in insert function.
+With hlist_nulls we can avoid extra smp_rmb() in lockless_lookup().

 For example, if we choose to store the slot number as the 'nulls'
 end-of-list marker for each slot of the hash table, we can detect
@@ -182,6 +181,9 @@ scan the list again without harm.
 2) Insert algorithm
 -------------------

+Same to the above one, but uses hlist_nulls_add_head_rcu() instead of
+hlist_add_head_rcu().
+
 ::

   /*
@@ -191,7 +193,7 @@ scan the list again without harm.
   obj = kmem_cache_alloc(cachep);
   lock_chain(); // typically a spin_lock()
   obj->key = key;
-  atomic_set_release(&obj->refcnt, 1); // key before refcnt
+  atomic_set(&obj->refcnt, 1);
   /*
    * insert obj in RCU way (readers might be traversing chain)
    */
```

[1] https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/Documentation/RCU/rculist_nulls.rst#n133

Thanks,
SJ

Quoted 13 lines

Thanx, Paul

Quoted 10 lines

Thanks,
SJ

Quoted 7 lines

For the other 3 patches, feel free to add:

thanks,

- Joel

#10 lore raw

Re: [PATCH 4/4] Docs/RCU/rculist_nulls: Drop unnecessary '_release' in insert function

In reply to Paul E. McKenney

Hi Paul,

Quoted 62 lines

2023年6月10日 07:42,Paul E. McKenney <[email protected]> 写道:

Quoted 32 lines · SeongJae Park
Quoted 30 lines · On Fri, 19 May 2023 14:52:50 -0400 Joel Fernandes <[email protected]>…
Quoted 16 lines · SeongJae Park

The document says we can avoid extra smp_rmb() in lockless_lookup() and extra _release() in insert function when hlist_nulls is used. However, the example code snippet for the insert function is still using the extra _release(). Drop it.

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

1 file changed, 1 insertion(+), 1 deletion(-)
Documentation/RCU/rculist_nulls.rst +0 -0
index 5cd6f3f8810f..463270273d89 100644

Documentation/RCU/rculist_nulls.rst scan the list again without harm. · line 197

Quoted 8 lines
Documentation/RCU/rculist_nulls.rst +1 -1
@@ -191,7 +191,7 @@ scan the list again without harm.
  obj = kmem_cache_alloc(cachep);
  lock_chain(); // typically a spin_lock()
  obj->key = key;
-  atomic_set_release(&obj->refcnt, 1); // key before refcnt
+  atomic_set(&obj->refcnt, 1);
  /*
   * insert obj in RCU way (readers might be traversing chain)
   */

If write to ->refcnt of 1 is reordered with setting of ->key, what prevents the 'lookup algorithm' from doing a key match (obj->key == key) before the refcount has been initialized?

Quoted 4 lines
Quoted 2 lines

Are we sure the reordering mentioned in the document is the same as the reordering prevented by the atomic_set_release()?

Paul, may I ask your opinion?

The next line of code is this:

hlist_nulls_add_head_rcu(&obj->obj_node, list);

If I understand the code correctly, obj (and thus *obj) are not visible to readers before the hlist_nulls_add_head_rcu(). And hlist_nulls_add_head_rcu() uses rcu_assign_pointer() to ensure that initialization (including both ->key and ->refcnt) is ordered before list insertion.

Except that this memory is being allocated from a slab cache that was created with SLAB_TYPESAFE_BY_RCU. This means that there can be readers who gained a reference before this object was freed, and who still hold their references.

Unfortunately, the implementation of try_get_ref() is not shown. However, if ->refcnt is non-zero, this can succeed, and if it succeeds, we need the subsequent check of obj->key with key in the lookup algorithm to be stable. For this check to be stable, try_get_ref() needs to use an atomic operation with at least acquire semantics (kref_get_unless_zero() would work), and this must pair with something in the initialization.

Quoted 2 lines

So I don't see how it is safe to weaken that atomic_set_release() to atomic_set(), even on x86.

I totally agree, but only in the case of using hlist_nulls.

That means, atomic_set_release() is not enough in the case without using hlist_nulls, we must ensure that storing to obj->next (in hlist_add_head_rcu) is ordered before storing to obj->key. Otherwise, we can get the new ‘next' and the old ‘key' in which case we can’t detect an object movement(from one chain to another).

So, I’m afraid that the atomic_set_release() in insertion algorithm without using hlist_nulls should change back to:

	smp_wmb();
	atomic_set(&obj->refcnt, 1);

Thanks,
Alan

Quoted 15 lines

Or am I missing something subtle here?

Thanx, Paul

Quoted 10 lines

Thanks,
SJ

Quoted 7 lines

For the other 3 patches, feel free to add:

thanks,

- Joel

#9 lore raw

Re: [PATCH 4/4] Docs/RCU/rculist_nulls: Drop unnecessary '_release' in insert function

In reply to SeongJae Park

Hi SJ,

Quoted 67 lines

2023年6月10日 08:20,SeongJae Park <[email protected]> 写道:

Quoted 60 lines · On Fri, 9 Jun 2023 16:42:59 -0700 "Paul E. McKenney" <[email protected]> wrote:
Quoted 32 lines · SeongJae Park
Quoted 30 lines · On Fri, 19 May 2023 14:52:50 -0400 Joel Fernandes <[email protected]>…
Quoted 16 lines · SeongJae Park

The document says we can avoid extra smp_rmb() in lockless_lookup() and extra _release() in insert function when hlist_nulls is used. However, the example code snippet for the insert function is still using the extra _release(). Drop it.

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

1 file changed, 1 insertion(+), 1 deletion(-)
Documentation/RCU/rculist_nulls.rst +0 -0
index 5cd6f3f8810f..463270273d89 100644

Documentation/RCU/rculist_nulls.rst scan the list again without harm. · line 197

Quoted 8 lines
Documentation/RCU/rculist_nulls.rst +1 -1
@@ -191,7 +191,7 @@ scan the list again without harm.
  obj = kmem_cache_alloc(cachep);
  lock_chain(); // typically a spin_lock()
  obj->key = key;
-  atomic_set_release(&obj->refcnt, 1); // key before refcnt
+  atomic_set(&obj->refcnt, 1);
  /*
   * insert obj in RCU way (readers might be traversing chain)
   */

If write to ->refcnt of 1 is reordered with setting of ->key, what prevents the 'lookup algorithm' from doing a key match (obj->key == key) before the refcount has been initialized?

Quoted 4 lines
Quoted 2 lines

Are we sure the reordering mentioned in the document is the same as the reordering prevented by the atomic_set_release()?

Paul, may I ask your opinion?

The next line of code is this:

hlist_nulls_add_head_rcu(&obj->obj_node, list);

If I understand the code correctly, obj (and thus *obj) are not visible to readers before the hlist_nulls_add_head_rcu(). And hlist_nulls_add_head_rcu() uses rcu_assign_pointer() to ensure that initialization (including both ->key and ->refcnt) is ordered before list insertion.

Except that this memory is being allocated from a slab cache that was created with SLAB_TYPESAFE_BY_RCU. This means that there can be readers who gained a reference before this object was freed, and who still hold their references.

Unfortunately, the implementation of try_get_ref() is not shown. However, if ->refcnt is non-zero, this can succeed, and if it succeeds, we need the subsequent check of obj->key with key in the lookup algorithm to be stable. For this check to be stable, try_get_ref() needs to use an atomic operation with at least acquire semantics (kref_get_unless_zero() would work), and this must pair with something in the initialization.

Quoted 2 lines

So I don't see how it is safe to weaken that atomic_set_release() to atomic_set(), even on x86.

Quoted 8 lines

Thank you for the nice explanation, and I agree.

Quoted 2 lines

Or am I missing something subtle here?

I found the text is saying extra _release() in insert function is not needed[1], and I thought it means the atomic_set_release(). Am I misreading it? If not, would it be better to fix the text, for example, like below?

The original text is:

“With hlist_nulls we can avoid extra smp_rmb() in lockless_lookup()
and extra smp_wmb() in insert function.”

We can avoid the extra smp_wmb(), but the _release is required,

As Paul said,

Quoted 4 lines
Quoted 4 lines

Except that this memory is being allocated from a slab cache that was created with SLAB_TYPESAFE_BY_RCU. This means that there can be readers who gained a reference before this object was freed, and who still hold their references.

Without the _release, we can get the old ‘key’ after the invocation of try_get_ref (although try_get_ref noticed the effect of atomic_set).

Thanks,
Alan

Quoted 54 lines

```

Documentation/RCU/rculist_nulls.rst +0 -0
@@ -129,8 +129,7 @@ very very fast (before the end of RCU grace period)
 Avoiding extra smp_rmb()

========================

Documentation/RCU/rculist_nulls.rst +1 -2
-With hlist_nulls we can avoid extra smp_rmb() in lockless_lookup()
-and extra _release() in insert function.
+With hlist_nulls we can avoid extra smp_rmb() in lockless_lookup().

For example, if we choose to store the slot number as the 'nulls' end-of-list marker for each slot of the hash table, we can detect

Documentation/RCU/rculist_nulls.rst +0 -0
@@ -182,6 +181,9 @@ scan the list again without harm.

2) Insert algorithm
-------------------

Documentation/RCU/rculist_nulls.rst +3 -0
+Same to the above one, but uses hlist_nulls_add_head_rcu() instead of
+hlist_add_head_rcu().
+

::

/*

Documentation/RCU/rculist_nulls.rst +1 -1
@@ -191,7 +193,7 @@ scan the list again without harm.
  obj = kmem_cache_alloc(cachep);
  lock_chain(); // typically a spin_lock()
  obj->key = key;
-  atomic_set_release(&obj->refcnt, 1); // key before refcnt
+  atomic_set(&obj->refcnt, 1);
  /*
   * insert obj in RCU way (readers might be traversing chain)
   */

```

[1] https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/Documentation/RCU/rculist_nulls.rst#n133

Thanks,
SJ

Quoted 13 lines

Thanx, Paul

Quoted 10 lines

Thanks,
SJ

Quoted 7 lines

For the other 3 patches, feel free to add:

thanks,

- Joel

#11 lore raw

Re: [PATCH 4/4] Docs/RCU/rculist_nulls: Drop unnecessary '_release' in insert function

In reply to Alan Huang
Quoted 67 lines

2023年6月10日 13:37,Alan Huang <[email protected]> 写道:

Hi Paul,

Quoted 62 lines

2023年6月10日 07:42,Paul E. McKenney <[email protected]> 写道:

Quoted 32 lines · SeongJae Park
Quoted 30 lines · On Fri, 19 May 2023 14:52:50 -0400 Joel Fernandes <[email protected]>…
Quoted 16 lines · SeongJae Park

The document says we can avoid extra smp_rmb() in lockless_lookup() and extra _release() in insert function when hlist_nulls is used. However, the example code snippet for the insert function is still using the extra _release(). Drop it.

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

1 file changed, 1 insertion(+), 1 deletion(-)
Documentation/RCU/rculist_nulls.rst +0 -0
index 5cd6f3f8810f..463270273d89 100644

Documentation/RCU/rculist_nulls.rst scan the list again without harm. · line 197

Quoted 8 lines
Documentation/RCU/rculist_nulls.rst +1 -1
@@ -191,7 +191,7 @@ scan the list again without harm.
 obj = kmem_cache_alloc(cachep);
 lock_chain(); // typically a spin_lock()
 obj->key = key;
-  atomic_set_release(&obj->refcnt, 1); // key before refcnt
+  atomic_set(&obj->refcnt, 1);
 /*
  * insert obj in RCU way (readers might be traversing chain)
  */

If write to ->refcnt of 1 is reordered with setting of ->key, what prevents the 'lookup algorithm' from doing a key match (obj->key == key) before the refcount has been initialized?

Quoted 4 lines
Quoted 2 lines

Are we sure the reordering mentioned in the document is the same as the reordering prevented by the atomic_set_release()?

Paul, may I ask your opinion?

The next line of code is this:

hlist_nulls_add_head_rcu(&obj->obj_node, list);

If I understand the code correctly, obj (and thus *obj) are not visible to readers before the hlist_nulls_add_head_rcu(). And hlist_nulls_add_head_rcu() uses rcu_assign_pointer() to ensure that initialization (including both ->key and ->refcnt) is ordered before list insertion.

Except that this memory is being allocated from a slab cache that was created with SLAB_TYPESAFE_BY_RCU. This means that there can be readers who gained a reference before this object was freed, and who still hold their references.

Unfortunately, the implementation of try_get_ref() is not shown. However, if ->refcnt is non-zero, this can succeed, and if it succeeds, we need the subsequent check of obj->key with key in the lookup algorithm to be stable. For this check to be stable, try_get_ref() needs to use an atomic operation with at least acquire semantics (kref_get_unless_zero() would work), and this must pair with something in the initialization.

Quoted 7 lines
Quoted 2 lines

So I don't see how it is safe to weaken that atomic_set_release() to atomic_set(), even on x86.

I totally agree, but only in the case of using hlist_nulls.

That means, atomic_set_release() is not enough in the case without using hlist_nulls, we must ensure that storing to obj->next (in hlist_add_head_rcu) is ordered before storing

Typo: not before, but after.

Quoted 27 lines

to obj->key. Otherwise, we can get the new ‘next' and the old ‘key' in which case we can’t detect an object movement(from one chain to another).

So, I’m afraid that the atomic_set_release() in insertion algorithm without using hlist_nulls should change back to:

smp_wmb();
atomic_set(&obj->refcnt, 1);

Thanks,
Alan

Quoted 15 lines

Or am I missing something subtle here?

Thanx, Paul

Quoted 10 lines

Thanks,
SJ

Quoted 7 lines

For the other 3 patches, feel free to add:

thanks,

- Joel