Contention reduction for v4.18

Currently, rcu_gp_cleanup() scans the rcu_node tree in order to reset state to reflect the end of the grace period. It also checks to see whether a new grace period is needed, but in a number of cases, rather than directly cause the new grace period to be immediately started, it instead leaves the grace-period-needed state where various fail-safes can find it. This works fine, but results in higher contention on the root rcu_node structure's ->lock, which is undesirable, and contention on that lock has recently become noticeable.

This commit therefore makes rcu_gp_cleanup() immediately start a new grace period if there is any need for one.

It is quite possible that it will later be necessary to throttle the grace-period rate, but that can be dealt with when and if.

Reported-by Nicholas Piggin <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

---
 kernel/rcu/tree.c        | 16 ++++++++++------
 kernel/rcu/tree.h        |  1 -
 kernel/rcu/tree_plugin.h | 17 -----------------
 3 files changed, 10 insertions(+), 24 deletions(-)

kernel/rcu/tree.c +4 -6

index 497f139056c7..afc5e32f0da4 100644
@@ -1763,14 +1763,14 @@ rcu_start_future_gp(struct rcu_node *rnp, struct rcu_data *rdp,
  * Clean up any old requests for the just-ended grace period.  Also return
  * whether any additional grace periods have been requested.
  */
-static int rcu_future_gp_cleanup(struct rcu_state *rsp, struct rcu_node *rnp)
+static bool rcu_future_gp_cleanup(struct rcu_state *rsp, struct rcu_node *rnp)
 {
 	int c = rnp->completed;
-	int needmore;
+	bool needmore;
 	struct rcu_data *rdp = this_cpu_ptr(rsp->rda);
 
 	need_future_gp_element(rnp, c) = 0;
-	needmore = need_future_gp_element(rnp, c + 1);
+	needmore = need_any_future_gp(rnp);
 	trace_rcu_future_gp(rnp, rdp, c,
 			    needmore ? TPS("CleanupMore") : TPS("Cleanup"));
 	return needmore;

@@ -2113,7 +2113,6 @@ static void rcu_gp_cleanup(struct rcu_state *rsp)
 {
 	unsigned long gp_duration;
 	bool needgp = false;
-	int nocb = 0;
 	struct rcu_data *rdp;
 	struct rcu_node *rnp = rcu_get_root(rsp);
 	struct swait_queue_head *sq;

@@ -2152,7 +2151,7 @@ static void rcu_gp_cleanup(struct rcu_state *rsp)
 		if (rnp == rdp->mynode)
 			needgp = __note_gp_changes(rsp, rnp, rdp) || needgp;
 		/* smp_mb() provided by prior unlock-lock pair. */
-		nocb += rcu_future_gp_cleanup(rsp, rnp);
+		needgp = rcu_future_gp_cleanup(rsp, rnp) || needgp;
 		sq = rcu_nocb_gp_get(rnp);
 		raw_spin_unlock_irq_rcu_node(rnp);
 		rcu_nocb_gp_cleanup(sq);

@@ -2162,13 +2161,18 @@ static void rcu_gp_cleanup(struct rcu_state *rsp)
 	}
 	rnp = rcu_get_root(rsp);
 	raw_spin_lock_irq_rcu_node(rnp); /* Order GP before ->completed update. */
-	rcu_nocb_gp_set(rnp, nocb);
 

Hi Paul,

Quoted 68 lines · Paul E. McKenney

Currently, rcu_gp_cleanup() scans the rcu_node tree in order to reset state to reflect the end of the grace period. It also checks to see whether a new grace period is needed, but in a number of cases, rather than directly cause the new grace period to be immediately started, it instead leaves the grace-period-needed state where various fail-safes can find it. This works fine, but results in higher contention on the root rcu_node structure's ->lock, which is undesirable, and contention on that lock has recently become noticeable.

This commit therefore makes rcu_gp_cleanup() immediately start a new grace period if there is any need for one.

It is quite possible that it will later be necessary to throttle the grace-period rate, but that can be dealt with when and if.

Reported-by Nicholas Piggin <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

---
 kernel/rcu/tree.c        | 16 ++++++++++------
 kernel/rcu/tree.h        |  1 -
 kernel/rcu/tree_plugin.h | 17 -----------------
 3 files changed, 10 insertions(+), 24 deletions(-)

kernel/rcu/tree.c +4 -6

index 497f139056c7..afc5e32f0da4 100644
@@ -1763,14 +1763,14 @@ rcu_start_future_gp(struct rcu_node *rnp, struct rcu_data *rdp,
  * Clean up any old requests for the just-ended grace period.  Also return
  * whether any additional grace periods have been requested.
  */
-static int rcu_future_gp_cleanup(struct rcu_state *rsp, struct rcu_node *rnp)
+static bool rcu_future_gp_cleanup(struct rcu_state *rsp, struct rcu_node *rnp)
 {
 	int c = rnp->completed;
-	int needmore;
+	bool needmore;
 	struct rcu_data *rdp = this_cpu_ptr(rsp->rda);
 
 	need_future_gp_element(rnp, c) = 0;
-	needmore = need_future_gp_element(rnp, c + 1);
+	needmore = need_any_future_gp(rnp);
 	trace_rcu_future_gp(rnp, rdp, c,
 			    needmore ? TPS("CleanupMore") : TPS("Cleanup"));
 	return needmore;

@@ -2113,7 +2113,6 @@ static void rcu_gp_cleanup(struct rcu_state *rsp)
 {
 	unsigned long gp_duration;
 	bool needgp = false;
-	int nocb = 0;
 	struct rcu_data *rdp;
 	struct rcu_node *rnp = rcu_get_root(rsp);
 	struct swait_queue_head *sq;

@@ -2152,7 +2151,7 @@ static void rcu_gp_cleanup(struct rcu_state *rsp)
 		if (rnp == rdp->mynode)
 			needgp = __note_gp_changes(rsp, rnp, rdp) || needgp;
 		/* smp_mb() provided by prior unlock-lock pair. */
-		nocb += rcu_future_gp_cleanup(rsp, rnp);
+		needgp = rcu_future_gp_cleanup(rsp, rnp) || needgp;
 		sq = rcu_nocb_gp_get(rnp);
 		raw_spin_unlock_irq_rcu_node(rnp);
 		rcu_nocb_gp_cleanup(sq);

@@ -2162,13 +2161,18 @@ static void rcu_gp_cleanup(struct rcu_state *rsp)
 	}
 	rnp = rcu_get_root(rsp);
 	raw_spin_lock_irq_rcu_node(rnp); /* Order GP before ->completed update. */
-	rcu_nocb_gp_set(rnp, nocb);
 

kernel/rcu/tree.c static void rcu_gp_cleanup(struct rcu_state *rsp) · line 2174

Quoted 10 lines

kernel/rcu/tree.c +5 -0

 	/* Declare grace period done. */
 	WRITE_ONCE(rsp->completed, rsp->gpnum);
 	trace_rcu_grace_period(rsp->name, rsp->completed, TPS("end"));
 	rsp->gp_state = RCU_GP_IDLE;
+	/* Check for GP requests since above loop. */
 	rdp = this_cpu_ptr(rsp->rda);
+	if (need_any_future_gp(rnp)) {
+		trace_rcu_future_gp(rnp, rdp, rsp->completed - 1,
+				    TPS("CleanupMore"));
+		needgp = true;

Patch makes sense to me.

I didn't get the "rsp->completed - 1" bit in the call to trace_rcu_future_gp. The grace period that just completed is in rsp->completed. The future one should be completed + 1. What is meaning of the third argument 'c' to the trace event?

Also in rcu_future_gp_cleanup, we call:

	trace_rcu_future_gp(rnp, rdp, c,
			    needmore ? TPS("CleanupMore") : TPS("Cleanup"));

For this case, in the final trace event record, rnp->completed and c will be the same, since c is set to rnp->completed before calling trace_rcu_future_gp. I was thinking they should be different, do you expect them to be the same?

Quoted 84 lines · Joel Fernandes

Hi Paul,

Quoted 68 lines · Paul E. McKenney

Currently, rcu_gp_cleanup() scans the rcu_node tree in order to reset state to reflect the end of the grace period. It also checks to see whether a new grace period is needed, but in a number of cases, rather than directly cause the new grace period to be immediately started, it instead leaves the grace-period-needed state where various fail-safes can find it. This works fine, but results in higher contention on the root rcu_node structure's ->lock, which is undesirable, and contention on that lock has recently become noticeable.

This commit therefore makes rcu_gp_cleanup() immediately start a new grace period if there is any need for one.

It is quite possible that it will later be necessary to throttle the grace-period rate, but that can be dealt with when and if.

Reported-by Nicholas Piggin <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

---
 kernel/rcu/tree.c        | 16 ++++++++++------
 kernel/rcu/tree.h        |  1 -
 kernel/rcu/tree_plugin.h | 17 -----------------
 3 files changed, 10 insertions(+), 24 deletions(-)

kernel/rcu/tree.c +4 -6

index 497f139056c7..afc5e32f0da4 100644
@@ -1763,14 +1763,14 @@ rcu_start_future_gp(struct rcu_node *rnp, struct rcu_data *rdp,
  * Clean up any old requests for the just-ended grace period.  Also return
  * whether any additional grace periods have been requested.
  */
-static int rcu_future_gp_cleanup(struct rcu_state *rsp, struct rcu_node *rnp)
+static bool rcu_future_gp_cleanup(struct rcu_state *rsp, struct rcu_node *rnp)
 {
 	int c = rnp->completed;
-	int needmore;
+	bool needmore;
 	struct rcu_data *rdp = this_cpu_ptr(rsp->rda);
 
 	need_future_gp_element(rnp, c) = 0;
-	needmore = need_future_gp_element(rnp, c + 1);
+	needmore = need_any_future_gp(rnp);
 	trace_rcu_future_gp(rnp, rdp, c,
 			    needmore ? TPS("CleanupMore") : TPS("Cleanup"));
 	return needmore;

@@ -2113,7 +2113,6 @@ static void rcu_gp_cleanup(struct rcu_state *rsp)
 {
 	unsigned long gp_duration;
 	bool needgp = false;
-	int nocb = 0;
 	struct rcu_data *rdp;
 	struct rcu_node *rnp = rcu_get_root(rsp);
 	struct swait_queue_head *sq;

@@ -2152,7 +2151,7 @@ static void rcu_gp_cleanup(struct rcu_state *rsp)
 		if (rnp == rdp->mynode)
 			needgp = __note_gp_changes(rsp, rnp, rdp) || needgp;
 		/* smp_mb() provided by prior unlock-lock pair. */
-		nocb += rcu_future_gp_cleanup(rsp, rnp);
+		needgp = rcu_future_gp_cleanup(rsp, rnp) || needgp;
 		sq = rcu_nocb_gp_get(rnp);
 		raw_spin_unlock_irq_rcu_node(rnp);
 		rcu_nocb_gp_cleanup(sq);

@@ -2162,13 +2161,18 @@ static void rcu_gp_cleanup(struct rcu_state *rsp)
 	}
 	rnp = rcu_get_root(rsp);
 	raw_spin_lock_irq_rcu_node(rnp); /* Order GP before ->completed update. */
-	rcu_nocb_gp_set(rnp, nocb);
 

kernel/rcu/tree.c static void rcu_gp_cleanup(struct rcu_state *rsp) · line 2174

Quoted 10 lines

kernel/rcu/tree.c +5 -0

 	/* Declare grace period done. */
 	WRITE_ONCE(rsp->completed, rsp->gpnum);
 	trace_rcu_grace_period(rsp->name, rsp->completed, TPS("end"));
 	rsp->gp_state = RCU_GP_IDLE;
+	/* Check for GP requests since above loop. */
 	rdp = this_cpu_ptr(rsp->rda);
+	if (need_any_future_gp(rnp)) {
+		trace_rcu_future_gp(rnp, rdp, rsp->completed - 1,
+				    TPS("CleanupMore"));
+		needgp = true;

Patch makes sense to me.

Quoted 4 lines

I didn't get the "rsp->completed - 1" bit in the call to trace_rcu_future_gp. The grace period that just completed is in rsp->completed. The future one should be completed + 1. What is meaning of the third argument 'c' to the trace event?

The thought was that the grace period must have been requested while rsp->completed was one less than it is now.

In the current code, it uses rnp->gp_seq_needed, which is instead the grace period that is being requested.

Quoted 7 lines

Also in rcu_future_gp_cleanup, we call:

	trace_rcu_future_gp(rnp, rdp, c,
			    needmore ? TPS("CleanupMore") : TPS("Cleanup"));

For this case, in the final trace event record, rnp->completed and c will be the same, since c is set to rnp->completed before calling trace_rcu_future_gp. I was thinking they should be different, do you expect them to be the same?

Hmmm... That does look a bit inconsistent. And it currently uses rnp->gp_seq instead of rnp->gp_seq_needed despite having the same "CleanupMore" name.

Looks like a review of the calls to trace_rcu_this_gp() is in order.

Or did you have suggestions for name/gp assocations for this trace message type?

Quoted 7 lines

Also in rcu_future_gp_cleanup, we call:

	trace_rcu_future_gp(rnp, rdp, c,
			    needmore ? TPS("CleanupMore") : TPS("Cleanup"));

For this case, in the final trace event record, rnp->completed and c will be the same, since c is set to rnp->completed before calling trace_rcu_future_gp. I was thinking they should be different, do you expect them to be the same?

Hmmm... That does look a bit inconsistent. And it currently uses rnp->gp_seq instead of rnp->gp_seq_needed despite having the same "CleanupMore" name.

Looks like a review of the calls to trace_rcu_this_gp() is in order.

Quoted 90 lines · Paul E. McKenney

Quoted 84 lines · Joel Fernandes

Hi Paul,

Quoted 68 lines · Paul E. McKenney

Currently, rcu_gp_cleanup() scans the rcu_node tree in order to reset state to reflect the end of the grace period. It also checks to see whether a new grace period is needed, but in a number of cases, rather than directly cause the new grace period to be immediately started, it instead leaves the grace-period-needed state where various fail-safes can find it. This works fine, but results in higher contention on the root rcu_node structure's ->lock, which is undesirable, and contention on that lock has recently become noticeable.

This commit therefore makes rcu_gp_cleanup() immediately start a new grace period if there is any need for one.

It is quite possible that it will later be necessary to throttle the grace-period rate, but that can be dealt with when and if.

Reported-by Nicholas Piggin <[email protected]>

Signed-off-by Paul E. McKenney <[email protected]>

---
 kernel/rcu/tree.c        | 16 ++++++++++------
 kernel/rcu/tree.h        |  1 -
 kernel/rcu/tree_plugin.h | 17 -----------------
 3 files changed, 10 insertions(+), 24 deletions(-)

kernel/rcu/tree.c +4 -6

index 497f139056c7..afc5e32f0da4 100644
@@ -1763,14 +1763,14 @@ rcu_start_future_gp(struct rcu_node *rnp, struct rcu_data *rdp,
  * Clean up any old requests for the just-ended grace period.  Also return
  * whether any additional grace periods have been requested.
  */
-static int rcu_future_gp_cleanup(struct rcu_state *rsp, struct rcu_node *rnp)
+static bool rcu_future_gp_cleanup(struct rcu_state *rsp, struct rcu_node *rnp)
 {
 	int c = rnp->completed;
-	int needmore;
+	bool needmore;
 	struct rcu_data *rdp = this_cpu_ptr(rsp->rda);
 
 	need_future_gp_element(rnp, c) = 0;
-	needmore = need_future_gp_element(rnp, c + 1);
+	needmore = need_any_future_gp(rnp);
 	trace_rcu_future_gp(rnp, rdp, c,
 			    needmore ? TPS("CleanupMore") : TPS("Cleanup"));
 	return needmore;

@@ -2113,7 +2113,6 @@ static void rcu_gp_cleanup(struct rcu_state *rsp)
 {
 	unsigned long gp_duration;
 	bool needgp = false;
-	int nocb = 0;
 	struct rcu_data *rdp;
 	struct rcu_node *rnp = rcu_get_root(rsp);
 	struct swait_queue_head *sq;

@@ -2152,7 +2151,7 @@ static void rcu_gp_cleanup(struct rcu_state *rsp)
 		if (rnp == rdp->mynode)
 			needgp = __note_gp_changes(rsp, rnp, rdp) || needgp;
 		/* smp_mb() provided by prior unlock-lock pair. */
-		nocb += rcu_future_gp_cleanup(rsp, rnp);
+		needgp = rcu_future_gp_cleanup(rsp, rnp) || needgp;
 		sq = rcu_nocb_gp_get(rnp);
 		raw_spin_unlock_irq_rcu_node(rnp);
 		rcu_nocb_gp_cleanup(sq);

@@ -2162,13 +2161,18 @@ static void rcu_gp_cleanup(struct rcu_state *rsp)
 	}
 	rnp = rcu_get_root(rsp);
 	raw_spin_lock_irq_rcu_node(rnp); /* Order GP before ->completed update. */
-	rcu_nocb_gp_set(rnp, nocb);
 

kernel/rcu/tree.c static void rcu_gp_cleanup(struct rcu_state *rsp) · line 2174

Quoted 10 lines

kernel/rcu/tree.c +5 -0

 	/* Declare grace period done. */
 	WRITE_ONCE(rsp->completed, rsp->gpnum);
 	trace_rcu_grace_period(rsp->name, rsp->completed, TPS("end"));
 	rsp->gp_state = RCU_GP_IDLE;
+	/* Check for GP requests since above loop. */
 	rdp = this_cpu_ptr(rsp->rda);
+	if (need_any_future_gp(rnp)) {
+		trace_rcu_future_gp(rnp, rdp, rsp->completed - 1,
+				    TPS("CleanupMore"));
+		needgp = true;

Patch makes sense to me.

Quoted 4 lines

I didn't get the "rsp->completed - 1" bit in the call to trace_rcu_future_gp. The grace period that just completed is in rsp->completed. The future one should be completed + 1. What is meaning of the third argument 'c' to the trace event?

Quoted 5 lines

The thought was that the grace period must have been requested while rsp->completed was one less than it is now.

In the current code, it uses rnp->gp_seq_needed, which is instead the grace period that is being requested.

Oh ok, IIUC from the code, the 'c' parameter passed to trace_rcu_future_gp is the grace-period number in the future. Perhaps we should clarify this in the include/trace/events/rcu.h code what this parameter means. Probably 'future_gp' or something like that.

Quoted 11 lines

Quoted 7 lines

Also in rcu_future_gp_cleanup, we call:

	trace_rcu_future_gp(rnp, rdp, c,
			    needmore ? TPS("CleanupMore") : TPS("Cleanup"));

For this case, in the final trace event record, rnp->completed and c will be the same, since c is set to rnp->completed before calling trace_rcu_future_gp. I was thinking they should be different, do you expect them to be the same?

Hmmm... That does look a bit inconsistent. And it currently uses rnp->gp_seq instead of rnp->gp_seq_needed despite having the same "CleanupMore" name.

Yes I was thinking in rcu_future_gp_cleanup, the call to trace_rcu_future_gp should be trace_rcu_future_gp(rnp, rdp, c + 1, needmore...);

This is because in rcu_future_gp_cleanup, c is set to rnp->completed. Just before this point rnp->completed was set to rsp->gpnum, which marks the end of the GP for the node. The next gp would be c + 1 right?

Quoted 1 line

Looks like a review of the calls to trace_rcu_this_gp() is in order.

Yes, I'll do some tracing and see if something else doesn't make sense to me and let you know.

Quoted 2 lines

Or did you have suggestions for name/gp assocations for this trace message type?

I think the name for this one is fine but also that "CleanupMore" sounds like more clean up is needed. It could be improved to "CleanupNeedgp" or "CleanupAndStart" or something like that.

On Thu, May 10, 2018 at 06:15:46AM -0700, Paul E. McKenney wrote:
[...]

Quoted 12 lines

Quoted 7 lines

Also in rcu_future_gp_cleanup, we call:

	trace_rcu_future_gp(rnp, rdp, c,
			    needmore ? TPS("CleanupMore") : TPS("Cleanup"));

For this case, in the final trace event record, rnp->completed and c will be the same, since c is set to rnp->completed before calling trace_rcu_future_gp. I was thinking they should be different, do you expect them to be the same?

Hmmm... That does look a bit inconsistent. And it currently uses rnp->gp_seq instead of rnp->gp_seq_needed despite having the same "CleanupMore" name.

Quoted 1 line

Looks like a review of the calls to trace_rcu_this_gp() is in order.

I see you changed trace_rcu_future_gp to use trace_rcu_this_gp in 15/21.. I am not sure if the concern is still valid then since you seem to be correctly getting the future GP in those cases, except for the naming which I suggest be changed from 'c' to 'future_gp' just for clarity / self-documenting code.

Quoted 16 lines · Joel Fernandes

On Thu, May 10, 2018 at 06:15:46AM -0700, Paul E. McKenney wrote:
[...]

Quoted 13 lines

Quoted 7 lines

Also in rcu_future_gp_cleanup, we call:

	trace_rcu_future_gp(rnp, rdp, c,
			    needmore ? TPS("CleanupMore") : TPS("Cleanup"));

For this case, in the final trace event record, rnp->completed and c will be the same, since c is set to rnp->completed before calling trace_rcu_future_gp. I was thinking they should be different, do you expect them to be the same?

Hmmm... That does look a bit inconsistent. And it currently uses rnp->gp_seq instead of rnp->gp_seq_needed despite having the same "CleanupMore" name.

Looks like a review of the calls to trace_rcu_this_gp() is in order.

Quoted 4 lines

I see you changed trace_rcu_future_gp to use trace_rcu_this_gp in 15/21.. I am not sure if the concern is still valid then since you seem to be correctly getting the future GP in those cases, except for the naming which I suggest be changed from 'c' to 'future_gp' just for clarity / self-documenting code.

Indeed, "c" for "->completed" is completely outdated. ;-)

Would you be willing to send a patch providing a better name?

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 <[email protected]>

---
 kernel/rcu/tree.c | 92 +++++++++++++++++++++----------------------------------
 1 file changed, 35 insertions(+), 57 deletions(-)

kernel/rcu/tree.c +3 -14

index 94519c7d552f..d3c769502929 100644
@@ -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

kernel/rcu/tree.c +6 -0

+		}
+		need_future_gp_element(rnp_root, c) = true;
+		if (rnp_root != rnp && rnp_root->parent != NULL)
+			raw_spin_unlock_rcu_node(rnp_root);
+		if (!rnp_root->parent)
+			break;  /* At root, and perhaps also leaf. */
 	}
 

Quoted 60 lines · Paul E. McKenney

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 <[email protected]>

---
 kernel/rcu/tree.c | 92 +++++++++++++++++++++----------------------------------
 1 file changed, 35 insertions(+), 57 deletions(-)

kernel/rcu/tree.c +3 -14

index 94519c7d552f..d3c769502929 100644
@@ -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

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1705

Quoted 10 lines

kernel/rcu/tree.c +5 -4

+	 * 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..)

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1706

Quoted 11 lines

kernel/rcu/tree.c +11 -0

+	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 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?

Quoted 99 lines · Joel Fernandes

Quoted 60 lines · Paul E. McKenney

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 <[email protected]>

---
 kernel/rcu/tree.c | 92 +++++++++++++++++++++----------------------------------
 1 file changed, 35 insertions(+), 57 deletions(-)

kernel/rcu/tree.c +3 -14

index 94519c7d552f..d3c769502929 100644
@@ -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

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1705

Quoted 10 lines

kernel/rcu/tree.c +5 -4

+	 * 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..)

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1706

Quoted 11 lines

kernel/rcu/tree.c +11 -0

+	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.

Quoted 7 lines

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?

Quoted 5 lines

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

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

kernel/rcu/tree.c +0 -0

index 1abe29a43944..abf3195e01dc 100644

kernel/rcu/tree.c +1 -0

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

Quoted 140 lines · Paul E. McKenney

Quoted 99 lines · Joel Fernandes

Quoted 60 lines · Paul E. McKenney

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 <[email protected]>

---
 kernel/rcu/tree.c | 92 +++++++++++++++++++++----------------------------------
 1 file changed, 35 insertions(+), 57 deletions(-)

kernel/rcu/tree.c +3 -14

index 94519c7d552f..d3c769502929 100644
@@ -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

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1705

Quoted 10 lines

kernel/rcu/tree.c +5 -4

+	 * 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..)

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1706

Quoted 11 lines

kernel/rcu/tree.c +11 -0

+	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.

Quoted 7 lines

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?

Quoted 5 lines

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

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

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1587

Quoted 8 lines

kernel/rcu/tree.c +0 -0

index 1abe29a43944..abf3195e01dc 100644
@@ -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;

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1589

Quoted 2 lines

kernel/rcu/tree.c +2 -0

+		if (rcu_seq_statn(rcu_seq_current(&rnp_root->gp_seq)))
+		if (rcu_seq_state(rcu_seq_current(&rnp_root->gp_seq)))

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

Thanx, Paul

Quoted 141 lines · Paul E. McKenney

Quoted 140 lines · Paul E. McKenney

Quoted 99 lines · Joel Fernandes

Quoted 60 lines · Paul E. McKenney

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 <[email protected]>

---
 kernel/rcu/tree.c | 92 +++++++++++++++++++++----------------------------------
 1 file changed, 35 insertions(+), 57 deletions(-)

kernel/rcu/tree.c +3 -14

index 94519c7d552f..d3c769502929 100644
@@ -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

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1705

Quoted 10 lines

kernel/rcu/tree.c +5 -4

+	 * 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..)

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1706

Quoted 11 lines

kernel/rcu/tree.c +11 -0

+	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.

Quoted 7 lines

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?

Quoted 5 lines

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

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

Quoted 8 lines

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1587

Quoted 8 lines

kernel/rcu/tree.c +0 -0

index 1abe29a43944..abf3195e01dc 100644
@@ -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;

e

Quoted 5 lines

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1589

Quoted 2 lines

kernel/rcu/tree.c +2 -0

+		if (rcu_seq_statn(rcu_seq_current(&rnp_root->gp_seq)))
+		if (rcu_seq_state(rcu_seq_current(&rnp_root->gp_seq)))

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

Thanx, Paul

Yes, I think this condition would be right to add. I could roll it into my clean up patch.

Also, I think its better if we split the conditions for prestarted into separate if conditions and comment them so its clear, I have started to do that in my tree.

If you don't mind going through the if conditions in the funnel locking loop with me, it would be quite helpful so that I don't mess the code up and would also help me add tracing correctly.

The if condition for prestarted is this:

               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;
		need_future_gp_element(rnp_root, c) = true;

As of 16/21, the heart of the loop is the above (excluding the locking bits)

In this what confuses me is the second and the third condition for pre-started.

The second condition is: ULONG_CMP_GE(rnp_root->gpnum, c). AIUI the goal of this condition is to check whether the requested grace period has already started. I believe then the above check is insufficient. The reason I think its insufficient is I believe we should also check the state of the grace period to augment this check.
IMO the condition should really be:
(ULONG_CMP_GT(rnp_root->gpnum, c) ||

  (rnp_root->gpnum == c && rnp_root->gpnum != rnp_root->completed))

In a later patch you replaced this with rseq_done(&rnp_root->gp_seq, c) which kind of accounts for the state, except that rseq_done uses ULONG_CMP_GE, whereas to fix this, rseq_done IMO should be using ULONG_CMP_GT to be equivalent to the above check. Do you agree?

The third condition for pre-started is:

                   (rnp != rnp_root && rnp_root->gpnum != rnp_root->completed))

This as I followed from your commit message is if an intermediate node thinks RCU is non-idle, then its not necessary to mark the tree and we can bail out since the clean up will scan the whole tree anyway. That makes sense to me but I think I will like to squash the diff in your previous email into this condition as well to handle both conditions together.

Quoted 155 lines · Joel Fernandes

Quoted 141 lines · Paul E. McKenney

Quoted 140 lines · Paul E. McKenney

Quoted 99 lines · Joel Fernandes

Quoted 60 lines · Paul E. McKenney

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 <[email protected]>

---
 kernel/rcu/tree.c | 92 +++++++++++++++++++++----------------------------------
 1 file changed, 35 insertions(+), 57 deletions(-)

kernel/rcu/tree.c +3 -14

index 94519c7d552f..d3c769502929 100644
@@ -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

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1705

Quoted 10 lines

kernel/rcu/tree.c +5 -4

+	 * 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..)

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1706

Quoted 11 lines

kernel/rcu/tree.c +11 -0

+	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.

Quoted 7 lines

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?

Quoted 5 lines

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

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

Quoted 8 lines

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1587

Quoted 8 lines

kernel/rcu/tree.c +0 -0

index 1abe29a43944..abf3195e01dc 100644
@@ -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;

e

Quoted 4 lines

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1589

Quoted 2 lines

kernel/rcu/tree.c +2 -0

+		if (rcu_seq_statn(rcu_seq_current(&rnp_root->gp_seq)))
+		if (rcu_seq_state(rcu_seq_current(&rnp_root->gp_seq)))

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

Quoted 4 lines

Quoted 1 line

Thanx, Paul

Yes, I think this condition would be right to add. I could roll it into my clean up patch.

I already queued it, please see below.

Quoted 3 lines

Also, I think its better if we split the conditions for prestarted into separate if conditions and comment them so its clear, I have started to do that in my tree.

Hmmm... Let's see how this plays out.

Quoted 19 lines

If you don't mind going through the if conditions in the funnel locking loop with me, it would be quite helpful so that I don't mess the code up and would also help me add tracing correctly.

The if condition for prestarted is this:

               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;
		need_future_gp_element(rnp_root, c) = true;

As of 16/21, the heart of the loop is the above (excluding the locking bits)

In this what confuses me is the second and the third condition for pre-started.

Quoted 7 lines

The second condition is: ULONG_CMP_GE(rnp_root->gpnum, c). AIUI the goal of this condition is to check whether the requested grace period has already started. I believe then the above check is insufficient. The reason I think its insufficient is I believe we should also check the state of the grace period to augment this check.
IMO the condition should really be:
(ULONG_CMP_GT(rnp_root->gpnum, c) ||

The above asks whether the -next- grace period -after- the requested one had started.

Quoted 1 line

  (rnp_root->gpnum == c && rnp_root->gpnum != rnp_root->completed))

This asks that the requested grace period not have completed.

What about the case where the requested grace period has completed, but the one after has not yet started? If you add that in, I bet you will have something that simplifies to my original.

Quoted 4 lines

In a later patch you replaced this with rseq_done(&rnp_root->gp_seq, c) which kind of accounts for the state, except that rseq_done uses ULONG_CMP_GE, whereas to fix this, rseq_done IMO should be using ULONG_CMP_GT to be equivalent to the above check. Do you agree?

I do not believe that I do. The ULONG_CMP_GE() allows for the missing case where the requested grace period completed, but the following grace period has not yet started.

Quoted 8 lines

The third condition for pre-started is:

                   (rnp != rnp_root && rnp_root->gpnum != rnp_root->completed))

This as I followed from your commit message is if an intermediate node thinks RCU is non-idle, then its not necessary to mark the tree and we can bail out since the clean up will scan the whole tree anyway. That makes sense to me but I think I will like to squash the diff in your previous email into this condition as well to handle both conditions together.

Please keep in mind that it is necessary to actually record the request in the leaf case. Or are you advocating use of ?: or similar to make this happen?

Quoted 156 lines · Paul E. McKenney

Quoted 155 lines · Joel Fernandes

Quoted 141 lines · Paul E. McKenney

Quoted 140 lines · Paul E. McKenney

Quoted 99 lines · Joel Fernandes

Quoted 60 lines · Paul E. McKenney

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 <[email protected]>

---
 kernel/rcu/tree.c | 92 +++++++++++++++++++++----------------------------------
 1 file changed, 35 insertions(+), 57 deletions(-)

kernel/rcu/tree.c +3 -14

index 94519c7d552f..d3c769502929 100644
@@ -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

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1705

Quoted 10 lines

kernel/rcu/tree.c +5 -4

+	 * 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..)

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1706

