Limited queueing in NMI for rqspinlock
Subsystems (4)
Kumar Kartikeya Dwivedi
maintainerv2 cover Limited queueing in NMI for rqspinlock
Ritesh reported that he was frequently seeing timeouts in cases which should have been covered by the AA heuristics. This led to the discovery of multiple gaps in the current code that could lead to timeouts when AA heuristics could work to prevent them. More details and investigation is available in the original threads. [0][1]
This set restores the ability for NMI waiters to queue in the slow path, and reduces the cases where they would attempt to trylock. However, such queueing must not happen when interrupting waiters which the NMI itself depends upon for forward progress; in those cases the trylock fallback remains, but with a single attempt to avoid aimless attempts to acquire the lock.
It also closes a possible window in the lock fast path and the unlock path where NMIs landing between cmpxchg and entry creation, or entry deletion and unlock would miss the detection of an AA scenario and end up timing out.
This virtually eliminates all the cases where existing heuristics can prevent timeouts and quickly recover from a deadlock. More details are available in the commit logs for each patch.
[0]: https://lore.kernel.org/bpf/CAH6OuBTjG+N=+GGwcpOUbeDN563oz4iVcU3rbse68egp9wj9_A@mail.gmail.com
[1]: https://lore.kernel.org/bpf/[email protected]
Kumar Kartikeya Dwivedi (6):
rqspinlock: Enclose lock/unlock within lock entry acquisitions
rqspinlock: Perform AA checks immediately
rqspinlock: Use trylock fallback when per-CPU rqnode is busy
rqspinlock: Disable spinning for trylock fallback
rqspinlock: Precede non-head waiter queueing with AA check selftests/bpf: Add success stats to rqspinlock stress test
include/asm-generic/rqspinlock.h | 60 ++++++++-------- kernel/bpf/rqspinlock.c | 69 +++++++++---------- .../bpf/test_kmods/bpf_test_rqspinlock.c | 55 +++++++++++---- 3 files changed, 108 insertions(+), 76 deletions(-)
base-commit: 688b745401ab16e2e1a3b504863f0a45fd345638
Signature · 1 line
2.51.0
Kumar Kartikeya Dwivedi
maintainerPATCH v2 1/6 rqspinlock: Enclose lock/unlock within lock entry acquisitions
Ritesh reported that timeouts occurred frequently for rqspinlock despite reentrancy on the same lock on the same CPU in [0]. This patch closes one of the races leading to this behavior, and reduces the frequency of timeouts.
We currently have a tiny window between the fast-path cmpxchg and the grabbing of the lock entry where an NMI could land, attempt the same lock that was just acquired, and end up timing out. This is not ideal. Instead, move the lock entry acquisition from the fast path to before the cmpxchg, and remove the grabbing of the lock entry in the slow path, assuming it was already taken by the fast path. The TAS fallback is invoked directly without being preceded by the typical fast path, therefore we must continue to grab the deadlock detection entry in that case.
Case on lock leading to missed AA:
cmpxchg lock A
<NMI> ... rqspinlock acquisition of A ... timeout </NMI>
grab_held_lock_entry(A)
There is a similar case when unlocking the lock. If the NMI lands between the WRITE_ONCE and smp_store_release, it is possible that we end up in a situation where the NMI fails to diagnose the AA condition, leading to a timeout.
Case on unlock leading to missed AA:
WRITE_ONCE(rqh->locks[rqh->cnt - 1], NULL)
<NMI> ... rqspinlock acquisition of A ... timeout </NMI>
smp_store_release(A->locked, 0)
The patch changes the order on unlock to smp_store_release() succeeded by WRITE_ONCE() of NULL. This avoids the missed AA detection described above, but may lead to a false positive if the NMI lands between these two statements, which is acceptable (and preferred over a timeout).
The original intention of the reverse order on unlock was to prevent the following possible misdiagnosis of an ABBA scenario:
grab entry A
lock A
grab entry B
lock B
unlock B
smp_store_release(B->locked, 0)
grab entry B lock B grab entry A lock A ! <detect ABBA>
WRITE_ONCE(rqh->locks[rqh->cnt - 1], NULL)
If the store release were is after the WRITE_ONCE, the other CPU would not observe B in the table of the CPU unlocking the lock B. However, since the threads are obviously participating in an ABBA deadlock, it is no longer appealing to use the order above since it may lead to a 250 ms timeout due to missed AA detection.
[0]: https://lore.kernel.org/bpf/CAH6OuBTjG+N=+GGwcpOUbeDN563oz4iVcU3rbse68egp9wj9_A@mail.gmail.com
--- include/asm-generic/rqspinlock.h | 60 +++++++++++++++++--------------- kernel/bpf/rqspinlock.c | 15 ++++---- 2 files changed, 38 insertions(+), 37 deletions(-)
include/asm-generic/rqspinlock.h +32 -28
@@ -129,8 +129,8 @@ static __always_inline void release_held_lock_entry(void)* <error> for lock B * release_held_lock_entry * -* try_cmpxchg_acquire for lock A * grab_held_lock_entry +* try_cmpxchg_acquire for lock A * * Lack of any ordering means reordering may occur such that dec, inc * are done before entry is overwritten. This permits a remote lock
@@ -139,13 +139,8 @@ static __always_inline void release_held_lock_entry(void)* CPU holds a lock it is attempting to acquire, leading to false ABBA * diagnosis). * -* In case of unlock, we will always do a release on the lock word after -* releasing the entry, ensuring that other CPUs cannot hold the lock -* (and make conclusions about deadlocks) until the entry has been -* cleared on the local CPU, preventing any anomalies. Reordering is -* still possible there, but a remote CPU cannot observe a lock in our -* table which it is already holding, since visibility entails our -* release store for the said lock has not retired. +* The case of unlock is treated differently due to NMI reentrancy, see +* comments in res_spin_unlock. * * In theory we don't have a problem if the dec and WRITE_ONCE above get * reordered with each other, we either notice an empty NULL entry on
@@ -175,10 +170,22 @@ static __always_inline int res_spin_lock(rqspinlock_t *lock) {int val =0 ; -if (likely (atomic_try_cmpxchg_acquire (&lock->val, &val, _Q_LOCKED_VAL))) { -grab_held_lock_entry (lock); +/* +* Grab the deadlock detection entry before doing the cmpxchg, so that +* reentrancy due to NMIs between the succeeding cmpxchg and creation of +* held lock entry can correctly detect an acquisition attempt in the +* interrupted context. +* +* cmpxchg lock A +* <NMI> +* res_spin_lock(A) --> missed AA, leads to timeout +* </NMI> +* grab_held_lock_entry(A) +*/ +grab_held_lock_entry (lock); + +if (likely (atomic_try_cmpxchg_acquire (&lock->val, &val, _Q_LOCKED_VAL)))return 0 ; - }return resilient_queued_spin_lock_slowpath (lock, val); }
@@ -192,28 +199,25 @@ static __always_inline void res_spin_unlock(rqspinlock_t *lock) {struct rqspinlock_held *rqh =this_cpu_ptr (&rqspinlock_held_locks); -if (unlikely (rqh->cnt >RES_NR_HELD )) - goto unlock; -WRITE_ONCE (rqh->locks[rqh->cnt -1 ],NULL ); -unlock:/* -* Release barrier, ensures correct ordering. See release_held_lock_entry -* for details. Perform release store instead of queued_spin_unlock, -* since we use this function for test-and-set fallback as well. When we -* have CONFIG_QUEUED_SPINLOCKS=n, we clear the full 4-byte lockword. +* Release barrier, ensures correct ordering. Perform release store +* instead of queued_spin_unlock, since we use this function for the TAS +* fallback as well. When we have CONFIG_QUEUED_SPINLOCKS=n, we clear +* the full 4-byte lockword. * -* Like release_held_lock_entry, we can do the release before the dec. -* We simply care about not seeing the 'lock' in our table from a remote -* CPU once the lock has been released, which doesn't rely on the dec. +* Perform the smp_store_release before clearing the lock entry so that +* NMIs landing in the unlock path can correctly detect AA issues. The +* opposite order shown below may lead to missed AA checks: * -* Unlike smp_wmb(), release is not a two way fence, hence it is -* possible for a inc to move up and reorder with our clearing of the -* entry. This isn't a problem however, as for a misdiagnosis of ABBA, -* the remote CPU needs to hold this lock, which won't be released until -* the store below is done, which would ensure the entry is overwritten -* to NULL, etc. +* WRITE_ONCE(rqh->locks[rqh->cnt - 1], NULL) +* <NMI> +* res_spin_lock(A) --> missed AA, leads to timeout +* </NMI> +* smp_store_release(A->locked, 0) */ smp_store_release (&lock->locked,0 ); +if (likely (rqh->cnt <=RES_NR_HELD )) +WRITE_ONCE (rqh->locks[rqh->cnt -1 ],NULL );this_cpu_dec (rqspinlock_held_locks.cnt); }
kernel/bpf/rqspinlock.c +6 -9
@@ -275,6 +275,10 @@ int __lockfunc resilient_tas_spin_lock(rqspinlock_t *lock)int val, ret =0 ;RES_INIT_TIMEOUT (ts); +/* +* The fast path is not invoked for the TAS fallback, so we must grab +* the deadlock detection entry here. +*/ grab_held_lock_entry (lock);/*
@@ -397,10 +401,7 @@ int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val) goto queue; } -/* -* Grab an entry in the held locks array, to enable deadlock detection. -*/ -grab_held_lock_entry (lock); +/* Deadlock detection entry already held after failing fast path. */ /* * We're pending, wait for the owner to go away.
@@ -448,11 +449,7 @@ int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val)*/ queue:lockevent_inc (lock_slowpath); -/* -* Grab deadlock detection entry for the queue path. -*/ -grab_held_lock_entry (lock); - +/* Deadlock detection entry already held after failing fast path. */ node =this_cpu_ptr (&rqnodes[0 ].mcs); idx = node->count++; tail =encode_tail (smp_processor_id (), idx);
Signature · 1 line
2.51.0
Kumar Kartikeya Dwivedi
maintainerPATCH v2 2/6 rqspinlock: Perform AA checks immediately
In reply to Kumar Kartikeya DwivediCurrently, while we enter the check_timeout call immediately due to the way the ts.spin is initialized, we still invoke the AA and ABBA checks in the second invocation, and only initialize the timestamp in the first one. Since each iteration is at least done with a 1ms delay, this can add delays in detection of AA deadlocks, up to a ms.
Rework check_timeout() to avoid this. First, call check_deadlock_AA() while initializing the timestamps for the wait period. This also means that we only do it once per waiting period, instead of every invocation. Finally, drop check_deadlock() and call check_deadlock_ABBA() directly.
To save on unnecessary ktime_get_mono_fast_ns() in case of AA deadlock, sample the time only if it returns 0.
--- kernel/bpf/rqspinlock.c | 25 +++++++------------------ 1 file changed, 7 insertions(+), 18 deletions(-)
kernel/bpf/rqspinlock.c +7 -18
@@ -196,32 +196,21 @@ static noinline int check_deadlock_ABBA(rqspinlock_t *lock, u32 mask)return 0 ; } -static noinline int check_deadlock(rqspinlock_t *lock, u32 mask) -{ -int ret; - - ret =check_deadlock_AA (lock); -if (ret) -return ret; - ret =check_deadlock_ABBA (lock, mask); -if (ret) -return ret; - -return 0 ; -} - static noinline int check_timeout(rqspinlock_t *lock, u32 mask,struct rqspinlock_timeout *ts) { -u64 time =ktime_get_mono_fast_ns ();u64 prev = ts->cur; +u64 time;if (!ts->timeout_end) { - ts->cur = time; - ts->timeout_end = time + ts->duration; +if (check_deadlock_AA (lock)) +return -EDEADLK ; + ts->cur =ktime_get_mono_fast_ns (); + ts->timeout_end = ts->cur + ts->duration;return 0 ; } + time =ktime_get_mono_fast_ns ();if (time > ts->timeout_end)return -ETIMEDOUT ;
@@ -231,7 +220,7 @@ static noinline int check_timeout(rqspinlock_t *lock, u32 mask,*/ if (prev +NSEC_PER_MSEC < time) { ts->cur = time; -return check_deadlock (lock, mask); +return check_deadlock_ABBA (lock, mask); }return 0 ;
Signature · 1 line
2.51.0
Kumar Kartikeya Dwivedi
maintainerPATCH v2 3/6 rqspinlock: Use trylock fallback when per-CPU rqnode is busy
In reply to Kumar Kartikeya DwivediIn addition to deferring to the trylock fallback in NMIs, only do so when an rqspinlock waiter is queued on the current CPU. This is detected by noticing a non-zero node index. This allows NMI waiters to join the waiter queue if it isn't interrupting an existing rqspinlock waiter, and increase the chances of fairly obtaining the lock, performing deadlock detection as the head, and not being starved while attempting the trylock.
The trylock path in particular is unlikely to succeed under contention, as it relies on the lock word becoming 0, which indicates no contention. This means that the most likely result for NMIs attempting a trylock is a timeout under contention if they don't hit an AA or ABBA case.
The core problem being addressed through the fixed commit was removing the dependency edge between an NMI queue waiter and the queue waiter it is interrupting. Whenever a circular dependency forms, and with no way to break it (as non-head waiters don't poll for deadlocks or timeouts), we would enter into a deadlock. A trylock either breaks such an edge by probing for deadlocks, and finally terminating the waiting loop using a timeout.
By excluding queueing on CPUs where the node index is non-zero for NMIs, this sort of dependency is broken. The CPU enters the trylock path for those cases, and falls back to deadlock checks and timeouts. However, in other case where it doesn't interrupt the CPU in the slow path while its queued on the lock, it can join the queue as a normal waiter, and avoid trylock associated starvation and subsequent timeouts.
There are a few remaining cases here that matter: the NMI can still preempt the owner in its critical section, and if it queues as a non-head waiter, it can end up impeding the progress of the owner. While this won't deadlock, since the head waiter will eventually signal the NMI waiter to either stop (due to a timeout), it can still lead to long timeouts. These gaps will be addressed in subsequent commits.
Note that while the node count detection approach is less conservative than simply deferring NMIs to trylock, it is going to return errors where attempts to lock B in NMI happen while waiters for lock A are in a lower context on the same CPU. However, this only occurs when the lower context is queued in the slow path, and the NMI attempt can proceed without failure in all other cases. To continue to prevent AA deadlocks (or ABBA in a similar NMI interrupting lower context pattern), we'd need a more fleshed out algorithm to unlink NMI waiters after they queue and detect such cases. However, all that complexity isn't appealing yet to reduce the failure rate in the small window inside the slow path.
It is important to note that reentrancy in the slow path can also happen through trace_contention_{begin,end}, but in those cases, unlike an NMI, the forward progress of the head waiter (or the predecessor in general) is not being blocked.
--- kernel/bpf/rqspinlock.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
kernel/bpf/rqspinlock.c +1 -1
@@ -454,7 +454,7 @@ int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val)* any MCS node. This is not the most elegant solution, but is * simple enough. */ -if (unlikely (idx >= _Q_MAX_NODES ||in_nmi ())) { +if (unlikely (idx >= _Q_MAX_NODES || (in_nmi () && idx >0 ))) {lockevent_inc (lock_no_node);RES_RESET_TIMEOUT (ts,RES_DEF_TIMEOUT );while (!queued_spin_trylock (lock)) {
Signature · 1 line
2.51.0
[email protected]
AI reviewRe: [PATCH bpf-next v2 3/6] rqspinlock: Use trylock fallback when per-CPU rqnode is busy
Can an NMI interrupt between the load and store operations of this non-atomic increment? If so, both the interrupted context and the NMI could read count=0, increment it, and both end up with idx=0.
kernel/bpf/rqspinlock.c int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val) · line 444
Quoted 10 lines
kernel/bpf/rqspinlock.c +0
-0@@ -440,10 +440,25 @@ int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val) queue:lockevent_inc (lock_slowpath);/* Deadlock detection entry already held after failing fast path. */ node =this_cpu_ptr (&rqnodes[0 ].mcs); idx = node->count++;
Can an NMI interrupt between the load and store operations of this non-atomic increment? If so, both the interrupted context and the NMI could read count=0, increment it, and both end up with idx=0.
Looking at the structure definition in include/asm-generic/mcs_spinlock.h, the count field is a plain int, not atomic_t. The sequence for count++ typically compiles to separate load/add/store instructions.
If an NMI fires after the load but before the store completes:
Process context: loads count=0
<< NMI interrupts >>
NMI context: loads count=0, stores count=1, gets idx=0
NMI: Checks (in_nmi() && 0 > 0) = false, proceeds to queue path
NMI: Uses rqnodes[0]
<< Process resumes >>
Process: stores count=1, gets idx=0
Process: Also uses rqnodes[0]
Both contexts would then call grab_mcs_node(node, 0) and corrupt the same queue node's locked and next fields.
The old code had this race too, but it was harmless because in_nmi() was always true, forcing the fallback path. Now that NMIs with idx=0 can enter the normal queue path, does this race become exploitable?
Quoted 7 lines
kernel/bpf/rqspinlock.c +0
-0tail =encode_tail (smp_processor_id (), idx);trace_contention_begin (lock,LCB_F_SPIN );/* * 4 nodes are allocated based on the assumption that there will * not be nested NMIs taking spinlocks. That may not be true in
kernel/bpf/rqspinlock.c int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val)
Quoted 10 lines
kernel/bpf/rqspinlock.c +1
-1* some architectures even though the chance of needing more than * 4 nodes will still be extremely unlikely. When that happens, * we fall back to spinning on the lock directly without using * any MCS node. This is not the most elegant solution, but is * simple enough. */ -if (unlikely (idx >= _Q_MAX_NODES ||in_nmi ())) { +if (unlikely (idx >= _Q_MAX_NODES || (in_nmi () && idx >0 ))) {lockevent_inc (lock_no_node);RES_RESET_TIMEOUT (ts,RES_DEF_TIMEOUT );
[ ... ]
---
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/19775799393
Kumar Kartikeya Dwivedi
maintainerRe: [PATCH bpf-next v2 3/6] rqspinlock: Use trylock fallback when per-CPU rqnode is busy
Quoted 31 lines · On Sat, 29 Nov 2025 at 02:12, <[email protected]> wrote:
kernel/bpf/rqspinlock.c int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val) · line 444
Quoted 11 lines
kernel/bpf/rqspinlock.c +0
-0@@ -440,10 +440,25 @@ int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val) queue:lockevent_inc (lock_slowpath);/* Deadlock detection entry already held after failing fast path. */ node =this_cpu_ptr (&rqnodes[0 ].mcs); idx = node->count++;Can an NMI interrupt between the load and store operations of this non-atomic increment? If so, both the interrupted context and the NMI could read count=0, increment it, and both end up with idx=0.
Looking at the structure definition in
include/asm-generic/mcs_spinlock.h, the count field is a plain int, notatomic_t. The sequence for count++ typically compiles to separate load/add/store instructions.If an NMI fires after the load but before the store completes:
Process context: loads count=0
<< NMI interrupts >>
NMI context: loads count=0, stores count=1, gets idx=0
NMI: Checks (in_nmi()&& 0 > 0) = false, proceeds to queue path
NMI: Uses rqnodes[0]
<< Process resumes >>
Process: stores count=1, gets idx=0
Process: Also uses rqnodes[0]
Quoted 6 lines
Both contexts would then call
grab_mcs_node(node, 0)and corrupt the same queue node's locked and next fields.The old code had this race too, but it was harmless because
in_nmi()was always true, forcing the fallback path. Now that NMIs with idx=0 can enter the normal queue path, does this race become exploitable?
Great observation, but since the NMI (or any other interrupt) concludes its usage of the node before it returns to the lower context, the values it overwrote do not matter, and the lower context will continue using things at idx=0. The key thing is for the store of count=1 to be done before the lower context starts writing anything to the node, which is why there is a compiler barrier() to prevent the compiler from reordering any statements. If it initializes the node before storing in count=1, then the values overwritten by the NMI/interrupt could cause node corruption.
Quoted 27 lines
Quoted 8 lines
kernel/bpf/rqspinlock.c +0
-0tail =encode_tail (smp_processor_id (), idx);trace_contention_begin (lock,LCB_F_SPIN );/* * 4 nodes are allocated based on the assumption that there will * not be nested NMIs taking spinlocks. That may not be true in kernel/bpf/rqspinlock.c int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val)
Quoted 10 lines
kernel/bpf/rqspinlock.c +1
-1* some architectures even though the chance of needing more than * 4 nodes will still be extremely unlikely. When that happens, * we fall back to spinning on the lock directly without using * any MCS node. This is not the most elegant solution, but is * simple enough. */ -if (unlikely (idx >= _Q_MAX_NODES ||in_nmi ())) { +if (unlikely (idx >= _Q_MAX_NODES || (in_nmi () && idx >0 ))) {lockevent_inc (lock_no_node);RES_RESET_TIMEOUT (ts,RES_DEF_TIMEOUT );[ ... ]
---
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.mdCI run summary: https://github.com/kernel-patches/bpf/actions/runs/19775799393
Kumar Kartikeya Dwivedi
maintainerPATCH v2 4/6 rqspinlock: Disable spinning for trylock fallback
In reply to Kumar Kartikeya DwivediThe original trylock fallback was inherited from qspinlock, and then reused for the reentrant NMIs while the slow path is active. However, under contention, it is very unlikely for the trylock to succeed in taking the lock. In addition, a trylock also has no fairness guarantees, and thus is prone to starvation issues under extreme scenarios.
The original qspinlock had no choice in terms of returning an error the caller; if the node count was breached, it had to fall back to trylock to attempt to take the lock. In case of rqspinlock, we do have the option of returning to the user. Thus, simply attempt the trylock once, and instead of spinning, return an error in case the lock cannot be taken.
This ends up significantly reducing the time spent in the trylock fallback, since we no longer wait for the timeout duration trying to aimlessly acquire the lock when there's a high-probability that under contention, it won't be available to us anyway.
--- kernel/bpf/rqspinlock.c | 18 ++++++++---------- 1 file changed, 8 insertions(+), 10 deletions(-)
kernel/bpf/rqspinlock.c +8 -10
@@ -450,19 +450,17 @@ int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val)* not be nested NMIs taking spinlocks. That may not be true in * some architectures even though the chance of needing more than * 4 nodes will still be extremely unlikely. When that happens, -* we fall back to spinning on the lock directly without using -* any MCS node. This is not the most elegant solution, but is -* simple enough. +* we fall back to attempting a trylock operation without using +* any MCS node. Unlike qspinlock which cannot fail, we have the +* option of failing the slow path, and under contention, such a +* trylock spinning will likely be treated unfairly due to lack of +* queueing, hence do not spin. */ if (unlikely (idx >= _Q_MAX_NODES || (in_nmi () && idx >0 ))) {lockevent_inc (lock_no_node); -RES_RESET_TIMEOUT (ts,RES_DEF_TIMEOUT ); -while (!queued_spin_trylock (lock)) { -if (RES_CHECK_TIMEOUT (ts, ret, ~0u )) { -lockevent_inc (rqspinlock_lock_timeout); - goto err_release_node; - } -cpu_relax (); +if (!queued_spin_trylock (lock)) { + ret = -EDEADLK ; + goto err_release_node; } goto release; }
Signature · 1 line
2.51.0
Kumar Kartikeya Dwivedi
maintainerPATCH v2 5/6 rqspinlock: Precede non-head waiter queueing with AA check
In reply to Kumar Kartikeya DwivediWhile previous commits sufficiently address the deadlocks, there are still scenarios where queueing of waiters in NMIs can exacerbate the possibility of timeouts.
Consider the case below:
CPU 0
<NMI> res_spin_lock(A) -> becomes non-head waiter </NMI>
lock owner in CS or pending waiter spinning
CPU 1res_spin_lock(A) -> head waiter spinning on owner/pending bits
In such a scenario, the non-head waiter in NMI on CPU 0 will not poll for deadlocks or timeout since it will simply queue behind previous waiter (head on CPU 1), and also not enter the trylock fallback since no rqspinlock queue waiter is active on CPU 0. In such a scenario, the transaction initiated by the head waiter on CPU 1 will timeout, signalling the NMI and ending the cyclic dependency, but it will cost 250 ms of time.
Instead, the NMI on CPU 0 could simply check for the presence of an AA deadlock and only proceed with queueing on success. Add such a check right before any form of queueing is initiated.
The reason the AA deadlock check is not used in conjunction with in_nmi() is that a similar case could occur due to a reentrant path in the owner's critical section, and unconditionally checking for AA before entering the queueing path avoids expensive timeouts. Non-NMI reentrancy only happens at controlled points in the slow path (with specific tracepoints which do not impede the forward progress of a waiter loop), or in the owner CS, while NMIs can land anywhere.
While this check is only needed for non-head waiter queueing, checking whether we are head or not is racy without xchg_tail, and after that point, we are already queued, hence for simplicity we must invoke the check unconditionally.
Note that a more contrived case could still be constructed by using two locks, and interrupting the progress of the respective owners by non-head waiters of the other lock, in an ABBA fashion, which would still not be covered by the current set of checks and conditions. It would still lead to a timeout though, and not a deadlock. An ABBA check cannot happen optimistically before the queueing, since it can be racy, and needs to be happen continuously during the waiting period, which would then require an unlinking step for queued NMI/reentrant waiters. This is beyond the scope of this patch.
--- kernel/bpf/rqspinlock.c | 13 +++++++++++++ 1 file changed, 13 insertions(+)
kernel/bpf/rqspinlock.c +13 -0
@@ -437,6 +437,19 @@ int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val)* queuing. */ queue: +/* +* Do not queue if we're a waiter and someone is attempting this lock on +* the same CPU. In case of NMIs, this prevents long timeouts where we +* interrupt the pending waiter, and the owner, that will eventually +* signal the head of our queue, both of which are logically but not +* physically part of the queue, hence outside the scope of the idx > 0 +* check above for the trylock fallback. +*/ +if (check_deadlock_AA (lock)) { + ret = -EDEADLK ; + goto err_release_entry; + } +lockevent_inc (lock_slowpath);/* Deadlock detection entry already held after failing fast path. */ node =this_cpu_ptr (&rqnodes[0 ].mcs);
Signature · 1 line
2.51.0
Kumar Kartikeya Dwivedi
maintainerPATCH v2 6/6 selftests/bpf: Add success stats to rqspinlock stress test
In reply to Kumar Kartikeya DwivediAdd stats to observe the success and failure rate of lock acquisition attempts in various contexts.
--- .../bpf/test_kmods/bpf_test_rqspinlock.c | 55 +++++++++++++++---- 1 file changed, 43 insertions(+), 12 deletions(-)
tools/testing/selftests/bpf/test_kmods/bpf_test_rqspinlock.c +43 -12
@@ -33,9 +33,16 @@ static const unsigned int rqsl_hist_ms[] = { };#define RQSL_NR_HIST_BUCKETS ARRAY_SIZE(rqsl_hist_ms) +enum rqsl_context { +RQSL_CTX_NORMAL =0 , +RQSL_CTX_NMI , +RQSL_CTX_MAX , +}; +struct rqsl_cpu_hist { -atomic64_t normal[RQSL_NR_HIST_BUCKETS ]; -atomic64_t nmi[RQSL_NR_HIST_BUCKETS ]; +atomic64_t hist[RQSL_CTX_MAX ][RQSL_NR_HIST_BUCKETS ]; +atomic64_t success[RQSL_CTX_MAX ]; +atomic64_t failure[RQSL_CTX_MAX ]; }; static DEFINE_PER_CPU(struct rqsl_cpu_hist, rqsl_cpu_hists);
@@ -117,14 +124,18 @@ static u32 rqsl_hist_bucket_idx(u32 delta_ms)return RQSL_NR_HIST_BUCKETS -1 ; } -static void rqsl_record_lock_time (u64 delta_ns,bool is_nmi) +static void rqsl_record_lock_result (u64 delta_ns,enum rqsl_context ctx,int ret) {struct rqsl_cpu_hist *hist =this_cpu_ptr (&rqsl_cpu_hists);u32 delta_ms =DIV_ROUND_UP_ULL (delta_ns,NSEC_PER_MSEC );u32 bucket =rqsl_hist_bucket_idx (delta_ms); -atomic64_t *buckets = is_nmi ? hist->nmi : hist->normal; +atomic64_t *buckets = hist->hist[ctx];atomic64_inc (&buckets[bucket]); +if (!ret) +atomic64_inc (&hist->success[ctx]); +else +atomic64_inc (&hist->failure[ctx]); }static int rqspinlock_worker_fn (void *arg)
@@ -147,7 +158,8 @@ static int rqspinlock_worker_fn(void *arg) } start_ns =ktime_get_mono_fast_ns (); ret =raw_res_spin_lock_irqsave (worker_lock, flags); -rqsl_record_lock_time (ktime_get_mono_fast_ns () - start_ns, false); +rqsl_record_lock_result (ktime_get_mono_fast_ns () - start_ns, +RQSL_CTX_NORMAL , ret);mdelay (normal_delay);if (!ret)raw_res_spin_unlock_irqrestore (worker_lock, flags);
@@ -190,7 +202,8 @@ static void nmi_cb(struct perf_event *event, struct perf_sample_data *data, locks =rqsl_get_lock_pair (cpu); start_ns =ktime_get_mono_fast_ns (); ret =raw_res_spin_lock_irqsave (locks.nmi_lock, flags); -rqsl_record_lock_time (ktime_get_mono_fast_ns () - start_ns, true); +rqsl_record_lock_result (ktime_get_mono_fast_ns () - start_ns, +RQSL_CTX_NMI , ret);mdelay (nmi_delay);
@@ -300,12 +313,14 @@ static void rqsl_print_histograms(void)u64 norm_counts[RQSL_NR_HIST_BUCKETS ];u64 nmi_counts[RQSL_NR_HIST_BUCKETS ];u64 total_counts[RQSL_NR_HIST_BUCKETS ]; +u64 norm_success, nmi_success, success_total; +u64 norm_failure, nmi_failure, failure_total;u64 norm_total =0 , nmi_total =0 , total =0 ;bool has_slow = false;for (i =0 ; i <RQSL_NR_HIST_BUCKETS ; i++) { - norm_counts[i] =atomic64_read (&hist->normal[i]); - nmi_counts[i] =atomic64_read (&hist->nmi[i]); + norm_counts[i] =atomic64_read (&hist->hist[RQSL_CTX_NORMAL ][i]); + nmi_counts[i] =atomic64_read (&hist->hist[RQSL_CTX_NMI ][i]); total_counts[i] = norm_counts[i] + nmi_counts[i]; norm_total += norm_counts[i]; nmi_total += nmi_counts[i];
@@ -315,17 +330,33 @@ static void rqsl_print_histograms(void) has_slow = true; } + norm_success =atomic64_read (&hist->success[RQSL_CTX_NORMAL ]); + nmi_success =atomic64_read (&hist->success[RQSL_CTX_NMI ]); + norm_failure =atomic64_read (&hist->failure[RQSL_CTX_NORMAL ]); + nmi_failure =atomic64_read (&hist->failure[RQSL_CTX_NMI ]); + success_total = norm_success + nmi_success; + failure_total = norm_failure + nmi_failure; +if (!total)continue ;if (!has_slow) { -pr_err (" cpu%d: total %llu (normal %llu, nmi %llu), all within 0-%ums\n" , - cpu, total, norm_total, nmi_total,RQSL_SLOW_THRESHOLD_MS ); +pr_err (" cpu%d: total %llu (normal %llu, nmi %llu) | " +"success %llu (normal %llu, nmi %llu) | " +"failure %llu (normal %llu, nmi %llu), all within 0-%ums\n" , + cpu, total, norm_total, nmi_total, + success_total, norm_success, nmi_success, + failure_total, norm_failure, nmi_failure, +RQSL_SLOW_THRESHOLD_MS );continue ; } -pr_err (" cpu%d: total %llu (normal %llu, nmi %llu)\n" , - cpu, total, norm_total, nmi_total); +pr_err (" cpu%d: total %llu (normal %llu, nmi %llu) | " +"success %llu (normal %llu, nmi %llu) | " +"failure %llu (normal %llu, nmi %llu)\n" , + cpu, total, norm_total, nmi_total, + success_total, norm_success, nmi_success, + failure_total, norm_failure, nmi_failure);for (i =0 ; i <RQSL_NR_HIST_BUCKETS ; i++) {unsigned int start_ms;
Signature · 1 line
2.51.0
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:
Quoted 6 lines · On Fri, 28 Nov 2025 23:27:56 +0000 you wrote:
Ritesh reported that he was frequently seeing timeouts in cases which should have been covered by the AA heuristics. This led to the discovery of multiple gaps in the current code that could lead to timeouts when AA heuristics could work to prevent them. More details and investigation is available in the original threads. [0][1]
Quoted 8 lines
This set restores the ability for NMI waiters to queue in the slow path, and reduces the cases where they would attempt to trylock. However, such queueing must not happen when interrupting waiters which the NMI itself depends upon for forward progress; in those cases the trylock fallback remains, but with a single attempt to avoid aimless attempts to acquire the lock.
[...]
Here is the summary with links:
- [bpf-next,v2,1/6] rqspinlock: Enclose lock/unlock within lock entry acquisitions
https://git.kernel.org/bpf/bpf-next/c/beb7021a6003 - [bpf-next,v2,2/6] rqspinlock: Perform AA checks immediately https://git.kernel.org/bpf/bpf-next/c/5860f5ce479f - [bpf-next,v2,3/6] rqspinlock: Use trylock fallback when per-CPU rqnode is busy https://git.kernel.org/bpf/bpf-next/c/81d5a6a43859 - [bpf-next,v2,4/6] rqspinlock: Disable spinning for trylock fallback https://git.kernel.org/bpf/bpf-next/c/30dc2f7025fe - [bpf-next,v2,5/6] rqspinlock: Precede non-head waiter queueing with AA check https://git.kernel.org/bpf/bpf-next/c/087849cca31d - [bpf-next,v2,6/6] selftests/bpf: Add success stats to rqspinlock stress test https://git.kernel.org/bpf/bpf-next/c/3448375e71a4
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html