[PATCH 0/3] [RFC] Fallocate Volatile Ranges v3

[PATCH 0/3] [RFC] Fallocate Volatile Ranges v3

[John Stultz]

Just another quick iteration on the fallocate volatile ranges.

This version utilizes Dave Hansen's suggestion to use the
shmem_writepage code to trigger the volatile range purging.
This avoids using a shrinker as requested by KOSAKI Motohiro
and makes unnecessary some of the page counting logic.

Also caught an off by one bug in the page purging.

Let me know if you have any further feedback or thoughts!

thanks
-john

CC: Andrew Morton <akpm@linux-foundation.org>
CC: Android Kernel Team <kernel-team@android.com>
CC: Robert Love <rlove@google.com>
CC: Mel Gorman <mel@csn.ul.ie>
CC: Hugh Dickins <hughd@google.com>
CC: Dave Hansen <dave@linux.vnet.ibm.com>
CC: Rik van Riel <riel@redhat.com>
CC: Dmitry Adamushko <dmitry.adamushko@gmail.com>
CC: Dave Chinner <david@fromorbit.com>
CC: Neil Brown <neilb@suse.de>
CC: Andrea Righi <andrea@betterlinux.com>
CC: Aneesh Kumar K.V <aneesh.kumar@linux.vnet.ibm.com>
CC: Taras Glek <tgek@mozilla.com>
CC: Mike Hommey <mh@glandium.org>
CC: Jan Kara <jack@suse.cz>
CC: KOSAKI Motohiro <kosaki.motohiro@gmail.com>

John Stultz (3):
  [RFC] Interval tree implementation
  [RFC] Add volatile range management code
  [RFC] tmpfs: Add FALLOC_FL_MARK_VOLATILE/UNMARK_VOLATILE handlers

 fs/open.c                    |    3 +-
 include/linux/falloc.h       |    7 +-
 include/linux/intervaltree.h |   55 +++++
 include/linux/volatile.h     |   41 ++++
 lib/Makefile                 |    2 +-
 lib/intervaltree.c           |  119 ++++++++++
 mm/Makefile                  |    2 +-
 mm/shmem.c                   |   84 ++++++++
 mm/volatile.c                |  486 ++++++++++++++++++++++++++++++++++++++++++
 9 files changed, 793 insertions(+), 6 deletions(-)
 create mode 100644 include/linux/intervaltree.h
 create mode 100644 include/linux/volatile.h
 create mode 100644 lib/intervaltree.c
 create mode 100644 mm/volatile.c

-- 
1.7.3.2.146.gca209

[PATCH 1/3] [RFC] Interval tree implementation

[John Stultz]

After Andrew suggested something like his mumbletree idea
to better store a list of intervals, I worked on a few different
approaches, and this is what I've finally managed to get working.

The idea of storing intervals in a tree is nice, but has a number
of complications. When adding an interval, its possible that a
large interval will consume and merge a number of smaller intervals.
When removing a interval, its possible you may end up splitting an
existing interval, causing one interval to become two. This makes it
very difficult to provide generic list_head like behavior, as
the parent structures would need to be duplicated and removed,
and that has lots of memory ownership issues.

So, this is a much simplified and more list_head like
implementation. You can add a node to a tree, or remove a node
to a tree, but the generic implementation doesn't do the
merging or splitting for you. But it does provide helpers to
find overlapping and adjacent intervals.

Andrew also really wanted this interval-tree implementation to be
resuable so we don't duplicate the file locking logic. I'm not
totally convinced that the requirements between the volatile
intervals and file locking are really equivelent, but this reduced
impelementation may make it possible.

Changelog:
v2:
* Reworked code to use an rbtree instead of splaying

v3:
* Added range_tree_next_in_range() to avoid having to start
  lookups from the root every time.
* Fixed some comments and return NULL instead of 0, as suggested
  by Aneesh Kumar K.V

v6:
* Fixed range_tree_in_range() so that it finds the earliest range,
  rather then the first. This allows the next_in_range() function
  to properly cover all the ranges in the tree.
* Minor clenaups to simplify some of the functions

v7:
* Changed terminology from rangetree to intervaltree as suggested
  by Jan Kara

CC: Andrew Morton <akpm@linux-foundation.org>
CC: Android Kernel Team <kernel-team@android.com>
CC: Robert Love <rlove@google.com>
CC: Mel Gorman <mel@csn.ul.ie>
CC: Hugh Dickins <hughd@google.com>
CC: Dave Hansen <dave@linux.vnet.ibm.com>
CC: Rik van Riel <riel@redhat.com>
CC: Dmitry Adamushko <dmitry.adamushko@gmail.com>
CC: Dave Chinner <david@fromorbit.com>
CC: Neil Brown <neilb@suse.de>
CC: Andrea Righi <andrea@betterlinux.com>
CC: Aneesh Kumar K.V <aneesh.kumar@linux.vnet.ibm.com>
CC: Taras Glek <tgek@mozilla.com>
CC: Mike Hommey <mh@glandium.org>
CC: Jan Kara <jack@suse.cz>
CC: KOSAKI Motohiro <kosaki.motohiro@gmail.com>
Signed-off-by: John Stultz <john.stultz@linaro.org>
---
 include/linux/intervaltree.h |   55 +++++++++++++++++++
 lib/Makefile                 |    2 +-
 lib/intervaltree.c           |  119 ++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 175 insertions(+), 1 deletions(-)
 create mode 100644 include/linux/intervaltree.h
 create mode 100644 lib/intervaltree.c

