Changes from v3
(https://lore.kernel.org/rcu/[email protected]/)
- Fix Paul's name on 'Suggested-by:' tag
- Use 'atomic_t' for refcnt field of 'struct object'
Changes from v2
(https://lore.kernel.org/rcu/[email protected]/)
- Drop first two patches that merged to Paul's tree
- Add definition of 'obj' (Paul E. McKenney)
- Fix more wrong hlist_[nulls]_head field name mentions
Changes from v1
(https://lore.kernel.org/rcu/[email protected]/)
- Add Reviewed-by tags from Joel Fernandes for first three patches
- Fix the text for wrong extra _release()
---
Fix minor problems in example code snippets and the text of
rculist_nulls.rst file.
SeongJae Park (3):
Docs/RCU/rculist_nulls: Specify type of the object in examples
Docs/RCU/rculist_nulls: Fix hlist_[nulls]_head field names of 'obj'
Docs/RCU/rculist_nulls: Fix text about atomic_set_release()
Documentation/RCU/rculist_nulls.rst | 28 +++++++++++++++++++++-------
1 file changed, 21 insertions(+), 7 deletions(-)
--
2.25.1
The type of 'obj' in example code of rculist_nulls.rst is implicit.
Provide the specific type of it before the example code.
Suggested-by: Paul E. McKenney <[email protected]>
Link: https://lore.kernel.org/rcu/43943609-f80c-4b6a-9844-994eef800757@paulmck-laptop/
Signed-off-by: SeongJae Park <[email protected]>
---
Documentation/RCU/rculist_nulls.rst | 14 +++++++++++++-
1 file changed, 13 insertions(+), 1 deletion(-)
diff --git a/Documentation/RCU/rculist_nulls.rst b/Documentation/RCU/rculist_nulls.rst
index 94a8bfe9f560..a6827cc31791 100644
--- a/Documentation/RCU/rculist_nulls.rst
+++ b/Documentation/RCU/rculist_nulls.rst
@@ -18,7 +18,16 @@ to solve following problem.
Without 'nulls', a typical RCU linked list managing objects which are
allocated with SLAB_TYPESAFE_BY_RCU kmem_cache can use the following
-algorithms:
+algorithms. Following examples assume 'obj' is a pointer to such
+objects, which is having below type.
+
+::
+
+ struct object {
+ struct hlist_node obj_node;
+ atomic_t refcnt;
+ unsigned int key;
+ };
1) Lookup algorithm
-------------------
@@ -142,6 +151,9 @@ the beginning. If the object was moved to the same chain,
then the reader doesn't care: It might occasionally
scan the list again without harm.
+Note that using hlist_nulls means the type of 'obj_node' field of
+'struct object' becomes 'struct hlist_nulls_node'.
+
1) lookup algorithm
-------------------
--
2.25.1
The example code snippets on rculist_nulls.rst are assuming 'obj' to
have the 'hlist_head' or 'hlist_nulls_head' field named 'obj_node', but
a sentence and some code snippets are wrongly calling
'obj->obj_node.next' as 'obj->obj_next', or 'obj->obj_node' as 'member'.
Fix it.
Signed-off-by: SeongJae Park <[email protected]>
---
Documentation/RCU/rculist_nulls.rst | 8 ++++----
1 file changed, 4 insertions(+), 4 deletions(-)
diff --git a/Documentation/RCU/rculist_nulls.rst b/Documentation/RCU/rculist_nulls.rst
index a6827cc31791..4afa11f2c906 100644
--- a/Documentation/RCU/rculist_nulls.rst
+++ b/Documentation/RCU/rculist_nulls.rst
@@ -63,7 +63,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; }) &&
- ({ obj = hlist_entry(pos, typeof(*obj), member); 1; });
+ ({ obj = hlist_entry(pos, typeof(*obj), obj_node); 1; });
pos = rcu_dereference(next))
if (obj->key == key)
return obj;
@@ -75,7 +75,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; }) &&
- ({ obj = hlist_entry(pos, typeof(*obj), member); 1; });
+ ({ obj = hlist_entry(pos, typeof(*obj), obj_node); 1; });
pos = rcu_dereference(pos->next))
if (obj->key == key)
return obj;
@@ -95,7 +95,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
@@ -163,7 +163,7 @@ Note that using hlist_nulls means the type of 'obj_node' field of
head = &table[slot];
begin:
rcu_read_lock();
- hlist_nulls_for_each_entry_rcu(obj, node, head, member) {
+ hlist_nulls_for_each_entry_rcu(obj, node, head, obj_node) {
if (obj->key == key) {
if (!try_get_ref(obj)) { // might fail for free objects
rcu_read_unlock();
--
2.25.1
The document says we can avoid extra _release() in insert function when
hlist_nulls is used, but that's not true[1]. Drop it.
[1] https://lore.kernel.org/rcu/46440869-644a-4982-b790-b71b43976c66@paulmck-laptop/
Signed-off-by: SeongJae Park <[email protected]>
---
Documentation/RCU/rculist_nulls.rst | 6 ++++--
1 file changed, 4 insertions(+), 2 deletions(-)
diff --git a/Documentation/RCU/rculist_nulls.rst b/Documentation/RCU/rculist_nulls.rst
index 4afa11f2c906..660cc3f0f1e5 100644
--- a/Documentation/RCU/rculist_nulls.rst
+++ b/Documentation/RCU/rculist_nulls.rst
@@ -138,8 +138,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
@@ -194,6 +193,9 @@ Note that using hlist_nulls means the type of 'obj_node' field of
2) Insert algorithm
-------------------
+Same to the above one, but uses hlist_nulls_add_head_rcu() instead of
+hlist_add_head_rcu().
+
::
/*
--
2.25.1
On Fri, Jun 16, 2023 at 11:36:23PM +0000, SeongJae Park wrote:
> Changes from v3
> (https://lore.kernel.org/rcu/[email protected]/)
> - Fix Paul's name on 'Suggested-by:' tag
> - Use 'atomic_t' for refcnt field of 'struct object'
>
> Changes from v2
> (https://lore.kernel.org/rcu/[email protected]/)
> - Drop first two patches that merged to Paul's tree
> - Add definition of 'obj' (Paul E. McKenney)
> - Fix more wrong hlist_[nulls]_head field name mentions
>
> Changes from v1
> (https://lore.kernel.org/rcu/[email protected]/)
> - Add Reviewed-by tags from Joel Fernandes for first three patches
> - Fix the text for wrong extra _release()
>
> ---
>
> Fix minor problems in example code snippets and the text of
> rculist_nulls.rst file.
I am replacing the earlier versions with this version, thank you!!!
Thanx, Paul
> SeongJae Park (3):
> Docs/RCU/rculist_nulls: Specify type of the object in examples
> Docs/RCU/rculist_nulls: Fix hlist_[nulls]_head field names of 'obj'
> Docs/RCU/rculist_nulls: Fix text about atomic_set_release()
>
> Documentation/RCU/rculist_nulls.rst | 28 +++++++++++++++++++++-------
> 1 file changed, 21 insertions(+), 7 deletions(-)
>
> --
> 2.25.1
>