1/* SPDX-License-Identifier: GPL-2.0 */
  2
  3/*
  4 * 'Generic' ticket-lock implementation.
  5 *
  6 * It relies on atomic_fetch_add() having well defined forward progress
  7 * guarantees under contention. If your architecture cannot provide this, stick
  8 * to a test-and-set lock.
  9 *
 10 * It also relies on atomic_fetch_add() being safe vs smp_store_release() on a
 11 * sub-word of the value. This is generally true for anything LL/SC although
 12 * you'd be hard pressed to find anything useful in architecture specifications
 13 * about this. If your architecture cannot do this you might be better off with
 14 * a test-and-set.
 15 *
 16 * It further assumes atomic_*_release() + atomic_*_acquire() is RCpc and hence
 17 * uses atomic_fetch_add() which is RCsc to create an RCsc hot path, along with
 18 * a full fence after the spin to upgrade the otherwise-RCpc
 19 * atomic_cond_read_acquire().
 20 *
 21 * The implementation uses smp_cond_load_acquire() to spin, so if the
 22 * architecture has WFE like instructions to sleep instead of poll for word
 23 * modifications be sure to implement that (see ARM64 for example).
 24 *
 25 */
 26
 27#ifndef __ASM_GENERIC_TICKET_SPINLOCK_H
 28#define __ASM_GENERIC_TICKET_SPINLOCK_H
 29
 30#include <linux/atomic.h>
 31#include <asm-generic/spinlock_types.h>
 32
 33static __always_inline void ticket_spin_lock(arch_spinlock_t *lock)
 34{
 35	u32 val = atomic_fetch_add(1<<16, &lock->val);
 36	u16 ticket = val >> 16;
 37
 38	if (ticket == (u16)val)
 39		return;
 40
 41	/*
 42	 * atomic_cond_read_acquire() is RCpc, but rather than defining a
 43	 * custom cond_read_rcsc() here we just emit a full fence.  We only
 44	 * need the prior reads before subsequent writes ordering from
 45	 * smb_mb(), but as atomic_cond_read_acquire() just emits reads and we
 46	 * have no outstanding writes due to the atomic_fetch_add() the extra
 47	 * orderings are free.
 48	 */
 49	atomic_cond_read_acquire(&lock->val, ticket == (u16)VAL);
 50	smp_mb();
 51}
 52
 53static __always_inline bool ticket_spin_trylock(arch_spinlock_t *lock)
 54{
 55	u32 old = atomic_read(&lock->val);
 56
 57	if ((old >> 16) != (old & 0xffff))
 58		return false;
 59
 60	return atomic_try_cmpxchg(&lock->val, &old, old + (1<<16)); /* SC, for RCsc */
 61}
 62
 63static __always_inline void ticket_spin_unlock(arch_spinlock_t *lock)
 64{
 65	u16 *ptr = (u16 *)lock + IS_ENABLED(CONFIG_CPU_BIG_ENDIAN);
 66	u32 val = atomic_read(&lock->val);
 67
 68	smp_store_release(ptr, (u16)val + 1);
 69}
 70
 71static __always_inline int ticket_spin_value_unlocked(arch_spinlock_t lock)
 72{
 73	u32 val = lock.val.counter;
 74
 75	return ((val >> 16) == (val & 0xffff));
 76}
 77
 78static __always_inline int ticket_spin_is_locked(arch_spinlock_t *lock)
 79{
 80	arch_spinlock_t val = READ_ONCE(*lock);
 81
 82	return !ticket_spin_value_unlocked(val);
 83}
 84
 85static __always_inline int ticket_spin_is_contended(arch_spinlock_t *lock)
 86{
 87	u32 val = atomic_read(&lock->val);
 88
 89	return (s16)((val >> 16) - (val & 0xffff)) > 1;
 90}
 91
 92#ifndef __no_arch_spinlock_redefine
 93/*
 94 * Remapping spinlock architecture specific functions to the corresponding
 95 * ticket spinlock functions.
 96 */
 97#define arch_spin_is_locked(l)		ticket_spin_is_locked(l)
 98#define arch_spin_is_contended(l)	ticket_spin_is_contended(l)
 99#define arch_spin_value_unlocked(l)	ticket_spin_value_unlocked(l)
100#define arch_spin_lock(l)		ticket_spin_lock(l)
101#define arch_spin_trylock(l)		ticket_spin_trylock(l)
102#define arch_spin_unlock(l)		ticket_spin_unlock(l)
103#endif
104
105#endif /* __ASM_GENERIC_TICKET_SPINLOCK_H */