diff --git a/include/linux/intervaltree.h b/include/linux/intervaltree.h
new file mode 100644
index 0000000..cfaa174
--- /dev/null
+++ b/include/linux/intervaltree.h
@@ -0,0 +1,55 @@
+#ifndef _LINUX_INTERVALTREE_H
+#define _LINUX_INTERVALTREE_H
+
+#include <linux/types.h>
+#include <linux/rbtree.h>
+
+struct interval_tree_node {
+	struct rb_node rb;
+	u64 start;
+	u64 end;
+};
+
+struct interval_tree_root {
+	struct rb_root head;
+};
+
+static inline void interval_tree_init(struct interval_tree_root *root)
+{
+	root->head = RB_ROOT;
+}
+
+static inline void interval_tree_node_init(struct interval_tree_node *node)
+{
+	rb_init_node(&node->rb);
+	node->start = 0;
+	node->end = 0;
+}
+
+static inline int interval_tree_empty(struct interval_tree_root *root)
+{
+	return RB_EMPTY_ROOT(&root->head);
+}
+
+static inline
+struct interval_tree_node *interval_tree_root_node(
+						struct interval_tree_root *root)
+{
+	struct interval_tree_node *ret;
+	ret = container_of(root->head.rb_node, struct interval_tree_node, rb);
+	return ret;
+}
+
+extern struct interval_tree_node *interval_tree_in_interval(
+						struct interval_tree_root *root,
+						 u64 start, u64 end);
+extern struct interval_tree_node *interval_tree_next_in_interval(
+						struct interval_tree_node *node,
+						u64 start, u64 end);
+extern void interval_tree_add(struct interval_tree_root *root,
+					struct interval_tree_node *node);
+extern void interval_tree_remove(struct interval_tree_root *root,
+					struct interval_tree_node *node);
+#endif
+
+
diff --git a/lib/Makefile b/lib/Makefile
index 8c31a0c..2bbad25 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -12,7 +12,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 idr.o int_sqrt.o extable.o prio_tree.o \
 	 sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \
 	 proportions.o prio_heap.o ratelimit.o show_mem.o \
-	 is_single_threaded.o plist.o decompress.o
+	 is_single_threaded.o plist.o decompress.o intervaltree.o
 
 lib-$(CONFIG_MMU) += ioremap.o
 lib-$(CONFIG_SMP) += cpumask.o
diff --git a/lib/intervaltree.c b/lib/intervaltree.c
new file mode 100644
index 0000000..47c52e0
--- /dev/null
+++ b/lib/intervaltree.c
@@ -0,0 +1,119 @@
+#include <linux/intervaltree.h>
+#include <linux/kernel.h>
+#include <linux/slab.h>
+
+/* This code implements a naive interval tree, which stores a series of
+ * non-intersecting intervals.
+ * More complex interval trees can be read about here:
+ *		http://en.wikipedia.org/wiki/Interval_tree
+ */
+
+
+/**
+ * interval_tree_in_interval - Returns the first node that intersects with the
+ *                             given interval
+ * @root: interval_tree root
+ * @start: interval start
+ * @end: interval end
+ *
+ */
+struct interval_tree_node *interval_tree_in_interval(
+						struct interval_tree_root *root,
+						u64 start, u64 end)
+{
+	struct rb_node *p = root->head.rb_node;
+	struct interval_tree_node *candidate, *match = NULL;
+
+	while (p) {
+		candidate = rb_entry(p, struct interval_tree_node, rb);
+		if (end < candidate->start)
+			p = p->rb_left;
+		else if (start > candidate->end)
+			p = p->rb_right;
+		else {
+			/* We found one, but try to find an earlier match */
+			match = candidate;
+			p = p->rb_left;
+		}
+	}
+
+	return match;
+}
+
+
+/**
+ * interval_tree_next_in_interval - Return the next interval in a intervaltree
+ *                                  thatintersects with a specified interval.
+ * @root: interval_tree root
+ * @start: interval start
+ * @end: interval end
+ *
+ */
+struct interval_tree_node *interval_tree_next_in_interval(
+						struct interval_tree_node *node,
+						u64 start, u64 end)
+{
+	struct rb_node *next;
+	struct interval_tree_node *candidate;
+	if (!node)
+		return NULL;
+	next = rb_next(&node->rb);
+	if (!next)
+		return NULL;
+
+	candidate = container_of(next, struct interval_tree_node, rb);
+
+	if ((candidate->start > end) || (candidate->end < start))
+		return NULL;
+
+	return candidate;
+}
+
+/**
+ * interval_tree_add - Add a node to a interval tree
+ * @root: interval tree to be added to
+ * @node: interval_tree_node to be added
+ *
+ * Adds a node to the interval tree. Added interval should not intersect with
+ * existing intervals in the tree.
+ */
+void interval_tree_add(struct interval_tree_root *root,
+					struct interval_tree_node *node)
+{
+	struct rb_node **p = &root->head.rb_node;
+	struct rb_node *parent = NULL;
+	struct interval_tree_node *ptr;
+
+	WARN_ON_ONCE(!RB_EMPTY_NODE(&node->rb));
+
+	/* XXX might want to conditionalize this on debugging checks */
+	WARN_ON_ONCE(!!interval_tree_in_interval(root, node->start, node->end));
+
+	while (*p) {
+		parent = *p;
+		ptr = rb_entry(parent, struct interval_tree_node, rb);
+		if (node->start < ptr->start)
+			p = &(*p)->rb_left;
+		else
+			p = &(*p)->rb_right;
+	}
+	rb_link_node(&node->rb, parent, p);
+	rb_insert_color(&node->rb, &root->head);
+}
+
+
+/**
+ * interval_tree_remove: Removes a given node from the tree
+ * @root: root of tree
+ * @node: Node to be removed
+ *
+ * Removes a node and splays the tree
+ */
+void interval_tree_remove(struct interval_tree_root *root,
+					struct interval_tree_node *node)
+{
+	WARN_ON_ONCE(RB_EMPTY_NODE(&node->rb));
+
+	rb_erase(&node->rb, &root->head);
+	RB_CLEAR_NODE(&node->rb);
+}
-- 
1.7.3.2.146.gca209

[PATCH 2/3] [RFC] Add volatile range management code

[John Stultz]

This patch provides the volatile range management code
that filesystems can utilize when implementing
FALLOC_FL_MARK_VOLATILE.

It tracks a collection of page ranges against a mapping
stored in an interval-tree. This code handles coalescing
overlapping and adjacent ranges, as well as splitting
ranges when sub-chunks are removed.

The ranges can be marked purged or unpurged. And there is
a per-fs lru list that tracks all the unpurged ranges for
that fs.

v2:
* Fix bug in volatile_ranges_get_last_used returning bad
  start,end values
* Rework for intervaltree renaming
* Optimize volatile_range_lru_size to avoid running through
  lru list each time.

v3:
* Improve function name to make it clear what the
  volatile_ranges_pluck_lru() code does.
* Drop volatile_range_lru_size and unpurged_page_count
  mangement as its now unused

