back out red-black tree. they are very fast but alpha UVM is broken and

the tree triggers the bug, PMAP_PREFER case was broken also.

4 files changed, 20 insertions, 427 deletions

diff --git a/sys/uvm/uvm_extern.h b/sys/uvm/uvm_extern.h
index aafd01207ec..eb2f3358c1a 100644
--- a/sys/uvm/uvm_extern.h
+++ b/sys/uvm/uvm_extern.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm_extern.h,v 1.41 2002/02/25 00:20:45 provos Exp $	*/
+/*	$OpenBSD: uvm_extern.h,v 1.42 2002/02/25 05:38:50 provos Exp $	*/
 /*	$NetBSD: uvm_extern.h,v 1.57 2001/03/09 01:02:12 chs Exp $	*/
 
 /*
@@ -373,7 +373,6 @@ extern struct uvmexp uvmexp;
  */
 #include <sys/vmmeter.h>
 #include <sys/queue.h>
-#include <sys/tree.h>
 #include <uvm/uvm_param.h>
 #include <sys/lock.h>
 #include <uvm/uvm_page.h>
diff --git a/sys/uvm/uvm_map.c b/sys/uvm/uvm_map.c
index 0bf712b09ed..4400ae70d2e 100644
--- a/sys/uvm/uvm_map.c
+++ b/sys/uvm/uvm_map.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm_map.c,v 1.39 2002/02/25 00:20:45 provos Exp $	*/
+/*	$OpenBSD: uvm_map.c,v 1.40 2002/02/25 05:38:50 provos Exp $	*/
 /*	$NetBSD: uvm_map.c,v 1.86 2000/11/27 08:40:03 chs Exp $	*/
 
 /* 
@@ -83,7 +83,6 @@
 #include <sys/shm.h>
 #endif
 
-#define RB_AUGMENT(x) uvm_rb_augment(x)
 #define UVM_MAP
 #include <uvm/uvm.h>
 
@@ -91,6 +90,7 @@
 #include <uvm/uvm_ddb.h>
 #endif
 
+
 struct uvm_cnt uvm_map_call, map_backmerge, map_forwmerge;
 struct uvm_cnt uvm_mlk_call, uvm_mlk_hint;
 const char vmmapbsy[] = "vmmapbsy";
@@ -134,7 +134,6 @@ vaddr_t uvm_maxkaddr;
 	(entry)->next = (after_where)->next; \
 	(entry)->prev->next = (entry); \
 	(entry)->next->prev = (entry); \
-	uvm_rb_insert(map, entry); \
 } while (0)
 
 /*
@@ -146,7 +145,6 @@ vaddr_t uvm_maxkaddr;
 	(map)->nentries--; \
 	(entry)->next->prev = (entry)->prev; \
 	(entry)->prev->next = (entry)->next; \
-	uvm_rb_remove(map, entry); \
 } while (0)
 
 /*
@@ -187,164 +185,6 @@ static void		uvm_map_entry_unwire __P((vm_map_t, vm_map_entry_t));
 static void		uvm_map_reference_amap __P((vm_map_entry_t, int));
 static void		uvm_map_unreference_amap __P((vm_map_entry_t, int));
 
-int			uvm_map_spacefits __P((vm_map_t, vaddr_t *, vsize_t, vm_map_entry_t, voff_t, vsize_t));
-
-int _uvm_tree_sanity(vm_map_t map, char *name);
-static int		uvm_rb_subtree_space __P((vm_map_entry_t));
-
-static __inline int
-uvm_compare(vm_map_entry_t a, vm_map_entry_t b)
-{
-	if (a->start < b->start)
-		return (-1);
-	else if (a->start > b->start)
-		return (1);
-	
-	return (0);
-}
-
-
-static __inline void
-uvm_rb_augment(vm_map_entry_t entry)
-{
-	entry->space = uvm_rb_subtree_space(entry);
-}
-
-RB_PROTOTYPE(uvm_tree, vm_map_entry, rb_entry, uvm_compare);
-
-RB_GENERATE(uvm_tree, vm_map_entry, rb_entry, uvm_compare);
-
-static __inline int
-uvm_rb_space(vm_map_t map, vm_map_entry_t entry)
-{
-	vm_map_entry_t next;
-	vaddr_t space;
-
-	if ((next = entry->next) == &map->header)
-		space = map->max_offset - entry->end;
-	else {
-		KASSERT(next);
-		space = next->start - entry->end;
-	}
-	return (space);
-}
-		
-static int
-uvm_rb_subtree_space(vm_map_entry_t entry)
-{
-	vaddr_t space, tmp;
-
-	space = entry->ownspace;
-	if (RB_LEFT(entry, rb_entry)) {
-		tmp = RB_LEFT(entry, rb_entry)->space;
-		if (tmp > space)
-			space = tmp;
-	}
-
-	if (RB_RIGHT(entry, rb_entry)) {
-		tmp = RB_RIGHT(entry, rb_entry)->space;
-		if (tmp > space)
-			space = tmp;
-	}
-
-	return (space);
-}
-
-static __inline void
-uvm_rb_fixup(vm_map_t map, vm_map_entry_t entry)
-{
-	/* We need to traverse to the very top */
-	do {
-		entry->ownspace = uvm_rb_space(map, entry);
-		entry->space = uvm_rb_subtree_space(entry);
-	} while ((entry = RB_PARENT(entry, rb_entry)) != NULL);
-}
-
-static __inline void
-uvm_rb_insert(vm_map_t map, vm_map_entry_t entry)
-{
-	vaddr_t space = uvm_rb_space(map, entry);
-
-	entry->ownspace = entry->space = space;
-	RB_INSERT(uvm_tree, &(map)->rbhead, entry);
-	uvm_rb_fixup(map, entry);
-	if (entry->prev != &map->header)
-		uvm_rb_fixup(map, entry->prev);
-}
-
-static __inline void
-uvm_rb_remove(vm_map_t map, vm_map_entry_t entry)
-{
-	vm_map_entry_t parent;
-
-	parent = RB_PARENT(entry, rb_entry);
-	RB_REMOVE(uvm_tree, &(map)->rbhead, entry);
-	if (entry->prev != &map->header)
-		uvm_rb_fixup(map, entry->prev);
-	if (parent)
-		uvm_rb_fixup(map, parent);
-}
-
-#define uvm_tree_sanity(x,y)
-
-int
-_uvm_tree_sanity(vm_map_t map, char *name)
-{
-	vm_map_entry_t tmp, trtmp;
-	int n = 0, i = 1;
-
-	RB_FOREACH(tmp, uvm_tree, &map->rbhead) {
-		if (tmp->ownspace != uvm_rb_space(map, tmp)) {
-			printf("%s: %d/%d ownspace %x != %x %s\n",
-			    name, n + 1, map->nentries,
-			    tmp->ownspace, uvm_rb_space(map, tmp),
-			    tmp->next == &map->header ? "(last)" : "");
-			goto error;
-		}
-	}
-	trtmp = NULL;
-	RB_FOREACH(tmp, uvm_tree, &map->rbhead) {
-		if (tmp->space != uvm_rb_subtree_space(tmp)) {
-			printf("%s: space %d != %d\n",
-			    name, tmp->space, uvm_rb_subtree_space(tmp));
-			goto error;
-		}
-		if (trtmp != NULL && trtmp->start >= tmp->start) {
-			printf("%s: corrupt: %p >= %p\n",
-			    name, trtmp->start, tmp->start);
-			goto error;
-		}
-		n++;
-
-	    trtmp = tmp;
-	}
-
-	if (n != map->nentries) {
-		printf("%s: nentries: %d vs %d\n",
-		    name, n, map->nentries);
-		goto error;
-	}
-
-	for (tmp = map->header.next; tmp && tmp != &map->header;
-	    tmp = tmp->next, i++) {
-		trtmp = RB_FIND(uvm_tree, &map->rbhead, tmp);
-		if (trtmp != tmp) {
-			printf("%s: lookup: %d: %p - %p: %p\n",
-			    name, i, tmp, trtmp,
-			    RB_PARENT(tmp, rb_entry));
-			goto error;
-		}
-	}
-
-	return (0);
- error:
-#ifdef	DDB
-	/* handy breakpoint location for error case */
-	__asm(".globl treesanity_label ; treesanity_label:");
-#endif
-	return (-1);
-}
-
 /*
  * local inlines
  */
