Re: [PATCH v8 03/10] sched: move cfs task on a CPU with higher capacity

Re: [PATCH v8 03/10] sched: move cfs task on a CPU with higher capacity

[Hillf Danton]

> >>   +     /*
> >> +        * The dst_cpu is idle and the src_cpu CPU has only 1 CFS task.
> >
> >
> > Why specify one task instead of not less than one?
> 
> if cfs.h_nr_running = 0 (which should not occurs at that point), we
> don't need to do more test to check if it's worth moving the task
> because there is no task to move.
> 
I wonder if you can please shed light on the case that 
the dst_cpu is newly idle.

Thanks
Hillf

Re: [PATCH v8 03/10] sched: move cfs task on a CPU with higher capacity

[Vincent Guittot]

On 4 November 2014 13:07, Hillf Danton <hillf.zj@alibaba-inc.com> wrote:
>> >>   +     /*
>> >> +        * The dst_cpu is idle and the src_cpu CPU has only 1 CFS task.
>> >
>> >
>> > Why specify one task instead of not less than one?
>>
>> if cfs.h_nr_running = 0 (which should not occurs at that point), we
>> don't need to do more test to check if it's worth moving the task
>> because there is no task to move.
>>
> I wonder if you can please shed light on the case that
> the dst_cpu is newly idle.

The main problem if we do the test only for newly idle case, is that
we are not sure to move the task because we must rely on the
wakeup/sleep sequence of other tasks on an idle CPU in order to trig
the migration (periodic background task as an example). So we might
never move the task whereas idle CPUs are available

Regards,
Vincent

>
> Thanks
> Hillf
>

RE: [PATCH v8 03/10] sched: move cfs task on a CPU with higher capacity

[Hillf Danton]

> 
> On 4 November 2014 13:07, Hillf Danton <hillf.zj@alibaba-inc.com> wrote:
> >> >>   +     /*
> >> >> +        * The dst_cpu is idle and the src_cpu CPU has only 1 CFS task.
> >> >
> >> >
> >> > Why specify one task instead of not less than one?
> >>
> >> if cfs.h_nr_running = 0 (which should not occurs at that point), we
> >> don't need to do more test to check if it's worth moving the task
> >> because there is no task to move.
> >>
> > I wonder if you can please shed light on the case that
> > the dst_cpu is newly idle.
> 
> The main problem if we do the test only for newly idle case, is that
> we are not sure to move the task because we must rely on the
> wakeup/sleep sequence of other tasks on an idle CPU in order to trig
> the migration (periodic background task as an example). So we might
> never move the task whereas idle CPUs are available
> 
So no task is migrated in the newly idle case, if I understand the
above correctly.

Hillf

Re: [PATCH v8 03/10] sched: move cfs task on a CPU with higher capacity

[Vincent Guittot]

On 4 November 2014 13:54, Hillf Danton <hillf.zj@alibaba-inc.com> wrote:
>>
>> On 4 November 2014 13:07, Hillf Danton <hillf.zj@alibaba-inc.com> wrote:
>> >> >>   +     /*
>> >> >> +        * The dst_cpu is idle and the src_cpu CPU has only 1 CFS task.
>> >> >
>> >> >
>> >> > Why specify one task instead of not less than one?
>> >>
>> >> if cfs.h_nr_running = 0 (which should not occurs at that point), we
>> >> don't need to do more test to check if it's worth moving the task
>> >> because there is no task to move.
>> >>
>> > I wonder if you can please shed light on the case that
>> > the dst_cpu is newly idle.
>>
>> The main problem if we do the test only for newly idle case, is that
>> we are not sure to move the task because we must rely on the
>> wakeup/sleep sequence of other tasks on an idle CPU in order to trig
>> the migration (periodic background task as an example). So we might
>> never move the task whereas idle CPUs are available
>>
> So no task is migrated in the newly idle case, if I understand the
> above correctly.

A task can be moved in both idle and newly idle. If we rely only on
newly idle and we  have only idle CPUs, we can never move task. In the
same way, if we rely only on idle case and a CPU never stays idle long
enough to trig the idle load balance, we will never move the task. I
agree that for the latter, we might wonder if it's worth moving the
task. This is your concern ?

Vincent

>
> Hillf
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

RE: [PATCH v8 03/10] sched: move cfs task on a CPU with higher capacity

[Hillf Danton]

> >> > I wonder if you can please shed light on the case that
> >> > the dst_cpu is newly idle.
> >>
> >> The main problem if we do the test only for newly idle case, is that
> >> we are not sure to move the task because we must rely on the
> >> wakeup/sleep sequence of other tasks on an idle CPU in order to trig
> >> the migration (periodic background task as an example). So we might
> >> never move the task whereas idle CPUs are available
> >>
> > So no task is migrated in the newly idle case, if I understand the
> > above correctly.
> 
> A task can be moved in both idle and newly idle. If we rely only on
> newly idle and we  have only idle CPUs, we can never move task. In the
> same way, if we rely only on idle case and a CPU never stays idle long
> enough to trig the idle load balance, we will never move the task. I
> agree that for the latter, we might wonder if it's worth moving the
> task. This is your concern ?
> 
I concern if the only-one cfs task is migrated to a newly-idle CPU in
your code:
+	/*
+	 * The dst_cpu is idle and the src_cpu CPU has only 1 CFS task.
+	 * It's worth migrating the task if the src_cpu's capacity is reduced
+	 * because of other sched_class or IRQs whereas capacity stays
+	 * available on dst_cpu.
+	 */
+	if ((env->idle != CPU_NOT_IDLE) &&
+			(env->src_rq->cfs.h_nr_running == 1)) {
+	
due to the comment:
                /*
                 * Increment the failure counter only on periodic balance.
                 * We do not want newidle balance, which can be very
                 * frequent, pollute the failure counter causing
                 * excessive cache_hot migrations and active balances.
                 */
                if (idle != CPU_NEWLY_IDLE)
                        sd->nr_balance_failed++;

Hillf

Re: [PATCH v8 03/10] sched: move cfs task on a CPU with higher capacity

[Vincent Guittot]

On 4 November 2014 14:31, Hillf Danton <hillf.zj@alibaba-inc.com> wrote:
>> >> > I wonder if you can please shed light on the case that
>> >> > the dst_cpu is newly idle.
>> >>
>> >> The main problem if we do the test only for newly idle case, is that
>> >> we are not sure to move the task because we must rely on the
>> >> wakeup/sleep sequence of other tasks on an idle CPU in order to trig
>> >> the migration (periodic background task as an example). So we might
>> >> never move the task whereas idle CPUs are available
>> >>
>> > So no task is migrated in the newly idle case, if I understand the
>> > above correctly.
>>
>> A task can be moved in both idle and newly idle. If we rely only on
>> newly idle and we  have only idle CPUs, we can never move task. In the
>> same way, if we rely only on idle case and a CPU never stays idle long
>> enough to trig the idle load balance, we will never move the task. I
>> agree that for the latter, we might wonder if it's worth moving the
>> task. This is your concern ?
>>
> I concern if the only-one cfs task is migrated to a newly-idle CPU in
> your code:
> +       /*
> +        * The dst_cpu is idle and the src_cpu CPU has only 1 CFS task.
> +        * It's worth migrating the task if the src_cpu's capacity is reduced
> +        * because of other sched_class or IRQs whereas capacity stays
> +        * available on dst_cpu.
> +        */
> +       if ((env->idle != CPU_NOT_IDLE) &&
> +                       (env->src_rq->cfs.h_nr_running == 1)) {
> +
> due to the comment:
>                 /*
>                  * Increment the failure counter only on periodic balance.
>                  * We do not want newidle balance, which can be very
>                  * frequent, pollute the failure counter causing
>                  * excessive cache_hot migrations and active balances.
>                  */
>                 if (idle != CPU_NEWLY_IDLE)
>                         sd->nr_balance_failed++;
>

I understand the code above as only idle CPU increases the
nr_balance_failed and can generate an active load balance but newly
idle CPUs don't increase it because it can occur quite often and would
generate excessive active migration.
This patch will not pollute nr_balance_failed as it will clear it once
the task has moved on another CPU with full capacity. If a newly idle
load balance occurs before, the nr_balance_failed will also be cleared

Vincent

> Hillf
>

[PATCH v8 00/10] sched: consolidation of CPU capacity and usage

[Vincent Guittot]

This patchset consolidates several changes in the capacity and the usage
tracking of the CPU. It provides a frequency invariant metric of the usage of
CPUs and generally improves the accuracy of load/usage tracking in the
scheduler. The frequency invariant metric is the foundation required for the
consolidation of cpufreq and implementation of a fully invariant load tracking.
These are currently WIP and require several changes to the load balancer
(including how it will use and interprets load and capacity metrics) and
extensive validation. The frequency invariance is done with
arch_scale_freq_capacity and this patchset doesn't provide the backends of
the function which are architecture dependent.

As discussed at LPC14, Morten and I have consolidated our changes into a single
patchset to make it easier to review and merge.

During load balance, the scheduler evaluates the number of tasks that a group
of CPUs can handle. The current method assumes that tasks have a fix load of
SCHED_LOAD_SCALE and CPUs have a default capacity of SCHED_CAPACITY_SCALE.
This assumption generates wrong decision by creating ghost cores or by
removing real ones when the original capacity of CPUs is different from the
default SCHED_CAPACITY_SCALE. With this patch set, we don't try anymore to
evaluate the number of available cores based on the group_capacity but instead
we evaluate the usage of a group and compare it with its capacity.

This patchset mainly replaces the old capacity_factor method by a new one and
keeps the general policy almost unchanged. These new metrics will be also used
in later patches.

The CPU usage is based on a running time tracking version of the current
implementation of the load average tracking. I also have a version that is
based on the new implementation proposal [1] but I haven't provide the patches
and results as [1] is still under review. I can provide change above [1] to
change how CPU usage is computed and to adapt to new mecanism.

Change since V7
 - add freq invariance for usage tracking
 - add freq invariance for scale_rt
 - update comments and commits' message
 - fix init of utilization_avg_contrib
 - fix prefer_sibling

Change since V6
 - add group usage tracking
 - fix some commits' messages
 - minor fix like comments and argument order

Change since V5
 - remove patches that have been merged since v5 : patches 01, 02, 03, 04, 05, 07
 - update commit log and add more details on the purpose of the patches
 - fix/remove useless code with the rebase on patchset [2]
 - remove capacity_orig in sched_group_capacity as it is not used
 - move code in the right patch
 - add some helper function to factorize code

Change since V4
 - rebase to manage conflicts with changes in selection of busiest group

Change since V3:
 - add usage_avg_contrib statistic which sums the running time of tasks on a rq
 - use usage_avg_contrib instead of runnable_avg_sum for cpu_utilization
 - fix replacement power by capacity
 - update some comments

Change since V2:
 - rebase on top of capacity renaming
 - fix wake_affine statistic update
 - rework nohz_kick_needed
 - optimize the active migration of a task from CPU with reduced capacity
 - rename group_activity by group_utilization and remove unused total_utilization
 - repair SD_PREFER_SIBLING and use it for SMT level
 - reorder patchset to gather patches with same topics

Change since V1:
 - add 3 fixes
 - correct some commit messages
 - replace capacity computation by activity
 - take into account current cpu capacity

[1] https://lkml.org/lkml/2014/10/10/131
[2] https://lkml.org/lkml/2014/7/25/589

Morten Rasmussen (2):
  sched: Track group sched_entity usage contributions
  sched: Make sched entity usage tracking scale-invariant

Vincent Guittot (8):
  sched: add per rq cpu_capacity_orig
  sched: remove frequency scaling from cpu_capacity
  sched: move cfs task on a CPU with higher capacity
  sched: add utilization_avg_contrib
  sched: get CPU's usage statistic
  sched: replace capacity_factor by usage
  sched: add SD_PREFER_SIBLING for SMT level
  sched: make scale_rt invariant with frequency

 include/linux/sched.h |  21 ++-
 kernel/sched/core.c   |  15 +-
 kernel/sched/debug.c  |  12 +-
 kernel/sched/fair.c   | 369 ++++++++++++++++++++++++++++++++------------------
 kernel/sched/sched.h  |  15 +-
 5 files changed, 276 insertions(+), 156 deletions(-)

-- 
1.9.1

[PATCH v8 03/10] sched: move cfs task on a CPU with higher capacity

[Vincent Guittot]

When a CPU is used to handle a lot of IRQs or some RT tasks, the remaining
capacity for CFS tasks can be significantly reduced. Once we detect such
situation by comparing cpu_capacity_orig and cpu_capacity, we trig an idle
load balance to check if it's worth moving its tasks on an idle CPU.

Once the idle load_balance has selected the busiest CPU, it will look for an
active load balance for only two cases :
- there is only 1 task on the busiest CPU.
- we haven't been able to move a task of the busiest rq.

A CPU with a reduced capacity is included in the 1st case, and it's worth to
actively migrate its task if the idle CPU has got full capacity. This test has
been added in need_active_balance.

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

env.src_cpu and env.src_rq must be set unconditionnally because they are used
in need_active_balance which is called even if busiest->nr_running equals 1

Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
---
 kernel/sched/fair.c | 86 ++++++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 65 insertions(+), 21 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index bd214d2..54468f3 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -5889,6 +5889,18 @@ fix_small_capacity(struct sched_domain *sd, struct sched_group *group)
 }
 
 /*
+ * 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
+ */
+static inline int
+check_cpu_capacity(struct rq *rq, struct sched_domain *sd)
+{
+	return ((rq->cpu_capacity * sd->imbalance_pct) <
+				(rq->cpu_capacity_orig * 100));
+}
+
+/*
  * Group imbalance indicates (and tries to solve) the problem where balancing
  * groups is inadequate due to tsk_cpus_allowed() constraints.
  *
@@ -6562,6 +6574,28 @@ static int need_active_balance(struct lb_env *env)
 			return 1;
 	}
 
+	/*
+	 * The dst_cpu is idle and the src_cpu CPU has only 1 CFS task.
+	 * It's worth migrating the task if the src_cpu's capacity is reduced
+	 * because of other sched_class or IRQs whereas capacity stays
+	 * available on dst_cpu.
+	 */
+	if ((env->idle != CPU_NOT_IDLE) &&
+			(env->src_rq->cfs.h_nr_running == 1)) {
+		unsigned long src_eff_capacity, dst_eff_capacity;
+
+		dst_eff_capacity = 100;
+		dst_eff_capacity *= capacity_of(env->dst_cpu);
+		dst_eff_capacity *= capacity_orig_of(env->src_cpu);
+
+		src_eff_capacity = sd->imbalance_pct;
+		src_eff_capacity *= capacity_of(env->src_cpu);
+		src_eff_capacity *= capacity_orig_of(env->dst_cpu);
+
+		if (src_eff_capacity < dst_eff_capacity)
+			return 1;
+	}
+
 	return unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2);
 }
 
