Page MenuHomeFreeBSD
Files F153399632

D47044.id146002.diff
No OneTemporary
Actions

D47044.id146002.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);
@@ -630,6 +635,24 @@
return (&node->pn_child[pctrie_slot(node, it->index)]);
}
+int
+pctrie_iter_insert(struct pctrie_iter *it, uint64_t *val,
+ pctrie_allocfn_t allocfn)
+{
+ struct pctrie_node *parent;
+ void *parentp;
+
+ 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);
+
+ return (0);
+}
+
/*
* Returns the value stored at a fixed offset from the current index value,
* possibly NULL.
@@ -680,6 +703,172 @@
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, uintptr_t offs, pctrie_allocfn_t allocfn)
+{
+ 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;
+ if (__predict_false(pctrie_iter_insert(it, val, allocfn) != 0))
+ return (0);
+ 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:
+ node = allocfn(it->ptree);
+ if (__predict_false(node == NULL))
+ return (total);
+ 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:
+ node = allocfn(it->ptree);
+ if (__predict_false(node == NULL)) {
+ if (rv == SPLIT) {
+
+ /*
+ * Node allocation failed after a
+ * successful split. Store the current
+ * value into the appropriate slot
+ * and return.
+ */
+ pctrie_addnode(next, index,
+ pctrie_toleaf(val), PCTRIE_LOCKED);
+ total++;
+ }
+ return (total);
+ }
+
+ /*
+ * 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;
+ if (__predict_false(pctrie_iter_insert(it, val, allocfn) != 0))
+ return (0);
+ 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
@@ -37,6 +37,7 @@
#ifdef _KERNEL
typedef void (*pctrie_cb_t)(void *ptr, void *arg);
+typedef void *(*pctrie_allocfn_t)(struct pctrie *);
#define PCTRIE_DEFINE_SMR(name, type, field, allocfn, freefn, smr) \
PCTRIE_DEFINE(name, type, field, allocfn, freefn) \
@@ -175,6 +176,14 @@
return (0); \
} \
\
+static __inline __unused int \
+name##_PCTRIE_INSERT_BATCH(struct pctrie_iter *it, \
+ struct type **arr, uint64_t start, int nitems) \
+{ \
+ return (pctrie_batch_insert(it, (uintptr_t *)arr, start, \
+ nitems, __offsetof(struct type, field), allocfn)); \
+} \
+ \
static __inline __unused struct type * \
name##_PCTRIE_LOOKUP(struct pctrie *ptree, uint64_t key) \
{ \
@@ -229,19 +238,8 @@
static __inline __unused int \
name##_PCTRIE_ITER_INSERT(struct pctrie_iter *it, struct type *ptr) \
{ \
- struct pctrie_node *parent; \
- void *parentp; \
- uint64_t *val = name##_PCTRIE_PTR2VAL(ptr); \
- \
- 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; \
- return (0); \
+ return (pctrie_iter_insert(it, name##_PCTRIE_PTR2VAL(ptr), \
+ allocfn)); \
} \
\
static __inline __unused struct type * \
@@ -372,6 +370,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, uintptr_t offs,
+ pctrie_allocfn_t allocfn);
uint64_t *pctrie_lookup(struct pctrie *ptree, uint64_t key);
uint64_t *pctrie_lookup_unlocked(struct pctrie *ptree, uint64_t key,
smr_t smr);
@@ -381,6 +382,8 @@
uint64_t *pctrie_iter_prev(struct pctrie_iter *it);
void *pctrie_iter_insert_lookup(struct pctrie_iter *it,
uint64_t *val);
+int pctrie_iter_insert(struct pctrie_iter *it, uint64_t *val,
+ pctrie_allocfn_t allocfn);
uint64_t *pctrie_lookup_ge(struct pctrie *ptree, uint64_t key);
uint64_t *pctrie_subtree_lookup_gt(struct pctrie_node *node,
uint64_t key);

File Metadata

Mime Type
text/plain
Expires
Tue, Apr 21, 10:46 PM (9 h, 16 s)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
31937547
Default Alt Text
D47044.id146002.diff (9 KB)

Event Timeline