[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

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

[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

[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