[bpf-next,v2,07/26] rqspinlock: Add support for timeouts

Commit Message

Kumar Kartikeya Dwivedi Feb. 6, 2025, 10:54 a.m. UTC

Introduce policy macro RES_CHECK_TIMEOUT which can be used to detect
when the timeout has expired for the slow path to return an error. It
depends on being passed two variables initialized to 0: ts, ret. The
'ts' parameter is of type rqspinlock_timeout.

This macro resolves to the (ret) expression so that it can be used in
statements like smp_cond_load_acquire to break the waiting loop
condition.

The 'spin' member is used to amortize the cost of checking time by
dispatching to the implementation every 64k iterations. The
'timeout_end' member is used to keep track of the timestamp that denotes
the end of the waiting period. The 'ret' parameter denotes the status of
the timeout, and can be checked in the slow path to detect timeouts
after waiting loops.

The 'duration' member is used to store the timeout duration for each
waiting loop, that is passed down from the caller of the slow path
function.  Use the RES_INIT_TIMEOUT macro to initialize it. The default
timeout value defined in the header (RES_DEF_TIMEOUT) is 0.5 seconds.

This macro will be used as a condition for waiting loops in the slow
path.  Since each waiting loop applies a fresh timeout using the same
rqspinlock_timeout, we add a new RES_RESET_TIMEOUT as well to ensure the
values can be easily reinitialized to the default state.

Reviewed-by: Barret Rhoden <[e-mail]>
Signed-off-by: Kumar Kartikeya Dwivedi <[e-mail]>
---
 include/asm-generic/rqspinlock.h |  8 +++++-
 kernel/locking/rqspinlock.c      | 46 +++++++++++++++++++++++++++++++-
 2 files changed, 52 insertions(+), 2 deletions(-)

Comments

Peter Zijlstra Feb. 10, 2025, 9:56 a.m. UTC | #1

On Thu, Feb 06, 2025 at 02:54:15AM -0800, Kumar Kartikeya Dwivedi wrote:
> @@ -68,6 +71,44 @@
>  
>  #include "mcs_spinlock.h"
>  
> +struct rqspinlock_timeout {
> +	u64 timeout_end;
> +	u64 duration;
> +	u16 spin;
> +};
> +
> +static noinline int check_timeout(struct rqspinlock_timeout *ts)
> +{
> +	u64 time = ktime_get_mono_fast_ns();

This is only sane if you have a TSC clocksource. If you ever manage to
hit the HPET fallback, you're *really* sad.

> +
> +	if (!ts->timeout_end) {
> +		ts->timeout_end = time + ts->duration;
> +		return 0;
> +	}
> +
> +	if (time > ts->timeout_end)
> +		return -ETIMEDOUT;
> +
> +	return 0;
> +}
> +
> +#define RES_CHECK_TIMEOUT(ts, ret)                    \
> +	({                                            \
> +		if (!(ts).spin++)                     \
> +			(ret) = check_timeout(&(ts)); \
> +		(ret);                                \
> +	})

Alexei Starovoitov Feb. 11, 2025, 4:55 a.m. UTC | #2

