sched_ext: document and enforce vtime ordering constraints
Subsystems (3)
v3 cover sched_ext: document and enforce vtime ordering constraints
From: Tao Cui <[email protected]>
Patch 1 documents the rolling-cursor requirement for vtime ordering in scx_bpf_dsq_insert_vtime(). Patch 2 fixes scx_flatcg's comparator to use the cyclic comparison, which is correct there because cgrp_cap_budget() upholds that requirement.
Changes since v2:
- 1/2: "less than 2^63 apart" (not "within"), folded into the paragraph above
- 2/2: use time_before() instead of open-coded comparison, drop the comment, fix the wrap direction and timing, state both lag and lead bounds, Fixes corrected to upstream a4103eacc2ab (Tejun)
Changes since v1:
- drop 1/2 (kernel priq comparator change): the cyclic ordering is the documented contract; a plain comparison causes unbounded starvation at the natural wrap (Andrea, Tejun)
- new 1/2: document the rolling-cursor requirement instead
- 2/2 (flatcg) unchanged
Tao Cui (2):
sched_ext: document the rolling-cursor requirement for dsq_vtime sched_ext/scx_flatcg: make cgv_node_less() wraparound-safe
kernel/sched/ext/ext.c | 4 +++- tools/sched_ext/scx_flatcg.bpf.c | 2 +- 2 files changed, 4 insertions(+), 2 deletions(-)
Signature · 1 line
2.43.0
PATCH v3 1/2 sched_ext: document the rolling-cursor requirement for dsq_vtime
From: Tao Cui <[email protected]>
scx_bpf_dsq_insert_vtime() orders tasks by time_before64(), which is only meaningful when the values within a given DSQ stay less than 2^63 apart. This is implicit in how a vtime scheduler works but not spelled out anywhere. Document it so BPF scheduler authors know the constraint.
--- kernel/sched/ext/ext.c | 4 +++- 1 file changed, 3 insertions(+), 1 deletion(-)
kernel/sched/ext/ext.c +3 -1
@@ -8903,7 +8903,9 @@ struct scx_bpf_dsq_insert_vtime_args {* * @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. +* ordering and vice-versa. vtime is a rolling cursor and values used for +* ordering within a given DSQ should stay less than 2^63 apart for +* time_before64() ordering to remain well-defined. * * A DSQ can only be used as a FIFO or priority queue at any given time and this * function must not be called on a DSQ which already has one or more FIFO tasks
Signature · 1 line
2.43.0
PATCH v3 2/2 sched_ext/scx_flatcg: make cgv_node_less() wraparound-safe
In reply to Tao CuiFrom: Tao Cui <[email protected]>
cgv_node_less() compares cvtimes with a plain <, which misorders once cvtime wraps: the wrapped node lands at the front of the tree while the unwrapped ones get stuck behind it. Each CPU picking a cgroup charges it a full slice, making wrap occur earlier than a naive estimate might suggest.
Use time_before() instead. cgrp_cap_budget() bounds the lag behind cvtime_now, while the lead is bounded by the slice charge plus pending cvtime_delta on re-insertion, so the cyclic ordering assumptions of time_before() hold.
--- tools/sched_ext/scx_flatcg.bpf.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-)
tools/sched_ext/scx_flatcg.bpf.c +1 -1
@@ -144,7 +144,7 @@ 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; +return time_before (cgc_a->cvtime, cgc_b->cvtime); }static struct fcg_cpu_ctx *find_cpu_ctx (void )
Signature · 1 line
2.43.0
[email protected]
AI reviewRe: [PATCH v3 2/2] sched_ext/scx_flatcg: make cgv_node_less() wraparound-safe
Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
Thank you for your contribution! Sashiko AI review found 2 potential issue(s) to consider:
Pre-existing issues:
- [High] Unsigned division on a wrapped negative time delta causes massive artificial inflation of virtual time for expired cgroups.
- [Medium] Race condition in cvtime_delta extraction using __sync_fetch_and_sub(ptr, *ptr) causes double accounting. --
commit 069998f7546e450b1de3ae56c137b9e1dd16b919
Author: Tao Cui <[email protected]>
sched_ext/scx_flatcg: make cgv_node_less() wraparound-safe
cgv_node_less() compares cvtimes with a plain <, which misorders once cvtime wraps: the wrapped node lands at the front of the tree while the unwrapped ones get stuck behind it. Each CPU picking a cgroup charges it a full slice, making wrap occur earlier than a naive estimate might suggest.
Quoted 4 lines
tools/sched_ext/scx_flatcg.bpf.c +0
-0
[ ... ]
tools/sched_ext/scx_flatcg.bpf.c static bool cgv_node_less(struct bpf_rb_node *a, const struct bpf_rb_node *b) · line 148
Quoted 7 lines
tools/sched_ext/scx_flatcg.bpf.c +1
-1@@ -144,7 +144,7 @@ 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; +return time_before (cgc_a->cvtime, cgc_b->cvtime); }
While reviewing this file, I noticed a couple of pre-existing issues:
tools/sched_ext/scx_flatcg.bpf.c:cgrp_cap_budget() {
...
delta = __sync_fetch_and_sub(&cgc->cvtime_delta, cgc->cvtime_delta);
cvtime = cgv_node->cvtime + delta;
...
}[Severity: Medium]
This isn't a bug introduced by this patch, but does this create a race condition that leads to double accounting?
Because __sync_fetch_and_sub(ptr, *ptr) evaluates the second argument before the atomic subtraction, a concurrent __sync_fetch_and_add() from another CPU between the memory read of cgc->cvtime_delta and the atomic subtraction will cause the added delta to be subtracted but still partially left in the counter. The atomic operation returns the new value, charging the cgroup for the increment, but leaves the increment in the counter to be charged again on the next extraction.
If CPU A executes fcg_stopping() or fcg_dispatch() and calls __sync_fetch_and_add(&cgc->cvtime_delta, val), and concurrently CPU B executes cgrp_cap_budget() and evaluates __sync_fetch_and_sub(&cgc->cvtime_delta, cgc->cvtime_delta), a race in the tiny window between B's argument evaluation and the atomic subtraction could trigger double charging.
Could this be replaced with an atomic exchange (e.g., __sync_lock_test_and_set()) to safely extract and clear the counter?
tools/sched_ext/scx_flatcg.bpf.c:fcg_dispatch() {
...
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));
bpf_spin_unlock(&cgv_tree_lock);
...
}[Severity: High]
This isn't a bug introduced by this patch, but does this calculation suffer from unsigned division on a wrapped negative time delta?
When a cgroup's slice has expired, the current time 'now' can easily be greater than 'cpuc->cur_at + cgrp_slice_ns' due to interrupt latency or normal scheduling jitter. The '(cpuc->cur_at + cgrp_slice_ns - now)' is computed using unsigned u64 arithmetic, resulting in a wrapped large positive number. Since all operands are unsigned and hweight is a u32, the subsequent multiplication and division execute as unsigned arithmetic.
The resulting huge positive quotient is then added to cgc->cvtime_delta, artificially inflating the virtual time by a massive amount and potentially starving all tasks within the cgroup.
Should there be an explicit cast to a signed type (like s64) before division to prevent this?
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=2
Tejun Heo
reviewerQuoted 3 lines · Tao Cui
Tao Cui (2):
sched_ext: document the rolling-cursor requirement fordsq_vtimesched_ext/scx_flatcg: makecgv_node_less()wraparound-safe
Applied 1-2 to sched_ext/for-7.4 with the subjects capitalized.
Thanks.
--
tejun