[PATCH] sched/fair: Avoid overflow in place_entity()

[PATCH] sched/fair: Avoid overflow in place_entity()

[Hui Su]

place_entity() inflates an entity's virtual lag with

    lag * (load + weight) / load

Commit 4823725d9d1d ("sched/fair: Increase weight bits for avg_vruntime")
replaced the scaled-down weights used in this calculation with
avg_vruntime_weight(), removing the arithmetic headroom provided by
scale_load_down().

The multiplication can overflow s64 before the division even when the
final quotient is representable. A task's hierarchical effective weight
can be as small as 2 after avg_vruntime_weight() scaling under group
scheduling, while entity_lag() bounds |vlag| by

    calc_delta_fair(cfs_rq_max_slice(cfs_rq) + TICK_NSEC, se)

For example, with HZ=1000, NICE_0_LOAD=1048576, and the minimum scaled
hierarchical weight scale_load(2)=2048, this bound is 891289600. With 114
maximum-weight entities, the runqueue load is 10361604096. The
intermediate product is:

    891289600 * (10361604096 + 2)
        = 9235189971864780800
        > S64_MAX

The signed overflow corrupts the entity's placement.

Rewrite

    lag * (load + weight) / load

as

    lag + lag * weight / load

The two expressions are equivalent, but the latter avoids multiplying the
virtual lag by the total runqueue weight. entity_lag() bounds vlag against
the entity's effective weight, so the remaining lag * weight product stays
bounded. rescale_entity() preserves this scale across h_load changes and
already relies on the same product when rescaling vlag.

Keep the original zero-load warning semantics by multiplying lag by weight
after replacing the divisor with one.

Fixes: 4823725d9d1d ("sched/fair: Increase weight bits for avg_vruntime")
Signed-off-by: Hui Su <sh_def@163.com>
---
Testing:
- PASS: UBSAN positive/negative overflow cases, zero-load/control paths,
  64-bit landmarks NICE_0_LOAD=1048576 and scale_load(88761)=90891264,
  unscaled 32-bit landmarks 1024/88761, and 100000 random cases checked
  against a __int128 oracle.
- PASS: Full x86_64 kernel build; kernel/sched/fair.o builds for i386
  and arm64.

 kernel/sched/fair.c | 15 ++++++++++++---
 1 file changed, 12 insertions(+), 3 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 7455a83a6a99..a013bfba576b 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -6268,10 +6268,19 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 			load += avg_vruntime_weight(cfs_rq, curr->h_load.weight);
 
 		weight = avg_vruntime_weight(cfs_rq, se->h_load.weight);
