v2 Provide infrastructure for full-system idle

The individual patches are as follows:

1. Add a CONFIG_NO_HZ_FULL_SYSIDLE Kconfig parameter to enable
this feature. Kernels built with CONFIG_NO_HZ_FULL_SYSIDLE=n act exactly as they do today.

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

This commit adds fields to the rcu_dyntick structure that are used to detect idle CPUs. These new fields differ from the existing ones in that the existing ones consider a CPU executing in user mode to be idle, where the new ones consider CPUs executing in user mode to be busy.

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

This commit adds the code that updates the rcu_dyntick structure's new fields to track the per-CPU idle state based on interrupts and transitions into and out of the idle loop (NMIs are ignored because NMI handlers cannot cleanly read out the time anyway). This code is similar to the code that maintains RCU's idea of per-CPU idleness, but differs in that RCU treats CPUs running in user mode as idle, where this new code does not.

Quoted 6 lines · Paul E. McKenney

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

This commit adds fields to the rcu_dyntick structure that are used to detect idle CPUs. These new fields differ from the existing ones in that the existing ones consider a CPU executing in user mode to be idle, where the new ones consider CPUs executing in user mode to be busy.

Can you explain, both in the commit messages and in the comments added by the next commit, *why* this code doesn't consider userspace a quiescent state?

Quoted 6 lines · Paul E. McKenney

The individual patches are as follows:

1. Add a CONFIG_NO_HZ_FULL_SYSIDLE Kconfig parameter to enable
this feature. Kernels built with CONFIG_NO_HZ_FULL_SYSIDLE=n act exactly as they do today.

Is this extra CONFIG option really needed? RCU already has a bewildering variety of CONFIG options, and no idle CONFIG is also pretty complicated. At some point noone will know how to configure kernels anymore if these non trivial, complicated trade off CONFIGs keep spreading.

The facility sounds like a good thing in general. Just enable it implicitely with NO_HZ_SYSIDLE ?

If you want a switch for testing I would advise a sysctl or sysfs knob

I am guessing that you want CONFIG_NO_HZ_FULL to implicitly enable the sysidle code so that CONFIG_NO_HZ_FULL_SYSIDLE can be eliminated. I will be happy to take that step, but only after I gain full confidence in the correctness and performance of the sysidle code.

Quoted 1 line

If you want a switch for testing I would advise a sysctl or sysfs knob

This would work well for the correctness part, but not for the performance part.

/*
+ * Unconditionally force exit from full system-idle state. This is
+ * invoked when a normal CPU exits idle, but must be called separately
+ * for the timekeeping CPU (tick_do_timer_cpu). The reason for this
+ * is that the timekeeping CPU is permitted to take scheduling-clock
+ * interrupts while the system is in system-idle state, and of course
+ * rcu_sysidle_exit() has no way of distinguishing a scheduling-clock
+ * interrupt from any other type of interrupt.
+ */

kernel/rcutree_plugin.h +64 -0

