[PATCH] Convert powerpc simple spinlocks into ticket locks

From: Torsten Duwe
Date: Thu Feb 06 2014 - 05:43:40 EST

x86 has them, MIPS has them, ARM has them, even ia64 has them:
ticket locks. They reduce memory bus and cache pressure especially
for contended spinlocks, increasing performance.

This patch is a port of the x86 spin locks, mostly written in C,
to the powerpc, introducing inline asm where needed. The pSeries
directed yield for vCPUs is taken care of by an additional "holder"
field in the lock.

Signed-off-by: Torsten Duwe <duwe@xxxxxxx>
--
arch/powerpc/include/asm/spinlock_types.h | 27 ++++-
arch/powerpc/include/asm/spinlock.h | 157 +++++++++++++++++++++++-------
arch/powerpc/lib/locks.c | 6 -
3 files changed, 151 insertions(+), 39 deletions(-)

diff --git a/arch/powerpc/include/asm/spinlock_types.h b/arch/powerpc/include/asm/spinlock_types.h
index 2351adc..64a98be 100644
--- a/arch/powerpc/include/asm/spinlock_types.h
+++ b/arch/powerpc/include/asm/spinlock_types.h
@@ -5,11 +5,30 @@
# error "please don't include this file directly"
#endif

-typedef struct {
- volatile unsigned int slock;
-} arch_spinlock_t;
+typedef u16 __ticket_t;
+typedef u32 __ticketpair_t;
+
+#define TICKET_LOCK_INC ((__ticket_t)1)
+
+#define TICKET_SHIFT (sizeof(__ticket_t) * 8)
+
+typedef struct arch_spinlock {
+ union {
+ __ticketpair_t head_tail;
+ struct __raw_tickets {
+#ifdef __BIG_ENDIAN__ /* The "tail" part should be in the MSBs */
+ __ticket_t tail, head;
+#else
+ __ticket_t head, tail;
+#endif
+ } tickets;
+ };
+#if defined(CONFIG_PPC64)
+ u32 holder;
+#endif
+} arch_spinlock_t __aligned(8);

-#define __ARCH_SPIN_LOCK_UNLOCKED { 0 }
+#define __ARCH_SPIN_LOCK_UNLOCKED { { 0 }, 0 }

