[PATCH v2 0/2] sched_ext: document and enforce vtime ordering constraints

[PATCH v2 0/2] sched_ext: document and enforce vtime ordering constraints

[Tao Cui]

From: Tao Cui <cuitao@kylinos.cn>

Patch 1 documents the rolling-cursor and half-range requirement for
dsq_vtime ordering in scx_bpf_dsq_insert_vtime(). Patch 2 fixes
scx_flatcg's comparator to use the cyclic comparison, which is
correct there because cgrp_cap_budget() upholds that requirement.

Changes since v1:
- drop 1/2 (kernel priq comparator change): the cyclic ordering is
  the documented contract; a plain comparison causes unbounded
  starvation at the natural wrap (Andrea, Tejun)
- new 1/2: document the rolling-cursor requirement instead (Tejun)
- 2/2 (flatcg) unchanged

Tao Cui (2):
  sched_ext: document the rolling-cursor requirement for dsq_vtime
  sched_ext/scx_flatcg: make cgv_node_less() wraparound-safe

 kernel/sched/ext/ext.c           | 5 +++++
 tools/sched_ext/scx_flatcg.bpf.c | 3 ++-
 2 files changed, 7 insertions(+), 1 deletion(-)

-- 
2.43.0

[PATCH v2 1/2] sched_ext: document the rolling-cursor requirement for dsq_vtime

[Tao Cui]

From: Tao Cui <cuitao@kylinos.cn>

scx_bpf_dsq_insert_vtime() orders tasks by time_before64(), which is
only meaningful when the values within a given DSQ stay within a
half-range (2^63) of each other. This is implicit in how a vtime
scheduler works -- the cursor advances monotonically -- but not
spelled out anywhere. Document it so BPF scheduler authors know the
constraint.

Signed-off-by: Tao Cui <cuitao@kylinos.cn>
---
 kernel/sched/ext/ext.c | 5 +++++
 1 file changed, 5 insertions(+)

