Page MenuHomeFreeBSD
Files F108325981

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

File Metadata

Mime Type
text/plain
Expires
Fri, Jan 24, 9:28 PM (20 h, 58 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
16104777
Default Alt Text
D47044.diff (9 KB)

Event Timeline