block: recursive merge requests

In a workload, thread 1 accesses a, a+2, ..., thread 2 accesses a+1, a+3,....
When the requests are flushed to queue, a and a+1 are merged to (a, a+1), a+2
and a+3 too to (a+2, a+3), but (a, a+1) and (a+2, a+3) aren't merged.

If we do recursive merge for such interleave access, some workloads throughput
get improvement. A recent worload I'm checking on is swap, below change
boostes the throughput around 5% ~ 10%.

Signed-off-by: Shaohua Li <shli@fusionio.com>
Signed-off-by: Jens Axboe <axboe@kernel.dk>
Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>
sched: Fix select_idle_sibling() bouncing cow syndrome

If the previous CPU is cache affine and idle, select it.

The current implementation simply traverses the sd_llc domain,
taking the first idle CPU encountered, which walks buddy pairs
hand in hand over the package, inflicting excruciating pain.

1 tbench pair (worst case) in a 10 core + SMT package:

  pre   15.22 MB/sec 1 procs
  post 252.01 MB/sec 1 procs

Signed-off-by: Mike Galbraith <bitbucket@online.de>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Link: http://lkml.kernel.org/r/1359371965.5783.127.camel@marge.simpson.net
Signed-off-by: Ingo Molnar <mingo@kernel.org>
Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>
block: Reserve only one queue tag for sync IO if only 3 tags are available

In case a device has three tags available we still reserve two of them
for sync IO. That leaves only a single tag for async IO such as
writeback from flusher thread which results in poor performance.

Allow async IO to consume two tags in case queue has three tag availabe
to get a decent async write performance.

This patch improves streaming write performance on a machine with such disk
from ~21 MB/s to ~52 MB/s. Also postmark throughput in presence of
streaming writer improves from 8 to 12 transactions per second so sync
IO doesn't seem to be harmed in presence of heavy async writer.

Signed-off-by: Jan Kara <jack@suse.cz>
Signed-off-by: Jens Axboe <axboe@kernel.dk>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>
sched: LOAD_FREQ (4*HZ+122) avoids loadavg Moire

From http://ripke.com/loadavg/moire but corrected for 200HZ.
readahead: make context readahead more conservative

This helps performance on moderately dense random reads on SSD.

Transaction-Per-Second numbers provided by Taobao:

		QPS	case
		-------------------------------------------------------
		7536	disable context readahead totally
w/ patch:	7129	slower size rampup and start RA on the 3rd read
		6717	slower size rampup
w/o patch:	5581	unmodified context readahead

Before, readahead will be started whenever reading page N+1 when it happen
to read N recently.  After patch, we'll only start readahead when *three*
random reads happen to access pages N, N+1, N+2.  The probability of this
happening is extremely low for pure random reads, unless they are very
dense, which actually deserves some readahead.

Also start with a smaller readahead window.  The impact to interleaved
sequential reads should be small, because for a long run stream, the the
small readahead window rampup phase is negletable.

The context readahead actually benefits clustered random reads on HDD
whose seek cost is pretty high.  However as SSD is increasingly used for
random read workloads it's better for the context readahead to concentrate
on interleaved sequential reads.

Another SSD rand read test from Miao

        # file size:        2GB
        # read IO amount: 625MB
        sysbench --test=fileio          \
                --max-requests=10000    \
                --num-threads=1         \
                --file-num=1            \
                --file-block-size=64K   \
                --file-test-mode=rndrd  \
                --file-fsync-freq=0     \
                --file-fsync-end=off    run

shows the performance of btrfs grows up from 69MB/s to 121MB/s, ext4 from
104MB/s to 121MB/s.

Signed-off-by: Wu Fengguang <fengguang.wu@intel.com>
Tested-by: Tao Ma <tm@tao.ma>
Tested-by: Miao Xie <miaox@cn.fujitsu.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Pranav Vashi <neobuddy89@gmail.com>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>
cpuidle: Quickly notice prediction failure for repeat mode

The prediction for future is difficult and when the cpuidle governor prediction
fails and govenor possibly choose the shallower C-state than it should. How to
quickly notice and find the failure becomes important for power saving.

cpuidle menu governor has a method to predict the repeat pattern if there are 8
C-states residency which are continuous and the same or very close, so it will
predict the next C-states residency will keep same residency time.

There is a real case that turbostat utility (tools/power/x86/turbostat)
at kernel 3.3 or early. turbostat utility will read 10 registers one by one at
Sandybridge, so it will generate 10 IPIs to wake up idle CPUs. So cpuidle menu
 governor will predict it is repeat mode and there is another IPI wake up idle
 CPU soon, so it keeps idle CPU stay at C1 state even though CPU is totally