@@ -549,8 +389,6 @@ void uvm_map_clip_start(map, entry, start)
 
 	/* uvm_map_simplify_entry(map, entry); */ /* XXX */
 
-	uvm_tree_sanity(map, "clip_start entry");
-
 	/*
 	 * Split off the front portion.  note that we must insert the new
 	 * entry BEFORE this one, so that this entry has the specified
@@ -564,8 +402,6 @@ void uvm_map_clip_start(map, entry, start)
 	new_adj = start - new_entry->start;
 	if (entry->object.uvm_obj)
 		entry->offset += new_adj;	/* shift start over */
-
-	/* Does not change order for the RB tree */
 	entry->start = start;
 
 	if (new_entry->aref.ar_amap) {
@@ -584,8 +420,6 @@ void uvm_map_clip_start(map, entry, start)
 			entry->object.uvm_obj->pgops->pgo_reference(
 			    entry->object.uvm_obj);
 	}
-
-	uvm_tree_sanity(map, "clip_start leave");
 }
 
 /*
@@ -606,7 +440,6 @@ uvm_map_clip_end(map, entry, end)
 	vm_map_entry_t	new_entry;
 	vaddr_t new_adj; /* #bytes we move start forward */
 
-	uvm_tree_sanity(map, "clip_end entry");
 	/*
 	 *	Create a new entry and insert it
 	 *	AFTER the specified entry
@@ -622,8 +455,6 @@ uvm_map_clip_end(map, entry, end)
 
 	if (entry->aref.ar_amap)
 		amap_splitref(&entry->aref, &new_entry->aref, new_adj);
-	
-	uvm_rb_fixup(map, entry);
 
 	uvm_map_entry_link(map, entry, new_entry);
 
@@ -637,7 +468,6 @@ uvm_map_clip_end(map, entry, end)
 			entry->object.uvm_obj->pgops->pgo_reference(
 			    entry->object.uvm_obj);
 	}
-	uvm_tree_sanity(map, "clip_end leave");
 }
 
 
@@ -692,8 +522,6 @@ uvm_map(map, startp, size, uobj, uoffset, align, flags)
 	    map, *startp, size, flags);
 	UVMHIST_LOG(maphist, "  uobj/offset 0x%x/%d", uobj, uoffset,0,0);
 
-	uvm_tree_sanity(map, "map entry");
-
 	/*
 	 * step 0: sanity check of protection code
 	 */
