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>

4 files changed, 240 insertions, 25 deletions

diff --git a/include/linux/fs.h b/include/linux/fs.h
index 5a8a273d5b2f..c617ed024df8 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -401,7 +401,7 @@ struct inodes_stat_t {
 #include <linux/cache.h>
 #include <linux/list.h>
 #include <linux/radix-tree.h>
-#include <linux/prio_tree.h>
+#include <linux/rbtree.h>
 #include <linux/init.h>
 #include <linux/pid.h>
 #include <linux/bug.h>
@@ -669,7 +669,7 @@ struct address_space {
         struct radix_tree_root  page_tree;      /* radix tree of all pages */
         spinlock_t              tree_lock;      /* and lock protecting it */
         unsigned int            i_mmap_writable;/* count VM_SHARED mappings */
-        struct prio_tree_root   i_mmap;         /* tree of private and shared mappings */
+        struct rb_root          i_mmap;         /* tree of private and shared mappings */
         struct list_head        i_mmap_nonlinear;/*list VM_NONLINEAR mappings */
         struct mutex            i_mmap_mutex;   /* protect tree, count, list */
         /* Protected by tree_lock together with the radix tree */
@@ -741,7 +741,7 @@ int mapping_tagged(struct address_space *mapping, int tag);
  */
 static inline int mapping_mapped(struct address_space *mapping)
 {
-        return  !prio_tree_empty(&mapping->i_mmap) ||
+        return  !RB_EMPTY_ROOT(&mapping->i_mmap) ||
                 !list_empty(&mapping->i_mmap_nonlinear);
 }
 
diff --git a/include/linux/interval_tree_tmpl.h b/include/linux/interval_tree_tmpl.h
new file mode 100644
index 000000000000..c65deda31413
--- /dev/null
+++ b/include/linux/interval_tree_tmpl.h
@@ -0,0 +1,215 @@
+/*
+  Interval Trees
+  (C) 2012  Michel Lespinasse <walken@google.com>
+
+  This program is free software; you can redistribute it and/or modify
+  it under the terms of the GNU General Public License as published by
+  the Free Software Foundation; either version 2 of the License, or
+  (at your option) any later version.
+
+  This program is distributed in the hope that it will be useful,
+  but WITHOUT ANY WARRANTY; without even the implied warranty of
+  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+  GNU General Public License for more details.
+
+  You should have received a copy of the GNU General Public License
+  along with this program; if not, write to the Free Software
+  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+
+  include/linux/interval_tree_tmpl.h
+*/
+
+/*
+ * Template for implementing interval trees
+ *
+ * ITSTRUCT:   struct type of the interval tree nodes
+ * ITRB:       name of struct rb_node field within ITSTRUCT
+ * ITTYPE:     type of the interval endpoints
+ * ITSUBTREE:  name of ITTYPE field within ITSTRUCT holding last-in-subtree
+ * ITSTART(n): start endpoint of ITSTRUCT node n
+ * ITLAST(n):  last endpoing of ITSTRUCT node n
+ * ITSTATIC:   'static' or empty
+ * ITPREFIX:   prefix to use for the inline tree definitions
+ */
+
+/* IT(name) -> ITPREFIX_name */
+#define _ITNAME(prefix, name) prefix ## _ ## name
+#define ITNAME(prefix, name) _ITNAME(prefix, name)
+#define IT(name) ITNAME(ITPREFIX, name)
+
+/* Callbacks for augmented rbtree insert and remove */
+
+static inline ITTYPE IT(compute_subtree_last)(ITSTRUCT *node)
+{
+        ITTYPE max = ITLAST(node), subtree_last;
+        if (node->ITRB.rb_left) {
+                subtree_last = rb_entry(node->ITRB.rb_left,
+                                        ITSTRUCT, ITRB)->ITSUBTREE;
+                if (max < subtree_last)
+                        max = subtree_last;
+        }
+        if (node->ITRB.rb_right) {
+                subtree_last = rb_entry(node->ITRB.rb_right,
+                                        ITSTRUCT, ITRB)->ITSUBTREE;
+                if (max < subtree_last)
+                        max = subtree_last;
+        }
+        return max;
+}
+
+static void IT(augment_propagate)(struct rb_node *rb, struct rb_node *stop)
+{
+        while (rb != stop) {
+                ITSTRUCT *node = rb_entry(rb, ITSTRUCT, ITRB);
+                ITTYPE subtree_last = IT(compute_subtree_last)(node);
+                if (node->ITSUBTREE == subtree_last)
+                        break;
+                node->ITSUBTREE = subtree_last;
+                rb = rb_parent(&node->ITRB);
+        }
+}
+
+static void IT(augment_copy)(struct rb_node *rb_old, struct rb_node *rb_new)
+{
+        ITSTRUCT *old = rb_entry(rb_old, ITSTRUCT, ITRB);
+        ITSTRUCT *new = rb_entry(rb_new, ITSTRUCT, ITRB);
+
+        new->ITSUBTREE = old->ITSUBTREE;
+}
+
+static void IT(augment_rotate)(struct rb_node *rb_old, struct rb_node *rb_new)
+{
+        ITSTRUCT *old = rb_entry(rb_old, ITSTRUCT, ITRB);
+        ITSTRUCT *new = rb_entry(rb_new, ITSTRUCT, ITRB);
+
+        new->ITSUBTREE = old->ITSUBTREE;
+        old->ITSUBTREE = IT(compute_subtree_last)(old);
+}
+
+static const struct rb_augment_callbacks IT(augment_callbacks) = {
+        IT(augment_propagate), IT(augment_copy), IT(augment_rotate)
+};
+
+/* Insert / remove interval nodes from the tree */
+
+ITSTATIC void IT(insert)(ITSTRUCT *node, struct rb_root *root)
+{
+        struct rb_node **link = &root->rb_node, *rb_parent = NULL;
+        ITTYPE start = ITSTART(node), last = ITLAST(node);
+        ITSTRUCT *parent;
+
+        while (*link) {
+                rb_parent = *link;
+                parent = rb_entry(rb_parent, ITSTRUCT, ITRB);
+                if (parent->ITSUBTREE < last)
+                        parent->ITSUBTREE = last;
+                if (start < ITSTART(parent))
+                        link = &parent->ITRB.rb_left;
+                else
+                        link = &parent->ITRB.rb_right;
+        }
+
+        node->ITSUBTREE = last;
+        rb_link_node(&node->ITRB, rb_parent, link);
+        rb_insert_augmented(&node->ITRB, root, &IT(augment_callbacks));
+}
+
+ITSTATIC void IT(remove)(ITSTRUCT *node, struct rb_root *root)
+{
+        rb_erase_augmented(&node->ITRB, root, &IT(augment_callbacks));
+}
+
+/*
+ * Iterate over intervals intersecting [start;last]
+ *
+ * Note that a node's interval intersects [start;last] iff:
+ *   Cond1: ITSTART(node) <= last
+ * and
+ *   Cond2: start <= ITLAST(node)
+ */
+
+static ITSTRUCT *IT(subtree_search)(ITSTRUCT *node, ITTYPE start, ITTYPE last)
+{
+        while (true) {
+                /*
+                 * Loop invariant: start <= node->ITSUBTREE
+                 * (Cond2 is satisfied by one of the subtree nodes)
+                 */
+                if (node->ITRB.rb_left) {
+                        ITSTRUCT *left = rb_entry(node->ITRB.rb_left,
+                                                  ITSTRUCT, ITRB);
+                        if (start <= left->ITSUBTREE) {
+                                /*
+                                 * Some nodes in left subtree satisfy Cond2.
+                                 * Iterate to find the leftmost such node N.
+                                 * If it also satisfies Cond1, that's the match
+                                 * we are looking for. Otherwise, there is no
+                                 * matching interval as nodes to the right of N
+                                 * can't satisfy Cond1 either.
+                                 */
+                                node = left;
+                                continue;
+                        }
+                }
+                if (ITSTART(node) <= last) {            /* Cond1 */
+                        if (start <= ITLAST(node))      /* Cond2 */
+                                return node;    /* node is leftmost match */
+                        if (node->ITRB.rb_right) {
+                                node = rb_entry(node->ITRB.rb_right,
+                                                ITSTRUCT, ITRB);
+                                if (start <= node->ITSUBTREE)
+                                        continue;
+                        }
+                }
+                return NULL;    /* No match */
+        }
+}
+
+ITSTATIC ITSTRUCT *IT(iter_first)(struct rb_root *root,
+                                  ITTYPE start, ITTYPE last)
+{
+        ITSTRUCT *node;
+
+        if (!root->rb_node)
+                return NULL;
+        node = rb_entry(root->rb_node, ITSTRUCT, ITRB);
+        if (node->ITSUBTREE < start)
+                return NULL;
+        return IT(subtree_search)(node, start, last);
+}
+
+ITSTATIC ITSTRUCT *IT(iter_next)(ITSTRUCT *node, ITTYPE start, ITTYPE last)
+{
+        struct rb_node *rb = node->ITRB.rb_right, *prev;
+
+        while (true) {
+                /*
+                 * Loop invariants:
+                 *   Cond1: ITSTART(node) <= last
+                 *   rb == node->ITRB.rb_right
+                 *
+                 * First, search right subtree if suitable
+                 */
+                if (rb) {
+                        ITSTRUCT *right = rb_entry(rb, ITSTRUCT, ITRB);
+                        if (start <= right->ITSUBTREE)
+                                return IT(subtree_search)(right, start, last);
+                }
+
+                /* Move up the tree until we come from a node's left child */
+                do {
+                        rb = rb_parent(&node->ITRB);
+                        if (!rb)
+                                return NULL;
+                        prev = &node->ITRB;
+                        node = rb_entry(rb, ITSTRUCT, ITRB);
+                        rb = node->ITRB.rb_right;
+                } while (prev == rb);
+
+                /* Check if the node intersects [start;last] */
+                if (last < ITSTART(node))               /* !Cond1 */
+                        return NULL;
+                else if (start <= ITLAST(node))         /* Cond2 */
+                        return node;
+        }
+}
diff --git a/include/linux/mm.h b/include/linux/mm.h
index 5ddb11b2b4bb..0f671ef09eba 100644
--- a/include/linux/mm.h
+++ b/include/linux/mm.h
@@ -10,7 +10,6 @@
 #include <linux/list.h>
 #include <linux/mmzone.h>
 #include <linux/rbtree.h>
-#include <linux/prio_tree.h>
 #include <linux/atomic.h>
 #include <linux/debug_locks.h>
 #include <linux/mm_types.h>
@@ -1355,22 +1354,27 @@ extern void zone_pcp_reset(struct zone *zone);
 extern atomic_long_t mmap_pages_allocated;
 extern int nommu_shrink_inode_mappings(struct inode *, size_t, size_t);
 
-/* prio_tree.c */
-void vma_prio_tree_add(struct vm_area_struct *, struct vm_area_struct *old);
-void vma_prio_tree_insert(struct vm_area_struct *, struct prio_tree_root *);
-void vma_prio_tree_remove(struct vm_area_struct *, struct prio_tree_root *);
-struct vm_area_struct *vma_prio_tree_next(struct vm_area_struct *vma,
-        struct prio_tree_iter *iter);
-
-#define vma_prio_tree_foreach(vma, iter, root, begin, end)      \
-        for (prio_tree_iter_init(iter, root, begin, end), vma = NULL;   \
-                (vma = vma_prio_tree_next(vma, iter)); )
+/* interval_tree.c */
+void vma_interval_tree_add(struct vm_area_struct *vma,
+                           struct vm_area_struct *old,
+                           struct address_space *mapping);
+void vma_interval_tree_insert(struct vm_area_struct *node,
+                              struct rb_root *root);
+void vma_interval_tree_remove(struct vm_area_struct *node,
+                              struct rb_root *root);
+struct vm_area_struct *vma_interval_tree_iter_first(struct rb_root *root,
+                                unsigned long start, unsigned long last);
+struct vm_area_struct *vma_interval_tree_iter_next(struct vm_area_struct *node,
+                                unsigned long start, unsigned long last);
+
+#define vma_interval_tree_foreach(vma, root, start, last)               \
+        for (vma = vma_interval_tree_iter_first(root, start, last);     \
+             vma; vma = vma_interval_tree_iter_next(vma, start, last))
 
 static inline void vma_nonlinear_insert(struct vm_area_struct *vma,
                                         struct list_head *list)
 {
-        vma->shared.vm_set.parent = NULL;
-        list_add_tail(&vma->shared.vm_set.list, list);
+        list_add_tail(&vma->shared.nonlinear, list);
 }
 
 /* mmap.c */
diff --git a/include/linux/mm_types.h b/include/linux/mm_types.h
index a57a43f5ca7c..31f8a3af7d94 100644
--- a/include/linux/mm_types.h
+++ b/include/linux/mm_types.h
@@ -6,7 +6,6 @@
 #include <linux/threads.h>
 #include <linux/list.h>
 #include <linux/spinlock.h>
-#include <linux/prio_tree.h>
 #include <linux/rbtree.h>
 #include <linux/rwsem.h>
 #include <linux/completion.h>
@@ -240,18 +239,15 @@ struct vm_area_struct {
 
         /*
          * For areas with an address space and backing store,
-         * linkage into the address_space->i_mmap prio tree, or
-         * linkage to the list of like vmas hanging off its node, or
+         * linkage into the address_space->i_mmap interval tree, or
          * linkage of vma in the address_space->i_mmap_nonlinear list.
          */
         union {
                 struct {
-                        struct list_head list;
-                        void *parent;   /* aligns with prio_tree_node parent */
-                        struct vm_area_struct *head;
-                } vm_set;
-
-                struct raw_prio_tree_node prio_tree_node;
+                        struct rb_node rb;
+                        unsigned long rb_subtree_last;
+                } linear;
+                struct list_head nonlinear;
         } shared;
 
         /*