Index: vm_map.c
===================================================================
--- vm_map.c
+++ vm_map.c
@@ -966,55 +966,92 @@
 }
 
 /*
- *	vm_map_entry_set_max_free:
+ *	vm_map_entry_max_free_{left,right}:
  *
- *	Set the max_free field in a vm_map_entry.
+ *	Compute the size of the largest free gap between two entries,
+ *	one the root of a tree and the other the ancestor of that root
+ *	that is the least or greatest ancestor found on the search path.
  */
-static inline void
-vm_map_entry_set_max_free(vm_map_entry_t entry)
+static inline vm_size_t
+vm_map_entry_max_free_left(vm_map_entry_t root, vm_map_entry_t left_ancestor)
 {
-	vm_map_entry_t child;
-	vm_size_t max_left, max_right;
 
-	child = entry->left;
-	max_left = (child != NULL) ? child->max_free :
-	    entry->start - entry->prev->end;
-	child = entry->right;
-	max_right = (child != NULL) ? child->max_free :
-	    entry->next->start - entry->end;
-	entry->max_free = MAX(max_left, max_right);
+	return (root->left != NULL ?
+	    root->left->max_free : root->start - left_ancestor->end);
 }
 
-#define SPLAY_LEFT_STEP(root, y, rlist, test) do {	\
-	y = root->left;					\
-	if (y != NULL && (test)) {			\
-		/* Rotate right and make y root. */	\
-		root->left = y->right;			\
-		y->right = root;			\
-		vm_map_entry_set_max_free(root);	\
-		root = y;				\
-		y = root->left;				\
-	}						\
-	/* Put root on rlist. */			\
-	root->left = rlist;				\
-	rlist = root;					\
-	root = y;					\
+static inline vm_size_t
+vm_map_entry_max_free_right(vm_map_entry_t root, vm_map_entry_t right_ancestor)
+{
+
+	return (root->right != NULL ?
+	    root->right->max_free : right_ancestor->start - root->end);
+}
+
+#define SPLAY_LEFT_STEP(root, y, rlist, test) do {			\
+	vm_size_t max_free;						\
+									\
+	/*								\
+	 * Infer root->right->max_free == root->max_free when		\
+	 * y->max_free < root->max_free || root->max_free == 0.		\
+	 * Otherwise, look right to find it.				\
+	 */								\
+	y = root->left;							\
+	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)	\
+		max_free = vm_map_entry_max_free_right(root, rlist);	\
+	if (y != NULL && (test)) {					\
+		/* Rotate right and make y root. */			\
+		root->left = y->right;					\
+		y->right = root;					\
+		if (max_free < y->max_free)				\
+			root->max_free = max_free = MAX(max_free,	\
+			    vm_map_entry_max_free_left(root, y));	\
+		root = y;						\
+		y = root->left;						\
+	}								\
+	/* Copy right->max_free.  Put root on rlist. */			\
+	root->max_free = max_free;					\
+	KASSERT(max_free == vm_map_entry_max_free_right(root, rlist),	\
+	    ("%s: max_free not copied from right", __func__));		\
+	root->left = rlist;						\
+	rlist = root;							\
+	root = y;							\
 } while (0)
 
-#define SPLAY_RIGHT_STEP(root, y, llist, test) do {	\
-	y = root->right;				\
-	if (y != NULL && (test)) {			\
-		/* Rotate left and make y root. */	\
-		root->right = y->left;			\
-		y->left = root;				\
-		vm_map_entry_set_max_free(root);	\
-		root = y;				\
-		y = root->right;			\
-	}						\
-	/* Put root on llist. */			\
-	root->right = llist;				\
-	llist = root;					\
-	root = y;					\
+#define SPLAY_RIGHT_STEP(root, y, llist, test) do {			\
+	vm_size_t max_free;						\
+									\
+	/*								\
+	 * Infer root->left->max_free == root->max_free when		\
+	 * y->max_free < root->max_free || root->max_free == 0.		\
+	 * Otherwise, look left to find it.				\
+	 */								\
+	y = root->right;						\
+	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)	\
+		max_free = vm_map_entry_max_free_left(root, llist);	\
+	if (y != NULL && (test)) {					\
+		/* Rotate left and make y root. */			\
+		root->right = y->left;					\
+		y->left = root;						\
+		if (max_free < y->max_free)				\
+			root->max_free = max_free = MAX(max_free,	\
+			    vm_map_entry_max_free_right(root, y));	\
+		root = y;						\
+		y = root->right;					\
+	}								\
+	/* Copy left->max_free.  Put root on llist. */			\
+	root->max_free = max_free;					\
+	KASSERT(max_free == vm_map_entry_max_free_left(root, llist),	\
+	    ("%s: max_free not copied from left", __func__));		\
+	root->right = llist;						\
+	llist = root;							\
+	root = y;							\
 } while (0)
 
 /*
@@ -1023,18 +1060,21 @@
  * 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.
+ * vm_map_entry, and both lists terminated by &map->header.  This function, and
+ * the subsequent call to vm_map_splay_merge, rely on the values of start and
+ * end address values in &map->header.
  */
 static vm_map_entry_t
