mirror of https://lore.kernel.org/lkml/
 help / color / mirror / Atom feed
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 v2] rqspinlock: Keep claiming the lock while the queue head is still the tail
Date: Wed, 18 Nov 2026 16:17:58 +0530	[thread overview]
Message-ID: <20261118104758.98620-1-jain.sm@gmail.com> (raw)

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.

Fixes: 0d80e7f951be ("rqspinlock: Choose trylock fallback for NMI waiters")
Fixes: 087849cca31d ("rqspinlock: Precede non-head waiter queueing with AA check")
Suggested-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Assisted-by: LLM
Signed-off-by: Shashank Mohan Jain <jain.sm@gmail.com>
---
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/20261117225023.36660-1-jain.sm@gmail.com/

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(-)

diff --git a/kernel/bpf/rqspinlock.c b/kernel/bpf/rqspinlock.c
index 111ec80..f6a938e 100644
--- a/kernel/bpf/rqspinlock.c
+++ b/kernel/bpf/rqspinlock.c
@@ -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
-- 
2.54.0 (Apple Git-157)


             reply	other threads:[~2026-11-18 10:48 UTC|newest]

Thread overview: 2+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2026-11-18 10:47 Shashank Mohan Jain [this message]
2026-11-18 11:27 ` bot+bpf-ci

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=20261118104758.98620-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®