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
34  * The basic principle of a queue-based spinlock can best be understood
35  * by studying a classic queue-based spinlock implementation called the
37  * Synchronization on Shared-Memory Multiprocessors by Mellor-Crummey and
48  * unlock the next pending (next->locked), we compress both these: {tail,
49  * next->locked} into a single u32 value.
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
56  * 32-bit word is now needed. Even though we only need 1 bit for the lock,
66  *      atomic operations on smaller 8-bit and 16-bit data types.
73  * Per-CPU queue node structures; we can never have more than 4 nested
76  * Exactly fits one 64-byte cacheline on a 64-bit architecture.
110  * queued_spin_lock_slowpath - acquire the queued spinlock
112  * @val: Current value of the queued spinlock 32-bit word
114  * (queue tail, pending bit, lock value)
118  * uncontended  (0,0,0) -:--> (0,0,1) ------------------------------:--> (*,*,0)
119  *                       :       | ^--------.------.             /  :
121  * pending               :    (0,1,1) +--> (0,1,0)   \           |  :
122  *                       :       | ^--'              |           |  :
124  * uncontended           :    (n,x,y) +--> (n,0,0) --'           |  :
125  *   queue               :       | ^--'                          |  :
127  * contended             :    (*,x,y) +--> (*,0,0) ---> (*,0,1) -'  :
128  *   queue               :         ^--'                             :
145 	 * Wait for in-progress pending->locked hand-overs with a bounded  in queued_spin_lock_slowpath()
148 	 * 0,1,0 -> 0,0,1  in queued_spin_lock_slowpath()
152 		val = atomic_cond_read_relaxed(&lock->val,  in queued_spin_lock_slowpath()
153 					       (VAL != _Q_PENDING_VAL) || !cnt--);  in queued_spin_lock_slowpath()
157 	 * If we observe any contention; queue.  in queued_spin_lock_slowpath()
160 		goto queue;  in queued_spin_lock_slowpath()
165 	 * 0,0,* -> 0,1,* -> 0,0,1 pending, trylock  in queued_spin_lock_slowpath()
172 	 * Undo and queue; our setting of PENDING might have made the  in queued_spin_lock_slowpath()
173 	 * n,0,0 -> 0,0,0 transition fail and it will now be waiting  in queued_spin_lock_slowpath()
182 		goto queue;  in queued_spin_lock_slowpath()
186 	 * We're pending, wait for the owner to go away.  in queued_spin_lock_slowpath()
188 	 * 0,1,1 -> *,1,0  in queued_spin_lock_slowpath()
190 	 * this wait loop must be a load-acquire such that we match the  in queued_spin_lock_slowpath()
191 	 * store-release that clears the locked bit and create lock  in queued_spin_lock_slowpath()
197 		smp_cond_load_acquire(&lock->locked, !VAL);  in queued_spin_lock_slowpath()
202 	 * 0,1,0 -> 0,0,1  in queued_spin_lock_slowpath()
212 queue:  in queued_spin_lock_slowpath()
216 	idx = node->count++;  in queued_spin_lock_slowpath()
240 	 * Keep counts of non-zero index values:  in queued_spin_lock_slowpath()
242 	lockevent_cond_inc(lock_use_node2 + idx - 1, idx);  in queued_spin_lock_slowpath()
245 	 * Ensure that we increment the head node->count before initialising  in queued_spin_lock_slowpath()
251 	node->locked = 0;  in queued_spin_lock_slowpath()
252 	node->next = NULL;  in queued_spin_lock_slowpath()
256 	 * We touched a (possibly) cold cacheline in the per-cpu queue node;  in queued_spin_lock_slowpath()
266 	 * @node into the waitqueue via WRITE_ONCE(prev->next, node) below.  in queued_spin_lock_slowpath()
275 	 * p,*,* -> n,*,*  in queued_spin_lock_slowpath()
281 	 * if there was a previous node; link it and wait until reaching the  in queued_spin_lock_slowpath()
288 		WRITE_ONCE(prev->next, node);  in queued_spin_lock_slowpath()
291 		arch_mcs_spin_lock_contended(&node->locked);  in queued_spin_lock_slowpath()
299 		next = READ_ONCE(node->next);  in queued_spin_lock_slowpath()
305 	 * we're at the head of the waitqueue, wait for the owner & pending to  in queued_spin_lock_slowpath()
308 	 * *,x,y -> *,0,0  in queued_spin_lock_slowpath()
310 	 * this wait loop must use a load-acquire such that we match the  in queued_spin_lock_slowpath()
311 	 * store-release that clears the locked bit and create lock  in queued_spin_lock_slowpath()
316 	 * the lock and return a non-zero value. So we have to skip the  in queued_spin_lock_slowpath()
317 	 * atomic_cond_read_acquire() call. As the next PV queue head hasn't  in queued_spin_lock_slowpath()
328 	val = atomic_cond_read_acquire(&lock->val, !(VAL & _Q_LOCKED_PENDING_MASK));  in queued_spin_lock_slowpath()
334 	 * n,0,0 -> 0,0,1 : lock, uncontended  in queued_spin_lock_slowpath()
335 	 * *,*,0 -> *,*,1 : lock, contended  in queued_spin_lock_slowpath()
337 	 * If the queue head is the only one in the queue (lock value == tail)  in queued_spin_lock_slowpath()
346 	 * n,0,1 -> 0,0,1  in queued_spin_lock_slowpath()
349 	 *       above wait condition, therefore any concurrent setting of  in queued_spin_lock_slowpath()
353 		if (atomic_try_cmpxchg_relaxed(&lock->val, &val, _Q_LOCKED_VAL))  in queued_spin_lock_slowpath()
359 	 * which will then detect the remaining tail and queue behind us  in queued_spin_lock_slowpath()
365 	 * contended path; wait for next if not observed yet, release.  in queued_spin_lock_slowpath()
368 		next = smp_cond_load_relaxed(&node->next, (VAL));  in queued_spin_lock_slowpath()
370 	arch_mcs_spin_unlock_contended(&next->locked);  in queued_spin_lock_slowpath()