mm: replace vma prio_tree with an interval tree
authorMichel Lespinasse <walken@google.com>
Mon, 8 Oct 2012 23:31:25 +0000 (16:31 -0700)
committerLinus Torvalds <torvalds@linux-foundation.org>
Tue, 9 Oct 2012 07:22:39 +0000 (16:22 +0900)
commit6b2dbba8b6ac4df26f72eda1e5ea7bab9f950e08
tree422ed8d7ac2fe45069f20cfba84a9a097bf444af
parentfff3fd8a1210a165252cd7cd01206da7a90d3a06
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>
25 files changed:
arch/arm/mm/fault-armv.c
arch/arm/mm/flush.c
arch/parisc/kernel/cache.c
arch/x86/mm/hugetlbpage.c
fs/hugetlbfs/inode.c
fs/inode.c
include/linux/fs.h
include/linux/interval_tree_tmpl.h [new file with mode: 0644]
include/linux/mm.h
include/linux/mm_types.h
kernel/events/uprobes.c
kernel/fork.c
lib/interval_tree.c
lib/prio_tree.c
mm/Makefile
mm/filemap_xip.c
mm/fremap.c
mm/hugetlb.c
mm/interval_tree.c [new file with mode: 0644]
mm/memory-failure.c
mm/memory.c
mm/mmap.c
mm/nommu.c
mm/prio_tree.c [deleted file]
mm/rmap.c