Auto-queued ticketlock

arch/x86/include/asm/spinlock_types.h +8 -2

@@ -7,12 +7,18 @@
 
 #include <linux/types.h>
 
-#if (CONFIG_NR_CPUS < 256)
+#if (CONFIG_NR_CPUS < 128)
 typedef u8  __ticket_t;
 typedef u16 __ticketpair_t;
-#else
+#define TICKET_T_CMP_GE(a, b) (UCHAR_MAX / 2 >= (unsigned char)((a) - (b)))
+#elif (CONFIG_NR_CPUS < 32768)
 typedef u16 __ticket_t;
 typedef u32 __ticketpair_t;
+#define TICKET_T_CMP_GE(a, b) (USHRT_MAX / 2 >= (unsigned short)((a) - (b)))
+#else
+typedef u32 __ticket_t;
+typedef u64 __ticketpair_t;
+#define TICKET_T_CMP_GE(a, b) (UINT_MAX / 2 >= (unsigned int)((a) - (b)))
 #endif
 
 #define TICKET_SHIFT	(sizeof(__ticket_t) * 8)

arch/x86/include/asm/spinlock_types.h +3 -0

+			__ticket_t tail, head;
+#else /* #ifdef __BIG_ENDIAN__ */
 			__ticket_t head, tail;
+#endif /* #else #ifdef __BIG_ENDIAN__ */
 		} tickets;
 	};
 } arch_spinlock_t;

Quoted 22 lines · Paul E. McKenney

arch/x86/include/asm/spinlock_types.h +8 -2

@@ -7,12 +7,18 @@
 
 #include <linux/types.h>
 
-#if (CONFIG_NR_CPUS < 256)
+#if (CONFIG_NR_CPUS < 128)
 typedef u8  __ticket_t;
 typedef u16 __ticketpair_t;
-#else
+#define TICKET_T_CMP_GE(a, b) (UCHAR_MAX / 2 >= (unsigned char)((a) - (b)))
+#elif (CONFIG_NR_CPUS < 32768)
 typedef u16 __ticket_t;
 typedef u32 __ticketpair_t;
+#define TICKET_T_CMP_GE(a, b) (USHRT_MAX / 2 >= (unsigned short)((a) - (b)))
+#else
+typedef u32 __ticket_t;
+typedef u64 __ticketpair_t;
+#define TICKET_T_CMP_GE(a, b) (UINT_MAX / 2 >= (unsigned int)((a) - (b)))
 #endif
 

arch/x86/include/asm/spinlock_types.h typedef struct arch_spinlock { · line 30

Quoted 6 lines

arch/x86/include/asm/spinlock_types.h +1 -0

 #define TICKET_SHIFT	(sizeof(__ticket_t) * 8)

@@ -21,7 +27,11 @@ typedef struct arch_spinlock {
 	union {
 		__ticketpair_t head_tail;
 		struct __raw_tickets {
+#ifdef __BIG_ENDIAN__

Is there such a thing as a BIG_ENDIAN x86 box? This is in arch/x86/include/asm/spinlock_types.h

-- Steve

Quoted 7 lines

arch/x86/include/asm/spinlock_types.h +3 -0

+			__ticket_t tail, head;
+#else /* #ifdef __BIG_ENDIAN__ */
 			__ticket_t head, tail;
+#endif /* #else #ifdef __BIG_ENDIAN__ */
 		} tickets;
 	};
 } arch_spinlock_t;

Quoted 1 line · Paul E. McKenney

+#ifdef __BIG_ENDIAN__

Is there such a thing as a BIG_ENDIAN x86 box? This is in arch/x86/include/asm/spinlock_types.h

Quoted 5 lines · Steven Rostedt

Quoted 1 line · Paul E. McKenney

+#ifdef __BIG_ENDIAN__

Is there such a thing as a BIG_ENDIAN x86 box? This is in arch/x86/include/asm/spinlock_types.h

That's just an habit for people who have been forced to deal with BE CPUs.

The sad thing is that BE CPUs have been designed by folks who blindly expanded BCD computing without understanding the hardware implications.

Unfortunately they managed to inflict BE to the network protocols which in turn manifested the only excuse of keeping the BE nonsense alive.

arch/x86/include/asm/spinlock.h +9 -0

+#else /* #ifndef CONFIG_TICKET_LOCK_QUEUED */
+
+bool tkt_spin_pass(arch_spinlock_t *ap, struct __raw_tickets inc);
+
+static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
+{
+	register struct __raw_tickets inc = { .tail = 2 };
+
+	inc = xadd(&lock->tickets, inc);

Quoted 14 lines · Paul E. McKenney

arch/x86/include/asm/spinlock.h +13 -0

+#else /* #ifndef CONFIG_TICKET_LOCK_QUEUED */
+
+bool tkt_spin_pass(arch_spinlock_t *ap, struct __raw_tickets inc);
+
+static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
+{
+	register struct __raw_tickets inc = { .tail = 2 };
+
+	inc = xadd(&lock->tickets, inc);
+	for (;;) {
+		if (inc.head == inc.tail || tkt_spin_pass(lock, inc))
+			break;
+		inc.head = ACCESS_ONCE(lock->tickets.head);

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

Quoted 6 lines

arch/x86/include/asm/spinlock.h +6 -0

+	}
+	barrier(); /* smp_mb() on Power or ARM. */
+}
+
+#endif /* #else #ifndef CONFIG_TICKET_LOCK_QUEUED */
+

To avoid the above code duplication, I would have this instead:

#ifdef CONFIG_TICKET_LOCK_QUEUED

bool tkt_spin_pass(arch_spinlock_t *ap, struct __raw_tickets inc); #define __TKT_SPIN_INC 2

#else

static inline bool tkt_spin_pass(arch_spinlock_t *ap, struct __raw_tickets inc)

{
	return false;
}

#define __TKT_SPIN_INC 1

#endif

static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)

{
	register struct __raw_tickets inc = { .tail = __TKT_SPIN_INC };

	inc = xadd(&lock->tickets, inc);

	for (;;) {
		if (inc.head == inc.tail || tkt_spin_pass(lock, inc))
			break;
		cpu_relax();
		inc.head = ACCESS_ONCE(lock->tickets.head);
	}
	barrier;	/* make sure nothing creeps before the lock is taken */
}

-- Steve

Breaking up locks is better than implementing high-contention locks, but if we must have high-contention locks, why not make them automatically switch between light-weight ticket locks at low contention and queued locks at high contention?

This commit therefore allows ticket locks to automatically switch between pure ticketlock and queued-lock operation as needed. If too many CPUs are spinning on a given ticket lock, a queue structure will be allocated and the lock will switch to queued-lock operation. When the lock becomes free, it will switch back into ticketlock operation. The low-order bit of the head counter is used to indicate that the lock is in queued mode, which forces an unconditional mismatch between the head and tail counters. This approach means that the common-case code path under conditions of low contention is very nearly that of a plain ticket lock.

A fixed number of queueing structures is statically allocated in an array. The ticket-lock address is used to hash into an initial element, but if that element is already in use, it moves to the next element. If the entire array is already in use, continue to spin in ticket mode.

This has been only lightly tested in the kernel, though a userspace implementation has survived substantial testing.

Signed-off-by Paul E. McKenney <[email protected]>

kernel/tktqlock.c new file +19 -0

+	if (head & 0x1)
+		tkt_q_do_wake(lock);
+}
+#endif /* #else #ifndef CONFIG_TICKET_LOCK_QUEUED */
 
+ */
+void tkt_q_do_wake(arch_spinlock_t *asp)
+{
+	struct tkt_q_head *tqhp;
+	struct tkt_q *tqp;
+
+	/* If the queue is still being set up, wait for it. */
+	while ((tqhp = tkt_q_find_head(asp)) == NULL)
+		cpu_relax();
+
+	for (;;) {
+
+		/* Find the first queue element. */
+		tqp = ACCESS_ONCE(tqhp->spin);
+		if (tqp != NULL)

Quoted 20 lines · Paul E. McKenney

Breaking up locks is better than implementing high-contention locks, but if we must have high-contention locks, why not make them automatically switch between light-weight ticket locks at low contention and queued locks at high contention?

This commit therefore allows ticket locks to automatically switch between pure ticketlock and queued-lock operation as needed. If too many CPUs are spinning on a given ticket lock, a queue structure will be allocated and the lock will switch to queued-lock operation. When the lock becomes free, it will switch back into ticketlock operation. The low-order bit of the head counter is used to indicate that the lock is in queued mode, which forces an unconditional mismatch between the head and tail counters. This approach means that the common-case code path under conditions of low contention is very nearly that of a plain ticket lock.

A fixed number of queueing structures is statically allocated in an array. The ticket-lock address is used to hash into an initial element, but if that element is already in use, it moves to the next element. If the entire array is already in use, continue to spin in ticket mode.

Quoted 4 lines

This has been only lightly tested in the kernel, though a userspace implementation has survived substantial testing.

Signed-off-by Paul E. McKenney <[email protected]>

This looks a great idea ;)

arch/x86/include/asm/spinlock.h static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock) · line 119

Quoted 6 lines

arch/x86/include/asm/spinlock.h +6 -0

+
+static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
+{
+	__ticket_t head = 2;
+
+	head = xadd(&lock->tickets.head, 2);

	head = xadd(&lock->tickets.head, head);

Quoted 24 lines

kernel/tktqlock.c new file +23 -0

+	if (head & 0x1)
+		tkt_q_do_wake(lock);
+}
+#endif /* #else #ifndef CONFIG_TICKET_LOCK_QUEUED */
 
+ */
+void tkt_q_do_wake(arch_spinlock_t *asp)
+{
+	struct tkt_q_head *tqhp;
+	struct tkt_q *tqp;
+
+	/* If the queue is still being set up, wait for it. */
+	while ((tqhp = tkt_q_find_head(asp)) == NULL)
+		cpu_relax();
+
+	for (;;) {
+
+		/* Find the first queue element. */
+		tqp = ACCESS_ONCE(tqhp->spin);
+		if (tqp != NULL)
+			break;  /* Element exists, hand off lock. */
+		if (tkt_q_try_unqueue(asp, tqhp))
+			return; /* No element, successfully removed queue. */
+		cpu_relax();

kernel/tktqlock.c line 148

Quoted 6 lines

kernel/tktqlock.c new file +6 -0

+	}
+	if (ACCESS_ONCE(tqhp->head_tkt) != -1)
+		ACCESS_ONCE(tqhp->head_tkt) = -1;
+	smp_mb(); /* Order pointer fetch and assignment against handoff. */
+	ACCESS_ONCE(tqp->cpu) = -1;
+}

EXPORT_SYMBOL(tkt_q_do_wake) ?

Hmm, unfortunately I lack time this week to fully read the patch !

kernel/tktqlock.c new file +12 -0

+{
+	int i;
+	int start;
+
+	start = i = tkt_q_hash(asp);
+	do
+		if (tkt_q_heads[i].ref == asp)
+			return &tkt_q_heads[i];
+	while ((i = tkt_q_next_slot(i)) != start);
+	return NULL;
+}
+

kernel/tktqlock.c line 77

Quoted 6 lines · Paul E. McKenney

kernel/tktqlock.c new file +6 -0

+/*
+ * Return a pointer to the queue header associated with the specified lock,
+ * or return NULL if there is no queue for the lock or if the lock's queue
+ * is in transition.
+ */
+static struct tkt_q_head *tkt_q_find_head(arch_spinlock_t *asp)

BTW, what does "asp" mean? arch_spinlock?

If so, can we just call it
"lock" and be consistent with all the other spinlock calls in the kernel. Because, I keep thinking this has something to do with Microsoft dynamic web pages.

-- Steve

Quoted 12 lines

kernel/tktqlock.c new file +12 -0

+{
+	int i;
+	int start;
+
+	start = i = tkt_q_hash(asp);
+	do
+		if (tkt_q_heads[i].ref == asp)
+			return &tkt_q_heads[i];
+	while ((i = tkt_q_next_slot(i)) != start);
+	return NULL;
+}
+

arch/x86/include/asm/spinlock.h +39 -0

