Index: sys/vm/vm_map.h
===================================================================
--- sys/vm/vm_map.h
+++ sys/vm/vm_map.h
@@ -106,7 +106,6 @@
 	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 */
Index: sys/vm/vm_map.c
===================================================================
--- sys/vm/vm_map.c
+++ sys/vm/vm_map.c
@@ -869,12 +869,13 @@
 static inline void
 vm_map_entry_set_max_free(vm_map_entry_t entry)
 {
+	vm_size_t max_left, max_right;
 
-	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;
+	max_left = (entry->left != NULL) ? entry->left->max_free :
+	    entry->start - entry->prev->end;
+	max_right = (entry->right != NULL) ? entry->right->max_free :
+		entry->next->start - entry->end;
+	entry->max_free = MAX(max_left, max_right);
 }
 
 /*
@@ -996,40 +997,43 @@
  */
 static void
 vm_map_entry_link(vm_map_t map,
-		  vm_map_entry_t after_where,
+		  vm_map_entry_t prev,
 		  vm_map_entry_t entry)
 {
+	vm_map_entry_t next = prev->next;
 
 	CTR4(KTR_VM,
 	    "vm_map_entry_link: map %p, nentries %d, entry %p, after %p", map,
-	    map->nentries, entry, after_where);
+	    map->nentries, entry, prev);
 	VM_MAP_ASSERT_LOCKED(map);
-	KASSERT(after_where->end <= entry->start,
+	KASSERT(prev->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,
+	    (uintmax_t)prev->end, (uintmax_t)entry->start));
+	KASSERT(entry->end <= next->start,
 	    ("vm_map_entry_link: new end %jx next start %jx overlap",
-	    (uintmax_t)entry->end, (uintmax_t)after_where->next->start));
+	    (uintmax_t)entry->end, (uintmax_t)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->prev = prev;
+	entry->next = next;
+	next->prev = entry;
+	prev->next = entry;
+
+	if (prev != &map->header) {
+		entry->left = vm_map_entry_splay(prev->start, map->root);
+		map->root = prev->right;
+		prev->right = NULL;
+		vm_map_entry_set_max_free(prev);
+	}
+	else
 		entry->left = NULL;
+
+	if (next != &map->header) {
+		entry->right = vm_map_entry_splay(next->start, map->root);
+		vm_map_entry_set_max_free(next);
 	}
-	entry->adj_free = entry->next->start - entry->end;
+	else
+		entry->right = NULL;
 	vm_map_entry_set_max_free(entry);
 	map->root = entry;
 }
@@ -1043,20 +1047,19 @@
 	VM_MAP_ASSERT_LOCKED(map);
 	if (entry != map->root)
 		vm_map_entry_splay(entry->start, map->root);
-	if (entry->left == NULL)
-		root = entry->right;
+	prev = entry->prev;
+	next = entry->next;
+	next->prev = prev;
+	prev->next = next;
+	if (prev == &map->header)
+		root = vm_map_entry_splay(entry->start, entry->right);
 	else {
 		root = vm_map_entry_splay(entry->start, entry->left);
-		root->right = entry->right;
-		root->adj_free = entry->next->start - root->end;
+		root->right = vm_map_entry_splay(entry->start, entry->right);
 		vm_map_entry_set_max_free(root);
 	}
 	map->root = root;
 
-	prev = entry->prev;
-	next = entry->next;
-	next->prev = prev;
-	prev->next = next;
 	map->nentries--;
 	CTR3(KTR_VM, "vm_map_entry_unlink: map %p, nentries %d, entry %p", map,
 	    map->nentries, entry);
@@ -1084,7 +1087,6 @@
 	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);
 }
 
@@ -1381,11 +1383,11 @@
  *	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.
  *
@@ -1397,7 +1399,6 @@
     vm_offset_t *addr)	/* OUT */
 {
 	vm_map_entry_t entry;
-	vm_offset_t st;
 
 	/*
 	 * Request must fit within min/max VM address and must avoid
@@ -1428,14 +1429,15 @@
 	 * 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;
+	entry = map->root;
+	start = MAX(start, entry->end);
+	if (length <= entry->next->start - start) {
+		*addr = start;
 		return (0);
 	}
 
 	/* With max_free, can immediately tell if no solution. */
-	entry = map->root->right;
+	entry = entry->right;
 	if (entry == NULL || length > entry->max_free)
 		return (1);
 
@@ -1447,11 +1449,16 @@
 	while (entry != NULL) {
 		if (entry->left != NULL && entry->left->max_free >= length)
 			entry = entry->left;
-		else if (entry->adj_free >= length) {
-			*addr = entry->end;
+		else if (entry->left == NULL &&
+		    entry->start - entry->prev->end >= length) {
+			*addr = entry->prev->end;
 			return (0);
-		} else
+		} else if (entry->right != NULL)
 			entry = entry->right;
+		else {
+			*addr = entry->end;
+			return (0);
+		}
 	}
 
 	/* Can't get here, so panic if we do. */