Besides that, it also adds two improvements I borrowed from Andrey
Savochkin's patch: the vm_next field is allocated in the same cache line
as vm_start and vm_end, and the function find_vma_prev halves the cost
of computing the neighbours.
Here are the timings for the common case:
2.1.119 2.1.119 2.1.119 2.1.119
plain avl fuzzyhash avl if >=32
vm_enough_memory 4 4 6 9
vma_insert_hash - - 6 -
vma_remove - - 3 -
sys_brk 6 6 8 5
do_mmap 33 25 19 20
get_unmapped_area 6 2 3 2
find_vma 27 44 67 29
find_vma_prev - - - 12
unmap_fixup 4 1 6 3
do_munmap 18 20 17 13
build_mmap_avl - 13 - 0
sys_munmap 1 0 1 0
exit_mmap 14 5 13 9
insert_vm_struct 10 23 8 12
merge_segments 17 36 28 21
total of mmap.c 140 179 185 135
Here are some timings (total system time) of a 4-minute running application
whose number of VMAs is between 40 and 60, constantly changing. In each case,
I ran the test twice; the figure is the average of two runs.
2.1.119 2.1.119 2.1.119 2.1.119
plain avl fuzzyhash avl if >=32
system time (sec) 4.04 3.97 4.16 3.95
Bruno
*** linux-2.1.119/kernel/fork.c.bak Mon Aug 31 00:43:29 1998
--- linux-2.1.119/kernel/fork.c Sun Sep 6 16:07:34 1998
***************
*** 236,251 ****
* Link in the new vma even if an error occurred,
* so that exit_mmap() can clean up the mess.
*/
! if((tmp->vm_next = *pprev) != NULL)
! (*pprev)->vm_pprev = &tmp->vm_next;
*pprev = tmp;
- tmp->vm_pprev = pprev;
pprev = &tmp->vm_next;
if (retval)
goto fail_nomem;
}
retval = 0;
fail_nomem:
flush_tlb_mm(current->mm);
--- 236,251 ----
* Link in the new vma even if an error occurred,
* so that exit_mmap() can clean up the mess.
*/
! tmp->vm_next = *pprev;
*pprev = tmp;
pprev = &tmp->vm_next;
if (retval)
goto fail_nomem;
}
retval = 0;
+ if (mm->map_count >= AVL_MIN_MAP_COUNT)
+ build_mmap_avl(mm);
fail_nomem:
flush_tlb_mm(current->mm);
***************
*** 274,280 ****
* Leave mm->pgd set to the parent's pgd
* so that pgd_offset() is always valid.
*/
! mm->mmap = mm->mmap_cache = NULL;
/* It has not run yet, so cannot be present in anyone's
* cache or tlb.
--- 274,280 ----
* Leave mm->pgd set to the parent's pgd
* so that pgd_offset() is always valid.
*/
! mm->mmap = mm->mmap_avl = mm->mmap_cache = NULL;
/* It has not run yet, so cannot be present in anyone's
* cache or tlb.
*** linux-2.1.119/mm/mmap.c.bak Mon Aug 31 00:43:31 1998
--- linux-2.1.119/mm/mmap.c Sun Sep 6 19:50:03 1998
***************
*** 356,361 ****
--- 356,454 ----
}
}
+ #define vm_avl_empty (struct vm_area_struct *) NULL
+
+ #include "mmap_avl.c"
+
+ /* Look up the first VMA which satisfies addr < vm_end, NULL if none. */
+ struct vm_area_struct * find_vma(struct mm_struct * mm, unsigned long addr)
+ {
+ struct vm_area_struct *vma = NULL;
+
+ if (mm) {
+ /* Check the cache first. */
+ /* (Cache hit rate is typically around 35%.) */
+ vma = mm->mmap_cache;
+ if (!(vma && vma->vm_end > addr && vma->vm_start <= addr)) {
+ if (!mm->mmap_avl) {
+ /* Go through the linear list. */
+ vma = mm->mmap;
+ while (vma && vma->vm_end <= addr)
+ vma = vma->vm_next;
+ } else {
+ /* Then go through the AVL tree quickly. */
+ struct vm_area_struct * tree = mm->mmap_avl;
+ for (;;) {
+ if (tree == vm_avl_empty)
+ break;
+ if (tree->vm_end > addr) {
+ vma = tree;
+ if (tree->vm_start <= addr)
+ break;
+ tree = tree->vm_avl_left;
+ } else
+ tree = tree->vm_avl_right;
+ }
+ }
+ if (vma)
+ mm->mmap_cache = vma;
+ }
+ }
+ return vma;
+ }
+
+ /* Same as find_vma, but also return a pointer to the previous VMA in *pprev. */
+ struct vm_area_struct * find_vma_prev(struct mm_struct * mm, unsigned long addr,
+ struct vm_area_struct **pprev)
+ {
+ if (mm) {
+ if (!mm->mmap_avl) {
+ /* Go through the linear list. */
+ struct vm_area_struct * prev = NULL;
+ struct vm_area_struct * vma = mm->mmap;
+ while (vma && vma->vm_end <= addr) {
+ prev = vma;
+ vma = vma->vm_next;
+ }
+ *pprev = prev;
+ return vma;
+ } else {
+ /* Go through the AVL tree quickly. */
+ struct vm_area_struct * vma = NULL;
+ struct vm_area_struct * last_turn_right = NULL;
+ struct vm_area_struct * prev = NULL;
+ struct vm_area_struct * tree = mm->mmap_avl;
+ for (;;) {
+ if (tree == vm_avl_empty)
+ break;
+ if (tree->vm_end > addr) {
+ vma = tree;
+ prev = last_turn_right;
+ if (tree->vm_start <= addr)
+ break;
+ tree = tree->vm_avl_left;
+ } else {
+ last_turn_right = tree;
+ tree = tree->vm_avl_right;
+ }
+ }
+ if (vma) {
+ if (vma->vm_avl_left != vm_avl_empty) {
+ prev = vma->vm_avl_left;
+ while (prev->vm_avl_right != vm_avl_empty)
+ prev = prev->vm_avl_right;
+ }
+ if ((prev ? prev->vm_next : mm->mmap) != vma)
+ printk("find_vma_prev: tree inconsistent with list\n");
+ *pprev = prev;
+ return vma;
+ }
+ }
+ }
+ *pprev = NULL;
+ return NULL;
+ }
+
/* Normal function to fix up a mapping
* This function is the default for when an area has no specific
* function. This may be used as part of a more specific routine.
***************
*** 438,444 ****
int do_munmap(unsigned long addr, size_t len)
{
struct mm_struct * mm;
! struct vm_area_struct *mpnt, *free, *extra;
int freed;
if ((addr & ~PAGE_MASK) || addr > TASK_SIZE || len > TASK_SIZE-addr)
--- 531,537 ----
int do_munmap(unsigned long addr, size_t len)
{
struct mm_struct * mm;
! struct vm_area_struct *mpnt, *prev, **npp, *free, *extra;
int freed;
if ((addr & ~PAGE_MASK) || addr > TASK_SIZE || len > TASK_SIZE-addr)
***************
*** 453,467 ****
* on the list. If nothing is put on, nothing is affected.
*/
mm = current->mm;
! mpnt = mm->mmap;
! while(mpnt && mpnt->vm_end <= addr)
! mpnt = mpnt->vm_next;
if (!mpnt)
return 0;
/* If we'll make "hole", check the vm areas limit */
! if ((mpnt->vm_start < addr && mpnt->vm_end > addr+len) &&
! mm->map_count > MAX_MAP_COUNT)
return -ENOMEM;
/*
--- 546,562 ----
* on the list. If nothing is put on, nothing is affected.
*/
mm = current->mm;
! mpnt = find_vma_prev(mm, addr, &prev);
if (!mpnt)
return 0;
+ /* we have addr < mpnt->vm_end */
+
+ if (mpnt->vm_start >= addr+len)
+ return 0;
/* If we'll make "hole", check the vm areas limit */
! if ((mpnt->vm_start < addr && mpnt->vm_end > addr+len)
! && mm->map_count >= MAX_MAP_COUNT)
return -ENOMEM;
/*
***************
*** 472,489 ****
if (!extra)
return -ENOMEM;
! /* we have addr < mpnt->vm_end */
free = NULL;
! for ( ; mpnt && mpnt->vm_start < addr+len; ) {
! struct vm_area_struct *next = mpnt->vm_next;
!
! if(mpnt->vm_next)
! mpnt->vm_next->vm_pprev = mpnt->vm_pprev;
! *mpnt->vm_pprev = mpnt->vm_next;
!
mpnt->vm_next = free;
free = mpnt;
! mpnt = next;
}
/* Ok - we have the memory areas we should free on the 'free' list,
--- 567,580 ----
if (!extra)
return -ENOMEM;
! npp = (prev ? &prev->vm_next : &mm->mmap);
free = NULL;
! for ( ; mpnt && mpnt->vm_start < addr+len; mpnt = *npp) {
! *npp = mpnt->vm_next;
mpnt->vm_next = free;
free = mpnt;
! if (mm->mmap_avl)
! avl_remove(mpnt, &mm->mmap_avl);
}
/* Ok - we have the memory areas we should free on the 'free' list,
***************
*** 541,553 ****
return ret;
}
/* Release all mmaps. */
void exit_mmap(struct mm_struct * mm)
{
struct vm_area_struct * mpnt;
mpnt = mm->mmap;
! mm->mmap = mm->mmap_cache = NULL;
mm->rss = 0;
mm->total_vm = 0;
mm->locked_vm = 0;
--- 632,654 ----
return ret;
}
+ /* Build the AVL tree corresponding to the VMA list. */
+ void build_mmap_avl(struct mm_struct * mm)
+ {
+ struct vm_area_struct * vma;
+
+ mm->mmap_avl = NULL;
+ for (vma = mm->mmap; vma; vma = vma->vm_next)
+ avl_insert(vma, &mm->mmap_avl);
+ }
+
/* Release all mmaps. */
void exit_mmap(struct mm_struct * mm)
{
struct vm_area_struct * mpnt;
mpnt = mm->mmap;
! mm->mmap = mm->mmap_avl = mm->mmap_cache = NULL;
mm->rss = 0;
mm->total_vm = 0;
mm->locked_vm = 0;
***************
*** 582,601 ****
*/
void insert_vm_struct(struct mm_struct *mm, struct vm_area_struct *vmp)
{
! struct vm_area_struct **pprev = &mm->mmap;
struct file * file;
! mm->map_count++;
!
! /* Find where to link it in. */
! while(*pprev && (*pprev)->vm_start <= vmp->vm_start)
! pprev = &(*pprev)->vm_next;
!
! /* Insert it. */
! if((vmp->vm_next = *pprev) != NULL)
! (*pprev)->vm_pprev = &vmp->vm_next;
*pprev = vmp;
! vmp->vm_pprev = pprev;
file = vmp->vm_file;
if (file) {
--- 683,708 ----
*/
void insert_vm_struct(struct mm_struct *mm, struct vm_area_struct *vmp)
{
! struct vm_area_struct **pprev;
struct file * file;
! if (!mm->mmap_avl) {
! pprev = &mm->mmap;
! while (*pprev && (*pprev)->vm_start <= vmp->vm_start)
! pprev = &(*pprev)->vm_next;
! } else {
! struct vm_area_struct *prev, *next;
! avl_insert_neighbours(vmp, &mm->mmap_avl, &prev, &next);
! pprev = (prev ? &prev->vm_next : &mm->mmap);
! if (*pprev != next)
! printk("insert_vm_struct: tree inconsistent with list\n");
! }
! vmp->vm_next = *pprev;
*pprev = vmp;
!
! mm->map_count++;
! if (mm->map_count >= AVL_MIN_MAP_COUNT && !mm->mmap_avl)
! build_mmap_avl(mm);
file = vmp->vm_file;
if (file) {
***************
*** 621,643 ****
*/
void merge_segments (struct mm_struct * mm, unsigned long start_addr, unsigned long end_addr)
{
! struct vm_area_struct *prev, *mpnt, *next;
! prev = NULL;
! mpnt = mm->mmap;
! while(mpnt && mpnt->vm_end <= start_addr) {
! prev = mpnt;
! mpnt = mpnt->vm_next;
! }
if (!mpnt)
return;
! next = mpnt->vm_next;
!
! /* we have prev->vm_next == mpnt && mpnt->vm_next = next */
! if (!prev) {
prev = mpnt;
! mpnt = next;
}
/* prev and mpnt cycle through the list, as long as
--- 728,744 ----
*/
void merge_segments (struct mm_struct * mm, unsigned long start_addr, unsigned long end_addr)
{
! struct vm_area_struct *prev, *mpnt, *next, *prev1;
! mpnt = find_vma_prev(mm, start_addr, &prev1);
if (!mpnt)
return;
! if (prev1) {
! prev = prev1;
! } else {
prev = mpnt;
! mpnt = mpnt->vm_next;
}
/* prev and mpnt cycle through the list, as long as
***************
*** 668,678 ****
* big segment can possibly merge with the next one.
* The old unused mpnt is freed.
*/
! if(mpnt->vm_next)
! mpnt->vm_next->vm_pprev = mpnt->vm_pprev;
! *mpnt->vm_pprev = mpnt->vm_next;
!
prev->vm_end = mpnt->vm_end;
if (mpnt->vm_ops && mpnt->vm_ops->close) {
mpnt->vm_offset += mpnt->vm_end - mpnt->vm_start;
mpnt->vm_start = mpnt->vm_end;
--- 769,778 ----
* big segment can possibly merge with the next one.
* The old unused mpnt is freed.
*/
! if (mm->mmap_avl)
! avl_remove(mpnt, &mm->mmap_avl);
prev->vm_end = mpnt->vm_end;
+ prev->vm_next = mpnt->vm_next;
if (mpnt->vm_ops && mpnt->vm_ops->close) {
mpnt->vm_offset += mpnt->vm_end - mpnt->vm_start;
mpnt->vm_start = mpnt->vm_end;
*** linux-2.1.119/mm/mmap_avl.c.bak Wed Sep 2 11:10:34 1998
--- linux-2.1.119/mm/mmap_avl.c Sun Sep 6 19:47:40 1998
***************
*** 0 ****
--- 1,374 ----
+ /*
+ * Searching a VMA in the linear list task->mm->mmap is horribly slow.
+ * Use an AVL (Adelson-Velskii and Landis) tree to speed up this search
+ * from O(n) to O(log n), where n is the number of VMAs of the task
+ * n is typically around 6, but may reach 3000 in some cases: object-oriented
+ * databases, persistent store, generational garbage collection (Java, Lisp),
+ * ElectricFence.
+ * Written by Bruno Haible <haible@ma2s2.mathematik.uni-karlsruhe.de>.
+ */
+
+ /* We keep the list and tree sorted by address. */
+ #define vm_avl_key vm_end
+ #define vm_avl_key_t unsigned long /* typeof(vma->avl_key) */
+
+ /*
+ * task->mm->mmap_avl is the AVL tree corresponding to task->mm->mmap
+ * or, more exactly, its root.
+ * A vm_area_struct has the following fields:
+ * vm_avl_left left son of a tree node
+ * vm_avl_right right son of a tree node
+ * vm_avl_height 1+max(heightof(left),heightof(right))
+ * The empty tree is represented as NULL.
+ */
+
+ /* Since the trees are balanced, their height will never be large. */
+ #define avl_maxheight 41 /* why this? a small exercise */
+ #define heightof(tree) ((tree) == vm_avl_empty ? 0 : (tree)->vm_avl_height)
+ /*
+ * Consistency and balancing rules:
+ * 1. tree->vm_avl_height == 1+max(heightof(tree->vm_avl_left),heightof(tree->vm_avl_right))
+ * 2. abs( heightof(tree->vm_avl_left) - heightof(tree->vm_avl_right) ) <= 1
+ * 3. foreach node in tree->vm_avl_left: node->vm_avl_key <= tree->vm_avl_key,
+ * foreach node in tree->vm_avl_right: node->vm_avl_key >= tree->vm_avl_key.
+ */
+
+ #ifdef DEBUG_AVL
+
+ /* Look up the nodes at the left and at the right of a given node. */
+ 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)
+ {
+ vm_avl_key_t key = node->vm_avl_key;
+
+ *to_the_left = *to_the_right = NULL;
+ for (;;) {
+ if (tree == vm_avl_empty) {
+ printk("avl_neighbours: node not found in the tree\n");
+ return;
+ }
+ if (key == tree->vm_avl_key)
+ break;
+ if (key < tree->vm_avl_key) {
+ *to_the_right = tree;
+ tree = tree->vm_avl_left;
+ } else {
+ *to_the_left = tree;
+ tree = tree->vm_avl_right;
+ }
+ }
+ if (tree != node) {
+ printk("avl_neighbours: node not exactly found in the tree\n");
+ return;
+ }
+ if (tree->vm_avl_left != vm_avl_empty) {
+ struct vm_area_struct * node;
+ for (node = tree->vm_avl_left; node->vm_avl_right != vm_avl_empty; node = node->vm_avl_right)
+ continue;
+ *to_the_left = node;
+ }
+ if (tree->vm_avl_right != vm_avl_empty) {
+ struct vm_area_struct * node;
+ for (node = tree->vm_avl_right; node->vm_avl_left != vm_avl_empty; node = node->vm_avl_left)
+ continue;
+ *to_the_right = node;
+ }
+ if ((*to_the_left && ((*to_the_left)->vm_next != node)) || (node->vm_next != *to_the_right))
+ printk("avl_neighbours: tree inconsistent with list\n");
+ }
+
+ #endif
+
+ /*
+ * Rebalance a tree.
+ * After inserting or deleting a node of a tree we have a sequence of subtrees
+ * nodes[0]..nodes[k-1] such that
+ * nodes[0] is the root and nodes[i+1] = nodes[i]->{vm_avl_left|vm_avl_right}.
+ */
+ static void avl_rebalance (struct vm_area_struct *** nodeplaces_ptr, int count)
+ {
+ for ( ; count > 0 ; count--) {
+ struct vm_area_struct ** nodeplace = *--nodeplaces_ptr;
+ struct vm_area_struct * node = *nodeplace;
+ struct vm_area_struct * nodeleft = node->vm_avl_left;
+ struct vm_area_struct * noderight = node->vm_avl_right;
+ int heightleft = heightof(nodeleft);
+ int heightright = heightof(noderight);
+ if (heightright + 1 < heightleft) {
+ /* */
+ /* * */
+ /* / \ */
+ /* n+2 n */
+ /* */
+ struct vm_area_struct * nodeleftleft = nodeleft->vm_avl_left;
+ struct vm_area_struct * nodeleftright = nodeleft->vm_avl_right;
+ int heightleftright = heightof(nodeleftright);
+ if (heightof(nodeleftleft) >= heightleftright) {
+ /* */
+ /* * n+2|n+3 */
+ /* / \ / \ */
+ /* n+2 n --> / n+1|n+2 */
+ /* / \ | / \ */
+ /* n+1 n|n+1 n+1 n|n+1 n */
+ /* */
+ node->vm_avl_left = nodeleftright; nodeleft->vm_avl_right = node;
+ nodeleft->vm_avl_height = 1 + (node->vm_avl_height = 1 + heightleftright);
+ *nodeplace = nodeleft;
+ } else {
+ /* */
+ /* * n+2 */
+ /* / \ / \ */
+ /* n+2 n --> n+1 n+1 */
+ /* / \ / \ / \ */
+ /* n n+1 n L R n */
+ /* / \ */
+ /* L R */
+ /* */
+ nodeleft->vm_avl_right = nodeleftright->vm_avl_left;
+ node->vm_avl_left = nodeleftright->vm_avl_right;
+ nodeleftright->vm_avl_left = nodeleft;
+ nodeleftright->vm_avl_right = node;
+ nodeleft->vm_avl_height = node->vm_avl_height = heightleftright;
+ nodeleftright->vm_avl_height = heightleft;
+ *nodeplace = nodeleftright;
+ }
+ }
+ else if (heightleft + 1 < heightright) {
+ /* similar to the above, just interchange 'left' <--> 'right' */
+ struct vm_area_struct * noderightright = noderight->vm_avl_right;
+ struct vm_area_struct * noderightleft = noderight->vm_avl_left;
+ int heightrightleft = heightof(noderightleft);
+ if (heightof(noderightright) >= heightrightleft) {
+ node->vm_avl_right = noderightleft; noderight->vm_avl_left = node;
+ noderight->vm_avl_height = 1 + (node->vm_avl_height = 1 + heightrightleft);
+ *nodeplace = noderight;
+ } else {
+ noderight->vm_avl_left = noderightleft->vm_avl_right;
+ node->vm_avl_right = noderightleft->vm_avl_left;
+ noderightleft->vm_avl_right = noderight;
+ noderightleft->vm_avl_left = node;
+ noderight->vm_avl_height = node->vm_avl_height = heightrightleft;
+ noderightleft->vm_avl_height = heightright;
+ *nodeplace = noderightleft;
+ }
+ }
+ else {
+ int height = (heightleft<heightright ? heightright : heightleft) + 1;
+ if (height == node->vm_avl_height)
+ break;
+ node->vm_avl_height = height;
+ }
+ }
+ }
+
+ /* Insert a node into a tree. */
+ static inline void avl_insert (struct vm_area_struct * new_node, struct vm_area_struct ** ptree)
+ {
+ vm_avl_key_t key = new_node->vm_avl_key;
+ struct vm_area_struct ** nodeplace = ptree;
+ struct vm_area_struct ** stack[avl_maxheight];
+ int stack_count = 0;
+ struct vm_area_struct *** stack_ptr = &stack[0]; /* = &stack[stackcount] */
+ for (;;) {
+ struct vm_area_struct * node = *nodeplace;
+ if (node == vm_avl_empty)
+ break;
+ *stack_ptr++ = nodeplace; stack_count++;
+ if (key < node->vm_avl_key)
+ nodeplace = &node->vm_avl_left;
+ else
+ nodeplace = &node->vm_avl_right;
+ }
+ new_node->vm_avl_left = vm_avl_empty;
+ new_node->vm_avl_right = vm_avl_empty;
+ new_node->vm_avl_height = 1;
+ *nodeplace = new_node;
+ avl_rebalance(stack_ptr,stack_count);
+ }
+
+ /* Insert a node into a tree, and
+ * return the node to the left of it and the node to the right of it.
+ */
+ static inline void avl_insert_neighbours (struct vm_area_struct * new_node, struct vm_area_struct ** ptree,
+ struct vm_area_struct ** to_the_left, struct vm_area_struct ** to_the_right)
+ {
+ vm_avl_key_t key = new_node->vm_avl_key;
+ struct vm_area_struct ** nodeplace = ptree;
+ struct vm_area_struct ** stack[avl_maxheight];
+ int stack_count = 0;
+ struct vm_area_struct *** stack_ptr = &stack[0]; /* = &stack[stackcount] */
+ *to_the_left = *to_the_right = NULL;
+ for (;;) {
+ struct vm_area_struct * node = *nodeplace;
+ if (node == vm_avl_empty)
+ break;
+ *stack_ptr++ = nodeplace; stack_count++;
+ if (key < node->vm_avl_key) {
+ *to_the_right = node;
+ nodeplace = &node->vm_avl_left;
+ } else {
+ *to_the_left = node;
+ nodeplace = &node->vm_avl_right;
+ }
+ }
+ new_node->vm_avl_left = vm_avl_empty;
+ new_node->vm_avl_right = vm_avl_empty;
+ new_node->vm_avl_height = 1;
+ *nodeplace = new_node;
+ avl_rebalance(stack_ptr,stack_count);
+ }
+
+ /* Removes a node out of a tree. */
+ static void avl_remove (struct vm_area_struct * node_to_delete, struct vm_area_struct ** ptree)
+ {
+ vm_avl_key_t key = node_to_delete->vm_avl_key;
+ struct vm_area_struct ** nodeplace = ptree;
+ struct vm_area_struct ** stack[avl_maxheight];
+ int stack_count = 0;
+ struct vm_area_struct *** stack_ptr = &stack[0]; /* = &stack[stackcount] */
+ struct vm_area_struct ** nodeplace_to_delete;
+ for (;;) {
+ struct vm_area_struct * node = *nodeplace;
+ #ifdef DEBUG_AVL
+ if (node == vm_avl_empty) {
+ /* what? node_to_delete not found in tree? */
+ printk("avl_remove: node to delete not found in tree\n");
+ return;
+ }
+ #endif
+ *stack_ptr++ = nodeplace; stack_count++;
+ if (key == node->vm_avl_key)
+ break;
+ if (key < node->vm_avl_key)
+ nodeplace = &node->vm_avl_left;
+ else
+ nodeplace = &node->vm_avl_right;
+ }
+ nodeplace_to_delete = nodeplace;
+ /* Have to remove node_to_delete = *nodeplace_to_delete. */
+ if (node_to_delete->vm_avl_left == vm_avl_empty) {
+ *nodeplace_to_delete = node_to_delete->vm_avl_right;
+ stack_ptr--; stack_count--;
+ } else {
+ struct vm_area_struct *** stack_ptr_to_delete = stack_ptr;
+ struct vm_area_struct ** nodeplace = &node_to_delete->vm_avl_left;
+ struct vm_area_struct * node;
+ for (;;) {
+ node = *nodeplace;
+ if (node->vm_avl_right == vm_avl_empty)
+ break;
+ *stack_ptr++ = nodeplace; stack_count++;
+ nodeplace = &node->vm_avl_right;
+ }
+ *nodeplace = node->vm_avl_left;
+ /* node replaces node_to_delete */
+ node->vm_avl_left = node_to_delete->vm_avl_left;
+ node->vm_avl_right = node_to_delete->vm_avl_right;
+ node->vm_avl_height = node_to_delete->vm_avl_height;
+ *nodeplace_to_delete = node; /* replace node_to_delete */
+ *stack_ptr_to_delete = &node->vm_avl_left; /* replace &node_to_delete->vm_avl_left */
+ }
+ avl_rebalance(stack_ptr,stack_count);
+ }
+
+ #ifdef DEBUG_AVL
+
+ /* print a list */
+ static void printk_list (struct vm_area_struct * vma)
+ {
+ printk("[");
+ while (vma) {
+ printk("%08lX-%08lX", vma->vm_start, vma->vm_end);
+ vma = vma->vm_next;
+ if (!vma)
+ break;
+ printk(" ");
+ }
+ printk("]");
+ }
+
+ /* print a tree */
+ static void printk_avl (struct vm_area_struct * tree)
+ {
+ if (tree != vm_avl_empty) {
+ printk("(");
+ if (tree->vm_avl_left != vm_avl_empty) {
+ printk_avl(tree->vm_avl_left);
+ printk("<");
+ }
+ printk("%08lX-%08lX", tree->vm_start, tree->vm_end);
+ if (tree->vm_avl_right != vm_avl_empty) {
+ printk(">");
+ printk_avl(tree->vm_avl_right);
+ }
+ printk(")");
+ }
+ }
+
+ static char *avl_check_point = "somewhere";
+
+ /* check a tree's consistency and balancing */
+ static void avl_checkheights (struct vm_area_struct * tree)
+ {
+ int h, hl, hr;
+
+ if (tree == vm_avl_empty)
+ return;
+ avl_checkheights(tree->vm_avl_left);
+ avl_checkheights(tree->vm_avl_right);
+ h = tree->vm_avl_height;
+ hl = heightof(tree->vm_avl_left);
+ hr = heightof(tree->vm_avl_right);
+ if ((h == hl+1) && (hr <= hl) && (hl <= hr+1))
+ return;
+ if ((h == hr+1) && (hl <= hr) && (hr <= hl+1))
+ return;
+ printk("%s: avl_checkheights: heights inconsistent\n",avl_check_point);
+ }
+
+ /* check that all values stored in a tree are < key */
+ static void avl_checkleft (struct vm_area_struct * tree, vm_avl_key_t key)
+ {
+ if (tree == vm_avl_empty)
+ return;
+ avl_checkleft(tree->vm_avl_left,key);
+ avl_checkleft(tree->vm_avl_right,key);
+ if (tree->vm_avl_key < key)
+ return;
+ printk("%s: avl_checkleft: left key %lu >= top key %lu\n",avl_check_point,tree->vm_avl_key,key);
+ }
+
+ /* check that all values stored in a tree are > key */
+ static void avl_checkright (struct vm_area_struct * tree, vm_avl_key_t key)
+ {
+ if (tree == vm_avl_empty)
+ return;
+ avl_checkright(tree->vm_avl_left,key);
+ avl_checkright(tree->vm_avl_right,key);
+ if (tree->vm_avl_key > key)
+ return;
+ printk("%s: avl_checkright: right key %lu <= top key %lu\n",avl_check_point,tree->vm_avl_key,key);
+ }
+
+ /* check that all values are properly increasing */
+ static void avl_checkorder (struct vm_area_struct * tree)
+ {
+ if (tree == vm_avl_empty)
+ return;
+ avl_checkorder(tree->vm_avl_left);
+ avl_checkorder(tree->vm_avl_right);
+ avl_checkleft(tree->vm_avl_left,tree->vm_avl_key);
+ avl_checkright(tree->vm_avl_right,tree->vm_avl_key);
+ }
+
+ /* all checks */
+ static void avl_check (struct task_struct * task, char *caller)
+ {
+ avl_check_point = caller;
+ /* printk("task \"%s\", %s\n",task->comm,caller); */
+ /* printk("task \"%s\" list: ",task->comm); printk_list(task->mm->mmap); printk("\n"); */
+ /* printk("task \"%s\" tree: ",task->comm); printk_avl(task->mm->mmap_avl); printk("\n"); */
+ avl_checkheights(task->mm->mmap_avl);
+ avl_checkorder(task->mm->mmap_avl);
+ }
+
+ #endif
*** linux-2.1.119/include/linux/sched.h.bak Mon Aug 31 03:14:21 1998
--- linux-2.1.119/include/linux/sched.h Sun Sep 6 16:13:29 1998
***************
*** 157,167 ****
/* Maximum number of active map areas.. This is a random (large) number */
#define MAX_MAP_COUNT (65536)
struct mm_struct {
! struct vm_area_struct *mmap, *mmap_cache;
pgd_t * pgd;
atomic_t count;
! int map_count;
struct semaphore mmap_sem;
unsigned long context;
unsigned long start_code, end_code, start_data, end_data;
--- 157,172 ----
/* Maximum number of active map areas.. This is a random (large) number */
#define MAX_MAP_COUNT (65536)
+ /* Number of map areas at which the AVL tree is activated. This is arbitrary. */
+ #define AVL_MIN_MAP_COUNT 32
+
struct mm_struct {
! struct vm_area_struct *mmap; /* list of VMAs */
! struct vm_area_struct *mmap_avl; /* tree of VMAs */
! struct vm_area_struct *mmap_cache; /* last find_vma result */
pgd_t * pgd;
atomic_t count;
! int map_count; /* number of VMAs */
struct semaphore mmap_sem;
unsigned long context;
unsigned long start_code, end_code, start_data, end_data;
***************
*** 178,184 ****
};
#define INIT_MM { \
! &init_mmap, NULL, swapper_pg_dir, \
ATOMIC_INIT(1), 1, \
MUTEX, \
0, \
--- 183,190 ----
};
#define INIT_MM { \
! &init_mmap, NULL, NULL, \
! swapper_pg_dir, \
ATOMIC_INIT(1), 1, \
MUTEX, \
0, \
*** linux-2.1.119/include/linux/mm.h.bak Mon Aug 31 03:14:21 1998
--- linux-2.1.119/include/linux/mm.h Sun Sep 6 16:13:29 1998
***************
*** 35,44 ****
struct mm_struct * vm_mm; /* VM area parameters */
unsigned long vm_start;
unsigned long vm_end;
pgprot_t vm_page_prot;
unsigned short vm_flags;
! struct vm_area_struct *vm_next;
! struct vm_area_struct **vm_pprev;
/* For areas with inode, the list inode->i_mmap, for shm areas,
* the list of attaches, otherwise unused.
--- 35,51 ----
struct mm_struct * vm_mm; /* VM area parameters */
unsigned long vm_start;
unsigned long vm_end;
+
+ /* linked list of VM areas per task, sorted by address */
+ struct vm_area_struct *vm_next;
+
pgprot_t vm_page_prot;
unsigned short vm_flags;
!
! /* AVL tree of VM areas per task, sorted by address */
! short vm_avl_height;
! struct vm_area_struct * vm_avl_left;
! struct vm_area_struct * vm_avl_right;
/* For areas with inode, the list inode->i_mmap, for shm areas,
* the list of attaches, otherwise unused.
***************
*** 294,299 ****
--- 301,307 ----
extern void vma_init(void);
extern void merge_segments(struct mm_struct *, unsigned long, unsigned long);
extern void insert_vm_struct(struct mm_struct *, struct vm_area_struct *);
+ extern void build_mmap_avl(struct mm_struct *);
extern void exit_mmap(struct mm_struct *);
extern unsigned long get_unmapped_area(unsigned long, unsigned long);
***************
*** 352,373 ****
}
/* Look up the first VMA which satisfies addr < vm_end, NULL if none. */
! static inline struct vm_area_struct * find_vma(struct mm_struct * mm, unsigned long addr)
! {
! struct vm_area_struct *vma = NULL;
!
! if (mm) {
! /* Check the cache first. */
! vma = mm->mmap_cache;
! if(!vma || (vma->vm_end <= addr) || (vma->vm_start > addr)) {
! vma = mm->mmap;
! while(vma && vma->vm_end <= addr)
! vma = vma->vm_next;
! mm->mmap_cache = vma;
! }
! }
! return vma;
! }
/* Look up the first VMA which intersects the interval start_addr..end_addr-1,
NULL if none. Assume start_addr < end_addr. */
--- 360,366 ----
}
/* Look up the first VMA which satisfies addr < vm_end, NULL if none. */
! extern struct vm_area_struct * find_vma(struct mm_struct * mm, unsigned long addr);
/* Look up the first VMA which intersects the interval start_addr..end_addr-1,
NULL if none. Assume start_addr < end_addr. */
*** linux-2.1.119/include/asm-i386/processor.h.bak Mon Aug 31 00:41:28 1998
--- linux-2.1.119/include/asm-i386/processor.h Sun Sep 6 16:11:11 1998
***************
*** 235,241 ****
};
#define INIT_MMAP \
! { &init_mm, 0, 0, PAGE_SHARED, VM_READ | VM_WRITE | VM_EXEC, NULL, &init_mm.mmap }
#define INIT_TSS { \
0,0, /* back_link, __blh */ \
--- 235,241 ----
};
#define INIT_MMAP \
! { &init_mm, 0, 0, NULL, PAGE_SHARED, VM_READ | VM_WRITE | VM_EXEC, 1, NULL, NULL }
#define INIT_TSS { \
0,0, /* back_link, __blh */ \
*** linux-2.1.119/include/asm-mips/processor.h.bak Mon Aug 31 00:39:58 1998
--- linux-2.1.119/include/asm-mips/processor.h Sun Sep 6 17:50:41 1998
***************
*** 116,123 ****
#endif /* !defined (__LANGUAGE_ASSEMBLY__) */
! #define INIT_MMAP { &init_mm, KSEG0, KSEG1, PAGE_SHARED, \
! VM_READ | VM_WRITE | VM_EXEC, NULL, &init_mm.mmap }
#define INIT_TSS { \
/* \
--- 116,123 ----
#endif /* !defined (__LANGUAGE_ASSEMBLY__) */
! #define INIT_MMAP { &init_mm, KSEG0, KSEG1, NULL, PAGE_SHARED, \
! VM_READ | VM_WRITE | VM_EXEC, 1, NULL, NULL }
#define INIT_TSS { \
/* \
*** linux-2.1.119/include/asm-alpha/processor.h.bak Mon Aug 31 00:41:27 1998
--- linux-2.1.119/include/asm-alpha/processor.h Sun Sep 6 17:49:46 1998
***************
*** 62,69 ****
long debugreg[8];
};
! #define INIT_MMAP { &init_mm, 0xfffffc0000000000, 0xfffffc0010000000, \
! PAGE_SHARED, VM_READ | VM_WRITE | VM_EXEC, NULL, &init_mm.mmap }
#define INIT_TSS { \
0, 0, 0, \
--- 62,69 ----
long debugreg[8];
};
! #define INIT_MMAP { &init_mm, 0xfffffc0000000000, 0xfffffc0010000000, NULL, \
! PAGE_SHARED, VM_READ | VM_WRITE | VM_EXEC, 1, NULL, NULL }
#define INIT_TSS { \
0, 0, 0, \
*** linux-2.1.119/include/asm-m68k/processor.h.bak Sat Jun 13 22:14:33 1998
--- linux-2.1.119/include/asm-m68k/processor.h Sun Sep 6 17:50:17 1998
***************
*** 45,51 ****
unsigned char fpstate[FPSTATESIZE]; /* floating point state */
};
! #define INIT_MMAP { &init_mm, 0, 0x40000000, __pgprot(_PAGE_PRESENT|_PAGE_ACCESSED), VM_READ | VM_WRITE | VM_EXEC, NULL, &init_mm.mmap }
#define INIT_TSS { \
sizeof(init_stack) + (unsigned long) init_stack, 0, \
--- 45,51 ----
unsigned char fpstate[FPSTATESIZE]; /* floating point state */
};
! #define INIT_MMAP { &init_mm, 0, 0x40000000, NULL, __pgprot(_PAGE_PRESENT|_PAGE_ACCESSED), VM_READ | VM_WRITE | VM_EXEC, 1, NULL, NULL }
#define INIT_TSS { \
sizeof(init_stack) + (unsigned long) init_stack, 0, \
*** linux-2.1.119/include/asm-sparc/processor.h.bak Mon Aug 31 00:40:03 1998
--- linux-2.1.119/include/asm-sparc/processor.h Sun Sep 6 17:52:12 1998
***************
*** 87,94 ****
#define SPARC_FLAG_KTHREAD 0x1 /* task is a kernel thread */
#define SPARC_FLAG_UNALIGNED 0x2 /* is allowed to do unaligned accesses */
! #define INIT_MMAP { &init_mm, (0), (0), \
! __pgprot(0x0) , VM_READ | VM_WRITE | VM_EXEC, NULL, &init_mm.mmap }
#define INIT_TSS { \
/* uwinmask, kregs, sig_address, sig_desc, ksp, kpc, kpsr, kwim */ \
--- 87,95 ----
#define SPARC_FLAG_KTHREAD 0x1 /* task is a kernel thread */
#define SPARC_FLAG_UNALIGNED 0x2 /* is allowed to do unaligned accesses */
! #define INIT_MMAP { &init_mm, (0), (0), NULL, \
! __pgprot(0x0) , VM_READ | VM_WRITE | VM_EXEC, \
! 1, NULL, NULL }
#define INIT_TSS { \
/* uwinmask, kregs, sig_address, sig_desc, ksp, kpc, kpsr, kwim */ \
*** linux-2.1.119/include/asm-ppc/processor.h.bak Mon Aug 31 00:40:00 1998
--- linux-2.1.119/include/asm-ppc/processor.h Sun Sep 6 17:51:30 1998
***************
*** 278,285 ****
* Note: the vm_start and vm_end fields here should *not*
* be in kernel space. (Could vm_end == vm_start perhaps?)
*/
! #define INIT_MMAP { &init_mm, 0, 0x1000, \
! PAGE_SHARED, VM_READ | VM_WRITE | VM_EXEC }
/*
* Return saved PC of a blocked thread. For now, this is the "user" PC
--- 278,286 ----
* Note: the vm_start and vm_end fields here should *not*
* be in kernel space. (Could vm_end == vm_start perhaps?)
*/
! #define INIT_MMAP { &init_mm, 0, 0x1000, NULL, \
! PAGE_SHARED, VM_READ | VM_WRITE | VM_EXEC, \
! 1, NULL, NULL }
/*
* Return saved PC of a blocked thread. For now, this is the "user" PC
*** linux-2.1.119/include/asm-sparc64/processor.h.bak Mon Aug 31 00:40:06 1998
--- linux-2.1.119/include/asm-sparc64/processor.h Sun Sep 6 17:53:01 1998
***************
*** 75,82 ****
#define SPARC_FLAG_32BIT 0x080 /* task is older 32-bit binary */
#define SPARC_FLAG_NEWCHILD 0x100 /* task is just-spawned child process */
! #define INIT_MMAP { &init_mm, 0xfffff80000000000, 0xfffff80001000000, \
! PAGE_SHARED , VM_READ | VM_WRITE | VM_EXEC, NULL, &init_mm.mmap }
#define INIT_TSS { \
/* ksp, wstate, cwp, flags, ctx, */ \
--- 75,83 ----
#define SPARC_FLAG_32BIT 0x080 /* task is older 32-bit binary */
#define SPARC_FLAG_NEWCHILD 0x100 /* task is just-spawned child process */
! #define INIT_MMAP { &init_mm, 0xfffff80000000000, 0xfffff80001000000, NULL, \
! PAGE_SHARED , VM_READ | VM_WRITE | VM_EXEC, \
! 1, NULL, NULL }
#define INIT_TSS { \
/* ksp, wstate, cwp, flags, ctx, */ \
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.rutgers.edu
Please read the FAQ at http://www.tux.org/lkml/faq.html