Skip to contentSkip to conversation

Paravirtualized ticketlocks

RFC PATCH Superseded Jeremy Fitzhardinge 6 participants 35 messages Sep 15, 2011 – Oct 10, 2011

Subsystems (5)

v2 of 5 Superseded Latest is v5 →

lore
Share & tools
lore
#0 lore raw

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 START

1: 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
#1 lore raw

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
index f5695ee..972c260 100644
@@ -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
#2 lore raw

PATCH v2 2/10 x86/spinlocks: replace pv spinlocks with pv ticketlocks

In reply to Jeremy Fitzhardinge

From: 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
index a7d2db9..76cae7a 100644
@@ -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
index 8e8b9a4..005e24d 100644
@@ -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
index 8ebd5df..dbe223d 100644
@@ -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
index 676b8c7..c2e010e 100644
@@ -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
index cc9b1e1..23af06a 100644
@@ -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
#3 lore raw

PATCH v2 3/10 x86/ticketlock: don't inline _spin_unlock when using paravirt spinlocks

In reply to Jeremy Fitzhardinge

From: 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
index 6a47bb2..1f03f82 100644
@@ -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
index 5068e2a..584637b 100644
@@ -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
#4 lore raw

PATCH v2 4/10 x86/ticketlock: collapse a layer of functions

In reply to Jeremy Fitzhardinge

From: 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
index 860fc4b..98fe202 100644
@@ -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)
 {
 	register struct __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
#5 lore raw

PATCH v2 5/10 xen/pvticketlock: Xen implementation for PV ticket locks

In reply to Jeremy Fitzhardinge

From: 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
index 23af06a..f6133c5 100644
@@ -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
#6 lore raw

PATCH v2 6/10 x86/pvticketlock: use callee-save for lock_spinning

In reply to Jeremy Fitzhardinge

From: 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
index 76cae7a..50281c7 100644
@@ -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
index 005e24d..5e0c138 100644
@@ -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
index c2e010e..4251c1d 100644
@@ -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
index f6133c5..7a04950 100644
@@ -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
#7 lore raw

PATCH v2 7/10 x86/ticketlocks: when paravirtualizing ticket locks, increment by 2

In reply to Jeremy Fitzhardinge

From: 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
index 98fe202..40c90aa 100644
@@ -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)
 {
-	register struct __raw_tickets inc = { .tail = 1 };
+	register struct __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)
 {
-	asm volatile(UNLOCK_LOCK_PREFIX "incb %0"
+	asm volatile(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)
 {
-	asm volatile(UNLOCK_LOCK_PREFIX "incw %0"
+	asm volatile(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
index dbe223d..aa9a205 100644
@@ -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
#8 lore raw

PATCH v2 8/10 x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge

From: 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
index 50281c7..13b3d8b 100644
@@ -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
index aa9a205..407f7f7 100644
@@ -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
index 4251c1d..0883c48 100644
@@ -15,3 +15,4 @@ struct pv_lock_ops pv_lock_ops = {
 };
 EXPORT_SYMBOL(pv_lock_ops);
 
+
arch/x86/xen/spinlock.c +4 -0
index 7a04950..c939723 100644
@@ -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
#9 lore raw

PATCH v2 9/10 xen/pvticketlock: allow interrupts to be enabled while blocking

In reply to Jeremy Fitzhardinge

From: 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
index c939723..7366b39 100644
@@ -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
#10 lore raw

PATCH v2 10/10 xen: enable PV ticketlocks on HVM Xen

In reply to Jeremy Fitzhardinge

From: Stefano Stabellini <[email protected]>

---
 arch/x86/xen/smp.c |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)
arch/x86/xen/smp.c +1 -0
index e79dbb9..bf958ce 100644
@@ -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
#11 lore raw
In reply to Jeremy Fitzhardinge
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 START

1: 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

[...]

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
#12 lore raw
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 START

1: 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

[...]

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)
...

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

#13 lore raw
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 START

1: 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

[...]

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)
...

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
#16 lore raw
In reply to Jeremy Fitzhardinge
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

#17 lore raw
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

#18 lore raw
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

#14 lore raw
In reply to Stephan Diestelhorst
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

#19 lore raw
In reply to Linus Torvalds
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

#20 lore raw
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

#21 lore raw
Quoted 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.
#22 lore raw
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(&paravirt_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

#23 lore raw
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_inline void arch_spin_unlock(arch_spinlock_t *lock)

{
	if (TICKET_SLOWPATH_FLAG && unlikely(arch_static_branch(&paravirt_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 
#15 lore raw
In reply to Jeremy Fitzhardinge
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 
#24 lore raw
In reply to Stephan Diestelhorst
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_inline void arch_spin_unlock(arch_spinlock_t *lock)

{
	if (TICKET_SLOWPATH_FLAG && unlikely(arch_static_branch(&paravirt_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

#25 lore raw
In reply to Stephan Diestelhorst
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

#26 lore raw
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

#27 lore raw
In reply to Linus Torvalds
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
#28 lore raw
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;
}
#29 lore raw
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

#30 lore raw
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

#32 lore raw
In reply to Jeremy Fitzhardinge
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 
#33 lore raw
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;
}
#34 lore raw
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

#31 lore raw
In reply to Ingo Molnar
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