[PATCH tip/core/rcu 0/4] Documentation updates for 3.8

[PATCH tip/core/rcu 0/4] Documentation updates for 3.8

[Paul E. McKenney]

Hello!

This patch series contains documentation updates as follows:

1.	Fix a broken example in memory-barriers.txt.
2.	Fix a paper title in RTFP.txt. (Courtesy of Dhaval Giani.)
3.	Mention kfree_rcu() in the whatisRCU.txt section covering
	call_rcu(), and fix example code. (Courtesy of Kees Cook.)
4.	Add two more ways of combining RCU and reference counting
	in rcuref.txt.

							Thanx, Paul


 b/Documentation/RCU/RTFP.txt        |    2 -
 b/Documentation/RCU/listRCU.txt     |    2 -
 b/Documentation/RCU/rcuref.txt      |   61 ++++++++++++++++++++++++++++++++++--
 b/Documentation/RCU/whatisRCU.txt   |   13 ++++++-
 b/Documentation/memory-barriers.txt |    9 ++---
 5 files changed, 77 insertions(+), 10 deletions(-)

[PATCH tip/core/rcu 1/4] Documentation: Fix memory-barriers.txt example

[Paul E. McKenney]

From: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>

This commit fixes a broken example of overlapping stores in the
Documentation/memory-barriers.txt file.

Reported-by: Nikunj A Dadhania <nikunj@linux.vnet.ibm.com>
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
---
 Documentation/memory-barriers.txt |    9 +++++----
 1 files changed, 5 insertions(+), 4 deletions(-)

diff --git a/Documentation/memory-barriers.txt b/Documentation/memory-barriers.txt
index 2759f7c..3c4e1b3 100644
--- a/Documentation/memory-barriers.txt
+++ b/Documentation/memory-barriers.txt
@@ -251,12 +251,13 @@ And there are a number of things that _must_ or _must_not_ be assumed:
 
      And for:
 
-	*A = X; Y = *A;
+	*A = X; *(A + 4) = Y;
 
-     we may get either of:
+     we may get any of:
 
-	STORE *A = X; Y = LOAD *A;
-	STORE *A = Y = X;
+	STORE *A = X; STORE *(A + 4) = Y;
+	STORE *(A + 4) = Y; STORE *A = X;
+	STORE {*A, *(A + 4) } = {X, Y};
 
 
 =========================
-- 
1.7.8

[PATCH tip/core/rcu 2/4] rcu: Correct the name of a reference in list of RCU papers

[Paul E. McKenney]

From: Dhaval Giani <dhaval.giani@gmail.com>

Trying to go through the history of RCU (not for the weak
minded) led me to search for a non-existent paper.

Correct it to the actual reference

Signed-off-by: Dhaval Giani <dhaval.giani@gmail.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
---
 Documentation/RCU/RTFP.txt |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/Documentation/RCU/RTFP.txt b/Documentation/RCU/RTFP.txt
index 7c1dfb1..7f40c72 100644
--- a/Documentation/RCU/RTFP.txt
+++ b/Documentation/RCU/RTFP.txt
@@ -186,7 +186,7 @@ Bibtex Entries
 
 @article{Kung80
 ,author="H. T. Kung and Q. Lehman"
-,title="Concurrent Maintenance of Binary Search Trees"
+,title="Concurrent Manipulation of Binary Search Trees"
 ,Year="1980"
 ,Month="September"
 ,journal="ACM Transactions on Database Systems"
-- 
1.7.8

[PATCH tip/core/rcu 3/4] RCU: Update docs to include kfree_rcu()

[Paul E. McKenney]

From: Kees Cook <keescook@chromium.org>

Mention kfree_rcu() in the call_rcu() section.  Additionally fix the
example code for list replacement that used the wrong structure element.

Signed-off-by: Kees Cook <keescook@chromium.org>
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
---
 Documentation/RCU/listRCU.txt   |    2 +-
 Documentation/RCU/whatisRCU.txt |   13 +++++++++++--
 2 files changed, 12 insertions(+), 3 deletions(-)

diff --git a/Documentation/RCU/listRCU.txt b/Documentation/RCU/listRCU.txt
index 4349c14..adb5a37 100644
--- a/Documentation/RCU/listRCU.txt
+++ b/Documentation/RCU/listRCU.txt
@@ -205,7 +205,7 @@ RCU ("read-copy update") its name.  The RCU code is as follows:
 				audit_copy_rule(&ne->rule, &e->rule);
 				ne->rule.action = newaction;
 				ne->rule.file_count = newfield_count;
-				list_replace_rcu(e, ne);
+				list_replace_rcu(&e->list, &ne->list);
 				call_rcu(&e->rcu, audit_free_rule);
 				return 0;
 			}
