[PATCH 1/2] sched_ext: fix vtime priority queue inversion on wide vtime spread

[Tao Cui]

From: Tao Cui <cuitao@xxxxxxxxxx>

scx_dsq_priq_less() compares dsq_vtime with time_before64(), a cyclic
comparison that is only valid when the values in the queue are less
than 2^63 apart. Unlike CFS, which enforces that invariant with
min_vruntime clamping, sched_ext takes dsq_vtime directly from the BPF
scheduler and cannot bound the spread. A scheduler that inserts tasks
with vtimes wider than 2^63 apart into one DSQ gets the order inverted:
the tasks it placed last run first and the rest starve. Reproduced with
a probe scheduler assigning half its tasks vtimes near 0 and the other
half vtimes above 2^63 -- four of eight busy tasks monopolized the CPU
while the other four starved.

Compare with plain u64 < instead, which is a total order and always
honors the order the scheduler asked for. The transient misordering
around the natural 2^64 wrap is the same class of anomaly the cyclic
comparison trades it for, but bounded.

Fixes: 06e51be3d5e7 ("sched_ext: Add vtime-ordered priority queue to dispatch_q's")
Signed-off-by: Tao Cui <cuitao@xxxxxxxxxx>
---
 kernel/sched/ext/ext.c | 3 ++-
 1 file changed, 2 insertions(+), 1 deletion(-)

diff --git a/kernel/sched/ext/ext.c b/kernel/sched/ext/ext.c
index 8041c87a3562..dd0ce01370d1 100644
--- a/kernel/sched/ext/ext.c
+++ b/kernel/sched/ext/ext.c
@@ -1417,7 +1417,8 @@ static bool scx_dsq_priq_less(struct rb_node *node_a,
 	const struct task_struct *b =
 		container_of(node_b, struct task_struct, scx.dsq_priq);
 
-	return time_before64(a->scx.dsq_vtime, b->scx.dsq_vtime);
+	/* dsq_vtime is arbitrary BPF input: keep a total order */
+	return a->scx.dsq_vtime < b->scx.dsq_vtime;
 }
 
 static void dsq_inc_nr(struct scx_dispatch_q *dsq, struct task_struct *p, u64 enq_flags)
-- 
2.43.0