Paravirtualized ticketlocks
Subsystems (5)
v2 cover Paravirtualized ticketlocks
From: Jeremy Fitzhardinge <[email protected]>
[ Changes since last posting:
- fix bugs exposed by the cold light of testing
- make the "slow flag" read in unlock cover the whole lock to force ordering WRT the unlock write
- when kicking on unlock, only look for the CPU *we* released (ie, head value the unlock resulted in), rather than re-reading the new head and kicking on that basis
- enable PV ticketlocks in Xen HVM guests
]
NOTE: this series is available in:
git://github.com/jsgf/linux-xen.git upstream/pvticketlock-slowflag
and is based on the previously posted ticketlock cleanup series in
git://github.com/jsgf/linux-xen.git upstream/ticketlock-cleanup
This series replaces the existing paravirtualized spinlock mechanism with a paravirtualized ticketlock mechanism.
Ticket locks have an inherent problem in a virtualized case, because the vCPUs are scheduled rather than running concurrently (ignoring gang scheduled vCPUs). This can result in catastrophic performance collapses when the vCPU scheduler doesn't schedule the correct "next" vCPU, and ends up scheduling a vCPU which burns its entire timeslice spinning. (Note that this is not the same problem as lock-holder preemption, which this series also addresses; that's also a problem, but not catastrophic).
(See Thomas Friebel's talk "Prevent Guests from Spinning Around"
http://www.xen.org/files/xensummitboston08/LHP.pdf for more details.)
Currently we deal with this by having PV spinlocks, which adds a layer of indirection in front of all the spinlock functions, and defining a completely new implementation for Xen (and for other pvops users, but there are none at present).
PV ticketlocks keeps the existing ticketlock implemenentation (fastpath) as-is, but adds a couple of pvops for the slow paths:
- If a CPU has been waiting for a spinlock for SPIN_THRESHOLD iterations, then call out to the __ticket_lock_spinning() pvop, which allows a backend to block the vCPU rather than spinning. This pvop can set the lock into "slowpath state".
- When releasing a lock, if it is in "slowpath state", the call __ticket_unlock_kick() to kick the next vCPU in line awake. If the lock is no longer in contention, it also clears the slowpath flag.
The "slowpath state" is stored in the LSB of the within the lock ticket. This has the effect of reducing the max number of CPUs by half (so, a "small ticket" can deal with 128 CPUs, and "large ticket" 32768).
This series provides a Xen implementation, but it should be straightforward to add a KVM implementation as well.
Overall, it results in a large reduction in code, it makes the native and virtualized cases closer, and it removes a layer of indirection around all the spinlock functions.
The fast path (taking an uncontended lock which isn't in "slowpath" state) is optimal, identical to the non-paravirtualized case.
The inner part of ticket lock code becomes:
inc = xadd(&lock->tickets, inc);
inc.tail &= ~TICKET_SLOWPATH_FLAG;
if (likely(inc.head == inc.tail))
goto out;
for (;;) {
unsigned count = SPIN_THRESHOLD;
do {
if (ACCESS_ONCE(lock->tickets.head) == inc.tail)
goto out;
cpu_relax();
} while (--count);
__ticket_lock_spinning(lock, inc.tail);
}out: barrier();
which results in:
push %rbp
mov %rsp,%rbp
mov $0x200,%eax
lock xadd %ax,(%rdi)
movzbl %ah,%edx
cmp %al,%dl
jne 1f
pop %rbp
retq
### SLOWPATH START
1: and $-2,%edx
movzbl %dl,%esi
2: mov $0x800,%eax
jmp 4f
3: pause
sub $0x1,%eax je 5f
4: movzbl (%rdi),%ecx
cmp %cl,%dl
jne 3b
pop %rbp
retq
5: callq *__ticket_lock_spinning
jmp 2b
### SLOWPATH END
with CONFIG_PARAVIRT_SPINLOCKS=n, the code has changed slightly, where the fastpath case is straight through (taking the lock without contention), and the spin loop is out of line:
push %rbp
mov %rsp,%rbp
mov $0x100,%eax
lock xadd %ax,(%rdi)
movzbl %ah,%edx
cmp %al,%dl
jne 1f
pop %rbp
retq
### SLOWPATH START
1: pause
movzbl (%rdi),%eax cmp %dl,%al jne 1b pop %rbp retq ### SLOWPATH END
The unlock code is very straightforward:
prev = *lock; __ticket_unlock_release(lock); if (unlikely(__ticket_in_slowpath(lock))) __ticket_unlock_slowpath(lock, prev);
which generates:
push %rbp
mov %rsp,%rbp
movzwl (%rdi),%esi
addb $0x2,(%rdi)
movzwl (%rdi),%eax
testb $0x1,%ah
jne 1f
pop %rbp
retq
### SLOWPATH START1: movzwl (%rdi),%edx
movzbl %dh,%ecx
mov %edx,%eax
and $-2,%ecx # clear TICKET_SLOWPATH_FLAG
mov %cl,%dh
cmp %dl,%cl # test to see if lock is uncontended
je 3f
2: movzbl %dl,%esi
callq *__ticket_unlock_kick # kick anyone waiting
pop %rbp
retq
3: lock cmpxchg %dx,(%rdi) # use cmpxchg to safely write back flag
jmp 2b
### SLOWPATH END
The fastpath is pretty straightforward, but it is definitely more complex than a simple "addb $1,(%rdi)" - which is still generated (and inlined) when PARAVIRT_SPINLOCKS is disabled.
Thoughts? Comments? Suggestions?
Thanks,
J
Jeremy Fitzhardinge (9):
x86/spinlocks: replace pv spinlocks with pv ticketlocks x86/ticketlock: don't inline _spin_unlock when using paravirt
spinlocks
x86/ticketlock: collapse a layer of functions xen/pvticketlock: Xen implementation for PV ticket locks x86/pvticketlock: use callee-save for lock_spinning x86/ticketlocks: when paravirtualizing ticket locks, increment by 2 x86/ticketlock: add slowpath logic
xen/pvticketlock: allow interrupts to be enabled while blocking
Stefano Stabellini (1):
xen: enable PV ticketlocks on HVM Xen
arch/x86/Kconfig | 3 + arch/x86/include/asm/paravirt.h | 30 +--- arch/x86/include/asm/paravirt_types.h | 10 +- arch/x86/include/asm/spinlock.h | 160 ++++++++++++----- arch/x86/include/asm/spinlock_types.h | 16 ++- arch/x86/kernel/paravirt-spinlocks.c | 16 +-- arch/x86/xen/smp.c | 1 + arch/x86/xen/spinlock.c | 315 ++++++++------------------------ kernel/Kconfig.locks | 2 +- 9 files changed, 217 insertions(+), 336 deletions(-)
Signature · 1 line
1.7.6
PATCH v2 1/10 x86/ticketlocks: remove obsolete comment
From: Jeremy Fitzhardinge <[email protected]>
The note about partial registers is not really relevent now that we rely on gcc to generate all the assembler.
--- arch/x86/include/asm/spinlock.h | 4 ---- 1 files changed, 0 insertions(+), 4 deletions(-)
arch/x86/include/asm/spinlock.h +0 -4
@@ -49,10 +49,6 @@* issues and should be optimal for the uncontended case. Note the tail must be * in the high part, because a wide xadd increment of the low part would carry * up and contaminate the high part. -* -* With fewer than 2^8 possible CPUs, we can use x86's partial registers to -* 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. */ static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock) {
Signature · 1 line
1.7.6
PATCH v2 2/10 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 | 10 ++--- arch/x86/include/asm/spinlock.h | 59 ++++++++++++++++++++++++++------- arch/x86/include/asm/spinlock_types.h | 4 -- arch/x86/kernel/paravirt-spinlocks.c | 15 +------- arch/x86/xen/spinlock.c | 7 +++- 6 files changed, 63 insertions(+), 62 deletions(-)
arch/x86/include/asm/paravirt.h +4 -26
@@ -750,36 +750,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 __always_inline void __ticket_lock_spinning(struct arch_spinlock *lock, __ticket_t 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 __always_inline void ____ticket_unlock_kick(struct arch_spinlock *lock, __ticket_t 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 +4 -6
@@ -327,13 +327,11 @@ struct pv_mmu_ops { };struct arch_spinlock ; +#include <asm/spinlock_types.h> +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,__ticket_t ticket); +void (*unlock_kick)(struct arch_spinlock *lock,__ticket_t ticket); };/* This contains all the paravirt structures: we get a convenient
arch/x86/include/asm/spinlock.h +47 -12
108 lines not on this page · raw message
arch/x86/include/asm/spinlock_types.h +0 -4
@@ -1,10 +1,6 @@#ifndef _ASM_X86_SPINLOCK_TYPES_H#define _ASM_X86_SPINLOCK_TYPES_H -#ifndef __LINUX_SPINLOCK_TYPES_H -# error "please don't include this file directly" -#endif -#include <linux/types.h> #if (CONFIG_NR_CPUS <256 )
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.6
PATCH v2 3/10 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
@@ -585,6 +585,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.6
PATCH v2 4/10 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
@@ -76,7 +76,7 @@ static __always_inline void __ticket_unlock_kick(struct arch_spinlock *lock, __t* in the high part, because a wide xadd increment of the low part would carry * up and contaminate the high part. */ -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 = { .tail =1 };
@@ -96,7 +96,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;
@@ -128,7 +128,7 @@ static __always_inline void __ticket_unlock_release(arch_spinlock_t *lock) }#endif -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 ;
@@ -136,46 +136,21 @@ static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)__ticket_unlock_kick (lock, next); } -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.6
PATCH v2 5/10 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.
We need to make sure interrupts are disabled while we're relying on the contents of the per-cpu lock_waiting values, otherwise an interrupt handler could come in, try to take some other lock, block, and overwrite our values.
--- arch/x86/xen/spinlock.c | 287 +++++++---------------------------------------- 1 files changed, 43 insertions(+), 244 deletions(-)
arch/x86/xen/spinlock.c +43 -244
@@ -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,84 @@ 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) +static void xen_lock_spinning (struct arch_spinlock *lock,__ticket_t want) { -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 =__this_cpu_read (lock_spinners); -__this_cpu_write (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 */ -__this_cpu_write (lock_spinners, prev); -} - -static noinline int xen_spin_lock_slow(struct arch_spinlock *lock, bool irq_enable) -{ -struct xen_spinlock *xl = (struct xen_spinlock *)lock; -struct xen_spinlock *prev;int irq =__this_cpu_read (lock_kicker_irq); -int ret; +struct xen_lock_waiting *w = &__get_cpu_var (lock_waiting); +int cpu =smp_processor_id ();u64 start; +unsigned long flags;/* 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); +/* Make sure interrupts are disabled to ensure that these +per-cpu values are not overwritten. */ +local_irq_save (flags); + + 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); -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 ; +cpumask_clear_cpu (cpu, &waiting_cpus); + w->lock =NULL ; - 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" ); +local_irq_restore (flags); -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)); +spin_time_accum_blocked (start); } -static noinline void xen_spin_unlock_slow(struct xen_spinlock *xl) +static void xen_unlock_kick (struct arch_spinlock *lock,__ticket_t 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 +163,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 +197,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 +216,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.6
PATCH v2 6/10 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
@@ -752,7 +752,7 @@ static inline void __set_fixmap(unsigned /* enum fixed_addresses */ idx, static __always_inline void __ticket_lock_spinning(struct arch_spinlock *lock, __ticket_t ticket) { -PVOP_VCALL2 (pv_lock_ops.lock_spinning, lock, ticket); +PVOP_VCALLEE2 (pv_lock_ops.lock_spinning, lock, ticket); } static __always_inline void ____ticket_unlock_kick(struct arch_spinlock *lock, __ticket_t ticket)
arch/x86/include/asm/paravirt_types.h +1 -1
@@ -330,7 +330,7 @@ struct arch_spinlock;#include <asm/spinlock_types.h> struct pv_lock_ops { -void (*lock_spinning)(struct arch_spinlock *lock,__ticket_t ticket); +struct paravirt_callee_save lock_spinning;void (*unlock_kick)(struct arch_spinlock *lock,__ticket_t 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
@@ -145,6 +145,7 @@ out:spin_time_accum_blocked (start); } +PV_CALLEE_SAVE_REGS_THUNK (xen_lock_spinning);static void xen_unlock_kick (struct arch_spinlock *lock,__ticket_t next) {
@@ -197,7 +198,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.6
PATCH v2 7/10 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 | 16 ++++++++-------- arch/x86/include/asm/spinlock_types.h | 10 +++++++++- 2 files changed, 17 insertions(+), 9 deletions(-)
arch/x86/include/asm/spinlock.h +8 -8
@@ -78,7 +78,7 @@ static __always_inline void __ticket_unlock_kick(struct arch_spinlock *lock, __t*/ static __always_inline void arch_spin_lock(struct arch_spinlock *lock) { - registerstruct __raw_tickets inc = { .tail =1 }; + registerstruct __raw_tickets inc = { .tail =TICKET_LOCK_INC }; inc =xadd (&lock->tickets, inc);
@@ -104,7 +104,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;
@@ -113,24 +113,24 @@ static __always_inline int arch_spin_trylock(arch_spinlock_t *lock)#if (NR_CPUS <256 ) static __always_inline void __ticket_unlock_release(arch_spinlock_t *lock) { - asmvolatile (UNLOCK_LOCK_PREFIX "incb %0" + asmvolatile (UNLOCK_LOCK_PREFIX "addb %1, %0" :"+m" (lock->head_tail) - : + :"i" (TICKET_LOCK_INC ) :"memory" ,"cc" ); }#else static __always_inline void __ticket_unlock_release(arch_spinlock_t *lock) { - asmvolatile (UNLOCK_LOCK_PREFIX "incw %0" + asmvolatile (UNLOCK_LOCK_PREFIX "addw %1, %0" :"+m" (lock->head_tail) - : + :"i" (TICKET_LOCK_INC ) :"memory" ,"cc" ); }#endif 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);
@@ -147,7 +147,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
@@ -3,7 +3,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
@@ -11,6 +17,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.6
PATCH v2 8/10 x86/ticketlock: add slowpath logic
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
Maintain a flag in the LSB of the ticket lock tail 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 (ie, no contention).
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 unlock test slowpath -> false set slowpath flags block
Whereas this works in any ordering:
Unlocker Locker
set slowpath flags test for lock pickup
-> fail
block
unlock
test slowpath
-> true, kick
If the unlocker finds that the lock has the slowpath flag set but it is actually uncontended (ie, head == tail, so nobody is waiting), then it clear the slowpath flag.
Note on memory access ordering:
When unlocking a ticketlock with PV callbacks enabled, unlock first "add"s to the lock head, then checks to see if the slowpath flag is set in the lock tail.
However, because reads are not ordered with respect to writes in different memory locations, the CPU could perform the read before updating head to release the lock.
This would deadlock with another CPU in the lock slowpath, as it will set the slowpath flag before checking to see if the lock has been released in the interim.
A heavyweight fix would be to stick a full mfence between the two. However, a lighterweight fix is to simply make sure the flag tests loads both head and tail of the lock in a single operation, thereby making sure that it overlaps with the memory written by the unlock, forcing the CPU to maintain ordering.
Note: this code relies on gcc making sure that unlikely() code is out of line of the fastpath, which only happens when OPTIMIZE_SIZE=n. If it doesn't the generated code isn't too bad, but its definitely suboptimal.
(Thanks to Srivatsa Vaddagiri for providing a bugfix to the original version of this change, which has been folded in.)
--- arch/x86/include/asm/paravirt.h | 2 +- arch/x86/include/asm/spinlock.h | 92 ++++++++++++++++++++++++++------ arch/x86/include/asm/spinlock_types.h | 2 + arch/x86/kernel/paravirt-spinlocks.c | 1 + arch/x86/xen/spinlock.c | 4 ++ 5 files changed, 82 insertions(+), 19 deletions(-)
arch/x86/include/asm/paravirt.h +1 -1
@@ -755,7 +755,7 @@ static __always_inline void __ticket_lock_spinning(struct arch_spinlock *lock, _PVOP_VCALLEE2 (pv_lock_ops.lock_spinning, lock, ticket); } -static __always_inline void ____ticket_unlock_kick(struct arch_spinlock *lock, __ticket_t ticket) +static __always_inline void __ticket_unlock_kick(struct arch_spinlock *lock, __ticket_t ticket) {PVOP_VCALL2 (pv_lock_ops.unlock_kick, lock, ticket); }
arch/x86/include/asm/spinlock.h +74 -18
142 lines not on this page · raw message
arch/x86/include/asm/spinlock_types.h +2 -0
@@ -5,8 +5,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 +1 -0
@@ -15,3 +15,4 @@ struct pv_lock_ops pv_lock_ops = { };EXPORT_SYMBOL (pv_lock_ops); +
arch/x86/xen/spinlock.c +4 -0
@@ -124,6 +124,10 @@ static void xen_lock_spinning(struct arch_spinlock *lock, __ticket_t 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.6
PATCH v2 9/10 xen/pvticketlock: allow interrupts to be enabled while blocking
In reply to Jeremy FitzhardingeFrom: Jeremy Fitzhardinge <[email protected]>
If interrupts were enabled when taking the spinlock, we can leave them enabled while blocking to get the lock.
If we can enable interrupts while waiting for the lock to become available, and we take an interrupt before entering the poll, and the handler takes a spinlock which ends up going into the slow state (invalidating the per-cpu "lock" and "want" values), then when the interrupt handler returns the event channel will remain pending so the poll will return immediately, causing it to return out to the main spinlock loop.
--- arch/x86/xen/spinlock.c | 48 ++++++++++++++++++++++++++++++++++++++++------ 1 files changed, 41 insertions(+), 7 deletions(-)
arch/x86/xen/spinlock.c +41 -7
@@ -106,11 +106,28 @@ static void xen_lock_spinning(struct arch_spinlock *lock, __ticket_t want) start =spin_time_start (); -/* Make sure interrupts are disabled to ensure that these -per-cpu values are not overwritten. */ +/* +* Make sure an interrupt handler can't upset things in a +* partially setup state. +*/ local_irq_save (flags); +/* +* We don't really care if we're overwriting some other +* (lock,want) pair, as that would mean that we're currently +* in an interrupt context, and the outer context had +* interrupts enabled. That has already kicked the VCPU out +* of xen_poll_irq(), so it will just return spuriously and +* retry with newly setup (lock,want). +* +* The ordering protocol on this is that the "lock" pointer +* may only be set non-NULL if the "want" ticket is correct. +* If we're updating "want", we must first clear "lock". +*/ + w->lock =NULL ; +smp_wmb (); w->want = want; +smp_wmb (); w->lock = lock;/* This uses set_bit, which atomic and therefore a barrier */
@@ -124,21 +141,36 @@ static void xen_lock_spinning(struct arch_spinlock *lock, __ticket_t 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. */ +/* +* 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 */ +/* +* 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; } +/* Allow interrupts while blocked */ +local_irq_restore (flags); + +/* +* If an interrupt happens here, it will leave the wakeup irq +* pending, which will cause xen_poll_irq() to return +* immediately. +*/ +/* Block until irq becomes pending (or perhaps a spurious wakeup) */ xen_poll_irq (irq);ADD_STATS (taken_slow_spurious, !xen_test_irq_pending (irq)); +local_irq_save (flags); +kstat_incr_irqs_this_cpu (irq,irq_to_desc (irq)); out:
@@ -160,7 +192,9 @@ static void xen_unlock_kick(struct arch_spinlock *lock, __ticket_t next)for_each_cpu (cpu, &waiting_cpus) {const struct xen_lock_waiting *w = &per_cpu (lock_waiting, cpu); -if (w->lock == lock && w->want == next) { +/* Make sure we read lock before want */ +if (ACCESS_ONCE (w->lock) == lock && +ACCESS_ONCE (w->want) == next) {ADD_STATS (released_slow_kicked,1 );xen_send_IPI_one (cpu,XEN_SPIN_UNLOCK_VECTOR );break ;
Signature · 1 line
1.7.6
PATCH v2 10/10 xen: enable PV ticketlocks on HVM Xen
In reply to Jeremy FitzhardingeFrom: Stefano Stabellini <[email protected]>
--- arch/x86/xen/smp.c | 1 + 1 files changed, 1 insertions(+), 0 deletions(-)
arch/x86/xen/smp.c +1 -0
@@ -552,4 +552,5 @@ void __init xen_hvm_smp_init(void) smp_ops.cpu_die = xen_hvm_cpu_die; smp_ops.send_call_func_ipi = xen_smp_send_call_function_ipi; smp_ops.send_call_func_single_ipi = xen_smp_send_call_function_single_ipi; +xen_init_spinlocks (); }
Signature · 1 line
1.7.6
Quoted 2 lines · On Wednesday 14 September 2011, 17:31:32 Jeremy Fitzhardinge wrote:
This series replaces the existing paravirtualized spinlock mechanism with a paravirtualized ticketlock mechanism.
[...]
Quoted 36 lines
The unlock code is very straightforward:
prev = *lock; __ticket_unlock_release(lock); if (unlikely(__ticket_in_slowpath(lock))) __ticket_unlock_slowpath(lock, prev);which generates:
push %rbp mov %rsp,%rbp movzwl (%rdi),%esi addb $0x2,(%rdi) movzwl (%rdi),%eax testb $0x1,%ah jne 1f pop %rbp retq ### SLOWPATH START1: movzwl (%rdi),%edx
movzbl %dh,%ecx
mov %edx,%eax
and $-2,%ecx # clearTICKET_SLOWPATH_FLAG
mov %cl,%dh
cmp %dl,%cl # test to see if lock is uncontended
je 3f2: movzbl %dl,%esi
callq*__ticket_unlock_kick# kick anyone waiting
pop %rbp
retq3: lock cmpxchg %dx,(%rdi) # use cmpxchg to safely write back flag
jmp 2b
### SLOWPATH END
[...]
Quoted 1 line
Thoughts? Comments? Suggestions?
You have a nasty data race in your code that can cause a losing acquirer to sleep forever, because its setting the TICKET_SLOWPATH flag can race with the lock holder releasing the lock.
I used the code for the slow path from the GIT repo.
Let me try to point out an interleaving:
Lock is held by one thread, contains 0x0200.
_Lock holder_ _Acquirer_
mov $0x200,%eax
lock xadd %ax,(%rdi)
// ax:= 0x0200, lock:= 0x0400
...
// this guy spins for a while, reading
// the lock
...//trying to free the lock
movzwl (%rdi),%esi (esi:=0x0400)
addb $0x2,(%rdi) (LOCAL copy of lock is now: 0x0402)
movzwl (%rdi),%eax (local forwarding from previous store: eax := 0x0402)
testb $0x1,%ah (no wakeup of anybody)
jne 1f
callq *__ticket_lock_spinning
...
// __ticket_enter_slowpath(lock)
lock or (%rdi), $0x100
// (global view of lock := 0x0500)
...
ACCESS_ONCE(lock->tickets.head) == want
// (reads 0x00)
...
xen_poll_irq(irq); // goes to sleep...
[addb $0x2,(%rdi)]
// (becomes globally visible only now! global view of lock := 0x0502)
...
Your code is reusing the (just about) safe version of unlocking a spinlock without understanding the effect that close has on later memory ordering. It may work on CPUs that cannot do narrow -> wide store to load forwarding and have to make the addb store visible globally. This is an implementation artifact of specific uarches, and you mustn't rely on it, since our specified memory model allows looser behaviour.
Since you want to get that addb out to global memory before the second read, either use a LOCK prefix for it, add an MFENCE between addb and movzwl, or use a LOCKed instruction that will have a fencing effect (e.g., to top-of-stack)between addb and movzwl.
Stephan
Signature · 12 lines
Stephan Diestelhorst, AMD Operating System Research Center [email protected] Tel. +49 (0)351 448 356 719 Advanced Micro Devices GmbH Einsteinring 24 85609 Aschheim Germany Geschaeftsfuehrer: Alberto Bozzo Sitz: Dornach, Gemeinde Aschheim, Landkreis Muenchen Registergericht Muenchen, HRB Nr. 43632, WEEE-Reg-Nr: DE 12919551
Quoted 82 lines · Stephan Diestelhorst
Quoted 2 lines · On Wednesday 14 September 2011, 17:31:32 Jeremy Fitzhardinge wrote:
This series replaces the existing paravirtualized spinlock mechanism with a paravirtualized ticketlock mechanism.
[...]
Quoted 36 lines
The unlock code is very straightforward:
prev = *lock; __ticket_unlock_release(lock); if (unlikely(__ticket_in_slowpath(lock))) __ticket_unlock_slowpath(lock, prev);which generates:
push %rbp mov %rsp,%rbp movzwl (%rdi),%esi addb $0x2,(%rdi) movzwl (%rdi),%eax testb $0x1,%ah jne 1f pop %rbp retq ### SLOWPATH START1: movzwl (%rdi),%edx
movzbl %dh,%ecx
mov %edx,%eax
and $-2,%ecx # clearTICKET_SLOWPATH_FLAG
mov %cl,%dh
cmp %dl,%cl # test to see if lock is uncontended
je 3f2: movzbl %dl,%esi
callq*__ticket_unlock_kick# kick anyone waiting
pop %rbp
retq3: lock cmpxchg %dx,(%rdi) # use cmpxchg to safely write back flag
jmp 2b
### SLOWPATH END[...]
Quoted 1 line
Thoughts? Comments? Suggestions?
You have a nasty data race in your code that can cause a losing acquirer to sleep forever, because its setting the
TICKET_SLOWPATHflag can race with the lock holder releasing the lock.I used the code for the slow path from the GIT repo.
Let me try to point out an interleaving:
Lock is held by one thread, contains
0x0200.
_Lockholder__Acquirer_mov $0x200,%eax lock xadd %ax,(%rdi) // ax:= 0x0200, lock:= 0x0400 ... // this guy spins for a while, reading // the lock ...//trying to free the lock
movzwl (%rdi),%esi (esi:=0x0400)
addb $0x2,(%rdi) (LOCAL copy of lock is now:0x0402)
movzwl (%rdi),%eax (local forwarding from previous store: eax :=0x0402)
testb $0x1,%ah (no wakeup of anybody)
jne 1fcallq *__ticket_lock_spinning ... // __ticket_enter_slowpath(lock) lock or (%rdi), $0x100 // (global view of lock := 0x0500) ... ACCESS_ONCE(lock->tickets.head) == want // (reads 0x00) ... xen_poll_irq(irq); // goes to sleep...
[addb $0x2,(%rdi)]
// (becomes globally visible only now! global view of lock :=0x0502)
...
Quoted 7 lines
Your code is reusing the (just about) safe version of unlocking a spinlock without understanding the effect that close has on later memory ordering. It may work on CPUs that cannot do narrow -> wide store to load forwarding and have to make the addb store visible globally. This is an implementation artifact of specific uarches, and you mustn't rely on it, since our specified memory model allows looser behaviour.
Ah, thanks for this observation. I've seen this bug before when I didn't pay attention to the unlock W vs flag R ordering at all, and I was hoping the aliasing would be sufficient - and certainly this seems to have been OK on my Intel systems. But you're saying that it will fail on current AMD systems? Have you tested this, or is this just from code analysis (which I agree with after reviewing the ordering rules in the Intel manual).
Quoted 4 lines
Since you want to get that addb out to global memory before the second read, either use a LOCK prefix for it, add an MFENCE between addb and movzwl, or use a LOCKed instruction that will have a fencing effect (e.g., to top-of-stack)between addb and movzwl.
Hm. I don't really want to do any of those because it will probably have a significant effect on the unlock performance; I was really trying to avoid adding any more locked instructions. A previous version of the code had an mfence in here, but I hit on the idea of using aliasing to get the ordering I want - but overlooked the possible effect of store forwarding.
I guess it comes down to throwing myself on the efficiency of some kind of fence instruction. I guess an lfence would be sufficient; is that any more efficient than a full mfence? At least I can make it so that its only present when pv ticket locks are actually in use, so it won't affect the native case.
Could you give me a pointer to AMD's description of the ordering rules?
Thanks,
J
Quoted 91 lines · On Tuesday 27 September 2011, 12:44:02 Jeremy Fitzhardinge wrote:
Quoted 82 lines · Stephan Diestelhorst
Quoted 2 lines · On Wednesday 14 September 2011, 17:31:32 Jeremy Fitzhardinge wrote:
This series replaces the existing paravirtualized spinlock mechanism with a paravirtualized ticketlock mechanism.
[...]
Quoted 36 lines
The unlock code is very straightforward:
prev = *lock; __ticket_unlock_release(lock); if (unlikely(__ticket_in_slowpath(lock))) __ticket_unlock_slowpath(lock, prev);which generates:
push %rbp mov %rsp,%rbp movzwl (%rdi),%esi addb $0x2,(%rdi) movzwl (%rdi),%eax testb $0x1,%ah jne 1f pop %rbp retq ### SLOWPATH START1: movzwl (%rdi),%edx
movzbl %dh,%ecx
mov %edx,%eax
and $-2,%ecx # clearTICKET_SLOWPATH_FLAG
mov %cl,%dh
cmp %dl,%cl # test to see if lock is uncontended
je 3f2: movzbl %dl,%esi
callq*__ticket_unlock_kick# kick anyone waiting
pop %rbp
retq3: lock cmpxchg %dx,(%rdi) # use cmpxchg to safely write back flag
jmp 2b
### SLOWPATH END[...]
Quoted 1 line
Thoughts? Comments? Suggestions?
You have a nasty data race in your code that can cause a losing acquirer to sleep forever, because its setting the
TICKET_SLOWPATHflag can race with the lock holder releasing the lock.I used the code for the slow path from the GIT repo.
Let me try to point out an interleaving:
Lock is held by one thread, contains
0x0200.
_Lockholder__Acquirer_mov $0x200,%eax lock xadd %ax,(%rdi) // ax:= 0x0200, lock:= 0x0400 ... // this guy spins for a while, reading // the lock ...//trying to free the lock
movzwl (%rdi),%esi (esi:=0x0400)
addb $0x2,(%rdi) (LOCAL copy of lock is now:0x0402)
movzwl (%rdi),%eax (local forwarding from previous store: eax :=0x0402)
testb $0x1,%ah (no wakeup of anybody)
jne 1fcallq *__ticket_lock_spinning ... // __ticket_enter_slowpath(lock) lock or (%rdi), $0x100 // (global view of lock := 0x0500) ... ACCESS_ONCE(lock->tickets.head) == want // (reads 0x00) ... xen_poll_irq(irq); // goes to sleep...
[addb $0x2,(%rdi)]
// (becomes globally visible only now! global view of lock :=0x0502)
...Quoted 7 lines
Your code is reusing the (just about) safe version of unlocking a spinlock without understanding the effect that close has on later memory ordering. It may work on CPUs that cannot do narrow -> wide store to load forwarding and have to make the addb store visible globally. This is an implementation artifact of specific uarches, and you mustn't rely on it, since our specified memory model allows looser behaviour.
Quoted 5 lines
Ah, thanks for this observation. I've seen this bug before when I didn't pay attention to the unlock W vs flag R ordering at all, and I was hoping the aliasing would be sufficient - and certainly this seems to have been OK on my Intel systems. But you're saying that it will fail on current AMD systems?
I have tested this and have not seen it fail on publicly released AMD systems. But as I have tried to point out, this does not mean it is safe to do in software, because future microarchtectures may have more capable forwarding engines.
Quoted 2 lines
Have you tested this, or is this just from code analysis (which I agree with after reviewing the ordering rules in the Intel manual).
We have found a similar issue in Novell's PV ticket lock implementation during internal product testing.
Quoted 11 lines
Quoted 4 lines
Since you want to get that addb out to global memory before the second read, either use a LOCK prefix for it, add an MFENCE between addb and movzwl, or use a LOCKed instruction that will have a fencing effect (e.g., to top-of-stack)between addb and movzwl.
Hm. I don't really want to do any of those because it will probably have a significant effect on the unlock performance; I was really trying to avoid adding any more locked instructions. A previous version of the code had an mfence in here, but I hit on the idea of using aliasing to get the ordering I want - but overlooked the possible effect of store forwarding.
Well, I'd be curious about the actual performance impact. If the store needs to commit to memory due to aliasing anyways, this would slow down execution, too. After all it is better to write working than fast code, no? ;-)
Quoted 3 lines
I guess it comes down to throwing myself on the efficiency of some kind of fence instruction. I guess an lfence would be sufficient; is that any more efficient than a full mfence?
An lfence should not be sufficient, since that essentially is a NOP on WB memory. You really want a full fence here, since the store needs to be published before reading the lock with the next load.
Quoted 2 lines
At least I can make it so that its only present when pv ticket locks are actually in use, so it won't affect the native case.
That would be a good thing, indeed. Of course, always relative to an actual performance comparison.
Quoted 1 line
Could you give me a pointer to AMD's description of the ordering rules?
They should be in "AMD64 Architecture Programmer's Manual Volume 2:
System Programming", Section 7.2 Multiprocessor Memory Access Ordering.
http://developer.amd.com/documentation/guides/pages/default.aspx#manuals
Let me know if you have some clarifying suggestions. We are currently revising these documents...
Cheers,
Stephan
Signature · 12 lines
Stephan Diestelhorst, AMD Operating System Research Center [email protected] Tel. +49 (0)351 448 356 719 Advanced Micro Devices GmbH Einsteinring 24 85609 Aschheim Germany Geschaeftsfuehrer: Alberto Bozzo Sitz: Dornach, Gemeinde Aschheim, Landkreis Muenchen Registergericht Muenchen, HRB Nr. 43632, WEEE-Reg-Nr: DE 12919551
Quoted 6 lines · Jeremy Fitzhardinge
I guess it comes down to throwing myself on the efficiency of some kind of fence instruction. I guess an lfence would be sufficient; is that any more efficient than a full mfence? At least I can make it so that its only present when pv ticket locks are actually in use, so it won't affect the native case.
Please don't play with fences, just do the final "addb" as a locked instruction.
In fact, don't even use an addb, this whole thing is disgusting:
movzwl (%rdi),%esi (esi:=0x0400)
addb $0x2,(%rdi) (LOCAL copy of lock is now: 0x0402)
movzwl (%rdi),%eax (local forwarding from previous store: eax := 0x0402)
just use "lock xaddw" there too.
The fact that the PV unlock is going to be much more expensive than a regular native unlock is just a fact of life. It comes from fundamentally caring about the old/new value, and has nothing to do with aliasing. You care about the other bits, and it doesn't matter where in memory they are.
The native unlock can do a simple "addb" (or incb), but that doesn't mean the PV unlock can. There are no ordering issues with the final unlock in the native case, because the native unlock is like the honey
badger: it don't care. It only cares that the store make it out *some* day, but it doesn't care about what order the upper/lower bits get updated. You do. So you have to use a locked access.
Good catch by Stephan.
Linus
Quoted 12 lines
Quoted 1 line
Quoted 1 line · Linus Torvalds
Quoted 6 lines · Jeremy Fitzhardinge
I guess it comes down to throwing myself on the efficiency of some kind of fence instruction. I guess an lfence would be sufficient; is that any more efficient than a full mfence? At least I can make it so that its only present when pv ticket locks are actually in use, so it won't affect the native case.
Please don't play with fences, just do the final "addb" as a locked instruction.
Quoted 7 lines
In fact, don't even use an addb, this whole thing is disgusting:
movzwl (%rdi),%esi (esi:=0x0400)
addb $0x2,(%rdi) (LOCAL copy of lock is now:0x0402)
movzwl (%rdi),%eax (local forwarding from previous store: eax :=0x0402)just use "lock xaddw" there too.
I'm afraid that's not possible, as that might carry from the low 8 bits into the upper 8 ones, which must be avoided.
Jan
Quoted 5 lines · Jan Beulich
Quoted 2 lines
just use "lock xaddw" there too.
I'm afraid that's not possible, as that might carry from the low 8 bits into the upper 8 ones, which must be avoided.
Oh damn, you're right. So I guess the "right" way to do things is with cmpxchg, but some nasty mfence setup could do it too.
Linus
Quoted 4 lines · Stephan Diestelhorst
I have tested this and have not seen it fail on publicly released AMD systems. But as I have tried to point out, this does not mean it is safe to do in software, because future microarchtectures may have more capable forwarding engines.
Sure.
Quoted 4 lines
Quoted 2 lines
Have you tested this, or is this just from code analysis (which I agree with after reviewing the ordering rules in the Intel manual).
We have found a similar issue in Novell's PV ticket lock implementation during internal product testing.
Jan may have picked it up from an earlier set of my patches.
Quoted 10 lines
Quoted 10 lines
Quoted 4 lines
Since you want to get that addb out to global memory before the second read, either use a LOCK prefix for it, add an MFENCE between addb and movzwl, or use a LOCKed instruction that will have a fencing effect (e.g., to top-of-stack)between addb and movzwl.
Hm. I don't really want to do any of those because it will probably have a significant effect on the unlock performance; I was really trying to avoid adding any more locked instructions. A previous version of the code had an mfence in here, but I hit on the idea of using aliasing to get the ordering I want - but overlooked the possible effect of store forwarding.
Quoted 4 lines
Well, I'd be curious about the actual performance impact. If the store needs to commit to memory due to aliasing anyways, this would slow down execution, too. After all it is better to write working than fast code, no? ;-)
Rule of thumb is that AMD tends to do things like lock and fence more efficiently than Intel - at least historically. I don't know if that's still true for current Intel microarchitectures.
Quoted 6 lines
Quoted 3 lines
I guess it comes down to throwing myself on the efficiency of some kind of fence instruction. I guess an lfence would be sufficient; is that any more efficient than a full mfence?
An lfence should not be sufficient, since that essentially is a NOP on WB memory. You really want a full fence here, since the store needs to be published before reading the lock with the next load.
The Intel manual reads:
Reads cannot pass earlier LFENCE and MFENCE instructions. Writes cannot pass earlier LFENCE, SFENCE, and MFENCE instructions. LFENCE instructions cannot pass earlier reads.
Which I interpreted as meaning that an lfence would prevent forwarding. But I guess it doesn't say "lfence instructions cannot pass earlier writes", which means that the lfence could logically happen before the write, thereby allowing forwarding? Or should I be reading this some other way?
Quoted 8 lines
Quoted 1 line
Could you give me a pointer to AMD's description of the ordering rules?
They should be in "AMD64 Architecture Programmer's Manual Volume 2:
System Programming", Section 7.2 Multiprocessor Memory Access Ordering.http://developer.amd.com/documentation/guides/pages/default.aspx#manuals
Let me know if you have some clarifying suggestions. We are currently revising these documents...
I find the English descriptions of these kinds of things frustrating to read because of ambiguities in the precise meaning of words like "pass", "ahead", "behind" in these contexts. I find the prose useful to get an overview, but when I have a specific question I wonder if something more formal would be useful.
I guess it's implied that anything that is not prohibited by the ordering rules is allowed, but it wouldn't hurt to say it explicitly. That said, the AMD description seems clearer and more explicit than the Intel manual (esp since it specifically discusses the problem here).
Thanks,
J
Quoted 6 lines · Linus Torvalds
Quoted 3 lines · Jan Beulich
Quoted 1 line
just use "lock xaddw" there too.
I'm afraid that's not possible, as that might carry from the low 8 bits into the upper 8 ones, which must be avoided.
Oh damn, you're right. So I guess the "right" way to do things is with cmpxchg, but some nasty mfence setup could do it too.
Could do something like:
if (ticket->head >= 254) prev = xadd(&ticket->head_tail, 0xff02); else prev = xadd(&ticket->head_tail, 0x0002);
to compensate for the overflow.
J
Quoted 9 lines · Jeremy Fitzhardinge
Could do something like:
if (
ticket->head>= 254)
prev =xadd(&ticket->head_tail, 0xff02); else
prev =xadd(&ticket->head_tail, 0x0002);to compensate for the overflow.
Oh wow. You havge an even more twisted mind than I do.
I guess that will work, exactly because we control "head" and thus can know about the overflow in the low byte. But boy is that ugly ;)
But at least you wouldn't need to do the loop with cmpxchg. So it's twisted and ugly, but migth be practical.
Linus
H. Peter Anvin
reviewerQuoted 11 lines · Linus Torvalds
Quoted 9 lines · Jeremy Fitzhardinge
Could do something like:
if (ticket->head >= 254) prev = xadd(&ticket->head_tail, 0xff02); else prev = xadd(&ticket->head_tail, 0x0002);to compensate for the overflow.
Quoted 8 lines
Oh wow. You havge an even more twisted mind than I do.
I guess that will work, exactly because we control "head" and thus can know about the overflow in the low byte. But boy is that ugly ;)
But at least you wouldn't need to do the loop with cmpxchg. So it's twisted and ugly, but migth be practical.
I suspect it should be coded as -254 in order to use a short immediate if that is even possible...
-hpa
Signature · 2 lines
H. Peter Anvin, Intel Open Source Technology Center I work for Intel. I don't speak on their behalf.
Quoted 12 lines · H. Peter Anvin
Quoted 11 lines · Linus Torvalds
Quoted 8 lines · Jeremy Fitzhardinge
Could do something like:
if (ticket->head >= 254) prev = xadd(&ticket->head_tail, 0xff02); else prev = xadd(&ticket->head_tail, 0x0002);to compensate for the overflow.
Oh wow. You havge an even more twisted mind than I do.
Quoted 8 lines
Quoted 6 lines
I guess that will work, exactly because we control "head" and thus can know about the overflow in the low byte. But boy is that ugly ;)
But at least you wouldn't need to do the loop with cmpxchg. So it's twisted and ugly, but migth be practical.
I suspect it should be coded as -254 in order to use a short immediate if that is even possible...
I'm about to test:
static __always_inline void arch_spin_unlock(arch_spinlock_t *lock)
{
if (TICKET_SLOWPATH_FLAG && unlikely(arch_static_branch(¶virt_ticketlocks_enabled))) {
arch_spinlock_t prev;
__ticketpair_t inc = TICKET_LOCK_INC;
if (lock->tickets.head >= (1 << TICKET_SHIFT) - TICKET_LOCK_INC)
inc += -1 << TICKET_SHIFT;
prev.head_tail = xadd(&lock->head_tail, inc);
if (prev.tickets.tail & TICKET_SLOWPATH_FLAG)
__ticket_unlock_slowpath(lock, prev);
} else
__ticket_unlock_release(lock);
}Which, frankly, is not something I particularly want to put my name to.
It makes gcc go into paroxysms of trickiness:
4a8: 80 3f fe cmpb $0xfe,(%rdi) 4ab: 19 f6 sbb %esi,%esi 4ad: 66 81 e6 00 01 and $0x100,%si 4b2: 66 81 ee fe 00 sub $0xfe,%si 4b7: f0 66 0f c1 37 lock xadd %si,(%rdi)
...which is pretty neat, actually.
J
Quoted 41 lines · On Wednesday 28 September 2011 19:50:08 Jeremy Fitzhardinge wrote:
Quoted 12 lines · H. Peter Anvin
Quoted 11 lines · Linus Torvalds
Quoted 8 lines · Jeremy Fitzhardinge
Could do something like:
if (ticket->head >= 254) prev = xadd(&ticket->head_tail, 0xff02); else prev = xadd(&ticket->head_tail, 0x0002);to compensate for the overflow.
Oh wow. You havge an even more twisted mind than I do.
Quoted 8 lines
Quoted 6 lines
I guess that will work, exactly because we control "head" and thus can know about the overflow in the low byte. But boy is that ugly ;)
But at least you wouldn't need to do the loop with cmpxchg. So it's twisted and ugly, but migth be practical.
I suspect it should be coded as -254 in order to use a short immediate if that is even possible...
I'm about to test:
static
__always_inlinevoidarch_spin_unlock(arch_spinlock_t *lock){ if (TICKET_SLOWPATH_FLAG && unlikely(arch_static_branch(¶virt_ticketlocks_enabled))) { arch_spinlock_t prev; __ticketpair_t inc = TICKET_LOCK_INC; if (lock->tickets.head >= (1 << TICKET_SHIFT) - TICKET_LOCK_INC) inc += -1 << TICKET_SHIFT; prev.head_tail = xadd(&lock->head_tail, inc); if (prev.tickets.tail & TICKET_SLOWPATH_FLAG) __ticket_unlock_slowpath(lock, prev); } else __ticket_unlock_release(lock); }
Quoted 1 line
Which, frankly, is not something I particularly want to put my name to.
I must have missed the part when this turned into the propose-the- craziest-way-that-this-still-works.contest :)
What is wrong with converting the original addb into a lock addb? The crazy wrap around tricks add a conditional and lots of headache. The lock addb/w is clean. We are paying an atomic in both cases, so I just don't see the benefit of the second solution.
Stephan
Signature · 11 lines
Stephan Diestelhorst, AMD Operating System Research Center [email protected], Tel. +49 (0)351 448 356 719 Advanced Micro Devices GmbH Einsteinring 24 85609 Aschheim Germany Geschaeftsfuehrer: Alberto Bozzo; Sitz: Dornach, Gemeinde Aschheim, Landkreis Muenchen Registergericht Muenchen, HRB Nr. 43632, WEEE-Reg-Nr: DE 12919551
Quoted 14 lines · On Wednesday 28 September 2011 18:44:25 Jeremy Fitzhardinge wrote:
Quoted 6 lines · Stephan Diestelhorst
Quoted 3 lines
I guess it comes down to throwing myself on the efficiency of some kind of fence instruction. I guess an lfence would be sufficient; is that any more efficient than a full mfence?
An lfence should not be sufficient, since that essentially is a NOP on WB memory. You really want a full fence here, since the store needs to be published before reading the lock with the next load.
The Intel manual reads:
Reads cannot pass earlier LFENCE and MFENCE instructions. Writes cannot pass earlier LFENCE, SFENCE, and MFENCE instructions. LFENCE instructions cannot pass earlier reads.
Quoted 5 lines
Which I interpreted as meaning that an lfence would prevent forwarding. But I guess it doesn't say "lfence instructions cannot pass earlier writes", which means that the lfence could logically happen before the write, thereby allowing forwarding? Or should I be reading this some other way?
Indeed. You are reading this the right way.
Quoted 6 lines
Quoted 6 lines
Quoted 1 line
Could you give me a pointer to AMD's description of the ordering rules?
They should be in "AMD64 Architecture Programmer's Manual Volume 2:
System Programming", Section 7.2 Multiprocessor Memory Access Ordering.http://developer.amd.com/documentation/guides/pages/default.aspx#manuals
Quoted 8 lines
Quoted 2 lines
Let me know if you have some clarifying suggestions. We are currently revising these documents...
I find the English descriptions of these kinds of things frustrating to read because of ambiguities in the precise meaning of words like "pass", "ahead", "behind" in these contexts. I find the prose useful to get an overview, but when I have a specific question I wonder if something more formal would be useful.
It would be, and some have started this efort:
http://www.cl.cam.ac.uk/~pes20/weakmemory/
But I am not sure whether that particular nasty forwarding case is captured properly in their model It is on my list of things to check.
Quoted 4 lines
I guess it's implied that anything that is not prohibited by the ordering rules is allowed, but it wouldn't hurt to say it explicitly. That said, the AMD description seems clearer and more explicit than the Intel manual (esp since it specifically discusses the problem here).
Thanks! Glad you like it :)
Stephan
Signature · 11 lines
Stephan Diestelhorst, AMD Operating System Research Center [email protected], Tel. +49 (0)351 448 356 719 Advanced Micro Devices GmbH Einsteinring 24 85609 Aschheim Germany Geschaeftsfuehrer: Alberto Bozzo; Sitz: Dornach, Gemeinde Aschheim, Landkreis Muenchen Registergericht Muenchen, HRB Nr. 43632, WEEE-Reg-Nr: DE 12919551
Quoted 41 lines · Stephan Diestelhorst
Quoted 40 lines · On Wednesday 28 September 2011 19:50:08 Jeremy Fitzhardinge wrote:
Quoted 12 lines · H. Peter Anvin
Quoted 11 lines · Linus Torvalds
Quoted 8 lines · Jeremy Fitzhardinge
Could do something like:
if (ticket->head >= 254) prev = xadd(&ticket->head_tail, 0xff02); else prev = xadd(&ticket->head_tail, 0x0002);to compensate for the overflow.
Oh wow. You havge an even more twisted mind than I do.
Quoted 8 lines
Quoted 6 lines
I guess that will work, exactly because we control "head" and thus can know about the overflow in the low byte. But boy is that ugly ;)
But at least you wouldn't need to do the loop with cmpxchg. So it's twisted and ugly, but migth be practical.
I suspect it should be coded as -254 in order to use a short immediate if that is even possible...
I'm about to test:
static
__always_inlinevoidarch_spin_unlock(arch_spinlock_t *lock){ if (TICKET_SLOWPATH_FLAG && unlikely(arch_static_branch(¶virt_ticketlocks_enabled))) { arch_spinlock_t prev; __ticketpair_t inc = TICKET_LOCK_INC; if (lock->tickets.head >= (1 << TICKET_SHIFT) - TICKET_LOCK_INC) inc += -1 << TICKET_SHIFT; prev.head_tail = xadd(&lock->head_tail, inc); if (prev.tickets.tail & TICKET_SLOWPATH_FLAG) __ticket_unlock_slowpath(lock, prev); } else __ticket_unlock_release(lock); }
Quoted 8 lines
Quoted 1 line
Which, frankly, is not something I particularly want to put my name to.
I must have missed the part when this turned into the propose-the- craziest-way-that-this-still-works.contest :)
What is wrong with converting the original addb into a lock addb? The crazy wrap around tricks add a conditional and lots of headache. The lock addb/w is clean. We are paying an atomic in both cases, so I just don't see the benefit of the second solution.
Well, it does end up generating surprisingly nice code. And to be honest, being able to do the unlock and atomically fetch the flag as one operation makes it much easier to reason about.
I'll do a locked add variant as well to see how it turns out.
Do you think locked add is better than unlocked + mfence?
Thanks,
J
Quoted 3 lines · Stephan Diestelhorst
I must have missed the part when this turned into the propose-the- craziest-way-that-this-still-works.contest :)
So doing it just with the "lock addb" probably works fine, but I have to say that I personally shudder at the "surround the locked addb by reads from the word, in order to approximate an atomic read of the upper bits".
Because what you get is not really an "atomic read of the upper bits", it's a "ok, we'll get the worst case of somebody modifying the upper bits at the same time".
Which certainly should *work*, but from a conceptual standpoint, isn't it just *much* nicer to say "we actually know *exactly* what the upper bits were".
But I don't care all *that* deeply. I do agree that the xaddw trick is pretty tricky. I just happen to think that it's actually *less* tricky than "read the upper bits separately and depend on subtle ordering issues with another writer that happens at the same time on another CPU".
So I can live with either form - as long as it works. I think it might be easier to argue that the xaddw is guaranteed to work, because all values at all points are unarguably atomic (yeah, we read the lower bits nonatomically, but as the owner of the lock we know that nobody else can write them).
Linus
Quoted 11 lines · Linus Torvalds
But I don't care all *that* deeply. I do agree that the xaddw trick is pretty tricky. I just happen to think that it's actually *less* tricky than "read the upper bits separately and depend on subtle ordering issues with another writer that happens at the same time on another CPU".
So I can live with either form - as long as it works. I think it might be easier to argue that the xaddw is guaranteed to work, because all values at all points are unarguably atomic (yeah, we read the lower bits nonatomically, but as the owner of the lock we know that nobody else can write them).
Exactly. I just did a locked add variant, and while the code looks a little simpler, it definitely has more actual complexity to analyze.
J
Quoted 11 lines · On Wednesday 28 September 2011, 14:49:56 Linus Torvalds wrote:
Quoted 3 lines · Stephan Diestelhorst
I must have missed the part when this turned into the propose-the- craziest-way-that-this-still-works.contest :)
So doing it just with the "lock addb" probably works fine, but I have to say that I personally shudder at the "surround the locked addb by reads from the word, in order to approximate an atomic read of the upper bits".
Quoted 7 lines
Because what you get is not really an "atomic read of the upper bits", it's a "ok, we'll get the worst case of somebody modifying the upper bits at the same time".
Which certainly should *work*, but from a conceptual standpoint, isn't it just *much* nicer to say "we actually know *exactly* what the upper bits were".
Well, we really do NOT want atomicity here. What we really rather want is sequentiality: free the lock, make the update visible, and THEN check if someone has gone sleeping on it.
Atomicity only conveniently enforces that the three do not happen in a different order (with the store becoming visible after the checking load).
This does not have to be atomic, since spurious wakeups are not a problem, in particular not with the FIFO-ness of ticket locks.
For that the fence, additional atomic etc. would be IMHO much cleaner than the crazy overflow logic.
Quoted 5 lines
But I don't care all *that* deeply. I do agree that the xaddw trick is pretty tricky. I just happen to think that it's actually *less* tricky than "read the upper bits separately and depend on subtle ordering issues with another writer that happens at the same time on another CPU".
Fair enough :)
Stephan
Signature · 12 lines
Stephan Diestelhorst, AMD Operating System Research Center [email protected] Tel. +49 (0)351 448 356 719 Advanced Micro Devices GmbH Einsteinring 24 85609 Aschheim Germany Geschaeftsfuehrer: Alberto Bozzo Sitz: Dornach, Gemeinde Aschheim, Landkreis Muenchen Registergericht Muenchen, HRB Nr. 43632, WEEE-Reg-Nr: DE 12919551
Quoted 12 lines · Stephan Diestelhorst
Quoted 3 lines · On Wednesday 28 September 2011, 14:49:56 Linus Torvalds wrote:
Which certainly should *work*, but from a conceptual standpoint, isn't it just *much* nicer to say "we actually know *exactly* what the upper bits were".
Well, we really do NOT want atomicity here. What we really rather want is sequentiality: free the lock, make the update visible, and THEN check if someone has gone sleeping on it.
Atomicity only conveniently enforces that the three do not happen in a different order (with the store becoming visible after the checking load).
Quoted 5 lines
This does not have to be atomic, since spurious wakeups are not a problem, in particular not with the FIFO-ness of ticket locks.
For that the fence, additional atomic etc. would be IMHO much cleaner than the crazy overflow logic.
All things being equal I'd prefer lock-xadd just because its easier to analyze the concurrency for, crazy overflow tests or no. But if add+mfence turned out to be a performance win, then that would obviously tip the scales.
However, it looks like locked xadd is also has better performance: on my Sandybridge laptop (2 cores, 4 threads), the add+mfence is 20% slower than locked xadd, so that pretty much settles it unless you think there'd be a dramatic difference on an AMD system.
(On Nehalem it was much less dramatic 2% difference, but still in favour of locked xadd.)
This is with dumb-as-rocks run it in a loop with "time" benchmark, but the results are not very subtle.
J
#include <stdio.h>
struct {
unsigned char flag;
unsigned char val;
} l;int main(int argc, char **argv)
{
int i;
for (i = 0; i < 100000000; i++) {
l.val += 2;
asm volatile("mfence" : : : "memory");
if (l.flag)
break;
asm volatile("" : : : "memory");
}
return 0;
}#include <stdio.h>
union {
struct {
unsigned char val;
unsigned char flag;
};
unsigned short lock;
} l = { 0,0 };int main(int argc, char **argv)
{
int i;
for (i = 0; i < 100000000; i++) {
unsigned short inc = 2;
if (l.val >= (0x100 - 2))
inc += -1 << 8;
asm volatile("lock; xadd %1,%0" : "+m" (l.lock), "+r" (inc) : );
if (inc & 0x100)
break;
asm volatile("" : : : "memory");
}
return 0;
}Quoted 4 lines · Jeremy Fitzhardinge
However, it looks like locked xadd is also has better performance: on my Sandybridge laptop (2 cores, 4 threads), the add+mfence is 20% slower than locked xadd, so that pretty much settles it unless you think there'd be a dramatic difference on an AMD system.
Konrad measures add+mfence is about 65% slower on AMD Phenom as well.
J
Quoted 7 lines · Jeremy Fitzhardinge
Quoted 4 lines · Jeremy Fitzhardinge
However, it looks like locked xadd is also has better performance: on my Sandybridge laptop (2 cores, 4 threads), the add+mfence is 20% slower than locked xadd, so that pretty much settles it unless you think there'd be a dramatic difference on an AMD system.
Konrad measures add+mfence is about 65% slower on AMD Phenom as well.
xadd also results in smaller/tighter code, right?
Thanks,
Ingo
Quoted 24 lines · On Thursday 06 October 2011, 13:40:01 Jeremy Fitzhardinge wrote:
Quoted 12 lines · Stephan Diestelhorst
Quoted 3 lines · On Wednesday 28 September 2011, 14:49:56 Linus Torvalds wrote:
Which certainly should *work*, but from a conceptual standpoint, isn't it just *much* nicer to say "we actually know *exactly* what the upper bits were".
Well, we really do NOT want atomicity here. What we really rather want is sequentiality: free the lock, make the update visible, and THEN check if someone has gone sleeping on it.
Atomicity only conveniently enforces that the three do not happen in a different order (with the store becoming visible after the checking load).
Quoted 5 lines
This does not have to be atomic, since spurious wakeups are not a problem, in particular not with the FIFO-ness of ticket locks.
For that the fence, additional atomic etc. would be IMHO much cleaner than the crazy overflow logic.
All things being equal I'd prefer lock-xadd just because its easier to analyze the concurrency for, crazy overflow tests or no. But if add+mfence turned out to be a performance win, then that would obviously tip the scales.
Quoted 4 lines
However, it looks like locked xadd is also has better performance: on my Sandybridge laptop (2 cores, 4 threads), the add+mfence is 20% slower than locked xadd, so that pretty much settles it unless you think there'd be a dramatic difference on an AMD system.
Indeed, the fences are usually slower than locked RMWs, in particular, if you do not need to add an instruction. I originally missed that amazing stunt the GCC pulled off with replacing the branch with carry flag magic. It seems that two twisted minds have found each other here :)
One of my concerns was adding a branch in here... so that is settled, and if everybody else feels like this is easier to reason about... go ahead :) (I'll keep my itch to myself then.)
Stephan
Signature · 11 lines
Stephan Diestelhorst, AMD Operating System Research Center [email protected], Tel. +49 (0)351 448 356 719 Advanced Micro Devices GmbH Einsteinring 24 85609 Aschheim Germany Geschaeftsfuehrer: Alberto Bozzo; Sitz: Dornach, Gemeinde Aschheim, Landkreis Muenchen Registergericht Muenchen, HRB Nr. 43632, WEEE-Reg-Nr: DE 12919551
Quoted 36 lines · On Monday 10 October 2011, 07:00:50 Stephan Diestelhorst wrote:
Quoted 24 lines · On Thursday 06 October 2011, 13:40:01 Jeremy Fitzhardinge wrote:
Quoted 12 lines · Stephan Diestelhorst
Quoted 3 lines · On Wednesday 28 September 2011, 14:49:56 Linus Torvalds wrote:
Which certainly should *work*, but from a conceptual standpoint, isn't it just *much* nicer to say "we actually know *exactly* what the upper bits were".
Well, we really do NOT want atomicity here. What we really rather want is sequentiality: free the lock, make the update visible, and THEN check if someone has gone sleeping on it.
Atomicity only conveniently enforces that the three do not happen in a different order (with the store becoming visible after the checking load).
Quoted 5 lines
This does not have to be atomic, since spurious wakeups are not a problem, in particular not with the FIFO-ness of ticket locks.
For that the fence, additional atomic etc. would be IMHO much cleaner than the crazy overflow logic.
All things being equal I'd prefer lock-xadd just because its easier to analyze the concurrency for, crazy overflow tests or no. But if add+mfence turned out to be a performance win, then that would obviously tip the scales.
Quoted 4 lines
However, it looks like locked xadd is also has better performance: on my Sandybridge laptop (2 cores, 4 threads), the add+mfence is 20% slower than locked xadd, so that pretty much settles it unless you think there'd be a dramatic difference on an AMD system.
Indeed, the fences are usually slower than locked RMWs, in particular, if you do not need to add an instruction. I originally missed that amazing stunt the GCC pulled off with replacing the branch with carry flag magic. It seems that two twisted minds have found each other here :)
Quoted 3 lines
One of my concerns was adding a branch in here... so that is settled, and if everybody else feels like this is easier to reason about... go ahead :) (I'll keep my itch to myself then.)
Just that I can't... if performance is a concern, adding the LOCK prefix to the addb outperforms the xadd significantly:
With mean over 100 runs... this comes out as follows (on my Phenom II)
locked-add 0.648500 s 80% add-rmwtos 0.707700 s 88% locked-xadd 0.807600 s 100% add-barrier 1.270000 s 157%
With huge read contention added in (as cheaply as possible):
locked-add.openmp 0.640700 s 84% add-rmwtos.openmp 0.658400 s 86%
locked-xadd.openmp 0.763800 s 100%
And the numbers for write contention are crazy, but also feature the locked-add version:
locked-add.openmp 0.571400 s 71% add-rmwtos.openmp 0.699900 s 87%
locked-xadd.openmp 0.800200 s 100%
Stephan
Signature · 11 lines
Stephan Diestelhorst, AMD Operating System Research Center [email protected], Tel. +49 (0)351 448 356 719 Advanced Micro Devices GmbH Einsteinring 24 85609 Aschheim Germany Geschaeftsfuehrer: Alberto Bozzo; Sitz: Dornach, Gemeinde Aschheim, Landkreis Muenchen Registergericht Muenchen, HRB Nr. 43632, WEEE-Reg-Nr: DE 12919551
#include <stdio.h>
struct {
unsigned char flag;
unsigned char val;
} l;int main(int argc, char **argv)
{
int i;
{
{
for (i = 0; i < 100000000; i++) {
l.val += 2;
asm volatile("lock or $0x0,(%%rsp)" : : : "memory");
if (l.flag)
break;
asm volatile("" : : : "memory");
}
l.flag = 1;
}
}
return 0;
}#include <stdio.h>
struct {
unsigned char flag;
unsigned char val;
} l;int main(int argc, char **argv)
{
int i;# pragma omp sections
{
# pragma omp section
{
for (i = 0; i < 100000000; i++) {
l.val += 2;
asm volatile("lock or $0x0,(%%rsp)" : : : "memory");
if (l.flag)
break;
asm volatile("" : : : "memory");
}
l.flag = 1;
}
# pragma omp section
while(!l.flag)
asm volatile("":::"memory");
//asm volatile("lock orb $0x0, %0"::"m"(l.flag):"memory");
}
return 0;
}#include <stdio.h>
struct {
unsigned char flag;
unsigned char val;
} l;int main(int argc, char **argv)
{
int i;
{
{
for (i = 0; i < 100000000; i++) {
asm volatile("lock addb %1, %0":"+m"(l.val):"r"((char)2):"memory");
if (l.flag)
break;
asm volatile("" : : : "memory");
}
l.flag = 1;
}
}
return 0;
}#include <stdio.h>
union {
struct {
unsigned char val;
unsigned char flag;
};
unsigned short lock;
} l = { 0,0 };int main(int argc, char **argv)
{
int i;
# pragma omp sections
{
# pragma omp section
{
for (i = 0; i < 100000000; i++) {
unsigned short inc = 2;
if (l.val >= (0x100 - 2))
inc += -1 << 8;
asm volatile("lock; xadd %1,%0" : "+m" (l.lock), "+r" (inc) : );
if (inc & 0x100)
break;
asm volatile("" : : : "memory");
}
l.flag = 1;
}
# pragma omp section
while(!l.flag)
asm volatile("":::"memory");
//asm volatile("lock orb $0x0, %0"::"m"(l.flag):"memory");
}
return 0;
}#include <stdio.h>
struct {
unsigned char flag;
unsigned char val;
} l;int main(int argc, char **argv)
{
int i;
# pragma omp sections
{
# pragma omp section
{
for (i = 0; i < 100000000; i++) {
asm volatile("lock addb %1, %0":"+m"(l.val):"r"((char)2):"memory");
if (l.flag)
break;
asm volatile("" : : : "memory");
}
l.flag = 1;
}
# pragma omp section
while(!l.flag)
asm volatile("":::"memory");
//asm volatile("lock orb $0x0, %0"::"m"(l.flag):"memory");
}
return 0;
}#include <stdio.h>
union {
struct {
unsigned char val;
unsigned char flag;
};
unsigned short lock;
} l = { 0,0 };int main(int argc, char **argv)
{
int i;
{
{
for (i = 0; i < 100000000; i++) {
unsigned short inc = 2;
if (l.val >= (0x100 - 2))
inc += -1 << 8;
asm volatile("lock; xadd %1,%0" : "+m" (l.lock), "+r" (inc) : );
if (inc & 0x100)
break;
asm volatile("" : : : "memory");
}
l.flag = 1;
}
}
return 0;
}Quoted 35 lines · Stephan Diestelhorst
Quoted 34 lines · On Monday 10 October 2011, 07:00:50 Stephan Diestelhorst wrote:
Quoted 23 lines · On Thursday 06 October 2011, 13:40:01 Jeremy Fitzhardinge wrote:
Quoted 12 lines · Stephan Diestelhorst
Quoted 3 lines · On Wednesday 28 September 2011, 14:49:56 Linus Torvalds wrote:
Which certainly should *work*, but from a conceptual standpoint, isn't it just *much* nicer to say "we actually know *exactly* what the upper bits were".
Well, we really do NOT want atomicity here. What we really rather want is sequentiality: free the lock, make the update visible, and THEN check if someone has gone sleeping on it.
Atomicity only conveniently enforces that the three do not happen in a different order (with the store becoming visible after the checking load).
Quoted 5 lines
This does not have to be atomic, since spurious wakeups are not a problem, in particular not with the FIFO-ness of ticket locks.
For that the fence, additional atomic etc. would be IMHO much cleaner than the crazy overflow logic.
All things being equal I'd prefer lock-xadd just because its easier to analyze the concurrency for, crazy overflow tests or no. But if add+mfence turned out to be a performance win, then that would obviously tip the scales.
Quoted 4 lines
However, it looks like locked xadd is also has better performance: on my Sandybridge laptop (2 cores, 4 threads), the add+mfence is 20% slower than locked xadd, so that pretty much settles it unless you think there'd be a dramatic difference on an AMD system.
Indeed, the fences are usually slower than locked RMWs, in particular, if you do not need to add an instruction. I originally missed that amazing stunt the GCC pulled off with replacing the branch with carry flag magic. It seems that two twisted minds have found each other here :)
Quoted 5 lines
Quoted 3 lines
One of my concerns was adding a branch in here... so that is settled, and if everybody else feels like this is easier to reason about... go ahead :) (I'll keep my itch to myself then.)
Just that I can't... if performance is a concern, adding the LOCK prefix to the addb outperforms the xadd significantly:
Hm, yes. So using the lock prefix on add instead of the mfence? Hm.
J
Quoted 9 lines · Ingo Molnar
Quoted 6 lines · Jeremy Fitzhardinge
Quoted 4 lines · Jeremy Fitzhardinge
However, it looks like locked xadd is also has better performance: on my Sandybridge laptop (2 cores, 4 threads), the add+mfence is 20% slower than locked xadd, so that pretty much settles it unless you think there'd be a dramatic difference on an AMD system.
Konrad measures add+mfence is about 65% slower on AMD Phenom as well.
xadd also results in smaller/tighter code, right?
Not particularly, mostly because of the overflow-into-the-high-part compensation. But its only a couple of extra instructions, and no conditionals, so I don't think it would have any concrete effect.
But, as Stephen points out, perhaps locked add is preferable to locked xadd, since it also has the same barrier as mfence but has (significantly!) better performance than either mfence or locked xadd...
J