sched/fair: fix load balancer behavior when cgroup is in use
RFC PATCH v2 1/1 sched/fair: fix load balancer behavior when cgroup is in use
Hello,
v1 posting can be found at
http://lkml.kernel.org/r/[email protected]
The patchset is still RFC and based on v4.11. I used Peter's updated calc_cfs_shares() instead of scaling manually and updated so that runnable_load_avg is propagated independently from load_avg. Due to the way sched_entity and cfs_rq loads are calculated, this requires an extra runnable_load_avg calculation for group sched_entities, but the end result is cleaner and actually makes sense.
Vincent, can you please verify whether the regression that you see is gone with this version?
Thanks.
Signature · 1 line
tejun
PATCH 1/3 sched/fair: Peter's shares_type patch
From: Peter Zijlstra <[email protected]>
This patch is combination of
http://lkml.kernel.org/r/[email protected]
+ http://lkml.kernel.org/r/[email protected]
+ build fix & use shares_avg for propagating load_avg instead of runnable
This fixes the propagation problem described in the following while keeping group se->load_avg.avg in line with the matching cfs_rq->load_avg.avg.
http://lkml.kernel.org/r/[email protected]
--- kernel/sched/fair.c | 98 +++++++++++++++++++++++++--------------------------- 1 file changed, 48 insertions(+), 50 deletions(-)
kernel/sched/fair.c +48 -50
@@ -2636,26 +2636,57 @@ account_entity_dequeue(struct cfs_rq *cf cfs_rq->nr_running--; } +enum shares_type { + shares_runnable, + shares_avg, + shares_weight, +}; + #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, struct task_group *tg, + enum shares_type shares_type) { - long tg_weight, load, shares; + long tg_weight, tg_shares, load, 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. - */ - load = scale_load_down(cfs_rq->load.weight); + tg_shares = READ_ONCE(tg->shares); + + switch (shares_type) { + case shares_runnable: + /* + * Instead of the correct cfs_rq->avg.load_avg we use + * cfs_rq->runnable_load_avg, which does not include the + * blocked load. + */ + load = cfs_rq->runnable_load_avg; + break; + + case shares_avg: + load = cfs_rq->avg.load_avg; + break; + + case shares_weight: + /* + * Instead of the correct cfs_rq->avg.load_avg we use + * cfs_rq->load.weight, which is its upper bound. This helps + * ramp up the shares for small weight interactive tasks. + */ + load = scale_load_down(cfs_rq->load.weight); + break; + } tg_weight = atomic_long_read(&tg->load_avg); - /* Ensure tg_weight >= load */ + /* + * This ensures the sum is up-to-date for this CPU, in case of the other + * two approximations it biases the sum towards their value and in case + * of (near) UP ensures the division ends up <= 1. + */ 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;
@@ -2671,15 +2702,11 @@ 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; + return clamp_t(long, shares, MIN_SHARES, tg_shares); }# else /* CONFIG_SMP */ -static inline long calc_cfs_shares (struct cfs_rq *cfs_rq,struct task_group *tg) +static inline long +calc_cfs_shares (struct cfs_rq *cfs_rq,struct task_group *tg,enum shares_type shares_type) {return tg->shares; }
@@ -2721,7 +2748,7 @@ static void update_cfs_shares(struct schif (likely (se->load.weight == tg->shares))return ;#endif - shares =calc_cfs_shares (cfs_rq, tg); + shares =calc_cfs_shares (cfs_rq, tg, shares_weight);reweight_entity (cfs_rq_of (se), se, shares); }
@@ -3078,39 +3105,10 @@ static inline void update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se) { struct cfs_rq *gcfs_rq = group_cfs_rq(se); -long delta, load = gcfs_rq->avg.load_avg; - -/* -* If the load of group cfs_rq is null, the load of the -* sched_entity will also be null so we can skip the formula -*/ -if (load) { -long tg_load; - -/* Get tg's load and ensure tg_load > 0 */ - tg_load =atomic_long_read (&gcfs_rq->tg->load_avg) +1 ; - -/* Ensure tg_load >= load and updated with current load*/ - tg_load -= gcfs_rq->tg_load_avg_contrib; - tg_load += load; - -/* -* We need to compute a correction term in the case that the -* task group is consuming more CPU than a task of equal -* weight. A task with a weight equals to tg->shares will have -* a load less or equal to scale_load_down(tg->shares). -* Similarly, the sched_entities that represent the task group -* at parent level, can't have a load higher than -* scale_load_down(tg->shares). And the Sum of sched_entities' -* load must be <= scale_load_down(tg->shares). -*/ -if (tg_load >scale_load_down (gcfs_rq->tg->shares)) { -/* scale gcfs_rq's load into tg's shares*/ - load *=scale_load_down (gcfs_rq->tg->shares); - load /= tg_load; - } - } +long load, delta; + load =scale_load_down (calc_cfs_shares (gcfs_rq, gcfs_rq->tg, + shares_avg)); delta = load - se->avg.load_avg;/* Nothing to update */
Vincent Guittot
maintainerRe: [PATCH 1/3] sched/fair: Peter's shares_type patch
Quoted 72 lines · Tejun Heo
From: Peter Zijlstra <[email protected]>
This patch is combination of
http://lkml.kernel.org/r/[email protected]+ http://lkml.kernel.org/r/[email protected]
+ build fix & useshares_avgfor propagatingload_avginstead of runnableThis fixes the propagation problem described in the following while keeping group
se->load_avg.avgin line with the matchingcfs_rq->load_avg.avg.http://lkml.kernel.org/r/[email protected]--- kernel/sched/fair.c | 98 +++++++++++++++++++++++++--------------------------- 1 file changed, 48 insertions(+), 50 deletions(-)kernel/sched/fair.c +35
-8@@ -2636,26 +2636,57 @@ account_entity_dequeue(struct cfs_rq *cf cfs_rq->nr_running--; } +enum shares_type { + shares_runnable, + shares_avg, + shares_weight, +}; + #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, struct task_group *tg, + enum shares_type shares_type) { - long tg_weight, load, shares; + long tg_weight, tg_shares, load, 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. - */ - load = scale_load_down(cfs_rq->load.weight); + tg_shares = READ_ONCE(tg->shares); + + switch (shares_type) { + case shares_runnable: + /* + * Instead of the correct cfs_rq->avg.load_avg we use + * cfs_rq->runnable_load_avg, which does not include the + * blocked load. + */ + load = cfs_rq->runnable_load_avg; + break; + + case shares_avg: + load = cfs_rq->avg.load_avg; + break; + + case shares_weight: + /* + * Instead of the correct cfs_rq->avg.load_avg we use + * cfs_rq->load.weight, which is its upper bound. This helps + * ramp up the shares for small weight interactive tasks. + */ + load = scale_load_down(cfs_rq->load.weight); + break; + }
kernel/sched/fair.c account_entity_dequeue(struct cfs_rq *cf · line 2687
Quoted 10 lines
kernel/sched/fair.c +5
-1tg_weight =atomic_long_read (&tg->load_avg); -/* Ensure tg_weight >= load */ +/* +* This ensures the sum is up-to-date for this CPU, in case of the other +* two approximations it biases the sum towards their value and in case +* of (near) UP ensures the division ends up <= 1. +*/ tg_weight -= cfs_rq->tg_load_avg_contrib; tg_weight += load;
The above is correct for shares_avg and shares_weight but it's not correct for shares_runnable because runnable_load_avg is a subset of load_avg.
To highlight this, i have run a single periodic task TA which runs 3ms with a period of 7.777ms. In case you wonder why 7.777ms, it is just to be sure to not be synced with the tick (4ms on my platform) and cover more case but this doesn't have any impact in this example. TA is the only task, nothing else runs on the CPU and the background activity is near nothing and doesn't impact the result below
When TA runs in the root domain, {root cfs_rq,TA}->avg.{load_avg,util_avg} are in the range [390..440] and root cfs_rq->avg.runnable_load_avg toogles between 0 when cfs_rq is idle and [390..440] when TA is running
When TA runs in a dedicated cgroup, {root cfs_rq,TA}->avg.{load_avg,util_avg} remains in the range [390..440] but root cfs_rq->avg.runnable_load_avg is in the range [1012..1036] and often stays in this range whereas TA is sleeping. I have checked that I was tracing correctly all PELT metrics update and that root cfs_rq->avg.runnable_load_avg is really not null and not the side effect of a missing trace.
In fact, if TA is the only task in the cgroup, tg->load_avg == cfs_rq->tg_load_avg_contrib.
For shares_avg, tg_weight == cfs_rq->runnable_load_avg and shares = cfs_rq->runnable_load_avg * tg->shares / cfs_rq->runnable_load_avg = tg->shares = 1024.
Then, because of rounding in pelt computation, child cfs_rq->runnable_load_avg can something be not null (around 2 or 3) when idle so groupentity and root cfs_rq stays around 1024
For shares_runnable, it should be
group_entity->runnable_load_avg = cfs_rq->runnable_load_avg * group_entity->avg.load_avg / cfs_rq->avg.load_avg
And i think that shares_avg is also wrong and should be something like:
group_entity->avg.load_avg = cfs_rq->avg.load_avg * group_entity->load.weight / cfs_rq->load.weight
Then we have to take into account the fact that when we propagate load, group_entity->load.weight and cfs_rq->load.weight of prev cpu and new cpu have not been updated yet. I still need to think a bit more on that impact and how to compensate that when propagating load
Quoted 77 lines
kernel/sched/fair.c +8
-41- shares = (tg->shares * load); + shares = (tg_shares * load);if (tg_weight) shares /= tg_weight;@@ -2671,15 +2702,11 @@ 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; + return clamp_t(long, shares, MIN_SHARES, tg_shares); }# else /* CONFIG_SMP */ -static inline long calc_cfs_shares (struct cfs_rq *cfs_rq,struct task_group *tg) +static inline long +calc_cfs_shares (struct cfs_rq *cfs_rq,struct task_group *tg,enum shares_type shares_type) {return tg->shares; }@@ -2721,7 +2748,7 @@ static void update_cfs_shares(struct schif (likely (se->load.weight == tg->shares))return ;#endif - shares =calc_cfs_shares (cfs_rq, tg); + shares =calc_cfs_shares (cfs_rq, tg, shares_weight);reweight_entity (cfs_rq_of (se), se, shares); }@@ -3078,39 +3105,10 @@ static inline void update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se) { struct cfs_rq *gcfs_rq = group_cfs_rq(se); -long delta, load = gcfs_rq->avg.load_avg; - -/* -* If the load of group cfs_rq is null, the load of the -* sched_entity will also be null so we can skip the formula -*/ -if (load) { -long tg_load; - -/* Get tg's load and ensure tg_load > 0 */ - tg_load =atomic_long_read (&gcfs_rq->tg->load_avg) +1 ; - -/* Ensure tg_load >= load and updated with current load*/ - tg_load -= gcfs_rq->tg_load_avg_contrib; - tg_load += load; - -/* -* We need to compute a correction term in the case that the -* task group is consuming more CPU than a task of equal -* weight. A task with a weight equals to tg->shares will have -* a load less or equal to scale_load_down(tg->shares). -* Similarly, the sched_entities that represent the task group -* at parent level, can't have a load higher than -* scale_load_down(tg->shares). And the Sum of sched_entities' -* load must be <= scale_load_down(tg->shares). -*/ -if (tg_load >scale_load_down (gcfs_rq->tg->shares)) { -/* scale gcfs_rq's load into tg's shares*/ - load *=scale_load_down (gcfs_rq->tg->shares); - load /= tg_load; - } - } +long load, delta; + load =scale_load_down (calc_cfs_shares (gcfs_rq, gcfs_rq->tg, + shares_avg)); delta = load - se->avg.load_avg;/* Nothing to update */
Re: [PATCH 1/3] sched/fair: Peter's shares_type patch
Hello,
Quoted 8 lines · Vincent Guittot
In fact, if TA is the only task in the cgroup,
tg->load_avg==cfs_rq->tg_load_avg_contrib.
Forshares_avg,tg_weight==cfs_rq->runnable_load_avgand shares =cfs_rq->runnable_load_avg*tg->shares/cfs_rq->runnable_load_avg=tg->shares= 1024.
Then, because of rounding in pelt computation, childcfs_rq->runnable_load_avgcan something be not null (around 2 or 3) when idle so groupentity and rootcfs_rqstays around 1024
I see. This is the minor calculation errors and the "replacing local term" adjustment combining to yield a wild result.
Quoted 4 lines
For
shares_runnable, it should be
group_entity->runnable_load_avg=cfs_rq->runnable_load_avg*group_entity->avg.load_avg/cfs_rq->avg.load_avg
Yeah, that could be one way to calculate the value while avoiding the artifacts. Hmmm... IIUC, replacing the local contribution with the current one is to ensure that we at least calculate with the current term on the local queue. This makes sense for weight and shares but as you pointed out it doesn't make sense to replace local base with runnable when the base is expected to be sum of load_avgs. How about something like the following?
--- kernel/sched/fair.c | 101 +++++++++++++++++++++++++--------------------------- 1 file changed, 50 insertions(+), 51 deletions(-)
kernel/sched/fair.c +50 -51
@@ -2636,26 +2636,58 @@ account_entity_dequeue(struct cfs_rq *cf cfs_rq->nr_running--; } +enum shares_type { + shares_runnable, + shares_avg, + shares_weight, +}; + #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, struct task_group *tg, + enum shares_type shares_type) { - long tg_weight, load, shares; + long tg_weight, tg_shares, load, load_base, 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. - */ - load = scale_load_down(cfs_rq->load.weight); + tg_shares = READ_ONCE(tg->shares); + + switch (shares_type) { + case shares_runnable: + /* + * Instead of the correct cfs_rq->avg.load_avg we use + * cfs_rq->runnable_load_avg, which does not include the + * blocked load. + */ + load = cfs_rq->runnable_load_avg; + load_base = cfs_rq->avg.load_avg; + break; + + case shares_avg: + load = load_base = cfs_rq->avg.load_avg; + break; + + case shares_weight: + /* + * Instead of the correct cfs_rq->avg.load_avg we use + * cfs_rq->load.weight, which is its upper bound. This helps + * ramp up the shares for small weight interactive tasks. + */ + load = load_base = scale_load_down(cfs_rq->load.weight); + break; + } tg_weight = atomic_long_read(&tg->load_avg); - /* Ensure tg_weight >= load */ + /* + * This ensures the sum is up-to-date for this CPU, in case of the other + * two approximations it biases the sum towards their value and in case + * of (near) UP ensures the division ends up <= 1. + */ tg_weight -= cfs_rq->tg_load_avg_contrib; - tg_weight += load; + tg_weight += load_base; - shares = (tg->shares * load); + shares = (tg_shares * load); if (tg_weight) shares /= tg_weight;
@@ -2671,15 +2703,11 @@ 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; + return clamp_t(long, shares, MIN_SHARES, tg_shares); }# else /* CONFIG_SMP */ -static inline long calc_cfs_shares (struct cfs_rq *cfs_rq,struct task_group *tg) +static inline long +calc_cfs_shares (struct cfs_rq *cfs_rq,struct task_group *tg,enum shares_type shares_type) {return tg->shares; }
@@ -2721,7 +2749,7 @@ static void update_cfs_shares(struct schif (likely (se->load.weight == tg->shares))return ;#endif - shares =calc_cfs_shares (cfs_rq, tg); + shares =calc_cfs_shares (cfs_rq, tg, shares_weight);reweight_entity (cfs_rq_of (se), se, shares); }
@@ -3078,39 +3106,10 @@ static inline void update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se) { struct cfs_rq *gcfs_rq = group_cfs_rq(se); -long delta, load = gcfs_rq->avg.load_avg; - -/* -* If the load of group cfs_rq is null, the load of the -* sched_entity will also be null so we can skip the formula -*/ -if (load) { -long tg_load; - -/* Get tg's load and ensure tg_load > 0 */ - tg_load =atomic_long_read (&gcfs_rq->tg->load_avg) +1 ; - -/* Ensure tg_load >= load and updated with current load*/ - tg_load -= gcfs_rq->tg_load_avg_contrib; - tg_load += load; - -/* -* We need to compute a correction term in the case that the -* task group is consuming more CPU than a task of equal -* weight. A task with a weight equals to tg->shares will have -* a load less or equal to scale_load_down(tg->shares). -* Similarly, the sched_entities that represent the task group -* at parent level, can't have a load higher than -* scale_load_down(tg->shares). And the Sum of sched_entities' -* load must be <= scale_load_down(tg->shares). -*/ -if (tg_load >scale_load_down (gcfs_rq->tg->shares)) { -/* scale gcfs_rq's load into tg's shares*/ - load *=scale_load_down (gcfs_rq->tg->shares); - load /= tg_load; - } - } +long load, delta; + load =scale_load_down (calc_cfs_shares (gcfs_rq, gcfs_rq->tg, + shares_avg)); delta = load - se->avg.load_avg;/* Nothing to update */
Re: [PATCH 1/3] sched/fair: Peter's shares_type patch
Hello, Vincent.
Quoted 5 lines · Tejun Heo
Quoted 4 lines
For
shares_runnable, it should be
group_entity->runnable_load_avg=cfs_rq->runnable_load_avg*group_entity->avg.load_avg/cfs_rq->avg.load_avg
Quoted 7 lines
Yeah, that could be one way to calculate the value while avoiding the artifacts. Hmmm... IIUC, replacing the local contribution with the current one is to ensure that we at least calculate with the current term on the local queue. This makes sense for weight and shares but as you pointed out it doesn't make sense to replace local base with runnable when the base is expected to be sum of
load_avgs. How about something like the following?
Vincent, have you given this patch a try?
Also, I got the hikey board but of course it can't be powered by usb, so am waiting on the power supply now. Any chance you can share the system image you're using so that I can exactly replicate your environment?
Thanks.
Signature · 1 line
tejun
Vincent Guittot
maintainerRe: [PATCH 1/3] sched/fair: Peter's shares_type patch
Quoted 16 lines · Tejun Heo
Hello, Vincent.
Quoted 5 lines · Tejun Heo
Quoted 4 lines
For
shares_runnable, it should be
group_entity->runnable_load_avg=cfs_rq->runnable_load_avg*group_entity->avg.load_avg/cfs_rq->avg.load_avgQuoted 7 lines
Yeah, that could be one way to calculate the value while avoiding the artifacts. Hmmm... IIUC, replacing the local contribution with the current one is to ensure that we at least calculate with the current term on the local queue. This makes sense for weight and shares but as you pointed out it doesn't make sense to replace local base with runnable when the base is expected to be sum of
load_avgs. How about something like the following?
Quoted 1 line
Vincent, have you given this patch a try?
No I haven't.
My understand of Peter's feedback is that calc_cfs_shares should not be the place where to implement calculation of group_entity->runnable_load_avg and group_entity->avg.load_avg when propagating
Quoted 5 lines
Also, I got the hikey board but of course it can't be powered by usb, so am waiting on the power supply now. Any chance you can share the system image you're using so that I can exactly replicate your environment?
Yes of course.
I will send you details in a dedicated email.
Regards,
Vincent
Quoted 5 lines
Thanks.
--
tejun
Peter Zijlstra
maintainerRe: [PATCH 1/3] sched/fair: Peter's shares_type patch
Quoted 17 lines · Vincent Guittot
Quoted 16 lines · Tejun Heo
Hello, Vincent.
Quoted 12 lines · Tejun Heo
Quoted 4 lines
For
shares_runnable, it should be
group_entity->runnable_load_avg=cfs_rq->runnable_load_avg*group_entity->avg.load_avg/cfs_rq->avg.load_avgYeah, that could be one way to calculate the value while avoiding the artifacts. Hmmm... IIUC, replacing the local contribution with the current one is to ensure that we at least calculate with the current term on the local queue. This makes sense for weight and shares but as you pointed out it doesn't make sense to replace local base with runnable when the base is expected to be sum of
load_avgs. How about something like the following?
Quoted 7 lines
Quoted 1 line
Vincent, have you given this patch a try?
No I haven't.
My understand of Peter's feedback is thatcalc_cfs_sharesshould not be the place where to implement calculation ofgroup_entity->runnable_load_avgandgroup_entity->avg.load_avgwhen propagating
Right, so I have a pile of patches that implement all that my longish email outlined. I'm just chasing some strange behaviour; in particular I'm having runnable_load_avg > load_avg, which is something that should not happen.
It _looks_ like the add/sub cycle leaks a little and a lot of such cycles then push runnable_load_avg out. I've not managed to pin it down.
If I don't find it, I'll send it out regardless as an RFC so that others can 'enjoy'.
One request for Chris / Tejun, could you guys pretty please make a reproducible benchmark? Relying on some ill specified background noise just doesn't work, as this thread has clearly illustrated, nobody can reproduce your issue.
And although I think the specific issue has been fairly well explained, it would be good to have a working benchmark to prove the point.
Peter Zijlstra
maintainerRe: [PATCH 1/3] sched/fair: Peter's shares_type patch
In reply to Vincent GuittotHi all,
Sorry for the overly long post, this is a semi coherent collection of all the notes I found on my desk and some continuations thereon.
Quoted 42 lines · Vincent Guittot
Quoted 42 lines
kernel/sched/fair.c +35
-0+enum shares_type { + shares_runnable, + shares_avg, + shares_weight, +}; + #ifdef CONFIG_FAIR_GROUP_SCHED # ifdef CONFIG_SMP +static long +calc_cfs_shares(struct cfs_rq *cfs_rq, struct task_group *tg, + enum shares_type shares_type) { + long tg_weight, tg_shares, load, shares; + tg_shares = READ_ONCE(tg->shares); + + switch (shares_type) { + case shares_runnable: + /* + * Instead of the correct cfs_rq->avg.load_avg we use + * cfs_rq->runnable_load_avg, which does not include the + * blocked load. + */ + load = cfs_rq->runnable_load_avg; + break; + + case shares_avg: + load = cfs_rq->avg.load_avg; + break; + + case shares_weight: + /* + * Instead of the correct cfs_rq->avg.load_avg we use + * cfs_rq->load.weight, which is its upper bound. This helps + * ramp up the shares for small weight interactive tasks. + */ + load = scale_load_down(cfs_rq->load.weight); + break; + } tg_weight = atomic_long_read(&tg->load_avg);
Quoted 11 lines
kernel/sched/fair.c account_entity_dequeue(struct cfs_rq *cf · line 2687
Quoted 7 lines
kernel/sched/fair.c +5
-0+/* +* This ensures the sum is up-to-date for this CPU, in case of the other +* two approximations it biases the sum towards their value and in case +* of (near) UP ensures the division ends up <= 1. +*/ tg_weight -= cfs_rq->tg_load_avg_contrib; tg_weight += load;The above is correct for
shares_avgandshares_weightbut it's not correct forshares_runnablebecauserunnable_load_avgis a subset ofload_avg.
Its only correct for shares_avg. shares_weight and shares_runnable are both icky.
Remember, 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.weightNow, 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_avgBecause: 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.weightThat 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.weightAnd that is shares_weight and is icky. In the (near) UP case it approaches (4) while in the normal case it approaches, but never quite reaches, (3). I consistently overestimates the ge->load.weight and therefore:
\Sum ge->load.weight >= tg->weight
hence icky!
Now, on to the propagate stuff.
I'm still struggling with this, so I might have gotten it completely backwards. Bear with me.
Quoted 4 lines
And i think that
shares_avgis also wrong and should be something like:
group_entity->avg.load_avg=cfs_rq->avg.load_avg * group_entity->load.weight / cfs_rq->load.weight
So firstly, no, shares_avg was intended to be (3) and that is right.
What you're looking for is an expression for ge->avg.load_avg, that's an entirely different beast.
But lets take a few steps back.
The whole point of the propagation thing is that:
ge->avg == grq->avg (6)
_IFF_ we look at the pure running and runnable sums. Because they represent the very same entity, just as different views.
But since we've just added an entity to grq->avg, we must also update ge->avg to retain our invariant (6).
Per the above update_tg_cfs_util() is trivial (and still 'wrong') and simply copies the running sum over.
However, update_tg_cfs_load() is making my head hurt. So we have:
ge->avg.load_avg = ge->load.weight * ge->avg.runnable_avg (7)
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 (8)
And per (6) we have:
ge->avg.running_avg == grq->avg.running_avg
Which gives (6,7,8):
ge->load.weight * grq->avg.load_avg
ge->avg.load_avg = ----------------------------------- (9)
grq->load.weightExcept 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 (8).
OK, so what then?
The code (more or less) does:
tg->weight * grq->avg.load_avg
ge->avg.load_avg = ------------------------------
tg->load_avgWhich is basically (3), but since that was the right expression for ge->load.weight, and per (7) that does not preserve the runnable sum, its an upper bound and basically completely destroys the runnable part.
[
however, since we actually use (5), and (5) > (3) we get an effective ge->avg.runnable_avg < 1. But still, afaict there's no relation to the desired grq->avg.runnable_avg part.
]
You now propose (9), which as I've explained is wrong (also, trying to implement it doesn't work, grq->load.weight will be 0 etc..).
Another way to look at things is:
grq->avg.load_avg = \Sum se->avg.load_avg
Therefore, per (7):
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, if we were to keep track of cfs_rq->removed_runnable_avg and cfs_rq->added_runnable_avg for the migrate condition, which would be, per (7) the already tracked se->load_avg divided by the corresponding se->weight.
Basically (9) but in differential form:
d(runnable_avg) += se->avg.load_avg / se->load.weight
(10)
ge->avg.load_avg += ge->load.weight * d(runnable_avg)
OK, on to the whole runnable thing, which we should not confuse with the propagation thing, it has very little to do with the invariant (6).
Quoted 10 lines
In fact, if TA is the only task in the cgroup,
tg->load_avg==cfs_rq->tg_load_avg_contrib.For
shares_avg,
tg_weight==cfs_rq->runnable_load_avg, andshares =
cfs_rq->runnable_load_avg*tg->shares/cfs_rq->runnable_load_avg= tg->shares = 1024.
That was the intent. (Also, _please_, use whitespace, its cheap and makes things _so_ much more readable).
grq->runnable_load_avg = \Sum se->avg.load_avg ; where se->on_rq
So its a subset of grq->avg.load_avg. Now, since each group entity (can) represents multiple tasks, not all of which will be runnable at the same time, our group entity should not contribute its entire load_avg to its parent cfs_rq's runnable.
Here I think we can use a simple proportion:
grq->runnable_load_avg
ge->runnable_avg = ge->avg.load_avg * ----------------------
grq->avg.load_avgIts a local property, afaict.
And since it needs to be updated on every enqueue/dequeue, we should do it in {en,de}queue_entity_load_avg() or thereabout.
I've not thought much about time how this interacts with the regular PELT() function and if this fraction is retained under it.
But at this point my brain is completely fried..
Quoted 4 lines
For
shares_runnable, it should be
group_entity->runnable_load_avg=cfs_rq->runnable_load_avg * group_entity->avg.load_avg / cfs_rq->avg.load_avg
I agree with the equation.
Quoted 38 lines
Quoted 38 lines
kernel/sched/fair.c +1
-32@@ -3078,39 +3105,10 @@ static inline void update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se) { struct cfs_rq *gcfs_rq = group_cfs_rq(se); -long delta, load = gcfs_rq->avg.load_avg; - -/* -* If the load of group cfs_rq is null, the load of the -* sched_entity will also be null so we can skip the formula -*/ -if (load) { -long tg_load; - -/* Get tg's load and ensure tg_load > 0 */ - tg_load =atomic_long_read (&gcfs_rq->tg->load_avg) +1 ; - -/* Ensure tg_load >= load and updated with current load*/ - tg_load -= gcfs_rq->tg_load_avg_contrib; - tg_load += load; - -/* -* We need to compute a correction term in the case that the -* task group is consuming more CPU than a task of equal -* weight. A task with a weight equals to tg->shares will have -* a load less or equal to scale_load_down(tg->shares). -* Similarly, the sched_entities that represent the task group -* at parent level, can't have a load higher than -* scale_load_down(tg->shares). And the Sum of sched_entities' -* load must be <= scale_load_down(tg->shares). -*/ -if (tg_load >scale_load_down (gcfs_rq->tg->shares)) { -/* scale gcfs_rq's load into tg's shares*/ - load *=scale_load_down (gcfs_rq->tg->shares); - load /= tg_load; - } - } +long load, delta;
Quoted 5 lines
kernel/sched/fair.c static inline void · line 3114
Quoted 5 lines
kernel/sched/fair.c +2
-0+ load =scale_load_down (calc_cfs_shares (gcfs_rq, gcfs_rq->tg, + shares_avg)); delta = load - se->avg.load_avg;/* Nothing to update */
So this part... I'm fairly sure both the old and new version is wrong.
PATCH 2/3 sched/fair: Add load_weight->runnable_load_{sum|avg}
In reply to Tejun HeoCurrently, runnable_load_avg, which represents the portion of load avg only from tasks which are currently active, is tracked by cfs_rq but not by sched_entity. We want to propagate runnable_load_avg of a nested cfs_rq without affecting load_avg propagation. To implement an equivalent propagation channel, sched_entity needs to track runnable_load_avg too.
This patch moves cfs_rq->runnable_load_{sum|avg} into struct load_weight which is already used to track load_avg and shared by both cfs_rq and sched_entity.
This patch only changes where runnable_load_{sum|avg} are located and doesn't cause any actual behavior changes. The fields are still only used for cfs_rqs.
--- include/linux/sched.h | 2 + kernel/sched/debug.c | 2 - kernel/sched/fair.c | 63 +++++++++++++++++++++++++------------------------- kernel/sched/sched.h | 2 - 4 files changed, 35 insertions(+), 34 deletions(-)
include/linux/sched.h +2 -0
@@ -314,9 +314,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; };
kernel/sched/debug.c +1 -1
@@ -516,7 +516,7 @@ void print_cfs_rq(struct seq_file *m, inSEQ_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",
kernel/sched/fair.c +32 -31
154 lines not on this page · raw message
kernel/sched/sched.h +0 -2
@@ -422,8 +422,6 @@ struct cfs_rq {* CFS load tracking */ struct sched_avg avg; -u64 runnable_load_sum; -unsigned long runnable_load_avg;#ifdef CONFIG_FAIR_GROUP_SCHED unsigned long tg_load_avg_contrib;unsigned long propagate_avg;
Dietmar Eggemann
reviewerRe: [PATCH 2/3] sched/fair: Add load_weight->runnable_load_{sum|avg}
Hi Tejun,
Quoted 7 lines · Tejun Heo
Currently,
runnable_load_avg, which represents the portion of load avg only from tasks which are currently active, is tracked bycfs_rqbut not bysched_entity. We want to propagaterunnable_load_avgof a nestedcfs_rqwithout affectingload_avgpropagation. To implement an equivalent propagation channel,sched_entityneeds to trackrunnable_load_avgtoo.
Quoted 7 lines
This patch moves cfs_rq->runnable_load_{sum|avg} into struct
load_weightwhich is already used to trackload_avgand shared by bothcfs_rqandsched_entity.This patch only changes where runnable_load_{sum|avg} are located and doesn't cause any actual behavior changes. The fields are still only used for
cfs_rqs.
This one doesn't apply cleanly on tip/sched/core. There has been a lot of changes in the actual PELT code.
e.g.a481db34b9be - sched/fair: Optimize ___update_sched_avg() (2017-03-30 Yuyang Du)0ccb977f4c80 - sched/fair: Explicitly generate __update_load_avg() instances (2017-03-30 Peter Zijlstra)
I stitch this up locally to be able to run some tests.
[...]
Re: [PATCH 2/3] sched/fair: Add load_weight->runnable_load_{sum|avg}
Quoted 14 lines · Dietmar Eggemann
Hi Tejun,
Quoted 11 lines · Tejun Heo
Currently,
runnable_load_avg, which represents the portion of load avg only from tasks which are currently active, is tracked bycfs_rqbut not bysched_entity. We want to propagaterunnable_load_avgof a nestedcfs_rqwithout affectingload_avgpropagation. To implement an equivalent propagation channel,sched_entityneeds to trackrunnable_load_avgtoo.This patch moves cfs_rq->runnable_load_{sum|avg} into struct
load_weightwhich is already used to trackload_avgand shared by bothcfs_rqandsched_entity.
Quoted 6 lines
Quoted 3 lines
This patch only changes where runnable_load_{sum|avg} are located and doesn't cause any actual behavior changes. The fields are still only used for
cfs_rqs.This one doesn't apply cleanly on tip/sched/core. There has been a lot of changes in the actual PELT code.
The patches are on top of v4.11 as noted in the head message.
Thanks.
Signature · 1 line
tejun
Dietmar Eggemann
reviewerRe: [PATCH 2/3] sched/fair: Add load_weight->runnable_load_{sum|avg}
Quoted 3 lines · Tejun Heo
Quoted 2 lines · Dietmar Eggemann
Hi Tejun,
[...]
Quoted 2 lines
The patches are on top of v4.11 as noted in the head message.
Sorry, haven't seen it. Will use v4.11 instead.
[...]
PATCH 3/3 sched/fair: Propagate runnable_load_avg independently from load_avg
In reply to Tejun HeoWe noticed that with cgroup CPU controller in use, the scheduling latency gets wonky regardless of nesting level or weight configuration. This is easily reproducible with Chris Mason's schbench[1].
All tests are run on a single socket, 16 cores, 32 threads machine. While the machine is mostly idle, it isn't completey. There's always some variable management load going on. The command used is
schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
which measures scheduling latency with 32 threads each of which repeatedly runs for 15ms and then sleeps for 10ms. Here's a representative result when running from the root cgroup.
# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)
50.0000th: 26 75.0000th: 62 90.0000th: 74 95.0000th: 86 *99.0000th: 887 99.5000th: 3692 99.9000th: 10832 min=0, max=13374
The following is inside a first level CPU cgroup with the maximum weight.
# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)
50.0000th: 31 75.0000th: 65 90.0000th: 71 95.0000th: 91 *99.0000th: 7288 99.5000th: 10352 99.9000th: 12496 min=0, max=13023
Note the drastic increase in p99 scheduling latency. After investigation, it turned out that the update_sd_lb_stats(), which is used by load_balance() to pick the most loaded group, was often picking the wrong group. A CPU which has one schbench running and another queued wouldn't report the correspondingly higher weighted_cpuload() and get looked over as the target of load balancing.
weighted_cpuload() is the root cfs_rq's runnable_load_avg which is the sum of the load_avg of all active sched_entities. Without cgroups or at the root cgroup, each task's load_avg contributes directly to the sum. When a task wakes up or goes to sleep, the change is immediately reflected on runnable_load_avg which in turn affects load balancing.
However, when CPU cgroup is in use, a nested cfs_rq blocks this immediate propagation. When a task wakes up inside a cgroup, the nested cfs_rq's runnable_load_avg is updated but doesn't get propagated to the parent. It only affects the matching sched_entity's load_avg over time which then gets propagated to the runnable_load_avg at that level. This makes the runnable_load_avg at the root queue incorrectly include blocked load_avgs of tasks queued in nested cfs_rqs causing the load balancer to make the wrong choices.
This patch fixes the bug by propagating nested cfs_rq's runnable_load_avg independently from load_avg. Tasks still contribute to its cfs_rq's runnable_load_avg the same way; however, a nested cfs_rq directly propagates the scaled runnable_load_avg to the matching group sched_entity's avg.runnable_load_avg and keeps the se's and parent cfs_rq's runnable_load_avg in sync.
This ensures that, for any given cfs_rq, its runnable_load_avg is the sum of the scaled load_avgs of all and only active tasks queued on it and its descendants. This allows the load balancer to operate on the same information whether there are nested cfs_rqs or not.
With the patch applied, the p99 latency from inside a cgroup is equivalent to the root cgroup case.
# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)
50.0000th: 40 75.0000th: 71 90.0000th: 89 95.0000th: 108 *99.0000th: 679 99.5000th: 3500 99.9000th: 10960 min=0, max=13790
[1] git://git.kernel.org/pub/scm/linux/kernel/git/mason/schbench.git
--- kernel/sched/fair.c | 55 ++++++++++++++++++++++++++++++++++------------------ 1 file changed, 37 insertions(+), 18 deletions(-)
kernel/sched/fair.c +37 -18
@@ -3098,6 +3098,30 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq cfs_rq->avg.util_sum = cfs_rq->avg.util_avg *LOAD_AVG_MAX ; } +static inline void +update_tg_cfs_runnable (struct cfs_rq *cfs_rq,struct sched_entity *se) +{ +struct cfs_rq *gcfs_rq =group_cfs_rq (se); +long load, delta; + + load =scale_load_down (calc_cfs_shares (gcfs_rq, gcfs_rq->tg, + shares_runnable)); + delta = load - se->avg.runnable_load_avg; + +/* Nothing to update */ +if (!delta) +return ; + +/* Set new sched_entity's load */ + se->avg.runnable_load_avg = load; + se->avg.runnable_load_sum = se->avg.runnable_load_avg *LOAD_AVG_MAX ; + +/* Update parent cfs_rq load */ +add_positive (&cfs_rq->avg.runnable_load_avg, delta); + cfs_rq->avg.runnable_load_sum = + cfs_rq->avg.runnable_load_avg *LOAD_AVG_MAX ; +} +/* Take into account change of load of a child task group */ static inline void update_tg_cfs_load (struct cfs_rq *cfs_rq,struct sched_entity *se)
@@ -3120,17 +3144,6 @@ update_tg_cfs_load(struct cfs_rq *cfs_rq/* Update parent cfs_rq load */ add_positive (&cfs_rq->avg.load_avg, delta); cfs_rq->avg.load_sum = cfs_rq->avg.load_avg *LOAD_AVG_MAX ; - -/* -* If the sched_entity is already enqueued, we also have to update the -* runnable load avg. -*/ -if (se->on_rq) { -/* Update parent cfs_rq runnable_load_avg */ -add_positive (&cfs_rq->avg.runnable_load_avg, delta); - cfs_rq->avg.runnable_load_sum = - cfs_rq->avg.runnable_load_avg *LOAD_AVG_MAX ; - } }static inline void set_tg_cfs_propagate (struct cfs_rq *cfs_rq)
@@ -3152,16 +3165,16 @@ static inline int test_and_clear_tg_cfs_/* Update task and its cfs_rq load average */ static inline int propagate_entity_load_avg (struct sched_entity *se) { -struct cfs_rq *cfs_rq; +struct cfs_rq *cfs_rq =cfs_rq_of (se);if (entity_is_task (se))return 0 ; +update_tg_cfs_runnable (cfs_rq, se); +if (!test_and_clear_tg_cfs_propagate (se))return 0 ; - cfs_rq =cfs_rq_of (se); -set_tg_cfs_propagate (cfs_rq);update_tg_cfs_util (cfs_rq, se);
@@ -3298,7 +3311,7 @@ static inline void update_load_avg(strucif (se->avg.last_update_time && !(flags &SKIP_AGE_LOAD )) {__update_load_avg (now, cpu, &se->avg, se->on_rq *scale_load_down (se->load.weight), - cfs_rq->curr == se, false); + cfs_rq->curr == se, !entity_is_task (se)); } decayed =update_cfs_rq_load_avg (now, cfs_rq, true);
@@ -3354,8 +3367,10 @@ enqueue_entity_load_avg(struct cfs_rq *c {struct sched_avg *sa = &se->avg; - cfs_rq->avg.runnable_load_avg += sa->load_avg; - cfs_rq->avg.runnable_load_sum += sa->load_sum; +if (entity_is_task (se)) { + cfs_rq->avg.runnable_load_avg += sa->load_avg; + cfs_rq->avg.runnable_load_sum += sa->load_sum; + }if (!sa->last_update_time) {attach_entity_load_avg (cfs_rq, se);
@@ -3369,6 +3384,9 @@ dequeue_entity_load_avg(struct cfs_rq *c {struct sched_avg *sa = &se->avg; +if (!entity_is_task (se)) +return ; + cfs_rq->avg.runnable_load_avg =max_t (long, cfs_rq->avg.runnable_load_avg - sa->load_avg,0 ); cfs_rq->avg.runnable_load_sum =
@@ -3406,7 +3424,8 @@ void sync_entity_load_avg(struct sched_eu64 last_update_time; last_update_time =cfs_rq_last_update_time (cfs_rq); -__update_load_avg (last_update_time,cpu_of (rq_of (cfs_rq)), &se->avg,0 ,0 , false); +__update_load_avg (last_update_time,cpu_of (rq_of (cfs_rq)), + &se->avg,0 ,0 , !entity_is_task (se)); }/*
Vincent Guittot
maintainerRe: [PATCH 3/3] sched/fair: Propagate runnable_load_avg independently from load_avg
Quoted 183 lines · Tejun Heo
We noticed that with cgroup CPU controller in use, the scheduling latency gets wonky regardless of nesting level or weight configuration. This is easily reproducible with Chris Mason's schbench[1].
All tests are run on a single socket, 16 cores, 32 threads machine. While the machine is mostly idle, it isn't completey. There's always some variable management load going on. The command used is
schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
which measures scheduling latency with 32 threads each of which repeatedly runs for 15ms and then sleeps for 10ms. Here's a representative result when running from the root cgroup.
# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)50.0000th: 26 75.0000th: 62 90.0000th: 74 95.0000th: 86 *99.0000th: 887 99.5000th: 3692 99.9000th: 10832 min=0, max=13374The following is inside a first level CPU cgroup with the maximum weight.
# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)50.0000th: 31 75.0000th: 65 90.0000th: 71 95.0000th: 91 *99.0000th: 7288 99.5000th: 10352 99.9000th: 12496 min=0, max=13023Note the drastic increase in p99 scheduling latency. After investigation, it turned out that the
update_sd_lb_stats(), which is used byload_balance()to pick the most loaded group, was often picking the wrong group. A CPU which has one schbench running and another queued wouldn't report the correspondingly higherweighted_cpuload()and get looked over as the target of load balancing.
weighted_cpuload()is the root cfs_rq'srunnable_load_avgwhich is the sum of theload_avgof all activesched_entities. Without cgroups or at the root cgroup, each task'sload_avgcontributes directly to the sum. When a task wakes up or goes to sleep, the change is immediately reflected onrunnable_load_avgwhich in turn affects load balancing.However, when CPU cgroup is in use, a nested
cfs_rqblocks this immediate propagation. When a task wakes up inside a cgroup, the nested cfs_rq'srunnable_load_avgis updated but doesn't get propagated to the parent. It only affects the matching sched_entity'sload_avgover time which then gets propagated to therunnable_load_avgat that level. This makes therunnable_load_avgat the root queue incorrectly include blockedload_avgsof tasks queued in nestedcfs_rqscausing the load balancer to make the wrong choices.This patch fixes the bug by propagating nested cfs_rq's
runnable_load_avgindependently fromload_avg. Tasks still contribute to its cfs_rq'srunnable_load_avgthe same way; however, a nestedcfs_rqdirectly propagates the scaledrunnable_load_avgto the matching group sched_entity's avg.runnable_load_avg and keeps the se's and parent cfs_rq'srunnable_load_avgin sync.This ensures that, for any given
cfs_rq, itsrunnable_load_avgis the sum of the scaledload_avgsof all and only active tasks queued on it and its descendants. This allows the load balancer to operate on the same information whether there are nestedcfs_rqsor not.With the patch applied, the p99 latency from inside a cgroup is equivalent to the root cgroup case.
# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)50.0000th: 40 75.0000th: 71 90.0000th: 89 95.0000th: 108 *99.0000th: 679 99.5000th: 3500 99.9000th: 10960 min=0, max=13790[1]
git://git.kernel.org/pub/scm/linux/kernel/git/mason/schbench.gitSigned-off-by Tejun Heo <[email protected]>Cc Vincent Guittot <[email protected]>Cc Ingo Molnar <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Mike Galbraith <[email protected]>Cc Paul Turner <[email protected]>Cc Chris Mason <[email protected]>--- kernel/sched/fair.c | 55 ++++++++++++++++++++++++++++++++++------------------ 1 file changed, 37 insertions(+), 18 deletions(-)kernel/sched/fair.c +28
-15@@ -3098,6 +3098,30 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq cfs_rq->avg.util_sum = cfs_rq->avg.util_avg *LOAD_AVG_MAX ; } +static inline void +update_tg_cfs_runnable (struct cfs_rq *cfs_rq,struct sched_entity *se) +{ +struct cfs_rq *gcfs_rq =group_cfs_rq (se); +long load, delta; + + load =scale_load_down (calc_cfs_shares (gcfs_rq, gcfs_rq->tg, + shares_runnable)); + delta = load - se->avg.runnable_load_avg; + +/* Nothing to update */ +if (!delta) +return ; + +/* Set new sched_entity's load */ + se->avg.runnable_load_avg = load; + se->avg.runnable_load_sum = se->avg.runnable_load_avg *LOAD_AVG_MAX ; + +/* Update parent cfs_rq load */ +add_positive (&cfs_rq->avg.runnable_load_avg, delta); + cfs_rq->avg.runnable_load_sum = + cfs_rq->avg.runnable_load_avg *LOAD_AVG_MAX ; +} +/* Take into account change of load of a child task group */ static inline void update_tg_cfs_load (struct cfs_rq *cfs_rq,struct sched_entity *se)@@ -3120,17 +3144,6 @@ update_tg_cfs_load(struct cfs_rq *cfs_rq/* Update parent cfs_rq load */ add_positive (&cfs_rq->avg.load_avg, delta); cfs_rq->avg.load_sum = cfs_rq->avg.load_avg *LOAD_AVG_MAX ; - -/* -* If the sched_entity is already enqueued, we also have to update the -* runnable load avg. -*/ -if (se->on_rq) { -/* Update parent cfs_rq runnable_load_avg */ -add_positive (&cfs_rq->avg.runnable_load_avg, delta); - cfs_rq->avg.runnable_load_sum = - cfs_rq->avg.runnable_load_avg *LOAD_AVG_MAX ; - } }static inline void set_tg_cfs_propagate (struct cfs_rq *cfs_rq)@@ -3152,16 +3165,16 @@ static inline int test_and_clear_tg_cfs_/* Update task and its cfs_rq load average */ static inline int propagate_entity_load_avg (struct sched_entity *se) { -struct cfs_rq *cfs_rq; +struct cfs_rq *cfs_rq =cfs_rq_of (se);if (entity_is_task (se))return 0 ; +update_tg_cfs_runnable (cfs_rq, se); +if (!test_and_clear_tg_cfs_propagate (se))return 0 ; - cfs_rq =cfs_rq_of (se); -set_tg_cfs_propagate (cfs_rq);update_tg_cfs_util (cfs_rq, se);@@ -3298,7 +3311,7 @@ static inline void update_load_avg(strucif (se->avg.last_update_time && !(flags &SKIP_AGE_LOAD )) {__update_load_avg (now, cpu, &se->avg, se->on_rq *scale_load_down (se->load.weight), - cfs_rq->curr == se, false); + cfs_rq->curr == se, !entity_is_task (se)); } decayed =update_cfs_rq_load_avg (now, cfs_rq, true);
kernel/sched/fair.c enqueue_entity_load_avg(struct cfs_rq *c · line 3370
Quoted 6 lines
kernel/sched/fair.c +1
-2@@ -3354,8 +3367,10 @@ enqueue_entity_load_avg(struct cfs_rq *c {struct sched_avg *sa = &se->avg; - cfs_rq->avg.runnable_load_avg += sa->load_avg; - cfs_rq->avg.runnable_load_sum += sa->load_sum; +if (entity_is_task (se)) {
Why don't you add the runnable_load_avg of a group_entity that is enqueued ?
kernel/sched/fair.c dequeue_entity_load_avg(struct cfs_rq *c · line 3388
Quoted 12 lines
kernel/sched/fair.c +5
-0+ cfs_rq->avg.runnable_load_avg += sa->load_avg; + cfs_rq->avg.runnable_load_sum += sa->load_sum; + }if (!sa->last_update_time) {attach_entity_load_avg (cfs_rq, se);@@ -3369,6 +3384,9 @@ dequeue_entity_load_avg(struct cfs_rq *c {struct sched_avg *sa = &se->avg; +if (!entity_is_task (se)) +return ;
Same as enqueue, you have to remove the runnable_load_avg of a group_entity that is dequeued
Quoted 14 lines
kernel/sched/fair.c +3
-1+ cfs_rq->avg.runnable_load_avg =max_t (long, cfs_rq->avg.runnable_load_avg - sa->load_avg,0 ); cfs_rq->avg.runnable_load_sum =@@ -3406,7 +3424,8 @@ void sync_entity_load_avg(struct sched_eu64 last_update_time; last_update_time =cfs_rq_last_update_time (cfs_rq); -__update_load_avg (last_update_time,cpu_of (rq_of (cfs_rq)), &se->avg,0 ,0 , false); +__update_load_avg (last_update_time,cpu_of (rq_of (cfs_rq)), + &se->avg,0 ,0 , !entity_is_task (se)); }/*
Vincent Guittot
maintainerRe: [PATCH 3/3] sched/fair: Propagate runnable_load_avg independently from load_avg
Quoted 187 lines · Vincent Guittot
Quoted 186 lines · Tejun Heo
We noticed that with cgroup CPU controller in use, the scheduling latency gets wonky regardless of nesting level or weight configuration. This is easily reproducible with Chris Mason's schbench[1].
All tests are run on a single socket, 16 cores, 32 threads machine. While the machine is mostly idle, it isn't completey. There's always some variable management load going on. The command used is
schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
which measures scheduling latency with 32 threads each of which repeatedly runs for 15ms and then sleeps for 10ms. Here's a representative result when running from the root cgroup.
# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)50.0000th: 26 75.0000th: 62 90.0000th: 74 95.0000th: 86 *99.0000th: 887 99.5000th: 3692 99.9000th: 10832 min=0, max=13374The following is inside a first level CPU cgroup with the maximum weight.
# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)50.0000th: 31 75.0000th: 65 90.0000th: 71 95.0000th: 91 *99.0000th: 7288 99.5000th: 10352 99.9000th: 12496 min=0, max=13023Note the drastic increase in p99 scheduling latency. After investigation, it turned out that the
update_sd_lb_stats(), which is used byload_balance()to pick the most loaded group, was often picking the wrong group. A CPU which has one schbench running and another queued wouldn't report the correspondingly higherweighted_cpuload()and get looked over as the target of load balancing.
weighted_cpuload()is the root cfs_rq'srunnable_load_avgwhich is the sum of theload_avgof all activesched_entities. Without cgroups or at the root cgroup, each task'sload_avgcontributes directly to the sum. When a task wakes up or goes to sleep, the change is immediately reflected onrunnable_load_avgwhich in turn affects load balancing.However, when CPU cgroup is in use, a nested
cfs_rqblocks this immediate propagation. When a task wakes up inside a cgroup, the nested cfs_rq'srunnable_load_avgis updated but doesn't get propagated to the parent. It only affects the matching sched_entity'sload_avgover time which then gets propagated to therunnable_load_avgat that level. This makes therunnable_load_avgat the root queue incorrectly include blockedload_avgsof tasks queued in nestedcfs_rqscausing the load balancer to make the wrong choices.This patch fixes the bug by propagating nested cfs_rq's
runnable_load_avgindependently fromload_avg. Tasks still contribute to its cfs_rq'srunnable_load_avgthe same way; however, a nestedcfs_rqdirectly propagates the scaledrunnable_load_avgto the matching group sched_entity's avg.runnable_load_avg and keeps the se's and parent cfs_rq'srunnable_load_avgin sync.This ensures that, for any given
cfs_rq, itsrunnable_load_avgis the sum of the scaledload_avgsof all and only active tasks queued on it and its descendants. This allows the load balancer to operate on the same information whether there are nestedcfs_rqsor not.With the patch applied, the p99 latency from inside a cgroup is equivalent to the root cgroup case.
# ~/schbench -m 2 -t 16 -s 10000 -c 15000 -r 30
Latency percentiles (usec)50.0000th: 40 75.0000th: 71 90.0000th: 89 95.0000th: 108 *99.0000th: 679 99.5000th: 3500 99.9000th: 10960 min=0, max=13790[1]
git://git.kernel.org/pub/scm/linux/kernel/git/mason/schbench.gitSigned-off-by Tejun Heo <[email protected]>Cc Vincent Guittot <[email protected]>Cc Ingo Molnar <[email protected]>Cc Peter Zijlstra <[email protected]>Cc Mike Galbraith <[email protected]>Cc Paul Turner <[email protected]>Cc Chris Mason <[email protected]>--- kernel/sched/fair.c | 55 ++++++++++++++++++++++++++++++++++------------------ 1 file changed, 37 insertions(+), 18 deletions(-)kernel/sched/fair.c +28
-15@@ -3098,6 +3098,30 @@ update_tg_cfs_util(struct cfs_rq *cfs_rq cfs_rq->avg.util_sum = cfs_rq->avg.util_avg *LOAD_AVG_MAX ; } +static inline void +update_tg_cfs_runnable (struct cfs_rq *cfs_rq,struct sched_entity *se) +{ +struct cfs_rq *gcfs_rq =group_cfs_rq (se); +long load, delta; + + load =scale_load_down (calc_cfs_shares (gcfs_rq, gcfs_rq->tg, + shares_runnable)); + delta = load - se->avg.runnable_load_avg; + +/* Nothing to update */ +if (!delta) +return ; + +/* Set new sched_entity's load */ + se->avg.runnable_load_avg = load; + se->avg.runnable_load_sum = se->avg.runnable_load_avg *LOAD_AVG_MAX ; + +/* Update parent cfs_rq load */ +add_positive (&cfs_rq->avg.runnable_load_avg, delta); + cfs_rq->avg.runnable_load_sum = + cfs_rq->avg.runnable_load_avg *LOAD_AVG_MAX ; +} +/* Take into account change of load of a child task group */ static inline void update_tg_cfs_load (struct cfs_rq *cfs_rq,struct sched_entity *se)@@ -3120,17 +3144,6 @@ update_tg_cfs_load(struct cfs_rq *cfs_rq/* Update parent cfs_rq load */ add_positive (&cfs_rq->avg.load_avg, delta); cfs_rq->avg.load_sum = cfs_rq->avg.load_avg *LOAD_AVG_MAX ; - -/* -* If the sched_entity is already enqueued, we also have to update the -* runnable load avg. -*/ -if (se->on_rq) { -/* Update parent cfs_rq runnable_load_avg */ -add_positive (&cfs_rq->avg.runnable_load_avg, delta); - cfs_rq->avg.runnable_load_sum = - cfs_rq->avg.runnable_load_avg *LOAD_AVG_MAX ; - } }static inline void set_tg_cfs_propagate (struct cfs_rq *cfs_rq)@@ -3152,16 +3165,16 @@ static inline int test_and_clear_tg_cfs_/* Update task and its cfs_rq load average */ static inline int propagate_entity_load_avg (struct sched_entity *se) { -struct cfs_rq *cfs_rq; +struct cfs_rq *cfs_rq =cfs_rq_of (se);if (entity_is_task (se))return 0 ; +update_tg_cfs_runnable (cfs_rq, se); +if (!test_and_clear_tg_cfs_propagate (se))return 0 ; - cfs_rq =cfs_rq_of (se); -set_tg_cfs_propagate (cfs_rq);update_tg_cfs_util (cfs_rq, se);@@ -3298,7 +3311,7 @@ static inline void update_load_avg(strucif (se->avg.last_update_time && !(flags &SKIP_AGE_LOAD )) {__update_load_avg (now, cpu, &se->avg, se->on_rq *scale_load_down (se->load.weight), - cfs_rq->curr == se, false); + cfs_rq->curr == se, !entity_is_task (se)); } decayed =update_cfs_rq_load_avg (now, cfs_rq, true);@@ -3354,8 +3367,10 @@ enqueue_entity_load_avg(struct cfs_rq *c {struct sched_avg *sa = &se->avg;
Quoted 5 lines
kernel/sched/fair.c enqueue_entity_load_avg(struct cfs_rq *c · line 3370
Quoted 3 lines
kernel/sched/fair.c +1
-2- cfs_rq->avg.runnable_load_avg += sa->load_avg; - cfs_rq->avg.runnable_load_sum += sa->load_sum; +if (entity_is_task (se)) {Why don't you add the
runnable_load_avgof agroup_entitythat is enqueued ?
ok, i forgot that you propagate runnable_load_avg in entity now. But this seems really weird and adds more exceptions to the normal behavior of load tracking
Quoted 31 lines
kernel/sched/fair.c dequeue_entity_load_avg(struct cfs_rq *c · line 3388
Quoted 13 lines
kernel/sched/fair.c +5
-0+ cfs_rq->avg.runnable_load_avg += sa->load_avg; + cfs_rq->avg.runnable_load_sum += sa->load_sum; + }if (!sa->last_update_time) {attach_entity_load_avg (cfs_rq, se);@@ -3369,6 +3384,9 @@ dequeue_entity_load_avg(struct cfs_rq *c {struct sched_avg *sa = &se->avg; +if (!entity_is_task (se)) +return ;Same as enqueue, you have to remove the
runnable_load_avgof agroup_entitythat is dequeuedQuoted 14 lines
kernel/sched/fair.c +3
-1+ cfs_rq->avg.runnable_load_avg =max_t (long, cfs_rq->avg.runnable_load_avg - sa->load_avg,0 ); cfs_rq->avg.runnable_load_sum =@@ -3406,7 +3424,8 @@ void sync_entity_load_avg(struct sched_eu64 last_update_time; last_update_time =cfs_rq_last_update_time (cfs_rq); -__update_load_avg (last_update_time,cpu_of (rq_of (cfs_rq)), &se->avg,0 ,0 , false); +__update_load_avg (last_update_time,cpu_of (rq_of (cfs_rq)), + &se->avg,0 ,0 , !entity_is_task (se)); }/*
Re: [PATCH 3/3] sched/fair: Propagate runnable_load_avg independently from load_avg
Hello,
Quoted 10 lines · Vincent Guittot
Quoted 9 lines
kernel/sched/fair.c enqueue_entity_load_avg(struct cfs_rq *c · line 3370
Quoted 7 lines
kernel/sched/fair.c +1
-2@@ -3354,8 +3367,10 @@ enqueue_entity_load_avg(struct cfs_rq *c {struct sched_avg *sa = &se->avg; - cfs_rq->avg.runnable_load_avg += sa->load_avg; - cfs_rq->avg.runnable_load_sum += sa->load_sum; +if (entity_is_task (se)) {Why don't you add the
runnable_load_avgof agroup_entitythat is enqueued ?
Quoted 3 lines
ok, i forgot that you propagate
runnable_load_avgin entity now. But this seems really weird and adds more exceptions to the normal behavior of load tracking
It seems cleaner this way to me. The actual runnable tracking is taking place for tasks only on their immediate queues and everything beyond that is pure propagation. The distinction is inherent as there's no point in calculating runnable for a task's se.
Obviously, we can special-case dequeueing of nested group entities too but it's more code and fragility.
Thanks.
Signature · 1 line
tejun
Vincent Guittot
maintainerRe: [PATCH 3/3] sched/fair: Propagate runnable_load_avg independently from load_avg
In reply to Tejun HeoOn 4 May 2017 at 22:30, Tejun Heo <[email protected]> wrote:
[snip]
Quoted 22 lines
/* Take into account change of load of a child task group */ static inline void
update_tg_cfs_load(struct cfs_rq *cfs_rq, struct sched_entity *se)kernel/sched/fair.c +0
-11@@ -3120,17 +3144,6 @@ update_tg_cfs_load(struct cfs_rq *cfs_rq/* Update parent cfs_rq load */ add_positive (&cfs_rq->avg.load_avg, delta); cfs_rq->avg.load_sum = cfs_rq->avg.load_avg *LOAD_AVG_MAX ; - -/* -* If the sched_entity is already enqueued, we also have to update the -* runnable load avg. -*/ -if (se->on_rq) { -/* Update parent cfs_rq runnable_load_avg */ -add_positive (&cfs_rq->avg.runnable_load_avg, delta); - cfs_rq->avg.runnable_load_sum = - cfs_rq->avg.runnable_load_avg *LOAD_AVG_MAX ; - } }static inline void set_tg_cfs_propagate (struct cfs_rq *cfs_rq)
kernel/sched/fair.c static inline int test_and_clear_tg_cfs_ · line 3173
Quoted 10 lines
kernel/sched/fair.c +2
-1@@ -3152,16 +3165,16 @@ static inline int test_and_clear_tg_cfs_/* Update task and its cfs_rq load average */ static inline int propagate_entity_load_avg (struct sched_entity *se) { -struct cfs_rq *cfs_rq; +struct cfs_rq *cfs_rq =cfs_rq_of (se);if (entity_is_task (se))return 0 ; +update_tg_cfs_runnable (cfs_rq, se);
I wonder if update_tg_cfs_runnable() should really be called in propagate_entity_load_avg().propagate_entity_load_avg() is called on every update_load_avg because of entity can be asynchronously detached so we must catch this asynchronous events each time we update the load
But enqueue/dequeue of entity of fully synchronous and we know when runnable_load_avg is updated and should be propagated. So instead of calling update_tg_cfs_runnable() at every update_load_avg(), we can only call it in the enque_/dequeue path and save lot of useless call
Quoted 1 line
(quoted diff) +1
-0+
Vincent Guittot
maintainerHi Tejun,
Quoted 13 lines · Tejun Heo
Hello,
v1 posting can be found at
http://lkml.kernel.org/r/[email protected]
The patchset is still RFC and based on v4.11. I used Peter's updated
calc_cfs_shares()instead of scaling manually and updated so thatrunnable_load_avgis propagated independently fromload_avg. Due to the waysched_entityandcfs_rqloads are calculated, this requires an extrarunnable_load_avgcalculation for groupsched_entities, but the end result is cleaner and actually makes sense.
Quoted 2 lines
Vincent, can you please verify whether the regression that you see is gone with this version?
schbench results looks better with this version
Latency percentiles (usec)
50.0000th: 212
75.0000th: 292
90.0000th: 385
95.0000th: 439
*99.0000th: 671
99.5000th: 7992
99.9000th: 12176
min=0, max=14855
p99 is back to a normal value but p99.5 stays higher than mainline
I have also checked load_avg and runnable_load_avg value and there is something incorrect. I will provide details on the related patch
Regards,
Vincent
Quoted 5 lines
Thanks.
--
tejun
Hello, Vincent.
Quoted 11 lines · Vincent Guittot
schbench results looks better with this version
Latency percentiles (usec)
50.0000th: 212
75.0000th: 292
90.0000th: 385
95.0000th: 439
*99.0000th: 671
99.5000th: 7992
99.9000th: 12176
min=0, max=14855
Quoted 1 line
p99 is back to a normal value but p99.5 stays higher than mainline
By how much and is that with the weight adjustment on the cgroup? I can't get reliable numbers on p99.5 and beyond on my test setup. I ordered the hikey board and will try to replicate your setup once it arrives.
Quoted 2 lines
I have also checked
load_avgandrunnable_load_avgvalue and there is something incorrect. I will provide details on the related patch
Sure, will respond there.
Thanks.
Signature · 1 line
tejun
Vincent Guittot
maintainerQuoted 14 lines · Tejun Heo
Hello, Vincent.
Quoted 11 lines · Vincent Guittot
schbench results looks better with this version
Latency percentiles (usec)
50.0000th: 212
75.0000th: 292
90.0000th: 385
95.0000th: 439
*99.0000th: 671
99.5000th: 7992
99.9000th: 12176
min=0, max=14855
Quoted 6 lines
Quoted 1 line
p99 is back to a normal value but p99.5 stays higher than mainline
By how much and is that with the weight adjustment on the cgroup? I can't get reliable numbers on p99.5 and beyond on my test setup. I ordered the hikey board and will try to replicate your setup once it arrives.
This is the results that I got when i tested you 1st version last week:
With v4.11-rc8. I have run 10 times the test and get consistent results schbench -m 2 -t 4 -s 10000 -c 15000 -r 30
Latency percentiles (usec)
50.0000th: 255
75.0000th: 350
90.0000th: 454
95.0000th: 489
*99.0000th: 539
99.5000th: 585
99.9000th: 10224
min=0, max=13567
Quoted 10 lines
Quoted 3 lines
I have also checked
load_avgandrunnable_load_avgvalue and there is something incorrect. I will provide details on the related patchSure, will respond there.
Thanks.
--
tejun