Page MenuHomeFreeBSD
Files F101977253

D47044.diff
No OneTemporary
Actions

D47044.diff
View Options

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
@@ -420,14 +420,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
@@ -441,15 +436,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,
@@ -462,7 +448,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);
@@ -680,6 +685,184 @@
return (_pctrie_iter_stride(it, -1, NULL, PCTRIE_LOCKED));
}
+/*
+ * Attempts to insert an array of items into a 0-level node.
+ *
+ * Returns the number of inserted items.
+ */
+static int
+pctrie_addnode_batch(struct pctrie_node *node, uintptr_t *arr,
+ int nitems, uint64_t index, 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;
+ KASSERT((node->pn_popmap & mask) == mask,
+ ("%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);
+}
+
+/*
+ * Attempts to insert an array of elements into the pctrie
+ * starting from key 'start'.
+ * Panics if a key is already present.
+ *
+ * Returns the number of inserted items.
+ */
+int
+pctrie_batch_insert(struct pctrie_iter *it, uintptr_t *arr, uint64_t start,
+ int nitems, struct pctrie_node **nodes,
+ int *nnodes, const uintptr_t offs)
+{
+ int total;
+ void *parentp;
+ uint64_t oldval;
+ uint64_t *val, index;
+ struct pctrie_node *parent;
+ struct pctrie_node *next, *node;
+ enum { FOUND, SPLIT, ALLOC_INSERT } rv;
+
+ val = pctrie_iter_lookup_ge(it, start);
+ if (val != NULL && *val <= start + nitems - 1)
+ panic("%s: key '%lu' already present", __func__, *val);
+ total = 0;
+ if (__predict_false((start + 1) % PCTRIE_COUNT == 0)) {
+
+ /*
+ * We're inserting into the last node slot and
+ * potentially violating path compression by
+ * allocating a whole node for a single element.
+ * Avoid this by simply inserting the current
+ * value into the tree.
+ */
+ val = (uint64_t *)(arr[total] + offs);
+ *val = start;
+ parentp = pctrie_iter_insert_lookup(it, val);
+ if (parentp != NULL) {
+ if (__predict_false(*nnodes == 0))
+ return (total);
+ node = nodes[--(*nnodes)];
+ pctrie_insert_node(parentp, node, val);
+ }
+ total++;
+ }
+ while (total < nitems - 1) {
+ val = (uint64_t *)(arr[total] + offs);
+ index = start + total;
+ node = _pctrie_iter_lookup_node(it, index, NULL, PCTRIE_LOCKED);
+ next = (it->top - 1 >= 0) ? it->path[it->top - 1] : NULL;
+ if (!pctrie_isleaf(node) || node != PCTRIE_NULL)
+ rv = SPLIT;
+ else if (next != NULL && next->pn_clev == 0)
+ rv = FOUND;
+ else
+ rv = ALLOC_INSERT;
+
+ switch (rv) {
+ case SPLIT:
+ if (__predict_false(*nnodes == 0))
+ return (total);
+ node = nodes[--(*nnodes)];
+ if (__predict_false(next == NULL))
+ parentp = (void *)&it->ptree->pt_root;
+ else
+ parentp = (void *)&next->pn_child[pctrie_slot(next, index)];
+ parent = pctrie_node_load(parentp, NULL,
+ PCTRIE_UNSERIALIZED);
+ oldval = *pctrie_toval(parent);
+ pctrie_init_node(node, index, oldval);
+ pctrie_addnode(node, oldval,
+ parent, PCTRIE_UNSERIALIZED);
+ pctrie_node_store(parentp, node, PCTRIE_UNSERIALIZED);
+ if (node->pn_clev == 0) {
+ total += pctrie_addnode_batch(node,
+ &arr[total], nitems - total,
+ index, offs);
+ break;
+ }
+ next = node;
+ /* FALLTHROUGH */
+ case ALLOC_INSERT:
+ if (__predict_false(*nnodes == 0)) {
+ if (rv == SPLIT) {
+
+ /*
+ * Node allocation failed after a
+ * successful split. Store the current
+ * value into the appropriate slot
+ * and return.
+ */
+ *val = index;
+ pctrie_addnode(next, index,
+ pctrie_toleaf(val), PCTRIE_LOCKED);
+ total++;
+ }
+ return (total);
+ }
+ node = nodes[--(*nnodes)];
+
+ /*
+ * We're inserting a clev 0 node. Pass
+ * newind = 1 ^ index so pctrie_init_node
+ * sets pn_clev to 0.
+ */
+ pctrie_init_node(node, index, 1 ^ index);
+ if (__predict_false(next == NULL))
+ pctrie_node_store((void *)&it->ptree->pt_root,
+ node, PCTRIE_UNSERIALIZED);
+ else
+ pctrie_addnode(next, index, node,
+ PCTRIE_UNSERIALIZED);
+ next = node;
+ /* FALLTHROUGH */
+ case FOUND:
+ total += pctrie_addnode_batch(next,
+ &arr[total], nitems - total, index, offs);
+ break;
+ }
+ }
+ if (total != nitems) {
+ val = (uint64_t *)(arr[total] + offs);
+ *val = start + total;
+ parentp = pctrie_iter_insert_lookup(it, val);
+ if (parentp != NULL) {
+ if (__predict_false(*nnodes == 0))
+ return (total);
+ node = nodes[--(*nnodes)];
+ pctrie_insert_node(parentp, node, val);
+ }
+ total++;
+ }
+
+ return (total);
+}
+
/*
* 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
@@ -175,6 +175,26 @@
return (0); \
} \
\
+static __inline __unused int \
+name##_PCTRIE_INSERT_BATCH(struct pctrie_iter *it, \
+ struct type **arr, uint64_t start, int nitems) \
+{ \
+ int i, ninserted; \
+ const int nnodes = (nitems / PCTRIE_COUNT) + 2; \
+ struct pctrie_node *nodes[nnodes]; \
+ \
+ for (i = 0; i < nnodes; i++) { \
+ nodes[i] = allocfn(it->ptree); \
+ if(nodes[i] == NULL) \
+ break; \
+ } \
+ ninserted = pctrie_batch_insert(it, (uintptr_t *)arr, start, \
+ nitems, nodes, &i, __offsetof(struct type, field)); \
+ while (i > 0) \
+ freefn(it->ptree, nodes[--i]); \
+ return (ninserted); \
+} \
+ \
static __inline __unused struct type * \
name##_PCTRIE_LOOKUP(struct pctrie *ptree, uint64_t key) \
{ \
@@ -372,6 +392,9 @@
uint64_t *val);
void pctrie_insert_node(void *parentp,
struct pctrie_node *parent, uint64_t *val);
+int pctrie_batch_insert(struct pctrie_iter *it, uintptr_t *arr,
+ uint64_t start, int nitems, struct pctrie_node **nodes,
+ int *nnodes, 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);

File Metadata

Mime Type
text/plain
Expires
Thu, Nov 7, 1:56 AM (21 h, 15 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
14503165
Default Alt Text
D47044.diff (8 KB)

Event Timeline