+#else /* #ifndef CONFIG_TICKET_LOCK_QUEUED */
+
+bool tkt_spin_pass(arch_spinlock_t *ap, struct __raw_tickets inc);
+
+static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
+{
+	register struct __raw_tickets inc = { .tail = 2 };
+
+	inc = xadd(&lock->tickets, inc);
+	for (;;) {
+		if (inc.head == inc.tail || tkt_spin_pass(lock, inc))
+			break;
+		inc.head = ACCESS_ONCE(lock->tickets.head);
+	}
+	barrier(); /* smp_mb() on Power or ARM. */
+}
+
+#endif /* #else #ifndef CONFIG_TICKET_LOCK_QUEUED */
+
 static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 {
 	arch_spinlock_t old, new;

@@ -70,17 +91,37 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 	if (old.tickets.head != old.tickets.tail)
 		return 0;
 
+#ifndef CONFIG_TICKET_LOCK_QUEUED
 	new.head_tail = old.head_tail + (1 << TICKET_SHIFT);
+#else /* #ifndef CONFIG_TICKET_LOCK_QUEUED */
+	new.head_tail = old.head_tail + (2 << TICKET_SHIFT);
+#endif /* #else #ifndef CONFIG_TICKET_LOCK_QUEUED */
 
 	/* 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;
 }
 
+#ifndef CONFIG_TICKET_LOCK_QUEUED
+
 static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
 {
 	__add(&lock->tickets.head, 1, UNLOCK_LOCK_PREFIX);
 }
 
+#else /* #ifndef CONFIG_TICKET_LOCK_QUEUED */
+
+extern void tkt_q_do_wake(arch_spinlock_t *asp);
+
+static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
+{
+	__ticket_t head = 2;
+
+	head = xadd(&lock->tickets.head, 2);
+	if (head & 0x1)
+		tkt_q_do_wake(lock);
+}
+#endif /* #else #ifndef CONFIG_TICKET_LOCK_QUEUED */
+
 static inline int __ticket_spin_is_locked(arch_spinlock_t *lock)
 {
 	struct __raw_tickets tmp = ACCESS_ONCE(lock->tickets);

arch/x86/include/asm/spinlock_types.h +12 -2

index ad0ad07..cdaefdd 100644
@@ -7,12 +7,18 @@
 
 #include <linux/types.h>
 
-#if (CONFIG_NR_CPUS < 256)
+#if (CONFIG_NR_CPUS < 128)
 typedef u8  __ticket_t;
 typedef u16 __ticketpair_t;
-#else
+#define TICKET_T_CMP_GE(a, b) (UCHAR_MAX / 2 >= (unsigned char)((a) - (b)))
+#elif (CONFIG_NR_CPUS < 32768)
 typedef u16 __ticket_t;
 typedef u32 __ticketpair_t;
+#define TICKET_T_CMP_GE(a, b) (USHRT_MAX / 2 >= (unsigned short)((a) - (b)))
+#else
+typedef u32 __ticket_t;
+typedef u64 __ticketpair_t;
+#define TICKET_T_CMP_GE(a, b) (UINT_MAX / 2 >= (unsigned int)((a) - (b)))
 #endif
 
 #define TICKET_SHIFT	(sizeof(__ticket_t) * 8)

@@ -21,7 +27,11 @@ typedef struct arch_spinlock {
 	union {
 		__ticketpair_t head_tail;
 		struct __raw_tickets {
+#ifdef __BIG_ENDIAN__
+			__ticket_t tail, head;
+#else /* #ifdef __BIG_ENDIAN__ */
 			__ticket_t head, tail;
+#endif /* #else #ifdef __BIG_ENDIAN__ */
 		} tickets;
 	};
 } arch_spinlock_t;

include/linux/kernel.h +1 -0

index e9ef6d6..816a87c 100644
@@ -15,6 +15,7 @@
 #include <asm/byteorder.h>
 #include <uapi/linux/kernel.h>
 
+#define UCHAR_MAX	((u8)(~0U))
 #define USHRT_MAX	((u16)(~0U))
 #define SHRT_MAX	((s16)(USHRT_MAX>>1))
 #define SHRT_MIN	((s16)(-SHRT_MAX - 1))

kernel/Kconfig.locks +18 -0

index 44511d1..ad9c67c 100644
@@ -223,3 +223,21 @@ endif
 config MUTEX_SPIN_ON_OWNER
 	def_bool y
 	depends on SMP && !DEBUG_MUTEXES
+
+config TICKET_LOCK_QUEUED
+	bool "Dynamically switch between ticket and queued locking"
+	default n
+	---help---
+	  Enable dynamic switching between ticketlock and queued locking
+	  on a per-lock basis.  This option will slow down low-contention
+	  acquisition and release very slightly (additional conditional
+	  in release path), but will provide more efficient operation at
+	  high levels of lock contention.  High-contention operation will
+	  not be quite as efficient as would be a pure queued lock, but
+	  this dynamic approach consumes less memory than queud locks
+	  and also runs faster at low levels of contention.
+
+	  Say "Y" if you are running on a large system with a workload
+	  that is likely to result in high levels of contention.
+
+	  Say "N" if you are unsure.

kernel/Makefile +1 -0

index 271fd31..70a91f7 100644
@@ -51,6 +51,7 @@ endif
 obj-$(CONFIG_SMP) += spinlock.o
 obj-$(CONFIG_DEBUG_SPINLOCK) += spinlock.o
 obj-$(CONFIG_PROVE_LOCKING) += spinlock.o
+obj-$(CONFIG_TICKET_LOCK_QUEUED) += tktqlock.o
 obj-$(CONFIG_UID16) += uid16.o
 obj-$(CONFIG_MODULES) += module.o
 obj-$(CONFIG_MODULE_SIG) += module_signing.o modsign_pubkey.o modsign_certificate.o

kernel/tktqlock.c new file +175 -0

new file mode 100644
index 0000000..f01b760
@@ -0,0 +1,333 @@
+/*
+ * Queued ticket spinlocks.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ *
+ * Copyright IBM Corporation, 2013
+ *
+ * Authors: Paul E. McKenney <[email protected]>
+ */
+#include <linux/types.h>
+#include <linux/kernel.h>
+#include <linux/spinlock.h>
+#include <linux/smp.h>
+#include <linux/percpu.h>
+
+struct tkt_q {
+	int cpu;
+	__ticket_t tail;
+	struct tkt_q *next;
+};
+
+struct tkt_q_head {
+	arch_spinlock_t *ref;		/* Pointer to spinlock if in use. */
+	s32 head_tkt;			/* Head ticket when started queuing. */
+	struct tkt_q *spin;		/* Head of queue. */
+	struct tkt_q **spin_tail;	/* Tail of queue. */
+};
+
+/*
+ * TKT_Q_SWITCH is twice the number of CPUs that must be spinning on a
+ * given ticket lock to motivate switching to spinning on a queue.
+ * The reason that it is twice the number is because the bottom bit of
+ * the ticket is reserved for the bit that indicates that a queue is
+ * associated with the lock.
+ */
+#define TKT_Q_SWITCH  (16 * 2)
+
+/*
+ * TKT_Q_NQUEUES is the number of queues to maintain.  Large systems
+ * might have multiple highly contended locks, so provide more queues for
+ * systems with larger numbers of CPUs.
+ */
+#define TKT_Q_NQUEUES (DIV_ROUND_UP(NR_CPUS + TKT_Q_SWITCH - 1, TKT_Q_SWITCH) * 2)
+
+/* The queues themselves. */
+struct tkt_q_head tkt_q_heads[TKT_Q_NQUEUES];
+
+/* Advance to the next queue slot, wrapping around to the beginning. */
+static int tkt_q_next_slot(int i)
+{
+	return (++i < TKT_Q_NQUEUES) ? i : 0;
+}
+
+/* Very crude hash from lock address to queue slot number. */
+static unsigned long tkt_q_hash(arch_spinlock_t *asp)
+{
+	return (((unsigned long)asp) >> 8) % TKT_Q_NQUEUES;
+}
+
+/*
+ * Return a pointer to the queue header associated with the specified lock,
+ * or return NULL if there is no queue for the lock or if the lock's queue
+ * is in transition.
+ */
+static struct tkt_q_head *tkt_q_find_head(arch_spinlock_t *asp)
+{
+	int i;
+	int start;
+
+	start = i = tkt_q_hash(asp);
+	do
+		if (tkt_q_heads[i].ref == asp)
+			return &tkt_q_heads[i];
+	while ((i = tkt_q_next_slot(i)) != start);
+	return NULL;
+}
+
+/*
+ * Try to stop queuing, reverting back to normal ticket-lock operation.
+ * We can only stop queuing when the queue is empty, which means that
+ * we need to correctly handle races where someone shows up in the queue
+ * just as we are trying to dispense with the queue.  They win, we lose.
+ */
+static bool tkt_q_try_unqueue(arch_spinlock_t *asp, struct tkt_q_head *tqhp)
+{
+	arch_spinlock_t asold;
+	arch_spinlock_t asnew;
+
+	/* Pick up the ticket values. */
+	asold = ACCESS_ONCE(*asp);
+	if ((asold.tickets.head & ~0x1) == asold.tickets.tail) {
+
+		/* Attempt to mark the lock as not having a queue. */
+		asnew = asold;
+		asnew.tickets.head &= ~0x1;
+		if (cmpxchg(&asp->head_tail,
+			    asold.head_tail,
+			    asnew.head_tail) == asold.head_tail) {
+
+			/* Succeeded, mark the queue as unused. */
+			ACCESS_ONCE(tqhp->ref) = NULL;
+			return true;
+		}
+	}
+
+	/* Failed, tell the caller there is still a queue to pass off to. */
+	return false;
+}
+
+/*
+ * Hand the lock off to the first CPU on the queue.
+ */
+void tkt_q_do_wake(arch_spinlock_t *asp)
+{
+	struct tkt_q_head *tqhp;
+	struct tkt_q *tqp;
+
+	/* If the queue is still being set up, wait for it. */
+	while ((tqhp = tkt_q_find_head(asp)) == NULL)
+		cpu_relax();
+
+	for (;;) {
+
+		/* Find the first queue element. */
+		tqp = ACCESS_ONCE(tqhp->spin);
+		if (tqp != NULL)
+			break;  /* Element exists, hand off lock. */
+		if (tkt_q_try_unqueue(asp, tqhp))
+			return; /* No element, successfully removed queue. */
+		cpu_relax();
+	}
+	if (ACCESS_ONCE(tqhp->head_tkt) != -1)
+		ACCESS_ONCE(tqhp->head_tkt) = -1;
+	smp_mb(); /* Order pointer fetch and assignment against handoff. */
+	ACCESS_ONCE(tqp->cpu) = -1;
+}
+
+/*
+ * Given a lock that already has a queue associated with it, spin on
+ * that queue.  Return false if there was no queue (which means we do not
+ * hold the lock) and true otherwise (meaning we -do- hold the lock).
+ */
+bool tkt_q_do_spin(arch_spinlock_t *asp, struct __raw_tickets inc)
+{
+	struct tkt_q **oldtail;
+	struct tkt_q tq;
+	struct tkt_q_head *tqhp;
+
+	/*
+	 * Ensure that accesses to queue header happen after sensing
+	 * the lock's have-queue bit.
+	 */
+	smp_mb();  /* See above block comment. */
+
+	/* If there no longer is a queue, leave. */
+	tqhp = tkt_q_find_head(asp);
+	if (tqhp == NULL)
+		return false;
+
+	/* Initialize our queue element. */
+	tq.cpu = raw_smp_processor_id();
+	tq.tail = inc.tail;
+	tq.next = NULL;

kernel/tktqlock.c new file +128 -0

+			return true; /* Succeeded, queue is now empty. */
+
+		/* Failed, if needed, wait for the enqueue to complete. */
+		while (tq.next == NULL)
+			cpu_relax();
+
+		/* The following code will repair the head. */
+	}
+	smp_mb(); /* Force ordering between handoff and critical section. */
+
+	/* Advance list-head pointer. */
+	ACCESS_ONCE(tqhp->spin) = tq.next;
+	return true;
+}
+
+/*
+ * Given a lock that does not have a queue, attempt to associate the
+ * i-th queue with it, returning true if successful (meaning we hold
+ * the lock) or false otherwise (meaning we do -not- hold the lock).
+ * Note that the caller has already filled in ->ref with 0x1, so we
+ * own the queue.
+ */
+static bool
+tkt_q_init_contend(int i, arch_spinlock_t *asp, struct __raw_tickets inc)
+{
+	arch_spinlock_t asold;
+	arch_spinlock_t asnew;
+	struct tkt_q_head *tqhp;
+
+	/* Initialize the i-th queue header. */
+	tqhp = &tkt_q_heads[i];
+	tqhp->spin = NULL;
+	tqhp->spin_tail = &tqhp->spin;
+
+	/* Each pass through this loop attempts to mark the lock as queued. */
+	do {
+		asold.head_tail = ACCESS_ONCE(asp->head_tail);
+		asnew = asold;
+		if (asnew.tickets.head & 0x1) {
+
+			/* Someone beat us to it, back out. */
+			smp_mb();
+			ACCESS_ONCE(tqhp->ref) = NULL;
+
+			/* Spin on the queue element they set up. */
+			return tkt_q_do_spin(asp, inc);
+		}
+
+		/* The low-order bit in the head counter says "queued". */
+		asnew.tickets.head |= 0x1;
+	} while (cmpxchg(&asp->head_tail,
+		 asold.head_tail,
+		 asnew.head_tail) != asold.head_tail);
+
+	/* Point the queue at the lock and go spin on it. */
+	tqhp->head_tkt = asold.tickets.head;
+	smp_mb(); /* Ensure head_tkt is set prior to queuers seeing tqhp. */
+	ACCESS_ONCE(tqhp->ref) = asp;
+	return tkt_q_do_spin(asp, inc);
+}
+
+/*
+ * Start handling a period of high contention by finding a queue to associate
+ * with this lock.  Returns true if successful (in which case we hold the
+ * lock) and false otherwise (in which case we do -not- hold the lock).
+ */
+bool tkt_q_start_contend(arch_spinlock_t *asp, struct __raw_tickets inc)
+{
+	int i;
+	int start;
+
+	/* Hash the lock address to find a starting point. */
+	start = i = tkt_q_hash(asp);
+
+	/*
+	 * Each pass through the following loop attempts to associate
+	 * the lock with the corresponding queue.
+	 */
+	do {
+		/*
+		 * Use 0x1 to mark the queue in use, but also avoiding
+		 * any spinners trying to use it before we get it all
+		 * initialized.
+		 */
+		if (cmpxchg(&tkt_q_heads[i].ref,
+			    NULL,
+			    (arch_spinlock_t *)0x1) == NULL) {
+
+			/* Succeeded, now go initialize it. */
+			return tkt_q_init_contend(i, asp, inc);
+		}
+
+		/* If someone beat us to it, go spin on their queue. */
+		if (ACCESS_ONCE(asp->tickets.head) & 0x1)
+			return tkt_q_do_spin(asp, inc);
+	} while ((i = tkt_q_next_slot(i)) != start);
+
+	/* All the queues are in use, revert to spinning on the ticket lock. */
+	return false;
+}
+
+bool tkt_spin_pass(arch_spinlock_t *ap, struct __raw_tickets inc)
+{
+	if (unlikely(inc.head & 0x1)) {
+
+		/* This lock has a queue, so go spin on the queue. */
+		if (tkt_q_do_spin(ap, inc))
+			return true;
+
+		/* Get here if the queue is in transition: Retry next time. */
+
+	} else if (TICKET_T_CMP_GE(ACCESS_ONCE(ap->tickets.tail) - TKT_Q_SWITCH,
+				   ACCESS_ONCE(ap->tickets.head))) {
+
+		/*
+		 * This lock has lots of spinners, but no queue.
+		 * Go create a queue to spin on.
+		 */
+		if (tkt_q_start_contend(ap, inc))
+			return true;
+
+		/* Get here if the queue is in transition: Retry next time. */
+	}
+
+	/* Either no need for a queue or the queue is in transition.  Spin. */
+	cpu_relax();
+	return false;
+}

OK, I haven't found a issue here yet, but youss are beiing trickssy! We don't like trickssy, and we must find precccciouss!!!

Quoted 3 lines · Steven Rostedt

OK, I haven't found a issue here yet, but youss are beiing trickssy! We don't like trickssy, and we must find precccciouss!!!

.. and I personally have my usual reservations. I absolutely hate papering over scalability issues, and historically whenever people have ever thought that we want complex spinlocks, the problem has always been that the locking sucks.

So reinforced by previous events, I really feel that code that needs this kind of spinlock is broken and needs to be fixed, rather than actually introduce tricky spinlocks.

So in order to merge something like this, I want (a) numbers for real loads and (b) explanations for why the spinlock users cannot be fixed.

Because "we might hit loads" is just not good enough. I would counter with "hiding problems causes more of them".

Quoted 14 lines · Linus Torvalds

Quoted 3 lines · Steven Rostedt

OK, I haven't found a issue here yet, but youss are beiing trickssy! We don't like trickssy, and we must find precccciouss!!!

.. and I personally have my usual reservations. I absolutely hate papering over scalability issues, and historically whenever people have ever thought that we want complex spinlocks, the problem has always been that the locking sucks.

So reinforced by previous events, I really feel that code that needs this kind of spinlock is broken and needs to be fixed, rather than actually introduce tricky spinlocks.

Quoted 6 lines

So in order to merge something like this, I want (a) numbers for real loads and (b) explanations for why the spinlock users cannot be fixed.

Because "we might hit loads" is just not good enough. I would counter with "hiding problems causes more of them".

Hi, all

Off-topic, although I am in this community for several years, I am not exactly clear with this problem.

1) In general case, which lock is the most competitive in the kernel? what it protects for?
2) In which special case, which lock is the most competitive in the kernel? what it protects for?
3) In general case, which list is the most hot list?
4) In which special case, which list is the most hot list?

Quoted 8 lines

Off-topic, although I am in this community for several years, I am not exactly clear with this problem.

1) In general case, which lock is the most competitive in the kernel? what it protects for?
2) In which special case, which lock is the most competitive in the kernel? what it protects for?
3) In general case, which list is the most hot list?
4) In which special case, which list is the most hot list?

Others would know better than I, but mmap_sem has been called out as a

