Index: sys/kern/subr_pctrie.c =================================================================== --- sys/kern/subr_pctrie.c +++ sys/kern/subr_pctrie.c @@ -472,211 +472,112 @@ } /* - * Look up the nearest entry at a position bigger than or equal to index, + * Returns the least value stored at a position greater than or equal to index * assuming access is externally synchronized by a lock. + * + * Returns NULL if the all positions are less than index. */ uint64_t * pctrie_lookup_ge(struct pctrie *ptree, uint64_t index) { - struct pctrie_node *stack[PCTRIE_LIMIT]; + struct pctrie_node *node, *succ; uint64_t *m; - struct pctrie_node *child, *node; -#ifdef INVARIANTS - int loops = 0; -#endif - unsigned tos; int slot; node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); - if (node == NULL) - return (NULL); - else if (pctrie_isleaf(node)) { - m = pctrie_toval(node); - if (*m >= index) - return (m); - else - return (NULL); - } - tos = 0; - for (;;) { - /* - * If the keys differ before the current bisection node, - * then the search key might rollback to the earliest - * available bisection node or to the smallest key - * in the current node (if the owner is greater than the - * search key). - */ + succ = NULL; + while (node != NULL) { + if (pctrie_isleaf(node)) { + m = pctrie_toval(node); + if (*m >= index) + return (m); + break; + } if (pctrie_keybarr(node, index)) { - if (index > node->pn_owner) { -ascend: - KASSERT(++loops < 1000, - ("pctrie_lookup_ge: too many loops")); - - /* - * Pop nodes from the stack until either the - * stack is empty or a node that could have a - * matching descendant is found. - */ - do { - if (tos == 0) - return (NULL); - node = stack[--tos]; - } while (pctrie_slot(index, - node->pn_clev) == (PCTRIE_COUNT - 1)); - - /* - * The following computation cannot overflow - * because index's slot at the current level - * is less than PCTRIE_COUNT - 1. - */ - index = pctrie_trimkey(index, - node->pn_clev); - index += PCTRIE_UNITLEVEL(node->pn_clev); - } else - index = node->pn_owner; - KASSERT(!pctrie_keybarr(node, index), - ("pctrie_lookup_ge: keybarr failed")); + if (node->pn_owner >= index) + /* Min node in subtree is min >= index */ + succ = node; + break; } slot = pctrie_slot(index, node->pn_clev); - child = pctrie_node_load(&node->pn_child[slot], NULL, + if (node->pn_popmap >> slot >> 1 != 0) + /* A next bigger sibling has nodes > index. */ + succ = node; + node = pctrie_node_load(&node->pn_child[slot], NULL, + PCTRIE_LOCKED); + } + if (succ == NULL) + /* No nodes >= index. */ + return (NULL); + if (succ != node) { + /* Step to the next bigger sibling with nodes > index. */ + slot = pctrie_slot(index, succ->pn_clev) + 1; + slot += __builtin_ctz(succ->pn_popmap >> slot); + succ = pctrie_node_load(&succ->pn_child[slot], NULL, + PCTRIE_LOCKED); + } + /* Min node in subtree is min > index */ + while (!pctrie_isleaf(succ)) { + slot = __builtin_ctz(succ->pn_popmap); + succ = pctrie_node_load(&succ->pn_child[slot], NULL, PCTRIE_LOCKED); - if (pctrie_isleaf(child)) { - m = pctrie_toval(child); - if (*m >= index) - return (m); - } else if (child != NULL) - goto descend; - - /* Find the first set bit beyond the first slot+1 bits. */ - slot = ffs(node->pn_popmap & (-2 << slot)) - 1; - if (slot < 0) { - /* - * A value or edge greater than the search slot is not - * found in the current node; ascend to the next - * higher-level node. - */ - goto ascend; - } - child = pctrie_node_load(&node->pn_child[slot], - NULL, PCTRIE_LOCKED); - KASSERT(child != NULL, ("%s: bad popmap slot %d in node %p", - __func__, slot, node)); - if (pctrie_isleaf(child)) - return (pctrie_toval(child)); - index = pctrie_trimkey(index, node->pn_clev + 1) + - slot * PCTRIE_UNITLEVEL(node->pn_clev); -descend: - KASSERT(node->pn_clev > 0, - ("pctrie_lookup_ge: pushing leaf's parent")); - KASSERT(tos < PCTRIE_LIMIT, - ("pctrie_lookup_ge: stack overflow")); - stack[tos++] = node; - node = child; } + return (pctrie_toval(succ)); } /* - * Look up the nearest entry at a position less than or equal to index, + * Returns the greatest value stored at a position less than or equal to index * assuming access is externally synchronized by a lock. + * + * Returns NULL if the all positions are more than index. */ uint64_t * pctrie_lookup_le(struct pctrie *ptree, uint64_t index) { - struct pctrie_node *stack[PCTRIE_LIMIT]; + struct pctrie_node *node, *pred; uint64_t *m; - struct pctrie_node *child, *node; -#ifdef INVARIANTS - int loops = 0; -#endif - unsigned tos; int slot; node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); - if (node == NULL) - return (NULL); - else if (pctrie_isleaf(node)) { - m = pctrie_toval(node); - if (*m <= index) - return (m); - else - return (NULL); - } - tos = 0; - for (;;) { - /* - * If the keys differ before the current bisection node, - * then the search key might rollback to the earliest - * available bisection node or to the largest key - * in the current node (if the owner is smaller than the - * search key). - */ + pred = NULL; + while (node != NULL) { + if (pctrie_isleaf(node)) { + m = pctrie_toval(node); + if (*m <= index) + return (m); + break; + } if (pctrie_keybarr(node, index)) { - if (index > node->pn_owner) { - index = node->pn_owner + PCTRIE_COUNT * - PCTRIE_UNITLEVEL(node->pn_clev); - } else { -ascend: - KASSERT(++loops < 1000, - ("pctrie_lookup_le: too many loops")); - - /* - * Pop nodes from the stack until either the - * stack is empty or a node that could have a - * matching descendant is found. - */ - do { - if (tos == 0) - return (NULL); - node = stack[--tos]; - } while (pctrie_slot(index, - node->pn_clev) == 0); - - /* - * The following computation cannot overflow - * because index's slot at the current level - * is greater than 0. - */ - index = pctrie_trimkey(index, - node->pn_clev); - } - index--; - KASSERT(!pctrie_keybarr(node, index), - ("pctrie_lookup_le: keybarr failed")); + if (node->pn_owner <= index) + /* Max node in subtree is max <= index */ + pred = node; + break; } slot = pctrie_slot(index, node->pn_clev); - child = pctrie_node_load(&node->pn_child[slot], NULL, + if ((node->pn_popmap & ((1 << slot) - 1)) != 0) + /* A next smaller sibling has nodes < index. */ + pred = node; + node = pctrie_node_load(&node->pn_child[slot], NULL, + PCTRIE_LOCKED); + } + if (pred == NULL) + /* No nodes <= index. */ + return (NULL); + if (pred != node) { + /* Step to the next smaller sibling with nodes < index. */ + slot = pctrie_slot(index, pred->pn_clev); + slot = 8 * sizeof(int) - 1 - + __builtin_clz(pred->pn_popmap & ((1 << slot) - 1)); + pred = pctrie_node_load(&pred->pn_child[slot], NULL, + PCTRIE_LOCKED); + } + /* Max node in subtree is max <= index */ + while (!pctrie_isleaf(pred)) { + slot = 8 * sizeof(int) - 1 - __builtin_clz(pred->pn_popmap); + pred = pctrie_node_load(&pred->pn_child[slot], NULL, PCTRIE_LOCKED); - if (pctrie_isleaf(child)) { - m = pctrie_toval(child); - if (*m <= index) - return (m); - } else if (child != NULL) - goto descend; - - /* Find the last set bit among the first slot bits. */ - slot = fls(node->pn_popmap & ((1 << slot) - 1)) - 1; - if (slot < 0) { - /* - * A value or edge smaller than the search slot is not - * found in the current node; ascend to the next - * higher-level node. - */ - goto ascend; - } - child = pctrie_node_load(&node->pn_child[slot], - NULL, PCTRIE_LOCKED); - if (pctrie_isleaf(child)) - return (pctrie_toval(child)); - index = pctrie_trimkey(index, node->pn_clev + 1) + - (slot + 1) * PCTRIE_UNITLEVEL(node->pn_clev) - 1; -descend: - KASSERT(node->pn_clev > 0, - ("pctrie_lookup_le: pushing leaf's parent")); - KASSERT(tos < PCTRIE_LIMIT, - ("pctrie_lookup_le: stack overflow")); - stack[tos++] = node; - node = child; } + return (pctrie_toval(pred)); } /* Index: sys/vm/vm_radix.c =================================================================== --- sys/vm/vm_radix.c +++ sys/vm/vm_radix.c @@ -513,205 +513,106 @@ } /* - * Look up the nearest entry at a position greater than or equal to index. + * Returns the least value stored at a position greater than or equal to index + * assuming access is externally synchronized by a lock. + * + * Returns NULL if the all positions are less than index. */ vm_page_t vm_radix_lookup_ge(struct vm_radix *rtree, vm_pindex_t index) { - struct vm_radix_node *stack[VM_RADIX_LIMIT]; + struct vm_radix_node *rnode, *succ; vm_page_t m; - struct vm_radix_node *child, *rnode; -#ifdef INVARIANTS - int loops = 0; -#endif - int slot, tos; + int slot; rnode = vm_radix_root_load(rtree, LOCKED); - if (rnode == NULL) - return (NULL); - else if (vm_radix_isleaf(rnode)) { - m = vm_radix_topage(rnode); - if (m->pindex >= index) - return (m); - else - return (NULL); - } - tos = 0; - for (;;) { - /* - * If the keys differ before the current bisection node, - * then the search key might rollback to the earliest - * available bisection node or to the smallest key - * in the current node (if the owner is greater than the - * search key). - */ - if (vm_radix_keybarr(rnode, index)) { - if (index > rnode->rn_owner) { -ascend: - KASSERT(++loops < 1000, - ("vm_radix_lookup_ge: too many loops")); - - /* - * Pop nodes from the stack until either the - * stack is empty or a node that could have a - * matching descendant is found. - */ - do { - if (tos == 0) - return (NULL); - rnode = stack[--tos]; - } while (vm_radix_slot(index, - rnode->rn_clev) == (VM_RADIX_COUNT - 1)); - - /* - * The following computation cannot overflow - * because index's slot at the current level - * is less than VM_RADIX_COUNT - 1. - */ - index = vm_radix_trimkey(index, - rnode->rn_clev); - index += VM_RADIX_UNITLEVEL(rnode->rn_clev); - } else - index = rnode->rn_owner; - KASSERT(!vm_radix_keybarr(rnode, index), - ("vm_radix_lookup_ge: keybarr failed")); - } - slot = vm_radix_slot(index, rnode->rn_clev); - child = vm_radix_node_load(&rnode->rn_child[slot], LOCKED); - if (vm_radix_isleaf(child)) { - m = vm_radix_topage(child); + succ = NULL; + while (rnode != NULL) { + if (vm_radix_isleaf(rnode)) { + m = vm_radix_topage(rnode); if (m->pindex >= index) return (m); - } else if (child != NULL) - goto descend; - - /* Find the first set bit beyond the first slot+1 bits. */ - slot = ffs(rnode->rn_popmap & (-2 << slot)) - 1; - if (slot < 0) { - /* - * A page or edge greater than the search slot is not - * found in the current node; ascend to the next - * higher-level node. - */ - goto ascend; + break; } - child = vm_radix_node_load(&rnode->rn_child[slot], LOCKED); - KASSERT(child != NULL, ("%s: bad popmap slot %d in rnode %p", - __func__, slot, rnode)); - if (vm_radix_isleaf(child)) - return (vm_radix_topage(child)); - index = vm_radix_trimkey(index, rnode->rn_clev + 1) + - slot * VM_RADIX_UNITLEVEL(rnode->rn_clev); -descend: - KASSERT(rnode->rn_clev > 0, - ("vm_radix_lookup_ge: pushing leaf's parent")); - KASSERT(tos < VM_RADIX_LIMIT, - ("vm_radix_lookup_ge: stack overflow")); - stack[tos++] = rnode; - rnode = child; + if (vm_radix_keybarr(rnode, index)) { + if (rnode->rn_owner >= index) + /* Min node in subtree is min >= index */ + succ = rnode; + break; + } + slot = vm_radix_slot(index, rnode->rn_clev); + if (rnode->rn_popmap >> slot >> 1 != 0) + /* A next bigger sibling has nodes > index. */ + succ = rnode; + rnode = vm_radix_node_load(&rnode->rn_child[slot], LOCKED); } + if (succ == NULL) + /* No nodes >= index. */ + return (NULL); + if (succ != rnode) { + /* Step to the next bigger sibling with nodes > index. */ + slot = vm_radix_slot(index, succ->rn_clev) + 1; + slot += __builtin_ctz(succ->rn_popmap >> slot); + succ = vm_radix_node_load(&succ->rn_child[slot], LOCKED); + } + /* Min node in subtree is min > index */ + while (!vm_radix_isleaf(succ)) { + slot = __builtin_ctz(succ->rn_popmap); + succ = vm_radix_node_load(&succ->rn_child[slot], LOCKED); + } + return (vm_radix_topage(succ)); } /* - * Look up the nearest entry at a position less than or equal to index. + * Returns the greatest value stored at a position less than or equal to index + * assuming access is externally synchronized by a lock. + * + * Returns NULL if the all positions are more than index. */ vm_page_t vm_radix_lookup_le(struct vm_radix *rtree, vm_pindex_t index) { - struct vm_radix_node *stack[VM_RADIX_LIMIT]; + struct vm_radix_node *pred, *rnode; vm_page_t m; - struct vm_radix_node *child, *rnode; -#ifdef INVARIANTS - int loops = 0; -#endif - int slot, tos; + int slot; rnode = vm_radix_root_load(rtree, LOCKED); - if (rnode == NULL) - return (NULL); - else if (vm_radix_isleaf(rnode)) { - m = vm_radix_topage(rnode); - if (m->pindex <= index) - return (m); - else - return (NULL); - } - tos = 0; - for (;;) { - /* - * If the keys differ before the current bisection node, - * then the search key might rollback to the earliest - * available bisection node or to the largest key - * in the current node (if the owner is smaller than the - * search key). - */ - if (vm_radix_keybarr(rnode, index)) { - if (index > rnode->rn_owner) { - index = rnode->rn_owner + VM_RADIX_COUNT * - VM_RADIX_UNITLEVEL(rnode->rn_clev); - } else { -ascend: - KASSERT(++loops < 1000, - ("vm_radix_lookup_le: too many loops")); - - /* - * Pop nodes from the stack until either the - * stack is empty or a node that could have a - * matching descendant is found. - */ - do { - if (tos == 0) - return (NULL); - rnode = stack[--tos]; - } while (vm_radix_slot(index, - rnode->rn_clev) == 0); - - /* - * The following computation cannot overflow - * because index's slot at the current level - * is greater than 0. - */ - index = vm_radix_trimkey(index, - rnode->rn_clev); - } - index--; - KASSERT(!vm_radix_keybarr(rnode, index), - ("vm_radix_lookup_le: keybarr failed")); - } - slot = vm_radix_slot(index, rnode->rn_clev); - child = vm_radix_node_load(&rnode->rn_child[slot], LOCKED); - if (vm_radix_isleaf(child)) { - m = vm_radix_topage(child); + pred = NULL; + while (rnode != NULL) { + if (vm_radix_isleaf(rnode)) { + m = vm_radix_topage(rnode); if (m->pindex <= index) return (m); - } else if (child != NULL) - goto descend; - - /* Find the last set bit among the first slot bits. */ - slot = fls(rnode->rn_popmap & ((1 << slot) - 1)) - 1; - if (slot < 0) { - /* - * A page or edge smaller than the search slot is not - * found in the current node; ascend to the next - * higher-level node. - */ - goto ascend; + break; } - child = vm_radix_node_load(&rnode->rn_child[slot], LOCKED); - KASSERT(child != NULL, ("%s: bad popmap slot %d in rnode %p", - __func__, slot, rnode)); - if (vm_radix_isleaf(child)) - return (vm_radix_topage(child)); - index = vm_radix_trimkey(index, rnode->rn_clev + 1) + - (slot + 1) * VM_RADIX_UNITLEVEL(rnode->rn_clev) - 1; -descend: - KASSERT(rnode->rn_clev > 0, - ("vm_radix_lookup_le: pushing leaf's parent")); - KASSERT(tos < VM_RADIX_LIMIT, - ("vm_radix_lookup_le: stack overflow")); - stack[tos++] = rnode; - rnode = child; + if (vm_radix_keybarr(rnode, index)) { + if (rnode->rn_owner <= index) + /* Max node in subtree is max <= index */ + pred = rnode; + break; + } + slot = vm_radix_slot(index, rnode->rn_clev); + if ((rnode->rn_popmap & ((1 << slot) - 1)) != 0) + /* A next smaller sibling has nodes < index. */ + pred = rnode; + rnode = vm_radix_node_load(&rnode->rn_child[slot], LOCKED); + } + if (pred == NULL) + /* No nodes <= index. */ + return (NULL); + if (pred != rnode) { + /* Step to the next smaller sibling with nodes < index. */ + slot = vm_radix_slot(index, pred->rn_clev); + slot = 8 * sizeof(int) - 1 - + __builtin_clz(pred->rn_popmap & ((1 << slot) - 1)); + pred = vm_radix_node_load(&pred->rn_child[slot], LOCKED); + } + /* Max node in subtree is max <= index */ + while (!vm_radix_isleaf(pred)) { + slot = 8 * sizeof(int) - 1 - __builtin_clz(pred->rn_popmap); + pred = vm_radix_node_load(&pred->rn_child[slot], LOCKED); } + return (vm_radix_topage(pred)); } /*