@@ -816,11 +644,8 @@ uvm_map(map, startp, size, uobj, uoffset, align, flags)
 		}
 
 		prev_entry->end += size;
-		uvm_rb_fixup(map, prev_entry);
 		map->size += size;
 
-		uvm_tree_sanity(map, "map leave 2");
-
 		UVMHIST_LOG(maphist,"<- done (via backmerge)!", 0, 0, 0, 0);
 		vm_map_unlock(map);
 		return (KERN_SUCCESS);
@@ -892,8 +717,6 @@ step3:
 	    (prev_entry->end >= new_entry->start))
 		map->first_free = new_entry;
 
-	uvm_tree_sanity(map, "map leave");
-
 	UVMHIST_LOG(maphist,"<- done!", 0, 0, 0, 0);
 	vm_map_unlock(map);
 	return(KERN_SUCCESS);
@@ -915,7 +738,6 @@ uvm_map_lookup_entry(map, address, entry)
 {
 	vm_map_entry_t		cur;
 	vm_map_entry_t		last;
-	int			use_tree = 0;
 	UVMHIST_FUNC("uvm_map_lookup_entry");
 	UVMHIST_CALLED(maphist);
 
@@ -955,43 +777,12 @@ uvm_map_lookup_entry(map, address, entry)
 			    cur, 0, 0, 0);
 			return (TRUE);
 		}
