[PATCH 00/14] PV ticket locks without expanding spinlock

[PATCH 00/14] PV ticket locks without expanding spinlock

[Jeremy Fitzhardinge]

From: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>

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

-- 
1.7.2.3

[PATCH 01/14] x86/ticketlock: clean up types and accessors

[Jeremy Fitzhardinge]

From: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>

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.

Signed-off-by: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>
---
 arch/x86/include/asm/spinlock.h       |   24 ++++++++++--------------
 arch/x86/include/asm/spinlock_types.h |   20 ++++++++++++++++++--
 2 files changed, 28 insertions(+), 16 deletions(-)

diff --git a/arch/x86/include/asm/spinlock.h b/arch/x86/include/asm/spinlock.h
index 3089f70..d6d5784 100644
--- a/arch/x86/include/asm/spinlock.h
+++ b/arch/x86/include/asm/spinlock.h
@@ -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
diff --git a/arch/x86/include/asm/spinlock_types.h b/arch/x86/include/asm/spinlock_types.h
index dcb48b2..e3ad1e3 100644
--- a/arch/x86/include/asm/spinlock_types.h
+++ b/arch/x86/include/asm/spinlock_types.h
@@ -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;
-- 
1.7.2.3

[PATCH 02/14] x86/ticketlock: convert spin loop to C

[Jeremy Fitzhardinge]

From: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>

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.

Signed-off-by: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>
---
 arch/x86/include/asm/spinlock.h |   58 +++++++++++++++++++-------------------
 1 files changed, 29 insertions(+), 29 deletions(-)

diff --git a/arch/x86/include/asm/spinlock.h b/arch/x86/include/asm/spinlock.h
index d6d5784..f48a6e3 100644
--- a/arch/x86/include/asm/spinlock.h
+++ b/arch/x86/include/asm/spinlock.h
@@ -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)
-- 
1.7.2.3

[PATCH 03/14] x86/ticketlock: Use C for __ticket_spin_unlock

[Jeremy Fitzhardinge]

From: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>

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

Signed-off-by: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>
---
 arch/x86/include/asm/spinlock.h |   32 +++++++++++++++++---------------
 1 files changed, 17 insertions(+), 15 deletions(-)

diff --git a/arch/x86/include/asm/spinlock.h b/arch/x86/include/asm/spinlock.h
index f48a6e3..0170ba9 100644
--- a/arch/x86/include/asm/spinlock.h
+++ b/arch/x86/include/asm/spinlock.h
@@ -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)
 {
-- 
1.7.2.3

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

[Jeremy Fitzhardinge]

From: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>

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

Signed-off-by: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>
---
 arch/x86/include/asm/spinlock.h |   23 ++++++++---------------
 1 files changed, 8 insertions(+), 15 deletions(-)

diff --git a/arch/x86/include/asm/spinlock.h b/arch/x86/include/asm/spinlock.h
index 0170ba9..1b81809 100644
--- a/arch/x86/include/asm/spinlock.h
+++ b/arch/x86/include/asm/spinlock.h
@@ -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 */
 }
-- 
1.7.2.3

[PATCH 05/14] x86/ticketlock: make __ticket_spin_lock common

[Jeremy Fitzhardinge]

From: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>

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

Signed-off-by: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>
---
 arch/x86/include/asm/spinlock.h |   42 ++++++++++++++++++--------------------
 1 files changed, 20 insertions(+), 22 deletions(-)

diff --git a/arch/x86/include/asm/spinlock.h b/arch/x86/include/asm/spinlock.h
index 1b81809..f722f96 100644
--- a/arch/x86/include/asm/spinlock.h
+++ b/arch/x86/include/asm/spinlock.h
@@ -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;
-- 
1.7.2.3

[PATCH 06/14] x86/ticketlock: make __ticket_spin_trylock common

[Jeremy Fitzhardinge]

From: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>

Make trylock code common regardless of ticket size.

Signed-off-by: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>
---
 arch/x86/include/asm/spinlock.h       |   49 +++++++--------------------------
 arch/x86/include/asm/spinlock_types.h |    6 +++-
 2 files changed, 14 insertions(+), 41 deletions(-)

diff --git a/arch/x86/include/asm/spinlock.h b/arch/x86/include/asm/spinlock.h
index f722f96..3afb1a7 100644
--- a/arch/x86/include/asm/spinlock.h
+++ b/arch/x86/include/asm/spinlock.h
@@ -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)
 {
diff --git a/arch/x86/include/asm/spinlock_types.h b/arch/x86/include/asm/spinlock_types.h
index e3ad1e3..72e154e 100644
--- a/arch/x86/include/asm/spinlock_types.h
+++ b/arch/x86/include/asm/spinlock_types.h
@@ -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;
-- 
1.7.2.3

[PATCH 07/14] x86/spinlocks: replace pv spinlocks with pv ticketlocks

[Jeremy Fitzhardinge]

From: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>

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.

Signed-off-by: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>
---
 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(-)

diff --git a/arch/x86/include/asm/paravirt.h b/arch/x86/include/asm/paravirt.h
index 18e3b8a..c864775 100644
--- a/arch/x86/include/asm/paravirt.h
+++ b/arch/x86/include/asm/paravirt.h
@@ -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
diff --git a/arch/x86/include/asm/paravirt_types.h b/arch/x86/include/asm/paravirt_types.h
index b82bac9..1078474 100644
--- a/arch/x86/include/asm/paravirt_types.h
+++ b/arch/x86/include/asm/paravirt_types.h
@@ -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
diff --git a/arch/x86/include/asm/spinlock.h b/arch/x86/include/asm/spinlock.h
index 3afb1a7..8e379d3 100644
--- a/arch/x86/include/asm/spinlock.h
+++ b/arch/x86/include/asm/spinlock.h
@@ -50,6 +50,21 @@ static __always_inline void __ticket_unlock_release(struct arch_spinlock *lock)
 }
 #endif
 
