powerpc ticket locks
Subsystems (2)
PATCH v2 1/1 powerpc ticket locks
Ticket locks for ppc, version 2. Changes since v1:
* The atomically exchanged entity is always 32 bits.
* asm inline string variations thus removed.
* Carry the additional holder hint only #if defined(CONFIG_PPC_SPLPAR)
--
arch/powerpc/include/asm/spinlock_types.h | 29 +++++ arch/powerpc/include/asm/spinlock.h | 146 +++++++++++++++++++++++------- arch/powerpc/lib/locks.c | 6 - 3 files changed, 144 insertions(+), 37 deletions(-)
arch/powerpc/include/asm/spinlock_types.h +26 -3
@@ -5,11 +5,34 @@# error "please don't include this file directly"#endif +typedef u16 __ticket_t ; +typedef u32 __ticketpair_t ; + +#define TICKET_LOCK_INC ((__ticket_t)1) + +#define TICKET_SHIFT (sizeof(__ticket_t) * 8) +typedef struct { -volatile unsigned int slock; -}arch_spinlock_t ; +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_PPC_SPLPAR ) +u32 holder; +#endif +}arch_spinlock_t __aligned(4) ; -#define __ARCH_SPIN_LOCK_UNLOCKED { 0 } +#if defined(CONFIG_PPC_SPLPAR ) +#define __ARCH_SPIN_LOCK_UNLOCKED { { 0 }, 0 } +#else +#define __ARCH_SPIN_LOCK_UNLOCKED { { 0 } } +#endif typedef struct { volatile signed int lock;
arch/powerpc/include/asm/spinlock.h +115 -31
215 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);
Peter Zijlstra
maintainerQuoted 8 lines · Torsten Duwe
arch/powerpc/include/asm/spinlock.h +6
-0+static __always_inline void arch_spin_lock(arch_spinlock_t *lock) { + registerstruct __raw_tickets old, tmp, + inc = { .tail =TICKET_LOCK_INC }; +CLEAR_IO_SYNC ; + __asm__ __volatile__( +"1: lwarx %0,0,%4 # arch_spin_lock\n"
arch/powerpc/include/asm/spinlock.h extern void __rw_yield(arch_rwlock_t *lock); · line 179
Quoted 10 lines
arch/powerpc/include/asm/spinlock.h +10
-0+" 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)) + goto out;
I would have expected an lwsync someplace hereabouts.
Quoted 30 lines
arch/powerpc/include/asm/spinlock.h +16
-0+for (;;) { +unsigned count =100 ; +do { +if (ACCESS_ONCE (lock->tickets.head) == old.tail) + goto out;HMT_low ();if (SHARED_PROCESSOR )__spin_yield (lock); + }while (--count);HMT_medium (); } +out: +#if defined(CONFIG_PPC_SPLPAR ) + lock->holder =LOCK_TOKEN ; +#endif +barrier ();/* make sure nothing creeps before the lock is taken */ } static inline@@ -147,10 +220,21 @@ 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_PPC_SPLPAR ) + lock->holder =0 ; +#endif
arch/powerpc/include/asm/spinlock.h void arch_spin_lock_flags(arch_spinlock_t *lock, unsigned long flags) · line 237
Quoted 10 lines
arch/powerpc/include/asm/spinlock.h +7
-0+do { + old.tickets =ACCESS_ONCE (lock->tickets); + new.tickets.head = old.tickets.head +TICKET_LOCK_INC ; + new.tickets.tail = old.tickets.tail; + }while (unlikely (__arch_spin_cmpxchg_eq (lock, + old.head_tail, + new.head_tail)));SYNC_IO ; __asm__ __volatile__("# arch_spin_unlock\n\t" PPC_RELEASE_BARRIER : : :"memory" );
Doens't your cmpxchg_eq not already imply a lwsync?
arch/powerpc/include/asm/spinlock.h void arch_spin_lock_flags(arch_spinlock_t *lock, unsigned long flags) · line 238
Quoted 2 lines
arch/powerpc/include/asm/spinlock.h +0
-1- lock->slock =0 ; }
I'm still failing to see why you need an ll/sc pair for unlock.
Quoted 13 lines · Peter Zijlstra
Quoted 12 lines · Torsten Duwe
arch/powerpc/include/asm/spinlock.h +10
-0+static __always_inline void arch_spin_lock(arch_spinlock_t *lock) { + registerstruct __raw_tickets old, tmp, + inc = { .tail =TICKET_LOCK_INC }; +CLEAR_IO_SYNC ; + __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"
Quoted 8 lines
arch/powerpc/include/asm/spinlock.h extern void __rw_yield(arch_rwlock_t *lock); · line 179
Quoted 6 lines
arch/powerpc/include/asm/spinlock.h +6
-0+ : "=&r" (old), "=&r" (tmp), "+m" (lock->tickets) + : "r" (inc), "r" (&lock->tickets) + : "cc"); + +if (likely (old.head == old.tail)) + goto out;I would have expected an lwsync someplace hereabouts.
Let me reconsider this. The v1 code worked on an 8 core, maybe I didn't beat it enough.
Quoted 11 lines
Quoted 11 lines
static inline void
arch_spin_unlock(arch_spinlock_t *lock){arch/powerpc/include/asm/spinlock.h +9
-0+arch_spinlock_t old, new; + +#if defined(CONFIG_PPC_SPLPAR ) + lock->holder =0 ; +#endif + do { + old.tickets = ACCESS_ONCE(lock->tickets); + new.tickets.head = old.tickets.head + TICKET_LOCK_INC; + new.tickets.tail = old.tickets.tail;
Quoted 8 lines
arch/powerpc/include/asm/spinlock.h void arch_spin_lock_flags(arch_spinlock_t *lock, unsigned long flags) · line 237
Quoted 6 lines
arch/powerpc/include/asm/spinlock.h +3
-0+ }while (unlikely (__arch_spin_cmpxchg_eq (lock, + old.head_tail, + new.head_tail)));SYNC_IO ; __asm__ __volatile__("# arch_spin_unlock\n\t" PPC_RELEASE_BARRIER : : :"memory" );Doens't your
cmpxchg_eqnot already imply a lwsync?
Right.
Quoted 4 lines
arch/powerpc/include/asm/spinlock.h void arch_spin_lock_flags(arch_spinlock_t *lock, unsigned long flags) · line 238
Quoted 2 lines
arch/powerpc/include/asm/spinlock.h +0
-1- lock->slock =0 ; }I'm still failing to see why you need an ll/sc pair for unlock.
Like so:
static inline void arch_spin_unlock(arch_spinlock_t *lock)
{
arch_spinlock_t tmp;#if defined(CONFIG_PPC_SPLPAR)
lock->holder = 0;
#endif
tmp.tickets = ACCESS_ONCE(lock->tickets);
tmp.tickets.head += TICKET_LOCK_INC;
lock->tickets.head = tmp.tickets.head;
SYNC_IO;
__asm__ __volatile__("# arch_spin_unlock\n\t"
PPC_RELEASE_BARRIER: : :"memory");
}?
I'll wrap it all up next week. I only wanted to post an updated v2 with the agreed-upon changes for BenH.
Thanks so far!
Torsten
Quoted 7 lines · Torsten Duwe
typedef struct {
arch/powerpc/include/asm/spinlock_types.h +4
-2-volatile unsigned int slock; -} arch_spinlock_t; +union { +__ticketpair_t head_tail; +struct __raw_tickets { +#ifdef __BIG_ENDIAN__/* The "tail" part should be in the MSBs */
arch/powerpc/include/asm/spinlock_types.h line 29
Quoted 10 lines
arch/powerpc/include/asm/spinlock_types.h +10
-0+__ticket_t tail, head; +#else +__ticket_t head, tail; +#endif + } tickets; + }; +#if defined(CONFIG_PPC_SPLPAR ) +u32 holder; +#endif +} arch_spinlock_t__aligned(4) ;
That's still broken with lockref (which we just merged).
We must have the arch_spinlock_t and the ref in the same 64-bit word otherwise it will break.
We can make it work in theory since the holder doesn't have to be accessed atomically, but the practicals are a complete mess ... lockref would essentially have to re-implement the holder handling of the spinlocks and use lower level ticket stuff.
Unless you can find a sneaky trick ... :-(
Ben.
Quoted 21 lines · Benjamin Herrenschmidt
Quoted 7 lines · Torsten Duwe
typedef struct {
arch/powerpc/include/asm/spinlock_types.h +4
-2-volatile unsigned int slock; -} arch_spinlock_t; +union { +__ticketpair_t head_tail; +struct __raw_tickets { +#ifdef __BIG_ENDIAN__/* The "tail" part should be in the MSBs */ arch/powerpc/include/asm/spinlock_types.h line 29
Quoted 10 lines
arch/powerpc/include/asm/spinlock_types.h +10
-0+__ticket_t tail, head; +#else +__ticket_t head, tail; +#endif + } tickets; + }; +#if defined(CONFIG_PPC_SPLPAR ) +u32 holder; +#endif +} arch_spinlock_t__aligned(4) ;That's still broken with lockref (which we just merged).
Quoted 2 lines
We must have the
arch_spinlock_tand the ref in the same 64-bit word otherwise it will break.
Well, as far as I can see you'll just not be able to USE_CMPXCHG_LOCKREF -- with the appropriate performance hit -- the code just falls back into lock&ref on pSeries.
What again was the intention of directed yield in the first place...?
Quoted 6 lines
We can make it work in theory since the holder doesn't have to be accessed atomically, but the practicals are a complete mess ... lockref would essentially have to re-implement the holder handling of the spinlocks and use lower level ticket stuff.
Unless you can find a sneaky trick ... :-(
What if I squeeze the bits a little?
4k vCPUs, and 256 physical, as a limit to stay within 32 bits? At the cost that unlock may become an ll/sc operation again. I could think about a trick against that.
But alas, hw_cpu_id is 16 bit, which makes a lookup table neccessary :-/
Doing another round of yields for lockrefs now doesn't sound so bad any more.
Opinions, anyone?
Torsten
Peter Zijlstra
maintainerQuoted 1 line · Torsten Duwe
Opinions, anyone?
Since the holder thing is a performance thing, not a correctness thing; one thing you could do is something like:
static const int OWNER_HASH_SIZE = CONFIG_NR_CPUS * 4; static const int OWNER_HASH_BITS = ilog2(OWNER_HASH_SIZE);
u16 lock_owner_array[OWNER_HASH_SIZE] = { 0, };
void set_owner(struct arch_spinlock_t *lock, int owner)
{
int hash = hash_ptr(lock, OWNER_HASH_BITS);
lock_owner_array[hash] = owner;
}void yield_to_owner(struct arch_spinlock_t *lock)
{
int hash = hash_ptr(lock, OWNER_HASH_BITS);
int owner = lock_owner_array[hash];
yield_to_cpu(owner);
}And call set_owner() after the ticket lock is acquired, and don't bother clearing it again; a new acquire will overwrite, a collision we have to live with.
It should on average get you the right yield and does away with having to track the owner field in place.
It does however get you an extra cacheline miss on acquire :/
One could consider patching it out when you know your kernel is not running on an overloaded partition.
(Linus, Al, a question for you down there about lockref "ref" size)
Quoted 8 lines · Torsten Duwe
What if I squeeze the bits a little?
4k vCPUs, and 256 physical, as a limit to stay within 32 bits? At the cost that unlock may become an ll/sc operation again. I could think about a trick against that.
But alas,hw_cpu_idis 16 bit, which makes a lookup table neccessary :-/Doing another round of yields for lockrefs now doesn't sound so bad any more.
So, the ticketpair has to be 16:16 so we can avoid the atomic on unlock
That leaves us with 32 bits to put the ref and the owner. The question is how big the ref really has to be and can we have a reasonable failure mode if it overflows ?
If we limit ourselves to, for example, 16-bit for the ref in lockref, then we can have the second 32-bit split between the owner and the ref.
If we limit ourselves to 4k CPUs, then we get 4 more bits of ref ...
So the question is, is it reasonable to have the ref smaller than 32-bit...
Cheers,
Ben.
Quoted 11 lines · Benjamin Herrenschmidt
That leaves us with 32 bits to put the ref and the owner. The question is how big the ref really has to be and can we have a reasonable failure mode if it overflows ?
If we limit ourselves to, for example, 16-bit for the ref in lockref, then we can have the second 32-bit split between the owner and the ref.
If we limit ourselves to 4k CPUs, then we get 4 more bits of ref ...
So the question is, is it reasonable to have the ref smaller than 32-bit...
Every time you open a file, you bump dentry refcount. Something like libc or ld.so will be opened on just about every execve(), so I'd say that 16 bits is far too low. If nothing else, 32 bits might be too low on 64bit boxen...
Quoted 7 lines · Al Viro
Quoted 2 lines
So the question is, is it reasonable to have the ref smaller than 32-bit...
Every time you open a file, you bump dentry refcount. Something like libc or ld.so will be opened on just about every
execve(), so I'd say that 16 bits is far too low. If nothing else, 32 bits might be too low on 64bit boxen...
So back to square 1 ... we can't implement together lockref, ticket locks, and our lock confer mechanism within 64-bit.
I see two options at this stage. Both require a custom implementation of lockref for powerpc, so some ifdef's such that we can replace the generic implementation completely.
- We can use a small ref, and when it's too big, overflow into a larger
one, falling back to the "old style" lock + ref (an overflow bit or a compare with ffff)
- We can have lockref "build" it's own lock out of the ticketpair and
ref, keeping the owner in a separate word. The owner doesn't strictly need to be atomic.
Both are gross though :(
Anybody has a better idea ?
Ben.
Quoted 7 lines · Torsten Duwe
Ticket locks for ppc, version 2. Changes since v1:
* The atomically exchanged entity is always 32 bits.
* asm inline string variations thus removed.
* Carry the additional holder hint only #ifdefined(CONFIG_PPC_SPLPAR)Signed-off-by Torsten Duwe <[email protected]>--
[...]
Quoted 14 lines
arch/powerpc/include/asm/spinlock.h +9
-3+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"
arch/powerpc/include/asm/spinlock.h extern void __rw_yield(arch_rwlock_t *lock); · line 182
Quoted 10 lines
arch/powerpc/include/asm/spinlock.h +10
-0+" bne- 1b" + : "=&r" (old), "=&r" (tmp), "+m" (lock->tickets) + : "r" (inc), "r" (&lock->tickets) + : "cc"); + +if (likely (old.head == old.tail)) + goto out; + +for (;;) { +unsigned count =100 ;
I am sure you wanted to tune the total loops to typical lock holding time ...
Quoted 21 lines · Benjamin Herrenschmidt
Quoted 7 lines · Torsten Duwe
typedef struct {
arch/powerpc/include/asm/spinlock_types.h +4
-2-volatile unsigned int slock; -} arch_spinlock_t; +union { +__ticketpair_t head_tail; +struct __raw_tickets { +#ifdef __BIG_ENDIAN__/* The "tail" part should be in the MSBs */ arch/powerpc/include/asm/spinlock_types.h line 29
Quoted 10 lines
arch/powerpc/include/asm/spinlock_types.h +10
-0+__ticket_t tail, head; +#else +__ticket_t head, tail; +#endif + } tickets; + }; +#if defined(CONFIG_PPC_SPLPAR ) +u32 holder; +#endif +} arch_spinlock_t__aligned(4) ;That's still broken with lockref (which we just merged).
Quoted 8 lines
We must have the
arch_spinlock_tand the ref in the same 64-bit word otherwise it will break.We can make it work in theory since the holder doesn't have to be accessed atomically, but the practicals are a complete mess ... lockref would essentially have to re-implement the holder handling of the spinlocks and use lower level ticket stuff.
Probably very basic and stupid question from me.
How much important to have holder information for PPC? From my previous experiment
on x86, it was lock-waiter preemption which is problematic rather than lock-holder preemption.
Quoted 4 lines · Raghavendra KT
How much important to have holder information for PPC? From my previous experiment
on x86, it was lock-waiter preemption which is problematic rather than lock-holder preemption.
It's something very special to IBM pSeries: the hypervisor can assign fractions of physical CPUs to guests. Sometimes a guest with 4 quarter CPUs will be faster than 1 monoprocessor. (correct me if I'm wrong).
The directed yield resolves the silly situation when holder and waiter reside on the same physical CPU, as I understand it.
x86 has nothing comparable.
Torsten
Quoted 6 lines · Torsten Duwe
Quoted 4 lines · Raghavendra KT
How much important to have holder information for PPC? From my previous experiment
on x86, it was lock-waiter preemption which is problematic rather than lock-holder preemption.
Quoted 8 lines
It's something very special to IBM pSeries: the hypervisor can assign fractions of physical CPUs to guests. Sometimes a guest with 4 quarter CPUs will be faster than 1 monoprocessor. (correct me if I'm wrong).
The directed yield resolves the silly situation when holder and waiter reside on the same physical CPU, as I understand it.
x86 has nothing comparable.
How is this different from the very ordinary case of an SMP KVM guest whose vcpus are not bound to host cpus, and thus you could have multiple vcpus running on the same host cpu?
-Scott
Quoted 4 lines · Scott Wood
Quoted 4 lines
It's something very special to IBM pSeries: the hypervisor can assign fractions of physical CPUs to guests. Sometimes a guest with 4 quarter CPUs will be faster than 1 monoprocessor. (correct me if I'm wrong).
Quoted 8 lines
Quoted 4 lines
The directed yield resolves the silly situation when holder and waiter reside on the same physical CPU, as I understand it.
x86 has nothing comparable.
How is this different from the very ordinary case of an SMP KVM guest whose vcpus are not bound to host cpus, and thus you could have multiple vcpus running on the same host cpu?
It's not really ... though I can see drawbacks with the scheme as well and I think in KVM we should be careful to only confer if the owner vcpu last scheduled on the same physical cpu where the waiter is, other wise, there's too much chances of us bouncing things around the machine for minor contention cases.
Paul, what's your policy today ?
Cheers,
Ben.