rqspinlock: Keep claiming the lock while the queue head is still the tail
PATCH v2 1/1 rqspinlock: Keep claiming the lock while the queue head is still the tail
When the head of the wait queue claims the lock and its cmpxchg from n,0,0 to 0,0,1 fails, it sets the locked bit and waits for node->next, with no timeout. The comment, taken from qspinlock, says the cmpxchg can only fail if somebody queued behind us, or if a waiter set PENDING, which will then see our tail and queue behind us.
In rqspinlock that waiter does not always queue. After clear_pending() it goes to queue:, and two paths return -EDEADLK there before xchg_tail():
- the trylock fallback for an NMI waiter whose per-CPU node is busy (in_nmi() && idx > 0), or when idx >= _Q_MAX_NODES;
- check_deadlock_AA(), when this CPU already holds an entry for the lock.
For example, with the queue head H alone in the queue:
CPU 0 (H, head) CPU 1 (NMI, idx 1 on another lock)
reads lock->val == H,0,0
queued_fetch_set_pending_acquire()
sees tail H
try_cmpxchg(H,0,0 -> 0,0,1) fails
set_locked() -> H,1,1
clear_pending() -> H,0,1
in_nmi() && idx > 0, trylock fails
return -EDEADLK waits for node->next ...
H now owns the lock and spins until another context queues on the same lock. For a lock that is rarely taken, such as a hash map bucket lock, that can be a long time, with interrupts disabled. The same happens on v6.17 and v6.18 for any NMI waiter, as the trylock fallback was used for all of them. The AA path needs the interrupted context to have taken its entry for the lock and not to try the lock again, so it is much narrower.
Only a different tail shows that a waiter did xchg_tail() and will link into our node. So while the tail is still ours, retry the claim and keep the PENDING bit of a waiter that may still be backing out, and set the locked bit and wait for node->next only once the tail has moved. The loop that waits for node->next is unchanged.
Found with a TLA+ model of the slow path. With this change the model has no violation in the configurations where the head hangs without it (an NMI waiter using the trylock fallback, and the AA bail-out). A userspace port of the slow path, driven through the interleaving above, hangs without this change and completes with the lock word clean with it. I have not reproduced the hang on a running kernel.
---
Changes in v2:
- Use Kumar's approach: retry the claim while the tail is still ours, keeping PENDING, instead of resetting the tail in the loop that waits for node->next, so that loop is not slowed down for this rare case. The diff is Kumar's from the v1 review.
- Target bpf-next and drop Cc: stable (Kumar).
- Checked the new approach in the TLA+ model (no violation in the NMI trylock and AA configurations that hang without a fix) and in the userspace replay of the interleaving (completes, lock word clean).
v1: https://lore.kernel.org/all/[email protected]/
Prepared with Claude Code (Anthropic), model Claude Opus 5.5 (claude-opus-5-5).
Based on bpf-next 32b66b94c86f.
kernel/bpf/rqspinlock.c | 23 +++++++++++++---------- 1 file changed, 13 insertions(+), 10 deletions(-)
kernel/bpf/rqspinlock.c +13 -10
@@ -624,20 +624,23 @@ waitq_timeout:* Otherwise, we only need to grab the lock. */ -/* -* Note: at this point: (val & _Q_PENDING_MASK) == 0, because of the -* above wait condition, therefore any concurrent setting of -* PENDING will make the uncontended transition fail. -*/ if ((val & _Q_TAIL_MASK) == tail) { -if (atomic_try_cmpxchg_relaxed (&lock->val, &val, _Q_LOCKED_VAL)) - goto release;/* No contention */ +u32 new = _Q_LOCKED_VAL; + +for (;;) { +if (atomic_try_cmpxchg_relaxed (&lock->val, &val, new)) + goto release;/* No queued successor */ +if ((val & _Q_TAIL_MASK) != tail) +break ; +/* A pending claimant can abandon before publishing a tail. */ + new = _Q_LOCKED_VAL | (val & _Q_PENDING_MASK); + } }/* -* Either somebody is queued behind us or _Q_PENDING_VAL got set -* which will then detect the remaining tail and queue behind us -* ensuring we'll see a @next. +* A different tail proves that a successor will publish node->next. +* Preserve pending while installing ownership; a racing claimant may +* still be undoing its speculative reservation against this queue. */ set_locked (lock);
base-commit: 32b66b94c86f009b49668de7340f2ed65aad2dc5
Signature · 1 line
2.54.0 (Apple Git-157)
[email protected]
AI reviewTL;DR: Nits only: two comments in rqspinlock.c (queue-head claim and pending undo path) still describe the old behaviour and could be updated to match the new retry loop.
Quoted 1 line
rqspinlock: Keep claiming the lock while the queue head is still the tail
TL;DR: Nits only: two comments in rqspinlock.c (queue-head claim and pending undo path) still describe the old behaviour and could be updated to match the new retry loop.
Quoted 3 lines
kernel/bpf/rqspinlock.c +0
-0
[ ... ]
Quoted 13 lines
kernel/bpf/rqspinlock.c +1
-7@@ -624,20 +624,23 @@ int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val)* Otherwise, we only need to grab the lock. */ -/* -* Note: at this point: (val & _Q_PENDING_MASK) == 0, because of the -* above wait condition, therefore any concurrent setting of -* PENDING will make the uncontended transition fail. -*/ if ((val & _Q_TAIL_MASK) == tail) { -if (atomic_try_cmpxchg_relaxed (&lock->val, &val, _Q_LOCKED_VAL)) - goto release;/* No contention */ +u32 new = _Q_LOCKED_VAL;
kernel/bpf/rqspinlock.c int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val) · line 638
Quoted 10 lines
kernel/bpf/rqspinlock.c +9
-0+ +for (;;) { +if (atomic_try_cmpxchg_relaxed (&lock->val, &val, new)) + goto release;/* No queued successor */ +if ((val & _Q_TAIL_MASK) != tail) +break ; +/* A pending claimant can abandon before publishing a tail. */ + new = _Q_LOCKED_VAL | (val & _Q_PENDING_MASK); + } }
This isn't a bug, but the comment block just above this hunk still describes the old behaviour:
* If the queue head is the only one in the queue (lock value == tail)
* and nobody is pending, clear the tail code and grab the lock.
The new loop also clears the tail when pending is set, keeping the pending bit (the n,1,0 -> 0,1,1 transition). Could that comment be updated?
Similarly, the comment on the pending claimant's undo path still says:
* Undo and queue; our setting of PENDING might have made the
* n,0,0 -> 0,0,0 transition fail and it will now be waiting
* on @next to become !NULL.
With this change the head no longer waits on @next in that case while the tail is still its own. Could that comment be adjusted in this patch as well?
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
CI run summary: https://github.com/kernel-patches/bpf/actions/runs/44290867653
Quoted 3 lines · Shashank Mohan Jain
Only a different tail shows that a waiter did
xchg_tail()and will link into our node. So while the tail is still ours, retry the claim and keep the PENDING bit of a waiter that may still be backing out,
On x86 that waiter doesn't always back out. queued_fetch_set_pending_acquire() is lock btsl and then a separate load:
val |= atomic_read(&lock->val) & ~_Q_PENDING_MASK;
With the patch the head can remove the tail between the two:
CPU 0 (H, head) CPU 1
lock btsl -> H,1,0
try_cmpxchg(H,0,0 -> 0,0,1) fails
try_cmpxchg(H,1,0 -> 0,1,1)
atomic_read() == 0,1,1
val = 0,0,1, no contention
waits for H as the pending waiterToday that load sees tail H and CPU 1 calls clear_pending(). The new case works only because the head keeps PENDING. Does your TAL model have btsl and the load as two steps?
Quoted 3 lines
Suggested-by Kumar Kartikeya Dwivedi <[email protected]>The diff is Kumar's from the v1 review.
Pls keep his authorship and SOB.
Review
Quoted 7 lines
(quoted diff) +7
-0+ u32 new = _Q_LOCKED_VAL; + + for (;;) { + if (atomic_try_cmpxchg_relaxed(&lock->val, &val, new)) + goto release; /* No queued successor */ + if ((val & _Q_TAIL_MASK) != tail) + break;
PENDING is zero in val on the first pass. The wait loop above checks it. No need for 'new' and the second tail check.
Two comments in this function still describe the old code:
* and nobody is pending, clear the tail code and grab the lock.
* n,0,0 -> 0,0,0 transition fail and it will now be waiting
* on @next to become !NULL.
The head clears the tail with PENDING set now.
It waits for next only after the tail has moved.
Would the following be simpler?
kernel/bpf/rqspinlock.c +14 -21
@@ -378,9 +378,7 @@ int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val)/* * If we observe contention, there is a concurrent locker. * -* Undo and queue; our setting of PENDING might have made the -* n,0,0 -> 0,0,0 transition fail and it will now be waiting -* on @next to become !NULL. +* Undo and queue. */ if (unlikely (val & ~_Q_LOCKED_MASK)) {
@@ -616,29 +614,24 @@ waitq_timeout:/* * claim the lock: * -* n,0,0 -> 0,0,1 : lock, uncontended +* n,*,0 -> 0,*,1 : lock, uncontended * *,*,0 -> *,*,1 : lock, contended * -* If the queue head is the only one in the queue (lock value == tail) -* and nobody is pending, clear the tail code and grab the lock. -* Otherwise, we only need to grab the lock. -*/ - -/* -* Note: at this point: (val & _Q_PENDING_MASK) == 0, because of the -* above wait condition, therefore any concurrent setting of -* PENDING will make the uncontended transition fail. +* If the queue head is the only one in the queue, clear the tail code +* and grab the lock. Otherwise, we only need to grab the lock. +* +* A waiter that sets PENDING now may leave with -EDEADLK and never +* queue behind us, so retry as long as the tail is ours. PENDING +* belongs to that waiter, keep it. It either clears the bit or, on +* x86, no longer sees our tail and becomes the pending waiter. */ -if ((val & _Q_TAIL_MASK) == tail) { -if (atomic_try_cmpxchg_relaxed (&lock->val, &val, _Q_LOCKED_VAL)) - goto release;/* No contention */ +while ((val & _Q_TAIL_MASK) == tail) { +if (atomic_try_cmpxchg_relaxed (&lock->val, &val, + (val & _Q_PENDING_MASK) | _Q_LOCKED_VAL)) + goto release; } -/* -* Either somebody is queued behind us or _Q_PENDING_VAL got set -* which will then detect the remaining tail and queue behind us -* ensuring we'll see a @next. -*/ +/* Somebody is queued behind us, ensuring we'll see a @next. */ set_locked (lock);/*
pw-bot: cr