Quoted 11 lines

kernel/rcu/tree.c +11 -0

+	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.

Quoted 7 lines

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?

Quoted 5 lines

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

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

Quoted 8 lines

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1587

Quoted 8 lines

kernel/rcu/tree.c +0 -0

index 1abe29a43944..abf3195e01dc 100644
@@ -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;

e

Quoted 4 lines

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1589

Quoted 2 lines

kernel/rcu/tree.c +2 -0

+		if (rcu_seq_statn(rcu_seq_current(&rnp_root->gp_seq)))
+		if (rcu_seq_state(rcu_seq_current(&rnp_root->gp_seq)))

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

Quoted 6 lines

Quoted 4 lines

Quoted 1 line

Thanx, Paul

Yes, I think this condition would be right to add. I could roll it into my clean up patch.

I already queued it, please see below.

Cool!

Quoted 6 lines

Quoted 3 lines

Also, I think its better if we split the conditions for prestarted into separate if conditions and comment them so its clear, I have started to do that in my tree.

Hmmm... Let's see how this plays out.

Sure.

Quoted 38 lines

Quoted 19 lines

If you don't mind going through the if conditions in the funnel locking loop with me, it would be quite helpful so that I don't mess the code up and would also help me add tracing correctly.

The if condition for prestarted is this:

               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;
		need_future_gp_element(rnp_root, c) = true;

