Skip to contentSkip to conversation

cpuhotplug: introduce try_get_online_cpus()

PATCH In review Lai Jiangshan 4 participants 6 messages May 29, 2009 – Jun 4, 2009 CPU hotplug

lore
Share & tools
lore
#0 lore raw

PATCH 2/2 cpuhotplug: introduce try_get_online_cpus()

get_online_cpus() is a typically coarsely granular lock. It's a source of ABBA deadlock.

Thanks to the CPU notifiers, Some subsystem's global lock will be required after cpu_hotplug.rwlock. Subsystem's global lock is coarsely granular lock too, thus a lot's of lock in kernel should be required after cpu_hotplug.rwlock(if we need cpu_hotplug.rwlock held too)

Otherwise it may come to a ABBA deadlock like this:

thread 1                                      |        thread 2
_cpu_down()                                   |  Lock a-kernel-lock.
  cpu_hotplug_begin()                         |
    down_write(&cpu_hotplug.rwlock)           |
  __raw_notifier_call_chain(CPU_DOWN_PREPARE) |  get_online_cpus()

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

But CPU online/offline are happened very rarely, get_online_cpus() returns success quickly in all probability.
So it's an asinine behavior that get_online_cpus() is not allowed to be required after we had held "a-kernel-lock".

To dispel the ABBA deadlock, this patch introduces try_get_online_cpus(). It returns fail very rarely. It gives the caller a chance to select an alternative way to finish works, instead of sleeping or deadlock.

---

include/linux/cpu.h +2 -0
index 2643d84..98f5c4b 100644
@@ -104,6 +104,7 @@ extern struct sysdev_class cpu_sysdev_class;
 
 extern void get_online_cpus(void);
 extern void put_online_cpus(void);
+extern int try_get_online_cpus(void);
 #define hotcpu_notifier(fn, pri) {				\
 	static struct notifier_block fn##_nb __cpuinitdata =	\
 		{ .notifier_call = fn, .priority = pri };	\
@@ -117,6 +118,7 @@ int cpu_down(unsigned int cpu);
 
 #define get_online_cpus()	do { } while (0)
 #define put_online_cpus()	do { } while (0)
+#define try_get_online_cpus()	(1)
 #define hotcpu_notifier(fn, pri)	do { (void)(fn); } while (0)
 /* These aren't inline functions due to a GCC bug. */
 #define register_hotcpu_notifier(nb)	({ (void)(nb); 0; })
kernel/cpu.c +9 -0
index 62198ec..e948f19 100644
@@ -66,6 +66,15 @@ void put_online_cpus(void)
 }
 EXPORT_SYMBOL_GPL(put_online_cpus);
 
+int try_get_online_cpus(void)
+{
+	might_sleep();
+	if (cpu_hotplug.active_writer == current)
+		return 1;
+	return down_read_trylock(&cpu_hotplug.rwlock);
+
+}
+EXPORT_SYMBOL_GPL(try_get_online_cpus);
 #endif	/* CONFIG_HOTPLUG_CPU */
 
 /*
#1 lore raw
Quoted 26 lines · On Fri, 29 May 2009 16:29:34 +0800 Lai Jiangshan <[email protected]> wrote:

get_online_cpus() is a typically coarsely granular lock. It's a source of ABBA deadlock.

Thanks to the CPU notifiers, Some subsystem's global lock will be required after cpu_hotplug.rwlock. Subsystem's global lock is coarsely granular lock too, thus a lot's of lock in kernel should be required after cpu_hotplug.rwlock(if we need cpu_hotplug.rwlock held too)

Otherwise it may come to a ABBA deadlock like this:

thread 1                                      |        thread 2
_cpu_down()                                   |  Lock a-kernel-lock.
  cpu_hotplug_begin()                         |
    down_write(&cpu_hotplug.rwlock)           |
  __raw_notifier_call_chain(CPU_DOWN_PREPARE) |  get_online_cpus()

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

But CPU online/offline are happened very rarely, get_online_cpus() returns success quickly in all probability.
So it's an asinine behavior that get_online_cpus() is not allowed to be required after we had held "a-kernel-lock".

Quoted 5 lines

To dispel the ABBA deadlock, this patch introduces try_get_online_cpus(). It returns fail very rarely. It gives the caller a chance to select an alternative way to finish works, instead of sleeping or deadlock.

We really really really don't want to add new trylocks. They're nasty things, requiring that callers provide alternative fallback code paths which are really hard to test. The original code writer _might_ have performed runtime testing of the contention path when originally writing the patch, but after that nobody will tesst that path at all and there's a good chance that it will become broken over time and nobody will know about it.

I assume that one advantage of your rwlock conversion patch is that code paths such as the above are now checked by lockdep, yes? And this is how you discovered the bug in some subsystem whcih you didn't tell us about?

Quoted 28 lines

---

include/linux/cpu.h +2 -0
index 2643d84..98f5c4b 100644
@@ -104,6 +104,7 @@ extern struct sysdev_class cpu_sysdev_class;
 
 extern void get_online_cpus(void);
 extern void put_online_cpus(void);
+extern int try_get_online_cpus(void);
 #define hotcpu_notifier(fn, pri) {				\
 	static struct notifier_block fn##_nb __cpuinitdata =	\
 		{ .notifier_call = fn, .priority = pri };	\
@@ -117,6 +118,7 @@ int cpu_down(unsigned int cpu);
 
 #define get_online_cpus()	do { } while (0)
 #define put_online_cpus()	do { } while (0)
+#define try_get_online_cpus()	(1)
 #define hotcpu_notifier(fn, pri)	do { (void)(fn); } while (0)
 /* These aren't inline functions due to a GCC bug. */
 #define register_hotcpu_notifier(nb)	({ (void)(nb); 0; })
