[linux-2.6-block.git] / kernel / locking / qspinlock.c

// SPDX-License-Identifier: GPL-2.0-or-later
/*
 * Queued spinlock
 *
 * (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
 *
 * Authors: Waiman Long <longman@redhat.com>
 *          Peter Zijlstra <peterz@infradead.org>
 */

#ifndef _GEN_PV_LOCK_SLOWPATH

#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 queued spinlock definitions and statistics code
 */
#include "qspinlock.h"
#include "qspinlock_stat.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 "mcs_spinlock.h"

/*
 * 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.
 *
 * PV doubles the storage and uses the second cacheline for PV state.
 */
static DEFINE_PER_CPU_ALIGNED(struct qnode, qnodes[_Q_MAX_NODES]);

/*
 * Generate the native code for queued_spin_unlock_slowpath(); provide NOPs for
 * all the PV callbacks.
 */

static __always_inline void __pv_init_node(struct mcs_spinlock *node) { }
static __always_inline void __pv_wait_node(struct mcs_spinlock *node,
					   struct mcs_spinlock *prev) { }
static __always_inline void __pv_kick_node(struct qspinlock *lock,
					   struct mcs_spinlock *node) { }
static __always_inline u32  __pv_wait_head_or_lock(struct qspinlock *lock,
						   struct mcs_spinlock *node)
						   { return 0; }

#define pv_enabled()		false

#define pv_init_node		__pv_init_node
#define pv_wait_node		__pv_wait_node
#define pv_kick_node		__pv_kick_node
#define pv_wait_head_or_lock	__pv_wait_head_or_lock

#ifdef CONFIG_PARAVIRT_SPINLOCKS
#define queued_spin_lock_slowpath	native_queued_spin_lock_slowpath
#endif

#endif /* _GEN_PV_LOCK_SLOWPATH */

/**
 * queued_spin_lock_slowpath - acquire the queued spinlock
 * @lock: Pointer to queued spinlock structure
 * @val: Current value of the queued spinlock 32-bit word
 *
 * (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               :         ^--'                             :
 */
