by Rik van Riel

[permalink] [raw]

Subject: Re: [PATCH 01/15] sched: introduce task_se_h_load helper

On Fri, 2019-08-23 at 20:13 +0200, Dietmar Eggemann wrote:
>
>
> > @@ -1668,7 +1668,7 @@ static void task_numa_compare(struct
> > task_numa_env *env,
> > /*
> > * In the overloaded case, try and keep the load balanced.
> > */
> > - load = task_h_load(env->p) - task_h_load(cur);
> > + load = task_se_h_load(env->p->se) - task_se_h_load(cur->se);
>
> Shouldn't this be:
>
> load = task_se_h_load(&env->p->se) - task_se_h_load(&cur->se);

Yes indeed. Sorry I forgot to fix these after you
pointed them out last time.

They are now fixed in my tree.

--
All Rights Reversed.

Attachments:

signature.asc (499.00 B)
This is a digitally signed message part

2019-08-24 01:17:50

On Wed, 2019-08-28 at 09:51 +0200, Dietmar Eggemann wrote:
> On 22/08/2019 04:17, Rik van Riel wrote:
> > Now that enqueue_task_fair and dequeue_task_fair no longer iterate
> > up
> > the hierarchy all the time, a method to lazily propagate
> > sum_exec_runtime
> > up the hierarchy is necessary.
> >
> > Once a tick, propagate the newly accumulated exec_runtime up the
> > hierarchy,
> > and feed it into CFS bandwidth control.
> >
> > Remove the pointless call to account_cfs_rq_runtime from
> > update_curr,
> > which is always called with a root cfs_rq.
>
> But what about the call to account_cfs_rq_runtime() in
> set_curr_task_fair()? Here you always call it with the root cfs_rq.
> Shouldn't this be called also in a loop over all se's until !se-
> >parent
> (like in propagate_exec_runtime() further below).

I believe that call should be only on the cgroup
cfs_rq, with account_cfs_rq_runtime figuring out
whether more runtime needs to be obtained from
further up in the hierarchy.

By default we should probably work under the assumption
that account_cfs_rq_runtime() will succeed at the current
level, and no gymnastics are required to obtain CPU time.

--
All Rights Reversed.

Attachments:

signature.asc (499.00 B)
This is a digitally signed message part

2019-08-28 13:52:23

by Vincent Guittot

[permalink] [raw]

Subject: Re: [PATCH 03/15] sched,fair: redefine runnable_load_avg as the sum of task_h_load

Hi Rik,

On Thu, 22 Aug 2019 at 04:18, Rik van Riel <[email protected]> wrote:
>
> The runnable_load magic is used to quickly propagate information about
> runnable tasks up the hierarchy of runqueues. The runnable_load_avg is
> mostly used for the load balancing code, which only examines the value at
> the root cfs_rq.
>
> Redefine the root cfs_rq runnable_load_avg to be the sum of task_h_loads
> of the runnable tasks. This works because the hierarchical runnable_load of
> a task is already equal to the task_se_h_load today. This provides enough
> information to the load balancer.
>
> The runnable_load_avg of the cgroup cfs_rqs does not appear to be
> used for anything, so don't bother calculating those.
>
> This removes one of the things that the code currently traverses the
> cgroup hierarchy for, and getting rid of it brings us one step closer
> to a flat runqueue for the CPU controller.

I like your proposal but just wanted to clarify one thing with this patch.
Although you removed the computation of runnable_load_avg of the
cgroup cfs_rq, we are still traversing the hierarchy to update the
root cfs_rq runnable_load_avg because we are traversing the hierarchy
for computing the task_h_loads

That being said, if we manage to remove the need on using
runnable_load_avg we will completely skip this traversal. I have a
proposal to remove it from load balance and wake up path but i haven't
look at numa stats which also use it

>
> Signed-off-by: Rik van Riel <[email protected]>
> ---
> include/linux/sched.h | 3 +-
> kernel/sched/core.c | 2 -
> kernel/sched/debug.c | 1 +
> kernel/sched/fair.c | 125 +++++++++++++-----------------------------
> kernel/sched/pelt.c | 64 ++++++---------------
> kernel/sched/sched.h | 6 --
> 6 files changed, 56 insertions(+), 145 deletions(-)
>
> diff --git a/include/linux/sched.h b/include/linux/sched.h
> index 11837410690f..f5bb6948e40c 100644
> --- a/include/linux/sched.h
> +++ b/include/linux/sched.h
> @@ -391,7 +391,6 @@ struct util_est {
> struct sched_avg {
> u64 last_update_time;
> u64 load_sum;
> - u64 runnable_load_sum;
> u32 util_sum;
> u32 period_contrib;
> unsigned long load_avg;
> @@ -439,7 +438,6 @@ 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;
> @@ -455,6 +453,7 @@ struct sched_entity {
>
> #ifdef CONFIG_FAIR_GROUP_SCHED
> int depth;
> + unsigned long enqueued_h_load;
> struct sched_entity *parent;
> /* rq on which this entity is (to be) queued: */
> struct cfs_rq *cfs_rq;
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 874c427742a9..fbd96900f715 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -744,7 +744,6 @@ static void set_load_weight(struct task_struct *p, bool update_load)
> if (task_has_idle_policy(p)) {
> load->weight = scale_load(WEIGHT_IDLEPRIO);
> load->inv_weight = WMULT_IDLEPRIO;
> - p->se.runnable_weight = load->weight;
> return;
> }
>
> @@ -757,7 +756,6 @@ static void set_load_weight(struct task_struct *p, bool update_load)
> } else {
> load->weight = scale_load(sched_prio_to_weight[prio]);
> load->inv_weight = sched_prio_to_wmult[prio];
> - p->se.runnable_weight = load->weight;
> }
> }
>
> diff --git a/kernel/sched/debug.c b/kernel/sched/debug.c
> index f6beaca97a09..cefc1b171c0b 100644
> --- a/kernel/sched/debug.c
> +++ b/kernel/sched/debug.c
> @@ -962,6 +962,7 @@ void proc_sched_show_task(struct task_struct *p, struct pid_namespace *ns,
> P(se.avg.load_avg);
> P(se.avg.runnable_load_avg);
> P(se.avg.util_avg);
> + P(se.enqueued_h_load);
> P(se.avg.last_update_time);
> P(se.avg.util_est.ewma);
> P(se.avg.util_est.enqueued);
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index eadf9a96b3e1..30afeda1620f 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -723,9 +723,7 @@ void init_entity_runnable_average(struct sched_entity *se)
> * nothing has been attached to the task group yet.
> */
> if (entity_is_task(se))
> - sa->runnable_load_avg = sa->load_avg = scale_load_down(se->load.weight);
> -
> - se->runnable_weight = se->load.weight;
> + sa->load_avg = scale_load_down(se->load.weight);
>
> /* when this task enqueue'ed, it will contribute to its cfs_rq's load_avg */
> }
> @@ -2766,20 +2764,39 @@ account_entity_dequeue(struct cfs_rq *cfs_rq, struct sched_entity *se)
> static inline void
> enqueue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
> {
> - cfs_rq->runnable_weight += se->runnable_weight;
> + if (entity_is_task(se)) {
> + struct cfs_rq *root_cfs_rq = &cfs_rq->rq->cfs;
> + se->enqueued_h_load = task_se_h_load(se);
>
> - cfs_rq->avg.runnable_load_avg += se->avg.runnable_load_avg;
> - cfs_rq->avg.runnable_load_sum += se_runnable(se) * se->avg.runnable_load_sum;
> + root_cfs_rq->avg.runnable_load_avg += se->enqueued_h_load;
> + }
> }
>
> static inline void
> dequeue_runnable_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se)
> {
> - cfs_rq->runnable_weight -= se->runnable_weight;
> + if (entity_is_task(se)) {
> + struct cfs_rq *root_cfs_rq = &cfs_rq->rq->cfs;
> + sub_positive(&root_cfs_rq->avg.runnable_load_avg,
> + se->enqueued_h_load);
> + }
> +}
> +
> +static inline void
> +update_runnable_load_avg(struct sched_entity *se)
> +{
> + struct cfs_rq *root_cfs_rq = &cfs_rq_of(se)->rq->cfs;
> + long new_h_load, delta;
>
> - sub_positive(&cfs_rq->avg.runnable_load_avg, se->avg.runnable_load_avg);
> - sub_positive(&cfs_rq->avg.runnable_load_sum,
> - se_runnable(se) * se->avg.runnable_load_sum);
> + SCHED_WARN_ON(!entity_is_task(se));
> +
> + if (!se->on_rq)
> + return;
> +
> + new_h_load = task_se_h_load(se);
> + delta = new_h_load - se->enqueued_h_load;
> + root_cfs_rq->avg.runnable_load_avg += delta;
> + se->enqueued_h_load = new_h_load;
> }
>
> static inline void
> @@ -2807,7 +2824,7 @@ dequeue_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *se) { }
> #endif
>
> static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
> - unsigned long weight, unsigned long runnable)
> + unsigned long weight)
> {
> if (se->on_rq) {
> /* commit outstanding execution time */
> @@ -2818,7 +2835,6 @@ static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
> }
> dequeue_load_avg(cfs_rq, se);
>
> - se->runnable_weight = runnable;
> update_load_set(&se->load, weight);
>
> #ifdef CONFIG_SMP
> @@ -2826,8 +2842,6 @@ static void reweight_entity(struct cfs_rq *cfs_rq, struct sched_entity *se,
> u32 divider = LOAD_AVG_MAX - 1024 + se->avg.period_contrib;
>
> se->avg.load_avg = div_u64(se_weight(se) * se->avg.load_sum, divider);
> - se->avg.runnable_load_avg =
> - div_u64(se_runnable(se) * se->avg.runnable_load_sum, divider);
> } while (0);
> #endif
>
> @@ -2845,7 +2859,7 @@ void reweight_task(struct task_struct *p, int prio)
> struct load_weight *load = &se->load;
> unsigned long weight = scale_load(sched_prio_to_weight[prio]);
>
> - reweight_entity(cfs_rq, se, weight, weight);
> + reweight_entity(cfs_rq, se, weight);
> load->inv_weight = sched_prio_to_wmult[prio];
> }
>
> @@ -2958,49 +2972,6 @@ static long calc_group_shares(struct cfs_rq *cfs_rq)
> return clamp_t(long, shares, MIN_SHARES, tg_shares);
> }
>
> -/*
> - * 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.
> - *
> - * 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 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 */
>
> static inline int throttled_hierarchy(struct cfs_rq *cfs_rq);
> @@ -3012,25 +2983,26 @@ static inline int throttled_hierarchy(struct cfs_rq *cfs_rq);
> static void update_cfs_group(struct sched_entity *se)
> {
> struct cfs_rq *gcfs_rq = group_cfs_rq(se);
> - long shares, runnable;
> + long shares;
>
> - if (!gcfs_rq)
> + if (!gcfs_rq) {
> + update_runnable_load_avg(se);
> return;
> + }
>
> if (throttled_hierarchy(gcfs_rq))
> return;
>
> #ifndef CONFIG_SMP
> - runnable = shares = READ_ONCE(gcfs_rq->tg->shares);
> + shares = READ_ONCE(gcfs_rq->tg->shares);
>
> if (likely(se->load.weight == shares))
> return;
> #else
> shares = calc_group_shares(gcfs_rq);
> - runnable = calc_group_runnable(gcfs_rq, shares);
> #endif
>
> - reweight_entity(cfs_rq_of(se), se, shares, runnable);
> + reweight_entity(cfs_rq_of(se), se, shares);
> }
>
> #else /* CONFIG_FAIR_GROUP_SCHED */
> @@ -3243,8 +3215,8 @@ static inline void
> update_tg_cfs_runnable(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cfs_rq *gcfs_rq)
> {
> 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;
> + unsigned long load_avg;
> + u64 load_sum = 0;
> s64 delta_sum;
>
> if (!runnable_sum)
> @@ -3292,19 +3264,6 @@ update_tg_cfs_runnable(struct cfs_rq *cfs_rq, struct sched_entity *se, struct cf
> 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);
> - }
> }
>
> static inline void add_tg_cfs_propagate(struct cfs_rq *cfs_rq, long runnable_sum)
> @@ -3399,7 +3358,7 @@ static inline void add_tg_cfs_propagate(struct cfs_rq *cfs_rq, long runnable_sum
> static inline int
> update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq)
> {
> - unsigned long removed_load = 0, removed_util = 0, removed_runnable_sum = 0;
> + unsigned long removed_load = 0, removed_util = 0;
> struct sched_avg *sa = &cfs_rq->avg;
> int decayed = 0;
>
> @@ -3410,7 +3369,6 @@ update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq)
> raw_spin_lock(&cfs_rq->removed.lock);
> swap(cfs_rq->removed.util_avg, removed_util);
> swap(cfs_rq->removed.load_avg, removed_load);
> - swap(cfs_rq->removed.runnable_sum, removed_runnable_sum);
> cfs_rq->removed.nr = 0;
> raw_spin_unlock(&cfs_rq->removed.lock);
>
> @@ -3422,8 +3380,6 @@ update_cfs_rq_load_avg(u64 now, struct cfs_rq *cfs_rq)
> sub_positive(&sa->util_avg, r);
> sub_positive(&sa->util_sum, r * divider);
>
> - add_tg_cfs_propagate(cfs_rq, -(long)removed_runnable_sum);
> -
> decayed = 1;
> }
>
> @@ -3477,8 +3433,6 @@ static void attach_entity_load_avg(struct cfs_rq *cfs_rq, struct sched_entity *s
> 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;
> @@ -7735,9 +7689,6 @@ static inline bool cfs_rq_is_decayed(struct cfs_rq *cfs_rq)
> if (cfs_rq->avg.util_sum)
> return false;
>
> - if (cfs_rq->avg.runnable_load_sum)
> - return false;
> -
> return true;
> }
>
> diff --git a/kernel/sched/pelt.c b/kernel/sched/pelt.c
> index befce29bd882..b3f3e8b29394 100644
> --- a/kernel/sched/pelt.c
> +++ b/kernel/sched/pelt.c
> @@ -106,7 +106,7 @@ static u32 __accumulate_pelt_segments(u64 periods, u32 d1, u32 d3)
> */
> static __always_inline u32
> accumulate_sum(u64 delta, struct sched_avg *sa,
> - unsigned long load, unsigned long runnable, int running)
> + unsigned long load, int running)
> {
> u32 contrib = (u32)delta; /* p == 0 -> delta < 1024 */
> u64 periods;
> @@ -119,8 +119,6 @@ accumulate_sum(u64 delta, struct sched_avg *sa,
> */
> if (periods) {
> sa->load_sum = decay_load(sa->load_sum, periods);
> - sa->runnable_load_sum =
> - decay_load(sa->runnable_load_sum, periods);
> sa->util_sum = decay_load((u64)(sa->util_sum), periods);
>
> /*
> @@ -134,8 +132,6 @@ accumulate_sum(u64 delta, struct sched_avg *sa,
>
> if (load)
> sa->load_sum += load * contrib;
> - if (runnable)
> - sa->runnable_load_sum += runnable * contrib;
> if (running)
> sa->util_sum += contrib << SCHED_CAPACITY_SHIFT;
>
> @@ -172,7 +168,7 @@ accumulate_sum(u64 delta, struct sched_avg *sa,
> */
> static __always_inline int
> ___update_load_sum(u64 now, struct sched_avg *sa,
> - unsigned long load, unsigned long runnable, int running)
> + unsigned long load, int running)
> {
> u64 delta;
>
> @@ -206,7 +202,7 @@ ___update_load_sum(u64 now, struct sched_avg *sa,
> * update_blocked_averages()
> */
> if (!load)
> - runnable = running = 0;
> + running = 0;
>
> /*
> * Now we know we crossed measurement unit boundaries. The *_avg
> @@ -215,14 +211,14 @@ ___update_load_sum(u64 now, struct sched_avg *sa,
> * Step 1: accumulate *_sum since last_update_time. If we haven't
> * crossed period boundaries, finish.
> */
> - if (!accumulate_sum(delta, sa, load, runnable, running))
> + if (!accumulate_sum(delta, sa, load, running))
> return 0;
>
> return 1;
> }
>
> static __always_inline void
> -___update_load_avg(struct sched_avg *sa, unsigned long load, unsigned long runnable)
> +___update_load_avg(struct sched_avg *sa, unsigned long load)
> {
> u32 divider = LOAD_AVG_MAX - 1024 + sa->period_contrib;
>
> @@ -230,41 +226,25 @@ ___update_load_avg(struct sched_avg *sa, unsigned long load, unsigned long runna
> * Step 2: update *_avg.
> */
> sa->load_avg = div_u64(load * sa->load_sum, divider);
> - sa->runnable_load_avg = div_u64(runnable * sa->runnable_load_sum, divider);
> WRITE_ONCE(sa->util_avg, sa->util_sum / divider);
> }
>
> /*
> * sched_entity:
> *
> - * task:
> - * se_runnable() == se_weight()
> - *
> - * group: [ see update_cfs_group() ]
> - * se_weight() = tg->weight * grq->load_avg / tg->load_avg
> - * se_runnable() = se_weight(se) * grq->runnable_load_avg / grq->load_avg
> - *
> * load_sum := runnable_sum
> * load_avg = se_weight(se) * runnable_avg
> *
> - * runnable_load_sum := runnable_sum
> - * runnable_load_avg = se_runnable(se) * runnable_avg
> - *
> - * XXX collapse load_sum and runnable_load_sum
> - *
> * cfq_rq:
> *
> * load_sum = \Sum se_weight(se) * se->avg.load_sum
> * load_avg = \Sum se->avg.load_avg
> - *
> - * runnable_load_sum = \Sum se_runnable(se) * se->avg.runnable_load_sum
> - * runnable_load_avg = \Sum se->avg.runable_load_avg
> */
>
> int __update_load_avg_blocked_se(u64 now, struct sched_entity *se)
> {
> - if (___update_load_sum(now, &se->avg, 0, 0, 0)) {
> - ___update_load_avg(&se->avg, se_weight(se), se_runnable(se));
> + if (___update_load_sum(now, &se->avg, 0, 0)) {
> + ___update_load_avg(&se->avg, se_weight(se));
> return 1;
> }
>
> @@ -273,10 +253,10 @@ int __update_load_avg_blocked_se(u64 now, struct sched_entity *se)
>
> int __update_load_avg_se(u64 now, struct cfs_rq *cfs_rq, struct sched_entity *se)
> {
> - if (___update_load_sum(now, &se->avg, !!se->on_rq, !!se->on_rq,
> + if (___update_load_sum(now, &se->avg, !!se->on_rq,
> cfs_rq->curr == se)) {
>
> - ___update_load_avg(&se->avg, se_weight(se), se_runnable(se));
> + ___update_load_avg(&se->avg, se_weight(se));
> cfs_se_util_change(&se->avg);
> return 1;
> }
> @@ -288,10 +268,9 @@ int __update_load_avg_cfs_rq(u64 now, struct cfs_rq *cfs_rq)
> {
> if (___update_load_sum(now, &cfs_rq->avg,
> scale_load_down(cfs_rq->load.weight),
> - scale_load_down(cfs_rq->runnable_weight),
> cfs_rq->curr != NULL)) {
>
> - ___update_load_avg(&cfs_rq->avg, 1, 1);
> + ___update_load_avg(&cfs_rq->avg, 1);
> return 1;
> }
>
> @@ -303,20 +282,18 @@ int __update_load_avg_cfs_rq(u64 now, struct cfs_rq *cfs_rq)
> *
> * util_sum = \Sum se->avg.util_sum but se->avg.util_sum is not tracked
> * util_sum = cpu_scale * load_sum
> - * runnable_load_sum = load_sum
> *
> - * load_avg and runnable_load_avg are not supported and meaningless.
> + * load_avg is not supported and meaningless.
> *
> */
>
> int update_rt_rq_load_avg(u64 now, struct rq *rq, int running)
> {
> if (___update_load_sum(now, &rq->avg_rt,
> - running,
> running,
> running)) {
>
> - ___update_load_avg(&rq->avg_rt, 1, 1);
> + ___update_load_avg(&rq->avg_rt, 1);
> return 1;
> }
>
> @@ -328,18 +305,16 @@ int update_rt_rq_load_avg(u64 now, struct rq *rq, int running)
> *
> * util_sum = \Sum se->avg.util_sum but se->avg.util_sum is not tracked
> * util_sum = cpu_scale * load_sum
> - * runnable_load_sum = load_sum
> *
> */
>
> int update_dl_rq_load_avg(u64 now, struct rq *rq, int running)
> {
> if (___update_load_sum(now, &rq->avg_dl,
> - running,
> running,
> running)) {
>
> - ___update_load_avg(&rq->avg_dl, 1, 1);
> + ___update_load_avg(&rq->avg_dl, 1);
> return 1;
> }
>
> @@ -352,7 +327,6 @@ int update_dl_rq_load_avg(u64 now, struct rq *rq, int running)
> *
> * util_sum = \Sum se->avg.util_sum but se->avg.util_sum is not tracked
> * util_sum = cpu_scale * load_sum
> - * runnable_load_sum = load_sum
> *
> */
>
> @@ -379,17 +353,11 @@ int update_irq_load_avg(struct rq *rq, u64 running)
> * We can safely remove running from rq->clock because
> * rq->clock += delta with delta >= running
> */
> - ret = ___update_load_sum(rq->clock - running, &rq->avg_irq,
> - 0,
> - 0,
> - 0);
> - ret += ___update_load_sum(rq->clock, &rq->avg_irq,
> - 1,
> - 1,
> - 1);
> + ret = ___update_load_sum(rq->clock - running, &rq->avg_irq, 0, 0);
> + ret += ___update_load_sum(rq->clock, &rq->avg_irq, 1, 1);
>
> if (ret)
> - ___update_load_avg(&rq->avg_irq, 1, 1);
> + ___update_load_avg(&rq->avg_irq, 1);
>
> return ret;
> }
> diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
> index b52ed1ada0be..5be14cee61f9 100644
> --- a/kernel/sched/sched.h
> +++ b/kernel/sched/sched.h
> @@ -487,7 +487,6 @@ struct cfs_bandwidth { };
> /* CFS-related fields in a runqueue */
> struct cfs_rq {
> struct load_weight load;
> - unsigned long runnable_weight;
> unsigned int nr_running;
> unsigned int h_nr_running;
>
> @@ -700,11 +699,6 @@ static inline long se_weight(struct sched_entity *se)
> return scale_load_down(se->load.weight);
> }
>
> -static inline long se_runnable(struct sched_entity *se)
> -{
> - return scale_load_down(se->runnable_weight);
> -}
> -
> static inline bool sched_asym_prefer(int a, int b)
> {
> return arch_asym_cpu_priority(a) > arch_asym_cpu_priority(b);
> --
> 2.20.1
>

2019-08-28 13:55:18

by Vincent Guittot

[permalink] [raw]

Subject: Re: [PATCH 06/15] sched,cfs: use explicit cfs_rq of parent se helper

On Thu, 22 Aug 2019 at 04:18, Rik van Riel <[email protected]> wrote:
>
> Use an explicit "cfs_rq of parent sched_entity" helper in a few
> strategic places, where cfs_rq_of(se) may no longer point at the

The only case is the sched_entity of a task which will point to root
cfs, isn't it ?

> right runqueue once we flatten the hierarchical cgroup runqueues.
>
> No functional change.
>
> Signed-off-by: Rik van Riel <[email protected]>
> ---
> kernel/sched/fair.c | 17 +++++++++++++----
> 1 file changed, 13 insertions(+), 4 deletions(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 04b216234265..31a26737a873 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -276,6 +276,15 @@ static inline struct cfs_rq *group_cfs_rq(struct sched_entity *grp)
> return grp->my_q;
> }
>
> +/* runqueue owned by the parent entity; the root cfs_rq for a top level se */
> +static inline struct cfs_rq *group_cfs_rq_of_parent(struct sched_entity *se)
> +{
> + if (se->parent)
> + return group_cfs_rq(se->parent);
> +
> + return cfs_rq_of(se);
> +}
> +
> static inline bool list_add_leaf_cfs_rq(struct cfs_rq *cfs_rq)
> {
> struct rq *rq = rq_of(cfs_rq);
> @@ -3319,7 +3328,7 @@ static inline int propagate_entity_load_avg(struct sched_entity *se)
>
> gcfs_rq->propagate = 0;
>
> - cfs_rq = cfs_rq_of(se);
> + cfs_rq = group_cfs_rq_of_parent(se);
>
> add_tg_cfs_propagate(cfs_rq, gcfs_rq->prop_runnable_sum);
>
> @@ -7796,7 +7805,7 @@ static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq)
>
> WRITE_ONCE(cfs_rq->h_load_next, NULL);
> for_each_sched_entity(se) {
> - cfs_rq = cfs_rq_of(se);
> + cfs_rq = group_cfs_rq_of_parent(se);
> WRITE_ONCE(cfs_rq->h_load_next, se);
> if (cfs_rq->last_h_load_update == now)
> break;
> @@ -7819,7 +7828,7 @@ static void update_cfs_rq_h_load(struct cfs_rq *cfs_rq)
>
> static unsigned long task_se_h_load(struct sched_entity *se)
> {
> - struct cfs_rq *cfs_rq = cfs_rq_of(se);
> + struct cfs_rq *cfs_rq = group_cfs_rq_of_parent(se);
>
> update_cfs_rq_h_load(cfs_rq);
> return div64_ul(se->avg.load_avg * cfs_rq->h_load,
> @@ -10166,7 +10175,7 @@ static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
> struct sched_entity *se = &curr->se;
>
> for_each_sched_entity(se) {
> - cfs_rq = cfs_rq_of(se);
> + cfs_rq = group_cfs_rq_of_parent(se);
> entity_tick(cfs_rq, se, queued);
> }
>
> --
> 2.20.1
>

2019-08-28 14:13:21

by Vincent Guittot

[permalink] [raw]

Subject: Re: [PATCH 05/15] sched,fair: remove cfs_rqs from leaf_cfs_rq_list bottom up

On Thu, 22 Aug 2019 at 04:18, Rik van Riel <[email protected]> wrote:
>
> Reducing the overhead of the CPU controller is achieved by not walking
> all the sched_entities every time a task is enqueued or dequeued.
>
> One of the things being checked every single time is whether the cfs_rq
> is on the rq->leaf_cfs_rq_list.
>
> By only removing a cfs_rq from the list once it no longer has children
> on the list, we can avoid walking the sched_entity hierarchy if the bottom
> cfs_rq is on the list, once the runqueues have been flattened.
>
> Signed-off-by: Rik van Riel <[email protected]>
> Suggested-by: Vincent Guittot <[email protected]>

Acked-by: Vincent Guittot <[email protected]>

> ---
> kernel/sched/fair.c | 35 ++++++++++++++++++++++++++++++++++-
> 1 file changed, 34 insertions(+), 1 deletion(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index a48d0dbfc232..04b216234265 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -369,6 +369,39 @@ static inline void assert_list_leaf_cfs_rq(struct rq *rq)
> SCHED_WARN_ON(rq->tmp_alone_branch != &rq->leaf_cfs_rq_list);
> }
>
> +/*
> + * Because list_add_leaf_cfs_rq always places a child cfs_rq on the list
> + * immediately before a parent cfs_rq, and cfs_rqs are removed from the list
> + * bottom-up, we only have to test whether the cfs_rq before us on the list
> + * is our child.
> + */
> +static inline bool child_cfs_rq_on_list(struct cfs_rq *cfs_rq)
> +{
> + struct cfs_rq *prev_cfs_rq;
> + struct list_head *prev;
> +
> + prev = cfs_rq->leaf_cfs_rq_list.prev;
> + prev_cfs_rq = container_of(prev, struct cfs_rq, leaf_cfs_rq_list);
> +
> + return (prev_cfs_rq->tg->parent == cfs_rq->tg);
> +}
> +
> +/*
> + * Remove a cfs_rq from the list if it has no children on the list.
> + * The scheduler iterates over the list regularly; if conditions for
> + * removal are still true, we'll get to this cfs_rq in the future.
> + */
> +static inline void list_del_leaf_cfs_rq_bottom(struct cfs_rq *cfs_rq)
> +{
> + if (!cfs_rq->on_list)
> + return;
> +
> + if (child_cfs_rq_on_list(cfs_rq))
> + return;
> +
> + list_del_leaf_cfs_rq(cfs_rq);
> +}
> +
> /* Iterate thr' all leaf cfs_rq's on a runqueue */
> #define for_each_leaf_cfs_rq_safe(rq, cfs_rq, pos) \
> list_for_each_entry_safe(cfs_rq, pos, &rq->leaf_cfs_rq_list, \
> @@ -7723,7 +7756,7 @@ static void update_blocked_averages(int cpu)
> * decayed cfs_rqs linger on the list.
> */
> if (cfs_rq_is_decayed(cfs_rq))
> - list_del_leaf_cfs_rq(cfs_rq);
> + list_del_leaf_cfs_rq_bottom(cfs_rq);
>
> /* Don't need periodic decay once load/util_avg are null */
> if (cfs_rq_has_blocked(cfs_rq))
> --
> 2.20.1
>

2019-08-28 14:49:36

On Wed, 2019-08-28 at 15:53 +0200, Vincent Guittot wrote:
> On Thu, 22 Aug 2019 at 04:18, Rik van Riel <[email protected]> wrote:
> > Use an explicit "cfs_rq of parent sched_entity" helper in a few
> > strategic places, where cfs_rq_of(se) may no longer point at the
>
> The only case is the sched_entity of a task which will point to root
> cfs, isn't it ?

True. I am more than open to ideas to simplify this
part of the code, hopefully in some way that makes
it easier to read.

--
All Rights Reversed.

Attachments:

signature.asc (499.00 B)
This is a digitally signed message part

2019-08-28 16:36:25

by Vincent Guittot

[permalink] [raw]

Subject: Re: [PATCH 06/15] sched,cfs: use explicit cfs_rq of parent se helper

by Dietmar Eggemann

[permalink] [raw]

Subject: Re: [PATCH RFC v4 0/15] sched,fair: flatten CPU controller runqueues

On 22/08/2019 04:17, Rik van Riel wrote:
> The current implementation of the CPU controller uses hierarchical
> runqueues, where on wakeup a task is enqueued on its group's runqueue,
> the group is enqueued on the runqueue of the group above it, etc.
>
> This increases a fairly large amount of overhead for workloads that
> do a lot of wakeups a second, especially given that the default systemd
> hierarchy is 2 or 3 levels deep.
>
> This patch series is an attempt at reducing that overhead, by placing
> all the tasks on the same runqueue, and scaling the task priority by
> the priority of the group, which is calculated periodically.
>
> My main TODO items for the next period of time are likely going to
> be testing, testing, and testing. I hope to find and flush out any
> corner case I can find, and make sure performance does not regress
> with any workloads, and hopefully improves some.

I did some testing with a small & simple rt-app based test-case:

2 CPUs (rq->cpu_capacity_orig=1024), CPUfreq performance governor

2 taskgroups /tg0 and /tg1

6 CFS tasks (periodic, 8/16ms (runtime/period))

/tg0 (cpu.shares=1024) ran 4 tasks and /tg1 (cpu.shares=1024) ran 2 tasks

(arm64 defconfig with !CONFIG_NUMA_BALANCING, !CONFIG_SCHED_AUTOGROUP)

---

v5.2:

The 2 /tg1 tasks ran 8/16ms. The 4 /tg0 tasks ran 4/16ms in the
beginning and then 8/16ms after the 2 /tg1 tasks did finish.

---

v5.2 + v4:

There is no runtime/period pattern visible anymore. I see a lot of extra
wakeup latency for those tasks though.

v5.2 + (v4 without 07/15, 08/15, 15/15) didn't change much.

---

I could try to reduce the stack even further (e.g. without 13/15).

IMHO it's a good idea to have a set of these small & simple test-cases
handy to verify that the base-functionality is still in place. This
might be hard to achieve with benchmarks.

2019-09-02 17:48:51

by Rik van Riel

[permalink] [raw]

Subject: Re: [PATCH 08/15] sched,fair: simplify timeslice length code

On Mon, 2019-09-02 at 09:51 +0200, Vincent Guittot wrote:
> On Fri, 30 Aug 2019 at 17:02, Rik van Riel <[email protected]> wrote:

> > I would be more than happy to drop this patch if you
> > prefer. Just let me know.
>
> If i'm not wrong, this change is not mandatory to flatten the
> runqueue and because of the possible impact if you would prefer to
> drop it from this serie

OK, will do.

--
All Rights Reversed.

Attachments:

signature.asc (499.00 B)
This is a digitally signed message part

2019-09-03 01:45:38

On Tue, 2019-09-03 at 17:38 +0200, Vincent Guittot wrote:
> Hi Rik,
>
> On Thu, 22 Aug 2019 at 04:18, Rik van Riel <[email protected]> wrote:
> > Refactor enqueue_entity, dequeue_entity, and update_load_avg, in
> > order
> > to split out the things we still want to happen at every level in
> > the
> > cgroup hierarchy with a flat runqueue from the things we only need
> > to
> > happen once.
> >
> > No functional changes.
> >
> > Signed-off-by: Rik van Riel <[email protected]>
> > ---
> > kernel/sched/fair.c | 64 +++++++++++++++++++++++++++++----------
> > ------
> > 1 file changed, 42 insertions(+), 22 deletions(-)
> >
> > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > index 74ee22c59d13..7b0d95f2e3a8 100644
> > --- a/kernel/sched/fair.c
> > +++ b/kernel/sched/fair.c
> > @@ -3502,7 +3502,7 @@ static void detach_entity_load_avg(struct
> > cfs_rq *cfs_rq, struct sched_entity *s
> > #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)
> > +static inline bool update_load_avg(struct cfs_rq *cfs_rq, struct
> > sched_entity *se, int flags)
> > {
> > u64 now = cfs_rq_clock_pelt(cfs_rq);
> > int decayed;
> > @@ -3531,6 +3531,8 @@ static inline void update_load_avg(struct
> > cfs_rq *cfs_rq, struct sched_entity *s
> >
> > } else if (decayed && (flags & UPDATE_TG))
> > update_tg_load_avg(cfs_rq, 0);
> > +
> > + return decayed;
>
> This is a functional change, isn't it ?
> update_cfs_group is now called only if decayed but we can we attach a
> task during the enqueue and there is no decay

Yes, it is, and patch 11 changes the way this functional
change is done.

If you want, I can change this patch to not have the
functional change, though in the end it should not make
any difference.

--
All Rights Reversed.

Attachments:

signature.asc (499.00 B)
This is a digitally signed message part

2019-09-04 06:46:02

by Vincent Guittot

[permalink] [raw]

Subject: Re: [PATCH 09/15] sched,fair: refactor enqueue/dequeue_entity

On Tue, 3 Sep 2019 at 22:27, Rik van Riel <[email protected]> wrote:
>
> On Tue, 2019-09-03 at 17:38 +0200, Vincent Guittot wrote:
> > Hi Rik,
> >
> > On Thu, 22 Aug 2019 at 04:18, Rik van Riel <[email protected]> wrote:
> > > Refactor enqueue_entity, dequeue_entity, and update_load_avg, in
> > > order
> > > to split out the things we still want to happen at every level in
> > > the
> > > cgroup hierarchy with a flat runqueue from the things we only need
> > > to
> > > happen once.
> > >
> > > No functional changes.
> > >
> > > Signed-off-by: Rik van Riel <[email protected]>
> > > ---
> > > kernel/sched/fair.c | 64 +++++++++++++++++++++++++++++----------
> > > ------
> > > 1 file changed, 42 insertions(+), 22 deletions(-)
> > >
> > > diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> > > index 74ee22c59d13..7b0d95f2e3a8 100644
> > > --- a/kernel/sched/fair.c
> > > +++ b/kernel/sched/fair.c
> > > @@ -3502,7 +3502,7 @@ static void detach_entity_load_avg(struct
> > > cfs_rq *cfs_rq, struct sched_entity *s
> > > #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)
> > > +static inline bool update_load_avg(struct cfs_rq *cfs_rq, struct
> > > sched_entity *se, int flags)
> > > {
> > > u64 now = cfs_rq_clock_pelt(cfs_rq);
> > > int decayed;
> > > @@ -3531,6 +3531,8 @@ static inline void update_load_avg(struct
> > > cfs_rq *cfs_rq, struct sched_entity *s
> > >
> > > } else if (decayed && (flags & UPDATE_TG))
> > > update_tg_load_avg(cfs_rq, 0);
> > > +
> > > + return decayed;
> >
> > This is a functional change, isn't it ?
> > update_cfs_group is now called only if decayed but we can we attach a
> > task during the enqueue and there is no decay
>
> Yes, it is, and patch 11 changes the way this functional
> change is done.
>
> If you want, I can change this patch to not have the
> functional change, though in the end it should not make
> any difference.

It's mainly that the code is not aligned with the commit message

I will continue to review other patch and will come back to this one
after reviewing patch 11

Thanks
Vincent
>
> --
> All Rights Reversed.