CC: Andrew Morton <akpm@linux-foundation.org>
CC: Android Kernel Team <kernel-team@android.com>
CC: Robert Love <rlove@google.com>
CC: Mel Gorman <mel@csn.ul.ie>
CC: Hugh Dickins <hughd@google.com>
CC: Dave Hansen <dave@linux.vnet.ibm.com>
CC: Rik van Riel <riel@redhat.com>
CC: Dmitry Adamushko <dmitry.adamushko@gmail.com>
CC: Dave Chinner <david@fromorbit.com>
CC: Neil Brown <neilb@suse.de>
CC: Andrea Righi <andrea@betterlinux.com>
CC: Aneesh Kumar K.V <aneesh.kumar@linux.vnet.ibm.com>
CC: Taras Glek <tgek@mozilla.com>
CC: Mike Hommey <mh@glandium.org>
CC: Jan Kara <jack@suse.cz>
CC: KOSAKI Motohiro <kosaki.motohiro@gmail.com>
Signed-off-by: John Stultz <john.stultz@linaro.org>
---
 include/linux/volatile.h |   41 ++++
 mm/Makefile              |    2 +-
 mm/volatile.c            |  486 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 528 insertions(+), 1 deletions(-)
 create mode 100644 include/linux/volatile.h
 create mode 100644 mm/volatile.c

diff --git a/include/linux/volatile.h b/include/linux/volatile.h
new file mode 100644
index 0000000..8deee06
--- /dev/null
+++ b/include/linux/volatile.h
@@ -0,0 +1,41 @@
+#ifndef _LINUX_VOLATILE_H
+#define _LINUX_VOLATILE_H
+
+#include <linux/fs.h>
+
+struct volatile_fs_head {
+	struct mutex lock;
+	struct list_head lru_head;
+};
+
+
+#define DEFINE_VOLATILE_FS_HEAD(name) struct volatile_fs_head name = {	\
+	.lock = __MUTEX_INITIALIZER(name.lock),				\
+	.lru_head = LIST_HEAD_INIT(name.lru_head),			\
+}
+
+
+static inline void volatile_range_lock(struct volatile_fs_head *head)
+{
+	mutex_lock(&head->lock);
+}
+
+static inline void volatile_range_unlock(struct volatile_fs_head *head)
+{
+	mutex_unlock(&head->lock);
+}
+
+extern long volatile_range_add(struct volatile_fs_head *head,
+				struct address_space *mapping,
+				pgoff_t start_index, pgoff_t end_index);
+extern long volatile_range_remove(struct volatile_fs_head *head,
+				struct address_space *mapping,
+				pgoff_t start_index, pgoff_t end_index);
+
+extern void volatile_range_clear(struct volatile_fs_head *head,
+					struct address_space *mapping);
+
+extern s64 volatile_ranges_pluck_lru(struct volatile_fs_head *head,
+				struct address_space **mapping,
+				loff_t *start, loff_t *end);
+#endif /* _LINUX_VOLATILE_H */
diff --git a/mm/Makefile b/mm/Makefile
index a156285..dc79eb8 100644
--- a/mm/Makefile
+++ b/mm/Makefile
@@ -16,7 +16,7 @@ obj-y			:= filemap.o mempool.o oom_kill.o fadvise.o \
 			   readahead.o swap.o truncate.o vmscan.o shmem.o \
 			   prio_tree.o util.o mmzone.o vmstat.o backing-dev.o \
 			   page_isolation.o mm_init.o mmu_context.o percpu.o \
-			   compaction.o $(mmu-y)
+			   compaction.o volatile.o $(mmu-y)
 obj-y += init-mm.o
 
 ifdef CONFIG_NO_BOOTMEM
