Index: sys/vm/vm_map.c
===================================================================
--- sys/vm/vm_map.c
+++ sys/vm/vm_map.c
@@ -917,36 +917,52 @@
 	entry->max_free = MAX(max_left, max_right);
 }
 
-#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, 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)			\
+			vm_map_entry_set_max_free(root);		\
+		root = y;						\
+		y = root->left;						\
+	}								\
+	/* Put root on rlist. */					\
+	root->left = rlist;						\
+	rlist = root;							\
+	root = y;							\
+	/* Make rlist->max_free match max_free for its right child. */	\
+	if (broken || rlist->max_free == ((root != NULL) ?			\
+	    root->max_free : rlist->start - rlist->prev->end)) {	\
+		y = rlist->right;					\
+		rlist->max_free = (y != NULL) ?				\
+		    y->max_free : rlist->next->start - rlist->end;	\
+	}								\
 } 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 {			\
+	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)			\
+			vm_map_entry_set_max_free(root);		\
+		root = y;						\
+		y = root->right;					\
+	}								\
+	/* Put root on llist. */					\
+	root->right = llist;						\
+	llist = root;							\
+	root = y;							\
+	/* Make llist->max_free match max_free for its left child. */	\
+	if (broken || llist->max_free == ((root != NULL) ?			\
+	    root->max_free : llist->next->start - llist->end)) {	\
+		y = llist->left;					\
+		llist->max_free = (y != NULL) ?				\
+		    y->max_free : llist->start - llist->prev->end;	\
+	}								\
 } while (0)
 
 /*
@@ -959,7 +975,7 @@
  */
 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 *out_llist, vm_map_entry_t *out_rlist, bool broken)
 {
 	vm_map_entry_t llist, rlist;
 	vm_map_entry_t y;
@@ -982,7 +998,7 @@
 }
 
 static void
-vm_map_splay_findnext(vm_map_entry_t root, vm_map_entry_t *iolist)
+vm_map_splay_findnext(vm_map_entry_t root, vm_map_entry_t *iolist, bool broken)
 {
 	vm_map_entry_t rlist, y;
 
@@ -994,7 +1010,7 @@
 }
 
 static void
