* [PATCH bpf] rqspinlock: Reset tail if no waiter queues behind the queue head
@ 2026-11-17 22:50 Shashank Mohan Jain
2026-11-18 10:35 ` Kumar Kartikeya Dwivedi
0 siblings, 1 reply; 3+ messages in thread
From: Shashank Mohan Jain @ 2026-11-17 22:50 UTC (permalink / raw)
To: Kumar Kartikeya Dwivedi, Alexei Starovoitov
Cc: Daniel Borkmann, Andrii Nakryiko, Eduard Zingerman,
Martin KaFai Lau, Song Liu, Yonghong Song, Jiri Olsa,
Emil Tsalapatis, Ihor Solodrai, bpf, linux-kernel
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, so it shows up as an
RCU stall or a hard lockup. 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.
While waiting for the successor, reset the tail if it still points to
us, as the deadlock and timeout exits already do, and keep the lock. If
the tail has moved, a waiter has done xchg_tail() and will link into
our node, so keep waiting for it. try_cmpxchg_tail() reads the lock
word first, so the loop only adds a plain load while a successor
finishes linking.
Found with a TLA+ model of the slow path. 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.
Fixes: 0d80e7f951be ("rqspinlock: Choose trylock fallback for NMI waiters")
Fixes: 087849cca31d ("rqspinlock: Precede non-head waiter queueing with AA check")
Cc: stable@vger.kernel.org
Assisted-by: LLM
Signed-off-by: Shashank Mohan Jain <jain.sm@gmail.com>
---
Prepared with Claude Code (Anthropic), model Claude Opus 5.5
(claude-opus-5-5).
Based on mainline 63fdb511c27a. bpf and bpf-next have the same
rqspinlock.c. The TLA+ model and the userspace replay are not part of
the patch; I can post them if they help.
kernel/bpf/rqspinlock.c | 19 ++++++++++++++-----
1 file changed, 14 insertions(+), 5 deletions(-)
diff --git a/kernel/bpf/rqspinlock.c b/kernel/bpf/rqspinlock.c
index 111ec80..c50afaf 100644
--- a/kernel/bpf/rqspinlock.c
+++ b/kernel/bpf/rqspinlock.c
@@ -635,17 +635,26 @@ waitq_timeout:
}
/*
- * 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.
+ * Either somebody is queued behind us or _Q_PENDING_VAL got set.
+ * Unlike in qspinlock, the waiter that set _Q_PENDING_VAL may return
+ * without queueing behind us (AA check, trylock fallback).
*/
set_locked(lock);
/*
* contended path; wait for next if not observed yet, release.
+ *
+ * If we are still the tail, nobody has queued behind us and nobody
+ * will link into our node, so reset the tail instead of waiting for
+ * @next forever with the lock held.
+ *
+ * n,*,1 -> 0,*,1
*/
- if (!next)
- next = smp_cond_load_relaxed(&node->next, (VAL));
+ while (!next && !(next = READ_ONCE(node->next))) {
+ if (try_cmpxchg_tail(lock, tail, 0))
+ goto release;
+ cpu_relax();
+ }
arch_mcs_spin_unlock_contended(&next->locked);
--
2.54.0 (Apple Git-157)
^ permalink raw reply related [flat|nested] 3+ messages in thread
* Re: [PATCH bpf] rqspinlock: Reset tail if no waiter queues behind the queue head
2026-11-17 22:50 [PATCH bpf] rqspinlock: Reset tail if no waiter queues behind the queue head Shashank Mohan Jain
@ 2026-11-18 10:35 ` Kumar Kartikeya Dwivedi
2026-11-18 10:49 ` shashank Jain
0 siblings, 1 reply; 3+ messages in thread
From: Kumar Kartikeya Dwivedi @ 2026-11-18 10:35 UTC (permalink / raw)
To: Shashank Mohan Jain, Alexei Starovoitov
Cc: Daniel Borkmann, Andrii Nakryiko, Eduard Zingerman,
Martin KaFai Lau, Song Liu, Yonghong Song, Jiri Olsa,
Emil Tsalapatis, Ihor Solodrai, bpf, linux-kernel
On Tue Nov 17, 2026 at 11:50 PM CET, Shashank Mohan Jain wrote:
> 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, so it shows up as an
> RCU stall or a hard lockup. 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.
>
> While waiting for the successor, reset the tail if it still points to
> us, as the deadlock and timeout exits already do, and keep the lock. If
> the tail has moved, a waiter has done xchg_tail() and will link into
> our node, so keep waiting for it. try_cmpxchg_tail() reads the lock
> word first, so the loop only adds a plain load while a successor
> finishes linking.
>
> Found with a TLA+ model of the slow path. 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.
>
> Fixes: 0d80e7f951be ("rqspinlock: Choose trylock fallback for NMI waiters")
> Fixes: 087849cca31d ("rqspinlock: Precede non-head waiter queueing with AA check")
> Cc: stable@vger.kernel.org
> Assisted-by: LLM
> Signed-off-by: Shashank Mohan Jain <jain.sm@gmail.com>
> ---
I am aware of this one, but I don't think it's that serious (of course, needs to
be fixed). I was going to send it in a couple weeks with some other changes for
rqspinlock. For the next version, let's drop Cc to stable and target bpf-next.
How about the approach below instead that I have? You could check whether the
violation in your TLA+ model goes away. The benefit is that we don't penalize
the loop that waits for next, for this very rare condition that is not likely to
be hit.
diff --git a/kernel/bpf/rqspinlock.c b/kernel/bpf/rqspinlock.c
index 111ec80ea958..f6a938ee7ab4 100644
--- a/kernel/bpf/rqspinlock.c
+++ b/kernel/bpf/rqspinlock.c
@@ -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;
+
+ 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);
^ permalink raw reply related [flat|nested] 3+ messages in thread
* Re: [PATCH bpf] rqspinlock: Reset tail if no waiter queues behind the queue head
2026-11-18 10:35 ` Kumar Kartikeya Dwivedi
@ 2026-11-18 10:49 ` shashank Jain
0 siblings, 0 replies; 3+ messages in thread
From: shashank Jain @ 2026-11-18 10:49 UTC (permalink / raw)
To: Kumar Kartikeya Dwivedi
Cc: Alexei Starovoitov, Daniel Borkmann, Andrii Nakryiko,
Eduard Zingerman, Martin KaFai Lau, Song Liu, Yonghong Song,
Jiri Olsa, Emil Tsalapatis, Ihor Solodrai, bpf, linux-kernel
Thanks Kumar. Your version has no violation in the model (the NMI
trylock and AA cases that hang without a fix), and the userspace
replay of the interleaving completes with the lock word clean. v2 on
bpf-next with your diff and no Cc: stable:
https://lore.kernel.org/all/20261118104758.98620-1-jain.sm@gmail.com/
Shashank
On Wed, Nov 18, 2026 at 4:05 PM Kumar Kartikeya Dwivedi
<memxor@gmail.com> wrote:
>
> On Tue Nov 17, 2026 at 11:50 PM CET, Shashank Mohan Jain wrote:
> > 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, so it shows up as an
> > RCU stall or a hard lockup. 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.
> >
> > While waiting for the successor, reset the tail if it still points to
> > us, as the deadlock and timeout exits already do, and keep the lock. If
> > the tail has moved, a waiter has done xchg_tail() and will link into
> > our node, so keep waiting for it. try_cmpxchg_tail() reads the lock
> > word first, so the loop only adds a plain load while a successor
> > finishes linking.
> >
> > Found with a TLA+ model of the slow path. 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.
> >
> > Fixes: 0d80e7f951be ("rqspinlock: Choose trylock fallback for NMI waiters")
> > Fixes: 087849cca31d ("rqspinlock: Precede non-head waiter queueing with AA check")
> > Cc: stable@vger.kernel.org
> > Assisted-by: LLM
> > Signed-off-by: Shashank Mohan Jain <jain.sm@gmail.com>
> > ---
>
> I am aware of this one, but I don't think it's that serious (of course, needs to
> be fixed). I was going to send it in a couple weeks with some other changes for
> rqspinlock. For the next version, let's drop Cc to stable and target bpf-next.
>
> How about the approach below instead that I have? You could check whether the
> violation in your TLA+ model goes away. The benefit is that we don't penalize
> the loop that waits for next, for this very rare condition that is not likely to
> be hit.
>
> diff --git a/kernel/bpf/rqspinlock.c b/kernel/bpf/rqspinlock.c
> index 111ec80ea958..f6a938ee7ab4 100644
> --- a/kernel/bpf/rqspinlock.c
> +++ b/kernel/bpf/rqspinlock.c
> @@ -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;
> +
> + 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);
^ permalink raw reply [flat|nested] 3+ messages in thread
end of thread, other threads:[~2026-11-18 10:49 UTC | newest]
Thread overview: 3+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-11-17 22:50 [PATCH bpf] rqspinlock: Reset tail if no waiter queues behind the queue head Shashank Mohan Jain
2026-11-18 10:35 ` Kumar Kartikeya Dwivedi
2026-11-18 10:49 ` shashank Jain
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.