diff --git a/mm/volatile.c b/mm/volatile.c
new file mode 100644
index 0000000..7d6dc9b
--- /dev/null
+++ b/mm/volatile.c
@@ -0,0 +1,486 @@
+/* mm/volatile.c
+ *
+ * Volatile page range managment.
+ *      Copyright 2011 Linaro
+ *
+ * Based on mm/ashmem.c
+ *      by Robert Love <rlove@google.com>
+ *      Copyright (C) 2008 Google, Inc.
+ *
+ *
+ * This software is licensed under the terms of the GNU General Public
+ * License version 2, as published by the Free Software Foundation, and
+ * may be copied, distributed, and modified under those terms.
+ *
+ * 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.
+ *
+ * The volatile range management is a helper layer on top of the range tree
+ * code, which is used to help filesystems manage page ranges that are volatile.
+ *
+ * These ranges are stored in a per-mapping range tree. Storing both purged and
+ * unpurged ranges connected to that address_space. Unpurged ranges are also
+ * linked together in an lru list that is per-volatile-fs-head (basically
+ * per-filesystem).
+ *
+ * The goal behind volatile ranges is to allow applications to interact
+ * with the kernel's cache management infrastructure.  In particular an
+ * application can say "this memory contains data that might be useful in
+ * the future, but can be reconstructed if necessary, so if the kernel
+ * needs, it can zap and reclaim this memory without having to swap it out.
+ *
+ * The proposed mechanism - at a high level - is for user-space to be able
+ * to say "This memory is volatile" and then later "this memory is no longer
+ * volatile".  If the content of the memory is still available the second
+ * request succeeds.  If not, the memory is marked non-volatile and an
+ * error is returned to denote that the contents have been lost.
+ *
+ * Credits to Neil Brown for the above description.
+ *
+ */
+
+#include <linux/kernel.h>
+#include <linux/fs.h>
+#include <linux/mm.h>
+#include <linux/slab.h>
+#include <linux/pagemap.h>
+#include <linux/volatile.h>
+#include <linux/intervaltree.h>
+#include <linux/hash.h>
+#include <linux/shmem_fs.h>
+
+
+struct volatile_range {
+	struct list_head		lru;
+	struct interval_tree_node	interval_node;
+	unsigned int			purged;
+	struct address_space		*mapping;
+};
+
+
+/*
+ * To avoid bloating the address_space structure, we use
+ * a hash structure to map from address_space mappings to
+ * the interval_tree root that stores volatile ranges
+ */
+static DEFINE_MUTEX(hash_mutex);
+static struct hlist_head *mapping_hash;
+static long mapping_hash_shift = 8;
+struct mapping_hash_entry {
+	struct interval_tree_root	root;
+	struct address_space		*mapping;
+	struct hlist_node		hnode;
+};
+
+
+static inline
+struct interval_tree_root *__mapping_to_root(struct address_space *mapping)
+{
+	struct hlist_node *elem;
+	struct mapping_hash_entry *entry;
+	struct interval_tree_root *ret = NULL;
+
+	hlist_for_each_entry_rcu(entry, elem,
+			&mapping_hash[hash_ptr(mapping, mapping_hash_shift)],
+				hnode)
+		if (entry->mapping == mapping)
+			ret =  &entry->root;
+
+	return ret;
+}
+
+
+static inline
+struct interval_tree_root *mapping_to_root(struct address_space *mapping)
+{
+	struct interval_tree_root *ret;
+
+	mutex_lock(&hash_mutex);
+	ret =  __mapping_to_root(mapping);
+	mutex_unlock(&hash_mutex);
+	return ret;
+}
+
+
+static inline
+struct interval_tree_root *mapping_allocate_root(struct address_space *mapping)
+{
+	struct mapping_hash_entry *entry;
+	struct interval_tree_root *dblchk;
+	struct interval_tree_root *ret = NULL;
+
+	entry = kzalloc(sizeof(*entry), GFP_KERNEL);
+	if (!entry)
+		return NULL;
+
+	mutex_lock(&hash_mutex);
+	/* Since we dropped the lock, double check that no one has
+	 * created the same hash entry.
+	 */
+	dblchk = __mapping_to_root(mapping);
+	if (dblchk) {
+		kfree(entry);
+		ret = dblchk;
+		goto out;
+	}
+
+	INIT_HLIST_NODE(&entry->hnode);
+	entry->mapping = mapping;
+	interval_tree_init(&entry->root);
+
+	hlist_add_head_rcu(&entry->hnode,
+		&mapping_hash[hash_ptr(mapping, mapping_hash_shift)]);
+
+	ret = &entry->root;
+out:
+	mutex_unlock(&hash_mutex);
+	return ret;
+}
+
+
+static inline void mapping_free_root(struct interval_tree_root *root)
+{
+	struct mapping_hash_entry *entry;
+
+	mutex_lock(&hash_mutex);
+	entry = container_of(root, struct mapping_hash_entry, root);
+
+	hlist_del_rcu(&entry->hnode);
+	kfree(entry);
+	mutex_unlock(&hash_mutex);
+}
+
+
+/* volatile range helpers */
+static inline void vrange_resize(struct volatile_fs_head *head,
+				struct volatile_range *range,
+				pgoff_t start_index, pgoff_t end_index)
+{
+	s64 old_size, new_size;
+
+	old_size = range->interval_node.end - range->interval_node.start;
+	new_size = end_index-start_index;
+
+	range->interval_node.start = start_index;
+	range->interval_node.end = end_index;
+}
+
+static struct volatile_range *vrange_alloc(void)
+{
+	struct volatile_range *new;
+
+	new = kzalloc(sizeof(struct volatile_range), GFP_KERNEL);
+	if (!new)
+		return 0;
+	interval_tree_node_init(&new->interval_node);
+	return new;
+}
+
+static void vrange_del(struct volatile_fs_head *head,
+				struct interval_tree_root *root,
+				struct volatile_range *vrange)
+{
+	if (!vrange->purged)
+		list_del(&vrange->lru);
+	interval_tree_remove(root, &vrange->interval_node);
+	kfree(vrange);
+}
+
+
+/**
+ * volatile_range_add: Marks a page interval as volatile
+ * @head: per-fs volatile head
+ * @mapping: address space who's range is being marked volatile
+ * @start_index: Starting page in range to be marked volatile
+ * @end_index: Ending page in range to be marked volatile
+ *
+ * Mark a region as volatile. Coalesces overlapping and neighboring regions.
+ *
+ * Must lock the volatile_fs_head before calling!
+ *
+ * Returns 1 if the range was coalesced with any purged ranges.
+ * Returns 0 on success.
+ */
+long volatile_range_add(struct volatile_fs_head *head,
+				struct address_space *mapping,
+				pgoff_t start_index, pgoff_t end_index)
+{
+	struct volatile_range *new;
+	struct interval_tree_node *node;
+	struct volatile_range *vrange;
+	struct interval_tree_root *root;
+	int purged = 0;
+	u64 start = (u64)start_index;
+	u64 end = (u64)end_index;
+
+	/* Make sure we're properly locked */
+	WARN_ON(!mutex_is_locked(&head->lock));
+
+	/*
+	 * Because the lock might be held in a shrinker, release
+	 * it during allocation.
+	 */
+	mutex_unlock(&head->lock);
+	new = vrange_alloc();
+	mutex_lock(&head->lock);
+	if (!new)
+		return -ENOMEM;
+
+	root = mapping_to_root(mapping);
+	if (!root) {
+		mutex_unlock(&head->lock);
+		root = mapping_allocate_root(mapping);
+		mutex_lock(&head->lock);
+		if (!root) {
+			kfree(new);
+			return -ENOMEM;
+		}
+	}
+
+	/* First, find any existing intervals that overlap */
+	node = interval_tree_in_interval(root, start, end);
+	while (node) {
+		/* Already entirely marked volatile, so we're done */
+		if (node->start < start && node->end > end) {
+			/* don't need the allocated value */
+			kfree(new);
+			return purged;
+		}
+
+		/* Grab containing volatile range */
+		vrange = container_of(node, struct volatile_range,
+								interval_node);
+
+		/* Resize the new range to cover all overlapping ranges */
+		start = min_t(u64, start, node->start);
+		end = max_t(u64, end, node->end);
+
+		/* Inherit purged state from overlapping ranges */
+		purged |= vrange->purged;
+
+
+		node = interval_tree_next_in_interval(&vrange->interval_node,
+								start, end);
+		/* Delete the old range, as we consume it */
+		vrange_del(head, root, vrange);
+	}
+
+	/* Coalesce left-adjacent ranges */
+	node = interval_tree_in_interval(root, start-1, start);
+	if (node) {
+		vrange = container_of(node, struct volatile_range,
+								interval_node);
+		/* Only coalesce if both are either purged or unpurged */
+		if (vrange->purged == purged) {
+			/* resize new range */
+			start = min_t(u64, start, node->start);
+			end = max_t(u64, end, node->end);
+			/* delete old range */
+			vrange_del(head, root, vrange);
+		}
+	}
+
+	/* Coalesce right-adjacent ranges */
+	node = interval_tree_in_interval(root, end, end+1);
+	if (node) {
+		vrange = container_of(node, struct volatile_range,
+								interval_node);
+		/* Only coalesce if both are either purged or unpurged */
+		if (vrange->purged == purged) {
+			/* resize new range */
+			start = min_t(u64, start, node->start);
+			end = max_t(u64, end, node->end);
+			/* delete old range */
+			vrange_del(head, root, vrange);
+		}
+	}
+	/* Assign and store the new range in the range tree */
+	new->mapping = mapping;
+	new->interval_node.start = start;
+	new->interval_node.end = end;
+	new->purged = purged;
+	interval_tree_add(root, &new->interval_node);
+
+	/* Only add unpurged ranges to LRU */
+	if (!purged)
+		list_add_tail(&new->lru, &head->lru_head);
+
+	return purged;
+}
+
+
+/**
+ * volatile_range_remove: Marks a page interval as nonvolatile
+ * @head: per-fs volatile head
+ * @mapping: address space who's range is being marked nonvolatile
+ * @start_index: Starting page in range to be marked nonvolatile
+ * @end_index: Ending page in range to be marked nonvolatile
+ *
+ * Mark a region as nonvolatile. And remove any contained pages
+ * from the volatile range tree.
+ *
+ * Must lock the volatile_fs_head before calling!
+ *
+ * Returns 1 if any portion of the range was purged.
+ * Returns 0 on success.
+ */
+long volatile_range_remove(struct volatile_fs_head *head,
+				struct address_space *mapping,
+				pgoff_t start_index, pgoff_t end_index)
+{
+	struct volatile_range *new;
+	struct interval_tree_node *node;
+	struct interval_tree_root *root;
+	int ret		= 0;
+	int used_new	= 0;
+	u64 start	= (u64)start_index;
+	u64 end		= (u64)end_index;
+
+	/* Make sure we're properly locked */
+	WARN_ON(!mutex_is_locked(&head->lock));
+
+	/*
+	 * Because the lock might be held in a shrinker, release
+	 * it during allocation.
+	 */
+	mutex_unlock(&head->lock);
+	new = vrange_alloc();
+	mutex_lock(&head->lock);
+	if (!new)
+		return -ENOMEM;
+
+	root = mapping_to_root(mapping);
+	if (!root)
+		goto out;
+
+
+	/* Find any overlapping ranges */
+	node = interval_tree_in_interval(root, start, end);
+	while (node) {
+		struct volatile_range *vrange;
+		vrange = container_of(node, struct volatile_range,
+								interval_node);
+
+		ret |= vrange->purged;
+
+		if (start <= node->start && end >= node->end) {
+			/* delete: volatile range is totally within range */
+			node = interval_tree_next_in_interval(
+							&vrange->interval_node,
+							start, end);
+			vrange_del(head, root, vrange);
+		} else if (node->start >= start) {
+			/* resize: volatile range right-overlaps range */
+			vrange_resize(head, vrange, end+1, node->end);
+			node = interval_tree_next_in_interval(
+							&vrange->interval_node,
+							start, end);
+
+		} else if (node->end <= end) {
+			/* resize: volatile range left-overlaps range */
+			vrange_resize(head, vrange, node->start, start-1);
+			node = interval_tree_next_in_interval(
+							&vrange->interval_node,
+							start, end);
+		} else {
+			/* split: range is totally within a volatile range */
+			used_new = 1; /* we only do this once */
+			new->mapping = mapping;
+			new->interval_node.start = end + 1;
+			new->interval_node.end = node->end;
+			new->purged = vrange->purged;
+			interval_tree_add(root, &new->interval_node);
+			if (!new->purged)
+				list_add_tail(&new->lru, &head->lru_head);
+			vrange_resize(head, vrange, node->start, start-1);
+
+			break;
+		}
+	}
+
+out:
+	if (!used_new)
+		kfree(new);
+
+	return ret;
+}
+
+
+/**
+ * volatile_ranges_pluck_lru: Returns mapping and size of lru unpurged range
+ * @head: per-fs volatile head
+ * @mapping: dbl pointer to mapping who's range is being purged
+ * @start: Pointer to starting address of range being purged
+ * @end: Pointer to ending address of range being purged
+ *
+ * Returns the mapping, start and end values of the least recently used
+ * range. Marks the range as purged and removes it from the LRU.
+ *
+ * Must lock the volatile_fs_head before calling!
+ *
+ * Returns 1 on success if a range was returned
+ * Return 0 if no ranges were found.
+ */
+s64 volatile_ranges_pluck_lru(struct volatile_fs_head *head,
+				struct address_space **mapping,
+				loff_t *start, loff_t *end)
+{
+	struct volatile_range *range;
+
+	WARN_ON(!mutex_is_locked(&head->lock));
+
+	if (list_empty(&head->lru_head))
+		return 0;
+
+	range = list_first_entry(&head->lru_head, struct volatile_range, lru);
+
+	*start = range->interval_node.start;
+	*end = range->interval_node.end;
+	*mapping = range->mapping;
+
+	list_del(&range->lru);
+	range->purged = 1;
+
+	return 1;
+}
+
+
+/*
+ * Cleans up any volatile ranges.
+ */
+void volatile_range_clear(struct volatile_fs_head *head,
+				struct address_space *mapping)
+{
+	struct volatile_range *tozap;
+	struct interval_tree_root *root;
+
+	WARN_ON(!mutex_is_locked(&head->lock));
+
+	root = mapping_to_root(mapping);
+	if (!root)
+		return;
+
+	while (!interval_tree_empty(root)) {
+		struct interval_tree_node *tmp;
+		tmp = interval_tree_root_node(root);
+		tozap = container_of(tmp, struct volatile_range, interval_node);
+		vrange_del(head, root, tozap);
+	}
+	mapping_free_root(root);
+}
+
+
+static int __init volatile_init(void)
+{
+	int i, size;
+
+	size = 1U << mapping_hash_shift;
+	mapping_hash = kzalloc(sizeof(mapping_hash)*size, GFP_KERNEL);
+	for (i = 0; i < size; i++)
+		INIT_HLIST_HEAD(&mapping_hash[i]);
+
+	return 0;
+}
+arch_initcall(volatile_init);
-- 
1.7.3.2.146.gca209