-vm_map_splay_findprev(vm_map_entry_t root, vm_map_entry_t *iolist)
+vm_map_splay_findprev(vm_map_entry_t root, vm_map_entry_t *iolist, bool broken)
 {
 	vm_map_entry_t llist, y;
 
@@ -1015,18 +1031,31 @@
     vm_map_entry_t ltree, vm_map_entry_t rtree)
 {
 	vm_map_entry_t y;
+	vm_size_t max_free;
 
+	if (llist != NULL)
+		max_free = (ltree != NULL) ? ltree->max_free :
+		    llist->next->start - llist->end;
 	while (llist != NULL) {
 		y = llist->right;
 		llist->right = ltree;
-		vm_map_entry_set_max_free(llist);
+		if (llist->max_free < max_free)
+			llist->max_free = max_free;
+		else
+			max_free = llist->max_free;
 		ltree = llist;
 		llist = y;
 	}
+	if (rlist != NULL)
+		max_free = (rtree != NULL) ? rtree->max_free :
+		    rlist->start - rlist->prev->end;
 	while (rlist != NULL) {
 		y = rlist->left;
 		rlist->left = rtree;
-		vm_map_entry_set_max_free(rlist);
+		if (rlist->max_free < max_free)
+			rlist->max_free = max_free;
+		else
+			max_free = rlist->max_free;
 		rtree = rlist;
 		rlist = y;
 	}
@@ -1062,8 +1091,9 @@
 vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t root)
 {
 	vm_map_entry_t llist, rlist;
+	bool broken = false;
 
-	root = vm_map_splay_split(addr, 0, root, &llist, &rlist);
+	root = vm_map_splay_split(addr, 0, root, &llist, &rlist, broken);
 	if (root != NULL) {
 		/* do nothing */
 	} else if (llist != NULL) {
@@ -1100,6 +1130,7 @@
 		  vm_map_entry_t entry)
 {
 	vm_map_entry_t llist, rlist, root;
+	bool broken = false;
 
 	CTR3(KTR_VM,
 	    "vm_map_entry_link: map %p, nentries %d, entry %p", map,
@@ -1107,7 +1138,7 @@
 	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(entry->start, 0, root, &llist, &rlist, broken);
 	KASSERT(root == NULL,
 	    ("vm_map_entry_link: link object already mapped"));
 	entry->prev = (llist == NULL) ? &map->header : llist;
@@ -1130,20 +1161,17 @@
 		    enum unlink_merge_type op)
 {
 	vm_map_entry_t llist, rlist, root, y;
+	bool broken = true;
 
 	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(entry->start, 0, root, &llist, &rlist, broken);
 	KASSERT(root != NULL,
 	    ("vm_map_entry_unlink: unlink object not mapped"));
 
 	switch (op) {
 	case UNLINK_MERGE_PREV:
-		vm_map_splay_findprev(root, &llist);
+		vm_map_splay_findprev(root, &llist, broken);
 		llist->end = root->end;
 		y = root->right;
 		root = llist;
@@ -1151,7 +1179,7 @@
 		root->right = y;
 		break;
 	case UNLINK_MERGE_NEXT:
-		vm_map_splay_findnext(root, &rlist);
+		vm_map_splay_findnext(root, &rlist, broken);
 		rlist->start = root->start;
 		rlist->offset = root->offset;
 		y = root->left;
@@ -1160,8 +1188,8 @@
 		root->left = y;
 		break;
 	case UNLINK_MERGE_NONE:
-		vm_map_splay_findprev(root, &llist);
-		vm_map_splay_findnext(root, &rlist);
+		vm_map_splay_findprev(root, &llist, broken);
+		vm_map_splay_findnext(root, &rlist, broken);
 		if (llist != NULL) {
 			root = llist;
 			llist = root->right;
@@ -1174,6 +1202,9 @@
 			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);
@@ -1195,17 +1226,19 @@
  *	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, vm_offset_t addToEnd)
 {
 	vm_map_entry_t llist, rlist, root;
+	bool broken = true;
 
 	VM_MAP_ASSERT_LOCKED(map);
 	root = map->root;
-	root = vm_map_splay_split(entry->start, 0, root, &llist, &rlist);
+	root = vm_map_splay_split(entry->start, 0, root, &llist, &rlist, broken);
 	KASSERT(root != NULL,
 	    ("vm_map_entry_resize_free: resize_free object not mapped"));
-	vm_map_splay_findnext(root, &rlist);
+	vm_map_splay_findnext(root, &rlist, broken);
 	root->right = NULL;
+	entry->end += addToEnd;
 	map->root = vm_map_splay_merge(root, llist, rlist,
 	    root->left, root->right);
 	VM_MAP_ASSERT_CONSISTENT(map);
@@ -1427,8 +1460,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);
 		}
@@ -1521,6 +1554,7 @@
 {
 	vm_map_entry_t llist, rlist, root, y;
 	vm_size_t left_length;
+	bool broken = true;
 
 	/*
 	 * Request must fit within min/max VM address and must avoid
@@ -1539,7 +1573,7 @@
 	 * must be a gap from start to the root.
 	 */
 	root = vm_map_splay_split(start, length, map->root,
-	    &llist, &rlist);
+	    &llist, &rlist, broken);
 	if (root != NULL)
 		start = root->end;
 	else if (rlist != NULL) {
@@ -4181,25 +4215,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;
@@ -4213,13 +4242,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->end += grow_amount;
+				vm_map_entry_resize_free(map, stack_entry, 0);
+			}
 			map->size += grow_amount;
-			vm_map_entry_resize_free(map, stack_entry);
 			rv = KERN_SUCCESS;
 		} else
 			rv = KERN_FAILURE;