Possible bug with mutex adaptative spinning

Possible bug with mutex adaptative spinning

[Benjamin Herrenschmidt]

Hi Peter !

I -may- have found a bug with mutex adaptative spinning. We hit it when
torture testing CPU unplug.

Basically, what happens is mutex_spin_on_owner() returns 1 if the owner
CPU is offline. That means that the caller (__mutex_lock_common()) will
spin until the mutex is released since there's a valid owner (so the
need_resched() test doesn't trigger). This will deadlock if this is the
only remaining CPU online.

In fact, it even deadlocks with more than 1 CPU online, for example, I
have a case where the 2 remaining online CPUs got into
__mutex_lock_common() at the same time, and so got into that spin loop
before any of them added itself to the wait_list, thus never hitting the
exist condition there.

I believe your test against nr_cpumask_bits is also a bit fragile for
similar reasons. IE. You have what looks like a valid owner but it seems
to be on an invalid CPU. It could be a freed thread_info, in which case
returning 1 is fine, but if it's anything else, kaboom. I think it's
better to be safe than sorry here and just go to sleep (ie return 0).

Same comment with the DEBUG_PAGE_ALLOC case. In fact, this (untested)
patch makes the function simpler and I don't think will have any
negative effect on performances. Let me know what you think:

---- cut here ----

[PATCH] mutex: Don't spin when the owner CPU is offline or other weird cases

The current code might spin forever if the CPU owning the mutex has been
offlined, and the last CPU in the system is trying to acquire it, since
mutex_spin_on_owner() will always return 1, telling the caller to spin
until the mutex has been released.

This patch changes mutex_spin_on_owner() to return 0 (don't spin) in any
case where we aren't sure about the owner struct validity or CPU number,
and if the said CPU is offline. There is no point going back &
re-evaluate spinning in corner cases like that, let's just go to sleep.

Signed-off-by: Benjamin Herrenschmidt <benh@kernel.crashing.org>
---

diff --git a/kernel/sched.c b/kernel/sched.c
index a3dff1f..11b7f4a 100644
--- a/kernel/sched.c
+++ b/kernel/sched.c
@@ -3780,7 +3780,7 @@ int mutex_spin_on_owner(struct mutex *lock, struct
thread_info *owner)
 	 * the mutex owner just released it and exited.
 	 */
 	if (probe_kernel_address(&owner->cpu, cpu))
-		goto out;
+		return 0;
 #else
 	cpu = owner->cpu;
 #endif
@@ -3788,16 +3788,21 @@ int mutex_spin_on_owner(struct mutex *lock,
struct thread_info *owner)
 	/*
 	 * Even if the access succeeded (likely case),
 	 * the cpu field may no longer be valid.
+	 *
+	 * We stop spinning in this case since the owner may never
 	 */
 	if (cpu >= nr_cpumask_bits)
-		goto out;
+		return 0;
 
 	/*
 	 * We need to validate that we can do a
 	 * get_cpu() and that we have the percpu area.
+	 *
+	 * If the CPU is offline, the owner will never release it so
+	 * we must not spin
 	 */
 	if (!cpu_online(cpu))
-		goto out;
+		return 0;
 
 	rq = cpu_rq(cpu);
 
@@ -3816,7 +3821,6 @@ int mutex_spin_on_owner(struct mutex *lock, struct
thread_info *owner)
 
 		cpu_relax();
 	}
-out:
 	return 1;
 }
 #endif

Re: Possible bug with mutex adaptative spinning

[Benjamin Herrenschmidt]

On Wed, 2010-04-14 at 12:35 +1000, Benjamin Herrenschmidt wrote:
> Hi Peter !
> 
> I -may- have found a bug with mutex adaptative spinning. We hit it when
> torture testing CPU unplug.

 .../...

In fact, I wonder if there's another potential problem:

If the owner is actually running, it may do so for a very long time. It
looks to me that everybody trying to take the mutex will thus spin and
never get out of the spin loop until the owner stops running.

That sounds very wrong to me :-)

Shouldn't you at least remove the test for !owner when testing
need_resched() in __mutex_lock_common() ?

Cheers,
Ben.

Re: Possible bug with mutex adaptative spinning

[Peter Zijlstra]

On Wed, 2010-04-14 at 12:56 +1000, Benjamin Herrenschmidt wrote:
> On Wed, 2010-04-14 at 12:35 +1000, Benjamin Herrenschmidt wrote:
> > Hi Peter !
> > 
> > I -may- have found a bug with mutex adaptative spinning. We hit it when
> > torture testing CPU unplug.
> 
>  .../...
> 
> In fact, I wonder if there's another potential problem:
> 
> If the owner is actually running, it may do so for a very long time. It
> looks to me that everybody trying to take the mutex will thus spin and
> never get out of the spin loop until the owner stops running.

The inner-most spin loop breaks out on need_resched():

                if (task_thread_info(rq->curr) != owner || need_resched())
                        return 0;

Re: Possible bug with mutex adaptative spinning

[Benjamin Herrenschmidt]

On Fri, 2010-04-16 at 23:27 +0200, Peter Zijlstra wrote:
> > If the owner is actually running, it may do so for a very long time. It
> > looks to me that everybody trying to take the mutex will thus spin and
> > never get out of the spin loop until the owner stops running.
> 
> The inner-most spin loop breaks out on need_resched():
> 
>                 if (task_thread_info(rq->curr) != owner || need_resched())
>                         return 0; 

You are right, this was only a problem in conjunction with the other bug
returning 1 all the time, causing us to ignore need_resched(). With
that fixed, it looks fine now.