kernel/cpu.c +0 -0
index 62198ec..e948f19 100644
@@ -66,6 +66,15 @@ void put_online_cpus(void)
 }
 EXPORT_SYMBOL_GPL(put_online_cpus);

kernel/cpu.c void put_online_cpus(void) · line 77

Quoted 10 lines
kernel/cpu.c +9 -0
 
+int try_get_online_cpus(void)
+{
+	might_sleep();
+	if (cpu_hotplug.active_writer == current)
+		return 1;
+	return down_read_trylock(&cpu_hotplug.rwlock);
+
+}
+EXPORT_SYMBOL_GPL(try_get_online_cpus);

It's strange to add a might_sleep() to a function which doesn't sleep.

The patch adds no callers to this function. This is significant because it would be quite interesting to find out which subsystem(s) you've found to have this deadlock. I do think that we should look at alternative (non-trylocky) ways of fixing them.

#2 lore raw
Quoted 30 lines · Andrew Morton
Quoted 30 lines

---

include/linux/cpu.h +2 -0
index 2643d84..98f5c4b 100644
@@ -104,6 +104,7 @@ extern struct sysdev_class cpu_sysdev_class;
 
 extern void get_online_cpus(void);
 extern void put_online_cpus(void);
+extern int try_get_online_cpus(void);
 #define hotcpu_notifier(fn, pri) {				\
 	static struct notifier_block fn##_nb __cpuinitdata =	\
 		{ .notifier_call = fn, .priority = pri };	\
@@ -117,6 +118,7 @@ int cpu_down(unsigned int cpu);
 
 #define get_online_cpus()	do { } while (0)
 #define put_online_cpus()	do { } while (0)
+#define try_get_online_cpus()	(1)
 #define hotcpu_notifier(fn, pri)	do { (void)(fn); } while (0)
 /* These aren't inline functions due to a GCC bug. */
 #define register_hotcpu_notifier(nb)	({ (void)(nb); 0; })
kernel/cpu.c +0 -0
index 62198ec..e948f19 100644
@@ -66,6 +66,15 @@ void put_online_cpus(void)
 }
 EXPORT_SYMBOL_GPL(put_online_cpus);
 
Quoted 11 lines

kernel/cpu.c void put_online_cpus(void) · line 77

Quoted 9 lines
kernel/cpu.c +9 -0
+int try_get_online_cpus(void)
+{
+	might_sleep();
+	if (cpu_hotplug.active_writer == current)
+		return 1;
+	return down_read_trylock(&cpu_hotplug.rwlock);
+
+}
+EXPORT_SYMBOL_GPL(try_get_online_cpus);

It's strange to add a might_sleep() to a function which doesn't sleep.

It might sleep indeed. I prefer to add a might_sleep()/cond_sched() for a sleepable function.

Quoted 6 lines

The patch adds no callers to this function. This is significant because it would be quite interesting to find out which subsystem(s) you've found to have this deadlock. I do think that we should look at alternative (non-trylocky) ways of fixing them.

This problem exist in cgroup/cpuset. and Max Krasnyansky fix it:
(non-trylocky way)
*
* The rebuild_sched_domains() and partition_sched_domains()
* routines must nest cgroup_lock() inside get_online_cpus(),
* but such cpuset changes as these must nest that locking the
* other way, holding cgroup_lock() for much of the code. *
* So in order to avoid an ABBA deadlock, the cpuset code handling
* these user changes delegates the actual sched domain rebuilding
* to a separate workqueue thread, which ends up processing the
* above do_rebuild_sched_domains() function.
*/
static void async_rebuild_sched_domains(void)

