From owner-svn-src-all@FreeBSD.ORG Tue Oct 25 16:35:09 2011 Return-Path: Delivered-To: svn-src-all@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 3D3201065673; Tue, 25 Oct 2011 16:35:09 +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 2CB3A8FC16; Tue, 25 Oct 2011 16:35:09 +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 p9PGZ9qA005492; Tue, 25 Oct 2011 16:35:09 GMT (envelope-from alc@svn.freebsd.org) Received: (from alc@localhost) by svn.freebsd.org (8.14.4/8.14.4/Submit) id p9PGZ97C005490; Tue, 25 Oct 2011 16:35:09 GMT (envelope-from alc@svn.freebsd.org) Message-Id: <201110251635.p9PGZ97C005490@svn.freebsd.org> From: Alan Cox Date: Tue, 25 Oct 2011 16:35:09 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org X-SVN-Group: head MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Cc: Subject: svn commit: r226740 - head/sys/vm X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 25 Oct 2011 16:35:09 -0000 Author: alc Date: Tue Oct 25 16:35:08 2011 New Revision: 226740 URL: http://svn.freebsd.org/changeset/base/226740 Log: Speed up vm_page_cache() and vm_page_remove() by checking for a few common cases that can be handled in constant time. The insight being that a page's parent in the vm object's tree is very often its predecessor or successor in the vm object's ordered memq. Tested by: jhb MFC after: 10 days Modified: head/sys/vm/vm_page.c Modified: head/sys/vm/vm_page.c ============================================================================== --- head/sys/vm/vm_page.c Tue Oct 25 16:30:16 2011 (r226739) +++ head/sys/vm/vm_page.c Tue Oct 25 16:35:08 2011 (r226740) @@ -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--;