[PATCH 6.18] sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")

[PATCH 6.18] sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")

[John Stultz]

From: Peter Zijlstra <peterz@infradead.org>

[ Upstream commit 101f3498b4bdfef97152a444847948de1543f692 ]

Zicheng Qu reported that, because avg_vruntime() always includes
cfs_rq->curr, when ->on_rq, place_entity() doesn't work right.

Specifically, the lag scaling in place_entity() relies on
avg_vruntime() being the state *before* placement of the new entity.
However in this case avg_vruntime() will actually already include the
entity, which breaks things.

Also, Zicheng Qu argues that avg_vruntime should be invariant under
reweight. IOW commit 6d71a9c61604 ("sched/fair: Fix EEVDF entity
placement bug causing scheduling lag") was wrong!

The issue reported in 6d71a9c61604 could possibly be explained by
rounding artifacts -- notably the extreme weight '2' is outside of the
range of avg_vruntime/sum_w_vruntime, since that uses
scale_load_down(). By scaling vruntime by the real weight, but
accounting it in vruntime with a factor 1024 more, the average moves
significantly. However, that is now cured.

Tested by reverting 66951e4860d3 ("sched/fair: Fix update_cfs_group()
vs DELAY_DEQUEUE") and tracing vruntime and vlag figures again.

Reported-by: Zicheng Qu <quzicheng@huawei.com>
Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>
Reviewed-by: Vincent Guittot <vincent.guittot@linaro.org>
Tested-by: K Prateek Nayak <kprateek.nayak@amd.com>
Tested-by: Shubhang Kaushik <shubhang@os.amperecomputing.com>
Link: https://patch.msgid.link/20260219080625.066102672%40infradead.org
(cherry picked from commit 101f3498b4bdfef97152a444847948de1543f692)
[jstultz: Resolved minor collision in the revert against 6.18-stable]
Signed-off-by: John Stultz <jstultz@google.com>
---
Cc: Dietmar Eggemann <dietmar.eggemann@arm.com>
Cc: "Xuewen Yan" <xuewen.yan@unisoc.com>
Cc: William Montaz <willymontaz@gmail.com>
---
 kernel/sched/fair.c | 148 +++++++++++++++++++++++++++++++++++++-------
 1 file changed, 124 insertions(+), 24 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index d9777c81db0da..4279035367dbb 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -764,17 +764,22 @@ static inline u64 cfs_rq_max_slice(struct cfs_rq *cfs_rq);
  *
  *   -r_max < lag < max(r_max, q)
  */
-static void update_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se)
+static s64 entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se, u64 avruntime)
 {
 	u64 max_slice = cfs_rq_max_slice(cfs_rq) + TICK_NSEC;
 	s64 vlag, limit;
 
-	WARN_ON_ONCE(!se->on_rq);
-
-	vlag = avg_vruntime(cfs_rq) - se->vruntime;
+	vlag = avruntime - se->vruntime;
 	limit = calc_delta_fair(max_slice, se);
 
-	se->vlag = clamp(vlag, -limit, limit);
+	return clamp(vlag, -limit, limit);
+}
+
+static void update_entity_lag(struct cfs_rq *cfs_rq, struct sched_entity *se)
+{
+	WARN_ON_ONCE(!se->on_rq);
+
+	se->vlag = entity_lag(cfs_rq, se, avg_vruntime(cfs_rq));
 }
 
 /*
@@ -3831,23 +3836,125 @@ dequeue_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 					  cfs_rq->avg.load_avg * PELT_MIN_DIVIDER);
 }
 
-static void place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags);
+static void
+rescale_entity(struct sched_entity *se, unsigned long weight, bool rel_vprot)
+{
+	unsigned long old_weight = se->load.weight;
+
+	/*
+	 * VRUNTIME
+	 * --------
+	 *
+	 * COROLLARY #1: The virtual runtime of the entity needs to be
+	 * adjusted if re-weight at !0-lag point.
+	 *
+	 * Proof: For contradiction assume this is not true, so we can
+	 * re-weight without changing vruntime at !0-lag point.
+	 *
+	 *             Weight	VRuntime   Avg-VRuntime
+	 *     before    w          v            V
+	 *      after    w'         v'           V'
+	 *
+	 * Since lag needs to be preserved through re-weight:
+	 *
+	 *	lag = (V - v)*w = (V'- v')*w', where v = v'
+	 *	==>	V' = (V - v)*w/w' + v		(1)
+	 *
+	 * Let W be the total weight of the entities before reweight,
+	 * since V' is the new weighted average of entities:
+	 *
+	 *	V' = (WV + w'v - wv) / (W + w' - w)	(2)
+	 *
+	 * by using (1) & (2) we obtain:
+	 *
+	 *	(WV + w'v - wv) / (W + w' - w) = (V - v)*w/w' + v
+	 *	==> (WV-Wv+Wv+w'v-wv)/(W+w'-w) = (V - v)*w/w' + v
+	 *	==> (WV - Wv)/(W + w' - w) + v = (V - v)*w/w' + v
+	 *	==>	(V - v)*W/(W + w' - w) = (V - v)*w/w' (3)
+	 *
+	 * Since we are doing at !0-lag point which means V != v, we
+	 * can simplify (3):
+	 *
+	 *	==>	W / (W + w' - w) = w / w'
+	 *	==>	Ww' = Ww + ww' - ww
+	 *	==>	W * (w' - w) = w * (w' - w)
+	 *	==>	W = w	(re-weight indicates w' != w)
+	 *
+	 * So the cfs_rq contains only one entity, hence vruntime of
+	 * the entity @v should always equal to the cfs_rq's weighted
+	 * average vruntime @V, which means we will always re-weight
+	 * at 0-lag point, thus breach assumption. Proof completed.
+	 *
+	 *
+	 * COROLLARY #2: Re-weight does NOT affect weighted average
+	 * vruntime of all the entities.
+	 *
+	 * Proof: According to corollary #1, Eq. (1) should be:
+	 *
+	 *	(V - v)*w = (V' - v')*w'
+	 *	==>    v' = V' - (V - v)*w/w'		(4)
+	 *
+	 * According to the weighted average formula, we have:
+	 *
+	 *	V' = (WV - wv + w'v') / (W - w + w')
+	 *	   = (WV - wv + w'(V' - (V - v)w/w')) / (W - w + w')
+	 *	   = (WV - wv + w'V' - Vw + wv) / (W - w + w')
+	 *	   = (WV + w'V' - Vw) / (W - w + w')
+	 *
+	 *	==>  V'*(W - w + w') = WV + w'V' - Vw
+	 *	==>	V' * (W - w) = (W - w) * V	(5)
+	 *
+	 * If the entity is the only one in the cfs_rq, then reweight
+	 * always occurs at 0-lag point, so V won't change. Or else
+	 * there are other entities, hence W != w, then Eq. (5) turns
+	 * into V' = V. So V won't change in either case, proof done.
+	 *
+	 *
+	 * So according to corollary #1 & #2, the effect of re-weight
+	 * on vruntime should be:
+	 *
+	 *	v' = V' - (V - v) * w / w'		(4)
+	 *	   = V  - (V - v) * w / w'
+	 *	   = V  - vl * w / w'
+	 *	   = V  - vl'
+	 */
+	se->vlag = div64_long(se->vlag * old_weight, weight);
+
+	/*
+	 * DEADLINE
+	 * --------
+	 *
+	 * When the weight changes, the virtual time slope changes and
+	 * we should adjust the relative virtual deadline accordingly.
+	 *
+	 *	d' = v' + (d - v)*w/w'
+	 *	   = V' - (V - v)*w/w' + (d - v)*w/w'
+	 *	   = V  - (V - v)*w/w' + (d - v)*w/w'
+	 *	   = V  + (d - V)*w/w'
+	 */
+	if (se->rel_deadline)
+		se->deadline = div64_long(se->deadline * old_weight, weight);
+
+	if (rel_vprot)
+		se->vprot = div64_long(se->vprot * old_weight, weight);
+}
 
 static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
 			    unsigned long weight)
 {
 	bool curr = cfs_rq->curr == se;
 	bool rel_vprot = false;
-	u64 vprot;
+	u64 avruntime = 0;
 
 	if (se->on_rq) {
 		/* commit outstanding execution time */
 		update_curr(cfs_rq);
-		update_entity_lag(cfs_rq, se);
-		se->deadline -= se->vruntime;
+		avruntime = avg_vruntime(cfs_rq);
+		se->vlag = entity_lag(cfs_rq, se, avruntime);
+		se->deadline -= avruntime;
 		se->rel_deadline = 1;
 		if (curr && protect_slice(se)) {
-			vprot = se->vprot - se->vruntime;
+			se->vprot -= avruntime;
 			rel_vprot = true;
 		}
 
@@ -3858,30 +3965,23 @@ static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
 	}
 	dequeue_load_avg(cfs_rq, se);
 
-	/*
-	 * Because we keep se->vlag = V - v_i, while: lag_i = w_i*(V - v_i),
-	 * we need to scale se->vlag when w_i changes.
-	 */
-	se->vlag = div_s64(se->vlag * se->load.weight, weight);
-	if (se->rel_deadline)
-		se->deadline = div_s64(se->deadline * se->load.weight, weight);
-
-	if (rel_vprot)
-		vprot = div_s64(vprot * se->load.weight, weight);
+	rescale_entity(se, weight, rel_vprot);
 
 	update_load_set(&se->load, weight);
 
 	do {
 		u32 divider = get_pelt_divider(&se->avg);
-
 		se->avg.load_avg = div_u64(se_weight(se) * se->avg.load_sum, divider);
 	} while (0);
 
 	enqueue_load_avg(cfs_rq, se);
 	if (se->on_rq) {
-		place_entity(cfs_rq, se, 0);
 		if (rel_vprot)
-			se->vprot = se->vruntime + vprot;
+			se->vprot += avruntime;
+		se->deadline += avruntime;
+		se->rel_deadline = 0;
+		se->vruntime = avruntime - se->vlag;
+
 		update_load_add(&cfs_rq->load, se->load.weight);
 		if (!curr)
 			__enqueue_entity(cfs_rq, se);
@@ -5281,7 +5381,7 @@ place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 
 	se->vruntime = vruntime - lag;
 
-	if (se->rel_deadline) {
+	if (sched_feat(PLACE_REL_DEADLINE) && se->rel_deadline) {
 		se->deadline += se->vruntime;
 		se->rel_deadline = 0;
 		return;
-- 
2.54.0.rc1.513.gad8abe7a5a-goog

Re: [PATCH 6.18] sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")

[Jose Fernandez]

On Wed, Apr 15, 2026 at 09:10:53PM +0000, John Stultz wrote:
> From: Peter Zijlstra <peterz@infradead.org>
>
> [ Upstream commit 101f3498b4bdfef97152a444847948de1543f692 ]
>
[...]
> (cherry picked from commit 101f3498b4bdfef97152a444847948de1543f692)
> [jstultz: Resolved minor collision in the revert against 6.18-stable]
> Signed-off-by: John Stultz <jstultz@google.com>

We have been hitting this on 6.18.y in production. The setup is a
thread spinning on one CPU inside a cgroup that holds nearly all the
weight on that CPU. That cgroup's weight gets recalculated on almost
every tick, and the per-cpu kworker on the same CPU ends up runnable
but never picked for minutes to hours. We see it as workqueue lockup
reports and hung tasks stuck behind lru_add_drain_all().

I tested this patch on 6.18.44 in a 4 vCPU KVM guest with a reproducer
along the lines of William's script. Three spinners are pinned to three
CPUs inside a nested cgroup with a high cpu.weight, and some extra load
in the group keeps its weight changing. On plain 6.18.44 the kworkers
on those CPUs get stuck runnable but never picked, and their vruntime
stops moving. With this patch they run normally. Running the same load
with no cgroup does not starve anything on either kernel.

Peter said in April that this could go to 6.18 [1]. Janne Huttunen
posted the same backport last month [2] and Sasha is holding it for
Peter's ack on taking the revert without 4823725d9d1d [3]. This patch
and [2] differ only in div64_long() against div_s64().

Tested-by: Jose Fernandez (Anthropic) <jose.fernandez@linux.dev>

[1] https://lore.kernel.org/all/20260407134519.GH3738010@noisy.programming.kicks-ass.net/
[2] https://lore.kernel.org/stable/PAWPR07MB100712177EB29A65F4385E4C29ACF2@PAWPR07MB10071.eurprd07.prod.outlook.com/
[3] https://lore.kernel.org/stable/20260725192000.stable-0001@kernel.org/

Re: [PATCH 6.18] sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")

[Peter Zijlstra]

On Mon, Aug 10, 2026 at 01:44:25AM +0000, Jose Fernandez wrote:
> On Wed, Apr 15, 2026 at 09:10:53PM +0000, John Stultz wrote:
> > From: Peter Zijlstra <peterz@infradead.org>
> >
> > [ Upstream commit 101f3498b4bdfef97152a444847948de1543f692 ]
> >
> [...]
> > (cherry picked from commit 101f3498b4bdfef97152a444847948de1543f692)
> > [jstultz: Resolved minor collision in the revert against 6.18-stable]
> > Signed-off-by: John Stultz <jstultz@google.com>
> 
> We have been hitting this on 6.18.y in production. The setup is a
> thread spinning on one CPU inside a cgroup that holds nearly all the
> weight on that CPU. That cgroup's weight gets recalculated on almost
> every tick, and the per-cpu kworker on the same CPU ends up runnable
> but never picked for minutes to hours. We see it as workqueue lockup
> reports and hung tasks stuck behind lru_add_drain_all().
> 
> I tested this patch on 6.18.44 in a 4 vCPU KVM guest with a reproducer
> along the lines of William's script. Three spinners are pinned to three
> CPUs inside a nested cgroup with a high cpu.weight, and some extra load
> in the group keeps its weight changing. On plain 6.18.44 the kworkers
> on those CPUs get stuck runnable but never picked, and their vruntime
> stops moving. With this patch they run normally. Running the same load
> with no cgroup does not starve anything on either kernel.
> 
> Peter said in April that this could go to 6.18 [1]. Janne Huttunen
> posted the same backport last month [2] and Sasha is holding it for
> Peter's ack on taking the revert without 4823725d9d1d [3]. This patch
> and [2] differ only in div64_long() against div_s64().
> 
> Tested-by: Jose Fernandez (Anthropic) <jose.fernandez@linux.dev>
> 
> [1] https://lore.kernel.org/all/20260407134519.GH3738010@noisy.programming.kicks-ass.net/
> [2] https://lore.kernel.org/stable/PAWPR07MB100712177EB29A65F4385E4C29ACF2@PAWPR07MB10071.eurprd07.prod.outlook.com/
> [3] https://lore.kernel.org/stable/20260725192000.stable-0001@kernel.org/

Yeah, this should be fine without 4823725d9d1d.

Re: [PATCH 6.18] sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")

[Jose Fernandez (Anthropic)]

On Mon, Aug 10, 2026 at 09:38:30AM +0200, Peter Zijlstra wrote:
> Yeah, this should be fine without 4823725d9d1d.

One heads up, our review tooling caught this after I sent the
Tested-by. The revert was written after commit 80390ead2080
("sched/fair: Separate se->vlag from se->vprot") took vlag and vprot
out of their union, and 6.18 still has the union. Without that split
first, the rel_vprot path in the new reweight_entity() scales vlag
twice and curr's vruntime comes out wrong.

Re: [PATCH 6.18] sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")

[John Stultz]

On Mon, Aug 10, 2026 at 4:32 PM Jose Fernandez (Anthropic)
<jose.fernandez@linux.dev> wrote:
>
> On Mon, Aug 10, 2026 at 09:38:30AM +0200, Peter Zijlstra wrote:
> > Yeah, this should be fine without 4823725d9d1d.
>
> One heads up, our review tooling caught this after I sent the
> Tested-by. The revert was written after commit 80390ead2080
> ("sched/fair: Separate se->vlag from se->vprot") took vlag and vprot
> out of their union, and 6.18 still has the union. Without that split
> first, the rel_vprot path in the new reweight_entity() scales vlag
> twice and curr's vruntime comes out wrong.

Indeed! I was looking earlier today as I had some foggy memory of an
issue the backport caused in our android17-6.18 tree, but couldn't
find it right off!

Since we were KABI frozen in the android tree, we used the following
patch to work around it: https://r.android.com/4103883

But then reverted that and cherry-picked 80390ead2080 ("UPSTREAM:
sched/fair: Separate se->vlag from se->vprot") for the KABI thaw.

Thanks for noticing and reminding me of this!

thanks
-john

Re: [PATCH 6.18] sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")

[Sasha Levin]

> > Peter said in April that this could go to 6.18 [1]. Janne Huttunen
> > posted the same backport last month [2] and Sasha is holding it for
> > Peter's ack on taking the revert without 4823725d9d1d [3].
>
> Yeah, this should be fine without 4823725d9d1d.

Thanks, that was what I was waiting on. Queued John's version for 6.18.

-- 
Thanks,
Sasha

Re: [PATCH 6.18] sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")

[John Stultz]

On Mon, Aug 10, 2026 at 4:57 PM Sasha Levin <sashal@kernel.org> wrote:
>
> > > Peter said in April that this could go to 6.18 [1]. Janne Huttunen
> > > posted the same backport last month [2] and Sasha is holding it for
> > > Peter's ack on taking the revert without 4823725d9d1d [3].
> >
> > Yeah, this should be fine without 4823725d9d1d.
>
> Thanks, that was what I was waiting on. Queued John's version for 6.18.

Do note, as Jose pointed out you should probably take: 80390ead2080
("UPSTREAM: sched/fair: Separate se->vlag from se->vprot") as well
then (ideally prior to).

thanks
-john

Re: [PATCH 6.18] sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")

[Sasha Levin]

> Do note, as Jose pointed out you should probably take: 80390ead2080
> ("UPSTREAM: sched/fair: Separate se->vlag from se->vprot") as well
> then (ideally prior to).

Queued for 6.18, thanks - and thanks to Jose for catching it.

-- 
Thanks,
Sasha