diff --git a/sys/kern/subr_pctrie.c b/sys/kern/subr_pctrie.c --- a/sys/kern/subr_pctrie.c +++ b/sys/kern/subr_pctrie.c @@ -418,14 +418,9 @@ neighbor_out, PCTRIE_INSERT_NEIGHBOR_LT)); } -/* - * 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) +static void +pctrie_init_node(struct pctrie_node *parent, 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 @@ -439,15 +434,6 @@ parent->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, @@ -460,7 +446,26 @@ parent->pn_clev = rounddown(ilog2(index ^ newind), PCTRIE_WIDTH); parent->pn_owner = PCTRIE_COUNT; parent->pn_owner = index & -(parent->pn_owner << parent->pn_clev); +} + +/* + * 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) +{ + struct pctrie_node *node; + uint64_t index, newind; + /* + * 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); + pctrie_init_node(parent, index, newind); /* These writes are not yet visible due to ordering. */ pctrie_addnode(parent, index, pctrie_toleaf(val), PCTRIE_UNSERIALIZED); @@ -678,6 +683,170 @@ return (_pctrie_iter_stride(it, -1, NULL, PCTRIE_LOCKED)); } +static int +pctrie_addnode_batch(struct pctrie_node *node, uintptr_t *arr, int nitems, + uint64_t index, const uintptr_t offs) +{ + int slot, n; + uint64_t *val; + pn_popmap_t mask; + + MPASS(nitems > 1); + KASSERT(node->pn_clev == 0, + ("%s: node %p has nonzero clev", __func__, node)); + + slot = pctrie_slot(node, index); + nitems = min(nitems, PCTRIE_COUNT - slot); + mask = ((1 << nitems) - 1) << slot; + node->pn_popmap ^= mask; + if ((node->pn_popmap & mask) != mask) + panic("%s: bad popmap in node %p: %04x", __func__, + node, node->pn_popmap); + + for (n = 0; n < nitems - 1; n++) { + KASSERT(arr[n] != (uintptr_t)NULL, + ("%s: value at index %d is NULL", __func__, n)); + val = (uint64_t *)(arr[n] + offs); + *val = index + n; + pctrie_node_store(&node->pn_child[slot + n], pctrie_toleaf(val), + PCTRIE_UNSERIALIZED); + } + KASSERT(arr[n] != (uintptr_t)NULL, + ("%s: value at index %d is NULL", __func__, n)); + val = (uint64_t *)(arr[n] + offs); + *val = index + n; + pctrie_node_store(&node->pn_child[slot + n], pctrie_toleaf(val), + PCTRIE_LOCKED); + + return (nitems); +} + +/* + * Looks up 'index' key and records information required to + * insert a clev 0 node containing the target key. + */ +int +pctrie_batch_insert_lookup(struct pctrie_iter *it, + struct pctrie_batch_lookup_result *res, uintptr_t *arr, int nitems, + uint64_t index, const uintptr_t offs) +{ + struct pctrie_node *node, *parent; + + node = _pctrie_iter_lookup_node(it, index, NULL, PCTRIE_LOCKED); + parent = (it->top - 1 >= 0) ? it->path[it->top - 1] : NULL; + if (node != PCTRIE_NULL) { + if (pctrie_isleaf(node) && + (*pctrie_toval(node) >> PCTRIE_WIDTH) == + (index >> PCTRIE_WIDTH)) { + res->action = PCTRIE_BATCH_ALLOC_INSERT; + res->oldval = node; + } else { + res->action = PCTRIE_BATCH_SPLIT; + res->oldval = PCTRIE_NULL; + } + } else if (parent != NULL && parent->pn_clev == 0) { + res->action = PCTRIE_BATCH_FOUND; + return (pctrie_addnode_batch(parent, arr, nitems, index, offs)); + } else { + res->action = PCTRIE_BATCH_ALLOC_INSERT; + res->oldval = PCTRIE_NULL; + } + + return (0); +} + +/* + * Attempts to insert an array of items starting from 'index' + * using a previously filled batch lookup result structure. + * + * Returns the number of inserted items. + */ +int +pctrie_batch_insert(struct pctrie_iter *it, + struct pctrie_batch_lookup_result *res, uintptr_t *arr, int nitems, + uint64_t index, const uintptr_t offs) +{ + int slot; + void *parentp; + uint64_t *val; + uint64_t oldval; + struct pctrie_node *parent; + + MPASS(nitems > 1); + parent = (it->top - 1 >= 0) ? it->path[it->top - 1] : NULL; + switch (res->action) { + case PCTRIE_BATCH_SPLIT: + if (__predict_false(res->new_parent == NULL)) + return (0); + if (__predict_false(parent == NULL)) + parentp = (void *)&it->ptree->pt_root; + else + parentp = (void *)&parent->pn_child[pctrie_slot( + parent, index)]; + parent = pctrie_node_load(parentp, NULL, PCTRIE_UNSERIALIZED); + oldval = *pctrie_toval(parent); + pctrie_init_node(res->new_parent, index, oldval); + pctrie_addnode(res->new_parent, oldval, parent, + PCTRIE_UNSERIALIZED); + pctrie_node_store(parentp, res->new_parent, + PCTRIE_UNSERIALIZED); + parent = res->new_parent; + case PCTRIE_BATCH_ALLOC_INSERT: + if (__predict_false(res->node == NULL)) { + if (res->action == PCTRIE_BATCH_SPLIT) { + /* + * Node allocation failed after a + * successful split. Store the current + * value into the appropriate slot + * and return. + */ + val = (uint64_t *)(arr[0] + offs); + *val = index; + pctrie_addnode(parent, index, + pctrie_toleaf(val), PCTRIE_LOCKED); + } + return (1); + } + + /* + * We're inserting a clev 0 node. Pass + * newind = 1 ^ index so pctrie_init_node + * sets pn_clev to 0. + */ + pctrie_init_node(res->node, index, 1 ^ index); + if (__predict_false(parent == NULL)) + pctrie_node_store((void *)&it->ptree->pt_root, + res->node, PCTRIE_UNSERIALIZED); + else { + slot = pctrie_slot(parent, index); + pctrie_node_store(&parent->pn_child[slot], + res->node, PCTRIE_UNSERIALIZED); + if (res->oldval == PCTRIE_NULL) { + parent->pn_popmap ^= 1 << slot; + KASSERT((parent->pn_popmap & (1 << slot)) + != 0, + ("%s: bad popmap slot %d in node %p", + __func__, slot, parent)); + } + } + if (res->oldval != PCTRIE_NULL) { + + /* + * Restore the old leaf value that was present + * in the target parent slot, if any. + */ + MPASS(!pctrie_keybarr(res->node, + *pctrie_toval(res->oldval), &slot)); + pctrie_addnode(res->node, *pctrie_toval(res->oldval), + res->oldval, PCTRIE_UNSERIALIZED); + } + case PCTRIE_BATCH_FOUND: + break; + } + + return (pctrie_addnode_batch(res->node, arr, nitems, index, offs)); +} + /* * Returns the value with the least index that is greater than or equal to the * specified index, or NULL if there are no such values. diff --git a/sys/sys/pctrie.h b/sys/sys/pctrie.h --- a/sys/sys/pctrie.h +++ b/sys/sys/pctrie.h @@ -36,6 +36,17 @@ #ifdef _KERNEL +struct pctrie_batch_lookup_result { + enum { + PCTRIE_BATCH_FOUND, + PCTRIE_BATCH_SPLIT, + PCTRIE_BATCH_ALLOC_INSERT + } action; + struct pctrie_node *node; + struct pctrie_node *new_parent; + struct pctrie_node *oldval; +}; + typedef void (*pctrie_cb_t)(void *ptr, void *arg); #define PCTRIE_DEFINE_SMR(name, type, field, allocfn, freefn, smr) \ @@ -310,6 +321,55 @@ return name##_PCTRIE_VAL2PTR(pctrie_iter_jump_le(it, 1)); \ } \ \ +static __inline __unused int \ +name##_PCTRIE_INSERT_BATCH(struct pctrie_iter *it, struct type **arr, \ + uint64_t start, int nitems) \ +{ \ + uint64_t index; \ + int ninserted, total; \ + struct pctrie_batch_lookup_result res; \ + \ + total = 0; \ + if (__predict_false((start + 1) % PCTRIE_COUNT == 0)) { \ + *name##_PCTRIE_PTR2VAL(arr[0]) = start; \ + if (name##_PCTRIE_ITER_INSERT(it, arr[0]) == ENOMEM) \ + return (0); \ + total++; \ + } \ + while (total < nitems - 1) { \ + index = start + total; \ + ninserted = pctrie_batch_insert_lookup(it, &res, \ + (uintptr_t *)&arr[total], nitems - total, \ + index, __offsetof(struct type, field)); \ + switch (res.action) { \ + case PCTRIE_BATCH_SPLIT: \ + res.new_parent = allocfn(it->ptree); \ + case PCTRIE_BATCH_ALLOC_INSERT: \ + if (__predict_false(res.action == \ + PCTRIE_BATCH_SPLIT && \ + res.new_parent == NULL)) \ + break; \ + res.node = allocfn(it->ptree); \ + break; \ + case PCTRIE_BATCH_FOUND: \ + total += ninserted; \ + continue; \ + } \ + ninserted = pctrie_batch_insert(it, &res, \ + (uintptr_t *)&arr[total], nitems - total, \ + index, __offsetof(struct type, field)); \ + if (__predict_false(ninserted == 1)) \ + return (total + 1); \ + total += ninserted; \ + } \ + if (total != nitems) { \ + *name##_PCTRIE_PTR2VAL(arr[total]) = start + total; \ + if (name##_PCTRIE_ITER_INSERT(it, arr[total]) == 0) \ + total++; \ + } \ + return (total); \ +} \ + \ static __inline __unused void \ name##_PCTRIE_REMOVE_BASE(struct pctrie *ptree, \ struct pctrie_node *freenode) \ @@ -372,6 +432,12 @@ uint64_t *val); void pctrie_insert_node(void *parentp, struct pctrie_node *parent, uint64_t *val); +int pctrie_batch_insert(struct pctrie_iter *it, + struct pctrie_batch_lookup_result *res, uintptr_t *arr, + int nitems, uint64_t index, const uintptr_t offs); +int pctrie_batch_insert_lookup(struct pctrie_iter *it, + struct pctrie_batch_lookup_result *res, uintptr_t *arr, + int nitems, uint64_t index, const uintptr_t offs); uint64_t *pctrie_lookup(struct pctrie *ptree, uint64_t key); uint64_t *pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t key, smr_t smr);