[PATCH] sched_ext/scx_flatcg: Fix cvtime true-up on slice expiry

[PATCH] sched_ext/scx_flatcg: Fix cvtime true-up on slice expiry

[Tao Cui]

From: Tao Cui <cuitao@kylinos.cn>

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.

Fixes: a4103eacc2ab ("sched_ext: Add a cgroup scheduler which uses flattened hierarchy")
Suggested-by: Tejun Heo <tj@kernel.org>
Signed-off-by: Tao Cui <cuitao@kylinos.cn>
---
 tools/sched_ext/scx_flatcg.bpf.c | 14 +++++++++++---
 1 file changed, 11 insertions(+), 3 deletions(-)

diff --git a/tools/sched_ext/scx_flatcg.bpf.c b/tools/sched_ext/scx_flatcg.bpf.c
index 0fd214cc61da..ddcf6bc03b11 100644
--- a/tools/sched_ext/scx_flatcg.bpf.c
+++ b/tools/sched_ext/scx_flatcg.bpf.c
@@ -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);
-- 
2.43.0

Re: [PATCH] sched_ext/scx_flatcg: Fix cvtime true-up on slice expiry

[sashiko-bot]

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

> diff --git a/tools/sched_ext/scx_flatcg.bpf.c b/tools/sched_ext/scx_flatcg.bpf.c
> index 0fd214cc61dae..ddcf6bc03b11c 100644
> --- a/tools/sched_ext/scx_flatcg.bpf.c
> +++ b/tools/sched_ext/scx_flatcg.bpf.c

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

[ ... ]

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

Re: [PATCH] sched_ext/scx_flatcg: Fix cvtime true-up on slice expiry

[Tao Cui]

在 2026/8/15 13:14, sashiko-bot@kernel.org 写道:
> 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 <cuitao@kylinos.cn>
> 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.
> 
>> diff --git a/tools/sched_ext/scx_flatcg.bpf.c b/tools/sched_ext/scx_flatcg.bpf.c
>> index 0fd214cc61dae..ddcf6bc03b11c 100644
>> --- a/tools/sched_ext/scx_flatcg.bpf.c
>> +++ b/tools/sched_ext/scx_flatcg.bpf.c
> 
> [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?
> 
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.

> [ ... ]
> 

Re: [PATCH] sched_ext/scx_flatcg: Fix cvtime true-up on slice expiry

[Tejun Heo]

Applied to sched_ext/for-7.3.

Thanks.

--
tejun