nohz: Reduce overhead under high-freq idling patterns

One testbox of mine (Intel Nehalem, 16-way) uses MWAIT for its idle routine,
which apparently can break out of its idle loop rather frequently, with
high frequency.

In that case NO_HZ_FULL=y kernels show high ksoftirqd overhead and constant
context switching, because tick_nohz_stop_sched_tick() will, if
delta_jiffies == 0, mis-identify this as a timer event - activating the
TIMER_SOFTIRQ, which wakes up ksoftirqd.

Fix this by treating delta_jiffies == 0 the same way we treat other short
wakeups, delta_jiffies == 1.

Cc: Frederic Weisbecker <fweisbec@gmail.com>
Cc: Chris Metcalf <cmetcalf@tilera.com>
Cc: Christoph Lameter <cl@linux.com>
Cc: Geoff Levand <geoff@infradead.org>
Cc: Gilad Ben Yossef <gilad@benyossef.com>
Cc: Hakan Akkan <hakanakkan@gmail.com>
Cc: Kevin Hilman <khilman@linaro.org>
Cc: Li Zhong <zhong@linux.vnet.ibm.com>
Cc: Oleg Nesterov <oleg@redhat.com>
Cc: Paul E. McKenney <paulmck@linux.vnet.ibm.com>
Cc: Paul Gortmaker <paul.gortmaker@windriver.com>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Steven Rostedt <rostedt@goodmis.org>
Signed-off-by: Ingo Molnar <mingo@kernel.org>
misc compile fixes
locking: Move the mutex code to kernel/locking/

Suggested-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Peter Zijlstra <peterz@infradead.org>
Link: http://lkml.kernel.org/n/tip-1ditvncg30dgbpvrz2bxfmke@git.kernel.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
locking: Move the lockdep code to kernel/locking/

Suggested-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Peter Zijlstra <peterz@infradead.org>
Link: http://lkml.kernel.org/n/tip-wl7s3tta5isufzfguc23et06@git.kernel.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
locking: Move the spinlock code to kernel/locking/

Suggested-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Peter Zijlstra <peterz@infradead.org>
Link: http://lkml.kernel.org/n/tip-b81ol0z3mon45m51o131yc9j@git.kernel.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
locking: Move the semaphore core to kernel/locking/

Suggested-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Peter Zijlstra <peterz@infradead.org>
Link: http://lkml.kernel.org/n/tip-vmw5sf6vzmua1z6nx1cg69h2@git.kernel.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
locking: Move the rtmutex code to kernel/locking/

Suggested-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Peter Zijlstra <peterz@infradead.org>
Link: http://lkml.kernel.org/n/tip-p9ijt8div0hwldexwfm4nlhj@git.kernel.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: Introduce efficiency, load_scale_factor and capacity

Efficiency reflects instructions per cycle capability of a cpu.

load_scale_factor reflects magnification factor that is applied for
task load when estimating bandwidth it will consume on a cpu. It
accounts for the fact that task load is scaled in reference to "best"
cpu that has best efficiency factor and also best possible max_freq.
Note that there may be no single CPU in the system that has both the
best efficiency and best possible max_freq, but that is still the
combination that all task load in the system is scaled against.

capacity reflects max_freq and efficiency metric of a cpu. It is
defined such that the "least" performing cpu (one with lowest
efficiency factor and max_freq) gets capacity of 1024. Again, there
may not be a CPU in the system that has both the lowest efficiency
and lowest max_freq. This is still the combination that is assigned
a capacity of 1024 however, other CPU capacities are relative to this.

Change-Id: I4a853f1f0f90020721d2a4ee8b10db3d226b287c
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: Use rq->efficiency in scaling load stats

Extend task load scaling function to account for cpu efficiency
factor. Task load is scaled in reference to "most" efficient cpu.

Change-Id: I7bf829211a6e1293076e8ba0f93b4f6abcf20d92
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: Influence cpu_power based on max_freq and efficiency