-		lag *= load + weight;
-		if (WARN_ON_ONCE(!load))
+		if (WARN_ON_ONCE(!load)) {
 			load = 1;
-		lag = div64_long(lag, load);
+			lag *= weight;
+		} else {
+			/*
+			 * Avoid overflowing lag * (load + weight) by distributing
+			 * the division:
+			 *
+			 *   lag * (load + weight) / load
+			 *     = lag + lag * weight / load
+			 */
+			lag += div64_long(lag * weight, load);
+		}
 
 		/*
 		 * A heavy entity (relative to the tree) will pull the

base-commit: 6812ce4e4379ffc99c52401ec28f0d7ffbc36206

Re: [PATCH] sched/fair: Avoid overflow in place_entity()

[Peter Zijlstra]

On Mon, Sep 28, 2026 at 09:47:54PM +0900, Hui Su wrote:
> place_entity() inflates an entity's virtual lag with
> 
>     lag * (load + weight) / load
> 
> Commit 4823725d9d1d ("sched/fair: Increase weight bits for avg_vruntime")
> replaced the scaled-down weights used in this calculation with
> avg_vruntime_weight(), removing the arithmetic headroom provided by
> scale_load_down().
> 
> The multiplication can overflow s64 before the division even when the
> final quotient is representable. A task's hierarchical effective weight
> can be as small as 2 after avg_vruntime_weight() scaling under group
> scheduling, while entity_lag() bounds |vlag| by
> 
>     calc_delta_fair(cfs_rq_max_slice(cfs_rq) + TICK_NSEC, se)
> 
> For example, with HZ=1000, NICE_0_LOAD=1048576, and the minimum scaled
> hierarchical weight scale_load(2)=2048, this bound is 891289600. With 114
> maximum-weight entities, the runqueue load is 10361604096. The
> intermediate product is:
> 
>     891289600 * (10361604096 + 2)
>         = 9235189971864780800
>         > S64_MAX
> 
> The signed overflow corrupts the entity's placement.
> 
> Rewrite
> 
>     lag * (load + weight) / load
> 
> as
> 
>     lag + lag * weight / load
> 
> The two expressions are equivalent, but the latter avoids multiplying the
> virtual lag by the total runqueue weight. entity_lag() bounds vlag against
> the entity's effective weight, so the remaining lag * weight product stays
> bounded. rescale_entity() preserves this scale across h_load changes and
> already relies on the same product when rescaling vlag.
> 
> Keep the original zero-load warning semantics by multiplying lag by weight
> after replacing the divisor with one.
> 
> Fixes: 4823725d9d1d ("sched/fair: Increase weight bits for avg_vruntime")
> Signed-off-by: Hui Su <sh_def@163.com>
> ---

Indeed so; however I've rewritten things like below. Hope that works for
you.

---
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 7455a83a6a99..6ce7233cd339 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -6266,12 +6266,20 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 		load = cfs_rq->sum_weight;
 		if (curr && curr->on_rq)
 			load += avg_vruntime_weight(cfs_rq, curr->h_load.weight);
-
-		weight = avg_vruntime_weight(cfs_rq, se->h_load.weight);
-		lag *= load + weight;
 		if (WARN_ON_ONCE(!load))
 			load = 1;
-		lag = div64_long(lag, load);
+
+		weight = avg_vruntime_weight(cfs_rq, se->h_load.weight);
+
+		/*
+		 * Rewrite, because the product (W + w_i)*vl'_i might
+		 * overflow s64:
+		 *
+		 *   vl_i = (W + w_i)*vl'_i / W
+		 *        = (W*vl'_i + w_i*vl'_i) / W
+		 *        = vl'_i + w_i*vl'_i/W
+		 */
+		lag += div64_long(lag * weight, load);
 
 		/*
 		 * A heavy entity (relative to the tree) will pull the

Re: [PATCH] sched/fair: Avoid overflow in place_entity()

[Hui Su]

> Indeed so; however I've rewritten things like below. Hope that works for
> you.
>
> ---
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 7455a83a6a99..6ce7233cd339 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -6266,12 +6266,20 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
> 		load = cfs_rq->sum_weight;
> 		if (curr && curr->on_rq)
> 			load += avg_vruntime_weight(cfs_rq, curr->h_load.weight);
> -
> -		weight = avg_vruntime_weight(cfs_rq, se->h_load.weight);
> -		lag *= load + weight;
> 		if (WARN_ON_ONCE(!load))
> 			load = 1;
> -		lag = div64_long(lag, load);
> +
> +		weight = avg_vruntime_weight(cfs_rq, se->h_load.weight);
> +
> +		/*
> +		 * Rewrite, because the product (W + w_i)*vl'_i might
> +		 * overflow s64:
> +		 *
> +		 *   vl_i = (W + w_i)*vl'_i / W
> +		 *        = (W*vl'_i + w_i*vl'_i) / W
> +		 *        = vl'_i + w_i*vl'_i/W
> +		 */
> +		lag += div64_long(lag * weight, load);
> 
> 		/*
> 		 * A heavy entity (relative to the tree) will pull the

Yes, this looks good to me for the normal path. One minor difference is the
`WARN_ON_ONCE(!load)` fallback: the old code produces `lag * weight`, while
this rewrite produces `lag * (weight + 1)` after setting `load` to one.
Since that should be an invariant-violation path, I don't think it matters
in practice.

Thanks for the rewrite.

Hui

[tip: sched/urgent] sched/fair: Avoid overflow in place_entity()

[tip-bot2 for Hui Su]

The following commit has been merged into the sched/urgent branch of tip:

Commit-ID:     2f93bcb3f9aaf6ceee1aec0a97d4fe386d48e781
Gitweb:        https://git.kernel.org/tip/2f93bcb3f9aaf6ceee1aec0a97d4fe386d48e781
Author:        Hui Su <sh_def@163.com>
AuthorDate:    Mon, 28 Sep 2026 21:47:54 +09:00
Committer:     Peter Zijlstra <peterz@infradead.org>
CommitterDate: Fri, 16 Oct 2026 09:49:00 +02:00

sched/fair: Avoid overflow in place_entity()

place_entity() inflates an entity's virtual lag with

    lag * (load + weight) / load

Commit 4823725d9d1d ("sched/fair: Increase weight bits for avg_vruntime")
replaced the scaled-down weights used in this calculation with
avg_vruntime_weight(), removing the arithmetic headroom provided by
scale_load_down().

The multiplication can overflow s64 before the division even when the
final quotient is representable. A task's hierarchical effective weight
can be as small as 2 after avg_vruntime_weight() scaling under group
scheduling, while entity_lag() bounds |vlag| by

    calc_delta_fair(cfs_rq_max_slice(cfs_rq) + TICK_NSEC, se)

For example, with HZ=1000, NICE_0_LOAD=1048576, and the minimum scaled
hierarchical weight scale_load(2)=2048, this bound is 891289600. With 114
maximum-weight entities, the runqueue load is 10361604096. The
intermediate product is:

    891289600 * (10361604096 + 2)
        = 9235189971864780800
        > S64_MAX

The signed overflow corrupts the entity's placement.

Rewrite

    lag * (load + weight) / load

as

    lag + lag * weight / load

The two expressions are equivalent, but the latter avoids multiplying the
virtual lag by the total runqueue weight. entity_lag() bounds vlag against
the entity's effective weight, so the remaining lag * weight product stays
bounded. rescale_entity() preserves this scale across h_load changes and
already relies on the same product when rescaling vlag.

Keep the original zero-load warning semantics by multiplying lag by weight
after replacing the divisor with one.

Fixes: 4823725d9d1d ("sched/fair: Increase weight bits for avg_vruntime")
Signed-off-by: Hui Su <sh_def@163.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Link: https://patch.msgid.link/20260928124754.1692077-1-sh_def@163.com
---
 kernel/sched/fair.c | 16 ++++++++++++----
 1 file changed, 12 insertions(+), 4 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 57360f5..0f23644 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -6463,12 +6463,20 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 		load = cfs_rq->sum_weight;
 		if (curr && curr->on_rq)
 			load += avg_vruntime_weight(cfs_rq, curr->h_load.weight);
-
-		weight = avg_vruntime_weight(cfs_rq, se->h_load.weight);
-		lag *= load + weight;
 		if (WARN_ON_ONCE(!load))
 			load = 1;
-		lag = div64_long(lag, load);
+
+		weight = avg_vruntime_weight(cfs_rq, se->h_load.weight);
+
+		/*
+		 * Rewrite, because the product (W + w_i)*vl'_i might
+		 * overflow s64:
+		 *
+		 *   vl_i = (W + w_i)*vl'_i / W
+		 *        = (W*vl'_i + w_i*vl'_i) / W
+		 *        = vl'_i + w_i*vl'_i/W
+		 */
+		lag += div64_long(lag * weight, load);
 
 		/*
 		 * A heavy entity (relative to the tree) will pull the