xref: /linux/kernel/bpf/rqspinlock.c (revision 3bb159366a13d8f5ead58f1cc1d0efa0183e951e)

// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * Resilient Queued Spin Lock
 *
 * (C) Copyright 2013-2015 Hewlett-Packard Development Company, L.P.
 * (C) Copyright 2013-2014,2018 Red Hat, Inc.
 * (C) Copyright 2015 Intel Corp.
 * (C) Copyright 2015 Hewlett-Packard Enterprise Development LP
 * (C) Copyright 2024-2025 Meta Platforms, Inc. and affiliates.
 *
 * Authors: Waiman Long <longman@redhat.com>
 *          Peter Zijlstra <peterz@infradead.org>
 *          Kumar Kartikeya Dwivedi <memxor@gmail.com>
 */

#include <linux/smp.h>
#include <linux/bug.h>
#include <linux/cpumask.h>
#include <linux/percpu.h>
#include <linux/hardirq.h>
#include <linux/mutex.h>
#include <linux/prefetch.h>
#include <asm/byteorder.h>
#include <asm/qspinlock.h>
#include <trace/events/lock.h>
#include <asm/rqspinlock.h>
#include <linux/timekeeping.h>

/*
 * Include queued spinlock definitions and statistics code
 */
#include "../locking/qspinlock.h"
#include "../locking/lock_events.h"

/*
 * The basic principle of a queue-based spinlock can best be understood
 * by studying a classic queue-based spinlock implementation called the
 * MCS lock. A copy of the original MCS lock paper ("Algorithms for Scalable
 * Synchronization on Shared-Memory Multiprocessors by Mellor-Crummey and
 * Scott") is available at
 *
 * https://bugzilla.kernel.org/show_bug.cgi?id=206115
 *
 * This queued spinlock implementation is based on the MCS lock, however to
 * make it fit the 4 bytes we assume spinlock_t to be, and preserve its
 * existing API, we must modify it somehow.
 *
 * In particular; where the traditional MCS lock consists of a tail pointer
 * (8 bytes) and needs the next pointer (another 8 bytes) of its own node to
 * unlock the next pending (next->locked), we compress both these: {tail,
 * next->locked} into a single u32 value.
 *
 * Since a spinlock disables recursion of its own context and there is a limit
 * to the contexts that can nest; namely: task, softirq, hardirq, nmi. As there
 * are at most 4 nesting levels, it can be encoded by a 2-bit number. Now
 * we can encode the tail by combining the 2-bit nesting level with the cpu
 * number. With one byte for the lock value and 3 bytes for the tail, only a
 * 32-bit word is now needed. Even though we only need 1 bit for the lock,
 * we extend it to a full byte to achieve better performance for architectures
 * that support atomic byte write.
 *
 * We also change the first spinner to spin on the lock bit instead of its
 * node; whereby avoiding the need to carry a node from lock to unlock, and
 * preserving existing lock API. This also makes the unlock code simpler and
 * faster.
 *
 * N.B. The current implementation only supports architectures that allow
 *      atomic operations on smaller 8-bit and 16-bit data types.
 *
 */

#include "../locking/mcs_spinlock.h"

struct rqspinlock_timeout {
	u64 timeout_end;
	u64 duration;
	u16 spin;
};

#define RES_TIMEOUT_VAL	2

static noinline int check_timeout(struct rqspinlock_timeout *ts)
{
	u64 time = ktime_get_mono_fast_ns();

	if (!ts->timeout_end) {
		ts->timeout_end = time + ts->duration;
		return 0;
	}

	if (time > ts->timeout_end)
		return -ETIMEDOUT;

	return 0;
}

/*
 * Do not amortize with spins when res_smp_cond_load_acquire is defined,
 * as the macro does internal amortization for us.
 */
#ifndef res_smp_cond_load_acquire
#define RES_CHECK_TIMEOUT(ts, ret)                    \
	({                                            \
		if (!(ts).spin++)                     \
			(ret) = check_timeout(&(ts)); \
		(ret);                                \
	})
#else
#define RES_CHECK_TIMEOUT(ts, ret, mask)	      \
	({ (ret) = check_timeout(&(ts)); })
