nohz: stat: Fix CPU idle time accounting

Since cpustat[CPUTIME_IDLE] is never connected to ts->idle_sleeptime,
never read from cpustat[CPUTIME_IDLE] when reporting stats in
/proc/stat.

Note this was rejected by Michal Hocko when it was initially proposed
by Martin Schwidefsky in LKML, so if you want to upstream it, better
find an alternative (either completely disable cpustat[CPUTIME_IDLE]
for CONFIG_NO_HZ or somehow connect them to keep them in sync.)

Signed-off-by: Bo Yan <byan@nvidia.com>
Reviewed-on: http://git-master/r/214638
Reviewed-by: Automatic_Commit_Validation_User
Reviewed-by: Liang Cheng (SW) <licheng@nvidia.com>
Tested-by: Liang Cheng (SW) <licheng@nvidia.com>
sched: remove redundant update_runtime notifier

migration_call() will do all the things that update_runtime() does.
So it seems update_runtime() is a redundant notifier, remove it.

Furthermore, there is potential risk that the current code will catch
BUG_ON at line 687 of rt.c when do cpu hotplug while there are realtime
threads running because of enable runtime twice.

Signed-off-by: Neil Zhang <zhangwm@marvell.com>
Reviewed-on: http://git-master/r/215596
Reviewed-on: http://git-master/r/223067
Reviewed-by: Peter Boonstoppel <pboonstoppel@nvidia.com>
Tested-by: Peter Boonstoppel <pboonstoppel@nvidia.com>
Reviewed-by: Paul Walmsley <pwalmsley@nvidia.com>
Reviewed-by: Automatic_Commit_Validation_User
Reviewed-by: Diwakar Tundlam <dtundlam@nvidia.com>
writeback: fix race that cause writeback hung

There is a race between mark inode dirty and writeback thread, see the
following scenario.  In this case, writeback thread will not run though
there is dirty_io.

__mark_inode_dirty()                                          bdi_writeback_workfn()
    ...                                                       	...
    spin_lock(&inode->i_lock);
    ...
    if (bdi_cap_writeback_dirty(bdi)) {
	<<< assume wb has dirty_io, so wakeup_bdi is false.
	<<< the following inode_dirty also have wakeup_bdi false.
	if (!wb_has_dirty_io(&bdi->wb))
		wakeup_bdi = true;
    }
    spin_unlock(&inode->i_lock);
								<<< assume last dirty_io is removed here.
								pages_written = wb_do_writeback(wb);
								...
								<<< work_list empty and wb has no dirty_io,
								<<< delayed_work will not be queued.
								if (!list_empty(&bdi->work_list) ||
								    (wb_has_dirty_io(wb) && dirty_writeback_interval))
								    queue_delayed_work(bdi_wq, &wb->dwork,
									msecs_to_jiffies(dirty_writeback_interval * 10));
    spin_lock(&bdi->wb.list_lock);
    inode->dirtied_when = jiffies;
    <<< new dirty_io is added.
    list_move(&inode->i_wb_list, &bdi->wb.b_dirty);
    spin_unlock(&bdi->wb.list_lock);

    <<< though there is dirty_io, but wakeup_bdi is false,
    <<< so writeback thread will not be waked up and
    <<< the new dirty_io will not be flushed.
    if (wakeup_bdi)
	bdi_wakeup_thread_delayed(bdi);

Writeback will run until there is a new flush work queued.  This may cause
a lot of dirty pages stay in memory for a long time.

Signed-off-by: Junxiao Bi <junxiao.bi@oracle.com>
Reviewed-by: Jan Kara <jack@suse.cz>
Cc: Fengguang Wu <fengguang.wu@intel.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
writeback: Do not sort b_io list only because of block device inode

It is very likely that block device inode will be part of BDI dirty list
as well. However it doesn't make sence to sort inodes on the b_io list
just because of this inode (as it contains buffers all over the device
anyway). So save some CPU cycles which is valuable since we hold relatively
contented wb->list_lock.

Signed-off-by: Jan Kara <jack@suse.cz>
sync: don't block the flusher thread waiting on IO

When sync does it's WB_SYNC_ALL writeback, it issues data Io and
then immediately waits for IO completion. This is done in the
context of the flusher thread, and hence completely ties up the
flusher thread for the backing device until all the dirty inodes
have been synced. On filesystems that are dirtying inodes constantly
and quickly, this means the flusher thread can be tied up for
minutes per sync call and hence badly affect system level write IO
performance as the page cache cannot be cleaned quickly.

We already have a wait loop for IO completion for sync(2), so cut
this out of the flusher thread and delegate it to wait_sb_inodes().
Hence we can do rapid IO submission, and then wait for it all to
complete.

Effect of sync on fsmark before the patch:

FSUse%        Count         Size    Files/sec     App Overhead
.....
      0       640000         4096      35154.6          1026984
      0       720000         4096      36740.3          1023844
      0       800000         4096      36184.6           916599
      0       880000         4096       1282.7          1054367
      0       960000         4096       3951.3           918773
      0      1040000         4096      40646.2           996448
      0      1120000         4096      43610.1           895647
      0      1200000         4096      40333.1           921048

And a single sync pass took:

  real    0m52.407s
  user    0m0.000s
  sys     0m0.090s

After the patch, there is no impact on fsmark results, and each
individual sync(2) operation run concurrently with the same fsmark
workload takes roughly 7s:

  real    0m6.930s
  user    0m0.000s
  sys     0m0.039s

IOWs, sync is 7-8x faster on a busy filesystem and does not have an
adverse impact on ongoing async data write operations.

Signed-off-by: Dave Chinner <dchinner@redhat.com>
Reviewed-by: Jan Kara <jack@suse.cz>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
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>
lib/percpu_counter.c: *squashing updates*

switch the protection of percpu_counter list to spinlock

      ... making percpu_counter_destroy() non-blocking

      Signed-off-by: Al Viro <viro@zeniv.linux.org.uk>