+void rcu_sysidle_force_exit(void)
+{
+	int oldstate = ACCESS_ONCE(full_sysidle_state);
+	int newoldstate;
+
+	/*
+	 * Each pass through the following loop attempts to exit full
+	 * system-idle state.  If contention proves to be a problem,
+	 * a trylock-based contention tree could be used here.
+	 */
+	while (oldstate > RCU_SYSIDLE_SHORT) {
+		newoldstate = cmpxchg(&full_sysidle_state,
+				      oldstate, RCU_SYSIDLE_NOT);
+		if (oldstate == newoldstate &&
+		    oldstate == RCU_SYSIDLE_FULL_NOTED) {
+			rcu_kick_nohz_cpu(tick_do_timer_cpu);
+			return; /* We cleared it, done! */
+		}
+		oldstate = newoldstate;
+	}
+	smp_mb(); /* Order initial oldstate fetch vs. later non-idle work. */
+}
+
+/*
  * Invoked to note entry to irq or task transition from idle.  Note that
  * usermode execution does -not- count as idle here!  The caller must
  * have disabled interrupts.

@@ -2474,6 +2506,214 @@ static void rcu_sysidle_exit(struct rcu_dynticks *rdtp, int irq)
 	atomic_inc(&rdtp->dynticks_idle);
 	smp_mb__after_atomic_inc();
 	WARN_ON_ONCE(!(atomic_read(&rdtp->dynticks_idle) & 0x1));
+
+	/*
+	 * If we are the timekeeping CPU, we are permitted to be non-idle
+	 * during a system-idle state.  This must be the case, because
+	 * the timekeeping CPU has to take scheduling-clock interrupts
+	 * during the time that the system is transitioning to full
+	 * system-idle state.  This means that the timekeeping CPU must
+	 * invoke rcu_sysidle_force_exit() directly if it does anything
+	 * more than take a scheduling-clock interrupt.
+	 */
+	if (smp_processor_id() == tick_do_timer_cpu)
+		return;
+
+	/* Update system-idle state: We are clearly no longer fully idle! */
+	rcu_sysidle_force_exit();
+}
+
+/*
+ * Check to see if the current CPU is idle.  Note that usermode execution
+ * does not count as idle.  The caller must have disabled interrupts.
+ */
+static void rcu_sysidle_check_cpu(struct rcu_data *rdp, bool *isidle,
+				  unsigned long *maxj)
+{
+	int cur;
+	int curnmi;
+	unsigned long j;
+	struct rcu_dynticks *rdtp = rdp->dynticks;
+
+	/*
+	 * If some other CPU has already reported non-idle, if this is
+	 * not the flavor of RCU that tracks sysidle state, or if this
+	 * is an offline or the timekeeping CPU, nothing to do.
+	 */
+	if (!*isidle || rdp->rsp != rcu_sysidle_state ||
+	    cpu_is_offline(rdp->cpu) || rdp->cpu == tick_do_timer_cpu)
+		return;
+	/* WARN_ON_ONCE(smp_processor_id() != tick_do_timer_cpu); */
+
+	/*

kernel/rcutree_plugin.h +17 -0

+
+/*
+ * Check to see if the system is fully idle, other than the timekeeping CPU.
+ * The caller must have disabled interrupts.
+ */
+bool rcu_sys_is_idle(void)
+{
+	static struct rcu_sysidle_head rsh;
+	int rss = ACCESS_ONCE(full_sysidle_state);
+
+	WARN_ON_ONCE(smp_processor_id() != tick_do_timer_cpu);
+
+	/* Handle small-system case by doing a full scan of CPUs. */
+	if (nr_cpu_ids <= RCU_SYSIDLE_SMALL && rss < RCU_SYSIDLE_FULL) {
+		int cpu;
+		bool isidle = true;
+		unsigned long maxj = jiffies - ULONG_MAX / 4;

kernel/rcutree_plugin.h +41 -0

+		rss = ACCESS_ONCE(full_sysidle_state);
+	}
+
+	/* If this is the first observation of an idle period, record it. */
+	if (rss == RCU_SYSIDLE_FULL) {
+		rss = cmpxchg(&full_sysidle_state,
+			      RCU_SYSIDLE_FULL, RCU_SYSIDLE_FULL_NOTED);
+		return rss == RCU_SYSIDLE_FULL;
+	}
+
+	smp_mb(); /* ensure rss load happens before later caller actions. */
+
+	/* If already fully idle, tell the caller (in case of races). */
+	if (rss == RCU_SYSIDLE_FULL_NOTED)
+		return true;
+
+	/*
+	 * If we aren't there yet, and a grace period is not in flight,
+	 * initiate a grace period.  Either way, tell the caller that
+	 * we are not there yet.
+	 */
+	if (nr_cpu_ids > RCU_SYSIDLE_SMALL &&
+	    !rcu_gp_in_progress(rcu_sysidle_state) &&
+	    !rsh.inuse && xchg(&rsh.inuse, 1) == 0)
+		call_rcu(&rsh.rh, rcu_sysidle_cb);
+	return false;
 }
 
 /*

@@ -2494,6 +2734,21 @@ static void rcu_sysidle_exit(struct rcu_dynticks *rdtp, int irq)
 {
 }
 
+static void rcu_sysidle_check_cpu(struct rcu_data *rdp, bool *isidle,
+				  unsigned long *maxj)
+{
+}
+
+static bool is_sysidle_rcu_state(struct rcu_state *rsp)
+{
+	return false;
+}
+
+static void rcu_sysidle_report(struct rcu_state *rsp, int isidle,
+			       unsigned long maxj)
+{
+}
+
 static void rcu_sysidle_init_percpu_data(struct rcu_dynticks *rdtp)
 {
 }

Signature · 1 line

1.8.1.5

Quoted 80 lines · Paul E. McKenney

/*
+ * Unconditionally force exit from full system-idle state. This is
+ * invoked when a normal CPU exits idle, but must be called separately
+ * for the timekeeping CPU (tick_do_timer_cpu). The reason for this
+ * is that the timekeeping CPU is permitted to take scheduling-clock
+ * interrupts while the system is in system-idle state, and of course
+ * rcu_sysidle_exit() has no way of distinguishing a scheduling-clock
+ * interrupt from any other type of interrupt.
+ */

kernel/rcutree_plugin.h +64 -0

+void rcu_sysidle_force_exit(void)
+{
+	int oldstate = ACCESS_ONCE(full_sysidle_state);
+	int newoldstate;
+
+	/*
+	 * Each pass through the following loop attempts to exit full
+	 * system-idle state.  If contention proves to be a problem,
+	 * a trylock-based contention tree could be used here.
+	 */
+	while (oldstate > RCU_SYSIDLE_SHORT) {
+		newoldstate = cmpxchg(&full_sysidle_state,
+				      oldstate, RCU_SYSIDLE_NOT);
+		if (oldstate == newoldstate &&
+		    oldstate == RCU_SYSIDLE_FULL_NOTED) {
+			rcu_kick_nohz_cpu(tick_do_timer_cpu);
+			return; /* We cleared it, done! */
+		}
+		oldstate = newoldstate;
+	}
+	smp_mb(); /* Order initial oldstate fetch vs. later non-idle work. */
+}
+
+/*
  * Invoked to note entry to irq or task transition from idle.  Note that
  * usermode execution does -not- count as idle here!  The caller must
  * have disabled interrupts.

@@ -2474,6 +2506,214 @@ static void rcu_sysidle_exit(struct rcu_dynticks *rdtp, int irq)
 	atomic_inc(&rdtp->dynticks_idle);
 	smp_mb__after_atomic_inc();
 	WARN_ON_ONCE(!(atomic_read(&rdtp->dynticks_idle) & 0x1));
+
+	/*
+	 * If we are the timekeeping CPU, we are permitted to be non-idle
+	 * during a system-idle state.  This must be the case, because
+	 * the timekeeping CPU has to take scheduling-clock interrupts
+	 * during the time that the system is transitioning to full
+	 * system-idle state.  This means that the timekeeping CPU must
+	 * invoke rcu_sysidle_force_exit() directly if it does anything
+	 * more than take a scheduling-clock interrupt.
+	 */
+	if (smp_processor_id() == tick_do_timer_cpu)
+		return;
+
+	/* Update system-idle state: We are clearly no longer fully idle! */
+	rcu_sysidle_force_exit();
+}
+
+/*
+ * Check to see if the current CPU is idle.  Note that usermode execution
+ * does not count as idle.  The caller must have disabled interrupts.
+ */
+static void rcu_sysidle_check_cpu(struct rcu_data *rdp, bool *isidle,
+				  unsigned long *maxj)
+{
+	int cur;
+	int curnmi;
+	unsigned long j;
+	struct rcu_dynticks *rdtp = rdp->dynticks;
+
+	/*
+	 * If some other CPU has already reported non-idle, if this is
+	 * not the flavor of RCU that tracks sysidle state, or if this
+	 * is an offline or the timekeeping CPU, nothing to do.
+	 */
+	if (!*isidle || rdp->rsp != rcu_sysidle_state ||
+	    cpu_is_offline(rdp->cpu) || rdp->cpu == tick_do_timer_cpu)
+		return;
+	/* WARN_ON_ONCE(smp_processor_id() != tick_do_timer_cpu); */
+
+	/*

kernel/rcutree_plugin.h static void rcu_sysidle_exit(struct rcu_dynticks *rdtp, int irq) · line 2558

Quoted 10 lines

kernel/rcutree_plugin.h +10 -0

+	 * Pick up current idle and NMI-nesting counters, check.  We check
+	 * for NMIs using RCU's main ->dynticks counter.  This works because
+	 * any time ->dynticks has its low bit set, ->dynticks_idle will
+	 * too -- unless the only reason that ->dynticks's low bit is set
+	 * is due to an NMI from idle.  Which is exactly the case we need
+	 * to account for.
+	 */
+	cur = atomic_read(&rdtp->dynticks_idle);
+	curnmi = atomic_read(&rdtp->dynticks);
+	if ((cur & 0x1) || (curnmi & 0x1)) {

I think you wanted to ignore NMIs this time because they don't read walltime?

By the way they can still read jiffies, but unlike irq_enter(), nmi_enter() don't catch up with missing jiffies update. So the behaviour doesn't change compared to !NO_HZ_FULL.

kernel/rcutree_plugin.h static void rcu_sysidle_exit(struct rcu_dynticks *rdtp, int irq) · line 2568

Quoted 10 lines

kernel/rcutree_plugin.h +10 -0

+		*isidle = 0; /* We are not idle! */
+		return;
+	}
+	smp_mb(); /* Read counters before timestamps. */
+
+	/* Pick up timestamps. */
+	j = ACCESS_ONCE(rdtp->dynticks_idle_jiffies);
+	/* If this CPU entered idle more recently, update maxj timestamp. */
+	if (ULONG_CMP_LT(*maxj, j))
+		*maxj = j;

So I'm a bit confused with the ordering so I'm probably going to ask a silly question.

What makes sure that we are not reading a stale value of rdtp->dynticks_idle in the following scenario:

    CPU 0                          CPU 1
    
                                   //CPU 1 idle
                                   //rdtp(1)->dynticks_idle == 0

sysidle_check_cpu(CPU 1) {
    rdtp(1)->dynticks_idle == 0
}
cmpxchg(full_sysidle_state, 
        ...RCU_SYSIDLE_SHORT)
                                   rcu_irq_exit() {

                                         rdtp(1)->dynticks_idle = 1
                                         smp_mb()
                                         rcu_sysidle_force_exit() {
                                            full_sysidle_state == RCU_SYSIDLE_SHORT
                                            // no cmpxchg
                                            smp_mb()
                                   ...

[1]

sysidle_check_cpu(CPU 1) {
    rdtp(1)->dynticks_idle == 0
}

cmpxchg(RCU_SYSIDLE_FULL, ...)

[2]

sysidle_check_cpu(CPU 1) {
    rdtp(1)->dynticks_idle == 0
}

cmpxchg(RCU_SYSIDLE_FULL_NOTED, ...)

I mean in [1] and [2] I can't see something in the ordering that guarantees that we see the new value rdtp(1)->dynticks_idle == 1.

Quoted 11 lines · Josh Triplett

Quoted 6 lines · Paul E. McKenney

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

This commit adds fields to the rcu_dyntick structure that are used to detect idle CPUs. These new fields differ from the existing ones in that the existing ones consider a CPU executing in user mode to be idle, where the new ones consider CPUs executing in user mode to be busy.

Can you explain, both in the commit messages and in the comments added by the next commit, *why* this code doesn't consider userspace a quiescent state?

Good point! Does the following explain it?

Although one of RCU's quiescent states is usermode execution, it is not a full-system idle state. This is because the purpose of the full-system idle state is not RCU, but rather determining when accurate timekeeping can safely be disabled. Whenever accurate timekeeping is required in a CONFIG_NO_HZ_FULL kernel, at least one CPU must keep the scheduling-clock tick going. If even one CPU is executing in user mode, accurate timekeeping is requires, particularly for architectures where gettimeofday() and friends do not enter the kernel. Only when all CPUs are really and truly idle can accurate timekeeping be disabled, allowing all CPUs to turn off the scheduling clock interrupt, thus greatly improving energy efficiency.

This naturally raises the question "Why is this code in RCU rather than in timekeeping?", and the answer is that RCU has the data and infrastructure to efficiently make this determination.

Quoted 17 lines · Paul E. McKenney

kernel/rcutree_plugin.h +17 -0

+
+/*
+ * Check to see if the system is fully idle, other than the timekeeping CPU.
+ * The caller must have disabled interrupts.
+ */
+bool rcu_sys_is_idle(void)
+{
+	static struct rcu_sysidle_head rsh;
+	int rss = ACCESS_ONCE(full_sysidle_state);
+
+	WARN_ON_ONCE(smp_processor_id() != tick_do_timer_cpu);
+
+	/* Handle small-system case by doing a full scan of CPUs. */
+	if (nr_cpu_ids <= RCU_SYSIDLE_SMALL && rss < RCU_SYSIDLE_FULL) {
+		int cpu;
+		bool isidle = true;
+		unsigned long maxj = jiffies - ULONG_MAX / 4;

kernel/rcutree_plugin.h static void rcu_sysidle_exit(struct rcu_dynticks *rdtp, int irq) · line 2690

Quoted 10 lines

kernel/rcutree_plugin.h +10 -0

+		struct rcu_data *rdp;
+
+		/* Scan all the CPUs looking for nonidle CPUs. */
+		for_each_possible_cpu(cpu) {
+			rdp = per_cpu_ptr(rcu_sysidle_state->rda, cpu);
+			rcu_sysidle_check_cpu(rdp, &isidle, &maxj);
+			if (!isidle)
+				break;
+		}
+		rcu_sysidle_report(rcu_sysidle_state, isidle, maxj);

To clarify my worries, I would expect the following ordering:

CPU 0 CPU 1

cmpxchg(global_state, RCU_SYSIDLE_..., ...) write rdtp(1)->idle_dynticks
smp_mb() // implied by cmpxchg smp_mb()
read rdtp(1)-idle_dynticks cmpxchg(global_state, RCU_SYSIDLE_NONE)

This example doesn't really make sense because CPU 0 only wants to change global state after checking rdtp(1)->idle_dynticks. So we obviously want the other way around as you did. But then I can't find an ordering that makes sure that only either happens:

* CPU 0 sees CPU 1 update when it wakes up and so we reset to RCU_SYSIDLE_NONE from CPU 0
* CPU 1 wakes up and reset to RCU_SYSIDLE_NONE and sends an IPI to CPU 0

I mean that's what the code does, but I don't get the ordering that guarantees we can't fall into some intermediate state when CPU 0 sees CPU 1 idle whereas it already woke up without sending the IPI.

I'm sure you'll point me to my mistaken review :)

Quoted 54 lines

kernel/rcutree_plugin.h +41 -0

+		rss = ACCESS_ONCE(full_sysidle_state);
+	}
+
+	/* If this is the first observation of an idle period, record it. */
+	if (rss == RCU_SYSIDLE_FULL) {
+		rss = cmpxchg(&full_sysidle_state,
+			      RCU_SYSIDLE_FULL, RCU_SYSIDLE_FULL_NOTED);
+		return rss == RCU_SYSIDLE_FULL;
+	}
+
+	smp_mb(); /* ensure rss load happens before later caller actions. */
+
+	/* If already fully idle, tell the caller (in case of races). */
+	if (rss == RCU_SYSIDLE_FULL_NOTED)
+		return true;
+
+	/*
+	 * If we aren't there yet, and a grace period is not in flight,
+	 * initiate a grace period.  Either way, tell the caller that
+	 * we are not there yet.
+	 */
+	if (nr_cpu_ids > RCU_SYSIDLE_SMALL &&
+	    !rcu_gp_in_progress(rcu_sysidle_state) &&
+	    !rsh.inuse && xchg(&rsh.inuse, 1) == 0)
+		call_rcu(&rsh.rh, rcu_sysidle_cb);
+	return false;
 }
 
 /*

@@ -2494,6 +2734,21 @@ static void rcu_sysidle_exit(struct rcu_dynticks *rdtp, int irq)
 {
 }
 
+static void rcu_sysidle_check_cpu(struct rcu_data *rdp, bool *isidle,
+				  unsigned long *maxj)
+{
+}
+
+static bool is_sysidle_rcu_state(struct rcu_state *rsp)
+{
+	return false;
+}
+
+static void rcu_sysidle_report(struct rcu_state *rsp, int isidle,
+			       unsigned long maxj)
+{
+}
+
 static void rcu_sysidle_init_percpu_data(struct rcu_dynticks *rdtp)
 {
 }

Signature · 1 line

1.8.1.5

Quoted 28 lines · Paul E. McKenney

Quoted 11 lines · Josh Triplett

Quoted 6 lines · Paul E. McKenney

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

This commit adds fields to the rcu_dyntick structure that are used to detect idle CPUs. These new fields differ from the existing ones in that the existing ones consider a CPU executing in user mode to be idle, where the new ones consider CPUs executing in user mode to be busy.

Can you explain, both in the commit messages and in the comments added by the next commit, *why* this code doesn't consider userspace a quiescent state?

Good point! Does the following explain it?

Although one of RCU's quiescent states is usermode execution, it is not a full-system idle state. This is because the purpose of the full-system idle state is not RCU, but rather determining when accurate timekeeping can safely be disabled. Whenever accurate timekeeping is required in a CONFIG_NO_HZ_FULL kernel, at least one CPU must keep the scheduling-clock tick going. If even one CPU is executing in user mode, accurate timekeeping is requires, particularly for architectures where gettimeofday() and friends do not enter the kernel. Only when all CPUs are really and truly idle can accurate timekeeping be disabled, allowing all CPUs to turn off the scheduling clock interrupt, thus greatly improving energy efficiency.

Quoted 3 lines

This naturally raises the question "Why is this code in RCU rather than in timekeeping?", and the answer is that RCU has the data and infrastructure to efficiently make this determination.

Good explanation, thanks.

This also naturally raises the question "How can we let userspace get accurate time without forcing a timer tick?".

Quoted 33 lines · Josh Triplett

Quoted 31 lines · Paul E. McKenney

Quoted 11 lines · Josh Triplett

Quoted 6 lines · Paul E. McKenney

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

This commit adds fields to the rcu_dyntick structure that are used to detect idle CPUs. These new fields differ from the existing ones in that the existing ones consider a CPU executing in user mode to be idle, where the new ones consider CPUs executing in user mode to be busy.

Can you explain, both in the commit messages and in the comments added by the next commit, *why* this code doesn't consider userspace a quiescent state?

Good point! Does the following explain it?

Although one of RCU's quiescent states is usermode execution, it is not a full-system idle state. This is because the purpose of the full-system idle state is not RCU, but rather determining when accurate timekeeping can safely be disabled. Whenever accurate timekeeping is required in a CONFIG_NO_HZ_FULL kernel, at least one CPU must keep the scheduling-clock tick going. If even one CPU is executing in user mode, accurate timekeeping is requires, particularly for architectures where gettimeofday() and friends do not enter the kernel. Only when all CPUs are really and truly idle can accurate timekeeping be disabled, allowing all CPUs to turn off the scheduling clock interrupt, thus greatly improving energy efficiency.

This naturally raises the question "Why is this code in RCU rather than in timekeeping?", and the answer is that RCU has the data and infrastructure to efficiently make this determination.

Quoted 4 lines

Good explanation, thanks.

This also naturally raises the question "How can we let userspace get accurate time without forcing a timer tick?".

We don't. ;-)

Without CONFIG_NO_HZ_FULL, if a CPU is running in user mode, that CPU takes scheduling-clock interrupts. User-mode code will therefore always see accurate time. For some definition of "accurate", anyway.

With CONFIG_NO_HZ_FULL and without CONFIG_NO_HZ_FULL_SYSIDLE, a single designated CPU will always be taking scheduling-clock interrupts, which again ensures that user-mode code will always see accurate time.

With both CONFIG_NO_HZ_FULL and CONFIG_NO_HZ_FULL_SYSIDLE, if any CPU other than the timekeeping CPU is nonidle (where "nonidle" includes usermode execution), then the timekeeping CPU will be taking scheduling-clock interrupts, yet again ensuring that user-mode code will always see accurate time. If all CPUs are idle (in other words, we are in RCU_SYSIDLE_FULL_NOTED state and the timekeeping CPU is also idle), scheduling-clock interrupts will be globally disabled. Or will be, once I fix the bug noted by Frederic.

I am guessing that you would like this added to the explanation? ;-)

Quoted 34 lines · Paul E. McKenney

Quoted 33 lines · Josh Triplett

Quoted 31 lines · Paul E. McKenney

Quoted 11 lines · Josh Triplett

Quoted 6 lines · Paul E. McKenney

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

This commit adds fields to the rcu_dyntick structure that are used to detect idle CPUs. These new fields differ from the existing ones in that the existing ones consider a CPU executing in user mode to be idle, where the new ones consider CPUs executing in user mode to be busy.

Can you explain, both in the commit messages and in the comments added by the next commit, *why* this code doesn't consider userspace a quiescent state?

Good point! Does the following explain it?

Although one of RCU's quiescent states is usermode execution, it is not a full-system idle state. This is because the purpose of the full-system idle state is not RCU, but rather determining when accurate timekeeping can safely be disabled. Whenever accurate timekeeping is required in a CONFIG_NO_HZ_FULL kernel, at least one CPU must keep the scheduling-clock tick going. If even one CPU is executing in user mode, accurate timekeeping is requires, particularly for architectures where gettimeofday() and friends do not enter the kernel. Only when all CPUs are really and truly idle can accurate timekeeping be disabled, allowing all CPUs to turn off the scheduling clock interrupt, thus greatly improving energy efficiency.

This naturally raises the question "Why is this code in RCU rather than in timekeeping?", and the answer is that RCU has the data and infrastructure to efficiently make this determination.

Quoted 6 lines

Quoted 4 lines

Good explanation, thanks.

This also naturally raises the question "How can we let userspace get accurate time without forcing a timer tick?".

We don't. ;-)

We don't currently, hence my question about how we can. :)

Quoted 17 lines

Without CONFIG_NO_HZ_FULL, if a CPU is running in user mode, that CPU takes scheduling-clock interrupts. User-mode code will therefore always see accurate time. For some definition of "accurate", anyway.

With CONFIG_NO_HZ_FULL and without CONFIG_NO_HZ_FULL_SYSIDLE, a single designated CPU will always be taking scheduling-clock interrupts, which again ensures that user-mode code will always see accurate time.

With both CONFIG_NO_HZ_FULL and CONFIG_NO_HZ_FULL_SYSIDLE, if any CPU other than the timekeeping CPU is nonidle (where "nonidle" includes usermode execution), then the timekeeping CPU will be taking scheduling-clock interrupts, yet again ensuring that user-mode code will always see accurate time. If all CPUs are idle (in other words, we are in RCU_SYSIDLE_FULL_NOTED state and the timekeeping CPU is also idle), scheduling-clock interrupts will be globally disabled. Or will be, once I fix the bug noted by Frederic.

Quoted 1 line

I am guessing that you would like this added to the explanation? ;-)

Seemed pretty clear already from your previous explanation above, but since you've taken the time to write it... :)

Quoted 4 lines

I am guessing that you want CONFIG_NO_HZ_FULL to implicitly enable the sysidle code so that CONFIG_NO_HZ_FULL_SYSIDLE can be eliminated. I will be happy to take that step, but only after I gain full confidence in the correctness and performance of the sysidle code.

FWIW if you want useful testing you need to enable it by default (as part of NO_IDLE_HZ) anyways. Users will most likely pick whatever is "default" in Kconfig.

Quoted 4 lines

Quoted 1 line

If you want a switch for testing I would advise a sysctl or sysfs knob

This would work well for the correctness part, but not for the performance part.

What performance part?

Are you saying this adds so many checks to hot paths that normal runtime if() with a flag is too expensive?

Unfortunately, timekeeping CPU continues taking scheduling-clock interrupts even when all other CPUs are completely idle, which is not so good for energy efficiency and battery lifetime. Clearly, it would be good to turn off the timekeeping CPU's scheduling-clock tick when all CPUs are completely idle. This is conceptually simple, but we also need good performance and scalability on large systems, which rules out implementations based on frequently updated global counts of non-idle CPUs as well as implementations that frequently scan all CPUs. Nevertheless, we need a single global indicator in order to keep the overhead of checking acceptably low.

Quoted 10 lines · Paul E. McKenney

Unfortunately, timekeeping CPU continues taking scheduling-clock interrupts even when all other CPUs are completely idle, which is not so good for energy efficiency and battery lifetime. Clearly, it would be good to turn off the timekeeping CPU's scheduling-clock tick when all CPUs are completely idle. This is conceptually simple, but we also need good performance and scalability on large systems, which rules out implementations based on frequently updated global counts of non-idle CPUs as well as implementations that frequently scan all CPUs. Nevertheless, we need a single global indicator in order to keep the overhead of checking acceptably low.

Can we turn off timekeeping when no cpu needs time in adaptive mode? Setting breakpoints in the VDSO could force timekeeping on again whenever something needs time. Would this not be simpler?

Quoted 13 lines · Christoph Lameter

Quoted 10 lines · Paul E. McKenney

Unfortunately, timekeeping CPU continues taking scheduling-clock interrupts even when all other CPUs are completely idle, which is not so good for energy efficiency and battery lifetime. Clearly, it would be good to turn off the timekeeping CPU's scheduling-clock tick when all CPUs are completely idle. This is conceptually simple, but we also need good performance and scalability on large systems, which rules out implementations based on frequently updated global counts of non-idle CPUs as well as implementations that frequently scan all CPUs. Nevertheless, we need a single global indicator in order to keep the overhead of checking acceptably low.

Quoted 3 lines

Can we turn off timekeeping when no cpu needs time in adaptive mode? Setting breakpoints in the VDSO could force timekeeping on again whenever something needs time. Would this not be simpler?

Might be. But what causes the breakpoints to be set on a system where there is one CPU-bound nohz_full user-mode task with all other CPUs idle? Or are you suggesting taking a breakpoint trap on each timekeeping access to VDSO?

Quoted 14 lines · Paul E. McKenney

Quoted 13 lines · Christoph Lameter

Quoted 10 lines · Paul E. McKenney

Unfortunately, timekeeping CPU continues taking scheduling-clock interrupts even when all other CPUs are completely idle, which is not so good for energy efficiency and battery lifetime. Clearly, it would be good to turn off the timekeeping CPU's scheduling-clock tick when all CPUs are completely idle. This is conceptually simple, but we also need good performance and scalability on large systems, which rules out implementations based on frequently updated global counts of non-idle CPUs as well as implementations that frequently scan all CPUs. Nevertheless, we need a single global indicator in order to keep the overhead of checking acceptably low.

Quoted 8 lines

Quoted 3 lines

Can we turn off timekeeping when no cpu needs time in adaptive mode? Setting breakpoints in the VDSO could force timekeeping on again whenever something needs time. Would this not be simpler?

Might be. But what causes the breakpoints to be set on a system where there is one CPU-bound nohz_full user-mode task with all other CPUs idle? Or are you suggesting taking a breakpoint trap on each timekeeping access to VDSO?

Well when a tick notices that it is the last one still enabled on the system and it could disable itself then it would set the breakpoint and then turn the tick on the last processor off. The code invoked by the breakpoint would reenable tick processing, update time and then use that new info to return the correct time.

Quoted 8 lines · Frederic Weisbecker

What makes sure that we are not reading a stale value of rdtp->dynticks_idle in the following scenario:

    CPU 0                          CPU 1
    
                                   //CPU 1 idle
                                   //rdtp(1)->dynticks_idle == 0

Quoted 6 lines

sysidle_check_cpu(CPU 1) {
    rdtp(1)->dynticks_idle == 0
}
cmpxchg(full_sysidle_state, 
        ...RCU_SYSIDLE_SHORT)
                                   rcu_irq_exit() {

rcu_irq_enter(), right?

kernel/rcutree_plugin.h +36 -0

+{
+	static struct rcu_sysidle_head rsh;
+	int rss = ACCESS_ONCE(full_sysidle_state);
+
+	WARN_ON_ONCE(smp_processor_id() != tick_do_timer_cpu);
+
+	/* Handle small-system case by doing a full scan of CPUs. */
+	if (nr_cpu_ids <= RCU_SYSIDLE_SMALL && rss < RCU_SYSIDLE_FULL) {
+		int cpu;
+		bool isidle = true;
+		unsigned long maxj = jiffies - ULONG_MAX / 4;
+		struct rcu_data *rdp;
+
+		/* Scan all the CPUs looking for nonidle CPUs. */
+		for_each_possible_cpu(cpu) {
+			rdp = per_cpu_ptr(rcu_sysidle_state->rda, cpu);
+			rcu_sysidle_check_cpu(rdp, &isidle, &maxj);
+			if (!isidle)
+				break;
+		}
+		rcu_sysidle_report(rcu_sysidle_state, isidle, maxj);
+		rss = ACCESS_ONCE(full_sysidle_state);
+	}
+
+	/* If this is the first observation of an idle period, record it. */
+	if (rss == RCU_SYSIDLE_FULL) {
+		rss = cmpxchg(&full_sysidle_state,
+			      RCU_SYSIDLE_FULL, RCU_SYSIDLE_FULL_NOTED);
+		return rss == RCU_SYSIDLE_FULL;
+	}
+
+	smp_mb(); /* ensure rss load happens before later caller actions. */
+
+	/* If already fully idle, tell the caller (in case of races). */
+	if (rss == RCU_SYSIDLE_FULL_NOTED)
+		return true;

kernel/rcutree_plugin.h +16 -0

+	return false;
 }
 
 /*

@@ -2494,6 +2734,21 @@ static void rcu_sysidle_exit(struct rcu_dynticks *rdtp, int irq)
 {
 }
 
+static void rcu_sysidle_check_cpu(struct rcu_data *rdp, bool *isidle,
+				  unsigned long *maxj)
+{
+}
+
+static bool is_sysidle_rcu_state(struct rcu_state *rsp)
+{
+	return false;
+}
+
+static void rcu_sysidle_report(struct rcu_state *rsp, int isidle,
+			       unsigned long maxj)
+{
+}
+
 static void rcu_sysidle_init_percpu_data(struct rcu_dynticks *rdtp)
 {
 }

Signature · 1 line

1.8.1.5

kernel/rcutree_plugin.h static void rcu_sysidle_exit(struct rcu_dynticks *rdtp, int irq) · line 2669

Quoted 5 lines · Paul E. McKenney

kernel/rcutree_plugin.h +5 -0

+/*
+ * Check to see if the system is fully idle, other than the timekeeping CPU.
+ * The caller must have disabled interrupts.
+ */
+bool rcu_sys_is_idle(void)

Where is this function called? I can't find any caller in the patchset.

Quoted 36 lines

kernel/rcutree_plugin.h +36 -0

+{
+	static struct rcu_sysidle_head rsh;
+	int rss = ACCESS_ONCE(full_sysidle_state);
+
+	WARN_ON_ONCE(smp_processor_id() != tick_do_timer_cpu);
+
+	/* Handle small-system case by doing a full scan of CPUs. */
+	if (nr_cpu_ids <= RCU_SYSIDLE_SMALL && rss < RCU_SYSIDLE_FULL) {
+		int cpu;
+		bool isidle = true;
+		unsigned long maxj = jiffies - ULONG_MAX / 4;
+		struct rcu_data *rdp;
+
+		/* Scan all the CPUs looking for nonidle CPUs. */
+		for_each_possible_cpu(cpu) {
+			rdp = per_cpu_ptr(rcu_sysidle_state->rda, cpu);
+			rcu_sysidle_check_cpu(rdp, &isidle, &maxj);
+			if (!isidle)
+				break;
+		}
+		rcu_sysidle_report(rcu_sysidle_state, isidle, maxj);
+		rss = ACCESS_ONCE(full_sysidle_state);
+	}
+
+	/* If this is the first observation of an idle period, record it. */
+	if (rss == RCU_SYSIDLE_FULL) {
+		rss = cmpxchg(&full_sysidle_state,
+			      RCU_SYSIDLE_FULL, RCU_SYSIDLE_FULL_NOTED);
+		return rss == RCU_SYSIDLE_FULL;
+	}
+
+	smp_mb(); /* ensure rss load happens before later caller actions. */
+
+	/* If already fully idle, tell the caller (in case of races). */
+	if (rss == RCU_SYSIDLE_FULL_NOTED)
+		return true;

kernel/rcutree_plugin.h static void rcu_sysidle_exit(struct rcu_dynticks *rdtp, int irq) · line 2715

Quoted 10 lines

kernel/rcutree_plugin.h +10 -0

+
+	/*
+	 * If we aren't there yet, and a grace period is not in flight,
+	 * initiate a grace period.  Either way, tell the caller that
+	 * we are not there yet.
+	 */
+	if (nr_cpu_ids > RCU_SYSIDLE_SMALL &&
+	    !rcu_gp_in_progress(rcu_sysidle_state) &&
+	    !rsh.inuse && xchg(&rsh.inuse, 1) == 0)
+		call_rcu(&rsh.rh, rcu_sysidle_cb);

So this starts an RCU/RCU_preempt grace period to force the global idle detection.

Would it make sense to create a new RCU flavour instead for this purpose? Its only per CPU quiescent state would be when the timekeeping CPU ticks (from rcu_check_callbacks()). The other CPUs would only complete their QS request through extended quiescent states, ie: only the timekeeping CPU is burdened.

This way you can enqueue a callback that is executed in the end of the grace period for that flavour and that callback can help driving the state machine somehow.

Now may be that's not a good idea because this adds some overhead to any code that uses for_each_rcu_flavour().

Quoted 29 lines

kernel/rcutree_plugin.h +16 -0

+	return false;
 }
 
 /*

@@ -2494,6 +2734,21 @@ static void rcu_sysidle_exit(struct rcu_dynticks *rdtp, int irq)
 {
 }
 
+static void rcu_sysidle_check_cpu(struct rcu_data *rdp, bool *isidle,
+				  unsigned long *maxj)
+{
+}
+
+static bool is_sysidle_rcu_state(struct rcu_state *rsp)
+{
+	return false;
+}
+
+static void rcu_sysidle_report(struct rcu_state *rsp, int isidle,
+			       unsigned long maxj)
+{
+}
+
 static void rcu_sysidle_init_percpu_data(struct rcu_dynticks *rdtp)
 {
 }

Signature · 1 line

1.8.1.5

Quoted 6 lines · Josh Triplett

Quoted 4 lines

Quoted 2 lines

This also naturally raises the question "How can we let userspace get accurate time without forcing a timer tick?".

We don't. ;-)

We don't currently, hence my question about how we can. :)

Per-CPU atomic clocks?

Quoted 7 lines · Paul E. McKenney

Quoted 5 lines · Josh Triplett

Quoted 4 lines

Quoted 2 lines

This also naturally raises the question "How can we let userspace get accurate time without forcing a timer tick?".

We don't. ;-)

Quoted 3 lines

Quoted 1 line

We don't currently, hence my question about how we can. :)

Per-CPU atomic clocks?

Great idea, who needs timekeeping code.

http://www.euronews.com/2013/04/02/swiss-sets-sights-on-miniscule-atomic-clock/