Re: [RFC PATCH 1/1] kernel/rcu/tree.c: correct a check for grace period in progress

["Paul E. McKenney" <paulmck@linux.vnet.ibm.com>]

On Tue, Jun 10, 2014 at 09:42:42PM -0700, Paul E. McKenney wrote:
> On Wed, Jun 11, 2014 at 12:23:57AM -0400, Pranith Kumar wrote:
> > Hi Paul,
> > 
> > On Wed, Jun 11, 2014 at 12:12 AM, Paul E. McKenney
> > <paulmck@linux.vnet.ibm.com> wrote:
> > >>       if (rnp->gpnum != rnp->completed ||
> > >> -         ACCESS_ONCE(rnp->gpnum) != ACCESS_ONCE(rnp->completed)) {
> > >> +         ACCESS_ONCE(rnp_root->gpnum) != ACCESS_ONCE(rnp_root->completed)) {
> > >
> > > At this point in the code, we are checking the current rcu_node structure,
> > > which might or might not be the root.  If it is not the root, we absolutely
> > > cannot compare against the root because we don't yet hold the root's lock.
> > >
> > 
> > I was a bit thrown by the double checking which is being done
> > (rnp->gpnum != rnp->complete) in that if condition. Once without
> > ACCESS_ONCE and one with. Is there any particular reason for this?
> > 
> > I now understand that we are comparing ->gpnum and ->completed of the
> > root node which might change from under us if we don't hold the root's
> > lock. I will keep looking :)
> 
> Hmmm...  Now that you mention it, that does look a bit strange.

And it turns out that you were right to begin with!  I queue your change,
but with a full explanation in the commit log and with some additions to
the comment.  Please see below.

							Thanx, Paul

------------------------------------------------------------------------

rcu: Check both root and current rcu_node when setting up future grace period

The rcu_start_future_gp() function checks the current rcu_node's ->gpnum
and ->completed twice, once without ACCESS_ONCE() and once with it.
Which is pointless because we hold that rcu_node's ->lock at that point.
The intent was to check the current rcu_node structure and the root
rcu_node structure, the latter locklessly with ACCESS_ONCE().  This
commit therefore makes that change.

The reason that it is safe to locklessly check the root rcu_nodes's
->gpnum and ->completed fields is that we hold the current rcu_node's
->lock, which constrains the root rcu_node's ability to change its
->gpnum and ->completed fields.  Of course, if there is a single rcu_node
structure, then rnp_root==rnp, and holding the lock prevents all changes.
If there is more than one rcu_node structure, then the code updates the
fields in the following order:

1.	Increment rnp_root->gpnum to start new grace period.
2.	Increment rnp->gpnum to initialize the current rcu_node,
    	continuing initialization for the new grace period.
3.	Increment rnp_root->completed to end the current grace period.
4.	Increment rnp->completed to continue cleaning up after the
    	old grace period.
    
So there are four possible combinations of relative values of these
four fields:

N   N   N   N:  RCU idle, new grace period must be initiated.
    		Although rnp_root->gpnum might be incremented immediately
    		after we check, that will just result in unnecessary work.
    		The grace period already started, and we try to start it.
    
N+1 N   N   N:  RCU grace period just started.  No further change is
    		possible because we hold rnp->lock, so the checks of
    		rnp_root->gpnum and rnp_root->completed are stable.
    		We know that our request for a future grace period will
    		be seen during grace-period cleanup.
    
N+1 N   N+1 N:  RCU grace period is ongoing.  Because rnp->gpnum is
    		different than rnp->completed, we won't even look at
    		rnp_root->gpnum and rnp_root->completed, so the possible
    		concurrent change to rnp_root->completed does not matter.
    		We know that our request for a future grace period will
    		be seen during grace-period cleanup, which cannot pass
    		this rcu_node because we hold its ->lock.
    
N+1 N+1 N+1 N:  RCU grace period has ended, but not yet been cleaned up.
    		Because rnp->gpnum is different than rnp->completed, we
    		won't look at rnp_root->gpnum and rnp_root->completed, so
    		the possible concurrent change to rnp_root->completed does
    		not matter.  We know that our request for a future grace
    		period will be seen during grace-period cleanup, which
    		cannot pass this rcu_node because we hold its ->lock.
    
Therefore, despite initial appearances, the lockless check is safe.

Signed-off-by: Pranith Kumar <bobby.prani@gmail.com>
[ paulmck: Update comment to say why the lockless check is safe. ]
Signed-off-by: Paul E. McKenney <paulmck@linux.vnet.ibm.com>

diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index b14ea3693b79..ebafb08f2b2a 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -1224,10 +1224,16 @@ rcu_start_future_gp(struct rcu_node *rnp, struct rcu_data *rdp,
 	 * believe that a grace period is in progress, then we must wait
 	 * for the one following, which is in "c".  Because our request
 	 * will be noticed at the end of the current grace period, we don't
-	 * need to explicitly start one.
+	 * need to explicitly start one.  We only do the lockless check
+	 * of rnp_root's fields if the current rcu_node structure thinks
+	 * there is no grace period in flight, and because we hold rnp->lock,
+	 * the only possible change is when rnp_root's two fields are
+	 * equal, in which case rnp_root->gpnum might be concurrently
+	 * incremented.  But that is OK, as it will just result in our
+	 * doing some extra useless work.
 	 */
 	if (rnp->gpnum != rnp->completed ||
-	    ACCESS_ONCE(rnp->gpnum) != ACCESS_ONCE(rnp->completed)) {
+	    ACCESS_ONCE(rnp_root->gpnum) != ACCESS_ONCE(rnp_root->completed)) {
 		rnp->need_future_gp[c & 0x1]++;
 		trace_rcu_future_gp(rnp, rdp, c, TPS("Startedleaf"));
 		goto out;