Fix for cond_resched performance regression

Hello!

This series contains changes to address the performance regressions introduced by commit ac1bea85781e (Make cond_resched() report RCU quiescent states), which was in turn fixing a problem where tasks looping in the kernel could delay RCU grace periods. The changes in this series are as follows:

1. Reduce the overhead of checking added to cond_resched() and friends.

2. Add a new cond_resched_rcu_qs() to provide RCU quiescent states
even if cond_resched() should stop doing so.

3. Add a new RCU_COND_RESCHED_QS to prevent cond_resched() from
reporting RCU quiescent states.

4. Prevent rcutorture testing from reporting spurious RCU CPU stall
warnings, and also to test RCU_COND_RESCHED_QS.

5. Provides a boot/sysfs rcutree.jiffies_till_cond_resched_qs
parameter to replace the magic "7".

Hello!

This series contains changes to address the performance regressions introduced by commit ac1bea85781e (Make cond_resched() report RCU quiescent states), which was in turn fixing a problem where tasks looping in the kernel could delay RCU grace periods. The changes in this series are as follows:

1. Reduce the overhead of checking added to cond_resched() and friends.

2. Add a new cond_resched_rcu_qs() to provide RCU quiescent states
even if cond_resched() should stop doing so.

3. Add a new RCU_COND_RESCHED_QS to prevent cond_resched() from
reporting RCU quiescent states.

4. Prevent rcutorture testing from reporting spurious RCU CPU stall
warnings, and also to test RCU_COND_RESCHED_QS.

5. Provides a boot/sysfs rcutree.jiffies_till_cond_resched_qs
parameter to replace the magic "7".

o Make cond_resched() a no-op for PREEMPT=y. This might well turn
out to be a good thing, but it doesn't help give RCU the quiescent states that it needs.

Quoted 19 lines · Paul E. McKenney

Hello!

This series contains changes to address the performance regressions introduced by commit ac1bea85781e (Make cond_resched() report RCU quiescent states), which was in turn fixing a problem where tasks looping in the kernel could delay RCU grace periods. The changes in this series are as follows:

1. Reduce the overhead of checking added to cond_resched() and friends.

2. Add a new cond_resched_rcu_qs() to provide RCU quiescent states
even if cond_resched() should stop doing so.

3. Add a new RCU_COND_RESCHED_QS to prevent cond_resched() from
reporting RCU quiescent states.

4. Prevent rcutorture testing from reporting spurious RCU CPU stall
warnings, and also to test RCU_COND_RESCHED_QS.

Quoted 2 lines

5. Provides a boot/sysfs rcutree.jiffies_till_cond_resched_qs
parameter to replace the magic "7".

For all five patches:

Reviewed-by Josh Triplett <[email protected]>

Glad to see this doesn't add any overhead to rcutiny.

Quoted 3 lines · Paul E. McKenney

o Make cond_resched() a no-op for PREEMPT=y. This might well turn
out to be a good thing, but it doesn't help give RCU the quiescent states that it needs.

What about doing this, together with letting the fqs logic poke un-quiesced kernel code as needed? That way, rather than having cond_resched do any work, you have the fqs logic recognize that a particular CPU has gone too long without quiescing, without disturbing that CPU at all if it hasn't gone too long.

Quoted 10 lines · On Fri, Jun 20, 2014 at 02:24:23PM -0700, [email protected] wrote:

Quoted 3 lines · Paul E. McKenney

o Make cond_resched() a no-op for PREEMPT=y. This might well turn
out to be a good thing, but it doesn't help give RCU the quiescent states that it needs.

What about doing this, together with letting the fqs logic poke un-quiesced kernel code as needed? That way, rather than having cond_resched do any work, you have the fqs logic recognize that a particular CPU has gone too long without quiescing, without disturbing that CPU at all if it hasn't gone too long.

My next stop is to post the previous series, but with a couple of exports and one bug fix uncovered by testing thus far, but after another round of testing. Then I am going to take a close look at this one:

o Push the checks further into cond_resched(), so that the
fastpath does the same sequence of instructions that the original did. This might work well, but requires IPIs, which are not so good for latencies on the remote CPU. It nevertheless might be a decent long-term solution given that if your CPU is spending many jiffies looping in the kernel, you aren't getting good latencies anyway. It also has the benefit of allowing RCU to take advantage of the implicit quiescent states of all cond_resched() calls, and of eliminating the need for a separate cond_resched_rcu_qs() and for RCU_COND_RESCHED_QS.

The one you call out is of course interesting as well. But there are a couple of questions:

1. Why wasn't cond_resched() a no-op in CONFIG_PREEMPT to start
with? It just seems to obvious a thing to do for it to possibly be an oversight. (What, me paranoid?)

2. When RCU recognizes that a particular CPU has gone too long,
exactly what are you suggesting that RCU do about it? When formulating your answer, please give due consideration to the implications of that CPU being a NO_HZ_FULL CPU. ;-)

Quoted 35 lines · Paul E. McKenney

Quoted 10 lines · On Fri, Jun 20, 2014 at 02:24:23PM -0700, [email protected] wrote:

Quoted 3 lines · Paul E. McKenney

o Make cond_resched() a no-op for PREEMPT=y. This might well turn
out to be a good thing, but it doesn't help give RCU the quiescent states that it needs.

What about doing this, together with letting the fqs logic poke un-quiesced kernel code as needed? That way, rather than having cond_resched do any work, you have the fqs logic recognize that a particular CPU has gone too long without quiescing, without disturbing that CPU at all if it hasn't gone too long.

My next stop is to post the previous series, but with a couple of exports and one bug fix uncovered by testing thus far, but after another round of testing. Then I am going to take a close look at this one:

o Push the checks further into cond_resched(), so that the
fastpath does the same sequence of instructions that the original did. This might work well, but requires IPIs, which are not so good for latencies on the remote CPU. It nevertheless might be a decent long-term solution given that if your CPU is spending many jiffies looping in the kernel, you aren't getting good latencies anyway. It also has the benefit of allowing RCU to take advantage of the implicit quiescent states of all cond_resched() calls, and of eliminating the need for a separate cond_resched_rcu_qs() and for RCU_COND_RESCHED_QS.

The one you call out is of course interesting as well. But there are a couple of questions:

1. Why wasn't cond_resched() a no-op in CONFIG_PREEMPT to start
with? It just seems to obvious a thing to do for it to possibly be an oversight. (What, me paranoid?)

Quoted 4 lines

2. When RCU recognizes that a particular CPU has gone too long,
exactly what are you suggesting that RCU do about it? When formulating your answer, please give due consideration to the implications of that CPU being a NO_HZ_FULL CPU. ;-)

Send it an IPI that either causes it to flag a quiescent state immediately if currently quiesced or causes it to quiesce at the next opportunity if not.

Quoted 41 lines · On Fri, Jun 20, 2014 at 03:39:51PM -0700, [email protected] wrote:

Quoted 39 lines · Paul E. McKenney

Quoted 10 lines · On Fri, Jun 20, 2014 at 02:24:23PM -0700, [email protected] wrote:

Quoted 3 lines · Paul E. McKenney

o Make cond_resched() a no-op for PREEMPT=y. This might well turn
out to be a good thing, but it doesn't help give RCU the quiescent states that it needs.

What about doing this, together with letting the fqs logic poke un-quiesced kernel code as needed? That way, rather than having cond_resched do any work, you have the fqs logic recognize that a particular CPU has gone too long without quiescing, without disturbing that CPU at all if it hasn't gone too long.

My next stop is to post the previous series, but with a couple of exports and one bug fix uncovered by testing thus far, but after another round of testing. Then I am going to take a close look at this one:

o Push the checks further into cond_resched(), so that the
fastpath does the same sequence of instructions that the original did. This might work well, but requires IPIs, which are not so good for latencies on the remote CPU. It nevertheless might be a decent long-term solution given that if your CPU is spending many jiffies looping in the kernel, you aren't getting good latencies anyway. It also has the benefit of allowing RCU to take advantage of the implicit quiescent states of all cond_resched() calls, and of eliminating the need for a separate cond_resched_rcu_qs() and for RCU_COND_RESCHED_QS.

