sched: add a new arch_sd_local_flags for sched_domain init

Date	Fri, 18 Oct 2013 13:52:15 +0200

The function arch_sd_local_flags is used to set flags in sched_domains
according to the platform architecture. A new flag SD_SHARE_POWERDOMAIN is
also created to reflect whether groups of CPUs in a sched_domain level can or
not reach different power state. As an example, the flag should be cleared at
CPU level if groups of cores can be power gated independently. This information
is used to decide if it's worth packing some tasks in a group of CPUs in order
to power gate the other groups instead of spreading the tasks. The default
behavior of the scheduler is to spread tasks across CPUs and groups of CPUs so
the flag is set into all sched_domains.

The cpu parameter of arch_sd_local_flags can be used by architecture to fine
tune the scheduler domain flags. As an example SD_SHARE_POWERDOMAIN flag can be
set differently for groups of CPUs according to DT information

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

Signed-off-by: Paul Reioux <reioux@gmail.com>
ARM: sched: clear SD_SHARE_POWERDOMAIN

Fri Oct 18 07:54:53 EDT 2013

The ARM platforms take advantage of packing tasks on few cores if the latters
can be powergated independantly. We use DT and the cpu topology descirption
to define at which level a core can be independantly powergated to the others
and the SD_SHARE_POWERDOMAIN will be set accordingly at MC and CPU sched_domain
level.

The power-gate properties should be added with the value 1 in cpu and cluster
node when then can power gate independantly from the other.

As an example of a quad cores system which can power gate each core
independantly, we should have a DT similar to the example below

	cpus {
		#address-cells = <1>;
		#size-cells = <0>;

	       cpu-map {
	               cluster0 {
				power-gate = <1>;
				core0 {
	                               cpu = <&cpu0>;
					power-gate = <1>;
				};
				core1 {
				        cpu = <&cpu1>;
					power-gate = <1>;
				};
				core2 {
					cpu = <&cpu2>;
					power-gate = <1>;
				};
				core3 {
					cpu = <&cpu3>;
					power-gate = <1>;
				};
			};
		};

	...

	};

Signed-off-by: Vincent Guittot <vincent.guittot at linaro.org>

Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: define pack buddy CPUs

Date	Fri, 18 Oct 2013 13:52:16 +0200

During the creation of sched_domain, we define a pack buddy CPU for each CPU
when one is available. We want to pack at all levels where a group of CPUs can
be power gated independently from others.
On a system that can't power gate a group of CPUs independently, the flag is
set at all sched_domain level and the buddy is set to -1. This is the default
behavior for all architectures.

On a dual clusters / dual cores system which can power gate each core and
cluster independently, the buddy configuration will be :

      | Cluster 0   | Cluster 1   |
      | CPU0 | CPU1 | CPU2 | CPU3 |
-----------------------------------
buddy | CPU0 | CPU0 | CPU0 | CPU2 |
If the cores in a cluster can't be power gated independently, the buddy
configuration becomes:

      | Cluster 0   | Cluster 1   |
      | CPU0 | CPU1 | CPU2 | CPU3 |
-----------------------------------
buddy | CPU0 | CPU1 | CPU0 | CPU0 |
Signed-off-by: Vincent Guittot <vincent.guittot@linaro.org>

Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: do load balance only with packing cpus

Date	Fri, 18 Oct 2013 13:52:17 +0200

The tasks will be scheduled only on the CPUs that participate to the packing
effort. A CPU participates to the packing effort when it is its own buddy.

For ILB, look for an idle CPU close to the packing CPUs whenever possible.
The goal is to prevent the wake up of a CPU which doesn't share the power
domain of the pack buddy CPU.

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

Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: add a packing level knob

Date	Fri, 18 Oct 2013 13:52:18 +0200

The knob is used to set an average load threshold that will be used to trig
the inclusion/removal of CPUs in the packing effort list.

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

Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: create a new field with available capacity

Date	Fri, 18 Oct 2013 13:52:19 +0200

This new field power_available reflects the available capacity of a CPU
unlike the cpu_power which reflects the current capacity.

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

Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: get CPU's activity statistic

Date	Fri, 18 Oct 2013 13:52:20 +0200

Monitor the activity level of each group of each sched_domain level. The
activity is the amount of cpu_power that is currently used on a CPU. We use
the runnable_avg_sum and _period to evaluate this activity 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_power in order to reflect the overload of
The cpu

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

backported to Linux 3.10

Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: move load idx selection in find_idlest_group

Date	Fri, 18 Oct 2013 13:52:21 +0200

load_idx is used in find_idlest_group but initialized in select_task_rq_fair
even when not used. The load_idx initialisation is moved in find_idlest_group
and the sd_flag replaces it in the function's args.

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

Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: Factor out code to should_we_balance()

Now checking whether this cpu is appropriate to balance or not
is embedded into update_sg_lb_stats() and this checking has no direct
relationship to this function. There is not enough reason to place
this checking at update_sg_lb_stats(), except saving one iteration
for sched_group_cpus.

In this patch, I factor out this checking to should_we_balance() function.
And before doing actual work for load_balancing, check whether this cpu is
appropriate to balance via should_we_balance(). If this cpu is not
a candidate for balancing, it quit the work immediately.

With this change, we can save two memset cost and can expect better
compiler optimization.