lib/percpu_counter.c: __this_cpu_write() doesn't need to be protected by spinlock

      __this_cpu_write doesn't need to be protected by spinlock, AS we are doing
      per cpu write with preempt disabled.  And another reason to remove
      __this_cpu_write outside of spinlock: __percpu_counter_sum is not an
      accurate counter.

      Signed-off-by: Fan Du <fan.du@windriver.com>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

lib/percpu_counter.c: fix __percpu_counter_add()

      __percpu_counter_add() may be called in softirq/hardirq handler (such
      as, blk_mq_queue_exit() is typically called in hardirq/softirq handler),
      so we need to call this_cpu_add()(irq safe helper) to update percpu
      counter, otherwise counts may be lost.

      This fixes the problem that 'rmmod null_blk' hangs in blk_cleanup_queue()
      because of miscounting of request_queue->mq_usage_counter.

      This patch is the v1 of previous one of "lib/percpu_counter.c:
      disable local irq when updating percpu couter", and takes Andrew's
      approach which may be more efficient for ARCHs(x86, s390) that
      have optimized this_cpu_add().

      Signed-off-by: Ming Lei <tom.leiming@gmail.com>
      Cc: Paul Gortmaker <paul.gortmaker@windriver.com>
      Cc: Shaohua Li <shli@fusionio.com>
      Cc: Jens Axboe <axboe@kernel.dk>
      Cc: Fan Du <fan.du@windriver.com>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

percpu_counter: make APIs irq safe

      In my usage, sometimes the percpu APIs are called with irq locked,
      sometimes not. lockdep complains there is potential deadlock. Let's
      always use percpucounter lock in irq safe way. There should be no
      performance penality, as all those are slow code path.

      Cc: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Shaohua Li <shli@fusionio.com>
      Signed-off-by: Jens Axboe <axboe@kernel.dk>
cpu: rewrite cpu-notifier-error-inject module

Rewrite existing cpu-notifier-error-inject module to use debugfs based new
framework.

This change removes cpu_up_prepare_error and cpu_down_prepare_error module
parameters which were used to specify error code to be injected.  We could
keep these module parameters for backward compatibility by module_param_cb
but it seems overkill for this module.

This provides the ability to inject artifical errors to CPU notifier chain
callbacks.  It is controlled through debugfs interface under
/sys/kernel/debug/notifier-error-inject/cpu

If the notifier call chain should be failed with some events notified,
write the error code to "actions/<notifier event>/error".

Example1: inject CPU offline error (-1 == -EPERM)

	# cd /sys/kernel/debug/notifier-error-inject/cpu
	# echo -1 > actions/CPU_DOWN_PREPARE/error
	# echo 0 > /sys/devices/system/cpu/cpu1/online
	bash: echo: write error: Operation not permitted

Example2: inject CPU online error (-2 == -ENOENT)

	# cd /sys/kernel/debug/notifier-error-inject/cpu
	# echo -2 > actions/CPU_UP_PREPARE/error
	# echo 1 > /sys/devices/system/cpu/cpu1/online
	bash: echo: write error: No such file or directory

Signed-off-by: Akinobu Mita <akinobu.mita@gmail.com>
Cc: Pavel Machek <pavel@ucw.cz>
Cc: "Rafael J. Wysocki" <rjw@sisk.pl>
Cc: Greg KH <greg@kroah.com>
Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
Cc: Paul Mackerras <paulus@samba.org>
Cc: Michael Ellerman <michael@ellerman.id.au>
Cc: Dave Jones <davej@redhat.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
bootmem: fix wrong call parameter for free_bootmem()

It is strange that alloc_bootmem() returns a virtual address and
free_bootmem() requires a physical address.  Anyway, free_bootmem()'s
first parameter should be physical address.

There are some call sites for free_bootmem() with virtual address.  So fix
them.

[akpm@linux-foundation.org: improve free_bootmem() and free_bootmem_pate() documentation]
Signed-off-by: Joonsoo Kim <js1304@gmail.com>
Cc: Haavard Skinnemoen <hskinnemoen@gmail.com>
Cc: Hans-Christian Egtvedt <egtvedt@samfundet.no>
Cc: Johannes Weiner <hannes@cmpxchg.org>
Cc: FUJITA Tomonori <fujita.tomonori@lab.ntt.co.jp>
Cc: Benjamin Herrenschmidt <benh@kernel.crashing.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
lib/decompress: *squashing updates*

lib/decompress.c add __init to decompress_method and data

      Fix the warning:

	WARNING: vmlinux.o(.text+0x14cfd8): Section mismatch in reference from the variable compressed_formats to the function .init.text:gunzip()
	The function compressed_formats() references
	the function __init gunzip().
	etc..

      Within decompress.c, compressed_formats[] needs 'a __initdata annotation',
      because some of it's data members refer to functions which will be
      unloaded after init.

      Consequently, its user decompress_method() will get the __init prefix.

      Signed-off-by: Hein Tibosch <hein_tibosch@yahoo.es>
      Cc: Albin Tonnerre <albin.tonnerre@free-electrons.com>
      Cc: Phillip Lougher <phillip@lougher.demon.co.uk>
      Cc: "H. Peter Anvin" <hpa@zytor.com>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

lib/decompress.c: fix initconst

      Signed-off-by: Andi Kleen <andi@firstfloor.org>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

initramfs: debug detected compression method

      This can greatly aid in narrowing down the real source of initramfs
      problems such as failures related to the compression of the in-kernel
      initramfs when an external initramfs is in use as well.  Existing errors
      are ambiguous as to which initramfs is a problem and why.

      [akpm@linux-foundation.org: use pr_debug()]
      Signed-off-by: Daniel M. Weeks <dan@danweeks.net>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

