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

[Andrea Righi]

Hi Tao,

On Tue, Sep 01, 2026 at 10:40:37AM +0800, Tao Cui wrote:
> 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.

I don't think switching to plain u64 ordering is safe here.

The current scx_bpf_dsq_insert_vtime() documentation explicitly defines the
ordering in terms of time_before64(), including wraparound. For example:

  a = U64_MAX - 5
  b = 3

a is earlier than b in cyclic vtime ordering. time_before64(a, b) correctly
returns true, while plain a < b would place b first.

Moreover, this is not a short transient. If post-wrap tasks continue to be
reinserted with small vtimes, a can remain behind them until their vtime
traverses almost the entire u64 range, resulting in effective starvation.

Can we preserve time_before64() and document or enforce the half-range
requirement instead?

Thanks,
-Andrea

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