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

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

[Tao Cui]

From: Tao Cui <cuitao@kylinos.cn>

Patch 1 documents the rolling-cursor requirement for 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 v2:
- 1/2: "less than 2^63 apart" (not "within"), folded into the paragraph
  above
- 2/2: use time_before() instead of open-coded comparison, drop the
  comment, fix the wrap direction and timing, state both lag and lead
  bounds, Fixes corrected to upstream a4103eacc2ab (Tejun)

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
- 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           | 4 +++-
 tools/sched_ext/scx_flatcg.bpf.c | 2 +-
 2 files changed, 4 insertions(+), 2 deletions(-)

-- 
2.43.0

[PATCH v3 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 less than 2^63
apart. This is implicit in how a vtime scheduler works 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 | 4 +++-
 1 file changed, 3 insertions(+), 1 deletion(-)

diff --git a/kernel/sched/ext/ext.c b/kernel/sched/ext/ext.c
index 8041c87a3562..81a506a4c8ab 100644
--- a/kernel/sched/ext/ext.c
+++ b/kernel/sched/ext/ext.c
@@ -8903,7 +8903,9 @@ struct scx_bpf_dsq_insert_vtime_args {
  *
  * @args->vtime ordering is according to time_before64() which considers
  * wrapping. A numerically larger vtime may indicate an earlier position in the
- * ordering and vice-versa.
+ * ordering and vice-versa. vtime is a rolling cursor and values used for
+ * ordering within a given DSQ should stay less than 2^63 apart for
+ * time_before64() ordering to remain 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
-- 
2.43.0

[PATCH v3 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 misorders once
cvtime wraps: the wrapped node lands at the front of the tree while
the unwrapped ones get stuck behind it. Each CPU picking a cgroup
charges it a full slice, making wrap occur earlier than a naive
estimate might suggest.

Use time_before() instead. cgrp_cap_budget() bounds the lag behind
cvtime_now, while the lead is bounded by the slice charge plus pending
cvtime_delta on re-insertion, so the cyclic ordering assumptions of
time_before() hold.

Fixes: a4103eacc2ab ("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 | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/tools/sched_ext/scx_flatcg.bpf.c b/tools/sched_ext/scx_flatcg.bpf.c
index 454ebb820c5e..5e6abd0bccb3 100644
--- a/tools/sched_ext/scx_flatcg.bpf.c
+++ b/tools/sched_ext/scx_flatcg.bpf.c
@@ -144,7 +144,7 @@ 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;
+	return time_before(cgc_a->cvtime, cgc_b->cvtime);
 }
 
 static struct fcg_cpu_ctx *find_cpu_ctx(void)
-- 
2.43.0

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

[Tejun Heo]

On Wed, Sep 02, 2026 at 10:48:10AM +0800, Tao Cui wrote:
> Tao Cui (2):
>   sched_ext: document the rolling-cursor requirement for dsq_vtime
>   sched_ext/scx_flatcg: make cgv_node_less() wraparound-safe

Applied 1-2 to sched_ext/for-7.4 with the subjects capitalized.

Thanks.

--
tejun