Below is result of this patch.

 * Vanilla *
   text	   data	    bss	    dec	    hex	filename
  34499	   1136	    116	  35751	   8ba7	kernel/sched/fair.o

 * Patched *
   text	   data	    bss	    dec	    hex	filename
  34243	   1136	    116	  35495	   8aa7	kernel/sched/fair.o

In addition, rename @balance to @continue_balancing in order to represent
its purpose more clearly.

Signed-off-by: Joonsoo Kim <iamjoonsoo.kim@lge.com>
[ s/should_balance/continue_balancing/g ]
Reviewed-by: Paul Turner <pjt@google.com>
[ Made style changes and a fix in should_we_balance(). ]
Signed-off-by: Peter Zijlstra <peterz@infradead.org>
Link: http://lkml.kernel.org/r/1375778203-31343-3-git-send-email-iamjoonsoo.kim@lge.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
sched: Fix load balancing performance regression in should_we_balance()

Commit 23f0d20 ("sched: Factor out code to should_we_balance()")
introduces the should_we_balance() function.  This function should
return 1 if this cpu is appropriate for balancing. But the newly
introduced code doesn't do so, it returns 0 instead of 1.

This introduces performance regression, reported by Dave Chinner:

                        v4 filesystem           v5 filesystem
3.11+xfsdev:            220k files/s            225k files/s
3.12-git                180k files/s            185k files/s
3.12-git-revert         245k files/s            247k files/s

You can find more detailed information at:

  https://lkml.org/lkml/2013/9/10/1

This patch corrects the return value of should_we_balance()
function as orignally intended.

With this patch, Dave Chinner reports that the regression is gone:

                        v4 filesystem           v5 filesystem
3.11+xfsdev:            220k files/s            225k files/s
3.12-git                180k files/s            185k files/s
3.12-git-revert         245k files/s            247k files/s
3.12-git-fix            249k files/s            248k files/s

Reported-by: Dave Chinner <dchinner@redhat.com>
Tested-by: Dave Chinner <dchinner@redhat.com>
Signed-off-by: Joonsoo Kim <iamjoonsoo.kim@lge.com>
Cc: Paul Turner <pjt@google.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Dave Chinner <david@fromorbit.com>
Link: http://lkml.kernel.org/r/20130910065448.GA20368@lge.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
sched: update the packing cpu list

Date	Fri, 18 Oct 2013 13:52:22 +0200

Use the activity statistics to update the list of CPUs that should be used
to hanlde the current system activity.

The cpu_power is updated for CPUs that don't participate to the packing
effort. We consider that their cpu_power is allocated to idleness as it
could be allocated by rt. So the cpu_power that remains available for cfs,
is set to min value (i.e. 1).

The cpu_power is used for a task that wakes up because a waking up task is
already taken into account in the current activity whereas we use the
power_available for a fork and exec because the task is not part of the current
activity.

In order to quickly found the packing starting point, we save information that
will be used to directly start with the right sched_group at the right
sched_domain level instead of running the complete update_packing_domain
algorithm each time we need to use the packing cpu list.

The sd_power_leader defines the leader of a group of CPU that can't be
powergated independantly. As soon as this CPU is used, all the CPU in the same
group will be used based on the fact that it doesn't worth to keep some cores
idle if they can't be power gated while one core in the group is running.
The sd_pack_group and sd_pack_domain are used to quickly check if a power
leader should be used in the packing effort

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

Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: init this_load to max in find_idlest_group

Date	Fri, 18 Oct 2013 13:52:23 +0200

Init this_load to max value instead of 0 in find_idlest_group.
If the local group is skipped because it doesn't have allowed CPUs, this_load
stays to 0,  no idlest group will be returned and the selected CPU will be a
not allowed one (which will be replaced in select_fallback_rq by a random
one). With a default value set to max, we will use the idlest group even if we
skip the local_group.

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

Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: add a SCHED_PACKING_TASKS config

Date	Fri, 18 Oct 2013 13:52:24 +0200

The SCHED_PACKING_TASKS config is used to enable the packing tasks mecanism

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

Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: create a statistic structure

Date	Fri, 18 Oct 2013 13:52:25 +0200

Create a statistic structure that will be used to share information with
other frameworks like cpuidle and cpufreq. This structure only contains the
current wake up latency of a core for now but could be extended with other
usefull information.

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

Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: differantiate idle cpu

Date	Fri, 18 Oct 2013 13:52:26 +0200

The cost for waking up of a core varies according to its current idle state.
This includes C-state and intermediate state when some sync between cores is
required to reach a deep C-state.
Waking up a CPU in a deep C-state for running a short task is not efficient
from both a power and a performance point of view. We should take into account
the wake up latency of an idle CPU when the scheduler looks for the best CPU
to use for a waking task.
The wake up latency of a CPU is computed into a load that can be directly
compared with task load and other CPUs load.

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

Backported to Linux 3.10

Signed-off-by: Paul Reioux <reioux@gmail.com>
cpuidle: set the current wake up latency

Date	Fri, 18 Oct 2013 13:52:27 +0200

Save the current wake up latency of a core. This latency is not always
the latency of a defined c-state but can also be an intermediate value
when a core is ready to shutdown (timer migration, cache flush ...) but
wait for the last core of the cluster to finalize the cluster power down.
This latter use case is not manage by the current version of the patch because
it implies that the cpuidle drivers set the wake up latency instead of the
cpuidle core.

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

Signed-off-by: Paul Reioux <reioux@gmail.com>