Skip to contentSkip to conversation

sched/fair: A bit of a cgroup/PELT overhaul

PATCH In review Peter Zijlstra 6 participants 57 messages Sep 1, 2017 – Dec 6, 2017 Scheduler

lore
Share & tools
lore

Peter Zijlstra

author maintainer
#0 lore raw

cover sched/fair: A bit of a cgroup/PELT overhaul

Hi all,

New this time is that Josef identified and fixed a problem he had with it. He also provided many compile fixes. Meanwhile I managed to reflow the patches so that the whole now looks like a normal patch series.

Other than that, it should still very much be what it was before.. From the previous announce:

---

So after staring at all that PELT stuff and working my way through it again:

https://lkml.kernel.org/r/[email protected]

I started doing some patches to fix some of the identified broken.

So here are a few too many patches that do:

- fix 'reweight_entity' to instantly propagate the change in se->load.weight.

- rewrite/fix the propagate on migrate (attach/detach)

- introduce the hierarchical runnable_load_avg, as proposed by Tejun.

- synchronous detach for runnable migrates

- aligns the PELT windows between a cfs_rq and all its se's

- deals with random fallout from the above (some of this needs folding back and reordering, but its all well past the point I should post this anyway).

IIRC pjt recently mentioned the reweight_entity thing, and I have very vague memories he once talked about the window alignment thing -- which I only remembered after (very painfully) having discovered I really needed that.

In any case, the reason I did the reweight_entity thing first, is because I feel that is the right place to also propagate the hierarchical runnable_load, as that is the natural place where a group's cfs_rq is coupled to its sched_entity.

And the hierachical runnable_load needs that coupling. TJ did it by hijacking the attach/detach migrate code, which I didn't much like. In any case, all that got me looking at said attach/detach migrate code and find pain. So I went and fixed that too.

---

Still very many thanks to Vincent, Dietmar and Josef for poking at these patches.

If nothing untowards happens, I plan to get them merged after the immenent merge window.

author maintainer
#1 lore raw

PATCH 1/18 sched/fair: Clean up calc_cfs_shares()

For consistencies sake, we should have only a single reading of tg->shares.

---
 kernel/sched/fair.c |   31 ++++++++++++-------------------
 1 file changed, 12 insertions(+), 19 deletions(-)
kernel/sched/fair.c +12 -19
@@ -2633,9 +2633,12 @@ account_entity_dequeue(struct cfs_rq *cf
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
 # ifdef CONFIG_SMP
-static long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
+static long calc_cfs_shares(struct cfs_rq *cfs_rq)
 {
-	long tg_weight, load, shares;
+	long tg_weight, tg_shares, load, shares;
+	struct task_group *tg = cfs_rq->tg;
+
+	tg_shares = READ_ONCE(tg->shares);
 
 	/*
 	 * This really should be: cfs_rq->avg.load_avg, but instead we use
@@ -2650,7 +2653,7 @@ static long calc_cfs_shares(struct cfs_r
 	tg_weight -= cfs_rq->tg_load_avg_contrib;
 	tg_weight += load;
 
-	shares = (tg->shares * load);
+	shares = (tg_shares * load);
 	if (tg_weight)
 		shares /= tg_weight;
 
@@ -2666,17 +2669,7 @@ static long calc_cfs_shares(struct cfs_r
 	 * case no task is runnable on a CPU MIN_SHARES=2 should be returned
 	 * instead of 0.
 	 */
-	if (shares < MIN_SHARES)
-		shares = MIN_SHARES;
-	if (shares > tg->shares)
-		shares = tg->shares;
-
-	return shares;
-}
-# else /* CONFIG_SMP */
-static inline long calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg)
-{
-	return tg->shares;
+	return clamp_t(long, shares, MIN_SHARES, tg_shares);
 }
 # endif /* CONFIG_SMP */
 
