Index: sys/vm/vm_object.c
===================================================================
--- sys/vm/vm_object.c
+++ sys/vm/vm_object.c
@@ -1101,14 +1101,14 @@
 {
 	vm_pindex_t tpindex;
 	vm_object_t backing_object, tobject;
-	vm_page_t m;
+	vm_page_t m, tm;
 
 	if (object == NULL)
 		return;
 
-	VM_OBJECT_WLOCK(object);
-	for (m = NULL; pindex < end; pindex++) {
 relookup:
+	VM_OBJECT_WLOCK(object);
+	for (m = vm_page_find_least(object, pindex); pindex < end; pindex++) {
 		tobject = object;
 		tpindex = pindex;
 shadowlookup:
@@ -1120,81 +1120,91 @@
 			if ((tobject->type != OBJT_DEFAULT &&
 			     tobject->type != OBJT_SWAP) ||
 			    (tobject->flags & OBJ_ONEMAPPING) == 0) {
-				goto unlock_tobject;
+				goto next_pindex;
 			}
 		} else if ((tobject->flags & OBJ_UNMANAGED) != 0)
-			goto unlock_tobject;
+			goto next_pindex;
 
 		/*
-		 * In the common case where the object has no backing object, we
-		 * can avoid performing lookups at each pindex.  In either case,
-		 * when applying MADV_FREE we take care to release any swap
-		 * space used to store non-resident pages.
+		 * If the next page isn't resident in the top-level object, we
+		 * need to search the shadow chain.  When applying MADV_FREE, we
+		 * take care to release any swap space used to store
+		 * non-resident pages.
 		 */
-		if (object->backing_object == NULL) {
-			m = (m != NULL) ? TAILQ_NEXT(m, listq) :
-			    vm_page_find_least(object, pindex);
-			tpindex = (m != NULL && m->pindex < end) ?
-			    m->pindex : end;
-			if (advice == MADV_FREE && object->type == OBJT_SWAP &&
-			    tpindex > pindex)
-				swap_pager_freespace(object, pindex,
-				    tpindex - pindex);
-			if ((pindex = tpindex) == end)
-				break;
-		} else if ((m = vm_page_lookup(tobject, tpindex)) == NULL) {
+		if (m == NULL || tpindex < m->pindex) {
+			/*
+			 * Optimize a common special case: if the top-level
+			 * object has no backing object, we can skip over the
+			 * non-resident range in constant time.
+			 */
+			if (object->backing_object == NULL) {
+				tpindex = (m != NULL && m->pindex < end) ?
+				    m->pindex : end;
+				if (advice == MADV_FREE &&
+				    object->type == OBJT_SWAP)
+					swap_pager_freespace(object, pindex,
+					    tpindex - pindex);
+				if ((pindex = tpindex) == end)
+					break;
+				goto next_page;
+			}
+
 			if (advice == MADV_FREE && tobject->type == OBJT_SWAP)
 				swap_pager_freespace(tobject, tpindex, 1);
+
 			/*
 			 * Prepare to search the next object in the chain.
 			 */
 			backing_object = tobject->backing_object;
 			if (backing_object == NULL)
-				goto unlock_tobject;
+				goto next_pindex;
 			VM_OBJECT_WLOCK(backing_object);
 			tpindex += OFF_TO_IDX(tobject->backing_object_offset);
 			if (tobject != object)
 				VM_OBJECT_WUNLOCK(tobject);
 			tobject = backing_object;
+			m = vm_page_lookup(tobject, tpindex);
 			goto shadowlookup;
+		} else {
+next_page:
+			tm = m;
+			m = TAILQ_NEXT(m, listq);
 		}
 
 		/*
 		 * If the page is not in a normal state, skip it.
 		 */
-		if (m->valid != VM_PAGE_BITS_ALL)
-			goto unlock_tobject;
-		vm_page_lock(m);
-		if (m->hold_count != 0 || m->wire_count != 0) {
-			vm_page_unlock(m);
-			goto unlock_tobject;
+		if (tm->valid != VM_PAGE_BITS_ALL)
+			goto next_pindex;
+		vm_page_lock(tm);
+		if (tm->hold_count != 0 || tm->wire_count != 0) {
+			vm_page_unlock(tm);
+			goto next_pindex;
 		}
-		KASSERT((m->flags & PG_FICTITIOUS) == 0,
-		    ("vm_object_madvise: page %p is fictitious", m));
-		KASSERT((m->oflags & VPO_UNMANAGED) == 0,
-		    ("vm_object_madvise: page %p is not managed", m));
-		if (vm_page_busied(m)) {
+		KASSERT((tm->flags & PG_FICTITIOUS) == 0,
+		    ("vm_object_madvise: page %p is fictitious", tm));
+		KASSERT((tm->oflags & VPO_UNMANAGED) == 0,
+		    ("vm_object_madvise: page %p is not managed", tm));
+		if (vm_page_busied(tm)) {
+			if (object != tobject)
+				VM_OBJECT_WUNLOCK(tobject);
+			VM_OBJECT_WUNLOCK(object);
 			if (advice == MADV_WILLNEED) {
 				/*
 				 * Reference the page before unlocking and
 				 * sleeping so that the page daemon is less
-				 * likely to reclaim it. 
+				 * likely to reclaim it.
 				 */
-				vm_page_aflag_set(m, PGA_REFERENCED);
+				vm_page_aflag_set(tm, PGA_REFERENCED);
 			}
-			if (object != tobject)
-				VM_OBJECT_WUNLOCK(object);
-			VM_OBJECT_WUNLOCK(tobject);
-			vm_page_busy_sleep(m, "madvpo", false);
-			m = NULL;
-			VM_OBJECT_WLOCK(object);
+			vm_page_busy_sleep(tm, "madvpo", false);
   			goto relookup;
 		}
-		vm_page_advise(m, advice);
-		vm_page_unlock(m);
+		vm_page_advise(tm, advice);
+		vm_page_unlock(tm);
 		if (advice == MADV_FREE && tobject->type == OBJT_SWAP)
 			swap_pager_freespace(tobject, tpindex, 1);
-unlock_tobject:
+next_pindex:
 		if (tobject != object)
 			VM_OBJECT_WUNLOCK(tobject);
 	}