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

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

[Changwoo Min]

Many BPF schedulers (such as scx_lavd, scx_rusty, scx_bpfland)
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 enough, scx_bpf_clock_get_ns() provides the rq clock, which is
already updated by the scheduler core (update_rq_clock), so it can reduce
the reading TSC calls.

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.

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                     | 22 ++++++-
 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, 109 insertions(+), 5 deletions(-)

-- 
2.47.0

[PATCH 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. 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 | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)

diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 4d79804631e4..61efff790e24 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_UPDATED	= 1 << 5, /* RQ clock is updated by the core */
 
 	SCX_RQ_IN_WAKEUP	= 1 << 16,
 	SCX_RQ_IN_BALANCE	= 1 << 17,
@@ -765,6 +766,7 @@ struct scx_rq {
 	struct list_head	ddsp_deferred_locals;	/* deferred ddsps from enq */
 	unsigned long		ops_qseq;
 	u64			extra_enq_flags;	/* see move_task_to_local_dsq() */
+	u64			clock;			/* cached per-rq clock -- see scx_bpf_clock_get_ns() */
 	u32			nr_running;
 	u32			flags;
 	u32			cpuperf_target;		/* [0, SCHED_CAPACITY_SCALE] */
@@ -1345,6 +1347,24 @@ DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);
 #define cpu_curr(cpu)		(cpu_rq(cpu)->curr)
 #define raw_rq()		raw_cpu_ptr(&runqueues)
 
+#ifdef CONFIG_SCHED_CLASS_EXT
+static inline void scx_rq_clock_update(struct rq *rq, u64 clock)
+{
+	rq->scx.clock = clock;
+	rq->scx.flags |= SCX_RQ_CLK_UPDATED;
+}
+
+static inline void scx_rq_clock_stale(struct rq *rq)
+{
+	rq->scx.flags &= ~SCX_RQ_CLK_UPDATED;
+}
+
+#else
+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 */
+
 #ifdef CONFIG_SCHED_CORE
 static inline struct cpumask *sched_group_span(struct sched_group *sg);
 
-- 
2.47.0

[PATCH 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.

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 a910a5b4c274..d0eb58b6a2da 100644
--- a/kernel/sched/core.c
+++ b/kernel/sched/core.c
@@ -784,6 +784,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);
 
@@ -795,11 +796,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 9f9bc2930658..b8ad776ef516 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 61efff790e24..03854ac9914b 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -1758,7 +1758,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.0

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

[Peter Zijlstra]

On Sun, Nov 17, 2024 at 01:01:23AM +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.
> 
> 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 a910a5b4c274..d0eb58b6a2da 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -784,6 +784,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);
>  
> @@ -795,11 +796,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);

It is not at all clear why you think you need to keep a second copy of
that value. You like cache misses?

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

[Changwoo Min]

Hello,

On 24. 11. 17. 04:32, Peter Zijlstra wrote:
> It is not at all clear why you think you need to keep a second copy of
> that value. You like cache misses?

Of course not. :-) I always try to avoid cache misses whenever
possible.

The main reason to keep the second copy (rq->scx.clock) is that
a BPF scheduler can call scx_bpf_clock_get_ns() at almost any
time in any context, including any of sched_ext operations, BPF
timer callbacks, BPF syscalls, kprobes, and so on.

However, the rq->clock is supposed to be updated while holding
the rq lock (lockdep_assert_rq_held), which is not always the
case in a BPF scheduler. Also, rq->clock is also used in other
places (e.g., PELT), so updating rq->clock in arbitrary points by
a BPF scheduler will create unnecessary dependencies.

Another approach would be to extend struct sched_clock_data (in
kernel/sched/clock.c) to store the update flag
(SCX_RQ_CLK_UPDATED). This would be the best regarding the number
of cache line accesses. However, that would be an overkill since
now sched_clock_data stores the sched_ext-specific data.
I thought it would be better to keep sched_ext specific data in
one place, struct scx_rq, for managibility.

Regards,
Changwoo Min

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

[Peter Zijlstra]

On Mon, Nov 18, 2024 at 12:46:32AM +0900, Changwoo Min wrote:

> The main reason to keep the second copy (rq->scx.clock) is that
> a BPF scheduler can call scx_bpf_clock_get_ns() at almost any
> time in any context, including any of sched_ext operations, BPF
> timer callbacks, BPF syscalls, kprobes, and so on.

If it's going to be a BPF wide thing, why is it presented as part of
sched_ext ? That makes no sense.

> Another approach would be to extend struct sched_clock_data (in
> kernel/sched/clock.c) to store the update flag
> (SCX_RQ_CLK_UPDATED). This would be the best regarding the number
> of cache line accesses. However, that would be an overkill since
> now sched_clock_data stores the sched_ext-specific data.
> I thought it would be better to keep sched_ext specific data in
> one place, struct scx_rq, for managibility.

What's the purpose of that flag? Why can't BPF use sched_clock_local()
and call it a day?

