Index: sys/vm/vm_map.c
===================================================================
--- sys/vm/vm_map.c
+++ sys/vm/vm_map.c
@@ -909,55 +909,67 @@
 }
 
 /*
- *	vm_map_entry_set_max_free:
+ *	vm_map_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 entry that lies on
+ *	the other side of the tree.
  */
-static inline void
-vm_map_entry_set_max_free(vm_map_entry_t entry)
+
+static inline size_t
+vm_map_max_free_left(vm_map_entry_t root, vm_map_entry_t y)
 {
-	vm_map_entry_t child;
-	vm_size_t max_left, max_right;
+	return (root->left != NULL ?
+	    root->left->max_free : root->start - y->end);
+}
 
-	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);
+static inline size_t
+vm_map_max_free_right(vm_map_entry_t root, vm_map_entry_t y)
+{
+	return (root->right != NULL ?
+	    root->right->max_free : y->start - root->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;					\
+#define SPLAY_LEFT_STEP(root, y, llist, rlist, test) do {		\
+	y = root->left;							\
+	if (y != NULL && (test)) {					\
+		/* Rotate right and make y root. */			\
+		root->left = y->right;					\
+		y->right = root;					\
+		if (root->max_free == y->max_free)			\
+			root->max_free = MAX(				\
+			    vm_map_max_free_left(root, y),		\
+			    vm_map_max_free_right(root, rlist));	\
+		y->max_free = root->max_free;				\
+		root = y;						\
+		y = root->left;						\
+	} else if (root->max_free == vm_map_max_free_left(root, llist))	\
+		root->max_free = vm_map_max_free_right(root, rlist);	\
+	/* Put root on rlist. */					\
+	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, rlist, test) do {		\
+	y = root->right;						\
+	if (y != NULL && (test)) {					\
+		/* Rotate left and make y root. */			\
+		root->right = y->left;					\
+		y->left = root;						\
+		if (root->max_free == y->max_free)			\
+			root->max_free = MAX(				\
+			    vm_map_max_free_left(root, llist),		\
+			    vm_map_max_free_right(root, y));		\
+		y->max_free = root->max_free;				\
+		root = y;						\
+		y = root->right;					\
+	} else if (root->max_free == vm_map_max_free_right(root, rlist))\
+		root->max_free = vm_map_max_free_left(root, llist);	\
+	/* Put root on llist. */					\
+	root->right = llist;						\
+	llist = root;							\
+	root = y;							\
 } while (0)
 
 /*
@@ -970,49 +982,51 @@
  */
 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_entry_t root, vm_map_entry_t *io_llist, vm_map_entry_t *io_rlist)
 {
 	vm_map_entry_t llist, rlist;
 	vm_map_entry_t y;
 
-	llist = NULL;
-	rlist = NULL;
+	llist = *io_llist;
+	rlist = *io_rlist;
 	while (root != NULL && root->max_free >= length) {
 		if (addr < root->start) {
-			SPLAY_LEFT_STEP(root, y, rlist,
+			SPLAY_LEFT_STEP(root, y, llist, rlist,
 			    y->max_free >= length && addr < y->start);
 		} else if (addr >= root->end) {
-			SPLAY_RIGHT_STEP(root, y, llist,
+			SPLAY_RIGHT_STEP(root, y, llist, rlist,
 			    y->max_free >= length && addr >= y->end);
 		} else
 			break;
 	}
-	*out_llist = llist;
-	*out_rlist = rlist;
+	*io_llist = llist;
+	*io_rlist = rlist;
 	return (root);
 }
 
 static void
 vm_map_splay_findnext(vm_map_entry_t root, vm_map_entry_t *iolist)
 {
-	vm_map_entry_t rlist, y;
+	vm_map_entry_t llist, rlist, y;
 
+	llist = root;
 	root = root->right;
 	rlist = *iolist;
 	while (root != NULL)
-		SPLAY_LEFT_STEP(root, y, rlist, true);
+		SPLAY_LEFT_STEP(root, y, llist, 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;
+	vm_map_entry_t llist, rlist, y;
 
+	rlist = root;
 	root = root->left;
 	llist = *iolist;
 	while (root != NULL)
-		SPLAY_RIGHT_STEP(root, y, llist, true);
+		SPLAY_RIGHT_STEP(root, y, llist, rlist, true);
 	*iolist = llist;
 }
 
@@ -1020,36 +1034,44 @@
  * 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
+static void
 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)
+    vm_map_entry_t llist, vm_map_entry_t rlist)
 {
-	vm_map_entry_t y;
+	vm_map_entry_t tree, y;
+	vm_size_t max_free;
 
-	while (llist != NULL) {
+	tree = root->left;
+	if ((llist->eflags & MAP_ENTRY_HEADER) == 0)
+		max_free = vm_map_max_free_left(root, llist);
+	while ((llist->eflags & MAP_ENTRY_HEADER) == 0) {
 		y = llist->right;
-		llist->right = ltree;
-		vm_map_entry_set_max_free(llist);
-		ltree = llist;
+		llist->right = tree;
+		if (llist->max_free < max_free)
+			llist->max_free = max_free;
+		else
+			max_free = llist->max_free;
+		tree = llist;
 		llist = y;
 	}
-	while (rlist != NULL) {
+	root->left = tree;
+	tree = root->right;
+	if ((rlist->eflags & MAP_ENTRY_HEADER) == 0)
+		max_free = vm_map_max_free_right(root, rlist);
+	while ((rlist->eflags & MAP_ENTRY_HEADER) == 0) {
 		y = rlist->left;
-		rlist->left = rtree;
-		vm_map_entry_set_max_free(rlist);
-		rtree = rlist;
+		rlist->left = tree;
+		if (rlist->max_free < max_free)
+			rlist->max_free = max_free;
+		else
+			max_free = rlist->max_free;
+		tree = 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);
+	root->right = tree;
+	root->max_free = MAX(
+	    vm_map_max_free_left(root, llist),
+	    vm_map_max_free_right(root, rlist));
 }
 
 /*
@@ -1070,14 +1092,16 @@
  *	Returns: the new root.
  */
 static vm_map_entry_t
-vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t root)
+vm_map_entry_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);
+	VM_MAP_ASSERT_CONSISTENT(map);
+	llist = rlist = &map->header;
+	root = vm_map_splay_split(addr, 0, map->root, &llist, &rlist);
 	if (root != NULL) {
 		/* do nothing */
-	} else if (llist != NULL) {
+	} else if ((llist->eflags & MAP_ENTRY_HEADER) == 0) {
 		/*
 		 * Recover the greatest node in the left
 		 * subtree and make it the root.
@@ -1085,7 +1109,7 @@
 		root = llist;
 		llist = root->right;
 		root->right = NULL;
-	} else if (rlist != NULL) {
+	} else if ((rlist->eflags & MAP_ENTRY_HEADER) == 0) {
 		/*
 		 * Recover the least node in the right
 		 * subtree and make it the root.
@@ -1095,10 +1119,13 @@
 		root->left = NULL;
 	} else {
 		/* There is no root. */
+		map->root = NULL;
 		return (NULL);
 	}
-	return (vm_map_splay_merge(root, llist, rlist,
-	    root->left, root->right));
+	vm_map_splay_merge(root, llist, rlist);
+	map->root = root;
+	VM_MAP_ASSERT_CONSISTENT(map);
+	return (root);
 }
 
 /*
@@ -1116,15 +1143,38 @@
 	    "vm_map_entry_link: map %p, nentries %d, entry %p", map,
 	    map->nentries, entry);
 	VM_MAP_ASSERT_LOCKED(map);
+	VM_MAP_ASSERT_CONSISTENT(map);
 	map->nentries++;
-	root = map->root;
-	root = vm_map_splay_split(entry->start, 0, root, &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);
+	llist = rlist = &map->header;
+	root = vm_map_splay_split(entry->start, 0, map->root, &llist, &rlist);
+	if (root != NULL &&
+	    entry->start == root->start && entry->end < root->end) {
+		if (root->max_free == vm_map_max_free_left(root, llist))
+			root->max_free = vm_map_max_free_right(root, rlist);
+		vm_map_splay_findprev(root, &llist);
+		root->left = rlist;
+		rlist = root;
+		rlist->offset += (entry->end - rlist->start);
+		rlist->start = entry->end;
+	} else if (root != NULL &&
+		   entry->start > root->start && entry->end == root->end) {
+		if (root->max_free == vm_map_max_free_right(root, rlist))
+			root->max_free = vm_map_max_free_left(root, llist);
+		vm_map_splay_findnext(root, &rlist);
+		root->right= llist;
+		llist = root;
+		llist->end = entry->start;
+	} else
+		KASSERT(root == NULL,
+		    ("vm_map_entry_link: inserting range [%jx, %jx) improperly"
+		    " overlaps mapped range [%jx, %jx)",
+		    (uintmax_t)entry->start, (uintmax_t)entry->end,
+		    (uintmax_t)root->start, (uintmax_t)root->end));
+	entry->prev = llist;
+	entry->next = rlist;
+	llist->next = rlist->prev = entry;
+	entry->left = entry->right = NULL;
+	vm_map_splay_merge(entry, llist, rlist);
 	map->root = entry;
 	VM_MAP_ASSERT_CONSISTENT(map);
 }
@@ -1143,12 +1193,9 @@
 	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);
+	VM_MAP_ASSERT_CONSISTENT(map);
+	llist = rlist = &map->header;
+	root = vm_map_splay_split(entry->start, 0, map->root, &llist, &rlist);
 	KASSERT(root != NULL,
 	    ("vm_map_entry_unlink: unlink object not mapped"));
 
@@ -1173,11 +1220,11 @@
 	case UNLINK_MERGE_NONE:
 		vm_map_splay_findprev(root, &llist);
 		vm_map_splay_findnext(root, &rlist);
-		if (llist != NULL) {
+		if ((llist->eflags & MAP_ENTRY_HEADER) == 0) {
 			root = llist;
 			llist = root->right;
 			root->right = NULL;
-		} else if (rlist != NULL) {
+		} else if ((rlist->eflags & MAP_ENTRY_HEADER) == 0) {
 			root = rlist;
 			rlist = root->left;
 			root->left = NULL;
@@ -1185,9 +1232,11 @@
 			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);
+		vm_map_splay_merge(root, llist, rlist);
 	map->root = root;
 	VM_MAP_ASSERT_CONSISTENT(map);
 	map->nentries--;
@@ -1206,22 +1255,24 @@
  *	The map must be locked, and leaves it so.
  */
 static void
