sched_ext: fix wraparound-unsafe vtime orderings
Subsystems (3)
cover sched_ext: fix wraparound-unsafe vtime orderings
From: Tao Cui <[email protected]>
Two spots order tasks by 64-bit virtual time with comparisons that break when the values are far apart: the kernel's vtime DSQ priority queue and scx_flatcg's cgroup tree. They need opposite fixes, which is the point of this series.
The kernel's scx_dsq_priq_less() compares with time_before64(), i.e. (s64)(a - b) < 0. That is only a valid ordering when all values in the queue are less than 2^63 apart. CFS upholds that invariant with min_vruntime clamping; sched_ext cannot, because dsq_vtime comes straight from the BPF scheduler. A scheduler that inserts vtimes wider than 2^63 apart into one DSQ gets the inverted order -- the tasks it placed last run first while the rest starve. Patch 1 switches to a plain u64 comparison, which is a total order and always honors the requested order; it reproduces the inversion with a probe scheduler and verifies the fix.
scx_flatcg's cgv_node_less() has the inverse problem: it compares with a plain <, which misorders once cvtime wraps. There the cyclic (s64)(a - b) < 0 comparison from patch 1's bug is the correct fix, because flatcg does uphold the spread invariant -- cgrp_cap_budget() clamps every node to within max_budget behind cvtime_now -- and the cyclic comparison also carries the ordering correctly across the natural 2^64 wrap, which a plain comparison would not.
So: same bug family, opposite fixes, each justified by whether the spread invariant exists. This is also why the naive "use time_before64 everywhere" suggestion doesn't hold -- without the invariant it is exactly the inversion patch 1 fixes.
Tao Cui (2):
sched_ext: fix vtime priority queue inversion on wide vtime spread sched_ext/scx_flatcg: make cgv_node_less() wraparound-safe
kernel/sched/ext/ext.c | 3 ++- tools/sched_ext/scx_flatcg.bpf.c | 3 ++- 2 files changed, 4 insertions(+), 2 deletions(-)
Signature · 1 line
2.43.0
PATCH 1/2 sched_ext: fix vtime priority queue inversion on wide vtime spread
From: Tao Cui <[email protected]>
scx_dsq_priq_less() compares dsq_vtime with time_before64(), a cyclic comparison that is only valid when the values in the queue are less than 2^63 apart. Unlike CFS, which enforces that invariant with min_vruntime clamping, sched_ext takes dsq_vtime directly from the BPF scheduler and cannot bound the spread. A scheduler that inserts tasks with vtimes wider than 2^63 apart into one DSQ gets the order inverted:
the tasks it placed last run first and the rest starve. Reproduced with a probe scheduler assigning half its tasks vtimes near 0 and the other half vtimes above 2^63 -- four of eight busy tasks monopolized the CPU while the other four starved.
Compare with plain u64 < instead, which is a total order and always honors the order the scheduler asked for. The transient misordering around the natural 2^64 wrap is the same class of anomaly the cyclic comparison trades it for, but bounded.
--- kernel/sched/ext/ext.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)
kernel/sched/ext/ext.c +2 -1
@@ -1417,7 +1417,8 @@ static bool scx_dsq_priq_less(struct rb_node *node_a,const struct task_struct *b = container_of(node_b, struct task_struct, scx.dsq_priq); -return time_before64 (a->scx.dsq_vtime, b->scx.dsq_vtime); +/* dsq_vtime is arbitrary BPF input: keep a total order */ +return a->scx.dsq_vtime < b->scx.dsq_vtime; }static void dsq_inc_nr (struct scx_dispatch_q *dsq,struct task_struct *p,u64 enq_flags)
Signature · 1 line
2.43.0
PATCH 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 2/2] sched_ext/scx_flatcg: make cgv_node_less() wraparound-safe
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
Pre-existing issues:
- [High] Incorrect usage of __sync_fetch_and_sub with a self-referencing argument leads to double-counting of concurrent time additions. --
commit aa8a669e2d8a03160f8c5bfda45d4fd749f2352c
Author: Tao Cui <[email protected]>
sched_ext/scx_flatcg: make cgv_node_less() wraparound-safe
cgv_node_less() compares cvtimes with a plain <, which breaks once cvtime wraps. 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.
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 )
[ ... ]
[Severity: High]
This is a pre-existing issue, but does using __sync_fetch_and_sub() with a self-referencing argument cause double-counting of concurrent time additions?
In tools/sched_ext/scx_flatcg.bpf.c:cgrp_cap_budget():
delta = __sync_fetch_and_sub(&cgc->cvtime_delta, cgc->cvtime_delta);
If fcg_stopping() concurrently updates cgc->cvtime_delta using __sync_fetch_and_add() without holding cgv_tree_lock, can this sequence occur?
CPU 1 executes cgrp_cap_budget() and reads the second argument (the amount to subtract), getting the current value (e.g., X).
CPU 2 executes fcg_stopping() and concurrently adds Y, making the memory value X + Y.
CPU 1 executes the atomic subtract of X from X + Y, returning the old memory value of X + Y, but leaving Y in memory.
CPU 1 then processes delta as X + Y, while Y remains in memory.
Could this result in the concurrent addition Y being processed immediately, and then remaining in memory to be processed again later, incorrectly calculating the CPU share for the cgroup?
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=2
[email protected]
AI reviewRe: [PATCH 1/2] sched_ext: fix vtime priority queue inversion on wide vtime spread
In reply to Tao CuiThank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [High] The patch silently breaks the established cyclic `vtime` ordering contract by switching to an…
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] The patch silently breaks the established cyclic vtime ordering contract by switching to an absolute < comparison, causing permanent task starvation upon wraparound and contradicting existing kfunc documentation and selftests. --
commit b0708e9275ee1ffad12d1e3811001b6d6ee4c741
Author: Tao Cui <[email protected]>
sched_ext: fix vtime priority queue inversion on wide vtime spread
This commit replaces the time_before64() cyclic comparison in scx_dsq_priq_less() with a plain less-than operation to prevent priority queue inversion when vtimes have a wide spread.
kernel/sched/ext/ext.c static bool scx_dsq_priq_less(struct rb_node *node_a, · line 1360
Quoted 11 lines
kernel/sched/ext/ext.c +2
-1@@ -1356,7 +1356,8 @@ static bool scx_dsq_priq_less(struct rb_node *node_a,const struct task_struct *b = container_of(node_b, struct task_struct, scx.dsq_priq); -return time_before64 (a->scx.dsq_vtime, b->scx.dsq_vtime); +/* dsq_vtime is arbitrary BPF input: keep a total order */ +return a->scx.dsq_vtime < b->scx.dsq_vtime;
[Severity: High]
Does this break the established cyclic vtime ordering contract and cause permanent task starvation upon wraparound?
If a BPF scheduler assigns vtime to tasks, and the vtime advances and eventually wraps around U64_MAX, tasks that are in the queue at the time of wraparound (with vtime near U64_MAX) will be indefinitely starved. This happens because new post-wrap tasks (with small absolute vtimes) will be strictly less than the old ones and placed ahead of them.
The user-facing kfunc documentation for __scx_bpf_dsq_insert_vtime() in kernel/sched/ext/ext.c still explicitly promises the cyclic wrapping behavior:
* @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.
Additionally, BPF schedulers still actively rely on the cyclic vtime semantics, as seen in tools/testing/selftests/sched_ext/select_cpu_vtime.bpf.c:
static inline bool vtime_before(u64 a, u64 b)
{
return (s64)(a - b) < 0;
}Quoted 1 line
kernel/sched/ext/ext.c +0
-0}
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
[email protected]
AI reviewRe: [PATCH 2/2] sched_ext/scx_flatcg: make cgv_node_less() wraparound-safe
In reply to Tao CuiIs the Fixes: tag correct? The tag references commit 7b742aa2c2c9, which does not exist in this repository. The bug was actually introduced by commit a4103eacc2ab4 ("sched_ext: Add a cgroup…
Quoted 13 lines
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 withinmax_budgetbehindcvtime_now, so any two nodes are far less than 2^63 apart and the cyclic order agrees with the true order.
Quoted 7 lines
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 <[email protected]>Signed-off-by Tao Cui <[email protected]>
Is the Fixes: tag correct? The tag references commit 7b742aa2c2c9, which does not exist in this repository. The bug was actually introduced by commit a4103eacc2ab4 ("sched_ext: Add a cgroup scheduler which uses flattened hierarchy"), which added the buggy plain comparison 'cgc_a->cvtime < cgc_b->cvtime' that this commit fixes. Should the tag be:
---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
CI run summary: https://github.com/kernel-patches/bpf/actions/runs/33465241568
Andrea Righi
reviewerRe: [PATCH 1/2] sched_ext: fix vtime priority queue inversion on wide vtime spread
In reply to Tao CuiHi Tao,
Quoted 13 lines · Tao Cui
From: Tao Cui <[email protected]>
scx_dsq_priq_less()comparesdsq_vtimewithtime_before64(), a cyclic comparison that is only valid when the values in the queue are less than 2^63 apart. Unlike CFS, which enforces that invariant withmin_vruntimeclamping,sched_exttakesdsq_vtimedirectly from the BPF scheduler and cannot bound the spread. A scheduler that inserts tasks with vtimes wider than 2^63 apart into one DSQ gets the order inverted:
the tasks it placed last run first and the rest starve. Reproduced with a probe scheduler assigning half its tasks vtimes near 0 and the other half vtimes above 2^63 -- four of eight busy tasks monopolized the CPU while the other four starved.
Quoted 4 lines
Compare with plain u64 < instead, which is a total order and always honors the order the scheduler asked for. The transient misordering around the natural 2^64 wrap is the same class of anomaly the cyclic comparison trades it for, but bounded.
I don't think switching to plain u64 ordering is safe here.
The current scx_bpf_dsq_insert_vtime() documentation explicitly defines the ordering in terms of time_before64(), including wraparound. For example:
a = U64_MAX - 5
b = 3
a is earlier than b in cyclic vtime ordering. time_before64(a, b) correctly returns true, while plain a < b would place b first.
Moreover, this is not a short transient. If post-wrap tasks continue to be reinserted with small vtimes, a can remain behind them until their vtime traverses almost the entire u64 range, resulting in effective starvation.
Can we preserve time_before64() and document or enforce the half-range requirement instead?
Thanks,
-Andrea
Quoted 24 lines
Fixes 06e51be3d5e7 ("sched_ext: Add vtime-ordered priority queue to dispatch_q's")Signed-off-by Tao Cui <[email protected]>--- kernel/sched/ext/ext.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)kernel/sched/ext/ext.c +2
-1@@ -1417,7 +1417,8 @@ static bool scx_dsq_priq_less(struct rb_node *node_a,const struct task_struct *b = container_of(node_b, struct task_struct, scx.dsq_priq); -return time_before64 (a->scx.dsq_vtime, b->scx.dsq_vtime); +/* dsq_vtime is arbitrary BPF input: keep a total order */ +return a->scx.dsq_vtime < b->scx.dsq_vtime; }static void dsq_inc_nr (struct scx_dispatch_q *dsq,struct task_struct *p,u64 enq_flags)Signature · 1 line
2.43.0
Tejun Heo
reviewerRe: [PATCH 1/2] sched_ext: fix vtime priority queue inversion on wide vtime spread
In reply to Tao CuiHello,
On Tue, Sep 01, 2026 at 10:40:37AM +0800, Tao Cui wrote:
...
Quoted 3 lines
than 2^63 apart. Unlike CFS, which enforces that invariant with
min_vruntimeclamping,sched_exttakesdsq_vtimedirectly from the BPF scheduler and cannot bound the spread. A scheduler that inserts tasks
This doesn't make any practical sense. dsq_vtime is by (implicit) definition a rolling cursor. Please feel free to add documentation if that'd help.
Thanks.
Signature · 1 line
tejun
Re: [PATCH 1/2] sched_ext: fix vtime priority queue inversion on wide vtime spread
In reply to Andrea RighiHello, Andrea, Tejun.
Quoted 32 lines · Andrea Righi
Hi Tao,
Quoted 13 lines · Tao Cui
From: Tao Cui <[email protected]>
scx_dsq_priq_less()comparesdsq_vtimewithtime_before64(), a cyclic comparison that is only valid when the values in the queue are less than 2^63 apart. Unlike CFS, which enforces that invariant withmin_vruntimeclamping,sched_exttakesdsq_vtimedirectly from the BPF scheduler and cannot bound the spread. A scheduler that inserts tasks with vtimes wider than 2^63 apart into one DSQ gets the order inverted:
the tasks it placed last run first and the rest starve. Reproduced with a probe scheduler assigning half its tasks vtimes near 0 and the other half vtimes above 2^63 -- four of eight busy tasks monopolized the CPU while the other four starved.Quoted 4 lines
Compare with plain u64 < instead, which is a total order and always honors the order the scheduler asked for. The transient misordering around the natural 2^64 wrap is the same class of anomaly the cyclic comparison trades it for, but bounded.
I don't think switching to plain u64 ordering is safe here.
The current
scx_bpf_dsq_insert_vtime()documentation explicitly defines the ordering in terms oftime_before64(), including wraparound. For example:a =
U64_MAX- 5
b = 3a is earlier than b in cyclic vtime ordering.
time_before64(a, b)correctly returns true, while plain a < b would place b first.
Quoted 7 lines
Moreover, this is not a short transient. If post-wrap tasks continue to be reinserted with small vtimes, a can remain behind them until their vtime traverses almost the entire u64 range, resulting in effective starvation.
Can we preserve
time_before64()and document or enforce the half-range requirement instead?
You're both right, patch 1/2 was wrong. My probe fed values that violate the rolling-cursor assumption, and the "inversion" was the API behaving as documented. Dropping 1/2.
I'll send the documentation patch Tejun suggested.
Thanks,
Tao
Quoted 27 lines
Thanks,
-AndreaQuoted 24 lines
Fixes 06e51be3d5e7 ("sched_ext: Add vtime-ordered priority queue to dispatch_q's")Signed-off-by Tao Cui <[email protected]>--- kernel/sched/ext/ext.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)kernel/sched/ext/ext.c +2
-1@@ -1417,7 +1417,8 @@ static bool scx_dsq_priq_less(struct rb_node *node_a,const struct task_struct *b = container_of(node_b, struct task_struct, scx.dsq_priq); -return time_before64 (a->scx.dsq_vtime, b->scx.dsq_vtime); +/* dsq_vtime is arbitrary BPF input: keep a total order */ +return a->scx.dsq_vtime < b->scx.dsq_vtime; }static void dsq_inc_nr (struct scx_dispatch_q *dsq,struct task_struct *p,u64 enq_flags)Signature · 1 line
2.43.0