* [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-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-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 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).