@@ -6661,6 +6695,9 @@ static int load_balance(int this_cpu, struct rq *this_rq,
 
 	schedstat_add(sd, lb_imbalance[idle], env.imbalance);
 
+	env.src_cpu = busiest->cpu;
+	env.src_rq = busiest;
+
 	ld_moved = 0;
 	if (busiest->nr_running > 1) {
 		/*
@@ -6670,8 +6707,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);
 
 more_balance:
@@ -7371,22 +7406,25 @@ 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.
  */
-static inline int nohz_kick_needed(struct rq *rq)
+static inline bool nohz_kick_needed(struct rq *rq)
 {
 	unsigned long now = jiffies;
 	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
@@ -7400,38 +7438,44 @@ 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)
-		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) &&
+				check_cpu_capacity(rq, sd)) {
+			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) { }
-- 
1.9.1

Re: [PATCH v8 03/10] sched: move cfs task on a CPU with higher capacity

[Wanpeng Li]

On 14/10/31 下午4:47, Vincent Guittot wrote:
> When a CPU is used to handle a lot of IRQs or some RT tasks, the remaining
> capacity for CFS tasks can be significantly reduced. Once we detect such
> situation by comparing cpu_capacity_orig and cpu_capacity, we trig an idle
> load balance to check if it's worth moving its tasks on an idle CPU.
>
> Once the idle load_balance has selected the busiest CPU, it will look for an
> active load balance for only two cases :
> - there is only 1 task on the busiest CPU.
> - we haven't been able to move a task of the busiest rq.
>
> A CPU with a reduced capacity is included in the 1st case, and it's worth to
> actively migrate its task if the idle CPU has got full capacity. This test has
> been added in need_active_balance.
>
> 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
>
> env.src_cpu and env.src_rq must be set unconditionnally because they are used
> in need_active_balance which is called even if busiest->nr_running equals 1
>
> Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> ---
>   kernel/sched/fair.c | 86 ++++++++++++++++++++++++++++++++++++++++-------------
>   1 file changed, 65 insertions(+), 21 deletions(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index bd214d2..54468f3 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -5889,6 +5889,18 @@ fix_small_capacity(struct sched_domain *sd, struct sched_group *group)
>   }
>   
>   /*
> + * 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
> + */
> +static inline int
> +check_cpu_capacity(struct rq *rq, struct sched_domain *sd)
> +{
> +	return ((rq->cpu_capacity * sd->imbalance_pct) <
> +				(rq->cpu_capacity_orig * 100));
> +}
> +
> +/*
>    * Group imbalance indicates (and tries to solve) the problem where balancing
>    * groups is inadequate due to tsk_cpus_allowed() constraints.
>    *
> @@ -6562,6 +6574,28 @@ static int need_active_balance(struct lb_env *env)
>   			return 1;
>   	}
>   
> +	/*
> +	 * The dst_cpu is idle and the src_cpu CPU has only 1 CFS task.

Why specify one task instead of not less than one?

Regards,
Wanpeng Li

> +	 * It's worth migrating the task if the src_cpu's capacity is reduced
> +	 * because of other sched_class or IRQs whereas capacity stays
> +	 * available on dst_cpu.
> +	 */
> +	if ((env->idle != CPU_NOT_IDLE) &&
> +			(env->src_rq->cfs.h_nr_running == 1)) {
> +		unsigned long src_eff_capacity, dst_eff_capacity;
> +
> +		dst_eff_capacity = 100;
> +		dst_eff_capacity *= capacity_of(env->dst_cpu);
> +		dst_eff_capacity *= capacity_orig_of(env->src_cpu);
> +
> +		src_eff_capacity = sd->imbalance_pct;
> +		src_eff_capacity *= capacity_of(env->src_cpu);
> +		src_eff_capacity *= capacity_orig_of(env->dst_cpu);
> +
> +		if (src_eff_capacity < dst_eff_capacity)
> +			return 1;
> +	}
> +
>   	return unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2);
>   }
>   
> @@ -6661,6 +6695,9 @@ static int load_balance(int this_cpu, struct rq *this_rq,
>   
>   	schedstat_add(sd, lb_imbalance[idle], env.imbalance);
>   
> +	env.src_cpu = busiest->cpu;
> +	env.src_rq = busiest;
> +
>   	ld_moved = 0;
>   	if (busiest->nr_running > 1) {
>   		/*
> @@ -6670,8 +6707,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);
>   
>   more_balance:
> @@ -7371,22 +7406,25 @@ 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.
>    */
> -static inline int nohz_kick_needed(struct rq *rq)
> +static inline bool nohz_kick_needed(struct rq *rq)
>   {
>   	unsigned long now = jiffies;
>   	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
> @@ -7400,38 +7438,44 @@ 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)
> -		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) &&
> +				check_cpu_capacity(rq, sd)) {
> +			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) { }