prime offender for some workloads. There is of course some debate as to whether the fault lies mmap_sem or with the workloads. There have been some efforts to solve this one on LKML, plus some in academia have worked on this as well:

Quoted 9 lines · Paul E. McKenney

Quoted 8 lines

Off-topic, although I am in this community for several years, I am not exactly clear with this problem.

1) In general case, which lock is the most competitive in the kernel? what it protects for?
2) In which special case, which lock is the most competitive in the kernel? what it protects for?
3) In general case, which list is the most hot list?
4) In which special case, which list is the most hot list?

Quoted 1 line

Others would know better than I, but mmap_sem has been called out as a

If the contention is with mmap_sem, then I doubt this is going to help much, as that's a sleeping rw semaphore. Now, rw semaphores are implemented with raw spinlocks, but I doubt that would be the main point of contention, compared to the sleeping part.

-- Steve

Quoted 5 lines

prime offender for some workloads. There is of course some debate as to whether the fault lies mmap_sem or with the workloads. There have been some efforts to solve this one on LKML, plus some in academia have worked on this as well:

Quoted 3 lines · Steven Rostedt

OK, I haven't found a issue here yet, but youss are beiing trickssy! We don't like trickssy, and we must find precccciouss!!!

.. and I personally have my usual reservations. I absolutely hate papering over scalability issues, and historically whenever people have ever thought that we want complex spinlocks, the problem has always been that the locking sucks.

So reinforced by previous events, I really feel that code that needs this kind of spinlock is broken and needs to be fixed, rather than actually introduce tricky spinlocks.

So in order to merge something like this, I want (a) numbers for real loads and (b) explanations for why the spinlock users cannot be fixed.

Because "we might hit loads" is just not good enough. I would counter with "hiding problems causes more of them".

Quoted 3 lines · Steven Rostedt

OK, I haven't found a issue here yet, but youss are beiing trickssy! We don't like trickssy, and we must find precccciouss!!!

.. and I personally have my usual reservations. I absolutely hate papering over scalability issues, and historically whenever people have ever thought that we want complex spinlocks, the problem has always been that the locking sucks.

So reinforced by previous events, I really feel that code that needs this kind of spinlock is broken and needs to be fixed, rather than actually introduce tricky spinlocks.

So in order to merge something like this, I want (a) numbers for real loads and (b) explanations for why the spinlock users cannot be fixed.

Quoted 14 lines · Linus Torvalds

Quoted 3 lines · Steven Rostedt

OK, I haven't found a issue here yet, but youss are beiing trickssy! We don't like trickssy, and we must find precccciouss!!!

.. and I personally have my usual reservations. I absolutely hate papering over scalability issues, and historically whenever people have ever thought that we want complex spinlocks, the problem has always been that the locking sucks.

So reinforced by previous events, I really feel that code that needs this kind of spinlock is broken and needs to be fixed, rather than actually introduce tricky spinlocks.

Quoted 2 lines

So in order to merge something like this, I want (a) numbers for real loads and (b) explanations for why the spinlock users cannot be fixed.

I hate to be the bearer of bad news but I got some pretty bad aim7 performance numbers with this patch on an 8-socket (80 core) 256 Gb memory DL980 box against a vanilla 3.10-rc4 kernel:

* shared workload:
10-100 users is in the noise area.
100-2000 users: -13% throughput.

* high_systime workload:
10-700 users is in the noise area.
700-2000 users: -55% throughput.

* disk:
10-100 users -57% throughput.
100-1000 users: -25% throughput
1000-2000 users: +8% throughput (this patch only benefits when we have a lot of concurrency).

* custom:
10-100 users: -33% throughput.
100-2000 users: -46% throughput.

* alltests:
10-1000 users is in the noise area.
1000-2000 users: -10% throughput.

One notable exception is the short workload where we actually see positive numbers:
10-100 users: +40% throughput.
100-2000 users: +69% throughput.

Thanks,
Davidlohr

I hate to be the bearer of bad news but I got some pretty bad aim7 performance numbers with this patch on an 8-socket (80 core) 256 Gb memory DL980 box against a vanilla 3.10-rc4 kernel:

* shared workload:
10-100 users is in the noise area.
100-2000 users: -13% throughput.

* high_systime workload:
10-700 users is in the noise area.
700-2000 users: -55% throughput.

* disk:
10-100 users -57% throughput.
100-1000 users: -25% throughput
1000-2000 users: +8% throughput (this patch only benefits when we have a

lot of concurrency).

* custom:
10-100 users: -33% throughput.
100-2000 users: -46% throughput.

* alltests:
10-1000 users is in the noise area.
1000-2000 users: -10% throughput.

One notable exception is the short workload where we actually see positive numbers:
10-100 users: +40% throughput.
100-2000 users: +69% throughput.

Quoted 3 lines · Davidlohr Bueso

I hate to be the bearer of bad news but I got some pretty bad aim7 performance numbers with this patch on an 8-socket (80 core) 256 Gb memory DL980 box against a vanilla 3.10-rc4 kernel:

This doesn't surprise me as the spin lock now contains a function call on any contention. Not to mention the added i$ pressure on the embedded spinlock code having to setup a function call.

Even if the queues are not used, it adds a slight overhead to all spinlocks, due to the code size increase as well as a function call on all contention, which will also have an impact on i$ and branch prediction.

Quoted 5 lines

* shared workload:
10-100 users is in the noise area.
100-2000 users: -13% throughput.

Quoted 8 lines

* high_systime workload:
10-700 users is in the noise area.
700-2000 users: -55% throughput.

* disk:
10-100 users -57% throughput.
100-1000 users: -25% throughput
1000-2000 users: +8% throughput (this patch only benefits when we have a

Perhaps this actually started using the queues?

Quoted 6 lines

lot of concurrency).

* custom:
10-100 users: -33% throughput.
100-2000 users: -46% throughput.

Quoted 8 lines

* alltests:
10-1000 users is in the noise area.
1000-2000 users: -10% throughput.

One notable exception is the short workload where we actually see positive numbers:
10-100 users: +40% throughput.
100-2000 users: +69% throughput.

Perhaps short work loads have a cold cache, and the impact on cache is not as drastic?

It would be interesting to see what perf reports on these runs.

Quoted 3 lines · Davidlohr Bueso

I hate to be the bearer of bad news but I got some pretty bad aim7 performance numbers with this patch on an 8-socket (80 core) 256 Gb memory DL980 box against a vanilla 3.10-rc4 kernel:

This doesn't surprise me as the spin lock now contains a function call on any contention. Not to mention the added i$ pressure on the embedded spinlock code having to setup a function call.

Even if the queues are not used, it adds a slight overhead to all spinlocks, due to the code size increase as well as a function call on all contention, which will also have an impact on i$ and branch prediction.

Quoted 4 lines

* shared workload:
10-100 users is in the noise area.
100-2000 users: -13% throughput.

Quoted 8 lines

* high_systime workload:
10-700 users is in the noise area.
700-2000 users: -55% throughput.

* disk:
10-100 users -57% throughput.
100-1000 users: -25% throughput
1000-2000 users: +8% throughput (this patch only benefits when we have a

Perhaps this actually started using the queues?

Quoted 6 lines

lot of concurrency).

* custom:
10-100 users: -33% throughput.
100-2000 users: -46% throughput.

Quoted 8 lines

* alltests:
10-1000 users is in the noise area.
1000-2000 users: -10% throughput.

One notable exception is the short workload where we actually see positive numbers:
10-100 users: +40% throughput.
100-2000 users: +69% throughput.

Perhaps short work loads have a cold cache, and the impact on cache is not as drastic?

It would be interesting to see what perf reports on these runs.

-- Steve

Perhaps short work loads have a cold cache, and the impact on cache is not as drastic?

It would be interesting to see what perf reports on these runs.

* short: is the big winner for this patch, +69% throughput improvement with 100-2000 users. This makes a lot of sense since the workload spends a ridiculous amount of time trying to acquire the d_lock:

84.86% 1569902 reaim [kernel.kallsyms] [k] _raw_spin_lock

                      |
                      --- _raw_spin_lock
                         |
                         |--49.96%-- dget_parent
                         |          __fsnotify_parent
                         |--49.71%-- dput

Quoted 5 lines · Davidlohr Bueso

* short: is the big winner for this patch, +69% throughput improvement with 100-2000 users. This makes a lot of sense since the workload spends a ridiculous amount of time trying to acquire the d_lock:

Quoted 7 lines

84.86% 1569902 reaim [kernel.kallsyms] [k] _raw_spin_lock

                      |
                      --- _raw_spin_lock
                         |
                         |--49.96%-- dget_parent
                         |          __fsnotify_parent
                         |--49.71%-- dput

Ugh. Do you have any idea what the heck that thing actually does?

Normally, we shouldn't see lots of dget contention, since the dcache these days does everything but the last path component locklessly.

But there's a few exceptions, like symlinks (act as "last component" in the middle). And obviously, if some crazy threaded program opens the *same* file concurrently over and over again, then that "last component" will hammer on the dentry lock of that particular path. But that "open the same file concurrently" seems totally unrealistic - although maybe that's what AIM does..

Anybody know the AIM subtests?

Also, we *may* actually be able to optimize this by making dentry->d_count atomic, which will allow us to often do dget_parent and put() without taking the dcache lock at all. That's what it used to be, but the RCU patches actually made it be protected by the d_lock. It made sense at the time, as a step in the sequence, and many of the dentry d_count accesses are under the lock, but now that the remaining hot-paths are dget_parent and dput and many of the dentry d_count increments are gone from the hot-paths, we might want to re-visit that decision. It could go either way.

According to him:

"the short workload calls security functions like getpwnam(), getpwuid(), getgrgid() a couple of times. These functions open the /etc/passwd or /etc/group files, read their content and close the files.

I did a quick attempt at this (patch attached).

Quoted 7 lines · Davidlohr Bueso

According to him:

"the short workload calls security functions like getpwnam(), getpwuid(), getgrgid() a couple of times. These functions open the /etc/passwd or /etc/group files, read their content and close the files.

Ahh, ok. So yeah, it's multiple threads all hitting the same file.

I guess that /etc/passwd case is historically interesting, but I'm not sure we really want to care too deeply..

Quoted 1 line

I did a quick attempt at this (patch attached).

Yeah, that's wrong, although it probably approximates the dget() case (but incorrectly).

One of the points behind using an atomic d_count is that then dput() should do

   if (!atomic_dec_and_lock(&dentry->d_count, &dentry->d_count))
      return;

at the very top of the function. It can avoid taking the lock entirely if the count doesn't go down to zero, which would be a common case if you have lots of users opening the same file. While still protecting d_count from ever going to zero while the lock is held.

Your

fs/dcache.c +5 -0

+       if (atomic_read(&dentry->d_count) > 1) {
+               atomic_dec(&dentry->d_count);
+               return;
+       }
+       spin_lock(&dentry->d_lock);

pattern is fundamentally racy, but it's what "atomic_dec_and_lock()" should do race-free.
For similar reasons, I think you need to still maintain the d_lock in d_prune_aliases etc. That's a slow-path, so the fact that we add an atomic sequence there doesn't much matter.

However, one optimization missing from your patch is obvious in the profile. "dget_parent()" also needs to be optimized - you still have that as 99% of the spin-lock case. I think we could do something like

   rcu_read_lock();
   parent = ACCESS_ONCE(dentry->d_parent);
   if (atomic_inc_nonzero(&parent->d_count))
      return parent;
   .. get d_lock and do it the slow way ...
   rcu_read_unlock();

to locklessly get the parent pointer. We know "parent" isn't going away (dentries are rcu-free'd and we hold the rcu read lock), and I think that we can optimistically take *any* parent dentry that happened to be valid at one point. As long as the refcount didn't go down to zero. Al?

With dput and dget_parent() both being lockless for the common case, you might get rid of the d_lock contention entirely for that load. I dunno. And I should really think more about that dget_parent() thing a bit more, but I cannot imagine how it could not be right (because even with the current d_lock model, the lock is gotten *within* dget_parent(), so the caller can never know if it gets a new or an old parent, so there is no higher-level serialization going on - and we might as well return *either* the new or the old as such).

I really want Al to double-check me if we decide to try going down this hole. But the above two fixes to your patch should at least approximate the d_lock changes, even if I'd have to look more closely at the other details of your patch..

Quoted 7 lines · Davidlohr Bueso

According to him:

"the short workload calls security functions like getpwnam(), getpwuid(), getgrgid() a couple of times. These functions open the /etc/passwd or /etc/group files, read their content and close the files.

Ahh, ok. So yeah, it's multiple threads all hitting the same file

I guess that /etc/passwd case is historically interesting, but I'm not sure we really want to care too deeply..

Quoted 1 line

I did a quick attempt at this (patch attached).

Yeah, that's wrong, although it probably approximates the dget() case (but incorrectly).

One of the points behind using an atomic d_count is that then dput() should do

   if (!atomic_dec_and_lock(&dentry->d_count, &dentry->d_count))
      return;

at the very top of the function. It can avoid taking the lock entirely if the count doesn't go down to zero, which would be a common case if you have lots of users opening the same file. While still protecting d_count from ever going to zero while the lock is held.

Your

fs/dcache.c +5 -0

+       if (atomic_read(&dentry->d_count) > 1) {
+               atomic_dec(&dentry->d_count);
+               return;
+       }
+       spin_lock(&dentry->d_lock);

pattern is fundamentally racy, but it's what "atomic_dec_and_lock()" should do race-free.

For similar reasons, I think you need to still maintain the d_lock in d_prune_aliases etc. That's a slow-path, so the fact that we add an atomic sequence there doesn't much matter.

However, one optimization missing from your patch is obvious in the profile. "dget_parent()" also needs to be optimized - you still have that as 99% of the spin-lock case. I think we could do something like

   rcu_read_lock();
   parent = ACCESS_ONCE(dentry->d_parent);
   if (atomic_inc_nonzero(&parent->d_count))
      return parent;
   .. get d_lock and do it the slow way ...
   rcu_read_unlock();

to locklessly get the parent pointer. We know "parent" isn't going away (dentries are rcu-free'd and we hold the rcu read lock), and I think that we can optimistically take *any* parent dentry that happened to be valid at one point. As long as the refcount didn't go down to zero. Al?

With dput and dget_parent() both being lockless for the common case, you might get rid of the d_lock contention entirely for that load. I dunno. And I should really think more about that dget_parent() thing a bit more, but I cannot imagine how it could not be right (because even with the current d_lock model, the lock is gotten *within* dget_parent(), so the caller can never know if it gets a new or an old parent, so there is no higher-level serialization going on - and we might as well return *either* the new or the old as such).

I really want Al to double-check me if we decide to try going down this hole. But the above two fixes to your patch should at least approximate the d_lock changes, even if I'd have to look more closely at the other details of your patch..

Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected]
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

For similar reasons, I think you need to still maintain the d_lock in d_prune_aliases etc. That's a slow-path, so the fact that we add an atomic sequence there doesn't much matter.

However, one optimization missing from your patch is obvious in the profile. "dget_parent()" also needs to be optimized - you still have that as 99% of the spin-lock case. I think we could do something like

   rcu_read_lock();
   parent = ACCESS_ONCE(dentry->d_parent);
   if (atomic_inc_nonzero(&parent->d_count))
      return parent;
   .. get d_lock and do it the slow way ...
   rcu_read_unlock();

