Skip to contentSkip to conversation

v7 expedited "big hammer" RCU grace periods

RFC PATCH In review Paul E. McKenney 3 participants 16 messages May 22, 2009 – May 29, 2009

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

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

Seventh cut of "big hammer" expedited RCU grace periods. This leverages the existing per-CPU migration kthreads, as suggested by Ingo. These are awakened in a loop, and waited for in a second loop. Not fully scalable, but removing the extra hop through smp_call_function reduces latency on systems with moderate numbers of CPUs. The synchronize_rcu_expedited() and and synchronize_bh_expedited() primitives invoke synchronize_sched_expedited(), except for CONFIG_PREEMPT_RCU, where they instead invoke synchronize_rcu() and synchronize_rcu_bh(), respectively. This will be fixed in the future, after preemptable RCU is folded into the rcutree implementation.

As before, this does nothing to expedite callbacks already registered with call_rcu() or call_rcu_bh(), but there is no need to.

Passes 10 hours of rcutorture testing in parallel with a script that randomly offlines and onlines CPUs. Grace periods take about 28 microseconds on an 8-CPU Power machine, which I believe is good enough from a performance viewpoint for the near future.

This is not yet for inclusion. This does seem to me to be a good-enough implementation, but more testing and review is required.

Shortcomings:

o Does not address preemptable RCU.

o Probably not helpful on systems with thousands of CPUs, but likely
quite helpful even on systems with a few hundreds of CPUs.

Changes since v6:

o Moved to using the migration threads, as suggested by Ingo.

Changes since v5:

o Fixed several embarrassing locking bugs, including those
noted by Ingo and Lai.

o Added a missing set of braces.

o Cut out the extra kthread, so that synchronize_sched_expedited()
directly calls smp_call_function() and waits for the quiescent states.

o Removed some debug code, but promoted one to production.

o Fix a compiler warning.

Changes since v4:

o Use per-CPU kthreads to force the quiescent states in parallel.

Changes since v3:

o Use a kthread that schedules itself on each CPU in turn to
force a grace period. The synchronize_rcu() primitive wakes up the kthread in order to avoid messing with affinity masks on user tasks.

o Tried a number of additional variations on the v3 approach, none
of which helped much.

Changes since v2:

o Use reschedule IPIs rather than a softirq.

Changes since v1:

o Added rcutorture support, and added exports required by
rcutorture.

o Added comment stating that smp_call_function() implies a
memory barrier, suggested by Mathieu.

o Added #include for delay.h.

---

 include/linux/rcuclassic.h |   15 +++
 include/linux/rcupdate.h   |   24 ++---
 include/linux/rcupreempt.h |   10 ++
 include/linux/rcutree.h    |   12 ++
 kernel/rcupdate.c          |   27 ++++++
 kernel/rcutorture.c        |  200 ++++++++++++++++++++++++---------------------
 kernel/sched.c             |   52 +++++++++++
 7 files changed, 233 insertions(+), 107 deletions(-)
include/linux/rcuclassic.h +14 -1
index bfd92e1..b4b4fe1 100644
@@ -158,14 +158,27 @@ extern struct lockdep_map rcu_lock_map;
 
 #define call_rcu_sched(head, func) call_rcu(head, func)
 
+static inline void synchronize_rcu_expedited(void)
+{
+	synchronize_sched_expedited();
+}
+
+static inline void synchronize_rcu_bh_expedited(void)
+{
+	synchronize_sched_expedited();
+}
+
 extern void __rcu_init(void);
-#define rcu_init_sched()	do { } while (0)
 extern void rcu_check_callbacks(int cpu, int user);
 extern void rcu_restart_cpu(int cpu);
 
 extern long rcu_batches_completed(void);
 extern long rcu_batches_completed_bh(void);
 
+static inline void rcu_init_sched(void)
+{
+}
+
 #define rcu_enter_nohz()	do { } while (0)
 #define rcu_exit_nohz()		do { } while (0)
 
include/linux/rcupdate.h +12 -12
index 15fbb3c..d67dfce 100644
@@ -51,7 +51,18 @@ struct rcu_head {
 	void (*func)(struct rcu_head *head);
 };
 
-/* Internal to kernel, but needed by rcupreempt.h. */
+/* Exported common interfaces */
+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_sched_expedited(void);
+extern int sched_expedited_torture_stats(char *page);
+
+/* Internal to kernel */
+extern void rcu_init(void);
+extern void rcu_scheduler_starting(void);
+extern int rcu_needs_cpu(int cpu);
 extern int rcu_scheduler_active;
 
 #if defined(CONFIG_CLASSIC_RCU)
