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

[Tao Cui]

Hello, Andrea, Tejun.

在 2026/9/1 14:47, 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?
> 

You're both right, patch 1/2 was wrong. My probe fed values that
violate the rolling-cursor assumption, and the "inversion" was the
API behaving as documented. Dropping 1/2.

I'll send the documentation patch Tejun suggested.

Thanks,
Tao

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