Skip to contentSkip to conversation

Is stopmachine() preempt safe?

DISCUSSION Keith Owens 2 participants 6 messages Aug 27, 2006 – Aug 28, 2006

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

I cannot convince myself that stopmachine() is preempt safe. What prevents this race with CONFIG_PREEMPT=y?

cpu 0 cpu 1
stop_machine()
Process <n> reads a global resource
do_stop()
kernel_thread(stopmachine, 1)
Process <n> is preempted stopmachine() runs on cpu 1 STOPMACHINE_PREPARE STOPMACHINE_DISABLE_IRQ
do_stop() calls smdata->fn
smdata->fn changes global data
restart_machine()
STOPMACHINE_EXIT stopmachine() exits Scheduler resumes process <n> The global resource is out of sync

The stopmachine() threads on the other cpus are set to MAX_RT_PRIO-1 so they will preempt any existing process. The yield() in stopmachine() only guarantees that these kernel threads get onto the other cpus, it does not guarantee that all running tasks will proceed to a yield themselves before stopmachine runs. IOW, what guarantees that the scheduler will only run stopmachine() on the target cpus when those cpus are completely idle with no locally cached global resources?

#1 lore raw
Quoted 2 lines · Keith Owens

I cannot convince myself that stopmachine() is preempt safe. What prevents this race with CONFIG_PREEMPT=y?

Nothing. Read side is preempt_disable. Write side is stopmachine.

I wrote it that way to avoid having to touch the scheduler. A bigger stopmachine is possible which schedules all preempted tasks; my plan is to write such a thing shortly, to see what it looks like.

Cheers,
Rusty.

Signature · 1 line
Help! Save Australia from the worst of the DMCA: http://linux.org.au/law
#2 lore raw
Quoted 5 lines · Rusty Russell (on Mon, 28 Aug 2006 09:38:55 +1000) wrote:
Quoted 2 lines · Keith Owens

I cannot convince myself that stopmachine() is preempt safe. What prevents this race with CONFIG_PREEMPT=y?

Nothing. Read side is preempt_disable. Write side is stopmachine.

That is very worrying. The whole point of stopmachine is to get all cpus to a known state with no locally cached global data, so the caller of stopmachine can safely fiddle with some global data (like updating the module lists). But CONFIG_PREEMPT defeats this and turns any code that relies on stopmachine into a race.

What we need is either a scheduler flag or a new task state to be assigned to the kstopmachine threads. That indicator says

If the current state is not preempt active then schedule me.

If the current state is preempt active then put me back in the active queue.

While the runqueue contains at least one task with this flag then ignore reschedule on irq and prempt_enable.

That will ensure that the kstopmachine threads get scheduled as soon as possible but only when all the preempted tasks have got to a clean stop point, e.g. sleep or yield. At which point they have no locally cached global data, making stopmachine race safe again.

#3 lore raw
Quoted 5 lines · Keith Owens
Quoted 4 lines · Rusty Russell (on Mon, 28 Aug 2006 09:38:55 +1000) wrote:
Quoted 2 lines · Keith Owens

I cannot convince myself that stopmachine() is preempt safe. What prevents this race with CONFIG_PREEMPT=y?

Quoted 7 lines
Quoted 1 line

Nothing. Read side is preempt_disable. Write side is stopmachine.

That is very worrying. The whole point of stopmachine is to get all cpus to a known state with no locally cached global data, so the caller of stopmachine can safely fiddle with some global data (like updating the module lists). But CONFIG_PREEMPT defeats this and turns any code that relies on stopmachine into a race.

Hi Keith,

Do not panic: this is not a bug, and was never how stop_machine was to
be used. try_module_get() disables preemption, and you are supposed to disable preemption (or take cpu_hotplug_lock) when relying on cpu_online_map. Grep tells me that mm/page_alloc.c now uses it too:
looks like __alloc_pages might be buggy with this?

I thought the comment on stop_machine_run made this pretty plain:

* Description: This causes a thread to be scheduled on every other cpu,
* each of which disables interrupts, and finally interrupts are disabled
* on the current CPU. The result is that noone is holding a spinlock
* or inside any other preempt-disabled region when @fn() runs. *
* This can be thought of as a very heavy write lock, equivalent to
* grabbing every spinlock in the kernel. */

Quoted 2 lines

At which point they have no locally cached global data, making stopmachine race safe again.

My main reason for considering a change is to get rid of the preempt_disable()/preempt_enable() around try_module_get(), not to fix any existing bugs. Now we have multiple users, the branches in the sched fastpath are probably worth it.