@@ -259,15 +270,4 @@ extern void call_rcu(struct rcu_head *head,
 extern void call_rcu_bh(struct rcu_head *head,
 			void (*func)(struct rcu_head *head));
 
-/* Exported common interfaces */
-extern void synchronize_rcu(void);
-extern void rcu_barrier(void);
-extern void rcu_barrier_bh(void);
-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 +10 -0
index fce5227..78117ed 100644
@@ -74,6 +74,16 @@ extern int rcu_needs_cpu(int cpu);
 
 extern void __synchronize_sched(void);
 
+static inline void synchronize_rcu_expedited(void)
+{
+	synchronize_rcu();  /* Placeholder for new rcupreempt implementation. */
+}
+
+static inline void synchronize_rcu_bh_expedited(void)
+{
+	synchronize_rcu();  /* Placeholder for new rcupreempt implementation. */
+}
+
 extern void __rcu_init(void);
 extern void rcu_init_sched(void);
 extern void rcu_check_callbacks(int cpu, int user);
include/linux/rcutree.h +11 -1
index 58b2aa5..41c23cb 100644
@@ -279,8 +279,14 @@ static inline void __rcu_read_unlock_bh(void)
 
 #define call_rcu_sched(head, func) call_rcu(head, func)
 
-static inline void rcu_init_sched(void)
+static inline void synchronize_rcu_expedited(void)
+{
+	synchronize_sched_expedited();
+}
+
+static inline void synchronize_rcu_bh_expedited(void)
 {
+	synchronize_sched_expedited();
 }
 
 extern void __rcu_init(void);
@@ -290,6 +296,10 @@ extern void rcu_restart_cpu(int cpu);
 extern long rcu_batches_completed(void);
 extern long rcu_batches_completed_bh(void);
 
+static inline void rcu_init_sched(void)
+{
+}
+
 #ifdef CONFIG_NO_HZ
 void rcu_enter_nohz(void);
 void rcu_exit_nohz(void);
kernel/rcupdate.c +27 -0
index a967c9f..454995f 100644
@@ -45,6 +45,8 @@
 #include <linux/mutex.h>
 #include <linux/module.h>
 #include <linux/kernel_stat.h>
+#include <linux/delay.h>
+#include <linux/kthread.h>
 
 enum rcu_barrier {
 	RCU_BARRIER_STD,
@@ -98,6 +100,30 @@ void synchronize_rcu(void)
 }
 EXPORT_SYMBOL_GPL(synchronize_rcu);
 
+/**
+ * synchronize_rcu_bh - wait until an rcu_bh grace period has elapsed.
+ *
+ * Control will return to the caller some time after a full rcu_bh grace
+ * period has elapsed, in other words after all currently executing rcu_bh
+ * read-side critical sections have completed.  RCU read-side critical
+ * sections are delimited by rcu_read_lock_bh() and rcu_read_unlock_bh(),
+ * and may be nested.
+ */
+void synchronize_rcu_bh(void)
+{
+	struct rcu_synchronize rcu;
+
+	if (rcu_blocking_is_gp())
+		return;
+
+	init_completion(&rcu.completion);
+	/* Will wake me after RCU finished. */
+	call_rcu_bh(&rcu.head, wakeme_after_rcu);
+	/* Wait for it. */
+	wait_for_completion(&rcu.completion);
+}
+EXPORT_SYMBOL_GPL(synchronize_rcu_bh);
+
 static void rcu_barrier_callback(struct rcu_head *notused)
 {
 	if (atomic_dec_and_test(&rcu_barrier_cpu_count))
@@ -129,6 +155,7 @@ static void rcu_barrier_func(void *type)
 static inline void wait_migrated_callbacks(void)
 {
 	wait_event(rcu_migrate_wq, !atomic_read(&rcu_migrate_type_count));
+	smp_mb(); /* In case we didn't sleep. */
 }
 
 /*
kernel/rcutorture.c +108 -92

292 lines not on this page · raw message

kernel/sched.c +51 -1

61 lines not on this page · raw message

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

Seventh cut of "big hammer" expedited RCU grace periods. This leverages the existing per-CPU migration kthreads, as suggested by Ingo. These are awakened in a loop, and waited for in a second loop. Not fully scalable, but removing the extra hop through smp_call_function reduces latency on systems with moderate numbers of CPUs. The synchronize_rcu_expedited() and and synchronize_bh_expedited() primitives invoke synchronize_sched_expedited(), except for CONFIG_PREEMPT_RCU, where they instead invoke synchronize_rcu() and synchronize_rcu_bh(), respectively. This will be fixed in the future, after preemptable RCU is folded into the rcutree implementation.

I'm strongly need this guarantee:

preempt_disable() guarantees/implies rcu_read_lock().

And
local_irq_diable() guarantees/implies rcu_read_lock(). rcu_read_lock_bh() guarantees/implies rcu_read_lock().

It will simplifies codes.

And
A lot's of current kernel code does not use rcu_read_lock() when it has preempt_disable()-ed/local_irq_diable()-ed or when it is in irq/softirq.

Without these guarantees, these code is broken.

Quoted 32 lines
kernel/sched.c +30 -0
+
+static DEFINE_PER_CPU(struct migration_req, rcu_migration_req);
+static DEFINE_MUTEX(rcu_sched_expedited_mutex);
+
+/*
+ * Wait for an rcu-sched grace period to elapse, but use "big hammer"
+ * approach to force grace period to end quickly.  This consumes
+ * significant time on all CPUs, and is thus not recommended for
+ * any sort of common-case code.
+ */
+void synchronize_sched_expedited(void)
+{
+	int cpu;
+	unsigned long flags;
+	struct rq *rq;
+	struct migration_req *req;
+
+	mutex_lock(&rcu_sched_expedited_mutex);
+	get_online_cpus();
+	for_each_online_cpu(cpu) {
+		rq = cpu_rq(cpu);
+		req = &per_cpu(rcu_migration_req, cpu);
+		init_completion(&req->done);
+		req->task = NULL;
+		req->dest_cpu = -1;
+		spin_lock_irqsave(&rq->lock, flags);
+		list_add(&req->list, &rq->migration_queue);
+		spin_unlock_irqrestore(&rq->lock, flags);
+		wake_up_process(rq->migration_thread);
+	}

kernel/sched.c struct cgroup_subsys cpuacct_subsys = { · line 10291

Quoted 10 lines
kernel/sched.c +10 -0
+	for_each_online_cpu(cpu) {
+		req = &per_cpu(rcu_migration_req, cpu);
+		wait_for_completion(&req->done);
+	}
+	put_online_cpus();
+	mutex_unlock(&rcu_sched_expedited_mutex);
+}
+EXPORT_SYMBOL_GPL(synchronize_sched_expedited);
+
+#endif /* #else #ifndef CONFIG_SMP */

Very nice implement!

Only one opinion:
get_online_cpus() is a large lock, a lot's of lock in kernel is required after cpu_hotplug.lock.

_cpu_down()
cpu_hotplug_begin()
mutex_lock(&cpu_hotplug.lock)
__raw_notifier_call_chain(CPU_DOWN_PREPARE)
Lock a-kernel-lock.

It means when we have held a-kernel-lock, we can not call synchronize_sched_expedited(). get_online_cpus() narrows synchronize_sched_expedited()'s usages.

I think we can reuse req->dest_cpu and remove get_online_cpus(). (and use preempt_disable() and for_each_possible_cpu())

req->dest_cpu = -2 means @req is not queued
req->dest_cpu = -1 means @req is queued

a little like this code:

	mutex_lock(&rcu_sched_expedited_mutex);
	for_each_possible_cpu(cpu) {
		preempt_disable()
		if (cpu is not online)
			just set req->dest_cpu to -2;
		else
			init and queue req, and wake_up_process().
		preempt_enable()
	}
	for_each_possible_cpu(cpu) {
		if (req is queued)
			wait_for_completion().
	}
	mutex_unlock(&rcu_sched_expedited_mutex);

The coupling of synchronize_sched_expedited() and migration_req is largely increased:

1) The offline cpu's per_cpu(rcu_migration_req, cpu) is handled. See migration_call::CPU_DEAD

2) migration_call() is the highest priority of cpu notifiers, So even any other cpu notifier calls synchronize_sched_expedited(), It'll not cause DEADLOCK.

Lai.

#2 lore raw
Quoted 15 lines · Lai Jiangshan
Quoted 11 lines · Paul E. McKenney

Seventh cut of "big hammer" expedited RCU grace periods. This leverages the existing per-CPU migration kthreads, as suggested by Ingo. These are awakened in a loop, and waited for in a second loop. Not fully scalable, but removing the extra hop through smp_call_function reduces latency on systems with moderate numbers of CPUs. The synchronize_rcu_expedited() and and synchronize_bh_expedited() primitives invoke synchronize_sched_expedited(), except for CONFIG_PREEMPT_RCU, where they instead invoke synchronize_rcu() and synchronize_rcu_bh(), respectively. This will be fixed in the future, after preemptable RCU is folded into the rcutree implementation.

I'm strongly need this guarantee:

Quoted 8 lines

preempt_disable() guarantees/implies rcu_read_lock().

And
local_irq_diable() guarantees/implies rcu_read_lock(). rcu_read_lock_bh() guarantees/implies rcu_read_lock().

It will simplifies codes.

Hmmm... I did produce a patch that modified preemptable RCU in this way quite some time back, but at that time the problem was solved in a different way. The approach was either to add rcu_read_lock()/rcu_read_unlock() pairs as needed, or to switch to call_rcu_sched() or synchronize_sched() for the update side.

But please note that this approach would not permit the current implementation of synchronize_sched_expedited() to be used in the preemptable-RCU case, because synchronize_sched_expedited() would not wait for RCU read-side critical sections that had been preempted. And the ability to preempt RCU read-side critical sections is absolutely required for CONFIG_PREEMPT_RT versions of the Linux kernel.

Quoted 6 lines

And
A lot's of current kernel code does not use rcu_read_lock() when it has preempt_disable()-ed/local_irq_diable()-ed or when it is in irq/softirq.

Without these guarantees, these code is broken.

One way or another, such code does need to be fixed. Either by reintroducing the old patch, or by fixing the code itself.

Quoted 36 lines
Quoted 36 lines
kernel/sched.c +36 -0
+
+static DEFINE_PER_CPU(struct migration_req, rcu_migration_req);
+static DEFINE_MUTEX(rcu_sched_expedited_mutex);
+
+/*
+ * Wait for an rcu-sched grace period to elapse, but use "big hammer"
+ * approach to force grace period to end quickly.  This consumes
+ * significant time on all CPUs, and is thus not recommended for
+ * any sort of common-case code.
+ */
+void synchronize_sched_expedited(void)
+{
+	int cpu;
+	unsigned long flags;
+	struct rq *rq;
+	struct migration_req *req;
+
+	mutex_lock(&rcu_sched_expedited_mutex);
+	get_online_cpus();
+	for_each_online_cpu(cpu) {
+		rq = cpu_rq(cpu);
+		req = &per_cpu(rcu_migration_req, cpu);
+		init_completion(&req->done);
+		req->task = NULL;
+		req->dest_cpu = -1;
+		spin_lock_irqsave(&rq->lock, flags);
+		list_add(&req->list, &rq->migration_queue);
+		spin_unlock_irqrestore(&rq->lock, flags);
+		wake_up_process(rq->migration_thread);
+	}
+	for_each_online_cpu(cpu) {
+		req = &per_cpu(rcu_migration_req, cpu);
+		wait_for_completion(&req->done);
+	}
+	put_online_cpus();
+	mutex_unlock(&rcu_sched_expedited_mutex);
Quoted 8 lines

kernel/sched.c struct cgroup_subsys cpuacct_subsys = { · line 10291

Quoted 6 lines
kernel/sched.c +4 -0
+}
+EXPORT_SYMBOL_GPL(synchronize_sched_expedited);
+
+#endif /* #else #ifndef CONFIG_SMP */

Very nice implement!

Glad you like it!!! The idea is Ingo's.

Gah!!! I need to have included a Suggested-by on v7 of the patch!!!

Quoted 22 lines

Only one opinion:
get_online_cpus() is a large lock, a lot's of lock in kernel is required after cpu_hotplug.lock.

_cpu_down()
cpu_hotplug_begin()
mutex_lock(&cpu_hotplug.lock)
__raw_notifier_call_chain(CPU_DOWN_PREPARE)
Lock a-kernel-lock.

It means when we have held a-kernel-lock, we can not call synchronize_sched_expedited(). get_online_cpus() narrows synchronize_sched_expedited()'s usages.

I think we can reuse req->dest_cpu and remove get_online_cpus(). (and use preempt_disable() and for_each_possible_cpu())

req->dest_cpu = -2 means @req is not queued
req->dest_cpu = -1 means @req is queued

a little like this code:

Quoted 14 lines
	mutex_lock(&rcu_sched_expedited_mutex);
	for_each_possible_cpu(cpu) {
		preempt_disable()
		if (cpu is not online)
			just set req->dest_cpu to -2;
		else
			init and queue req, and wake_up_process().
		preempt_enable()
	}
	for_each_possible_cpu(cpu) {
		if (req is queued)
			wait_for_completion().
	}
	mutex_unlock(&rcu_sched_expedited_mutex);

Good point -- I should at the very least add a comment to synchronize_sched_expedited() stating that it cannot be called holding any lock that is acquired in a CPU hotplug notifier. If this restriction causes any problems, then your approach seems like a promising fix.

Quoted 5 lines

The coupling of synchronize_sched_expedited() and migration_req is largely increased:

1) The offline cpu's per_cpu(rcu_migration_req, cpu) is handled. See migration_call::CPU_DEAD

Good. ;-)

Quoted 3 lines

2) migration_call() is the highest priority of cpu notifiers, So even any other cpu notifier calls synchronize_sched_expedited(), It'll not cause DEADLOCK.

You mean if using your preempt_disable() approach, right? Unless I am missing something, the current get_online_cpus() approach would deadlock in this case.

Thanx, Paul

Reviewed-by
#3 lore raw
Quoted 5 lines · Paul E. McKenney

Good point -- I should at the very least add a comment to synchronize_sched_expedited() stating that it cannot be called holding any lock that is acquired in a CPU hotplug notifier. If this restriction causes any problems, then your approach seems like a promising fix.

Quoted 9 lines
Quoted 6 lines

The coupling of synchronize_sched_expedited() and migration_req is largely increased:

1) The offline cpu's per_cpu(rcu_migration_req, cpu) is handled. See migration_call::CPU_DEAD

Good. ;-)

Quoted 8 lines
Quoted 3 lines

2) migration_call() is the highest priority of cpu notifiers, So even any other cpu notifier calls synchronize_sched_expedited(), It'll not cause DEADLOCK.

You mean if using your preempt_disable() approach, right? Unless I am missing something, the current get_online_cpus() approach would deadlock in this case.

Yes, I mean if using my preempt_disable() approach. The current get_online_cpus() approach would NOT deadlock in this case also, we can require get_online_cpus() in cpu notifiers.

Quoted 8 lines
include/linux/rcupreempt.h +0 -0
index fce5227..78117ed 100644
@@ -74,6 +74,16 @@ extern int rcu_needs_cpu(int cpu);
 
 extern void __synchronize_sched(void);
 

