Index: sys/vm/vm_page.h =================================================================== --- sys/vm/vm_page.h +++ sys/vm/vm_page.h @@ -223,6 +223,9 @@ } vm_page_astate_t; struct vm_page { + /* radix trie key must appear first */ + vm_pindex_t pindex; /* offset into object (O,P) */ + vm_object_t object; /* which object am I in (O) */ union { TAILQ_ENTRY(vm_page) q; /* page queue or free list (Q) */ struct { @@ -238,8 +241,6 @@ } uma; } plinks; TAILQ_ENTRY(vm_page) listq; /* pages in same object (O) */ - vm_object_t object; /* which object am I in (O) */ - vm_pindex_t pindex; /* offset into object (O,P) */ vm_paddr_t phys_addr; /* physical address of page (C) */ struct md_page md; /* machine dependent stuff */ u_int ref_count; /* page references (A) */ Index: sys/vm/vm_radix.c =================================================================== --- sys/vm/vm_radix.c +++ sys/vm/vm_radix.c @@ -59,6 +59,7 @@ #include #include #include +#include #include #include #include @@ -454,33 +455,6 @@ return (0); } -/* - * Returns the value stored at the index. If the index is not present, - * NULL is returned. - */ -static __always_inline vm_page_t -_vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index, - enum vm_radix_access access) -{ - struct vm_radix_node *rnode; - vm_page_t m; - int slot; - - rnode = vm_radix_root_load(rtree, access); - for (;;) { - if (vm_radix_isleaf(rnode)) { - if ((m = vm_radix_topage(rnode)) != NULL && - m->pindex == index) - return (m); - break; - } - if (vm_radix_keybarr(rnode, index, &slot)) - break; - rnode = vm_radix_node_load(&rnode->rn_child[slot], access); - } - return (NULL); -} - /* * Returns the value stored at the index assuming there is an external lock. * @@ -489,8 +463,7 @@ vm_page_t vm_radix_lookup(struct vm_radix *rtree, vm_pindex_t index) { - - return _vm_radix_lookup(rtree, index, LOCKED); + return ((vm_page_t)(pctrie_lookup((struct pctrie *)rtree, index))); } /* @@ -501,13 +474,8 @@ vm_page_t vm_radix_lookup_unlocked(struct vm_radix *rtree, vm_pindex_t index) { - vm_page_t m; - - smr_enter(vm_radix_smr); - m = _vm_radix_lookup(rtree, index, SMR); - smr_exit(vm_radix_smr); - - return (m); + return ((vm_page_t)pctrie_lookup_unlocked( + (struct pctrie *)rtree, index, vm_radix_smr)); } /* @@ -519,83 +487,7 @@ vm_page_t vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index) { - struct vm_radix_node *rnode, *succ; - vm_page_t m; - int slot; - - /* - * Descend the trie as if performing an ordinary lookup for the page - * with the specified pindex. However, unlike an ordinary lookup, as we - * descend the trie, we use "succ" to remember the last branching-off - * point, that is, the interior node under which the page with the least - * pindex that is both outside our current path down the trie and more - * than the specified pindex resides. (The node's popmap makes it fast - * and easy to recognize a branching-off point.) If our ordinary lookup - * fails to yield a page with a pindex that is greater than or equal to - * the specified pindex, then we will exit this loop and perform a - * lookup starting from "succ". If "succ" is not NULL, then that lookup - * is guaranteed to succeed. - */ - rnode = vm_radix_root_load(rtree, LOCKED); - succ = NULL; - for (;;) { - if (vm_radix_isleaf(rnode)) { - if ((m = vm_radix_topage(rnode)) != NULL && - m->pindex >= index) - return (m); - break; - } - if (vm_radix_keybarr(rnode, index, &slot)) { - /* - * If all pages in this subtree have pindex > index, - * then the page in this subtree with the least pindex - * is the answer. - */ - if (rnode->rn_owner > index) - succ = rnode; - break; - } - - /* - * Just in case the next search step leads to a subtree of all - * pages with pindex < index, check popmap to see if a next - * bigger step, to a subtree of all pages with pindex > index, - * is available. If so, remember to restart the search here. - */ - if ((rnode->rn_popmap >> slot) > 1) - succ = rnode; - rnode = vm_radix_node_load(&rnode->rn_child[slot], LOCKED); - } - - /* - * Restart the search from the last place visited in the subtree that - * included some pages with pindex > index, if there was such a place. - */ - if (succ == NULL) - return (NULL); - if (succ != rnode) { - /* - * Take a step to the next bigger sibling of the node chosen - * last time. In that subtree, all pages have pindex > index. - */ - slot = vm_radix_slot(succ, index) + 1; - KASSERT((succ->rn_popmap >> slot) != 0, - ("%s: no popmap siblings past slot %d in node %p", - __func__, slot, succ)); - slot += ffs(succ->rn_popmap >> slot) - 1; - succ = vm_radix_node_load(&succ->rn_child[slot], LOCKED); - } - - /* - * Find the page in the subtree rooted at "succ" with the least pindex. - */ - while (!vm_radix_isleaf(succ)) { - KASSERT(succ->rn_popmap != 0, - ("%s: no popmap children in node %p", __func__, succ)); - slot = ffs(succ->rn_popmap) - 1; - succ = vm_radix_node_load(&succ->rn_child[slot], LOCKED); - } - return (vm_radix_topage(succ)); + return ((vm_page_t)pctrie_lookup_ge((struct pctrie *)rtree, index)); } /* @@ -607,48 +499,7 @@ vm_page_t vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index) { - struct vm_radix_node *pred, *rnode; - vm_page_t m; - int slot; - - /* - * Mirror the implementation of vm_radix_lookup_ge, described above. - */ - rnode = vm_radix_root_load(rtree, LOCKED); - pred = NULL; - for (;;) { - if (vm_radix_isleaf(rnode)) { - if ((m = vm_radix_topage(rnode)) != NULL && - m->pindex <= index) - return (m); - break; - } - if (vm_radix_keybarr(rnode, index, &slot)) { - if (rnode->rn_owner < index) - pred = rnode; - break; - } - if ((rnode->rn_popmap & ((1 << slot) - 1)) != 0) - pred = rnode; - rnode = vm_radix_node_load(&rnode->rn_child[slot], LOCKED); - } - if (pred == NULL) - return (NULL); - if (pred != rnode) { - slot = vm_radix_slot(pred, index); - KASSERT((pred->rn_popmap & ((1 << slot) - 1)) != 0, - ("%s: no popmap siblings before slot %d in node %p", - __func__, slot, pred)); - slot = fls(pred->rn_popmap & ((1 << slot) - 1)) - 1; - pred = vm_radix_node_load(&pred->rn_child[slot], LOCKED); - } - while (!vm_radix_isleaf(pred)) { - KASSERT(pred->rn_popmap != 0, - ("%s: no popmap children in node %p", __func__, pred)); - slot = fls(pred->rn_popmap) - 1; - pred = vm_radix_node_load(&pred->rn_child[slot], LOCKED); - } - return (vm_radix_topage(pred)); + return ((vm_page_t)pctrie_lookup_le((struct pctrie *)rtree, index)); } /*