As of 16/21, the heart of the loop is the above (excluding the locking bits)

In this what confuses me is the second and the third condition for pre-started.

Quoted 7 lines

The second condition is: ULONG_CMP_GE(rnp_root->gpnum, c). AIUI the goal of this condition is to check whether the requested grace period has already started. I believe then the above check is insufficient. The reason I think its insufficient is I believe we should also check the state of the grace period to augment this check.
IMO the condition should really be:
(ULONG_CMP_GT(rnp_root->gpnum, c) ||

The above asks whether the -next- grace period -after- the requested one had started.

Quoted 1 line

  (rnp_root->gpnum == c && rnp_root->gpnum != rnp_root->completed))

This asks that the requested grace period not have completed.

What about the case where the requested grace period has completed, but the one after has not yet started? If you add that in, I bet you will have something that simplifies to my original.

Quoted 8 lines

Quoted 4 lines

In a later patch you replaced this with rseq_done(&rnp_root->gp_seq, c) which kind of accounts for the state, except that rseq_done uses ULONG_CMP_GE, whereas to fix this, rseq_done IMO should be using ULONG_CMP_GT to be equivalent to the above check. Do you agree?

I do not believe that I do. The ULONG_CMP_GE() allows for the missing case where the requested grace period completed, but the following grace period has not yet started.