+/* How long a lock should spin before we consider blocking */
+#define SPIN_THRESHOLD	(1 << 11)
+
+#ifndef CONFIG_PARAVIRT_SPINLOCKS
+
+static __always_inline void __ticket_lock_spinning(struct arch_spinlock *lock, unsigned ticket)
+{
+}
+
+static __always_inline void ____ticket_unlock_kick(struct arch_spinlock *lock, unsigned ticket)
+{
+}
+
+#endif	/* CONFIG_PARAVIRT_SPINLOCKS */
+
 /*
  * Ticket locks are conceptually two parts, one indicating the current head of
  * the queue, and the other indicating the current tail. The lock is acquired
@@ -83,6 +98,16 @@ static __always_inline struct __raw_tickets __ticket_spin_claim(struct arch_spin
 	return 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 __ticket_spin_lock(struct arch_spinlock *lock)
 {
 	register struct __raw_tickets inc;
@@ -90,10 +115,15 @@ static __always_inline void __ticket_spin_lock(struct arch_spinlock *lock)
 	inc = __ticket_spin_claim(lock);
 
 	for (;;) {
-		if (inc.head == inc.tail)
-			goto out;
-		cpu_relax();
-		inc.head = ACCESS_ONCE(lock->tickets.head);
+		unsigned count = SPIN_THRESHOLD;
+
+		do {
+			if (inc.head == inc.tail)
+				goto out;
+			cpu_relax();
+			inc.head = ACCESS_ONCE(lock->tickets.head);
+		} while (--count);
+		__ticket_lock_spinning(lock, inc.tail);
 	}
 out:	barrier();		/* make sure nothing creeps before the lock is taken */
 }
@@ -114,7 +144,9 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 
 static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
 {
+	__ticket_t next = lock->tickets.head + 1;
 	__ticket_unlock_release(lock);
+	__ticket_unlock_kick(lock, next);
 	barrier();		/* prevent reordering into locked region */
 }
 
@@ -132,8 +164,6 @@ static inline int __ticket_spin_is_contended(arch_spinlock_t *lock)
 	return ((tmp.tail - tmp.head) & TICKET_MASK) > 1;
 }
 
-#ifndef CONFIG_PARAVIRT_SPINLOCKS
-
 static inline int arch_spin_is_locked(arch_spinlock_t *lock)
 {
 	return __ticket_spin_is_locked(lock);
@@ -166,8 +196,6 @@ static __always_inline void arch_spin_lock_flags(arch_spinlock_t *lock,
 	arch_spin_lock(lock);
 }
 
-#endif	/* CONFIG_PARAVIRT_SPINLOCKS */
-
 static inline void arch_spin_unlock_wait(arch_spinlock_t *lock)
 {
 	while (arch_spin_is_locked(lock))
diff --git a/arch/x86/kernel/paravirt-spinlocks.c b/arch/x86/kernel/paravirt-spinlocks.c
index 676b8c7..c2e010e 100644
--- a/arch/x86/kernel/paravirt-spinlocks.c
+++ b/arch/x86/kernel/paravirt-spinlocks.c
@@ -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);
diff --git a/arch/x86/xen/spinlock.c b/arch/x86/xen/spinlock.c
index 23e061b..3d9da72 100644
--- a/arch/x86/xen/spinlock.c
+++ b/arch/x86/xen/spinlock.c
@@ -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
-- 
1.7.2.3

[PATCH 08/14] x86/ticketlock: collapse a layer of functions

[Jeremy Fitzhardinge]

From: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>

Now that the paravirtualization layer doesn't exist at the spinlock
level any more, we can collapse the __ticket_ functions into the arch_
functions.

Signed-off-by: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>
---
 arch/x86/include/asm/spinlock.h |   35 +++++------------------------------
 1 files changed, 5 insertions(+), 30 deletions(-)

diff --git a/arch/x86/include/asm/spinlock.h b/arch/x86/include/asm/spinlock.h
index 8e379d3..cfa80b5 100644
--- a/arch/x86/include/asm/spinlock.h
+++ b/arch/x86/include/asm/spinlock.h
@@ -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)
 {
-- 
1.7.2.3

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

[Jeremy Fitzhardinge]

From: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>

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.

Signed-off-by: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>
---
 arch/x86/xen/spinlock.c |  281 ++++++-----------------------------------------
 1 files changed, 36 insertions(+), 245 deletions(-)

diff --git a/arch/x86/xen/spinlock.c b/arch/x86/xen/spinlock.c
index 3d9da72..5feb897 100644
--- a/arch/x86/xen/spinlock.c
+++ b/arch/x86/xen/spinlock.c
@@ -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);
 
-- 
1.7.2.3

[PATCH 10/14] x86/pvticketlock: use callee-save for lock_spinning

[Jeremy Fitzhardinge]

From: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>

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.

Signed-off-by: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>
---
 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(-)

diff --git a/arch/x86/include/asm/paravirt.h b/arch/x86/include/asm/paravirt.h
index c864775..6f275ca 100644
--- a/arch/x86/include/asm/paravirt.h
+++ b/arch/x86/include/asm/paravirt.h
@@ -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)
diff --git a/arch/x86/include/asm/paravirt_types.h b/arch/x86/include/asm/paravirt_types.h
index 1078474..53f249a 100644
--- a/arch/x86/include/asm/paravirt_types.h
+++ b/arch/x86/include/asm/paravirt_types.h
@@ -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);
 };
 
diff --git a/arch/x86/kernel/paravirt-spinlocks.c b/arch/x86/kernel/paravirt-spinlocks.c
index c2e010e..4251c1d 100644
--- a/arch/x86/kernel/paravirt-spinlocks.c
+++ b/arch/x86/kernel/paravirt-spinlocks.c
@@ -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
 };
diff --git a/arch/x86/xen/spinlock.c b/arch/x86/xen/spinlock.c
index 5feb897..c31c5a3 100644
--- a/arch/x86/xen/spinlock.c
+++ b/arch/x86/xen/spinlock.c
@@ -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;
 }
 
-- 
1.7.2.3

[PATCH 11/14] x86/ticketlock: don't inline _spin_unlock when using paravirt spinlocks