[PATCH 3/3] [RFC] tmpfs: Add FALLOC_FL_MARK_VOLATILE/UNMARK_VOLATILE handlers

[John Stultz]

This patch enables FALLOC_FL_MARK_VOLATILE/UNMARK_VOLATILE
functionality for tmpfs making use of the volatile range
management code.

Conceptually, FALLOC_FL_MARK_VOLATILE is like a delayed
FALLOC_FL_PUNCH_HOLE.  This allows applications that have
data caches that can be re-created to tell the kernel that
some memory contains data that is useful in the future, but
can be recreated if needed, so if the kernel needs, it can
zap the memory without having to swap it out.

In use, applications use FALLOC_FL_MARK_VOLATILE to mark
page ranges as volatile when they are not in use. Then later
if they wants to reuse the data, they use
FALLOC_FL_UNMARK_VOLATILE, which will return an error if the
data has been purged.

This is very much influenced by the Android Ashmem interface by
Robert Love so credits to him and the Android developers.
In many cases the code & logic come directly from the ashmem patch.
The intent of this patch is to allow for ashmem-like behavior, but
embeds the idea a little deeper into the VM code.

This is a reworked version of the fadvise volatile idea submitted
earlier to the list. Thanks to Dave Chinner for suggesting to
rework the idea in this fashion. Also thanks to Dmitry Adamushko
for continued review and bug reporting, and Dave Hansen for
help with the original design and mentoring me in the VM code.