to locklessly get the parent pointer. We know "parent" isn't going away (dentries are rcu-free'd and we hold the rcu read lock), and I think that we can optimistically take *any* parent dentry that happened to be valid at one point. As long as the refcount didn't go down to zero. Al?

Quoted 12 lines · Linus Torvalds

However, one optimization missing from your patch is obvious in the profile. "dget_parent()" also needs to be optimized - you still have that as 99% of the spin-lock case. I think we could do something like

   rcu_read_lock();
   parent = ACCESS_ONCE(dentry->d_parent);
   if (atomic_inc_nonzero(&parent->d_count))
      return parent;
   .. get d_lock and do it the slow way ...
   rcu_read_unlock();

Quoted 5 lines

to locklessly get the parent pointer. We know "parent" isn't going away (dentries are rcu-free'd and we hold the rcu read lock), and I think that we can optimistically take *any* parent dentry that happened to be valid at one point. As long as the refcount didn't go down to zero. Al?

What will you do with __d_rcu_to_refcount()? Any such scheme has to hold d_lock from zero->non-zero d_count changes, or atomic_dec_and_lock in dput() won't help at all.

As it is, both complete_walk() and unlazy_walk()
are grabbing ->d_lock on the dentry we'd reached, so they can call that sucker. And that'll give you ->d_lock contention when a bunch of threads are hitting the same file; I don't see how atomics would avoid that one...

