Index: sys/vm/vm_map.c
===================================================================
--- sys/vm/vm_map.c
+++ sys/vm/vm_map.c
@@ -796,13 +796,16 @@
 {
 
 	map->header.next = map->header.prev = &map->header;
+	map->header.left = map->header.right = NULL;
+	map->header.adj_free = max - min;
+	map->header.max_free = map->header.adj_free;
 	map->needs_wakeup = FALSE;
 	map->system_map = 0;
 	map->pmap = pmap;
 	map->min_offset = min;
 	map->max_offset = max;
 	map->flags = 0;
-	map->root = NULL;
+	map->root = &map->header;
 	map->timestamp = 0;
 	map->busy = 0;
 }
@@ -877,7 +880,7 @@
 }
 
 /*
- *	vm_map_entry_splay:
+ *	vm_map_splay:
  *
  *	The Sleator and Tarjan top-down splay algorithm with the
  *	following variation.  Max_free must be computed bottom-up, so
@@ -893,16 +896,17 @@
  *
  *	Returns: the new root.
  */
-static vm_map_entry_t
-vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t root)
+static void
+vm_map_splay(vm_offset_t addr, vm_map_t map, vm_map_entry_t *io)
 {
 	vm_map_entry_t llist, rlist;
 	vm_map_entry_t ltree, rtree;
-	vm_map_entry_t y;
+	vm_map_entry_t root, x, y;
 
-	/* Special case of empty tree. */
-	if (root == NULL)
-		return (root);
+	KASSERT(addr >= map->min_offset && addr < map->max_offset,
+	    ("vm_map_splay: addr %jx, offsets start %jx, end %jx",
+	    (uintmax_t)addr,
+	    (uintmax_t)map->min_offset, (uintmax_t)map->max_offset));
 
 	/*
 	 * Pass One: Splay down the tree until we find addr or a NULL
@@ -914,46 +918,116 @@
 	 */
 	llist = NULL;
 	rlist = NULL;
-	for (;;) {
-		/* root is never NULL in here. */
-		if (addr < root->start) {
-			y = root->left;
-			if (y == NULL)
-				break;
-			if (addr < y->start && y->left != NULL) {
-				/* Rotate right and put y on rlist. */
-				root->left = y->right;
-				y->right = root;
-				vm_map_entry_set_max_free(root);
+	root = map->root;
+	do {
+		x = root;
+		/* x is never NULL in here. */
+		if (addr >= x->end) {
+			y = x->right;
+			if (y != NULL && addr >= y->end) {
+				root = y->right;
+				/* Rotate left. */
+				x->right = y->left;
+				y->left = x;
+				vm_map_entry_set_max_free(x);
+				/* Put y on llist. */
+				y->right = llist;
+				llist = y;
+			} else if (y != NULL && addr < y->start) {
 				root = y->left;
+				/* Put y on rlist */
 				y->left = rlist;
 				rlist = y;
+				/* Put x on llist. */
+				x->right = llist;
+				llist = x;
 			} else {
-				/* Put root on rlist. */
-				root->left = rlist;
-				rlist = root;
 				root = y;
-			}
-		} else if (addr >= root->end) {
-			y = root->right;
-			if (y == NULL)
+				/* Put x on llist. */
+				x->right = llist;
+				llist = x;
 				break;
-			if (addr >= y->end && y->right != NULL) {
-				/* Rotate left and put y on llist. */
-				root->right = y->left;
-				y->left = root;
-				vm_map_entry_set_max_free(root);
+			}
+		} else if (addr < x->start) {
+			y = x->left;
+			if (y != NULL && addr >= y->end) {
 				root = y->right;
+				/* Put y on llist. */
 				y->right = llist;
 				llist = y;
+				/* Put x on rlist. */
+				x->left = rlist;
+				rlist = x;
+			} else if (y != NULL && addr < y->start) {
+				root = y->left;
+				/* Rotate right. */
+				x->left = y->right;
+				y->right = x;
+				vm_map_entry_set_max_free(x);
+				/* Put y on rlist. */
+				y->left = rlist;
+				rlist = y;
 			} else {
-				/* Put root on llist. */
-				root->right = llist;
-				llist = root;
 				root = y;
+				/* Put x on rlist. */
+				x->left = rlist;
+				rlist = x;
+				break;
 			}
 		} else
 			break;
+	} while (root != NULL);
+
+	if (io == NULL) {	/* Lookup only. */
+		if (root == NULL) {
+			/*
+			 * With no matching node found, recover the
+			 * greatest node in the left subtree and make
+			 * it the root.  There is such a node, since
+			 * map->header is in the tree and left of all
+			 * addresses.
+			 */
+			root = llist;
+			llist = root->right;
+			root->right = NULL;
+		}
+	} else if (*io == NULL && root != NULL) {
+		/*
+		 * To delete the found item from the tree, walk the
+		 * left spine of the found subtree, extending the left
+		 * spine of the new subtree, so that the predecessor
+		 * of the found node can be the new root.
+		 */
+		rtree = root->right;
+		root->right = NULL;
+		ltree = root->left;
+		root->left = NULL;
+		*io = root;
+		root = ltree;
+		for (;;) {
+			/* root is never NULL in here. */
+			y = root->right;
+			if (y == NULL)
+				break;
+			x = root;
+			root = y->right;
+			/* Rotate left. */
+			x->right = y->left;
+			y->left = x;
+			vm_map_entry_set_max_free(x);
+			if (root == NULL) {
+				root = y;
+				break;
+			}
+			/* put y on llist. */
+			y->right = llist;
+			llist = y;
+		}
+		root->right = rtree;
+	} else if (*io != NULL && root == NULL) {
+		/* Install the new item as tree root */
+		root = *io;
+		*io = NULL;
 	}
 
 	/*
@@ -985,7 +1059,7 @@
 	root->right = rtree;
 	vm_map_entry_set_max_free(root);
 
-	return (root);
+	map->root = root;
 }
 
 /*
@@ -1015,47 +1089,25 @@
 	entry->next = after_where->next;
 	entry->next->prev = entry;
 	after_where->next = entry;
-
-	if (after_where != &map->header) {
-		if (after_where != map->root)
-			vm_map_entry_splay(after_where->start, map->root);
-		entry->right = after_where->right;
-		entry->left = after_where;
-		after_where->right = NULL;
-		after_where->adj_free = entry->start - after_where->end;
-		vm_map_entry_set_max_free(after_where);
-	} else {
-		entry->right = map->root;
-		entry->left = NULL;
-	}
+	after_where->adj_free = entry->start - after_where->end;
 	entry->adj_free = entry->next->start - entry->end;
-	vm_map_entry_set_max_free(entry);
-	map->root = entry;
+	vm_map_splay(entry->start, map, &entry);
 }
 
 static void
 vm_map_entry_unlink(vm_map_t map,
 		    vm_map_entry_t entry)
 {
-	vm_map_entry_t next, prev, root;
+	vm_map_entry_t next, prev;
 
 	VM_MAP_ASSERT_LOCKED(map);
-	if (entry != map->root)
-		vm_map_entry_splay(entry->start, map->root);
-	if (entry->left == NULL)
-		root = entry->right;
-	else {
-		root = vm_map_entry_splay(entry->start, entry->left);
-		root->right = entry->right;
-		root->adj_free = entry->next->start - root->end;
-		vm_map_entry_set_max_free(root);
-	}
-	map->root = root;
-
 	prev = entry->prev;
 	next = entry->next;
 	next->prev = prev;
 	prev->next = next;
+	prev->adj_free = next->start - prev->end;
+	prev = NULL;
+	vm_map_splay(entry->start, map, &prev);
 	map->nentries--;
 	CTR3(KTR_VM, "vm_map_entry_unlink: map %p, nentries %d, entry %p", map,
 	    map->nentries, entry);
@@ -1081,7 +1133,7 @@
 	 * root and making the change there.
 	 */
 	if (entry != map->root)
-		map->root = vm_map_entry_splay(entry->start, map->root);
+		vm_map_splay(entry->start, map, NULL);
 
 	entry->adj_free = entry->next->start - entry->end;
 	vm_map_entry_set_max_free(entry);
@@ -1107,61 +1159,53 @@
 	boolean_t locked;
 
 	/*
+	 * If the address is out of range, fail immediately.
+	 */
+	if (address < map->min_offset || address >= map->max_offset) {
+		*entry = &map->header;
+		return (FALSE);
+	}
+
+	/*
 	 * If the map is empty, then the map entry immediately preceding
 	 * "address" is the map's header.
 	 */
 	cur = map->root;
-	if (cur == NULL)
-		*entry = &map->header;
-	else if (address >= cur->start && cur->end > address) {
+	if (address >= cur->start && cur->end > address) {
 		*entry = cur;
 		return (TRUE);
-	} else if ((locked = vm_map_locked(map)) ||
-	    sx_try_upgrade(&map->lock)) {
+	}
+	if ((locked = vm_map_locked(map)) || sx_try_upgrade(&map->lock)) {
 		/*
 		 * Splay requires a write lock on the map.  However, it only
 		 * restructures the binary search tree; it does not otherwise
 		 * change the map.  Thus, the map's timestamp need not change
 		 * on a temporary upgrade.
 		 */
-		map->root = cur = vm_map_entry_splay(address, cur);
+		vm_map_splay(address, map, NULL);
+		cur = map->root;
 		if (!locked)
 			sx_downgrade(&map->lock);
 
-		/*
-		 * If "address" is contained within a map entry, the new root
-		 * is that map entry.  Otherwise, the new root is a map entry
-		 * immediately before or after "address".
-		 */
-		if (address >= cur->start) {
-			*entry = cur;
-			if (cur->end > address)
-				return (TRUE);
-		} else
-			*entry = cur->prev;
+		*entry = cur;
+		if (cur->end > address)
+			return (TRUE);
 	} else
 		/*
 		 * Since the map is only locked for read access, perform a
 		 * standard binary search tree lookup for "address".
 		 */
-		for (;;) {
-			if (address < cur->start) {
-				if (cur->left == NULL) {
-					*entry = cur->prev;
-					break;
-				}
+		do {
+			if (cur->end <= address) {
+				*entry = cur;
+				cur = cur->right;
+			} else if (address < cur->start) {
 				cur = cur->left;
-			} else if (cur->end > address) {
+			} else {
 				*entry = cur;
 				return (TRUE);
-			} else {
-				if (cur->right == NULL) {
-					*entry = cur;
-					break;
-				}
-				cur = cur->right;
 			}
-		}
+		} while (cur != NULL);
 	return (FALSE);
 }
 
@@ -1403,27 +1447,12 @@
 	if (start + length > map->max_offset || start + length < start)
 		return (1);
 
-	/* Empty tree means wide open address space. */
-	if (map->root == NULL) {
-		*addr = start;
-		return (0);
-	}
-
-	/*
-	 * After splay, if start comes before root node, then there
-	 * must be a gap from start to the root.
-	 */
-	map->root = vm_map_entry_splay(start, map->root);
-	if (start + length <= map->root->start) {
-		*addr = start;
-		return (0);
-	}
-
 	/*
 	 * Root is the last node that might begin its gap before
 	 * start, and this is the last comparison where address
 	 * wrap might be a problem.
 	 */
+	vm_map_splay(start, map, NULL);
 	st = (start > map->root->end) ? start : map->root->end;
 	if (length <= map->root->end + map->root->adj_free - st) {
 		*addr = st;