lib/decompressors: fix "no limit" output buffer length

      When decompressing into memory, the output buffer length is set to some
      arbitrarily high value (0x7fffffff) to indicate the output is, virtually,
      unlimited in size.

      The problem with this is that some platforms have their physical memory at
      high physical addresses (0x80000000 or more), and that the output buffer
      address and its "unlimited" length cannot be added without overflowing.
      An example of this can be found in inflate_fast():

      /* next_out is the output buffer address */
      out = strm->next_out - OFF;
      /* avail_out is the output buffer size. end will overflow if the output
      * address is >= 0x80000104 */
      end = out + (strm->avail_out - 257);

      This has huge consequences on the performance of kernel decompression,
      since the following exit condition of inflate_fast() will be always true:

      } while (in < last && out < end);

      Indeed, "end" has overflowed and is now always lower than "out".  As a
      result, inflate_fast() will return after processing one single byte of
      input data, and will thus need to be called an unreasonably high number of
      times.  This probably went unnoticed because kernel decompression is fast
      enough even with this issue.

      Nonetheless, adjusting the output buffer length in such a way that the
      above pointer arithmetic never overflows results in a kernel decompression
      that is about 3 times faster on affected machines.

      Signed-off-by: Alexandre Courbot <acourbot@nvidia.com>
      Tested-by: Jon Medhurst <tixy@linaro.org>
      Cc: Stephen Warren <swarren@wwwdotorg.org>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