[Jeremy Fitzhardinge]

From: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>

The code size expands somewhat, and its probably better to just call
a function rather than inline it.

Signed-off-by: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>
---
 arch/x86/Kconfig     |    3 +++
 kernel/Kconfig.locks |    2 +-
 2 files changed, 4 insertions(+), 1 deletions(-)

diff --git a/arch/x86/Kconfig b/arch/x86/Kconfig
index e832768..a615c9c 100644
--- a/arch/x86/Kconfig
+++ b/arch/x86/Kconfig
@@ -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
 
diff --git a/kernel/Kconfig.locks b/kernel/Kconfig.locks
index 88c92fb..3216c22 100644
--- a/kernel/Kconfig.locks
+++ b/kernel/Kconfig.locks
@@ -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
-- 
1.7.2.3

[PATCH 12/14] x86/ticketlocks: when paravirtualizing ticket locks, increment by 2

[Jeremy Fitzhardinge]

From: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>

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.

Signed-off-by: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>
---
 arch/x86/include/asm/spinlock.h       |   18 +++++++++---------
 arch/x86/include/asm/spinlock_types.h |   10 +++++++++-
 2 files changed, 18 insertions(+), 10 deletions(-)

diff --git a/arch/x86/include/asm/spinlock.h b/arch/x86/include/asm/spinlock.h
index cfa80b5..9e1c7ce 100644
--- a/arch/x86/include/asm/spinlock.h
+++ b/arch/x86/include/asm/spinlock.h
@@ -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
 
diff --git a/arch/x86/include/asm/spinlock_types.h b/arch/x86/include/asm/spinlock_types.h
index 72e154e..0553c0b 100644
--- a/arch/x86/include/asm/spinlock_types.h
+++ b/arch/x86/include/asm/spinlock_types.h
@@ -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))
 
-- 
1.7.2.3

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

[Jeremy Fitzhardinge]

From: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>

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

Signed-off-by: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>
---
 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(-)

diff --git a/arch/x86/include/asm/spinlock.h b/arch/x86/include/asm/spinlock.h
index 9e1c7ce..8d1cb42 100644
--- a/arch/x86/include/asm/spinlock.h
+++ b/arch/x86/include/asm/spinlock.h
@@ -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 */
 }
 
diff --git a/arch/x86/include/asm/spinlock_types.h b/arch/x86/include/asm/spinlock_types.h
index 0553c0b..7b383e2 100644
--- a/arch/x86/include/asm/spinlock_types.h
+++ b/arch/x86/include/asm/spinlock_types.h
@@ -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))
diff --git a/arch/x86/kernel/paravirt-spinlocks.c b/arch/x86/kernel/paravirt-spinlocks.c
index 4251c1d..21b6986 100644
--- a/arch/x86/kernel/paravirt-spinlocks.c
+++ b/arch/x86/kernel/paravirt-spinlocks.c
@@ -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);
diff --git a/arch/x86/xen/spinlock.c b/arch/x86/xen/spinlock.c
index c31c5a3..91f2fd2 100644
--- a/arch/x86/xen/spinlock.c
+++ b/arch/x86/xen/spinlock.c
@@ -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) {
-- 
1.7.2.3

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

[Jeremy Fitzhardinge]

From: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>

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

Signed-off-by: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>
---
 arch/x86/include/asm/paravirt.h |    2 +-
 arch/x86/include/asm/spinlock.h |   14 --------------
 2 files changed, 1 insertions(+), 15 deletions(-)

diff --git a/arch/x86/include/asm/paravirt.h b/arch/x86/include/asm/paravirt.h
index 6f275ca..7755b16 100644
--- a/arch/x86/include/asm/paravirt.h
+++ b/arch/x86/include/asm/paravirt.h
@@ -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);
 }
diff --git a/arch/x86/include/asm/spinlock.h b/arch/x86/include/asm/spinlock.h
index 8d1cb42..70675bc 100644
--- a/arch/x86/include/asm/spinlock.h
+++ b/arch/x86/include/asm/spinlock.h
@@ -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;
-- 
1.7.2.3

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

[Jan Beulich]

>>> On 16.11.10 at 22:08, Jeremy Fitzhardinge <jeremy@goop.org> wrote:
> +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);

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

Jan

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

[Jan Beulich]

>>> On 16.11.10 at 22:08, Jeremy Fitzhardinge <jeremy@goop.org> wrote:
> +static inline void __ticket_enter_slowpath(struct arch_spinlock *lock)
> +{
> +	if (sizeof(lock->tickets.tail) == sizeof(u8))
> +		asm (LOCK_PREFIX "orb %1, %0"
> +		     : "+m" (lock->tickets.tail)
> +		     : "i" (TICKET_SLOWPATH_FLAG) : "memory");
> +	else
> +		asm (LOCK_PREFIX "orw %1, %0"
> +		     : "+m" (lock->tickets.tail)
> +		     : "i" (TICKET_SLOWPATH_FLAG) : "memory");
> +}

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

Jan

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

[Jeremy Fitzhardinge]

On 11/17/2010 12:31 AM, Jan Beulich wrote:
>>>> On 16.11.10 at 22:08, Jeremy Fitzhardinge <jeremy@goop.org> wrote:
>> +static inline void __ticket_enter_slowpath(struct arch_spinlock *lock)
>> +{
>> +	if (sizeof(lock->tickets.tail) == sizeof(u8))
>> +		asm (LOCK_PREFIX "orb %1, %0"
>> +		     : "+m" (lock->tickets.tail)
>> +		     : "i" (TICKET_SLOWPATH_FLAG) : "memory");
>> +	else
>> +		asm (LOCK_PREFIX "orw %1, %0"
>> +		     : "+m" (lock->tickets.tail)
>> +		     : "i" (TICKET_SLOWPATH_FLAG) : "memory");
>> +}
> Came only now to mind: Here and elsewhere, did you try using
> %z0 to have gcc produce the opcode suffix character, rather
> than having these somewhat ugly if()-s?

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

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