v3:
* Fix off by one issue when truncating page ranges
* Use Dave Hansesn's suggestion to use shmem_writepage to trigger
  range purging instead of using a shrinker.

CC: Andrew Morton <akpm@linux-foundation.org>
CC: Android Kernel Team <kernel-team@android.com>
CC: Robert Love <rlove@google.com>
CC: Mel Gorman <mel@csn.ul.ie>
CC: Hugh Dickins <hughd@google.com>
CC: Dave Hansen <dave@linux.vnet.ibm.com>
CC: Rik van Riel <riel@redhat.com>
CC: Dmitry Adamushko <dmitry.adamushko@gmail.com>
CC: Dave Chinner <david@fromorbit.com>
CC: Neil Brown <neilb@suse.de>
CC: Andrea Righi <andrea@betterlinux.com>
CC: Aneesh Kumar K.V <aneesh.kumar@linux.vnet.ibm.com>
CC: Taras Glek <tgek@mozilla.com>
CC: Mike Hommey <mh@glandium.org>
CC: Jan Kara <jack@suse.cz>
CC: KOSAKI Motohiro <kosaki.motohiro@gmail.com>
Signed-off-by: John Stultz <john.stultz@linaro.org>
---
 fs/open.c              |    3 +-
 include/linux/falloc.h |    7 ++--
 mm/shmem.c             |   84 ++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 90 insertions(+), 4 deletions(-)

diff --git a/fs/open.c b/fs/open.c
index d543012..448ed5a 100644
--- a/fs/open.c
+++ b/fs/open.c
@@ -223,7 +223,8 @@ int do_fallocate(struct file *file, int mode, loff_t offset, loff_t len)
 		return -EINVAL;
 
 	/* Return error if mode is not supported */
-	if (mode & ~(FALLOC_FL_KEEP_SIZE | FALLOC_FL_PUNCH_HOLE))
+	if (mode & ~(FALLOC_FL_KEEP_SIZE | FALLOC_FL_PUNCH_HOLE |
+			FALLOC_FL_MARK_VOLATILE | FALLOC_FL_UNMARK_VOLATILE))
 		return -EOPNOTSUPP;
 
 	/* Punch hole must have keep size set */
diff --git a/include/linux/falloc.h b/include/linux/falloc.h
index 73e0b62..3e47ad5 100644
--- a/include/linux/falloc.h
+++ b/include/linux/falloc.h
@@ -1,9 +1,10 @@
 #ifndef _FALLOC_H_
 #define _FALLOC_H_
 