Do note that kernel/sched/clock.c is very much x86 specific (it was
briefly used by ia64 since their 'TSC' was of equal quality).

Growing sched_clock_data shouldn't be a problem, it's only 24 bytes, so
we have plenty free bytes there.

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

[Changwoo Min]

Hello,

Thank you for the prompt feedback. I hope the following answers
can clarify most of your doubts.

On 24. 11. 18. 18:41, Peter Zijlstra wrote:
> On Mon, Nov 18, 2024 at 12:46:32AM +0900, Changwoo Min wrote:
> 
>> The main reason to keep the second copy (rq->scx.clock) is that
>> a BPF scheduler can call scx_bpf_clock_get_ns() at almost any
>> time in any context, including any of sched_ext operations, BPF
>> timer callbacks, BPF syscalls, kprobes, and so on.
> 
> If it's going to be a BPF wide thing, why is it presented as part of
> sched_ext ? That makes no sense.

There is a confusion here. scx_bpf_clock_get_ns() is for BPF
schedulers, not for random BPF programs. In almost all cases, it
will be used in the shced_ext operations, such as ops.running()
and ops.stopping(), to implement scheduling policies. However, if
BPF schedulers use other BPF features, such as BPF timer,
scx_bpf_clock_get_ns() also can be used. For example, scx_lavd uses
a BPF timer for periodic background processing; scx_lavd and
scx_flash use kprobe to trace futex system calls. Also, since
scx_bpf_clock_get_ns() relies on rq lock, it is not meaningful
outside of the BPF schedulers. Hence, it should be a part of
sched_ext.

>> Another approach would be to extend struct sched_clock_data (in
>> kernel/sched/clock.c) to store the update flag
>> (SCX_RQ_CLK_UPDATED). This would be the best regarding the number
>> of cache line accesses. However, that would be an overkill since
>> now sched_clock_data stores the sched_ext-specific data.
>> I thought it would be better to keep sched_ext specific data in
>> one place, struct scx_rq, for managibility.
> 
> What's the purpose of that flag? Why can't BPF use sched_clock_local()
> and call it a day?

Let's suppose the following timeline:

   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_UPDATED is set), so scx_bpf_clock_get_ns calls during
[T2, T4) (including T3) will return the rq clock updated at T2.
Let's think about what we should do for the duration [T4, T7)
when a BPF scheduler can still call scx_bpf_clock_get_ns (T5).
During that duration, we consider the rq clock is invalid
(SCX_RQ_CLK_UPDATED is unset). So when calling
scx_bpf_clock_get_ns at T5, we call sched_clock() to get the
fresh clock.

I think the term `UPDATED` was misleading. I will change it to
`VALID` in the next version.

> Growing sched_clock_data shouldn't be a problem, it's only 24 bytes, so
> we have plenty free bytes there.

Alright. I will change the current implementation and extend
`struct sched_clock_data` to store the `VALID` flag in the next
version.

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

[Peter Zijlstra]

On Tue, Nov 19, 2024 at 10:19:44AM +0900, Changwoo Min wrote:

> > What's the purpose of that flag? Why can't BPF use sched_clock_local()
> > and call it a day?
> 
> Let's suppose the following timeline:
> 
>   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_UPDATED is set), so scx_bpf_clock_get_ns calls during
> [T2, T4) (including T3) will return the rq clock updated at T2.
> Let's think about what we should do for the duration [T4, T7)
> when a BPF scheduler can still call scx_bpf_clock_get_ns (T5).
> During that duration, we consider the rq clock is invalid
> (SCX_RQ_CLK_UPDATED is unset). So when calling
> scx_bpf_clock_get_ns at T5, we call sched_clock() to get the
> fresh clock.
> 
> I think the term `UPDATED` was misleading. I will change it to
> `VALID` in the next version.

So the reason rq->clock is tied to rq->lock, is to ensure a scheduling
operation happens at a single point in time.

Suppose re-nice, you dequeue the task, you modify its properties
(weight) and then you requeue it. If time were passing 'normally' the
task would loose the time between dequeue and enqueue -- this is not
right.

The only obvious exception here is a migration.

So the question then becomes, what is T5 doing and is it 'right' for it
to get a fresh clock value.

Please give an example of T5 -- I really don't know this BPF crap much
-- and reason about how the clock should behave.

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

[Changwoo Min]

Hello,

On 24. 11. 19. 17:17, Peter Zijlstra wrote:
> On Tue, Nov 19, 2024 at 10:19:44AM +0900, Changwoo Min wrote:

>> Let's suppose the following timeline:
>>
>>    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_UPDATED is set), so scx_bpf_clock_get_ns calls during
>> [T2, T4) (including T3) will return the rq clock updated at T2.
>> Let's think about what we should do for the duration [T4, T7)
>> when a BPF scheduler can still call scx_bpf_clock_get_ns (T5).
>> During that duration, we consider the rq clock is invalid
>> (SCX_RQ_CLK_UPDATED is unset). So when calling
>> scx_bpf_clock_get_ns at T5, we call sched_clock() to get the
>> fresh clock.

