aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--include/linux/interval_tree_generic.h191
-rw-r--r--include/linux/interval_tree_tmpl.h219
-rw-r--r--include/linux/mm.h6
-rw-r--r--kernel/fork.c7
-rw-r--r--lib/interval_tree.c15
-rw-r--r--mm/interval_tree.c60
6 files changed, 235 insertions, 263 deletions
diff --git a/include/linux/interval_tree_generic.h b/include/linux/interval_tree_generic.h
new file mode 100644
index 000000000000..58370e1862ad
--- /dev/null
+++ b/include/linux/interval_tree_generic.h
@@ -0,0 +1,191 @@
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_generic.h
20*/
21
22#include <linux/rbtree_augmented.h>
23
24/*
25 * Template for implementing interval trees
26 *
27 * ITSTRUCT: struct type of the interval tree nodes
28 * ITRB: name of struct rb_node field within ITSTRUCT
29 * ITTYPE: type of the interval endpoints
30 * ITSUBTREE: name of ITTYPE field within ITSTRUCT holding last-in-subtree
31 * ITSTART(n): start endpoint of ITSTRUCT node n
32 * ITLAST(n): last endpoint of ITSTRUCT node n
33 * ITSTATIC: 'static' or empty
34 * ITPREFIX: prefix to use for the inline tree definitions
35 *
36 * Note - before using this, please consider if non-generic version
37 * (interval_tree.h) would work for you...
38 */
39
40#define INTERVAL_TREE_DEFINE(ITSTRUCT, ITRB, ITTYPE, ITSUBTREE, \
41 ITSTART, ITLAST, ITSTATIC, ITPREFIX) \
42 \
43/* Callbacks for augmented rbtree insert and remove */ \
44 \
45static inline ITTYPE ITPREFIX ## _compute_subtree_last(ITSTRUCT *node) \
46{ \
47 ITTYPE max = ITLAST(node), subtree_last; \
48 if (node->ITRB.rb_left) { \
49 subtree_last = rb_entry(node->ITRB.rb_left, \
50 ITSTRUCT, ITRB)->ITSUBTREE; \
51 if (max < subtree_last) \
52 max = subtree_last; \
53 } \
54 if (node->ITRB.rb_right) { \
55 subtree_last = rb_entry(node->ITRB.rb_right, \
56 ITSTRUCT, ITRB)->ITSUBTREE; \
57 if (max < subtree_last) \
58 max = subtree_last; \
59 } \
60 return max; \
61} \
62 \
63RB_DECLARE_CALLBACKS(static, ITPREFIX ## _augment, ITSTRUCT, ITRB, \
64 ITTYPE, ITSUBTREE, ITPREFIX ## _compute_subtree_last) \
65 \
66/* Insert / remove interval nodes from the tree */ \
67 \
68ITSTATIC void ITPREFIX ## _insert(ITSTRUCT *node, struct rb_root *root) \
69{ \
70 struct rb_node **link = &root->rb_node, *rb_parent = NULL; \
71 ITTYPE start = ITSTART(node), last = ITLAST(node); \
72 ITSTRUCT *parent; \
73 \
74 while (*link) { \
75 rb_parent = *link; \
76 parent = rb_entry(rb_parent, ITSTRUCT, ITRB); \
77 if (parent->ITSUBTREE < last) \
78 parent->ITSUBTREE = last; \
79 if (start < ITSTART(parent)) \
80 link = &parent->ITRB.rb_left; \
81 else \
82 link = &parent->ITRB.rb_right; \
83 } \
84 \
85 node->ITSUBTREE = last; \
86 rb_link_node(&node->ITRB, rb_parent, link); \
87 rb_insert_augmented(&node->ITRB, root, &ITPREFIX ## _augment); \
88} \
89 \
90ITSTATIC void ITPREFIX ## _remove(ITSTRUCT *node, struct rb_root *root) \
91{ \
92 rb_erase_augmented(&node->ITRB, root, &ITPREFIX ## _augment); \
93} \
94 \
95/* \
96 * Iterate over intervals intersecting [start;last] \
97 * \
98 * Note that a node's interval intersects [start;last] iff: \
99 * Cond1: ITSTART(node) <= last \
100 * and \
101 * Cond2: start <= ITLAST(node) \
102 */ \
103 \
104static ITSTRUCT * \
105ITPREFIX ## _subtree_search(ITSTRUCT *node, ITTYPE start, ITTYPE last) \
106{ \
107 while (true) { \
108 /* \
109 * Loop invariant: start <= node->ITSUBTREE \
110 * (Cond2 is satisfied by one of the subtree nodes) \
111 */ \
112 if (node->ITRB.rb_left) { \
113 ITSTRUCT *left = rb_entry(node->ITRB.rb_left, \
114 ITSTRUCT, ITRB); \
115 if (start <= left->ITSUBTREE) { \
116 /* \
117 * Some nodes in left subtree satisfy Cond2. \
118 * Iterate to find the leftmost such node N. \
119 * If it also satisfies Cond1, that's the \
120 * match we are looking for. Otherwise, there \
121 * is no matching interval as nodes to the \
122 * right of N can't satisfy Cond1 either. \
123 */ \
124 node = left; \
125 continue; \
126 } \
127 } \
128 if (ITSTART(node) <= last) { /* Cond1 */ \
129 if (start <= ITLAST(node)) /* Cond2 */ \
130 return node; /* node is leftmost match */ \
131 if (node->ITRB.rb_right) { \
132 node = rb_entry(node->ITRB.rb_right, \
133 ITSTRUCT, ITRB); \
134 if (start <= node->ITSUBTREE) \
135 continue; \
136 } \
137 } \
138 return NULL; /* No match */ \
139 } \
140} \
141 \
142ITSTATIC ITSTRUCT * \
143ITPREFIX ## _iter_first(struct rb_root *root, ITTYPE start, ITTYPE last) \
144{ \
145 ITSTRUCT *node; \
146 \
147 if (!root->rb_node) \
148 return NULL; \
149 node = rb_entry(root->rb_node, ITSTRUCT, ITRB); \
150 if (node->ITSUBTREE < start) \
151 return NULL; \
152 return ITPREFIX ## _subtree_search(node, start, last); \
153} \
154 \
155ITSTATIC ITSTRUCT * \
156ITPREFIX ## _iter_next(ITSTRUCT *node, ITTYPE start, ITTYPE last) \
157{ \
158 struct rb_node *rb = node->ITRB.rb_right, *prev; \
159 \
160 while (true) { \
161 /* \
162 * Loop invariants: \
163 * Cond1: ITSTART(node) <= last \
164 * rb == node->ITRB.rb_right \
165 * \
166 * First, search right subtree if suitable \
167 */ \
168 if (rb) { \
169 ITSTRUCT *right = rb_entry(rb, ITSTRUCT, ITRB); \
170 if (start <= right->ITSUBTREE) \
171 return ITPREFIX ## _subtree_search(right, \
172 start, last); \
173 } \
174 \
175 /* Move up the tree until we come from a node's left child */ \
176 do { \
177 rb = rb_parent(&node->ITRB); \
178 if (!rb) \
179 return NULL; \
180 prev = &node->ITRB; \
181 node = rb_entry(rb, ITSTRUCT, ITRB); \
182 rb = node->ITRB.rb_right; \
183 } while (prev == rb); \
184 \
185 /* Check if the node intersects [start;last] */ \
186 if (last < ITSTART(node)) /* !Cond1 */ \
187 return NULL; \
188 else if (start <= ITLAST(node)) /* Cond2 */ \
189 return node; \
190 } \
191}
diff --git a/include/linux/interval_tree_tmpl.h b/include/linux/interval_tree_tmpl.h
deleted file mode 100644
index c1aeb922d65f..000000000000
--- a/include/linux/interval_tree_tmpl.h
+++ /dev/null
@@ -1,219 +0,0 @@
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#include <linux/rbtree_augmented.h>
23
24/*
25 * Template for implementing interval trees
26 *
27 * ITSTRUCT: struct type of the interval tree nodes
28 * ITRB: name of struct rb_node field within ITSTRUCT
29 * ITTYPE: type of the interval endpoints
30 * ITSUBTREE: name of ITTYPE field within ITSTRUCT holding last-in-subtree
31 * ITSTART(n): start endpoint of ITSTRUCT node n
32 * ITLAST(n): last endpoing of ITSTRUCT node n
33 * ITSTATIC: 'static' or empty
34 * ITPREFIX: prefix to use for the inline tree definitions
35 */
36
37/* IT(name) -> ITPREFIX_name */
38#define _ITNAME(prefix, name) prefix ## _ ## name
39#define ITNAME(prefix, name) _ITNAME(prefix, name)
40#define IT(name) ITNAME(ITPREFIX, name)
41
42/* Callbacks for augmented rbtree insert and remove */
43
44static inline ITTYPE IT(compute_subtree_last)(ITSTRUCT *node)
45{
46 ITTYPE max = ITLAST(node), subtree_last;
47 if (node->ITRB.rb_left) {
48 subtree_last = rb_entry(node->ITRB.rb_left,
49 ITSTRUCT, ITRB)->ITSUBTREE;
50 if (max < subtree_last)
51 max = subtree_last;
52 }
53 if (node->ITRB.rb_right) {
54 subtree_last = rb_entry(node->ITRB.rb_right,
55 ITSTRUCT, ITRB)->ITSUBTREE;
56 if (max < subtree_last)
57 max = subtree_last;
58 }
59 return max;
60}
61
62static inline void
63IT(augment_propagate)(struct rb_node *rb, struct rb_node *stop)
64{
65 while (rb != stop) {
66 ITSTRUCT *node = rb_entry(rb, ITSTRUCT, ITRB);
67 ITTYPE subtree_last = IT(compute_subtree_last)(node);
68 if (node->ITSUBTREE == subtree_last)
69 break;
70 node->ITSUBTREE = subtree_last;
71 rb = rb_parent(&node->ITRB);
72 }
73}
74
75static inline void
76IT(augment_copy)(struct rb_node *rb_old, struct rb_node *rb_new)
77{
78 ITSTRUCT *old = rb_entry(rb_old, ITSTRUCT, ITRB);
79 ITSTRUCT *new = rb_entry(rb_new, ITSTRUCT, ITRB);
80
81 new->ITSUBTREE = old->ITSUBTREE;
82}
83
84static void IT(augment_rotate)(struct rb_node *rb_old, struct rb_node *rb_new)
85{
86 ITSTRUCT *old = rb_entry(rb_old, ITSTRUCT, ITRB);
87 ITSTRUCT *new = rb_entry(rb_new, ITSTRUCT, ITRB);
88
89 new->ITSUBTREE = old->ITSUBTREE;
90 old->ITSUBTREE = IT(compute_subtree_last)(old);
91}
92
93static const struct rb_augment_callbacks IT(augment_callbacks) = {
94 IT(augment_propagate), IT(augment_copy), IT(augment_rotate)
95};
96
97/* Insert / remove interval nodes from the tree */
98
99ITSTATIC void IT(insert)(ITSTRUCT *node, struct rb_root *root)
100{
101 struct rb_node **link = &root->rb_node, *rb_parent = NULL;
102 ITTYPE start = ITSTART(node), last = ITLAST(node);
103 ITSTRUCT *parent;
104
105 while (*link) {
106 rb_parent = *link;
107 parent = rb_entry(rb_parent, ITSTRUCT, ITRB);
108 if (parent->ITSUBTREE < last)
109 parent->ITSUBTREE = last;
110 if (start < ITSTART(parent))
111 link = &parent->ITRB.rb_left;
112 else
113 link = &parent->ITRB.rb_right;
114 }
115
116 node->ITSUBTREE = last;
117 rb_link_node(&node->ITRB, rb_parent, link);
118 rb_insert_augmented(&node->ITRB, root, &IT(augment_callbacks));
119}
120
121ITSTATIC void IT(remove)(ITSTRUCT *node, struct rb_root *root)
122{
123 rb_erase_augmented(&node->ITRB, root, &IT(augment_callbacks));
124}
125
126/*
127 * Iterate over intervals intersecting [start;last]
128 *
129 * Note that a node's interval intersects [start;last] iff:
130 * Cond1: ITSTART(node) <= last
131 * and
132 * Cond2: start <= ITLAST(node)
133 */
134
135static ITSTRUCT *IT(subtree_search)(ITSTRUCT *node, ITTYPE start, ITTYPE last)
136{
137 while (true) {
138 /*
139 * Loop invariant: start <= node->ITSUBTREE
140 * (Cond2 is satisfied by one of the subtree nodes)
141 */
142 if (node->ITRB.rb_left) {
143 ITSTRUCT *left = rb_entry(node->ITRB.rb_left,
144 ITSTRUCT, ITRB);
145 if (start <= left->ITSUBTREE) {
146 /*
147 * Some nodes in left subtree satisfy Cond2.
148 * Iterate to find the leftmost such node N.
149 * If it also satisfies Cond1, that's the match
150 * we are looking for. Otherwise, there is no
151 * matching interval as nodes to the right of N
152 * can't satisfy Cond1 either.
153 */
154 node = left;
155 continue;
156 }
157 }
158 if (ITSTART(node) <= last) { /* Cond1 */
159 if (start <= ITLAST(node)) /* Cond2 */
160 return node; /* node is leftmost match */
161 if (node->ITRB.rb_right) {
162 node = rb_entry(node->ITRB.rb_right,
163 ITSTRUCT, ITRB);
164 if (start <= node->ITSUBTREE)
165 continue;
166 }
167 }
168 return NULL; /* No match */
169 }
170}
171
172ITSTATIC ITSTRUCT *IT(iter_first)(struct rb_root *root,
173 ITTYPE start, ITTYPE last)
174{
175 ITSTRUCT *node;
176
177 if (!root->rb_node)
178 return NULL;
179 node = rb_entry(root->rb_node, ITSTRUCT, ITRB);
180 if (node->ITSUBTREE < start)
181 return NULL;
182 return IT(subtree_search)(node, start, last);
183}
184
185ITSTATIC ITSTRUCT *IT(iter_next)(ITSTRUCT *node, ITTYPE start, ITTYPE last)
186{
187 struct rb_node *rb = node->ITRB.rb_right, *prev;
188
189 while (true) {
190 /*
191 * Loop invariants:
192 * Cond1: ITSTART(node) <= last
193 * rb == node->ITRB.rb_right
194 *
195 * First, search right subtree if suitable
196 */
197 if (rb) {
198 ITSTRUCT *right = rb_entry(rb, ITSTRUCT, ITRB);
199 if (start <= right->ITSUBTREE)
200 return IT(subtree_search)(right, start, last);
201 }
202
203 /* Move up the tree until we come from a node's left child */
204 do {
205 rb = rb_parent(&node->ITRB);
206 if (!rb)
207 return NULL;
208 prev = &node->ITRB;
209 node = rb_entry(rb, ITSTRUCT, ITRB);
210 rb = node->ITRB.rb_right;
211 } while (prev == rb);
212
213 /* Check if the node intersects [start;last] */
214 if (last < ITSTART(node)) /* !Cond1 */
215 return NULL;
216 else if (start <= ITLAST(node)) /* Cond2 */
217 return node;
218 }
219}
diff --git a/include/linux/mm.h b/include/linux/mm.h
index 0f671ef09eba..f1d9aaadb566 100644
--- a/include/linux/mm.h
+++ b/include/linux/mm.h
@@ -1355,11 +1355,11 @@ extern atomic_long_t mmap_pages_allocated;
1355extern int nommu_shrink_inode_mappings(struct inode *, size_t, size_t); 1355extern int nommu_shrink_inode_mappings(struct inode *, size_t, size_t);
1356 1356
1357/* interval_tree.c */ 1357/* interval_tree.c */
1358void vma_interval_tree_add(struct vm_area_struct *vma,
1359 struct vm_area_struct *old,
1360 struct address_space *mapping);
1361void vma_interval_tree_insert(struct vm_area_struct *node, 1358void vma_interval_tree_insert(struct vm_area_struct *node,
1362 struct rb_root *root); 1359 struct rb_root *root);
1360void vma_interval_tree_insert_after(struct vm_area_struct *node,
1361 struct vm_area_struct *prev,
1362 struct rb_root *root);
1363void vma_interval_tree_remove(struct vm_area_struct *node, 1363void vma_interval_tree_remove(struct vm_area_struct *node,
1364 struct rb_root *root); 1364 struct rb_root *root);
1365struct vm_area_struct *vma_interval_tree_iter_first(struct rb_root *root, 1365struct vm_area_struct *vma_interval_tree_iter_first(struct rb_root *root,
diff --git a/kernel/fork.c b/kernel/fork.c
index 90dace52715e..1cd7d581b3b2 100644
--- a/kernel/fork.c
+++ b/kernel/fork.c
@@ -423,7 +423,12 @@ static int dup_mmap(struct mm_struct *mm, struct mm_struct *oldmm)
423 mapping->i_mmap_writable++; 423 mapping->i_mmap_writable++;
424 flush_dcache_mmap_lock(mapping); 424 flush_dcache_mmap_lock(mapping);
425 /* insert tmp into the share list, just after mpnt */ 425 /* insert tmp into the share list, just after mpnt */
426 vma_interval_tree_add(tmp, mpnt, mapping); 426 if (unlikely(tmp->vm_flags & VM_NONLINEAR))
427 vma_nonlinear_insert(tmp,
428 &mapping->i_mmap_nonlinear);
429 else
430 vma_interval_tree_insert_after(tmp, mpnt,
431 &mapping->i_mmap);
427 flush_dcache_mmap_unlock(mapping); 432 flush_dcache_mmap_unlock(mapping);
428 mutex_unlock(&mapping->i_mmap_mutex); 433 mutex_unlock(&mapping->i_mmap_mutex);
429 } 434 }
diff --git a/lib/interval_tree.c b/lib/interval_tree.c
index 77a793e0644b..e6eb406f2d65 100644
--- a/lib/interval_tree.c
+++ b/lib/interval_tree.c
@@ -1,13 +1,10 @@
1#include <linux/init.h> 1#include <linux/init.h>
2#include <linux/interval_tree.h> 2#include <linux/interval_tree.h>
3#include <linux/interval_tree_generic.h>
3 4
4#define ITSTRUCT struct interval_tree_node 5#define START(node) ((node)->start)
5#define ITRB rb 6#define LAST(node) ((node)->last)
6#define ITTYPE unsigned long
7#define ITSUBTREE __subtree_last
8#define ITSTART(n) ((n)->start)
9#define ITLAST(n) ((n)->last)
10#define ITSTATIC
11#define ITPREFIX interval_tree
12 7
13#include <linux/interval_tree_tmpl.h> 8INTERVAL_TREE_DEFINE(struct interval_tree_node, rb,
9 unsigned long, __subtree_last,
10 START, LAST,, interval_tree)
diff --git a/mm/interval_tree.c b/mm/interval_tree.c
index 7dc565660e56..4ab7b9ec3a56 100644
--- a/mm/interval_tree.c
+++ b/mm/interval_tree.c
@@ -8,40 +8,38 @@
8 8
9#include <linux/mm.h> 9#include <linux/mm.h>
10#include <linux/fs.h> 10#include <linux/fs.h>
11#include <linux/interval_tree_generic.h>
11 12
12#define ITSTRUCT struct vm_area_struct 13static inline unsigned long vma_start_pgoff(struct vm_area_struct *v)
13#define ITRB shared.linear.rb 14{
14#define ITTYPE unsigned long 15 return v->vm_pgoff;
15#define ITSUBTREE shared.linear.rb_subtree_last 16}
16#define ITSTART(n) ((n)->vm_pgoff) 17
17#define ITLAST(n) ((n)->vm_pgoff + \ 18static inline unsigned long vma_last_pgoff(struct vm_area_struct *v)
18 (((n)->vm_end - (n)->vm_start) >> PAGE_SHIFT) - 1) 19{
19#define ITSTATIC 20 return v->vm_pgoff + ((v->vm_end - v->vm_start) >> PAGE_SHIFT) - 1;
20#define ITPREFIX vma_interval_tree 21}
21 22
22#include <linux/interval_tree_tmpl.h> 23INTERVAL_TREE_DEFINE(struct vm_area_struct, shared.linear.rb,
23 24 unsigned long, shared.linear.rb_subtree_last,
24/* Insert old immediately after vma in the interval tree */ 25 vma_start_pgoff, vma_last_pgoff,, vma_interval_tree)
25void vma_interval_tree_add(struct vm_area_struct *vma, 26
26 struct vm_area_struct *old, 27/* Insert node immediately after prev in the interval tree */
27 struct address_space *mapping) 28void vma_interval_tree_insert_after(struct vm_area_struct *node,
29 struct vm_area_struct *prev,
30 struct rb_root *root)
28{ 31{
29 struct rb_node **link; 32 struct rb_node **link;
30 struct vm_area_struct *parent; 33 struct vm_area_struct *parent;
31 unsigned long last; 34 unsigned long last = vma_last_pgoff(node);
32
33 if (unlikely(vma->vm_flags & VM_NONLINEAR)) {
34 list_add(&vma->shared.nonlinear, &old->shared.nonlinear);
35 return;
36 }
37 35
38 last = ITLAST(vma); 36 VM_BUG_ON(vma_start_pgoff(node) != vma_start_pgoff(prev));
39 37
40 if (!old->shared.linear.rb.rb_right) { 38 if (!prev->shared.linear.rb.rb_right) {
41 parent = old; 39 parent = prev;
42 link = &old->shared.linear.rb.rb_right; 40 link = &prev->shared.linear.rb.rb_right;
43 } else { 41 } else {
44 parent = rb_entry(old->shared.linear.rb.rb_right, 42 parent = rb_entry(prev->shared.linear.rb.rb_right,
45 struct vm_area_struct, shared.linear.rb); 43 struct vm_area_struct, shared.linear.rb);
46 if (parent->shared.linear.rb_subtree_last < last) 44 if (parent->shared.linear.rb_subtree_last < last)
47 parent->shared.linear.rb_subtree_last = last; 45 parent->shared.linear.rb_subtree_last = last;
@@ -54,8 +52,8 @@ void vma_interval_tree_add(struct vm_area_struct *vma,
54 link = &parent->shared.linear.rb.rb_left; 52 link = &parent->shared.linear.rb.rb_left;
55 } 53 }
56 54
57 vma->shared.linear.rb_subtree_last = last; 55 node->shared.linear.rb_subtree_last = last;
58 rb_link_node(&vma->shared.linear.rb, &parent->shared.linear.rb, link); 56 rb_link_node(&node->shared.linear.rb, &parent->shared.linear.rb, link);
59 rb_insert_augmented(&vma->shared.linear.rb, &mapping->i_mmap, 57 rb_insert_augmented(&node->shared.linear.rb, root,
60 &vma_interval_tree_augment_callbacks); 58 &vma_interval_tree_augment);
61} 59}
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-16 07:57:12 -0500