lib/decompress_inflate.c: include appropriate header file

      Include appropriate header file include/linux/decompress/inflate.h in
      lib/decompress_inflate.c because it has prototype declaration of
      function defined in lib/decompress_inflate.c.

      Also, fix the guard around the header file
      include/linux/decompress/inflate.h to use a more unique guard symbol.
      This avoids conflict with the INFLATE_H defined by
      zlib_inflate/inflate.h.

      This eliminates the following warning in lib/decompress_inflate.c:

	lib/decompress_inflate.c:35:17: warning: no previous prototype for `gunzip' [-Wmissing-prototypes]

      Signed-off-by: Rashika Kheria <rashika.kheria@gmail.com>
      Reviewed-by: Josh Triplett <josh@joshtriplett.org>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
lib/genalloc.c: *squashing updates*

lib: Pass the correct align offset to bitmap_find_next_zero_area_off

      bitmap_find_next_zero_area_off requires everything to be given in terms
      of bits. genpool no longer keeps track of everything in terms of bits
      so the start address must be shifted before passing to
      bitmap_find_next_zero_area_off. Without this, if the start address
      is unaligned, the code will not take this into account.

      Change-Id: I49e3dba51c48e2f97b03b21304e1258e83881c6b
      Signed-off-by: Laura Abbott <lauraa@codeaurora.org>

genalloc: stop crashing the system when destroying a pool

      The genalloc code uses the bitmap API from include/linux/bitmap.h and
      lib/bitmap.c, which is based on long values.  Both bitmap_set from
      lib/bitmap.c and bitmap_set_ll, which is the lockless version from
      genalloc.c, use BITMAP_LAST_WORD_MASK to set the first bits in a long in
      the bitmap.

      That one uses (1 << bits) - 1, 0b111, if you are setting the first three
      bits.  This means that the API counts from the least significant bits
      (LSB from now on) to the MSB.  The LSB in the first long is bit 0, then.
      The same works for the lookup functions.

      The genalloc code uses longs for the bitmap, as it should.  In
      include/linux/genalloc.h, struct gen_pool_chunk has unsigned long
      bits[0] as its last member.  When allocating the struct, genalloc should
      reserve enough space for the bitmap.  This should be a proper number of
      longs that can fit the amount of bits in the bitmap.

      However, genalloc allocates an integer number of bytes that fit the
      amount of bits, but may not be an integer amount of longs.  9 bytes, for
      example, could be allocated for 70 bits.

      This is a problem in itself if the Least Significat Bit in a long is in
      the byte with the largest address, which happens in Big Endian machines.
      This means genalloc is not allocating the byte in which it will try to
      set or check for a bit.

      This may end up in memory corruption, where genalloc will try to set the
      bits it has not allocated.  In fact, genalloc may not set these bits
      because it may find them already set, because they were not zeroed since
      they were not allocated.  And that's what causes a BUG when
      gen_pool_destroy is called and check for any set bits.

      What really happens is that genalloc uses kmalloc_node with __GFP_ZERO
      on gen_pool_add_virt.  With SLAB and SLUB, this means the whole slab
      will be cleared, not only the requested bytes.  Since struct
      gen_pool_chunk has a size that is a multiple of 8, and slab sizes are
      multiples of 8, we get lucky and allocate and clear the right amount of
      bytes.

      Hower, this is not the case with SLOB or with older code that did memset
      after allocating instead of using __GFP_ZERO.

      So, a simple module as this (running 3.6.0), will cause a crash when
      rmmod'ed.

	[root@phantom-lp2 foo]# cat foo.c
	#include <linux/kernel.h>
	#include <linux/module.h>
	#include <linux/init.h>
	#include <linux/genalloc.h>

	MODULE_LICENSE("GPL");
	MODULE_VERSION("0.1");

	static struct gen_pool *foo_pool;

	static __init int foo_init(void)
	{
		int ret;
		foo_pool = gen_pool_create(10, -1);
		if (!foo_pool)
			return -ENOMEM;
		ret = gen_pool_add(foo_pool, 0xa0000000, 32 << 10, -1);
		if (ret) {
			gen_pool_destroy(foo_pool);
			return ret;
		}
		return 0;
	}

	static __exit void foo_exit(void)
	{
		gen_pool_destroy(foo_pool);
	}

	module_init(foo_init);
	module_exit(foo_exit);
	[root@phantom-lp2 foo]# zcat /proc/config.gz | grep SLOB
	CONFIG_SLOB=y
	[root@phantom-lp2 foo]# insmod ./foo.ko
	[root@phantom-lp2 foo]# rmmod foo
	------------[ cut here ]------------
	kernel BUG at lib/genalloc.c:243!
	cpu 0x4: Vector: 700 (Program Check) at [c0000000bb0e7960]
	    pc: c0000000003cb50c: .gen_pool_destroy+0xac/0x110
	    lr: c0000000003cb4fc: .gen_pool_destroy+0x9c/0x110
	    sp: c0000000bb0e7be0
	  msr: 8000000000029032
	  current = 0xc0000000bb0e0000
	  paca    = 0xc000000006d30e00   softe: 0        irq_happened: 0x01
	    pid   = 13044, comm = rmmod
	kernel BUG at lib/genalloc.c:243!
	[c0000000bb0e7ca0] d000000004b00020 .foo_exit+0x20/0x38 [foo]
	[c0000000bb0e7d20] c0000000000dff98 .SyS_delete_module+0x1a8/0x290
	[c0000000bb0e7e30] c0000000000097d4 syscall_exit+0x0/0x94
	--- Exception: c00 (System Call) at 000000800753d1a0
	SP (fffd0b0e640) is in userspace

      Signed-off-by: Thadeu Lima de Souza Cascardo <cascardo@linux.vnet.ibm.com>
      Cc: Paul Gortmaker <paul.gortmaker@windriver.com>
      Cc: Benjamin Gaignard <benjamin.gaignard@stericsson.com>
      Cc: <stable@vger.kernel.org>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

lib/genalloc.c: fix overflow of ending address of memory chunk

      In struct gen_pool_chunk, end_addr means the end address of memory chunk
      (inclusive), but in the implementation it is treated as address + size of
      memory chunk (exclusive), so it points to the address plus one instead of
      correct ending address.

      The ending address of memory chunk plus one will cause overflow on the
      memory chunk including the last address of memory map, e.g.  when starting
      address is 0xFFF00000 and size is 0x100000 on 32bit machine, ending
      address will be 0x100000000.

      Use correct ending address like starting address + size - 1.

      [akpm@linux-foundation.org: add comment to struct gen_pool_chunk:end_addr]
      Signed-off-by: Joonyoung Shim <jy0922.shim@samsung.com>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

lib/genalloc.c: convert kmalloc_node(...GFP_ZERO...) to kzalloc_node(...)

      Use the helper function instead of __GFP_ZERO.

      Signed-off-by: Joe Perches <joe@perches.com>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
ARM: vfp: fix saving d16-d31 vfp registers on v6+ kernels

Michael Olbrich reported that his test program fails when built with
-O2 -mcpu=cortex-a8 -mfpu=neon, and a kernel which supports v6 and v7
CPUs:

volatile int x = 2;
volatile int64_t y = 2;

int main() {
	volatile int a = 0;
	volatile int64_t b = 0;
	while (1) {
		a = (a + x) % (1 << 30);
		b = (b + y) % (1 << 30);
		assert(a == b);
	}
}

and two instances are run.  When built for just v7 CPUs, this program
works fine.  It uses the "vadd.i64 d19, d18, d16" VFP instruction.

It appears that we do not save the high-16 double VFP registers across
context switches when the kernel is built for v6 CPUs.  Fix that.

Cc: <stable@vger.kernel.org>
Tested-By: Michael Olbrich <m.olbrich@pengutronix.de>
Signed-off-by: Russell King <rmk+kernel@arm.linux.org.uk>
rbtree: *squashing updates by Michel Lespinasse*

rbtree: reference Documentation/rbtree.txt for usage instructions

      I recently started looking at the rbtree code (with an eye towards
      improving the augmented rbtree support, but I haven't gotten there yet).
      I noticed a lot of possible speed improvements, which I am now proposing
      in this patch set.

      Patches 1-4 are preparatory: remove internal functions from rbtree.h so
      that users won't be tempted to use them instead of the documented APIs,
      clean up some incorrect usages I've noticed (in particular, with the
      recently added fs/proc/proc_sysctl.c rbtree usage), reference the
      documentation so that people have one less excuse to miss it, etc.

      Patch 5 is a small module I wrote to check the rbtree performance.  It
      creates 100 nodes with random keys and repeatedly inserts and erases them
      from an rbtree.  Additionally, it has code to check for rbtree invariants
      after each insert or erase operation.

      Patches 6-12 is where the rbtree optimizations are done, and they touch
      only that one file, lib/rbtree.c .  I am getting good results out of these
      - in my small benchmark doing rbtree insertion (including search) and
      erase, I'm seeing a 30% runtime reduction on Sandybridge E5, which is more
      than I initially thought would be possible.  (the results aren't as
      impressive on my two other test hosts though, AMD barcelona and Intel
      Westmere, where I am seeing 14% runtime reduction only).  The code size -
      both source (ommiting comments) and compiled - is also shorter after these
      changes.  However, I do admit that the updated code is more arduous to
      read - one big reason for that is the removal of the tree rotation
      helpers, which added some overhead but also made it easier to reason about
      things locally.  Overall, I believe this is an acceptable compromise,
      given that this code doesn't get modified very often, and that I have good
      tests for it.

      Upon Peter's suggestion, I added comments showing the rtree configuration
      before every rotation.  I think they help; however it's still best to have
      a copy of the cormen/leiserson/rivest book when digging into this code.

      This patch: reference Documentation/rbtree.txt for usage instructions

      include/linux/rbtree.h included some basic usage instructions, while
      Documentation/rbtree.txt had some more complete and easier to follow
      instructions.  Replacing the former with a reference to the latter.

      Signed-off-by: Michel Lespinasse <walken@google.com>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Acked-by: David Woodhouse <David.Woodhouse@intel.com>
      Cc: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Daniel Santos <daniel.santos@pobox.com>
      Cc: Jens Axboe <axboe@kernel.dk>
      Cc: "Eric W. Biederman" <ebiederm@xmission.com>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

rbtree: empty nodes have no color

      Empty nodes have no color.  We can make use of this property to simplify
      the code emitted by the RB_EMPTY_NODE and RB_CLEAR_NODE macros.  Also,
      we can get rid of the rb_init_node function which had been introduced by
      commit 88d19cf37952 ("timers: Add rb_init_node() to allow for stack
      allocated rb nodes") to avoid some issue with the empty node's color not
      being initialized.

      I'm not sure what the RB_EMPTY_NODE checks in rb_prev() / rb_next() are
      doing there, though.  axboe introduced them in commit 10fd48f2376d
      ("rbtree: fixed reversed RB_EMPTY_NODE and rb_next/prev").  The way I
      see it, the 'empty node' abstraction is only used by rbtree users to
      flag nodes that they haven't inserted in any rbtree, so asking the
      predecessor or successor of such nodes doesn't make any sense.

      One final rb_init_node() caller was recently added in sysctl code to
      implement faster sysctl name lookups.  This code doesn't make use of
      RB_EMPTY_NODE at all, and from what I could see it only called
      rb_init_node() under the mistaken assumption that such initialization was
      required before node insertion.

      [sfr@canb.auug.org.au: fix net/ceph/osd_client.c build]
      Signed-off-by: Michel Lespinasse <walken@google.com>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Acked-by: David Woodhouse <David.Woodhouse@intel.com>
      Cc: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Daniel Santos <daniel.santos@pobox.com>
      Cc: Jens Axboe <axboe@kernel.dk>
      Cc: "Eric W. Biederman" <ebiederm@xmission.com>
      Cc: John Stultz <john.stultz@linaro.org>
      Signed-off-by: Stephen Rothwell <sfr@canb.auug.org.au>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

rbtree: fix incorrect rbtree node insertion in fs/proc/proc_sysctl.c

      The recently added code to use rbtrees in sysctl did not follow the proper
      rbtree interface on insertion - it was calling rb_link_node() which
      inserts a new node into the binary tree, but missed the call to
      rb_insert_color() which properly balances the rbtree and establishes all
      expected rbtree invariants.

      I found out about this only because faulty commit also used
      rb_init_node(), which I am removing within this patchset.  But I think
      it's an easy mistake to make, and it makes me wonder if we should change
      the rbtree API so that insertions would be done with a single rb_insert()
      call (even if its implementation could still inline the rb_link_node()
      part and call a private __rb_insert_color function to do the rebalancing).

      Signed-off-by: Michel Lespinasse <walken@google.com>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Acked-by: David Woodhouse <David.Woodhouse@intel.com>
      Cc: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Daniel Santos <daniel.santos@pobox.com>
      Cc: Jens Axboe <axboe@kernel.dk>
      Cc: "Eric W. Biederman" <ebiederm@xmission.com>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

rbtree: move some implementation details from rbtree.h to rbtree.c

      rbtree users must use the documented APIs to manipulate the tree
      structure.  Low-level helpers to manipulate node colors and parenthood are
      not part of that API, so move them to lib/rbtree.c

      [dwmw2@infradead.org: fix jffs2 build issue due to renamed __rb_parent_color field]
      Signed-off-by: Michel Lespinasse <walken@google.com>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Acked-by: David Woodhouse <David.Woodhouse@intel.com>
      Cc: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Daniel Santos <daniel.santos@pobox.com>
      Cc: Jens Axboe <axboe@kernel.dk>
      Cc: "Eric W. Biederman" <ebiederm@xmission.com>
      Signed-off-by: David Woodhouse <David.Woodhouse@intel.com>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

rbtree: performance and correctness test

      This small module helps measure the performance of rbtree insert and
      erase.

      Additionally, we run a few correctness tests to check that the rbtrees
      have all desired properties:

      - contains the right number of nodes in the order desired,
      - never two consecutive red nodes on any path,
      - all paths to leaf nodes have the same number of black nodes,
      - root node is black

      [akpm@linux-foundation.org: fix printk warning: sparc64 cycles_t is unsigned long]
      Signed-off-by: Michel Lespinasse <walken@google.com>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Acked-by: David Woodhouse <David.Woodhouse@intel.com>
      Cc: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Daniel Santos <daniel.santos@pobox.com>
      Cc: Jens Axboe <axboe@kernel.dk>
      Cc: "Eric W. Biederman" <ebiederm@xmission.com>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

rbtree: break out of rb_insert_color loop after tree rotation

      It is a well known property of rbtrees that insertion never requires more
      than two tree rotations.  In our implementation, after one loop iteration
      identified one or two necessary tree rotations, we would iterate and look
      for more.  However at that point the node's parent would always be black,
      which would cause us to exit the loop.

      We can make the code flow more obvious by just adding a break statement
      after the tree rotations, where we know we are done.  Additionally, in the
      cases where two tree rotations are necessary, we don't have to update the
      'node' pointer as it wouldn't be used until the next loop iteration, which
      we now avoid due to this break statement.

      Signed-off-by: Michel Lespinasse <walken@google.com>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Acked-by: David Woodhouse <David.Woodhouse@intel.com>
      Cc: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Daniel Santos <daniel.santos@pobox.com>
      Cc: Jens Axboe <axboe@kernel.dk>
      Cc: "Eric W. Biederman" <ebiederm@xmission.com>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

rbtree: adjust root color in rb_insert_color() only when necessary

      The root node of an rbtree must always be black.  However,
      rb_insert_color() only needs to maintain this invariant when it has been
      broken - that is, when it exits the loop due to the current (red) node
      being the root.  In all other cases (exiting after tree rotations, or
      exiting due to an existing black parent) the invariant is already
      satisfied, so there is no need to adjust the root node color.

      Signed-off-by: Michel Lespinasse <walken@google.com>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Acked-by: David Woodhouse <David.Woodhouse@intel.com>
      Cc: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Daniel Santos <daniel.santos@pobox.com>
      Cc: Jens Axboe <axboe@kernel.dk>
      Cc: "Eric W. Biederman" <ebiederm@xmission.com>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

rbtree: low level optimizations in rb_insert_color()

      - Use the newly introduced rb_set_parent_color() function to flip the color
	of nodes whose parent is already known.
      - Optimize rb_parent() when the node is known to be red - there is no need
	to mask out the color in that case.
      - Flipping gparent's color to red requires us to fetch its rb_parent_color
	field, so we can reuse it as the parent value for the next loop iteration.
      - Do not use __rb_rotate_left() and __rb_rotate_right() to handle tree
	rotations: we already have pointers to all relevant nodes, and know their
	colors (either because we want to adjust it, or because we've tested it,
	or we can deduce it as black due to the node proximity to a known red node).
	So we can generate more efficient code by making use of the node pointers
	we already have, and setting both the parent and color attributes for
	nodes all at once. Also in Case 2, some node attributes don't have to
	be set because we know another tree rotation (Case 3) will always follow
	and override them.

      Signed-off-by: Michel Lespinasse <walken@google.com>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Acked-by: David Woodhouse <David.Woodhouse@intel.com>
      Cc: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Daniel Santos <daniel.santos@pobox.com>
      Cc: Jens Axboe <axboe@kernel.dk>
      Cc: "Eric W. Biederman" <ebiederm@xmission.com>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

rbtree: adjust node color in __rb_erase_color() only when necessary

      In __rb_erase_color(), we were always setting a node to black after
      exiting the main loop.  And in one case, after fixing up the tree to
      satisfy all rbtree invariants, we were setting the current node to root
      just to guarantee a loop exit, at which point the root would be set to
      black.  However this is not necessary, as the root of an rbtree is already
      known to be black.  The only case where the color flip is required is when
      we exit the loop due to the current node being red, and it's easiest to
      just do the flip at that point instead of doing it after the loop.

      [adrian.hunter@intel.com: perf tools: fix build for another rbtree.c change]
      Signed-off-by: Michel Lespinasse <walken@google.com>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Acked-by: David Woodhouse <David.Woodhouse@intel.com>
      Cc: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Daniel Santos <daniel.santos@pobox.com>
      Cc: Jens Axboe <axboe@kernel.dk>
      Cc: "Eric W. Biederman" <ebiederm@xmission.com>
      Signed-off-by: Adrian Hunter <adrian.hunter@intel.com>
      Cc: Alexander Shishkin <alexander.shishkin@intel.com>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

rbtree: optimize case selection logic in __rb_erase_color()

      In __rb_erase_color(), we have to select one of 3 cases depending on the
      color on the 'other' node children.  If both children are black, we flip a
      few node colors and iterate.  Otherwise, we do either one or two tree
      rotations, depending on the color of the 'other' child opposite to 'node',
      and then we are done.

      The corresponding logic had duplicate checks for the color of the 'other'
      child opposite to 'node'.  It was checking it first to determine if both
      children are black, and then to determine how many tree rotations are
      required.  Rearrange the logic to avoid that extra check.

      Signed-off-by: Michel Lespinasse <walken@google.com>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Acked-by: David Woodhouse <David.Woodhouse@intel.com>
      Cc: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Daniel Santos <daniel.santos@pobox.com>
      Cc: Jens Axboe <axboe@kernel.dk>
      Cc: "Eric W. Biederman" <ebiederm@xmission.com>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

rbtree: low level optimizations in __rb_erase_color()

      In __rb_erase_color(), we often already have pointers to the nodes being
      rotated and/or know what their colors must be, so we can generate more
      efficient code than the generic __rb_rotate_left() and __rb_rotate_right()
      functions.

      Also when the current node is red or when flipping the sibling's color,
      the parent is already known so we can use the more efficient
      rb_set_parent_color() function to set the desired color.

      Signed-off-by: Michel Lespinasse <walken@google.com>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Acked-by: David Woodhouse <David.Woodhouse@intel.com>
      Cc: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Daniel Santos <daniel.santos@pobox.com>
      Cc: Jens Axboe <axboe@kernel.dk>
      Cc: "Eric W. Biederman" <ebiederm@xmission.com>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

rbtree: coding style adjustments

      Set comment and indentation style to be consistent with linux coding style
      and the rest of the file, as suggested by Peter Zijlstra

      Signed-off-by: Michel Lespinasse <walken@google.com>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Acked-by: David Woodhouse <David.Woodhouse@intel.com>
      Cc: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Daniel Santos <daniel.santos@pobox.com>
      Cc: Jens Axboe <axboe@kernel.dk>
      Cc: "Eric W. Biederman" <ebiederm@xmission.com>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

rbtree: optimize fetching of sibling node

      When looking to fetch a node's sibling, we went through a sequence of:
      - check if node is the parent's left child
      - if it is, then fetch the parent's right child

      This can be replaced with:
      - fetch the parent's right child as an assumed sibling
      - check that node is NOT the fetched child

      This avoids fetching the parent's left child when node is actually
      that child. Saves a bit on code size, though it doesn't seem to make
      a large difference in speed.

      Signed-off-by: Michel Lespinasse <walken@google.com>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Cc: David Woodhouse <David.Woodhouse@intel.com>
      Acked-by: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Daniel Santos <daniel.santos@pobox.com>
      Cc: Jens Axboe <axboe@kernel.dk>
      Cc: "Eric W. Biederman" <ebiederm@xmission.com>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

rbtree test: fix sparse warning about 64-bit constant

      Just a small fix to make sparse happy.

      Signed-off-by: Michel Lespinasse <walken@google.com>
      Reported-by: Fengguang Wu <wfg@linux.intel.com>
      Acked-by: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Cc: David Woodhouse <dwmw2@infradead.org>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

rbtree: add __rb_change_child() helper function

      Add __rb_change_child() as an inline helper function to replace code that
      would otherwise be duplicated 4 times in the source.

      No changes to binary size or speed.

      Signed-off-by: Michel Lespinasse <walken@google.com>
      Reviewed-by: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Cc: David Woodhouse <dwmw2@infradead.org>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

rbtree: place easiest case first in rb_erase()

      In rb_erase, move the easy case (node to erase has no more than
      1 child) first. I feel the code reads easier that way.

      Signed-off-by: Michel Lespinasse <walken@google.com>
      Reviewed-by: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Cc: David Woodhouse <dwmw2@infradead.org>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

      # This is the 17th commit message:

      rbtree: handle 1-child recoloring in rb_erase() instead of rb_erase_color()

      An interesting observation for rb_erase() is that when a node has
      exactly one child, the node must be black and the child must be red.
      An interesting consequence is that removing such a node can be done by
      simply replacing it with its child and making the child black,
      which we can do efficiently in rb_erase(). __rb_erase_color() then
      only needs to handle the no-childs case and can be modified accordingly.

      Signed-off-by: Michel Lespinasse <walken@google.com>
      Acked-by: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Cc: David Woodhouse <dwmw2@infradead.org>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

rbtree: low level optimizations in rb_erase()

      Various minor optimizations in rb_erase():
      - Avoid multiple loading of node->__rb_parent_color when computing parent
	and color information (possibly not in close sequence, as there might
	be further branches in the algorithm)
      - In the 1-child subcase of case 1, copy the __rb_parent_color field from
	the erased node to the child instead of recomputing it from the desired
	parent and color
      - When searching for the erased node's successor, differentiate between
	cases 2 and 3 based on whether any left links were followed. This avoids
	a condition later down.
      - In case 3, keep a pointer to the erased node's right child so we don't
	have to refetch it later to adjust its parent.
      - In the no-childs subcase of cases 2 and 3, place the rebalance assigment
	last so that the compiler can remove the following if(rebalance) test.

      Also, added some comments to illustrate cases 2 and 3.

      Signed-off-by: Michel Lespinasse <walken@google.com>
      Acked-by: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Cc: David Woodhouse <dwmw2@infradead.org>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

rbtree: augmented rbtree test

      Small test to measure the performance of augmented rbtrees.

      Signed-off-by: Michel Lespinasse <walken@google.com>
      Acked-by: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Cc: David Woodhouse <dwmw2@infradead.org>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

rbtree: faster augmented rbtree manipulation

      Introduce new augmented rbtree APIs that allow minimal recalculation of
      augmented node information.

      A new callback is added to the rbtree insertion and erase rebalancing
      functions, to be called on each tree rotations. Such rotations preserve
      the subtree's root augmented value, but require recalculation of the one
      child that was previously located at the subtree root.

      In the insertion case, the handcoded search phase must be updated to
      maintain the augmented information on insertion, and then the rbtree
      coloring/rebalancing algorithms keep it up to date.

      In the erase case, things are more complicated since it is library
      code that manipulates the rbtree in order to remove internal nodes.
      This requires a couple additional callbacks to copy a subtree's
      augmented value when a new root is stitched in, and to recompute
      augmented values down the ancestry path when a node is removed from
      the tree.

      In order to preserve maximum speed for the non-augmented case,
      we provide two versions of each tree manipulation function.
      rb_insert_augmented() is the augmented equivalent of rb_insert_color(),
      and rb_erase_augmented() is the augmented equivalent of rb_erase().

      Signed-off-by: Michel Lespinasse <walken@google.com>
      Acked-by: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Cc: David Woodhouse <dwmw2@infradead.org>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

rbtree: remove prior augmented rbtree implementation

      convert arch/x86/mm/pat_rbtree.c to the proposed augmented rbtree api
      and remove the old augmented rbtree implementation.

      Signed-off-by: Michel Lespinasse <walken@google.com>
      Acked-by: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Cc: David Woodhouse <dwmw2@infradead.org>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

rbtree: add RB_DECLARE_CALLBACKS() macro

      As proposed by Peter Zijlstra, this makes it easier to define the augmented
      rbtree callbacks.

      Signed-off-by: Michel Lespinasse <walken@google.com>
      Cc: Rik van Riel <riel@redhat.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Cc: David Woodhouse <dwmw2@infradead.org>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

rbtree: add prio tree and interval tree tests

      Patch 1 implements support for interval trees, on top of the augmented
      rbtree API. It also adds synthetic tests to compare the performance of
      interval trees vs prio trees. Short answers is that interval trees are
      slightly faster (~25%) on insert/erase, and much faster (~2.4 - 3x)
      on search. It is debatable how realistic the synthetic test is, and I have
      not made such measurements yet, but my impression is that interval trees
      would still come out faster.

      Patch 2 uses a preprocessor template to make the interval tree generic,
      and uses it as a replacement for the vma prio_tree.

      Patch 3 takes the other prio_tree user, kmemleak, and converts it to use
      a basic rbtree. We don't actually need the augmented rbtree support here
      because the intervals are always non-overlapping.

      Patch 4 removes the now-unused prio tree library.

      Patch 5 proposes an additional optimization to rb_erase_augmented, now
      providing it as an inline function so that the augmented callbacks can be
      inlined in. This provides an additional 5-10% performance improvement
      for the interval tree insert/erase benchmark. There is a maintainance cost
      as it exposes augmented rbtree users to some of the rbtree library internals;
      however I think this cost shouldn't be too high as I expect the augmented
      rbtree will always have much less users than the base rbtree.

      I should probably add a quick summary of why I think it makes sense to
      replace prio trees with augmented rbtree based interval trees now.  One of
      the drivers is that we need augmented rbtrees for Rik's vma gap finding
      code, and once you have them, it just makes sense to use them for interval
      trees as well, as this is the simpler and more well known algorithm.  prio
      trees, in comparison, seem *too* clever: they impose an additional 'heap'
      constraint on the tree, which they use to guarantee a faster worst-case
      complexity of O(k+log N) for stabbing queries in a well-balanced prio
      tree, vs O(k*log N) for interval trees (where k=number of matches,
      N=number of intervals).  Now this sounds great, but in practice prio trees
      don't realize this theorical benefit.  First, the additional constraint
      makes them harder to update, so that the kernel implementation has to
      simplify things by balancing them like a radix tree, which is not always
      ideal.  Second, the fact that there are both index and heap properties
      makes both tree manipulation and search more complex, which results in a
      higher multiplicative time constant.  As it turns out, the simple interval
      tree algorithm ends up running faster than the more clever prio tree.

      This patch:

      Add two test modules:

      - prio_tree_test measures the performance of lib/prio_tree.c, both for
	insertion/removal and for stabbing searches

      - interval_tree_test measures the performance of a library of equivalent
	functionality, built using the augmented rbtree support.

      In order to support the second test module, lib/interval_tree.c is
      introduced. It is kept separate from the interval_tree_test main file
      for two reasons: first we don't want to provide an unfair advantage
      over prio_tree_test by having everything in a single compilation unit,
      and second there is the possibility that the interval tree functionality
      could get some non-test users in kernel over time.

      Signed-off-by: Michel Lespinasse <walken@google.com>
      Cc: Rik van Riel <riel@redhat.com>
      Cc: Hillf Danton <dhillf@gmail.com>
      Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
      Cc: Catalin Marinas <catalin.marinas@arm.com>
      Cc: Andrea Arcangeli <aarcange@redhat.com>
      Cc: David Woodhouse <dwmw2@infradead.org>
      Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
      Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
mm: replace vma prio_tree with an interval tree

Implement an interval tree as a replacement for the VMA prio_tree.  The
algorithms are similar to lib/interval_tree.c; however that code can't be
directly reused as the interval endpoints are not explicitly stored in the
VMA.  So instead, the common algorithm is moved into a template and the
details (node type, how to get interval endpoints from the node, etc) are
filled in using the C preprocessor.

Once the interval tree functions are available, using them as a
replacement to the VMA prio tree is a relatively simple, mechanical job.

Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Hillf Danton <dhillf@gmail.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Catalin Marinas <catalin.marinas@arm.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: David Woodhouse <dwmw2@infradead.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
kmemleak: use rbtree instead of prio tree

kmemleak uses a tree where each node represents an allocated memory object
in order to quickly find out what object a given address is part of.
However, the objects don't overlap, so rbtrees are a better choice than
prio tree for this use.  They are both faster and have lower memory
overhead.

Tested by booting a kernel with kmemleak enabled, loading the
kmemleak_test module, and looking for the expected messages.

Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Hillf Danton <dhillf@gmail.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: David Woodhouse <dwmw2@infradead.org>
Acked-by: Catalin Marinas <catalin.marinas@arm.com>
Tested-by: Catalin Marinas <catalin.marinas@arm.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
prio_tree: remove

After both prio_tree users have been converted to use red-black trees,
there is no need to keep around the prio tree library anymore.

Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Hillf Danton <dhillf@gmail.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Catalin Marinas <catalin.marinas@arm.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: David Woodhouse <dwmw2@infradead.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
rbtree: move augmented rbtree functionality to rbtree_augmented.h

Provide rb_insert_augmented() and rb_erase_augmented() through a new
rbtree_augmented.h include file.  rb_erase_augmented() is defined there as
an __always_inline function, in order to allow inlining of augmented
rbtree callbacks into it.  Since this generates a relatively large
function, each augmented rbtree user should make sure to have a single
call site.

Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Hillf Danton <dhillf@gmail.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Catalin Marinas <catalin.marinas@arm.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: David Woodhouse <dwmw2@infradead.org>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
mm: interval tree updates

Update the generic interval tree code that was introduced in "mm: replace
vma prio_tree with an interval tree".

Changes:

- fixed 'endpoing' typo noticed by Andrew Morton

- replaced include/linux/interval_tree_tmpl.h, which was used as a
  template (including it automatically defined the interval tree
  functions) with include/linux/interval_tree_generic.h, which only
  defines a preprocessor macro INTERVAL_TREE_DEFINE(), which itself
  defines the interval tree functions when invoked. Now that is a very
  long macro which is unfortunate, but it does make the usage sites
  (lib/interval_tree.c and mm/interval_tree.c) a bit nicer than previously.

- make use of RB_DECLARE_CALLBACKS() in the INTERVAL_TREE_DEFINE() macro,
  instead of duplicating that code in the interval tree template.

- replaced vma_interval_tree_add(), which was actually handling the
  nonlinear and interval tree cases, with vma_interval_tree_insert_after()
  which handles only the interval tree case and has an API that is more
  consistent with the other interval tree handling functions.
  The nonlinear case is now handled explicitly in kernel/fork.c dup_mmap().

Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Hugh Dickins <hughd@google.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
mm anon rmap: remove anon_vma_moveto_tail

mremap() had a clever optimization where move_ptes() did not take the
anon_vma lock to avoid a race with anon rmap users such as page migration.
 Instead, the avc's were ordered in such a way that the origin vma was
always visited by rmap before the destination.  This ordering and the use
of page table locks rmap usage safe.  However, we want to replace the use
of linked lists in anon rmap with an interval tree, and this will make it
harder to impose such ordering as the interval tree will always be sorted
by the avc->vma->vm_pgoff value.  For now, let's replace the
anon_vma_moveto_tail() ordering function with proper anon_vma locking in
move_ptes().  Once we have the anon interval tree in place, we will
re-introduce an optimization to avoid taking these locks in the most
common cases.

Signed-off-by: Michel Lespinasse <walken@google.com>
Cc: Andrea Arcangeli <aarcange@redhat.com>
Cc: Rik van Riel <riel@redhat.com>
Cc: Peter Zijlstra <a.p.zijlstra@chello.nl>
Cc: Daniel Santos <daniel.santos@pobox.com>
Cc: Hugh Dickins <hughd@google.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>