Re: [PATCH v8 03/10] sched: move cfs task on a CPU with higher capacity

[Vincent Guittot]

On 4 November 2014 09:30, Wanpeng Li <kernellwp@gmail.com> wrote:
>
> On 14/10/31 下午4:47, Vincent Guittot wrote:
>>
>> When a CPU is used to handle a lot of IRQs or some RT tasks, the remaining
>> capacity for CFS tasks can be significantly reduced. Once we detect such
>> situation by comparing cpu_capacity_orig and cpu_capacity, we trig an idle
>> load balance to check if it's worth moving its tasks on an idle CPU.
>>
>> Once the idle load_balance has selected the busiest CPU, it will look for
>> an
>> active load balance for only two cases :
>> - there is only 1 task on the busiest CPU.
>> - we haven't been able to move a task of the busiest rq.
>>
>> A CPU with a reduced capacity is included in the 1st case, and it's worth
>> to
>> actively migrate its task if the idle CPU has got full capacity. This test
>> has
>> been added in need_active_balance.
>>
>> 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
>>
>> env.src_cpu and env.src_rq must be set unconditionnally because they are
>> used
>> in need_active_balance which is called even if busiest->nr_running equals
>> 1
>>
>> Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
>> ---
>>   kernel/sched/fair.c | 86
>> ++++++++++++++++++++++++++++++++++++++++-------------
>>   1 file changed, 65 insertions(+), 21 deletions(-)
>>
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index bd214d2..54468f3 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -5889,6 +5889,18 @@ fix_small_capacity(struct sched_domain *sd, struct
>> sched_group *group)
>>   }
>>     /*
>> + * 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
>> + */
>> +static inline int
>> +check_cpu_capacity(struct rq *rq, struct sched_domain *sd)
>> +{
>> +       return ((rq->cpu_capacity * sd->imbalance_pct) <
>> +                               (rq->cpu_capacity_orig * 100));
>> +}
>> +
>> +/*
>>    * Group imbalance indicates (and tries to solve) the problem where
>> balancing
>>    * groups is inadequate due to tsk_cpus_allowed() constraints.
>>    *
>> @@ -6562,6 +6574,28 @@ static int need_active_balance(struct lb_env *env)
>>                         return 1;
>>         }
>>   +     /*
>> +        * The dst_cpu is idle and the src_cpu CPU has only 1 CFS task.
>
>
> Why specify one task instead of not less than one?

if cfs.h_nr_running == 0 (which should not occurs at that point), we
don't need to do more test to check if it's worth moving the task
because there is no task to move.

Regards,
Vincent
>
> Regards,
> Wanpeng Li
>
>
>> +        * It's worth migrating the task if the src_cpu's capacity is
>> reduced
>> +        * because of other sched_class or IRQs whereas capacity stays
>> +        * available on dst_cpu.
>> +        */
>> +       if ((env->idle != CPU_NOT_IDLE) &&
>> +                       (env->src_rq->cfs.h_nr_running == 1)) {
>> +               unsigned long src_eff_capacity, dst_eff_capacity;
>> +
>> +               dst_eff_capacity = 100;
>> +               dst_eff_capacity *= capacity_of(env->dst_cpu);
>> +               dst_eff_capacity *= capacity_orig_of(env->src_cpu);
>> +
>> +               src_eff_capacity = sd->imbalance_pct;
>> +               src_eff_capacity *= capacity_of(env->src_cpu);
>> +               src_eff_capacity *= capacity_orig_of(env->dst_cpu);
>> +
>> +               if (src_eff_capacity < dst_eff_capacity)
>> +                       return 1;
>> +       }
>> +
>>         return unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2);
>>   }
>>   @@ -6661,6 +6695,9 @@ static int load_balance(int this_cpu, struct rq
>> *this_rq,
>>         schedstat_add(sd, lb_imbalance[idle], env.imbalance);
>>   +     env.src_cpu = busiest->cpu;
>> +       env.src_rq = busiest;
>> +
>>         ld_moved = 0;
>>         if (busiest->nr_running > 1) {
>>                 /*
>> @@ -6670,8 +6707,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);
>>     more_balance:
>> @@ -7371,22 +7406,25 @@ 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.
>>    */
>> -static inline int nohz_kick_needed(struct rq *rq)
>> +static inline bool nohz_kick_needed(struct rq *rq)
>>   {
>>         unsigned long now = jiffies;
>>         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
>> @@ -7400,38 +7438,44 @@ 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)
>> -               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) &&
>> +                               check_cpu_capacity(rq, sd)) {
>> +                       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) { }
>
>

