3 files changed, 406 insertions, 250 deletions

diff --git a/sys/vm/vm_kern.c b/sys/vm/vm_kern.c
index 05b3669449eb..ac87a40a3b81 100644
--- a/sys/vm/vm_kern.c
+++ b/sys/vm/vm_kern.c
@@ -641,7 +641,8 @@ kmap_alloc_wait(vm_map_t map, vm_size_t size)
 		 * to lock out sleepers/wakers.
 		 */
 		vm_map_lock(map);
-		if (vm_map_findspace(map, vm_map_min(map), size, &addr) == 0)
+		addr = vm_map_findspace(map, vm_map_min(map), size);
+		if (addr + size <= vm_map_max(map))
 			break;
 		/* no space now; see if we can ever get space */
 		if (vm_map_max(map) - vm_map_min(map) < size) {
diff --git a/sys/vm/vm_map.c b/sys/vm/vm_map.c
index 346a6c162497..b799b517e49a 100644
--- a/sys/vm/vm_map.c
+++ b/sys/vm/vm_map.c
@@ -132,9 +132,6 @@ static int vmspace_zinit(void *mem, int size, int flags);
 static int vm_map_zinit(void *mem, int ize, int flags);
 static void _vm_map_init(vm_map_t map, pmap_t pmap, vm_offset_t min,
     vm_offset_t max);
-static int vm_map_alignspace(vm_map_t map, vm_object_t object,
-    vm_ooffset_t offset, vm_offset_t *addr, vm_size_t length,
-    vm_offset_t max_addr, vm_offset_t alignment);
 static void vm_map_entry_deallocate(vm_map_entry_t entry, boolean_t system_map);
 static void vm_map_entry_dispose(vm_map_t map, vm_map_entry_t entry);
 static void vm_map_entry_unwire(vm_map_t map, vm_map_entry_t entry);
@@ -672,8 +669,51 @@ _vm_map_assert_locked(vm_map_t map, const char *file, int line)
 
 #define	VM_MAP_ASSERT_LOCKED(map) \
     _vm_map_assert_locked(map, LOCK_FILE, LOCK_LINE)
+
+static void
+_vm_map_assert_consistent(vm_map_t map)
+{
+	vm_map_entry_t entry;
+	vm_map_entry_t child;
+	vm_size_t max_left, max_right;
+
+	for (entry = map->header.next; entry != &map->header;
+	    entry = entry->next) {
+		KASSERT(entry->prev->end <= entry->start,
+		    ("map %p prev->end = %jx, start = %jx", map,
+		    (uintmax_t)entry->prev->end, (uintmax_t)entry->start));
+		KASSERT(entry->start < entry->end,
+		    ("map %p start = %jx, end = %jx", map,
+		    (uintmax_t)entry->start, (uintmax_t)entry->end));
+		KASSERT(entry->end <= entry->next->start,
+		    ("map %p end = %jx, next->start = %jx", map,
+		    (uintmax_t)entry->end, (uintmax_t)entry->next->start));
+		KASSERT(entry->left == NULL ||
+		    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 ||
+		    entry->start < entry->right->start,
+		    ("map %p start = %jx, right->start = %jx", map,
+		    (uintmax_t)entry->start, (uintmax_t)entry->right->start));
+		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;
+		KASSERT(entry->max_free == 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));
+	}	
+}
+
+#define VM_MAP_ASSERT_CONSISTENT(map) \
+    _vm_map_assert_consistent(map)
 #else
 #define	VM_MAP_ASSERT_LOCKED(map)