Thanks,
    J

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

[Jeremy Fitzhardinge]

On 11/17/2010 12:11 AM, Jan Beulich wrote:
>>>> On 16.11.10 at 22:08, Jeremy Fitzhardinge <jeremy@goop.org> wrote:
>> +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);
> Since you don't allow nesting, don't you need to disable
> interrupts before you touch per-CPU state?

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

    J

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

[Jeremy Fitzhardinge]

On 11/17/2010 12:52 AM, Jeremy Fitzhardinge wrote:
> But, yes, %z0 sounds interesting.  Is it documented anywhere?  I think
> I've tried to use it in the past and run into gcc bugs.
This one: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39590

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

    J

Re: [PATCH 00/14] PV ticket locks without expanding spinlock

[Avi Kivity]

On 11/16/2010 11:08 PM, Jeremy Fitzhardinge wrote:
> From: Jeremy Fitzhardinge<jeremy.fitzhardinge@citrix.com>
>
> 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.

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

-- 
error compiling committee.c: too many arguments to function

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

[Avi Kivity]

On 11/17/2010 10:52 AM, Jeremy Fitzhardinge wrote:
> On 11/17/2010 12:31 AM, Jan Beulich wrote:
> >>>>  On 16.11.10 at 22:08, Jeremy Fitzhardinge<jeremy@goop.org>  wrote:
> >>  +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...
>

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.

-- 
error compiling committee.c: too many arguments to function

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

[Jeremy Fitzhardinge]

On 11/17/2010 12:58 AM, Avi Kivity wrote:
>> Actually in this case I'm pretty sure there's already a "set bit"
>> function which will do the job.  set_bit(), I guess, though it takes a
>> bit number rather than a mask...
>>
>
>
> set_bit() operates on a long, while the intel manuals recommend
> against operating on operands of different size, especially with
> locked operations.  I think newer processors have more relaxed
> requirements, though.

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

    J

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

[Jeremy Fitzhardinge]

On 11/17/2010 12:56 AM, Jeremy Fitzhardinge wrote:
> On 11/17/2010 12:52 AM, Jeremy Fitzhardinge wrote:
>> But, yes, %z0 sounds interesting.  Is it documented anywhere?  I think
>> I've tried to use it in the past and run into gcc bugs.
> This one: http://gcc.gnu.org/bugzilla/show_bug.cgi?id=39590
>
> Should be OK in this case because there's no 64-bit values to be seen...
Hm, it fails when __ticket_t is 16 bits:

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

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


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

    J

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

[Avi Kivity]

On 11/17/2010 11:05 AM, Jeremy Fitzhardinge wrote:
> On 11/17/2010 12:58 AM, Avi Kivity wrote:
> >>  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).
>

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.

-- 
error compiling committee.c: too many arguments to function

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

[Jan Beulich]

>>> On 17.11.10 at 10:08, Jeremy Fitzhardinge <jeremy@goop.org> wrote:
> On 11/17/2010 12:56 AM, Jeremy Fitzhardinge wrote:
>> On 11/17/2010 12:52 AM, Jeremy Fitzhardinge wrote:
>>> 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...

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

Jan

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

[Jeremy Fitzhardinge]

On 11/17/2010 12:52 AM, Jeremy Fitzhardinge wrote:
> On 11/17/2010 12:11 AM, Jan Beulich wrote:
>>>>> On 16.11.10 at 22:08, Jeremy Fitzhardinge <jeremy@goop.org> wrote:
>>> +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);
>> 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.

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

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

    J

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

[Jan Beulich]

>>> On 17.11.10 at 10:57, Jeremy Fitzhardinge <jeremy@goop.org> wrote:
> On 11/17/2010 12:52 AM, Jeremy Fitzhardinge wrote:
>> On 11/17/2010 12:11 AM, Jan Beulich wrote:
>>>>>> On 16.11.10 at 22:08, Jeremy Fitzhardinge <jeremy@goop.org> wrote:
>>>> +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);
>>> 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.
> 
> 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.

> 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

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

[Peter Zijlstra]

On Tue, 2010-11-16 at 13:08 -0800, Jeremy Fitzhardinge wrote:
> Maintain a flag in both LSBs of the ticket lock which indicates whether
> anyone is in the lock slowpath and may need kicking when the current
> holder unlocks.  The flags are set when the first locker enters
> the slowpath, and cleared when unlocking to an empty queue.

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

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

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

[Jeremy Fitzhardinge]

On 11/17/2010 04:21 AM, Peter Zijlstra wrote:
> On Tue, 2010-11-16 at 13:08 -0800, Jeremy Fitzhardinge wrote:
>> Maintain a flag in both LSBs of the ticket lock which indicates whether
>> anyone is in the lock slowpath and may need kicking when the current
>> holder unlocks.  The flags are set when the first locker enters
>> the slowpath, and cleared when unlocking to an empty queue.
> So here you say you set both LSBs in order to keep head == tail working,
> but the code seems to suggest you only use the tail LSB.
>
> I think I see why using only one LSB is sufficient, but some consistency
> would be nice :-)

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

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

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

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

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

    J

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

[Jeremy Fitzhardinge]

On 11/17/2010 02:34 AM, Jan Beulich wrote:
>> 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.

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

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

[Konrad Rzeszutek Wilk]

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

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

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

[Srivatsa Vaddagiri]

On Tue, Nov 16, 2010 at 01:08:44PM -0800, Jeremy Fitzhardinge wrote:
> From: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>
> 
> 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

I think this is still racy ..

Unlocker				Locker

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


unlock

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

- vatsa

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

[Srivatsa Vaddagiri]

On Mon, Jan 17, 2011 at 08:52:22PM +0530, Srivatsa Vaddagiri wrote:
> 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

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


Signed-off-by: Srivatsa Vaddagiri <vatsa@linux.vnet.ibm.com>

---
 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
===================================================================
--- linux-2.6.37.orig/arch/x86/include/asm/spinlock.h
+++ 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 */
 }
 
