Index: sys/vm/vm_kern.c
===================================================================
--- sys/vm/vm_kern.c
+++ sys/vm/vm_kern.c
@@ -332,7 +332,7 @@
 kmem_back(vm_object_t object, vm_offset_t addr, vm_size_t size, int flags)
 {
 	vm_offset_t offset, i;
-	vm_page_t m;
+	vm_page_t m, mpred;
 	int pflags;
 
 	KASSERT(object == kmem_object || object == kernel_object,
@@ -341,10 +341,15 @@
 	offset = addr - VM_MIN_KERNEL_ADDRESS;
 	pflags = malloc2vm_flags(flags) | VM_ALLOC_NOBUSY | VM_ALLOC_WIRED;
 
-	VM_OBJECT_WLOCK(object);
-	for (i = 0; i < size; i += PAGE_SIZE) {
+	i = 0;
 retry:
-		m = vm_page_alloc(object, atop(offset + i), pflags);
+	VM_OBJECT_WLOCK(object);
+	for (mpred = NULL; i < size; i += PAGE_SIZE, mpred = m) {
+		if (mpred != NULL)
+			m = vm_page_alloc_after(object, mpred, atop(offset + i),
+			    pflags);
+		else
+			m = vm_page_alloc(object, atop(offset + i), pflags);
 
 		/*
 		 * Ran out of space, free everything up and return. Don't need
@@ -355,7 +360,6 @@
 			VM_OBJECT_WUNLOCK(object);
 			if ((flags & M_NOWAIT) == 0) {
 				VM_WAIT;
-				VM_OBJECT_WLOCK(object);
 				goto retry;
 			}
 			kmem_unback(object, addr, i);
Index: sys/vm/vm_page.h
===================================================================
--- sys/vm/vm_page.h
+++ sys/vm/vm_page.h
@@ -480,7 +480,8 @@
 
 void vm_page_activate (vm_page_t);
 void vm_page_advise(vm_page_t m, int advice);
-vm_page_t vm_page_alloc (vm_object_t, vm_pindex_t, int);
+vm_page_t vm_page_alloc(vm_object_t, vm_pindex_t, int);
+vm_page_t vm_page_alloc_after(vm_object_t, vm_page_t, vm_pindex_t, int);
 vm_page_t vm_page_alloc_contig(vm_object_t object, vm_pindex_t pindex, int req,
     u_long npages, vm_paddr_t low, vm_paddr_t high, u_long alignment,
     vm_paddr_t boundary, vm_memattr_t memattr);
Index: sys/vm/vm_page.c
===================================================================
--- sys/vm/vm_page.c
+++ sys/vm/vm_page.c
@@ -1540,15 +1540,32 @@
 vm_page_t
 vm_page_alloc(vm_object_t object, vm_pindex_t pindex, int req)
 {
-	vm_page_t m, mpred;
+
+	return (vm_page_alloc_after(object, object != NULL ?
+	    vm_radix_lookup_le(&object->rtree, pindex) : NULL, pindex, req));
+}
+
+/*
+ * Allocate a page in the specified object with the given page index.  To
+ * optimize insertion of the page into the object, the caller must also specifiy
+ * the resident page in the object with largest index smaller than the given
+ * page index, or NULL if no such page exists.
+ */
+vm_page_t
+vm_page_alloc_after(vm_object_t object, vm_page_t mpred, vm_pindex_t pindex,
+    int req)
+{
+	vm_page_t m;
 	int flags, req_class;
 
-	mpred = NULL;	/* XXX: pacify gcc */
 	KASSERT((object != NULL) == ((req & VM_ALLOC_NOOBJ) == 0) &&
 	    (object != NULL || (req & VM_ALLOC_SBUSY) == 0) &&
 	    ((req & (VM_ALLOC_NOBUSY | VM_ALLOC_SBUSY)) !=
 	    (VM_ALLOC_NOBUSY | VM_ALLOC_SBUSY)),
-	    ("vm_page_alloc: inconsistent object(%p)/req(%x)", object, req));
+	    ("inconsistent object(%p)/req(%x)", object, req));
+	KASSERT(mpred == NULL || mpred->pindex < pindex,
+	    ("mpred %p doesn't precede pindex 0x%jx", mpred,
+	    (uintmax_t)pindex));
 	if (object != NULL)
 		VM_OBJECT_ASSERT_WLOCKED(object);
 
@@ -1560,12 +1577,6 @@
 	if (curproc == pageproc && req_class != VM_ALLOC_INTERRUPT)
 		req_class = VM_ALLOC_SYSTEM;
 
-	if (object != NULL) {
-		mpred = vm_radix_lookup_le(&object->rtree, pindex);
-		KASSERT(mpred == NULL || mpred->pindex != pindex,
-		   ("vm_page_alloc: pindex already allocated"));
-	}
-
 	/*
 	 * Allocate a page if the number of free pages exceeds the minimum
 	 * for the request class.
@@ -1612,7 +1623,7 @@
 	/*
 	 *  At this point we had better have found a good page.
 	 */
-	KASSERT(m != NULL, ("vm_page_alloc: missing page"));
+	KASSERT(m != NULL, ("missing page"));
 	vm_phys_freecnt_adj(m, -1);
 	mtx_unlock(&vm_page_queue_free_mtx);
 	vm_page_alloc_check(m);
@@ -3181,7 +3192,7 @@
     vm_page_t *ma, int count)
 {
 	vm_page_t m;
-	int i;
+	int i, newflags;
 	bool sleep;
 
 	VM_OBJECT_ASSERT_WLOCKED(object);
@@ -3227,8 +3238,13 @@
 			if ((allocflags & VM_ALLOC_SBUSY) != 0)
 				vm_page_sbusy(m);
 		} else {
-			m = vm_page_alloc(object, pindex + i, (allocflags &
-			    ~VM_ALLOC_IGN_SBUSY) | VM_ALLOC_COUNT(count - i));
+			newflags = (allocflags & ~VM_ALLOC_IGN_SBUSY) |
+			    VM_ALLOC_COUNT(count - i);
+			if (i > 0)
+				m = vm_page_alloc_after(object, ma[i - 1],
+				    pindex + i, newflags);
+			else
+				m = vm_page_alloc(object, pindex + i, newflags);
 			if (m == NULL) {
 				VM_OBJECT_WUNLOCK(object);
 				VM_WAIT;