sched/fair: Fix overflow in vruntime_eligible()
On Wed, Apr 29, 2026 at 10:33:48AM +0530, K Prateek Nayak wrote:
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 },
}
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
--
Anyway, I had a poke around with godbolt, and the below seems to
generate the best code for things like x86_64 and arm64.
Specifically, the __builtin_mul_overflow() already has to compute the
128 bit product anyway for most architectures, so using that directly
then leads to saner asm and easier to understand code.
AFAICT HPPA64 is the only 64bit architecture that doesn't implement
__int128 and will thus be demoted to doing what we do on 32bit.
Now all I need to do is write a coherent Changelog to go with it ...
*sigh*
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Link: https://patch.msgid.link/20260501104006.GA3102624@noisy.programming.kicks-ass.net
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 7289658..214fe9d 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -904,7 +904,7 @@ static int vruntime_eligible(struct cfs_rq *cfs_rq, u64 vruntime)
load += weight;
}
- return avg >= vruntime_op(vruntime, "-", cfs_rq->zero_vruntime) * load;
+ return avg >= (sched_double_long_t)vruntime_op(vruntime, "-", cfs_rq->zero_vruntime) * load;
}
int entity_eligible(struct cfs_rq *cfs_rq, struct sched_entity *se)
diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
index 9f63b15..b5f18ef 100644
--- a/kernel/sched/sched.h
+++ b/kernel/sched/sched.h
@@ -146,7 +146,7 @@ extern struct list_head asym_cap_list;
* Really only required when CONFIG_FAIR_GROUP_SCHED=y is also set, but to
* increase coverage and consistency always enable it on 64-bit platforms.
*/
-#ifdef CONFIG_64BIT
+#if defined(CONFIG_64BIT) && defined(__SIZEOF_INT128__)
# define NICE_0_LOAD_SHIFT (SCHED_FIXEDPOINT_SHIFT + SCHED_FIXEDPOINT_SHIFT)
# define scale_load(w) ((w) << SCHED_FIXEDPOINT_SHIFT)
# define scale_load_down(w) \
@@ -157,10 +157,12 @@ extern struct list_head asym_cap_list;
__w = max(2UL, __w >> SCHED_FIXEDPOINT_SHIFT); \
__w; \
})
+typedef __int128 sched_double_long_t;
#else
# define NICE_0_LOAD_SHIFT (SCHED_FIXEDPOINT_SHIFT)
# define scale_load(w) (w)
# define scale_load_down(w) (w)
+typedef s64 sched_double_long_t;
#endif
/*