diff --git a/Documentation/RCU/whatisRCU.txt b/Documentation/RCU/whatisRCU.txt
index bf0f6de..160ac55 100644
--- a/Documentation/RCU/whatisRCU.txt
+++ b/Documentation/RCU/whatisRCU.txt
@@ -499,6 +499,8 @@ The foo_reclaim() function might appear as follows:
 	{
 		struct foo *fp = container_of(rp, struct foo, rcu);
 
+		foo_cleanup(fp->a);
+
 		kfree(fp);
 	}
 
@@ -521,6 +523,12 @@ o	Use call_rcu() -after- removing a data element from an
 	read-side critical sections that might be referencing that
 	data item.
 
+If the callback for call_rcu() is not doing anything more than calling
+kfree() on the structure, you can use kfree_rcu() instead of call_rcu()
+to avoid having to write your own callback:
+
+	kfree_rcu(old_fp, rcu);
+
 Again, see checklist.txt for additional rules governing the use of RCU.
 
 
@@ -773,8 +781,8 @@ a single atomic update, converting to RCU will require special care.
 
 Also, the presence of synchronize_rcu() means that the RCU version of
 delete() can now block.  If this is a problem, there is a callback-based
-mechanism that never blocks, namely call_rcu(), that can be used in
-place of synchronize_rcu().
+mechanism that never blocks, namely call_rcu() or kfree_rcu(), that can
+be used in place of synchronize_rcu().
 
 
 7.  FULL LIST OF RCU APIs
@@ -813,6 +821,7 @@ RCU:	Critical sections	Grace period		Barrier
 	rcu_read_unlock		synchronize_rcu
 	rcu_dereference		synchronize_rcu_expedited
 				call_rcu
+				kfree_rcu
 
 
 bh:	Critical sections	Grace period		Barrier
-- 
1.7.8

[PATCH tip/core/rcu 4/4] rcu: Document alternative RCU/reference-count algorithms

[Paul E. McKenney]

From: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>

The approach for mixing RCU and reference counting listed in the RCU
documentation only describes one possible approach.  This approach can
result in failure on the read side, which is nice if you want fresh data,
but not so good if you want simple code.  This commit therefore adds
two additional approaches that feature unconditional reference-count
acquisition by RCU readers.  These approaches are very similar to that
used in the security code.

Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
---
 Documentation/RCU/rcuref.txt |   61 ++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 59 insertions(+), 2 deletions(-)

