Index: sys/vm/vm_map.h
===================================================================
--- sys/vm/vm_map.h
+++ sys/vm/vm_map.h
@@ -99,10 +99,8 @@
  *	Also included is control information for virtual copy operations.
  */
 struct vm_map_entry {
-	struct vm_map_entry *prev;	/* previous entry */
-	struct vm_map_entry *next;	/* next entry */
-	struct vm_map_entry *left;	/* left child in binary search tree */
-	struct vm_map_entry *right;	/* right child in binary search tree */
+	struct vm_map_entry *left;	/* left child or previous entry */
+	struct vm_map_entry *right;	/* right child or next entry */
 	vm_offset_t start;		/* start address */
 	vm_offset_t end;		/* end address */
 	vm_offset_t next_read;		/* vaddr of the next sequential read */
@@ -424,14 +422,21 @@
 vm_map_entry_first(vm_map_t map)
 {
 
-	return (map->header.next);
+	return (map->header.right);
 }
 
 static inline vm_map_entry_t
 vm_map_entry_succ(vm_map_entry_t entry)
 {
+	vm_map_entry_t after;
 
-	return (entry->next);
+	after = entry->right;
+	if (after->left->start > entry->start) {
+		do
+			after = after->left;
+		while (after->left != entry);
+	}
+	return (after);
 }
 
 #define VM_MAP_ENTRY_FOREACH(it, map)		\
Index: sys/vm/vm_map.c
===================================================================
--- sys/vm/vm_map.c
+++ sys/vm/vm_map.c
@@ -885,7 +885,6 @@
 _vm_map_init(vm_map_t map, pmap_t pmap, vm_offset_t min, vm_offset_t max)
 {
 
-	map->header.next = map->header.prev = &map->header;
 	map->header.eflags = MAP_ENTRY_HEADER;
 	map->needs_wakeup = FALSE;
 	map->system_map = 0;
@@ -893,6 +892,7 @@
 	map->header.end = min;
 	map->header.start = max;
 	map->flags = 0;
+	map->header.left = map->header.right = &map->header;
 	map->root = NULL;
 	map->timestamp = 0;
 	map->busy = 0;
@@ -955,6 +955,12 @@
 	    (behavior & MAP_ENTRY_BEHAV_MASK);
 }
 
+static inline vm_size_t
+vm_size_max(vm_size_t a, vm_size_t b)
+{
+	return (a > b) ? a : b;
+}
+
 /*
  *	vm_map_entry_max_free_{left,right}:
  *
@@ -966,7 +972,7 @@
 vm_map_entry_max_free_left(vm_map_entry_t root, vm_map_entry_t left_ancestor)
 {
 
-	return (root->left != NULL ?
+	return (root->left != left_ancestor ?
 	    root->left->max_free : root->start - left_ancestor->end);
 }
 
@@ -974,7 +980,7 @@
 vm_map_entry_max_free_right(vm_map_entry_t root, vm_map_entry_t right_ancestor)
 {
 
-	return (root->right != NULL ?
+	return (root->right != right_ancestor ?
 	    root->right->max_free : right_ancestor->start - root->end);
 }
 
@@ -987,13 +993,20 @@
 static inline vm_map_entry_t
 vm_map_entry_pred(vm_map_entry_t entry)
 {
+	vm_map_entry_t prior;
 
-	return (entry->prev);
+	prior = entry->left;
+	if (prior->right->start < entry->start) {
+		do
+			prior = prior->right;
+		while (prior->right != entry);
+	}
+	return (prior);
 }
 
 /* vm_map_entry_succ is defined in vm_map.h. */
 
-#define SPLAY_LEFT_STEP(root, y, rlist, test) do {			\
+#define SPLAY_LEFT_STEP(root, y, llist, rlist, found, test) do {	\
 	vm_size_t max_free;						\
 									\
 	/*								\
@@ -1005,14 +1018,17 @@
 	max_free = root->max_free;					\
 	KASSERT(max_free >= vm_map_entry_max_free_right(root, rlist),	\
 	    ("%s: max_free invariant fails", __func__));		\
-	if (y == NULL ? max_free > 0 : max_free - 1 < y->max_free)	\
+	if (y == llist ? max_free > 0 : max_free - 1 < y->max_free)	\
 		max_free = vm_map_entry_max_free_right(root, rlist);	\
-	if (y != NULL && (test)) {					\
+	if (y != llist && (test)) {					\
 		/* Rotate right and make y root. */			\
-		root->left = y->right;					\
-		y->right = root;					\
+		if (y->right != root) {					\
+			root->left = y->right;				\
+			y->right = root;				\
+		}							\
 		if (max_free < y->max_free)				\
-			root->max_free = max_free = MAX(max_free,	\
+			root->max_free = max_free =			\
+			    vm_size_max(max_free,			\
 			    vm_map_entry_max_free_left(root, y));	\
 		root = y;						\
 		y = root->left;						\
@@ -1024,9 +1040,10 @@
 	root->left = rlist;						\
 	rlist = root;							\
 	root = y;							\
+	found = root != llist;						\
 } while (0)
 
-#define SPLAY_RIGHT_STEP(root, y, llist, test) do {			\
+#define SPLAY_RIGHT_STEP(root, y, llist, rlist, found, test) do {	\
 	vm_size_t max_free;						\
 									\
 	/*								\
@@ -1038,14 +1055,17 @@
 	max_free = root->max_free;					\
 	KASSERT(max_free >= vm_map_entry_max_free_left(root, llist),	\
 	    ("%s: max_free invariant fails", __func__));		\
-	if (y == NULL ? max_free > 0 : max_free - 1 < y->max_free)	\
+	if (y == rlist ? max_free > 0 : max_free - 1 < y->max_free)	\
 		max_free = vm_map_entry_max_free_left(root, llist);	\
-	if (y != NULL && (test)) {					\
+	if (y != rlist && (test)) {					\
 		/* Rotate left and make y root. */			\
-		root->right = y->left;					\
-		y->left = root;						\
+		if (y->left != root) {					\
+			root->right = y->left;				\
+			y->left = root;					\
+		}							\
 		if (max_free < y->max_free)				\
-			root->max_free = max_free = MAX(max_free,	\
+			root->max_free = max_free =			\
+			    vm_size_max(max_free,			\
 			    vm_map_entry_max_free_right(root, y));	\
 		root = y;						\
 		y = root->right;					\
@@ -1057,67 +1077,65 @@
 	root->right = llist;						\
 	llist = root;							\
 	root = y;							\
+	found = root != rlist;						\
 } while (0)
 
 /*
- * Walk down the tree until we find addr or a NULL pointer where addr would go,
- * breaking off left and right subtrees of nodes less than, or greater than
- * addr.  Treat pointers to nodes with max_free < length as NULL pointers.
- * llist and rlist are the two sides in reverse order (bottom-up), with llist
- * linked by the right pointer and rlist linked by the left pointer in the
- * vm_map_entry, and both lists terminated by &map->header.  This function, and
- * the subsequent call to vm_map_splay_merge, rely on the start and end address
- * values in &map->header.
+ * Walk down the tree until we find addr or a gap where addr would go, breaking
+ * off left and right subtrees of nodes less than, or greater than addr.  Treat
+ * subtrees with root->max_free < length as empty trees.  llist and rlist are
+ * the two sides in reverse order (bottom-up), with llist linked by the right
+ * pointer and rlist linked by the left pointer in the vm_map_entry, and both
+ * lists terminated by &map->header.  This function, and the subsequent call to
+ * vm_map_splay_merge_{left,right}, rely on the start and end address values in
+ * &map->header.
  */
-static vm_map_entry_t
-vm_map_splay_split(vm_map_t map, vm_offset_t addr, vm_size_t length,
-    vm_map_entry_t *out_llist, vm_map_entry_t *out_rlist)
-{
-	vm_map_entry_t llist, rlist, root, y;
+#define VM_MAP_SPLAY_SPLIT(map, addr, length, root, llist, rlist, found)\
+do {									\
+	vm_map_entry_t y;						\
+									\
+	llist = rlist = &map->header;					\
+	root = map->root;						\
+	found = root != NULL;						\
+	while (found && root->max_free >= length) {			\
+		KASSERT(llist->end <= root->start &&			\
+		    root->end <= rlist->start,				\
+		    ("%s: root not within tree bounds", __func__));	\
+		if (addr < root->start) {				\
+			SPLAY_LEFT_STEP(root, y, llist, rlist, found,	\
+			    y->max_free >= length && addr < y->start);	\
+		} else if (addr >= root->end) {				\
+			SPLAY_RIGHT_STEP(root, y, llist, rlist,	found,	\
+			    y->max_free >= length && addr >= y->end);	\
+		} else							\
+			break;						\
+	}								\
+} while (0)
 
-	llist = rlist = &map->header;
-	root = map->root;
-	while (root != NULL && root->max_free >= length) {
-		KASSERT(llist->end <= root->start && root->end <= rlist->start,
-		    ("%s: root not within tree bounds", __func__));
-		if (addr < root->start) {
-			SPLAY_LEFT_STEP(root, y, rlist,
-			    y->max_free >= length && addr < y->start);
-		} else if (addr >= root->end) {
-			SPLAY_RIGHT_STEP(root, y, llist,
-			    y->max_free >= length && addr >= y->end);
-		} else
-			break;
-	}
-	*out_llist = llist;
-	*out_rlist = rlist;
-	return (root);
-}
+#define VM_MAP_SPLAY_FINDNEXT(root, rlist) do {				\
+	vm_map_entry_t hi, y;						\
+	bool found;							\
+									\
+	hi = root->right;						\
+	if (hi == rlist)						\
+		break;							\
+	do								\
+		SPLAY_LEFT_STEP(hi, y, root, rlist, found, true);	\
+	while (found);							\
+} while (0)
 
