Skip to contentSkip to conversation

v1 expedited "big hammer" RCU grace periods

RFC PATCH In review Paul E. McKenney 5 participants 11 messages Apr 23, 2009 – Apr 24, 2009

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 v1 expedited "big hammer" RCU grace periods

First cut of "big hammer" expedited RCU grace periods, but only for rcu_bh. This creates another softirq vector, so that entering this softirq vector will have forced an rcu_bh quiescent state (as noted by Dave Miller). Use smp_call_function() to invoke raise_softirq() on all CPUs in order to cause this to happen. Track the CPUs that have passed through a quiescent state (or gone offline) with a cpumask.

Does nothing to expedite callbacks already registered with call_rcu_bh(), but there is no need to.

Shortcomings:

o Untested, probably does not compile, not for inclusion.

o Does not handle rcu, only rcu_bh.

Thoughts?

---

 include/linux/interrupt.h |    1 
 include/linux/rcupdate.h  |    1 
 kernel/rcupdate.c         |  106 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 108 insertions(+)
include/linux/interrupt.h +1 -0
index 91bb76f..b7b58cc 100644
@@ -338,6 +338,7 @@ enum
 	TASKLET_SOFTIRQ,
 	SCHED_SOFTIRQ,
 	HRTIMER_SOFTIRQ,
+	RCU_EXPEDITED_SOFTIRQ,
 	RCU_SOFTIRQ,	/* Preferable RCU should always be the last softirq */
 
 	NR_SOFTIRQS
include/linux/rcupdate.h +1 -0
index 15fbb3c..d4af557 100644
@@ -264,6 +264,7 @@ extern void synchronize_rcu(void);
 extern void rcu_barrier(void);
 extern void rcu_barrier_bh(void);
 extern void rcu_barrier_sched(void);
+extern void synchronize_rcu_bh_expedited(void);
 
 /* Internal to kernel */
 extern void rcu_init(void);
kernel/rcupdate.c +106 -0

116 lines not on this page · raw message

#1 lore raw
Quoted 162 lines · Paul E. McKenney

First cut of "big hammer" expedited RCU grace periods, but only for rcu_bh. This creates another softirq vector, so that entering this softirq vector will have forced an rcu_bh quiescent state (as noted by Dave Miller). Use smp_call_function() to invoke raise_softirq() on all CPUs in order to cause this to happen. Track the CPUs that have passed through a quiescent state (or gone offline) with a cpumask.

Does nothing to expedite callbacks already registered with call_rcu_bh(), but there is no need to.

Shortcomings:

o Untested, probably does not compile, not for inclusion.

o Does not handle rcu, only rcu_bh.

Thoughts?

---

 include/linux/interrupt.h |    1 
 include/linux/rcupdate.h  |    1 
 kernel/rcupdate.c         |  106 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 108 insertions(+)
include/linux/interrupt.h +1 -0
index 91bb76f..b7b58cc 100644
@@ -338,6 +338,7 @@ enum
 	TASKLET_SOFTIRQ,
 	SCHED_SOFTIRQ,
 	HRTIMER_SOFTIRQ,
+	RCU_EXPEDITED_SOFTIRQ,
 	RCU_SOFTIRQ,	/* Preferable RCU should always be the last softirq */
 
 	NR_SOFTIRQS
include/linux/rcupdate.h +1 -0
index 15fbb3c..d4af557 100644
@@ -264,6 +264,7 @@ extern void synchronize_rcu(void);
 extern void rcu_barrier(void);
 extern void rcu_barrier_bh(void);
 extern void rcu_barrier_sched(void);
+extern void synchronize_rcu_bh_expedited(void);
 
 /* Internal to kernel */
 extern void rcu_init(void);
kernel/rcupdate.c +103 -0
index a967c9f..bfa98dd 100644
@@ -217,10 +217,116 @@ static int __cpuinit rcu_barrier_cpu_hotplug(struct notifier_block *self,
 	return NOTIFY_OK;
 }
 