diff --git a/Documentation/RCU/rcuref.txt b/Documentation/RCU/rcuref.txt
index 4202ad0..99ca662 100644
--- a/Documentation/RCU/rcuref.txt
+++ b/Documentation/RCU/rcuref.txt
@@ -20,7 +20,7 @@ release_referenced()			delete()
 {					{
     ...					    write_lock(&list_lock);
     atomic_dec(&el->rc, relfunc)	    ...
-    ...					    delete_element
+    ...					    remove_element
 }					    write_unlock(&list_lock);
  					    ...
 					    if (atomic_dec_and_test(&el->rc))
@@ -52,7 +52,7 @@ release_referenced()			delete()
 {					{
     ...					    spin_lock(&list_lock);
     if (atomic_dec_and_test(&el->rc))       ...
-        call_rcu(&el->head, el_free);       delete_element
+        call_rcu(&el->head, el_free);       remove_element
     ...                                     spin_unlock(&list_lock);
 } 					    ...
 					    if (atomic_dec_and_test(&el->rc))
@@ -64,3 +64,60 @@ Sometimes, a reference to the element needs to be obtained in the
 update (write) stream.  In such cases, atomic_inc_not_zero() might be
 overkill, since we hold the update-side spinlock.  One might instead
 use atomic_inc() in such cases.
+
+It is not always convenient to deal with "FAIL" in the
+search_and_reference() code path.  In such cases, the
+atomic_dec_and_test() may be moved from delete() to el_free()
+as follows:
+
+1.					2.
+add()					search_and_reference()
+{					{
+    alloc_object			    rcu_read_lock();
+    ...					    search_for_element
+    atomic_set(&el->rc, 1);		    atomic_inc(&el->rc);
+    spin_lock(&list_lock);		    ...
+				
+    add_element				    rcu_read_unlock();
+    ...					}
+    spin_unlock(&list_lock);		4.
+}					delete()
+3.					{
+release_referenced()			    spin_lock(&list_lock);
+{					    ...
+    ...					    remove_element
+    if (atomic_dec_and_test(&el->rc))       spin_unlock(&list_lock);
+        kfree(el);			    ...
+    ...                                     call_rcu(&el->head, el_free);
+} 					    ...
+5.					}
+void el_free(struct rcu_head *rhp)
+{
+    release_referenced();
+}
+
+The key point is that the initial reference added by add() is not removed
+until after a grace period has elapsed following removal.  This means that
+search_and_reference() cannot find this element, which means that the value
+of el->rc cannot increase.  Thus, once it reaches zero, there are no
+readers that can or ever will be able to reference the element.  The
+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.
+
+In cases where delete() can sleep, synchronize_rcu() can be called from
+delete(), so that el_free() can be subsumed into delete as follows:
+
+4.
+delete()
+{
+    spin_lock(&list_lock);
+    ...
+    remove_element
+    spin_unlock(&list_lock);
+    ...
+    synchronize_rcu();
+    if (atomic_dec_and_test(&el->rc))
+    	kfree(el);
+    ...
+}
-- 
1.7.8

Re: [PATCH tip/core/rcu 4/4] rcu: Document alternative RCU/reference-count algorithms

[Mathieu Desnoyers]

* Paul E. McKenney (paulmck@linux.vnet.ibm.com) wrote:
> From: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
> 
> The approach for mixing RCU and reference counting listed in the RCU
> documentation only describes one possible approach.  This approach can
> result in failure on the read side, which is nice if you want fresh data,
> but not so good if you want simple code.  This commit therefore adds
> two additional approaches that feature unconditional reference-count
> acquisition by RCU readers.  These approaches are very similar to that
> used in the security code.
> 
> Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> ---
>  Documentation/RCU/rcuref.txt |   61 ++++++++++++++++++++++++++++++++++++++++-
>  1 files changed, 59 insertions(+), 2 deletions(-)
> 
> diff --git a/Documentation/RCU/rcuref.txt b/Documentation/RCU/rcuref.txt
> index 4202ad0..99ca662 100644
> --- a/Documentation/RCU/rcuref.txt
> +++ b/Documentation/RCU/rcuref.txt
> @@ -20,7 +20,7 @@ release_referenced()			delete()
>  {					{
>      ...					    write_lock(&list_lock);
>      atomic_dec(&el->rc, relfunc)	    ...
> -    ...					    delete_element
> +    ...					    remove_element
>  }					    write_unlock(&list_lock);
>   					    ...
>  					    if (atomic_dec_and_test(&el->rc))
> @@ -52,7 +52,7 @@ release_referenced()			delete()
>  {					{
>      ...					    spin_lock(&list_lock);
>      if (atomic_dec_and_test(&el->rc))       ...
> -        call_rcu(&el->head, el_free);       delete_element
> +        call_rcu(&el->head, el_free);       remove_element
>      ...                                     spin_unlock(&list_lock);
>  } 					    ...
>  					    if (atomic_dec_and_test(&el->rc))
> @@ -64,3 +64,60 @@ Sometimes, a reference to the element needs to be obtained in the
>  update (write) stream.  In such cases, atomic_inc_not_zero() might be
>  overkill, since we hold the update-side spinlock.  One might instead
>  use atomic_inc() in such cases.
> +
> +It is not always convenient to deal with "FAIL" in the
> +search_and_reference() code path.  In such cases, the
> +atomic_dec_and_test() may be moved from delete() to el_free()
> +as follows:
> +
> +1.					2.
> +add()					search_and_reference()
> +{					{
> +    alloc_object			    rcu_read_lock();
> +    ...					    search_for_element
> +    atomic_set(&el->rc, 1);		    atomic_inc(&el->rc);
> +    spin_lock(&list_lock);		    ...
> +				
> +    add_element				    rcu_read_unlock();
> +    ...					}

indentation looks wrong in my mail client for the two lines above (for
the 2. block).

Otherwise, it looks good to me,

Thanks,

Mathieu


> +    spin_unlock(&list_lock);		4.
> +}					delete()
> +3.					{
> +release_referenced()			    spin_lock(&list_lock);
> +{					    ...
> +    ...					    remove_element
> +    if (atomic_dec_and_test(&el->rc))       spin_unlock(&list_lock);
> +        kfree(el);			    ...
> +    ...                                     call_rcu(&el->head, el_free);
> +} 					    ...
> +5.					}
> +void el_free(struct rcu_head *rhp)
> +{
> +    release_referenced();
> +}
> +
> +The key point is that the initial reference added by add() is not removed
> +until after a grace period has elapsed following removal.  This means that
> +search_and_reference() cannot find this element, which means that the value
> +of el->rc cannot increase.  Thus, once it reaches zero, there are no
> +readers that can or ever will be able to reference the element.  The
> +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.
> +
> +In cases where delete() can sleep, synchronize_rcu() can be called from
> +delete(), so that el_free() can be subsumed into delete as follows:
> +
> +4.
> +delete()
> +{
> +    spin_lock(&list_lock);
> +    ...
> +    remove_element
> +    spin_unlock(&list_lock);
> +    ...
> +    synchronize_rcu();
> +    if (atomic_dec_and_test(&el->rc))
> +    	kfree(el);
> +    ...
> +}
> -- 
> 1.7.8
> 

-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com

Re: [PATCH tip/core/rcu 4/4] rcu: Document alternative RCU/reference-count algorithms

[Paul E. McKenney]

On Tue, Oct 30, 2012 at 12:21:03PM -0400, Mathieu Desnoyers wrote:
> * Paul E. McKenney (paulmck@linux.vnet.ibm.com) wrote:
> > From: "Paul E. McKenney" <paulmck@linux.vnet.ibm.com>
> > 
> > The approach for mixing RCU and reference counting listed in the RCU
> > documentation only describes one possible approach.  This approach can
> > result in failure on the read side, which is nice if you want fresh data,
> > but not so good if you want simple code.  This commit therefore adds
> > two additional approaches that feature unconditional reference-count
> > acquisition by RCU readers.  These approaches are very similar to that
> > used in the security code.
> > 
> > Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
> > ---
> >  Documentation/RCU/rcuref.txt |   61 ++++++++++++++++++++++++++++++++++++++++-
> >  1 files changed, 59 insertions(+), 2 deletions(-)
> > 
> > diff --git a/Documentation/RCU/rcuref.txt b/Documentation/RCU/rcuref.txt
> > index 4202ad0..99ca662 100644
> > --- a/Documentation/RCU/rcuref.txt
> > +++ b/Documentation/RCU/rcuref.txt
> > @@ -20,7 +20,7 @@ release_referenced()			delete()
> >  {					{
> >      ...					    write_lock(&list_lock);
> >      atomic_dec(&el->rc, relfunc)	    ...
> > -    ...					    delete_element
> > +    ...					    remove_element
> >  }					    write_unlock(&list_lock);
> >   					    ...
> >  					    if (atomic_dec_and_test(&el->rc))
> > @@ -52,7 +52,7 @@ release_referenced()			delete()
> >  {					{
> >      ...					    spin_lock(&list_lock);
> >      if (atomic_dec_and_test(&el->rc))       ...
> > -        call_rcu(&el->head, el_free);       delete_element
> > +        call_rcu(&el->head, el_free);       remove_element
> >      ...                                     spin_unlock(&list_lock);
> >  } 					    ...
> >  					    if (atomic_dec_and_test(&el->rc))
> > @@ -64,3 +64,60 @@ Sometimes, a reference to the element needs to be obtained in the
> >  update (write) stream.  In such cases, atomic_inc_not_zero() might be
> >  overkill, since we hold the update-side spinlock.  One might instead
> >  use atomic_inc() in such cases.
> > +
> > +It is not always convenient to deal with "FAIL" in the
> > +search_and_reference() code path.  In such cases, the
> > +atomic_dec_and_test() may be moved from delete() to el_free()
> > +as follows:
> > +
> > +1.					2.
> > +add()					search_and_reference()
> > +{					{
> > +    alloc_object			    rcu_read_lock();
> > +    ...					    search_for_element
> > +    atomic_set(&el->rc, 1);		    atomic_inc(&el->rc);
> > +    spin_lock(&list_lock);		    ...
> > +				
> > +    add_element				    rcu_read_unlock();
> > +    ...					}
> 
> indentation looks wrong in my mail client for the two lines above (for
> the 2. block).

Ah, the "+" characters offset the tab stops.  Looks OK in the actual
file when the patch is applied.  (Though it would not hurt to check.)

							Thanx, Paul

> Otherwise, it looks good to me,
> 
> Thanks,
> 
> Mathieu
> 
> 
> > +    spin_unlock(&list_lock);		4.
> > +}					delete()
> > +3.					{
> > +release_referenced()			    spin_lock(&list_lock);
> > +{					    ...
> > +    ...					    remove_element
> > +    if (atomic_dec_and_test(&el->rc))       spin_unlock(&list_lock);
> > +        kfree(el);			    ...
> > +    ...                                     call_rcu(&el->head, el_free);
> > +} 					    ...
> > +5.					}
> > +void el_free(struct rcu_head *rhp)
> > +{
> > +    release_referenced();
> > +}
> > +
> > +The key point is that the initial reference added by add() is not removed
> > +until after a grace period has elapsed following removal.  This means that
> > +search_and_reference() cannot find this element, which means that the value
> > +of el->rc cannot increase.  Thus, once it reaches zero, there are no
> > +readers that can or ever will be able to reference the element.  The
> > +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.
> > +
> > +In cases where delete() can sleep, synchronize_rcu() can be called from
> > +delete(), so that el_free() can be subsumed into delete as follows:
> > +
> > +4.
> > +delete()
> > +{
> > +    spin_lock(&list_lock);
> > +    ...
> > +    remove_element
> > +    spin_unlock(&list_lock);
> > +    ...
> > +    synchronize_rcu();
> > +    if (atomic_dec_and_test(&el->rc))
> > +    	kfree(el);
> > +    ...
> > +}
> > -- 
> > 1.7.8
> > 
> 
> -- 
> Mathieu Desnoyers
> Operating System Efficiency R&D Consultant
> EfficiOS Inc.
> http://www.efficios.com
>