Skip to contentSkip to conversation

sched_ext: fix wraparound-unsafe vtime orderings

PATCH In review Tao Cui 5 participants 9 messages Sep 1

Subsystems (3)
lore
Share & tools
lore

Tao Cui

author
#0 lore raw

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
author
#1 lore raw

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.

Fixes 06e51be3d5e7 ("sched_ext: Add vtime-ordered priority queue to dispatch_q's")
---
 kernel/sched/ext/ext.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
kernel/sched/ext/ext.c +2 -1
index 8041c87a3562..dd0ce01370d1 100644
@@ -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
author
#6 lore raw

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

In reply to Tao Cui

From: 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.

Fixes 7b742aa2c2c9 ("sched_ext: Add a cgroup scheduler which uses flattened hierarchy")
---
 tools/sched_ext/scx_flatcg.bpf.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
tools/sched_ext/scx_flatcg.bpf.c +2 -1
index 454ebb820c5e..be03b409db5e 100644
@@ -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
#7 lore raw

Re: [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
index fec3595818269..3a25cfdc97092 100644

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
#2 lore raw

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

In reply to Tao Cui
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…

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
index 18183062f751c..db1ea9054c0ca 100644
@@ -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
#8 lore raw

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

In reply to Tao Cui
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…
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 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.

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

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

reviewer
#3 lore raw

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

In reply to Tao Cui

Hi Tao,

Quoted 13 lines · Tao Cui

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.

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")
---
 kernel/sched/ext/ext.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
kernel/sched/ext/ext.c +2 -1
index 8041c87a3562..dd0ce01370d1 100644
@@ -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
reviewer
#5 lore raw

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

In reply to Tao Cui

Hello,

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

Signature · 1 line
tejun
author
#4 lore raw

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

In reply to Andrea Righi

Hello, Andrea, Tejun.

Quoted 32 lines · Andrea Righi

Hi Tao,

Quoted 13 lines · Tao Cui

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.

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.

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

Quoted 24 lines
Fixes 06e51be3d5e7 ("sched_ext: Add vtime-ordered priority queue to dispatch_q's")
---
 kernel/sched/ext/ext.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)
kernel/sched/ext/ext.c +2 -1
index 8041c87a3562..dd0ce01370d1 100644
@@ -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