lkml.org 
[lkml]   [2019]   [Aug]   [6]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patches in this message
    /
    SubjectRe: [PATCH v2 4/8] sched/fair: rework load_balance
    From
    Date
    Second batch, get it while it's hot...

    On 01/08/2019 15:40, Vincent Guittot wrote:
    [...]
    > @@ -7438,19 +7453,53 @@ static int detach_tasks(struct lb_env *env)
    > if (!can_migrate_task(p, env))
    > goto next;
    >
    > - load = task_h_load(p);
    > + switch (env->balance_type) {
    > + case migrate_task:
    > + /* Migrate task */
    > + env->imbalance--;
    > + break;
    >
    > - if (sched_feat(LB_MIN) && load < 16 && !env->sd->nr_balance_failed)
    > - goto next;
    > + case migrate_util:
    > + util = task_util_est(p);
    >
    > - if ((load / 2) > env->imbalance)
    > - goto next;
    > + if (util > env->imbalance)
    > + goto next;
    > +
    > + env->imbalance -= util;
    > + break;
    > +
    > + case migrate_load:
    > + load = task_h_load(p);
    > +
    > + if (sched_feat(LB_MIN) &&
    > + load < 16 && !env->sd->nr_balance_failed)
    > + goto next;
    > +
    > + if ((load / 2) > env->imbalance)
    > + goto next;
    > +
    > + env->imbalance -= load;
    > + break;
    > +
    > + case migrate_misfit:
    > + load = task_h_load(p);
    > +
    > + /*
    > + * utilization of misfit task might decrease a bit
    > + * since it has been recorded. Be conservative in the
    > + * condition.
    > + */
    > + if (load < env->imbalance)
    > + goto next;
    > +
    > + env->imbalance = 0;
    > + break;
    > + }
    >
    > detach_task(p, env);
    > list_add(&p->se.group_node, &env->tasks);
    >
    > detached++;
    > - env->imbalance -= load;
    >

    It's missing something like this:

    -----8<-----
    diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
    index b0631ff2a4bd..055563e19090 100644
    --- a/kernel/sched/fair.c
    +++ b/kernel/sched/fair.c
    @@ -7506,7 +7506,7 @@ static int detach_tasks(struct lb_env *env)

    /*
    * We only want to steal up to the prescribed amount of
    - * runnable load.
    + * load/util/tasks
    */
    if (env->imbalance <= 0)
    break;
    ----->8-----
    [...]
    > @@ -8013,19 +8059,26 @@ group_smaller_max_cpu_capacity(struct sched_group *sg, struct sched_group *ref)
    > }
    >
    > static inline enum
    > -group_type group_classify(struct sched_group *group,
    > +group_type group_classify(struct lb_env *env,
    > + struct sched_group *group,
    > struct sg_lb_stats *sgs)
    > {
    > - if (sgs->group_no_capacity)
    > + if (group_is_overloaded(env, sgs))
    > return group_overloaded;
    >
    > if (sg_imbalanced(group))
    > return group_imbalanced;
    >
    > + if (sgs->group_asym_capacity)
    > + return group_asym_capacity;
    > +
    > if (sgs->group_misfit_task_load)
    > return group_misfit_task;
    >
    > - return group_other;
    > + if (!group_has_capacity(env, sgs))
    > + return group_fully_busy;

    If I got my booleans right, reaching group_fully_busy means
    !group_is_overloaded() && !group_has_capacity(), which gives us:

    - If nr_running > group_weight, then we had to have
    sgs->group_capacity * 100 == sgs->group_util * env->sd->imbalance_pct
    - If nr_running == group_weight, then we had to have
    sgs->group_capacity * 100 <= sgs->group_util * env->sd->imbalance_pct

    - (if nr_running < group_weight we go to group_has_spare)

    That first equality seems somewhat odd considering how rarely it will
    occur, but then we still want the util check to fall down to
    group_has_spare when

    nr_running >= group_weight &&
    sgs->group_capacity * 100 > sgs->group_util * env->sd->imbalance_pct
    Maybe we could change group_has_capacity()'s util comparison from '>' to
    '>=' to avoid this weird "artefact".

    > +
    > + return group_has_spare;
    > }
    >
    > static bool update_nohz_stats(struct rq *rq, bool force)

    [...]
    > @@ -8147,11 +8223,67 @@ static bool update_sd_pick_busiest(struct lb_env *env,
    > if (sgs->group_type < busiest->group_type)
    > return false;
    >
    > - if (sgs->avg_load <= busiest->avg_load)
    > + /*
    > + * The candidate and the current busiest group are the same type of
    > + * group. Let check which one is the busiest according to the type.
    > + */
    > +
    > + switch (sgs->group_type) {
    > + case group_overloaded:
    > + /* Select the overloaded group with highest avg_load. */
    > + if (sgs->avg_load <= busiest->avg_load)
    > + return false;
    > + break;
    > +
    > + case group_imbalanced:
    > + /* Select the 1st imbalanced group as we don't have
    > + * any way to choose one more than another
    > + */
    > return false;
    > + break;
    >
    > - if (!(env->sd->flags & SD_ASYM_CPUCAPACITY))
    > - goto asym_packing;
    > + case group_asym_capacity:
    > + /* Prefer to move from lowest priority CPU's work */
    > + if (sched_asym_prefer(sg->asym_prefer_cpu, sds->busiest->asym_prefer_cpu))
    > + return false;
    > + break;
    > +
    > + case group_misfit_task:
    > + /*
    > + * If we have more than one misfit sg go with the
    > + * biggest misfit.
    > + */
    > + if (sgs->group_misfit_task_load < busiest->group_misfit_task_load)
    > + return false;
    > + break;
    > +
    > + case group_fully_busy:
    > + /*
    > + * Select the fully busy group with highest avg_load.
    > + * In theory, there is no need to pull task from such
    > + * kind of group because tasks have all compute
    > + * capacity that they need but we can still improve the
    > + * overall throughput by reducing contention when
    > + * accessing shared HW resources.
    > + * XXX for now avg_load is not computed and always 0 so
    > + * we select the 1st one.
    > + */

    What's wrong with unconditionally computing avg_load in update_sg_lb_stats()?
    We already unconditionally accumulate group_load anyway.

    If it's to make way for patch 6/8 (using load instead of runnable load),
    then I think you are doing things in the wrong order. IMO in this patch we
    should unconditionally compute avg_load (using runnable load), and then
    you could tweak it up in a subsequent patch.

    > + if (sgs->avg_load <= busiest->avg_load)
    > + return false;
    > + break;
    > +
    > + case group_has_spare:
    > + /*
    > + * Select not overloaded group with lowest number of
    > + * idle cpus. We could also compare the spare capacity
    > + * which is more stable but it can end up that the
    > + * group has less spare capacity but finally more idle
    > + * cpus which means less opportunity to pull tasks.
    > + */
    > + if (sgs->idle_cpus >= busiest->idle_cpus)
    > + return false;
    > + break;
    > + }
    >
    > /*
    > * Candidate sg has no more than one task per CPU and

    [...]
    > @@ -8341,69 +8421,132 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
    > */
    > static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *sds)
    > {
    > - unsigned long max_pull, load_above_capacity = ~0UL;
    > struct sg_lb_stats *local, *busiest;
    >
    > local = &sds->local_stat;
    > busiest = &sds->busiest_stat;
    > + if (busiest->group_type == group_imbalanced) {
    > + /*
    > + * In the group_imb case we cannot rely on group-wide averages
    > + * to ensure CPU-load equilibrium, try to move any task to fix
    > + * the imbalance. The next load balance will take care of
    > + * balancing back the system.
    > + */
    > + env->balance_type = migrate_task;
    > + env->imbalance = 1;
    > + return;
    > + }
    >
    > - if (busiest->group_asym_capacity) {
    > + if (busiest->group_type == group_asym_capacity) {
    > + /*
    > + * In case of asym capacity, we will try to migrate all load
    > + * to the preferred CPU
    > + */
    > + env->balance_type = migrate_load;
    > env->imbalance = busiest->group_load;
    > return;
    > }
    >
    > + if (busiest->group_type == group_misfit_task) {
    > + /* Set imbalance to allow misfit task to be balanced. */
    > + env->balance_type = migrate_misfit;
    > + env->imbalance = busiest->group_misfit_task_load;

    AFAICT we don't ever use this value, other than setting it to 0 in
    detach_tasks(), so what we actually set it to doesn't matter (as long as
    it's > 0).
    I'd re-suggest folding migrate_misfit into migrate_task, which is doable if
    we re-instore lb_env.src_grp_type (or rather, not delete it in this patch),
    though it makes some other places somewhat uglier. The good thing is that
    it actually does end up being implemented as a special kind of task
    migration, rather than being loosely related.

    Below's a diff, only compile-tested but should help show my point.
    -----8<-----
    diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
    index a8681c32445b..b0631ff2a4bd 100644
    --- a/kernel/sched/fair.c
    +++ b/kernel/sched/fair.c
    @@ -7155,7 +7155,6 @@ enum migration_type {
    migrate_task = 0,
    migrate_util,
    migrate_load,
    - migrate_misfit,
    };

    #define LBF_ALL_PINNED 0x01
    @@ -7188,6 +7187,7 @@ struct lb_env {
    unsigned int loop_max;

    enum fbq_type fbq_type;
    + enum group_type src_grp_type;
    enum migration_type balance_type;
    struct list_head tasks;
    };
    @@ -7455,6 +7455,13 @@ static int detach_tasks(struct lb_env *env)

    switch (env->balance_type) {
    case migrate_task:
    + /* Check for special kinds of tasks */
    + if (env->src_grp_type == group_misfit_task) {
    + /* This isn't the misfit task */
    + if (task_fits_capacity(p, capacity_of(env->src_cpu)))
    + goto next;
    + }
    +
    /* Migrate task */
    env->imbalance--;
    break;
    @@ -7480,20 +7487,6 @@ static int detach_tasks(struct lb_env *env)

    env->imbalance -= load;
    break;
    -
    - case migrate_misfit:
    - load = task_h_load(p);
    -
    - /*
    - * utilization of misfit task might decrease a bit
    - * since it has been recorded. Be conservative in the
    - * condition.
    - */
    - if (load < env->imbalance)
    - goto next;
    -
    - env->imbalance = 0;
    - break;
    }

    detach_task(p, env);
    @@ -8449,8 +8442,8 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s

    if (busiest->group_type == group_misfit_task) {
    /* Set imbalance to allow misfit task to be balanced. */
    - env->balance_type = migrate_misfit;
    - env->imbalance = busiest->group_misfit_task_load;
    + env->balance_type = migrate_task;
    + env->imbalance = 1;
    return;
    }

    @@ -8661,8 +8654,8 @@ static struct sched_group *find_busiest_group(struct lb_env *env)

    force_balance:
    /* Looks like there is an imbalance. Compute it */
    + env->src_grp_type = busiest->group_type;
    calculate_imbalance(env, &sds);
    -
    return env->imbalance ? sds.busiest : NULL;

    out_balanced:
    @@ -8728,7 +8721,15 @@ static struct rq *find_busiest_queue(struct lb_env *env,

    switch (env->balance_type) {
    case migrate_task:
    - if (busiest_nr < nr_running) {
    + /*
    + * For ASYM_CPUCAPACITY domains with misfit tasks we simply
    + * seek the "biggest" misfit task.
    + */
    + if (env->src_grp_type == group_misfit_task &&
    + rq->misfit_task_load > busiest_load) {
    + busiest_load = rq->misfit_task_load;
    + busiest = rq;
    + } else if (busiest_nr < nr_running) {
    busiest_nr = nr_running;
    busiest = rq;
    }
    @@ -8771,19 +8772,6 @@ static struct rq *find_busiest_queue(struct lb_env *env,
    busiest = rq;
    }
    break;
    -
    - case migrate_misfit:
    - /*
    - * For ASYM_CPUCAPACITY domains with misfit tasks we simply
    - * seek the "biggest" misfit task.
    - */
    - if (rq->misfit_task_load > busiest_load) {
    - busiest_load = rq->misfit_task_load;
    - busiest = rq;
    - }
    -
    - break;
    -
    }
    }

    @@ -8829,7 +8817,7 @@ voluntary_active_balance(struct lb_env *env)
    return 1;
    }

    - if (env->balance_type == migrate_misfit)
    + if (env->src_grp_type == group_misfit_task)
    return 1;

    return 0;
    ----->8-----

    > + return;
    > + }
    > +

    Also, I think these three busiest->group_type conditions could be turned
    into a switch case.

    > /*
    > - * Avg load of busiest sg can be less and avg load of local sg can
    > - * be greater than avg load across all sgs of sd because avg load
    > - * factors in sg capacity and sgs with smaller group_type are
    > - * skipped when updating the busiest sg:
    > + * Try to use spare capacity of local group without overloading it or
    > + * emptying busiest
    > */
    > - if (busiest->group_type != group_misfit_task &&
    > - (busiest->avg_load <= sds->avg_load ||
    > - local->avg_load >= sds->avg_load)) {
    > - env->imbalance = 0;
    > + if (local->group_type == group_has_spare) {
    > + if (busiest->group_type > group_fully_busy) {
    > + /*
    > + * If busiest is overloaded, try to fill spare
    > + * capacity. This might end up creating spare capacity
    > + * in busiest or busiest still being overloaded but
    > + * there is no simple way to directly compute the
    > + * amount of load to migrate in order to balance the
    > + * system.
    > + */
    > + env->balance_type = migrate_util;
    > + env->imbalance = max(local->group_capacity, local->group_util) -
    > + local->group_util;
    > + return;
    > + }
    > +
    > + if (busiest->group_weight == 1 || sds->prefer_sibling) {
    > + /*
    > + * When prefer sibling, evenly spread running tasks on
    > + * groups.
    > + */
    > + env->balance_type = migrate_task;
    > + env->imbalance = (busiest->sum_h_nr_running - local->sum_h_nr_running) >> 1;
    > + return;
    > + }
    > +
    > + /*
    > + * If there is no overload, we just want to even the number of
    > + * idle cpus.
    > + */
    > + env->balance_type = migrate_task;
    > + env->imbalance = max_t(long, 0, (local->idle_cpus - busiest->idle_cpus) >> 1);
    > return;
    > }
    >
    > /*
    > - * If there aren't any idle CPUs, avoid creating some.
    > + * Local is fully busy but have to take more load to relieve the
    > + * busiest group
    > */
    > - if (busiest->group_type == group_overloaded &&
    > - local->group_type == group_overloaded) {
    > - load_above_capacity = busiest->sum_h_nr_running * SCHED_CAPACITY_SCALE;
    > - if (load_above_capacity > busiest->group_capacity) {
    > - load_above_capacity -= busiest->group_capacity;
    > - load_above_capacity *= scale_load_down(NICE_0_LOAD);
    > - load_above_capacity /= busiest->group_capacity;
    > - } else
    > - load_above_capacity = ~0UL;
    > + if (local->group_type < group_overloaded) {
    > + /*
    > + * Local will become overvloaded so the avg_load metrics are
    ^^^^^^^^^^^
    s/overvloaded/overloaded/

    > + * finally needed
    > + */
    > +
    > + local->avg_load = (local->group_load * SCHED_CAPACITY_SCALE) /
    > + local->group_capacity;
    > +
    > + sds->avg_load = (sds->total_load * SCHED_CAPACITY_SCALE) /
    > + sds->total_capacity;
    > }
    >
    > /*
    > - * We're trying to get all the CPUs to the average_load, so we don't
    > - * want to push ourselves above the average load, nor do we wish to
    > - * reduce the max loaded CPU below the average load. At the same time,
    > - * we also don't want to reduce the group load below the group
    > - * capacity. Thus we look for the minimum possible imbalance.
    > + * Both group are or will become overloaded and we're trying to get
    > + * all the CPUs to the average_load, so we don't want to push
    > + * ourselves above the average load, nor do we wish to reduce the
    > + * max loaded CPU below the average load. At the same time, we also
    > + * don't want to reduce the group load below the group capacity.
    > + * Thus we look for the minimum possible imbalance.
    > */
    > - max_pull = min(busiest->avg_load - sds->avg_load, load_above_capacity);
    > -
    > - /* How much load to actually move to equalise the imbalance */
    > + env->balance_type = migrate_load;
    > env->imbalance = min(
    > - max_pull * busiest->group_capacity,
    > + (busiest->avg_load - sds->avg_load) * busiest->group_capacity,
    > (sds->avg_load - local->avg_load) * local->group_capacity
    > ) / SCHED_CAPACITY_SCALE;
    > -
    > - /* Boost imbalance to allow misfit task to be balanced. */
    > - if (busiest->group_type == group_misfit_task) {
    > - env->imbalance = max_t(long, env->imbalance,
    > - busiest->group_misfit_task_load);
    > - }
    > -
    > }
    >
    > /******* find_busiest_group() helpers end here *********************/
    >
    > +/*
    > + * Decision matrix according to the local and busiest group state
    > + *
    > + * busiest \ local has_spare fully_busy misfit asym imbalanced overloaded
    > + * has_spare nr_idle balanced N/A N/A balanced balanced
    > + * fully_busy nr_idle nr_idle N/A N/A balanced balanced
    > + * misfit_task force N/A N/A N/A force force
    > + * asym_capacity force force N/A N/A force force
    > + * imbalanced force force N/A N/A force force
    > + * overloaded force force N/A N/A force avg_load
    > + *
    > + * N/A : Not Applicable because already filtered while updating
    > + * statistics.
    > + * balanced : The system is balanced for these 2 groups.
    > + * force : Calculate the imbalance as load migration is probably needed.
    > + * avg_load : Only if imbalance is significant enough.
    > + * nr_idle : dst_cpu is not busy and the number of idle cpus is quite
    > + * different in groups.
    > + */
    > +
    > /**
    > * find_busiest_group - Returns the busiest group within the sched_domain
    > * if there is an imbalance.

    [...]
    > @@ -8459,59 +8602,71 @@ static struct sched_group *find_busiest_group(struct lb_env *env)
    > goto force_balance;
    >

    As for their counterpart in calculate_imbalance(), maybe go for a switch?

    Also, it would be nice if the ordering of these matched the one in
    calculate_imbalance() - right now it's the exact reverse order.

    Finally, would it hurt much to just move the balance_type and imbalance
    computation for these group types here? It breaks the nice partitions
    you've set up between find_busiest_group() and calculate_imbalance(),
    but it leads to less redirections for what in the end is just a simple
    condition.

    > /*
    > - * When dst_cpu is idle, prevent SMP nice and/or asymmetric group
    > - * capacities from resulting in underutilization due to avg_load.
    > - */
    > - if (env->idle != CPU_NOT_IDLE && group_has_capacity(env, local) &&
    > - busiest->group_no_capacity)
    > - goto force_balance;
    > -
    > - /* Misfit tasks should be dealt with regardless of the avg load */
    > - if (busiest->group_type == group_misfit_task)
    > - goto force_balance;
    > -
    > - /*
    > * If the local group is busier than the selected busiest group
    > * don't try and pull any tasks.
    > */
    > - if (local->avg_load >= busiest->avg_load)
    > + if (local->group_type > busiest->group_type)
    > goto out_balanced;
    >
    > /*
    > - * Don't pull any tasks if this group is already above the domain
    > - * average load.
    > + * When groups are overloaded, use the avg_load to ensure fairness
    > + * between tasks.
    > */
    > - if (local->avg_load >= sds.avg_load)
    > - goto out_balanced;
    > + if (local->group_type == group_overloaded) {
    > + /*
    > + * If the local group is more loaded than the selected
    > + * busiest group don't try and pull any tasks.
    > + */
    > + if (local->avg_load >= busiest->avg_load)
    > + goto out_balanced;
    > +
    > + /* XXX broken for overlapping NUMA groups */
    > + sds.avg_load = (sds.total_load * SCHED_CAPACITY_SCALE) /
    > + sds.total_capacity;
    >
    > - if (env->idle == CPU_IDLE) {
    > /*
    > - * This CPU is idle. If the busiest group is not overloaded
    > - * and there is no imbalance between this and busiest group
    > - * wrt idle CPUs, it is balanced. The imbalance becomes
    > - * significant if the diff is greater than 1 otherwise we
    > - * might end up to just move the imbalance on another group
    > + * Don't pull any tasks if this group is already above the
    > + * domain average load.
    > */
    > - if ((busiest->group_type != group_overloaded) &&
    > - (local->idle_cpus <= (busiest->idle_cpus + 1)))
    > + if (local->avg_load >= sds.avg_load)
    > goto out_balanced;
    > - } else {
    > +
    > /*
    > - * In the CPU_NEWLY_IDLE, CPU_NOT_IDLE cases, use
    > - * imbalance_pct to be conservative.
    > + * If the busiest group is more loaded, use imbalance_pct to be
    > + * conservative.
    > */
    > if (100 * busiest->avg_load <=
    > env->sd->imbalance_pct * local->avg_load)
    > goto out_balanced;
    > +
    > }
    >
    > + /* Try to move all excess tasks to child's sibling domain */
    > + if (sds.prefer_sibling && local->group_type == group_has_spare &&
    > + busiest->sum_h_nr_running > local->sum_h_nr_running + 1)
    > + goto force_balance;
    > +
    > + if (busiest->group_type != group_overloaded &&
    > + (env->idle == CPU_NOT_IDLE ||

    Disregarding the idle_cpus count, we never balance load when the busiest
    is < group_misfit_task and we're CPU_NOT_IDLE.

    I *think* that's okay, since AFAICT that should mean

    (local) nr_running < group_weight
    (busiest) nr_running <= group_weight
    (or that weird == case)

    and if we (local) are not idle then we shouldn't pull anything. Bleh, guess
    it made me scratch my head for nothing.

    > + local->idle_cpus <= (busiest->idle_cpus + 1)))
    > + /*
    > + * If the busiest group is not overloaded
    > + * and there is no imbalance between this and busiest group
    > + * wrt idle CPUs, it is balanced. The imbalance
    > + * becomes significant if the diff is greater than 1 otherwise
    > + * we might end up to just move the imbalance on another
    > + * group.
    > + */
    > + goto out_balanced;
    > +
    > force_balance:
    > /* Looks like there is an imbalance. Compute it */
    > - env->src_grp_type = busiest->group_type;
    > calculate_imbalance(env, &sds);
    > +
    > return env->imbalance ? sds.busiest : NULL;
    >
    > out_balanced:
    > +
    > env->imbalance = 0;
    > return NULL;
    > }

    [...]
    > @@ -8765,7 +8942,7 @@ static int load_balance(int this_cpu, struct rq *this_rq,
    > env.src_rq = busiest;
    >
    > ld_moved = 0;
    > - if (busiest->cfs.h_nr_running > 1) {
    > + if (busiest->nr_running > 1) {

    Shouldn't that stay h_nr_running ? We can't do much if those aren't CFS
    tasks.

    > /*
    > * Attempt to move tasks. If find_busiest_group has found
    > * an imbalance but busiest->nr_running <= 1, the group is
    >

    \
     
     \ /
      Last update: 2019-08-06 19:19    [W:4.467 / U:0.100 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site