[PATCH 0/2] sched_ext: fix wraparound-unsafe vtime orderings

[PATCH 0/2] sched_ext: fix wraparound-unsafe vtime orderings

[Tao Cui]

From: Tao Cui <cuitao@kylinos.cn>

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(-)

-- 
2.43.0

[PATCH 1/2] sched_ext: fix vtime priority queue inversion on wide vtime spread

[Tao Cui]

From: Tao Cui <cuitao@kylinos.cn>

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.

Fixes: 06e51be3d5e7 ("sched_ext: Add vtime-ordered priority queue to dispatch_q's")
Signed-off-by: Tao Cui <cuitao@kylinos.cn>
---
 kernel/sched/ext/ext.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/kernel/sched/ext/ext.c b/kernel/sched/ext/ext.c
index 8041c87a3562..dd0ce01370d1 100644
--- a/kernel/sched/ext/ext.c
+++ b/kernel/sched/ext/ext.c
@@ -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)
-- 
2.43.0

Re: [PATCH 1/2] sched_ext: fix vtime priority queue inversion on wide vtime spread

[sashiko-bot]

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 <cuitao@kylinos.cn>

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.

> diff --git a/kernel/sched/ext/ext.c b/kernel/sched/ext/ext.c
> index 18183062f751c..db1ea9054c0ca 100644
> --- a/kernel/sched/ext/ext.c
> +++ b/kernel/sched/ext/ext.c
> @@ -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;
}

>  }

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

Re: [PATCH 1/2] sched_ext: fix vtime priority queue inversion on wide vtime spread

[Andrea Righi]

Hi Tao,

On Tue, Sep 01, 2026 at 10:40:37AM +0800, Tao Cui wrote:
> From: Tao Cui <cuitao@kylinos.cn>
> 
> 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.

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

> 
> Fixes: 06e51be3d5e7 ("sched_ext: Add vtime-ordered priority queue to dispatch_q's")
> Signed-off-by: Tao Cui <cuitao@kylinos.cn>
> ---
>  kernel/sched/ext/ext.c | 3 ++-
>  1 file changed, 2 insertions(+), 1 deletion(-)
> 
> diff --git a/kernel/sched/ext/ext.c b/kernel/sched/ext/ext.c
> index 8041c87a3562..dd0ce01370d1 100644
> --- a/kernel/sched/ext/ext.c
> +++ b/kernel/sched/ext/ext.c
> @@ -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)
> -- 
> 2.43.0
> 

Re: [PATCH 1/2] sched_ext: fix vtime priority queue inversion on wide vtime spread

[Tao Cui]

Hello, Andrea, Tejun.

在 2026/9/1 14:47, Andrea Righi 写道:
> Hi Tao,
> 
> On Tue, Sep 01, 2026 at 10:40:37AM +0800, Tao Cui wrote:
>> From: Tao Cui <cuitao@kylinos.cn>
>>
>> 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.
> 
> 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?
> 

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

> Thanks,
> -Andrea
> 
>>
>> Fixes: 06e51be3d5e7 ("sched_ext: Add vtime-ordered priority queue to dispatch_q's")
>> Signed-off-by: Tao Cui <cuitao@kylinos.cn>
>> ---
>>  kernel/sched/ext/ext.c | 3 ++-
>>  1 file changed, 2 insertions(+), 1 deletion(-)
>>
>> diff --git a/kernel/sched/ext/ext.c b/kernel/sched/ext/ext.c
>> index 8041c87a3562..dd0ce01370d1 100644
>> --- a/kernel/sched/ext/ext.c
>> +++ b/kernel/sched/ext/ext.c
>> @@ -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)
>> -- 
>> 2.43.0
>>

Re: [PATCH 1/2] sched_ext: fix vtime priority queue inversion on wide vtime spread

[Tejun Heo]

Hello,

On Tue, Sep 01, 2026 at 10:40:37AM +0800, Tao Cui wrote:
...
> 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

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.

-- 
tejun

[PATCH 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 2/2] sched_ext/scx_flatcg: make cgv_node_less() wraparound-safe

[sashiko-bot]

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 <cuitao@kylinos.cn>

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.

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..3a25cfdc97092 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)

[ ... ]

[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?

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

Re: [PATCH 2/2] sched_ext/scx_flatcg: make cgv_node_less() wraparound-safe

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 1751 bytes --]

> 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>

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:

  Fixes: a4103eacc2ab4 ("sched_ext: Add a cgroup scheduler which uses flattened hierarchy")


---
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