Ok thanks that clears it up. For some reason I was thinking if rnp_root->gpnum == c, that could means 'c' has not yet started, unless we also checked the state. Obviously, now I realize gpnum == c can only mean 2 things:
- c has started but not yet completed
- c has completed

Both of these cases should cause a bail out so I agree now with your condition ULONG_CMP_GE, thanks.

Quoted 9 lines

Quoted 8 lines

The third condition for pre-started is:

                   (rnp != rnp_root && rnp_root->gpnum != rnp_root->completed))

This as I followed from your commit message is if an intermediate node thinks RCU is non-idle, then its not necessary to mark the tree and we can bail out since the clean up will scan the whole tree anyway. That makes sense to me but I think I will like to squash the diff in your previous email into this condition as well to handle both conditions together.

Quoted 3 lines

Please keep in mind that it is necessary to actually record the request in the leaf case. Or are you advocating use of ?: or similar to make this happen?

Yes, I realized yesterday you wanted to record it for the leaf that's why you're doing things this way. I'll let you know if I find any other ways of simplifying it once I look at your latest tree.

Btw, I checked your git tree and couldn't see the update that you mentioned you queued above. Could you push those changes?

Quoted 249 lines · Joel Fernandes

Quoted 156 lines · Paul E. McKenney

Quoted 155 lines · Joel Fernandes

