Skip to contentSkip to conversation

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

PATCH Applied Tao Cui 3 participants 4 messages Aug 15

Subsystems (2)
lore
Share & tools
lore

Tao Cui

author
#0 lore raw

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.

Fixes a4103eacc2ab ("sched_ext: Add a cgroup scheduler which uses flattened hierarchy")
---
 tools/sched_ext/scx_flatcg.bpf.c | 14 +++++++++++---
 1 file changed, 11 insertions(+), 3 deletions(-)
tools/sched_ext/scx_flatcg.bpf.c +11 -3
index 0fd214cc61da..ddcf6bc03b11 100644
@@ -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
#1 lore raw
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] 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
index 0fd214cc61dae..ddcf6bc03b11c 100644

[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
author
#2 lore raw
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 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
index 0fd214cc61dae..ddcf6bc03b11c 100644

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

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

Quoted 2 lines

[ ... ]