As to bug fixes, if people didn't understand how it worked before, I'm not convinced making it more magic is really going to help them...

Here's an untested example patch:

Documentation/cpu-hotplug.txt +6 -6
diff -urpN --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/dontdiff --minimal linux-2.6.18-rc4/Documentation/cpu-hotplug.txt working-2.6.18-rc4-stop_machine_no_preempt/Documentation/cpu-hotplug.txt
@@ -111,12 +111,12 @@ for_each_cpu_mask(x,mask) - Iterate over
 #include <linux/cpu.h>
 lock_cpu_hotplug() and unlock_cpu_hotplug():
 
-The above calls are used to inhibit cpu hotplug operations. While holding the
-cpucontrol mutex, cpu_online_map will not change. If you merely need to avoid
-cpus going away, you could also use preempt_disable() and preempt_enable()
-for those sections. Just remember the critical section cannot call any
-function that can sleep or schedule this process away. The preempt_disable()
-will work as long as stop_machine_run() is used to take a cpu down.
+The above calls are used to inhibit cpu hotplug operations while
+sleeping. While holding the cpucontrol mutex, cpu_online_map will not
+change. If you merely need to avoid cpus going away, simply avoid
+calling any function that can sleep or schedule this process away.
+(This will work as long as stop_machine_run() is used to take a cpu
+down).
 
 CPU Hotplug - Frequently Asked Questions.
 
include/linux/module.h +5 -10
diff -urpN --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/dontdiff --minimal linux-2.6.18-rc4/include/linux/module.h working-2.6.18-rc4-stop_machine_no_preempt/include/linux/module.h
@@ -17,7 +17,7 @@
 #include <linux/stringify.h>
 #include <linux/kobject.h>
 #include <linux/moduleparam.h>
-#include <asm/local.h>
+#include <asm/atomic.h>
 
 #include <asm/module.h>
 
