Skip to contentSkip to conversation

CPU hotplug: active_writer not woken up in some cases - deadlock

PATCH Superseded David Hildenbrand 3 participants 8 messages Dec 8, 2014 – Dec 9, 2014 CPU hotplug

v2 of 5 Superseded Latest is v5 →

lore
Share & tools
lore
#0 lore raw

PATCH v2 1/1 CPU hotplug: active_writer not woken up in some cases - deadlock

Commit b2c4623dcd07 ("rcu: More on deadlock between CPU hotplug and expedited grace periods") introduced another problem that can easily be reproduced by starting/stopping cpus in a loop.

E.g.:
for i in seq 5000; do
echo 1 > /sys/devices/system/cpu/cpu1/online echo 0 > /sys/devices/system/cpu/cpu1/online
done

Will result in:

  INFO: task /cpu_start_stop:1 blocked for more than 120 seconds.
  Call Trace:
  ([<00000000006a028e>] __schedule+0x406/0x91c)
   [<0000000000130f60>] cpu_hotplug_begin+0xd0/0xd4
   [<0000000000130ff6>] _cpu_up+0x3e/0x1c4
   [<0000000000131232>] cpu_up+0xb6/0xd4
   [<00000000004a5720>] device_online+0x80/0xc0
   [<00000000004a57f0>] online_store+0x90/0xb0
  ...

And a deadlock.

Problem is that if the last ref in put_online_cpus() can't get the cpu_hotplug.lock the puts_pending count is incremented, but a sleeping active_writer might never be woken up, therefore never exiting the loop in cpu_hotplug_begin().

This quick fix wakes up the active_writer proactively. The writer already goes back to sleep if the ref count isn't already down to 0, so this should be fine. Also move setting of TASK_UNINTERRUPTIBLE in cpu_hotplug_begin() above the check, so we won't lose any wakeups when racing with put_online_cpus().

Can't reproduce it with this fix.

---
 kernel/cpu.c | 12 ++++++++++--
 1 file changed, 10 insertions(+), 2 deletions(-)