On Mon, Feb 10, 2025 at 1:56 AM Peter Zijlstra <[e-mail]> wrote:
>
> On Thu, Feb 06, 2025 at 02:54:15AM -0800, Kumar Kartikeya Dwivedi wrote:
> > @@ -68,6 +71,44 @@
> >
> >  #include "mcs_spinlock.h"
> >
> > +struct rqspinlock_timeout {
> > +     u64 timeout_end;
> > +     u64 duration;
> > +     u16 spin;
> > +};
> > +
> > +static noinline int check_timeout(struct rqspinlock_timeout *ts)
> > +{
> > +     u64 time = ktime_get_mono_fast_ns();
>
> This is only sane if you have a TSC clocksource. If you ever manage to
> hit the HPET fallback, you're *really* sad.

ktime_get_mono_fast_ns() is the best NMI safe time source we're aware of.
perf, rcu, even hardlockup detector are using it.
The clock source can drop to hpet on buggy hw and everything is indeed
sad in that case, but not like we have a choice.
Note that the timeout detection is the last resort.
The logic goes through AA and ABBA detection first.
So timeout means that the locking dependency is quite complex.
Periodically checking "are we spinning too long" via
ktime_get_mono_fast_ns() is what lets us abort the lock.
Maybe I'm missing the concern.
Should we use
__arch_get_hw_counter(VDSO_CLOCKMODE_TSC, NULL) instead ?

Peter Zijlstra Feb. 11, 2025, 10:11 a.m. UTC | #3

On Mon, Feb 10, 2025 at 08:55:56PM -0800, Alexei Starovoitov wrote:
> On Mon, Feb 10, 2025 at 1:56 AM Peter Zijlstra <[e-mail]> wrote:
> >
> > On Thu, Feb 06, 2025 at 02:54:15AM -0800, Kumar Kartikeya Dwivedi wrote:
> > > @@ -68,6 +71,44 @@
> > >
> > >  #include "mcs_spinlock.h"
> > >
> > > +struct rqspinlock_timeout {
> > > +     u64 timeout_end;
> > > +     u64 duration;
> > > +     u16 spin;
> > > +};
> > > +
> > > +static noinline int check_timeout(struct rqspinlock_timeout *ts)
> > > +{
> > > +     u64 time = ktime_get_mono_fast_ns();
> >
> > This is only sane if you have a TSC clocksource. If you ever manage to
> > hit the HPET fallback, you're *really* sad.
> 
> ktime_get_mono_fast_ns() is the best NMI safe time source we're aware of.
> perf, rcu, even hardlockup detector are using it.

perf is primarily using local_clock(), as is the scheduler.

Alexei Starovoitov Feb. 11, 2025, 6 p.m. UTC | #4

On Tue, Feb 11, 2025 at 2:11 AM Peter Zijlstra <[e-mail]> wrote:
>
> On Mon, Feb 10, 2025 at 08:55:56PM -0800, Alexei Starovoitov wrote:
> > On Mon, Feb 10, 2025 at 1:56 AM Peter Zijlstra <[e-mail]> wrote:
> > >
> > > On Thu, Feb 06, 2025 at 02:54:15AM -0800, Kumar Kartikeya Dwivedi wrote:
> > > > @@ -68,6 +71,44 @@
> > > >
> > > >  #include "mcs_spinlock.h"
> > > >
> > > > +struct rqspinlock_timeout {
> > > > +     u64 timeout_end;
> > > > +     u64 duration;
> > > > +     u16 spin;
> > > > +};
> > > > +
> > > > +static noinline int check_timeout(struct rqspinlock_timeout *ts)
> > > > +{
> > > > +     u64 time = ktime_get_mono_fast_ns();
> > >
> > > This is only sane if you have a TSC clocksource. If you ever manage to
> > > hit the HPET fallback, you're *really* sad.
> >
> > ktime_get_mono_fast_ns() is the best NMI safe time source we're aware of.
> > perf, rcu, even hardlockup detector are using it.
>
> perf is primarily using local_clock(), as is the scheduler.

We considered it, but I think it won't tick when irqs are disabled,
since the generic part is jiffies based ?

Patch

diff --git a/include/asm-generic/rqspinlock.h b/include/asm-generic/rqspinlock.h
index 54860b519571..c89733cbe643 100644
--- a/include/asm-generic/rqspinlock.h
+++ b/include/asm-generic/rqspinlock.h
@@ -10,10 +10,16 @@ 
 #define __ASM_GENERIC_RQSPINLOCK_H
 
 #include <linux/types.h>
+#include <vdso/time64.h>
 
 struct qspinlock;
 typedef struct qspinlock rqspinlock_t;
 
-extern void resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val);
+/*
+ * Default timeout for waiting loops is 0.5 seconds
+ */
+#define RES_DEF_TIMEOUT (NSEC_PER_SEC / 2)
+
+extern void resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val, u64 timeout);
 
 #endif /* __ASM_GENERIC_RQSPINLOCK_H */
diff --git a/kernel/locking/rqspinlock.c b/kernel/locking/rqspinlock.c
index 52db60cd9691..200454e9c636 100644
--- a/kernel/locking/rqspinlock.c
+++ b/kernel/locking/rqspinlock.c
@@ -6,9 +6,11 @@ 
  * (C) Copyright 2013-2014,2018 Red Hat, Inc.
  * (C) Copyright 2015 Intel Corp.
  * (C) Copyright 2015 Hewlett-Packard Enterprise Development LP
+ * (C) Copyright 2024 Meta Platforms, Inc. and affiliates.
  *
  * Authors: Waiman Long <[e-mail]>
  *          Peter Zijlstra <[e-mail]>
+ *          Kumar Kartikeya Dwivedi <[e-mail]>
  */
 
 #include <linux/smp.h>
@@ -22,6 +24,7 @@ 
 #include <asm/qspinlock.h>
 #include <trace/events/lock.h>
 #include <asm/rqspinlock.h>
+#include <linux/timekeeping.h>
 
 /*
  * Include queued spinlock definitions and statistics code
@@ -68,6 +71,44 @@ 
 
 #include "mcs_spinlock.h"
 
+struct rqspinlock_timeout {
+	u64 timeout_end;
+	u64 duration;
+	u16 spin;
+};
+
+static noinline int check_timeout(struct rqspinlock_timeout *ts)
+{
+	u64 time = ktime_get_mono_fast_ns();
+
+	if (!ts->timeout_end) {
+		ts->timeout_end = time + ts->duration;
+		return 0;
+	}
+
+	if (time > ts->timeout_end)
+		return -ETIMEDOUT;
+
+	return 0;
+}
+
+#define RES_CHECK_TIMEOUT(ts, ret)                    \
+	({                                            \
+		if (!(ts).spin++)                     \
+			(ret) = check_timeout(&(ts)); \
+		(ret);                                \
+	})
+
+/*
+ * Initialize the 'duration' member with the chosen timeout.
+ */
+#define RES_INIT_TIMEOUT(ts, _timeout) ({ (ts).spin = 1; (ts).duration = _timeout; })
+
+/*
+ * We only need to reset 'timeout_end', 'spin' will just wrap around as necessary.
+ */
+#define RES_RESET_TIMEOUT(ts) ({ (ts).timeout_end = 0; })
+
 /*
  * Per-CPU queue node structures; we can never have more than 4 nested
  * contexts: task, softirq, hardirq, nmi.
@@ -97,14 +138,17 @@  static DEFINE_PER_CPU_ALIGNED(struct qnode, qnodes[_Q_MAX_NODES]);
  * contended             :    (*,x,y) +--> (*,0,0) ---> (*,0,1) -'  :
  *   queue               :         ^--'                             :
  */
-void __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val)
+void __lockfunc resilient_queued_spin_lock_slowpath(rqspinlock_t *lock, u32 val, u64 timeout)
 {
 	struct mcs_spinlock *prev, *next, *node;
+	struct rqspinlock_timeout ts;
 	u32 old, tail;
 	int idx;
 
 	BUILD_BUG_ON(CONFIG_NR_CPUS >= (1U << _Q_TAIL_CPU_BITS));
 
+	RES_INIT_TIMEOUT(ts, timeout);
+
 	/*
 	 * Wait for in-progress pending->locked hand-overs with a bounded
 	 * number of spins so that we guarantee forward progress.