[PATCH] rmap 16: pretend prio_tree

From: Hugh Dickins <hugh@veritas.com>

Pave the way for prio_tree by switching over to its interfaces, but actually
still implement them with the same old lists as before.

Most of the vma_prio_tree interfaces are straightforward.  The interesting one
is vma_prio_tree_next, used to search the tree for all vmas which overlap the
given range: unlike the list_for_each_entry it replaces, it does not find
every vma, just those that match.

But this does leave handling of nonlinear vmas in a very unsatisfactory state:
for now we have to search again over the maximum range to find all the
nonlinear vmas which might contain a page, which of course takes away the
point of the tree.  Fixed in later patch of this batch.

There is no need to initialize vma linkage all over, just do it before
inserting the vma in list or tree.  /proc/pid/statm had an odd test for its
shared count: simplified to an equivalent test on vm_file.

3 files changed, 63 insertions, 8 deletions

diff --git a/include/linux/fs.h b/include/linux/fs.h
index c30ed84a5f7f..650fd6d7a802 100644
--- a/include/linux/fs.h
+++ b/include/linux/fs.h
@@ -18,6 +18,7 @@
 #include <linux/stat.h>
 #include <linux/cache.h>
 #include <linux/radix-tree.h>
+#include <linux/prio_tree.h>
 #include <linux/kobject.h>
 #include <asm/atomic.h>
 #include <linux/audit.h>
@@ -329,9 +330,9 @@ struct address_space {
 	unsigned long		nrpages;	/* number of total pages */
 	pgoff_t			writeback_index;/* writeback starts here */
 	struct address_space_operations *a_ops;	/* methods */
-	struct list_head	i_mmap;		/* list of private mappings */
-	struct list_head	i_mmap_shared;	/* list of shared mappings */
-	spinlock_t		i_mmap_lock;	/* protect both above lists */
+	struct prio_tree_root	i_mmap;		/* tree of private mappings */
+	struct prio_tree_root	i_mmap_shared;	/* tree of shared mappings */
+	spinlock_t		i_mmap_lock;	/* protect trees & list above */
 	atomic_t		truncate_count;	/* Cover race condition with truncate */
 	unsigned long		flags;		/* error bits/gfp mask */
 	struct backing_dev_info *backing_dev_info; /* device readahead, etc */
@@ -380,8 +381,8 @@ int mapping_tagged(struct address_space *mapping, int tag);
  */
 static inline int mapping_mapped(struct address_space *mapping)
 {
-	return	!list_empty(&mapping->i_mmap) ||
-		!list_empty(&mapping->i_mmap_shared);
+	return	!prio_tree_empty(&mapping->i_mmap) ||
+		!prio_tree_empty(&mapping->i_mmap_shared);
 }
 
 /*
@@ -392,7 +393,7 @@ static inline int mapping_mapped(struct address_space *mapping)
  */
 static inline int mapping_writably_mapped(struct address_space *mapping)
 {
-	return	!list_empty(&mapping->i_mmap_shared);
+	return	!prio_tree_empty(&mapping->i_mmap_shared);
 }
 
 /*
diff --git a/include/linux/mm.h b/include/linux/mm.h
index 0747a53a5f62..f8143037c274 100644
--- a/include/linux/mm.h
+++ b/include/linux/mm.h
@@ -11,6 +11,7 @@
 #include <linux/list.h>
 #include <linux/mmzone.h>
 #include <linux/rbtree.h>
+#include <linux/prio_tree.h>
 #include <linux/fs.h>
 
 struct mempolicy;
@@ -70,8 +71,7 @@ struct vm_area_struct {
 
 	/*
 	 * For areas with an address space and backing store,
-	 * one of the address_space->i_mmap{,shared} lists,
-	 * for shm areas, the list of attaches, otherwise unused.
+	 * one of the address_space->i_mmap{,shared} trees.
 	 */
 	struct list_head shared;
 
@@ -587,6 +587,33 @@ extern void show_mem(void);
 extern void si_meminfo(struct sysinfo * val);
 extern void si_meminfo_node(struct sysinfo *val, int nid);
 
+static inline void vma_prio_tree_init(struct vm_area_struct *vma)
+{
+	INIT_LIST_HEAD(&vma->shared);
+}
+
+static inline void vma_prio_tree_add(struct vm_area_struct *vma,
+				     struct vm_area_struct *old)
+{
+	list_add(&vma->shared, &old->shared);
+}
+
+static inline void vma_prio_tree_insert(struct vm_area_struct *vma,
+					struct prio_tree_root *root)
+{
+	list_add_tail(&vma->shared, &root->list);
+}
+
+static inline void vma_prio_tree_remove(struct vm_area_struct *vma,
+					struct prio_tree_root *root)
+{
+	list_del_init(&vma->shared);
+}
+
+struct vm_area_struct *vma_prio_tree_next(
+	struct vm_area_struct *, struct prio_tree_root *,
+	struct prio_tree_iter *, pgoff_t begin, pgoff_t end);
+
 /* mmap.c */
 extern void vma_adjust(struct vm_area_struct *vma, unsigned long start,
 	unsigned long end, pgoff_t pgoff, struct vm_area_struct *next);
diff --git a/include/linux/prio_tree.h b/include/linux/prio_tree.h
new file mode 100644
index 000000000000..5c5e61ab3d11
--- /dev/null
+++ b/include/linux/prio_tree.h
@@ -0,0 +1,27 @@
+#ifndef _LINUX_PRIO_TREE_H
+#define _LINUX_PRIO_TREE_H
+/*
+ * Dummy version of include/linux/prio_tree.h, just for this patch:
+ * no radix priority search tree whatsoever, just implement interfaces
+ * using the old lists.
+ */
+
+struct prio_tree_root {
+	struct list_head	list;
+};
+
+struct prio_tree_iter {
+	int			not_used_yet;
+};
+
+#define INIT_PRIO_TREE_ROOT(ptr)	\
+do {					\
+	INIT_LIST_HEAD(&(ptr)->list);	\
+} while (0)				\
+
+static inline int prio_tree_empty(const struct prio_tree_root *root)
+{
+	return list_empty(&root->list);
+}
+
+#endif /* _LINUX_PRIO_TREE_H */