Quoted 141 lines · Paul E. McKenney

Quoted 140 lines · Paul E. McKenney

Quoted 99 lines · Joel Fernandes

Quoted 60 lines · Paul E. McKenney

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 <[email protected]>

---
 kernel/rcu/tree.c | 92 +++++++++++++++++++++----------------------------------
 1 file changed, 35 insertions(+), 57 deletions(-)

kernel/rcu/tree.c +3 -14

index 94519c7d552f..d3c769502929 100644
@@ -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

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1705

Quoted 10 lines

kernel/rcu/tree.c +5 -4

+	 * 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..)

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1706

Quoted 11 lines

kernel/rcu/tree.c +11 -0

+	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.

Quoted 7 lines

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?

Quoted 5 lines

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

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

Quoted 8 lines

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1587

Quoted 8 lines

kernel/rcu/tree.c +0 -0

index 1abe29a43944..abf3195e01dc 100644
@@ -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;

e

Quoted 4 lines

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1589

Quoted 2 lines

kernel/rcu/tree.c +2 -0

+		if (rcu_seq_statn(rcu_seq_current(&rnp_root->gp_seq)))
+		if (rcu_seq_state(rcu_seq_current(&rnp_root->gp_seq)))

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

Quoted 6 lines

Quoted 4 lines

Quoted 1 line

Thanx, Paul

Yes, I think this condition would be right to add. I could roll it into my clean up patch.

I already queued it, please see below.

Cool!

Quoted 6 lines

Quoted 3 lines

Also, I think its better if we split the conditions for prestarted into separate if conditions and comment them so its clear, I have started to do that in my tree.

Hmmm... Let's see how this plays out.

Sure.

Quoted 38 lines

Quoted 19 lines

If you don't mind going through the if conditions in the funnel locking loop with me, it would be quite helpful so that I don't mess the code up and would also help me add tracing correctly.

The if condition for prestarted is this:

               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;
		need_future_gp_element(rnp_root, c) = true;

As of 16/21, the heart of the loop is the above (excluding the locking bits)

In this what confuses me is the second and the third condition for pre-started.

Quoted 7 lines

The second condition is: ULONG_CMP_GE(rnp_root->gpnum, c). AIUI the goal of this condition is to check whether the requested grace period has already started. I believe then the above check is insufficient. The reason I think its insufficient is I believe we should also check the state of the grace period to augment this check.
IMO the condition should really be:
(ULONG_CMP_GT(rnp_root->gpnum, c) ||

The above asks whether the -next- grace period -after- the requested one had started.

Quoted 1 line

  (rnp_root->gpnum == c && rnp_root->gpnum != rnp_root->completed))

