Index: sys/kern/subr_pctrie.c
===================================================================
--- sys/kern/subr_pctrie.c
+++ sys/kern/subr_pctrie.c
@@ -539,14 +539,27 @@
     enum pctrie_access access)
 {
 	struct pctrie_node *node;
-	int slot;
+	int slot, top;
+
+	top = it->top;
+	if (top != 0) {
+		node = it->path[top - 1];
+		KASSERT(!powerof2(node->pn_popmap),
+		    ("%s: freed node in iter path", __func__));
+		if (!pctrie_keybarr(node, index, &slot)) {
+			node = pctrie_node_load(
+			    &node->pn_child[slot], smr, access);
+			if (pctrie_isleaf(node))
+				return (node);
+		}
+	}
 
 	/*
 	 * Climb the search path to find the lowest node from which to start the
 	 * search for a value matching 'index'.
 	 */
-	while (it->top != 0) {
-		node = it->path[it->top - 1];
+	while (top != 0) {
+		node = it->path[top - 1];
 		KASSERT(!powerof2(node->pn_popmap),
 		    ("%s: freed node in iter path", __func__));
 		if (!pctrie_keybarr(node, index, &slot)) {
@@ -554,18 +567,19 @@
 			    &node->pn_child[slot], smr, access);
 			break;
 		}
-		--it->top;
+		--top;
 	}
-	if (it->top == 0)
+	if (top == 0)
 		node = pctrie_root_load(it->ptree, smr, access);
 
 	/* Seek a node that matches index. */
 	while (!pctrie_isleaf(node) && !pctrie_keybarr(node, index, &slot)) {
-		KASSERT(it->top < nitems(it->path),
+		KASSERT(top < nitems(it->path),
 		    ("%s: path overflow in trie %p", __func__, it->ptree));
-		it->path[it->top++] = node;
+		it->path[top++] = node;
 		node = pctrie_node_load(&node->pn_child[slot], smr, access);
 	}
+	it->top = top;
 	return (node);
 }
 
@@ -781,6 +795,43 @@
 	return (pctrie_lookup_ge_node(node, index + 1));
 }
 
+static struct pctrie_node *
+_pctrie_iter_lookup_gt_node(struct pctrie_iter *it, uint64_t index)
+{
+	struct pctrie_node *node;
+	int slot, top;
+
+	top = it->top;
+	if (top != 0) {
+		node = it->path[top - 1];
+		slot = pctrie_slot(node, index);
+		if ((node->pn_popmap & (-2 << slot)) != 0) {
+			/* Return least child with a descendant > index. */
+			slot = ffs(node->pn_popmap & (-2 << slot)) - 1;
+			node = pctrie_node_load(&node->pn_child[slot], NULL,
+			    PCTRIE_LOCKED);
+			return (node);
+		}
+		--top;
+	}
+	while (top != 0) {
+		node = it->path[top - 1];
+		slot = pctrie_slot(node, index);
+		if ((node->pn_popmap & (-2 << slot)) != 0) {
+			/* Return least child with a descendant > index. */
+			slot = ffs(node->pn_popmap & (-2 << slot)) - 1;
+			node = pctrie_node_load(&node->pn_child[slot], NULL,
+			    PCTRIE_LOCKED);
+			it->top = top;
+			return (node);
+		}
+		--top;
+	}
+	it->top = 0;
+	return (NULL);
+
+}
+
 /*
  * Find first leaf >= index, and fill iter with the path to the parent of that
  * leaf.  Return NULL if there is no such leaf less than limit.
@@ -801,21 +852,11 @@
 	 */
 	if (node == PCTRIE_NULL || *pctrie_toval(node) < index) {
 		/* Climb the path to find a node with a descendant > index. */
-		while (it->top != 0) {
-			node = it->path[it->top - 1];
-			slot = pctrie_slot(node, index) + 1;
-			if ((node->pn_popmap >> slot) != 0)
-				break;
-			--it->top;
-		}
-		if (it->top == 0)
+		node = _pctrie_iter_lookup_gt_node(it, index);
+		if (node == NULL)
 			return (NULL);
-
-		/* Step to the least child with a descendant > index. */
-		slot += ffs(node->pn_popmap >> slot) - 1;
-		node = pctrie_node_load(&node->pn_child[slot], NULL,
-		    PCTRIE_LOCKED);
 	}
+
 	/* Descend to the least leaf of the subtrie. */
 	while (!pctrie_isleaf(node)) {
 		if (it->limit != 0 && node->pn_owner >= it->limit)
@@ -938,6 +979,44 @@
 	return (pctrie_lookup_le_node(node, index - 1));
 }
 
+static struct pctrie_node *
+_pctrie_iter_lookup_lt_node(struct pctrie_iter *it, uint64_t index)
+{
+	struct pctrie_node *node;
+	int slot, top;
+
+	top = it->top;
+	if (top != 0) {
+		node = it->path[top - 1];
+		slot = pctrie_slot(node, index);
+		if ((node->pn_popmap & ((1 << slot) - 1)) != 0) {
+			/* Return greatest child with a descendant < index. */
+			slot = ilog2(node->pn_popmap & ((1 << slot) - 1));
+			node = pctrie_node_load(&node->pn_child[slot], NULL,
+			    PCTRIE_LOCKED);
+			return (node);
+		}
+		--top;
+	}
+
+	while (top != 0) {
+		node = it->path[top - 1];
+		slot = pctrie_slot(node, index);
+		if ((node->pn_popmap & ((1 << slot) - 1)) != 0) {
+			/* Return greatest child with a descendant < index. */
+			slot = ilog2(node->pn_popmap & ((1 << slot) - 1));
+			node = pctrie_node_load(&node->pn_child[slot], NULL,
+			    PCTRIE_LOCKED);
+			it->top = top;
+			return (node);
+		}
+		--top;
+	}
+	it->top = 0;
+	return (NULL);
+
+}
+
 /*
  * Find first leaf <= index, and fill iter with the path to the parent of that
  * leaf.  Return NULL if there is no such leaf greater than limit.
@@ -958,21 +1037,11 @@
 	 */
 	if (node == PCTRIE_NULL || *pctrie_toval(node) > index) {
 		/* Climb the path to find a node with a descendant < index. */
-		while (it->top != 0) {
-			node = it->path[it->top - 1];
-			slot = pctrie_slot(node, index);
-			if ((node->pn_popmap & ((1 << slot) - 1)) != 0)
-				break;
-			--it->top;
-		}
-		if (it->top == 0)
+		node = _pctrie_iter_lookup_lt_node(it, index);
+		if (node == NULL)
 			return (NULL);
-
-		/* Step to the greatest child with a descendant < index. */
-		slot = ilog2(node->pn_popmap & ((1 << slot) - 1));
-		node = pctrie_node_load(&node->pn_child[slot], NULL,
-		    PCTRIE_LOCKED);
 	}
+
 	/* Descend to the greatest leaf of the subtrie. */
 	while (!pctrie_isleaf(node)) {
 		if (it->limit != 0 && it->limit >=