Lines Matching +full:load +full:- +full:acquire
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
9 * (C) Copyright 2024-2025 Meta Platforms, Inc. and affiliates.
44 * The basic principle of a queue-based spinlock can best be understood
45 * by studying a classic queue-based spinlock implementation called the
47 * Synchronization on Shared-Memory Multiprocessors by Mellor-Crummey and
58 * unlock the next pending (next->locked), we compress both these: {tail,
59 * next->locked} into a single u32 value.
63 * are at most 4 nesting levels, it can be encoded by a 2-bit number. Now
64 * we can encode the tail by combining the 2-bit nesting level with the cpu
66 * 32-bit word is now needed. Even though we only need 1 bit for the lock,
76 * atomic operations on smaller 8-bit and 16-bit data types.
94 if (!(atomic_read_acquire(&lock->val) & (mask)))
102 int cnt = min(RES_NR_HELD, rqh->cnt);
105 * Return an error if we hold the lock we are attempting to acquire.
108 for (int i = 0; i < cnt - 1; i++) {
109 if (rqh->locks[i] == lock)
110 return -EDEADLK;
123 int rqh_cnt = min(RES_NR_HELD, rqh->cnt);
128 * Find the CPU holding the lock that we want to acquire. If there is a
136 int real_cnt = READ_ONCE(rqh_cpu->cnt);
141 * us to potentially acquire.
160 * remote CPU is attempting to acquire in a deadlock situation,
163 remote_lock = READ_ONCE(rqh_cpu->locks[cnt - 1]);
171 * Find if the lock we're attempting to acquire is held by this CPU.
174 * attempt to acquire a lock we hold, so for this search only 'cnt - 1'
177 for (int i = 0; i < cnt - 1; i++) {
178 if (READ_ONCE(rqh_cpu->locks[i]) != lock)
186 for (int i = 0; i < rqh_cnt - 1; i++) {
187 if (rqh->locks[i] == remote_lock)
188 return -EDEADLK;
202 u64 prev = ts->cur;
205 if (!ts->timeout_end) {
207 return -EDEADLK;
208 ts->cur = ktime_get_mono_fast_ns();
209 ts->timeout_end = ts->cur + ts->duration;
214 if (time > ts->timeout_end)
215 return -ETIMEDOUT;
222 ts->cur = time;
258 * Provide a test-and-set fallback for cases when queued spin lock support is
280 val = atomic_read(&lock->val);
282 if (val || !atomic_try_cmpxchg(&lock->val, &val, 1)) {
299 * Per-CPU queue node structures; we can never have more than 4 nested
302 * Exactly fits one 64-byte cacheline on a 64-bit architecture.
310 #define res_atomic_cond_read_acquire(v, c) res_smp_cond_load_acquire(&(v)->counter, (c))
313 * resilient_queued_spin_lock_slowpath - acquire the queued spinlock
315 * @val: Current value of the queued spinlock 32-bit word
318 * * 0 - Lock was acquired successfully.
319 * * -EDEADLK - Lock acquisition failed because of AA/ABBA deadlock.
320 * * -ETIMEDOUT - Lock acquisition failed because of timeout.
326 * uncontended (0,0,0) -:--> (0,0,1) ------------------------------:--> (*,*,0)
327 * : | ^--------.------. / :
329 * pending : (0,1,1) +--> (0,1,0) \ | :
330 * : | ^--' | | :
332 * uncontended : (n,x,y) +--> (n,0,0) --' | :
333 * queue : | ^--' | :
335 * contended : (*,x,y) +--> (*,0,0) ---> (*,0,1) -' :
336 * queue : ^--' :
353 * Wait for in-progress pending->locked hand-overs with a bounded
356 * 0,1,0 -> 0,0,1
360 val = atomic_cond_read_relaxed(&lock->val,
361 (VAL != _Q_PENDING_VAL) || !cnt--);
373 * 0,0,* -> 0,1,* -> 0,0,1 pending, trylock
381 * n,0,0 -> 0,0,0 transition fail and it will now be waiting
398 * 0,1,1 -> *,1,0
400 * this wait loop must be a load-acquire such that we match the
401 * store-release that clears the locked bit and create lock
408 res_smp_cond_load_acquire(&lock->locked, !VAL || RES_CHECK_TIMEOUT(ts, ret, _Q_LOCKED_MASK));
419 * *,1,* -> *,0,*
429 * 0,1,0 -> 0,0,1
449 ret = -EDEADLK;
456 idx = node->count++;
475 ret = -EDEADLK;
484 * Keep counts of non-zero index values:
486 lockevent_cond_inc(lock_use_node2 + idx - 1, idx);
489 * Ensure that we increment the head node->count before initialising
495 node->locked = 0;
496 node->next = NULL;
499 * We touched a (possibly) cold cacheline in the per-cpu queue node;
509 * @node into the waitqueue via WRITE_ONCE(prev->next, node) below.
518 * p,*,* -> n,*,*
533 WRITE_ONCE(prev->next, node);
535 val = arch_mcs_spin_lock_contended(&node->locked);
537 ret = -ETIMEDOUT;
543 * been set by another lock waiter. We optimistically load
547 next = READ_ONCE(node->next);
556 * *,x,y -> *,0,0
558 * this wait loop must use a load-acquire such that we match the
559 * store-release that clears the locked bit and create lock
569 val = res_atomic_cond_read_acquire(&lock->val, !(VAL & _Q_LOCKED_PENDING_MASK) ||
573 if (ret == -EDEADLK) {
575 next = smp_cond_load_relaxed(&node->next, (VAL));
576 arch_mcs_spin_unlock_contended(&next->locked);
588 * n,*,* -> 0,*,*
599 * we eschew per-waiter timeouts with one applied at the head of
607 next = smp_cond_load_relaxed(&node->next, VAL);
608 WRITE_ONCE(next->locked, RES_TIMEOUT_VAL);
617 * n,0,0 -> 0,0,1 : lock, uncontended
618 * *,*,0 -> *,*,1 : lock, contended
631 if (atomic_try_cmpxchg_relaxed(&lock->val, &val, _Q_LOCKED_VAL))
646 next = smp_cond_load_relaxed(&node->next, (VAL));
648 arch_mcs_spin_unlock_contended(&next->locked);
683 bpf_stream_printk(ss, "Total held locks = %d\n", rqh->cnt);
684 for (int i = 0; i < min(RES_NR_HELD, rqh->cnt); i++)
685 bpf_stream_printk(ss, "Held lock[%2d] = 0x%px\n", i, rqh->locks[i]);
690 #define REPORT_STR(ret) ({ (ret) == -ETIMEDOUT ? "Timeout detected" : "AA or ABBA deadlock detected"; })