Index: linux-2.6.37/arch/x86/kernel/paravirt-spinlocks.c
===================================================================
--- linux-2.6.37.orig/arch/x86/kernel/paravirt-spinlocks.c
+++ 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);

Re: [PATCH 00/14] PV ticket locks without expanding spinlock

[Srivatsa Vaddagiri]

On Tue, Nov 16, 2010 at 01:08:31PM -0800, Jeremy Fitzhardinge wrote:
> From: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>
> 
> Hi all,
> 
> This is a revised version of the pvticket lock series.

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

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

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

- vatsa

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

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

Signed-off-by: Srivatsa Vaddagiri <vatsa@linux.vnet.ibm.com>
Signed-off-by: Suzuki Poulose <suzuki@in.ibm.com>

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

Index: linux-2.6.37/arch/x86/xen/debugfs.c
===================================================================
--- linux-2.6.37.orig/arch/x86/xen/debugfs.c
+++ 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);
-}
Index: linux-2.6.37/arch/x86/xen/debugfs.h
===================================================================
--- linux-2.6.37.orig/arch/x86/xen/debugfs.h
+++ 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 */
Index: linux-2.6.37/arch/x86/xen/mmu.c
===================================================================
--- linux-2.6.37.orig/arch/x86/xen/mmu.c
+++ 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);
Index: linux-2.6.37/arch/x86/xen/multicalls.c
===================================================================
--- linux-2.6.37.orig/arch/x86/xen/multicalls.c
+++ 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;
Index: linux-2.6.37/arch/x86/xen/spinlock.c
===================================================================
--- linux-2.6.37.orig/arch/x86/xen/spinlock.c
+++ 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;
Index: linux-2.6.37/fs/debugfs/file.c
===================================================================
--- linux-2.6.37.orig/fs/debugfs/file.c
+++ linux-2.6.37/fs/debugfs/file.c
@@ -18,6 +18,7 @@
 #include <linux/pagemap.h>
 #include <linux/namei.h>
 #include <linux/debugfs.h>
+#include <linux/slab.h>
 
 static ssize_t default_read_file(struct file *file, char __user *buf,
 				 size_t count, loff_t *ppos)
@@ -534,3 +535,110 @@ struct dentry *debugfs_create_blob(const
 	return debugfs_create_file(name, mode, parent, blob, &fops_blob);
 }
 EXPORT_SYMBOL_GPL(debugfs_create_blob);