+static DEFINE_MUTEX(synchronize_rcu_bh_mutex);
+static long synchronize_rcu_bh_completed; /* Expedited-grace-period count. */
+
+#ifndef CONFIG_SMP
+
+static void __init synchronize_rcu_expedited_init(void)
+{
+}
+
+void synchronize_rcu_bh_expedited(void)
+{
+	mutex_lock(&synchronize_rcu_bh_mutex);
+	synchronize_rcu_bh_completed++;
+	mutex_unlock(&synchronize_rcu_bh_mutex);
+}
+
+#else /* #ifndef CONFIG_SMP */
+
+static DEFINE_PER_CPU(int, rcu_bh_need_qs);
+static cpumask_var_t rcu_bh_waiting_map;
+
+static void synchronize_rcu_bh_expedited_help(struct softirq_action *unused)
+{
+	if (__get_cpu_var(rcu_bh_need_qs)) {
+		smp_mb();
+		__get_cpu_var(rcu_bh_need_qs) = 0;
+		smp_mb();
+	}
+}
+
+static void rcu_bh_fast_qs(void *unused)
+{
+	raise_softirq(RCU_EXPEDITED_SOFTIRQ);
+}
+
+static void __init synchronize_rcu_expedited_init(void)
+{
+	open_softirq(RCU_EXPEDITED_SOFTIRQ, synchronize_rcu_bh_expedited_help);
+	alloc_bootmem_cpumask_var(&rcu_bh_waiting_map);
+}
+
+void synchronize_rcu_bh_expedited(void)
+{
+	int cpu;
+	int done;
+	int times = 0;
+
+	mutex_lock(&synchronize_rcu_bh_mutex);
+
+	/* Take snapshot of online CPUs, blocking CPU hotplug. */
+	preempt_disable();
+	cpumask_copy(rcu_bh_waiting_map, &cpu_online_map);
+	preempt_enable();
+
+	/* Mark each online CPU as needing a quiescent state. */
+	for_each_cpu(cpu, rcu_bh_waiting_map)
+		per_cpu(rcu_bh_need_qs, cpu) = 1;
+
+	/* Call for a quiescent state on each online CPU. */
+	preempt_disable();
+	cpumask_clear_cpu(smp_processor_id(), rcu_bh_waiting_map);
+	smp_call_function(rcu_bh_fast_qs, NULL, 1);
+	preempt_enable();
+
+	/*
+	 * Loop waiting for each CPU to either pass through a quiescent
+	 * state or to go offline.  We don't care which.
+	 */
+	for (;;) {
+		
+		/* Ignore CPUs that have gone offline, blocking CPU hotplug. */
+		preempt_disable();
+		cpumask_and(rcu_bh_waiting_map, rcu_bh_waiting_map,
+			    &cpu_online_map);
+		cpumask_clear_cpu(smp_processor_id(), rcu_bh_waiting_map);
+		preempt_enable();
+
+		/* Check if any CPUs still need a quiescent state. */
+		done = 1;
+		for_each_cpu(cpu, rcu_bh_waiting_map) {
+			if (per_cpu(rcu_bh_need_qs, cpu)) {
+				done = 0;
+				break;
+			}
+			cpumask_clear_cpu(cpu, rcu_bh_waiting_map);
+		}
+		if (done)
+			break;
+
+		/*
+		 * Wait a bit.  If we have already waited a fair
+		 * amount of time, sleep.
+		 */
+		if (++times < 10)
+			udelay(10 * times);
+		else
+			schedule_timeout_uninterruptible(1);
+	}
+
+	synchronize_rcu_bh_completed++;
+	mutex_unlock(&synchronize_rcu_bh_mutex);
+}
+

