Skip to contentSkip to conversation

stop_machine: Remove cpu swap from stop_two_cpus

PATCH In review Isaac J. Manjarres 4 participants 4 messages Jun 26, 2018 – Jun 28, 2018

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 stop_machine: Remove cpu swap from stop_two_cpus

When invoking migrate_swap(), stop_two_cpus() swaps the source and destination CPU IDs if the destination CPU ID is greater than the source CPU ID. This leads to the following race condition:

The source CPU invokes migrate_swap and sets itself as the source CPU, and sets the destination CPU to another CPU, such that the CPU ID of the destination CPU is greater than that of the source CPU ID, and invokes stop_two_cpus(cpu1=destination CPU, cpu2=source CPU,...) Now, stop_two_cpus sees that the destination CPU ID is greater than the source CPU ID, and performs the swap, so that cpu1=source CPU, and cpu2=destination CPU.

The source CPU calls cpu_stop_queue_two_works(), with cpu1 as the source CPU, and cpu2 as the destination CPU. When adding the stopper threads to the wake queue used in this function, the source CPU stopper thread is added first, and the destination CPU stopper thread is added last.

When wake_up_q() is invoked to wake the stopper threads, the threads are woken up in the order that they are queued in, so the source CPU's stopper thread is woken up first, and it preempts the thread running on the source CPU.

The stopper thread will then execute on the source CPU, disable preemption, and begin executing multi_cpu_stop() and wait for an ack from the destination CPU's stopper thread, with preemption still disabled. Since the worker thread that woke up the stopper thread on the source CPU is affine to the source CPU, and preemption is disabled on the source CPU, that thread will never run to dequeue the destination CPU's stopper thread from the wake queue, and thus, the destination CPU's stopper thread will never run, causing the source CPU's stopper thread to wait forever, and stall.

Remove CPU ID swapping in stop_two_cpus() so that the source CPU's stopper thread is added to the wake queue last, so that the source CPU's stopper thread is woken up last, ensuring that all other threads that it depends on are woken up before it runs.

---
 kernel/stop_machine.c | 2 --
 1 file changed, 2 deletions(-)
