* [PATCH v2] doc/rcuref: Document real world examples in kernel @ 2019-03-29 14:05 Joel Fernandes (Google) 2019-04-04 20:10 ` Paul E. McKenney 0 siblings, 1 reply; 6+ messages in thread From: Joel Fernandes (Google) @ 2019-03-29 14:05 UTC (permalink / raw) To: linux-kernel Cc: Joel Fernandes (Google), oleg, jannh, Jonathan Corbet, Josh Triplett, Lai Jiangshan, linux-doc, Mathieu Desnoyers, Paul E. McKenney, Steven Rostedt Document similar real world examples in the kernel corresponding to the second and third code snippets. Also correct an issue in release_referenced() in the code snippet example. Cc: oleg@redhat.com Cc: jannh@google.com Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org> v1->v2: - minor fixups, label code listings. Documentation/RCU/rcuref.txt | 17 ++++++++++++++++- 1 file changed, 16 insertions(+), 1 deletion(-) diff --git a/Documentation/RCU/rcuref.txt b/Documentation/RCU/rcuref.txt index 613033ff2b9b..a49d525ce975 100644 --- a/Documentation/RCU/rcuref.txt +++ b/Documentation/RCU/rcuref.txt @@ -12,6 +12,7 @@ please read on. Reference counting on elements of lists which are protected by traditional reader/writer spinlocks or semaphores are straightforward: +CODE LISTING A: 1. 2. add() search_and_reference() { { @@ -28,7 +29,8 @@ add() search_and_reference() release_referenced() delete() { { ... write_lock(&list_lock); - atomic_dec(&el->rc, relfunc) ... + if(atomic_dec_and_test(&el->rc)) ... + kfree(el); ... remove_element } write_unlock(&list_lock); ... @@ -44,6 +46,7 @@ search_and_reference() could potentially hold reference to an element which has already been deleted from the list/array. Use atomic_inc_not_zero() in this scenario as follows: +CODE LISTING B: 1. 2. add() search_and_reference() { { @@ -79,6 +82,7 @@ search_and_reference() code path. In such cases, the atomic_dec_and_test() may be moved from delete() to el_free() as follows: +CODE LISTING C: 1. 2. add() search_and_reference() { { @@ -114,6 +118,13 @@ element can therefore safely be freed. This in turn guarantees that if any reader finds the element, that reader may safely acquire a reference without checking the value of the reference counter. +As can be seen, a clear advantage of the pattern in listing C is, if there are +several calls to search_and_reference() in parallel to the delete(), then all +of those will succeed in obtaining a reference to the object if the object +could be found in the list before it was deleted in delete(), unlike the +pattern in listing B which would fail to acquire references in such a situation +even though the object is still in memory. + In cases where delete() can sleep, synchronize_rcu() can be called from delete(), so that el_free() can be subsumed into delete as follows: @@ -130,3 +141,7 @@ delete() kfree(el); ... } + +As additional examples in the kernel, the pattern in listing C is used by +reference counting of struct pid, while the pattern in listing B is used by +struct posix_acl. -- 2.21.0.392.gf8f6787159e-goog ^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH v2] doc/rcuref: Document real world examples in kernel 2019-03-29 14:05 [PATCH v2] doc/rcuref: Document real world examples in kernel Joel Fernandes (Google) @ 2019-04-04 20:10 ` Paul E. McKenney 2019-04-06 2:17 ` Joel Fernandes 0 siblings, 1 reply; 6+ messages in thread From: Paul E. McKenney @ 2019-04-04 20:10 UTC (permalink / raw) To: Joel Fernandes (Google) Cc: linux-kernel, oleg, jannh, Jonathan Corbet, Josh Triplett, Lai Jiangshan, linux-doc, Mathieu Desnoyers, Steven Rostedt On Fri, Mar 29, 2019 at 10:05:55AM -0400, Joel Fernandes (Google) wrote: > Document similar real world examples in the kernel corresponding to the > second and third code snippets. Also correct an issue in > release_referenced() in the code snippet example. > > Cc: oleg@redhat.com > Cc: jannh@google.com > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org> Good catch, thank you! As usual, I could not resist doing a bit of wordsmithing. Please let me know if I messed anything up in the version shown below. Thanx, Paul ------------------------------------------------------------------------ commit adcd92c0ab303b57b28a3cd097bd9ece824c14f6 Author: Joel Fernandes (Google) <joel@joelfernandes.org> Date: Fri Mar 29 10:05:55 2019 -0400 doc/rcuref: Document real world examples in kernel Document similar real world examples in the kernel corresponding to the second and third code snippets. Also correct an issue in release_referenced() in the code snippet example. Cc: oleg@redhat.com Cc: jannh@google.com Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org> [ paulmck: Do a bit of wordsmithing. ] Signed-off-by: Paul E. McKenney <paulmck@linux.ibm.com> diff --git a/Documentation/RCU/rcuref.txt b/Documentation/RCU/rcuref.txt index 613033ff2b9b..c0bab7fb57e7 100644 --- a/Documentation/RCU/rcuref.txt +++ b/Documentation/RCU/rcuref.txt @@ -12,6 +12,7 @@ please read on. Reference counting on elements of lists which are protected by traditional reader/writer spinlocks or semaphores are straightforward: +CODE LISTING A: 1. 2. add() search_and_reference() { { @@ -28,7 +29,8 @@ add() search_and_reference() release_referenced() delete() { { ... write_lock(&list_lock); - atomic_dec(&el->rc, relfunc) ... + if(atomic_dec_and_test(&el->rc)) ... + kfree(el); ... remove_element } write_unlock(&list_lock); ... @@ -44,6 +46,7 @@ search_and_reference() could potentially hold reference to an element which has already been deleted from the list/array. Use atomic_inc_not_zero() in this scenario as follows: +CODE LISTING B: 1. 2. add() search_and_reference() { { @@ -79,6 +82,7 @@ search_and_reference() code path. In such cases, the atomic_dec_and_test() may be moved from delete() to el_free() as follows: +CODE LISTING C: 1. 2. add() search_and_reference() { { @@ -114,6 +118,16 @@ element can therefore safely be freed. This in turn guarantees that if any reader finds the element, that reader may safely acquire a reference without checking the value of the reference counter. +A clear advantage of the RCU-based pattern in listing C over the one +in listing B is that any call to search_and_reference() that locates +a given object will succeed in obtaining a reference to that object, +even given a concurrent invocation of delete() for that same object. +Similarly, a call to delete() is not delayed even if there are an +arbitrarily large number of calls to search_and_reference() searching +for the same object that delete() was invoked on. Instead, all that is +delayed is the eventual invocation of kfree(), which is usually not a +problem on modern computer systems, even the small ones. + In cases where delete() can sleep, synchronize_rcu() can be called from delete(), so that el_free() can be subsumed into delete as follows: @@ -130,3 +144,7 @@ delete() kfree(el); ... } + +As additional examples in the kernel, the pattern in listing C is used by +reference counting of struct pid, while the pattern in listing B is used by +struct posix_acl. ^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH v2] doc/rcuref: Document real world examples in kernel 2019-04-04 20:10 ` Paul E. McKenney @ 2019-04-06 2:17 ` Joel Fernandes 2019-04-08 17:52 ` Paul E. McKenney 0 siblings, 1 reply; 6+ messages in thread From: Joel Fernandes @ 2019-04-06 2:17 UTC (permalink / raw) To: Paul E. McKenney Cc: linux-kernel, oleg, jannh, Jonathan Corbet, Josh Triplett, Lai Jiangshan, linux-doc, Mathieu Desnoyers, Steven Rostedt On Thu, Apr 04, 2019 at 01:10:39PM -0700, Paul E. McKenney wrote: > On Fri, Mar 29, 2019 at 10:05:55AM -0400, Joel Fernandes (Google) wrote: > > Document similar real world examples in the kernel corresponding to the > > second and third code snippets. Also correct an issue in > > release_referenced() in the code snippet example. > > > > Cc: oleg@redhat.com > > Cc: jannh@google.com > > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org> > > Good catch, thank you! > > As usual, I could not resist doing a bit of wordsmithing. Please let me > know if I messed anything up in the version shown below. > > Thanx, Paul > > ------------------------------------------------------------------------ > > commit adcd92c0ab303b57b28a3cd097bd9ece824c14f6 > Author: Joel Fernandes (Google) <joel@joelfernandes.org> > Date: Fri Mar 29 10:05:55 2019 -0400 > > doc/rcuref: Document real world examples in kernel > > Document similar real world examples in the kernel corresponding to the > second and third code snippets. Also correct an issue in > release_referenced() in the code snippet example. > > Cc: oleg@redhat.com > Cc: jannh@google.com > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org> > [ paulmck: Do a bit of wordsmithing. ] > Signed-off-by: Paul E. McKenney <paulmck@linux.ibm.com> > > diff --git a/Documentation/RCU/rcuref.txt b/Documentation/RCU/rcuref.txt > index 613033ff2b9b..c0bab7fb57e7 100644 > --- a/Documentation/RCU/rcuref.txt > +++ b/Documentation/RCU/rcuref.txt > @@ -12,6 +12,7 @@ please read on. > Reference counting on elements of lists which are protected by traditional > reader/writer spinlocks or semaphores are straightforward: > > +CODE LISTING A: > 1. 2. > add() search_and_reference() > { { > @@ -28,7 +29,8 @@ add() search_and_reference() > release_referenced() delete() > { { > ... write_lock(&list_lock); > - atomic_dec(&el->rc, relfunc) ... > + if(atomic_dec_and_test(&el->rc)) ... > + kfree(el); > ... remove_element > } write_unlock(&list_lock); > ... > @@ -44,6 +46,7 @@ search_and_reference() could potentially hold reference to an element which > has already been deleted from the list/array. Use atomic_inc_not_zero() > in this scenario as follows: > > +CODE LISTING B: > 1. 2. > add() search_and_reference() > { { > @@ -79,6 +82,7 @@ search_and_reference() code path. In such cases, the > atomic_dec_and_test() may be moved from delete() to el_free() > as follows: > > +CODE LISTING C: > 1. 2. > add() search_and_reference() > { { > @@ -114,6 +118,16 @@ element can therefore safely be freed. This in turn guarantees that if > any reader finds the element, that reader may safely acquire a reference > without checking the value of the reference counter. > > +A clear advantage of the RCU-based pattern in listing C over the one > +in listing B is that any call to search_and_reference() that locates > +a given object will succeed in obtaining a reference to that object, > +even given a concurrent invocation of delete() for that same object. This part sounds good to me. > +Similarly, a call to delete() is not delayed even if there are an > +arbitrarily large number of calls to search_and_reference() searching > +for the same object that delete() was invoked on. Instead, all that is > +delayed is the eventual invocation of kfree(), which is usually not a > +problem on modern computer systems, even the small ones. > + small nit: This part is common to both listing B and C right? The delete() is never delayed due to the search_and_reference in either case, and the kfree is what is delayed. My patch was highlighting the difference between the 2 listings, but this text says what is common between both listings. As such I am Ok with the changes you made, and thanks for this document in the first place. thanks, - Joel > In cases where delete() can sleep, synchronize_rcu() can be called from > delete(), so that el_free() can be subsumed into delete as follows: > > @@ -130,3 +144,7 @@ delete() > kfree(el); > ... > } > + > +As additional examples in the kernel, the pattern in listing C is used by > +reference counting of struct pid, while the pattern in listing B is used by > +struct posix_acl. > ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH v2] doc/rcuref: Document real world examples in kernel 2019-04-06 2:17 ` Joel Fernandes @ 2019-04-08 17:52 ` Paul E. McKenney 2019-04-08 18:08 ` Joel Fernandes 0 siblings, 1 reply; 6+ messages in thread From: Paul E. McKenney @ 2019-04-08 17:52 UTC (permalink / raw) To: Joel Fernandes Cc: linux-kernel, oleg, jannh, Jonathan Corbet, Josh Triplett, Lai Jiangshan, linux-doc, Mathieu Desnoyers, Steven Rostedt On Sat, Apr 06, 2019 at 02:17:05AM +0000, Joel Fernandes wrote: > On Thu, Apr 04, 2019 at 01:10:39PM -0700, Paul E. McKenney wrote: > > On Fri, Mar 29, 2019 at 10:05:55AM -0400, Joel Fernandes (Google) wrote: > > > Document similar real world examples in the kernel corresponding to the > > > second and third code snippets. Also correct an issue in > > > release_referenced() in the code snippet example. > > > > > > Cc: oleg@redhat.com > > > Cc: jannh@google.com > > > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org> > > > > Good catch, thank you! > > > > As usual, I could not resist doing a bit of wordsmithing. Please let me > > know if I messed anything up in the version shown below. > > > > Thanx, Paul > > > > ------------------------------------------------------------------------ > > > > commit adcd92c0ab303b57b28a3cd097bd9ece824c14f6 > > Author: Joel Fernandes (Google) <joel@joelfernandes.org> > > Date: Fri Mar 29 10:05:55 2019 -0400 > > > > doc/rcuref: Document real world examples in kernel > > > > Document similar real world examples in the kernel corresponding to the > > second and third code snippets. Also correct an issue in > > release_referenced() in the code snippet example. > > > > Cc: oleg@redhat.com > > Cc: jannh@google.com > > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org> > > [ paulmck: Do a bit of wordsmithing. ] > > Signed-off-by: Paul E. McKenney <paulmck@linux.ibm.com> > > > > diff --git a/Documentation/RCU/rcuref.txt b/Documentation/RCU/rcuref.txt > > index 613033ff2b9b..c0bab7fb57e7 100644 > > --- a/Documentation/RCU/rcuref.txt > > +++ b/Documentation/RCU/rcuref.txt > > @@ -12,6 +12,7 @@ please read on. > > Reference counting on elements of lists which are protected by traditional > > reader/writer spinlocks or semaphores are straightforward: > > > > +CODE LISTING A: > > 1. 2. > > add() search_and_reference() > > { { > > @@ -28,7 +29,8 @@ add() search_and_reference() > > release_referenced() delete() > > { { > > ... write_lock(&list_lock); > > - atomic_dec(&el->rc, relfunc) ... > > + if(atomic_dec_and_test(&el->rc)) ... > > + kfree(el); > > ... remove_element > > } write_unlock(&list_lock); > > ... > > @@ -44,6 +46,7 @@ search_and_reference() could potentially hold reference to an element which > > has already been deleted from the list/array. Use atomic_inc_not_zero() > > in this scenario as follows: > > > > +CODE LISTING B: > > 1. 2. > > add() search_and_reference() > > { { > > @@ -79,6 +82,7 @@ search_and_reference() code path. In such cases, the > > atomic_dec_and_test() may be moved from delete() to el_free() > > as follows: > > > > +CODE LISTING C: > > 1. 2. > > add() search_and_reference() > > { { > > @@ -114,6 +118,16 @@ element can therefore safely be freed. This in turn guarantees that if > > any reader finds the element, that reader may safely acquire a reference > > without checking the value of the reference counter. > > > > +A clear advantage of the RCU-based pattern in listing C over the one > > +in listing B is that any call to search_and_reference() that locates > > +a given object will succeed in obtaining a reference to that object, > > +even given a concurrent invocation of delete() for that same object. > > This part sounds good to me. > > > +Similarly, a call to delete() is not delayed even if there are an > > +arbitrarily large number of calls to search_and_reference() searching > > +for the same object that delete() was invoked on. Instead, all that is > > +delayed is the eventual invocation of kfree(), which is usually not a > > +problem on modern computer systems, even the small ones. > > + > > small nit: > This part is common to both listing B and C right? The delete() is never > delayed due to the search_and_reference in either case, and the kfree is what > is delayed. My patch was highlighting the difference between the 2 > listings, but this text says what is common between both listings. > > As such I am Ok with the changes you made, and thanks for this document in > the first place. Good point! How about the following patch to be merged into the current patch? Thanx, Paul ------------------------------------------------------------------------ diff --git a/Documentation/RCU/rcuref.txt b/Documentation/RCU/rcuref.txt index c0bab7fb57e7..5e6429d66c24 100644 --- a/Documentation/RCU/rcuref.txt +++ b/Documentation/RCU/rcuref.txt @@ -122,11 +122,12 @@ A clear advantage of the RCU-based pattern in listing C over the one in listing B is that any call to search_and_reference() that locates a given object will succeed in obtaining a reference to that object, even given a concurrent invocation of delete() for that same object. -Similarly, a call to delete() is not delayed even if there are an -arbitrarily large number of calls to search_and_reference() searching -for the same object that delete() was invoked on. Instead, all that is -delayed is the eventual invocation of kfree(), which is usually not a -problem on modern computer systems, even the small ones. +Similarly, a clear advantage of both listings B and C over listing A is +that a call to delete() is not delayed even if there are an arbitrarily +large number of calls to search_and_reference() searching for the same +object that delete() was invoked on. Instead, all that is delayed is +the eventual invocation of kfree(), which is usually not a problem on +modern computer systems, even the small ones. In cases where delete() can sleep, synchronize_rcu() can be called from delete(), so that el_free() can be subsumed into delete as follows: ^ permalink raw reply related [flat|nested] 6+ messages in thread
* Re: [PATCH v2] doc/rcuref: Document real world examples in kernel 2019-04-08 17:52 ` Paul E. McKenney @ 2019-04-08 18:08 ` Joel Fernandes 2019-04-08 18:29 ` Paul E. McKenney 0 siblings, 1 reply; 6+ messages in thread From: Joel Fernandes @ 2019-04-08 18:08 UTC (permalink / raw) To: Paul E. McKenney Cc: linux-kernel, oleg, jannh, Jonathan Corbet, Josh Triplett, Lai Jiangshan, linux-doc, Mathieu Desnoyers, Steven Rostedt On Mon, Apr 08, 2019 at 10:52:13AM -0700, Paul E. McKenney wrote: > On Sat, Apr 06, 2019 at 02:17:05AM +0000, Joel Fernandes wrote: > > On Thu, Apr 04, 2019 at 01:10:39PM -0700, Paul E. McKenney wrote: > > > On Fri, Mar 29, 2019 at 10:05:55AM -0400, Joel Fernandes (Google) wrote: > > > > Document similar real world examples in the kernel corresponding to the > > > > second and third code snippets. Also correct an issue in > > > > release_referenced() in the code snippet example. > > > > > > > > Cc: oleg@redhat.com > > > > Cc: jannh@google.com > > > > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org> > > > > > > Good catch, thank you! > > > > > > As usual, I could not resist doing a bit of wordsmithing. Please let me > > > know if I messed anything up in the version shown below. > > > > > > Thanx, Paul > > > > > > ------------------------------------------------------------------------ > > > > > > commit adcd92c0ab303b57b28a3cd097bd9ece824c14f6 > > > Author: Joel Fernandes (Google) <joel@joelfernandes.org> > > > Date: Fri Mar 29 10:05:55 2019 -0400 > > > > > > doc/rcuref: Document real world examples in kernel > > > > > > Document similar real world examples in the kernel corresponding to the > > > second and third code snippets. Also correct an issue in > > > release_referenced() in the code snippet example. > > > > > > Cc: oleg@redhat.com > > > Cc: jannh@google.com > > > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org> > > > [ paulmck: Do a bit of wordsmithing. ] > > > Signed-off-by: Paul E. McKenney <paulmck@linux.ibm.com> > > > > > > diff --git a/Documentation/RCU/rcuref.txt b/Documentation/RCU/rcuref.txt > > > index 613033ff2b9b..c0bab7fb57e7 100644 > > > --- a/Documentation/RCU/rcuref.txt > > > +++ b/Documentation/RCU/rcuref.txt > > > @@ -12,6 +12,7 @@ please read on. > > > Reference counting on elements of lists which are protected by traditional > > > reader/writer spinlocks or semaphores are straightforward: > > > > > > +CODE LISTING A: > > > 1. 2. > > > add() search_and_reference() > > > { { > > > @@ -28,7 +29,8 @@ add() search_and_reference() > > > release_referenced() delete() > > > { { > > > ... write_lock(&list_lock); > > > - atomic_dec(&el->rc, relfunc) ... > > > + if(atomic_dec_and_test(&el->rc)) ... > > > + kfree(el); > > > ... remove_element > > > } write_unlock(&list_lock); > > > ... > > > @@ -44,6 +46,7 @@ search_and_reference() could potentially hold reference to an element which > > > has already been deleted from the list/array. Use atomic_inc_not_zero() > > > in this scenario as follows: > > > > > > +CODE LISTING B: > > > 1. 2. > > > add() search_and_reference() > > > { { > > > @@ -79,6 +82,7 @@ search_and_reference() code path. In such cases, the > > > atomic_dec_and_test() may be moved from delete() to el_free() > > > as follows: > > > > > > +CODE LISTING C: > > > 1. 2. > > > add() search_and_reference() > > > { { > > > @@ -114,6 +118,16 @@ element can therefore safely be freed. This in turn guarantees that if > > > any reader finds the element, that reader may safely acquire a reference > > > without checking the value of the reference counter. > > > > > > +A clear advantage of the RCU-based pattern in listing C over the one > > > +in listing B is that any call to search_and_reference() that locates > > > +a given object will succeed in obtaining a reference to that object, > > > +even given a concurrent invocation of delete() for that same object. > > > > This part sounds good to me. > > > > > +Similarly, a call to delete() is not delayed even if there are an > > > +arbitrarily large number of calls to search_and_reference() searching > > > +for the same object that delete() was invoked on. Instead, all that is > > > +delayed is the eventual invocation of kfree(), which is usually not a > > > +problem on modern computer systems, even the small ones. > > > + > > > > small nit: > > This part is common to both listing B and C right? The delete() is never > > delayed due to the search_and_reference in either case, and the kfree is what > > is delayed. My patch was highlighting the difference between the 2 > > listings, but this text says what is common between both listings. > > > > As such I am Ok with the changes you made, and thanks for this document in > > the first place. > > Good point! How about the following patch to be merged into the current > patch? > > Thanx, Paul > > ------------------------------------------------------------------------ > > diff --git a/Documentation/RCU/rcuref.txt b/Documentation/RCU/rcuref.txt > index c0bab7fb57e7..5e6429d66c24 100644 > --- a/Documentation/RCU/rcuref.txt > +++ b/Documentation/RCU/rcuref.txt > @@ -122,11 +122,12 @@ A clear advantage of the RCU-based pattern in listing C over the one > in listing B is that any call to search_and_reference() that locates > a given object will succeed in obtaining a reference to that object, > even given a concurrent invocation of delete() for that same object. > -Similarly, a call to delete() is not delayed even if there are an > -arbitrarily large number of calls to search_and_reference() searching > -for the same object that delete() was invoked on. Instead, all that is > -delayed is the eventual invocation of kfree(), which is usually not a > -problem on modern computer systems, even the small ones. > +Similarly, a clear advantage of both listings B and C over listing A is > +that a call to delete() is not delayed even if there are an arbitrarily > +large number of calls to search_and_reference() searching for the same > +object that delete() was invoked on. Instead, all that is delayed is > +the eventual invocation of kfree(), which is usually not a problem on > +modern computer systems, even the small ones. > > In cases where delete() can sleep, synchronize_rcu() can be called from > delete(), so that el_free() can be subsumed into delete as follows: > This one looks better to me, thanks a lot! Reviewed-by: Joel Fernandes (Google) <joel@joelfernandes.org> thanks, - Joel ^ permalink raw reply [flat|nested] 6+ messages in thread
* Re: [PATCH v2] doc/rcuref: Document real world examples in kernel 2019-04-08 18:08 ` Joel Fernandes @ 2019-04-08 18:29 ` Paul E. McKenney 0 siblings, 0 replies; 6+ messages in thread From: Paul E. McKenney @ 2019-04-08 18:29 UTC (permalink / raw) To: Joel Fernandes Cc: linux-kernel, oleg, jannh, Jonathan Corbet, Josh Triplett, Lai Jiangshan, linux-doc, Mathieu Desnoyers, Steven Rostedt On Mon, Apr 08, 2019 at 02:08:59PM -0400, Joel Fernandes wrote: > On Mon, Apr 08, 2019 at 10:52:13AM -0700, Paul E. McKenney wrote: > > On Sat, Apr 06, 2019 at 02:17:05AM +0000, Joel Fernandes wrote: > > > On Thu, Apr 04, 2019 at 01:10:39PM -0700, Paul E. McKenney wrote: > > > > On Fri, Mar 29, 2019 at 10:05:55AM -0400, Joel Fernandes (Google) wrote: > > > > > Document similar real world examples in the kernel corresponding to the > > > > > second and third code snippets. Also correct an issue in > > > > > release_referenced() in the code snippet example. > > > > > > > > > > Cc: oleg@redhat.com > > > > > Cc: jannh@google.com > > > > > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org> > > > > > > > > Good catch, thank you! > > > > > > > > As usual, I could not resist doing a bit of wordsmithing. Please let me > > > > know if I messed anything up in the version shown below. > > > > > > > > Thanx, Paul > > > > > > > > ------------------------------------------------------------------------ > > > > > > > > commit adcd92c0ab303b57b28a3cd097bd9ece824c14f6 > > > > Author: Joel Fernandes (Google) <joel@joelfernandes.org> > > > > Date: Fri Mar 29 10:05:55 2019 -0400 > > > > > > > > doc/rcuref: Document real world examples in kernel > > > > > > > > Document similar real world examples in the kernel corresponding to the > > > > second and third code snippets. Also correct an issue in > > > > release_referenced() in the code snippet example. > > > > > > > > Cc: oleg@redhat.com > > > > Cc: jannh@google.com > > > > Signed-off-by: Joel Fernandes (Google) <joel@joelfernandes.org> > > > > [ paulmck: Do a bit of wordsmithing. ] > > > > Signed-off-by: Paul E. McKenney <paulmck@linux.ibm.com> > > > > > > > > diff --git a/Documentation/RCU/rcuref.txt b/Documentation/RCU/rcuref.txt > > > > index 613033ff2b9b..c0bab7fb57e7 100644 > > > > --- a/Documentation/RCU/rcuref.txt > > > > +++ b/Documentation/RCU/rcuref.txt > > > > @@ -12,6 +12,7 @@ please read on. > > > > Reference counting on elements of lists which are protected by traditional > > > > reader/writer spinlocks or semaphores are straightforward: > > > > > > > > +CODE LISTING A: > > > > 1. 2. > > > > add() search_and_reference() > > > > { { > > > > @@ -28,7 +29,8 @@ add() search_and_reference() > > > > release_referenced() delete() > > > > { { > > > > ... write_lock(&list_lock); > > > > - atomic_dec(&el->rc, relfunc) ... > > > > + if(atomic_dec_and_test(&el->rc)) ... > > > > + kfree(el); > > > > ... remove_element > > > > } write_unlock(&list_lock); > > > > ... > > > > @@ -44,6 +46,7 @@ search_and_reference() could potentially hold reference to an element which > > > > has already been deleted from the list/array. Use atomic_inc_not_zero() > > > > in this scenario as follows: > > > > > > > > +CODE LISTING B: > > > > 1. 2. > > > > add() search_and_reference() > > > > { { > > > > @@ -79,6 +82,7 @@ search_and_reference() code path. In such cases, the > > > > atomic_dec_and_test() may be moved from delete() to el_free() > > > > as follows: > > > > > > > > +CODE LISTING C: > > > > 1. 2. > > > > add() search_and_reference() > > > > { { > > > > @@ -114,6 +118,16 @@ element can therefore safely be freed. This in turn guarantees that if > > > > any reader finds the element, that reader may safely acquire a reference > > > > without checking the value of the reference counter. > > > > > > > > +A clear advantage of the RCU-based pattern in listing C over the one > > > > +in listing B is that any call to search_and_reference() that locates > > > > +a given object will succeed in obtaining a reference to that object, > > > > +even given a concurrent invocation of delete() for that same object. > > > > > > This part sounds good to me. > > > > > > > +Similarly, a call to delete() is not delayed even if there are an > > > > +arbitrarily large number of calls to search_and_reference() searching > > > > +for the same object that delete() was invoked on. Instead, all that is > > > > +delayed is the eventual invocation of kfree(), which is usually not a > > > > +problem on modern computer systems, even the small ones. > > > > + > > > > > > small nit: > > > This part is common to both listing B and C right? The delete() is never > > > delayed due to the search_and_reference in either case, and the kfree is what > > > is delayed. My patch was highlighting the difference between the 2 > > > listings, but this text says what is common between both listings. > > > > > > As such I am Ok with the changes you made, and thanks for this document in > > > the first place. > > > > Good point! How about the following patch to be merged into the current > > patch? > > > > Thanx, Paul > > > > ------------------------------------------------------------------------ > > > > diff --git a/Documentation/RCU/rcuref.txt b/Documentation/RCU/rcuref.txt > > index c0bab7fb57e7..5e6429d66c24 100644 > > --- a/Documentation/RCU/rcuref.txt > > +++ b/Documentation/RCU/rcuref.txt > > @@ -122,11 +122,12 @@ A clear advantage of the RCU-based pattern in listing C over the one > > in listing B is that any call to search_and_reference() that locates > > a given object will succeed in obtaining a reference to that object, > > even given a concurrent invocation of delete() for that same object. > > -Similarly, a call to delete() is not delayed even if there are an > > -arbitrarily large number of calls to search_and_reference() searching > > -for the same object that delete() was invoked on. Instead, all that is > > -delayed is the eventual invocation of kfree(), which is usually not a > > -problem on modern computer systems, even the small ones. > > +Similarly, a clear advantage of both listings B and C over listing A is > > +that a call to delete() is not delayed even if there are an arbitrarily > > +large number of calls to search_and_reference() searching for the same > > +object that delete() was invoked on. Instead, all that is delayed is > > +the eventual invocation of kfree(), which is usually not a problem on > > +modern computer systems, even the small ones. > > > > In cases where delete() can sleep, synchronize_rcu() can be called from > > delete(), so that el_free() can be subsumed into delete as follows: > > This one looks better to me, thanks a lot! > > Reviewed-by: Joel Fernandes (Google) <joel@joelfernandes.org> Thank you! (Though this one gets merged into your original patch.) Thanx, Paul ^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2019-04-08 18:29 UTC | newest] Thread overview: 6+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2019-03-29 14:05 [PATCH v2] doc/rcuref: Document real world examples in kernel Joel Fernandes (Google) 2019-04-04 20:10 ` Paul E. McKenney 2019-04-06 2:17 ` Joel Fernandes 2019-04-08 17:52 ` Paul E. McKenney 2019-04-08 18:08 ` Joel Fernandes 2019-04-08 18:29 ` Paul E. McKenney
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 NNTP newsgroup(s).