diff --git a/kernel/sched/ext/ext.c b/kernel/sched/ext/ext.c
index 8041c87a3562..9030962f4df1 100644
--- a/kernel/sched/ext/ext.c
+++ b/kernel/sched/ext/ext.c
@@ -8905,6 +8905,11 @@ struct scx_bpf_dsq_insert_vtime_args {
  * wrapping. A numerically larger vtime may indicate an earlier position in the
  * ordering and vice-versa.
  *
+ * vtime is a rolling cursor and should be treated as a virtual timestamp
+ * that advances monotonically. Values used for ordering within a given DSQ
+ * should stay within half the u64 range (2^63) of each other so that
+ * time_before64() ordering remains well-defined.
+ *
  * A DSQ can only be used as a FIFO or priority queue at any given time and this
  * function must not be called on a DSQ which already has one or more FIFO tasks
  * queued and vice-versa. Also, the built-in DSQs (SCX_DSQ_LOCAL and
-- 
2.43.0

[PATCH v2 2/2] sched_ext/scx_flatcg: make cgv_node_less() wraparound-safe

[Tao Cui]

From: Tao Cui <cuitao@kylinos.cn>

cgv_node_less() compares cvtimes with a plain <, which breaks once
cvtime wraps. A weight-1 cgroup in a hierarchy summing to 10000
advances cvtime at up to 10000x wall time, so 2^64 ns of cvtime is
weeks of continuous saturation away -- unlikely but reachable on a
long-running host. At the wrap instant the plain comparison puts the
wrapped node behind everything else permanently.

Compare with (s64)(a - b) < 0 instead, as CFS does for vruntime. A
cyclic comparison is valid as an rbtree comparator only because
cgrp_cap_budget() clamps every node to within max_budget behind
cvtime_now, so any two nodes are far less than 2^63 apart and the
cyclic order agrees with the true order.

Compile-tested and smoke-tested in a VM: weight distribution and
dispatch unaffected.

Fixes: 7b742aa2c2c9 ("sched_ext: Add a cgroup scheduler which uses flattened hierarchy")
Reported-by: Sashiko <sashiko-bot@kernel.org>
Link: https://lore.kernel.org/r/3f1ce004-e259-4e72-a5f7-14a5050053bd@linux.dev
Signed-off-by: Tao Cui <cuitao@kylinos.cn>
---
 tools/sched_ext/scx_flatcg.bpf.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/tools/sched_ext/scx_flatcg.bpf.c b/tools/sched_ext/scx_flatcg.bpf.c
index 454ebb820c5e..be03b409db5e 100644
--- a/tools/sched_ext/scx_flatcg.bpf.c
+++ b/tools/sched_ext/scx_flatcg.bpf.c
@@ -144,7 +144,8 @@ static bool cgv_node_less(struct bpf_rb_node *a, const struct bpf_rb_node *b)
 	cgc_a = container_of(a, struct cgv_node, rb_node);
 	cgc_b = container_of(b, struct cgv_node, rb_node);
 
-	return cgc_a->cvtime < cgc_b->cvtime;
+	/* wrap-safe: cap_budget keeps nodes within 2^63 of each other */
+	return (s64)(cgc_a->cvtime - cgc_b->cvtime) < 0;
 }
 
 static struct fcg_cpu_ctx *find_cpu_ctx(void)
-- 
2.43.0

Re: [PATCH v2 2/2] sched_ext/scx_flatcg: make cgv_node_less() wraparound-safe

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:

Pre-existing issues:
- [High] Atomic read-modify-write race in cgrp_cap_budget duplicates cvtime_delta charges.
- [High] Yielding early penalizes a cgroup's cvtime instead of refunding it, and overrunning causes massive unintended penalties due to unsigned underflow.
--

commit 3be5a2d907efdab246afa9bb4e4577fd489ec842
Author: Tao Cui <cuitao@kylinos.cn>

sched_ext/scx_flatcg: make cgv_node_less() wraparound-safe

The commit addresses a potential wraparound issue in cgv_node_less() by
using a signed difference for cvtime comparison instead of a plain '<'.

Link: https://lore.kernel.org/r/3f1ce004-e259-4e72-a5f7-14a5050053bd@linux.dev

> diff --git a/tools/sched_ext/scx_flatcg.bpf.c b/tools/sched_ext/scx_flatcg.bpf.c
> index fec3595818269..3a25cfdc97092 100644
> --- a/tools/sched_ext/scx_flatcg.bpf.c
> +++ b/tools/sched_ext/scx_flatcg.bpf.c
> @@ -144,7 +144,8 @@ static bool cgv_node_less(struct bpf_rb_node *a, const struct bpf_rb_node *b)
>  	cgc_a = container_of(a, struct cgv_node, rb_node);
>  	cgc_b = container_of(b, struct cgv_node, rb_node);
>  
> -	return cgc_a->cvtime < cgc_b->cvtime;
> +	/* wrap-safe: cap_budget keeps nodes within 2^63 of each other */
> +	return (s64)(cgc_a->cvtime - cgc_b->cvtime) < 0;
>  }
>  
>  static struct fcg_cpu_ctx *find_cpu_ctx(void)

While reviewing this patch, I noticed a couple of preexisting issues in
tools/sched_ext/scx_flatcg.bpf.c.

tools/sched_ext/scx_flatcg.bpf.c:cgrp_cap_budget()
> 	/*
> 	 * A node which is on the rbtree can't be pointed to from elsewhere yet
> 	 * and thus can't be updated and repositioned. Instead, we collect the
> 	 * vtime deltas separately and apply it asynchronously here.
> 	 */
> 	delta = __sync_fetch_and_sub(&cgc->cvtime_delta, cgc->cvtime_delta);

[Severity: High]
This is a pre-existing issue, but could this atomic subtraction lead to a race
condition with concurrent updates?

In C, the second argument (cgc->cvtime_delta) is evaluated before the atomic
operation. If another CPU adds to cvtime_delta (e.g. via lockless
__sync_fetch_and_add in fcg_stopping) after the second argument is evaluated
but before the atomic subtraction executes, the operation will subtract the
old value from the new value.

This returns the new value, which gets added to cvtime, but the concurrent
addition remains in cvtime_delta and will be added again in the next call.
Would it be safer to use an atomic exchange here, such as
__sync_lock_test_and_set or bpf_atomic_xchg?


tools/sched_ext/scx_flatcg.bpf.c:fcg_dispatch()
> 		__sync_fetch_and_add(&cgc->cvtime_delta,
> 				     (cpuc->cur_at + cgrp_slice_ns - now) *
> 				     FCG_HWEIGHT_ONE / (cgc->hweight ?: 1));

[Severity: High]
This isn't a bug introduced by this patch, but does this logic penalize
cgroups when they yield early?

