diff options
author | alc <alc@FreeBSD.org> | 2011-10-25 16:35:08 +0000 |
---|---|---|
committer | alc <alc@FreeBSD.org> | 2011-10-25 16:35:08 +0000 |
commit | 955d2b5af8740fe3af16a47e773773f03e52cdde (patch) | |
tree | c44ba760670cedf98c25880bb3cef763b351e2af /sys/vm | |
parent | afe77a15ac76058e7f1725e7ba0ccc6e9a314d87 (diff) | |
download | FreeBSD-src-955d2b5af8740fe3af16a47e773773f03e52cdde.zip FreeBSD-src-955d2b5af8740fe3af16a47e773773f03e52cdde.tar.gz |
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
Diffstat (limited to 'sys/vm')
-rw-r--r-- | sys/vm/vm_page.c | 90 |
1 files changed, 72 insertions, 18 deletions
diff --git a/sys/vm/vm_page.c b/sys/vm/vm_page.c index c0b3a70..cde1387 100644 --- a/sys/vm/vm_page.c +++ b/sys/vm/vm_page.c @@ -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--; |