From owner-svn-src-stable@FreeBSD.ORG Thu Nov 10 17:04:33 2011 Return-Path: Delivered-To: svn-src-stable@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 9AF701065673; Thu, 10 Nov 2011 17:04:33 +0000 (UTC) (envelope-from alc@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:4f8:fff6::2c]) by mx1.freebsd.org (Postfix) with ESMTP id 89D988FC0A; Thu, 10 Nov 2011 17:04:33 +0000 (UTC) Received: from svn.freebsd.org (localhost [127.0.0.1]) by svn.freebsd.org (8.14.4/8.14.4) with ESMTP id pAAH4XNe048044; Thu, 10 Nov 2011 17:04:33 GMT (envelope-from alc@svn.freebsd.org) Received: (from alc@localhost) by svn.freebsd.org (8.14.4/8.14.4/Submit) id pAAH4XdQ048042; Thu, 10 Nov 2011 17:04:33 GMT (envelope-from alc@svn.freebsd.org) Message-Id: <201111101704.pAAH4XdQ048042@svn.freebsd.org> From: Alan Cox Date: Thu, 10 Nov 2011 17:04:33 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-stable@freebsd.org, svn-src-stable-8@freebsd.org X-SVN-Group: stable-8 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Cc: Subject: svn commit: r227422 - stable/8/sys/vm X-BeenThere: svn-src-stable@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: SVN commit messages for all the -stable branches of the src tree List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 10 Nov 2011 17:04:33 -0000 Author: alc Date: Thu Nov 10 17:04:33 2011 New Revision: 227422 URL: http://svn.freebsd.org/changeset/base/227422 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. Modified: stable/8/sys/vm/vm_page.c Directory Properties: stable/8/sys/ (props changed) stable/8/sys/amd64/include/xen/ (props changed) stable/8/sys/cddl/contrib/opensolaris/ (props changed) stable/8/sys/contrib/dev/acpica/ (props changed) stable/8/sys/contrib/pf/ (props changed) Modified: stable/8/sys/vm/vm_page.c ============================================================================== --- stable/8/sys/vm/vm_page.c Thu Nov 10 17:01:34 2011 (r227421) +++ stable/8/sys/vm/vm_page.c Thu Nov 10 17:04:33 2011 (r227422) @@ -737,7 +737,7 @@ void vm_page_remove(vm_page_t m) { vm_object_t object; - vm_page_t root; + vm_page_t next, prev, root; if ((object = m->object) == NULL) return; @@ -751,15 +751,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); /* @@ -1802,7 +1829,7 @@ void vm_page_cache(vm_page_t m) { vm_object_t object; - vm_page_t root; + vm_page_t next, prev, root; mtx_assert(&vm_page_queue_mtx, MA_OWNED); object = m->object; @@ -1838,15 +1865,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--;