Skip to contentSkip to conversation

bpf: Add deadlock check at the entry of slowpath for quick exit

RFC In review Siddharth Chintamaneni 2 participants 3 messages Sep 30, 2025 – Oct 1, 2025 BPF

lore
Share & tools
lore
#0 lore raw

RFC 1/1 bpf: Add deadlock check at the entry of slowpath for quick exit

A single deadlock check at the start of slowpath function enables quick deadlock detection. This additional check don't create any overhead because same check happens in both pending and queuing cases during contention. Also cleaned up the unused function args in check_deadlock* functions.

I've checked the resilient spinlocks cover letter for benchmarks to run but I couldn't figure out the link to run those benchmarks. Can you point me to those benchmarks so that I can run that with this change?

Fixes a8fcf2a ("locking: Copy out qspinlock.c to kernel/bpf/rqspinlock.c")
---
 kernel/bpf/rqspinlock.c | 45 ++++++++++++++++++++++-------------------
 1 file changed, 24 insertions(+), 21 deletions(-)
kernel/bpf/rqspinlock.c +24 -21
index a00561b1d3e5..6ec4e97a73a2 100644
@@ -89,15 +89,14 @@ struct rqspinlock_timeout {
 DEFINE_PER_CPU_ALIGNED(struct rqspinlock_held, rqspinlock_held_locks);
 EXPORT_SYMBOL_GPL(rqspinlock_held_locks);
 
-static bool is_lock_released(rqspinlock_t *lock, u32 mask, struct rqspinlock_timeout *ts)
+static bool is_lock_released(rqspinlock_t *lock, u32 mask)
 {
 	if (!(atomic_read_acquire(&lock->val) & (mask)))
 		return true;
 	return false;
 }
 
-static noinline int check_deadlock_AA(rqspinlock_t *lock, u32 mask,
-				      struct rqspinlock_timeout *ts)
+static noinline int check_deadlock_AA(rqspinlock_t *lock)
 {
 	struct rqspinlock_held *rqh = this_cpu_ptr(&rqspinlock_held_locks);
 	int cnt = min(RES_NR_HELD, rqh->cnt);
@@ -118,8 +117,7 @@ static noinline int check_deadlock_AA(rqspinlock_t *lock, u32 mask,
  * more locks, which reduce to ABBA). This is not exhaustive, and we rely on
  * timeouts as the final line of defense.
  */
-static noinline int check_deadlock_ABBA(rqspinlock_t *lock, u32 mask,
-					struct rqspinlock_timeout *ts)
+static noinline int check_deadlock_ABBA(rqspinlock_t *lock, u32 mask)
 {
 	struct rqspinlock_held *rqh = this_cpu_ptr(&rqspinlock_held_locks);
 	int rqh_cnt = min(RES_NR_HELD, rqh->cnt);
@@ -142,7 +140,7 @@ static noinline int check_deadlock_ABBA(rqspinlock_t *lock, u32 mask,
 		 * Let's ensure to break out of this loop if the lock is available for
 		 * us to potentially acquire.
 		 */
-		if (is_lock_released(lock, mask, ts))
+		if (is_lock_released(lock, mask))
 			return 0;
 
 		/*
@@ -198,15 +196,14 @@ static noinline int check_deadlock_ABBA(rqspinlock_t *lock, u32 mask,
 	return 0;
 }
 
-static noinline int check_deadlock(rqspinlock_t *lock, u32 mask,
-				   struct rqspinlock_timeout *ts)
+static noinline int check_deadlock(rqspinlock_t *lock, u32 mask)
 {
 	int ret;
 
-	ret = check_deadlock_AA(lock, mask, ts);
+	ret = check_deadlock_AA(lock);
 	if (ret)
 		return ret;
-	ret = check_deadlock_ABBA(lock, mask, ts);
+	ret = check_deadlock_ABBA(lock, mask);
 	if (ret)
 		return ret;
 
@@ -234,7 +231,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, ts);
+		return check_deadlock(lock, mask);
 	}
 
 	return 0;
@@ -350,7 +347,7 @@ int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val)
 	struct mcs_spinlock *prev, *next, *node;
 	struct rqspinlock_timeout ts;
 	int idx, ret = 0;
-	u32 old, tail;
+	u32 old, tail, mask = _Q_LOCKED_MASK;
 
 	BUILD_BUG_ON(CONFIG_NR_CPUS >= (1U << _Q_TAIL_CPU_BITS));
 
@@ -359,6 +356,21 @@ int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val)
 
 	RES_INIT_TIMEOUT(ts);
 
+	/*
+	 * Grab an entry in the held locks array, to enable deadlock detection
+	 */
+	grab_held_lock_entry(lock);
+
+	if (val & _Q_PENDING_VAL)
+		mask = _Q_LOCKED_PENDING_MASK;
+
+	/*
+	 * Do a deadlock check on the entry of the slowpath
+	 */
+	ret = check_deadlock(lock, mask);
+	if (ret)
+		goto err_release_entry;
+
 	/*
 	 * Wait for in-progress pending->locked hand-overs with a bounded
 	 * number of spins so that we guarantee forward progress.
@@ -400,11 +412,6 @@ 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);
-
 	/*
 	 * We're pending, wait for the owner to go away.
 	 *
@@ -451,10 +458,6 @@ 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);
 
 	node = this_cpu_ptr(&rqnodes[0].mcs);
 	idx = node->count++;
Signature · 1 line
2.43.0
#1 lore raw
Quoted 6 lines · Siddharth Chintamaneni

A single deadlock check at the start of slowpath function enables quick deadlock detection. This additional check don't create any overhead because same check happens in both pending and queuing cases during contention. Also cleaned up the unused function args in check_deadlock* functions.

What's the motivation? Are you trying to address the bug that the recent in_nmi() fix tried to work around?
Note that I'm working on a proper fix; just doing deadlock detection on entry into non-head waiter slow path is not sufficient, as the table updates for held locks is racy and can populate a deadlock-signalling combination right after our check, so it needs to happen repeatedly.

Quoted 5 lines

I've checked the resilient spinlocks cover letter for benchmarks to run but I couldn't figure out the link to run those benchmarks. Can you point me to those benchmarks so that I can run that with this change?

All benchmark scripts are here: https://github.com/kkdwivedi/rqspinlock
But they can also be run manually. I ran will-it-scale and locktorture back then.
The description of which locks contend for various cases (openN_threads, lockN_threads) is in the CNA paper. [0]

[0]: https://arxiv.org/pdf/1810.05600

Quoted 68 lines
Fixes a8fcf2a ("locking: Copy out qspinlock.c to kernel/bpf/rqspinlock.c")
---
 kernel/bpf/rqspinlock.c | 45 ++++++++++++++++++++++-------------------
 1 file changed, 24 insertions(+), 21 deletions(-)
kernel/bpf/rqspinlock.c +7 -10
index a00561b1d3e5..6ec4e97a73a2 100644
@@ -89,15 +89,14 @@ struct rqspinlock_timeout {
 DEFINE_PER_CPU_ALIGNED(struct rqspinlock_held, rqspinlock_held_locks);
 EXPORT_SYMBOL_GPL(rqspinlock_held_locks);
 
-static bool is_lock_released(rqspinlock_t *lock, u32 mask, struct rqspinlock_timeout *ts)
+static bool is_lock_released(rqspinlock_t *lock, u32 mask)
 {
        if (!(atomic_read_acquire(&lock->val) & (mask)))
                return true;
        return false;
 }
 
-static noinline int check_deadlock_AA(rqspinlock_t *lock, u32 mask,
-                                     struct rqspinlock_timeout *ts)
+static noinline int check_deadlock_AA(rqspinlock_t *lock)
 {
        struct rqspinlock_held *rqh = this_cpu_ptr(&rqspinlock_held_locks);
        int cnt = min(RES_NR_HELD, rqh->cnt);
@@ -118,8 +117,7 @@ static noinline int check_deadlock_AA(rqspinlock_t *lock, u32 mask,
  * more locks, which reduce to ABBA). This is not exhaustive, and we rely on
  * timeouts as the final line of defense.
  */
-static noinline int check_deadlock_ABBA(rqspinlock_t *lock, u32 mask,
-                                       struct rqspinlock_timeout *ts)
+static noinline int check_deadlock_ABBA(rqspinlock_t *lock, u32 mask)
 {
        struct rqspinlock_held *rqh = this_cpu_ptr(&rqspinlock_held_locks);
        int rqh_cnt = min(RES_NR_HELD, rqh->cnt);
@@ -142,7 +140,7 @@ static noinline int check_deadlock_ABBA(rqspinlock_t *lock, u32 mask,
                 * Let's ensure to break out of this loop if the lock is available for
                 * us to potentially acquire.
                 */
-               if (is_lock_released(lock, mask, ts))
+               if (is_lock_released(lock, mask))
                        return 0;
 
                /*
@@ -198,15 +196,14 @@ static noinline int check_deadlock_ABBA(rqspinlock_t *lock, u32 mask,
        return 0;
 }
 
-static noinline int check_deadlock(rqspinlock_t *lock, u32 mask,
-                                  struct rqspinlock_timeout *ts)
+static noinline int check_deadlock(rqspinlock_t *lock, u32 mask)
 {
        int ret;
 
-       ret = check_deadlock_AA(lock, mask, ts);
+       ret = check_deadlock_AA(lock);
        if (ret)
                return ret;
-       ret = check_deadlock_ABBA(lock, mask, ts);
+       ret = check_deadlock_ABBA(lock, mask);
        if (ret)
                return ret;
 

kernel/bpf/rqspinlock.c static noinline int check_timeout(rqspinlock_t *lock, u32 mask, · line 234

Quoted 5 lines
kernel/bpf/rqspinlock.c +1 -1
@@ -234,7 +231,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, ts);
+               return check_deadlock(lock, mask);

This removal of unused arguments still looks useful, please send it as a separate clean up.

Quoted 20 lines
kernel/bpf/rqspinlock.c +5 -1
        }
 
        return 0;
@@ -350,7 +347,7 @@ int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val)
        struct mcs_spinlock *prev, *next, *node;
        struct rqspinlock_timeout ts;
        int idx, ret = 0;
-       u32 old, tail;
+       u32 old, tail, mask = _Q_LOCKED_MASK;
 
        BUILD_BUG_ON(CONFIG_NR_CPUS >= (1U << _Q_TAIL_CPU_BITS));
 
@@ -359,6 +356,21 @@ int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val)
 
        RES_INIT_TIMEOUT(ts);
 
+       /*
+        * Grab an entry in the held locks array, to enable deadlock detection
+        */
+       grab_held_lock_entry(lock);

kernel/bpf/rqspinlock.c int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val) · line 372

Quoted 10 lines
kernel/bpf/rqspinlock.c +10 -0
+
+       if (val & _Q_PENDING_VAL)
+               mask = _Q_LOCKED_PENDING_MASK;
+
+       /*
+        * Do a deadlock check on the entry of the slowpath
+        */
+       ret = check_deadlock(lock, mask);
+       if (ret)
+               goto err_release_entry;

As I explained above, this won't be sufficient. Imagine that there is an ABBA case and we have A over B here,
but B over A hasn't had its A populated in the other CPU's table right at this moment. Once you do the checks
here and conclude there isn't a deadlock, the write can go through, and then you'd probably end up in a deadlock again.

Regardless, I think in general, it is not a good idea to add more overhead to the slow path to detect rare cases such as deadlocks. For correct code, they will never occur in practice, so all of this quick detection cost is simply overhead that slows everyone down. The ABBA checks are pretty expensive on big machines since the complexity is O(N).

If you have time, please review patches that I plan to send improving all of this for non-head waiters later on.
I will add you to the Cc list.

Thanks

Quoted 3 lines

[...]

#2 lore raw
Quoted 10 lines · Kumar Kartikeya Dwivedi
Quoted 6 lines · Siddharth Chintamaneni

A single deadlock check at the start of slowpath function enables quick deadlock detection. This additional check don't create any overhead because same check happens in both pending and queuing cases during contention. Also cleaned up the unused function args in check_deadlock* functions.

Quoted 8 lines

What's the motivation? Are you trying to address the bug that the recent in_nmi() fix tried to work around?
Note that I'm working on a proper fix; just doing deadlock detection on entry into non-head waiter slow path is not sufficient, as the table updates for held locks is racy and can populate a deadlock-signalling combination right after our check, so it needs to happen repeatedly.

I've seen the in_nmi() check that you've added to address this issue for now. The main motivation is to quickly detect the deadlocks if it is obvious with a single check.

Quoted 6 lines
Quoted 5 lines

I've checked the resilient spinlocks cover letter for benchmarks to run but I couldn't figure out the link to run those benchmarks. Can you point me to those benchmarks so that I can run that with this change?

Quoted 8 lines

All benchmark scripts are here: https://github.com/kkdwivedi/rqspinlock
But they can also be run manually. I ran will-it-scale and locktorture back then.
The description of which locks contend for various cases (openN_threads, lockN_threads) is in the CNA paper. [0]

[0]: https://arxiv.org/pdf/1810.05600

Thanks for sharing this is helpful.

Quoted 67 lines
Quoted 67 lines
Fixes a8fcf2a ("locking: Copy out qspinlock.c to kernel/bpf/rqspinlock.c")
---
 kernel/bpf/rqspinlock.c | 45 ++++++++++++++++++++++-------------------
 1 file changed, 24 insertions(+), 21 deletions(-)
kernel/bpf/rqspinlock.c +7 -10
index a00561b1d3e5..6ec4e97a73a2 100644
@@ -89,15 +89,14 @@ struct rqspinlock_timeout {
 DEFINE_PER_CPU_ALIGNED(struct rqspinlock_held, rqspinlock_held_locks);
 EXPORT_SYMBOL_GPL(rqspinlock_held_locks);
 
-static bool is_lock_released(rqspinlock_t *lock, u32 mask, struct rqspinlock_timeout *ts)
+static bool is_lock_released(rqspinlock_t *lock, u32 mask)
 {
        if (!(atomic_read_acquire(&lock->val) & (mask)))
                return true;
        return false;
 }
 
-static noinline int check_deadlock_AA(rqspinlock_t *lock, u32 mask,
-                                     struct rqspinlock_timeout *ts)
+static noinline int check_deadlock_AA(rqspinlock_t *lock)
 {
        struct rqspinlock_held *rqh = this_cpu_ptr(&rqspinlock_held_locks);
        int cnt = min(RES_NR_HELD, rqh->cnt);
@@ -118,8 +117,7 @@ static noinline int check_deadlock_AA(rqspinlock_t *lock, u32 mask,
  * more locks, which reduce to ABBA). This is not exhaustive, and we rely on
  * timeouts as the final line of defense.
  */
-static noinline int check_deadlock_ABBA(rqspinlock_t *lock, u32 mask,
-                                       struct rqspinlock_timeout *ts)
+static noinline int check_deadlock_ABBA(rqspinlock_t *lock, u32 mask)
 {
        struct rqspinlock_held *rqh = this_cpu_ptr(&rqspinlock_held_locks);
        int rqh_cnt = min(RES_NR_HELD, rqh->cnt);
@@ -142,7 +140,7 @@ static noinline int check_deadlock_ABBA(rqspinlock_t *lock, u32 mask,
                 * Let's ensure to break out of this loop if the lock is available for
                 * us to potentially acquire.
                 */
-               if (is_lock_released(lock, mask, ts))
+               if (is_lock_released(lock, mask))
                        return 0;
 
                /*
@@ -198,15 +196,14 @@ static noinline int check_deadlock_ABBA(rqspinlock_t *lock, u32 mask,
        return 0;
 }
 
-static noinline int check_deadlock(rqspinlock_t *lock, u32 mask,
-                                  struct rqspinlock_timeout *ts)
+static noinline int check_deadlock(rqspinlock_t *lock, u32 mask)
 {
        int ret;
 
-       ret = check_deadlock_AA(lock, mask, ts);
+       ret = check_deadlock_AA(lock);
        if (ret)
                return ret;
-       ret = check_deadlock_ABBA(lock, mask, ts);
+       ret = check_deadlock_ABBA(lock, mask);
        if (ret)
                return ret;
 
Quoted 10 lines

kernel/bpf/rqspinlock.c static noinline int check_timeout(rqspinlock_t *lock, u32 mask, · line 234

Quoted 6 lines
kernel/bpf/rqspinlock.c +1 -1
@@ -234,7 +231,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, ts);
+               return check_deadlock(lock, mask);

This removal of unused arguments still looks useful, please send it as a separate clean up.

Will do.

Quoted 29 lines
Quoted 29 lines
kernel/bpf/rqspinlock.c +14 -1
        }
 
        return 0;
@@ -350,7 +347,7 @@ int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val)
        struct mcs_spinlock *prev, *next, *node;
        struct rqspinlock_timeout ts;
        int idx, ret = 0;
-       u32 old, tail;
+       u32 old, tail, mask = _Q_LOCKED_MASK;
 
        BUILD_BUG_ON(CONFIG_NR_CPUS >= (1U << _Q_TAIL_CPU_BITS));
 
@@ -359,6 +356,21 @@ int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val)
 
        RES_INIT_TIMEOUT(ts);
 
+       /*
+        * Grab an entry in the held locks array, to enable deadlock detection
+        */
+       grab_held_lock_entry(lock);
+
+       if (val & _Q_PENDING_VAL)
+               mask = _Q_LOCKED_PENDING_MASK;
+
+       /*
+        * Do a deadlock check on the entry of the slowpath
+        */
+       ret = check_deadlock(lock, mask);
+       if (ret)
Quoted 9 lines

kernel/bpf/rqspinlock.c int __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val) · line 372

Quoted 1 line
kernel/bpf/rqspinlock.c +1 -0
+               goto err_release_entry;

As I explained above, this won't be sufficient. Imagine that there is an ABBA case and we have A over B here,
but B over A hasn't had its A populated in the other CPU's table right at this moment. Once you do the checks
here and conclude there isn't a deadlock, the write can go through, and then you'd probably end up in a deadlock again.

The idea is not to declare that it is safe after this check because resilient timeout checks will still happen during pending and queuing state.

Quoted 7 lines

Regardless, I think in general, it is not a good idea to add more overhead to the slow path to detect rare cases such as deadlocks. For correct code, they will never occur in practice, so all of this quick detection cost is simply overhead that slows everyone down. The ABBA checks are pretty expensive on big machines since the complexity is O(N).

Initially I've just added an AA check but later included ABBA as well to get your thoughts. I am curious about the overhead.

Quoted 4 lines

If you have time, please review patches that I plan to send improving all of this for non-head waiters later on.
I will add you to the Cc list.

Will definitely check, Thanks!

Quoted 5 lines

Thanks

Quoted 3 lines

[...]