sched: Tighten controls for tasks spillover to idle cluster

Several conditions can cause an idle cluster to pick up load from a
busy cluster. One such condition is when busy cluster has number of
tasks that exceeds its capacity (or number of cpus). This patch
extends that condition to consider small and big tasks on a cluster.
Too many "small" tasks should not cause them to spill over to another
idle cluster. Like-wise presence of big tasks should be considered
by a cluster to pick up load from another another cluster with lower
capacity.

Change-Id: I0545bf2989c37217d84ed18756c6f5c8946d5ae5
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: Extend /proc/sched_debug with additional information

Provide additional information in /proc/sched_debug for every cpu.
This will be a valuable debug aid.

Change-Id: If22ee530e880cd21719242be7bc2c41308ad4186
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: Add additional ftrace events

This patch adds two ftrace events:

sched_task_load -> records information of a task, such as scaled demand
sched_cpu_load  -> records information of a cpu, such as nr_running,
		   nr_big_tasks etc

This will be useful to debug HMP related task placement decisions by
scheduler.

Change-Id: If91587149bcd9bed157b5d2bfdecc3c3bf6652ff
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: Provide scaled load information for tasks in /proc

Extend "sched" file in /proc for every task to provide information on
scaled load statistics and percentage-scaled based load (load_avg) for
a task. This will be valuable debug aid.

Change-Id: I6ee0394b409c77c7f79f5b9ac560da03dc879758
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: Reset decay_count when task is enqueued

A non-zero and positive decay_count indicates the time when a task
went to sleep and thus was removed from its cfs_rq.
cfs_rq->blocked_load_avg tracks load of such "blocked" tasks.
cfs_rq->blocked_load_avg is decayed over time and in turn signifies
decay of (blocked) tasks load. cfs_rq->decay_counter represents time
when blocked_load_avg was last decayed. cfs_rq->decay_counter is
derived from rq->clock_task, which can be different for each cpu.
When tasks go to sleep, their decay_count is set to
cfs_rq->decay_counter.

When task wakeup from sleep, its (new decayed) load_avg needs to be
removed from cfs_rq->blocked_load_avg (as tasks is no longer blocked).
Amount of decay for task's load_avg is defined by its sleep time,
roughly derived as (cfs_rq->decay_counter - se->decay_count). This is
accomplished in __synchronize_entity_decay().

Once task's load_avg is decayed and is subtracted from
cfs_rq->blocked_load_avg, decay_count should be reset to 0, to
indicate that task is no longer sleeping and its load_avg has been
synchronized with decay of blocked_load_avg. A zero decay count thus
signifies that a task is on runqueue and its load_avg has been decayed
and synchronized with that of cfs_rq->blocked_load_avg.

