Page MenuHomeFreeBSD
Files F154614112

D46895.id144502.diff
No OneTemporary
Actions

D46895.id144502.diff
View Options

Index: sys/kern/subr_pctrie.c
===================================================================
--- sys/kern/subr_pctrie.c
+++ sys/kern/subr_pctrie.c
@@ -129,8 +129,6 @@
#endif
}
-enum pctrie_access { PCTRIE_SMR, PCTRIE_LOCKED, PCTRIE_UNSERIALIZED };
-
/*
* Fetch a node pointer from a slot.
*/
@@ -286,7 +284,7 @@
static __always_inline void *
pctrie_insert_lookup_compound(struct pctrie *ptree, uint64_t *val,
uint64_t **found_out, struct pctrie_node **neighbor_out,
- enum pctrie_insert_neighbor_mode mode)
+ enum pctrie_insert_neighbor_mode mode, enum pctrie_access access)
{
uint64_t index;
struct pctrie_node *node, *parent;
@@ -305,10 +303,10 @@
if (node == PCTRIE_NULL) {
if (parent == NULL)
pctrie_root_store(ptree,
- pctrie_toleaf(val), PCTRIE_LOCKED);
+ pctrie_toleaf(val), access);
else
pctrie_addnode(parent, index,
- pctrie_toleaf(val), PCTRIE_LOCKED);
+ pctrie_toleaf(val), access);
return (NULL);
}
if (*pctrie_toval(node) == index) {
@@ -363,14 +361,15 @@
* if the key already exists, and do not look for neighboring entries.
*/
void *
-pctrie_insert_lookup_strict(struct pctrie *ptree, uint64_t *val)
+pctrie_insert_lookup_strict(struct pctrie *ptree, uint64_t *val,
+ enum pctrie_access access)
{
void *parentp;
uint64_t *found;
found = NULL;
parentp = pctrie_insert_lookup_compound(ptree, val, &found, NULL,
- PCTRIE_INSERT_NEIGHBOR_NONE);
+ PCTRIE_INSERT_NEIGHBOR_NONE, access);
if (__predict_false(found != NULL))
panic("%s: key %jx is already present", __func__,
(uintmax_t)*val);
@@ -383,11 +382,11 @@
*/
void *
pctrie_insert_lookup(struct pctrie *ptree, uint64_t *val,
- uint64_t **found_out)
+ uint64_t **found_out, enum pctrie_access access)
{
*found_out = NULL;
return (pctrie_insert_lookup_compound(ptree, val, found_out, NULL,
- PCTRIE_INSERT_NEIGHBOR_NONE));
+ PCTRIE_INSERT_NEIGHBOR_NONE, access));
}
/*
@@ -397,12 +396,13 @@
*/
void *
pctrie_insert_lookup_gt(struct pctrie *ptree, uint64_t *val,
- uint64_t **found_out, struct pctrie_node **neighbor_out)
+ uint64_t **found_out, struct pctrie_node **neighbor_out,
+ enum pctrie_access access)
{
*found_out = NULL;
*neighbor_out = NULL;
return (pctrie_insert_lookup_compound(ptree, val, found_out,
- neighbor_out, PCTRIE_INSERT_NEIGHBOR_GT));
+ neighbor_out, PCTRIE_INSERT_NEIGHBOR_GT, access));
}
/*
@@ -412,19 +412,21 @@
*/
void *
pctrie_insert_lookup_lt(struct pctrie *ptree, uint64_t *val,
- uint64_t **found_out, struct pctrie_node **neighbor_out)
+ uint64_t **found_out, struct pctrie_node **neighbor_out,
+ enum pctrie_access access)
{
*found_out = NULL;
*neighbor_out = NULL;
return (pctrie_insert_lookup_compound(ptree, val, found_out,
- neighbor_out, PCTRIE_INSERT_NEIGHBOR_LT));
+ neighbor_out, PCTRIE_INSERT_NEIGHBOR_LT, access));
}
/*
* Uses new node to insert key-value pair into the trie at given location.
*/
void
-pctrie_insert_node(void *parentp, struct pctrie_node *parent, uint64_t *val)
+pctrie_insert_node(void *parentp, struct pctrie_node *parent, uint64_t *val,
+ enum pctrie_access access)
{
struct pctrie_node *node;
uint64_t index, newind;
@@ -468,7 +470,7 @@
pctrie_addnode(parent, index, pctrie_toleaf(val), PCTRIE_UNSERIALIZED);
pctrie_addnode(parent, newind, node, PCTRIE_UNSERIALIZED);
/* Synchronize to make the above visible. */
- pctrie_node_store(parentp, parent, PCTRIE_LOCKED);
+ pctrie_node_store(parentp, parent, access);
}
/*
@@ -600,7 +602,8 @@
* Assumes access is externally synchronized by a lock.
*/
void *
-pctrie_iter_insert_lookup(struct pctrie_iter *it, uint64_t *val)
+pctrie_iter_insert_lookup(struct pctrie_iter *it, uint64_t *val,
+ enum pctrie_access access)
{
struct pctrie_node *node;
@@ -609,10 +612,10 @@
if (node == PCTRIE_NULL) {
if (it->top == 0)
pctrie_root_store(it->ptree,
- pctrie_toleaf(val), PCTRIE_LOCKED);
+ pctrie_toleaf(val), access);
else
pctrie_addnode(it->path[it->top - 1], it->index,
- pctrie_toleaf(val), PCTRIE_LOCKED);
+ pctrie_toleaf(val), access);
return (NULL);
}
if (__predict_false(pctrie_match_value(node, it->index) != NULL))
@@ -1035,13 +1038,14 @@
static void
pctrie_remove(struct pctrie *ptree, uint64_t index, struct pctrie_node *parent,
- struct pctrie_node *node, struct pctrie_node **freenode)
+ struct pctrie_node *node, struct pctrie_node **freenode,
+ enum pctrie_access access)
{
struct pctrie_node *child;
int slot;
if (node == NULL) {
- pctrie_root_store(ptree, PCTRIE_NULL, PCTRIE_LOCKED);
+ pctrie_root_store(ptree, PCTRIE_NULL, access);
return;
}
slot = pctrie_slot(node, index);
@@ -1049,7 +1053,7 @@
("%s: bad popmap slot %d in node %p",
__func__, slot, node));
node->pn_popmap ^= 1 << slot;
- pctrie_node_store(&node->pn_child[slot], PCTRIE_NULL, PCTRIE_LOCKED);
+ pctrie_node_store(&node->pn_child[slot], PCTRIE_NULL, access);
if (!powerof2(node->pn_popmap))
return;
KASSERT(node->pn_popmap != 0, ("%s: bad popmap all zeroes", __func__));
@@ -1058,14 +1062,13 @@
KASSERT(child != PCTRIE_NULL,
("%s: bad popmap slot %d in node %p", __func__, slot, node));
if (parent == NULL)
- pctrie_root_store(ptree, child, PCTRIE_LOCKED);
+ pctrie_root_store(ptree, child, access);
else {
slot = pctrie_slot(parent, index);
KASSERT(node ==
pctrie_node_load(&parent->pn_child[slot], NULL,
PCTRIE_LOCKED), ("%s: invalid child value", __func__));
- pctrie_node_store(&parent->pn_child[slot], child,
- PCTRIE_LOCKED);
+ pctrie_node_store(&parent->pn_child[slot], child, access);
}
/*
* The child is still valid and we can not zero the
@@ -1081,7 +1084,7 @@
*/
uint64_t *
pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,
- struct pctrie_node **freenode)
+ struct pctrie_node **freenode, enum pctrie_access access)
{
struct pctrie_node *child, *node, *parent;
uint64_t *m;
@@ -1099,7 +1102,7 @@
}
m = pctrie_match_value(child, index);
if (m != NULL)
- pctrie_remove(ptree, index, parent, node, freenode);
+ pctrie_remove(ptree, index, parent, node, freenode, access);
return (m);
}
@@ -1108,7 +1111,8 @@
* adjust the path if it's last member is to be freed.
*/
uint64_t *
-pctrie_iter_remove(struct pctrie_iter *it, struct pctrie_node **freenode)
+pctrie_iter_remove(struct pctrie_iter *it, struct pctrie_node **freenode,
+ enum pctrie_access access)
{
struct pctrie_node *child, *node, *parent;
uint64_t *m;
@@ -1128,7 +1132,8 @@
}
m = pctrie_match_value(child, it->index);
if (m != NULL)
- pctrie_remove(it->ptree, it->index, parent, node, freenode);
+ pctrie_remove(it->ptree, it->index, parent, node, freenode,
+ access);
if (*freenode != NULL)
--it->top;
return (m);
@@ -1264,7 +1269,8 @@
* Panics if there is not an old value in the trie at the new value's index.
*/
uint64_t *
-pctrie_replace(struct pctrie *ptree, uint64_t *newval)
+pctrie_replace(struct pctrie *ptree, uint64_t *newval,
+ enum pctrie_access access)
{
struct pctrie_node *leaf, *parent, *node;
uint64_t *m;
@@ -1280,11 +1286,11 @@
if ((m = pctrie_toval(node)) != NULL && *m == index) {
if (parent == NULL)
pctrie_root_store(ptree,
- leaf, PCTRIE_LOCKED);
+ leaf, access);
else
pctrie_node_store(
&parent->pn_child[slot], leaf,
- PCTRIE_LOCKED);
+ access);
return (m);
}
break;
Index: sys/sys/pctrie.h
===================================================================
--- sys/sys/pctrie.h
+++ sys/sys/pctrie.h
@@ -38,8 +38,15 @@
typedef void (*pctrie_cb_t)(void *ptr, void *arg);
+enum pctrie_access { PCTRIE_SMR, PCTRIE_LOCKED, PCTRIE_UNSERIALIZED };
+
+#define PCTRIE_DEFINE(name, type, field, allocfn, freefn) \
+ PCTRIE_DEFINE_COMMON(name, type, field, allocfn, freefn, \
+ PCTRIE_UNSERIALIZED) \
+
#define PCTRIE_DEFINE_SMR(name, type, field, allocfn, freefn, smr) \
- PCTRIE_DEFINE(name, type, field, allocfn, freefn) \
+ PCTRIE_DEFINE_COMMON(name, type, field, allocfn, freefn, \
+ PCTRIE_LOCKED) \
\
static __inline struct type * \
name##_PCTRIE_LOOKUP_UNLOCKED(struct pctrie *ptree, uint64_t key) \
@@ -59,7 +66,7 @@
#define pctrie_subtree_lookup_lt_assert(node, key, ptree, res)
#endif
-#define PCTRIE_DEFINE(name, type, field, allocfn, freefn) \
+#define PCTRIE_DEFINE_COMMON(name, type, field, allocfn, freefn, access)\
\
CTASSERT(sizeof(((struct type *)0)->field) == sizeof(uint64_t)); \
/* \
@@ -92,13 +99,13 @@
void *parentp; \
uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
\
- parentp = pctrie_insert_lookup_strict(ptree, val); \
+ parentp = pctrie_insert_lookup_strict(ptree, val, access); \
if (parentp == NULL) \
return (0); \
parent = allocfn(ptree); \
if (__predict_false(parent == NULL)) \
return (ENOMEM); \
- pctrie_insert_node(parentp, parent, val); \
+ pctrie_insert_node(parentp, parent, val, access); \
return (0); \
} \
\
@@ -111,7 +118,7 @@
uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
uint64_t *found; \
\
- parentp = pctrie_insert_lookup(ptree, val, &found); \
+ parentp = pctrie_insert_lookup(ptree, val, &found, access); \
if (found != NULL) { \
if (found_out_opt != NULL) \
*found_out_opt = name##_PCTRIE_VAL2PTR(found); \
@@ -122,7 +129,7 @@
parent = allocfn(ptree); \
if (__predict_false(parent == NULL)) \
return (ENOMEM); \
- pctrie_insert_node(parentp, parent, val); \
+ pctrie_insert_node(parentp, parent, val, access); \
return (0); \
} \
\
@@ -136,7 +143,7 @@
uint64_t *found; \
\
parentp = pctrie_insert_lookup_gt(ptree, val, &found, \
- &neighbor); \
+ &neighbor, access); \
if (__predict_false(found != NULL)) { \
*found_out = name##_PCTRIE_VAL2PTR(found); \
return (EEXIST); \
@@ -149,7 +156,7 @@
} \
if (neighbor == parentp) \
neighbor = parent; \
- pctrie_insert_node(parentp, parent, val); \
+ pctrie_insert_node(parentp, parent, val, access); \
} \
found = pctrie_subtree_lookup_gt(neighbor, *val); \
*found_out = name##_PCTRIE_VAL2PTR(found); \
@@ -167,7 +174,7 @@
uint64_t *found; \
\
parentp = pctrie_insert_lookup_lt(ptree, val, &found, \
- &neighbor); \
+ &neighbor, access); \
if (__predict_false(found != NULL)) { \
*found_out = name##_PCTRIE_VAL2PTR(found); \
return (EEXIST); \
@@ -180,7 +187,7 @@
} \
if (neighbor == parentp) \
neighbor = parent; \
- pctrie_insert_node(parentp, parent, val); \
+ pctrie_insert_node(parentp, parent, val, access); \
} \
found = pctrie_subtree_lookup_lt(neighbor, *val); \
*found_out = name##_PCTRIE_VAL2PTR(found); \
@@ -246,13 +253,13 @@
void *parentp; \
uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
\
- parentp = pctrie_iter_insert_lookup(it, val); \
+ parentp = pctrie_iter_insert_lookup(it, val, access); \
if (parentp == NULL) \
return (0); \
parent = allocfn(it->ptree); \
if (__predict_false(parent == NULL)) \
return (ENOMEM); \
- pctrie_insert_node(parentp, parent, val); \
+ pctrie_insert_node(parentp, parent, val, access); \
it->path[it->top++] = parent; \
return (0); \
} \
@@ -329,7 +336,7 @@
uint64_t *val; \
struct pctrie_node *freenode; \
\
- val = pctrie_iter_remove(it, &freenode); \
+ val = pctrie_iter_remove(it, &freenode, access); \
if (val == NULL) \
panic("%s: key not found", __func__); \
if (freenode != NULL) \
@@ -341,7 +348,7 @@
{ \
\
return name##_PCTRIE_VAL2PTR( \
- pctrie_replace(ptree, name##_PCTRIE_PTR2VAL(ptr))); \
+ pctrie_replace(ptree, name##_PCTRIE_PTR2VAL(ptr), access)); \
} \
\
static __inline __unused void \
@@ -350,7 +357,7 @@
uint64_t *val; \
struct pctrie_node *freenode; \
\
- val = pctrie_remove_lookup(ptree, key, &freenode); \
+ val = pctrie_remove_lookup(ptree, key, &freenode, access); \
if (val == NULL) \
panic("%s: key not found", __func__); \
if (freenode != NULL) \
@@ -363,7 +370,7 @@
uint64_t *val; \
struct pctrie_node *freenode; \
\
- val = pctrie_remove_lookup(ptree, key, &freenode); \
+ val = pctrie_remove_lookup(ptree, key, &freenode, access); \
if (freenode != NULL) \
freefn(ptree, freenode); \
return name##_PCTRIE_VAL2PTR(val); \
@@ -371,15 +378,17 @@
struct pctrie_iter;
void *pctrie_insert_lookup(struct pctrie *ptree, uint64_t *val,
- uint64_t **found_out);
+ uint64_t **found_out, enum pctrie_access access);
void *pctrie_insert_lookup_gt(struct pctrie *ptree, uint64_t *val,
- uint64_t **found_out, struct pctrie_node **neighbor_out);
+ uint64_t **found_out, struct pctrie_node **neighbor_out,
+ enum pctrie_access access);
void *pctrie_insert_lookup_lt(struct pctrie *ptree, uint64_t *val,
- uint64_t **found_out, struct pctrie_node **neighbor_out);
+ uint64_t **found_out, struct pctrie_node **neighbor_out,
+ enum pctrie_access access);
void *pctrie_insert_lookup_strict(struct pctrie *ptree,
- uint64_t *val);
-void pctrie_insert_node(void *parentp,
- struct pctrie_node *parent, uint64_t *val);
+ uint64_t *val, enum pctrie_access access);
+void pctrie_insert_node(void *parentp, struct pctrie_node *parent,
+ uint64_t *val, enum pctrie_access access);
uint64_t *pctrie_lookup(struct pctrie *ptree, uint64_t key);
uint64_t *pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t key,
smr_t smr);
@@ -388,7 +397,7 @@
uint64_t *pctrie_iter_next(struct pctrie_iter *it);
uint64_t *pctrie_iter_prev(struct pctrie_iter *it);
void *pctrie_iter_insert_lookup(struct pctrie_iter *it,
- uint64_t *val);
+ uint64_t *val, enum pctrie_access access);
uint64_t *pctrie_lookup_ge(struct pctrie *ptree, uint64_t key);
uint64_t *pctrie_subtree_lookup_gt(struct pctrie_node *node,
uint64_t key);
@@ -408,11 +417,12 @@
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);
+ struct pctrie_node **killnode, enum pctrie_access access);
uint64_t *pctrie_iter_remove(struct pctrie_iter *it,
- struct pctrie_node **freenode);
+ struct pctrie_node **freenode, enum pctrie_access access);
uint64_t *pctrie_iter_value(struct pctrie_iter *it);
-uint64_t *pctrie_replace(struct pctrie *ptree, uint64_t *newval);
+uint64_t *pctrie_replace(struct pctrie *ptree, uint64_t *newval,
+ enum pctrie_access access);
size_t pctrie_node_size(void);
int pctrie_zone_init(void *mem, int size, int flags);

File Metadata

Mime Type
text/plain
Expires
Thu, Apr 30, 1:22 AM (14 h, 17 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
32425285
Default Alt Text
D46895.id144502.diff (14 KB)

Event Timeline