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>

11 files changed, 94 insertions, 251 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
 
diff --git a/mm/filemap_xip.c b/mm/filemap_xip.c
index 91750227a191..a52daee11d3f 100644
--- a/mm/filemap_xip.c
+++ b/mm/filemap_xip.c
@@ -167,7 +167,6 @@ __xip_unmap (struct address_space * mapping,
 {
         struct vm_area_struct *vma;
         struct mm_struct *mm;
-        struct prio_tree_iter iter;
         unsigned long address;
         pte_t *pte;
         pte_t pteval;
@@ -184,7 +183,7 @@ __xip_unmap (struct address_space * mapping,
 
 retry:
         mutex_lock(&mapping->i_mmap_mutex);
-        vma_prio_tree_foreach(vma, &iter, &mapping->i_mmap, pgoff, pgoff) {
+        vma_interval_tree_foreach(vma, &mapping->i_mmap, pgoff, pgoff) {
                 mm = vma->vm_mm;
                 address = vma->vm_start +
                         ((pgoff - vma->vm_pgoff) << PAGE_SHIFT);
diff --git a/mm/fremap.c b/mm/fremap.c
index 3d731a498788..3899a86851ce 100644
--- a/mm/fremap.c
+++ b/mm/fremap.c
@@ -214,7 +214,7 @@ SYSCALL_DEFINE5(remap_file_pages, unsigned long, start, unsigned long, size,
                 mutex_lock(&mapping->i_mmap_mutex);
                 flush_dcache_mmap_lock(mapping);
                 vma->vm_flags |= VM_NONLINEAR;
-                vma_prio_tree_remove(vma, &mapping->i_mmap);
+                vma_interval_tree_remove(vma, &mapping->i_mmap);
                 vma_nonlinear_insert(vma, &mapping->i_mmap_nonlinear);
                 flush_dcache_mmap_unlock(mapping);
                 mutex_unlock(&mapping->i_mmap_mutex);
diff --git a/mm/hugetlb.c b/mm/hugetlb.c
index f1bb534254f6..c9b40e3a9936 100644
--- a/mm/hugetlb.c
+++ b/mm/hugetlb.c
@@ -2474,7 +2474,6 @@ static int unmap_ref_private(struct mm_struct *mm, struct vm_area_struct *vma,
         struct hstate *h = hstate_vma(vma);
         struct vm_area_struct *iter_vma;
         struct address_space *mapping;
-        struct prio_tree_iter iter;
         pgoff_t pgoff;
 
         /*
@@ -2491,7 +2490,7 @@ static int unmap_ref_private(struct mm_struct *mm, struct vm_area_struct *vma,
          * __unmap_hugepage_range() is called as the lock is already held
          */
         mutex_lock(&mapping->i_mmap_mutex);
-        vma_prio_tree_foreach(iter_vma, &iter, &mapping->i_mmap, pgoff, pgoff) {
+        vma_interval_tree_foreach(iter_vma, &mapping->i_mmap, pgoff, pgoff) {
                 /* Do not unmap the current VMA */
                 if (iter_vma == vma)
                         continue;
diff --git a/mm/interval_tree.c b/mm/interval_tree.c
new file mode 100644
index 000000000000..7dc565660e56
--- /dev/null
+++ b/mm/interval_tree.c
@@ -0,0 +1,61 @@
+/*
+ * mm/interval_tree.c - interval tree for mapping->i_mmap
+ *
+ * Copyright (C) 2012, Michel Lespinasse <walken@google.com>
+ *
+ * This file is released under the GPL v2.
+ */
+
+#include <linux/mm.h>
+#include <linux/fs.h>
+
+#define ITSTRUCT   struct vm_area_struct
+#define ITRB       shared.linear.rb
+#define ITTYPE     unsigned long
+#define ITSUBTREE  shared.linear.rb_subtree_last
+#define ITSTART(n) ((n)->vm_pgoff)
+#define ITLAST(n)  ((n)->vm_pgoff + \
+                    (((n)->vm_end - (n)->vm_start) >> PAGE_SHIFT) - 1)
+#define ITSTATIC
+#define ITPREFIX   vma_interval_tree
+
+#include <linux/interval_tree_tmpl.h>
+
+/* Insert old immediately after vma in the interval tree */
+void vma_interval_tree_add(struct vm_area_struct *vma,
+                           struct vm_area_struct *old,
+                           struct address_space *mapping)
+{
+        struct rb_node **link;
+        struct vm_area_struct *parent;
+        unsigned long last;
+
+        if (unlikely(vma->vm_flags & VM_NONLINEAR)) {
+                list_add(&vma->shared.nonlinear, &old->shared.nonlinear);
+                return;
+        }
+
+        last = ITLAST(vma);
+
+        if (!old->shared.linear.rb.rb_right) {
+                parent = old;
+                link = &old->shared.linear.rb.rb_right;
+        } else {
+                parent = rb_entry(old->shared.linear.rb.rb_right,
+                                  struct vm_area_struct, shared.linear.rb);
+                if (parent->shared.linear.rb_subtree_last < last)
+                        parent->shared.linear.rb_subtree_last = last;
+                while (parent->shared.linear.rb.rb_left) {
+                        parent = rb_entry(parent->shared.linear.rb.rb_left,
+                                struct vm_area_struct, shared.linear.rb);
+                        if (parent->shared.linear.rb_subtree_last < last)
+                                parent->shared.linear.rb_subtree_last = last;
+                }
+                link = &parent->shared.linear.rb.rb_left;
+        }
+
+        vma->shared.linear.rb_subtree_last = last;
+        rb_link_node(&vma->shared.linear.rb, &parent->shared.linear.rb, link);
+        rb_insert_augmented(&vma->shared.linear.rb, &mapping->i_mmap,
+                            &vma_interval_tree_augment_callbacks);
+}
diff --git a/mm/memory-failure.c b/mm/memory-failure.c
index a6e2141a6610..c38a6257d082 100644
--- a/mm/memory-failure.c
+++ b/mm/memory-failure.c
@@ -431,7 +431,6 @@ static void collect_procs_file(struct page *page, struct list_head *to_kill,
 {
         struct vm_area_struct *vma;
         struct task_struct *tsk;
-        struct prio_tree_iter iter;
         struct address_space *mapping = page->mapping;
 
         mutex_lock(&mapping->i_mmap_mutex);
@@ -442,7 +441,7 @@ static void collect_procs_file(struct page *page, struct list_head *to_kill,
                 if (!task_early_kill(tsk))
                         continue;
 
-                vma_prio_tree_foreach(vma, &iter, &mapping->i_mmap, pgoff,
+                vma_interval_tree_foreach(vma, &mapping->i_mmap, pgoff,
                                       pgoff) {
                         /*
                          * Send early kill signal to tasks where a vma covers
diff --git a/mm/memory.c b/mm/memory.c
index e09c04813186..d205e4381a34 100644
--- a/mm/memory.c
+++ b/mm/memory.c
@@ -2801,14 +2801,13 @@ static void unmap_mapping_range_vma(struct vm_area_struct *vma,
         zap_page_range_single(vma, start_addr, end_addr - start_addr, details);
 }
 
-static inline void unmap_mapping_range_tree(struct prio_tree_root *root,
+static inline void unmap_mapping_range_tree(struct rb_root *root,
                                             struct zap_details *details)
 {
         struct vm_area_struct *vma;
-        struct prio_tree_iter iter;
         pgoff_t vba, vea, zba, zea;
 
-        vma_prio_tree_foreach(vma, &iter, root,
+        vma_interval_tree_foreach(vma, root,
                         details->first_index, details->last_index) {
 
                 vba = vma->vm_pgoff;
@@ -2839,7 +2838,7 @@ static inline void unmap_mapping_range_list(struct list_head *head,
          * across *all* the pages in each nonlinear VMA, not just the pages
          * whose virtual address lies outside the file truncation point.
          */
-        list_for_each_entry(vma, head, shared.vm_set.list) {
+        list_for_each_entry(vma, head, shared.nonlinear) {
                 details->nonlinear_vma = vma;
                 unmap_mapping_range_vma(vma, vma->vm_start, vma->vm_end, details);
         }
@@ -2883,7 +2882,7 @@ void unmap_mapping_range(struct address_space *mapping,
 
 
         mutex_lock(&mapping->i_mmap_mutex);
-        if (unlikely(!prio_tree_empty(&mapping->i_mmap)))
+        if (unlikely(!RB_EMPTY_ROOT(&mapping->i_mmap)))
                 unmap_mapping_range_tree(&mapping->i_mmap, &details);
         if (unlikely(!list_empty(&mapping->i_mmap_nonlinear)))
                 unmap_mapping_range_list(&mapping->i_mmap_nonlinear, &details);
diff --git a/mm/mmap.c b/mm/mmap.c
index e3c365ff1b6a..5ac533f88e99 100644
--- a/mm/mmap.c
+++ b/mm/mmap.c
@@ -199,14 +199,14 @@ static void __remove_shared_vm_struct(struct vm_area_struct *vma,
 
         flush_dcache_mmap_lock(mapping);
         if (unlikely(vma->vm_flags & VM_NONLINEAR))
-                list_del_init(&vma->shared.vm_set.list);
+                list_del_init(&vma->shared.nonlinear);
         else
-                vma_prio_tree_remove(vma, &mapping->i_mmap);
+                vma_interval_tree_remove(vma, &mapping->i_mmap);
         flush_dcache_mmap_unlock(mapping);
 }
 
 /*
- * Unlink a file-based vm structure from its prio_tree, to hide
+ * Unlink a file-based vm structure from its interval tree, to hide
  * vma from rmap and vmtruncate before freeing its page tables.
  */
 void unlink_file_vma(struct vm_area_struct *vma)
@@ -411,7 +411,7 @@ static void __vma_link_file(struct vm_area_struct *vma)
                 if (unlikely(vma->vm_flags & VM_NONLINEAR))
                         vma_nonlinear_insert(vma, &mapping->i_mmap_nonlinear);
                 else
-                        vma_prio_tree_insert(vma, &mapping->i_mmap);
+                        vma_interval_tree_insert(vma, &mapping->i_mmap);
                 flush_dcache_mmap_unlock(mapping);
         }
 }
@@ -449,7 +449,7 @@ static void vma_link(struct mm_struct *mm, struct vm_area_struct *vma,
 
 /*
  * Helper for vma_adjust() in the split_vma insert case: insert a vma into the
- * mm's list and rbtree.  It has already been inserted into the prio_tree.
+ * mm's list and rbtree.  It has already been inserted into the interval tree.
  */
 static void __insert_vm_struct(struct mm_struct *mm, struct vm_area_struct *vma)
 {
@@ -491,7 +491,7 @@ int vma_adjust(struct vm_area_struct *vma, unsigned long start,
         struct vm_area_struct *next = vma->vm_next;
         struct vm_area_struct *importer = NULL;
         struct address_space *mapping = NULL;
-        struct prio_tree_root *root = NULL;
+        struct rb_root *root = NULL;
         struct anon_vma *anon_vma = NULL;
         struct file *file = vma->vm_file;
         long adjust_next = 0;
@@ -554,7 +554,7 @@ again:			remove_next = 1 + (end > next->vm_end);
                 mutex_lock(&mapping->i_mmap_mutex);
                 if (insert) {
                         /*
-                         * Put into prio_tree now, so instantiated pages
+                         * Put into interval tree now, so instantiated pages
                          * are visible to arm/parisc __flush_dcache_page
                          * throughout; but we cannot insert into address
                          * space until vma start or end is updated.
@@ -582,9 +582,9 @@ again:			remove_next = 1 + (end > next->vm_end);
 
         if (root) {
                 flush_dcache_mmap_lock(mapping);
-                vma_prio_tree_remove(vma, root);
+                vma_interval_tree_remove(vma, root);
                 if (adjust_next)
-                        vma_prio_tree_remove(next, root);
+                        vma_interval_tree_remove(next, root);
         }
 
         vma->vm_start = start;
@@ -597,8 +597,8 @@ again:			remove_next = 1 + (end > next->vm_end);
 
         if (root) {
                 if (adjust_next)
-                        vma_prio_tree_insert(next, root);
-                vma_prio_tree_insert(vma, root);
+                        vma_interval_tree_insert(next, root);
+                vma_interval_tree_insert(vma, root);
                 flush_dcache_mmap_unlock(mapping);
         }
 
diff --git a/mm/nommu.c b/mm/nommu.c
index 12e84e69dd06..45131b41bcdb 100644
--- a/mm/nommu.c
+++ b/mm/nommu.c
@@ -698,7 +698,7 @@ static void add_vma_to_mm(struct mm_struct *mm, struct vm_area_struct *vma)
 
                 mutex_lock(&mapping->i_mmap_mutex);
                 flush_dcache_mmap_lock(mapping);
-                vma_prio_tree_insert(vma, &mapping->i_mmap);
+                vma_interval_tree_insert(vma, &mapping->i_mmap);
                 flush_dcache_mmap_unlock(mapping);
                 mutex_unlock(&mapping->i_mmap_mutex);
         }
@@ -764,7 +764,7 @@ static void delete_vma_from_mm(struct vm_area_struct *vma)
 
                 mutex_lock(&mapping->i_mmap_mutex);
                 flush_dcache_mmap_lock(mapping);
-                vma_prio_tree_remove(vma, &mapping->i_mmap);
+                vma_interval_tree_remove(vma, &mapping->i_mmap);
                 flush_dcache_mmap_unlock(mapping);
                 mutex_unlock(&mapping->i_mmap_mutex);
         }
@@ -2044,7 +2044,6 @@ int nommu_shrink_inode_mappings(struct inode *inode, size_t size,
                                 size_t newsize)
 {
         struct vm_area_struct *vma;
-        struct prio_tree_iter iter;
         struct vm_region *region;
         pgoff_t low, high;
         size_t r_size, r_top;
@@ -2056,8 +2055,7 @@ int nommu_shrink_inode_mappings(struct inode *inode, size_t size,
         mutex_lock(&inode->i_mapping->i_mmap_mutex);
 
         /* search for VMAs that fall within the dead zone */
-        vma_prio_tree_foreach(vma, &iter, &inode->i_mapping->i_mmap,
-                              low, high) {
+        vma_interval_tree_foreach(vma, &inode->i_mapping->i_mmap, low, high) {
                 /* found one - only interested if it's shared out of the page
                  * cache */
                 if (vma->vm_flags & VM_SHARED) {
@@ -2073,8 +2071,8 @@ int nommu_shrink_inode_mappings(struct inode *inode, size_t size,
          * we don't check for any regions that start beyond the EOF as there
          * shouldn't be any
          */
-        vma_prio_tree_foreach(vma, &iter, &inode->i_mapping->i_mmap,
-                              0, ULONG_MAX) {
+        vma_interval_tree_foreach(vma, &inode->i_mapping->i_mmap,
+                                  0, ULONG_MAX) {
                 if (!(vma->vm_flags & VM_SHARED))
                         continue;
 
diff --git a/mm/prio_tree.c b/mm/prio_tree.c
deleted file mode 100644
index 799dcfd7cd8c..000000000000
--- a/mm/prio_tree.c
+++ /dev/null
@@ -1,208 +0,0 @@
-/*
- * mm/prio_tree.c - priority search tree for mapping->i_mmap
- *
- * Copyright (C) 2004, Rajesh Venkatasubramanian <vrajesh@umich.edu>
- *
- * This file is released under the GPL v2.
- *
- * Based on the radix priority search tree proposed by Edward M. McCreight
- * SIAM Journal of Computing, vol. 14, no.2, pages 257-276, May 1985
- *
- * 02Feb2004    Initial version
- */
-
-#include <linux/mm.h>
-#include <linux/prio_tree.h>
-#include <linux/prefetch.h>
-
-/*
- * See lib/prio_tree.c for details on the general radix priority search tree
- * code.
- */
-
-/*
- * The following #defines are mirrored from lib/prio_tree.c. They're only used
- * for debugging, and should be removed (along with the debugging code using
- * them) when switching also VMAs to the regular prio_tree code.
- */
-
-#define RADIX_INDEX(vma)  ((vma)->vm_pgoff)
-#define VMA_SIZE(vma)     (((vma)->vm_end - (vma)->vm_start) >> PAGE_SHIFT)
-/* avoid overflow */
-#define HEAP_INDEX(vma)   ((vma)->vm_pgoff + (VMA_SIZE(vma) - 1))
-
-/*
- * Radix priority search tree for address_space->i_mmap
- *
- * For each vma that map a unique set of file pages i.e., unique [radix_index,
- * heap_index] value, we have a corresponding priority search tree node. If
- * multiple vmas have identical [radix_index, heap_index] value, then one of
- * them is used as a tree node and others are stored in a vm_set list. The tree
- * node points to the first vma (head) of the list using vm_set.head.
- *
- * prio_tree_root
- *      |
- *      A       vm_set.head
- *     / \      /
- *    L   R -> H-I-J-K-M-N-O-P-Q-S
- *    ^   ^    <-- vm_set.list -->
- *  tree nodes
- *
- * We need some way to identify whether a vma is a tree node, head of a vm_set
- * list, or just a member of a vm_set list. We cannot use vm_flags to store
- * such information. The reason is, in the above figure, it is possible that
- * vm_flags' of R and H are covered by the different mmap_sems. When R is
- * removed under R->mmap_sem, H replaces R as a tree node. Since we do not hold
- * H->mmap_sem, we cannot use H->vm_flags for marking that H is a tree node now.
- * That's why some trick involving shared.vm_set.parent is used for identifying
- * tree nodes and list head nodes.
- *
- * vma radix priority search tree node rules:
- *
- * vma->shared.vm_set.parent != NULL    ==> a tree node
- *      vma->shared.vm_set.head != NULL ==> list of others mapping same range
- *      vma->shared.vm_set.head == NULL ==> no others map the same range
- *
- * vma->shared.vm_set.parent == NULL
- *      vma->shared.vm_set.head != NULL ==> list head of vmas mapping same range
- *      vma->shared.vm_set.head == NULL ==> a list node
- */
-
-/*
- * Add a new vma known to map the same set of pages as the old vma:
- * useful for fork's dup_mmap as well as vma_prio_tree_insert below.
- * Note that it just happens to work correctly on i_mmap_nonlinear too.
- */
-void vma_prio_tree_add(struct vm_area_struct *vma, struct vm_area_struct *old)
-{
-        /* Leave these BUG_ONs till prio_tree patch stabilizes */
-        BUG_ON(RADIX_INDEX(vma) != RADIX_INDEX(old));
-        BUG_ON(HEAP_INDEX(vma) != HEAP_INDEX(old));
-
-        vma->shared.vm_set.head = NULL;
-        vma->shared.vm_set.parent = NULL;
-
-        if (!old->shared.vm_set.parent)
-                list_add(&vma->shared.vm_set.list,
-                                &old->shared.vm_set.list);
-        else if (old->shared.vm_set.head)
-                list_add_tail(&vma->shared.vm_set.list,
-                                &old->shared.vm_set.head->shared.vm_set.list);
-        else {
-                INIT_LIST_HEAD(&vma->shared.vm_set.list);
-                vma->shared.vm_set.head = old;
-                old->shared.vm_set.head = vma;
-        }
-}
-
-void vma_prio_tree_insert(struct vm_area_struct *vma,
-                          struct prio_tree_root *root)
-{
-        struct prio_tree_node *ptr;
-        struct vm_area_struct *old;
-
-        vma->shared.vm_set.head = NULL;
-
-        ptr = raw_prio_tree_insert(root, &vma->shared.prio_tree_node);
-        if (ptr != (struct prio_tree_node *) &vma->shared.prio_tree_node) {
-                old = prio_tree_entry(ptr, struct vm_area_struct,
-                                        shared.prio_tree_node);
-                vma_prio_tree_add(vma, old);
-        }
-}
-
-void vma_prio_tree_remove(struct vm_area_struct *vma,
-                          struct prio_tree_root *root)
-{
-        struct vm_area_struct *node, *head, *new_head;
-
-        if (!vma->shared.vm_set.head) {
-                if (!vma->shared.vm_set.parent)
-                        list_del_init(&vma->shared.vm_set.list);
-                else
-                        raw_prio_tree_remove(root, &vma->shared.prio_tree_node);
-        } else {
-                /* Leave this BUG_ON till prio_tree patch stabilizes */
-                BUG_ON(vma->shared.vm_set.head->shared.vm_set.head != vma);
-                if (vma->shared.vm_set.parent) {
-                        head = vma->shared.vm_set.head;
-                        if (!list_empty(&head->shared.vm_set.list)) {
-                                new_head = list_entry(
-                                        head->shared.vm_set.list.next,
-                                        struct vm_area_struct,
-                                        shared.vm_set.list);
-                                list_del_init(&head->shared.vm_set.list);
-                        } else
-                                new_head = NULL;
-
-                        raw_prio_tree_replace(root, &vma->shared.prio_tree_node,
-                                        &head->shared.prio_tree_node);
-                        head->shared.vm_set.head = new_head;
-                        if (new_head)
-                                new_head->shared.vm_set.head = head;
-
-                } else {
-                        node = vma->shared.vm_set.head;
-                        if (!list_empty(&vma->shared.vm_set.list)) {
-                                new_head = list_entry(
-                                        vma->shared.vm_set.list.next,
-                                        struct vm_area_struct,
-                                        shared.vm_set.list);
-                                list_del_init(&vma->shared.vm_set.list);
-                                node->shared.vm_set.head = new_head;
-                                new_head->shared.vm_set.head = node;
-                        } else
-                                node->shared.vm_set.head = NULL;
-                }
-        }
-}
-
-/*
- * Helper function to enumerate vmas that map a given file page or a set of
- * contiguous file pages. The function returns vmas that at least map a single
- * page in the given range of contiguous file pages.
- */
-struct vm_area_struct *vma_prio_tree_next(struct vm_area_struct *vma,
-                                        struct prio_tree_iter *iter)
-{
-        struct prio_tree_node *ptr;
-        struct vm_area_struct *next;
-
-        if (!vma) {
-                /*
-                 * First call is with NULL vma
-                 */
-                ptr = prio_tree_next(iter);
-                if (ptr) {
-                        next = prio_tree_entry(ptr, struct vm_area_struct,
-                                                shared.prio_tree_node);
-                        prefetch(next->shared.vm_set.head);
-                        return next;
-                } else
-                        return NULL;
-        }
-
-        if (vma->shared.vm_set.parent) {
-                if (vma->shared.vm_set.head) {
-                        next = vma->shared.vm_set.head;
-                        prefetch(next->shared.vm_set.list.next);
-                        return next;
-                }
-        } else {
-                next = list_entry(vma->shared.vm_set.list.next,
-                                struct vm_area_struct, shared.vm_set.list);
-                if (!next->shared.vm_set.head) {
-                        prefetch(next->shared.vm_set.list.next);
-                        return next;
-                }
-        }
-
-        ptr = prio_tree_next(iter);
-        if (ptr) {
-                next = prio_tree_entry(ptr, struct vm_area_struct,
-                                        shared.prio_tree_node);
-                prefetch(next->shared.vm_set.head);
-                return next;
-        } else
-                return NULL;
-}
diff --git a/mm/rmap.c b/mm/rmap.c
index 0f3b7cda2a24..7b5b51d25fc5 100644
--- a/mm/rmap.c
+++ b/mm/rmap.c
@@ -820,7 +820,6 @@ static int page_referenced_file(struct page *page,
         struct address_space *mapping = page->mapping;
         pgoff_t pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
         struct vm_area_struct *vma;
-        struct prio_tree_iter iter;
         int referenced = 0;
 
         /*
@@ -846,7 +845,7 @@ static int page_referenced_file(struct page *page,
          */
         mapcount = page_mapcount(page);
 
-        vma_prio_tree_foreach(vma, &iter, &mapping->i_mmap, pgoff, pgoff) {
+        vma_interval_tree_foreach(vma, &mapping->i_mmap, pgoff, pgoff) {
                 unsigned long address = vma_address(page, vma);
                 if (address == -EFAULT)
                         continue;
@@ -945,13 +944,12 @@ static int page_mkclean_file(struct address_space *mapping, struct page *page)
 {
         pgoff_t pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
         struct vm_area_struct *vma;
-        struct prio_tree_iter iter;
         int ret = 0;
 
         BUG_ON(PageAnon(page));
 
         mutex_lock(&mapping->i_mmap_mutex);
-        vma_prio_tree_foreach(vma, &iter, &mapping->i_mmap, pgoff, pgoff) {
+        vma_interval_tree_foreach(vma, &mapping->i_mmap, pgoff, pgoff) {
                 if (vma->vm_flags & VM_SHARED) {
                         unsigned long address = vma_address(page, vma);
                         if (address == -EFAULT)
@@ -1547,7 +1545,6 @@ static int try_to_unmap_file(struct page *page, enum ttu_flags flags)
         struct address_space *mapping = page->mapping;
         pgoff_t pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
         struct vm_area_struct *vma;
-        struct prio_tree_iter iter;
         int ret = SWAP_AGAIN;
         unsigned long cursor;
         unsigned long max_nl_cursor = 0;
@@ -1555,7 +1552,7 @@ static int try_to_unmap_file(struct page *page, enum ttu_flags flags)
         unsigned int mapcount;
 
         mutex_lock(&mapping->i_mmap_mutex);
-        vma_prio_tree_foreach(vma, &iter, &mapping->i_mmap, pgoff, pgoff) {
+        vma_interval_tree_foreach(vma, &mapping->i_mmap, pgoff, pgoff) {
                 unsigned long address = vma_address(page, vma);
                 if (address == -EFAULT)
                         continue;
@@ -1576,7 +1573,7 @@ static int try_to_unmap_file(struct page *page, enum ttu_flags flags)
                 goto out;
 
         list_for_each_entry(vma, &mapping->i_mmap_nonlinear,
-                                                shared.vm_set.list) {
+                                                        shared.nonlinear) {
                 cursor = (unsigned long) vma->vm_private_data;
                 if (cursor > max_nl_cursor)
                         max_nl_cursor = cursor;
@@ -1608,7 +1605,7 @@ static int try_to_unmap_file(struct page *page, enum ttu_flags flags)
 
         do {
                 list_for_each_entry(vma, &mapping->i_mmap_nonlinear,
-                                                shared.vm_set.list) {
+                                                        shared.nonlinear) {
                         cursor = (unsigned long) vma->vm_private_data;
                         while ( cursor < max_nl_cursor &&
                                 cursor < vma->vm_end - vma->vm_start) {
@@ -1631,7 +1628,7 @@ static int try_to_unmap_file(struct page *page, enum ttu_flags flags)
          * in locked vmas).  Reset cursor on all unreserved nonlinear
          * vmas, now forgetting on which ones it had fallen behind.
          */
-        list_for_each_entry(vma, &mapping->i_mmap_nonlinear, shared.vm_set.list)
+        list_for_each_entry(vma, &mapping->i_mmap_nonlinear, shared.nonlinear)
                 vma->vm_private_data = NULL;
 out:
         mutex_unlock(&mapping->i_mmap_mutex);
@@ -1748,13 +1745,12 @@ static int rmap_walk_file(struct page *page, int (*rmap_one)(struct page *,
         struct address_space *mapping = page->mapping;
         pgoff_t pgoff = page->index << (PAGE_CACHE_SHIFT - PAGE_SHIFT);
         struct vm_area_struct *vma;
-        struct prio_tree_iter iter;
         int ret = SWAP_AGAIN;
 
         if (!mapping)
                 return ret;
         mutex_lock(&mapping->i_mmap_mutex);
-        vma_prio_tree_foreach(vma, &iter, &mapping->i_mmap, pgoff, pgoff) {
+        vma_interval_tree_foreach(vma, &mapping->i_mmap, pgoff, pgoff) {
                 unsigned long address = vma_address(page, vma);
                 if (address == -EFAULT)
                         continue;