cpufreq: interactive: New 'interactive' governor

This governor is designed for latency-sensitive workloads, such as
interactive user interfaces.  The interactive governor aims to be
significantly more responsive to ramp CPU quickly up when CPU-intensive
activity begins.

Existing governors sample CPU load at a particular rate, typically
every X ms.  This can lead to under-powering UI threads for the period of
time during which the user begins interacting with a previously-idle system
until the next sample period happens.

The 'interactive' governor uses a different approach. Instead of sampling
the CPU at a specified rate, the governor will check whether to scale the
CPU frequency up soon after coming out of idle.  When the CPU comes out of
idle, a timer is configured to fire within 1-2 ticks.  If the CPU is very
busy from exiting idle to when the timer fires then we assume the CPU is
underpowered and ramp to MAX speed.

If the CPU was not sufficiently busy to immediately ramp to MAX speed, then
the governor evaluates the CPU load since the last speed adjustment,
choosing the highest value between that longer-term load or the short-term
load since idle exit to determine the CPU speed to ramp to.

A realtime thread is used for scaling up, giving the remaining tasks the
CPU performance benefit, unlike existing governors which are more likely to
schedule rampup work to occur after your performance starved tasks have
completed.

The tuneables for this governor are:
/sys/devices/system/cpu/cpufreq/interactive/min_sample_time:
	The minimum amount of time to spend at the current frequency before
	ramping down. This is to ensure that the governor has seen enough
	historic CPU load data to determine the appropriate workload.
	Default is 80000 uS.
/sys/devices/system/cpu/cpufreq/interactive/go_maxspeed_load
	The CPU load at which to ramp to max speed.  Default is 85.

Change-Id: Ib2b362607c62f7c56d35f44a9ef3280f98c17585
Signed-off-by: Mike Chan <mike@android.com>
Signed-off-by: Todd Poynor <toddpoynor@google.com>
Bug: 3152864

Conflicts:
	drivers/cpufreq/Kconfig
cpufreq interactive governor: event tracing

Change-Id: Ic13614a3da2faa2d4bd215ca3eb7191614f0cf66
Signed-off-by: Todd Poynor <toddpoynor@google.com>

Conflicts:
	drivers/cpufreq/cpufreq_interactive.c
	include/trace/events/cpufreq_interactive.h
cpufreq: interactive: apply intermediate load to max speed not current

Evaluate spikes in load (below go_hispeed_load) against the maximum
speed supported by the device, not the current speed (which tends to
make it too difficult to raise speed to intermediate levels until
very busy).

Change-Id: Ib937006abf8bedb60891a739acd733e89b732ae0
Signed-off-by: Todd Poynor <toddpoynor@google.com>
cpufreq: interactive: set at least hispeed when above hispeed load

If load is above go_hispeed_load, always go to at least hispeed_freq,
even when reducing speed from a higher speed, not just when jumping
up from minimum speed.  Avoids running at a lower than intended
speed after a burst of even higher load.

Change-Id: I5b9d2a15ba25ce609b21bac7c724265cf6838dee
Signed-off-by: Todd Poynor <toddpoynor@google.com>
cpufreq: interactive: don't drop speed if recently at higher load

Apply min_sample_time to the last time the current target speed
was originally requested or re-validated as appropriate for the
current load, not to the time since the current speed was
originally set.  Avoids periodic dips in speed during bursty
loads.

Change-Id: I250bda657985de60373f9897cc41f480664d51a1
Signed-off-by: Todd Poynor <toddpoynor@google.com>
cpufreq: interactive: configurable delay before raising above hispeed

Change-Id: I4d6ac40b23a3790d48e30c37408284e9f955e8fa
Signed-off-by: Todd Poynor <toddpoynor@google.com>
cpufreq: interactive: adjust code and documentation to match

Change-Id: If59c668d514a29febe5c35404fd9d01df8548eb1
Signed-off-by: Todd Poynor <toddpoynor@google.com>

Conflicts:
	Documentation/cpu-freq/governors.txt
cpufreq: interactive: base hispeed bump on target freq, not actual

For systems that set a common speed for all CPUs, checking current
speed here could bypass the intermediate hispeed bump decision for
this CPU when another CPU was already at hispeed.  This could
result in an overly high setting (for all CPUs) in situations
where all CPUs were about to drop to load levels that map to
hispeed or below.

Change-Id: I186f23dcfc5e2b6336cab8b0327f0c8a9a4482bc
Signed-off-by: Todd Poynor <toddpoynor@google.com>
cpufreq: interactive: Separate speed target revalidate time and initial set time

