use a red-black tree to find entries in the vm_map. augment the red-black

tree to find free space between entries.  speeds up memory allocation,
etc...

4 files changed, 427 insertions, 20 deletions

diff --git a/sys/uvm/uvm_extern.h b/sys/uvm/uvm_extern.h
index 39d6fcb6767..aafd01207ec 100644
--- a/sys/uvm/uvm_extern.h
+++ b/sys/uvm/uvm_extern.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm_extern.h,v 1.40 2001/12/19 08:58:07 art Exp $	*/
+/*	$OpenBSD: uvm_extern.h,v 1.41 2002/02/25 00:20:45 provos Exp $	*/
 /*	$NetBSD: uvm_extern.h,v 1.57 2001/03/09 01:02:12 chs Exp $	*/
 
 /*
@@ -373,6 +373,7 @@ 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 4c02265a654..0bf712b09ed 100644
--- a/sys/uvm/uvm_map.c
+++ b/sys/uvm/uvm_map.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm_map.c,v 1.38 2002/02/18 10:02:20 art Exp $	*/
+/*	$OpenBSD: uvm_map.c,v 1.39 2002/02/25 00:20:45 provos Exp $	*/
 /*	$NetBSD: uvm_map.c,v 1.86 2000/11/27 08:40:03 chs Exp $	*/
 
 /* 
@@ -83,6 +83,7 @@
 #include <sys/shm.h>
 #endif
 
+#define RB_AUGMENT(x) uvm_rb_augment(x)
 #define UVM_MAP
 #include <uvm/uvm.h>
 
@@ -90,7 +91,6 @@
 #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,6 +134,7 @@ vaddr_t uvm_maxkaddr;
 	(entry)->next = (after_where)->next; \
 	(entry)->prev->next = (entry); \
 	(entry)->next->prev = (entry); \
+	uvm_rb_insert(map, entry); \
 } while (0)
 
 /*
@@ -145,6 +146,7 @@ vaddr_t uvm_maxkaddr;
 	(map)->nentries--; \
 	(entry)->next->prev = (entry)->prev; \
 	(entry)->prev->next = (entry)->next; \
+	uvm_rb_remove(map, entry); \
 } while (0)
 
 /*
@@ -185,6 +187,164 @@ 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
  */
@@ -389,6 +549,8 @@ 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
@@ -402,6 +564,8 @@ 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) {
@@ -420,6 +584,8 @@ 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");
 }
 
 /*
@@ -440,6 +606,7 @@ 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
@@ -455,6 +622,8 @@ 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);
 
@@ -468,6 +637,7 @@ 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");
 }
 
 
@@ -522,6 +692,8 @@ 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
 	 */
@@ -644,8 +816,11 @@ 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);
@@ -717,6 +892,8 @@ 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);
@@ -738,6 +915,7 @@ 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);
 
@@ -777,12 +955,43 @@ 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);
 	}
 
 	/*
@@ -807,6 +1016,7 @@ 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);
@@ -814,6 +1024,40 @@ 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
@@ -838,6 +1082,8 @@ 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);
@@ -847,6 +1093,8 @@ 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
@@ -888,6 +1136,123 @@ 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.
@@ -908,8 +1273,7 @@ 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 ((flags & UVM_FLAG_FIXED) == 0 &&
-		    uoffset != UVM_UNKNOWN_OFFSET)
+		if (uoffset != UVM_UNKNOWN_OFFSET)
 			PMAP_PREFER(uoffset, &hint);
 #endif
 		if (align != 0) {
@@ -922,27 +1286,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);
-			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);
+			goto error;
 		}
 		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);
 }
 
 /*
@@ -974,6 +1338,8 @@ 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
 	 */
@@ -1119,6 +1485,8 @@ 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.  
@@ -1245,6 +1613,8 @@ 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
 	 */
@@ -1301,7 +1671,6 @@ uvm_map_replace(map, start, end, newents, nnewents)
 	 */
 
 	if (newents) {
-
 		last = newents->prev;		/* we expect this */
 
 		/* critical: flush stale hints out of map */
@@ -1311,10 +1680,25 @@ 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 */
@@ -1327,6 +1711,8 @@ 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.
 	 */
@@ -1372,6 +1758,9 @@ 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
@@ -1649,6 +2038,10 @@ 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);
 
 	/*
@@ -1660,6 +2053,10 @@ 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);
 }
@@ -2825,7 +3222,11 @@ 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 ad865ece22b..36e5707f1c9 100644
--- a/sys/uvm/uvm_map.h
+++ b/sys/uvm/uvm_map.h
@@ -1,4 +1,4 @@
-/*	$OpenBSD: uvm_map.h,v 1.21 2002/02/18 10:02:20 art Exp $	*/
+/*	$OpenBSD: uvm_map.h,v 1.22 2002/02/25 00:20:45 provos Exp $	*/
 /*	$NetBSD: uvm_map.h,v 1.24 2001/02/18 21:19:08 chs Exp $	*/
 
 /* 
@@ -139,6 +139,9 @@ 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 */
@@ -217,6 +220,7 @@ 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 54625e7fb4e..4556f48e6a8 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.12 2001/12/19 08:58:07 art Exp $	*/
+/*	$OpenBSD: uvm_map_i.h,v 1.13 2002/02/25 00:20:45 provos Exp $	*/
 /*	$NetBSD: uvm_map_i.h,v 1.18 2000/11/27 08:40:04 chs Exp $	*/
 
 /* 
@@ -114,6 +114,7 @@ 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;