From: Shashank Mohan Jain <jain.sm@gmail.com>
To: Kumar Kartikeya Dwivedi <memxor@gmail.com>,
Alexei Starovoitov <ast@kernel.org>
Cc: Daniel Borkmann <daniel@iogearbox.net>,
Andrii Nakryiko <andrii@kernel.org>,
Eduard Zingerman <eddyz87@gmail.com>,
Martin KaFai Lau <martin.lau@linux.dev>,
Song Liu <song@kernel.org>,
Yonghong Song <yonghong.song@linux.dev>,
Jiri Olsa <jolsa@kernel.org>,
Emil Tsalapatis <emil@etsalapatis.com>,
Ihor Solodrai <ihor.solodrai@linux.dev>,
bpf@vger.kernel.org, linux-kernel@vger.kernel.org
Subject: [PATCH bpf-next v3] rqspinlock: Keep claiming the lock while the queue head is still the tail
Date: Thu, 19 Nov 2026 08:03:07 +0530 [thread overview]
Message-ID: <20261119023307.65178-1-jain.sm@gmail.com> (raw)
From: Kumar Kartikeya Dwivedi <memxor@gmail.com>
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 retry the claim as long as the tail is ours,
and keep PENDING, which belongs to the waiter. That waiter either
clears the bit, or on x86, where queued_fetch_set_pending_acquire() is
a lock btsl followed by a separate load, it no longer sees our tail and
becomes the pending waiter behind the new owner. Update the comments
that described the old claim.
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),
also with the btsl and the load of queued_fetch_set_pending_acquire()
modelled as two steps on x86; the model reaches the case above where
the waiter no longer sees the tail. 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")
Reported-by: Shashank Mohan Jain <jain.sm@gmail.com>
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Assisted-by: LLM
Signed-off-by: Shashank Mohan Jain <jain.sm@gmail.com>
---
Changes in v3:
- Kumar's patch with his authorship and Signed-off-by (Alexei).
Kumar, please tell me if you would rather send it yourself.
- Use Alexei's simpler loop (PENDING is 0 on the first pass, so no
separate 'new' and no second tail check) and his comment updates,
which also cover the two stale comments (Alexei, BPF CI).
- Checked the x86 case Alexei raised: the model now has the lock btsl
and the load of queued_fetch_set_pending_acquire() as two steps. It
reaches the window where the head clears the tail between them and the
waiter becomes the pending waiter, with no violation; without the fix
the head still hangs.
Changes in v2:
- Kumar's approach instead of resetting the tail in the wait for next.
- Target bpf-next, drop Cc: stable (Kumar).
v2: https://lore.kernel.org/all/20261118104758.98620-1-jain.sm@gmail.com/
v1: https://lore.kernel.org/all/20261117225023.36660-1-jain.sm@gmail.com/
Prepared with Claude Code (Anthropic), model Claude Opus 5.5
(claude-opus-5-5).
kernel/bpf/rqspinlock.c | 35 ++++++++++++++---------------------
1 file changed, 14 insertions(+), 21 deletions(-)
diff --git a/kernel/bpf/rqspinlock.c b/kernel/bpf/rqspinlock.c
index 111ec80..14d3798 100644
--- a/kernel/bpf/rqspinlock.c
+++ b/kernel/bpf/rqspinlock.c
@@ -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);
/*
--
2.54.0 (Apple Git-157)
base-commit: 32b66b94c86f009b49668de7340f2ed65aad2dc5
reply other threads:[~2026-11-19 2:33 UTC|newest]
Thread overview: [no followups] expand[flat|nested] mbox.gz Atom feed
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20261119023307.65178-1-jain.sm@gmail.com \
--to=jain.sm@gmail.com \
--cc=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=eddyz87@gmail.com \
--cc=emil@etsalapatis.com \
--cc=ihor.solodrai@linux.dev \
--cc=jolsa@kernel.org \
--cc=linux-kernel@vger.kernel.org \
--cc=martin.lau@linux.dev \
--cc=memxor@gmail.com \
--cc=song@kernel.org \
--cc=yonghong.song@linux.dev \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox
all inboxes | Powered by JetHome®