[PATCH] x86/spinlocks: Fix regression in spinlock contention detection

[PATCH] x86/spinlocks: Fix regression in spinlock contention detection

[Tahsin Erdogan]

A spinlock is regarded as contended when there is at least one waiter.
Currently, the code that checks whether there are any waiters rely on
tail value being greater than head. However, this is not true if tail
reaches the max value and wraps back to zero, so arch_spin_is_contended()
incorrectly returns 0 (not contended) when tail is smaller than head.

The original code (before regression) handled this case by casting the
(tail - head) to an unsigned value. This change simply restores that
behavior.

Fixes: d6abfdb20223 ("x86/spinlocks/paravirt: Fix memory corruption on
unlock")
Signed-off-by: Tahsin Erdogan <tahsin@google.com>
---
 arch/x86/include/asm/spinlock.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/arch/x86/include/asm/spinlock.h b/arch/x86/include/asm/spinlock.h
index cf87de3..64b6117 100644
--- a/arch/x86/include/asm/spinlock.h
+++ b/arch/x86/include/asm/spinlock.h
@@ -169,7 +169,7 @@ static inline int arch_spin_is_contended(arch_spinlock_t *lock)
 	struct __raw_tickets tmp = READ_ONCE(lock->tickets);
 
 	tmp.head &= ~TICKET_SLOWPATH_FLAG;
-	return (tmp.tail - tmp.head) > TICKET_LOCK_INC;
+	return (__ticket_t)(tmp.tail - tmp.head) > TICKET_LOCK_INC;
 }
 #define arch_spin_is_contended	arch_spin_is_contended
 
-- 
2.2.0.rc0.207.ga3a616c

[tip:x86/urgent] x86/spinlocks: Fix regression in spinlock contention detection

[tip-bot for Tahsin Erdogan]

Commit-ID:  e8a4a2696fecb398b0288c43c0e0dbb91e265bb2
Gitweb:     http://git.kernel.org/tip/e8a4a2696fecb398b0288c43c0e0dbb91e265bb2
Author:     Tahsin Erdogan <tahsin@google.com>
AuthorDate: Mon, 4 May 2015 21:15:31 -0700
Committer:  Thomas Gleixner <tglx@linutronix.de>
CommitDate: Tue, 5 May 2015 11:01:38 +0200

x86/spinlocks: Fix regression in spinlock contention detection

A spinlock is regarded as contended when there is at least one waiter.
Currently, the code that checks whether there are any waiters rely on
tail value being greater than head. However, this is not true if tail
reaches the max value and wraps back to zero, so arch_spin_is_contended()
incorrectly returns 0 (not contended) when tail is smaller than head.

The original code (before regression) handled this case by casting the
(tail - head) to an unsigned value. This change simply restores that
behavior.

Fixes: d6abfdb20223 ("x86/spinlocks/paravirt: Fix memory corruption on unlock")
Signed-off-by: Tahsin Erdogan <tahsin@google.com>
Cc: peterz@infradead.org
Cc: Waiman.Long@hp.com
Cc: borntraeger@de.ibm.com
Cc: oleg@redhat.com
Cc: raghavendra.kt@linux.vnet.ibm.com
Cc: stable@vger.kernel.org
Link: http://lkml.kernel.org/r/1430799331-20445-1-git-send-email-tahsin@google.com
Signed-off-by: Thomas Gleixner <tglx@linutronix.de>
---
 arch/x86/include/asm/spinlock.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/arch/x86/include/asm/spinlock.h b/arch/x86/include/asm/spinlock.h
index cf87de3..64b6117 100644
--- a/arch/x86/include/asm/spinlock.h
+++ b/arch/x86/include/asm/spinlock.h
@@ -169,7 +169,7 @@ static inline int arch_spin_is_contended(arch_spinlock_t *lock)
 	struct __raw_tickets tmp = READ_ONCE(lock->tickets);
 
 	tmp.head &= ~TICKET_SLOWPATH_FLAG;
-	return (tmp.tail - tmp.head) > TICKET_LOCK_INC;
+	return (__ticket_t)(tmp.tail - tmp.head) > TICKET_LOCK_INC;
 }
 #define arch_spin_is_contended	arch_spin_is_contended
 

Re: [PATCH] x86/spinlocks: Fix regression in spinlock contention detection

[Peter Zijlstra]