{
	queue_work(cpuset_wq, &rebuild_sched_domains_work);
}

get_online_cpus() is so a coarsely granular lock, and try_get_online_cpus() fails rarely. The kernel indeed needs try_get_online_cpus().

Paul will use it:
http://lkml.org/lkml/2009/5/22/332

Lai

#3 lore raw
In reply to Andrew Morton
Quoted 2 lines · Andrew Morton

I do think that we should look at
alternative (non-trylocky) ways of fixing them.

Speculating: we could add a "keep_cpu()" (FIXME: improve name) which is kind of like get_cpu() only doesn't disable preemption and only stops *this* cpu from going down.

Not sure where that gets us, but if someone's going to dig deep into this it might help.

Thanks,
Rusty.

#4 lore raw
Quoted 10 lines · Rusty Russell
Quoted 2 lines · Andrew Morton

I do think that we should look at
alternative (non-trylocky) ways of fixing them.

Speculating: we could add a "keep_cpu()" (FIXME: improve name) which is kind of like get_cpu() only doesn't disable preemption and only stops *this* cpu from going down.

Not sure where that gets us, but if someone's going to dig deep into this it might help.

I have been beating up on the approach of disabling preemption to pin down a single CPU, and although it is working, it is no faster than simply doing get_online_cpus() and it is much much more subtle and complex. I am not sure that I have all the races properly accounted for, and I am failing to see the point of having something quite this ugly in the kernel when much simpler alternatives exist.

The main vulnerability is the possibility that someone will invoke synchroniize_rcu_expedited() while holding a mutex that is also acquired in a CPU-hotplug notifier, as Lai noted. But this is easily handled given a primitive that will say whether the current CPU is executing in a CPU-hotplug notifier. This primitive is permitted to sometimes mistakenly say that the current CPU is executing in a CPU-hotplug notifier when it is not (as long as it doesn't do so too often), but not vice versa.

One way to implement this would be to have such a primitive simply say whether or not a CPU-hotplug operation is currently in effect. Yes, this is racy, but not when it matters -- you cannot possibly exit a CPU-hotplug operation while executing in a CPU-hotplug notifier. For example, the following exported from kernel/cpu.c would work just fine:

	bool cpu_hotplug_in_progress(void)
	{
		return cpu_hotplug.active_writer != NULL;
	}

I believe that we should be OK moving forward with an updated version of
http://lkml.org/lkml/2009/5/22/332 even without the deadlock avoidance. Having the deadlock avoidance would be better, of course, so I will use something like the above on the next patch.

Thoughts?

Thanx, Paul

#5 lore raw
Quoted 38 lines · Paul E. McKenney
Quoted 10 lines · Rusty Russell
Quoted 2 lines · Andrew Morton

I do think that we should look at
alternative (non-trylocky) ways of fixing them.

Speculating: we could add a "keep_cpu()" (FIXME: improve name) which is kind of like get_cpu() only doesn't disable preemption and only stops *this* cpu from going down.

Not sure where that gets us, but if someone's going to dig deep into this it might help.

I have been beating up on the approach of disabling preemption to pin down a single CPU, and although it is working, it is no faster than simply doing get_online_cpus() and it is much much more subtle and complex. I am not sure that I have all the races properly accounted for, and I am failing to see the point of having something quite this ugly in the kernel when much simpler alternatives exist.

The main vulnerability is the possibility that someone will invoke synchroniize_rcu_expedited() while holding a mutex that is also acquired in a CPU-hotplug notifier, as Lai noted. But this is easily handled given a primitive that will say whether the current CPU is executing in a CPU-hotplug notifier. This primitive is permitted to sometimes mistakenly say that the current CPU is executing in a CPU-hotplug notifier when it is not (as long as it doesn't do so too often), but not vice versa.

One way to implement this would be to have such a primitive simply say whether or not a CPU-hotplug operation is currently in effect. Yes, this is racy, but not when it matters -- you cannot possibly exit a CPU-hotplug operation while executing in a CPU-hotplug notifier. For example, the following exported from kernel/cpu.c would work just fine:

	bool cpu_hotplug_in_progress(void)
	{
		return cpu_hotplug.active_writer != NULL;
	}
Quoted 4 lines

I believe that we should be OK moving forward with an updated version of
http://lkml.org/lkml/2009/5/22/332 even without the deadlock avoidance. Having the deadlock avoidance would be better, of course, so I will use something like the above on the next patch.

Of course, the above does not actually solve the deadlock, instead merely making it less likely to occur. I have absolutely no idea what I was thinking!

Back to try_get_online_cpus().

Thanx, Paul