Skip to contentSkip to conversation

stop_machine: Fix deadlock between multiple stop_two_cpus()

RFC PATCH In review Peter Zijlstra 3 participants 3 messages Jun 5, 2015 – Jun 19, 2015 Locking primitives

lore
Share & tools
lore

Peter Zijlstra

author maintainer
#0 lore raw

RFC PATCH 1/1 stop_machine: Fix deadlock between multiple stop_two_cpus()

Jiri reported a machine stuck in multi_cpu_stop() with migrate_swap_stop() as function and with the following src,dst cpu
pairs: {11, 4} {13, 11} { 4, 13}

                        4       11      13

cpuM: queue(4 ,13)

                        *Ma

cpuN: queue(13,11)
*N Na
*M Mb
cpuO: queue(11, 4)

                        *O      Oa
                                *Nb
                        *Ob

Where *X denotes the cpu running the queueing of cpu-X and X[ab] denotes the first/second queued work.

You'll observe the top of the workqueue for each cpu: 4,11,13 to be work from cpus: M, O, N resp. IOW. deadlock.

Do away with the queueing trickery and introduce lg_double_lock() to lock both CPUs and fully serialize the stop_two_cpus() callers instead of the partial (and buggy) serialization we have now.

Completely untested..

---
 include/linux/lglock.h  |  5 +++++
 kernel/locking/lglock.c | 22 ++++++++++++++++++++++
 kernel/stop_machine.c   | 41 +++++------------------------------------
 3 files changed, 32 insertions(+), 36 deletions(-)
