* [PATCH 0/4] Docs/RCU/rculist_nulls: Minor fixups
@ 2023-05-18 22:40 SeongJae Park
2023-05-18 22:40 ` [PATCH 1/4] Docs/RCU/rculist_nulls: Fix trivial coding style SeongJae Park
` (3 more replies)
0 siblings, 4 replies; 12+ messages in thread
From: SeongJae Park @ 2023-05-18 22:40 UTC (permalink / raw)
To: paulmck; +Cc: SeongJae Park, joel, corbet, rcu, linux-doc, linux-kernel
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(-)
--
2.25.1
^ permalink raw reply [flat|nested] 12+ messages in thread
* [PATCH 1/4] Docs/RCU/rculist_nulls: Fix trivial coding style
2023-05-18 22:40 [PATCH 0/4] Docs/RCU/rculist_nulls: Minor fixups SeongJae Park
@ 2023-05-18 22:40 ` SeongJae Park
2023-05-18 22:40 ` [PATCH 2/4] Docs/RCU/rculist_nulls: Assign 'obj' before use from the examples SeongJae Park
` (2 subsequent siblings)
3 siblings, 0 replies; 12+ messages in thread
From: SeongJae Park @ 2023-05-18 22:40 UTC (permalink / raw)
To: paulmck; +Cc: SeongJae Park, joel, corbet, rcu, linux-doc, linux-kernel
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.
Signed-off-by: SeongJae Park <sj@kernel.org>
---
Documentation/RCU/rculist_nulls.rst | 6 +++---
1 file changed, 3 insertions(+), 3 deletions(-)
diff --git a/Documentation/RCU/rculist_nulls.rst b/Documentation/RCU/rculist_nulls.rst
index 9a734bf54b76..253ecd869fc2 100644
--- a/Documentation/RCU/rculist_nulls.rst
+++ b/Documentation/RCU/rculist_nulls.rst
@@ -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::
--
2.25.1
^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH 2/4] Docs/RCU/rculist_nulls: Assign 'obj' before use from the examples
2023-05-18 22:40 [PATCH 0/4] Docs/RCU/rculist_nulls: Minor fixups SeongJae Park
2023-05-18 22:40 ` [PATCH 1/4] Docs/RCU/rculist_nulls: Fix trivial coding style SeongJae Park
@ 2023-05-18 22:40 ` SeongJae Park
2023-05-18 22:40 ` [PATCH 3/4] Docs/RCU/rculist_nulls: Fix hlist_head field name of 'obj' SeongJae Park
2023-05-18 22:40 ` [PATCH 4/4] Docs/RCU/rculist_nulls: Drop unnecessary '_release' in insert function SeongJae Park
3 siblings, 0 replies; 12+ messages in thread
From: SeongJae Park @ 2023-05-18 22:40 UTC (permalink / raw)
To: paulmck; +Cc: SeongJae Park, joel, corbet, rcu, linux-doc, linux-kernel
Lookup example code snippets in rculist_nulls.rst are using 'obj'
without assignment. Fix the code to assign it properly.
Signed-off-by: SeongJae Park <sj@kernel.org>
---
Documentation/RCU/rculist_nulls.rst | 4 ++--
1 file changed, 2 insertions(+), 2 deletions(-)
diff --git a/Documentation/RCU/rculist_nulls.rst b/Documentation/RCU/rculist_nulls.rst
index 253ecd869fc2..94a8bfe9f560 100644
--- a/Documentation/RCU/rculist_nulls.rst
+++ b/Documentation/RCU/rculist_nulls.rst
@@ -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;
--
2.25.1
^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH 3/4] Docs/RCU/rculist_nulls: Fix hlist_head field name of 'obj'
2023-05-18 22:40 [PATCH 0/4] Docs/RCU/rculist_nulls: Minor fixups SeongJae Park
2023-05-18 22:40 ` [PATCH 1/4] Docs/RCU/rculist_nulls: Fix trivial coding style SeongJae Park
2023-05-18 22:40 ` [PATCH 2/4] Docs/RCU/rculist_nulls: Assign 'obj' before use from the examples SeongJae Park
@ 2023-05-18 22:40 ` SeongJae Park
2023-05-18 22:40 ` [PATCH 4/4] Docs/RCU/rculist_nulls: Drop unnecessary '_release' in insert function SeongJae Park
3 siblings, 0 replies; 12+ messages in thread
From: SeongJae Park @ 2023-05-18 22:40 UTC (permalink / raw)
To: paulmck; +Cc: SeongJae Park, joel, corbet, rcu, linux-doc, linux-kernel
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.
Signed-off-by: SeongJae Park <sj@kernel.org>
---
Documentation/RCU/rculist_nulls.rst | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/Documentation/RCU/rculist_nulls.rst b/Documentation/RCU/rculist_nulls.rst
index 94a8bfe9f560..5cd6f3f8810f 100644
--- a/Documentation/RCU/rculist_nulls.rst
+++ b/Documentation/RCU/rculist_nulls.rst
@@ -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
--
2.25.1
^ permalink raw reply related [flat|nested] 12+ messages in thread
* [PATCH 4/4] Docs/RCU/rculist_nulls: Drop unnecessary '_release' in insert function
2023-05-18 22:40 [PATCH 0/4] Docs/RCU/rculist_nulls: Minor fixups SeongJae Park
` (2 preceding siblings ...)
2023-05-18 22:40 ` [PATCH 3/4] Docs/RCU/rculist_nulls: Fix hlist_head field name of 'obj' SeongJae Park
@ 2023-05-18 22:40 ` SeongJae Park
2023-05-19 18:52 ` Joel Fernandes
3 siblings, 1 reply; 12+ messages in thread
From: SeongJae Park @ 2023-05-18 22:40 UTC (permalink / raw)
To: paulmck; +Cc: SeongJae Park, joel, corbet, rcu, linux-doc, linux-kernel
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.
Signed-off-by: SeongJae Park <sj@kernel.org>
---
Documentation/RCU/rculist_nulls.rst | 2 +-
1 file changed, 1 insertion(+), 1 deletion(-)
diff --git a/Documentation/RCU/rculist_nulls.rst b/Documentation/RCU/rculist_nulls.rst
index 5cd6f3f8810f..463270273d89 100644
--- a/Documentation/RCU/rculist_nulls.rst
+++ b/Documentation/RCU/rculist_nulls.rst
@@ -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)
*/
--
2.25.1
^ permalink raw reply related [flat|nested] 12+ messages in thread
* Re: [PATCH 4/4] Docs/RCU/rculist_nulls: Drop unnecessary '_release' in insert function
2023-05-18 22:40 ` [PATCH 4/4] Docs/RCU/rculist_nulls: Drop unnecessary '_release' in insert function SeongJae Park
@ 2023-05-19 18:52 ` Joel Fernandes
2023-06-09 19:12 ` SeongJae Park
0 siblings, 1 reply; 12+ messages in thread
From: Joel Fernandes @ 2023-05-19 18:52 UTC (permalink / raw)
To: SeongJae Park; +Cc: paulmck, corbet, rcu, linux-doc, linux-kernel
On Thu, May 18, 2023 at 6:40 PM SeongJae Park <sj@kernel.org> wrote:
>
> 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.
>
> Signed-off-by: SeongJae Park <sj@kernel.org>
> ---
> Documentation/RCU/rculist_nulls.rst | 2 +-
> 1 file changed, 1 insertion(+), 1 deletion(-)
>
> diff --git a/Documentation/RCU/rculist_nulls.rst b/Documentation/RCU/rculist_nulls.rst
> index 5cd6f3f8810f..463270273d89 100644
> --- a/Documentation/RCU/rculist_nulls.rst
> +++ b/Documentation/RCU/rculist_nulls.rst
> @@ -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:
Reviewed-by: Joel Fernandes (Google) <joel@joelfernandes.org>
thanks,
- Joel
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 4/4] Docs/RCU/rculist_nulls: Drop unnecessary '_release' in insert function
2023-05-19 18:52 ` Joel Fernandes
@ 2023-06-09 19:12 ` SeongJae Park
2023-06-09 23:42 ` Paul E. McKenney
0 siblings, 1 reply; 12+ messages in thread
From: SeongJae Park @ 2023-06-09 19:12 UTC (permalink / raw)
To: Joel Fernandes
Cc: SeongJae Park, paulmck, corbet, rcu, linux-doc, linux-kernel
On Fri, 19 May 2023 14:52:50 -0400 Joel Fernandes <joel@joelfernandes.org> wrote:
> On Thu, May 18, 2023 at 6:40 PM SeongJae Park <sj@kernel.org> wrote:
> >
> > 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.
> >
> > Signed-off-by: SeongJae Park <sj@kernel.org>
> > ---
> > Documentation/RCU/rculist_nulls.rst | 2 +-
> > 1 file changed, 1 insertion(+), 1 deletion(-)
> >
> > diff --git a/Documentation/RCU/rculist_nulls.rst b/Documentation/RCU/rculist_nulls.rst
> > index 5cd6f3f8810f..463270273d89 100644
> > --- a/Documentation/RCU/rculist_nulls.rst
> > +++ b/Documentation/RCU/rculist_nulls.rst
> > @@ -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()?
Paul, may I ask your opinion?
Thanks,
SJ
>
> For the other 3 patches, feel free to add:
> Reviewed-by: Joel Fernandes (Google) <joel@joelfernandes.org>
>
> thanks,
>
> - Joel
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 4/4] Docs/RCU/rculist_nulls: Drop unnecessary '_release' in insert function
2023-06-09 19:12 ` SeongJae Park
@ 2023-06-09 23:42 ` Paul E. McKenney
2023-06-10 0:20 ` SeongJae Park
2023-06-10 5:37 ` Alan Huang
0 siblings, 2 replies; 12+ messages in thread
From: Paul E. McKenney @ 2023-06-09 23:42 UTC (permalink / raw)
To: SeongJae Park; +Cc: Joel Fernandes, corbet, rcu, linux-doc, linux-kernel
On Fri, Jun 09, 2023 at 07:12:06PM +0000, SeongJae Park wrote:
> On Fri, 19 May 2023 14:52:50 -0400 Joel Fernandes <joel@joelfernandes.org> wrote:
>
> > On Thu, May 18, 2023 at 6:40 PM SeongJae Park <sj@kernel.org> wrote:
> > >
> > > 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.
> > >
> > > Signed-off-by: SeongJae Park <sj@kernel.org>
> > > ---
> > > Documentation/RCU/rculist_nulls.rst | 2 +-
> > > 1 file changed, 1 insertion(+), 1 deletion(-)
> > >
> > > diff --git a/Documentation/RCU/rculist_nulls.rst b/Documentation/RCU/rculist_nulls.rst
> > > index 5cd6f3f8810f..463270273d89 100644
> > > --- a/Documentation/RCU/rculist_nulls.rst
> > > +++ b/Documentation/RCU/rculist_nulls.rst
> > > @@ -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()?
>
> 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
> Thanks,
> SJ
>
> >
> > For the other 3 patches, feel free to add:
> > Reviewed-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> >
> > thanks,
> >
> > - Joel
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 4/4] Docs/RCU/rculist_nulls: Drop unnecessary '_release' in insert function
2023-06-09 23:42 ` Paul E. McKenney
@ 2023-06-10 0:20 ` SeongJae Park
2023-06-10 5:52 ` Alan Huang
2023-06-10 5:37 ` Alan Huang
1 sibling, 1 reply; 12+ messages in thread
From: SeongJae Park @ 2023-06-10 0:20 UTC (permalink / raw)
To: Paul E. McKenney
Cc: SeongJae Park, Joel Fernandes, corbet, rcu, linux-doc,
linux-kernel
On Fri, 9 Jun 2023 16:42:59 -0700 "Paul E. McKenney" <paulmck@kernel.org> wrote:
> On Fri, Jun 09, 2023 at 07:12:06PM +0000, SeongJae Park wrote:
> > On Fri, 19 May 2023 14:52:50 -0400 Joel Fernandes <joel@joelfernandes.org> wrote:
> >
> > > On Thu, May 18, 2023 at 6:40 PM SeongJae Park <sj@kernel.org> wrote:
> > > >
> > > > 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.
> > > >
> > > > Signed-off-by: SeongJae Park <sj@kernel.org>
> > > > ---
> > > > Documentation/RCU/rculist_nulls.rst | 2 +-
> > > > 1 file changed, 1 insertion(+), 1 deletion(-)
> > > >
> > > > diff --git a/Documentation/RCU/rculist_nulls.rst b/Documentation/RCU/rculist_nulls.rst
> > > > index 5cd6f3f8810f..463270273d89 100644
> > > > --- a/Documentation/RCU/rculist_nulls.rst
> > > > +++ b/Documentation/RCU/rculist_nulls.rst
> > > > @@ -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()?
> >
> > 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.
Thank you for the nice explanation, and I agree.
>
> 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
>
> Thanx, Paul
>
> > Thanks,
> > SJ
> >
> > >
> > > For the other 3 patches, feel free to add:
> > > Reviewed-by: Joel Fernandes (Google) <joel@joelfernandes.org>
> > >
> > > thanks,
> > >
> > > - Joel
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 4/4] Docs/RCU/rculist_nulls: Drop unnecessary '_release' in insert function
2023-06-09 23:42 ` Paul E. McKenney
2023-06-10 0:20 ` SeongJae Park
@ 2023-06-10 5:37 ` Alan Huang
2023-06-10 11:04 ` Alan Huang
1 sibling, 1 reply; 12+ messages in thread
From: Alan Huang @ 2023-06-10 5:37 UTC (permalink / raw)
To: paulmck; +Cc: SeongJae Park, Joel Fernandes, corbet, rcu, linux-doc,
linux-kernel
Hi Paul,
> 2023年6月10日 07:42，Paul E. McKenney <paulmck@kernel.org> 写道：
>
> On Fri, Jun 09, 2023 at 07:12:06PM +0000, SeongJae Park wrote:
>> On Fri, 19 May 2023 14:52:50 -0400 Joel Fernandes <joel@joelfernandes.org> wrote:
>>
>>> On Thu, May 18, 2023 at 6:40 PM SeongJae Park <sj@kernel.org> wrote:
>>>>
>>>> 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.
>>>>
>>>> Signed-off-by: SeongJae Park <sj@kernel.org>
>>>> ---
>>>> Documentation/RCU/rculist_nulls.rst | 2 +-
>>>> 1 file changed, 1 insertion(+), 1 deletion(-)
>>>>
>>>> diff --git a/Documentation/RCU/rculist_nulls.rst b/Documentation/RCU/rculist_nulls.rst
>>>> index 5cd6f3f8810f..463270273d89 100644
>>>> --- a/Documentation/RCU/rculist_nulls.rst
>>>> +++ b/Documentation/RCU/rculist_nulls.rst
>>>> @@ -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()?
>>
>> 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.
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
>
> Or am I missing something subtle here?
>
> Thanx, Paul
>
>> Thanks,
>> SJ
>>
>>>
>>> For the other 3 patches, feel free to add:
>>> Reviewed-by: Joel Fernandes (Google) <joel@joelfernandes.org>
>>>
>>> thanks,
>>>
>>> - Joel
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 4/4] Docs/RCU/rculist_nulls: Drop unnecessary '_release' in insert function
2023-06-10 0:20 ` SeongJae Park
@ 2023-06-10 5:52 ` Alan Huang
0 siblings, 0 replies; 12+ messages in thread
From: Alan Huang @ 2023-06-10 5:52 UTC (permalink / raw)
To: SeongJae Park
Cc: Paul E. McKenney, Joel Fernandes, corbet, rcu, linux-doc,
linux-kernel
Hi SJ,
> 2023年6月10日 08:20，SeongJae Park <sj@kernel.org> 写道：
>
> On Fri, 9 Jun 2023 16:42:59 -0700 "Paul E. McKenney" <paulmck@kernel.org> wrote:
>
>> On Fri, Jun 09, 2023 at 07:12:06PM +0000, SeongJae Park wrote:
>>> On Fri, 19 May 2023 14:52:50 -0400 Joel Fernandes <joel@joelfernandes.org> wrote:
>>>
>>>> On Thu, May 18, 2023 at 6:40 PM SeongJae Park <sj@kernel.org> wrote:
>>>>>
>>>>> 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.
>>>>>
>>>>> Signed-off-by: SeongJae Park <sj@kernel.org>
>>>>> ---
>>>>> Documentation/RCU/rculist_nulls.rst | 2 +-
>>>>> 1 file changed, 1 insertion(+), 1 deletion(-)
>>>>>
>>>>> diff --git a/Documentation/RCU/rculist_nulls.rst b/Documentation/RCU/rculist_nulls.rst
>>>>> index 5cd6f3f8810f..463270273d89 100644
>>>>> --- a/Documentation/RCU/rculist_nulls.rst
>>>>> +++ b/Documentation/RCU/rculist_nulls.rst
>>>>> @@ -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()?
>>>
>>> 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.
>
> Thank you for the nice explanation, and I agree.
>
>>
>> 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,
>> 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
>
> ```
> --- 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
>
>>
>> Thanx, Paul
>>
>>> Thanks,
>>> SJ
>>>
>>>>
>>>> For the other 3 patches, feel free to add:
>>>> Reviewed-by: Joel Fernandes (Google) <joel@joelfernandes.org>
>>>>
>>>> thanks,
>>>>
>>>> - Joel
^ permalink raw reply [flat|nested] 12+ messages in thread
* Re: [PATCH 4/4] Docs/RCU/rculist_nulls: Drop unnecessary '_release' in insert function
2023-06-10 5:37 ` Alan Huang
@ 2023-06-10 11:04 ` Alan Huang
0 siblings, 0 replies; 12+ messages in thread
From: Alan Huang @ 2023-06-10 11:04 UTC (permalink / raw)
To: paulmck; +Cc: SeongJae Park, Joel Fernandes, corbet, rcu, linux-doc,
linux-kernel
> 2023年6月10日 13:37，Alan Huang <mmpgouride@gmail.com> 写道：
>
> Hi Paul,
>
>> 2023年6月10日 07:42，Paul E. McKenney <paulmck@kernel.org> 写道：
>>
>> On Fri, Jun 09, 2023 at 07:12:06PM +0000, SeongJae Park wrote:
>>> On Fri, 19 May 2023 14:52:50 -0400 Joel Fernandes <joel@joelfernandes.org> wrote:
>>>
>>>> On Thu, May 18, 2023 at 6:40 PM SeongJae Park <sj@kernel.org> wrote:
>>>>>
>>>>> 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.
>>>>>
>>>>> Signed-off-by: SeongJae Park <sj@kernel.org>
>>>>> ---
>>>>> Documentation/RCU/rculist_nulls.rst | 2 +-
>>>>> 1 file changed, 1 insertion(+), 1 deletion(-)
>>>>>
>>>>> diff --git a/Documentation/RCU/rculist_nulls.rst b/Documentation/RCU/rculist_nulls.rst
>>>>> index 5cd6f3f8810f..463270273d89 100644
>>>>> --- a/Documentation/RCU/rculist_nulls.rst
>>>>> +++ b/Documentation/RCU/rculist_nulls.rst
>>>>> @@ -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()?
>>>
>>> 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.
>
> 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.
> 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
>
>>
>> Or am I missing something subtle here?
>>
>> Thanx, Paul
>>
>>> Thanks,
>>> SJ
>>>
>>>>
>>>> For the other 3 patches, feel free to add:
>>>> Reviewed-by: Joel Fernandes (Google) <joel@joelfernandes.org>
>>>>
>>>> thanks,
>>>>
>>>> - Joel
^ permalink raw reply [flat|nested] 12+ messages in thread
end of thread, other threads:[~2023-06-10 11:05 UTC | newest]
Thread overview: 12+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2023-05-18 22:40 [PATCH 0/4] Docs/RCU/rculist_nulls: Minor fixups SeongJae Park
2023-05-18 22:40 ` [PATCH 1/4] Docs/RCU/rculist_nulls: Fix trivial coding style SeongJae Park
2023-05-18 22:40 ` [PATCH 2/4] Docs/RCU/rculist_nulls: Assign 'obj' before use from the examples SeongJae Park
2023-05-18 22:40 ` [PATCH 3/4] Docs/RCU/rculist_nulls: Fix hlist_head field name of 'obj' SeongJae Park
2023-05-18 22:40 ` [PATCH 4/4] Docs/RCU/rculist_nulls: Drop unnecessary '_release' in insert function SeongJae Park
2023-05-19 18:52 ` Joel Fernandes
2023-06-09 19:12 ` SeongJae Park
2023-06-09 23:42 ` Paul E. McKenney
2023-06-10 0:20 ` SeongJae Park
2023-06-10 5:52 ` Alan Huang
2023-06-10 5:37 ` Alan Huang
2023-06-10 11:04 ` Alan Huang
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).