typedef struct {
volatile signed int lock;
diff --git a/arch/powerpc/include/asm/spinlock.h b/arch/powerpc/include/asm/spinlock.h
index 5f54a74..6e33691 100644
--- a/arch/powerpc/include/asm/spinlock.h
+++ b/arch/powerpc/include/asm/spinlock.h
@@ -9,8 +9,7 @@
* Copyright (C) 2001 Anton Blanchard <anton@xxxxxxxxxx>, IBM
* Copyright (C) 2002 Dave Engebretsen <engebret@xxxxxxxxxx>, IBM
* Rework to support virtual processors
- *
- * Type of int is used as a full 64b word is not necessary.
+ * Copyright (C) 2014 Torsten Duwe <duwe@xxxxxxx>, ticket lock port
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License
@@ -28,7 +27,20 @@
#include <asm/synch.h>
#include <asm/ppc-opcode.h>

-#define arch_spin_is_locked(x) ((x)->slock != 0)
+static inline int arch_spin_is_locked(arch_spinlock_t *lock)
+{
+ struct __raw_tickets tmp = ACCESS_ONCE(lock->tickets);
+
+ return tmp.tail != tmp.head;
+}
+
+static inline int arch_spin_is_contended(arch_spinlock_t *lock)
+{
+ struct __raw_tickets tmp = ACCESS_ONCE(lock->tickets);
+
+ return (__ticket_t)(tmp.tail - tmp.head) > TICKET_LOCK_INC;
+}
+#define arch_spin_is_contended arch_spin_is_contended

#ifdef CONFIG_PPC64
/* use 0x800000yy when locked, where yy == CPU number */
@@ -37,8 +49,12 @@
#else
#define LOCK_TOKEN (*(u32 *)(&get_paca()->paca_index))
#endif
+#define SIZE_LETTER "d"
+#define L64 "1"
#else
#define LOCK_TOKEN 1
+#define SIZE_LETTER "w"
+#define L64 "0"
#endif

#if defined(CONFIG_PPC64) && defined(CONFIG_SMP)
@@ -55,33 +71,59 @@
#endif

/*
- * This returns the old value in the lock, so we succeeded
- * in getting the lock if the return value is 0.
+ * Our own cmpxchg, operating on spinlock_t's. Returns 0 iff value
+ * read at lock was equal to "old" AND the cmpxchg succeeded
+ * uninterruptedly.
*/
-static inline unsigned long __arch_spin_trylock(arch_spinlock_t *lock)
+static __always_inline int __arch_spin_cmpxchg_eq(arch_spinlock_t *lock,
+ arch_spinlock_t old,
+ arch_spinlock_t new)
{
- unsigned long tmp, token;
+ register int retval = 1;
+ register arch_spinlock_t tmp;
+
+ __asm__ __volatile__ (
+" li %0,1\n" /* default to "fail" */
+ PPC_RELEASE_BARRIER
+"1: l" SIZE_LETTER "arx %2,0,%5 # __arch_spin_cmpxchg_eq\n"
+" cmp 0,"L64",%3,%2\n"
+" bne- 2f\n"
+ PPC405_ERR77(0, "%5")
+" st" SIZE_LETTER "cx. %4,0,%5\n"
+" bne- 1b\n"
+" isync\n"
+" li %0,0\n"
+"2:"
+ : "=&r" (retval), "+m" (*lock)
+ : "r" (tmp), "r" (old), "r" (new), "r" (lock)
+ : "cc", "memory");
+
+ return retval;
+}
+#undef SIZE_LETTER
+#undef L64

- token = LOCK_TOKEN;
- __asm__ __volatile__(
-"1: " PPC_LWARX(%0,0,%2,1) "\n\
- cmpwi 0,%0,0\n\
- bne- 2f\n\
- stwcx. %1,0,%2\n\
- bne- 1b\n"
- PPC_ACQUIRE_BARRIER
-"2:"
- : "=&r" (tmp)
- : "r" (token), "r" (&lock->slock)
- : "cr0", "memory");
+static __always_inline int __arch_spin_trylock(arch_spinlock_t *lock)
+{
+ arch_spinlock_t old, new;

- return tmp;
+ old.tickets = ACCESS_ONCE(lock->tickets);
+ if (old.tickets.head != old.tickets.tail)
+ return 0;
+
+ new.head_tail = old.head_tail + (TICKET_LOCK_INC << TICKET_SHIFT);
+#if defined(CONFIG_PPC64)
+ old.holder = lock->holder;
+ new.holder = LOCK_TOKEN;
+#endif
+
+ return !__arch_spin_cmpxchg_eq(lock, old, new);
}

static inline int arch_spin_trylock(arch_spinlock_t *lock)
{
CLEAR_IO_SYNC;
- return __arch_spin_trylock(lock) == 0;
+ return __arch_spin_trylock(lock);
}

/*
@@ -93,9 +135,8 @@ static inline int arch_spin_trylock(arch_spinlock_t *lock)
* rest of our timeslice to the lock holder.
*
* So that we can tell which virtual processor is holding a lock,
- * we put 0x80000000 | smp_processor_id() in the lock when it is
- * held. Conveniently, we have a word in the paca that holds this
- * value.
+ * we put 0x80000000 | smp_processor_id() into lock->holder.
+ * Conveniently, we have a word in the paca that holds this value.
*/

#if defined(CONFIG_PPC_SPLPAR)
@@ -109,19 +150,59 @@ extern void __rw_yield(arch_rwlock_t *lock);
#define SHARED_PROCESSOR 0
#endif

-static inline void arch_spin_lock(arch_spinlock_t *lock)
+/*
+ * 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
+ * by atomically noting the tail and incrementing it by one (thus adding
+ * ourself to the queue and noting our position), then waiting until the head
+ * becomes equal to the the initial value of the tail.
+ *
+ * We use an asm covering *both* parts of the lock, to increment the tail and
+ * also load the position of the head, which takes care of memory ordering
+ * issues and should be optimal for the uncontended case. Note the tail must be
+ * in the high part, because a wide add increment of the low part would carry
+ * up and contaminate the high part.
+ */
+static __always_inline void arch_spin_lock(arch_spinlock_t *lock)
{
+ register struct __raw_tickets old, tmp,
+ inc = { .tail = TICKET_LOCK_INC };
+
CLEAR_IO_SYNC;
- while (1) {
- if (likely(__arch_spin_trylock(lock) == 0))
- break;
+ __asm__ __volatile__(
+"1: lwarx %0,0,%4 # arch_spin_lock\n"
+" add %1,%3,%0\n"
+ PPC405_ERR77(0, "%4")
+" stwcx. %1,0,%4\n"
+" bne- 1b"
+ : "=&r" (old), "=&r" (tmp), "+m" (lock->tickets)
+ : "r" (inc), "r" (&lock->tickets)
+ : "cc");
+
+ if (likely(old.head == old.tail)) {
+#if defined(CONFIG_PPC64)
+ lock->holder = LOCK_TOKEN;
+#endif
+ goto out;
+ }
+
+ for (;;) {
+ unsigned count = 100;
+
do {
+ if (ACCESS_ONCE(lock->tickets.head) == old.tail) {
+#if defined(CONFIG_PPC64)
+ lock->holder = LOCK_TOKEN;
+#endif
+ goto out;
+ }
HMT_low();
if (SHARED_PROCESSOR)
__spin_yield(lock);
- } while (unlikely(lock->slock != 0));
+ } while (--count);
HMT_medium();
}
+out: barrier(); /* make sure nothing creeps before the lock is taken */
}

static inline
@@ -131,7 +211,7 @@ void arch_spin_lock_flags(arch_spinlock_t *lock, unsigned long flags)

CLEAR_IO_SYNC;
while (1) {
- if (likely(__arch_spin_trylock(lock) == 0))
+ if (likely(__arch_spin_trylock(lock)))
break;
local_save_flags(flags_dis);
local_irq_restore(flags);
@@ -139,7 +219,7 @@ void arch_spin_lock_flags(arch_spinlock_t *lock, unsigned long flags)
HMT_low();
if (SHARED_PROCESSOR)
__spin_yield(lock);
- } while (unlikely(lock->slock != 0));
+ } while (arch_spin_is_locked(lock));
HMT_medium();
local_irq_restore(flags_dis);
}
@@ -147,10 +227,22 @@ void arch_spin_lock_flags(arch_spinlock_t *lock, unsigned long flags)

