lkml.org 
[lkml]   [1998]   [Sep]   [7]   [last100]   RSS Feed
Views: [more markup]  [less markup]  [headers]  [forward] 
 
Messages in this thread
/
FromBruno Haible <>
DateMon, 7 Sep 1998 12:39:00 +0200 (MET DST)
Subject[PATCH] Re: 2.1.xxx makes Electric Fence 22x slower
Here is a new AVL patch. It uses normal linked lists in the normal case,
and switches to AVL when the number of VMAs exceeds a certain threshold:
32 VMAs. It thus combines the good timings of plain 2.1.119 with the
guaranteed worst-case O(log n) scalability of the AVL trees.

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

\
 
 \ /
  Last update: 2005-03-22 12:44    [from the cache]
©2003-2008