bpf: Add deadlock check at the entry of slowpath for quick exit
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?
--- kernel/bpf/rqspinlock.c | 45 ++++++++++++++++++++++------------------- 1 file changed, 24 insertions(+), 21 deletions(-)
kernel/bpf/rqspinlock.c +24 -21
@@ -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
Kumar Kartikeya Dwivedi
maintainerQuoted 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")Signed-off-by Siddharth Chintamaneni <[email protected]>--- kernel/bpf/rqspinlock.c | 45 ++++++++++++++++++++++------------------- 1 file changed, 24 insertions(+), 21 deletions(-)kernel/bpf/rqspinlock.c +7
-10@@ -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
[...]
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]
Thanks for sharing this is helpful.
Quoted 67 lines
Quoted 67 lines
Fixes a8fcf2a ("locking: Copy out qspinlock.c to kernel/bpf/rqspinlock.c")Signed-off-by Siddharth Chintamaneni <[email protected]>--- kernel/bpf/rqspinlock.c | 45 ++++++++++++++++++++++------------------- 1 file changed, 24 insertions(+), 21 deletions(-)kernel/bpf/rqspinlock.c +7
-10@@ -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
[...]