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 | |
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')
-rw-r--r-- | include/linux/fs.h | 6 | ||||
-rw-r--r-- | include/linux/interval_tree_tmpl.h | 215 | ||||
-rw-r--r-- | include/linux/mm.h | 30 | ||||
-rw-r--r-- | include/linux/mm_types.h | 14 |
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 { | |||
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 | ||
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 @@ | |||
1 | /* | ||
2 | Interval Trees | ||
3 | (C) 2012 Michel Lespinasse <walken@google.com> | ||
4 | |||
5 | This program is free software; you can redistribute it and/or modify | ||
6 | it under the terms of the GNU General Public License as published by | ||
7 | the Free Software Foundation; either version 2 of the License, or | ||
8 | (at your option) any later version. | ||
9 | |||
10 | This program is distributed in the hope that it will be useful, | ||
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | ||
13 | GNU General Public License for more details. | ||
14 | |||
15 | You should have received a copy of the GNU General Public License | ||
16 | along with this program; if not, write to the Free Software | ||
17 | Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA | ||
18 | |||
19 | include/linux/interval_tree_tmpl.h | ||
20 | */ | ||
21 | |||
22 | /* | ||
23 | * Template for implementing interval trees | ||
24 | * | ||
25 | * ITSTRUCT: struct type of the interval tree nodes | ||
26 | * ITRB: name of struct rb_node field within ITSTRUCT | ||
27 | * ITTYPE: type of the interval endpoints | ||
28 | * ITSUBTREE: name of ITTYPE field within ITSTRUCT holding last-in-subtree | ||
29 | * ITSTART(n): start endpoint of ITSTRUCT node n | ||
30 | * ITLAST(n): last endpoing of ITSTRUCT node n | ||
31 | * ITSTATIC: 'static' or empty | ||
32 | * ITPREFIX: prefix to use for the inline tree definitions | ||
33 | */ | ||
34 | |||
35 | /* IT(name) -> ITPREFIX_name */ | ||
36 | #define _ITNAME(prefix, name) prefix ## _ ## name | ||
37 | #define ITNAME(prefix, name) _ITNAME(prefix, name) | ||
38 | #define IT(name) ITNAME(ITPREFIX, name) | ||
39 | |||
40 | /* Callbacks for augmented rbtree insert and remove */ | ||
41 | |||
42 | static inline ITTYPE IT(compute_subtree_last)(ITSTRUCT *node) | ||
43 | { | ||
44 | ITTYPE max = ITLAST(node), subtree_last; | ||
45 | if (node->ITRB.rb_left) { | ||
46 | subtree_last = rb_entry(node->ITRB.rb_left, | ||
47 | ITSTRUCT, ITRB)->ITSUBTREE; | ||
48 | if (max < subtree_last) | ||
49 | max = subtree_last; | ||
50 | } | ||
51 | if (node->ITRB.rb_right) { | ||
52 | subtree_last = rb_entry(node->ITRB.rb_right, | ||
53 | ITSTRUCT, ITRB)->ITSUBTREE; | ||
54 | if (max < subtree_last) | ||
55 | max = subtree_last; | ||
56 | } | ||
57 | return max; | ||
58 | } | ||
59 | |||
60 | static void IT(augment_propagate)(struct rb_node *rb, struct rb_node *stop) | ||
61 | { | ||
62 | while (rb != stop) { | ||
63 | ITSTRUCT *node = rb_entry(rb, ITSTRUCT, ITRB); | ||
64 | ITTYPE subtree_last = IT(compute_subtree_last)(node); | ||
65 | if (node->ITSUBTREE == subtree_last) | ||
66 | break; | ||
67 | node->ITSUBTREE = subtree_last; | ||
68 | rb = rb_parent(&node->ITRB); | ||
69 | } | ||
70 | } | ||
71 | |||
72 | static void IT(augment_copy)(struct rb_node *rb_old, struct rb_node *rb_new) | ||
73 | { | ||
74 | ITSTRUCT *old = rb_entry(rb_old, ITSTRUCT, ITRB); | ||
75 | ITSTRUCT *new = rb_entry(rb_new, ITSTRUCT, ITRB); | ||
76 | |||
77 | new->ITSUBTREE = old->ITSUBTREE; | ||
78 | } | ||
79 | |||
80 | static void IT(augment_rotate)(struct rb_node *rb_old, struct rb_node *rb_new) | ||
81 | { | ||
82 | ITSTRUCT *old = rb_entry(rb_old, ITSTRUCT, ITRB); | ||
83 | ITSTRUCT *new = rb_entry(rb_new, ITSTRUCT, ITRB); | ||
84 | |||
85 | new->ITSUBTREE = old->ITSUBTREE; | ||
86 | old->ITSUBTREE = IT(compute_subtree_last)(old); | ||
87 | } | ||
88 | |||
89 | static const struct rb_augment_callbacks IT(augment_callbacks) = { | ||
90 | IT(augment_propagate), IT(augment_copy), IT(augment_rotate) | ||
91 | }; | ||
92 | |||
93 | /* Insert / remove interval nodes from the tree */ | ||
94 | |||
95 | ITSTATIC void IT(insert)(ITSTRUCT *node, struct rb_root *root) | ||
96 | { | ||
97 | struct rb_node **link = &root->rb_node, *rb_parent = NULL; | ||
98 | ITTYPE start = ITSTART(node), last = ITLAST(node); | ||
99 | ITSTRUCT *parent; | ||
100 | |||
101 | while (*link) { | ||
102 | rb_parent = *link; | ||
103 | parent = rb_entry(rb_parent, ITSTRUCT, ITRB); | ||
104 | if (parent->ITSUBTREE < last) | ||
105 | parent->ITSUBTREE = last; | ||
106 | if (start < ITSTART(parent)) | ||
107 | link = &parent->ITRB.rb_left; | ||
108 | else | ||
109 | link = &parent->ITRB.rb_right; | ||
110 | } | ||
111 | |||
112 | node->ITSUBTREE = last; | ||
113 | rb_link_node(&node->ITRB, rb_parent, link); | ||
114 | rb_insert_augmented(&node->ITRB, root, &IT(augment_callbacks)); | ||
115 | } | ||
116 | |||
117 | ITSTATIC void IT(remove)(ITSTRUCT *node, struct rb_root *root) | ||
118 | { | ||
119 | rb_erase_augmented(&node->ITRB, root, &IT(augment_callbacks)); | ||
120 | } | ||
121 | |||
122 | /* | ||
123 | * Iterate over intervals intersecting [start;last] | ||
124 | * | ||
125 | * Note that a node's interval intersects [start;last] iff: | ||
126 | * Cond1: ITSTART(node) <= last | ||
127 | * and | ||
128 | * Cond2: start <= ITLAST(node) | ||
129 | */ | ||
130 | |||
131 | static ITSTRUCT *IT(subtree_search)(ITSTRUCT *node, ITTYPE start, ITTYPE last) | ||
132 | { | ||
133 | while (true) { | ||
134 | /* | ||
135 | * Loop invariant: start <= node->ITSUBTREE | ||
136 | * (Cond2 is satisfied by one of the subtree nodes) | ||
137 | */ | ||
138 | if (node->ITRB.rb_left) { | ||
139 | ITSTRUCT *left = rb_entry(node->ITRB.rb_left, | ||
140 | ITSTRUCT, ITRB); | ||
141 | if (start <= left->ITSUBTREE) { | ||
142 | /* | ||
143 | * Some nodes in left subtree satisfy Cond2. | ||
144 | * Iterate to find the leftmost such node N. | ||
145 | * If it also satisfies Cond1, that's the match | ||
146 | * we are looking for. Otherwise, there is no | ||
147 | * matching interval as nodes to the right of N | ||
148 | * can't satisfy Cond1 either. | ||
149 | */ | ||
150 | node = left; | ||
151 | continue; | ||
152 | } | ||
153 | } | ||
154 | if (ITSTART(node) <= last) { /* Cond1 */ | ||
155 | if (start <= ITLAST(node)) /* Cond2 */ | ||
156 | return node; /* node is leftmost match */ | ||
157 | if (node->ITRB.rb_right) { | ||
158 | node = rb_entry(node->ITRB.rb_right, | ||
159 | ITSTRUCT, ITRB); | ||
160 | if (start <= node->ITSUBTREE) | ||
161 | continue; | ||
162 | } | ||
163 | } | ||
164 | return NULL; /* No match */ | ||
165 | } | ||
166 | } | ||
167 | |||
168 | ITSTATIC ITSTRUCT *IT(iter_first)(struct rb_root *root, | ||
169 | ITTYPE start, ITTYPE last) | ||
170 | { | ||
171 | ITSTRUCT *node; | ||
172 | |||
173 | if (!root->rb_node) | ||
174 | return NULL; | ||
175 | node = rb_entry(root->rb_node, ITSTRUCT, ITRB); | ||
176 | if (node->ITSUBTREE < start) | ||
177 | return NULL; | ||
178 | return IT(subtree_search)(node, start, last); | ||
179 | } | ||
180 | |||
181 | ITSTATIC ITSTRUCT *IT(iter_next)(ITSTRUCT *node, ITTYPE start, ITTYPE last) | ||
182 | { | ||
183 | struct rb_node *rb = node->ITRB.rb_right, *prev; | ||
184 | |||
185 | while (true) { | ||
186 | /* | ||
187 | * Loop invariants: | ||
188 | * Cond1: ITSTART(node) <= last | ||
189 | * rb == node->ITRB.rb_right | ||
190 | * | ||
191 | * First, search right subtree if suitable | ||
192 | */ | ||
193 | if (rb) { | ||
194 | ITSTRUCT *right = rb_entry(rb, ITSTRUCT, ITRB); | ||
195 | if (start <= right->ITSUBTREE) | ||
196 | return IT(subtree_search)(right, start, last); | ||
197 | } | ||
198 | |||
199 | /* Move up the tree until we come from a node's left child */ | ||
200 | do { | ||
201 | rb = rb_parent(&node->ITRB); | ||
202 | if (!rb) | ||
203 | return NULL; | ||
204 | prev = &node->ITRB; | ||
205 | node = rb_entry(rb, ITSTRUCT, ITRB); | ||
206 | rb = node->ITRB.rb_right; | ||
207 | } while (prev == rb); | ||
208 | |||
209 | /* Check if the node intersects [start;last] */ | ||
210 | if (last < ITSTART(node)) /* !Cond1 */ | ||
211 | return NULL; | ||
212 | else if (start <= ITLAST(node)) /* Cond2 */ | ||
213 | return node; | ||
214 | } | ||
215 | } | ||
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 @@ | |||
10 | #include <linux/list.h> | 10 | #include <linux/list.h> |
11 | #include <linux/mmzone.h> | 11 | #include <linux/mmzone.h> |
12 | #include <linux/rbtree.h> | 12 | #include <linux/rbtree.h> |
13 | #include <linux/prio_tree.h> | ||
14 | #include <linux/atomic.h> | 13 | #include <linux/atomic.h> |
15 | #include <linux/debug_locks.h> | 14 | #include <linux/debug_locks.h> |
16 | #include <linux/mm_types.h> | 15 | #include <linux/mm_types.h> |
@@ -1355,22 +1354,27 @@ extern void zone_pcp_reset(struct zone *zone); | |||
1355 | extern atomic_long_t mmap_pages_allocated; | 1354 | extern atomic_long_t mmap_pages_allocated; |
1356 | extern int nommu_shrink_inode_mappings(struct inode *, size_t, size_t); | 1355 | extern int nommu_shrink_inode_mappings(struct inode *, size_t, size_t); |
1357 | 1356 | ||
1358 | /* prio_tree.c */ | 1357 | /* interval_tree.c */ |
1359 | void vma_prio_tree_add(struct vm_area_struct *, struct vm_area_struct *old); | 1358 | void vma_interval_tree_add(struct vm_area_struct *vma, |
1360 | void vma_prio_tree_insert(struct vm_area_struct *, struct prio_tree_root *); | 1359 | struct vm_area_struct *old, |
1361 | void vma_prio_tree_remove(struct vm_area_struct *, struct prio_tree_root *); | 1360 | struct address_space *mapping); |
1362 | struct vm_area_struct *vma_prio_tree_next(struct vm_area_struct *vma, | 1361 | void vma_interval_tree_insert(struct vm_area_struct *node, |
1363 | struct prio_tree_iter *iter); | 1362 | struct rb_root *root); |
1364 | 1363 | void vma_interval_tree_remove(struct vm_area_struct *node, | |
1365 | #define vma_prio_tree_foreach(vma, iter, root, begin, end) \ | 1364 | struct rb_root *root); |
1366 | for (prio_tree_iter_init(iter, root, begin, end), vma = NULL; \ | 1365 | struct vm_area_struct *vma_interval_tree_iter_first(struct rb_root *root, |
1367 | (vma = vma_prio_tree_next(vma, iter)); ) | 1366 | unsigned long start, unsigned long last); |
1367 | struct vm_area_struct *vma_interval_tree_iter_next(struct vm_area_struct *node, | ||
1368 | unsigned long start, unsigned long last); | ||
1369 | |||
1370 | #define vma_interval_tree_foreach(vma, root, start, last) \ | ||
1371 | for (vma = vma_interval_tree_iter_first(root, start, last); \ | ||
1372 | vma; vma = vma_interval_tree_iter_next(vma, start, last)) | ||
1368 | 1373 | ||
1369 | static inline void vma_nonlinear_insert(struct vm_area_struct *vma, | 1374 | static inline void vma_nonlinear_insert(struct vm_area_struct *vma, |
1370 | struct list_head *list) | 1375 | struct list_head *list) |
1371 | { | 1376 | { |
1372 | vma->shared.vm_set.parent = NULL; | 1377 | list_add_tail(&vma->shared.nonlinear, list); |
1373 | list_add_tail(&vma->shared.vm_set.list, list); | ||
1374 | } | 1378 | } |
1375 | 1379 | ||
1376 | /* mmap.c */ | 1380 | /* 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 @@ | |||
6 | #include <linux/threads.h> | 6 | #include <linux/threads.h> |
7 | #include <linux/list.h> | 7 | #include <linux/list.h> |
8 | #include <linux/spinlock.h> | 8 | #include <linux/spinlock.h> |
9 | #include <linux/prio_tree.h> | ||
10 | #include <linux/rbtree.h> | 9 | #include <linux/rbtree.h> |
11 | #include <linux/rwsem.h> | 10 | #include <linux/rwsem.h> |
12 | #include <linux/completion.h> | 11 | #include <linux/completion.h> |
@@ -240,18 +239,15 @@ struct vm_area_struct { | |||
240 | 239 | ||
241 | /* | 240 | /* |
242 | * For areas with an address space and backing store, | 241 | * For areas with an address space and backing store, |
243 | * linkage into the address_space->i_mmap prio tree, or | 242 | * linkage into the address_space->i_mmap interval tree, or |
244 | * linkage to the list of like vmas hanging off its node, or | ||
245 | * linkage of vma in the address_space->i_mmap_nonlinear list. | 243 | * linkage of vma in the address_space->i_mmap_nonlinear list. |
246 | */ | 244 | */ |
247 | union { | 245 | union { |
248 | struct { | 246 | struct { |
249 | struct list_head list; | 247 | struct rb_node rb; |
250 | void *parent; /* aligns with prio_tree_node parent */ | 248 | unsigned long rb_subtree_last; |
251 | struct vm_area_struct *head; | 249 | } linear; |
252 | } vm_set; | 250 | struct list_head nonlinear; |
253 | |||
254 | struct raw_prio_tree_node prio_tree_node; | ||
255 | } shared; | 251 | } shared; |
256 | 252 | ||
257 | /* | 253 | /* |