-
-		if (map->nentries > 30)
-			use_tree = 1;
 	} else {
 	    	/*
 		 * go from start to hint, *inclusively*
 		 */
 		last = cur->next;
 		cur = map->header.next;
-		use_tree = 1;
-	}
-
-	uvm_tree_sanity(map, __FUNCTION__);
-
-	if (use_tree) {
-		vm_map_entry_t prev = &map->header;
-		cur = RB_ROOT(&map->rbhead);
-
-		/*
-		 * Simple lookup in the tree.  Happens when the hint is
-		 * invalid, or nentries reach a threshold.
-		 */
-		while (cur) {
-			if (address >= cur->start) {
-				if (address < cur->end) {
-					*entry = cur;
-					SAVE_HINT(map, map->hint, cur);
-					return (TRUE);
-				}
-				prev = cur;
-				cur = RB_RIGHT(cur, rb_entry);
-			} else
-				cur = RB_LEFT(cur, rb_entry);
-		}
-		*entry = prev;
-		UVMHIST_LOG(maphist,"<- failed!",0,0,0,0);
-		return (FALSE);
 	}
 
 	/*
@@ -1016,7 +807,6 @@ uvm_map_lookup_entry(map, address, entry)
 		}
 		cur = cur->next;
 	}
-
 	*entry = cur->prev;
 	SAVE_HINT(map, map->hint, *entry);
 	UVMHIST_LOG(maphist,"<- failed!",0,0,0,0);
@@ -1024,40 +814,6 @@ uvm_map_lookup_entry(map, address, entry)
 }
 
 /*
- * Checks if address pointed to be phint fits into the empty
- * space before the vm_map_entry after.  Takes aligment and
- * offset into consideration.
- */
-
-int
-uvm_map_spacefits(vm_map_t map, vaddr_t *phint, vsize_t length,
-    vm_map_entry_t after, voff_t uoffset, vsize_t align)
-{
-	vaddr_t hint = *phint;
-	vaddr_t end;
-
-#ifdef PMAP_PREFER
-	/*
-	 * push hint forward as needed to avoid VAC alias problems.
-	 * we only do this if a valid offset is specified.
-	 */
-	if (uoffset != UVM_UNKNOWN_OFFSET)
-		PMAP_PREFER(uoffset, &hint);
-#endif
-	if (align != 0)
-		if ((hint & (align - 1)) != 0)
-			hint = roundup(hint, align);
-	end = hint + length;
-	if (end > map->max_offset || end < hint)
-		return (FALSE);
-	if (after != NULL && after != &map->header && after->start < end)
-		return (FALSE);
-	
-	*phint = hint;
-	return (TRUE);
-}
-
-/*
  * uvm_map_findspace: find "length" sized space in "map".
  *
  * => "hint" is a hint about where we want it, unless FINDSPACE_FIXED is
@@ -1082,8 +838,6 @@ uvm_map_findspace(map, hint, length, result, uobj, uoffset, align, flags)
 	int flags;
 {
 	vm_map_entry_t entry, next, tmp;
-	vm_map_entry_t child, prev = NULL;
-
 	vaddr_t end, orig_hint;
 	UVMHIST_FUNC("uvm_map_findspace");
 	UVMHIST_CALLED(maphist);
@@ -1093,8 +847,6 @@ uvm_map_findspace(map, hint, length, result, uobj, uoffset, align, flags)
 	KASSERT((align & (align - 1)) == 0);
 	KASSERT((flags & UVM_FLAG_FIXED) == 0 || align == 0);
 
-	uvm_tree_sanity(map, "map_findspace entry");
-
 	/*
 	 * remember the original hint.  if we are aligning, then we
 	 * may have to try again with no alignment constraint if
@@ -1136,123 +888,6 @@ uvm_map_findspace(map, hint, length, result, uobj, uoffset, align, flags)
 		entry = tmp;
 	}
 
-	if (flags & UVM_FLAG_FIXED) {
-#ifdef PMAP_PREFER
-		/*
-		 * push hint forward as needed to avoid VAC alias problems.
-		 * we only do this if a valid offset is specified.
-		 */
-		if (uoffset != UVM_UNKNOWN_OFFSET)
-			PMAP_PREFER(uoffset, &hint);
-#endif
-		if (align != 0) {
-			if ((hint & (align - 1)) != 0)
-				hint = roundup(hint, align);
-			/*
-			 * XXX Should we PMAP_PREFER() here again?
-			 */
-		}
-		end = hint + length;
-		if (end > map->max_offset || end < hint) {
-			UVMHIST_LOG(maphist,"<- failed (off end)", 0,0,0,0);
-			goto error;
-		}
-		next = entry->next;
-		if (next == &map->header || next->start >= end)
-			goto found;
-		UVMHIST_LOG(maphist,"<- fixed mapping failed", 0,0,0,0);
-		return(NULL); /* only one shot at it ... */
-	}
-
-	/* Try to find the space in the red-black tree */
-
-	/* Check slot before any entry */
-	tmp = map->header.next;
-	if (uvm_map_spacefits(map, &hint, length, tmp, uoffset, align)) {
-		entry = map->first_free;
-		goto found;
-	}
-	
-	/* If there is not enough space in the whole tree, we fail */
-	tmp = RB_ROOT(&map->rbhead);
-	if (tmp == NULL || tmp->space < length)
-		goto error;
-
-	/* Find an entry close to hint that has enough space */
-	for (; tmp;) {
-		if (tmp->start > hint &&
-		    (prev == NULL || tmp->start < prev->start)) {
-			if (tmp->ownspace >= length)
-				prev = tmp;
-			else if ((child = RB_RIGHT(tmp, rb_entry)) != NULL &&
-			    child->space >= length)
-				prev = tmp;
-		}
-		if (tmp->start < hint)
-			child = RB_RIGHT(tmp, rb_entry);
-		else if (tmp->start > hint)
-			child = RB_LEFT(tmp, rb_entry);
-		else {
-			if (tmp->ownspace >= length)
-				break;
-			child = RB_RIGHT(tmp, rb_entry);
-		}
-		if (child == NULL || child->space < length)
-			break;
-		tmp = child;
-	}
-	
-	if (tmp != NULL) {
-		/* 
-		 * Check if the entry that we found satifies the
-		 * space requirement
-		 */
-		if (hint < tmp->end)
-			hint = tmp->end;
-		if (uvm_map_spacefits(map, &hint, length, tmp->next, uoffset,
-			align)) {
-			entry = tmp;
-			hint = hint;
-			goto found;
-		}
-	}
-	if (prev == NULL)
-		goto error;
-	
-	hint = prev->end;
-	if (uvm_map_spacefits(map, &hint, length, prev->next, uoffset,
-		align)) {
-		entry = prev;
-		goto found;
-	}
-	
-	if ((tmp = RB_RIGHT(prev, rb_entry)) == NULL ||
-	    tmp->space < length)
-		goto error;
-	
-	for (;;) {
-		KASSERT(tmp && tmp->space >= length);
-		child = RB_LEFT(tmp, rb_entry);
-		if (child && child->space >= length) {
-			tmp = child;
-			continue;
-		}
-		if (tmp->ownspace >= length)
-			break;
-		tmp = RB_RIGHT(tmp, rb_entry);
-	}
-	
-	hint = tmp->end;
-	if (uvm_map_spacefits(map, &hint, length, tmp->next, uoffset, align)) {
-		entry = tmp;
-		goto found;
-	}
-
-	/* 
-	 * The tree fails to find an entry because of offset or alignment
-	 * restrictions.  Search the list instead.
-	 */
-
 	/*
 	 * Look through the rest of the map, trying to fit a new region in
 	 * the gap between existing regions, or after the very last region.
@@ -1273,7 +908,8 @@ uvm_map_findspace(map, hint, length, result, uobj, uoffset, align, flags)
 		 * push hint forward as needed to avoid VAC alias problems.
 		 * we only do this if a valid offset is specified.
 		 */