@@ -2701,7 +2694,6 @@ static inline int throttled_hierarchy(st
 static void update_cfs_shares(struct sched_entity *se)
 {
 	struct cfs_rq *cfs_rq = group_cfs_rq(se);
-	struct task_group *tg;
 	long shares;
 
 	if (!cfs_rq)
@@ -2710,13 +2702,14 @@ static void update_cfs_shares(struct sch
 	if (throttled_hierarchy(cfs_rq))
 		return;
 
-	tg = cfs_rq->tg;
-
 #ifndef CONFIG_SMP
-	if (likely(se->load.weight == tg->shares))
+	shares = READ_ONCE(cfs_rq->tg->shares);
+
+	if (likely(se->load.weight == shares))
 		return;
+#else
+	shares = calc_cfs_shares(cfs_rq);
 #endif
-	shares = calc_cfs_shares(cfs_rq, tg);
 
 	reweight_entity(cfs_rq_of(se), se, shares);
 }
author maintainer
#2 lore raw

PATCH 2/18 sched/fair: Add comment to calc_cfs_shares()

In reply to Peter Zijlstra

Explain the magic equation in calc_cfs_shares() a bit better.

---
 kernel/sched/fair.c |   61 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 61 insertions(+)
kernel/sched/fair.c +61 -0
@@ -2707,6 +2707,67 @@ account_entity_dequeue(struct cfs_rq *cf
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
 # ifdef CONFIG_SMP
+/*
+ * All this does is approximate the hierarchical proportion which includes that
+ * global sum we all love to hate.
+ *
+ * That is, the weight of a group entity, is the proportional share of the
+ * group weight based on the group runqueue weights. That is:
+ *
+ *                     tg->weight * grq->load.weight
+ *   ge->load.weight = -----------------------------               (1)
+ *			  \Sum grq->load.weight
+ *
+ * Now, because computing that sum is prohibitively expensive to compute (been
+ * there, done that) we approximate it with this average stuff. The average
+ * moves slower and therefore the approximation is cheaper and more stable.
+ *
+ * So instead of the above, we substitute:
+ *
+ *   grq->load.weight -> grq->avg.load_avg                         (2)
+ *
+ * which yields the following:
+ *
+ *                     tg->weight * grq->avg.load_avg
+ *   ge->load.weight = ------------------------------              (3)
+ *				tg->load_avg
+ *
+ * Where: tg->load_avg ~= \Sum grq->avg.load_avg
+ *
+ * That is shares_avg, and it is right (given the approximation (2)).
+ *
+ * The problem with it is that because the average is slow -- it was designed
+ * to be exactly that of course -- this leads to transients in boundary
+ * conditions. In specific, the case where the group was idle and we start the
+ * one task. It takes time for our CPU's grq->avg.load_avg to build up,
+ * yielding bad latency etc..
+ *
+ * Now, in that special case (1) reduces to:
+ *
+ *                     tg->weight * grq->load.weight
+ *   ge->load.weight = ----------------------------- = tg>weight   (4)
+ *			    grp->load.weight
+ *
+ * That is, the sum collapses because all other CPUs are idle; the UP scenario.
+ *
+ * So what we do is modify our approximation (3) to approach (4) in the (near)
+ * UP case, like:
+ *
+ *   ge->load.weight =
+ *
+ *              tg->weight * grq->load.weight
+ *     ---------------------------------------------------         (5)
+ *     tg->load_avg - grq->avg.load_avg + grq->load.weight
+ *
+ *
+ * And that is shares_weight and is icky. In the (near) UP case it approaches
+ * (4) while in the normal case it approaches (3). It consistently
+ * overestimates the ge->load.weight and therefore:
+ *
+ *   \Sum ge->load.weight >= tg->weight
+ *
+ * hence icky!
+ */
 static long calc_cfs_shares(struct cfs_rq *cfs_rq)
 {
 	long tg_weight, tg_shares, load, shares;
#3 lore raw

Re: [PATCH -v2 02/18] sched/fair: Add comment to calc_cfs_shares()

Quoted 43 lines · Peter Zijlstra

Explain the magic equation in calc_cfs_shares() a bit better.

---
 kernel/sched/fair.c |   61 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 61 insertions(+)
kernel/sched/fair.c +30 -0
@@ -2707,6 +2707,67 @@ account_entity_dequeue(struct cfs_rq *cf
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
 # ifdef CONFIG_SMP
+/*
+ * All this does is approximate the hierarchical proportion which includes that
+ * global sum we all love to hate.
+ *
+ * That is, the weight of a group entity, is the proportional share of the
+ * group weight based on the group runqueue weights. That is:
+ *
+ *                     tg->weight * grq->load.weight
+ *   ge->load.weight = -----------------------------               (1)
+ *			  \Sum grq->load.weight
+ *
+ * Now, because computing that sum is prohibitively expensive to compute (been
+ * there, done that) we approximate it with this average stuff. The average
+ * moves slower and therefore the approximation is cheaper and more stable.
+ *
+ * So instead of the above, we substitute:
+ *
+ *   grq->load.weight -> grq->avg.load_avg                         (2)
+ *
+ * which yields the following:
+ *
+ *                     tg->weight * grq->avg.load_avg
+ *   ge->load.weight = ------------------------------              (3)
+ *				tg->load_avg
+ *
+ * Where: tg->load_avg ~= \Sum grq->avg.load_avg
+ *
+ * That is shares_avg, and it is right (given the approximation (2)).
+ *
+ * The problem with it is that because the average is slow -- it was designed

kernel/sched/fair.c account_entity_dequeue(struct cfs_rq *cf · line 2749

Quoted 10 lines
kernel/sched/fair.c +10 -0
+ * to be exactly that of course -- this leads to transients in boundary
+ * conditions. In specific, the case where the group was idle and we start the
+ * one task. It takes time for our CPU's grq->avg.load_avg to build up,
+ * yielding bad latency etc..
+ *
+ * Now, in that special case (1) reduces to:
+ *
+ *                     tg->weight * grq->load.weight
+ *   ge->load.weight = ----------------------------- = tg>weight   (4)
+ *			    grp->load.weight

Should it be "grq->load.weight" in the denominator of (4)? And "tg->weight" at the end?

kernel/sched/fair.c account_entity_dequeue(struct cfs_rq *cf · line 2751

Quoted 2 lines
kernel/sched/fair.c +2 -0
+ *
+ * That is, the sum collapses because all other CPUs are idle; the UP scenario.

Shouldn't (3) collapse in the same way too in this special case? In theory it should reduce to:

                     tg->weight * grq->avg.load_avg
   ge->load.weight = ------------------------------
			grq->avg.load_avg

But I can see many reasons why it won't happen in practice if things aren't perfectly up-to-date. If tg->load_avg and grq->avg.load_avg in
(3) aren't in sync, or there are stale contributions to tg->load_avg from other cpus then (3) can return anything between 0 and tg->weight.

Quoted 8 lines
kernel/sched/fair.c +8 -0
+ *
+ * So what we do is modify our approximation (3) to approach (4) in the (near)
+ * UP case, like:
+ *
+ *   ge->load.weight =
+ *
+ *              tg->weight * grq->load.weight
+ *     ---------------------------------------------------         (5)

kernel/sched/fair.c account_entity_dequeue(struct cfs_rq *cf · line 2769

Quoted 10 lines
kernel/sched/fair.c +10 -0
+ *     tg->load_avg - grq->avg.load_avg + grq->load.weight
+ *
+ *
+ * And that is shares_weight and is icky. In the (near) UP case it approaches
+ * (4) while in the normal case it approaches (3). It consistently
+ * overestimates the ge->load.weight and therefore:
+ *
+ *   \Sum ge->load.weight >= tg->weight
+ *
+ * hence icky!

IIUC, if grq->avg.load_avg > grq->load.weight, i.e. you have blocked tasks, you can end up with underestimating the ge->load.weight for some of the group entities lead to \Sum ge->load.weight < tg->weight.

Let's take a simple example:

Two cpus, one task group with three tasks in it: An always-running task on both cpus, and an additional periodic task currently blocked on cpu 0 (contributing 512 to grq->avg.load_avg on cpu 0).

tg->weight = 1024
tg->load_avg = 2560
\Sum grq->load.weight = 2048

cpu 0 1 \Sum
grq->avg.load_avg 1536 1024
grq->load.weight 1024 1024
ge->load_weight (1) 512 512 1024 >= tg->weight
ge->load_weight (3) 614 410 1024 >= tg->weight
ge->load_weight (5) 512 410 922 < tg->weight

So with (5) we are missing 102 worth of ge->load.weight.

If (1), the instantaneous ge->load.weight, is what we want, then ge->load.weight of cpu 1 is underestimated, if (3), shares_avg, is the goal, then ge->load.weight of cpu 0 is underestimated.

The "missing" ge->load.weight can get much larger if the blocked task had higher priority.

Another thing is that we are loosing a bit of the nice stability that
(3) provides if you have periodic tasks.

I'm not sure if we can do better than (5), I'm just trying to understand how the approximation will behave and make sure we understand the implications.

Morten

author maintainer
#4 lore raw

Re: [PATCH -v2 02/18] sched/fair: Add comment to calc_cfs_shares()

Quoted 41 lines · Morten Rasmussen
Quoted 32 lines

+/*
+ * All this does is approximate the hierarchical proportion which includes that
+ * global sum we all love to hate.
+ *
+ * That is, the weight of a group entity, is the proportional share of the
+ * group weight based on the group runqueue weights. That is:
+ *
+ * tg->weight * grq->load.weight
+ * ge->load.weight = ----------------------------- (1)
+ * \Sum grq->load.weight
+ *
+ * Now, because computing that sum is prohibitively expensive to compute (been
+ * there, done that) we approximate it with this average stuff. The average
+ * moves slower and therefore the approximation is cheaper and more stable.
+ *
+ * So instead of the above, we substitute:
+ *
+ * grq->load.weight -> grq->avg.load_avg (2)
+ *
+ * which yields the following:
+ *
+ * tg->weight * grq->avg.load_avg
+ * ge->load.weight = ------------------------------ (3)
+ * tg->load_avg
+ *
+ * Where: tg->load_avg ~= \Sum grq->avg.load_avg
+ *
+ * That is shares_avg, and it is right (given the approximation (2)).
+ *
+ * The problem with it is that because the average is slow -- it was designed
+ * to be exactly that of course -- this leads to transients in boundary
+ * conditions. In specific, the case where the group was idle and we start the

Quoted 8 lines

+ * one task. It takes time for our CPU's grq->avg.load_avg to build up,
+ * yielding bad latency etc..
+ *
+ * Now, in that special case (1) reduces to:
+ *
+ * tg->weight * grq->load.weight
+ * ge->load.weight = ----------------------------- = tg>weight (4)
+ * grp->load.weight

Quoted 2 lines

Should it be "grq->load.weight" in the denominator of (4)? And "tg->weight" at the end?

Yes, otherwise its all doesn't really make sense :-) Typing is hard it seems.

Quoted 4 lines
Quoted 2 lines

+ *
+ * That is, the sum collapses because all other CPUs are idle; the UP scenario.

Shouldn't (3) collapse in the same way too in this special case?

That's more difficult to see and (1) is the canonical form.

Quoted 5 lines

In theory it should reduce to:

                     tg->weight * grq->avg.load_avg
   ge->load.weight = ------------------------------
			grq->avg.load_avg

Yes, agreed.

Quoted 4 lines

But I can see many reasons why it won't happen in practice if things aren't perfectly up-to-date. If tg->load_avg and grq->avg.load_avg in
(3) aren't in sync, or there are stale contributions to tg->load_avg from other cpus then (3) can return anything between 0 and tg->weight.

Just so.

Quoted 19 lines
Quoted 10 lines

+ *
+ * So what we do is modify our approximation (3) to approach (4) in the (near)
+ * UP case, like:
+ *
+ * ge->load.weight =
+ *
+ * tg->weight * grq->load.weight
+ * --------------------------------------------------- (5)
+ * tg->load_avg - grq->avg.load_avg + grq->load.weight
+ *

Quoted 8 lines

+ *
+ * And that is shares_weight and is icky. In the (near) UP case it approaches
+ * (4) while in the normal case it approaches (3). It consistently
+ * overestimates the ge->load.weight and therefore:
+ *
+ * \Sum ge->load.weight >= tg->weight
+ *
+ * hence icky!

Quoted 3 lines

IIUC, if grq->avg.load_avg > grq->load.weight, i.e. you have blocked tasks, you can end up with underestimating the ge->load.weight for some of the group entities lead to \Sum ge->load.weight < tg->weight.

Ah yes, you're right. However, if you look at the end of the series we actually end up with using:

	max(grq->load.weight, grq->avg.load_avg)

Which I suppose makes it true again.

#5 lore raw

Re: [PATCH -v2 02/18] sched/fair: Add comment to calc_cfs_shares()

Quoted 11 lines · Peter Zijlstra
Quoted 3 lines · Morten Rasmussen

IIUC, if grq->avg.load_avg > grq->load.weight, i.e. you have blocked tasks, you can end up with underestimating the ge->load.weight for some of the group entities lead to \Sum ge->load.weight < tg->weight.

Ah yes, you're right. However, if you look at the end of the series we actually end up with using:

	max(grq->load.weight, grq->avg.load_avg)

Which I suppose makes it true again.

Yes, with the next patch in the series, underestimation is no longer possible.

author maintainer
#6 lore raw

PATCH 3/18 sched/fair: Cure calc_cfs_shares() vs reweight_entity()

In reply to Peter Zijlstra

Vincent reported that when running in a cgroup, his root cfs_rq->avg.load_avg dropped to 0 on task idle.

This is because reweight_entity() will now immediately propagate the weight change of the group entity to its cfs_rq, and as it happens, our approxmation (5) for calc_cfs_shares() results in 0 when the group is idle.

Avoid this by using the correct (3) as a lower bound on (5). This way the empty cgroup will slowly decay instead of instantly drop to 0.

---
 kernel/sched/fair.c |    7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)
kernel/sched/fair.c +3 -4
@@ -2703,11 +2703,10 @@ static long calc_cfs_shares(struct cfs_r
 	tg_shares = READ_ONCE(tg->shares);
 
 	/*
-	 * This really should be: cfs_rq->avg.load_avg, but instead we use
-	 * cfs_rq->load.weight, which is its upper bound. This helps ramp up
-	 * the shares for small weight interactive tasks.
+	 * Because (5) drops to 0 when the cfs_rq is idle, we need to use (3)
+	 * as a lower bound.
 	 */
-	load = scale_load_down(cfs_rq->load.weight);
+	load = max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg);
 
 	tg_weight = atomic_long_read(&tg->load_avg);
 
#7 lore raw

Re: [PATCH -v2 03/18] sched/fair: Cure calc_cfs_shares() vs reweight_entity()

Quoted 21 lines · Peter Zijlstra

Vincent reported that when running in a cgroup, his root cfs_rq->avg.load_avg dropped to 0 on task idle.

This is because reweight_entity() will now immediately propagate the weight change of the group entity to its cfs_rq, and as it happens, our approxmation (5) for calc_cfs_shares() results in 0 when the group is idle.

Avoid this by using the correct (3) as a lower bound on (5). This way the empty cgroup will slowly decay instead of instantly drop to 0.

---
 kernel/sched/fair.c |    7 +++----
 1 file changed, 3 insertions(+), 4 deletions(-)
kernel/sched/fair.c +0 -0
@@ -2703,11 +2703,10 @@ static long calc_cfs_shares(struct cfs_r
 	tg_shares = READ_ONCE(tg->shares);

kernel/sched/fair.c static long calc_cfs_shares(struct cfs_r · line 2709

Quoted 10 lines
kernel/sched/fair.c +3 -4
 
 	/*
-	 * This really should be: cfs_rq->avg.load_avg, but instead we use
-	 * cfs_rq->load.weight, which is its upper bound. This helps ramp up
-	 * the shares for small weight interactive tasks.
+	 * Because (5) drops to 0 when the cfs_rq is idle, we need to use (3)
+	 * as a lower bound.
 	 */
-	load = scale_load_down(cfs_rq->load.weight);
+	load = max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg);

We use cfs_rq->tg_load_avg_contrib (the filtered version of cfs_rq->avg.load_avg) instead of cfs_rq->avg.load_avg further down, so I think we should here too for consistency.

+ load = max(scale_load_down(cfs_rq->load.weight),
+ cfs_rq->tg_load_avg_contrib);

With this change (5) almost becomes (3):

ge->load.weight =

                 tg->weight * max(grq->load.weight, grq->avg.load_avg)
     ---------------------------------------------------------------------------
     tg->load_avg - grq->avg.load_avg + max(grq->load.weight, grq->avg.load_avg)

The difference is that we boost ge->load.weight for if the grq has runnable tasks with se->avg.load_avg < se->load.weight, i.e. tasks that occasionally block. This means that the underestimate scenario I have in my reply for patch #2 is no longer possible. AFAICT, we are now guaranteed to over-estimate ge->load.weight. It is still quite sensitive to periodic high priority tasks though.

tg->weight              = 1024
tg->load_avg            = 2560
\Sum grq->load.weight   = 2048
cpu                     0       1       \Sum
grq->avg.load_avg       1536    1024
grq->load.weight        1024    1024
load (max)		1536	1024
ge->load_weight (1)     512     512     1024 >= tg->weight
ge->load_weight (3)     614     410     1024 >= tg->weight
ge->load_weight (5)     512     410     922 < tg->weight
ge->load_weight (5*)    614     410     1024 >= tg->weight
author maintainer
#8 lore raw

Re: [PATCH -v2 03/18] sched/fair: Cure calc_cfs_shares() vs reweight_entity()

Review

Quoted 10 lines · Morten Rasmussen

kernel/sched/fair.c static long calc_cfs_shares(struct cfs_r · line 2709

Quoted 2 lines
kernel/sched/fair.c +1 -1
-	load = scale_load_down(cfs_rq->load.weight);
+	load = max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg);

We use cfs_rq->tg_load_avg_contrib (the filtered version of cfs_rq->avg.load_avg) instead of cfs_rq->avg.load_avg further down, so I think we should here too for consistency.

(quoted diff) +2 -0
+	load = max(scale_load_down(cfs_rq->load.weight),
+		   cfs_rq->tg_load_avg_contrib);

No; we must use tg_load_avg_contrib because that is what's inclded in tg_weight, but we want to add the most up-to-date value back in.

#9 lore raw

Re: [PATCH -v2 03/18] sched/fair: Cure calc_cfs_shares() vs reweight_entity()

Quoted 9 lines · Peter Zijlstra
Quoted 7 lines · Morten Rasmussen

kernel/sched/fair.c static long calc_cfs_shares(struct cfs_r · line 2709

Quoted 2 lines
kernel/sched/fair.c +1 -1
-	load = scale_load_down(cfs_rq->load.weight);
+	load = max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg);

We use cfs_rq->tg_load_avg_contrib (the filtered version of cfs_rq->avg.load_avg) instead of cfs_rq->avg.load_avg further down, so I think we should here too for consistency.

Quoted 6 lines

Review

Quoted 3 lines
(quoted diff) +2 -0
+	load = max(scale_load_down(cfs_rq->load.weight),
+		   cfs_rq->tg_load_avg_contrib);

No; we must use tg_load_avg_contrib because that is what's inclded in tg_weight, but we want to add the most up-to-date value back in.

Agreed. Looking at it again it make sense.

author maintainer
#10 lore raw

PATCH 4/18 sched/fair: Remove se->load.weight from se->avg.load_sum

In reply to Peter Zijlstra

Remove the load from the load_sum for sched_entities, basically turning load_sum into runnable_sum. This prepares for better reweighting of group entities.

Since we now have different rules for computing load_avg, split ___update_load_avg() into two parts, ___update_load_sum() and ___update_load_avg().

So for se:

___update_load_sum(.weight = 1)
___upate_load_avg(.weight = se->load.weight)

and for cfs_rq:

___update_load_sum(.weight = cfs_rq->load.weight) ___upate_load_avg(.weight = 1)

Since the primary consumable is load_avg, most things will not be affected. Only those few sites that initialize/modify load_sum need attention.

---
 kernel/sched/fair.c |   91 ++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 64 insertions(+), 27 deletions(-)
kernel/sched/fair.c +64 -27
@@ -744,7 +744,7 @@ void init_entity_runnable_average(struct
 	 */
 	if (entity_is_task(se))
 		sa->load_avg = scale_load_down(se->load.weight);
-	sa->load_sum = sa->load_avg * LOAD_AVG_MAX;
+	sa->load_sum = LOAD_AVG_MAX;
 	/*
 	 * At this point, util_avg won't be used in select_task_rq_fair anyway
 	 */
@@ -1967,7 +1967,7 @@ static u64 numa_get_avg_runtime(struct t
 		delta = runtime - p->last_sum_exec_runtime;
 		*period = now - p->last_task_numa_placement;
 	} else {
-		delta = p->se.avg.load_sum / p->se.load.weight;
+		delta = p->se.avg.load_sum;
 		*period = LOAD_AVG_MAX;
 	}
 
@@ -2872,8 +2872,8 @@ accumulate_sum(u64 delta, int cpu, struc
  *            = u_0 + u_1*y + u_2*y^2 + ... [re-labeling u_i --> u_{i+1}]
  */
 static __always_inline int
-___update_load_avg(u64 now, int cpu, struct sched_avg *sa,
-		  unsigned long weight, int running, struct cfs_rq *cfs_rq)
+___update_load_sum(u64 now, int cpu, struct sched_avg *sa,
+		   unsigned long weight, int running, struct cfs_rq *cfs_rq)
 {
 	u64 delta;
 
@@ -2907,39 +2907,80 @@ ___update_load_avg(u64 now, int cpu, str
 	if (!accumulate_sum(delta, cpu, sa, weight, running, cfs_rq))
 		return 0;
 
+	return 1;
+}
+
+static __always_inline void
+___update_load_avg(struct sched_avg *sa, unsigned long weight, struct cfs_rq *cfs_rq)
+{
+	u32 divider = LOAD_AVG_MAX - 1024 + sa->period_contrib;
+
 	/*
 	 * Step 2: update *_avg.
 	 */
-	sa->load_avg = div_u64(sa->load_sum, LOAD_AVG_MAX - 1024 + sa->period_contrib);
+	sa->load_avg = div_u64(weight * sa->load_sum, divider);
 	if (cfs_rq) {
 		cfs_rq->runnable_load_avg =
-			div_u64(cfs_rq->runnable_load_sum, LOAD_AVG_MAX - 1024 + sa->period_contrib);
+			div_u64(cfs_rq->runnable_load_sum, divider);
 	}
-	sa->util_avg = sa->util_sum / (LOAD_AVG_MAX - 1024 + sa->period_contrib);
+	sa->util_avg = sa->util_sum / divider;
+}
 
-	return 1;
+/*
+ * XXX we want to get rid of this helper and use the full load resolution.
+ */
+static inline long se_weight(struct sched_entity *se)
+{
+	return scale_load_down(se->load.weight);
 }
 
+/*
+ * sched_entity:
+ *
+ *   load_sum := runnable_sum
+ *   load_avg = se_weight(se) * runnable_avg
+ *
+ * cfq_rs:
+ *
+ *   load_sum = \Sum se_weight(se) * se->avg.load_sum
+ *   load_avg = \Sum se->avg.load_avg
+ */
+
 static int
 __update_load_avg_blocked_se(u64 now, int cpu, struct sched_entity *se)
 {
-	return ___update_load_avg(now, cpu, &se->avg, 0, 0, NULL);
+	if (___update_load_sum(now, cpu, &se->avg, 0, 0, NULL)) {
+		___update_load_avg(&se->avg, se_weight(se), NULL);
+		return 1;
+	}
+
+	return 0;
 }
 
 static int
 __update_load_avg_se(u64 now, int cpu, struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
-	return ___update_load_avg(now, cpu, &se->avg,
-				  se->on_rq * scale_load_down(se->load.weight),
-				  cfs_rq->curr == se, NULL);
+	if (___update_load_sum(now, cpu, &se->avg, !!se->on_rq,
+				cfs_rq->curr == se, NULL)) {
+
+		___update_load_avg(&se->avg, se_weight(se), NULL);
+		return 1;
+	}
+
+	return 0;
 }
 
 static int
 __update_load_avg_cfs_rq(u64 now, int cpu, struct cfs_rq *cfs_rq)
 {
-	return ___update_load_avg(now, cpu, &cfs_rq->avg,
-			scale_load_down(cfs_rq->load.weight),
-			cfs_rq->curr != NULL, cfs_rq);
+	if (___update_load_sum(now, cpu, &cfs_rq->avg,
+				scale_load_down(cfs_rq->load.weight),
+				cfs_rq->curr != NULL, cfs_rq)) {
+		___update_load_avg(&cfs_rq->avg, 1, cfs_rq);
+		return 1;
+	}
+
+	return 0;
 }
 
 /*
@@ -3110,7 +3151,7 @@ update_tg_cfs_load(struct cfs_rq *cfs_rq
 
 	/* Set new sched_entity's load */
 	se->avg.load_avg = load;
-	se->avg.load_sum = se->avg.load_avg * LOAD_AVG_MAX;
+	se->avg.load_sum = LOAD_AVG_MAX;
 
 	/* Update parent cfs_rq load */
 	add_positive(&cfs_rq->avg.load_avg, delta);
@@ -3340,7 +3381,7 @@ static void attach_entity_load_avg(struc
 {
 	se->avg.last_update_time = cfs_rq->avg.last_update_time;
 	cfs_rq->avg.load_avg += se->avg.load_avg;
-	cfs_rq->avg.load_sum += se->avg.load_sum;
+	cfs_rq->avg.load_sum += se_weight(se) * se->avg.load_sum;
 	cfs_rq->avg.util_avg += se->avg.util_avg;
 	cfs_rq->avg.util_sum += se->avg.util_sum;
 	set_tg_cfs_propagate(cfs_rq);
@@ -3360,7 +3401,7 @@ static void detach_entity_load_avg(struc
 {
 
 	sub_positive(&cfs_rq->avg.load_avg, se->avg.load_avg);
-	sub_positive(&cfs_rq->avg.load_sum, se->avg.load_sum);
+	sub_positive(&cfs_rq->avg.load_sum, se_weight(se) * se->avg.load_sum);
 	sub_positive(&cfs_rq->avg.util_avg, se->avg.util_avg);
 	sub_positive(&cfs_rq->avg.util_sum, se->avg.util_sum);
 	set_tg_cfs_propagate(cfs_rq);
@@ -3372,12 +3413,10 @@ static void detach_entity_load_avg(struc
 static inline void
 enqueue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
-	struct sched_avg *sa = &se->avg;
-
-	cfs_rq->runnable_load_avg += sa->load_avg;
-	cfs_rq->runnable_load_sum += sa->load_sum;
+	cfs_rq->runnable_load_avg += se->avg.load_avg;
+	cfs_rq->runnable_load_sum += se_weight(se) * se->avg.load_sum;
 
-	if (!sa->last_update_time) {
+	if (!se->avg.last_update_time) {
 		attach_entity_load_avg(cfs_rq, se);
 		update_tg_load_avg(cfs_rq, 0);
 	}
@@ -3387,10 +3426,8 @@ enqueue_entity_load_avg(struct cfs_rq *c
 static inline void
 dequeue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
-	cfs_rq->runnable_load_avg =
-		max_t(long, cfs_rq->runnable_load_avg - se->avg.load_avg, 0);
-	cfs_rq->runnable_load_sum =
-		max_t(s64,  cfs_rq->runnable_load_sum - se->avg.load_sum, 0);
+	sub_positive(&cfs_rq->runnable_load_avg, se->avg.load_avg);
+	sub_positive(&cfs_rq->runnable_load_sum, se_weight(se) * se->avg.load_sum);
 }
 
 #ifndef CONFIG_64BIT
#11 lore raw

Re: [PATCH -v2 04/18] sched/fair: Remove se->load.weight from se->avg.load_sum

Quoted 7 lines · Peter Zijlstra

+/*
+ * sched_entity:
+ *
+ * load_sum := runnable_sum
+ * load_avg = se_weight(se) * runnable_avg
+ *
+ * cfq_rs:

I think this should be "cfs_rq" instead.

Quoted 4 lines

+ *
+ * load_sum = \Sum se_weight(se) * se->avg.load_sum
+ * load_avg = \Sum se->avg.load_avg
+ */

I find it a bit confusing that load_sum and load_avg have different definitions, but I guess I will discover why dropping weight from se->avg.load_sum helps a bit later. We can't do the same for cfs_rq as it is a \Sum of sums where we add/remove contributions when tasks migrate.

Have we defined the relation between runnable_sum and runnable_avg in a comment somewhere already? Otherwise it might be helpful to add. It is in the code of course :-)

author maintainer
#12 lore raw

Re: [PATCH -v2 04/18] sched/fair: Remove se->load.weight from se->avg.load_sum

Quoted 10 lines · Morten Rasmussen
Quoted 7 lines · Peter Zijlstra

+/*
+ * sched_entity:
+ *
+ * load_sum := runnable_sum
+ * load_avg = se_weight(se) * runnable_avg
+ *
+ * cfq_rs:

I think this should be "cfs_rq" instead.

Quite.

Quoted 8 lines
Quoted 4 lines

+ *
+ * load_sum = \Sum se_weight(se) * se->avg.load_sum
+ * load_avg = \Sum se->avg.load_avg
+ */

I find it a bit confusing that load_sum and load_avg have different definitions, but I guess I will discover why dropping weight from se->avg.load_sum helps a bit later.

It makes changing the weight cheaper, we don't have to divide the old weight out and then multiple by the new weight.

Up until this patch set, we mixed the old and new weight in the sum, with the result that a weight change takes a while to propagate.

But we want to change weight instantly. See:

sched/fair: More accurate reweight_entity()

Quoted 2 lines

We can't do the same for cfs_rq as it is a \Sum of sums where we add/remove contributions when tasks migrate.

Just so. The patch:

sched/fair: Rewrite PELT migration propagation

Has text on this:

+ * Because while for entities historical weight is not important and we
+ * really only care about our future and therefore can consider a pure
+ * runnable sum, runqueues can NOT do this.
+ *
+ * We specifically want runqueues to have a load_avg that includes
+ * historical weights. Those represent the blocked load, the load we expect
+ * to (shortly) return to us. This only works by keeping the weights as
+ * integral part of the sum. We therefore cannot decompose as per (3).

Quoted 3 lines

Have we defined the relation between runnable_sum and runnable_avg in a comment somewhere already? Otherwise it might be helpful to add. It is in the code of course :-)

I think this comment here is about it... But who knows. Please keep this as a note while you read the rest of the series. If you find its still insufficiently addressed at the end, I'm sure we can do another patch with moar comments still ;-)

author maintainer
#13 lore raw

PATCH 5/18 sched/fair: Change update_load_avg() arguments

In reply to Peter Zijlstra

Most call sites of update_load_avg() already have cfs_rq_of(se) available, pass it down instead of recomputing it.

---
 kernel/sched/fair.c |   31 +++++++++++++++----------------
 1 file changed, 15 insertions(+), 16 deletions(-)
kernel/sched/fair.c +15 -16
@@ -3498,9 +3498,8 @@ update_cfs_rq_load_avg(u64 now, struct c
 #define SKIP_AGE_LOAD	0x2
 
 /* Update task and its cfs_rq load average */
-static inline void update_load_avg(struct sched_entity *se, int flags)
+static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
 {
-	struct cfs_rq *cfs_rq = cfs_rq_of(se);
 	u64 now = cfs_rq_clock_task(cfs_rq);
 	struct rq *rq = rq_of(cfs_rq);
 	int cpu = cpu_of(rq);
@@ -3661,9 +3660,9 @@ update_cfs_rq_load_avg(u64 now, struct c
 #define UPDATE_TG	0x0
 #define SKIP_AGE_LOAD	0x0
 
-static inline void update_load_avg(struct sched_entity *se, int not_used1)
+static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int not_used1)
 {
-	cfs_rq_util_change(cfs_rq_of(se));
+	cfs_rq_util_change(cfs_rq);
 }
 
 static inline void
@@ -3814,7 +3813,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, st
 	 *     its group cfs_rq
 	 *   - Add its new weight to cfs_rq->load.weight
 	 */
-	update_load_avg(se, UPDATE_TG);
+	update_load_avg(cfs_rq, se, UPDATE_TG);
 	enqueue_entity_load_avg(cfs_rq, se);
 	update_cfs_shares(se);
 	account_entity_enqueue(cfs_rq, se);
@@ -3898,7 +3897,7 @@ dequeue_entity(struct cfs_rq *cfs_rq, st
 	 *   - For group entity, update its weight to reflect the new share
 	 *     of its group cfs_rq.
 	 */
-	update_load_avg(se, UPDATE_TG);
+	update_load_avg(cfs_rq, se, UPDATE_TG);
 	dequeue_entity_load_avg(cfs_rq, se);
 
 	update_stats_dequeue(cfs_rq, se, flags);
@@ -3986,7 +3985,7 @@ set_next_entity(struct cfs_rq *cfs_rq, s
 		 */
 		update_stats_wait_end(cfs_rq, se);
 		__dequeue_entity(cfs_rq, se);
-		update_load_avg(se, UPDATE_TG);
+		update_load_avg(cfs_rq, se, UPDATE_TG);
 	}
 
 	update_stats_curr_start(cfs_rq, se);
@@ -4088,7 +4087,7 @@ static void put_prev_entity(struct cfs_r
 		/* Put 'current' back into the tree. */
 		__enqueue_entity(cfs_rq, prev);
 		/* in !on_rq case, update occurred at dequeue */
-		update_load_avg(prev, 0);
+		update_load_avg(cfs_rq, prev, 0);
 	}
 	cfs_rq->curr = NULL;
 }
@@ -4104,7 +4103,7 @@ entity_tick(struct cfs_rq *cfs_rq, struc
 	/*
 	 * Ensure that runnable average is periodically updated.
 	 */
-	update_load_avg(curr, UPDATE_TG);
+	update_load_avg(cfs_rq, curr, UPDATE_TG);
 	update_cfs_shares(curr);
 
 #ifdef CONFIG_SCHED_HRTICK
@@ -5022,7 +5021,7 @@ enqueue_task_fair(struct rq *rq, struct
 		if (cfs_rq_throttled(cfs_rq))
 			break;
 
-		update_load_avg(se, UPDATE_TG);
+		update_load_avg(cfs_rq, se, UPDATE_TG);
 		update_cfs_shares(se);
 	}
 
@@ -5081,7 +5080,7 @@ static void dequeue_task_fair(struct rq
 		if (cfs_rq_throttled(cfs_rq))
 			break;
 
-		update_load_avg(se, UPDATE_TG);
+		update_load_avg(cfs_rq, se, UPDATE_TG);
 		update_cfs_shares(se);
 	}
 
@@ -7044,7 +7043,7 @@ static void update_blocked_averages(int
 		/* Propagate pending load changes to the parent, if any: */
 		se = cfs_rq->tg->se[cpu];
 		if (se && !skip_blocked_update(se))
-			update_load_avg(se, 0);
+			update_load_avg(cfs_rq_of(se), se, 0);
 
 		/*
 		 * There can be a lot of idle CPU cgroups.  Don't let fully
@@ -9185,7 +9184,7 @@ static void propagate_entity_cfs_rq(stru
 		if (cfs_rq_throttled(cfs_rq))
 			break;
 
-		update_load_avg(se, UPDATE_TG);
+		update_load_avg(cfs_rq, se, UPDATE_TG);
 	}
 }
 #else
@@ -9197,7 +9196,7 @@ static void detach_entity_cfs_rq(struct
 	struct cfs_rq *cfs_rq = cfs_rq_of(se);
 
 	/* Catch up with the cfs_rq and remove our load when we leave */
-	update_load_avg(se, 0);
+	update_load_avg(cfs_rq, se, 0);
 	detach_entity_load_avg(cfs_rq, se);
 	update_tg_load_avg(cfs_rq, false);
 	propagate_entity_cfs_rq(se);
@@ -9216,7 +9215,7 @@ static void attach_entity_cfs_rq(struct
 #endif
 
 	/* Synchronize entity with its cfs_rq */
-	update_load_avg(se, sched_feat(ATTACH_AGE_LOAD) ? 0 : SKIP_AGE_LOAD);
+	update_load_avg(cfs_rq, se, sched_feat(ATTACH_AGE_LOAD) ? 0 : SKIP_AGE_LOAD);
 	attach_entity_load_avg(cfs_rq, se);
 	update_tg_load_avg(cfs_rq, false);
 	propagate_entity_cfs_rq(se);
@@ -9500,7 +9499,7 @@ int sched_group_set_shares(struct task_g
 		rq_lock_irqsave(rq, &rf);
 		update_rq_clock(rq);
 		for_each_sched_entity(se) {
-			update_load_avg(se, UPDATE_TG);
+			update_load_avg(cfs_rq_of(se), se, UPDATE_TG);
 			update_cfs_shares(se);
 		}
 		rq_unlock_irqrestore(rq, &rf);
author maintainer
#14 lore raw

PATCH 6/18 sched/fair: Move enqueue migrate handling

In reply to Peter Zijlstra

Move the entity migrate handling from enqueue_entity_load_avg() to update_load_avg(). This has two benefits:

- {en,de}queue_entity_load_avg() will become purely about managing runnable_load

- we can avoid a double update_tg_load_avg() and reduce pressure on the global tg->shares cacheline

The reason we do this is so that we can change update_cfs_shares() to change both weight and (future) runnable_weight. For this to work we need to have the cfs_rq averages up-to-date (which means having done the attach), but we need the cfs_rq->avg.runnable_avg to not yet include the se's contribution (since se->on_rq == 0).

---
 kernel/sched/fair.c |   70 ++++++++++++++++++++++++++--------------------------
 1 file changed, 36 insertions(+), 34 deletions(-)
kernel/sched/fair.c +36 -34
@@ -3491,34 +3491,6 @@ update_cfs_rq_load_avg(u64 now, struct c
 	return decayed || removed_load;
 }
 
-/*
- * Optional action to be done while updating the load average
- */
-#define UPDATE_TG	0x1
-#define SKIP_AGE_LOAD	0x2
-
-/* Update task and its cfs_rq load average */
-static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
-{
-	u64 now = cfs_rq_clock_task(cfs_rq);
-	struct rq *rq = rq_of(cfs_rq);
-	int cpu = cpu_of(rq);
-	int decayed;
-
-	/*
-	 * Track task load average for carrying it to new CPU after migrated, and
-	 * track group sched_entity load average for task_h_load calc in migration
-	 */
-	if (se->avg.last_update_time && !(flags & SKIP_AGE_LOAD))
-		__update_load_avg_se(now, cpu, cfs_rq, se);
-
-	decayed  = update_cfs_rq_load_avg(now, cfs_rq);
-	decayed |= propagate_entity_load_avg(se);
-
-	if (decayed && (flags & UPDATE_TG))
-		update_tg_load_avg(cfs_rq, 0);
-}
-
 /**
  * attach_entity_load_avg - attach this entity to its cfs_rq load avg
  * @cfs_rq: cfs_rq to attach to
@@ -3559,17 +3531,46 @@ static void detach_entity_load_avg(struc
 	cfs_rq_util_change(cfs_rq);
 }
 
+/*
+ * Optional action to be done while updating the load average
+ */
+#define UPDATE_TG	0x1
+#define SKIP_AGE_LOAD	0x2
+#define DO_ATTACH	0x4
+
+/* Update task and its cfs_rq load average */
+static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int flags)
+{
+	u64 now = cfs_rq_clock_task(cfs_rq);
+	struct rq *rq = rq_of(cfs_rq);
+	int cpu = cpu_of(rq);
+	int decayed;
+
+	/*
+	 * Track task load average for carrying it to new CPU after migrated, and
+	 * track group sched_entity load average for task_h_load calc in migration
+	 */
+	if (se->avg.last_update_time && !(flags & SKIP_AGE_LOAD))
+		__update_load_avg_se(now, cpu, cfs_rq, se);
+
+	decayed  = update_cfs_rq_load_avg(now, cfs_rq);
+	decayed |= propagate_entity_load_avg(se);
+
+	if (!se->avg.last_update_time && (flags & DO_ATTACH)) {
+
+		attach_entity_load_avg(cfs_rq, se);
+		update_tg_load_avg(cfs_rq, 0);
+
+	} else if (decayed && (flags & UPDATE_TG))
+		update_tg_load_avg(cfs_rq, 0);
+}
+
 /* Add the load generated by se into cfs_rq's load average */
 static inline void
 enqueue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
 	cfs_rq->runnable_load_avg += se->avg.load_avg;
 	cfs_rq->runnable_load_sum += se_weight(se) * se->avg.load_sum;
-
-	if (!se->avg.last_update_time) {
-		attach_entity_load_avg(cfs_rq, se);
-		update_tg_load_avg(cfs_rq, 0);
-	}
 }
 
 /* Remove the runnable load generated by se from cfs_rq's runnable load average */
@@ -3659,6 +3660,7 @@ update_cfs_rq_load_avg(u64 now, struct c
 
 #define UPDATE_TG	0x0
 #define SKIP_AGE_LOAD	0x0
+#define DO_ATTACH	0x0
 
 static inline void update_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se, int not_used1)
 {
@@ -3813,7 +3815,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, st
 	 *     its group cfs_rq
 	 *   - Add its new weight to cfs_rq->load.weight
 	 */
-	update_load_avg(cfs_rq, se, UPDATE_TG);
+	update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH);
 	enqueue_entity_load_avg(cfs_rq, se);
 	update_cfs_shares(se);
 	account_entity_enqueue(cfs_rq, se);
author maintainer
#15 lore raw

PATCH 7/18 sched/fair: Rename {en,de}queue_entity_load_avg()

In reply to Peter Zijlstra

Since they're now purely about runnable_load, rename them.

---
 kernel/sched/fair.c |   12 ++++++------
 1 file changed, 6 insertions(+), 6 deletions(-)
kernel/sched/fair.c +6 -6
@@ -3561,7 +3561,7 @@ static inline void update_load_avg(struc
 
 /* Add the load generated by se into cfs_rq's load average */
 static inline void
-enqueue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
+enqueue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
 	cfs_rq->runnable_load_avg += se->avg.load_avg;
 	cfs_rq->runnable_load_sum += se_weight(se) * se->avg.load_sum;
@@ -3569,7 +3569,7 @@ enqueue_entity_load_avg(struct cfs_rq *c
 
 /* Remove the runnable load generated by se from cfs_rq's runnable load average */
 static inline void
-dequeue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
+dequeue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
 	sub_positive(&cfs_rq->runnable_load_avg, se->avg.load_avg);
 	sub_positive(&cfs_rq->runnable_load_sum, se_weight(se) * se->avg.load_sum);
@@ -3662,9 +3662,9 @@ static inline void update_load_avg(struc
 }
 
 static inline void
-enqueue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) {}
+enqueue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) {}
 static inline void
-dequeue_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) {}
+dequeue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) {}
 static inline void remove_entity_load_avg(struct sched_entity *se) {}
 
 static inline void
@@ -3810,7 +3810,7 @@ enqueue_entity(struct cfs_rq *cfs_rq, st
 	 *   - Add its new weight to cfs_rq->load.weight
 	 */
 	update_load_avg(cfs_rq, se, UPDATE_TG | DO_ATTACH);
-	enqueue_entity_load_avg(cfs_rq, se);
+	enqueue_runnable_load_avg(cfs_rq, se);
 	update_cfs_shares(se);
 	account_entity_enqueue(cfs_rq, se);
 
@@ -3894,7 +3894,7 @@ dequeue_entity(struct cfs_rq *cfs_rq, st
 	 *     of its group cfs_rq.
 	 */
 	update_load_avg(cfs_rq, se, UPDATE_TG);
-	dequeue_entity_load_avg(cfs_rq, se);
+	dequeue_runnable_load_avg(cfs_rq, se);
 
 	update_stats_dequeue(cfs_rq, se, flags);
 
author maintainer
#16 lore raw

PATCH 8/18 sched/fair: Introduce {en,de}queue_load_avg()

In reply to Peter Zijlstra

Analogous to the existing {en,de}queue_runnable_load_avg() add helpers for {en,de}queue_load_avg(). More users will follow.

Includes some code movement to avoid fwd declarations.

---
 kernel/sched/fair.c |  156 ++++++++++++++++++++++++++++------------------------
 1 file changed, 86 insertions(+), 70 deletions(-)
kernel/sched/fair.c +86 -70
@@ -2705,6 +2705,90 @@ account_entity_dequeue(struct cfs_rq *cf
 	cfs_rq->nr_running--;
 }
 
+/*
+ * Signed add and clamp on underflow.
+ *
+ * Explicitly do a load-store to ensure the intermediate value never hits
+ * memory. This allows lockless observations without ever seeing the negative
+ * values.
+ */
+#define add_positive(_ptr, _val) do {                           \
+	typeof(_ptr) ptr = (_ptr);                              \
+	typeof(_val) val = (_val);                              \
+	typeof(*ptr) res, var = READ_ONCE(*ptr);                \
+								\
+	res = var + val;                                        \
+								\
+	if (val < 0 && res > var)                               \
+		res = 0;                                        \
+								\
+	WRITE_ONCE(*ptr, res);                                  \
+} while (0)
+
+/*
+ * Unsigned subtract and clamp on underflow.
+ *
+ * Explicitly do a load-store to ensure the intermediate value never hits
+ * memory. This allows lockless observations without ever seeing the negative
+ * values.
+ */
+#define sub_positive(_ptr, _val) do {				\
+	typeof(_ptr) ptr = (_ptr);				\
+	typeof(*ptr) val = (_val);				\
+	typeof(*ptr) res, var = READ_ONCE(*ptr);		\
+	res = var - val;					\
+	if (res > var)						\
+		res = 0;					\
+	WRITE_ONCE(*ptr, res);					\
+} while (0)
+
+#ifdef CONFIG_SMP
+/*
+ * XXX we want to get rid of this helper and use the full load resolution.
+ */
+static inline long se_weight(struct sched_entity *se)
+{
+	return scale_load_down(se->load.weight);
+}
+
+static inline void
+enqueue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
+{
+	cfs_rq->runnable_load_avg += se->avg.load_avg;
+	cfs_rq->runnable_load_sum += se_weight(se) * se->avg.load_sum;
+}
+
+static inline void
+dequeue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
+{
+	sub_positive(&cfs_rq->runnable_load_avg, se->avg.load_avg);
+	sub_positive(&cfs_rq->runnable_load_sum, se_weight(se) * se->avg.load_sum);
+}
+
+static inline void
+enqueue_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
+{
+	cfs_rq->avg.load_avg += se->avg.load_avg;
+	cfs_rq->avg.load_sum += se_weight(se) * se->avg.load_sum;
+}
+
+static inline void
+dequeue_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
+{
+	sub_positive(&cfs_rq->avg.load_avg, se->avg.load_avg);
+	sub_positive(&cfs_rq->avg.load_sum, se_weight(se) * se->avg.load_sum);
+}
+#else
+static inline void
+enqueue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) { }
+static inline void
+dequeue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) { }
+static inline void
+enqueue_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) { }
+static inline void
+dequeue_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) { }
+#endif
+
 #ifdef CONFIG_FAIR_GROUP_SCHED
 # ifdef CONFIG_SMP
 /*
@@ -3097,14 +3181,6 @@ ___update_load_avg(struct sched_avg *sa,
 }
 
 /*
- * XXX we want to get rid of this helper and use the full load resolution.
- */
-static inline long se_weight(struct sched_entity *se)
-{
-	return scale_load_down(se->load.weight);
-}
-
-/*
  * sched_entity:
  *
  *   load_sum := runnable_sum
@@ -3153,26 +3229,6 @@ __update_load_avg_cfs_rq(u64 now, int cp
 	return 0;
 }
 
-/*
- * Signed add and clamp on underflow.
- *
- * Explicitly do a load-store to ensure the intermediate value never hits
- * memory. This allows lockless observations without ever seeing the negative
- * values.
- */
-#define add_positive(_ptr, _val) do {                           \
-	typeof(_ptr) ptr = (_ptr);                              \
-	typeof(_val) val = (_val);                              \
-	typeof(*ptr) res, var = READ_ONCE(*ptr);                \
-								\
-	res = var + val;                                        \
-								\
-	if (val < 0 && res > var)                               \
-		res = 0;                                        \
-								\
-	WRITE_ONCE(*ptr, res);                                  \
-} while (0)
-
 #ifdef CONFIG_FAIR_GROUP_SCHED
 /**
  * update_tg_load_avg - update the tg's load avg
@@ -3417,23 +3473,6 @@ static inline void set_tg_cfs_propagate(
 
 #endif /* CONFIG_FAIR_GROUP_SCHED */
 
-/*
- * Unsigned subtract and clamp on underflow.
- *
- * Explicitly do a load-store to ensure the intermediate value never hits
- * memory. This allows lockless observations without ever seeing the negative
- * values.
- */
-#define sub_positive(_ptr, _val) do {				\
-	typeof(_ptr) ptr = (_ptr);				\
-	typeof(*ptr) val = (_val);				\
-	typeof(*ptr) res, var = READ_ONCE(*ptr);		\
-	res = var - val;					\
-	if (res > var)						\
-		res = 0;					\
-	WRITE_ONCE(*ptr, res);					\
-} while (0)
-
 /**
  * update_cfs_rq_load_avg - update the cfs_rq's load/util averages
  * @now: current time, as per cfs_rq_clock_task()
@@ -3496,8 +3535,7 @@ update_cfs_rq_load_avg(u64 now, struct c
 static void attach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
 	se->avg.last_update_time = cfs_rq->avg.last_update_time;
-	cfs_rq->avg.load_avg += se->avg.load_avg;
-	cfs_rq->avg.load_sum += se_weight(se) * se->avg.load_sum;
+	enqueue_load_avg(cfs_rq, se);
 	cfs_rq->avg.util_avg += se->avg.util_avg;
 	cfs_rq->avg.util_sum += se->avg.util_sum;
 	set_tg_cfs_propagate(cfs_rq);
@@ -3515,9 +3553,7 @@ static void attach_entity_load_avg(struc
  */
 static void detach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
-
-	sub_positive(&cfs_rq->avg.load_avg, se->avg.load_avg);
-	sub_positive(&cfs_rq->avg.load_sum, se_weight(se) * se->avg.load_sum);
+	dequeue_load_avg(cfs_rq, se);
 	sub_positive(&cfs_rq->avg.util_avg, se->avg.util_avg);
 	sub_positive(&cfs_rq->avg.util_sum, se->avg.util_sum);
 	set_tg_cfs_propagate(cfs_rq);
@@ -3559,22 +3595,6 @@ static inline void update_load_avg(struc
 		update_tg_load_avg(cfs_rq, 0);
 }
 
-/* Add the load generated by se into cfs_rq's load average */
-static inline void
-enqueue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
-{
-	cfs_rq->runnable_load_avg += se->avg.load_avg;
-	cfs_rq->runnable_load_sum += se_weight(se) * se->avg.load_sum;
-}
-
-/* Remove the runnable load generated by se from cfs_rq's runnable load average */
-static inline void
-dequeue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
-{
-	sub_positive(&cfs_rq->runnable_load_avg, se->avg.load_avg);
-	sub_positive(&cfs_rq->runnable_load_sum, se_weight(se) * se->avg.load_sum);
-}
-
 #ifndef CONFIG_64BIT
 static inline u64 cfs_rq_last_update_time(struct cfs_rq *cfs_rq)
 {
@@ -3661,10 +3681,6 @@ static inline void update_load_avg(struc
 	cfs_rq_util_change(cfs_rq);
 }
 
-static inline void
-enqueue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) {}
-static inline void
-dequeue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) {}
 static inline void remove_entity_load_avg(struct sched_entity *se) {}
 
 static inline void
author maintainer
#17 lore raw

PATCH 9/18 sched/fair: More accurate reweight_entity()

In reply to Peter Zijlstra

When a (group) entity changes it's weight we should instantly change its load_avg and propagate that change into the sums it is part of. Because we use these values to predict future behaviour and are not interested in its historical value.

Without this change, the change in load would need to propagate through the average, by which time it could again have changed etc.. always chasing itself.

With this change, the cfs_rq load_avg sum will more accurately reflect the current runnable and expected return of blocked load.

[josef: compile fix !SMP || !FAIR_GROUP]
---
 kernel/sched/fair.c |   12 +++++++++++-
 1 file changed, 11 insertions(+), 1 deletion(-)
kernel/sched/fair.c +11 -1
@@ -2900,12 +2900,22 @@ static void reweight_entity(struct cfs_r
 		if (cfs_rq->curr == se)
 			update_curr(cfs_rq);
 		account_entity_dequeue(cfs_rq, se);
+		dequeue_runnable_load_avg(cfs_rq, se);
 	}
+	dequeue_load_avg(cfs_rq, se);
 
 	update_load_set(&se->load, weight);
 
-	if (se->on_rq)
+#ifdef CONFIG_SMP
+	se->avg.load_avg = div_u64(se_weight(se) * se->avg.load_sum,
+				   LOAD_AVG_MAX - 1024 + se->avg.period_contrib);
+#endif
+
+	enqueue_load_avg(cfs_rq, se);
+	if (se->on_rq) {
 		account_entity_enqueue(cfs_rq, se);
+		enqueue_runnable_load_avg(cfs_rq, se);
+	}
 }
 
 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq);
author maintainer
#18 lore raw

PATCH 10/18 sched/fair: Use reweight_entity() for set_user_nice()

In reply to Peter Zijlstra

From: Vincent Guittot <[email protected]>

Now that we directly change load_avg and propagate that change into the sums, sys_nice() and co should do the same, otherwise its possible to confuse load accounting when we migrate near the weight change.

[peterz: Changelog, call condition]
[josef: fixed runnable and !SMP compilation]
---
 kernel/sched/core.c  |   22 ++++++++++++-----
 kernel/sched/fair.c  |   63 +++++++++++++++++++++++++++++----------------------
 kernel/sched/sched.h |    2 +
 3 files changed, 54 insertions(+), 33 deletions(-)
kernel/sched/core.c +15 -7
@@ -733,7 +733,7 @@ int tg_nop(struct task_group *tg, void *
 }
 #endif
 
-static void set_load_weight(struct task_struct *p)
+static void set_load_weight(struct task_struct *p, bool update_load)
 {
 	int prio = p->static_prio - MAX_RT_PRIO;
 	struct load_weight *load = &p->se.load;
@@ -747,8 +747,16 @@ static void set_load_weight(struct task_
 		return;
 	}
 
-	load->weight = scale_load(sched_prio_to_weight[prio]);
-	load->inv_weight = sched_prio_to_wmult[prio];
+	/*
+	 * SCHED_OTHER tasks have to update their load when changing their
+	 * weight
+	 */
+	if (update_load && p->sched_class == &fair_sched_class) {
+		reweight_task(p, prio);
+	} else {
+		load->weight = scale_load(sched_prio_to_weight[prio]);
+		load->inv_weight = sched_prio_to_wmult[prio];
+	}
 }
 
 static inline void enqueue_task(struct rq *rq, struct task_struct *p, int flags)
@@ -2356,7 +2364,7 @@ int sched_fork(unsigned long clone_flags
 			p->static_prio = NICE_TO_PRIO(0);
 
 		p->prio = p->normal_prio = __normal_prio(p);
-		set_load_weight(p);
+		set_load_weight(p, false);
 
 		/*
 		 * We don't need the reset flag anymore after the fork. It has
@@ -3803,7 +3811,7 @@ void set_user_nice(struct task_struct *p
 		put_prev_task(rq, p);
 
 	p->static_prio = NICE_TO_PRIO(nice);
-	set_load_weight(p);
+	set_load_weight(p, true);
 	old_prio = p->prio;
 	p->prio = effective_prio(p);
 	delta = p->prio - old_prio;
@@ -3960,7 +3968,7 @@ static void __setscheduler_params(struct
 	 */
 	p->rt_priority = attr->sched_priority;
 	p->normal_prio = normal_prio(p);
-	set_load_weight(p);
+	set_load_weight(p, true);
 }
 
 /* Actually do priority change: must hold pi & rq lock. */
@@ -5910,7 +5918,7 @@ void __init sched_init(void)
 		atomic_set(&rq->nr_iowait, 0);
 	}
 
-	set_load_weight(&init_task);
+	set_load_weight(&init_task, false);
 
 	/*
 	 * The boot idle thread does lazy MMU switching as well:
kernel/sched/fair.c +37 -26

75 lines not on this page · raw message

kernel/sched/sched.h +2 -0
@@ -1532,6 +1532,8 @@ extern void init_sched_dl_class(void);
 extern void init_sched_rt_class(void);
 extern void init_sched_fair_class(void);
 
+extern void reweight_task(struct task_struct *p, int prio);
+
 extern void resched_curr(struct rq *rq);
 extern void resched_cpu(int cpu);
 
author maintainer
#19 lore raw

PATCH 11/18 sched/fair: Rewrite cfs_rq->removed_*avg

In reply to Peter Zijlstra

Since on wakeup migration we don't hold the rq->lock for the old CPU we cannot update its state. Instead we add the removed 'load' to an atomic variable and have the next update on that CPU collect and process it.

Currently we have 2 atomic variables; which already have the issue that they can be read out-of-sync. Also, two atomic ops on a single cacheline is already more expensive than an uncontended lock.

Since we want to add more, convert the thing over to an explicit cacheline with a lock in.

---
 kernel/sched/debug.c |    8 ++++----
 kernel/sched/fair.c  |   51 +++++++++++++++++++++++++++++++++++----------------
 kernel/sched/sched.h |   13 +++++++++----
 3 files changed, 48 insertions(+), 24 deletions(-)
kernel/sched/debug.c +4 -4
@@ -519,10 +519,10 @@ void print_cfs_rq(struct seq_file *m, in
 			cfs_rq->runnable_load_avg);
 	SEQ_printf(m, "  .%-30s: %lu\n", "util_avg",
 			cfs_rq->avg.util_avg);
-	SEQ_printf(m, "  .%-30s: %ld\n", "removed_load_avg",
-			atomic_long_read(&cfs_rq->removed_load_avg));
-	SEQ_printf(m, "  .%-30s: %ld\n", "removed_util_avg",
-			atomic_long_read(&cfs_rq->removed_util_avg));
+	SEQ_printf(m, "  .%-30s: %ld\n", "removed.load_avg",
+			cfs_rq->removed.load_avg);
+	SEQ_printf(m, "  .%-30s: %ld\n", "removed.util_avg",
+			cfs_rq->removed.util_avg);
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	SEQ_printf(m, "  .%-30s: %lu\n", "tg_load_avg_contrib",
 			cfs_rq->tg_load_avg_contrib);
kernel/sched/fair.c +35 -16

96 lines not on this page · raw message

kernel/sched/sched.h +9 -4
@@ -446,14 +446,19 @@ struct cfs_rq {
 	struct sched_avg avg;
 	u64 runnable_load_sum;
 	unsigned long runnable_load_avg;
+#ifndef CONFIG_64BIT
+	u64 load_last_update_time_copy;
+#endif
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	unsigned long tg_load_avg_contrib;
 	unsigned long propagate_avg;
 #endif
-	atomic_long_t removed_load_avg, removed_util_avg;
-#ifndef CONFIG_64BIT
-	u64 load_last_update_time_copy;
-#endif
+	struct {
+		raw_spinlock_t	lock ____cacheline_aligned;
+		int		nr;
+		unsigned long	load_avg;
+		unsigned long	util_avg;
+	} removed;
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	/*
author maintainer
#20 lore raw

PATCH 12/18 sched/fair: Rewrite PELT migration propagation

In reply to Peter Zijlstra

When an entity migrates in (or out) of a runqueue, we need to add (or remove) its contribution from the entire PELT hierarchy, because even non-runnable entities are included in the load average sums.

In order to do this we have some propagation logic that updates the PELT tree, however the way it 'propagates' the runnable (or load) change is (more or less):

                     tg->weight * grq->avg.load_avg
  ge->avg.load_avg = ------------------------------
                               tg->load_avg

But that is the expression for ge->weight, and per the definition of load_avg:

ge->avg.load_avg := ge->weight * ge->avg.runnable_avg

That destroys the runnable_avg (by setting it to 1) we wanted to propagate.

Instead directly propagate runnable_sum.

---
 kernel/sched/debug.c |    2 
 kernel/sched/fair.c  |  186 ++++++++++++++++++++++++++++-----------------------
 kernel/sched/sched.h |    9 +-
 3 files changed, 112 insertions(+), 85 deletions(-)
kernel/sched/debug.c +2 -0
@@ -565,6 +565,8 @@ void print_cfs_rq(struct seq_file *m, in
 			cfs_rq->removed.load_avg);
 	SEQ_printf(m, "  .%-30s: %ld\n", "removed.util_avg",
 			cfs_rq->removed.util_avg);
+	SEQ_printf(m, "  .%-30s: %ld\n", "removed.runnable_sum",
+			cfs_rq->removed.runnable_sum);
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	SEQ_printf(m, "  .%-30s: %lu\n", "tg_load_avg_contrib",
 			cfs_rq->tg_load_avg_contrib);
kernel/sched/fair.c +105 -81

281 lines not on this page · raw message

kernel/sched/sched.h +5 -4
@@ -449,18 +449,19 @@ struct cfs_rq {
 #ifndef CONFIG_64BIT
 	u64 load_last_update_time_copy;
 #endif
-#ifdef CONFIG_FAIR_GROUP_SCHED
-	unsigned long tg_load_avg_contrib;
-	unsigned long propagate_avg;
-#endif
 	struct {
 		raw_spinlock_t	lock ____cacheline_aligned;
 		int		nr;
 		unsigned long	load_avg;
 		unsigned long	util_avg;
+		unsigned long	runnable_sum;
 	} removed;
 
 #ifdef CONFIG_FAIR_GROUP_SCHED
+	unsigned long tg_load_avg_contrib;
+	long propagate;
+	long prop_runnable_sum;
+
 	/*
 	 *   h_load = weight * f(tg)
 	 *
#21 lore raw

Re: [PATCH -v2 12/18] sched/fair: Rewrite PELT migration propagation

Quoted 8 lines · Peter Zijlstra

When an entity migrates in (or out) of a runqueue, we need to add (or remove) its contribution from the entire PELT hierarchy, because even non-runnable entities are included in the load average sums.

In order to do this we have some propagation logic that updates the PELT tree, however the way it 'propagates' the runnable (or load) change is (more or less):

Quoted 8 lines
                     tg->weight * grq->avg.load_avg
  ge->avg.load_avg = ------------------------------
                               tg->load_avg

But that is the expression for ge->weight, and per the definition of load_avg:

ge->avg.load_avg := ge->weight * ge->avg.runnable_avg

You may want to replace "ge->weight" by "ge->load.weight" to be consistent with the code comments introduced by the patch.

Quoted 43 lines

That destroys the runnable_avg (by setting it to 1) we wanted to propagate.

Instead directly propagate runnable_sum.

---
 kernel/sched/debug.c |    2 
 kernel/sched/fair.c  |  186 ++++++++++++++++++++++++++++-----------------------
 kernel/sched/sched.h |    9 +-
 3 files changed, 112 insertions(+), 85 deletions(-)
kernel/sched/debug.c +2 -0
@@ -565,6 +565,8 @@ void print_cfs_rq(struct seq_file *m, in
 			cfs_rq->removed.load_avg);
 	SEQ_printf(m, "  .%-30s: %ld\n", "removed.util_avg",
 			cfs_rq->removed.util_avg);
+	SEQ_printf(m, "  .%-30s: %ld\n", "removed.runnable_sum",
+			cfs_rq->removed.runnable_sum);
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	SEQ_printf(m, "  .%-30s: %lu\n", "tg_load_avg_contrib",
 			cfs_rq->tg_load_avg_contrib);
kernel/sched/fair.c +13 -1
@@ -3330,11 +3330,77 @@ void set_task_rq_fair(struct sched_entit
 	se->avg.last_update_time = n_last_update_time;
 }
 
-/* Take into account change of utilization of a child task group */
+
+/*
+ * When on migration a sched_entity joins/leaves the PELT hierarchy, we need to
+ * propagate its contribution. The key to this propagation is the invariant
+ * that for each group:
+ *
+ *   ge->avg == grq->avg						(1)
+ *
+ * _IFF_ we look at the pure running and runnable sums. Because they
+ * represent the very same entity, just at different points in the hierarchy.
+ *
+ *
+ * Per the above update_tg_cfs_util() is trivial (and still 'wrong') and

kernel/sched/fair.c void set_task_rq_fair(struct sched_entit · line 3355

Quoted 10 lines
kernel/sched/fair.c +10 -0
+ * simply copies the running sum over.
+ *
+ * However, update_tg_cfs_runnable() is more complex. So we have:
+ *
+ *   ge->avg.load_avg = ge->load.weight * ge->avg.runnable_avg		(2)
+ *
+ * And since, like util, the runnable part should be directly transferable,
+ * the following would _appear_ to be the straight forward approach:
+ *
+ *   grq->avg.load_avg = grq->load.weight * grq->avg.running_avg	(3)

Should it be grq->avg.runnable_avg instead of running_avg?

cfs_rq->avg.load_avg has been defined previous (in patch 2 I think) to be:

	load_avg = \Sum se->avg.load_avg
		 = \Sum se->load.weight * se->avg.runnable_avg

That sum will increase when ge is runnable regardless of whether it is running or not. So, I think it has to be runnable_avg to make sense?

kernel/sched/fair.c void set_task_rq_fair(struct sched_entit · line 3359

Quoted 4 lines
kernel/sched/fair.c +4 -0
+ *
+ * And per (1) we have:
+ *
+ *   ge->avg.running_avg == grq->avg.running_avg

You just said further up that (1) only applies to running and runnable sums? These are averages, so I think this is invalid use of (1). But maybe that is part of your point about (4) being wrong?

I'm still trying to get my head around the remaining bits, but it sort of depends if I understood the above bits correctly :)

Morten

Quoted 41 lines
kernel/sched/fair.c +41 -0
+ *
+ * Which gives:
+ *
+ *                      ge->load.weight * grq->avg.load_avg
+ *   ge->avg.load_avg = -----------------------------------		(4)
+ *                               grq->load.weight
+ *
+ * Except that is wrong!
+ *
+ * Because while for entities historical weight is not important and we
+ * really only care about our future and therefore can consider a pure
+ * runnable sum, runqueues can NOT do this.
+ *
+ * We specifically want runqueues to have a load_avg that includes
+ * historical weights. Those represent the blocked load, the load we expect
+ * to (shortly) return to us. This only works by keeping the weights as
+ * integral part of the sum. We therefore cannot decompose as per (3).
+ *
+ * OK, so what then?
+ *
+ *
+ * Another way to look at things is:
+ *
+ *   grq->avg.load_avg = \Sum se->avg.load_avg
+ *
+ * Therefore, per (2):
+ *
+ *   grq->avg.load_avg = \Sum se->load.weight * se->avg.runnable_avg
+ *
+ * And the very thing we're propagating is a change in that sum (someone
+ * joined/left). So we can easily know the runnable change, which would be, per
+ * (2) the already tracked se->load_avg divided by the corresponding
+ * se->weight.
+ *
+ * Basically (4) but in differential form:
+ *
+ *   d(runnable_avg) += se->avg.load_avg / se->load.weight
+ *								   (5)
+ *   ge->avg.load_avg += ge->load.weight * d(runnable_avg)
+ */
+
author maintainer
#22 lore raw

Re: [PATCH -v2 12/18] sched/fair: Rewrite PELT migration propagation

Quoted 35 lines · Morten Rasmussen
Quoted 35 lines
kernel/sched/debug.c +2 -0
@@ -565,6 +565,8 @@ void print_cfs_rq(struct seq_file *m, in
 			cfs_rq->removed.load_avg);
 	SEQ_printf(m, "  .%-30s: %ld\n", "removed.util_avg",
 			cfs_rq->removed.util_avg);
+	SEQ_printf(m, "  .%-30s: %ld\n", "removed.runnable_sum",
+			cfs_rq->removed.runnable_sum);
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	SEQ_printf(m, "  .%-30s: %lu\n", "tg_load_avg_contrib",
 			cfs_rq->tg_load_avg_contrib);
kernel/sched/fair.c +17 -1
@@ -3330,11 +3330,77 @@ void set_task_rq_fair(struct sched_entit
 	se->avg.last_update_time = n_last_update_time;
 }
 
-/* Take into account change of utilization of a child task group */
+
+/*
+ * When on migration a sched_entity joins/leaves the PELT hierarchy, we need to
+ * propagate its contribution. The key to this propagation is the invariant
+ * that for each group:
+ *
+ *   ge->avg == grq->avg						(1)
+ *
+ * _IFF_ we look at the pure running and runnable sums. Because they
+ * represent the very same entity, just at different points in the hierarchy.
+ *
+ *
+ * Per the above update_tg_cfs_util() is trivial (and still 'wrong') and
+ * simply copies the running sum over.
+ *
+ * However, update_tg_cfs_runnable() is more complex. So we have:
+ *
Quoted 8 lines

kernel/sched/fair.c void set_task_rq_fair(struct sched_entit · line 3355

Quoted 6 lines
kernel/sched/fair.c +6 -0
+ *   ge->avg.load_avg = ge->load.weight * ge->avg.runnable_avg		(2)
+ *
+ * And since, like util, the runnable part should be directly transferable,
+ * the following would _appear_ to be the straight forward approach:
+ *
+ *   grq->avg.load_avg = grq->load.weight * grq->avg.running_avg	(3)

Should it be grq->avg.runnable_avg instead of running_avg?

Yes very much so. Typing hard. Otherwise (3) would not follow from (2) either.

Quoted 8 lines

cfs_rq->avg.load_avg has been defined previous (in patch 2 I think) to be:

	load_avg = \Sum se->avg.load_avg
		 = \Sum se->load.weight * se->avg.runnable_avg

That sum will increase when ge is runnable regardless of whether it is running or not. So, I think it has to be runnable_avg to make sense?

Ack.

Quoted 11 lines

kernel/sched/fair.c void set_task_rq_fair(struct sched_entit · line 3359

Quoted 4 lines
kernel/sched/fair.c +4 -0
+ *
+ * And per (1) we have:
+ *
+ *   ge->avg.running_avg == grq->avg.running_avg

You just said further up that (1) only applies to running and runnable sums? These are averages, so I think this is invalid use of (1). But maybe that is part of your point about (4) being wrong?

I'm still trying to get my head around the remaining bits, but it sort of depends if I understood the above bits correctly :)

So while true, the thing we're looking for is indeed runnable_avg.

Quoted 11 lines
Quoted 11 lines
kernel/sched/fair.c +11 -0
+ *
+ * Which gives:
+ *
+ *                      ge->load.weight * grq->avg.load_avg
+ *   ge->avg.load_avg = -----------------------------------		(4)
+ *                               grq->load.weight
+ *
+ * Except that is wrong!
+ *
+ * Because while for entities historical weight is not important and we
+ * really only care about our future and therefore can consider a pure
Quoted 8 lines

kernel/sched/fair.c void set_task_rq_fair(struct sched_entit · line 3378

Quoted 8 lines
kernel/sched/fair.c +8 -0
+ * runnable sum, runqueues can NOT do this.
+ *
+ * We specifically want runqueues to have a load_avg that includes
+ * historical weights. Those represent the blocked load, the load we expect
+ * to (shortly) return to us. This only works by keeping the weights as
+ * integral part of the sum. We therefore cannot decompose as per (3).
+ *
+ * OK, so what then?

And as the text above suggests, we cannot decompose because it contains the blocked weight, which is not included in grq->load.weight and thus things come apart.

Quoted 10 lines
Quoted 10 lines
kernel/sched/fair.c +10 -0
+ * Another way to look at things is:
+ *
+ *   grq->avg.load_avg = \Sum se->avg.load_avg
+ *
+ * Therefore, per (2):
+ *
+ *   grq->avg.load_avg = \Sum se->load.weight * se->avg.runnable_avg
+ *
+ * And the very thing we're propagating is a change in that sum (someone
+ * joined/left). So we can easily know the runnable change, which would be, per
Quoted 8 lines

kernel/sched/fair.c void set_task_rq_fair(struct sched_entit · line 3396

Quoted 8 lines
kernel/sched/fair.c +8 -0
+ * (2) the already tracked se->load_avg divided by the corresponding
+ * se->weight.
+ *
+ * Basically (4) but in differential form:
+ *
+ *   d(runnable_avg) += se->avg.load_avg / se->load.weight
+ *								   (5)
+ *   ge->avg.load_avg += ge->load.weight * d(runnable_avg)

And this all has runnable again, and so should make sense.

Combined with an earlier bit, noted by Dietmar, I now have the below delta.

---
 kernel/sched/fair.c | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)
kernel/sched/fair.c +4 -4
index b9e520b6923e..ba879c42bddd 100644
@@ -3333,7 +3333,7 @@ __update_load_avg_cfs_rq(u64 now, int cpu, struct cfs_rq *cfs_rq)
  * differential update where we store the last value we propagated. This in
  * turn allows skipping updates if the differential is 'small'.
  *
- * Updating tg's load_avg is necessary before update_cfs_share().
+ * Updating tg's load_avg is necessary before update_cfs_group().
  */
 static inline void update_tg_load_avg(struct cfs_rq *cfs_rq, int force)
 {
@@ -3422,11 +3422,11 @@ void set_task_rq_fair(struct sched_entity *se,
  * And since, like util, the runnable part should be directly transferable,
  * the following would _appear_ to be the straight forward approach:
  *
- *   grq->avg.load_avg = grq->load.weight * grq->avg.running_avg	(3)
+ *   grq->avg.load_avg = grq->load.weight * grq->avg.runnable_avg	(3)
  *
  * And per (1) we have:
  *
- *   ge->avg.running_avg == grq->avg.running_avg
+ *   ge->avg.runnable_avg == grq->avg.runnable_avg
  *
  * Which gives:
  *
@@ -3601,7 +3601,7 @@ static inline void add_tg_cfs_propagate(struct cfs_rq *cfs_rq, long runnable_sum
  * avg. The immediate corollary is that all (fair) tasks must be attached, see
  * post_init_entity_util_avg().
  *
- * cfs_rq->avg is used for task_h_load() and update_cfs_share() for example.
+ * cfs_rq->avg is used for task_h_load() and update_cfs_group() for example.
  *
  * Returns true if the load decayed or we removed load.
  *
#23 lore raw

Re: [PATCH -v2 12/18] sched/fair: Rewrite PELT migration propagation

Quoted 116 lines · Peter Zijlstra
Quoted 35 lines · Morten Rasmussen
Quoted 35 lines
kernel/sched/debug.c +2 -0
@@ -565,6 +565,8 @@ void print_cfs_rq(struct seq_file *m, in
 			cfs_rq->removed.load_avg);
 	SEQ_printf(m, "  .%-30s: %ld\n", "removed.util_avg",
 			cfs_rq->removed.util_avg);
+	SEQ_printf(m, "  .%-30s: %ld\n", "removed.runnable_sum",
+			cfs_rq->removed.runnable_sum);
 #ifdef CONFIG_FAIR_GROUP_SCHED
 	SEQ_printf(m, "  .%-30s: %lu\n", "tg_load_avg_contrib",
 			cfs_rq->tg_load_avg_contrib);
kernel/sched/fair.c +17 -1
@@ -3330,11 +3330,77 @@ void set_task_rq_fair(struct sched_entit
 	se->avg.last_update_time = n_last_update_time;
 }
 
-/* Take into account change of utilization of a child task group */
+
+/*
+ * When on migration a sched_entity joins/leaves the PELT hierarchy, we need to
+ * propagate its contribution. The key to this propagation is the invariant
+ * that for each group:
+ *
+ *   ge->avg == grq->avg						(1)
+ *
+ * _IFF_ we look at the pure running and runnable sums. Because they
+ * represent the very same entity, just at different points in the hierarchy.
+ *
+ *
+ * Per the above update_tg_cfs_util() is trivial (and still 'wrong') and
+ * simply copies the running sum over.
+ *
+ * However, update_tg_cfs_runnable() is more complex. So we have:
+ *
Quoted 8 lines

kernel/sched/fair.c void set_task_rq_fair(struct sched_entit · line 3355

Quoted 6 lines
kernel/sched/fair.c +6 -0
+ *   ge->avg.load_avg = ge->load.weight * ge->avg.runnable_avg		(2)
+ *
+ * And since, like util, the runnable part should be directly transferable,
+ * the following would _appear_ to be the straight forward approach:
+ *
+ *   grq->avg.load_avg = grq->load.weight * grq->avg.running_avg	(3)

Should it be grq->avg.runnable_avg instead of running_avg?

Yes very much so. Typing hard. Otherwise (3) would not follow from (2) either.

Quoted 8 lines

cfs_rq->avg.load_avg has been defined previous (in patch 2 I think) to be:

	load_avg = \Sum se->avg.load_avg
		 = \Sum se->load.weight * se->avg.runnable_avg

That sum will increase when ge is runnable regardless of whether it is running or not. So, I think it has to be runnable_avg to make sense?

Ack.

Quoted 11 lines

kernel/sched/fair.c void set_task_rq_fair(struct sched_entit · line 3359

Quoted 4 lines
kernel/sched/fair.c +4 -0
+ *
+ * And per (1) we have:
+ *
+ *   ge->avg.running_avg == grq->avg.running_avg

You just said further up that (1) only applies to running and runnable sums? These are averages, so I think this is invalid use of (1). But maybe that is part of your point about (4) being wrong?

I'm still trying to get my head around the remaining bits, but it sort of depends if I understood the above bits correctly :)

So while true, the thing we're looking for is indeed runnable_avg.

Quoted 11 lines
Quoted 11 lines
kernel/sched/fair.c +11 -0
+ *
+ * Which gives:
+ *
+ *                      ge->load.weight * grq->avg.load_avg
+ *   ge->avg.load_avg = -----------------------------------		(4)
+ *                               grq->load.weight
+ *
+ * Except that is wrong!
+ *
+ * Because while for entities historical weight is not important and we
+ * really only care about our future and therefore can consider a pure
Quoted 8 lines

kernel/sched/fair.c void set_task_rq_fair(struct sched_entit · line 3378

Quoted 8 lines
kernel/sched/fair.c +8 -0
+ * runnable sum, runqueues can NOT do this.
+ *
+ * We specifically want runqueues to have a load_avg that includes
+ * historical weights. Those represent the blocked load, the load we expect
+ * to (shortly) return to us. This only works by keeping the weights as
+ * integral part of the sum. We therefore cannot decompose as per (3).
+ *
+ * OK, so what then?

And as the text above suggests, we cannot decompose because it contains the blocked weight, which is not included in grq->load.weight and thus things come apart.

Quoted 10 lines
Quoted 10 lines
kernel/sched/fair.c +10 -0
+ * Another way to look at things is:
+ *
+ *   grq->avg.load_avg = \Sum se->avg.load_avg
+ *
+ * Therefore, per (2):
+ *
+ *   grq->avg.load_avg = \Sum se->load.weight * se->avg.runnable_avg
+ *
+ * And the very thing we're propagating is a change in that sum (someone
+ * joined/left). So we can easily know the runnable change, which would be, per
Quoted 8 lines

kernel/sched/fair.c void set_task_rq_fair(struct sched_entit · line 3396

Quoted 8 lines
kernel/sched/fair.c +8 -0
+ * (2) the already tracked se->load_avg divided by the corresponding
+ * se->weight.
+ *
+ * Basically (4) but in differential form:
+ *
+ *   d(runnable_avg) += se->avg.load_avg / se->load.weight
+ *								   (5)
+ *   ge->avg.load_avg += ge->load.weight * d(runnable_avg)
Quoted 1 line

And this all has runnable again, and so should make sense.

I'm afraid I don't quite get why (5) is correct. It might be related to the issues Vincent already pointed out.

d(runnable_avg) is the runnable_avg series for the joining/leaving se which is contributing to grq->avg.load_avg, but I don't see how you can use that to compute the impact on ge->avg.load_avg.

	ge->avg.load_avg = ge->load.weight * ge->avg.runnable_avg		(2)

In (5) you have just substituted ge->avg.runnable_avg with d(runnable_avg) in (2). However, the relationship between ge->avg.runnable_avg and se->avg.runnable_avg is complicated. ge is runnable whenever se is, but the reverse isn't necessarily true. Let's say you have two always-runnable tasks on your grq and one of the leaves (migrates away). In that case, ge->avg.runnable_avg is equal to se->avg.runnable_avg (both always-runnable) which is d(runnable_avg), so in (5) we end up with:

	ge->avg.load_avg =	ge->load.weight * ge->avg.runnable_avg
			      - ge->load.weight * se->avg.runnable_avg
			 = 0

But you still have one always-running task on the grq so clearly it shouldn't be zero.

IOW, AFAICT, it is not possible to decompose ge->avg.runnable_avg into contributions from each individual se on the grq. At least not without some additional assumptions.

What am I missing?

Morten

author maintainer
#24 lore raw

Re: [PATCH -v2 12/18] sched/fair: Rewrite PELT migration propagation

Quoted 10 lines · Morten Rasmussen
Quoted 7 lines
Quoted 5 lines
Quoted 5 lines

+ * Basically (4) but in differential form:
+ *
+ * d(runnable_avg) += se->avg.load_avg / se->load.weight
+ * (5)
+ * ge->avg.load_avg += ge->load.weight * d(runnable_avg)

And this all has runnable again, and so should make sense.

I'm afraid I don't quite get why (5) is correct. It might be related to the issues Vincent already pointed out.

Yeah; I think so... Let me stare at his latest -- which still doesn't update this comment.. :/

maintainer
#25 lore raw

Re: [PATCH -v2 12/18] sched/fair: Rewrite PELT migration propagation

In reply to Peter Zijlstra

Hi Peter,

Quoted 47 lines · Peter Zijlstra

When an entity migrates in (or out) of a runqueue, we need to add (or remove) its contribution from the entire PELT hierarchy, because even non-runnable entities are included in the load average sums.

In order to do this we have some propagation logic that updates the PELT tree, however the way it 'propagates' the runnable (or load) change is (more or less):

                     tg->weight * grq->avg.load_avg
  ge->avg.load_avg = ------------------------------
                               tg->load_avg

But that is the expression for ge->weight, and per the definition of load_avg:

ge->avg.load_avg := ge->weight * ge->avg.runnable_avg

That destroys the runnable_avg (by setting it to 1) we wanted to propagate.

Instead directly propagate runnable_sum.

---
 kernel/sched/debug.c |    2
 kernel/sched/fair.c  |  186 ++++++++++++++++++++++++++++-----------------------
 kernel/sched/sched.h |    9 +-
 3 files changed, 112 insertions(+), 85 deletions(-)
kernel/sched/debug.c +2 -0
@@ -565,6 +565,8 @@ void print_cfs_rq(struct seq_file *m, in
                        cfs_rq->removed.load_avg);
        SEQ_printf(m, "  .%-30s: %ld\n", "removed.util_avg",
                        cfs_rq->removed.util_avg);
+       SEQ_printf(m, "  .%-30s: %ld\n", "removed.runnable_sum",
+                       cfs_rq->removed.runnable_sum);
 #ifdef CONFIG_FAIR_GROUP_SCHED
        SEQ_printf(m, "  .%-30s: %lu\n", "tg_load_avg_contrib",
                        cfs_rq->tg_load_avg_contrib);
kernel/sched/fair.c +0 -1
@@ -3330,11 +3330,77 @@ void set_task_rq_fair(struct sched_entit
        se->avg.last_update_time = n_last_update_time;
 }
 
-/* Take into account change of utilization of a child task group */

kernel/sched/fair.c void set_task_rq_fair(struct sched_entit · line 3342

Quoted 10 lines
kernel/sched/fair.c +10 -0
+
+/*
+ * When on migration a sched_entity joins/leaves the PELT hierarchy, we need to
+ * propagate its contribution. The key to this propagation is the invariant
+ * that for each group:
+ *
+ *   ge->avg == grq->avg                                               (1)
+ *
+ * _IFF_ we look at the pure running and runnable sums. Because they
+ * represent the very same entity, just at different points in the hierarchy.

I agree for the running part because only one entity can be running but i'm not sure for the pure runnable sum because we can have several runnable task in a cfs_rq but only one runnable group entity to reflect them
or I misunderstand (1)

As an example, we have 2 always running task TA and TB so their load_sum is LOAD_AVG_MAX for each task
The grq->avg.load_sum = \Sum se->avg.load_sum = 2*LOAD_AVG_MAX But
the ge->avg.load_sum will be only LOAD_AVG_MAX

So If we apply directly the d(TB->avg.load_sum) on the group hierachy and on ge->avg.load_sum in particular, the latter decreases to 0 whereas it should decrease only by half

I have been able to see this wrong behavior with a rt-app json file

so I think that we should instead remove only

delta = se->avg.load_sum / grq->avg.load_sum * ge->avg.load_sum

We don't have grq->avg.load_sum but we can have a rough estimate with grq->avg.load_avg/grq->weight

Quoted 58 lines
kernel/sched/fair.c +58 -0
+ *
+ *
+ * Per the above update_tg_cfs_util() is trivial (and still 'wrong') and
+ * simply copies the running sum over.
+ *
+ * However, update_tg_cfs_runnable() is more complex. So we have:
+ *
+ *   ge->avg.load_avg = ge->load.weight * ge->avg.runnable_avg         (2)
+ *
+ * And since, like util, the runnable part should be directly transferable,
+ * the following would _appear_ to be the straight forward approach:
+ *
+ *   grq->avg.load_avg = grq->load.weight * grq->avg.running_avg       (3)
+ *
+ * And per (1) we have:
+ *
+ *   ge->avg.running_avg == grq->avg.running_avg
+ *
+ * Which gives:
+ *
+ *                      ge->load.weight * grq->avg.load_avg
+ *   ge->avg.load_avg = -----------------------------------            (4)
+ *                               grq->load.weight
+ *
+ * Except that is wrong!
+ *
+ * Because while for entities historical weight is not important and we
+ * really only care about our future and therefore can consider a pure
+ * runnable sum, runqueues can NOT do this.
+ *
+ * We specifically want runqueues to have a load_avg that includes
+ * historical weights. Those represent the blocked load, the load we expect
+ * to (shortly) return to us. This only works by keeping the weights as
+ * integral part of the sum. We therefore cannot decompose as per (3).
+ *
+ * OK, so what then?
+ *
+ *
+ * Another way to look at things is:
+ *
+ *   grq->avg.load_avg = \Sum se->avg.load_avg
+ *
+ * Therefore, per (2):
+ *
+ *   grq->avg.load_avg = \Sum se->load.weight * se->avg.runnable_avg
+ *
+ * And the very thing we're propagating is a change in that sum (someone
+ * joined/left). So we can easily know the runnable change, which would be, per
+ * (2) the already tracked se->load_avg divided by the corresponding
+ * se->weight.
+ *
+ * Basically (4) but in differential form:
+ *
+ *   d(runnable_avg) += se->avg.load_avg / se->load.weight
+ *                                                                (5)
+ *   ge->avg.load_avg += ge->load.weight * d(runnable_avg)
+ */
+

[snip]

maintainer
#26 lore raw

Re: [PATCH -v2 12/18] sched/fair: Rewrite PELT migration propagation

Quoted 77 lines · Vincent Guittot

Hi Peter,

Quoted 47 lines · Peter Zijlstra

When an entity migrates in (or out) of a runqueue, we need to add (or remove) its contribution from the entire PELT hierarchy, because even non-runnable entities are included in the load average sums.

In order to do this we have some propagation logic that updates the PELT tree, however the way it 'propagates' the runnable (or load) change is (more or less):

                     tg->weight * grq->avg.load_avg
  ge->avg.load_avg = ------------------------------
                               tg->load_avg

But that is the expression for ge->weight, and per the definition of load_avg:

ge->avg.load_avg := ge->weight * ge->avg.runnable_avg

That destroys the runnable_avg (by setting it to 1) we wanted to propagate.

Instead directly propagate runnable_sum.

---
 kernel/sched/debug.c |    2
 kernel/sched/fair.c  |  186 ++++++++++++++++++++++++++++-----------------------
 kernel/sched/sched.h |    9 +-
 3 files changed, 112 insertions(+), 85 deletions(-)
kernel/sched/debug.c +2 -0
@@ -565,6 +565,8 @@ void print_cfs_rq(struct seq_file *m, in
                        cfs_rq->removed.load_avg);
        SEQ_printf(m, "  .%-30s: %ld\n", "removed.util_avg",
                        cfs_rq->removed.util_avg);
+       SEQ_printf(m, "  .%-30s: %ld\n", "removed.runnable_sum",
+                       cfs_rq->removed.runnable_sum);
 #ifdef CONFIG_FAIR_GROUP_SCHED
        SEQ_printf(m, "  .%-30s: %lu\n", "tg_load_avg_contrib",
                        cfs_rq->tg_load_avg_contrib);
kernel/sched/fair.c +0 -1
@@ -3330,11 +3330,77 @@ void set_task_rq_fair(struct sched_entit
        se->avg.last_update_time = n_last_update_time;
 }
 
-/* Take into account change of utilization of a child task group */

kernel/sched/fair.c void set_task_rq_fair(struct sched_entit · line 3342

Quoted 10 lines
kernel/sched/fair.c +10 -0
+
+/*
+ * When on migration a sched_entity joins/leaves the PELT hierarchy, we need to
+ * propagate its contribution. The key to this propagation is the invariant
+ * that for each group:
+ *
+ *   ge->avg == grq->avg                                               (1)
+ *
+ * _IFF_ we look at the pure running and runnable sums. Because they
+ * represent the very same entity, just at different points in the hierarchy.

I agree for the running part because only one entity can be running but i'm not sure for the pure runnable sum because we can have several runnable task in a cfs_rq but only one runnable group entity to reflect them
or I misunderstand (1)

As an example, we have 2 always running task TA and TB so their load_sum is LOAD_AVG_MAX for each task
The grq->avg.load_sum = \Sum se->avg.load_sum = 2*LOAD_AVG_MAX But
the ge->avg.load_sum will be only LOAD_AVG_MAX

So If we apply directly the d(TB->avg.load_sum) on the group hierachy and on ge->avg.load_sum in particular, the latter decreases to 0 whereas it should decrease only by half

Quoted 5 lines

I have been able to see this wrong behavior with a rt-app json file

so I think that we should instead remove only

delta = se->avg.load_sum / grq->avg.load_sum * ge->avg.load_sum

delta = se->avg.load_sum / (grq->avg.load_sum+se->avg.load_sum) * ge->avg.load_sum

as the se has already been detached

Quoted 65 lines

We don't have grq->avg.load_sum but we can have a rough estimate with grq->avg.load_avg/grq->weight

Quoted 58 lines
kernel/sched/fair.c +58 -0
+ *
+ *
+ * Per the above update_tg_cfs_util() is trivial (and still 'wrong') and
+ * simply copies the running sum over.
+ *
+ * However, update_tg_cfs_runnable() is more complex. So we have:
+ *
+ *   ge->avg.load_avg = ge->load.weight * ge->avg.runnable_avg         (2)
+ *
+ * And since, like util, the runnable part should be directly transferable,
+ * the following would _appear_ to be the straight forward approach:
+ *
+ *   grq->avg.load_avg = grq->load.weight * grq->avg.running_avg       (3)
+ *
+ * And per (1) we have:
+ *
+ *   ge->avg.running_avg == grq->avg.running_avg
+ *
+ * Which gives:
+ *
+ *                      ge->load.weight * grq->avg.load_avg
+ *   ge->avg.load_avg = -----------------------------------            (4)
+ *                               grq->load.weight
+ *
+ * Except that is wrong!
+ *
+ * Because while for entities historical weight is not important and we
+ * really only care about our future and therefore can consider a pure
+ * runnable sum, runqueues can NOT do this.
+ *
+ * We specifically want runqueues to have a load_avg that includes
+ * historical weights. Those represent the blocked load, the load we expect
+ * to (shortly) return to us. This only works by keeping the weights as
+ * integral part of the sum. We therefore cannot decompose as per (3).
+ *
+ * OK, so what then?
+ *
+ *
+ * Another way to look at things is:
+ *
+ *   grq->avg.load_avg = \Sum se->avg.load_avg
+ *
+ * Therefore, per (2):
+ *
+ *   grq->avg.load_avg = \Sum se->load.weight * se->avg.runnable_avg
+ *
+ * And the very thing we're propagating is a change in that sum (someone
+ * joined/left). So we can easily know the runnable change, which would be, per
+ * (2) the already tracked se->load_avg divided by the corresponding
+ * se->weight.
+ *
+ * Basically (4) but in differential form:
+ *
+ *   d(runnable_avg) += se->avg.load_avg / se->load.weight
+ *                                                                (5)
+ *   ge->avg.load_avg += ge->load.weight * d(runnable_avg)
+ */
+

[snip]

author maintainer
#27 lore raw

Re: [PATCH -v2 12/18] sched/fair: Rewrite PELT migration propagation

Quoted 13 lines · Vincent Guittot
Quoted 12 lines · Vincent Guittot
Quoted 9 lines · Peter Zijlstra

+/*
+ * When on migration a sched_entity joins/leaves the PELT hierarchy, we need to
+ * propagate its contribution. The key to this propagation is the invariant
+ * that for each group:
+ *
+ * ge->avg == grq->avg (1)
+ *
+ * _IFF_ we look at the pure running and runnable sums. Because they
+ * represent the very same entity, just at different points in the hierarchy.

Quoted 4 lines
Quoted 4 lines

I agree for the running part because only one entity can be running but i'm not sure for the pure runnable sum because we can have several runnable task in a cfs_rq but only one runnable group entity to reflect them or I misunderstand (1)

The idea is that they (ge and grq) are the _same_ entity, just at different levels in the hierarchy. If the grq is runnable, it is through the ge.

As a whole, they don't care how many runnable tasks there are.

Quoted 11 lines
Quoted 11 lines

As an example, we have 2 always running task TA and TB so their load_sum is LOAD_AVG_MAX for each task The grq->avg.load_sum = \Sum se->avg.load_sum = 2*LOAD_AVG_MAX But the ge->avg.load_sum will be only LOAD_AVG_MAX

So If we apply directly the d(TB->avg.load_sum) on the group hierachy and on ge->avg.load_sum in particular, the latter decreases to 0 whereas it should decrease only by half

I have been able to see this wrong behavior with a rt-app json file

Quoted 11 lines
Quoted 3 lines

so I think that we should instead remove only

delta = se->avg.load_sum / grq->avg.load_sum * ge->avg.load_sum

delta = se->avg.load_sum / (grq->avg.load_sum+se->avg.load_sum) * ge->avg.load_sum

as the se has already been detached

Quoted 2 lines

We don't have grq->avg.load_sum but we can have a rough estimate with grq->avg.load_avg/grq->weight

Hurm, I think I see what you're saying, let me ponder this more.

maintainer
#28 lore raw

Re: [PATCH -v2 12/18] sched/fair: Rewrite PELT migration propagation

Quoted 19 lines · Peter Zijlstra
Quoted 13 lines · Vincent Guittot
Quoted 12 lines · Vincent Guittot
Quoted 9 lines · Peter Zijlstra

+/*
+ * When on migration a sched_entity joins/leaves the PELT hierarchy, we need to
+ * propagate its contribution. The key to this propagation is the invariant
+ * that for each group:
+ *
+ * ge->avg == grq->avg (1)
+ *
+ * _IFF_ we look at the pure running and runnable sums. Because they
+ * represent the very same entity, just at different points in the hierarchy.

Quoted 4 lines
Quoted 4 lines

I agree for the running part because only one entity can be running but i'm not sure for the pure runnable sum because we can have several runnable task in a cfs_rq but only one runnable group entity to reflect them or I misunderstand (1)

Quoted 5 lines

The idea is that they (ge and grq) are the _same_ entity, just at different levels in the hierarchy. If the grq is runnable, it is through the ge.

As a whole, they don't care how many runnable tasks there are.

Ok so I agree with this point that both grp and ge runnable follow the same trend

my point is that even if same changes apply on both grp and ge, we can't directly apply changes of grp's runnable on ge's runnable

Quoted 19 lines
Quoted 19 lines
Quoted 10 lines

As an example, we have 2 always running task TA and TB so their load_sum is LOAD_AVG_MAX for each task The grq->avg.load_sum = \Sum se->avg.load_sum = 2*LOAD_AVG_MAX But the ge->avg.load_sum will be only LOAD_AVG_MAX

So If we apply directly the d(TB->avg.load_sum) on the group hierachy and on ge->avg.load_sum in particular, the latter decreases to 0 whereas it should decrease only by half

Quoted 5 lines

I have been able to see this wrong behavior with a rt-app json file

so I think that we should instead remove only

delta = se->avg.load_sum / grq->avg.load_sum * ge->avg.load_sum

delta = se->avg.load_sum / (grq->avg.load_sum+se->avg.load_sum) * ge->avg.load_sum

Quoted 6 lines
Quoted 4 lines

as the se has already been detached

Quoted 2 lines

We don't have grq->avg.load_sum but we can have a rough estimate with grq->avg.load_avg/grq->weight

Hurm, I think I see what you're saying, let me ponder this more.

The formula above works was an example for detaching but it doesn't apply for all use case. we need a more generic way to propagate runnable changes

maintainer
#29 lore raw

Re: [PATCH -v2 12/18] sched/fair: Rewrite PELT migration propagation

Hi Peter,

Quoted 53 lines · Vincent Guittot
Quoted 19 lines · Peter Zijlstra
Quoted 13 lines · Vincent Guittot
Quoted 12 lines · Vincent Guittot
Quoted 9 lines · Peter Zijlstra

+/*
+ * When on migration a sched_entity joins/leaves the PELT hierarchy, we need to
+ * propagate its contribution. The key to this propagation is the invariant
+ * that for each group:
+ *
+ * ge->avg == grq->avg (1)
+ *
+ * _IFF_ we look at the pure running and runnable sums. Because they
+ * represent the very same entity, just at different points in the hierarchy.

Quoted 4 lines
Quoted 4 lines

I agree for the running part because only one entity can be running but i'm not sure for the pure runnable sum because we can have several runnable task in a cfs_rq but only one runnable group entity to reflect them or I misunderstand (1)

Quoted 5 lines

The idea is that they (ge and grq) are the _same_ entity, just at different levels in the hierarchy. If the grq is runnable, it is through the ge.

As a whole, they don't care how many runnable tasks there are.

Ok so I agree with this point that both grp and ge runnable follow the same trend

my point is that even if same changes apply on both grp and ge, we can't directly apply changes of grp's runnable on ge's runnable

Quoted 21 lines
Quoted 21 lines
Quoted 10 lines

As an example, we have 2 always running task TA and TB so their load_sum is LOAD_AVG_MAX for each task The grq->avg.load_sum = \Sum se->avg.load_sum = 2*LOAD_AVG_MAX But the ge->avg.load_sum will be only LOAD_AVG_MAX

So If we apply directly the d(TB->avg.load_sum) on the group hierachy and on ge->avg.load_sum in particular, the latter decreases to 0 whereas it should decrease only by half

Quoted 5 lines

I have been able to see this wrong behavior with a rt-app json file

so I think that we should instead remove only

delta = se->avg.load_sum / grq->avg.load_sum * ge->avg.load_sum

delta = se->avg.load_sum / (grq->avg.load_sum+se->avg.load_sum) * ge->avg.load_sum

as the se has already been detached

Quoted 8 lines
Quoted 4 lines
Quoted 2 lines
Quoted 2 lines

We don't have grq->avg.load_sum but we can have a rough estimate with grq->avg.load_avg/grq->weight

Hurm, I think I see what you're saying, let me ponder this more.

The formula above works was an example for detaching but it doesn't apply for all use case. we need a more generic way to propagate runnable changes

I have studied a bit more how to improve the propagation formula and the changes below is doing the job for the UCs that I have tested.

Unlike running, we can't directly propagate the runnable through hierarchy when we migrate a task. Instead we must ensure that we will not over/underestimate the impact of the migration thanks to several rules:
-ge->avg.runnable_sum can't be higher than LOAD_AVG_MAX -ge->avg.runnable_sum can't be lower than ge->avg.running_sum (once scaled to the same range)
-we can't directly propagate a negative delta of runnable_sum because part of this runnable time can be "shared" with others sched_entities and stays on the gcfs_rq. Instead, we can't estimate the new runnable_sum of the gcfs_rq with the formula: gcfs_rq's runnable sum = gcfs_rq's load_sum / gcfs_rq's weight. -ge->avg.runnable_sum can't increase when we detach a task.

---
 kernel/sched/fair.c | 56 ++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 45 insertions(+), 11 deletions(-)
kernel/sched/fair.c +45 -11
index 350dbec0..a063b048 100644
@@ -3489,33 +3489,67 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq
 static inline void
 update_tg_cfs_runnable(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq *gcfs_rq)
 {
-	long runnable_sum = gcfs_rq->prop_runnable_sum;
-	long runnable_load_avg, load_avg;
-	s64 runnable_load_sum, load_sum;
+	long running_sum, runnable_sum = gcfs_rq->prop_runnable_sum;
+	long runnable_load_avg, delta_avg, load_avg;
+	s64 runnable_load_sum, delta_sum, load_sum = 0;
 
 	if (!runnable_sum)
 		return;
 
 	gcfs_rq->prop_runnable_sum = 0;
 
+	/*
+	 * Get a rough estimate of gcfs_rq's runnable
+	 * This is a low guess as it assumes that tasks are equally
+	 * runnable which is not true but we can't really do better
+	 */
+	if (scale_load_down(gcfs_rq->load.weight))
+		load_sum = div_s64(gcfs_rq->avg.load_sum,
+				scale_load_down(gcfs_rq->load.weight));
+
+	/*
+	 * Propating a delta of runnable is not just adding it to ge's
+	 * runnable_sum:
+	 * - Adding a delta runnable can't make ge's runnable_sum higher than
+	 *   LOAD_AVG_MAX
+	 * - We can't directly remove a delta of runnable from
+	 *   ge's runnable_sum but we can only guest estimate what runnable
+	 *   will become thanks to few simple rules:
+	 *   - gcfs_rq's runnable is a good estimate
+	 *   - ge's runnable_sum can't increase when we remove runnable
+	 *   - runnable_sum can't be lower than running_sum
+	 */
+	if (runnable_sum >= 0) {
+		runnable_sum += se->avg.load_sum;
+		runnable_sum = min(runnable_sum, LOAD_AVG_MAX);
+	} else
+		runnable_sum = min(se->avg.load_sum, load_sum);
+
+	running_sum = se->avg.util_sum >> SCHED_CAPACITY_SHIFT;
+	runnable_sum = max(runnable_sum, running_sum);
+
 	load_sum = (s64)se_weight(se) * runnable_sum;
 	load_avg = div_s64(load_sum, LOAD_AVG_MAX);
 
-	add_positive(&se->avg.load_sum, runnable_sum);
-	add_positive(&se->avg.load_avg, load_avg);
+	delta_sum = load_sum - (s64)se_weight(se) * se->avg.load_sum;
+	delta_avg = load_avg - se->avg.load_avg;
 
-	add_positive(&cfs_rq->avg.load_avg, load_avg);
-	add_positive(&cfs_rq->avg.load_sum, load_sum);
+	se->avg.load_sum = runnable_sum;
+	se->avg.load_avg = load_avg;
+	add_positive(&cfs_rq->avg.load_avg, delta_avg);
+	add_positive(&cfs_rq->avg.load_sum, delta_sum);
 
 	runnable_load_sum = (s64)se_runnable(se) * runnable_sum;
 	runnable_load_avg = div_s64(runnable_load_sum, LOAD_AVG_MAX);
+	delta_sum = runnable_load_sum - se_weight(se) * se->avg.runnable_load_sum;
+	delta_avg = runnable_load_avg - se->avg.runnable_load_avg;
 
-	add_positive(&se->avg.runnable_load_sum, runnable_sum);
-	add_positive(&se->avg.runnable_load_avg, runnable_load_avg);
+	se->avg.runnable_load_sum = runnable_sum;
+	se->avg.runnable_load_avg = runnable_load_avg;
 
 	if (se->on_rq) {
-		add_positive(&cfs_rq->avg.runnable_load_avg, runnable_load_avg);
-		add_positive(&cfs_rq->avg.runnable_load_sum, runnable_load_sum);
+		add_positive(&cfs_rq->avg.runnable_load_avg, delta_avg);
+		add_positive(&cfs_rq->avg.runnable_load_sum, delta_sum);
 	}
 }
 
Signature · 1 line
2.7.4
author maintainer
#30 lore raw

Re: [PATCH -v2 12/18] sched/fair: Rewrite PELT migration propagation

Quoted 4 lines · Vincent Guittot

I have studied a bit more how to improve the propagation formula and the changes below is doing the job for the UCs that I have tested.

Quoted 9 lines

Unlike running, we can't directly propagate the runnable through hierarchy when we migrate a task. Instead we must ensure that we will not over/underestimate the impact of the migration thanks to several rules:
- ge->avg.runnable_sum can't be higher than LOAD_AVG_MAX
- ge->avg.runnable_sum can't be lower than ge->avg.running_sum (once scaled to the same range)
- we can't directly propagate a negative delta of runnable_sum because part of this runnable time can be "shared" with others sched_entities and stays on the gcfs_rq.

Right, that's about how far I got.

Quoted 1 line

- ge->avg.runnable_sum can't increase when we detach a task.

Yeah, that would be fairly broken.

Quoted 1 line

Instead, we can't estimate the new runnable_sum of the gcfs_rq with

s/can't/can/ ?

Quoted 3 lines

the formula:

gcfs_rq's runnable sum = gcfs_rq's load_sum / gcfs_rq's weight.

That might be the best we can do.. its wrong, but then its less wrong that what we have now. The comments can be much improved though. Not to mention that the big comment on top needs a little help.

Quoted 19 lines
---
 kernel/sched/fair.c | 56 ++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 45 insertions(+), 11 deletions(-)
kernel/sched/fair.c +3 -0
index 350dbec0..a063b048 100644
@@ -3489,33 +3489,67 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq
 static inline void
 update_tg_cfs_runnable(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq *gcfs_rq)
 {
+	long running_sum, runnable_sum = gcfs_rq->prop_runnable_sum;
+	long runnable_load_avg, delta_avg, load_avg;
+	s64 runnable_load_sum, delta_sum, load_sum = 0;
 
 	if (!runnable_sum)
 		return;
 

kernel/sched/fair.c update_tg_cfs_util(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq · line 3508

Quoted 10 lines
kernel/sched/fair.c +8 -0
 	gcfs_rq->prop_runnable_sum = 0;
 
+	/*
+	 * Get a rough estimate of gcfs_rq's runnable
+	 * This is a low guess as it assumes that tasks are equally
+	 * runnable which is not true but we can't really do better
+	 */
+	if (scale_load_down(gcfs_rq->load.weight)) {
+		load_sum = div_s64(gcfs_rq->avg.load_sum,
+				scale_load_down(gcfs_rq->load.weight));
	}
Quoted 8 lines
kernel/sched/fair.c +8 -0
+
+	/*
+	 * Propating a delta of runnable is not just adding it to ge's
+	 * runnable_sum:
+	 * - Adding a delta runnable can't make ge's runnable_sum higher than
+	 *   LOAD_AVG_MAX
+	 * - We can't directly remove a delta of runnable from
+	 *   ge's runnable_sum but we can only guest estimate what runnable

kernel/sched/fair.c update_tg_cfs_util(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq · line 3526

Quoted 10 lines
kernel/sched/fair.c +10 -0
+	 *   will become thanks to few simple rules:
+	 *   - gcfs_rq's runnable is a good estimate
+	 *   - ge's runnable_sum can't increase when we remove runnable
+	 *   - runnable_sum can't be lower than running_sum
+	 */
+	if (runnable_sum >= 0) {
+		runnable_sum += se->avg.load_sum;
+		runnable_sum = min(runnable_sum, LOAD_AVG_MAX);
+	} else {
+		runnable_sum = min(se->avg.load_sum, load_sum);
	}
Quoted 32 lines
kernel/sched/fair.c +16 -0
+
+	running_sum = se->avg.util_sum >> SCHED_CAPACITY_SHIFT;
+	runnable_sum = max(runnable_sum, running_sum);
+
 	load_sum = (s64)se_weight(se) * runnable_sum;
 	load_avg = div_s64(load_sum, LOAD_AVG_MAX);
 
+	delta_sum = load_sum - (s64)se_weight(se) * se->avg.load_sum;
+	delta_avg = load_avg - se->avg.load_avg;
 
+	se->avg.load_sum = runnable_sum;
+	se->avg.load_avg = load_avg;
+	add_positive(&cfs_rq->avg.load_avg, delta_avg);
+	add_positive(&cfs_rq->avg.load_sum, delta_sum);
 
 	runnable_load_sum = (s64)se_runnable(se) * runnable_sum;
 	runnable_load_avg = div_s64(runnable_load_sum, LOAD_AVG_MAX);
+	delta_sum = runnable_load_sum - se_weight(se) * se->avg.runnable_load_sum;
+	delta_avg = runnable_load_avg - se->avg.runnable_load_avg;
 
+	se->avg.runnable_load_sum = runnable_sum;
+	se->avg.runnable_load_avg = runnable_load_avg;
 
 	if (se->on_rq) {
+		add_positive(&cfs_rq->avg.runnable_load_avg, delta_avg);
+		add_positive(&cfs_rq->avg.runnable_load_sum, delta_sum);
 	}
 }
 
Signature · 1 line
2.7.4
maintainer
#31 lore raw

Re: [PATCH -v2 12/18] sched/fair: Rewrite PELT migration propagation

Quoted 17 lines · Peter Zijlstra
Quoted 4 lines · Vincent Guittot

I have studied a bit more how to improve the propagation formula and the changes below is doing the job for the UCs that I have tested.

Quoted 9 lines

Unlike running, we can't directly propagate the runnable through hierarchy when we migrate a task. Instead we must ensure that we will not over/underestimate the impact of the migration thanks to several rules:
- ge->avg.runnable_sum can't be higher than LOAD_AVG_MAX
- ge->avg.runnable_sum can't be lower than ge->avg.running_sum (once scaled to the same range)
- we can't directly propagate a negative delta of runnable_sum because part of this runnable time can be "shared" with others sched_entities and stays on the gcfs_rq.

Right, that's about how far I got.

Quoted 7 lines
Quoted 1 line

- ge->avg.runnable_sum can't increase when we detach a task.

Yeah, that would be fairly broken.

Quoted 1 line

Instead, we can't estimate the new runnable_sum of the gcfs_rq with

s/can't/can/ ?

yes it's can

Quoted 8 lines
Quoted 4 lines

the formula:

gcfs_rq's runnable sum = gcfs_rq's load_sum / gcfs_rq's weight.

That might be the best we can do.. its wrong, but then its less wrong that what we have now. The comments can be much improved though. Not to mention that the big comment on top needs a little help.

I'm going to update the comment

Quoted 82 lines
Quoted 20 lines
---
 kernel/sched/fair.c | 56 ++++++++++++++++++++++++++++++++++++++++++-----------
 1 file changed, 45 insertions(+), 11 deletions(-)
kernel/sched/fair.c +3 -0
index 350dbec0..a063b048 100644
@@ -3489,33 +3489,67 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq
 static inline void
 update_tg_cfs_runnable(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq *gcfs_rq)
 {
+     long running_sum, runnable_sum = gcfs_rq->prop_runnable_sum;
+     long runnable_load_avg, delta_avg, load_avg;
+     s64 runnable_load_sum, delta_sum, load_sum = 0;
 
      if (!runnable_sum)
              return;
 

kernel/sched/fair.c update_tg_cfs_util(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq · line 3508

Quoted 10 lines
kernel/sched/fair.c +8 -0
      gcfs_rq->prop_runnable_sum = 0;
 
+     /*
+      * Get a rough estimate of gcfs_rq's runnable
+      * This is a low guess as it assumes that tasks are equally
+      * runnable which is not true but we can't really do better
+      */
+     if (scale_load_down(gcfs_rq->load.weight)) {
+             load_sum = div_s64(gcfs_rq->avg.load_sum,
+                             scale_load_down(gcfs_rq->load.weight));
        }
Quoted 8 lines
kernel/sched/fair.c +8 -0
+
+     /*
+      * Propating a delta of runnable is not just adding it to ge's
+      * runnable_sum:
+      * - Adding a delta runnable can't make ge's runnable_sum higher than
+      *   LOAD_AVG_MAX
+      * - We can't directly remove a delta of runnable from
+      *   ge's runnable_sum but we can only guest estimate what runnable

kernel/sched/fair.c update_tg_cfs_util(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq · line 3526

Quoted 10 lines
kernel/sched/fair.c +10 -0
+      *   will become thanks to few simple rules:
+      *   - gcfs_rq's runnable is a good estimate
+      *   - ge's runnable_sum can't increase when we remove runnable
+      *   - runnable_sum can't be lower than running_sum
+      */
+     if (runnable_sum >= 0) {
+             runnable_sum += se->avg.load_sum;
+             runnable_sum = min(runnable_sum, LOAD_AVG_MAX);
+     } else {
+             runnable_sum = min(se->avg.load_sum, load_sum);
        }
Quoted 32 lines
kernel/sched/fair.c +16 -1
+
+     running_sum = se->avg.util_sum >> SCHED_CAPACITY_SHIFT;
+     runnable_sum = max(runnable_sum, running_sum);
+
      load_sum = (s64)se_weight(se) * runnable_sum;
      load_avg = div_s64(load_sum, LOAD_AVG_MAX);
 
+     delta_sum = load_sum - (s64)se_weight(se) * se->avg.load_sum;
+     delta_avg = load_avg - se->avg.load_avg;
 
+     se->avg.load_sum = runnable_sum;
+     se->avg.load_avg = load_avg;
+     add_positive(&cfs_rq->avg.load_avg, delta_avg);
+     add_positive(&cfs_rq->avg.load_sum, delta_sum);
 
      runnable_load_sum = (s64)se_runnable(se) * runnable_sum;
      runnable_load_avg = div_s64(runnable_load_sum, LOAD_AVG_MAX);
+     delta_sum = runnable_load_sum - se_weight(se) * se->avg.runnable_load_sum;
+     delta_avg = runnable_load_avg - se->avg.runnable_load_avg;
 
+     se->avg.runnable_load_sum = runnable_sum;
+     se->avg.runnable_load_avg = runnable_load_avg;
 
      if (se->on_rq) {
+             add_positive(&cfs_rq->avg.runnable_load_avg, delta_avg);
+             add_positive(&cfs_rq->avg.runnable_load_sum, delta_sum);
      }
 }
 
--

2.7.4

maintainer
#32 lore raw

Re: [PATCH -v2 12/18] sched/fair: Rewrite PELT migration propagation

In reply to Peter Zijlstra

Hi Peter,

Quoted 26 lines · Peter Zijlstra
Quoted 4 lines · Vincent Guittot

I have studied a bit more how to improve the propagation formula and the changes below is doing the job for the UCs that I have tested.

Quoted 9 lines

Unlike running, we can't directly propagate the runnable through hierarchy when we migrate a task. Instead we must ensure that we will not over/underestimate the impact of the migration thanks to several rules:
- ge->avg.runnable_sum can't be higher than LOAD_AVG_MAX
- ge->avg.runnable_sum can't be lower than ge->avg.running_sum (once scaled to the same range)
- we can't directly propagate a negative delta of runnable_sum because part of this runnable time can be "shared" with others sched_entities and stays on the gcfs_rq.

Right, that's about how far I got.

Quoted 1 line

- ge->avg.runnable_sum can't increase when we detach a task.

Yeah, that would be fairly broken.

Quoted 1 line

Instead, we can't estimate the new runnable_sum of the gcfs_rq with

s/can't/can/ ?

Quoted 7 lines
Quoted 3 lines

the formula:

gcfs_rq's runnable sum = gcfs_rq's load_sum / gcfs_rq's weight.

That might be the best we can do.. its wrong, but then its less wrong that what we have now. The comments can be much improved though. Not to mention that the big comment on top needs a little help.

Subject: [PATCH] sched: Update runnable propagation rule

Unlike running, the runnable part can't be directly propagated through the hierarchy when we migrate a task. The main reason is that runnable time can be shared with other sched_entities that stay on the rq and this runnable time will also remain on prev cfs_rq and must not be removed. Instead, we can estimate what should be the new runnable of the prev cfs_rq and check that this estimation stay in a possible range.
The prop_runnable_sum is a good estimation when adding runnable_sum but fails most often when we remove it. Instead, we could use the formula below instead:

gcfs_rq's runnable_sum = gcfs_rq->avg.load_sum / gcfs_rq->load.weight (1)

(1) assumes that tasks are equally runnable which is not true but easy to compute.

Beside these estimates, we have several simple rules that help us to filter out wrong ones:
-ge->avg.runnable_sum <= than LOAD_AVG_MAX
-ge->avg.runnable_sum >= ge->avg.running_sum (ge->avg.util_sum << LOAD_AVG_MAX) -ge->avg.runnable_sum can't increase when we detach a task

---
 kernel/sched/fair.c | 45 ++++++++++++++++++++++++++++++++++-----------
 1 file changed, 34 insertions(+), 11 deletions(-)
kernel/sched/fair.c +34 -11
index 350dbec0..08d2a58 100644
@@ -3489,33 +3489,56 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq
 static inline void
 update_tg_cfs_runnable(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq *gcfs_rq)
 {
-	long runnable_sum = gcfs_rq->prop_runnable_sum;
-	long runnable_load_avg, load_avg;
-	s64 runnable_load_sum, load_sum;
+	long running_sum, runnable_sum = gcfs_rq->prop_runnable_sum;
+	long runnable_load_avg, delta_avg, load_avg;
+	s64 runnable_load_sum, delta_sum, load_sum = 0;
 
 	if (!runnable_sum)
 		return;
 
 	gcfs_rq->prop_runnable_sum = 0;
 
+	if (runnable_sum >= 0) {
+		/* Get a rough estimate of the new gcfs_rq's runnable */
+		runnable_sum += se->avg.load_sum;
+		/* ge->avg.runnable_sum can't be higher than LOAD_AVG_MAX */
+		runnable_sum = min(runnable_sum, LOAD_AVG_MAX);
+	} else {
+		/* Get a rough estimate of the new gcfs_rq's runnable */
+		if (scale_load_down(gcfs_rq->load.weight))
+			load_sum = div_s64(gcfs_rq->avg.load_sum,
+				scale_load_down(gcfs_rq->load.weight));
+
+		/* ge->avg.runnable_sum can't increase when removing runnable */
+		runnable_sum = min(se->avg.load_sum, load_sum);
+	}
+
+	/* runnable_sum can't be lower than running_sum */
+	running_sum = se->avg.util_sum >> SCHED_CAPACITY_SHIFT;
+	runnable_sum = max(runnable_sum, running_sum);
+
 	load_sum = (s64)se_weight(se) * runnable_sum;
 	load_avg = div_s64(load_sum, LOAD_AVG_MAX);
 
-	add_positive(&se->avg.load_sum, runnable_sum);
-	add_positive(&se->avg.load_avg, load_avg);
+	delta_sum = load_sum - (s64)se_weight(se) * se->avg.load_sum;
+	delta_avg = load_avg - se->avg.load_avg;
 
-	add_positive(&cfs_rq->avg.load_avg, load_avg);
-	add_positive(&cfs_rq->avg.load_sum, load_sum);
+	se->avg.load_sum = runnable_sum;
+	se->avg.load_avg = load_avg;
+	add_positive(&cfs_rq->avg.load_avg, delta_avg);
+	add_positive(&cfs_rq->avg.load_sum, delta_sum);
 
 	runnable_load_sum = (s64)se_runnable(se) * runnable_sum;
 	runnable_load_avg = div_s64(runnable_load_sum, LOAD_AVG_MAX);
+	delta_sum = runnable_load_sum - se_weight(se) * se->avg.runnable_load_sum;
+	delta_avg = runnable_load_avg - se->avg.runnable_load_avg;
 
-	add_positive(&se->avg.runnable_load_sum, runnable_sum);
-	add_positive(&se->avg.runnable_load_avg, runnable_load_avg);
+	se->avg.runnable_load_sum = runnable_sum;
+	se->avg.runnable_load_avg = runnable_load_avg;
 
 	if (se->on_rq) {
-		add_positive(&cfs_rq->avg.runnable_load_avg, runnable_load_avg);
-		add_positive(&cfs_rq->avg.runnable_load_sum, runnable_load_sum);
+		add_positive(&cfs_rq->avg.runnable_load_avg, delta_avg);
+		add_positive(&cfs_rq->avg.runnable_load_sum, delta_sum);
 	}
 }
 
Signature · 1 line
2.7.4
maintainer
#33 lore raw

Re: [PATCH -v2 12/18] sched/fair: Rewrite PELT migration propagation

Subject: [PATCH v2] sched: Update runnable propagation rule

Unlike running, the runnable part can't be directly propagated through the hierarchy when we migrate a task. The main reason is that runnable time can be shared with other sched_entities that stay on the rq and this runnable time will also remain on prev cfs_rq and must not be removed. Instead, we can estimate what should be the new runnable of the prev cfs_rq and check that this estimation stay in a possible range.
The prop_runnable_sum is a good estimation when adding runnable_sum but fails most often when we remove it. Instead, we could use the formula below instead:

gcfs_rq's runnable_sum = gcfs_rq->avg.load_sum / gcfs_rq->load.weight (1)

(1) assumes that tasks are equally runnable which is not true but easy to compute.

Beside these estimates, we have several simple rules that help us to filter out wrong ones:
-ge->avg.runnable_sum <= than LOAD_AVG_MAX
-ge->avg.runnable_sum >= ge->avg.running_sum (ge->avg.util_sum << LOAD_AVG_MAX) -ge->avg.runnable_sum can't increase when we detach a task

---

v2:
- Fixed some type mismatch warnings

 kernel/sched/fair.c | 46 +++++++++++++++++++++++++++++++++++-----------
 1 file changed, 35 insertions(+), 11 deletions(-)
kernel/sched/fair.c +35 -11
index 56f343b..aea89df 100644
@@ -3489,33 +3489,57 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq
 static inline void
 update_tg_cfs_runnable(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq *gcfs_rq)
 {
-	long runnable_sum = gcfs_rq->prop_runnable_sum;
-	long runnable_load_avg, load_avg;
-	s64 runnable_load_sum, load_sum;
+	long delta_avg, running_sum, runnable_sum = gcfs_rq->prop_runnable_sum;
+	unsigned long runnable_load_avg, load_avg;
+	s64 delta_sum;
+	u64 runnable_load_sum, load_sum = 0;
 
 	if (!runnable_sum)
 		return;
 
 	gcfs_rq->prop_runnable_sum = 0;
 
+	if (runnable_sum >= 0) {
+		/* Get a rough estimate of the new gcfs_rq's runnable */
+		runnable_sum += se->avg.load_sum;
+		/* ge->avg.runnable_sum can't be higher than LOAD_AVG_MAX */
+		runnable_sum = min(runnable_sum, (long)LOAD_AVG_MAX);
+	} else {
+		/* Get a rough estimate of the new gcfs_rq's runnable */
+		if (scale_load_down(gcfs_rq->load.weight))
+			load_sum = div_s64(gcfs_rq->avg.load_sum,
+				scale_load_down(gcfs_rq->load.weight));
+
+		/* ge->avg.runnable_sum can't increase when removing runnable */
+		runnable_sum = min(se->avg.load_sum, load_sum);
+	}
+
+	/* runnable_sum can't be lower than running_sum */
+	running_sum = se->avg.util_sum >> SCHED_CAPACITY_SHIFT;
+	runnable_sum = max(runnable_sum, running_sum);
+
 	load_sum = (s64)se_weight(se) * runnable_sum;
 	load_avg = div_s64(load_sum, LOAD_AVG_MAX);
 
-	add_positive(&se->avg.load_sum, runnable_sum);
-	add_positive(&se->avg.load_avg, load_avg);
+	delta_sum = load_sum - (s64)se_weight(se) * se->avg.load_sum;
+	delta_avg = load_avg - se->avg.load_avg;
 
-	add_positive(&cfs_rq->avg.load_avg, load_avg);
-	add_positive(&cfs_rq->avg.load_sum, load_sum);
+	se->avg.load_sum = runnable_sum;
+	se->avg.load_avg = load_avg;
+	add_positive(&cfs_rq->avg.load_avg, delta_avg);
+	add_positive(&cfs_rq->avg.load_sum, delta_sum);
 
 	runnable_load_sum = (s64)se_runnable(se) * runnable_sum;
 	runnable_load_avg = div_s64(runnable_load_sum, LOAD_AVG_MAX);
+	delta_sum = runnable_load_sum - se_weight(se) * se->avg.runnable_load_sum;
+	delta_avg = runnable_load_avg - se->avg.runnable_load_avg;
 
-	add_positive(&se->avg.runnable_load_sum, runnable_sum);
-	add_positive(&se->avg.runnable_load_avg, runnable_load_avg);
+	se->avg.runnable_load_sum = runnable_sum;
+	se->avg.runnable_load_avg = runnable_load_avg;
 
 	if (se->on_rq) {
-		add_positive(&cfs_rq->avg.runnable_load_avg, runnable_load_avg);
-		add_positive(&cfs_rq->avg.runnable_load_sum, runnable_load_sum);
+		add_positive(&cfs_rq->avg.runnable_load_avg, delta_avg);
+		add_positive(&cfs_rq->avg.runnable_load_sum, delta_sum);
 	}
 }
 
Signature · 1 line
2.7.4
author maintainer
#34 lore raw

Re: [PATCH -v2 12/18] sched/fair: Rewrite PELT migration propagation

So after a bit of poking I ended up with something like the below; I think there's still a few open points, see XXX. But its better than we have now.

Josef, could you see if this completely wrecks your workloads?

---
Subject: sched: Update runnable propagation rule
From: Vincent Guittot <[email protected]>
Date: Thu, 19 Oct 2017 17:04:42 +0200

Unlike running, the runnable part can't be directly propagated through the hierarchy when we migrate a task. The main reason is that runnable time can be shared with other sched_entities that stay on the rq and this runnable time will also remain on prev cfs_rq and must not be removed.

Instead, we can estimate what should be the new runnable of the prev cfs_rq and check that this estimation stay in a possible range. The prop_runnable_sum is a good estimation when adding runnable_sum but fails most often when we remove it. Instead, we could use the formula below instead:

gcfs_rq's runnable_sum = gcfs_rq->avg.load_sum / gcfs_rq->load.weight

which assumes that tasks are equally runnable which is not true but easy to compute.

Beside these estimates, we have several simple rules that help us to filter out wrong ones:

- ge->avg.runnable_sum <= than LOAD_AVG_MAX
- ge->avg.runnable_sum >= ge->avg.running_sum (ge->avg.util_sum << LOAD_AVG_MAX)
- ge->avg.runnable_sum can't increase when we detach a task

Cc Yuyang Du <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Mike Galbraith <[email protected]>
Cc Chris Mason <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Dietmar Eggemann <[email protected]>
Cc Josef Bacik <[email protected]>
Cc Ben Segall <[email protected]>
Cc Paul Turner <[email protected]>
Cc Tejun Heo <[email protected]>
Cc Morten Rasmussen <[email protected]>

---

 kernel/sched/fair.c |   99 ++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 70 insertions(+), 29 deletions(-)
kernel/sched/fair.c +70 -29
@@ -3412,9 +3412,9 @@ void set_task_rq_fair(struct sched_entit
  * _IFF_ we look at the pure running and runnable sums. Because they
  * represent the very same entity, just at different points in the hierarchy.
  *
- *
- * Per the above update_tg_cfs_util() is trivial (and still 'wrong') and
- * simply copies the running sum over.
+ * Per the above update_tg_cfs_util() is trivial and simply copies the running
+ * sum over (but still wrong, because the group entity and group rq do not have
+ * their PELT windows aligned).
  *
  * However, update_tg_cfs_runnable() is more complex. So we have:
  *
@@ -3423,11 +3423,11 @@ void set_task_rq_fair(struct sched_entit
  * And since, like util, the runnable part should be directly transferable,
  * the following would _appear_ to be the straight forward approach:
  *
- *   grq->avg.load_avg = grq->load.weight * grq->avg.running_avg	(3)
+ *   grq->avg.load_avg = grq->load.weight * grq->avg.runnable_avg	(3)
  *
  * And per (1) we have:
  *
- *   ge->avg.running_avg == grq->avg.running_avg
+ *   ge->avg.runnable_avg == grq->avg.runnable_avg
  *
  * Which gives:
  *
@@ -3446,27 +3446,28 @@ void set_task_rq_fair(struct sched_entit
  * to (shortly) return to us. This only works by keeping the weights as
  * integral part of the sum. We therefore cannot decompose as per (3).
  *
- * OK, so what then?
+ * Another reason this doesn't work is that runnable isn't a 0-sum entity.
+ * Imagine a rq with 2 tasks that each are runnable 2/3 of the time. Then the
+ * rq itself is runnable anywhere between 2/3 and 1 depending on how the
+ * runnable section of these tasks overlap (or not). If they were to perfectly
+ * align the rq as a whole would be runnable 2/3 of the time. If however we
+ * always have at least 1 runnable task, the rq as a whole is always runnable.
  *
+ * So we'll have to approximate.. :/
  *
- * Another way to look at things is:
+ * Given the constraint:
  *
- *   grq->avg.load_avg = \Sum se->avg.load_avg
+ *   ge->avg.running_sum <= ge->avg.runnable_sum <= LOAD_AVG_MAX
  *
- * Therefore, per (2):
+ * We can construct a rule that adds runnable to a rq by assuming minimal
+ * overlap.
  *
- *   grq->avg.load_avg = \Sum se->load.weight * se->avg.runnable_avg
+ * On removal, we'll assume each task is equally runnable; which yields:
  *
- * And the very thing we're propagating is a change in that sum (someone
- * joined/left). So we can easily know the runnable change, which would be, per
- * (2) the already tracked se->load_avg divided by the corresponding
- * se->weight.
+ *   grq->avg.runnable_sum = grq->avg.load_sum / grq->load.weight
  *
- * Basically (4) but in differential form:
+ * XXX: only do this for the part of runnable > running ?
  *
- *   d(runnable_avg) += se->avg.load_avg / se->load.weight
- *								   (5)
- *   ge->avg.load_avg += ge->load.weight * d(runnable_avg)
  */
 
 static inline void
@@ -3478,6 +3479,14 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq
 	if (!delta)
 		return;
 
+	/*
+	 * The relation between sum and avg is:
+	 *
+	 *   LOAD_AVG_MAX - 1024 + sa->period_contrib
+	 *
+	 * however, the PELT windows are not aligned between grq and gse.
+	 */
+
 	/* Set new sched_entity's utilization */
 	se->avg.util_avg = gcfs_rq->avg.util_avg;
 	se->avg.util_sum = se->avg.util_avg * LOAD_AVG_MAX;
@@ -3490,33 +3499,65 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq
 static inline void
 update_tg_cfs_runnable(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq *gcfs_rq)
 {
-	long runnable_sum = gcfs_rq->prop_runnable_sum;
-	long runnable_load_avg, load_avg;
-	s64 runnable_load_sum, load_sum;
+	long delta_avg, running_sum, runnable_sum = gcfs_rq->prop_runnable_sum;
+	unsigned long runnable_load_avg, load_avg;
+	u64 runnable_load_sum, load_sum = 0;
+	s64 delta_sum;
 
 	if (!runnable_sum)
 		return;
 
 	gcfs_rq->prop_runnable_sum = 0;
 
+	if (runnable_sum >= 0) {
+		/*
+		 * Add runnable; clip at LOAD_AVG_MAX. Reflects that until
+		 * the CPU is saturated running == runnable.
+		 */
+		runnable_sum += se->avg.load_sum;
+		runnable_sum = min(runnable_sum, (long)LOAD_AVG_MAX);
+	} else {
+		/*
+		 * Estimate the departing task's runnable by assuming all tasks
+		 * are equally runnable.
+		 *
+		 * XXX: doesn't deal with multiple departures?
+		 */
+		if (scale_load_down(gcfs_rq->load.weight)) {
+			load_sum = div_s64(gcfs_rq->avg.load_sum,
+				scale_load_down(gcfs_rq->load.weight));
+		}
+
+		/* But make sure to not inflate se's runnable */
+		runnable_sum = min(se->avg.load_sum, load_sum);
+	}
+
+	/* runnable_sum can't be lower than running_sum */
+	running_sum = se->avg.util_sum >> SCHED_CAPACITY_SHIFT; /* XXX ? */
+	runnable_sum = max(runnable_sum, running_sum);
+
 	load_sum = (s64)se_weight(se) * runnable_sum;
 	load_avg = div_s64(load_sum, LOAD_AVG_MAX);
 
-	add_positive(&se->avg.load_sum, runnable_sum);
-	add_positive(&se->avg.load_avg, load_avg);
+	delta_sum = load_sum - (s64)se_weight(se) * se->avg.load_sum;
+	delta_avg = load_avg - se->avg.load_avg;
 
-	add_positive(&cfs_rq->avg.load_avg, load_avg);
-	add_positive(&cfs_rq->avg.load_sum, load_sum);
+	se->avg.load_sum = runnable_sum;
+	se->avg.load_avg = load_avg;
+	add_positive(&cfs_rq->avg.load_avg, delta_avg);
+	add_positive(&cfs_rq->avg.load_sum, delta_sum);
 
 	runnable_load_sum = (s64)se_runnable(se) * runnable_sum;
 	runnable_load_avg = div_s64(runnable_load_sum, LOAD_AVG_MAX);
+	delta_sum = runnable_load_sum - se_weight(se) * se->avg.runnable_load_sum;
+	delta_avg = runnable_load_avg - se->avg.runnable_load_avg;
 
-	add_positive(&se->avg.runnable_load_sum, runnable_sum);
-	add_positive(&se->avg.runnable_load_avg, runnable_load_avg);
+	se->avg.runnable_load_sum = runnable_sum;
+	se->avg.runnable_load_avg = runnable_load_avg;
 
 	if (se->on_rq) {
-		add_positive(&cfs_rq->avg.runnable_load_avg, runnable_load_avg);
-		add_positive(&cfs_rq->avg.runnable_load_sum, runnable_load_sum);
+		add_positive(&cfs_rq->avg.runnable_load_avg, delta_avg);
+		add_positive(&cfs_rq->avg.runnable_load_sum, delta_sum);
 	}
 }
maintainer
#35 lore raw

Re: [PATCH -v2 12/18] sched/fair: Rewrite PELT migration propagation

Quoted 108 lines · Peter Zijlstra

So after a bit of poking I ended up with something like the below; I think there's still a few open points, see XXX. But its better than we have now.

Josef, could you see if this completely wrecks your workloads?

---
Subject: sched: Update runnable propagation rule
From: Vincent Guittot <[email protected]>
Date: Thu, 19 Oct 2017 17:04:42 +0200

Unlike running, the runnable part can't be directly propagated through the hierarchy when we migrate a task. The main reason is that runnable time can be shared with other sched_entities that stay on the rq and this runnable time will also remain on prev cfs_rq and must not be removed.

Instead, we can estimate what should be the new runnable of the prev cfs_rq and check that this estimation stay in a possible range. The prop_runnable_sum is a good estimation when adding runnable_sum but fails most often when we remove it. Instead, we could use the formula below instead:

gcfs_rq's runnable_sum = gcfs_rq->avg.load_sum / gcfs_rq->load.weight

which assumes that tasks are equally runnable which is not true but easy to compute.

Beside these estimates, we have several simple rules that help us to filter out wrong ones:

- ge->avg.runnable_sum <= than LOAD_AVG_MAX
- ge->avg.runnable_sum >= ge->avg.running_sum (ge->avg.util_sum << LOAD_AVG_MAX)
- ge->avg.runnable_sum can't increase when we detach a task

Cc Yuyang Du <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Mike Galbraith <[email protected]>
Cc Chris Mason <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Dietmar Eggemann <[email protected]>
Cc Josef Bacik <[email protected]>
Cc Ben Segall <[email protected]>
Cc Paul Turner <[email protected]>
Cc Tejun Heo <[email protected]>
Cc Morten Rasmussen <[email protected]>

---

 kernel/sched/fair.c |   99 ++++++++++++++++++++++++++++++++++++----------------
 1 file changed, 70 insertions(+), 29 deletions(-)
kernel/sched/fair.c +16 -10
@@ -3412,9 +3412,9 @@ void set_task_rq_fair(struct sched_entit
  * _IFF_ we look at the pure running and runnable sums. Because they
  * represent the very same entity, just at different points in the hierarchy.
  *
- *
- * Per the above update_tg_cfs_util() is trivial (and still 'wrong') and
- * simply copies the running sum over.
+ * Per the above update_tg_cfs_util() is trivial and simply copies the running
+ * sum over (but still wrong, because the group entity and group rq do not have
+ * their PELT windows aligned).
  *
  * However, update_tg_cfs_runnable() is more complex. So we have:
  *
@@ -3423,11 +3423,11 @@ void set_task_rq_fair(struct sched_entit
  * And since, like util, the runnable part should be directly transferable,
  * the following would _appear_ to be the straight forward approach:
  *
- *   grq->avg.load_avg = grq->load.weight * grq->avg.running_avg       (3)
+ *   grq->avg.load_avg = grq->load.weight * grq->avg.runnable_avg      (3)
  *
  * And per (1) we have:
  *
- *   ge->avg.running_avg == grq->avg.running_avg
+ *   ge->avg.runnable_avg == grq->avg.runnable_avg
  *
  * Which gives:
  *
@@ -3446,27 +3446,28 @@ void set_task_rq_fair(struct sched_entit
  * to (shortly) return to us. This only works by keeping the weights as
  * integral part of the sum. We therefore cannot decompose as per (3).
  *
- * OK, so what then?
+ * Another reason this doesn't work is that runnable isn't a 0-sum entity.
+ * Imagine a rq with 2 tasks that each are runnable 2/3 of the time. Then the
+ * rq itself is runnable anywhere between 2/3 and 1 depending on how the
+ * runnable section of these tasks overlap (or not). If they were to perfectly
+ * align the rq as a whole would be runnable 2/3 of the time. If however we
+ * always have at least 1 runnable task, the rq as a whole is always runnable.
  *
+ * So we'll have to approximate.. :/
  *
- * Another way to look at things is:
+ * Given the constraint:
  *
- *   grq->avg.load_avg = \Sum se->avg.load_avg
+ *   ge->avg.running_sum <= ge->avg.runnable_sum <= LOAD_AVG_MAX
  *
- * Therefore, per (2):
+ * We can construct a rule that adds runnable to a rq by assuming minimal
+ * overlap.
  *
- *   grq->avg.load_avg = \Sum se->load.weight * se->avg.runnable_avg

kernel/sched/fair.c void set_task_rq_fair(struct sched_entit · line 3469

Quoted 10 lines
kernel/sched/fair.c +3 -5
+ * On removal, we'll assume each task is equally runnable; which yields:
  *
- * And the very thing we're propagating is a change in that sum (someone
- * joined/left). So we can easily know the runnable change, which would be, per
- * (2) the already tracked se->load_avg divided by the corresponding
- * se->weight.
+ *   grq->avg.runnable_sum = grq->avg.load_sum / grq->load.weight
  *
- * Basically (4) but in differential form:
+ * XXX: only do this for the part of runnable > running ?

That can be a possible improvement in how we are estimating the the runnable. I'm going to make some trials to see the impact on the estimation

Quoted 42 lines
kernel/sched/fair.c +15 -6
  *
- *   d(runnable_avg) += se->avg.load_avg / se->load.weight
- *                                                                (5)
- *   ge->avg.load_avg += ge->load.weight * d(runnable_avg)
  */
 
 static inline void
@@ -3478,6 +3479,14 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq
        if (!delta)
                return;
 
+       /*
+        * The relation between sum and avg is:
+        *
+        *   LOAD_AVG_MAX - 1024 + sa->period_contrib
+        *
+        * however, the PELT windows are not aligned between grq and gse.
+        */
+
        /* Set new sched_entity's utilization */
        se->avg.util_avg = gcfs_rq->avg.util_avg;
        se->avg.util_sum = se->avg.util_avg * LOAD_AVG_MAX;
@@ -3490,33 +3499,65 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq
 static inline void
 update_tg_cfs_runnable(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq *gcfs_rq)
 {
-       long runnable_sum = gcfs_rq->prop_runnable_sum;
-       long runnable_load_avg, load_avg;
-       s64 runnable_load_sum, load_sum;
+       long delta_avg, running_sum, runnable_sum = gcfs_rq->prop_runnable_sum;
+       unsigned long runnable_load_avg, load_avg;
+       u64 runnable_load_sum, load_sum = 0;
+       s64 delta_sum;
 
        if (!runnable_sum)
                return;
 
        gcfs_rq->prop_runnable_sum = 0;
 
+       if (runnable_sum >= 0) {
+               /*
+                * Add runnable; clip at LOAD_AVG_MAX. Reflects that until

kernel/sched/fair.c update_tg_cfs_util(struct cfs_rq *cfs_rq · line 3524

Quoted 10 lines
kernel/sched/fair.c +10 -0
+                * the CPU is saturated running == runnable.
+                */
+               runnable_sum += se->avg.load_sum;
+               runnable_sum = min(runnable_sum, (long)LOAD_AVG_MAX);
+       } else {
+               /*
+                * Estimate the departing task's runnable by assuming all tasks
+                * are equally runnable.
+                *
+                * XXX: doesn't deal with multiple departures?

Why this would not deal with multiple departures ?
we are using gcfs_rq->avg.load_sum that reflects the new state of the gcfs_rq to evaluate the runnable_sum

kernel/sched/fair.c update_tg_cfs_util(struct cfs_rq *cfs_rq · line 3536

Quoted 12 lines
kernel/sched/fair.c +12 -0
+                */
+               if (scale_load_down(gcfs_rq->load.weight)) {
+                       load_sum = div_s64(gcfs_rq->avg.load_sum,
+                               scale_load_down(gcfs_rq->load.weight));
+               }
+
+               /* But make sure to not inflate se's runnable */
+               runnable_sum = min(se->avg.load_sum, load_sum);
+       }
+
+       /* runnable_sum can't be lower than running_sum */
+       running_sum = se->avg.util_sum >> SCHED_CAPACITY_SHIFT; /* XXX ? */

running_sum is scaled by cpu's capacity but not load_sum

I have made the shortcut of using SCHED_CAPACITY_SHIFT for capacity but we might better use arch_scale_cpu_capacity(NULL, cpu) instead

Quoted 34 lines
kernel/sched/fair.c +14 -8
+       runnable_sum = max(runnable_sum, running_sum);
+
        load_sum = (s64)se_weight(se) * runnable_sum;
        load_avg = div_s64(load_sum, LOAD_AVG_MAX);
 
-       add_positive(&se->avg.load_sum, runnable_sum);
-       add_positive(&se->avg.load_avg, load_avg);
+       delta_sum = load_sum - (s64)se_weight(se) * se->avg.load_sum;
+       delta_avg = load_avg - se->avg.load_avg;
 
-       add_positive(&cfs_rq->avg.load_avg, load_avg);
-       add_positive(&cfs_rq->avg.load_sum, load_sum);
+       se->avg.load_sum = runnable_sum;
+       se->avg.load_avg = load_avg;
+       add_positive(&cfs_rq->avg.load_avg, delta_avg);
+       add_positive(&cfs_rq->avg.load_sum, delta_sum);
 
        runnable_load_sum = (s64)se_runnable(se) * runnable_sum;
        runnable_load_avg = div_s64(runnable_load_sum, LOAD_AVG_MAX);
+       delta_sum = runnable_load_sum - se_weight(se) * se->avg.runnable_load_sum;
+       delta_avg = runnable_load_avg - se->avg.runnable_load_avg;
 
-       add_positive(&se->avg.runnable_load_sum, runnable_sum);
-       add_positive(&se->avg.runnable_load_avg, runnable_load_avg);
+       se->avg.runnable_load_sum = runnable_sum;
+       se->avg.runnable_load_avg = runnable_load_avg;
 
        if (se->on_rq) {
-               add_positive(&cfs_rq->avg.runnable_load_avg, runnable_load_avg);
-               add_positive(&cfs_rq->avg.runnable_load_sum, runnable_load_sum);
+               add_positive(&cfs_rq->avg.runnable_load_avg, delta_avg);
+               add_positive(&cfs_rq->avg.runnable_load_sum, delta_sum);
        }
 }
author maintainer
#36 lore raw

Re: [PATCH -v2 12/18] sched/fair: Rewrite PELT migration propagation

Quoted 14 lines · Vincent Guittot

kernel/sched/fair.c update_tg_cfs_util(struct cfs_rq *cfs_rq · line 3524

Quoted 13 lines
kernel/sched/fair.c +13 -0
+       if (runnable_sum >= 0) {
+               /*
+                * Add runnable; clip at LOAD_AVG_MAX. Reflects that until
+                * the CPU is saturated running == runnable.
+                */
+               runnable_sum += se->avg.load_sum;
+               runnable_sum = min(runnable_sum, (long)LOAD_AVG_MAX);
+       } else {
+               /*
+                * Estimate the departing task's runnable by assuming all tasks
+                * are equally runnable.
+                *
+                * XXX: doesn't deal with multiple departures?
Quoted 3 lines

Why this would not deal with multiple departures ?
we are using gcfs_rq->avg.load_sum that reflects the new state of the gcfs_rq to evaluate the runnable_sum

Ah, I figured the load_sum thing below reflected one average task worth of runnable.

Quoted 7 lines

kernel/sched/fair.c update_tg_cfs_util(struct cfs_rq *cfs_rq · line 3536

Quoted 2 lines
kernel/sched/fair.c +2 -0
+       /* runnable_sum can't be lower than running_sum */
+       running_sum = se->avg.util_sum >> SCHED_CAPACITY_SHIFT; /* XXX ? */

running_sum is scaled by cpu's capacity but not load_sum

I have made the shortcut of using SCHED_CAPACITY_SHIFT for capacity but we might better use arch_scale_cpu_capacity(NULL, cpu) instead

Ah, right. We should improve the comments thereabouts, I got totally lost trying to track that yesterday.

Also; we should look at doing that invariant patch you're still sitting on.

maintainer
#37 lore raw

Re: [PATCH -v2 12/18] sched/fair: Rewrite PELT migration propagation

Quoted 29 lines · Peter Zijlstra
Quoted 14 lines · Vincent Guittot

kernel/sched/fair.c update_tg_cfs_util(struct cfs_rq *cfs_rq · line 3524

Quoted 13 lines
kernel/sched/fair.c +13 -0
+       if (runnable_sum >= 0) {
+               /*
+                * Add runnable; clip at LOAD_AVG_MAX. Reflects that until
+                * the CPU is saturated running == runnable.
+                */
+               runnable_sum += se->avg.load_sum;
+               runnable_sum = min(runnable_sum, (long)LOAD_AVG_MAX);
+       } else {
+               /*
+                * Estimate the departing task's runnable by assuming all tasks
+                * are equally runnable.
+                *
+                * XXX: doesn't deal with multiple departures?
Quoted 3 lines

Why this would not deal with multiple departures ?
we are using gcfs_rq->avg.load_sum that reflects the new state of the gcfs_rq to evaluate the runnable_sum

Ah, I figured the load_sum thing below reflected one average task worth of runnable.

Quoted 5 lines

kernel/sched/fair.c update_tg_cfs_util(struct cfs_rq *cfs_rq · line 3536

Quoted 2 lines
kernel/sched/fair.c +2 -0
+       /* runnable_sum can't be lower than running_sum */
+       running_sum = se->avg.util_sum >> SCHED_CAPACITY_SHIFT; /* XXX ? */

running_sum is scaled by cpu's capacity but not load_sum

Quoted 8 lines
Quoted 2 lines

I have made the shortcut of using SCHED_CAPACITY_SHIFT for capacity but we might better use arch_scale_cpu_capacity(NULL, cpu) instead

Ah, right. We should improve the comments thereabouts, I got totally lost trying to track that yesterday.

Also; we should look at doing that invariant patch you're still sitting on.

Yes. I have to rebase and test lastest changes i did

maintainer
#38 lore raw

PATCH v3 1/1 sched: Update runnable propagation rule

In reply to Peter Zijlstra

Unlike running, the runnable part can't be directly propagated through the hierarchy when we migrate a task. The main reason is that runnable time can be shared with other sched_entities that stay on the rq and this runnable time will also remain on prev cfs_rq and must not be removed.

Instead, we can estimate what should be the new runnable of the prev cfs_rq and check that this estimation stay in a possible range. The prop_runnable_sum is a good estimation when adding runnable_sum but fails most often when we remove it. Instead, we could use the formula below instead:

gcfs_rq's runnable_sum = gcfs_rq->avg.load_sum / gcfs_rq->load.weight

which assumes that tasks are equally runnable which is not true but easy to compute.

Beside these estimates, we have several simple rules that help us to filter out wrong ones:

- ge->avg.runnable_sum <= than LOAD_AVG_MAX
- ge->avg.runnable_sum >= ge->avg.running_sum (ge->avg.util_sum << LOAD_AVG_MAX)
- ge->avg.runnable_sum can't increase when we detach a task

Cc Yuyang Du <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Mike Galbraith <[email protected]>
Cc Chris Mason <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Dietmar Eggemann <[email protected]>
Cc Josef Bacik <[email protected]>
Cc Ben Segall <[email protected]>
Cc Paul Turner <[email protected]>
Cc Tejun Heo <[email protected]>
Cc Morten Rasmussen <[email protected]>

---

Hi Peter,

I have rebased the patch, updated the 2 comments that were unclear and fixed the computation of running_sum by using arch_scale_cpu_capacity() instead of

Quoted 1 line
Quoted 1 line

SCHED_CAPACITY_SHIFT.

 kernel/sched/fair.c | 101 +++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 72 insertions(+), 29 deletions(-)
kernel/sched/fair.c +72 -29
index 0989676..05eabb2 100644
@@ -3413,9 +3413,9 @@ void set_task_rq_fair(struct sched_entity *se,
  * _IFF_ we look at the pure running and runnable sums. Because they
  * represent the very same entity, just at different points in the hierarchy.
  *
- *
- * Per the above update_tg_cfs_util() is trivial (and still 'wrong') and
- * simply copies the running sum over.
+ * Per the above update_tg_cfs_util() is trivial and simply copies the running
+ * sum over (but still wrong, because the group entity and group rq do not have
+ * their PELT windows aligned).
  *
  * However, update_tg_cfs_runnable() is more complex. So we have:
  *
@@ -3424,11 +3424,11 @@ void set_task_rq_fair(struct sched_entity *se,
  * And since, like util, the runnable part should be directly transferable,
  * the following would _appear_ to be the straight forward approach:
  *
- *   grq->avg.load_avg = grq->load.weight * grq->avg.running_avg	(3)
+ *   grq->avg.load_avg = grq->load.weight * grq->avg.runnable_avg	(3)
  *
  * And per (1) we have:
  *
- *   ge->avg.running_avg == grq->avg.running_avg
+ *   ge->avg.runnable_avg == grq->avg.runnable_avg
  *
  * Which gives:
  *
@@ -3447,27 +3447,28 @@ void set_task_rq_fair(struct sched_entity *se,
  * to (shortly) return to us. This only works by keeping the weights as
  * integral part of the sum. We therefore cannot decompose as per (3).
  *
- * OK, so what then?
+ * Another reason this doesn't work is that runnable isn't a 0-sum entity.
+ * Imagine a rq with 2 tasks that each are runnable 2/3 of the time. Then the
+ * rq itself is runnable anywhere between 2/3 and 1 depending on how the
+ * runnable section of these tasks overlap (or not). If they were to perfectly
+ * align the rq as a whole would be runnable 2/3 of the time. If however we
+ * always have at least 1 runnable task, the rq as a whole is always runnable.
  *
+ * So we'll have to approximate.. :/
  *
- * Another way to look at things is:
+ * Given the constraint:
  *
- *   grq->avg.load_avg = \Sum se->avg.load_avg
+ *   ge->avg.running_sum <= ge->avg.runnable_sum <= LOAD_AVG_MAX
  *
- * Therefore, per (2):
+ * We can construct a rule that adds runnable to a rq by assuming minimal
+ * overlap.
  *
- *   grq->avg.load_avg = \Sum se->load.weight * se->avg.runnable_avg
+ * On removal, we'll assume each task is equally runnable; which yields:
  *
- * And the very thing we're propagating is a change in that sum (someone
- * joined/left). So we can easily know the runnable change, which would be, per
- * (2) the already tracked se->load_avg divided by the corresponding
- * se->weight.
+ *   grq->avg.runnable_sum = grq->avg.load_sum / grq->load.weight
  *
- * Basically (4) but in differential form:
+ * XXX: only do this for the part of runnable > running ?
  *
- *   d(runnable_avg) += se->avg.load_avg / se->load.weight
- *								   (5)
- *   ge->avg.load_avg += ge->load.weight * d(runnable_avg)
  */
 
 static inline void
@@ -3479,6 +3480,14 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq
 	if (!delta)
 		return;
 
+	/*
+	 * The relation between sum and avg is:
+	 *
+	 *   LOAD_AVG_MAX - 1024 + sa->period_contrib
+	 *
+	 * however, the PELT windows are not aligned between grq and gse.
+	 */
+
 	/* Set new sched_entity's utilization */
 	se->avg.util_avg = gcfs_rq->avg.util_avg;
 	se->avg.util_sum = se->avg.util_avg * LOAD_AVG_MAX;
@@ -3491,33 +3500,67 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq
 static inline void
 update_tg_cfs_runnable(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq *gcfs_rq)
 {
-	long runnable_sum = gcfs_rq->prop_runnable_sum;
-	long runnable_load_avg, load_avg;
-	s64 runnable_load_sum, load_sum;
+	long delta_avg, running_sum, runnable_sum = gcfs_rq->prop_runnable_sum;
+	unsigned long runnable_load_avg, load_avg;
+	u64 runnable_load_sum, load_sum = 0;
+	s64 delta_sum;
 
 	if (!runnable_sum)
 		return;
 
 	gcfs_rq->prop_runnable_sum = 0;
 
+	if (runnable_sum >= 0) {
+		/*
+		 * Add runnable; clip at LOAD_AVG_MAX. Reflects that until
+		 * the CPU is saturated running == runnable.
+		 */
+		runnable_sum += se->avg.load_sum;
+		runnable_sum = min(runnable_sum, (long)LOAD_AVG_MAX);
+	} else {
+		/*
+		 * Estimate the new unweighted runnable_sum of the gcfs_rq by
+		 * assuming all tasks are equally runnable.
+		 */
+		if (scale_load_down(gcfs_rq->load.weight)) {
+			load_sum = div_s64(gcfs_rq->avg.load_sum,
+				scale_load_down(gcfs_rq->load.weight));
+		}
+
+		/* But make sure to not inflate se's runnable */
+		runnable_sum = min(se->avg.load_sum, load_sum);
+	}
+
+	/*
+	 * runnable_sum can't be lower than running_sum
+	 * As running sum is scale with cpu capacity wehreas the runnable sum
+	 * is not we rescale running_sum 1st
+	 */
+	running_sum = se->avg.util_sum / arch_scale_cpu_capacity(NULL, cpu)
+	runnable_sum = max(runnable_sum, running_sum);
+
 	load_sum = (s64)se_weight(se) * runnable_sum;
 	load_avg = div_s64(load_sum, LOAD_AVG_MAX);
 
-	add_positive(&se->avg.load_sum, runnable_sum);
-	add_positive(&se->avg.load_avg, load_avg);
+	delta_sum = load_sum - (s64)se_weight(se) * se->avg.load_sum;
+	delta_avg = load_avg - se->avg.load_avg;
 
-	add_positive(&cfs_rq->avg.load_avg, load_avg);
-	add_positive(&cfs_rq->avg.load_sum, load_sum);
+	se->avg.load_sum = runnable_sum;
+	se->avg.load_avg = load_avg;
+	add_positive(&cfs_rq->avg.load_avg, delta_avg);
+	add_positive(&cfs_rq->avg.load_sum, delta_sum);
 
 	runnable_load_sum = (s64)se_runnable(se) * runnable_sum;
 	runnable_load_avg = div_s64(runnable_load_sum, LOAD_AVG_MAX);
+	delta_sum = runnable_load_sum - se_weight(se) * se->avg.runnable_load_sum;
+	delta_avg = runnable_load_avg - se->avg.runnable_load_avg;
 
-	add_positive(&se->avg.runnable_load_sum, runnable_sum);
-	add_positive(&se->avg.runnable_load_avg, runnable_load_avg);
+	se->avg.runnable_load_sum = runnable_sum;
+	se->avg.runnable_load_avg = runnable_load_avg;
 
 	if (se->on_rq) {
-		add_positive(&cfs_rq->avg.runnable_load_avg, runnable_load_avg);
-		add_positive(&cfs_rq->avg.runnable_load_sum, runnable_load_sum);
+		add_positive(&cfs_rq->avg.runnable_load_avg, delta_avg);
+		add_positive(&cfs_rq->avg.runnable_load_sum, delta_sum);
 	}
 }
 
Signature · 1 line
2.7.4
maintainer
#39 lore raw

PATCH v4 1/1 sched: Update runnable propagation rule

Unlike running, the runnable part can't be directly propagated through the hierarchy when we migrate a task. The main reason is that runnable time can be shared with other sched_entities that stay on the rq and this runnable time will also remain on prev cfs_rq and must not be removed.

Instead, we can estimate what should be the new runnable of the prev cfs_rq and check that this estimation stay in a possible range. The prop_runnable_sum is a good estimation when adding runnable_sum but fails most often when we remove it. Instead, we could use the formula below instead:

gcfs_rq's runnable_sum = gcfs_rq->avg.load_sum / gcfs_rq->load.weight

which assumes that tasks are equally runnable which is not true but easy to compute.

Beside these estimates, we have several simple rules that help us to filter out wrong ones:

- ge->avg.runnable_sum <= than LOAD_AVG_MAX
- ge->avg.runnable_sum >= ge->avg.running_sum (ge->avg.util_sum << LOAD_AVG_MAX)
- ge->avg.runnable_sum can't increase when we detach a task

Cc Yuyang Du <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Mike Galbraith <[email protected]>
Cc Chris Mason <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Dietmar Eggemann <[email protected]>
Cc Josef Bacik <[email protected]>
Cc Ben Segall <[email protected]>
Cc Paul Turner <[email protected]>
Cc Tejun Heo <[email protected]>
Cc Morten Rasmussen <[email protected]>

---

Hi Peter,

Please forget v3 which doesn' compile.

I have rebased the patch, updated the 2 comments that were unclear and fixed the computation of running_sum by using arch_scale_cpu_capacity() instead of

Quoted 1 line
Quoted 1 line

SCHED_CAPACITY_SHIFT.

 kernel/sched/fair.c | 102 +++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 73 insertions(+), 29 deletions(-)
kernel/sched/fair.c +73 -29
index 0989676..7d4dd7e 100644
@@ -3413,9 +3413,9 @@ void set_task_rq_fair(struct sched_entity *se,
  * _IFF_ we look at the pure running and runnable sums. Because they
  * represent the very same entity, just at different points in the hierarchy.
  *
- *
- * Per the above update_tg_cfs_util() is trivial (and still 'wrong') and
- * simply copies the running sum over.
+ * Per the above update_tg_cfs_util() is trivial and simply copies the running
+ * sum over (but still wrong, because the group entity and group rq do not have
+ * their PELT windows aligned).
  *
  * However, update_tg_cfs_runnable() is more complex. So we have:
  *
@@ -3424,11 +3424,11 @@ void set_task_rq_fair(struct sched_entity *se,
  * And since, like util, the runnable part should be directly transferable,
  * the following would _appear_ to be the straight forward approach:
  *
- *   grq->avg.load_avg = grq->load.weight * grq->avg.running_avg	(3)
+ *   grq->avg.load_avg = grq->load.weight * grq->avg.runnable_avg	(3)
  *
  * And per (1) we have:
  *
- *   ge->avg.running_avg == grq->avg.running_avg
+ *   ge->avg.runnable_avg == grq->avg.runnable_avg
  *
  * Which gives:
  *
@@ -3447,27 +3447,28 @@ void set_task_rq_fair(struct sched_entity *se,
  * to (shortly) return to us. This only works by keeping the weights as
  * integral part of the sum. We therefore cannot decompose as per (3).
  *
- * OK, so what then?
+ * Another reason this doesn't work is that runnable isn't a 0-sum entity.
+ * Imagine a rq with 2 tasks that each are runnable 2/3 of the time. Then the
+ * rq itself is runnable anywhere between 2/3 and 1 depending on how the
+ * runnable section of these tasks overlap (or not). If they were to perfectly
+ * align the rq as a whole would be runnable 2/3 of the time. If however we
+ * always have at least 1 runnable task, the rq as a whole is always runnable.
  *
+ * So we'll have to approximate.. :/
  *
- * Another way to look at things is:
+ * Given the constraint:
  *
- *   grq->avg.load_avg = \Sum se->avg.load_avg
+ *   ge->avg.running_sum <= ge->avg.runnable_sum <= LOAD_AVG_MAX
  *
- * Therefore, per (2):
+ * We can construct a rule that adds runnable to a rq by assuming minimal
+ * overlap.
  *
- *   grq->avg.load_avg = \Sum se->load.weight * se->avg.runnable_avg
+ * On removal, we'll assume each task is equally runnable; which yields:
  *
- * And the very thing we're propagating is a change in that sum (someone
- * joined/left). So we can easily know the runnable change, which would be, per
- * (2) the already tracked se->load_avg divided by the corresponding
- * se->weight.
+ *   grq->avg.runnable_sum = grq->avg.load_sum / grq->load.weight
  *
- * Basically (4) but in differential form:
+ * XXX: only do this for the part of runnable > running ?
  *
- *   d(runnable_avg) += se->avg.load_avg / se->load.weight
- *								   (5)
- *   ge->avg.load_avg += ge->load.weight * d(runnable_avg)
  */
 
 static inline void
@@ -3479,6 +3480,14 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq
 	if (!delta)
 		return;
 
+	/*
+	 * The relation between sum and avg is:
+	 *
+	 *   LOAD_AVG_MAX - 1024 + sa->period_contrib
+	 *
+	 * however, the PELT windows are not aligned between grq and gse.
+	 */
+
 	/* Set new sched_entity's utilization */
 	se->avg.util_avg = gcfs_rq->avg.util_avg;
 	se->avg.util_sum = se->avg.util_avg * LOAD_AVG_MAX;
@@ -3491,33 +3500,68 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq
 static inline void
 update_tg_cfs_runnable(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq *gcfs_rq)
 {
-	long runnable_sum = gcfs_rq->prop_runnable_sum;
-	long runnable_load_avg, load_avg;
-	s64 runnable_load_sum, load_sum;
+	long delta_avg, running_sum, runnable_sum = gcfs_rq->prop_runnable_sum;
+	unsigned long runnable_load_avg, load_avg;
+	u64 runnable_load_sum, load_sum = 0;
+	s64 delta_sum;
 
 	if (!runnable_sum)
 		return;
 
 	gcfs_rq->prop_runnable_sum = 0;
 
+	if (runnable_sum >= 0) {
+		/*
+		 * Add runnable; clip at LOAD_AVG_MAX. Reflects that until
+		 * the CPU is saturated running == runnable.
+		 */
+		runnable_sum += se->avg.load_sum;
+		runnable_sum = min(runnable_sum, (long)LOAD_AVG_MAX);
+	} else {
+		/*
+		 * Estimate the new unweighted runnable_sum of the gcfs_rq by
+		 * assuming all tasks are equally runnable.
+		 */
+		if (scale_load_down(gcfs_rq->load.weight)) {
+			load_sum = div_s64(gcfs_rq->avg.load_sum,
+				scale_load_down(gcfs_rq->load.weight));
+		}
+
+		/* But make sure to not inflate se's runnable */
+		runnable_sum = min(se->avg.load_sum, load_sum);
+	}
+
+	/*
+	 * runnable_sum can't be lower than running_sum
+	 * As running sum is scale with cpu capacity wehreas the runnable sum
+	 * is not we rescale running_sum 1st
+	 */
+	running_sum = se->avg.util_sum /
+		arch_scale_cpu_capacity(NULL, cpu_of(rq_of(cfs_rq)));
+	runnable_sum = max(runnable_sum, running_sum);
+
 	load_sum = (s64)se_weight(se) * runnable_sum;
 	load_avg = div_s64(load_sum, LOAD_AVG_MAX);
 
-	add_positive(&se->avg.load_sum, runnable_sum);
-	add_positive(&se->avg.load_avg, load_avg);
+	delta_sum = load_sum - (s64)se_weight(se) * se->avg.load_sum;
+	delta_avg = load_avg - se->avg.load_avg;
 
-	add_positive(&cfs_rq->avg.load_avg, load_avg);
-	add_positive(&cfs_rq->avg.load_sum, load_sum);
+	se->avg.load_sum = runnable_sum;
+	se->avg.load_avg = load_avg;
+	add_positive(&cfs_rq->avg.load_avg, delta_avg);
+	add_positive(&cfs_rq->avg.load_sum, delta_sum);
 
 	runnable_load_sum = (s64)se_runnable(se) * runnable_sum;
 	runnable_load_avg = div_s64(runnable_load_sum, LOAD_AVG_MAX);
+	delta_sum = runnable_load_sum - se_weight(se) * se->avg.runnable_load_sum;
+	delta_avg = runnable_load_avg - se->avg.runnable_load_avg;
 
-	add_positive(&se->avg.runnable_load_sum, runnable_sum);
-	add_positive(&se->avg.runnable_load_avg, runnable_load_avg);
+	se->avg.runnable_load_sum = runnable_sum;
+	se->avg.runnable_load_avg = runnable_load_avg;
 
 	if (se->on_rq) {
-		add_positive(&cfs_rq->avg.runnable_load_avg, runnable_load_avg);
-		add_positive(&cfs_rq->avg.runnable_load_sum, runnable_load_sum);
+		add_positive(&cfs_rq->avg.runnable_load_avg, delta_avg);
+		add_positive(&cfs_rq->avg.runnable_load_sum, delta_sum);
 	}
 }
 
Signature · 1 line
2.7.4
author maintainer Acked-by on v4 1/1
#40 lore raw

Re: [PATCH v4] sched: Update runnable propagation rule

Quoted 24 lines · Vincent Guittot

Unlike running, the runnable part can't be directly propagated through the hierarchy when we migrate a task. The main reason is that runnable time can be shared with other sched_entities that stay on the rq and this runnable time will also remain on prev cfs_rq and must not be removed.

Instead, we can estimate what should be the new runnable of the prev cfs_rq and check that this estimation stay in a possible range. The prop_runnable_sum is a good estimation when adding runnable_sum but fails most often when we remove it. Instead, we could use the formula below instead:

gcfs_rq's runnable_sum = gcfs_rq->avg.load_sum / gcfs_rq->load.weight

which assumes that tasks are equally runnable which is not true but easy to compute.

Beside these estimates, we have several simple rules that help us to filter out wrong ones:

- ge->avg.runnable_sum <= than LOAD_AVG_MAX
- ge->avg.runnable_sum >= ge->avg.running_sum (ge->avg.util_sum << LOAD_AVG_MAX)
- ge->avg.runnable_sum can't increase when we detach a task

Quoted 14 lines
Cc Yuyang Du <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Mike Galbraith <[email protected]>
Cc Chris Mason <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Dietmar Eggemann <[email protected]>
Cc Josef Bacik <[email protected]>
Cc Ben Segall <[email protected]>
Cc Paul Turner <[email protected]>
Cc Tejun Heo <[email protected]>
Cc Morten Rasmussen <[email protected]>

Ingo, can you stuff this in sched/urgent ?

#41 lore raw

Re: [PATCH v4] sched: Update runnable propagation rule

Quoted 40 lines · Peter Zijlstra
Quoted 24 lines · Vincent Guittot

Unlike running, the runnable part can't be directly propagated through the hierarchy when we migrate a task. The main reason is that runnable time can be shared with other sched_entities that stay on the rq and this runnable time will also remain on prev cfs_rq and must not be removed.

Instead, we can estimate what should be the new runnable of the prev cfs_rq and check that this estimation stay in a possible range. The prop_runnable_sum is a good estimation when adding runnable_sum but fails most often when we remove it. Instead, we could use the formula below instead:

gcfs_rq's runnable_sum = gcfs_rq->avg.load_sum / gcfs_rq->load.weight

which assumes that tasks are equally runnable which is not true but easy to compute.

Beside these estimates, we have several simple rules that help us to filter out wrong ones:

- ge->avg.runnable_sum <= than LOAD_AVG_MAX
- ge->avg.runnable_sum >= ge->avg.running_sum (ge->avg.util_sum << LOAD_AVG_MAX)
- ge->avg.runnable_sum can't increase when we detach a task

Quoted 14 lines
Cc Yuyang Du <[email protected]>
Cc Ingo Molnar <[email protected]>
Cc Mike Galbraith <[email protected]>
Cc Chris Mason <[email protected]>
Cc Linus Torvalds <[email protected]>
Cc Dietmar Eggemann <[email protected]>
Cc Josef Bacik <[email protected]>
Cc Ben Segall <[email protected]>
Cc Paul Turner <[email protected]>
Cc Tejun Heo <[email protected]>
Cc Morten Rasmussen <[email protected]>
Quoted 3 lines

Ingo, can you stuff this in sched/urgent ?

Yeah, I've queued up in tip:sched/urgent.

Thanks,

Ingo

#42 lore raw

[tip:sched/core] sched/fair: Update and fix the runnable propagation rule

In reply to Vincent Guittot
sched/fair: Update and fix the runnable propagation rule
Commit-ID:  a4c3c04974d648ee6e1a09ef4131eb32a02ab494
Gitweb:     https://git.kernel.org/tip/a4c3c04974d648ee6e1a09ef4131eb32a02ab494
Author:     Vincent Guittot <[email protected]>
AuthorDate: Thu, 16 Nov 2017 15:21:52 +0100
Committer:  Ingo Molnar <[email protected]>
CommitDate: Wed, 6 Dec 2017 19:30:50 +0100

sched/fair: Update and fix the runnable propagation rule

Unlike running, the runnable part can't be directly propagated through the hierarchy when we migrate a task. The main reason is that runnable time can be shared with other sched_entities that stay on the rq and this runnable time will also remain on prev cfs_rq and must not be removed.

Instead, we can estimate what should be the new runnable of the prev cfs_rq and check that this estimation stay in a possible range. The prop_runnable_sum is a good estimation when adding runnable_sum but fails most often when we remove it. Instead, we could use the formula below instead:

gcfs_rq's runnable_sum = gcfs_rq->avg.load_sum / gcfs_rq->load.weight

which assumes that tasks are equally runnable which is not true but easy to compute.

Beside these estimates, we have several simple rules that help us to filter out wrong ones:

- ge->avg.runnable_sum <= than LOAD_AVG_MAX
- ge->avg.runnable_sum >= ge->avg.running_sum (ge->avg.util_sum << LOAD_AVG_MAX)
- ge->avg.runnable_sum can't increase when we detach a task

The effect of these fixes is better cgroups balancing.

---
 kernel/sched/fair.c | 102 +++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 73 insertions(+), 29 deletions(-)
kernel/sched/fair.c +73 -29
index 4037e19..2fe3aa8 100644
@@ -3413,9 +3413,9 @@ void set_task_rq_fair(struct sched_entity *se,
  * _IFF_ we look at the pure running and runnable sums. Because they
  * represent the very same entity, just at different points in the hierarchy.
  *
- *
- * Per the above update_tg_cfs_util() is trivial (and still 'wrong') and
- * simply copies the running sum over.
+ * Per the above update_tg_cfs_util() is trivial and simply copies the running
+ * sum over (but still wrong, because the group entity and group rq do not have
+ * their PELT windows aligned).
  *
  * However, update_tg_cfs_runnable() is more complex. So we have:
  *
@@ -3424,11 +3424,11 @@ void set_task_rq_fair(struct sched_entity *se,
  * And since, like util, the runnable part should be directly transferable,
  * the following would _appear_ to be the straight forward approach:
  *
- *   grq->avg.load_avg = grq->load.weight * grq->avg.running_avg	(3)
+ *   grq->avg.load_avg = grq->load.weight * grq->avg.runnable_avg	(3)
  *
  * And per (1) we have:
  *
- *   ge->avg.running_avg == grq->avg.running_avg
+ *   ge->avg.runnable_avg == grq->avg.runnable_avg
  *
  * Which gives:
  *
@@ -3447,27 +3447,28 @@ void set_task_rq_fair(struct sched_entity *se,
  * to (shortly) return to us. This only works by keeping the weights as
  * integral part of the sum. We therefore cannot decompose as per (3).
  *
- * OK, so what then?
+ * Another reason this doesn't work is that runnable isn't a 0-sum entity.
+ * Imagine a rq with 2 tasks that each are runnable 2/3 of the time. Then the
+ * rq itself is runnable anywhere between 2/3 and 1 depending on how the
+ * runnable section of these tasks overlap (or not). If they were to perfectly
+ * align the rq as a whole would be runnable 2/3 of the time. If however we
+ * always have at least 1 runnable task, the rq as a whole is always runnable.
  *
+ * So we'll have to approximate.. :/
  *
- * Another way to look at things is:
+ * Given the constraint:
  *
- *   grq->avg.load_avg = \Sum se->avg.load_avg
+ *   ge->avg.running_sum <= ge->avg.runnable_sum <= LOAD_AVG_MAX
  *
- * Therefore, per (2):
+ * We can construct a rule that adds runnable to a rq by assuming minimal
+ * overlap.
  *
- *   grq->avg.load_avg = \Sum se->load.weight * se->avg.runnable_avg
+ * On removal, we'll assume each task is equally runnable; which yields:
  *
- * And the very thing we're propagating is a change in that sum (someone
- * joined/left). So we can easily know the runnable change, which would be, per
- * (2) the already tracked se->load_avg divided by the corresponding
- * se->weight.
+ *   grq->avg.runnable_sum = grq->avg.load_sum / grq->load.weight
  *
- * Basically (4) but in differential form:
+ * XXX: only do this for the part of runnable > running ?
  *
- *   d(runnable_avg) += se->avg.load_avg / se->load.weight
- *								   (5)
- *   ge->avg.load_avg += ge->load.weight * d(runnable_avg)
  */
 
 static inline void
@@ -3479,6 +3480,14 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq
 	if (!delta)
 		return;
 
+	/*
+	 * The relation between sum and avg is:
+	 *
+	 *   LOAD_AVG_MAX - 1024 + sa->period_contrib
+	 *
+	 * however, the PELT windows are not aligned between grq and gse.
+	 */
+
 	/* Set new sched_entity's utilization */
 	se->avg.util_avg = gcfs_rq->avg.util_avg;
 	se->avg.util_sum = se->avg.util_avg * LOAD_AVG_MAX;
@@ -3491,33 +3500,68 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq
 static inline void
 update_tg_cfs_runnable(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq *gcfs_rq)
 {
-	long runnable_sum = gcfs_rq->prop_runnable_sum;
-	long runnable_load_avg, load_avg;
-	s64 runnable_load_sum, load_sum;
+	long delta_avg, running_sum, runnable_sum = gcfs_rq->prop_runnable_sum;
+	unsigned long runnable_load_avg, load_avg;
+	u64 runnable_load_sum, load_sum = 0;
+	s64 delta_sum;
 
 	if (!runnable_sum)
 		return;
 
 	gcfs_rq->prop_runnable_sum = 0;
 
+	if (runnable_sum >= 0) {
+		/*
+		 * Add runnable; clip at LOAD_AVG_MAX. Reflects that until
+		 * the CPU is saturated running == runnable.
+		 */
+		runnable_sum += se->avg.load_sum;
+		runnable_sum = min(runnable_sum, (long)LOAD_AVG_MAX);
+	} else {
+		/*
+		 * Estimate the new unweighted runnable_sum of the gcfs_rq by
+		 * assuming all tasks are equally runnable.
+		 */
+		if (scale_load_down(gcfs_rq->load.weight)) {
+			load_sum = div_s64(gcfs_rq->avg.load_sum,
+				scale_load_down(gcfs_rq->load.weight));
+		}
+
+		/* But make sure to not inflate se's runnable */
+		runnable_sum = min(se->avg.load_sum, load_sum);
+	}
+
+	/*
+	 * runnable_sum can't be lower than running_sum
+	 * As running sum is scale with cpu capacity wehreas the runnable sum
+	 * is not we rescale running_sum 1st
+	 */
+	running_sum = se->avg.util_sum /
+		arch_scale_cpu_capacity(NULL, cpu_of(rq_of(cfs_rq)));
+	runnable_sum = max(runnable_sum, running_sum);
+
 	load_sum = (s64)se_weight(se) * runnable_sum;
 	load_avg = div_s64(load_sum, LOAD_AVG_MAX);
 
-	add_positive(&se->avg.load_sum, runnable_sum);
-	add_positive(&se->avg.load_avg, load_avg);
+	delta_sum = load_sum - (s64)se_weight(se) * se->avg.load_sum;
+	delta_avg = load_avg - se->avg.load_avg;
 
-	add_positive(&cfs_rq->avg.load_avg, load_avg);
-	add_positive(&cfs_rq->avg.load_sum, load_sum);
+	se->avg.load_sum = runnable_sum;
+	se->avg.load_avg = load_avg;
+	add_positive(&cfs_rq->avg.load_avg, delta_avg);
+	add_positive(&cfs_rq->avg.load_sum, delta_sum);
 
 	runnable_load_sum = (s64)se_runnable(se) * runnable_sum;
 	runnable_load_avg = div_s64(runnable_load_sum, LOAD_AVG_MAX);
+	delta_sum = runnable_load_sum - se_weight(se) * se->avg.runnable_load_sum;
+	delta_avg = runnable_load_avg - se->avg.runnable_load_avg;
 
-	add_positive(&se->avg.runnable_load_sum, runnable_sum);
-	add_positive(&se->avg.runnable_load_avg, runnable_load_avg);
+	se->avg.runnable_load_sum = runnable_sum;
+	se->avg.runnable_load_avg = runnable_load_avg;
 
 	if (se->on_rq) {
-		add_positive(&cfs_rq->avg.runnable_load_avg, runnable_load_avg);
-		add_positive(&cfs_rq->avg.runnable_load_sum, runnable_load_sum);
+		add_positive(&cfs_rq->avg.runnable_load_avg, delta_avg);
+		add_positive(&cfs_rq->avg.runnable_load_sum, delta_sum);
 	}
 }
 
author maintainer
#43 lore raw

PATCH 13/18 sched/fair: Propagate an effective runnable_load_avg

In reply to Peter Zijlstra

The load balancer uses runnable_load_avg as load indicator. For !cgroup this is:

runnable_load_avg = \Sum se->avg.load_avg ; where se->on_rq

That is, a direct sum of all runnable tasks on that runqueue. As opposed to load_avg, which is a sum of all tasks on the runqueue, which includes a blocked component.

However, in the cgroup case, this comes apart since the group entities are always runnable, even if most of their constituent entities are blocked.

Therefore introduce a runnable_weight which for task entities is the same as the regular weight, but for group entities is a fraction of the entity weight and represents the runnable part of the group runqueue.

Then propagate this load through the PELT hierarchy to arrive at an effective runnable load avgerage -- which we should not confuse with the canonical runnable load average.

---
 include/linux/sched.h |    3 
 kernel/sched/debug.c  |    8 ++
 kernel/sched/fair.c   |  173 ++++++++++++++++++++++++++++++++------------------
 kernel/sched/sched.h  |    3 
 4 files changed, 125 insertions(+), 62 deletions(-)
include/linux/sched.h +3 -0
@@ -332,9 +332,11 @@ struct load_weight {
 struct sched_avg {
 	u64				last_update_time;
 	u64				load_sum;
+	u64				runnable_load_sum;
 	u32				util_sum;
 	u32				period_contrib;
 	unsigned long			load_avg;
+	unsigned long			runnable_load_avg;
 	unsigned long			util_avg;
 };
 
@@ -377,6 +379,7 @@ struct sched_statistics {
 struct sched_entity {
 	/* For load-balancing: */
 	struct load_weight		load;
+	unsigned long			runnable_weight;
 	struct rb_node			run_node;
 	struct list_head		group_node;
 	unsigned int			on_rq;
kernel/sched/debug.c +7 -1
@@ -436,9 +436,11 @@ static void print_cfs_group_stats(struct
 		P_SCHEDSTAT(se->statistics.wait_count);
 	}
 	P(se->load.weight);
+	P(se->runnable_weight);
 #ifdef CONFIG_SMP
 	P(se->avg.load_avg);
 	P(se->avg.util_avg);
+	P(se->avg.runnable_load_avg);
 #endif
 
 #undef PN_SCHEDSTAT
@@ -555,10 +557,11 @@ void print_cfs_rq(struct seq_file *m, in
 	SEQ_printf(m, "  .%-30s: %d\n", "nr_running", cfs_rq->nr_running);
 	SEQ_printf(m, "  .%-30s: %ld\n", "load", cfs_rq->load.weight);
 #ifdef CONFIG_SMP
+	SEQ_printf(m, "  .%-30s: %ld\n", "runnable_weight", cfs_rq->runnable_weight);
 	SEQ_printf(m, "  .%-30s: %lu\n", "load_avg",
 			cfs_rq->avg.load_avg);
 	SEQ_printf(m, "  .%-30s: %lu\n", "runnable_load_avg",
-			cfs_rq->runnable_load_avg);
+			cfs_rq->avg.runnable_load_avg);
 	SEQ_printf(m, "  .%-30s: %lu\n", "util_avg",
 			cfs_rq->avg.util_avg);
 	SEQ_printf(m, "  .%-30s: %ld\n", "removed.load_avg",
@@ -1003,10 +1006,13 @@ void proc_sched_show_task(struct task_st
 		   "nr_involuntary_switches", (long long)p->nivcsw);
 
 	P(se.load.weight);
+	P(se.runnable_weight);
 #ifdef CONFIG_SMP
 	P(se.avg.load_sum);
+	P(se.avg.runnable_load_sum);
 	P(se.avg.util_sum);
 	P(se.avg.load_avg);
+	P(se.avg.runnable_load_avg);
 	P(se.avg.util_avg);
 	P(se.avg.last_update_time);
 #endif
kernel/sched/fair.c +113 -59

382 lines not on this page · raw message

kernel/sched/sched.h +1 -2
@@ -418,6 +418,7 @@ struct cfs_bandwidth { };
 /* CFS-related fields in a runqueue */
 struct cfs_rq {
 	struct load_weight load;
+	unsigned long runnable_weight;
 	unsigned int nr_running, h_nr_running;
 
 	u64 exec_clock;
@@ -444,8 +445,6 @@ struct cfs_rq {
 	 * CFS load tracking
 	 */
 	struct sched_avg avg;
-	u64 runnable_load_sum;
-	unsigned long runnable_load_avg;
 #ifndef CONFIG_64BIT
 	u64 load_last_update_time_copy;
 #endif
#44 lore raw

Re: [PATCH -v2 13/18] sched/fair: Propagate an effective runnable_load_avg

Quoted 30 lines · Peter Zijlstra

The load balancer uses runnable_load_avg as load indicator. For !cgroup this is:

runnable_load_avg = \Sum se->avg.load_avg ; where se->on_rq

That is, a direct sum of all runnable tasks on that runqueue. As opposed to load_avg, which is a sum of all tasks on the runqueue, which includes a blocked component.

However, in the cgroup case, this comes apart since the group entities are always runnable, even if most of their constituent entities are blocked.

Therefore introduce a runnable_weight which for task entities is the same as the regular weight, but for group entities is a fraction of the entity weight and represents the runnable part of the group runqueue.

Then propagate this load through the PELT hierarchy to arrive at an effective runnable load avgerage -- which we should not confuse with the canonical runnable load average.

---
 include/linux/sched.h |    3 
 kernel/sched/debug.c  |    8 ++
 kernel/sched/fair.c   |  173 ++++++++++++++++++++++++++++++++------------------
 kernel/sched/sched.h  |    3 
 4 files changed, 125 insertions(+), 62 deletions(-)

[...]

kernel/sched/fair.c static long calc_cfs_shares(struct cfs_r · line 2956

Quoted 10 lines
kernel/sched/fair.c +5 -1
@@ -2931,31 +2949,45 @@ static long calc_cfs_shares(struct cfs_r
 
 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq);
 
-static void update_cfs_shares(struct sched_entity *se)
+/*
+ * Recomputes the group entity based on the current state of its group
+ * runqueue.
+ */
+static void update_cfs_group(struct sched_entity *se)

update_cfs_share(s)() is still mentioned in the function header of update_tg_load_avg() and update_cfs_rq_load_avg().

Should we rename those comments with this patch?

IMHO, the comment for update_tg_load_avg() is still true whereas the one for update_cfs_rq_load_avg() mentions cfs_rq->avg as cfs_rq->avg.load_avg (or cfs_rq_load_avg()) and update_cfs_group() doesn't use it anymore. It's now used in calc_group_runnable() and calc_group_shares() instead.

[...]

author maintainer
#45 lore raw

Re: [PATCH -v2 13/18] sched/fair: Propagate an effective runnable_load_avg

Quoted 11 lines · Dietmar Eggemann

Review

Quoted 5 lines
(quoted diff) +5 -0
+/*
+ * Recomputes the group entity based on the current state of its group
+ * runqueue.
+ */
+static void update_cfs_group(struct sched_entity *se)

update_cfs_share(s)() is still mentioned in the function header of update_tg_load_avg() and update_cfs_rq_load_avg().

Should we rename those comments with this patch?

Quoted 7 lines

IMHO, the comment for update_tg_load_avg() is still true whereas the one for update_cfs_rq_load_avg() mentions cfs_rq->avg as cfs_rq->avg.load_avg (or cfs_rq_load_avg()) and update_cfs_group() doesn't use it anymore. It's now used in calc_group_runnable() and calc_group_shares() instead.

[...]

Right, so something like the below? Thinking that update_cfs_group() immediately leads to calc_group_*() so no need to spell those out.

kernel/sched/fair.c +2 -2
index 350dbec01523..fee2e34812da 100644
@@ -3333,7 +3333,7 @@ __update_load_avg_cfs_rq(u64 now, int cpu, struct cfs_rq *cfs_rq)
  * differential update where we store the last value we propagated. This in
  * turn allows skipping updates if the differential is 'small'.
  *
- * Updating tg's load_avg is necessary before update_cfs_share().
+ * Updating tg's load_avg is necessary before update_cfs_group().
  */
 static inline void update_tg_load_avg(struct cfs_rq *cfs_rq, int force)
 {
@@ -3601,7 +3601,7 @@ static inline void add_tg_cfs_propagate(struct cfs_rq *cfs_rq, long runnable_sum
  * avg. The immediate corollary is that all (fair) tasks must be attached, see
  * post_init_entity_util_avg().
  *
- * cfs_rq->avg is used for task_h_load() and update_cfs_share() for example.
+ * cfs_rq->avg is used for task_h_load() and update_cfs_group() for example.
  *
  * Returns true if the load decayed or we removed load.
  *
#46 lore raw

Re: [PATCH -v2 13/18] sched/fair: Propagate an effective runnable_load_avg

Quoted 19 lines · Peter Zijlstra
Quoted 17 lines · Dietmar Eggemann

Review

Quoted 5 lines
(quoted diff) +5 -0
+/*
+ * Recomputes the group entity based on the current state of its group
+ * runqueue.
+ */
+static void update_cfs_group(struct sched_entity *se)

update_cfs_share(s)() is still mentioned in the function header of update_tg_load_avg() and update_cfs_rq_load_avg().

Should we rename those comments with this patch?

IMHO, the comment for update_tg_load_avg() is still true whereas the one for update_cfs_rq_load_avg() mentions cfs_rq->avg as cfs_rq->avg.load_avg (or cfs_rq_load_avg()) and update_cfs_group() doesn't use it anymore. It's now used in calc_group_runnable() and calc_group_shares() instead.

Quoted 4 lines
Quoted 1 line

[...]

Right, so something like the below? Thinking that update_cfs_group() immediately leads to calc_group_*() so no need to spell those out.

Looks good to me, agreed.

Quoted 25 lines
kernel/sched/fair.c +2 -2
index 350dbec01523..fee2e34812da 100644
@@ -3333,7 +3333,7 @@ __update_load_avg_cfs_rq(u64 now, int cpu, struct cfs_rq *cfs_rq)
  * differential update where we store the last value we propagated. This in
  * turn allows skipping updates if the differential is 'small'.
  *
- * Updating tg's load_avg is necessary before update_cfs_share().
+ * Updating tg's load_avg is necessary before update_cfs_group().
  */
 static inline void update_tg_load_avg(struct cfs_rq *cfs_rq, int force)
 {
@@ -3601,7 +3601,7 @@ static inline void add_tg_cfs_propagate(struct cfs_rq *cfs_rq, long runnable_sum
  * avg. The immediate corollary is that all (fair) tasks must be attached, see
  * post_init_entity_util_avg().
  *
- * cfs_rq->avg is used for task_h_load() and update_cfs_share() for example.
+ * cfs_rq->avg is used for task_h_load() and update_cfs_group() for example.
  *
  * Returns true if the load decayed or we removed load.
  *
#47 lore raw

Re: [PATCH -v2 13/18] sched/fair: Propagate an effective runnable_load_avg

In reply to Peter Zijlstra

On 01/09/17 14:21, Peter Zijlstra wrote:

[...]

kernel/sched/fair.c ___update_load_sum(u64 now, int cpu, str · line 3200

Quoted 4 lines
kernel/sched/fair.c +0 -0
@@ -3169,8 +3198,8 @@ ___update_load_sum(u64 now, int cpu, str
 	 * this happens during idle_balance() which calls
 	 * update_blocked_averages()
 	 */

another nit-pick:

s/weight/load in comment above.

Quoted 4 lines
kernel/sched/fair.c +2 -2
-	if (!weight)
-		running = 0;
+	if (!load)
+		runnable = running = 0;

[...]

author maintainer
#48 lore raw

PATCH 14/18 sched/fair: Synchonous PELT detach on load-balance migrate

In reply to Peter Zijlstra

Vincent wondered why his self migrating task had a roughly 50% dip in load_avg when landing on the new CPU. This is because we uncondionally take the asynchronous detatch_entity route, which can lead to the attach on the new CPU still seeing the old CPU's contribution to tg->load_avg, effectively halving the new CPU's shares.

While in general this is something we have to live with, there is the special case of runnable migration where we can do better.

---
 kernel/sched/fair.c |   33 +++++++++++++++++++++------------
 1 file changed, 21 insertions(+), 12 deletions(-)
kernel/sched/fair.c +21 -12
@@ -3649,10 +3649,6 @@ void remove_entity_load_avg(struct sched
 	 * Similarly for groups, they will have passed through
 	 * post_init_entity_util_avg() before unregister_sched_fair_group()
 	 * calls this.
-	 *
-	 * XXX in case entity_is_task(se) && task_of(se)->on_rq == MIGRATING
-	 * we could actually get the right time, since we're called with
-	 * rq->lock held, see detach_task().
 	 */
 
 	sync_entity_load_avg(se);
@@ -6251,6 +6247,8 @@ select_task_rq_fair(struct task_struct *
 	return new_cpu;
 }
 
+static void detach_entity_cfs_rq(struct sched_entity *se);
+
 /*
  * Called immediately before a task is migrated to a new cpu; task_cpu(p) and
  * cfs_rq_of(p) references at time of call are still valid and identify the
@@ -6284,14 +6282,25 @@ static void migrate_task_rq_fair(struct
 		se->vruntime -= min_vruntime;
 	}
 
-	/*
-	 * We are supposed to update the task to "current" time, then its up to date
-	 * and ready to go to new CPU/cfs_rq. But we have difficulty in getting
-	 * what current time is, so simply throw away the out-of-date time. This
-	 * will result in the wakee task is less decayed, but giving the wakee more
-	 * load sounds not bad.
-	 */
-	remove_entity_load_avg(&p->se);
+	if (p->on_rq == TASK_ON_RQ_MIGRATING) {
+		/*
+		 * In case of TASK_ON_RQ_MIGRATING we in fact hold the 'old'
+		 * rq->lock and can modify state directly.
+		 */
+		lockdep_assert_held(&task_rq(p)->lock);
+		detach_entity_cfs_rq(&p->se);
+
+	} else {
+		/*
+		 * We are supposed to update the task to "current" time, then
+		 * its up to date and ready to go to new CPU/cfs_rq. But we
+		 * have difficulty in getting what current time is, so simply
+		 * throw away the out-of-date time. This will result in the
+		 * wakee task is less decayed, but giving the wakee more load
+		 * sounds not bad.
+		 */
+		remove_entity_load_avg(&p->se);
+	}
 
 	/* Tell new CPU we are migrated */
 	p->se.avg.last_update_time = 0;
author maintainer
#49 lore raw

PATCH 15/18 sched/fair: Align PELT windows between cfs_rq and its se

In reply to Peter Zijlstra

The PELT _sum values are a saw-tooth function, dropping on the decay edge and then growing back up again during the window.

When these window-edges are not aligned between cfs_rq and se, we can have the situation where, for example, on dequeue, the se decays first.

Its _sum values will be small(er), while the cfs_rq _sum values will still be on their way up. Because of this, the subtraction:
cfs_rq->avg._sum -= se->avg._sum will result in a positive value. This will then, once the cfs_rq reaches an edge, translate into its _avg value jumping up.

This is especially visible with the runnable_load bits, since they get added/subtracted a lot.

---
 kernel/sched/fair.c |   45 +++++++++++++++++++++++++++++++--------------
 1 file changed, 31 insertions(+), 14 deletions(-)
kernel/sched/fair.c +31 -14
@@ -729,13 +729,8 @@ void init_entity_runnable_average(struct
 {
 	struct sched_avg *sa = &se->avg;
 
-	sa->last_update_time = 0;
-	/*
-	 * sched_avg's period_contrib should be strictly less then 1024, so
-	 * we give it 1023 to make sure it is almost a period (1024us), and
-	 * will definitely be update (after enqueue).
-	 */
-	sa->period_contrib = 1023;
+	memset(sa, 0, sizeof(*sa));
+
 	/*
 	 * Tasks are intialized with full load to be seen as heavy tasks until
 	 * they get a chance to stabilize to their real load level.
@@ -744,13 +739,9 @@ void init_entity_runnable_average(struct
 	 */
 	if (entity_is_task(se))
 		sa->runnable_load_avg = sa->load_avg = scale_load_down(se->load.weight);
-	sa->runnable_load_sum = sa->load_sum = LOAD_AVG_MAX;
 
-	/*
-	 * At this point, util_avg won't be used in select_task_rq_fair anyway
-	 */
-	sa->util_avg = 0;
-	sa->util_sum = 0;
+	se->runnable_weight = se->load.weight;
+
 	/* when this task enqueue'ed, it will contribute to its cfs_rq's load_avg */
 }
 
@@ -798,7 +789,6 @@ void post_init_entity_util_avg(struct sc
 		} else {
 			sa->util_avg = cap;
 		}
-		sa->util_sum = sa->util_avg * LOAD_AVG_MAX;
 	}
 
 	if (entity_is_task(se)) {
@@ -3644,7 +3634,34 @@ update_cfs_rq_load_avg(u64 now, struct c
  */
 static void attach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
+	u32 divider = LOAD_AVG_MAX - 1024 + cfs_rq->avg.period_contrib;
+
+	/*
+	 * When we attach the @se to the @cfs_rq, we must align the decay
+	 * window because without that, really weird and wonderful things can
+	 * happen.
+	 *
+	 * XXX illustrate
+	 */
 	se->avg.last_update_time = cfs_rq->avg.last_update_time;
+	se->avg.period_contrib = cfs_rq->avg.period_contrib;
+
+	/*
+	 * Hell(o) Nasty stuff.. we need to recompute _sum based on the new
+	 * period_contrib. This isn't strictly correct, but since we're
+	 * entirely outside of the PELT hierarchy, nobody cares if we truncate
+	 * _sum a little.
+	 */
+	se->avg.util_sum = se->avg.util_avg * divider;
+
+	se->avg.load_sum = divider;
+	if (se_weight(se)) {
+		se->avg.load_sum =
+			div_u64(se->avg.load_avg * se->avg.load_sum, se_weight(se));
+	}
+
+	se->avg.runnable_load_sum = se->avg.load_sum;
+
 	enqueue_load_avg(cfs_rq, se);
 	cfs_rq->avg.util_avg += se->avg.util_avg;
 	cfs_rq->avg.util_sum += se->avg.util_sum;
#50 lore raw

Re: [PATCH -v2 15/18] sched/fair: Align PELT windows between cfs_rq and its se

Quoted 20 lines · Peter Zijlstra

The PELT _sum values are a saw-tooth function, dropping on the decay edge and then growing back up again during the window.

When these window-edges are not aligned between cfs_rq and se, we can have the situation where, for example, on dequeue, the se decays first.

Its _sum values will be small(er), while the cfs_rq _sum values will still be on their way up. Because of this, the subtraction:
cfs_rq->avg._sum -= se->avg._sum will result in a positive value. This will then, once the cfs_rq reaches an edge, translate into its _avg value jumping up.

This is especially visible with the runnable_load bits, since they get added/subtracted a lot.

---
 kernel/sched/fair.c |   45 +++++++++++++++++++++++++++++++--------------
 1 file changed, 31 insertions(+), 14 deletions(-)

[...]

Quoted 19 lines
kernel/sched/fair.c +14 -0
@@ -3644,7 +3634,34 @@ update_cfs_rq_load_avg(u64 now, struct c
  */
 static void attach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
+	u32 divider = LOAD_AVG_MAX - 1024 + cfs_rq->avg.period_contrib;
+
+	/*
+	 * When we attach the @se to the @cfs_rq, we must align the decay
+	 * window because without that, really weird and wonderful things can
+	 * happen.
+	 *
+	 * XXX illustrate
+	 */
 	se->avg.last_update_time = cfs_rq->avg.last_update_time;
+	se->avg.period_contrib = cfs_rq->avg.period_contrib;
+
+	/*
+	 * Hell(o) Nasty stuff.. we need to recompute _sum based on the new
+	 * period_contrib. This isn't strictly correct, but since we're

kernel/sched/fair.c update_cfs_rq_load_avg(u64 now, struct c · line 3661

Quoted 10 lines
kernel/sched/fair.c +10 -0
+	 * entirely outside of the PELT hierarchy, nobody cares if we truncate
+	 * _sum a little.
+	 */
+	se->avg.util_sum = se->avg.util_avg * divider;
+
+	se->avg.load_sum = divider;
+	if (se_weight(se)) {
+		se->avg.load_sum =
+			div_u64(se->avg.load_avg * se->avg.load_sum, se_weight(se));
+	}

Can scale_load_down(se->load.weight) ever become 0 here?

[...]

author maintainer
#51 lore raw

Re: [PATCH -v2 15/18] sched/fair: Align PELT windows between cfs_rq and its se

Quoted 47 lines · Dietmar Eggemann
Quoted 20 lines · Peter Zijlstra

The PELT _sum values are a saw-tooth function, dropping on the decay edge and then growing back up again during the window.

When these window-edges are not aligned between cfs_rq and se, we can have the situation where, for example, on dequeue, the se decays first.

Its _sum values will be small(er), while the cfs_rq _sum values will still be on their way up. Because of this, the subtraction:
cfs_rq->avg._sum -= se->avg._sum will result in a positive value. This will then, once the cfs_rq reaches an edge, translate into its _avg value jumping up.

This is especially visible with the runnable_load bits, since they get added/subtracted a lot.

---
 kernel/sched/fair.c |   45 +++++++++++++++++++++++++++++++--------------
 1 file changed, 31 insertions(+), 14 deletions(-)

[...]

Quoted 23 lines
kernel/sched/fair.c +18 -0
@@ -3644,7 +3634,34 @@ update_cfs_rq_load_avg(u64 now, struct c
  */
 static void attach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
+	u32 divider = LOAD_AVG_MAX - 1024 + cfs_rq->avg.period_contrib;
+
+	/*
+	 * When we attach the @se to the @cfs_rq, we must align the decay
+	 * window because without that, really weird and wonderful things can
+	 * happen.
+	 *
+	 * XXX illustrate
+	 */
 	se->avg.last_update_time = cfs_rq->avg.last_update_time;
+	se->avg.period_contrib = cfs_rq->avg.period_contrib;
+
+	/*
+	 * Hell(o) Nasty stuff.. we need to recompute _sum based on the new
+	 * period_contrib. This isn't strictly correct, but since we're
+	 * entirely outside of the PELT hierarchy, nobody cares if we truncate
+	 * _sum a little.
+	 */
+	se->avg.util_sum = se->avg.util_avg * divider;
Quoted 8 lines

kernel/sched/fair.c update_cfs_rq_load_avg(u64 now, struct c · line 3661

Quoted 6 lines
kernel/sched/fair.c +6 -0
+
+	se->avg.load_sum = divider;
+	if (se_weight(se)) {
+		se->avg.load_sum =
+			div_u64(se->avg.load_avg * se->avg.load_sum, se_weight(se));
+	}

Can scale_load_down(se->load.weight) ever become 0 here?

Yeah, don't see why not.

#52 lore raw

Re: [PATCH -v2 15/18] sched/fair: Align PELT windows between cfs_rq and its se

Quoted 57 lines · Peter Zijlstra
Quoted 47 lines · Dietmar Eggemann
Quoted 20 lines · Peter Zijlstra

The PELT _sum values are a saw-tooth function, dropping on the decay edge and then growing back up again during the window.

When these window-edges are not aligned between cfs_rq and se, we can have the situation where, for example, on dequeue, the se decays first.

Its _sum values will be small(er), while the cfs_rq _sum values will still be on their way up. Because of this, the subtraction:
cfs_rq->avg._sum -= se->avg._sum will result in a positive value. This will then, once the cfs_rq reaches an edge, translate into its _avg value jumping up.

This is especially visible with the runnable_load bits, since they get added/subtracted a lot.

---
 kernel/sched/fair.c |   45 +++++++++++++++++++++++++++++++--------------
 1 file changed, 31 insertions(+), 14 deletions(-)

[...]

Quoted 23 lines
kernel/sched/fair.c +18 -0
@@ -3644,7 +3634,34 @@ update_cfs_rq_load_avg(u64 now, struct c
  */
 static void attach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
 {
+	u32 divider = LOAD_AVG_MAX - 1024 + cfs_rq->avg.period_contrib;
+
+	/*
+	 * When we attach the @se to the @cfs_rq, we must align the decay
+	 * window because without that, really weird and wonderful things can
+	 * happen.
+	 *
+	 * XXX illustrate
+	 */
 	se->avg.last_update_time = cfs_rq->avg.last_update_time;
+	se->avg.period_contrib = cfs_rq->avg.period_contrib;
+
+	/*
+	 * Hell(o) Nasty stuff.. we need to recompute _sum based on the new
+	 * period_contrib. This isn't strictly correct, but since we're
+	 * entirely outside of the PELT hierarchy, nobody cares if we truncate
+	 * _sum a little.
+	 */
+	se->avg.util_sum = se->avg.util_avg * divider;
Quoted 8 lines

kernel/sched/fair.c update_cfs_rq_load_avg(u64 now, struct c · line 3661

Quoted 6 lines
kernel/sched/fair.c +6 -0
+
+	se->avg.load_sum = divider;
+	if (se_weight(se)) {
+		se->avg.load_sum =
+			div_u64(se->avg.load_avg * se->avg.load_sum, se_weight(se));
+	}

Can scale_load_down(se->load.weight) ever become 0 here?

Quoted 1 line

Yeah, don't see why not.

Tasks should be safe since for them scale_load_down(se->load.weight) should be >= 15 when they get attached.

task groups get attached via attach_entity_cfs_rq()

# mkdir /sys/fs/cgroup/foo
[   63.885333] [<ffff00000811a558>] attach_entity_load_avg+0x138/0x558
[   63.885345] [<ffff0000081208e0>] attach_entity_cfs_rq+0x298/0x998
[   63.885357] [<ffff00000812d660>] online_fair_sched_group+0x70/0xb0
[   63.885369] [<ffff0000081182d4>] sched_online_group+0x94/0xb0
[   63.885381] [<ffff000008118318>] cpu_cgroup_css_online+0x28/0x38
[   63.885393] [<ffff0000081a5e80>] online_css+0x38/0xd0
[   63.885406] [<ffff0000081acae0>] cgroup_apply_control_enable+0x260
[   63.885418] [<ffff0000081afc54>] cgroup_mkdir+0x314/0x4e8

mkdir-2501 [004] 63.689455: bprint:
attach_entity_load_avg: cpu=1 se=0xffff800072fffc00 load.weight=1048576

If I apply the smallest shares possible to that task group, it is already attched.

# echo 2 > /sys/fs/cgroup/foo/cpu.shares

create_cpu_cgro-2500 [003] 64.591878: bprint:
update_cfs_group: cpu=1 se=0xffff800072fffc00 tg->shares=2048 shares=0 load=0 tg_weight=0
create_cpu_cgro-2500 [003] 64.591904: bprint:
reweight_entity: cpu=1 se=0xffff800072fffc00 se->load.weight=2

I can't see right now how a task group can get attached with se->load.weight < 1024 (32 bit)/1048576 (64 bit)? Do I miss something?

author maintainer
#53 lore raw

Re: [PATCH -v2 15/18] sched/fair: Align PELT windows between cfs_rq and its se

Quoted 2 lines · Dietmar Eggemann

I can't see right now how a task group can get attached with se->load.weight < 1024 (32 bit)/1048576 (64 bit)? Do I miss something?

Ah, I think I made a think-o, I think I considered migration for group entities, but those don't migrate.

author maintainer
#54 lore raw

PATCH 16/18 sched/fair: More accurate async detach

In reply to Peter Zijlstra

The problem with the overestimate is that it will subtract too big a value from the load_sum, thereby pushing it down further than it ought to go. Since runnable_load_avg is not subject to a similar 'force', this results in the occasional 'runnable_load > load' situation.

---
 kernel/sched/fair.c |    9 +++------
 1 file changed, 3 insertions(+), 6 deletions(-)
kernel/sched/fair.c +3 -6
@@ -3469,6 +3469,7 @@ update_cfs_rq_load_avg(u64 now, struct c
 
 	if (cfs_rq->removed.nr) {
 		unsigned long r;
+		u32 divider = LOAD_AVG_MAX - 1024 + sa->period_contrib;
 
 		raw_spin_lock(&cfs_rq->removed.lock);
 		swap(cfs_rq->removed.util_avg, removed_util);
@@ -3477,17 +3478,13 @@ update_cfs_rq_load_avg(u64 now, struct c
 		cfs_rq->removed.nr = 0;
 		raw_spin_unlock(&cfs_rq->removed.lock);
 
-		/*
-		 * The LOAD_AVG_MAX for _sum is a slight over-estimate,
-		 * which is safe due to sub_positive() clipping at 0.
-		 */
 		r = removed_load;
 		sub_positive(&sa->load_avg, r);
-		sub_positive(&sa->load_sum, r * LOAD_AVG_MAX);
+		sub_positive(&sa->load_sum, r * divider);
 
 		r = removed_util;
 		sub_positive(&sa->util_avg, r);
-		sub_positive(&sa->util_sum, r * LOAD_AVG_MAX);
+		sub_positive(&sa->util_sum, r * divider);
 
 		add_tg_cfs_propagate(cfs_rq, -(long)removed_runnable_sum);
 
author maintainer
#55 lore raw

PATCH 17/18 sched/fair: Calculate runnable_weight slightly differently

In reply to Peter Zijlstra

From: Josef Bacik <[email protected]>

Our runnable_weight currently looks like this

runnable_weight = shares * runnable_load_avg / load_avg

The goal is to scale the runnable weight for the group based on its runnable to load_avg ratio. The problem with this is it biases us towards tasks that never go to sleep. Tasks that go to sleep are going to have their runnable_load_avg decayed pretty hard, which will drastically reduce the runnable weight of groups with interactive tasks. To solve this imbalance we tweak this slightly, so in the ideal case it is still the above, but in the interactive case it is

runnable_weight = shares * runnable_weight / load_weight

which will make the weight distribution fairer between interactive and non-interactive groups.

---
 kernel/sched/fair.c |   45 +++++++++++++++++++++++++++++++++------------
 1 file changed, 33 insertions(+), 12 deletions(-)
kernel/sched/fair.c +33 -12
@@ -2897,7 +2897,7 @@ void reweight_task(struct task_struct *p
  *
  * hence icky!
  */
-static long calc_cfs_shares(struct cfs_rq *cfs_rq)
+static long calc_group_shares(struct cfs_rq *cfs_rq)
 {
 	long tg_weight, tg_shares, load, shares;
 	struct task_group *tg = cfs_rq->tg;
@@ -2934,6 +2934,36 @@ static long calc_cfs_shares(struct cfs_r
 	 */
 	return clamp_t(long, shares, MIN_SHARES, tg_shares);
 }
+
+/*
+ * The runnable shares of this group are calculated as such
+ *
+ *          max(cfs_rq->avg.runnable_load_avg, cfs_rq->runnable_weight)
+ * shares * ------------------------------------------------------------
+ *               max(cfs_rq->avg.load_avg, cfs_rq->load.weight)
+ *
+ * We do this to keep the shares in line with expected load on the cfs_rq.
+ * Consider a cfs_rq that has several tasks wake up on this cfs_rq for the first
+ * time, it's runnable_load_avg is not going to be representative of the actual
+ * load this cfs_rq will now experience, which will bias us agaisnt this cfs_rq.
+ * The weight on the cfs_rq is the immediate effect of having new tasks
+ * enqueue'd onto it which should be used to calculate the new runnable shares.
+ * At the same time we need the actual load_avg to be the lower bounds for the
+ * calculation, to handle when our weight drops quickly from having entities
+ * dequeued.
+ */
+static long calc_group_runnable(struct cfs_rq *cfs_rq, long shares)
+{
+	long load_avg = max(cfs_rq->avg.load_avg,
+			    scale_load_down(cfs_rq->load.weight));
+	long runnable = max(cfs_rq->avg.runnable_load_avg,
+			    scale_load_down(cfs_rq->runnable_weight));
+
+	runnable *= shares;
+	if (load_avg)
+		runnable /= load_avg;
+	return clamp_t(long, runnable, MIN_SHARES, shares);
+}
 # endif /* CONFIG_SMP */
 
 static inline int throttled_hierarchy(struct cfs_rq *cfs_rq);
@@ -2959,17 +2989,8 @@ static void update_cfs_group(struct sche
 	if (likely(se->load.weight == shares))
 		return;
 #else
-	shares = calc_cfs_shares(gcfs_rq);
-	/*
-	 * The hierarchical runnable load metric is the proportional part
-	 * of this group's runnable_load_avg / load_avg.
-	 *
-	 * Note: we need to deal with very sporadic 'runnable > load' cases
-	 * due to numerical instability.
-	 */
-	runnable = shares * gcfs_rq->avg.runnable_load_avg;
-	if (runnable)
-		runnable /= max(gcfs_rq->avg.load_avg, gcfs_rq->avg.runnable_load_avg);
+	shares   = calc_group_shares(gcfs_rq);
+	runnable = calc_group_runnable(gcfs_rq, shares);
 #endif
 
 	reweight_entity(cfs_rq_of(se), se, shares, runnable);
author maintainer
#56 lore raw

PATCH 18/18 sched/fair: Update calc_group_*() comments

In reply to Peter Zijlstra

I had a wee bit of trouble recalling how the calc_group_runnable() stuff worked.. add hopefully better comments.

---
 kernel/sched/fair.c |   68 ++++++++++++++++++++++++++++++++++------------------
 1 file changed, 45 insertions(+), 23 deletions(-)
kernel/sched/fair.c +45 -23
@@ -2874,7 +2874,7 @@ void reweight_task(struct task_struct *p
  * Now, in that special case (1) reduces to:
  *
  *                     tg->weight * grq->load.weight
- *   ge->load.weight = ----------------------------- = tg>weight   (4)
+ *   ge->load.weight = ----------------------------- = tg->weight   (4)
  *			    grp->load.weight
  *
  * That is, the sum collapses because all other CPUs are idle; the UP scenario.
@@ -2888,6 +2888,18 @@ void reweight_task(struct task_struct *p
  *     ---------------------------------------------------         (5)
  *     tg->load_avg - grq->avg.load_avg + grq->load.weight
  *
+ * But because grq->load.weight can drop to 0, resulting in a divide by zero,
+ * we need to use grq->avg.load_avg as its lower bound, which then gives:
+ *
+ *
+ *                     tg->weight * grq->load.weight
+ *   ge->load.weight = -----------------------------		   (6)
+ *				tg_load_avg'
+ *
+ * Where:
+ *
+ *   tg_load_avg' = tg->load_avg - grq->avg.load_avg +
+ *                  max(grq->load.weight, grq->avg.load_avg)
  *
  * And that is shares_weight and is icky. In the (near) UP case it approaches
  * (4) while in the normal case it approaches (3). It consistently
@@ -2904,10 +2916,6 @@ static long calc_group_shares(struct cfs
 
 	tg_shares = READ_ONCE(tg->shares);
 
-	/*
-	 * Because (5) drops to 0 when the cfs_rq is idle, we need to use (3)
-	 * as a lower bound.
-	 */
 	load = max(scale_load_down(cfs_rq->load.weight), cfs_rq->avg.load_avg);
 
 	tg_weight = atomic_long_read(&tg->load_avg);
@@ -2936,32 +2944,46 @@ static long calc_group_shares(struct cfs
 }
 
 /*
- * The runnable shares of this group are calculated as such
+ * This calculates the effective runnable weight for a group entity based on
+ * the group entity weight calculated above.
+ *
+ * Because of the above approximation (2), our group entity weight is
+ * an load_avg based ratio (3). This means that it includes blocked load and
+ * does not represent the runnable weight.
  *
- *          max(cfs_rq->avg.runnable_load_avg, cfs_rq->runnable_weight)
- * shares * ------------------------------------------------------------
- *               max(cfs_rq->avg.load_avg, cfs_rq->load.weight)
- *
- * We do this to keep the shares in line with expected load on the cfs_rq.
- * Consider a cfs_rq that has several tasks wake up on this cfs_rq for the first
- * time, it's runnable_load_avg is not going to be representative of the actual
- * load this cfs_rq will now experience, which will bias us agaisnt this cfs_rq.
- * The weight on the cfs_rq is the immediate effect of having new tasks
- * enqueue'd onto it which should be used to calculate the new runnable shares.
- * At the same time we need the actual load_avg to be the lower bounds for the
- * calculation, to handle when our weight drops quickly from having entities
- * dequeued.
+ * Approximate the group entity's runnable weight per ratio from the group
+ * runqueue:
+ *
+ *					     grq->avg.runnable_load_avg
+ *   ge->runnable_weight = ge->load.weight * -------------------------- (7)
+ *						 grq->avg.load_avg
+ *
+ * However, analogous to above, since the avg numbers are slow, this leads to
+ * transients in the from-idle case. Instead we use:
+ *
+ *   ge->runnable_weight = ge->load.weight *
+ *
+ *		max(grq->avg.runnable_load_avg, grq->runnable_weight)
+ *		-----------------------------------------------------	(8)
+ *		      max(grq->avg.load_avg, grq->load.weight)
+ *
+ * Where these max() serve both to use the 'instant' values to fix the slow
+ * from-idle and avoid the /0 on to-idle, similar to (6).
  */
 static long calc_group_runnable(struct cfs_rq *cfs_rq, long shares)
 {
-	long load_avg = max(cfs_rq->avg.load_avg,
-			    scale_load_down(cfs_rq->load.weight));
-	long runnable = max(cfs_rq->avg.runnable_load_avg,
-			    scale_load_down(cfs_rq->runnable_weight));
+	long runnable, load_avg;
+
+	load_avg = max(cfs_rq->avg.load_avg,
+		       scale_load_down(cfs_rq->load.weight));
+
+	runnable = max(cfs_rq->avg.runnable_load_avg,
+		       scale_load_down(cfs_rq->runnable_weight));
 
 	runnable *= shares;
 	if (load_avg)
 		runnable /= load_avg;
+
 	return clamp_t(long, runnable, MIN_SHARES, shares);
 }
 # endif /* CONFIG_SMP */