This asks that the requested grace period not have completed.

What about the case where the requested grace period has completed, but the one after has not yet started? If you add that in, I bet you will have something that simplifies to my original.

Quoted 8 lines

Quoted 4 lines

In a later patch you replaced this with rseq_done(&rnp_root->gp_seq, c) which kind of accounts for the state, except that rseq_done uses ULONG_CMP_GE, whereas to fix this, rseq_done IMO should be using ULONG_CMP_GT to be equivalent to the above check. Do you agree?

I do not believe that I do. The ULONG_CMP_GE() allows for the missing case where the requested grace period completed, but the following grace period has not yet started.

Ok thanks that clears it up. For some reason I was thinking if rnp_root->gpnum == c, that could means 'c' has not yet started, unless we also checked the state. Obviously, now I realize gpnum == c can only mean 2 things:
- c has started but not yet completed
- c has completed

Both of these cases should cause a bail out so I agree now with your condition ULONG_CMP_GE, thanks.

Quoted 9 lines

Quoted 8 lines

The third condition for pre-started is:

                   (rnp != rnp_root && rnp_root->gpnum != rnp_root->completed))

This as I followed from your commit message is if an intermediate node thinks RCU is non-idle, then its not necessary to mark the tree and we can bail out since the clean up will scan the whole tree anyway. That makes sense to me but I think I will like to squash the diff in your previous email into this condition as well to handle both conditions together.

Quoted 3 lines

Please keep in mind that it is necessary to actually record the request in the leaf case. Or are you advocating use of ?: or similar to make this happen?

Yes, I realized yesterday you wanted to record it for the leaf that's why you're doing things this way. I'll let you know if I find any other ways of simplifying it once I look at your latest tree.

Quoted 2 lines

Btw, I checked your git tree and couldn't see the update that you mentioned you queued above. Could you push those changes?

Good point, pushed now. And the patch that I forgot to include in the last email is below.

Quoted 253 lines · Paul E. McKenney

Quoted 251 lines · Joel Fernandes

Quoted 156 lines · Paul E. McKenney

Quoted 155 lines · Joel Fernandes

Quoted 141 lines · Paul E. McKenney

Quoted 140 lines · Paul E. McKenney

Quoted 99 lines · Joel Fernandes

Quoted 60 lines · Paul E. McKenney

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 <[email protected]>

---
 kernel/rcu/tree.c | 92 +++++++++++++++++++++----------------------------------
 1 file changed, 35 insertions(+), 57 deletions(-)

kernel/rcu/tree.c +3 -14

index 94519c7d552f..d3c769502929 100644
@@ -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

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1705

Quoted 10 lines

kernel/rcu/tree.c +5 -4

+	 * 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..)

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1706

Quoted 11 lines

kernel/rcu/tree.c +11 -0

+	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.

Quoted 7 lines

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?

Quoted 5 lines

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

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

Quoted 8 lines

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1587

Quoted 8 lines

kernel/rcu/tree.c +0 -0

index 1abe29a43944..abf3195e01dc 100644
@@ -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;

e

Quoted 4 lines

kernel/rcu/tree.c static bool rcu_start_this_gp(struct rcu_node *rnp, struct rcu_data *rdp, · line 1589

Quoted 2 lines

kernel/rcu/tree.c +2 -0

+		if (rcu_seq_statn(rcu_seq_current(&rnp_root->gp_seq)))
+		if (rcu_seq_state(rcu_seq_current(&rnp_root->gp_seq)))

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

Quoted 6 lines

Quoted 4 lines

Quoted 1 line

Thanx, Paul

Yes, I think this condition would be right to add. I could roll it into my clean up patch.

I already queued it, please see below.

Cool!

Quoted 6 lines

Quoted 3 lines

Also, I think its better if we split the conditions for prestarted into separate if conditions and comment them so its clear, I have started to do that in my tree.

Hmmm... Let's see how this plays out.

Sure.

Quoted 38 lines

Quoted 19 lines

If you don't mind going through the if conditions in the funnel locking loop with me, it would be quite helpful so that I don't mess the code up and would also help me add tracing correctly.

The if condition for prestarted is this:

               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;
		need_future_gp_element(rnp_root, c) = true;

As of 16/21, the heart of the loop is the above (excluding the locking bits)

In this what confuses me is the second and the third condition for pre-started.

Quoted 7 lines

The second condition is: ULONG_CMP_GE(rnp_root->gpnum, c). AIUI the goal of this condition is to check whether the requested grace period has already started. I believe then the above check is insufficient. The reason I think its insufficient is I believe we should also check the state of the grace period to augment this check.
IMO the condition should really be:
(ULONG_CMP_GT(rnp_root->gpnum, c) ||

The above asks whether the -next- grace period -after- the requested one had started.

Quoted 1 line

  (rnp_root->gpnum == c && rnp_root->gpnum != rnp_root->completed))

This asks that the requested grace period not have completed.

What about the case where the requested grace period has completed, but the one after has not yet started? If you add that in, I bet you will have something that simplifies to my original.

Quoted 8 lines

Quoted 4 lines

In a later patch you replaced this with rseq_done(&rnp_root->gp_seq, c) which kind of accounts for the state, except that rseq_done uses ULONG_CMP_GE, whereas to fix this, rseq_done IMO should be using ULONG_CMP_GT to be equivalent to the above check. Do you agree?

I do not believe that I do. The ULONG_CMP_GE() allows for the missing case where the requested grace period completed, but the following grace period has not yet started.

Ok thanks that clears it up. For some reason I was thinking if rnp_root->gpnum == c, that could means 'c' has not yet started, unless we also checked the state. Obviously, now I realize gpnum == c can only mean 2 things:
- c has started but not yet completed
- c has completed

Both of these cases should cause a bail out so I agree now with your condition ULONG_CMP_GE, thanks.

Quoted 9 lines

Quoted 8 lines

The third condition for pre-started is:

                   (rnp != rnp_root && rnp_root->gpnum != rnp_root->completed))

This as I followed from your commit message is if an intermediate node thinks RCU is non-idle, then its not necessary to mark the tree and we can bail out since the clean up will scan the whole tree anyway. That makes sense to me but I think I will like to squash the diff in your previous email into this condition as well to handle both conditions together.

Quoted 3 lines

Please keep in mind that it is necessary to actually record the request in the leaf case. Or are you advocating use of ?: or similar to make this happen?

Yes, I realized yesterday you wanted to record it for the leaf that's why you're doing things this way. I'll let you know if I find any other ways of simplifying it once I look at your latest tree.

Btw, I checked your git tree and couldn't see the update that you mentioned you queued above. Could you push those changes?

Quoted 2 lines

Good point, pushed now. And the patch that I forgot to include in the last email is below.

Cool, thanks. Also one thing I wanted to discuss, I am a bit unclear about the if (rcu_seq_done..) condition in the loop which decides if the GP requested is pre-started.

Say c is 8 (0b1000) - i.e. gp requested is 2.
I drew some tables with some examples, the result column is what the current code will do.

Say gp_seq is 12 and its not progress (0b1100),

gp_seq gp_num state analysis of gp_seq result
12 3 0 gp 3 not started pre-started
(gp 2 completed)

For this, the "greater than" check in rcu_seq_done will work because 2 already completed (The check essentially does 12 >= 8 which implies prestarted).

Say gp_seq is 9 and it is in progress (0b1001)
gp_seq gp_num state state of gp_seq result
9 2 1 gp 2 in progress pre-started
(gp 1 completed)

Here also the "greater than" check is correct (9 >= 8 which implies prestarted).

However, say gp_seq is 8
gp_seq gp_num state state of gp_seq result
8 2 0 gp 2 not started pre-started
(gp 1 completed)

In this case, rcu_seq_done will incorrectly say that its pre-started when 2 has not yet started. For this reason, I feel the equal-to check in rcu_seq_done will incorrectly predict prestarted.