idle. However, in the turbostat, following 10 registers reading is sleep 5
seconds by default, so the idle CPU will keep at C1 for a long time though it is
 idle until break event occurs.
In a idle Sandybridge system, run "./turbostat -v", we will notice that deep
C-state dangles between "70% ~ 99%". After patched the kernel, we will notice
deep C-state stays at >99.98%.

In the patch, a timer is added when menu governor detects a repeat mode and
choose a shallow C-state. The timer is set to a time out value that greater
than predicted time, and we conclude repeat mode prediction failure if timer is
triggered. When repeat mode happens as expected, the timer is not triggered
and CPU waken up from C-states and it will cancel the timer initiatively.
When repeat mode does not happen, the timer will be time out and menu governor
will quickly notice that the repeat mode prediction fails and then re-evaluates
deeper C-states possibility.

Below is another case which will clearly show the patch much benefit:

volatile int * shutdown;
volatile long * count;
int delay = 20;
int loop = 8;

void usage(void)
{
	fprintf(stderr,
		"Usage: idle_predict [options]\n"
		"  --help	-h  Print this help\n"
		"  --thread	-n  Thread number\n"
		"  --loop     	-l  Loop times in shallow Cstate\n"
		"  --delay	-t  Sleep time (uS)in shallow Cstate\n");
}

void *simple_loop() {
	int idle_num = 1;
	while (!(*shutdown)) {
		*count = *count + 1;

		if (idle_num % loop)
			usleep(delay);
		else {
			/* sleep 1 second */
			usleep(1000000);
			idle_num = 0;
		}
		idle_num++;
	}

}

static void sighand(int sig)
{
	*shutdown = 1;
}

int main(int argc, char *argv[])
{
	sigset_t sigset;
	int signum = SIGALRM;
	int i, c, er = 0, thread_num = 8;
	pthread_t pt[1024];

	static char optstr[] = "n:l:t:h:";

	while ((c = getopt(argc, argv, optstr)) != EOF)
		switch (c) {
			case 'n':
				thread_num = atoi(optarg);
				break;
			case 'l':
				loop = atoi(optarg);
				break;
			case 't':
				delay = atoi(optarg);
				break;
			case 'h':
			default:
				usage();
				exit(1);
		}

	printf("thread=%d,loop=%d,delay=%d\n",thread_num,loop,delay);
	count = malloc(sizeof(long));
	shutdown = malloc(sizeof(int));
	*count = 0;
	*shutdown = 0;

	sigemptyset(&sigset);
	sigaddset(&sigset, signum);
	sigprocmask (SIG_BLOCK, &sigset, NULL);
	signal(SIGINT, sighand);
	signal(SIGTERM, sighand);

	for(i = 0; i < thread_num ; i++)
		pthread_create(&pt[i], NULL, simple_loop, NULL);

	for (i = 0; i < thread_num; i++)
		pthread_join(pt[i], NULL);

	exit(0);
}

Get powertop V2 from git://github.com/fenrus75/powertop, build powertop.
After build the above test application, then run it.
Test plaform can be Intel Sandybridge or other recent platforms.

We will find that deep C-state will dangle between 40%~100% and much time spent
on C1 state. It is because menu governor wrongly predict that repeat mode
is kept, so it will choose the C1 shallow C-state even though it has chance to
sleep 1 second in deep C-state.

While after patched the kernel, we find that deep C-state will keep >99.6%.

Signed-off-by: Rik van Riel <riel@redhat.com>
Signed-off-by: Youquan Song <youquan.song@intel.com>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>

Conflicts:

	kernel/time/tick-sched.c

Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>
cpuidle: Quickly notice prediction failure in general case

The prediction for future is difficult and when the cpuidle governor prediction
fails and govenor possibly choose the shallower C-state than it should. How to
quickly notice and find the failure becomes important for power saving.

The patch extends to general case that prediction logic get a small predicted
residency, so it choose a shallow C-state though the expected residency is large
. Once the prediction will be fail, the CPU will keep staying at shallow C-state
for a long time. Acutally, the CPU has change enter into deep C-state.
So when the expected residency is long enough but governor choose a shallow
C-state, an timer will be added in order to monitor if the prediction failure.

When C-state is waken up prior to the adding timer, the timer will be cancelled
initiatively. When the timer is triggered and menu governor will quickly notice
prediction failure and re-evaluates deeper C-states possibility.

Signed-off-by: Rik van Riel <riel@redhat.com>
Signed-off-by: Youquan Song <youquan.song@intel.com>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>
cpuidle: Get typical recent sleep interval