-vm_map_splay_split(vm_offset_t addr, vm_size_t length,
-    vm_map_entry_t root, vm_map_entry_t *out_llist, vm_map_entry_t *out_rlist)
+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;
-	vm_map_entry_t y;
+	vm_map_entry_t llist, rlist, root, y;
 
-	llist = NULL;
-	rlist = NULL;
+	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);
@@ -1073,44 +1113,65 @@
 	*iolist = llist;
 }
 
+static inline void
+vm_map_entry_swap(vm_map_entry_t *a, vm_map_entry_t *b)
+{
+	vm_map_entry_t tmp;
+
+	tmp = *b;
+	*b = *a;
+	*a = tmp;
+}
+
 /*
  * 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 vm_map_entry_t
-vm_map_splay_merge(vm_map_entry_t root,
-    vm_map_entry_t llist, vm_map_entry_t rlist,
-    vm_map_entry_t ltree, vm_map_entry_t rtree)
+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)
 {
-	vm_map_entry_t y;
+	vm_map_entry_t prev;
+	vm_size_t max_free_left, max_free_right;
 
-	while (llist != NULL) {
-		y = llist->right;
-		llist->right = ltree;
-		vm_map_entry_set_max_free(llist);
-		ltree = llist;
-		llist = y;
+	max_free_left = 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;
 	}
-	while (rlist != NULL) {
-		y = rlist->left;
-		rlist->left = rtree;
-		vm_map_entry_set_max_free(rlist);
-		rtree = rlist;
-		rlist = y;
-	}
-
-	/*
-	 * Final assembly: add ltree and rtree as subtrees of root.
-	 */
-	root->left = ltree;
-	root->right = rtree;
-	vm_map_entry_set_max_free(root);
-
-	return (root);
+	max_free_right = 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;
 }
 
 /*
- *	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
@@ -1127,14 +1188,14 @@
  *	Returns: the new root.
  */
 static vm_map_entry_t
-vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t root)
+vm_map_splay(vm_offset_t addr, vm_map_t map)
 {
-	vm_map_entry_t llist, rlist;
+	vm_map_entry_t llist, rlist, root;
 
-	root = vm_map_splay_split(addr, 0, root, &llist, &rlist);
+	root = vm_map_splay_split(map, addr, 0, &llist, &rlist);
 	if (root != NULL) {
 		/* do nothing */
-	} else if (llist != NULL) {
+	} else if (llist != &map->header) {
 		/*
 		 * Recover the greatest node in the left
 		 * subtree and make it the root.
@@ -1142,7 +1203,7 @@
 		root = llist;
 		llist = root->right;
 		root->right = NULL;
-	} else if (rlist != NULL) {
+	} else if (rlist != &map->header) {
 		/*
 		 * Recover the least node in the right
 		 * subtree and make it the root.
@@ -1154,8 +1215,9 @@
 		/* There is no root. */
 		return (NULL);
 	}
-	return (vm_map_splay_merge(root, llist, rlist,
-	    root->left, root->right));
+	vm_map_splay_merge(map, root, llist, rlist);
+	VM_MAP_ASSERT_CONSISTENT(map);
+	return (root);
 }
 
 /*
@@ -1164,8 +1226,7 @@
  *	Insert/remove entries from maps.
  */
 static void
-vm_map_entry_link(vm_map_t map,
-		  vm_map_entry_t entry)
+vm_map_entry_link(vm_map_t map, vm_map_entry_t entry)
 {
 	vm_map_entry_t llist, rlist, root;
 
@@ -1174,15 +1235,14 @@
 	    map->nentries, entry);
 	VM_MAP_ASSERT_LOCKED(map);
 	map->nentries++;
-	root = map->root;
-	root = vm_map_splay_split(entry->start, 0, root, &llist, &rlist);
+	root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
 	KASSERT(root == NULL,
 	    ("vm_map_entry_link: link object already mapped"));
-	entry->prev = (llist == NULL) ? &map->header : llist;
-	entry->next = (rlist == NULL) ? &map->header : rlist;
-	entry->prev->next = entry->next->prev = entry;
-	root = vm_map_splay_merge(entry, llist, rlist, NULL, NULL);
-	map->root = entry;
+	entry->prev = llist;
+	entry->next = rlist;
+	llist->next = rlist->prev = entry;
+	entry->left = entry->right = NULL;
+	vm_map_splay_merge(map, entry, llist, rlist);
 	VM_MAP_ASSERT_CONSISTENT(map);
 }
 
@@ -1193,19 +1253,13 @@
 };
 
 static void