-		if (uoffset != UVM_UNKNOWN_OFFSET)
+		if ((flags & UVM_FLAG_FIXED) == 0 &&
+		    uoffset != UVM_UNKNOWN_OFFSET)
 			PMAP_PREFER(uoffset, &hint);
 #endif
 		if (align != 0) {
@@ -1286,27 +922,27 @@ uvm_map_findspace(map, hint, length, result, uobj, uoffset, align, flags)
 		end = hint + length;
 		if (end > map->max_offset || end < hint) {
 			UVMHIST_LOG(maphist,"<- failed (off end)", 0,0,0,0);
-			goto error;
+			if (align != 0) {
+				UVMHIST_LOG(maphist,
+				    "calling recursively, no align",
+				    0,0,0,0);
+				return (uvm_map_findspace(map, orig_hint,
+				    length, result, uobj, uoffset, 0, flags));
+			}
+			return (NULL);
 		}
 		next = entry->next;
 		if (next == &map->header || next->start >= end)
 			break;
+		if (flags & UVM_FLAG_FIXED) {
+			UVMHIST_LOG(maphist,"<- fixed mapping failed", 0,0,0,0);
+			return(NULL); /* only one shot at it ... */
+		}
 	}
- found:
 	SAVE_HINT(map, map->hint, entry);
 	*result = hint;
 	UVMHIST_LOG(maphist,"<- got it!  (result=0x%x)", hint, 0,0,0);
 	return (entry);
