The branch main has been updated by dougm:
URL:
https://cgit.FreeBSD.org/src/commit/?id=8adb3acb63ee8e7c20c3da497a9640c481bc7612
commit 8adb3acb63ee8e7c20c3da497a9640c481bc7612
Author: Doug Moore <do...@freebsd.org>
AuthorDate: 2025-07-10 08:14:07 +0000
Commit: Doug Moore <do...@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. */