Update cpu_power metric of a cpu by accounting its efficiency and
max_freq factors. cpu_power is defined such that "least" performing
cpu (one with lowest efficiency and max_freq factor) gets cpu_power of
1024. Note that no single CPU may have both the lowest efficiency and
lowest max_freq. All CPUs will still have cpu_power values relative to
this combination receiving a cpu_power of 1024 however.

cpu_power differs from capacity metric of a cpu by accounting
real-time task activity.

Change-Id: I255d3ad80d8bc8237b9ffb8f6e7c0dc4c44ec10f
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: Basic task placement support for HMP systems

HMP systems have cpus with different power and performance
characteristics. Some cpus could offer better power at cost of lower
performance while other cpus could offer better performance at cost of
higher power. As a result, bandwidth consumed by a task to do some
"fixed" amount of work could vary across cpus.

Optimal task placement on HMP would involve placing a task on a cpu
where it can meet its performance goals at lowest power cost. Since
kernel has little to no awareness of performance goals of
applications, we guestimate whether task is meeting its performance
goals or not by looking at its cpu bandwidth consumption. High
bandwidth consumption could imply that task's performance can improve
by running on cpus with better capacity/performance-characterisitcs.

This patch makes the basic changes to support HMP. It provides a
configurable threshold and any task consuming bandwidth in excess of
threshold will be placed on a cpu with better capacity.

Change-Id: I3fd98edd430f73342fbef06411e8b2d1cf2f56fa
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: Send NOHZ kick to idle cpu in same cluster

A busy cpu will kick (via IPI) one of the idle cpus in tickless state
to run load balance and help move tasks off itself. The cpu chosen to
receive kick is simply the "first" idle cpu found in
nohz.idle_cpus_mask. This could cause unnecessary wakeups of a
cluster. A better choice would be to look for an idle cpu that is in
the same cluster as busy cpu, which should minimize cluster wakeups.

Change-Id: Ia63038d7c34b416b53c8feef3c3b31dab5200e42
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: Extend active balance to accept 'push_task' argument

Active balance currently picks one task to migrate from busy cpu to
a chosen cpu (push_cpu). This patch extends active load balance to
recognize a particular task ('push_task') that needs to be migrated to
'push_cpu'. This capability will be leveraged by HMP-aware task
placement in a subsequent patch.

Change-Id: If31320111e6cc7044e617b5c3fd6d8e0c0e16952
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: Handle cpu-bound tasks stuck on wrong cpu

CPU-bound tasks that don't sleep for long intervals can stay stuck on
the wrong cpu, as the selection of "ideal" cpu for tasks largely
happens during task wakeup time. This patch adds a check in the
scheduler tick for task/cpu mismatch (big task on little cpu OR
little task on big cpu) and forces migration of such tasks to their
ideal cpu (via select_best_cpu()).

Change-Id: Icac3485b6aa4b558c4ed9df23c2e81fb8f4bb9d9
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched: Track number of big and small tasks on a cpu

This patch adds 'nr_big_tasks' and 'nr_small_tasks' per-cpu counters
that tracks number of big and small tasks on a cpu respectively. This
will be used in load balance decisions introduced in a subsequent
patch.

Change-Id: Ia174904140f81dd6d1946286889a50be3f16ea83
Signed-off-by: Srivatsa Vaddagiri <vatsa@codeaurora.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched/fair: Let minimally loaded cpu balance the
 group

Currently we let the leftmost (or first idle) cpu ascend the
sched_domain tree and perform load-balancing. The result is that the
busiest cpu in the group might be performing this function and pull
more load to itself. The next load balance pass will then try to
equalize this again.

Change this to pick the least loaded cpu to perform higher domain
balancing.

Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Link: http://lkml.kernel.org/n/tip-v8zlrmgmkne3bkcy9dej1fvm@git.kernel.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
sched/fair: Add some serialization to the
 sched_domain load-balance walk

Since the sched_domain walk is completely unserialized (!SD_SERIALIZE)
it is possible that multiple cpus in the group get elected to do the
next level. Avoid this by adding some serialization.

Signed-off-by: Peter Zijlstra <a.p.zijlstra@chello.nl>
Link: http://lkml.kernel.org/n/tip-vqh9ai6s0ewmeakjz80w4qz6@git.kernel.org
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
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>