File: /usr/src/linux/mm/mmap_avl.c
1 /*
2 * Searching a VMA in the linear list task->mm->mmap is horribly slow.
3 * Use an AVL (Adelson-Velskii and Landis) tree to speed up this search
4 * from O(n) to O(log n), where n is the number of VMAs of the task
5 * n is typically around 6, but may reach 3000 in some cases: object-oriented
6 * databases, persistent store, generational garbage collection (Java, Lisp),
7 * ElectricFence.
8 * Written by Bruno Haible <haible@ma2s2.mathematik.uni-karlsruhe.de>.
9 */
10
11 /* We keep the list and tree sorted by address. */
12 #define vm_avl_key vm_end
13 #define vm_avl_key_t unsigned long /* typeof(vma->avl_key) */
14
15 /*
16 * task->mm->mmap_avl is the AVL tree corresponding to task->mm->mmap
17 * or, more exactly, its root.
18 * A vm_area_struct has the following fields:
19 * vm_avl_left left son of a tree node
20 * vm_avl_right right son of a tree node
21 * vm_avl_height 1+max(heightof(left),heightof(right))
22 * The empty tree is represented as NULL.
23 */
24
25 /* Since the trees are balanced, their height will never be large. */
26 #define avl_maxheight 41 /* why this? a small exercise */
27 #define heightof(tree) ((tree) == vm_avl_empty ? 0 : (tree)->vm_avl_height)
28 /*
29 * Consistency and balancing rules:
30 * 1. tree->vm_avl_height == 1+max(heightof(tree->vm_avl_left),heightof(tree->vm_avl_right))
31 * 2. abs( heightof(tree->vm_avl_left) - heightof(tree->vm_avl_right) ) <= 1
32 * 3. foreach node in tree->vm_avl_left: node->vm_avl_key <= tree->vm_avl_key,
33 * foreach node in tree->vm_avl_right: node->vm_avl_key >= tree->vm_avl_key.
34 */
35
36 #ifdef DEBUG_AVL
37
38 /* Look up the nodes at the left and at the right of a given node. */
39 static void avl_neighbours (struct vm_area_struct * node, struct vm_area_struct * tree, struct vm_area_struct ** to_the_left, struct vm_area_struct ** to_the_right)
40 {
41 vm_avl_key_t key = node->vm_avl_key;
42
43 *to_the_left = *to_the_right = NULL;
44 for (;;) {
45 if (tree == vm_avl_empty) {
46 printk("avl_neighbours: node not found in the tree\n");
47 return;
48 }
49 if (key == tree->vm_avl_key)
50 break;
51 if (key < tree->vm_avl_key) {
52 *to_the_right = tree;
53 tree = tree->vm_avl_left;
54 } else {
55 *to_the_left = tree;
56 tree = tree->vm_avl_right;
57 }
58 }
59 if (tree != node) {
60 printk("avl_neighbours: node not exactly found in the tree\n");
61 return;
62 }
63 if (tree->vm_avl_left != vm_avl_empty) {
64 struct vm_area_struct * node;
65 for (node = tree->vm_avl_left; node->vm_avl_right != vm_avl_empty; node = node->vm_avl_right)
66 continue;
67 *to_the_left = node;
68 }
69 if (tree->vm_avl_right != vm_avl_empty) {
70 struct vm_area_struct * node;
71 for (node = tree->vm_avl_right; node->vm_avl_left != vm_avl_empty; node = node->vm_avl_left)
72 continue;
73 *to_the_right = node;
74 }
75 if ((*to_the_left && ((*to_the_left)->vm_next != node)) || (node->vm_next != *to_the_right))
76 printk("avl_neighbours: tree inconsistent with list\n");
77 }
78
79 #endif
80
81 /*
82 * Rebalance a tree.
83 * After inserting or deleting a node of a tree we have a sequence of subtrees
84 * nodes[0]..nodes[k-1] such that
85 * nodes[0] is the root and nodes[i+1] = nodes[i]->{vm_avl_left|vm_avl_right}.
86 */
87 static void avl_rebalance (struct vm_area_struct *** nodeplaces_ptr, int count)
88 {
89 for ( ; count > 0 ; count--) {
90 struct vm_area_struct ** nodeplace = *--nodeplaces_ptr;
91 struct vm_area_struct * node = *nodeplace;
92 struct vm_area_struct * nodeleft = node->vm_avl_left;
93 struct vm_area_struct * noderight = node->vm_avl_right;
94 int heightleft = heightof(nodeleft);
95 int heightright = heightof(noderight);
96 if (heightright + 1 < heightleft) {
97 /* */
98 /* * */
99 /* / \ */
100 /* n+2 n */
101 /* */
102 struct vm_area_struct * nodeleftleft = nodeleft->vm_avl_left;
103 struct vm_area_struct * nodeleftright = nodeleft->vm_avl_right;
104 int heightleftright = heightof(nodeleftright);
105 if (heightof(nodeleftleft) >= heightleftright) {
106 /* */
107 /* * n+2|n+3 */
108 /* / \ / \ */
109 /* n+2 n --> / n+1|n+2 */
110 /* / \ | / \ */
111 /* n+1 n|n+1 n+1 n|n+1 n */
112 /* */
113 node->vm_avl_left = nodeleftright; nodeleft->vm_avl_right = node;
114 nodeleft->vm_avl_height = 1 + (node->vm_avl_height = 1 + heightleftright);
115 *nodeplace = nodeleft;
116 } else {
117 /* */
118 /* * n+2 */
119 /* / \ / \ */
120 /* n+2 n --> n+1 n+1 */
121 /* / \ / \ / \ */
122 /* n n+1 n L R n */
123 /* / \ */
124 /* L R */
125 /* */
126 nodeleft->vm_avl_right = nodeleftright->vm_avl_left;
127 node->vm_avl_left = nodeleftright->vm_avl_right;
128 nodeleftright->vm_avl_left = nodeleft;
129 nodeleftright->vm_avl_right = node;
130 nodeleft->vm_avl_height = node->vm_avl_height = heightleftright;
131 nodeleftright->vm_avl_height = heightleft;
132 *nodeplace = nodeleftright;
133 }
134 }
135 else if (heightleft + 1 < heightright) {
136 /* similar to the above, just interchange 'left' <--> 'right' */
137 struct vm_area_struct * noderightright = noderight->vm_avl_right;
138 struct vm_area_struct * noderightleft = noderight->vm_avl_left;
139 int heightrightleft = heightof(noderightleft);
140 if (heightof(noderightright) >= heightrightleft) {
141 node->vm_avl_right = noderightleft; noderight->vm_avl_left = node;
142 noderight->vm_avl_height = 1 + (node->vm_avl_height = 1 + heightrightleft);
143 *nodeplace = noderight;
144 } else {
145 noderight->vm_avl_left = noderightleft->vm_avl_right;
146 node->vm_avl_right = noderightleft->vm_avl_left;
147 noderightleft->vm_avl_right = noderight;
148 noderightleft->vm_avl_left = node;
149 noderight->vm_avl_height = node->vm_avl_height = heightrightleft;
150 noderightleft->vm_avl_height = heightright;
151 *nodeplace = noderightleft;
152 }
153 }
154 else {
155 int height = (heightleft<heightright ? heightright : heightleft) + 1;
156 if (height == node->vm_avl_height)
157 break;
158 node->vm_avl_height = height;
159 }
160 }
161 }
162
163 /* Insert a node into a tree. */
164 static inline void avl_insert (struct vm_area_struct * new_node, struct vm_area_struct ** ptree)
165 {
166 vm_avl_key_t key = new_node->vm_avl_key;
167 struct vm_area_struct ** nodeplace = ptree;
168 struct vm_area_struct ** stack[avl_maxheight];
169 int stack_count = 0;
170 struct vm_area_struct *** stack_ptr = &stack[0]; /* = &stack[stackcount] */
171 for (;;) {
172 struct vm_area_struct * node = *nodeplace;
173 if (node == vm_avl_empty)
174 break;
175 *stack_ptr++ = nodeplace; stack_count++;
176 if (key < node->vm_avl_key)
177 nodeplace = &node->vm_avl_left;
178 else
179 nodeplace = &node->vm_avl_right;
180 }
181 new_node->vm_avl_left = vm_avl_empty;
182 new_node->vm_avl_right = vm_avl_empty;
183 new_node->vm_avl_height = 1;
184 *nodeplace = new_node;
185 avl_rebalance(stack_ptr,stack_count);
186 }
187
188 /* Insert a node into a tree, and
189 * return the node to the left of it and the node to the right of it.
190 */
191 static inline void avl_insert_neighbours (struct vm_area_struct * new_node, struct vm_area_struct ** ptree,
192 struct vm_area_struct ** to_the_left, struct vm_area_struct ** to_the_right)
193 {
194 vm_avl_key_t key = new_node->vm_avl_key;
195 struct vm_area_struct ** nodeplace = ptree;
196 struct vm_area_struct ** stack[avl_maxheight];
197 int stack_count = 0;
198 struct vm_area_struct *** stack_ptr = &stack[0]; /* = &stack[stackcount] */
199 *to_the_left = *to_the_right = NULL;
200 for (;;) {
201 struct vm_area_struct * node = *nodeplace;
202 if (node == vm_avl_empty)
203 break;
204 *stack_ptr++ = nodeplace; stack_count++;
205 if (key < node->vm_avl_key) {
206 *to_the_right = node;
207 nodeplace = &node->vm_avl_left;
208 } else {
209 *to_the_left = node;
210 nodeplace = &node->vm_avl_right;
211 }
212 }
213 new_node->vm_avl_left = vm_avl_empty;
214 new_node->vm_avl_right = vm_avl_empty;
215 new_node->vm_avl_height = 1;
216 *nodeplace = new_node;
217 avl_rebalance(stack_ptr,stack_count);
218 }
219
220 /* Removes a node out of a tree. */
221 static void avl_remove (struct vm_area_struct * node_to_delete, struct vm_area_struct ** ptree)
222 {
223 vm_avl_key_t key = node_to_delete->vm_avl_key;
224 struct vm_area_struct ** nodeplace = ptree;
225 struct vm_area_struct ** stack[avl_maxheight];
226 int stack_count = 0;
227 struct vm_area_struct *** stack_ptr = &stack[0]; /* = &stack[stackcount] */
228 struct vm_area_struct ** nodeplace_to_delete;
229 for (;;) {
230 struct vm_area_struct * node = *nodeplace;
231 #ifdef DEBUG_AVL
232 if (node == vm_avl_empty) {
233 /* what? node_to_delete not found in tree? */
234 printk("avl_remove: node to delete not found in tree\n");
235 return;
236 }
237 #endif
238 *stack_ptr++ = nodeplace; stack_count++;
239 if (key == node->vm_avl_key)
240 break;
241 if (key < node->vm_avl_key)
242 nodeplace = &node->vm_avl_left;
243 else
244 nodeplace = &node->vm_avl_right;
245 }
246 nodeplace_to_delete = nodeplace;
247 /* Have to remove node_to_delete = *nodeplace_to_delete. */
248 if (node_to_delete->vm_avl_left == vm_avl_empty) {
249 *nodeplace_to_delete = node_to_delete->vm_avl_right;
250 stack_ptr--; stack_count--;
251 } else {
252 struct vm_area_struct *** stack_ptr_to_delete = stack_ptr;
253 struct vm_area_struct ** nodeplace = &node_to_delete->vm_avl_left;
254 struct vm_area_struct * node;
255 for (;;) {
256 node = *nodeplace;
257 if (node->vm_avl_right == vm_avl_empty)
258 break;
259 *stack_ptr++ = nodeplace; stack_count++;
260 nodeplace = &node->vm_avl_right;
261 }
262 *nodeplace = node->vm_avl_left;
263 /* node replaces node_to_delete */
264 node->vm_avl_left = node_to_delete->vm_avl_left;
265 node->vm_avl_right = node_to_delete->vm_avl_right;
266 node->vm_avl_height = node_to_delete->vm_avl_height;
267 *nodeplace_to_delete = node; /* replace node_to_delete */
268 *stack_ptr_to_delete = &node->vm_avl_left; /* replace &node_to_delete->vm_avl_left */
269 }
270 avl_rebalance(stack_ptr,stack_count);
271 }
272
273 #ifdef DEBUG_AVL
274
275 /* print a list */
276 static void printk_list (struct vm_area_struct * vma)
277 {
278 printk("[");
279 while (vma) {
280 printk("%08lX-%08lX", vma->vm_start, vma->vm_end);
281 vma = vma->vm_next;
282 if (!vma)
283 break;
284 printk(" ");
285 }
286 printk("]");
287 }
288
289 /* print a tree */
290 static void printk_avl (struct vm_area_struct * tree)
291 {
292 if (tree != vm_avl_empty) {
293 printk("(");
294 if (tree->vm_avl_left != vm_avl_empty) {
295 printk_avl(tree->vm_avl_left);
296 printk("<");
297 }
298 printk("%08lX-%08lX", tree->vm_start, tree->vm_end);
299 if (tree->vm_avl_right != vm_avl_empty) {
300 printk(">");
301 printk_avl(tree->vm_avl_right);
302 }
303 printk(")");
304 }
305 }
306
307 static char *avl_check_point = "somewhere";
308
309 /* check a tree's consistency and balancing */
310 static void avl_checkheights (struct vm_area_struct * tree)
311 {
312 int h, hl, hr;
313
314 if (tree == vm_avl_empty)
315 return;
316 avl_checkheights(tree->vm_avl_left);
317 avl_checkheights(tree->vm_avl_right);
318 h = tree->vm_avl_height;
319 hl = heightof(tree->vm_avl_left);
320 hr = heightof(tree->vm_avl_right);
321 if ((h == hl+1) && (hr <= hl) && (hl <= hr+1))
322 return;
323 if ((h == hr+1) && (hl <= hr) && (hr <= hl+1))
324 return;
325 printk("%s: avl_checkheights: heights inconsistent\n",avl_check_point);
326 }
327
328 /* check that all values stored in a tree are < key */
329 static void avl_checkleft (struct vm_area_struct * tree, vm_avl_key_t key)
330 {
331 if (tree == vm_avl_empty)
332 return;
333 avl_checkleft(tree->vm_avl_left,key);
334 avl_checkleft(tree->vm_avl_right,key);
335 if (tree->vm_avl_key < key)
336 return;
337 printk("%s: avl_checkleft: left key %lu >= top key %lu\n",avl_check_point,tree->vm_avl_key,key);
338 }
339
340 /* check that all values stored in a tree are > key */
341 static void avl_checkright (struct vm_area_struct * tree, vm_avl_key_t key)
342 {
343 if (tree == vm_avl_empty)
344 return;
345 avl_checkright(tree->vm_avl_left,key);
346 avl_checkright(tree->vm_avl_right,key);
347 if (tree->vm_avl_key > key)
348 return;
349 printk("%s: avl_checkright: right key %lu <= top key %lu\n",avl_check_point,tree->vm_avl_key,key);
350 }
351
352 /* check that all values are properly increasing */
353 static void avl_checkorder (struct vm_area_struct * tree)
354 {
355 if (tree == vm_avl_empty)
356 return;
357 avl_checkorder(tree->vm_avl_left);
358 avl_checkorder(tree->vm_avl_right);
359 avl_checkleft(tree->vm_avl_left,tree->vm_avl_key);
360 avl_checkright(tree->vm_avl_right,tree->vm_avl_key);
361 }
362
363 /* all checks */
364 static void avl_check (struct task_struct * task, char *caller)
365 {
366 avl_check_point = caller;
367 /* printk("task \"%s\", %s\n",task->comm,caller); */
368 /* printk("task \"%s\" list: ",task->comm); printk_list(task->mm->mmap); printk("\n"); */
369 /* printk("task \"%s\" tree: ",task->comm); printk_avl(task->mm->mmap_avl); printk("\n"); */
370 avl_checkheights(task->mm->mmap_avl);
371 avl_checkorder(task->mm->mmap_avl);
372 }
373
374 #endif
375