The function detect_repeating_patterns was not very useful for
workloads with alternating long and short pauses, for example
virtual machines handling network requests for each other (say
a web and database server).

Instead, try to find a recent sleep interval that is somewhere
between the median and the mode sleep time, by discarding outliers
to the up side and recalculating the average and standard deviation
until that is no longer required.

This should do something sane with a sleep interval series like:

	200 180 210 10000 30 1000 170 200

The current code would simply discard such a series, while the
new code will guess a typical sleep interval just shy of 200.

The original patch come from Rik van Riel <riel@redhat.com>.

Signed-off-by: Rik van Riel <riel@redhat.com>
Signed-off-by: Youquan Song <youquan.song@intel.com>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>
cpuidle: Fix finding state with min power_usage

Since cpuidle_state.power_usage is a signed value, use INT_MAX (instead
of -1) to init the local copies so that functions that tries to find
cpuidle states with minimum power usage works correctly even if they use
non-negative values.

Signed-off-by: Sivaram Nair <sivaramn@nvidia.com>
Reviewed-by: Rik van Riel <riel@redhat.com>
Signed-off-by: Rafael J. Wysocki <rafael.j.wysocki@intel.com>
Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>
AIO: Don't plug the I/O queue in do_io_submit() Asynchronous I/O latency to a solid-state disk greatly increased between the 2.6.32 and 3.0 kernels. By removing the plug from do_io_submit(), we observed a 34% improvement in the I/O latency.

Unfortunately, at this level, we don't know if the request is to
a rotating disk or not.

Change-Id: I7101df956473ed9fd5dcff18e473dd93b688a5c1
Signed-off-by: Dave Kleikamp <dave.kleikamp@oracle.com>
Cc: linux-aio@kvack.org
Cc: Chris Mason <chris.mason@oracle.com>
Cc: Jens Axboe <axboe@kernel.dk>
Cc: Andi Kleen <ak@linux.intel.com>
Cc: Jeff Moyer <jmoyer@redhat.com>
writeback: fix occasional slow sync(1)

In case when system contains no dirty pages, wakeup_flusher_threads() will
submit WB_SYNC_NONE writeback for 0 pages so wb_writeback() exits
immediately without doing anything, even though there are dirty inodes in
the system.  Thus sync(1) will write all the dirty inodes from a
WB_SYNC_ALL writeback pass which is slow.

Fix the problem by using get_nr_dirty_pages() in wakeup_flusher_threads()
instead of calculating number of dirty pages manually.  That function also
takes number of dirty inodes into account.

Signed-off-by: Jan Kara <jack@suse.cz>
Reported-by: Paul Taysom <taysom@chromium.org>
Cc: Wu Fengguang <fengguang.wu@intel.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
arm: vfpmodule: Fix warning procfs vfp_bounce reporting failed

Creation of procfs cpu/vfp_bounce fails because we're initialized too early. Fix
this by creating it on rootfs_initcall as before the NEON patches.

<6>[    0.130770] VFP support v0.3: implementor 51 architecture 64 part 6f varia
nt 2 rev 0
<4>[    0.130795] ------------[ cut here ]------------
<4>[    0.130813] WARNING: at fs/proc/generic.c:323 __xlate_proc_name+0xac/0xcc(
)
<4>[    0.130822] name 'cpu/vfp_bounce'
<4>[    0.130855] [<c010e26c>] (unwind_backtrace+0x0/0x144) from [<c0a20f58>] (d
ump_stack+0x20/0x24)
<4>[    0.130879] [<c0a20f58>] (dump_stack+0x20/0x24) from [<c019b670>] (warn_sl
owpath_common+0x58/0x70)
<4>[    0.130899] [<c019b670>] (warn_slowpath_common+0x58/0x70) from [<c019b704>
] (warn_slowpath_fmt+0x40/0x48)
<4>[    0.130919] [<c019b704>] (warn_slowpath_fmt+0x40/0x48) from [<c02c2ad8>] (
__xlate_proc_name+0xac/0xcc)
<4>[    0.130938] [<c02c2ad8>] (__xlate_proc_name+0xac/0xcc) from [<c02c2b50>] (
__proc_create+0x58/0x100)
<4>[    0.130956] [<c02c2b50>] (__proc_create+0x58/0x100) from [<c02c2ed0>] (pro
c_create_data+0x5c/0xc0)
<4>[    0.130979] [<c02c2ed0>] (proc_create_data+0x5c/0xc0) from [<c0f03484>] (v
fp_init+0x19c/0x200)
<4>[    0.131000] [<c0f03484>] (vfp_init+0x19c/0x200) from [<c0f00c98>] (do_one_
initcall+0x98/0x168)
<4>[    0.131020] [<c0f00c98>] (do_one_initcall+0x98/0x168) from [<c0f00e60>] (k
ernel_init+0xf8/0x1b4)
<4>[    0.131043] [<c0f00e60>] (kernel_init+0xf8/0x1b4) from [<c01081a0>] (kerne
l_thread_exit+0x0/0x8)
<4>[    0.131076] ---[ end trace ea6d9a9b5e947151 ]---
<3>[    0.131086] Failed to create procfs node for VFP bounce reporting
msm: move printk out of spin lock low_water_lock