-
- error:
-	if (align != 0) {
-		UVMHIST_LOG(maphist,
-		    "calling recursively, no align",
-		    0,0,0,0);
-		return (uvm_map_findspace(map, orig_hint,
-			    length, result, uobj, uoffset, 0, flags));
-			}
-	return (NULL);
 }
 
 /*
@@ -1338,8 +974,6 @@ uvm_unmap_remove(map, start, end, entry_list)
 
 	VM_MAP_RANGE_CHECK(map, start, end);
 
-	uvm_tree_sanity(map, "unmap_remove entry");
-
 	/*
 	 * find first entry
 	 */
@@ -1485,8 +1119,6 @@ uvm_unmap_remove(map, start, end, entry_list)
 		entry = next;		/* next entry, please */
 	}
 
-	uvm_tree_sanity(map, "unmap_remove leave");
-
 	/*
 	 * now we've cleaned up the map and are ready for the caller to drop
 	 * references to the mapped objects.  
@@ -1613,8 +1245,6 @@ uvm_map_replace(map, start, end, newents, nnewents)
 {
 	vm_map_entry_t oldent, last;
 
-	uvm_tree_sanity(map, "map_replace entry");
-
 	/*
 	 * first find the blank map entry at the specified address
 	 */
@@ -1671,6 +1301,7 @@ uvm_map_replace(map, start, end, newents, nnewents)
 	 */
 
 	if (newents) {
+
 		last = newents->prev;		/* we expect this */
 
 		/* critical: flush stale hints out of map */
@@ -1680,25 +1311,10 @@ uvm_map_replace(map, start, end, newents, nnewents)
 
 		last->next = oldent->next;
 		last->next->prev = last;
-
-		/* Fix RB tree */
-		uvm_rb_remove(map, oldent);
-
 		newents->prev = oldent->prev;
 		newents->prev->next = newents;
 		map->nentries = map->nentries + (nnewents - 1);
 
-		/* Fixup the RB tree */
-		{
-			int i;
-			vm_map_entry_t tmp;
-
-			tmp = newents;
-			for (i = 0; i < nnewents && tmp; i++) {
-				uvm_rb_insert(map, tmp);
-				tmp = tmp->next;
-			}
-		}
 	} else {
 
 		/* critical: flush stale hints out of map */
@@ -1711,8 +1327,6 @@ uvm_map_replace(map, start, end, newents, nnewents)
 	}
 
 
-	uvm_tree_sanity(map, "map_replace leave");
-
 	/*
 	 * now we can free the old blank entry, unlock the map and return.
 	 */
@@ -1758,9 +1372,6 @@ uvm_map_extract(srcmap, start, len, dstmap, dstaddrp, flags)
 	    len,0);
 	UVMHIST_LOG(maphist," ...,dstmap=0x%x, flags=0x%x)", dstmap,flags,0,0);
 