void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
{
	struct mcs_spinlock *prev, *next, *node;
	u32 old, tail;
	int idx;

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

	if (pv_enabled())
		goto pv_queue;

	if (virt_spin_lock(lock))
		return;

	/*
	 * 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)
		smp_cond_load_acquire(&lock->locked, !VAL);

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

	/*
	 * End of pending bit optimistic spinning and beginning of MCS
	 * queuing.
	 */
queue:
	lockevent_inc(lock_slowpath);
pv_queue:
	node = this_cpu_ptr(&qnodes[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);
		while (!queued_spin_trylock(lock))
			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;
	pv_init_node(node);

	/*
	 * 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) {
		prev = decode_tail(old, qnodes);

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

		pv_wait_node(node, prev);
		arch_mcs_spin_lock_contended(&node->locked);

		/*
		 * 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.
	 *
	 * The PV pv_wait_head_or_lock function, if active, will acquire
	 * the lock and return a non-zero value. So we have to skip the
	 * atomic_cond_read_acquire() call. As the next PV queue head hasn't
	 * been designated yet, there is no way for the locked value to become
	 * _Q_SLOW_VAL. So both the set_locked() and the
	 * atomic_cmpxchg_relaxed() calls will be safe.
	 *
	 * If PV isn't active, 0 will be returned instead.
	 *
	 */
	if ((val = pv_wait_head_or_lock(lock, node)))
		goto locked;

	val = atomic_cond_read_acquire(&lock->val, !(VAL & _Q_LOCKED_PENDING_MASK));

locked:
	/*
	 * 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.
	 */

	/*
	 * In the PV case we might already have _Q_LOCKED_VAL set, because
	 * of lock stealing; therefore we must also allow:
	 *
	 * n,0,1 -> 0,0,1
	 *
	 * 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);
	pv_kick_node(lock, next);

release:
	trace_contention_end(lock, 0);

	/*
	 * release the node
	 */
	__this_cpu_dec(qnodes[0].mcs.count);
}
EXPORT_SYMBOL(queued_spin_lock_slowpath);

/*
 * Generate the paravirt code for queued_spin_unlock_slowpath().
 */
#if !defined(_GEN_PV_LOCK_SLOWPATH) && defined(CONFIG_PARAVIRT_SPINLOCKS)
#define _GEN_PV_LOCK_SLOWPATH

#undef  pv_enabled
#define pv_enabled()	true

#undef pv_init_node
#undef pv_wait_node
#undef pv_kick_node
#undef pv_wait_head_or_lock

#undef  queued_spin_lock_slowpath
#define queued_spin_lock_slowpath	__pv_queued_spin_lock_slowpath

#include "qspinlock_paravirt.h"
#include "qspinlock.c"

bool nopvspin;
static __init int parse_nopvspin(char *arg)
{
	nopvspin = true;
	return 0;
}
early_param("nopvspin", parse_nopvspin);
#endif
Commit	Line	Data
	1	// SPDX-License-Identifier: GPL-2.0-or-later
	2	/*
	3	* Queued spinlock
	4	*
	5	* (C) Copyright 2013-2015 Hewlett-Packard Development Company, L.P.
	6	* (C) Copyright 2013-2014,2018 Red Hat, Inc.
	7	* (C) Copyright 2015 Intel Corp.
	8	* (C) Copyright 2015 Hewlett-Packard Enterprise Development LP
	9	*
	10	* Authors: Waiman Long <longman@redhat.com>
	11	* Peter Zijlstra <peterz@infradead.org>
	12	*/
	13
	14	#ifndef _GEN_PV_LOCK_SLOWPATH
	15
	16	#include <linux/smp.h>
	17	#include <linux/bug.h>
	18	#include <linux/cpumask.h>
	19	#include <linux/percpu.h>
	20	#include <linux/hardirq.h>
	21	#include <linux/mutex.h>
	22	#include <linux/prefetch.h>
	23	#include <asm/byteorder.h>
	24	#include <asm/qspinlock.h>
	25	#include <trace/events/lock.h>
	26
	27	/*
	28	* Include queued spinlock definitions and statistics code
	29	*/
	30	#include "qspinlock.h"
	31	#include "qspinlock_stat.h"
	32
	33	/*
	34	* The basic principle of a queue-based spinlock can best be understood
	35	* by studying a classic queue-based spinlock implementation called the
	36	* MCS lock. A copy of the original MCS lock paper ("Algorithms for Scalable
	37	* Synchronization on Shared-Memory Multiprocessors by Mellor-Crummey and
	38	* Scott") is available at
	39	*
	40	* https://bugzilla.kernel.org/show_bug.cgi?id=206115
	41	*
	42	* This queued spinlock implementation is based on the MCS lock, however to
	43	* make it fit the 4 bytes we assume spinlock_t to be, and preserve its
	44	* existing API, we must modify it somehow.
	45	*
	46	* In particular; where the traditional MCS lock consists of a tail pointer
	47	* (8 bytes) and needs the next pointer (another 8 bytes) of its own node to
	48	* unlock the next pending (next->locked), we compress both these: {tail,
	49	* next->locked} into a single u32 value.
	50	*
	51	* Since a spinlock disables recursion of its own context and there is a limit
	52	* to the contexts that can nest; namely: task, softirq, hardirq, nmi. As there
	53	* are at most 4 nesting levels, it can be encoded by a 2-bit number. Now
	54	* we can encode the tail by combining the 2-bit nesting level with the cpu
	55	* number. With one byte for the lock value and 3 bytes for the tail, only a
	56	* 32-bit word is now needed. Even though we only need 1 bit for the lock,
	57	* we extend it to a full byte to achieve better performance for architectures
	58	* that support atomic byte write.
	59	*
	60	* We also change the first spinner to spin on the lock bit instead of its
	61	* node; whereby avoiding the need to carry a node from lock to unlock, and
	62	* preserving existing lock API. This also makes the unlock code simpler and
	63	* faster.
	64	*
	65	* N.B. The current implementation only supports architectures that allow
	66	* atomic operations on smaller 8-bit and 16-bit data types.
	67	*
	68	*/
	69
	70	#include "mcs_spinlock.h"
	71
	72	/*
	73	* Per-CPU queue node structures; we can never have more than 4 nested
	74	* contexts: task, softirq, hardirq, nmi.
	75	*
	76	* Exactly fits one 64-byte cacheline on a 64-bit architecture.
	77	*
	78	* PV doubles the storage and uses the second cacheline for PV state.
	79	*/
	80	static DEFINE_PER_CPU_ALIGNED(struct qnode, qnodes[_Q_MAX_NODES]);
	81
	82	/*
	83	* Generate the native code for queued_spin_unlock_slowpath(); provide NOPs for
	84	* all the PV callbacks.
	85	*/
	86
	87	static __always_inline void __pv_init_node(struct mcs_spinlock *node) { }
	88	static __always_inline void __pv_wait_node(struct mcs_spinlock *node,
	89	struct mcs_spinlock *prev) { }
	90	static __always_inline void __pv_kick_node(struct qspinlock *lock,
	91	struct mcs_spinlock *node) { }
	92	static __always_inline u32 __pv_wait_head_or_lock(struct qspinlock *lock,
	93	struct mcs_spinlock *node)
	94	{ return 0; }
	95
	96	#define pv_enabled() false
	97
	98	#define pv_init_node __pv_init_node
	99	#define pv_wait_node __pv_wait_node
	100	#define pv_kick_node __pv_kick_node
	101	#define pv_wait_head_or_lock __pv_wait_head_or_lock
	102
	103	#ifdef CONFIG_PARAVIRT_SPINLOCKS
	104	#define queued_spin_lock_slowpath native_queued_spin_lock_slowpath
	105	#endif
	106
	107	#endif /* _GEN_PV_LOCK_SLOWPATH */
	108
	109	/**
	110	* queued_spin_lock_slowpath - acquire the queued spinlock
	111	* @lock: Pointer to queued spinlock structure
	112	* @val: Current value of the queued spinlock 32-bit word
	113	*
	114	* (queue tail, pending bit, lock value)
	115	*
	116	* fast : slow : unlock
	117	* : :
	118	* uncontended (0,0,0) -:--> (0,0,1) ------------------------------:--> (,,0)
	119	* : \| ^--------.------. / :
	120	* : v \ \ \| :
	121	* pending : (0,1,1) +--> (0,1,0) \ \| :
	122	* : \| ^--' \| \| :
	123	* : v \| \| :
	124	* uncontended : (n,x,y) +--> (n,0,0) --' \| :
	125	* queue : \| ^--' \| :
	126	* : v \| :
	127	* contended : (,x,y) +--> (,0,0) ---> (*,0,1) -' :
	128	* queue : ^--' :
	129	*/
	130	void __lockfunc queued_spin_lock_slowpath(struct qspinlock *lock, u32 val)
	131	{
	132	struct mcs_spinlock prev, next, *node;
	133	u32 old, tail;
	134	int idx;
	135
	136	BUILD_BUG_ON(CONFIG_NR_CPUS >= (1U << _Q_TAIL_CPU_BITS));
	137
	138	if (pv_enabled())
	139	goto pv_queue;
	140
	141	if (virt_spin_lock(lock))
	142	return;
	143
	144	/*
	145	* Wait for in-progress pending->locked hand-overs with a bounded
	146	* number of spins so that we guarantee forward progress.
	147	*
	148	* 0,1,0 -> 0,0,1
	149	*/
	150	if (val == _Q_PENDING_VAL) {
	151	int cnt = _Q_PENDING_LOOPS;
	152	val = atomic_cond_read_relaxed(&lock->val,
	153	(VAL != _Q_PENDING_VAL) \|\| !cnt--);
	154	}
	155
	156	/*
	157	* If we observe any contention; queue.
	158	*/
	159	if (val & ~_Q_LOCKED_MASK)
	160	goto queue;
	161
	162	/*
	163	* trylock \|\| pending
	164	*
	165	* 0,0,* -> 0,1,* -> 0,0,1 pending, trylock
	166	*/
	167	val = queued_fetch_set_pending_acquire(lock);
	168
	169	/*
	170	* If we observe contention, there is a concurrent locker.
	171	*
	172	* Undo and queue; our setting of PENDING might have made the
	173	* n,0,0 -> 0,0,0 transition fail and it will now be waiting
	174	* on @next to become !NULL.
	175	*/
	176	if (unlikely(val & ~_Q_LOCKED_MASK)) {
	177
	178	/* Undo PENDING if we set it. */
	179	if (!(val & _Q_PENDING_MASK))
	180	clear_pending(lock);
	181
	182	goto queue;
	183	}
	184
	185	/*
	186	* We're pending, wait for the owner to go away.
	187	*
	188	* 0,1,1 -> *,1,0
	189	*
	190	* this wait loop must be a load-acquire such that we match the
	191	* store-release that clears the locked bit and create lock
	192	* sequentiality; this is because not all
	193	* clear_pending_set_locked() implementations imply full
	194	* barriers.
	195	*/
	196	if (val & _Q_LOCKED_MASK)
	197	smp_cond_load_acquire(&lock->locked, !VAL);
	198
	199	/*
	200	* take ownership and clear the pending bit.
	201	*
	202	* 0,1,0 -> 0,0,1
	203	*/
	204	clear_pending_set_locked(lock);
	205	lockevent_inc(lock_pending);
	206	return;
	207
	208	/*
	209	* End of pending bit optimistic spinning and beginning of MCS
	210	* queuing.
	211	*/
	212	queue:
	213	lockevent_inc(lock_slowpath);
	214	pv_queue:
	215	node = this_cpu_ptr(&qnodes[0].mcs);
	216	idx = node->count++;
	217	tail = encode_tail(smp_processor_id(), idx);
	218
	219	trace_contention_begin(lock, LCB_F_SPIN);
	220
	221	/*
	222	* 4 nodes are allocated based on the assumption that there will
	223	* not be nested NMIs taking spinlocks. That may not be true in
	224	* some architectures even though the chance of needing more than
	225	* 4 nodes will still be extremely unlikely. When that happens,
	226	* we fall back to spinning on the lock directly without using
	227	* any MCS node. This is not the most elegant solution, but is
	228	* simple enough.
	229	*/
	230	if (unlikely(idx >= _Q_MAX_NODES)) {
	231	lockevent_inc(lock_no_node);
	232	while (!queued_spin_trylock(lock))
	233	cpu_relax();
	234	goto release;
	235	}
	236
	237	node = grab_mcs_node(node, idx);
	238
	239	/*
	240	* Keep counts of non-zero index values:
	241	*/
	242	lockevent_cond_inc(lock_use_node2 + idx - 1, idx);
	243
	244	/*
	245	* Ensure that we increment the head node->count before initialising
	246	* the actual node. If the compiler is kind enough to reorder these
	247	* stores, then an IRQ could overwrite our assignments.
	248	*/
	249	barrier();
	250
	251	node->locked = 0;
	252	node->next = NULL;
	253	pv_init_node(node);
	254
	255	/*
	256	* We touched a (possibly) cold cacheline in the per-cpu queue node;
	257	* attempt the trylock once more in the hope someone let go while we
	258	* weren't watching.
	259	*/
	260	if (queued_spin_trylock(lock))
	261	goto release;
	262
	263	/*
	264	* Ensure that the initialisation of @node is complete before we
	265	* publish the updated tail via xchg_tail() and potentially link
	266	* @node into the waitqueue via WRITE_ONCE(prev->next, node) below.
	267	*/
	268	smp_wmb();
	269
	270	/*
	271	* Publish the updated tail.
	272	* We have already touched the queueing cacheline; don't bother with
	273	* pending stuff.
	274	*
	275	* p,, -> n,,
	276	*/
	277	old = xchg_tail(lock, tail);
	278	next = NULL;
	279
	280	/*
	281	* if there was a previous node; link it and wait until reaching the
	282	* head of the waitqueue.
	283	*/
	284	if (old & _Q_TAIL_MASK) {
	285	prev = decode_tail(old, qnodes);
	286
	287	/* Link @node into the waitqueue. */
	288	WRITE_ONCE(prev->next, node);
	289
	290	pv_wait_node(node, prev);
	291	arch_mcs_spin_lock_contended(&node->locked);
	292
	293	/*
	294	* While waiting for the MCS lock, the next pointer may have
	295	* been set by another lock waiter. We optimistically load
	296	* the next pointer & prefetch the cacheline for writing
	297	* to reduce latency in the upcoming MCS unlock operation.
	298	*/
	299	next = READ_ONCE(node->next);
	300	if (next)
	301	prefetchw(next);
	302	}
	303
	304	/*
	305	* we're at the head of the waitqueue, wait for the owner & pending to
	306	* go away.
	307	*
	308	* ,x,y -> ,0,0
	309	*
	310	* this wait loop must use a load-acquire such that we match the
	311	* store-release that clears the locked bit and create lock
	312	* sequentiality; this is because the set_locked() function below
	313	* does not imply a full barrier.
	314	*
	315	* The PV pv_wait_head_or_lock function, if active, will acquire
	316	* the lock and return a non-zero value. So we have to skip the
	317	* atomic_cond_read_acquire() call. As the next PV queue head hasn't
	318	* been designated yet, there is no way for the locked value to become
	319	* _Q_SLOW_VAL. So both the set_locked() and the
	320	* atomic_cmpxchg_relaxed() calls will be safe.
	321	*
	322	* If PV isn't active, 0 will be returned instead.
	323	*
	324	*/
	325	if ((val = pv_wait_head_or_lock(lock, node)))
	326	goto locked;
	327
	328	val = atomic_cond_read_acquire(&lock->val, !(VAL & _Q_LOCKED_PENDING_MASK));
	329
	330	locked:
	331	/*
	332	* claim the lock:
	333	*
	334	* n,0,0 -> 0,0,1 : lock, uncontended
	335	* ,,0 -> ,,1 : lock, contended
	336	*
	337	* If the queue head is the only one in the queue (lock value == tail)
	338	* and nobody is pending, clear the tail code and grab the lock.
	339	* Otherwise, we only need to grab the lock.
	340	*/
	341
	342	/*
	343	* In the PV case we might already have _Q_LOCKED_VAL set, because
	344	* of lock stealing; therefore we must also allow:
	345	*
	346	* n,0,1 -> 0,0,1
	347	*
	348	* Note: at this point: (val & _Q_PENDING_MASK) == 0, because of the
	349	* above wait condition, therefore any concurrent setting of
	350	* PENDING will make the uncontended transition fail.
	351	*/
	352	if ((val & _Q_TAIL_MASK) == tail) {
	353	if (atomic_try_cmpxchg_relaxed(&lock->val, &val, _Q_LOCKED_VAL))
	354	goto release; /* No contention */
	355	}
	356
	357	/*
	358	* Either somebody is queued behind us or _Q_PENDING_VAL got set
	359	* which will then detect the remaining tail and queue behind us
	360	* ensuring we'll see a @next.
	361	*/
	362	set_locked(lock);
	363
	364	/*
	365	* contended path; wait for next if not observed yet, release.
	366	*/
	367	if (!next)
	368	next = smp_cond_load_relaxed(&node->next, (VAL));
	369
	370	arch_mcs_spin_unlock_contended(&next->locked);
	371	pv_kick_node(lock, next);
	372
	373	release:
	374	trace_contention_end(lock, 0);
	375
	376	/*
	377	* release the node
	378	*/
	379	__this_cpu_dec(qnodes[0].mcs.count);
	380	}
	381	EXPORT_SYMBOL(queued_spin_lock_slowpath);
	382
	383	/*
	384	* Generate the paravirt code for queued_spin_unlock_slowpath().
	385	*/
	386	#if !defined(_GEN_PV_LOCK_SLOWPATH) && defined(CONFIG_PARAVIRT_SPINLOCKS)
	387	#define _GEN_PV_LOCK_SLOWPATH
	388
	389	#undef pv_enabled
	390	#define pv_enabled() true
	391
	392	#undef pv_init_node
	393	#undef pv_wait_node
	394	#undef pv_kick_node
	395	#undef pv_wait_head_or_lock
	396
	397	#undef queued_spin_lock_slowpath
	398	#define queued_spin_lock_slowpath __pv_queued_spin_lock_slowpath
	399
	400	#include "qspinlock_paravirt.h"
	401	#include "qspinlock.c"
	402
	403	bool nopvspin;
	404	static __init int parse_nopvspin(char *arg)
	405	{
	406	nopvspin = true;
	407	return 0;
	408	}
	409	early_param("nopvspin", parse_nopvspin);
	410	#endif