kernel/stop_machine.c +0 -2
index f89014a..d10d633 100644
@@ -307,8 +307,6 @@ int stop_two_cpus(unsigned int cpu1, unsigned int cpu2, cpu_stop_fn_t fn, void *
 	cpu_stop_init_done(&done, 2);
 	set_state(&msdata, MULTI_STOP_PREPARE);
 
-	if (cpu1 > cpu2)
-		swap(cpu1, cpu2);
 	if (cpu_stop_queue_two_works(cpu1, &work1, cpu2, &work2))
 		return -ENOENT;
 
Signature · 2 lines
The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum,
a Linux Foundation Collaborative Project
#1 lore raw
Quoted 5 lines · Isaac J. Manjarres

Remove CPU ID swapping in stop_two_cpus() so that the source CPU's stopper thread is added to the wake queue last, so that the source CPU's stopper thread is woken up last, ensuring that all other threads that it depends on are woken up before it runs.

You can't do that because you could deadlock while locking the stoper lock.
Couldn't you swap cpu1+cpu2 and work1+work2?

kernel/stop_machine.c int stop_two_cpus(unsigned int cpu1, unsigned int cpu2, cpu_stop_fn_t fn, void * · line 312

Quoted 13 lines
kernel/stop_machine.c +0 -2
index f89014a..d10d633 100644
@@ -307,8 +307,6 @@ int stop_two_cpus(unsigned int cpu1, unsigned int cpu2, cpu_stop_fn_t fn, void *
 	cpu_stop_init_done(&done, 2);
 	set_state(&msdata, MULTI_STOP_PREPARE);
 
-	if (cpu1 > cpu2)
-		swap(cpu1, cpu2);
 	if (cpu_stop_queue_two_works(cpu1, &work1, cpu2, &work2))
 		return -ENOENT;
 

Sebastian

#2 lore raw
Quoted 9 lines · Sebastian Andrzej Siewior
Quoted 5 lines · Isaac J. Manjarres

Remove CPU ID swapping in stop_two_cpus() so that the source CPU's stopper thread is added to the wake queue last, so that the source CPU's stopper thread is woken up last, ensuring that all other threads that it depends on are woken up before it runs.

You can't do that because you could deadlock while locking the stoper lock.

<Prasad> Without this change boot up issues are observed with Linux 4.14.52. One of the core is executing the stopper thread after wake_up_q() in cpu_stop_queue_two_works() function, without waking up other cores stopper thread. We see this issue 100% on device boot up with Linux 4.14.52.

Could you please explain bit more how the deadlock occurs? static int cpu_stop_queue_two_works(int cpu1, struct cpu_stop_work *work1,
int cpu2, struct cpu_stop_work
*work2)

{
        struct cpu_stopper *stopper1 = per_cpu_ptr(&cpu_stopper, cpu1);
        struct cpu_stopper *stopper2 = per_cpu_ptr(&cpu_stopper, cpu2);
        DEFINE_WAKE_Q(wakeq);
        int err;
retry:
        raw_spin_lock_irq(&stopper1->lock);
        raw_spin_lock_nested(&stopper2->lock, SINGLE_DEPTH_NESTING);

<SNIP>

I think, you are suggesting to switch the locking sequence too. stopper2->lock and stopper1->lock.

could you please share the test case to stress this code flow?

Quoted 1 line

Couldn't you swap cpu1+cpu2 and work1+work2?

<Prasad> Work1 and work2 are having same data contents.

Quoted 17 lines
Quoted 8 lines
kernel/stop_machine.c +0 -0
index f89014a..d10d633 100644
@@ -307,8 +307,6 @@ int stop_two_cpus(unsigned int cpu1, unsigned int 

cpu2, cpu_stop_fn_t fn, void *

kernel/stop_machine.c int stop_two_cpus(unsigned int cpu1, unsigned int cpu2, cpu_stop_fn_t fn, void * · line 311

Quoted 7 lines
kernel/stop_machine.c +0 -2
 	cpu_stop_init_done(&done, 2);
 	set_state(&msdata, MULTI_STOP_PREPARE);
 
-	if (cpu1 > cpu2)
-		swap(cpu1, cpu2);
 	if (cpu_stop_queue_two_works(cpu1, &work1, cpu2, &work2))
 		return -ENOENT;

Sebastian

Signature · 2 lines
The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum,
Linux Foundation Collaborative Project
#3 lore raw
In reply to Isaac J. Manjarres
Quoted 54 lines · Isaac J. Manjarres

When invoking migrate_swap(), stop_two_cpus() swaps the source and destination CPU IDs if the destination CPU ID is greater than the source CPU ID. This leads to the following race condition:

The source CPU invokes migrate_swap and sets itself as the source CPU, and sets the destination CPU to another CPU, such that the CPU ID of the destination CPU is greater than that of the source CPU ID, and invokes stop_two_cpus(cpu1=destination CPU, cpu2=source CPU,...) Now, stop_two_cpus sees that the destination CPU ID is greater than the source CPU ID, and performs the swap, so that cpu1=source CPU, and cpu2=destination CPU.

The source CPU calls cpu_stop_queue_two_works(), with cpu1 as the source CPU, and cpu2 as the destination CPU. When adding the stopper threads to the wake queue used in this function, the source CPU stopper thread is added first, and the destination CPU stopper thread is added last.

When wake_up_q() is invoked to wake the stopper threads, the threads are woken up in the order that they are queued in, so the source CPU's stopper thread is woken up first, and it preempts the thread running on the source CPU.

The stopper thread will then execute on the source CPU, disable preemption, and begin executing multi_cpu_stop() and wait for an ack from the destination CPU's stopper thread, with preemption still disabled. Since the worker thread that woke up the stopper thread on the source CPU is affine to the source CPU, and preemption is disabled on the source CPU, that thread will never run to dequeue the destination CPU's stopper thread from the wake queue, and thus, the destination CPU's stopper thread will never run, causing the source CPU's stopper thread to wait forever, and stall.

Remove CPU ID swapping in stop_two_cpus() so that the source CPU's stopper thread is added to the wake queue last, so that the source CPU's stopper thread is woken up last, ensuring that all other threads that it depends on are woken up before it runs.

---
 kernel/stop_machine.c | 2 --
 1 file changed, 2 deletions(-)
kernel/stop_machine.c +0 -0
index f89014a..d10d633 100644

kernel/stop_machine.c int stop_two_cpus(unsigned int cpu1, unsigned int cpu2, cpu_stop_fn_t fn, void * · line 312

Quoted 8 lines
kernel/stop_machine.c +0 -2
@@ -307,8 +307,6 @@ int stop_two_cpus(unsigned int cpu1, unsigned int cpu2, cpu_stop_fn_t fn, void *
 	cpu_stop_init_done(&done, 2);
 	set_state(&msdata, MULTI_STOP_PREPARE);
 
-	if (cpu1 > cpu2)
-		swap(cpu1, cpu2);
 	if (cpu_stop_queue_two_works(cpu1, &work1, cpu2, &work2))
 		return -ENOENT;
 

Nested spinlocks must be taken in the same order everywhere. If you don't it can create circular dependency which leads to deadlock. Sebastian already pointed it out.

For example,

CPU2: stop_two_cpus(CPU0, CPU1)
CPU3: stop_two_cpus(CPU1, CPU0)

CPU2 may acquire CPU0 lock and waiting for CPU1 lock. At the same time, CPU3 which acquired CPU1 lock could be waiting for CPU0 lock. They stuck forever.

Coming to the original problem described in the changelog, it is happening due to not waking stopper threads atomically in cpu_stop_queue_two_works().

Can you check if the below patch (not tested :-)) helps?

kernel/stop_machine.c +5 -1
index f89014a..1ff523d 100644
@@ -270,7 +270,11 @@ static int cpu_stop_queue_two_works(int cpu1, struct cpu_stop_work *work1,
 		goto retry;
 	}
 
-	wake_up_q(&wakeq);
+	if (!err) {
+		preempt_disable();
+		wake_up_q(&wakeq);
+		preempt_enable();
+	}
 
 	return err;
 }
Signature · 2 lines
Qualcomm India Private Limited, on behalf of Qualcomm Innovation Center, Inc.
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, a Linux Foundation Collaborative Project.