Skip to contentSkip to conversation

sched_ext: document and enforce vtime ordering constraints

PATCH In review Tao Cui 3 participants 5 messages Sep 2

Subsystems (3)
lore
Share & tools
lore

Tao Cui

author
#0 lore raw

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

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
index 8041c87a3562..81a506a4c8ab 100644
@@ -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
author
#2 lore raw

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

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

Re: [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
index fec3595818269..acc1995630e6d 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 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
reviewer
#4 lore raw
In reply to Tao Cui
Quoted 3 lines · Tao Cui

Tao Cui (2):
sched_ext: document the rolling-cursor requirement for dsq_vtime sched_ext/scx_flatcg: make cgv_node_less() wraparound-safe

Applied 1-2 to sched_ext/for-7.4 with the subjects capitalized.

Thanks.

--
tejun