The one you call out is of course interesting as well. But there are a couple of questions:

1. Why wasn't cond_resched() a no-op in CONFIG_PREEMPT to start
with? It just seems to obvious a thing to do for it to possibly be an oversight. (What, me paranoid?)

2. When RCU recognizes that a particular CPU has gone too long,
exactly what are you suggesting that RCU do about it? When formulating your answer, please give due consideration to the implications of that CPU being a NO_HZ_FULL CPU. ;-)

Quoted 3 lines

Send it an IPI that either causes it to flag a quiescent state immediately if currently quiesced or causes it to quiesce at the next opportunity if not.

OK. But if we are in a !PREEMPT kernel,

Quoted 42 lines · Paul E. McKenney

Quoted 41 lines · On Fri, Jun 20, 2014 at 03:39:51PM -0700, [email protected] wrote:

Quoted 39 lines · Paul E. McKenney

Quoted 10 lines · On Fri, Jun 20, 2014 at 02:24:23PM -0700, [email protected] wrote:

Quoted 3 lines · Paul E. McKenney

o Make cond_resched() a no-op for PREEMPT=y. This might well turn
out to be a good thing, but it doesn't help give RCU the quiescent states that it needs.

What about doing this, together with letting the fqs logic poke un-quiesced kernel code as needed? That way, rather than having cond_resched do any work, you have the fqs logic recognize that a particular CPU has gone too long without quiescing, without disturbing that CPU at all if it hasn't gone too long.

My next stop is to post the previous series, but with a couple of exports and one bug fix uncovered by testing thus far, but after another round of testing. Then I am going to take a close look at this one:

o Push the checks further into cond_resched(), so that the
fastpath does the same sequence of instructions that the original did. This might work well, but requires IPIs, which are not so good for latencies on the remote CPU. It nevertheless might be a decent long-term solution given that if your CPU is spending many jiffies looping in the kernel, you aren't getting good latencies anyway. It also has the benefit of allowing RCU to take advantage of the implicit quiescent states of all cond_resched() calls, and of eliminating the need for a separate cond_resched_rcu_qs() and for RCU_COND_RESCHED_QS.

The one you call out is of course interesting as well. But there are a couple of questions:

1. Why wasn't cond_resched() a no-op in CONFIG_PREEMPT to start
with? It just seems to obvious a thing to do for it to possibly be an oversight. (What, me paranoid?)

2. When RCU recognizes that a particular CPU has gone too long,
exactly what are you suggesting that RCU do about it? When formulating your answer, please give due consideration to the implications of that CPU being a NO_HZ_FULL CPU. ;-)

Quoted 5 lines

Quoted 3 lines

Send it an IPI that either causes it to flag a quiescent state immediately if currently quiesced or causes it to quiesce at the next opportunity if not.

OK. But if we are in a !PREEMPT kernel,

That's not the case I was suggesting.

*If* the kernel is fully
preemptible, then it makes little sense to put any code in cond_resched, when instead another thread can simply cause a preemption if it needs a quiescent state. That has the advantage of not imposing any unnecessary polling on code running in the kernel.

In a !PREEMPT kernel, it makes a bit more sense to have cond_resched as a voluntary preemption point. But voluntary preemption points don't make as much sense in a kernel prepared to preempt a thread anywhere.

Quoted 43 lines · On Fri, Jun 20, 2014 at 04:52:15PM -0700, [email protected] wrote:

Quoted 42 lines · Paul E. McKenney

Quoted 41 lines · On Fri, Jun 20, 2014 at 03:39:51PM -0700, [email protected] wrote:

Quoted 39 lines · Paul E. McKenney

Quoted 10 lines · On Fri, Jun 20, 2014 at 02:24:23PM -0700, [email protected] wrote:

Quoted 3 lines · Paul E. McKenney

o Make cond_resched() a no-op for PREEMPT=y. This might well turn
out to be a good thing, but it doesn't help give RCU the quiescent states that it needs.

What about doing this, together with letting the fqs logic poke un-quiesced kernel code as needed? That way, rather than having cond_resched do any work, you have the fqs logic recognize that a particular CPU has gone too long without quiescing, without disturbing that CPU at all if it hasn't gone too long.

My next stop is to post the previous series, but with a couple of exports and one bug fix uncovered by testing thus far, but after another round of testing. Then I am going to take a close look at this one:

o Push the checks further into cond_resched(), so that the
fastpath does the same sequence of instructions that the original did. This might work well, but requires IPIs, which are not so good for latencies on the remote CPU. It nevertheless might be a decent long-term solution given that if your CPU is spending many jiffies looping in the kernel, you aren't getting good latencies anyway. It also has the benefit of allowing RCU to take advantage of the implicit quiescent states of all cond_resched() calls, and of eliminating the need for a separate cond_resched_rcu_qs() and for RCU_COND_RESCHED_QS.

The one you call out is of course interesting as well. But there are a couple of questions:

1. Why wasn't cond_resched() a no-op in CONFIG_PREEMPT to start
with? It just seems to obvious a thing to do for it to possibly be an oversight. (What, me paranoid?)

2. When RCU recognizes that a particular CPU has gone too long,
exactly what are you suggesting that RCU do about it? When formulating your answer, please give due consideration to the implications of that CPU being a NO_HZ_FULL CPU. ;-)

Quoted 7 lines

Quoted 5 lines

Quoted 3 lines

Send it an IPI that either causes it to flag a quiescent state immediately if currently quiesced or causes it to quiesce at the next opportunity if not.

OK. But if we are in a !PREEMPT kernel,

That's not the case I was suggesting.

Fair enough, but we still need to support !PREEMPT kernels.

Quoted 5 lines

*If* the kernel is fully
preemptible, then it makes little sense to put any code in cond_resched, when instead another thread can simply cause a preemption if it needs a quiescent state. That has the advantage of not imposing any unnecessary polling on code running in the kernel.

OK. Exactly which thread are you suggesting should cause the preemption?

Quoted 3 lines

In a !PREEMPT kernel, it makes a bit more sense to have cond_resched as a voluntary preemption point. But voluntary preemption points don't make as much sense in a kernel prepared to preempt a thread anywhere.

That does sound intuitive, but I am not yet prepared to believe that the scheduler guys missed this trick. There might well be some good reason for cond_resched() doing something, though I cannot think what it might be (something to do with preempt_enable_no_resched(), perhaps?). We should at least ask them, although if you want to do some testing before asking them, I of course have no objection to your doing so.

This commit takes a different approach to fixing this bug, mainly by avoiding having cond_resched() do an RCU-visible quiescent state unless there is a grace period that has been in flight for a significant period of time. This commit also reduces the common-case cond_resched() overhead to a check of a single per-CPU variable.

kernel/rcu/tree.c +16 -0

