Re: [tip/core/rcu,16/21] rcu: Add funnel locking to rcu_start_this_gp()

[Paul E. McKenney]

On Fri, May 11, 2018 at 11:03:25PM -0700, Joel Fernandes wrote:
> On Sun, Apr 22, 2018 at 08:03:39PM -0700, Paul E. McKenney wrote:
> > The rcu_start_this_gp() function had a simple form of funnel locking that
> > used only the leaves and root of the rcu_node tree, which is fine for
> > systems with only a few hundred CPUs, but sub-optimal for systems having
> > thousands of CPUs.  This commit therefore adds full-tree funnel locking.
> > 
> > This variant of funnel locking is unusual in the following ways:
> > 
> > 1.	The leaf-level rcu_node structure's ->lock is held throughout.
> > 	Other funnel-locking implementations drop the leaf-level lock
> > 	before progressing to the next level of the tree.
> > 
> > 2.	Funnel locking can be started at the root, which is convenient
> > 	for code that already holds the root rcu_node structure's ->lock.
> > 	Other funnel-locking implementations start at the leaves.
> > 
> > 3.	If an rcu_node structure other than the initial one believes
> > 	that a grace period is in progress, it is not necessary to
> > 	go further up the tree.  This is because grace-period cleanup
> > 	scans the full tree, so that marking the need for a subsequent
> > 	grace period anywhere in the tree suffices -- but only if
> > 	a grace period is currently in progress.
> > 
> > 4.	It is possible that the RCU grace-period kthread has not yet
> > 	started, and this case must be handled appropriately.
> > 
> > However, the general approach of using a tree to control lock contention
> > is still in place.
> > 
> > Signed-off-by: Paul E. McKenney <paulmck@xxxxxxxxxxxxxxxxxx>
> > ---
> >  kernel/rcu/tree.c | 92 +++++++++++++++++++++----------------------------------
> >  1 file changed, 35 insertions(+), 57 deletions(-)
> > 
> > diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
> > index 94519c7d552f..d3c769502929 100644
> > --- a/kernel/rcu/tree.c
> > +++ b/kernel/rcu/tree.c
> > @@ -1682,74 +1682,52 @@ static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
> >  {
> >  	bool ret = false;
> >  	struct rcu_state *rsp = rdp->rsp;
> > -	struct rcu_node *rnp_root = rcu_get_root(rsp);
> > -
> > -	raw_lockdep_assert_held_rcu_node(rnp);
> > -
> > -	/* If the specified GP is already known needed, return to caller. */
> > -	trace_rcu_this_gp(rnp, rdp, c, TPS("Startleaf"));
> > -	if (need_future_gp_element(rnp, c)) {
> > -		trace_rcu_this_gp(rnp, rdp, c, TPS("Prestartleaf"));
> > -		goto out;
> > -	}
> > +	struct rcu_node *rnp_root;
> >  
> >  	/*
> > -	 * If this rcu_node structure believes 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.
> > +	 * Use funnel locking to either acquire the root rcu_node
> > +	 * structure's lock or bail out if the need for this grace period
> > +	 * has already been recorded -- or has already started.  If there
> > +	 * is already a grace period in progress in a non-leaf node, no
> > +	 * recording is needed because the end of the grace period will
> > +	 * scan the leaf rcu_node structures.  Note that rnp->lock must
> > +	 * not be released.
> >  	 */
> > -	if (rnp->gpnum != rnp->completed) {
> > -		need_future_gp_element(rnp, c) = true;
> > -		trace_rcu_this_gp(rnp, rdp, c, TPS("Startedleaf"));
> > -		goto out;
> 
> Referring to the above negative diff as [1] (which I wanted to refer to later
> in this message..)
> 
> > +	raw_lockdep_assert_held_rcu_node(rnp);
> > +	trace_rcu_this_gp(rnp, rdp, c, TPS("Startleaf"));
> > +	for (rnp_root = rnp; 1; rnp_root = rnp_root->parent) {
> > +		if (rnp_root != rnp)
> > +			raw_spin_lock_rcu_node(rnp_root);
> > +		if (need_future_gp_element(rnp_root, c) ||
> > +		    ULONG_CMP_GE(rnp_root->gpnum, c) ||
> > +		    (rnp != rnp_root &&
> > +		     rnp_root->gpnum != rnp_root->completed)) {
> > +			trace_rcu_this_gp(rnp_root, rdp, c, TPS("Prestarted"));
> > +			goto unlock_out;
> 
> I was a bit confused about the implementation of the above for loop:
> 
> In the previous code (which I refer to in the negative diff [1]), we were
> checking the leaf, and if the leaf believed that RCU was not idle, then we
> were marking the need for the future GP and quitting this function. In the
> new code, it seems like even if the leaf believes RCU is not-idle, we still
> go all the way up the tree.
> 
> I think the big change is, in the above new for loop, we either bail of if a
> future GP need was already marked by an intermediate node, or we go marking
> up the whole tree about the need for one.
> 
> If a leaf believes RCU is not idle, can we not just mark the future GP need
> like before and return? It seems we would otherwise increase the lock
> contention since now we lock intermediate nodes and then finally even the
> root. Where as before we were not doing that if the leaf believed RCU was not
> idle.
> 
> I am sorry if I missed something obvious.

The trick is that we do the check before we have done the marking.
So if we bailed, we would not have marked at all.  If we are at an
intermediate node and a grace period is in progress, we do bail.

You are right that this means that we (perhaps unnecessarily) acquire
the lock of the parent rcu_node, which might or might not be the root.
And on systems with default fanout with 1024 CPUs or fewer, yes, it will
be the root, and yes, this is the common case.  So might be well worth
improving.

One way to implement the old mark-and-return approach as you suggest
above would be as shown below (untested, probably doesn't build, and
against current rcu/dev).  What do you think?

> The other thing is we now don't have the 'Startedleaf' trace like we did
> before. I sent a patch to remove it, but I think the removal of that is
> somehow connected to what I was just talking about.. and I was thinking if we
> should really remove it. Should we add the case for checking leaves only back
> or is that a bad thing to do?

Suppose I got hit by a bus and you were stuck with the job of debugging
this.  What traces would you want and where would they be?  Keeping in
mind that too-frequent traces have their problems as well.

(Yes, I will be trying very hard to avoid this scenario for as long as
I can, but this might be a good way for you (and everyone else) to be
thinking about this.)

							Thanx, Paul

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

diff --git a/kernel/rcu/tree.c b/kernel/rcu/tree.c
index 1abe29a43944..abf3195e01dc 100644
--- a/kernel/rcu/tree.c
+++ b/kernel/rcu/tree.c
@@ -1585,6 +1585,8 @@ static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp,
 			goto unlock_out;
 		}
 		rnp_root->gp_seq_needed = c;
+		if (rcu_seq_state(rcu_seq_current(&rnp_root->gp_seq)))
+			goto unlock_out;
 		if (rnp_root != rnp && rnp_root->parent != NULL)
 			raw_spin_unlock_rcu_node(rnp_root);
 		if (!rnp_root->parent)