cpu3 stuck in printk more time in spin lock low_water_lock cause cpu0
get spin lock fail and system crashed.

CRs-Fixed: 521570
Change-Id: I75356a4b4171ae2888ce6cce792f569b5ca8cdcf
Signed-off-by: Tingting Yang <tingting@codeaurora.org>
epoll: optimize EPOLL_CTL_DEL using rcu

Date	Tue, 1 Oct 2013 17:08:10 +0000 (GMT)

Optimize EPOLL_CTL_DEL such that it does not require the 'epmutex' by
converting the file->f_ep_links list into an rcu one. In this way, we can
traverse the epoll network on the add path in parallel with deletes. Since
deletes can't create loops or worse wakeup paths, this is safe.

This patch in combination with the patch "epoll: Do not take global 'epmutex'
for simple topologies", shows a dramatic performance improvement in
scalability for SPECjbb.

Tested-by: Nathan Zimmer <nzimmer@sgi.com>
Signed-off-by: Jason Baron <jbaron@akamai.com>

backported for Linux 3.4 for use on Android
Signed-off-by: Paul Reioux <reioux@gmail.com>
epoll: Do not take global 'epmutex' for simple topologies

Date	Tue, 1 Oct 2013 17:08:14 +0000 (GMT)

When calling EPOLL_CTL_ADD for an epoll file descriptor that is attached
directly to a wakeup source, we do not need to take the global 'epmutex',
unless the epoll file descriptor is nested. The purpose of taking
the 'epmutex' on add is to prevent complex topologies such as loops and
deep wakeup paths from forming in parallel through multiple EPOLL_CTL_ADD
operations. However, for the simple case of an epoll file descriptor
attached directly to a wakeup source (with no nesting), we do not need
to hold the 'epmutex'.

This patch along with 'epoll: optimize EPOLL_CTL_DEL using rcu' improves
scalability on larger systems. Quoting Nathan Zimmer's mail on SPECjbb
performance:

"
On the 16 socket run the performance went from 35k jOPS to 125k jOPS.
In addition the benchmark when from scaling well on 10 sockets to scaling well
on just over 40 sockets.

...

Currently the benchmark stops scaling at around 40-44 sockets but it seems like
I found a second unrelated bottleneck.
"

Tested-by: Nathan Zimmer <nzimmer@sgi.com>
Signed-off-by: Jason Baron <jbaron@akamai.com>

backported to Linux 3.4 for use on Android
Signed-off-by: Paul Reioux <reioux@gmail.com>
epoll: do not take globals epmutex for simple topologies fix

