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