x86: convert ticketlocks to C and remove duplicate code
Subsystems (2)
cover x86: convert ticketlocks to C and remove duplicate code
From: Jeremy Fitzhardinge <[email protected]>
Hi all,
I'm proposing this series for 3[.0].1.
This is a repost of a series to clean up the x86 ticket lock code by converting it to a mostly C implementation and removing lots of duplicate code relating to the ticket size.
The last time I posted this series, the only significant comments were from Nick Piggin, specifically relating to:
1. A wrongly placed barrier on unlock (which may have allowed the compiler to move things out of the locked region. I went belt-and-suspenders by having two barriers to prevent motion into or out of the locked region.
2. With NR_CPUS < 256 the ticket size is 8 bits. The compiler doesn't use the same trick as the hand-coded asm to directly compare the high and low bytes in the word, but does a bit of extra shuffling around. However, the Intel optimisation guide and several x86 experts have opined that its best to avoid the high-byte operations anyway, since they will cause a partial word stall, and the gcc-generated code should be better.
Overall the compiler-generated code is very similar to the hand-coded versions, with the partial byte operations being the only significant difference. (Curiously, gcc does generate a high-byte compare for me in trylock, so it can if it wants to.)
I've been running with this code in place for several months on 4 core systems without any problems.
I couldn't measure a consistent performance difference between the two implemenations; there seemed to be +/- ~1% +/-, which is the level of variation I see from simply recompiling the kernel with slightly different code alignment.
Overall, I think the large reduction in code size is a big win.
Thanks,
J
Jeremy Fitzhardinge (7):
x86/ticketlock: clean up types and accessors x86/ticketlock: convert spin loop to C
x86/ticketlock: Use C for __ticket_spin_unlock x86/ticketlock: make large and small ticket versions of spin_lock the
same
x86/ticketlock: make __ticket_spin_lock common x86/ticketlock: make __ticket_spin_trylock common x86/ticketlock: prevent memory accesses from reordered out of lock
region
arch/x86/include/asm/spinlock.h | 147 ++++++++++++--------------------- arch/x86/include/asm/spinlock_types.h | 22 +++++- 2 files changed, 74 insertions(+), 95 deletions(-)
Signature · 1 line
1.7.5.4
PATCH 1/7 x86/ticketlock: clean up types and accessors
From: Jeremy Fitzhardinge <[email protected]>
A few cleanups to the way spinlocks are defined and accessed:
- define __ticket_t which is the size of a spinlock ticket (ie, enough bits to hold all the cpus)
- Define struct arch_spinlock as a union containing plain slock and the head and tail tickets
- Use head and tail to implement some of the spinlock predicates.
- Make all ticket variables unsigned.
- Use TICKET_SHIFT to form constants
Most of this will be used in later patches.
--- arch/x86/include/asm/spinlock.h | 24 ++++++++++-------------- arch/x86/include/asm/spinlock_types.h | 20 ++++++++++++++++++-- 2 files changed, 28 insertions(+), 16 deletions(-)
arch/x86/include/asm/spinlock.h +10 -14
@@ -56,11 +56,9 @@* much between them in performance though, especially as locks are out of line. */ #if (NR_CPUS <256 ) -#define TICKET_SHIFT 8 - static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) { -short inc =0x0100 ; +unsigned short inc =1 <<TICKET_SHIFT ; asmvolatile ( LOCK_PREFIX "xaddw %w0, %1\n"
@@ -79,7 +77,7 @@ static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock) { -int tmp, new; +unsigned int tmp, new; asmvolatile ("movzwl %2, %0\n\t" "cmpb %h0,%b0\n\t"
@@ -104,12 +102,10 @@ static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock) : "memory", "cc"); }#else -#define TICKET_SHIFT 16 - static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) { -int inc =0x00010000 ; -int tmp; +unsigned inc =1 <<TICKET_SHIFT ; +unsigned tmp; asmvolatile (LOCK_PREFIX "xaddl %0, %1\n" "movzwl %w0, %2\n\t"
@@ -129,8 +125,8 @@ static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock) { -int tmp; -int new; +unsigned tmp; +unsigned new; asmvolatile ("movl %2,%0\n\t" "movl %0,%1\n\t"
@@ -160,16 +156,16 @@ static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)static inline int __ticket_spin_is_locked (arch_spinlock_t *lock) { -int tmp =ACCESS_ONCE (lock->slock); +struct __raw_tickets tmp =ACCESS_ONCE (lock->tickets); -return !!(((tmp >>TICKET_SHIFT ) ^ tmp) & ((1 <<TICKET_SHIFT ) -1 )); +return !!(tmp.tail ^ tmp.head); }static inline int __ticket_spin_is_contended (arch_spinlock_t *lock) { -int tmp =ACCESS_ONCE (lock->slock); +struct __raw_tickets tmp =ACCESS_ONCE (lock->tickets); -return (((tmp >>TICKET_SHIFT ) - tmp) & ((1 <<TICKET_SHIFT ) -1 )) >1 ; +return ((tmp.tail - tmp.head) &TICKET_MASK ) >1 ; }#ifndef CONFIG_PARAVIRT_SPINLOCKS
arch/x86/include/asm/spinlock_types.h +18 -2
@@ -5,11 +5,27 @@# error "please don't include this file directly"#endif +#include <linux/types.h> + +#if (CONFIG_NR_CPUS <256 ) +typedef u8 __ticket_t ; +#else +typedef u16 __ticket_t ; +#endif + +#define TICKET_SHIFT (sizeof(__ticket_t) * 8) +#define TICKET_MASK ((__ticket_t)((1 << TICKET_SHIFT) - 1)) +typedef struct arch_spinlock { -unsigned int slock; +union { +unsigned int slock; +struct __raw_tickets { +__ticket_t head, tail; + } tickets; + }; }arch_spinlock_t ; -#define __ARCH_SPIN_LOCK_UNLOCKED { 0 } +#define __ARCH_SPIN_LOCK_UNLOCKED { { .slock = 0 } } typedef struct { unsigned int lock;
Signature · 1 line
1.7.5.4
PATCH 2/7 x86/ticketlock: convert spin loop to C
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
The inner loop of __ticket_spin_lock isn't doing anything very special, so reimplement it in C.
For the 8 bit ticket lock variant, we use a register union to get direct access to the lower and upper bytes in the tickets, but unfortunately gcc won't generate a direct comparison between the two halves of the register, so the generated asm isn't quite as pretty as the hand-coded version. However benchmarking shows that this is actually a small improvement in runtime performance on some benchmarks, and never a slowdown.
We also need to make sure there's a barrier at the end of the lock loop to make sure that the compiler doesn't move any instructions from within the locked region into the region where we don't yet own the lock.
--- arch/x86/include/asm/spinlock.h | 58 +++++++++++++++++++------------------- 1 files changed, 29 insertions(+), 29 deletions(-)
arch/x86/include/asm/spinlock.h +30 -30
@@ -58,21 +58,21 @@#if (NR_CPUS <256 ) static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) { -unsigned short inc =1 <<TICKET_SHIFT ; - - asmvolatile ( -LOCK_PREFIX "xaddw %w0, %1\n" -"1:\t" -"cmpb %h0, %b0\n\t" -"je 2f\n\t" -"rep ; nop\n\t" -"movb %1, %b0\n\t" -/* don't need lfence here, because loads are in-order */ -"jmp 1b\n" -"2:" - :"+Q" (inc),"+m" (lock->slock) - : - :"memory" ,"cc" ); + registerunion { +struct __raw_tickets tickets; +unsigned short slock; + } inc = { .slock =1 <<TICKET_SHIFT }; + + asmvolatile (LOCK_PREFIX "xaddw %w0, %1\n" + :"+Q" (inc),"+m" (lock->slock) : :"memory" ,"cc" ); + +for (;;) { +if (inc.tickets.head == inc.tickets.tail) + goto out; +cpu_relax (); + inc.tickets.head =ACCESS_ONCE (lock->tickets.head); + } +out:barrier ();/* make sure nothing creeps before the lock is taken */ } static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
@@ -105,22 +105,22 @@ static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock) static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) {unsigned inc =1 <<TICKET_SHIFT ; -unsigned tmp; +__ticket_t tmp; - asmvolatile (LOCK_PREFIX "xaddl %0, %1\n" -"movzwl %w0, %2\n\t" -"shrl $16, %0\n\t" -"1:\t" -"cmpl %0, %2\n\t" -"je 2f\n\t" -"rep ; nop\n\t" -"movzwl %1, %2\n\t" -/* don't need lfence here, because loads are in-order */ -"jmp 1b\n" -"2:" - :"+r" (inc),"+m" (lock->slock),"=&r" (tmp) - : - :"memory" ,"cc" ); + asmvolatile (LOCK_PREFIX "xaddl %0, %1\n\t" + :"+r" (inc),"+m" (lock->slock) + : :"memory" ,"cc" ); + + tmp = inc; + inc >>=TICKET_SHIFT ; + +for (;;) { +if ((__ticket_t )inc == tmp) + goto out; +cpu_relax (); + tmp =ACCESS_ONCE (lock->tickets.head); + } +out:barrier ();/* make sure nothing creeps before the lock is taken */ } static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
Signature · 1 line
1.7.5.4
PATCH 3/7 x86/ticketlock: Use C for __ticket_spin_unlock
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
If we don't need to use a locked inc for unlock, then implement it in C.
--- arch/x86/include/asm/spinlock.h | 32 +++++++++++++++++--------------- 1 files changed, 17 insertions(+), 15 deletions(-)
arch/x86/include/asm/spinlock.h +17 -15
@@ -33,9 +33,21 @@* On PPro SMP or if we are using OOSTORE, we use a locked operation to unlock * (PPro errata 66, 92) */ -# define UNLOCK_LOCK_PREFIX LOCK_PREFIX +static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock) +{ +if (sizeof (lock->tickets.head) ==sizeof (u8)) + asm (LOCK_PREFIX "incb %0" + :"+m" (lock->tickets.head) : :"memory" ); +else + asm (LOCK_PREFIX "incw %0" + :"+m" (lock->tickets.head) : :"memory" ); + +}#else -# define UNLOCK_LOCK_PREFIX +static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock) +{ + lock->tickets.head++; +}#endif /*
@@ -93,14 +105,6 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)return tmp; } - -static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock) -{ - asmvolatile (UNLOCK_LOCK_PREFIX "incb %0" - :"+m" (lock->slock) - : - :"memory" ,"cc" ); -}#else static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) {
@@ -144,15 +148,13 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)return tmp; } +#endif static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock) { - asmvolatile (UNLOCK_LOCK_PREFIX "incw %0" - :"+m" (lock->slock) - : - :"memory" ,"cc" ); +__ticket_unlock_release (lock); +barrier ();/* prevent reordering into locked region */ } -#endif static inline int __ticket_spin_is_locked (arch_spinlock_t *lock) {
Signature · 1 line
1.7.5.4
PATCH 4/7 x86/ticketlock: make large and small ticket versions of spin_lock the same
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
Make the bulk of __ticket_spin_lock look identical for large and small number of cpus.
--- arch/x86/include/asm/spinlock.h | 23 ++++++++--------------- 1 files changed, 8 insertions(+), 15 deletions(-)
arch/x86/include/asm/spinlock.h +8 -15
@@ -70,19 +70,16 @@ static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)#if (NR_CPUS <256 ) static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) { - registerunion { -struct __raw_tickets tickets; -unsigned short slock; - } inc = { .slock =1 <<TICKET_SHIFT }; + registerstruct __raw_tickets inc = { .tail =1 }; asmvolatile (LOCK_PREFIX "xaddw %w0, %1\n" - :"+Q" (inc),"+m" (lock->slock) : :"memory" ,"cc" ); + :"+r" (inc),"+m" (lock->tickets) : :"memory" ,"cc" );for (;;) { -if (inc.tickets.head == inc.tickets.tail) +if (inc.head == inc.tail) goto out;cpu_relax (); - inc.tickets.head =ACCESS_ONCE (lock->tickets.head); + inc.head =ACCESS_ONCE (lock->tickets.head); } out:barrier ();/* make sure nothing creeps before the lock is taken */ }
@@ -108,21 +105,17 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)#else static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) { -unsigned inc =1 <<TICKET_SHIFT ; -__ticket_t tmp; + registerstruct __raw_tickets inc = { .tail =1 }; asmvolatile (LOCK_PREFIX "xaddl %0, %1\n\t" - :"+r" (inc),"+m" (lock->slock) + :"+r" (inc),"+m" (lock->tickets) : :"memory" ,"cc" ); - tmp = inc; - inc >>=TICKET_SHIFT ; -for (;;) { -if ((__ticket_t )inc == tmp) +if (inc.head == inc.tail) goto out;cpu_relax (); - tmp =ACCESS_ONCE (lock->tickets.head); + inc.head =ACCESS_ONCE (lock->tickets.head); } out:barrier ();/* make sure nothing creeps before the lock is taken */ }
Signature · 1 line
1.7.5.4
PATCH 5/7 x86/ticketlock: make __ticket_spin_lock common
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
Aside from the particular form of the xadd instruction, they're identical. So factor out the xadd and use common code for the rest.
--- arch/x86/include/asm/spinlock.h | 42 ++++++++++++++++++-------------------- 1 files changed, 20 insertions(+), 22 deletions(-)
arch/x86/include/asm/spinlock.h +20 -22
@@ -67,13 +67,27 @@ static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)* save some instructions and make the code more elegant. There really isn't * much between them in performance though, especially as locks are out of line. */ -#if (NR_CPUS <256 ) -static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) +static __always_inline struct __raw_tickets __ticket_spin_claim(struct arch_spinlock *lock) { - registerstruct __raw_tickets inc = { .tail =1 }; + registerstruct __raw_tickets tickets = { .tail =1 }; + +if (sizeof (lock->tickets.head) ==sizeof (u8)) + asmvolatile (LOCK_PREFIX "xaddw %w0, %1\n" + :"+r" (tickets),"+m" (lock->tickets) + : :"memory" ,"cc" ); +else + asmvolatile (LOCK_PREFIX "xaddl %0, %1\n" + :"+r" (tickets),"+m" (lock->tickets) + : :"memory" ,"cc" ); - asmvolatile (LOCK_PREFIX "xaddw %w0, %1\n" - :"+r" (inc),"+m" (lock->tickets) : :"memory" ,"cc" ); +return tickets; +} + +static __always_inline void __ticket_spin_lock(struct arch_spinlock *lock) +{ + registerstruct __raw_tickets inc; + + inc =__ticket_spin_claim (lock);for (;;) {if (inc.head == inc.tail)
@@ -84,6 +98,7 @@ static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) out:barrier ();/* make sure nothing creeps before the lock is taken */ } +#if (NR_CPUS <256 ) static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock) {unsigned int tmp, new;
@@ -103,23 +118,6 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)return tmp; }#else -static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) -{ - registerstruct __raw_tickets inc = { .tail =1 }; - - asmvolatile (LOCK_PREFIX "xaddl %0, %1\n\t" - :"+r" (inc),"+m" (lock->tickets) - : :"memory" ,"cc" ); - -for (;;) { -if (inc.head == inc.tail) - goto out; -cpu_relax (); - inc.head =ACCESS_ONCE (lock->tickets.head); - } -out:barrier ();/* make sure nothing creeps before the lock is taken */ -} - static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock) {unsigned tmp;
Signature · 1 line
1.7.5.4
PATCH 6/7 x86/ticketlock: make __ticket_spin_trylock common
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
Make trylock code common regardless of ticket size.
--- arch/x86/include/asm/spinlock.h | 49 +++++++-------------------------- arch/x86/include/asm/spinlock_types.h | 6 +++- 2 files changed, 14 insertions(+), 41 deletions(-)
arch/x86/include/asm/spinlock.h +10 -39
@@ -98,48 +98,19 @@ static __always_inline void __ticket_spin_lock(struct arch_spinlock *lock) out:barrier ();/* make sure nothing creeps before the lock is taken */ } -#if (NR_CPUS <256 ) static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock) { -unsigned int tmp, new; - - asmvolatile ("movzwl %2, %0\n\t" -"cmpb %h0,%b0\n\t" -"leal 0x100(%" REG_PTR_MODE "0), %1\n\t" -"jne 1f\n\t" -LOCK_PREFIX "cmpxchgw %w1,%2\n\t" -"1:" -"sete %b1\n\t" -"movzbl %b1,%0\n\t" - :"=&a" (tmp),"=&q" (new),"+m" (lock->slock) - : - :"memory" ,"cc" ); - -return tmp; -} -#else -static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock) -{ -unsigned tmp; -unsigned new; - - asmvolatile ("movl %2,%0\n\t" -"movl %0,%1\n\t" -"roll $16, %0\n\t" -"cmpl %0,%1\n\t" -"leal 0x00010000(%" REG_PTR_MODE "0), %1\n\t" -"jne 1f\n\t" -LOCK_PREFIX "cmpxchgl %1,%2\n\t" -"1:" -"sete %b1\n\t" -"movzbl %b1,%0\n\t" - :"=&a" (tmp),"=&q" (new),"+m" (lock->slock) - : - :"memory" ,"cc" ); - -return tmp; +arch_spinlock_t old, new; + + old.tickets =ACCESS_ONCE (lock->tickets); +if (old.tickets.head != old.tickets.tail) +return 0 ; + + new.head_tail = old.head_tail + (1 <<TICKET_SHIFT ); + +/* cmpxchg is a full barrier, so nothing can move before it */ +return cmpxchg (&lock->head_tail, old.head_tail, new.head_tail) == old.head_tail; } -#endif static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock) {
arch/x86/include/asm/spinlock_types.h +4 -2
@@ -9,8 +9,10 @@#if (CONFIG_NR_CPUS <256 )typedef u8 __ticket_t ; +typedef u16 __ticketpair_t ;#else typedef u16 __ticket_t ; +typedef u32 __ticketpair_t ;#endif #define TICKET_SHIFT (sizeof(__ticket_t) * 8)
@@ -18,14 +20,14 @@ typedef u16 __ticket_t;typedef struct arch_spinlock {union { -unsigned int slock; +__ticketpair_t head_tail;struct __raw_tickets {__ticket_t head, tail; } tickets; }; }arch_spinlock_t ; -#define __ARCH_SPIN_LOCK_UNLOCKED { { .slock = 0 } } +#define __ARCH_SPIN_LOCK_UNLOCKED { { 0 } } typedef struct { unsigned int lock;
Signature · 1 line
1.7.5.4
PATCH 7/7 x86/ticketlock: prevent memory accesses from reordered out of lock region
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
--- arch/x86/include/asm/spinlock.h | 1 + 1 files changed, 1 insertions(+), 0 deletions(-)
arch/x86/include/asm/spinlock.h +1 -0
@@ -114,6 +114,7 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock) static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock) { +barrier ();/* prevent reordering out of locked region */ __ticket_unlock_release (lock);barrier ();/* prevent reordering into locked region */ }
Signature · 1 line
1.7.5.4
Peter Zijlstra
maintainerQuoted 34 lines · Jeremy Fitzhardinge
From: Jeremy Fitzhardinge <[email protected]>
Hi all,
I'm proposing this series for 3[.0].1.
This is a repost of a series to clean up the x86 ticket lock code by converting it to a mostly C implementation and removing lots of duplicate code relating to the ticket size.
The last time I posted this series, the only significant comments were from Nick Piggin, specifically relating to:
1. A wrongly placed barrier on unlock (which may have allowed the compiler to move things out of the locked region. I went belt-and-suspenders by having two barriers to prevent motion into or out of the locked region.
2. With
NR_CPUS< 256 the ticket size is 8 bits. The compiler doesn't use the same trick as the hand-coded asm to directly compare the high and low bytes in the word, but does a bit of extra shuffling around. However, the Intel optimisation guide and several x86 experts have opined that its best to avoid the high-byte operations anyway, since they will cause a partial word stall, and the gcc-generated code should be better.Overall the compiler-generated code is very similar to the hand-coded versions, with the partial byte operations being the only significant difference. (Curiously, gcc does generate a high-byte compare for me in trylock, so it can if it wants to.)
I've been running with this code in place for several months on 4 core systems without any problems.
Quoted 6 lines
I couldn't measure a consistent performance difference between the two implemenations; there seemed to be +/- ~1% +/-, which is the level of variation I see from simply recompiling the kernel with slightly different code alignment.
Overall, I think the large reduction in code size is a big win.
No complaints from me, I rather like the result.
One other thing you could contemplate is adding something like:
#define xadd(ptr, inc) \
do { \
switch(sizeof(*(ptr))) { \
case 1: \
asm volatile (LOCK_PREFIX "xaddb %0, %1\n" \
: "+r" (inc), "+m" (*(ptr)) \
: : "memory", "cc"); \
case 2:
... xaddw ...
case 4:
... xaddl ...
} while (0)and a similar something for inc. For both there seem to be various asm bits left (we could even consider adding xadd to arch/x86/include/asm/cmpxchg*.h).
Also, you might have wanted to CC Linus on this, he's usually interested in these bits.
Quoted 1 line · Peter Zijlstra
No complaints from me, I rather like the result.
OK, good.
Quoted 15 lines
One other thing you could contemplate is adding something like:
#define
xadd(ptr, inc)\do { \ switch(sizeof(*(ptr))) { \ case 1: \ asm volatile (LOCK_PREFIX "xaddb %0, %1\n" \ : "+r" (inc), "+m" (*(ptr)) \ : : "memory", "cc"); \ case 2: ... xaddw ... case 4: ... xaddl ... } while (0)
Quoted 6 lines
and a similar something for inc. For both there seem to be various asm bits left (we could even consider adding xadd to
arch/x86/include/asm/cmpxchg*.h).Also, you might have wanted to CC Linus on this, he's usually interested in these bits.
OK, I'll add the xadd/inc helpers and repost.
J
Quoted 15 lines · Peter Zijlstra
One other thing you could contemplate is adding something like:
#define
xadd(ptr, inc)\do { \ switch(sizeof(*(ptr))) { \ case 1: \ asm volatile (LOCK_PREFIX "xaddb %0, %1\n" \ : "+r" (inc), "+m" (*(ptr)) \ : : "memory", "cc"); \ case 2: ... xaddw ... case 4: ... xaddl ... } while (0)
Quoted 3 lines
and a similar something for inc. For both there seem to be various asm bits left (we could even consider adding xadd to
arch/x86/include/asm/cmpxchg*.h).
A friend just pointed out that gcc has a "__sync_fetch_and_add()" intrinsic, which compiles to xadd when used in this context. What's the general feeling about using these kinds of gcc features?
It also has __sync_bool_compare_and_swap(), which would simplify a lot of asm/cmpxchg.h...
J
H. Peter Anvin
reviewerQuoted 5 lines · Jeremy Fitzhardinge
A friend just pointed out that gcc has a "
__sync_fetch_and_add()" intrinsic, which compiles to xadd when used in this context. What's the general feeling about using these kinds of gcc features?
In general they are good, IF:
a) they cover all versions of gcc we care about (or we have a fallback), and
b) they have the right semantics.
Using gcc intrinsics can generate better code than we can in inline assembly.
However, (b) is a killer since gcc doesn't have a way to generate our lock prefix annotations, and so it isn't really useful here.
-hpa
Quoted 8 lines · H. Peter Anvin
Quoted 4 lines · Jeremy Fitzhardinge
A friend just pointed out that gcc has a "
__sync_fetch_and_add()" intrinsic, which compiles to xadd when used in this context. What's the general feeling about using these kinds of gcc features?In general they are good, IF:
a) they cover all versions of gcc we care about (or we have a fallback),
What is the supported range for these days?
Quoted 2 lines
and
b) they have the right semantics.
My main concern was making sure that its a strong enough barrier, but the documentation is pretty explicit about that.
Quoted 2 lines
Using gcc intrinsics can generate better code than we can in inline assembly.
It does seem to do a pretty good job; it generates a plain locked add if you never look at the returned value, for example.
Quoted 2 lines
However, (b) is a killer since gcc doesn't have a way to generate our lock prefix annotations, and so it isn't really useful here.
Yeah, I thought about that. Its a bit unfortunate we're getting into spinlock code at all on a UP system, but we don't have a mechanism to stomp locking at a higher level. (Ignoring all the insane stuff that happens when the system becomes UP transiently just because all the other CPUs have been unplugged for suspend, etc; we just shouldn't bother in that case.)
J
H. Peter Anvin
reviewerQuoted 6 lines · Jeremy Fitzhardinge
Quoted 5 lines · H. Peter Anvin
Quoted 4 lines · Jeremy Fitzhardinge
A friend just pointed out that gcc has a "
__sync_fetch_and_add()" intrinsic, which compiles to xadd when used in this context. What's the general feeling about using these kinds of gcc features?
Quoted 6 lines
Quoted 3 lines
In general they are good, IF:
a) they cover all versions of gcc we care about (or we have a fallback),
What is the supported range for these days?
For x86, we support 3.4, 4.0 and 4.1.2 and above (not sure if 4.0.x actually works). Other architectures have different rules. At some point we'll probably drop anything below 4.1.2, but we apparently can't yet.
Quoted 15 lines
Quoted 2 lines
and
b) they have the right semantics.My main concern was making sure that its a strong enough barrier, but the documentation is pretty explicit about that.
Quoted 2 lines
Using gcc intrinsics can generate better code than we can in inline assembly.
It does seem to do a pretty good job; it generates a plain locked add if you never look at the returned value, for example.
Quoted 2 lines
However, (b) is a killer since gcc doesn't have a way to generate our lock prefix annotations, and so it isn't really useful here.
Quoted 6 lines
Yeah, I thought about that. Its a bit unfortunate we're getting into spinlock code at all on a UP system, but we don't have a mechanism to stomp locking at a higher level. (Ignoring all the insane stuff that happens when the system becomes UP transiently just because all the other CPUs have been unplugged for suspend, etc; we just shouldn't bother in that case.)
Yep...
-hpa
Quoted 3 lines · H. Peter Anvin
For x86, we support 3.4, 4.0 and 4.1.2 and above (not sure if 4.0.x actually works). Other architectures have different rules. At some point we'll probably drop anything below 4.1.2, but we apparently can't yet.
Looks like the intrinsics turned up in 4.1.0.
J
H. Peter Anvin
reviewerQuoted 7 lines · Jeremy Fitzhardinge
Quoted 3 lines · H. Peter Anvin
For x86, we support 3.4, 4.0 and 4.1.2 and above (not sure if 4.0.x actually works). Other architectures have different rules. At some point we'll probably drop anything below 4.1.2, but we apparently can't yet.
Looks like the intrinsics turned up in 4.1.0.
Yes, but they still don't do what we want...
-hpa
Quoted 5 lines · Jeremy Fitzhardinge
From: Jeremy Fitzhardinge <[email protected]>
Hi all,
I'm proposing this series for 3[.0].1.
Is there a git branch with these patches? I've looked over them and they look good (and they make the code much easier to read) but I would like to ingest them in my branches for some extra testing goodness.
PATCH 1/8 x86/ticketlock: clean up types and accessors
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
A few cleanups to the way spinlocks are defined and accessed:
- define __ticket_t which is the size of a spinlock ticket (ie, enough bits to hold all the cpus)
- Define struct arch_spinlock as a union containing plain slock and the head and tail tickets
- Use head and tail to implement some of the spinlock predicates.
- Make all ticket variables unsigned.
- Use TICKET_SHIFT to form constants
Most of this will be used in later patches.
--- arch/x86/include/asm/spinlock.h | 24 ++++++++++-------------- arch/x86/include/asm/spinlock_types.h | 20 ++++++++++++++++++-- 2 files changed, 28 insertions(+), 16 deletions(-)
arch/x86/include/asm/spinlock.h +10 -14
@@ -56,11 +56,9 @@* much between them in performance though, especially as locks are out of line. */ #if (NR_CPUS <256 ) -#define TICKET_SHIFT 8 - static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) { -short inc =0x0100 ; +unsigned short inc =1 <<TICKET_SHIFT ; asmvolatile ( LOCK_PREFIX "xaddw %w0, %1\n"
@@ -79,7 +77,7 @@ static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock) { -int tmp, new; +unsigned int tmp, new; asmvolatile ("movzwl %2, %0\n\t" "cmpb %h0,%b0\n\t"
@@ -104,12 +102,10 @@ static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock) : "memory", "cc"); }#else -#define TICKET_SHIFT 16 - static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) { -int inc =0x00010000 ; -int tmp; +unsigned inc =1 <<TICKET_SHIFT ; +unsigned tmp; asmvolatile (LOCK_PREFIX "xaddl %0, %1\n" "movzwl %w0, %2\n\t"
@@ -129,8 +125,8 @@ static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock) { -int tmp; -int new; +unsigned tmp; +unsigned new; asmvolatile ("movl %2,%0\n\t" "movl %0,%1\n\t"
@@ -160,16 +156,16 @@ static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)static inline int __ticket_spin_is_locked (arch_spinlock_t *lock) { -int tmp =ACCESS_ONCE (lock->slock); +struct __raw_tickets tmp =ACCESS_ONCE (lock->tickets); -return !!(((tmp >>TICKET_SHIFT ) ^ tmp) & ((1 <<TICKET_SHIFT ) -1 )); +return !!(tmp.tail ^ tmp.head); }static inline int __ticket_spin_is_contended (arch_spinlock_t *lock) { -int tmp =ACCESS_ONCE (lock->slock); +struct __raw_tickets tmp =ACCESS_ONCE (lock->tickets); -return (((tmp >>TICKET_SHIFT ) - tmp) & ((1 <<TICKET_SHIFT ) -1 )) >1 ; +return ((tmp.tail - tmp.head) &TICKET_MASK ) >1 ; }#ifndef CONFIG_PARAVIRT_SPINLOCKS
arch/x86/include/asm/spinlock_types.h +18 -2
@@ -5,11 +5,27 @@# error "please don't include this file directly"#endif +#include <linux/types.h> + +#if (CONFIG_NR_CPUS <256 ) +typedef u8 __ticket_t ; +#else +typedef u16 __ticket_t ; +#endif + +#define TICKET_SHIFT (sizeof(__ticket_t) * 8) +#define TICKET_MASK ((__ticket_t)((1 << TICKET_SHIFT) - 1)) +typedef struct arch_spinlock { -unsigned int slock; +union { +unsigned int slock; +struct __raw_tickets { +__ticket_t head, tail; + } tickets; + }; }arch_spinlock_t ; -#define __ARCH_SPIN_LOCK_UNLOCKED { 0 } +#define __ARCH_SPIN_LOCK_UNLOCKED { { .slock = 0 } } typedef struct { unsigned int lock;
Signature · 1 line
1.7.5.4
[tip:x86/spinlocks] x86, ticketlock: Clean up types and accessors
Commit-ID: 699f3dd4e4f8fba6ded83a3dc21e3db960323fcc Gitweb: http://git.kernel.org/tip/699f3dd4e4f8fba6ded83a3dc21e3db960323fcc Author: Jeremy Fitzhardinge <[email protected]> AuthorDate: Thu, 23 Jun 2011 18:19:13 -0700 Committer: H. Peter Anvin <[email protected]> CommitDate: Fri, 22 Jul 2011 11:13:17 -0700
x86, ticketlock: Clean up types and accessors
A few cleanups to the way spinlocks are defined and accessed:
- define __ticket_t which is the size of a spinlock ticket (ie, enough bits to hold all the cpus)
- Define struct arch_spinlock as a union containing plain slock and the head and tail tickets
- Use head and tail to implement some of the spinlock predicates.
- Make all ticket variables unsigned.
- Use TICKET_SHIFT to form constants
Most of this will be used in later patches.
--- arch/x86/include/asm/spinlock.h | 24 ++++++++++-------------- arch/x86/include/asm/spinlock_types.h | 20 ++++++++++++++++++-- 2 files changed, 28 insertions(+), 16 deletions(-)
arch/x86/include/asm/spinlock.h +10 -14
@@ -56,11 +56,9 @@* much between them in performance though, especially as locks are out of line. */ #if (NR_CPUS <256 ) -#define TICKET_SHIFT 8 - static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) { -short inc =0x0100 ; +unsigned short inc =1 <<TICKET_SHIFT ; asmvolatile ( LOCK_PREFIX "xaddw %w0, %1\n"
@@ -79,7 +77,7 @@ static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock) { -int tmp, new; +unsigned int tmp, new; asmvolatile ("movzwl %2, %0\n\t" "cmpb %h0,%b0\n\t"
@@ -104,12 +102,10 @@ static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock) : "memory", "cc"); }#else -#define TICKET_SHIFT 16 - static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) { -int inc =0x00010000 ; -int tmp; +unsigned inc =1 <<TICKET_SHIFT ; +unsigned tmp; asmvolatile (LOCK_PREFIX "xaddl %0, %1\n" "movzwl %w0, %2\n\t"
@@ -129,8 +125,8 @@ static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock) { -int tmp; -int new; +unsigned tmp; +unsigned new; asmvolatile ("movl %2,%0\n\t" "movl %0,%1\n\t"
@@ -160,16 +156,16 @@ static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)static inline int __ticket_spin_is_locked (arch_spinlock_t *lock) { -int tmp =ACCESS_ONCE (lock->slock); +struct __raw_tickets tmp =ACCESS_ONCE (lock->tickets); -return !!(((tmp >>TICKET_SHIFT ) ^ tmp) & ((1 <<TICKET_SHIFT ) -1 )); +return !!(tmp.tail ^ tmp.head); }static inline int __ticket_spin_is_contended (arch_spinlock_t *lock) { -int tmp =ACCESS_ONCE (lock->slock); +struct __raw_tickets tmp =ACCESS_ONCE (lock->tickets); -return (((tmp >>TICKET_SHIFT ) - tmp) & ((1 <<TICKET_SHIFT ) -1 )) >1 ; +return ((tmp.tail - tmp.head) &TICKET_MASK ) >1 ; }#ifndef CONFIG_PARAVIRT_SPINLOCKS
arch/x86/include/asm/spinlock_types.h +18 -2
@@ -5,11 +5,27 @@# error "please don't include this file directly"#endif +#include <linux/types.h> + +#if (CONFIG_NR_CPUS <256 ) +typedef u8 __ticket_t ; +#else +typedef u16 __ticket_t ; +#endif + +#define TICKET_SHIFT (sizeof(__ticket_t) * 8) +#define TICKET_MASK ((__ticket_t)((1 << TICKET_SHIFT) - 1)) +typedef struct arch_spinlock { -unsigned int slock; +union { +unsigned int slock; +struct __raw_tickets { +__ticket_t head, tail; + } tickets; + }; }arch_spinlock_t ; -#define __ARCH_SPIN_LOCK_UNLOCKED { 0 } +#define __ARCH_SPIN_LOCK_UNLOCKED { { .slock = 0 } } typedef struct { unsigned int lock;
PATCH 2/8 x86/ticketlock: convert spin loop to C
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
The inner loop of __ticket_spin_lock isn't doing anything very special, so reimplement it in C.
For the 8 bit ticket lock variant, we use a register union to get direct access to the lower and upper bytes in the tickets, but unfortunately gcc won't generate a direct comparison between the two halves of the register, so the generated asm isn't quite as pretty as the hand-coded version. However benchmarking shows that this is actually a small improvement in runtime performance on some benchmarks, and never a slowdown.
We also need to make sure there's a barrier at the end of the lock loop to make sure that the compiler doesn't move any instructions from within the locked region into the region where we don't yet own the lock.
--- arch/x86/include/asm/spinlock.h | 58 +++++++++++++++++++------------------- 1 files changed, 29 insertions(+), 29 deletions(-)
arch/x86/include/asm/spinlock.h +30 -30
@@ -58,21 +58,21 @@#if (NR_CPUS <256 ) static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) { -unsigned short inc =1 <<TICKET_SHIFT ; - - asmvolatile ( -LOCK_PREFIX "xaddw %w0, %1\n" -"1:\t" -"cmpb %h0, %b0\n\t" -"je 2f\n\t" -"rep ; nop\n\t" -"movb %1, %b0\n\t" -/* don't need lfence here, because loads are in-order */ -"jmp 1b\n" -"2:" - :"+Q" (inc),"+m" (lock->slock) - : - :"memory" ,"cc" ); + registerunion { +struct __raw_tickets tickets; +unsigned short slock; + } inc = { .slock =1 <<TICKET_SHIFT }; + + asmvolatile (LOCK_PREFIX "xaddw %w0, %1\n" + :"+Q" (inc),"+m" (lock->slock) : :"memory" ,"cc" ); + +for (;;) { +if (inc.tickets.head == inc.tickets.tail) + goto out; +cpu_relax (); + inc.tickets.head =ACCESS_ONCE (lock->tickets.head); + } +out:barrier ();/* make sure nothing creeps before the lock is taken */ } static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
@@ -105,22 +105,22 @@ static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock) static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) {unsigned inc =1 <<TICKET_SHIFT ; -unsigned tmp; +__ticket_t tmp; - asmvolatile (LOCK_PREFIX "xaddl %0, %1\n" -"movzwl %w0, %2\n\t" -"shrl $16, %0\n\t" -"1:\t" -"cmpl %0, %2\n\t" -"je 2f\n\t" -"rep ; nop\n\t" -"movzwl %1, %2\n\t" -/* don't need lfence here, because loads are in-order */ -"jmp 1b\n" -"2:" - :"+r" (inc),"+m" (lock->slock),"=&r" (tmp) - : - :"memory" ,"cc" ); + asmvolatile (LOCK_PREFIX "xaddl %0, %1\n\t" + :"+r" (inc),"+m" (lock->slock) + : :"memory" ,"cc" ); + + tmp = inc; + inc >>=TICKET_SHIFT ; + +for (;;) { +if ((__ticket_t )inc == tmp) + goto out; +cpu_relax (); + tmp =ACCESS_ONCE (lock->tickets.head); + } +out:barrier ();/* make sure nothing creeps before the lock is taken */ } static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
Signature · 1 line
1.7.5.4
[tip:x86/spinlocks] x86, ticketlock: Convert spin loop to C
Commit-ID: 79e661791e9681d31fe32dfebe6d2fcf4938b64b Gitweb: http://git.kernel.org/tip/79e661791e9681d31fe32dfebe6d2fcf4938b64b Author: Jeremy Fitzhardinge <[email protected]> AuthorDate: Thu, 23 Jun 2011 18:19:14 -0700 Committer: H. Peter Anvin <[email protected]> CommitDate: Fri, 22 Jul 2011 11:13:26 -0700
x86, ticketlock: Convert spin loop to C
The inner loop of __ticket_spin_lock isn't doing anything very special, so reimplement it in C.
For the 8 bit ticket lock variant, we use a register union to get direct access to the lower and upper bytes in the tickets, but unfortunately gcc won't generate a direct comparison between the two halves of the register, so the generated asm isn't quite as pretty as the hand-coded version. However benchmarking shows that this is actually a small improvement in runtime performance on some benchmarks, and never a slowdown.
We also need to make sure there's a barrier at the end of the lock loop to make sure that the compiler doesn't move any instructions from within the locked region into the region where we don't yet own the lock.
--- arch/x86/include/asm/spinlock.h | 58 +++++++++++++++++++------------------- 1 files changed, 29 insertions(+), 29 deletions(-)
arch/x86/include/asm/spinlock.h +30 -30
@@ -58,21 +58,21 @@#if (NR_CPUS <256 ) static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) { -unsigned short inc =1 <<TICKET_SHIFT ; - - asmvolatile ( -LOCK_PREFIX "xaddw %w0, %1\n" -"1:\t" -"cmpb %h0, %b0\n\t" -"je 2f\n\t" -"rep ; nop\n\t" -"movb %1, %b0\n\t" -/* don't need lfence here, because loads are in-order */ -"jmp 1b\n" -"2:" - :"+Q" (inc),"+m" (lock->slock) - : - :"memory" ,"cc" ); + registerunion { +struct __raw_tickets tickets; +unsigned short slock; + } inc = { .slock =1 <<TICKET_SHIFT }; + + asmvolatile (LOCK_PREFIX "xaddw %w0, %1\n" + :"+Q" (inc),"+m" (lock->slock) : :"memory" ,"cc" ); + +for (;;) { +if (inc.tickets.head == inc.tickets.tail) + goto out; +cpu_relax (); + inc.tickets.head =ACCESS_ONCE (lock->tickets.head); + } +out:barrier ();/* make sure nothing creeps before the lock is taken */ } static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
@@ -105,22 +105,22 @@ static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock) static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) {unsigned inc =1 <<TICKET_SHIFT ; -unsigned tmp; +__ticket_t tmp; - asmvolatile (LOCK_PREFIX "xaddl %0, %1\n" -"movzwl %w0, %2\n\t" -"shrl $16, %0\n\t" -"1:\t" -"cmpl %0, %2\n\t" -"je 2f\n\t" -"rep ; nop\n\t" -"movzwl %1, %2\n\t" -/* don't need lfence here, because loads are in-order */ -"jmp 1b\n" -"2:" - :"+r" (inc),"+m" (lock->slock),"=&r" (tmp) - : - :"memory" ,"cc" ); + asmvolatile (LOCK_PREFIX "xaddl %0, %1\n\t" + :"+r" (inc),"+m" (lock->slock) + : :"memory" ,"cc" ); + + tmp = inc; + inc >>=TICKET_SHIFT ; + +for (;;) { +if ((__ticket_t )inc == tmp) + goto out; +cpu_relax (); + tmp =ACCESS_ONCE (lock->tickets.head); + } +out:barrier ();/* make sure nothing creeps before the lock is taken */ } static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
PATCH 3/8 x86/ticketlock: Use C for __ticket_spin_unlock
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
If we don't need to use a locked inc for unlock, then implement it in C.
--- arch/x86/include/asm/spinlock.h | 33 ++++++++++++++++++--------------- 1 files changed, 18 insertions(+), 15 deletions(-)
arch/x86/include/asm/spinlock.h +18 -15
@@ -33,9 +33,21 @@* On PPro SMP or if we are using OOSTORE, we use a locked operation to unlock * (PPro errata 66, 92) */ -# define UNLOCK_LOCK_PREFIX LOCK_PREFIX +static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock) +{ +if (sizeof (lock->tickets.head) ==sizeof (u8)) + asm (LOCK_PREFIX "incb %0" + :"+m" (lock->tickets.head) : :"memory" ); +else + asm (LOCK_PREFIX "incw %0" + :"+m" (lock->tickets.head) : :"memory" ); + +}#else -# define UNLOCK_LOCK_PREFIX +static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock) +{ + lock->tickets.head++; +}#endif /*
@@ -93,14 +105,6 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)return tmp; } - -static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock) -{ - asmvolatile (UNLOCK_LOCK_PREFIX "incb %0" - :"+m" (lock->slock) - : - :"memory" ,"cc" ); -}#else static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) {
@@ -144,15 +148,14 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)return tmp; } +#endif static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock) { - asmvolatile (UNLOCK_LOCK_PREFIX "incw %0" - :"+m" (lock->slock) - : - :"memory" ,"cc" ); +barrier ();/* prevent reordering out of locked region */ +__ticket_unlock_release (lock); +barrier ();/* prevent reordering into locked region */ } -#endif static inline int __ticket_spin_is_locked (arch_spinlock_t *lock) {
Signature · 1 line
1.7.5.4
H. Peter Anvin
reviewerRe: [PATCH 3/8] x86/ticketlock: Use C for __ticket_spin_unlock
Quoted 17 lines · Jeremy Fitzhardinge
From: Jeremy Fitzhardinge <[email protected]>
If we don't need to use a locked inc for unlock, then implement it in C.
Signed-off-by Jeremy Fitzhardinge <[email protected]>--- arch/x86/include/asm/spinlock.h | 33 ++++++++++++++++++--------------- 1 files changed, 18 insertions(+), 15 deletions(-)arch/x86/include/asm/spinlock.h +0
-0@@ -33,9 +33,21 @@* On PPro SMP or if we are using OOSTORE, we use a locked operation to unlock * (PPro errata 66, 92) */
arch/x86/include/asm/spinlock.h line 44
Quoted 10 lines
arch/x86/include/asm/spinlock.h +9
-1-# define UNLOCK_LOCK_PREFIX LOCK_PREFIX +static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock) +{ +if (sizeof (lock->tickets.head) ==sizeof (u8)) + asm (LOCK_PREFIX "incb %0" + :"+m" (lock->tickets.head) : :"memory" ); +else + asm (LOCK_PREFIX "incw %0" + :"+m" (lock->tickets.head) : :"memory" ); +
These should be asm volatile, I believe.
-hpa
Re: [PATCH 3/8] x86/ticketlock: Use C for __ticket_spin_unlock
Quoted 1 line · H. Peter Anvin
These should be asm volatile, I believe.
OK.
J
H. Peter Anvin
reviewerRe: [PATCH 3/8] x86/ticketlock: Use C for __ticket_spin_unlock
Quoted 6 lines · Jeremy Fitzhardinge
Quoted 1 line · H. Peter Anvin
These should be asm volatile, I believe.
OK.
J
You still owe me a new patch here, I believe...
-hpa
Re: [PATCH 3/8] x86/ticketlock: Use C for __ticket_spin_unlock
Quoted 7 lines · H. Peter Anvin
Quoted 5 lines · Jeremy Fitzhardinge
Quoted 1 line · H. Peter Anvin
These should be asm volatile, I believe.
OK.
J
You still owe me a new patch here, I believe...
Ah, yes, though I don't think it can make a difference in practice, since the caller contains barrier()s on either side. And the non-asm non-locked variant has no equivalent. But it can't hurt.
J
From: Jeremy Fitzhardinge <[email protected]>
Date: Fri, 22 Jul 2011 12:27:14 -0700
Subject: [PATCH] x86/ticketlocks: make asms volatile to be extra sure
Make the locked-unlock asms volatile, just to be extra sure they won't wander away.
arch/x86/include/asm/spinlock.h +4 -4
@@ -36,11 +36,11 @@ static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock) {if (sizeof (lock->tickets.head) ==sizeof (u8)) - asm (LOCK_PREFIX "incb %0" - :"+m" (lock->tickets.head) : :"memory" ); + asmvolatile (LOCK_PREFIX "incb %0" + :"+m" (lock->tickets.head) : :"memory" );else - asm (LOCK_PREFIX "incw %0" - :"+m" (lock->tickets.head) : :"memory" ); + asmvolatile (LOCK_PREFIX "incw %0" + :"+m" (lock->tickets.head) : :"memory" ); }#else
[tip:x86/spinlocks] x86, ticketlock: Use asm volatile for __ticket_unlock_release()
In reply to H. Peter AnvinCommit-ID: 26056c822f9428ddc95fd7ac3008bbb0032d1086 Gitweb: http://git.kernel.org/tip/26056c822f9428ddc95fd7ac3008bbb0032d1086 Author: H. Peter Anvin <[email protected]> AuthorDate: Fri, 22 Jul 2011 11:15:20 -0700 Committer: H. Peter Anvin <[email protected]> CommitDate: Fri, 22 Jul 2011 11:15:20 -0700
x86, ticketlock: Use asm volatile for __ticket_unlock_release()
__ticket_uplock_release() really should have barrier semantics, so use "asm volatile" there.
--- arch/x86/include/asm/spinlock.h | 8 ++++---- 1 files changed, 4 insertions(+), 4 deletions(-)
arch/x86/include/asm/spinlock.h +4 -4
@@ -36,11 +36,11 @@ static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock) {if (sizeof (lock->tickets.head) ==sizeof (u8)) - asm (LOCK_PREFIX "incb %0" - :"+m" (lock->tickets.head) : :"memory" ); + asmvolatile (LOCK_PREFIX "incb %0" + :"+m" (lock->tickets.head) : :"memory" );else - asm (LOCK_PREFIX "incw %0" - :"+m" (lock->tickets.head) : :"memory" ); + asmvolatile (LOCK_PREFIX "incw %0" + :"+m" (lock->tickets.head) : :"memory" ); }#else
[tip:x86/spinlocks] x86, ticketlock: Use C for __ticket_spin_unlock
In reply to Jeremy FitzhardingeCommit-ID: 68302ae430d388a0118a8ce2a1abb5f87b737ef6 Gitweb: http://git.kernel.org/tip/68302ae430d388a0118a8ce2a1abb5f87b737ef6 Author: Jeremy Fitzhardinge <[email protected]> AuthorDate: Thu, 23 Jun 2011 18:19:15 -0700 Committer: H. Peter Anvin <[email protected]> CommitDate: Fri, 22 Jul 2011 11:13:44 -0700
x86, ticketlock: Use C for __ticket_spin_unlock
If we don't need to use a locked inc for unlock, then implement it in C.
--- arch/x86/include/asm/spinlock.h | 33 ++++++++++++++++++--------------- 1 files changed, 18 insertions(+), 15 deletions(-)
arch/x86/include/asm/spinlock.h +18 -15
@@ -33,9 +33,21 @@* On PPro SMP or if we are using OOSTORE, we use a locked operation to unlock * (PPro errata 66, 92) */ -# define UNLOCK_LOCK_PREFIX LOCK_PREFIX +static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock) +{ +if (sizeof (lock->tickets.head) ==sizeof (u8)) + asm (LOCK_PREFIX "incb %0" + :"+m" (lock->tickets.head) : :"memory" ); +else + asm (LOCK_PREFIX "incw %0" + :"+m" (lock->tickets.head) : :"memory" ); + +}#else -# define UNLOCK_LOCK_PREFIX +static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock) +{ + lock->tickets.head++; +}#endif /*
@@ -93,14 +105,6 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)return tmp; } - -static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock) -{ - asmvolatile (UNLOCK_LOCK_PREFIX "incb %0" - :"+m" (lock->slock) - : - :"memory" ,"cc" ); -}#else static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) {
@@ -144,15 +148,14 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)return tmp; } +#endif static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock) { - asmvolatile (UNLOCK_LOCK_PREFIX "incw %0" - :"+m" (lock->slock) - : - :"memory" ,"cc" ); +barrier ();/* prevent reordering out of locked region */ +__ticket_unlock_release (lock); +barrier ();/* prevent reordering into locked region */ } -#endif static inline int __ticket_spin_is_locked (arch_spinlock_t *lock) {
PATCH 4/8 x86/ticketlock: make large and small ticket versions of spin_lock the same
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
Make the bulk of __ticket_spin_lock look identical for large and small number of cpus.
--- arch/x86/include/asm/spinlock.h | 23 ++++++++--------------- 1 files changed, 8 insertions(+), 15 deletions(-)
arch/x86/include/asm/spinlock.h +8 -15
@@ -70,19 +70,16 @@ static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)#if (NR_CPUS <256 ) static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) { - registerunion { -struct __raw_tickets tickets; -unsigned short slock; - } inc = { .slock =1 <<TICKET_SHIFT }; + registerstruct __raw_tickets inc = { .tail =1 }; asmvolatile (LOCK_PREFIX "xaddw %w0, %1\n" - :"+Q" (inc),"+m" (lock->slock) : :"memory" ,"cc" ); + :"+r" (inc),"+m" (lock->tickets) : :"memory" ,"cc" );for (;;) { -if (inc.tickets.head == inc.tickets.tail) +if (inc.head == inc.tail) goto out;cpu_relax (); - inc.tickets.head =ACCESS_ONCE (lock->tickets.head); + inc.head =ACCESS_ONCE (lock->tickets.head); } out:barrier ();/* make sure nothing creeps before the lock is taken */ }
@@ -108,21 +105,17 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)#else static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) { -unsigned inc =1 <<TICKET_SHIFT ; -__ticket_t tmp; + registerstruct __raw_tickets inc = { .tail =1 }; asmvolatile (LOCK_PREFIX "xaddl %0, %1\n\t" - :"+r" (inc),"+m" (lock->slock) + :"+r" (inc),"+m" (lock->tickets) : :"memory" ,"cc" ); - tmp = inc; - inc >>=TICKET_SHIFT ; -for (;;) { -if ((__ticket_t )inc == tmp) +if (inc.head == inc.tail) goto out;cpu_relax (); - tmp =ACCESS_ONCE (lock->tickets.head); + inc.head =ACCESS_ONCE (lock->tickets.head); } out:barrier ();/* make sure nothing creeps before the lock is taken */ }
Signature · 1 line
1.7.5.4
[tip:x86/spinlocks] x86, ticketlock: Make large and small ticket versions of spin_lock the same
Commit-ID: dc126c03ca25de516eaa8e575a98b81382d6d4b4 Gitweb: http://git.kernel.org/tip/dc126c03ca25de516eaa8e575a98b81382d6d4b4 Author: Jeremy Fitzhardinge <[email protected]> AuthorDate: Thu, 23 Jun 2011 18:19:16 -0700 Committer: H. Peter Anvin <[email protected]> CommitDate: Fri, 22 Jul 2011 11:18:37 -0700
x86, ticketlock: Make large and small ticket versions of spin_lock the same
Make the bulk of __ticket_spin_lock look identical for large and small number of cpus.
--- arch/x86/include/asm/spinlock.h | 23 ++++++++--------------- 1 files changed, 8 insertions(+), 15 deletions(-)
arch/x86/include/asm/spinlock.h +8 -15
@@ -70,19 +70,16 @@ static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)#if (NR_CPUS <256 ) static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) { - registerunion { -struct __raw_tickets tickets; -unsigned short slock; - } inc = { .slock =1 <<TICKET_SHIFT }; + registerstruct __raw_tickets inc = { .tail =1 }; asmvolatile (LOCK_PREFIX "xaddw %w0, %1\n" - :"+Q" (inc),"+m" (lock->slock) : :"memory" ,"cc" ); + :"+r" (inc),"+m" (lock->tickets) : :"memory" ,"cc" );for (;;) { -if (inc.tickets.head == inc.tickets.tail) +if (inc.head == inc.tail) goto out;cpu_relax (); - inc.tickets.head =ACCESS_ONCE (lock->tickets.head); + inc.head =ACCESS_ONCE (lock->tickets.head); } out:barrier ();/* make sure nothing creeps before the lock is taken */ }
@@ -108,21 +105,17 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)#else static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) { -unsigned inc =1 <<TICKET_SHIFT ; -__ticket_t tmp; + registerstruct __raw_tickets inc = { .tail =1 }; asmvolatile (LOCK_PREFIX "xaddl %0, %1\n\t" - :"+r" (inc),"+m" (lock->slock) + :"+r" (inc),"+m" (lock->tickets) : :"memory" ,"cc" ); - tmp = inc; - inc >>=TICKET_SHIFT ; -for (;;) { -if ((__ticket_t )inc == tmp) +if (inc.head == inc.tail) goto out;cpu_relax (); - tmp =ACCESS_ONCE (lock->tickets.head); + inc.head =ACCESS_ONCE (lock->tickets.head); } out:barrier ();/* make sure nothing creeps before the lock is taken */ }
PATCH 5/8 x86/ticketlock: make __ticket_spin_lock common
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
Aside from the particular form of the xadd instruction, they're identical. So factor out the xadd and use common code for the rest.
--- arch/x86/include/asm/spinlock.h | 42 ++++++++++++++++++-------------------- 1 files changed, 20 insertions(+), 22 deletions(-)
arch/x86/include/asm/spinlock.h +20 -22
@@ -67,13 +67,27 @@ static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)* save some instructions and make the code more elegant. There really isn't * much between them in performance though, especially as locks are out of line. */ -#if (NR_CPUS <256 ) -static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) +static __always_inline struct __raw_tickets __ticket_spin_claim(struct arch_spinlock *lock) { - registerstruct __raw_tickets inc = { .tail =1 }; + registerstruct __raw_tickets tickets = { .tail =1 }; + +if (sizeof (lock->tickets.head) ==sizeof (u8)) + asmvolatile (LOCK_PREFIX "xaddw %w0, %1\n" + :"+r" (tickets),"+m" (lock->tickets) + : :"memory" ,"cc" ); +else + asmvolatile (LOCK_PREFIX "xaddl %0, %1\n" + :"+r" (tickets),"+m" (lock->tickets) + : :"memory" ,"cc" ); - asmvolatile (LOCK_PREFIX "xaddw %w0, %1\n" - :"+r" (inc),"+m" (lock->tickets) : :"memory" ,"cc" ); +return tickets; +} + +static __always_inline void __ticket_spin_lock(struct arch_spinlock *lock) +{ + registerstruct __raw_tickets inc; + + inc =__ticket_spin_claim (lock);for (;;) {if (inc.head == inc.tail)
@@ -84,6 +98,7 @@ static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) out:barrier ();/* make sure nothing creeps before the lock is taken */ } +#if (NR_CPUS <256 ) static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock) {unsigned int tmp, new;
@@ -103,23 +118,6 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)return tmp; }#else -static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) -{ - registerstruct __raw_tickets inc = { .tail =1 }; - - asmvolatile (LOCK_PREFIX "xaddl %0, %1\n\t" - :"+r" (inc),"+m" (lock->tickets) - : :"memory" ,"cc" ); - -for (;;) { -if (inc.head == inc.tail) - goto out; -cpu_relax (); - inc.head =ACCESS_ONCE (lock->tickets.head); - } -out:barrier ();/* make sure nothing creeps before the lock is taken */ -} - static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock) {unsigned tmp;
Signature · 1 line
1.7.5.4
[tip:x86/spinlocks] x86, ticketlock: Make __ticket_spin_lock common
Commit-ID: 65bd26616b53c5dfab162f18c34ec57ddb682a00 Gitweb: http://git.kernel.org/tip/65bd26616b53c5dfab162f18c34ec57ddb682a00 Author: Jeremy Fitzhardinge <[email protected]> AuthorDate: Thu, 23 Jun 2011 18:19:17 -0700 Committer: H. Peter Anvin <[email protected]> CommitDate: Fri, 22 Jul 2011 11:18:44 -0700
x86, ticketlock: Make __ticket_spin_lock common
Aside from the particular form of the xadd instruction, they're identical. So factor out the xadd and use common code for the rest.
--- arch/x86/include/asm/spinlock.h | 42 ++++++++++++++++++-------------------- 1 files changed, 20 insertions(+), 22 deletions(-)
arch/x86/include/asm/spinlock.h +20 -22
@@ -67,13 +67,27 @@ static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)* save some instructions and make the code more elegant. There really isn't * much between them in performance though, especially as locks are out of line. */ -#if (NR_CPUS <256 ) -static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) +static __always_inline struct __raw_tickets __ticket_spin_claim(struct arch_spinlock *lock) { - registerstruct __raw_tickets inc = { .tail =1 }; + registerstruct __raw_tickets tickets = { .tail =1 }; + +if (sizeof (lock->tickets.head) ==sizeof (u8)) + asmvolatile (LOCK_PREFIX "xaddw %w0, %1\n" + :"+r" (tickets),"+m" (lock->tickets) + : :"memory" ,"cc" ); +else + asmvolatile (LOCK_PREFIX "xaddl %0, %1\n" + :"+r" (tickets),"+m" (lock->tickets) + : :"memory" ,"cc" ); - asmvolatile (LOCK_PREFIX "xaddw %w0, %1\n" - :"+r" (inc),"+m" (lock->tickets) : :"memory" ,"cc" ); +return tickets; +} + +static __always_inline void __ticket_spin_lock(struct arch_spinlock *lock) +{ + registerstruct __raw_tickets inc; + + inc =__ticket_spin_claim (lock);for (;;) {if (inc.head == inc.tail)
@@ -84,6 +98,7 @@ static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) out:barrier ();/* make sure nothing creeps before the lock is taken */ } +#if (NR_CPUS <256 ) static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock) {unsigned int tmp, new;
@@ -103,23 +118,6 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)return tmp; }#else -static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) -{ - registerstruct __raw_tickets inc = { .tail =1 }; - - asmvolatile (LOCK_PREFIX "xaddl %0, %1\n\t" - :"+r" (inc),"+m" (lock->tickets) - : :"memory" ,"cc" ); - -for (;;) { -if (inc.head == inc.tail) - goto out; -cpu_relax (); - inc.head =ACCESS_ONCE (lock->tickets.head); - } -out:barrier ();/* make sure nothing creeps before the lock is taken */ -} - static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock) {unsigned tmp;
PATCH 6/8 x86/ticketlock: make __ticket_spin_trylock common
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
Make trylock code common regardless of ticket size.
--- arch/x86/include/asm/spinlock.h | 49 +++++++-------------------------- arch/x86/include/asm/spinlock_types.h | 6 +++- 2 files changed, 14 insertions(+), 41 deletions(-)
arch/x86/include/asm/spinlock.h +10 -39
@@ -98,48 +98,19 @@ static __always_inline void __ticket_spin_lock(struct arch_spinlock *lock) out:barrier ();/* make sure nothing creeps before the lock is taken */ } -#if (NR_CPUS <256 ) static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock) { -unsigned int tmp, new; - - asmvolatile ("movzwl %2, %0\n\t" -"cmpb %h0,%b0\n\t" -"leal 0x100(%" REG_PTR_MODE "0), %1\n\t" -"jne 1f\n\t" -LOCK_PREFIX "cmpxchgw %w1,%2\n\t" -"1:" -"sete %b1\n\t" -"movzbl %b1,%0\n\t" - :"=&a" (tmp),"=&q" (new),"+m" (lock->slock) - : - :"memory" ,"cc" ); - -return tmp; -} -#else -static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock) -{ -unsigned tmp; -unsigned new; - - asmvolatile ("movl %2,%0\n\t" -"movl %0,%1\n\t" -"roll $16, %0\n\t" -"cmpl %0,%1\n\t" -"leal 0x00010000(%" REG_PTR_MODE "0), %1\n\t" -"jne 1f\n\t" -LOCK_PREFIX "cmpxchgl %1,%2\n\t" -"1:" -"sete %b1\n\t" -"movzbl %b1,%0\n\t" - :"=&a" (tmp),"=&q" (new),"+m" (lock->slock) - : - :"memory" ,"cc" ); - -return tmp; +arch_spinlock_t old, new; + + old.tickets =ACCESS_ONCE (lock->tickets); +if (old.tickets.head != old.tickets.tail) +return 0 ; + + new.head_tail = old.head_tail + (1 <<TICKET_SHIFT ); + +/* cmpxchg is a full barrier, so nothing can move before it */ +return cmpxchg (&lock->head_tail, old.head_tail, new.head_tail) == old.head_tail; } -#endif static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock) {
arch/x86/include/asm/spinlock_types.h +4 -2
@@ -9,8 +9,10 @@#if (CONFIG_NR_CPUS <256 )typedef u8 __ticket_t ; +typedef u16 __ticketpair_t ;#else typedef u16 __ticket_t ; +typedef u32 __ticketpair_t ;#endif #define TICKET_SHIFT (sizeof(__ticket_t) * 8)
@@ -18,14 +20,14 @@ typedef u16 __ticket_t;typedef struct arch_spinlock {union { -unsigned int slock; +__ticketpair_t head_tail;struct __raw_tickets {__ticket_t head, tail; } tickets; }; }arch_spinlock_t ; -#define __ARCH_SPIN_LOCK_UNLOCKED { { .slock = 0 } } +#define __ARCH_SPIN_LOCK_UNLOCKED { { 0 } } typedef struct { unsigned int lock;
Signature · 1 line
1.7.5.4
[tip:x86/spinlocks] x86, ticketlock: Make __ticket_spin_trylock common
Commit-ID: f5b00da7b60cc444b5e6caf2f08b0eebcebff75e Gitweb: http://git.kernel.org/tip/f5b00da7b60cc444b5e6caf2f08b0eebcebff75e Author: Jeremy Fitzhardinge <[email protected]> AuthorDate: Thu, 23 Jun 2011 18:19:18 -0700 Committer: H. Peter Anvin <[email protected]> CommitDate: Fri, 22 Jul 2011 11:18:53 -0700
x86, ticketlock: Make __ticket_spin_trylock common
Make trylock code common regardless of ticket size.
--- arch/x86/include/asm/spinlock.h | 49 +++++++-------------------------- arch/x86/include/asm/spinlock_types.h | 6 +++- 2 files changed, 14 insertions(+), 41 deletions(-)
arch/x86/include/asm/spinlock.h +10 -39
@@ -98,48 +98,19 @@ static __always_inline void __ticket_spin_lock(struct arch_spinlock *lock) out:barrier ();/* make sure nothing creeps before the lock is taken */ } -#if (NR_CPUS <256 ) static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock) { -unsigned int tmp, new; - - asmvolatile ("movzwl %2, %0\n\t" -"cmpb %h0,%b0\n\t" -"leal 0x100(%" REG_PTR_MODE "0), %1\n\t" -"jne 1f\n\t" -LOCK_PREFIX "cmpxchgw %w1,%2\n\t" -"1:" -"sete %b1\n\t" -"movzbl %b1,%0\n\t" - :"=&a" (tmp),"=&q" (new),"+m" (lock->slock) - : - :"memory" ,"cc" ); - -return tmp; -} -#else -static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock) -{ -unsigned tmp; -unsigned new; - - asmvolatile ("movl %2,%0\n\t" -"movl %0,%1\n\t" -"roll $16, %0\n\t" -"cmpl %0,%1\n\t" -"leal 0x00010000(%" REG_PTR_MODE "0), %1\n\t" -"jne 1f\n\t" -LOCK_PREFIX "cmpxchgl %1,%2\n\t" -"1:" -"sete %b1\n\t" -"movzbl %b1,%0\n\t" - :"=&a" (tmp),"=&q" (new),"+m" (lock->slock) - : - :"memory" ,"cc" ); - -return tmp; +arch_spinlock_t old, new; + + old.tickets =ACCESS_ONCE (lock->tickets); +if (old.tickets.head != old.tickets.tail) +return 0 ; + + new.head_tail = old.head_tail + (1 <<TICKET_SHIFT ); + +/* cmpxchg is a full barrier, so nothing can move before it */ +return cmpxchg (&lock->head_tail, old.head_tail, new.head_tail) == old.head_tail; } -#endif static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock) {
arch/x86/include/asm/spinlock_types.h +4 -2
@@ -9,8 +9,10 @@#if (CONFIG_NR_CPUS <256 )typedef u8 __ticket_t ; +typedef u16 __ticketpair_t ;#else typedef u16 __ticket_t ; +typedef u32 __ticketpair_t ;#endif #define TICKET_SHIFT (sizeof(__ticket_t) * 8)
@@ -18,14 +20,14 @@ typedef u16 __ticket_t;typedef struct arch_spinlock {union { -unsigned int slock; +__ticketpair_t head_tail;struct __raw_tickets {__ticket_t head, tail; } tickets; }; }arch_spinlock_t ; -#define __ARCH_SPIN_LOCK_UNLOCKED { { .slock = 0 } } +#define __ARCH_SPIN_LOCK_UNLOCKED { { 0 } } typedef struct { unsigned int lock;
PATCH 7/8 x86: add xadd helper macro
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
--- arch/x86/include/asm/cmpxchg_32.h | 21 +++++++++++++++++++++ arch/x86/include/asm/cmpxchg_64.h | 26 ++++++++++++++++++++++++++ 2 files changed, 47 insertions(+), 0 deletions(-)
arch/x86/include/asm/cmpxchg_32.h +21 -0
@@ -280,4 +280,25 @@ static inline unsigned long cmpxchg_386(volatile void *ptr, unsigned long old,#endif +#define xadd (ptr, inc) \ + do { \ + switch (sizeof(*(ptr))) { \ + case 1: \ + asm volatile (LOCK_PREFIX "xaddb %b0, %1\n" \ + : "+r" (inc), "+m" (*(ptr)) \ + : : "memory", "cc"); \ + break; \ + case 2: \ + asm volatile (LOCK_PREFIX "xaddw %w0, %1\n" \ + : "+r" (inc), "+m" (*(ptr)) \ + : : "memory", "cc"); \ + break; \ + case 4: \ + asm volatile (LOCK_PREFIX "xaddl %0, %1\n" \ + : "+r" (inc), "+m" (*(ptr)) \ + : : "memory", "cc"); \ + break; \ + } \ + } while(0) +#endif /* _ASM_X86_CMPXCHG_32_H */
arch/x86/include/asm/cmpxchg_64.h +26 -0
@@ -151,4 +151,30 @@ extern void __cmpxchg_wrong_size(void);cmpxchg_local ((ptr), (o), (n)); \ }) +#define xadd (ptr, inc) \ + do { \ + switch (sizeof(*(ptr))) { \ + case 1: \ + asm volatile (LOCK_PREFIX "xaddb %b0, %1\n" \ + : "+r" (inc), "+m" (*(ptr)) \ + : : "memory", "cc"); \ + break; \ + case 2: \ + asm volatile (LOCK_PREFIX "xaddw %w0, %1\n" \ + : "+r" (inc), "+m" (*(ptr)) \ + : : "memory", "cc"); \ + break; \ + case 4: \ + asm volatile (LOCK_PREFIX "xaddl %0, %1\n" \ + : "+r" (inc), "+m" (*(ptr)) \ + : : "memory", "cc"); \ + break; \ + case 8: \ + asm volatile (LOCK_PREFIX "xaddq %q0, %1\n" \ + : "+r" (inc), "+m" (*(ptr)) \ + : : "memory", "cc"); \ + break; \ + } \ + } while(0) +#endif /* _ASM_X86_CMPXCHG_64_H */
Signature · 1 line
1.7.5.4
[tip:x86/spinlocks] x86: Add xadd helper macro
Commit-ID: 847c73e8042e565a2cc4934c84103ab82e0eac42 Gitweb: http://git.kernel.org/tip/847c73e8042e565a2cc4934c84103ab82e0eac42 Author: Jeremy Fitzhardinge <[email protected]> AuthorDate: Thu, 23 Jun 2011 18:19:19 -0700 Committer: H. Peter Anvin <[email protected]> CommitDate: Fri, 22 Jul 2011 11:18:58 -0700
x86: Add xadd helper macro
--- arch/x86/include/asm/cmpxchg_32.h | 21 +++++++++++++++++++++ arch/x86/include/asm/cmpxchg_64.h | 26 ++++++++++++++++++++++++++ 2 files changed, 47 insertions(+), 0 deletions(-)
arch/x86/include/asm/cmpxchg_32.h +21 -0
@@ -280,4 +280,25 @@ static inline unsigned long cmpxchg_386(volatile void *ptr, unsigned long old,#endif +#define xadd (ptr, inc) \ + do { \ + switch (sizeof(*(ptr))) { \ + case 1: \ + asm volatile (LOCK_PREFIX "xaddb %b0, %1\n" \ + : "+r" (inc), "+m" (*(ptr)) \ + : : "memory", "cc"); \ + break; \ + case 2: \ + asm volatile (LOCK_PREFIX "xaddw %w0, %1\n" \ + : "+r" (inc), "+m" (*(ptr)) \ + : : "memory", "cc"); \ + break; \ + case 4: \ + asm volatile (LOCK_PREFIX "xaddl %0, %1\n" \ + : "+r" (inc), "+m" (*(ptr)) \ + : : "memory", "cc"); \ + break; \ + } \ + } while(0) +#endif /* _ASM_X86_CMPXCHG_32_H */
arch/x86/include/asm/cmpxchg_64.h +26 -0
@@ -151,4 +151,30 @@ extern void __cmpxchg_wrong_size(void);cmpxchg_local ((ptr), (o), (n)); \ }) +#define xadd (ptr, inc) \ + do { \ + switch (sizeof(*(ptr))) { \ + case 1: \ + asm volatile (LOCK_PREFIX "xaddb %b0, %1\n" \ + : "+r" (inc), "+m" (*(ptr)) \ + : : "memory", "cc"); \ + break; \ + case 2: \ + asm volatile (LOCK_PREFIX "xaddw %w0, %1\n" \ + : "+r" (inc), "+m" (*(ptr)) \ + : : "memory", "cc"); \ + break; \ + case 4: \ + asm volatile (LOCK_PREFIX "xaddl %0, %1\n" \ + : "+r" (inc), "+m" (*(ptr)) \ + : : "memory", "cc"); \ + break; \ + case 8: \ + asm volatile (LOCK_PREFIX "xaddq %q0, %1\n" \ + : "+r" (inc), "+m" (*(ptr)) \ + : : "memory", "cc"); \ + break; \ + } \ + } while(0) +#endif /* _ASM_X86_CMPXCHG_64_H */
PATCH 8/8 x86/ticketlock: use xadd helper
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
--- arch/x86/include/asm/spinlock.h | 9 +-------- 1 files changed, 1 insertions(+), 8 deletions(-)
arch/x86/include/asm/spinlock.h +1 -8
@@ -71,14 +71,7 @@ static __always_inline struct __raw_tickets __ticket_spin_claim(struct arch_spin { registerstruct __raw_tickets tickets = { .tail =1 }; -if (sizeof (lock->tickets.head) ==sizeof (u8)) - asmvolatile (LOCK_PREFIX "xaddw %w0, %1\n" - :"+r" (tickets),"+m" (lock->tickets) - : :"memory" ,"cc" ); -else - asmvolatile (LOCK_PREFIX "xaddl %0, %1\n" - :"+r" (tickets),"+m" (lock->tickets) - : :"memory" ,"cc" ); +xadd (&lock->tickets, tickets);return tickets; }
Signature · 1 line
1.7.5.4
[tip:x86/spinlocks] x86, ticketlock: Use xadd helper
Commit-ID: 599c3e7724ab4520c6f11857eb953271d365f842 Gitweb: http://git.kernel.org/tip/599c3e7724ab4520c6f11857eb953271d365f842 Author: Jeremy Fitzhardinge <[email protected]> AuthorDate: Thu, 23 Jun 2011 18:19:20 -0700 Committer: H. Peter Anvin <[email protected]> CommitDate: Fri, 22 Jul 2011 11:19:05 -0700
x86, ticketlock: Use xadd helper
--- arch/x86/include/asm/spinlock.h | 9 +-------- 1 files changed, 1 insertions(+), 8 deletions(-)
arch/x86/include/asm/spinlock.h +1 -8
@@ -71,14 +71,7 @@ static __always_inline struct __raw_tickets __ticket_spin_claim(struct arch_spin { registerstruct __raw_tickets tickets = { .tail =1 }; -if (sizeof (lock->tickets.head) ==sizeof (u8)) - asmvolatile (LOCK_PREFIX "xaddw %w0, %1\n" - :"+r" (tickets),"+m" (lock->tickets) - : :"memory" ,"cc" ); -else - asmvolatile (LOCK_PREFIX "xaddl %0, %1\n" - :"+r" (tickets),"+m" (lock->tickets) - : :"memory" ,"cc" ); +xadd (&lock->tickets, tickets);return tickets; }
H. Peter Anvin
reviewerQuoted 11 lines · Jeremy Fitzhardinge
I've been running with this code in place for several months on 4 core systems without any problems.
I couldn't measure a consistent performance difference between the two implemenations; there seemed to be +/- ~1% +/-, which is the level of variation I see from simply recompiling the kernel with slightly different code alignment.
Overall, I think the large reduction in code size is a big win.
Could you give us the delta in *compiled* code size?
-hpa
Quoted 4 lines · H. Peter Anvin
Quoted 3 lines · Jeremy Fitzhardinge
I've been running with this code in place for several months on 4 core systems without any problems.
Quoted 8 lines
Quoted 7 lines
I couldn't measure a consistent performance difference between the two implemenations; there seemed to be +/- ~1% +/-, which is the level of variation I see from simply recompiling the kernel with slightly different code alignment.
Overall, I think the large reduction in code size is a big win.
Could you give us the delta in *compiled* code size?
Sure. Do you mean for the individual lock sequences, or for the overall kernel?
J
H. Peter Anvin
reviewerQuoted 15 lines · Jeremy Fitzhardinge
Quoted 2 lines · H. Peter Anvin
Quoted 1 line · Jeremy Fitzhardinge
I've been running with this code in place for several months on 4
core
Quoted 3 lines
Quoted 3 lines
systems without any problems.
I couldn't measure a consistent performance difference between the
two
Quoted 1 line
Quoted 1 line
implemenations; there seemed to be +/- ~1% +/-, which is the level
of
Quoted 5 lines
Quoted 5 lines
variation I see from simply recompiling the kernel with slightly different code alignment.
Overall, I think the large reduction in code size is a big win.
Quoted 7 lines
Quoted 1 line
Could you give us the delta in *compiled* code size?
Sure. Do you mean for the individual lock sequences, or for the overall
kernel?J
Overall is fine.
Signature · 1 line
Sent from my mobile phone. Please excuse my brevity and lack of formatting.
Quoted 7 lines · H. Peter Anvin
Quoted 6 lines
Quoted 1 line
Could you give us the delta in *compiled* code size?
Sure. Do you mean for the individual lock sequences, or for the overall
kernel?J
Overall is fine.
Here's both ;)
For the NR_CPUS < 256 case, it shrinks the kernel text by a little over 1k (and a bit of a data reduction too?):
text data bss dec hex filename
7287009 1915524 2347008 11549541 b03b65 vmlinux-spin-base
7285777 1915412 2347008 11548197 b03625 vmlinux-cleantick
A comparison of spin_lock before:
<do_raw_spin_lock>:
55 push %rbp
48 89 e5 mov %rsp,%rbp
e8 6f fa 3d 00 callq <mcount>
b8 00 01 00 00 mov $0x100,%eax
f0 66 0f c1 07 lock xadd %ax,(%rdi)
1: 38 e0 cmp %ah,%al
74 06 je 2f
f3 90 pause
8a 07 mov (%rdi),%al
eb f6 jmp 1b
2: 5d pop %rbp
c3 retq and after:
<do_raw_spin_lock>:
55 push %rbp
48 89 e5 mov %rsp,%rbp
e8 1f f6 3d 00 callq <mcount>
b8 00 01 00 00 mov $0x100,%eax
f0 66 0f c1 07 lock xadd %ax,(%rdi)
0f b6 d4 movzbl %ah,%edx
1: 38 d0 cmp %dl,%al
74 06 je 2f
f3 90 pause
8a 07 mov (%rdi),%al
eb f6 jmp 1b
2: 5d pop %rbp
c3 retq IOW the generated code is identical except that the original has "cmp %ah,%al" and the compiler generates
movzbl %ah,%edx
cmp %dl,%al
I posted a bug about gcc not generating cmp %ah, %al in this case, but the general consensus was that it's not a good choice on current Intel chips, because it causes a partial word stall, and that the current generated code is better. (And gcc can generate "cmp %Xh, %Xl" if it wants to - see below.)
Likewise trylock before:
<do_raw_spin_trylock>:
55 push %rbp
48 89 e5 mov %rsp,%rbp
e8 50 fa 3d 00 callq <mcount>
0f b7 07 movzwl (%rdi),%eax
38 e0 cmp %ah,%al
8d 90 00 01 00 00 lea 0x100(%rax),%edx
75 05 jne 1f
f0 66 0f b1 17 lock cmpxchg %dx,(%rdi)
1: 0f 94 c2 sete %dl
0f b6 c2 movzbl %dl,%eax
5d pop %rbp
c3 retq and after:
<do_raw_spin_trylock>:
55 push %rbp
48 89 e5 mov %rsp,%rbp
e8 fd f5 3d 00 callq <mcount>
31 c0 xor %eax,%eax
66 8b 17 mov (%rdi),%dx
38 d6 cmp %dl,%dh
75 16 jne 1f
8d 8a 00 01 00 00 lea 0x100(%rdx),%ecx
89 d0 mov %edx,%eax
f0 66 0f b1 0f lock cmpxchg %cx,(%rdi)
66 39 d0 cmp %dx,%ax
0f 94 c0 sete %al
0f b6 c0 movzbl %al,%eax
1: 5d pop %rbp
c3 retq The differences here are a little more extensive, but the code is
broadly comparable. Some interesting points on the gcc code:
* it pre-loads the failure return value, so it doesn't need to use sete unless its actually doing the cmpxchg - whether this is good or not depends on how often trylock fails vs succeeds, but is pretty minor either way
* it generates a 16 bit load, rather than using zero extending 32-bit load
* it *can* generate a "cmp %dl,%dh" if it wants to
* it ends up re-comparing the "old" and "new" values after cmpxchg rather than reusing the flags it sets. This could be fixed by having a cmpxchg() variant which returns a flag rather than old, which would be generally useful since most cmpxchg() callers end up doing that comparison anyway.
spin_unlock is a little trickier to compare because it's inlined, but I'm guessing that's the source of the code shrinkage.
Likewise, for NR_CPUS=512, there's a ~900 byte kernel shrinkage with the new code:
text data bss dec hex filename
7296571 1945380 2424832 11666783 b2055f vmlinux-spin-base-big
7295610 1945412 2424832 11665854 b201be vmlinux-cleantick-big
The generated code for do_raw_spin_lock is even closer:
Before:
<do_raw_spin_lock>:
55 push %rbp
48 89 e5 mov %rsp,%rbp
e8 cf 0a 3e 00 callq <mcount>
b8 00 00 01 00 mov $0x10000,%eax
f0 0f c1 07 lock xadd %eax,(%rdi)
0f b7 d0 movzwl %ax,%edx
c1 e8 10 shr $0x10,%eax
1: 39 c2 cmp %eax,%edx
74 07 je 2f
f3 90 pause
0f b7 17 movzwl (%rdi),%edx
eb f5 jmp 1b
2: 5d pop %rbp
c3 retq After:
<do_raw_spin_lock>:
55 push %rbp
48 89 e5 mov %rsp,%rbp
e8 63 07 3e 00 callq <mcount>
b8 00 00 01 00 mov $0x10000,%eax
f0 0f c1 07 lock xadd %eax,(%rdi)
89 c2 mov %eax,%edx
c1 ea 10 shr $0x10,%edx
1: 66 39 d0 cmp %dx,%ax
74 07 je 2f
f3 90 pause
66 8b 07 mov (%rdi),%ax
eb f4 jmp 1b
2: 5d pop %rbp
c3 retq In other words, identical aside from using 16 bit regs rather than 32 bit regs and zero extend.
Trylock:
Before:
<do_raw_spin_trylock>:
55 push %rbp
48 89 e5 mov %rsp,%rbp
e8 aa 0a 3e 00 callq <mcount>
8b 07 mov (%rdi),%eax
89 c2 mov %eax,%edx
c1 c0 10 rol $0x10,%eax
39 c2 cmp %eax,%edx
8d 90 00 00 01 00 lea 0x10000(%rax),%edx
75 04 jne 1f
f0 0f b1 17 lock cmpxchg %edx,(%rdi)
1: 0f 94 c2 sete %dl
0f b6 c2 movzbl %dl,%eax
5d pop %rbp
c3 retq After:
<do_raw_spin_trylock>:
55 push %rbp
48 89 e5 mov %rsp,%rbp
e8 3e 07 3e 00 callq <mcount>
31 c0 xor %eax,%eax
8b 17 mov (%rdi),%edx
89 d1 mov %edx,%ecx
c1 e9 10 shr $0x10,%ecx
66 39 ca cmp %cx,%dx
75 14 jne 1f
8d 8a 00 00 01 00 lea 0x10000(%rdx),%ecx
89 d0 mov %edx,%eax
f0 0f b1 0f lock cmpxchg %ecx,(%rdi)
39 d0 cmp %edx,%eax
0f 94 c0 sete %al
0f b6 c0 movzbl %al,%eax
1: 5d pop %rbp
c3 retq The differences here are similar to the < 256 CPU case:
* gcc generates a straightforward shift and 16-bit compare to compare the head and tail, rather than the rol version (which I guess keeps everything 32b)
* same pre-loading the failure return value rather than reusing sete
* same redundant compare after cmpxchg
So conclusion:
* overall kernel code size reduction
* the spinlock code is very similar
* the trylock code could be improved a little, but its unclear to me that it would make much difference (since there's a big fat locked cmpxchg in the middle of any interesting code path)
* unlock is inlined, so I couldn't evaluate that, but since its just an unlocked inc, its hard to see how that could go wrong.
J
H. Peter Anvin
reviewerQuoted 5 lines · Jeremy Fitzhardinge
I posted a bug about gcc not generating cmp %ah, %al in this case, but the general consensus was that it's not a good choice on current Intel chips, because it causes a partial word stall, and that the current generated code is better. (And gcc can generate "cmp %Xh, %Xl" if it wants to - see below.)
Which version of gcc is this, and also, do you have the gcc bug report number? I was talking to H.J. and he said he thought it sounded strange.
-hpa
Quoted 7 lines · H. Peter Anvin
Quoted 4 lines · Jeremy Fitzhardinge
I posted a bug about gcc not generating cmp %ah, %al in this case, but the general consensus was that it's not a good choice on current Intel chips, because it causes a partial word stall, and that the current generated code is better. (And gcc can generate "cmp %Xh, %Xl" if it wants to - see below.)
Which version of gcc is this, and also, do you have the gcc bug report number? I was talking to H.J. and he said he thought it sounded strange.
gcc version 4.6.0 20110530 (Red Hat 4.6.0-9) (GCC)
It's bug 47556.
J
Quoted 8 lines · Jeremy Fitzhardinge
2. With
NR_CPUS< 256 the ticket size is 8 bits. The compiler doesn't use the same trick as the hand-coded asm to directly compare the high and low bytes in the word, but does a bit of extra shuffling around. However, the Intel optimisation guide and several x86 experts have opined that its best to avoid the high-byte operations anyway, since they will cause a partial word stall, and the gcc-generated code should be better.
Quoted 7 lines
Overall the compiler-generated code is very similar to the hand-coded versions, with the partial byte operations being the only significant difference. (Curiously, gcc does generate a high-byte compare for me in trylock, so it can if it wants to.)
I've been running with this code in place for several months on 4 core systems without any problems.
Please do measurements both in terms of disassembly based instruction count(s) in the fastpath(s) (via looking at the before/after disassembly) and actual cycle, instruction and branch counts (via perf measurements).
Quoted 4 lines
I couldn't measure a consistent performance difference between the two implemenations; there seemed to be +/- ~1% +/-, which is the level of variation I see from simply recompiling the kernel with slightly different code alignment.
Then you've done the micro-cost measurements the wrong way - we can and do detect much finer effects than 1%, see the methods used in this commit for example:
c8b281161dfa: sched: Increase SCHED_LOAD_SCALE resolution
Please also ensure that the cold-cache behavior is fairly measured via hot-cache benchmarks (that is not always guaranteed).
Thanks,
Ingo
Quoted 5 lines · Jeremy Fitzhardinge
I couldn't measure a consistent performance difference between the two implemenations; there seemed to be +/- ~1% +/-, which is the level of variation I see from simply recompiling the kernel with slightly different code alignment.
I ran your new locks in my lock tester and I have a similar experience. There's some variation, but it seems to be in the usual variance. In some cases the C locks were actually faster.
-Andi
Signature · 1 line
[email protected] -- Speaking for myself only
Quoted 8 lines · Andi Kleen
Quoted 4 lines · Jeremy Fitzhardinge
I couldn't measure a consistent performance difference between the two implemenations; there seemed to be +/- ~1% +/-, which is the level of variation I see from simply recompiling the kernel with slightly different code alignment.
I ran your new locks in my lock tester and I have a similar experience. There's some variation, but it seems to be in the usual variance. In some cases the C locks were actually faster.
Yes, I observed cases where they were faster. What is your lock tester? Does it test the lock code in isolation, or in situ?
Thanks,
J
Quoted 3 lines · Jeremy Fitzhardinge
Yes, I observed cases where they were faster. What is your lock tester? Does it test the lock code in isolation, or in situ?
User space harness to test a couple of lock scenarios with different numbers of CPUs competing.
It tests the lock code in isolation.
-Andi
Signature · 1 line
[email protected] -- Speaking for myself only
Quoted 8 lines · Andi Kleen
Quoted 4 lines · Jeremy Fitzhardinge
I couldn't measure a consistent performance difference between the two implemenations; there seemed to be +/- ~1% +/-, which is the level of variation I see from simply recompiling the kernel with slightly different code alignment.
I ran your new locks in my lock tester and I have a similar experience. There's some variation, but it seems to be in the usual variance. In some cases the C locks were actually faster.
Is your test harness available?
J