lowmemorykiller: make default lowmemorykiller debug message useful

lowmemorykiller debug messages are inscrutable and mostly useful
for debugging the lowmemorykiller, not explaining why a process
was killed.  Make the messages more useful by prefixing them
with "lowmemorykiller: " and explaining in more readable terms
what was killed, who it was killed for, and why it was killed.

The messages now look like:
[   76.997631] lowmemorykiller: Killing 'droid.gallery3d' (2172), adj 1000,
[   76.997635]    to free 27436kB on behalf of 'kswapd0' (29) because
[   76.997638]    cache 122624kB is below limit 122880kB for oom_score_adj 1000
[   76.997641]    Free memory is -53356kB above reserved

A negative number for free memory above reserved means some of the
reserved memory has been used and is being regenerated by kswapd,
which is likely what called the shrinkers.

Change-Id: I1fe983381e73e124b90aa5d91cb66e55eaca390f
Signed-off-by: Colin Cross <ccross@android.com>
cpufreq: interactive: turn boost_pulse off on boost off

Change-Id: I36fe217fa047d68ea90e78b12c7db4537ea8010b
Signed-off-by: Ruchi Kandoi <kandoiruchi@google.com>
cpufreq: interactive: Optimize sync_freq implementation

Don't let frequency drop below sync_freq if either load or
frequency among other cpus is above a certain threshold,
not necessarily both.
SELinux: Reduce overhead of mls_level_isvalid() function call

Date	Mon, 10 Jun 2013 13:55:08 -0400

v4->v5:
  - Fix scripts/checkpatch.pl warning.

v3->v4:
  - Merge the 2 separate while loops in ebitmap_contains() into
    a single one.

v2->v3:
  - Remove unused local variables i, node from mls_level_isvalid().

v1->v2:
 - Move the new ebitmap comparison logic from mls_level_isvalid()
   into the ebitmap_contains() helper function.
 - Rerun perf and performance tests on the latest v3.10-rc4 kernel.

While running the high_systime workload of the AIM7 benchmark on
a 2-socket 12-core Westmere x86-64 machine running 3.10-rc4 kernel
(with HT on), it was found that a pretty sizable amount of time was
spent in the SELinux code. Below was the perf trace of the "perf
record -a -s" of a test run at 1500 users:

  5.04%            ls  [kernel.kallsyms]     [k] ebitmap_get_bit
  1.96%            ls  [kernel.kallsyms]     [k] mls_level_isvalid
  1.95%            ls  [kernel.kallsyms]     [k] find_next_bit

The ebitmap_get_bit() was the hottest function in the perf-report
output.  Both the ebitmap_get_bit() and find_next_bit() functions
were, in fact, called by mls_level_isvalid(). As a result, the
mls_level_isvalid() call consumed 8.95% of the total CPU time of
all the 24 virtual CPUs which is quite a lot. The majority of the
mls_level_isvalid() function invocations come from the socket creation
system call.

Looking at the mls_level_isvalid() function, it is checking to see
if all the bits set in one of the ebitmap structure are also set in
another one as well as the highest set bit is no bigger than the one
specified by the given policydb data structure. It is doing it in
a bit-by-bit manner. So if the ebitmap structure has many bits set,
the iteration loop will be done many times.

The current code can be rewritten to use a similar algorithm as the
ebitmap_contains() function with an additional check for the
highest set bit. The ebitmap_contains() function was extended to
cover an optional additional check for the highest set bit, and the
mls_level_isvalid() function was modified to call ebitmap_contains().

With that change, the perf trace showed that the used CPU time drop
down to just 0.08% (ebitmap_contains + mls_level_isvalid) of the
total which is about 100X less than before.

  0.07%            ls  [kernel.kallsyms]     [k] ebitmap_contains
  0.05%            ls  [kernel.kallsyms]     [k] ebitmap_get_bit
  0.01%            ls  [kernel.kallsyms]     [k] mls_level_isvalid
  0.01%            ls  [kernel.kallsyms]     [k] find_next_bit

The remaining ebitmap_get_bit() and find_next_bit() functions calls
are made by other kernel routines as the new mls_level_isvalid()
function will not call them anymore.

This patch also improves the high_systime AIM7 benchmark result,
though the improvement is not as impressive as is suggested by the
reduction in CPU time spent in the ebitmap functions. The table below
shows the performance change on the 2-socket x86-64 system (with HT
on) mentioned above.

+--------------+---------------+----------------+-----------------+
|   Workload   | mean % change | mean % change  | mean % change   |
|              | 10-100 users  | 200-1000 users | 1100-2000 users |
+--------------+---------------+----------------+-----------------+
| high_systime |     +0.1%     |     +0.9%      |     +2.6%       |
+--------------+---------------+----------------+-----------------+
Signed-off-by: Waiman Long <Waiman.Long@hp.com>
Signed-off-by: Paul Reioux <reioux@gmail.com>
kernel:sched: LOAD_FREQ (4*HZ+61) avoids loadavg Moire

LOAD_FREQ is (5*HZ+1) to avoid high load average when idle:
http://kerneltrap.org/mailarchive/linux-kernel/2007/10/3/328568

I suggest (4*HZ+61) for a better distribution.

With some seconds based load (like SSL heartbeats)
and LOAD_FREQ at (5*HZ+1) I see Moire patterns like inverse sawtooth,
since 2 or 3 probes hit the jobs (load increases quickly),
followed by several probes missing it.

