Please backport 101f3498b4bd to 6.18.y

Please backport 101f3498b4bd to 6.18.y

[Janne Huttunen (Nokia)]

Please consider backporting this patch to 6.18.y:

101f3498b4bd sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")


Rationale:

After updating a bunch of servers to 6.18.y, we started experiencing
some scheduler related starvations. The servers each have a group of
very dedicated and isolated CPU cores, meaning that they normally
only run a single user space thread (in "system.slice"), they don't
process any interrupts and nohz_full is in effect. The thread is
SCHED_OTHER (nice -10) and it is almost always runnable consuming
all the available CPU time.

In some rare situations, for e.g. debugging or metrics collecting,
there might be also some other thread for a brief period of time on
such a core. This other thread is also SCHED_OTHER, but it is in
"user.slice". The affinity mask allows that thread to only run on
that specific core. Now whether this CPU sharing is intentional or
not is debatable, but I don't think it should cause the kind of
problem we have observed. What sometimes happens is that the thread
in "user.slice" gets starved for seconds, minutes, hours (seen),
maybe even days (I don't think we have seen that). During that
starvation even SIGKILL won't release the thread because it gets
no runtime and cannot complete processing the signal.

After staring at this way too long, I came up with these observations
and (not 100% proven) theory:

1. The vruntime of "user.slice" advances forward quite a bit and
   the corresponding thread gets pre-empted. The slice is now ready
   to run but ineligible due to its large vruntime compared to the
   "system.slice".

2. The vruntime of "system.slice" starts behaving in a strange
   "sawtooth" pattern where apparently update_curr() nudges it
   forward a few times (causing the upward slope of the sawtooth)
   until a reweight comes. The reweight then calls place_entity()
   with 'cfs_rq->curr == se == "system.slice"', which seems to mess
   up the vruntime. I don't claim to understand the math in there,
   but to me it looks like when 'cfs_rq->curr == se', the math
   includes the weight of it twice when calculating the lag
   preservation. Apparently this may negate most/all of the upward
   slope causing the downward drop of the sawtooth.

The overall trend of the vruntime over long period of time seems to
still be slightly upward, which means that eventually it does reach
a point where "user.slice" becomes eligible again, but due to the
vruntime constantly snapping back down, this can take extremely long
time. During all that time the "user.slice" is never picked by the
scheduler causing the starvation. Introducing even more threads to
"user.slice" of the affected core seems to somehow fix the math and
release the blockage, but it varies how many such treads are needed
(they hang too if they don't manage to fix it).

After coming up with this theory, I noticed that the scheduler in
7.1 was changed to not call the place_entity() the same way anymore.
With a trivial backport (I think there was some difference in the
division operation) of the patch mentioned at the beginning of this
mail on top of 6.18.y, we could not reproduce the starvation anymore.

Re: Please backport 101f3498b4bd to 6.18.y

[Sasha Levin]

> Please consider backporting this patch to 6.18.y:
>
> 101f3498b4bd sched/fair: Revert 6d71a9c61604 ("sched/fair: Fix EEVDF entity placement bug causing scheduling lag")

It doesn't backport cleanly. Could you please send a tested backport?

-- 
Thanks,
Sasha

Re: Please backport 101f3498b4bd to 6.18.y

[Janne Huttunen (Nokia)]

> It doesn't backport cleanly. Could you please send a tested backport?

My attempt at a backport is below. Apologies in advance if the mail
system mangles it. The only real diff between this and the original
should be the use use of div_s64 vs div64_long + maybe tiny bit of
patch context. I leave it to the real experts to say which divide is
correct, but at least this applies, seems to fix the issue and we
haven't observed it to cause any new problems. It has been running on
the affected servers a few weeks now. It must be admitted though that
if this would somehow for example make the CPU shares incorrect, we
wouldn't necessarily notice it. We just noticed when some operations
got totally stuck before this backport.


diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index 7e0e2044d840..6bf765c8b6c3 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));
 }
 
 /*
@@ -3838,23 +3843,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 = div_s64(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 = div_s64(se->deadline * old_weight, weight);
+
+	if (rel_vprot)
+		se->vprot = div_s64(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;
 		}
 
@@ -3865,30 +3972,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);
@@ -5288,7 +5388,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;

Re: Please backport 101f3498b4bd to 6.18.y

[Sasha Levin]

> My attempt at a backport is below. Apologies in advance if the mail
> system mangles it. The only real diff between this and the original
> should be the use use of div_s64 vs div64_long + maybe tiny bit of
> patch context.

Thanks for putting this together, and for the weeks of production
testing.

I'd like to hold this one until Peter can weigh in. Upstream the revert
was preceded by 4823725d9d1d ("sched/fair: Increase weight bits for
avg_vruntime"), which is what actually cured the underlying rounding
artifact that 6d71a9c61604 was working around. That prerequisite is part
of the larger v7.1 avg_vruntime rework and isn't practical to bring back
to 6.18. Reverting alone on 6.18 (which still uses the scale_load_down
avg_vruntime) theoretically re-exposes that artifact, so I'd rather not
queue a scheduler change like this without the author's ack.

Peter, does a standalone revert of 6d71a9c61604 look correct/safe for
6.18 without 4823725d9d1d?

-- 
Thanks,
Sasha