-vm_map_entry_resize_free(vm_map_t map, vm_map_entry_t entry)
+vm_map_entry_resize_free(vm_map_t map, vm_map_entry_t entry, size_t grow_amount)
 {
 	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);
+	VM_MAP_ASSERT_CONSISTENT(map);
+	llist = rlist = &map->header;
+	root = vm_map_splay_split(entry->start, 0, map->root, &llist, &rlist);
 	KASSERT(root != NULL,
 	    ("vm_map_entry_resize_free: resize_free object not mapped"));
 	vm_map_splay_findnext(root, &rlist);
 	root->right = NULL;
-	map->root = vm_map_splay_merge(root, llist, rlist,
-	    root->left, root->right);
+	entry->end += grow_amount;
+	vm_map_splay_merge(root, llist, rlist);
+	map->root = root;
 	VM_MAP_ASSERT_CONSISTENT(map);
-	CTR3(KTR_VM, "vm_map_entry_resize_free: map %p, nentries %d, entry %p", map,
-	    map->nentries, entry);
+	CTR3(KTR_VM, "vm_map_entry_resize_free: map %p, nentries %d, entry %p",
+            map, map->nentries, entry);
 }
 
 /*
@@ -1264,8 +1315,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_entry_splay(address, map);
 		if (!locked)
 			sx_downgrade(&map->lock);
 
@@ -1438,8 +1488,8 @@
 			    prev_entry));
 			if ((prev_entry->eflags & MAP_ENTRY_GUARD) == 0)
 				map->size += end - prev_entry->end;
-			prev_entry->end = end;
-			vm_map_entry_resize_free(map, prev_entry);
+			vm_map_entry_resize_free(map, prev_entry,
+			    end - prev_entry->end);
 			vm_map_simplify_entry(map, prev_entry);
 			return (KERN_SUCCESS);
 		}
@@ -1549,11 +1599,12 @@
 	 * 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);
+	VM_MAP_ASSERT_CONSISTENT(map);
+	llist = rlist = &map->header;
+	root = vm_map_splay_split(start, length, map->root, &llist, &rlist);
 	if (root != NULL)
 		start = root->end;
-	else if (rlist != NULL) {
+	else if ((rlist->eflags & MAP_ENTRY_HEADER) == 0) {
 		root = rlist;
 		rlist = root->left;
 		root->left = NULL;
@@ -1562,8 +1613,8 @@
 		llist = root->right;
 		root->right = NULL;
 	}
-	map->root = vm_map_splay_merge(root, llist, rlist,
-	    root->left, root->right);
+	vm_map_splay_merge(root, llist, rlist);
+	map->root = root;
 	VM_MAP_ASSERT_CONSISTENT(map);
 	if (start + length <= root->start)
 		return (start);
@@ -1584,39 +1635,33 @@
 	/*
 	 * Splay for the least large-enough gap in the right subtree.
 	 */
