From: "Alexei Starovoitov" <alexei.starovoitov@gmail.com>
To: "Shashank Mohan Jain" <jain.sm@gmail.com>,
"Kumar Kartikeya Dwivedi" <memxor@gmail.com>
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: Re: [PATCH bpf-next v2] rqspinlock: Keep claiming the lock while the queue head is still the tail
Date: Thu, 19 Nov 2026 01:22:33 +0000 [thread overview]
Message-ID: <DMYSLJIVTW06.330AM0ETRNHEG@gmail.com> (raw)
In-Reply-To: <20261118104758.98620-1-jain.sm@gmail.com>
On Wed, Nov 18, 2026 at 02:47 AM Shashank Mohan Jain <jain.sm@gmail.com> wrote:
> 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 waiter
Today 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?
> Suggested-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
> The diff is Kumar's from the v1 review.
Pls keep his authorship and SOB.
> + 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?
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);
/*
pw-bot: cr
prev parent reply other threads:[~2026-11-19 1:22 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-11-18 10:47 Shashank Mohan Jain
2026-11-18 11:27 ` bot+bpf-ci
2026-11-19 1:22 ` Alexei Starovoitov [this message]
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=DMYSLJIVTW06.330AM0ETRNHEG@gmail.com \
--to=alexei.starovoitov@gmail.com \
--cc=andrii@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=jain.sm@gmail.com \
--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®