I think to fix this, the rseq_done condition could be replaced with:

	if (ULONG_CMP_GT(rnp_root->gpseq, c)) {
		// pre-started
	}

I believe the difference arises because one of the patches during the conversion to use gp_seq in the tree replaced rcu_seq_done with ULONG_CMP_GE, where as such a replacement doesn't work in the gp_seq regime because of difference in the way a gp's starte/end is accounted (vs the old way).

Does it make sense or was I way off about something :D ?

Quoted 77 lines

Quoted 77 lines

Quoted 76 lines

Quoted 38 lines

Quoted 19 lines

If you don't mind going through the if conditions in the funnel locking loop with me, it would be quite helpful so that I don't mess the code up and would also help me add tracing correctly.

The if condition for prestarted is this:

               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;
		need_future_gp_element(rnp_root, c) = true;

As of 16/21, the heart of the loop is the above (excluding the locking bits)

In this what confuses me is the second and the third condition for pre-started.

Quoted 7 lines

The second condition is: ULONG_CMP_GE(rnp_root->gpnum, c). AIUI the goal of this condition is to check whether the requested grace period has already started. I believe then the above check is insufficient. The reason I think its insufficient is I believe we should also check the state of the grace period to augment this check.
IMO the condition should really be:
(ULONG_CMP_GT(rnp_root->gpnum, c) ||

The above asks whether the -next- grace period -after- the requested one had started.

Quoted 1 line

  (rnp_root->gpnum == c && rnp_root->gpnum != rnp_root->completed))

This asks that the requested grace period not have completed.

What about the case where the requested grace period has completed, but the one after has not yet started? If you add that in, I bet you will have something that simplifies to my original.

Quoted 8 lines

Quoted 4 lines

In a later patch you replaced this with rseq_done(&rnp_root->gp_seq, c) which kind of accounts for the state, except that rseq_done uses ULONG_CMP_GE, whereas to fix this, rseq_done IMO should be using ULONG_CMP_GT to be equivalent to the above check. Do you agree?

I do not believe that I do. The ULONG_CMP_GE() allows for the missing case where the requested grace period completed, but the following grace period has not yet started.

Ok thanks that clears it up. For some reason I was thinking if rnp_root->gpnum == c, that could means 'c' has not yet started, unless we also checked the state. Obviously, now I realize gpnum == c can only mean 2 things:
- c has started but not yet completed
- c has completed

Both of these cases should cause a bail out so I agree now with your condition ULONG_CMP_GE, thanks.

Quoted 9 lines

Quoted 8 lines

The third condition for pre-started is:

                   (rnp != rnp_root && rnp_root->gpnum != rnp_root->completed))

This as I followed from your commit message is if an intermediate node thinks RCU is non-idle, then its not necessary to mark the tree and we can bail out since the clean up will scan the whole tree anyway. That makes sense to me but I think I will like to squash the diff in your previous email into this condition as well to handle both conditions together.

Quoted 3 lines

Please keep in mind that it is necessary to actually record the request in the leaf case. Or are you advocating use of ?: or similar to make this happen?

Yes, I realized yesterday you wanted to record it for the leaf that's why you're doing things this way. I'll let you know if I find any other ways of simplifying it once I look at your latest tree.

Btw, I checked your git tree and couldn't see the update that you mentioned you queued above. Could you push those changes?

Quoted 6 lines

Quoted 2 lines

Good point, pushed now. And the patch that I forgot to include in the last email is below.

Cool, thanks. Also one thing I wanted to discuss, I am a bit unclear about the if (rcu_seq_done..) condition in the loop which decides if the GP requested is pre-started.

Actually, rcu_seq_done() instead determines whether or not the GP has -completed-.

Quoted 4 lines

Say c is 8 (0b1000) - i.e. gp requested is 2.
I drew some tables with some examples, the result column is what the current code will do.

Quoted 8 lines

Say gp_seq is 12 and its not progress (0b1100),

gp_seq gp_num state analysis of gp_seq result
12 3 0 gp 3 not started pre-started
(gp 2 completed)

For this, the "greater than" check in rcu_seq_done will work because 2 already completed (The check essentially does 12 >= 8 which implies prestarted).

Agreed.

Quoted 6 lines

Say gp_seq is 9 and it is in progress (0b1001)
gp_seq gp_num state state of gp_seq result
9 2 1 gp 2 in progress pre-started
(gp 1 completed)

Here also the "greater than" check is correct (9 >= 8 which implies prestarted).

Yes, ->gp_seq of 9 implies that _snap() of 8 is done and gone.

Quoted 8 lines

However, say gp_seq is 8
gp_seq gp_num state state of gp_seq result
8 2 0 gp 2 not started pre-started
(gp 1 completed)

In this case, rcu_seq_done will incorrectly say that its pre-started when 2 has not yet started. For this reason, I feel the equal-to check in rcu_seq_done will incorrectly predict prestarted.

If _snap() said 8, then it meant that when ->gp_seq reached 8, the needed grace periods had elapsed. So ULONG_CMP_GE() really is what we want.

Quoted 11 lines

I think to fix this, the rseq_done condition could be replaced with:

	if (ULONG_CMP_GT(rnp_root->gpseq, c)) {
		// pre-started
	}

I believe the difference arises because one of the patches during the conversion to use gp_seq in the tree replaced rcu_seq_done with ULONG_CMP_GE, where as such a replacement doesn't work in the gp_seq regime because of difference in the way a gp's starte/end is accounted (vs the old way).

Quoted 1 line

Does it make sense or was I way off about something :D ?

I believe that you need to start with where the value passed via "c" to rcu_start_this_gp() came from. I suggest starting with the call from the rcu_seq_snap() in rcu_nocb_wait_gp(), whose return value is then passed to rcu_start_this_gp(), the reason being that it doesn't drag you through the callback lists.

Hello!

This series reduces lock contention on the root rcu_node structure, and is also the first precursor to TBD changes to consolidate the three RCU flavors (RCU-bh, RCU-preempt, and RCU-sched) into one.

On Sun, May 13, 2018 at 07:22:06PM -0700, Paul E. McKenney wrote:
[..]

Quoted 107 lines

Quoted 77 lines

Quoted 77 lines

Quoted 76 lines

Quoted 38 lines

Quoted 19 lines

If you don't mind going through the if conditions in the funnel locking loop with me, it would be quite helpful so that I don't mess the code up and would also help me add tracing correctly.

The if condition for prestarted is this:

               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;
		need_future_gp_element(rnp_root, c) = true;

As of 16/21, the heart of the loop is the above (excluding the locking bits)

In this what confuses me is the second and the third condition for pre-started.

Quoted 7 lines

The second condition is: ULONG_CMP_GE(rnp_root->gpnum, c). AIUI the goal of this condition is to check whether the requested grace period has already started. I believe then the above check is insufficient. The reason I think its insufficient is I believe we should also check the state of the grace period to augment this check.
IMO the condition should really be:
(ULONG_CMP_GT(rnp_root->gpnum, c) ||

The above asks whether the -next- grace period -after- the requested one had started.

Quoted 1 line

  (rnp_root->gpnum == c && rnp_root->gpnum != rnp_root->completed))

This asks that the requested grace period not have completed.

What about the case where the requested grace period has completed, but the one after has not yet started? If you add that in, I bet you will have something that simplifies to my original.

Quoted 8 lines

Quoted 4 lines

In a later patch you replaced this with rseq_done(&rnp_root->gp_seq, c) which kind of accounts for the state, except that rseq_done uses ULONG_CMP_GE, whereas to fix this, rseq_done IMO should be using ULONG_CMP_GT to be equivalent to the above check. Do you agree?

I do not believe that I do. The ULONG_CMP_GE() allows for the missing case where the requested grace period completed, but the following grace period has not yet started.