Re: [PATCH v8 03/10] sched: move cfs task on a CPU with higher capacity

[Wanpeng Li]

Hi Vincent,
On 14/11/4 下午5:41, Vincent Guittot wrote:
> On 4 November 2014 09:30, Wanpeng Li <kernellwp@gmail.com> wrote:
>> On 14/10/31 下午4:47, Vincent Guittot wrote:
>>> When a CPU is used to handle a lot of IRQs or some RT tasks, the remaining
>>> capacity for CFS tasks can be significantly reduced. Once we detect such
>>> situation by comparing cpu_capacity_orig and cpu_capacity, we trig an idle
>>> load balance to check if it's worth moving its tasks on an idle CPU.
>>>
>>> Once the idle load_balance has selected the busiest CPU, it will look for
>>> an
>>> active load balance for only two cases :
>>> - there is only 1 task on the busiest CPU.
>>> - we haven't been able to move a task of the busiest rq.
>>>
>>> A CPU with a reduced capacity is included in the 1st case, and it's worth
>>> to
>>> actively migrate its task if the idle CPU has got full capacity. This test
>>> has
>>> been added in need_active_balance.
>>>
>>> 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
>>>
>>> env.src_cpu and env.src_rq must be set unconditionnally because they are
>>> used
>>> in need_active_balance which is called even if busiest->nr_running equals
>>> 1
>>>
>>> Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
>>> ---
>>>    kernel/sched/fair.c | 86
>>> ++++++++++++++++++++++++++++++++++++++++-------------
>>>    1 file changed, 65 insertions(+), 21 deletions(-)
>>>
>>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>>> index bd214d2..54468f3 100644
>>> --- a/kernel/sched/fair.c
>>> +++ b/kernel/sched/fair.c
>>> @@ -5889,6 +5889,18 @@ fix_small_capacity(struct sched_domain *sd, struct
>>> sched_group *group)
>>>    }
>>>      /*
>>> + * 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
>>> + */
>>> +static inline int
>>> +check_cpu_capacity(struct rq *rq, struct sched_domain *sd)
>>> +{
>>> +       return ((rq->cpu_capacity * sd->imbalance_pct) <
>>> +                               (rq->cpu_capacity_orig * 100));
>>> +}
>>> +
>>> +/*
>>>     * Group imbalance indicates (and tries to solve) the problem where
>>> balancing
>>>     * groups is inadequate due to tsk_cpus_allowed() constraints.
>>>     *
>>> @@ -6562,6 +6574,28 @@ static int need_active_balance(struct lb_env *env)
>>>                          return 1;
>>>          }
>>>    +     /*
>>> +        * The dst_cpu is idle and the src_cpu CPU has only 1 CFS task.
>>
>> Why specify one task instead of not less than one?
> if cfs.h_nr_running == 0 (which should not occurs at that point), we
> don't need to do more test to check if it's worth moving the task
> because there is no task to move.

Sorry for my confusing statement. I mean cfs.h_nr_running >= 1.

Regards,
Wanpeng Li

>
> Regards,
> Vincent
>> Regards,
>> Wanpeng Li
>>
>>
>>> +        * It's worth migrating the task if the src_cpu's capacity is
>>> reduced
>>> +        * because of other sched_class or IRQs whereas capacity stays
>>> +        * available on dst_cpu.
>>> +        */
>>> +       if ((env->idle != CPU_NOT_IDLE) &&
>>> +                       (env->src_rq->cfs.h_nr_running == 1)) {
>>> +               unsigned long src_eff_capacity, dst_eff_capacity;
>>> +
>>> +               dst_eff_capacity = 100;
>>> +               dst_eff_capacity *= capacity_of(env->dst_cpu);
>>> +               dst_eff_capacity *= capacity_orig_of(env->src_cpu);
>>> +
>>> +               src_eff_capacity = sd->imbalance_pct;
>>> +               src_eff_capacity *= capacity_of(env->src_cpu);
>>> +               src_eff_capacity *= capacity_orig_of(env->dst_cpu);
>>> +
>>> +               if (src_eff_capacity < dst_eff_capacity)
>>> +                       return 1;
>>> +       }
>>> +
>>>          return unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2);
>>>    }
>>>    @@ -6661,6 +6695,9 @@ static int load_balance(int this_cpu, struct rq
>>> *this_rq,
>>>          schedstat_add(sd, lb_imbalance[idle], env.imbalance);
>>>    +     env.src_cpu = busiest->cpu;
>>> +       env.src_rq = busiest;
>>> +
>>>          ld_moved = 0;
>>>          if (busiest->nr_running > 1) {
>>>                  /*
>>> @@ -6670,8 +6707,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);
>>>      more_balance:
>>> @@ -7371,22 +7406,25 @@ 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.
>>>     */
>>> -static inline int nohz_kick_needed(struct rq *rq)
>>> +static inline bool nohz_kick_needed(struct rq *rq)
>>>    {
>>>          unsigned long now = jiffies;
>>>          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
>>> @@ -7400,38 +7438,44 @@ 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)
>>> -               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) &&
>>> +                               check_cpu_capacity(rq, sd)) {
>>> +                       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) { }
>>