include/linux/rcupreempt.h extern int rcu_needs_cpu(int cpu); · line 86

Quoted 10 lines
include/linux/rcupreempt.h +10 -0
+static inline void synchronize_rcu_expedited(void)
+{
+	synchronize_rcu();  /* Placeholder for new rcupreempt implementation. */
+}
+
+static inline void synchronize_rcu_bh_expedited(void)
+{
+	synchronize_rcu();  /* Placeholder for new rcupreempt implementation. */
+}
+

Why not synchronize_rcu_bh() ?

In mainline, rcu_read_lock_bh() is not preemptable, So I think synchronize_sched_expedited() is better.

Anyway, synchronize_rcu() is OK for me, because it is "Placeholder for new rcupreempt implementation".

Lai

#4 lore raw
Quoted 8 lines · Lai Jiangshan
Quoted 5 lines · Paul E. McKenney

Good point -- I should at the very least add a comment to synchronize_sched_expedited() stating that it cannot be called holding any lock that is acquired in a CPU hotplug notifier. If this restriction causes any problems, then your approach seems like a promising fix.

Thank you very much for your review and comments!!!

Quoted 12 lines
Quoted 12 lines
Quoted 5 lines

The coupling of synchronize_sched_expedited() and migration_req is largely increased:

1) The offline cpu's per_cpu(rcu_migration_req, cpu) is handled. See migration_call::CPU_DEAD

Good. ;-)

Quoted 3 lines

2) migration_call() is the highest priority of cpu notifiers, So even any other cpu notifier calls synchronize_sched_expedited(), It'll not cause DEADLOCK.

Quoted 7 lines
Quoted 3 lines

You mean if using your preempt_disable() approach, right? Unless I am missing something, the current get_online_cpus() approach would deadlock in this case.

Yes, I mean if using my preempt_disable() approach. The current get_online_cpus() approach would NOT deadlock in this case also, we can require get_online_cpus() in cpu notifiers.

I have added the comment for the time being, but should people need to use this in CPU-hotplug notifiers, then again your preempt_disable() approach looks to be a promising fix.

Quoted 8 lines
Quoted 8 lines
include/linux/rcupreempt.h +0 -0
index fce5227..78117ed 100644
@@ -74,6 +74,16 @@ extern int rcu_needs_cpu(int cpu);
 
 extern void __synchronize_sched(void);
 
Quoted 12 lines

include/linux/rcupreempt.h extern int rcu_needs_cpu(int cpu); · line 86

Quoted 10 lines
include/linux/rcupreempt.h +10 -0
+static inline void synchronize_rcu_expedited(void)
+{
+	synchronize_rcu();  /* Placeholder for new rcupreempt implementation. */
+}
+
+static inline void synchronize_rcu_bh_expedited(void)
+{
+	synchronize_rcu();  /* Placeholder for new rcupreempt implementation. */
+}
+

Why not synchronize_rcu_bh() ?

Ummm... Because I did a typo. Fixed.

Quoted 5 lines

In mainline, rcu_read_lock_bh() is not preemptable, So I think synchronize_sched_expedited() is better.

Anyway, synchronize_rcu() is OK for me, because it is "Placeholder for new rcupreempt implementation".

And I am worried that preemptable RCU's rcu_bh read sides might someday become preemptable. Seems a bit unlikely at this point, but why tempt fate?

Thanx, Paul

#5 lore raw
Quoted 28 lines · Paul E. McKenney
Quoted 8 lines · Lai Jiangshan
Quoted 5 lines · Paul E. McKenney

Good point -- I should at the very least add a comment to synchronize_sched_expedited() stating that it cannot be called holding any lock that is acquired in a CPU hotplug notifier. If this restriction causes any problems, then your approach seems like a promising fix.

Thank you very much for your review and comments!!!

Quoted 16 lines
Quoted 15 lines
Quoted 5 lines

The coupling of synchronize_sched_expedited() and migration_req is largely increased:

1) The offline cpu's per_cpu(rcu_migration_req, cpu) is handled. See migration_call::CPU_DEAD

Good. ;-)

Quoted 3 lines

2) migration_call() is the highest priority of cpu notifiers, So even any other cpu notifier calls synchronize_sched_expedited(), It'll not cause DEADLOCK.

You mean if using your preempt_disable() approach, right? Unless I am missing something, the current get_online_cpus() approach would deadlock in this case.

Quoted 7 lines
Quoted 3 lines

Yes, I mean if using my preempt_disable() approach. The current get_online_cpus() approach would NOT deadlock in this case also, we can require get_online_cpus() in cpu notifiers.

I have added the comment for the time being, but should people need to use this in CPU-hotplug notifiers, then again your preempt_disable() approach looks to be a promising fix.

I looked more closely at your preempt_disable() suggestion, which you presented earlier as follows:

Quoted 8 lines

I think we can reuse req->dest_cpu and remove get_online_cpus(). (and use preempt_disable() and for_each_possible_cpu())

req->dest_cpu = -2 means @req is not queued
req->dest_cpu = -1 means @req is queued

a little like this code:

Quoted 14 lines
	mutex_lock(&rcu_sched_expedited_mutex);
	for_each_possible_cpu(cpu) {
		preempt_disable()
		if (cpu is not online)
			just set req->dest_cpu to -2;
		else
			init and queue req, and wake_up_process().
		preempt_enable()
	}
	for_each_possible_cpu(cpu) {
		if (req is queued)
			wait_for_completion().
	}
	mutex_unlock(&rcu_sched_expedited_mutex);

I am concerned about the following sequence of events:

o synchronize_sched_expedited() disables preemption, thus blocking
offlining operations.

o CPU 1 starts offlining CPU 0. It acquires the CPU-hotplug lock,
and proceeds, and is now waiting for preemption to be enabled.

o synchronize_sched_expedited() disables preemption, sees
that CPU 0 is online, so initializes and queues a request, does a wake-up-process(), and finally does a preempt_enable().

o CPU 0 is currently running a high-priority real-time process,
so the wakeup does not immediately happen.

o The offlining process completes, including the kthread_stop()
to the migration task.

o The migration task wakes up, sees kthread_should_stop(),
and so exits without checking its queue.

o synchronize_sched_expedited() waits forever for CPU 0 to respond.

I suppose that one way to handle this would be to check for the CPU going offline before doing the wait_for_completion(), but I am concerned about races affecting this check as well.

Or is there something in the CPU-offline process that makes the above sequence of events impossible?

Thanx, Paul

#6 lore raw
Quoted 84 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 28 lines · Paul E. McKenney
Quoted 8 lines · Lai Jiangshan
Quoted 5 lines · Paul E. McKenney

Good point -- I should at the very least add a comment to synchronize_sched_expedited() stating that it cannot be called holding any lock that is acquired in a CPU hotplug notifier. If this restriction causes any problems, then your approach seems like a promising fix.

Thank you very much for your review and comments!!!

Quoted 16 lines
Quoted 15 lines
Quoted 5 lines

The coupling of synchronize_sched_expedited() and migration_req is largely increased:

1) The offline cpu's per_cpu(rcu_migration_req, cpu) is handled. See migration_call::CPU_DEAD

Good. ;-)

Quoted 3 lines

2) migration_call() is the highest priority of cpu notifiers, So even any other cpu notifier calls synchronize_sched_expedited(), It'll not cause DEADLOCK.

You mean if using your preempt_disable() approach, right? Unless I am missing something, the current get_online_cpus() approach would deadlock in this case.

Quoted 7 lines
Quoted 3 lines

Yes, I mean if using my preempt_disable() approach. The current get_online_cpus() approach would NOT deadlock in this case also, we can require get_online_cpus() in cpu notifiers.

I have added the comment for the time being, but should people need to use this in CPU-hotplug notifiers, then again your preempt_disable() approach looks to be a promising fix.

I looked more closely at your preempt_disable() suggestion, which you presented earlier as follows:

Quoted 8 lines

I think we can reuse req->dest_cpu and remove get_online_cpus(). (and use preempt_disable() and for_each_possible_cpu())

req->dest_cpu = -2 means @req is not queued
req->dest_cpu = -1 means @req is queued

a little like this code:

Quoted 14 lines
	mutex_lock(&rcu_sched_expedited_mutex);
	for_each_possible_cpu(cpu) {
		preempt_disable()
		if (cpu is not online)
			just set req->dest_cpu to -2;
		else
			init and queue req, and wake_up_process().
		preempt_enable()
	}
	for_each_possible_cpu(cpu) {
		if (req is queued)
			wait_for_completion().
	}
	mutex_unlock(&rcu_sched_expedited_mutex);

I am concerned about the following sequence of events:

o synchronize_sched_expedited() disables preemption, thus blocking
offlining operations.

o CPU 1 starts offlining CPU 0. It acquires the CPU-hotplug lock,
and proceeds, and is now waiting for preemption to be enabled.

o synchronize_sched_expedited() disables preemption, sees
that CPU 0 is online, so initializes and queues a request, does a wake-up-process(), and finally does a preempt_enable().

o CPU 0 is currently running a high-priority real-time process,
so the wakeup does not immediately happen.

o The offlining process completes, including the kthread_stop()
to the migration task.

o The migration task wakes up, sees kthread_should_stop(),
and so exits without checking its queue.

Quoted 9 lines

o synchronize_sched_expedited() waits forever for CPU 0 to respond.

I suppose that one way to handle this would be to check for the CPU going offline before doing the wait_for_completion(), but I am concerned about races affecting this check as well.

Or is there something in the CPU-offline process that makes the above sequence of events impossible?

I think you are right, there is a problem there. The simple fact that this needs to disable preemption to protect against cpu hotplug seems a bit strange. If I may propose an alternate solution, which assumes that threads pinned to a CPU are migrated to a different CPU when a CPU goes offline (and will therefore execute anyway), and that a CPU brought online after the first iteration on online cpus was already quiescent (hopefully my assumptions are right). Preemption is left enabled during all the critical section.