-vm_map_entry_unlink(vm_map_t map,
-		    vm_map_entry_t entry,
+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_ASSERT_LOCKED(map);
-	llist = entry->prev;
-	rlist = entry->next;
-	llist->next = rlist;
-	rlist->prev = llist;
-	root = map->root;
-	root = vm_map_splay_split(entry->start, 0, root, &llist, &rlist);
+	root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
 	KASSERT(root != NULL,
 	    ("vm_map_entry_unlink: unlink object not mapped"));
 
@@ -1230,11 +1284,11 @@
 	case UNLINK_MERGE_NONE:
 		vm_map_splay_findprev(root, &llist);
 		vm_map_splay_findnext(root, &rlist);
-		if (llist != NULL) {
+		if (llist != &map->header) {
 			root = llist;
 			llist = root->right;
 			root->right = NULL;
-		} else if (rlist != NULL) {
+		} else if (rlist != &map->header) {
 			root = rlist;
 			rlist = root->left;
 			root->left = NULL;
@@ -1242,10 +1296,13 @@
 			root = NULL;
 		break;
 	}
+	y = entry->next;
+	y->prev = entry->prev;
+	y->prev->next = y;
 	if (root != NULL)
-		root = vm_map_splay_merge(root, llist, rlist,
-		    root->left, root->right);
-	map->root = root;
+		vm_map_splay_merge(map, root, llist, rlist);
+	else
+		map->root = NULL;
 	VM_MAP_ASSERT_CONSISTENT(map);
 	map->nentries--;
 	CTR3(KTR_VM, "vm_map_entry_unlink: map %p, nentries %d, entry %p", map,
@@ -1266,15 +1323,13 @@
 	vm_map_entry_t llist, rlist, root;
 
 	VM_MAP_ASSERT_LOCKED(map);
-	root = map->root;
-	root = vm_map_splay_split(entry->start, 0, root, &llist, &rlist);
+	root = vm_map_splay_split(map, entry->start, 0, &llist, &rlist);
 	KASSERT(root != NULL,
 	    ("%s: resize object not mapped", __func__));
 	vm_map_splay_findnext(root, &rlist);
 	root->right = NULL;
 	entry->end += grow_amount;
-	map->root = vm_map_splay_merge(root, llist, rlist,
-	    root->left, root->right);
+	vm_map_splay_merge(map, root, llist, rlist);
 	VM_MAP_ASSERT_CONSISTENT(map);
 	CTR4(KTR_VM, "%s: map %p, nentries %d, entry %p",
 	    __func__, map, map->nentries, entry);
@@ -1320,8 +1375,7 @@
 		 * 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_ASSERT_CONSISTENT(map);
+		cur = vm_map_splay(address, map);
 		if (!locked)
 			sx_downgrade(&map->lock);
 
@@ -1608,11 +1662,10 @@
 	 * After splay, if start comes before root node, then there
 	 * must be a gap from start to the root.
 	 */
-	root = vm_map_splay_split(start, length, map->root,
-	    &llist, &rlist);
+	root = vm_map_splay_split(map, start, length, &llist, &rlist);
 	if (root != NULL)
 		start = root->end;
-	else if (rlist != NULL) {
+	else if (rlist != &map->header) {
 		root = rlist;
 		rlist = root->left;
 		root->left = NULL;
@@ -1621,8 +1674,7 @@
 		llist = root->right;
 		root->right = NULL;
 	}
-	map->root = vm_map_splay_merge(root, llist, rlist,
-	    root->left, root->right);
+	vm_map_splay_merge(map, root, llist, rlist);
 	VM_MAP_ASSERT_CONSISTENT(map);
 	if (start + length <= root->start)
 		return (start);
@@ -1643,40 +1695,32 @@
 	/*
 	 * Splay for the least large-enough gap in the right subtree.
 	 */
-	llist = NULL;
-        rlist = NULL;
-	for (left_length = 0; ;
-	     left_length = root->left != NULL ?
-	     root->left->max_free : root->start - llist->end) {
+	llist = rlist = &map->header;
+	for (left_length = 0;;
+	    left_length = vm_map_entry_max_free_left(root, llist)) {
 		if (length <= left_length)
 			SPLAY_LEFT_STEP(root, y, rlist,
-			    length <= (y->left != NULL ?
-			    y->left->max_free : y->start - llist->end));
+			    length <= vm_map_entry_max_free_left(y, llist));
 		else
 			SPLAY_RIGHT_STEP(root, y, llist,
-			    length > (y->left != NULL ?
-			    y->left->max_free : y->start - root->end));
+			    length > vm_map_entry_max_free_left(y, root));
 		if (root == NULL)
 			break;
 	}
 	root = llist;
 	llist = root->right;
-	if ((y = rlist) == NULL)
-		root->right = NULL;
-	else {
+	root->right = NULL;
+	if (rlist != &map->header) {
+		y = rlist;
 		rlist = y->left;
 		y->left = NULL;
-		root->right = y->right;
-	}
-	root = vm_map_splay_merge(root, llist, rlist,
-	    root->left, root->right);
-	if (y != NULL) {
-		y->right = root->right;
-		vm_map_entry_set_max_free(y);
+		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));
 		root->right = y;
-		vm_map_entry_set_max_free(root);
 	}
-	map->root = root;
+	vm_map_splay_merge(map, root, llist, &map->header);
 	VM_MAP_ASSERT_CONSISTENT(map);
 	return (root->end);
 }