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)
225 	old = atomic_read(&lock->val);  in xchg_tail()
233 	} while (!atomic_try_cmpxchg_relaxed(&lock->val, &old, new));  in xchg_tail()
240  * queued_fetch_set_pending_acquire - fetch the whole lock value and set pending
244  * *,*,* -> *,1,*
249 	return atomic_fetch_or_acquire(_Q_PENDING_VAL, &lock->val);  in queued_fetch_set_pending_acquire()
254  * set_locked - Set the lock bit and own the lock
257  * *,*,0 -> *,0,1
261 	WRITE_ONCE(lock->locked, _Q_LOCKED_VAL);  in set_locked()
293  * queued_spin_lock_slowpath - acquire the queued spinlock
295  * @val: Current value of the queued spinlock 32-bit word
297  * (queue tail, pending bit, lock value)
301  * uncontended  (0,0,0) -:--> (0,0,1) ------------------------------:--> (*,*,0)
302  *                       :       | ^--------.------.             /  :
304  * pending               :    (0,1,1) +--> (0,1,0)   \           |  :
305  *                       :       | ^--'              |           |  :
307  * uncontended           :    (n,x,y) +--> (n,0,0) --'           |  :
308  *   queue               :       | ^--'                          |  :
310  * contended             :    (*,x,y) +--> (*,0,0) ---> (*,0,1) -'  :
311  *   queue               :         ^--'                             :
328 	 * Wait for in-progress pending->locked hand-overs with a bounded  in queued_spin_lock_slowpath()
331 	 * 0,1,0 -> 0,0,1  in queued_spin_lock_slowpath()
335 		val = atomic_cond_read_relaxed(&lock->val,  in queued_spin_lock_slowpath()
336 					       (VAL != _Q_PENDING_VAL) || !cnt--);  in queued_spin_lock_slowpath()
340 	 * If we observe any contention; queue.  in queued_spin_lock_slowpath()
343 		goto queue;  in queued_spin_lock_slowpath()
348 	 * 0,0,* -> 0,1,* -> 0,0,1 pending, trylock  in queued_spin_lock_slowpath()
355 	 * Undo and queue; our setting of PENDING might have made the  in queued_spin_lock_slowpath()
356 	 * n,0,0 -> 0,0,0 transition fail and it will now be waiting  in queued_spin_lock_slowpath()
365 		goto queue;  in queued_spin_lock_slowpath()
369 	 * We're pending, wait for the owner to go away.  in queued_spin_lock_slowpath()
371 	 * 0,1,1 -> *,1,0  in queued_spin_lock_slowpath()
373 	 * this wait loop must be a load-acquire such that we match the  in queued_spin_lock_slowpath()
374 	 * store-release that clears the locked bit and create lock  in queued_spin_lock_slowpath()
380 		smp_cond_load_acquire(&lock->locked, !VAL);  in queued_spin_lock_slowpath()
385 	 * 0,1,0 -> 0,0,1  in queued_spin_lock_slowpath()
395 queue:  in queued_spin_lock_slowpath()
399 	idx = node->count++;  in queued_spin_lock_slowpath()
423 	 * Keep counts of non-zero index values:  in queued_spin_lock_slowpath()
425 	lockevent_cond_inc(lock_use_node2 + idx - 1, idx);  in queued_spin_lock_slowpath()
428 	 * Ensure that we increment the head node->count before initialising  in queued_spin_lock_slowpath()
434 	node->locked = 0;  in queued_spin_lock_slowpath()
435 	node->next = NULL;  in queued_spin_lock_slowpath()
439 	 * We touched a (possibly) cold cacheline in the per-cpu queue node;  in queued_spin_lock_slowpath()
449 	 * @node into the waitqueue via WRITE_ONCE(prev->next, node) below.  in queued_spin_lock_slowpath()
458 	 * p,*,* -> n,*,*  in queued_spin_lock_slowpath()
464 	 * if there was a previous node; link it and wait until reaching the  in queued_spin_lock_slowpath()
471 		WRITE_ONCE(prev->next, node);  in queued_spin_lock_slowpath()
474 		arch_mcs_spin_lock_contended(&node->locked);  in queued_spin_lock_slowpath()
482 		next = READ_ONCE(node->next);  in queued_spin_lock_slowpath()
488 	 * we're at the head of the waitqueue, wait for the owner & pending to  in queued_spin_lock_slowpath()
491 	 * *,x,y -> *,0,0  in queued_spin_lock_slowpath()
493 	 * this wait loop must use a load-acquire such that we match the  in queued_spin_lock_slowpath()
494 	 * store-release that clears the locked bit and create lock  in queued_spin_lock_slowpath()
499 	 * the lock and return a non-zero value. So we have to skip the  in queued_spin_lock_slowpath()
500 	 * atomic_cond_read_acquire() call. As the next PV queue head hasn't  in queued_spin_lock_slowpath()
511 	val = atomic_cond_read_acquire(&lock->val, !(VAL & _Q_LOCKED_PENDING_MASK));  in queued_spin_lock_slowpath()
517 	 * n,0,0 -> 0,0,1 : lock, uncontended  in queued_spin_lock_slowpath()
518 	 * *,*,0 -> *,*,1 : lock, contended  in queued_spin_lock_slowpath()
520 	 * If the queue head is the only one in the queue (lock value == tail)  in queued_spin_lock_slowpath()
529 	 * n,0,1 -> 0,0,1  in queued_spin_lock_slowpath()
532 	 *       above wait condition, therefore any concurrent setting of  in queued_spin_lock_slowpath()
536 		if (atomic_try_cmpxchg_relaxed(&lock->val, &val, _Q_LOCKED_VAL))  in queued_spin_lock_slowpath()
542 	 * which will then detect the remaining tail and queue behind us  in queued_spin_lock_slowpath()
548 	 * contended path; wait for next if not observed yet, release.  in queued_spin_lock_slowpath()
551 		next = smp_cond_load_relaxed(&node->next, (VAL));  in queued_spin_lock_slowpath()
553 	arch_mcs_spin_unlock_contended(&next->locked);  in queued_spin_lock_slowpath()