It looks a lot like Lai's approach, except that I use a cpumask (I thought it looked cleaner and typically involves less operations than looping on each possible cpu). I also don't disable preemption and assume that cpu hotplug can happen at any point during this critical section.

Something along the lines of :

static DECLARE_BITMAP(cpu_wait_expedited_bits, CONFIG_NR_CPUS); const struct cpumask *const cpu_wait_expedited_mask =

			to_cpumask(cpu_wait_expedited_bits);

	mutex_lock(&rcu_sched_expedited_mutex);
	cpumask_clear(cpu_wait_expedited_mask);
	for_each_online_cpu(cpu) {
		init and queue cpu req, and wake_up_process().
		cpumask_set_cpu(cpu, cpu_wait_expedited_mask);
	}
	for_each_cpu_mask(cpu, cpu_wait_expedited_mask) {
		wait_for_completion(cpu req);
	}
	mutex_unlock(&rcu_sched_expedited_mutex);

There is one concern with this approach : if a CPU is hotunplugged and hotplugged during the critical section, I think the scheduler would migrate the thread to a different CPU (upon hotunplug) and let the thread run on this other CPU. If the target CPU is hotplugged again, this would mean the thread would have run on a different CPU than the target. I think we can argue that a CPU going offline and online again will meet quiescent state requirements, so this should not be a problem.

Mathieu

Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#7 lore raw
Quoted 127 lines · Mathieu Desnoyers
Quoted 84 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 28 lines · Paul E. McKenney
Quoted 8 lines · Lai Jiangshan
Quoted 5 lines · Paul E. McKenney

Good point -- I should at the very least add a comment to synchronize_sched_expedited() stating that it cannot be called holding any lock that is acquired in a CPU hotplug notifier. If this restriction causes any problems, then your approach seems like a promising fix.

Thank you very much for your review and comments!!!

Quoted 16 lines
Quoted 15 lines
Quoted 5 lines

The coupling of synchronize_sched_expedited() and migration_req is largely increased:

1) The offline cpu's per_cpu(rcu_migration_req, cpu) is handled. See migration_call::CPU_DEAD

Good. ;-)

Quoted 3 lines

2) migration_call() is the highest priority of cpu notifiers, So even any other cpu notifier calls synchronize_sched_expedited(), It'll not cause DEADLOCK.

You mean if using your preempt_disable() approach, right? Unless I am missing something, the current get_online_cpus() approach would deadlock in this case.

Quoted 7 lines
Quoted 3 lines

Yes, I mean if using my preempt_disable() approach. The current get_online_cpus() approach would NOT deadlock in this case also, we can require get_online_cpus() in cpu notifiers.

I have added the comment for the time being, but should people need to use this in CPU-hotplug notifiers, then again your preempt_disable() approach looks to be a promising fix.

I looked more closely at your preempt_disable() suggestion, which you presented earlier as follows:

Quoted 8 lines

I think we can reuse req->dest_cpu and remove get_online_cpus(). (and use preempt_disable() and for_each_possible_cpu())

req->dest_cpu = -2 means @req is not queued
req->dest_cpu = -1 means @req is queued

a little like this code:

Quoted 14 lines
	mutex_lock(&rcu_sched_expedited_mutex);
	for_each_possible_cpu(cpu) {
		preempt_disable()
		if (cpu is not online)
			just set req->dest_cpu to -2;
		else
			init and queue req, and wake_up_process().
		preempt_enable()
	}
	for_each_possible_cpu(cpu) {
		if (req is queued)
			wait_for_completion().
	}
	mutex_unlock(&rcu_sched_expedited_mutex);

I am concerned about the following sequence of events:

o synchronize_sched_expedited() disables preemption, thus blocking
offlining operations.

o CPU 1 starts offlining CPU 0. It acquires the CPU-hotplug lock,
and proceeds, and is now waiting for preemption to be enabled.

o synchronize_sched_expedited() disables preemption, sees
that CPU 0 is online, so initializes and queues a request, does a wake-up-process(), and finally does a preempt_enable().

o CPU 0 is currently running a high-priority real-time process,
so the wakeup does not immediately happen.

o The offlining process completes, including the kthread_stop()
to the migration task.

o The migration task wakes up, sees kthread_should_stop(),
and so exits without checking its queue.

Quoted 9 lines

o synchronize_sched_expedited() waits forever for CPU 0 to respond.

I suppose that one way to handle this would be to check for the CPU going offline before doing the wait_for_completion(), but I am concerned about races affecting this check as well.

Or is there something in the CPU-offline process that makes the above sequence of events impossible?

I think you are right, there is a problem there. The simple fact that this needs to disable preemption to protect against cpu hotplug seems a bit strange. If I may propose an alternate solution, which assumes that threads pinned to a CPU are migrated to a different CPU when a CPU goes offline (and will therefore execute anyway), and that a CPU brought online after the first iteration on online cpus was already quiescent (hopefully my assumptions are right). Preemption is left enabled during all the critical section.

It looks a lot like Lai's approach, except that I use a cpumask (I thought it looked cleaner and typically involves less operations than looping on each possible cpu). I also don't disable preemption and assume that cpu hotplug can happen at any point during this critical section.

Something along the lines of :

static DECLARE_BITMAP(cpu_wait_expedited_bits, CONFIG_NR_CPUS); const struct cpumask *const cpu_wait_expedited_mask =

			to_cpumask(cpu_wait_expedited_bits);

	mutex_lock(&rcu_sched_expedited_mutex);
	cpumask_clear(cpu_wait_expedited_mask);
	for_each_online_cpu(cpu) {
		init and queue cpu req, and wake_up_process().
		cpumask_set_cpu(cpu, cpu_wait_expedited_mask);
	}
	for_each_cpu_mask(cpu, cpu_wait_expedited_mask) {
		wait_for_completion(cpu req);
	}
	mutex_unlock(&rcu_sched_expedited_mutex);
Quoted 7 lines

There is one concern with this approach : if a CPU is hotunplugged and hotplugged during the critical section, I think the scheduler would migrate the thread to a different CPU (upon hotunplug) and let the thread run on this other CPU. If the target CPU is hotplugged again, this would mean the thread would have run on a different CPU than the target. I think we can argue that a CPU going offline and online again will meet quiescent state requirements, so this should not be a problem.

Having the task runnable on some other CPU is very scary to me. If the CPU comes back online, and synchronize_sched_expedited() manages to run before the task gets migrated back onto that CPU, then the grace period could be ended too soon.

All of this is intended to make synchronize_sched_expedited() be able to run in a CPU hotplug notifier. Do we have an example where someone really wants to do this? If not, I am really starting to like v7 of the patch. ;-)

If someone really does need to run synchronize_sched_expedited() from a CPU hotplug notifier, perhaps a simpler approach is to have something like a try_get_online_cpus(), and just invoke synchronize_sched() upon failure:

	void synchronize_sched_expedited(void)
	{
		int cpu;
		unsigned long flags;
		struct rq *rq;
		struct migration_req *req;

		mutex_lock(&rcu_sched_expedited_mutex);
		if (!try_get_online_cpus()) {
			synchronize_sched();
			return;
		}

		/* rest of synchronize_sched_expedited()... */

But I would want to see a real need for this beforehand.

Thanx, Paul

#8 lore raw
Quoted 136 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 127 lines · Mathieu Desnoyers
Quoted 84 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 28 lines · Paul E. McKenney
Quoted 8 lines · Lai Jiangshan
Quoted 5 lines · Paul E. McKenney

Good point -- I should at the very least add a comment to synchronize_sched_expedited() stating that it cannot be called holding any lock that is acquired in a CPU hotplug notifier. If this restriction causes any problems, then your approach seems like a promising fix.

Thank you very much for your review and comments!!!

Quoted 16 lines
Quoted 15 lines
Quoted 5 lines

The coupling of synchronize_sched_expedited() and migration_req is largely increased:

1) The offline cpu's per_cpu(rcu_migration_req, cpu) is handled. See migration_call::CPU_DEAD

Good. ;-)

Quoted 3 lines

2) migration_call() is the highest priority of cpu notifiers, So even any other cpu notifier calls synchronize_sched_expedited(), It'll not cause DEADLOCK.

You mean if using your preempt_disable() approach, right? Unless I am missing something, the current get_online_cpus() approach would deadlock in this case.

Quoted 7 lines
Quoted 3 lines

Yes, I mean if using my preempt_disable() approach. The current get_online_cpus() approach would NOT deadlock in this case also, we can require get_online_cpus() in cpu notifiers.

I have added the comment for the time being, but should people need to use this in CPU-hotplug notifiers, then again your preempt_disable() approach looks to be a promising fix.

I looked more closely at your preempt_disable() suggestion, which you presented earlier as follows:

Quoted 8 lines

I think we can reuse req->dest_cpu and remove get_online_cpus(). (and use preempt_disable() and for_each_possible_cpu())

req->dest_cpu = -2 means @req is not queued
req->dest_cpu = -1 means @req is queued

a little like this code:

Quoted 14 lines
	mutex_lock(&rcu_sched_expedited_mutex);
	for_each_possible_cpu(cpu) {
		preempt_disable()
		if (cpu is not online)
			just set req->dest_cpu to -2;
		else
			init and queue req, and wake_up_process().
		preempt_enable()
	}
	for_each_possible_cpu(cpu) {
		if (req is queued)
			wait_for_completion().
	}
	mutex_unlock(&rcu_sched_expedited_mutex);

I am concerned about the following sequence of events:

o synchronize_sched_expedited() disables preemption, thus blocking
offlining operations.

o CPU 1 starts offlining CPU 0. It acquires the CPU-hotplug lock,
and proceeds, and is now waiting for preemption to be enabled.

o synchronize_sched_expedited() disables preemption, sees
that CPU 0 is online, so initializes and queues a request, does a wake-up-process(), and finally does a preempt_enable().

o CPU 0 is currently running a high-priority real-time process,
so the wakeup does not immediately happen.

o The offlining process completes, including the kthread_stop()
to the migration task.

o The migration task wakes up, sees kthread_should_stop(),
and so exits without checking its queue.