+
+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 u32_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 = u32_array_release,
+	.read	 = u32_array_read,
+	.llseek  = no_llseek,
+};
+
+struct dentry *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);
+}
Index: linux-2.6.37/include/linux/debugfs.h
===================================================================
--- linux-2.6.37.orig/include/linux/debugfs.h
+++ 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)
 {

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

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


Signed-off-by: Srivatsa Vaddagiri <vatsa@linux.vnet.ibm.com>
Signed-off-by: Suzuki Poulose <suzuki@in.ibm.com>

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

Index: linux-2.6.37/arch/x86/include/asm/kvm_para.h
===================================================================
--- linux-2.6.37.orig/arch/x86/include/asm/kvm_para.h
+++ 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
  */
Index: linux-2.6.37/arch/x86/kvm/x86.c
===================================================================
--- linux-2.6.37.orig/arch/x86/kvm/x86.c
+++ linux-2.6.37/arch/x86/kvm/x86.c
@@ -1922,6 +1922,7 @@ int kvm_dev_ioctl_check_extension(long e
 	case KVM_CAP_DEBUGREGS:
 	case KVM_CAP_X86_ROBUST_SINGLESTEP:
 	case KVM_CAP_XSAVE:
+	case KVM_CAP_WAIT_FOR_KICK:
 		r = 1;
 		break;
 	case KVM_CAP_COALESCED_MMIO:
@@ -2340,7 +2341,8 @@ static void do_cpuid_ent(struct kvm_cpui
 		entry->eax = (1 << KVM_FEATURE_CLOCKSOURCE) |
 			     (1 << KVM_FEATURE_NOP_IO_DELAY) |
 			     (1 << KVM_FEATURE_CLOCKSOURCE2) |
-			     (1 << KVM_FEATURE_CLOCKSOURCE_STABLE_BIT);
+			     (1 << KVM_FEATURE_CLOCKSOURCE_STABLE_BIT) |
+			     (1 << KVM_FEATURE_WAIT_FOR_KICK);
 		entry->ebx = 0;
 		entry->ecx = 0;
 		entry->edx = 0;
@@ -4766,6 +4768,63 @@ int kvm_hv_hypercall(struct kvm_vcpu *vc
 	return 1;
 }
 
+/*
+ * kvm_pv_wait_for_kick_op : Block until kicked by either a KVM_HC_KICK_CPU
+ * hypercall or a event like interrupt.
+ *
+ * @vcpu : vcpu which is blocking.
+ */
+static void kvm_pv_wait_for_kick_op(struct kvm_vcpu *vcpu)
+{
+	DEFINE_WAIT(wait);
+
+	/*
+	 * Blocking on vcpu->wq allows us to wake up sooner if required to
+	 * service pending events (like interrupts).
+	 *
+	 * Also set state to TASK_INTERRUPTIBLE before checking vcpu->kicked to
+	 * avoid racing with kvm_pv_kick_cpu_op().
+	 */
+	prepare_to_wait(&vcpu->wq, &wait, TASK_INTERRUPTIBLE);
+
+	do {
+		/*
+		 * Somebody has already tried kicking us. Acknowledge that
+		 * and terminate the wait.
+		 */
+		if (vcpu->kicked) {
+			vcpu->kicked = 0;
+			break;
+		}
+
+		/* Let's wait for either KVM_HC_KICK_CPU or someother event
+		 * to wake us up.
+		 */
+
+		srcu_read_unlock(&vcpu->kvm->srcu, vcpu->srcu_idx);
+		schedule();
+		vcpu->srcu_idx = srcu_read_lock(&vcpu->kvm->srcu);
+
+	} while (0);
+
+	finish_wait(&vcpu->wq, &wait);
+}
+
+/*
+ * kvm_pv_kick_cpu_op:  Kick a vcpu.
+ *
+ * @cpu - vcpu to be kicked.
+ */
+static void kvm_pv_kick_cpu_op(struct kvm *kvm, int cpu)
+{
+	struct kvm_vcpu *vcpu = kvm_get_vcpu(kvm, cpu);
+
+	if (vcpu) {
+		vcpu->kicked = 1;
+		wake_up_interruptible(&vcpu->wq);
+	}
+}
+
 int kvm_emulate_hypercall(struct kvm_vcpu *vcpu)
 {
 	unsigned long nr, a0, a1, a2, a3, ret;
@@ -4802,6 +4861,14 @@ int kvm_emulate_hypercall(struct kvm_vcp
 	case KVM_HC_MMU_OP:
 		r = kvm_pv_mmu_op(vcpu, a0, hc_gpa(vcpu, a1, a2), &ret);
 		break;
+	case KVM_HC_WAIT_FOR_KICK:
+		kvm_pv_wait_for_kick_op(vcpu);
+		ret = 0;
+		break;
+	case KVM_HC_KICK_CPU:
+		kvm_pv_kick_cpu_op(vcpu->kvm, a0);
+		ret = 0;
+		break;
 	default:
 		ret = -KVM_ENOSYS;
 		break;
Index: linux-2.6.37/include/linux/kvm.h
===================================================================
--- linux-2.6.37.orig/include/linux/kvm.h
+++ 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
 
Index: linux-2.6.37/include/linux/kvm_host.h
===================================================================
--- linux-2.6.37.orig/include/linux/kvm_host.h
+++ linux-2.6.37/include/linux/kvm_host.h
@@ -105,6 +105,7 @@ struct kvm_vcpu {
 #endif
 
 	struct kvm_vcpu_arch arch;
+	int kicked;
 };
 
 /*
Index: linux-2.6.37/include/linux/kvm_para.h
===================================================================
--- linux-2.6.37.orig/include/linux/kvm_para.h
+++ 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
Index: linux-2.6.37/virt/kvm/kvm_main.c
===================================================================
--- linux-2.6.37.orig/virt/kvm/kvm_main.c
+++ 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);

 

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

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

Signed-off-by: Srivatsa Vaddagiri <vatsa@linux.vnet.ibm.com>
Signed-off-by: Suzuki Poulose <suzuki@in.ibm.com>

---
 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(+)

Index: linux-2.6.37/arch/x86/Kconfig
===================================================================
--- linux-2.6.37.orig/arch/x86/Kconfig
+++ 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
Index: linux-2.6.37/arch/x86/include/asm/kvm_para.h
===================================================================
--- linux-2.6.37.orig/arch/x86/include/asm/kvm_para.h
+++ 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__ */
Index: linux-2.6.37/arch/x86/kernel/head64.c
===================================================================
--- linux-2.6.37.orig/arch/x86/kernel/head64.c
+++ 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
Index: linux-2.6.37/arch/x86/kernel/kvm.c
===================================================================
--- linux-2.6.37.orig/arch/x86/kernel/kvm.c
+++ linux-2.6.37/arch/x86/kernel/kvm.c
@@ -238,3 +238,211 @@ void __init kvm_guest_init(void)
 
 	paravirt_ops_setup();
 }
+
+#ifdef CONFIG_PARAVIRT_SPINLOCKS
+
+#ifdef CONFIG_KVM_DEBUG_FS
+
+#include <linux/debugfs.h>
+#include <linux/sched.h>
+
+static struct kvm_spinlock_stats
+{
+	u32 taken_slow;
+	u32 taken_slow_pickup;
+
+	u32 released_slow;
+	u32 released_slow_kicked;
+
+#define HISTO_BUCKETS	30
+	u32 histo_spin_blocked[HISTO_BUCKETS+1];
+
+	u64 time_blocked;
+} spinlock_stats;
+
+static u8 zero_stats;
+
+static inline void check_zero(void)
+{
+	if (unlikely(zero_stats)) {
+		memset(&spinlock_stats, 0, sizeof(spinlock_stats));
+		zero_stats = 0;
+	}
+}
+
+#define ADD_STATS(elem, val)			\
+	do { check_zero(); spinlock_stats.elem += (val); } while (0)
+
+static inline u64 spin_time_start(void)
+{
+	return sched_clock();
+}
+
+static void __spin_time_accum(u64 delta, u32 *array)
+{
+	unsigned index = ilog2(delta);
+
+	check_zero();
+
+	if (index < HISTO_BUCKETS)
+		array[index]++;
+	else
+		array[HISTO_BUCKETS]++;
+}
+
+static inline void spin_time_accum_blocked(u64 start)
+{
+	u32 delta = sched_clock() - start;
+
+	__spin_time_accum(delta, spinlock_stats.histo_spin_blocked);
+	spinlock_stats.time_blocked += delta;
+}
+
+static struct dentry *d_spin_debug;
+static struct dentry *d_kvm_debug;
+
+struct dentry *kvm_init_debugfs(void)
+{
+	d_kvm_debug = debugfs_create_dir("kvm", NULL);
+	if (!d_kvm_debug)
+		printk(KERN_WARNING "Could not create 'kvm' debugfs directory\n");
+
+	return d_kvm_debug;
+}
+
+static int __init kvm_spinlock_debugfs(void)
+{
+	struct dentry *d_kvm = kvm_init_debugfs();
+
+	if (d_kvm == NULL)
+		return -ENOMEM;
+
+	d_spin_debug = debugfs_create_dir("spinlocks", d_kvm);
+
+	debugfs_create_u8("zero_stats", 0644, d_spin_debug, &zero_stats);
+
+	debugfs_create_u32("taken_slow", 0444, d_spin_debug,
+			   &spinlock_stats.taken_slow);
+	debugfs_create_u32("taken_slow_pickup", 0444, d_spin_debug,
+			   &spinlock_stats.taken_slow_pickup);
+
+	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_blocked", 0444, d_spin_debug,
+			   &spinlock_stats.time_blocked);
+
+	debugfs_create_u32_array("histo_blocked", 0444, d_spin_debug,
+		     spinlock_stats.histo_spin_blocked, HISTO_BUCKETS + 1);
+
+	return 0;
+}
+fs_initcall(kvm_spinlock_debugfs);
+#else  /* !CONFIG_KVM_DEBUG_FS */
+#define TIMEOUT			(1 << 10)
+#define ADD_STATS(elem, val)	do { (void)(val); } while (0)
+
+static inline u64 spin_time_start(void)
+{
+	return 0;
+}
+
+static inline void spin_time_accum_blocked(u64 start)
+{
+}
+#endif  /* CONFIG_KVM_DEBUG_FS */
+
+struct kvm_lock_waiting {
+	struct arch_spinlock *lock;
+	__ticket_t want;
+};
+
+/* cpus 'waiting' on a spinlock to become available */
+static cpumask_t waiting_cpus;
+
+/* Track spinlock on which a cpu is waiting */
+static DEFINE_PER_CPU(struct kvm_lock_waiting, lock_waiting);
+
+static inline void kvm_wait_for_kick(void)
+{
+	kvm_hypercall0(KVM_HC_WAIT_FOR_KICK);
+}
+
+static void kvm_lock_spinning(struct arch_spinlock *lock, unsigned want)
+{
+	struct kvm_lock_waiting *w = &__get_cpu_var(lock_waiting);
+	int cpu = smp_processor_id();
+	u64 start;
+
+	start = spin_time_start();
+
+	w->want = want;
+	w->lock = lock;
+
+	ADD_STATS(taken_slow, 1);
+
+	cpumask_set_cpu(cpu, &waiting_cpus);
+
+	/* 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) {
+		ADD_STATS(taken_slow_pickup, 1);
+		goto out;
+	}
+
+	kvm_wait_for_kick();
+
+out:
+	cpumask_clear_cpu(cpu, &waiting_cpus);
+	w->lock = NULL;
+	spin_time_accum_blocked(start);
+}
+PV_CALLEE_SAVE_REGS_THUNK(kvm_lock_spinning);
+
+/* Kick a cpu */
+static inline void kvm_kick_cpu(int cpu)
+{
+	kvm_hypercall1(KVM_HC_KICK_CPU, cpu);
+}
+
+/* Kick vcpu waiting on @lock->head to reach value @ticket */
+static void kvm_unlock_kick(struct arch_spinlock *lock, unsigned ticket)
+{
+	int cpu;
+
+	ADD_STATS(released_slow, 1);
+
+	for_each_cpu(cpu, &waiting_cpus) {
+		const struct kvm_lock_waiting *w = &per_cpu(lock_waiting, cpu);
+		if (w->lock == lock && w->want == ticket) {
+			ADD_STATS(released_slow_kicked, 1);
+			kvm_kick_cpu(cpu);
+			break;
+		}
+	}
+}
+
+/*
+ * Setup pv_lock_ops to exploit KVM_FEATURE_WAIT_FOR_KICK if present.
+ * This needs to be setup really early in boot, before the first call to
+ * spinlock is issued!
+ */
+void __init kvm_guest_early_init(void)
+{
+	if (!kvm_para_available())
+		return;
+
+	/* Does host kernel support KVM_FEATURE_WAIT_FOR_KICK? */
+	if (!kvm_para_has_feature(KVM_FEATURE_WAIT_FOR_KICK))
+		return;
+
+	pv_lock_ops.lock_spinning = PV_CALLEE_SAVE(kvm_lock_spinning);
+	pv_lock_ops.unlock_kick = kvm_unlock_kick;
+}
+#endif	/* CONFIG_PARAVIRT_SPINLOCKS */

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

[Peter Zijlstra]

On Wed, 2011-01-19 at 22:42 +0530, Srivatsa Vaddagiri wrote:
> 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.

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

[Srivatsa Vaddagiri]

On Wed, Jan 19, 2011 at 10:42:39PM +0530, Srivatsa Vaddagiri wrote:
> 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

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

[Peter Zijlstra]

On Wed, 2011-01-19 at 22:53 +0530, Srivatsa Vaddagiri wrote:
> On Wed, Jan 19, 2011 at 10:42:39PM +0530, Srivatsa Vaddagiri wrote:
> > 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.

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

[Srivatsa Vaddagiri]

On Wed, Jan 19, 2011 at 06:21:12PM +0100, Peter Zijlstra wrote:
> 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.

> My guess is not, since the ticket locks used don't know who the owner
> is, which is of course, sad. There are FIFO spinlock implementations
> that can do this though.. although I think they all have a bigger memory
> footprint.
> 
> The reason for wanting this should be clear I guess, it allows PI.

Yeah - that would be good to experiment with.

- vatsa

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

[Jeremy Fitzhardinge]

On 01/17/2011 07:22 AM, Srivatsa Vaddagiri wrote:
> On Tue, Nov 16, 2010 at 01:08:44PM -0800, Jeremy Fitzhardinge wrote:
>> From: Jeremy Fitzhardinge <jeremy.fitzhardinge@citrix.com>
>>
>> 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
> 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

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

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

How much testing have you given it?

Thanks,
    J

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

[Srivatsa Vaddagiri]

On Wed, Jan 19, 2011 at 10:31:06AM -0800, Jeremy Fitzhardinge wrote:
> I think you're probably right; when I last tested this code, it was
> hanging in at about the rate this kind of race would cause.  And in my
> previous analysis of similar schemes (the current pv spinlock code), it
> was always correct to do the "slowpath" test after doing do the unlock.
> 
> *But* I haven't yet had the chance to specifically go through and
> analyse your patch in detail to make sure there's nothing else going on,
> so take this as provisional.
> 
> How much testing have you given it?

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

- vatsa

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

[Jeremy Fitzhardinge]

On 01/19/2011 09:21 AM, Peter Zijlstra wrote:
> On Wed, 2011-01-19 at 22:42 +0530, Srivatsa Vaddagiri wrote:
>> 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.

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.

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

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

    J

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

[Jeremy Fitzhardinge]

On 01/19/2011 10:39 AM, Srivatsa Vaddagiri wrote:
> I have tested quite extensively with booting a 16-vcpu guest (on a 16-pcpu host)
> and running kernel compine (with 32-threads). Without this patch, I had
> difficulty booting/shutting-down successfully (it would hang mid-way).

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

    J

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

[Srivatsa Vaddagiri]

On Wed, Jan 19, 2011 at 10:55:10AM -0800, Jeremy Fitzhardinge wrote:
> On 01/19/2011 10:39 AM, Srivatsa Vaddagiri wrote:
> > I have tested quite extensively with booting a 16-vcpu guest (on a 16-pcpu host)
> > and running kernel compine (with 32-threads). Without this patch, I had
> > difficulty booting/shutting-down successfully (it would hang mid-way).
> 
> Sounds good.  But I like to test with "make -j 100-200" to really give
> things a workout.

I reran the tests with the following configuration:

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

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

- vasa

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

[Jan Beulich]

>>> On 19.01.11 at 19:55, Jeremy Fitzhardinge <jeremy@goop.org> wrote:
> On 01/19/2011 10:39 AM, Srivatsa Vaddagiri wrote:
>> 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.

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

Jan

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

[Srivatsa Vaddagiri]

On Wed, Jan 19, 2011 at 10:53:52AM -0800, Jeremy Fitzhardinge wrote:
> > The reason for wanting this should be clear I guess, it allows PI.
> 
> Well, if we can expand the spinlock to include an owner, then all this
> becomes moot...

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

- vatsa

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

[Srivatsa Vaddagiri]

On Wed, Jan 19, 2011 at 10:53:52AM -0800, Jeremy Fitzhardinge wrote:
> > 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.

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

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

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

- vatsa

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

[Peter Zijlstra]

On Thu, 2011-01-20 at 17:29 +0530, Srivatsa Vaddagiri wrote:
> 
> If we had a yield-to [1] sort of interface _and_ information on which vcpu
> owns a lock, then lock-spinners can yield-to the owning vcpu, 

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

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

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

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

[Srivatsa Vaddagiri]

On Thu, Jan 20, 2011 at 02:41:46PM +0100, Peter Zijlstra wrote:
> On Thu, 2011-01-20 at 17:29 +0530, Srivatsa Vaddagiri wrote:
> > 
> > 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.

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

- vatsa

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

[Jeremy Fitzhardinge]

On 01/20/2011 03:42 AM, Srivatsa Vaddagiri wrote:
> On Wed, Jan 19, 2011 at 10:53:52AM -0800, Jeremy Fitzhardinge wrote:
>>> The reason for wanting this should be clear I guess, it allows PI.
>> Well, if we can expand the spinlock to include an owner, then all this
>> becomes moot...
> How so? Having an owner will not eliminate the need for pv-ticketlocks
> afaict. We still need a mechanism to reduce latency in scheduling the next
> thread-in-waiting, which is achieved by your patches. 

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

    J

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

[Jeremy Fitzhardinge]

On 01/20/2011 03:59 AM, Srivatsa Vaddagiri wrote:
>> 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.

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

>  and also to ensure that lock-owner as well as the next-in-line lock-owner 
> are not unduly made to wait for cpu. 
>
> Is there a way we can dynamically expand the size of lock only upon contention
> to include additional information like owning vcpu? Have the lock point to a
> per-cpu area upon contention where additional details can be stored perhaps?

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

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

    J

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

[Srivatsa Vaddagiri]

On Thu, Jan 20, 2011 at 09:56:27AM -0800, Jeremy Fitzhardinge wrote:
> >  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).

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

> > Is there a way we can dynamically expand the size of lock only upon contention
> > to include additional information like owning vcpu? Have the lock point to a
> > per-cpu area upon contention where additional details can be stored perhaps?
> 
> As soon as you add a pointer to the lock, you're increasing its size. 

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

- vatsa

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

[Rik van Riel]

On 01/21/2011 09:02 AM, Srivatsa Vaddagiri wrote:
> On Thu, Jan 20, 2011 at 09:56:27AM -0800, Jeremy Fitzhardinge wrote:
>>>   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).

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

-- 
All rights reversed

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

[Srivatsa Vaddagiri]

On Fri, Jan 21, 2011 at 09:48:29AM -0500, Rik van Riel wrote:
> >>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

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

[Rik van Riel]

On 01/22/2011 01:14 AM, Srivatsa Vaddagiri wrote:

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

-- 
All rights reversed

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

[Jeremy Fitzhardinge]

On 01/22/2011 06:53 AM, Rik van Riel wrote:
> The main question that remains is whether the PV ticketlocks are
> a large enough improvement to also merge those.  I expect they
> will be, and we'll see so in the benchmark numbers.

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

    J

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

[Jeremy Fitzhardinge]

On 01/19/2011 08:23 AM, Srivatsa Vaddagiri wrote:
> On Mon, Jan 17, 2011 at 08:52:22PM +0530, Srivatsa Vaddagiri wrote:
>> 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
> Patch below fixes the race described above. You can fold this to your patch
> 13/14 if you agree this is in right direction.
>
>
> Signed-off-by: Srivatsa Vaddagiri <vatsa@linux.vnet.ibm.com>
>
> ---
>  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
> ===================================================================
> --- linux-2.6.37.orig/arch/x86/include/asm/spinlock.h
> +++ 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 */
>  }
>  
> Index: linux-2.6.37/arch/x86/kernel/paravirt-spinlocks.c
> ===================================================================
> --- linux-2.6.37.orig/arch/x86/kernel/paravirt-spinlocks.c
> +++ 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);

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

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

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

    J

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

[Srivatsa Vaddagiri]

> On Mon, Jan 24, 2011 at 01:56:53PM -0800, Jeremy Fitzhardinge wrote:

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

> >   * 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);
> 
> 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