git: 8adb3acb63ee - main - pctrie: leave iter at root after ge_lookup failure

The branch main has been updated by dougm:

URL: https://cgit.FreeBSD.org/src/commit/?id=8adb3acb63ee8e7c20c3da497a9640c481bc7612

commit 8adb3acb63ee8e7c20c3da497a9640c481bc7612
Author:     Doug Moore <dougm@FreeBSD.org>
AuthorDate: 2025-07-10 08:14:07 +0000
Commit:     Doug Moore <dougm@FreeBSD.org>
CommitDate: 2025-07-10 08:14:07 +0000

    pctrie: leave iter at root after ge_lookup failure
    
    If pctrie_lookup_iter_ge fails to return a node, the iterator is left
    with NULL as the current node. Instead, make the pctrie_root the
    current node when the pctrie has an internalnode. Do the same thing
    for lookup_iter_le. If an iterator is reused after a ge/le lookup
    fails, this will skip the step in _pctrie_lookup_node where a NULL is
    replaced by the node at the top of the trie.
    
    Reviewed by:    alc
    Differential Revision:  https://reviews.freebsd.org/D51232
---
 sys/kern/subr_pctrie.c | 36 ++++++++++++++++++++----------------
 1 file changed, 20 insertions(+), 16 deletions(-)

diff --git a/sys/kern/subr_pctrie.c b/sys/kern/subr_pctrie.c
index 3a3548bad52b..bb86c779b936 100644
--- a/sys/kern/subr_pctrie.c
+++ b/sys/kern/subr_pctrie.c
@@ -691,21 +691,23 @@ _pctrie_lookup_ge(struct pctrie *ptree, struct pctrie_node *node,
 	 */
 	if (node == PCTRIE_NULL || *pctrie_toval(node) < index) {
 		/* Climb the path to find a node with a descendant > index. */
-		for (node = parent; node != NULL; node = pctrie_parent(node)) {
-			slot = pctrie_slot(node, index) + 1;
-			if ((node->pn_popmap >> slot) != 0)
+		node = NULL;
+		while (parent != NULL) {
+			slot = pctrie_slot(parent, index) + 1;
+			if ((parent->pn_popmap >> slot) != 0)
 				break;
+			node = parent;
+			parent = pctrie_parent(node);
 		}
-		if (node == NULL) {
+		if (parent == NULL) {
 			if (parent_out != NULL)
-				*parent_out = NULL;
+				*parent_out = node;
 			return (NULL);
 		}
 
 		/* Step to the least child with a descendant > index. */
-		slot += ffs(node->pn_popmap >> slot) - 1;
-		parent = node;
-		node = pctrie_node_load(&node->pn_child[slot], NULL,
+		slot += ffs(parent->pn_popmap >> slot) - 1;
+		node = pctrie_node_load(&parent->pn_child[slot], NULL,
 		    PCTRIE_LOCKED);
 	}
 	/* Descend to the least leaf of the subtrie. */
@@ -785,21 +787,23 @@ _pctrie_lookup_le(struct pctrie *ptree, struct pctrie_node *node,
 	 */
 	if (node == PCTRIE_NULL || *pctrie_toval(node) > index) {
 		/* Climb the path to find a node with a descendant < index. */
-		for (node = parent; node != NULL; node = pctrie_parent(node)) {
-			slot = pctrie_slot(node, index);
-			if ((node->pn_popmap & ((1 << slot) - 1)) != 0)
+		node = NULL;
+		while (parent != NULL) {
+			slot = pctrie_slot(parent, index);
+			if ((parent->pn_popmap & ((1 << slot) - 1)) != 0)
 				break;
+			node = parent;
+			parent = pctrie_parent(node);
 		}
-		if (node == NULL) {
+		if (parent == NULL) {
 			if (parent_out != NULL)
-				*parent_out = NULL;
+				*parent_out = node;
 			return (NULL);
 		}
 
 		/* Step to the greatest child with a descendant < index. */
-		slot = ilog2(node->pn_popmap & ((1 << slot) - 1));
-		parent = node;
-		node = pctrie_node_load(&node->pn_child[slot], NULL,
+		slot = ilog2(parent->pn_popmap & ((1 << slot) - 1));
+		node = pctrie_node_load(&parent->pn_child[slot], NULL,
 		    PCTRIE_LOCKED);
 	}
 	/* Descend to the greatest leaf of the subtrie. */