The branch main has been updated by dougm:
URL:
https://cgit.FreeBSD.org/src/commit/?id=c0d0bc2bed8003d2f2b24c3c29ce971ca8dfc556
commit c0d0bc2bed8003d2f2b24c3c29ce971ca8dfc556
Author: Doug Moore <do...@freebsd.org>
AuthorDate: 2024-06-13 16:44:38 +0000
Commit: Doug Moore <do...@freebsd.org>
CommitDate: 2024-06-13 16:48:09 +0000
subr_pctrie: add leaf callbacks to pctrie_reclaim
PCTRIE_RECLAIM frees all the interior nodes in a pctrie, but is little
used because most trie-destroyers want to free leaves of the tree
too. Add PCTRIE_RECLAIM_CALLBACK, with two extra arguments, a callback
function and an auxiliary argument, that is invoked on every non-NULL
leaf in the tree as the tree is destroyed.
Reviewed by: rlibby, kib (previous version)
Differential Revision: https://reviews.freebsd.org/D45565
---
sys/kern/subr_pctrie.c | 78 ++++++++++++++++++++++++++++++++++++++------------
sys/sys/pctrie.h | 25 ++++++++++++++++
2 files changed, 85 insertions(+), 18 deletions(-)
diff --git a/sys/kern/subr_pctrie.c b/sys/kern/subr_pctrie.c
index 4017f98c207d..347c2bffd503 100644
--- a/sys/kern/subr_pctrie.c
+++ b/sys/kern/subr_pctrie.c
@@ -198,7 +198,6 @@ pctrie_root_store(struct pctrie *ptree, struct pctrie_node
*node,
static __inline bool
pctrie_isleaf(struct pctrie_node *node)
{
-
return (((uintptr_t)node & PCTRIE_ISLEAF) != 0);
}
@@ -217,10 +216,18 @@ pctrie_toleaf(uint64_t *val)
static __inline uint64_t *
pctrie_toval(struct pctrie_node *node)
{
-
return ((uint64_t *)((uintptr_t)node & ~PCTRIE_FLAGS));
}
+/*
+ * Returns the associated pointer extracted from node and field offset.
+ */
+static __inline void *
+pctrie_toptr(struct pctrie_node *node, int keyoff)
+{
+ return ((void *)(((uintptr_t)node & ~PCTRIE_FLAGS) - keyoff));
+}
+
/*
* Make 'child' a child of 'node'.
*/
@@ -792,14 +799,14 @@ pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,
}
/*
- * Prune all the leaves of 'node' before its first non-leaf child, make child
- * zero of 'node' point up to 'parent', make 'node' into 'parent' and that
- * non-leaf child into 'node'. Repeat until a node has been stripped of all
- * children, and mark it for freeing, returning its parent.
+ * Walk the subtrie rooted at *pnode in order, invoking callback on leaves and
+ * using the leftmost child pointer for path reversal, until an interior node
+ * is stripped of all children, and returned for deallocation, with *pnode left
+ * pointing the parent of that node.
*/
-static struct pctrie_node *
-pctrie_reclaim_prune(struct pctrie_node **pnode,
- struct pctrie_node *parent)
+static __always_inline struct pctrie_node *
+pctrie_reclaim_prune(struct pctrie_node **pnode, struct pctrie_node *parent,
+ pctrie_cb_t callback, int keyoff, void *arg)
{
struct pctrie_node *child, *node;
int slot;
@@ -812,8 +819,11 @@ pctrie_reclaim_prune(struct pctrie_node **pnode,
PCTRIE_UNSERIALIZED);
pctrie_node_store(&node->pn_child[slot], PCTRIE_NULL,
PCTRIE_UNSERIALIZED);
- if (pctrie_isleaf(child))
+ if (pctrie_isleaf(child)) {
+ if (callback != NULL)
+ callback(pctrie_toptr(child, keyoff), arg);
continue;
+ }
/* Climb one level down the trie. */
pctrie_node_store(&node->pn_child[0], parent,
PCTRIE_UNSERIALIZED);
@@ -827,8 +837,9 @@ pctrie_reclaim_prune(struct pctrie_node **pnode,
/*
* Recover the node parent from its first child and continue pruning.
*/
-struct pctrie_node *
-pctrie_reclaim_resume(struct pctrie_node **pnode)
+static __always_inline struct pctrie_node *
+pctrie_reclaim_resume_compound(struct pctrie_node **pnode,
+ pctrie_cb_t callback, int keyoff, void *arg)
{
struct pctrie_node *parent, *node;
@@ -839,24 +850,55 @@ pctrie_reclaim_resume(struct pctrie_node **pnode)
parent = pctrie_node_load(&node->pn_child[0], NULL,
PCTRIE_UNSERIALIZED);
pctrie_node_store(&node->pn_child[0], PCTRIE_NULL, PCTRIE_UNSERIALIZED);
- return (pctrie_reclaim_prune(pnode, parent));
+ return (pctrie_reclaim_prune(pnode, parent, callback, keyoff, arg));
}
/*
* Find the trie root, and start pruning with a NULL parent.
*/
-struct pctrie_node *
-pctrie_reclaim_begin(struct pctrie_node **pnode,
- struct pctrie *ptree)
+static __always_inline struct pctrie_node *
+pctrie_reclaim_begin_compound(struct pctrie_node **pnode,
+ struct pctrie *ptree,
+ pctrie_cb_t callback, int keyoff, void *arg)
{
struct pctrie_node *node;
node = pctrie_root_load(ptree, NULL, PCTRIE_UNSERIALIZED);
pctrie_root_store(ptree, PCTRIE_NULL, PCTRIE_UNSERIALIZED);
- if (pctrie_isleaf(node))
+ if (pctrie_isleaf(node)) {
+ if (callback != NULL && node != PCTRIE_NULL)
+ callback(pctrie_toptr(node, keyoff), arg);
return (NULL);
+ }
*pnode = node;
- return (pctrie_reclaim_prune(pnode, NULL));
+ return (pctrie_reclaim_prune(pnode, NULL, callback, keyoff, arg));
+}
+
+struct pctrie_node *
+pctrie_reclaim_resume(struct pctrie_node **pnode)
+{
+ return (pctrie_reclaim_resume_compound(pnode, NULL, 0, NULL));
+}
+
+struct pctrie_node *
+pctrie_reclaim_begin(struct pctrie_node **pnode, struct pctrie *ptree)
+{
+ return (pctrie_reclaim_begin_compound(pnode, ptree, NULL, 0, NULL));
+}
+
+struct pctrie_node *
+pctrie_reclaim_resume_cb(struct pctrie_node **pnode,
+ pctrie_cb_t callback, int keyoff, void *arg)
+{
+ return (pctrie_reclaim_resume_compound(pnode, callback, keyoff, arg));
+}
+
+struct pctrie_node *
+pctrie_reclaim_begin_cb(struct pctrie_node **pnode, struct pctrie *ptree,
+ pctrie_cb_t callback, int keyoff, void *arg)
+{
+ return (pctrie_reclaim_begin_compound(pnode, ptree,
+ callback, keyoff, arg));
}
/*
diff --git a/sys/sys/pctrie.h b/sys/sys/pctrie.h
index 06b9fca79528..4e1d8c7f8617 100644
--- a/sys/sys/pctrie.h
+++ b/sys/sys/pctrie.h
@@ -36,6 +36,8 @@
#ifdef _KERNEL
+typedef void (*pctrie_cb_t)(void *ptr, void *arg);
+
#define PCTRIE_DEFINE_SMR(name, type, field, allocfn, freefn, smr)
\
PCTRIE_DEFINE(name, type, field, allocfn, freefn) \
\
@@ -218,6 +220,24 @@ name##_PCTRIE_RECLAIM(struct pctrie *ptree)
\
freefn(ptree, freenode); \
} \
\
+/* \
+ * While reclaiming all internal trie nodes, invoke callback(leaf, arg)
\
+ * on every leaf in the trie, in order.
\
+ */ \
+static __inline __unused void \
+name##_PCTRIE_RECLAIM_CALLBACK(struct pctrie *ptree, \
+ pctrie_cb_t callback, void *arg) \
+{ \
+ struct pctrie_node *freenode, *node; \
+ \
+ for (freenode = pctrie_reclaim_begin_cb(&node, ptree, \
+ callback, __offsetof(struct type, field), arg); \
+ freenode != NULL; \
+ freenode = pctrie_reclaim_resume_cb(&node, \
+ callback, __offsetof(struct type, field), arg)) \
+ freefn(ptree, freenode); \
+} \
+ \
static __inline __unused struct type * \
name##_PCTRIE_REPLACE(struct pctrie *ptree, struct type *ptr) \
{ \
@@ -269,6 +289,11 @@ uint64_t *pctrie_lookup_unlocked(struct pctrie *ptree,
uint64_t key,
struct pctrie_node *pctrie_reclaim_begin(struct pctrie_node **pnode,
struct pctrie *ptree);
struct pctrie_node *pctrie_reclaim_resume(struct pctrie_node **pnode);
+struct pctrie_node *pctrie_reclaim_begin_cb(struct pctrie_node **pnode,
+ struct pctrie *ptree,
+ pctrie_cb_t callback, int keyoff, void *arg);
+struct pctrie_node *pctrie_reclaim_resume_cb(struct pctrie_node **pnode,
+ pctrie_cb_t callback, int keyoff, void *arg);
uint64_t *pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,
struct pctrie_node **killnode);
uint64_t *pctrie_replace(struct pctrie *ptree, uint64_t *newval);
