Hi Vincent,

On 08/26/2014 04:36 PM, Vincent Guittot wrote:

The computation of avg_load and avg_load_per_task should only takes into account the number of cfs tasks. The non cfs task are already taken into account by decreasing the cpu's capacity and they will be tracked in the CPU's utilization (group_utilization) of the next patches

Signed-off-by: Vincent Guittot vincent.guittot@linaro.org

kernel/sched/fair.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 87b9dc7..b85e9f7 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -4092,7 +4092,7 @@ static unsigned long capacity_of(int cpu) static unsigned long cpu_avg_load_per_task(int cpu) { struct rq *rq = cpu_rq(cpu);

• unsigned long nr_running = ACCESS_ONCE(rq->nr_running);

• unsigned long nr_running = ACCESS_ONCE(rq->cfs.h_nr_running); unsigned long load_avg = rq->cfs.runnable_load_avg;

  if (nr_running)

@@ -5985,7 +5985,7 @@ static inline void update_sg_lb_stats(struct lb_env *env, load = source_load(i, load_idx);

sgs->group_load += load;

• sgs->sum_nr_running += rq->nr_running;
  

• sgs->sum_nr_running += rq->cfs.h_nr_running;
  
  

  if (rq->nr_running > 1) *overload = true;

Why do we probe rq->nr_running while we do load balancing? Should not we be probing cfs_rq->nr_running instead? We are interested after all in load balancing fair tasks right? The reason I ask this is, I was wondering if we need to make the above similar change in more places in load balancing.

To cite examples: The above check says a cpu is overloaded when rq->nr_running > 1. However if these tasks happen to be rt tasks, we would anyway not be able to load balance. So while I was looking through this patch, I noticed this and wanted to cross verify if we are checking rq->nr_running on purpose in some places in load balancing; another example being in nohz_kick_needed().

Regards Preeti U Murthy

On Wed, 2014-09-03 at 13:09 +0200, Vincent Guittot wrote:

On 30 August 2014 14:00, Preeti U Murthy preeti@linux.vnet.ibm.com wrote:

...

Hi Vincent,

On 08/26/2014 04:36 PM, Vincent Guittot wrote:

...

The computation of avg_load and avg_load_per_task should only takes into account the number of cfs tasks. The non cfs task are already taken into account by decreasing the cpu's capacity and they will be tracked in the CPU's utilization (group_utilization) of the next patches

Signed-off-by: Vincent Guittot vincent.guittot@linaro.org

kernel/sched/fair.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 87b9dc7..b85e9f7 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -4092,7 +4092,7 @@ static unsigned long capacity_of(int cpu) static unsigned long cpu_avg_load_per_task(int cpu) { struct rq *rq = cpu_rq(cpu);

• unsigned long nr_running = ACCESS_ONCE(rq->nr_running);
  

• unsigned long nr_running = ACCESS_ONCE(rq->cfs.h_nr_running);
  unsigned long load_avg = rq->cfs.runnable_load_avg;
  
  if (nr_running)
  

@@ -5985,7 +5985,7 @@ static inline void update_sg_lb_stats(struct lb_env *env, load = source_load(i, load_idx);

          sgs->group_load += load;

•         sgs->sum_nr_running += rq->nr_running;
  

•         sgs->sum_nr_running += rq->cfs.h_nr_running;
  
          if (rq->nr_running > 1)
                  *overload = true;
  
  

Why do we probe rq->nr_running while we do load balancing? Should not we be probing cfs_rq->nr_running instead? We are interested after all in load balancing fair tasks right? The reason I ask this is, I was wondering if we need to make the above similar change in more places in load balancing.

Hi Preeti,

Yes, we should probably the test rq->cfs.h_nr_running > 0 before setting overload.

The overload indicator is used for knowing when we can totally avoid load balancing to a cpu that is about to go idle. We can avoid load balancing when no cpu has more than 1 task. So if you have say just one fair task and multiple deadline tasks on a cpu, and another cpu about to go idle, you should turn on normal load balancing in the idle path by setting overload to true.

So setting overload should be set based on rq->nr_running and not on rq->cfs.h_nr_running.

Thanks.

Tim

On Thu, 2014-09-04 at 09:17 +0200, Vincent Guittot wrote:

On 4 September 2014 01:43, Tim Chen tim.c.chen@linux.intel.com wrote:

...

On Wed, 2014-09-03 at 13:09 +0200, Vincent Guittot wrote:

...

On 30 August 2014 14:00, Preeti U Murthy preeti@linux.vnet.ibm.com wrote:

...

Hi Vincent,

On 08/26/2014 04:36 PM, Vincent Guittot wrote:

...

The computation of avg_load and avg_load_per_task should only takes into account the number of cfs tasks. The non cfs task are already taken into account by decreasing the cpu's capacity and they will be tracked in the CPU's utilization (group_utilization) of the next patches

Signed-off-by: Vincent Guittot vincent.guittot@linaro.org

kernel/sched/fair.c | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 87b9dc7..b85e9f7 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -4092,7 +4092,7 @@ static unsigned long capacity_of(int cpu) static unsigned long cpu_avg_load_per_task(int cpu) { struct rq *rq = cpu_rq(cpu);

• unsigned long nr_running = ACCESS_ONCE(rq->nr_running);
  

• unsigned long nr_running = ACCESS_ONCE(rq->cfs.h_nr_running);
  unsigned long load_avg = rq->cfs.runnable_load_avg;
  
  if (nr_running)
  

@@ -5985,7 +5985,7 @@ static inline void update_sg_lb_stats(struct lb_env *env, load = source_load(i, load_idx);

          sgs->group_load += load;

•         sgs->sum_nr_running += rq->nr_running;
  

•         sgs->sum_nr_running += rq->cfs.h_nr_running;
  
          if (rq->nr_running > 1)
                  *overload = true;
  
  

Why do we probe rq->nr_running while we do load balancing? Should not we be probing cfs_rq->nr_running instead? We are interested after all in load balancing fair tasks right? The reason I ask this is, I was wondering if we need to make the above similar change in more places in load balancing.

Hi Preeti,

Yes, we should probably the test rq->cfs.h_nr_running > 0 before setting overload.

The overload indicator is used for knowing when we can totally avoid load balancing to a cpu that is about to go idle. We can avoid load balancing when no cpu has more than 1 task. So if you have say just one fair task and multiple deadline tasks on a cpu, and another cpu about to go idle, you should turn on normal load balancing in the idle path by setting overload to true.

The newly idle load balancing can only affect CFS tasks so triggering a load_balance because a cpu is overloaded by rt tasks only, will not change anything.

...

So setting overload should be set based on rq->nr_running and not on rq->cfs.h_nr_running.

We should probably use both values like below

if ((rq->nr_running > 1) && ( rq->cfs.h_nr_running > 0))

Yes, this modification is the correct one that takes care of the condition I objected to previously.

Thanks.

Tim

Hi Vincent,

On 08/26/2014 04:36 PM, Vincent Guittot wrote:

capacity_orig is only changed for system with a SMT sched_domain level in order

I think I had asked this before, but why only capacity_orig? The capacity of a group is also being updated the same way. This patch fixes the capacity of a group to reflect the capacity of the heterogeneous CPUs in it, this capacity being both the full capacity of the group: capacity_orig and the capacity available for the fair tasks. So I feel in the subject as well as the changelog it would suffice to say 'capacity'.

to reflect the lower capacity of CPUs. Heterogenous system also have to reflect an original capacity that is different from the default value.

Create a more generic function arch_scale_cpu_capacity that can be also used by non SMT platform to set capacity_orig.

The weak behavior of arch_scale_cpu_capacity is the previous SMT one in order to keep backward compatibility in the use of capacity_orig.

arch_scale_smt_capacity and default_scale_smt_capacity have been removed as they were not use elsewhere than in arch_scale_cpu_capacity.

Signed-off-by: Vincent Guittot vincent.guittot@linaro.org

kernel/sched/fair.c | 25 ++++++------------------- 1 file changed, 6 insertions(+), 19 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index b85e9f7..8176bda 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -5705,19 +5705,12 @@ unsigned long __weak arch_scale_freq_capacity(struct sched_domain *sd, int cpu) return default_scale_capacity(sd, cpu); }

-static unsigned long default_scale_smt_capacity(struct sched_domain *sd, int cpu) +unsigned long __weak arch_scale_cpu_capacity(struct sched_domain *sd, int cpu) {

• unsigned long weight = sd->span_weight;
• unsigned long smt_gain = sd->smt_gain;

• if ((sd->flags & SD_SHARE_CPUCAPACITY) && (sd->span_weight > 1))

• return sd->smt_gain / sd->span_weight;
  
  

• smt_gain /= weight;
• return smt_gain;

-}

-unsigned long __weak arch_scale_smt_capacity(struct sched_domain *sd, int cpu) -{

• return default_scale_smt_capacity(sd, cpu);

• return SCHED_CAPACITY_SCALE;

}

static unsigned long scale_rt_capacity(int cpu) @@ -5756,18 +5749,12 @@ static unsigned long scale_rt_capacity(int cpu)

static void update_cpu_capacity(struct sched_domain *sd, int cpu) {

• unsigned long weight = sd->span_weight; unsigned long capacity = SCHED_CAPACITY_SCALE; struct sched_group *sdg = sd->groups;

• if ((sd->flags & SD_SHARE_CPUCAPACITY) && weight > 1) {

• if (sched_feat(ARCH_CAPACITY))
  

Aren't you missing this check above? I understand that it is not crucial, but that would also mean removing ARCH_CAPACITY sched_feat altogether, wouldn't it?

Regards Preeti U Murthy

• 	capacity *= arch_scale_smt_capacity(sd, cpu);
  

• else
  

• 	capacity *= default_scale_smt_capacity(sd, cpu);
  

• capacity *= arch_scale_cpu_capacity(sd, cpu);

• capacity >>= SCHED_CAPACITY_SHIFT;
  

• }

• capacity >>= SCHED_CAPACITY_SHIFT;

  sdg->sgc->capacity_orig = capacity;

On 10 September 2014 15:50, Peter Zijlstra peterz@infradead.org wrote:

On Sat, Aug 30, 2014 at 10:37:40PM +0530, Preeti U Murthy wrote:

...

...

• if ((sd->flags & SD_SHARE_CPUCAPACITY) && weight > 1) {

•       if (sched_feat(ARCH_CAPACITY))
  

Aren't you missing this check above? I understand that it is not crucial, but that would also mean removing ARCH_CAPACITY sched_feat altogether, wouldn't it?

Yes he's missing that, I added the below bit on top.

FWIW, your changes are fine for me

So the argument last time: lkml.kernel.org/r/20140709105721.GT19379@twins.programming.kicks-ass.net was that you cannot put sched_feat(ARCH_CAPACITY) inside a weak arch_* function. The test has to be outside, seeing how it needs to decide to call the arch function at all (or revert to the default implementation).

---

--- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -5700,7 +5700,7 @@ unsigned long __weak arch_scale_freq_cap return default_scale_capacity(sd, cpu); }

-unsigned long __weak arch_scale_cpu_capacity(struct sched_domain *sd, int cpu) +static unsigned long default_scale_cpu_capacity(struct sched_domain *sd, int cpu) { if ((sd->flags & SD_SHARE_CPUCAPACITY) && (sd->span_weight > 1)) return sd->smt_gain / sd->span_weight; @@ -5708,6 +5708,11 @@ unsigned long __weak arch_scale_cpu_capa return SCHED_CAPACITY_SCALE; }

+unsigned long __weak arch_scale_cpu_capacity(struct sched_domain *sd, int cpu) +{

•   return default_scale_cpu_capacity(sd, cpu);
  

+}

static unsigned long scale_rt_capacity(int cpu) { struct rq *rq = cpu_rq(cpu); @@ -5747,7 +5752,10 @@ static void update_cpu_capacity(struct s unsigned long capacity = SCHED_CAPACITY_SCALE; struct sched_group *sdg = sd->groups;

•   capacity *= arch_scale_cpu_capacity(sd, cpu);
  

•   if (sched_feat(ARCH_CAPACITY))
  

•           capacity *= arch_scale_cpu_capacity(sd, cpu);
  

•   else
  

•           capacity *= default_scale_cpu_capacity(sd, cpu);
  
    capacity >>= SCHED_CAPACITY_SHIFT;
  
  

On 11 September 2014 21:02, Nicolas Pitre nicolas.pitre@linaro.org wrote:

On Tue, 26 Aug 2014, Vincent Guittot wrote:

...

This new field cpu_capacity_orig reflects the available capacity of a CPUs

s/a CPUs/a CPU/

good catch

...

unlike the cpu_capacity which reflects the current capacity that can be altered by frequency and rt tasks.

Shouldn't this be described as the "highest possible capacity" instead of only "available capacity" to make it clearer? In which case, shouldn't it be called capacity_max instead of capacity_orig? With "orig" we may think "origin" as the capacity that was available at boot time or the like. If for example the CPU was booted with a low P-state then its max capacity is different from the original one.

I have use the orig suffix to be aligned with the capacity_orig which is a sum of cpu_capacity_orig. I agree that orig is standing for original in the sense that it's the original capacity befor being altered by scale_freq and scale_rt

Vincent

...

Signed-off-by: Vincent Guittot vincent.guittot@linaro.org

kernel/sched/core.c | 2 +- kernel/sched/fair.c | 1 + kernel/sched/sched.h | 1 + 3 files changed, 3 insertions(+), 1 deletion(-)

diff --git a/kernel/sched/core.c b/kernel/sched/core.c index a394f99..7c3b237 100644 --- a/kernel/sched/core.c +++ b/kernel/sched/core.c @@ -7003,7 +7003,7 @@ void __init sched_init(void) #ifdef CONFIG_SMP rq->sd = NULL; rq->rd = NULL;

•         rq->cpu_capacity = SCHED_CAPACITY_SCALE;
  

•         rq->cpu_capacity = rq->cpu_capacity_orig = SCHED_CAPACITY_SCALE;
          rq->post_schedule = 0;
          rq->active_balance = 0;
          rq->next_balance = jiffies;
  

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 8176bda..17c16cc 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -5756,6 +5756,7 @@ 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;
  
  if (sched_feat(ARCH_CAPACITY))
  

diff --git a/kernel/sched/sched.h b/kernel/sched/sched.h index aa0f73b..7c0a74e 100644 --- a/kernel/sched/sched.h +++ b/kernel/sched/sched.h @@ -575,6 +575,7 @@ struct rq { struct sched_domain *sd;

  unsigned long cpu_capacity;

• unsigned long cpu_capacity_orig;
  
  unsigned char idle_balance;
  /* For active balancing */
  

-- 1.9.1

Hi Vincent,

On 08/26/2014 04:36 PM, Vincent Guittot wrote:

If the CPU is used for handling lot of IRQs, trig a load balance to check if it's worth moving its tasks on another CPU that has more capacity.

As a sidenote, this will note generate more spurious ilb because we already trig an ilb if there is more than 1 busy cpu. If this cpu is the only one that has a task, we will trig the ilb once for migrating the task.

The nohz_kick_needed function has been cleaned up a bit while adding the new test

Signed-off-by: Vincent Guittot vincent.guittot@linaro.org

kernel/sched/fair.c | 69 +++++++++++++++++++++++++++++++++++++---------------- 1 file changed, 49 insertions(+), 20 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 18db43e..60ae1ce 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -6049,6 +6049,14 @@ static bool update_sd_pick_busiest(struct lb_env *env, return true; }

• /*

• * The group capacity is reduced probably because of activity from other
  

• * sched class or interrupts which use part of the available capacity
  

• */
  

• if ((sg->sgc->capacity_orig * 100) > (sgs->group_capacity *

• 		env->sd->imbalance_pct))
  

Wouldn't the check on avg_load let us know if we are packing more tasks in this group than its capacity ? Isn't that the metric we are more interested in?

• return true;
  

• return false;

}

@@ -6534,13 +6542,23 @@ static int need_active_balance(struct lb_env *env) struct sched_domain *sd = env->sd;

if (env->idle == CPU_NEWLY_IDLE) {

• int src_cpu = env->src_cpu;
  
  

  /*

  • ASYM_PACKING needs to force migrate tasks from busy but
  • higher numbered CPUs in order to pack all tasks in the
  • lowest numbered CPUs.

  */

• if ((sd->flags & SD_ASYM_PACKING) && env->src_cpu > env->dst_cpu)
  

• if ((sd->flags & SD_ASYM_PACKING) && src_cpu > env->dst_cpu)
  

• 	return 1;
  

• /*
  

•  * If the CPUs share their cache and the src_cpu's capacity is
  

•  * reduced because of other sched_class or IRQs, we trig an
  

•  * active balance to move the task
  

•  */
  

• if ((capacity_orig_of(src_cpu) * 100) > (capacity_of(src_cpu) *
  

• 		sd->imbalance_pct))
  return 1;
  

  }

@@ -6643,6 +6661,8 @@ static int load_balance(int this_cpu, struct rq *this_rq,

schedstat_add(sd, lb_imbalance[idle], env.imbalance);

• env.src_cpu = busiest->cpu;
• ld_moved = 0; if (busiest->nr_running > 1) { /*

@@ -6652,7 +6672,6 @@ static int load_balance(int this_cpu, struct rq *this_rq, * correctly treated as an imbalance. */ env.flags |= LBF_ALL_PINNED;

• env.src_cpu   = busiest->cpu;
  

  env.src_rq = busiest; env.loop_max = min(sysctl_sched_nr_migrate, busiest->nr_running);

@@ -7359,10 +7378,12 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)

/*

• Current heuristic for kicking the idle load balancer in the presence

• • of an idle cpu is the system.

• • of an idle cpu in the system.
  • • This rq has more than one task.

• • • At any scheduler domain level, this cpu's scheduler group has multiple

• • busy cpu's exceeding the group's capacity.
    

• • • This rq has at least one CFS task and the capacity of the CPU is

• • significantly reduced because of RT tasks or IRQs.
    

• • • At parent of LLC scheduler domain level, this cpu's scheduler group has

• • multiple busy cpu.
    

  • • For SD_ASYM_PACKING, if the lower numbered cpu's in the scheduler

  • domain span are idle.
    

  */

@@ -7372,9 +7393,10 @@ static inline int nohz_kick_needed(struct rq *rq) struct sched_domain *sd; struct sched_group_capacity *sgc; int nr_busy, cpu = rq->cpu;

• bool kick = false;

  if (unlikely(rq->idle_balance))

• return 0;
  

• return false;
  
  

  /*

  • We may be recently in ticked or tickless idle mode. At the first

@@ -7388,38 +7410,45 @@ static inline int nohz_kick_needed(struct rq *rq) * balancing. */ if (likely(!atomic_read(&nohz.nr_cpus)))

• return 0;
  

• return false;
  
  

  if (time_before(now, nohz.next_balance))

• return 0;
  

• return false;
  
  

  if (rq->nr_running >= 2)

Will this check ^^ not catch those cases which this patch is targeting?

Regards Preeti U Murthy

• goto need_kick;
  

• return true;
  
  

  rcu_read_lock(); sd = rcu_dereference(per_cpu(sd_busy, cpu));

• if (sd) { sgc = sd->groups->sgc; nr_busy = atomic_read(&sgc->nr_busy_cpus);

• if (nr_busy > 1)
  

• 	goto need_kick_unlock;
  

• if (nr_busy > 1) {
  

• 	kick = true;
  

• 	goto unlock;
  

• }
  

• }

• sd = rcu_dereference(per_cpu(sd_asym, cpu));

• sd = rcu_dereference(rq->sd);

• if (sd) {

• if ((rq->cfs.h_nr_running >= 1) &&
  

• 		((rq->cpu_capacity * sd->imbalance_pct) <
  

• 		(rq->cpu_capacity_orig * 100))) {
  

• 	kick = true;
  

• 	goto unlock;
  

• }
  

• }

• sd = rcu_dereference(per_cpu(sd_asym, cpu)); if (sd && (cpumask_first_and(nohz.idle_cpus_mask, sched_domain_span(sd)) < cpu))

• goto need_kick_unlock;
  

• kick = true;
  
  

+unlock: rcu_read_unlock();

• return 0;

-need_kick_unlock:

• rcu_read_unlock();

-need_kick:

• return 1;

• return kick;

} #else static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle) { }

On 09/01/2014 02:15 PM, Vincent Guittot wrote:

On 30 August 2014 19:50, Preeti U Murthy preeti@linux.vnet.ibm.com wrote:

...

Hi Vincent,

...

index 18db43e..60ae1ce 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -6049,6 +6049,14 @@ static bool update_sd_pick_busiest(struct lb_env *env, return true; }

• /*
  

•  * The group capacity is reduced probably because of activity from other
  

•  * sched class or interrupts which use part of the available capacity
  

•  */
  

• if ((sg->sgc->capacity_orig * 100) > (sgs->group_capacity *
  

•                         env->sd->imbalance_pct))
  

Wouldn't the check on avg_load let us know if we are packing more tasks in this group than its capacity ? Isn't that the metric we are more interested in?

With this patch, we don't want to pack but we prefer to spread the task on another CPU than the one which handles the interruption if latter uses a significant part of the CPU capacity.

...

...

•         return true;
  

• return false;
  

}

@@ -6534,13 +6542,23 @@ static int need_active_balance(struct lb_env *env) struct sched_domain *sd = env->sd;

  if (env->idle == CPU_NEWLY_IDLE) {

•         int src_cpu = env->src_cpu;
  
          /*
           * ASYM_PACKING needs to force migrate tasks from busy but
           * higher numbered CPUs in order to pack all tasks in the
           * lowest numbered CPUs.
           */
  

•         if ((sd->flags & SD_ASYM_PACKING) && env->src_cpu > env->dst_cpu)
  

•         if ((sd->flags & SD_ASYM_PACKING) && src_cpu > env->dst_cpu)
  

•                 return 1;
  

•         /*
  

•          * If the CPUs share their cache and the src_cpu's capacity is
  

•          * reduced because of other sched_class or IRQs, we trig an
  

•          * active balance to move the task
  

•          */
  

•         if ((capacity_orig_of(src_cpu) * 100) > (capacity_of(src_cpu) *
  

•                         sd->imbalance_pct))
                  return 1;
  }
  
  

@@ -6643,6 +6661,8 @@ static int load_balance(int this_cpu, struct rq *this_rq,

  schedstat_add(sd, lb_imbalance[idle], env.imbalance);

• env.src_cpu = busiest->cpu;
  

• ld_moved = 0;
  if (busiest->nr_running > 1) {
          /*
  

@@ -6652,7 +6672,6 @@ static int load_balance(int this_cpu, struct rq *this_rq, * correctly treated as an imbalance. */ env.flags |= LBF_ALL_PINNED;

•         env.src_cpu   = busiest->cpu;
          env.src_rq    = busiest;
          env.loop_max  = min(sysctl_sched_nr_migrate, busiest->nr_running);
  
  

@@ -7359,10 +7378,12 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)

/*

• Current heuristic for kicking the idle load balancer in the presence

• • of an idle cpu is the system.

• • of an idle cpu in the system.
  • • This rq has more than one task.

• • • At any scheduler domain level, this cpu's scheduler group has multiple

• • busy cpu's exceeding the group's capacity.
    

• • • This rq has at least one CFS task and the capacity of the CPU is

• • significantly reduced because of RT tasks or IRQs.
    

• • • At parent of LLC scheduler domain level, this cpu's scheduler group has

• • multiple busy cpu.
    

  • • For SD_ASYM_PACKING, if the lower numbered cpu's in the scheduler

  • domain span are idle.
    

  */

@@ -7372,9 +7393,10 @@ static inline int nohz_kick_needed(struct rq *rq) struct sched_domain *sd; struct sched_group_capacity *sgc; int nr_busy, cpu = rq->cpu;

• bool kick = false;
  
  if (unlikely(rq->idle_balance))
  

•         return 0;
  

•         return false;
  
    /*
  * We may be recently in ticked or tickless idle mode. At the first
  

@@ -7388,38 +7410,45 @@ static inline int nohz_kick_needed(struct rq *rq) * balancing. */ if (likely(!atomic_read(&nohz.nr_cpus)))

•         return 0;
  

•         return false;
  
  if (time_before(now, nohz.next_balance))
  

•         return 0;
  

•         return false;
  
  if (rq->nr_running >= 2)
  

Will this check ^^ not catch those cases which this patch is targeting?

This patch is not about how many tasks are running but if the capacity of the CPU is reduced because of side activity like interruptions which are only visible in the capacity value (with IRQ_TIME_ACCOUNTING config) but not in nr_running. Even if the capacity is reduced because of RT tasks, nothing ensures that the RT task will be running when the tick fires

Regards, Vincent

...

Regards Preeti U Murthy

...

•         goto need_kick;
  

•         return true;
  
  rcu_read_lock();
  sd = rcu_dereference(per_cpu(sd_busy, cpu));
  

• if (sd) {
          sgc = sd->groups->sgc;
          nr_busy = atomic_read(&sgc->nr_busy_cpus);
  
  

•         if (nr_busy > 1)
  

•                 goto need_kick_unlock;
  

•         if (nr_busy > 1) {
  

•                 kick = true;
  

•                 goto unlock;
  

•         }
  

• }
  
  

• sd = rcu_dereference(per_cpu(sd_asym, cpu));
  

• sd = rcu_dereference(rq->sd);
  

• if (sd) {
  

•         if ((rq->cfs.h_nr_running >= 1) &&
  

•                         ((rq->cpu_capacity * sd->imbalance_pct) <
  

•                         (rq->cpu_capacity_orig * 100))) {
  

Ok I understand your explanation above. But I was wondering if you would need to add this check around rq->cfs.h_nr_running >= 1 in the above two cases as well.

I have actually raised this concern over whether we should be using rq->nr_running or cfs_rq->nr_running while we do load balancing in reply to your patch3. While all our load measurements are about the cfs_rq load, we use rq->nr_running, which may include tasks from other sched classes as well. We divide them to get average load per task during load balancing which is wrong, isn't it? Similarly during nohz_kick_needed(), we trigger load balancing based on rq->nr_running again.

In this patch too, even if you know that the cpu is being dominated by tasks that do not belong to cfs class, you would be triggering a futile load balance if there are no fair tasks to move.

Regards Preeti U Murthy

On 09/03/2014 05:14 PM, Vincent Guittot wrote:

On 3 September 2014 11:11, Preeti U Murthy preeti@linux.vnet.ibm.com wrote:

...

On 09/01/2014 02:15 PM, Vincent Guittot wrote:

...

On 30 August 2014 19:50, Preeti U Murthy preeti@linux.vnet.ibm.com wrote:

...

Hi Vincent,

...

index 18db43e..60ae1ce 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -6049,6 +6049,14 @@ static bool update_sd_pick_busiest(struct lb_env *env, return true; }

• /*
  

•  * The group capacity is reduced probably because of activity from other
  

•  * sched class or interrupts which use part of the available capacity
  

•  */
  

• if ((sg->sgc->capacity_orig * 100) > (sgs->group_capacity *
  

•                         env->sd->imbalance_pct))
  

Wouldn't the check on avg_load let us know if we are packing more tasks in this group than its capacity ? Isn't that the metric we are more interested in?

With this patch, we don't want to pack but we prefer to spread the task on another CPU than the one which handles the interruption if latter uses a significant part of the CPU capacity.

...

...

•         return true;
  

• return false;
  

}

@@ -6534,13 +6542,23 @@ static int need_active_balance(struct lb_env *env) struct sched_domain *sd = env->sd;

  if (env->idle == CPU_NEWLY_IDLE) {

•         int src_cpu = env->src_cpu;
  
          /*
           * ASYM_PACKING needs to force migrate tasks from busy but
           * higher numbered CPUs in order to pack all tasks in the
           * lowest numbered CPUs.
           */
  

•         if ((sd->flags & SD_ASYM_PACKING) && env->src_cpu > env->dst_cpu)
  

•         if ((sd->flags & SD_ASYM_PACKING) && src_cpu > env->dst_cpu)
  

•                 return 1;
  

•         /*
  

•          * If the CPUs share their cache and the src_cpu's capacity is
  

•          * reduced because of other sched_class or IRQs, we trig an
  

•          * active balance to move the task
  

•          */
  

•         if ((capacity_orig_of(src_cpu) * 100) > (capacity_of(src_cpu) *
  

•                         sd->imbalance_pct))
                  return 1;
  }
  
  

@@ -6643,6 +6661,8 @@ static int load_balance(int this_cpu, struct rq *this_rq,

  schedstat_add(sd, lb_imbalance[idle], env.imbalance);

• env.src_cpu = busiest->cpu;
  

• ld_moved = 0;
  if (busiest->nr_running > 1) {
          /*
  

@@ -6652,7 +6672,6 @@ static int load_balance(int this_cpu, struct rq *this_rq, * correctly treated as an imbalance. */ env.flags |= LBF_ALL_PINNED;

•         env.src_cpu   = busiest->cpu;
          env.src_rq    = busiest;
          env.loop_max  = min(sysctl_sched_nr_migrate, busiest->nr_running);
  
  

@@ -7359,10 +7378,12 @@ static void nohz_idle_balance(struct rq *this_rq, enum cpu_idle_type idle)

/*

• Current heuristic for kicking the idle load balancer in the presence

• • of an idle cpu is the system.

• • of an idle cpu in the system.
  • • This rq has more than one task.

• • • At any scheduler domain level, this cpu's scheduler group has multiple

• • busy cpu's exceeding the group's capacity.
    

• • • This rq has at least one CFS task and the capacity of the CPU is

• • significantly reduced because of RT tasks or IRQs.
    

• • • At parent of LLC scheduler domain level, this cpu's scheduler group has

• • multiple busy cpu.
    

  • • For SD_ASYM_PACKING, if the lower numbered cpu's in the scheduler

  • domain span are idle.
    

  */

@@ -7372,9 +7393,10 @@ static inline int nohz_kick_needed(struct rq *rq) struct sched_domain *sd; struct sched_group_capacity *sgc; int nr_busy, cpu = rq->cpu;

• bool kick = false;
  
  if (unlikely(rq->idle_balance))
  

•         return 0;
  

•         return false;
  
    /*
  * We may be recently in ticked or tickless idle mode. At the first
  

@@ -7388,38 +7410,45 @@ static inline int nohz_kick_needed(struct rq *rq) * balancing. */ if (likely(!atomic_read(&nohz.nr_cpus)))

•         return 0;
  

•         return false;
  
  if (time_before(now, nohz.next_balance))
  

•         return 0;
  

•         return false;
  
  if (rq->nr_running >= 2)
  

Will this check ^^ not catch those cases which this patch is targeting?

This patch is not about how many tasks are running but if the capacity of the CPU is reduced because of side activity like interruptions which are only visible in the capacity value (with IRQ_TIME_ACCOUNTING config) but not in nr_running. Even if the capacity is reduced because of RT tasks, nothing ensures that the RT task will be running when the tick fires

Regards, Vincent

...

Regards Preeti U Murthy

...

•         goto need_kick;
  

•         return true;
  
  rcu_read_lock();
  sd = rcu_dereference(per_cpu(sd_busy, cpu));
  

• if (sd) {
          sgc = sd->groups->sgc;
          nr_busy = atomic_read(&sgc->nr_busy_cpus);
  
  

•         if (nr_busy > 1)
  

•                 goto need_kick_unlock;
  

•         if (nr_busy > 1) {
  

•                 kick = true;
  

•                 goto unlock;
  

•         }
  

• }
  
  

• sd = rcu_dereference(per_cpu(sd_asym, cpu));
  

• sd = rcu_dereference(rq->sd);
  

• if (sd) {
  

•         if ((rq->cfs.h_nr_running >= 1) &&
  

•                         ((rq->cpu_capacity * sd->imbalance_pct) <
  

•                         (rq->cpu_capacity_orig * 100))) {
  

Ok I understand your explanation above. But I was wondering if you would need to add this check around rq->cfs.h_nr_running >= 1 in the above two cases as well.

yes you're right for the test if (rq->nr_running >= 2).

It's not so straight forward for nr_busy_cpus which reflects how many CPUs have not stopped their tick. The scheduler assumes that the latter are busy with cfs tasks

...

I have actually raised this concern over whether we should be using rq->nr_running or cfs_rq->nr_running while we do load balancing in reply to your patch3. While all our load measurements are about the cfs_rq

I have just replied to your comments on patch 3. Sorry for the delay

...

load, we use rq->nr_running, which may include tasks from other sched classes as well. We divide them to get average load per task during load balancing which is wrong, isn't it? Similarly during nohz_kick_needed(), we trigger load balancing based on rq->nr_running again.

In this patch too, even if you know that the cpu is being dominated by tasks that do not belong to cfs class, you would be triggering a futile load balance if there are no fair tasks to move.

This patch adds one additional condition that is based on rq->cfs.h_nr_running so it should not trigger any futile load balance. Then, I have also take advantage of this patch to clean up nohz_kick_needed as proposed by Peter but the conditions are the same than previously (except the one with rq->cfs.h_nr_running)

I can prepare another patchset that will solve the concerns that you raised for nohz_kick_needed and in patch 3 but i would prefer not include them in this patchset which is large enough and which subject is a bit different. Does it seem ok for you ?

Sure Vincent, thanks! I have in fact sent out a mail raising my concern over rq->nr_running. If others agree on the issue to be existing, maybe we can work on this next patchset that can clean this up in all places necessary and not just in nohz_kick_needed().

Regards Preeti U Murthy

Regards, Vincent

...

Regards Preeti U Murthy

On 11 September 2014 12:07, Peter Zijlstra peterz@infradead.org wrote:

On Tue, Aug 26, 2014 at 01:06:51PM +0200, Vincent Guittot wrote:

...

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 18db43e..60ae1ce 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -6049,6 +6049,14 @@ static bool update_sd_pick_busiest(struct lb_env *env, return true; }

• /*
  

•  * The group capacity is reduced probably because of activity from other
  

•  * sched class or interrupts which use part of the available capacity
  

•  */
  

• if ((sg->sgc->capacity_orig * 100) > (sgs->group_capacity *
  

•                         env->sd->imbalance_pct))
  

•         return true;
  

• return false;
  

}

This is unlikely to have worked as intended. You will never reach this, except on PowerPC >= 7. All other machines will have bailed at the !ASYM_PACKING check above this.

Ah yes, i miss that change while rebasing on rik patches. My use case fall in this wider test now that we always select a busiest group

On 11 September 2014 12:13, Peter Zijlstra peterz@infradead.org wrote:

On Tue, Aug 26, 2014 at 01:06:51PM +0200, Vincent Guittot wrote:

...

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 18db43e..60ae1ce 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -6049,6 +6049,14 @@ static bool update_sd_pick_busiest(struct lb_env *env, return true; }

• /*
  

•  * The group capacity is reduced probably because of activity from other
  

•  * sched class or interrupts which use part of the available capacity
  

•  */
  

• if ((sg->sgc->capacity_orig * 100) > (sgs->group_capacity *
  

•                         env->sd->imbalance_pct))
  

•         return true;
  

• return false;
  

}

@@ -6534,13 +6542,23 @@ static int need_active_balance(struct lb_env *env) struct sched_domain *sd = env->sd;

  if (env->idle == CPU_NEWLY_IDLE) {

•         int src_cpu = env->src_cpu;
  
          /*
           * ASYM_PACKING needs to force migrate tasks from busy but
           * higher numbered CPUs in order to pack all tasks in the
           * lowest numbered CPUs.
           */
  

•         if ((sd->flags & SD_ASYM_PACKING) && env->src_cpu > env->dst_cpu)
  

•         if ((sd->flags & SD_ASYM_PACKING) && src_cpu > env->dst_cpu)
  

•                 return 1;
  

•         /*
  

•          * If the CPUs share their cache and the src_cpu's capacity is
  

•          * reduced because of other sched_class or IRQs, we trig an
  

•          * active balance to move the task
  

•          */
  

•         if ((capacity_orig_of(src_cpu) * 100) > (capacity_of(src_cpu) *
  

•                         sd->imbalance_pct))
                  return 1;
  }
  

Should you not also check -- in both cases -- that the destination is any better?

The case should have been solved earlier when calculating the imbalance which should be null if the destination is worse than the source.

But i haven't formally check that calculate_imbalance correctly handles that case

Also, there's some obvious repetition going on there, maybe add a helper?

yes

Also, both sites should probably ensure they're operating in the non-saturated/overloaded scenario. Because as soon as we're completely saturated we want SMP nice etc. and that all already works right (presumably).

If both are overloaded, calculated_imbalance will cap the max load that can be pulled so the busiest_group will not become idle

On 11 September 2014 13:17, Peter Zijlstra peterz@infradead.org wrote:

On Tue, Aug 26, 2014 at 01:06:52PM +0200, Vincent Guittot wrote:

...

index 5c2c885..7dfd584 100644 --- a/include/linux/sched.h +++ b/include/linux/sched.h @@ -1073,10 +1073,10 @@ struct sched_avg { * above by 1024/(1-y). Thus we only need a u32 to store them for all * choices of y < 1-2^(-32)*1024. */

• u32 runnable_avg_sum, runnable_avg_period;
  

• u32 runnable_avg_sum, runnable_avg_period, running_avg_sum;
  

Seeing how we use runnable_avg_period for both runnable and running, does it make sense to remove the runnable part of it from the name?

It's right

Also, 4 byte hole here, not sure we've got anything useful to stuff in it though.

I can move all u32 declaration at the end of the struct unless it has been put before any u64 for good reason

...

  u64 last_runnable_update;
  s64 decay_count;

• unsigned long load_avg_contrib;
  

• unsigned long load_avg_contrib, usage_avg_contrib;
  

};

Man, I should go look at Yuyang's rewrite of this all again. I just tried to figure out the decay stuff and my head hurts ;-)

On 11 September 2014 14:34, Peter Zijlstra peterz@infradead.org wrote:

On Tue, Aug 26, 2014 at 01:06:53PM +0200, Vincent Guittot wrote:

...

Monitor the utilization level of each group of each sched_domain level. The utilization is the amount of cpu_capacity that is currently used on a CPU or group of CPUs. We use the usage_load_avg to evaluate this utilization level. In the special use case where the CPU is fully loaded by more than 1 task, the activity level is set above the cpu_capacity in order to reflect the overload of the CPU

Signed-off-by: Vincent Guittot vincent.guittot@linaro.org

kernel/sched/fair.c | 19 ++++++++++++++++++- 1 file changed, 18 insertions(+), 1 deletion(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c index 1fd2131..2f95d1c 100644 --- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -4126,6 +4126,11 @@ static unsigned long capacity_of(int cpu) return cpu_rq(cpu)->cpu_capacity; }

+static unsigned long capacity_orig_of(int cpu) +{

• return cpu_rq(cpu)->cpu_capacity_orig;
  

+}

static unsigned long cpu_avg_load_per_task(int cpu) { struct rq *rq = cpu_rq(cpu);

This hunk should probably go into patch 6.

...

@@ -4514,6 +4519,17 @@ static int select_idle_sibling(struct task_struct *p, int target) return target; }

+static int get_cpu_utilization(int cpu) +{

• unsigned long usage = cpu_rq(cpu)->cfs.usage_load_avg;
  

• unsigned long capacity = capacity_of(cpu);
  

• if (usage >= SCHED_LOAD_SCALE)
  

•         return capacity + 1;
  

• return (usage * capacity) >> SCHED_LOAD_SHIFT;
  

+}

So if I understood patch 9 correct, your changelog is iffy. usage_load_avg should never get > 1 (of whatever unit), no matter how many tasks are on the rq. You can only maximally run all the time.

Therefore I can only interpret the if (usage >= SCHED_LOAD_SCALE) as numerical error handling, nothing more.

yes

Also I'm not entirely sure I like the usage, utilization names/metrics. I would suggest to reverse them. Call the pure running number 'utilization' and this scaled with capacity 'usage' or so.

ok. i can invert 'usage' and 'utilization', which will give

s/get_cpu_utilization/get_cpu_usage/ s/sgs->group_utilization/sgs->group_usage/ s/cfs.usage_load_avg/cfs.utilization_load_avg/ s/se->avg.usage_avg_contrib/se->avg.utilization_avg_contrib s/__update_task_entity_usage/__update_task_entity_utilization s/__update_entity_usage_avg_contrib/__update_entity_utilization_avg_contrib

...

@@ -6188,7 +6206,6 @@ static inline void update_sd_lb_stats(struct lb_env *env, struct sd_lb_stats *sd /* Now, start updating sd_lb_stats */ sds->total_load += sgs->group_load; sds->total_capacity += sgs->group_capacity;

•         sg = sg->next;
  } while (sg != env->sd->groups);
  
  

I like that extra line of whitespace, it separates the body from the loop itself.

Sorry, i don't know why i remove it

On Thu, Sep 11, 2014 at 01:34:12PM +0100, Peter Zijlstra wrote:

...

@@ -4514,6 +4519,17 @@ static int select_idle_sibling(struct task_struct *p, int target) return target; } +static int get_cpu_utilization(int cpu) +{

• unsigned long usage = cpu_rq(cpu)->cfs.usage_load_avg;
• unsigned long capacity = capacity_of(cpu);
• if (usage >= SCHED_LOAD_SCALE)

• return capacity + 1;
  

• return (usage * capacity) >> SCHED_LOAD_SHIFT;

+}

So if I understood patch 9 correct, your changelog is iffy. usage_load_avg should never get > 1 (of whatever unit), no matter how many tasks are on the rq. You can only maximally run all the time.

Therefore I can only interpret the if (usage >= SCHED_LOAD_SCALE) as numerical error handling, nothing more.

That is not entirely true unless you also classify transient usage spikes due to task migrations as numerical errors as well.

Since each task sched_entity is carrying around 350ms worth of execution history with it between different cpus and cpu utilization is based on the sum of task entity usage_avg_contrib on the runqueue you may get cfs.usage_load_avg > 1 temporarily after task migrations. It will eventually converge to 1.

The same goes for new tasks which are initialized to have a usage_avg_contrib of 1 and may be queued on cpu with tasks already running. In that case cfs.usage_load_avg is temporarily unbounded.

Also I'm not entirely sure I like the usage, utilization names/metrics. I would suggest to reverse them. Call the pure running number 'utilization' and this scaled with capacity 'usage' or so.

I can agree with calling running for utilization, but I'm not convienced about capacity. What does it exactly cover here? I'm confused and jetlagged.

Morten

On Tue, Aug 26, 2014 at 01:06:54PM +0200, 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 capacity is SCHED_CAPACITY_SCALE. We can now have a better idea of the capacity of a group of CPUs and of the utilization of this group thanks to the rework of group_capacity_orig and the group_utilization. We can now deduct how many capacity is still available.

Signed-off-by: Vincent Guittot vincent.guittot@linaro.org

A few minor changes I did while going through it.

--- a/kernel/sched/fair.c +++ b/kernel/sched/fair.c @@ -5669,7 +5669,7 @@ struct sg_lb_stats { unsigned int idle_cpus; unsigned int group_weight; enum group_type group_type; - int group_out_of_capacity; + int group_no_capacity; #ifdef CONFIG_NUMA_BALANCING unsigned int nr_numa_running; unsigned int nr_preferred_running; @@ -5931,37 +5931,37 @@ static inline int sg_imbalanced(struct s return group->sgc->imbalance; }

-static inline int group_has_free_capacity(struct sg_lb_stats *sgs, - struct lb_env *env) +static inline bool +group_has_capacity(struct lb_env *env, struct sg_lb_stats *sgs) { if ((sgs->group_capacity_orig * 100) > (sgs->group_utilization * env->sd->imbalance_pct)) - return 1; + return true;

if (sgs->sum_nr_running < sgs->group_weight) - return 1; + return true;

- return 0; + return false; }

-static inline int group_is_overloaded(struct sg_lb_stats *sgs, - struct lb_env *env) +static inline bool +group_is_overloaded(struct lb_env *env, struct sg_lb_stats *sgs) { if (sgs->sum_nr_running <= sgs->group_weight) - return 0; + return false;

if ((sgs->group_capacity_orig * 100) < (sgs->group_utilization * env->sd->imbalance_pct)) - return 1; + return true;

- return 0; + return false; }

-static enum group_type -group_classify(struct sched_group *group, struct sg_lb_stats *sgs, - struct lb_env *env) +static enum group_type group_classify(struct lb_env *env, + struct sched_group *group, + struct sg_lb_stats *sgs) { - if (group_is_overloaded(sgs, env)) + if (group_is_overloaded(env, sgs)) return group_overloaded;

if (sg_imbalanced(group)) @@ -6024,9 +6024,8 @@ static inline void update_sg_lb_stats(st

sgs->group_weight = group->group_weight;

- sgs->group_type = group_classify(group, sgs, env); - - sgs->group_out_of_capacity = group_is_overloaded(sgs, env); + sgs->group_type = group_classify(env, group, sgs); + sgs->group_no_capacity = group_is_overloaded(env, sgs); }

/** @@ -6157,9 +6156,9 @@ static inline void update_sd_lb_stats(st * with a large weight task outweighs the tasks on the system). */ if (prefer_sibling && sds->local && - group_has_free_capacity(&sds->local_stat, env)) { + group_has_capacity(env, &sds->local_stat)) { if (sgs->sum_nr_running > 1) - sgs->group_out_of_capacity = 1; + sgs->group_no_capacity = 1; sgs->group_capacity = min(sgs->group_capacity, SCHED_CAPACITY_SCALE); } @@ -6430,9 +6429,8 @@ static struct sched_group *find_busiest_ goto force_balance;

/* SD_BALANCE_NEWIDLE trumps SMP nice when underutilized */ - if (env->idle == CPU_NEWLY_IDLE && - group_has_free_capacity(local, env) && - busiest->group_out_of_capacity) + if (env->idle == CPU_NEWLY_IDLE && group_has_capacity(env, local) && + busiest->group_no_capacity) goto force_balance;

/*