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>

1 files changed, 2 insertions, 2 deletions

diff --git a/mm/Makefile b/mm/Makefile
index 92753e2d82da..6b025f80af34 100644
--- a/mm/Makefile
+++ b/mm/Makefile
@@ -14,9 +14,9 @@ endif
 obj-y                   := filemap.o mempool.o oom_kill.o fadvise.o \
                            maccess.o page_alloc.o page-writeback.o \
                            readahead.o swap.o truncate.o vmscan.o shmem.o \
-                           prio_tree.o util.o mmzone.o vmstat.o backing-dev.o \
+                           util.o mmzone.o vmstat.o backing-dev.o \
                            mm_init.o mmu_context.o percpu.o slab_common.o \
-                           compaction.o $(mmu-y)
+                           compaction.o interval_tree.o $(mmu-y)
 
 obj-y += init-mm.o