Allow speed drop after min_sample_time elapses from last time
the current speed was last re-validated as appropriate for
current load / input boost.

Allow speed bump after min_sample_time (or above_hispeed_delay)
elapses from the time the current speed was originally set.

Change-Id: Ic25687a7a53d25e6544c30c47d7ab6f27a47bee8
Signed-off-by: Todd Poynor <toddpoynor@google.com>
cpufreq: interactive: Boost frequency on touchscreen input

Based on previous patches by Tero Kristo <tero.kristo@nokia.com>,
Brian Steuer <bsteuer@codeaurora.org>,
David Ng <dave@codeaurora.org>,
Antti P Miettinen <amiettinen@nvidia.com>, and
Thomas Renninger <trenn@suse.de>

Change-Id: Ic55fedcf6f9310f43a7022fb88e23b0392122769
Signed-off-by: Todd Poynor <toddpoynor@google.com>
cpufreq: interactive: remove unused target_validate_time_in_idle

Change-Id: I37c5085b91318242612440dfd775ad762996612f
Signed-off-by: Todd Poynor <toddpoynor@google.com>
cpufreq: interactive: Add sysfs boost interface for hints from userspace

The explicit hint on/off version.

Change-Id: Ibf62b6d45bf6fb8c9c055b9bdaf074ce9374c04f
Signed-off-by: Todd Poynor <toddpoynor@google.com>
cpufreq: interactive: set floor for boosted speed

Allow speed to drop to flooor frequency but not below, don't pin
to speed at last boost.

Change-Id: I0147c2b7a2e61ba16820605af6baaf09570be787
Signed-off-by: Todd Poynor <toddpoynor@google.com>
cpufreq: interactive: add boost pulse interface

Change-Id: Icf1e86d2065cc8f0816ba9c6b065eb056d4e8249
Signed-off-by: Todd Poynor <toddpoynor@google.com>
cpufreq-interactive: Compile fixup

Looks like AOSP has a compile bug. Fix it up.

Signed-off-by: John Stultz <john.stultz@linaro.org>
cpufreq: interactive: restart above_hispeed_delay at each hispeed load

Change-Id: I2e5b91d45e8806b0ab94ca2301ed671c9af9ab13
Signed-off-by: Todd Poynor <toddpoynor@google.com>
cpufreq: interactive: fixup trace of string params

Change-Id: Iac47f62437e61b13724afbbf9df1a0729f58f236
Signed-off-by: Todd Poynor <toddpoynor@google.com>
mach-tegra: board-m7.c: Fixing #endif location necessary to compile without phase 2 ondemand
From 18bc095e952d31d5e07b88b8b89fb2ae8c3048ad Mon Sep 17 00:00:00 2001
From: Arianna Avanzini <avanzini.arianna@gmail.com>
Date: Sat, 4 Feb 2012 10:55:51 +0100
Subject: [PATCH 1/2] block: cgroups, kconfig, build bits for BFQ-v5r1-3.4

Update Kconfig.iosched to include kernel configuration options
for BFQ. Add a Kconfig option and do the related Makefile changes
to compile the scheduler. Also let the cgroups subsystem know about
the BFQ I/O controller.

Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>

Conflicts:
	include/linux/cgroup_subsys.h
rom 2ebfcb6f325e27261c80a5c3b3a9e9e5ba3749a8 Mon Sep 17 00:00:00 2001
From: Arianna Avanzini <avanzini.arianna@gmail.com>
Date: Sun, 5 Feb 2012 01:04:27 +0100
Subject: [PATCH 2/2] block: introduce the BFQ-v5r1 I/O sched for 3.4

Add the BFQ-v5r1 I/O scheduler to 3.4.
The general structure is borrowed from CFQ, as much code. A (bfq_)queue is
associated to each task doing I/O on a device, and each time a scheduling
decision has to be taken a queue is selected and it is 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 very low latency.

    - Latency guarantees are preserved also in presence of NCQ.

    - High throughput with flash-based devices, while still preserving
      latency guarantees.

    - Useful features borrowed from CFQ: cooperating-queues merging (with
      some additional optimizations with respect to the original CFQ version),
      static fallback queue for OOM.

    - BFQ supports full hierarchical scheduling, exporting a cgroups
      interface.  Each node has a full scheduler, so each group can
      be assigned its own ioprio and an ioprio_class.

    - If the cgroups interface is used, weights can be explictly assigned,
      otherwise ioprio values are mapped to weights using 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 weights 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>