sched: Make scheduler aware of cpu frequency state

Capacity of a cpu (how much performance it can deliver) is partly
determined by its frequency (P) state, both current frequency as well
as max frequency it can reach.  Knowing frequency state of cpus will
help scheduler optimize various functions such as tracking every
task's cpu demand and placing tasks on various cpus.

This patch has scheduler registering for cpufreq notifications to
become aware of cpu's frequency state. Subsequent patches will make
use of derived information for various purposes, such as task's scaled
load (cpu demand) accounting and task placement.

Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: window-based load stats for tasks

Provide a metric per task that specifies how cpu bound a task is. Task
execution is monitored over several time windows and the fraction of
the window for which task was found to be executing or wanting to run
is recorded as task's demand. Windows over which task was sleeping are
ignored. We track last 5 recent windows for every task and the maximum
demand seen in any of the previous 5 windows (where task had some
activity) drives freq demand for every task.

A per-cpu metric (rq->cumulative_runnable_avg) is also provided which
is an aggregation of cpu demand of all tasks currently enqueued on it.
rq->cumulative_runnable_avg will be useful to know if cpu frequency
will need to be changed to match task demand.

Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
cpufreq: cpu-boost: Use hotplug thread infrastructure

Before this patch, thread migration ran in uninterruptible threads.
Use the relatively new hotplug thread infrastructure with parked
threads to reduce cpu load (x4).

Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
cpufreq: cpu-boost: Introduce scheduler assisted load based syncs

Previously, on getting a migration notification cpu-boost changed
the scaling min of the destination frequency to match that of the
source frequency or sync_threshold whichever was minimum.

If the scheduler migration notification is extended with task load
(cpu demand) information, the cpu boost driver can use this load to
compute a suitable frequency for the migrating task. The required
frequency for the task is calculated by taking the load percentage
of the max frequency and no sync is performed if the load is less
than a particular value (migration_load_threshold).This change is
beneficial for both perf and power as demand of a task is taken into
consideration while making cpufreq decisions and unnecessary syncs
for lightweight tasks are avoided.

The task load information provided by scheduler comes from a
window-based load collection mechanism which also normalizes the
load collected by the scheduler to the max possible frequency
across all CPUs.

Signed-off-by: Rohit Gupta <rohgup@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
cpufreq: cpu-boost: Handle wakeup hints received for foreground tasks

A previous change modifies the notification conditions in the scheduler
to call the notifier chain even on foreground_thread wakeups for tasks
having load more than a threshold value.

If load_based_syncs is turned OFF then we do not need to perform
cpu boost for wakeup hints for foreground tasks from scheduler

Signed-off-by: Rohit Gupta <rohgup@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
cpufreq: cpu-boost: Consider only task load to decide on sync frequency

Currently we take the maximum between the source CPU frequency and
the calculated frequency based on the migrating task load to decide on
the frequency to sync the destination CPU to. This was done to handle
short bursts in workloads of tasks which migrated immediately after
causing a ramp up on the source CPU. Since their load history wasn't
high enough, the destination CPU synced to a lower frequency which
wasn't sufficient for the spike in workload.

But as such cases are rare, taking the higher of source and calculated
frequency can lead to destination CPU unnecessarily spending a
considerable amount of time at higher frequencies which in turn can
hurt power.

With this change we make sure only the migrating task load is used
to calculate the sync frequency for destination CPU when load based
syncing is enabled.

Signed-off-by: Girish Ghongdemath <girishsg@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: Call the notify_on_migrate notifier chain for wakeups as well

Add a change to send notify_on_migrate hints on wakeups of
foreground tasks from scheduler if their load is above
wakeup_load_thresholds (default value is 60).
These hints can be used to choose an appropriate CPU frequency
corresponding to the load of the task being woken up.

Signed-off-by: Rohit Gupta <rohgup@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: Disable wakeup hints for foreground tasks by default

By default sched_wakeup_load_threshold is set to 60 and therefore
wakeup hints are sent out for those tasks whose loads are higher
that value. This might cause unnecessary wakeup boosts to happen
when load based syncing is turned ON for cpu-boost.
Disable the wake up hints by setting the sched_wakeup_load_threshold
to a value higher than 100 so that wakeup boost doesnt happen unless
it is explicitly turned ON from adb shell.

Signed-off-by: Rohit Gupta <rohgup@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: Window-based load stat improvements

Some tasks can have a sporadic load pattern such that they can suddenly
start running for longer intervals of time after running for shorter
durations. To recognize such sharp increase in tasks' demands, max
between the average of 5 window load samples and the most recent sample
is chosen as the task demand.

