1 // SPDX-License-Identifier: GPL-2.0-or-later
5  * (C) Copyright 2013-2015 Hewlett-Packard Development Company, L.P.
6  * (C) Copyright 2013-2014,2018 Red Hat, Inc.
8  * (C) Copyright 2015 Hewlett-Packard Enterprise Development LP
33  * The basic principle of a queue-based spinlock can best be understood
34  * by studying a classic queue-based spinlock implementation called the
36  * Synchronization on Shared-Memory Multiprocessors by Mellor-Crummey and
47  * unlock the next pending (next->locked), we compress both these: {tail,
48  * next->locked} into a single u32 value.
52  * are at most 4 nesting levels, it can be encoded by a 2-bit number. Now
53  * we can encode the tail by combining the 2-bit nesting level with the cpu
55  * 32-bit word is now needed. Even though we only need 1 bit for the lock,
65  *      atomic operations on smaller 8-bit and 16-bit data types.
73  * On 64-bit architectures, the mcs_spinlock structure will be 16 bytes in
74  * size and four of them will fit nicely in one 64-byte cacheline. For
102  * Per-CPU queue node structures; we can never have more than 4 nested
105  * Exactly fits one 64-byte cacheline on a 64-bit architecture.
112  * We must be able to distinguish between no-tail and the tail at 0:0,
128 	int cpu = (tail >> _Q_TAIL_CPU_OFFSET) - 1;  in decode_tail()
137 	return &((struct qnode *)base + idx)->mcs;  in grab_mcs_node()
144  * clear_pending - clear the pending bit.
147  * *,1,* -> *,0,*
151 	WRITE_ONCE(lock->pending, 0);  in clear_pending()
155  * clear_pending_set_locked - take ownership and clear the pending bit.
158  * *,1,0 -> *,0,1
164 	WRITE_ONCE(lock->locked_pending, _Q_LOCKED_VAL);  in clear_pending_set_locked()
168  * xchg_tail - Put in the new queue tail code word & retrieve previous one
170  * @tail : The new queue tail code word
171  * Return: The previous queue tail code word
175  * p,*,* -> n,*,* ; prev = xchg(lock, node)
183 	return (u32)xchg_relaxed(&lock->tail,  in xchg_tail()
190  * clear_pending - clear the pending bit.
193  * *,1,* -> *,0,*
197 	atomic_andnot(_Q_PENDING_VAL, &lock->val);  in clear_pending()
201  * clear_pending_set_locked - take ownership and clear the pending bit.
204  * *,1,0 -> *,0,1
208 	atomic_add(-_Q_PENDING_VAL + _Q_LOCKED_VAL, &lock->val);  in clear_pending_set_locked()
212  * xchg_tail - Put in the new queue tail code word & retrieve previous one
214  * @tail : The new queue tail code word
215  * Return: The previous queue tail code word
219  * p,*,* -> n,*,* ; prev = xchg(lock, node)
223 	u32 old, new, val = atomic_read(&lock->val);  in xchg_tail()
232 		old = atomic_cmpxchg_relaxed(&lock->val, val, new);  in xchg_tail()
243  * queued_fetch_set_pending_acquire - fetch the whole lock value and set pending
247  * *,*,* -> *,1,*
252 	return atomic_fetch_or_acquire(_Q_PENDING_VAL, &lock->val);  in queued_fetch_set_pending_acquire()
257  * set_locked - Set the lock bit and own the lock
260  * *,*,0 -> *,0,1
264 	WRITE_ONCE(lock->locked, _Q_LOCKED_VAL);  in set_locked()
296  * queued_spin_lock_slowpath - acquire the queued spinlock
298  * @val: Current value of the queued spinlock 32-bit word
300  * (queue tail, pending bit, lock value)
304  * uncontended  (0,0,0) -:--> (0,0,1) ------------------------------:--> (*,*,0)
305  *                       :       | ^--------.------.             /  :
307  * pending               :    (0,1,1) +--> (0,1,0)   \           |  :
308  *                       :       | ^--'              |           |  :
310  * uncontended           :    (n,x,y) +--> (n,0,0) --'           |  :
311  *   queue               :       | ^--'                          |  :
313  * contended             :    (*,x,y) +--> (*,0,0) ---> (*,0,1) -'  :
314  *   queue               :         ^--'                             :
331 	 * Wait for in-progress pending->locked hand-overs with a bounded  in queued_spin_lock_slowpath()
334 	 * 0,1,0 -> 0,0,1  in queued_spin_lock_slowpath()
338 		val = atomic_cond_read_relaxed(&lock->val,  in queued_spin_lock_slowpath()
339 					       (VAL != _Q_PENDING_VAL) || !cnt--);  in queued_spin_lock_slowpath()
343 	 * If we observe any contention; queue.  in queued_spin_lock_slowpath()
346 		goto queue;  in queued_spin_lock_slowpath()
351 	 * 0,0,* -> 0,1,* -> 0,0,1 pending, trylock  in queued_spin_lock_slowpath()
358 	 * Undo and queue; our setting of PENDING might have made the  in queued_spin_lock_slowpath()
359 	 * n,0,0 -> 0,0,0 transition fail and it will now be waiting  in queued_spin_lock_slowpath()
368 		goto queue;  in queued_spin_lock_slowpath()
372 	 * We're pending, wait for the owner to go away.  in queued_spin_lock_slowpath()
374 	 * 0,1,1 -> *,1,0  in queued_spin_lock_slowpath()
376 	 * this wait loop must be a load-acquire such that we match the  in queued_spin_lock_slowpath()
377 	 * store-release that clears the locked bit and create lock  in queued_spin_lock_slowpath()
383 		smp_cond_load_acquire(&lock->locked, !VAL);  in queued_spin_lock_slowpath()
388 	 * 0,1,0 -> 0,0,1  in queued_spin_lock_slowpath()
398 queue:  in queued_spin_lock_slowpath()
402 	idx = node->count++;  in queued_spin_lock_slowpath()
426 	 * Keep counts of non-zero index values:  in queued_spin_lock_slowpath()
428 	lockevent_cond_inc(lock_use_node2 + idx - 1, idx);  in queued_spin_lock_slowpath()
431 	 * Ensure that we increment the head node->count before initialising  in queued_spin_lock_slowpath()
437 	node->locked = 0;  in queued_spin_lock_slowpath()
438 	node->next = NULL;  in queued_spin_lock_slowpath()
442 	 * We touched a (possibly) cold cacheline in the per-cpu queue node;  in queued_spin_lock_slowpath()
452 	 * @node into the waitqueue via WRITE_ONCE(prev->next, node) below.  in queued_spin_lock_slowpath()
461 	 * p,*,* -> n,*,*  in queued_spin_lock_slowpath()
467 	 * if there was a previous node; link it and wait until reaching the  in queued_spin_lock_slowpath()
474 		WRITE_ONCE(prev->next, node);  in queued_spin_lock_slowpath()
477 		arch_mcs_spin_lock_contended(&node->locked);  in queued_spin_lock_slowpath()
485 		next = READ_ONCE(node->next);  in queued_spin_lock_slowpath()
491 	 * we're at the head of the waitqueue, wait for the owner & pending to  in queued_spin_lock_slowpath()
494 	 * *,x,y -> *,0,0  in queued_spin_lock_slowpath()
496 	 * this wait loop must use a load-acquire such that we match the  in queued_spin_lock_slowpath()
497 	 * store-release that clears the locked bit and create lock  in queued_spin_lock_slowpath()
502 	 * the lock and return a non-zero value. So we have to skip the  in queued_spin_lock_slowpath()
503 	 * atomic_cond_read_acquire() call. As the next PV queue head hasn't  in queued_spin_lock_slowpath()
514 	val = atomic_cond_read_acquire(&lock->val, !(VAL & _Q_LOCKED_PENDING_MASK));  in queued_spin_lock_slowpath()
520 	 * n,0,0 -> 0,0,1 : lock, uncontended  in queued_spin_lock_slowpath()
521 	 * *,*,0 -> *,*,1 : lock, contended  in queued_spin_lock_slowpath()
523 	 * If the queue head is the only one in the queue (lock value == tail)  in queued_spin_lock_slowpath()
532 	 * n,0,1 -> 0,0,1  in queued_spin_lock_slowpath()
535 	 *       above wait condition, therefore any concurrent setting of  in queued_spin_lock_slowpath()
539 		if (atomic_try_cmpxchg_relaxed(&lock->val, &val, _Q_LOCKED_VAL))  in queued_spin_lock_slowpath()
545 	 * which will then detect the remaining tail and queue behind us  in queued_spin_lock_slowpath()
551 	 * contended path; wait for next if not observed yet, release.  in queued_spin_lock_slowpath()
554 		next = smp_cond_load_relaxed(&node->next, (VAL));  in queued_spin_lock_slowpath()
556 	arch_mcs_spin_unlock_contended(&next->locked);  in queued_spin_lock_slowpath()