block: cgroups, kconfig, build bits for BFQ-v7r6-3.10.8+

Update Kconfig.iosched and do the related Makefile changes to include
kernel configuration options for BFQ. Also add the bfqio controller
to the cgroups subsystem.

Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
Signed-off-by: flar2 <asegaert@gmail.com>
block: introduce the BFQ-v7r6 I/O sched for 3.10.8+

Add the BFQ-v7r6 I/O scheduler to 3.10.8+.
The general structure is borrowed from CFQ, as much of the code for
handling I/O contexts Over time, several useful features have been
ported from CFQ as well (details in the changelog in README.BFQ). A
(bfq_)queue is associated to each task doing I/O on a device, and each
time a scheduling decision has to be made a queue is selected and served
until it expires.

    - Slices are given in the service domain: tasks are assigned
      budgets, measured in number of sectors. Once got the disk, a task
      must however consume its assigned budget within a configurable
      maximum time (by default, the maximum possible value of the
      budgets is automatically computed to comply with this timeout).
      This allows the desired latency vs "throughput boosting" tradeoff
      to be set.

    - Budgets are scheduled according to a variant of WF2Q+, implemented
      using an augmented rb-tree to take eligibility into account while
      preserving an O(log N) overall complexity.

    - A low-latency tunable is provided; if enabled, both interactive
      and soft real-time applications are guaranteed a very low latency.

    - Latency guarantees are preserved also in the presence of NCQ.

    - Also with flash-based devices, a high throughput is achieved
      while still preserving latency guarantees.

    - BFQ features Early Queue Merge (EQM), a sort of fusion of the
      cooperating-queue-merging and the preemption mechanisms present
      in CFQ. EQM is in fact a unified mechanism that tries to get a
      sequential read pattern, and hence a high throughput, with any
      set of processes performing interleaved I/O over a contiguous
      sequence of sectors.

    - BFQ supports full hierarchical scheduling, exporting a cgroups
      interface.  Since each node has a full scheduler, each group can
      be assigned its own weight.

    - If the cgroups interface is not used, only I/O priorities can be
      assigned to processes, with ioprio values mapped to weights
      with the relation weight = IOPRIO_BE_NR - ioprio.

    - ioprio classes are served in strict priority order, i.e., lower
      priority queues are not served as long as there are higher
      priority queues.  Among queues in the same class the bandwidth is
      distributed in proportion to the weight of each queue. A very
      thin extra bandwidth is however guaranteed to the Idle class, to
      prevent it from starving.

Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
Signed-off-by: flar2 <asegaert@gmail.com>
block, bfq: add Early Queue Merge (EQM) to BFQ-v7r6 for 3.10.8+

A set of processes may happen  to  perform interleaved reads, i.e.,requests
whose union would give rise to a  sequential read  pattern.  There are two
typical  cases: in the first  case,   processes  read  fixed-size chunks of
data at a fixed distance from each other, while in the second case processes
may read variable-size chunks at  variable distances. The latter case occurs
for  example with  QEMU, which splits the  I/O generated  by the  guest into
multiple chunks,  and lets these chunks  be served by a  pool of cooperating
processes,  iteratively  assigning  the  next  chunk of  I/O  to  the first
available  process. CFQ  uses actual  queue merging  for the  first type of
rocesses, whereas it  uses preemption to get a sequential  read pattern out
of the read requests  performed by the second type of  processes. In the end
it uses  two different  mechanisms to  achieve the  same goal: boosting the
throughput with interleaved I/O.

This patch introduces  Early Queue Merge (EQM), a unified mechanism to get a
sequential  read pattern  with both  types of  processes. The  main idea is
checking newly arrived requests against the next request of the active queue
both in case of actual request insert and in case of request merge. By doing
so, both the types of processes can be handled by just merging their queues.
EQM is  then simpler and  more compact than the  pair of mechanisms used in
CFQ.

Finally, EQM  also preserves the  typical low-latency properties of BFQ, by
properly restoring the weight-raising state of  a queue when it gets back to
a non-merged state.

Signed-off-by: Mauro Andreolini <mauro.andreolini@unimore.it>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
Signed-off-by: flar2 <asegaert@gmail.com>
Fix version name

Signed-off-by: flar2 <asegaert@gmail.com>
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 at linaro.org>
Signed-off-by: flar2 <asegaert@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: flar2 <asegaert@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 at linaro.org>
Signed-off-by: flar2 <asegaert@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 at linaro.org>
Signed-off-by: flar2 <asegaert@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 at linaro.org>
Signed-off-by: flar2 <asegaert@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 at linaro.org>
Signed-off-by: flar2 <asegaert@gmail.com>
sched: get CPU's activity statistic

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>
Signed-off-by: flar2 <asegaert@gmail.com>
sched: move load idx selection in find_idlest_group

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: flar2 <asegaert@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>
Signed-off-by: flar2 <asegaert@gmail.com>
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>
Signed-off-by: flar2 <asegaert@gmail.com>
sched: update the packing cpu list

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: flar2 <asegaert@gmail.com>
sched: init this_load to max in find_idlest_group

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: flar2 <asegaert@gmail.com>
sched: add a SCHED_PACKING_TASKS config

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: flar2 <asegaert@gmail.com>
sched: create a statistic structure

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: flar2 <asegaert@gmail.com>
sched: differantiate idle cpu

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>
Signed-off-by: flar2 <asegaert@gmail.com>
cpuidle: set the current wake up latency

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>

Conflicts:

	drivers/cpuidle/cpuidle.c
Signed-off-by: flar2 <asegaert@gmail.com>