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);