diff options
author | Michel Lespinasse <walken@google.com> | 2012-10-08 19:31:25 -0400 |
---|---|---|
committer | Linus Torvalds <torvalds@linux-foundation.org> | 2012-10-09 03:22:39 -0400 |
commit | 6b2dbba8b6ac4df26f72eda1e5ea7bab9f950e08 (patch) | |
tree | 422ed8d7ac2fe45069f20cfba84a9a097bf444af /include/linux/fs.h | |
parent | fff3fd8a1210a165252cd7cd01206da7a90d3a06 (diff) |
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>
Diffstat (limited to 'include/linux/fs.h')
-rw-r--r-- | include/linux/fs.h | 6 |
1 files changed, 3 insertions, 3 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 { | |||
401 | #include <linux/cache.h> | 401 | #include <linux/cache.h> |
402 | #include <linux/list.h> | 402 | #include <linux/list.h> |
403 | #include <linux/radix-tree.h> | 403 | #include <linux/radix-tree.h> |
404 | #include <linux/prio_tree.h> | 404 | #include <linux/rbtree.h> |
405 | #include <linux/init.h> | 405 | #include <linux/init.h> |
406 | #include <linux/pid.h> | 406 | #include <linux/pid.h> |
407 | #include <linux/bug.h> | 407 | #include <linux/bug.h> |
@@ -669,7 +669,7 @@ struct address_space { | |||
669 | struct radix_tree_root page_tree; /* radix tree of all pages */ | 669 | struct radix_tree_root page_tree; /* radix tree of all pages */ |
670 | spinlock_t tree_lock; /* and lock protecting it */ | 670 | spinlock_t tree_lock; /* and lock protecting it */ |
671 | unsigned int i_mmap_writable;/* count VM_SHARED mappings */ | 671 | unsigned int i_mmap_writable;/* count VM_SHARED mappings */ |
672 | struct prio_tree_root i_mmap; /* tree of private and shared mappings */ | 672 | struct rb_root i_mmap; /* tree of private and shared mappings */ |
673 | struct list_head i_mmap_nonlinear;/*list VM_NONLINEAR mappings */ | 673 | struct list_head i_mmap_nonlinear;/*list VM_NONLINEAR mappings */ |
674 | struct mutex i_mmap_mutex; /* protect tree, count, list */ | 674 | struct mutex i_mmap_mutex; /* protect tree, count, list */ |
675 | /* Protected by tree_lock together with the radix tree */ | 675 | /* Protected by tree_lock together with the radix tree */ |
@@ -741,7 +741,7 @@ int mapping_tagged(struct address_space *mapping, int tag); | |||
741 | */ | 741 | */ |
742 | static inline int mapping_mapped(struct address_space *mapping) | 742 | static inline int mapping_mapped(struct address_space *mapping) |
743 | { | 743 | { |
744 | return !prio_tree_empty(&mapping->i_mmap) || | 744 | return !RB_EMPTY_ROOT(&mapping->i_mmap) || |
745 | !list_empty(&mapping->i_mmap_nonlinear); | 745 | !list_empty(&mapping->i_mmap_nonlinear); |
746 | } | 746 | } |
747 | 747 | ||