RFC: mutex: hung tasks on SMP platforms with asm-generic/mutex-xchg.h

RFC: mutex: hung tasks on SMP platforms with asm-generic/mutex-xchg.h

[Will Deacon]

Hello,

ARM recently moved to asm-generic/mutex-xchg.h for its mutex implementation
after our previous implementation was found to be missing some crucial
memory barriers. However, I'm seeing some problems running hackbench on
SMP platforms due to the way in which the MUTEX_SPIN_ON_OWNER code operates.

The symptoms are that a bunch of hackbench tasks are left waiting on an
unlocked mutex and therefore never get woken up to claim it. I think this
boils down to the following sequence:


        Task A        Task B        Task C        Lock value
0                                                     1
1       lock()                                        0
2                     lock()                          0
3                     spin(A)                         0
4       unlock()                                      1
5                                   lock()            0
6                     cmpxchg(1,0)                    0
7                     contended()                    -1
8       lock()                                        0
9       spin(C)                                       0
10                                  unlock()          1
11      cmpxchg(1,0)                                  0
12      unlock()                                      1


At this point, the lock is unlocked, but Task B is in an uninterruptible
sleep with nobody to wake it up.

The following patch fixes the problem by ensuring we put the lock into
the contended state if we acquire it from the spin loop on the slowpath
but I'd like to be sure that this won't cause problems with other mutex
implementations:


diff --git a/kernel/mutex.c b/kernel/mutex.c
index a307cc9..27b7887 100644
--- a/kernel/mutex.c
+++ b/kernel/mutex.c
@@ -170,7 +170,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
                if (owner && !mutex_spin_on_owner(lock, owner))
                        break;
 