Thanks !

Cheers,
Ben.

Re: Possible bug with mutex adaptative spinning

[Peter Zijlstra]

On Wed, 2010-04-14 at 12:35 +1000, Benjamin Herrenschmidt wrote:

> [PATCH] mutex: Don't spin when the owner CPU is offline or other weird cases
> 
> The current code might spin forever if the CPU owning the mutex has been
> offlined, and the last CPU in the system is trying to acquire it, since
> mutex_spin_on_owner() will always return 1, telling the caller to spin
> until the mutex has been released.
> 
> This patch changes mutex_spin_on_owner() to return 0 (don't spin) in any
> case where we aren't sure about the owner struct validity or CPU number,
> and if the said CPU is offline. There is no point going back &
> re-evaluate spinning in corner cases like that, let's just go to sleep.
> 
> Signed-off-by: Benjamin Herrenschmidt <benh@kernel.crashing.org>

Right, patch looks good, comments are a tad misleading.


I've queued the below patch

---
Subject: mutex: Don't spin when the owner CPU is offline or other weird cases
From: Benjamin Herrenschmidt <benh@kernel.crashing.org>
Date: Fri Apr 16 23:20:00 CEST 2010

Due to recent load-balancer changes that delay the task migration to
the next wakeup, the adaptive mutex spinning ends up in a live lock
when the owner's CPU gets offlined because the cpu_online() check
lives before the owner running check.

This patch changes mutex_spin_on_owner() to return 0 (don't spin) in
any case where we aren't sure about the owner struct validity or CPU
number, and if the said CPU is offline. There is no point going back &
re-evaluate spinning in corner cases like that, let's just go to
sleep.

Signed-off-by: Benjamin Herrenschmidt <benh@kernel.crashing.org>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
LKML-Reference: <1271212509.13059.135.camel@pasglop>
---
 kernel/sched.c |    8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

Index: linux-2.6/kernel/sched.c
===================================================================
--- linux-2.6.orig/kernel/sched.c
+++ linux-2.6/kernel/sched.c
@@ -3647,7 +3647,7 @@ int mutex_spin_on_owner(struct mutex *lo
 	 * the mutex owner just released it and exited.
 	 */
 	if (probe_kernel_address(&owner->cpu, cpu))
-		goto out;
+		return 0;
 #else
 	cpu = owner->cpu;
 #endif
@@ -3657,14 +3657,14 @@ int mutex_spin_on_owner(struct mutex *lo
 	 * the cpu field may no longer be valid.
 	 */
 	if (cpu >= nr_cpumask_bits)
-		goto out;
+		return 0;
 
 	/*
 	 * We need to validate that we can do a
 	 * get_cpu() and that we have the percpu area.
 	 */
 	if (!cpu_online(cpu))
-		goto out;
+		return 0;
 
 	rq = cpu_rq(cpu);
 
@@ -3683,7 +3683,7 @@ int mutex_spin_on_owner(struct mutex *lo
 
 		cpu_relax();
 	}
-out:
+
 	return 1;
 }
 #endif

Re: Possible bug with mutex adaptative spinning

[Benjamin Herrenschmidt]

> 
> I've queued the below patch

Thanks. Should it make -stable as well ?

Cheers,
Ben.

> ---
> Subject: mutex: Don't spin when the owner CPU is offline or other weird cases
> From: Benjamin Herrenschmidt <benh@kernel.crashing.org>
> Date: Fri Apr 16 23:20:00 CEST 2010
> 
> Due to recent load-balancer changes that delay the task migration to
> the next wakeup, the adaptive mutex spinning ends up in a live lock
> when the owner's CPU gets offlined because the cpu_online() check
> lives before the owner running check.
> 
> This patch changes mutex_spin_on_owner() to return 0 (don't spin) in
> any case where we aren't sure about the owner struct validity or CPU
> number, and if the said CPU is offline. There is no point going back &
> re-evaluate spinning in corner cases like that, let's just go to
> sleep.
> 
> Signed-off-by: Benjamin Herrenschmidt <benh@kernel.crashing.org>
> Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
> LKML-Reference: <1271212509.13059.135.camel@pasglop>
> ---
>  kernel/sched.c |    8 ++++----
>  1 file changed, 4 insertions(+), 4 deletions(-)
> 
> Index: linux-2.6/kernel/sched.c
> ===================================================================
> --- linux-2.6.orig/kernel/sched.c
> +++ linux-2.6/kernel/sched.c
> @@ -3647,7 +3647,7 @@ int mutex_spin_on_owner(struct mutex *lo
>  	 * the mutex owner just released it and exited.
>  	 */
>  	if (probe_kernel_address(&owner->cpu, cpu))
> -		goto out;
> +		return 0;
>  #else
>  	cpu = owner->cpu;
>  #endif
> @@ -3657,14 +3657,14 @@ int mutex_spin_on_owner(struct mutex *lo
>  	 * the cpu field may no longer be valid.
>  	 */
>  	if (cpu >= nr_cpumask_bits)
> -		goto out;
> +		return 0;
>  
>  	/*
>  	 * We need to validate that we can do a
>  	 * get_cpu() and that we have the percpu area.
>  	 */
>  	if (!cpu_online(cpu))
> -		goto out;
> +		return 0;
>  
>  	rq = cpu_rq(cpu);
>  
> @@ -3683,7 +3683,7 @@ int mutex_spin_on_owner(struct mutex *lo
>  
>  		cpu_relax();
>  	}
> -out:
> +
>  	return 1;
>  }
>  #endif
>