Skip to contentSkip to conversation

Teach RCU that idle task is not quiscent state at boot

PATCH Applied Paul E. McKenney 5 participants 21 messages Feb 23, 2009 – Feb 26, 2009 RCU

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 Teach RCU that idle task is not quiscent state at boot

This patch fixes a bug located by Vegard Nossum with the aid of kmemcheck.

The boot CPU runs in the context of its idle thread during boot-up. During this time, idle_cpu(0) will always return nonzero, which will fool Classic and Hierarchical RCU into deciding that a large chunk of the boot-up sequence is a big long quiescent state. This in turn causes RCU to prematurely end grace periods during this time.

This patch changes the rcutree.c and rcuclassic.c rcu_check_callbacks() function to ignore the idle tasks as a quiescent state until the system_state is no longer SYSTEM_BOOTING. After this point, the idle task really does represent a quiescent state.

In addition, this patch takes Nick Piggin's suggestion to make the system_state global variable be __read_mostly.

---

 init/main.c         |    2 +-
 kernel/rcuclassic.c |    4 ++--
 kernel/rcutree.c    |    4 ++--
 3 files changed, 5 insertions(+), 5 deletions(-)
init/main.c +1 -1
index 8442094..5067cfc 100644
@@ -97,7 +97,7 @@ static inline void mark_rodata_ro(void) { }
 extern void tc_init(void);
 #endif
 
-enum system_states system_state;
+enum system_states system_state __read_mostly;
 EXPORT_SYMBOL(system_state);
 
 /*
kernel/rcuclassic.c +2 -2
index bd5a900..909d04e 100644
@@ -679,8 +679,8 @@ int rcu_needs_cpu(int cpu)
 void rcu_check_callbacks(int cpu, int user)
 {
 	if (user ||
-	    (idle_cpu(cpu) && !in_softirq() &&
-				hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
+	    (idle_cpu(cpu) && (system_state != SYSTEM_BOOTING) &&
+	     !in_softirq() && hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
 
 		/*
 		 * Get here if this CPU took its interrupt from user
kernel/rcutree.c +2 -2
index b2fd602..da685ea 100644
@@ -948,8 +948,8 @@ static void rcu_do_batch(struct rcu_data *rdp)
 void rcu_check_callbacks(int cpu, int user)
 {
 	if (user ||
-	    (idle_cpu(cpu) && !in_softirq() &&
-				hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
+	    (idle_cpu(cpu) && (system_state != SYSTEM_BOOTING) &&
+	     !in_softirq() && hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
 
 		/*
 		 * Get here if this CPU took its interrupt from user
Applied
#1 lore raw
Quoted 20 lines · Paul E. McKenney

This patch fixes a bug located by Vegard Nossum with the aid of kmemcheck.

The boot CPU runs in the context of its idle thread during boot-up. During this time, idle_cpu(0) will always return nonzero, which will fool Classic and Hierarchical RCU into deciding that a large chunk of the boot-up sequence is a big long quiescent state. This in turn causes RCU to prematurely end grace periods during this time.

This patch changes the rcutree.c and rcuclassic.c rcu_check_callbacks() function to ignore the idle tasks as a quiescent state until the system_state is no longer SYSTEM_BOOTING. After this point, the idle task really does represent a quiescent state.

In addition, this patch takes Nick Piggin's suggestion to make the system_state global variable be __read_mostly.

Quoted 6 lines

---

 init/main.c         |    2 +-
 kernel/rcuclassic.c |    4 ++--
 kernel/rcutree.c    |    4 ++--
 3 files changed, 5 insertions(+), 5 deletions(-)

Applied to tip:core/urgent, thanks Paul!

Ingo

#2 lore raw

PATCH 1/1 v2 Teach RCU that idle task is not quiscent state at boot

In reply to Paul E. McKenney

This patch fixes a bug located by Vegard Nossum with the aid of kmemcheck, updated based on review comments from Nick Piggin, Ingo Molnar, and Andrew Morton.

The boot CPU runs in the context of its idle thread during boot-up. During this time, idle_cpu(0) will always return nonzero, which will fool Classic and Hierarchical RCU into deciding that a large chunk of the boot-up sequence is a big long quiescent state. This in turn causes RCU to prematurely end grace periods during this time.

This patch changes the rcutree.c and rcuclassic.c rcu_check_callbacks() function to ignore the idle task as a quiescent state until the system has started up the scheduler in rest_init(), introducing a new non-API function rcu_idle_now_means_idle() to inform RCU of this transition. RCU maintains an internal rcu_idle_cpu_truthful variable to track this state, which is then used by rcu_check_callback() to determine if it should believe idle_cpu().

Because this patch has the effect of disallowing RCU grace periods during long stretches of the boot-up sequence, this patch also introduces Josh Triplett's UP-only optimization that makes synchronize_rcu() be a no-op if num_online_cpus() returns 1. This allows boot-time code that calls synchronize_rcu() to proceed normally. Note, however, that RCU callbacks registered by call_rcu() will likely queue up until later in the boot sequence.

In addition, this patch takes Nick Piggin's suggestion to make the system_state global variable be __read_mostly.

---

 include/linux/rcupdate.h |    2 ++
 init/main.c              |    3 ++-
 kernel/rcuclassic.c      |    4 ++--
 kernel/rcupdate.c        |   10 ++++++++++
 kernel/rcutree.c         |    4 ++--
 5 files changed, 18 insertions(+), 5 deletions(-)
include/linux/rcupdate.h +2 -0
index 921340a..063c67b 100644
@@ -265,6 +265,8 @@ extern void rcu_barrier_sched(void);
 
 /* Internal to kernel */
 extern void rcu_init(void);
+extern void rcu_idle_now_means_idle(void);
+extern int rcu_idle_cpu_truthful;
 extern int rcu_needs_cpu(int cpu);
 
 #endif /* __LINUX_RCUPDATE_H */
init/main.c +2 -1
index 8442094..b952287 100644
@@ -97,7 +97,7 @@ static inline void mark_rodata_ro(void) { }
 extern void tc_init(void);
 #endif
 
-enum system_states system_state;
+enum system_states system_state __read_mostly;
 EXPORT_SYMBOL(system_state);
 
 /*
@@ -463,6 +463,7 @@ static noinline void __init_refok rest_init(void)
 	 * at least once to get things moving:
 	 */
 	init_idle_bootup_task(current);
+	rcu_idle_now_means_idle();
 	preempt_enable_no_resched();
 	schedule();
 	preempt_disable();