-               if (atomic_cmpxchg(&lock->count, 1, 0) == 1) {
+               if (atomic_cmpxchg(&lock->count, 1, -1) == 1) {
                        lock_acquired(&lock->dep_map, ip);
                        mutex_set_owner(lock);
                        preempt_enable();


All comments welcome.

Cheers,

Will

RFC: mutex: hung tasks on SMP platforms with asm-generic/mutex-xchg.h

[Peter Zijlstra]

On Tue, 2012-08-07 at 12:56 +0100, Will Deacon wrote:
> Hello,
> 
> ARM recently moved to asm-generic/mutex-xchg.h for its mutex implementation
> after our previous implementation was found to be missing some crucial
> memory barriers. 


This is a76d7bd96d ("ARM: 7467/1: mutex: use generic xchg-based
implementation for ARMv6+"), right? Why do you use xchg and not dec
based? The changelog mumbles something about shorter critical sections,
but me not knowing anything about ARM wonders about the why of that.

> However, I'm seeing some problems running hackbench on
> SMP platforms due to the way in which the MUTEX_SPIN_ON_OWNER code operates.
> 
> The symptoms are that a bunch of hackbench tasks are left waiting on an
> unlocked mutex and therefore never get woken up to claim it. I think this
> boils down to the following sequence:
> 
> 
>         Task A        Task B        Task C        Lock value
> 0                                                     1
> 1       lock()                                        0
> 2                     lock()                          0
> 3                     spin(A)                         0
> 4       unlock()                                      1
> 5                                   lock()            0
> 6                     cmpxchg(1,0)                    0
> 7                     contended()                    -1
> 8       lock()                                        0
> 9       spin(C)                                       0
> 10                                  unlock()          1
> 11      cmpxchg(1,0)                                  0
> 12      unlock()                                      1
> 
> 
> At this point, the lock is unlocked, but Task B is in an uninterruptible
> sleep with nobody to wake it up.
> 
> The following patch fixes the problem by ensuring we put the lock into
> the contended state if we acquire it from the spin loop on the slowpath
> but I'd like to be sure that this won't cause problems with other mutex
> implementations:
> 
> 
> diff --git a/kernel/mutex.c b/kernel/mutex.c
> index a307cc9..27b7887 100644
> --- a/kernel/mutex.c
> +++ b/kernel/mutex.c
> @@ -170,7 +170,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
>                 if (owner && !mutex_spin_on_owner(lock, owner))
>                         break;
>  
> -               if (atomic_cmpxchg(&lock->count, 1, 0) == 1) {
> +               if (atomic_cmpxchg(&lock->count, 1, -1) == 1) {
>                         lock_acquired(&lock->dep_map, ip);
>                         mutex_set_owner(lock);
>                         preempt_enable();
> 

But in this case, either B is still spinning in our spin-loop, or it has
already passed the atomic_xchg(&lock->count, -1) when we fell out.

Since you say B is in UNINTERRUPTIBLE state, we'll assume it fell
through and so the lock count should be -1 (or less) to mark it
contended.

RFC: mutex: hung tasks on SMP platforms with asm-generic/mutex-xchg.h

[Will Deacon]

On Tue, Aug 07, 2012 at 02:48:42PM +0100, Peter Zijlstra wrote:
> On Tue, 2012-08-07 at 12:56 +0100, Will Deacon wrote:
> > ARM recently moved to asm-generic/mutex-xchg.h for its mutex implementation
> > after our previous implementation was found to be missing some crucial
> > memory barriers. 
> 
> 
> This is a76d7bd96d ("ARM: 7467/1: mutex: use generic xchg-based
> implementation for ARMv6+"), right? Why do you use xchg and not dec
> based? The changelog mumbles something about shorter critical sections,
> but me not knowing anything about ARM wonders about the why of that.

Correct, that's the patch. We don't have atomic add/sub instructions on ARM,
so instead we have to do:

1:	ldrex	...	@ Exclusive load
	add/sub ...     @ Do the arithmetic
	strex	...	@ Exclusive store
	cmp	...	@ Check the store succeeded
	bne	1b	@ Retry if we weren't atomic

So using dec adds a sub where we wouldn't need an instruction there for xchg.
I suspect there's no measurable difference between the two, but we use the
xchg-based implementation for CPUs prior to ARMv6 so it saves an ifdef as
well. Some discussion on the original patch here:

  http://lists.infradead.org/pipermail/linux-arm-kernel/2012-July/109333.html

> >         Task A        Task B        Task C        Lock value
> > 0                                                     1
> > 1       lock()                                        0
> > 2                     lock()                          0
> > 3                     spin(A)                         0
> > 4       unlock()                                      1
> > 5                                   lock()            0
> > 6                     cmpxchg(1,0)                    0
> > 7                     contended()                    -1
> > 8       lock()                                        0
> > 9       spin(C)                                       0
> > 10                                  unlock()          1
> > 11      cmpxchg(1,0)                                  0
> > 12      unlock()                                      1
> > 
> > 
> > At this point, the lock is unlocked, but Task B is in an uninterruptible
> > sleep with nobody to wake it up.

[...]

> But in this case, either B is still spinning in our spin-loop, or it has
> already passed the atomic_xchg(&lock->count, -1) when we fell out.

Yes, it does that xchg on line 7 (see the lock value of -1)...

> Since you say B is in UNINTERRUPTIBLE state, we'll assume it fell
> through and so the lock count should be -1 (or less) to mark it
> contended.

... but then A sets it straight back to 0 in __mutex_fastpath_lock and falls
down the slowpath due to it being contended. The problem is that it doesn't
restore the -1 when it acquires the lock on line 11, so B is never woken up.

Will

RFC: mutex: hung tasks on SMP platforms with asm-generic/mutex-xchg.h

[Nicolas Pitre]

On Tue, 7 Aug 2012, Will Deacon wrote:

> Hello,
> 
> ARM recently moved to asm-generic/mutex-xchg.h for its mutex implementation
> after our previous implementation was found to be missing some crucial
> memory barriers. However, I'm seeing some problems running hackbench on
> SMP platforms due to the way in which the MUTEX_SPIN_ON_OWNER code operates.
> 
> The symptoms are that a bunch of hackbench tasks are left waiting on an
> unlocked mutex and therefore never get woken up to claim it. I think this
> boils down to the following sequence:
> 
> 
>         Task A        Task B        Task C        Lock value
> 0                                                     1
> 1       lock()                                        0
> 2                     lock()                          0
> 3                     spin(A)                         0
> 4       unlock()                                      1
> 5                                   lock()            0
> 6                     cmpxchg(1,0)                    0
> 7                     contended()                    -1
> 8       lock()                                        0
> 9       spin(C)                                       0
> 10                                  unlock()          1
> 11      cmpxchg(1,0)                                  0
> 12      unlock()                                      1
> 
> 
> At this point, the lock is unlocked, but Task B is in an uninterruptible
> sleep with nobody to wake it up.

I fail to see how the lock value would go from -1 to 0 on line 8.  How 
does that happen?
> The following patch fixes the problem by ensuring we put the lock into
> the contended state if we acquire it from the spin loop on the slowpath
> but I'd like to be sure that this won't cause problems with other mutex
> implementations:
> 
> 
> diff --git a/kernel/mutex.c b/kernel/mutex.c
> index a307cc9..27b7887 100644
> --- a/kernel/mutex.c
> +++ b/kernel/mutex.c
> @@ -170,7 +170,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
>                 if (owner && !mutex_spin_on_owner(lock, owner))
>                         break;
>  
> -               if (atomic_cmpxchg(&lock->count, 1, 0) == 1) {
> +               if (atomic_cmpxchg(&lock->count, 1, -1) == 1) {
>                         lock_acquired(&lock->dep_map, ip);
>                         mutex_set_owner(lock);
>                         preempt_enable();

This would force invokation of the slow path on unlock even if in most 
cases the lock is unlikely to be contended.  The really slow path does 
check if the waiting list is empty and sets the count to 0 before 
exiting to avoid that.  I don't see how this could be done safely in the 
spin_on_owner loop code as the lock->wait_lock isn't held (which appears 
to be the point of this code in the first place).

Yet, if the lock is heavily contended with a waiting task, the count 
should never get back to 1 and the cmpxchg on line 11 would not set the 
count to 0.  Hence my interrogation about line 8 above.


Nicolas

RFC: mutex: hung tasks on SMP platforms with asm-generic/mutex-xchg.h

[Will Deacon]

On Tue, Aug 07, 2012 at 06:14:36PM +0100, Nicolas Pitre wrote:
> On Tue, 7 Aug 2012, Will Deacon wrote:
> > The symptoms are that a bunch of hackbench tasks are left waiting on an
> > unlocked mutex and therefore never get woken up to claim it. I think this
> > boils down to the following sequence:
> > 
> > 
> >         Task A        Task B        Task C        Lock value
> > 0                                                     1
> > 1       lock()                                        0
> > 2                     lock()                          0
> > 3                     spin(A)                         0
> > 4       unlock()                                      1
> > 5                                   lock()            0
> > 6                     cmpxchg(1,0)                    0
> > 7                     contended()                    -1
> > 8       lock()                                        0
> > 9       spin(C)                                       0
> > 10                                  unlock()          1
> > 11      cmpxchg(1,0)                                  0
> > 12      unlock()                                      1
> > 
> > 
> > At this point, the lock is unlocked, but Task B is in an uninterruptible
> > sleep with nobody to wake it up.
> 
> I fail to see how the lock value would go from -1 to 0 on line 8.  How 
> does that happen?

What I think is happening is that B writes the -1 in __mutex_lock_common
and, after seeing a NULL owner (C may not have set that yet), drops through
to the:

	if (atomic_xchg(&lock->count, -1) == 1)
		goto done;

bit. At the same time, A does a mutex_lock, which goes down the fastpath:

	if (unlikely(atomic_xchg(count, 0) != 1))
		fail_fn(count);

setting the count to 0. It then trundles off down the slowpath and spins on
the new owner (C).

Maybe my diagram is confusing... the lock value is supposed to be the value
*after* the relevant operations on that same line have completed.

> > diff --git a/kernel/mutex.c b/kernel/mutex.c
> > index a307cc9..27b7887 100644
> > --- a/kernel/mutex.c
> > +++ b/kernel/mutex.c
> > @@ -170,7 +170,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
> >                 if (owner && !mutex_spin_on_owner(lock, owner))
> >                         break;
> >  
> > -               if (atomic_cmpxchg(&lock->count, 1, 0) == 1) {
> > +               if (atomic_cmpxchg(&lock->count, 1, -1) == 1) {
> >                         lock_acquired(&lock->dep_map, ip);
> >                         mutex_set_owner(lock);
> >                         preempt_enable();
> 
> This would force invokation of the slow path on unlock even if in most 
> cases the lock is unlikely to be contended.  The really slow path does 
> check if the waiting list is empty and sets the count to 0 before 
> exiting to avoid that.  I don't see how this could be done safely in the 
> spin_on_owner loop code as the lock->wait_lock isn't held (which appears 
> to be the point of this code in the first place).

Indeed, it will trigger the slowpath on the next unlock but only in the case
that the lock was contended. You're right that there might not be any
waiters though, and we'd need to take the spinlock to check that.

> Yet, if the lock is heavily contended with a waiting task, the count 
> should never get back to 1 and the cmpxchg on line 11 would not set the 
> count to 0.  Hence my interrogation about line 8 above.

Hmm. __mutex_fastpath_unlock always sets the count to 1:

	if (unlikely(atomic_xchg(count, 1) != 0))
		failt_fn(count);

so there's always a window for a spinning waiter (as opposed to one blocked
in the queue) to succeed in the cmpxchg.

Unless I'm barking up the wrong tree!

Will

RFC: mutex: hung tasks on SMP platforms with asm-generic/mutex-xchg.h

[Will Deacon]

On Tue, Aug 07, 2012 at 06:33:44PM +0100, Will Deacon wrote:
> What I think is happening is that B writes the -1 in __mutex_lock_common
> and, after seeing a NULL owner (C may not have set that yet), drops through
> to the:
> 
> 	if (atomic_xchg(&lock->count, -1) == 1)
> 		goto done;

Sorry, should have proofread that. I meant to say:

 What I think is happening is that B writes the -1 in __mutex_lock_common
 after seeing a NULL owner (C may not have set that yet) and dropping through
 to the:
 
 	if (atomic_xchg(&lock->count, -1) == 1)
 		goto done;
 

Will

RFC: mutex: hung tasks on SMP platforms with asm-generic/mutex-xchg.h

[Nicolas Pitre]

On Tue, 7 Aug 2012, Will Deacon wrote:

> On Tue, Aug 07, 2012 at 06:14:36PM +0100, Nicolas Pitre wrote:
> > On Tue, 7 Aug 2012, Will Deacon wrote:
> > > The symptoms are that a bunch of hackbench tasks are left waiting on an
> > > unlocked mutex and therefore never get woken up to claim it. I think this
> > > boils down to the following sequence:
> > > 
> > > 
> > >         Task A        Task B        Task C        Lock value
> > > 0                                                     1
> > > 1       lock()                                        0
> > > 2                     lock()                          0
> > > 3                     spin(A)                         0
> > > 4       unlock()                                      1
> > > 5                                   lock()            0
> > > 6                     cmpxchg(1,0)                    0
> > > 7                     contended()                    -1
> > > 8       lock()                                        0
> > > 9       spin(C)                                       0
> > > 10                                  unlock()          1
> > > 11      cmpxchg(1,0)                                  0
> > > 12      unlock()                                      1
> > > 
> > > 
> > > At this point, the lock is unlocked, but Task B is in an uninterruptible
> > > sleep with nobody to wake it up.
> > 
> > I fail to see how the lock value would go from -1 to 0 on line 8.  How 
> > does that happen?
> 
> [...]

Forget that.  I assumed cmpxchg when it is just xchg.

(And, for that matter, I'm even the original author for some of that 
 code.: http://lkml.org/lkml/2005/12/26/83).

Back to thinking.


Nicolas

RFC: mutex: hung tasks on SMP platforms with asm-generic/mutex-xchg.h

[Nicolas Pitre]

On Tue, 7 Aug 2012, Will Deacon wrote:

> Hello,
> 
> ARM recently moved to asm-generic/mutex-xchg.h for its mutex implementation
> after our previous implementation was found to be missing some crucial
> memory barriers. However, I'm seeing some problems running hackbench on
> SMP platforms due to the way in which the MUTEX_SPIN_ON_OWNER code operates.
> 
> The symptoms are that a bunch of hackbench tasks are left waiting on an
> unlocked mutex and therefore never get woken up to claim it. I think this
> boils down to the following sequence:
> 
> 
>         Task A        Task B        Task C        Lock value
> 0                                                     1
> 1       lock()                                        0
> 2                     lock()                          0
> 3                     spin(A)                         0
> 4       unlock()                                      1
> 5                                   lock()            0
> 6                     cmpxchg(1,0)                    0
> 7                     contended()                    -1
> 8       lock()                                        0
> 9       spin(C)                                       0
> 10                                  unlock()          1
> 11      cmpxchg(1,0)                                  0
> 12      unlock()                                      1
> 
> 
> At this point, the lock is unlocked, but Task B is in an uninterruptible
> sleep with nobody to wake it up.
> 
> The following patch fixes the problem by ensuring we put the lock into
> the contended state if we acquire it from the spin loop on the slowpath
> but I'd like to be sure that this won't cause problems with other mutex
> implementations:
> 
> 
> diff --git a/kernel/mutex.c b/kernel/mutex.c
> index a307cc9..27b7887 100644
> --- a/kernel/mutex.c
> +++ b/kernel/mutex.c
> @@ -170,7 +170,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
>                 if (owner && !mutex_spin_on_owner(lock, owner))
>                         break;
>  
> -               if (atomic_cmpxchg(&lock->count, 1, 0) == 1) {
> +               if (atomic_cmpxchg(&lock->count, 1, -1) == 1) {
>                         lock_acquired(&lock->dep_map, ip);
>                         mutex_set_owner(lock);
>                         preempt_enable();
> 
> 
> All comments welcome.

Well... after thinking about this for a while, I came to the conclusion 
that the mutex_spin_on_owner code is indeed breaking the contract 
between the xchg lock fast path and the slow path.  The xchg fast path 
will always set the count to 0 and rely on the slow path to restore a 
possible pre-existing negative count.  So the above change would be 
needed for correctness in the xchg case, even if it always forces the 
unlock into the slow path.

As I mentioned previously, we don't want to force the slow path in all 
cases though.  The atomic decrement based fast path doesn't need that, 
so I'd suggest this fix instead:

diff --git a/include/asm-generic/mutex-xchg.h b/include/asm-generic/mutex-xchg.h
index 580a6d35c7..60964844c8 100644
--- a/include/asm-generic/mutex-xchg.h
+++ b/include/asm-generic/mutex-xchg.h
@@ -108,4 +108,6 @@ __mutex_fastpath_trylock(atomic_t *count, int (*fail_fn)(atomic_t *))
 	return prev;
 }
 
+#define __MUTEX_XCHG_FAST_PATH
+
 #endif
diff --git a/kernel/mutex.c b/kernel/mutex.c
index a307cc9c95..c6a26a4f1c 100644
--- a/kernel/mutex.c
+++ b/kernel/mutex.c
@@ -161,6 +161,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 
 	for (;;) {
 		struct task_struct *owner;
+		int locked_val;
 
 		/*
 		 * If there's an owner, wait for it to either
@@ -170,7 +171,19 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
 		if (owner && !mutex_spin_on_owner(lock, owner))
 			break;
 
-		if (atomic_cmpxchg(&lock->count, 1, 0) == 1) {
+#ifdef __MUTEX_XCHG_FAST_PATH
+		/*
+		 * The fast path based on xchg sets a transient 0 count,
+		 * relying on the slow path to restore a possible
+		 * pre-existing contended count.  Without checking the
+		 * waiters' list we must presume possible contension here.
+		 */
+		locked_val = -1;
+#else
+		locked_val = 0;
+#endif
+
+		if (atomic_cmpxchg(&lock->count, 1, locked_val) == 1) {
 			lock_acquired(&lock->dep_map, ip);
 			mutex_set_owner(lock);
 			preempt_enable();

That would be needed for the stable tree as well.

A further cleanup could remove all definitions of 
__mutex_slowpath_needs_to_unlock() given that they're all set to 1 
except for the xchg fast path, in which case __MUTEX_XCHG_FAST_PATH 
could be reused instead.

Of course that might tilt the balance towards using mutex-dec.h on ARM 
v6 and above instead of mutex-xchg.h.  But that is an orthogonal issue, 
and that doesn't remove the need for fixing the xchg based case for 
correctness.


Nicolas

RFC: mutex: hung tasks on SMP platforms with asm-generic/mutex-xchg.h

[Will Deacon]

Hi Nicolas,

Thanks for the replies.

On Thu, Aug 09, 2012 at 06:12:15AM +0100, Nicolas Pitre wrote:
> On Tue, 7 Aug 2012, Will Deacon wrote:
> > diff --git a/kernel/mutex.c b/kernel/mutex.c
> > index a307cc9..27b7887 100644
> > --- a/kernel/mutex.c
> > +++ b/kernel/mutex.c
> > @@ -170,7 +170,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
> >                 if (owner && !mutex_spin_on_owner(lock, owner))
> >                         break;
> >  
> > -               if (atomic_cmpxchg(&lock->count, 1, 0) == 1) {
> > +               if (atomic_cmpxchg(&lock->count, 1, -1) == 1) {
> >                         lock_acquired(&lock->dep_map, ip);
> >                         mutex_set_owner(lock);
> >                         preempt_enable();
> > 
> > 
> > All comments welcome.
> 
> Well... after thinking about this for a while, I came to the conclusion 
> that the mutex_spin_on_owner code is indeed breaking the contract 
> between the xchg lock fast path and the slow path.  The xchg fast path 
> will always set the count to 0 and rely on the slow path to restore a 
> possible pre-existing negative count.  So the above change would be 
> needed for correctness in the xchg case, even if it always forces the 
> unlock into the slow path.

Great, so we agree on that.

> As I mentioned previously, we don't want to force the slow path in all 
> cases though.  The atomic decrement based fast path doesn't need that, 
> so I'd suggest this fix instead:

One minor typo and a suggested alternative below...

> diff --git a/include/asm-generic/mutex-xchg.h b/include/asm-generic/mutex-xchg.h
> index 580a6d35c7..60964844c8 100644
> --- a/include/asm-generic/mutex-xchg.h
> +++ b/include/asm-generic/mutex-xchg.h
> @@ -108,4 +108,6 @@ __mutex_fastpath_trylock(atomic_t *count, int (*fail_fn)(atomic_t *))
>  	return prev;
>  }
>  
> +#define __MUTEX_XCHG_FAST_PATH
> +
>  #endif
> diff --git a/kernel/mutex.c b/kernel/mutex.c
> index a307cc9c95..c6a26a4f1c 100644
> --- a/kernel/mutex.c
> +++ b/kernel/mutex.c
> @@ -161,6 +161,7 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
>  
>  	for (;;) {
>  		struct task_struct *owner;
> +		int locked_val;
>  
>  		/*
>  		 * If there's an owner, wait for it to either
> @@ -170,7 +171,19 @@ __mutex_lock_common(struct mutex *lock, long state, unsigned int subclass,
>  		if (owner && !mutex_spin_on_owner(lock, owner))
>  			break;
>  
> -		if (atomic_cmpxchg(&lock->count, 1, 0) == 1) {
> +#ifdef __MUTEX_XCHG_FAST_PATH
> +		/*
> +		 * The fast path based on xchg sets a transient 0 count,
> +		 * relying on the slow path to restore a possible
> +		 * pre-existing contended count.  Without checking the
> +		 * waiters' list we must presume possible contension here.

s/contension/contention/

> +		 */
> +		locked_val = -1;
> +#else
> +		locked_val = 0;
> +#endif
> +
> +		if (atomic_cmpxchg(&lock->count, 1, locked_val) == 1) {
>  			lock_acquired(&lock->dep_map, ip);
>  			mutex_set_owner(lock);
>  			preempt_enable();
> 
> That would be needed for the stable tree as well.
> 
> A further cleanup could remove all definitions of 
> __mutex_slowpath_needs_to_unlock() given that they're all set to 1 
> except for the xchg fast path, in which case __MUTEX_XCHG_FAST_PATH 
> could be reused instead.

I think we could actually fix this entirely in mutex-xchg.h by doing
something in fastpath_lock similar to what we do for trylock:


diff --git a/include/asm-generic/mutex-xchg.h b/include/asm-generic/mutex-xchg.h
index 580a6d3..c082e99 100644
--- a/include/asm-generic/mutex-xchg.h
+++ b/include/asm-generic/mutex-xchg.h
@@ -25,8 +25,19 @@
 static inline void
 __mutex_fastpath_lock(atomic_t *count, void (*fail_fn)(atomic_t *))
 {
-       if (unlikely(atomic_xchg(count, 0) != 1))
-               fail_fn(count);
+       int prev = atomic_xchg(count, 0);
+
+       if (unlikely(prev != 1)) {
+               if (prev < 0)
+                       /*
+                        * The lock was contended, so we need to restore
+                        * its original state to ensure that any waiting
+                        * tasks are woken up by the unlock slow path.
+                        */
+                       prev = atomic_xchg(count, prev);
+               if (prev != 1)
+                       fail_fn(count);
+       }
 }
 
 /**


What do you reckon?

> Of course that might tilt the balance towards using mutex-dec.h on ARM 
> v6 and above instead of mutex-xchg.h.  But that is an orthogonal issue, 
> and that doesn't remove the need for fixing the xchg based case for 
> correctness.

I'll do some hackbench runs against mutex-dec once we've decided on the final
xchg code. If it's faster, I'll submit a patch for ARM.

Cheers,

Will

RFC: mutex: hung tasks on SMP platforms with asm-generic/mutex-xchg.h

[Nicolas Pitre]

On Thu, 9 Aug 2012, Will Deacon wrote:

> I think we could actually fix this entirely in mutex-xchg.h by doing
> something in fastpath_lock similar to what we do for trylock:
> 
> 
> diff --git a/include/asm-generic/mutex-xchg.h b/include/asm-generic/mutex-xchg.h
> index 580a6d3..c082e99 100644
> --- a/include/asm-generic/mutex-xchg.h
> +++ b/include/asm-generic/mutex-xchg.h
> @@ -25,8 +25,19 @@
>  static inline void
>  __mutex_fastpath_lock(atomic_t *count, void (*fail_fn)(atomic_t *))
>  {
> -       if (unlikely(atomic_xchg(count, 0) != 1))
> -               fail_fn(count);
> +       int prev = atomic_xchg(count, 0);
> +
> +       if (unlikely(prev != 1)) {
> +               if (prev < 0)
> +                       /*
> +                        * The lock was contended, so we need to restore
> +                        * its original state to ensure that any waiting
> +                        * tasks are woken up by the unlock slow path.
> +                        */
> +                       prev = atomic_xchg(count, prev);
> +               if (prev != 1)
> +                       fail_fn(count);
> +       }
>  }
> 
> What do you reckon?

Yes, that looks fine.  I'd remove that if (prev < 0) entirely though.  
We'll just swap a 0 for a 0 if the count wasn't < 0, or a 0 for a 1 if 
the mutex just got unlocked which is also fine.  This is especially 
beneficial when a native xchg processor instruction is used.

> > Of course that might tilt the balance towards using mutex-dec.h on ARM 
> > v6 and above instead of mutex-xchg.h.  But that is an orthogonal issue, 
> > and that doesn't remove the need for fixing the xchg based case for 
> > correctness.
> 
> I'll do some hackbench runs against mutex-dec once we've decided on the final
> xchg code. If it's faster, I'll submit a patch for ARM.

I don't think it would be faster.  It is just potentially more fair.


Nicolas

RFC: mutex: hung tasks on SMP platforms with asm-generic/mutex-xchg.h

[Nicolas Pitre]

On Thu, 9 Aug 2012, Nicolas Pitre wrote:

> On Thu, 9 Aug 2012, Will Deacon wrote:
> 
> > I think we could actually fix this entirely in mutex-xchg.h by doing
> > something in fastpath_lock similar to what we do for trylock:
> > 
> > 
> > diff --git a/include/asm-generic/mutex-xchg.h b/include/asm-generic/mutex-xchg.h
> > index 580a6d3..c082e99 100644
> > --- a/include/asm-generic/mutex-xchg.h
> > +++ b/include/asm-generic/mutex-xchg.h
> > @@ -25,8 +25,19 @@
> >  static inline void
> >  __mutex_fastpath_lock(atomic_t *count, void (*fail_fn)(atomic_t *))
> >  {
> > -       if (unlikely(atomic_xchg(count, 0) != 1))
> > -               fail_fn(count);
> > +       int prev = atomic_xchg(count, 0);
> > +
> > +       if (unlikely(prev != 1)) {
> > +               if (prev < 0)
> > +                       /*
> > +                        * The lock was contended, so we need to restore
> > +                        * its original state to ensure that any waiting
> > +                        * tasks are woken up by the unlock slow path.
> > +                        */
> > +                       prev = atomic_xchg(count, prev);
> > +               if (prev != 1)
> > +                       fail_fn(count);
> > +       }
> >  }
> > 
> > What do you reckon?
> 
> Yes, that looks fine.  I'd remove that if (prev < 0) entirely though.  
> We'll just swap a 0 for a 0 if the count wasn't < 0, or a 0 for a 1 if 
> the mutex just got unlocked which is also fine.  This is especially 
> beneficial when a native xchg processor instruction is used.

In fact, this suggestion isn't entirely correct either. The inner xchg 
in this case should be -1 and not 'count'.  If 'count' is 0 and the 
mutex becomes contended in the small window between the two xchg's then 
the contention mark would be lost again.

In other words, I think this should look like this:

diff --git a/include/asm-generic/mutex-xchg.h b/include/asm-generic/mutex-xchg.h
index 580a6d35c7..44a66c99c8 100644
--- a/include/asm-generic/mutex-xchg.h
+++ b/include/asm-generic/mutex-xchg.h
@@ -25,8 +25,11 @@
 static inline void
 __mutex_fastpath_lock(atomic_t *count, void (*fail_fn)(atomic_t *))
 {
-	if (unlikely(atomic_xchg(count, 0) != 1))
-		fail_fn(count);
+	if (unlikely(atomic_xchg(count, 0) != 1)) {
+		/* Mark lock contention explicitly */
+		if (likely(atomic_xchg(count, -1) != 1))
+			fail_fn(count);
+	}
 }
 
 /**


Nicolas

RFC: mutex: hung tasks on SMP platforms with asm-generic/mutex-xchg.h

[Will Deacon]

On Thu, Aug 09, 2012 at 05:57:33PM +0100, Nicolas Pitre wrote:
> On Thu, 9 Aug 2012, Nicolas Pitre wrote:
> > Yes, that looks fine.  I'd remove that if (prev < 0) entirely though.  
> > We'll just swap a 0 for a 0 if the count wasn't < 0, or a 0 for a 1 if 
> > the mutex just got unlocked which is also fine.  This is especially 
> > beneficial when a native xchg processor instruction is used.
> 
> In fact, this suggestion isn't entirely correct either. The inner xchg 
> in this case should be -1 and not 'count'.  If 'count' is 0 and the 
> mutex becomes contended in the small window between the two xchg's then 
> the contention mark would be lost again.
> 
> In other words, I think this should look like this:
> 
> diff --git a/include/asm-generic/mutex-xchg.h b/include/asm-generic/mutex-xchg.h
> index 580a6d35c7..44a66c99c8 100644
> --- a/include/asm-generic/mutex-xchg.h
> +++ b/include/asm-generic/mutex-xchg.h
> @@ -25,8 +25,11 @@
>  static inline void
>  __mutex_fastpath_lock(atomic_t *count, void (*fail_fn)(atomic_t *))
>  {
> -	if (unlikely(atomic_xchg(count, 0) != 1))
> -		fail_fn(count);
> +	if (unlikely(atomic_xchg(count, 0) != 1)) {
> +		/* Mark lock contention explicitly */
> +		if (likely(atomic_xchg(count, -1) != 1))
> +			fail_fn(count);
> +	}
>  }
>  
>  /**

Doesn't this mean that we're no longer just swapping 0 for a 0 if the lock
was taken, therefore needlessly sending the current owner down the slowpath
on unlock? If we have the explicit test, that doesn't happen and the
disassembly isn't much different (an additional cmp/conditional branch).

Will

RFC: mutex: hung tasks on SMP platforms with asm-generic/mutex-xchg.h

[Nicolas Pitre]

On Thu, 9 Aug 2012, Will Deacon wrote:

> On Thu, Aug 09, 2012 at 05:57:33PM +0100, Nicolas Pitre wrote:
> > On Thu, 9 Aug 2012, Nicolas Pitre wrote:
> > > Yes, that looks fine.  I'd remove that if (prev < 0) entirely though.  
> > > We'll just swap a 0 for a 0 if the count wasn't < 0, or a 0 for a 1 if 
> > > the mutex just got unlocked which is also fine.  This is especially 
> > > beneficial when a native xchg processor instruction is used.
> > 
> > In fact, this suggestion isn't entirely correct either. The inner xchg 
> > in this case should be -1 and not 'count'.  If 'count' is 0 and the 
> > mutex becomes contended in the small window between the two xchg's then 
> > the contention mark would be lost again.
> > 
> > In other words, I think this should look like this:
> > 
> > diff --git a/include/asm-generic/mutex-xchg.h b/include/asm-generic/mutex-xchg.h
> > index 580a6d35c7..44a66c99c8 100644
> > --- a/include/asm-generic/mutex-xchg.h
> > +++ b/include/asm-generic/mutex-xchg.h
> > @@ -25,8 +25,11 @@
> >  static inline void
> >  __mutex_fastpath_lock(atomic_t *count, void (*fail_fn)(atomic_t *))
> >  {
> > -	if (unlikely(atomic_xchg(count, 0) != 1))
> > -		fail_fn(count);
> > +	if (unlikely(atomic_xchg(count, 0) != 1)) {
> > +		/* Mark lock contention explicitly */
> > +		if (likely(atomic_xchg(count, -1) != 1))
> > +			fail_fn(count);
> > +	}
> >  }
> >  
> >  /**
> 
> Doesn't this mean that we're no longer just swapping 0 for a 0 if the lock
> was taken, therefore needlessly sending the current owner down the slowpath
> on unlock?

If the lock was taken, this means the count was either 0 or -1.  If it 
was 1 then we just put a 0 there and we own it.  But if the cound was 0 
then we should store -1 instead, which is what the inner xchg does.  If 
the count was already -1 then we store -1 back.  That more closely mimic 
what the atomic dec does which is what we want.


Nicolas

RFC: mutex: hung tasks on SMP platforms with asm-generic/mutex-xchg.h

[Will Deacon]

On Thu, Aug 09, 2012 at 07:09:02PM +0100, Nicolas Pitre wrote:
> On Thu, 9 Aug 2012, Will Deacon wrote:
> > On Thu, Aug 09, 2012 at 05:57:33PM +0100, Nicolas Pitre wrote:
> > > On Thu, 9 Aug 2012, Nicolas Pitre wrote:
> > > diff --git a/include/asm-generic/mutex-xchg.h b/include/asm-generic/mutex-xchg.h
> > > index 580a6d35c7..44a66c99c8 100644
> > > --- a/include/asm-generic/mutex-xchg.h
> > > +++ b/include/asm-generic/mutex-xchg.h
> > > @@ -25,8 +25,11 @@
> > >  static inline void
> > >  __mutex_fastpath_lock(atomic_t *count, void (*fail_fn)(atomic_t *))
> > >  {
> > > -	if (unlikely(atomic_xchg(count, 0) != 1))
> > > -		fail_fn(count);
> > > +	if (unlikely(atomic_xchg(count, 0) != 1)) {
> > > +		/* Mark lock contention explicitly */
> > > +		if (likely(atomic_xchg(count, -1) != 1))
> > > +			fail_fn(count);
> > > +	}
> > >  }
> > >  
> > >  /**
> > 
> > Doesn't this mean that we're no longer just swapping 0 for a 0 if the lock
> > was taken, therefore needlessly sending the current owner down the slowpath
> > on unlock?
> 
> If the lock was taken, this means the count was either 0 or -1.  If it 
> was 1 then we just put a 0 there and we own it.  But if the cound was 0 
> then we should store -1 instead, which is what the inner xchg does.  If 
> the count was already -1 then we store -1 back.  That more closely mimic 
> what the atomic dec does which is what we want.

Ok, I just wasn't sure that marking the lock contended was required when it
was previously locked, given that we'll drop into spinning on the owner
anyway.

I'll add a commit message to the above and re-post if that's ok?

Will

RFC: mutex: hung tasks on SMP platforms with asm-generic/mutex-xchg.h

[Nicolas Pitre]

On Thu, 9 Aug 2012, Will Deacon wrote:

> On Thu, Aug 09, 2012 at 07:09:02PM +0100, Nicolas Pitre wrote:
> > On Thu, 9 Aug 2012, Will Deacon wrote:
> > > On Thu, Aug 09, 2012 at 05:57:33PM +0100, Nicolas Pitre wrote:
> > > > On Thu, 9 Aug 2012, Nicolas Pitre wrote:
> > > > diff --git a/include/asm-generic/mutex-xchg.h b/include/asm-generic/mutex-xchg.h
> > > > index 580a6d35c7..44a66c99c8 100644
> > > > --- a/include/asm-generic/mutex-xchg.h
> > > > +++ b/include/asm-generic/mutex-xchg.h
> > > > @@ -25,8 +25,11 @@
> > > >  static inline void
> > > >  __mutex_fastpath_lock(atomic_t *count, void (*fail_fn)(atomic_t *))
> > > >  {
> > > > -	if (unlikely(atomic_xchg(count, 0) != 1))
> > > > -		fail_fn(count);
> > > > +	if (unlikely(atomic_xchg(count, 0) != 1)) {
> > > > +		/* Mark lock contention explicitly */
> > > > +		if (likely(atomic_xchg(count, -1) != 1))
> > > > +			fail_fn(count);
> > > > +	}
> > > >  }
> > > >  
> > > >  /**
> > > 
> > > Doesn't this mean that we're no longer just swapping 0 for a 0 if the lock
> > > was taken, therefore needlessly sending the current owner down the slowpath
> > > on unlock?
> > 
> > If the lock was taken, this means the count was either 0 or -1.  If it 
> > was 1 then we just put a 0 there and we own it.  But if the cound was 0 
> > then we should store -1 instead, which is what the inner xchg does.  If 
> > the count was already -1 then we store -1 back.  That more closely mimic 
> > what the atomic dec does which is what we want.
> 
> Ok, I just wasn't sure that marking the lock contended was required when it
> was previously locked, given that we'll drop into spinning on the owner
> anyway.

That's fine, and the owner will put 1 back when it unlocks it as well as 
processing the wait queue which is what we need.

> I'll add a commit message to the above and re-post if that's ok?

Sure.  Don't forget to update __mutex_fastpath_lock_retval() as well.


Nicolas

RFC: mutex: hung tasks on SMP platforms with asm-generic/mutex-xchg.h

[Peter Zijlstra]

On Thu, 2012-08-09 at 12:57 -0400, Nicolas Pitre wrote:
> 
> In other words, I think this should look like this:
> 
> diff --git a/include/asm-generic/mutex-xchg.h b/include/asm-generic/mutex-xchg.h
> index 580a6d35c7..44a66c99c8 100644
> --- a/include/asm-generic/mutex-xchg.h
> +++ b/include/asm-generic/mutex-xchg.h
> @@ -25,8 +25,11 @@
>  static inline void
>  __mutex_fastpath_lock(atomic_t *count, void (*fail_fn)(atomic_t *))
>  {
> -       if (unlikely(atomic_xchg(count, 0) != 1))
> -               fail_fn(count);
> +       if (unlikely(atomic_xchg(count, 0) != 1)) {
> +               /* Mark lock contention explicitly */
> +               if (likely(atomic_xchg(count, -1) != 1))
> +                       fail_fn(count);
> +       }
>  } 

OK, I like this.. Thanks guys! Will will you send a final and complete
patch?

RFC: mutex: hung tasks on SMP platforms with asm-generic/mutex-xchg.h

[Will Deacon]

Hi Peter,

On Mon, Aug 13, 2012 at 09:15:04AM +0100, Peter Zijlstra wrote:
> On Thu, 2012-08-09 at 12:57 -0400, Nicolas Pitre wrote:
> > 
> > In other words, I think this should look like this:
> > 
> > diff --git a/include/asm-generic/mutex-xchg.h b/include/asm-generic/mutex-xchg.h
> > index 580a6d35c7..44a66c99c8 100644
> > --- a/include/asm-generic/mutex-xchg.h
> > +++ b/include/asm-generic/mutex-xchg.h
> > @@ -25,8 +25,11 @@
> >  static inline void
> >  __mutex_fastpath_lock(atomic_t *count, void (*fail_fn)(atomic_t *))
> >  {
> > -       if (unlikely(atomic_xchg(count, 0) != 1))
> > -               fail_fn(count);
> > +       if (unlikely(atomic_xchg(count, 0) != 1)) {
> > +               /* Mark lock contention explicitly */
> > +               if (likely(atomic_xchg(count, -1) != 1))
> > +                       fail_fn(count);
> > +       }
> >  } 
> 
> OK, I like this.. Thanks guys! Will will you send a final and complete
> patch?

I sent one out on Friday but somehow managed to drop you from CC -- sorry
about that:

  http://thread.gmane.org/gmane.linux.kernel/1341305

Cheers,

Will

RFC: mutex: hung tasks on SMP platforms with asm-generic/mutex-xchg.h

[Nicolas Pitre]

On Mon, 13 Aug 2012, Peter Zijlstra wrote:

> OK, I like this.. Thanks guys! Will will you send a final and complete
> patch?

Here it is:

--- >8

Date: Fri, 10 Aug 2012 15:22:09 +0100
From: Will Deacon <will.deacon@arm.com>
Subject: [PATCH] mutex: place lock in contended state after fastpath_lock failure

ARM recently moved to asm-generic/mutex-xchg.h for its mutex
implementation after the previous implementation was found to be missing
some crucial memory barriers. However, this has revealed some problems
running hackbench on SMP platforms due to the way in which the
MUTEX_SPIN_ON_OWNER code operates.

The symptoms are that a bunch of hackbench tasks are left waiting on an
unlocked mutex and therefore never get woken up to claim it. This boils
down to the following sequence of events:

        Task A        Task B        Task C        Lock value
0                                                     1
1       lock()                                        0
2                     lock()                          0
3                     spin(A)                         0
4       unlock()                                      1
5                                   lock()            0
6                     cmpxchg(1,0)                    0
7                     contended()                    -1
8       lock()                                        0
9       spin(C)                                       0
10                                  unlock()          1
11      cmpxchg(1,0)                                  0
12      unlock()                                      1

At this point, the lock is unlocked, but Task B is in an uninterruptible
sleep with nobody to wake it up.

This patch fixes the problem by ensuring we put the lock into the
contended state if we fail to acquire it on the fastpath, ensuring that
any blocked waiters are woken up when the mutex is released.

Cc: Arnd Bergmann <arnd@arndb.de>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Chris Mason <chris.mason@fusionio.com>
Cc: Ingo Molnar <mingo@elte.hu>
Cc: <stable@vger.kernel.org>
Signed-off-by: Will Deacon <will.deacon@arm.com>
Reviewed-by: Nicolas Pitre <nico@linaro.org>
---

 include/asm-generic/mutex-xchg.h |   11 +++++++++--
 1 files changed, 9 insertions(+), 2 deletions(-)

diff --git a/include/asm-generic/mutex-xchg.h b/include/asm-generic/mutex-xchg.h
index 580a6d3..c04e0db 100644
--- a/include/asm-generic/mutex-xchg.h
+++ b/include/asm-generic/mutex-xchg.h
@@ -26,7 +26,13 @@ static inline void
 __mutex_fastpath_lock(atomic_t *count, void (*fail_fn)(atomic_t *))
 {
 	if (unlikely(atomic_xchg(count, 0) != 1))
-		fail_fn(count);
+		/*
+		 * We failed to acquire the lock, so mark it contended
+		 * to ensure that any waiting tasks are woken up by the
+		 * unlock slow path.
+		 */
+		if (likely(atomic_xchg(count, -1) != 1))
+			fail_fn(count);
 }
 
 /**
@@ -43,7 +49,8 @@ static inline int
 __mutex_fastpath_lock_retval(atomic_t *count, int (*fail_fn)(atomic_t *))
 {
 	if (unlikely(atomic_xchg(count, 0) != 1))
-		return fail_fn(count);
+		if (likely(atomic_xchg(count, -1) != 1))
+			return fail_fn(count);
 	return 0;
 }
 

RFC: mutex: hung tasks on SMP platforms with asm-generic/mutex-xchg.h

[Peter Zijlstra]

On Mon, 2012-08-13 at 09:35 -0400, Nicolas Pitre wrote:
> Date: Fri, 10 Aug 2012 15:22:09 +0100
> From: Will Deacon <will.deacon@arm.com>
> Subject: [PATCH] mutex: place lock in contended state after fastpath_lock failure
> 
> ARM recently moved to asm-generic/mutex-xchg.h for its mutex
> implementation after the previous implementation was found to be missing
> some crucial memory barriers. However, this has revealed some problems
> running hackbench on SMP platforms due to the way in which the
> MUTEX_SPIN_ON_OWNER code operates.
> 
> The symptoms are that a bunch of hackbench tasks are left waiting on an
> unlocked mutex and therefore never get woken up to claim it. This boils
> down to the following sequence of events:
> 
>         Task A        Task B        Task C        Lock value
> 0                                                     1
> 1       lock()                                        0
> 2                     lock()                          0
> 3                     spin(A)                         0
> 4       unlock()                                      1
> 5                                   lock()            0
> 6                     cmpxchg(1,0)                    0
> 7                     contended()                    -1
> 8       lock()                                        0
> 9       spin(C)                                       0
> 10                                  unlock()          1
> 11      cmpxchg(1,0)                                  0
> 12      unlock()                                      1
> 
> At this point, the lock is unlocked, but Task B is in an uninterruptible
> sleep with nobody to wake it up.
> 
> This patch fixes the problem by ensuring we put the lock into the
> contended state if we fail to acquire it on the fastpath, ensuring that
> any blocked waiters are woken up when the mutex is released.
> 
> Cc: Arnd Bergmann <arnd@arndb.de>
> Cc: Thomas Gleixner <tglx@linutronix.de>
> Cc: Chris Mason <chris.mason@fusionio.com>
> Cc: Ingo Molnar <mingo@elte.hu>
> Cc: <stable@vger.kernel.org>
> Signed-off-by: Will Deacon <will.deacon@arm.com>
> Reviewed-by: Nicolas Pitre <nico@linaro.org> 

Acked-by: Peter Zijlstra <a.p.zijlstra@chello.nl>


Will you carry this through the ARM tree or do you want me/Ingo to take
it?

RFC: mutex: hung tasks on SMP platforms with asm-generic/mutex-xchg.h

[Will Deacon]

On Mon, Aug 13, 2012 at 03:05:17PM +0100, Peter Zijlstra wrote:
> Acked-by: Peter Zijlstra <a.p.zijlstra@chello.nl>

Thanks Peter.

> Will you carry this through the ARM tree or do you want me/Ingo to take
> it?

Please can you guys take it? The move to mutex-dec can go through the ARM
tree but it's probably best if you take the core change.

Cheers,

Will

RFC: mutex: hung tasks on SMP platforms with asm-generic/mutex-xchg.h

[Peter Zijlstra]

On Mon, 2012-08-13 at 15:11 +0100, Will Deacon wrote:
> 
> > Will you carry this through the ARM tree or do you want me/Ingo to take
> > it?
> 
> Please can you guys take it? The move to mutex-dec can go through the ARM
> tree but it's probably best if you take the core change. 

OK, done. Thanks!