static inline void arch_spin_unlock(arch_spinlock_t *lock)
{
+ arch_spinlock_t old, new;
+
+#if defined(CONFIG_PPC64)
+ new.holder = 0;
+#endif
+ do {
+ old.tickets = ACCESS_ONCE(lock->tickets);
+#if defined(CONFIG_PPC64)
+ old.holder = lock->holder;
+#endif
+ new.tickets.head = old.tickets.head + TICKET_LOCK_INC;
+ new.tickets.tail = old.tickets.tail;
+ } while (unlikely(__arch_spin_cmpxchg_eq(lock, old, new)));
SYNC_IO;
__asm__ __volatile__("# arch_spin_unlock\n\t"
PPC_RELEASE_BARRIER: : :"memory");
- lock->slock = 0;
}

#ifdef CONFIG_PPC64
diff --git a/arch/powerpc/lib/locks.c b/arch/powerpc/lib/locks.c
index 0c9c8d7..4a57e32 100644
--- a/arch/powerpc/lib/locks.c
+++ b/arch/powerpc/lib/locks.c
@@ -27,7 +27,7 @@ void __spin_yield(arch_spinlock_t *lock)
{
unsigned int lock_value, holder_cpu, yield_count;

- lock_value = lock->slock;
+ lock_value = lock->holder;
if (lock_value == 0)
return;
holder_cpu = lock_value & 0xffff;
@@ -36,7 +36,7 @@ void __spin_yield(arch_spinlock_t *lock)
if ((yield_count & 1) == 0)
return; /* virtual cpu is currently running */
rmb();
- if (lock->slock != lock_value)
+ if (lock->holder != lock_value)
return; /* something has changed */
plpar_hcall_norets(H_CONFER,
get_hard_smp_processor_id(holder_cpu), yield_count);
@@ -70,7 +70,7 @@ void __rw_yield(arch_rwlock_t *rw)

void arch_spin_unlock_wait(arch_spinlock_t *lock)
{
- while (lock->slock) {
+ while (arch_spin_is_locked(lock)) {
HMT_low();
if (SHARED_PROCESSOR)
__spin_yield(lock);
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/