Skip to contentSkip to conversation

PV ticket locks without expanding spinlock

PATCH In review Jeremy Fitzhardinge 7 participants 120 messages Nov 16, 2010 – Feb 18, 2011

Subsystems (9)
x86 KVM Driver core virtio core +5 more subsystems
lore
Share & tools
lore
#0 lore raw

cover PV ticket locks without expanding spinlock

From: Jeremy Fitzhardinge <[email protected]>

Hi all,

This is a revised version of the pvticket lock series.

The early part of the series is mostly unchanged: it converts the bulk of the ticket lock code into C and makes the "small" and "large" ticket code common. The only changes are the incorporation of various review comments.

The latter part of the series converts from pv spinlocks to pv ticket locks (ie, using the ticket lock fastpath as-is, but adding pv ops for the ticketlock slowpaths).

The significant difference here is that rather than adding a new ticket_t-sized element to arch_spinlock_t - effectively doubling the size - I steal the LSB of the tickets themselves to store a bit. This allows the structure to remain the same size, but at the cost of halving the max number of CPUs (127 for a 8-bit ticket, and a hard max of 32767 overall).

The extra bit (well, two, but one is unused) in indicates whether the lock has gone into "slowpath state", which means one of its lockers has entered its slowpath and has blocked in the hypervisor. This means the current lock-holder needs to make sure it gets kicked out of the hypervisor on unlock.

The spinlock remains in slowpath state until the last unlock happens (ie there are no more queued lockers).

This code survives for a while with moderate testing, (make -j 100 on 8 VCPUs on a 4 PCPU system), but locks up after about 20 iterations, so there's still some race/deadlock in there (probably something misordered), but I think the basic approach is sound.

Thanks,
J

Jeremy Fitzhardinge (14):
x86/ticketlock: clean up types and accessors x86/ticketlock: convert spin loop to C
x86/ticketlock: Use C for __ticket_spin_unlock x86/ticketlock: make large and small ticket versions of spin_lock the
same
x86/ticketlock: make __ticket_spin_lock common x86/ticketlock: make __ticket_spin_trylock common x86/spinlocks: replace pv spinlocks with pv ticketlocks x86/ticketlock: collapse a layer of functions xen/pvticketlock: Xen implementation for PV ticket locks x86/pvticketlock: use callee-save for lock_spinning x86/ticketlock: don't inline _spin_unlock when using paravirt
spinlocks
x86/ticketlocks: when paravirtualizing ticket locks, increment by 2 x86/ticketlock: add slowpath logic
x86/ticketlocks: tidy up __ticket_unlock_kick()

 arch/x86/Kconfig                      |    3 +
 arch/x86/include/asm/paravirt.h       |   30 +---
 arch/x86/include/asm/paravirt_types.h |    8 +-
 arch/x86/include/asm/spinlock.h       |  236 +++++++++++++---------------
 arch/x86/include/asm/spinlock_types.h |   32 ++++-
 arch/x86/kernel/paravirt-spinlocks.c  |   52 +++++--
 arch/x86/xen/spinlock.c               |  281 +++++----------------------------
 kernel/Kconfig.locks                  |    2 +-
 8 files changed, 231 insertions(+), 413 deletions(-)
Signature · 1 line
1.7.2.3
#1 lore raw

PATCH 1/14 x86/ticketlock: clean up types and accessors

From: Jeremy Fitzhardinge <[email protected]>

A few cleanups to the way spinlocks are defined and accessed:
- define __ticket_t which is the size of a spinlock ticket (ie, enough bits to hold all the cpus)
- Define struct arch_spinlock as a union containing plain slock and the head and tail tickets
- Use head and tail to implement some of the spinlock predicates.
- Make all ticket variables unsigned.
- Use TICKET_SHIFT to form constants

Most of this will be used in later patches.

---
 arch/x86/include/asm/spinlock.h       |   24 ++++++++++--------------
 arch/x86/include/asm/spinlock_types.h |   20 ++++++++++++++++++--
 2 files changed, 28 insertions(+), 16 deletions(-)
arch/x86/include/asm/spinlock.h +10 -14
index 3089f70..d6d5784 100644
@@ -56,11 +56,9 @@
  * much between them in performance though, especially as locks are out of line.
  */
 #if (NR_CPUS < 256)