If a cgroup yields before its slice is fully consumed, cpuc->cur_at +
cgrp_slice_ns - now is positive. Adding this unused time to cvtime_delta
increases cvtime, pushing the deadline further into the future instead of
refunding it.

Additionally, if the cgroup overruns its slice, could the subtraction
underflow? Since the arithmetic is unsigned, an overrun would result in a
huge number which, after division by cgc->hweight, produces a massive
positive value. This would heavily penalize the cgroup by adding days of
virtual time to its cvtime_delta.

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20260901140343.764080-1-cui.tao@linux.dev?part=2

Re: [PATCH v2 1/2] sched_ext: document the rolling-cursor requirement for dsq_vtime

[Tejun Heo]

Hello,

On Tue, Sep 01, 2026 at 10:03:42PM +0800, Tao Cui wrote:
...
> + * should stay within half the u64 range (2^63) of each other so that
> + * time_before64() ordering remains well-defined.

Two values exactly 2^63 apart are before each other in both directions, so
"less than 2^63 apart". Also, please fold this into the paragraph above.

Thanks.

--
tejun

Re: [PATCH v2 2/2] sched_ext/scx_flatcg: make cgv_node_less() wraparound-safe

[Tejun Heo]

Hello,

On Tue, Sep 01, 2026 at 10:03:43PM +0800, Tao Cui wrote:
...
> long-running host. At the wrap instant the plain comparison puts the
> wrapped node behind everything else permanently.

Plain < puts the wrapped node at the front. The unwrapped ones get stuck
behind it. Also, each CPU picking a cgroup charges it a full slice, so the
wrap is closer than weeks.

...
> cyclic comparison is valid as an rbtree comparator only because
> cgrp_cap_budget() clamps every node to within max_budget behind
> cvtime_now, so any two nodes are far less than 2^63 apart and the
...

cgrp_cap_budget() only bounds the lag. The lead is bounded by the slice
charge plus pending cvtime_delta on re-insertion.

> Fixes: 7b742aa2c2c9 ("sched_ext: Add a cgroup scheduler which uses flattened hierarchy")

Not in mainline. The upstream commit is a4103eacc2ab.

> +	/* wrap-safe: cap_budget keeps nodes within 2^63 of each other */
> +	return (s64)(cgc_a->cvtime - cgc_b->cvtime) < 0;

Use time_before() and drop the comment.

Thanks.

--
tejun

Re: [PATCH v2 2/2] sched_ext/scx_flatcg: make cgv_node_less() wraparound-safe

[Tao Cui]

Hello, Tejun.

在 2026/9/2 04:00, Tejun Heo 写道:
> Hello,
> 
> On Tue, Sep 01, 2026 at 10:03:43PM +0800, Tao Cui wrote:
> ...
>> long-running host. At the wrap instant the plain comparison puts the
>> wrapped node behind everything else permanently.
> 
> Plain < puts the wrapped node at the front. The unwrapped ones get stuck
> behind it. Also, each CPU picking a cgroup charges it a full slice, so the
> wrap is closer than weeks.
> 
> ...
>> cyclic comparison is valid as an rbtree comparator only because
>> cgrp_cap_budget() clamps every node to within max_budget behind
>> cvtime_now, so any two nodes are far less than 2^63 apart and the
> ...
> 
> cgrp_cap_budget() only bounds the lag. The lead is bounded by the slice
> charge plus pending cvtime_delta on re-insertion.
> 
>> Fixes: 7b742aa2c2c9 ("sched_ext: Add a cgroup scheduler which uses flattened hierarchy")
> 
> Not in mainline. The upstream commit is a4103eacc2ab.
> 
>> +	/* wrap-safe: cap_budget keeps nodes within 2^63 of each other */
>> +	return (s64)(cgc_a->cvtime - cgc_b->cvtime) < 0;
> 
> Use time_before() and drop the comment.
> 

Thanks for both reviews, all points taken. Here's what changed:

1/2: "less than 2^63 apart", folded into the paragraph above.

2/2: wrapped node goes to the front (not behind), wrap timing
corrected (per-CPU slice charge), lag and lead bounds both stated,
Fixes points at a4103eacc2ab, comparator uses time_before(), and the
comment is dropped.

I'll send v3 shortly.

Thanks,
Tao

> Thanks.
> 
> --
> tejun