Date: Thu, 10 Nov 2011 17:04:33 +0000 (UTC) From: Alan Cox <alc@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-stable@freebsd.org, svn-src-stable-8@freebsd.org Subject: svn commit: r227422 - stable/8/sys/vm Message-ID: <201111101704.pAAH4XdQ048042@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
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--;
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201111101704.pAAH4XdQ048042>