-#define FALLOC_FL_KEEP_SIZE	0x01 /* default is extend size */
-#define FALLOC_FL_PUNCH_HOLE	0x02 /* de-allocates range */
-
+#define FALLOC_FL_KEEP_SIZE		0x01 /* default is extend size */
+#define FALLOC_FL_PUNCH_HOLE		0x02 /* de-allocates range */
+#define FALLOC_FL_MARK_VOLATILE		0x04 /* mark range volatile */
+#define FALLOC_FL_UNMARK_VOLATILE	0x08 /* mark range non-volatile */
 #ifdef __KERNEL__
 
 /*
diff --git a/mm/shmem.c b/mm/shmem.c
index d576b84..0cc33a4 100644
--- a/mm/shmem.c
+++ b/mm/shmem.c
@@ -64,6 +64,7 @@ static struct vfsmount *shm_mnt;
 #include <linux/highmem.h>
 #include <linux/seq_file.h>
 #include <linux/magic.h>
+#include <linux/volatile.h>
 
 #include <asm/uaccess.h>
 #include <asm/pgtable.h>
@@ -624,11 +625,79 @@ static int shmem_setattr(struct dentry *dentry, struct iattr *attr)
 	return error;
 }
 
+static DEFINE_VOLATILE_FS_HEAD(shmem_volatile_head);
+
+static int shmem_mark_volatile(struct inode *inode, loff_t offset, loff_t len)
+{
+	loff_t lstart, lend;
+	int ret;
+
+	lstart = offset >> PAGE_CACHE_SHIFT;
+	lend = (offset+len) >> PAGE_CACHE_SHIFT;
+
+	volatile_range_lock(&shmem_volatile_head);
+	ret = volatile_range_add(&shmem_volatile_head, &inode->i_data,
+					lstart, lend);
+	if (ret > 0) { /* immdiately purge */
+		shmem_truncate_range(inode, lstart<<PAGE_CACHE_SHIFT,
+				((lend+1)<<PAGE_CACHE_SHIFT)-1);
+		ret = 0;
+	}
+	volatile_range_unlock(&shmem_volatile_head);
+
+	return ret;
+}
+
+static int shmem_unmark_volatile(struct inode *inode, loff_t offset, loff_t len)
+{
+	loff_t lstart, lend;
+	int ret;
+
+	lstart = offset >> PAGE_CACHE_SHIFT;
+	lend = (offset+len) >> PAGE_CACHE_SHIFT;
+
+	volatile_range_lock(&shmem_volatile_head);
+	ret = volatile_range_remove(&shmem_volatile_head,
+					&inode->i_data,
+					lstart, lend);
+	volatile_range_unlock(&shmem_volatile_head);
+
+	return ret;
+}
+
+static void shmem_clear_volatile(struct inode *inode)
+{
+	volatile_range_lock(&shmem_volatile_head);
+	volatile_range_clear(&shmem_volatile_head, &inode->i_data);
+	volatile_range_unlock(&shmem_volatile_head);
+}
+
+
+
+static int shmem_purge_one_volatile_range(void)
+{
+	struct address_space *mapping;
+	loff_t start, end;
+	int ret;
+
+	volatile_range_lock(&shmem_volatile_head);
+	ret = volatile_ranges_pluck_lru(&shmem_volatile_head, &mapping,
+								&start, &end);
+	if (ret)
+		shmem_truncate_range(mapping->host, start<<PAGE_CACHE_SHIFT,
+						(end<<PAGE_CACHE_SHIFT)-1);
+	volatile_range_unlock(&shmem_volatile_head);
+	return ret;
+}
+
+
 static void shmem_evict_inode(struct inode *inode)
 {
 	struct shmem_inode_info *info = SHMEM_I(inode);
 	struct shmem_xattr *xattr, *nxattr;
 
+	shmem_clear_volatile(inode);
+
 	if (inode->i_mapping->a_ops == &shmem_aops) {
 		shmem_unacct_size(info->flags, inode->i_size);
 		inode->i_size = 0;
@@ -776,6 +845,7 @@ static int shmem_writepage(struct page *page, struct writeback_control *wbc)
 	struct inode *inode;
 	swp_entry_t swap;
 	pgoff_t index;
+	int purged;
 
 	BUG_ON(!PageLocked(page));
 	mapping = page->mapping;
@@ -830,6 +900,12 @@ static int shmem_writepage(struct page *page, struct writeback_control *wbc)
 		SetPageUptodate(page);
 	}
 
+
+	/* If we have volatile pages, try purging them first */
+	purged = shmem_purge_one_volatile_range();
+	if (purged)
+		goto redirty;
+
 	swap = get_swap_page();
 	if (!swap.val)
 		goto redirty;
@@ -1789,6 +1865,14 @@ static long shmem_fallocate(struct file *file, int mode, loff_t offset,
 		/* No need to unmap again: hole-punching leaves COWed pages */
 		error = 0;
 		goto out;
+	} else if (mode & FALLOC_FL_MARK_VOLATILE) {
+		/* Mark pages volatile, sort of delayed hole punching */
+		error = shmem_mark_volatile(inode, offset, len);
+		goto out;
+	} else if (mode & FALLOC_FL_UNMARK_VOLATILE) {
+		/* Mark pages non-volatile, return error if pages were purged */
+		error = shmem_unmark_volatile(inode, offset, len);
+		goto out;
 	}
 
 	/* We need to check rlimit even when FALLOC_FL_KEEP_SIZE */
-- 
1.7.3.2.146.gca209

[PATCH 1/3] [RFC] Interval tree implementation

[John Stultz]

After Andrew suggested something like his mumbletree idea
to better store a list of intervals, I worked on a few different
approaches, and this is what I've finally managed to get working.

The idea of storing intervals in a tree is nice, but has a number
of complications. When adding an interval, its possible that a
large interval will consume and merge a number of smaller intervals.
When removing a interval, its possible you may end up splitting an
existing interval, causing one interval to become two. This makes it
very difficult to provide generic list_head like behavior, as
the parent structures would need to be duplicated and removed,
and that has lots of memory ownership issues.

So, this is a much simplified and more list_head like
implementation. You can add a node to a tree, or remove a node
to a tree, but the generic implementation doesn't do the
merging or splitting for you. But it does provide helpers to
find overlapping and adjacent intervals.

Andrew also really wanted this interval-tree implementation to be
resuable so we don't duplicate the file locking logic. I'm not
totally convinced that the requirements between the volatile
intervals and file locking are really equivelent, but this reduced
impelementation may make it possible.

Changelog:
v2:
* Reworked code to use an rbtree instead of splaying

v3:
* Added range_tree_next_in_range() to avoid having to start
  lookups from the root every time.
* Fixed some comments and return NULL instead of 0, as suggested
  by Aneesh Kumar K.V

v6:
* Fixed range_tree_in_range() so that it finds the earliest range,
  rather then the first. This allows the next_in_range() function
  to properly cover all the ranges in the tree.
* Minor clenaups to simplify some of the functions

v7:
* Changed terminology from rangetree to intervaltree as suggested
  by Jan Kara

CC: Andrew Morton <akpm@linux-foundation.org>
CC: Android Kernel Team <kernel-team@android.com>
CC: Robert Love <rlove@google.com>
CC: Mel Gorman <mel@csn.ul.ie>
CC: Hugh Dickins <hughd@google.com>
CC: Dave Hansen <dave@linux.vnet.ibm.com>
CC: Rik van Riel <riel@redhat.com>
CC: Dmitry Adamushko <dmitry.adamushko@gmail.com>
CC: Dave Chinner <david@fromorbit.com>
CC: Neil Brown <neilb@suse.de>
CC: Andrea Righi <andrea@betterlinux.com>
CC: Aneesh Kumar K.V <aneesh.kumar@linux.vnet.ibm.com>
CC: Taras Glek <tgek@mozilla.com>
CC: Mike Hommey <mh@glandium.org>
CC: Jan Kara <jack@suse.cz>
Signed-off-by: John Stultz <john.stultz@linaro.org>
---
 include/linux/intervaltree.h |   55 +++++++++++++++++++
 lib/Makefile                 |    2 +-
 lib/intervaltree.c           |  119 ++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 175 insertions(+), 1 deletions(-)
 create mode 100644 include/linux/intervaltree.h
 create mode 100644 lib/intervaltree.c

diff --git a/include/linux/intervaltree.h b/include/linux/intervaltree.h
new file mode 100644
index 0000000..cfaa174
--- /dev/null
+++ b/include/linux/intervaltree.h
@@ -0,0 +1,55 @@
+#ifndef _LINUX_INTERVALTREE_H
+#define _LINUX_INTERVALTREE_H
+
+#include <linux/types.h>
+#include <linux/rbtree.h>
+
+struct interval_tree_node {
+	struct rb_node rb;
+	u64 start;
+	u64 end;
+};
+
+struct interval_tree_root {
+	struct rb_root head;
+};
+
+static inline void interval_tree_init(struct interval_tree_root *root)
+{
+	root->head = RB_ROOT;
+}
+
+static inline void interval_tree_node_init(struct interval_tree_node *node)
+{
+	rb_init_node(&node->rb);
+	node->start = 0;
+	node->end = 0;
+}
+
+static inline int interval_tree_empty(struct interval_tree_root *root)
+{
+	return RB_EMPTY_ROOT(&root->head);
+}
+
+static inline
+struct interval_tree_node *interval_tree_root_node(
+						struct interval_tree_root *root)
+{
+	struct interval_tree_node *ret;
+	ret = container_of(root->head.rb_node, struct interval_tree_node, rb);
+	return ret;
+}
+
+extern struct interval_tree_node *interval_tree_in_interval(
+						struct interval_tree_root *root,
+						 u64 start, u64 end);
+extern struct interval_tree_node *interval_tree_next_in_interval(
+						struct interval_tree_node *node,
+						u64 start, u64 end);
+extern void interval_tree_add(struct interval_tree_root *root,
+					struct interval_tree_node *node);
+extern void interval_tree_remove(struct interval_tree_root *root,
+					struct interval_tree_node *node);
+#endif
+
+
diff --git a/lib/Makefile b/lib/Makefile
index 8c31a0c..2bbad25 100644
--- a/lib/Makefile
+++ b/lib/Makefile
@@ -12,7 +12,7 @@ lib-y := ctype.o string.o vsprintf.o cmdline.o \
 	 idr.o int_sqrt.o extable.o prio_tree.o \
 	 sha1.o md5.o irq_regs.o reciprocal_div.o argv_split.o \
 	 proportions.o prio_heap.o ratelimit.o show_mem.o \
-	 is_single_threaded.o plist.o decompress.o
+	 is_single_threaded.o plist.o decompress.o intervaltree.o
 
 lib-$(CONFIG_MMU) += ioremap.o
 lib-$(CONFIG_SMP) += cpumask.o
diff --git a/lib/intervaltree.c b/lib/intervaltree.c
new file mode 100644
index 0000000..47c52e0
--- /dev/null
+++ b/lib/intervaltree.c
@@ -0,0 +1,119 @@
+#include <linux/intervaltree.h>
+#include <linux/kernel.h>
+#include <linux/slab.h>
+
+/* This code implements a naive interval tree, which stores a series of
+ * non-intersecting intervals.
+ * More complex interval trees can be read about here:
+ *		http://en.wikipedia.org/wiki/Interval_tree
+ */
+
+
+/**
+ * interval_tree_in_interval - Returns the first node that intersects with the
+ *                             given interval
+ * @root: interval_tree root
+ * @start: interval start
+ * @end: interval end
+ *
+ */
+struct interval_tree_node *interval_tree_in_interval(
+						struct interval_tree_root *root,
+						u64 start, u64 end)
+{
+	struct rb_node *p = root->head.rb_node;
+	struct interval_tree_node *candidate, *match = NULL;
+
+	while (p) {
+		candidate = rb_entry(p, struct interval_tree_node, rb);
+		if (end < candidate->start)
+			p = p->rb_left;
+		else if (start > candidate->end)
+			p = p->rb_right;
+		else {
+			/* We found one, but try to find an earlier match */
+			match = candidate;
+			p = p->rb_left;
+		}
+	}
+
+	return match;
+}
+
+
+/**
+ * interval_tree_next_in_interval - Return the next interval in a intervaltree
+ *                                  thatintersects with a specified interval.
+ * @root: interval_tree root
+ * @start: interval start
+ * @end: interval end
+ *
+ */
+struct interval_tree_node *interval_tree_next_in_interval(
+						struct interval_tree_node *node,
+						u64 start, u64 end)
+{
+	struct rb_node *next;
+	struct interval_tree_node *candidate;
+	if (!node)
+		return NULL;
+	next = rb_next(&node->rb);
+	if (!next)
+		return NULL;
+
+	candidate = container_of(next, struct interval_tree_node, rb);
+
+	if ((candidate->start > end) || (candidate->end < start))
+		return NULL;
+
+	return candidate;
+}
+
+/**
+ * interval_tree_add - Add a node to a interval tree
+ * @root: interval tree to be added to
+ * @node: interval_tree_node to be added
+ *
+ * Adds a node to the interval tree. Added interval should not intersect with
+ * existing intervals in the tree.
+ */
+void interval_tree_add(struct interval_tree_root *root,
+					struct interval_tree_node *node)
+{
+	struct rb_node **p = &root->head.rb_node;
+	struct rb_node *parent = NULL;
+	struct interval_tree_node *ptr;
+
+	WARN_ON_ONCE(!RB_EMPTY_NODE(&node->rb));
+
+	/* XXX might want to conditionalize this on debugging checks */
+	WARN_ON_ONCE(!!interval_tree_in_interval(root, node->start, node->end));
+
+	while (*p) {
+		parent = *p;
+		ptr = rb_entry(parent, struct interval_tree_node, rb);
+		if (node->start < ptr->start)
+			p = &(*p)->rb_left;
+		else
+			p = &(*p)->rb_right;
+	}
+	rb_link_node(&node->rb, parent, p);
+	rb_insert_color(&node->rb, &root->head);
+}
+
+
+/**
+ * interval_tree_remove: Removes a given node from the tree
+ * @root: root of tree
+ * @node: Node to be removed
+ *
+ * Removes a node and splays the tree
+ */
+void interval_tree_remove(struct interval_tree_root *root,
+					struct interval_tree_node *node)
+{
+	WARN_ON_ONCE(RB_EMPTY_NODE(&node->rb));
+
+	rb_erase(&node->rb, &root->head);
+	RB_CLEAR_NODE(&node->rb);
+}
-- 
1.7.3.2.146.gca209