Re: [PATCH v8 03/10] sched: move cfs task on a CPU with higher capacity

[Vincent Guittot]

On 4 November 2014 11:42, Wanpeng Li <kernellwp@gmail.com> wrote:
> Hi Vincent,
>
>>>> +
>>>> +/*
>>>>     * Group imbalance indicates (and tries to solve) the problem where
>>>> balancing
>>>>     * groups is inadequate due to tsk_cpus_allowed() constraints.
>>>>     *
>>>> @@ -6562,6 +6574,28 @@ static int need_active_balance(struct lb_env
>>>> *env)
>>>>                          return 1;
>>>>          }
>>>>    +     /*
>>>> +        * The dst_cpu is idle and the src_cpu CPU has only 1 CFS task.
>>>
>>>
>>> Why specify one task instead of not less than one?
>>
>> if cfs.h_nr_running == 0 (which should not occurs at that point), we
>> don't need to do more test to check if it's worth moving the task
>> because there is no task to move.
>
>
> Sorry for my confusing statement. I mean cfs.h_nr_running >= 1.

ok.

If we have more than 1 task, we fall back into the default balancing
policy than should move a not running task or that will use the
imbalance field in case of the presence of pinned tasks

Regards,
Vincent

>
> Regards,
> Wanpeng Li
>
>
>>
>> Regards,
>> Vincent
>>>
>>> Regards,
>>> Wanpeng Li
>>>
>>>
>>>> +        * It's worth migrating the task if the src_cpu's capacity is
>>>> reduced
>>>> +        * because of other sched_class or IRQs whereas capacity stays
>>>> +        * available on dst_cpu.
>>>> +        */
>>>> +       if ((env->idle != CPU_NOT_IDLE) &&
>>>> +                       (env->src_rq->cfs.h_nr_running == 1)) {
>>>> +               unsigned long src_eff_capacity, dst_eff_capacity;
>>>> +
>>>> +               dst_eff_capacity = 100;
>>>> +               dst_eff_capacity *= capacity_of(env->dst_cpu);
>>>> +               dst_eff_capacity *= capacity_orig_of(env->src_cpu);
>>>> +
>>>> +               src_eff_capacity = sd->imbalance_pct;
>>>> +               src_eff_capacity *= capacity_of(env->src_cpu);
>>>> +               src_eff_capacity *= capacity_orig_of(env->dst_cpu);
>>>> +
>>>> +               if (src_eff_capacity < dst_eff_capacity)
>>>> +                       return 1;
>>>> +       }
>>>> +