Make the window size (sched_ravg_window) configurable at boot up
time. To prevent users from setting inappropriate values for window
size, min and max limits are defined. As 'ravg' struct tracks load for
both real-time and non real-time tasks it is moved out of sched_entity
struct.

In order to prevent changing function signatures for move_tasks() and
move_one_task() per-cpu variables are defined to track the total load
moved. In case multiple tasks are selected to migrate in one load
balance operation, loads > 100 could be sent through migration notifiers.
Prevent this scenario by setting mnd.load to 100 in such cases.

Define wrapper functions to compute cpu demands for tasks and to change
rq->cumulative_runnable_avg.

Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Rohit Gupta <rohgup@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: window-stats: Fix overflow bug

Multiplication over-flow possibility exists in update_task_ravg() when
updating task's window_start. That would lead to incorrect accounting
of task load. Fix the issue by using 64-bit arithmetic.

Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
mutex: Move mutex spinning code from sched/core.c back to mutex.c

As mentioned by Ingo, the SCHED_FEAT_OWNER_SPIN scheduler
feature bit was really just an early hack to make with/without
mutex-spinning testable. So it is no longer necessary.

This patch removes the SCHED_FEAT_OWNER_SPIN feature bit and
move the mutex spinning code from kernel/sched/core.c back to
kernel/mutex.c which is where they should belong.

Signed-off-by: Waiman Long <Waiman.Long@hp.com>
Cc: Linus Torvalds <torvalds@linux-foundation.org>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Thomas Gleixner <tglx@linutronix.de>
Cc: Chandramouleeswaran Aswin <aswin@hp.com>
Cc: Davidlohr Bueso <davidlohr.bueso@hp.com>
Cc: Norton Scott J <scott.norton@hp.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Cc: David Howells <dhowells@redhat.com>
Cc: Dave Jones <davej@redhat.com>
Cc: Clark Williams <williams@redhat.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: Implement smarter wake-affine logic

The wake-affine scheduler feature is currently always trying to pull
the wakee close to the waker. In theory this should be beneficial if
the waker's CPU caches hot data for the wakee, and it's also beneficial
in the extreme ping-pong high context switch rate case.

Testing shows it can benefit hackbench up to 15%.

However, the feature is somewhat blind, from which some workloads
such as pgbench suffer. It's also time-consuming algorithmically.

Testing shows it can damage pgbench up to 50% - far more than the
benefit it brings in the best case.

So wake-affine should be smarter and it should realize when to
stop its thankless effort at trying to find a suitable CPU to wake on.

This patch introduces 'wakee_flips', which will be increased each
time the task flips (switches) its wakee target.

So a high 'wakee_flips' value means the task has more than one
wakee, and the bigger the number, the higher the wakeup frequency.

Now when making the decision on whether to pull or not, pay attention to
the wakee with a high 'wakee_flips', pulling such a task may benefit
the wakee. Also imply that the waker will face cruel competition later,
it could be very cruel or very fast depends on the story behind
'wakee_flips', waker therefore suffers.

Furthermore, if waker also has a high 'wakee_flips', that implies that
multiple tasks rely on it, then waker's higher latency will damage all
of them, so pulling wakee seems to be a bad deal.

Thus, when 'waker->wakee_flips / wakee->wakee_flips' becomes
higher and higher, the cost of pulling seems to be worse and worse.

The patch therefore helps the wake-affine feature to stop its pulling
work when:

	wakee->wakee_flips > factor &&
	waker->wakee_flips > (factor * wakee->wakee_flips)

The 'factor' here is the number of CPUs in the current CPU's NUMA node,
so a bigger node will lead to more pulling since the trial becomes more
severe.

After applying the patch, pgbench shows up to 40% improvements and no regressions.

Tested with 12 cpu x86 server and tip 3.10.0-rc7.

