[PATCH v3 0/5] sched_ext: Support high-performance monotonically non-decreasing clock

[PATCH v3 0/5] sched_ext: Support high-performance monotonically non-decreasing clock

[Changwoo Min]

Many BPF schedulers (such as scx_central, scx_lavd, scx_rusty, scx_bpfland,
and scx_flash) frequently call bpf_ktime_get_ns() for tracking tasks' runtime
properties. If supported, bpf_ktime_get_ns() eventually reads a hardware
timestamp counter (TSC). However, reading a hardware TSC is not
performant in some hardware platforms, degrading IPC.

This patchset addresses the performance problem of reading hardware TSC
by leveraging the rq clock in the scheduler core, introducing a
scx_bpf_clock_get_ns() function for BPF schedulers. Whenever the rq clock
is fresh and valid, scx_bpf_clock_get_ns() provides the rq clock, which is
already updated by the scheduler core (update_rq_clock), so it can reduce
reading the hardware TSC.

When the rq lock is released (rq_unpin_lock) or a long-running
operations are done by the BPF scheduler (ops.running, ops.update_idle),
the rq clock is invalidated, so a subsequent scx_bpf_clock_get_ns() call
gets the fresh sched_clock for the caller.

In addition, scx_bpf_clock_get_ns() guarantees the clock is
monotonically non-decreasing for the same CPU, so the clock cannot go
backward in the same CPU.

Using scx_bpf_clock_get_ns() reduces the number of reading hardware TSC
by 40-70% (65% for scx_lavd, 58% for scx_bpfland, and 43% for scx_rusty)
for the following benchmark.

    perf bench -f simple sched messaging -t -g 20 -l 6000

The patchset begins by managing the status of rq clock in the scheduler
core, then implementing scx_bpf_clock_get_ns(), and finally applying it
to the BPF schedulers.

ChangeLog v2 -> v3:
  - To avoid unnecessarily modifying cache lines, scx_rq_clock_update()
    and scx_rq_clock_stale() update the clock and flags only when a
    sched_ext scheduler is enabled.

ChangeLog v1 -> v2:
  - Rename SCX_RQ_CLK_UPDATED to SCX_RQ_CLK_VALID to denote the validity
    of an rq clock clearly.
  - Rearrange the clock and flags fields in struct scx_rq to make sure
    they are in the same cacheline to minimize the cache misses 
  - Add an additional explanation to the commit message in the 2/5 patch
    describing when the rq clock will be reused with an example.
  - Fix typos
  - Rebase the code to the tip of Tejun's sched_ext repo

Changwoo Min (5):
  sched_ext: Implement scx_rq_clock_update/stale()
  sched_ext: Manage the validity of scx_rq_clock
  sched_ext: Implement scx_bpf_clock_get_ns()
  sched_ext: Add scx_bpf_clock_get_ns() for BPF scheduler
  sched_ext: Replace bpf_ktime_get_ns() to scx_bpf_clock_get_ns()

 kernel/sched/core.c                      |  6 +-
 kernel/sched/ext.c                       | 74 ++++++++++++++++++++++++
 kernel/sched/sched.h                     | 50 +++++++++++-----
 tools/sched_ext/include/scx/common.bpf.h |  1 +
 tools/sched_ext/include/scx/compat.bpf.h |  5 ++
 tools/sched_ext/scx_central.bpf.c        |  4 +-
 tools/sched_ext/scx_flatcg.bpf.c         |  2 +-
 7 files changed, 123 insertions(+), 19 deletions(-)

-- 
2.47.1

[PATCH v3 1/5] sched_ext: Implement scx_rq_clock_update/stale()

[Changwoo Min]

scx_rq_clock_update() and scx_rq_clock_stale() manage the status of an
rq clock when sched_ext is enabled. scx_rq_clock_update() keeps the rq
clock in memory and its status valid. scx_rq_clock_stale() invalidates
the current rq clock not to use the cached rq clock.

Signed-off-by: Changwoo Min <changwoo@igalia.com>
---
 kernel/sched/sched.h | 48 +++++++++++++++++++++++++++++++-------------
 1 file changed, 34 insertions(+), 14 deletions(-)

diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 76f5f53a645f..da55b39c9e58 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -754,6 +754,7 @@ enum scx_rq_flags {
 	SCX_RQ_BAL_PENDING	= 1 << 2, /* balance hasn't run yet */
 	SCX_RQ_BAL_KEEP		= 1 << 3, /* balance decided to keep current */
 	SCX_RQ_BYPASSING	= 1 << 4,
+	SCX_RQ_CLK_VALID	= 1 << 5, /* RQ clock is fresh and valid */
 
 	SCX_RQ_IN_WAKEUP	= 1 << 16,
 	SCX_RQ_IN_BALANCE	= 1 << 17,
@@ -766,8 +767,9 @@ struct scx_rq {
 	unsigned long		ops_qseq;
 	u64			extra_enq_flags;	/* see move_task_to_local_dsq() */
 	u32			nr_running;
-	u32			flags;
 	u32			cpuperf_target;		/* [0, SCHED_CAPACITY_SCALE] */
+	u64			clock;			/* cached per-rq clock -- see scx_bpf_clock_get_ns() */
+	u32			flags;
 	bool			cpu_released;
 	cpumask_var_t		cpus_to_kick;
 	cpumask_var_t		cpus_to_kick_if_idle;
@@ -1717,6 +1719,37 @@ struct rq_flags {
 
 extern struct balance_callback balance_push_callback;
 
+#ifdef CONFIG_SCHED_CLASS_EXT
+extern const struct sched_class ext_sched_class;
+
+DECLARE_STATIC_KEY_FALSE(__scx_ops_enabled);	/* SCX BPF scheduler loaded */
+DECLARE_STATIC_KEY_FALSE(__scx_switched_all);	/* all fair class tasks on SCX */
+
+#define scx_enabled()		static_branch_unlikely(&__scx_ops_enabled)
+#define scx_switched_all()	static_branch_unlikely(&__scx_switched_all)
+
+static inline void scx_rq_clock_update(struct rq *rq, u64 clock)
+{
+	if (scx_enabled()) {
+		rq->scx.clock = clock;
+		rq->scx.flags |= SCX_RQ_CLK_VALID;
+	}
+}
+
+static inline void scx_rq_clock_stale(struct rq *rq)
+{
+	if (scx_enabled())
+		rq->scx.flags &= ~SCX_RQ_CLK_VALID;
+}
+
+#else /* !CONFIG_SCHED_CLASS_EXT */
+#define scx_enabled()		false
+#define scx_switched_all()	false
+
+static inline void scx_rq_clock_update(struct rq *rq, u64 clock) {}
+static inline void scx_rq_clock_stale(struct rq *rq) {}
+#endif /* !CONFIG_SCHED_CLASS_EXT */
+
 /*
  * Lockdep annotation that avoids accidental unlocks; it's like a
  * sticky/continuous lockdep_assert_held().
@@ -2505,19 +2538,6 @@ extern const struct sched_class rt_sched_class;
 extern const struct sched_class fair_sched_class;
 extern const struct sched_class idle_sched_class;
 
-#ifdef CONFIG_SCHED_CLASS_EXT
-extern const struct sched_class ext_sched_class;
-
-DECLARE_STATIC_KEY_FALSE(__scx_ops_enabled);	/* SCX BPF scheduler loaded */
-DECLARE_STATIC_KEY_FALSE(__scx_switched_all);	/* all fair class tasks on SCX */
-
-#define scx_enabled()		static_branch_unlikely(&__scx_ops_enabled)
-#define scx_switched_all()	static_branch_unlikely(&__scx_switched_all)
-#else /* !CONFIG_SCHED_CLASS_EXT */
-#define scx_enabled()		false
-#define scx_switched_all()	false
-#endif /* !CONFIG_SCHED_CLASS_EXT */
-
 /*
  * Iterate only active classes. SCX can take over all fair tasks or be
  * completely disabled. If the former, skip fair. If the latter, skip SCX.
-- 
2.47.1

[PATCH v3 2/5] sched_ext: Manage the validity of scx_rq_clock

[Changwoo Min]

An rq clock becomes valid when it is updated using update_rq_clock()
and invalidated when the rq is unlocked using rq_unpin_lock(). Also,
after long-running operations -- ops.running() and ops.update_idle() --
in a BPF scheduler, the sched_ext core invalidates the rq clock.

Let's suppose the following timeline in the scheduler core:

   T1. rq_lock(rq)
   T2. update_rq_clock(rq)
   T3. a sched_ext BPF operation
   T4. rq_unlock(rq)
   T5. a sched_ext BPF operation
   T6. rq_lock(rq)
   T7. update_rq_clock(rq)

For [T2, T4), we consider that rq clock is valid (SCX_RQ_CLK_VALID is
set), so scx_bpf_clock_get_ns() calls during [T2, T4) (including T3)
will return the rq clock updated at T2. For duration [T4, T7),
when a BPF scheduler can still call scx_bpf_clock_get_ns() (T5), we
consider the rq clock is invalid (SCX_RQ_CLK_VALID is unset at T4). So
when calling scx_bpf_clock_get_ns() at T5, we will return a fresh clock
value by calling sched_clock() internally.

One example of calling scx_bpf_clock_get_ns(), when the rq clock is
invalid (like T5), is in scx_central [1]. The scx_central scheduler uses
a BPF timer for preemptive scheduling. In every msec, the timer callback
checks if the currently running tasks exceed their timeslice. At the
beginning of the BPF timer callback (central_timerfn in scx_central.bpf.c),
scx_central gets the current time. When the BPF timer callback runs, the rq
clock could be invalid, the same as T5. In this case, scx_bpf_clock_get_ns()
returns a fresh clock value rather than returning the old one (T2).

[1] https://github.com/sched-ext/scx/blob/main/scheds/c/scx_central.bpf.c

Signed-off-by: Changwoo Min <changwoo@igalia.com>
---
 kernel/sched/core.c  | 6 +++++-
 kernel/sched/ext.c   | 3 +++
 kernel/sched/sched.h | 2 +-
 3 files changed, 9 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c
index 95e40895a519..ab8015c8cab4 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -789,6 +789,7 @@ static void update_rq_clock_task(struct rq *rq, s64 delta)
 void update_rq_clock(struct rq *rq)
 {
 	s64 delta;
+	u64 clock;
 
 	lockdep_assert_rq_held(rq);
 
@@ -800,11 +801,14 @@ void update_rq_clock(struct rq *rq)
 		SCHED_WARN_ON(rq->clock_update_flags & RQCF_UPDATED);
 	rq->clock_update_flags |= RQCF_UPDATED;
 #endif
+	clock = sched_clock_cpu(cpu_of(rq));
+	scx_rq_clock_update(rq, clock);
 
-	delta = sched_clock_cpu(cpu_of(rq)) - rq->clock;
+	delta = clock - rq->clock;
 	if (delta < 0)
 		return;
 	rq->clock += delta;
+
 	update_rq_clock_task(rq, delta);
 }
 
diff --git a/kernel/sched/ext.c b/kernel/sched/ext.c
index 7fff1d045477..ac279a657d50 100644
--- a/kernel/sched/ext.c
+++ b/kernel/sched/ext.c
@@ -2928,6 +2928,8 @@ static void set_next_task_scx(struct rq *rq, struct task_struct *p, bool first)
 	if (SCX_HAS_OP(running) && (p->scx.flags & SCX_TASK_QUEUED))
 		SCX_CALL_OP_TASK(SCX_KF_REST, running, p);
 
+	scx_rq_clock_stale(rq);
+
 	clr_task_runnable(p, true);
 
 	/*
@@ -3590,6 +3592,7 @@ void __scx_update_idle(struct rq *rq, bool idle)
 {
 	int cpu = cpu_of(rq);
 
+	scx_rq_clock_stale(rq);
 	if (SCX_HAS_OP(update_idle) && !scx_rq_bypassing(rq)) {
 		SCX_CALL_OP(SCX_KF_REST, update_idle, cpu_of(rq), idle);
 		if (!static_branch_unlikely(&scx_builtin_idle_enabled))
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index da55b39c9e58..7d26731c350f 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -1779,7 +1779,7 @@ static inline void rq_unpin_lock(struct rq *rq, struct rq_flags *rf)
 	if (rq->clock_update_flags > RQCF_ACT_SKIP)
 		rf->clock_update_flags = RQCF_UPDATED;
 #endif
-
+	scx_rq_clock_stale(rq);
 	lockdep_unpin_lock(__rq_lockp(rq), rf->cookie);
 }
 
-- 
2.47.1

[PATCH v3 3/5] sched_ext: Implement scx_bpf_clock_get_ns()

[Changwoo Min]

Returns a high-performance monotonically non-decreasing clock for the
current CPU. The clock returned is in nanoseconds.

It provides the following properties:

1) High performance: Many BPF schedulers call bpf_ktime_get_ns()
 frequently to account for execution time and track tasks' runtime
 properties. Unfortunately, in some hardware platforms, bpf_ktime_get_ns()
 -- which eventually reads a hardware timestamp counter -- is neither
 performant nor scalable. scx_bpf_clock_get_ns() aims to provide a
 high-performance clock by using the rq clock in the scheduler core
 whenever possible.

2) High enough resolution for the BPF scheduler use cases: In most BPF
 scheduler use cases, the required clock resolution is lower than the
 most accurate hardware clock (e.g., rdtsc in x86). scx_bpf_clock_get_ns()
 basically uses the rq clock in the scheduler core whenever it is valid.
 It considers that the rq clock is valid from the time the rq clock is
 updated (update_rq_clock) until the rq is unlocked (rq_unpin_lock).
 In addition, it invalidates the rq clock after long operations --
 ops.running() and ops.update_idle() -- in a BPF scheduler.

3) Monotonically non-decreasing clock for the same CPU:
 scx_bpf_clock_get_ns() guarantees the clock never goes backward when
 comparing them in the same CPU. On the other hand, when comparing clocks
 in different CPUs, there is no such guarantee -- the clock can go backward.
 It provides a monotonically *non-decreasing* clock so that it would provide
 the same clock values in two different scx_bpf_clock_get_ns() calls in the
 same CPU during the same period of when the rq clock is valid.

Signed-off-by: Changwoo Min <changwoo@igalia.com>
---
 kernel/sched/ext.c | 71 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 71 insertions(+)

diff --git a/kernel/sched/ext.c b/kernel/sched/ext.c
index ac279a657d50..9e2656e21593 100644
--- a/kernel/sched/ext.c
+++ b/kernel/sched/ext.c
@@ -7546,6 +7546,76 @@ __bpf_kfunc struct cgroup *scx_bpf_task_cgroup(struct task_struct *p)
 }
 #endif
 
+/**
+ * scx_bpf_clock_get_ns - Returns a high-performance monotonically
+ * non-decreasing clock for the current CPU. The clock returned is in
+ * nanoseconds.
+ *
+ * It provides the following properties:
+ *
+ * 1) High performance: Many BPF schedulers call bpf_ktime_get_ns() frequently
+ *  to account for execution time and track tasks' runtime properties.
+ *  Unfortunately, in some hardware platforms, bpf_ktime_get_ns() -- which
+ *  eventually reads a hardware timestamp counter -- is neither performant nor
+ *  scalable. scx_bpf_clock_get_ns() aims to provide a high-performance clock
+ *  by using the rq clock in the scheduler core whenever possible.
+ *
+ * 2) High enough resolution for the BPF scheduler use cases: In most BPF
+ *  scheduler use cases, the required clock resolution is lower than the most
+ *  accurate hardware clock (e.g., rdtsc in x86). scx_bpf_clock_get_ns()
+ *  basically uses the rq clock in the scheduler core whenever it is valid.
+ *  It considers that the rq clock is valid from the time the rq clock is
+ *  updated (update_rq_clock) until the rq is unlocked (rq_unpin_lock).
+ *  In addition, it invalidates the rq clock after long operations --
+ *  ops.running() and ops.update_idle().
+ *
+ * 3) Monotonically non-decreasing clock for the same CPU:
+ *  scx_bpf_clock_get_ns() guarantees the clock never goes backward when
+ *  comparing them in the same CPU. On the other hand, when comparing clocks
+ *  in different CPUs, there is no such guarantee -- the clock can go backward.
+ *  It provides a monotonically *non-decreasing* clock so that it would provide
+ *  the same clock values in two different scx_bpf_clock_get_ns() calls in the
+ *  same CPU during the same period of when the rq clock is valid.
+ */
+__bpf_kfunc u64 scx_bpf_clock_get_ns(void)
+{
+	static DEFINE_PER_CPU(u64, prev_clk);
+	struct rq *rq = this_rq();
+	u64 pr_clk, cr_clk;
+
+	preempt_disable();
+	pr_clk = __this_cpu_read(prev_clk);
+
+	/*
+	 * If the rq clock is invalid, start a new rq clock period
+	 * with a fresh sched_clock().
+	 */
+	if (!(rq->scx.flags & SCX_RQ_CLK_VALID)) {
+		cr_clk = sched_clock();
+		scx_rq_clock_update(rq, cr_clk);
+	}
+	/*
+	 * If the rq clock is valid, use the cached rq clock
+	 * whenever the clock does not go backward.
+	 */
+	else {
+		cr_clk = rq->scx.clock;
+		/*
+		 * If the clock goes backward, start a new rq clock period
+		 * with a fresh sched_clock().
+		 */
+		if (pr_clk > cr_clk) {
+			cr_clk = sched_clock();
+			scx_rq_clock_update(rq, cr_clk);
+		}
+	}
+
+	__this_cpu_write(prev_clk, cr_clk);
+	preempt_enable();
+
+	return cr_clk;
+}
+
 __bpf_kfunc_end_defs();
 
 BTF_KFUNCS_START(scx_kfunc_ids_any)
@@ -7577,6 +7647,7 @@ BTF_ID_FLAGS(func, scx_bpf_cpu_rq)
 #ifdef CONFIG_CGROUP_SCHED
 BTF_ID_FLAGS(func, scx_bpf_task_cgroup, KF_RCU | KF_ACQUIRE)
 #endif
+BTF_ID_FLAGS(func, scx_bpf_clock_get_ns)
 BTF_KFUNCS_END(scx_kfunc_ids_any)
 
 static const struct btf_kfunc_id_set scx_kfunc_set_any = {
-- 
2.47.1

[PATCH v3 4/5] sched_ext: Add scx_bpf_clock_get_ns() for BPF scheduler

[Changwoo Min]

scx_bpf_clock_get_ns() is added to the header files so the BPF
scheduler can use it.

Signed-off-by: Changwoo Min <changwoo@igalia.com>
---
 tools/sched_ext/include/scx/common.bpf.h | 1 +
 tools/sched_ext/include/scx/compat.bpf.h | 5 +++++
 2 files changed, 6 insertions(+)

diff --git a/tools/sched_ext/include/scx/common.bpf.h b/tools/sched_ext/include/scx/common.bpf.h
index 2f36b7b6418d..230c7f2e8ad6 100644
--- a/tools/sched_ext/include/scx/common.bpf.h
+++ b/tools/sched_ext/include/scx/common.bpf.h
@@ -72,6 +72,7 @@ bool scx_bpf_task_running(const struct task_struct *p) __ksym;
 s32 scx_bpf_task_cpu(const struct task_struct *p) __ksym;
 struct rq *scx_bpf_cpu_rq(s32 cpu) __ksym;
 struct cgroup *scx_bpf_task_cgroup(struct task_struct *p) __ksym __weak;
+u64 scx_bpf_clock_get_ns(void) __ksym __weak;
 
 /*
  * Use the following as @it__iter when calling scx_bpf_dsq_move[_vtime]() from
diff --git a/tools/sched_ext/include/scx/compat.bpf.h b/tools/sched_ext/include/scx/compat.bpf.h
index d56520100a26..d295c59e3f05 100644
--- a/tools/sched_ext/include/scx/compat.bpf.h
+++ b/tools/sched_ext/include/scx/compat.bpf.h
@@ -125,6 +125,11 @@ bool scx_bpf_dispatch_vtime_from_dsq___compat(struct bpf_iter_scx_dsq *it__iter,
 	false;									\
 })
 
+#define scx_bpf_clock_get_ns()							\
+	(bpf_ksym_exists(scx_bpf_clock_get_ns) ?				\
+	 scx_bpf_clock_get_ns() :						\
+	 bpf_ktime_get_ns())
+
 /*
  * Define sched_ext_ops. This may be expanded to define multiple variants for
  * backward compatibility. See compat.h::SCX_OPS_LOAD/ATTACH().
-- 
2.47.1

[PATCH v3 5/5] sched_ext: Replace bpf_ktime_get_ns() to scx_bpf_clock_get_ns()

[Changwoo Min]

In the BPF schedulers that use bpf_ktime_get_ns() -- scx_central and
scx_flatcg, replace bpf_ktime_get_ns() calls to scx_bpf_clock_get_ns().

Signed-off-by: Changwoo Min <changwoo@igalia.com>
---
 tools/sched_ext/scx_central.bpf.c | 4 ++--
 tools/sched_ext/scx_flatcg.bpf.c  | 2 +-
 2 files changed, 3 insertions(+), 3 deletions(-)

diff --git a/tools/sched_ext/scx_central.bpf.c b/tools/sched_ext/scx_central.bpf.c
index e6fad6211f6c..cb7428b6a198 100644
--- a/tools/sched_ext/scx_central.bpf.c
+++ b/tools/sched_ext/scx_central.bpf.c
@@ -245,7 +245,7 @@ void BPF_STRUCT_OPS(central_running, struct task_struct *p)
 	s32 cpu = scx_bpf_task_cpu(p);
 	u64 *started_at = ARRAY_ELEM_PTR(cpu_started_at, cpu, nr_cpu_ids);
 	if (started_at)
-		*started_at = bpf_ktime_get_ns() ?: 1;	/* 0 indicates idle */
+		*started_at = scx_bpf_clock_get_ns() ?: 1;	/* 0 indicates idle */
 }
 
 void BPF_STRUCT_OPS(central_stopping, struct task_struct *p, bool runnable)
@@ -258,7 +258,7 @@ void BPF_STRUCT_OPS(central_stopping, struct task_struct *p, bool runnable)
 
 static int central_timerfn(void *map, int *key, struct bpf_timer *timer)
 {
-	u64 now = bpf_ktime_get_ns();
+	u64 now = scx_bpf_clock_get_ns();
 	u64 nr_to_kick = nr_queued;
 	s32 i, curr_cpu;
 
diff --git a/tools/sched_ext/scx_flatcg.bpf.c b/tools/sched_ext/scx_flatcg.bpf.c
index 4e3afcd260bf..15351bf2f053 100644
--- a/tools/sched_ext/scx_flatcg.bpf.c
+++ b/tools/sched_ext/scx_flatcg.bpf.c
@@ -734,7 +734,7 @@ void BPF_STRUCT_OPS(fcg_dispatch, s32 cpu, struct task_struct *prev)
 	struct fcg_cpu_ctx *cpuc;
 	struct fcg_cgrp_ctx *cgc;
 	struct cgroup *cgrp;
-	u64 now = bpf_ktime_get_ns();
+	u64 now = scx_bpf_clock_get_ns();
 	bool picked_next = false;
 
 	cpuc = find_cpu_ctx();
-- 
2.47.1

Re: [PATCH v3 1/5] sched_ext: Implement scx_rq_clock_update/stale()

[Tejun Heo]

Hello,

On Tue, Dec 03, 2024 at 11:27:58PM +0900, Changwoo Min wrote:
...
> @@ -2505,19 +2538,6 @@ extern const struct sched_class rt_sched_class;
>  extern const struct sched_class fair_sched_class;
>  extern const struct sched_class idle_sched_class;
>  
> -#ifdef CONFIG_SCHED_CLASS_EXT
> -extern const struct sched_class ext_sched_class;
> -
> -DECLARE_STATIC_KEY_FALSE(__scx_ops_enabled);	/* SCX BPF scheduler loaded */
> -DECLARE_STATIC_KEY_FALSE(__scx_switched_all);	/* all fair class tasks on SCX */
> -
> -#define scx_enabled()		static_branch_unlikely(&__scx_ops_enabled)
> -#define scx_switched_all()	static_branch_unlikely(&__scx_switched_all)
> -#else /* !CONFIG_SCHED_CLASS_EXT */
> -#define scx_enabled()		false
> -#define scx_switched_all()	false
> -#endif /* !CONFIG_SCHED_CLASS_EXT */

Can you please separate out code relocations into a separate patch? Here,
it's on the smaller side but patches are difficult to read when they're
mixed up.

Thanks.

-- 
tejun

Re: [PATCH v3 2/5] sched_ext: Manage the validity of scx_rq_clock

[Tejun Heo]

Hello,

On Tue, Dec 03, 2024 at 11:27:59PM +0900, Changwoo Min wrote:
> An rq clock becomes valid when it is updated using update_rq_clock()
> and invalidated when the rq is unlocked using rq_unpin_lock(). Also,
> after long-running operations -- ops.running() and ops.update_idle() --
> in a BPF scheduler, the sched_ext core invalidates the rq clock.

Hmm... why are ops.running() or ops.update_idle() special? ie. How does
sched_ext core determine what are long-running and what are not.

Thanks.

-- 
tejun

Re: [PATCH v3 3/5] sched_ext: Implement scx_bpf_clock_get_ns()

[Tejun Heo]

Hello,

On Tue, Dec 03, 2024 at 11:28:00PM +0900, Changwoo Min wrote:
> +__bpf_kfunc u64 scx_bpf_clock_get_ns(void)
> +{
> +	static DEFINE_PER_CPU(u64, prev_clk);
> +	struct rq *rq = this_rq();

this_rq() is this_cpu_ptr(). Shouldn't this be below preempt_disable() if
this function is allowed to be called from sleepable ops?

> +	u64 pr_clk, cr_clk;
> +
> +	preempt_disable();
> +	pr_clk = __this_cpu_read(prev_clk);

Would it make sense to make the above rq->scx.prev_clk?

> +	/*
> +	 * If the rq clock is invalid, start a new rq clock period
> +	 * with a fresh sched_clock().
> +	 */
> +	if (!(rq->scx.flags & SCX_RQ_CLK_VALID)) {
> +		cr_clk = sched_clock();
> +		scx_rq_clock_update(rq, cr_clk);
> +	}
> +	/*
> +	 * If the rq clock is valid, use the cached rq clock
> +	 * whenever the clock does not go backward.
> +	 */

Can you move the comments inside the if/else bodies so that "} else {" can
stay on the same line?

> +	else {
> +		cr_clk = rq->scx.clock;
> +		/*
> +		 * If the clock goes backward, start a new rq clock period
> +		 * with a fresh sched_clock().
> +		 */

Can you please add comment explaining how this can happen?

Thanks.

-- 
tejun

Re: [PATCH v3 5/5] sched_ext: Replace bpf_ktime_get_ns() to scx_bpf_clock_get_ns()

[Tejun Heo]

On Tue, Dec 03, 2024 at 11:28:02PM +0900, Changwoo Min wrote:
> @@ -245,7 +245,7 @@ void BPF_STRUCT_OPS(central_running, struct task_struct *p)
>  	s32 cpu = scx_bpf_task_cpu(p);
>  	u64 *started_at = ARRAY_ELEM_PTR(cpu_started_at, cpu, nr_cpu_ids);
>  	if (started_at)
> -		*started_at = bpf_ktime_get_ns() ?: 1;	/* 0 indicates idle */
> +		*started_at = scx_bpf_clock_get_ns() ?: 1;	/* 0 indicates idle */

Not from this commit, but how about scx_bpf_now_ns() for the name?

Thanks.

-- 
tejun

Re: [PATCH v3 1/5] sched_ext: Implement scx_rq_clock_update/stale()

[Changwoo Min]

Hello,

On 24. 12. 4. 08:23, Tejun Heo wrote:
> Hello,
> 
> On Tue, Dec 03, 2024 at 11:27:58PM +0900, Changwoo Min wrote:
> ...
>> @@ -2505,19 +2538,6 @@ extern const struct sched_class rt_sched_class;
>>   extern const struct sched_class fair_sched_class;
>>   extern const struct sched_class idle_sched_class;
>>   
>> -#ifdef CONFIG_SCHED_CLASS_EXT
>> -extern const struct sched_class ext_sched_class;
>> -
>> -DECLARE_STATIC_KEY_FALSE(__scx_ops_enabled);	/* SCX BPF scheduler loaded */
>> -DECLARE_STATIC_KEY_FALSE(__scx_switched_all);	/* all fair class tasks on SCX */
>> -
>> -#define scx_enabled()		static_branch_unlikely(&__scx_ops_enabled)
>> -#define scx_switched_all()	static_branch_unlikely(&__scx_switched_all)
>> -#else /* !CONFIG_SCHED_CLASS_EXT */
>> -#define scx_enabled()		false
>> -#define scx_switched_all()	false
>> -#endif /* !CONFIG_SCHED_CLASS_EXT */
> 
> Can you please separate out code relocations into a separate patch? Here,
> it's on the smaller side but patches are difficult to read when they're
> mixed up.

Thanks for the comment! I will separate the code relocation out
in the next version.

Regards,
Changwoo Min

Re: [PATCH v3 2/5] sched_ext: Manage the validity of scx_rq_clock

[Changwoo Min]

Hello,

On 24. 12. 4. 08:26, Tejun Heo wrote:
> Hello,
> 
> On Tue, Dec 03, 2024 at 11:27:59PM +0900, Changwoo Min wrote:
>> An rq clock becomes valid when it is updated using update_rq_clock()
>> and invalidated when the rq is unlocked using rq_unpin_lock(). Also,
>> after long-running operations -- ops.running() and ops.update_idle() --
>> in a BPF scheduler, the sched_ext core invalidates the rq clock.
> 
> Hmm... why are ops.running() or ops.update_idle() special? ie. How does
> sched_ext core determine what are long-running and what are not.

I investigated all sched_ext_ops. Besides these two ops, all the
rest are control operations, of which BPF operation should be
relatively simple. On the other hand, ops.running() and
ops.update_idle() are different from the others since a CPU
executes a task or becomes idle, which could be arbitrarily long.
So I think refreshing the clock in those cases would be nice.
Does it make sense to you?

Regards,
Changwoo Min

Re: [PATCH v3 3/5] sched_ext: Implement scx_bpf_clock_get_ns()

[Changwoo Min]

Hello,


On 24. 12. 4. 08:37, Tejun Heo wrote:
> Hello,
> 
> On Tue, Dec 03, 2024 at 11:28:00PM +0900, Changwoo Min wrote:
>> +__bpf_kfunc u64 scx_bpf_clock_get_ns(void)
>> +{
>> +	static DEFINE_PER_CPU(u64, prev_clk);
>> +	struct rq *rq = this_rq();
> 
> this_rq() is this_cpu_ptr(). Shouldn't this be below preempt_disable() if
> this function is allowed to be called from sleepable ops?

Thanks for pointing that out. You are right. I will change it in
the next version.

> 
>> +	u64 pr_clk, cr_clk;
>> +
>> +	preempt_disable();
>> +	pr_clk = __this_cpu_read(prev_clk);
> 
> Would it make sense to make the above rq->scx.prev_clk?

That will also work. I will change it as suggested in the next
version.

> 
>> +	/*
>> +	 * If the rq clock is invalid, start a new rq clock period
>> +	 * with a fresh sched_clock().
>> +	 */
>> +	if (!(rq->scx.flags & SCX_RQ_CLK_VALID)) {
>> +		cr_clk = sched_clock();
>> +		scx_rq_clock_update(rq, cr_clk);
>> +	}
>> +	/*
>> +	 * If the rq clock is valid, use the cached rq clock
>> +	 * whenever the clock does not go backward.
>> +	 */
> 
> Can you move the comments inside the if/else bodies so that "} else {" can
> stay on the same line?

Sure.

> 
>> +	else {
>> +		cr_clk = rq->scx.clock;
>> +		/*
>> +		 * If the clock goes backward, start a new rq clock period
>> +		 * with a fresh sched_clock().
>> +		 */
> 
> Can you please add comment explaining how this can happen?

Sure, I will add the explanation in the next version.


Thanks!
Changwoo Min

Re: [PATCH v3 5/5] sched_ext: Replace bpf_ktime_get_ns() to scx_bpf_clock_get_ns()

[Changwoo Min]

Hello,

On 24. 12. 4. 08:40, Tejun Heo wrote:
> On Tue, Dec 03, 2024 at 11:28:02PM +0900, Changwoo Min wrote:
>> @@ -245,7 +245,7 @@ void BPF_STRUCT_OPS(central_running, struct task_struct *p)
>>   	s32 cpu = scx_bpf_task_cpu(p);
>>   	u64 *started_at = ARRAY_ELEM_PTR(cpu_started_at, cpu, nr_cpu_ids);
>>   	if (started_at)
>> -		*started_at = bpf_ktime_get_ns() ?: 1;	/* 0 indicates idle */
>> +		*started_at = scx_bpf_clock_get_ns() ?: 1;	/* 0 indicates idle */
> 
> Not from this commit, but how about scx_bpf_now_ns() for the name?
> 
> Thanks.
> 

That sounds good. I will change the function name in the next version.

Regards,
Changwoo Min

Re: [PATCH v3 2/5] sched_ext: Manage the validity of scx_rq_clock

[Tejun Heo]

Hello,

On Wed, Dec 04, 2024 at 10:42:13AM +0900, Changwoo Min wrote:
> I investigated all sched_ext_ops. Besides these two ops, all the
> rest are control operations, of which BPF operation should be
> relatively simple. On the other hand, ops.running() and
> ops.update_idle() are different from the others since a CPU
> executes a task or becomes idle, which could be arbitrarily long.
> So I think refreshing the clock in those cases would be nice.
> Does it make sense to you?

Hmm... I'm not really following. Both ops.running() and ops.update_idle()
are called during task switches with rq lock held. I don't see why they'd be
any different in terms of expected runtime, which should be pretty short,
compared to any other rq-locked operations.

Thanks.

-- 
tejun

Re: [PATCH v3 2/5] sched_ext: Manage the validity of scx_rq_clock

[Changwoo Min]

Hello,

On 24. 12. 5. 03:46, Tejun Heo wrote:
> Hello,
> 
> On Wed, Dec 04, 2024 at 10:42:13AM +0900, Changwoo Min wrote:
>> I investigated all sched_ext_ops. Besides these two ops, all the
>> rest are control operations, of which BPF operation should be
>> relatively simple. On the other hand, ops.running() and
>> ops.update_idle() are different from the others since a CPU
>> executes a task or becomes idle, which could be arbitrarily long.
>> So I think refreshing the clock in those cases would be nice.
>> Does it make sense to you?
> 
> Hmm... I'm not really following. Both ops.running() and ops.update_idle()
> are called during task switches with rq lock held. I don't see why they'd be
> any different in terms of expected runtime, which should be pretty short,
> compared to any other rq-locked operations.


Originally, what I wanted to say is the rq clock *after*
ops.running() and ops.update_idle() should be invalidated since
task running and idling could be arbitrarily long.

However, after double-checking the scheduler core again, I found
that such invalidations are redundant because anyway rq lock will
be released right after ops.running() and ops.update_idle().

I will remove two redundant invalidation in the next version.

Regards,
Changwoo Min