sched/fair: A bit of a cgroup/PELT overhaul
Peter Zijlstra
maintainercover 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.
Peter Zijlstra
maintainerPATCH 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(ststatic 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 schif (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); }
Peter Zijlstra
maintainerPATCH 2/18 sched/fair: Add comment to calc_cfs_shares()
In reply to Peter ZijlstraExplain 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;
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.Signed-off-by Peter Zijlstra (Intel) <[email protected]>--- 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 = 1024tg->load_avg = 2560
\Sum grq->load.weight = 2048
cpu 0 1 \Sumgrq->avg.load_avg 1536 1024grq->load.weight 1024 1024ge->load_weight (1) 512 512 1024 >= tg->weightge->load_weight (3) 614 410 1024 >= tg->weightge->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
Peter Zijlstra
maintainerRe: [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)
+ * \Sumgrq->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~= \Sumgrq->avg.load_avg
+ *
+ * That isshares_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 theQuoted 8 lines
+ * one task. It takes time for our CPU's
grq->avg.load_avgto 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_avgandgrq->avg.load_avgin
(3) aren't in sync, or there are stale contributions totg->load_avgfrom other cpus then (3) can return anything between 0 andtg->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 isshares_weightand is icky. In the (near) UP case it approaches
+ * (4) while in the normal case it approaches (3). It consistently
+ * overestimates thege->load.weightand therefore:
+ *
+ * \Sumge->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 thege->load.weightfor some of the group entities lead to \Sumge->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.
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 thege->load.weightfor some of the group entities lead to \Sumge->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.
Peter Zijlstra
maintainerPATCH 3/18 sched/fair: Cure calc_cfs_shares() vs reweight_entity()
In reply to Peter ZijlstraVincent 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);
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_avgdropped to 0 on task idle.This is because
reweight_entity()will now immediately propagate the weight change of the group entity to itscfs_rq, and as it happens, our approxmation (5) forcalc_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.
Reported-by Vincent Guittot <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>--- 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
Peter Zijlstra
maintainerRe: [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 ofcfs_rq->avg.load_avg) instead ofcfs_rq->avg.load_avgfurther 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.
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 ofcfs_rq->avg.load_avg) instead ofcfs_rq->avg.load_avgfurther 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_contribbecause that is what's inclded intg_weight, but we want to add the most up-to-date value back in.
Agreed. Looking at it again it make sense.
Peter Zijlstra
maintainerPATCH 4/18 sched/fair: Remove se->load.weight from se->avg.load_sum
In reply to Peter ZijlstraRemove 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, strif (!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(strucstatic 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 *cstatic 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
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= \Sumse_weight(se)*se->avg.load_sum
+ *load_avg= \Sumse->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 :-)
Peter Zijlstra
maintainerRe: [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= \Sumse_weight(se)*se->avg.load_sum
+ *load_avg= \Sumse->avg.load_avg
+ */I find it a bit confusing that
load_sumandload_avghave different definitions, but I guess I will discover why dropping weight fromse->avg.load_sumhelps 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_rqas 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_sumandrunnable_avgin 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 ;-)
Peter Zijlstra
maintainerPATCH 5/18 sched/fair: Change update_load_avg() arguments
In reply to Peter ZijlstraMost 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, structif (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 rqif (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(struif (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(structstruct 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_grq_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);
Peter Zijlstra
maintainerPATCH 6/18 sched/fair: Move enqueue migrate handling
In reply to Peter ZijlstraMove 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 creturn 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(struccfs_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 0x0static 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);
Peter Zijlstra
maintainerPATCH 7/18 sched/fair: Rename {en,de}queue_entity_load_avg()
In reply to Peter ZijlstraSince 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);
Peter Zijlstra
maintainerPATCH 8/18 sched/fair: Introduce {en,de}queue_load_avg()
In reply to Peter ZijlstraAnalogous 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 cpreturn 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 cstatic 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(strucupdate_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(struccfs_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
Peter Zijlstra
maintainerPATCH 9/18 sched/fair: More accurate reweight_entity()
In reply to Peter ZijlstraWhen 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.
--- 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_rif (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);
Peter Zijlstra
maintainerPATCH 10/18 sched/fair: Use reweight_entity() for set_user_nice()
In reply to Peter ZijlstraFrom: 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.
--- 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 *pput_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);
Peter Zijlstra
maintainerPATCH 11/18 sched/fair: Rewrite cfs_rq->removed_*avg
In reply to Peter ZijlstraSince 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 /*
Peter Zijlstra
maintainerPATCH 12/18 sched/fair: Rewrite PELT migration propagation
In reply to Peter ZijlstraWhen 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_avgBut 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) *
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_avgBut that is the expression for
ge->weight, and per the definition ofload_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.Signed-off-by Peter Zijlstra (Intel) <[email protected]>--- 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) +*/ +
Peter Zijlstra
maintainerRe: [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_avginstead ofrunning_avg?
Yes very much so. Typing hard. Otherwise (3) would not follow from (2) either.
Quoted 8 lines
cfs_rq->avg.load_avghas been defined previous (in patch 2 I think) to be:load_avg = \Sum se->avg.load_avg = \Sum se->load.weight * se->avg.runnable_avgThat sum will increase when ge is runnable regardless of whether it is running or not. So, I think it has to be
runnable_avgto 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
@@ -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. *
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_avginstead ofrunning_avg?Yes very much so. Typing hard. Otherwise (3) would not follow from (2) either.
Quoted 8 lines
cfs_rq->avg.load_avghas been defined previous (in patch 2 I think) to be:load_avg = \Sum se->avg.load_avg = \Sum se->load.weight * se->avg.runnable_avgThat sum will increase when ge is runnable regardless of whether it is running or not. So, I think it has to be
runnable_avgto 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.weightand 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
Peter Zijlstra
maintainerRe: [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.. :/
Vincent Guittot
maintainerRe: [PATCH -v2 12/18] sched/fair: Rewrite PELT migration propagation
In reply to Peter ZijlstraHi 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_avgBut that is the expression for
ge->weight, and per the definition ofload_avg:
ge->avg.load_avg:=ge->weight*ge->avg.runnable_avgThat destroys the
runnable_avg(by setting it to 1) we wanted to propagate.Instead directly propagate
runnable_sum.Signed-off-by Peter Zijlstra (Intel) <[email protected]>--- 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]
Vincent Guittot
maintainerRe: [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_avgBut that is the expression for
ge->weight, and per the definition ofload_avg:
ge->avg.load_avg:=ge->weight*ge->avg.runnable_avgThat destroys the
runnable_avg(by setting it to 1) we wanted to propagate.Instead directly propagate
runnable_sum.Signed-off-by Peter Zijlstra (Intel) <[email protected]>--- 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_rqbut 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_sumisLOAD_AVG_MAXfor each task
Thegrq->avg.load_sum= \Sumse->avg.load_sum= 2*LOAD_AVG_MAX But
thege->avg.load_sumwill be onlyLOAD_AVG_MAXSo If we apply directly the
d(TB->avg.load_sum)on the group hierachy and onge->avg.load_sumin 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_sumbut we can have a rough estimate with grq->avg.load_avg/grq->weightQuoted 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]
Peter Zijlstra
maintainerRe: [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 asched_entityjoins/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_rqbut 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_sumisLOAD_AVG_MAXfor each task Thegrq->avg.load_sum= \Sumse->avg.load_sum= 2*LOAD_AVG_MAX But thege->avg.load_sumwill be onlyLOAD_AVG_MAXSo If we apply directly the
d(TB->avg.load_sum)on the group hierachy and onge->avg.load_sumin particular, the latter decreases to 0 whereas it should decrease only by halfI 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_sumdelta =
se->avg.load_sum/ (grq->avg.load_sum+se->avg.load_sum) *ge->avg.load_sumas the se has already been detached
Quoted 2 lines
We don't have
grq->avg.load_sumbut 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.
Vincent Guittot
maintainerRe: [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 asched_entityjoins/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_rqbut 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_sumisLOAD_AVG_MAXfor each task Thegrq->avg.load_sum= \Sumse->avg.load_sum= 2*LOAD_AVG_MAX But thege->avg.load_sumwill be onlyLOAD_AVG_MAXSo If we apply directly the
d(TB->avg.load_sum)on the group hierachy and onge->avg.load_sumin particular, the latter decreases to 0 whereas it should decrease only by halfQuoted 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_sumdelta =
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_sumbut we can have a rough estimate with grq->avg.load_avg/grq->weightHurm, 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
Vincent Guittot
maintainerRe: [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 asched_entityjoins/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_rqbut 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_sumisLOAD_AVG_MAXfor each task Thegrq->avg.load_sum= \Sumse->avg.load_sum= 2*LOAD_AVG_MAX But thege->avg.load_sumwill be onlyLOAD_AVG_MAXSo If we apply directly the
d(TB->avg.load_sum)on the group hierachy and onge->avg.load_sumin particular, the latter decreases to 0 whereas it should decrease only by halfQuoted 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_sumdelta =
se->avg.load_sum/ (grq->avg.load_sum+se->avg.load_sum) *ge->avg.load_sumas 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_sumbut we can have a rough estimate with grq->avg.load_avg/grq->weightHurm, 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
@@ -3489,33 +3489,67 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rqstatic 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
Peter Zijlstra
maintainerRe: [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_sumcan't be higher thanLOAD_AVG_MAX
-ge->avg.runnable_sumcan't be lower thange->avg.running_sum(once scaled to the same range)
- we can't directly propagate a negative delta ofrunnable_sumbecause part of this runnable time can be "shared" with otherssched_entitiesand stays on thegcfs_rq.
Right, that's about how far I got.
Quoted 1 line
-
ge->avg.runnable_sumcan't increase when we detach a task.
Yeah, that would be fairly broken.
Quoted 1 line
Instead, we can't estimate the new
runnable_sumof thegcfs_rqwith
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@@ -3489,33 +3489,67 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rqstatic 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
-0gcfs_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
Vincent Guittot
maintainerRe: [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_sumcan't be higher thanLOAD_AVG_MAX
-ge->avg.runnable_sumcan't be lower thange->avg.running_sum(once scaled to the same range)
- we can't directly propagate a negative delta ofrunnable_sumbecause part of this runnable time can be "shared" with otherssched_entitiesand stays on thegcfs_rq.Right, that's about how far I got.
Quoted 7 lines
Quoted 1 line
-
ge->avg.runnable_sumcan't increase when we detach a task.Yeah, that would be fairly broken.
Quoted 1 line
Instead, we can't estimate the new
runnable_sumof thegcfs_rqwiths/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@@ -3489,33 +3489,67 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rqstatic 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
-0gcfs_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
Vincent Guittot
maintainerRe: [PATCH -v2 12/18] sched/fair: Rewrite PELT migration propagation
In reply to Peter ZijlstraHi 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_sumcan't be higher thanLOAD_AVG_MAX
-ge->avg.runnable_sumcan't be lower thange->avg.running_sum(once scaled to the same range)
- we can't directly propagate a negative delta ofrunnable_sumbecause part of this runnable time can be "shared" with otherssched_entitiesand stays on thegcfs_rq.Right, that's about how far I got.
Quoted 1 line
-
ge->avg.runnable_sumcan't increase when we detach a task.Yeah, that would be fairly broken.
Quoted 1 line
Instead, we can't estimate the new
runnable_sumof thegcfs_rqwiths/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
@@ -3489,33 +3489,56 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rqstatic 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
Vincent Guittot
maintainerRe: [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
@@ -3489,33 +3489,57 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rqstatic 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
Peter Zijlstra
maintainerRe: [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
---
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_rqif (!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_rqstatic 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); } }
Vincent Guittot
maintainerRe: [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 +0200Unlike 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_entitiesthat stay on the rq and this runnable time will also remain on prevcfs_rqand must not be removed.Instead, we can estimate what should be the new runnable of the prev
cfs_rqand check that this estimation stay in a possible range. Theprop_runnable_sumis a good estimation when addingrunnable_sumbut 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.weightwhich 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<= thanLOAD_AVG_MAX
-ge->avg.runnable_sum>=ge->avg.running_sum(ge->avg.util_sum<<LOAD_AVG_MAX)
-ge->avg.runnable_sumcan't increase when we detach a taskCc 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]>Signed-off-by Vincent Guittot <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[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_rqif (!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_rqstatic 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); } }
Peter Zijlstra
maintainerRe: [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 usinggcfs_rq->avg.load_sumthat reflects the new state of thegcfs_rqto evaluate therunnable_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_sumis scaled by cpu's capacity but notload_sumI have made the shortcut of using
SCHED_CAPACITY_SHIFTfor capacity but we might better usearch_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.
Vincent Guittot
maintainerRe: [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 usinggcfs_rq->avg.load_sumthat reflects the new state of thegcfs_rqto evaluate therunnable_sumAh, I figured the
load_sumthing 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_sumis scaled by cpu's capacity but notload_sum
Quoted 8 lines
Quoted 2 lines
I have made the shortcut of using
SCHED_CAPACITY_SHIFTfor capacity but we might better usearch_scale_cpu_capacity(NULL, cpu)insteadAh, 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
Vincent Guittot
maintainerPATCH v3 1/1 sched: Update runnable propagation rule
In reply to Peter ZijlstraUnlike 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
---
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
@@ -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_rqif (!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_rqstatic 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
Vincent Guittot
maintainerPATCH 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
---
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
@@ -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_rqif (!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_rqstatic 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
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_entitiesthat stay on the rq and this runnable time will also remain on prevcfs_rqand must not be removed.Instead, we can estimate what should be the new runnable of the prev
cfs_rqand check that this estimation stay in a possible range. Theprop_runnable_sumis a good estimation when addingrunnable_sumbut 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.weightwhich 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<= thanLOAD_AVG_MAX
-ge->avg.runnable_sum>=ge->avg.running_sum(ge->avg.util_sum<<LOAD_AVG_MAX)
-ge->avg.runnable_sumcan'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]>Signed-off-by Vincent Guittot <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>
Ingo, can you stuff this in sched/urgent ?
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_entitiesthat stay on the rq and this runnable time will also remain on prevcfs_rqand must not be removed.Instead, we can estimate what should be the new runnable of the prev
cfs_rqand check that this estimation stay in a possible range. Theprop_runnable_sumis a good estimation when addingrunnable_sumbut 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.weightwhich 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<= thanLOAD_AVG_MAX
-ge->avg.runnable_sum>=ge->avg.running_sum(ge->avg.util_sum<<LOAD_AVG_MAX)
-ge->avg.runnable_sumcan't increase when we detach a taskQuoted 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]>Signed-off-by Vincent Guittot <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>
Quoted 3 lines
Ingo, can you stuff this in sched/urgent ?
Yeah, I've queued up in tip:sched/urgent.
Thanks,
Ingo
tip-bot for Vincent Guittot
merge bot[tip:sched/core] sched/fair: Update and fix the runnable propagation rule
In reply to Vincent Guittotsched/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
@@ -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_rqif (!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_rqstatic 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); } }
Peter Zijlstra
maintainerPATCH 13/18 sched/fair: Propagate an effective runnable_load_avg
In reply to Peter ZijlstraThe 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(structP_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, inSEQ_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
Dietmar Eggemann
reviewerRe: [PATCH -v2 13/18] sched/fair: Propagate an effective runnable_load_avg
Quoted 30 lines · Peter Zijlstra
The load balancer uses
runnable_load_avgas load indicator. For !cgroup this is:
runnable_load_avg= \Sumse->avg.load_avg; wherese->on_rqThat 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_weightwhich 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.
Suggested-by Tejun Heo <[email protected]>Signed-off-by Peter Zijlstra (Intel) <[email protected]>--- 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_rstatic 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.
[...]
Peter Zijlstra
maintainerRe: [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()andupdate_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 forupdate_cfs_rq_load_avg()mentionscfs_rq->avgascfs_rq->avg.load_avg(orcfs_rq_load_avg()) andupdate_cfs_group()doesn't use it anymore. It's now used incalc_group_runnable()andcalc_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
@@ -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. *
Dietmar Eggemann
reviewerRe: [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()andupdate_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 forupdate_cfs_rq_load_avg()mentionscfs_rq->avgascfs_rq->avg.load_avg(orcfs_rq_load_avg()) andupdate_cfs_group()doesn't use it anymore. It's now used incalc_group_runnable()andcalc_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@@ -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. *
Dietmar Eggemann
reviewerRe: [PATCH -v2 13/18] sched/fair: Propagate an effective runnable_load_avg
In reply to Peter ZijlstraOn 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 ;
[...]
Peter Zijlstra
maintainerPATCH 14/18 sched/fair: Synchonous PELT detach on load-balance migrate
In reply to Peter ZijlstraVincent 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 ;
Peter Zijlstra
maintainerPATCH 15/18 sched/fair: Align PELT windows between cfs_rq and its se
In reply to Peter ZijlstraThe 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;
Dietmar Eggemann
reviewerRe: [PATCH -v2 15/18] sched/fair: Align PELT windows between cfs_rq and its se
Quoted 20 lines · Peter Zijlstra
The PELT
_sumvalues 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_rqand se, we can have the situation where, for example, on dequeue, the se decays first.Its
_sumvalues will be small(er), while thecfs_rq_sumvalues will still be on their way up. Because of this, the subtraction:cfs_rq->avg._sum-=se->avg._sumwill result in a positive value. This will then, once thecfs_rqreaches an edge, translate into its_avgvalue jumping up.This is especially visible with the
runnable_loadbits, since they get added/subtracted a lot.Signed-off-by Peter Zijlstra (Intel) <[email protected]>--- 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?
[...]
Peter Zijlstra
maintainerRe: [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
_sumvalues 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_rqand se, we can have the situation where, for example, on dequeue, the se decays first.Its
_sumvalues will be small(er), while thecfs_rq_sumvalues will still be on their way up. Because of this, the subtraction:cfs_rq->avg._sum-=se->avg._sumwill result in a positive value. This will then, once thecfs_rqreaches an edge, translate into its_avgvalue jumping up.This is especially visible with the
runnable_loadbits, since they get added/subtracted a lot.Signed-off-by Peter Zijlstra (Intel) <[email protected]>--- 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.
Dietmar Eggemann
reviewerRe: [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
_sumvalues 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_rqand se, we can have the situation where, for example, on dequeue, the se decays first.Its
_sumvalues will be small(er), while thecfs_rq_sumvalues will still be on their way up. Because of this, the subtraction:cfs_rq->avg._sum-=se->avg._sumwill result in a positive value. This will then, once thecfs_rqreaches an edge, translate into its_avgvalue jumping up.This is especially visible with the
runnable_loadbits, since they get added/subtracted a lot.Signed-off-by Peter Zijlstra (Intel) <[email protected]>--- 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?
Peter Zijlstra
maintainerRe: [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.
Peter Zijlstra
maintainerPATCH 16/18 sched/fair: More accurate async detach
In reply to Peter ZijlstraThe 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 cif (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);
Peter Zijlstra
maintainerPATCH 17/18 sched/fair: Calculate runnable_weight slightly differently
In reply to Peter ZijlstraFrom: 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 scheif (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);
Peter Zijlstra
maintainerPATCH 18/18 sched/fair: Update calc_group_*() comments
In reply to Peter ZijlstraI 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 */