Quoted 9 lines

o synchronize_sched_expedited() waits forever for CPU 0 to respond.

I suppose that one way to handle this would be to check for the CPU going offline before doing the wait_for_completion(), but I am concerned about races affecting this check as well.

Or is there something in the CPU-offline process that makes the above sequence of events impossible?

I think you are right, there is a problem there. The simple fact that this needs to disable preemption to protect against cpu hotplug seems a bit strange. If I may propose an alternate solution, which assumes that threads pinned to a CPU are migrated to a different CPU when a CPU goes offline (and will therefore execute anyway), and that a CPU brought online after the first iteration on online cpus was already quiescent (hopefully my assumptions are right). Preemption is left enabled during all the critical section.

It looks a lot like Lai's approach, except that I use a cpumask (I thought it looked cleaner and typically involves less operations than looping on each possible cpu). I also don't disable preemption and assume that cpu hotplug can happen at any point during this critical section.

Something along the lines of :

static DECLARE_BITMAP(cpu_wait_expedited_bits, CONFIG_NR_CPUS); const struct cpumask *const cpu_wait_expedited_mask =

			to_cpumask(cpu_wait_expedited_bits);

	mutex_lock(&rcu_sched_expedited_mutex);
	cpumask_clear(cpu_wait_expedited_mask);
	for_each_online_cpu(cpu) {
		init and queue cpu req, and wake_up_process().
		cpumask_set_cpu(cpu, cpu_wait_expedited_mask);
	}
	for_each_cpu_mask(cpu, cpu_wait_expedited_mask) {
		wait_for_completion(cpu req);
	}
	mutex_unlock(&rcu_sched_expedited_mutex);
Quoted 7 lines

There is one concern with this approach : if a CPU is hotunplugged and hotplugged during the critical section, I think the scheduler would migrate the thread to a different CPU (upon hotunplug) and let the thread run on this other CPU. If the target CPU is hotplugged again, this would mean the thread would have run on a different CPU than the target. I think we can argue that a CPU going offline and online again will meet quiescent state requirements, so this should not be a problem.

Quoted 5 lines

Having the task runnable on some other CPU is very scary to me. If the CPU comes back online, and synchronize_sched_expedited() manages to run before the task gets migrated back onto that CPU, then the grace period could be ended too soon.

Well, the idea is that we want all in-flight preempt off sections (as seen at the beginning of synchronize_sched_expedited()) to be over before we consider the grace period as ended, right ?

Let's say we read the cpu online mask at a given time (potentially non atomically, we don't really care).

If, at any point in time while we read the cpu online mask, a CPU appears to be offline, this means that it cannot hold any in-flight preempt off section.

Even if that specific CPU comes back online after this moment, and starts scheduling threads again, these threads cannot ever possibly be in-flight in the old grace period.

Therefore, my argument is that for rcu_sched (classic rcu), a CPU going back online while we wait for quiescent state cannot possibly ever start running a thread in the previous grace period.

My second argument is that if a CPU is hotunplugging while we wait for QS, either :

- It lets the completion thread run before it goes offline. That's fine
- It goes offline and the completion thread is migrated to another CPU. This will just make synchronize_sched_expedited() wait for one more completion that will execute on the CPU the thread has migrated to. Again, we don't care.
- It goes offline/online/offline/online/... : We go back to my first argument, which states that if a CPU is out of the cpu online mask at any given time after we started the synchronize_sched_expedited() execution, it cannot possibly hold an in-flight preempt off section belonging to the old GP.

Or am I missing something ?

Mathieu

Quoted 28 lines

All of this is intended to make synchronize_sched_expedited() be able to run in a CPU hotplug notifier. Do we have an example where someone really wants to do this? If not, I am really starting to like v7 of the patch. ;-)

If someone really does need to run synchronize_sched_expedited() from a CPU hotplug notifier, perhaps a simpler approach is to have something like a try_get_online_cpus(), and just invoke synchronize_sched() upon failure:

	void synchronize_sched_expedited(void)
	{
		int cpu;
		unsigned long flags;
		struct rq *rq;
		struct migration_req *req;

		mutex_lock(&rcu_sched_expedited_mutex);
		if (!try_get_online_cpus()) {
			synchronize_sched();
			return;
		}

		/* rest of synchronize_sched_expedited()... */

But I would want to see a real need for this beforehand.

Thanx, Paul

Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#9 lore raw
Quoted 176 lines · Mathieu Desnoyers
Quoted 136 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 127 lines · Mathieu Desnoyers
Quoted 84 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 28 lines · Paul E. McKenney
Quoted 8 lines · Lai Jiangshan
Quoted 5 lines · Paul E. McKenney

Good point -- I should at the very least add a comment to synchronize_sched_expedited() stating that it cannot be called holding any lock that is acquired in a CPU hotplug notifier. If this restriction causes any problems, then your approach seems like a promising fix.

Thank you very much for your review and comments!!!

Quoted 16 lines
Quoted 15 lines
Quoted 5 lines

The coupling of synchronize_sched_expedited() and migration_req is largely increased:

1) The offline cpu's per_cpu(rcu_migration_req, cpu) is handled. See migration_call::CPU_DEAD

Good. ;-)

Quoted 3 lines

2) migration_call() is the highest priority of cpu notifiers, So even any other cpu notifier calls synchronize_sched_expedited(), It'll not cause DEADLOCK.

You mean if using your preempt_disable() approach, right? Unless I am missing something, the current get_online_cpus() approach would deadlock in this case.

Quoted 7 lines
Quoted 3 lines

Yes, I mean if using my preempt_disable() approach. The current get_online_cpus() approach would NOT deadlock in this case also, we can require get_online_cpus() in cpu notifiers.

I have added the comment for the time being, but should people need to use this in CPU-hotplug notifiers, then again your preempt_disable() approach looks to be a promising fix.

I looked more closely at your preempt_disable() suggestion, which you presented earlier as follows:

Quoted 8 lines

I think we can reuse req->dest_cpu and remove get_online_cpus(). (and use preempt_disable() and for_each_possible_cpu())

req->dest_cpu = -2 means @req is not queued
req->dest_cpu = -1 means @req is queued

a little like this code:

Quoted 14 lines
	mutex_lock(&rcu_sched_expedited_mutex);
	for_each_possible_cpu(cpu) {
		preempt_disable()
		if (cpu is not online)
			just set req->dest_cpu to -2;
		else
			init and queue req, and wake_up_process().
		preempt_enable()
	}
	for_each_possible_cpu(cpu) {
		if (req is queued)
			wait_for_completion().
	}
	mutex_unlock(&rcu_sched_expedited_mutex);

I am concerned about the following sequence of events:

o synchronize_sched_expedited() disables preemption, thus blocking
offlining operations.

o CPU 1 starts offlining CPU 0. It acquires the CPU-hotplug lock,
and proceeds, and is now waiting for preemption to be enabled.

o synchronize_sched_expedited() disables preemption, sees
that CPU 0 is online, so initializes and queues a request, does a wake-up-process(), and finally does a preempt_enable().

o CPU 0 is currently running a high-priority real-time process,
so the wakeup does not immediately happen.

o The offlining process completes, including the kthread_stop()
to the migration task.

o The migration task wakes up, sees kthread_should_stop(),
and so exits without checking its queue.

Quoted 9 lines

o synchronize_sched_expedited() waits forever for CPU 0 to respond.

I suppose that one way to handle this would be to check for the CPU going offline before doing the wait_for_completion(), but I am concerned about races affecting this check as well.

Or is there something in the CPU-offline process that makes the above sequence of events impossible?

I think you are right, there is a problem there. The simple fact that this needs to disable preemption to protect against cpu hotplug seems a bit strange. If I may propose an alternate solution, which assumes that threads pinned to a CPU are migrated to a different CPU when a CPU goes offline (and will therefore execute anyway), and that a CPU brought online after the first iteration on online cpus was already quiescent (hopefully my assumptions are right). Preemption is left enabled during all the critical section.

It looks a lot like Lai's approach, except that I use a cpumask (I thought it looked cleaner and typically involves less operations than looping on each possible cpu). I also don't disable preemption and assume that cpu hotplug can happen at any point during this critical section.

Something along the lines of :

static DECLARE_BITMAP(cpu_wait_expedited_bits, CONFIG_NR_CPUS); const struct cpumask *const cpu_wait_expedited_mask =

			to_cpumask(cpu_wait_expedited_bits);

	mutex_lock(&rcu_sched_expedited_mutex);
	cpumask_clear(cpu_wait_expedited_mask);
	for_each_online_cpu(cpu) {
		init and queue cpu req, and wake_up_process().
		cpumask_set_cpu(cpu, cpu_wait_expedited_mask);
	}
	for_each_cpu_mask(cpu, cpu_wait_expedited_mask) {
		wait_for_completion(cpu req);
	}
	mutex_unlock(&rcu_sched_expedited_mutex);
Quoted 7 lines

There is one concern with this approach : if a CPU is hotunplugged and hotplugged during the critical section, I think the scheduler would migrate the thread to a different CPU (upon hotunplug) and let the thread run on this other CPU. If the target CPU is hotplugged again, this would mean the thread would have run on a different CPU than the target. I think we can argue that a CPU going offline and online again will meet quiescent state requirements, so this should not be a problem.

Quoted 5 lines

Having the task runnable on some other CPU is very scary to me. If the CPU comes back online, and synchronize_sched_expedited() manages to run before the task gets migrated back onto that CPU, then the grace period could be ended too soon.

Well, the idea is that we want all in-flight preempt off sections (as seen at the beginning of synchronize_sched_expedited()) to be over before we consider the grace period as ended, right ?

Let's say we read the cpu online mask at a given time (potentially non atomically, we don't really care).

If, at any point in time while we read the cpu online mask, a CPU appears to be offline, this means that it cannot hold any in-flight preempt off section.

Even if that specific CPU comes back online after this moment, and starts scheduling threads again, these threads cannot ever possibly be in-flight in the old grace period.

