Index: vm_map.c
===================================================================
--- vm_map.c
+++ vm_map.c
@@ -956,55 +956,68 @@
 /*
  *	vm_map_entry_set_max_free:
  *
- *	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;					\
-} while (0)
+static inline vm_size_t
+vm_map_entry_max_free_right(vm_map_entry_t root, vm_map_entry_t right_ancestor)
+{
 
-#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;					\
+	return (root->right != NULL ?
+	    root->right->max_free : right_ancestor->start - root->end);
+}
+
+#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_entry_max_free_left(root, y),	\
+			    vm_map_entry_max_free_right(root, rlist));	\
+		y->max_free = root->max_free;				\
+		root = y;						\
+		y = root->left;						\
+	} else if (root->max_free == vm_map_entry_max_free_left(root, llist)) \
+		root->max_free = vm_map_entry_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, 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_entry_max_free_left(root, llist),	\
+			    vm_map_entry_max_free_right(root, y));	\
+		y->max_free = root->max_free;				\
+		root = y;						\
+		y = root->right;					\
+	} else if (root->max_free == vm_map_entry_max_free_right(root, rlist)) \
+		root->max_free = vm_map_entry_max_free_left(root, llist); \
+	/* Put root on llist. */					\
+	root->right = llist;						\
+	llist = root;							\
+	root = y;							\
+ } 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
@@ -1015,49 +1028,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;
 }
 
@@ -1065,40 +1080,48 @@
  * 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_entry_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_entry_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_entry_max_free_left(root, llist),
+	    vm_map_entry_max_free_right(root, rlist));
 }
 
 /*
- *	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
@@ -1115,14 +1138,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_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.
@@ -1130,7 +1155,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.
@@ -1142,8 +1167,10 @@
 		/* There is no root. */
 		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);
 }
 
 /*
@@ -1161,15 +1188,40 @@
 	    "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_entry_max_free_left(root, llist))
+			root->max_free =
+			    vm_map_entry_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_entry_max_free_right(root, rlist))
+			root->max_free =
+			    vm_map_entry_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);
 }
@@ -1188,12 +1240,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"));
 
@@ -1218,11 +1267,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;
@@ -1230,9 +1279,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--;
@@ -1256,15 +1307,16 @@
 	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;
 	entry->end += grow_amount;
-	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);
 	CTR3(KTR_VM, "vm_map_entry_resize_free: map %p, nentries %d, entry %p",
             map, map->nentries, entry);
@@ -1310,8 +1362,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);
 
@@ -1598,11 +1649,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;
@@ -1611,8 +1663,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);
@@ -1633,39 +1685,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_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));
+			SPLAY_LEFT_STEP(root, y, llist, rlist,
+			    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));
+			SPLAY_RIGHT_STEP(root, y, llist, rlist,
+			    length > vm_map_entry_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_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);
 	}
+	vm_map_splay_merge(root, llist, &map->header);
 	map->root = root;
 	VM_MAP_ASSERT_CONSISTENT(map);
 	return (root->end);
@@ -2128,8 +2174,6 @@
 	*new_entry = *entry;
 
 	new_entry->end = start;
-	entry->offset += (start - entry->start);
-	entry->start = start;
 	if (new_entry->cred != NULL)
 		crhold(entry->cred);
 
@@ -2211,7 +2255,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);