-#define TICKET_SHIFT 8
-
 static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 {
-	short inc = 0x0100;
+	unsigned short inc = 1 << TICKET_SHIFT;
 
 	asm volatile (
 		LOCK_PREFIX "xaddw %w0, %1\n"
@@ -79,7 +77,7 @@ static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 
 static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 {
-	int tmp, new;
+	unsigned int tmp, new;
 
 	asm volatile("movzwl %2, %0\n\t"
 		     "cmpb %h0,%b0\n\t"
@@ -104,12 +102,10 @@ static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
 		     : "memory", "cc");
 }
 #else
-#define TICKET_SHIFT 16
-
 static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 {
-	int inc = 0x00010000;
-	int tmp;
+	unsigned inc = 1 << TICKET_SHIFT;
+	unsigned tmp;
 
 	asm volatile(LOCK_PREFIX "xaddl %0, %1\n"
 		     "movzwl %w0, %2\n\t"
@@ -129,8 +125,8 @@ static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 
 static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 {
-	int tmp;
-	int new;
+	unsigned tmp;
+	unsigned new;
 
 	asm volatile("movl %2,%0\n\t"
 		     "movl %0,%1\n\t"
@@ -160,16 +156,16 @@ static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
 
 static inline int __ticket_spin_is_locked(arch_spinlock_t *lock)
 {
-	int tmp = ACCESS_ONCE(lock->slock);
+	struct __raw_tickets tmp = ACCESS_ONCE(lock->tickets);
 
-	return !!(((tmp >> TICKET_SHIFT) ^ tmp) & ((1 << TICKET_SHIFT) - 1));
+	return !!(tmp.tail ^ tmp.head);
 }
 
 static inline int __ticket_spin_is_contended(arch_spinlock_t *lock)
 {
-	int tmp = ACCESS_ONCE(lock->slock);
+	struct __raw_tickets tmp = ACCESS_ONCE(lock->tickets);
 
-	return (((tmp >> TICKET_SHIFT) - tmp) & ((1 << TICKET_SHIFT) - 1)) > 1;
+	return ((tmp.tail - tmp.head) & TICKET_MASK) > 1;
 }
 
 #ifndef CONFIG_PARAVIRT_SPINLOCKS
arch/x86/include/asm/spinlock_types.h +18 -2
index dcb48b2..e3ad1e3 100644
@@ -5,11 +5,27 @@
 # error "please don't include this file directly"
 #endif
 
+#include <linux/types.h>
+
+#if (CONFIG_NR_CPUS < 256)
+typedef u8  __ticket_t;
+#else
+typedef u16 __ticket_t;
+#endif
+
+#define TICKET_SHIFT	(sizeof(__ticket_t) * 8)
+#define TICKET_MASK	((__ticket_t)((1 << TICKET_SHIFT) - 1))
+
 typedef struct arch_spinlock {
-	unsigned int slock;
+	union {
+		unsigned int slock;
+		struct __raw_tickets {
+			__ticket_t head, tail;
+		} tickets;
+	};
 } arch_spinlock_t;
 
-#define __ARCH_SPIN_LOCK_UNLOCKED	{ 0 }
+#define __ARCH_SPIN_LOCK_UNLOCKED	{ { .slock = 0 } }
 
 typedef struct {
 	unsigned int lock;
Signature · 1 line
1.7.2.3
#4 lore raw

PATCH 1/14 x86/ticketlock: clean up types and accessors

In reply to Jeremy Fitzhardinge

From: Jeremy Fitzhardinge <[email protected]>

A few cleanups to the way spinlocks are defined and accessed:
- define __ticket_t which is the size of a spinlock ticket (ie, enough bits to hold all the cpus)
- Define struct arch_spinlock as a union containing plain slock and the head and tail tickets
- Use head and tail to implement some of the spinlock predicates.
- Make all ticket variables unsigned.
- Use TICKET_SHIFT to form constants

Most of this will be used in later patches.

---
 arch/x86/include/asm/spinlock.h       |   24 ++++++++++--------------
 arch/x86/include/asm/spinlock_types.h |   20 ++++++++++++++++++--
 2 files changed, 28 insertions(+), 16 deletions(-)
arch/x86/include/asm/spinlock.h +10 -14
index 3089f70..d6d5784 100644
@@ -56,11 +56,9 @@
  * much between them in performance though, especially as locks are out of line.
  */
 #if (NR_CPUS < 256)
-#define TICKET_SHIFT 8
-
 static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 {
-	short inc = 0x0100;
+	unsigned short inc = 1 << TICKET_SHIFT;
 
 	asm volatile (
 		LOCK_PREFIX "xaddw %w0, %1\n"
@@ -79,7 +77,7 @@ static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 
 static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 {
-	int tmp, new;
+	unsigned int tmp, new;
 
 	asm volatile("movzwl %2, %0\n\t"
 		     "cmpb %h0,%b0\n\t"
@@ -104,12 +102,10 @@ static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
 		     : "memory", "cc");
 }
 #else
-#define TICKET_SHIFT 16
-
 static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 {
-	int inc = 0x00010000;
-	int tmp;
+	unsigned inc = 1 << TICKET_SHIFT;
+	unsigned tmp;
 
 	asm volatile(LOCK_PREFIX "xaddl %0, %1\n"
 		     "movzwl %w0, %2\n\t"
@@ -129,8 +125,8 @@ static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 
 static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 {
-	int tmp;
-	int new;
+	unsigned tmp;
+	unsigned new;
 
 	asm volatile("movl %2,%0\n\t"
 		     "movl %0,%1\n\t"
@@ -160,16 +156,16 @@ static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
 
 static inline int __ticket_spin_is_locked(arch_spinlock_t *lock)
 {
-	int tmp = ACCESS_ONCE(lock->slock);
+	struct __raw_tickets tmp = ACCESS_ONCE(lock->tickets);
 
-	return !!(((tmp >> TICKET_SHIFT) ^ tmp) & ((1 << TICKET_SHIFT) - 1));
+	return !!(tmp.tail ^ tmp.head);
 }
 
 static inline int __ticket_spin_is_contended(arch_spinlock_t *lock)
 {
-	int tmp = ACCESS_ONCE(lock->slock);
+	struct __raw_tickets tmp = ACCESS_ONCE(lock->tickets);
 
-	return (((tmp >> TICKET_SHIFT) - tmp) & ((1 << TICKET_SHIFT) - 1)) > 1;
+	return ((tmp.tail - tmp.head) & TICKET_MASK) > 1;
 }
 
 #ifndef CONFIG_PARAVIRT_SPINLOCKS
arch/x86/include/asm/spinlock_types.h +18 -2
index dcb48b2..e3ad1e3 100644
@@ -5,11 +5,27 @@
 # error "please don't include this file directly"
 #endif
 
+#include <linux/types.h>
+
+#if (CONFIG_NR_CPUS < 256)
+typedef u8  __ticket_t;
+#else
+typedef u16 __ticket_t;
+#endif
+
+#define TICKET_SHIFT	(sizeof(__ticket_t) * 8)
+#define TICKET_MASK	((__ticket_t)((1 << TICKET_SHIFT) - 1))
+
 typedef struct arch_spinlock {
-	unsigned int slock;
+	union {
+		unsigned int slock;
+		struct __raw_tickets {
+			__ticket_t head, tail;
+		} tickets;
+	};
 } arch_spinlock_t;
 
-#define __ARCH_SPIN_LOCK_UNLOCKED	{ 0 }
+#define __ARCH_SPIN_LOCK_UNLOCKED	{ { .slock = 0 } }
 
 typedef struct {
 	unsigned int lock;
Signature · 1 line
1.7.2.3
#5 lore raw

PATCH 2/14 x86/ticketlock: convert spin loop to C

In reply to Jeremy Fitzhardinge

From: Jeremy Fitzhardinge <[email protected]>

The inner loop of __ticket_spin_lock isn't doing anything very special, so reimplement it in C.

For the 8 bit ticket lock variant, we use a register union to get direct access to the lower and upper bytes in the tickets, but unfortunately gcc won't generate a direct comparison between the two halves of the register, so the generated asm isn't quite as pretty as the hand-coded version. However benchmarking shows that this is actually a small improvement in runtime performance on some benchmarks, and never a slowdown.

We also need to make sure there's a barrier at the end of the lock loop to make sure that the compiler doesn't move any instructions from within the locked region into the region where we don't yet own the lock.

---
 arch/x86/include/asm/spinlock.h |   58 +++++++++++++++++++-------------------
 1 files changed, 29 insertions(+), 29 deletions(-)
arch/x86/include/asm/spinlock.h +30 -30
index d6d5784..f48a6e3 100644
@@ -58,21 +58,21 @@
 #if (NR_CPUS < 256)
 static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 {
-	unsigned short inc = 1 << TICKET_SHIFT;
-
-	asm volatile (
-		LOCK_PREFIX "xaddw %w0, %1\n"
-		"1:\t"
-		"cmpb %h0, %b0\n\t"
-		"je 2f\n\t"
-		"rep ; nop\n\t"
-		"movb %1, %b0\n\t"
-		/* don't need lfence here, because loads are in-order */
-		"jmp 1b\n"
-		"2:"
-		: "+Q" (inc), "+m" (lock->slock)
-		:
-		: "memory", "cc");
+	register union {
+		struct __raw_tickets tickets;
+		unsigned short slock;
+	} inc = { .slock = 1 << TICKET_SHIFT };
+
+	asm volatile (LOCK_PREFIX "xaddw %w0, %1\n"
+		      : "+Q" (inc), "+m" (lock->slock) : : "memory", "cc");
+
+	for (;;) {
+		if (inc.tickets.head == inc.tickets.tail)
+			goto out;
+		cpu_relax();
+		inc.tickets.head = ACCESS_ONCE(lock->tickets.head);
+	}
+out:	barrier();		/* make sure nothing creeps before the lock is taken */
 }
 
 static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
@@ -105,22 +105,22 @@ static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
 static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 {
 	unsigned inc = 1 << TICKET_SHIFT;
-	unsigned tmp;
+	__ticket_t tmp;
 
-	asm volatile(LOCK_PREFIX "xaddl %0, %1\n"
-		     "movzwl %w0, %2\n\t"
-		     "shrl $16, %0\n\t"
-		     "1:\t"
-		     "cmpl %0, %2\n\t"
-		     "je 2f\n\t"
-		     "rep ; nop\n\t"
-		     "movzwl %1, %2\n\t"
-		     /* don't need lfence here, because loads are in-order */
-		     "jmp 1b\n"
-		     "2:"
-		     : "+r" (inc), "+m" (lock->slock), "=&r" (tmp)
-		     :
-		     : "memory", "cc");
+	asm volatile(LOCK_PREFIX "xaddl %0, %1\n\t"
+		     : "+r" (inc), "+m" (lock->slock)
+		     : : "memory", "cc");
+
+	tmp = inc;
+	inc >>= TICKET_SHIFT;
+
+	for (;;) {
+		if ((__ticket_t)inc == tmp)
+			goto out;
+		cpu_relax();
+		tmp = ACCESS_ONCE(lock->tickets.head);
+	}
+out:	barrier();		/* make sure nothing creeps before the lock is taken */
 }
 
 static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
Signature · 1 line
1.7.2.3
#6 lore raw

PATCH 2/14 x86/ticketlock: convert spin loop to C

In reply to Jeremy Fitzhardinge

From: Jeremy Fitzhardinge <[email protected]>

The inner loop of __ticket_spin_lock isn't doing anything very special, so reimplement it in C.

For the 8 bit ticket lock variant, we use a register union to get direct access to the lower and upper bytes in the tickets, but unfortunately gcc won't generate a direct comparison between the two halves of the register, so the generated asm isn't quite as pretty as the hand-coded version. However benchmarking shows that this is actually a small improvement in runtime performance on some benchmarks, and never a slowdown.

We also need to make sure there's a barrier at the end of the lock loop to make sure that the compiler doesn't move any instructions from within the locked region into the region where we don't yet own the lock.

---
 arch/x86/include/asm/spinlock.h |   58 +++++++++++++++++++-------------------
 1 files changed, 29 insertions(+), 29 deletions(-)
arch/x86/include/asm/spinlock.h +30 -30
index d6d5784..f48a6e3 100644
@@ -58,21 +58,21 @@
 #if (NR_CPUS < 256)
 static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 {
-	unsigned short inc = 1 << TICKET_SHIFT;
-
-	asm volatile (
-		LOCK_PREFIX "xaddw %w0, %1\n"
-		"1:\t"
-		"cmpb %h0, %b0\n\t"
-		"je 2f\n\t"
-		"rep ; nop\n\t"
-		"movb %1, %b0\n\t"
-		/* don't need lfence here, because loads are in-order */
-		"jmp 1b\n"
-		"2:"
-		: "+Q" (inc), "+m" (lock->slock)
-		:
-		: "memory", "cc");
+	register union {
+		struct __raw_tickets tickets;
+		unsigned short slock;
+	} inc = { .slock = 1 << TICKET_SHIFT };
+
+	asm volatile (LOCK_PREFIX "xaddw %w0, %1\n"
+		      : "+Q" (inc), "+m" (lock->slock) : : "memory", "cc");
+
+	for (;;) {
+		if (inc.tickets.head == inc.tickets.tail)
+			goto out;
+		cpu_relax();
+		inc.tickets.head = ACCESS_ONCE(lock->tickets.head);
+	}
+out:	barrier();		/* make sure nothing creeps before the lock is taken */
 }
 
 static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
@@ -105,22 +105,22 @@ static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
 static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 {
 	unsigned inc = 1 << TICKET_SHIFT;
-	unsigned tmp;
+	__ticket_t tmp;
 
-	asm volatile(LOCK_PREFIX "xaddl %0, %1\n"
-		     "movzwl %w0, %2\n\t"
-		     "shrl $16, %0\n\t"
-		     "1:\t"
-		     "cmpl %0, %2\n\t"
-		     "je 2f\n\t"
-		     "rep ; nop\n\t"
-		     "movzwl %1, %2\n\t"
-		     /* don't need lfence here, because loads are in-order */
-		     "jmp 1b\n"
-		     "2:"
-		     : "+r" (inc), "+m" (lock->slock), "=&r" (tmp)
-		     :
-		     : "memory", "cc");
+	asm volatile(LOCK_PREFIX "xaddl %0, %1\n\t"
+		     : "+r" (inc), "+m" (lock->slock)
+		     : : "memory", "cc");
+
+	tmp = inc;
+	inc >>= TICKET_SHIFT;
+
+	for (;;) {
+		if ((__ticket_t)inc == tmp)
+			goto out;
+		cpu_relax();
+		tmp = ACCESS_ONCE(lock->tickets.head);
+	}
+out:	barrier();		/* make sure nothing creeps before the lock is taken */
 }
 
 static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
Signature · 1 line
1.7.2.3
#7 lore raw

PATCH 3/14 x86/ticketlock: Use C for __ticket_spin_unlock

In reply to Jeremy Fitzhardinge

From: Jeremy Fitzhardinge <[email protected]>

If we don't need to use a locked inc for unlock, then implement it in C.

---
 arch/x86/include/asm/spinlock.h |   32 +++++++++++++++++---------------
 1 files changed, 17 insertions(+), 15 deletions(-)
arch/x86/include/asm/spinlock.h +17 -15
index f48a6e3..0170ba9 100644
@@ -33,9 +33,21 @@
  * On PPro SMP or if we are using OOSTORE, we use a locked operation to unlock
  * (PPro errata 66, 92)
  */
-# define UNLOCK_LOCK_PREFIX LOCK_PREFIX
+static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)
+{
+	if (sizeof(lock->tickets.head) == sizeof(u8))
+		asm (LOCK_PREFIX "incb %0"
+		     : "+m" (lock->tickets.head) : : "memory");
+	else
+		asm (LOCK_PREFIX "incw %0"
+		     : "+m" (lock->tickets.head) : : "memory");
+
+}
 #else
-# define UNLOCK_LOCK_PREFIX
+static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)
+{
+	lock->tickets.head++;
+}
 #endif
 
 /*
@@ -93,14 +105,6 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 
 	return tmp;
 }
-
-static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
-{
-	asm volatile(UNLOCK_LOCK_PREFIX "incb %0"
-		     : "+m" (lock->slock)
-		     :
-		     : "memory", "cc");
-}
 #else
 static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 {
@@ -144,15 +148,13 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 
 	return tmp;
 }
+#endif
 
 static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
 {
-	asm volatile(UNLOCK_LOCK_PREFIX "incw %0"
-		     : "+m" (lock->slock)
-		     :
-		     : "memory", "cc");
+	__ticket_unlock_release(lock);
+	barrier();		/* prevent reordering into locked region */
 }
-#endif
 
 static inline int __ticket_spin_is_locked(arch_spinlock_t *lock)
 {
Signature · 1 line
1.7.2.3
#8 lore raw

PATCH 3/14 x86/ticketlock: Use C for __ticket_spin_unlock

In reply to Jeremy Fitzhardinge

From: Jeremy Fitzhardinge <[email protected]>

If we don't need to use a locked inc for unlock, then implement it in C.

---
 arch/x86/include/asm/spinlock.h |   32 +++++++++++++++++---------------
 1 files changed, 17 insertions(+), 15 deletions(-)
arch/x86/include/asm/spinlock.h +17 -15
index f48a6e3..0170ba9 100644
@@ -33,9 +33,21 @@
  * On PPro SMP or if we are using OOSTORE, we use a locked operation to unlock
  * (PPro errata 66, 92)
  */
-# define UNLOCK_LOCK_PREFIX LOCK_PREFIX
+static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)
+{
+	if (sizeof(lock->tickets.head) == sizeof(u8))
+		asm (LOCK_PREFIX "incb %0"
+		     : "+m" (lock->tickets.head) : : "memory");
+	else
+		asm (LOCK_PREFIX "incw %0"
+		     : "+m" (lock->tickets.head) : : "memory");
+
+}
 #else
-# define UNLOCK_LOCK_PREFIX
+static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)
+{
+	lock->tickets.head++;
+}
 #endif
 
 /*
@@ -93,14 +105,6 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 
 	return tmp;
 }
-
-static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
-{
-	asm volatile(UNLOCK_LOCK_PREFIX "incb %0"
-		     : "+m" (lock->slock)
-		     :
-		     : "memory", "cc");
-}
 #else
 static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 {
@@ -144,15 +148,13 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 
 	return tmp;
 }
+#endif
 
 static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
 {
-	asm volatile(UNLOCK_LOCK_PREFIX "incw %0"
-		     : "+m" (lock->slock)
-		     :
-		     : "memory", "cc");
+	__ticket_unlock_release(lock);
+	barrier();		/* prevent reordering into locked region */
 }
-#endif
 
 static inline int __ticket_spin_is_locked(arch_spinlock_t *lock)
 {
Signature · 1 line
1.7.2.3
#9 lore raw

PATCH 4/14 x86/ticketlock: make large and small ticket versions of spin_lock the same

In reply to Jeremy Fitzhardinge

From: Jeremy Fitzhardinge <[email protected]>

Make the bulk of __ticket_spin_lock look identical for large and small number of cpus.

---
 arch/x86/include/asm/spinlock.h |   23 ++++++++---------------
 1 files changed, 8 insertions(+), 15 deletions(-)
arch/x86/include/asm/spinlock.h +8 -15
index 0170ba9..1b81809 100644
@@ -70,19 +70,16 @@ static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)
 #if (NR_CPUS < 256)
 static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 {
-	register union {
-		struct __raw_tickets tickets;
-		unsigned short slock;
-	} inc = { .slock = 1 << TICKET_SHIFT };
+	register struct __raw_tickets inc = { .tail = 1 };
 
 	asm volatile (LOCK_PREFIX "xaddw %w0, %1\n"
-		      : "+Q" (inc), "+m" (lock->slock) : : "memory", "cc");
+		      : "+r" (inc), "+m" (lock->tickets) : : "memory", "cc");
 
 	for (;;) {
-		if (inc.tickets.head == inc.tickets.tail)
+		if (inc.head == inc.tail)
 			goto out;
 		cpu_relax();
-		inc.tickets.head = ACCESS_ONCE(lock->tickets.head);
+		inc.head = ACCESS_ONCE(lock->tickets.head);
 	}
 out:	barrier();		/* make sure nothing creeps before the lock is taken */
 }
@@ -108,21 +105,17 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 #else
 static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 {
-	unsigned inc = 1 << TICKET_SHIFT;
-	__ticket_t tmp;
+	register struct __raw_tickets inc = { .tail = 1 };
 
 	asm volatile(LOCK_PREFIX "xaddl %0, %1\n\t"
-		     : "+r" (inc), "+m" (lock->slock)
+		     : "+r" (inc), "+m" (lock->tickets)
 		     : : "memory", "cc");
 
-	tmp = inc;
-	inc >>= TICKET_SHIFT;
-
 	for (;;) {
-		if ((__ticket_t)inc == tmp)
+		if (inc.head == inc.tail)
 			goto out;
 		cpu_relax();
-		tmp = ACCESS_ONCE(lock->tickets.head);
+		inc.head = ACCESS_ONCE(lock->tickets.head);
 	}
 out:	barrier();		/* make sure nothing creeps before the lock is taken */
 }
Signature · 1 line
1.7.2.3
#10 lore raw

PATCH 4/14 x86/ticketlock: make large and small ticket versions of spin_lock the same

In reply to Jeremy Fitzhardinge

From: Jeremy Fitzhardinge <[email protected]>

Make the bulk of __ticket_spin_lock look identical for large and small number of cpus.

---
 arch/x86/include/asm/spinlock.h |   23 ++++++++---------------
 1 files changed, 8 insertions(+), 15 deletions(-)
arch/x86/include/asm/spinlock.h +8 -15
index 0170ba9..1b81809 100644
@@ -70,19 +70,16 @@ static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)
 #if (NR_CPUS < 256)
 static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 {
-	register union {
-		struct __raw_tickets tickets;
-		unsigned short slock;
-	} inc = { .slock = 1 << TICKET_SHIFT };
+	register struct __raw_tickets inc = { .tail = 1 };
 
 	asm volatile (LOCK_PREFIX "xaddw %w0, %1\n"
-		      : "+Q" (inc), "+m" (lock->slock) : : "memory", "cc");
+		      : "+r" (inc), "+m" (lock->tickets) : : "memory", "cc");
 
 	for (;;) {
-		if (inc.tickets.head == inc.tickets.tail)
+		if (inc.head == inc.tail)
 			goto out;
 		cpu_relax();
-		inc.tickets.head = ACCESS_ONCE(lock->tickets.head);
+		inc.head = ACCESS_ONCE(lock->tickets.head);
 	}
 out:	barrier();		/* make sure nothing creeps before the lock is taken */
 }
@@ -108,21 +105,17 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 #else
 static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 {
-	unsigned inc = 1 << TICKET_SHIFT;
-	__ticket_t tmp;
+	register struct __raw_tickets inc = { .tail = 1 };
 
 	asm volatile(LOCK_PREFIX "xaddl %0, %1\n\t"
-		     : "+r" (inc), "+m" (lock->slock)
+		     : "+r" (inc), "+m" (lock->tickets)
 		     : : "memory", "cc");
 
-	tmp = inc;
-	inc >>= TICKET_SHIFT;
-
 	for (;;) {
-		if ((__ticket_t)inc == tmp)
+		if (inc.head == inc.tail)
 			goto out;
 		cpu_relax();
-		tmp = ACCESS_ONCE(lock->tickets.head);
+		inc.head = ACCESS_ONCE(lock->tickets.head);
 	}
 out:	barrier();		/* make sure nothing creeps before the lock is taken */
 }
Signature · 1 line
1.7.2.3
#11 lore raw

PATCH 5/14 x86/ticketlock: make __ticket_spin_lock common

In reply to Jeremy Fitzhardinge

From: Jeremy Fitzhardinge <[email protected]>

Aside from the particular form of the xadd instruction, they're identical. So factor out the xadd and use common code for the rest.

---
 arch/x86/include/asm/spinlock.h |   42 ++++++++++++++++++--------------------
 1 files changed, 20 insertions(+), 22 deletions(-)
arch/x86/include/asm/spinlock.h +20 -22
index 1b81809..f722f96 100644
@@ -67,13 +67,27 @@ static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)
  * save some instructions and make the code more elegant. There really isn't
  * much between them in performance though, especially as locks are out of line.
  */
-#if (NR_CPUS < 256)
-static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
+static __always_inline struct __raw_tickets __ticket_spin_claim(struct arch_spinlock *lock)
 {
-	register struct __raw_tickets inc = { .tail = 1 };
+	register struct __raw_tickets tickets = { .tail = 1 };
+
+	if (sizeof(lock->tickets.head) == sizeof(u8))
+		asm volatile (LOCK_PREFIX "xaddw %w0, %1\n"
+			      : "+r" (tickets), "+m" (lock->tickets)
+			      : : "memory", "cc");
+	else
+		asm volatile (LOCK_PREFIX "xaddl %0, %1\n"
+			     : "+r" (tickets), "+m" (lock->tickets)
+			     : : "memory", "cc");
 
-	asm volatile (LOCK_PREFIX "xaddw %w0, %1\n"
-		      : "+r" (inc), "+m" (lock->tickets) : : "memory", "cc");
+	return tickets;
+}
+
+static __always_inline void __ticket_spin_lock(struct arch_spinlock *lock)
+{
+	register struct __raw_tickets inc;
+
+	inc = __ticket_spin_claim(lock);
 
 	for (;;) {
 		if (inc.head == inc.tail)
@@ -84,6 +98,7 @@ static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 out:	barrier();		/* make sure nothing creeps before the lock is taken */
 }
 
+#if (NR_CPUS < 256)
 static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 {
 	unsigned int tmp, new;
@@ -103,23 +118,6 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 	return tmp;
 }
 #else
-static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
-{
-	register struct __raw_tickets inc = { .tail = 1 };
-
-	asm volatile(LOCK_PREFIX "xaddl %0, %1\n\t"
-		     : "+r" (inc), "+m" (lock->tickets)
-		     : : "memory", "cc");
-
-	for (;;) {
-		if (inc.head == inc.tail)
-			goto out;
-		cpu_relax();
-		inc.head = ACCESS_ONCE(lock->tickets.head);
-	}
-out:	barrier();		/* make sure nothing creeps before the lock is taken */
-}
-
 static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 {
 	unsigned tmp;
Signature · 1 line
1.7.2.3
#12 lore raw

PATCH 5/14 x86/ticketlock: make __ticket_spin_lock common

In reply to Jeremy Fitzhardinge

From: Jeremy Fitzhardinge <[email protected]>

Aside from the particular form of the xadd instruction, they're identical. So factor out the xadd and use common code for the rest.

---
 arch/x86/include/asm/spinlock.h |   42 ++++++++++++++++++--------------------
 1 files changed, 20 insertions(+), 22 deletions(-)
arch/x86/include/asm/spinlock.h +20 -22
index 1b81809..f722f96 100644
@@ -67,13 +67,27 @@ static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)
  * save some instructions and make the code more elegant. There really isn't
  * much between them in performance though, especially as locks are out of line.
  */
-#if (NR_CPUS < 256)
-static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
+static __always_inline struct __raw_tickets __ticket_spin_claim(struct arch_spinlock *lock)
 {
-	register struct __raw_tickets inc = { .tail = 1 };
+	register struct __raw_tickets tickets = { .tail = 1 };
+
+	if (sizeof(lock->tickets.head) == sizeof(u8))
+		asm volatile (LOCK_PREFIX "xaddw %w0, %1\n"
+			      : "+r" (tickets), "+m" (lock->tickets)
+			      : : "memory", "cc");
+	else
+		asm volatile (LOCK_PREFIX "xaddl %0, %1\n"
+			     : "+r" (tickets), "+m" (lock->tickets)
+			     : : "memory", "cc");
 
-	asm volatile (LOCK_PREFIX "xaddw %w0, %1\n"
-		      : "+r" (inc), "+m" (lock->tickets) : : "memory", "cc");
+	return tickets;
+}
+
+static __always_inline void __ticket_spin_lock(struct arch_spinlock *lock)
+{
+	register struct __raw_tickets inc;
+
+	inc = __ticket_spin_claim(lock);
 
 	for (;;) {
 		if (inc.head == inc.tail)
@@ -84,6 +98,7 @@ static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 out:	barrier();		/* make sure nothing creeps before the lock is taken */
 }
 
+#if (NR_CPUS < 256)
 static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 {
 	unsigned int tmp, new;
@@ -103,23 +118,6 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 	return tmp;
 }
 #else
-static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
-{
-	register struct __raw_tickets inc = { .tail = 1 };
-
-	asm volatile(LOCK_PREFIX "xaddl %0, %1\n\t"
-		     : "+r" (inc), "+m" (lock->tickets)
-		     : : "memory", "cc");
-
-	for (;;) {
-		if (inc.head == inc.tail)
-			goto out;
-		cpu_relax();
-		inc.head = ACCESS_ONCE(lock->tickets.head);
-	}
-out:	barrier();		/* make sure nothing creeps before the lock is taken */
-}
-
 static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 {
 	unsigned tmp;
Signature · 1 line
1.7.2.3
#13 lore raw

PATCH 6/14 x86/ticketlock: make __ticket_spin_trylock common

In reply to Jeremy Fitzhardinge

From: Jeremy Fitzhardinge <[email protected]>

Make trylock code common regardless of ticket size.

---
 arch/x86/include/asm/spinlock.h       |   49 +++++++--------------------------
 arch/x86/include/asm/spinlock_types.h |    6 +++-
 2 files changed, 14 insertions(+), 41 deletions(-)
arch/x86/include/asm/spinlock.h +10 -39
index f722f96..3afb1a7 100644
@@ -98,48 +98,19 @@ static __always_inline void __ticket_spin_lock(struct arch_spinlock *lock)
 out:	barrier();		/* make sure nothing creeps before the lock is taken */
 }
 
-#if (NR_CPUS < 256)
 static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 {
-	unsigned int tmp, new;
-
-	asm volatile("movzwl %2, %0\n\t"
-		     "cmpb %h0,%b0\n\t"
-		     "leal 0x100(%" REG_PTR_MODE "0), %1\n\t"
-		     "jne 1f\n\t"
-		     LOCK_PREFIX "cmpxchgw %w1,%2\n\t"
-		     "1:"
-		     "sete %b1\n\t"
-		     "movzbl %b1,%0\n\t"
-		     : "=&a" (tmp), "=&q" (new), "+m" (lock->slock)
-		     :
-		     : "memory", "cc");
-
-	return tmp;
-}
-#else
-static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
-{
-	unsigned tmp;
-	unsigned new;
-
-	asm volatile("movl %2,%0\n\t"
-		     "movl %0,%1\n\t"
-		     "roll $16, %0\n\t"
-		     "cmpl %0,%1\n\t"
-		     "leal 0x00010000(%" REG_PTR_MODE "0), %1\n\t"
-		     "jne 1f\n\t"
-		     LOCK_PREFIX "cmpxchgl %1,%2\n\t"
-		     "1:"
-		     "sete %b1\n\t"
-		     "movzbl %b1,%0\n\t"
-		     : "=&a" (tmp), "=&q" (new), "+m" (lock->slock)
-		     :
-		     : "memory", "cc");
-
-	return tmp;
+	arch_spinlock_t old, new;
+
+	old.tickets = ACCESS_ONCE(lock->tickets);
+	if (old.tickets.head != old.tickets.tail)
+		return 0;
+
+	new.head_tail = old.head_tail + (1 << TICKET_SHIFT);
+
+	/* cmpxchg is a full barrier, so nothing can move before it */
+	return cmpxchg(&lock->head_tail, old.head_tail, new.head_tail) == old.head_tail;
 }
-#endif
 
 static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
 {
arch/x86/include/asm/spinlock_types.h +4 -2
index e3ad1e3..72e154e 100644
@@ -9,8 +9,10 @@
 
 #if (CONFIG_NR_CPUS < 256)
 typedef u8  __ticket_t;
+typedef u16 __ticketpair_t;
 #else
 typedef u16 __ticket_t;
+typedef u32 __ticketpair_t;
 #endif
 
 #define TICKET_SHIFT	(sizeof(__ticket_t) * 8)
@@ -18,14 +20,14 @@ typedef u16 __ticket_t;
 
 typedef struct arch_spinlock {
 	union {
-		unsigned int slock;
+		__ticketpair_t head_tail;
 		struct __raw_tickets {
 			__ticket_t head, tail;
 		} tickets;
 	};
 } arch_spinlock_t;
 
-#define __ARCH_SPIN_LOCK_UNLOCKED	{ { .slock = 0 } }
+#define __ARCH_SPIN_LOCK_UNLOCKED	{ { 0 } }
 
 typedef struct {
 	unsigned int lock;
Signature · 1 line
1.7.2.3
#14 lore raw

PATCH 6/14 x86/ticketlock: make __ticket_spin_trylock common

In reply to Jeremy Fitzhardinge

From: Jeremy Fitzhardinge <[email protected]>

Make trylock code common regardless of ticket size.

---
 arch/x86/include/asm/spinlock.h       |   49 +++++++--------------------------
 arch/x86/include/asm/spinlock_types.h |    6 +++-
 2 files changed, 14 insertions(+), 41 deletions(-)
arch/x86/include/asm/spinlock.h +10 -39
index f722f96..3afb1a7 100644
@@ -98,48 +98,19 @@ static __always_inline void __ticket_spin_lock(struct arch_spinlock *lock)
 out:	barrier();		/* make sure nothing creeps before the lock is taken */
 }
 
-#if (NR_CPUS < 256)
 static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 {
-	unsigned int tmp, new;
-
-	asm volatile("movzwl %2, %0\n\t"
-		     "cmpb %h0,%b0\n\t"
-		     "leal 0x100(%" REG_PTR_MODE "0), %1\n\t"
-		     "jne 1f\n\t"
-		     LOCK_PREFIX "cmpxchgw %w1,%2\n\t"
-		     "1:"
-		     "sete %b1\n\t"
-		     "movzbl %b1,%0\n\t"
-		     : "=&a" (tmp), "=&q" (new), "+m" (lock->slock)
-		     :
-		     : "memory", "cc");
-
-	return tmp;
-}
-#else
-static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
-{
-	unsigned tmp;
-	unsigned new;
-
-	asm volatile("movl %2,%0\n\t"
-		     "movl %0,%1\n\t"
-		     "roll $16, %0\n\t"
-		     "cmpl %0,%1\n\t"
-		     "leal 0x00010000(%" REG_PTR_MODE "0), %1\n\t"
-		     "jne 1f\n\t"
-		     LOCK_PREFIX "cmpxchgl %1,%2\n\t"
-		     "1:"
-		     "sete %b1\n\t"
-		     "movzbl %b1,%0\n\t"
-		     : "=&a" (tmp), "=&q" (new), "+m" (lock->slock)
-		     :
-		     : "memory", "cc");
-
-	return tmp;
+	arch_spinlock_t old, new;
+
+	old.tickets = ACCESS_ONCE(lock->tickets);
+	if (old.tickets.head != old.tickets.tail)
+		return 0;
+
+	new.head_tail = old.head_tail + (1 << TICKET_SHIFT);
+
+	/* cmpxchg is a full barrier, so nothing can move before it */
+	return cmpxchg(&lock->head_tail, old.head_tail, new.head_tail) == old.head_tail;
 }
-#endif
 
 static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
 {
arch/x86/include/asm/spinlock_types.h +4 -2
index e3ad1e3..72e154e 100644
@@ -9,8 +9,10 @@
 
 #if (CONFIG_NR_CPUS < 256)
 typedef u8  __ticket_t;
+typedef u16 __ticketpair_t;
 #else
 typedef u16 __ticket_t;
+typedef u32 __ticketpair_t;
 #endif
 
 #define TICKET_SHIFT	(sizeof(__ticket_t) * 8)
@@ -18,14 +20,14 @@ typedef u16 __ticket_t;
 
 typedef struct arch_spinlock {
 	union {
-		unsigned int slock;
+		__ticketpair_t head_tail;
 		struct __raw_tickets {
 			__ticket_t head, tail;
 		} tickets;
 	};
 } arch_spinlock_t;
 
-#define __ARCH_SPIN_LOCK_UNLOCKED	{ { .slock = 0 } }
+#define __ARCH_SPIN_LOCK_UNLOCKED	{ { 0 } }
 
 typedef struct {
 	unsigned int lock;
Signature · 1 line
1.7.2.3
#15 lore raw

PATCH 7/14 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 |    8 +----
 arch/x86/include/asm/spinlock.h       |   44 +++++++++++++++++++++++++++------
 arch/x86/kernel/paravirt-spinlocks.c  |   15 +---------
 arch/x86/xen/spinlock.c               |    7 ++++-
 5 files changed, 50 insertions(+), 54 deletions(-)
arch/x86/include/asm/paravirt.h +4 -26
index 18e3b8a..c864775 100644
@@ -717,36 +717,14 @@ static inline void __set_fixmap(unsigned /* enum fixed_addresses */ idx,
 
 #if defined(CONFIG_SMP) && defined(CONFIG_PARAVIRT_SPINLOCKS)
 
-static inline int arch_spin_is_locked(struct arch_spinlock *lock)
+static inline void __ticket_lock_spinning(struct arch_spinlock *lock, unsigned ticket)
 {
-	return PVOP_CALL1(int, pv_lock_ops.spin_is_locked, lock);
+	PVOP_VCALL2(pv_lock_ops.lock_spinning, lock, ticket);
 }
 
-static inline int arch_spin_is_contended(struct arch_spinlock *lock)
+static inline void ____ticket_unlock_kick(struct arch_spinlock *lock, unsigned ticket)
 {
-	return PVOP_CALL1(int, pv_lock_ops.spin_is_contended, lock);
-}
-#define arch_spin_is_contended	arch_spin_is_contended
-
-static __always_inline void arch_spin_lock(struct arch_spinlock *lock)
-{
-	PVOP_VCALL1(pv_lock_ops.spin_lock, lock);
-}
-
-static __always_inline void arch_spin_lock_flags(struct arch_spinlock *lock,
-						  unsigned long flags)
-{
-	PVOP_VCALL2(pv_lock_ops.spin_lock_flags, lock, flags);
-}
-
-static __always_inline int arch_spin_trylock(struct arch_spinlock *lock)
-{
-	return PVOP_CALL1(int, pv_lock_ops.spin_trylock, lock);
-}
-
-static __always_inline void arch_spin_unlock(struct arch_spinlock *lock)
-{
-	PVOP_VCALL1(pv_lock_ops.spin_unlock, lock);
+	PVOP_VCALL2(pv_lock_ops.unlock_kick, lock, ticket);
 }
 
 #endif
arch/x86/include/asm/paravirt_types.h +2 -6
index b82bac9..1078474 100644
@@ -315,12 +315,8 @@ struct pv_mmu_ops {
 
 struct arch_spinlock;
 struct pv_lock_ops {
-	int (*spin_is_locked)(struct arch_spinlock *lock);
-	int (*spin_is_contended)(struct arch_spinlock *lock);
-	void (*spin_lock)(struct arch_spinlock *lock);
-	void (*spin_lock_flags)(struct arch_spinlock *lock, unsigned long flags);
-	int (*spin_trylock)(struct arch_spinlock *lock);
-	void (*spin_unlock)(struct arch_spinlock *lock);
+	void (*lock_spinning)(struct arch_spinlock *lock, unsigned ticket);
+	void (*unlock_kick)(struct arch_spinlock *lock, unsigned ticket);
 };
 
 /* This contains all the paravirt structures: we get a convenient
arch/x86/include/asm/spinlock.h +36 -8

81 lines not on this page · raw message

arch/x86/kernel/paravirt-spinlocks.c +2 -13
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 23e061b..3d9da72 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.2.3
#16 lore raw

PATCH 7/14 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 |    8 +----
 arch/x86/include/asm/spinlock.h       |   44 +++++++++++++++++++++++++++------
 arch/x86/kernel/paravirt-spinlocks.c  |   15 +---------
 arch/x86/xen/spinlock.c               |    7 ++++-
 5 files changed, 50 insertions(+), 54 deletions(-)
arch/x86/include/asm/paravirt.h +4 -26
index 18e3b8a..c864775 100644
@@ -717,36 +717,14 @@ static inline void __set_fixmap(unsigned /* enum fixed_addresses */ idx,
 
 #if defined(CONFIG_SMP) && defined(CONFIG_PARAVIRT_SPINLOCKS)
 
-static inline int arch_spin_is_locked(struct arch_spinlock *lock)
+static inline void __ticket_lock_spinning(struct arch_spinlock *lock, unsigned ticket)
 {
-	return PVOP_CALL1(int, pv_lock_ops.spin_is_locked, lock);
+	PVOP_VCALL2(pv_lock_ops.lock_spinning, lock, ticket);
 }
 
-static inline int arch_spin_is_contended(struct arch_spinlock *lock)
+static inline void ____ticket_unlock_kick(struct arch_spinlock *lock, unsigned ticket)
 {
-	return PVOP_CALL1(int, pv_lock_ops.spin_is_contended, lock);
-}
-#define arch_spin_is_contended	arch_spin_is_contended
-
-static __always_inline void arch_spin_lock(struct arch_spinlock *lock)
-{
-	PVOP_VCALL1(pv_lock_ops.spin_lock, lock);
-}
-
-static __always_inline void arch_spin_lock_flags(struct arch_spinlock *lock,
-						  unsigned long flags)
-{
-	PVOP_VCALL2(pv_lock_ops.spin_lock_flags, lock, flags);
-}
-
-static __always_inline int arch_spin_trylock(struct arch_spinlock *lock)
-{
-	return PVOP_CALL1(int, pv_lock_ops.spin_trylock, lock);
-}
-
-static __always_inline void arch_spin_unlock(struct arch_spinlock *lock)
-{
-	PVOP_VCALL1(pv_lock_ops.spin_unlock, lock);
+	PVOP_VCALL2(pv_lock_ops.unlock_kick, lock, ticket);
 }
 
 #endif
arch/x86/include/asm/paravirt_types.h +2 -6
index b82bac9..1078474 100644
@@ -315,12 +315,8 @@ struct pv_mmu_ops {
 
 struct arch_spinlock;
 struct pv_lock_ops {
-	int (*spin_is_locked)(struct arch_spinlock *lock);
-	int (*spin_is_contended)(struct arch_spinlock *lock);
-	void (*spin_lock)(struct arch_spinlock *lock);
-	void (*spin_lock_flags)(struct arch_spinlock *lock, unsigned long flags);
-	int (*spin_trylock)(struct arch_spinlock *lock);
-	void (*spin_unlock)(struct arch_spinlock *lock);
+	void (*lock_spinning)(struct arch_spinlock *lock, unsigned ticket);
+	void (*unlock_kick)(struct arch_spinlock *lock, unsigned ticket);
 };
 
 /* This contains all the paravirt structures: we get a convenient
arch/x86/include/asm/spinlock.h +36 -8

81 lines not on this page · raw message

arch/x86/kernel/paravirt-spinlocks.c +2 -13
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 23e061b..3d9da72 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.2.3
#17 lore raw

PATCH 8/14 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 8e379d3..cfa80b5 100644
@@ -108,7 +108,7 @@ static __always_inline void __ticket_unlock_kick(struct arch_spinlock *lock, __t
 		____ticket_unlock_kick(lock, next);
 }
 
-static __always_inline void __ticket_spin_lock(struct arch_spinlock *lock)
+static __always_inline void arch_spin_lock(struct arch_spinlock *lock)
 {
 	register struct __raw_tickets inc;
 
@@ -128,7 +128,7 @@ static __always_inline void __ticket_spin_lock(struct arch_spinlock *lock)
 out:	barrier();		/* make sure nothing creeps before the lock is taken */
 }
 
-static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
+static __always_inline int arch_spin_trylock(arch_spinlock_t *lock)
 {
 	arch_spinlock_t old, new;
 
@@ -142,7 +142,7 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 	return cmpxchg(&lock->head_tail, old.head_tail, new.head_tail) == old.head_tail;
 }
 
-static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
+static __always_inline void arch_spin_unlock(arch_spinlock_t *lock)
 {
 	__ticket_t next = lock->tickets.head + 1;
 	__ticket_unlock_release(lock);
@@ -150,46 +150,21 @@ static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
 	barrier();		/* prevent reordering into locked region */
 }
 
-static inline int __ticket_spin_is_locked(arch_spinlock_t *lock)
+static inline int arch_spin_is_locked(arch_spinlock_t *lock)
 {
 	struct __raw_tickets tmp = ACCESS_ONCE(lock->tickets);
 
 	return !!(tmp.tail ^ tmp.head);
 }
 
-static inline int __ticket_spin_is_contended(arch_spinlock_t *lock)
+static inline int arch_spin_is_contended(arch_spinlock_t *lock)
 {
 	struct __raw_tickets tmp = ACCESS_ONCE(lock->tickets);
 
 	return ((tmp.tail - tmp.head) & TICKET_MASK) > 1;
 }
-
-static inline int arch_spin_is_locked(arch_spinlock_t *lock)
-{
-	return __ticket_spin_is_locked(lock);
-}
-
-static inline int arch_spin_is_contended(arch_spinlock_t *lock)
-{
-	return __ticket_spin_is_contended(lock);
-}
 #define arch_spin_is_contended	arch_spin_is_contended
 
-static __always_inline void arch_spin_lock(arch_spinlock_t *lock)
-{
-	__ticket_spin_lock(lock);
-}
-
-static __always_inline int arch_spin_trylock(arch_spinlock_t *lock)
-{
-	return __ticket_spin_trylock(lock);
-}
-
-static __always_inline void arch_spin_unlock(arch_spinlock_t *lock)
-{
-	__ticket_spin_unlock(lock);
-}
-
 static __always_inline void arch_spin_lock_flags(arch_spinlock_t *lock,
 						  unsigned long flags)
 {
Signature · 1 line
1.7.2.3
#18 lore raw

PATCH 8/14 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 8e379d3..cfa80b5 100644
@@ -108,7 +108,7 @@ static __always_inline void __ticket_unlock_kick(struct arch_spinlock *lock, __t
 		____ticket_unlock_kick(lock, next);
 }
 
-static __always_inline void __ticket_spin_lock(struct arch_spinlock *lock)
+static __always_inline void arch_spin_lock(struct arch_spinlock *lock)
 {
 	register struct __raw_tickets inc;
 
@@ -128,7 +128,7 @@ static __always_inline void __ticket_spin_lock(struct arch_spinlock *lock)
 out:	barrier();		/* make sure nothing creeps before the lock is taken */
 }
 
-static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
+static __always_inline int arch_spin_trylock(arch_spinlock_t *lock)
 {
 	arch_spinlock_t old, new;
 
@@ -142,7 +142,7 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 	return cmpxchg(&lock->head_tail, old.head_tail, new.head_tail) == old.head_tail;
 }
 
-static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
+static __always_inline void arch_spin_unlock(arch_spinlock_t *lock)
 {
 	__ticket_t next = lock->tickets.head + 1;
 	__ticket_unlock_release(lock);
@@ -150,46 +150,21 @@ static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
 	barrier();		/* prevent reordering into locked region */
 }
 
-static inline int __ticket_spin_is_locked(arch_spinlock_t *lock)
+static inline int arch_spin_is_locked(arch_spinlock_t *lock)
 {
 	struct __raw_tickets tmp = ACCESS_ONCE(lock->tickets);
 
 	return !!(tmp.tail ^ tmp.head);
 }
 
-static inline int __ticket_spin_is_contended(arch_spinlock_t *lock)
+static inline int arch_spin_is_contended(arch_spinlock_t *lock)
 {
 	struct __raw_tickets tmp = ACCESS_ONCE(lock->tickets);
 
 	return ((tmp.tail - tmp.head) & TICKET_MASK) > 1;
 }
-
-static inline int arch_spin_is_locked(arch_spinlock_t *lock)
-{
-	return __ticket_spin_is_locked(lock);
-}
-
-static inline int arch_spin_is_contended(arch_spinlock_t *lock)
-{
-	return __ticket_spin_is_contended(lock);
-}
 #define arch_spin_is_contended	arch_spin_is_contended
 
-static __always_inline void arch_spin_lock(arch_spinlock_t *lock)
-{
-	__ticket_spin_lock(lock);
-}
-
-static __always_inline int arch_spin_trylock(arch_spinlock_t *lock)
-{
-	return __ticket_spin_trylock(lock);
-}
-
-static __always_inline void arch_spin_unlock(arch_spinlock_t *lock)
-{
-	__ticket_spin_unlock(lock);
-}
-
 static __always_inline void arch_spin_lock_flags(arch_spinlock_t *lock,
 						  unsigned long flags)
 {
Signature · 1 line
1.7.2.3
#19 lore raw

PATCH 9/14 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.

---
 arch/x86/xen/spinlock.c |  281 ++++++-----------------------------------------
 1 files changed, 36 insertions(+), 245 deletions(-)
arch/x86/xen/spinlock.c +36 -245
index 3d9da72..5feb897 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,76 @@ static inline u64 spin_time_start(void)
 	return 0;
 }
 
-static inline void spin_time_accum_total(u64 start)
-{
-}
-static inline void spin_time_accum_spinning(u64 start)
-{
-}
 static inline void spin_time_accum_blocked(u64 start)
 {
 }
 #endif  /* CONFIG_XEN_DEBUG_FS */
 
-struct xen_spinlock {
-	unsigned char lock;		/* 0 -> free; 1 -> locked */
-	unsigned short spinners;	/* count of waiting cpus */
+struct xen_lock_waiting {
+	struct arch_spinlock *lock;
+	__ticket_t want;
 };
 
 static DEFINE_PER_CPU(int, lock_kicker_irq) = -1;
+static DEFINE_PER_CPU(struct xen_lock_waiting, lock_waiting);
+static cpumask_t waiting_cpus;
 
-#if 0
-static int xen_spin_is_locked(struct arch_spinlock *lock)
-{
-	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
-
-	return xl->lock != 0;
-}
-
-static int xen_spin_is_contended(struct arch_spinlock *lock)
-{
-	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
-
-	/* Not strictly true; this is only the count of contended
-	   lock-takers entering the slow path. */
-	return xl->spinners != 0;
-}
-
-static int xen_spin_trylock(struct arch_spinlock *lock)
-{
-	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
-	u8 old = 1;
-
-	asm("xchgb %b0,%1"
-	    : "+q" (old), "+m" (xl->lock) : : "memory");
-
-	return old == 0;
-}
-
-static DEFINE_PER_CPU(struct xen_spinlock *, lock_spinners);
-
-/*
- * Mark a cpu as interested in a lock.  Returns the CPU's previous
- * lock of interest, in case we got preempted by an interrupt.
- */
-static inline struct xen_spinlock *spinning_lock(struct xen_spinlock *xl)
-{
-	struct xen_spinlock *prev;
-
-	prev = __get_cpu_var(lock_spinners);
-	__get_cpu_var(lock_spinners) = xl;
-
-	wmb();			/* set lock of interest before count */
-
-	asm(LOCK_PREFIX " incw %0"
-	    : "+m" (xl->spinners) : : "memory");
-
-	return prev;
-}
-
-/*
- * Mark a cpu as no longer interested in a lock.  Restores previous
- * lock of interest (NULL for none).
- */
-static inline void unspinning_lock(struct xen_spinlock *xl, struct xen_spinlock *prev)
-{
-	asm(LOCK_PREFIX " decw %0"
-	    : "+m" (xl->spinners) : : "memory");
-	wmb();			/* decrement count before restoring lock */
-	__get_cpu_var(lock_spinners) = prev;
-}
-
-static noinline int xen_spin_lock_slow(struct arch_spinlock *lock, bool irq_enable)
+static void xen_lock_spinning(struct arch_spinlock *lock, unsigned want)
 {
-	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
-	struct xen_spinlock *prev;
 	int irq = __get_cpu_var(lock_kicker_irq);
-	int ret;
+	struct xen_lock_waiting *w = &__get_cpu_var(lock_waiting);
+	int cpu = smp_processor_id();
 	u64 start;
 
 	/* If kicker interrupts not initialized yet, just spin */
 	if (irq == -1)
-		return 0;
+		return;
 
 	start = spin_time_start();
 
-	/* announce we're spinning */
-	prev = spinning_lock(xl);
+	w->want = want;
+	w->lock = lock;
+
+	/* This uses set_bit, which atomic and therefore a barrier */
+	cpumask_set_cpu(cpu, &waiting_cpus);
 
 	ADD_STATS(taken_slow, 1);
-	ADD_STATS(taken_slow_nested, prev != NULL);
-
-	do {
-		unsigned long flags;
-
-		/* clear pending */
-		xen_clear_irq_pending(irq);
-
-		/* check again make sure it didn't become free while
-		   we weren't looking  */
-		ret = xen_spin_trylock(lock);
-		if (ret) {
-			ADD_STATS(taken_slow_pickup, 1);
-
-			/*
-			 * If we interrupted another spinlock while it
-			 * was blocking, make sure it doesn't block
-			 * without rechecking the lock.
-			 */
-			if (prev != NULL)
-				xen_set_irq_pending(irq);
-			goto out;
-		}
 
-		flags = arch_local_save_flags();
-		if (irq_enable) {
-			ADD_STATS(taken_slow_irqenable, 1);
-			raw_local_irq_enable();
-		}
+	/* clear pending */
+	xen_clear_irq_pending(irq);
 
-		/*
-		 * Block until irq becomes pending.  If we're
-		 * interrupted at this point (after the trylock but
-		 * before entering the block), then the nested lock
-		 * handler guarantees that the irq will be left
-		 * pending if there's any chance the lock became free;
-		 * xen_poll_irq() returns immediately if the irq is
-		 * pending.
-		 */
-		xen_poll_irq(irq);
+	/* Only check lock once pending cleared */
+	barrier();
 
-		raw_local_irq_restore(flags);
+	/* check again make sure it didn't become free while
+	   we weren't looking  */
+	if (ACCESS_ONCE(lock->tickets.head) == want) {
+		ADD_STATS(taken_slow_pickup, 1);
+		goto out;
+	}
 
-		ADD_STATS(taken_slow_spurious, !xen_test_irq_pending(irq));
-	} while (!xen_test_irq_pending(irq)); /* check for spurious wakeups */
+	/* Block until irq becomes pending (or perhaps a spurious wakeup) */
+	xen_poll_irq(irq);
+	ADD_STATS(taken_slow_spurious, !xen_test_irq_pending(irq));
 
 	kstat_incr_irqs_this_cpu(irq, irq_to_desc(irq));
 
 out:
-	unspinning_lock(xl, prev);
+	cpumask_clear_cpu(cpu, &waiting_cpus);
+	w->lock = NULL;
 	spin_time_accum_blocked(start);
-
-	return ret;
 }
 
-static inline void __xen_spin_lock(struct arch_spinlock *lock, bool irq_enable)
-{
-	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
-	unsigned timeout;
-	u8 oldval;
-	u64 start_spin;
-
-	ADD_STATS(taken, 1);
-
-	start_spin = spin_time_start();
-
-	do {
-		u64 start_spin_fast = spin_time_start();
-
-		timeout = TIMEOUT;
-
-		asm("1: xchgb %1,%0\n"
-		    "   testb %1,%1\n"
-		    "   jz 3f\n"
-		    "2: rep;nop\n"
-		    "   cmpb $0,%0\n"
-		    "   je 1b\n"
-		    "   dec %2\n"
-		    "   jnz 2b\n"
-		    "3:\n"
-		    : "+m" (xl->lock), "=q" (oldval), "+r" (timeout)
-		    : "1" (1)
-		    : "memory");
-
-		spin_time_accum_spinning(start_spin_fast);
-
-	} while (unlikely(oldval != 0 &&
-			  (TIMEOUT == ~0 || !xen_spin_lock_slow(lock, irq_enable))));
-
-	spin_time_accum_total(start_spin);
-}
-
-static void xen_spin_lock(struct arch_spinlock *lock)
-{
-	__xen_spin_lock(lock, false);
-}
-
-static void xen_spin_lock_flags(struct arch_spinlock *lock, unsigned long flags)
-{
-	__xen_spin_lock(lock, !raw_irqs_disabled_flags(flags));
-}
-
-static noinline void xen_spin_unlock_slow(struct xen_spinlock *xl)
+static void xen_unlock_kick(struct arch_spinlock *lock, unsigned next)
 {
 	int cpu;
 
 	ADD_STATS(released_slow, 1);
 
-	for_each_online_cpu(cpu) {
-		/* XXX should mix up next cpu selection */
-		if (per_cpu(lock_spinners, cpu) == xl) {
+	for_each_cpu(cpu, &waiting_cpus) {
+		const struct xen_lock_waiting *w = &per_cpu(lock_waiting, cpu);
+
+		if (w->lock == lock && w->want == next) {
 			ADD_STATS(released_slow_kicked, 1);
 			xen_send_IPI_one(cpu, XEN_SPIN_UNLOCK_VECTOR);
 			break;
@@ -320,28 +155,6 @@ static noinline void xen_spin_unlock_slow(struct xen_spinlock *xl)
 	}
 }
 
-static void xen_spin_unlock(struct arch_spinlock *lock)
-{
-	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
-
-	ADD_STATS(released, 1);
-
-	smp_wmb();		/* make sure no writes get moved after unlock */
-	xl->lock = 0;		/* release lock */
-
-	/*
-	 * Make sure unlock happens before checking for waiting
-	 * spinners.  We need a strong barrier to enforce the
-	 * write-read ordering to different memory locations, as the
-	 * CPU makes no implied guarantees about their ordering.
-	 */
-	mb();
-
-	if (unlikely(xl->spinners))
-		xen_spin_unlock_slow(xl);
-}
-#endif
-
 static irqreturn_t dummy_handler(int irq, void *dev_id)
 {
 	BUG();
@@ -376,14 +189,8 @@ void xen_uninit_lock_cpu(int cpu)
 
 void __init xen_init_spinlocks(void)
 {
-#if 0
-	pv_lock_ops.spin_is_locked = xen_spin_is_locked;
-	pv_lock_ops.spin_is_contended = xen_spin_is_contended;
-	pv_lock_ops.spin_lock = xen_spin_lock;
-	pv_lock_ops.spin_lock_flags = xen_spin_lock_flags;
-	pv_lock_ops.spin_trylock = xen_spin_trylock;
-	pv_lock_ops.spin_unlock = xen_spin_unlock;
-#endif
+	pv_lock_ops.lock_spinning = xen_lock_spinning;
+	pv_lock_ops.unlock_kick = xen_unlock_kick;
 }
 
 #ifdef CONFIG_XEN_DEBUG_FS
@@ -401,37 +208,21 @@ static int __init xen_spinlock_debugfs(void)
 
 	debugfs_create_u8("zero_stats", 0644, d_spin_debug, &zero_stats);
 
-	debugfs_create_u32("timeout", 0644, d_spin_debug, &lock_timeout);
-
-	debugfs_create_u64("taken", 0444, d_spin_debug, &spinlock_stats.taken);
 	debugfs_create_u32("taken_slow", 0444, d_spin_debug,
 			   &spinlock_stats.taken_slow);
-	debugfs_create_u32("taken_slow_nested", 0444, d_spin_debug,
-			   &spinlock_stats.taken_slow_nested);
 	debugfs_create_u32("taken_slow_pickup", 0444, d_spin_debug,
 			   &spinlock_stats.taken_slow_pickup);
 	debugfs_create_u32("taken_slow_spurious", 0444, d_spin_debug,
 			   &spinlock_stats.taken_slow_spurious);
-	debugfs_create_u32("taken_slow_irqenable", 0444, d_spin_debug,
-			   &spinlock_stats.taken_slow_irqenable);
 
-	debugfs_create_u64("released", 0444, d_spin_debug, &spinlock_stats.released);
 	debugfs_create_u32("released_slow", 0444, d_spin_debug,
 			   &spinlock_stats.released_slow);
 	debugfs_create_u32("released_slow_kicked", 0444, d_spin_debug,
 			   &spinlock_stats.released_slow_kicked);
 
-	debugfs_create_u64("time_spinning", 0444, d_spin_debug,
-			   &spinlock_stats.time_spinning);
 	debugfs_create_u64("time_blocked", 0444, d_spin_debug,
 			   &spinlock_stats.time_blocked);
-	debugfs_create_u64("time_total", 0444, d_spin_debug,
-			   &spinlock_stats.time_total);
 
-	xen_debugfs_create_u32_array("histo_total", 0444, d_spin_debug,
-				     spinlock_stats.histo_spin_total, HISTO_BUCKETS + 1);
-	xen_debugfs_create_u32_array("histo_spinning", 0444, d_spin_debug,
-				     spinlock_stats.histo_spin_spinning, HISTO_BUCKETS + 1);
 	xen_debugfs_create_u32_array("histo_blocked", 0444, d_spin_debug,
 				     spinlock_stats.histo_spin_blocked, HISTO_BUCKETS + 1);
 
Signature · 1 line
1.7.2.3
#30 lore raw

PATCH 9/14 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.

---
 arch/x86/xen/spinlock.c |  281 ++++++-----------------------------------------
 1 files changed, 36 insertions(+), 245 deletions(-)
arch/x86/xen/spinlock.c +36 -245
index 3d9da72..5feb897 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,76 @@ static inline u64 spin_time_start(void)
 	return 0;
 }
 
-static inline void spin_time_accum_total(u64 start)
-{
-}
-static inline void spin_time_accum_spinning(u64 start)
-{
-}
 static inline void spin_time_accum_blocked(u64 start)
 {
 }
 #endif  /* CONFIG_XEN_DEBUG_FS */
 
-struct xen_spinlock {
-	unsigned char lock;		/* 0 -> free; 1 -> locked */
-	unsigned short spinners;	/* count of waiting cpus */
+struct xen_lock_waiting {
+	struct arch_spinlock *lock;
+	__ticket_t want;
 };
 
 static DEFINE_PER_CPU(int, lock_kicker_irq) = -1;
+static DEFINE_PER_CPU(struct xen_lock_waiting, lock_waiting);
+static cpumask_t waiting_cpus;
 
-#if 0
-static int xen_spin_is_locked(struct arch_spinlock *lock)
-{
-	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
-
-	return xl->lock != 0;
-}
-
-static int xen_spin_is_contended(struct arch_spinlock *lock)
-{
-	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
-
-	/* Not strictly true; this is only the count of contended
-	   lock-takers entering the slow path. */
-	return xl->spinners != 0;
-}
-
-static int xen_spin_trylock(struct arch_spinlock *lock)
-{
-	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
-	u8 old = 1;
-
-	asm("xchgb %b0,%1"
-	    : "+q" (old), "+m" (xl->lock) : : "memory");
-
-	return old == 0;
-}
-
-static DEFINE_PER_CPU(struct xen_spinlock *, lock_spinners);
-
-/*
- * Mark a cpu as interested in a lock.  Returns the CPU's previous
- * lock of interest, in case we got preempted by an interrupt.
- */
-static inline struct xen_spinlock *spinning_lock(struct xen_spinlock *xl)
-{
-	struct xen_spinlock *prev;
-
-	prev = __get_cpu_var(lock_spinners);
-	__get_cpu_var(lock_spinners) = xl;
-
-	wmb();			/* set lock of interest before count */
-
-	asm(LOCK_PREFIX " incw %0"
-	    : "+m" (xl->spinners) : : "memory");
-
-	return prev;
-}
-
-/*
- * Mark a cpu as no longer interested in a lock.  Restores previous
- * lock of interest (NULL for none).
- */
-static inline void unspinning_lock(struct xen_spinlock *xl, struct xen_spinlock *prev)
-{
-	asm(LOCK_PREFIX " decw %0"
-	    : "+m" (xl->spinners) : : "memory");
-	wmb();			/* decrement count before restoring lock */
-	__get_cpu_var(lock_spinners) = prev;
-}
-
-static noinline int xen_spin_lock_slow(struct arch_spinlock *lock, bool irq_enable)
+static void xen_lock_spinning(struct arch_spinlock *lock, unsigned want)
 {
-	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
-	struct xen_spinlock *prev;
 	int irq = __get_cpu_var(lock_kicker_irq);
-	int ret;
+	struct xen_lock_waiting *w = &__get_cpu_var(lock_waiting);
+	int cpu = smp_processor_id();
 	u64 start;
 
 	/* If kicker interrupts not initialized yet, just spin */
 	if (irq == -1)
-		return 0;
+		return;
 
 	start = spin_time_start();
 
-	/* announce we're spinning */
-	prev = spinning_lock(xl);
+	w->want = want;
+	w->lock = lock;
+
+	/* This uses set_bit, which atomic and therefore a barrier */
+	cpumask_set_cpu(cpu, &waiting_cpus);
 
 	ADD_STATS(taken_slow, 1);
-	ADD_STATS(taken_slow_nested, prev != NULL);
-
-	do {
-		unsigned long flags;
-
-		/* clear pending */
-		xen_clear_irq_pending(irq);
-
-		/* check again make sure it didn't become free while
-		   we weren't looking  */
-		ret = xen_spin_trylock(lock);
-		if (ret) {
-			ADD_STATS(taken_slow_pickup, 1);
-
-			/*
-			 * If we interrupted another spinlock while it
-			 * was blocking, make sure it doesn't block
-			 * without rechecking the lock.
-			 */
-			if (prev != NULL)
-				xen_set_irq_pending(irq);
-			goto out;
-		}
 
-		flags = arch_local_save_flags();
-		if (irq_enable) {
-			ADD_STATS(taken_slow_irqenable, 1);
-			raw_local_irq_enable();
-		}
+	/* clear pending */
+	xen_clear_irq_pending(irq);
 
-		/*
-		 * Block until irq becomes pending.  If we're
-		 * interrupted at this point (after the trylock but
-		 * before entering the block), then the nested lock
-		 * handler guarantees that the irq will be left
-		 * pending if there's any chance the lock became free;
-		 * xen_poll_irq() returns immediately if the irq is
-		 * pending.
-		 */
-		xen_poll_irq(irq);
+	/* Only check lock once pending cleared */
+	barrier();
 
-		raw_local_irq_restore(flags);
+	/* check again make sure it didn't become free while
+	   we weren't looking  */
+	if (ACCESS_ONCE(lock->tickets.head) == want) {
+		ADD_STATS(taken_slow_pickup, 1);
+		goto out;
+	}
 
-		ADD_STATS(taken_slow_spurious, !xen_test_irq_pending(irq));
-	} while (!xen_test_irq_pending(irq)); /* check for spurious wakeups */
+	/* Block until irq becomes pending (or perhaps a spurious wakeup) */
+	xen_poll_irq(irq);
+	ADD_STATS(taken_slow_spurious, !xen_test_irq_pending(irq));
 
 	kstat_incr_irqs_this_cpu(irq, irq_to_desc(irq));
 
 out:
-	unspinning_lock(xl, prev);
+	cpumask_clear_cpu(cpu, &waiting_cpus);
+	w->lock = NULL;
 	spin_time_accum_blocked(start);
-
-	return ret;
 }
 
-static inline void __xen_spin_lock(struct arch_spinlock *lock, bool irq_enable)
-{
-	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
-	unsigned timeout;
-	u8 oldval;
-	u64 start_spin;
-
-	ADD_STATS(taken, 1);
-
-	start_spin = spin_time_start();
-
-	do {
-		u64 start_spin_fast = spin_time_start();
-
-		timeout = TIMEOUT;
-
-		asm("1: xchgb %1,%0\n"
-		    "   testb %1,%1\n"
-		    "   jz 3f\n"
-		    "2: rep;nop\n"
-		    "   cmpb $0,%0\n"
-		    "   je 1b\n"
-		    "   dec %2\n"
-		    "   jnz 2b\n"
-		    "3:\n"
-		    : "+m" (xl->lock), "=q" (oldval), "+r" (timeout)
-		    : "1" (1)
-		    : "memory");
-
-		spin_time_accum_spinning(start_spin_fast);
-
-	} while (unlikely(oldval != 0 &&
-			  (TIMEOUT == ~0 || !xen_spin_lock_slow(lock, irq_enable))));
-
-	spin_time_accum_total(start_spin);
-}
-
-static void xen_spin_lock(struct arch_spinlock *lock)
-{
-	__xen_spin_lock(lock, false);
-}
-
-static void xen_spin_lock_flags(struct arch_spinlock *lock, unsigned long flags)
-{
-	__xen_spin_lock(lock, !raw_irqs_disabled_flags(flags));
-}
-
-static noinline void xen_spin_unlock_slow(struct xen_spinlock *xl)
+static void xen_unlock_kick(struct arch_spinlock *lock, unsigned next)
 {
 	int cpu;
 
 	ADD_STATS(released_slow, 1);
 
-	for_each_online_cpu(cpu) {
-		/* XXX should mix up next cpu selection */
-		if (per_cpu(lock_spinners, cpu) == xl) {
+	for_each_cpu(cpu, &waiting_cpus) {
+		const struct xen_lock_waiting *w = &per_cpu(lock_waiting, cpu);
+
+		if (w->lock == lock && w->want == next) {
 			ADD_STATS(released_slow_kicked, 1);
 			xen_send_IPI_one(cpu, XEN_SPIN_UNLOCK_VECTOR);
 			break;
@@ -320,28 +155,6 @@ static noinline void xen_spin_unlock_slow(struct xen_spinlock *xl)
 	}
 }
 
-static void xen_spin_unlock(struct arch_spinlock *lock)
-{
-	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
-
-	ADD_STATS(released, 1);
-
-	smp_wmb();		/* make sure no writes get moved after unlock */
-	xl->lock = 0;		/* release lock */
-
-	/*
-	 * Make sure unlock happens before checking for waiting
-	 * spinners.  We need a strong barrier to enforce the
-	 * write-read ordering to different memory locations, as the
-	 * CPU makes no implied guarantees about their ordering.
-	 */
-	mb();
-
-	if (unlikely(xl->spinners))
-		xen_spin_unlock_slow(xl);
-}
-#endif
-
 static irqreturn_t dummy_handler(int irq, void *dev_id)
 {
 	BUG();
@@ -376,14 +189,8 @@ void xen_uninit_lock_cpu(int cpu)
 
 void __init xen_init_spinlocks(void)
 {
-#if 0
-	pv_lock_ops.spin_is_locked = xen_spin_is_locked;
-	pv_lock_ops.spin_is_contended = xen_spin_is_contended;
-	pv_lock_ops.spin_lock = xen_spin_lock;
-	pv_lock_ops.spin_lock_flags = xen_spin_lock_flags;
-	pv_lock_ops.spin_trylock = xen_spin_trylock;
-	pv_lock_ops.spin_unlock = xen_spin_unlock;
-#endif
+	pv_lock_ops.lock_spinning = xen_lock_spinning;
+	pv_lock_ops.unlock_kick = xen_unlock_kick;
 }
 
 #ifdef CONFIG_XEN_DEBUG_FS
@@ -401,37 +208,21 @@ static int __init xen_spinlock_debugfs(void)
 
 	debugfs_create_u8("zero_stats", 0644, d_spin_debug, &zero_stats);
 
-	debugfs_create_u32("timeout", 0644, d_spin_debug, &lock_timeout);
-
-	debugfs_create_u64("taken", 0444, d_spin_debug, &spinlock_stats.taken);
 	debugfs_create_u32("taken_slow", 0444, d_spin_debug,
 			   &spinlock_stats.taken_slow);
-	debugfs_create_u32("taken_slow_nested", 0444, d_spin_debug,
-			   &spinlock_stats.taken_slow_nested);
 	debugfs_create_u32("taken_slow_pickup", 0444, d_spin_debug,
 			   &spinlock_stats.taken_slow_pickup);
 	debugfs_create_u32("taken_slow_spurious", 0444, d_spin_debug,
 			   &spinlock_stats.taken_slow_spurious);
-	debugfs_create_u32("taken_slow_irqenable", 0444, d_spin_debug,
-			   &spinlock_stats.taken_slow_irqenable);
 
-	debugfs_create_u64("released", 0444, d_spin_debug, &spinlock_stats.released);
 	debugfs_create_u32("released_slow", 0444, d_spin_debug,
 			   &spinlock_stats.released_slow);
 	debugfs_create_u32("released_slow_kicked", 0444, d_spin_debug,
 			   &spinlock_stats.released_slow_kicked);
 
-	debugfs_create_u64("time_spinning", 0444, d_spin_debug,
-			   &spinlock_stats.time_spinning);
 	debugfs_create_u64("time_blocked", 0444, d_spin_debug,
 			   &spinlock_stats.time_blocked);
-	debugfs_create_u64("time_total", 0444, d_spin_debug,
-			   &spinlock_stats.time_total);
 
-	xen_debugfs_create_u32_array("histo_total", 0444, d_spin_debug,
-				     spinlock_stats.histo_spin_total, HISTO_BUCKETS + 1);
-	xen_debugfs_create_u32_array("histo_spinning", 0444, d_spin_debug,
-				     spinlock_stats.histo_spin_spinning, HISTO_BUCKETS + 1);
 	xen_debugfs_create_u32_array("histo_blocked", 0444, d_spin_debug,
 				     spinlock_stats.histo_spin_blocked, HISTO_BUCKETS + 1);
 
Signature · 1 line
1.7.2.3
#31 lore raw

PATCH 10/14 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 c864775..6f275ca 100644
@@ -719,7 +719,7 @@ static inline void __set_fixmap(unsigned /* enum fixed_addresses */ idx,
 
 static inline void __ticket_lock_spinning(struct arch_spinlock *lock, unsigned ticket)
 {
-	PVOP_VCALL2(pv_lock_ops.lock_spinning, lock, ticket);
+	PVOP_VCALLEE2(pv_lock_ops.lock_spinning, lock, ticket);
 }
 
 static inline void ____ticket_unlock_kick(struct arch_spinlock *lock, unsigned ticket)
arch/x86/include/asm/paravirt_types.h +1 -1
index 1078474..53f249a 100644
@@ -315,7 +315,7 @@ struct pv_mmu_ops {
 
 struct arch_spinlock;
 struct pv_lock_ops {
-	void (*lock_spinning)(struct arch_spinlock *lock, unsigned ticket);
+	struct paravirt_callee_save lock_spinning;
 	void (*unlock_kick)(struct arch_spinlock *lock, unsigned ticket);
 };
 
arch/x86/kernel/paravirt-spinlocks.c +1 -1
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 5feb897..c31c5a3 100644
@@ -137,6 +137,7 @@ out:
 	w->lock = NULL;
 	spin_time_accum_blocked(start);
 }
+PV_CALLEE_SAVE_REGS_THUNK(xen_lock_spinning);
 
 static void xen_unlock_kick(struct arch_spinlock *lock, unsigned next)
 {
@@ -189,7 +190,7 @@ void xen_uninit_lock_cpu(int cpu)
 
 void __init xen_init_spinlocks(void)
 {
-	pv_lock_ops.lock_spinning = xen_lock_spinning;
+	pv_lock_ops.lock_spinning = PV_CALLEE_SAVE(xen_lock_spinning);
 	pv_lock_ops.unlock_kick = xen_unlock_kick;
 }
 
Signature · 1 line
1.7.2.3
#32 lore raw

PATCH 10/14 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 c864775..6f275ca 100644
@@ -719,7 +719,7 @@ static inline void __set_fixmap(unsigned /* enum fixed_addresses */ idx,
 
 static inline void __ticket_lock_spinning(struct arch_spinlock *lock, unsigned ticket)
 {
-	PVOP_VCALL2(pv_lock_ops.lock_spinning, lock, ticket);
+	PVOP_VCALLEE2(pv_lock_ops.lock_spinning, lock, ticket);
 }
 
 static inline void ____ticket_unlock_kick(struct arch_spinlock *lock, unsigned ticket)
arch/x86/include/asm/paravirt_types.h +1 -1
index 1078474..53f249a 100644
@@ -315,7 +315,7 @@ struct pv_mmu_ops {
 
 struct arch_spinlock;
 struct pv_lock_ops {
-	void (*lock_spinning)(struct arch_spinlock *lock, unsigned ticket);
+	struct paravirt_callee_save lock_spinning;
 	void (*unlock_kick)(struct arch_spinlock *lock, unsigned ticket);
 };
 
arch/x86/kernel/paravirt-spinlocks.c +1 -1
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 5feb897..c31c5a3 100644
@@ -137,6 +137,7 @@ out:
 	w->lock = NULL;
 	spin_time_accum_blocked(start);
 }
+PV_CALLEE_SAVE_REGS_THUNK(xen_lock_spinning);
 
 static void xen_unlock_kick(struct arch_spinlock *lock, unsigned next)
 {
@@ -189,7 +190,7 @@ void xen_uninit_lock_cpu(int cpu)
 
 void __init xen_init_spinlocks(void)
 {
-	pv_lock_ops.lock_spinning = xen_lock_spinning;
+	pv_lock_ops.lock_spinning = PV_CALLEE_SAVE(xen_lock_spinning);
 	pv_lock_ops.unlock_kick = xen_unlock_kick;
 }
 
Signature · 1 line
1.7.2.3
#33 lore raw

PATCH 11/14 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 e832768..a615c9c 100644
@@ -531,6 +531,9 @@ config PARAVIRT_SPINLOCKS
 
 	  If you are unsure how to answer this question, answer N.
 
+config ARCH_NOINLINE_SPIN_UNLOCK
+       def_bool PARAVIRT_SPINLOCKS
+
 config PARAVIRT_CLOCK
 	bool
 
kernel/Kconfig.locks +1 -1
index 88c92fb..3216c22 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.2.3
#34 lore raw

PATCH 11/14 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 e832768..a615c9c 100644
@@ -531,6 +531,9 @@ config PARAVIRT_SPINLOCKS
 
 	  If you are unsure how to answer this question, answer N.
 
+config ARCH_NOINLINE_SPIN_UNLOCK
+       def_bool PARAVIRT_SPINLOCKS
+
 config PARAVIRT_CLOCK
 	bool
 
kernel/Kconfig.locks +1 -1
index 88c92fb..3216c22 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.2.3
#35 lore raw

PATCH 12/14 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       |   18 +++++++++---------
 arch/x86/include/asm/spinlock_types.h |   10 +++++++++-
 2 files changed, 18 insertions(+), 10 deletions(-)
arch/x86/include/asm/spinlock.h +9 -9
index cfa80b5..9e1c7ce 100644
@@ -36,17 +36,17 @@
 static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)
 {
 	if (sizeof(lock->tickets.head) == sizeof(u8))
-		asm (LOCK_PREFIX "incb %0"
-		     : "+m" (lock->tickets.head) : : "memory");
+		asm (LOCK_PREFIX "addb %1, %0"
+		     : "+m" (lock->tickets.head) : "i" (TICKET_LOCK_INC) : "memory");
 	else
-		asm (LOCK_PREFIX "incw %0"
-		     : "+m" (lock->tickets.head) : : "memory");
+		asm (LOCK_PREFIX "addw %1, %0"
+		     : "+m" (lock->tickets.head) : "i" (TICKET_LOCK_INC) : "memory");
 
 }
 #else
 static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)
 {
-	lock->tickets.head++;
+	lock->tickets.head += TICKET_LOCK_INC;
 }
 #endif
 
@@ -84,7 +84,7 @@ static __always_inline void ____ticket_unlock_kick(struct arch_spinlock *lock, u
  */
 static __always_inline struct __raw_tickets __ticket_spin_claim(struct arch_spinlock *lock)
 {
-	register struct __raw_tickets tickets = { .tail = 1 };
+	register struct __raw_tickets tickets = { .tail = TICKET_LOCK_INC };
 
 	if (sizeof(lock->tickets.head) == sizeof(u8))
 		asm volatile (LOCK_PREFIX "xaddw %w0, %1\n"
@@ -136,7 +136,7 @@ static __always_inline int arch_spin_trylock(arch_spinlock_t *lock)
 	if (old.tickets.head != old.tickets.tail)
 		return 0;
 
-	new.head_tail = old.head_tail + (1 << TICKET_SHIFT);
+	new.head_tail = old.head_tail + (TICKET_LOCK_INC << TICKET_SHIFT);
 
 	/* cmpxchg is a full barrier, so nothing can move before it */
 	return cmpxchg(&lock->head_tail, old.head_tail, new.head_tail) == old.head_tail;
@@ -144,7 +144,7 @@ static __always_inline int arch_spin_trylock(arch_spinlock_t *lock)
 
 static __always_inline void arch_spin_unlock(arch_spinlock_t *lock)
 {
-	__ticket_t next = lock->tickets.head + 1;
+	__ticket_t next = lock->tickets.head + TICKET_LOCK_INC;
 	__ticket_unlock_release(lock);
 	__ticket_unlock_kick(lock, next);
 	barrier();		/* prevent reordering into locked region */
@@ -161,7 +161,7 @@ static inline int arch_spin_is_contended(arch_spinlock_t *lock)
 {
 	struct __raw_tickets tmp = ACCESS_ONCE(lock->tickets);
 
-	return ((tmp.tail - tmp.head) & TICKET_MASK) > 1;
+	return ((tmp.tail - tmp.head) & TICKET_MASK) > TICKET_LOCK_INC;
 }
 #define arch_spin_is_contended	arch_spin_is_contended
 
arch/x86/include/asm/spinlock_types.h +9 -1
index 72e154e..0553c0b 100644
@@ -7,7 +7,13 @@
 
 #include <linux/types.h>
 
-#if (CONFIG_NR_CPUS < 256)
+#ifdef CONFIG_PARAVIRT_SPINLOCKS
+#define __TICKET_LOCK_INC	2
+#else
+#define __TICKET_LOCK_INC	1
+#endif
+
+#if (CONFIG_NR_CPUS < (256 / __TICKET_LOCK_INC))
 typedef u8  __ticket_t;
 typedef u16 __ticketpair_t;
 #else
@@ -15,6 +21,8 @@ typedef u16 __ticket_t;
 typedef u32 __ticketpair_t;
 #endif
 
+#define TICKET_LOCK_INC	((__ticket_t)__TICKET_LOCK_INC)
+
 #define TICKET_SHIFT	(sizeof(__ticket_t) * 8)
 #define TICKET_MASK	((__ticket_t)((1 << TICKET_SHIFT) - 1))
 
Signature · 1 line
1.7.2.3
#36 lore raw

PATCH 12/14 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       |   18 +++++++++---------
 arch/x86/include/asm/spinlock_types.h |   10 +++++++++-
 2 files changed, 18 insertions(+), 10 deletions(-)
arch/x86/include/asm/spinlock.h +9 -9
index cfa80b5..9e1c7ce 100644
@@ -36,17 +36,17 @@
 static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)
 {
 	if (sizeof(lock->tickets.head) == sizeof(u8))
-		asm (LOCK_PREFIX "incb %0"
-		     : "+m" (lock->tickets.head) : : "memory");
+		asm (LOCK_PREFIX "addb %1, %0"
+		     : "+m" (lock->tickets.head) : "i" (TICKET_LOCK_INC) : "memory");
 	else
-		asm (LOCK_PREFIX "incw %0"
-		     : "+m" (lock->tickets.head) : : "memory");
+		asm (LOCK_PREFIX "addw %1, %0"
+		     : "+m" (lock->tickets.head) : "i" (TICKET_LOCK_INC) : "memory");
 
 }
 #else
 static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)
 {
-	lock->tickets.head++;
+	lock->tickets.head += TICKET_LOCK_INC;
 }
 #endif
 
@@ -84,7 +84,7 @@ static __always_inline void ____ticket_unlock_kick(struct arch_spinlock *lock, u
  */
 static __always_inline struct __raw_tickets __ticket_spin_claim(struct arch_spinlock *lock)
 {
-	register struct __raw_tickets tickets = { .tail = 1 };
+	register struct __raw_tickets tickets = { .tail = TICKET_LOCK_INC };
 
 	if (sizeof(lock->tickets.head) == sizeof(u8))
 		asm volatile (LOCK_PREFIX "xaddw %w0, %1\n"
@@ -136,7 +136,7 @@ static __always_inline int arch_spin_trylock(arch_spinlock_t *lock)
 	if (old.tickets.head != old.tickets.tail)
 		return 0;
 
-	new.head_tail = old.head_tail + (1 << TICKET_SHIFT);
+	new.head_tail = old.head_tail + (TICKET_LOCK_INC << TICKET_SHIFT);
 
 	/* cmpxchg is a full barrier, so nothing can move before it */
 	return cmpxchg(&lock->head_tail, old.head_tail, new.head_tail) == old.head_tail;
@@ -144,7 +144,7 @@ static __always_inline int arch_spin_trylock(arch_spinlock_t *lock)
 
 static __always_inline void arch_spin_unlock(arch_spinlock_t *lock)
 {
-	__ticket_t next = lock->tickets.head + 1;
+	__ticket_t next = lock->tickets.head + TICKET_LOCK_INC;
 	__ticket_unlock_release(lock);
 	__ticket_unlock_kick(lock, next);
 	barrier();		/* prevent reordering into locked region */
@@ -161,7 +161,7 @@ static inline int arch_spin_is_contended(arch_spinlock_t *lock)
 {
 	struct __raw_tickets tmp = ACCESS_ONCE(lock->tickets);
 
-	return ((tmp.tail - tmp.head) & TICKET_MASK) > 1;
+	return ((tmp.tail - tmp.head) & TICKET_MASK) > TICKET_LOCK_INC;
 }
 #define arch_spin_is_contended	arch_spin_is_contended
 
arch/x86/include/asm/spinlock_types.h +9 -1
index 72e154e..0553c0b 100644
@@ -7,7 +7,13 @@
 
 #include <linux/types.h>
 
-#if (CONFIG_NR_CPUS < 256)
+#ifdef CONFIG_PARAVIRT_SPINLOCKS
+#define __TICKET_LOCK_INC	2
+#else
+#define __TICKET_LOCK_INC	1
+#endif
+
+#if (CONFIG_NR_CPUS < (256 / __TICKET_LOCK_INC))
 typedef u8  __ticket_t;
 typedef u16 __ticketpair_t;
 #else
@@ -15,6 +21,8 @@ typedef u16 __ticket_t;
 typedef u32 __ticketpair_t;
 #endif
 
+#define TICKET_LOCK_INC	((__ticket_t)__TICKET_LOCK_INC)
+
 #define TICKET_SHIFT	(sizeof(__ticket_t) * 8)
 #define TICKET_MASK	((__ticket_t)((1 << TICKET_SHIFT) - 1))
 
Signature · 1 line
1.7.2.3
#37 lore raw

PATCH 13/14 x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge

From: Jeremy Fitzhardinge <[email protected]>

Maintain a flag in both LSBs of the ticket lock which indicates whether anyone is in the lock slowpath and may need kicking when the current holder unlocks. The flags are set when the first locker enters the slowpath, and cleared when unlocking to an empty queue.

In the specific implementation of lock_spinning(), make sure to set the slowpath flags on the lock just before blocking. We must do this before the last-chance pickup test to prevent a deadlock with the unlocker:

Unlocker Locker

				test for lock pickup
					-> fail
test slowpath + unlock
	-> false
				set slowpath flags
				block

Whereas this works in any ordering:

Unlocker Locker
set slowpath flags test for lock pickup
-> fail
block
test slowpath + unlock

	-> true, kick
---
 arch/x86/include/asm/spinlock.h       |   53 ++++++++++++++++++++++++++++-----
 arch/x86/include/asm/spinlock_types.h |    2 +
 arch/x86/kernel/paravirt-spinlocks.c  |   37 +++++++++++++++++++++++
 arch/x86/xen/spinlock.c               |    4 ++
 4 files changed, 88 insertions(+), 8 deletions(-)
arch/x86/include/asm/spinlock.h +45 -8
index 9e1c7ce..8d1cb42 100644
@@ -53,7 +53,38 @@ static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)
 /* How long a lock should spin before we consider blocking */
 #define SPIN_THRESHOLD	(1 << 11)
 
-#ifndef CONFIG_PARAVIRT_SPINLOCKS
+/* Only defined when CONFIG_PARAVIRT_SPINLOCKS defined, but may as
+ * well leave the prototype always visible.  */
+extern void __ticket_unlock_release_slowpath(struct arch_spinlock *lock);
+
+#ifdef CONFIG_PARAVIRT_SPINLOCKS
+
+/*
+ * Return true if someone is in the slowpath on this lock.  This
+ * should only be used by the current lock-holder.
+ */
+static inline bool __ticket_in_slowpath(struct arch_spinlock *lock)
+{
+	return !!(lock->tickets.tail & TICKET_SLOWPATH_FLAG);
+}
+
+static inline void __ticket_enter_slowpath(struct arch_spinlock *lock)
+{
+	if (sizeof(lock->tickets.tail) == sizeof(u8))
+		asm (LOCK_PREFIX "orb %1, %0"
+		     : "+m" (lock->tickets.tail)
+		     : "i" (TICKET_SLOWPATH_FLAG) : "memory");
+	else
+		asm (LOCK_PREFIX "orw %1, %0"
+		     : "+m" (lock->tickets.tail)
+		     : "i" (TICKET_SLOWPATH_FLAG) : "memory");
+}
+
+#else  /* !CONFIG_PARAVIRT_SPINLOCKS */
+static inline bool __ticket_in_slowpath(struct arch_spinlock *lock)
+{
+	return false;
+}
 
 static __always_inline void __ticket_lock_spinning(struct arch_spinlock *lock, unsigned ticket)
 {
@@ -84,18 +115,22 @@ static __always_inline void ____ticket_unlock_kick(struct arch_spinlock *lock, u
  */
 static __always_inline struct __raw_tickets __ticket_spin_claim(struct arch_spinlock *lock)
 {
-	register struct __raw_tickets tickets = { .tail = TICKET_LOCK_INC };
+	register struct arch_spinlock tickets = {
+		{ .tickets.tail = TICKET_LOCK_INC }
+	};
 
 	if (sizeof(lock->tickets.head) == sizeof(u8))
 		asm volatile (LOCK_PREFIX "xaddw %w0, %1\n"
-			      : "+r" (tickets), "+m" (lock->tickets)
+			      : "+r" (tickets.head_tail), "+m" (lock->tickets)
 			      : : "memory", "cc");
 	else
 		asm volatile (LOCK_PREFIX "xaddl %0, %1\n"
-			     : "+r" (tickets), "+m" (lock->tickets)
+			     : "+r" (tickets.head_tail), "+m" (lock->tickets)
 			     : : "memory", "cc");
 
-	return tickets;
+	tickets.tickets.tail &= ~TICKET_SLOWPATH_FLAG;
+
+	return tickets.tickets;
 }
 
 /* 
@@ -144,9 +179,11 @@ static __always_inline int arch_spin_trylock(arch_spinlock_t *lock)
 
 static __always_inline void arch_spin_unlock(arch_spinlock_t *lock)
 {
-	__ticket_t next = lock->tickets.head + TICKET_LOCK_INC;
-	__ticket_unlock_release(lock);
-	__ticket_unlock_kick(lock, next);
+	barrier();		/* prevent reordering out of locked region */
+	if (unlikely(__ticket_in_slowpath(lock)))
+		__ticket_unlock_release_slowpath(lock);
+	else
+		__ticket_unlock_release(lock);
 	barrier();		/* prevent reordering into locked region */
 }
 
arch/x86/include/asm/spinlock_types.h +2 -0
index 0553c0b..7b383e2 100644
@@ -9,8 +9,10 @@
 
 #ifdef CONFIG_PARAVIRT_SPINLOCKS
 #define __TICKET_LOCK_INC	2
+#define TICKET_SLOWPATH_FLAG	((__ticket_t)1)
 #else
 #define __TICKET_LOCK_INC	1
+#define TICKET_SLOWPATH_FLAG	((__ticket_t)0)
 #endif
 
 #if (CONFIG_NR_CPUS < (256 / __TICKET_LOCK_INC))
arch/x86/kernel/paravirt-spinlocks.c +37 -0
index 4251c1d..21b6986 100644
@@ -15,3 +15,40 @@ struct pv_lock_ops pv_lock_ops = {
 };
 EXPORT_SYMBOL(pv_lock_ops);
 
+
+/*
+ * If we're unlocking and we're leaving the lock uncontended (there's
+ * nobody else waiting for the lock), then we can clear the slowpath
+ * bits.  However, we need to be careful about this because someone
+ * may just be entering as we leave, and enter the slowpath.
+ */
+void __ticket_unlock_release_slowpath(struct arch_spinlock *lock)
+{
+	struct arch_spinlock old, new;
+
+	BUILD_BUG_ON(((__ticket_t)NR_CPUS) != NR_CPUS);
+
+	old = ACCESS_ONCE(*lock);
+
+	new = old;
+	new.tickets.head += TICKET_LOCK_INC;
+
+	/* Clear the slowpath flag */
+	new.tickets.tail &= ~TICKET_SLOWPATH_FLAG;
+
+	/*
+	 * If there's currently people waiting or someone snuck in
+	 * since we read the lock above, then do a normal unlock and
+	 * kick.  If we managed to unlock with no queued waiters, then
+	 * we can clear the slowpath flag.
+	 */
+	if (new.tickets.head != new.tickets.tail ||
+	    cmpxchg(&lock->head_tail,
+		    old.head_tail, new.head_tail) != old.head_tail) {
+		/* still people waiting */
+		__ticket_unlock_release(lock);
+	}
+
+	__ticket_unlock_kick(lock, new.tickets.head);
+}
+EXPORT_SYMBOL(__ticket_unlock_release_slowpath);
arch/x86/xen/spinlock.c +4 -0
index c31c5a3..91f2fd2 100644
@@ -119,6 +119,10 @@ static void xen_lock_spinning(struct arch_spinlock *lock, unsigned want)
 	/* Only check lock once pending cleared */
 	barrier();
 
+	/* Mark entry to slowpath before doing the pickup test to make
+	   sure we don't deadlock with an unlocker. */
+	__ticket_enter_slowpath(lock);
+
 	/* check again make sure it didn't become free while
 	   we weren't looking  */
 	if (ACCESS_ONCE(lock->tickets.head) == want) {
Signature · 1 line
1.7.2.3
#75 lore raw

PATCH 13/14 x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge

From: Jeremy Fitzhardinge <[email protected]>

Maintain a flag in both LSBs of the ticket lock which indicates whether anyone is in the lock slowpath and may need kicking when the current holder unlocks. The flags are set when the first locker enters the slowpath, and cleared when unlocking to an empty queue.

In the specific implementation of lock_spinning(), make sure to set the slowpath flags on the lock just before blocking. We must do this before the last-chance pickup test to prevent a deadlock with the unlocker:

Unlocker Locker

				test for lock pickup
					-> fail
test slowpath + unlock
	-> false
				set slowpath flags
				block

Whereas this works in any ordering:

Unlocker Locker
set slowpath flags test for lock pickup
-> fail
block
test slowpath + unlock

	-> true, kick
---
 arch/x86/include/asm/spinlock.h       |   53 ++++++++++++++++++++++++++++-----
 arch/x86/include/asm/spinlock_types.h |    2 +
 arch/x86/kernel/paravirt-spinlocks.c  |   37 +++++++++++++++++++++++
 arch/x86/xen/spinlock.c               |    4 ++
 4 files changed, 88 insertions(+), 8 deletions(-)
arch/x86/include/asm/spinlock.h +45 -8
index 9e1c7ce..8d1cb42 100644
@@ -53,7 +53,38 @@ static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)
 /* How long a lock should spin before we consider blocking */
 #define SPIN_THRESHOLD	(1 << 11)
 
-#ifndef CONFIG_PARAVIRT_SPINLOCKS
+/* Only defined when CONFIG_PARAVIRT_SPINLOCKS defined, but may as
+ * well leave the prototype always visible.  */
+extern void __ticket_unlock_release_slowpath(struct arch_spinlock *lock);
+
+#ifdef CONFIG_PARAVIRT_SPINLOCKS
+
+/*
+ * Return true if someone is in the slowpath on this lock.  This
+ * should only be used by the current lock-holder.
+ */
+static inline bool __ticket_in_slowpath(struct arch_spinlock *lock)
+{
+	return !!(lock->tickets.tail & TICKET_SLOWPATH_FLAG);
+}
+
+static inline void __ticket_enter_slowpath(struct arch_spinlock *lock)
+{
+	if (sizeof(lock->tickets.tail) == sizeof(u8))
+		asm (LOCK_PREFIX "orb %1, %0"
+		     : "+m" (lock->tickets.tail)
+		     : "i" (TICKET_SLOWPATH_FLAG) : "memory");
+	else
+		asm (LOCK_PREFIX "orw %1, %0"
+		     : "+m" (lock->tickets.tail)
+		     : "i" (TICKET_SLOWPATH_FLAG) : "memory");
+}
+
+#else  /* !CONFIG_PARAVIRT_SPINLOCKS */
+static inline bool __ticket_in_slowpath(struct arch_spinlock *lock)
+{
+	return false;
+}
 
 static __always_inline void __ticket_lock_spinning(struct arch_spinlock *lock, unsigned ticket)
 {
@@ -84,18 +115,22 @@ static __always_inline void ____ticket_unlock_kick(struct arch_spinlock *lock, u
  */
 static __always_inline struct __raw_tickets __ticket_spin_claim(struct arch_spinlock *lock)
 {
-	register struct __raw_tickets tickets = { .tail = TICKET_LOCK_INC };
+	register struct arch_spinlock tickets = {
+		{ .tickets.tail = TICKET_LOCK_INC }
+	};
 
 	if (sizeof(lock->tickets.head) == sizeof(u8))
 		asm volatile (LOCK_PREFIX "xaddw %w0, %1\n"
-			      : "+r" (tickets), "+m" (lock->tickets)
+			      : "+r" (tickets.head_tail), "+m" (lock->tickets)
 			      : : "memory", "cc");
 	else
 		asm volatile (LOCK_PREFIX "xaddl %0, %1\n"
-			     : "+r" (tickets), "+m" (lock->tickets)
+			     : "+r" (tickets.head_tail), "+m" (lock->tickets)
 			     : : "memory", "cc");
 
-	return tickets;
+	tickets.tickets.tail &= ~TICKET_SLOWPATH_FLAG;
+
+	return tickets.tickets;
 }
 
 /* 
@@ -144,9 +179,11 @@ static __always_inline int arch_spin_trylock(arch_spinlock_t *lock)
 
 static __always_inline void arch_spin_unlock(arch_spinlock_t *lock)
 {
-	__ticket_t next = lock->tickets.head + TICKET_LOCK_INC;
-	__ticket_unlock_release(lock);
-	__ticket_unlock_kick(lock, next);
+	barrier();		/* prevent reordering out of locked region */
+	if (unlikely(__ticket_in_slowpath(lock)))
+		__ticket_unlock_release_slowpath(lock);
+	else
+		__ticket_unlock_release(lock);
 	barrier();		/* prevent reordering into locked region */
 }
 
arch/x86/include/asm/spinlock_types.h +2 -0
index 0553c0b..7b383e2 100644
@@ -9,8 +9,10 @@
 
 #ifdef CONFIG_PARAVIRT_SPINLOCKS
 #define __TICKET_LOCK_INC	2
+#define TICKET_SLOWPATH_FLAG	((__ticket_t)1)
 #else
 #define __TICKET_LOCK_INC	1
+#define TICKET_SLOWPATH_FLAG	((__ticket_t)0)
 #endif
 
 #if (CONFIG_NR_CPUS < (256 / __TICKET_LOCK_INC))
arch/x86/kernel/paravirt-spinlocks.c +37 -0
index 4251c1d..21b6986 100644
@@ -15,3 +15,40 @@ struct pv_lock_ops pv_lock_ops = {
 };
 EXPORT_SYMBOL(pv_lock_ops);
 
+
+/*
+ * If we're unlocking and we're leaving the lock uncontended (there's
+ * nobody else waiting for the lock), then we can clear the slowpath
+ * bits.  However, we need to be careful about this because someone
+ * may just be entering as we leave, and enter the slowpath.
+ */
+void __ticket_unlock_release_slowpath(struct arch_spinlock *lock)
+{
+	struct arch_spinlock old, new;
+
+	BUILD_BUG_ON(((__ticket_t)NR_CPUS) != NR_CPUS);
+
+	old = ACCESS_ONCE(*lock);
+
+	new = old;
+	new.tickets.head += TICKET_LOCK_INC;
+
+	/* Clear the slowpath flag */
+	new.tickets.tail &= ~TICKET_SLOWPATH_FLAG;
+
+	/*
+	 * If there's currently people waiting or someone snuck in
+	 * since we read the lock above, then do a normal unlock and
+	 * kick.  If we managed to unlock with no queued waiters, then
+	 * we can clear the slowpath flag.
+	 */
+	if (new.tickets.head != new.tickets.tail ||
+	    cmpxchg(&lock->head_tail,
+		    old.head_tail, new.head_tail) != old.head_tail) {
+		/* still people waiting */
+		__ticket_unlock_release(lock);
+	}
+
+	__ticket_unlock_kick(lock, new.tickets.head);
+}
+EXPORT_SYMBOL(__ticket_unlock_release_slowpath);
arch/x86/xen/spinlock.c +4 -0
index c31c5a3..91f2fd2 100644
@@ -119,6 +119,10 @@ static void xen_lock_spinning(struct arch_spinlock *lock, unsigned want)
 	/* Only check lock once pending cleared */
 	barrier();
 
+	/* Mark entry to slowpath before doing the pickup test to make
+	   sure we don't deadlock with an unlocker. */
+	__ticket_enter_slowpath(lock);
+
 	/* check again make sure it didn't become free while
 	   we weren't looking  */
 	if (ACCESS_ONCE(lock->tickets.head) == want) {
Signature · 1 line
1.7.2.3
#76 lore raw

PATCH 14/14 x86/ticketlocks: tidy up __ticket_unlock_kick()

In reply to Jeremy Fitzhardinge

From: Jeremy Fitzhardinge <[email protected]>

__ticket_unlock_kick() is now only called from known slowpaths, so there's no need for it to do any checking of its own.

---
 arch/x86/include/asm/paravirt.h |    2 +-
 arch/x86/include/asm/spinlock.h |   14 --------------
 2 files changed, 1 insertions(+), 15 deletions(-)
arch/x86/include/asm/paravirt.h +1 -1
index 6f275ca..7755b16 100644
@@ -722,7 +722,7 @@ static inline void __ticket_lock_spinning(struct arch_spinlock *lock, unsigned t
 	PVOP_VCALLEE2(pv_lock_ops.lock_spinning, lock, ticket);
 }
 
-static inline void ____ticket_unlock_kick(struct arch_spinlock *lock, unsigned ticket)
+static inline void __ticket_unlock_kick(struct arch_spinlock *lock, unsigned ticket)
 {
 	PVOP_VCALL2(pv_lock_ops.unlock_kick, lock, ticket);
 }
arch/x86/include/asm/spinlock.h +0 -14
index 8d1cb42..70675bc 100644
@@ -90,10 +90,6 @@ static __always_inline void __ticket_lock_spinning(struct arch_spinlock *lock, u
 {
 }
 
-static __always_inline void ____ticket_unlock_kick(struct arch_spinlock *lock, unsigned ticket)
-{
-}
-
 #endif	/* CONFIG_PARAVIRT_SPINLOCKS */
 
 /*
@@ -133,16 +129,6 @@ static __always_inline struct __raw_tickets __ticket_spin_claim(struct arch_spin
 	return tickets.tickets;
 }
 
-/* 
- * If a spinlock has someone waiting on it, then kick the appropriate
- * waiting cpu.
- */
-static __always_inline void __ticket_unlock_kick(struct arch_spinlock *lock, __ticket_t next)
-{
-	if (unlikely(lock->tickets.tail != next))
-		____ticket_unlock_kick(lock, next);
-}
-
 static __always_inline void arch_spin_lock(struct arch_spinlock *lock)
 {
 	register struct __raw_tickets inc;
Signature · 1 line
1.7.2.3
#77 lore raw

PATCH 14/14 x86/ticketlocks: tidy up __ticket_unlock_kick()

In reply to Jeremy Fitzhardinge

From: Jeremy Fitzhardinge <[email protected]>

__ticket_unlock_kick() is now only called from known slowpaths, so there's no need for it to do any checking of its own.

---
 arch/x86/include/asm/paravirt.h |    2 +-
 arch/x86/include/asm/spinlock.h |   14 --------------
 2 files changed, 1 insertions(+), 15 deletions(-)
arch/x86/include/asm/paravirt.h +1 -1
index 6f275ca..7755b16 100644
@@ -722,7 +722,7 @@ static inline void __ticket_lock_spinning(struct arch_spinlock *lock, unsigned t
 	PVOP_VCALLEE2(pv_lock_ops.lock_spinning, lock, ticket);
 }
 
-static inline void ____ticket_unlock_kick(struct arch_spinlock *lock, unsigned ticket)
+static inline void __ticket_unlock_kick(struct arch_spinlock *lock, unsigned ticket)
 {
 	PVOP_VCALL2(pv_lock_ops.unlock_kick, lock, ticket);
 }
arch/x86/include/asm/spinlock.h +0 -14
index 8d1cb42..70675bc 100644
@@ -90,10 +90,6 @@ static __always_inline void __ticket_lock_spinning(struct arch_spinlock *lock, u
 {
 }
 
-static __always_inline void ____ticket_unlock_kick(struct arch_spinlock *lock, unsigned ticket)
-{
-}
-
 #endif	/* CONFIG_PARAVIRT_SPINLOCKS */
 
 /*
@@ -133,16 +129,6 @@ static __always_inline struct __raw_tickets __ticket_spin_claim(struct arch_spin
 	return tickets.tickets;
 }
 
-/* 
- * If a spinlock has someone waiting on it, then kick the appropriate
- * waiting cpu.
- */
-static __always_inline void __ticket_unlock_kick(struct arch_spinlock *lock, __ticket_t next)
-{
-	if (unlikely(lock->tickets.tail != next))
-		____ticket_unlock_kick(lock, next);
-}
-
 static __always_inline void arch_spin_lock(struct arch_spinlock *lock)
 {
 	register struct __raw_tickets inc;
Signature · 1 line
1.7.2.3
#20 lore raw

Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks

In reply to Jeremy Fitzhardinge
Quoted 15 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/xen/spinlock.c +4 -4
+static void xen_lock_spinning(struct arch_spinlock *lock, unsigned want)
 {
-	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
-	struct xen_spinlock *prev;
 	int irq = __get_cpu_var(lock_kicker_irq);
-	int ret;
+	struct xen_lock_waiting *w = &__get_cpu_var(lock_waiting);
+	int cpu = smp_processor_id();
 	u64 start;
 
 	/* If kicker interrupts not initialized yet, just spin */
 	if (irq == -1)
-		return 0;
+		return;

arch/x86/xen/spinlock.c static inline u64 spin_time_start(void) · line 112

Quoted 10 lines
arch/x86/xen/spinlock.c +5 -2
 
 	start = spin_time_start();
 
-	/* announce we're spinning */
-	prev = spinning_lock(xl);
+	w->want = want;
+	w->lock = lock;
+
+	/* This uses set_bit, which atomic and therefore a barrier */
+	cpumask_set_cpu(cpu, &waiting_cpus);

Since you don't allow nesting, don't you need to disable interrupts before you touch per-CPU state?

Jan

#29 lore raw

Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks

In reply to Jeremy Fitzhardinge
Quoted 15 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/xen/spinlock.c +4 -4
+static void xen_lock_spinning(struct arch_spinlock *lock, unsigned want)
 {
-	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
-	struct xen_spinlock *prev;
 	int irq = __get_cpu_var(lock_kicker_irq);
-	int ret;
+	struct xen_lock_waiting *w = &__get_cpu_var(lock_waiting);
+	int cpu = smp_processor_id();
 	u64 start;
 
 	/* If kicker interrupts not initialized yet, just spin */
 	if (irq == -1)
-		return 0;
+		return;

arch/x86/xen/spinlock.c static inline u64 spin_time_start(void) · line 112

Quoted 10 lines
arch/x86/xen/spinlock.c +5 -2
 
 	start = spin_time_start();
 
-	/* announce we're spinning */
-	prev = spinning_lock(xl);
+	w->want = want;
+	w->lock = lock;
+
+	/* This uses set_bit, which atomic and therefore a barrier */
+	cpumask_set_cpu(cpu, &waiting_cpus);

Since you don't allow nesting, don't you need to disable interrupts before you touch per-CPU state?

Jan

#38 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge

arch/x86/include/asm/spinlock.h static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock) · line 81

Quoted 12 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/include/asm/spinlock.h +11 -0
+static inline void __ticket_enter_slowpath(struct arch_spinlock *lock)
+{
+	if (sizeof(lock->tickets.tail) == sizeof(u8))
+		asm (LOCK_PREFIX "orb %1, %0"
+		     : "+m" (lock->tickets.tail)
+		     : "i" (TICKET_SLOWPATH_FLAG) : "memory");
+	else
+		asm (LOCK_PREFIX "orw %1, %0"
+		     : "+m" (lock->tickets.tail)
+		     : "i" (TICKET_SLOWPATH_FLAG) : "memory");
+}

Came only now to mind: Here and elsewhere, did you try using %z0 to have gcc produce the opcode suffix character, rather than having these somewhat ugly if()-s?

Jan

#52 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge

arch/x86/include/asm/spinlock.h static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock) · line 81

Quoted 12 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/include/asm/spinlock.h +11 -0
+static inline void __ticket_enter_slowpath(struct arch_spinlock *lock)
+{
+	if (sizeof(lock->tickets.tail) == sizeof(u8))
+		asm (LOCK_PREFIX "orb %1, %0"
+		     : "+m" (lock->tickets.tail)
+		     : "i" (TICKET_SLOWPATH_FLAG) : "memory");
+	else
+		asm (LOCK_PREFIX "orw %1, %0"
+		     : "+m" (lock->tickets.tail)
+		     : "i" (TICKET_SLOWPATH_FLAG) : "memory");
+}

Came only now to mind: Here and elsewhere, did you try using %z0 to have gcc produce the opcode suffix character, rather than having these somewhat ugly if()-s?

Jan

#39 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jan Beulich
Quoted 15 lines · Jan Beulich

arch/x86/include/asm/spinlock.h static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock) · line 81

Quoted 12 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/include/asm/spinlock.h +11 -0
+static inline void __ticket_enter_slowpath(struct arch_spinlock *lock)
+{
+	if (sizeof(lock->tickets.tail) == sizeof(u8))
+		asm (LOCK_PREFIX "orb %1, %0"
+		     : "+m" (lock->tickets.tail)
+		     : "i" (TICKET_SLOWPATH_FLAG) : "memory");
+	else
+		asm (LOCK_PREFIX "orw %1, %0"
+		     : "+m" (lock->tickets.tail)
+		     : "i" (TICKET_SLOWPATH_FLAG) : "memory");
+}

Came only now to mind: Here and elsewhere, did you try using %z0 to have gcc produce the opcode suffix character, rather than having these somewhat ugly if()-s?

Actually in this case I'm pretty sure there's already a "set bit" function which will do the job. set_bit(), I guess, though it takes a bit number rather than a mask...

But, yes, %z0 sounds interesting. Is it documented anywhere? I think I've tried to use it in the past and run into gcc bugs.

Thanks,
J

#51 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jan Beulich
Quoted 15 lines · Jan Beulich

arch/x86/include/asm/spinlock.h static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock) · line 81

Quoted 12 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/include/asm/spinlock.h +11 -0
+static inline void __ticket_enter_slowpath(struct arch_spinlock *lock)
+{
+	if (sizeof(lock->tickets.tail) == sizeof(u8))
+		asm (LOCK_PREFIX "orb %1, %0"
+		     : "+m" (lock->tickets.tail)
+		     : "i" (TICKET_SLOWPATH_FLAG) : "memory");
+	else
+		asm (LOCK_PREFIX "orw %1, %0"
+		     : "+m" (lock->tickets.tail)
+		     : "i" (TICKET_SLOWPATH_FLAG) : "memory");
+}

Came only now to mind: Here and elsewhere, did you try using %z0 to have gcc produce the opcode suffix character, rather than having these somewhat ugly if()-s?

Actually in this case I'm pretty sure there's already a "set bit" function which will do the job. set_bit(), I guess, though it takes a bit number rather than a mask...

But, yes, %z0 sounds interesting. Is it documented anywhere? I think I've tried to use it in the past and run into gcc bugs.

Thanks,
J

#21 lore raw

Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks

In reply to Jan Beulich
Quoted 18 lines · Jan Beulich
Quoted 18 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/xen/spinlock.c +4 -4
+static void xen_lock_spinning(struct arch_spinlock *lock, unsigned want)
 {
-	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
-	struct xen_spinlock *prev;
 	int irq = __get_cpu_var(lock_kicker_irq);
-	int ret;
+	struct xen_lock_waiting *w = &__get_cpu_var(lock_waiting);
+	int cpu = smp_processor_id();
 	u64 start;
 
 	/* If kicker interrupts not initialized yet, just spin */
 	if (irq == -1)
-		return 0;
+		return;
 
 	start = spin_time_start();
Quoted 9 lines

arch/x86/xen/spinlock.c static inline u64 spin_time_start(void) · line 112

Quoted 7 lines
arch/x86/xen/spinlock.c +5 -2
-	/* announce we're spinning */
-	prev = spinning_lock(xl);
+	w->want = want;
+	w->lock = lock;
+
+	/* This uses set_bit, which atomic and therefore a barrier */
+	cpumask_set_cpu(cpu, &waiting_cpus);

Since you don't allow nesting, don't you need to disable interrupts before you touch per-CPU state?

Yes, I think you're right - interrupts need to be disabled for the bulk of this function.

J

#28 lore raw

Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks

In reply to Jan Beulich
Quoted 18 lines · Jan Beulich
Quoted 18 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/xen/spinlock.c +4 -4
+static void xen_lock_spinning(struct arch_spinlock *lock, unsigned want)
 {
-	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
-	struct xen_spinlock *prev;
 	int irq = __get_cpu_var(lock_kicker_irq);
-	int ret;
+	struct xen_lock_waiting *w = &__get_cpu_var(lock_waiting);
+	int cpu = smp_processor_id();
 	u64 start;
 
 	/* If kicker interrupts not initialized yet, just spin */
 	if (irq == -1)
-		return 0;
+		return;
 
 	start = spin_time_start();
Quoted 9 lines

arch/x86/xen/spinlock.c static inline u64 spin_time_start(void) · line 112

Quoted 7 lines
arch/x86/xen/spinlock.c +5 -2
-	/* announce we're spinning */
-	prev = spinning_lock(xl);
+	w->want = want;
+	w->lock = lock;
+
+	/* This uses set_bit, which atomic and therefore a barrier */
+	cpumask_set_cpu(cpu, &waiting_cpus);

Since you don't allow nesting, don't you need to disable interrupts before you touch per-CPU state?

Yes, I think you're right - interrupts need to be disabled for the bulk of this function.

J

#78 lore raw
In reply to Jeremy Fitzhardinge
Quoted 28 lines · Jeremy Fitzhardinge

From: Jeremy Fitzhardinge<[email protected]>

Hi all,

This is a revised version of the pvticket lock series.

The early part of the series is mostly unchanged: it converts the bulk of the ticket lock code into C and makes the "small" and "large" ticket code common. The only changes are the incorporation of various review comments.

The latter part of the series converts from pv spinlocks to pv ticket locks (ie, using the ticket lock fastpath as-is, but adding pv ops for the ticketlock slowpaths).

The significant difference here is that rather than adding a new ticket_t-sized element to arch_spinlock_t - effectively doubling the size - I steal the LSB of the tickets themselves to store a bit. This allows the structure to remain the same size, but at the cost of halving the max number of CPUs (127 for a 8-bit ticket, and a hard max of 32767 overall).

The extra bit (well, two, but one is unused) in indicates whether the lock has gone into "slowpath state", which means one of its lockers has entered its slowpath and has blocked in the hypervisor. This means the current lock-holder needs to make sure it gets kicked out of the hypervisor on unlock.

Quoted 7 lines

The spinlock remains in slowpath state until the last unlock happens (ie there are no more queued lockers).

This code survives for a while with moderate testing, (make -j 100 on 8 VCPUs on a 4 PCPU system), but locks up after about 20 iterations, so there's still some race/deadlock in there (probably something misordered), but I think the basic approach is sound.

This is going to be very useful for kvm; I'd like to see the fixed version gets merged.

Signature · 1 line
error compiling committee.c: too many arguments to function
#79 lore raw
In reply to Jeremy Fitzhardinge
Quoted 28 lines · Jeremy Fitzhardinge

From: Jeremy Fitzhardinge<[email protected]>

Hi all,

This is a revised version of the pvticket lock series.

The early part of the series is mostly unchanged: it converts the bulk of the ticket lock code into C and makes the "small" and "large" ticket code common. The only changes are the incorporation of various review comments.

The latter part of the series converts from pv spinlocks to pv ticket locks (ie, using the ticket lock fastpath as-is, but adding pv ops for the ticketlock slowpaths).

The significant difference here is that rather than adding a new ticket_t-sized element to arch_spinlock_t - effectively doubling the size - I steal the LSB of the tickets themselves to store a bit. This allows the structure to remain the same size, but at the cost of halving the max number of CPUs (127 for a 8-bit ticket, and a hard max of 32767 overall).

The extra bit (well, two, but one is unused) in indicates whether the lock has gone into "slowpath state", which means one of its lockers has entered its slowpath and has blocked in the hypervisor. This means the current lock-holder needs to make sure it gets kicked out of the hypervisor on unlock.

Quoted 7 lines

The spinlock remains in slowpath state until the last unlock happens (ie there are no more queued lockers).

This code survives for a while with moderate testing, (make -j 100 on 8 VCPUs on a 4 PCPU system), but locks up after about 20 iterations, so there's still some race/deadlock in there (probably something misordered), but I think the basic approach is sound.

This is going to be very useful for kvm; I'd like to see the fixed version gets merged.

Signature · 1 line
error compiling committee.c: too many arguments to function
#46 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge
Quoted 13 lines · Jeremy Fitzhardinge
Quoted 12 lines · Jan Beulich
Quoted 12 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge

+static inline void __ticket_enter_slowpath(struct arch_spinlock *lock) +{
+ if (sizeof(lock->tickets.tail) == sizeof(u8))
+ asm (LOCK_PREFIX "orb %1, %0"
+ : "+m" (lock->tickets.tail)
+ : "i" (TICKET_SLOWPATH_FLAG) : "memory");
+ else
+ asm (LOCK_PREFIX "orw %1, %0"
+ : "+m" (lock->tickets.tail)
+ : "i" (TICKET_SLOWPATH_FLAG) : "memory");
+}

Quoted 8 lines
Quoted 3 lines

Came only now to mind: Here and elsewhere, did you try using %z0 to have gcc produce the opcode suffix character, rather than having these somewhat ugly if()-s?

Actually in this case I'm pretty sure there's already a "set bit" function which will do the job. set_bit(), I guess, though it takes a bit number rather than a mask...

set_bit() operates on a long, while the intel manuals recommend against operating on operands of different size, especially with locked operations. I think newer processors have more relaxed requirements, though.

Signature · 1 line
error compiling committee.c: too many arguments to function
#47 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

Quoted 10 lines · Avi Kivity
Quoted 4 lines

Actually in this case I'm pretty sure there's already a "set bit" function which will do the job. set_bit(), I guess, though it takes a bit number rather than a mask...

set_bit() operates on a long, while the intel manuals recommend against operating on operands of different size, especially with locked operations. I think newer processors have more relaxed requirements, though.

Despite its prototype, set_bit() is pretty specifically using "orb" for a the constant case, or bts otherwise (I don't know what size memory operation bts is considered to generate).

J

#50 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Avi Kivity
Quoted 10 lines · Avi Kivity
Quoted 4 lines

Actually in this case I'm pretty sure there's already a "set bit" function which will do the job. set_bit(), I guess, though it takes a bit number rather than a mask...

set_bit() operates on a long, while the intel manuals recommend against operating on operands of different size, especially with locked operations. I think newer processors have more relaxed requirements, though.

Despite its prototype, set_bit() is pretty specifically using "orb" for a the constant case, or bts otherwise (I don't know what size memory operation bts is considered to generate).

J

#41 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge
Quoted 6 lines · Jeremy Fitzhardinge
Quoted 2 lines · Jeremy Fitzhardinge

But, yes, %z0 sounds interesting. Is it documented anywhere? I think I've tried to use it in the past and run into gcc bugs.

This one: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39590

Should be OK in this case because there's no 64-bit values to be seen...

Hm, it fails when __ticket_t is 16 bits:

/home/jeremy/git/linux/arch/x86/include/asm/spinlock.h: Assembler messages:
/home/jeremy/git/linux/arch/x86/include/asm/spinlock.h:73: Error: suffix or operands invalid for `or'

        lock; ors $1, 2(%rbx)   #,

So I don't think that's going to work out...

J

#44 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge
Quoted 6 lines · Jeremy Fitzhardinge
Quoted 2 lines · Jeremy Fitzhardinge

But, yes, %z0 sounds interesting. Is it documented anywhere? I think I've tried to use it in the past and run into gcc bugs.

This one: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39590

Should be OK in this case because there's no 64-bit values to be seen...

Hm, it fails when __ticket_t is 16 bits:

/home/jeremy/git/linux/arch/x86/include/asm/spinlock.h: Assembler messages:
/home/jeremy/git/linux/arch/x86/include/asm/spinlock.h:73: Error: suffix or operands invalid for `or'

        lock; ors $1, 2(%rbx)   #,

So I don't think that's going to work out...

J

#48 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge
Quoted 7 lines · Jeremy Fitzhardinge
Quoted 6 lines · Avi Kivity
Quoted 4 lines

Actually in this case I'm pretty sure there's already a "set bit" function which will do the job. set_bit(), I guess, though it takes a bit number rather than a mask...

Quoted 9 lines
Quoted 4 lines

set_bit() operates on a long, while the intel manuals recommend against operating on operands of different size, especially with locked operations. I think newer processors have more relaxed requirements, though.

Despite its prototype, set_bit() is pretty specifically using "orb" for a the constant case, or bts otherwise (I don't know what size memory operation bts is considered to generate).

Perhaps that should be fixed.

bts will take its size from the argument, so it will be a btsq on x86_64. AFAICT, the only visible difference between btsl and btsq is a page fault if the last four bytes of the operand are in an unmapped page.

Signature · 1 line
error compiling committee.c: too many arguments to function
#49 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge
Quoted 7 lines · Jeremy Fitzhardinge
Quoted 6 lines · Avi Kivity
Quoted 4 lines

Actually in this case I'm pretty sure there's already a "set bit" function which will do the job. set_bit(), I guess, though it takes a bit number rather than a mask...

Quoted 9 lines
Quoted 4 lines

set_bit() operates on a long, while the intel manuals recommend against operating on operands of different size, especially with locked operations. I think newer processors have more relaxed requirements, though.

Despite its prototype, set_bit() is pretty specifically using "orb" for a the constant case, or bts otherwise (I don't know what size memory operation bts is considered to generate).

Perhaps that should be fixed.

bts will take its size from the argument, so it will be a btsq on x86_64. AFAICT, the only visible difference between btsl and btsq is a page fault if the last four bytes of the operand are in an unmapped page.

Signature · 1 line
error compiling committee.c: too many arguments to function
#42 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge
Quoted 10 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
Quoted 6 lines · Jeremy Fitzhardinge
Quoted 2 lines · Jeremy Fitzhardinge

But, yes, %z0 sounds interesting. Is it documented anywhere? I think I've tried to use it in the past and run into gcc bugs.

This one: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39590

Should be OK in this case because there's no 64-bit values to be seen...

Hm, it fails when __ticket_t is 16 bits:

Quoted 8 lines

/home/jeremy/git/linux/arch/x86/include/asm/spinlock.h: Assembler messages:
/home/jeremy/git/linux/arch/x86/include/asm/spinlock.h:73: Error: suffix or operands invalid for `or'

        lock; ors $1, 2(%rbx)   #,

So I don't think that's going to work out...

Indeed, it's only with 4.5 that non-float operands are properly supported here. Sad.

Jan

#43 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge
Quoted 10 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
Quoted 6 lines · Jeremy Fitzhardinge
Quoted 2 lines · Jeremy Fitzhardinge

But, yes, %z0 sounds interesting. Is it documented anywhere? I think I've tried to use it in the past and run into gcc bugs.

This one: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39590

Should be OK in this case because there's no 64-bit values to be seen...

Hm, it fails when __ticket_t is 16 bits:

Quoted 8 lines

/home/jeremy/git/linux/arch/x86/include/asm/spinlock.h: Assembler messages:
/home/jeremy/git/linux/arch/x86/include/asm/spinlock.h:73: Error: suffix or operands invalid for `or'

        lock; ors $1, 2(%rbx)   #,

So I don't think that's going to work out...

Indeed, it's only with 4.5 that non-float operands are properly supported here. Sad.

Jan

#22 lore raw

Re: [Xen-devel] Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks

In reply to Jeremy Fitzhardinge
Quoted 28 lines · Jeremy Fitzhardinge
Quoted 18 lines · Jan Beulich
Quoted 18 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/xen/spinlock.c +4 -4
+static void xen_lock_spinning(struct arch_spinlock *lock, unsigned want)
 {
-	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
-	struct xen_spinlock *prev;
 	int irq = __get_cpu_var(lock_kicker_irq);
-	int ret;
+	struct xen_lock_waiting *w = &__get_cpu_var(lock_waiting);
+	int cpu = smp_processor_id();
 	u64 start;
 
 	/* If kicker interrupts not initialized yet, just spin */
 	if (irq == -1)
-		return 0;
+		return;
 
 	start = spin_time_start();
Quoted 9 lines

arch/x86/xen/spinlock.c static inline u64 spin_time_start(void) · line 112

Quoted 7 lines
arch/x86/xen/spinlock.c +5 -2
-	/* announce we're spinning */
-	prev = spinning_lock(xl);
+	w->want = want;
+	w->lock = lock;
+
+	/* This uses set_bit, which atomic and therefore a barrier */
+	cpumask_set_cpu(cpu, &waiting_cpus);

Since you don't allow nesting, don't you need to disable interrupts before you touch per-CPU state?

Quoted 2 lines

Yes, I think you're right - interrupts need to be disabled for the bulk of this function.

Actually, on second thoughts, maybe it doesn't matter so much. The main issue is making sure that the interrupt will make the VCPU drop out of xen_poll_irq() - if it happens before xen_poll_irq(), it should leave the event pending, which will cause the poll to return immediately. I hope. Certainly disabling interrupts for some of the function will make it easier to analyze with respect to interrupt nesting.

Another issue may be making sure the writes and reads of "w->want" and "w->lock" are ordered properly to make sure that xen_unlock_kick() never sees an inconsistent view of the (lock,want) tuple. The risk being that xen_unlock_kick() sees a random, spurious (lock,want) pairing and sends the kick event to the wrong VCPU, leaving the deserving one hung.

J

#27 lore raw

Re: [Xen-devel] Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks

In reply to Jeremy Fitzhardinge
Quoted 28 lines · Jeremy Fitzhardinge
Quoted 18 lines · Jan Beulich
Quoted 18 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/xen/spinlock.c +4 -4
+static void xen_lock_spinning(struct arch_spinlock *lock, unsigned want)
 {
-	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
-	struct xen_spinlock *prev;
 	int irq = __get_cpu_var(lock_kicker_irq);
-	int ret;
+	struct xen_lock_waiting *w = &__get_cpu_var(lock_waiting);
+	int cpu = smp_processor_id();
 	u64 start;
 
 	/* If kicker interrupts not initialized yet, just spin */
 	if (irq == -1)
-		return 0;
+		return;
 
 	start = spin_time_start();
Quoted 9 lines

arch/x86/xen/spinlock.c static inline u64 spin_time_start(void) · line 112

Quoted 7 lines
arch/x86/xen/spinlock.c +5 -2
-	/* announce we're spinning */
-	prev = spinning_lock(xl);
+	w->want = want;
+	w->lock = lock;
+
+	/* This uses set_bit, which atomic and therefore a barrier */
+	cpumask_set_cpu(cpu, &waiting_cpus);

Since you don't allow nesting, don't you need to disable interrupts before you touch per-CPU state?

Quoted 2 lines

Yes, I think you're right - interrupts need to be disabled for the bulk of this function.

Actually, on second thoughts, maybe it doesn't matter so much. The main issue is making sure that the interrupt will make the VCPU drop out of xen_poll_irq() - if it happens before xen_poll_irq(), it should leave the event pending, which will cause the poll to return immediately. I hope. Certainly disabling interrupts for some of the function will make it easier to analyze with respect to interrupt nesting.

Another issue may be making sure the writes and reads of "w->want" and "w->lock" are ordered properly to make sure that xen_unlock_kick() never sees an inconsistent view of the (lock,want) tuple. The risk being that xen_unlock_kick() sees a random, spurious (lock,want) pairing and sends the kick event to the wrong VCPU, leaving the deserving one hung.

J

#23 lore raw

Re: [Xen-devel] Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks

In reply to Jeremy Fitzhardinge
Quoted 33 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
Quoted 28 lines · Jeremy Fitzhardinge
Quoted 18 lines · Jan Beulich
Quoted 18 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/xen/spinlock.c +4 -4
+static void xen_lock_spinning(struct arch_spinlock *lock, unsigned want)
 {
-	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
-	struct xen_spinlock *prev;
 	int irq = __get_cpu_var(lock_kicker_irq);
-	int ret;
+	struct xen_lock_waiting *w = &__get_cpu_var(lock_waiting);
+	int cpu = smp_processor_id();
 	u64 start;
 
 	/* If kicker interrupts not initialized yet, just spin */
 	if (irq == -1)
-		return 0;
+		return;
 
 	start = spin_time_start();
Quoted 9 lines

arch/x86/xen/spinlock.c static inline u64 spin_time_start(void) · line 112

Quoted 7 lines
arch/x86/xen/spinlock.c +5 -2
-	/* announce we're spinning */
-	prev = spinning_lock(xl);
+	w->want = want;
+	w->lock = lock;
+
+	/* This uses set_bit, which atomic and therefore a barrier */
+	cpumask_set_cpu(cpu, &waiting_cpus);

Since you don't allow nesting, don't you need to disable interrupts before you touch per-CPU state?

Quoted 2 lines

Yes, I think you're right - interrupts need to be disabled for the bulk of this function.

Quoted 6 lines

Actually, on second thoughts, maybe it doesn't matter so much. The main issue is making sure that the interrupt will make the VCPU drop out of xen_poll_irq() - if it happens before xen_poll_irq(), it should leave the event pending, which will cause the poll to return immediately. I hope. Certainly disabling interrupts for some of the function will make it easier to analyze with respect to interrupt nesting.

That's not my main concern. Instead, what if you get interrupted anywhere here, the interrupt handler tries to acquire another spinlock and also has to go into the slow path? It'll overwrite part or all of the outer context's state.

Quoted 5 lines

Another issue may be making sure the writes and reads of "w->want" and "w->lock" are ordered properly to make sure that xen_unlock_kick() never sees an inconsistent view of the (lock,want) tuple. The risk being that xen_unlock_kick() sees a random, spurious (lock,want) pairing and sends the kick event to the wrong VCPU, leaving the deserving one hung.

Yes, proper operation sequence (and barriers) is certainly required here. If you allowed nesting, this may even become simpler (as you'd have a single write making visible the new "head" pointer, after having written all relevant fields of the new "head" structure).

Jan

#26 lore raw

Re: [Xen-devel] Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks

In reply to Jeremy Fitzhardinge
Quoted 33 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
Quoted 28 lines · Jeremy Fitzhardinge
Quoted 18 lines · Jan Beulich
Quoted 18 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
arch/x86/xen/spinlock.c +4 -4
+static void xen_lock_spinning(struct arch_spinlock *lock, unsigned want)
 {
-	struct xen_spinlock *xl = (struct xen_spinlock *)lock;
-	struct xen_spinlock *prev;
 	int irq = __get_cpu_var(lock_kicker_irq);
-	int ret;
+	struct xen_lock_waiting *w = &__get_cpu_var(lock_waiting);
+	int cpu = smp_processor_id();
 	u64 start;
 
 	/* If kicker interrupts not initialized yet, just spin */
 	if (irq == -1)
-		return 0;
+		return;
 
 	start = spin_time_start();
Quoted 9 lines

arch/x86/xen/spinlock.c static inline u64 spin_time_start(void) · line 112

Quoted 7 lines
arch/x86/xen/spinlock.c +5 -2
-	/* announce we're spinning */
-	prev = spinning_lock(xl);
+	w->want = want;
+	w->lock = lock;
+
+	/* This uses set_bit, which atomic and therefore a barrier */
+	cpumask_set_cpu(cpu, &waiting_cpus);

Since you don't allow nesting, don't you need to disable interrupts before you touch per-CPU state?

Quoted 2 lines

Yes, I think you're right - interrupts need to be disabled for the bulk of this function.

Quoted 6 lines

Actually, on second thoughts, maybe it doesn't matter so much. The main issue is making sure that the interrupt will make the VCPU drop out of xen_poll_irq() - if it happens before xen_poll_irq(), it should leave the event pending, which will cause the poll to return immediately. I hope. Certainly disabling interrupts for some of the function will make it easier to analyze with respect to interrupt nesting.

That's not my main concern. Instead, what if you get interrupted anywhere here, the interrupt handler tries to acquire another spinlock and also has to go into the slow path? It'll overwrite part or all of the outer context's state.

Quoted 5 lines

Another issue may be making sure the writes and reads of "w->want" and "w->lock" are ordered properly to make sure that xen_unlock_kick() never sees an inconsistent view of the (lock,want) tuple. The risk being that xen_unlock_kick() sees a random, spurious (lock,want) pairing and sends the kick event to the wrong VCPU, leaving the deserving one hung.

Yes, proper operation sequence (and barriers) is certainly required here. If you allowed nesting, this may even become simpler (as you'd have a single write making visible the new "head" pointer, after having written all relevant fields of the new "head" structure).

Jan

maintainer
#53 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge
Quoted 4 lines · Jeremy Fitzhardinge

Maintain a flag in both LSBs of the ticket lock which indicates whether anyone is in the lock slowpath and may need kicking when the current holder unlocks. The flags are set when the first locker enters the slowpath, and cleared when unlocking to an empty queue.

So here you say you set both LSBs in order to keep head == tail working, but the code seems to suggest you only use the tail LSB.

I think I see why using only one LSB is sufficient, but some consistency would be nice :-)

maintainer
#56 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge
Quoted 4 lines · Jeremy Fitzhardinge

Maintain a flag in both LSBs of the ticket lock which indicates whether anyone is in the lock slowpath and may need kicking when the current holder unlocks. The flags are set when the first locker enters the slowpath, and cleared when unlocking to an empty queue.

So here you say you set both LSBs in order to keep head == tail working, but the code seems to suggest you only use the tail LSB.

I think I see why using only one LSB is sufficient, but some consistency would be nice :-)

#54 lore raw

Re: [Xen-devel] Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Peter Zijlstra
Quoted 10 lines · Peter Zijlstra
Quoted 4 lines · Jeremy Fitzhardinge

Maintain a flag in both LSBs of the ticket lock which indicates whether anyone is in the lock slowpath and may need kicking when the current holder unlocks. The flags are set when the first locker enters the slowpath, and cleared when unlocking to an empty queue.

So here you say you set both LSBs in order to keep head == tail working, but the code seems to suggest you only use the tail LSB.

I think I see why using only one LSB is sufficient, but some consistency would be nice :-)

I tried that initially, but it turned out more messy. The problem is that the flag can change while you're spinning on the lock, so you need to mask it out every time you read tail before you can compare it to head; if head has the flag set too, you just need to mask it out of there as well:

	ticket = xadd(lock, 2 << TICKET_SHIFT);
	ticket.tail &= ~TICKET_SLOW_FLAGS;

	while (ticket.head != ticket.tail) {
		relax();
		ticket.head = lock->head /* & ~TICKET_SLOW_FLAGS */;
	}

IOW setting both doesn't help anything, and just requires an extra mask in the spin loop (and anywhere else that uses 'head').

And hey, extra bit. Bound to be useful for something.

J

#55 lore raw

Re: [Xen-devel] Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Peter Zijlstra
Quoted 10 lines · Peter Zijlstra
Quoted 4 lines · Jeremy Fitzhardinge

Maintain a flag in both LSBs of the ticket lock which indicates whether anyone is in the lock slowpath and may need kicking when the current holder unlocks. The flags are set when the first locker enters the slowpath, and cleared when unlocking to an empty queue.

So here you say you set both LSBs in order to keep head == tail working, but the code seems to suggest you only use the tail LSB.

I think I see why using only one LSB is sufficient, but some consistency would be nice :-)

I tried that initially, but it turned out more messy. The problem is that the flag can change while you're spinning on the lock, so you need to mask it out every time you read tail before you can compare it to head; if head has the flag set too, you just need to mask it out of there as well:

	ticket = xadd(lock, 2 << TICKET_SHIFT);
	ticket.tail &= ~TICKET_SLOW_FLAGS;

	while (ticket.head != ticket.tail) {
		relax();
		ticket.head = lock->head /* & ~TICKET_SLOW_FLAGS */;
	}

IOW setting both doesn't help anything, and just requires an extra mask in the spin loop (and anywhere else that uses 'head').

And hey, extra bit. Bound to be useful for something.

J

#24 lore raw

Re: [Xen-devel] Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks

In reply to Jan Beulich
Quoted 10 lines · Jan Beulich
Quoted 6 lines

Actually, on second thoughts, maybe it doesn't matter so much. The main issue is making sure that the interrupt will make the VCPU drop out of xen_poll_irq() - if it happens before xen_poll_irq(), it should leave the event pending, which will cause the poll to return immediately. I hope. Certainly disabling interrupts for some of the function will make it easier to analyze with respect to interrupt nesting.

That's not my main concern. Instead, what if you get interrupted anywhere here, the interrupt handler tries to acquire another spinlock and also has to go into the slow path? It'll overwrite part or all of the outer context's state.

That doesn't matter if the outer context doesn't end up blocking. If it has already blocked then it will unblock as a result of the interrupt; if it hasn't yet blocked, then the inner context will leave the event pending and cause it to not block. Either way, it no longer uses or needs that per-cpu state: it will return to the spin loop and (maybe) get re-entered, setting it all up again.

I think there is a problem with the code as posted because it sets up the percpu data before clearing the pending event, so it can end up blocking with bad percpu data.

Quoted 10 lines
Quoted 5 lines

Another issue may be making sure the writes and reads of "w->want" and "w->lock" are ordered properly to make sure that xen_unlock_kick() never sees an inconsistent view of the (lock,want) tuple. The risk being that xen_unlock_kick() sees a random, spurious (lock,want) pairing and sends the kick event to the wrong VCPU, leaving the deserving one hung.

Yes, proper operation sequence (and barriers) is certainly required here. If you allowed nesting, this may even become simpler (as you'd have a single write making visible the new "head" pointer, after having written all relevant fields of the new "head" structure).

Yes, simple nesting should be quite straightforward (ie allowing an interrupt handler to take some other lock than the one the outer context is waiting on).

J

#25 lore raw

Re: [Xen-devel] Re: [PATCH 09/14] xen/pvticketlock: Xen implementation for PV ticket locks

In reply to Jan Beulich
Quoted 10 lines · Jan Beulich
Quoted 6 lines

Actually, on second thoughts, maybe it doesn't matter so much. The main issue is making sure that the interrupt will make the VCPU drop out of xen_poll_irq() - if it happens before xen_poll_irq(), it should leave the event pending, which will cause the poll to return immediately. I hope. Certainly disabling interrupts for some of the function will make it easier to analyze with respect to interrupt nesting.

That's not my main concern. Instead, what if you get interrupted anywhere here, the interrupt handler tries to acquire another spinlock and also has to go into the slow path? It'll overwrite part or all of the outer context's state.

That doesn't matter if the outer context doesn't end up blocking. If it has already blocked then it will unblock as a result of the interrupt; if it hasn't yet blocked, then the inner context will leave the event pending and cause it to not block. Either way, it no longer uses or needs that per-cpu state: it will return to the spin loop and (maybe) get re-entered, setting it all up again.

I think there is a problem with the code as posted because it sets up the percpu data before clearing the pending event, so it can end up blocking with bad percpu data.

Quoted 10 lines
Quoted 5 lines

Another issue may be making sure the writes and reads of "w->want" and "w->lock" are ordered properly to make sure that xen_unlock_kick() never sees an inconsistent view of the (lock,want) tuple. The risk being that xen_unlock_kick() sees a random, spurious (lock,want) pairing and sends the kick event to the wrong VCPU, leaving the deserving one hung.

Yes, proper operation sequence (and barriers) is certainly required here. If you allowed nesting, this may even become simpler (as you'd have a single write making visible the new "head" pointer, after having written all relevant fields of the new "head" structure).

Yes, simple nesting should be quite straightforward (ie allowing an interrupt handler to take some other lock than the one the outer context is waiting on).

J

#2 lore raw

Re: [Xen-devel] [PATCH 01/14] x86/ticketlock: clean up types and accessors

In reply to Jeremy Fitzhardinge

arch/x86/include/asm/spinlock.h static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock) · line 161

Quoted 7 lines

static inline int __ticket_spin_is_locked(arch_spinlock_t *lock) {

arch/x86/include/asm/spinlock.h +2 -2
-	int tmp = ACCESS_ONCE(lock->slock);
+	struct __raw_tickets tmp = ACCESS_ONCE(lock->tickets);
 
-	return !!(((tmp >> TICKET_SHIFT) ^ tmp) & ((1 << TICKET_SHIFT) - 1));
+	return !!(tmp.tail ^ tmp.head);

Does it make sense to mask it here it here with TICKET_MASK as it was done before?

#3 lore raw

Re: [Xen-devel] [PATCH 01/14] x86/ticketlock: clean up types and accessors

In reply to Jeremy Fitzhardinge

arch/x86/include/asm/spinlock.h static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock) · line 161

Quoted 7 lines

static inline int __ticket_spin_is_locked(arch_spinlock_t *lock) {

arch/x86/include/asm/spinlock.h +2 -2
-	int tmp = ACCESS_ONCE(lock->slock);
+	struct __raw_tickets tmp = ACCESS_ONCE(lock->tickets);
 
-	return !!(((tmp >> TICKET_SHIFT) ^ tmp) & ((1 << TICKET_SHIFT) - 1));
+	return !!(tmp.tail ^ tmp.head);

Does it make sense to mask it here it here with TICKET_MASK as it was done before?

#57 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge
Quoted 22 lines · Jeremy Fitzhardinge

From: Jeremy Fitzhardinge <[email protected]>

Maintain a flag in both LSBs of the ticket lock which indicates whether anyone is in the lock slowpath and may need kicking when the current holder unlocks. The flags are set when the first locker enters the slowpath, and cleared when unlocking to an empty queue.

In the specific implementation of lock_spinning(), make sure to set the slowpath flags on the lock just before blocking. We must do this before the last-chance pickup test to prevent a deadlock with the unlocker:

Unlocker Locker

				test for lock pickup
					-> fail
test slowpath + unlock
	-> false
				set slowpath flags
				block

Whereas this works in any ordering:

Quoted 7 lines

Unlocker Locker
set slowpath flags test for lock pickup
-> fail
block
test slowpath + unlock

	-> true, kick

I think this is still racy ..

Unlocker Locker

test slowpath

	-> false
		
				set slowpath flag
				test for lock pickup
					-> fail
				block

unlock

unlock needs to happen first before testing slowpath? I have made that change for my KVM guest and it seems to be working well with that change .. Will cleanup and post my patches shortly

- vatsa

#74 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge
Quoted 22 lines · Jeremy Fitzhardinge

From: Jeremy Fitzhardinge <[email protected]>

Maintain a flag in both LSBs of the ticket lock which indicates whether anyone is in the lock slowpath and may need kicking when the current holder unlocks. The flags are set when the first locker enters the slowpath, and cleared when unlocking to an empty queue.

In the specific implementation of lock_spinning(), make sure to set the slowpath flags on the lock just before blocking. We must do this before the last-chance pickup test to prevent a deadlock with the unlocker:

Unlocker Locker

				test for lock pickup
					-> fail
test slowpath + unlock
	-> false
				set slowpath flags
				block

Whereas this works in any ordering:

Quoted 7 lines

Unlocker Locker
set slowpath flags test for lock pickup
-> fail
block
test slowpath + unlock

	-> true, kick

I think this is still racy ..

Unlocker Locker

test slowpath

	-> false
		
				set slowpath flag
				test for lock pickup
					-> fail
				block

unlock

unlock needs to happen first before testing slowpath? I have made that change for my KVM guest and it seems to be working well with that change .. Will cleanup and post my patches shortly

- vatsa

#58 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Srivatsa Vaddagiri
Quoted 14 lines · Srivatsa Vaddagiri

I think this is still racy ..

Unlocker Locker

test slowpath

	-> false
		
				set slowpath flag
				test for lock pickup
					-> fail
				block
Quoted 5 lines

unlock

unlock needs to happen first before testing slowpath? I have made that change for my KVM guest and it seems to be working well with that change .. Will cleanup and post my patches shortly

Patch below fixes the race described above. You can fold this to your patch 13/14 if you agree this is in right direction.

---
 arch/x86/include/asm/spinlock.h      |    7 +++----
 arch/x86/kernel/paravirt-spinlocks.c |   22 +++++-----------------
 2 files changed, 8 insertions(+), 21 deletions(-)
arch/x86/include/asm/spinlock.h +3 -4
Index: linux-2.6.37/arch/x86/include/asm/spinlock.h
===================================================================
@@ -55,7 +55,7 @@ static __always_inline void __ticket_unl
 
 /* Only defined when CONFIG_PARAVIRT_SPINLOCKS defined, but may as
  * well leave the prototype always visible.  */
-extern void __ticket_unlock_release_slowpath(struct arch_spinlock *lock);
+extern void __ticket_unlock_slowpath(struct arch_spinlock *lock);
 
 #ifdef CONFIG_PARAVIRT_SPINLOCKS
 
@@ -166,10 +166,9 @@ static __always_inline int arch_spin_try
 static __always_inline void arch_spin_unlock(arch_spinlock_t *lock)
 {
 	barrier();		/* prevent reordering out of locked region */
+	__ticket_unlock_release(lock);
 	if (unlikely(__ticket_in_slowpath(lock)))
-		__ticket_unlock_release_slowpath(lock);
-	else
-		__ticket_unlock_release(lock);
+		__ticket_unlock_slowpath(lock);
 	barrier();		/* prevent reordering into locked region */
 }
 
arch/x86/kernel/paravirt-spinlocks.c +5 -17
Index: linux-2.6.37/arch/x86/kernel/paravirt-spinlocks.c
===================================================================
@@ -22,33 +22,21 @@ EXPORT_SYMBOL(pv_lock_ops);
  * bits.  However, we need to be careful about this because someone
  * may just be entering as we leave, and enter the slowpath.
  */
-void __ticket_unlock_release_slowpath(struct arch_spinlock *lock)
+void __ticket_unlock_slowpath(struct arch_spinlock *lock)
 {
 	struct arch_spinlock old, new;
 
 	BUILD_BUG_ON(((__ticket_t)NR_CPUS) != NR_CPUS);
 
 	old = ACCESS_ONCE(*lock);
-
 	new = old;
-	new.tickets.head += TICKET_LOCK_INC;
 
 	/* Clear the slowpath flag */
 	new.tickets.tail &= ~TICKET_SLOWPATH_FLAG;
+	if (new.tickets.head == new.tickets.tail)
+		cmpxchg(&lock->head_tail, old.head_tail, new.head_tail);
 
-	/*
-	 * If there's currently people waiting or someone snuck in
-	 * since we read the lock above, then do a normal unlock and
-	 * kick.  If we managed to unlock with no queued waiters, then
-	 * we can clear the slowpath flag.
-	 */
-	if (new.tickets.head != new.tickets.tail ||
-	    cmpxchg(&lock->head_tail,
-		    old.head_tail, new.head_tail) != old.head_tail) {
-		/* still people waiting */
-		__ticket_unlock_release(lock);
-	}
-
+	/* Wake up an appropriate waiter */
 	__ticket_unlock_kick(lock, new.tickets.head);
 }
-EXPORT_SYMBOL(__ticket_unlock_release_slowpath);
+EXPORT_SYMBOL(__ticket_unlock_slowpath);
#63 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Srivatsa Vaddagiri
Quoted 14 lines · Srivatsa Vaddagiri

I think this is still racy ..

Unlocker Locker

test slowpath

	-> false
		
				set slowpath flag
				test for lock pickup
					-> fail
				block
Quoted 5 lines

unlock

unlock needs to happen first before testing slowpath? I have made that change for my KVM guest and it seems to be working well with that change .. Will cleanup and post my patches shortly

Patch below fixes the race described above. You can fold this to your patch 13/14 if you agree this is in right direction.

---
 arch/x86/include/asm/spinlock.h      |    7 +++----
 arch/x86/kernel/paravirt-spinlocks.c |   22 +++++-----------------
 2 files changed, 8 insertions(+), 21 deletions(-)
arch/x86/include/asm/spinlock.h +3 -4
Index: linux-2.6.37/arch/x86/include/asm/spinlock.h
===================================================================
@@ -55,7 +55,7 @@ static __always_inline void __ticket_unl
 
 /* Only defined when CONFIG_PARAVIRT_SPINLOCKS defined, but may as
  * well leave the prototype always visible.  */
-extern void __ticket_unlock_release_slowpath(struct arch_spinlock *lock);
+extern void __ticket_unlock_slowpath(struct arch_spinlock *lock);
 
 #ifdef CONFIG_PARAVIRT_SPINLOCKS
 
@@ -166,10 +166,9 @@ static __always_inline int arch_spin_try
 static __always_inline void arch_spin_unlock(arch_spinlock_t *lock)
 {
 	barrier();		/* prevent reordering out of locked region */
+	__ticket_unlock_release(lock);
 	if (unlikely(__ticket_in_slowpath(lock)))
-		__ticket_unlock_release_slowpath(lock);
-	else
-		__ticket_unlock_release(lock);
+		__ticket_unlock_slowpath(lock);
 	barrier();		/* prevent reordering into locked region */
 }
 
arch/x86/kernel/paravirt-spinlocks.c +5 -17
Index: linux-2.6.37/arch/x86/kernel/paravirt-spinlocks.c
===================================================================
@@ -22,33 +22,21 @@ EXPORT_SYMBOL(pv_lock_ops);
  * bits.  However, we need to be careful about this because someone
  * may just be entering as we leave, and enter the slowpath.
  */
-void __ticket_unlock_release_slowpath(struct arch_spinlock *lock)
+void __ticket_unlock_slowpath(struct arch_spinlock *lock)
 {
 	struct arch_spinlock old, new;
 
 	BUILD_BUG_ON(((__ticket_t)NR_CPUS) != NR_CPUS);
 
 	old = ACCESS_ONCE(*lock);
-
 	new = old;
-	new.tickets.head += TICKET_LOCK_INC;
 
 	/* Clear the slowpath flag */
 	new.tickets.tail &= ~TICKET_SLOWPATH_FLAG;
+	if (new.tickets.head == new.tickets.tail)
+		cmpxchg(&lock->head_tail, old.head_tail, new.head_tail);
 
-	/*
-	 * If there's currently people waiting or someone snuck in
-	 * since we read the lock above, then do a normal unlock and
-	 * kick.  If we managed to unlock with no queued waiters, then
-	 * we can clear the slowpath flag.
-	 */
-	if (new.tickets.head != new.tickets.tail ||
-	    cmpxchg(&lock->head_tail,
-		    old.head_tail, new.head_tail) != old.head_tail) {
-		/* still people waiting */
-		__ticket_unlock_release(lock);
-	}
-
+	/* Wake up an appropriate waiter */
 	__ticket_unlock_kick(lock, new.tickets.head);
 }
-EXPORT_SYMBOL(__ticket_unlock_release_slowpath);
+EXPORT_SYMBOL(__ticket_unlock_slowpath);
#80 lore raw
In reply to Jeremy Fitzhardinge
Quoted 5 lines · Jeremy Fitzhardinge

From: Jeremy Fitzhardinge <[email protected]>

Hi all,

This is a revised version of the pvticket lock series.

The 3-patch series to follow this email extends KVM-hypervisor and Linux guest running on KVM-hypervisor to support pv-ticket spinlocks.

Two hypercalls are being introduced in KVM hypervisor, one that allows a vcpu (spinning on a lock) to block and another that allows a vcpu to kick another out of blocking state.

Patches are against 2.6.37 mainline kernel. I also don't yet have numbers at this time to show benefit of pv-ticketlocks - I would think the benefit should be similar across hypervisors (Xen and KVM in this case).

- vatsa

#119 lore raw
In reply to Jeremy Fitzhardinge
Quoted 5 lines · Jeremy Fitzhardinge

From: Jeremy Fitzhardinge <[email protected]>

Hi all,

This is a revised version of the pvticket lock series.

The 3-patch series to follow this email extends KVM-hypervisor and Linux guest running on KVM-hypervisor to support pv-ticket spinlocks.

Two hypercalls are being introduced in KVM hypervisor, one that allows a vcpu (spinning on a lock) to block and another that allows a vcpu to kick another out of blocking state.

Patches are against 2.6.37 mainline kernel. I also don't yet have numbers at this time to show benefit of pv-ticketlocks - I would think the benefit should be similar across hypervisors (Xen and KVM in this case).

- vatsa

#81 lore raw

PATCH 1/3 debugfs: Add support to print u32 array

In reply to Srivatsa Vaddagiri

Add debugfs support to print u32-arrays.

Most of this comes from Xen-hypervisor sources, which has been refactored to make the code common for other users as well.

---
 arch/x86/xen/debugfs.c    |  104 --------------------------------------------
 arch/x86/xen/debugfs.h    |    4 -
 arch/x86/xen/mmu.c        |    2 
 arch/x86/xen/multicalls.c |    6 +-
 arch/x86/xen/spinlock.c   |    2 
 fs/debugfs/file.c         |  108 ++++++++++++++++++++++++++++++++++++++++++++++
 include/linux/debugfs.h   |   11 ++++
 7 files changed, 124 insertions(+), 113 deletions(-)
arch/x86/xen/debugfs.c +0 -104
Index: linux-2.6.37/arch/x86/xen/debugfs.c
===================================================================
@@ -19,107 +19,3 @@ struct dentry * __init xen_init_debugfs(
 	return d_xen_debug;
 }
 
-struct array_data
-{
-	void *array;
-	unsigned elements;
-};
-
-static int u32_array_open(struct inode *inode, struct file *file)
-{
-	file->private_data = NULL;
-	return nonseekable_open(inode, file);
-}
-
-static size_t format_array(char *buf, size_t bufsize, const char *fmt,
-			   u32 *array, unsigned array_size)
-{
-	size_t ret = 0;
-	unsigned i;
-
-	for(i = 0; i < array_size; i++) {
-		size_t len;
-
-		len = snprintf(buf, bufsize, fmt, array[i]);
-		len++;	/* ' ' or '\n' */
-		ret += len;
-
-		if (buf) {
-			buf += len;
-			bufsize -= len;
-			buf[-1] = (i == array_size-1) ? '\n' : ' ';
-		}
-	}
-
-	ret++;		/* \0 */
-	if (buf)
-		*buf = '\0';
-
-	return ret;
-}
-
-static char *format_array_alloc(const char *fmt, u32 *array, unsigned array_size)
-{
-	size_t len = format_array(NULL, 0, fmt, array, array_size);
-	char *ret;
-
-	ret = kmalloc(len, GFP_KERNEL);
-	if (ret == NULL)
-		return NULL;
-
-	format_array(ret, len, fmt, array, array_size);
-	return ret;
-}
-
-static ssize_t u32_array_read(struct file *file, char __user *buf, size_t len,
-			      loff_t *ppos)
-{
-	struct inode *inode = file->f_path.dentry->d_inode;
-	struct array_data *data = inode->i_private;
-	size_t size;
-
-	if (*ppos == 0) {
-		if (file->private_data) {
-			kfree(file->private_data);
-			file->private_data = NULL;
-		}
-
-		file->private_data = format_array_alloc("%u", data->array, data->elements);
-	}
-
-	size = 0;
-	if (file->private_data)
-		size = strlen(file->private_data);
-
-	return simple_read_from_buffer(buf, len, ppos, file->private_data, size);
-}
-
-static int xen_array_release(struct inode *inode, struct file *file)
-{
-	kfree(file->private_data);
-
-	return 0;
-}
-
-static const struct file_operations u32_array_fops = {
-	.owner	= THIS_MODULE,
-	.open	= u32_array_open,
-	.release= xen_array_release,
-	.read	= u32_array_read,
-	.llseek = no_llseek,
-};
-
-struct dentry *xen_debugfs_create_u32_array(const char *name, mode_t mode,
-					    struct dentry *parent,
-					    u32 *array, unsigned elements)
-{
-	struct array_data *data = kmalloc(sizeof(*data), GFP_KERNEL);
-
-	if (data == NULL)
-		return NULL;
-
-	data->array = array;
-	data->elements = elements;
-
-	return debugfs_create_file(name, mode, parent, data, &u32_array_fops);
-}
arch/x86/xen/debugfs.h +0 -4
Index: linux-2.6.37/arch/x86/xen/debugfs.h
===================================================================
@@ -3,8 +3,4 @@
 
 struct dentry * __init xen_init_debugfs(void);
 
-struct dentry *xen_debugfs_create_u32_array(const char *name, mode_t mode,
-					    struct dentry *parent,
-					    u32 *array, unsigned elements);
-
 #endif /* _XEN_DEBUGFS_H */
arch/x86/xen/mmu.c +1 -1
Index: linux-2.6.37/arch/x86/xen/mmu.c
===================================================================
@@ -2757,7 +2757,7 @@ static int __init xen_mmu_debugfs(void)
 	debugfs_create_u32("mmu_update", 0444, d_mmu_debug, &mmu_stats.mmu_update);
 	debugfs_create_u32("mmu_update_extended", 0444, d_mmu_debug,
 			   &mmu_stats.mmu_update_extended);
-	xen_debugfs_create_u32_array("mmu_update_histo", 0444, d_mmu_debug,
+	debugfs_create_u32_array("mmu_update_histo", 0444, d_mmu_debug,
 				     mmu_stats.mmu_update_histo, 20);
 
 	debugfs_create_u32("set_pte_at", 0444, d_mmu_debug, &mmu_stats.set_pte_at);
arch/x86/xen/multicalls.c +3 -3
Index: linux-2.6.37/arch/x86/xen/multicalls.c
===================================================================
@@ -269,11 +269,11 @@ static int __init xen_mc_debugfs(void)
 	debugfs_create_u32("hypercalls", 0444, d_mc_debug, &mc_stats.hypercalls);
 	debugfs_create_u32("arg_total", 0444, d_mc_debug, &mc_stats.arg_total);
 
-	xen_debugfs_create_u32_array("batch_histo", 0444, d_mc_debug,
+	debugfs_create_u32_array("batch_histo", 0444, d_mc_debug,
 				     mc_stats.histo, MC_BATCH);
-	xen_debugfs_create_u32_array("hypercall_histo", 0444, d_mc_debug,
+	debugfs_create_u32_array("hypercall_histo", 0444, d_mc_debug,
 				     mc_stats.histo_hypercalls, NHYPERCALLS);
-	xen_debugfs_create_u32_array("flush_reasons", 0444, d_mc_debug,
+	debugfs_create_u32_array("flush_reasons", 0444, d_mc_debug,
 				     mc_stats.flush, FL_N_REASONS);
 
 	return 0;
arch/x86/xen/spinlock.c +1 -1
Index: linux-2.6.37/arch/x86/xen/spinlock.c
===================================================================
@@ -228,7 +228,7 @@ static int __init xen_spinlock_debugfs(v
 	debugfs_create_u64("time_blocked", 0444, d_spin_debug,
 			   &spinlock_stats.time_blocked);
 
-	xen_debugfs_create_u32_array("histo_blocked", 0444, d_spin_debug,
+	debugfs_create_u32_array("histo_blocked", 0444, d_spin_debug,
 				     spinlock_stats.histo_spin_blocked, HISTO_BUCKETS + 1);
 
 	return 0;
fs/debugfs/file.c +108 -0

117 lines not on this page · raw message

include/linux/debugfs.h +11 -0
Index: linux-2.6.37/include/linux/debugfs.h
===================================================================
@@ -74,6 +74,10 @@ struct dentry *debugfs_create_blob(const
 				  struct dentry *parent,
 				  struct debugfs_blob_wrapper *blob);
 
+struct dentry *debugfs_create_u32_array(const char *name, mode_t mode,
+					    struct dentry *parent,
+					    u32 *array, unsigned elements);
+
 bool debugfs_initialized(void);
 
 #else
@@ -187,6 +191,13 @@ static inline struct dentry *debugfs_cre
 {
 	return ERR_PTR(-ENODEV);
 }
+
+struct dentry *debugfs_create_u32_array(const char *name, mode_t mode,
+					    struct dentry *parent,
+					    u32 *array, unsigned elements)
+{
+	return ERR_PTR(-ENODEV);
+}
 
 static inline bool debugfs_initialized(void)
 {
#82 lore raw

PATCH 1/3 debugfs: Add support to print u32 array

In reply to Srivatsa Vaddagiri

Add debugfs support to print u32-arrays.

Most of this comes from Xen-hypervisor sources, which has been refactored to make the code common for other users as well.

---
 arch/x86/xen/debugfs.c    |  104 --------------------------------------------
 arch/x86/xen/debugfs.h    |    4 -
 arch/x86/xen/mmu.c        |    2 
 arch/x86/xen/multicalls.c |    6 +-
 arch/x86/xen/spinlock.c   |    2 
 fs/debugfs/file.c         |  108 ++++++++++++++++++++++++++++++++++++++++++++++
 include/linux/debugfs.h   |   11 ++++
 7 files changed, 124 insertions(+), 113 deletions(-)
arch/x86/xen/debugfs.c +0 -104
Index: linux-2.6.37/arch/x86/xen/debugfs.c
===================================================================
@@ -19,107 +19,3 @@ struct dentry * __init xen_init_debugfs(
 	return d_xen_debug;
 }
 
-struct array_data
-{
-	void *array;
-	unsigned elements;
-};
-
-static int u32_array_open(struct inode *inode, struct file *file)
-{
-	file->private_data = NULL;
-	return nonseekable_open(inode, file);
-}
-
-static size_t format_array(char *buf, size_t bufsize, const char *fmt,
-			   u32 *array, unsigned array_size)
-{
-	size_t ret = 0;
-	unsigned i;
-
-	for(i = 0; i < array_size; i++) {
-		size_t len;
-
-		len = snprintf(buf, bufsize, fmt, array[i]);
-		len++;	/* ' ' or '\n' */
-		ret += len;
-
-		if (buf) {
-			buf += len;
-			bufsize -= len;
-			buf[-1] = (i == array_size-1) ? '\n' : ' ';
-		}
-	}
-
-	ret++;		/* \0 */
-	if (buf)
-		*buf = '\0';
-
-	return ret;
-}
-
-static char *format_array_alloc(const char *fmt, u32 *array, unsigned array_size)
-{
-	size_t len = format_array(NULL, 0, fmt, array, array_size);
-	char *ret;
-
-	ret = kmalloc(len, GFP_KERNEL);
-	if (ret == NULL)
-		return NULL;
-
-	format_array(ret, len, fmt, array, array_size);
-	return ret;
-}
-
-static ssize_t u32_array_read(struct file *file, char __user *buf, size_t len,
-			      loff_t *ppos)
-{
-	struct inode *inode = file->f_path.dentry->d_inode;
-	struct array_data *data = inode->i_private;
-	size_t size;
-
-	if (*ppos == 0) {
-		if (file->private_data) {
-			kfree(file->private_data);
-			file->private_data = NULL;
-		}
-
-		file->private_data = format_array_alloc("%u", data->array, data->elements);
-	}
-
-	size = 0;
-	if (file->private_data)
-		size = strlen(file->private_data);
-
-	return simple_read_from_buffer(buf, len, ppos, file->private_data, size);
-}
-
-static int xen_array_release(struct inode *inode, struct file *file)
-{
-	kfree(file->private_data);
-
-	return 0;
-}
-
-static const struct file_operations u32_array_fops = {
-	.owner	= THIS_MODULE,
-	.open	= u32_array_open,
-	.release= xen_array_release,
-	.read	= u32_array_read,
-	.llseek = no_llseek,
-};
-
-struct dentry *xen_debugfs_create_u32_array(const char *name, mode_t mode,
-					    struct dentry *parent,
-					    u32 *array, unsigned elements)
-{
-	struct array_data *data = kmalloc(sizeof(*data), GFP_KERNEL);
-
-	if (data == NULL)
-		return NULL;
-
-	data->array = array;
-	data->elements = elements;
-
-	return debugfs_create_file(name, mode, parent, data, &u32_array_fops);
-}
arch/x86/xen/debugfs.h +0 -4
Index: linux-2.6.37/arch/x86/xen/debugfs.h
===================================================================
@@ -3,8 +3,4 @@
 
 struct dentry * __init xen_init_debugfs(void);
 
-struct dentry *xen_debugfs_create_u32_array(const char *name, mode_t mode,
-					    struct dentry *parent,
-					    u32 *array, unsigned elements);
-
 #endif /* _XEN_DEBUGFS_H */
arch/x86/xen/mmu.c +1 -1
Index: linux-2.6.37/arch/x86/xen/mmu.c
===================================================================
@@ -2757,7 +2757,7 @@ static int __init xen_mmu_debugfs(void)
 	debugfs_create_u32("mmu_update", 0444, d_mmu_debug, &mmu_stats.mmu_update);
 	debugfs_create_u32("mmu_update_extended", 0444, d_mmu_debug,
 			   &mmu_stats.mmu_update_extended);
-	xen_debugfs_create_u32_array("mmu_update_histo", 0444, d_mmu_debug,
+	debugfs_create_u32_array("mmu_update_histo", 0444, d_mmu_debug,
 				     mmu_stats.mmu_update_histo, 20);
 
 	debugfs_create_u32("set_pte_at", 0444, d_mmu_debug, &mmu_stats.set_pte_at);
arch/x86/xen/multicalls.c +3 -3
Index: linux-2.6.37/arch/x86/xen/multicalls.c
===================================================================
@@ -269,11 +269,11 @@ static int __init xen_mc_debugfs(void)
 	debugfs_create_u32("hypercalls", 0444, d_mc_debug, &mc_stats.hypercalls);
 	debugfs_create_u32("arg_total", 0444, d_mc_debug, &mc_stats.arg_total);
 
-	xen_debugfs_create_u32_array("batch_histo", 0444, d_mc_debug,
+	debugfs_create_u32_array("batch_histo", 0444, d_mc_debug,
 				     mc_stats.histo, MC_BATCH);
-	xen_debugfs_create_u32_array("hypercall_histo", 0444, d_mc_debug,
+	debugfs_create_u32_array("hypercall_histo", 0444, d_mc_debug,
 				     mc_stats.histo_hypercalls, NHYPERCALLS);
-	xen_debugfs_create_u32_array("flush_reasons", 0444, d_mc_debug,
+	debugfs_create_u32_array("flush_reasons", 0444, d_mc_debug,
 				     mc_stats.flush, FL_N_REASONS);
 
 	return 0;
arch/x86/xen/spinlock.c +1 -1
Index: linux-2.6.37/arch/x86/xen/spinlock.c
===================================================================
@@ -228,7 +228,7 @@ static int __init xen_spinlock_debugfs(v
 	debugfs_create_u64("time_blocked", 0444, d_spin_debug,
 			   &spinlock_stats.time_blocked);
 
-	xen_debugfs_create_u32_array("histo_blocked", 0444, d_spin_debug,
+	debugfs_create_u32_array("histo_blocked", 0444, d_spin_debug,
 				     spinlock_stats.histo_spin_blocked, HISTO_BUCKETS + 1);
 
 	return 0;
fs/debugfs/file.c +108 -0

117 lines not on this page · raw message

include/linux/debugfs.h +11 -0
Index: linux-2.6.37/include/linux/debugfs.h
===================================================================
@@ -74,6 +74,10 @@ struct dentry *debugfs_create_blob(const
 				  struct dentry *parent,
 				  struct debugfs_blob_wrapper *blob);
 
+struct dentry *debugfs_create_u32_array(const char *name, mode_t mode,
+					    struct dentry *parent,
+					    u32 *array, unsigned elements);
+
 bool debugfs_initialized(void);
 
 #else
@@ -187,6 +191,13 @@ static inline struct dentry *debugfs_cre
 {
 	return ERR_PTR(-ENODEV);
 }
+
+struct dentry *debugfs_create_u32_array(const char *name, mode_t mode,
+					    struct dentry *parent,
+					    u32 *array, unsigned elements)
+{
+	return ERR_PTR(-ENODEV);
+}
 
 static inline bool debugfs_initialized(void)
 {
#83 lore raw

PATCH 2/3 kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Srivatsa Vaddagiri

Add two hypercalls to KVM hypervisor to support pv-ticketlocks.

KVM_HC_WAIT_FOR_KICK blocks the calling vcpu until another vcpu kicks it or it is woken up because of an event like interrupt.

KVM_HC_KICK_CPU allows the calling vcpu to kick another vcpu.

The presence of these hypercalls is indicated to guest via KVM_FEATURE_WAIT_FOR_KICK/KVM_CAP_WAIT_FOR_KICK. Qemu needs a corresponding patch to pass up the presence of this feature to guest via cpuid. Patch to qemu will be sent separately.

---
 arch/x86/include/asm/kvm_para.h |    2 +
 arch/x86/kvm/x86.c              |   69 +++++++++++++++++++++++++++++++++++++++-
 include/linux/kvm.h             |    1 
 include/linux/kvm_host.h        |    1 
 include/linux/kvm_para.h        |    2 +
 virt/kvm/kvm_main.c             |    1 
 6 files changed, 75 insertions(+), 1 deletion(-)
arch/x86/include/asm/kvm_para.h +2 -0
Index: linux-2.6.37/arch/x86/include/asm/kvm_para.h
===================================================================
@@ -16,6 +16,8 @@
 #define KVM_FEATURE_CLOCKSOURCE		0
 #define KVM_FEATURE_NOP_IO_DELAY	1
 #define KVM_FEATURE_MMU_OP		2
+#define KVM_FEATURE_WAIT_FOR_KICK       4
+
 /* This indicates that the new set of kvmclock msrs
  * are available. The use of 0x11 and 0x12 is deprecated
  */
arch/x86/kvm/x86.c +68 -1

93 lines not on this page · raw message

include/linux/kvm.h +1 -0
Index: linux-2.6.37/include/linux/kvm.h
===================================================================
@@ -540,6 +540,7 @@ struct kvm_ppc_pvinfo {
 #endif
 #define KVM_CAP_PPC_GET_PVINFO 57
 #define KVM_CAP_PPC_IRQ_LEVEL 58
+#define KVM_CAP_WAIT_FOR_KICK 59
 
 #ifdef KVM_CAP_IRQ_ROUTING
 
include/linux/kvm_host.h +1 -0
Index: linux-2.6.37/include/linux/kvm_host.h
===================================================================
@@ -105,6 +105,7 @@ struct kvm_vcpu {
 #endif
 
 	struct kvm_vcpu_arch arch;
+	int kicked;
 };
 
 /*
include/linux/kvm_para.h +2 -0
Index: linux-2.6.37/include/linux/kvm_para.h
===================================================================
@@ -19,6 +19,8 @@
 #define KVM_HC_MMU_OP			2
 #define KVM_HC_FEATURES			3
 #define KVM_HC_PPC_MAP_MAGIC_PAGE	4
+#define KVM_HC_WAIT_FOR_KICK            5
+#define KVM_HC_KICK_CPU		        6
 
 /*
  * hypercalls use architecture specific
virt/kvm/kvm_main.c +1 -0
Index: linux-2.6.37/virt/kvm/kvm_main.c
===================================================================
@@ -185,6 +185,7 @@ int kvm_vcpu_init(struct kvm_vcpu *vcpu,
 	vcpu->cpu = -1;
 	vcpu->kvm = kvm;
 	vcpu->vcpu_id = id;
+	vcpu->kicked = 0;
 	init_waitqueue_head(&vcpu->wq);
 
 	page = alloc_page(GFP_KERNEL | __GFP_ZERO);
#116 lore raw

PATCH 2/3 kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Srivatsa Vaddagiri

Add two hypercalls to KVM hypervisor to support pv-ticketlocks.

KVM_HC_WAIT_FOR_KICK blocks the calling vcpu until another vcpu kicks it or it is woken up because of an event like interrupt.

KVM_HC_KICK_CPU allows the calling vcpu to kick another vcpu.

The presence of these hypercalls is indicated to guest via KVM_FEATURE_WAIT_FOR_KICK/KVM_CAP_WAIT_FOR_KICK. Qemu needs a corresponding patch to pass up the presence of this feature to guest via cpuid. Patch to qemu will be sent separately.

---
 arch/x86/include/asm/kvm_para.h |    2 +
 arch/x86/kvm/x86.c              |   69 +++++++++++++++++++++++++++++++++++++++-
 include/linux/kvm.h             |    1 
 include/linux/kvm_host.h        |    1 
 include/linux/kvm_para.h        |    2 +
 virt/kvm/kvm_main.c             |    1 
 6 files changed, 75 insertions(+), 1 deletion(-)
arch/x86/include/asm/kvm_para.h +2 -0
Index: linux-2.6.37/arch/x86/include/asm/kvm_para.h
===================================================================
@@ -16,6 +16,8 @@
 #define KVM_FEATURE_CLOCKSOURCE		0
 #define KVM_FEATURE_NOP_IO_DELAY	1
 #define KVM_FEATURE_MMU_OP		2
+#define KVM_FEATURE_WAIT_FOR_KICK       4
+
 /* This indicates that the new set of kvmclock msrs
  * are available. The use of 0x11 and 0x12 is deprecated
  */
arch/x86/kvm/x86.c +68 -1

93 lines not on this page · raw message

include/linux/kvm.h +1 -0
Index: linux-2.6.37/include/linux/kvm.h
===================================================================
@@ -540,6 +540,7 @@ struct kvm_ppc_pvinfo {
 #endif
 #define KVM_CAP_PPC_GET_PVINFO 57
 #define KVM_CAP_PPC_IRQ_LEVEL 58
+#define KVM_CAP_WAIT_FOR_KICK 59
 
 #ifdef KVM_CAP_IRQ_ROUTING
 
include/linux/kvm_host.h +1 -0
Index: linux-2.6.37/include/linux/kvm_host.h
===================================================================
@@ -105,6 +105,7 @@ struct kvm_vcpu {
 #endif
 
 	struct kvm_vcpu_arch arch;
+	int kicked;
 };
 
 /*
include/linux/kvm_para.h +2 -0
Index: linux-2.6.37/include/linux/kvm_para.h
===================================================================
@@ -19,6 +19,8 @@
 #define KVM_HC_MMU_OP			2
 #define KVM_HC_FEATURES			3
 #define KVM_HC_PPC_MAP_MAGIC_PAGE	4
+#define KVM_HC_WAIT_FOR_KICK            5
+#define KVM_HC_KICK_CPU		        6
 
 /*
  * hypercalls use architecture specific
virt/kvm/kvm_main.c +1 -0
Index: linux-2.6.37/virt/kvm/kvm_main.c
===================================================================
@@ -185,6 +185,7 @@ int kvm_vcpu_init(struct kvm_vcpu *vcpu,
 	vcpu->cpu = -1;
 	vcpu->kvm = kvm;
 	vcpu->vcpu_id = id;
+	vcpu->kicked = 0;
 	init_waitqueue_head(&vcpu->wq);
 
 	page = alloc_page(GFP_KERNEL | __GFP_ZERO);
#117 lore raw

PATCH 3/3 kvm guest : Add support for pv-ticketlocks

In reply to Srivatsa Vaddagiri

This patch extends Linux guests running on KVM hypervisor to support pv-ticketlocks. Very early during bootup, paravirtualied KVM guest detects if the hypervisor has required feature (KVM_FEATURE_WAIT_FOR_KICK) to support pv-ticketlocks. If so, support for pv-ticketlocks is registered via pv_lock_ops.

---
 arch/x86/Kconfig                |    9 +
 arch/x86/include/asm/kvm_para.h |    8 +
 arch/x86/kernel/head64.c        |    3 
 arch/x86/kernel/kvm.c           |  208 ++++++++++++++++++++++++++++++++++++++++
 4 files changed, 228 insertions(+)
arch/x86/Kconfig +9 -0
Index: linux-2.6.37/arch/x86/Kconfig
===================================================================
@@ -508,6 +508,15 @@ config KVM_GUEST
 	  This option enables various optimizations for running under the KVM
 	  hypervisor.
 
+config KVM_DEBUG_FS
+	bool "Enable debug information for KVM Guests in debugfs"
+	depends on KVM_GUEST
+	default n
+	---help---
+	  This option enables collection of various statistics for KVM guest.
+   	  Statistics are displayed in debugfs filesystem. Enabling this option
+	  may incur significant overhead.
+
 source "arch/x86/lguest/Kconfig"
 
 config PARAVIRT
arch/x86/include/asm/kvm_para.h +8 -0
Index: linux-2.6.37/arch/x86/include/asm/kvm_para.h
===================================================================
@@ -162,8 +162,16 @@ static inline unsigned int kvm_arch_para
 
 #ifdef CONFIG_KVM_GUEST
 void __init kvm_guest_init(void);
+
+#ifdef CONFIG_PARAVIRT_SPINLOCKS
+void __init kvm_guest_early_init(void);
+#else
+#define kvm_guest_early_init() do { } while (0)
+#endif
+
 #else
 #define kvm_guest_init() do { } while (0)
+#define kvm_guest_early_init() do { } while (0)
 #endif
 
 #endif /* __KERNEL__ */
arch/x86/kernel/head64.c +3 -0
Index: linux-2.6.37/arch/x86/kernel/head64.c
===================================================================
@@ -13,6 +13,7 @@
 #include <linux/start_kernel.h>
 #include <linux/io.h>
 #include <linux/memblock.h>
+#include <linux/kvm_para.h>
 
 #include <asm/processor.h>
 #include <asm/proto.h>
@@ -118,6 +119,8 @@ void __init x86_64_start_reservations(ch
 
 	reserve_ebda_region();
 
+	kvm_guest_early_init();
+
 	/*
 	 * At this point everything still needed from the boot loader
 	 * or BIOS or kernel text should be early reserved or marked not
arch/x86/kernel/kvm.c +208 -0

211 lines not on this page · raw message

#118 lore raw

PATCH 3/3 kvm guest : Add support for pv-ticketlocks

In reply to Srivatsa Vaddagiri

This patch extends Linux guests running on KVM hypervisor to support pv-ticketlocks. Very early during bootup, paravirtualied KVM guest detects if the hypervisor has required feature (KVM_FEATURE_WAIT_FOR_KICK) to support pv-ticketlocks. If so, support for pv-ticketlocks is registered via pv_lock_ops.

---
 arch/x86/Kconfig                |    9 +
 arch/x86/include/asm/kvm_para.h |    8 +
 arch/x86/kernel/head64.c        |    3 
 arch/x86/kernel/kvm.c           |  208 ++++++++++++++++++++++++++++++++++++++++
 4 files changed, 228 insertions(+)
arch/x86/Kconfig +9 -0
Index: linux-2.6.37/arch/x86/Kconfig
===================================================================
@@ -508,6 +508,15 @@ config KVM_GUEST
 	  This option enables various optimizations for running under the KVM
 	  hypervisor.
 
+config KVM_DEBUG_FS
+	bool "Enable debug information for KVM Guests in debugfs"
+	depends on KVM_GUEST
+	default n
+	---help---
+	  This option enables collection of various statistics for KVM guest.
+   	  Statistics are displayed in debugfs filesystem. Enabling this option
+	  may incur significant overhead.
+
 source "arch/x86/lguest/Kconfig"
 
 config PARAVIRT
arch/x86/include/asm/kvm_para.h +8 -0
Index: linux-2.6.37/arch/x86/include/asm/kvm_para.h
===================================================================
@@ -162,8 +162,16 @@ static inline unsigned int kvm_arch_para
 
 #ifdef CONFIG_KVM_GUEST
 void __init kvm_guest_init(void);
+
+#ifdef CONFIG_PARAVIRT_SPINLOCKS
+void __init kvm_guest_early_init(void);
+#else
+#define kvm_guest_early_init() do { } while (0)
+#endif
+
 #else
 #define kvm_guest_init() do { } while (0)
+#define kvm_guest_early_init() do { } while (0)
 #endif
 
 #endif /* __KERNEL__ */
arch/x86/kernel/head64.c +3 -0
Index: linux-2.6.37/arch/x86/kernel/head64.c
===================================================================
@@ -13,6 +13,7 @@
 #include <linux/start_kernel.h>
 #include <linux/io.h>
 #include <linux/memblock.h>
+#include <linux/kvm_para.h>
 
 #include <asm/processor.h>
 #include <asm/proto.h>
@@ -118,6 +119,8 @@ void __init x86_64_start_reservations(ch
 
 	reserve_ebda_region();
 
+	kvm_guest_early_init();
+
 	/*
 	 * At this point everything still needed from the boot loader
 	 * or BIOS or kernel text should be early reserved or marked not
arch/x86/kernel/kvm.c +208 -0

211 lines not on this page · raw message

maintainer
#84 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Srivatsa Vaddagiri
Quoted 11 lines · Srivatsa Vaddagiri

Add two hypercalls to KVM hypervisor to support pv-ticketlocks.

KVM_HC_WAIT_FOR_KICK blocks the calling vcpu until another vcpu kicks it or it is woken up because of an event like interrupt.

KVM_HC_KICK_CPU allows the calling vcpu to kick another vcpu.

The presence of these hypercalls is indicated to guest via KVM_FEATURE_WAIT_FOR_KICK/KVM_CAP_WAIT_FOR_KICK. Qemu needs a corresponding patch to pass up the presence of this feature to guest via cpuid. Patch to qemu will be sent separately.

I didn't really read the patch, and I totally forgot everything from when I looked at the Xen series, but does the Xen/KVM hypercall interface for this include the vcpu to await the kick from?

My guess is not, since the ticket locks used don't know who the owner is, which is of course, sad. There are FIFO spinlock implementations that can do this though.. although I think they all have a bigger memory footprint.

The reason for wanting this should be clear I guess, it allows PI.

maintainer
#111 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Srivatsa Vaddagiri
Quoted 11 lines · Srivatsa Vaddagiri

Add two hypercalls to KVM hypervisor to support pv-ticketlocks.

KVM_HC_WAIT_FOR_KICK blocks the calling vcpu until another vcpu kicks it or it is woken up because of an event like interrupt.

KVM_HC_KICK_CPU allows the calling vcpu to kick another vcpu.

The presence of these hypercalls is indicated to guest via KVM_FEATURE_WAIT_FOR_KICK/KVM_CAP_WAIT_FOR_KICK. Qemu needs a corresponding patch to pass up the presence of this feature to guest via cpuid. Patch to qemu will be sent separately.

I didn't really read the patch, and I totally forgot everything from when I looked at the Xen series, but does the Xen/KVM hypercall interface for this include the vcpu to await the kick from?

My guess is not, since the ticket locks used don't know who the owner is, which is of course, sad. There are FIFO spinlock implementations that can do this though.. although I think they all have a bigger memory footprint.

The reason for wanting this should be clear I guess, it allows PI.

#112 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Srivatsa Vaddagiri
Quoted 4 lines · Srivatsa Vaddagiri

Add two hypercalls to KVM hypervisor to support pv-ticketlocks.

KVM_HC_WAIT_FOR_KICK blocks the calling vcpu until another vcpu kicks it or it is woken up because of an event like interrupt.

One possibility is to extend this hypercall to do a directed yield as well, which needs some more thought. Another issue that needs to be resolved with pv-ticketlocks is the impact on intra-VM fairness. A guest experiencing heavy contention can keep yielding cpu, allowing other VMs to get more time than they deserve.

- vatsa

#115 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Srivatsa Vaddagiri
Quoted 4 lines · Srivatsa Vaddagiri

Add two hypercalls to KVM hypervisor to support pv-ticketlocks.

KVM_HC_WAIT_FOR_KICK blocks the calling vcpu until another vcpu kicks it or it is woken up because of an event like interrupt.

One possibility is to extend this hypercall to do a directed yield as well, which needs some more thought. Another issue that needs to be resolved with pv-ticketlocks is the impact on intra-VM fairness. A guest experiencing heavy contention can keep yielding cpu, allowing other VMs to get more time than they deserve.

- vatsa

maintainer
#113 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Srivatsa Vaddagiri
Quoted 11 lines · Srivatsa Vaddagiri
Quoted 4 lines · Srivatsa Vaddagiri

Add two hypercalls to KVM hypervisor to support pv-ticketlocks.

KVM_HC_WAIT_FOR_KICK blocks the calling vcpu until another vcpu kicks it or it is woken up because of an event like interrupt.

One possibility is to extend this hypercall to do a directed yield as well, which needs some more thought. Another issue that needs to be resolved with pv-ticketlocks is the impact on intra-VM fairness. A guest experiencing heavy contention can keep yielding cpu, allowing other VMs to get more time than they deserve.

No, yield sucks, if you know the owner you can do actual PI.

maintainer
#114 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Srivatsa Vaddagiri
Quoted 11 lines · Srivatsa Vaddagiri
Quoted 4 lines · Srivatsa Vaddagiri

Add two hypercalls to KVM hypervisor to support pv-ticketlocks.

KVM_HC_WAIT_FOR_KICK blocks the calling vcpu until another vcpu kicks it or it is woken up because of an event like interrupt.

One possibility is to extend this hypercall to do a directed yield as well, which needs some more thought. Another issue that needs to be resolved with pv-ticketlocks is the impact on intra-VM fairness. A guest experiencing heavy contention can keep yielding cpu, allowing other VMs to get more time than they deserve.

No, yield sucks, if you know the owner you can do actual PI.

#85 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Peter Zijlstra
Quoted 3 lines · Peter Zijlstra

I didn't really read the patch, and I totally forgot everything from when I looked at the Xen series, but does the Xen/KVM hypercall interface for this include the vcpu to await the kick from?

No not yet, for reasons you mention below.

Quoted 6 lines

My guess is not, since the ticket locks used don't know who the owner is, which is of course, sad. There are FIFO spinlock implementations that can do this though.. although I think they all have a bigger memory footprint.

The reason for wanting this should be clear I guess, it allows PI.

Yeah - that would be good to experiment with.

- vatsa

#86 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Peter Zijlstra
Quoted 3 lines · Peter Zijlstra

I didn't really read the patch, and I totally forgot everything from when I looked at the Xen series, but does the Xen/KVM hypercall interface for this include the vcpu to await the kick from?

No not yet, for reasons you mention below.

Quoted 6 lines

My guess is not, since the ticket locks used don't know who the owner is, which is of course, sad. There are FIFO spinlock implementations that can do this though.. although I think they all have a bigger memory footprint.

The reason for wanting this should be clear I guess, it allows PI.

Yeah - that would be good to experiment with.

- vatsa

#64 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Srivatsa Vaddagiri
Quoted 44 lines · Srivatsa Vaddagiri
Quoted 22 lines · Jeremy Fitzhardinge

From: Jeremy Fitzhardinge <[email protected]>

Maintain a flag in both LSBs of the ticket lock which indicates whether anyone is in the lock slowpath and may need kicking when the current holder unlocks. The flags are set when the first locker enters the slowpath, and cleared when unlocking to an empty queue.

In the specific implementation of lock_spinning(), make sure to set the slowpath flags on the lock just before blocking. We must do this before the last-chance pickup test to prevent a deadlock with the unlocker:

Unlocker Locker

				test for lock pickup
					-> fail
test slowpath + unlock
	-> false
				set slowpath flags
				block

Whereas this works in any ordering:

Quoted 7 lines

Unlocker Locker
set slowpath flags test for lock pickup
-> fail
block
test slowpath + unlock

	-> true, kick

I think this is still racy ..

Unlocker Locker

test slowpath

	-> false
		
				set slowpath flag
				test for lock pickup
					-> fail
				block
Quoted 5 lines

unlock

unlock needs to happen first before testing slowpath? I have made that change for my KVM guest and it seems to be working well with that change .. Will cleanup and post my patches shortly

I think you're probably right; when I last tested this code, it was hanging in at about the rate this kind of race would cause. And in my previous analysis of similar schemes (the current pv spinlock code), it was always correct to do the "slowpath" test after doing do the unlock.

*But* I haven't yet had the chance to specifically go through and analyse your patch in detail to make sure there's nothing else going on, so take this as provisional.

How much testing have you given it?

Thanks,
J

#73 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Srivatsa Vaddagiri
Quoted 44 lines · Srivatsa Vaddagiri
Quoted 22 lines · Jeremy Fitzhardinge

From: Jeremy Fitzhardinge <[email protected]>

Maintain a flag in both LSBs of the ticket lock which indicates whether anyone is in the lock slowpath and may need kicking when the current holder unlocks. The flags are set when the first locker enters the slowpath, and cleared when unlocking to an empty queue.

In the specific implementation of lock_spinning(), make sure to set the slowpath flags on the lock just before blocking. We must do this before the last-chance pickup test to prevent a deadlock with the unlocker:

Unlocker Locker

				test for lock pickup
					-> fail
test slowpath + unlock
	-> false
				set slowpath flags
				block

Whereas this works in any ordering:

Quoted 7 lines

Unlocker Locker
set slowpath flags test for lock pickup
-> fail
block
test slowpath + unlock

	-> true, kick

I think this is still racy ..

Unlocker Locker

test slowpath

	-> false
		
				set slowpath flag
				test for lock pickup
					-> fail
				block
Quoted 5 lines

unlock

unlock needs to happen first before testing slowpath? I have made that change for my KVM guest and it seems to be working well with that change .. Will cleanup and post my patches shortly

I think you're probably right; when I last tested this code, it was hanging in at about the rate this kind of race would cause. And in my previous analysis of similar schemes (the current pv spinlock code), it was always correct to do the "slowpath" test after doing do the unlock.

*But* I haven't yet had the chance to specifically go through and analyse your patch in detail to make sure there's nothing else going on, so take this as provisional.

How much testing have you given it?

Thanks,
J

#65 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge
Quoted 10 lines · Jeremy Fitzhardinge

I think you're probably right; when I last tested this code, it was hanging in at about the rate this kind of race would cause. And in my previous analysis of similar schemes (the current pv spinlock code), it was always correct to do the "slowpath" test after doing do the unlock.

*But* I haven't yet had the chance to specifically go through and analyse your patch in detail to make sure there's nothing else going on, so take this as provisional.

How much testing have you given it?

I have tested quite extensively with booting a 16-vcpu guest (on a 16-pcpu host) and running kernel compine (with 32-threads). Without this patch, I had difficulty booting/shutting-down successfully (it would hang mid-way).

- vatsa

#72 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge
Quoted 10 lines · Jeremy Fitzhardinge

I think you're probably right; when I last tested this code, it was hanging in at about the rate this kind of race would cause. And in my previous analysis of similar schemes (the current pv spinlock code), it was always correct to do the "slowpath" test after doing do the unlock.

*But* I haven't yet had the chance to specifically go through and analyse your patch in detail to make sure there's nothing else going on, so take this as provisional.

How much testing have you given it?

I have tested quite extensively with booting a 16-vcpu guest (on a 16-pcpu host) and running kernel compine (with 32-threads). Without this patch, I had difficulty booting/shutting-down successfully (it would hang mid-way).

- vatsa

#87 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Peter Zijlstra
Quoted 13 lines · Peter Zijlstra
Quoted 11 lines · Srivatsa Vaddagiri

Add two hypercalls to KVM hypervisor to support pv-ticketlocks.

KVM_HC_WAIT_FOR_KICK blocks the calling vcpu until another vcpu kicks it or it is woken up because of an event like interrupt.

KVM_HC_KICK_CPU allows the calling vcpu to kick another vcpu.

The presence of these hypercalls is indicated to guest via KVM_FEATURE_WAIT_FOR_KICK/KVM_CAP_WAIT_FOR_KICK. Qemu needs a corresponding patch to pass up the presence of this feature to guest via cpuid. Patch to qemu will be sent separately.

Quoted 8 lines

I didn't really read the patch, and I totally forgot everything from when I looked at the Xen series, but does the Xen/KVM hypercall interface for this include the vcpu to await the kick from?

My guess is not, since the ticket locks used don't know who the owner is, which is of course, sad. There are FIFO spinlock implementations that can do this though.. although I think they all have a bigger memory footprint.

At least in the Xen code, a current owner isn't very useful, because we need the current owner to kick the *next* owner to life at release time, which we can't do without some structure recording which ticket belongs to which cpu.

(A reminder: the big problem with ticket locks is not with the current owner getting preempted, but making sure the next VCPU gets scheduled quickly when the current one releases; without that all the waiting VCPUs burn the timeslices until the VCPU scheduler gets around to scheduling the actual next in line.)

At present, the code needs to scan an array of percpu "I am waiting on lock X with ticket Y" structures to work out who's next. The search is somewhat optimised by keeping a cpuset of which CPUs are actually blocked on spinlocks, but its still going to scale badly with lots of CPUs.

I haven't thought of a good way to improve on this; an obvious approach is to just add a pointer to the spinlock and hang an explicit linked list off it, but that's incompatible with wanting to avoid expanding the lock.

You could have a table of auxiliary per-lock data hashed on the lock address, but its not clear to me that its an improvement on the array approach, especially given the synchronization issues of keeping that structure up to date (do we have a generic lockless hashtable implementation?). But perhaps its one of those things that makes sense at larger scales.

Quoted 1 line

The reason for wanting this should be clear I guess, it allows PI.

Well, if we can expand the spinlock to include an owner, then all this becomes moot...

J

#110 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Peter Zijlstra
Quoted 13 lines · Peter Zijlstra
Quoted 11 lines · Srivatsa Vaddagiri

Add two hypercalls to KVM hypervisor to support pv-ticketlocks.

KVM_HC_WAIT_FOR_KICK blocks the calling vcpu until another vcpu kicks it or it is woken up because of an event like interrupt.

KVM_HC_KICK_CPU allows the calling vcpu to kick another vcpu.

The presence of these hypercalls is indicated to guest via KVM_FEATURE_WAIT_FOR_KICK/KVM_CAP_WAIT_FOR_KICK. Qemu needs a corresponding patch to pass up the presence of this feature to guest via cpuid. Patch to qemu will be sent separately.

Quoted 8 lines

I didn't really read the patch, and I totally forgot everything from when I looked at the Xen series, but does the Xen/KVM hypercall interface for this include the vcpu to await the kick from?

My guess is not, since the ticket locks used don't know who the owner is, which is of course, sad. There are FIFO spinlock implementations that can do this though.. although I think they all have a bigger memory footprint.

At least in the Xen code, a current owner isn't very useful, because we need the current owner to kick the *next* owner to life at release time, which we can't do without some structure recording which ticket belongs to which cpu.

(A reminder: the big problem with ticket locks is not with the current owner getting preempted, but making sure the next VCPU gets scheduled quickly when the current one releases; without that all the waiting VCPUs burn the timeslices until the VCPU scheduler gets around to scheduling the actual next in line.)

At present, the code needs to scan an array of percpu "I am waiting on lock X with ticket Y" structures to work out who's next. The search is somewhat optimised by keeping a cpuset of which CPUs are actually blocked on spinlocks, but its still going to scale badly with lots of CPUs.

I haven't thought of a good way to improve on this; an obvious approach is to just add a pointer to the spinlock and hang an explicit linked list off it, but that's incompatible with wanting to avoid expanding the lock.

You could have a table of auxiliary per-lock data hashed on the lock address, but its not clear to me that its an improvement on the array approach, especially given the synchronization issues of keeping that structure up to date (do we have a generic lockless hashtable implementation?). But perhaps its one of those things that makes sense at larger scales.

Quoted 1 line

The reason for wanting this should be clear I guess, it allows PI.

Well, if we can expand the spinlock to include an owner, then all this becomes moot...

J

#66 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Srivatsa Vaddagiri
Quoted 3 lines · Srivatsa Vaddagiri

I have tested quite extensively with booting a 16-vcpu guest (on a 16-pcpu host) and running kernel compine (with 32-threads). Without this patch, I had difficulty booting/shutting-down successfully (it would hang mid-way).

Sounds good. But I like to test with "make -j 100-200" to really give things a workout.

J

#71 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Srivatsa Vaddagiri
Quoted 3 lines · Srivatsa Vaddagiri

I have tested quite extensively with booting a 16-vcpu guest (on a 16-pcpu host) and running kernel compine (with 32-threads). Without this patch, I had difficulty booting/shutting-down successfully (it would hang mid-way).

Sounds good. But I like to test with "make -j 100-200" to really give things a workout.

J

#67 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge
Quoted 7 lines · Jeremy Fitzhardinge
Quoted 3 lines · Srivatsa Vaddagiri

I have tested quite extensively with booting a 16-vcpu guest (on a 16-pcpu host) and running kernel compine (with 32-threads). Without this patch, I had difficulty booting/shutting-down successfully (it would hang mid-way).

Sounds good. But I like to test with "make -j 100-200" to really give things a workout.

I reran the tests with the following configuration:

Host : 16pcpus, 32GB Memory
Single KVM guest w/ 32vcpus, 16GB memory

It survived a kernel compile with 200 threads once and another time with 300 threads. 'make allyesconfig' was run before compiling the kernel. So looks quite stable to me ..additional testing from wider community will also help.

- vasa

#68 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge
Quoted 7 lines · Jeremy Fitzhardinge
Quoted 3 lines · Srivatsa Vaddagiri

I have tested quite extensively with booting a 16-vcpu guest (on a 16-pcpu host) and running kernel compine (with 32-threads). Without this patch, I had difficulty booting/shutting-down successfully (it would hang mid-way).

Sounds good. But I like to test with "make -j 100-200" to really give things a workout.

I reran the tests with the following configuration:

Host : 16pcpus, 32GB Memory
Single KVM guest w/ 32vcpus, 16GB memory

It survived a kernel compile with 200 threads once and another time with 300 threads. 'make allyesconfig' was run before compiling the kernel. So looks quite stable to me ..additional testing from wider community will also help.

- vasa

#69 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge
Quoted 9 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
Quoted 1 line · Srivatsa Vaddagiri

I have tested quite extensively with booting a 16-vcpu guest (on a 16-pcpu

host)

Quoted 2 lines

and running kernel compine (with 32-threads). Without this patch, I had difficulty booting/shutting-down successfully (it would hang mid-way).

Sounds good. But I like to test with "make -j 100-200" to really give things a workout.

Hmm, in my experience, heavily over-committing CPUs (e.g. a domain with double or more the vCPU-s that the system has pCPU-s, or the pCPU-s the domain is allowed to run on) is a much better test for eventual problems in the spin lock code paths.

Jan

#70 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge
Quoted 9 lines
Quoted 1 line
Quoted 1 line · Jeremy Fitzhardinge
Quoted 1 line · Srivatsa Vaddagiri

I have tested quite extensively with booting a 16-vcpu guest (on a 16-pcpu

host)

Quoted 2 lines

and running kernel compine (with 32-threads). Without this patch, I had difficulty booting/shutting-down successfully (it would hang mid-way).

Sounds good. But I like to test with "make -j 100-200" to really give things a workout.

Hmm, in my experience, heavily over-committing CPUs (e.g. a domain with double or more the vCPU-s that the system has pCPU-s, or the pCPU-s the domain is allowed to run on) is a much better test for eventual problems in the spin lock code paths.

Jan

#88 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Jeremy Fitzhardinge
Quoted 4 lines · Jeremy Fitzhardinge
Quoted 1 line

The reason for wanting this should be clear I guess, it allows PI.

Well, if we can expand the spinlock to include an owner, then all this becomes moot...

How so? Having an owner will not eliminate the need for pv-ticketlocks afaict. We still need a mechanism to reduce latency in scheduling the next thread-in-waiting, which is achieved by your patches.

- vatsa

#91 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Jeremy Fitzhardinge
Quoted 4 lines · Jeremy Fitzhardinge
Quoted 1 line

The reason for wanting this should be clear I guess, it allows PI.

Well, if we can expand the spinlock to include an owner, then all this becomes moot...

How so? Having an owner will not eliminate the need for pv-ticketlocks afaict. We still need a mechanism to reduce latency in scheduling the next thread-in-waiting, which is achieved by your patches.

- vatsa

#92 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Jeremy Fitzhardinge
Quoted 9 lines · Jeremy Fitzhardinge
Quoted 8 lines

I didn't really read the patch, and I totally forgot everything from when I looked at the Xen series, but does the Xen/KVM hypercall interface for this include the vcpu to await the kick from?

My guess is not, since the ticket locks used don't know who the owner is, which is of course, sad. There are FIFO spinlock implementations that can do this though.. although I think they all have a bigger memory footprint.

Quoted 4 lines

At least in the Xen code, a current owner isn't very useful, because we need the current owner to kick the *next* owner to life at release time, which we can't do without some structure recording which ticket belongs to which cpu.

If we had a yield-to [1] sort of interface _and_ information on which vcpu owns a lock, then lock-spinners can yield-to the owning vcpu, while the unlocking vcpu can yield-to the next-vcpu-in-waiting. The key here is not to sleep when waiting for locks (as implemented by current patch-series, which can put other VMs at an advantage by giving them more time than they are entitled to) and also to ensure that lock-owner as well as the next-in-line lock-owner are not unduly made to wait for cpu.

Is there a way we can dynamically expand the size of lock only upon contention to include additional information like owning vcpu? Have the lock point to a per-cpu area upon contention where additional details can be stored perhaps?

1. https://lkml.org/lkml/2011/1/14/44

- vatsa

#109 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Jeremy Fitzhardinge
Quoted 9 lines · Jeremy Fitzhardinge
Quoted 8 lines

I didn't really read the patch, and I totally forgot everything from when I looked at the Xen series, but does the Xen/KVM hypercall interface for this include the vcpu to await the kick from?

My guess is not, since the ticket locks used don't know who the owner is, which is of course, sad. There are FIFO spinlock implementations that can do this though.. although I think they all have a bigger memory footprint.

Quoted 4 lines

At least in the Xen code, a current owner isn't very useful, because we need the current owner to kick the *next* owner to life at release time, which we can't do without some structure recording which ticket belongs to which cpu.

If we had a yield-to [1] sort of interface _and_ information on which vcpu owns a lock, then lock-spinners can yield-to the owning vcpu, while the unlocking vcpu can yield-to the next-vcpu-in-waiting. The key here is not to sleep when waiting for locks (as implemented by current patch-series, which can put other VMs at an advantage by giving them more time than they are entitled to) and also to ensure that lock-owner as well as the next-in-line lock-owner are not unduly made to wait for cpu.

Is there a way we can dynamically expand the size of lock only upon contention to include additional information like owning vcpu? Have the lock point to a per-cpu area upon contention where additional details can be stored perhaps?

1. https://lkml.org/lkml/2011/1/14/44

- vatsa

maintainer
#93 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Srivatsa Vaddagiri
Quoted 3 lines · Srivatsa Vaddagiri

If we had a yield-to [1] sort of interface _and_ information on which vcpu owns a lock, then lock-spinners can yield-to the owning vcpu,

and then I'd nak it for being stupid ;-)

really, yield*() is retarded, never even consider using it. If you've got the actual owner you can do full blown PI, which is tons better than a 'do-something-random' call.

The only reason the whole non-virt pause loop filtering muck uses it is because it really doesn't know anything, and do-something is pretty much all it can do. Its a broken interface.

maintainer
#96 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Srivatsa Vaddagiri
Quoted 3 lines · Srivatsa Vaddagiri

If we had a yield-to [1] sort of interface _and_ information on which vcpu owns a lock, then lock-spinners can yield-to the owning vcpu,

and then I'd nak it for being stupid ;-)

really, yield*() is retarded, never even consider using it. If you've got the actual owner you can do full blown PI, which is tons better than a 'do-something-random' call.

The only reason the whole non-virt pause loop filtering muck uses it is because it really doesn't know anything, and do-something is pretty much all it can do. Its a broken interface.

#94 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Peter Zijlstra
Quoted 10 lines · Peter Zijlstra
Quoted 3 lines · Srivatsa Vaddagiri

If we had a yield-to [1] sort of interface _and_ information on which vcpu owns a lock, then lock-spinners can yield-to the owning vcpu,

and then I'd nak it for being stupid ;-)

really, yield*() is retarded, never even consider using it. If you've got the actual owner you can do full blown PI, which is tons better than a 'do-something-random' call.

Yes definitely that would be much better than yield-to.

Quoted 3 lines

The only reason the whole non-virt pause loop filtering muck uses it is because it really doesn't know anything, and do-something is pretty much all it can do. Its a broken interface.

- vatsa

#95 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Peter Zijlstra
Quoted 10 lines · Peter Zijlstra
Quoted 3 lines · Srivatsa Vaddagiri

If we had a yield-to [1] sort of interface _and_ information on which vcpu owns a lock, then lock-spinners can yield-to the owning vcpu,

and then I'd nak it for being stupid ;-)

really, yield*() is retarded, never even consider using it. If you've got the actual owner you can do full blown PI, which is tons better than a 'do-something-random' call.

Yes definitely that would be much better than yield-to.

Quoted 3 lines

The only reason the whole non-virt pause loop filtering muck uses it is because it really doesn't know anything, and do-something is pretty much all it can do. Its a broken interface.

- vatsa

#89 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Srivatsa Vaddagiri
Quoted 7 lines · Srivatsa Vaddagiri
Quoted 3 lines · Jeremy Fitzhardinge
Quoted 1 line

The reason for wanting this should be clear I guess, it allows PI.

Well, if we can expand the spinlock to include an owner, then all this becomes moot...

How so? Having an owner will not eliminate the need for pv-ticketlocks afaict. We still need a mechanism to reduce latency in scheduling the next thread-in-waiting, which is achieved by your patches.

No, sorry, I should have been clearer. I meant that going to the effort of not increasing the lock size to record "in slowpath" state.

J

#90 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Srivatsa Vaddagiri
Quoted 7 lines · Srivatsa Vaddagiri
Quoted 3 lines · Jeremy Fitzhardinge
Quoted 1 line

The reason for wanting this should be clear I guess, it allows PI.

Well, if we can expand the spinlock to include an owner, then all this becomes moot...

How so? Having an owner will not eliminate the need for pv-ticketlocks afaict. We still need a mechanism to reduce latency in scheduling the next thread-in-waiting, which is achieved by your patches.

No, sorry, I should have been clearer. I meant that going to the effort of not increasing the lock size to record "in slowpath" state.

J

#97 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Srivatsa Vaddagiri
Quoted 7 lines · Srivatsa Vaddagiri
Quoted 4 lines

At least in the Xen code, a current owner isn't very useful, because we need the current owner to kick the *next* owner to life at release time, which we can't do without some structure recording which ticket belongs to which cpu.

If we had a yield-to [1] sort of interface _and_ information on which vcpu owns a lock, then lock-spinners can yield-to the owning vcpu, while the unlocking vcpu can yield-to the next-vcpu-in-waiting.

Perhaps, but the core problem is how to find "next-vcpu-in-waiting" efficiently. Once you have that info, there's a number of things you can usefully do with it.

Quoted 4 lines

The key here is not to
sleep when waiting for locks (as implemented by current patch-series, which can put other VMs at an advantage by giving them more time than they are entitled to)

Why? If a VCPU can't make progress because its waiting for some resource, then why not schedule something else instead? Presumably when the VCPU does become runnable, the scheduler will credit its previous blocked state and let it run in preference to something else.

Quoted 6 lines

and also to ensure that lock-owner as well as the next-in-line lock-owner
are not unduly made to wait for cpu.

Is there a way we can dynamically expand the size of lock only upon contention to include additional information like owning vcpu? Have the lock point to a per-cpu area upon contention where additional details can be stored perhaps?

As soon as you add a pointer to the lock, you're increasing its size. If we had a pointer in there already, then all of this would be moot.

If auxiliary per-lock is uncommon, then using a hash keyed on lock address would be one way to do it.

J

#108 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Srivatsa Vaddagiri
Quoted 7 lines · Srivatsa Vaddagiri
Quoted 4 lines

At least in the Xen code, a current owner isn't very useful, because we need the current owner to kick the *next* owner to life at release time, which we can't do without some structure recording which ticket belongs to which cpu.

If we had a yield-to [1] sort of interface _and_ information on which vcpu owns a lock, then lock-spinners can yield-to the owning vcpu, while the unlocking vcpu can yield-to the next-vcpu-in-waiting.

Perhaps, but the core problem is how to find "next-vcpu-in-waiting" efficiently. Once you have that info, there's a number of things you can usefully do with it.

Quoted 4 lines

The key here is not to
sleep when waiting for locks (as implemented by current patch-series, which can put other VMs at an advantage by giving them more time than they are entitled to)

Why? If a VCPU can't make progress because its waiting for some resource, then why not schedule something else instead? Presumably when the VCPU does become runnable, the scheduler will credit its previous blocked state and let it run in preference to something else.

Quoted 6 lines

and also to ensure that lock-owner as well as the next-in-line lock-owner
are not unduly made to wait for cpu.

Is there a way we can dynamically expand the size of lock only upon contention to include additional information like owning vcpu? Have the lock point to a per-cpu area upon contention where additional details can be stored perhaps?

As soon as you add a pointer to the lock, you're increasing its size. If we had a pointer in there already, then all of this would be moot.

If auxiliary per-lock is uncommon, then using a hash keyed on lock address would be one way to do it.

J

#98 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Jeremy Fitzhardinge
Quoted 7 lines · Jeremy Fitzhardinge
Quoted 4 lines

The key here is not to
sleep when waiting for locks (as implemented by current patch-series, which can put other VMs at an advantage by giving them more time than they are entitled to)

Why? If a VCPU can't make progress because its waiting for some resource, then why not schedule something else instead?

In the process, "something else" can get more share of cpu resource than its entitled to and that's where I was bit concerned. I guess one could employ hard-limits to cap "something else's" bandwidth where it is of real concern (like clouds).

Quoted 3 lines

Presumably when
the VCPU does become runnable, the scheduler will credit its previous blocked state and let it run in preference to something else.

which may not be sufficient for it to gain back bandwidth lost while blocked (speaking of mainline scheduler atleast).

Quoted 5 lines
Quoted 3 lines

Is there a way we can dynamically expand the size of lock only upon contention to include additional information like owning vcpu? Have the lock point to a per-cpu area upon contention where additional details can be stored perhaps?

As soon as you add a pointer to the lock, you're increasing its size.

I didn't really mean to expand size statically. Rather have some bits of the lock word store pointer to a per-cpu area when there is contention (somewhat similar to how bits of rt_mutex.owner are used). I haven't thought thr' this in detail to see if that is possible though.

- vatsa

#107 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Jeremy Fitzhardinge
Quoted 7 lines · Jeremy Fitzhardinge
Quoted 4 lines

The key here is not to
sleep when waiting for locks (as implemented by current patch-series, which can put other VMs at an advantage by giving them more time than they are entitled to)

Why? If a VCPU can't make progress because its waiting for some resource, then why not schedule something else instead?

In the process, "something else" can get more share of cpu resource than its entitled to and that's where I was bit concerned. I guess one could employ hard-limits to cap "something else's" bandwidth where it is of real concern (like clouds).

Quoted 3 lines

Presumably when
the VCPU does become runnable, the scheduler will credit its previous blocked state and let it run in preference to something else.

which may not be sufficient for it to gain back bandwidth lost while blocked (speaking of mainline scheduler atleast).

Quoted 5 lines
Quoted 3 lines

Is there a way we can dynamically expand the size of lock only upon contention to include additional information like owning vcpu? Have the lock point to a per-cpu area upon contention where additional details can be stored perhaps?

As soon as you add a pointer to the lock, you're increasing its size.

I didn't really mean to expand size statically. Rather have some bits of the lock word store pointer to a per-cpu area when there is contention (somewhat similar to how bits of rt_mutex.owner are used). I haven't thought thr' this in detail to see if that is possible though.

- vatsa

#99 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Srivatsa Vaddagiri
Quoted 6 lines · Srivatsa Vaddagiri
Quoted 5 lines · Jeremy Fitzhardinge
Quoted 4 lines

The key here is not to
sleep when waiting for locks (as implemented by current patch-series, which can put other VMs at an advantage by giving them more time than they are entitled to)

Quoted 7 lines
Quoted 2 lines

Why? If a VCPU can't make progress because its waiting for some resource, then why not schedule something else instead?

In the process, "something else" can get more share of cpu resource than its entitled to and that's where I was bit concerned. I guess one could employ hard-limits to cap "something else's" bandwidth where it is of real concern (like clouds).

I'd like to think I fixed those things in my yield_task_fair + yield_to + kvm_vcpu_on_spin patch series from yesterday.

https://lkml.org/lkml/2011/1/20/403

Signature · 1 line
All rights reversed
#106 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Srivatsa Vaddagiri
Quoted 6 lines · Srivatsa Vaddagiri
Quoted 5 lines · Jeremy Fitzhardinge
Quoted 4 lines

The key here is not to
sleep when waiting for locks (as implemented by current patch-series, which can put other VMs at an advantage by giving them more time than they are entitled to)

Quoted 7 lines
Quoted 2 lines

Why? If a VCPU can't make progress because its waiting for some resource, then why not schedule something else instead?

In the process, "something else" can get more share of cpu resource than its entitled to and that's where I was bit concerned. I guess one could employ hard-limits to cap "something else's" bandwidth where it is of real concern (like clouds).

I'd like to think I fixed those things in my yield_task_fair + yield_to + kvm_vcpu_on_spin patch series from yesterday.

https://lkml.org/lkml/2011/1/20/403

Signature · 1 line
All rights reversed
#100 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Rik van Riel
Quoted 10 lines · Rik van Riel
Quoted 7 lines
Quoted 2 lines

Why? If a VCPU can't make progress because its waiting for some resource, then why not schedule something else instead?

In the process, "something else" can get more share of cpu resource than its entitled to and that's where I was bit concerned. I guess one could employ hard-limits to cap "something else's" bandwidth where it is of real concern (like clouds).

I'd like to think I fixed those things in my yield_task_fair + yield_to + kvm_vcpu_on_spin patch series from yesterday.

Speaking of the spinlock-in-virtualized-environment problem as whole, IMHO I don't think that kvm_vcpu_on_spin + yield changes will provide the best results, especially where ticketlocks are involved and they are paravirtualized in a manner being discussed in this thread. An important focus of pv-ticketlocks is to reduce the lock _acquisition_ time by ensuring that the next-in-line vcpu gets to run asap when a ticket lock is released. With the way kvm_vcpu_on_spin+yield_to is implemented, I don't see how we can provide the best lock acquisition times for threads. It would be nice though to compare the two approaches (kvm_vcpu_on_spin optimization and the pv-ticketlock scheme) to get some real-world numbers. I unfortunately don't have access to a PLE capable hardware which is required to test your kvm_vcpu_on_spin changes?

Also it may be possible for the pv-ticketlocks to track owning vcpu and make use of a yield-to interface as further optimization to avoid the "others-get-more-time" problem, but Peterz rightly pointed that PI would be a better solution there than yield-to. So overall IMO kvm_vcpu_on_spin+yield_to could be the best solution for unmodified guests, while paravirtualized ticketlocks + some sort of PI would be a better solution where we have the luxury of modifying guest sources!

- vatsa

#105 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Rik van Riel
Quoted 10 lines · Rik van Riel
Quoted 7 lines
Quoted 2 lines

Why? If a VCPU can't make progress because its waiting for some resource, then why not schedule something else instead?

In the process, "something else" can get more share of cpu resource than its entitled to and that's where I was bit concerned. I guess one could employ hard-limits to cap "something else's" bandwidth where it is of real concern (like clouds).

I'd like to think I fixed those things in my yield_task_fair + yield_to + kvm_vcpu_on_spin patch series from yesterday.

Speaking of the spinlock-in-virtualized-environment problem as whole, IMHO I don't think that kvm_vcpu_on_spin + yield changes will provide the best results, especially where ticketlocks are involved and they are paravirtualized in a manner being discussed in this thread. An important focus of pv-ticketlocks is to reduce the lock _acquisition_ time by ensuring that the next-in-line vcpu gets to run asap when a ticket lock is released. With the way kvm_vcpu_on_spin+yield_to is implemented, I don't see how we can provide the best lock acquisition times for threads. It would be nice though to compare the two approaches (kvm_vcpu_on_spin optimization and the pv-ticketlock scheme) to get some real-world numbers. I unfortunately don't have access to a PLE capable hardware which is required to test your kvm_vcpu_on_spin changes?

Also it may be possible for the pv-ticketlocks to track owning vcpu and make use of a yield-to interface as further optimization to avoid the "others-get-more-time" problem, but Peterz rightly pointed that PI would be a better solution there than yield-to. So overall IMO kvm_vcpu_on_spin+yield_to could be the best solution for unmodified guests, while paravirtualized ticketlocks + some sort of PI would be a better solution where we have the luxury of modifying guest sources!

- vatsa

#101 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Srivatsa Vaddagiri
Quoted 7 lines · Srivatsa Vaddagiri

Also it may be possible for the pv-ticketlocks to track owning vcpu and make use of a yield-to interface as further optimization to avoid the "others-get-more-time" problem, but Peterz rightly pointed that PI would be a better solution there than yield-to. So overall IMO kvm_vcpu_on_spin+yield_to could be the best solution for unmodified guests, while paravirtualized ticketlocks + some sort of PI would be a better solution where we have the luxury of modifying guest sources!

Agreed, for unmodified guests (which is what people will mostly be running for the next couple of years), we have little choice but to use PLE + kvm_vcpu_on_spin + yield_to.

The main question that remains is whether the PV ticketlocks are a large enough improvement to also merge those. I expect they will be, and we'll see so in the benchmark numbers.

Signature · 1 line
All rights reversed
#104 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Srivatsa Vaddagiri
Quoted 7 lines · Srivatsa Vaddagiri

Also it may be possible for the pv-ticketlocks to track owning vcpu and make use of a yield-to interface as further optimization to avoid the "others-get-more-time" problem, but Peterz rightly pointed that PI would be a better solution there than yield-to. So overall IMO kvm_vcpu_on_spin+yield_to could be the best solution for unmodified guests, while paravirtualized ticketlocks + some sort of PI would be a better solution where we have the luxury of modifying guest sources!

Agreed, for unmodified guests (which is what people will mostly be running for the next couple of years), we have little choice but to use PLE + kvm_vcpu_on_spin + yield_to.

The main question that remains is whether the PV ticketlocks are a large enough improvement to also merge those. I expect they will be, and we'll see so in the benchmark numbers.

Signature · 1 line
All rights reversed
#102 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Rik van Riel
Quoted 3 lines · Rik van Riel

The main question that remains is whether the PV ticketlocks are a large enough improvement to also merge those. I expect they will be, and we'll see so in the benchmark numbers.

The pathological worst-case of ticket locks in a virtual environment isn't very hard to hit, so I expect they'll make a huge difference
there. On lightly loaded systems (little or no CPU overcommit) then
they should be close to a no-op.

J

#103 lore raw

Re: [PATCH 2/3] kvm hypervisor : Add hypercalls to support pv-ticketlock

In reply to Rik van Riel
Quoted 3 lines · Rik van Riel

The main question that remains is whether the PV ticketlocks are a large enough improvement to also merge those. I expect they will be, and we'll see so in the benchmark numbers.

The pathological worst-case of ticket locks in a virtual environment isn't very hard to hit, so I expect they'll make a huge difference
there. On lightly loaded systems (little or no CPU overcommit) then
they should be close to a no-op.

J

#59 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Srivatsa Vaddagiri
Quoted 87 lines · Srivatsa Vaddagiri
Quoted 14 lines · Srivatsa Vaddagiri

I think this is still racy ..

Unlocker Locker

test slowpath

	-> false
		
				set slowpath flag
				test for lock pickup
					-> fail
				block
Quoted 5 lines

unlock

unlock needs to happen first before testing slowpath? I have made that change for my KVM guest and it seems to be working well with that change .. Will cleanup and post my patches shortly

Patch below fixes the race described above. You can fold this to your patch 13/14 if you agree this is in right direction.

---
 arch/x86/include/asm/spinlock.h      |    7 +++----
 arch/x86/kernel/paravirt-spinlocks.c |   22 +++++-----------------
 2 files changed, 8 insertions(+), 21 deletions(-)

Index: linux-2.6.37/arch/x86/include/asm/spinlock.h
===================================================================

arch/x86/include/asm/spinlock.h +3 -4
@@ -55,7 +55,7 @@ static __always_inline void __ticket_unl
 
 /* Only defined when CONFIG_PARAVIRT_SPINLOCKS defined, but may as
  * well leave the prototype always visible.  */
-extern void __ticket_unlock_release_slowpath(struct arch_spinlock *lock);
+extern void __ticket_unlock_slowpath(struct arch_spinlock *lock);
 
 #ifdef CONFIG_PARAVIRT_SPINLOCKS
 
@@ -166,10 +166,9 @@ static __always_inline int arch_spin_try
 static __always_inline void arch_spin_unlock(arch_spinlock_t *lock)
 {
 	barrier();		/* prevent reordering out of locked region */
+	__ticket_unlock_release(lock);
 	if (unlikely(__ticket_in_slowpath(lock)))
-		__ticket_unlock_release_slowpath(lock);
-	else
-		__ticket_unlock_release(lock);
+		__ticket_unlock_slowpath(lock);
 	barrier();		/* prevent reordering into locked region */
 }
 

Index: linux-2.6.37/arch/x86/kernel/paravirt-spinlocks.c
===================================================================

arch/x86/kernel/paravirt-spinlocks.c +3 -8
@@ -22,33 +22,21 @@ EXPORT_SYMBOL(pv_lock_ops);
  * bits.  However, we need to be careful about this because someone
  * may just be entering as we leave, and enter the slowpath.
  */
-void __ticket_unlock_release_slowpath(struct arch_spinlock *lock)
+void __ticket_unlock_slowpath(struct arch_spinlock *lock)
 {
 	struct arch_spinlock old, new;
 
 	BUILD_BUG_ON(((__ticket_t)NR_CPUS) != NR_CPUS);
 
 	old = ACCESS_ONCE(*lock);
-
 	new = old;
-	new.tickets.head += TICKET_LOCK_INC;
 
 	/* Clear the slowpath flag */
 	new.tickets.tail &= ~TICKET_SLOWPATH_FLAG;
+	if (new.tickets.head == new.tickets.tail)
+		cmpxchg(&lock->head_tail, old.head_tail, new.head_tail);
 
-	/*
-	 * If there's currently people waiting or someone snuck in
-	 * since we read the lock above, then do a normal unlock and
-	 * kick.  If we managed to unlock with no queued waiters, then
-	 * we can clear the slowpath flag.

arch/x86/kernel/paravirt-spinlocks.c EXPORT_SYMBOL(pv_lock_ops); · line 40

Quoted 10 lines
arch/x86/kernel/paravirt-spinlocks.c +1 -8
-	 */
-	if (new.tickets.head != new.tickets.tail ||
-	    cmpxchg(&lock->head_tail,
-		    old.head_tail, new.head_tail) != old.head_tail) {
-		/* still people waiting */
-		__ticket_unlock_release(lock);
-	}
-
+	/* Wake up an appropriate waiter */
 	__ticket_unlock_kick(lock, new.tickets.head);

Does the __ticket_unlock_kick need to be unconditional? If the cmpxchg() fails, then it means someone else has come in and changed the lock under our feet, and presumably they'll do the kick as needed?

Or is there the possibility that the kick will get lost?

There's certainly no harm in doing a redundant kick, and I'd expect that case to be pretty rare...

J

#62 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Srivatsa Vaddagiri
Quoted 87 lines · Srivatsa Vaddagiri
Quoted 14 lines · Srivatsa Vaddagiri

I think this is still racy ..

Unlocker Locker

test slowpath

	-> false
		
				set slowpath flag
				test for lock pickup
					-> fail
				block
Quoted 5 lines

unlock

unlock needs to happen first before testing slowpath? I have made that change for my KVM guest and it seems to be working well with that change .. Will cleanup and post my patches shortly

Patch below fixes the race described above. You can fold this to your patch 13/14 if you agree this is in right direction.

---
 arch/x86/include/asm/spinlock.h      |    7 +++----
 arch/x86/kernel/paravirt-spinlocks.c |   22 +++++-----------------
 2 files changed, 8 insertions(+), 21 deletions(-)

Index: linux-2.6.37/arch/x86/include/asm/spinlock.h
===================================================================

arch/x86/include/asm/spinlock.h +3 -4
@@ -55,7 +55,7 @@ static __always_inline void __ticket_unl
 
 /* Only defined when CONFIG_PARAVIRT_SPINLOCKS defined, but may as
  * well leave the prototype always visible.  */
-extern void __ticket_unlock_release_slowpath(struct arch_spinlock *lock);
+extern void __ticket_unlock_slowpath(struct arch_spinlock *lock);
 
 #ifdef CONFIG_PARAVIRT_SPINLOCKS
 
@@ -166,10 +166,9 @@ static __always_inline int arch_spin_try
 static __always_inline void arch_spin_unlock(arch_spinlock_t *lock)
 {
 	barrier();		/* prevent reordering out of locked region */
+	__ticket_unlock_release(lock);
 	if (unlikely(__ticket_in_slowpath(lock)))
-		__ticket_unlock_release_slowpath(lock);
-	else
-		__ticket_unlock_release(lock);
+		__ticket_unlock_slowpath(lock);
 	barrier();		/* prevent reordering into locked region */
 }
 

Index: linux-2.6.37/arch/x86/kernel/paravirt-spinlocks.c
===================================================================

arch/x86/kernel/paravirt-spinlocks.c +3 -8
@@ -22,33 +22,21 @@ EXPORT_SYMBOL(pv_lock_ops);
  * bits.  However, we need to be careful about this because someone
  * may just be entering as we leave, and enter the slowpath.
  */
-void __ticket_unlock_release_slowpath(struct arch_spinlock *lock)
+void __ticket_unlock_slowpath(struct arch_spinlock *lock)
 {
 	struct arch_spinlock old, new;
 
 	BUILD_BUG_ON(((__ticket_t)NR_CPUS) != NR_CPUS);
 
 	old = ACCESS_ONCE(*lock);
-
 	new = old;
-	new.tickets.head += TICKET_LOCK_INC;
 
 	/* Clear the slowpath flag */
 	new.tickets.tail &= ~TICKET_SLOWPATH_FLAG;
+	if (new.tickets.head == new.tickets.tail)
+		cmpxchg(&lock->head_tail, old.head_tail, new.head_tail);
 
-	/*
-	 * If there's currently people waiting or someone snuck in
-	 * since we read the lock above, then do a normal unlock and
-	 * kick.  If we managed to unlock with no queued waiters, then
-	 * we can clear the slowpath flag.

arch/x86/kernel/paravirt-spinlocks.c EXPORT_SYMBOL(pv_lock_ops); · line 40

Quoted 10 lines
arch/x86/kernel/paravirt-spinlocks.c +1 -8
-	 */
-	if (new.tickets.head != new.tickets.tail ||
-	    cmpxchg(&lock->head_tail,
-		    old.head_tail, new.head_tail) != old.head_tail) {
-		/* still people waiting */
-		__ticket_unlock_release(lock);
-	}
-
+	/* Wake up an appropriate waiter */
 	__ticket_unlock_kick(lock, new.tickets.head);

Does the __ticket_unlock_kick need to be unconditional? If the cmpxchg() fails, then it means someone else has come in and changed the lock under our feet, and presumably they'll do the kick as needed?

Or is there the possibility that the kick will get lost?

There's certainly no harm in doing a redundant kick, and I'd expect that case to be pretty rare...

J

#60 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge
Quoted 1 line · Jeremy Fitzhardinge

For some reason, I seem to be missing emails from your id/domain and hence had missed this completely!

Quoted 29 lines
Quoted 29 lines

* bits. However, we need to be careful about this because someone
* may just be entering as we leave, and enter the slowpath. */

arch/x86/kernel/paravirt-spinlocks.c +3 -12
-void __ticket_unlock_release_slowpath(struct arch_spinlock *lock)
+void __ticket_unlock_slowpath(struct arch_spinlock *lock)
 {
 	struct arch_spinlock old, new;
 
 	BUILD_BUG_ON(((__ticket_t)NR_CPUS) != NR_CPUS);
 
 	old = ACCESS_ONCE(*lock);
-
 	new = old;
-	new.tickets.head += TICKET_LOCK_INC;
 
 	/* Clear the slowpath flag */
 	new.tickets.tail &= ~TICKET_SLOWPATH_FLAG;
+	if (new.tickets.head == new.tickets.tail)
+		cmpxchg(&lock->head_tail, old.head_tail, new.head_tail);
 
-	/*
-	 * If there's currently people waiting or someone snuck in
-	 * since we read the lock above, then do a normal unlock and
-	 * kick.  If we managed to unlock with no queued waiters, then
-	 * we can clear the slowpath flag.
-	 */
-	if (new.tickets.head != new.tickets.tail ||
-	    cmpxchg(&lock->head_tail,
-		    old.head_tail, new.head_tail) != old.head_tail) {
Quoted 8 lines

arch/x86/kernel/paravirt-spinlocks.c EXPORT_SYMBOL(pv_lock_ops); · line 40

Quoted 6 lines
arch/x86/kernel/paravirt-spinlocks.c +1 -4
-		/* still people waiting */
-		__ticket_unlock_release(lock);
-	}
-
+	/* Wake up an appropriate waiter */
 	__ticket_unlock_kick(lock, new.tickets.head);

Does the __ticket_unlock_kick need to be unconditional?

I recall having tried optimizing it to be conditional, something along these lines:

	if (new.ticket.head == new.tickets.tail) {
		cmpxchg();	
	} else {
		__ticket_unlock_kick(lock, new.tickets.head);
	}

but it didn't work for some reason. I left the call unconditional as was the case previously based on that experiment.

- vatsa

#61 lore raw

Re: [PATCH 13/14] x86/ticketlock: add slowpath logic

In reply to Jeremy Fitzhardinge
Quoted 1 line · Jeremy Fitzhardinge

For some reason, I seem to be missing emails from your id/domain and hence had missed this completely!

Quoted 29 lines
Quoted 29 lines

* bits. However, we need to be careful about this because someone
* may just be entering as we leave, and enter the slowpath. */

arch/x86/kernel/paravirt-spinlocks.c +3 -12
-void __ticket_unlock_release_slowpath(struct arch_spinlock *lock)
+void __ticket_unlock_slowpath(struct arch_spinlock *lock)
 {
 	struct arch_spinlock old, new;
 
 	BUILD_BUG_ON(((__ticket_t)NR_CPUS) != NR_CPUS);
 
 	old = ACCESS_ONCE(*lock);
-
 	new = old;
-	new.tickets.head += TICKET_LOCK_INC;
 
 	/* Clear the slowpath flag */
 	new.tickets.tail &= ~TICKET_SLOWPATH_FLAG;
+	if (new.tickets.head == new.tickets.tail)
+		cmpxchg(&lock->head_tail, old.head_tail, new.head_tail);
 
-	/*
-	 * If there's currently people waiting or someone snuck in
-	 * since we read the lock above, then do a normal unlock and
-	 * kick.  If we managed to unlock with no queued waiters, then
-	 * we can clear the slowpath flag.
-	 */
-	if (new.tickets.head != new.tickets.tail ||
-	    cmpxchg(&lock->head_tail,
-		    old.head_tail, new.head_tail) != old.head_tail) {
Quoted 8 lines

arch/x86/kernel/paravirt-spinlocks.c EXPORT_SYMBOL(pv_lock_ops); · line 40

Quoted 6 lines
arch/x86/kernel/paravirt-spinlocks.c +1 -4
-		/* still people waiting */
-		__ticket_unlock_release(lock);
-	}
-
+	/* Wake up an appropriate waiter */
 	__ticket_unlock_kick(lock, new.tickets.head);

Does the __ticket_unlock_kick need to be unconditional?

I recall having tried optimizing it to be conditional, something along these lines:

	if (new.ticket.head == new.tickets.tail) {
		cmpxchg();	
	} else {
		__ticket_unlock_kick(lock, new.tickets.head);
	}

but it didn't work for some reason. I left the call unconditional as was the case previously based on that experiment.

- vatsa