Re: [PATCH RESEND] sched/fair: Fix overflow in vruntime_eligible()

K Prateek Nayak
2026-04-29T05:03:58Z

Hello Peter,

On 4/28/2026 11:05 PM, Peter Zijlstra wrote:
> On Tue, Apr 28, 2026 at 09:47:11PM +0530, K Prateek Nayak wrote:
>> (+ scheduler folks)
>>
>> Hello Zhan,
>>
>> On 4/28/2026 8:19 PM, Zhan Xusheng wrote:
>>> After commit 556146ce5e94 ("sched/fair: Avoid overflow in
>>> enqueue_entity()"), place_entity() can shift cfs_rq->zero_vruntime
>>> towards a newly enqueued heavy entity. This can make (vruntime -
>>> zero_vruntime) very large for other entities and cause key * load in
>>> vruntime_eligible() to overflow s64, flipping the eligibility result.
>>
>> So the commit in question moves the zero_vruntime only when the
>> load > sum_weight.
>>
>> You seem to have found a case where the entity_key() is already large
>> enough that moving the zero_vruntime farther will make the eligibility
>> check overflow which we were hoping will not be the case.
>>
>> Do you have a reproducer that fails pick_eevdf() after introduction of
>> commit 556146ce5e94? Also, do you see any splats in the dmesg since we
>> have a defensive WARN_ON() to catch an overflow.
>
> Right, either a reproducer or a trace showing the values leading up to
> this are the absolute minimum you need to provide. That is, you need a
> definite description of how you got there, otherwise you cannot judge
> the solution is sound.
>
> Anyway... let me construct a worst case.
>
> So if you have this cgroup crap on, then you can have an entity of
> weight 2, and vlag should then be bounded by: (slice+TICK_NSEC) *
> NICE_0_LOAD, which is around 44 bits as per the comment on entity_key().
>
> The other end is 100*NICE_0_LOAD, so lets wake that, then you get:
>
> {key, weight}[] := {
> puny: { (slice + TICK_NSEC) * NICE_0_LOAD, 2 },
> max: { 0, 100*NICE_0_LOAD },
> }

So MAX_SHARES is (1UL << 18) and we then scale it up so the weight can
can go up to (1 << 28) I suppose in UP setting.

So let us assume there is a single task with the largest custom slice on
each cgroup making the min_slice equal to 100ms. Things start off in
such a way that puny having a vruntime of say -1 is picked over max which
had a vruntime of 0 for the sake of simplicity.

Deadline then becomes:

puny->deadline = -1 + __calc_delta(100ms, NICE_0_LOAD, 2)

which is 52428800000000 - 1.

At 10HZ tick + RUN_TO_PARITY, we get 10ms error so that puts the
entity_key() at 57671680000000 (46 bits)

>
> The avg_vruntime() would end up being very close to 0 (which is
> zero_vruntime), so no real help making that more accurate.
>
> vruntime_eligible(puny) ends up with:
>
> avg = 2 * puny.key (+ 0)
> weight = 2 + 100 * NICE_0_LOAD
>
> avg >= puny.key * weight
>
> And that is: (slice + TICK_NSEC) * NICE_0_LOAD * NICE_0_LOAD * 100
> > and yes, I suppose that can exceed 64bit :-(

Then the worst case right side would be:

57671680000000 * load /* load = ((1 << 28) + 2) */

and yes that goes beyond 64-bits at 15481123719086080000000.

I'm running with this configurations:

echo 2 > /sys/fs/cgroup/cg0/cpu.weight
echo 10000 > /sys/fs/cgroup/cg1/cpu.weight

Weight of 2 actually gets scaled up to 20480 for UP scenario so I go try
to make it even smaller with SMP and wait until it gets picked again.

So it goes from ...

cfs_rq[0]:/cg0
.se->vruntime : 11602839.678164
.se->deadline : 19092472.390575
.se->sum_exec_runtime : 4243.207300
.se->slice : 100.000000
.se->custom_slice : 1
.se->load.weight : 14
.se->avg.load_avg : 2
.se->avg.util_avg : 0
.se->avg.runnable_avg : 1024

cfs_rq[0]:/cg1
.se->vruntime : 11602835.026387
.se->deadline : 11602835.706227
.se->sum_exec_runtime : 2646719.706164
.se->slice : 100.000000
.se->custom_slice : 1
.se->load.weight : 104857600
.se->avg.load_avg : 102389
.se->avg.util_avg : 1024
.se->avg.runnable_avg : 1024

cfs_rq[0]:/
.left_deadline : 19092472.390575
.left_vruntime : 11602839.678164
.zero_vruntime : 11602835.026387
.sum_w_vruntime : 65124878 (25 bits)
.sum_weight : 14
.sum_shift : 0
.avg_vruntime : 11602835.026387
.right_vruntime : 11602839.678164
.spread : 0.000000

... to ...

cfs_rq[0]:/cg0
.se->vruntime : 19392969.031442
.se->deadline : 26881950.428361
.se->sum_exec_runtime : 4347.216748
.se->slice : 100.000000
.se->custom_slice : 1
.se->load.weight : 14
.se->avg.load_avg : 1
.se->avg.util_avg : 904
.se->avg.runnable_avg : 1024

cfs_rq[0]:/cg1
.se->vruntime : 11602851.024250
.se->deadline : 11602851.144214
.se->sum_exec_runtime : 2648319.534241
.se->slice : 100.000000
.se->custom_slice : 1
.se->load.weight : 104857600
.se->avg.load_avg : 102386
.se->avg.util_avg : 1024
.se->avg.runnable_avg : 1024

cfs_rq[0]:/
.left_deadline : 26881950.428361
.left_vruntime : 19392969.031442
.zero_vruntime : 11602852.064342
.sum_w_vruntime : 109061637539400 (46 bits)
.sum_weight : 14
.sum_shift : 0
.avg_vruntime : 11602852.064342
.right_vruntime : 19392969.031442
.spread : 0.000000

without any splat so I'm not sure if there is something that prevents
a possible crash since a weight of 104857600 should have definitely
made that entity_key() overflow.

>
> Can someone double check that? I have a silly head-ache and could easily
> have made mistake. Not sure what the best solution is either. I think we
> can show avg cannot overflow, and if this multiplication overflows, then
> it must be larger, so perhaps the proposed patch is the best option.
>
> Dunno, need clear head :/

--
Thanks and Regards,
Prateek