Therefore, my argument is that for rcu_sched (classic rcu), a CPU going back online while we wait for quiescent state cannot possibly ever start running a thread in the previous grace period.

My second argument is that if a CPU is hotunplugging while we wait for QS, either :

- It lets the completion thread run before it goes offline. That's fine
- It goes offline and the completion thread is migrated to another CPU. This will just make synchronize_sched_expedited() wait for one more completion that will execute on the CPU the thread has migrated to. Again, we don't care.
- It goes offline/online/offline/online/... : We go back to my first argument, which states that if a CPU is out of the cpu online mask at any given time after we started the synchronize_sched_expedited() execution, it cannot possibly hold an in-flight preempt off section belonging to the old GP.

Quoted 1 line

Or am I missing something ?

I am worried (perhaps unnecessarily) about the CPU coming online, its kthread still running on some other CPU, someone doing a synchronize_sched_expedited(), which then might possibly complete before the kthread migrates back where it belongs. If the newly onlined CPU is in an extended RCU read-side critical section, we might end the expedited grace period too soon.

My turn. Am I missing something? ;-)

Thanx, Paul

Quoted 39 lines

Mathieu

Quoted 28 lines

All of this is intended to make synchronize_sched_expedited() be able to run in a CPU hotplug notifier. Do we have an example where someone really wants to do this? If not, I am really starting to like v7 of the patch. ;-)

If someone really does need to run synchronize_sched_expedited() from a CPU hotplug notifier, perhaps a simpler approach is to have something like a try_get_online_cpus(), and just invoke synchronize_sched() upon failure:

	void synchronize_sched_expedited(void)
	{
		int cpu;
		unsigned long flags;
		struct rq *rq;
		struct migration_req *req;

		mutex_lock(&rcu_sched_expedited_mutex);
		if (!try_get_online_cpus()) {
			synchronize_sched();
			return;
		}

		/* rest of synchronize_sched_expedited()... */

But I would want to see a real need for this beforehand.

Thanx, Paul

Signature · 6 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
#10 lore raw
Quoted 179 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 176 lines · Mathieu Desnoyers
Quoted 136 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 127 lines · Mathieu Desnoyers
Quoted 84 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 28 lines · Paul E. McKenney
Quoted 8 lines · Lai Jiangshan
Quoted 5 lines · Paul E. McKenney

Good point -- I should at the very least add a comment to synchronize_sched_expedited() stating that it cannot be called holding any lock that is acquired in a CPU hotplug notifier. If this restriction causes any problems, then your approach seems like a promising fix.

Thank you very much for your review and comments!!!

Quoted 16 lines
Quoted 15 lines
Quoted 5 lines

The coupling of synchronize_sched_expedited() and migration_req is largely increased:

1) The offline cpu's per_cpu(rcu_migration_req, cpu) is handled. See migration_call::CPU_DEAD

Good. ;-)

Quoted 3 lines

2) migration_call() is the highest priority of cpu notifiers, So even any other cpu notifier calls synchronize_sched_expedited(), It'll not cause DEADLOCK.

You mean if using your preempt_disable() approach, right? Unless I am missing something, the current get_online_cpus() approach would deadlock in this case.

Quoted 7 lines
Quoted 3 lines

Yes, I mean if using my preempt_disable() approach. The current get_online_cpus() approach would NOT deadlock in this case also, we can require get_online_cpus() in cpu notifiers.

I have added the comment for the time being, but should people need to use this in CPU-hotplug notifiers, then again your preempt_disable() approach looks to be a promising fix.

I looked more closely at your preempt_disable() suggestion, which you presented earlier as follows:

Quoted 8 lines

I think we can reuse req->dest_cpu and remove get_online_cpus(). (and use preempt_disable() and for_each_possible_cpu())

req->dest_cpu = -2 means @req is not queued
req->dest_cpu = -1 means @req is queued

a little like this code:

Quoted 14 lines
	mutex_lock(&rcu_sched_expedited_mutex);
	for_each_possible_cpu(cpu) {
		preempt_disable()
		if (cpu is not online)
			just set req->dest_cpu to -2;
		else
			init and queue req, and wake_up_process().
		preempt_enable()
	}
	for_each_possible_cpu(cpu) {
		if (req is queued)
			wait_for_completion().
	}
	mutex_unlock(&rcu_sched_expedited_mutex);

I am concerned about the following sequence of events:

o synchronize_sched_expedited() disables preemption, thus blocking
offlining operations.

o CPU 1 starts offlining CPU 0. It acquires the CPU-hotplug lock,
and proceeds, and is now waiting for preemption to be enabled.

o synchronize_sched_expedited() disables preemption, sees
that CPU 0 is online, so initializes and queues a request, does a wake-up-process(), and finally does a preempt_enable().

o CPU 0 is currently running a high-priority real-time process,
so the wakeup does not immediately happen.

o The offlining process completes, including the kthread_stop()
to the migration task.

o The migration task wakes up, sees kthread_should_stop(),
and so exits without checking its queue.

Quoted 9 lines

o synchronize_sched_expedited() waits forever for CPU 0 to respond.

I suppose that one way to handle this would be to check for the CPU going offline before doing the wait_for_completion(), but I am concerned about races affecting this check as well.

Or is there something in the CPU-offline process that makes the above sequence of events impossible?

I think you are right, there is a problem there. The simple fact that this needs to disable preemption to protect against cpu hotplug seems a bit strange. If I may propose an alternate solution, which assumes that threads pinned to a CPU are migrated to a different CPU when a CPU goes offline (and will therefore execute anyway), and that a CPU brought online after the first iteration on online cpus was already quiescent (hopefully my assumptions are right). Preemption is left enabled during all the critical section.

It looks a lot like Lai's approach, except that I use a cpumask (I thought it looked cleaner and typically involves less operations than looping on each possible cpu). I also don't disable preemption and assume that cpu hotplug can happen at any point during this critical section.

Something along the lines of :

static DECLARE_BITMAP(cpu_wait_expedited_bits, CONFIG_NR_CPUS); const struct cpumask *const cpu_wait_expedited_mask =

			to_cpumask(cpu_wait_expedited_bits);

	mutex_lock(&rcu_sched_expedited_mutex);
	cpumask_clear(cpu_wait_expedited_mask);
	for_each_online_cpu(cpu) {
		init and queue cpu req, and wake_up_process().
		cpumask_set_cpu(cpu, cpu_wait_expedited_mask);
	}
	for_each_cpu_mask(cpu, cpu_wait_expedited_mask) {
		wait_for_completion(cpu req);
	}
	mutex_unlock(&rcu_sched_expedited_mutex);
Quoted 7 lines

There is one concern with this approach : if a CPU is hotunplugged and hotplugged during the critical section, I think the scheduler would migrate the thread to a different CPU (upon hotunplug) and let the thread run on this other CPU. If the target CPU is hotplugged again, this would mean the thread would have run on a different CPU than the target. I think we can argue that a CPU going offline and online again will meet quiescent state requirements, so this should not be a problem.

Quoted 5 lines

Having the task runnable on some other CPU is very scary to me. If the CPU comes back online, and synchronize_sched_expedited() manages to run before the task gets migrated back onto that CPU, then the grace period could be ended too soon.

Well, the idea is that we want all in-flight preempt off sections (as seen at the beginning of synchronize_sched_expedited()) to be over before we consider the grace period as ended, right ?

Let's say we read the cpu online mask at a given time (potentially non atomically, we don't really care).

If, at any point in time while we read the cpu online mask, a CPU appears to be offline, this means that it cannot hold any in-flight preempt off section.

Even if that specific CPU comes back online after this moment, and starts scheduling threads again, these threads cannot ever possibly be in-flight in the old grace period.

Therefore, my argument is that for rcu_sched (classic rcu), a CPU going back online while we wait for quiescent state cannot possibly ever start running a thread in the previous grace period.

My second argument is that if a CPU is hotunplugging while we wait for QS, either :

- It lets the completion thread run before it goes offline. That's fine
- It goes offline and the completion thread is migrated to another CPU. This will just make synchronize_sched_expedited() wait for one more completion that will execute on the CPU the thread has migrated to. Again, we don't care.
- It goes offline/online/offline/online/... : We go back to my first argument, which states that if a CPU is out of the cpu online mask at any given time after we started the synchronize_sched_expedited() execution, it cannot possibly hold an in-flight preempt off section belonging to the old GP.

Quoted 1 line

Or am I missing something ?

Quoted 9 lines

I am worried (perhaps unnecessarily) about the CPU coming online, its kthread still running on some other CPU, someone doing a synchronize_sched_expedited(), which then might possibly complete before the kthread migrates back where it belongs. If the newly onlined CPU is in an extended RCU read-side critical section, we might end the expedited grace period too soon.

My turn. Am I missing something? ;-)

If the completion kthreads only live within the boundary of the rcu_sched_expedited_mutex critical section, we never face this problem.

Therefore, all kthreads created for a given expedited grace period should be waited for before the rcu_sched_expedited_mutex is released.

Here, I don't know the specific behavior of the threads you are willing to use, but I see two possibilities when facing cpu hotplug :

- Either those threads are always active in the system, _really_ tied to a CPU and the hotunplug event kills them and sends their completion. (this is I think what Lai described)
- Or we create them while holding the rcu_sched_expedited_mutex, pin them to a CPU. They are less strictly bound to a CPU and get migrated to a different CPU upon hotunplug. Note that their life-span is limited to the rcu_sched_expedited_mutex section, because we expect them to die after completion. This implies a thread creation overhead.

Hopefully one of the solutions I describe above match the current implementation. :)

Mathieu

Quoted 41 lines

Thanx, Paul

Quoted 39 lines

Mathieu

Quoted 28 lines

All of this is intended to make synchronize_sched_expedited() be able to run in a CPU hotplug notifier. Do we have an example where someone really wants to do this? If not, I am really starting to like v7 of the patch. ;-)