kernel/cpu.c +10 -2
index 90a3d01..1f50c06 100644
@@ -113,10 +113,16 @@ EXPORT_SYMBOL_GPL(try_get_online_cpus);
 
 void put_online_cpus(void)
 {
+	struct task_struct *active_writer;
+
 	if (cpu_hotplug.active_writer == current)
 		return;
 	if (!mutex_trylock(&cpu_hotplug.lock)) {
 		atomic_inc(&cpu_hotplug.puts_pending);
+		/* we might be the last one */
+		active_writer = cpu_hotplug.active_writer;
+		if (unlikely(active_writer))
+			wake_up_process(active_writer);
 		cpuhp_lock_release();
 		return;
 	}
@@ -161,15 +167,17 @@ void cpu_hotplug_begin(void)
 	cpuhp_lock_acquire();
 	for (;;) {
 		mutex_lock(&cpu_hotplug.lock);
+		__set_current_state(TASK_UNINTERRUPTIBLE);
 		if (atomic_read(&cpu_hotplug.puts_pending)) {
 			int delta;
 
 			delta = atomic_xchg(&cpu_hotplug.puts_pending, 0);
 			cpu_hotplug.refcount -= delta;
 		}
-		if (likely(!cpu_hotplug.refcount))
+		if (likely(!cpu_hotplug.refcount)) {
+			__set_current_state(TASK_RUNNING);
 			break;
-		__set_current_state(TASK_UNINTERRUPTIBLE);
+		}
 		mutex_unlock(&cpu_hotplug.lock);
 		schedule();
 	}
Signature · 1 line
1.8.5.5
#1 lore raw
Quoted 45 lines · David Hildenbrand

Commit b2c4623dcd07 ("rcu: More on deadlock between CPU hotplug and expedited grace periods") introduced another problem that can easily be reproduced by starting/stopping cpus in a loop.

E.g.:
for i in seq 5000; do
echo 1 > /sys/devices/system/cpu/cpu1/online echo 0 > /sys/devices/system/cpu/cpu1/online
done

Will result in:

  INFO: task /cpu_start_stop:1 blocked for more than 120 seconds.
  Call Trace:
  ([<00000000006a028e>] __schedule+0x406/0x91c)
   [<0000000000130f60>] cpu_hotplug_begin+0xd0/0xd4
   [<0000000000130ff6>] _cpu_up+0x3e/0x1c4
   [<0000000000131232>] cpu_up+0xb6/0xd4
   [<00000000004a5720>] device_online+0x80/0xc0
   [<00000000004a57f0>] online_store+0x90/0xb0
  ...

And a deadlock.

Problem is that if the last ref in put_online_cpus() can't get the cpu_hotplug.lock the puts_pending count is incremented, but a sleeping active_writer might never be woken up, therefore never exiting the loop in cpu_hotplug_begin().

This quick fix wakes up the active_writer proactively. The writer already goes back to sleep if the ref count isn't already down to 0, so this should be fine. Also move setting of TASK_UNINTERRUPTIBLE in cpu_hotplug_begin() above the check, so we won't lose any wakeups when racing with put_online_cpus().

Can't reproduce it with this fix.

---
 kernel/cpu.c | 12 ++++++++++--
 1 file changed, 10 insertions(+), 2 deletions(-)
kernel/cpu.c +0 -0
index 90a3d01..1f50c06 100644
@@ -113,10 +113,16 @@ EXPORT_SYMBOL_GPL(try_get_online_cpus);
 

kernel/cpu.c EXPORT_SYMBOL_GPL(try_get_online_cpus); · line 123

Quoted 10 lines
kernel/cpu.c +4 -0
 void put_online_cpus(void)
 {
+	struct task_struct *active_writer;
+
 	if (cpu_hotplug.active_writer == current)
 		return;
 	if (!mutex_trylock(&cpu_hotplug.lock)) {
 		atomic_inc(&cpu_hotplug.puts_pending);
+		/* we might be the last one */
+		active_writer = cpu_hotplug.active_writer;

The compiler is within its rights to optimize the active_writer local variable out of existence, thus re-introducing the possible race with the writer that can pass a NULL pointer to wake_up_process(). So you really need the ACCESS_ONCE() on the read from cpu_hotplug.active_writer. Please see http://lwn.net/Articles/508991/ for more information why this is absolutely required.

kernel/cpu.c void cpu_hotplug_begin(void) · line 170

Quoted 10 lines
kernel/cpu.c +3 -0
+		if (unlikely(active_writer))
+			wake_up_process(active_writer);
 		cpuhp_lock_release();
 		return;
 	}
@@ -161,15 +167,17 @@ void cpu_hotplug_begin(void)
 	cpuhp_lock_acquire();
 	for (;;) {
 		mutex_lock(&cpu_hotplug.lock);
+		__set_current_state(TASK_UNINTERRUPTIBLE);

You lost me on this one. How does this help?

Thanx, Paul

Quoted 18 lines
kernel/cpu.c +3 -2
 		if (atomic_read(&cpu_hotplug.puts_pending)) {
 			int delta;
 
 			delta = atomic_xchg(&cpu_hotplug.puts_pending, 0);
 			cpu_hotplug.refcount -= delta;
 		}
-		if (likely(!cpu_hotplug.refcount))
+		if (likely(!cpu_hotplug.refcount)) {
+			__set_current_state(TASK_RUNNING);
 			break;
-		__set_current_state(TASK_UNINTERRUPTIBLE);
+		}
 		mutex_unlock(&cpu_hotplug.lock);
 		schedule();
 	}
Signature · 1 line
1.8.5.5
#2 lore raw
Quoted 6 lines

The compiler is within its rights to optimize the active_writer local variable out of existence, thus re-introducing the possible race with the writer that can pass a NULL pointer to wake_up_process(). So you really need the ACCESS_ONCE() on the read from cpu_hotplug.active_writer. Please see http://lwn.net/Articles/508991/ for more information why this is absolutely required.

You're absolutely right, saw your reply on the other patch just after I sent this version ...

So if you agree with the change below, I'll send an updated version!

Quoted 14 lines

kernel/cpu.c void cpu_hotplug_begin(void) · line 170

Quoted 11 lines
kernel/cpu.c +3 -0
+		if (unlikely(active_writer))
+			wake_up_process(active_writer);
 		cpuhp_lock_release();
 		return;
 	}
@@ -161,15 +167,17 @@ void cpu_hotplug_begin(void)
 	cpuhp_lock_acquire();
 	for (;;) {
 		mutex_lock(&cpu_hotplug.lock);
+		__set_current_state(TASK_UNINTERRUPTIBLE);

You lost me on this one. How does this help?

Quoted 1 line

Thanx, Paul

Imagine e.g. the following (simplified) scenario:

CPU1 CPU2
----------------------------------------------------------------------------

!mutex_trylock(&cpu_hotplug.lock) |
                                  | cpu_hotplug.puts_pending == 0
cpu_hotplug.puts_pending++;       |
                                  | cpu_hotplug.refcount != 0
wake_up_process(active_writer)
                                  | __set_current_state(TASK_UNINTERRUPTIBLE);
                                  | schedule();
                                  | /* will never be woken up */

Therefore we have to move the condition check inside the
__set_current_state(TASK_UNINTERRUPTIBLE) -> schedule();
section to not miss any wake ups when the condition is satisfied.

So wake_up_process() will either see TASK_RUNNING and do nothing or see TASK_UNINTERRUPTIBLE and set it to TASK_RUNNING, so schedule() will in fact be woken up again.

Thanks a lot!

David

#3 lore raw
Quoted 41 lines · David Hildenbrand
Quoted 6 lines

The compiler is within its rights to optimize the active_writer local variable out of existence, thus re-introducing the possible race with the writer that can pass a NULL pointer to wake_up_process(). So you really need the ACCESS_ONCE() on the read from cpu_hotplug.active_writer. Please see http://lwn.net/Articles/508991/ for more information why this is absolutely required.

You're absolutely right, saw your reply on the other patch just after I sent this version ...

So if you agree with the change below, I'll send an updated version!

Quoted 14 lines

kernel/cpu.c void cpu_hotplug_begin(void) · line 170

Quoted 11 lines
kernel/cpu.c +3 -0
+		if (unlikely(active_writer))
+			wake_up_process(active_writer);
 		cpuhp_lock_release();
 		return;
 	}
@@ -161,15 +167,17 @@ void cpu_hotplug_begin(void)
 	cpuhp_lock_acquire();
 	for (;;) {
 		mutex_lock(&cpu_hotplug.lock);
+		__set_current_state(TASK_UNINTERRUPTIBLE);

You lost me on this one. How does this help?

Quoted 1 line

Thanx, Paul

Imagine e.g. the following (simplified) scenario:

CPU1 CPU2
----------------------------------------------------------------------------

!mutex_trylock(&cpu_hotplug.lock) |
                                  | cpu_hotplug.puts_pending == 0
cpu_hotplug.puts_pending++;       |
                                  | cpu_hotplug.refcount != 0
wake_up_process(active_writer)
                                  | __set_current_state(TASK_UNINTERRUPTIBLE);
                                  | schedule();
                                  | /* will never be woken up */
Quoted 7 lines

Therefore we have to move the condition check inside the
__set_current_state(TASK_UNINTERRUPTIBLE) -> schedule();
section to not miss any wake ups when the condition is satisfied.

So wake_up_process() will either see TASK_RUNNING and do nothing or see TASK_UNINTERRUPTIBLE and set it to TASK_RUNNING, so schedule() will in fact be woken up again.

Or the third alternative would be that 'active_writer' which was running on CPU2 already terminated and wake_up_process() has a non-NULL pointer to task_struct which is already dead.
Or is there anything that prevents this use-after-free race?

#4 lore raw
Quoted 4 lines
Quoted 4 lines

Therefore we have to move the condition check inside the
__set_current_state(TASK_UNINTERRUPTIBLE) -> schedule();
section to not miss any wake ups when the condition is satisfied.

Quoted 8 lines
Quoted 3 lines

So wake_up_process() will either see TASK_RUNNING and do nothing or see TASK_UNINTERRUPTIBLE and set it to TASK_RUNNING, so schedule() will in fact be woken up again.

Or the third alternative would be that 'active_writer' which was running on CPU2 already terminated and wake_up_process() has a non-NULL pointer to task_struct which is already dead.
Or is there anything that prevents this use-after-free race?

Hmmm ... I think that is also a valid scenario.
That would mean we need soemthing like this:

void put_online_cpus(void)
{
+ struct task_struct *awr;
+

        if (cpu_hotplug.active_writer == current)
                return;
        if (!mutex_trylock(&cpu_hotplug.lock)) {

+ awr = ACCESS_ONCE(cpu_hotplug.active_writer);
+ if (unlikely(awr))
+ get_task_struct(awr);
+ /* inc after get_task_struct(), so the writer can't get NULL */

                atomic_inc(&cpu_hotplug.puts_pending);

+ /* we might be the last one */
+ if (unlikely(awr)) {
+ wake_up_process(awr);
+ put_task_struct(awr);
+ }

                cpuhp_lock_release();
                return;
        }

Thanks!

David

#5 lore raw
Quoted 19 lines · David Hildenbrand
Quoted 4 lines
Quoted 4 lines

Therefore we have to move the condition check inside the
__set_current_state(TASK_UNINTERRUPTIBLE) -> schedule();
section to not miss any wake ups when the condition is satisfied.

Quoted 8 lines
Quoted 3 lines

So wake_up_process() will either see TASK_RUNNING and do nothing or see TASK_UNINTERRUPTIBLE and set it to TASK_RUNNING, so schedule() will in fact be woken up again.

Or the third alternative would be that 'active_writer' which was running on CPU2 already terminated and wake_up_process() has a non-NULL pointer to task_struct which is already dead.
Or is there anything that prevents this use-after-free race?

Hmmm ... I think that is also a valid scenario.
That would mean we need soemthing like this:

void put_online_cpus(void)
{
+ struct task_struct *awr;

kernel/cpu.c EXPORT_SYMBOL_GPL(try_get_online_cpus);

Quoted 7 lines
kernel/cpu.c +4 -0
+
        if (cpu_hotplug.active_writer == current)
                return;
        if (!mutex_trylock(&cpu_hotplug.lock)) {
+         awr = ACCESS_ONCE(cpu_hotplug.active_writer);
+         if (unlikely(awr))
+                 get_task_struct(awr);

How would this solve the problem?

#6 lore raw
Quoted 28 lines · David Hildenbrand
Quoted 19 lines
Quoted 4 lines
Quoted 4 lines

Therefore we have to move the condition check inside the
__set_current_state(TASK_UNINTERRUPTIBLE) -> schedule();
section to not miss any wake ups when the condition is satisfied.

Quoted 8 lines
Quoted 3 lines

So wake_up_process() will either see TASK_RUNNING and do nothing or see TASK_UNINTERRUPTIBLE and set it to TASK_RUNNING, so schedule() will in fact be woken up again.

Or the third alternative would be that 'active_writer' which was running on CPU2 already terminated and wake_up_process() has a non-NULL pointer to task_struct which is already dead.
Or is there anything that prevents this use-after-free race?

Hmmm ... I think that is also a valid scenario.
That would mean we need soemthing like this:

void put_online_cpus(void)
{
+ struct task_struct *awr;

kernel/cpu.c EXPORT_SYMBOL_GPL(try_get_online_cpus);

Quoted 7 lines
kernel/cpu.c +4 -0
+
        if (cpu_hotplug.active_writer == current)
                return;
        if (!mutex_trylock(&cpu_hotplug.lock)) {
+         awr = ACCESS_ONCE(cpu_hotplug.active_writer);
+         if (unlikely(awr))
+                 get_task_struct(awr);
Quoted 1 line

How would this solve the problem?

If I am not completely wrong, an active_writer will remain in it's loop (cpu_hotplug_begin) until the refcount is down to 0. As we are putting the cpus, the refcount is > 0 (because of the previous get_all_cpus() which incremented the refcount).

cpu_hotplug_begin will only be able to exit as soon as refcount == 0, therefore in our special case if cpu_hotplug.puts_pending has been incremented.

As long as we don't increment cpu_hotplug.puts_pending, the active_writer will not vanish. Therefore awr still points to a valid task struct after we incremented cpu_hotplug.puts_pending.

get_task_struct() will make sure that the struct will not vanish after we incremented cpu_hotplug.puts_pending (and therefore decremented the refcount).

Or am I missing something?

Thanks!

David

#7 lore raw
In reply to Heiko Carstens
Quoted 28 lines · David Hildenbrand
Quoted 19 lines
Quoted 4 lines
Quoted 4 lines

Therefore we have to move the condition check inside the
__set_current_state(TASK_UNINTERRUPTIBLE) -> schedule();
section to not miss any wake ups when the condition is satisfied.

Quoted 8 lines
Quoted 3 lines

So wake_up_process() will either see TASK_RUNNING and do nothing or see TASK_UNINTERRUPTIBLE and set it to TASK_RUNNING, so schedule() will in fact be woken up again.

Or the third alternative would be that 'active_writer' which was running on CPU2 already terminated and wake_up_process() has a non-NULL pointer to task_struct which is already dead.
Or is there anything that prevents this use-after-free race?

Hmmm ... I think that is also a valid scenario.
That would mean we need soemthing like this:

void put_online_cpus(void)
{
+ struct task_struct *awr;

kernel/cpu.c EXPORT_SYMBOL_GPL(try_get_online_cpus);

Quoted 7 lines
kernel/cpu.c +4 -0
+
        if (cpu_hotplug.active_writer == current)
                return;
        if (!mutex_trylock(&cpu_hotplug.lock)) {
+         awr = ACCESS_ONCE(cpu_hotplug.active_writer);
+         if (unlikely(awr))
+                 get_task_struct(awr);
Quoted 1 line

How would this solve the problem?

Although this might fix the problem you addressed, it exposes another one:

CPU1 CPU2
----------------------------------------------------------------------------

!mutex_trylock(&cpu_hotplug.lock) |
cpu_hotplug.active_writer == 0    |
awr = 0;                          |
                                  | cpu_hotplug.active_writer = current
                                  | __set_current_state(TASK_UNINTERRUPTIBLE);
                                  | cpu_hotplug.puts_pending == 0
cpu_hotplug.puts_pending++;       | ...
                                  | schedule();

/* no wakeup as awr == 0 */

So we really need to cpu_hotplug.puts_pending++; before checking for cpu_hotplug.active_writer. That in turn can lead to the active_writer struct vanishing.

So we can't get around a lock for cpu_hotplug.active_writer IMHO. Or we have to revert the original patch - but that one addressed an rcu problem.

Opinions?

David