+#define VM_MAP_ASSERT_CONSISTENT(map)
 #endif
 
 /*
@@ -865,100 +905,117 @@ vm_map_entry_set_behavior(vm_map_entry_t entry, u_char behavior)
 static inline void
 vm_map_entry_set_max_free(vm_map_entry_t entry)
 {
-
-	entry->max_free = entry->adj_free;
-	if (entry->left != NULL && entry->left->max_free > entry->max_free)
-		entry->max_free = entry->left->max_free;
-	if (entry->right != NULL && entry->right->max_free > entry->max_free)
-		entry->max_free = entry->right->max_free;
+	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);
 }
 
+#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)
+
+#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;					\
+} while (0)
+
 /*
- *	vm_map_entry_splay:
- *
- *	The Sleator and Tarjan top-down splay algorithm with the
- *	following variation.  Max_free must be computed bottom-up, so
- *	on the downward pass, maintain the left and right spines in
- *	reverse order.  Then, make a second pass up each side to fix
- *	the pointers and compute max_free.  The time bound is O(log n)
- *	amortized.
- *
- *	The new root is the vm_map_entry containing "addr", or else an
- *	adjacent entry (lower or higher) if addr is not in the tree.
- *
- *	The map must be locked, and leaves it so.
- *
- *	Returns: the new root.
+ * 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.
  */
 static vm_map_entry_t
-vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t root)
+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 llist, rlist;
-	vm_map_entry_t ltree, rtree;
 	vm_map_entry_t y;
 
-	/* Special case of empty tree. */
-	if (root == NULL)
-		return (root);
-
-	/*
-	 * Pass One: Splay down the tree until we find addr or a NULL
-	 * pointer where addr would go.  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.  Wait until Pass Two to set max_free on
-	 * the two spines.
-	 */
 	llist = NULL;
 	rlist = NULL;
-	for (;;) {
-		/* root is never NULL in here. */
+	while (root != NULL && root->max_free >= length) {
 		if (addr < root->start) {
-			y = root->left;
-			if (y == NULL)
-				break;
-			if (addr < y->start && y->left != NULL) {
-				/* Rotate right and put y on rlist. */
-				root->left = y->right;
-				y->right = root;
-				vm_map_entry_set_max_free(root);
-				root = y->left;
-				y->left = rlist;
-				rlist = y;
-			} else {
-				/* Put root on rlist. */
-				root->left = rlist;
-				rlist = root;
-				root = y;
-			}
+			SPLAY_LEFT_STEP(root, y, rlist,
+			    y->max_free >= length && addr < y->start);
 		} else if (addr >= root->end) {
-			y = root->right;
-			if (y == NULL)
-				break;
-			if (addr >= y->end && y->right != NULL) {
-				/* Rotate left and put y on llist. */
-				root->right = y->left;
-				y->left = root;
-				vm_map_entry_set_max_free(root);
-				root = y->right;
-				y->right = llist;
-				llist = y;
-			} else {
-				/* Put root on llist. */
-				root->right = llist;
-				llist = root;
-				root = y;
-			}
+			SPLAY_RIGHT_STEP(root, y, llist,
+			    y->max_free >= length && addr >= y->end);
 		} else
 			break;
 	}
+	*out_llist = llist;
+	*out_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;
+
+	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;
+}
+
+/*
+ * 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)
+{
+	vm_map_entry_t y;
 
-	/*
-	 * Pass Two: 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.
-	 */
-	ltree = root->left;
 	while (llist != NULL) {
 		y = llist->right;
 		llist->right = ltree;
@@ -966,7 +1023,6 @@ vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t root)
 		ltree = llist;
 		llist = y;
 	}