@@ -216,7 +216,7 @@ void *__symbol_get_gpl(const char *symbo
 
 struct module_ref
 {
-	local_t count;
+	atomic_t count;
 } ____cacheline_aligned;
 
 enum module_state
@@ -386,8 +386,7 @@ static inline void __module_get(struct m
 {
 	if (module) {
 		BUG_ON(module_refcount(module) == 0);
-		local_inc(&module->ref[get_cpu()].count);
-		put_cpu();
+		atomic_inc(&module->ref[raw_smp_processor_id()].count);
 	}
 }
 
@@ -396,12 +395,10 @@ static inline int try_module_get(struct 
 	int ret = 1;
 
 	if (module) {
-		unsigned int cpu = get_cpu();
 		if (likely(module_is_live(module)))
-			local_inc(&module->ref[cpu].count);
+			atomic_inc(&module->ref[raw_smp_processor_id()].count);
 		else
 			ret = 0;
-		put_cpu();
 	}
 	return ret;
 }
@@ -409,12 +406,10 @@ static inline int try_module_get(struct 
 static inline void module_put(struct module *module)
 {
 	if (module) {
-		unsigned int cpu = get_cpu();
-		local_dec(&module->ref[cpu].count);
+		atomic_dec(&module->ref[raw_smp_processor_id()].count);
 		/* Maybe they're waiting for us to drop reference? */
 		if (unlikely(!module_is_live(module)))
 			wake_up_process(module->waiter);
-		put_cpu();
 	}
 }
 
include/linux/sched.h +3 -1
diff -urpN --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/dontdiff --minimal linux-2.6.18-rc4/include/linux/sched.h working-2.6.18-rc4-stop_machine_no_preempt/include/linux/sched.h
@@ -126,7 +126,9 @@ extern unsigned long nr_uninterruptible(
 extern unsigned long nr_active(void);
 extern unsigned long nr_iowait(void);
 extern unsigned long weighted_cpuload(const int cpu);
-
+#ifdef CONFIG_PREEMPT
+DECLARE_PER_CPU(struct task_struct *, stop_machine_thread);
+#endif
 
 /*
  * Task state bitmask. NOTE! These bits are also
include/linux/stop_machine.h +5 -17
diff -urpN --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/dontdiff --minimal linux-2.6.18-rc4/include/linux/stop_machine.h working-2.6.18-rc4-stop_machine_no_preempt/include/linux/stop_machine.h
@@ -1,13 +1,13 @@
 #ifndef _LINUX_STOP_MACHINE
 #define _LINUX_STOP_MACHINE
-/* "Bogolock": stop the entire machine, disable interrupts.  This is a
-   very heavy lock, which is equivalent to grabbing every spinlock
-   (and more).  So the "read" side to such a lock is anything which
-   diables preeempt. */
+
+/* "Bogolock": flushes all preempted tasks, stop the entire machine,
+   disable interrupts.  This is a very heavy lock, which is equivalent
+   to grabbing every spinlock (and more).  So the "read" side to such
+   a lock is anything which doesn't sleep. */
 #include <linux/cpu.h>
 #include <asm/system.h>
 
-#if defined(CONFIG_STOP_MACHINE) && defined(CONFIG_SMP)
 /**
  * stop_machine_run: freeze the machine on all CPUs and run this function
  * @fn: the function to run
@@ -36,16 +36,4 @@ int stop_machine_run(int (*fn)(void *), 
 struct task_struct *__stop_machine_run(int (*fn)(void *), void *data,
 				       unsigned int cpu);
 
-#else
-
-static inline int stop_machine_run(int (*fn)(void *), void *data,
-				   unsigned int cpu)
-{
-	int ret;
-	local_irq_disable();
-	ret = fn(data);
-	local_irq_enable();
-	return ret;
-}
-#endif /* CONFIG_SMP */
 #endif /* _LINUX_STOP_MACHINE */
init/Kconfig +0 -7
diff -urpN --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/dontdiff --minimal linux-2.6.18-rc4/init/Kconfig working-2.6.18-rc4-stop_machine_no_preempt/init/Kconfig
@@ -502,13 +502,6 @@ config KMOD
 	  automatically: when a part of the kernel needs a module, it
 	  runs modprobe with the appropriate arguments, thereby
 	  loading the module if it is available.  If unsure, say Y.
-
-config STOP_MACHINE
-	bool
-	default y
-	depends on (SMP && MODULE_UNLOAD) || HOTPLUG_CPU
-	help
-	  Need stop_machine() primitive.
 endmenu
 
 menu "Block layer"
kernel/Makefile +1 -2
diff -urpN --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/dontdiff --minimal linux-2.6.18-rc4/kernel/Makefile working-2.6.18-rc4-stop_machine_no_preempt/kernel/Makefile
@@ -8,7 +8,7 @@ obj-y     = sched.o fork.o exec_domain.o
 	    signal.o sys.o kmod.o workqueue.o pid.o \
 	    rcupdate.o extable.o params.o posix-timers.o \
 	    kthread.o wait.o kfifo.o sys_ni.o posix-cpu-timers.o mutex.o \
-	    hrtimer.o rwsem.o
+	    hrtimer.o rwsem.o stop_machine.o
 
 obj-$(CONFIG_STACKTRACE) += stacktrace.o
 obj-y += time/
@@ -38,7 +38,6 @@ obj-$(CONFIG_KEXEC) += kexec.o
 obj-$(CONFIG_COMPAT) += compat.o
 obj-$(CONFIG_CPUSETS) += cpuset.o
 obj-$(CONFIG_IKCONFIG) += configs.o
-obj-$(CONFIG_STOP_MACHINE) += stop_machine.o
 obj-$(CONFIG_AUDIT) += audit.o auditfilter.o
 obj-$(CONFIG_AUDITSYSCALL) += auditsc.o
 obj-$(CONFIG_KPROBES) += kprobes.o
kernel/module.c +3 -3
diff -urpN --exclude TAGS -X /home/rusty/devel/kernel/kernel-patches/dontdiff --minimal linux-2.6.18-rc4/kernel/module.c working-2.6.18-rc4-stop_machine_no_preempt/kernel/module.c
@@ -498,9 +498,9 @@ static void module_unload_init(struct mo
 
 	INIT_LIST_HEAD(&mod->modules_which_use_me);
 	for (i = 0; i < NR_CPUS; i++)
-		local_set(&mod->ref[i].count, 0);
+		atomic_set(&mod->ref[i].count, 0);
 	/* Hold reference count during initialization. */
-	local_set(&mod->ref[raw_smp_processor_id()].count, 1);
+	atomic_set(&mod->ref[raw_smp_processor_id()].count, 1);
 	/* Backwards compatibility macros put refcount during init. */
 	mod->waiter = current;
 }
@@ -620,7 +620,7 @@ unsigned int module_refcount(struct modu
 	unsigned int i, total = 0;
 
 	for (i = 0; i < NR_CPUS; i++)
-		total += local_read(&mod->ref[i].count);
+		total += atomic_read(&mod->ref[i].count);
 	return total;
 }
 EXPORT_SYMBOL(module_refcount);
kernel/sched.c +43 -0

61 lines not on this page · raw message

kernel/stop_machine.c +44 -7

85 lines not on this page · raw message

Signature · 1 line
Help! Save Australia from the worst of the DMCA: http://linux.org.au/law
#4 lore raw
Quoted 14 lines · Rusty Russell (on Mon, 28 Aug 2006 16:17:11 +1000) wrote:
Quoted 5 lines · Keith Owens
Quoted 4 lines · Rusty Russell (on Mon, 28 Aug 2006 09:38:55 +1000) wrote:
Quoted 2 lines · Keith Owens

I cannot convince myself that stopmachine() is preempt safe. What prevents this race with CONFIG_PREEMPT=y?

Quoted 7 lines
Quoted 1 line

Nothing. Read side is preempt_disable. Write side is stopmachine.

That is very worrying. The whole point of stopmachine is to get all cpus to a known state with no locally cached global data, so the caller of stopmachine can safely fiddle with some global data (like updating the module lists). But CONFIG_PREEMPT defeats this and turns any code that relies on stopmachine into a race.

Quoted 5 lines

Hi Keith,

Do not panic: this is not a bug, and was never how stop_machine was to
be used. try_module_get() disables preemption, and you are supposed to disable preemption

Disabling preemption only guarantees that the current task will not be preempted. It says nothing about the state of tasks that were already running on the cpus when stopmachine was called. It is these tasks that were already running and were preempted by stopmachine that have to be flushed before stopmachine can continue. Remember that this is the race:

cpu 0 cpu 1
stop_machine()
Process <n> reads a global resource
do_stop()
kernel_thread(stopmachine, 1)
Process <n> is preempted stopmachine() runs on cpu 1 STOPMACHINE_PREPARE STOPMACHINE_DISABLE_IRQ
do_stop() calls smdata->fn
smdata->fn changes global data
restart_machine()
STOPMACHINE_EXIT stopmachine() exits Scheduler resumes process <n> The global resource is out of sync

Quoted 2 lines

(or take cpu_hotplug_lock) when relying on
cpu_online_map.

There is a lot of code in the kernel that runs cpu_online_map without taking any locks and without disabling preemption. Obviously we do not want all that code to lock or disable preemption, it will kill scalability. The lack of locking on the read side means that changes to cpu_online_map have to be done under stopmachine, which brings in the race again.

I will have a look at your scheduler patch and see if it fixes the race.

#5 lore raw
Quoted 4 lines · Keith Owens

There is a lot of code in the kernel that runs cpu_online_map without taking any locks and without disabling preemption. Obviously we do not want all that code to lock or disable preemption, it will kill scalability.

There is actually not much code which should use cpu_online_map. Code which does must be careful: you generally need to think about handling cpu hotplug notifiers as well as the map changing underneath you.

Doing a brief audit, ignoring the already-acknowledged cpufreq code and arch-specifics, I can see these cases which seem suspicious:

./drivers/acpi/processor_core.c:acpi_processor_handle_eject()
- I assume this is relying on some other mechanism so the cpu doesn't get onlined?
- A couple of other num_online_cpus() there in ACPI might need a rethink for hotplug CPU though.

./kernel/irq/proc.c: irq_affinity_write_proc()
- seems complicated, but I think migration.c handles when cpus gone offline?

./drivers/oprofile/cpu_buffer.c:
- needs to handle hotplug cpus (or just say don't do that?)

./drivers/infiniband/hw/ipath/ipath_file_ops.c:
- seems to be using num_online_cpus as a really poor heuristic, and incorrectly (for i = 0; i < num_online_cpus(); i++) <-- i is not a valid CPU number!).

./kernel/power/main.c:suspend_prepare()
- suspicious, code here, too.

./net/core/dev.c: net_dma_rebalance()
- This is a heuristic, which may be OK.
./net/core/dev.c: softnet_get_online()
- It'd be nice if net/dev/core.c used cpu_possible() not cpu_online() to report stats, so they don't get lost from offlined CPUs.

./net/core/pktgen.c: pg_init()
- Assumes no CPU plugging, but is a pretty specialized driver.

(Other uses get away with being in initcalls, or on platforms without hotplug CPU).

Disappointingly, none of these would be fixed by changing the semantics of stop_machine; they rely on the online cpus and must take action when they change, whether they are reading the online_cpu_map at the time or not.

Rusty.

Signature · 1 line
Help! Save Australia from the worst of the DMCA: http://linux.org.au/law