PV ticket locks without expanding spinlock
Subsystems (9)
cover PV ticket locks without expanding spinlock
From: Jeremy Fitzhardinge <[email protected]>
Hi all,
This is a revised version of the pvticket lock series.
The early part of the series is mostly unchanged: it converts the bulk of the ticket lock code into C and makes the "small" and "large" ticket code common. The only changes are the incorporation of various review comments.
The latter part of the series converts from pv spinlocks to pv ticket locks (ie, using the ticket lock fastpath as-is, but adding pv ops for the ticketlock slowpaths).
The significant difference here is that rather than adding a new ticket_t-sized element to arch_spinlock_t - effectively doubling the size - I steal the LSB of the tickets themselves to store a bit. This allows the structure to remain the same size, but at the cost of halving the max number of CPUs (127 for a 8-bit ticket, and a hard max of 32767 overall).
The extra bit (well, two, but one is unused) in indicates whether the lock has gone into "slowpath state", which means one of its lockers has entered its slowpath and has blocked in the hypervisor. This means the current lock-holder needs to make sure it gets kicked out of the hypervisor on unlock.
The spinlock remains in slowpath state until the last unlock happens (ie there are no more queued lockers).
This code survives for a while with moderate testing, (make -j 100 on 8 VCPUs on a 4 PCPU system), but locks up after about 20 iterations, so there's still some race/deadlock in there (probably something misordered), but I think the basic approach is sound.
Thanks,
J
Jeremy Fitzhardinge (14):
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/spinlocks: replace pv spinlocks with pv ticketlocks x86/ticketlock: collapse a layer of functions xen/pvticketlock: Xen implementation for PV ticket locks x86/pvticketlock: use callee-save for lock_spinning x86/ticketlock: don't inline _spin_unlock when using paravirt
spinlocks
x86/ticketlocks: when paravirtualizing ticket locks, increment by 2 x86/ticketlock: add slowpath logic
x86/ticketlocks: tidy up __ticket_unlock_kick()
arch/x86/Kconfig | 3 + arch/x86/include/asm/paravirt.h | 30 +--- arch/x86/include/asm/paravirt_types.h | 8 +- arch/x86/include/asm/spinlock.h | 236 +++++++++++++--------------- arch/x86/include/asm/spinlock_types.h | 32 ++++- arch/x86/kernel/paravirt-spinlocks.c | 52 +++++-- arch/x86/xen/spinlock.c | 281 +++++---------------------------- kernel/Kconfig.locks | 2 +- 8 files changed, 231 insertions(+), 413 deletions(-)
Signature · 1 line
1.7.2.3
PATCH 1/14 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.2.3
PATCH 1/14 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.2.3
PATCH 2/14 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.2.3
PATCH 2/14 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.2.3
PATCH 3/14 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.2.3
PATCH 3/14 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.2.3
PATCH 4/14 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.2.3
PATCH 4/14 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.2.3
PATCH 5/14 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.2.3
PATCH 5/14 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.2.3
PATCH 6/14 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.2.3
PATCH 6/14 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.2.3
PATCH 7/14 x86/spinlocks: replace pv spinlocks with pv ticketlocks
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
Rather than outright replacing the entire spinlock implementation in order to paravirtualize it, keep the ticket lock implementation but add a couple of pvops hooks on the slow patch (long spin on lock, unlocking a contended lock).
Ticket locks have a number of nice properties, but they also have some surprising behaviours in virtual environments. They enforce a strict FIFO ordering on cpus trying to take a lock; however, if the hypervisor scheduler does not schedule the cpus in the correct order, the system can waste a huge amount of time spinning until the next cpu can take the lock.
(See Thomas Friebel's talk "Prevent Guests from Spinning Around"
http://www.xen.org/files/xensummitboston08/LHP.pdf for more details.)
To address this, we add two hooks:
- __ticket_spin_lock which is called after the cpu has been spinning on the lock for a significant number of iterations but has failed to take the lock (presumably because the cpu holding the lock has been descheduled). The lock_spinning pvop is expected to block the cpu until it has been kicked by the current lock holder.
- __ticket_spin_unlock, which on releasing a contended lock (there are more cpus with tail tickets), it looks to see if the next cpu is blocked and wakes it if so.
When compiled with CONFIG_PARAVIRT_SPINLOCKS disabled, a set of stub functions causes all the extra code to go away.
--- arch/x86/include/asm/paravirt.h | 30 +++------------------- arch/x86/include/asm/paravirt_types.h | 8 +---- arch/x86/include/asm/spinlock.h | 44 +++++++++++++++++++++++++++------ arch/x86/kernel/paravirt-spinlocks.c | 15 +--------- arch/x86/xen/spinlock.c | 7 ++++- 5 files changed, 50 insertions(+), 54 deletions(-)
arch/x86/include/asm/paravirt.h +4 -26
@@ -717,36 +717,14 @@ static inline void __set_fixmap(unsigned /* enum fixed_addresses */ idx,#if defined(CONFIG_SMP ) && defined(CONFIG_PARAVIRT_SPINLOCKS ) -static inline int arch_spin_is_locked (struct arch_spinlock *lock) +static inline void __ticket_lock_spinning (struct arch_spinlock *lock,unsigned ticket) { -return PVOP_CALL1 (int, pv_lock_ops.spin_is_locked, lock); +PVOP_VCALL2 (pv_lock_ops.lock_spinning, lock, ticket); } -static inline int arch_spin_is_contended (struct arch_spinlock *lock) +static inline void ____ticket_unlock_kick (struct arch_spinlock *lock,unsigned ticket) { -return PVOP_CALL1 (int, pv_lock_ops.spin_is_contended, lock); -} -#define arch_spin_is_contended arch_spin_is_contended - -static __always_inline void arch_spin_lock(struct arch_spinlock *lock) -{ -PVOP_VCALL1 (pv_lock_ops.spin_lock, lock); -} - -static __always_inline void arch_spin_lock_flags(struct arch_spinlock *lock, -unsigned long flags) -{ -PVOP_VCALL2 (pv_lock_ops.spin_lock_flags, lock, flags); -} - -static __always_inline int arch_spin_trylock(struct arch_spinlock *lock) -{ -return PVOP_CALL1 (int, pv_lock_ops.spin_trylock, lock); -} - -static __always_inline void arch_spin_unlock(struct arch_spinlock *lock) -{ -PVOP_VCALL1 (pv_lock_ops.spin_unlock, lock); +PVOP_VCALL2 (pv_lock_ops.unlock_kick, lock, ticket); }#endif
arch/x86/include/asm/paravirt_types.h +2 -6
@@ -315,12 +315,8 @@ struct pv_mmu_ops {struct arch_spinlock ;struct pv_lock_ops { -int (*spin_is_locked)(struct arch_spinlock *lock); -int (*spin_is_contended)(struct arch_spinlock *lock); -void (*spin_lock)(struct arch_spinlock *lock); -void (*spin_lock_flags)(struct arch_spinlock *lock,unsigned long flags); -int (*spin_trylock)(struct arch_spinlock *lock); -void (*spin_unlock)(struct arch_spinlock *lock); +void (*lock_spinning)(struct arch_spinlock *lock,unsigned ticket); +void (*unlock_kick)(struct arch_spinlock *lock,unsigned ticket); };/* This contains all the paravirt structures: we get a convenient
arch/x86/include/asm/spinlock.h +36 -8
81 lines not on this page · raw message
arch/x86/kernel/paravirt-spinlocks.c +2 -13
@@ -7,21 +7,10 @@#include <asm/paravirt.h> -static inline void -default_spin_lock_flags (arch_spinlock_t *lock,unsigned long flags) -{ -arch_spin_lock (lock); -} -struct pv_lock_ops pv_lock_ops = { #ifdef CONFIG_SMP - .spin_is_locked = __ticket_spin_is_locked, - .spin_is_contended = __ticket_spin_is_contended, - - .spin_lock = __ticket_spin_lock, - .spin_lock_flags = default_spin_lock_flags, - .spin_trylock = __ticket_spin_trylock, - .spin_unlock = __ticket_spin_unlock, + .lock_spinning = paravirt_nop, + .unlock_kick = paravirt_nop, #endif };EXPORT_SYMBOL (pv_lock_ops);
arch/x86/xen/spinlock.c +6 -1
@@ -121,6 +121,9 @@ struct xen_spinlock {unsigned short spinners;/* count of waiting cpus */ }; +static DEFINE_PER_CPU(int, lock_kicker_irq) = -1; + +#if 0 static int xen_spin_is_locked (struct arch_spinlock *lock) {struct xen_spinlock *xl = (struct xen_spinlock *)lock;
@@ -148,7 +151,6 @@ static int xen_spin_trylock(struct arch_spinlock *lock)return old ==0 ; } -static DEFINE_PER_CPU(int, lock_kicker_irq) = -1; static DEFINE_PER_CPU(struct xen_spinlock *, lock_spinners);/*
@@ -338,6 +340,7 @@ static void xen_spin_unlock(struct arch_spinlock *lock)if (unlikely (xl->spinners)) xen_spin_unlock_slow(xl); } +#endif static irqreturn_t dummy_handler (int irq,void *dev_id) {
@@ -373,12 +376,14 @@ void xen_uninit_lock_cpu(int cpu)void __init xen_init_spinlocks (void ) { +#if 0 pv_lock_ops.spin_is_locked = xen_spin_is_locked; pv_lock_ops.spin_is_contended = xen_spin_is_contended; pv_lock_ops.spin_lock = xen_spin_lock; pv_lock_ops.spin_lock_flags = xen_spin_lock_flags; pv_lock_ops.spin_trylock = xen_spin_trylock; pv_lock_ops.spin_unlock = xen_spin_unlock; +#endif }#ifdef CONFIG_XEN_DEBUG_FS
Signature · 1 line
1.7.2.3
PATCH 7/14 x86/spinlocks: replace pv spinlocks with pv ticketlocks
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
Rather than outright replacing the entire spinlock implementation in order to paravirtualize it, keep the ticket lock implementation but add a couple of pvops hooks on the slow patch (long spin on lock, unlocking a contended lock).
Ticket locks have a number of nice properties, but they also have some surprising behaviours in virtual environments. They enforce a strict FIFO ordering on cpus trying to take a lock; however, if the hypervisor scheduler does not schedule the cpus in the correct order, the system can waste a huge amount of time spinning until the next cpu can take the lock.
(See Thomas Friebel's talk "Prevent Guests from Spinning Around"
http://www.xen.org/files/xensummitboston08/LHP.pdf for more details.)
To address this, we add two hooks:
- __ticket_spin_lock which is called after the cpu has been spinning on the lock for a significant number of iterations but has failed to take the lock (presumably because the cpu holding the lock has been descheduled). The lock_spinning pvop is expected to block the cpu until it has been kicked by the current lock holder.
- __ticket_spin_unlock, which on releasing a contended lock (there are more cpus with tail tickets), it looks to see if the next cpu is blocked and wakes it if so.
When compiled with CONFIG_PARAVIRT_SPINLOCKS disabled, a set of stub functions causes all the extra code to go away.
--- arch/x86/include/asm/paravirt.h | 30 +++------------------- arch/x86/include/asm/paravirt_types.h | 8 +---- arch/x86/include/asm/spinlock.h | 44 +++++++++++++++++++++++++++------ arch/x86/kernel/paravirt-spinlocks.c | 15 +--------- arch/x86/xen/spinlock.c | 7 ++++- 5 files changed, 50 insertions(+), 54 deletions(-)
arch/x86/include/asm/paravirt.h +4 -26
@@ -717,36 +717,14 @@ static inline void __set_fixmap(unsigned /* enum fixed_addresses */ idx,#if defined(CONFIG_SMP ) && defined(CONFIG_PARAVIRT_SPINLOCKS ) -static inline int arch_spin_is_locked (struct arch_spinlock *lock) +static inline void __ticket_lock_spinning (struct arch_spinlock *lock,unsigned ticket) { -return PVOP_CALL1 (int, pv_lock_ops.spin_is_locked, lock); +PVOP_VCALL2 (pv_lock_ops.lock_spinning, lock, ticket); } -static inline int arch_spin_is_contended (struct arch_spinlock *lock) +static inline void ____ticket_unlock_kick (struct arch_spinlock *lock,unsigned ticket) { -return PVOP_CALL1 (int, pv_lock_ops.spin_is_contended, lock); -} -#define arch_spin_is_contended arch_spin_is_contended - -static __always_inline void arch_spin_lock(struct arch_spinlock *lock) -{ -PVOP_VCALL1 (pv_lock_ops.spin_lock, lock); -} - -static __always_inline void arch_spin_lock_flags(struct arch_spinlock *lock, -unsigned long flags) -{ -PVOP_VCALL2 (pv_lock_ops.spin_lock_flags, lock, flags); -} - -static __always_inline int arch_spin_trylock(struct arch_spinlock *lock) -{ -return PVOP_CALL1 (int, pv_lock_ops.spin_trylock, lock); -} - -static __always_inline void arch_spin_unlock(struct arch_spinlock *lock) -{ -PVOP_VCALL1 (pv_lock_ops.spin_unlock, lock); +PVOP_VCALL2 (pv_lock_ops.unlock_kick, lock, ticket); }#endif
arch/x86/include/asm/paravirt_types.h +2 -6
@@ -315,12 +315,8 @@ struct pv_mmu_ops {struct arch_spinlock ;struct pv_lock_ops { -int (*spin_is_locked)(struct arch_spinlock *lock); -int (*spin_is_contended)(struct arch_spinlock *lock); -void (*spin_lock)(struct arch_spinlock *lock); -void (*spin_lock_flags)(struct arch_spinlock *lock,unsigned long flags); -int (*spin_trylock)(struct arch_spinlock *lock); -void (*spin_unlock)(struct arch_spinlock *lock); +void (*lock_spinning)(struct arch_spinlock *lock,unsigned ticket); +void (*unlock_kick)(struct arch_spinlock *lock,unsigned ticket); };/* This contains all the paravirt structures: we get a convenient
arch/x86/include/asm/spinlock.h +36 -8
81 lines not on this page · raw message
arch/x86/kernel/paravirt-spinlocks.c +2 -13
@@ -7,21 +7,10 @@#include <asm/paravirt.h> -static inline void -default_spin_lock_flags (arch_spinlock_t *lock,unsigned long flags) -{ -arch_spin_lock (lock); -} -struct pv_lock_ops pv_lock_ops = { #ifdef CONFIG_SMP - .spin_is_locked = __ticket_spin_is_locked, - .spin_is_contended = __ticket_spin_is_contended, - - .spin_lock = __ticket_spin_lock, - .spin_lock_flags = default_spin_lock_flags, - .spin_trylock = __ticket_spin_trylock, - .spin_unlock = __ticket_spin_unlock, + .lock_spinning = paravirt_nop, + .unlock_kick = paravirt_nop, #endif };EXPORT_SYMBOL (pv_lock_ops);
arch/x86/xen/spinlock.c +6 -1
@@ -121,6 +121,9 @@ struct xen_spinlock {unsigned short spinners;/* count of waiting cpus */ }; +static DEFINE_PER_CPU(int, lock_kicker_irq) = -1; + +#if 0 static int xen_spin_is_locked (struct arch_spinlock *lock) {struct xen_spinlock *xl = (struct xen_spinlock *)lock;
@@ -148,7 +151,6 @@ static int xen_spin_trylock(struct arch_spinlock *lock)return old ==0 ; } -static DEFINE_PER_CPU(int, lock_kicker_irq) = -1; static DEFINE_PER_CPU(struct xen_spinlock *, lock_spinners);/*
@@ -338,6 +340,7 @@ static void xen_spin_unlock(struct arch_spinlock *lock)if (unlikely (xl->spinners)) xen_spin_unlock_slow(xl); } +#endif static irqreturn_t dummy_handler (int irq,void *dev_id) {
@@ -373,12 +376,14 @@ void xen_uninit_lock_cpu(int cpu)void __init xen_init_spinlocks (void ) { +#if 0 pv_lock_ops.spin_is_locked = xen_spin_is_locked; pv_lock_ops.spin_is_contended = xen_spin_is_contended; pv_lock_ops.spin_lock = xen_spin_lock; pv_lock_ops.spin_lock_flags = xen_spin_lock_flags; pv_lock_ops.spin_trylock = xen_spin_trylock; pv_lock_ops.spin_unlock = xen_spin_unlock; +#endif }#ifdef CONFIG_XEN_DEBUG_FS
Signature · 1 line
1.7.2.3
PATCH 8/14 x86/ticketlock: collapse a layer of functions
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
Now that the paravirtualization layer doesn't exist at the spinlock level any more, we can collapse the __ticket_ functions into the arch_ functions.
--- arch/x86/include/asm/spinlock.h | 35 +++++------------------------------ 1 files changed, 5 insertions(+), 30 deletions(-)
arch/x86/include/asm/spinlock.h +5 -30
@@ -108,7 +108,7 @@ static __always_inline void __ticket_unlock_kick(struct arch_spinlock *lock, __t____ticket_unlock_kick (lock, next); } -static __always_inline void __ticket_spin_lock(struct arch_spinlock *lock) +static __always_inline void arch_spin_lock(struct arch_spinlock *lock) { registerstruct __raw_tickets inc;
@@ -128,7 +128,7 @@ static __always_inline void __ticket_spin_lock(struct arch_spinlock *lock) out:barrier ();/* make sure nothing creeps before the lock is taken */ } -static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock) +static __always_inline int arch_spin_trylock(arch_spinlock_t *lock) {arch_spinlock_t old, new;
@@ -142,7 +142,7 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)return cmpxchg (&lock->head_tail, old.head_tail, new.head_tail) == old.head_tail; } -static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock) +static __always_inline void arch_spin_unlock(arch_spinlock_t *lock) {__ticket_t next = lock->tickets.head +1 ;__ticket_unlock_release (lock);
@@ -150,46 +150,21 @@ static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)barrier ();/* prevent reordering into locked region */ } -static inline int __ticket_spin_is_locked (arch_spinlock_t *lock) +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 __ticket_spin_is_contended (arch_spinlock_t *lock) +static inline int arch_spin_is_contended (arch_spinlock_t *lock) {struct __raw_tickets tmp =ACCESS_ONCE (lock->tickets);return ((tmp.tail - tmp.head) &TICKET_MASK ) >1 ; } - -static inline int arch_spin_is_locked (arch_spinlock_t *lock) -{ -return __ticket_spin_is_locked (lock); -} - -static inline int arch_spin_is_contended (arch_spinlock_t *lock) -{ -return __ticket_spin_is_contended (lock); -}#define arch_spin_is_contended arch_spin_is_contended -static __always_inline void arch_spin_lock(arch_spinlock_t *lock) -{ -__ticket_spin_lock (lock); -} - -static __always_inline int arch_spin_trylock(arch_spinlock_t *lock) -{ -return __ticket_spin_trylock (lock); -} - -static __always_inline void arch_spin_unlock(arch_spinlock_t *lock) -{ -__ticket_spin_unlock (lock); -} - static __always_inline void arch_spin_lock_flags(arch_spinlock_t *lock,unsigned long flags) {
Signature · 1 line
1.7.2.3
PATCH 8/14 x86/ticketlock: collapse a layer of functions
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
Now that the paravirtualization layer doesn't exist at the spinlock level any more, we can collapse the __ticket_ functions into the arch_ functions.
--- arch/x86/include/asm/spinlock.h | 35 +++++------------------------------ 1 files changed, 5 insertions(+), 30 deletions(-)
arch/x86/include/asm/spinlock.h +5 -30
@@ -108,7 +108,7 @@ static __always_inline void __ticket_unlock_kick(struct arch_spinlock *lock, __t____ticket_unlock_kick (lock, next); } -static __always_inline void __ticket_spin_lock(struct arch_spinlock *lock) +static __always_inline void arch_spin_lock(struct arch_spinlock *lock) { registerstruct __raw_tickets inc;
@@ -128,7 +128,7 @@ static __always_inline void __ticket_spin_lock(struct arch_spinlock *lock) out:barrier ();/* make sure nothing creeps before the lock is taken */ } -static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock) +static __always_inline int arch_spin_trylock(arch_spinlock_t *lock) {arch_spinlock_t old, new;
@@ -142,7 +142,7 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)return cmpxchg (&lock->head_tail, old.head_tail, new.head_tail) == old.head_tail; } -static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock) +static __always_inline void arch_spin_unlock(arch_spinlock_t *lock) {__ticket_t next = lock->tickets.head +1 ;__ticket_unlock_release (lock);
@@ -150,46 +150,21 @@ static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)barrier ();/* prevent reordering into locked region */ } -static inline int __ticket_spin_is_locked (arch_spinlock_t *lock) +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 __ticket_spin_is_contended (arch_spinlock_t *lock) +static inline int arch_spin_is_contended (arch_spinlock_t *lock) {struct __raw_tickets tmp =ACCESS_ONCE (lock->tickets);return ((tmp.tail - tmp.head) &TICKET_MASK ) >1 ; } - -static inline int arch_spin_is_locked (arch_spinlock_t *lock) -{ -return __ticket_spin_is_locked (lock); -} - -static inline int arch_spin_is_contended (arch_spinlock_t *lock) -{ -return __ticket_spin_is_contended (lock); -}#define arch_spin_is_contended arch_spin_is_contended -static __always_inline void arch_spin_lock(arch_spinlock_t *lock) -{ -__ticket_spin_lock (lock); -} - -static __always_inline int arch_spin_trylock(arch_spinlock_t *lock) -{ -return __ticket_spin_trylock (lock); -} - -static __always_inline void arch_spin_unlock(arch_spinlock_t *lock) -{ -__ticket_spin_unlock (lock); -} - static __always_inline void arch_spin_lock_flags(arch_spinlock_t *lock,unsigned long flags) {
Signature · 1 line
1.7.2.3
PATCH 9/14 xen/pvticketlock: Xen implementation for PV ticket locks
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
Replace the old Xen implementation of PV spinlocks with and implementation of xen_lock_spinning and xen_unlock_kick.
xen_lock_spinning simply registers the cpu in its entry in lock_waiting, adds itself to the waiting_cpus set, and blocks on an event channel until the channel becomes pending.
xen_unlock_kick searches the cpus in waiting_cpus looking for the one which next wants this lock with the next ticket, if any. If found, it kicks it by making its event channel pending, which wakes it up.
--- arch/x86/xen/spinlock.c | 281 ++++++----------------------------------------- 1 files changed, 36 insertions(+), 245 deletions(-)
arch/x86/xen/spinlock.c +36 -245
@@ -19,32 +19,21 @@#ifdef CONFIG_XEN_DEBUG_FS static struct xen_spinlock_stats { -u64 taken;u32 taken_slow; -u32 taken_slow_nested;u32 taken_slow_pickup;u32 taken_slow_spurious; -u32 taken_slow_irqenable; -u64 released;u32 released_slow;u32 released_slow_kicked;#define HISTO_BUCKETS 30 -u32 histo_spin_total[HISTO_BUCKETS +1 ]; -u32 histo_spin_spinning[HISTO_BUCKETS +1 ];u32 histo_spin_blocked[HISTO_BUCKETS +1 ]; -u64 time_total; -u64 time_spinning;u64 time_blocked; } spinlock_stats;static u8 zero_stats; -static unsigned lock_timeout =1 <<10 ; -#define TIMEOUT lock_timeout -static inline void check_zero (void ) {if (unlikely (zero_stats)) {
@@ -73,22 +62,6 @@ static void __spin_time_accum(u64 delta, u32 *array) array[HISTO_BUCKETS ]++; } -static inline void spin_time_accum_spinning (u64 start) -{ -u32 delta =xen_clocksource_read () - start; - -__spin_time_accum (delta, spinlock_stats.histo_spin_spinning); - spinlock_stats.time_spinning += delta; -} - -static inline void spin_time_accum_total (u64 start) -{ -u32 delta =xen_clocksource_read () - start; - -__spin_time_accum (delta, spinlock_stats.histo_spin_total); - spinlock_stats.time_total += delta; -} -static inline void spin_time_accum_blocked (u64 start) {u32 delta =xen_clocksource_read () - start;
@@ -105,214 +78,76 @@ static inline u64 spin_time_start(void)return 0 ; } -static inline void spin_time_accum_total (u64 start) -{ -} -static inline void spin_time_accum_spinning (u64 start) -{ -}static inline void spin_time_accum_blocked (u64 start) { }#endif /* CONFIG_XEN_DEBUG_FS */ -struct xen_spinlock { -unsigned char lock;/* 0 -> free; 1 -> locked */ -unsigned short spinners;/* count of waiting cpus */ +struct xen_lock_waiting { +struct arch_spinlock *lock; +__ticket_t want; }; static DEFINE_PER_CPU(int, lock_kicker_irq) = -1; +static DEFINE_PER_CPU(struct xen_lock_waiting, lock_waiting); +static cpumask_t waiting_cpus; -#if 0 -static int xen_spin_is_locked (struct arch_spinlock *lock) -{ -struct xen_spinlock *xl = (struct xen_spinlock *)lock; - -return xl->lock !=0 ; -} - -static int xen_spin_is_contended (struct arch_spinlock *lock) -{ -struct xen_spinlock *xl = (struct xen_spinlock *)lock; - -/* Not strictly true; this is only the count of contended -lock-takers entering the slow path. */ -return xl->spinners !=0 ; -} - -static int xen_spin_trylock (struct arch_spinlock *lock) -{ -struct xen_spinlock *xl = (struct xen_spinlock *)lock; -u8 old =1 ; - - asm("xchgb %b0,%1" - :"+q" (old),"+m" (xl->lock) : :"memory" ); - -return old ==0 ; -} - -static DEFINE_PER_CPU(struct xen_spinlock *, lock_spinners); - -/* -* Mark a cpu as interested in a lock. Returns the CPU's previous -* lock of interest, in case we got preempted by an interrupt. -*/ -static inline struct xen_spinlock *spinning_lock (struct xen_spinlock *xl) -{ -struct xen_spinlock *prev; - - prev =__get_cpu_var (lock_spinners); -__get_cpu_var (lock_spinners) = xl; - -wmb ();/* set lock of interest before count */ - - asm(LOCK_PREFIX " incw %0" - :"+m" (xl->spinners) : :"memory" ); - -return prev; -} - -/* -* Mark a cpu as no longer interested in a lock. Restores previous -* lock of interest (NULL for none). -*/ -static inline void unspinning_lock (struct xen_spinlock *xl,struct xen_spinlock *prev) -{ - asm(LOCK_PREFIX " decw %0" - :"+m" (xl->spinners) : :"memory" ); -wmb ();/* decrement count before restoring lock */ -__get_cpu_var (lock_spinners) = prev; -} - -static noinline int xen_spin_lock_slow(struct arch_spinlock *lock, bool irq_enable) +static void xen_lock_spinning (struct arch_spinlock *lock,unsigned want) { -struct xen_spinlock *xl = (struct xen_spinlock *)lock; -struct xen_spinlock *prev;int irq =__get_cpu_var (lock_kicker_irq); -int ret; +struct xen_lock_waiting *w = &__get_cpu_var (lock_waiting); +int cpu =smp_processor_id ();u64 start;/* If kicker interrupts not initialized yet, just spin */ if (irq ==-1 ) -return 0 ; +return ; start =spin_time_start (); -/* announce we're spinning */ - prev =spinning_lock (xl); + w->want = want; + w->lock = lock; + +/* This uses set_bit, which atomic and therefore a barrier */ +cpumask_set_cpu (cpu, &waiting_cpus);ADD_STATS (taken_slow,1 ); -ADD_STATS (taken_slow_nested, prev !=NULL ); - -do { -unsigned long flags; - -/* clear pending */ -xen_clear_irq_pending (irq); - -/* check again make sure it didn't become free while -we weren't looking */ - ret =xen_spin_trylock (lock); -if (ret) { -ADD_STATS (taken_slow_pickup,1 ); - -/* -* If we interrupted another spinlock while it -* was blocking, make sure it doesn't block -* without rechecking the lock. -*/ -if (prev !=NULL ) -xen_set_irq_pending (irq); - goto out; - } - flags =arch_local_save_flags (); -if (irq_enable) { -ADD_STATS (taken_slow_irqenable,1 ); -raw_local_irq_enable (); - } +/* clear pending */ +xen_clear_irq_pending (irq); -/* -* Block until irq becomes pending. If we're -* interrupted at this point (after the trylock but -* before entering the block), then the nested lock -* handler guarantees that the irq will be left -* pending if there's any chance the lock became free; -* xen_poll_irq() returns immediately if the irq is -* pending. -*/ -xen_poll_irq (irq); +/* Only check lock once pending cleared */ +barrier (); -raw_local_irq_restore (flags); +/* check again make sure it didn't become free while +we weren't looking */ +if (ACCESS_ONCE (lock->tickets.head) == want) { +ADD_STATS (taken_slow_pickup,1 ); + goto out; + } -ADD_STATS (taken_slow_spurious, !xen_test_irq_pending (irq)); - }while (!xen_test_irq_pending (irq));/* check for spurious wakeups */ +/* Block until irq becomes pending (or perhaps a spurious wakeup) */ +xen_poll_irq (irq); +ADD_STATS (taken_slow_spurious, !xen_test_irq_pending (irq));kstat_incr_irqs_this_cpu (irq,irq_to_desc (irq)); out: -unspinning_lock (xl, prev); +cpumask_clear_cpu (cpu, &waiting_cpus); + w->lock =NULL ;spin_time_accum_blocked (start); - -return ret; } -static inline void __xen_spin_lock (struct arch_spinlock *lock,bool irq_enable) -{ -struct xen_spinlock *xl = (struct xen_spinlock *)lock; -unsigned timeout; -u8 oldval; -u64 start_spin; - -ADD_STATS (taken,1 ); - - start_spin =spin_time_start (); - -do { -u64 start_spin_fast =spin_time_start (); - - timeout =TIMEOUT ; - - asm("1: xchgb %1,%0\n" -" testb %1,%1\n" -" jz 3f\n" -"2: rep;nop\n" -" cmpb $0,%0\n" -" je 1b\n" -" dec %2\n" -" jnz 2b\n" -"3:\n" - :"+m" (xl->lock),"=q" (oldval),"+r" (timeout) - :"1" (1 ) - :"memory" ); - -spin_time_accum_spinning (start_spin_fast); - - }while (unlikely (oldval !=0 && - (TIMEOUT == ~0 || !xen_spin_lock_slow (lock, irq_enable)))); - -spin_time_accum_total (start_spin); -} - -static void xen_spin_lock (struct arch_spinlock *lock) -{ -__xen_spin_lock (lock, false); -} - -static void xen_spin_lock_flags (struct arch_spinlock *lock,unsigned long flags) -{ -__xen_spin_lock (lock, !raw_irqs_disabled_flags (flags)); -} - -static noinline void xen_spin_unlock_slow(struct xen_spinlock *xl) +static void xen_unlock_kick (struct arch_spinlock *lock,unsigned next) {int cpu;ADD_STATS (released_slow,1 ); -for_each_online_cpu (cpu) { -/* XXX should mix up next cpu selection */ -if (per_cpu (lock_spinners, cpu) == xl) { +for_each_cpu (cpu, &waiting_cpus) { +const struct xen_lock_waiting *w = &per_cpu (lock_waiting, cpu); + +if (w->lock == lock && w->want == next) {ADD_STATS (released_slow_kicked,1 );xen_send_IPI_one (cpu,XEN_SPIN_UNLOCK_VECTOR );break ;
@@ -320,28 +155,6 @@ static noinline void xen_spin_unlock_slow(struct xen_spinlock *xl) } } -static void xen_spin_unlock (struct arch_spinlock *lock) -{ -struct xen_spinlock *xl = (struct xen_spinlock *)lock; - -ADD_STATS (released,1 ); - -smp_wmb ();/* make sure no writes get moved after unlock */ - xl->lock =0 ;/* release lock */ - -/* -* Make sure unlock happens before checking for waiting -* spinners. We need a strong barrier to enforce the -* write-read ordering to different memory locations, as the -* CPU makes no implied guarantees about their ordering. -*/ -mb (); - -if (unlikely (xl->spinners)) -xen_spin_unlock_slow (xl); -} -#endif -static irqreturn_t dummy_handler (int irq,void *dev_id) {BUG ();
@@ -376,14 +189,8 @@ void xen_uninit_lock_cpu(int cpu)void __init xen_init_spinlocks (void ) { -#if 0 - pv_lock_ops.spin_is_locked = xen_spin_is_locked; - pv_lock_ops.spin_is_contended = xen_spin_is_contended; - pv_lock_ops.spin_lock = xen_spin_lock; - pv_lock_ops.spin_lock_flags = xen_spin_lock_flags; - pv_lock_ops.spin_trylock = xen_spin_trylock; - pv_lock_ops.spin_unlock = xen_spin_unlock; -#endif + pv_lock_ops.lock_spinning = xen_lock_spinning; + pv_lock_ops.unlock_kick = xen_unlock_kick; }#ifdef CONFIG_XEN_DEBUG_FS
@@ -401,37 +208,21 @@ static int __init xen_spinlock_debugfs(void)debugfs_create_u8 ("zero_stats" ,0644 , d_spin_debug, &zero_stats); -debugfs_create_u32 ("timeout" ,0644 , d_spin_debug, &lock_timeout); - -debugfs_create_u64 ("taken" ,0444 , d_spin_debug, &spinlock_stats.taken);debugfs_create_u32 ("taken_slow" ,0444 , d_spin_debug, &spinlock_stats.taken_slow); -debugfs_create_u32 ("taken_slow_nested" ,0444 , d_spin_debug, - &spinlock_stats.taken_slow_nested);debugfs_create_u32 ("taken_slow_pickup" ,0444 , d_spin_debug, &spinlock_stats.taken_slow_pickup);debugfs_create_u32 ("taken_slow_spurious" ,0444 , d_spin_debug, &spinlock_stats.taken_slow_spurious); -debugfs_create_u32 ("taken_slow_irqenable" ,0444 , d_spin_debug, - &spinlock_stats.taken_slow_irqenable); -debugfs_create_u64 ("released" ,0444 , d_spin_debug, &spinlock_stats.released);debugfs_create_u32 ("released_slow" ,0444 , d_spin_debug, &spinlock_stats.released_slow);debugfs_create_u32 ("released_slow_kicked" ,0444 , d_spin_debug, &spinlock_stats.released_slow_kicked); -debugfs_create_u64 ("time_spinning" ,0444 , d_spin_debug, - &spinlock_stats.time_spinning);debugfs_create_u64 ("time_blocked" ,0444 , d_spin_debug, &spinlock_stats.time_blocked); -debugfs_create_u64 ("time_total" ,0444 , d_spin_debug, - &spinlock_stats.time_total); -xen_debugfs_create_u32_array ("histo_total" ,0444 , d_spin_debug, - spinlock_stats.histo_spin_total,HISTO_BUCKETS +1 ); -xen_debugfs_create_u32_array ("histo_spinning" ,0444 , d_spin_debug, - spinlock_stats.histo_spin_spinning,HISTO_BUCKETS +1 );xen_debugfs_create_u32_array ("histo_blocked" ,0444 , d_spin_debug, spinlock_stats.histo_spin_blocked,HISTO_BUCKETS +1 );
Signature · 1 line
1.7.2.3
PATCH 9/14 xen/pvticketlock: Xen implementation for PV ticket locks
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
Replace the old Xen implementation of PV spinlocks with and implementation of xen_lock_spinning and xen_unlock_kick.
xen_lock_spinning simply registers the cpu in its entry in lock_waiting, adds itself to the waiting_cpus set, and blocks on an event channel until the channel becomes pending.
xen_unlock_kick searches the cpus in waiting_cpus looking for the one which next wants this lock with the next ticket, if any. If found, it kicks it by making its event channel pending, which wakes it up.
--- arch/x86/xen/spinlock.c | 281 ++++++----------------------------------------- 1 files changed, 36 insertions(+), 245 deletions(-)
arch/x86/xen/spinlock.c +36 -245
@@ -19,32 +19,21 @@#ifdef CONFIG_XEN_DEBUG_FS static struct xen_spinlock_stats { -u64 taken;u32 taken_slow; -u32 taken_slow_nested;u32 taken_slow_pickup;u32 taken_slow_spurious; -u32 taken_slow_irqenable; -u64 released;u32 released_slow;u32 released_slow_kicked;#define HISTO_BUCKETS 30 -u32 histo_spin_total[HISTO_BUCKETS +1 ]; -u32 histo_spin_spinning[HISTO_BUCKETS +1 ];u32 histo_spin_blocked[HISTO_BUCKETS +1 ]; -u64 time_total; -u64 time_spinning;u64 time_blocked; } spinlock_stats;static u8 zero_stats; -static unsigned lock_timeout =1 <<10 ; -#define TIMEOUT lock_timeout -static inline void check_zero (void ) {if (unlikely (zero_stats)) {
@@ -73,22 +62,6 @@ static void __spin_time_accum(u64 delta, u32 *array) array[HISTO_BUCKETS ]++; } -static inline void spin_time_accum_spinning (u64 start) -{ -u32 delta =xen_clocksource_read () - start; - -__spin_time_accum (delta, spinlock_stats.histo_spin_spinning); - spinlock_stats.time_spinning += delta; -} - -static inline void spin_time_accum_total (u64 start) -{ -u32 delta =xen_clocksource_read () - start; - -__spin_time_accum (delta, spinlock_stats.histo_spin_total); - spinlock_stats.time_total += delta; -} -static inline void spin_time_accum_blocked (u64 start) {u32 delta =xen_clocksource_read () - start;
@@ -105,214 +78,76 @@ static inline u64 spin_time_start(void)return 0 ; } -static inline void spin_time_accum_total (u64 start) -{ -} -static inline void spin_time_accum_spinning (u64 start) -{ -}static inline void spin_time_accum_blocked (u64 start) { }#endif /* CONFIG_XEN_DEBUG_FS */ -struct xen_spinlock { -unsigned char lock;/* 0 -> free; 1 -> locked */ -unsigned short spinners;/* count of waiting cpus */ +struct xen_lock_waiting { +struct arch_spinlock *lock; +__ticket_t want; }; static DEFINE_PER_CPU(int, lock_kicker_irq) = -1; +static DEFINE_PER_CPU(struct xen_lock_waiting, lock_waiting); +static cpumask_t waiting_cpus; -#if 0 -static int xen_spin_is_locked (struct arch_spinlock *lock) -{ -struct xen_spinlock *xl = (struct xen_spinlock *)lock; - -return xl->lock !=0 ; -} - -static int xen_spin_is_contended (struct arch_spinlock *lock) -{ -struct xen_spinlock *xl = (struct xen_spinlock *)lock; - -/* Not strictly true; this is only the count of contended -lock-takers entering the slow path. */ -return xl->spinners !=0 ; -} - -static int xen_spin_trylock (struct arch_spinlock *lock) -{ -struct xen_spinlock *xl = (struct xen_spinlock *)lock; -u8 old =1 ; - - asm("xchgb %b0,%1" - :"+q" (old),"+m" (xl->lock) : :"memory" ); - -return old ==0 ; -} - -static DEFINE_PER_CPU(struct xen_spinlock *, lock_spinners); - -/* -* Mark a cpu as interested in a lock. Returns the CPU's previous -* lock of interest, in case we got preempted by an interrupt. -*/ -static inline struct xen_spinlock *spinning_lock (struct xen_spinlock *xl) -{ -struct xen_spinlock *prev; - - prev =__get_cpu_var (lock_spinners); -__get_cpu_var (lock_spinners) = xl; - -wmb ();/* set lock of interest before count */ - - asm(LOCK_PREFIX " incw %0" - :"+m" (xl->spinners) : :"memory" ); - -return prev; -} - -/* -* Mark a cpu as no longer interested in a lock. Restores previous -* lock of interest (NULL for none). -*/ -static inline void unspinning_lock (struct xen_spinlock *xl,struct xen_spinlock *prev) -{ - asm(LOCK_PREFIX " decw %0" - :"+m" (xl->spinners) : :"memory" ); -wmb ();/* decrement count before restoring lock */ -__get_cpu_var (lock_spinners) = prev; -} - -static noinline int xen_spin_lock_slow(struct arch_spinlock *lock, bool irq_enable) +static void xen_lock_spinning (struct arch_spinlock *lock,unsigned want) { -struct xen_spinlock *xl = (struct xen_spinlock *)lock; -struct xen_spinlock *prev;int irq =__get_cpu_var (lock_kicker_irq); -int ret; +struct xen_lock_waiting *w = &__get_cpu_var (lock_waiting); +int cpu =smp_processor_id ();u64 start;/* If kicker interrupts not initialized yet, just spin */ if (irq ==-1 ) -return 0 ; +return ; start =spin_time_start (); -/* announce we're spinning */ - prev =spinning_lock (xl); + w->want = want; + w->lock = lock; + +/* This uses set_bit, which atomic and therefore a barrier */ +cpumask_set_cpu (cpu, &waiting_cpus);ADD_STATS (taken_slow,1 ); -ADD_STATS (taken_slow_nested, prev !=NULL ); - -do { -unsigned long flags; - -/* clear pending */ -xen_clear_irq_pending (irq); - -/* check again make sure it didn't become free while -we weren't looking */ - ret =xen_spin_trylock (lock); -if (ret) { -ADD_STATS (taken_slow_pickup,1 ); - -/* -* If we interrupted another spinlock while it -* was blocking, make sure it doesn't block -* without rechecking the lock. -*/ -if (prev !=NULL ) -xen_set_irq_pending (irq); - goto out; - } - flags =arch_local_save_flags (); -if (irq_enable) { -ADD_STATS (taken_slow_irqenable,1 ); -raw_local_irq_enable (); - } +/* clear pending */ +xen_clear_irq_pending (irq); -/* -* Block until irq becomes pending. If we're -* interrupted at this point (after the trylock but -* before entering the block), then the nested lock -* handler guarantees that the irq will be left -* pending if there's any chance the lock became free; -* xen_poll_irq() returns immediately if the irq is -* pending. -*/ -xen_poll_irq (irq); +/* Only check lock once pending cleared */ +barrier (); -raw_local_irq_restore (flags); +/* check again make sure it didn't become free while +we weren't looking */ +if (ACCESS_ONCE (lock->tickets.head) == want) { +ADD_STATS (taken_slow_pickup,1 ); + goto out; + } -ADD_STATS (taken_slow_spurious, !xen_test_irq_pending (irq)); - }while (!xen_test_irq_pending (irq));/* check for spurious wakeups */ +/* Block until irq becomes pending (or perhaps a spurious wakeup) */ +xen_poll_irq (irq); +ADD_STATS (taken_slow_spurious, !xen_test_irq_pending (irq));kstat_incr_irqs_this_cpu (irq,irq_to_desc (irq)); out: -unspinning_lock (xl, prev); +cpumask_clear_cpu (cpu, &waiting_cpus); + w->lock =NULL ;spin_time_accum_blocked (start); - -return ret; } -static inline void __xen_spin_lock (struct arch_spinlock *lock,bool irq_enable) -{ -struct xen_spinlock *xl = (struct xen_spinlock *)lock; -unsigned timeout; -u8 oldval; -u64 start_spin; - -ADD_STATS (taken,1 ); - - start_spin =spin_time_start (); - -do { -u64 start_spin_fast =spin_time_start (); - - timeout =TIMEOUT ; - - asm("1: xchgb %1,%0\n" -" testb %1,%1\n" -" jz 3f\n" -"2: rep;nop\n" -" cmpb $0,%0\n" -" je 1b\n" -" dec %2\n" -" jnz 2b\n" -"3:\n" - :"+m" (xl->lock),"=q" (oldval),"+r" (timeout) - :"1" (1 ) - :"memory" ); - -spin_time_accum_spinning (start_spin_fast); - - }while (unlikely (oldval !=0 && - (TIMEOUT == ~0 || !xen_spin_lock_slow (lock, irq_enable)))); - -spin_time_accum_total (start_spin); -} - -static void xen_spin_lock (struct arch_spinlock *lock) -{ -__xen_spin_lock (lock, false); -} - -static void xen_spin_lock_flags (struct arch_spinlock *lock,unsigned long flags) -{ -__xen_spin_lock (lock, !raw_irqs_disabled_flags (flags)); -} - -static noinline void xen_spin_unlock_slow(struct xen_spinlock *xl) +static void xen_unlock_kick (struct arch_spinlock *lock,unsigned next) {int cpu;ADD_STATS (released_slow,1 ); -for_each_online_cpu (cpu) { -/* XXX should mix up next cpu selection */ -if (per_cpu (lock_spinners, cpu) == xl) { +for_each_cpu (cpu, &waiting_cpus) { +const struct xen_lock_waiting *w = &per_cpu (lock_waiting, cpu); + +if (w->lock == lock && w->want == next) {ADD_STATS (released_slow_kicked,1 );xen_send_IPI_one (cpu,XEN_SPIN_UNLOCK_VECTOR );break ;
@@ -320,28 +155,6 @@ static noinline void xen_spin_unlock_slow(struct xen_spinlock *xl) } } -static void xen_spin_unlock (struct arch_spinlock *lock) -{ -struct xen_spinlock *xl = (struct xen_spinlock *)lock; - -ADD_STATS (released,1 ); - -smp_wmb ();/* make sure no writes get moved after unlock */ - xl->lock =0 ;/* release lock */ - -/* -* Make sure unlock happens before checking for waiting -* spinners. We need a strong barrier to enforce the -* write-read ordering to different memory locations, as the -* CPU makes no implied guarantees about their ordering. -*/ -mb (); - -if (unlikely (xl->spinners)) -xen_spin_unlock_slow (xl); -} -#endif -static irqreturn_t dummy_handler (int irq,void *dev_id) {BUG ();
@@ -376,14 +189,8 @@ void xen_uninit_lock_cpu(int cpu)void __init xen_init_spinlocks (void ) { -#if 0 - pv_lock_ops.spin_is_locked = xen_spin_is_locked; - pv_lock_ops.spin_is_contended = xen_spin_is_contended; - pv_lock_ops.spin_lock = xen_spin_lock; - pv_lock_ops.spin_lock_flags = xen_spin_lock_flags; - pv_lock_ops.spin_trylock = xen_spin_trylock; - pv_lock_ops.spin_unlock = xen_spin_unlock; -#endif + pv_lock_ops.lock_spinning = xen_lock_spinning; + pv_lock_ops.unlock_kick = xen_unlock_kick; }#ifdef CONFIG_XEN_DEBUG_FS
@@ -401,37 +208,21 @@ static int __init xen_spinlock_debugfs(void)debugfs_create_u8 ("zero_stats" ,0644 , d_spin_debug, &zero_stats); -debugfs_create_u32 ("timeout" ,0644 , d_spin_debug, &lock_timeout); - -debugfs_create_u64 ("taken" ,0444 , d_spin_debug, &spinlock_stats.taken);debugfs_create_u32 ("taken_slow" ,0444 , d_spin_debug, &spinlock_stats.taken_slow); -debugfs_create_u32 ("taken_slow_nested" ,0444 , d_spin_debug, - &spinlock_stats.taken_slow_nested);debugfs_create_u32 ("taken_slow_pickup" ,0444 , d_spin_debug, &spinlock_stats.taken_slow_pickup);debugfs_create_u32 ("taken_slow_spurious" ,0444 , d_spin_debug, &spinlock_stats.taken_slow_spurious); -debugfs_create_u32 ("taken_slow_irqenable" ,0444 , d_spin_debug, - &spinlock_stats.taken_slow_irqenable); -debugfs_create_u64 ("released" ,0444 , d_spin_debug, &spinlock_stats.released);debugfs_create_u32 ("released_slow" ,0444 , d_spin_debug, &spinlock_stats.released_slow);debugfs_create_u32 ("released_slow_kicked" ,0444 , d_spin_debug, &spinlock_stats.released_slow_kicked); -debugfs_create_u64 ("time_spinning" ,0444 , d_spin_debug, - &spinlock_stats.time_spinning);debugfs_create_u64 ("time_blocked" ,0444 , d_spin_debug, &spinlock_stats.time_blocked); -debugfs_create_u64 ("time_total" ,0444 , d_spin_debug, - &spinlock_stats.time_total); -xen_debugfs_create_u32_array ("histo_total" ,0444 , d_spin_debug, - spinlock_stats.histo_spin_total,HISTO_BUCKETS +1 ); -xen_debugfs_create_u32_array ("histo_spinning" ,0444 , d_spin_debug, - spinlock_stats.histo_spin_spinning,HISTO_BUCKETS +1 );xen_debugfs_create_u32_array ("histo_blocked" ,0444 , d_spin_debug, spinlock_stats.histo_spin_blocked,HISTO_BUCKETS +1 );
Signature · 1 line
1.7.2.3
PATCH 10/14 x86/pvticketlock: use callee-save for lock_spinning
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
Although the lock_spinning calls in the spinlock code are on the uncommon path, their presence can cause the compiler to generate many more register save/restores in the function pre/postamble, which is in the fast path. To avoid this, convert it to using the pvops callee-save calling convention, which defers all the save/restores until the actual function is called, keeping the fastpath clean.
--- arch/x86/include/asm/paravirt.h | 2 +- arch/x86/include/asm/paravirt_types.h | 2 +- arch/x86/kernel/paravirt-spinlocks.c | 2 +- arch/x86/xen/spinlock.c | 3 ++- 4 files changed, 5 insertions(+), 4 deletions(-)
arch/x86/include/asm/paravirt.h +1 -1
@@ -719,7 +719,7 @@ static inline void __set_fixmap(unsigned /* enum fixed_addresses */ idx,static inline void __ticket_lock_spinning (struct arch_spinlock *lock,unsigned ticket) { -PVOP_VCALL2 (pv_lock_ops.lock_spinning, lock, ticket); +PVOP_VCALLEE2 (pv_lock_ops.lock_spinning, lock, ticket); }static inline void ____ticket_unlock_kick (struct arch_spinlock *lock,unsigned ticket)
arch/x86/include/asm/paravirt_types.h +1 -1
@@ -315,7 +315,7 @@ struct pv_mmu_ops {struct arch_spinlock ;struct pv_lock_ops { -void (*lock_spinning)(struct arch_spinlock *lock,unsigned ticket); +struct paravirt_callee_save lock_spinning;void (*unlock_kick)(struct arch_spinlock *lock,unsigned ticket); };
arch/x86/kernel/paravirt-spinlocks.c +1 -1
@@ -9,7 +9,7 @@struct pv_lock_ops pv_lock_ops = { #ifdef CONFIG_SMP - .lock_spinning = paravirt_nop, + .lock_spinning =__PV_IS_CALLEE_SAVE (paravirt_nop), .unlock_kick = paravirt_nop, #endif };
arch/x86/xen/spinlock.c +2 -1
@@ -137,6 +137,7 @@ out: w->lock =NULL ;spin_time_accum_blocked (start); } +PV_CALLEE_SAVE_REGS_THUNK (xen_lock_spinning);static void xen_unlock_kick (struct arch_spinlock *lock,unsigned next) {
@@ -189,7 +190,7 @@ void xen_uninit_lock_cpu(int cpu)void __init xen_init_spinlocks (void ) { - pv_lock_ops.lock_spinning = xen_lock_spinning; + pv_lock_ops.lock_spinning =PV_CALLEE_SAVE (xen_lock_spinning); pv_lock_ops.unlock_kick = xen_unlock_kick; }
Signature · 1 line
1.7.2.3
PATCH 10/14 x86/pvticketlock: use callee-save for lock_spinning
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
Although the lock_spinning calls in the spinlock code are on the uncommon path, their presence can cause the compiler to generate many more register save/restores in the function pre/postamble, which is in the fast path. To avoid this, convert it to using the pvops callee-save calling convention, which defers all the save/restores until the actual function is called, keeping the fastpath clean.
--- arch/x86/include/asm/paravirt.h | 2 +- arch/x86/include/asm/paravirt_types.h | 2 +- arch/x86/kernel/paravirt-spinlocks.c | 2 +- arch/x86/xen/spinlock.c | 3 ++- 4 files changed, 5 insertions(+), 4 deletions(-)
arch/x86/include/asm/paravirt.h +1 -1
@@ -719,7 +719,7 @@ static inline void __set_fixmap(unsigned /* enum fixed_addresses */ idx,static inline void __ticket_lock_spinning (struct arch_spinlock *lock,unsigned ticket) { -PVOP_VCALL2 (pv_lock_ops.lock_spinning, lock, ticket); +PVOP_VCALLEE2 (pv_lock_ops.lock_spinning, lock, ticket); }static inline void ____ticket_unlock_kick (struct arch_spinlock *lock,unsigned ticket)
arch/x86/include/asm/paravirt_types.h +1 -1
@@ -315,7 +315,7 @@ struct pv_mmu_ops {struct arch_spinlock ;struct pv_lock_ops { -void (*lock_spinning)(struct arch_spinlock *lock,unsigned ticket); +struct paravirt_callee_save lock_spinning;void (*unlock_kick)(struct arch_spinlock *lock,unsigned ticket); };
arch/x86/kernel/paravirt-spinlocks.c +1 -1
@@ -9,7 +9,7 @@struct pv_lock_ops pv_lock_ops = { #ifdef CONFIG_SMP - .lock_spinning = paravirt_nop, + .lock_spinning =__PV_IS_CALLEE_SAVE (paravirt_nop), .unlock_kick = paravirt_nop, #endif };
arch/x86/xen/spinlock.c +2 -1
@@ -137,6 +137,7 @@ out: w->lock =NULL ;spin_time_accum_blocked (start); } +PV_CALLEE_SAVE_REGS_THUNK (xen_lock_spinning);static void xen_unlock_kick (struct arch_spinlock *lock,unsigned next) {
@@ -189,7 +190,7 @@ void xen_uninit_lock_cpu(int cpu)void __init xen_init_spinlocks (void ) { - pv_lock_ops.lock_spinning = xen_lock_spinning; + pv_lock_ops.lock_spinning =PV_CALLEE_SAVE (xen_lock_spinning); pv_lock_ops.unlock_kick = xen_unlock_kick; }
Signature · 1 line
1.7.2.3
PATCH 11/14 x86/ticketlock: don't inline _spin_unlock when using paravirt spinlocks
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
The code size expands somewhat, and its probably better to just call a function rather than inline it.
--- arch/x86/Kconfig | 3 +++ kernel/Kconfig.locks | 2 +- 2 files changed, 4 insertions(+), 1 deletions(-)
arch/x86/Kconfig +3 -0
@@ -531,6 +531,9 @@ config PARAVIRT_SPINLOCKS If you are unsure how to answer this question, answer N. +config ARCH_NOINLINE_SPIN_UNLOCK + def_bool PARAVIRT_SPINLOCKS + config PARAVIRT_CLOCK bool
kernel/Kconfig.locks +1 -1
@@ -125,7 +125,7 @@ config INLINE_SPIN_LOCK_IRQSAVE ARCH_INLINE_SPIN_LOCK_IRQSAVE config INLINE_SPIN_UNLOCK - def_bool !DEBUG_SPINLOCK && (!PREEMPT || ARCH_INLINE_SPIN_UNLOCK) + def_bool !DEBUG_SPINLOCK && (!PREEMPT || ARCH_INLINE_SPIN_UNLOCK) && !ARCH_NOINLINE_SPIN_UNLOCK config INLINE_SPIN_UNLOCK_BH def_bool !DEBUG_SPINLOCK && ARCH_INLINE_SPIN_UNLOCK_BH
Signature · 1 line
1.7.2.3
PATCH 11/14 x86/ticketlock: don't inline _spin_unlock when using paravirt spinlocks
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
The code size expands somewhat, and its probably better to just call a function rather than inline it.
--- arch/x86/Kconfig | 3 +++ kernel/Kconfig.locks | 2 +- 2 files changed, 4 insertions(+), 1 deletions(-)
arch/x86/Kconfig +3 -0
@@ -531,6 +531,9 @@ config PARAVIRT_SPINLOCKS If you are unsure how to answer this question, answer N. +config ARCH_NOINLINE_SPIN_UNLOCK + def_bool PARAVIRT_SPINLOCKS + config PARAVIRT_CLOCK bool
kernel/Kconfig.locks +1 -1
@@ -125,7 +125,7 @@ config INLINE_SPIN_LOCK_IRQSAVE ARCH_INLINE_SPIN_LOCK_IRQSAVE config INLINE_SPIN_UNLOCK - def_bool !DEBUG_SPINLOCK && (!PREEMPT || ARCH_INLINE_SPIN_UNLOCK) + def_bool !DEBUG_SPINLOCK && (!PREEMPT || ARCH_INLINE_SPIN_UNLOCK) && !ARCH_NOINLINE_SPIN_UNLOCK config INLINE_SPIN_UNLOCK_BH def_bool !DEBUG_SPINLOCK && ARCH_INLINE_SPIN_UNLOCK_BH
Signature · 1 line
1.7.2.3
PATCH 12/14 x86/ticketlocks: when paravirtualizing ticket locks, increment by 2
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
Increment ticket head/tails by 2 rather than 1 to leave the LSB free to store a "is in slowpath state" bit. This halves the number of possible CPUs for a given ticket size, but this shouldn't matter in practice - kernels built for 32k+ CPU systems are probably specially built for the hardware rather than a generic distro kernel.
--- arch/x86/include/asm/spinlock.h | 18 +++++++++--------- arch/x86/include/asm/spinlock_types.h | 10 +++++++++- 2 files changed, 18 insertions(+), 10 deletions(-)
arch/x86/include/asm/spinlock.h +9 -9
@@ -36,17 +36,17 @@ 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" ); + asm (LOCK_PREFIX "addb %1, %0" + :"+m" (lock->tickets.head) :"i" (TICKET_LOCK_INC ) :"memory" );else - asm (LOCK_PREFIX "incw %0" - :"+m" (lock->tickets.head) : :"memory" ); + asm (LOCK_PREFIX "addw %1, %0" + :"+m" (lock->tickets.head) :"i" (TICKET_LOCK_INC ) :"memory" ); }#else static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock) { - lock->tickets.head++; + lock->tickets.head +=TICKET_LOCK_INC ; }#endif
@@ -84,7 +84,7 @@ static __always_inline void ____ticket_unlock_kick(struct arch_spinlock *lock, u*/ static __always_inline struct __raw_tickets __ticket_spin_claim(struct arch_spinlock *lock) { - registerstruct __raw_tickets tickets = { .tail =1 }; + registerstruct __raw_tickets tickets = { .tail =TICKET_LOCK_INC };if (sizeof (lock->tickets.head) ==sizeof (u8)) asm volatile (LOCK_PREFIX "xaddw %w0, %1\n"
@@ -136,7 +136,7 @@ static __always_inline int arch_spin_trylock(arch_spinlock_t *lock)if (old.tickets.head != old.tickets.tail)return 0 ; - new.head_tail = old.head_tail + (1 <<TICKET_SHIFT ); + new.head_tail = old.head_tail + (TICKET_LOCK_INC <<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;
@@ -144,7 +144,7 @@ static __always_inline int arch_spin_trylock(arch_spinlock_t *lock) static __always_inline void arch_spin_unlock(arch_spinlock_t *lock) { -__ticket_t next = lock->tickets.head +1 ; +__ticket_t next = lock->tickets.head +TICKET_LOCK_INC ;__ticket_unlock_release (lock);__ticket_unlock_kick (lock, next);barrier ();/* prevent reordering into locked region */
@@ -161,7 +161,7 @@ static inline int arch_spin_is_contended(arch_spinlock_t *lock) {struct __raw_tickets tmp =ACCESS_ONCE (lock->tickets); -return ((tmp.tail - tmp.head) &TICKET_MASK ) >1 ; +return ((tmp.tail - tmp.head) &TICKET_MASK ) >TICKET_LOCK_INC ; }#define arch_spin_is_contended arch_spin_is_contended
arch/x86/include/asm/spinlock_types.h +9 -1
@@ -7,7 +7,13 @@#include <linux/types.h> -#if (CONFIG_NR_CPUS <256 ) +#ifdef CONFIG_PARAVIRT_SPINLOCKS +#define __TICKET_LOCK_INC 2 +#else +#define __TICKET_LOCK_INC 1 +#endif + +#if (CONFIG_NR_CPUS < (256 / __TICKET_LOCK_INC))typedef u8 __ticket_t ;typedef u16 __ticketpair_t ;#else
@@ -15,6 +21,8 @@ typedef u16 __ticket_t;typedef u32 __ticketpair_t ;#endif +#define TICKET_LOCK_INC ((__ticket_t)__TICKET_LOCK_INC) +#define TICKET_SHIFT (sizeof(__ticket_t) * 8)#define TICKET_MASK ((__ticket_t)((1 << TICKET_SHIFT) - 1))
Signature · 1 line
1.7.2.3
PATCH 12/14 x86/ticketlocks: when paravirtualizing ticket locks, increment by 2
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
Increment ticket head/tails by 2 rather than 1 to leave the LSB free to store a "is in slowpath state" bit. This halves the number of possible CPUs for a given ticket size, but this shouldn't matter in practice - kernels built for 32k+ CPU systems are probably specially built for the hardware rather than a generic distro kernel.
--- arch/x86/include/asm/spinlock.h | 18 +++++++++--------- arch/x86/include/asm/spinlock_types.h | 10 +++++++++- 2 files changed, 18 insertions(+), 10 deletions(-)
arch/x86/include/asm/spinlock.h +9 -9
@@ -36,17 +36,17 @@ 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" ); + asm (LOCK_PREFIX "addb %1, %0" + :"+m" (lock->tickets.head) :"i" (TICKET_LOCK_INC ) :"memory" );else - asm (LOCK_PREFIX "incw %0" - :"+m" (lock->tickets.head) : :"memory" ); + asm (LOCK_PREFIX "addw %1, %0" + :"+m" (lock->tickets.head) :"i" (TICKET_LOCK_INC ) :"memory" ); }#else static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock) { - lock->tickets.head++; + lock->tickets.head +=TICKET_LOCK_INC ; }#endif
@@ -84,7 +84,7 @@ static __always_inline void ____ticket_unlock_kick(struct arch_spinlock *lock, u*/ static __always_inline struct __raw_tickets __ticket_spin_claim(struct arch_spinlock *lock) { - registerstruct __raw_tickets tickets = { .tail =1 }; + registerstruct __raw_tickets tickets = { .tail =TICKET_LOCK_INC };if (sizeof (lock->tickets.head) ==sizeof (u8)) asm volatile (LOCK_PREFIX "xaddw %w0, %1\n"
@@ -136,7 +136,7 @@ static __always_inline int arch_spin_trylock(arch_spinlock_t *lock)if (old.tickets.head != old.tickets.tail)return 0 ; - new.head_tail = old.head_tail + (1 <<TICKET_SHIFT ); + new.head_tail = old.head_tail + (TICKET_LOCK_INC <<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;
@@ -144,7 +144,7 @@ static __always_inline int arch_spin_trylock(arch_spinlock_t *lock) static __always_inline void arch_spin_unlock(arch_spinlock_t *lock) { -__ticket_t next = lock->tickets.head +1 ; +__ticket_t next = lock->tickets.head +TICKET_LOCK_INC ;__ticket_unlock_release (lock);__ticket_unlock_kick (lock, next);barrier ();/* prevent reordering into locked region */
@@ -161,7 +161,7 @@ static inline int arch_spin_is_contended(arch_spinlock_t *lock) {struct __raw_tickets tmp =ACCESS_ONCE (lock->tickets); -return ((tmp.tail - tmp.head) &TICKET_MASK ) >1 ; +return ((tmp.tail - tmp.head) &TICKET_MASK ) >TICKET_LOCK_INC ; }#define arch_spin_is_contended arch_spin_is_contended
arch/x86/include/asm/spinlock_types.h +9 -1
@@ -7,7 +7,13 @@#include <linux/types.h> -#if (CONFIG_NR_CPUS <256 ) +#ifdef CONFIG_PARAVIRT_SPINLOCKS +#define __TICKET_LOCK_INC 2 +#else +#define __TICKET_LOCK_INC 1 +#endif + +#if (CONFIG_NR_CPUS < (256 / __TICKET_LOCK_INC))typedef u8 __ticket_t ;typedef u16 __ticketpair_t ;#else
@@ -15,6 +21,8 @@ typedef u16 __ticket_t;typedef u32 __ticketpair_t ;#endif +#define TICKET_LOCK_INC ((__ticket_t)__TICKET_LOCK_INC) +#define TICKET_SHIFT (sizeof(__ticket_t) * 8)#define TICKET_MASK ((__ticket_t)((1 << TICKET_SHIFT) - 1))
Signature · 1 line
1.7.2.3
PATCH 13/14 x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
Maintain a flag in both LSBs of the ticket lock which indicates whether anyone is in the lock slowpath and may need kicking when the current holder unlocks. The flags are set when the first locker enters the slowpath, and cleared when unlocking to an empty queue.
In the specific implementation of lock_spinning(), make sure to set the slowpath flags on the lock just before blocking. We must do this before the last-chance pickup test to prevent a deadlock with the unlocker:
Unlocker Locker
test for lock pickup -> fail test slowpath + unlock -> false set slowpath flags block
Whereas this works in any ordering:
Unlocker Locker
set slowpath flags test for lock pickup
-> fail
block
test slowpath + unlock
-> true, kick
--- arch/x86/include/asm/spinlock.h | 53 ++++++++++++++++++++++++++++----- arch/x86/include/asm/spinlock_types.h | 2 + arch/x86/kernel/paravirt-spinlocks.c | 37 +++++++++++++++++++++++ arch/x86/xen/spinlock.c | 4 ++ 4 files changed, 88 insertions(+), 8 deletions(-)
arch/x86/include/asm/spinlock.h +45 -8
@@ -53,7 +53,38 @@ static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)/* How long a lock should spin before we consider blocking */ #define SPIN_THRESHOLD (1 << 11) -#ifndef CONFIG_PARAVIRT_SPINLOCKS +/* Only defined when CONFIG_PARAVIRT_SPINLOCKS defined, but may as +* well leave the prototype always visible. */ +extern void __ticket_unlock_release_slowpath (struct arch_spinlock *lock); + +#ifdef CONFIG_PARAVIRT_SPINLOCKS + +/* +* Return true if someone is in the slowpath on this lock. This +* should only be used by the current lock-holder. +*/ +static inline bool __ticket_in_slowpath (struct arch_spinlock *lock) +{ +return !!(lock->tickets.tail &TICKET_SLOWPATH_FLAG ); +} + +static inline void __ticket_enter_slowpath (struct arch_spinlock *lock) +{ +if (sizeof (lock->tickets.tail) ==sizeof (u8)) + asm (LOCK_PREFIX "orb %1, %0" + :"+m" (lock->tickets.tail) + :"i" (TICKET_SLOWPATH_FLAG ) :"memory" ); +else + asm (LOCK_PREFIX "orw %1, %0" + :"+m" (lock->tickets.tail) + :"i" (TICKET_SLOWPATH_FLAG ) :"memory" ); +} + +#else /* !CONFIG_PARAVIRT_SPINLOCKS */ +static inline bool __ticket_in_slowpath (struct arch_spinlock *lock) +{ +return false; +} static __always_inline void __ticket_lock_spinning(struct arch_spinlock *lock, unsigned ticket) {
@@ -84,18 +115,22 @@ static __always_inline void ____ticket_unlock_kick(struct arch_spinlock *lock, u*/ static __always_inline struct __raw_tickets __ticket_spin_claim(struct arch_spinlock *lock) { - registerstruct __raw_tickets tickets = { .tail =TICKET_LOCK_INC }; + registerstruct arch_spinlock tickets = { + { .tickets.tail =TICKET_LOCK_INC } + };if (sizeof (lock->tickets.head) ==sizeof (u8)) asmvolatile (LOCK_PREFIX "xaddw %w0, %1\n" - :"+r" (tickets),"+m" (lock->tickets) + :"+r" (tickets.head_tail),"+m" (lock->tickets) : :"memory" ,"cc" );else asmvolatile (LOCK_PREFIX "xaddl %0, %1\n" - :"+r" (tickets),"+m" (lock->tickets) + :"+r" (tickets.head_tail),"+m" (lock->tickets) : :"memory" ,"cc" ); -return tickets; + tickets.tickets.tail &= ~TICKET_SLOWPATH_FLAG ; + +return tickets.tickets; }/*
@@ -144,9 +179,11 @@ static __always_inline int arch_spin_trylock(arch_spinlock_t *lock) static __always_inline void arch_spin_unlock(arch_spinlock_t *lock) { -__ticket_t next = lock->tickets.head +TICKET_LOCK_INC ; -__ticket_unlock_release (lock); -__ticket_unlock_kick (lock, next); +barrier ();/* prevent reordering out of locked region */ +if (unlikely (__ticket_in_slowpath (lock))) +__ticket_unlock_release_slowpath (lock); +else +__ticket_unlock_release (lock);barrier ();/* prevent reordering into locked region */ }
arch/x86/include/asm/spinlock_types.h +2 -0
@@ -9,8 +9,10 @@#ifdef CONFIG_PARAVIRT_SPINLOCKS #define __TICKET_LOCK_INC 2 +#define TICKET_SLOWPATH_FLAG ((__ticket_t)1)#else #define __TICKET_LOCK_INC 1 +#define TICKET_SLOWPATH_FLAG ((__ticket_t)0)#endif #if (CONFIG_NR_CPUS < (256 / __TICKET_LOCK_INC))
arch/x86/kernel/paravirt-spinlocks.c +37 -0
@@ -15,3 +15,40 @@ struct pv_lock_ops pv_lock_ops = { };EXPORT_SYMBOL (pv_lock_ops); + +/* +* If we're unlocking and we're leaving the lock uncontended (there's +* nobody else waiting for the lock), then we can clear the slowpath +* bits. However, we need to be careful about this because someone +* may just be entering as we leave, and enter the slowpath. +*/ +void __ticket_unlock_release_slowpath (struct arch_spinlock *lock) +{ +struct arch_spinlock old, new; + +BUILD_BUG_ON (((__ticket_t )NR_CPUS ) !=NR_CPUS ); + + old =ACCESS_ONCE (*lock); + + new = old; + new.tickets.head +=TICKET_LOCK_INC ; + +/* Clear the slowpath flag */ + new.tickets.tail &= ~TICKET_SLOWPATH_FLAG ; + +/* +* If there's currently people waiting or someone snuck in +* since we read the lock above, then do a normal unlock and +* kick. If we managed to unlock with no queued waiters, then +* we can clear the slowpath flag. +*/ +if (new.tickets.head != new.tickets.tail || +cmpxchg (&lock->head_tail, + old.head_tail, new.head_tail) != old.head_tail) { +/* still people waiting */ +__ticket_unlock_release (lock); + } + +__ticket_unlock_kick (lock, new.tickets.head); +} +EXPORT_SYMBOL (__ticket_unlock_release_slowpath);
arch/x86/xen/spinlock.c +4 -0
@@ -119,6 +119,10 @@ static void xen_lock_spinning(struct arch_spinlock *lock, unsigned want)/* Only check lock once pending cleared */ barrier (); +/* Mark entry to slowpath before doing the pickup test to make +sure we don't deadlock with an unlocker. */ +__ticket_enter_slowpath (lock); +/* check again make sure it didn't become free while we weren't looking */ if (ACCESS_ONCE (lock->tickets.head) == want) {
Signature · 1 line
1.7.2.3
PATCH 13/14 x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
Maintain a flag in both LSBs of the ticket lock which indicates whether anyone is in the lock slowpath and may need kicking when the current holder unlocks. The flags are set when the first locker enters the slowpath, and cleared when unlocking to an empty queue.
In the specific implementation of lock_spinning(), make sure to set the slowpath flags on the lock just before blocking. We must do this before the last-chance pickup test to prevent a deadlock with the unlocker:
Unlocker Locker
test for lock pickup -> fail test slowpath + unlock -> false set slowpath flags block
Whereas this works in any ordering:
Unlocker Locker
set slowpath flags test for lock pickup
-> fail
block
test slowpath + unlock
-> true, kick
--- arch/x86/include/asm/spinlock.h | 53 ++++++++++++++++++++++++++++----- arch/x86/include/asm/spinlock_types.h | 2 + arch/x86/kernel/paravirt-spinlocks.c | 37 +++++++++++++++++++++++ arch/x86/xen/spinlock.c | 4 ++ 4 files changed, 88 insertions(+), 8 deletions(-)
arch/x86/include/asm/spinlock.h +45 -8
@@ -53,7 +53,38 @@ static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)/* How long a lock should spin before we consider blocking */ #define SPIN_THRESHOLD (1 << 11) -#ifndef CONFIG_PARAVIRT_SPINLOCKS +/* Only defined when CONFIG_PARAVIRT_SPINLOCKS defined, but may as +* well leave the prototype always visible. */ +extern void __ticket_unlock_release_slowpath (struct arch_spinlock *lock); + +#ifdef CONFIG_PARAVIRT_SPINLOCKS + +/* +* Return true if someone is in the slowpath on this lock. This +* should only be used by the current lock-holder. +*/ +static inline bool __ticket_in_slowpath (struct arch_spinlock *lock) +{ +return !!(lock->tickets.tail &TICKET_SLOWPATH_FLAG ); +} + +static inline void __ticket_enter_slowpath (struct arch_spinlock *lock) +{ +if (sizeof (lock->tickets.tail) ==sizeof (u8)) + asm (LOCK_PREFIX "orb %1, %0" + :"+m" (lock->tickets.tail) + :"i" (TICKET_SLOWPATH_FLAG ) :"memory" ); +else + asm (LOCK_PREFIX "orw %1, %0" + :"+m" (lock->tickets.tail) + :"i" (TICKET_SLOWPATH_FLAG ) :"memory" ); +} + +#else /* !CONFIG_PARAVIRT_SPINLOCKS */ +static inline bool __ticket_in_slowpath (struct arch_spinlock *lock) +{ +return false; +} static __always_inline void __ticket_lock_spinning(struct arch_spinlock *lock, unsigned ticket) {
@@ -84,18 +115,22 @@ static __always_inline void ____ticket_unlock_kick(struct arch_spinlock *lock, u*/ static __always_inline struct __raw_tickets __ticket_spin_claim(struct arch_spinlock *lock) { - registerstruct __raw_tickets tickets = { .tail =TICKET_LOCK_INC }; + registerstruct arch_spinlock tickets = { + { .tickets.tail =TICKET_LOCK_INC } + };if (sizeof (lock->tickets.head) ==sizeof (u8)) asmvolatile (LOCK_PREFIX "xaddw %w0, %1\n" - :"+r" (tickets),"+m" (lock->tickets) + :"+r" (tickets.head_tail),"+m" (lock->tickets) : :"memory" ,"cc" );else asmvolatile (LOCK_PREFIX "xaddl %0, %1\n" - :"+r" (tickets),"+m" (lock->tickets) + :"+r" (tickets.head_tail),"+m" (lock->tickets) : :"memory" ,"cc" ); -return tickets; + tickets.tickets.tail &= ~TICKET_SLOWPATH_FLAG ; + +return tickets.tickets; }/*
@@ -144,9 +179,11 @@ static __always_inline int arch_spin_trylock(arch_spinlock_t *lock) static __always_inline void arch_spin_unlock(arch_spinlock_t *lock) { -__ticket_t next = lock->tickets.head +TICKET_LOCK_INC ; -__ticket_unlock_release (lock); -__ticket_unlock_kick (lock, next); +barrier ();/* prevent reordering out of locked region */ +if (unlikely (__ticket_in_slowpath (lock))) +__ticket_unlock_release_slowpath (lock); +else +__ticket_unlock_release (lock);barrier ();/* prevent reordering into locked region */ }
arch/x86/include/asm/spinlock_types.h +2 -0
@@ -9,8 +9,10 @@#ifdef CONFIG_PARAVIRT_SPINLOCKS #define __TICKET_LOCK_INC 2 +#define TICKET_SLOWPATH_FLAG ((__ticket_t)1)#else #define __TICKET_LOCK_INC 1 +#define TICKET_SLOWPATH_FLAG ((__ticket_t)0)#endif #if (CONFIG_NR_CPUS < (256 / __TICKET_LOCK_INC))
arch/x86/kernel/paravirt-spinlocks.c +37 -0
@@ -15,3 +15,40 @@ struct pv_lock_ops pv_lock_ops = { };EXPORT_SYMBOL (pv_lock_ops); + +/* +* If we're unlocking and we're leaving the lock uncontended (there's +* nobody else waiting for the lock), then we can clear the slowpath +* bits. However, we need to be careful about this because someone +* may just be entering as we leave, and enter the slowpath. +*/ +void __ticket_unlock_release_slowpath (struct arch_spinlock *lock) +{ +struct arch_spinlock old, new; + +BUILD_BUG_ON (((__ticket_t )NR_CPUS ) !=NR_CPUS ); + + old =ACCESS_ONCE (*lock); + + new = old; + new.tickets.head +=TICKET_LOCK_INC ; + +/* Clear the slowpath flag */ + new.tickets.tail &= ~TICKET_SLOWPATH_FLAG ; + +/* +* If there's currently people waiting or someone snuck in +* since we read the lock above, then do a normal unlock and +* kick. If we managed to unlock with no queued waiters, then +* we can clear the slowpath flag. +*/ +if (new.tickets.head != new.tickets.tail || +cmpxchg (&lock->head_tail, + old.head_tail, new.head_tail) != old.head_tail) { +/* still people waiting */ +__ticket_unlock_release (lock); + } + +__ticket_unlock_kick (lock, new.tickets.head); +} +EXPORT_SYMBOL (__ticket_unlock_release_slowpath);
arch/x86/xen/spinlock.c +4 -0
@@ -119,6 +119,10 @@ static void xen_lock_spinning(struct arch_spinlock *lock, unsigned want)/* Only check lock once pending cleared */ barrier (); +/* Mark entry to slowpath before doing the pickup test to make +sure we don't deadlock with an unlocker. */ +__ticket_enter_slowpath (lock); +/* check again make sure it didn't become free while we weren't looking */ if (ACCESS_ONCE (lock->tickets.head) == want) {
Signature · 1 line
1.7.2.3
PATCH 14/14 x86/ticketlocks: tidy up __ticket_unlock_kick()
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
__ticket_unlock_kick() is now only called from known slowpaths, so there's no need for it to do any checking of its own.
--- arch/x86/include/asm/paravirt.h | 2 +- arch/x86/include/asm/spinlock.h | 14 -------------- 2 files changed, 1 insertions(+), 15 deletions(-)
arch/x86/include/asm/paravirt.h +1 -1
@@ -722,7 +722,7 @@ static inline void __ticket_lock_spinning(struct arch_spinlock *lock, unsigned tPVOP_VCALLEE2 (pv_lock_ops.lock_spinning, lock, ticket); } -static inline void ____ticket_unlock_kick (struct arch_spinlock *lock,unsigned ticket) +static inline void __ticket_unlock_kick (struct arch_spinlock *lock,unsigned ticket) {PVOP_VCALL2 (pv_lock_ops.unlock_kick, lock, ticket); }
arch/x86/include/asm/spinlock.h +0 -14
@@ -90,10 +90,6 @@ static __always_inline void __ticket_lock_spinning(struct arch_spinlock *lock, u { } -static __always_inline void ____ticket_unlock_kick(struct arch_spinlock *lock, unsigned ticket) -{ -} -#endif /* CONFIG_PARAVIRT_SPINLOCKS */ /*
@@ -133,16 +129,6 @@ static __always_inline struct __raw_tickets __ticket_spin_claim(struct arch_spinreturn tickets.tickets; } -/* -* If a spinlock has someone waiting on it, then kick the appropriate -* waiting cpu. -*/ -static __always_inline void __ticket_unlock_kick(struct arch_spinlock *lock, __ticket_t next) -{ -if (unlikely (lock->tickets.tail != next)) -____ticket_unlock_kick (lock, next); -} - static __always_inline void arch_spin_lock(struct arch_spinlock *lock) { registerstruct __raw_tickets inc;
Signature · 1 line
1.7.2.3
PATCH 14/14 x86/ticketlocks: tidy up __ticket_unlock_kick()
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
__ticket_unlock_kick() is now only called from known slowpaths, so there's no need for it to do any checking of its own.
--- arch/x86/include/asm/paravirt.h | 2 +- arch/x86/include/asm/spinlock.h | 14 -------------- 2 files changed, 1 insertions(+), 15 deletions(-)
arch/x86/include/asm/paravirt.h +1 -1
@@ -722,7 +722,7 @@ static inline void __ticket_lock_spinning(struct arch_spinlock *lock, unsigned tPVOP_VCALLEE2 (pv_lock_ops.lock_spinning, lock, ticket); } -static inline void ____ticket_unlock_kick (struct arch_spinlock *lock,unsigned ticket) +static inline void __ticket_unlock_kick (struct arch_spinlock *lock,unsigned ticket) {PVOP_VCALL2 (pv_lock_ops.unlock_kick, lock, ticket); }
arch/x86/include/asm/spinlock.h +0 -14
@@ -90,10 +90,6 @@ static __always_inline void __ticket_lock_spinning(struct arch_spinlock *lock, u { } -static __always_inline void ____ticket_unlock_kick(struct arch_spinlock *lock, unsigned ticket) -{ -} -#endif /* CONFIG_PARAVIRT_SPINLOCKS */ /*
@@ -133,16 +129,6 @@ static __always_inline struct __raw_tickets __ticket_spin_claim(struct arch_spinreturn tickets.tickets; } -/* -* If a spinlock has someone waiting on it, then kick the appropriate -* waiting cpu. -*/ -static __always_inline void __ticket_unlock_kick(struct arch_spinlock *lock, __ticket_t next) -{ -if (unlikely (lock->tickets.tail != next)) -____ticket_unlock_kick (lock, next); -} - static __always_inline void arch_spin_lock(struct arch_spinlock *lock) { registerstruct __raw_tickets inc;
Signature · 1 line
1.7.2.3
Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks
In reply to Jeremy FitzhardingeQuoted 15 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/xen/spinlock.c +4
-4+static void xen_lock_spinning (struct arch_spinlock *lock,unsigned want) { -struct xen_spinlock *xl = (struct xen_spinlock *)lock; -struct xen_spinlock *prev;int irq =__get_cpu_var (lock_kicker_irq); -int ret; +struct xen_lock_waiting *w = &__get_cpu_var (lock_waiting); +int cpu =smp_processor_id ();u64 start;/* If kicker interrupts not initialized yet, just spin */ if (irq ==-1 ) -return 0 ; +return ;
arch/x86/xen/spinlock.c static inline u64 spin_time_start(void) · line 112
Quoted 10 lines
arch/x86/xen/spinlock.c +5
-2start =spin_time_start (); -/* announce we're spinning */ - prev =spinning_lock (xl); + w->want = want; + w->lock = lock; + +/* This uses set_bit, which atomic and therefore a barrier */ +cpumask_set_cpu (cpu, &waiting_cpus);
Since you don't allow nesting, don't you need to disable interrupts before you touch per-CPU state?
Jan
Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks
In reply to Jeremy FitzhardingeQuoted 15 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/xen/spinlock.c +4
-4+static void xen_lock_spinning (struct arch_spinlock *lock,unsigned want) { -struct xen_spinlock *xl = (struct xen_spinlock *)lock; -struct xen_spinlock *prev;int irq =__get_cpu_var (lock_kicker_irq); -int ret; +struct xen_lock_waiting *w = &__get_cpu_var (lock_waiting); +int cpu =smp_processor_id ();u64 start;/* If kicker interrupts not initialized yet, just spin */ if (irq ==-1 ) -return 0 ; +return ;
arch/x86/xen/spinlock.c static inline u64 spin_time_start(void) · line 112
Quoted 10 lines
arch/x86/xen/spinlock.c +5
-2start =spin_time_start (); -/* announce we're spinning */ - prev =spinning_lock (xl); + w->want = want; + w->lock = lock; + +/* This uses set_bit, which atomic and therefore a barrier */ +cpumask_set_cpu (cpu, &waiting_cpus);
Since you don't allow nesting, don't you need to disable interrupts before you touch per-CPU state?
Jan
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy Fitzhardingearch/x86/include/asm/spinlock.h static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock) · line 81
Quoted 12 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/include/asm/spinlock.h +11
-0+static inline void __ticket_enter_slowpath (struct arch_spinlock *lock) +{ +if (sizeof (lock->tickets.tail) ==sizeof (u8)) + asm (LOCK_PREFIX "orb %1, %0" + :"+m" (lock->tickets.tail) + :"i" (TICKET_SLOWPATH_FLAG ) :"memory" ); +else + asm (LOCK_PREFIX "orw %1, %0" + :"+m" (lock->tickets.tail) + :"i" (TICKET_SLOWPATH_FLAG ) :"memory" ); +}
Came only now to mind: Here and elsewhere, did you try using %z0 to have gcc produce the opcode suffix character, rather than having these somewhat ugly if()-s?
Jan
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy Fitzhardingearch/x86/include/asm/spinlock.h static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock) · line 81
Quoted 12 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/include/asm/spinlock.h +11
-0+static inline void __ticket_enter_slowpath (struct arch_spinlock *lock) +{ +if (sizeof (lock->tickets.tail) ==sizeof (u8)) + asm (LOCK_PREFIX "orb %1, %0" + :"+m" (lock->tickets.tail) + :"i" (TICKET_SLOWPATH_FLAG ) :"memory" ); +else + asm (LOCK_PREFIX "orw %1, %0" + :"+m" (lock->tickets.tail) + :"i" (TICKET_SLOWPATH_FLAG ) :"memory" ); +}
Came only now to mind: Here and elsewhere, did you try using %z0 to have gcc produce the opcode suffix character, rather than having these somewhat ugly if()-s?
Jan
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jan BeulichQuoted 15 lines · Jan Beulich
arch/x86/include/asm/spinlock.h static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock) · line 81
Quoted 12 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/include/asm/spinlock.h +11
-0+static inline void __ticket_enter_slowpath (struct arch_spinlock *lock) +{ +if (sizeof (lock->tickets.tail) ==sizeof (u8)) + asm (LOCK_PREFIX "orb %1, %0" + :"+m" (lock->tickets.tail) + :"i" (TICKET_SLOWPATH_FLAG ) :"memory" ); +else + asm (LOCK_PREFIX "orw %1, %0" + :"+m" (lock->tickets.tail) + :"i" (TICKET_SLOWPATH_FLAG ) :"memory" ); +}Came only now to mind: Here and elsewhere, did you try using %z0 to have gcc produce the opcode suffix character, rather than having these somewhat ugly if()-s?
Actually in this case I'm pretty sure there's already a "set bit" function which will do the job. set_bit(), I guess, though it takes a bit number rather than a mask...
But, yes, %z0 sounds interesting. Is it documented anywhere? I think I've tried to use it in the past and run into gcc bugs.
Thanks,
J
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jan BeulichQuoted 15 lines · Jan Beulich
arch/x86/include/asm/spinlock.h static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock) · line 81
Quoted 12 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/include/asm/spinlock.h +11
-0+static inline void __ticket_enter_slowpath (struct arch_spinlock *lock) +{ +if (sizeof (lock->tickets.tail) ==sizeof (u8)) + asm (LOCK_PREFIX "orb %1, %0" + :"+m" (lock->tickets.tail) + :"i" (TICKET_SLOWPATH_FLAG ) :"memory" ); +else + asm (LOCK_PREFIX "orw %1, %0" + :"+m" (lock->tickets.tail) + :"i" (TICKET_SLOWPATH_FLAG ) :"memory" ); +}Came only now to mind: Here and elsewhere, did you try using %z0 to have gcc produce the opcode suffix character, rather than having these somewhat ugly if()-s?
Actually in this case I'm pretty sure there's already a "set bit" function which will do the job. set_bit(), I guess, though it takes a bit number rather than a mask...
But, yes, %z0 sounds interesting. Is it documented anywhere? I think I've tried to use it in the past and run into gcc bugs.
Thanks,
J
Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks
In reply to Jan BeulichQuoted 18 lines · Jan Beulich
Quoted 18 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/xen/spinlock.c +4
-4+static void xen_lock_spinning (struct arch_spinlock *lock,unsigned want) { -struct xen_spinlock *xl = (struct xen_spinlock *)lock; -struct xen_spinlock *prev;int irq =__get_cpu_var (lock_kicker_irq); -int ret; +struct xen_lock_waiting *w = &__get_cpu_var (lock_waiting); +int cpu =smp_processor_id ();u64 start;/* If kicker interrupts not initialized yet, just spin */ if (irq ==-1 ) -return 0 ; +return ; start =spin_time_start ();
Quoted 9 lines
arch/x86/xen/spinlock.c static inline u64 spin_time_start(void) · line 112
Quoted 7 lines
arch/x86/xen/spinlock.c +5
-2-/* announce we're spinning */ - prev =spinning_lock (xl); + w->want = want; + w->lock = lock; + +/* This uses set_bit, which atomic and therefore a barrier */ +cpumask_set_cpu (cpu, &waiting_cpus);Since you don't allow nesting, don't you need to disable interrupts before you touch per-CPU state?
Yes, I think you're right - interrupts need to be disabled for the bulk of this function.
J
Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks
In reply to Jan BeulichQuoted 18 lines · Jan Beulich
Quoted 18 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/xen/spinlock.c +4
-4+static void xen_lock_spinning (struct arch_spinlock *lock,unsigned want) { -struct xen_spinlock *xl = (struct xen_spinlock *)lock; -struct xen_spinlock *prev;int irq =__get_cpu_var (lock_kicker_irq); -int ret; +struct xen_lock_waiting *w = &__get_cpu_var (lock_waiting); +int cpu =smp_processor_id ();u64 start;/* If kicker interrupts not initialized yet, just spin */ if (irq ==-1 ) -return 0 ; +return ; start =spin_time_start ();
Quoted 9 lines
arch/x86/xen/spinlock.c static inline u64 spin_time_start(void) · line 112
Quoted 7 lines
arch/x86/xen/spinlock.c +5
-2-/* announce we're spinning */ - prev =spinning_lock (xl); + w->want = want; + w->lock = lock; + +/* This uses set_bit, which atomic and therefore a barrier */ +cpumask_set_cpu (cpu, &waiting_cpus);Since you don't allow nesting, don't you need to disable interrupts before you touch per-CPU state?
Yes, I think you're right - interrupts need to be disabled for the bulk of this function.
J
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeQuoted 2 lines · Jeremy Fitzhardinge
But, yes, %z0 sounds interesting. Is it documented anywhere? I think I've tried to use it in the past and run into gcc bugs.
This one: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39590
Should be OK in this case because there's no 64-bit values to be seen...
J
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeQuoted 2 lines · Jeremy Fitzhardinge
But, yes, %z0 sounds interesting. Is it documented anywhere? I think I've tried to use it in the past and run into gcc bugs.
This one: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39590
Should be OK in this case because there's no 64-bit values to be seen...
J
Quoted 28 lines · Jeremy Fitzhardinge
From: Jeremy Fitzhardinge<[email protected]>
Hi all,
This is a revised version of the pvticket lock series.
The early part of the series is mostly unchanged: it converts the bulk of the ticket lock code into C and makes the "small" and "large" ticket code common. The only changes are the incorporation of various review comments.
The latter part of the series converts from pv spinlocks to pv ticket locks (ie, using the ticket lock fastpath as-is, but adding pv ops for the ticketlock slowpaths).
The significant difference here is that rather than adding a new ticket_t-sized element to
arch_spinlock_t- effectively doubling the size - I steal the LSB of the tickets themselves to store a bit. This allows the structure to remain the same size, but at the cost of halving the max number of CPUs (127 for a 8-bit ticket, and a hard max of 32767 overall).The extra bit (well, two, but one is unused) in indicates whether the lock has gone into "slowpath state", which means one of its lockers has entered its slowpath and has blocked in the hypervisor. This means the current lock-holder needs to make sure it gets kicked out of the hypervisor on unlock.
Quoted 7 lines
The spinlock remains in slowpath state until the last unlock happens (ie there are no more queued lockers).
This code survives for a while with moderate testing, (make -j 100 on 8 VCPUs on a 4 PCPU system), but locks up after about 20 iterations, so there's still some race/deadlock in there (probably something misordered), but I think the basic approach is sound.
This is going to be very useful for kvm; I'd like to see the fixed version gets merged.
Signature · 1 line
error compiling committee.c: too many arguments to function
Quoted 28 lines · Jeremy Fitzhardinge
From: Jeremy Fitzhardinge<[email protected]>
Hi all,
This is a revised version of the pvticket lock series.
The early part of the series is mostly unchanged: it converts the bulk of the ticket lock code into C and makes the "small" and "large" ticket code common. The only changes are the incorporation of various review comments.
The latter part of the series converts from pv spinlocks to pv ticket locks (ie, using the ticket lock fastpath as-is, but adding pv ops for the ticketlock slowpaths).
The significant difference here is that rather than adding a new ticket_t-sized element to
arch_spinlock_t- effectively doubling the size - I steal the LSB of the tickets themselves to store a bit. This allows the structure to remain the same size, but at the cost of halving the max number of CPUs (127 for a 8-bit ticket, and a hard max of 32767 overall).The extra bit (well, two, but one is unused) in indicates whether the lock has gone into "slowpath state", which means one of its lockers has entered its slowpath and has blocked in the hypervisor. This means the current lock-holder needs to make sure it gets kicked out of the hypervisor on unlock.
Quoted 7 lines
The spinlock remains in slowpath state until the last unlock happens (ie there are no more queued lockers).
This code survives for a while with moderate testing, (make -j 100 on 8 VCPUs on a 4 PCPU system), but locks up after about 20 iterations, so there's still some race/deadlock in there (probably something misordered), but I think the basic approach is sound.
This is going to be very useful for kvm; I'd like to see the fixed version gets merged.
Signature · 1 line
error compiling committee.c: too many arguments to function
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeQuoted 13 lines · Jeremy Fitzhardinge
Quoted 12 lines · Jan Beulich
Quoted 12 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
+static inline void
__ticket_enter_slowpath(struct arch_spinlock *lock)+{
+ if (sizeof(lock->tickets.tail)== sizeof(u8))
+ asm (LOCK_PREFIX"orb %1, %0"
+ : "+m" (lock->tickets.tail)
+ : "i" (TICKET_SLOWPATH_FLAG) : "memory");
+ else
+ asm (LOCK_PREFIX"orw %1, %0"
+ : "+m" (lock->tickets.tail)
+ : "i" (TICKET_SLOWPATH_FLAG) : "memory");
+}
Quoted 8 lines
Quoted 3 lines
Came only now to mind: Here and elsewhere, did you try using %z0 to have gcc produce the opcode suffix character, rather than having these somewhat ugly if()-s?
Actually in this case I'm pretty sure there's already a "set bit" function which will do the job.
set_bit(), I guess, though it takes a bit number rather than a mask...
set_bit() operates on a long, while the intel manuals recommend against operating on operands of different size, especially with locked operations. I think newer processors have more relaxed requirements, though.
Signature · 1 line
error compiling committee.c: too many arguments to function
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
Quoted 10 lines · Avi Kivity
Quoted 4 lines
Actually in this case I'm pretty sure there's already a "set bit" function which will do the job.
set_bit(), I guess, though it takes a bit number rather than a mask...
set_bit()operates on a long, while the intel manuals recommend against operating on operands of different size, especially with locked operations. I think newer processors have more relaxed requirements, though.
Despite its prototype, set_bit() is pretty specifically using "orb" for a the constant case, or bts otherwise (I don't know what size memory operation bts is considered to generate).
J
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Avi KivityQuoted 10 lines · Avi Kivity
Quoted 4 lines
Actually in this case I'm pretty sure there's already a "set bit" function which will do the job.
set_bit(), I guess, though it takes a bit number rather than a mask...
set_bit()operates on a long, while the intel manuals recommend against operating on operands of different size, especially with locked operations. I think newer processors have more relaxed requirements, though.
Despite its prototype, set_bit() is pretty specifically using "orb" for a the constant case, or bts otherwise (I don't know what size memory operation bts is considered to generate).
J
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeQuoted 6 lines · Jeremy Fitzhardinge
Quoted 2 lines · Jeremy Fitzhardinge
But, yes, %z0 sounds interesting. Is it documented anywhere? I think I've tried to use it in the past and run into gcc bugs.
This one: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39590
Should be OK in this case because there's no 64-bit values to be seen...
Hm, it fails when __ticket_t is 16 bits:
/home/jeremy/git/linux/arch/x86/include/asm/spinlock.h: Assembler messages:/home/jeremy/git/linux/arch/x86/include/asm/spinlock.h:73: Error: suffix or operands invalid for `or'
lock; ors $1, 2(%rbx) #,
So I don't think that's going to work out...
J
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeQuoted 6 lines · Jeremy Fitzhardinge
Quoted 2 lines · Jeremy Fitzhardinge
But, yes, %z0 sounds interesting. Is it documented anywhere? I think I've tried to use it in the past and run into gcc bugs.
This one: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39590
Should be OK in this case because there's no 64-bit values to be seen...
Hm, it fails when __ticket_t is 16 bits:
/home/jeremy/git/linux/arch/x86/include/asm/spinlock.h: Assembler messages:/home/jeremy/git/linux/arch/x86/include/asm/spinlock.h:73: Error: suffix or operands invalid for `or'
lock; ors $1, 2(%rbx) #,
So I don't think that's going to work out...
J
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeQuoted 7 lines · Jeremy Fitzhardinge
Quoted 6 lines · Avi Kivity
Quoted 4 lines
Actually in this case I'm pretty sure there's already a "set bit" function which will do the job.
set_bit(), I guess, though it takes a bit number rather than a mask...
Quoted 9 lines
Quoted 4 lines
set_bit()operates on a long, while the intel manuals recommend against operating on operands of different size, especially with locked operations. I think newer processors have more relaxed requirements, though.Despite its prototype,
set_bit()is pretty specifically using "orb" for a the constant case, or bts otherwise (I don't know what size memory operation bts is considered to generate).
Perhaps that should be fixed.
bts will take its size from the argument, so it will be a btsq on x86_64. AFAICT, the only visible difference between btsl and btsq is a page fault if the last four bytes of the operand are in an unmapped page.
Signature · 1 line
error compiling committee.c: too many arguments to function
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeQuoted 7 lines · Jeremy Fitzhardinge
Quoted 6 lines · Avi Kivity
Quoted 4 lines
Actually in this case I'm pretty sure there's already a "set bit" function which will do the job.
set_bit(), I guess, though it takes a bit number rather than a mask...
Quoted 9 lines
Quoted 4 lines
set_bit()operates on a long, while the intel manuals recommend against operating on operands of different size, especially with locked operations. I think newer processors have more relaxed requirements, though.Despite its prototype,
set_bit()is pretty specifically using "orb" for a the constant case, or bts otherwise (I don't know what size memory operation bts is considered to generate).
Perhaps that should be fixed.
bts will take its size from the argument, so it will be a btsq on x86_64. AFAICT, the only visible difference between btsl and btsq is a page fault if the last four bytes of the operand are in an unmapped page.
Signature · 1 line
error compiling committee.c: too many arguments to function
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeQuoted 10 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
Quoted 6 lines · Jeremy Fitzhardinge
Quoted 2 lines · Jeremy Fitzhardinge
But, yes, %z0 sounds interesting. Is it documented anywhere? I think I've tried to use it in the past and run into gcc bugs.
This one: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39590
Should be OK in this case because there's no 64-bit values to be seen...
Hm, it fails when
__ticket_tis 16 bits:
Quoted 8 lines
/home/jeremy/git/linux/arch/x86/include/asm/spinlock.h: Assembler messages:/home/jeremy/git/linux/arch/x86/include/asm/spinlock.h:73: Error: suffix or operands invalid for `or'lock; ors $1, 2(%rbx) #,So I don't think that's going to work out...
Indeed, it's only with 4.5 that non-float operands are properly supported here. Sad.
Jan
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeQuoted 10 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
Quoted 6 lines · Jeremy Fitzhardinge
Quoted 2 lines · Jeremy Fitzhardinge
But, yes, %z0 sounds interesting. Is it documented anywhere? I think I've tried to use it in the past and run into gcc bugs.
This one: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39590
Should be OK in this case because there's no 64-bit values to be seen...
Hm, it fails when
__ticket_tis 16 bits:
Quoted 8 lines
/home/jeremy/git/linux/arch/x86/include/asm/spinlock.h: Assembler messages:/home/jeremy/git/linux/arch/x86/include/asm/spinlock.h:73: Error: suffix or operands invalid for `or'lock; ors $1, 2(%rbx) #,So I don't think that's going to work out...
Indeed, it's only with 4.5 that non-float operands are properly supported here. Sad.
Jan
Re: [Xen-devel] Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks
In reply to Jeremy FitzhardingeQuoted 28 lines · Jeremy Fitzhardinge
Quoted 18 lines · Jan Beulich
Quoted 18 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/xen/spinlock.c +4
-4+static void xen_lock_spinning (struct arch_spinlock *lock,unsigned want) { -struct xen_spinlock *xl = (struct xen_spinlock *)lock; -struct xen_spinlock *prev;int irq =__get_cpu_var (lock_kicker_irq); -int ret; +struct xen_lock_waiting *w = &__get_cpu_var (lock_waiting); +int cpu =smp_processor_id ();u64 start;/* If kicker interrupts not initialized yet, just spin */ if (irq ==-1 ) -return 0 ; +return ; start =spin_time_start ();Quoted 9 lines
arch/x86/xen/spinlock.c static inline u64 spin_time_start(void) · line 112
Quoted 7 lines
arch/x86/xen/spinlock.c +5
-2-/* announce we're spinning */ - prev =spinning_lock (xl); + w->want = want; + w->lock = lock; + +/* This uses set_bit, which atomic and therefore a barrier */ +cpumask_set_cpu (cpu, &waiting_cpus);Since you don't allow nesting, don't you need to disable interrupts before you touch per-CPU state?
Quoted 2 lines
Yes, I think you're right - interrupts need to be disabled for the bulk of this function.
Actually, on second thoughts, maybe it doesn't matter so much. The main issue is making sure that the interrupt will make the VCPU drop out of xen_poll_irq() - if it happens before xen_poll_irq(), it should leave the event pending, which will cause the poll to return immediately. I hope. Certainly disabling interrupts for some of the function will make it easier to analyze with respect to interrupt nesting.
Another issue may be making sure the writes and reads of "w->want" and "w->lock" are ordered properly to make sure that xen_unlock_kick() never sees an inconsistent view of the (lock,want) tuple. The risk being that xen_unlock_kick() sees a random, spurious (lock,want) pairing and sends the kick event to the wrong VCPU, leaving the deserving one hung.
J
Re: [Xen-devel] Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks
In reply to Jeremy FitzhardingeQuoted 28 lines · Jeremy Fitzhardinge
Quoted 18 lines · Jan Beulich
Quoted 18 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/xen/spinlock.c +4
-4+static void xen_lock_spinning (struct arch_spinlock *lock,unsigned want) { -struct xen_spinlock *xl = (struct xen_spinlock *)lock; -struct xen_spinlock *prev;int irq =__get_cpu_var (lock_kicker_irq); -int ret; +struct xen_lock_waiting *w = &__get_cpu_var (lock_waiting); +int cpu =smp_processor_id ();u64 start;/* If kicker interrupts not initialized yet, just spin */ if (irq ==-1 ) -return 0 ; +return ; start =spin_time_start ();Quoted 9 lines
arch/x86/xen/spinlock.c static inline u64 spin_time_start(void) · line 112
Quoted 7 lines
arch/x86/xen/spinlock.c +5
-2-/* announce we're spinning */ - prev =spinning_lock (xl); + w->want = want; + w->lock = lock; + +/* This uses set_bit, which atomic and therefore a barrier */ +cpumask_set_cpu (cpu, &waiting_cpus);Since you don't allow nesting, don't you need to disable interrupts before you touch per-CPU state?
Quoted 2 lines
Yes, I think you're right - interrupts need to be disabled for the bulk of this function.
Actually, on second thoughts, maybe it doesn't matter so much. The main issue is making sure that the interrupt will make the VCPU drop out of xen_poll_irq() - if it happens before xen_poll_irq(), it should leave the event pending, which will cause the poll to return immediately. I hope. Certainly disabling interrupts for some of the function will make it easier to analyze with respect to interrupt nesting.
Another issue may be making sure the writes and reads of "w->want" and "w->lock" are ordered properly to make sure that xen_unlock_kick() never sees an inconsistent view of the (lock,want) tuple. The risk being that xen_unlock_kick() sees a random, spurious (lock,want) pairing and sends the kick event to the wrong VCPU, leaving the deserving one hung.
J
Re: [Xen-devel] Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks
In reply to Jeremy FitzhardingeQuoted 33 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
Quoted 28 lines · Jeremy Fitzhardinge
Quoted 18 lines · Jan Beulich
Quoted 18 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/xen/spinlock.c +4
-4+static void xen_lock_spinning (struct arch_spinlock *lock,unsigned want) { -struct xen_spinlock *xl = (struct xen_spinlock *)lock; -struct xen_spinlock *prev;int irq =__get_cpu_var (lock_kicker_irq); -int ret; +struct xen_lock_waiting *w = &__get_cpu_var (lock_waiting); +int cpu =smp_processor_id ();u64 start;/* If kicker interrupts not initialized yet, just spin */ if (irq ==-1 ) -return 0 ; +return ; start =spin_time_start ();Quoted 9 lines
arch/x86/xen/spinlock.c static inline u64 spin_time_start(void) · line 112
Quoted 7 lines
arch/x86/xen/spinlock.c +5
-2-/* announce we're spinning */ - prev =spinning_lock (xl); + w->want = want; + w->lock = lock; + +/* This uses set_bit, which atomic and therefore a barrier */ +cpumask_set_cpu (cpu, &waiting_cpus);Since you don't allow nesting, don't you need to disable interrupts before you touch per-CPU state?
Quoted 2 lines
Yes, I think you're right - interrupts need to be disabled for the bulk of this function.
Quoted 6 lines
Actually, on second thoughts, maybe it doesn't matter so much. The main issue is making sure that the interrupt will make the VCPU drop out of
xen_poll_irq()- if it happens beforexen_poll_irq(), it should leave the event pending, which will cause the poll to return immediately. I hope. Certainly disabling interrupts for some of the function will make it easier to analyze with respect to interrupt nesting.
That's not my main concern. Instead, what if you get interrupted anywhere here, the interrupt handler tries to acquire another spinlock and also has to go into the slow path? It'll overwrite part or all of the outer context's state.
Quoted 5 lines
Another issue may be making sure the writes and reads of "
w->want" and "w->lock" are ordered properly to make sure thatxen_unlock_kick()never sees an inconsistent view of the (lock,want) tuple. The risk being thatxen_unlock_kick()sees a random, spurious (lock,want) pairing and sends the kick event to the wrong VCPU, leaving the deserving one hung.
Yes, proper operation sequence (and barriers) is certainly required here. If you allowed nesting, this may even become simpler (as you'd have a single write making visible the new "head" pointer, after having written all relevant fields of the new "head" structure).
Jan
Re: [Xen-devel] Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks
In reply to Jeremy FitzhardingeQuoted 33 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
Quoted 28 lines · Jeremy Fitzhardinge
Quoted 18 lines · Jan Beulich
Quoted 18 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/xen/spinlock.c +4
-4+static void xen_lock_spinning (struct arch_spinlock *lock,unsigned want) { -struct xen_spinlock *xl = (struct xen_spinlock *)lock; -struct xen_spinlock *prev;int irq =__get_cpu_var (lock_kicker_irq); -int ret; +struct xen_lock_waiting *w = &__get_cpu_var (lock_waiting); +int cpu =smp_processor_id ();u64 start;/* If kicker interrupts not initialized yet, just spin */ if (irq ==-1 ) -return 0 ; +return ; start =spin_time_start ();Quoted 9 lines
arch/x86/xen/spinlock.c static inline u64 spin_time_start(void) · line 112
Quoted 7 lines
arch/x86/xen/spinlock.c +5
-2-/* announce we're spinning */ - prev =spinning_lock (xl); + w->want = want; + w->lock = lock; + +/* This uses set_bit, which atomic and therefore a barrier */ +cpumask_set_cpu (cpu, &waiting_cpus);Since you don't allow nesting, don't you need to disable interrupts before you touch per-CPU state?
Quoted 2 lines
Yes, I think you're right - interrupts need to be disabled for the bulk of this function.
Quoted 6 lines
Actually, on second thoughts, maybe it doesn't matter so much. The main issue is making sure that the interrupt will make the VCPU drop out of
xen_poll_irq()- if it happens beforexen_poll_irq(), it should leave the event pending, which will cause the poll to return immediately. I hope. Certainly disabling interrupts for some of the function will make it easier to analyze with respect to interrupt nesting.
That's not my main concern. Instead, what if you get interrupted anywhere here, the interrupt handler tries to acquire another spinlock and also has to go into the slow path? It'll overwrite part or all of the outer context's state.
Quoted 5 lines
Another issue may be making sure the writes and reads of "
w->want" and "w->lock" are ordered properly to make sure thatxen_unlock_kick()never sees an inconsistent view of the (lock,want) tuple. The risk being thatxen_unlock_kick()sees a random, spurious (lock,want) pairing and sends the kick event to the wrong VCPU, leaving the deserving one hung.
Yes, proper operation sequence (and barriers) is certainly required here. If you allowed nesting, this may even become simpler (as you'd have a single write making visible the new "head" pointer, after having written all relevant fields of the new "head" structure).
Jan
Peter Zijlstra
maintainerRe: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeQuoted 4 lines · Jeremy Fitzhardinge
Maintain a flag in both LSBs of the ticket lock which indicates whether anyone is in the lock slowpath and may need kicking when the current holder unlocks. The flags are set when the first locker enters the slowpath, and cleared when unlocking to an empty queue.
So here you say you set both LSBs in order to keep head == tail working, but the code seems to suggest you only use the tail LSB.
I think I see why using only one LSB is sufficient, but some consistency would be nice :-)
Peter Zijlstra
maintainerRe: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeQuoted 4 lines · Jeremy Fitzhardinge
Maintain a flag in both LSBs of the ticket lock which indicates whether anyone is in the lock slowpath and may need kicking when the current holder unlocks. The flags are set when the first locker enters the slowpath, and cleared when unlocking to an empty queue.
So here you say you set both LSBs in order to keep head == tail working, but the code seems to suggest you only use the tail LSB.
I think I see why using only one LSB is sufficient, but some consistency would be nice :-)
Re: [Xen-devel] Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Peter ZijlstraQuoted 10 lines · Peter Zijlstra
Quoted 4 lines · Jeremy Fitzhardinge
Maintain a flag in both LSBs of the ticket lock which indicates whether anyone is in the lock slowpath and may need kicking when the current holder unlocks. The flags are set when the first locker enters the slowpath, and cleared when unlocking to an empty queue.
So here you say you set both LSBs in order to keep head == tail working, but the code seems to suggest you only use the tail LSB.
I think I see why using only one LSB is sufficient, but some consistency would be nice :-)
I tried that initially, but it turned out more messy. The problem is that the flag can change while you're spinning on the lock, so you need to mask it out every time you read tail before you can compare it to head; if head has the flag set too, you just need to mask it out of there as well:
ticket = xadd(lock, 2 << TICKET_SHIFT);
ticket.tail &= ~TICKET_SLOW_FLAGS;
while (ticket.head != ticket.tail) {
relax();
ticket.head = lock->head /* & ~TICKET_SLOW_FLAGS */;
}IOW setting both doesn't help anything, and just requires an extra mask in the spin loop (and anywhere else that uses 'head').
And hey, extra bit. Bound to be useful for something.
J
Re: [Xen-devel] Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Peter ZijlstraQuoted 10 lines · Peter Zijlstra
Quoted 4 lines · Jeremy Fitzhardinge
Maintain a flag in both LSBs of the ticket lock which indicates whether anyone is in the lock slowpath and may need kicking when the current holder unlocks. The flags are set when the first locker enters the slowpath, and cleared when unlocking to an empty queue.
So here you say you set both LSBs in order to keep head == tail working, but the code seems to suggest you only use the tail LSB.
I think I see why using only one LSB is sufficient, but some consistency would be nice :-)
I tried that initially, but it turned out more messy. The problem is that the flag can change while you're spinning on the lock, so you need to mask it out every time you read tail before you can compare it to head; if head has the flag set too, you just need to mask it out of there as well:
ticket = xadd(lock, 2 << TICKET_SHIFT);
ticket.tail &= ~TICKET_SLOW_FLAGS;
while (ticket.head != ticket.tail) {
relax();
ticket.head = lock->head /* & ~TICKET_SLOW_FLAGS */;
}IOW setting both doesn't help anything, and just requires an extra mask in the spin loop (and anywhere else that uses 'head').
And hey, extra bit. Bound to be useful for something.
J
Re: [Xen-devel] Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks
In reply to Jan BeulichQuoted 10 lines · Jan Beulich
Quoted 6 lines
Actually, on second thoughts, maybe it doesn't matter so much. The main issue is making sure that the interrupt will make the VCPU drop out of
xen_poll_irq()- if it happens beforexen_poll_irq(), it should leave the event pending, which will cause the poll to return immediately. I hope. Certainly disabling interrupts for some of the function will make it easier to analyze with respect to interrupt nesting.That's not my main concern. Instead, what if you get interrupted anywhere here, the interrupt handler tries to acquire another spinlock and also has to go into the slow path? It'll overwrite part or all of the outer context's state.
That doesn't matter if the outer context doesn't end up blocking. If it has already blocked then it will unblock as a result of the interrupt; if it hasn't yet blocked, then the inner context will leave the event pending and cause it to not block. Either way, it no longer uses or needs that per-cpu state: it will return to the spin loop and (maybe) get re-entered, setting it all up again.
I think there is a problem with the code as posted because it sets up the percpu data before clearing the pending event, so it can end up blocking with bad percpu data.
Quoted 10 lines
Quoted 5 lines
Another issue may be making sure the writes and reads of "
w->want" and "w->lock" are ordered properly to make sure thatxen_unlock_kick()never sees an inconsistent view of the (lock,want) tuple. The risk being thatxen_unlock_kick()sees a random, spurious (lock,want) pairing and sends the kick event to the wrong VCPU, leaving the deserving one hung.Yes, proper operation sequence (and barriers) is certainly required here. If you allowed nesting, this may even become simpler (as you'd have a single write making visible the new "head" pointer, after having written all relevant fields of the new "head" structure).
Yes, simple nesting should be quite straightforward (ie allowing an interrupt handler to take some other lock than the one the outer context is waiting on).
J
Re: [Xen-devel] Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks
In reply to Jan BeulichQuoted 10 lines · Jan Beulich
Quoted 6 lines
Actually, on second thoughts, maybe it doesn't matter so much. The main issue is making sure that the interrupt will make the VCPU drop out of
xen_poll_irq()- if it happens beforexen_poll_irq(), it should leave the event pending, which will cause the poll to return immediately. I hope. Certainly disabling interrupts for some of the function will make it easier to analyze with respect to interrupt nesting.That's not my main concern. Instead, what if you get interrupted anywhere here, the interrupt handler tries to acquire another spinlock and also has to go into the slow path? It'll overwrite part or all of the outer context's state.
That doesn't matter if the outer context doesn't end up blocking. If it has already blocked then it will unblock as a result of the interrupt; if it hasn't yet blocked, then the inner context will leave the event pending and cause it to not block. Either way, it no longer uses or needs that per-cpu state: it will return to the spin loop and (maybe) get re-entered, setting it all up again.
I think there is a problem with the code as posted because it sets up the percpu data before clearing the pending event, so it can end up blocking with bad percpu data.
Quoted 10 lines
Quoted 5 lines
Another issue may be making sure the writes and reads of "
w->want" and "w->lock" are ordered properly to make sure thatxen_unlock_kick()never sees an inconsistent view of the (lock,want) tuple. The risk being thatxen_unlock_kick()sees a random, spurious (lock,want) pairing and sends the kick event to the wrong VCPU, leaving the deserving one hung.Yes, proper operation sequence (and barriers) is certainly required here. If you allowed nesting, this may even become simpler (as you'd have a single write making visible the new "head" pointer, after having written all relevant fields of the new "head" structure).
Yes, simple nesting should be quite straightforward (ie allowing an interrupt handler to take some other lock than the one the outer context is waiting on).
J
Re: [Xen-devel] [PATCH 01/14] x86/ticketlock: clean up types and accessors
In reply to Jeremy Fitzhardingearch/x86/include/asm/spinlock.h static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock) · line 161
Quoted 7 lines
static inline int
__ticket_spin_is_locked(arch_spinlock_t *lock){arch/x86/include/asm/spinlock.h +2
-2-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);
Does it make sense to mask it here it here with TICKET_MASK as it was done before?
Re: [Xen-devel] [PATCH 01/14] x86/ticketlock: clean up types and accessors
In reply to Jeremy Fitzhardingearch/x86/include/asm/spinlock.h static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock) · line 161
Quoted 7 lines
static inline int
__ticket_spin_is_locked(arch_spinlock_t *lock){arch/x86/include/asm/spinlock.h +2
-2-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);
Does it make sense to mask it here it here with TICKET_MASK as it was done before?
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeQuoted 22 lines · Jeremy Fitzhardinge
From: Jeremy Fitzhardinge <[email protected]>
Maintain a flag in both LSBs of the ticket lock which indicates whether anyone is in the lock slowpath and may need kicking when the current holder unlocks. The flags are set when the first locker enters the slowpath, and cleared when unlocking to an empty queue.
In the specific implementation of
lock_spinning(), make sure to set the slowpath flags on the lock just before blocking. We must do this before the last-chance pickup test to prevent a deadlock with the unlocker:Unlocker Locker
test for lock pickup -> fail test slowpath + unlock -> false set slowpath flags blockWhereas this works in any ordering:
Quoted 7 lines
Unlocker Locker
set slowpath flags test for lock pickup
-> fail
block
test slowpath + unlock-> true, kick
I think this is still racy ..
Unlocker Locker
test slowpath
-> false set slowpath flag test for lock pickup -> fail block
unlock
unlock needs to happen first before testing slowpath? I have made that change for my KVM guest and it seems to be working well with that change .. Will cleanup and post my patches shortly
- vatsa
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeQuoted 22 lines · Jeremy Fitzhardinge
From: Jeremy Fitzhardinge <[email protected]>
Maintain a flag in both LSBs of the ticket lock which indicates whether anyone is in the lock slowpath and may need kicking when the current holder unlocks. The flags are set when the first locker enters the slowpath, and cleared when unlocking to an empty queue.
In the specific implementation of
lock_spinning(), make sure to set the slowpath flags on the lock just before blocking. We must do this before the last-chance pickup test to prevent a deadlock with the unlocker:Unlocker Locker
test for lock pickup -> fail test slowpath + unlock -> false set slowpath flags blockWhereas this works in any ordering:
Quoted 7 lines
Unlocker Locker
set slowpath flags test for lock pickup
-> fail
block
test slowpath + unlock-> true, kick
I think this is still racy ..
Unlocker Locker
test slowpath
-> false set slowpath flag test for lock pickup -> fail block
unlock
unlock needs to happen first before testing slowpath? I have made that change for my KVM guest and it seems to be working well with that change .. Will cleanup and post my patches shortly
- vatsa
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Srivatsa VaddagiriQuoted 14 lines · Srivatsa Vaddagiri
I think this is still racy ..
Unlocker Locker
test slowpath
-> false set slowpath flag test for lock pickup -> fail block
Quoted 5 lines
unlock
unlock needs to happen first before testing slowpath? I have made that change for my KVM guest and it seems to be working well with that change .. Will cleanup and post my patches shortly
Patch below fixes the race described above. You can fold this to your patch 13/14 if you agree this is in right direction.
--- arch/x86/include/asm/spinlock.h | 7 +++---- arch/x86/kernel/paravirt-spinlocks.c | 22 +++++----------------- 2 files changed, 8 insertions(+), 21 deletions(-)
arch/x86/include/asm/spinlock.h +3 -4
@@ -55,7 +55,7 @@ static __always_inline void __ticket_unl/* Only defined when CONFIG_PARAVIRT_SPINLOCKS defined, but may as * well leave the prototype always visible. */ -extern void __ticket_unlock_release_slowpath (struct arch_spinlock *lock); +extern void __ticket_unlock_slowpath (struct arch_spinlock *lock);#ifdef CONFIG_PARAVIRT_SPINLOCKS
@@ -166,10 +166,9 @@ static __always_inline int arch_spin_try static __always_inline void arch_spin_unlock(arch_spinlock_t *lock) {barrier ();/* prevent reordering out of locked region */ +__ticket_unlock_release (lock);if (unlikely (__ticket_in_slowpath (lock))) -__ticket_unlock_release_slowpath (lock); -else -__ticket_unlock_release (lock); +__ticket_unlock_slowpath (lock);barrier ();/* prevent reordering into locked region */ }
arch/x86/kernel/paravirt-spinlocks.c +5 -17
@@ -22,33 +22,21 @@ EXPORT_SYMBOL(pv_lock_ops);* bits. However, we need to be careful about this because someone * may just be entering as we leave, and enter the slowpath. */ -void __ticket_unlock_release_slowpath (struct arch_spinlock *lock) +void __ticket_unlock_slowpath (struct arch_spinlock *lock) {struct arch_spinlock old, new;BUILD_BUG_ON (((__ticket_t )NR_CPUS ) !=NR_CPUS ); old =ACCESS_ONCE (*lock); - new = old; - new.tickets.head +=TICKET_LOCK_INC ;/* Clear the slowpath flag */ new.tickets.tail &= ~TICKET_SLOWPATH_FLAG ; +if (new.tickets.head == new.tickets.tail) +cmpxchg (&lock->head_tail, old.head_tail, new.head_tail); -/* -* If there's currently people waiting or someone snuck in -* since we read the lock above, then do a normal unlock and -* kick. If we managed to unlock with no queued waiters, then -* we can clear the slowpath flag. -*/ -if (new.tickets.head != new.tickets.tail || -cmpxchg (&lock->head_tail, - old.head_tail, new.head_tail) != old.head_tail) { -/* still people waiting */ -__ticket_unlock_release (lock); - } - +/* Wake up an appropriate waiter */ __ticket_unlock_kick (lock, new.tickets.head); } -EXPORT_SYMBOL (__ticket_unlock_release_slowpath); +EXPORT_SYMBOL (__ticket_unlock_slowpath);
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Srivatsa VaddagiriQuoted 14 lines · Srivatsa Vaddagiri
I think this is still racy ..
Unlocker Locker
test slowpath
-> false set slowpath flag test for lock pickup -> fail block
Quoted 5 lines
unlock
unlock needs to happen first before testing slowpath? I have made that change for my KVM guest and it seems to be working well with that change .. Will cleanup and post my patches shortly
Patch below fixes the race described above. You can fold this to your patch 13/14 if you agree this is in right direction.
--- arch/x86/include/asm/spinlock.h | 7 +++---- arch/x86/kernel/paravirt-spinlocks.c | 22 +++++----------------- 2 files changed, 8 insertions(+), 21 deletions(-)
arch/x86/include/asm/spinlock.h +3 -4
@@ -55,7 +55,7 @@ static __always_inline void __ticket_unl/* Only defined when CONFIG_PARAVIRT_SPINLOCKS defined, but may as * well leave the prototype always visible. */ -extern void __ticket_unlock_release_slowpath (struct arch_spinlock *lock); +extern void __ticket_unlock_slowpath (struct arch_spinlock *lock);#ifdef CONFIG_PARAVIRT_SPINLOCKS
@@ -166,10 +166,9 @@ static __always_inline int arch_spin_try static __always_inline void arch_spin_unlock(arch_spinlock_t *lock) {barrier ();/* prevent reordering out of locked region */ +__ticket_unlock_release (lock);if (unlikely (__ticket_in_slowpath (lock))) -__ticket_unlock_release_slowpath (lock); -else -__ticket_unlock_release (lock); +__ticket_unlock_slowpath (lock);barrier ();/* prevent reordering into locked region */ }
arch/x86/kernel/paravirt-spinlocks.c +5 -17
@@ -22,33 +22,21 @@ EXPORT_SYMBOL(pv_lock_ops);* bits. However, we need to be careful about this because someone * may just be entering as we leave, and enter the slowpath. */ -void __ticket_unlock_release_slowpath (struct arch_spinlock *lock) +void __ticket_unlock_slowpath (struct arch_spinlock *lock) {struct arch_spinlock old, new;BUILD_BUG_ON (((__ticket_t )NR_CPUS ) !=NR_CPUS ); old =ACCESS_ONCE (*lock); - new = old; - new.tickets.head +=TICKET_LOCK_INC ;/* Clear the slowpath flag */ new.tickets.tail &= ~TICKET_SLOWPATH_FLAG ; +if (new.tickets.head == new.tickets.tail) +cmpxchg (&lock->head_tail, old.head_tail, new.head_tail); -/* -* If there's currently people waiting or someone snuck in -* since we read the lock above, then do a normal unlock and -* kick. If we managed to unlock with no queued waiters, then -* we can clear the slowpath flag. -*/ -if (new.tickets.head != new.tickets.tail || -cmpxchg (&lock->head_tail, - old.head_tail, new.head_tail) != old.head_tail) { -/* still people waiting */ -__ticket_unlock_release (lock); - } - +/* Wake up an appropriate waiter */ __ticket_unlock_kick (lock, new.tickets.head); } -EXPORT_SYMBOL (__ticket_unlock_release_slowpath); +EXPORT_SYMBOL (__ticket_unlock_slowpath);
Quoted 5 lines · Jeremy Fitzhardinge
From: Jeremy Fitzhardinge <[email protected]>
Hi all,
This is a revised version of the pvticket lock series.
The 3-patch series to follow this email extends KVM-hypervisor and Linux guest running on KVM-hypervisor to support pv-ticket spinlocks.
Two hypercalls are being introduced in KVM hypervisor, one that allows a vcpu (spinning on a lock) to block and another that allows a vcpu to kick another out of blocking state.
Patches are against 2.6.37 mainline kernel. I also don't yet have numbers at this time to show benefit of pv-ticketlocks - I would think the benefit should be similar across hypervisors (Xen and KVM in this case).
- vatsa
Quoted 5 lines · Jeremy Fitzhardinge
From: Jeremy Fitzhardinge <[email protected]>
Hi all,
This is a revised version of the pvticket lock series.
The 3-patch series to follow this email extends KVM-hypervisor and Linux guest running on KVM-hypervisor to support pv-ticket spinlocks.
Two hypercalls are being introduced in KVM hypervisor, one that allows a vcpu (spinning on a lock) to block and another that allows a vcpu to kick another out of blocking state.
Patches are against 2.6.37 mainline kernel. I also don't yet have numbers at this time to show benefit of pv-ticketlocks - I would think the benefit should be similar across hypervisors (Xen and KVM in this case).
- vatsa
PATCH 1/3 debugfs: Add support to print u32 array
In reply to Srivatsa VaddagiriAdd debugfs support to print u32-arrays.
Most of this comes from Xen-hypervisor sources, which has been refactored to make the code common for other users as well.
--- arch/x86/xen/debugfs.c | 104 -------------------------------------------- arch/x86/xen/debugfs.h | 4 - arch/x86/xen/mmu.c | 2 arch/x86/xen/multicalls.c | 6 +- arch/x86/xen/spinlock.c | 2 fs/debugfs/file.c | 108 ++++++++++++++++++++++++++++++++++++++++++++++ include/linux/debugfs.h | 11 ++++ 7 files changed, 124 insertions(+), 113 deletions(-)
arch/x86/xen/debugfs.c +0 -104
@@ -19,107 +19,3 @@ struct dentry * __init xen_init_debugfs(return d_xen_debug; } -struct array_data -{ -void *array; -unsigned elements; -}; - -static int u32_array_open (struct inode *inode,struct file *file) -{ - file->private_data =NULL ; -return nonseekable_open (inode, file); -} - -static size_t format_array (char *buf,size_t bufsize,const char *fmt, -u32 *array,unsigned array_size) -{ -size_t ret =0 ; -unsigned i; - -for (i =0 ; i < array_size; i++) { -size_t len; - - len =snprintf (buf, bufsize, fmt, array[i]); - len++;/* ' ' or '\n' */ - ret += len; - -if (buf) { - buf += len; - bufsize -= len; - buf[-1 ] = (i == array_size-1 ) ?'\n' :' ' ; - } - } - - ret++;/* \0 */ -if (buf) - *buf ='\0' ; - -return ret; -} - -static char *format_array_alloc (const char *fmt,u32 *array,unsigned array_size) -{ -size_t len =format_array (NULL ,0 , fmt, array, array_size); -char *ret; - - ret =kmalloc (len,GFP_KERNEL ); -if (ret ==NULL ) -return NULL ; - -format_array (ret, len, fmt, array, array_size); -return ret; -} - -static ssize_t u32_array_read (struct file *file,char __user *buf,size_t len, -loff_t *ppos) -{ -struct inode *inode = file->f_path.dentry->d_inode; -struct array_data *data = inode->i_private; -size_t size; - -if (*ppos ==0 ) { -if (file->private_data) { -kfree (file->private_data); - file->private_data =NULL ; - } - - file->private_data =format_array_alloc ("%u" , data->array, data->elements); - } - - size =0 ; -if (file->private_data) - size =strlen (file->private_data); - -return simple_read_from_buffer (buf, len, ppos, file->private_data, size); -} - -static int xen_array_release (struct inode *inode,struct file *file) -{ -kfree (file->private_data); - -return 0 ; -} - -static const struct file_operations u32_array_fops = { - .owner =THIS_MODULE , - .open = u32_array_open, - .release= xen_array_release, - .read = u32_array_read, - .llseek = no_llseek, -}; - -struct dentry *xen_debugfs_create_u32_array (const char *name,mode_t mode, -struct dentry *parent, -u32 *array,unsigned elements) -{ -struct array_data *data =kmalloc (sizeof (*data),GFP_KERNEL ); - -if (data ==NULL ) -return NULL ; - - data->array = array; - data->elements = elements; - -return debugfs_create_file (name, mode, parent, data, &u32_array_fops); -}
arch/x86/xen/debugfs.h +0 -4
@@ -3,8 +3,4 @@struct dentry *__init xen_init_debugfs (void ); -struct dentry *xen_debugfs_create_u32_array (const char *name,mode_t mode, -struct dentry *parent, -u32 *array,unsigned elements); -#endif /* _XEN_DEBUGFS_H */
arch/x86/xen/mmu.c +1 -1
@@ -2757,7 +2757,7 @@ static int __init xen_mmu_debugfs(void)debugfs_create_u32 ("mmu_update" ,0444 , d_mmu_debug, &mmu_stats.mmu_update);debugfs_create_u32 ("mmu_update_extended" ,0444 , d_mmu_debug, &mmu_stats.mmu_update_extended); -xen_debugfs_create_u32_array ("mmu_update_histo" ,0444 , d_mmu_debug, +debugfs_create_u32_array ("mmu_update_histo" ,0444 , d_mmu_debug, mmu_stats.mmu_update_histo,20 );debugfs_create_u32 ("set_pte_at" ,0444 , d_mmu_debug, &mmu_stats.set_pte_at);
arch/x86/xen/multicalls.c +3 -3
@@ -269,11 +269,11 @@ static int __init xen_mc_debugfs(void)debugfs_create_u32 ("hypercalls" ,0444 , d_mc_debug, &mc_stats.hypercalls);debugfs_create_u32 ("arg_total" ,0444 , d_mc_debug, &mc_stats.arg_total); -xen_debugfs_create_u32_array ("batch_histo" ,0444 , d_mc_debug, +debugfs_create_u32_array ("batch_histo" ,0444 , d_mc_debug, mc_stats.histo,MC_BATCH ); -xen_debugfs_create_u32_array ("hypercall_histo" ,0444 , d_mc_debug, +debugfs_create_u32_array ("hypercall_histo" ,0444 , d_mc_debug, mc_stats.histo_hypercalls,NHYPERCALLS ); -xen_debugfs_create_u32_array ("flush_reasons" ,0444 , d_mc_debug, +debugfs_create_u32_array ("flush_reasons" ,0444 , d_mc_debug, mc_stats.flush,FL_N_REASONS );return 0 ;
arch/x86/xen/spinlock.c +1 -1
@@ -228,7 +228,7 @@ static int __init xen_spinlock_debugfs(vdebugfs_create_u64 ("time_blocked" ,0444 , d_spin_debug, &spinlock_stats.time_blocked); -xen_debugfs_create_u32_array ("histo_blocked" ,0444 , d_spin_debug, +debugfs_create_u32_array ("histo_blocked" ,0444 , d_spin_debug, spinlock_stats.histo_spin_blocked,HISTO_BUCKETS +1 );return 0 ;
fs/debugfs/file.c +108 -0
117 lines not on this page · raw message
include/linux/debugfs.h +11 -0
@@ -74,6 +74,10 @@ struct dentry *debugfs_create_blob(conststruct dentry *parent, struct debugfs_blob_wrapper *blob); +struct dentry *debugfs_create_u32_array (const char *name,mode_t mode, +struct dentry *parent, +u32 *array,unsigned elements); +bool debugfs_initialized (void );#else
@@ -187,6 +191,13 @@ static inline struct dentry *debugfs_cre {return ERR_PTR (-ENODEV ); } + +struct dentry *debugfs_create_u32_array (const char *name,mode_t mode, +struct dentry *parent, +u32 *array,unsigned elements) +{ +return ERR_PTR (-ENODEV ); +}static inline bool debugfs_initialized (void ) {
PATCH 1/3 debugfs: Add support to print u32 array
In reply to Srivatsa VaddagiriAdd debugfs support to print u32-arrays.
Most of this comes from Xen-hypervisor sources, which has been refactored to make the code common for other users as well.
--- arch/x86/xen/debugfs.c | 104 -------------------------------------------- arch/x86/xen/debugfs.h | 4 - arch/x86/xen/mmu.c | 2 arch/x86/xen/multicalls.c | 6 +- arch/x86/xen/spinlock.c | 2 fs/debugfs/file.c | 108 ++++++++++++++++++++++++++++++++++++++++++++++ include/linux/debugfs.h | 11 ++++ 7 files changed, 124 insertions(+), 113 deletions(-)
arch/x86/xen/debugfs.c +0 -104
@@ -19,107 +19,3 @@ struct dentry * __init xen_init_debugfs(return d_xen_debug; } -struct array_data -{ -void *array; -unsigned elements; -}; - -static int u32_array_open (struct inode *inode,struct file *file) -{ - file->private_data =NULL ; -return nonseekable_open (inode, file); -} - -static size_t format_array (char *buf,size_t bufsize,const char *fmt, -u32 *array,unsigned array_size) -{ -size_t ret =0 ; -unsigned i; - -for (i =0 ; i < array_size; i++) { -size_t len; - - len =snprintf (buf, bufsize, fmt, array[i]); - len++;/* ' ' or '\n' */ - ret += len; - -if (buf) { - buf += len; - bufsize -= len; - buf[-1 ] = (i == array_size-1 ) ?'\n' :' ' ; - } - } - - ret++;/* \0 */ -if (buf) - *buf ='\0' ; - -return ret; -} - -static char *format_array_alloc (const char *fmt,u32 *array,unsigned array_size) -{ -size_t len =format_array (NULL ,0 , fmt, array, array_size); -char *ret; - - ret =kmalloc (len,GFP_KERNEL ); -if (ret ==NULL ) -return NULL ; - -format_array (ret, len, fmt, array, array_size); -return ret; -} - -static ssize_t u32_array_read (struct file *file,char __user *buf,size_t len, -loff_t *ppos) -{ -struct inode *inode = file->f_path.dentry->d_inode; -struct array_data *data = inode->i_private; -size_t size; - -if (*ppos ==0 ) { -if (file->private_data) { -kfree (file->private_data); - file->private_data =NULL ; - } - - file->private_data =format_array_alloc ("%u" , data->array, data->elements); - } - - size =0 ; -if (file->private_data) - size =strlen (file->private_data); - -return simple_read_from_buffer (buf, len, ppos, file->private_data, size); -} - -static int xen_array_release (struct inode *inode,struct file *file) -{ -kfree (file->private_data); - -return 0 ; -} - -static const struct file_operations u32_array_fops = { - .owner =THIS_MODULE , - .open = u32_array_open, - .release= xen_array_release, - .read = u32_array_read, - .llseek = no_llseek, -}; - -struct dentry *xen_debugfs_create_u32_array (const char *name,mode_t mode, -struct dentry *parent, -u32 *array,unsigned elements) -{ -struct array_data *data =kmalloc (sizeof (*data),GFP_KERNEL ); - -if (data ==NULL ) -return NULL ; - - data->array = array; - data->elements = elements; - -return debugfs_create_file (name, mode, parent, data, &u32_array_fops); -}
arch/x86/xen/debugfs.h +0 -4
@@ -3,8 +3,4 @@struct dentry *__init xen_init_debugfs (void ); -struct dentry *xen_debugfs_create_u32_array (const char *name,mode_t mode, -struct dentry *parent, -u32 *array,unsigned elements); -#endif /* _XEN_DEBUGFS_H */
arch/x86/xen/mmu.c +1 -1
@@ -2757,7 +2757,7 @@ static int __init xen_mmu_debugfs(void)debugfs_create_u32 ("mmu_update" ,0444 , d_mmu_debug, &mmu_stats.mmu_update);debugfs_create_u32 ("mmu_update_extended" ,0444 , d_mmu_debug, &mmu_stats.mmu_update_extended); -xen_debugfs_create_u32_array ("mmu_update_histo" ,0444 , d_mmu_debug, +debugfs_create_u32_array ("mmu_update_histo" ,0444 , d_mmu_debug, mmu_stats.mmu_update_histo,20 );debugfs_create_u32 ("set_pte_at" ,0444 , d_mmu_debug, &mmu_stats.set_pte_at);
arch/x86/xen/multicalls.c +3 -3
@@ -269,11 +269,11 @@ static int __init xen_mc_debugfs(void)debugfs_create_u32 ("hypercalls" ,0444 , d_mc_debug, &mc_stats.hypercalls);debugfs_create_u32 ("arg_total" ,0444 , d_mc_debug, &mc_stats.arg_total); -xen_debugfs_create_u32_array ("batch_histo" ,0444 , d_mc_debug, +debugfs_create_u32_array ("batch_histo" ,0444 , d_mc_debug, mc_stats.histo,MC_BATCH ); -xen_debugfs_create_u32_array ("hypercall_histo" ,0444 , d_mc_debug, +debugfs_create_u32_array ("hypercall_histo" ,0444 , d_mc_debug, mc_stats.histo_hypercalls,NHYPERCALLS ); -xen_debugfs_create_u32_array ("flush_reasons" ,0444 , d_mc_debug, +debugfs_create_u32_array ("flush_reasons" ,0444 , d_mc_debug, mc_stats.flush,FL_N_REASONS );return 0 ;
arch/x86/xen/spinlock.c +1 -1
@@ -228,7 +228,7 @@ static int __init xen_spinlock_debugfs(vdebugfs_create_u64 ("time_blocked" ,0444 , d_spin_debug, &spinlock_stats.time_blocked); -xen_debugfs_create_u32_array ("histo_blocked" ,0444 , d_spin_debug, +debugfs_create_u32_array ("histo_blocked" ,0444 , d_spin_debug, spinlock_stats.histo_spin_blocked,HISTO_BUCKETS +1 );return 0 ;
fs/debugfs/file.c +108 -0
117 lines not on this page · raw message
include/linux/debugfs.h +11 -0
@@ -74,6 +74,10 @@ struct dentry *debugfs_create_blob(conststruct dentry *parent, struct debugfs_blob_wrapper *blob); +struct dentry *debugfs_create_u32_array (const char *name,mode_t mode, +struct dentry *parent, +u32 *array,unsigned elements); +bool debugfs_initialized (void );#else
@@ -187,6 +191,13 @@ static inline struct dentry *debugfs_cre {return ERR_PTR (-ENODEV ); } + +struct dentry *debugfs_create_u32_array (const char *name,mode_t mode, +struct dentry *parent, +u32 *array,unsigned elements) +{ +return ERR_PTR (-ENODEV ); +}static inline bool debugfs_initialized (void ) {
PATCH 2/3 kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Srivatsa VaddagiriAdd two hypercalls to KVM hypervisor to support pv-ticketlocks.
KVM_HC_WAIT_FOR_KICK blocks the calling vcpu until another vcpu kicks it or it is woken up because of an event like interrupt.
KVM_HC_KICK_CPU allows the calling vcpu to kick another vcpu.
The presence of these hypercalls is indicated to guest via KVM_FEATURE_WAIT_FOR_KICK/KVM_CAP_WAIT_FOR_KICK. Qemu needs a corresponding patch to pass up the presence of this feature to guest via cpuid. Patch to qemu will be sent separately.
--- arch/x86/include/asm/kvm_para.h | 2 + arch/x86/kvm/x86.c | 69 +++++++++++++++++++++++++++++++++++++++- include/linux/kvm.h | 1 include/linux/kvm_host.h | 1 include/linux/kvm_para.h | 2 + virt/kvm/kvm_main.c | 1 6 files changed, 75 insertions(+), 1 deletion(-)
arch/x86/include/asm/kvm_para.h +2 -0
@@ -16,6 +16,8 @@#define KVM_FEATURE_CLOCKSOURCE 0#define KVM_FEATURE_NOP_IO_DELAY 1#define KVM_FEATURE_MMU_OP 2 +#define KVM_FEATURE_WAIT_FOR_KICK 4 +/* This indicates that the new set of kvmclock msrs * are available. The use of 0x11 and 0x12 is deprecated */
arch/x86/kvm/x86.c +68 -1
93 lines not on this page · raw message
include/linux/kvm.h +1 -0
@@ -540,6 +540,7 @@ struct kvm_ppc_pvinfo {#endif #define KVM_CAP_PPC_GET_PVINFO 57#define KVM_CAP_PPC_IRQ_LEVEL 58 +#define KVM_CAP_WAIT_FOR_KICK 59#ifdef KVM_CAP_IRQ_ROUTING
include/linux/kvm_host.h +1 -0
@@ -105,6 +105,7 @@ struct kvm_vcpu {#endif struct kvm_vcpu_arch arch; +int kicked; };/*
include/linux/kvm_para.h +2 -0
@@ -19,6 +19,8 @@#define KVM_HC_MMU_OP 2#define KVM_HC_FEATURES 3#define KVM_HC_PPC_MAP_MAGIC_PAGE 4 +#define KVM_HC_WAIT_FOR_KICK 5 +#define KVM_HC_KICK_CPU 6/* * hypercalls use architecture specific
virt/kvm/kvm_main.c +1 -0
@@ -185,6 +185,7 @@ int kvm_vcpu_init(struct kvm_vcpu *vcpu, vcpu->cpu =-1 ; vcpu->kvm = kvm; vcpu->vcpu_id = id; + vcpu->kicked =0 ;init_waitqueue_head (&vcpu->wq); page =alloc_page (GFP_KERNEL | __GFP_ZERO);
PATCH 2/3 kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Srivatsa VaddagiriAdd two hypercalls to KVM hypervisor to support pv-ticketlocks.
KVM_HC_WAIT_FOR_KICK blocks the calling vcpu until another vcpu kicks it or it is woken up because of an event like interrupt.
KVM_HC_KICK_CPU allows the calling vcpu to kick another vcpu.
The presence of these hypercalls is indicated to guest via KVM_FEATURE_WAIT_FOR_KICK/KVM_CAP_WAIT_FOR_KICK. Qemu needs a corresponding patch to pass up the presence of this feature to guest via cpuid. Patch to qemu will be sent separately.
--- arch/x86/include/asm/kvm_para.h | 2 + arch/x86/kvm/x86.c | 69 +++++++++++++++++++++++++++++++++++++++- include/linux/kvm.h | 1 include/linux/kvm_host.h | 1 include/linux/kvm_para.h | 2 + virt/kvm/kvm_main.c | 1 6 files changed, 75 insertions(+), 1 deletion(-)
arch/x86/include/asm/kvm_para.h +2 -0
@@ -16,6 +16,8 @@#define KVM_FEATURE_CLOCKSOURCE 0#define KVM_FEATURE_NOP_IO_DELAY 1#define KVM_FEATURE_MMU_OP 2 +#define KVM_FEATURE_WAIT_FOR_KICK 4 +/* This indicates that the new set of kvmclock msrs * are available. The use of 0x11 and 0x12 is deprecated */
arch/x86/kvm/x86.c +68 -1
93 lines not on this page · raw message
include/linux/kvm.h +1 -0
@@ -540,6 +540,7 @@ struct kvm_ppc_pvinfo {#endif #define KVM_CAP_PPC_GET_PVINFO 57#define KVM_CAP_PPC_IRQ_LEVEL 58 +#define KVM_CAP_WAIT_FOR_KICK 59#ifdef KVM_CAP_IRQ_ROUTING
include/linux/kvm_host.h +1 -0
@@ -105,6 +105,7 @@ struct kvm_vcpu {#endif struct kvm_vcpu_arch arch; +int kicked; };/*
include/linux/kvm_para.h +2 -0
@@ -19,6 +19,8 @@#define KVM_HC_MMU_OP 2#define KVM_HC_FEATURES 3#define KVM_HC_PPC_MAP_MAGIC_PAGE 4 +#define KVM_HC_WAIT_FOR_KICK 5 +#define KVM_HC_KICK_CPU 6/* * hypercalls use architecture specific
virt/kvm/kvm_main.c +1 -0
@@ -185,6 +185,7 @@ int kvm_vcpu_init(struct kvm_vcpu *vcpu, vcpu->cpu =-1 ; vcpu->kvm = kvm; vcpu->vcpu_id = id; + vcpu->kicked =0 ;init_waitqueue_head (&vcpu->wq); page =alloc_page (GFP_KERNEL | __GFP_ZERO);
PATCH 3/3 kvm guest : Add support for pv-ticketlocks
In reply to Srivatsa VaddagiriThis patch extends Linux guests running on KVM hypervisor to support pv-ticketlocks. Very early during bootup, paravirtualied KVM guest detects if the hypervisor has required feature (KVM_FEATURE_WAIT_FOR_KICK) to support pv-ticketlocks. If so, support for pv-ticketlocks is registered via pv_lock_ops.
--- arch/x86/Kconfig | 9 + arch/x86/include/asm/kvm_para.h | 8 + arch/x86/kernel/head64.c | 3 arch/x86/kernel/kvm.c | 208 ++++++++++++++++++++++++++++++++++++++++ 4 files changed, 228 insertions(+)
arch/x86/Kconfig +9 -0
@@ -508,6 +508,15 @@ config KVM_GUEST This option enables various optimizations for running under the KVM hypervisor. +config KVM_DEBUG_FS + bool "Enable debug information for KVM Guests in debugfs" + depends on KVM_GUEST + default n + ---help--- + This option enables collection of various statistics for KVM guest. + Statistics are displayed in debugfs filesystem. Enabling this option + may incur significant overhead. + source "arch/x86/lguest/Kconfig" config PARAVIRT
arch/x86/include/asm/kvm_para.h +8 -0
@@ -162,8 +162,16 @@ static inline unsigned int kvm_arch_para#ifdef CONFIG_KVM_GUEST void __init kvm_guest_init (void ); + +#ifdef CONFIG_PARAVIRT_SPINLOCKS +void __init kvm_guest_early_init (void ); +#else +#define kvm_guest_early_init () do { } while (0) +#endif +#else #define kvm_guest_init () do { } while (0) +#define kvm_guest_early_init () do { } while (0)#endif #endif /* __KERNEL__ */
arch/x86/kernel/head64.c +3 -0
@@ -13,6 +13,7 @@#include <linux/start_kernel.h> #include <linux/io.h> #include <linux/memblock.h> +#include <linux/kvm_para.h> #include <asm/processor.h> #include <asm/proto.h>
@@ -118,6 +119,8 @@ void __init x86_64_start_reservations(chreserve_ebda_region (); +kvm_guest_early_init (); +/* * At this point everything still needed from the boot loader * or BIOS or kernel text should be early reserved or marked not
arch/x86/kernel/kvm.c +208 -0
211 lines not on this page · raw message
PATCH 3/3 kvm guest : Add support for pv-ticketlocks
In reply to Srivatsa VaddagiriThis patch extends Linux guests running on KVM hypervisor to support pv-ticketlocks. Very early during bootup, paravirtualied KVM guest detects if the hypervisor has required feature (KVM_FEATURE_WAIT_FOR_KICK) to support pv-ticketlocks. If so, support for pv-ticketlocks is registered via pv_lock_ops.
--- arch/x86/Kconfig | 9 + arch/x86/include/asm/kvm_para.h | 8 + arch/x86/kernel/head64.c | 3 arch/x86/kernel/kvm.c | 208 ++++++++++++++++++++++++++++++++++++++++ 4 files changed, 228 insertions(+)
arch/x86/Kconfig +9 -0
@@ -508,6 +508,15 @@ config KVM_GUEST This option enables various optimizations for running under the KVM hypervisor. +config KVM_DEBUG_FS + bool "Enable debug information for KVM Guests in debugfs" + depends on KVM_GUEST + default n + ---help--- + This option enables collection of various statistics for KVM guest. + Statistics are displayed in debugfs filesystem. Enabling this option + may incur significant overhead. + source "arch/x86/lguest/Kconfig" config PARAVIRT
arch/x86/include/asm/kvm_para.h +8 -0
@@ -162,8 +162,16 @@ static inline unsigned int kvm_arch_para#ifdef CONFIG_KVM_GUEST void __init kvm_guest_init (void ); + +#ifdef CONFIG_PARAVIRT_SPINLOCKS +void __init kvm_guest_early_init (void ); +#else +#define kvm_guest_early_init () do { } while (0) +#endif +#else #define kvm_guest_init () do { } while (0) +#define kvm_guest_early_init () do { } while (0)#endif #endif /* __KERNEL__ */
arch/x86/kernel/head64.c +3 -0
@@ -13,6 +13,7 @@#include <linux/start_kernel.h> #include <linux/io.h> #include <linux/memblock.h> +#include <linux/kvm_para.h> #include <asm/processor.h> #include <asm/proto.h>
@@ -118,6 +119,8 @@ void __init x86_64_start_reservations(chreserve_ebda_region (); +kvm_guest_early_init (); +/* * At this point everything still needed from the boot loader * or BIOS or kernel text should be early reserved or marked not
arch/x86/kernel/kvm.c +208 -0
211 lines not on this page · raw message
Peter Zijlstra
maintainerRe: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Srivatsa VaddagiriQuoted 11 lines · Srivatsa Vaddagiri
Add two hypercalls to KVM hypervisor to support pv-ticketlocks.
KVM_HC_WAIT_FOR_KICKblocks the calling vcpu until another vcpu kicks it or it is woken up because of an event like interrupt.
KVM_HC_KICK_CPUallows the calling vcpu to kick another vcpu.The presence of these hypercalls is indicated to guest via KVM_FEATURE_WAIT_FOR_KICK/KVM_CAP_WAIT_FOR_KICK. Qemu needs a corresponding patch to pass up the presence of this feature to guest via cpuid. Patch to qemu will be sent separately.
I didn't really read the patch, and I totally forgot everything from when I looked at the Xen series, but does the Xen/KVM hypercall interface for this include the vcpu to await the kick from?
My guess is not, since the ticket locks used don't know who the owner is, which is of course, sad. There are FIFO spinlock implementations that can do this though.. although I think they all have a bigger memory footprint.
The reason for wanting this should be clear I guess, it allows PI.
Peter Zijlstra
maintainerRe: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Srivatsa VaddagiriQuoted 11 lines · Srivatsa Vaddagiri
Add two hypercalls to KVM hypervisor to support pv-ticketlocks.
KVM_HC_WAIT_FOR_KICKblocks the calling vcpu until another vcpu kicks it or it is woken up because of an event like interrupt.
KVM_HC_KICK_CPUallows the calling vcpu to kick another vcpu.The presence of these hypercalls is indicated to guest via KVM_FEATURE_WAIT_FOR_KICK/KVM_CAP_WAIT_FOR_KICK. Qemu needs a corresponding patch to pass up the presence of this feature to guest via cpuid. Patch to qemu will be sent separately.
I didn't really read the patch, and I totally forgot everything from when I looked at the Xen series, but does the Xen/KVM hypercall interface for this include the vcpu to await the kick from?
My guess is not, since the ticket locks used don't know who the owner is, which is of course, sad. There are FIFO spinlock implementations that can do this though.. although I think they all have a bigger memory footprint.
The reason for wanting this should be clear I guess, it allows PI.
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Srivatsa VaddagiriQuoted 4 lines · Srivatsa Vaddagiri
Add two hypercalls to KVM hypervisor to support pv-ticketlocks.
KVM_HC_WAIT_FOR_KICKblocks the calling vcpu until another vcpu kicks it or it is woken up because of an event like interrupt.
One possibility is to extend this hypercall to do a directed yield as well, which needs some more thought. Another issue that needs to be resolved with pv-ticketlocks is the impact on intra-VM fairness. A guest experiencing heavy contention can keep yielding cpu, allowing other VMs to get more time than they deserve.
- vatsa
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Srivatsa VaddagiriQuoted 4 lines · Srivatsa Vaddagiri
Add two hypercalls to KVM hypervisor to support pv-ticketlocks.
KVM_HC_WAIT_FOR_KICKblocks the calling vcpu until another vcpu kicks it or it is woken up because of an event like interrupt.
One possibility is to extend this hypercall to do a directed yield as well, which needs some more thought. Another issue that needs to be resolved with pv-ticketlocks is the impact on intra-VM fairness. A guest experiencing heavy contention can keep yielding cpu, allowing other VMs to get more time than they deserve.
- vatsa
Peter Zijlstra
maintainerRe: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Srivatsa VaddagiriQuoted 11 lines · Srivatsa Vaddagiri
Quoted 4 lines · Srivatsa Vaddagiri
Add two hypercalls to KVM hypervisor to support pv-ticketlocks.
KVM_HC_WAIT_FOR_KICKblocks the calling vcpu until another vcpu kicks it or it is woken up because of an event like interrupt.One possibility is to extend this hypercall to do a directed yield as well, which needs some more thought. Another issue that needs to be resolved with pv-ticketlocks is the impact on intra-VM fairness. A guest experiencing heavy contention can keep yielding cpu, allowing other VMs to get more time than they deserve.
No, yield sucks, if you know the owner you can do actual PI.
Peter Zijlstra
maintainerRe: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Srivatsa VaddagiriQuoted 11 lines · Srivatsa Vaddagiri
Quoted 4 lines · Srivatsa Vaddagiri
Add two hypercalls to KVM hypervisor to support pv-ticketlocks.
KVM_HC_WAIT_FOR_KICKblocks the calling vcpu until another vcpu kicks it or it is woken up because of an event like interrupt.One possibility is to extend this hypercall to do a directed yield as well, which needs some more thought. Another issue that needs to be resolved with pv-ticketlocks is the impact on intra-VM fairness. A guest experiencing heavy contention can keep yielding cpu, allowing other VMs to get more time than they deserve.
No, yield sucks, if you know the owner you can do actual PI.
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Peter ZijlstraQuoted 3 lines · Peter Zijlstra
I didn't really read the patch, and I totally forgot everything from when I looked at the Xen series, but does the Xen/KVM hypercall interface for this include the vcpu to await the kick from?
No not yet, for reasons you mention below.
Quoted 6 lines
My guess is not, since the ticket locks used don't know who the owner is, which is of course, sad. There are FIFO spinlock implementations that can do this though.. although I think they all have a bigger memory footprint.
The reason for wanting this should be clear I guess, it allows PI.
Yeah - that would be good to experiment with.
- vatsa
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Peter ZijlstraQuoted 3 lines · Peter Zijlstra
I didn't really read the patch, and I totally forgot everything from when I looked at the Xen series, but does the Xen/KVM hypercall interface for this include the vcpu to await the kick from?
No not yet, for reasons you mention below.
Quoted 6 lines
My guess is not, since the ticket locks used don't know who the owner is, which is of course, sad. There are FIFO spinlock implementations that can do this though.. although I think they all have a bigger memory footprint.
The reason for wanting this should be clear I guess, it allows PI.
Yeah - that would be good to experiment with.
- vatsa
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Srivatsa VaddagiriQuoted 44 lines · Srivatsa Vaddagiri
Quoted 22 lines · Jeremy Fitzhardinge
From: Jeremy Fitzhardinge <[email protected]>
Maintain a flag in both LSBs of the ticket lock which indicates whether anyone is in the lock slowpath and may need kicking when the current holder unlocks. The flags are set when the first locker enters the slowpath, and cleared when unlocking to an empty queue.
In the specific implementation of
lock_spinning(), make sure to set the slowpath flags on the lock just before blocking. We must do this before the last-chance pickup test to prevent a deadlock with the unlocker:Unlocker Locker
test for lock pickup -> fail test slowpath + unlock -> false set slowpath flags blockWhereas this works in any ordering:
Quoted 7 lines
Unlocker Locker
set slowpath flags test for lock pickup
-> fail
block
test slowpath + unlock-> true, kickI think this is still racy ..
Unlocker Locker
test slowpath
-> false set slowpath flag test for lock pickup -> fail block
Quoted 5 lines
unlock
unlock needs to happen first before testing slowpath? I have made that change for my KVM guest and it seems to be working well with that change .. Will cleanup and post my patches shortly
I think you're probably right; when I last tested this code, it was hanging in at about the rate this kind of race would cause. And in my previous analysis of similar schemes (the current pv spinlock code), it was always correct to do the "slowpath" test after doing do the unlock.
*But* I haven't yet had the chance to specifically go through and analyse your patch in detail to make sure there's nothing else going on, so take this as provisional.
How much testing have you given it?
Thanks,
J
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Srivatsa VaddagiriQuoted 44 lines · Srivatsa Vaddagiri
Quoted 22 lines · Jeremy Fitzhardinge
From: Jeremy Fitzhardinge <[email protected]>
Maintain a flag in both LSBs of the ticket lock which indicates whether anyone is in the lock slowpath and may need kicking when the current holder unlocks. The flags are set when the first locker enters the slowpath, and cleared when unlocking to an empty queue.
In the specific implementation of
lock_spinning(), make sure to set the slowpath flags on the lock just before blocking. We must do this before the last-chance pickup test to prevent a deadlock with the unlocker:Unlocker Locker
test for lock pickup -> fail test slowpath + unlock -> false set slowpath flags blockWhereas this works in any ordering:
Quoted 7 lines
Unlocker Locker
set slowpath flags test for lock pickup
-> fail
block
test slowpath + unlock-> true, kickI think this is still racy ..
Unlocker Locker
test slowpath
-> false set slowpath flag test for lock pickup -> fail block
Quoted 5 lines
unlock
unlock needs to happen first before testing slowpath? I have made that change for my KVM guest and it seems to be working well with that change .. Will cleanup and post my patches shortly
I think you're probably right; when I last tested this code, it was hanging in at about the rate this kind of race would cause. And in my previous analysis of similar schemes (the current pv spinlock code), it was always correct to do the "slowpath" test after doing do the unlock.
*But* I haven't yet had the chance to specifically go through and analyse your patch in detail to make sure there's nothing else going on, so take this as provisional.
How much testing have you given it?
Thanks,
J
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeQuoted 10 lines · Jeremy Fitzhardinge
I think you're probably right; when I last tested this code, it was hanging in at about the rate this kind of race would cause. And in my previous analysis of similar schemes (the current pv spinlock code), it was always correct to do the "slowpath" test after doing do the unlock.
*But* I haven't yet had the chance to specifically go through and analyse your patch in detail to make sure there's nothing else going on, so take this as provisional.
How much testing have you given it?
I have tested quite extensively with booting a 16-vcpu guest (on a 16-pcpu host) and running kernel compine (with 32-threads). Without this patch, I had difficulty booting/shutting-down successfully (it would hang mid-way).
- vatsa
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeQuoted 10 lines · Jeremy Fitzhardinge
I think you're probably right; when I last tested this code, it was hanging in at about the rate this kind of race would cause. And in my previous analysis of similar schemes (the current pv spinlock code), it was always correct to do the "slowpath" test after doing do the unlock.
*But* I haven't yet had the chance to specifically go through and analyse your patch in detail to make sure there's nothing else going on, so take this as provisional.
How much testing have you given it?
I have tested quite extensively with booting a 16-vcpu guest (on a 16-pcpu host) and running kernel compine (with 32-threads). Without this patch, I had difficulty booting/shutting-down successfully (it would hang mid-way).
- vatsa
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Peter ZijlstraQuoted 13 lines · Peter Zijlstra
Quoted 11 lines · Srivatsa Vaddagiri
Add two hypercalls to KVM hypervisor to support pv-ticketlocks.
KVM_HC_WAIT_FOR_KICKblocks the calling vcpu until another vcpu kicks it or it is woken up because of an event like interrupt.
KVM_HC_KICK_CPUallows the calling vcpu to kick another vcpu.The presence of these hypercalls is indicated to guest via KVM_FEATURE_WAIT_FOR_KICK/KVM_CAP_WAIT_FOR_KICK. Qemu needs a corresponding patch to pass up the presence of this feature to guest via cpuid. Patch to qemu will be sent separately.
Quoted 8 lines
I didn't really read the patch, and I totally forgot everything from when I looked at the Xen series, but does the Xen/KVM hypercall interface for this include the vcpu to await the kick from?
My guess is not, since the ticket locks used don't know who the owner is, which is of course, sad. There are FIFO spinlock implementations that can do this though.. although I think they all have a bigger memory footprint.
At least in the Xen code, a current owner isn't very useful, because we need the current owner to kick the *next* owner to life at release time, which we can't do without some structure recording which ticket belongs to which cpu.
(A reminder: the big problem with ticket locks is not with the current owner getting preempted, but making sure the next VCPU gets scheduled quickly when the current one releases; without that all the waiting VCPUs burn the timeslices until the VCPU scheduler gets around to scheduling the actual next in line.)
At present, the code needs to scan an array of percpu "I am waiting on lock X with ticket Y" structures to work out who's next. The search is somewhat optimised by keeping a cpuset of which CPUs are actually blocked on spinlocks, but its still going to scale badly with lots of CPUs.
I haven't thought of a good way to improve on this; an obvious approach is to just add a pointer to the spinlock and hang an explicit linked list off it, but that's incompatible with wanting to avoid expanding the lock.
You could have a table of auxiliary per-lock data hashed on the lock address, but its not clear to me that its an improvement on the array approach, especially given the synchronization issues of keeping that structure up to date (do we have a generic lockless hashtable implementation?). But perhaps its one of those things that makes sense at larger scales.
Quoted 1 line
The reason for wanting this should be clear I guess, it allows PI.
Well, if we can expand the spinlock to include an owner, then all this becomes moot...
J
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Peter ZijlstraQuoted 13 lines · Peter Zijlstra
Quoted 11 lines · Srivatsa Vaddagiri
Add two hypercalls to KVM hypervisor to support pv-ticketlocks.
KVM_HC_WAIT_FOR_KICKblocks the calling vcpu until another vcpu kicks it or it is woken up because of an event like interrupt.
KVM_HC_KICK_CPUallows the calling vcpu to kick another vcpu.The presence of these hypercalls is indicated to guest via KVM_FEATURE_WAIT_FOR_KICK/KVM_CAP_WAIT_FOR_KICK. Qemu needs a corresponding patch to pass up the presence of this feature to guest via cpuid. Patch to qemu will be sent separately.
Quoted 8 lines
I didn't really read the patch, and I totally forgot everything from when I looked at the Xen series, but does the Xen/KVM hypercall interface for this include the vcpu to await the kick from?
My guess is not, since the ticket locks used don't know who the owner is, which is of course, sad. There are FIFO spinlock implementations that can do this though.. although I think they all have a bigger memory footprint.
At least in the Xen code, a current owner isn't very useful, because we need the current owner to kick the *next* owner to life at release time, which we can't do without some structure recording which ticket belongs to which cpu.
(A reminder: the big problem with ticket locks is not with the current owner getting preempted, but making sure the next VCPU gets scheduled quickly when the current one releases; without that all the waiting VCPUs burn the timeslices until the VCPU scheduler gets around to scheduling the actual next in line.)
At present, the code needs to scan an array of percpu "I am waiting on lock X with ticket Y" structures to work out who's next. The search is somewhat optimised by keeping a cpuset of which CPUs are actually blocked on spinlocks, but its still going to scale badly with lots of CPUs.
I haven't thought of a good way to improve on this; an obvious approach is to just add a pointer to the spinlock and hang an explicit linked list off it, but that's incompatible with wanting to avoid expanding the lock.
You could have a table of auxiliary per-lock data hashed on the lock address, but its not clear to me that its an improvement on the array approach, especially given the synchronization issues of keeping that structure up to date (do we have a generic lockless hashtable implementation?). But perhaps its one of those things that makes sense at larger scales.
Quoted 1 line
The reason for wanting this should be clear I guess, it allows PI.
Well, if we can expand the spinlock to include an owner, then all this becomes moot...
J
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Srivatsa VaddagiriQuoted 3 lines · Srivatsa Vaddagiri
I have tested quite extensively with booting a 16-vcpu guest (on a 16-pcpu host) and running kernel compine (with 32-threads). Without this patch, I had difficulty booting/shutting-down successfully (it would hang mid-way).
Sounds good. But I like to test with "make -j 100-200" to really give things a workout.
J
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Srivatsa VaddagiriQuoted 3 lines · Srivatsa Vaddagiri
I have tested quite extensively with booting a 16-vcpu guest (on a 16-pcpu host) and running kernel compine (with 32-threads). Without this patch, I had difficulty booting/shutting-down successfully (it would hang mid-way).
Sounds good. But I like to test with "make -j 100-200" to really give things a workout.
J
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeQuoted 7 lines · Jeremy Fitzhardinge
Quoted 3 lines · Srivatsa Vaddagiri
I have tested quite extensively with booting a 16-vcpu guest (on a 16-pcpu host) and running kernel compine (with 32-threads). Without this patch, I had difficulty booting/shutting-down successfully (it would hang mid-way).
Sounds good. But I like to test with "make -j 100-200" to really give things a workout.
I reran the tests with the following configuration:
Host : 16pcpus, 32GB Memory
Single KVM guest w/ 32vcpus, 16GB memory
It survived a kernel compile with 200 threads once and another time with 300 threads. 'make allyesconfig' was run before compiling the kernel. So looks quite stable to me ..additional testing from wider community will also help.
- vasa
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeQuoted 7 lines · Jeremy Fitzhardinge
Quoted 3 lines · Srivatsa Vaddagiri
I have tested quite extensively with booting a 16-vcpu guest (on a 16-pcpu host) and running kernel compine (with 32-threads). Without this patch, I had difficulty booting/shutting-down successfully (it would hang mid-way).
Sounds good. But I like to test with "make -j 100-200" to really give things a workout.
I reran the tests with the following configuration:
Host : 16pcpus, 32GB Memory
Single KVM guest w/ 32vcpus, 16GB memory
It survived a kernel compile with 200 threads once and another time with 300 threads. 'make allyesconfig' was run before compiling the kernel. So looks quite stable to me ..additional testing from wider community will also help.
- vasa
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeQuoted 9 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
Quoted 1 line · Srivatsa Vaddagiri
I have tested quite extensively with booting a 16-vcpu guest (on a 16-pcpu
host)
Quoted 2 lines
and running kernel compine (with 32-threads). Without this patch, I had difficulty booting/shutting-down successfully (it would hang mid-way).
Sounds good. But I like to test with "make -j 100-200" to really give things a workout.
Hmm, in my experience, heavily over-committing CPUs (e.g. a domain with double or more the vCPU-s that the system has pCPU-s, or the pCPU-s the domain is allowed to run on) is a much better test for eventual problems in the spin lock code paths.
Jan
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeQuoted 9 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
Quoted 1 line · Srivatsa Vaddagiri
I have tested quite extensively with booting a 16-vcpu guest (on a 16-pcpu
host)
Quoted 2 lines
and running kernel compine (with 32-threads). Without this patch, I had difficulty booting/shutting-down successfully (it would hang mid-way).
Sounds good. But I like to test with "make -j 100-200" to really give things a workout.
Hmm, in my experience, heavily over-committing CPUs (e.g. a domain with double or more the vCPU-s that the system has pCPU-s, or the pCPU-s the domain is allowed to run on) is a much better test for eventual problems in the spin lock code paths.
Jan
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Jeremy FitzhardingeQuoted 4 lines · Jeremy Fitzhardinge
Quoted 1 line
The reason for wanting this should be clear I guess, it allows PI.
Well, if we can expand the spinlock to include an owner, then all this becomes moot...
How so? Having an owner will not eliminate the need for pv-ticketlocks afaict. We still need a mechanism to reduce latency in scheduling the next thread-in-waiting, which is achieved by your patches.
- vatsa
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Jeremy FitzhardingeQuoted 4 lines · Jeremy Fitzhardinge
Quoted 1 line
The reason for wanting this should be clear I guess, it allows PI.
Well, if we can expand the spinlock to include an owner, then all this becomes moot...
How so? Having an owner will not eliminate the need for pv-ticketlocks afaict. We still need a mechanism to reduce latency in scheduling the next thread-in-waiting, which is achieved by your patches.
- vatsa
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Jeremy FitzhardingeQuoted 9 lines · Jeremy Fitzhardinge
Quoted 8 lines
I didn't really read the patch, and I totally forgot everything from when I looked at the Xen series, but does the Xen/KVM hypercall interface for this include the vcpu to await the kick from?
My guess is not, since the ticket locks used don't know who the owner is, which is of course, sad. There are FIFO spinlock implementations that can do this though.. although I think they all have a bigger memory footprint.
Quoted 4 lines
At least in the Xen code, a current owner isn't very useful, because we need the current owner to kick the *next* owner to life at release time, which we can't do without some structure recording which ticket belongs to which cpu.
If we had a yield-to [1] sort of interface _and_ information on which vcpu owns a lock, then lock-spinners can yield-to the owning vcpu, while the unlocking vcpu can yield-to the next-vcpu-in-waiting. The key here is not to sleep when waiting for locks (as implemented by current patch-series, which can put other VMs at an advantage by giving them more time than they are entitled to) and also to ensure that lock-owner as well as the next-in-line lock-owner are not unduly made to wait for cpu.
Is there a way we can dynamically expand the size of lock only upon contention to include additional information like owning vcpu? Have the lock point to a per-cpu area upon contention where additional details can be stored perhaps?
1. https://lkml.org/lkml/2011/1/14/44
- vatsa
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Jeremy FitzhardingeQuoted 9 lines · Jeremy Fitzhardinge
Quoted 8 lines
I didn't really read the patch, and I totally forgot everything from when I looked at the Xen series, but does the Xen/KVM hypercall interface for this include the vcpu to await the kick from?
My guess is not, since the ticket locks used don't know who the owner is, which is of course, sad. There are FIFO spinlock implementations that can do this though.. although I think they all have a bigger memory footprint.
Quoted 4 lines
At least in the Xen code, a current owner isn't very useful, because we need the current owner to kick the *next* owner to life at release time, which we can't do without some structure recording which ticket belongs to which cpu.
If we had a yield-to [1] sort of interface _and_ information on which vcpu owns a lock, then lock-spinners can yield-to the owning vcpu, while the unlocking vcpu can yield-to the next-vcpu-in-waiting. The key here is not to sleep when waiting for locks (as implemented by current patch-series, which can put other VMs at an advantage by giving them more time than they are entitled to) and also to ensure that lock-owner as well as the next-in-line lock-owner are not unduly made to wait for cpu.
Is there a way we can dynamically expand the size of lock only upon contention to include additional information like owning vcpu? Have the lock point to a per-cpu area upon contention where additional details can be stored perhaps?
1. https://lkml.org/lkml/2011/1/14/44
- vatsa
Peter Zijlstra
maintainerRe: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Srivatsa VaddagiriQuoted 3 lines · Srivatsa Vaddagiri
If we had a yield-to [1] sort of interface _and_ information on which vcpu owns a lock, then lock-spinners can yield-to the owning vcpu,
and then I'd nak it for being stupid ;-)
really, yield*() is retarded, never even consider using it. If you've got the actual owner you can do full blown PI, which is tons better than a 'do-something-random' call.
The only reason the whole non-virt pause loop filtering muck uses it is because it really doesn't know anything, and do-something is pretty much all it can do. Its a broken interface.
Peter Zijlstra
maintainerRe: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Srivatsa VaddagiriQuoted 3 lines · Srivatsa Vaddagiri
If we had a yield-to [1] sort of interface _and_ information on which vcpu owns a lock, then lock-spinners can yield-to the owning vcpu,
and then I'd nak it for being stupid ;-)
really, yield*() is retarded, never even consider using it. If you've got the actual owner you can do full blown PI, which is tons better than a 'do-something-random' call.
The only reason the whole non-virt pause loop filtering muck uses it is because it really doesn't know anything, and do-something is pretty much all it can do. Its a broken interface.
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Peter ZijlstraQuoted 10 lines · Peter Zijlstra
Quoted 3 lines · Srivatsa Vaddagiri
If we had a yield-to [1] sort of interface _and_ information on which vcpu owns a lock, then lock-spinners can yield-to the owning vcpu,
and then I'd nak it for being stupid ;-)
really, yield*() is retarded, never even consider using it. If you've got the actual owner you can do full blown PI, which is tons better than a 'do-something-random' call.
Yes definitely that would be much better than yield-to.
Quoted 3 lines
The only reason the whole non-virt pause loop filtering muck uses it is because it really doesn't know anything, and do-something is pretty much all it can do. Its a broken interface.
- vatsa
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Peter ZijlstraQuoted 10 lines · Peter Zijlstra
Quoted 3 lines · Srivatsa Vaddagiri
If we had a yield-to [1] sort of interface _and_ information on which vcpu owns a lock, then lock-spinners can yield-to the owning vcpu,
and then I'd nak it for being stupid ;-)
really, yield*() is retarded, never even consider using it. If you've got the actual owner you can do full blown PI, which is tons better than a 'do-something-random' call.
Yes definitely that would be much better than yield-to.
Quoted 3 lines
The only reason the whole non-virt pause loop filtering muck uses it is because it really doesn't know anything, and do-something is pretty much all it can do. Its a broken interface.
- vatsa
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Srivatsa VaddagiriQuoted 7 lines · Srivatsa Vaddagiri
Quoted 3 lines · Jeremy Fitzhardinge
Quoted 1 line
The reason for wanting this should be clear I guess, it allows PI.
Well, if we can expand the spinlock to include an owner, then all this becomes moot...
How so? Having an owner will not eliminate the need for pv-ticketlocks afaict. We still need a mechanism to reduce latency in scheduling the next thread-in-waiting, which is achieved by your patches.
No, sorry, I should have been clearer. I meant that going to the effort of not increasing the lock size to record "in slowpath" state.
J
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Srivatsa VaddagiriQuoted 7 lines · Srivatsa Vaddagiri
Quoted 3 lines · Jeremy Fitzhardinge
Quoted 1 line
The reason for wanting this should be clear I guess, it allows PI.
Well, if we can expand the spinlock to include an owner, then all this becomes moot...
How so? Having an owner will not eliminate the need for pv-ticketlocks afaict. We still need a mechanism to reduce latency in scheduling the next thread-in-waiting, which is achieved by your patches.
No, sorry, I should have been clearer. I meant that going to the effort of not increasing the lock size to record "in slowpath" state.
J
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Srivatsa VaddagiriQuoted 7 lines · Srivatsa Vaddagiri
Quoted 4 lines
At least in the Xen code, a current owner isn't very useful, because we need the current owner to kick the *next* owner to life at release time, which we can't do without some structure recording which ticket belongs to which cpu.
If we had a yield-to [1] sort of interface _and_ information on which vcpu owns a lock, then lock-spinners can yield-to the owning vcpu, while the unlocking vcpu can yield-to the next-vcpu-in-waiting.
Perhaps, but the core problem is how to find "next-vcpu-in-waiting" efficiently. Once you have that info, there's a number of things you can usefully do with it.
Quoted 4 lines
The key here is not to
sleep when waiting for locks (as implemented by current patch-series, which can put other VMs at an advantage by giving them more time than they are entitled to)
Why? If a VCPU can't make progress because its waiting for some resource, then why not schedule something else instead? Presumably when the VCPU does become runnable, the scheduler will credit its previous blocked state and let it run in preference to something else.
Quoted 6 lines
and also to ensure that lock-owner as well as the next-in-line lock-owner
are not unduly made to wait for cpu.Is there a way we can dynamically expand the size of lock only upon contention to include additional information like owning vcpu? Have the lock point to a per-cpu area upon contention where additional details can be stored perhaps?
As soon as you add a pointer to the lock, you're increasing its size. If we had a pointer in there already, then all of this would be moot.
If auxiliary per-lock is uncommon, then using a hash keyed on lock address would be one way to do it.
J
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Srivatsa VaddagiriQuoted 7 lines · Srivatsa Vaddagiri
Quoted 4 lines
At least in the Xen code, a current owner isn't very useful, because we need the current owner to kick the *next* owner to life at release time, which we can't do without some structure recording which ticket belongs to which cpu.
If we had a yield-to [1] sort of interface _and_ information on which vcpu owns a lock, then lock-spinners can yield-to the owning vcpu, while the unlocking vcpu can yield-to the next-vcpu-in-waiting.
Perhaps, but the core problem is how to find "next-vcpu-in-waiting" efficiently. Once you have that info, there's a number of things you can usefully do with it.
Quoted 4 lines
The key here is not to
sleep when waiting for locks (as implemented by current patch-series, which can put other VMs at an advantage by giving them more time than they are entitled to)
Why? If a VCPU can't make progress because its waiting for some resource, then why not schedule something else instead? Presumably when the VCPU does become runnable, the scheduler will credit its previous blocked state and let it run in preference to something else.
Quoted 6 lines
and also to ensure that lock-owner as well as the next-in-line lock-owner
are not unduly made to wait for cpu.Is there a way we can dynamically expand the size of lock only upon contention to include additional information like owning vcpu? Have the lock point to a per-cpu area upon contention where additional details can be stored perhaps?
As soon as you add a pointer to the lock, you're increasing its size. If we had a pointer in there already, then all of this would be moot.
If auxiliary per-lock is uncommon, then using a hash keyed on lock address would be one way to do it.
J
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Jeremy FitzhardingeQuoted 7 lines · Jeremy Fitzhardinge
Quoted 4 lines
The key here is not to
sleep when waiting for locks (as implemented by current patch-series, which can put other VMs at an advantage by giving them more time than they are entitled to)Why? If a VCPU can't make progress because its waiting for some resource, then why not schedule something else instead?
In the process, "something else" can get more share of cpu resource than its entitled to and that's where I was bit concerned. I guess one could employ hard-limits to cap "something else's" bandwidth where it is of real concern (like clouds).
Quoted 3 lines
Presumably when
the VCPU does become runnable, the scheduler will credit its previous blocked state and let it run in preference to something else.
which may not be sufficient for it to gain back bandwidth lost while blocked (speaking of mainline scheduler atleast).
Quoted 5 lines
Quoted 3 lines
Is there a way we can dynamically expand the size of lock only upon contention to include additional information like owning vcpu? Have the lock point to a per-cpu area upon contention where additional details can be stored perhaps?
As soon as you add a pointer to the lock, you're increasing its size.
I didn't really mean to expand size statically. Rather have some bits of the lock word store pointer to a per-cpu area when there is contention (somewhat similar to how bits of rt_mutex.owner are used). I haven't thought thr' this in detail to see if that is possible though.
- vatsa
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Jeremy FitzhardingeQuoted 7 lines · Jeremy Fitzhardinge
Quoted 4 lines
The key here is not to
sleep when waiting for locks (as implemented by current patch-series, which can put other VMs at an advantage by giving them more time than they are entitled to)Why? If a VCPU can't make progress because its waiting for some resource, then why not schedule something else instead?
In the process, "something else" can get more share of cpu resource than its entitled to and that's where I was bit concerned. I guess one could employ hard-limits to cap "something else's" bandwidth where it is of real concern (like clouds).
Quoted 3 lines
Presumably when
the VCPU does become runnable, the scheduler will credit its previous blocked state and let it run in preference to something else.
which may not be sufficient for it to gain back bandwidth lost while blocked (speaking of mainline scheduler atleast).
Quoted 5 lines
Quoted 3 lines
Is there a way we can dynamically expand the size of lock only upon contention to include additional information like owning vcpu? Have the lock point to a per-cpu area upon contention where additional details can be stored perhaps?
As soon as you add a pointer to the lock, you're increasing its size.
I didn't really mean to expand size statically. Rather have some bits of the lock word store pointer to a per-cpu area when there is contention (somewhat similar to how bits of rt_mutex.owner are used). I haven't thought thr' this in detail to see if that is possible though.
- vatsa
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Srivatsa VaddagiriQuoted 6 lines · Srivatsa Vaddagiri
Quoted 5 lines · Jeremy Fitzhardinge
Quoted 4 lines
The key here is not to
sleep when waiting for locks (as implemented by current patch-series, which can put other VMs at an advantage by giving them more time than they are entitled to)
Quoted 7 lines
Quoted 2 lines
Why? If a VCPU can't make progress because its waiting for some resource, then why not schedule something else instead?
In the process, "something else" can get more share of cpu resource than its entitled to and that's where I was bit concerned. I guess one could employ hard-limits to cap "something else's" bandwidth where it is of real concern (like clouds).
I'd like to think I fixed those things in my yield_task_fair + yield_to + kvm_vcpu_on_spin patch series from yesterday.
https://lkml.org/lkml/2011/1/20/403
Signature · 1 line
All rights reversed
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Srivatsa VaddagiriQuoted 6 lines · Srivatsa Vaddagiri
Quoted 5 lines · Jeremy Fitzhardinge
Quoted 4 lines
The key here is not to
sleep when waiting for locks (as implemented by current patch-series, which can put other VMs at an advantage by giving them more time than they are entitled to)
Quoted 7 lines
Quoted 2 lines
Why? If a VCPU can't make progress because its waiting for some resource, then why not schedule something else instead?
In the process, "something else" can get more share of cpu resource than its entitled to and that's where I was bit concerned. I guess one could employ hard-limits to cap "something else's" bandwidth where it is of real concern (like clouds).
I'd like to think I fixed those things in my yield_task_fair + yield_to + kvm_vcpu_on_spin patch series from yesterday.
https://lkml.org/lkml/2011/1/20/403
Signature · 1 line
All rights reversed
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Rik van RielQuoted 10 lines · Rik van Riel
Quoted 7 lines
Quoted 2 lines
Why? If a VCPU can't make progress because its waiting for some resource, then why not schedule something else instead?
In the process, "something else" can get more share of cpu resource than its entitled to and that's where I was bit concerned. I guess one could employ hard-limits to cap "something else's" bandwidth where it is of real concern (like clouds).
I'd like to think I fixed those things in my
yield_task_fair+yield_to+kvm_vcpu_on_spinpatch series from yesterday.
Speaking of the spinlock-in-virtualized-environment problem as whole, IMHO I don't think that kvm_vcpu_on_spin + yield changes will provide the best results, especially where ticketlocks are involved and they are paravirtualized in a manner being discussed in this thread. An important focus of pv-ticketlocks is to reduce the lock _acquisition_ time by ensuring that the next-in-line vcpu gets to run asap when a ticket lock is released. With the way kvm_vcpu_on_spin+yield_to is implemented, I don't see how we can provide the best lock acquisition times for threads. It would be nice though to compare the two approaches (kvm_vcpu_on_spin optimization and the pv-ticketlock scheme) to get some real-world numbers. I unfortunately don't have access to a PLE capable hardware which is required to test your kvm_vcpu_on_spin changes?
Also it may be possible for the pv-ticketlocks to track owning vcpu and make use of a yield-to interface as further optimization to avoid the "others-get-more-time" problem, but Peterz rightly pointed that PI would be a better solution there than yield-to. So overall IMO kvm_vcpu_on_spin+yield_to could be the best solution for unmodified guests, while paravirtualized ticketlocks + some sort of PI would be a better solution where we have the luxury of modifying guest sources!
- vatsa
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Rik van RielQuoted 10 lines · Rik van Riel
Quoted 7 lines
Quoted 2 lines
Why? If a VCPU can't make progress because its waiting for some resource, then why not schedule something else instead?
In the process, "something else" can get more share of cpu resource than its entitled to and that's where I was bit concerned. I guess one could employ hard-limits to cap "something else's" bandwidth where it is of real concern (like clouds).
I'd like to think I fixed those things in my
yield_task_fair+yield_to+kvm_vcpu_on_spinpatch series from yesterday.
Speaking of the spinlock-in-virtualized-environment problem as whole, IMHO I don't think that kvm_vcpu_on_spin + yield changes will provide the best results, especially where ticketlocks are involved and they are paravirtualized in a manner being discussed in this thread. An important focus of pv-ticketlocks is to reduce the lock _acquisition_ time by ensuring that the next-in-line vcpu gets to run asap when a ticket lock is released. With the way kvm_vcpu_on_spin+yield_to is implemented, I don't see how we can provide the best lock acquisition times for threads. It would be nice though to compare the two approaches (kvm_vcpu_on_spin optimization and the pv-ticketlock scheme) to get some real-world numbers. I unfortunately don't have access to a PLE capable hardware which is required to test your kvm_vcpu_on_spin changes?
Also it may be possible for the pv-ticketlocks to track owning vcpu and make use of a yield-to interface as further optimization to avoid the "others-get-more-time" problem, but Peterz rightly pointed that PI would be a better solution there than yield-to. So overall IMO kvm_vcpu_on_spin+yield_to could be the best solution for unmodified guests, while paravirtualized ticketlocks + some sort of PI would be a better solution where we have the luxury of modifying guest sources!
- vatsa
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Srivatsa VaddagiriQuoted 7 lines · Srivatsa Vaddagiri
Also it may be possible for the pv-ticketlocks to track owning vcpu and make use of a yield-to interface as further optimization to avoid the "others-get-more-time" problem, but Peterz rightly pointed that PI would be a better solution there than yield-to. So overall IMO kvm_vcpu_on_spin+yield_to could be the best solution for unmodified guests, while paravirtualized ticketlocks + some sort of PI would be a better solution where we have the luxury of modifying guest sources!
Agreed, for unmodified guests (which is what people will mostly be running for the next couple of years), we have little choice but to use PLE + kvm_vcpu_on_spin + yield_to.
The main question that remains is whether the PV ticketlocks are a large enough improvement to also merge those. I expect they will be, and we'll see so in the benchmark numbers.
Signature · 1 line
All rights reversed
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Srivatsa VaddagiriQuoted 7 lines · Srivatsa Vaddagiri
Also it may be possible for the pv-ticketlocks to track owning vcpu and make use of a yield-to interface as further optimization to avoid the "others-get-more-time" problem, but Peterz rightly pointed that PI would be a better solution there than yield-to. So overall IMO kvm_vcpu_on_spin+yield_to could be the best solution for unmodified guests, while paravirtualized ticketlocks + some sort of PI would be a better solution where we have the luxury of modifying guest sources!
Agreed, for unmodified guests (which is what people will mostly be running for the next couple of years), we have little choice but to use PLE + kvm_vcpu_on_spin + yield_to.
The main question that remains is whether the PV ticketlocks are a large enough improvement to also merge those. I expect they will be, and we'll see so in the benchmark numbers.
Signature · 1 line
All rights reversed
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Rik van RielQuoted 3 lines · Rik van Riel
The main question that remains is whether the PV ticketlocks are a large enough improvement to also merge those. I expect they will be, and we'll see so in the benchmark numbers.
The pathological worst-case of ticket locks in a virtual environment isn't very hard to hit, so I expect they'll make a huge difference
there. On lightly loaded systems (little or no CPU overcommit) then
they should be close to a no-op.
J
Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock
In reply to Rik van RielQuoted 3 lines · Rik van Riel
The main question that remains is whether the PV ticketlocks are a large enough improvement to also merge those. I expect they will be, and we'll see so in the benchmark numbers.
The pathological worst-case of ticket locks in a virtual environment isn't very hard to hit, so I expect they'll make a huge difference
there. On lightly loaded systems (little or no CPU overcommit) then
they should be close to a no-op.
J
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Srivatsa VaddagiriQuoted 87 lines · Srivatsa Vaddagiri
Quoted 14 lines · Srivatsa Vaddagiri
I think this is still racy ..
Unlocker Locker
test slowpath
-> false set slowpath flag test for lock pickup -> fail blockQuoted 5 lines
unlock
unlock needs to happen first before testing slowpath? I have made that change for my KVM guest and it seems to be working well with that change .. Will cleanup and post my patches shortly
Patch below fixes the race described above. You can fold this to your patch 13/14 if you agree this is in right direction.
Signed-off-by Srivatsa Vaddagiri <[email protected]>--- arch/x86/include/asm/spinlock.h | 7 +++---- arch/x86/kernel/paravirt-spinlocks.c | 22 +++++----------------- 2 files changed, 8 insertions(+), 21 deletions(-)Index:
linux-2.6.37/arch/x86/include/asm/spinlock.h
===================================================================arch/x86/include/asm/spinlock.h +3
-4@@ -55,7 +55,7 @@ static __always_inline void __ticket_unl/* Only defined when CONFIG_PARAVIRT_SPINLOCKS defined, but may as * well leave the prototype always visible. */ -extern void __ticket_unlock_release_slowpath (struct arch_spinlock *lock); +extern void __ticket_unlock_slowpath (struct arch_spinlock *lock);#ifdef CONFIG_PARAVIRT_SPINLOCKS @@ -166,10 +166,9 @@ static __always_inline int arch_spin_try static __always_inline void arch_spin_unlock(arch_spinlock_t *lock) {barrier ();/* prevent reordering out of locked region */ +__ticket_unlock_release (lock);if (unlikely (__ticket_in_slowpath (lock))) -__ticket_unlock_release_slowpath (lock); -else -__ticket_unlock_release (lock); +__ticket_unlock_slowpath (lock);barrier ();/* prevent reordering into locked region */ }Index:
linux-2.6.37/arch/x86/kernel/paravirt-spinlocks.c
===================================================================arch/x86/kernel/paravirt-spinlocks.c +3
-8@@ -22,33 +22,21 @@ EXPORT_SYMBOL(pv_lock_ops);* bits. However, we need to be careful about this because someone * may just be entering as we leave, and enter the slowpath. */ -void __ticket_unlock_release_slowpath (struct arch_spinlock *lock) +void __ticket_unlock_slowpath (struct arch_spinlock *lock) {struct arch_spinlock old, new;BUILD_BUG_ON (((__ticket_t )NR_CPUS ) !=NR_CPUS ); old =ACCESS_ONCE (*lock); - new = old; - new.tickets.head +=TICKET_LOCK_INC ;/* Clear the slowpath flag */ new.tickets.tail &= ~TICKET_SLOWPATH_FLAG ; +if (new.tickets.head == new.tickets.tail) +cmpxchg (&lock->head_tail, old.head_tail, new.head_tail); -/* -* If there's currently people waiting or someone snuck in -* since we read the lock above, then do a normal unlock and -* kick. If we managed to unlock with no queued waiters, then -* we can clear the slowpath flag.
arch/x86/kernel/paravirt-spinlocks.c EXPORT_SYMBOL(pv_lock_ops); · line 40
Quoted 10 lines
arch/x86/kernel/paravirt-spinlocks.c +1
-8-*/ -if (new.tickets.head != new.tickets.tail || -cmpxchg (&lock->head_tail, - old.head_tail, new.head_tail) != old.head_tail) { -/* still people waiting */ -__ticket_unlock_release (lock); - } - +/* Wake up an appropriate waiter */ __ticket_unlock_kick (lock, new.tickets.head);
Does the __ticket_unlock_kick need to be unconditional? If the cmpxchg() fails, then it means someone else has come in and changed the lock under our feet, and presumably they'll do the kick as needed?
Or is there the possibility that the kick will get lost?
There's certainly no harm in doing a redundant kick, and I'd expect that case to be pretty rare...
J
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Srivatsa VaddagiriQuoted 87 lines · Srivatsa Vaddagiri
Quoted 14 lines · Srivatsa Vaddagiri
I think this is still racy ..
Unlocker Locker
test slowpath
-> false set slowpath flag test for lock pickup -> fail blockQuoted 5 lines
unlock
unlock needs to happen first before testing slowpath? I have made that change for my KVM guest and it seems to be working well with that change .. Will cleanup and post my patches shortly
Patch below fixes the race described above. You can fold this to your patch 13/14 if you agree this is in right direction.
Signed-off-by Srivatsa Vaddagiri <[email protected]>--- arch/x86/include/asm/spinlock.h | 7 +++---- arch/x86/kernel/paravirt-spinlocks.c | 22 +++++----------------- 2 files changed, 8 insertions(+), 21 deletions(-)Index:
linux-2.6.37/arch/x86/include/asm/spinlock.h
===================================================================arch/x86/include/asm/spinlock.h +3
-4@@ -55,7 +55,7 @@ static __always_inline void __ticket_unl/* Only defined when CONFIG_PARAVIRT_SPINLOCKS defined, but may as * well leave the prototype always visible. */ -extern void __ticket_unlock_release_slowpath (struct arch_spinlock *lock); +extern void __ticket_unlock_slowpath (struct arch_spinlock *lock);#ifdef CONFIG_PARAVIRT_SPINLOCKS @@ -166,10 +166,9 @@ static __always_inline int arch_spin_try static __always_inline void arch_spin_unlock(arch_spinlock_t *lock) {barrier ();/* prevent reordering out of locked region */ +__ticket_unlock_release (lock);if (unlikely (__ticket_in_slowpath (lock))) -__ticket_unlock_release_slowpath (lock); -else -__ticket_unlock_release (lock); +__ticket_unlock_slowpath (lock);barrier ();/* prevent reordering into locked region */ }Index:
linux-2.6.37/arch/x86/kernel/paravirt-spinlocks.c
===================================================================arch/x86/kernel/paravirt-spinlocks.c +3
-8@@ -22,33 +22,21 @@ EXPORT_SYMBOL(pv_lock_ops);* bits. However, we need to be careful about this because someone * may just be entering as we leave, and enter the slowpath. */ -void __ticket_unlock_release_slowpath (struct arch_spinlock *lock) +void __ticket_unlock_slowpath (struct arch_spinlock *lock) {struct arch_spinlock old, new;BUILD_BUG_ON (((__ticket_t )NR_CPUS ) !=NR_CPUS ); old =ACCESS_ONCE (*lock); - new = old; - new.tickets.head +=TICKET_LOCK_INC ;/* Clear the slowpath flag */ new.tickets.tail &= ~TICKET_SLOWPATH_FLAG ; +if (new.tickets.head == new.tickets.tail) +cmpxchg (&lock->head_tail, old.head_tail, new.head_tail); -/* -* If there's currently people waiting or someone snuck in -* since we read the lock above, then do a normal unlock and -* kick. If we managed to unlock with no queued waiters, then -* we can clear the slowpath flag.
arch/x86/kernel/paravirt-spinlocks.c EXPORT_SYMBOL(pv_lock_ops); · line 40
Quoted 10 lines
arch/x86/kernel/paravirt-spinlocks.c +1
-8-*/ -if (new.tickets.head != new.tickets.tail || -cmpxchg (&lock->head_tail, - old.head_tail, new.head_tail) != old.head_tail) { -/* still people waiting */ -__ticket_unlock_release (lock); - } - +/* Wake up an appropriate waiter */ __ticket_unlock_kick (lock, new.tickets.head);
Does the __ticket_unlock_kick need to be unconditional? If the cmpxchg() fails, then it means someone else has come in and changed the lock under our feet, and presumably they'll do the kick as needed?
Or is there the possibility that the kick will get lost?
There's certainly no harm in doing a redundant kick, and I'd expect that case to be pretty rare...
J
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeQuoted 1 line · Jeremy Fitzhardinge
For some reason, I seem to be missing emails from your id/domain and hence had missed this completely!
Quoted 29 lines
Quoted 29 lines
* bits. However, we need to be careful about this because someone
* may just be entering as we leave, and enter the slowpath. */arch/x86/kernel/paravirt-spinlocks.c +3
-12-void __ticket_unlock_release_slowpath (struct arch_spinlock *lock) +void __ticket_unlock_slowpath (struct arch_spinlock *lock) {struct arch_spinlock old, new;BUILD_BUG_ON (((__ticket_t )NR_CPUS ) !=NR_CPUS ); old =ACCESS_ONCE (*lock); - new = old; - new.tickets.head +=TICKET_LOCK_INC ;/* Clear the slowpath flag */ new.tickets.tail &= ~TICKET_SLOWPATH_FLAG ; +if (new.tickets.head == new.tickets.tail) +cmpxchg (&lock->head_tail, old.head_tail, new.head_tail); -/* -* If there's currently people waiting or someone snuck in -* since we read the lock above, then do a normal unlock and -* kick. If we managed to unlock with no queued waiters, then -* we can clear the slowpath flag. -*/ -if (new.tickets.head != new.tickets.tail || -cmpxchg (&lock->head_tail, - old.head_tail, new.head_tail) != old.head_tail) {
Quoted 8 lines
arch/x86/kernel/paravirt-spinlocks.c EXPORT_SYMBOL(pv_lock_ops); · line 40
Quoted 6 lines
arch/x86/kernel/paravirt-spinlocks.c +1
-4-/* still people waiting */ -__ticket_unlock_release (lock); - } - +/* Wake up an appropriate waiter */ __ticket_unlock_kick (lock, new.tickets.head);Does the
__ticket_unlock_kickneed to be unconditional?
I recall having tried optimizing it to be conditional, something along these lines:
if (new.ticket.head == new.tickets.tail) {
cmpxchg();
} else {
__ticket_unlock_kick(lock, new.tickets.head);
}but it didn't work for some reason. I left the call unconditional as was the case previously based on that experiment.
- vatsa
Re: [PATCH 13/14] x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeQuoted 1 line · Jeremy Fitzhardinge
For some reason, I seem to be missing emails from your id/domain and hence had missed this completely!
Quoted 29 lines
Quoted 29 lines
* bits. However, we need to be careful about this because someone
* may just be entering as we leave, and enter the slowpath. */arch/x86/kernel/paravirt-spinlocks.c +3
-12-void __ticket_unlock_release_slowpath (struct arch_spinlock *lock) +void __ticket_unlock_slowpath (struct arch_spinlock *lock) {struct arch_spinlock old, new;BUILD_BUG_ON (((__ticket_t )NR_CPUS ) !=NR_CPUS ); old =ACCESS_ONCE (*lock); - new = old; - new.tickets.head +=TICKET_LOCK_INC ;/* Clear the slowpath flag */ new.tickets.tail &= ~TICKET_SLOWPATH_FLAG ; +if (new.tickets.head == new.tickets.tail) +cmpxchg (&lock->head_tail, old.head_tail, new.head_tail); -/* -* If there's currently people waiting or someone snuck in -* since we read the lock above, then do a normal unlock and -* kick. If we managed to unlock with no queued waiters, then -* we can clear the slowpath flag. -*/ -if (new.tickets.head != new.tickets.tail || -cmpxchg (&lock->head_tail, - old.head_tail, new.head_tail) != old.head_tail) {
Quoted 8 lines
arch/x86/kernel/paravirt-spinlocks.c EXPORT_SYMBOL(pv_lock_ops); · line 40
Quoted 6 lines
arch/x86/kernel/paravirt-spinlocks.c +1
-4-/* still people waiting */ -__ticket_unlock_release (lock); - } - +/* Wake up an appropriate waiter */ __ticket_unlock_kick (lock, new.tickets.head);Does the
__ticket_unlock_kickneed to be unconditional?
I recall having tried optimizing it to be conditional, something along these lines:
if (new.ticket.head == new.tickets.tail) {
cmpxchg();
} else {
__ticket_unlock_kick(lock, new.tickets.head);
}but it didn't work for some reason. I left the call unconditional as was the case previously based on that experiment.
- vatsa