Ok thanks that clears it up. For some reason I was thinking if rnp_root->gpnum == c, that could means 'c' has not yet started, unless we also checked the state. Obviously, now I realize gpnum == c can only mean 2 things:
- c has started but not yet completed
- c has completed

Both of these cases should cause a bail out so I agree now with your condition ULONG_CMP_GE, thanks.

Quoted 9 lines

Quoted 8 lines

The third condition for pre-started is:

                   (rnp != rnp_root && rnp_root->gpnum != rnp_root->completed))

This as I followed from your commit message is if an intermediate node thinks RCU is non-idle, then its not necessary to mark the tree and we can bail out since the clean up will scan the whole tree anyway. That makes sense to me but I think I will like to squash the diff in your previous email into this condition as well to handle both conditions together.

Quoted 3 lines

Please keep in mind that it is necessary to actually record the request in the leaf case. Or are you advocating use of ?: or similar to make this happen?

Yes, I realized yesterday you wanted to record it for the leaf that's why you're doing things this way. I'll let you know if I find any other ways of simplifying it once I look at your latest tree.

Btw, I checked your git tree and couldn't see the update that you mentioned you queued above. Could you push those changes?

Quoted 6 lines

Quoted 2 lines

Good point, pushed now. And the patch that I forgot to include in the last email is below.

Cool, thanks. Also one thing I wanted to discuss, I am a bit unclear about the if (rcu_seq_done..) condition in the loop which decides if the GP requested is pre-started.

Actually, rcu_seq_done() instead determines whether or not the GP has -completed-.

Quoted 4 lines

Say c is 8 (0b1000) - i.e. gp requested is 2.
I drew some tables with some examples, the result column is what the current code will do.

Quoted 8 lines

Say gp_seq is 12 and its not progress (0b1100),

gp_seq gp_num state analysis of gp_seq result
12 3 0 gp 3 not started pre-started
(gp 2 completed)

For this, the "greater than" check in rcu_seq_done will work because 2 already completed (The check essentially does 12 >= 8 which implies prestarted).

Agreed.

Quoted 5 lines

Say gp_seq is 9 and it is in progress (0b1001)
gp_seq gp_num state state of gp_seq result
9 2 1 gp 2 in progress pre-started
(gp 1 completed)

Quoted 3 lines

Quoted 1 line

Here also the "greater than" check is correct (9 >= 8 which implies prestarted).

Yes, ->gp_seq of 9 implies that _snap() of 8 is done and gone.

According to the above table, I was trying to indicate that gp_seq = 9 implies, gp_num of 2 is in progress, not done. So in my view, whatever the _snap returned is in progress now (state bit is set).

Quoted 11 lines

Quoted 8 lines

However, say gp_seq is 8
gp_seq gp_num state state of gp_seq result
8 2 0 gp 2 not started pre-started
(gp 1 completed)

In this case, rcu_seq_done will incorrectly say that its pre-started when 2 has not yet started. For this reason, I feel the equal-to check in rcu_seq_done will incorrectly predict prestarted.

If _snap() said 8, then it meant that when ->gp_seq reached 8, the needed grace periods had elapsed. So ULONG_CMP_GE() really is what we want.

I kind of don't agree still according to the below (but I'm pretty sure I'm missing something so I probably need to go through some more examples, do some more tracing etc.)

Forgetting about _snap for a second, can we not look at gp_seq independently and determine what the grace period is currently doing? In my view, if gp_seq reaches 8 (gp_num is 2) - that means that gp_num of 1 was just done. It doesn't mean 2 completed.. 2 could have either started or not yet started, we can't tell without look at the state bits... this is the part I didn't get.

rcu_seq_start only sets the state bit. rcu_seq_end increments the gp_num value.

I thought when rcu_seq_end sets the value part of gp_seq to gp_num, I thought that means that gp_num - 1 just completed. Is that not true?

Quoted 10 lines

Quoted 10 lines

I think to fix this, the rseq_done condition could be replaced with:

	if (ULONG_CMP_GT(rnp_root->gpseq, c)) {
		// pre-started
	}

I believe the difference arises because one of the patches during the conversion to use gp_seq in the tree replaced rcu_seq_done with ULONG_CMP_GE, where as such a replacement doesn't work in the gp_seq regime because of difference in the way a gp's starte/end is accounted (vs the old way).

Quoted 7 lines

Quoted 1 line

Does it make sense or was I way off about something :D ?

I believe that you need to start with where the value passed via "c" to rcu_start_this_gp() came from. I suggest starting with the call from the rcu_seq_snap() in rcu_nocb_wait_gp(), whose return value is then passed to rcu_start_this_gp(), the reason being that it doesn't drag you through the callback lists.

Ok I'll try to do some more tracing / analysis and think some more following your suggestions about starting from rcu_nocb_wait_gp. Most likely I am wrong, but I am yet to convince myself about it :-(

thanks so much!

- Joel

Quoted 5 lines · On Sun, 22 Apr 2018 20:02:58 -0700 "Paul E. McKenney"…

Hello!

This series reduces lock contention on the root rcu_node structure, and is also the first precursor to TBD changes to consolidate the three RCU flavors (RCU-bh, RCU-preempt, and RCU-sched) into one.

Hi Paul,

I've been running your rcu/dev branch and haven't noticed any problems yet. The irqsoff latency improvement is a little hard to measure because the scheduler, but I've tried turning balancing parameters right down and I'm yet to see any sign of RCU in traces (down to about 100us on a 176 CPU machine), so that's great.

(Not that RCU was ever the worst contributor to latency as I said, just that I noticed those couple of traces where it showed up.)

Thanks very much for the fast response, sorry I've taken a while to test.

Quoted 12 lines · Nicholas Piggin

Quoted 6 lines · On Sun, 22 Apr 2018 20:02:58 -0700 "Paul E. McKenney"…

Hello!

This series reduces lock contention on the root rcu_node structure, and is also the first precursor to TBD changes to consolidate the three RCU flavors (RCU-bh, RCU-preempt, and RCU-sched) into one.

Hi Paul,

Quoted 5 lines

I've been running your rcu/dev branch and haven't noticed any problems yet. The irqsoff latency improvement is a little hard to measure because the scheduler, but I've tried turning balancing parameters right down and I'm yet to see any sign of RCU in traces (down to about 100us on a 176 CPU machine), so that's great.

Good to hear!!!

Quoted 5 lines

(Not that RCU was ever the worst contributor to latency as I said, just that I noticed those couple of traces where it showed up.)

Thanks very much for the fast response, sorry I've taken a while to test.

Would you be willing to give me a Tested-by on that series of patches?

Quoted 19 lines · On Mon, 14 May 2018 09:09:07 -0700 "Paul E. McKenney"…

Quoted 17 lines · Nicholas Piggin

Quoted 6 lines · On Sun, 22 Apr 2018 20:02:58 -0700 "Paul E. McKenney"…

Hello!

This series reduces lock contention on the root rcu_node structure, and is also the first precursor to TBD changes to consolidate the three RCU flavors (RCU-bh, RCU-preempt, and RCU-sched) into one.

Hi Paul,

I've been running your rcu/dev branch and haven't noticed any problems yet. The irqsoff latency improvement is a little hard to measure because the scheduler, but I've tried turning balancing parameters right down and I'm yet to see any sign of RCU in traces (down to about 100us on a 176 CPU machine), so that's great.

Quoted 1 line

Good to hear!!!

Yep, as in, various other latencies are down to 100us, and still no sign of RCU, so RCU must be sitting somewhere below that.

Quoted 7 lines

Quoted 5 lines

(Not that RCU was ever the worst contributor to latency as I said, just that I noticed those couple of traces where it showed up.)

Thanks very much for the fast response, sorry I've taken a while to test.

Would you be willing to give me a Tested-by on that series of patches?

Yes of course, for your rcu/dev series

Tested-by Nicholas Piggin <[email protected]>

Let me know if you make any other changes you'd like me to test before merge.