-	rtree = root->right;
 	while (rlist != NULL) {
 		y = rlist->left;
 		rlist->left = rtree;
@@ -986,73 +1042,143 @@ vm_map_entry_splay(vm_offset_t addr, vm_map_entry_t root)
 }
 
 /*
+ *	vm_map_entry_splay:
+ *
+ *	The Sleator and Tarjan top-down splay algorithm with the
+ *	following variation.  Max_free must be computed bottom-up, so
+ *	on the downward pass, maintain the left and right spines in
+ *	reverse order.  Then, make a second pass up each side to fix
+ *	the pointers and compute max_free.  The time bound is O(log n)
+ *	amortized.
+ *
+ *	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.
+ *
+ *	The map must be locked, and leaves it so.
+ *
+ *	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_t llist, rlist;
+
+	root = vm_map_splay_split(addr, 0, root, &llist, &rlist);
+	if (root != NULL) {
+		/* do nothing */
+	} else if (llist != NULL) {
+		/*
+		 * Recover the greatest node in the left
+		 * subtree and make it the root.
+		 */
+		root = llist;
+		llist = root->right;
+		root->right = NULL;
+	} else if (rlist != NULL) {
+		/*
+		 * Recover the least node in the right
+		 * subtree and make it the root.
+		 */
+		root = rlist;
+		rlist = root->left;
+		root->left = NULL;
+	} else {
+		/* There is no root. */
+		return (NULL);
+	}
+	return (vm_map_splay_merge(root, llist, rlist,
+	    root->left, root->right));
+}
+
+/*
  *	vm_map_entry_{un,}link:
  *
  *	Insert/remove entries from maps.
  */
 static void
 vm_map_entry_link(vm_map_t map,
-		  vm_map_entry_t after_where,
 		  vm_map_entry_t entry)
 {
+	vm_map_entry_t llist, rlist, root;
 
-	CTR4(KTR_VM,
-	    "vm_map_entry_link: map %p, nentries %d, entry %p, after %p", map,
-	    map->nentries, entry, after_where);
+	CTR3(KTR_VM,
+	    "vm_map_entry_link: map %p, nentries %d, entry %p", map,
+	    map->nentries, entry);
 	VM_MAP_ASSERT_LOCKED(map);
-	KASSERT(after_where->end <= entry->start,
-	    ("vm_map_entry_link: prev end %jx new start %jx overlap",
-	    (uintmax_t)after_where->end, (uintmax_t)entry->start));
-	KASSERT(entry->end <= after_where->next->start,
-	    ("vm_map_entry_link: new end %jx next start %jx overlap",
-	    (uintmax_t)entry->end, (uintmax_t)after_where->next->start));
-
 	map->nentries++;
-	entry->prev = after_where;
-	entry->next = after_where->next;
-	entry->next->prev = entry;
-	after_where->next = entry;
-
-	if (after_where != &map->header) {
-		if (after_where != map->root)
-			vm_map_entry_splay(after_where->start, map->root);
-		entry->right = after_where->right;
-		entry->left = after_where;
-		after_where->right = NULL;
-		after_where->adj_free = entry->start - after_where->end;
-		vm_map_entry_set_max_free(after_where);
-	} else {
-		entry->right = map->root;
-		entry->left = NULL;
-	}
-	entry->adj_free = entry->next->start - entry->end;
-	vm_map_entry_set_max_free(entry);
+	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);
 	map->root = entry;
+	VM_MAP_ASSERT_CONSISTENT(map);
 }
 
