Page MenuHomeFreeBSD
Files F101956298

D45565.diff
No OneTemporary
Actions

D45565.diff
View Options

diff --git a/sys/kern/subr_pctrie.c b/sys/kern/subr_pctrie.c
--- a/sys/kern/subr_pctrie.c
+++ b/sys/kern/subr_pctrie.c
@@ -198,7 +198,6 @@
static __inline bool
pctrie_isleaf(struct pctrie_node *node)
{
-
return (((uintptr_t)node & PCTRIE_ISLEAF) != 0);
}
@@ -217,10 +216,18 @@
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 @@
}
/*
- * 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_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 @@
/*
* 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 @@
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
--- 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 @@
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 @@
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);

File Metadata

Mime Type
text/plain
Expires
Wed, Nov 6, 7:10 PM (19 h, 40 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
14498628
Default Alt Text
D45565.diff (6 KB)

Event Timeline