Index: sys/kern/subr_pctrie.c =================================================================== --- sys/kern/subr_pctrie.c +++ sys/kern/subr_pctrie.c @@ -54,9 +54,6 @@ #include #include #include -#include /* smr.h depends on struct thread. */ -#include -#include #ifdef DDB #include @@ -74,9 +71,6 @@ _Static_assert(sizeof(pn_popmap_t) <= sizeof(int), "pn_popmap_t too wide"); -struct pctrie_node; -typedef SMR_POINTER(struct pctrie_node *) smr_pctnode_t; - struct pctrie_node { uint64_t pn_owner; /* Owner of record. */ pn_popmap_t pn_popmap; /* Valid children. */ @@ -107,66 +101,6 @@ return (false); } -/* - * Check radix node. - */ -static __inline void -pctrie_node_put(struct pctrie_node *node) -{ -#ifdef INVARIANTS - int slot; - - KASSERT(powerof2(node->pn_popmap), - ("pctrie_node_put: node %p has too many children %04x", node, - node->pn_popmap)); - for (slot = 0; slot < PCTRIE_COUNT; slot++) { - if ((node->pn_popmap & (1 << slot)) != 0) - continue; - KASSERT(smr_unserialized_load(&node->pn_child[slot], true) == - PCTRIE_NULL, - ("pctrie_node_put: node %p has a child", node)); - } -#endif -} - -enum pctrie_access { PCTRIE_SMR, PCTRIE_LOCKED, PCTRIE_UNSERIALIZED }; - -/* - * Fetch a node pointer from a slot. - */ -static __inline struct pctrie_node * -pctrie_node_load(smr_pctnode_t *p, smr_t smr, enum pctrie_access access) -{ - switch (access) { - case PCTRIE_UNSERIALIZED: - return (smr_unserialized_load(p, true)); - case PCTRIE_LOCKED: - return (smr_serialized_load(p, true)); - case PCTRIE_SMR: - return (smr_entered_load(p, smr)); - } - __assert_unreachable(); -} - -static __inline void -pctrie_node_store(smr_pctnode_t *p, void *v, enum pctrie_access access) -{ - switch (access) { - case PCTRIE_UNSERIALIZED: - smr_unserialized_store(p, v, true); - break; - case PCTRIE_LOCKED: - smr_serialized_store(p, v, true); - break; - case PCTRIE_SMR: - panic("%s: Not supported in SMR section.", __func__); - break; - default: - __assert_unreachable(); - break; - } -} - /* * Get the root address, cast to proper type for load/store. */ @@ -194,15 +128,6 @@ return (((uintptr_t)node & PCTRIE_ISLEAF) != 0); } -/* - * Returns val with leaf bit set. - */ -static __inline void * -pctrie_toleaf(uint64_t *val) -{ - return ((void *)((uintptr_t)val | PCTRIE_ISLEAF)); -} - /* * Returns the associated val extracted from node. */ @@ -226,12 +151,12 @@ */ static __inline void pctrie_addnode(struct pctrie_node *node, uint64_t index, - struct pctrie_node *child, enum pctrie_access access) + struct pctrie_node *child) { int slot; slot = pctrie_slot(node, index); - pctrie_node_store(&node->pn_child[slot], child, access); + pctrie_node_store(&node->pn_child[slot], child, PCTRIE_UNSERIALIZED); node->pn_popmap ^= 1 << slot; KASSERT((node->pn_popmap & (1 << slot)) != 0, ("%s: bad popmap slot %d in node %p", __func__, slot, node)); @@ -282,16 +207,18 @@ * Note that mode is expected to be a compile-time constant, and this procedure * is expected to be inlined into callers with extraneous code optimized out. */ -static __always_inline void * -pctrie_insert_lookup_compound(struct pctrie *ptree, uint64_t *val, +static __always_inline smr_pctnode_t * +pctrie_insert_lookup_compound(struct pctrie *ptree, uint64_t index, uint64_t **found_out, struct pctrie_node **neighbor_out, enum pctrie_insert_neighbor_mode mode) { - uint64_t index; struct pctrie_node *node, *parent; int slot; - index = *val; + if (neighbor_out != NULL) + *neighbor_out = NULL; + if (found_out != NULL) + *found_out = NULL; /* * The owner of record for root is not really important because it @@ -301,19 +228,13 @@ parent = NULL; for (;;) { if (pctrie_isleaf(node)) { - if (node == PCTRIE_NULL) { - if (parent == NULL) - pctrie_node_store(pctrie_root(ptree), - pctrie_toleaf(val), PCTRIE_LOCKED); - else - pctrie_addnode(parent, index, - pctrie_toleaf(val), PCTRIE_LOCKED); - return (NULL); - } - if (*pctrie_toval(node) == index) { - *found_out = pctrie_toval(node); - return (NULL); - } + if (node != PCTRIE_NULL) { + if (*pctrie_toval(node) == index) { + *found_out = pctrie_toval(node); + return (NULL); + } + } else if (parent != NULL) + parent->pn_popmap ^= 1 << slot; break; } if (pctrie_keybarr(node, index, &slot)) @@ -336,22 +257,21 @@ } /* - * The caller will split this node. If we're tracking the next - * neighbor, record the old node if the old entry is in the right - * direction. + * If we're tracking the next neighbor, and node is not NULL, record + * this future sibling node if it is in the right direction. */ - if (mode == PCTRIE_INSERT_NEIGHBOR_LT) { + if (node != PCTRIE_NULL && mode == PCTRIE_INSERT_NEIGHBOR_LT) { if (*pctrie_toval(node) < index) *neighbor_out = node; - } else if (mode == PCTRIE_INSERT_NEIGHBOR_GT) { + } else if (node != PCTRIE_NULL && mode == PCTRIE_INSERT_NEIGHBOR_GT) { if (*pctrie_toval(node) > index) *neighbor_out = node; } /* - * 'node' must be replaced in the tree with a new branch node, with - * children 'node' and 'val'. Return the place that points to 'node' - * now, and will point to to the new branching node later. + * 'node' must be replaced in the tree with an index leaf, or with a new + * branch node, with children 'node' and an index leaf. Return the place + * that points to 'node' now, and will point to to the new node later. */ return ((parent == NULL) ? pctrie_root(ptree): &parent->pn_child[slot]); } @@ -360,18 +280,17 @@ * Wrap pctrie_insert_lookup_compound to implement a strict insertion. Panic * if the key already exists, and do not look for neighboring entries. */ -void * -pctrie_insert_lookup_strict(struct pctrie *ptree, uint64_t *val) +smr_pctnode_t * +pctrie_insert_lookup_strict(struct pctrie *ptree, uint64_t index) { - void *parentp; + smr_pctnode_t *parentp; uint64_t *found; - found = NULL; - parentp = pctrie_insert_lookup_compound(ptree, val, &found, NULL, + parentp = pctrie_insert_lookup_compound(ptree, index, &found, NULL, PCTRIE_INSERT_NEIGHBOR_NONE); if (__predict_false(found != NULL)) panic("%s: key %jx is already present", __func__, - (uintmax_t)*val); + (uintmax_t)index); return (parentp); } @@ -379,12 +298,11 @@ * Wrap pctrie_insert_lookup_compound to implement find-or-insert. Do not look * for neighboring entries. */ -void * -pctrie_insert_lookup(struct pctrie *ptree, uint64_t *val, +smr_pctnode_t * +pctrie_insert_lookup(struct pctrie *ptree, uint64_t index, uint64_t **found_out) { - *found_out = NULL; - return (pctrie_insert_lookup_compound(ptree, val, found_out, NULL, + return (pctrie_insert_lookup_compound(ptree, index, found_out, NULL, PCTRIE_INSERT_NEIGHBOR_NONE)); } @@ -393,13 +311,11 @@ * greater entry. Find a subtree that contains the next entry greater than the * newly-inserted or to-be-inserted entry. */ -void * -pctrie_insert_lookup_gt(struct pctrie *ptree, uint64_t *val, +smr_pctnode_t * +pctrie_insert_lookup_gt(struct pctrie *ptree, uint64_t index, uint64_t **found_out, struct pctrie_node **neighbor_out) { - *found_out = NULL; - *neighbor_out = NULL; - return (pctrie_insert_lookup_compound(ptree, val, found_out, + return (pctrie_insert_lookup_compound(ptree, index, found_out, neighbor_out, PCTRIE_INSERT_NEIGHBOR_GT)); } @@ -408,46 +324,34 @@ * lesser entry. Find a subtree that contains the next entry less than the * newly-inserted or to-be-inserted entry. */ -void * -pctrie_insert_lookup_lt(struct pctrie *ptree, uint64_t *val, +smr_pctnode_t * +pctrie_insert_lookup_lt(struct pctrie *ptree, uint64_t index, uint64_t **found_out, struct pctrie_node **neighbor_out) { - *found_out = NULL; - *neighbor_out = NULL; - return (pctrie_insert_lookup_compound(ptree, val, found_out, + return (pctrie_insert_lookup_compound(ptree, index, found_out, neighbor_out, PCTRIE_INSERT_NEIGHBOR_LT)); } /* - * Uses new node to insert key-value pair into the trie at given location. + * Prepare a newly allocated node, nulling any stray children and filling in its + * new clev and owner fields */ -void -pctrie_insert_node(void *parentp, struct pctrie_node *parent, uint64_t *val) +static void +pctrie_init_node(struct pctrie_node *child, uint64_t index, uint64_t newind) { - struct pctrie_node *node; - uint64_t index, newind; /* - * Clear the last child pointer of the newly allocated parent. We want + * Clear the last child pointer of the newly allocated child. We want * to clear it after the final section has exited so lookup can not * return false negatives. It is done here because it will be * cache-cold in the dtor callback. */ - if (parent->pn_popmap != 0) { - pctrie_node_store(&parent->pn_child[ffs(parent->pn_popmap) - 1], + if (child->pn_popmap != 0) { + pctrie_node_store(&child->pn_child[ffs(child->pn_popmap) - 1], PCTRIE_NULL, PCTRIE_UNSERIALIZED); - parent->pn_popmap = 0; + child->pn_popmap = 0; } - /* - * Recover the values of the two children of the new parent node. If - * 'node' is not a leaf, this stores into 'newind' the 'owner' field, - * which must be first in the node. - */ - index = *val; - node = pctrie_node_load(parentp, NULL, PCTRIE_UNSERIALIZED); - newind = *pctrie_toval(node); - /* * From the highest-order bit where the indexes differ, * compute the highest level in the trie where they differ. Then, @@ -456,17 +360,33 @@ _Static_assert(sizeof(long long) >= sizeof(uint64_t), "uint64 too wide"); _Static_assert(sizeof(uint64_t) * NBBY <= - (1 << (sizeof(parent->pn_clev) * NBBY)), "pn_clev too narrow"); - parent->pn_clev = rounddown(ilog2(index ^ newind), PCTRIE_WIDTH); - parent->pn_owner = PCTRIE_COUNT; - parent->pn_owner = index & -(parent->pn_owner << parent->pn_clev); + (1 << (sizeof(child->pn_clev) * NBBY)), "pn_clev too narrow"); + child->pn_clev = rounddown(ilog2(index ^ newind), PCTRIE_WIDTH); + child->pn_owner = PCTRIE_COUNT; + child->pn_owner = index & -(child->pn_owner << child->pn_clev); +} +/* + * Uses new node to insert key-value pair into the trie at given location. + */ +void +pctrie_insert_node(smr_pctnode_t *parentp, struct pctrie_node *node, + struct pctrie_node *child, uint64_t *val) +{ + uint64_t index, newind; + + /* + * Recover the values of the two children of the new child node. If + * 'node' is not a leaf, this stores into 'newind' the 'owner' field, + * which must be first in the node. + */ + index = *val; + newind = *pctrie_toval(node); + pctrie_init_node(child, index, newind); /* These writes are not yet visible due to ordering. */ - 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_addnode(child, index, pctrie_toleaf(val)); + pctrie_addnode(child, newind, node); } /* @@ -597,35 +517,35 @@ * to indicate where a new node must be allocated to complete insertion. * Assumes access is externally synchronized by a lock. */ -void * -pctrie_iter_insert_lookup(struct pctrie_iter *it, uint64_t *val) +smr_pctnode_t * +pctrie_iter_insert_lookup(struct pctrie_iter *it, uint64_t index) { - struct pctrie_node *node; + struct pctrie_node *node, *parent; + int slot; - it->index = *val; - node = _pctrie_iter_lookup_node(it, *val, NULL, PCTRIE_LOCKED); - if (node == PCTRIE_NULL) { - if (it->top == 0) - pctrie_node_store(pctrie_root(it->ptree), - pctrie_toleaf(val), PCTRIE_LOCKED); - else - pctrie_addnode(it->path[it->top - 1], it->index, - pctrie_toleaf(val), PCTRIE_LOCKED); - return (NULL); + it->index = index; + node = _pctrie_iter_lookup_node(it, index, NULL, PCTRIE_LOCKED); + if (it->top == 0) + parent = NULL; + else { + parent = it->path[it->top -1]; + slot = pctrie_slot(parent, index); } - if (__predict_false(pctrie_match_value(node, it->index) != NULL)) - panic("%s: key %jx is already present", __func__, - (uintmax_t)it->index); + if (node != PCTRIE_NULL) { + if (__predict_false( + pctrie_match_value(node, index) != NULL)) + panic("%s: key %jx is already present", __func__, + (uintmax_t)index); + } else if (parent != NULL) + parent->pn_popmap ^= 1 << slot; /* - * 'node' must be replaced in the tree with a new branch node, with - * children 'node' and 'val'. Return the place that points to 'node' - * now, and will point to to the new branching node later. + * 'node' must be replaced in the tree with a leaf 'val', or with a new + * branch node, with children 'node' and 'val'. Return the place that + * points to 'node' now, and will point to to the new node later. */ - if (it->top == 0) - return (pctrie_root(it->ptree)); - node = it->path[it->top - 1]; - return (&node->pn_child[pctrie_slot(node, it->index)]); + return (parent == NULL ? pctrie_root(it->ptree) : + &parent->pn_child[slot]); } /* @@ -1027,47 +947,31 @@ } #endif -static void +static smr_pctnode_t * 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 **child) { - struct pctrie_node *child; int slot; - if (node == NULL) { - pctrie_node_store(pctrie_root(ptree), - PCTRIE_NULL, PCTRIE_LOCKED); - return; - } + *child = PCTRIE_NULL; + if (node == NULL) + return (pctrie_root(ptree)); slot = pctrie_slot(node, index); KASSERT((node->pn_popmap & (1 << slot)) != 0, ("%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); if (!powerof2(node->pn_popmap)) - return; + return (&node->pn_child[slot]); + pctrie_node_store(&node->pn_child[slot], PCTRIE_NULL, + PCTRIE_UNSERIALIZED); KASSERT(node->pn_popmap != 0, ("%s: bad popmap all zeroes", __func__)); slot = ffs(node->pn_popmap) - 1; - child = pctrie_node_load(&node->pn_child[slot], NULL, PCTRIE_LOCKED); - KASSERT(child != PCTRIE_NULL, + *child = pctrie_node_load(&node->pn_child[slot], NULL, PCTRIE_LOCKED); + KASSERT(*child != PCTRIE_NULL, ("%s: bad popmap slot %d in node %p", __func__, slot, node)); - if (parent == NULL) - pctrie_node_store(pctrie_root(ptree), child, PCTRIE_LOCKED); - 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); - } - /* - * The child is still valid and we can not zero the - * pointer until all SMR references are gone. - */ - pctrie_node_put(node); - *freenode = node; + return ((parent == NULL) ? pctrie_root(ptree) : + &parent->pn_child[pctrie_slot(parent, index)]); } /* @@ -1076,25 +980,24 @@ */ uint64_t * pctrie_remove_lookup(struct pctrie *ptree, uint64_t index, - struct pctrie_node **freenode) + smr_pctnode_t **parentp, struct pctrie_node **child) { - struct pctrie_node *child, *node, *parent; + struct pctrie_node *next, *node, *parent; uint64_t *m; int slot; DEBUG_POISON_POINTER(parent); - *freenode = node = NULL; - child = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); - while (!pctrie_isleaf(child)) { + node = NULL; + next = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); + while (!pctrie_isleaf(next)) { parent = node; - node = child; + node = next; slot = pctrie_slot(node, index); - child = pctrie_node_load(&node->pn_child[slot], NULL, + next = pctrie_node_load(&node->pn_child[slot], NULL, PCTRIE_LOCKED); } - m = pctrie_match_value(child, index); - if (m != NULL) - pctrie_remove(ptree, index, parent, node, freenode); + if ((m = pctrie_match_value(next, index)) != NULL) + *parentp = pctrie_remove(ptree, index, parent, node, child); return (m); } @@ -1103,29 +1006,30 @@ * 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, + smr_pctnode_t **parentp, struct pctrie_node **child) { - struct pctrie_node *child, *node, *parent; + struct pctrie_node *next, *node, *parent; uint64_t *m; int slot; DEBUG_POISON_POINTER(parent); - *freenode = NULL; if (it->top >= 1) { parent = (it->top >= 2) ? it->path[it->top - 2] : NULL; node = it->path[it->top - 1]; slot = pctrie_slot(node, it->index); - child = pctrie_node_load(&node->pn_child[slot], NULL, + next = pctrie_node_load(&node->pn_child[slot], NULL, PCTRIE_LOCKED); } else { node = NULL; - child = pctrie_root_load(it->ptree, NULL, PCTRIE_LOCKED); + next = pctrie_root_load(it->ptree, NULL, PCTRIE_LOCKED); + } + if ((m = pctrie_match_value(next, it->index)) != NULL) { + *parentp = pctrie_remove(it->ptree, it->index, parent, node, + child); + if (*child != PCTRIE_NULL) + --it->top; } - m = pctrie_match_value(child, it->index); - if (m != NULL) - pctrie_remove(it->ptree, it->index, parent, node, freenode); - if (*freenode != NULL) - --it->top; return (m); } @@ -1259,27 +1163,24 @@ * 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, + smr_pctnode_t **parentp, struct pctrie_node **child) { - struct pctrie_node *leaf, *parent, *node; + struct pctrie_node *parent, *node; uint64_t *m; uint64_t index; int slot; - leaf = pctrie_toleaf(newval); + *child = pctrie_toleaf(newval); index = *newval; node = pctrie_root_load(ptree, NULL, PCTRIE_LOCKED); parent = NULL; for (;;) { if (pctrie_isleaf(node)) { if ((m = pctrie_toval(node)) != NULL && *m == index) { - if (parent == NULL) - pctrie_node_store(pctrie_root(ptree), - leaf, PCTRIE_LOCKED); - else - pctrie_node_store( - &parent->pn_child[slot], leaf, - PCTRIE_LOCKED); + *parentp = (parent == NULL) ? + pctrie_root(ptree): + &parent->pn_child[slot]; return (m); } break; Index: sys/sys/pctrie.h =================================================================== --- sys/sys/pctrie.h +++ sys/sys/pctrie.h @@ -33,13 +33,78 @@ #include #include +#include /* smr.h depends on struct thread. */ +#include +#include +struct pctrie_node; +typedef SMR_POINTER(struct pctrie_node *) smr_pctnode_t; #ifdef _KERNEL typedef void (*pctrie_cb_t)(void *ptr, void *arg); +/* + * Each search path in the trie terminates at a leaf, which is a pointer to a + * value marked with a set 1-bit. A leaf may be associated with a null pointer + * to indicate no value there. + */ +#define PCTRIE_ISLEAF 0x1 +#define PCTRIE_NULL (struct pctrie_node *)PCTRIE_ISLEAF + +enum pctrie_access { PCTRIE_SMR, PCTRIE_LOCKED, PCTRIE_UNSERIALIZED }; + +/* + * Fetch a node pointer from a slot. + */ +static __inline struct pctrie_node * +pctrie_node_load(smr_pctnode_t *p, smr_t smr, enum pctrie_access access) +{ + switch (access) { + case PCTRIE_UNSERIALIZED: + return (smr_unserialized_load(p, true)); + case PCTRIE_LOCKED: + return (smr_serialized_load(p, true)); + case PCTRIE_SMR: + return (smr_entered_load(p, smr)); + } + __assert_unreachable(); +} + +static __inline void +pctrie_node_store(smr_pctnode_t *p, void *v, enum pctrie_access access) +{ + switch (access) { + case PCTRIE_UNSERIALIZED: + smr_unserialized_store(p, v, true); + break; + case PCTRIE_LOCKED: + smr_serialized_store(p, v, true); + break; + case PCTRIE_SMR: + panic("%s: Not supported in SMR section.", __func__); + break; + default: + __assert_unreachable(); + break; + } +} + +/* + * Returns val with leaf bit set. + */ +static __inline void * +pctrie_toleaf(uint64_t *val) +{ + return ((void *)((uintptr_t)val | PCTRIE_ISLEAF)); +} + +#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) \ @@ -47,7 +112,7 @@ \ return name##_PCTRIE_VAL2PTR(pctrie_lookup_unlocked(ptree, \ key, (smr))); \ -} \ +} #ifdef INVARIANTS void pctrie_subtree_lookup_gt_assert(struct pctrie_node *node, @@ -59,14 +124,14 @@ #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)); \ /* \ * XXX This assert protects flag bits, it does not enforce natural \ * alignment. 32bit architectures do not naturally align 64bit fields. \ */ \ -CTASSERT((__offsetof(struct type, field) & (sizeof(uint32_t) - 1)) == 0); \ +CTASSERT((__offsetof(struct type, field) & (sizeof(uint32_t)-1)) == 0); \ \ static __inline struct type * \ name##_PCTRIE_VAL2PTR(uint64_t *val) \ @@ -86,34 +151,38 @@ } \ \ static __inline __unused int \ -name##_PCTRIE_INSERT_BASE(struct pctrie *ptree, void *parentp, \ +name##_PCTRIE_INSERT_BASE(struct pctrie *ptree, smr_pctnode_t *parentp, \ uint64_t *val, uint64_t *found, struct type **found_out) \ { \ - struct pctrie_node *parent; \ + struct pctrie_node *child, *node; \ \ if (__predict_false(found != NULL)) { \ *found_out = name##_PCTRIE_VAL2PTR(found); \ return (EEXIST); \ } \ - if (parentp != NULL) { \ - parent = allocfn(ptree); \ - if (__predict_false(parent == NULL)) { \ + node = pctrie_node_load(parentp, NULL, PCTRIE_UNSERIALIZED); \ + if (node != PCTRIE_NULL) { \ + child = allocfn(ptree); \ + if (__predict_false(child == NULL)) { \ if (found_out != NULL) \ *found_out = NULL; \ return (ENOMEM); \ } \ - pctrie_insert_node(parentp, parent, val); \ - } \ + pctrie_insert_node(parentp, node, child, val); \ + } else \ + child = pctrie_toleaf(val); \ + /* Synchronize to make changes visible. */ \ + pctrie_node_store(parentp, child, access); \ return (0); \ } \ \ static __inline __unused int \ name##_PCTRIE_INSERT(struct pctrie *ptree, struct type *ptr) \ { \ - void *parentp; \ + smr_pctnode_t *parentp; \ uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \ \ - parentp = pctrie_insert_lookup_strict(ptree, val); \ + parentp = pctrie_insert_lookup_strict(ptree, *val); \ return (name##_PCTRIE_INSERT_BASE(ptree, parentp, val, \ NULL, NULL)); \ } \ @@ -122,11 +191,11 @@ name##_PCTRIE_FIND_OR_INSERT(struct pctrie *ptree, struct type *ptr, \ struct type **found_out_opt) \ { \ - void *parentp; \ + smr_pctnode_t *parentp; \ uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \ uint64_t *found; \ \ - parentp = pctrie_insert_lookup(ptree, val, &found); \ + parentp = pctrie_insert_lookup(ptree, *val, &found); \ return (name##_PCTRIE_INSERT_BASE(ptree, parentp, val, \ found, found_out_opt)); \ } \ @@ -136,12 +205,12 @@ struct type **found_out) \ { \ struct pctrie_node *neighbor; \ - void *parentp; \ + smr_pctnode_t *parentp; \ uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \ uint64_t *found; \ int retval; \ \ - parentp = pctrie_insert_lookup_gt(ptree, val, &found, \ + parentp = pctrie_insert_lookup_gt(ptree, *val, &found, \ &neighbor); \ retval = name##_PCTRIE_INSERT_BASE(ptree, parentp, val, \ found, found_out); \ @@ -158,12 +227,12 @@ struct type **found_out) \ { \ struct pctrie_node *neighbor; \ - void *parentp; \ + smr_pctnode_t *parentp; \ uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \ uint64_t *found; \ int retval; \ \ - parentp = pctrie_insert_lookup_lt(ptree, val, &found, \ + parentp = pctrie_insert_lookup_lt(ptree, *val, &found, \ &neighbor); \ retval = name##_PCTRIE_INSERT_BASE(ptree, parentp, val, \ found, found_out); \ @@ -229,18 +298,22 @@ static __inline __unused int \ name##_PCTRIE_ITER_INSERT(struct pctrie_iter *it, struct type *ptr) \ { \ - struct pctrie_node *parent; \ - void *parentp; \ + smr_pctnode_t *parentp; \ + struct pctrie_node *node; \ uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \ + int retval; \ \ - parentp = pctrie_iter_insert_lookup(it, val); \ - if (parentp == NULL) \ - return (0); \ - parent = allocfn(it->ptree); \ - if (__predict_false(parent == NULL)) \ - return (ENOMEM); \ - pctrie_insert_node(parentp, parent, val); \ - it->path[it->top++] = parent; \ + parentp = pctrie_iter_insert_lookup(it, *val); \ + node = pctrie_node_load(parentp, NULL, PCTRIE_UNSERIALIZED); \ + retval = name##_PCTRIE_INSERT_BASE(it->ptree, parentp, val, \ + NULL, NULL); \ + if (retval != 0) \ + return (retval); \ + if (node != PCTRIE_NULL) { \ + node = pctrie_node_load(parentp, NULL, \ + PCTRIE_UNSERIALIZED); \ + it->path[it->top++] = node; \ + } \ return (0); \ } \ \ @@ -312,8 +385,17 @@ \ static __inline __unused void \ name##_PCTRIE_REMOVE_BASE(struct pctrie *ptree, \ - struct pctrie_node *freenode) \ + smr_pctnode_t *parentp, struct pctrie_node *child) \ { \ + struct pctrie_node *freenode; \ + \ + if (child != PCTRIE_NULL) { \ + freenode = pctrie_node_load(parentp, NULL, \ + PCTRIE_UNSERIALIZED); \ + } else \ + freenode = NULL; \ + /* Synchronize to make changes visible. */ \ + pctrie_node_store(parentp, child, access); \ if (freenode != NULL) \ freefn(ptree, freenode); \ } \ @@ -322,56 +404,68 @@ name##_PCTRIE_ITER_REMOVE(struct pctrie_iter *it) \ { \ uint64_t *val; \ - struct pctrie_node *freenode; \ + smr_pctnode_t *parentp; \ + struct pctrie_node *child; \ \ - val = pctrie_iter_remove(it, &freenode); \ + val = pctrie_iter_remove(it, &parentp, &child); \ if (val == NULL) \ panic("%s: key not found", __func__); \ - name##_PCTRIE_REMOVE_BASE(it->ptree, freenode); \ + name##_PCTRIE_REMOVE_BASE(it->ptree, parentp, child); \ } \ \ 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))); \ + smr_pctnode_t *parentp; \ + struct type *res; \ + struct pctrie_node *child; \ + \ + res = name##_PCTRIE_VAL2PTR( \ + pctrie_replace(ptree, name##_PCTRIE_PTR2VAL(ptr), \ + &parentp, &child)); \ + /* Synchronize to make changes visible. */ \ + pctrie_node_store(parentp, child, access); \ + return (res); \ } \ \ static __inline __unused void \ name##_PCTRIE_REMOVE(struct pctrie *ptree, uint64_t key) \ { \ uint64_t *val; \ - struct pctrie_node *freenode; \ + smr_pctnode_t *parentp; \ + struct pctrie_node *child; \ \ - val = pctrie_remove_lookup(ptree, key, &freenode); \ + val = pctrie_remove_lookup(ptree, key, &parentp, &child); \ if (val == NULL) \ panic("%s: key not found", __func__); \ - name##_PCTRIE_REMOVE_BASE(ptree, freenode); \ + name##_PCTRIE_REMOVE_BASE(ptree, parentp, child); \ } \ \ static __inline __unused struct type * \ name##_PCTRIE_REMOVE_LOOKUP(struct pctrie *ptree, uint64_t key) \ { \ uint64_t *val; \ - struct pctrie_node *freenode; \ + smr_pctnode_t *parentp; \ + struct pctrie_node *child; \ \ - val = pctrie_remove_lookup(ptree, key, &freenode); \ - name##_PCTRIE_REMOVE_BASE(ptree, freenode); \ - return name##_PCTRIE_VAL2PTR(val); \ + val = pctrie_remove_lookup(ptree, key, &parentp, &child); \ + if (val != NULL) \ + name##_PCTRIE_REMOVE_BASE(ptree, parentp, child); \ + return (name##_PCTRIE_VAL2PTR(val)); \ } struct pctrie_iter; -void *pctrie_insert_lookup(struct pctrie *ptree, uint64_t *val, +smr_pctnode_t *pctrie_insert_lookup(struct pctrie *ptree, uint64_t index, uint64_t **found_out); -void *pctrie_insert_lookup_gt(struct pctrie *ptree, uint64_t *val, +smr_pctnode_t *pctrie_insert_lookup_gt(struct pctrie *ptree, uint64_t index, uint64_t **found_out, struct pctrie_node **neighbor_out); -void *pctrie_insert_lookup_lt(struct pctrie *ptree, uint64_t *val, +smr_pctnode_t *pctrie_insert_lookup_lt(struct pctrie *ptree, uint64_t index, uint64_t **found_out, struct pctrie_node **neighbor_out); -void *pctrie_insert_lookup_strict(struct pctrie *ptree, +smr_pctnode_t *pctrie_insert_lookup_strict(struct pctrie *ptree, + uint64_t index); +void pctrie_insert_node(smr_pctnode_t *parentp, + struct pctrie_node *node, struct pctrie_node *child, uint64_t *val); -void pctrie_insert_node(void *parentp, - struct pctrie_node *parent, uint64_t *val); uint64_t *pctrie_lookup(struct pctrie *ptree, uint64_t key); uint64_t *pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t key, smr_t smr); @@ -379,8 +473,8 @@ uint64_t *pctrie_iter_stride(struct pctrie_iter *it, int stride); 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); +smr_pctnode_t *pctrie_iter_insert_lookup(struct pctrie_iter *it, + uint64_t index); uint64_t *pctrie_lookup_ge(struct pctrie *ptree, uint64_t key); uint64_t *pctrie_subtree_lookup_gt(struct pctrie_node *node, uint64_t key); @@ -400,22 +494,15 @@ 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); + smr_pctnode_t **parentp, struct pctrie_node **child); uint64_t *pctrie_iter_remove(struct pctrie_iter *it, - struct pctrie_node **freenode); + smr_pctnode_t **parentp, struct pctrie_node **child); 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, + smr_pctnode_t **parentp, struct pctrie_node **child); size_t pctrie_node_size(void); int pctrie_zone_init(void *mem, int size, int flags); -/* - * Each search path in the trie terminates at a leaf, which is a pointer to a - * value marked with a set 1-bit. A leaf may be associated with a null pointer - * to indicate no value there. - */ -#define PCTRIE_ISLEAF 0x1 -#define PCTRIE_NULL (struct pctrie_node *)PCTRIE_ISLEAF - static __inline void pctrie_init(struct pctrie *ptree) {