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/cpufreq_interactive.c
block: Adding ROW scheduling algorithm

This patch adds the implementation of a new scheduling algorithm - ROW.
The policy of this algorithm is to prioritize READ requests over WRITE
as much as possible without starving the WRITE requests.
The requests are kept in queues according to their priority. The dispatch
is done in a Round Robin manner with a different slice for each queue.
READ request queues get bigger dispatch quantum than the write requests.

Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>

block: Add support for reinsert a dispatched req

Add support for reinserting a dispatched request back to the
scheduler's internal data structures.
This capability is used by the device driver when it chooses to
interrupt the current request transmission and execute another (more
urgent) pending request. For example: interrupting long write in order
to handle pending read. The device driver re-inserts the
remaining write request back to the scheduler, to be rescheduled
for transmission later on.

Add API for verifying whether the current scheduler
supports reinserting requests mechanism. If reinsert mechanism isn't
supported by the scheduler, this code path will never be activated.

Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>

block: Add API for urgent request handling

This patch add support in block & elevator layers for handling
urgent requests. The decision if a request is urgent or not is taken
by the scheduler. Urgent request notification is passed to the underlying
block device driver (eMMC for example). Block device driver may decide to
interrupt the currently running low priority request to serve the new
urgent request. By doing so READ latency is greatly reduced in read&write
collision scenarios.

Note that if the current scheduler doesn't implement the urgent request
mechanism, this code path is never activated.

Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>

block: compile ROW statically into the kernel

ROW is a new scheduling algorithm. Similar to the existing scheduling
algorithms it should be compiled to the kernel statically giving the user
the ability to switch to it without kernel recompilation.

Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>

row: Adding support for reinsert already dispatched req

Add support for reinserting already dispatched request back to the
schedulers internal data structures.
The request will be reinserted back to the queue (head) it was
dispatched from as if it was never dispatched.

Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>

row: Add support for urgent request handling

This patch add support for handling urgent requests.
ROW queue can be marked as "urgent". If an urgent queue was
un-served in a previous dispatch cycle and a request was added
to it - it will trigger issuing urgent request to the device driver.

Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>

block: row: Add some debug information on ROW queues

1. Add a counter for number of requests on queue.
2. Add function to print queues status (number requests
   currently on queue and number of already dispatched requests
   in current dispatch cycle).

Change-Id: I1e98b9ca33853e6e6a8ddc53240f6cd6981e6024
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>

block: row: Insert dispatch_quantum into struct row_queue

There is really no point in keeping the dispatch quantum
of a queue outside of it. By inserting it to the row_queue
structure we spare extra level in accessing it.

Change-Id: Ic77571818b643e71f9aafbb2ca93d0a92158b199
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>

block: row: fix sysfs functions - idle_time conversion

idle_time was updated to be stored in msec instead of jiffies.
So there is no need to convert the value when reading from user or
displaying the value to him.

Change-Id: I58e074b204e90a90536d32199ac668112966e9cf
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>

block: row: Aggregate row_queue parameters to one structure

Each ROW queues has several parameters which default values are defined
in separate arrays. This patch aggregates all default values into one
array.
The values in question are:
 - is idling enabled for the queue
 - queue quantum
 - can the queue notify on urgent request

Change-Id: I3821b0a042542295069b340406a16b1000873ec6
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
cpufreq interactive governor save/restore IRQs around cpumask spinlocks

Need to use irqsave/restore spin locking for cpumasks since these
are accessed in timers and in thread context.

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

Conflicts:
	drivers/cpufreq/cpufreq_interactive.c
cpufreq interactive governor: fix crash on CPU shutdown

Don't reference the saved copy of the CPU's cpufreq policy
pointer after the governor has been stopped for the CPU.

When the governor is stopped for a CPU:

* Use del_timer_sync() to wait for a currently-running timer
function to stop.

* Delete the timer when the governor is stopped for the
associated CPU, not when the last CPU is stopped.

* Flush any speed down work ongoing.

* Reset the timestamp that is used to tell if the timer function
has had a chance to run since last idle exit.

Check the governor enabled flag for the CPU before re-arming the
timer from within the timer function and at idle exit (in case
stopping the governor at runtime).

Check the governor enabled flag for the CPU in the worker
function and thread before using the policy pointer.  (There is
still a tiny window in the thread that needs more work to close.)

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

Conflicts:
	drivers/cpufreq/cpufreq_interactive.c
cpufreq interactive: support shared CPU scaling

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

Conflicts:
	drivers/cpufreq/cpufreq_interactive.c
cpufreq interactive: support shared CPU scaling

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

Conflicts:
	drivers/cpufreq/cpufreq_interactive.c
cpufreq: interactive: remove debug trace code

Remove debug trace code in preparation of upstreaming

Change-Id: I0905885e75031f5e9d7cb06878fb68c1fd06d4fe
Signed-off-by: Allen Martin <amartin@nvidia.com>

Conflicts:
	drivers/cpufreq/cpufreq_interactive.c