lkml.org 
[lkml]   [1998]   [Sep]   [3]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
Date
Subject[PATCH] Re: 2.1.xxx makes Electric Fence 22x slower

Here is a patch which puts back the AVL trees for fast VMA lookup.

Since the fuzzy hashing scheme has given a good speedup on VMA intensive
applications, but not been able to get close to the 2.0.x performance,
here is the 2.0.x AVL code, adapted to 2.1.119.

Robert, what timings to you get for the Electric Fence app with this patch?

Btw, I kept the "last find_vma result" cache in. It has a surprisingly
good cache hit rate: about 35% on average. More precisely, the rate is
about 50% during boot process (lots of small statically linked
executables), about 35% during normal use, and drops to about 25% when
using a VMA intensive application.

Bruno


*** linux-2.1.119/kernel/fork.c.bak Mon Aug 31 00:43:29 1998
--- linux-2.1.119/kernel/fork.c Wed Sep 2 12:13:33 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,250 ----
* 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;
+ 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.
--- 273,279 ----
* 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 Thu Sep 3 01:48:38 1998
***************
*** 356,361 ****
--- 356,363 ----
}
}

+ #include "mmap_avl.c"
+
/* 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)
--- 440,446 ----
int do_munmap(unsigned long addr, size_t len)
{
struct mm_struct * mm;
! struct vm_area_struct *mpnt, *prev, *next, **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;

/*
--- 455,473 ----
* on the list. If nothing is put on, nothing is affected.
*/
mm = current->mm;
! mpnt = find_vma(mm, addr);
if (!mpnt)
return 0;
+ avl_neighbours(mpnt, mm->mmap_avl, &prev, &next);
+ /* we have prev->vm_next == mpnt && mpnt->vm_next = next */
+ /* and 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,
--- 478,490 ----
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;
! 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;
--- 542,564 ----
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) {
--- 593,624 ----
*/
void insert_vm_struct(struct mm_struct *mm, struct vm_area_struct *vmp)
{
struct file * file;

! #if 0 /* equivalent, but slow */
! struct vm_area_struct **pprev = &mm->mmap;

/* Find where to link it in. */
while(*pprev && (*pprev)->vm_start <= vmp->vm_start)
pprev = &(*pprev)->vm_next;

/* Insert it. */
! vmp->vm_next = *pprev;
*pprev = vmp;
! #else
! struct vm_area_struct *prev, *next;
!
! avl_insert_neighbours(vmp, &mm->mmap_avl, &prev, &next);
! if ((prev ? prev->vm_next : mm->mmap) != next)
! printk("insert_vm_struct: tree inconsistent with list\n");
! if (prev)
! prev->vm_next = vmp;
! else
! mm->mmap = vmp;
! vmp->vm_next = next;
! #endif
!
! mm->map_count++;

file = vmp->vm_file;
if (file) {
***************
*** 623,640 ****
{
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;
--- 646,658 ----
{
struct vm_area_struct *prev, *mpnt, *next;

! mpnt = find_vma(mm, start_addr);
if (!mpnt)
return;

! avl_neighbours(mpnt, mm->mmap_avl, &prev, &next);
! /* we have prev->vm_next == mpnt && mpnt->vm_next = next */

if (!prev) {
prev = mpnt;
mpnt = next;
***************
*** 644,649 ****
--- 662,670 ----
* start_addr < mpnt->vm_end && prev->vm_start < end_addr
*/
for ( ; mpnt && prev->vm_start < end_addr ; prev = mpnt, mpnt = next) {
+ #if 0
+ printk("looping in merge_segments, mpnt=0x%lX\n", (unsigned long) mpnt);
+ #endif
next = mpnt->vm_next;

/* To share, we must have the same file, operations.. */
***************
*** 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;
--- 689,697 ----
* big segment can possibly merge with the next one.
* The old unused mpnt is freed.
*/
! 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 Wed Sep 2 12:22:10 1998
***************
*** 0 ****
--- 1,368 ----
+ /*
+ * 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.
+ */
+
+ /* 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");
+ }
+
+ /*
+ * 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;
+ 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;
+ }
+ *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 Wed Sep 2 22:41:54 1998
***************
*** 158,164 ****
#define MAX_MAP_COUNT (65536)

struct mm_struct {
! struct vm_area_struct *mmap, *mmap_cache;
pgd_t * pgd;
atomic_t count;
int map_count;
--- 158,164 ----
#define MAX_MAP_COUNT (65536)

struct mm_struct {
! struct vm_area_struct *mmap, *mmap_avl, *mmap_cache;
pgd_t * pgd;
atomic_t count;
int map_count;
***************
*** 178,184 ****
};

#define INIT_MM { \
! &init_mmap, NULL, swapper_pg_dir, \
ATOMIC_INIT(1), 1, \
MUTEX, \
0, \
--- 178,185 ----
};

#define INIT_MM { \
! &init_mmap, &init_mmap, 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 Thu Sep 3 01:48:22 1998
***************
*** 37,44 ****
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.
--- 37,50 ----
unsigned long vm_end;
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;
+
+ /* linked list of VM areas per task, sorted by address */
struct vm_area_struct *vm_next;

/* For areas with inode, the list inode->i_mmap, for shm areas,
* the list of attaches, otherwise unused.
***************
*** 294,299 ****
--- 300,306 ----
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);

***************
*** 351,356 ****
--- 358,365 ----
return 0;
}

+ #define vm_avl_empty (struct vm_area_struct *) NULL
+
/* 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)
{
***************
*** 358,369 ****

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;
--- 367,390 ----

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)) {
! /* 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;
*** 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 Wed Sep 2 22:40:06 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, PAGE_SHARED, VM_READ | VM_WRITE | VM_EXEC, 1, NULL, NULL, NULL }

#define INIT_TSS { \
0,0, /* back_link, __blh */ \

-
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.altern.org/andrebalsa/doc/lkml-faq.html

\
 
 \ /
  Last update: 2005-03-22 13:44    [W:0.077 / U:0.680 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site