-	llist = NULL;
-        rlist = NULL;
+	llist = rlist = &map->header;
 	for (left_length = 0; ;
-	     left_length = root->left != NULL ?
-	     root->left->max_free : root->start - llist->end) {
+	     left_length = vm_map_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));
+			SPLAY_LEFT_STEP(root, y, llist, rlist,
+			    length <= vm_map_max_free_left(y, llist));
 		else
-			SPLAY_RIGHT_STEP(root, y, llist,
-			    length > (y->left != NULL ?
-			    y->left->max_free : y->start - root->end));
+			SPLAY_RIGHT_STEP(root, y, llist, rlist,
+			    length > vm_map_max_free_left(y, root));
 		if (root == NULL)
 			break;
 	}
 	root = llist;
 	llist = root->right;
-	if ((y = rlist) == NULL)
+	if (rlist == &map->header)
 		root->right = NULL;
 	else {
+		y = rlist;
 		rlist = y->left;
+		vm_map_splay_merge(y, &map->header, rlist);
 		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);
+		y->max_free = MAX(
+		    vm_map_max_free_left(y, root),
+		    vm_map_max_free_right(y, &map->header));
 		root->right = y;
-		vm_map_entry_set_max_free(root);
 	}
+	vm_map_splay_merge(root, llist, &map->header);
 	map->root = root;
 	VM_MAP_ASSERT_CONSISTENT(map);
 	return (root->end);