kernel/rcupdate.c static int __cpuinit rcu_barrier_cpu_hotplug(struct notifier_block *self, · line 332

Quoted 10 lines
kernel/rcupdate.c +3 -0
+#endif /* #else #ifndef CONFIG_SMP */
+
 void __init rcu_init(void)
 {
 	__rcu_init();
 	hotcpu_notifier(rcu_barrier_cpu_hotplug, 0);
+	synchronize_rcu_expedited_init();
 }
 
 void rcu_scheduler_starting(void)

Hi, Paul

I just typed codes in email, very like these two pathes:

[PATCH 1/2] sched: Introduce APIs for waiting multi events
http://lkml.org/lkml/2009/4/14/733

[PATCH 2/2] rcupdate: use struct ref_completion
http://lkml.org/lkml/2009/4/14/734

Lai.
--------------

#ifndef CONFIG_SMP

static void __init synchronize_rcu_expedited_init(void) {
}

void synchronize_rcu_bh_expedited(void)

{
	cond_resched();
}

#else /* #ifndef CONFIG_SMP */

static DEFINE_MUTEX(synchronize_rcu_bh_mutex); static DEFINE_PER_CPU(int, call_only_once); /* is it need ? */ static struct ref_completion rcu_bh_expedited_completion

static void synchronize_rcu_bh_expedited_help(struct softirq_action *unused)

{
	if (__get_cpu_var(call_only_once)) {
		smp_mb();
		ref_completion_put(&rcu_bh_expedited_completion);
		__get_cpu_var(call_only_once) = 0;
	}
}

static void rcu_bh_fast_qs(void *unused)

{
	__get_cpu_var(call_only_once) = 1;
	ref_completion_get(&rcu_bh_expedited_completion);
	raise_softirq(RCU_EXPEDITED_SOFTIRQ);
}

static void __init synchronize_rcu_expedited_init(void)

{
	open_softirq(RCU_EXPEDITED_SOFTIRQ, synchronize_rcu_bh_expedited_help);
}

void synchronize_rcu_bh_expedited(void)

{
	mutex_lock(&synchronize_rcu_bh_mutex);

	ref_completion_get_init(&rcu_bh_expedited_completion);

	smp_call_function(rcu_bh_fast_qs, NULL, 1);

	ref_completion_put_init(&rcu_bh_expedited_completion);
	ref_completion_wait(&rcu_bh_expedited_completion);

	mutex_unlock(&synchronize_rcu_bh_mutex);
}

#endif /* #else #ifndef CONFIG_SMP */

#5 lore raw
In reply to Paul E. McKenney
Quoted 11 lines · Paul E. McKenney

First cut of "big hammer" expedited RCU grace periods, but only for rcu_bh. This creates another softirq vector, so that entering this softirq vector will have forced an rcu_bh quiescent state (as noted by Dave Miller). Use smp_call_function() to invoke raise_softirq() on all CPUs in order to cause this to happen. Track the CPUs that have passed through a quiescent state (or gone offline) with a cpumask.

Does nothing to expedite callbacks already registered with call_rcu_bh(), but there is no need to.

Quoted 7 lines

Shortcomings:

o Untested, probably does not compile, not for inclusion.

o Does not handle rcu, only rcu_bh.

Thoughts?

I'm wondering, why not just do a two-liner, along the lines of:

	for_each_online_cpu(cpu)
		smp_send_reschedule(cpu);

That should trigger a quiescent state on all online cpus. It wont perturb the scheduler state (which is reschedule-IPI invariant). (And this is a big-hammer approach anyway so even if it did we wouldnt care.)

Am i missing something embarrasingly obvious perhaps?

Ingo

#9 lore raw
In reply to Paul E. McKenney
Quoted 55 lines · * Paul E. McKenney ([email protected]) wrote:

First cut of "big hammer" expedited RCU grace periods, but only for rcu_bh. This creates another softirq vector, so that entering this softirq vector will have forced an rcu_bh quiescent state (as noted by Dave Miller). Use smp_call_function() to invoke raise_softirq() on all CPUs in order to cause this to happen. Track the CPUs that have passed through a quiescent state (or gone offline) with a cpumask.

Does nothing to expedite callbacks already registered with call_rcu_bh(), but there is no need to.

Shortcomings:

o Untested, probably does not compile, not for inclusion.

o Does not handle rcu, only rcu_bh.

Thoughts?

---

 include/linux/interrupt.h |    1 
 include/linux/rcupdate.h  |    1 
 kernel/rcupdate.c         |  106 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 108 insertions(+)
include/linux/interrupt.h +1 -0
index 91bb76f..b7b58cc 100644
@@ -338,6 +338,7 @@ enum
 	TASKLET_SOFTIRQ,
 	SCHED_SOFTIRQ,
 	HRTIMER_SOFTIRQ,
+	RCU_EXPEDITED_SOFTIRQ,
 	RCU_SOFTIRQ,	/* Preferable RCU should always be the last softirq */
 
 	NR_SOFTIRQS
include/linux/rcupdate.h +1 -0
index 15fbb3c..d4af557 100644
@@ -264,6 +264,7 @@ extern void synchronize_rcu(void);
 extern void rcu_barrier(void);
 extern void rcu_barrier_bh(void);
 extern void rcu_barrier_sched(void);
+extern void synchronize_rcu_bh_expedited(void);
 
 /* Internal to kernel */
 extern void rcu_init(void);
kernel/rcupdate.c +0 -0
index a967c9f..bfa98dd 100644

kernel/rcupdate.c static int __cpuinit rcu_barrier_cpu_hotplug(struct notifier_block *self, · line 221

Quoted 5 lines
kernel/rcupdate.c +2 -0
@@ -217,10 +217,116 @@ static int __cpuinit rcu_barrier_cpu_hotplug(struct notifier_block *self,
 	return NOTIFY_OK;
 }
 
+static DEFINE_MUTEX(synchronize_rcu_bh_mutex);
+static long synchronize_rcu_bh_completed; /* Expedited-grace-period count. */

Given you access this variable through a mutex, you might want to consider using a u64 (unsigned long long) to make sure it counts a full 64-bits on 32-bits architectures. This would make overflows less likely to happen. Note that the reads should be done through a mutex then. Another alternative is to protect it using a seqlock. Note that the two previous "non-atomic" read solutions should never be used in NMI context. :-/

Quoted 12 lines
kernel/rcupdate.c +12 -0
+
+#ifndef CONFIG_SMP
+
+static void __init synchronize_rcu_expedited_init(void)
+{
+}
+
+void synchronize_rcu_bh_expedited(void)
+{
+	mutex_lock(&synchronize_rcu_bh_mutex);
+	synchronize_rcu_bh_completed++;
+	mutex_unlock(&synchronize_rcu_bh_mutex);

kernel/rcupdate.c static int __cpuinit rcu_barrier_cpu_hotplug(struct notifier_block *self, · line 243

Quoted 10 lines
kernel/rcupdate.c +10 -0
+}
+
+#else /* #ifndef CONFIG_SMP */
+
+static DEFINE_PER_CPU(int, rcu_bh_need_qs);
+static cpumask_var_t rcu_bh_waiting_map;
+
+static void synchronize_rcu_bh_expedited_help(struct softirq_action *unused)
+{
+	if (__get_cpu_var(rcu_bh_need_qs)) {

Is this test useful at all ? The value can only be 0 or 1, so if it is already 0, then we set it to 0 again. I doubt you care that much about cache-line bouncing ?

kernel/rcupdate.c static int __cpuinit rcu_barrier_cpu_hotplug(struct notifier_block *self, · line 246

Quoted 3 lines
kernel/rcupdate.c +3 -0
+		smp_mb();
+		__get_cpu_var(rcu_bh_need_qs) = 0;
+		smp_mb();

Is this second mb required ? We want to make sure no memory access coming from code executed before the flag write goes into the next qs period, this is fine (and explains the first mb()), but do we care about interleaving writes done after the flag write ? In the worse case, they will be put in the previous qs period, and that seems fine.

Quoted 14 lines
kernel/rcupdate.c +14 -0
+	}
+}
+
+static void rcu_bh_fast_qs(void *unused)
+{
+	raise_softirq(RCU_EXPEDITED_SOFTIRQ);
+}
+
+static void __init synchronize_rcu_expedited_init(void)
+{
+	open_softirq(RCU_EXPEDITED_SOFTIRQ, synchronize_rcu_bh_expedited_help);
+	alloc_bootmem_cpumask_var(&rcu_bh_waiting_map);
+}
+

kernel/rcupdate.c static int __cpuinit rcu_barrier_cpu_hotplug(struct notifier_block *self, · line 270

Quoted 10 lines
kernel/rcupdate.c +10 -0
+void synchronize_rcu_bh_expedited(void)
+{
+	int cpu;
+	int done;
+	int times = 0;
+
+	mutex_lock(&synchronize_rcu_bh_mutex);
+
+	/* Take snapshot of online CPUs, blocking CPU hotplug. */
+	preempt_disable();

Hrm, how about simply

get_online_cpus();

put_online_cpus();

just once at the beginning/end of this function to stop cpu hotplug ?

All these preempt_enable/disable seems a bit too much. But I see that you might not want to disabling cpu hotplug for too long, so you probably have a good reason to do it this way.

kernel/rcupdate.c static int __cpuinit rcu_barrier_cpu_hotplug(struct notifier_block *self, · line 280

Quoted 10 lines
kernel/rcupdate.c +10 -0
+	cpumask_copy(rcu_bh_waiting_map, &cpu_online_map);
+	preempt_enable();
+
+	/* Mark each online CPU as needing a quiescent state. */
+	for_each_cpu(cpu, rcu_bh_waiting_map)
+		per_cpu(rcu_bh_need_qs, cpu) = 1;
+
+	/* Call for a quiescent state on each online CPU. */
+	preempt_disable();
+	cpumask_clear_cpu(smp_processor_id(), rcu_bh_waiting_map);

Commenting that smp_call_function has a smp_mb(), which makes sure per_cpu(rcu_bh_need_qs, cpu) writes happened before calling the remote functions would not hurt.

Mathieu

Quoted 53 lines
kernel/rcupdate.c +45 -0
+	smp_call_function(rcu_bh_fast_qs, NULL, 1);
+	preempt_enable();
+
+	/*
+	 * Loop waiting for each CPU to either pass through a quiescent
+	 * state or to go offline.  We don't care which.
+	 */
+	for (;;) {
+		
+		/* Ignore CPUs that have gone offline, blocking CPU hotplug. */
+		preempt_disable();
+		cpumask_and(rcu_bh_waiting_map, rcu_bh_waiting_map,
+			    &cpu_online_map);
+		cpumask_clear_cpu(smp_processor_id(), rcu_bh_waiting_map);
+		preempt_enable();
+
+		/* Check if any CPUs still need a quiescent state. */
+		done = 1;
+		for_each_cpu(cpu, rcu_bh_waiting_map) {
+			if (per_cpu(rcu_bh_need_qs, cpu)) {
+				done = 0;
+				break;
+			}
+			cpumask_clear_cpu(cpu, rcu_bh_waiting_map);
+		}
+		if (done)
+			break;
+
+		/*
+		 * Wait a bit.  If we have already waited a fair
+		 * amount of time, sleep.
+		 */
+		if (++times < 10)
+			udelay(10 * times);
+		else
+			schedule_timeout_uninterruptible(1);
+	}
+
+	synchronize_rcu_bh_completed++;
 
+	mutex_unlock(&synchronize_rcu_bh_mutex);
+}
+
+#endif /* #else #ifndef CONFIG_SMP */
+
 void __init rcu_init(void)
 {
 	__rcu_init();
 	hotcpu_notifier(rcu_barrier_cpu_hotplug, 0);
+	synchronize_rcu_expedited_init();
 }
 

void rcu_scheduler_starting(void)

Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#2 lore raw
In reply to Lai Jiangshan
Quoted 1 line · Lai Jiangshan

Paul E. McKenney wrote:

[ . . . ]

Quoted 4 lines

Hi, Paul

I just typed codes in email, very like these two pathes:

Quoted 8 lines

[PATCH 1/2] sched: Introduce APIs for waiting multi events
http://lkml.org/lkml/2009/4/14/733

[PATCH 2/2] rcupdate: use struct ref_completion
http://lkml.org/lkml/2009/4/14/734

Lai.
--------------

Interesting approach! This would get a second use for your multi-events waiting code above. ;-)

Looks like the idea is to have the task doing the synchronize_rcu_bh_expedited() hold a reference across the process, and have each rcu_bh_fast_qs() also acquire a reference, which would be released in the softirq handler synchronize_rcu_bh_expedited_help().

One question -- does this approach correctly handle all the CPU hotplug scenarios? (I think that it might, but am not completely certain.)

Thanx, Paul

Quoted 54 lines

#ifndef CONFIG_SMP

static void __init synchronize_rcu_expedited_init(void) {
}

void synchronize_rcu_bh_expedited(void)

{
	cond_resched();
}

#else /* #ifndef CONFIG_SMP */

static DEFINE_MUTEX(synchronize_rcu_bh_mutex); static DEFINE_PER_CPU(int, call_only_once); /* is it need ? */ static struct ref_completion rcu_bh_expedited_completion

static void synchronize_rcu_bh_expedited_help(struct softirq_action *unused)

{
	if (__get_cpu_var(call_only_once)) {
		smp_mb();
		ref_completion_put(&rcu_bh_expedited_completion);
		__get_cpu_var(call_only_once) = 0;
	}
}

static void rcu_bh_fast_qs(void *unused)

{
	__get_cpu_var(call_only_once) = 1;
	ref_completion_get(&rcu_bh_expedited_completion);
	raise_softirq(RCU_EXPEDITED_SOFTIRQ);
}

static void __init synchronize_rcu_expedited_init(void)

{
	open_softirq(RCU_EXPEDITED_SOFTIRQ, synchronize_rcu_bh_expedited_help);
}

void synchronize_rcu_bh_expedited(void)

{
	mutex_lock(&synchronize_rcu_bh_mutex);

	ref_completion_get_init(&rcu_bh_expedited_completion);

	smp_call_function(rcu_bh_fast_qs, NULL, 1);

	ref_completion_put_init(&rcu_bh_expedited_completion);
	ref_completion_wait(&rcu_bh_expedited_completion);

	mutex_unlock(&synchronize_rcu_bh_mutex);
}

#endif /* #else #ifndef CONFIG_SMP */

#6 lore raw
In reply to Ingo Molnar
Quoted 27 lines · Ingo Molnar
Quoted 11 lines · Paul E. McKenney

First cut of "big hammer" expedited RCU grace periods, but only for rcu_bh. This creates another softirq vector, so that entering this softirq vector will have forced an rcu_bh quiescent state (as noted by Dave Miller). Use smp_call_function() to invoke raise_softirq() on all CPUs in order to cause this to happen. Track the CPUs that have passed through a quiescent state (or gone offline) with a cpumask.

Does nothing to expedite callbacks already registered with call_rcu_bh(), but there is no need to.

Quoted 7 lines

Shortcomings:

o Untested, probably does not compile, not for inclusion.

o Does not handle rcu, only rcu_bh.

Thoughts?

I'm wondering, why not just do a two-liner, along the lines of:

	for_each_online_cpu(cpu)
		smp_send_reschedule(cpu);
Quoted 6 lines

That should trigger a quiescent state on all online cpus. It wont perturb the scheduler state (which is reschedule-IPI invariant). (And this is a big-hammer approach anyway so even if it did we wouldnt care.)

Am i missing something embarrasingly obvious perhaps?

This two-liner would indeed trigger a quiescent state on all online CPUs.

However, it would not force RCU to notice these quiescent states quickly. This is because RCU's normal grace-period-detection path can be thought of as a state machine driven out of the per-CPU scheduling-clock interrupt handler. So RCU would still take another jiffy or two to close the grace period -- more if there was a partly-done grace period that needed to complete before a new one could start.

So both Lai's and my patch bypass RCU's normal state machine in order to not only force the quiescent states, but also to determine that they have in fact happened.

Hmmm... I need to ask Jeff Chua what HZ he was running with. Because if there was some read-side critical section soaking up 30 milliseconds, all that hammering will do is slow things down...

Thanx, Paul

#7 lore raw
Quoted 4 lines · Paul E. McKenney

Hmmm... I need to ask Jeff Chua what HZ he was running with. Because if there was some read-side critical section soaking up 30 milliseconds, all that hammering will do is slow things down...

The original bug report comes from simply bootup:

"I'm loading all the firewall rules during boot-up and this 6 secs
slowness is really not very nice to wait for."

IOW, the problematic case likely effectively has _nothing_ else going on. Sure, there might be some parallelism (the bootup scripts are getting better for that), but hopefully not 6 seconds worth, and not likely any complex critical sections.

Linus

#10 lore raw
In reply to Mathieu Desnoyers
Quoted 59 lines · Mathieu Desnoyers
Quoted 58 lines · * Paul E. McKenney ([email protected]) wrote:

First cut of "big hammer" expedited RCU grace periods, but only for rcu_bh. This creates another softirq vector, so that entering this softirq vector will have forced an rcu_bh quiescent state (as noted by Dave Miller). Use smp_call_function() to invoke raise_softirq() on all CPUs in order to cause this to happen. Track the CPUs that have passed through a quiescent state (or gone offline) with a cpumask.

Does nothing to expedite callbacks already registered with call_rcu_bh(), but there is no need to.

Shortcomings:

o Untested, probably does not compile, not for inclusion.

o Does not handle rcu, only rcu_bh.

Thoughts?

---

 include/linux/interrupt.h |    1 
 include/linux/rcupdate.h  |    1 
 kernel/rcupdate.c         |  106 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 108 insertions(+)
include/linux/interrupt.h +1 -0
index 91bb76f..b7b58cc 100644
@@ -338,6 +338,7 @@ enum
 	TASKLET_SOFTIRQ,
 	SCHED_SOFTIRQ,
 	HRTIMER_SOFTIRQ,
+	RCU_EXPEDITED_SOFTIRQ,
 	RCU_SOFTIRQ,	/* Preferable RCU should always be the last softirq */
 
 	NR_SOFTIRQS
include/linux/rcupdate.h +1 -0
index 15fbb3c..d4af557 100644
@@ -264,6 +264,7 @@ extern void synchronize_rcu(void);
 extern void rcu_barrier(void);
 extern void rcu_barrier_bh(void);
 extern void rcu_barrier_sched(void);
+extern void synchronize_rcu_bh_expedited(void);
 
 /* Internal to kernel */
 extern void rcu_init(void);
kernel/rcupdate.c +0 -0
index a967c9f..bfa98dd 100644
@@ -217,10 +217,116 @@ static int __cpuinit rcu_barrier_cpu_hotplug(struct notifier_block *self,
 	return NOTIFY_OK;
 }
 
Quoted 10 lines

kernel/rcupdate.c static int __cpuinit rcu_barrier_cpu_hotplug(struct notifier_block *self, · line 221

Quoted 2 lines
kernel/rcupdate.c +2 -0
+static DEFINE_MUTEX(synchronize_rcu_bh_mutex);
+static long synchronize_rcu_bh_completed; /* Expedited-grace-period count. */

Given you access this variable through a mutex, you might want to consider using a u64 (unsigned long long) to make sure it counts a full 64-bits on 32-bits architectures. This would make overflows less likely to happen. Note that the reads should be done through a mutex then. Another alternative is to protect it using a seqlock. Note that the two previous "non-atomic" read solutions should never be used in NMI context. :-/

Agreed, except that this is used only by rcutorture to show progress, and is OK to overflow.

Besides, if I change this, I have to change the corresponding pieces of the rest of RCU. ;-)

Quoted 18 lines
Quoted 18 lines
kernel/rcupdate.c +18 -0
+
+#ifndef CONFIG_SMP
+
+static void __init synchronize_rcu_expedited_init(void)
+{
+}
+
+void synchronize_rcu_bh_expedited(void)
+{
+	mutex_lock(&synchronize_rcu_bh_mutex);
+	synchronize_rcu_bh_completed++;
+	mutex_unlock(&synchronize_rcu_bh_mutex);
+}
+
+#else /* #ifndef CONFIG_SMP */
+
+static DEFINE_PER_CPU(int, rcu_bh_need_qs);
+static cpumask_var_t rcu_bh_waiting_map;
Quoted 8 lines

kernel/rcupdate.c static int __cpuinit rcu_barrier_cpu_hotplug(struct notifier_block *self, · line 243

Quoted 4 lines
kernel/rcupdate.c +4 -0
+
+static void synchronize_rcu_bh_expedited_help(struct softirq_action *unused)
+{
+	if (__get_cpu_var(rcu_bh_need_qs)) {

Is this test useful at all ? The value can only be 0 or 1, so if it is already 0, then we set it to 0 again. I doubt you care that much about cache-line bouncing ?

Nah, only about memory barriers. Probably not worth the check in this case.

Quoted 9 lines

kernel/rcupdate.c static int __cpuinit rcu_barrier_cpu_hotplug(struct notifier_block *self, · line 246

Quoted 3 lines
kernel/rcupdate.c +3 -0
+		smp_mb();
+		__get_cpu_var(rcu_bh_need_qs) = 0;
+		smp_mb();

Is this second mb required ? We want to make sure no memory access coming from code executed before the flag write goes into the next qs period, this is fine (and explains the first mb()), but do we care about interleaving writes done after the flag write ? In the worse case, they will be put in the previous qs period, and that seems fine.

Also that no RCU read-side critical section following gets reordered to precede the flip.

Quoted 29 lines
Quoted 14 lines
kernel/rcupdate.c +14 -0
+	}
+}
+
+static void rcu_bh_fast_qs(void *unused)
+{
+	raise_softirq(RCU_EXPEDITED_SOFTIRQ);
+}
+
+static void __init synchronize_rcu_expedited_init(void)
+{
+	open_softirq(RCU_EXPEDITED_SOFTIRQ, synchronize_rcu_bh_expedited_help);
+	alloc_bootmem_cpumask_var(&rcu_bh_waiting_map);
+}
+

kernel/rcupdate.c static int __cpuinit rcu_barrier_cpu_hotplug(struct notifier_block *self, · line 270

Quoted 10 lines
kernel/rcupdate.c +10 -0
+void synchronize_rcu_bh_expedited(void)
+{
+	int cpu;
+	int done;
+	int times = 0;
+
+	mutex_lock(&synchronize_rcu_bh_mutex);
+
+	/* Take snapshot of online CPUs, blocking CPU hotplug. */
+	preempt_disable();

Hrm, how about simply

get_online_cpus();

Quoted 7 lines

put_online_cpus();

just once at the beginning/end of this function to stop cpu hotplug ?

All these preempt_enable/disable seems a bit too much. But I see that you might not want to disabling cpu hotplug for too long, so you probably have a good reason to do it this way.

Your approach does have the virtue of simplicity. Lai's approach, if it correctly handles CPU hotplug, avoids even disabling preemption, though it does potentially do some serious cache thrashing for large numbers of CPUs.

Quoted 6 lines
Quoted 6 lines
kernel/rcupdate.c +6 -0
+	cpumask_copy(rcu_bh_waiting_map, &cpu_online_map);
+	preempt_enable();
+
+	/* Mark each online CPU as needing a quiescent state. */
+	for_each_cpu(cpu, rcu_bh_waiting_map)
+		per_cpu(rcu_bh_need_qs, cpu) = 1;
Quoted 8 lines

kernel/rcupdate.c static int __cpuinit rcu_barrier_cpu_hotplug(struct notifier_block *self, · line 280

Quoted 4 lines
kernel/rcupdate.c +4 -0
+
+	/* Call for a quiescent state on each online CPU. */
+	preempt_disable();
+	cpumask_clear_cpu(smp_processor_id(), rcu_bh_waiting_map);

Commenting that smp_call_function has a smp_mb(), which makes sure per_cpu(rcu_bh_need_qs, cpu) writes happened before calling the remote functions would not hurt.

Ah! I should have remembered that from last time, shouldn't I? :-)

Updated.

And thank you for looking this over!!!

Thanx, Paul

Quoted 59 lines

Mathieu

Quoted 53 lines
kernel/rcupdate.c +45 -0
+	smp_call_function(rcu_bh_fast_qs, NULL, 1);
+	preempt_enable();
+
+	/*
+	 * Loop waiting for each CPU to either pass through a quiescent
+	 * state or to go offline.  We don't care which.
+	 */
+	for (;;) {
+		
+		/* Ignore CPUs that have gone offline, blocking CPU hotplug. */
+		preempt_disable();
+		cpumask_and(rcu_bh_waiting_map, rcu_bh_waiting_map,
+			    &cpu_online_map);
+		cpumask_clear_cpu(smp_processor_id(), rcu_bh_waiting_map);
+		preempt_enable();
+
+		/* Check if any CPUs still need a quiescent state. */
+		done = 1;
+		for_each_cpu(cpu, rcu_bh_waiting_map) {
+			if (per_cpu(rcu_bh_need_qs, cpu)) {
+				done = 0;
+				break;
+			}
+			cpumask_clear_cpu(cpu, rcu_bh_waiting_map);
+		}
+		if (done)
+			break;
+
+		/*
+		 * Wait a bit.  If we have already waited a fair
+		 * amount of time, sleep.
+		 */
+		if (++times < 10)
+			udelay(10 * times);
+		else
+			schedule_timeout_uninterruptible(1);
+	}
+
+	synchronize_rcu_bh_completed++;
 
+	mutex_unlock(&synchronize_rcu_bh_mutex);
+}
+
+#endif /* #else #ifndef CONFIG_SMP */
+
 void __init rcu_init(void)
 {
 	__rcu_init();
 	hotcpu_notifier(rcu_barrier_cpu_hotplug, 0);
+	synchronize_rcu_expedited_init();
 }
 

void rcu_scheduler_starting(void)

Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#8 lore raw
In reply to Linus Torvalds
Quoted 10 lines · Linus Torvalds
Quoted 4 lines · Paul E. McKenney

Hmmm... I need to ask Jeff Chua what HZ he was running with. Because if there was some read-side critical section soaking up 30 milliseconds, all that hammering will do is slow things down...

The original bug report comes from simply bootup:

Quoted 7 lines

"I'm loading all the firewall rules during boot-up and this 6 secs
slowness is really not very nice to wait for."

IOW, the problematic case likely effectively has _nothing_ else going on. Sure, there might be some parallelism (the bootup scripts are getting better for that), but hopefully not 6 seconds worth, and not likely any complex critical sections.

Sounds good to me! ;-)

Thanx, Paul

#3 lore raw
In reply to Paul E. McKenney
Quoted 26 lines · Paul E. McKenney
Quoted 1 line · Lai Jiangshan

Paul E. McKenney wrote:

[ . . . ]

Quoted 4 lines

Hi, Paul

I just typed codes in email, very like these two pathes:

Quoted 8 lines

[PATCH 1/2] sched: Introduce APIs for waiting multi events
http://lkml.org/lkml/2009/4/14/733

[PATCH 2/2] rcupdate: use struct ref_completion
http://lkml.org/lkml/2009/4/14/734

Lai.
--------------

Interesting approach! This would get a second use for your multi-events waiting code above. ;-)

Looks like the idea is to have the task doing the synchronize_rcu_bh_expedited() hold a reference across the process, and have each rcu_bh_fast_qs() also acquire a reference, which would be released in the softirq handler synchronize_rcu_bh_expedited_help().

Quoted 4 lines

One question -- does this approach correctly handle all the CPU hotplug scenarios? (I think that it might, but am not completely certain.)

Thanx, Paul

Ah, raise_softirq(RCU_EXPEDITED_SOFTIRQ) can not ensure the softirq will be called when hotplug.

It needs get_online_cpus() and put_online_cpus().

Quoted 58 lines
Quoted 55 lines

#ifndef CONFIG_SMP

static void __init synchronize_rcu_expedited_init(void) {
}

void synchronize_rcu_bh_expedited(void)

{
	cond_resched();
}

#else /* #ifndef CONFIG_SMP */

static DEFINE_MUTEX(synchronize_rcu_bh_mutex); static DEFINE_PER_CPU(int, call_only_once); /* is it need ? */ static struct ref_completion rcu_bh_expedited_completion

static void synchronize_rcu_bh_expedited_help(struct softirq_action *unused)

{
	if (__get_cpu_var(call_only_once)) {
		smp_mb();
		ref_completion_put(&rcu_bh_expedited_completion);
		__get_cpu_var(call_only_once) = 0;
	}
}

static void rcu_bh_fast_qs(void *unused)

{
	__get_cpu_var(call_only_once) = 1;
	ref_completion_get(&rcu_bh_expedited_completion);
	raise_softirq(RCU_EXPEDITED_SOFTIRQ);
}

static void __init synchronize_rcu_expedited_init(void)

{
	open_softirq(RCU_EXPEDITED_SOFTIRQ, synchronize_rcu_bh_expedited_help);
}

void synchronize_rcu_bh_expedited(void)

{
	mutex_lock(&synchronize_rcu_bh_mutex);

	ref_completion_get_init(&rcu_bh_expedited_completion);

	smp_call_function(rcu_bh_fast_qs, NULL, 1);

	ref_completion_put_init(&rcu_bh_expedited_completion);
	ref_completion_wait(&rcu_bh_expedited_completion);

	mutex_unlock(&synchronize_rcu_bh_mutex);
}

#endif /* #else #ifndef CONFIG_SMP */

#4 lore raw
Quoted 30 lines · Lai Jiangshan
Quoted 29 lines · Paul E. McKenney
Quoted 1 line · Lai Jiangshan

Paul E. McKenney wrote:

[ . . . ]

Quoted 4 lines

Hi, Paul

I just typed codes in email, very like these two pathes:

Quoted 8 lines

[PATCH 1/2] sched: Introduce APIs for waiting multi events
http://lkml.org/lkml/2009/4/14/733

[PATCH 2/2] rcupdate: use struct ref_completion
http://lkml.org/lkml/2009/4/14/734

Lai.
--------------

Interesting approach! This would get a second use for your multi-events waiting code above. ;-)

Looks like the idea is to have the task doing the synchronize_rcu_bh_expedited() hold a reference across the process, and have each rcu_bh_fast_qs() also acquire a reference, which would be released in the softirq handler synchronize_rcu_bh_expedited_help().

One question -- does this approach correctly handle all the CPU hotplug scenarios? (I think that it might, but am not completely certain.)

Quoted 6 lines
Quoted 1 line

Thanx, Paul

Ah, raise_softirq(RCU_EXPEDITED_SOFTIRQ) can not ensure the softirq will be called when hotplug.

It needs get_online_cpus() and put_online_cpus().

OK, easy fix, then. ;-)

Thanx, Paul

Quoted 59 lines
Quoted 57 lines
Quoted 54 lines

#ifndef CONFIG_SMP

static void __init synchronize_rcu_expedited_init(void) {
}

void synchronize_rcu_bh_expedited(void)

{
	cond_resched();
}

#else /* #ifndef CONFIG_SMP */

static DEFINE_MUTEX(synchronize_rcu_bh_mutex); static DEFINE_PER_CPU(int, call_only_once); /* is it need ? */ static struct ref_completion rcu_bh_expedited_completion

static void synchronize_rcu_bh_expedited_help(struct softirq_action *unused)

{
	if (__get_cpu_var(call_only_once)) {
		smp_mb();
		ref_completion_put(&rcu_bh_expedited_completion);
		__get_cpu_var(call_only_once) = 0;
	}
}

static void rcu_bh_fast_qs(void *unused)

{
	__get_cpu_var(call_only_once) = 1;
	ref_completion_get(&rcu_bh_expedited_completion);
	raise_softirq(RCU_EXPEDITED_SOFTIRQ);
}

static void __init synchronize_rcu_expedited_init(void)

{
	open_softirq(RCU_EXPEDITED_SOFTIRQ, synchronize_rcu_bh_expedited_help);
}

void synchronize_rcu_bh_expedited(void)

{
	mutex_lock(&synchronize_rcu_bh_mutex);

	ref_completion_get_init(&rcu_bh_expedited_completion);

	smp_call_function(rcu_bh_fast_qs, NULL, 1);

	ref_completion_put_init(&rcu_bh_expedited_completion);
	ref_completion_wait(&rcu_bh_expedited_completion);

	mutex_unlock(&synchronize_rcu_bh_mutex);
}

#endif /* #else #ifndef CONFIG_SMP */