+void rcu_resched(void)
+{
+	unsigned long flags;
+	struct rcu_data *rdp;
+	struct rcu_dynticks *rdtp;
+	int resched_mask;
+	struct rcu_state *rsp;
+
+	local_irq_save(flags);
+
+	/*
+	 * Yes, we can lose flag-setting operations.  This is OK, because
+	 * the flag will be set again after some delay.
+	 */
+	resched_mask = raw_cpu_read(rcu_cond_resched_mask);
+	raw_cpu_write(rcu_cond_resched_mask, 0);

kernel/rcu/tree.c +5 -5

@@ -893,13 +946,20 @@ static int rcu_implicit_dynticks_qs(struct rcu_data *rdp,
 	}
 
 	/*
-	 * There is a possibility that a CPU in adaptive-ticks state
-	 * might run in the kernel with the scheduling-clock tick disabled
-	 * for an extended time period.  Invoke rcu_kick_nohz_cpu() to
-	 * force the CPU to restart the scheduling-clock tick in this
-	 * CPU is in this state.
+	 * A CPU running for an extended time within the kernel can
+	 * delay RCU grace periods.  When the CPU is in NO_HZ_FULL mode,
+	 * even context-switching back and forth between a pair of
+	 * in-kernel CPU-bound tasks cannot advance grace periods.
+	 * So if the grace period is old enough, make the CPU pay attention.

Quoted 6 lines · Paul E. McKenney

This commit takes a different approach to fixing this bug, mainly by avoiding having cond_resched() do an RCU-visible quiescent state unless there is a grace period that has been in flight for a significant period of time. This commit also reduces the common-case cond_resched() overhead to a check of a single per-CPU variable.

I can't say I fully understand this change, but I think it is fine. Just a really stupid question below.

Quoted 22 lines

kernel/rcu/tree.c +22 -0

+void rcu_resched(void)
+{
+	unsigned long flags;
+	struct rcu_data *rdp;
+	struct rcu_dynticks *rdtp;
+	int resched_mask;
+	struct rcu_state *rsp;
+
+	local_irq_save(flags);
+
+	/*
+	 * Yes, we can lose flag-setting operations.  This is OK, because
+	 * the flag will be set again after some delay.
+	 */
+	resched_mask = raw_cpu_read(rcu_cond_resched_mask);
+	raw_cpu_write(rcu_cond_resched_mask, 0);
+
+	/* Find the flavor that needs a quiescent state. */
+	for_each_rcu_flavor(rsp) {
+		rdp = raw_cpu_ptr(rsp->rda);
+		if (!(resched_mask & rsp->flavor_mask))
+			continue;

kernel/rcu/tree.c static DEFINE_PER_CPU(struct rcu_dynticks, rcu_dynticks) = { · line 267

Quoted 4 lines

kernel/rcu/tree.c +4 -0

+		smp_mb(); /* ->flavor_mask before ->cond_resched_completed. */
+		if (ACCESS_ONCE(rdp->mynode->completed) !=
+		    ACCESS_ONCE(rdp->cond_resched_completed))
+			continue;

Probably the comment above mb() meant "rcu_cond_resched_mask before ->cond_resched_completed" ? Otherwise I can't see why do we need any barrier.

Quoted 14 lines

kernel/rcu/tree.c +5 -5

@@ -893,13 +946,20 @@ static int rcu_implicit_dynticks_qs(struct rcu_data *rdp,
 	}
 
 	/*
-	 * There is a possibility that a CPU in adaptive-ticks state
-	 * might run in the kernel with the scheduling-clock tick disabled
-	 * for an extended time period.  Invoke rcu_kick_nohz_cpu() to
-	 * force the CPU to restart the scheduling-clock tick in this
-	 * CPU is in this state.
+	 * A CPU running for an extended time within the kernel can
+	 * delay RCU grace periods.  When the CPU is in NO_HZ_FULL mode,
+	 * even context-switching back and forth between a pair of
+	 * in-kernel CPU-bound tasks cannot advance grace periods.
+	 * So if the grace period is old enough, make the CPU pay attention.

kernel/rcu/tree.c static int rcu_implicit_dynticks_qs(struct rcu_data *rdp, · line 962

Quoted 10 lines

kernel/rcu/tree.c +8 -1

 	 */
-	rcu_kick_nohz_cpu(rdp->cpu);
+	if (ULONG_CMP_GE(jiffies, rdp->rsp->gp_start + 7)) {
+		rcrmp = &per_cpu(rcu_cond_resched_mask, rdp->cpu);
+		ACCESS_ONCE(rdp->cond_resched_completed) =
+			ACCESS_ONCE(rdp->mynode->completed);
+		smp_mb(); /* ->cond_resched_completed before *rcrmp. */
+		ACCESS_ONCE(*rcrmp) =
+			ACCESS_ONCE(*rcrmp) + rdp->rsp->flavor_mask;
+	}

OK, in this case I guess we need a full barrier because we need to read rcu_cond_resched_mask before updating it...

But, I am just curious, is there any reason to use ACCESS_ONCE() twice?

	ACCESS_ONCE(*rcrmp) |= rdp->rsp->flavor_mask;

or even

	ACCESS_ONCE(per_cpu(rcu_cond_resched_mask, rdp->cpu)) |=
		rdp->rsp->flavor_mask;

should equally work, or ACCESS_ONCE() can't be used to RMW ?

(and in fact at least the 2nd ACCESS_ONCE() (load) looks unnecessary anyway
because of smp_mb() above).

Once again, of course I am not arguing if there is no "real" reason and you just prefer it this way. But the kernel has more and more ACESS_ONCE() users and sometime I simply do not understand why it is needed. For example, cyc2ns_write_end().

Or even INIT_LIST_HEAD_RCU(). The comment in list_splice_init_rcu() says:

	/*
	 * "first" and "last" tracking list, so initialize it.  RCU readers
	 * have access to this list, so we must use INIT_LIST_HEAD_RCU()
	 * instead of INIT_LIST_HEAD().
	 */

	INIT_LIST_HEAD_RCU(list);

but we are going to call synchronize_rcu() or something similar, this should act as compiler barrier too?

Quoted 2 lines · Oleg Nesterov

should equally work, or ACCESS_ONCE() can't be used to RMW ?

It can be, but Linus doesn't like it to be. I recently changed all of the RMW ACCESS_ONCE() calls as a result. One of the reasons for avoiding RMW ACCESS_ONCE() is that language features that might one day replace ACCESS_ONCE() do not support RMW use.

Quoted 10 lines

Or even INIT_LIST_HEAD_RCU(). The comment in list_splice_init_rcu() says:

	/*
	 * "first" and "last" tracking list, so initialize it.  RCU readers
	 * have access to this list, so we must use INIT_LIST_HEAD_RCU()
	 * instead of INIT_LIST_HEAD().
	 */

	INIT_LIST_HEAD_RCU(list);

Quoted 2 lines

but we are going to call synchronize_rcu() or something similar, this should act as compiler barrier too?

Indeed, synchronize_rcu() enforces a barrier on each CPU between any prior and subsequent accesses to RCU-protected data by that CPU. (Which means that CPUs that would otherwise sleep through the entire grace period can continue sleeping, given that it is not accessing any RCU-protected data while sleeping.) I would guess load-tearing or store-tearing concerns.

Quoted 9 lines · Paul E. McKenney

Quoted 2 lines · Oleg Nesterov

should equally work, or ACCESS_ONCE() can't be used to RMW ?

It can be, but Linus doesn't like it to be. I recently changed all of the RMW ACCESS_ONCE() calls as a result. One of the reasons for avoiding RMW ACCESS_ONCE() is that language features that might one day replace ACCESS_ONCE() do not support RMW use.

OK, thanks.

Quoted 13 lines

Quoted 10 lines

Or even INIT_LIST_HEAD_RCU(). The comment in list_splice_init_rcu() says:

	/*
	 * "first" and "last" tracking list, so initialize it.  RCU readers
	 * have access to this list, so we must use INIT_LIST_HEAD_RCU()
	 * instead of INIT_LIST_HEAD().
	 */

	INIT_LIST_HEAD_RCU(list);

Quoted 2 lines

but we are going to call synchronize_rcu() or something similar, this should act as compiler barrier too?

Quoted 6 lines

Indeed, synchronize_rcu() enforces a barrier on each CPU between any prior and subsequent accesses to RCU-protected data by that CPU. (Which means that CPUs that would otherwise sleep through the entire grace period can continue sleeping, given that it is not accessing any RCU-protected data while sleeping.) I would guess load-tearing or store-tearing concerns.

But the kernel depends on the fact that "long" should be updated atomically, and the concurent reader should see the old-or-new value without any tricks.

Perhaps we should add ACCESS_ONCE_PARANOID_FOR_COMPILER(). Otherwise when you read the code it is not always clear why it is uses ACCESS_ONCE(), and sometimes this look as if you simply do not understand it. Or at least a /* not really needed but gcc can have bugs */ could help in these cases.

From: "Paul E. McKenney" <[email protected]>

Commit ac1bea85781e (Make cond_resched() report RCU quiescent states) fixed a problem where a CPU looping in the kernel with but one runnable task would give RCU CPU stall warnings, even if the in-kernel loop contained cond_resched() calls. Unfortunately, in so doing, it introduced performance regressions in Anton Blanchard's will-it-scale "open1" test. The problem appears to be not so much the increased cond_resched() path length as an increase in the rate at which grace periods complete, which increased per-update grace-period overhead.

This commit takes a different approach to fixing this bug, mainly by avoiding having cond_resched() do an RCU-visible quiescent state unless there is a grace period that has been in flight for a significant period of time. This commit also reduces the common-case cond_resched() overhead to a check of a single per-CPU variable.

index f1ba77363fbb..2cc72ce19ff6 100644

kernel/rcu/tree.c +22 -0

@@ -229,6 +229,58 @@ static DEFINE_PER_CPU(struct rcu_dynticks, rcu_dynticks) = {
 #endif /* #ifdef CONFIG_NO_HZ_FULL_SYSIDLE */
 };
 
+/*
+ * Hooks for cond_resched() and friends to avoid RCU CPU stall warnings.
+ */
+
+DEFINE_PER_CPU(int, rcu_cond_resched_mask);
+
+/*
+ * Let the RCU core know that this CPU has gone through a cond_resched(),
+ * which is a quiescent state.
+ */
+void rcu_resched(void)
+{
+	unsigned long flags;
+	struct rcu_data *rdp;
+	struct rcu_dynticks *rdtp;
+	int resched_mask;
+	struct rcu_state *rsp;
+
+	local_irq_save(flags);
+
+	/*
+	 * Yes, we can lose flag-setting operations.  This is OK, because

kernel/rcu/tree.c +34 -6

+		smp_mb(); /* ->flavor_mask before ->cond_resched_completed. */
+		if (ACCESS_ONCE(rdp->mynode->completed) !=
+		    ACCESS_ONCE(rdp->cond_resched_completed))
+			continue;
+
+		/*
+		 * Pretend to be momentarily idle for the quiescent state.
+		 * This allows the grace-period kthread to record the
+		 * quiescent state, with no need for this CPU to do anything
+		 * further.
+		 */
+		rdtp = this_cpu_ptr(&rcu_dynticks);
+		smp_mb__before_atomic(); /* Earlier stuff before QS. */
+		atomic_add(2, &rdtp->dynticks);  /* QS. */
+		smp_mb__after_atomic(); /* Later stuff after QS. */
+		break;
+	}
+	local_irq_restore(flags);
+}
+
 static long blimit = 10;	/* Maximum callbacks per rcu_do_batch. */
 static long qhimark = 10000;	/* If this many pending, ignore blimit. */
 static long qlowmark = 100;	/* Once only this many pending, use blimit. */

@@ -853,6 +905,7 @@ static int rcu_implicit_dynticks_qs(struct rcu_data *rdp,
 				    bool *isidle, unsigned long *maxj)
 {
 	unsigned int curr;
+	int *rcrmp;
 	unsigned int snap;
 
 	curr = (unsigned int)atomic_add_return(0, &rdp->dynticks->dynticks);

@@ -893,13 +946,20 @@ static int rcu_implicit_dynticks_qs(struct rcu_data *rdp,
 	}
 
 	/*
-	 * There is a possibility that a CPU in adaptive-ticks state
-	 * might run in the kernel with the scheduling-clock tick disabled
-	 * for an extended time period.  Invoke rcu_kick_nohz_cpu() to
-	 * force the CPU to restart the scheduling-clock tick in this
-	 * CPU is in this state.
+	 * A CPU running for an extended time within the kernel can
+	 * delay RCU grace periods.  When the CPU is in NO_HZ_FULL mode,
+	 * even context-switching back and forth between a pair of
+	 * in-kernel CPU-bound tasks cannot advance grace periods.
+	 * So if the grace period is old enough, make the CPU pay attention.
 	 */
-	rcu_kick_nohz_cpu(rdp->cpu);
+	if (ULONG_CMP_GE(jiffies, rdp->rsp->gp_start + 7)) {
+		rcrmp = &per_cpu(rcu_cond_resched_mask, rdp->cpu);
+		ACCESS_ONCE(rdp->cond_resched_completed) =
+			ACCESS_ONCE(rdp->mynode->completed);
+		smp_mb(); /* ->cond_resched_completed before *rcrmp. */
+		ACCESS_ONCE(*rcrmp) =
+			ACCESS_ONCE(*rcrmp) + rdp->rsp->flavor_mask;
+	}
 
 	/*
 	 * Alternatively, the CPU might be running in the kernel

kernel/rcu/tree.c +0 -0

 	/* Initialize the elements themselves, starting from the leaves. */
 

kernel/rcu/tree.h +5 -1

index bf2c1e669691..0f69a79c5b7d 100644
@@ -307,6 +307,9 @@ struct rcu_data {
 	/* 4) reasons this CPU needed to be kicked by force_quiescent_state */
 	unsigned long dynticks_fqs;	/* Kicked due to dynticks idle. */
 	unsigned long offline_fqs;	/* Kicked due to being offline. */
+	unsigned long cond_resched_completed;
+					/* Grace period that needs help */
+					/*  from cond_resched(). */
 
 	/* 5) __rcu_pending() statistics. */
 	unsigned long n_rcu_pending;	/* rcu_pending() calls since boot. */

@@ -392,6 +395,7 @@ struct rcu_state {
 	struct rcu_node *level[RCU_NUM_LVLS];	/* Hierarchy levels. */
 	u32 levelcnt[MAX_RCU_LVLS + 1];		/* # nodes in each level. */
 	u8 levelspread[RCU_NUM_LVLS];		/* kids/node in each level. */
+	u8 flavor_mask;				/* bit in flavor mask. */
 	struct rcu_data __percpu *rda;		/* pointer of percu rcu_data. */
 	void (*call)(struct rcu_head *head,	/* call_rcu() flavor. */
 		     void (*func)(struct rcu_head *head));

@@ -563,7 +567,7 @@ static bool rcu_nocb_need_deferred_wakeup(struct rcu_data *rdp);
 static void do_nocb_deferred_wakeup(struct rcu_data *rdp);
 static void rcu_boot_init_nocb_percpu_data(struct rcu_data *rdp);
 static void rcu_spawn_nocb_kthreads(struct rcu_state *rsp);
-static void rcu_kick_nohz_cpu(int cpu);
+static void __maybe_unused rcu_kick_nohz_cpu(int cpu);
 static bool init_nocb_callback_list(struct rcu_data *rdp);
 static void rcu_sysidle_enter(struct rcu_dynticks *rdtp, int irq);
 static void rcu_sysidle_exit(struct rcu_dynticks *rdtp, int irq);

kernel/rcu/tree_plugin.h +1 -1

index cbc2c45265e2..02ac0fb186b8 100644
@@ -2404,7 +2404,7 @@ static bool init_nocb_callback_list(struct rcu_data *rdp)
  * if an adaptive-ticks CPU is failing to respond to the current grace
  * period and has not be idle from an RCU perspective, kick it.
  */
-static void rcu_kick_nohz_cpu(int cpu)
+static void __maybe_unused rcu_kick_nohz_cpu(int cpu)
 {
 #ifdef CONFIG_NO_HZ_FULL
 	if (tick_nohz_full_cpu(cpu))

kernel/rcu/update.c +0 -18

index a2aeb4df0f60..d22309cae9f5 100644
@@ -350,21 +350,3 @@ static int __init check_cpu_stall_init(void)
 early_initcall(check_cpu_stall_init);
 
 #endif /* #ifdef CONFIG_RCU_STALL_COMMON */
-
-/*
- * Hooks for cond_resched() and friends to avoid RCU CPU stall warnings.
- */
-
-DEFINE_PER_CPU(int, rcu_cond_resched_count);
-
-/*
- * Report a set of RCU quiescent states, for use by cond_resched()
- * and friends.  Out of line due to being called infrequently.
- */
-void rcu_resched(void)
-{
-	preempt_disable();
-	__this_cpu_write(rcu_cond_resched_count, 0);
-	rcu_note_context_switch(smp_processor_id());
-	preempt_enable();
-}

Hi Paul,

I was going through this code and found a few inconsistencies. I git blamed it and found that it was this recent commit and thought I could ask a few questions. I am dropping the CC's as I am not sure since it is pretty late.

Please find a few questions below:

Quoted 17 lines · Paul E. McKenney

From: "Paul E. McKenney" <[email protected]>

Commit ac1bea85781e (Make cond_resched() report RCU quiescent states) fixed a problem where a CPU looping in the kernel with but one runnable task would give RCU CPU stall warnings, even if the in-kernel loop contained cond_resched() calls. Unfortunately, in so doing, it introduced performance regressions in Anton Blanchard's will-it-scale "open1" test. The problem appears to be not so much the increased cond_resched() path length as an increase in the rate at which grace periods complete, which increased per-update grace-period overhead.

This commit takes a different approach to fixing this bug, mainly by avoiding having cond_resched() do an RCU-visible quiescent state unless there is a grace period that has been in flight for a significant period of time. This commit also reduces the common-case cond_resched() overhead to a check of a single per-CPU variable.

<snip>

Quoted 29 lines

index f1ba77363fbb..2cc72ce19ff6 100644

kernel/rcu/tree.c +22 -0

@@ -229,6 +229,58 @@ static DEFINE_PER_CPU(struct rcu_dynticks, rcu_dynticks) = {
 #endif /* #ifdef CONFIG_NO_HZ_FULL_SYSIDLE */
 };
 
+/*
+ * Hooks for cond_resched() and friends to avoid RCU CPU stall warnings.
+ */
+
+DEFINE_PER_CPU(int, rcu_cond_resched_mask);
+
+/*
+ * Let the RCU core know that this CPU has gone through a cond_resched(),
+ * which is a quiescent state.
+ */
+void rcu_resched(void)
+{
+     unsigned long flags;
+     struct rcu_data *rdp;
+     struct rcu_dynticks *rdtp;
+     int resched_mask;
+     struct rcu_state *rsp;
+
+     local_irq_save(flags);
+
+     /*
+      * Yes, we can lose flag-setting operations.  This is OK, because

kernel/rcu/tree.c static DEFINE_PER_CPU(struct rcu_dynticks, rcu_dynticks) = { · line 263

Quoted 10 lines

kernel/rcu/tree.c +10 -0

+      * the flag will be set again after some delay.
+      */
+     resched_mask = raw_cpu_read(rcu_cond_resched_mask);
+     raw_cpu_write(rcu_cond_resched_mask, 0);
+
+     /* Find the flavor that needs a quiescent state. */
+     for_each_rcu_flavor(rsp) {
+             rdp = raw_cpu_ptr(rsp->rda);
+             if (!(resched_mask & rsp->flavor_mask))
+                     continue;

Here both resched_mask and flavor_mask are not being updated within the loop. Are they supposed to be? It is really not clear what flavor_mask is doing in the code.

Quoted 59 lines

kernel/rcu/tree.c +34 -6

+             smp_mb(); /* ->flavor_mask before ->cond_resched_completed. */
+             if (ACCESS_ONCE(rdp->mynode->completed) !=
+                 ACCESS_ONCE(rdp->cond_resched_completed))
+                     continue;
+
+             /*
+              * Pretend to be momentarily idle for the quiescent state.
+              * This allows the grace-period kthread to record the
+              * quiescent state, with no need for this CPU to do anything
+              * further.
+              */
+             rdtp = this_cpu_ptr(&rcu_dynticks);
+             smp_mb__before_atomic(); /* Earlier stuff before QS. */
+             atomic_add(2, &rdtp->dynticks);  /* QS. */
+             smp_mb__after_atomic(); /* Later stuff after QS. */
+             break;
+     }
+     local_irq_restore(flags);
+}
+
 static long blimit = 10;     /* Maximum callbacks per rcu_do_batch. */
 static long qhimark = 10000; /* If this many pending, ignore blimit. */
 static long qlowmark = 100;  /* Once only this many pending, use blimit. */

@@ -853,6 +905,7 @@ static int rcu_implicit_dynticks_qs(struct rcu_data *rdp,
                                  bool *isidle, unsigned long *maxj)
 {
      unsigned int curr;
+     int *rcrmp;
      unsigned int snap;
 
      curr = (unsigned int)atomic_add_return(0, &rdp->dynticks->dynticks);

@@ -893,13 +946,20 @@ static int rcu_implicit_dynticks_qs(struct rcu_data *rdp,
      }
 
      /*
-      * There is a possibility that a CPU in adaptive-ticks state
-      * might run in the kernel with the scheduling-clock tick disabled
-      * for an extended time period.  Invoke rcu_kick_nohz_cpu() to
-      * force the CPU to restart the scheduling-clock tick in this
-      * CPU is in this state.
+      * A CPU running for an extended time within the kernel can
+      * delay RCU grace periods.  When the CPU is in NO_HZ_FULL mode,
+      * even context-switching back and forth between a pair of
+      * in-kernel CPU-bound tasks cannot advance grace periods.
+      * So if the grace period is old enough, make the CPU pay attention.
       */
-     rcu_kick_nohz_cpu(rdp->cpu);
+     if (ULONG_CMP_GE(jiffies, rdp->rsp->gp_start + 7)) {
+             rcrmp = &per_cpu(rcu_cond_resched_mask, rdp->cpu);
+             ACCESS_ONCE(rdp->cond_resched_completed) =
+                     ACCESS_ONCE(rdp->mynode->completed);
+             smp_mb(); /* ->cond_resched_completed before *rcrmp. */
+             ACCESS_ONCE(*rcrmp) =
+                     ACCESS_ONCE(*rcrmp) + rdp->rsp->flavor_mask;
+     }
 
      /*
       * Alternatively, the CPU might be running in the kernel

kernel/rcu/tree.c static void __init rcu_init_one(struct rcu_state *rsp, · line 3554

Quoted 4 lines

kernel/rcu/tree.c +1 -0

@@ -3491,6 +3551,7 @@ static void __init rcu_init_one(struct rcu_state *rsp,
                             "rcu_node_fqs_1",
                             "rcu_node_fqs_2",
                             "rcu_node_fqs_3" };  /* Match MAX_RCU_LVLS */
+     static u8 fl_mask = 0x1;

What does 0x1 mean here? Is it for a particular flavor? This could use a comment.

kernel/rcu/tree.c static void __init rcu_init_one(struct rcu_state *rsp, · line 3574

Quoted 9 lines

kernel/rcu/tree.c +2 -0

      int cpustride = 1;
      int i;
      int j;

@@ -3509,6 +3570,8 @@ static void __init rcu_init_one(struct rcu_state *rsp,
      for (i = 1; i < rcu_num_lvls; i++)
              rsp->level[i] = rsp->level[i - 1] + rsp->levelcnt[i - 1];
      rcu_init_levelspread(rsp);
+     rsp->flavor_mask = fl_mask;
+     fl_mask <<= 1;

Something looks off here. fl_mask is not being used after this. Was it supposed to be used or is it just a stray statement?

The flavor_mask operations could really use some comments as it is not really clear what is being achieved by that.

--
Pranith

Quoted 74 lines

kernel/rcu/tree.c +0 -0

      /* Initialize the elements themselves, starting from the leaves. */
 

kernel/rcu/tree.h +5 -1

index bf2c1e669691..0f69a79c5b7d 100644
@@ -307,6 +307,9 @@ struct rcu_data {
      /* 4) reasons this CPU needed to be kicked by force_quiescent_state */
      unsigned long dynticks_fqs;     /* Kicked due to dynticks idle. */
      unsigned long offline_fqs;      /* Kicked due to being offline. */
+     unsigned long cond_resched_completed;
+                                     /* Grace period that needs help */
+                                     /*  from cond_resched(). */
 
      /* 5) __rcu_pending() statistics. */
      unsigned long n_rcu_pending;    /* rcu_pending() calls since boot. */

@@ -392,6 +395,7 @@ struct rcu_state {
      struct rcu_node *level[RCU_NUM_LVLS];   /* Hierarchy levels. */
      u32 levelcnt[MAX_RCU_LVLS + 1];         /* # nodes in each level. */
      u8 levelspread[RCU_NUM_LVLS];           /* kids/node in each level. */
+     u8 flavor_mask;                         /* bit in flavor mask. */
      struct rcu_data __percpu *rda;          /* pointer of percu rcu_data. */
      void (*call)(struct rcu_head *head,     /* call_rcu() flavor. */
                   void (*func)(struct rcu_head *head));

@@ -563,7 +567,7 @@ static bool rcu_nocb_need_deferred_wakeup(struct rcu_data *rdp);
 static void do_nocb_deferred_wakeup(struct rcu_data *rdp);
 static void rcu_boot_init_nocb_percpu_data(struct rcu_data *rdp);
 static void rcu_spawn_nocb_kthreads(struct rcu_state *rsp);
-static void rcu_kick_nohz_cpu(int cpu);
+static void __maybe_unused rcu_kick_nohz_cpu(int cpu);
 static bool init_nocb_callback_list(struct rcu_data *rdp);
 static void rcu_sysidle_enter(struct rcu_dynticks *rdtp, int irq);
 static void rcu_sysidle_exit(struct rcu_dynticks *rdtp, int irq);

kernel/rcu/tree_plugin.h +1 -1

index cbc2c45265e2..02ac0fb186b8 100644
@@ -2404,7 +2404,7 @@ static bool init_nocb_callback_list(struct rcu_data *rdp)
  * if an adaptive-ticks CPU is failing to respond to the current grace
  * period and has not be idle from an RCU perspective, kick it.
  */
-static void rcu_kick_nohz_cpu(int cpu)
+static void __maybe_unused rcu_kick_nohz_cpu(int cpu)
 {
 #ifdef CONFIG_NO_HZ_FULL
      if (tick_nohz_full_cpu(cpu))

kernel/rcu/update.c +0 -18

index a2aeb4df0f60..d22309cae9f5 100644
@@ -350,21 +350,3 @@ static int __init check_cpu_stall_init(void)
 early_initcall(check_cpu_stall_init);
 
 #endif /* #ifdef CONFIG_RCU_STALL_COMMON */
-
-/*
- * Hooks for cond_resched() and friends to avoid RCU CPU stall warnings.
- */
-
-DEFINE_PER_CPU(int, rcu_cond_resched_count);
-
-/*
- * Report a set of RCU quiescent states, for use by cond_resched()
- * and friends.  Out of line due to being called infrequently.
- */
-void rcu_resched(void)
-{
-     preempt_disable();
-     __this_cpu_write(rcu_cond_resched_count, 0);
-     rcu_note_context_switch(smp_processor_id());
-     preempt_enable();
-}

Hi Paul,

I was going through this code and found a few inconsistencies. I git blamed it and found that it was this recent commit and thought I could ask a few questions. I am dropping the CC's as I am not sure since it is pretty late.

Please find a few questions below:

Quoted 17 lines · Paul E. McKenney

From: "Paul E. McKenney" <[email protected]>

Commit ac1bea85781e (Make cond_resched() report RCU quiescent states) fixed a problem where a CPU looping in the kernel with but one runnable task would give RCU CPU stall warnings, even if the in-kernel loop contained cond_resched() calls. Unfortunately, in so doing, it introduced performance regressions in Anton Blanchard's will-it-scale "open1" test. The problem appears to be not so much the increased cond_resched() path length as an increase in the rate at which grace periods complete, which increased per-update grace-period overhead.

This commit takes a different approach to fixing this bug, mainly by avoiding having cond_resched() do an RCU-visible quiescent state unless there is a grace period that has been in flight for a significant period of time. This commit also reduces the common-case cond_resched() overhead to a check of a single per-CPU variable.

<snip>

Quoted 35 lines

index f1ba77363fbb..2cc72ce19ff6 100644

kernel/rcu/tree.c +28 -0

@@ -229,6 +229,58 @@ static DEFINE_PER_CPU(struct rcu_dynticks, rcu_dynticks) = {
 #endif /* #ifdef CONFIG_NO_HZ_FULL_SYSIDLE */
 };
 
+/*
+ * Hooks for cond_resched() and friends to avoid RCU CPU stall warnings.
+ */
+
+DEFINE_PER_CPU(int, rcu_cond_resched_mask);
+
+/*
+ * Let the RCU core know that this CPU has gone through a cond_resched(),
+ * which is a quiescent state.
+ */
+void rcu_resched(void)
+{
+	unsigned long flags;
+	struct rcu_data *rdp;
+	struct rcu_dynticks *rdtp;
+	int resched_mask;
+	struct rcu_state *rsp;
+
+	local_irq_save(flags);
+
+	/*
+	 * Yes, we can lose flag-setting operations.  This is OK, because
+	 * the flag will be set again after some delay.
+	 */
+	resched_mask = raw_cpu_read(rcu_cond_resched_mask);
+	raw_cpu_write(rcu_cond_resched_mask, 0);
+
+	/* Find the flavor that needs a quiescent state. */

kernel/rcu/tree.c static DEFINE_PER_CPU(struct rcu_dynticks, rcu_dynticks) = { · line 263

Quoted 4 lines

kernel/rcu/tree.c +4 -0

+	for_each_rcu_flavor(rsp) {
+		rdp = raw_cpu_ptr(rsp->rda);
+		if (!(resched_mask & rsp->flavor_mask))
+			continue;

Here both resched_mask and flavor_mask are not being updated within the loop. Are they supposed to be? It is really not clear what flavor_mask is doing in the code.

Quoted 56 lines

kernel/rcu/tree.c +34 -6

+		smp_mb(); /* ->flavor_mask before ->cond_resched_completed. */
+		if (ACCESS_ONCE(rdp->mynode->completed) !=
+		    ACCESS_ONCE(rdp->cond_resched_completed))
+			continue;
+
+		/*
+		 * Pretend to be momentarily idle for the quiescent state.
+		 * This allows the grace-period kthread to record the
+		 * quiescent state, with no need for this CPU to do anything
+		 * further.
+		 */
+		rdtp = this_cpu_ptr(&rcu_dynticks);
+		smp_mb__before_atomic(); /* Earlier stuff before QS. */
+		atomic_add(2, &rdtp->dynticks);  /* QS. */
+		smp_mb__after_atomic(); /* Later stuff after QS. */
+		break;
+	}
+	local_irq_restore(flags);
+}
+
 static long blimit = 10;	/* Maximum callbacks per rcu_do_batch. */
 static long qhimark = 10000;	/* If this many pending, ignore blimit. */
 static long qlowmark = 100;	/* Once only this many pending, use blimit. */

@@ -853,6 +905,7 @@ static int rcu_implicit_dynticks_qs(struct rcu_data *rdp,
 				    bool *isidle, unsigned long *maxj)
 {
 	unsigned int curr;
+	int *rcrmp;
 	unsigned int snap;
 
 	curr = (unsigned int)atomic_add_return(0, &rdp->dynticks->dynticks);

@@ -893,13 +946,20 @@ static int rcu_implicit_dynticks_qs(struct rcu_data *rdp,
 	}
 
 	/*
-	 * There is a possibility that a CPU in adaptive-ticks state
-	 * might run in the kernel with the scheduling-clock tick disabled
-	 * for an extended time period.  Invoke rcu_kick_nohz_cpu() to
-	 * force the CPU to restart the scheduling-clock tick in this
-	 * CPU is in this state.
+	 * A CPU running for an extended time within the kernel can
+	 * delay RCU grace periods.  When the CPU is in NO_HZ_FULL mode,
+	 * even context-switching back and forth between a pair of
+	 * in-kernel CPU-bound tasks cannot advance grace periods.
+	 * So if the grace period is old enough, make the CPU pay attention.
 	 */
-	rcu_kick_nohz_cpu(rdp->cpu);
+	if (ULONG_CMP_GE(jiffies, rdp->rsp->gp_start + 7)) {
+		rcrmp = &per_cpu(rcu_cond_resched_mask, rdp->cpu);
+		ACCESS_ONCE(rdp->cond_resched_completed) =
+			ACCESS_ONCE(rdp->mynode->completed);
+		smp_mb(); /* ->cond_resched_completed before *rcrmp. */
+		ACCESS_ONCE(*rcrmp) =
+			ACCESS_ONCE(*rcrmp) + rdp->rsp->flavor_mask;
+	}
 

kernel/rcu/tree.c static void __init rcu_init_one(struct rcu_state *rsp, · line 3554

Quoted 7 lines

kernel/rcu/tree.c +1 -0

 	/*
 	 * Alternatively, the CPU might be running in the kernel

@@ -3491,6 +3551,7 @@ static void __init rcu_init_one(struct rcu_state *rsp,
 			       "rcu_node_fqs_1",
 			       "rcu_node_fqs_2",
 			       "rcu_node_fqs_3" };  /* Match MAX_RCU_LVLS */
+	static u8 fl_mask = 0x1;

What does 0x1 mean here? Is it for a particular flavor? This could use a comment.

Quoted 4 lines

kernel/rcu/tree.c +0 -0

 	int cpustride = 1;
 	int i;
 	int j;

@@ -3509,6 +3570,8 @@ static void __init rcu_init_one(struct rcu_state *rsp,

kernel/rcu/tree.c static void __init rcu_init_one(struct rcu_state *rsp, · line 3574

Quoted 5 lines

kernel/rcu/tree.c +2 -0

 	for (i = 1; i < rcu_num_lvls; i++)
 		rsp->level[i] = rsp->level[i - 1] + rsp->levelcnt[i - 1];
 	rcu_init_levelspread(rsp);
+	rsp->flavor_mask = fl_mask;
+	fl_mask <<= 1;

Something looks off here. fl_mask is not being used after this. Was it supposed to be used or is it just a stray statement?

The flavor_mask operations could really use some comments as it is not really clear what is being achieved by that.

--
Pranith

Quoted 74 lines

kernel/rcu/tree.c +0 -0

 	/* Initialize the elements themselves, starting from the leaves. */
 

kernel/rcu/tree.h +5 -1

index bf2c1e669691..0f69a79c5b7d 100644
@@ -307,6 +307,9 @@ struct rcu_data {
 	/* 4) reasons this CPU needed to be kicked by force_quiescent_state */
 	unsigned long dynticks_fqs;	/* Kicked due to dynticks idle. */
 	unsigned long offline_fqs;	/* Kicked due to being offline. */
+	unsigned long cond_resched_completed;
+					/* Grace period that needs help */
+					/*  from cond_resched(). */
 
 	/* 5) __rcu_pending() statistics. */
 	unsigned long n_rcu_pending;	/* rcu_pending() calls since boot. */

@@ -392,6 +395,7 @@ struct rcu_state {
 	struct rcu_node *level[RCU_NUM_LVLS];	/* Hierarchy levels. */
 	u32 levelcnt[MAX_RCU_LVLS + 1];		/* # nodes in each level. */
 	u8 levelspread[RCU_NUM_LVLS];		/* kids/node in each level. */
+	u8 flavor_mask;				/* bit in flavor mask. */
 	struct rcu_data __percpu *rda;		/* pointer of percu rcu_data. */
 	void (*call)(struct rcu_head *head,	/* call_rcu() flavor. */
 		     void (*func)(struct rcu_head *head));

@@ -563,7 +567,7 @@ static bool rcu_nocb_need_deferred_wakeup(struct rcu_data *rdp);
 static void do_nocb_deferred_wakeup(struct rcu_data *rdp);
 static void rcu_boot_init_nocb_percpu_data(struct rcu_data *rdp);
 static void rcu_spawn_nocb_kthreads(struct rcu_state *rsp);
-static void rcu_kick_nohz_cpu(int cpu);
+static void __maybe_unused rcu_kick_nohz_cpu(int cpu);
 static bool init_nocb_callback_list(struct rcu_data *rdp);
 static void rcu_sysidle_enter(struct rcu_dynticks *rdtp, int irq);
 static void rcu_sysidle_exit(struct rcu_dynticks *rdtp, int irq);

kernel/rcu/tree_plugin.h +1 -1

index cbc2c45265e2..02ac0fb186b8 100644
@@ -2404,7 +2404,7 @@ static bool init_nocb_callback_list(struct rcu_data *rdp)
  * if an adaptive-ticks CPU is failing to respond to the current grace
  * period and has not be idle from an RCU perspective, kick it.
  */
-static void rcu_kick_nohz_cpu(int cpu)
+static void __maybe_unused rcu_kick_nohz_cpu(int cpu)
 {
 #ifdef CONFIG_NO_HZ_FULL
 	if (tick_nohz_full_cpu(cpu))

kernel/rcu/update.c +0 -18

index a2aeb4df0f60..d22309cae9f5 100644
@@ -350,21 +350,3 @@ static int __init check_cpu_stall_init(void)
 early_initcall(check_cpu_stall_init);
 
 #endif /* #ifdef CONFIG_RCU_STALL_COMMON */
-
-/*
- * Hooks for cond_resched() and friends to avoid RCU CPU stall warnings.
- */
-
-DEFINE_PER_CPU(int, rcu_cond_resched_count);
-
-/*
- * Report a set of RCU quiescent states, for use by cond_resched()
- * and friends.  Out of line due to being called infrequently.
- */
-void rcu_resched(void)
-{
-	preempt_disable();
-	__this_cpu_write(rcu_cond_resched_count, 0);
-	rcu_note_context_switch(smp_processor_id());
-	preempt_enable();
-}

Doh! I figured it out *after* I sent out the mail. Sorry for the noise!

Quoted 233 lines

Hi Paul,

I was going through this code and found a few inconsistencies. I git blamed it and found that it was this recent commit and thought I could ask a few questions. I am dropping the CC's as I am not sure since it is pretty late.

Please find a few questions below:

Quoted 17 lines · Paul E. McKenney

From: "Paul E. McKenney" <[email protected]>

Commit ac1bea85781e (Make cond_resched() report RCU quiescent states) fixed a problem where a CPU looping in the kernel with but one runnable task would give RCU CPU stall warnings, even if the in-kernel loop contained cond_resched() calls. Unfortunately, in so doing, it introduced performance regressions in Anton Blanchard's will-it-scale "open1" test. The problem appears to be not so much the increased cond_resched() path length as an increase in the rate at which grace periods complete, which increased per-update grace-period overhead.

This commit takes a different approach to fixing this bug, mainly by avoiding having cond_resched() do an RCU-visible quiescent state unless there is a grace period that has been in flight for a significant period of time. This commit also reduces the common-case cond_resched() overhead to a check of a single per-CPU variable.

<snip>

Quoted 29 lines

index f1ba77363fbb..2cc72ce19ff6 100644

kernel/rcu/tree.c +22 -0

@@ -229,6 +229,58 @@ static DEFINE_PER_CPU(struct rcu_dynticks, rcu_dynticks) = {
 #endif /* #ifdef CONFIG_NO_HZ_FULL_SYSIDLE */
 };
 
+/*
+ * Hooks for cond_resched() and friends to avoid RCU CPU stall warnings.
+ */
+
+DEFINE_PER_CPU(int, rcu_cond_resched_mask);
+
+/*
+ * Let the RCU core know that this CPU has gone through a cond_resched(),
+ * which is a quiescent state.
+ */
+void rcu_resched(void)
+{
+     unsigned long flags;
+     struct rcu_data *rdp;
+     struct rcu_dynticks *rdtp;
+     int resched_mask;
+     struct rcu_state *rsp;
+
+     local_irq_save(flags);
+
+     /*
+      * Yes, we can lose flag-setting operations.  This is OK, because

kernel/rcu/tree.c static DEFINE_PER_CPU(struct rcu_dynticks, rcu_dynticks) = { · line 263

Quoted 10 lines

kernel/rcu/tree.c +10 -0

+      * the flag will be set again after some delay.
+      */
+     resched_mask = raw_cpu_read(rcu_cond_resched_mask);
+     raw_cpu_write(rcu_cond_resched_mask, 0);
+
+     /* Find the flavor that needs a quiescent state. */
+     for_each_rcu_flavor(rsp) {
+             rdp = raw_cpu_ptr(rsp->rda);
+             if (!(resched_mask & rsp->flavor_mask))
+                     continue;

Here both resched_mask and flavor_mask are not being updated within the loop. Are they supposed to be? It is really not clear what flavor_mask is doing in the code.

Quoted 59 lines

kernel/rcu/tree.c +34 -6

+             smp_mb(); /* ->flavor_mask before ->cond_resched_completed. */
+             if (ACCESS_ONCE(rdp->mynode->completed) !=
+                 ACCESS_ONCE(rdp->cond_resched_completed))
+                     continue;
+
+             /*
+              * Pretend to be momentarily idle for the quiescent state.
+              * This allows the grace-period kthread to record the
+              * quiescent state, with no need for this CPU to do anything
+              * further.
+              */
+             rdtp = this_cpu_ptr(&rcu_dynticks);
+             smp_mb__before_atomic(); /* Earlier stuff before QS. */
+             atomic_add(2, &rdtp->dynticks);  /* QS. */
+             smp_mb__after_atomic(); /* Later stuff after QS. */
+             break;
+     }
+     local_irq_restore(flags);
+}
+
 static long blimit = 10;     /* Maximum callbacks per rcu_do_batch. */
 static long qhimark = 10000; /* If this many pending, ignore blimit. */
 static long qlowmark = 100;  /* Once only this many pending, use blimit. */

@@ -853,6 +905,7 @@ static int rcu_implicit_dynticks_qs(struct rcu_data *rdp,
                                  bool *isidle, unsigned long *maxj)
 {
      unsigned int curr;
+     int *rcrmp;
      unsigned int snap;
 
      curr = (unsigned int)atomic_add_return(0, &rdp->dynticks->dynticks);

@@ -893,13 +946,20 @@ static int rcu_implicit_dynticks_qs(struct rcu_data *rdp,
      }
 
      /*
-      * There is a possibility that a CPU in adaptive-ticks state
-      * might run in the kernel with the scheduling-clock tick disabled
-      * for an extended time period.  Invoke rcu_kick_nohz_cpu() to
-      * force the CPU to restart the scheduling-clock tick in this
-      * CPU is in this state.
+      * A CPU running for an extended time within the kernel can
+      * delay RCU grace periods.  When the CPU is in NO_HZ_FULL mode,
+      * even context-switching back and forth between a pair of
+      * in-kernel CPU-bound tasks cannot advance grace periods.
+      * So if the grace period is old enough, make the CPU pay attention.
       */
-     rcu_kick_nohz_cpu(rdp->cpu);
+     if (ULONG_CMP_GE(jiffies, rdp->rsp->gp_start + 7)) {
+             rcrmp = &per_cpu(rcu_cond_resched_mask, rdp->cpu);
+             ACCESS_ONCE(rdp->cond_resched_completed) =
+                     ACCESS_ONCE(rdp->mynode->completed);
+             smp_mb(); /* ->cond_resched_completed before *rcrmp. */
+             ACCESS_ONCE(*rcrmp) =
+                     ACCESS_ONCE(*rcrmp) + rdp->rsp->flavor_mask;
+     }
 
      /*
       * Alternatively, the CPU might be running in the kernel

kernel/rcu/tree.c static void __init rcu_init_one(struct rcu_state *rsp, · line 3554

Quoted 4 lines

kernel/rcu/tree.c +1 -0

@@ -3491,6 +3551,7 @@ static void __init rcu_init_one(struct rcu_state *rsp,
                             "rcu_node_fqs_1",
                             "rcu_node_fqs_2",
                             "rcu_node_fqs_3" };  /* Match MAX_RCU_LVLS */
+     static u8 fl_mask = 0x1;

What does 0x1 mean here? Is it for a particular flavor? This could use a comment.

kernel/rcu/tree.c static void __init rcu_init_one(struct rcu_state *rsp, · line 3574

Quoted 9 lines

kernel/rcu/tree.c +2 -0

      int cpustride = 1;
      int i;
      int j;

@@ -3509,6 +3570,8 @@ static void __init rcu_init_one(struct rcu_state *rsp,
      for (i = 1; i < rcu_num_lvls; i++)
              rsp->level[i] = rsp->level[i - 1] + rsp->levelcnt[i - 1];
      rcu_init_levelspread(rsp);
+     rsp->flavor_mask = fl_mask;
+     fl_mask <<= 1;

Something looks off here. fl_mask is not being used after this. Was it supposed to be used or is it just a stray statement?

The flavor_mask operations could really use some comments as it is not really clear what is being achieved by that.

--
Pranith

Quoted 74 lines

kernel/rcu/tree.c +0 -0

      /* Initialize the elements themselves, starting from the leaves. */
 

kernel/rcu/tree.h +5 -1

index bf2c1e669691..0f69a79c5b7d 100644
@@ -307,6 +307,9 @@ struct rcu_data {
      /* 4) reasons this CPU needed to be kicked by force_quiescent_state */
      unsigned long dynticks_fqs;     /* Kicked due to dynticks idle. */
      unsigned long offline_fqs;      /* Kicked due to being offline. */
+     unsigned long cond_resched_completed;
+                                     /* Grace period that needs help */
+                                     /*  from cond_resched(). */
 
      /* 5) __rcu_pending() statistics. */
      unsigned long n_rcu_pending;    /* rcu_pending() calls since boot. */

@@ -392,6 +395,7 @@ struct rcu_state {
      struct rcu_node *level[RCU_NUM_LVLS];   /* Hierarchy levels. */
      u32 levelcnt[MAX_RCU_LVLS + 1];         /* # nodes in each level. */
      u8 levelspread[RCU_NUM_LVLS];           /* kids/node in each level. */
+     u8 flavor_mask;                         /* bit in flavor mask. */
      struct rcu_data __percpu *rda;          /* pointer of percu rcu_data. */
      void (*call)(struct rcu_head *head,     /* call_rcu() flavor. */
                   void (*func)(struct rcu_head *head));

@@ -563,7 +567,7 @@ static bool rcu_nocb_need_deferred_wakeup(struct rcu_data *rdp);
 static void do_nocb_deferred_wakeup(struct rcu_data *rdp);
 static void rcu_boot_init_nocb_percpu_data(struct rcu_data *rdp);
 static void rcu_spawn_nocb_kthreads(struct rcu_state *rsp);
-static void rcu_kick_nohz_cpu(int cpu);
+static void __maybe_unused rcu_kick_nohz_cpu(int cpu);
 static bool init_nocb_callback_list(struct rcu_data *rdp);
 static void rcu_sysidle_enter(struct rcu_dynticks *rdtp, int irq);
 static void rcu_sysidle_exit(struct rcu_dynticks *rdtp, int irq);

kernel/rcu/tree_plugin.h +1 -1

index cbc2c45265e2..02ac0fb186b8 100644
@@ -2404,7 +2404,7 @@ static bool init_nocb_callback_list(struct rcu_data *rdp)
  * if an adaptive-ticks CPU is failing to respond to the current grace
  * period and has not be idle from an RCU perspective, kick it.
  */
-static void rcu_kick_nohz_cpu(int cpu)
+static void __maybe_unused rcu_kick_nohz_cpu(int cpu)
 {
 #ifdef CONFIG_NO_HZ_FULL
      if (tick_nohz_full_cpu(cpu))

kernel/rcu/update.c +0 -18

index a2aeb4df0f60..d22309cae9f5 100644
@@ -350,21 +350,3 @@ static int __init check_cpu_stall_init(void)
 early_initcall(check_cpu_stall_init);
 
 #endif /* #ifdef CONFIG_RCU_STALL_COMMON */
-
-/*
- * Hooks for cond_resched() and friends to avoid RCU CPU stall warnings.
- */
-
-DEFINE_PER_CPU(int, rcu_cond_resched_count);
-
-/*
- * Report a set of RCU quiescent states, for use by cond_resched()
- * and friends.  Out of line due to being called infrequently.
- */
-void rcu_resched(void)
-{
-     preempt_disable();
-     __this_cpu_write(rcu_cond_resched_count, 0);
-     rcu_note_context_switch(smp_processor_id());
-     preempt_enable();
-}

Signature · 1 line

Pranith