-static void
-vm_map_splay_findnext(vm_map_entry_t root, vm_map_entry_t *iolist)
-{
-	vm_map_entry_t rlist, y;
+#define VM_MAP_SPLAY_FINDPREV(root, llist) do {				\
+	vm_map_entry_t lo, y;						\
+	bool found;							\
+									\
+	lo = root->left;						\
+	if (lo == llist)						\
+		break;							\
+	do								\
+		SPLAY_RIGHT_STEP(lo, y, llist, root, found, true);	\
+	while (found);							\
+} while (0)
 
-	root = root->right;
-	rlist = *iolist;
-	while (root != NULL)
-		SPLAY_LEFT_STEP(root, y, rlist, true);
-	*iolist = rlist;
-}
-
-static void
-vm_map_splay_findprev(vm_map_entry_t root, vm_map_entry_t *iolist)
-{
-	vm_map_entry_t llist, y;
-
-	root = root->left;
-	llist = *iolist;
-	while (root != NULL)
-		SPLAY_RIGHT_STEP(root, y, llist, true);
-	*iolist = llist;
-}
-
 static inline void
 vm_map_entry_swap(vm_map_entry_t *a, vm_map_entry_t *b)
 {
@@ -1132,50 +1150,120 @@
  * Walk back up the two spines, flip the pointers and set max_free.  The
  * subtrees of the root go at the bottom of llist and rlist.
  */
-static void
-vm_map_splay_merge(vm_map_t map, vm_map_entry_t root,
-    vm_map_entry_t llist, vm_map_entry_t rlist)
+static vm_size_t
+vm_map_splay_merge_left_walk(vm_map_t map, vm_map_entry_t root,
+    vm_map_entry_t tail, vm_size_t max_free, vm_map_entry_t llist)
 {
-	vm_map_entry_t prev;
-	vm_size_t max_free_left, max_free_right;
+	do {
+		/*
+		 * The max_free values of the children of llist are in
+		 * llist->max_free and max_free.  Update with the
+		 * max value.
+		 */
+		llist->max_free = max_free =
+		    vm_size_max(llist->max_free, max_free);
+		vm_map_entry_swap(&llist->right, &tail);
+		vm_map_entry_swap(&tail, &llist);
+	} while (llist != &map->header);
+	root->left = tail;
+	return (max_free);
+}
 
-	max_free_left = vm_map_entry_max_free_left(root, llist);
+/*
+ * When llist is known to be the predecessor of root.
+ */
+static inline vm_size_t
+vm_map_splay_merge_pred(vm_map_t map, vm_map_entry_t root,
+    vm_map_entry_t llist)
+{
+	vm_size_t max_free;
+
+	max_free = root->start - llist->end;
+	if (llist != &map->header)
+		max_free = vm_map_splay_merge_left_walk(map, root,
+		    root, max_free, llist);
+	else {
+		root->left = llist;
+		llist->right = root;
+	}
+	return (max_free);
+}
+
+/*
+ * When llist may or may not be the predecessor of root.
+ */
+static inline vm_size_t
+vm_map_splay_merge_left(vm_map_t map, vm_map_entry_t root,
+    vm_map_entry_t llist)
+{
+	vm_size_t max_free;
+
+	max_free = vm_map_entry_max_free_left(root, llist);
 	if (llist != &map->header) {
-		prev = root->left;
-		do {
-			/*
-			 * The max_free values of the children of llist are in
-			 * llist->max_free and max_free_left.  Update with the
-			 * max value.
-			 */
-			llist->max_free = max_free_left =
-			    MAX(llist->max_free, max_free_left);
-			vm_map_entry_swap(&llist->right, &prev);
-			vm_map_entry_swap(&prev, &llist);
-		} while (llist != &map->header);
-		root->left = prev;
+		max_free = vm_map_splay_merge_left_walk(map, root,
+		    root->left == llist ? root : root->left,
+		    max_free, llist);
+	} else if (root->left == llist)
+		llist->right = root;
+	return (max_free);
+}
+
+static vm_size_t
+vm_map_splay_merge_right_walk(vm_map_t map, vm_map_entry_t root,
+    vm_map_entry_t tail, vm_size_t max_free, vm_map_entry_t rlist)
+{
+	do {
+		/*
+		 * The max_free values of the children of rlist are in
+		 * rlist->max_free and max_free.  Update with the
+		 * max value.
+		 */
+		rlist->max_free = max_free =
+		    vm_size_max(rlist->max_free, max_free);
+		vm_map_entry_swap(&rlist->left, &tail);
+		vm_map_entry_swap(&tail, &rlist);
+	} while (rlist != &map->header);
+	root->right = tail;
+	return (max_free);
+}
+
+/*
+ * When rlist is known to be the succecessor of root.
+ */
+static inline vm_size_t
+vm_map_splay_merge_succ(vm_map_t map, vm_map_entry_t root,
+    vm_map_entry_t rlist)
+{
+	vm_size_t max_free;
+
+	max_free = rlist->start - root->end;
+	if (rlist != &map->header) {
+		max_free = vm_map_splay_merge_right_walk(map, root,
+		    root, max_free, rlist);
+	} else {
+		root->right = rlist;
+		rlist->left = root;
 	}
-	max_free_right = vm_map_entry_max_free_right(root, rlist);
+	return (max_free);
+}
+
+/*
+ * When rlist may or may not be the succecessor of root.
+ */
+static inline vm_size_t
+vm_map_splay_merge_right(vm_map_t map, vm_map_entry_t root,
+    vm_map_entry_t rlist)
+{
+	vm_size_t max_free;
+
+	max_free = vm_map_entry_max_free_right(root, rlist);
 	if (rlist != &map->header) {
-		prev = root->right;
-		do {
-			/*
-			 * The max_free values of the children of rlist are in
-			 * rlist->max_free and max_free_right.  Update with the
-			 * max value.
-			 */
-			rlist->max_free = max_free_right =
-			    MAX(rlist->max_free, max_free_right);
-			vm_map_entry_swap(&rlist->left, &prev);
-			vm_map_entry_swap(&prev, &rlist);
-		} while (rlist != &map->header);
-		root->right = prev;
-	}		
-	root->max_free = MAX(max_free_left, max_free_right);
-	map->root = root;
-#ifdef DIAGNOSTIC
-	++map->nupdates;
-#endif
+		max_free = vm_map_splay_merge_right_walk(map, root,
+		    root->right == rlist ? root : root->right,
+		    max_free, rlist);
+	} else if (root->right == rlist)
+		rlist->left = root;
+	return (max_free);
 }
 
 /*
@@ -1188,6 +1276,14 @@
  *	the pointers and compute max_free.  The time bound is O(log n)
  *	amortized.
  *
+ *	The tree is threaded, which means that there are no null pointers.
+ *	When a node has no left child, its left pointer points to its
+ *	predecessor, which the last ancestor on the search path from the root
+ *	where the search branched right.  Likewise, when a node has no right
+ *	child, its right pointer points to its successor.  The map header node
+ *	is the predecessor of the first map entry, and the successor of the
+ *	last.
+ *
  *	The new root is the vm_map_entry containing "addr", or else an
  *	adjacent entry (lower if possible) if addr is not in the tree.
  *
@@ -1199,10 +1295,13 @@
 vm_map_splay(vm_map_t map, vm_offset_t addr)
 {
 	vm_map_entry_t llist, rlist, root;
+	vm_size_t max_free_left, max_free_right;
+	bool found;
 
-	root = vm_map_splay_split(map, addr, 0, &llist, &rlist);
-	if (root != NULL) {
-		/* do nothing */
+	VM_MAP_SPLAY_SPLIT(map, addr, 0, root, llist, rlist, found);
+	if (found) {
+		max_free_left = vm_map_splay_merge_left(map, root, llist);
+		max_free_right = vm_map_splay_merge_right(map, root, rlist);
 	} else if (llist != &map->header) {
 		/*
 		 * Recover the greatest node in the left
@@ -1210,7 +1309,8 @@
 		 */
 		root = llist;
 		llist = root->right;
-		root->right = NULL;
+		max_free_left = vm_map_splay_merge_left(map, root, llist);
+		max_free_right = vm_map_splay_merge_succ(map, root, rlist);
 	} else if (rlist != &map->header) {
 		/*
 		 * Recover the least node in the right
@@ -1218,12 +1318,14 @@
 		 */
 		root = rlist;
 		rlist = root->left;
-		root->left = NULL;
+		max_free_left = vm_map_splay_merge_pred(map, root, llist);
+		max_free_right = vm_map_splay_merge_right(map, root, rlist);
 	} else {
 		/* There is no root. */
 		return (NULL);
 	}