I'd actually suggest we do *not* remove any existing d_lock usage outside of the particular special cases we want to optimize, which at least from Davidlohr's profile is just dput() (which has shown up a lot before) and dget_parent() (which I'm not sure why it happens so much on his load, but it really seems trivially safe to optimistically do under just the RCU lock).

That said, I do wonder if we could do something like "atomic_inc_not_zero()" on the d_count, and only if it is zero (which won't be horribly unusual, since for leaf dentries that nobody else is using) we'd do the whole locking sequence.

End result: I think it would be interesting to try this all out, and it could be a noticeable win under some cases, but it *definitely* needs a lot of timing and testing to see which ways it goes..

Actually, dget_parent() change might be broken; the thing is, the assumptions are more subtle than "zero -> non-zero only happens under ->d_lock". It's actually "new references are grabbed by somebody who's either already holding one on the same dentry _or_ holding ->d_lock". That's what d_invalidate() check for ->d_count needs for correctness - caller holds one reference, so comparing ->d_count with 2 under ->d_lock means checking that there's no other holders _and_ there won't be any new ones appearing.

Quoted 8 lines · Al Viro

Actually, dget_parent() change might be broken; the thing is, the assumptions are more subtle than "zero -> non-zero only happens under ->d_lock". It's actually "new references are grabbed by somebody who's either already holding one on the same dentry _or_ holding ->d_lock". That's what d_invalidate() check for ->d_count needs for correctness - caller holds one reference, so comparing ->d_count with 2 under ->d_lock means checking that there's no other holders _and_ there won't be any new ones appearing.

For the particular case of dget_parent() maybe dget_parent() should just double-check the original dentry->d_parent pointer after getting the refcount on it (and if the parent has changed, drop the refcount again and go to the locked version). That might be a good idea anyway, and should fix the possible race (which would be with another cpu having to first rename the child to some other parent, and the d_invalidate() the original parent)

That said, the case we'd really want to fix isn't dget_parent(), but just the normal RCU lookup finishing touches (the__d_rcu_to_refcount() case you already mentioned) . *If* we could do that without ever taking the d_lock on the target, that would be lovely. But it would seem to have the exact same issue. Although maybe the dentry_rcuwalk_barrier() thing ends up solving it (ie if we had a lookup at a bad time, we know it will fail the sequence count test, so we're ok).

Subtle, subtle.

Quoted 8 lines · Linus Torvalds

For the particular case of dget_parent() maybe dget_parent() should just double-check the original dentry->d_parent pointer after getting the refcount on it (and if the parent has changed, drop the refcount again and go to the locked version). That might be a good idea anyway, and should fix the possible race (which would be with another cpu having to first rename the child to some other parent, and the d_invalidate() the original parent)

Yes, but... Then we'd need to dput() that sucker if we decide we shouldn't have grabbed that reference, after all, which would make dget_parent() potentially blocking.

Quoted 11 lines · Al Viro

Quoted 7 lines · Linus Torvalds

For the particular case of dget_parent() maybe dget_parent() should just double-check the original dentry->d_parent pointer after getting the refcount on it (and if the parent has changed, drop the refcount again and go to the locked version). That might be a good idea anyway, and should fix the possible race (which would be with another cpu having to first rename the child to some other parent, and the d_invalidate() the original parent)

Yes, but... Then we'd need to dput() that sucker if we decide we shouldn't have grabbed that reference, after all, which would make dget_parent() potentially blocking.

Ho humm.. interesting. I was talking about wanting to mix atomics and spinlocks earlier in this thread due to space constraints, and it strikes me that that would actually help this case a lot. Having the dentry count mix d_lock and the count in one word would allow for atomic ops like "increment if not locked", and we'd avoid this whole race entirely..

Something like "low bit of count is the lock bit" would end up being lovely for this case. Of course, that's not how our spinlocks work ..

Linus

Quoted 11 lines · Linus Torvalds

Ho humm.. interesting. I was talking about wanting to mix atomics and spinlocks earlier in this thread due to space constraints, and it strikes me that that would actually help this case a lot. Having the dentry count mix d_lock and the count in one word would allow for atomic ops like "increment if not locked", and we'd avoid this whole race entirely..

Something like "low bit of count is the lock bit" would end up being lovely for this case. Of course, that's not how our spinlocks work ..

Quoted 1 line

Linus

I have created another patch to do exactly the "increment if not locked" operation as suggested. It did help a lot. See the patch below for more information. Any additional comment will be appreciated.

Quoted 8 lines · Waiman Long

Quoted 7 lines · Linus Torvalds

Ho humm.. interesting. I was talking about wanting to mix atomics and spinlocks earlier in this thread due to space constraints, and it strikes me that that would actually help this case a lot. Having the dentry count mix d_lock and the count in one word would allow for atomic ops like "increment if not locked", and we'd avoid this whole race entirely..

Quoted 8 lines

Quoted 4 lines

Something like "low bit of count is the lock bit" would end up being lovely for this case. Of course, that's not how our spinlocks work ..

Linus

I have created another patch to do exactly the "increment if not locked" operation as suggested. It did help a lot. See the patch below for more information. Any additional comment will be appreciated.

Hmm. This is interesting and proves the concept, and the numbers look very promising.

The patch is not mergable, though, since it clearly depends on the spinlock/d_count fitting in a u64, which is normally true, but not the case of debugging locks etc, we'd need to generalize and fix the whole concept of "refcount+lock".

Generalizing it might be a good idea anyway, since there are other cases of "atomic_dec_and_lock()" etc behaviours where we might want to have these kinds of extended lock+count shenanigans.

I also do wonder if we could perhaps fit both in 32-bits, and just not use the "real" spinlocks at all, but use a bitlock in the low (or high) bit of the refcount. We do that in some other places - we'd potentially lose lockdep etc, and we'd lose some of the other good parts of spinlocks (fairness yadda yadda), but *if* we can reduce contention enough that it works out, maybe it would be worth it.

So this doesn't look like 3.11 material, but the numbers certainly make it look very promising, so with some more work on it ...

Linus

With some minor changes, the current patch can be modified to support debugging lock for 32-bit system. For 64-bit system, we can apply a similar concept for debugging lock with cmpxchg_double. However, for architecture that does not have cmpxchg_double support, it will be out of luck and we probably couldn't support the same feature in debugging mode. It will have to fall back to taking the lock.

Quoted 6 lines · Waiman Long

With some minor changes, the current patch can be modified to support debugging lock for 32-bit system. For 64-bit system, we can apply a similar concept for debugging lock with cmpxchg_double. However, for architecture that does not have cmpxchg_double support, it will be out of luck and we probably couldn't support the same feature in debugging mode. It will have to fall back to taking the lock.

That means only x86_64 and s390 would benefit from it ... I'm sure we can do better :-)

Cheers,
Ben.

Waiman's dcache patchet were actually an attempt to address these exact
issues: http://lkml.org/lkml/2013/5/22/716

Quoted 4 lines · Steven Rostedt

Perhaps short work loads have a cold cache, and the impact on cache is not as drastic?

It would be interesting to see what perf reports on these runs.

After running the aim7 workloads on Paul's v3 patch (same 80 core, 8 socket box - HT off) the results are quite similar to the v1. One difference is that the five_sec workload benefited with +15% throughput after 500 users.

Taking a further look at each workload:

* five_sec: spends a large amount of time in the newish mcs style lock at the spin on owner for the inode->i_mutex:

24.13% 315655 reaim [kernel.kallsyms] [k] mspin_lock

                      |
                      --- mspin_lock
                         |          
                         |--99.76%-- __mutex_lock_killable_slowpath
                         |          mutex_lock_killable
                         |          vfs_readdir
                         |          SyS_getdents
                         |          system_call_fastpath
                         |          __getdents64

With this patch:

    23.56%     310531            reaim  [kernel.kallsyms]            [k] mspin_lock                                                   
                      |
                      --- mspin_lock
                         |          
                         |--99.78%-- __mutex_lock_killable_slowpath
                         |          mutex_lock_killable
                         |          vfs_readdir
                         |          SyS_getdents
                         |          system_call
                         |          __getdents64

* custom: Got a -33% throughput regression with this patch with 10-100 users and -46% with 100 users and up. It spends most kernel space time dealing trying to take the inode->i_mutex and the ext4 ->s_orphan_lock (note that all runs are performed on ramdisks with ext4):

   3.12%     137131            reaim  [kernel.kallsyms]            [k] mspin_lock                                         
                      |
                      --- mspin_lock
                         |          
                         |--82.98%-- __mutex_lock_killable_slowpath
                         |          mutex_lock_killable
                         |          vfs_readdir
                         |          SyS_getdents
                         |          system_call_fastpath
                         |          __getdents64
                         |          
                         |--16.97%-- __mutex_lock_slowpath
                         |          mutex_lock
                         |          |          
                         |          |--47.65%-- ext4_orphan_del
                         |          |--45.01%-- ext4_orphan_add

With this patch:
2.14% 109982 reaim [kernel.kallsyms] [k] mspin_lock

                      |
                      --- mspin_lock
                         |          
                         |--68.67%-- __mutex_lock_killable_slowpath
                         |          mutex_lock_killable
                         |          vfs_readdir
                         |          SyS_getdents
                         |          system_call
                         |          __getdents64
                         |          
                         |--31.24%-- __mutex_lock_slowpath
                         |          mutex_lock
                         |          |          
                         |          |--40.36%-- ext4_orphan_del

* short: is the big winner for this patch, +69% throughput improvement with 100-2000 users. This makes a lot of sense since the workload spends a ridiculous amount of time trying to acquire the d_lock:

84.86% 1569902 reaim [kernel.kallsyms] [k] _raw_spin_lock

                      |
                      --- _raw_spin_lock
                         |
                         |--49.96%-- dget_parent
                         |          __fsnotify_parent
                         |--49.71%-- dput
                         |          |
                         |          |--99.98%-- __fsnotify_parent

With this patch:

   70.65%     467422           reaim  [kernel.kallsyms]     [k] tkt_q_do_spin
                     |
                     --- tkt_q_do_spin
                        |
                        |--100.00%-- tkt_spin_pass
                        |          |
                        |          |--100.00%-- _raw_spin_lock
                        |          |          |
                        |          |          |--50.07%-- dget_parent
                        |          |          |          __fsnotify_parent
                        |          |          |--49.93%-- dput
                        |          |          |          __fsnotify_parent

* disk: This patch benefits when adding more concurrency. Got -57% with 10-100 users, -25% with 100-1000 users and +8% with over 1000 users. Spends a good amount of time dealing with the wait_queue lock. The perf traces are with 80 users, where we see the worst numbers:

22.34% 20400 reaim [kernel.kallsyms] [k] _raw_spin_lock_irqsave

                      |
                      --- _raw_spin_lock_irqsave
                         |          
                         |--50.28%-- __wake_up
                         |          |          
                         |          |--99.10%-- __wake_up_bit
                         |          |          wake_up_bit
                         |          |          unlock_buffer
                         |          
                         |--33.73%-- prepare_to_wait_exclusive
                         |          __wait_on_bit_lock
                         |          out_of_line_wait_on_bit_lock
                         |          __lock_buffer
                         |          do_get_write_access
                         |          jbd2_journal_get_write_access
                         |          __ext4_journal_get_write_access
                         |--14.76%-- finish_wait
                         |          |          
                         |          |--98.93%-- __wait_on_bit_lock
                         |          |          out_of_line_wait_on_bit_lock
                         |          |          __lock_buffer
                         |          |          do_get_write_access
                         |          |          jbd2_journal_get_write_access
                         |          |          __ext4_journal_get_write_access

With this patch the the time spent in the mentioned spinlocks considerably reduced:

     8.09%       6237            reaim  [kernel.kallsyms]   [k] __read_lock_failed                                           
                      |
                      --- __read_lock_failed
                          _raw_read_lock
                         |          
                         |--99.08%-- start_this_handle
                         |          jbd2__journal_start
                         |          __ext4_journal_start_sb

    1.48%       1032            reaim  [kernel.kallsyms]   [k] _raw_spin_lock_irqsave                                       
                      |
                      --- _raw_spin_lock_irqsave
                         |          
                         |--50.77%-- prepare_to_wait
                         |          |          
                         |          |--72.61%-- jbd2_log_wait_commit
                         |          |          jbd2_complete_transaction
                         |--21.76%-- prepare_to_wait_exclusive
                         |          __wait_on_bit_lock
                         |          out_of_line_wait_on_bit_lock
                         |          __lock_buffer
                         |          do_get_write_access
                         |          jbd2_journal_get_write_access
                         |--11.46%-- __wake_up
                         |          |          
                         |          |--44.21%-- ftrace_define_fields_jbd2_run_stats
                         |          |          __ext4_journal_stop

                         |--10.39%-- finish_wait
                         |          |          
                         |          |--53.18%-- __wait_on_bit_lock
                         |          |          out_of_line_wait_on_bit_lock
                         |          |          __lock_buffer
                         |          |          do_get_write_access
                         |          |          jbd2_journal_get_write_access
                         |          |          __ext4_journal_get_write_access

Quoted 337 lines · Paul E. McKenney

arch/x86/include/asm/spinlock.h +39 -0

+#else /* #ifndef CONFIG_TICKET_LOCK_QUEUED */
+
+bool tkt_spin_pass(arch_spinlock_t *ap, struct __raw_tickets inc);
+
+static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
+{
+	register struct __raw_tickets inc = { .tail = 2 };
+
+	inc = xadd(&lock->tickets, inc);
+	for (;;) {
+		if (inc.head == inc.tail || tkt_spin_pass(lock, inc))
+			break;
+		inc.head = ACCESS_ONCE(lock->tickets.head);
+	}
+	barrier(); /* smp_mb() on Power or ARM. */
+}
+
+#endif /* #else #ifndef CONFIG_TICKET_LOCK_QUEUED */
+
 static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 {
 	arch_spinlock_t old, new;

@@ -70,17 +91,37 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 	if (old.tickets.head != old.tickets.tail)
 		return 0;
 
+#ifndef CONFIG_TICKET_LOCK_QUEUED
 	new.head_tail = old.head_tail + (1 << TICKET_SHIFT);
+#else /* #ifndef CONFIG_TICKET_LOCK_QUEUED */
+	new.head_tail = old.head_tail + (2 << TICKET_SHIFT);
+#endif /* #else #ifndef CONFIG_TICKET_LOCK_QUEUED */
 
 	/* 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;
 }
 
+#ifndef CONFIG_TICKET_LOCK_QUEUED
+
 static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
 {
 	__add(&lock->tickets.head, 1, UNLOCK_LOCK_PREFIX);
 }
 
+#else /* #ifndef CONFIG_TICKET_LOCK_QUEUED */
+
+extern void tkt_q_do_wake(arch_spinlock_t *asp);
+
+static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
+{
+	__ticket_t head = 2;
+
+	head = xadd(&lock->tickets.head, 2);
+	if (head & 0x1)
+		tkt_q_do_wake(lock);
+}
+#endif /* #else #ifndef CONFIG_TICKET_LOCK_QUEUED */
+
 static inline int __ticket_spin_is_locked(arch_spinlock_t *lock)
 {
 	struct __raw_tickets tmp = ACCESS_ONCE(lock->tickets);

arch/x86/include/asm/spinlock_types.h +12 -2

index ad0ad07..cdaefdd 100644
@@ -7,12 +7,18 @@
 
 #include <linux/types.h>
 
-#if (CONFIG_NR_CPUS < 256)
+#if (CONFIG_NR_CPUS < 128)
 typedef u8  __ticket_t;
 typedef u16 __ticketpair_t;
-#else
+#define TICKET_T_CMP_GE(a, b) (UCHAR_MAX / 2 >= (unsigned char)((a) - (b)))
+#elif (CONFIG_NR_CPUS < 32768)
 typedef u16 __ticket_t;
 typedef u32 __ticketpair_t;
+#define TICKET_T_CMP_GE(a, b) (USHRT_MAX / 2 >= (unsigned short)((a) - (b)))
+#else
+typedef u32 __ticket_t;
+typedef u64 __ticketpair_t;
+#define TICKET_T_CMP_GE(a, b) (UINT_MAX / 2 >= (unsigned int)((a) - (b)))
 #endif
 
 #define TICKET_SHIFT	(sizeof(__ticket_t) * 8)

@@ -21,7 +27,11 @@ typedef struct arch_spinlock {
 	union {
 		__ticketpair_t head_tail;
 		struct __raw_tickets {
+#ifdef __BIG_ENDIAN__
+			__ticket_t tail, head;
+#else /* #ifdef __BIG_ENDIAN__ */
 			__ticket_t head, tail;
+#endif /* #else #ifdef __BIG_ENDIAN__ */
 		} tickets;
 	};
 } arch_spinlock_t;

include/linux/kernel.h +1 -0

index e9ef6d6..816a87c 100644
@@ -15,6 +15,7 @@
 #include <asm/byteorder.h>
 #include <uapi/linux/kernel.h>
 
+#define UCHAR_MAX	((u8)(~0U))
 #define USHRT_MAX	((u16)(~0U))
 #define SHRT_MAX	((s16)(USHRT_MAX>>1))
 #define SHRT_MIN	((s16)(-SHRT_MAX - 1))

kernel/Kconfig.locks +18 -0

index 44511d1..ad9c67c 100644
@@ -223,3 +223,21 @@ endif
 config MUTEX_SPIN_ON_OWNER
 	def_bool y
 	depends on SMP && !DEBUG_MUTEXES
+
+config TICKET_LOCK_QUEUED
+	bool "Dynamically switch between ticket and queued locking"
+	default n
+	---help---
+	  Enable dynamic switching between ticketlock and queued locking
+	  on a per-lock basis.  This option will slow down low-contention
+	  acquisition and release very slightly (additional conditional
+	  in release path), but will provide more efficient operation at
+	  high levels of lock contention.  High-contention operation will
+	  not be quite as efficient as would be a pure queued lock, but
+	  this dynamic approach consumes less memory than queud locks
+	  and also runs faster at low levels of contention.
+
+	  Say "Y" if you are running on a large system with a workload
+	  that is likely to result in high levels of contention.
+
+	  Say "N" if you are unsure.

kernel/Makefile +1 -0

index 271fd31..70a91f7 100644
@@ -51,6 +51,7 @@ endif
 obj-$(CONFIG_SMP) += spinlock.o
 obj-$(CONFIG_DEBUG_SPINLOCK) += spinlock.o
 obj-$(CONFIG_PROVE_LOCKING) += spinlock.o
+obj-$(CONFIG_TICKET_LOCK_QUEUED) += tktqlock.o
 obj-$(CONFIG_UID16) += uid16.o
 obj-$(CONFIG_MODULES) += module.o
 obj-$(CONFIG_MODULE_SIG) += module_signing.o modsign_pubkey.o modsign_certificate.o

kernel/tktqlock.c new file +184 -0

new file mode 100644
index 0000000..f01b760
@@ -0,0 +1,333 @@
+/*
+ * Queued ticket spinlocks.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ *
+ * Copyright IBM Corporation, 2013
+ *
+ * Authors: Paul E. McKenney <[email protected]>
+ */
+#include <linux/types.h>
+#include <linux/kernel.h>
+#include <linux/spinlock.h>
+#include <linux/smp.h>
+#include <linux/percpu.h>
+
+struct tkt_q {
+	int cpu;
+	__ticket_t tail;
+	struct tkt_q *next;
+};
+
+struct tkt_q_head {
+	arch_spinlock_t *ref;		/* Pointer to spinlock if in use. */
+	s32 head_tkt;			/* Head ticket when started queuing. */
+	struct tkt_q *spin;		/* Head of queue. */
+	struct tkt_q **spin_tail;	/* Tail of queue. */
+};
+
+/*
+ * TKT_Q_SWITCH is twice the number of CPUs that must be spinning on a
+ * given ticket lock to motivate switching to spinning on a queue.
+ * The reason that it is twice the number is because the bottom bit of
+ * the ticket is reserved for the bit that indicates that a queue is
+ * associated with the lock.
+ */
+#define TKT_Q_SWITCH  (16 * 2)
+
+/*
+ * TKT_Q_NQUEUES is the number of queues to maintain.  Large systems
+ * might have multiple highly contended locks, so provide more queues for
+ * systems with larger numbers of CPUs.
+ */
+#define TKT_Q_NQUEUES (DIV_ROUND_UP(NR_CPUS + TKT_Q_SWITCH - 1, TKT_Q_SWITCH) * 2)
+
+/* The queues themselves. */
+struct tkt_q_head tkt_q_heads[TKT_Q_NQUEUES];
+
+/* Advance to the next queue slot, wrapping around to the beginning. */
+static int tkt_q_next_slot(int i)
+{
+	return (++i < TKT_Q_NQUEUES) ? i : 0;
+}
+
+/* Very crude hash from lock address to queue slot number. */
+static unsigned long tkt_q_hash(arch_spinlock_t *asp)
+{
+	return (((unsigned long)asp) >> 8) % TKT_Q_NQUEUES;
+}
+
+/*
+ * Return a pointer to the queue header associated with the specified lock,
+ * or return NULL if there is no queue for the lock or if the lock's queue
+ * is in transition.
+ */
+static struct tkt_q_head *tkt_q_find_head(arch_spinlock_t *asp)
+{
+	int i;
+	int start;
+
+	start = i = tkt_q_hash(asp);
+	do
+		if (tkt_q_heads[i].ref == asp)
+			return &tkt_q_heads[i];
+	while ((i = tkt_q_next_slot(i)) != start);
+	return NULL;
+}
+
+/*
+ * Try to stop queuing, reverting back to normal ticket-lock operation.
+ * We can only stop queuing when the queue is empty, which means that
+ * we need to correctly handle races where someone shows up in the queue
+ * just as we are trying to dispense with the queue.  They win, we lose.
+ */
+static bool tkt_q_try_unqueue(arch_spinlock_t *asp, struct tkt_q_head *tqhp)
+{
+	arch_spinlock_t asold;
+	arch_spinlock_t asnew;
+
+	/* Pick up the ticket values. */
+	asold = ACCESS_ONCE(*asp);
+	if ((asold.tickets.head & ~0x1) == asold.tickets.tail) {
+
+		/* Attempt to mark the lock as not having a queue. */
+		asnew = asold;
+		asnew.tickets.head &= ~0x1;
+		if (cmpxchg(&asp->head_tail,
+			    asold.head_tail,
+			    asnew.head_tail) == asold.head_tail) {
+
+			/* Succeeded, mark the queue as unused. */
+			ACCESS_ONCE(tqhp->ref) = NULL;
+			return true;
+		}
+	}
+
+	/* Failed, tell the caller there is still a queue to pass off to. */
+	return false;
+}
+
+/*
+ * Hand the lock off to the first CPU on the queue.
+ */
+void tkt_q_do_wake(arch_spinlock_t *asp)
+{
+	struct tkt_q_head *tqhp;
+	struct tkt_q *tqp;
+
+	/* If the queue is still being set up, wait for it. */
+	while ((tqhp = tkt_q_find_head(asp)) == NULL)
+		cpu_relax();
+
+	for (;;) {
+
+		/* Find the first queue element. */
+		tqp = ACCESS_ONCE(tqhp->spin);
+		if (tqp != NULL)
+			break;  /* Element exists, hand off lock. */
+		if (tkt_q_try_unqueue(asp, tqhp))
+			return; /* No element, successfully removed queue. */
+		cpu_relax();
+	}
+	if (ACCESS_ONCE(tqhp->head_tkt) != -1)
+		ACCESS_ONCE(tqhp->head_tkt) = -1;
+	smp_mb(); /* Order pointer fetch and assignment against handoff. */
+	ACCESS_ONCE(tqp->cpu) = -1;
+}
+
+/*
+ * Given a lock that already has a queue associated with it, spin on
+ * that queue.  Return false if there was no queue (which means we do not
+ * hold the lock) and true otherwise (meaning we -do- hold the lock).
+ */
+bool tkt_q_do_spin(arch_spinlock_t *asp, struct __raw_tickets inc)
+{
+	struct tkt_q **oldtail;
+	struct tkt_q tq;
+	struct tkt_q_head *tqhp;
+
+	/*
+	 * Ensure that accesses to queue header happen after sensing
+	 * the lock's have-queue bit.
+	 */
+	smp_mb();  /* See above block comment. */
+
+	/* If there no longer is a queue, leave. */
+	tqhp = tkt_q_find_head(asp);
+	if (tqhp == NULL)
+		return false;
+
+	/* Initialize our queue element. */
+	tq.cpu = raw_smp_processor_id();
+	tq.tail = inc.tail;
+	tq.next = NULL;
+
+	/* Check to see if we already hold the lock. */
+	if (ACCESS_ONCE(tqhp->head_tkt) == inc.tail) {
+		/* The last holder left before queue formed, we hold lock. */
+		tqhp->head_tkt = -1;
+		return true;
+	}
+
+	/* Add our element to the tail of the queue. */

kernel/tktqlock.c line 185

Quoted 1 line

kernel/tktqlock.c new file +1 -0

+	oldtail = xchg(&tqhp->spin_tail, &tq.next);

Boy this is tricky code! I thought I found a race window here, but as I went to write my email saying "Gotcha!" I found that it wasn't a race after all. But as I went though the effort of writing this, I figured I would send this out as documentation for others to see. Hmm, I wonder if we can use this email to add more comments. Anyway, here's what I thought was wrong ;-)

OK, I originally thought there was a race window here. Let's say that an NMI hit right here, and it happens to be a big one, where lots of things can happen on other CPUs right now.

The scenario is that there's just one item on the queue, which is waiting for the lock to be released, and is spinning below in the:

	while (ACCESS_ONCE(tq.cpu) != -1)
		cpu_relax();

And then the lock is released, where in tkt_q_do_wake() the following is called:

	ACCESS_ONCE(tqp->cpu) = -1;

Now the old queued task is released. But it's tq->next hasn't been set yet, and is still NULL. It leaves by doing:

	ACCESS_ONCE(tqhp->spin) = tq.next;
	return true;

All before this task gets to set *oldtail to &tq. But, I then looked below...

kernel/tktqlock.c line 197

Quoted 12 lines

kernel/tktqlock.c new file +12 -0

+	ACCESS_ONCE(*oldtail) = &tq;
+
+	/* Spin until handoff. */
+	while (ACCESS_ONCE(tq.cpu) != -1)
+		cpu_relax();
+
+	/*
+	 * Remove our element from the queue.  If the queue is now empty,
+	 * update carefully so that the next acquisition will queue itself
+	 * at the head of the list.
+	 */
+	if (tq.next == NULL) {

This checks for that scenario.

As if the old task were to come out
spinning, the problem would only be if it was the last one on the list, and its tq.next was NULL. But if that was the case, then we set spin to NULL and do the next trick, where I thought I gotcha again...

kernel/tktqlock.c line 205

Quoted 8 lines

kernel/tktqlock.c new file +8 -0

+
+		/* Mark the queue empty. */
+		tqhp->spin = NULL;
+
+		/* Try to point the tail back at the head. */
+		if (cmpxchg(&tqhp->spin_tail,
+			    &tq.next,
+			    &tqhp->spin) == &tq.next)

Here, I was thinking, oh wait, what happens if this is called right before the xchg() above. Then we would set spin_tail but not update the old tq.next. But wait! look at what we assign spin_tail to. It's the address of spin, which would be what oldtail would point to above, and then above would set spin to the new tq!

OK, I haven't found a issue here yet, but youss are beiing trickssy! We don't like trickssy, and we must find precccciouss!!!

This code is starting to make me look like Gollum :-p

-- Steve

Quoted 128 lines

kernel/tktqlock.c new file +128 -0

+			return true; /* Succeeded, queue is now empty. */
+
+		/* Failed, if needed, wait for the enqueue to complete. */
+		while (tq.next == NULL)
+			cpu_relax();
+
+		/* The following code will repair the head. */
+	}
+	smp_mb(); /* Force ordering between handoff and critical section. */
+
+	/* Advance list-head pointer. */
+	ACCESS_ONCE(tqhp->spin) = tq.next;
+	return true;
+}
+
+/*
+ * Given a lock that does not have a queue, attempt to associate the
+ * i-th queue with it, returning true if successful (meaning we hold
+ * the lock) or false otherwise (meaning we do -not- hold the lock).
+ * Note that the caller has already filled in ->ref with 0x1, so we
+ * own the queue.
+ */
+static bool
+tkt_q_init_contend(int i, arch_spinlock_t *asp, struct __raw_tickets inc)
+{
+	arch_spinlock_t asold;
+	arch_spinlock_t asnew;
+	struct tkt_q_head *tqhp;
+
+	/* Initialize the i-th queue header. */
+	tqhp = &tkt_q_heads[i];
+	tqhp->spin = NULL;
+	tqhp->spin_tail = &tqhp->spin;
+
+	/* Each pass through this loop attempts to mark the lock as queued. */
+	do {
+		asold.head_tail = ACCESS_ONCE(asp->head_tail);
+		asnew = asold;
+		if (asnew.tickets.head & 0x1) {
+
+			/* Someone beat us to it, back out. */
+			smp_mb();
+			ACCESS_ONCE(tqhp->ref) = NULL;
+
+			/* Spin on the queue element they set up. */
+			return tkt_q_do_spin(asp, inc);
+		}
+
+		/* The low-order bit in the head counter says "queued". */
+		asnew.tickets.head |= 0x1;
+	} while (cmpxchg(&asp->head_tail,
+		 asold.head_tail,
+		 asnew.head_tail) != asold.head_tail);
+
+	/* Point the queue at the lock and go spin on it. */
+	tqhp->head_tkt = asold.tickets.head;
+	smp_mb(); /* Ensure head_tkt is set prior to queuers seeing tqhp. */
+	ACCESS_ONCE(tqhp->ref) = asp;
+	return tkt_q_do_spin(asp, inc);
+}
+
+/*
+ * Start handling a period of high contention by finding a queue to associate
+ * with this lock.  Returns true if successful (in which case we hold the
+ * lock) and false otherwise (in which case we do -not- hold the lock).
+ */
+bool tkt_q_start_contend(arch_spinlock_t *asp, struct __raw_tickets inc)
+{
+	int i;
+	int start;
+
+	/* Hash the lock address to find a starting point. */
+	start = i = tkt_q_hash(asp);
+
+	/*
+	 * Each pass through the following loop attempts to associate
+	 * the lock with the corresponding queue.
+	 */
+	do {
+		/*
+		 * Use 0x1 to mark the queue in use, but also avoiding
+		 * any spinners trying to use it before we get it all
+		 * initialized.
+		 */
+		if (cmpxchg(&tkt_q_heads[i].ref,
+			    NULL,
+			    (arch_spinlock_t *)0x1) == NULL) {
+
+			/* Succeeded, now go initialize it. */
+			return tkt_q_init_contend(i, asp, inc);
+		}
+
+		/* If someone beat us to it, go spin on their queue. */
+		if (ACCESS_ONCE(asp->tickets.head) & 0x1)
+			return tkt_q_do_spin(asp, inc);
+	} while ((i = tkt_q_next_slot(i)) != start);
+
+	/* All the queues are in use, revert to spinning on the ticket lock. */
+	return false;
+}
+
+bool tkt_spin_pass(arch_spinlock_t *ap, struct __raw_tickets inc)
+{
+	if (unlikely(inc.head & 0x1)) {
+
+		/* This lock has a queue, so go spin on the queue. */
+		if (tkt_q_do_spin(ap, inc))
+			return true;
+
+		/* Get here if the queue is in transition: Retry next time. */
+
+	} else if (TICKET_T_CMP_GE(ACCESS_ONCE(ap->tickets.tail) - TKT_Q_SWITCH,
+				   ACCESS_ONCE(ap->tickets.head))) {
+
+		/*
+		 * This lock has lots of spinners, but no queue.
+		 * Go create a queue to spin on.
+		 */
+		if (tkt_q_start_contend(ap, inc))
+			return true;
+
+		/* Get here if the queue is in transition: Retry next time. */
+	}
+
+	/* Either no need for a queue or the queue is in transition.  Spin. */
+	cpu_relax();
+	return false;
+}

Quoted 1 line · Steven Rostedt

On Sun, 2013-06-09 at 12:36 -0700, Paul E. McKenney wrote:

Quoted 30 lines

Quoted 30 lines

kernel/tktqlock.c new file +30 -0

+bool tkt_q_do_spin(arch_spinlock_t *asp, struct __raw_tickets inc)
+{
+	struct tkt_q **oldtail;
+	struct tkt_q tq;
+	struct tkt_q_head *tqhp;
+
+	/*
+	 * Ensure that accesses to queue header happen after sensing
+	 * the lock's have-queue bit.
+	 */
+	smp_mb();  /* See above block comment. */
+
+	/* If there no longer is a queue, leave. */
+	tqhp = tkt_q_find_head(asp);
+	if (tqhp == NULL)
+		return false;
+
+	/* Initialize our queue element. */
+	tq.cpu = raw_smp_processor_id();
+	tq.tail = inc.tail;
+	tq.next = NULL;
+
+	/* Check to see if we already hold the lock. */
+	if (ACCESS_ONCE(tqhp->head_tkt) == inc.tail) {
+		/* The last holder left before queue formed, we hold lock. */
+		tqhp->head_tkt = -1;
+		return true;
+	}
+
+	/* Add our element to the tail of the queue. */

Quoted 8 lines

kernel/tktqlock.c line 185

Quoted 1 line

kernel/tktqlock.c new file +1 -0

+	oldtail = xchg(&tqhp->spin_tail, &tq.next);

Boy this is tricky code! I thought I found a race window here, but as I went to write my email saying "Gotcha!" I found that it wasn't a race after all. But as I went though the effort of writing this, I figured I would send this out as documentation for others to see. Hmm, I wonder if we can use this email to add more comments. Anyway, here's what I thought was wrong ;-)

If you didn't know any better, you might even think that I had done something like this before. ;-)

Quoted 25 lines

OK, I originally thought there was a race window here. Let's say that an NMI hit right here, and it happens to be a big one, where lots of things can happen on other CPUs right now.

The scenario is that there's just one item on the queue, which is waiting for the lock to be released, and is spinning below in the:

	while (ACCESS_ONCE(tq.cpu) != -1)
		cpu_relax();

And then the lock is released, where in tkt_q_do_wake() the following is called:

	ACCESS_ONCE(tqp->cpu) = -1;

Now the old queued task is released. But it's tq->next hasn't been set yet, and is still NULL. It leaves by doing:

	ACCESS_ONCE(tqhp->spin) = tq.next;
	return true;

All before this task gets to set *oldtail to &tq. But, I then looked below...

Quoted 14 lines

kernel/tktqlock.c line 197

Quoted 12 lines

kernel/tktqlock.c new file +12 -0

+	ACCESS_ONCE(*oldtail) = &tq;
+
+	/* Spin until handoff. */
+	while (ACCESS_ONCE(tq.cpu) != -1)
+		cpu_relax();
+
+	/*
+	 * Remove our element from the queue.  If the queue is now empty,
+	 * update carefully so that the next acquisition will queue itself
+	 * at the head of the list.
+	 */
+	if (tq.next == NULL) {

This checks for that scenario.

Yep!

Quoted 6 lines

As if the old task were to come out
spinning, the problem would only be if it was the last one on the list, and its tq.next was NULL. But if that was the case, then we set spin to NULL and do the next trick, where I thought I gotcha again...

Quoted 14 lines

kernel/tktqlock.c line 205

Quoted 8 lines

kernel/tktqlock.c new file +8 -0

+
+		/* Mark the queue empty. */
+		tqhp->spin = NULL;
+
+		/* Try to point the tail back at the head. */
+		if (cmpxchg(&tqhp->spin_tail,
+			    &tq.next,
+			    &tqhp->spin) == &tq.next)

Here, I was thinking, oh wait, what happens if this is called right before the xchg() above. Then we would set spin_tail but not update the old tq.next. But wait! look at what we assign spin_tail to. It's the address of spin, which would be what oldtail would point to above, and then above would set spin to the new tq!

Yep again!

Quoted 4 lines

OK, I haven't found a issue here yet, but youss are beiing trickssy! We don't like trickssy, and we must find precccciouss!!!

Quoted 1 line

This code is starting to make me look like Gollum :-p

Hmmm... The time and effort to do this might almost have been worthwhile just to accomplish that! ;-)

But yes, this would need better comments, design documentation, or maybe both.

Breaking up locks is better than implementing high-contention locks, but if we must have high-contention locks, why not make them automatically switch between light-weight ticket locks at low contention and queued locks at high contention?

This commit therefore allows ticket locks to automatically switch between pure ticketlock and queued-lock operation as needed. If too many CPUs are spinning on a given ticket lock, a queue structure will be allocated and the lock will switch to queued-lock operation. When the lock becomes free, it will switch back into ticketlock operation. The low-order bit of the head counter is used to indicate that the lock is in queued mode, which forces an unconditional mismatch between the head and tail counters. This approach means that the common-case code path under conditions of low contention is very nearly that of a plain ticket lock.

A fixed number of queueing structures is statically allocated in an array. The ticket-lock address is used to hash into an initial element, but if that element is already in use, it moves to the next element. If the entire array is already in use, continue to spin in ticket mode.

This has been only lightly tested in the kernel, though a userspace implementation has survived substantial testing.

Signed-off-by Paul E. McKenney <[email protected]>

arch/x86/include/asm/spinlock.h +41 -0

index 33692ea..b4a91b0 100644
@@ -34,6 +34,8 @@
 # define UNLOCK_LOCK_PREFIX
 #endif
 
+#ifndef CONFIG_TICKET_LOCK_QUEUED
+
 /*
  * 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

@@ -62,6 +64,25 @@ static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 	barrier();		/* make sure nothing creeps before the lock is taken */
 }
 
+#else /* #ifndef CONFIG_TICKET_LOCK_QUEUED */
+
+bool tkt_spin_pass(arch_spinlock_t *ap, struct __raw_tickets inc);
+
+static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
+{
+	register struct __raw_tickets inc = { .tail = 2 };
+
+	inc = xadd(&lock->tickets, inc);
+	for (;;) {
+		if (inc.head == inc.tail || tkt_spin_pass(lock, inc))
+			break;
+		inc.head = ACCESS_ONCE(lock->tickets.head);
+	}
+	barrier(); /* smp_mb() on Power or ARM. */
+}
+
+#endif /* #else #ifndef CONFIG_TICKET_LOCK_QUEUED */
+
 static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 {
 	arch_spinlock_t old, new;

@@ -70,17 +91,37 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 	if (old.tickets.head != old.tickets.tail)
 		return 0;
 
+#ifndef CONFIG_TICKET_LOCK_QUEUED
 	new.head_tail = old.head_tail + (1 << TICKET_SHIFT);
+#else /* #ifndef CONFIG_TICKET_LOCK_QUEUED */
+	new.head_tail = old.head_tail + (2 << TICKET_SHIFT);
+#endif /* #else #ifndef CONFIG_TICKET_LOCK_QUEUED */
 
 	/* 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;
 }
 
+#ifndef CONFIG_TICKET_LOCK_QUEUED
+
 static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
 {
 	__add(&lock->tickets.head, 1, UNLOCK_LOCK_PREFIX);
 }
 
+#else /* #ifndef CONFIG_TICKET_LOCK_QUEUED */
+
+extern void tkt_q_do_wake(arch_spinlock_t *asp);
+
+static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
+{
+	__ticket_t head = 2;
+
+	head = xadd(&lock->tickets.head, 2);
+	if (head & 0x1)
+		tkt_q_do_wake(lock);
+}
+#endif /* #else #ifndef CONFIG_TICKET_LOCK_QUEUED */
+
 static inline int __ticket_spin_is_locked(arch_spinlock_t *lock)
 {
 	struct __raw_tickets tmp = ACCESS_ONCE(lock->tickets);

arch/x86/include/asm/spinlock_types.h +12 -2

index ad0ad07..cdaefdd 100644
@@ -7,12 +7,18 @@
 
 #include <linux/types.h>
 
-#if (CONFIG_NR_CPUS < 256)
+#if (CONFIG_NR_CPUS < 128)
 typedef u8  __ticket_t;
 typedef u16 __ticketpair_t;
-#else
+#define TICKET_T_CMP_GE(a, b) (UCHAR_MAX / 2 >= (unsigned char)((a) - (b)))
+#elif (CONFIG_NR_CPUS < 32768)
 typedef u16 __ticket_t;
 typedef u32 __ticketpair_t;
+#define TICKET_T_CMP_GE(a, b) (USHRT_MAX / 2 >= (unsigned short)((a) - (b)))
+#else
+typedef u32 __ticket_t;
+typedef u64 __ticketpair_t;
+#define TICKET_T_CMP_GE(a, b) (UINT_MAX / 2 >= (unsigned int)((a) - (b)))
 #endif
 
 #define TICKET_SHIFT	(sizeof(__ticket_t) * 8)

@@ -21,7 +27,11 @@ typedef struct arch_spinlock {
 	union {
 		__ticketpair_t head_tail;
 		struct __raw_tickets {
+#ifdef __BIG_ENDIAN__
+			__ticket_t tail, head;
+#else /* #ifdef __BIG_ENDIAN__ */
 			__ticket_t head, tail;
+#endif /* #else #ifdef __BIG_ENDIAN__ */
 		} tickets;
 	};
 } arch_spinlock_t;

include/linux/kernel.h +1 -0

index e9ef6d6..816a87c 100644
@@ -15,6 +15,7 @@
 #include <asm/byteorder.h>
 #include <uapi/linux/kernel.h>
 
+#define UCHAR_MAX	((u8)(~0U))
 #define USHRT_MAX	((u16)(~0U))
 #define SHRT_MAX	((s16)(USHRT_MAX>>1))
 #define SHRT_MIN	((s16)(-SHRT_MAX - 1))

kernel/Kconfig.locks +18 -0

index 44511d1..ad9c67c 100644
@@ -223,3 +223,21 @@ endif
 config MUTEX_SPIN_ON_OWNER
 	def_bool y
 	depends on SMP && !DEBUG_MUTEXES
+
+config TICKET_LOCK_QUEUED
+	bool "Dynamically switch between ticket and queued locking"
+	default n
+	---help---
+	  Enable dynamic switching between ticketlock and queued locking
+	  on a per-lock basis.  This option will slow down low-contention
+	  acquisition and release very slightly (additional conditional
+	  in release path), but will provide more efficient operation at
+	  high levels of lock contention.  High-contention operation will
+	  not be quite as efficient as would be a pure queued lock, but
+	  this dynamic approach consumes less memory than queud locks
+	  and also runs faster at low levels of contention.
+
+	  Say "Y" if you are running on a large system with a workload
+	  that is likely to result in high levels of contention.
+
+	  Say "N" if you are unsure.

kernel/Makefile +1 -0

index 271fd31..70a91f7 100644
@@ -51,6 +51,7 @@ endif
 obj-$(CONFIG_SMP) += spinlock.o
 obj-$(CONFIG_DEBUG_SPINLOCK) += spinlock.o
 obj-$(CONFIG_PROVE_LOCKING) += spinlock.o
+obj-$(CONFIG_TICKET_LOCK_QUEUED) += tktqlock.o
 obj-$(CONFIG_UID16) += uid16.o
 obj-$(CONFIG_MODULES) += module.o
 obj-$(CONFIG_MODULE_SIG) += module_signing.o modsign_pubkey.o modsign_certificate.o

kernel/tktqlock.c new file +333 -0

new file mode 100644
index 0000000..f01b760
@@ -0,0 +1,333 @@
+/*
+ * Queued ticket spinlocks.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ *
+ * Copyright IBM Corporation, 2013
+ *
+ * Authors: Paul E. McKenney <[email protected]>
+ */
+#include <linux/types.h>
+#include <linux/kernel.h>
+#include <linux/spinlock.h>
+#include <linux/smp.h>
+#include <linux/percpu.h>
+
+struct tkt_q {
+	int cpu;
+	__ticket_t tail;
+	struct tkt_q *next;
+};
+
+struct tkt_q_head {
+	arch_spinlock_t *ref;		/* Pointer to spinlock if in use. */
+	s32 head_tkt;			/* Head ticket when started queuing. */
+	struct tkt_q *spin;		/* Head of queue. */
+	struct tkt_q **spin_tail;	/* Tail of queue. */
+};
+
+/*
+ * TKT_Q_SWITCH is twice the number of CPUs that must be spinning on a
+ * given ticket lock to motivate switching to spinning on a queue.
+ * The reason that it is twice the number is because the bottom bit of
+ * the ticket is reserved for the bit that indicates that a queue is
+ * associated with the lock.
+ */
+#define TKT_Q_SWITCH  (16 * 2)
+
+/*
+ * TKT_Q_NQUEUES is the number of queues to maintain.  Large systems
+ * might have multiple highly contended locks, so provide more queues for
+ * systems with larger numbers of CPUs.
+ */
+#define TKT_Q_NQUEUES (DIV_ROUND_UP(NR_CPUS + TKT_Q_SWITCH - 1, TKT_Q_SWITCH) * 2)
+
+/* The queues themselves. */
+struct tkt_q_head tkt_q_heads[TKT_Q_NQUEUES];
+
+/* Advance to the next queue slot, wrapping around to the beginning. */
+static int tkt_q_next_slot(int i)
+{
+	return (++i < TKT_Q_NQUEUES) ? i : 0;
+}
+
+/* Very crude hash from lock address to queue slot number. */
+static unsigned long tkt_q_hash(arch_spinlock_t *asp)
+{
+	return (((unsigned long)asp) >> 8) % TKT_Q_NQUEUES;
+}
+
+/*
+ * Return a pointer to the queue header associated with the specified lock,
+ * or return NULL if there is no queue for the lock or if the lock's queue
+ * is in transition.
+ */
+static struct tkt_q_head *tkt_q_find_head(arch_spinlock_t *asp)
+{
+	int i;
+	int start;
+
+	start = i = tkt_q_hash(asp);
+	do
+		if (tkt_q_heads[i].ref == asp)
+			return &tkt_q_heads[i];
+	while ((i = tkt_q_next_slot(i)) != start);
+	return NULL;
+}
+
+/*
+ * Try to stop queuing, reverting back to normal ticket-lock operation.
+ * We can only stop queuing when the queue is empty, which means that
+ * we need to correctly handle races where someone shows up in the queue
+ * just as we are trying to dispense with the queue.  They win, we lose.
+ */
+static bool tkt_q_try_unqueue(arch_spinlock_t *asp, struct tkt_q_head *tqhp)
+{
+	arch_spinlock_t asold;
+	arch_spinlock_t asnew;
+
+	/* Pick up the ticket values. */
+	asold = ACCESS_ONCE(*asp);
+	if ((asold.tickets.head & ~0x1) == asold.tickets.tail) {
+
+		/* Attempt to mark the lock as not having a queue. */
+		asnew = asold;
+		asnew.tickets.head &= ~0x1;
+		if (cmpxchg(&asp->head_tail,
+			    asold.head_tail,
+			    asnew.head_tail) == asold.head_tail) {
+
+			/* Succeeded, mark the queue as unused. */
+			ACCESS_ONCE(tqhp->ref) = NULL;
+			return true;
+		}
+	}
+
+	/* Failed, tell the caller there is still a queue to pass off to. */
+	return false;
+}
+
+/*
+ * Hand the lock off to the first CPU on the queue.
+ */
+void tkt_q_do_wake(arch_spinlock_t *asp)
+{
+	struct tkt_q_head *tqhp;
+	struct tkt_q *tqp;
+
+	/* If the queue is still being set up, wait for it. */
+	while ((tqhp = tkt_q_find_head(asp)) == NULL)
+		cpu_relax();
+
+	for (;;) {
+
+		/* Find the first queue element. */
+		tqp = ACCESS_ONCE(tqhp->spin);
+		if (tqp != NULL)
+			break;  /* Element exists, hand off lock. */
+		if (tkt_q_try_unqueue(asp, tqhp))
+			return; /* No element, successfully removed queue. */
+		cpu_relax();
+	}
+	if (ACCESS_ONCE(tqhp->head_tkt) != -1)
+		ACCESS_ONCE(tqhp->head_tkt) = -1;
+	smp_mb(); /* Order pointer fetch and assignment against handoff. */
+	ACCESS_ONCE(tqp->cpu) = -1;
+}
+
+/*
+ * Given a lock that already has a queue associated with it, spin on
+ * that queue.  Return false if there was no queue (which means we do not
+ * hold the lock) and true otherwise (meaning we -do- hold the lock).
+ */
+bool tkt_q_do_spin(arch_spinlock_t *asp, struct __raw_tickets inc)
+{
+	struct tkt_q **oldtail;
+	struct tkt_q tq;
+	struct tkt_q_head *tqhp;
+
+	/*
+	 * Ensure that accesses to queue header happen after sensing
+	 * the lock's have-queue bit.
+	 */
+	smp_mb();  /* See above block comment. */
+
+	/* If there no longer is a queue, leave. */
+	tqhp = tkt_q_find_head(asp);
+	if (tqhp == NULL)
+		return false;
+
+	/* Initialize our queue element. */
+	tq.cpu = raw_smp_processor_id();
+	tq.tail = inc.tail;
+	tq.next = NULL;
+
+	/* Check to see if we already hold the lock. */
+	if (ACCESS_ONCE(tqhp->head_tkt) == inc.tail) {
+		/* The last holder left before queue formed, we hold lock. */
+		tqhp->head_tkt = -1;
+		return true;
+	}
+
+	/* Add our element to the tail of the queue. */
+	oldtail = xchg(&tqhp->spin_tail, &tq.next);
+	ACCESS_ONCE(*oldtail) = &tq;
+
+	/* Spin until handoff. */
+	while (ACCESS_ONCE(tq.cpu) != -1)
+		cpu_relax();
+
+	/*
+	 * Remove our element from the queue.  If the queue is now empty,
+	 * update carefully so that the next acquisition will queue itself
+	 * at the head of the list.
+	 */
+	if (tq.next == NULL) {
+
+		/* Mark the queue empty. */
+		tqhp->spin = NULL;
+
+		/* Try to point the tail back at the head. */
+		if (cmpxchg(&tqhp->spin_tail,
+			    &tq.next,
+			    &tqhp->spin) == &tq.next)
+			return true; /* Succeeded, queue is now empty. */
+
+		/* Failed, if needed, wait for the enqueue to complete. */
+		while (tq.next == NULL)
+			cpu_relax();
+
+		/* The following code will repair the head. */
+	}
+	smp_mb(); /* Force ordering between handoff and critical section. */
+
+	/* Advance list-head pointer. */
+	ACCESS_ONCE(tqhp->spin) = tq.next;
+	return true;
+}
+
+/*
+ * Given a lock that does not have a queue, attempt to associate the
+ * i-th queue with it, returning true if successful (meaning we hold
+ * the lock) or false otherwise (meaning we do -not- hold the lock).
+ * Note that the caller has already filled in ->ref with 0x1, so we
+ * own the queue.
+ */
+static bool
+tkt_q_init_contend(int i, arch_spinlock_t *asp, struct __raw_tickets inc)
+{
+	arch_spinlock_t asold;
+	arch_spinlock_t asnew;
+	struct tkt_q_head *tqhp;
+
+	/* Initialize the i-th queue header. */
+	tqhp = &tkt_q_heads[i];
+	tqhp->spin = NULL;
+	tqhp->spin_tail = &tqhp->spin;
+
+	/* Each pass through this loop attempts to mark the lock as queued. */
+	do {
+		asold.head_tail = ACCESS_ONCE(asp->head_tail);
+		asnew = asold;
+		if (asnew.tickets.head & 0x1) {
+
+			/* Someone beat us to it, back out. */
+			smp_mb();
+			ACCESS_ONCE(tqhp->ref) = NULL;
+
+			/* Spin on the queue element they set up. */
+			return tkt_q_do_spin(asp, inc);
+		}
+
+		/* The low-order bit in the head counter says "queued". */
+		asnew.tickets.head |= 0x1;
+	} while (cmpxchg(&asp->head_tail,
+		 asold.head_tail,
+		 asnew.head_tail) != asold.head_tail);
+
+	/* Point the queue at the lock and go spin on it. */
+	tqhp->head_tkt = asold.tickets.head;
+	smp_mb(); /* Ensure head_tkt is set prior to queuers seeing tqhp. */
+	ACCESS_ONCE(tqhp->ref) = asp;
+	return tkt_q_do_spin(asp, inc);
+}
+
+/*
+ * Start handling a period of high contention by finding a queue to associate
+ * with this lock.  Returns true if successful (in which case we hold the
+ * lock) and false otherwise (in which case we do -not- hold the lock).
+ */
+bool tkt_q_start_contend(arch_spinlock_t *asp, struct __raw_tickets inc)
+{
+	int i;
+	int start;
+
+	/* Hash the lock address to find a starting point. */
+	start = i = tkt_q_hash(asp);
+
+	/*
+	 * Each pass through the following loop attempts to associate
+	 * the lock with the corresponding queue.
+	 */
+	do {
+		/*
+		 * Use 0x1 to mark the queue in use, but also avoiding
+		 * any spinners trying to use it before we get it all
+		 * initialized.
+		 */
+		if (cmpxchg(&tkt_q_heads[i].ref,
+			    NULL,
+			    (arch_spinlock_t *)0x1) == NULL) {
+
+			/* Succeeded, now go initialize it. */
+			return tkt_q_init_contend(i, asp, inc);
+		}
+
+		/* If someone beat us to it, go spin on their queue. */
+		if (ACCESS_ONCE(asp->tickets.head) & 0x1)
+			return tkt_q_do_spin(asp, inc);
+	} while ((i = tkt_q_next_slot(i)) != start);
+
+	/* All the queues are in use, revert to spinning on the ticket lock. */
+	return false;
+}
+
+bool tkt_spin_pass(arch_spinlock_t *ap, struct __raw_tickets inc)
+{
+	if (unlikely(inc.head & 0x1)) {
+
+		/* This lock has a queue, so go spin on the queue. */
+		if (tkt_q_do_spin(ap, inc))
+			return true;
+
+		/* Get here if the queue is in transition: Retry next time. */
+
+	} else if (TICKET_T_CMP_GE(ACCESS_ONCE(ap->tickets.tail) - TKT_Q_SWITCH,
+				   ACCESS_ONCE(ap->tickets.head))) {
+
+		/*
+		 * This lock has lots of spinners, but no queue.
+		 * Go create a queue to spin on.
+		 */
+		if (tkt_q_start_contend(ap, inc))
+			return true;
+
+		/* Get here if the queue is in transition: Retry next time. */
+	}
+
+	/* Either no need for a queue or the queue is in transition.  Spin. */
+	cpu_relax();
+	return false;
+}

Quoted 20 lines · Paul E. McKenney

Breaking up locks is better than implementing high-contention locks, but if we must have high-contention locks, why not make them automatically switch between light-weight ticket locks at low contention and queued locks at high contention?

This commit therefore allows ticket locks to automatically switch between pure ticketlock and queued-lock operation as needed. If too many CPUs are spinning on a given ticket lock, a queue structure will be allocated and the lock will switch to queued-lock operation. When the lock becomes free, it will switch back into ticketlock operation. The low-order bit of the head counter is used to indicate that the lock is in queued mode, which forces an unconditional mismatch between the head and tail counters. This approach means that the common-case code path under conditions of low contention is very nearly that of a plain ticket lock.

A fixed number of queueing structures is statically allocated in an array. The ticket-lock address is used to hash into an initial element, but if that element is already in use, it moves to the next element. If the entire array is already in use, continue to spin in ticket mode.

Quoted 2 lines

This has been only lightly tested in the kernel, though a userspace implementation has survived substantial testing.

I guess the point of this patch is to lower the cache ping pong effect of spin locks. I believe Rik was doing something similar to this as well.

Now, when we switch from ticket to queue, we basically blow away the old FIFO and all the tasks do a thundering herd to get on the queue. Even if the task was next to get the lock, it could end up being stuck at the back of the queue again and have to wait. When I put my real-time hat on, this bothers me. Even though it's still a bound latency, as it only gets put to the end of the queue once, it just doubled the length of the worse case grabbing of a lock.

-- Steve

Quoted 506 lines

Signed-off-by Paul E. McKenney <[email protected]>

arch/x86/include/asm/spinlock.h +41 -0

index 33692ea..b4a91b0 100644
@@ -34,6 +34,8 @@
 # define UNLOCK_LOCK_PREFIX
 #endif
 
+#ifndef CONFIG_TICKET_LOCK_QUEUED
+
 /*
  * 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

@@ -62,6 +64,25 @@ static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
 	barrier();		/* make sure nothing creeps before the lock is taken */
 }
 
+#else /* #ifndef CONFIG_TICKET_LOCK_QUEUED */
+
+bool tkt_spin_pass(arch_spinlock_t *ap, struct __raw_tickets inc);
+
+static __always_inline void __ticket_spin_lock(arch_spinlock_t *lock)
+{
+	register struct __raw_tickets inc = { .tail = 2 };
+
+	inc = xadd(&lock->tickets, inc);
+	for (;;) {
+		if (inc.head == inc.tail || tkt_spin_pass(lock, inc))
+			break;
+		inc.head = ACCESS_ONCE(lock->tickets.head);
+	}
+	barrier(); /* smp_mb() on Power or ARM. */
+}
+
+#endif /* #else #ifndef CONFIG_TICKET_LOCK_QUEUED */
+
 static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 {
 	arch_spinlock_t old, new;

@@ -70,17 +91,37 @@ static __always_inline int __ticket_spin_trylock(arch_spinlock_t *lock)
 	if (old.tickets.head != old.tickets.tail)
 		return 0;
 
+#ifndef CONFIG_TICKET_LOCK_QUEUED
 	new.head_tail = old.head_tail + (1 << TICKET_SHIFT);
+#else /* #ifndef CONFIG_TICKET_LOCK_QUEUED */
+	new.head_tail = old.head_tail + (2 << TICKET_SHIFT);
+#endif /* #else #ifndef CONFIG_TICKET_LOCK_QUEUED */
 
 	/* 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;
 }
 
+#ifndef CONFIG_TICKET_LOCK_QUEUED
+
 static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
 {
 	__add(&lock->tickets.head, 1, UNLOCK_LOCK_PREFIX);
 }
 
+#else /* #ifndef CONFIG_TICKET_LOCK_QUEUED */
+
+extern void tkt_q_do_wake(arch_spinlock_t *asp);
+
+static __always_inline void __ticket_spin_unlock(arch_spinlock_t *lock)
+{
+	__ticket_t head = 2;
+
+	head = xadd(&lock->tickets.head, 2);
+	if (head & 0x1)
+		tkt_q_do_wake(lock);
+}
+#endif /* #else #ifndef CONFIG_TICKET_LOCK_QUEUED */
+
 static inline int __ticket_spin_is_locked(arch_spinlock_t *lock)
 {
 	struct __raw_tickets tmp = ACCESS_ONCE(lock->tickets);

arch/x86/include/asm/spinlock_types.h +12 -2

index ad0ad07..cdaefdd 100644
@@ -7,12 +7,18 @@
 
 #include <linux/types.h>
 
-#if (CONFIG_NR_CPUS < 256)
+#if (CONFIG_NR_CPUS < 128)
 typedef u8  __ticket_t;
 typedef u16 __ticketpair_t;
-#else
+#define TICKET_T_CMP_GE(a, b) (UCHAR_MAX / 2 >= (unsigned char)((a) - (b)))
+#elif (CONFIG_NR_CPUS < 32768)
 typedef u16 __ticket_t;
 typedef u32 __ticketpair_t;
+#define TICKET_T_CMP_GE(a, b) (USHRT_MAX / 2 >= (unsigned short)((a) - (b)))
+#else
+typedef u32 __ticket_t;
+typedef u64 __ticketpair_t;
+#define TICKET_T_CMP_GE(a, b) (UINT_MAX / 2 >= (unsigned int)((a) - (b)))
 #endif
 
 #define TICKET_SHIFT	(sizeof(__ticket_t) * 8)

@@ -21,7 +27,11 @@ typedef struct arch_spinlock {
 	union {
 		__ticketpair_t head_tail;
 		struct __raw_tickets {
+#ifdef __BIG_ENDIAN__
+			__ticket_t tail, head;
+#else /* #ifdef __BIG_ENDIAN__ */
 			__ticket_t head, tail;
+#endif /* #else #ifdef __BIG_ENDIAN__ */
 		} tickets;
 	};
 } arch_spinlock_t;

include/linux/kernel.h +1 -0

index e9ef6d6..816a87c 100644
@@ -15,6 +15,7 @@
 #include <asm/byteorder.h>
 #include <uapi/linux/kernel.h>
 
+#define UCHAR_MAX	((u8)(~0U))
 #define USHRT_MAX	((u16)(~0U))
 #define SHRT_MAX	((s16)(USHRT_MAX>>1))
 #define SHRT_MIN	((s16)(-SHRT_MAX - 1))

kernel/Kconfig.locks +18 -0

index 44511d1..ad9c67c 100644
@@ -223,3 +223,21 @@ endif
 config MUTEX_SPIN_ON_OWNER
 	def_bool y
 	depends on SMP && !DEBUG_MUTEXES
+
+config TICKET_LOCK_QUEUED
+	bool "Dynamically switch between ticket and queued locking"
+	default n
+	---help---
+	  Enable dynamic switching between ticketlock and queued locking
+	  on a per-lock basis.  This option will slow down low-contention
+	  acquisition and release very slightly (additional conditional
+	  in release path), but will provide more efficient operation at
+	  high levels of lock contention.  High-contention operation will
+	  not be quite as efficient as would be a pure queued lock, but
+	  this dynamic approach consumes less memory than queud locks
+	  and also runs faster at low levels of contention.
+
+	  Say "Y" if you are running on a large system with a workload
+	  that is likely to result in high levels of contention.
+
+	  Say "N" if you are unsure.

kernel/Makefile +1 -0

index 271fd31..70a91f7 100644
@@ -51,6 +51,7 @@ endif
 obj-$(CONFIG_SMP) += spinlock.o
 obj-$(CONFIG_DEBUG_SPINLOCK) += spinlock.o
 obj-$(CONFIG_PROVE_LOCKING) += spinlock.o
+obj-$(CONFIG_TICKET_LOCK_QUEUED) += tktqlock.o
 obj-$(CONFIG_UID16) += uid16.o
 obj-$(CONFIG_MODULES) += module.o
 obj-$(CONFIG_MODULE_SIG) += module_signing.o modsign_pubkey.o modsign_certificate.o

kernel/tktqlock.c new file +333 -0

new file mode 100644
index 0000000..f01b760
@@ -0,0 +1,333 @@
+/*
+ * Queued ticket spinlocks.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
+ *
+ * Copyright IBM Corporation, 2013
+ *
+ * Authors: Paul E. McKenney <[email protected]>
+ */
+#include <linux/types.h>
+#include <linux/kernel.h>
+#include <linux/spinlock.h>
+#include <linux/smp.h>
+#include <linux/percpu.h>
+
+struct tkt_q {
+	int cpu;
+	__ticket_t tail;
+	struct tkt_q *next;
+};
+
+struct tkt_q_head {
+	arch_spinlock_t *ref;		/* Pointer to spinlock if in use. */
+	s32 head_tkt;			/* Head ticket when started queuing. */
+	struct tkt_q *spin;		/* Head of queue. */
+	struct tkt_q **spin_tail;	/* Tail of queue. */
+};
+
+/*
+ * TKT_Q_SWITCH is twice the number of CPUs that must be spinning on a
+ * given ticket lock to motivate switching to spinning on a queue.
+ * The reason that it is twice the number is because the bottom bit of
+ * the ticket is reserved for the bit that indicates that a queue is
+ * associated with the lock.
+ */
+#define TKT_Q_SWITCH  (16 * 2)
+
+/*
+ * TKT_Q_NQUEUES is the number of queues to maintain.  Large systems
+ * might have multiple highly contended locks, so provide more queues for
+ * systems with larger numbers of CPUs.
+ */
+#define TKT_Q_NQUEUES (DIV_ROUND_UP(NR_CPUS + TKT_Q_SWITCH - 1, TKT_Q_SWITCH) * 2)
+
+/* The queues themselves. */
+struct tkt_q_head tkt_q_heads[TKT_Q_NQUEUES];
+
+/* Advance to the next queue slot, wrapping around to the beginning. */
+static int tkt_q_next_slot(int i)
+{
+	return (++i < TKT_Q_NQUEUES) ? i : 0;
+}
+
+/* Very crude hash from lock address to queue slot number. */
+static unsigned long tkt_q_hash(arch_spinlock_t *asp)
+{
+	return (((unsigned long)asp) >> 8) % TKT_Q_NQUEUES;
+}
+
+/*
+ * Return a pointer to the queue header associated with the specified lock,
+ * or return NULL if there is no queue for the lock or if the lock's queue
+ * is in transition.
+ */
+static struct tkt_q_head *tkt_q_find_head(arch_spinlock_t *asp)
+{
+	int i;
+	int start;
+
+	start = i = tkt_q_hash(asp);
+	do
+		if (tkt_q_heads[i].ref == asp)
+			return &tkt_q_heads[i];
+	while ((i = tkt_q_next_slot(i)) != start);
+	return NULL;
+}
+
+/*
+ * Try to stop queuing, reverting back to normal ticket-lock operation.
+ * We can only stop queuing when the queue is empty, which means that
+ * we need to correctly handle races where someone shows up in the queue
+ * just as we are trying to dispense with the queue.  They win, we lose.
+ */
+static bool tkt_q_try_unqueue(arch_spinlock_t *asp, struct tkt_q_head *tqhp)
+{
+	arch_spinlock_t asold;
+	arch_spinlock_t asnew;
+
+	/* Pick up the ticket values. */
+	asold = ACCESS_ONCE(*asp);
+	if ((asold.tickets.head & ~0x1) == asold.tickets.tail) {
+
+		/* Attempt to mark the lock as not having a queue. */
+		asnew = asold;
+		asnew.tickets.head &= ~0x1;
+		if (cmpxchg(&asp->head_tail,
+			    asold.head_tail,
+			    asnew.head_tail) == asold.head_tail) {
+
+			/* Succeeded, mark the queue as unused. */
+			ACCESS_ONCE(tqhp->ref) = NULL;
+			return true;
+		}
+	}
+
+	/* Failed, tell the caller there is still a queue to pass off to. */
+	return false;
+}
+
+/*
+ * Hand the lock off to the first CPU on the queue.
+ */
+void tkt_q_do_wake(arch_spinlock_t *asp)
+{
+	struct tkt_q_head *tqhp;
+	struct tkt_q *tqp;
+
+	/* If the queue is still being set up, wait for it. */
+	while ((tqhp = tkt_q_find_head(asp)) == NULL)
+		cpu_relax();
+
+	for (;;) {
+
+		/* Find the first queue element. */
+		tqp = ACCESS_ONCE(tqhp->spin);
+		if (tqp != NULL)
+			break;  /* Element exists, hand off lock. */
+		if (tkt_q_try_unqueue(asp, tqhp))
+			return; /* No element, successfully removed queue. */
+		cpu_relax();
+	}
+	if (ACCESS_ONCE(tqhp->head_tkt) != -1)
+		ACCESS_ONCE(tqhp->head_tkt) = -1;
+	smp_mb(); /* Order pointer fetch and assignment against handoff. */
+	ACCESS_ONCE(tqp->cpu) = -1;
+}
+
+/*
+ * Given a lock that already has a queue associated with it, spin on
+ * that queue.  Return false if there was no queue (which means we do not
+ * hold the lock) and true otherwise (meaning we -do- hold the lock).
+ */
+bool tkt_q_do_spin(arch_spinlock_t *asp, struct __raw_tickets inc)
+{
+	struct tkt_q **oldtail;
+	struct tkt_q tq;
+	struct tkt_q_head *tqhp;
+
+	/*
+	 * Ensure that accesses to queue header happen after sensing
+	 * the lock's have-queue bit.
+	 */
+	smp_mb();  /* See above block comment. */
+
+	/* If there no longer is a queue, leave. */
+	tqhp = tkt_q_find_head(asp);
+	if (tqhp == NULL)
+		return false;
+
+	/* Initialize our queue element. */
+	tq.cpu = raw_smp_processor_id();
+	tq.tail = inc.tail;
+	tq.next = NULL;
+
+	/* Check to see if we already hold the lock. */
+	if (ACCESS_ONCE(tqhp->head_tkt) == inc.tail) {
+		/* The last holder left before queue formed, we hold lock. */
+		tqhp->head_tkt = -1;
+		return true;
+	}
+
+	/* Add our element to the tail of the queue. */
+	oldtail = xchg(&tqhp->spin_tail, &tq.next);
+	ACCESS_ONCE(*oldtail) = &tq;
+
+	/* Spin until handoff. */
+	while (ACCESS_ONCE(tq.cpu) != -1)
+		cpu_relax();
+
+	/*
+	 * Remove our element from the queue.  If the queue is now empty,
+	 * update carefully so that the next acquisition will queue itself
+	 * at the head of the list.
+	 */
+	if (tq.next == NULL) {
+
+		/* Mark the queue empty. */
+		tqhp->spin = NULL;
+
+		/* Try to point the tail back at the head. */
+		if (cmpxchg(&tqhp->spin_tail,
+			    &tq.next,
+			    &tqhp->spin) == &tq.next)
+			return true; /* Succeeded, queue is now empty. */
+
+		/* Failed, if needed, wait for the enqueue to complete. */
+		while (tq.next == NULL)
+			cpu_relax();
+
+		/* The following code will repair the head. */
+	}
+	smp_mb(); /* Force ordering between handoff and critical section. */
+
+	/* Advance list-head pointer. */
+	ACCESS_ONCE(tqhp->spin) = tq.next;
+	return true;
+}
+
+/*
+ * Given a lock that does not have a queue, attempt to associate the
+ * i-th queue with it, returning true if successful (meaning we hold
+ * the lock) or false otherwise (meaning we do -not- hold the lock).
+ * Note that the caller has already filled in ->ref with 0x1, so we
+ * own the queue.
+ */
+static bool
+tkt_q_init_contend(int i, arch_spinlock_t *asp, struct __raw_tickets inc)
+{
+	arch_spinlock_t asold;
+	arch_spinlock_t asnew;
+	struct tkt_q_head *tqhp;
+
+	/* Initialize the i-th queue header. */
+	tqhp = &tkt_q_heads[i];
+	tqhp->spin = NULL;
+	tqhp->spin_tail = &tqhp->spin;
+
+	/* Each pass through this loop attempts to mark the lock as queued. */
+	do {
+		asold.head_tail = ACCESS_ONCE(asp->head_tail);
+		asnew = asold;
+		if (asnew.tickets.head & 0x1) {
+
+			/* Someone beat us to it, back out. */
+			smp_mb();
+			ACCESS_ONCE(tqhp->ref) = NULL;
+
+			/* Spin on the queue element they set up. */
+			return tkt_q_do_spin(asp, inc);
+		}
+
+		/* The low-order bit in the head counter says "queued". */
+		asnew.tickets.head |= 0x1;
+	} while (cmpxchg(&asp->head_tail,
+		 asold.head_tail,
+		 asnew.head_tail) != asold.head_tail);
+
+	/* Point the queue at the lock and go spin on it. */
+	tqhp->head_tkt = asold.tickets.head;
+	smp_mb(); /* Ensure head_tkt is set prior to queuers seeing tqhp. */
+	ACCESS_ONCE(tqhp->ref) = asp;
+	return tkt_q_do_spin(asp, inc);
+}
+
+/*
+ * Start handling a period of high contention by finding a queue to associate
+ * with this lock.  Returns true if successful (in which case we hold the
+ * lock) and false otherwise (in which case we do -not- hold the lock).
+ */
+bool tkt_q_start_contend(arch_spinlock_t *asp, struct __raw_tickets inc)
+{
+	int i;
+	int start;
+
+	/* Hash the lock address to find a starting point. */
+	start = i = tkt_q_hash(asp);
+
+	/*
+	 * Each pass through the following loop attempts to associate
+	 * the lock with the corresponding queue.
+	 */
+	do {
+		/*
+		 * Use 0x1 to mark the queue in use, but also avoiding
+		 * any spinners trying to use it before we get it all
+		 * initialized.
+		 */
+		if (cmpxchg(&tkt_q_heads[i].ref,
+			    NULL,
+			    (arch_spinlock_t *)0x1) == NULL) {
+
+			/* Succeeded, now go initialize it. */
+			return tkt_q_init_contend(i, asp, inc);
+		}
+
+		/* If someone beat us to it, go spin on their queue. */
+		if (ACCESS_ONCE(asp->tickets.head) & 0x1)
+			return tkt_q_do_spin(asp, inc);
+	} while ((i = tkt_q_next_slot(i)) != start);
+
+	/* All the queues are in use, revert to spinning on the ticket lock. */
+	return false;
+}
+
+bool tkt_spin_pass(arch_spinlock_t *ap, struct __raw_tickets inc)
+{
+	if (unlikely(inc.head & 0x1)) {
+
+		/* This lock has a queue, so go spin on the queue. */
+		if (tkt_q_do_spin(ap, inc))
+			return true;
+
+		/* Get here if the queue is in transition: Retry next time. */
+
+	} else if (TICKET_T_CMP_GE(ACCESS_ONCE(ap->tickets.tail) - TKT_Q_SWITCH,
+				   ACCESS_ONCE(ap->tickets.head))) {
+
+		/*
+		 * This lock has lots of spinners, but no queue.
+		 * Go create a queue to spin on.
+		 */
+		if (tkt_q_start_contend(ap, inc))
+			return true;
+
+		/* Get here if the queue is in transition: Retry next time. */
+	}
+
+	/* Either no need for a queue or the queue is in transition.  Spin. */
+	cpu_relax();
+	return false;
+}