#endif

/*
 * Initialize the 'spin' member.
 */
#define RES_INIT_TIMEOUT(ts) ({ (ts).spin = 1; })

/*
 * We only need to reset 'timeout_end', 'spin' will just wrap around as necessary.
 * Duration is defined for each spin attempt, so set it here.
 */
#define RES_RESET_TIMEOUT(ts, _duration) ({ (ts).timeout_end = 0; (ts).duration = _duration; })

/*
 * Per-CPU queue node structures; we can never have more than 4 nested
 * contexts: task, softirq, hardirq, nmi.
 *
 * Exactly fits one 64-byte cacheline on a 64-bit architecture.
 */
static DEFINE_PER_CPU_ALIGNED(struct qnode, rqnodes[_Q_MAX_NODES]);

#ifndef res_smp_cond_load_acquire
#define res_smp_cond_load_acquire(v, c) smp_cond_load_acquire(v, c)
#endif

#define res_atomic_cond_read_acquire(v, c) res_smp_cond_load_acquire(&(v)->counter, (c))

/**
 * resilient_queued_spin_lock_slowpath - acquire the queued spinlock
 * @lock: Pointer to queued spinlock structure
 * @val: Current value of the queued spinlock 32-bit word
 *
 * Return:
 * * 0		- Lock was acquired successfully.
 * * -ETIMEDOUT - Lock acquisition failed because of timeout.
 *
 * (queue tail, pending bit, lock value)
 *
 *              fast     :    slow                                  :    unlock
 *                       :                                          :
 * uncontended  (0,0,0) -:--> (0,0,1) ------------------------------:--> (*,*,0)
 *                       :       | ^--------.------.             /  :
 *                       :       v           \      \            |  :
 * pending               :    (0,1,1) +--> (0,1,0)   \           |  :
 *                       :       | ^--'              |           |  :
 *                       :       v                   |           |  :
 * uncontended           :    (n,x,y) +--> (n,0,0) --'           |  :
 *   queue               :       | ^--'                          |  :
 *                       :       v                               |  :
 * contended             :    (*,x,y) +--> (*,0,0) ---> (*,0,1) -'  :
 *   queue               :         ^--'                             :
 */