A 4.61 sec interval gives optimal distribution over when within a
second a probe is taken, as .61 is close to golden ratio phi 1.618...
(test in http://ripke.com/goldenratio.c).

12*4.61 = 55.32 secs is still close to a minute,
and 13*4.61=59.93 is even closer than the current 12*5.01=60.12
(with exponents EXP_x adjusted to a ratio of 13 instead of 12).
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>
Link: http://lkml.kernel.org/r/51D50057.9000809@linux.vnet.ibm.com
[ Improved the changelog. ]
Signed-off-by: Ingo Molnar <mingo@kernel.org>

Signed-off-by: Paul Reioux <reioux@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>
Link: http://lkml.kernel.org/r/51D5008E.6030102@linux.vnet.ibm.com
[ Tidied up the changelog. ]
Signed-off-by: Ingo Molnar <mingo@kernel.org>

Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: add wait_for_completion_io[_timeout]

The only difference between wait_for_completion[_timeout]() and
wait_for_completion_io[_timeout]() is that the latter calls
io_schedule_timeout() instead of schedule_timeout() so that the caller
is accounted as waiting for IO, not just sleeping.

These functions can be used for correct iowait time accounting when the
completion struct is actually used for waiting for IO (e.g. completion
of a bio request in the block layer).

Modified to compile with 3.4.0 on the Nexus 4 (Mako)

Signed-off-by: Vladimir Davydov <vdavydov@parallels.com>
Acked-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Jens Axboe <axboe@kernel.dk>
Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>
cpufreq: Manage only online cpus

cpufreq core doesn't manage offline cpus and if driver->init() has returned
mask including offline cpus, it may result in unwanted behavior by cpufreq core
or governors.

We need to get only online cpus in this mask. There are two places to fix this
mask, cpufreq core and cpufreq driver. It makes sense to do this at common place
and hence is done in core.

Signed-off-by: Viresh Kumar <viresh.kumar@linaro.org>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>
cpufreq: force cpuN policy to match cpu0 when changing freq or gov
cpufreq: Optimize cpufreq_frequency_table_verify()

cpufreq_frequency_table_verify() is rewritten here to make it more logical
and efficient.
 - merge multiple lines for variable declarations together.
 - quit early if any frequency between min/max is found.
 - don't call cpufreq_verify_within_limits() in case any valid freq is
   found as it is of no use.
 - rename the count variable as found and change its type to boolean.

Signed-off-by: Viresh Kumar <viresh.kumar@linaro.org>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>
selinux: Report permissive mode in avc: denied messages.

We cannot presently tell from an avc: denied message whether access was in
fact denied or was allowed due to global or per-domain permissive mode.
Add a permissive= field to the avc message to reflect this information.

Signed-off-by: Stephen Smalley <sds@tycho.nsa.gov>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
tcp: network speed tweak

Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
prima: reduce rx wakelock
mmc: decrease wakelock timeout
suspend: shorten time to enter sleep state

Conflicts:

	kernel/power/process.c

Signed-off-by: Luis Cruz <ljc2491@gmail.com>

Conflicts:

	kernel/power/process.c
ARM: 7493/1: use generic unaligned.h

Conflicts:

	arch/arm/include/asm/Kbuild

Signed-off-by: Luis Cruz <ljc2491@gmail.com>
Revert dubious scheduler changes.

 * Rolled this series back on other devices as well. It's causing bad
   jank all over the system under a lot of use cases.

Revert "sched: reinitialize rq->next_balance when a CPU is hot-added"

This reverts commit 7c588520b259bf0a342058aa4a9e5ea677522a0d.

Revert "nohz: stat: Fix CPU idle time accounting"

This reverts commit 9446ae3986469a19a603344862e856d54f6df15b.

Revert "sched: remove redundant update_runtime notifier"

This reverts commit 1eb858976a30964ee1812f34f8a05056814ea8e9.

Revert "sched,rt: disable rt_runtime borrowing by default"

This reverts commit a731e214fe6606896de2b50a629bedbdbd95ced7.

Revert "sched/rt: Remove redundant nr_cpus_allowed test"

This reverts commit e169d922cc1fa6026225f9abc71ea28facafd43a.

Revert "sched: Micro-optimize the smart wake-affine logic"

This reverts commit 3bd0f8f8c045c77ca1d46a95ae09ab08c5d52c5d.

Revert "sched: Implement smarter wake-affine logic"

This reverts commit 8ea57b5895029c0694e8cb53295ce2cf735e9505.

Revert "sched: Reduce overestimating rq->avg_idle"

This reverts commit b49d8687515095bdf5089014c2c023d0e61de0cc.

Revert "sched: scale the busy and this queue's per-task load before compare"

This reverts commit a4d496cb8d418891f12cca0e5a3bd64dc2b83ea9.

Revert "sched: reduce calculation effort in fix_small_imbalance"

This reverts commit 65d048b5ef51f2104d3a26fb3e1fddfa8d401090.

Revert "mutex: back out architecture specific check for negative mutex count"

This reverts commit 2f983cc28c06648cc6a50b28a85b3008b51ec850.

Revert "mutex: Queue mutex spinners with MCS lock to reduce cacheline contention"

This reverts commit f6ab92b597a5d1cc6e4ffe82a787cd868140bc09.

Revert "mutex: Make more scalable by doing less atomic operations"

This reverts commit f425908d01a43e0e63e42d51b50c7b9b028e9702.

Change-Id: I7fcb7b2a7bb5657bf70a2189b2d04a5289987106