If someone really does need to run synchronize_sched_expedited() from a CPU hotplug notifier, perhaps a simpler approach is to have something like a try_get_online_cpus(), and just invoke synchronize_sched() upon failure:

	void synchronize_sched_expedited(void)
	{
		int cpu;
		unsigned long flags;
		struct rq *rq;
		struct migration_req *req;

		mutex_lock(&rcu_sched_expedited_mutex);
		if (!try_get_online_cpus()) {
			synchronize_sched();
			return;
		}

		/* rest of synchronize_sched_expedited()... */

But I would want to see a real need for this beforehand.

Thanx, Paul

Signature · 6 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Signature · 2 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
#11 lore raw
Quoted 187 lines · Mathieu Desnoyers
Quoted 186 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 176 lines · Mathieu Desnoyers
Quoted 136 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 127 lines · Mathieu Desnoyers
Quoted 84 lines · * Paul E. McKenney ([email protected]) wrote:
Quoted 28 lines · Paul E. McKenney
Quoted 8 lines · Lai Jiangshan
Quoted 5 lines · Paul E. McKenney

Good point -- I should at the very least add a comment to synchronize_sched_expedited() stating that it cannot be called holding any lock that is acquired in a CPU hotplug notifier. If this restriction causes any problems, then your approach seems like a promising fix.

Thank you very much for your review and comments!!!

Quoted 16 lines
Quoted 15 lines
Quoted 5 lines

The coupling of synchronize_sched_expedited() and migration_req is largely increased:

1) The offline cpu's per_cpu(rcu_migration_req, cpu) is handled. See migration_call::CPU_DEAD

Good. ;-)

Quoted 3 lines

2) migration_call() is the highest priority of cpu notifiers, So even any other cpu notifier calls synchronize_sched_expedited(), It'll not cause DEADLOCK.

You mean if using your preempt_disable() approach, right? Unless I am missing something, the current get_online_cpus() approach would deadlock in this case.

Quoted 7 lines
Quoted 3 lines

Yes, I mean if using my preempt_disable() approach. The current get_online_cpus() approach would NOT deadlock in this case also, we can require get_online_cpus() in cpu notifiers.

I have added the comment for the time being, but should people need to use this in CPU-hotplug notifiers, then again your preempt_disable() approach looks to be a promising fix.

I looked more closely at your preempt_disable() suggestion, which you presented earlier as follows:

Quoted 8 lines

I think we can reuse req->dest_cpu and remove get_online_cpus(). (and use preempt_disable() and for_each_possible_cpu())

req->dest_cpu = -2 means @req is not queued
req->dest_cpu = -1 means @req is queued

a little like this code:

Quoted 14 lines
	mutex_lock(&rcu_sched_expedited_mutex);
	for_each_possible_cpu(cpu) {
		preempt_disable()
		if (cpu is not online)
			just set req->dest_cpu to -2;
		else
			init and queue req, and wake_up_process().
		preempt_enable()
	}
	for_each_possible_cpu(cpu) {
		if (req is queued)
			wait_for_completion().
	}
	mutex_unlock(&rcu_sched_expedited_mutex);

I am concerned about the following sequence of events:

o synchronize_sched_expedited() disables preemption, thus blocking
offlining operations.

o CPU 1 starts offlining CPU 0. It acquires the CPU-hotplug lock,
and proceeds, and is now waiting for preemption to be enabled.

o synchronize_sched_expedited() disables preemption, sees
that CPU 0 is online, so initializes and queues a request, does a wake-up-process(), and finally does a preempt_enable().

o CPU 0 is currently running a high-priority real-time process,
so the wakeup does not immediately happen.

o The offlining process completes, including the kthread_stop()
to the migration task.

o The migration task wakes up, sees kthread_should_stop(),
and so exits without checking its queue.

Quoted 9 lines

o synchronize_sched_expedited() waits forever for CPU 0 to respond.

I suppose that one way to handle this would be to check for the CPU going offline before doing the wait_for_completion(), but I am concerned about races affecting this check as well.

Or is there something in the CPU-offline process that makes the above sequence of events impossible?

I think you are right, there is a problem there. The simple fact that this needs to disable preemption to protect against cpu hotplug seems a bit strange. If I may propose an alternate solution, which assumes that threads pinned to a CPU are migrated to a different CPU when a CPU goes offline (and will therefore execute anyway), and that a CPU brought online after the first iteration on online cpus was already quiescent (hopefully my assumptions are right). Preemption is left enabled during all the critical section.

It looks a lot like Lai's approach, except that I use a cpumask (I thought it looked cleaner and typically involves less operations than looping on each possible cpu). I also don't disable preemption and assume that cpu hotplug can happen at any point during this critical section.

Something along the lines of :

static DECLARE_BITMAP(cpu_wait_expedited_bits, CONFIG_NR_CPUS); const struct cpumask *const cpu_wait_expedited_mask =

			to_cpumask(cpu_wait_expedited_bits);

	mutex_lock(&rcu_sched_expedited_mutex);
	cpumask_clear(cpu_wait_expedited_mask);
	for_each_online_cpu(cpu) {
		init and queue cpu req, and wake_up_process().
		cpumask_set_cpu(cpu, cpu_wait_expedited_mask);
	}
	for_each_cpu_mask(cpu, cpu_wait_expedited_mask) {
		wait_for_completion(cpu req);
	}
	mutex_unlock(&rcu_sched_expedited_mutex);
Quoted 7 lines

There is one concern with this approach : if a CPU is hotunplugged and hotplugged during the critical section, I think the scheduler would migrate the thread to a different CPU (upon hotunplug) and let the thread run on this other CPU. If the target CPU is hotplugged again, this would mean the thread would have run on a different CPU than the target. I think we can argue that a CPU going offline and online again will meet quiescent state requirements, so this should not be a problem.

Quoted 5 lines

Having the task runnable on some other CPU is very scary to me. If the CPU comes back online, and synchronize_sched_expedited() manages to run before the task gets migrated back onto that CPU, then the grace period could be ended too soon.

Well, the idea is that we want all in-flight preempt off sections (as seen at the beginning of synchronize_sched_expedited()) to be over before we consider the grace period as ended, right ?

Let's say we read the cpu online mask at a given time (potentially non atomically, we don't really care).

If, at any point in time while we read the cpu online mask, a CPU appears to be offline, this means that it cannot hold any in-flight preempt off section.

Even if that specific CPU comes back online after this moment, and starts scheduling threads again, these threads cannot ever possibly be in-flight in the old grace period.

Therefore, my argument is that for rcu_sched (classic rcu), a CPU going back online while we wait for quiescent state cannot possibly ever start running a thread in the previous grace period.

My second argument is that if a CPU is hotunplugging while we wait for QS, either :

- It lets the completion thread run before it goes offline. That's fine
- It goes offline and the completion thread is migrated to another CPU. This will just make synchronize_sched_expedited() wait for one more completion that will execute on the CPU the thread has migrated to. Again, we don't care.
- It goes offline/online/offline/online/... : We go back to my first argument, which states that if a CPU is out of the cpu online mask at any given time after we started the synchronize_sched_expedited() execution, it cannot possibly hold an in-flight preempt off section belonging to the old GP.

Quoted 1 line

Or am I missing something ?

I am worried (perhaps unnecessarily) about the CPU coming online, its kthread still running on some other CPU, someone doing a synchronize_sched_expedited(), which then might possibly complete before the kthread migrates back where it belongs. If the newly onlined CPU is in an extended RCU read-side critical section, we might end the expedited grace period too soon.

Quoted 8 lines
Quoted 2 lines

My turn. Am I missing something? ;-)

If the completion kthreads only live within the boundary of the rcu_sched_expedited_mutex critical section, we never face this problem.

Therefore, all kthreads created for a given expedited grace period should be waited for before the rcu_sched_expedited_mutex is released.

True, but the overhead of creating (say) 100 kthreads is not so consistent with the "expedited" in synchronize_sched_expedited().

Quoted 6 lines

Here, I don't know the specific behavior of the threads you are willing to use, but I see two possibilities when facing cpu hotplug :

- Either those threads are always active in the system, _really_ tied to a CPU and the hotunplug event kills them and sends their completion. (this is I think what Lai described)

Yep. And this is what v7 of the patch did. Lai would like me to get rid of the get_online_cpus(), replacing it with preempt_disable(). Which I find to be incredibly scary, given the possibility of the kthread somehow executing on some other CPU, thus breaking RCU.

But see my next reply to Lai.

Quoted 5 lines

- Or we create them while holding the rcu_sched_expedited_mutex, pin them to a CPU. They are less strictly bound to a CPU and get migrated to a different CPU upon hotunplug. Note that their life-span is limited to the rcu_sched_expedited_mutex section, because we expect them to die after completion. This implies a thread creation overhead.

And the thread-creation/destruction overhead is fatal, I believe.

Quoted 2 lines

Hopefully one of the solutions I describe above match the current implementation. :)

#1. ;-)

Thanx, Paul

Quoted 53 lines

Mathieu

Quoted 41 lines

Thanx, Paul

Quoted 39 lines

Mathieu

Quoted 28 lines

All of this is intended to make synchronize_sched_expedited() be able to run in a CPU hotplug notifier. Do we have an example where someone really wants to do this? If not, I am really starting to like v7 of the patch. ;-)

