block: BFQ-v6r1 I/O sched for 3.4

BFQ is based on CFQ code, but it implements a more accurate scheduling policy. In brief, differently from CFQ, BFQ does not grant the disk to each process for a fixed time-slice, but until the process exhausts a previously assigned budget, measured in number of sectors. Budgets are scheduled with an internal budget scheduler, B-WF2Q+, a modified version of the WF2Q+ packet scheduler.
In more detail, in BFQ, as in CFQ, synchronous requests are collected in per-task queues, and asynchronous requests are collected in per-device (or, in case of hierarchical scheduling, per group) queues. When a new queue is created, it is assigned a budget, measured in number of sectors, to use when the queue itself is granted access to the disk. BFQ exclusively serves one queue at a time. When the underlying device driver asks for the next request to serve, BFQ selects the first request from the queue under service in C-LOOK order and returns it to the driver. The budget of the queue is decremented by the size of the request. As in CFQ, if a sync queue has no more requests to serve, but it has some budget left, the scheduler idles (i.e., it tells to the device driver that it has no requests to serve even if there are other backlogged queues) for a short period, waiting for a new request from the task associated to the queue. The queue under service goes on being served until one of the following conditions is met:

the idling timer expires while BFQ is idling to wait for the arrival of the next request from the task associated to the queue
the queue is spending too much time to consume its budget (budget timeout, see the timeout_* parameters below), or
the queue exhausts its budget, or
the queue is not sync and has no more requests to serve.
When the queue is deselected, it is assigned a new budget, computed as a function of which of the above events occurred. The next queue to serve is selected with B-WF2Q+, a modified version of the WF2Q+ packet scheduler. B-WF2Q+ schedules backlogged queues as a function of: their budgets, their weights and the service they have already received.

Working in the service domain and not in the time domain is what allows BFQ to distribute the disk throughput as desired, unconditionally and even if it fluctuates. In addition, the accurate service distribution of the internal B-WF2Q+ scheduler, guarantees tight delays with respect to the completion times that the requests would enjoy in an ideal perfectly-fair system.

The idea for reducing the latency for interactive and soft real-time processes (when low_latency is enabled) is just raising the weight of the associated queues. More details can be found here. An important point is that such an heuristics allows interactive and soft real-time queues to steal more throughput than their fair share to other queues. If the resulting loss of fairness is undesired (e.g., in a server system), it is certainly better to switch low_latency off.

When hierarchical scheduling is enabled, queues are collected in a tree of groups, and there is a distinct B-WFQ2+ scheduler on each non-leaf node. Leaf nodes are request queues as in the non-hierarchical case.

BFQ supports ioprio classes at each hierarchy level, enforcing a strict priority ordering among classes. This means that idle queues/groups are served only if there are no best effort queues/group in the same scheduler, and best effort queues/groups are served only if there are no real-time queues/groups.

Signed-off-by: Javelin <javelinanddart@gmail.com>

Conflicts:
	block/Kconfig.iosched
	block/bfq-cgroup.c
	block/bfq-ioc.c
	block/bfq-iosched.c
	block/bfq-sched.c
	block/bfq.h
Revert "block: BFQ-v6r1 I/O sched for 3.4"

This reverts commit 96c5b7459515462390fc940c65300aa04a7a51e8.
disable GENTLE_FAIR_SLEEPERS
hrtimer: Introduce effective timer slack

task_get_effective_timer_slack() returns timer slack value to be used
to configure per-task timers. It can be equal or higher than task's
timer slack value.

For now task_get_effective_timer_slack() returns timer_slack_ns of the
task. Timer slack cgroup controller will implement a bit more
sophisticated logic.

Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>
Signed-off-by: Cristoforo Cataldo <cristoforo.cataldo@gmail.com>
hrtimer: Implement PR_GET_EFFECTIVE_TIMERSLACK

PR_GET_EFFECTIVE_TIMERSLACK allows process to know its effective timer
slack value.

Signed-off-by: Kirill A. Shutemov <kirill@shutemov.name>
Signed-off-by: Cristoforo Cataldo <cristoforo.cataldo@gmail.com>
Signed-off-by: Javelin <javelinanddart@gmail.com>

Conflicts:
	include/linux/prctl.h
kernel: cgroup_timer_slack: Adaptations for 3.4 kernel

Signed-off-by: Cristoforo Cataldo <cristoforo.cataldo@gmail.com>
Signed-off-by: Javelin <javelinanddart@gmail.com>

Conflicts:
	kernel/cgroup_timer_slack.c
kernel: cgroup_timer_slack: Dynamic management of timer slack

This feature allows to use different minimal timer slack values and to
dynamically manage them when the system has been resumed (it's active)
or when has been suspended.

A new file is provided in addition to the two files provided by the
original timer slack controller:
- "timer_slack.min_slack_suspend_ns" is the minimal timer slack value
  to use when the system is suspended (screen off)

For further info, please refers to the timer slack documentation:
Documentation/cgroupd/timer_slack.txt

Signed-off-by: Cristoforo Cataldo <cristoforo.cataldo@gmail.com>
Signed-off-by: Javelin <javelinanddart@gmail.com>

Conflicts:
	Documentation/cgroups/timer_slack.txt
	init/Kconfig
Voltage Control: initial voltage control for 8960 krait

Signed-off-by: Javelin <javelinanddart@gmail.com>

Conflicts:
	arch/arm/mach-msm/Kconfig
	arch/arm/mach-msm/acpuclock-krait.c
Merge branch 'lollipop' of github.com:javelinanddart/android_kernel_aosp_ville into lollipop