Skip to content

sched_ext: fix wraparound-unsafe vtime orderings

Tao Cui bpf lkml sched-ext 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 Latest2 patches 3 repliesIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/2sched_ext: fix vtime priority queue inversion on wide vtime spreadkernel/sched/ext/ext.c+2 -13 replies
2/2sched_ext/scx_flatcg: make cgv_node_less() wraparound-safetools/sched_ext/scx_flatcg.bpf.c+2 -10 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

Cover letter [PATCH 0/2] sched_ext: fix wraparound-unsafe vtime orderings

From: Tao Cui <[email protected]>

Two spots order tasks by 64-bit virtual time with comparisons that break when the values are far apart: the kernel's vtime DSQ priority queue and scx_flatcg's cgroup tree. They need opposite fixes, which is the point of this series.

The kernel's scx_dsq_priq_less() compares with time_before64(), i.e. (s64)(a - b) < 0. That is only a valid ordering when all values in the queue are less than 2^63 apart. CFS upholds that invariant with min_vruntime clamping; sched_ext cannot, because dsq_vtime comes straight from the BPF scheduler. A scheduler that inserts vtimes wider than 2^63 apart into one DSQ gets the inverted order -- the tasks it placed last run first while the rest starve. Patch 1 switches to a plain u64 comparison, which is a total order and always honors the requested order; it reproduces the inversion with a probe scheduler and verifies the fix.

scx_flatcg's cgv_node_less() has the inverse problem: it compares with a plain <, which misorders once cvtime wraps. There the cyclic (s64)(a - b) < 0 comparison from patch 1's bug is the correct fix, because flatcg does uphold the spread invariant -- cgrp_cap_budget() clamps every node to within max_budget behind cvtime_now -- and the cyclic comparison also carries the ordering correctly across the natural 2^64 wrap, which a plain comparison would not.

So: same bug family, opposite fixes, each justified by whether the spread invariant exists. This is also why the naive "use time_before64 everywhere" suggestion doesn't hold -- without the invariant it is exactly the inversion patch 1 fixes.

Tao Cui (2):
sched_ext: fix vtime priority queue inversion on wide vtime spread sched_ext/scx_flatcg: make cgv_node_less() wraparound-safe

 kernel/sched/ext/ext.c           | 3 ++-
 tools/sched_ext/scx_flatcg.bpf.c | 3 ++-
 2 files changed, 4 insertions(+), 2 deletions(-)
Signature · 1 line
2.43.0