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

[Paul E. McKenney]

On Sat, May 12, 2018 at 07:40:02AM -0700, Paul E. McKenney wrote:
> 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)))

Right...  Make that rnp->gp_seq.  Memory locality and all that...

							Thanx, Paul

> +			goto unlock_out;
>  		if (rnp_root != rnp && rnp_root->parent != NULL)
>  			raw_spin_unlock_rcu_node(rnp_root);
>  		if (!rnp_root->parent)