Page Menu
Home
FreeBSD
Search
Configure Global Search
Log In
Files
F97670035
D45565.id139773.diff
No One
Temporary
Actions
View File
Edit File
Delete File
View Transforms
Subscribe
Mute Notifications
Flag For Later
Award Token
Size
5 KB
Referenced Files
None
Subscribers
None
D45565.id139773.diff
View Options
Index: sys/kern/subr_pctrie.c
===================================================================
--- sys/kern/subr_pctrie.c
+++ sys/kern/subr_pctrie.c
@@ -221,6 +221,16 @@
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'.
*/
@@ -797,9 +807,9 @@
* non-leaf child into 'node'. Repeat until a node has been stripped of all
* children, and mark it for freeing, returning its parent.
*/
-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 +822,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 +840,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 +853,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));
}
/*
Index: sys/sys/pctrie.h
===================================================================
--- sys/sys/pctrie.h
+++ 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
Details
Attached
Mime Type
text/plain
Expires
Tue, Oct 1, 4:45 PM (15 h, 9 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
13265307
Default Alt Text
D45565.id139773.diff (5 KB)
Attached To
Mode
D45565: subr_pctrie: add leaf callbacks to pctrie_reclaim
Attached
Detach File
Event Timeline
Log In to Comment