If someone really does need to run synchronize_sched_expedited() from a CPU hotplug notifier, perhaps a simpler approach is to have something like a try_get_online_cpus(), and just invoke synchronize_sched() upon failure:

	void synchronize_sched_expedited(void)
	{
		int cpu;
		unsigned long flags;
		struct rq *rq;
		struct migration_req *req;

		mutex_lock(&rcu_sched_expedited_mutex);
		if (!try_get_online_cpus()) {
			synchronize_sched();
			return;
		}

		/* rest of synchronize_sched_expedited()... */

But I would want to see a real need for this beforehand.

Thanx, Paul

Signature · 6 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Signature · 6 lines
Mathieu Desnoyers
OpenPGP key fingerprint: 8CD5 52C3 8E3C 4140 715F  BA06 3F25 A8FE 3BAE 9A68
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to [email protected]
More majordomo info at  http://vger.kernel.org/majordomo-info.html
#12 lore raw
In reply to Paul E. McKenney
Quoted 24 lines · Paul E. McKenney

I am concerned about the following sequence of events:

o synchronize_sched_expedited() disables preemption, thus blocking
offlining operations.

o CPU 1 starts offlining CPU 0. It acquires the CPU-hotplug lock,
and proceeds, and is now waiting for preemption to be enabled.

o synchronize_sched_expedited() disables preemption, sees
that CPU 0 is online, so initializes and queues a request, does a wake-up-process(), and finally does a preempt_enable().

o CPU 0 is currently running a high-priority real-time process,
so the wakeup does not immediately happen.

o The offlining process completes, including the kthread_stop()
to the migration task.

o The migration task wakes up, sees kthread_should_stop(),
and so exits without checking its queue.

o synchronize_sched_expedited() waits forever for CPU 0 to respond.

Quoted 10 lines

I suppose that one way to handle this would be to check for the CPU going offline before doing the wait_for_completion(), but I am concerned about races affecting this check as well.

Or is there something in the CPU-offline process that makes the above sequence of events impossible?

Thanx, Paul

I realized this, I wrote this:

Quoted 6 lines

The coupling of synchronize_sched_expedited() and migration_req is largely increased:

1) The offline cpu's per_cpu(rcu_migration_req, cpu) is handled. See migration_call::CPU_DEAD

synchronize_sched_expedited() will not wait for CPU#0, because migration_call()::case CPU_DEAD wakes up the requestors.

migration_call()

{
	...
	case CPU_DEAD:
	case CPU_DEAD_FROZEN:
		...
		/*
		 * No need to migrate the tasks: it was best-effort if
		 * they didn't take sched_hotcpu_mutex. Just wake up
		 * the requestors.
		 */
		spin_lock_irq(&rq->lock);
		while (!list_empty(&rq->migration_queue)) {
			struct migration_req *req;

			req = list_entry(rq->migration_queue.next,
					 struct migration_req, list);
			list_del_init(&req->list);
			spin_unlock_irq(&rq->lock);
			complete(&req->done);
			spin_lock_irq(&rq->lock);
		}
		spin_unlock_irq(&rq->lock);
		...
	...
}

My approach depend on the requestors are waked up at any case. migration_call() does it for us but the coupling is largely increased.

Lai

#13 lore raw
Quoted 74 lines · Lai Jiangshan
Quoted 24 lines · Paul E. McKenney

I am concerned about the following sequence of events:

o synchronize_sched_expedited() disables preemption, thus blocking
offlining operations.

o CPU 1 starts offlining CPU 0. It acquires the CPU-hotplug lock,
and proceeds, and is now waiting for preemption to be enabled.

o synchronize_sched_expedited() disables preemption, sees
that CPU 0 is online, so initializes and queues a request, does a wake-up-process(), and finally does a preempt_enable().

o CPU 0 is currently running a high-priority real-time process,
so the wakeup does not immediately happen.

o The offlining process completes, including the kthread_stop()
to the migration task.

o The migration task wakes up, sees kthread_should_stop(),
and so exits without checking its queue.

o synchronize_sched_expedited() waits forever for CPU 0 to respond.

Quoted 10 lines

I suppose that one way to handle this would be to check for the CPU going offline before doing the wait_for_completion(), but I am concerned about races affecting this check as well.

Or is there something in the CPU-offline process that makes the above sequence of events impossible?

Thanx, Paul

I realized this, I wrote this:

Quoted 6 lines

The coupling of synchronize_sched_expedited() and migration_req is largely increased:

1) The offline cpu's per_cpu(rcu_migration_req, cpu) is handled. See migration_call::CPU_DEAD

synchronize_sched_expedited() will not wait for CPU#0, because migration_call()::case CPU_DEAD wakes up the requestors.

migration_call()

{
	...
	case CPU_DEAD:
	case CPU_DEAD_FROZEN:
		...
		/*
		 * No need to migrate the tasks: it was best-effort if
		 * they didn't take sched_hotcpu_mutex. Just wake up
		 * the requestors.
		 */
		spin_lock_irq(&rq->lock);
		while (!list_empty(&rq->migration_queue)) {
			struct migration_req *req;

			req = list_entry(rq->migration_queue.next,
					 struct migration_req, list);
			list_del_init(&req->list);
			spin_unlock_irq(&rq->lock);
			complete(&req->done);
			spin_lock_irq(&rq->lock);
		}
		spin_unlock_irq(&rq->lock);
		...
	...
}
Quoted 3 lines

My approach depend on the requestors are waked up at any case. migration_call() does it for us but the coupling is largely increased.

OK, good point! I do need to think about this.

In the meantime, where do you see a need to run synchronize_sched_expedited() from within a hotplug CPU notifier?

Thanx, Paul

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

OK, good point! I do need to think about this.

In the meantime, where do you see a need to run synchronize_sched_expedited() from within a hotplug CPU notifier?

Thanx, Paul

I don't worry about synchronize_sched_expedited() called from within a hotplug CPU notifier:

1st synchronize_sched_expedited() is newly, nobody calls it before current. 2nd get_online_cpus() will not cause DEADLOCK in CPU notifier:
get_online_cpus() finds itself owns the cpu_hotplug.lock, it will not take it again.

I worry DEADLOCK like this:(ABBA DEADLOCK)

Quoted 9 lines

get_online_cpus() is a large lock, a lot's of lock in kernel is required after cpu_hotplug.lock.

_cpu_down()
cpu_hotplug_begin()
mutex_lock(&cpu_hotplug.lock)
__raw_notifier_call_chain(CPU_DOWN_PREPARE)
Lock a-kernel-lock.

Quoted 3 lines

It means when we have held a-kernel-lock, we can not call synchronize_sched_expedited(). get_online_cpus() narrows synchronize_sched_expedited()'s usages.

One thread calls _cpu_down() which do "mutex_lock(&cpu_hotplug.lock)" and then do "Lock a-kernel-lock", other thread calls synchronize_sched_expedited() with a-kernel-lock held, ABBA DEADLOCK would happen:

thread 1                            |        thread 2
_cpu_down()                         |    Lock a-kernel-lock. 
  mutex_lock(&cpu_hotplug.lock)     |    synchronize_sched_expedited()

------------------------------------------------------------------------
Lock a-kernel-lock.(wait thread2) | mutex_lock(&cpu_hotplug.lock)
(wait thread 1)

cpuset_lock() is an example of a-kernel-lock as described before. cpuset_lock() is required in CPU notifier.

But some work in cpuset need get_online_cpus().
(cpuset_lock() and then get_online_cpus(), we can
not release cpuset_lock() temporarily)

The fix is putting this work done in workqueue.
(get_online_cpus() and then cpuset_lock());

Thanx.
Lai

#15 lore raw
Quoted 12 lines · Lai Jiangshan
Quoted 7 lines · Paul E. McKenney

OK, good point! I do need to think about this.

In the meantime, where do you see a need to run synchronize_sched_expedited() from within a hotplug CPU notifier?

Thanx, Paul

I don't worry about synchronize_sched_expedited() called from within a hotplug CPU notifier:

Quoted 6 lines

1st synchronize_sched_expedited() is newly, nobody calls it before current. 2nd get_online_cpus() will not cause DEADLOCK in CPU notifier:
get_online_cpus() finds itself owns the cpu_hotplug.lock, it will not take it again.

I worry DEADLOCK like this:(ABBA DEADLOCK)

Good point -- you had in fact mentioned this earlier.

Quoted 29 lines
Quoted 9 lines

get_online_cpus() is a large lock, a lot's of lock in kernel is required after cpu_hotplug.lock.

_cpu_down()
cpu_hotplug_begin()
mutex_lock(&cpu_hotplug.lock)
__raw_notifier_call_chain(CPU_DOWN_PREPARE)
Lock a-kernel-lock.

Quoted 3 lines

It means when we have held a-kernel-lock, we can not call synchronize_sched_expedited(). get_online_cpus() narrows synchronize_sched_expedited()'s usages.

One thread calls _cpu_down() which do "mutex_lock(&cpu_hotplug.lock)" and then do "Lock a-kernel-lock", other thread calls synchronize_sched_expedited() with a-kernel-lock held, ABBA DEADLOCK would happen:

thread 1                            |        thread 2
_cpu_down()                         |    Lock a-kernel-lock. 
  mutex_lock(&cpu_hotplug.lock)     |    synchronize_sched_expedited()

------------------------------------------------------------------------
Lock a-kernel-lock.(wait thread2) | mutex_lock(&cpu_hotplug.lock)
(wait thread 1)

cpuset_lock() is an example of a-kernel-lock as described before. cpuset_lock() is required in CPU notifier.

Quoted 6 lines

But some work in cpuset need get_online_cpus().
(cpuset_lock() and then get_online_cpus(), we can
not release cpuset_lock() temporarily)

The fix is putting this work done in workqueue.
(get_online_cpus() and then cpuset_lock());

But there is another way.

Continue to use the migration kthreads, given that they already exist, already are created and destroyed by CPU hotplug operations, and given that they run as maximal priority.

My main concern with moving from get_online_cpus() to preempt_disable() has been the thought that somehow, sometime, in some future release of Linux, it will be possible for the migration threads to execute on the wrong CPU, perhaps only occasionally and perhaps only for very short time periods. If this were to happen, there would be the possibility that the grace period would end too soon, which would be silently fatal. My fingers simply refused to code something with this potential vulnerability.

But it is easy to insert a check into migration_thread() to see if it is running on the wrong CPU. If it is, I can do a WARN_ONCE() and also set a state variable to tell synchronize_sched_expedited() to invoke sychronize_sched(), thus avoiding messing up RCU. On the next call to synchronize_sched_expedited(), it would again try relying on the migration threads.

I am putting together yet another patch, but constructed along these lines, and will let you know how it turns out.

Thanx, Paul