sched_ext: document and enforce vtime ordering constraints
Subsystems (3)
v2 cover sched_ext: document and enforce vtime ordering constraints
From: Tao Cui <[email protected]>
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(-)
Signature · 1 line
2.43.0
PATCH v2 1/2 sched_ext: document the rolling-cursor requirement for dsq_vtime
From: Tao Cui <[email protected]>
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.
--- kernel/sched/ext/ext.c | 5 +++++ 1 file changed, 5 insertions(+)
kernel/sched/ext/ext.c +5 -0
@@ -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
Signature · 1 line
2.43.0
Tejun Heo
reviewerRe: [PATCH v2 1/2] sched_ext: document the rolling-cursor requirement for dsq_vtime
Hello,
On Tue, Sep 01, 2026 at 10:03:42PM +0800, Tao Cui wrote:
...
Quoted 2 lines
+ * 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
In reply to Tao CuiFrom: Tao Cui <[email protected]>
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.
--- tools/sched_ext/scx_flatcg.bpf.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)
tools/sched_ext/scx_flatcg.bpf.c +2 -1
@@ -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 )
Signature · 1 line
2.43.0
[email protected]
AI reviewRe: [PATCH v2 2/2] sched_ext/scx_flatcg: make cgv_node_less() wraparound-safe
Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
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 <[email protected]>
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 '<'.
Quoted 5 lines
tools/sched_ext/scx_flatcg.bpf.c +0
-0
tools/sched_ext/scx_flatcg.bpf.c static bool cgv_node_less(struct bpf_rb_node *a, const struct bpf_rb_node *b) · line 151
Quoted 9 lines
tools/sched_ext/scx_flatcg.bpf.c +2
-1@@ -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()
Quoted 6 lines
/* * 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()
Quoted 3 lines
__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.
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=2
Tejun Heo
reviewerRe: [PATCH v2 2/2] sched_ext/scx_flatcg: make cgv_node_less() wraparound-safe
In reply to Tao CuiHello,
On Tue, Sep 01, 2026 at 10:03:43PM +0800, Tao Cui wrote:
...
Quoted 2 lines
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.
...
Quoted 3 lines
cyclic comparison is valid as an rbtree comparator only because
cgrp_cap_budget()clamps every node to withinmax_budgetbehindcvtime_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.
Quoted 1 line
Fixes 7b742aa2c2c9 ("sched_ext: Add a cgroup scheduler which uses flattened hierarchy")
Not in mainline. The upstream commit is a4103eacc2ab.
tools/sched_ext/scx_flatcg.bpf.c static bool cgv_node_less(struct bpf_rb_node *a, const struct bpf_rb_node *b) · line 148
Quoted 2 lines
tools/sched_ext/scx_flatcg.bpf.c +2
-0+/* 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
Hello, Tejun.
Quoted 20 lines · Tejun Heo
Hello,
On Tue, Sep 01, 2026 at 10:03:43PM +0800, Tao Cui wrote:
...Quoted 2 lines
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.
...
Quoted 3 lines
cyclic comparison is valid as an rbtree comparator only because
cgrp_cap_budget()clamps every node to withinmax_budgetbehindcvtime_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 pendingcvtime_deltaon re-insertion.
Quoted 9 lines
Quoted 1 line
Fixes 7b742aa2c2c9 ("sched_ext: Add a cgroup scheduler which uses flattened hierarchy")Not in mainline. The upstream commit is
a4103eacc2ab.tools/sched_ext/scx_flatcg.bpf.c static bool cgv_node_less(struct bpf_rb_node *a, const struct bpf_rb_node *b) · line 148
Quoted 2 lines
tools/sched_ext/scx_flatcg.bpf.c +2
-0+/* 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
Quoted 4 lines
Thanks.
--
tejun