The percentages in the final column highlight the areas with the biggest wins,
all other areas improved as well:

	pgbench		    base	smart

	| db_size | clients |  tps  |	|  tps  |
	+---------+---------+-------+   +-------+
	| 22 MB   |       1 | 10598 |   | 10796 |
	| 22 MB   |       2 | 21257 |   | 21336 |
	| 22 MB   |       4 | 41386 |   | 41622 |
	| 22 MB   |       8 | 51253 |   | 57932 |
	| 22 MB   |      12 | 48570 |   | 54000 |
	| 22 MB   |      16 | 46748 |   | 55982 | +19.75%
	| 22 MB   |      24 | 44346 |   | 55847 | +25.93%
	| 22 MB   |      32 | 43460 |   | 54614 | +25.66%
	| 7484 MB |       1 |  8951 |   |  9193 |
	| 7484 MB |       2 | 19233 |   | 19240 |
	| 7484 MB |       4 | 37239 |   | 37302 |
	| 7484 MB |       8 | 46087 |   | 50018 |
	| 7484 MB |      12 | 42054 |   | 48763 |
	| 7484 MB |      16 | 40765 |   | 51633 | +26.66%
	| 7484 MB |      24 | 37651 |   | 52377 | +39.11%
	| 7484 MB |      32 | 37056 |   | 51108 | +37.92%
	| 15 GB   |       1 |  8845 |   |  9104 |
	| 15 GB   |       2 | 19094 |   | 19162 |
	| 15 GB   |       4 | 36979 |   | 36983 |
	| 15 GB   |       8 | 46087 |   | 49977 |
	| 15 GB   |      12 | 41901 |   | 48591 |
	| 15 GB   |      16 | 40147 |   | 50651 | +26.16%
	| 15 GB   |      24 | 37250 |   | 52365 | +40.58%
	| 15 GB   |      32 | 36470 |   | 50015 | +37.14%

Signed-off-by: Michael Wang <wangyun@linux.vnet.ibm.com>
Cc: Mike Galbraith <efault@gmx.de>
Signed-off-by: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: Micro-optimize the smart wake-affine logic

Smart wake-affine is using node-size as the factor currently, but the overhead
of the mask operation is high.

Thus, this patch introduce the 'sd_llc_size' percpu variable, which will record
the highest cache-share domain size, and make it to be the new factor, in order
to reduce the overhead and make it more reasonable.

Tested-by: Davidlohr Bueso <davidlohr.bueso@hp.com>
Tested-by: Michael Wang <wangyun@linux.vnet.ibm.com>
Signed-off-by: Peter Zijlstra <peterz@infradead.org>
Acked-by: Michael Wang <wangyun@linux.vnet.ibm.com>
Cc: Mike Galbraith <efault@gmx.de>
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: Fix memory leakage in build_sched_groups()

In build_sched_groups() we don't need to call get_group() for cpus
which are already covered in previous iterations. Calling get_group()
would mark the group used and eventually leak it since we wouldn't
connect it and not find it again to free it.

This will happen only in cases where sg->cpumask contained more than
one cpu (For any topology level). This patch would free sg's memory
for all cpus leaving the group leader as the group isn't marked used
now.

Signed-off-by: Viresh Kumar <viresh.kumar@linaro.org>
Signed-off-by: Peter Zijlstra <peterz@infradead.org>
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched/debug: Limit sd->*_idx range on sysctl

Various sd->*_idx's are used for refering the rq's load average table
when selecting a cpu to run.  However they can be set to any number
with sysctl knobs so that it can crash the kernel if something bad is
given. Fix it by limiting them into the actual range.

Signed-off-by: Namhyung Kim <namhyung@kernel.org>
Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Link: http://lkml.kernel.org/r/1345104204-8317-1-git-send-email-namhyung@kernel.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Cc: Rui Xiang <rui.xiang@huawei.com>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched/debug: Fix sd->*_idx limit range avoiding overflow

Commit ("sched/debug: Limit sd->*_idx range on
sysctl") was an incomplete bug fix.

This patch fixes sd->*_idx limit range to [0 ~ CPU_LOAD_IDX_MAX-1]
avoiding array overflow caused by setting sd->*_idx to CPU_LOAD_IDX_MAX
on sysctl.

Signed-off-by: Libin <huawei.libin@huawei.com>
Cc: <jiang.liu@huawei.com>
Cc: <guohanjun@huawei.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Link: http://lkml.kernel.org/r/51626610.2040607@huawei.com
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Cc: Rui Xiang <rui.xiang@huawei.com>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: Skip load update for idle task

Load statistics for idle tasks is not useful in any manner. Skip load
update for such idle tasks.

Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
cpufreq: cpu-boost: Add unified hotplug and wake boost

* Additionally, enable load based sync by default and increase
  load_migration_threshold.
* Remove keypad events notifier.
* Improve debugging and little code optimization.

Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
cpufreq: cpu-boost: Export cpu boost status

* This will help hotplug drivers to know boost status
  of CPU and act accordingly.

Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
cpufreq: cpu-boost: Export wakeup_boost

* This is needed to unify boost functions in cpu boost
  and hotplug drivers.

Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>