[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 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] Unsigned division on a wrapped negative time delta causes massive artificial inflation of virtual time for expired cgroups.
- [Medium] Race condition in cvtime_delta extraction using __sync_fetch_and_sub(ptr, *ptr) causes double accounting.
--

commit 069998f7546e450b1de3ae56c137b9e1dd16b919
Author: Tao Cui <cuitao@kylinos.cn>

sched_ext/scx_flatcg: make cgv_node_less() wraparound-safe

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.

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..acc1995630e6d 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);
>  }

While reviewing this file, I noticed a couple of pre-existing issues:

tools/sched_ext/scx_flatcg.bpf.c:cgrp_cap_budget() {
    ...
	delta = __sync_fetch_and_sub(&cgc->cvtime_delta, cgc->cvtime_delta);
	cvtime = cgv_node->cvtime + delta;
    ...
}

[Severity: Medium]
This isn't a bug introduced by this patch, but does this create a race condition
that leads to double accounting?

Because __sync_fetch_and_sub(ptr, *ptr) evaluates the second argument before
the atomic subtraction, a concurrent __sync_fetch_and_add() from another CPU
between the memory read of cgc->cvtime_delta and the atomic subtraction
will cause the added delta to be subtracted but still partially left in the
counter. The atomic operation returns the new value, charging the cgroup for
the increment, but leaves the increment in the counter to be charged again on
the next extraction.

If CPU A executes fcg_stopping() or fcg_dispatch() and calls
__sync_fetch_and_add(&cgc->cvtime_delta, val), and concurrently CPU B
executes cgrp_cap_budget() and evaluates
__sync_fetch_and_sub(&cgc->cvtime_delta, cgc->cvtime_delta), a race in the
tiny window between B's argument evaluation and the atomic subtraction could
trigger double charging.

Could this be replaced with an atomic exchange (e.g.,
__sync_lock_test_and_set()) to safely extract and clear the counter?


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

[Severity: High]
This isn't a bug introduced by this patch, but does this calculation suffer from
unsigned division on a wrapped negative time delta?

When a cgroup's slice has expired, the current time 'now' can easily be greater
than 'cpuc->cur_at + cgrp_slice_ns' due to interrupt latency or normal
scheduling jitter. The '(cpuc->cur_at + cgrp_slice_ns - now)' is computed using
unsigned u64 arithmetic, resulting in a wrapped large positive number. Since
all operands are unsigned and hweight is a u32, the subsequent multiplication
and division execute as unsigned arithmetic.

The resulting huge positive quotient is then added to cgc->cvtime_delta,
artificially inflating the virtual time by a massive amount and potentially
starving all tasks within the cgroup.

Should there be an explicit cast to a signed type (like s64) before division
to prevent this?

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

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