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

[Tao Cui]

From: Tao Cui <cuitao@xxxxxxxxxx>

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(-)

-- 
2.43.0