Message-ID: <CAP01T77FDwOs8wP2UvUNHC=oRE-ivUA5Ay04o0rnSc-M1NLmHA@mail.gmail.com>
Date: Thu, 9 Jan 2025 01:49:54 +0530
From: Kumar Kartikeya Dwivedi <memxor@...il.com>
To: Waiman Long <llong@...hat.com>
Cc: bpf@...r.kernel.org, linux-kernel@...r.kernel.org, 
	Linus Torvalds <torvalds@...ux-foundation.org>, Peter Zijlstra <peterz@...radead.org>, 
	Alexei Starovoitov <ast@...nel.org>, Andrii Nakryiko <andrii@...nel.org>, 
	Daniel Borkmann <daniel@...earbox.net>, Martin KaFai Lau <martin.lau@...nel.org>, 
	Eduard Zingerman <eddyz87@...il.com>, "Paul E. McKenney" <paulmck@...nel.org>, Tejun Heo <tj@...nel.org>, 
	Barret Rhoden <brho@...gle.com>, Josh Don <joshdon@...gle.com>, Dohyun Kim <dohyunkim@...gle.com>, 
	kernel-team@...a.com
Subject: Re: [PATCH bpf-next v1 11/22] rqspinlock: Add deadlock detection and recovery

On Wed, 8 Jan 2025 at 21:36, Waiman Long <llong@...hat.com> wrote:
>
>
> On 1/7/25 8:59 AM, Kumar Kartikeya Dwivedi wrote:
> > While the timeout logic provides guarantees for the waiter's forward
> > progress, the time until a stalling waiter unblocks can still be long.
> > The default timeout of 1/2 sec can be excessively long for some use
> > cases.  Additionally, custom timeouts may exacerbate recovery time.
> >
> > Introduce logic to detect common cases of deadlocks and perform quicker
> > recovery. This is done by dividing the time from entry into the locking
> > slow path until the timeout into intervals of 1 ms. Then, after each
> > interval elapses, deadlock detection is performed, while also polling
> > the lock word to ensure we can quickly break out of the detection logic
> > and proceed with lock acquisition.
> >
> > A 'held_locks' table is maintained per-CPU where the entry at the bottom
> > denotes a lock being waited for or already taken. Entries coming before
> > it denote locks that are already held. The current CPU's table can thus
> > be looked at to detect AA deadlocks. The tables from other CPUs can be
> > looked at to discover ABBA situations. Finally, when a matching entry
> > for the lock being taken on the current CPU is found on some other CPU,
> > a deadlock situation is detected. This function can take a long time,
> > therefore the lock word is constantly polled in each loop iteration to
> > ensure we can preempt detection and proceed with lock acquisition, using
> > the is_lock_released check.
> >
> > We set 'spin' member of rqspinlock_timeout struct to 0 to trigger
> > deadlock checks immediately to perform faster recovery.
> >
> > Note: Extending lock word size by 4 bytes to record owner CPU can allow
> > faster detection for ABBA. It is typically the owner which participates
> > in a ABBA situation. However, to keep compatibility with existing lock
> > words in the kernel (struct qspinlock), and given deadlocks are a rare
> > event triggered by bugs, we choose to favor compatibility over faster
> > detection.
> >
> > Signed-off-by: Kumar Kartikeya Dwivedi <memxor@...il.com>
> > ---
> >   include/asm-generic/rqspinlock.h |  56 +++++++++-
> >   kernel/locking/rqspinlock.c      | 178 ++++++++++++++++++++++++++++---
> >   2 files changed, 220 insertions(+), 14 deletions(-)
> >
> > diff --git a/include/asm-generic/rqspinlock.h b/include/asm-generic/rqspinlock.h
> > index 5c996a82e75f..c7e33ccc57a6 100644
> > --- a/include/asm-generic/rqspinlock.h
> > +++ b/include/asm-generic/rqspinlock.h
> > @@ -11,14 +11,68 @@
> >
> >   #include <linux/types.h>
> >   #include <vdso/time64.h>
> > +#include <linux/percpu.h>
> >
> >   struct qspinlock;
> >
> > +extern int resilient_queued_spin_lock_slowpath(struct qspinlock *lock, u32 val, u64 timeout);
> > +
> >   /*
> >    * Default timeout for waiting loops is 0.5 seconds
> >    */
> >   #define RES_DEF_TIMEOUT (NSEC_PER_SEC / 2)
> >
> > -extern int resilient_queued_spin_lock_slowpath(struct qspinlock *lock, u32 val, u64 timeout);
> > +#define RES_NR_HELD 32
> > +
> > +struct rqspinlock_held {
> > +     int cnt;
> > +     void *locks[RES_NR_HELD];
> > +};
> > +
> > +DECLARE_PER_CPU_ALIGNED(struct rqspinlock_held, rqspinlock_held_locks);
> > +
> > +static __always_inline void grab_held_lock_entry(void *lock)
> > +{
> > +     int cnt = this_cpu_inc_return(rqspinlock_held_locks.cnt);
> > +
> > +     if (unlikely(cnt > RES_NR_HELD)) {
> > +             /* Still keep the inc so we decrement later. */
> > +             return;
> > +     }
> > +
> > +     /*
> > +      * Implied compiler barrier in per-CPU operations; otherwise we can have
> > +      * the compiler reorder inc with write to table, allowing interrupts to
> > +      * overwrite and erase our write to the table (as on interrupt exit it
> > +      * will be reset to NULL).
> > +      */
> > +     this_cpu_write(rqspinlock_held_locks.locks[cnt - 1], lock);
> > +}
> > +
> > +/*
> > + * It is possible to run into misdetection scenarios of AA deadlocks on the same
> > + * CPU, and missed ABBA deadlocks on remote CPUs when this function pops entries
> > + * out of order (due to lock A, lock B, unlock A, unlock B) pattern. The correct
> > + * logic to preserve right entries in the table would be to walk the array of
> > + * held locks and swap and clear out-of-order entries, but that's too
> > + * complicated and we don't have a compelling use case for out of order unlocking.
> Maybe we can pass in the lock and print a warning if out-of-order unlock
> is being done.

I think alternatively, I will constrain the verifier in v2 to require
lock release to be in-order, which would obviate the need to warn at
runtime and reject programs potentially doing out-of-order unlocks.
This doesn't cover in-kernel users though, but we're not doing
out-of-order unlocks with this lock there, and it would be yet another
branch in the unlock function with little benefit.

> > + *
> > + * Therefore, we simply don't support such cases and keep the logic simple here.
> > + */
> > +static __always_inline void release_held_lock_entry(void)
> > +{
> > +     struct rqspinlock_held *rqh = this_cpu_ptr(&rqspinlock_held_locks);
> > +
> > +     if (unlikely(rqh->cnt > RES_NR_HELD))
> > +             goto dec;
> > +     smp_store_release(&rqh->locks[rqh->cnt - 1], NULL);
> > +     /*
> > +      * Overwrite of NULL should appear before our decrement of the count to
> > +      * other CPUs, otherwise we have the issue of a stale non-NULL entry being
> > +      * visible in the array, leading to misdetection during deadlock detection.
> > +      */
> > +dec:
> > +     this_cpu_dec(rqspinlock_held_locks.cnt);
> AFAIU, smp_store_release() only guarantees memory ordering before it,
> not after. That shouldn't be a problem if the decrement is observed
> before clearing the entry as that non-NULL entry won't be checked anyway.

Ack, I will improve the comment, it's a bit misleading right now.

> > +}
> >
> >   #endif /* __ASM_GENERIC_RQSPINLOCK_H */
> > diff --git a/kernel/locking/rqspinlock.c b/kernel/locking/rqspinlock.c
> > index b63f92bd43b1..b7c86127d288 100644
> > --- a/kernel/locking/rqspinlock.c
> > +++ b/kernel/locking/rqspinlock.c
> > @@ -30,6 +30,7 @@
> >    * Include queued spinlock definitions and statistics code
> >    */
> >   #include "qspinlock.h"
> > +#include "rqspinlock.h"
> >   #include "qspinlock_stat.h"
> >
> >   /*
> > @@ -74,16 +75,141 @@
> >   struct rqspinlock_timeout {
> >       u64 timeout_end;
> >       u64 duration;
> > +     u64 cur;
> >       u16 spin;
> >   };
> >
> >   #define RES_TIMEOUT_VAL     2
> >
> > -static noinline int check_timeout(struct rqspinlock_timeout *ts)
> > +DEFINE_PER_CPU_ALIGNED(struct rqspinlock_held, rqspinlock_held_locks);
> > +
> > +static bool is_lock_released(struct qspinlock *lock, u32 mask, struct rqspinlock_timeout *ts)
> > +{
> > +     if (!(atomic_read_acquire(&lock->val) & (mask)))
> > +             return true;
> > +     return false;
> > +}
> > +
> > +static noinline int check_deadlock_AA(struct qspinlock *lock, u32 mask,
> > +                                   struct rqspinlock_timeout *ts)
> > +{
> > +     struct rqspinlock_held *rqh = this_cpu_ptr(&rqspinlock_held_locks);
> > +     int cnt = min(RES_NR_HELD, rqh->cnt);
> > +
> > +     /*
> > +      * Return an error if we hold the lock we are attempting to acquire.
> > +      * We'll iterate over max 32 locks; no need to do is_lock_released.
> > +      */
> > +     for (int i = 0; i < cnt - 1; i++) {
> > +             if (rqh->locks[i] == lock)
> > +                     return -EDEADLK;
> > +     }
> > +     return 0;
> > +}
> > +
> > +static noinline int check_deadlock_ABBA(struct qspinlock *lock, u32 mask,
> > +                                     struct rqspinlock_timeout *ts)
> > +{
>
> I think you should note that the ABBA check here is not exhaustive. It
> is just the most common case and there are corner cases that will be missed.

Ack, will add a comment.

>
> Cheers,
> Longman
>

Powered by blists - more mailing lists