| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Date: Mon, 03 Nov 2014 15:01:38 +0800
From: Wanpeng Li <kernellwp@...il.com>
To: Vincent Guittot <vincent.guittot@...aro.org>, peterz@...radead.org,
mingo@...nel.org, linux-kernel@...r.kernel.org,
preeti@...ux.vnet.ibm.com, Morten.Rasmussen@....com,
kamalesh@...ux.vnet.ibm.com, linux@....linux.org.uk,
linux-arm-kernel@...ts.infradead.org
CC: riel@...hat.com, efault@....de, nicolas.pitre@...aro.org,
linaro-kernel@...ts.linaro.org
Subject: Re: [PATCH v8 07/10] sched: replace capacity_factor by usage
Hi Vincent,
On 14/10/31 下午4:47, Vincent Guittot wrote:
> The scheduler tries to compute how many tasks a group of CPUs can handle by
> assuming that a task's load is SCHED_LOAD_SCALE and a CPU's capacity is
> SCHED_CAPACITY_SCALE. group_capacity_factor divides the capacity of the group
> by SCHED_LOAD_SCALE to estimate how many task can run in the group. Then, it
> compares this value with the sum of nr_running to decide if the group is
> overloaded or not. But the group_capacity_factor is hardly working for SMT
> system, it sometimes works for big cores but fails to do the right thing for
> little cores.
>
> Below are two examples to illustrate the problem that this patch solves:
>
> 1- If the original capacity of a CPU is less than SCHED_CAPACITY_SCALE
> (640 as an example), a group of 3 CPUS will have a max capacity_factor of 2
> (div_round_closest(3x640/1024) = 2) which means that it will be seen as
> overloaded even if we have only one task per CPU.
>
> 2 - If the original capacity of a CPU is greater than SCHED_CAPACITY_SCALE
> (1512 as an example), a group of 4 CPUs will have a capacity_factor of 4
> (at max and thanks to the fix [0] for SMT system that prevent the apparition
What's the story of 'fix [0] for SMT system' here?
Regards,
Wanpeng Li
> of ghost CPUs) but if one CPU is fully used by rt tasks (and its capacity is
> reduced to nearly nothing), the capacity factor of the group will still be 4
> (div_round_closest(3*1512/1024) = 5 which is cap to 4 with [0]).
>
> So, this patch tries to solve this issue by removing capacity_factor and
> replacing it with the 2 following metrics :
> -The available CPU's capacity for CFS tasks which is already used by
> load_balance.
> -The usage of the CPU by the CFS tasks. For the latter, utilization_avg_contrib
> has been re-introduced to compute the usage of a CPU by CFS tasks.
>
> group_capacity_factor and group_has_free_capacity has been removed and replaced
> by group_no_capacity. We compare the number of task with the number of CPUs and
> we evaluate the level of utilization of the CPUs to define if a group is
> overloaded or if a group has capacity to handle more tasks.
>
> For SD_PREFER_SIBLING, a group is tagged overloaded if it has more than 1 task
> so it will be selected in priority (among the overloaded groups). Since [1],
> SD_PREFER_SIBLING is no more concerned by the computation of load_above_capacity
> because local is not overloaded.
>
> Finally, the sched_group->sched_group_capacity->capacity_orig has been removed
> because it's no more used during load balance.
>
> [1] https://lkml.org/lkml/2014/8/12/295
>
> Signed-off-by: Vincent Guittot <vincent.guittot@...aro.org>
> ---
> kernel/sched/core.c | 12 -----
> kernel/sched/fair.c | 150 +++++++++++++++++++++++----------------------------
> kernel/sched/sched.h | 2 +-
> 3 files changed, 69 insertions(+), 95 deletions(-)
>
> diff --git a/kernel/sched/core.c b/kernel/sched/core.c
> index 45ae52d..37fb92c 100644
> --- a/kernel/sched/core.c
> +++ b/kernel/sched/core.c
> @@ -5373,17 +5373,6 @@ static int sched_domain_debug_one(struct sched_domain *sd, int cpu, int level,
> break;
> }
>
> - /*
> - * Even though we initialize ->capacity to something semi-sane,
> - * we leave capacity_orig unset. This allows us to detect if
> - * domain iteration is still funny without causing /0 traps.
> - */
> - if (!group->sgc->capacity_orig) {
> - printk(KERN_CONT "\n");
> - printk(KERN_ERR "ERROR: domain->cpu_capacity not set\n");
> - break;
> - }
> -
> if (!cpumask_weight(sched_group_cpus(group))) {
> printk(KERN_CONT "\n");
> printk(KERN_ERR "ERROR: empty group\n");
> @@ -5868,7 +5857,6 @@ build_overlap_sched_groups(struct sched_domain *sd, int cpu)
> * die on a /0 trap.
> */
> sg->sgc->capacity = SCHED_CAPACITY_SCALE * cpumask_weight(sg_span);
> - sg->sgc->capacity_orig = sg->sgc->capacity;
>
> /*
> * Make sure the first group of this domain contains the
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index 7ca5656..c04f2b2 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -5710,11 +5710,10 @@ struct sg_lb_stats {
> unsigned long group_capacity;
> unsigned long group_usage; /* Total usage of the group */
> unsigned int sum_nr_running; /* Nr tasks running in the group */
> - unsigned int group_capacity_factor;
> unsigned int idle_cpus;
> unsigned int group_weight;
> enum group_type group_type;
> - int group_has_free_capacity;
> + int group_no_capacity;
> #ifdef CONFIG_NUMA_BALANCING
> unsigned int nr_numa_running;
> unsigned int nr_preferred_running;
> @@ -5855,7 +5854,6 @@ static void update_cpu_capacity(struct sched_domain *sd, int cpu)
> capacity >>= SCHED_CAPACITY_SHIFT;
>
> cpu_rq(cpu)->cpu_capacity_orig = capacity;
> - sdg->sgc->capacity_orig = capacity;
>
> capacity *= scale_rt_capacity(cpu);
> capacity >>= SCHED_CAPACITY_SHIFT;
> @@ -5871,7 +5869,7 @@ void update_group_capacity(struct sched_domain *sd, int cpu)
> {
> struct sched_domain *child = sd->child;
> struct sched_group *group, *sdg = sd->groups;
> - unsigned long capacity, capacity_orig;
> + unsigned long capacity;
> unsigned long interval;
>
> interval = msecs_to_jiffies(sd->balance_interval);
> @@ -5883,7 +5881,7 @@ void update_group_capacity(struct sched_domain *sd, int cpu)
> return;
> }
>
> - capacity_orig = capacity = 0;
> + capacity = 0;
>
> if (child->flags & SD_OVERLAP) {
> /*
> @@ -5903,19 +5901,15 @@ void update_group_capacity(struct sched_domain *sd, int cpu)
> * Use capacity_of(), which is set irrespective of domains
> * in update_cpu_capacity().
> *
> - * This avoids capacity/capacity_orig from being 0 and
> + * This avoids capacity from being 0 and
> * causing divide-by-zero issues on boot.
> - *
> - * Runtime updates will correct capacity_orig.
> */
> if (unlikely(!rq->sd)) {
> - capacity_orig += capacity_orig_of(cpu);
> capacity += capacity_of(cpu);
> continue;
> }
>
> sgc = rq->sd->groups->sgc;
> - capacity_orig += sgc->capacity_orig;
> capacity += sgc->capacity;
> }
> } else {
> @@ -5926,42 +5920,15 @@ void update_group_capacity(struct sched_domain *sd, int cpu)
>
> group = child->groups;
> do {
> - capacity_orig += group->sgc->capacity_orig;
> capacity += group->sgc->capacity;
> group = group->next;
> } while (group != child->groups);
> }
>
> - sdg->sgc->capacity_orig = capacity_orig;
> sdg->sgc->capacity = capacity;
> }
>
> /*
> - * Try and fix up capacity for tiny siblings, this is needed when
> - * things like SD_ASYM_PACKING need f_b_g to select another sibling
> - * which on its own isn't powerful enough.
> - *
> - * See update_sd_pick_busiest() and check_asym_packing().
> - */
> -static inline int
> -fix_small_capacity(struct sched_domain *sd, struct sched_group *group)
> -{
> - /*
> - * Only siblings can have significantly less than SCHED_CAPACITY_SCALE
> - */
> - if (!(sd->flags & SD_SHARE_CPUCAPACITY))
> - return 0;
> -
> - /*
> - * If ~90% of the cpu_capacity is still there, we're good.
> - */
> - if (group->sgc->capacity * 32 > group->sgc->capacity_orig * 29)
> - return 1;
> -
> - return 0;
> -}
> -
> -/*
> * Check whether the capacity of the rq has been noticeably reduced by side
> * activity. The imbalance_pct is used for the threshold.
> * Return true is the capacity is reduced
> @@ -6008,37 +5975,54 @@ static inline int sg_imbalanced(struct sched_group *group)
> }
>
> /*
> - * Compute the group capacity factor.
> - *
> - * Avoid the issue where N*frac(smt_capacity) >= 1 creates 'phantom' cores by
> - * first dividing out the smt factor and computing the actual number of cores
> - * and limit unit capacity with that.
> + * group_has_capacity returns true if the group has spare capacity that could
> + * be used by some tasks. We consider that a group has spare capacity if the
> + * number of task is smaller than the number of CPUs or if the usage is lower
> + * than the available capacity for CFS tasks. For the latter, we use a
> + * threshold to stabilize the state, to take into account the variance of the
> + * tasks' load and to return true if the available capacity in meaningful for
> + * the load balancer. As an example, an available capacity of 1% can appear
> + * but it doesn't make any benefit for the load balance.
> */
> -static inline int sg_capacity_factor(struct lb_env *env, struct sched_group *group)
> +static inline bool
> +group_has_capacity(struct lb_env *env, struct sg_lb_stats *sgs)
> {
> - unsigned int capacity_factor, smt, cpus;
> - unsigned int capacity, capacity_orig;
> + if ((sgs->group_capacity * 100) >
> + (sgs->group_usage * env->sd->imbalance_pct))
> + return true;
>
> - capacity = group->sgc->capacity;
> - capacity_orig = group->sgc->capacity_orig;
> - cpus = group->group_weight;
> + if (sgs->sum_nr_running < sgs->group_weight)
> + return true;
>
> - /* smt := ceil(cpus / capacity), assumes: 1 < smt_capacity < 2 */
> - smt = DIV_ROUND_UP(SCHED_CAPACITY_SCALE * cpus, capacity_orig);
> - capacity_factor = cpus / smt; /* cores */
> + return false;
> +}
>
> - capacity_factor = min_t(unsigned,
> - capacity_factor, DIV_ROUND_CLOSEST(capacity, SCHED_CAPACITY_SCALE));
> - if (!capacity_factor)
> - capacity_factor = fix_small_capacity(env->sd, group);
> +/*
> + * group_is_overloaded returns true if the group has more tasks than it can
> + * handle. We consider that a group is overloaded if the number of tasks is
> + * greater than the number of CPUs and the tasks already use all available
> + * capacity for CFS tasks. For the latter, we use a threshold to stabilize
> + * the state, to take into account the variance of tasks' load and to return
> + * true if available capacity is no more meaningful for load balancer
> + */
> +static inline bool
> +group_is_overloaded(struct lb_env *env, struct sg_lb_stats *sgs)
> +{
> + if (sgs->sum_nr_running <= sgs->group_weight)
> + return false;
> +
> + if ((sgs->group_capacity * 100) <
> + (sgs->group_usage * env->sd->imbalance_pct))
> + return true;
>
> - return capacity_factor;
> + return false;
> }
>
> -static enum group_type
> -group_classify(struct sched_group *group, struct sg_lb_stats *sgs)
> +static enum group_type group_classify(struct lb_env *env,
> + struct sched_group *group,
> + struct sg_lb_stats *sgs)
> {
> - if (sgs->sum_nr_running > sgs->group_capacity_factor)
> + if (sgs->group_no_capacity)
> return group_overloaded;
>
> if (sg_imbalanced(group))
> @@ -6099,11 +6083,9 @@ static inline void update_sg_lb_stats(struct lb_env *env,
> sgs->load_per_task = sgs->sum_weighted_load / sgs->sum_nr_running;
>
> sgs->group_weight = group->group_weight;
> - sgs->group_capacity_factor = sg_capacity_factor(env, group);
> - sgs->group_type = group_classify(group, sgs);
>
> - if (sgs->group_capacity_factor > sgs->sum_nr_running)
> - sgs->group_has_free_capacity = 1;
> + sgs->group_no_capacity = group_is_overloaded(env, sgs);
> + sgs->group_type = group_classify(env, group, sgs);
> }
>
> /**
> @@ -6225,17 +6207,20 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd
>
> /*
> * In case the child domain prefers tasks go to siblings
> - * first, lower the sg capacity factor to one so that we'll try
> + * first, lower the sg capacity so that we'll try
> * and move all the excess tasks away. We lower the capacity
> * of a group only if the local group has the capacity to fit
> - * these excess tasks, i.e. nr_running < group_capacity_factor. The
> - * extra check prevents the case where you always pull from the
> - * heaviest group when it is already under-utilized (possible
> - * with a large weight task outweighs the tasks on the system).
> + * these excess tasks. The extra check prevents the case where
> + * you always pull from the heaviest group when it is already
> + * under-utilized (possible with a large weight task outweighs
> + * the tasks on the system).
> */
> if (prefer_sibling && sds->local &&
> - sds->local_stat.group_has_free_capacity)
> - sgs->group_capacity_factor = min(sgs->group_capacity_factor, 1U);
> + group_has_capacity(env, &sds->local_stat) &&
> + (sgs->sum_nr_running > 1)) {
> + sgs->group_no_capacity = 1;
> + sgs->group_type = group_overloaded;
> + }
>
> if (update_sd_pick_busiest(env, sds, sg, sgs)) {
> sds->busiest = sg;
> @@ -6414,11 +6399,12 @@ static inline void calculate_imbalance(struct lb_env *env, struct sd_lb_stats *s
> */
> if (busiest->group_type == group_overloaded &&
> local->group_type == group_overloaded) {
> - load_above_capacity =
> - (busiest->sum_nr_running - busiest->group_capacity_factor);
> -
> - load_above_capacity *= (SCHED_LOAD_SCALE * SCHED_CAPACITY_SCALE);
> - load_above_capacity /= busiest->group_capacity;
> + load_above_capacity = busiest->sum_nr_running *
> + SCHED_LOAD_SCALE;
> + if (load_above_capacity > busiest->group_capacity)
> + load_above_capacity -= busiest->group_capacity;
> + else
> + load_above_capacity = ~0UL;
> }
>
> /*
> @@ -6481,6 +6467,7 @@ static struct sched_group *find_busiest_group(struct lb_env *env)
> local = &sds.local_stat;
> busiest = &sds.busiest_stat;
>
> + /* ASYM feature bypasses nice load balance check */
> if ((env->idle == CPU_IDLE || env->idle == CPU_NEWLY_IDLE) &&
> check_asym_packing(env, &sds))
> return sds.busiest;
> @@ -6501,8 +6488,8 @@ static struct sched_group *find_busiest_group(struct lb_env *env)
> goto force_balance;
>
> /* SD_BALANCE_NEWIDLE trumps SMP nice when underutilized */
> - if (env->idle == CPU_NEWLY_IDLE && local->group_has_free_capacity &&
> - !busiest->group_has_free_capacity)
> + if (env->idle == CPU_NEWLY_IDLE && group_has_capacity(env, local) &&
> + busiest->group_no_capacity)
> goto force_balance;
>
> /*
> @@ -6561,7 +6548,7 @@ static struct rq *find_busiest_queue(struct lb_env *env,
> int i;
>
> for_each_cpu_and(i, sched_group_cpus(group), env->cpus) {
> - unsigned long capacity, capacity_factor, wl;
> + unsigned long capacity, wl;
> enum fbq_type rt;
>
> rq = cpu_rq(i);
> @@ -6590,9 +6577,6 @@ static struct rq *find_busiest_queue(struct lb_env *env,
> continue;
>
> capacity = capacity_of(i);
> - capacity_factor = DIV_ROUND_CLOSEST(capacity, SCHED_CAPACITY_SCALE);
> - if (!capacity_factor)
> - capacity_factor = fix_small_capacity(env->sd, group);
>
> wl = weighted_cpuload(i);
>
> @@ -6600,7 +6584,9 @@ static struct rq *find_busiest_queue(struct lb_env *env,
> * When comparing with imbalance, use weighted_cpuload()
> * which is not scaled with the cpu capacity.
> */
> - if (capacity_factor && rq->nr_running == 1 && wl > env->imbalance)
> +
> + if (rq->nr_running == 1 && wl > env->imbalance &&
> + !check_cpu_capacity(rq, env->sd))
> continue;
>
> /*
> diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h
> index 35eca7d..7963981 100644
> --- a/kernel/sched/sched.h
> +++ b/kernel/sched/sched.h
> @@ -759,7 +759,7 @@ struct sched_group_capacity {
> * CPU capacity of this group, SCHED_LOAD_SCALE being max capacity
> * for a single CPU.
> */
> - unsigned int capacity, capacity_orig;
> + unsigned int capacity;
> unsigned long next_update;
> int imbalance; /* XXX unrelated to capacity but shared group state */
> /*
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Powered by blists - more mailing lists