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));
 }
 
 /*