+enum unlink_merge_type {
+	UNLINK_MERGE_PREV,
+	UNLINK_MERGE_NONE,
+	UNLINK_MERGE_NEXT
+};
+
 static void
 vm_map_entry_unlink(vm_map_t map,
-		    vm_map_entry_t entry)
+		    vm_map_entry_t entry,
+		    enum unlink_merge_type op)
 {
-	vm_map_entry_t next, prev, root;
+	vm_map_entry_t llist, rlist, root, y;
 
 	VM_MAP_ASSERT_LOCKED(map);
-	if (entry != map->root)
-		vm_map_entry_splay(entry->start, map->root);
-	if (entry->left == NULL)
-		root = entry->right;
-	else {
-		root = vm_map_entry_splay(entry->start, entry->left);
-		root->right = entry->right;
-		root->adj_free = entry->next->start - root->end;
-		vm_map_entry_set_max_free(root);
+	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);
+	KASSERT(root != NULL,
+	    ("vm_map_entry_unlink: unlink object not mapped"));
+
+	switch (op) {
+	case UNLINK_MERGE_PREV:
+		vm_map_splay_findprev(root, &llist);
+		llist->end = root->end;
+		y = root->right;
+		root = llist;
+		llist = root->right;
+		root->right = y;
+		break;
+	case UNLINK_MERGE_NEXT:
+		vm_map_splay_findnext(root, &rlist);
+		rlist->start = root->start;
+		rlist->offset = root->offset;
+		y = root->left;
+		root = rlist;
+		rlist = root->left;
+		root->left = y;
+		break;
+	case UNLINK_MERGE_NONE:
+		vm_map_splay_findprev(root, &llist);
+		vm_map_splay_findnext(root, &rlist);
+		if (llist != NULL) {
+			root = llist;
+			llist = root->right;
+			root->right = NULL;
+		} else if (rlist != NULL) {
+			root = rlist;
+			rlist = root->left;
+			root->left = NULL;
+		} else
+			root = NULL;
+		break;
 	}
+	if (root != NULL)
+		root = vm_map_splay_merge(root, llist, rlist,
+		    root->left, root->right);
 	map->root = root;
-
-	prev = entry->prev;
-	next = entry->next;
-	next->prev = prev;
-	prev->next = next;
+	VM_MAP_ASSERT_CONSISTENT(map);
 	map->nentries--;
 	CTR3(KTR_VM, "vm_map_entry_unlink: map %p, nentries %d, entry %p", map,
 	    map->nentries, entry);
@@ -1061,27 +1187,30 @@ vm_map_entry_unlink(vm_map_t map,
 /*
  *	vm_map_entry_resize_free:
  *
- *	Recompute the amount of free space following a vm_map_entry
- *	and propagate that value up the tree.  Call this function after
- *	resizing a map entry in-place, that is, without a call to
- *	vm_map_entry_link() or _unlink().
+ *	Recompute the amount of free space following a modified vm_map_entry
+ *	and propagate those values up the tree.  Call this function after
+ *	resizing a map entry in-place by changing the end value, without a
+ *	call to vm_map_entry_link() or _unlink().
  *
  *	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_t llist, rlist, root;
 
-	/*
-	 * Using splay trees without parent pointers, propagating
-	 * max_free up the tree is done by moving the entry to the
-	 * root and making the change there.
-	 */
-	if (entry != map->root)
-		map->root = vm_map_entry_splay(entry->start, map->root);
-
-	entry->adj_free = entry->next->start - entry->end;
-	vm_map_entry_set_max_free(entry);
+	VM_MAP_ASSERT_LOCKED(map);
+	root = map->root;
+	root = vm_map_splay_split(entry->start, 0, 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);
+	VM_MAP_ASSERT_CONSISTENT(map);
+	CTR3(KTR_VM, "vm_map_entry_resize_free: map %p, nentries %d, entry %p", map,
+	    map->nentries, entry);
 }
 
 /*
@@ -1100,7 +1229,7 @@ vm_map_lookup_entry(
 	vm_offset_t address,
 	vm_map_entry_t *entry)	/* OUT */
 {
-	vm_map_entry_t cur;
+	vm_map_entry_t cur, lbound;
 	boolean_t locked;
 
 	/*
@@ -1108,12 +1237,15 @@ vm_map_lookup_entry(
 	 * "address" is the map's header.
 	 */
 	cur = map->root;
-	if (cur == NULL)
+	if (cur == NULL) {
 		*entry = &map->header;
-	else if (address >= cur->start && cur->end > address) {
+		return (FALSE);
+	}
+	if (address >= cur->start && cur->end > address) {
 		*entry = cur;
 		return (TRUE);
-	} else if ((locked = vm_map_locked(map)) ||
+	}
+	if ((locked = vm_map_locked(map)) ||
 	    sx_try_upgrade(&map->lock)) {
 		/*
 		 * Splay requires a write lock on the map.  However, it only
@@ -1122,6 +1254,7 @@ vm_map_lookup_entry(
 		 * on a temporary upgrade.
 		 */
 		map->root = cur = vm_map_entry_splay(address, cur);
+		VM_MAP_ASSERT_CONSISTENT(map);
 		if (!locked)
 			sx_downgrade(&map->lock);
 
@@ -1130,35 +1263,30 @@ vm_map_lookup_entry(
 		 * is that map entry.  Otherwise, the new root is a map entry
 		 * immediately before or after "address".
 		 */
-		if (address >= cur->start) {
+		if (address < cur->start) {
+			*entry = &map->header;
+			return (FALSE);
+		}
+		*entry = cur;
+		return (address < cur->end);
+	}
+	/*
+	 * Since the map is only locked for read access, perform a
+	 * standard binary search tree lookup for "address".
+	 */
+	lbound = &map->header;
+	do {
+		if (address < cur->start) {
+			cur = cur->left;
+		} else if (cur->end <= address) {
+			lbound = cur;
+			cur = cur->right;
+		} else {
 			*entry = cur;
-			if (cur->end > address)
-				return (TRUE);
-		} else
-			*entry = cur->prev;
-	} else
-		/*
-		 * Since the map is only locked for read access, perform a
-		 * standard binary search tree lookup for "address".
-		 */
-		for (;;) {
-			if (address < cur->start) {
-				if (cur->left == NULL) {
-					*entry = cur->prev;
-					break;
-				}
-				cur = cur->left;
-			} else if (cur->end > address) {
-				*entry = cur;
-				return (TRUE);
-			} else {
-				if (cur->right == NULL) {
-					*entry = cur;
-					break;
-				}
-				cur = cur->right;
-			}
+			return (TRUE);
 		}
+	} while (cur != NULL);
+	*entry = lbound;
 	return (FALSE);
 }
 
@@ -1351,7 +1479,7 @@ charged:
 	/*
 	 * Insert the new entry into the list
 	 */
-	vm_map_entry_link(map, prev_entry, new_entry);
+	vm_map_entry_link(map, new_entry);
 	if ((new_entry->eflags & MAP_ENTRY_GUARD) == 0)
 		map->size += new_entry->end - new_entry->start;
 
@@ -1377,23 +1505,22 @@ charged:
  *	Find the first fit (lowest VM address) for "length" free bytes
  *	beginning at address >= start in the given map.
  *
- *	In a vm_map_entry, "adj_free" is the amount of free space
- *	adjacent (higher address) to this entry, and "max_free" is the
- *	maximum amount of contiguous free space in its subtree.  This
- *	allows finding a free region in one path down the tree, so
- *	O(log n) amortized with splay trees.
+ *	In a vm_map_entry, "max_free" is the maximum amount of
+ *	contiguous free space between an entry in its subtree and a
+ *	neighbor of that entry.  This allows finding a free region in
+ *	one path down the tree, so O(log n) amortized with splay
+ *	trees.
  *
  *	The map must be locked, and leaves it so.
  *
- *	Returns: 0 on success, and starting address in *addr,
- *		 1 if insufficient space.
+ *	Returns: starting address if sufficient space,
+ *		 vm_map_max(map)-length+1 if insufficient space.
  */
-int
-vm_map_findspace(vm_map_t map, vm_offset_t start, vm_size_t length,
-    vm_offset_t *addr)	/* OUT */
+vm_offset_t
+vm_map_findspace(vm_map_t map, vm_offset_t start, vm_size_t length)
 {
-	vm_map_entry_t entry;
-	vm_offset_t st;
+	vm_map_entry_t llist, rlist, root, y;
+	vm_size_t left_length;
 
 	/*
 	 * Request must fit within min/max VM address and must avoid
@@ -1401,57 +1528,87 @@ vm_map_findspace(vm_map_t map, vm_offset_t start, vm_size_t length,
 	 */
 	start = MAX(start, vm_map_min(map));
 	if (start + length > vm_map_max(map) || start + length < start)
-		return (1);
+		return (vm_map_max(map) - length + 1);
 
 	/* Empty tree means wide open address space. */
-	if (map->root == NULL) {
-		*addr = start;
-		return (0);
-	}
+	if (map->root == NULL)
+		return (start);
 
 	/*
 	 * After splay, if start comes before root node, then there
 	 * must be a gap from start to the root.
 	 */
-	map->root = vm_map_entry_splay(start, map->root);
-	if (start + length <= map->root->start) {
-		*addr = start;
-		return (0);
+	root = vm_map_splay_split(start, length, map->root,
+	    &llist, &rlist);
+	if (root != NULL)
+		start = root->end;
+	else if (rlist != NULL) {
+		root = rlist;
+		rlist = root->left;
+		root->left = NULL;
+	} else {
+		root = llist;
+		llist = root->right;
+		root->right = NULL;
 	}
+	map->root = vm_map_splay_merge(root, llist, rlist,
+	    root->left, root->right);
+	VM_MAP_ASSERT_CONSISTENT(map);
+	if (start + length <= root->start)
+		return (start);
 
 	/*
 	 * Root is the last node that might begin its gap before
 	 * start, and this is the last comparison where address
 	 * wrap might be a problem.
 	 */
-	st = (start > map->root->end) ? start : map->root->end;
-	if (length <= map->root->end + map->root->adj_free - st) {
-		*addr = st;
-		return (0);
-	}
+	if (root->right == NULL &&
+	    start + length <= vm_map_max(map))
+		return (start);
 
 	/* With max_free, can immediately tell if no solution. */
-	entry = map->root->right;
-	if (entry == NULL || length > entry->max_free)
-		return (1);
+	if (root->right == NULL || length > root->right->max_free)
+		return (vm_map_max(map) - length + 1);
 
 	/*
-	 * Search the right subtree in the order: left subtree, root,
-	 * right subtree (first fit).  The previous splay implies that
-	 * all regions in the right subtree have addresses > start.
+	 * Splay for the least large-enough gap in the right subtree.
 	 */
-	while (entry != NULL) {
-		if (entry->left != NULL && entry->left->max_free >= length)
-			entry = entry->left;
-		else if (entry->adj_free >= length) {
-			*addr = entry->end;
-			return (0);
-		} else
-			entry = entry->right;
+	llist = NULL;
+        rlist = NULL;
+	for (left_length = 0; ;
+	     left_length = root->left != NULL ?
+	     root->left->max_free : root->start - llist->end) {
+		if (length <= left_length)
+			SPLAY_LEFT_STEP(root, y, rlist,
+			    length <= (y->left != NULL ?
+			    y->left->max_free : y->start - llist->end));
+		else
+			SPLAY_RIGHT_STEP(root, y, llist,
+			    length > (y->left != NULL ?
+			    y->left->max_free : y->start - root->end));
+		if (root == NULL)
+			break;
 	}
-
-	/* Can't get here, so panic if we do. */
-	panic("vm_map_findspace: max_free corrupt");
+	root = llist;
+	llist = root->right;
+	if ((y = rlist) == NULL)
+		root->right = NULL;
+	else {
+		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);
+		root->right = y;
+		vm_map_entry_set_max_free(root);
+	}
+	map->root = root;
+	VM_MAP_ASSERT_CONSISTENT(map);
+	return (root->end);
 }
 
 int
@@ -1532,8 +1689,9 @@ vm_map_alignspace(vm_map_t map, vm_object_t object, vm_ooffset_t offset,
 
 	VM_MAP_ASSERT_LOCKED(map);
 	free_addr = *addr;
-	KASSERT(!vm_map_findspace(map, free_addr, length, addr) &&
-	    free_addr == *addr, ("caller provided insufficient free space"));
+	KASSERT(free_addr == vm_map_findspace(map, free_addr, length),
+	    ("caller failed to provide space %d at address %p",
+	     (int)length, (void*)free_addr));
 	for (;;) {
 		/*
 		 * At the start of every iteration, the free space at address
@@ -1559,8 +1717,10 @@ vm_map_alignspace(vm_map_t map, vm_object_t object, vm_ooffset_t offset,
 		 * be a valid address, in which case vm_map_findspace() cannot
 		 * be relied upon to fail.
 		 */
-		if (aligned_addr < free_addr ||
-		    vm_map_findspace(map, aligned_addr, length, addr) ||
+		if (aligned_addr < free_addr)
+			return (KERN_NO_SPACE);
+		*addr = vm_map_findspace(map, aligned_addr, length);
+		if (*addr + length > vm_map_max(map) ||
 		    (max_addr != 0 && *addr + length > max_addr))
 			return (KERN_NO_SPACE);
 		free_addr = *addr;
@@ -1672,22 +1832,27 @@ again:
 			gap = vm_map_max(map) > MAP_32BIT_MAX_ADDR &&
 			    (max_addr == 0 || max_addr > MAP_32BIT_MAX_ADDR) ?
 			    aslr_pages_rnd_64[pidx] : aslr_pages_rnd_32[pidx];
-			if (vm_map_findspace(map, curr_min_addr, length +
-			    gap * pagesizes[pidx], addr))
+			*addr = vm_map_findspace(map, curr_min_addr,
+			    length + gap * pagesizes[pidx]);
+			if (*addr + length + gap * pagesizes[pidx] >
++			    vm_map_max(map))
 				goto again;
 			/* And randomize the start address. */
 			*addr += (arc4random() % gap) * pagesizes[pidx];
 			if (max_addr != 0 && *addr + length > max_addr)
 				goto again;
-		} else if (vm_map_findspace(map, curr_min_addr, length, addr) ||
-		    (max_addr != 0 && *addr + length > max_addr)) {
-			if (cluster) {
-				cluster = false;
-				MPASS(try == 1);
-				goto again;
+		} else {
+			*addr = vm_map_findspace(map, curr_min_addr, length);
+			if (*addr + length > vm_map_max(map) ||
+			    (max_addr != 0 && *addr + length > max_addr)) {
+				if (cluster) {
+					cluster = false;
+					MPASS(try == 1);
+					goto again;
+				}
+				rv = KERN_NO_SPACE;
+				goto done;
 			}
-			rv = KERN_NO_SPACE;
-			goto done;
 		}
 
 		if (find_space != VMFS_ANY_SPACE &&
@@ -1825,18 +1990,12 @@ vm_map_simplify_entry(vm_map_t map, vm_map_entry_t entry)
 		return;
 	prev = entry->prev;
 	if (vm_map_mergeable_neighbors(prev, entry)) {
-		vm_map_entry_unlink(map, prev);
-		entry->start = prev->start;
-		entry->offset = prev->offset;
-		if (entry->prev != &map->header)
-			vm_map_entry_resize_free(map, entry->prev);
+		vm_map_entry_unlink(map, prev, UNLINK_MERGE_NEXT);
 		vm_map_merged_neighbor_dispose(map, prev);
 	}
 	next = entry->next;
 	if (vm_map_mergeable_neighbors(entry, next)) {
-		vm_map_entry_unlink(map, next);
-		entry->end = next->end;
-		vm_map_entry_resize_free(map, entry);
+		vm_map_entry_unlink(map, next, UNLINK_MERGE_PREV);
 		vm_map_merged_neighbor_dispose(map, next);
 	}
 }
@@ -1914,7 +2073,7 @@ _vm_map_clip_start(vm_map_t map, vm_map_entry_t entry, vm_offset_t start)
 	if (new_entry->cred != NULL)
 		crhold(entry->cred);
 
-	vm_map_entry_link(map, entry->prev, new_entry);
+	vm_map_entry_link(map, new_entry);
 
 	if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0) {
 		vm_object_reference(new_entry->object.vm_object);
@@ -1996,7 +2155,7 @@ _vm_map_clip_end(vm_map_t map, vm_map_entry_t entry, vm_offset_t end)
 	if (new_entry->cred != NULL)
 		crhold(entry->cred);
 
-	vm_map_entry_link(map, entry, new_entry);
+	vm_map_entry_link(map, new_entry);
 
 	if ((entry->eflags & MAP_ENTRY_IS_SUB_MAP) == 0) {
 		vm_object_reference(new_entry->object.vm_object);
@@ -3132,7 +3291,7 @@ vm_map_entry_delete(vm_map_t map, vm_map_entry_t entry)
 	vm_pindex_t offidxstart, offidxend, count, size1;
 	vm_size_t size;
 
-	vm_map_entry_unlink(map, entry);
+	vm_map_entry_unlink(map, entry, UNLINK_MERGE_NONE);
 	object = entry->object.vm_object;
 
 	if ((entry->eflags & MAP_ENTRY_GUARD) != 0) {
@@ -3675,8 +3834,7 @@ vmspace_fork(struct vmspace *vm1, vm_ooffset_t *fork_charge)
 			 * Insert the entry into the new map -- we know we're
 			 * inserting at the end of the new map.
 			 */
-			vm_map_entry_link(new_map, new_map->header.prev,
-			    new_entry);
+			vm_map_entry_link(new_map, new_entry);
 			vmspace_map_entry_forked(vm1, vm2, new_entry);
 
 			/*
@@ -3703,8 +3861,7 @@ vmspace_fork(struct vmspace *vm1, vm_ooffset_t *fork_charge)
 			new_entry->wired_count = 0;
 			new_entry->object.vm_object = NULL;
 			new_entry->cred = NULL;
-			vm_map_entry_link(new_map, new_map->header.prev,
-			    new_entry);
+			vm_map_entry_link(new_map, new_entry);
 			vmspace_map_entry_forked(vm1, vm2, new_entry);
 			vm_map_copy_entry(old_map, new_map, old_entry,
 			    new_entry, fork_charge);
@@ -3727,8 +3884,7 @@ vmspace_fork(struct vmspace *vm1, vm_ooffset_t *fork_charge)
 			new_entry->max_protection = old_entry->max_protection;
 			new_entry->inheritance = VM_INHERIT_ZERO;
 
-			vm_map_entry_link(new_map, new_map->header.prev,
-			    new_entry);
+			vm_map_entry_link(new_map, new_entry);
 			vmspace_map_entry_forked(vm1, vm2, new_entry);
 
 			new_entry->cred = curthread->td_ucred;
diff --git a/sys/vm/vm_map.h b/sys/vm/vm_map.h
index 6e0f37293280..307d693a791e 100644
--- a/sys/vm/vm_map.h
+++ b/sys/vm/vm_map.h
@@ -106,7 +106,6 @@ struct vm_map_entry {
 	vm_offset_t start;		/* start address */
 	vm_offset_t end;		/* end address */
 	vm_offset_t next_read;		/* vaddr of the next sequential read */
-	vm_size_t adj_free;		/* amount of adjacent free space */
 	vm_size_t max_free;		/* max free space in subtree */
 	union vm_map_object object;	/* object I point to */
 	vm_ooffset_t offset;		/* offset into object */
@@ -402,7 +401,7 @@ int vm_map_find_min(vm_map_t, vm_object_t, vm_ooffset_t, vm_offset_t *,
     vm_size_t, vm_offset_t, vm_offset_t, int, vm_prot_t, vm_prot_t, int);
 int vm_map_fixed(vm_map_t, vm_object_t, vm_ooffset_t, vm_offset_t, vm_size_t,
     vm_prot_t, vm_prot_t, int);
-int vm_map_findspace (vm_map_t, vm_offset_t, vm_size_t, vm_offset_t *);
+vm_offset_t vm_map_findspace(vm_map_t, vm_offset_t, vm_size_t);
 int vm_map_inherit (vm_map_t, vm_offset_t, vm_offset_t, vm_inherit_t);
 void vm_map_init(vm_map_t, pmap_t, vm_offset_t, vm_offset_t);
 int vm_map_insert (vm_map_t, vm_object_t, vm_ooffset_t, vm_offset_t, vm_offset_t, vm_prot_t, vm_prot_t, int);