kernel/rcuclassic.c +2 -2
index bd5a900..b4377de 100644
@@ -679,8 +679,8 @@ int rcu_needs_cpu(int cpu)
 void rcu_check_callbacks(int cpu, int user)
 {
 	if (user ||
-	    (idle_cpu(cpu) && !in_softirq() &&
-				hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
+	    (idle_cpu(cpu) && rcu_idle_cpu_truthful &&
+	     !in_softirq() && hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
 
 		/*
 		 * Get here if this CPU took its interrupt from user
kernel/rcupdate.c +10 -0
index d92a76a..0f85e18 100644
@@ -55,6 +55,7 @@ static DEFINE_PER_CPU(struct rcu_head, rcu_barrier_head) = {NULL};
 static atomic_t rcu_barrier_cpu_count;
 static DEFINE_MUTEX(rcu_barrier_mutex);
 static struct completion rcu_barrier_completion;
+int rcu_idle_cpu_truthful __read_mostly;
 
 /*
  * Awaken the corresponding synchronize_rcu() instance now that a
@@ -80,6 +81,10 @@ void wakeme_after_rcu(struct rcu_head  *head)
 void synchronize_rcu(void)
 {
 	struct rcu_synchronize rcu;
+
+	if (num_online_cpus() == 1)
+		return;  /* If UP, synchronize_rcu() is a grace period! */
+
 	init_completion(&rcu.completion);
 	/* Will wake me after RCU finished. */
 	call_rcu(&rcu.head, wakeme_after_rcu);
@@ -175,3 +180,8 @@ void __init rcu_init(void)
 	__rcu_init();
 }
 
+void rcu_idle_now_means_idle(void)
+{
+	WARN_ON(num_online_cpus() != 1);
+	rcu_idle_cpu_truthful = 1;
+}
kernel/rcutree.c +2 -2
index b2fd602..b37a7b1 100644
@@ -948,8 +948,8 @@ static void rcu_do_batch(struct rcu_data *rdp)
 void rcu_check_callbacks(int cpu, int user)
 {
 	if (user ||
-	    (idle_cpu(cpu) && !in_softirq() &&
-				hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
+	    (idle_cpu(cpu) && rcu_idle_cpu_truthful &&
+	     !in_softirq() && hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
 
 		/*
 		 * Get here if this CPU took its interrupt from user
#3 lore raw

Re: [PATCH] v2 Teach RCU that idle task is not quiscent state at boot

kernel/rcupdate.c void wakeme_after_rcu(struct rcu_head *head) · line 87

Quoted 8 lines · On Tuesday 24 February 2009 07:43:32 Paul E. McKenney wrote:
kernel/rcupdate.c +4 -0
@@ -80,6 +81,10 @@ void wakeme_after_rcu(struct rcu_head  *head)
 void synchronize_rcu(void)
 {
 	struct rcu_synchronize rcu;
+
+	if (num_online_cpus() == 1)
+		return;  /* If UP, synchronize_rcu() is a grace period! */
+

Nice patch... May I just suggest a comment to say that this is also a correctness requirement due to the grace period holdoff for early boot?

#4 lore raw

Re: [PATCH] v2 Teach RCU that idle task is not quiscent state at boot

Quoted 14 lines · Nick Piggin

kernel/rcupdate.c void wakeme_after_rcu(struct rcu_head *head) · line 87

Quoted 8 lines · On Tuesday 24 February 2009 07:43:32 Paul E. McKenney wrote:
kernel/rcupdate.c +4 -0
@@ -80,6 +81,10 @@ void wakeme_after_rcu(struct rcu_head  *head)
 void synchronize_rcu(void)
 {
 	struct rcu_synchronize rcu;
+
+	if (num_online_cpus() == 1)
+		return;  /* If UP, synchronize_rcu() is a grace period! */
+

Nice patch... May I just suggest a comment to say that this is also a correctness requirement due to the grace period holdoff for early boot?

Excellent point! If Ingo reports that this actually fixes the hang that he saw, I will add such a comment.

(And glad you like the patch!)

Thanx, Paul

#5 lore raw

Re: [PATCH] v2 Teach RCU that idle task is not quiscent state at boot

Quoted 16 lines · Paul E. McKenney
Quoted 14 lines · Nick Piggin

kernel/rcupdate.c void wakeme_after_rcu(struct rcu_head *head) · line 87

Quoted 8 lines · On Tuesday 24 February 2009 07:43:32 Paul E. McKenney wrote:
kernel/rcupdate.c +4 -0
@@ -80,6 +81,10 @@ void wakeme_after_rcu(struct rcu_head  *head)
 void synchronize_rcu(void)
 {
 	struct rcu_synchronize rcu;
+
+	if (num_online_cpus() == 1)
+		return;  /* If UP, synchronize_rcu() is a grace period! */
+

Nice patch... May I just suggest a comment to say that this is also a correctness requirement due to the grace period holdoff for early boot?

Quoted 4 lines

Excellent point! If Ingo reports that this actually fixes the hang that he saw, I will add such a comment.

(And glad you like the patch!)

Gah!!! I forgot about preemptable RCU, which the previous patch breaks completely on single-CPU systems.

A fix is in the works.

Thanx, Paul

#6 lore raw

PATCH 1/1 v3 Teach RCU that idle task is not quiscent state at boot

In reply to Paul E. McKenney

This patch fixes a bug located by Vegard Nossum with the aid of kmemcheck, updated based on review comments from Nick Piggin, Ingo Molnar, and Andrew Morton.

The boot CPU runs in the context of its idle thread during boot-up. During this time, idle_cpu(0) will always return nonzero, which will fool Classic and Hierarchical RCU into deciding that a large chunk of the boot-up sequence is a big long quiescent state. This in turn causes RCU to prematurely end grace periods during this time.

This patch changes the rcutree.c and rcuclassic.c rcu_check_callbacks() function to ignore the idle task as a quiescent state until the system has started up the scheduler in rest_init(), introducing a new non-API function rcu_idle_now_means_idle() to inform RCU of this transition. RCU maintains an internal rcu_idle_cpu_truthful variable to track this state, which is then used by rcu_check_callback() to determine if it should believe idle_cpu().

Because this patch has the effect of disallowing RCU grace periods during long stretches of the boot-up sequence, this patch also introduces Josh Triplett's UP-only optimization that makes synchronize_rcu() be a no-op if num_online_cpus() returns 1. This allows boot-time code that calls synchronize_rcu() to proceed normally. Note, however, that RCU callbacks registered by call_rcu() will likely queue up until later in the boot sequence. Although rcuclassic and rcutree can also use this same optimization after boot completes, rcupreempt must restrict its use of this optimization to the portion of the boot sequence before the scheduler starts up, given that an rcupreempt RCU read-side critical section may be preeempted.

In addition, this patch takes Nick Piggin's suggestion to make the system_state global variable be __read_mostly.

Changes since v2:

o Created rcu_blocking_is_gp() internal-to-RCU API that
determines whether a call to synchronize_rcu() is itself a grace period.

o The definition of rcu_blocking_is_gp() for rcuclassic and
rcutree checks to see if but a single CPU is online.

o The definition of rcu_blocking_is_gp() for rcupreempt
checks to see both if but a single CPU is online and if the system is still in early boot.

This allows rcupreempt to again work correctly if running on a single CPU after booting is complete.

o Added check to rcupreempt's synchronize_sched() for there
being but one online CPU.

Tested all three variants both SMP and !SMP, booted fine, passed a short rcutorture test.

---

 include/linux/rcuclassic.h |    6 ++++++
 include/linux/rcupdate.h   |    4 ++++
 include/linux/rcupreempt.h |   15 +++++++++++++++
 include/linux/rcutree.h    |    6 ++++++
 init/main.c                |    3 ++-
 kernel/rcuclassic.c        |    4 ++--
 kernel/rcupdate.c          |   10 ++++++++++
 kernel/rcupreempt.c        |    3 +++
 kernel/rcutree.c           |    4 ++--
 9 files changed, 50 insertions(+), 5 deletions(-)
include/linux/rcuclassic.h +6 -0
index f3f697d..80044a4 100644
@@ -181,4 +181,10 @@ extern long rcu_batches_completed_bh(void);
 #define rcu_enter_nohz()	do { } while (0)
 #define rcu_exit_nohz()		do { } while (0)
 
+/* A context switch is a grace period for rcuclassic. */
+static inline int rcu_blocking_is_gp(void)
+{
+	return num_online_cpus() == 1;
+}
+
 #endif /* __LINUX_RCUCLASSIC_H */
include/linux/rcupdate.h +4 -0
index 921340a..1e5249d 100644
@@ -52,6 +52,9 @@ struct rcu_head {
 	void (*func)(struct rcu_head *head);
 };
 
+/* Internal to kernel, but needed by rcupreempt.h. */
+extern int rcu_idle_cpu_truthful;
+
 #if defined(CONFIG_CLASSIC_RCU)
 #include <linux/rcuclassic.h>
 #elif defined(CONFIG_TREE_RCU)
@@ -265,6 +268,7 @@ extern void rcu_barrier_sched(void);
 
 /* Internal to kernel */
 extern void rcu_init(void);
+extern void rcu_idle_now_means_idle(void);
 extern int rcu_needs_cpu(int cpu);
 
 #endif /* __LINUX_RCUPDATE_H */
include/linux/rcupreempt.h +15 -0
index 3e05c09..504973d 100644
@@ -142,4 +142,19 @@ static inline void rcu_exit_nohz(void)
 #define rcu_exit_nohz()		do { } while (0)
 #endif /* CONFIG_NO_HZ */
 
+/*
+ * A context switch is a grace period for rcupreempt synchronize_rcu()
+ * only during early boot, before the scheduler has been initialized.
+ * So, how the heck do we get a context switch?  Well, if the caller
+ * invokes synchronize_rcu(), they are willing to accept a context
+ * switch, so we simply pretend that one happened.
+ *
+ * After boot, there might be a blocked or preempted task in an RCU
+ * read-side critical section, so we cannot then take the fastpath.
+ */
+static inline int rcu_blocking_is_gp(void)
+{
+	return num_online_cpus() == 1 && !rcu_idle_cpu_truthful;
+}
+
 #endif /* __LINUX_RCUPREEMPT_H */
include/linux/rcutree.h +6 -0
index d4368b7..a722fb6 100644
@@ -326,4 +326,10 @@ static inline void rcu_exit_nohz(void)
 }
 #endif /* CONFIG_NO_HZ */
 
+/* A context switch is a grace period for rcutree. */
+static inline int rcu_blocking_is_gp(void)
+{
+	return num_online_cpus() == 1;
+}
+
 #endif /* __LINUX_RCUTREE_H */
init/main.c +2 -1
index 8442094..b952287 100644
@@ -97,7 +97,7 @@ static inline void mark_rodata_ro(void) { }
 extern void tc_init(void);
 #endif
 
-enum system_states system_state;
+enum system_states system_state __read_mostly;
 EXPORT_SYMBOL(system_state);
 
 /*
@@ -463,6 +463,7 @@ static noinline void __init_refok rest_init(void)
 	 * at least once to get things moving:
 	 */
 	init_idle_bootup_task(current);
+	rcu_idle_now_means_idle();
 	preempt_enable_no_resched();
 	schedule();
 	preempt_disable();
kernel/rcuclassic.c +2 -2
index bd5a900..b4377de 100644
@@ -679,8 +679,8 @@ int rcu_needs_cpu(int cpu)
 void rcu_check_callbacks(int cpu, int user)
 {
 	if (user ||
-	    (idle_cpu(cpu) && !in_softirq() &&
-				hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
+	    (idle_cpu(cpu) && rcu_idle_cpu_truthful &&
+	     !in_softirq() && hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
 
 		/*
 		 * Get here if this CPU took its interrupt from user
kernel/rcupdate.c +10 -0
index d92a76a..bec84eb 100644
@@ -55,6 +55,7 @@ static DEFINE_PER_CPU(struct rcu_head, rcu_barrier_head) = {NULL};
 static atomic_t rcu_barrier_cpu_count;
 static DEFINE_MUTEX(rcu_barrier_mutex);
 static struct completion rcu_barrier_completion;
+int rcu_idle_cpu_truthful __read_mostly;
 
 /*
  * Awaken the corresponding synchronize_rcu() instance now that a
@@ -80,6 +81,10 @@ void wakeme_after_rcu(struct rcu_head  *head)
 void synchronize_rcu(void)
 {
 	struct rcu_synchronize rcu;
+
+	if (rcu_blocking_is_gp())
+		return;
+
 	init_completion(&rcu.completion);
 	/* Will wake me after RCU finished. */
 	call_rcu(&rcu.head, wakeme_after_rcu);
@@ -175,3 +180,8 @@ void __init rcu_init(void)
 	__rcu_init();
 }
 
+void rcu_idle_now_means_idle(void)
+{
+	WARN_ON(num_online_cpus() != 1);
+	rcu_idle_cpu_truthful = 1;
+}
kernel/rcupreempt.c +3 -0
index 33cfc50..5d59e85 100644
@@ -1181,6 +1181,9 @@ void __synchronize_sched(void)
 {
 	struct rcu_synchronize rcu;
 
+	if (num_online_cpus() == 1)
+		return;  /* blocking is gp if only one CPU! */
+
 	init_completion(&rcu.completion);
 	/* Will wake me after RCU finished. */
 	call_rcu_sched(&rcu.head, wakeme_after_rcu);
kernel/rcutree.c +2 -2
index b2fd602..b37a7b1 100644
@@ -948,8 +948,8 @@ static void rcu_do_batch(struct rcu_data *rdp)
 void rcu_check_callbacks(int cpu, int user)
 {
 	if (user ||
-	    (idle_cpu(cpu) && !in_softirq() &&
-				hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
+	    (idle_cpu(cpu) && rcu_idle_cpu_truthful &&
+	     !in_softirq() && hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
 
 		/*
 		 * Get here if this CPU took its interrupt from user
#7 lore raw

Re: [PATCH] v3 Teach RCU that idle task is not quiscent state at boot

Looks OK to me. It's a bit "theoretically" displeasing that you still treat synchronize_rcu as a gp even after we spawn some kernel threads.

... but it probably isn't worth trying to rearrange the boot code just to make this look better. I can't see any actual problems that could arise, as the threads should not have had a chance to run yet.

I wonder if you couldn't put in a WARN_ON(nr_context_switches() > 0) in rcu_idle_now_means_idle() just in case?

Quoted 3 lines · Paul E. McKenney

This patch fixes a bug located by Vegard Nossum with the aid of kmemcheck, updated based on review comments from Nick Piggin, Ingo Molnar, and Andrew Morton.

#8 lore raw

Re: [PATCH] v3 Teach RCU that idle task is not quiscent state at boot

Quoted 8 lines · Nick Piggin

Looks OK to me. It's a bit "theoretically" displeasing that you still treat synchronize_rcu as a gp even after we spawn some kernel threads.

... but it probably isn't worth trying to rearrange the boot code just to make this look better. I can't see any actual problems that could arise, as the threads should not have had a chance to run yet.

And if rcuclassic or rcutree on a UP system, even if threads have had a chance to run, it is OK to treat synchronize_rcu() as a grace period, since it has the opportunity to block.

Quoted 2 lines

I wonder if you couldn't put in a WARN_ON(nr_context_switches() > 0) in rcu_idle_now_means_idle() just in case?

Makes a lot of sense -- updated and am firing off the tests!

Thanx, Paul

Quoted 4 lines · Paul E. McKenney
Quoted 3 lines

This patch fixes a bug located by Vegard Nossum with the aid of kmemcheck, updated based on review comments from Nick Piggin, Ingo Molnar, and Andrew Morton.

#9 lore raw

PATCH 1/1 v4 Teach RCU that idle task is not quiscent state at boot

In reply to Paul E. McKenney

This patch fixes a bug located by Vegard Nossum with the aid of kmemcheck, updated based on review comments from Nick Piggin, Ingo Molnar, and Andrew Morton.

The boot CPU runs in the context of its idle thread during boot-up. During this time, idle_cpu(0) will always return nonzero, which will fool Classic and Hierarchical RCU into deciding that a large chunk of the boot-up sequence is a big long quiescent state. This in turn causes RCU to prematurely end grace periods during this time.

This patch changes the rcutree.c and rcuclassic.c rcu_check_callbacks() function to ignore the idle task as a quiescent state until the system has started up the scheduler in rest_init(), introducing a new non-API function rcu_idle_now_means_idle() to inform RCU of this transition. RCU maintains an internal rcu_idle_cpu_truthful variable to track this state, which is then used by rcu_check_callback() to determine if it should believe idle_cpu().

Because this patch has the effect of disallowing RCU grace periods during long stretches of the boot-up sequence, this patch also introduces Josh Triplett's UP-only optimization that makes synchronize_rcu() be a no-op if num_online_cpus() returns 1. This allows boot-time code that calls synchronize_rcu() to proceed normally. Note, however, that RCU callbacks registered by call_rcu() will likely queue up until later in the boot sequence. Although rcuclassic and rcutree can also use this same optimization after boot completes, rcupreempt must restrict its use of this optimization to the portion of the boot sequence before the scheduler starts up, given that an rcupreempt RCU read-side critical section may be preeempted.

In addition, this patch takes Nick Piggin's suggestion to make the system_state global variable be __read_mostly.

Changes since v3:

o WARN_ON(nr_context_switches() > 0) to verify that RCU
switches out of boot-time mode before the first context switch, as suggested by Nick Piggin.

Changes since v2:

o Created rcu_blocking_is_gp() internal-to-RCU API that
determines whether a call to synchronize_rcu() is itself a grace period.

o The definition of rcu_blocking_is_gp() for rcuclassic and
rcutree checks to see if but a single CPU is online.

o The definition of rcu_blocking_is_gp() for rcupreempt
checks to see both if but a single CPU is online and if the system is still in early boot.

This allows rcupreempt to again work correctly if running on a single CPU after booting is complete.

o Added check to rcupreempt's synchronize_sched() for there
being but one online CPU.

Tested all three variants both SMP and !SMP, booted fine, passed a short rcutorture test on both x86 and Power.

---

 include/linux/rcuclassic.h |    6 ++++++
 include/linux/rcupdate.h   |    4 ++++
 include/linux/rcupreempt.h |   15 +++++++++++++++
 include/linux/rcutree.h    |    6 ++++++
 init/main.c                |    3 ++-
 kernel/rcuclassic.c        |    4 ++--
 kernel/rcupdate.c          |   12 ++++++++++++
 kernel/rcupreempt.c        |    3 +++
 kernel/rcutree.c           |    4 ++--
 9 files changed, 52 insertions(+), 5 deletions(-)
include/linux/rcuclassic.h +6 -0
index f3f697d..80044a4 100644
@@ -181,4 +181,10 @@ extern long rcu_batches_completed_bh(void);
 #define rcu_enter_nohz()	do { } while (0)
 #define rcu_exit_nohz()		do { } while (0)
 
+/* A context switch is a grace period for rcuclassic. */
+static inline int rcu_blocking_is_gp(void)
+{
+	return num_online_cpus() == 1;
+}
+
 #endif /* __LINUX_RCUCLASSIC_H */
include/linux/rcupdate.h +4 -0
index 921340a..1e5249d 100644
@@ -52,6 +52,9 @@ struct rcu_head {
 	void (*func)(struct rcu_head *head);
 };
 
+/* Internal to kernel, but needed by rcupreempt.h. */
+extern int rcu_idle_cpu_truthful;
+
 #if defined(CONFIG_CLASSIC_RCU)
 #include <linux/rcuclassic.h>
 #elif defined(CONFIG_TREE_RCU)
@@ -265,6 +268,7 @@ extern void rcu_barrier_sched(void);
 
 /* Internal to kernel */
 extern void rcu_init(void);
+extern void rcu_idle_now_means_idle(void);
 extern int rcu_needs_cpu(int cpu);
 
 #endif /* __LINUX_RCUPDATE_H */
include/linux/rcupreempt.h +15 -0
index 3e05c09..504973d 100644
@@ -142,4 +142,19 @@ static inline void rcu_exit_nohz(void)
 #define rcu_exit_nohz()		do { } while (0)
 #endif /* CONFIG_NO_HZ */
 
+/*
+ * A context switch is a grace period for rcupreempt synchronize_rcu()
+ * only during early boot, before the scheduler has been initialized.
+ * So, how the heck do we get a context switch?  Well, if the caller
+ * invokes synchronize_rcu(), they are willing to accept a context
+ * switch, so we simply pretend that one happened.
+ *
+ * After boot, there might be a blocked or preempted task in an RCU
+ * read-side critical section, so we cannot then take the fastpath.
+ */
+static inline int rcu_blocking_is_gp(void)
+{
+	return num_online_cpus() == 1 && !rcu_idle_cpu_truthful;
+}
+
 #endif /* __LINUX_RCUPREEMPT_H */
include/linux/rcutree.h +6 -0
index d4368b7..a722fb6 100644
@@ -326,4 +326,10 @@ static inline void rcu_exit_nohz(void)
 }
 #endif /* CONFIG_NO_HZ */
 
+/* A context switch is a grace period for rcutree. */
+static inline int rcu_blocking_is_gp(void)
+{
+	return num_online_cpus() == 1;
+}
+
 #endif /* __LINUX_RCUTREE_H */
init/main.c +2 -1
index 8442094..b952287 100644
@@ -97,7 +97,7 @@ static inline void mark_rodata_ro(void) { }
 extern void tc_init(void);
 #endif
 
-enum system_states system_state;
+enum system_states system_state __read_mostly;
 EXPORT_SYMBOL(system_state);
 
 /*
@@ -463,6 +463,7 @@ static noinline void __init_refok rest_init(void)
 	 * at least once to get things moving:
 	 */
 	init_idle_bootup_task(current);
+	rcu_idle_now_means_idle();
 	preempt_enable_no_resched();
 	schedule();
 	preempt_disable();
kernel/rcuclassic.c +2 -2
index bd5a900..b4377de 100644
@@ -679,8 +679,8 @@ int rcu_needs_cpu(int cpu)
 void rcu_check_callbacks(int cpu, int user)
 {
 	if (user ||
-	    (idle_cpu(cpu) && !in_softirq() &&
-				hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
+	    (idle_cpu(cpu) && rcu_idle_cpu_truthful &&
+	     !in_softirq() && hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
 
 		/*
 		 * Get here if this CPU took its interrupt from user
kernel/rcupdate.c +12 -0
index d92a76a..ace4fd4 100644
@@ -44,6 +44,7 @@
 #include <linux/cpu.h>
 #include <linux/mutex.h>
 #include <linux/module.h>
+#include <linux/kernel_stat.h>
 
 enum rcu_barrier {
 	RCU_BARRIER_STD,
@@ -55,6 +56,7 @@ static DEFINE_PER_CPU(struct rcu_head, rcu_barrier_head) = {NULL};
 static atomic_t rcu_barrier_cpu_count;
 static DEFINE_MUTEX(rcu_barrier_mutex);
 static struct completion rcu_barrier_completion;
+int rcu_idle_cpu_truthful __read_mostly;
 
 /*
  * Awaken the corresponding synchronize_rcu() instance now that a
@@ -80,6 +82,10 @@ void wakeme_after_rcu(struct rcu_head  *head)
 void synchronize_rcu(void)
 {
 	struct rcu_synchronize rcu;
+
+	if (rcu_blocking_is_gp())
+		return;
+
 	init_completion(&rcu.completion);
 	/* Will wake me after RCU finished. */
 	call_rcu(&rcu.head, wakeme_after_rcu);
@@ -175,3 +181,9 @@ void __init rcu_init(void)
 	__rcu_init();
 }
 
+void rcu_idle_now_means_idle(void)
+{
+	WARN_ON(num_online_cpus() != 1);
+	WARN_ON(nr_context_switches() > 0);
+	rcu_idle_cpu_truthful = 1;
+}
kernel/rcupreempt.c +3 -0
index 33cfc50..5d59e85 100644
@@ -1181,6 +1181,9 @@ void __synchronize_sched(void)
 {
 	struct rcu_synchronize rcu;
 
+	if (num_online_cpus() == 1)
+		return;  /* blocking is gp if only one CPU! */
+
 	init_completion(&rcu.completion);
 	/* Will wake me after RCU finished. */
 	call_rcu_sched(&rcu.head, wakeme_after_rcu);
kernel/rcutree.c +2 -2
index b2fd602..b37a7b1 100644
@@ -948,8 +948,8 @@ static void rcu_do_batch(struct rcu_data *rdp)
 void rcu_check_callbacks(int cpu, int user)
 {
 	if (user ||
-	    (idle_cpu(cpu) && !in_softirq() &&
-				hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
+	    (idle_cpu(cpu) && rcu_idle_cpu_truthful &&
+	     !in_softirq() && hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
 
 		/*
 		 * Get here if this CPU took its interrupt from user
#10 lore raw

Re: [PATCH] v4 Teach RCU that idle task is not quiscent state at boot

include/linux/rcupdate.h struct rcu_head { · line 56

Quoted 2 lines · Paul E. McKenney
include/linux/rcupdate.h +2 -0
+/* Internal to kernel, but needed by rcupreempt.h. */
+extern int rcu_idle_cpu_truthful;

The name sucks a bit ;-) 'truthful' is an emotionally laden statement and distracts from the technical purpose when reading it ;)

Same for:

Quoted 1 line

+extern void rcu_idle_now_means_idle(void);

Also, i'm wondering, is there really no way to avoid this quirk. We almost got away without it for a long time.

This one:

kernel/rcuclassic.c int rcu_needs_cpu(int cpu) · line 683

Quoted 7 lines

void rcu_check_callbacks(int cpu, int user)
{

kernel/rcuclassic.c +2 -2
 	if (user ||
-	    (idle_cpu(cpu) && !in_softirq() &&
-				hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
+	    (idle_cpu(cpu) && rcu_idle_cpu_truthful &&
+	     !in_softirq() && hardirq_count() <= (1 << HARDIRQ_SHIFT))) {

Is a hotpath called very often ...

Ingo

#11 lore raw

Re: [PATCH] v4 Teach RCU that idle task is not quiscent state at boot

Quoted 10 lines · Ingo Molnar

include/linux/rcupdate.h struct rcu_head { · line 56

Quoted 2 lines · Paul E. McKenney
include/linux/rcupdate.h +2 -0
+/* Internal to kernel, but needed by rcupreempt.h. */
+extern int rcu_idle_cpu_truthful;

The name sucks a bit ;-) 'truthful' is an emotionally laden statement and distracts from the technical purpose when reading it ;)

Quoted 6 lines

Same for:

Quoted 1 line

+extern void rcu_idle_now_means_idle(void);

Also, i'm wondering, is there really no way to avoid this quirk. We almost got away without it for a long time.

I wonder if you couldn't leave cpu_rq(cpu)->idle as NULL until right up to the point where it actually becomes the "idle" thread? This would make idle_cpu() more truthful for all other callers in early boot code too. And rcupdate shouldn't need any changes (except the num_online_cpus() == 1 shortcut probably remains as a nice opt).

Quoted 13 lines

This one:

kernel/rcuclassic.c int rcu_needs_cpu(int cpu) · line 683

Quoted 7 lines

void rcu_check_callbacks(int cpu, int user)
{

kernel/rcuclassic.c +2 -2
 	if (user ||
-	    (idle_cpu(cpu) && !in_softirq() &&
-				hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
+	    (idle_cpu(cpu) && rcu_idle_cpu_truthful &&
+	     !in_softirq() && hardirq_count() <= (1 << HARDIRQ_SHIFT))) {

Is a hotpath called very often ...

Ingo

#12 lore raw

Re: [PATCH] v4 Teach RCU that idle task is not quiscent state at boot

Quoted 15 lines · Nick Piggin
Quoted 14 lines · Ingo Molnar

include/linux/rcupdate.h struct rcu_head { · line 56

Quoted 2 lines · Paul E. McKenney
include/linux/rcupdate.h +2 -0
+/* Internal to kernel, but needed by rcupreempt.h. */
+extern int rcu_idle_cpu_truthful;

The name sucks a bit ;-) 'truthful' is an emotionally laden statement and distracts from the technical purpose when reading it ;)

Same for:

Quoted 1 line

+extern void rcu_idle_now_means_idle(void);

Quoted 8 lines
Quoted 2 lines

Also, i'm wondering, is there really no way to avoid this quirk. We almost got away without it for a long time.

I wonder if you couldn't leave cpu_rq(cpu)->idle as NULL until right up to the point where it actually becomes the "idle" thread? This would make idle_cpu() more truthful for all other callers in early boot code too. And rcupdate shouldn't need any changes (except the num_online_cpus() == 1 shortcut probably remains as a nice opt).

It looked to me that the idle task initialization was moved early to allow interrupt handlers to see a more normal environment, but I could easily be confused here.

Thanx, Paul

Quoted 13 lines
Quoted 13 lines

This one:

kernel/rcuclassic.c int rcu_needs_cpu(int cpu) · line 683

Quoted 7 lines

void rcu_check_callbacks(int cpu, int user)
{

kernel/rcuclassic.c +2 -2
 	if (user ||
-	    (idle_cpu(cpu) && !in_softirq() &&
-				hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
+	    (idle_cpu(cpu) && rcu_idle_cpu_truthful &&
+	     !in_softirq() && hardirq_count() <= (1 << HARDIRQ_SHIFT))) {

Is a hotpath called very often ...

Ingo

#13 lore raw

Re: [PATCH] v4 Teach RCU that idle task is not quiscent state at boot

Quoted 10 lines · Paul E. McKenney
Quoted 5 lines · Nick Piggin

I wonder if you couldn't leave cpu_rq(cpu)->idle as NULL until right up to the point where it actually becomes the "idle" thread? This would make idle_cpu() more truthful for all other callers in early boot code too. And rcupdate shouldn't need any changes (except the num_online_cpus() == 1 shortcut probably remains as a nice opt).

It looked to me that the idle task initialization was moved early to allow interrupt handlers to see a more normal environment, but I could easily be confused here.

I think we might be OK. I think interrupt handlers shouldn't care so much about whether the cpu is idle or not (and seeing !idle here would be more accurate anyway).

#14 lore raw

Re: [PATCH] v4 Teach RCU that idle task is not quiscent state at boot

Quoted 8 lines · Nick Piggin
Quoted 7 lines · Paul E. McKenney
Quoted 5 lines · Nick Piggin

I wonder if you couldn't leave cpu_rq(cpu)->idle as NULL until right up to the point where it actually becomes the "idle" thread? This would make idle_cpu() more truthful for all other callers in early boot code too. And rcupdate shouldn't need any changes (except the num_online_cpus() == 1 shortcut probably remains as a nice opt).

Quoted 7 lines
Quoted 3 lines

It looked to me that the idle task initialization was moved early to allow interrupt handlers to see a more normal environment, but I could easily be confused here.

I think we might be OK. I think interrupt handlers shouldn't care so much about whether the cpu is idle or not (and seeing !idle here would be more accurate anyway).

My impression is that they mostly care about the CPU appearing to be running in the context of a task. I suppose one could create an extra task for this, or leave rq->idle NULL... But I don't have a full set of architectures, let alone devices, with which to test such a change.

Thanx, Paul

#15 lore raw

Re: [PATCH] v4 Teach RCU that idle task is not quiscent state at boot

In reply to Ingo Molnar
Quoted 13 lines · Ingo Molnar

include/linux/rcupdate.h struct rcu_head { · line 56

Quoted 2 lines · Paul E. McKenney
include/linux/rcupdate.h +2 -0
+/* Internal to kernel, but needed by rcupreempt.h. */
+extern int rcu_idle_cpu_truthful;

The name sucks a bit ;-) 'truthful' is an emotionally laden statement and distracts from the technical purpose when reading it ;)

Same for:

Quoted 1 line

+extern void rcu_idle_now_means_idle(void);

I must confess that I was in fact a bit annoyed to learn that idle_cpu() telling me that a decidedly active CPU was idle. And if you think -these- names are emotionally laden, you should have seen my first choices. ;-)

Nevertheless, point well taken. How about the following names instead?

	extern int rcu_scheduler_active;
	extern void rcu_scheduler_starting(void);
Quoted 2 lines

Also, i'm wondering, is there really no way to avoid this quirk. We almost got away without it for a long time.

A bit scary, isn't it? ;-)

Looks to me that some RCU usage finally found its way into the early boot code path -- until that happened, no one needed to care what RCU mistakenly thought was happening with grace periods at early boot.

I list some alternatives below.

Quoted 11 lines

This one:

kernel/rcuclassic.c int rcu_needs_cpu(int cpu) · line 683

Quoted 7 lines

void rcu_check_callbacks(int cpu, int user)
{

kernel/rcuclassic.c +2 -2
 	if (user ||
-	    (idle_cpu(cpu) && !in_softirq() &&
-				hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
+	    (idle_cpu(cpu) && rcu_idle_cpu_truthful &&
+	     !in_softirq() && hardirq_count() <= (1 << HARDIRQ_SHIFT))) {

Is a hotpath called very often ...

The "if" statement is indeed on the hotpath, but the additional check of rcu_idle_cpu_truthful is reached only if we didn't interrupt from user-mode execution and if the CPU is idle. So the only time anything is delayed by this extra check is when we take an interrupt from idle state, and then that interrupt handler is itself interrupted by the scheduling-clock interrupt.

And of course, in the CONFIG_NO_HZ case, this code path is normally disabled entirely for an idle CPU.

This therefore will not result in significant overhead, despite being in a hotpath.

OK, alternatives...

o Reverse the roles of the idle and init threads during startup,
so that there is initially no idle thread.

However, there appears to be a fair amount of code that assumes that there is always an idle thread.

o As above, but create both the init and idle threads early so
that there always is an idle thread that happens not to be running during boot.

This would work, but seems to me to be uglier than the flag.

o Stop using idle_cpu() in rcu_check_callbacks(), instead keeping
a per-CPU "cpu_is_idle" variable that is set upon entry to the various idle() loops and cleared upon exit. It would be OK to take interrupts while "cpu_is_idle" is set.

The disadvantage here is that there are quite a few idle loops, and it would be necessary to change them all. Missing one or two could result in indefinite grace periods on the affected systems.

o Drop idle as a quiescent state, as is already the case for
rcupreempt.

This would result in indefinite grace-period delays for rcuclassic, but would actually work for rcutree. Except that it would cause rcutree to IPI each and every idle CPU for every grace period if !CONFIG_NO_HZ. I expect that this overhead would far exceed that of the extra flag check in rcu_check_callbacks().

So I still like the flag check. Any alternatives that I am missing?

Thanx, Paul

#16 lore raw

Re: [PATCH] v4 Teach RCU that idle task is not quiscent state at boot

Quoted 27 lines · Paul E. McKenney

OK, alternatives...

o Reverse the roles of the idle and init threads during startup,
so that there is initially no idle thread.

However, there appears to be a fair amount of code that assumes that there is always an idle thread.

o As above, but create both the init and idle threads early so
that there always is an idle thread that happens not to be running during boot.

This would work, but seems to me to be uglier than the flag.

o Stop using idle_cpu() in rcu_check_callbacks(), instead keeping
a per-CPU "cpu_is_idle" variable that is set upon entry to the various idle() loops and cleared upon exit. It would be OK to take interrupts while "cpu_is_idle" is set.

The disadvantage here is that there are quite a few idle loops, and it would be necessary to change them all. Missing one or two could result in indefinite grace periods on the affected systems.

o Drop idle as a quiescent state, as is already the case for
rcupreempt.

Quoted 8 lines

This would result in indefinite grace-period delays for rcuclassic, but would actually work for rcutree. Except that it would cause rcutree to IPI each and every idle CPU for every grace period if !CONFIG_NO_HZ. I expect that this overhead would far exceed that of the extra flag check in rcu_check_callbacks().

So I still like the flag check. Any alternatives that I am missing?

Indeed none of the alternatives looks particularly appealing, so i concur. Thanks Paul for analyzing it so thoroughly!

Ingo

Tested-by on v1 1/1
#17 lore raw

Re: [PATCH] v4 Teach RCU that idle task is not quiscent state at boot

In reply to Paul E. McKenney

2009/2/25 Paul E. McKenney <[email protected]>:

Quoted 55 lines

This patch fixes a bug located by Vegard Nossum with the aid of kmemcheck, updated based on review comments from Nick Piggin, Ingo Molnar, and Andrew Morton.

The boot CPU runs in the context of its idle thread during boot-up. During this time, idle_cpu(0) will always return nonzero, which will fool Classic and Hierarchical RCU into deciding that a large chunk of the boot-up sequence is a big long quiescent state.  This in turn causes RCU to prematurely end grace periods during this time.

This patch changes the rcutree.c and rcuclassic.c rcu_check_callbacks() function to ignore the idle task as a quiescent state until the system has started up the scheduler in rest_init(), introducing a new non-API function rcu_idle_now_means_idle() to inform RCU of this transition.  RCU maintains an internal rcu_idle_cpu_truthful variable to track this state, which is then used by rcu_check_callback() to determine if it should believe idle_cpu().

Because this patch has the effect of disallowing RCU grace periods during long stretches of the boot-up sequence, this patch also introduces Josh Triplett's UP-only optimization that makes synchronize_rcu() be a no-op if num_online_cpus() returns 1.  This allows boot-time code that calls synchronize_rcu() to proceed normally.  Note, however, that RCU callbacks registered by call_rcu() will likely queue up until later in the boot sequence.  Although rcuclassic and rcutree can also use this same optimization after boot completes, rcupreempt must restrict its use of this optimization to the portion of the boot sequence before the scheduler starts up, given that an rcupreempt RCU read-side critical section may be preeempted.

In addition, this patch takes Nick Piggin's suggestion to make the system_state global variable be __read_mostly.

Changes since v3:

o       WARN_ON(nr_context_switches() > 0) to verify that RCU switches out of boot-time mode before the first context switch, as suggested by Nick Piggin.

Changes since v2:

o       Created rcu_blocking_is_gp() internal-to-RCU API that determines whether a call to synchronize_rcu() is itself a grace period.

o       The definition of rcu_blocking_is_gp() for rcuclassic and rcutree checks to see if but a single CPU is online.

o       The definition of rcu_blocking_is_gp() for rcupreempt checks to see both if but a single CPU is online and if the system is still in early boot.

       This allows rcupreempt to again work correctly if running on a single CPU after booting is complete.

Quoted 8 lines

o       Added check to rcupreempt's synchronize_sched() for there being but one online CPU.

Tested all three variants both SMP and !SMP, booted fine, passed a short rcutorture test on both x86 and Power.

I used such a patch and config (as attached) to verify. On unpatched kernel, I get this:

rcu callbacks called: 2300 (should be 4000)

And with the patch, it seems better:

rcu callbacks called: 4000 (should be 4000)

Actually, the first part of the text itself is wrong, because it used to count upwards. But it should really say "rcu callbacks NOT called".

Of course, this kind of check will always be inaccurate, so it is not fit for mainline. The inaccuracy stems from the fact that there could be other users of RCU that disturb our expected behaviour, and we don't know how quickly the callbacks will be run, only that if "enough" of them run inside the spinlock, something is probably wrong. But... what am I saying, you're the expert ;-)

But it is useful enough to verify your patch. Some other configs I tried gave the correct result all the time, but I don't know what is special about this one.

Vegard

Signature · 4 lines
"The animistic metaphor of the bug that maliciously sneaked in while
the programmer was not looking is intellectually dishonest as it
disguises that the error is the programmer's own creation."
	-- E. W. Dijkstra, EWD1036

From 6ecacd2411ea0e8fd101a16a9c943f6883c2c191 Mon Sep 17 00:00:00 2001
From: Vegard Nossum <[email protected]>
Date: Wed, 25 Feb 2009 18:58:41 +0100
Subject: [PATCH] rcu boot self-test

---
 init/main.c |   40 ++++++++++++++++++++++++++++++++++++++++
 1 files changed, 40 insertions(+), 0 deletions(-)
init/main.c +40 -0
index 7459fad..f2e2657 100644
@@ -440,6 +440,45 @@ static void __init setup_command_line(char *command_line)
 	strcpy (static_command_line, command_line);
 }
 
+static atomic_t rcu_idletest_counter;
+
+struct rcu_idletest_context {
+	struct rcu_head rcu_head;
+};
+
+static void rcu_idletest_callback(struct rcu_head *head)
+{
+	struct rcu_idletest_context *ctx =
+		container_of(head, struct rcu_idletest_context, rcu_head);
+
+	if (atomic_dec_and_test(&rcu_idletest_counter))
+		printk("last rcu_idletest_callback called!\n");
+	kfree(ctx);
+}
+
+static void rcu_idletest(void)
+{
+	static const int n = 4000;
+
+	spinlock_t lock;
+	int i;
+
+	atomic_set(&rcu_idletest_counter, n);
+
+	spin_lock_init(&lock);
+	spin_lock(&lock);
+	for (i = 0; i < n; ++i) {
+		struct rcu_idletest_context *ctx;
+
+		ctx = kmalloc(sizeof(*ctx), GFP_KERNEL);
+		call_rcu(&ctx->rcu_head, &rcu_idletest_callback);
+	}
+
+	printk(KERN_DEBUG "rcu callbacks called: %d (should be %d)\n",
+		atomic_read(&rcu_idletest_counter), n);
+	spin_unlock(&lock);
+}
+
 /*
  * We need to finalize in a non-__init function or else race conditions
  * between the root thread and the init thread may cause start_kernel to
@@ -684,6 +723,7 @@ asmlinkage void __init start_kernel(void)
 	taskstats_init_early();
 	delayacct_init();
 
+	rcu_idletest();
 	check_bugs();
 
 	acpi_early_init(); /* before LAPIC and SMP init */
Signature · 1 line
1.6.0.6
#18 lore raw

Re: [PATCH] v4 Teach RCU that idle task is not quiscent state at boot

Quoted 70 lines · Vegard Nossum

2009/2/25 Paul E. McKenney <[email protected]>:

Quoted 55 lines

This patch fixes a bug located by Vegard Nossum with the aid of kmemcheck, updated based on review comments from Nick Piggin, Ingo Molnar, and Andrew Morton.

The boot CPU runs in the context of its idle thread during boot-up. During this time, idle_cpu(0) will always return nonzero, which will fool Classic and Hierarchical RCU into deciding that a large chunk of the boot-up sequence is a big long quiescent state.  This in turn causes RCU to prematurely end grace periods during this time.

This patch changes the rcutree.c and rcuclassic.c rcu_check_callbacks() function to ignore the idle task as a quiescent state until the system has started up the scheduler in rest_init(), introducing a new non-API function rcu_idle_now_means_idle() to inform RCU of this transition.  RCU maintains an internal rcu_idle_cpu_truthful variable to track this state, which is then used by rcu_check_callback() to determine if it should believe idle_cpu().

Because this patch has the effect of disallowing RCU grace periods during long stretches of the boot-up sequence, this patch also introduces Josh Triplett's UP-only optimization that makes synchronize_rcu() be a no-op if num_online_cpus() returns 1.  This allows boot-time code that calls synchronize_rcu() to proceed normally.  Note, however, that RCU callbacks registered by call_rcu() will likely queue up until later in the boot sequence.  Although rcuclassic and rcutree can also use this same optimization after boot completes, rcupreempt must restrict its use of this optimization to the portion of the boot sequence before the scheduler starts up, given that an rcupreempt RCU read-side critical section may be preeempted.

In addition, this patch takes Nick Piggin's suggestion to make the system_state global variable be __read_mostly.

Changes since v3:

o       WARN_ON(nr_context_switches() > 0) to verify that RCU switches out of boot-time mode before the first context switch, as suggested by Nick Piggin.

Changes since v2:

o       Created rcu_blocking_is_gp() internal-to-RCU API that determines whether a call to synchronize_rcu() is itself a grace period.

o       The definition of rcu_blocking_is_gp() for rcuclassic and rcutree checks to see if but a single CPU is online.

o       The definition of rcu_blocking_is_gp() for rcupreempt checks to see both if but a single CPU is online and if the system is still in early boot.

       This allows rcupreempt to again work correctly if running on a single CPU after booting is complete.

Quoted 8 lines

o       Added check to rcupreempt's synchronize_sched() for there being but one online CPU.

Tested all three variants both SMP and !SMP, booted fine, passed a short rcutorture test on both x86 and Power.

I used such a patch and config (as attached) to verify. On unpatched kernel, I get this:

Quoted 8 lines

rcu callbacks called: 2300 (should be 4000)

And with the patch, it seems better:

rcu callbacks called: 4000 (should be 4000)

Actually, the first part of the text itself is wrong, because it used to count upwards. But it should really say "rcu callbacks NOT called".

Yes, your test patch does look like it validates my patch, thank you!!!

Quoted 6 lines

Of course, this kind of check will always be inaccurate, so it is not fit for mainline. The inaccuracy stems from the fact that there could be other users of RCU that disturb our expected behaviour, and we don't know how quickly the callbacks will be run, only that if "enough" of them run inside the spinlock, something is probably wrong. But... what am I saying, you're the expert ;-)

On RCU, maybe, but the boot-time code has changed considerably since I last looked at it. ;-)

Quoted 3 lines

But it is useful enough to verify your patch. Some other configs I tried gave the correct result all the time, but I don't know what is special about this one.

Thank you again!!!

I will be submitting another patch that differs only in the names of the variable and function that Ingo pointed out, so I believe it will be legitimate to attach your Tested-by: to that upcoming patch.

Thanx, Paul

#19 lore raw

PATCH 1/1 v5 Teach RCU that idle task is not quiscent state at boot

In reply to Paul E. McKenney

This patch fixes a bug located by Vegard Nossum with the aid of kmemcheck, updated based on review comments from Nick Piggin, Ingo Molnar, and Andrew Morton. And cleans up the variable-name and function-name language. ;-)

The boot CPU runs in the context of its idle thread during boot-up. During this time, idle_cpu(0) will always return nonzero, which will fool Classic and Hierarchical RCU into deciding that a large chunk of the boot-up sequence is a big long quiescent state. This in turn causes RCU to prematurely end grace periods during this time.

This patch changes the rcutree.c and rcuclassic.c rcu_check_callbacks() function to ignore the idle task as a quiescent state until the system has started up the scheduler in rest_init(), introducing a new non-API function rcu_idle_now_means_idle() to inform RCU of this transition. RCU maintains an internal rcu_idle_cpu_truthful variable to track this state, which is then used by rcu_check_callback() to determine if it should believe idle_cpu().

Because this patch has the effect of disallowing RCU grace periods during long stretches of the boot-up sequence, this patch also introduces Josh Triplett's UP-only optimization that makes synchronize_rcu() be a no-op if num_online_cpus() returns 1. This allows boot-time code that calls synchronize_rcu() to proceed normally. Note, however, that RCU callbacks registered by call_rcu() will likely queue up until later in the boot sequence. Although rcuclassic and rcutree can also use this same optimization after boot completes, rcupreempt must restrict its use of this optimization to the portion of the boot sequence before the scheduler starts up, given that an rcupreempt RCU read-side critical section may be preeempted.

In addition, this patch takes Nick Piggin's suggestion to make the system_state global variable be __read_mostly.

Changes since v4:

o Changes the name of the introduced function and variable to
be less emotional. ;-)

Changes since v3:

o WARN_ON(nr_context_switches() > 0) to verify that RCU
switches out of boot-time mode before the first context switch, as suggested by Nick Piggin.

Changes since v2:

o Created rcu_blocking_is_gp() internal-to-RCU API that
determines whether a call to synchronize_rcu() is itself a grace period.

o The definition of rcu_blocking_is_gp() for rcuclassic and
rcutree checks to see if but a single CPU is online.

o The definition of rcu_blocking_is_gp() for rcupreempt
checks to see both if but a single CPU is online and if the system is still in early boot.

This allows rcupreempt to again work correctly if running on a single CPU after booting is complete.

o Added check to rcupreempt's synchronize_sched() for there
being but one online CPU.

Tested all three variants both SMP and !SMP, booted fine, passed a short rcutorture test on both x86 and Power.

---

 include/linux/rcuclassic.h |    6 ++++++
 include/linux/rcupdate.h   |    4 ++++
 include/linux/rcupreempt.h |   15 +++++++++++++++
 include/linux/rcutree.h    |    6 ++++++
 init/main.c                |    3 ++-
 kernel/rcuclassic.c        |    4 ++--
 kernel/rcupdate.c          |   12 ++++++++++++
 kernel/rcupreempt.c        |    3 +++
 kernel/rcutree.c           |    4 ++--
 9 files changed, 52 insertions(+), 5 deletions(-)
include/linux/rcuclassic.h +6 -0
index f3f697d..80044a4 100644
@@ -181,4 +181,10 @@ extern long rcu_batches_completed_bh(void);
 #define rcu_enter_nohz()	do { } while (0)
 #define rcu_exit_nohz()		do { } while (0)
 
+/* A context switch is a grace period for rcuclassic. */
+static inline int rcu_blocking_is_gp(void)
+{
+	return num_online_cpus() == 1;
+}
+
 #endif /* __LINUX_RCUCLASSIC_H */
include/linux/rcupdate.h +4 -0
index 921340a..528343e 100644
@@ -52,6 +52,9 @@ struct rcu_head {
 	void (*func)(struct rcu_head *head);
 };
 
+/* Internal to kernel, but needed by rcupreempt.h. */
+extern int rcu_scheduler_active;
+
 #if defined(CONFIG_CLASSIC_RCU)
 #include <linux/rcuclassic.h>
 #elif defined(CONFIG_TREE_RCU)
@@ -265,6 +268,7 @@ extern void rcu_barrier_sched(void);
 
 /* Internal to kernel */
 extern void rcu_init(void);
+extern void rcu_scheduler_starting(void);
 extern int rcu_needs_cpu(int cpu);
 
 #endif /* __LINUX_RCUPDATE_H */
include/linux/rcupreempt.h +15 -0
index 3e05c09..74304b4 100644
@@ -142,4 +142,19 @@ static inline void rcu_exit_nohz(void)
 #define rcu_exit_nohz()		do { } while (0)
 #endif /* CONFIG_NO_HZ */
 
+/*
+ * A context switch is a grace period for rcupreempt synchronize_rcu()
+ * only during early boot, before the scheduler has been initialized.
+ * So, how the heck do we get a context switch?  Well, if the caller
+ * invokes synchronize_rcu(), they are willing to accept a context
+ * switch, so we simply pretend that one happened.
+ *
+ * After boot, there might be a blocked or preempted task in an RCU
+ * read-side critical section, so we cannot then take the fastpath.
+ */
+static inline int rcu_blocking_is_gp(void)
+{
+	return num_online_cpus() == 1 && !rcu_scheduler_active;
+}
+
 #endif /* __LINUX_RCUPREEMPT_H */
include/linux/rcutree.h +6 -0
index d4368b7..a722fb6 100644
@@ -326,4 +326,10 @@ static inline void rcu_exit_nohz(void)
 }
 #endif /* CONFIG_NO_HZ */
 
+/* A context switch is a grace period for rcutree. */
+static inline int rcu_blocking_is_gp(void)
+{
+	return num_online_cpus() == 1;
+}
+
 #endif /* __LINUX_RCUTREE_H */
init/main.c +2 -1
index 8442094..83697e1 100644
@@ -97,7 +97,7 @@ static inline void mark_rodata_ro(void) { }
 extern void tc_init(void);
 #endif
 
-enum system_states system_state;
+enum system_states system_state __read_mostly;
 EXPORT_SYMBOL(system_state);
 
 /*
@@ -463,6 +463,7 @@ static noinline void __init_refok rest_init(void)
 	 * at least once to get things moving:
 	 */
 	init_idle_bootup_task(current);
+	rcu_scheduler_starting();
 	preempt_enable_no_resched();
 	schedule();
 	preempt_disable();
kernel/rcuclassic.c +2 -2
index bd5a900..654c640 100644
@@ -679,8 +679,8 @@ int rcu_needs_cpu(int cpu)
 void rcu_check_callbacks(int cpu, int user)
 {
 	if (user ||
-	    (idle_cpu(cpu) && !in_softirq() &&
-				hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
+	    (idle_cpu(cpu) && rcu_scheduler_active &&
+	     !in_softirq() && hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
 
 		/*
 		 * Get here if this CPU took its interrupt from user
kernel/rcupdate.c +12 -0
index d92a76a..cae8a05 100644
@@ -44,6 +44,7 @@
 #include <linux/cpu.h>
 #include <linux/mutex.h>
 #include <linux/module.h>
+#include <linux/kernel_stat.h>
 
 enum rcu_barrier {
 	RCU_BARRIER_STD,
@@ -55,6 +56,7 @@ static DEFINE_PER_CPU(struct rcu_head, rcu_barrier_head) = {NULL};
 static atomic_t rcu_barrier_cpu_count;
 static DEFINE_MUTEX(rcu_barrier_mutex);
 static struct completion rcu_barrier_completion;
+int rcu_scheduler_active __read_mostly;
 
 /*
  * Awaken the corresponding synchronize_rcu() instance now that a
@@ -80,6 +82,10 @@ void wakeme_after_rcu(struct rcu_head  *head)
 void synchronize_rcu(void)
 {
 	struct rcu_synchronize rcu;
+
+	if (rcu_blocking_is_gp())
+		return;
+
 	init_completion(&rcu.completion);
 	/* Will wake me after RCU finished. */
 	call_rcu(&rcu.head, wakeme_after_rcu);
@@ -175,3 +181,9 @@ void __init rcu_init(void)
 	__rcu_init();
 }
 
+void rcu_scheduler_starting(void)
+{
+	WARN_ON(num_online_cpus() != 1);
+	WARN_ON(nr_context_switches() > 0);
+	rcu_scheduler_active = 1;
+}
kernel/rcupreempt.c +3 -0
index 33cfc50..5d59e85 100644
@@ -1181,6 +1181,9 @@ void __synchronize_sched(void)
 {
 	struct rcu_synchronize rcu;
 
+	if (num_online_cpus() == 1)
+		return;  /* blocking is gp if only one CPU! */
+
 	init_completion(&rcu.completion);
 	/* Will wake me after RCU finished. */
 	call_rcu_sched(&rcu.head, wakeme_after_rcu);
kernel/rcutree.c +2 -2
index b2fd602..97ce315 100644
@@ -948,8 +948,8 @@ static void rcu_do_batch(struct rcu_data *rdp)
 void rcu_check_callbacks(int cpu, int user)
 {
 	if (user ||
-	    (idle_cpu(cpu) && !in_softirq() &&
-				hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
+	    (idle_cpu(cpu) && rcu_scheduler_active &&
+	     !in_softirq() && hardirq_count() <= (1 << HARDIRQ_SHIFT))) {
 
 		/*
 		 * Get here if this CPU took its interrupt from user
Applied
#20 lore raw

Re: [PATCH] v5 Teach RCU that idle task is not quiscent state at boot

Quoted 4 lines · Paul E. McKenney

This patch fixes a bug located by Vegard Nossum with the aid of kmemcheck, updated based on review comments from Nick Piggin, Ingo Molnar, and Andrew Morton. And cleans up the variable-name and function-name language. ;-)

Applied to tip:core/rcu, thanks Paul!

Ingo