svn commit: r227420 - stable/9/sys/vm

[Alan Cox]

Author: alc
Date: Thu Nov 10 16:50:36 2011
New Revision: 227420
URL: http://svn.freebsd.org/changeset/base/227420

Log:
  MFC r226740
    Speed up vm_page_cache() and vm_page_remove() by checking for a few
    common cases that can be handled in constant time.
  
  Approved by:	re (kib)

Modified:
  stable/9/sys/vm/vm_page.c
Directory Properties:
  stable/9/sys/   (props changed)
  stable/9/sys/amd64/include/xen/   (props changed)
  stable/9/sys/boot/   (props changed)
  stable/9/sys/boot/i386/efi/   (props changed)
  stable/9/sys/boot/ia64/efi/   (props changed)
  stable/9/sys/boot/ia64/ski/   (props changed)
  stable/9/sys/boot/powerpc/boot1.chrp/   (props changed)
  stable/9/sys/boot/powerpc/ofw/   (props changed)
  stable/9/sys/cddl/contrib/opensolaris/   (props changed)
  stable/9/sys/conf/   (props changed)
  stable/9/sys/contrib/dev/acpica/   (props changed)
  stable/9/sys/contrib/octeon-sdk/   (props changed)
  stable/9/sys/contrib/pf/   (props changed)
  stable/9/sys/contrib/x86emu/   (props changed)

Modified: stable/9/sys/vm/vm_page.c
==============================================================================
--- stable/9/sys/vm/vm_page.c	Thu Nov 10 12:05:26 2011	(r227419)
+++ stable/9/sys/vm/vm_page.c	Thu Nov 10 16:50:36 2011	(r227420)
@@ -908,7 +908,7 @@ void
 vm_page_remove(vm_page_t m)
 {
 	vm_object_t object;
-	vm_page_t root;
+	vm_page_t next, prev, root;
 
 	if ((m->oflags & VPO_UNMANAGED) == 0)
 		vm_page_lock_assert(m, MA_OWNED);
@@ -923,15 +923,42 @@ vm_page_remove(vm_page_t m)
 	/*
 	 * Now remove from the object's list of backed pages.
 	 */
-	if (m != object->root)
-		vm_page_splay(m->pindex, object->root);
-	if (m->left == NULL)
-		root = m->right;
-	else {
-		root = vm_page_splay(m->pindex, m->left);
-		root->right = m->right;
+	if ((next = TAILQ_NEXT(m, listq)) != NULL && next->left == m) {
+		/*
+		 * Since the page's successor in the list is also its parent
+		 * in the tree, its right subtree must be empty.
+		 */
+		next->left = m->left;
+		KASSERT(m->right == NULL,
+		    ("vm_page_remove: page %p has right child", m));
+	} else if ((prev = TAILQ_PREV(m, pglist, listq)) != NULL &&
+	    prev->right == m) {
+		/*
+		 * Since the page's predecessor in the list is also its parent
+		 * in the tree, its left subtree must be empty.
+		 */
+		KASSERT(m->left == NULL,
+		    ("vm_page_remove: page %p has left child", m));
+		prev->right = m->right;
+	} else {
+		if (m != object->root)
+			vm_page_splay(m->pindex, object->root);
+		if (m->left == NULL)
+			root = m->right;
+		else if (m->right == NULL)
+			root = m->left;
+		else {
+			/*
+			 * Move the page's successor to the root, because
+			 * pages are usually removed in ascending order.
+			 */
+			if (m->right != next)
+				vm_page_splay(m->pindex, m->right);
+			next->left = m->left;
+			root = next;
+		}
+		object->root = root;
 	}
-	object->root = root;
 	TAILQ_REMOVE(&object->memq, m, listq);
 
 	/*
@@ -2021,7 +2048,7 @@ void
 vm_page_cache(vm_page_t m)
 {
 	vm_object_t object;
-	vm_page_t root;
+	vm_page_t next, prev, root;
 
 	vm_page_lock_assert(m, MA_OWNED);
 	object = m->object;
@@ -2056,15 +2083,42 @@ vm_page_cache(vm_page_t m)
 	 * Remove the page from the object's collection of resident
 	 * pages. 
 	 */
-	if (m != object->root)
-		vm_page_splay(m->pindex, object->root);
-	if (m->left == NULL)
-		root = m->right;
-	else {
-		root = vm_page_splay(m->pindex, m->left);
-		root->right = m->right;
+	if ((next = TAILQ_NEXT(m, listq)) != NULL && next->left == m) {
+		/*
+		 * Since the page's successor in the list is also its parent
+		 * in the tree, its right subtree must be empty.
+		 */
+		next->left = m->left;
+		KASSERT(m->right == NULL,
+		    ("vm_page_cache: page %p has right child", m));
+	} else if ((prev = TAILQ_PREV(m, pglist, listq)) != NULL &&
+	    prev->right == m) {
+		/*
+		 * Since the page's predecessor in the list is also its parent
+		 * in the tree, its left subtree must be empty.
+		 */
+		KASSERT(m->left == NULL,
+		    ("vm_page_cache: page %p has left child", m));
+		prev->right = m->right;
+	} else {
+		if (m != object->root)
+			vm_page_splay(m->pindex, object->root);
+		if (m->left == NULL)
+			root = m->right;
+		else if (m->right == NULL)
+			root = m->left;
+		else {
+			/*
+			 * Move the page's successor to the root, because
+			 * pages are usually removed in ascending order.
+			 */
+			if (m->right != next)
+				vm_page_splay(m->pindex, m->right);
+			next->left = m->left;
+			root = next;
+		}
+		object->root = root;
 	}
-	object->root = root;
 	TAILQ_REMOVE(&object->memq, m, listq);
 	object->resident_page_count--;