Re: [PATCH v8 03/10] sched: move cfs task on a CPU with higher capacity

[Wanpeng Li]

Hi Vincent,
On 10/31/14, 4:47 PM, Vincent Guittot wrote:
> When a CPU is used to handle a lot of IRQs or some RT tasks, the remaining
> capacity for CFS tasks can be significantly reduced. Once we detect such

I see the cpu capacity will be reduced if RT tasks are running in 
scale_rt_capacity(), could you point out where cpu capacity reduced due 
to IRQs?

Regards,
Wanpeng Li

> situation by comparing cpu_capacity_orig and cpu_capacity, we trig an idle
> load balance to check if it's worth moving its tasks on an idle CPU.
>
> Once the idle load_balance has selected the busiest CPU, it will look for an
> active load balance for only two cases :
> - there is only 1 task on the busiest CPU.
> - we haven't been able to move a task of the busiest rq.
>
> A CPU with a reduced capacity is included in the 1st case, and it's worth to
> actively migrate its task if the idle CPU has got full capacity. This test has
> been added in need_active_balance.
>
> 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
>
> env.src_cpu and env.src_rq must be set unconditionnally because they are used
> in need_active_balance which is called even if busiest->nr_running equals 1
>
> Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
> ---
>   kernel/sched/fair.c | 86 ++++++++++++++++++++++++++++++++++++++++-------------
>   1 file changed, 65 insertions(+), 21 deletions(-)
>
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index bd214d2..54468f3 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -5889,6 +5889,18 @@ fix_small_capacity(struct sched_domain *sd, struct sched_group *group)
>   }
>   
>   /*
> + * 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
> + */
> +static inline int
> +check_cpu_capacity(struct rq *rq, struct sched_domain *sd)
> +{
> +	return ((rq->cpu_capacity * sd->imbalance_pct) <
> +				(rq->cpu_capacity_orig * 100));
> +}
> +
> +/*
>    * Group imbalance indicates (and tries to solve) the problem where balancing
>    * groups is inadequate due to tsk_cpus_allowed() constraints.
>    *
> @@ -6562,6 +6574,28 @@ static int need_active_balance(struct lb_env *env)
>   			return 1;
>   	}
>   
> +	/*
> +	 * The dst_cpu is idle and the src_cpu CPU has only 1 CFS task.
> +	 * It's worth migrating the task if the src_cpu's capacity is reduced
> +	 * because of other sched_class or IRQs whereas capacity stays
> +	 * available on dst_cpu.
> +	 */
> +	if ((env->idle != CPU_NOT_IDLE) &&
> +			(env->src_rq->cfs.h_nr_running == 1)) {
> +		unsigned long src_eff_capacity, dst_eff_capacity;
> +
> +		dst_eff_capacity = 100;
> +		dst_eff_capacity *= capacity_of(env->dst_cpu);
> +		dst_eff_capacity *= capacity_orig_of(env->src_cpu);
> +
> +		src_eff_capacity = sd->imbalance_pct;
> +		src_eff_capacity *= capacity_of(env->src_cpu);
> +		src_eff_capacity *= capacity_orig_of(env->dst_cpu);
> +
> +		if (src_eff_capacity < dst_eff_capacity)
> +			return 1;
> +	}
> +
>   	return unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2);
>   }
>   
> @@ -6661,6 +6695,9 @@ static int load_balance(int this_cpu, struct rq *this_rq,
>   
>   	schedstat_add(sd, lb_imbalance[idle], env.imbalance);
>   
> +	env.src_cpu = busiest->cpu;
> +	env.src_rq = busiest;
> +
>   	ld_moved = 0;
>   	if (busiest->nr_running > 1) {
>   		/*
> @@ -6670,8 +6707,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);
>   
>   more_balance:
> @@ -7371,22 +7406,25 @@ 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.
>    */
> -static inline int nohz_kick_needed(struct rq *rq)
> +static inline bool nohz_kick_needed(struct rq *rq)
>   {
>   	unsigned long now = jiffies;
>   	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
> @@ -7400,38 +7438,44 @@ 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)
> -		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) &&
> +				check_cpu_capacity(rq, sd)) {
> +			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) { }