A negative decay_count on the other hand signifies a task that is
being migrated across cpus during wakeup. Lets say task went to sleep
on CPU0 and is waking on CPU1. In this case, task's load_avg needs to
be decayed first (over its sleep time derived as
cfs_rq0->decay_counter - se->decay_count), then subtracted from
cfs_rq0->blocked_load_avg and finally task's load metrics
(runnable_avg_sum) needs to be decayed over its sleep time. As task's
sleep_time is deduced from (rq->clock_task -
se->avg.last_runnable_update), and since se->avg.last_runnable_update
is in reference to CPU0's clock_task, it would be inappropriate to
deduce task's sleep time going by CPU1's rq->clock_task. Thus, in this
case, when task is migrated to a different cpu at wakeup time, its
decay_count is set to negative sleep time derived as
- (CPU0 cfs_rq->decay_counter - se->avg.decay_count). This information
is used during enqueue of task on CPU1 to adjust task's
se->avg.last_runnable_update as (cpu1 rq->clock_task -
(-se->avg.decay_count). This will let task's runnable_avg_sum to be
decayed correctly over its sleep time by referencing CPU1's
rq->clock_task and task's se->avg.last_runnable_update.

The bug that currently exists is when task wakes up from a "short"
sleep (couple of ms), is woken on the same cpu where it last ran and
subsequently migrated.

t0 -> task A went to sleep on cpu0.
	 A->se.avg.decay_count = cpu0 cfs_rq->decay_counter = t0

t1 -> task A woke up from sleep. cpu0's cfs_rq->decay_counter is still
      t0. Because of this, __synchronize_entity_decay() does nothing.
      It also returns *without* resetting task's decay_count

t2  ->  CPU0's blocked_load_avg is decayed. cfs_rq->decay_counter = t2

t3 -> Task A is migrated from CPU0 to CPU1. migrate_task_rq_fair()
      assumes that this is case of migration during wakeup as A's
      decay_count is non-zero and positive. It then deduces task's
      sleep time as (t2-t0) and decays its load_avg over that sleep
      time. Task's decay_count is set as -(t2-t0). When task is later
      enqueued on CPU1, task's load metrics (runnable_avg_sum) is
      decayed to account for its "sleep" interval of (t2-t0), which
      is *wrong* and further results in inaccurate load information
      for the task.

Fix for this is to have __synchronize_entity_decay() reset decay_count
even when it deduces zero sleep time for task.

Change-Id: I1016ecb148d62ff15ed698a5cca1a06afb73151f
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: Provide tunable to switch between PELT and window-based stats

Provide a runtime tunable to switch between using PELT-based load
stats and window-based load stats. This will be needed for runtime
analysis of the two load tracking schemes.

Change-Id: I018f6a90b49844bf2c4e5666912621d87acc7217
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: Switch to windows based load stats by default

Set window-based load stats to be the default mechanism under which
tasks get classified (as big/small) and which will drive frequency
demand for tasks.  sched_ravg_window kernel parameter can be used to
change this default setting to use PELT (per-entity load tracking)
scheme instead.

Change-Id: I626110daa0bb2b53172bedea829d31877255ceaa
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: add notifier for cross-cpu migrations

Originally from Jeremy Fitzhardinge.

Acked-by: Ingo Molnar <mingo@redhat.com>
Signed-off-by: Marcelo Tosatti <mtosatti@redhat.com>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: move definition of update_task_ravg()

set_task_cpu() will need to call update_task_ravg(). Move up
definition to make it easy.

Change-Id: I95c1c9e009bd1805f28708e8d6fd3b7b2166410e
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: window-stats: update during migration and earlier at wakeup

During migrations accounting needs to be done in set_task_cpu() to
subtract the task activity from the source CPU and add it to the
destination CPU. This accounting will require that the task's window
based load statistics be up to date.

Unfortunately, the window-based statistics cannot always be updated in
set_task_cpu() because they are already being updated in the wakeup
path. We cannot update the statistics solely in the wakeup path
because not all wakeups are migrations. Those non-migrating wakeups
will not enter set_task_cpu().

To ensure the window-based stats are always updated for both wakeup
migrations and regular migrations, they are updated earlier in the
wakeup path, and also updated in set_task_cpu if the task is already
runnable (this ensures it is not a wakeup migration, but a regular
migration).

Change-Id: Ib246028741d0be9bb38ce93679d6e6ba25b10756
Signed-off-by: Steve Muckle <smuckle@codeaurora.org>
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: window-stats: Do not account wait time

Task load statistics are used for two purposes : cpu frequency
management and placement. Task's load can't be accurately judged by
its wait time. For ex: a task could have waited for 10ms and when given
opportunity to run, could just execute for 1ms. Accounting for 11ms as
task's demand could be over-stating its needs in this example. For
now, remove wait time from task demand and instead let task load be
derived from its actual exec time. This may need to become a tunable
feature.

Change-Id: I47e94c444c6b44c3b0810347287d50f1ee685038
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: window-stats: synchronize windows across cpus

Synchronizing windows across cpus for task load measurements
simplifies cpu busy time accounting during migrations. For task
migrations, its usage in current window can be carried over to its new
cpu. This lets cpufreq governor see a correct picture of cpu busy time
that is not affected by migrations.

This patch lines up windows across cpus. One of the cpu, sync_cpu,
serves as a reference for all others. During bootup sync_cpu would
initialize its window_start (from its sched_clock()). Other cpus will
synchronize their window_start in reference to sync_cpu. This patch
assumes synchronous sched_clock() across cpus and may need some change
to address architectures which do not provide such synchronized
sched_clock().

Change-Id: I13381389a72f5f9f85cc2446401d493a55c78ab7
Signed-off-by: Steve Muckle <smuckle@codeaurora.org>
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: window-stats: add prev_window counter per-task

Currently windows where tasks had no execution time are ignored.
However accurate accounting of cpu busy time that factors in migration
would need to know actual utilization of a task in the window previous
to the latest one. This would help scheduler guide cpufreq governor on
busy time per-cpu that is not subject to migration induced errors.

Change-Id: I5841b1732c83e83d69002139de3bdb93333ce347
Signed-off-by: Steve Muckle <smuckle@codeaurora.org>
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: window-stats: Add aggregated runqueue windowed stats

Add counters per-cpu to track its busy time in the latest window and
one previous to that. This would be needed to track accurate busy time
per-cpu that accounts for migrations. Basically once a task migrates,
its execution time in current window is migrated as well to new cpu.

The idle task's runtime is not accounted since it should not count
towards runqueue busy time.

Change-Id: I4014dd686f95dbbfaa4274269bc36ed716573421
Signed-off-by: Steve Muckle <smuckle@codeaurora.org>
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: window-stats: adjust RQ curr, prev sums on task migration

Adjust cpu's busy time in its recent and previous window upon task
migration. This would enable scheduler to provide better inputs to
cpufreq governor on a cpu's busy time in a given window.

Change-Id: Idec2ca459382e9f46d882da3af53148412d631c6
Signed-off-by: Steve Muckle <smuckle@codeaurora.org>
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: add sched_get_busy, sched_set_window APIs

sched_get_busy() returns the busy time of a cpu during the most
recent completed window.
sched_set_window() will set window size and aligns windows across
all CPUs.

Change-Id: Ic53e27f43fd4600109b7b6db979e1c52c7aca103
Signed-off-by: Steve Muckle <smuckle@codeaurora.org>
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: Extend update_task_ravg() to accept wallclock as argument

This will make it easier to account interrupt time on a cpu,
introduced in a subsequent patch.

Change-Id: I0e1fb5255c280ca374fd255e7fc19d5de9f8b045
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: add power aware scheduling sysctl

The sched_enable_power_aware sysctl will control whether
or not scheduling decisions are influenced by the power
consumption of individual CPUs.

Change-Id: I312f892cf76a3fccc4ecc8aa6703908b205267f0
Signed-off-by: Steve Muckle <smuckle@codeaurora.org>
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: add hook for platform-specific CPU power information

To enable power-aware scheduling, provide a hook/infrastructure
for platforms to communicate CPU power requirements for each
supported CPU frequency. This information is then used to estimate
the cost of running a task on a given CPU.

Currently, an assumption is made that the task will be running
by itself on the CPU. Given the current policy tries to spread
tasks as much as possible this assumption should not be too
far off.

Change-Id: I19f1fa760a0d43222d2880f8aec0508c468b39bb
Signed-off-by: Steve Muckle <smuckle@codeaurora.org>
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: run idle_balance() on most power-efficient CPU

When a CPU goes idle, it checks to see whether it can pull any load
from other busy CPUs. The CPU going idle may not be the most
power-efficient idle CPU in the system however.

This patch causes the CPU going idle to check to see whether
there is a more power-efficient idle CPU within the same
lowest sched domain. If there is, then it runs the load balancer
on behalf of that CPU instead of itself.

Since it is unknown at this point what task load would be pulled,
a frequency must be assumed for this in order to do a comparison
of CPU power consumption. The maximum freqeuncy supported by all
CPUs is used for this.

Change-Id: I5eedddc1f7d10df58ecd358f37dba563eeecf4fc
Signed-off-by: Steve Muckle <smuckle@codeaurora.org>
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>