sched_ext/scx_flatcg: Fix cvtime true-up on slice expiry
Subsystems (2)
PATCH 1/1 sched_ext/scx_flatcg: Fix cvtime true-up on slice expiry
From: Tao Cui <[email protected]>
fcg_dispatch() true-ups the current cgroup's cvtime when its slice expires or its DSQ runs empty while the slice is still active:
__sync_fetch_and_add(&cgc->cvtime_delta, (cpuc->cur_at + cgrp_slice_ns - now) * FCG_HWEIGHT_ONE / (cgc->hweight ?: 1));
The true-up should be actual minus charged: on CNS_EXPIRE, the overrun (now - cur_at - cgrp_slice_ns) should be added; on CNS_EMPTY, the unused portion of the slice should be subtracted. The expression above has the sign inverted, and in the CNS_EXPIRE case now is already past cur_at + cgrp_slice_ns, so the u64 subtraction wraps. The multiplication preserves the two's complement encoding but the unsigned division by hweight destroys it, adding roughly 2^64/hweight per expiry instead of a small correction.
Under saturation the hweight budget clamp in cgrp_cap_budget() masks most of the garbage, so the weight distribution barely moves, but the accounting is broken all the same. Compute the delta as a signed value and use fetch_and_add()/fetch_and_sub() so that the dividends stay positive, as BPF division is unsigned.
Instrumented the true-up and ran a saturated three-leaf cgroup tree on a 4-CPU VM: without the fix, each expiry added ~5e15 (2^64/hweight territory) to cvtime_delta; with it, the corrections are back to slice scale, with the overrun added and the unused portion subtracted.
--- tools/sched_ext/scx_flatcg.bpf.c | 14 +++++++++++--- 1 file changed, 11 insertions(+), 3 deletions(-)
tools/sched_ext/scx_flatcg.bpf.c +11 -3
@@ -769,10 +769,18 @@ void BPF_STRUCT_OPS(fcg_dispatch, s32 cpu, struct task_struct *prev)* cgroup to execute but the latter needs to be done in a loop * and we can't keep the lock held. Oh well... */ +s64 delta = now - cpuc->cur_at - cgrp_slice_ns; +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 )); +/* keep the dividends positive, BPF division is unsigned */ +if (delta >=0 ) +__sync_fetch_and_add (&cgc->cvtime_delta, + (u64 )delta *FCG_HWEIGHT_ONE / + (cgc->hweight ?:1 )); +else +__sync_fetch_and_sub (&cgc->cvtime_delta, + (u64 )-delta *FCG_HWEIGHT_ONE / + (cgc->hweight ?:1 ));bpf_spin_unlock (&cgv_tree_lock); }else {stat_inc (FCG_STAT_CNS_GONE );
Signature · 1 line
2.43.0
[email protected]
AI reviewThank 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] Priority inversion in RB-tree due to unprotected cvtime wraparound in cgv_node_less(). --
--- Patch [1]: [PATCH] sched_ext/scx_flatcg: Fix cvtime true-up on slice expiry --- commit c84c79d28fee1a17412c6846489091841b03f293
Author: Tao Cui <[email protected]> Date: Sat Aug 15 04:59:05 2026 +0000
sched_ext/scx_flatcg: Fix cvtime true-up on slice expiry
This commit fixes the cvtime true-up calculation in fcg_dispatch() when a cgroup's slice expires or its DSQ runs empty. It addresses a bug where the unsigned division by hweight was inverting the sign of the delta, causing massive jumps in cvtime_delta instead of minor corrections. The fix properly computes the delta as a signed value and uses fetch_and_add()/fetch_and_sub() to keep dividends positive.
tools/sched_ext/scx_flatcg.bpf.c
Quoted 4 lines
tools/sched_ext/scx_flatcg.bpf.c +0
-0
[Severity: High]
This is a pre-existing issue, but was not introduced by the patch under review. Since this file handles cvtime accounting, could the red-black tree comparison in cgv_node_less() suffer from priority inversion due to cvtime wraparound?
Looking at tools/sched_ext/scx_flatcg.bpf.c:cgv_node_less():
static bool cgv_node_less(struct bpf_rb_node *a, const struct bpf_rb_node *b)
{
struct cgv_node *cgc_a, *cgc_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;
}If a cgroup with the lowest possible weight (1) advances its cvtime rapidly, a 64-bit nanosecond counter could wrap around in approximately 3.25 days of continuous execution.
When a cgroup's cvtime wraps to a small value (e.g., 100) while other cgroups are near the 64-bit maximum, the standard < operator will evaluate 100 < (2^64 - 1000) as true.
Would this place the wrapped cgroup permanently at the front of the tree and completely starve other cgroups? Should this use a wraparound-safe comparison like time_before64() instead, similar to the time_before() usage elsewhere in the scheduler?
[ ... ]
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
Quoted 47 lines · 在 2026/8/15 13:14, [email protected] 写道:
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
Pre-existing issues:
- [High] Priority inversion in RB-tree due to unprotected cvtime wraparound incgv_node_less(). ----- Patch [1]: [PATCH] sched_ext/scx_flatcg: Fix cvtime true-up on slice expiry --- commit
c84c79d28fee1a17412c6846489091841b03f293Author: Tao Cui <[email protected]> Date: Sat Aug 15 04:59:05 2026 +0000sched_ext/scx_flatcg: Fix cvtime true-up on slice expiry
This commit fixes the cvtime true-up calculation in
fcg_dispatch()when a cgroup's slice expires or its DSQ runs empty. It addresses a bug where the unsigned division by hweight was inverting the sign of the delta, causing massive jumps incvtime_deltainstead of minor corrections. The fix properly computes the delta as a signed value and uses fetch_and_add()/fetch_and_sub() to keep dividends positive.tools/sched_ext/scx_flatcg.bpf.c
Quoted 4 lines
tools/sched_ext/scx_flatcg.bpf.c +0
-0[Severity: High]
This is a pre-existing issue, but was not introduced by the patch under review. Since this file handles cvtime accounting, could the red-black tree comparison incgv_node_less()suffer from priority inversion due to cvtime wraparound?Looking at tools/sched_ext/scx_flatcg.bpf.c:cgv_node_less():
static bool
cgv_node_less(struct bpf_rb_node *a, const struct bpf_rb_node *b){ struct cgv_node *cgc_a, *cgc_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; }If a cgroup with the lowest possible weight (1) advances its cvtime rapidly, a 64-bit nanosecond counter could wrap around in approximately 3.25 days of continuous execution.
Quoted 9 lines
When a cgroup's cvtime wraps to a small value (e.g., 100) while other cgroups are near the 64-bit maximum, the standard < operator will evaluate 100 < (2^64 - 1000) as true.
Would this place the wrapped cgroup permanently at the front of the tree and completely starve other cgroups? Should this use a wraparound-safe comparison like
time_before64()instead, similar to thetime_before()usage elsewhere in the scheduler?
Right, the comparison is not wraparound-safe, and CFS compares vruntimes with (s64)(a - b) < 0 for the same reason. Hard to reach in practice though: cgrp_cap_budget() clamps each node's cvtime to within cvtime_now - max_budget, so wrapping needs an extreme weight ratio held for days. Pre-existing either way, and with the true-up fixed cvtime no longer collects garbage, so this patch only makes it less likely.
If we want to close it, (s64)(a->cvtime - b->cvtime) < 0 would do it, as a separate patch.
Quoted 2 lines
[ ... ]
Applied to sched_ext/for-7.3.
Thanks.
--
tejun