3  * Resilient Queued Spin Lock
29 #include <trace/events/lock.h>
46  * MCS lock. A copy of the original MCS lock paper ("Algorithms for Scalable
52  * This queued spinlock implementation is based on the MCS lock, however to
56  * In particular; where the traditional MCS lock consists of a tail pointer
65  * number. With one byte for the lock value and 3 bytes for the tail, only a
66  * 32-bit word is now needed. Even though we only need 1 bit for the lock,
70  * We also change the first spinner to spin on the lock bit instead of its
71  * node; whereby avoiding the need to carry a node from lock to unlock, and
72  * preserving existing lock API. This also makes the unlock code simpler and
92 static bool is_lock_released(rqspinlock_t *lock, u32 mask)  in is_lock_released()  argument
94 	if (!(atomic_read_acquire(&lock->val) & (mask)))  in is_lock_released()
99 static noinline int check_deadlock_AA(rqspinlock_t *lock)  in check_deadlock_AA()  argument
105 	 * Return an error if we hold the lock we are attempting to acquire.  in check_deadlock_AA()
109 		if (rqh->locks[i] == lock)  in check_deadlock_AA()
120 static noinline int check_deadlock_ABBA(rqspinlock_t *lock, u32 mask)  in check_deadlock_ABBA()  argument
128 	 * Find the CPU holding the lock that we want to acquire. If there is a  in check_deadlock_ABBA()
131 	 * O(NR_CPUS) if we could determine the owning CPU from a lock value, but  in check_deadlock_ABBA()
132 	 * that requires increasing the size of the lock word.  in check_deadlock_ABBA()
140 		 * Let's ensure to break out of this loop if the lock is available for  in check_deadlock_ABBA()
143 		if (is_lock_released(lock, mask))  in check_deadlock_ABBA()
148 		 * least one held lock and one acquisition attempt (reflected as top  in check_deadlock_ABBA()
151 		 * If cnt is more than RES_NR_HELD, it means the current lock being  in check_deadlock_ABBA()
159 		 * Obtain the entry at the top, this corresponds to the lock the  in check_deadlock_ABBA()
171 		 * Find if the lock we're attempting to acquire is held by this CPU.  in check_deadlock_ABBA()
172 		 * Don't consider the topmost entry, as that must be the latest lock  in check_deadlock_ABBA()
174 		 * attempt to acquire a lock we hold, so for this search only 'cnt - 1'  in check_deadlock_ABBA()
178 			if (READ_ONCE(rqh_cpu->locks[i]) != lock)  in check_deadlock_ABBA()
181 			 * We found our lock as held on the remote CPU.  Is the  in check_deadlock_ABBA()
182 			 * acquisition attempt on the remote CPU for a lock held  in check_deadlock_ABBA()
199 static noinline int check_timeout(rqspinlock_t *lock, u32 mask,  in check_timeout()  argument
206 		if (check_deadlock_AA(lock))  in check_timeout()
223 		return check_deadlock_ABBA(lock, mask);  in check_timeout()
237 			(ret) = check_timeout((lock), (mask), &(ts)); \
242 	({ (ret) = check_timeout((lock), (mask), &(ts)); })
258  * Provide a test-and-set fallback for cases when queued spin lock support is
261 int __lockfunc resilient_tas_spin_lock(rqspinlock_t *lock)  in resilient_tas_spin_lock()  argument
281 	val = atomic_read(&lock->val);  in resilient_tas_spin_lock()
283 	if (val || !atomic_try_cmpxchg(&lock->val, &val, 1)) {  in resilient_tas_spin_lock()
315  * @lock: Pointer to queued spinlock structure
319  * * 0		- Lock was acquired successfully.
320  * * -EDEADLK	- Lock acquisition failed because of AA/ABBA deadlock.
321  * * -ETIMEDOUT - Lock acquisition failed because of timeout.
323  * (queue tail, pending bit, lock value)
339 int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val)  in resilient_queued_spin_lock_slowpath()  argument
349 		return resilient_virt_spin_lock(lock);  in resilient_queued_spin_lock_slowpath()
361 		val = atomic_cond_read_relaxed(&lock->val,  in resilient_queued_spin_lock_slowpath()
376 	val = queued_fetch_set_pending_acquire(lock);  in resilient_queued_spin_lock_slowpath()
389 			clear_pending(lock);  in resilient_queued_spin_lock_slowpath()
402 	 * store-release that clears the locked bit and create lock  in resilient_queued_spin_lock_slowpath()
409 		res_smp_cond_load_acquire(&lock->locked, !VAL || RES_CHECK_TIMEOUT(ts, ret, _Q_LOCKED_MASK));  in resilient_queued_spin_lock_slowpath()
416 		 * we own it. Once a stuck owner has been recovered, the lock  in resilient_queued_spin_lock_slowpath()
422 		clear_pending(lock);  in resilient_queued_spin_lock_slowpath()
432 	clear_pending_set_locked(lock);  in resilient_queued_spin_lock_slowpath()
442 	 * Do not queue if we're a waiter and someone is attempting this lock on  in resilient_queued_spin_lock_slowpath()
449 	if (check_deadlock_AA(lock)) {  in resilient_queued_spin_lock_slowpath()
460 	trace_contention_begin(lock, LCB_F_SPIN);  in resilient_queued_spin_lock_slowpath()
475 		if (!queued_spin_trylock(lock)) {  in resilient_queued_spin_lock_slowpath()
504 	if (queued_spin_trylock(lock))  in resilient_queued_spin_lock_slowpath()
521 	old = xchg_tail(lock, tail);  in resilient_queued_spin_lock_slowpath()
543 		 * While waiting for the MCS lock, the next pointer may have  in resilient_queued_spin_lock_slowpath()
544 		 * been set by another lock waiter. We optimistically load  in resilient_queued_spin_lock_slowpath()
560 	 * store-release that clears the locked bit and create lock  in resilient_queued_spin_lock_slowpath()
566 	 * have both the owner of the lock and the pending bit waiter ahead of  in resilient_queued_spin_lock_slowpath()
570 	val = res_atomic_cond_read_acquire(&lock->val, !(VAL & _Q_LOCKED_PENDING_MASK) ||  in resilient_queued_spin_lock_slowpath()
575 		if (!try_cmpxchg_tail(lock, tail, 0)) {  in resilient_queued_spin_lock_slowpath()
596 		 * will queue behind us. This will leave the lock owner in  in resilient_queued_spin_lock_slowpath()
608 		if (!try_cmpxchg_tail(lock, tail, 0)) {  in resilient_queued_spin_lock_slowpath()
617 	 * claim the lock:  in resilient_queued_spin_lock_slowpath()
619 	 * n,0,0 -> 0,0,1 : lock, uncontended  in resilient_queued_spin_lock_slowpath()
620 	 * *,*,0 -> *,*,1 : lock, contended  in resilient_queued_spin_lock_slowpath()
622 	 * If the queue head is the only one in the queue (lock value == tail)  in resilient_queued_spin_lock_slowpath()
623 	 * and nobody is pending, clear the tail code and grab the lock.  in resilient_queued_spin_lock_slowpath()
624 	 * Otherwise, we only need to grab the lock.  in resilient_queued_spin_lock_slowpath()
633 		if (atomic_try_cmpxchg_relaxed(&lock->val, &val, _Q_LOCKED_VAL))  in resilient_queued_spin_lock_slowpath()
642 	set_locked(lock);  in resilient_queued_spin_lock_slowpath()
653 	trace_contention_end(lock, 0);  in resilient_queued_spin_lock_slowpath()
661 	trace_contention_end(lock, ret);  in resilient_queued_spin_lock_slowpath()
673 static void bpf_prog_report_rqspinlock_violation(const char *str, void *lock, bool irqsave)  in bpf_prog_report_rqspinlock_violation()  argument
684 		bpf_stream_printk(ss, "Attempted lock   = 0x%px\n", lock);  in bpf_prog_report_rqspinlock_violation()
687 			bpf_stream_printk(ss, "Held lock[%2d] = 0x%px\n", i, rqh->locks[i]);  in bpf_prog_report_rqspinlock_violation()
694 __bpf_kfunc int bpf_res_spin_lock(struct bpf_res_spin_lock *lock)  in bpf_res_spin_lock()  argument
701 	ret = res_spin_lock((rqspinlock_t *)lock);  in bpf_res_spin_lock()
703 		bpf_prog_report_rqspinlock_violation(REPORT_STR(ret), lock, false);  in bpf_res_spin_lock()
710 __bpf_kfunc void bpf_res_spin_unlock(struct bpf_res_spin_lock *lock)  in bpf_res_spin_unlock()  argument
712 	res_spin_unlock((rqspinlock_t *)lock);  in bpf_res_spin_unlock()
716 __bpf_kfunc int bpf_res_spin_lock_irqsave(struct bpf_res_spin_lock *lock, unsigned long *flags__irq…  in bpf_res_spin_lock_irqsave()  argument
724 	ret = res_spin_lock((rqspinlock_t *)lock);  in bpf_res_spin_lock_irqsave()
726 		bpf_prog_report_rqspinlock_violation(REPORT_STR(ret), lock, true);  in bpf_res_spin_lock_irqsave()
735 __bpf_kfunc void bpf_res_spin_unlock_irqrestore(struct bpf_res_spin_lock *lock, unsigned long *flag…  in bpf_res_spin_unlock_irqrestore()  argument
740 	res_spin_unlock((rqspinlock_t *)lock);  in bpf_res_spin_unlock_irqrestore()