Convert powerpc simple spinlocks into ticket locks
Subsystems (2)
PATCH 1/1 Convert powerpc simple spinlocks into ticket locks
x86 has them, MIPS has them, ARM has them, even ia64 has them:
ticket locks. They reduce memory bus and cache pressure especially for contended spinlocks, increasing performance.
This patch is a port of the x86 spin locks, mostly written in C, to the powerpc, introducing inline asm where needed. The pSeries directed yield for vCPUs is taken care of by an additional "holder" field in the lock.
--
arch/powerpc/include/asm/spinlock_types.h | 27 ++++- arch/powerpc/include/asm/spinlock.h | 157 +++++++++++++++++++++++------- arch/powerpc/lib/locks.c | 6 - 3 files changed, 151 insertions(+), 39 deletions(-)
arch/powerpc/include/asm/spinlock_types.h +23 -4
@@ -5,11 +5,30 @@# error "please don't include this file directly"#endif -typedef struct { -volatile unsigned int slock; -}arch_spinlock_t ; +typedef u16 __ticket_t ; +typedef u32 __ticketpair_t ; + +#define TICKET_LOCK_INC ((__ticket_t)1) + +#define TICKET_SHIFT (sizeof(__ticket_t) * 8) + +typedef struct arch_spinlock { +union { +__ticketpair_t head_tail; +struct __raw_tickets { +#ifdef __BIG_ENDIAN__/* The "tail" part should be in the MSBs */ +__ticket_t tail, head; +#else +__ticket_t head, tail; +#endif + } tickets; + }; +#if defined(CONFIG_PPC64 ) +u32 holder; +#endif +}arch_spinlock_t __aligned(8) ; -#define __ARCH_SPIN_LOCK_UNLOCKED { 0 } +#define __ARCH_SPIN_LOCK_UNLOCKED { { 0 }, 0 } typedef struct { volatile signed int lock;
arch/powerpc/include/asm/spinlock.h +125 -32
233 lines not on this page · raw message
arch/powerpc/lib/locks.c +3 -3
@@ -27,7 +27,7 @@ void __spin_yield(arch_spinlock_t *lock) {unsigned int lock_value, holder_cpu, yield_count; - lock_value = lock->slock; + lock_value = lock->holder;if (lock_value ==0 )return ; holder_cpu = lock_value &0xffff ;
@@ -36,7 +36,7 @@ void __spin_yield(arch_spinlock_t *lock)if ((yield_count &1 ) ==0 )return ;/* virtual cpu is currently running */ rmb (); -if (lock->slock != lock_value) +if (lock->holder != lock_value)return ;/* something has changed */ plpar_hcall_norets (H_CONFER ,get_hard_smp_processor_id (holder_cpu), yield_count);
@@ -70,7 +70,7 @@ void __rw_yield(arch_rwlock_t *rw)void arch_spin_unlock_wait (arch_spinlock_t *lock) { -while (lock->slock) { +while (arch_spin_is_locked (lock)) {HMT_low ();if (SHARED_PROCESSOR )__spin_yield (lock);
Quoted 8 lines · Torsten Duwe
x86 has them, MIPS has them, ARM has them, even ia64 has them:
ticket locks. They reduce memory bus and cache pressure especially for contended spinlocks, increasing performance.This patch is a port of the x86 spin locks, mostly written in C, to the powerpc, introducing inline asm where needed. The pSeries directed yield for vCPUs is taken care of by an additional "holder" field in the lock.
Thanks, I've been meaning to look into this for ages and never quite got to it :-)
I'm travelling right now, I'll review this next week.
Cheers,
Ben.
Quoted 328 lines
Signed-off-by Torsten Duwe <[email protected]>--
arch/powerpc/include/asm/spinlock_types.h | 27 ++++- arch/powerpc/include/asm/spinlock.h | 157 +++++++++++++++++++++++------- arch/powerpc/lib/locks.c | 6 - 3 files changed, 151 insertions(+), 39 deletions(-)arch/powerpc/include/asm/spinlock_types.h +23
-4@@ -5,11 +5,30 @@# error "please don't include this file directly"#endif -typedef struct { -volatile unsigned int slock; -}arch_spinlock_t ; +typedef u16 __ticket_t ; +typedef u32 __ticketpair_t ; + +#define TICKET_LOCK_INC ((__ticket_t)1) + +#define TICKET_SHIFT (sizeof(__ticket_t) * 8) + +typedef struct arch_spinlock { +union { +__ticketpair_t head_tail; +struct __raw_tickets { +#ifdef __BIG_ENDIAN__/* The "tail" part should be in the MSBs */ +__ticket_t tail, head; +#else +__ticket_t head, tail; +#endif + } tickets; + }; +#if defined(CONFIG_PPC64 ) +u32 holder; +#endif +}arch_spinlock_t __aligned(8) ; -#define __ARCH_SPIN_LOCK_UNLOCKED { 0 } +#define __ARCH_SPIN_LOCK_UNLOCKED { { 0 }, 0 } typedef struct { volatile signed int lock;arch/powerpc/include/asm/spinlock.h +125
-32@@ -9,8 +9,7 @@* Copyright (C) 2001 Anton Blanchard <[email protected]>, IBM * Copyright (C) 2002 Dave Engebretsen <[email protected]>, IBM * Rework to support virtual processors -* -* Type of int is used as a full 64b word is not necessary. +* Copyright (C) 2014 Torsten Duwe <[email protected]>, ticket lock port * * This program is free software; you can redistribute it and/or * modify it under the terms of the GNU General Public License @@ -28,7 +27,20 @@#include <asm/synch.h> #include <asm/ppc-opcode.h> -#define arch_spin_is_locked (x) ((x)->slock != 0) +static inline int arch_spin_is_locked (arch_spinlock_t *lock) +{ +struct __raw_tickets tmp =ACCESS_ONCE (lock->tickets); + +return tmp.tail != tmp.head; +} + +static inline int arch_spin_is_contended (arch_spinlock_t *lock) +{ +struct __raw_tickets tmp =ACCESS_ONCE (lock->tickets); + +return (__ticket_t)(tmp.tail - tmp.head) >TICKET_LOCK_INC ; +} +#define arch_spin_is_contended arch_spin_is_contended#ifdef CONFIG_PPC64 /* use 0x800000yy when locked, where yy == CPU number */ @@ -37,8 +49,12 @@#else #define LOCK_TOKEN (*(u32 *)(&get_paca()->paca_index))#endif +#define SIZE_LETTER "d" +#define L64 "1"#else #define LOCK_TOKEN 1 +#define SIZE_LETTER "w" +#define L64 "0"#endif #if defined(CONFIG_PPC64 ) && defined(CONFIG_SMP )@@ -55,33 +71,59 @@#endif /* -* This returns the old value in the lock, so we succeeded -* in getting the lock if the return value is 0. +* Our own cmpxchg, operating on spinlock_t's. Returns 0 iff value +* read at lock was equal to "old" AND the cmpxchg succeeded +* uninterruptedly. */ -static inline unsigned long __arch_spin_trylock (arch_spinlock_t *lock) +static __always_inline int __arch_spin_cmpxchg_eq(arch_spinlock_t *lock, +arch_spinlock_t old, +arch_spinlock_t new) { -unsigned long tmp, token; + registerint retval =1 ; + registerarch_spinlock_t tmp; + + __asm__ __volatile__ ( +" li %0,1\n" /* default to "fail" */ +PPC_RELEASE_BARRIER +"1: l" SIZE_LETTER "arx %2,0,%5 # __arch_spin_cmpxchg_eq\n" +" cmp 0," L64 ",%3,%2\n" +" bne- 2f\n" + PPC405_ERR77(0, "%5") +" st" SIZE_LETTER "cx. %4,0,%5\n" +" bne- 1b\n" +" isync\n" +" li %0,0\n" +"2:" + : "=&r" (retval), "+m" (*lock) + : "r" (tmp), "r" (old), "r" (new), "r" (lock) + : "cc", "memory"); + + return retval; +} +#undef SIZE_LETTER +#undef L64 - token =LOCK_TOKEN ; - __asm__ __volatile__( -"1: " PPC_LWARX(%0,0,%2,1) "\n\ -cmpwi 0,%0,0\n\ -bne- 2f\n\ -stwcx. %1,0,%2\n\ -bne- 1b\n" -PPC_ACQUIRE_BARRIER -"2:" - : "=&r" (tmp) - : "r" (token), "r" (&lock->slock) - : "cr0", "memory"); +static __always_inline int __arch_spin_trylock(arch_spinlock_t *lock) +{ +arch_spinlock_t old, new; - return tmp; + old.tickets =ACCESS_ONCE (lock->tickets); +if (old.tickets.head != old.tickets.tail) +return 0 ; + + new.head_tail = old.head_tail + (TICKET_LOCK_INC <<TICKET_SHIFT ); +#if defined(CONFIG_PPC64 ) + old.holder = lock->holder; + new.holder =LOCK_TOKEN ; +#endif + +return !__arch_spin_cmpxchg_eq (lock, old, new); }static inline int arch_spin_trylock (arch_spinlock_t *lock) {CLEAR_IO_SYNC ; -return __arch_spin_trylock (lock) ==0 ; +return __arch_spin_trylock (lock); }/* @@ -93,9 +135,8 @@ static inline int arch_spin_trylock(arch_spinlock_t *lock)* rest of our timeslice to the lock holder. * * So that we can tell which virtual processor is holding a lock, -* we put 0x80000000 | smp_processor_id() in the lock when it is -* held. Conveniently, we have a word in the paca that holds this -* value. +* we put 0x80000000 | smp_processor_id() into lock->holder. +* Conveniently, we have a word in the paca that holds this value. */ #if defined(CONFIG_PPC_SPLPAR )@@ -109,19 +150,59 @@ extern void __rw_yield(arch_rwlock_t *lock);#define SHARED_PROCESSOR 0#endif -static inline void arch_spin_lock (arch_spinlock_t *lock) +/* +* Ticket locks are conceptually two parts, one indicating the current head of +* the queue, and the other indicating the current tail. The lock is acquired +* by atomically noting the tail and incrementing it by one (thus adding +* ourself to the queue and noting our position), then waiting until the head +* becomes equal to the the initial value of the tail. +* +* We use an asm covering *both* parts of the lock, to increment the tail and +* also load the position of the head, which takes care of memory ordering +* issues and should be optimal for the uncontended case. Note the tail must be +* in the high part, because a wide add increment of the low part would carry +* up and contaminate the high part. +*/ +static __always_inline void arch_spin_lock(arch_spinlock_t *lock) { + registerstruct __raw_tickets old, tmp, + inc = { .tail =TICKET_LOCK_INC }; +CLEAR_IO_SYNC ; -while (1 ) { -if (likely (__arch_spin_trylock (lock) ==0 )) -break ; + __asm__ __volatile__( +"1: lwarx %0,0,%4 # arch_spin_lock\n" +" add %1,%3,%0\n" + PPC405_ERR77(0, "%4") +" stwcx. %1,0,%4\n" +" bne- 1b" + : "=&r" (old), "=&r" (tmp), "+m" (lock->tickets) + : "r" (inc), "r" (&lock->tickets) + : "cc"); + +if (likely (old.head == old.tail)) { +#if defined(CONFIG_PPC64 ) + lock->holder =LOCK_TOKEN ; +#endif + goto out; + } + +for (;;) { +unsigned count =100 ; +do { +if (ACCESS_ONCE (lock->tickets.head) == old.tail) { +#if defined(CONFIG_PPC64 ) + lock->holder =LOCK_TOKEN ; +#endif + goto out; + }HMT_low ();if (SHARED_PROCESSOR )__spin_yield (lock); - }while (unlikely (lock->slock !=0 )); + }while (--count);HMT_medium (); } +out:barrier ();/* make sure nothing creeps before the lock is taken */ } static inline@@ -131,7 +211,7 @@ void arch_spin_lock_flags(arch_spinlock_t *lock, unsigned long flags)CLEAR_IO_SYNC ;while (1 ) { -if (likely (__arch_spin_trylock (lock) ==0 )) +if (likely (__arch_spin_trylock (lock)))break ;local_save_flags (flags_dis);local_irq_restore (flags);@@ -139,7 +219,7 @@ void arch_spin_lock_flags(arch_spinlock_t *lock, unsigned long flags)HMT_low ();if (SHARED_PROCESSOR )__spin_yield (lock); - }while (unlikely (lock->slock !=0 )); + }while (arch_spin_is_locked (lock));HMT_medium ();local_irq_restore (flags_dis); }@@ -147,10 +227,22 @@ void arch_spin_lock_flags(arch_spinlock_t *lock, unsigned long flags)static inline void arch_spin_unlock (arch_spinlock_t *lock) { +arch_spinlock_t old, new; + +#if defined(CONFIG_PPC64 ) + new.holder =0 ; +#endif +do { + old.tickets =ACCESS_ONCE (lock->tickets); +#if defined(CONFIG_PPC64 ) + old.holder = lock->holder; +#endif + new.tickets.head = old.tickets.head +TICKET_LOCK_INC ; + new.tickets.tail = old.tickets.tail; + }while (unlikely (__arch_spin_cmpxchg_eq (lock, old, new)));SYNC_IO ; __asm__ __volatile__("# arch_spin_unlock\n\t" PPC_RELEASE_BARRIER : : :"memory" ); - lock->slock =0 ; }#ifdef CONFIG_PPC64 arch/powerpc/lib/locks.c +3
-4@@ -27,7 +27,7 @@ void __spin_yield(arch_spinlock_t *lock) {unsigned int lock_value, holder_cpu, yield_count; - lock_value = lock->slock; + lock_value = lock->holder;if (lock_value ==0 )return ; holder_cpu = lock_value &0xffff ;@@ -36,7 +36,7 @@ void __spin_yield(arch_spinlock_t *lock)if ((yield_count &1 ) ==0 )return ;/* virtual cpu is currently running */ rmb (); -if (lock->slock != lock_value) +if (lock->holder != lock_value)return ;/* something has changed */ plpar_hcall_norets (H_CONFER ,get_hard_smp_processor_id (holder_cpu), yield_count);@@ -70,7 +70,7 @@ void __rw_yield(arch_rwlock_t *rw)void arch_spin_unlock_wait (arch_spinlock_t *lock) { -while (lock->slock) { +while (arch_spin_is_locked (lock)) {HMT_low ();if (SHARED_PROCESSOR )__spin_yield (lock); --To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Peter Zijlstra
maintainerQuoted 9 lines · Torsten Duwe
x86 has them, MIPS has them, ARM has them, even ia64 has them:
ticket locks. They reduce memory bus and cache pressure especially for contended spinlocks, increasing performance.This patch is a port of the x86 spin locks, mostly written in C, to the powerpc, introducing inline asm where needed. The pSeries directed yield for vCPUs is taken care of by an additional "holder" field in the lock.
A few questions; what's with the ppc64 holder thing? Not having a 32bit spinlock_t is sad.
Can you pair lwarx with sthcx ? I couldn't immediately find the answer in the PowerISA doc. If so I think you can do better by being able to atomically load both tickets but only storing the head without affecting the tail.
In that case you can avoid the ll/sc on unlock, because only the lock owner can modify the tail, so you can use a single half-word store.
Quoted 5 lines · Peter Zijlstra
Quoted 4 lines · Torsten Duwe
x86 has them, MIPS has them, ARM has them, even ia64 has them:
ticket locks. They reduce memory bus and cache pressure especially for contended spinlocks, increasing performance.
Quoted 8 lines
Quoted 5 lines
This patch is a port of the x86 spin locks, mostly written in C, to the powerpc, introducing inline asm where needed. The pSeries directed yield for vCPUs is taken care of by an additional "holder" field in the lock.
A few questions; what's with the ppc64 holder thing? Not having a 32bit
spinlock_tis sad.
I must admit that I haven't tested the patch on non-pseries ppc64 nor on ppc32. Only ppc64 has the ldarx and I tried to atomically replace the holder along with the locks. That might prove unneccessary.
Quoted 4 lines
Can you pair lwarx with sthcx ? I couldn't immediately find the answer in the PowerISA doc. If so I think you can do better by being able to atomically load both tickets but only storing the head without affecting the tail.
V2.06b, Book II, Chapter 3, "sthcx" says:
| If a reservation exists and the length associated [...] is not 2 bytes, | it is undefined whether (RS)_48:63 are stored [...]
That doesn't make me feel comfortable :(
Torsten
Peter Zijlstra
maintainerQuoted 12 lines · Torsten Duwe
Quoted 11 lines · Peter Zijlstra
Quoted 9 lines · Torsten Duwe
x86 has them, MIPS has them, ARM has them, even ia64 has them:
ticket locks. They reduce memory bus and cache pressure especially for contended spinlocks, increasing performance.This patch is a port of the x86 spin locks, mostly written in C, to the powerpc, introducing inline asm where needed. The pSeries directed yield for vCPUs is taken care of by an additional "holder" field in the lock.
Quoted 6 lines
Quoted 2 lines
A few questions; what's with the ppc64 holder thing? Not having a 32bit
spinlock_tis sad.I must admit that I haven't tested the patch on non-pseries ppc64 nor on ppc32. Only ppc64 has the ldarx and I tried to atomically replace the holder along with the locks. That might prove unneccessary.
But what is the holder for? Can't we do away with that field?
Quoted 10 lines
Quoted 4 lines
Can you pair lwarx with sthcx ? I couldn't immediately find the answer in the PowerISA doc. If so I think you can do better by being able to atomically load both tickets but only storing the head without affecting the tail.
V2.06b, Book II, Chapter 3, "sthcx" says:
| If a reservation exists and the length associated [...] is not 2 bytes, | it is undefined whether (RS)_48:63 are stored [...]That doesn't make me feel comfortable :(
That's on page 692, right? The way I read that is of the lharx/sthcx don't have the exact same address, storage is undefined. But I can't find mention of non-matching load and store size, although I can imagine it being the same undefined.
Quoted 9 lines · Peter Zijlstra
Quoted 9 lines
Quoted 9 lines
Can you pair lwarx with sthcx ? I couldn't immediately find the answer
Quoted 3 lines
Quoted 3 lines
in the PowerISA doc. If so I think you can do better by being able to atomically load both tickets but only storing the head without affecting the tail.
V2.06b, Book II, Chapter 3, "sthcx" says:
| If a reservation exists and the length associated [...] is not 2 bytes, | it is undefined whether (RS)_48:63 are stored [...]
Quoted 5 lines
Quoted 1 line
Quoted 1 line
That doesn't make me feel comfortable :(
That's on page 692, right? The way I read that is of the lharx/sthcx don't have the exact same address, storage is undefined. But I can't find mention of non-matching load and store size, although I can imagine it being the same undefined.
My read is consistent with Torsten's ... this looks like a bad idea.
Look at the RTL for sthcx. on page 692 (Power ISA V2.06) and you will see this:
if RESERVE then
if RESERVE_LENGTH = 2 then
...
else
undefined_case <- 1
else
...
A legal implementation might never perform the store.
Quoted 12 lines · Torsten Duwe
Quoted 11 lines · Peter Zijlstra
Quoted 9 lines · Torsten Duwe
x86 has them, MIPS has them, ARM has them, even ia64 has them:
ticket locks. They reduce memory bus and cache pressure especially for contended spinlocks, increasing performance.This patch is a port of the x86 spin locks, mostly written in C, to the powerpc, introducing inline asm where needed. The pSeries directed yield for vCPUs is taken care of by an additional "holder" field in the lock.
Quoted 6 lines
Quoted 2 lines
A few questions; what's with the ppc64 holder thing? Not having a 32bit
spinlock_tis sad.I must admit that I haven't tested the patch on non-pseries ppc64 nor on ppc32. Only ppc64 has the ldarx and I tried to atomically replace the holder along with the locks. That might prove unneccessary.
Why is the functionality of holder only required on 64-bit? We have too many 32/64 differences as is. Perhaps on 32-bit a lower max number of CPUs could be assumed, to make it fit in one word.
Quoted 10 lines
Quoted 4 lines
Can you pair lwarx with sthcx ? I couldn't immediately find the answer in the PowerISA doc. If so I think you can do better by being able to atomically load both tickets but only storing the head without affecting the tail.
V2.06b, Book II, Chapter 3, "sthcx" says:
| If a reservation exists and the length associated [...] is not 2 bytes, | it is undefined whether (RS)_48:63 are stored [...]That doesn't make me feel comfortable :(
Plus, sthcx doesn't exist on all PPC chips.
-Scott
Quoted 6 lines · Peter Zijlstra
Quoted 3 lines · Torsten Duwe
I must admit that I haven't tested the patch on non-pseries ppc64 nor on ppc32. Only ppc64 has the ldarx and I tried to atomically replace the holder along with the locks. That might prove unneccessary.
But what is the holder for? Can't we do away with that field?
Scott, Peter: good questions.
The conditional is wrong because I confused pSeries with ppc64 CPUs with 64-bit kernels. I got deluded by the LOCK_TOKEN definition above. Is that correctly ifdef'd, with PPC64? The holder field should be ifdef'd CONFIG_PPC_SPLPAR, independent of ppc64.
It is an advisory performance hint, and doesn't need to be updated atomically with the lock; this and the above are 2 reasons to drop the asm string operand size voodoo as well.
Thanks,
Torsten
Quoted 7 lines · Scott Wood
Quoted 6 lines · Torsten Duwe
Quoted 4 lines · Peter Zijlstra
Can you pair lwarx with sthcx ? I couldn't immediately find the answer in the PowerISA doc. If so I think you can do better by being able to atomically load both tickets but only storing the head without affecting the tail.
Can I simply write the half word, without a reservation, or will the HW caches mess up the other half? Will it ruin the cache coherency on some (sub)architectures?
Quoted 1 line
Plus, sthcx doesn't exist on all PPC chips.
Which ones are lacking it? Do all have at least a simple 16-bit store?
Torsten
Peter Zijlstra
maintainerQuoted 11 lines · Torsten Duwe
Quoted 7 lines · Scott Wood
Quoted 6 lines · Torsten Duwe
Quoted 4 lines · Peter Zijlstra
Can you pair lwarx with sthcx ? I couldn't immediately find the answer in the PowerISA doc. If so I think you can do better by being able to atomically load both tickets but only storing the head without affecting the tail.
Can I simply write the half word, without a reservation, or will the HW caches mess up the other half? Will it ruin the cache coherency on some (sub)architectures?
So if you have ll/sc on the whole word concurrent with the half-word store, you can loose the half-word store like:
lwarx &tickets
... sth &tail
stwcd &tickets
The stwcd will over-write the tail store.
Anyway, what might work is something like (please forgive my ppc asm, I can barely read the thing, I've never before attempted writing it):
lock:
1: lharx %0, 0, &head
mov %1, %0 addic %0, %0, 1 stwcd %0, 0, &head bne- 1b
2: lhax %0, 0, &tail
lwsync cmp 0, %0, %0 bne- 2b
unlock:
lhz %0, 0, &tail addic %0, %0, 1 lwsync sth %0, 0, &tail
Which would somewhat translate into C as:
static inline void ticket_spin_lock(tickets_t *lock)
{
ticket_t mine = xadd(&lock->head);
while (smp_load_acquire(&lock->tail) != mine)
cpu_relax();
}static inline void ticket_spin_unlock(tickets_t *lock)
{
ticket_t tail = lock->tail + 1;
smp_store_release(&lock->tail, tail);
}Where xadd() returns the value before addition and we assume half word single-copy atomicy, such that the head and tail updates will not interfere.
The x86 implementation uses the 32bit xadd and places the head at the MSB end to get the atomic add + tail load in a single instruction, but for PPC its much better to have an extra load (to an already hot cacheline) and avoid a second ll/sc pair, as the ll/sc things are stupid slow for your arch afaik.
Peter Zijlstra
maintainerQuoted 9 lines
So if you have ll/sc on the whole word concurrent with the half-word store, you can loose the half-word store like:
lwarx &tickets
... sth &tail
stwcd &ticketsThe stwcd will over-write the tail store.
Oh wait, that's stupid, it will invalidate the lock and fail the store and make it try again, so you could try and combine the load, but you'd need an extra shift instruction instead of an extra load.
Not sure that's a valid trade-off..
Peter Zijlstra
maintainerQuoted 10 lines · Peter Zijlstra
Anyway, what might work is something like (please forgive my ppc asm, I can barely read the thing, I've never before attempted writing it):
lock:
1: lharx %0, 0, &headmov %1, %0 addic %0, %0, 1 stwcd %0, 0, &head bne- 1b2: lhax %0, 0, &tail
That might need to be lhz too, I'm confused on all the load variants.
Quoted 2 lines
lwsync cmp 0, %0, %0
cmp 0, %0, %1
So we compare the &tail load to the xadd return %1 above.
Quoted 9 lines
bne- 2bunlock:
lhz %0, 0, &tail addic %0, %0, 1 lwsync sth %0, 0, &tail
Quoted 2 lines · Peter Zijlstra
That might need to be lhz too, I'm confused on all the load variants.
;-)
Quoted 3 lines
Quoted 3 lines
unlock:
lhz %0, 0, &tail addic %0, %0, 1
No carry with this one, I'd say.
Besides, unlock increments the head.
Quoted 3 lines
Quoted 3 lines
lwsync sth %0, 0, &tail
Given the beauty and simplicity of this, may I ask Ingo:
you signed off 314cdbefd1fd0a7acf3780e9628465b77ea6a836; can you explain why head and tail must live on the same cache line? Or is it just a space saver? I just ported it to ppc, I didn't think about alternatives.
What about
atomic_t tail;
volatile int head; ?
Admittedly, that's usually 8 bytes instead of 4...
Torsten
Peter Zijlstra
maintainerQuoted 11 lines · Torsten Duwe
Quoted 2 lines · Peter Zijlstra
That might need to be lhz too, I'm confused on all the load variants.
;-)
Quoted 3 lines
Quoted 3 lines
unlock:
lhz %0, 0, &tail addic %0, %0, 1No carry with this one, I'd say.
Right you are, add immediate it is.
Quoted 1 line
Besides, unlock increments the head.
No, unlock increments the tail, lock increments the head and waits until the tail matches the pre-inc value.
That said, why do the atomic_inc() primitives do an carry add? (that's where I borrowed it from).
Quoted 9 lines
Quoted 3 lines
Quoted 3 lines
lwsync sth %0, 0, &tailGiven the beauty and simplicity of this, may I ask Ingo:
you signed off314cdbefd1fd0a7acf3780e9628465b77ea6a836; can you explain why head and tail must live on the same cache line? Or is it just a space saver? I just ported it to ppc, I didn't think about alternatives.
spinlock_t should, ideally, be 32bits.
Quoted 6 lines
What about
atomic_ttail;
volatile int head; ?Admittedly, that's usually 8 bytes instead of 4...
That still won't straddle a cacheline unless you do weird alignement things which will bloat all the various data structures more still.
Anyway, you can do a version with lwarx/stwcx if you're looking get rid of lharx.
Peter Zijlstra
maintainerQuoted 2 lines · Peter Zijlstra
Anyway, you can do a version with lwarx/stwcx if you're looking get rid of lharx.
the below seems to compile into relatively ok asm. It can be done better if you write the entire thing by hand though.
---
typedef unsigned short ticket_t;
typedef struct {
union {
unsigned int pair;
struct {
/* ensure @head is the MSB */
#ifdef __BIG_ENDIAN__
ticket_t head,tail;
#else
ticket_t tail,head;
#endif
};
};
} tickets_t;#define ACCESS_ONCE(x) (*(volatile typeof(x) *)&(x))
#define barrier() __asm__ __volatile__ ("" : : :"memory")
#define __lwsync() __asm__ __volatile__ ("lwsync" : : :"memory")
#define smp_store_release(p, v) \
do { \
__lwsync(); \
ACCESS_ONCE(*p) = (v); \} while (0)
#define smp_load_acquire(p) \
({ \
typeof(*p) ___p1 = ACCESS_ONCE(*p); \
__lwsync(); \
___p1; \})
#define likely(x) __builtin_expect(!!(x), 1)
#define cpu_relax() barrier();
static inline unsigned int xadd(unsigned int *v, unsigned int i)
{
int t, ret;
__asm__ __volatile__ ("1: lwarx %0, 0, %4\n"
" mr %1, %0\n"
" add %0, %3, %0\n"
" stwcx. %0, %0, %4\n"
" bne- 1b\n"
: "=&r" (t), "=&r" (ret), "+m" (*v) : "r" (i), "r" (v) : "cc"); return ret; }
void ticket_lock(tickets_t *lock)
{
tickets_t t;
/*
* Because @head is MSB, the direct increment wrap doesn't disturb
* @tail.
*/
t.pair = xadd(&lock->pair, 1<<16);
if (likely(t.head == t.tail)) {
__lwsync(); /* acquire */
return;
}
while (smp_load_acquire(&lock->tail) != t.tail)
cpu_relax();
}void ticket_unlock(tickets_t *lock)
{
ticket_t tail = lock->tail + 1;
/*
* The store is save against the xadd for it will make the ll/sc fail
* and try again. Aside from that PowerISA guarantees single-copy
* atomicy for half-word writes.
*
* And since only the lock owner will ever write the tail, we're good.
*/
smp_store_release(&lock->tail, tail);
}Peter Zijlstra
maintainerQuoted 17 lines · Peter Zijlstra
void
ticket_lock(tickets_t *lock){ tickets_t t; /* * Because @head is MSB, the direct increment wrap doesn't disturb * @tail. */ t.pair = xadd(&lock->pair, 1<<16); if (likely(t.head == t.tail)) { __lwsync(); /* acquire */ return; } while (smp_load_acquire(&lock->tail) != t.tail) cpu_relax();
That should be "!= t.head", for that contains our ticket.
I'm hopelessly scatter brained today it seems :/
Quoted 15 lines
}
void
ticket_unlock(tickets_t *lock){ ticket_t tail = lock->tail + 1; /* * The store is save against the xadd for it will make the ll/sc fail * and try again. Aside from that PowerISA guarantees single-copy * atomicy for half-word writes. * * And since only the lock owner will ever write the tail, we're good. */ smp_store_release(&lock->tail, tail); }
Quoted 5 lines · Torsten Duwe
Quoted 4 lines · Scott Wood
Quoted 1 line · Torsten Duwe
On Thu, Feb 06, 2014 at 05:38:37PM +0100, Peter Zijlstra wrote:
=20
Quoted 1 line
Quoted 1 line
Can you pair lwarx with sthcx ? I couldn't immediately find the =
answer
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
in the PowerISA doc. If so I think you can do better by being able =
to
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
atomically load both tickets but only storing the head without =
affecting
Quoted 3 lines
Quoted 1 line
Quoted 1 line
Quoted 1 line
the tail.
=20
Can I simply write the half word, without a reservation, or will the =
HW caches
Quoted 1 line
mess up the other half? Will it ruin the cache coherency on some =
(sub)architectures?
The coherency should be fine, I just can=92t remember if you=92ll lose = the reservation by doing this.
Quoted 3 lines
Quoted 1 line
Plus, sthcx doesn't exist on all PPC chips.
=20
Which ones are lacking it? Do all have at least a simple 16-bit store?
Everything implements a simple 16-bit store, just not everything = implements the store conditional of 16-bit data.
- k=
Peter Zijlstra
maintainerQuoted 12 lines · Kumar Gala
Quoted 9 lines · Torsten Duwe
Quoted 7 lines · Scott Wood
Quoted 6 lines · Torsten Duwe
Quoted 4 lines · Peter Zijlstra
Can you pair lwarx with sthcx ? I couldn't immediately find the answer in the PowerISA doc. If so I think you can do better by being able to atomically load both tickets but only storing the head without affecting the tail.
Quoted 4 lines
Quoted 2 lines
Can I simply write the half word, without a reservation, or will the HW caches mess up the other half? Will it ruin the cache coherency on some (sub)architectures?
The coherency should be fine, I just can’t remember if you’ll lose the reservation by doing this.
It should; I suppose; seeing how you 'destroy' the state it got from the load.
Quoted 5 lines
Quoted 3 lines
Quoted 1 line
Plus, sthcx doesn't exist on all PPC chips.
Which ones are lacking it? Do all have at least a simple 16-bit store?
Everything implements a simple 16-bit store, just not everything implements the store conditional of 16-bit data.
Ok, so then the last version I posted should work on those machines.
Quoted 6 lines · Peter Zijlstra
Quoted 2 lines · Peter Zijlstra
Anyway, you can do a version with lwarx/stwcx if you're looking get rid of lharx.
the below seems to compile into relatively ok asm. It can be done better if you write the entire thing by hand though.
[...]
Quoted 11 lines
static inline unsigned int
xadd(unsigned int *v, unsigned int i){ int t, ret; __asm__ __volatile__ ("1: lwarx %0, 0, %4\n"
" mr %1, %0\n"
" add %0, %3, %0\n"
" stwcx. %0, %0, %4\n"
" bne- 1b\n"
Quoted 7 lines
: "=&r" (t), "=&r" (ret), "+m" (*v) : "r" (i), "r" (v) : "cc"); return ret; }
I don't like this xadd thing -- it's so x86 ;) x86 has its LOCK prefix, ppc has ll/sc. That should be reflected somehow IMHO.
Maybe if xadd became mandatory for some kernel library.
Quoted 14 lines
void
ticket_unlock(tickets_t *lock){ ticket_t tail = lock->tail + 1; /* * The store is save against the xadd for it will make the ll/sc fail * and try again. Aside from that PowerISA guarantees single-copy * atomicy for half-word writes. * * And since only the lock owner will ever write the tail, we're good. */ smp_store_release(&lock->tail, tail); }
Yeah, let's try that on top of v2 (just posted). First, I want to see v2 work as nicely as v1 -- compiling a debug kernel takes a while...
Torsten
Peter Zijlstra
maintainerQuoted 14 lines · Torsten Duwe
Quoted 14 lines
static inline unsigned int
xadd(unsigned int *v, unsigned int i){ int t, ret; __asm__ __volatile__ ("1: lwarx %0, 0, %4\n"
" mr %1, %0\n"
" add %0, %3, %0\n"
" stwcx. %0, %0, %4\n"
" bne- 1b\n": "=&r" (t), "=&r" (ret), "+m" (*v) : "r" (i), "r" (v) : "cc");
Quoted 6 lines
Quoted 3 lines
return ret; }I don't like this xadd thing -- it's so x86 ;) x86 has its LOCK prefix, ppc has ll/sc. That should be reflected somehow IMHO.
Its the operational semantics I care about; this version is actually nicer in that it doesn't actually imply all sorts of barriers :-)
Quoted 1 line
Maybe if xadd became mandatory for some kernel library.
call it fetch_add() its not an uncommon operation and many people understand the semantics.
But you can simply include the asm bits in ticket_lock() and be done with it. In that case you can also replace the add with an addi which might be a little more efficient.
Quoted 14 lines
Quoted 13 lines
void
ticket_unlock(tickets_t *lock){ ticket_t tail = lock->tail + 1; /* * The store is save against the xadd for it will make the ll/sc fail * and try again. Aside from that PowerISA guarantees single-copy * atomicy for half-word writes. * * And since only the lock owner will ever write the tail, we're good. */ smp_store_release(&lock->tail, tail); }
Quoted 3 lines
Yeah, let's try that on top of v2 (just posted). First, I want to see v2 work as nicely as v1 -- compiling a debug kernel takes a while...
Use a faster machine... it can be done < 1 minute :-)
Quoted 7 lines · Tom Musta
My read is consistent with Torsten's ... this looks like a bad idea.
Look at the RTL for sthcx. on page 692 (Power ISA V2.06) and you will see this:
if RESERVE then
ifRESERVE_LENGTH= 2 then
Quoted 7 lines
...else
undefined_case<- 1
else
...A legal implementation might never perform the store.
This is an area where we definitely want to check with the implementors and if the implementations happen to do what we want (they likely do), get the architecture changed for future chips and use it anyway.
There's a a *significant* benefit in avoiding an atomic operation in the unlock case .
The reservation mechanism being based on a granule that is generally a cache line, I doubt implementations will ever check the actual access size, but we need to double check.
Cheers,
Ben.
Quoted 7 lines · Torsten Duwe
Quoted 4 lines
Quoted 4 lines
Quoted 4 lines
Can you pair lwarx with sthcx ? I couldn't immediately find the answer in the PowerISA doc. If so I think you can do better by being able to atomically load both tickets but only storing the head without affecting the tail.
Can I simply write the half word, without a reservation, or will the HW caches mess up the other half? Will it ruin the cache coherency on some (sub)architectures?
Yes, you can, I *think*
Quoted 3 lines
Quoted 1 line
Plus, sthcx doesn't exist on all PPC chips.
Which ones are lacking it? Do all have at least a simple 16-bit store?
half word atomics (and byte atomics) are new, they've been added in architecture 2.06 I believe so it's fairly recent, but it's still worthwhile to investigate a way to avoid atomics on unlock on recent processors (we can use instruction patching if necessary based on CPU features) because there's definitely a significant cost in doing a larx/stcx. sequence on powerpc, way higher than our current unlock path of barrier + store.
Cheers,
Ben.
Quoted 11 lines · Kumar Gala
Quoted 9 lines · Torsten Duwe
Quoted 7 lines · Scott Wood
Quoted 6 lines · Torsten Duwe
Quoted 4 lines · Peter Zijlstra
Can you pair lwarx with sthcx ? I couldn't immediately find the answer in the PowerISA doc. If so I think you can do better by being able to atomically load both tickets but only storing the head without affecting the tail.
Quoted 4 lines
Quoted 2 lines
Can I simply write the half word, without a reservation, or will the HW caches mess up the other half? Will it ruin the cache coherency on some (sub)architectures?
The coherency should be fine, I just can’t remember if you’ll lose the reservation by doing this.
Yes you do.
Quoted 5 lines
Quoted 3 lines
Quoted 1 line
Plus, sthcx doesn't exist on all PPC chips.
Which ones are lacking it? Do all have at least a simple 16-bit store?
Everything implements a simple 16-bit store, just not everything implements the store conditional of 16-bit data.
Ben.
Quoted 5 lines
- k--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/