Page MenuHomeFreeBSD
Files F151758703

D51060.id157649.diff
No OneTemporary
Actions

D51060.id157649.diff
View Options

Index: sys/kern/subr_pctrie.c
===================================================================
--- sys/kern/subr_pctrie.c
+++ sys/kern/subr_pctrie.c
@@ -164,6 +164,17 @@
return (pctrie_node_load(pctrie_root(ptree), smr, access));
}
+/*
+ * Set the non-NULL root node for a tree. Assumes that a write lock is held.
+ */
+void
+pctrie_root_store(struct pctrie *ptree, struct pctrie_node *node)
+{
+ if (node != NULL)
+ pctrie_node_store(pctrie_root(ptree), node, PCTRIE_LOCKED);
+}
+
+
/*
* Get the child of a node.
*/
@@ -294,9 +305,9 @@
struct pctrie_node *parent;
int slot;
- parent = node;
- if (parent == NULL)
+ if (node == NULL)
node = pctrie_root_load(ptree, smr, access);
+ parent = pctrie_isleaf(node) ? NULL : node;
/*
* Climb the search path to find the lowest node from which to start the
@@ -335,6 +346,7 @@
node = _pctrie_lookup_node(ptree, NULL, index, &parent, NULL,
PCTRIE_LOCKED);
+ pctrie_root_store(ptree, parent);
return (pctrie_match_value(node, index));
}
@@ -398,7 +410,8 @@
*/
static __always_inline void *
_pctrie_insert_lookup(struct pctrie *ptree, struct pctrie_node *parent,
- uint64_t *val, struct pctrie_node **parent_out, uint64_t **found_out)
+ uint64_t *val, struct pctrie_node **parent_out, uint64_t **found_out,
+ bool sync)
{
struct pctrie_node *node;
@@ -410,8 +423,8 @@
pctrie_node_store(pctrie_root(ptree),
pctrie_toleaf(val), PCTRIE_LOCKED);
else
- pctrie_addnode(*parent_out, *val,
- pctrie_toleaf(val), PCTRIE_LOCKED);
+ pctrie_addnode(*parent_out, *val, pctrie_toleaf(val),
+ sync ? PCTRIE_LOCKED : PCTRIE_UNSERIALIZED);
return (NULL);
}
if (__predict_false(pctrie_match_value(node, *val) != NULL)) {
@@ -424,6 +437,9 @@
* children 'node' and 'val'. Return the place that points to 'node'
* now, and will point to to the new branching node later.
*/
+ if (*parent_out == NULL)
+ pctrie_node_store(pctrie_root(ptree), node,
+ PCTRIE_UNSERIALIZED);
return (pctrie_child(ptree, *parent_out, *val));
}
@@ -438,7 +454,8 @@
void *parentp;
uint64_t *found;
- parentp = _pctrie_insert_lookup(ptree, NULL, val, parent_out, &found);
+ parentp = _pctrie_insert_lookup(ptree, NULL, val, parent_out, &found,
+ false);
if (__predict_false(found != NULL))
panic("%s: key %jx is already present", __func__,
(uintmax_t)*val);
@@ -453,7 +470,8 @@
pctrie_insert_lookup(struct pctrie *ptree, uint64_t *val,
struct pctrie_node **parent_out, uint64_t **found_out)
{
- return (_pctrie_insert_lookup(ptree, NULL, val, parent_out, found_out));
+ return (_pctrie_insert_lookup(ptree, NULL, val, parent_out, found_out,
+ false));
}
/*
@@ -469,7 +487,7 @@
it->index = *val;
res = _pctrie_insert_lookup(it->ptree, it->node, val, &it->node,
- &found);
+ &found, true);
if (__predict_false(found != NULL))
panic("%s: key %jx is already present", __func__,
(uintmax_t)it->index);
@@ -483,7 +501,7 @@
*/
void
pctrie_insert_node(uint64_t *val, struct pctrie_node *parent, void *parentp,
- struct pctrie_node *child)
+ struct pctrie_node *child, bool sync)
{
struct pctrie_node *node;
uint64_t index, newind;
@@ -530,7 +548,8 @@
pctrie_addnode(child, index, pctrie_toleaf(val), PCTRIE_UNSERIALIZED);
pctrie_addnode(child, newind, node, PCTRIE_UNSERIALIZED);
/* Synchronize to make the above visible. */
- pctrie_node_store(parentp, child, PCTRIE_LOCKED);
+ pctrie_node_store(parentp, child,
+ sync ? PCTRIE_LOCKED : PCTRIE_UNSERIALIZED);
}
/*
@@ -648,8 +667,12 @@
pctrie_lookup_range(struct pctrie *ptree, uint64_t index,
uint64_t *value[], int count)
{
- return (_pctrie_lookup_range(ptree, NULL, index, value, count, NULL,
- NULL, PCTRIE_LOCKED));
+ struct pctrie_node *parent;
+
+ count = _pctrie_lookup_range(ptree, NULL, index, value, count, &parent,
+ NULL, PCTRIE_LOCKED);
+ pctrie_root_store(ptree, parent); \
+ return (count);
}
/*
@@ -744,7 +767,12 @@
uint64_t *
pctrie_lookup_ge(struct pctrie *ptree, uint64_t index)
{
- return (_pctrie_lookup_ge(ptree, NULL, index, NULL, 0));
+ struct pctrie_node *parent;
+ uint64_t *m;
+
+ m = _pctrie_lookup_ge(ptree, NULL, index, &parent, 0);
+ pctrie_root_store(ptree, parent); \
+ return (m);
}
/*
@@ -839,7 +867,12 @@
uint64_t *
pctrie_lookup_le(struct pctrie *ptree, uint64_t index)
{
- return (_pctrie_lookup_le(ptree, NULL, index, NULL, 0));
+ struct pctrie_node *parent;
+ uint64_t *m;
+
+ m = _pctrie_lookup_le(ptree, NULL, index, &parent, 0);
+ pctrie_root_store(ptree, parent); \
+ return (m);
}
uint64_t *
@@ -889,12 +922,15 @@
* pctrie and save it in *freenode for later disposal.
*/
static bool
-pctrie_remove(struct pctrie *ptree, struct pctrie_node *node, uint64_t index)
+pctrie_remove(struct pctrie *ptree, struct pctrie_node *node, uint64_t index,
+ bool sync)
{
smr_pctnode_t *parentp;
struct pctrie_node *child;
int slot;
+ enum pctrie_access access;
+ access = sync ? PCTRIE_LOCKED : PCTRIE_UNSERIALIZED;
parentp = pctrie_child(ptree, node, index);
if (node == NULL) {
pctrie_node_store(parentp, PCTRIE_NULL, PCTRIE_LOCKED);
@@ -906,7 +942,7 @@
__func__, slot, node));
node->pn_popmap ^= 1 << slot;
if (!powerof2(node->pn_popmap)) {
- pctrie_node_store(parentp, PCTRIE_NULL, PCTRIE_LOCKED);
+ pctrie_node_store(parentp, PCTRIE_NULL, access);
return (false);
}
pctrie_node_store(parentp, PCTRIE_NULL, PCTRIE_UNSERIALIZED);
@@ -919,7 +955,7 @@
if (!pctrie_isleaf(child))
pctrie_setparent(child, node);
parentp = pctrie_child(ptree, node, index);
- pctrie_node_store(parentp, child, PCTRIE_LOCKED);
+ pctrie_node_store(parentp, child, access);
return (true);
}
@@ -937,10 +973,12 @@
node = _pctrie_lookup_node(ptree, NULL, index, &parent, NULL,
PCTRIE_LOCKED);
m = pctrie_match_value(node, index);
- if (m != NULL && pctrie_remove(ptree, parent, index))
+ if (m != NULL && pctrie_remove(ptree, parent, index, false)) {
*freenode = parent;
- else
+ parent = pctrie_parent(*freenode);
+ } else
*freenode = NULL;
+ pctrie_root_store(ptree, parent);
return (m);
}
@@ -955,9 +993,13 @@
it->ptree, it->node, it->index), NULL, PCTRIE_LOCKED), it->index),
("%s: removing value %jx not at iter", __func__,
(uintmax_t)it->index));
- if (pctrie_remove(it->ptree, it->node, it->index)) {
+ if (pctrie_remove(it->ptree, it->node, it->index, true)) {
*freenode = it->node;
- it->node = pctrie_parent(it->node);
+ it->node = pctrie_parent(*freenode);
+ if (*freenode == pctrie_root_load(it->ptree, NULL,
+ PCTRIE_LOCKED))
+ pctrie_node_store(pctrie_root(it->ptree), it->node,
+ PCTRIE_LOCKED);
} else
*freenode = NULL;
}
@@ -1040,6 +1082,8 @@
callback(pctrie_toptr(node, keyoff), arg);
return (NULL);
}
+ while (pctrie_parent(node) != NULL)
+ node = pctrie_parent(node);
*pnode = node;
return (pctrie_reclaim_prune(pnode, NULL, callback, keyoff, arg));
}
@@ -1088,6 +1132,7 @@
panic("%s: original replacing value not found", __func__);
pctrie_node_store(pctrie_child(ptree, parent, *newval),
pctrie_toleaf(newval), PCTRIE_LOCKED);
+ pctrie_root_store(ptree, parent); \
return (m);
}
Index: sys/sys/pctrie.h
===================================================================
--- sys/sys/pctrie.h
+++ sys/sys/pctrie.h
@@ -131,7 +131,7 @@
static __inline __unused int \
name##_PCTRIE_INSERT_BASE(struct pctrie *ptree, uint64_t *val, \
struct pctrie_node **parent, void *parentp, \
- uint64_t *found, struct type **found_out) \
+ uint64_t *found, struct type **found_out, bool sync) \
{ \
struct pctrie_node *child; \
\
@@ -146,7 +146,7 @@
*found_out = NULL; \
return (ENOMEM); \
} \
- pctrie_insert_node(val, *parent, parentp, child); \
+ pctrie_insert_node(val, *parent, parentp, child, sync); \
*parent = child; \
} \
return (0); \
@@ -158,10 +158,13 @@
void *parentp; \
struct pctrie_node *parent; \
uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
+ int retval; \
\
parentp = pctrie_insert_lookup_strict(ptree, val, &parent); \
- return (name##_PCTRIE_INSERT_BASE(ptree, val, &parent, parentp, \
- NULL, NULL)); \
+ retval = name##_PCTRIE_INSERT_BASE(ptree, val, &parent, parentp,\
+ NULL, NULL, false); \
+ pctrie_root_store(ptree, parent); \
+ return (retval); \
} \
\
static __inline __unused int \
@@ -172,10 +175,13 @@
struct pctrie_node *parent; \
uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
uint64_t *found; \
+ int retval; \
\
parentp = pctrie_insert_lookup(ptree, val, &parent, &found); \
- return (name##_PCTRIE_INSERT_BASE(ptree, val, &parent, parentp, \
- found, found_out_opt)); \
+ retval = name##_PCTRIE_INSERT_BASE(ptree, val, &parent, parentp,\
+ found, found_out_opt, false); \
+ pctrie_root_store(ptree, parent); \
+ return (retval); \
} \
\
static __inline __unused int \
@@ -190,7 +196,8 @@
\
parentp = pctrie_insert_lookup(ptree, val, &parent, &found); \
retval = name##_PCTRIE_INSERT_BASE(ptree, val, &parent, parentp, \
- found, found_out); \
+ found, found_out, false); \
+ pctrie_root_store(ptree, parent); \
if (retval != 0) \
return (retval); \
found = pctrie_subtree_lookup_lt(ptree, parent, *val); \
@@ -206,7 +213,7 @@
\
parentp = pctrie_iter_insert_lookup(it, val); \
return (name##_PCTRIE_INSERT_BASE(it->ptree, val, &it->node, \
- parentp, NULL, NULL)); \
+ parentp, NULL, NULL, true)); \
} \
\
static __inline __unused struct type * \
@@ -367,23 +374,6 @@
} \
\
static __inline __unused void \
-name##_PCTRIE_ITER_REMOVE(struct pctrie_iter *it) \
-{ \
- struct pctrie_node *freenode; \
- \
- pctrie_iter_remove(it, &freenode); \
- name##_PCTRIE_REMOVE_BASE(it->ptree, freenode); \
-} \
- \
-static __inline __unused struct type * \
-name##_PCTRIE_REPLACE(struct pctrie *ptree, struct type *ptr) \
-{ \
- \
- return name##_PCTRIE_VAL2PTR( \
- pctrie_replace(ptree, name##_PCTRIE_PTR2VAL(ptr))); \
-} \
- \
-static __inline __unused void \
name##_PCTRIE_REMOVE(struct pctrie *ptree, uint64_t key) \
{ \
uint64_t *val; \
@@ -404,6 +394,23 @@
val = pctrie_remove_lookup(ptree, key, &freenode); \
name##_PCTRIE_REMOVE_BASE(ptree, freenode); \
return name##_PCTRIE_VAL2PTR(val); \
+} \
+ \
+static __inline __unused void \
+name##_PCTRIE_ITER_REMOVE(struct pctrie_iter *it) \
+{ \
+ struct pctrie_node *freenode; \
+ \
+ pctrie_iter_remove(it, &freenode); \
+ name##_PCTRIE_REMOVE_BASE(it->ptree, freenode); \
+} \
+ \
+static __inline __unused struct type * \
+name##_PCTRIE_REPLACE(struct pctrie *ptree, struct type *ptr) \
+{ \
+ \
+ return name##_PCTRIE_VAL2PTR( \
+ pctrie_replace(ptree, name##_PCTRIE_PTR2VAL(ptr))); \
}
struct pctrie_iter;
@@ -412,7 +419,7 @@
void *pctrie_insert_lookup_strict(struct pctrie *ptree, uint64_t *val,
struct pctrie_node **parent_out);
void pctrie_insert_node(uint64_t *val, struct pctrie_node *parent,
- void *parentp, struct pctrie_node *child);
+ void *parentp, struct pctrie_node *child, bool sync);
uint64_t *pctrie_lookup(struct pctrie *ptree, uint64_t key);
uint64_t *pctrie_lookup_readonly(struct pctrie *ptree, uint64_t key);
uint64_t *pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t key,
@@ -447,6 +454,8 @@
pctrie_cb_t callback, int keyoff, void *arg);
uint64_t *pctrie_remove_lookup(struct pctrie *ptree, uint64_t index,
struct pctrie_node **killnode);
+void pctrie_root_store(struct pctrie *ptree,
+ struct pctrie_node *node);
void pctrie_iter_remove(struct pctrie_iter *it,
struct pctrie_node **freenode);
uint64_t *pctrie_iter_value(struct pctrie_iter *it);

File Metadata

Mime Type
text/plain
Expires
Sat, Apr 11, 11:41 AM (12 h, 39 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
31288198
Default Alt Text
D51060.id157649.diff (11 KB)

Event Timeline