> So the question then becomes, what is T5 doing and is it 'right' for it
> to get a fresh clock value.
> 
> Please give an example of T5 -- I really don't know this BPF crap much
> -- and reason about how the clock should behave.

Here is one example. `scx_central` 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, it is reasonable to return a fresh clock
value rather than returning the old one (T2).

Besides this timer example, scx_bpf_clock_get_ns() can be called
any callbacks defined in `struct sched_ext_ops`. Some callbacks
can be called without holding a rq lock (e.g., ops.cpu_online,
ops.cgroup_init). In these cases, it is reasonable to reutrn a
fresh clock value rather returning the old one.

Regards,
Changwoo Min

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

[Changwoo Min]

Hello,

On 24. 11. 20. 00:57, Changwoo Min wrote:
> Hello,
> 
> On 24. 11. 19. 17:17, Peter Zijlstra wrote:
>> On Tue, Nov 19, 2024 at 10:19:44AM +0900, Changwoo Min wrote:
> 
>>> Let's suppose the following timeline:
>>>
>>>    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_UPDATED is set), so scx_bpf_clock_get_ns calls during
>>> [T2, T4) (including T3) will return the rq clock updated at T2.
>>> Let's think about what we should do for the duration [T4, T7)
>>> when a BPF scheduler can still call scx_bpf_clock_get_ns (T5).
>>> During that duration, we consider the rq clock is invalid
>>> (SCX_RQ_CLK_UPDATED is unset). So when calling
>>> scx_bpf_clock_get_ns at T5, we call sched_clock() to get the
>>> fresh clock.
> 
>> So the question then becomes, what is T5 doing and is it 'right' for it
>> to get a fresh clock value.
>>
>> Please give an example of T5 -- I really don't know this BPF crap much
>> -- and reason about how the clock should behave.
> 
> Here is one example. `scx_central` 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, it is reasonable to return a fresh clock
> value rather than returning the old one (T2).
> 
> Besides this timer example, scx_bpf_clock_get_ns() can be called
> any callbacks defined in `struct sched_ext_ops`. Some callbacks
> can be called without holding a rq lock (e.g., ops.cpu_online,
> ops.cgroup_init). In these cases, it is reasonable to reutrn a
> fresh clock value rather returning the old one.

I wonder if the above example is sufficient for you. If you need
more examples or clarification, please let me know.


Regarding the my following my comment in the previous email, ...

On 24. 11. 19. 10:19, Changwoo Min wrote:
>> Growing sched_clock_data shouldn't be a problem, it's only 24 bytes,
>> so we have plenty free bytes there.
> 
> Alright. I will change the current implementation and extend
> `struct sched_clock_data` to store the `VALID` flag in the next
> version.


I found `struct sched_clock_data` is defined only when
CONFIG_HAVE_UNSTABLE_SCHED_CLOCK is set, so I think extending
`struct sched_clock_data` is not an approach approach. Extending
`struct scx_rq` seems the best option after opting out
sched_clock_data. I will make sure the cached clock value and
flag in the scx_rq are in the same cache line to minimize the
cache misses. What do you think?

Thanks!
Changwoo Min

[PATCH 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 the 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 b8ad776ef516..b0374274ead2 100644
--- a/kernel/sched/ext.c
+++ b/kernel/sched/ext.c
@@ -7541,6 +7541,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_UPDATED)) {
+		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)
@@ -7572,6 +7642,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.0

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

[Peter Zijlstra]

On Sun, Nov 17, 2024 at 01:01:24AM +0900, Changwoo Min wrote:
> 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 the 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.

Have you seen the insides of kernel/sched/clock.c ?

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

[Changwoo Min]

Hello,

On 24. 11. 17. 04:31, Peter Zijlstra wrote:
> Have you seen the insides of kernel/sched/clock.c ?

Of course. :-) It would be super helpful if you could let me know
specific questions or comments.

I didn't extend (or piggyback) on the clock.c because, as
I explained in the other email, I think it is overkill, creating
dependencies between clock.c and the sched_ext code.

Regards,
Changwoo Min

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

[Peter Zijlstra]

On Mon, Nov 18, 2024 at 12:48:35AM +0900, Changwoo Min wrote:
> Hello,
> 
> On 24. 11. 17. 04:31, Peter Zijlstra wrote:
> > Have you seen the insides of kernel/sched/clock.c ?
> 
> Of course. :-) It would be super helpful if you could let me know
> specific questions or comments.

Well, mostly I don't understand anything about what you're doing.
Perhaps if you explain what's wrong with the bits we have ?

If you're looking at the scheduler, then rq->clock really should be
sufficient.

If you're looking at rando BPF crud, then what's wrong with
local_clock()?

Also, why are we still caring about systems that have crazy TSC?

[PATCH 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.0

[PATCH 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..3be99f3c32fd 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_op_clock_get_ns();
 	bool picked_next = false;
 
 	cpuc = find_cpu_ctx();
-- 
2.47.0