Re: [PATCH v8 03/10] sched: move cfs task on a CPU with higher capacity

[Vincent Guittot]

On 18 November 2014 11:47, Wanpeng Li <kernellwp@gmail.com> wrote:
> Hi Vincent,
> On 10/31/14, 4:47 PM, Vincent Guittot wrote:
>>
>> When a CPU is used to handle a lot of IRQs or some RT tasks, the remaining
>> capacity for CFS tasks can be significantly reduced. Once we detect such
>
>
> I see the cpu capacity will be reduced if RT tasks are running in
> scale_rt_capacity(), could you point out where cpu capacity reduced due to
> IRQs?

with CONFIG_IRQ_TIME_ACCOUNTING, the time spent in interrupt context
will be added in rq->rt_avg

Regards,
Vincent

>
> Regards,
> Wanpeng Li
>
>
>> situation by comparing cpu_capacity_orig and cpu_capacity, we trig an idle
>> load balance to check if it's worth moving its tasks on an idle CPU.
>>
>> Once the idle load_balance has selected the busiest CPU, it will look for
>> an
>> active load balance for only two cases :
>> - there is only 1 task on the busiest CPU.
>> - we haven't been able to move a task of the busiest rq.
>>
>> A CPU with a reduced capacity is included in the 1st case, and it's worth
>> to
>> actively migrate its task if the idle CPU has got full capacity. This test
>> has
>> been added in need_active_balance.
>>
>> 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
>>
>> env.src_cpu and env.src_rq must be set unconditionnally because they are
>> used
>> in need_active_balance which is called even if busiest->nr_running equals
>> 1
>>
>> Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>
>> ---
>>   kernel/sched/fair.c | 86
>> ++++++++++++++++++++++++++++++++++++++++-------------
>>   1 file changed, 65 insertions(+), 21 deletions(-)
>>
>> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
>> index bd214d2..54468f3 100644
>> --- a/kernel/sched/fair.c
>> +++ b/kernel/sched/fair.c
>> @@ -5889,6 +5889,18 @@ fix_small_capacity(struct sched_domain *sd, struct
>> sched_group *group)
>>   }
>>     /*
>> + * 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
>> + */
>> +static inline int
>> +check_cpu_capacity(struct rq *rq, struct sched_domain *sd)
>> +{
>> +       return ((rq->cpu_capacity * sd->imbalance_pct) <
>> +                               (rq->cpu_capacity_orig * 100));
>> +}
>> +
>> +/*
>>    * Group imbalance indicates (and tries to solve) the problem where
>> balancing
>>    * groups is inadequate due to tsk_cpus_allowed() constraints.
>>    *
>> @@ -6562,6 +6574,28 @@ static int need_active_balance(struct lb_env *env)
>>                         return 1;
>>         }
>>   +     /*
>> +        * The dst_cpu is idle and the src_cpu CPU has only 1 CFS task.
>> +        * It's worth migrating the task if the src_cpu's capacity is
>> reduced
>> +        * because of other sched_class or IRQs whereas capacity stays
>> +        * available on dst_cpu.
>> +        */
>> +       if ((env->idle != CPU_NOT_IDLE) &&
>> +                       (env->src_rq->cfs.h_nr_running == 1)) {
>> +               unsigned long src_eff_capacity, dst_eff_capacity;
>> +
>> +               dst_eff_capacity = 100;
>> +               dst_eff_capacity *= capacity_of(env->dst_cpu);
>> +               dst_eff_capacity *= capacity_orig_of(env->src_cpu);
>> +
>> +               src_eff_capacity = sd->imbalance_pct;
>> +               src_eff_capacity *= capacity_of(env->src_cpu);
>> +               src_eff_capacity *= capacity_orig_of(env->dst_cpu);
>> +
>> +               if (src_eff_capacity < dst_eff_capacity)
>> +                       return 1;
>> +       }
>> +
>>         return unlikely(sd->nr_balance_failed > sd->cache_nice_tries+2);
>>   }
>>   @@ -6661,6 +6695,9 @@ static int load_balance(int this_cpu, struct rq
>> *this_rq,
>>         schedstat_add(sd, lb_imbalance[idle], env.imbalance);
>>   +     env.src_cpu = busiest->cpu;
>> +       env.src_rq = busiest;
>> +
>>         ld_moved = 0;
>>         if (busiest->nr_running > 1) {
>>                 /*
>> @@ -6670,8 +6707,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);
>>     more_balance:
>> @@ -7371,22 +7406,25 @@ 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.
>>    */
>> -static inline int nohz_kick_needed(struct rq *rq)
>> +static inline bool nohz_kick_needed(struct rq *rq)
>>   {
>>         unsigned long now = jiffies;
>>         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
>> @@ -7400,38 +7438,44 @@ 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)
>> -               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) &&
>> +                               check_cpu_capacity(rq, sd)) {
>> +                       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) { }
>
>