int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val)
{
	struct mcs_spinlock *prev, *next, *node;
	struct rqspinlock_timeout ts;
	int idx, ret = 0;
	u32 old, tail;

	BUILD_BUG_ON(CONFIG_NR_CPUS >= (1U << _Q_TAIL_CPU_BITS));

	RES_INIT_TIMEOUT(ts);

	/*
	 * Wait for in-progress pending->locked hand-overs with a bounded
	 * number of spins so that we guarantee forward progress.
	 *
	 * 0,1,0 -> 0,0,1
	 */
	if (val == _Q_PENDING_VAL) {
		int cnt = _Q_PENDING_LOOPS;
		val = atomic_cond_read_relaxed(&lock->val,
					       (VAL != _Q_PENDING_VAL) || !cnt--);
	}

	/*
	 * If we observe any contention; queue.
	 */
	if (val & ~_Q_LOCKED_MASK)
		goto queue;

	/*
	 * trylock || pending
	 *
	 * 0,0,* -> 0,1,* -> 0,0,1 pending, trylock
	 */
	val = queued_fetch_set_pending_acquire(lock);

	/*
	 * If we observe contention, there is a concurrent locker.
	 *
	 * Undo and queue; our setting of PENDING might have made the
	 * n,0,0 -> 0,0,0 transition fail and it will now be waiting
	 * on @next to become !NULL.
	 */
	if (unlikely(val & ~_Q_LOCKED_MASK)) {

		/* Undo PENDING if we set it. */
		if (!(val & _Q_PENDING_MASK))
			clear_pending(lock);

		goto queue;
	}

	/*
	 * We're pending, wait for the owner to go away.
	 *
	 * 0,1,1 -> *,1,0
	 *
	 * this wait loop must be a load-acquire such that we match the
	 * store-release that clears the locked bit and create lock
	 * sequentiality; this is because not all
	 * clear_pending_set_locked() implementations imply full
	 * barriers.
	 */
	if (val & _Q_LOCKED_MASK) {
		RES_RESET_TIMEOUT(ts, RES_DEF_TIMEOUT);
		res_smp_cond_load_acquire(&lock->locked, !VAL || RES_CHECK_TIMEOUT(ts, ret));
	}

	if (ret) {
		/*
		 * We waited for the locked bit to go back to 0, as the pending
		 * waiter, but timed out. We need to clear the pending bit since
		 * we own it. Once a stuck owner has been recovered, the lock
		 * must be restored to a valid state, hence removing the pending
		 * bit is necessary.
		 *
		 * *,1,* -> *,0,*
		 */
		clear_pending(lock);
		lockevent_inc(rqspinlock_lock_timeout);
		return ret;
	}

	/*
	 * take ownership and clear the pending bit.
	 *
	 * 0,1,0 -> 0,0,1
	 */
	clear_pending_set_locked(lock);
	lockevent_inc(lock_pending);
	return 0;

	/*
	 * End of pending bit optimistic spinning and beginning of MCS
	 * queuing.
	 */
queue:
	lockevent_inc(lock_slowpath);
	node = this_cpu_ptr(&rqnodes[0].mcs);
	idx = node->count++;
	tail = encode_tail(smp_processor_id(), idx);

	trace_contention_begin(lock, LCB_F_SPIN);

	/*
	 * 4 nodes are allocated based on the assumption that there will
	 * not be nested NMIs taking spinlocks. That may not be true in
	 * some architectures even though the chance of needing more than
	 * 4 nodes will still be extremely unlikely. When that happens,
	 * we fall back to spinning on the lock directly without using
	 * any MCS node. This is not the most elegant solution, but is
	 * simple enough.
	 */
	if (unlikely(idx >= _Q_MAX_NODES)) {
		lockevent_inc(lock_no_node);
		RES_RESET_TIMEOUT(ts, RES_DEF_TIMEOUT);
		while (!queued_spin_trylock(lock)) {
			if (RES_CHECK_TIMEOUT(ts, ret)) {
				lockevent_inc(rqspinlock_lock_timeout);
				break;
			}
			cpu_relax();
		}
		goto release;
	}

	node = grab_mcs_node(node, idx);

	/*
	 * Keep counts of non-zero index values:
	 */
	lockevent_cond_inc(lock_use_node2 + idx - 1, idx);

	/*
	 * Ensure that we increment the head node->count before initialising
	 * the actual node. If the compiler is kind enough to reorder these
	 * stores, then an IRQ could overwrite our assignments.
	 */
	barrier();

	node->locked = 0;
	node->next = NULL;

	/*
	 * We touched a (possibly) cold cacheline in the per-cpu queue node;
	 * attempt the trylock once more in the hope someone let go while we
	 * weren't watching.
	 */
	if (queued_spin_trylock(lock))
		goto release;

	/*
	 * Ensure that the initialisation of @node is complete before we
	 * publish the updated tail via xchg_tail() and potentially link
	 * @node into the waitqueue via WRITE_ONCE(prev->next, node) below.
	 */
	smp_wmb();

	/*
	 * Publish the updated tail.
	 * We have already touched the queueing cacheline; don't bother with
	 * pending stuff.
	 *
	 * p,*,* -> n,*,*
	 */
	old = xchg_tail(lock, tail);
	next = NULL;

	/*
	 * if there was a previous node; link it and wait until reaching the
	 * head of the waitqueue.
	 */
	if (old & _Q_TAIL_MASK) {
		int val;

		prev = decode_tail(old, rqnodes);

		/* Link @node into the waitqueue. */
		WRITE_ONCE(prev->next, node);

		val = arch_mcs_spin_lock_contended(&node->locked);
		if (val == RES_TIMEOUT_VAL) {
			ret = -EDEADLK;
			goto waitq_timeout;
		}

		/*
		 * While waiting for the MCS lock, the next pointer may have
		 * been set by another lock waiter. We optimistically load
		 * the next pointer & prefetch the cacheline for writing
		 * to reduce latency in the upcoming MCS unlock operation.
		 */
		next = READ_ONCE(node->next);
		if (next)
			prefetchw(next);
	}

	/*
	 * we're at the head of the waitqueue, wait for the owner & pending to
	 * go away.
	 *
	 * *,x,y -> *,0,0
	 *
	 * this wait loop must use a load-acquire such that we match the
	 * store-release that clears the locked bit and create lock
	 * sequentiality; this is because the set_locked() function below
	 * does not imply a full barrier.
	 *
	 * We use RES_DEF_TIMEOUT * 2 as the duration, as RES_DEF_TIMEOUT is
	 * meant to span maximum allowed time per critical section, and we may
	 * have both the owner of the lock and the pending bit waiter ahead of
	 * us.
	 */
	RES_RESET_TIMEOUT(ts, RES_DEF_TIMEOUT * 2);
	val = res_atomic_cond_read_acquire(&lock->val, !(VAL & _Q_LOCKED_PENDING_MASK) ||
					   RES_CHECK_TIMEOUT(ts, ret));

waitq_timeout:
	if (ret) {
		/*
		 * If the tail is still pointing to us, then we are the final waiter,
		 * and are responsible for resetting the tail back to 0. Otherwise, if
		 * the cmpxchg operation fails, we signal the next waiter to take exit
		 * and try the same. For a waiter with tail node 'n':
		 *
		 * n,*,* -> 0,*,*
		 *
		 * When performing cmpxchg for the whole word (NR_CPUS > 16k), it is
		 * possible locked/pending bits keep changing and we see failures even
		 * when we remain the head of wait queue. However, eventually,
		 * pending bit owner will unset the pending bit, and new waiters
		 * will queue behind us. This will leave the lock owner in
		 * charge, and it will eventually either set locked bit to 0, or
		 * leave it as 1, allowing us to make progress.
		 *
		 * We terminate the whole wait queue for two reasons. Firstly,
		 * we eschew per-waiter timeouts with one applied at the head of
		 * the wait queue.  This allows everyone to break out faster
		 * once we've seen the owner / pending waiter not responding for
		 * the timeout duration from the head.  Secondly, it avoids
		 * complicated synchronization, because when not leaving in FIFO
		 * order, prev's next pointer needs to be fixed up etc.
		 */
		if (!try_cmpxchg_tail(lock, tail, 0)) {
			next = smp_cond_load_relaxed(&node->next, VAL);
			WRITE_ONCE(next->locked, RES_TIMEOUT_VAL);
		}
		lockevent_inc(rqspinlock_lock_timeout);
		goto release;
	}

	/*
	 * claim the lock:
	 *
	 * n,0,0 -> 0,0,1 : lock, uncontended
	 * *,*,0 -> *,*,1 : lock, contended
	 *
	 * If the queue head is the only one in the queue (lock value == tail)
	 * and nobody is pending, clear the tail code and grab the lock.
	 * Otherwise, we only need to grab the lock.
	 */

	/*
	 * Note: at this point: (val & _Q_PENDING_MASK) == 0, because of the
	 *       above wait condition, therefore any concurrent setting of
	 *       PENDING will make the uncontended transition fail.
	 */
	if ((val & _Q_TAIL_MASK) == tail) {
		if (atomic_try_cmpxchg_relaxed(&lock->val, &val, _Q_LOCKED_VAL))
			goto release; /* No contention */
	}

	/*
	 * Either somebody is queued behind us or _Q_PENDING_VAL got set
	 * which will then detect the remaining tail and queue behind us
	 * ensuring we'll see a @next.
	 */
	set_locked(lock);

	/*
	 * contended path; wait for next if not observed yet, release.
	 */
	if (!next)
		next = smp_cond_load_relaxed(&node->next, (VAL));

	arch_mcs_spin_unlock_contended(&next->locked);

release:
	trace_contention_end(lock, 0);

	/*
	 * release the node
	 */
	__this_cpu_dec(rqnodes[0].mcs.count);
	return ret;
}
EXPORT_SYMBOL_GPL(resilient_queued_spin_lock_slowpath);