- use `bool' for boolean variables
- remove unneeded/undesirable cast of void*
- add missed ep_scan_ready_list() kerneldoc

Cc: "Paul E. McKenney" <paulmck@us.ibm.com>
Cc: Al Viro <viro@zeniv.linux.org.uk>
Cc: Davide Libenzi <davidel@xmailserver.org>
Cc: Eric Wong <normalperson@yhbt.net>
Cc: Jason Baron <jbaron@akamai.com>
Cc: Nathan Zimmer <nzimmer@sgi.com>
Cc: Nelson Elhage <nelhage@nelhage.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>

Signed-off-by: Paul Reioux <reioux@gmail.com>
jiffies conversions: Use compile time constants when possible

Date	Fri, 04 Jan 2013 13:15:43 -0800

Do the multiplications and divisions at compile time
instead of runtime when the converted value is a constant.

Make the calculation functions static __always_inline to jiffies.h.

Add #defines with __builtin_constant_p to test and use the
static inline or the runtime functions as appropriate.

Prefix the old exported symbols/functions with __

Signed-off-by: Paul Reioux <reioux@gmail.com>
sched: reinitialize rq->next_balance when a CPU is hot-added

Reinitialize rq->next_balance when a CPU is hot-added.  Otherwise,
scheduler domain rebalancing may be skipped if rq->next_balance was
set to a future time when the CPU was last active, and the
newly-re-added CPU is in idle_balance().  As a result, the
newly-re-added CPU will remain idle with no tasks scheduled until the
softlockup watchdog runs - potentially 4 seconds later.  This can
waste energy and reduce performance.

This behavior can be observed in some SoC kernels, which use CPU
hotplug to dynamically remove and add CPUs in response to load.  In
one case that triggered this behavior,

0. the system started with all cores enabled, running multi-threaded
   CPU-bound code;

1. the system entered some single-threaded code;

2. a CPU went idle and was hot-removed;

3. the system started executing a multi-threaded CPU-bound task;

4. the CPU from event 2 was re-added, to respond to the load.

The time interval between events 2 and 4 was approximately 300
milliseconds.

Of course, ideally CPU hotplug would not be used in this manner,
but this patch does appear to fix a real bug.

Nvidia folks: this patch is submitted as at least a partial fix for
bug 1243368 ("[sched] Load-balancing not happening correctly after
cores brought online")

Change-Id: Iabac21e110402bb581b7db40c42babc951d378d0
Signed-off-by: Paul Walmsley <pwalmsley@nvidia.com>
Cc: Peter Boonstoppel <pboonstoppel@nvidia.com>
Reviewed-on: http://git-master/r/208927
Reviewed-by: Automatic_Commit_Validation_User
Reviewed-by: Peter Zu <pzu@nvidia.com>
Reviewed-by: Peter Boonstoppel <pboonstoppel@nvidia.com>
GVS: Gerrit_Virtual_Submit
Tested-by: Peter Zu <pzu@nvidia.com>
Reviewed-by: Yu-Huan Hsu <yhsu@nvidia.com>
ARM: mm: rename jump labels in v7_flush_dcache_all function

This patch renames jump labels in v7_flush_dcache_all in order to define
a specific flush cache levels entry point.

TODO: factor out the level flushing loop if considered worthwhile and
      define the input registers requirements.

Signed-off-by: Lorenzo Pieralisi <lorenzo.pieralisi@xxxxxxx>
Signed-off-by: Paul Reioux <reioux@gmail.com>
cpufreq: interactive: Fix null pointer dereference in interactive governor

For the sync_freq feature currently we check pcpu->policy->cur frequency
for each online cpu.  But for a CPU that isn't using interactive governor
or for an offline CPU, pcpu->policy can be null or an invalid value.
This patch tries to avoid that scenario by using pcpu->target_freq
instead of policy->cur to get the frequency of an online CPU.

Kernel crash without this patch:
[   20.132373] Unable to handle kernel NULL pointer dereference at virtual address 00000028
[   20.132375] pgd = c34f34c0
[   20.132377] pgd = ef6f2440
[   20.132383] [00000028] *pgd=00000000
[   20.132385]
[   20.132388] [00000028] *pgd=2e98f003, *pmd=00000000
[   20.132390] Internal error: Oops: 205 [#1] PREEMPT SMP ARM
[   20.132394] Modules linked in:
[   20.132398] CPU: 0 PID: 1560 Comm: chown Tainted: G        W    3.10.0-perf-gb12057b-00001-ga2c6c16-dirty #7
[   20.132401] task: ef9af300 ti: ee49c000 task.ti: ee49c000
[   20.132411] PC is at cpufreq_interactive_timer+0x10c/0x650
[   20.132415] LR is at cpufreq_interactive_timer+0x128/0x650
<snip>
[   20.133002] [<c07eb204>] (cpufreq_interactive_timer+0x10c/0x650) from [<c02804d8>] (call_timer_fn+0x80/0x198)
[   20.133012] [<c02804d8>] (call_timer_fn+0x80/0x198) from [<c0280acc>] (run_timer_softirq+0x1f8/0x270)
[   20.133019] [<c0280acc>] (run_timer_softirq+0x1f8/0x270) from [<c0279e20>] (__do_softirq+0x12c/0x2d4)
[   20.133025] [<c0279e20>] (__do_softirq+0x12c/0x2d4) from [<c027a2d4>] (irq_exit+0x74/0xc8)
[   20.133034] [<c027a2d4>] (irq_exit+0x74/0xc8) from [<c0206a00>] (handle_IRQ+0x68/0x8c)
[   20.133041] [<c0206a00>] (handle_IRQ+0x68/0x8c) from [<c02004b8>] (gic_handle_irq+0x3c/0x60)
[   20.133051] [<c02004b8>] (gic_handle_irq+0x3c/0x60) from [<c0ac6900>] (__irq_svc+0x40/0x70)
<snip>

Change-Id: Ie834f5d383de4d41e0fe6fbd40c8b0a0c05d82f5
Signed-off-by: Vijay Ganti <viganti@codeaurora.org>