-	vm_map_splay_merge(map, root, llist, rlist);
+	root->max_free = vm_size_max(max_free_left, max_free_right);
+	map->root = root;
 	VM_MAP_ASSERT_CONSISTENT(map);
 	return (root);
 }
@@ -1237,20 +1339,21 @@
 vm_map_entry_link(vm_map_t map, vm_map_entry_t entry)
 {
 	vm_map_entry_t llist, rlist, root;
+	bool found;
 
 	CTR3(KTR_VM,
 	    "vm_map_entry_link: map %p, nentries %d, entry %p", map,
 	    map->nentries, entry);
 	VM_MAP_ASSERT_LOCKED(map);
 	map->nentries++;
-	root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
-	KASSERT(root == NULL,
+	VM_MAP_SPLAY_SPLIT(map, entry->start, 0, root, llist, rlist, found);
+	KASSERT(!found,
 	    ("vm_map_entry_link: link object already mapped"));
-	entry->prev = llist;
-	entry->next = rlist;
-	llist->next = rlist->prev = entry;
-	entry->left = entry->right = NULL;
-	vm_map_splay_merge(map, entry, llist, rlist);
+	root = entry;
+	root->max_free = vm_size_max(
+	    vm_map_splay_merge_pred(map, root, llist),
+	    vm_map_splay_merge_succ(map, root, rlist));
+	map->root = root;
 	VM_MAP_ASSERT_CONSISTENT(map);
 }
 
@@ -1263,44 +1366,38 @@
 vm_map_entry_unlink(vm_map_t map, vm_map_entry_t entry,
     enum unlink_merge_type op)
 {
-	vm_map_entry_t llist, rlist, root, y;
+	vm_map_entry_t llist, rlist, root;
+	vm_size_t max_free_left, max_free_right;
+	bool found;
 
 	VM_MAP_ASSERT_LOCKED(map);
-	root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
-	KASSERT(root != NULL,
+	VM_MAP_SPLAY_SPLIT(map, entry->start, 0, root, llist, rlist, found);
+	KASSERT(found,
 	    ("vm_map_entry_unlink: unlink object not mapped"));
 
-	vm_map_splay_findnext(root, &rlist);
-	switch (op) {
-	case UNLINK_MERGE_NEXT:
+	VM_MAP_SPLAY_FINDPREV(root, llist);
+	VM_MAP_SPLAY_FINDNEXT(root, rlist);
+	if (op == UNLINK_MERGE_NEXT) {
 		rlist->start = root->start;
 		rlist->offset = root->offset;
-		y = root->left;
+	}
+	if (llist != &map->header) {
+		root = llist;
+		llist = root->right;
+		max_free_left = vm_map_splay_merge_left(map, root, llist);
+		max_free_right = vm_map_splay_merge_succ(map, root, rlist);
+	} else if (rlist != &map->header) {
 		root = rlist;
 		rlist = root->left;
-		root->left = y;
-		break;
-	case UNLINK_MERGE_NONE:
-		vm_map_splay_findprev(root, &llist);
-		if (llist != &map->header) {
-			root = llist;
-			llist = root->right;
-			root->right = NULL;
-		} else if (rlist != &map->header) {
-			root = rlist;
-			rlist = root->left;
-			root->left = NULL;
-		} else
-			root = NULL;
-		break;
+		max_free_left = vm_map_splay_merge_pred(map, root, llist);
+		max_free_right = vm_map_splay_merge_right(map, root, rlist);
+	} else {
+		map->header.left = map->header.right = &map->header;
+		root = NULL;
 	}
-	y = entry->next;
-	y->prev = entry->prev;
-	y->prev->next = y;
 	if (root != NULL)
-		vm_map_splay_merge(map, root, llist, rlist);
-	else
-		map->root = NULL;
+		root->max_free = vm_size_max(max_free_left, max_free_right);
+	map->root = root;
 	VM_MAP_ASSERT_CONSISTENT(map);
 	map->nentries--;
 	CTR3(KTR_VM, "vm_map_entry_unlink: map %p, nentries %d, entry %p", map,
@@ -1319,15 +1416,18 @@
 vm_map_entry_resize(vm_map_t map, vm_map_entry_t entry, vm_size_t grow_amount)
 {
 	vm_map_entry_t llist, rlist, root;
+	bool found;
 
 	VM_MAP_ASSERT_LOCKED(map);
-	root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
-	KASSERT(root != NULL,
+	VM_MAP_SPLAY_SPLIT(map, entry->start, 0, root, llist, rlist, found);
+	KASSERT(found,
 	    ("%s: resize object not mapped", __func__));
-	vm_map_splay_findnext(root, &rlist);
-	root->right = NULL;
+	VM_MAP_SPLAY_FINDNEXT(root, rlist);
 	entry->end += grow_amount;
-	vm_map_splay_merge(map, root, llist, rlist);
+	root->max_free = vm_size_max(
+	    vm_map_splay_merge_left(map, root, llist),
+	    vm_map_splay_merge_succ(map, root, rlist));
+	map->root = root;
 	VM_MAP_ASSERT_CONSISTENT(map);
 	CTR4(KTR_VM, "%s: map %p, nentries %d, entry %p",
 	    __func__, map, map->nentries, entry);
@@ -1349,7 +1449,7 @@
 	vm_offset_t address,
 	vm_map_entry_t *entry)	/* OUT */
 {
-	vm_map_entry_t cur, lbound;
+	vm_map_entry_t cur, lbound, ubound;
 	boolean_t locked;
 
 	/*
@@ -1395,18 +1495,23 @@
 	 * Since the map is only locked for read access, perform a
 	 * standard binary search tree lookup for "address".
 	 */
-	lbound = &map->header;
-	do {
+	lbound = ubound = &map->header;
+	for (;;) {
 		if (address < cur->start) {
+			ubound = cur;
 			cur = cur->left;
+			if (cur == lbound)
+				break;
 		} else if (cur->end <= address) {
 			lbound = cur;
 			cur = cur->right;
+			if (cur == ubound)
+				break;
 		} else {
 			*entry = cur;
 			return (TRUE);
 		}
-	} while (cur != NULL);
+	}
 	*entry = lbound;
 	return (FALSE);
 }
@@ -1646,8 +1751,8 @@
 vm_map_findspace(vm_map_t map, vm_offset_t start, vm_size_t length)
 {
 	vm_map_entry_t llist, rlist, root, y;
-	vm_size_t left_length;
-	vm_offset_t gap_end;
+	vm_size_t left_length, max_free_left, max_free_right;
+	bool found;
 
 	/*
 	 * Request must fit within min/max VM address and must avoid
@@ -1664,63 +1769,70 @@
 	/*
 	 * After splay_split, if start is within an entry, push it to the start
 	 * of the following gap.  If rlist is at the end of the gap containing
-	 * start, save the end of that gap in gap_end to see if the gap is big
-	 * enough; otherwise set gap_end to start skip gap-checking and move
-	 * directly to a search of the right subtree.
+	 * start, clear 'found' and see if the gap is big enough.
 	 */
-	root = vm_map_splay_split(map, start, length, &llist, &rlist);
-	gap_end = rlist->start;
-	if (root != NULL) {
-		start = root->end;
-		if (root->right != NULL)
-			gap_end = start;
+	VM_MAP_SPLAY_SPLIT(map, start, length, root, llist, rlist, found);
+	if (found) {
+		max_free_left = vm_map_splay_merge_left(map, root, llist);
+		if (root->right == rlist) {
+			start = root->end;
+			found = false;
+		}
+		max_free_right = vm_map_splay_merge_right(map, root, rlist);
 	} else if (rlist != &map->header) {
 		root = rlist;
 		rlist = root->left;
-		root->left = NULL;
+		max_free_left = vm_map_splay_merge_pred(map, root, llist);
+		max_free_right = vm_map_splay_merge_right(map, root, rlist);
 	} else {
 		root = llist;
 		llist = root->right;
-		root->right = NULL;
+		root->right = rlist;
+		rlist->left = root;
+		max_free_left = vm_map_splay_merge_left(map, root, llist);
+		max_free_right = rlist->start - root->end;
 	}
-	vm_map_splay_merge(map, root, llist, rlist);
+	root->max_free = vm_size_max(max_free_left, max_free_right);
+	map->root = root;
 	VM_MAP_ASSERT_CONSISTENT(map);
-	if (length <= gap_end - start)
+	if (!found && length <= rlist->start - start)
 		return (start);
 
 	/* With max_free, can immediately tell if no solution. */
-	if (root->right == NULL || length > root->right->max_free)
+	if (root->right == &map->header || length > root->right->max_free)
 		return (vm_map_max(map) - length + 1);
 
 	/*
 	 * Splay for the least large-enough gap in the right subtree.
 	 */
 	llist = rlist = &map->header;
-	for (left_length = 0;;
+	for (left_length = 0, found = true; found;
 	    left_length = vm_map_entry_max_free_left(root, llist)) {
 		if (length <= left_length)
-			SPLAY_LEFT_STEP(root, y, rlist,
+			SPLAY_LEFT_STEP(root, y, llist, rlist, found,
 			    length <= vm_map_entry_max_free_left(y, llist));
 		else
-			SPLAY_RIGHT_STEP(root, y, llist,
+			SPLAY_RIGHT_STEP(root, y, llist, rlist, found,
 			    length > vm_map_entry_max_free_left(y, root));
-		if (root == NULL)
-			break;
 	}
 	root = llist;
 	llist = root->right;
-	root->right = NULL;
-	if (rlist != &map->header) {
+	root->max_free = vm_map_splay_merge_left(map, root, llist);
+	if (rlist == &map->header) {
+		root->right = rlist;
+		root->max_free = vm_size_max(root->max_free,
+			rlist->start - root->end);
+	} else {
 		y = rlist;
 		rlist = y->left;
-		y->left = NULL;
-		vm_map_splay_merge(map, y, &map->header, rlist);
-		y->max_free = MAX(
-		    vm_map_entry_max_free_left(y, root),
-		    vm_map_entry_max_free_right(y, &map->header));
+		y->left = root;
+		y->max_free = vm_size_max(
+		    y->start - root->end,
+		    vm_map_splay_merge_right(map, y, rlist));
 		root->right = y;
+		root->max_free = vm_size_max(root->max_free, y->max_free);
 	}
-	vm_map_splay_merge(map, root, llist, &map->header);
+	map->root = root;
 	VM_MAP_ASSERT_CONSISTENT(map);
 	return (root->end);
 }
@@ -4847,8 +4959,12 @@
 _vm_map_assert_consistent(vm_map_t map, int check)
 {
 	vm_map_entry_t entry, prev;
+	vm_map_entry_t cur, lbound, ubound;
 	vm_size_t max_left, max_right;
 
+#ifdef DIAGNOSTIC
+	++map->nupdates;
+#endif
 	if (enable_vmmap_check != check)
 		return;
 
@@ -4860,23 +4976,39 @@
 		KASSERT(entry->start < entry->end,
 		    ("map %p start = %jx, end = %jx", map,
 		    (uintmax_t)entry->start, (uintmax_t)entry->end));
-		KASSERT(entry->end <= vm_map_entry_succ(entry)->start,
-		    ("map %p end = %jx, next->start = %jx", map,
-		     (uintmax_t)entry->end,
-		     (uintmax_t)vm_map_entry_succ(entry)->start));
-		KASSERT(entry->left == NULL ||
+		KASSERT(entry->left == &map->header ||
 		    entry->left->start < entry->start,
 		    ("map %p left->start = %jx, start = %jx", map,
 		    (uintmax_t)entry->left->start, (uintmax_t)entry->start));
-		KASSERT(entry->right == NULL ||
+		KASSERT(entry->right == &map->header ||
 		    entry->start < entry->right->start,
 		    ("map %p start = %jx, right->start = %jx", map,
 		    (uintmax_t)entry->start, (uintmax_t)entry->right->start));
-		max_left = vm_map_entry_max_free_left(entry,
-		    vm_map_entry_pred(entry));
-		max_right = vm_map_entry_max_free_right(entry,
-		    vm_map_entry_succ(entry));
-		KASSERT(entry->max_free == MAX(max_left, max_right),
+		cur = map->root;
+		lbound = ubound = &map->header;
+		for (;;) {
+			if (entry->start < cur->start) {
+				ubound = cur;
+				cur = cur->left;
+				KASSERT(cur != lbound,
+				    ("map %p cannot find %jx",
+				    map, entry->start));
+			} else if (cur->end <= entry->start) {
+				lbound = cur;
+				cur = cur->right;
+				KASSERT(cur != ubound,
+				    ("map %p cannot find %jx",
+				    map, entry->start));
+			} else {
+				KASSERT(cur == entry,
+				    ("map %p cannot find %jx",
+				    map, entry->start));
+				break;
+			}
+		}
+		max_left = vm_map_entry_max_free_left(entry, lbound);
+		max_right = vm_map_entry_max_free_right(entry, ubound);
+		KASSERT(entry->max_free == vm_size_max(max_left, max_right),
 		    ("map %p max = %jx, max_left = %jx, max_right = %jx", map,
 		    (uintmax_t)entry->max_free,
 		    (uintmax_t)max_left, (uintmax_t)max_right));