-	uvm_tree_sanity(srcmap, "map_extract src enter");
-	uvm_tree_sanity(dstmap, "map_extract dst enter");
-
 	/*
 	 * step 0: sanity check: start must be on a page boundary, length
 	 * must be page sized.  can't ask for CONTIG/QREF if you asked for
@@ -2038,10 +1649,6 @@ uvm_map_extract(srcmap, start, len, dstmap, dstaddrp, flags)
 			goto bad2;
 		}
 	}
-
-	uvm_tree_sanity(srcmap, "map_extract src leave");
-	uvm_tree_sanity(dstmap, "map_extract dst leave");
-
 	return(0);
 
 	/*
@@ -2053,10 +1660,6 @@ bad2:			/* src already unlocked */
 	if (chain)
 		uvm_unmap_detach(chain,
 		    (flags & UVM_EXTRACT_QREF) ? AMAP_REFALL : 0);
-
-	uvm_tree_sanity(srcmap, "map_extract src err leave");
-	uvm_tree_sanity(dstmap, "map_extract dst err leave");
-
 	uvm_unmap(dstmap, dstaddr, dstaddr+len);   /* ??? */
 	return(error);
 }
@@ -3222,11 +2825,7 @@ uvmspace_exec(p, start, end)
 		 */
 		vm_map_lock(map);
 		map->min_offset = start;
-		uvm_tree_sanity(map, "resize enter");
 		map->max_offset = end;
-		if (map->header.prev != &map->header)
-			uvm_rb_fixup(map, map->header.prev);
-		uvm_tree_sanity(map, "resize leave");
 		vm_map_unlock(map);
 	
 
diff --git a/sys/uvm/uvm_map.h b/sys/uvm/uvm_map.h
index 36e5707f1c9..1fd0c00f196 100644
--- a/sys/uvm/uvm_map.h
+++ b/sys/uvm/uvm_map.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm_map.h,v 1.22 2002/02/25 00:20:45 provos Exp $	*/
+/*	$OpenBSD: uvm_map.h,v 1.23 2002/02/25 05:38:50 provos Exp $	*/
 /*	$NetBSD: uvm_map.h,v 1.24 2001/02/18 21:19:08 chs Exp $	*/
 
 /* 
@@ -139,9 +139,6 @@ union vm_map_object {
  * Also included is control information for virtual copy operations.
  */
 struct vm_map_entry {
-	RB_ENTRY(vm_map_entry)	rb_entry;	/* tree information */
-	vaddr_t			ownspace;	/* free space after */
-	vaddr_t			space;		/* space in subtree */
 	struct vm_map_entry	*prev;		/* previous entry */
 	struct vm_map_entry	*next;		/* next entry */
 	vaddr_t			start;		/* start address */
@@ -220,7 +217,6 @@ struct vm_map_entry {
 struct vm_map {
 	struct pmap *		pmap;		/* Physical map */
 	lock_data_t		lock;		/* Lock for map data */
-	RB_HEAD(uvm_tree, vm_map_entry) rbhead;	/* Tree for entries */
 	struct vm_map_entry	header;		/* List of entries */
 	int			nentries;	/* Number of entries */
 	vsize_t			size;		/* virtual size */
diff --git a/sys/uvm/uvm_map_i.h b/sys/uvm/uvm_map_i.h
index 4556f48e6a8..cb171708215 100644
--- a/sys/uvm/uvm_map_i.h
+++ b/sys/uvm/uvm_map_i.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm_map_i.h,v 1.13 2002/02/25 00:20:45 provos Exp $	*/
+/*	$OpenBSD: uvm_map_i.h,v 1.14 2002/02/25 05:38:50 provos Exp $	*/
 /*	$NetBSD: uvm_map_i.h,v 1.18 2000/11/27 08:40:04 chs Exp $	*/
 
 /* 
@@ -114,7 +114,6 @@ uvm_map_setup(map, min, max, flags)
 	int flags;
 {
 
-	RB_INIT(&map->rbhead);
 	map->header.next = map->header.prev = &map->header;
 	map->nentries = 0;
 	map->size = 0;