On Mon, May 04, 2015 at 09:15:31PM -0700, Tahsin Erdogan wrote:
> A spinlock is regarded as contended when there is at least one waiter.
> Currently, the code that checks whether there are any waiters rely on
> tail value being greater than head. However, this is not true if tail
> reaches the max value and wraps back to zero, so arch_spin_is_contended()
> incorrectly returns 0 (not contended) when tail is smaller than head.
> 
> The original code (before regression) handled this case by casting the
> (tail - head) to an unsigned value. This change simply restores that
> behavior.
> 
> Fixes: d6abfdb20223 ("x86/spinlocks/paravirt: Fix memory corruption on
> unlock")
> Signed-off-by: Tahsin Erdogan <tahsin@google.com>
> ---
>  arch/x86/include/asm/spinlock.h | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/arch/x86/include/asm/spinlock.h b/arch/x86/include/asm/spinlock.h
> index cf87de3..64b6117 100644
> --- a/arch/x86/include/asm/spinlock.h
> +++ b/arch/x86/include/asm/spinlock.h
> @@ -169,7 +169,7 @@ static inline int arch_spin_is_contended(arch_spinlock_t *lock)
>  	struct __raw_tickets tmp = READ_ONCE(lock->tickets);
>  
>  	tmp.head &= ~TICKET_SLOWPATH_FLAG;
> -	return (tmp.tail - tmp.head) > TICKET_LOCK_INC;
> +	return (__ticket_t)(tmp.tail - tmp.head) > TICKET_LOCK_INC;

I'm not seeing it, everything in that expression is of __ticket_t type
(tail, head and TICKET_LOCK_INC), nothing should cause it to be cast to
another type due to conversion rules.

Or does - always cast to a signed type? Lemme go grab the C rules again.

I'm not seeing it.. Please explain better, iow. your changelog fails to
properly explain the problem.

Re: [PATCH] x86/spinlocks: Fix regression in spinlock contention detection

[Raghavendra K T]

On 05/05/2015 02:47 PM, Peter Zijlstra wrote:
> On Mon, May 04, 2015 at 09:15:31PM -0700, Tahsin Erdogan wrote:
>> A spinlock is regarded as contended when there is at least one waiter.
>> Currently, the code that checks whether there are any waiters rely on
>> tail value being greater than head. However, this is not true if tail
>> reaches the max value and wraps back to zero, so arch_spin_is_contended()
>> incorrectly returns 0 (not contended) when tail is smaller than head.
>>
>> The original code (before regression) handled this case by casting the
>> (tail - head) to an unsigned value. This change simply restores that
>> behavior.
>>
>> Fixes: d6abfdb20223 ("x86/spinlocks/paravirt: Fix memory corruption on
>> unlock")
>> Signed-off-by: Tahsin Erdogan <tahsin@google.com>
>> ---
>>   arch/x86/include/asm/spinlock.h | 2 +-
>>   1 file changed, 1 insertion(+), 1 deletion(-)
>>
>> diff --git a/arch/x86/include/asm/spinlock.h b/arch/x86/include/asm/spinlock.h
>> index cf87de3..64b6117 100644
>> --- a/arch/x86/include/asm/spinlock.h
>> +++ b/arch/x86/include/asm/spinlock.h
>> @@ -169,7 +169,7 @@ static inline int arch_spin_is_contended(arch_spinlock_t *lock)
>>   	struct __raw_tickets tmp = READ_ONCE(lock->tickets);
>>
>>   	tmp.head &= ~TICKET_SLOWPATH_FLAG;
>> -	return (tmp.tail - tmp.head) > TICKET_LOCK_INC;
>> +	return (__ticket_t)(tmp.tail - tmp.head) > TICKET_LOCK_INC;
>
> I'm not seeing it, everything in that expression is of __ticket_t type
> (tail, head and TICKET_LOCK_INC), nothing should cause it to be cast to
> another type due to conversion rules.
>
> Or does - always cast to a signed type? Lemme go grab the C rules again.
>
> I'm not seeing it.. Please explain better, iow. your changelog fails to
> properly explain the problem.
>

Same from me here.

Did you really see a regression?

I am not seeing two unsigned value subtraction resulting in a negative
value.

================
#include <stdio.h>

#define LOCK_INC 2

int main()
{
         unsigned int head = 32700, tail=2;

         if ((tail - head) > LOCK_INC)
                 printf(" tail - head > LOCK_INC \n");
         else
                 printf(" tail - head < LOCK_INC \n");

         return 0;
}

Re: [PATCH] x86/spinlocks: Fix regression in spinlock contention detection

[Peter Zijlstra]

On Tue, May 05, 2015 at 04:08:22PM +0530, Raghavendra K T wrote:
> ================
> #include <stdio.h>
> 
> #define LOCK_INC 2

Note that to be completely identical to the kernel code you should've
written:

#define LOCK_INC	((unsigned int)2)

as per:

#define TICKET_LOCK_INC ((__ticket_t)__TICKET_LOCK_INC)

Re: [PATCH] x86/spinlocks: Fix regression in spinlock contention detection

[Tahsin Erdogan]

The conversion to signed happens with types shorter than int
(__ticket_t is either u8 or u16).

By changing Raghavendra's program to use unsigned short int, you can
see the problem:

================
#include <stdio.h>

#define LOCK_INC 2

int main()
{
        unsigned short int head = 32700, tail=2;

        if ((tail - head) > LOCK_INC)
                printf(" tail - head > LOCK_INC \n");
        else
                printf(" tail - head < LOCK_INC \n");

        return 0;
}

================
gcc -g -o t main.c
./t
 tail - head < LOCK_INC

However, having just unsigned int returns the opposite result
(unsigned int head = 32700, tail=2;)

gcc -g -o t main.c
./t
 tail - head > LOCK_INC

On Tue, May 5, 2015 at 3:58 AM, Peter Zijlstra <peterz@infradead.org> wrote:
> On Tue, May 05, 2015 at 04:08:22PM +0530, Raghavendra K T wrote:
>> ================
>> #include <stdio.h>
>>
>> #define LOCK_INC 2
>
> Note that to be completely identical to the kernel code you should've
> written:
>
> #define LOCK_INC        ((unsigned int)2)
>
> as per:
>
> #define TICKET_LOCK_INC ((__ticket_t)__TICKET_LOCK_INC)
>
>

Re: [PATCH] x86/spinlocks: Fix regression in spinlock contention detection

[Peter Zijlstra]

On Tue, May 05, 2015 at 07:10:19AM -0700, Tahsin Erdogan wrote:
> The conversion to signed happens with types shorter than int
> (__ticket_t is either u8 or u16).

Argh yes, I see.

(ISO C99) 6.3.1.1 rule 2 states that: "If an int can represent all values
of the original type, the value is converted to an int;... "

Originally I had only looked at: 6.3.1.8 Usual arithmetic conversions,
which has the following bit: "If both operands have the same type, then
no further conversion is needed."

Looking more closely, a sentence prior to that states: "Otherwise,
the integer promotions are performed on both operands." which brings us
back to that 6.3.1.1 rule 2.


I've slightly modified your Changelog to explicitly state this.

---
Subject: x86/spinlocks: Fix regression in spinlock contention detection
From: Tahsin Erdogan <tahsin@google.com>
Date: Mon, 4 May 2015 21:15:31 -0700

A spinlock is regarded as contended when there is at least one waiter.

Currently, the code that checks whether there are any waiters rely on
tail value being greater than head. However, this is not true if tail
reaches the max value and wraps back to zero, so arch_spin_is_contended()
incorrectly returns 0 (not contended) when tail is smaller than head.

This is because the normal C integer promotion rules will promote
__ticket_t to int because its of lower rank (u8,u16 < int).

The original code (before regression) handled this case by casting the
(tail - head) to an unsigned value. This change simply restores that
behavior.

Cc: hpa@zytor.com
Cc: x86@kernel.org
Cc: Waiman.Long@hp.com
Cc: borntraeger@de.ibm.com
Cc: oleg@redhat.com
Cc: raghavendra.kt@linux.vnet.ibm.com
Cc: tglx@linutronix.de
Cc: mingo@redhat.com
Fixes: d6abfdb20223 ("x86/spinlocks/paravirt: Fix memory corruption on unlock")
Signed-off-by: Tahsin Erdogan <tahsin@google.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Link: http://lkml.kernel.org/r/1430799331-20445-1-git-send-email-tahsin@google.com
---
 arch/x86/include/asm/spinlock.h |    2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

--- a/arch/x86/include/asm/spinlock.h
+++ b/arch/x86/include/asm/spinlock.h
@@ -173,7 +173,7 @@ static inline int arch_spin_is_contended
 	struct __raw_tickets tmp = READ_ONCE(lock->tickets);
 
 	tmp.head &= ~TICKET_SLOWPATH_FLAG;
-	return (tmp.tail - tmp.head) > TICKET_LOCK_INC;
+	return (__ticket_t)(tmp.tail - tmp.head) > TICKET_LOCK_INC;
 }
 #define arch_spin_is_contended	arch_spin_is_contended
 

Re: [PATCH] x86/spinlocks: Fix regression in spinlock contention detection

[Raghavendra K T]

On 05/05/2015 07:33 PM, Tahsin Erdogan wrote:
> The conversion to signed happens with types shorter than int (__ticket_t
> is either u8 or u16).
>
> By changing Raghavendra's program to use unsigned short int, you can see
> the problem:
>
> ================
> #include <stdio.h>
>
> #define LOCK_INC 2
>
> int main()
> {
>          unsigned short int head = 32700, tail=2;
>
>          if ((tail - head) > LOCK_INC)
>                  printf(" tail - head > LOCK_INC \n");
>          else
>                  printf(" tail - head < LOCK_INC \n");
>
>          return 0;
> }
>
> ================
> gcc -g -o t main.c
> ./t
>   tail - head < LOCK_INC
>
> However, having just unsigned int returns the opposite result (unsigned
> int head = 32700, tail=2;)
>

Interestingly,

#include <stdio.h>

//#define LOCK_INC ((unsigned int)2) // case 1
#define LOCK_INC 2 //case 2

int main()
{
	unsigned short int head = 32700, tail=2;

	if ((tail - head) > LOCK_INC)
		printf(" tail - head > LOCK_INC \n");
	else
		printf(" tail - head < LOCK_INC \n");

	return 0;
}

case 1 works here (PeterZ's stricter version)

case 2 gives tail - head < LOCK_INC

But is it not that we have case 1 we are looking here ?

Re: [PATCH] x86/spinlocks: Fix regression in spinlock contention detection

[Tahsin Erdogan]

//#define LOCK_INC ((unsigned int)2) // case 1

This works because it is casting to unsigned int. If you change it to
unsigned short int, it becomes consistent with case 2.

On Tue, May 5, 2015 at 8:25 AM, Raghavendra K T
<raghavendra.kt@linux.vnet.ibm.com> wrote:
> On 05/05/2015 07:33 PM, Tahsin Erdogan wrote:
>>
>> The conversion to signed happens with types shorter than int (__ticket_t
>> is either u8 or u16).
>>
>> By changing Raghavendra's program to use unsigned short int, you can see
>> the problem:
>>
>> ================
>> #include <stdio.h>
>>
>> #define LOCK_INC 2
>>
>> int main()
>> {
>>          unsigned short int head = 32700, tail=2;
>>
>>          if ((tail - head) > LOCK_INC)
>>                  printf(" tail - head > LOCK_INC \n");
>>          else
>>                  printf(" tail - head < LOCK_INC \n");
>>
>>          return 0;
>> }
>>
>> ================
>> gcc -g -o t main.c
>> ./t
>>   tail - head < LOCK_INC
>>
>> However, having just unsigned int returns the opposite result (unsigned
>> int head = 32700, tail=2;)
>>
>
> Interestingly,
>
> #include <stdio.h>
>
> //#define LOCK_INC ((unsigned int)2) // case 1
> #define LOCK_INC 2 //case 2
>
> int main()
> {
>         unsigned short int head = 32700, tail=2;
>
>         if ((tail - head) > LOCK_INC)
>                 printf(" tail - head > LOCK_INC \n");
>         else
>                 printf(" tail - head < LOCK_INC \n");
>
>         return 0;
> }
>
> case 1 works here (PeterZ's stricter version)
>
> case 2 gives tail - head < LOCK_INC
>
> But is it not that we have case 1 we are looking here ?
>
>

Re: [PATCH] x86/spinlocks: Fix regression in spinlock contention detection

[Waiman Long]

On 05/05/2015 11:25 AM, Raghavendra K T wrote:
> On 05/05/2015 07:33 PM, Tahsin Erdogan wrote:
>> The conversion to signed happens with types shorter than int (__ticket_t
>> is either u8 or u16).
>>
>> By changing Raghavendra's program to use unsigned short int, you can see
>> the problem:
>>
>> ================
>> #include <stdio.h>
>>
>> #define LOCK_INC 2
>>
>> int main()
>> {
>>          unsigned short int head = 32700, tail=2;
>>
>>          if ((tail - head) > LOCK_INC)
>>                  printf(" tail - head > LOCK_INC \n");
>>          else
>>                  printf(" tail - head < LOCK_INC \n");
>>
>>          return 0;
>> }
>>
>> ================
>> gcc -g -o t main.c
>> ./t
>>   tail - head < LOCK_INC
>>
>> However, having just unsigned int returns the opposite result (unsigned
>> int head = 32700, tail=2;)
>>
>
> Interestingly,
>
> #include <stdio.h>
>
> //#define LOCK_INC ((unsigned int)2) // case 1
> #define LOCK_INC 2 //case 2
>
> int main()
> {
>     unsigned short int head = 32700, tail=2;
>
>     if ((tail - head) > LOCK_INC)
>         printf(" tail - head > LOCK_INC \n");
>     else
>         printf(" tail - head < LOCK_INC \n");
>
>     return 0;
> }
>
> case 1 works here (PeterZ's stricter version)
>
> case 2 gives tail - head < LOCK_INC
>
> But is it not that we have case 1 we are looking here ?
>
>

__TICKET_LOCK_INC is currently ((unsigned short)2), not ((unsigned 
int)2). That makes a difference.

Cheers,
Longman

Re: [PATCH] x86/spinlocks: Fix regression in spinlock contention detection

[Raghavendra K T]

On 05/05/2015 09:02 PM, Waiman Long wrote:
> On 05/05/2015 11:25 AM, Raghavendra K T wrote:
>> On 05/05/2015 07:33 PM, Tahsin Erdogan wrote:
>>> The conversion to signed happens with types shorter than int (__ticket_t
>>> is either u8 or u16).
>>>
>>> By changing Raghavendra's program to use unsigned short int, you can see
>>> the problem:
>>>
>>> ================
>>> #include <stdio.h>
>>>
>>> #define LOCK_INC 2
>>>
>>> int main()
>>> {
>>>          unsigned short int head = 32700, tail=2;
>>>
>>>          if ((tail - head) > LOCK_INC)
>>>                  printf(" tail - head > LOCK_INC \n");
>>>          else
>>>                  printf(" tail - head < LOCK_INC \n");
>>>
>>>          return 0;
>>> }
>>>
>>> ================
>>> gcc -g -o t main.c
>>> ./t
>>>   tail - head < LOCK_INC
>>>
>>> However, having just unsigned int returns the opposite result (unsigned
>>> int head = 32700, tail=2;)
>>>
>>
>> Interestingly,
>>
>> #include <stdio.h>
>>
>> //#define LOCK_INC ((unsigned int)2) // case 1
>> #define LOCK_INC 2 //case 2
>>
>> int main()
>> {
>>     unsigned short int head = 32700, tail=2;
>>
>>     if ((tail - head) > LOCK_INC)
>>         printf(" tail - head > LOCK_INC \n");
>>     else
>>         printf(" tail - head < LOCK_INC \n");
>>
>>     return 0;
>> }
>>
>> case 1 works here (PeterZ's stricter version)
>>
>> case 2 gives tail - head < LOCK_INC
>>
>> But is it not that we have case 1 we are looking here ?
>>
>>
>
> __TICKET_LOCK_INC is currently ((unsigned short)2), not ((unsigned
> int)2). That makes a difference.
>

aah missed that part :). That makes sense.

Good catch Tahsin.

Re: [PATCH] x86/spinlocks: Fix regression in spinlock contention detection

[Raghavendra K T]

On 05/05/2015 09:45 AM, Tahsin Erdogan wrote:
> A spinlock is regarded as contended when there is at least one waiter.
> Currently, the code that checks whether there are any waiters rely on
> tail value being greater than head. However, this is not true if tail
> reaches the max value and wraps back to zero, so arch_spin_is_contended()
> incorrectly returns 0 (not contended) when tail is smaller than head.
>
> The original code (before regression) handled this case by casting the
> (tail - head) to an unsigned value. This change simply restores that
> behavior.
>
> Fixes: d6abfdb20223 ("x86/spinlocks/paravirt: Fix memory corruption on
> unlock")
> Signed-off-by: Tahsin Erdogan <tahsin@google.com>
> ---

Tahsin,
Perhaps we need to CC stable (3.19) too..?

Re: [PATCH] x86/spinlocks: Fix regression in spinlock contention detection

[Tahsin Erdogan]

> Perhaps we need to CC stable (3.19) too..?
>

Hi Greg,
Could you please push this patch to 3.19 ?

commit sha: e8a4a2696fecb398b0288c43c0e0dbb91e265bb2

thanks

Re: [PATCH] x86/spinlocks: Fix regression in spinlock contention detection

[Greg KH]

On Thu, May 07, 2015 at 12:13:22AM -0700, Tahsin Erdogan wrote:
> > Perhaps we need to CC stable (3.19) too..?
> >
> 
> Hi Greg,
> Could you please push this patch to 3.19 ?
> 
> commit sha: e8a4a2696fecb398b0288c43c0e0dbb91e265bb2

It's not even in a released version from Linus, so I can't add it to
anything.  I have to wait for it to be in a release before I can add it
to the stable tree.

Also, it's already marked for stable, so you don't have to do anything
special it will show up normally.

However, 3.19 is now end-of-life.  I'm doing a release for it in a few
hours, with only a small number of fixes in it.  Everyone should move to
4.0 by now, so this will not end up in a 3.19-stable release, sorry.

thanks,

greg k-h