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>
staging: android: logger: Allow to completely disable

* Logger is completely disabled on kernel_common branch.
* Let's disable it via userspace and give option to
  user to re-enable it when required.

Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
staging: android: logger: Allocate logs dynamically at boot (v3)

This changes the log initialization to be dynamic, but still
at boot time.  These changes are a predecessor to implementing
runtime allocation and freeing of logs, to make the Android logger
less hard-coded.

Change from a fixed set of static log structures, to allocation
at init time into a list.  Return proper error numbers on log
allocation failure.

Cc: Brian Swetland <swetland@google.com>
Signed-off-by: Tim Bird <tim.bird@am.sony.com>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>

Conflicts:
	drivers/staging/android/logger.c
staging: Android: Fix some checkpatch warnings

Warnings reported by checkpatch.pl have been fixed.

Cc: Brian Swetland <swetland@google.com>
Signed-off-by: Sachin Kamat <sachin.kamat@linaro.org>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
staging: android: logger: Fix some sparse and whitespace issues

Fix a few sparse warnings, and improve whitespace.

Cc: Brian Swetland <swetland@google.com>
Signed-off-by: Tim Bird <tim.bird@am.sony.com>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
staging: android: logger: enforce GID and CAP check on log flush

Restrict log flushing to those in the logs group, or
anyone with CAP_SYSLOG.

Cc: Android Kernel Team <kernel-team@android.com>
Cc: Charndeep Grewal <csgrewa@tycho.ncsc.mil>
Signed-off-by: Charndeep Grewal <csgrewa@tycho.ncsc.mil>
Signed-off-by: John Stultz <john.stultz@linaro.org>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
Staging: Android: logger: module_exit implementation

This patch creates the module_exit for the android logger
so that it can be loaded and unloaded as a module.

The android logger is already declared as a tristate in the
Kconfig but the module_exit function was missing.

device_initcall works also with modprobe since include/linux/init.h:

 #define module_init(x)  __initcall(x);
 ...
 #define __initcall(fn) device_initcall(fn)

Signed-off-by: Luca Clementi <luca.clementi@gmail.com>
Cc: Brian Swetland <swetland@google.com>
Cc: Robert Love <rlove@google.com>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
staging: android: logger: Correct write offset reset on error

In the situation that a writer fails to copy data from userspace it will reset
the write offset to the value it had before it went to sleep. This discarding
any messages written while aquiring the mutex.

Therefore the reset offset needs to be retrieved after acquiring the mutex.

Cc: Android Kernel Team <kernel-team@android.com>
Signed-off-by: Bjorn Andersson <bjorn.andersson@sonymobile.com>
Cc: stable <stable@vger.kernel.org>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
staging: android: fix a possible memory leak

Memory allocated by kstrdup should be freed.

CC: Brian Swetland <swetland@google.com>
Acked-by: Dan Carpenter <dan.carpenter@oracle.com>
Signed-off-by: Seunghun Lee <waydi1@gmail.com>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
staging: android: logger: fixed checkpatch.pl warnings.

Signed-off-by: Jerry Stralko <gerb.stralko@gmail.com>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>