@@ -2079,8 +2124,6 @@
 	*new_entry = *entry;
 
 	new_entry->end = start;
-	entry->offset += (start - entry->start);
-	entry->start = start;
 	if (new_entry->cred != NULL)
 		crhold(entry->cred);
 
@@ -2161,7 +2204,7 @@
 	new_entry = vm_map_entry_create(map);
 	*new_entry = *entry;
 
-	new_entry->start = entry->end = end;
+	new_entry->start = end;
 	new_entry->offset += (end - entry->start);
 	if (new_entry->cred != NULL)
 		crhold(entry->cred);
@@ -4192,25 +4235,20 @@
 			gap_deleted = true;
 		} else {
 			MPASS(gap_entry->start < gap_entry->end - grow_amount);
-			gap_entry->end -= grow_amount;
-			vm_map_entry_resize_free(map, gap_entry);
+			vm_map_entry_resize_free(map, gap_entry, -grow_amount);
 			gap_deleted = false;
 		}
 		rv = vm_map_insert(map, NULL, 0, grow_start,
 		    grow_start + grow_amount,
 		    stack_entry->protection, stack_entry->max_protection,
 		    MAP_STACK_GROWS_DOWN);
-		if (rv != KERN_SUCCESS) {
-			if (gap_deleted) {
-				rv1 = vm_map_insert(map, NULL, 0, gap_start,
-				    gap_end, VM_PROT_NONE, VM_PROT_NONE,
-				    MAP_CREATE_GUARD | MAP_CREATE_STACK_GAP_DN);
-				MPASS(rv1 == KERN_SUCCESS);
-			} else {
-				gap_entry->end += grow_amount;
-				vm_map_entry_resize_free(map, gap_entry);
-			}
-		}
+		if (rv != KERN_SUCCESS && gap_deleted) {
+			rv1 = vm_map_insert(map, NULL, 0, gap_start,
+			    gap_end, VM_PROT_NONE, VM_PROT_NONE,
+			    MAP_CREATE_GUARD | MAP_CREATE_STACK_GAP_DN);
+			MPASS(rv1 == KERN_SUCCESS);
+		} else if (rv != KERN_SUCCESS)
+			vm_map_entry_resize_free(map, gap_entry, grow_amount);
 	} else {
 		grow_start = stack_entry->end;
 		cred = stack_entry->cred;
@@ -4224,13 +4262,15 @@
 		    stack_entry->offset,
 		    (vm_size_t)(stack_entry->end - stack_entry->start),
 		    (vm_size_t)grow_amount, cred != NULL)) {
-			if (gap_entry->start + grow_amount == gap_entry->end)
+			if (gap_entry->start + grow_amount == gap_entry->end) {
 				vm_map_entry_delete(map, gap_entry);
-			else
+				vm_map_entry_resize_free(map, stack_entry,
+				    grow_amount);
+			} else {
 				gap_entry->start += grow_amount;
-			stack_entry->end += grow_amount;
+				stack_entry += grow_amount;
+			}
 			map->size += grow_amount;
-			vm_map_entry_resize_free(map, stack_entry);
 			rv = KERN_SUCCESS;
 		} else
 			rv = KERN_FAILURE;