[PATCH v2] CPU hotplug: active_writer not woken up in some cases - deadlock

[PATCH v2] CPU hotplug: active_writer not woken up in some cases - deadlock

[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.

Signed-off-by: David Hildenbrand <dahi@linux.vnet.ibm.com>
---
 kernel/cpu.c | 12 ++++++++++--
 1 file changed, 10 insertions(+), 2 deletions(-)

diff --git a/kernel/cpu.c b/kernel/cpu.c
index 90a3d01..1f50c06 100644
--- a/kernel/cpu.c
+++ b/kernel/cpu.c
@@ -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();
 	}
-- 
1.8.5.5

Re: [PATCH v2] CPU hotplug: active_writer not woken up in some cases - deadlock

[Paul E. McKenney]

On Mon, Dec 08, 2014 at 09:21:22PM +0100, David Hildenbrand wrote:
> 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.
> 
> Signed-off-by: David Hildenbrand <dahi@linux.vnet.ibm.com>
> ---
>  kernel/cpu.c | 12 ++++++++++--
>  1 file changed, 10 insertions(+), 2 deletions(-)
> 
> diff --git a/kernel/cpu.c b/kernel/cpu.c
> index 90a3d01..1f50c06 100644
> --- a/kernel/cpu.c
> +++ b/kernel/cpu.c
> @@ -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;

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.

> +		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

>  		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();
>  	}
> -- 
> 1.8.5.5
> 

Re: [PATCH v2] CPU hotplug: active_writer not woken up in some cases - deadlock

[David Hildenbrand]

> 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!

> 
> > +		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

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

Re: [PATCH v2] CPU hotplug: active_writer not woken up in some cases - deadlock

[Heiko Carstens]

On Tue, Dec 09, 2014 at 08:59:30AM +0100, David Hildenbrand wrote:
> > 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!
> 
> > 
> > > +		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
> 
> 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.

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?

Re: [PATCH v2] CPU hotplug: active_writer not woken up in some cases - deadlock

[David Hildenbrand]

> > 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?

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

Re: [PATCH v2] CPU hotplug: active_writer not woken up in some cases - deadlock

[Heiko Carstens]

On Tue, Dec 09, 2014 at 11:11:01AM +0100, David Hildenbrand wrote:
> > > 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?
> 
> 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);

How would this solve the problem?

Re: [PATCH v2] CPU hotplug: active_writer not woken up in some cases - deadlock

[David Hildenbrand]

> On Tue, Dec 09, 2014 at 11:11:01AM +0100, David Hildenbrand wrote:
> > > > 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?
> > 
> > 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);
> 
> 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

Re: [PATCH v2] CPU hotplug: active_writer not woken up in some cases - deadlock

[David Hildenbrand]

> On Tue, Dec 09, 2014 at 11:11:01AM +0100, David Hildenbrand wrote:
> > > > 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?
> > 
> > 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);
> 
> 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