Date: Thu, 10 Nov 2011 16:50:37 +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-9@freebsd.org Subject: svn commit: r227420 - stable/9/sys/vm Message-ID: <201111101650.pAAGobuW047534@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
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--;
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201111101650.pAAGobuW047534>