Page MenuHomeFreeBSD
Files F169118968

D47744.diff
No OneTemporary
Actions

D47744.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
@@ -685,6 +685,198 @@
return (_pctrie_iter_stride(it, -1, NULL, PCTRIE_LOCKED));
}
+/*
+ * Returns the number of nodes required to insert
+ * keys from [0, end).
+ */
+static __inline int
+pctrie_subtree_nnodes(uint64_t end)
+{
+ int cnt, clev;
+ uint64_t rem, nitems_slot;
+
+ cnt = 0;
+ rem = roundup2(end, PCTRIE_COUNT);
+ while (rem > 0) {
+ clev = rounddown(ilog2(rem), PCTRIE_WIDTH);
+ if (rem == (1 << clev)) {
+ cnt += rem / (PCTRIE_COUNT - 1);
+ break;
+ }
+ nitems_slot = 1 << clev;
+ cnt += (rem / nitems_slot) *
+ (nitems_slot / (PCTRIE_COUNT - 1)) +
+ 1;
+ rem = rem & (nitems_slot - 1);
+ }
+ return (cnt);
+}
+
+/*
+ * Returns the number of nodes required to insert
+ * keys from [start, end).
+ */
+int
+pctrie_iter_range_nnodes(struct pctrie_iter *it, uint64_t start,
+ uint64_t end)
+{
+ int cnt, clev, slot;
+ struct pctrie_node *parent;
+ int rclev, lclev, vclev, top;
+ uint64_t owner, nitems_slot, val;
+ uint64_t lbound, end_round, start_round;
+
+ MPASS((end - start) > 1);
+
+ /*
+ * Find the height and owner of the smallest subtree
+ * covering [start, end).
+ */
+ clev = rounddown(ilog2(start ^ (end - 1)), PCTRIE_WIDTH);
+ owner = start & -(PCTRIE_COUNT << clev);
+ start -= owner;
+ end -= owner;
+
+ /*
+ * Find and calculate the heights of the leftmost
+ * and rightmost subtrees, i.e., the trees inserted
+ * into the first and last last slot of the top-level node.
+ * This information will be used to account for any existing
+ * nodes when inserting into a non-empty tree.
+ */
+ nitems_slot = clev != 0 ? PCTRIE_COUNT << (clev - PCTRIE_WIDTH) : 1;
+ lbound = roundup2(start, nitems_slot);
+ rclev = (end - 1) % nitems_slot != 0 ?
+ rounddown(ilog2((end - 1) ^ rounddown2(end - 1, nitems_slot)),
+ PCTRIE_WIDTH) :
+ 0;
+ lclev = lbound != start && (lbound - 1) != start ?
+ rounddown(ilog2((lbound - 1) ^ start), PCTRIE_WIDTH) :
+ 0;
+
+ /*
+ * Calculate the number of required nodes
+ * by splitting the [start, end) range into two subtrees:
+ * the leftmost ([start, lbound)) and [lbound, end).
+ */
+ end_round = roundup2(end, PCTRIE_COUNT);
+ start_round = rounddown2(start, PCTRIE_COUNT);
+ if (start_round == 0)
+ cnt = pctrie_subtree_nnodes(end_round);
+ else {
+ cnt = pctrie_subtree_nnodes(lbound - start_round);
+ cnt += pctrie_subtree_nnodes(end_round - lbound);
+
+ /*
+ * If there are no fully populated subtrees between
+ * [lbound, end) we have to bump the node count
+ * to cover for the top-level node.
+ */
+ if (lbound != start && (end_round - lbound) <= nitems_slot)
+ cnt++;
+ }
+ /* Account for path compression. */
+ if (__predict_false(end % PCTRIE_COUNT == 1))
+ cnt--;
+ if (__predict_false((start + 1) % PCTRIE_COUNT == 0))
+ cnt--;
+
+ /*
+ * Look up the 'start' and 'end' keys and account
+ * for any leftmost or rightmost nodes that are
+ * already present.
+ */
+ if (__predict_true(!pctrie_isleaf(it->ptree->pt_root) && cnt > 0)) {
+ parent = _pctrie_iter_lookup_node(it, start + owner, NULL,
+ PCTRIE_UNSERIALIZED);
+ if (parent != PCTRIE_NULL) {
+
+ /*
+ * Determine if we have to allocate an additional
+ * node to acommodate the element stored in the
+ * target slot. If the leftmost subtree doesn't cover
+ * the [val, start) range, an additional node will
+ * have to be allocated.
+ */
+ val = *pctrie_toval(parent);
+ if (__predict_false((start + 1) % PCTRIE_COUNT == 0 &&
+ pctrie_isleaf(parent) &&
+ val / PCTRIE_COUNT ==
+ (start + owner) / PCTRIE_COUNT))
+ cnt++;
+ else if (val < (start_round + owner)) {
+ vclev = rounddown(ilog2((start + owner) ^ val),
+ PCTRIE_WIDTH);
+ if (vclev != clev && vclev > lclev)
+ cnt++;
+ }
+ }
+
+ /*
+ * Traverse the iterator path
+ * and decrement node count for each existing node
+ * in the leftmost subtree.
+ */
+ for (top = it->top - 1; top >= 0; top--) {
+ parent = it->path[top];
+ if (pctrie_isleaf(parent) || parent->pn_clev > clev)
+ break;
+ if (pctrie_keybarr(parent, start + owner, &slot) ||
+ (parent->pn_clev > lclev &&
+ parent->pn_clev != clev))
+ continue;
+ if (slot == (PCTRIE_COUNT - 1))
+ continue;
+ cnt--;
+ }
+ parent = _pctrie_iter_lookup_node(it, (end - 1) + owner, NULL,
+ PCTRIE_UNSERIALIZED);
+ if (parent != PCTRIE_NULL) {
+
+ /*
+ * Determine if we have to allocate an additional
+ * node to acommodate the element stored in the
+ * target slot. If the rightmost subtree doesn't cover
+ * the [end - 1, val] range, an additional node will
+ * have to be allocated.
+ */
+ val = *pctrie_toval(parent);
+ if (__predict_false(end % PCTRIE_COUNT == 1 &&
+ pctrie_isleaf(parent) &&
+ val / PCTRIE_COUNT ==
+ (end - 1 + owner) / PCTRIE_COUNT))
+ cnt++;
+ else if (val >=
+ roundup2(end - 1 + owner, PCTRIE_COUNT)) {
+ vclev = rounddown(ilog2(
+ (end - 1 + owner) ^ val),
+ PCTRIE_WIDTH);
+ if (vclev != clev && vclev > rclev)
+ cnt++;
+ }
+ }
+
+ /*
+ * Traverse the iterator's path
+ * and decrement node count for each existing node
+ * in the rightmost subtree.
+ */
+ for (top = it->top - 1; top >= 0; top--) {
+ parent = it->path[top];
+ if (pctrie_isleaf(parent) || parent->pn_clev > rclev ||
+ !pctrie_keybarr(parent, start + owner, &slot))
+ break;
+ if (pctrie_keybarr(parent, (end - 1) + owner, &slot) ||
+ slot == 0)
+ continue;
+ cnt--;
+ }
+ }
+ MPASS(cnt >= 0);
+
+ return (cnt);
+}
+
/*
* Attempts to insert an array of items into a 0-level node.
*
@@ -748,9 +940,6 @@
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)) {

File Metadata

Mime Type
text/plain
Expires
Tue, Sep 1, 11:31 AM (8 h, 27 m)
Storage Engine
blob
Storage Format
Raw Data
Storage Handle
37814731
Default Alt Text
D47744.diff (5 KB)

Event Timeline