include/linux/lglock.h +5 -0
index 0081f000e34b..c92ebd100d9b 100644
@@ -52,10 +52,15 @@ struct lglock {
 	static struct lglock name = { .lock = &name ## _lock }
 
 void lg_lock_init(struct lglock *lg, char *name);
+
 void lg_local_lock(struct lglock *lg);
 void lg_local_unlock(struct lglock *lg);
 void lg_local_lock_cpu(struct lglock *lg, int cpu);
 void lg_local_unlock_cpu(struct lglock *lg, int cpu);
+
+void lg_double_lock(struct lglock *lg, int cpu1, int cpu2);
+void lg_double_unlock(struct lglock *lg, int cpu1, int cpu2);
+
 void lg_global_lock(struct lglock *lg);
 void lg_global_unlock(struct lglock *lg);
 
kernel/locking/lglock.c +22 -0
index 86ae2aebf004..951cfcd10b4a 100644
@@ -60,6 +60,28 @@ void lg_local_unlock_cpu(struct lglock *lg, int cpu)
 }
 EXPORT_SYMBOL(lg_local_unlock_cpu);
 
+void lg_double_lock(struct lglock *lg, int cpu1, int cpu2)
+{
+	BUG_ON(cpu1 == cpu2);
+
+	/* lock in cpu order, just like lg_global_lock */
+	if (cpu2 < cpu1)
+		swap(cpu1, cpu2);
+
+	preempt_disable();
+	lock_acquire_shared(&lg->lock_dep_map, 0, 0, NULL, _RET_IP_);
+	arch_spin_lock(per_cpu_ptr(lg->lock, cpu1));
+	arch_spin_lock(per_cpu_ptr(lg->lock, cpu2));
+}
+
+void lg_double_unlock(struct lglock *lg, int cpu1, int cpu2)
+{
+	lock_release(&lg->lock_dep_map, 1, _RET_IP_);
+	arch_spin_unlock(per_cpu_ptr(lg->lock, cpu1));
+	arch_spin_unlock(per_cpu_ptr(lg->lock, cpu2));
+	preempt_enable();
+}
+
 void lg_global_lock(struct lglock *lg)
 {
 	int i;
kernel/stop_machine.c +5 -36

59 lines not on this page · raw message

#1 lore raw
Quoted 23 lines · Peter Zijlstra

Jiri reported a machine stuck in multi_cpu_stop() with migrate_swap_stop() as function and with the following src,dst cpu
pairs: {11, 4} {13, 11} { 4, 13}

                        4       11      13

cpuM: queue(4 ,13)

                        *Ma

cpuN: queue(13,11)
*N Na
*M Mb
cpuO: queue(11, 4)

                        *O      Oa
                                *Nb
                        *Ob

Where *X denotes the cpu running the queueing of cpu-X and X[ab] denotes the first/second queued work.

You'll observe the top of the workqueue for each cpu: 4,11,13 to be work from cpus: M, O, N resp. IOW. deadlock.

Quoted 8 lines

Do away with the queueing trickery and introduce lg_double_lock() to lock both CPUs and fully serialize the stop_two_cpus() callers instead of the partial (and buggy) serialization we have now.

Completely untested..

Certainly looks like it would work.

I suspect we should probably apply this patch after some basic testing, since the race is so incredibly hard to reproduce.

Signature · 1 line
All rights reversed
#2 lore raw

[tip:sched/core] sched/stop_machine: Fix deadlock between multiple stop_two_cpus()

In reply to Peter Zijlstra
sched/stop_machine: Fix deadlock between multiple stop_two_cpus()
Commit-ID:  b17718d02f54b90978d0e0146368b512b11c3e84
Gitweb:     http://git.kernel.org/tip/b17718d02f54b90978d0e0146368b512b11c3e84
Author:     Peter Zijlstra <[email protected]>
AuthorDate: Fri, 5 Jun 2015 17:30:23 +0200
Committer:  Ingo Molnar <[email protected]>
CommitDate: Fri, 19 Jun 2015 10:03:12 +0200

sched/stop_machine: Fix deadlock between multiple stop_two_cpus()

Jiri reported a machine stuck in multi_cpu_stop() with migrate_swap_stop() as function and with the following src,dst cpu
pairs: {11, 4} {13, 11} { 4, 13}

                        4       11      13

cpuM: queue(4 ,13)

                        *Ma

cpuN: queue(13,11)
*N Na
*M Mb
cpuO: queue(11, 4)

                        *O      Oa
                                *Nb
                        *Ob

Where *X denotes the cpu running the queueing of cpu-X and X[ab] denotes the first/second queued work.

You'll observe the top of the workqueue for each cpu: 4,11,13 to be work from cpus: M, O, N resp. IOW. deadlock.

Do away with the queueing trickery and introduce lg_double_lock() to lock both CPUs and fully serialize the stop_two_cpus() callers instead of the partial (and buggy) serialization we have now.

Cc Andrew Morton <[email protected]>
Cc Borislav Petkov <[email protected]>
Cc H. Peter Anvin <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Oleg Nesterov <[email protected]>
Cc Peter Zijlstra <[email protected]>
Cc Rik van Riel <[email protected]>
Cc Thomas Gleixner <[email protected]>
---
 include/linux/lglock.h  |  5 +++++
 kernel/locking/lglock.c | 22 ++++++++++++++++++++++
 kernel/stop_machine.c   | 42 +++++-------------------------------------
 3 files changed, 32 insertions(+), 37 deletions(-)
include/linux/lglock.h +5 -0
index 0081f00..c92ebd1 100644
@@ -52,10 +52,15 @@ struct lglock {
 	static struct lglock name = { .lock = &name ## _lock }
 
 void lg_lock_init(struct lglock *lg, char *name);
+
 void lg_local_lock(struct lglock *lg);
 void lg_local_unlock(struct lglock *lg);
 void lg_local_lock_cpu(struct lglock *lg, int cpu);
 void lg_local_unlock_cpu(struct lglock *lg, int cpu);
+
+void lg_double_lock(struct lglock *lg, int cpu1, int cpu2);
+void lg_double_unlock(struct lglock *lg, int cpu1, int cpu2);
+
 void lg_global_lock(struct lglock *lg);
 void lg_global_unlock(struct lglock *lg);
 
kernel/locking/lglock.c +22 -0
index 86ae2ae..951cfcd 100644
@@ -60,6 +60,28 @@ void lg_local_unlock_cpu(struct lglock *lg, int cpu)
 }
 EXPORT_SYMBOL(lg_local_unlock_cpu);
 
+void lg_double_lock(struct lglock *lg, int cpu1, int cpu2)
+{
+	BUG_ON(cpu1 == cpu2);
+
+	/* lock in cpu order, just like lg_global_lock */
+	if (cpu2 < cpu1)
+		swap(cpu1, cpu2);
+
+	preempt_disable();
+	lock_acquire_shared(&lg->lock_dep_map, 0, 0, NULL, _RET_IP_);
+	arch_spin_lock(per_cpu_ptr(lg->lock, cpu1));
+	arch_spin_lock(per_cpu_ptr(lg->lock, cpu2));
+}
+
+void lg_double_unlock(struct lglock *lg, int cpu1, int cpu2)
+{
+	lock_release(&lg->lock_dep_map, 1, _RET_IP_);
+	arch_spin_unlock(per_cpu_ptr(lg->lock, cpu1));
+	arch_spin_unlock(per_cpu_ptr(lg->lock, cpu2));
+	preempt_enable();
+}
+
 void lg_global_lock(struct lglock *lg)
 {
 	int i;
kernel/stop_machine.c +5 -37

66 lines not on this page · raw message

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in Please read the FAQ at http://www.tux.org/lkml/