summaryrefslogtreecommitdiffstats
path: root/module
diff options
context:
space:
mode:
Diffstat (limited to 'module')
-rw-r--r--module/os/linux/zfs/zfs_znode.c2
-rw-r--r--module/zfs/Makefile.in1
-rw-r--r--module/zfs/arc.c3
-rw-r--r--module/zfs/btree.c2124
-rw-r--r--module/zfs/ddt.c2
-rw-r--r--module/zfs/dmu_objset.c2
-rw-r--r--module/zfs/dmu_recv.c2
-rw-r--r--module/zfs/dmu_send.c14
-rw-r--r--module/zfs/dnode.c11
-rw-r--r--module/zfs/dsl_bookmark.c6
-rw-r--r--module/zfs/dsl_deadlist.c8
-rw-r--r--module/zfs/dsl_deleg.c2
-rw-r--r--module/zfs/dsl_scan.c65
-rw-r--r--module/zfs/metaslab.c594
-rw-r--r--module/zfs/range_tree.c564
-rw-r--r--module/zfs/sa.c6
-rw-r--r--module/zfs/spa.c2
-rw-r--r--module/zfs/spa_misc.c15
-rw-r--r--module/zfs/space_map.c37
-rw-r--r--module/zfs/space_reftree.c15
-rw-r--r--module/zfs/unique.c2
-rw-r--r--module/zfs/vdev.c25
-rw-r--r--module/zfs/vdev_cache.c4
-rw-r--r--module/zfs/vdev_initialize.c31
-rw-r--r--module/zfs/vdev_label.c6
-rw-r--r--module/zfs/vdev_queue.c8
-rw-r--r--module/zfs/vdev_raidz.c6
-rw-r--r--module/zfs/vdev_removal.c66
-rw-r--r--module/zfs/vdev_trim.c43
-rw-r--r--module/zfs/zap_micro.c4
-rw-r--r--module/zfs/zfs_fuid.c4
-rw-r--r--module/zfs/zfs_rlock.c2
-rw-r--r--module/zfs/zil.c8
33 files changed, 3138 insertions, 546 deletions
diff --git a/module/os/linux/zfs/zfs_znode.c b/module/os/linux/zfs/zfs_znode.c
index a4d336abe..ebfaae67b 100644
--- a/module/os/linux/zfs/zfs_znode.c
+++ b/module/os/linux/zfs/zfs_znode.c
@@ -247,7 +247,7 @@ zfs_znode_hold_compare(const void *a, const void *b)
const znode_hold_t *zh_a = (const znode_hold_t *)a;
const znode_hold_t *zh_b = (const znode_hold_t *)b;
- return (AVL_CMP(zh_a->zh_obj, zh_b->zh_obj));
+ return (TREE_CMP(zh_a->zh_obj, zh_b->zh_obj));
}
boolean_t
diff --git a/module/zfs/Makefile.in b/module/zfs/Makefile.in
index b60b799b5..c00c8e424 100644
--- a/module/zfs/Makefile.in
+++ b/module/zfs/Makefile.in
@@ -22,6 +22,7 @@ $(MODULE)-objs += blkptr.o
$(MODULE)-objs += bplist.o
$(MODULE)-objs += bpobj.o
$(MODULE)-objs += bptree.o
+$(MODULE)-objs += btree.o
$(MODULE)-objs += bqueue.o
$(MODULE)-objs += cityhash.o
$(MODULE)-objs += dataset_kstats.o
diff --git a/module/zfs/arc.c b/module/zfs/arc.c
index 9b90690b6..c1ad8785d 100644
--- a/module/zfs/arc.c
+++ b/module/zfs/arc.c
@@ -4759,7 +4759,6 @@ arc_kmem_reap_soon(void)
kmem_cache_t *prev_data_cache = NULL;
extern kmem_cache_t *zio_buf_cache[];
extern kmem_cache_t *zio_data_buf_cache[];
- extern kmem_cache_t *range_seg_cache;
#ifdef _KERNEL
if ((aggsum_compare(&arc_meta_used, arc_meta_limit) >= 0) &&
@@ -4796,7 +4795,7 @@ arc_kmem_reap_soon(void)
kmem_cache_reap_now(buf_cache);
kmem_cache_reap_now(hdr_full_cache);
kmem_cache_reap_now(hdr_l2only_cache);
- kmem_cache_reap_now(range_seg_cache);
+ kmem_cache_reap_now(zfs_btree_leaf_cache);
if (zio_arena != NULL) {
/*
diff --git a/module/zfs/btree.c b/module/zfs/btree.c
new file mode 100644
index 000000000..8f514caab
--- /dev/null
+++ b/module/zfs/btree.c
@@ -0,0 +1,2124 @@
+/*
+ * CDDL HEADER START
+ *
+ * This file and its contents are supplied under the terms of the
+ * Common Development and Distribution License ("CDDL"), version 1.0.
+ * You may only use this file in accordance with the terms of version
+ * 1.0 of the CDDL.
+ *
+ * A full copy of the text of the CDDL should have accompanied this
+ * source. A copy of the CDDL is also available via the Internet at
+ * http://www.illumos.org/license/CDDL.
+ *
+ * CDDL HEADER END
+ */
+/*
+ * Copyright (c) 2019 by Delphix. All rights reserved.
+ */
+
+#include <sys/btree.h>
+#include <sys/bitops.h>
+#include <sys/zfs_context.h>
+
+kmem_cache_t *zfs_btree_leaf_cache;
+
+/*
+ * Control the extent of the verification that occurs when zfs_btree_verify is
+ * called. Primarily used for debugging when extending the btree logic and
+ * functionality. As the intensity is increased, new verification steps are
+ * added. These steps are cumulative; intensity = 3 includes the intensity = 1
+ * and intensity = 2 steps as well.
+ *
+ * Intensity 1: Verify that the tree's height is consistent throughout.
+ * Intensity 2: Verify that a core node's children's parent pointers point
+ * to the core node.
+ * Intensity 3: Verify that the total number of elements in the tree matches the
+ * sum of the number of elements in each node. Also verifies that each node's
+ * count obeys the invariants (less than or equal to maximum value, greater than
+ * or equal to half the maximum minus one).
+ * Intensity 4: Verify that each element compares less than the element
+ * immediately after it and greater than the one immediately before it using the
+ * comparator function. For core nodes, also checks that each element is greater
+ * than the last element in the first of the two nodes it separates, and less
+ * than the first element in the second of the two nodes.
+ * Intensity 5: Verifies, if ZFS_DEBUG is defined, that all unused memory inside
+ * of each node is poisoned appropriately. Note that poisoning always occurs if
+ * ZFS_DEBUG is set, so it is safe to set the intensity to 5 during normal
+ * operation.
+ *
+ * Intensity 4 and 5 are particularly expensive to perform; the previous levels
+ * are a few memory operations per node, while these levels require multiple
+ * operations per element. In addition, when creating large btrees, these
+ * operations are called at every step, resulting in extremely slow operation
+ * (while the asymptotic complexity of the other steps is the same, the
+ * importance of the constant factors cannot be denied).
+ */
+int zfs_btree_verify_intensity = 0;
+
+/*
+ * A convenience function to silence warnings from memmove's return value and
+ * change argument order to src, dest.
+ */
+void
+bmov(const void *src, void *dest, size_t size)
+{
+ (void) memmove(dest, src, size);
+}
+
+#ifdef _ILP32
+#define BTREE_POISON 0xabadb10c
+#else
+#define BTREE_POISON 0xabadb10cdeadbeef
+#endif
+
+static void
+zfs_btree_poison_node(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
+{
+#ifdef ZFS_DEBUG
+ size_t size = tree->bt_elem_size;
+ if (!hdr->bth_core) {
+ zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;
+ (void) memset(leaf->btl_elems + hdr->bth_count * size, 0x0f,
+ BTREE_LEAF_SIZE - sizeof (zfs_btree_hdr_t) -
+ hdr->bth_count * size);
+ } else {
+ zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
+ for (int i = hdr->bth_count + 1; i <= BTREE_CORE_ELEMS; i++) {
+ node->btc_children[i] =
+ (zfs_btree_hdr_t *)BTREE_POISON;
+ }
+ (void) memset(node->btc_elems + hdr->bth_count * size, 0x0f,
+ (BTREE_CORE_ELEMS - hdr->bth_count) * size);
+ }
+#endif
+}
+
+static inline void
+zfs_btree_poison_node_at(zfs_btree_t *tree, zfs_btree_hdr_t *hdr,
+ uint64_t offset)
+{
+#ifdef ZFS_DEBUG
+ size_t size = tree->bt_elem_size;
+ ASSERT3U(offset, >=, hdr->bth_count);
+ if (!hdr->bth_core) {
+ zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;
+ (void) memset(leaf->btl_elems + offset * size, 0x0f, size);
+ } else {
+ zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
+ node->btc_children[offset + 1] =
+ (zfs_btree_hdr_t *)BTREE_POISON;
+ (void) memset(node->btc_elems + offset * size, 0x0f, size);
+ }
+#endif
+}
+
+static inline void
+zfs_btree_verify_poison_at(zfs_btree_t *tree, zfs_btree_hdr_t *hdr,
+ uint64_t offset)
+{
+#ifdef ZFS_DEBUG
+ size_t size = tree->bt_elem_size;
+ uint8_t eval = 0x0f;
+ if (hdr->bth_core) {
+ zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
+ zfs_btree_hdr_t *cval = (zfs_btree_hdr_t *)BTREE_POISON;
+ VERIFY3P(node->btc_children[offset + 1], ==, cval);
+ for (int i = 0; i < size; i++)
+ VERIFY3U(node->btc_elems[offset * size + i], ==, eval);
+ } else {
+ zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;
+ for (int i = 0; i < size; i++)
+ VERIFY3U(leaf->btl_elems[offset * size + i], ==, eval);
+ }
+#endif
+}
+
+void
+zfs_btree_init(void)
+{
+ zfs_btree_leaf_cache = kmem_cache_create("zfs_btree_leaf_cache",
+ BTREE_LEAF_SIZE, 0, NULL, NULL, NULL, NULL,
+ NULL, 0);
+}
+
+void
+zfs_btree_fini(void)
+{
+ kmem_cache_destroy(zfs_btree_leaf_cache);
+}
+
+void
+zfs_btree_create(zfs_btree_t *tree, int (*compar) (const void *, const void *),
+ size_t size)
+{
+ /*
+ * We need a minimmum of 4 elements so that when we split a node we
+ * always have at least two elements in each node. This simplifies the
+ * logic in zfs_btree_bulk_finish, since it means the last leaf will
+ * always have a left sibling to share with (unless it's the root).
+ */
+ ASSERT3U(size, <=, (BTREE_LEAF_SIZE - sizeof (zfs_btree_hdr_t)) / 4);
+
+ bzero(tree, sizeof (*tree));
+ tree->bt_compar = compar;
+ tree->bt_elem_size = size;
+ tree->bt_height = -1;
+ tree->bt_bulk = NULL;
+}
+
+/*
+ * Find value in the array of elements provided. Uses a simple binary search.
+ */
+static void *
+zfs_btree_find_in_buf(zfs_btree_t *tree, uint8_t *buf, uint64_t nelems,
+ const void *value, zfs_btree_index_t *where)
+{
+ uint64_t max = nelems;
+ uint64_t min = 0;
+ while (max > min) {
+ uint64_t idx = (min + max) / 2;
+ uint8_t *cur = buf + idx * tree->bt_elem_size;
+ int comp = tree->bt_compar(cur, value);
+ if (comp == -1) {
+ min = idx + 1;
+ } else if (comp == 1) {
+ max = idx;
+ } else {
+ ASSERT0(comp);
+ where->bti_offset = idx;
+ where->bti_before = B_FALSE;
+ return (cur);
+ }
+ }
+
+ where->bti_offset = max;
+ where->bti_before = B_TRUE;
+ return (NULL);
+}
+
+/*
+ * Find the given value in the tree. where may be passed as null to use as a
+ * membership test or if the btree is being used as a map.
+ */
+void *
+zfs_btree_find(zfs_btree_t *tree, const void *value, zfs_btree_index_t *where)
+{
+ if (tree->bt_height == -1) {
+ if (where != NULL) {
+ where->bti_node = NULL;
+ where->bti_offset = 0;
+ }
+ ASSERT0(tree->bt_num_elems);
+ return (NULL);
+ }
+
+ /*
+ * If we're in bulk-insert mode, we check the last spot in the tree
+ * and the last leaf in the tree before doing the normal search,
+ * because for most workloads the vast majority of finds in
+ * bulk-insert mode are to insert new elements.
+ */
+ zfs_btree_index_t idx;
+ if (tree->bt_bulk != NULL) {
+ zfs_btree_leaf_t *last_leaf = tree->bt_bulk;
+ int compar = tree->bt_compar(last_leaf->btl_elems +
+ ((last_leaf->btl_hdr.bth_count - 1) * tree->bt_elem_size),
+ value);
+ if (compar < 0) {
+ /*
+ * If what they're looking for is after the last
+ * element, it's not in the tree.
+ */
+ if (where != NULL) {
+ where->bti_node = (zfs_btree_hdr_t *)last_leaf;
+ where->bti_offset =
+ last_leaf->btl_hdr.bth_count;
+ where->bti_before = B_TRUE;
+ }
+ return (NULL);
+ } else if (compar == 0) {
+ if (where != NULL) {
+ where->bti_node = (zfs_btree_hdr_t *)last_leaf;
+ where->bti_offset =
+ last_leaf->btl_hdr.bth_count - 1;
+ where->bti_before = B_FALSE;
+ }
+ return (last_leaf->btl_elems +
+ ((last_leaf->btl_hdr.bth_count - 1) *
+ tree->bt_elem_size));
+ }
+ if (tree->bt_compar(last_leaf->btl_elems, value) <= 0) {
+ /*
+ * If what they're looking for is after the first
+ * element in the last leaf, it's in the last leaf or
+ * it's not in the tree.
+ */
+ void *d = zfs_btree_find_in_buf(tree,
+ last_leaf->btl_elems, last_leaf->btl_hdr.bth_count,
+ value, &idx);
+
+ if (where != NULL) {
+ idx.bti_node = (zfs_btree_hdr_t *)last_leaf;
+ *where = idx;
+ }
+ return (d);
+ }
+ }
+
+ zfs_btree_core_t *node = NULL;
+ uint64_t child = 0;
+ uint64_t depth = 0;
+
+ /*
+ * Iterate down the tree, finding which child the value should be in
+ * by comparing with the separators.
+ */
+ for (node = (zfs_btree_core_t *)tree->bt_root; depth < tree->bt_height;
+ node = (zfs_btree_core_t *)node->btc_children[child], depth++) {
+ ASSERT3P(node, !=, NULL);
+ void *d = zfs_btree_find_in_buf(tree, node->btc_elems,
+ node->btc_hdr.bth_count, value, &idx);
+ EQUIV(d != NULL, !idx.bti_before);
+ if (d != NULL) {
+ if (where != NULL) {
+ idx.bti_node = (zfs_btree_hdr_t *)node;
+ *where = idx;
+ }
+ return (d);
+ }
+ ASSERT(idx.bti_before);
+ child = idx.bti_offset;
+ }
+
+ /*
+ * The value is in this leaf, or it would be if it were in the
+ * tree. Find its proper location and return it.
+ */
+ zfs_btree_leaf_t *leaf = (depth == 0 ?
+ (zfs_btree_leaf_t *)tree->bt_root : (zfs_btree_leaf_t *)node);
+ void *d = zfs_btree_find_in_buf(tree, leaf->btl_elems,
+ leaf->btl_hdr.bth_count, value, &idx);
+
+ if (where != NULL) {
+ idx.bti_node = (zfs_btree_hdr_t *)leaf;
+ *where = idx;
+ }
+
+ return (d);
+}
+
+/*
+ * To explain the following functions, it is useful to understand the four
+ * kinds of shifts used in btree operation. First, a shift is a movement of
+ * elements within a node. It is used to create gaps for inserting new
+ * elements and children, or cover gaps created when things are removed. A
+ * shift has two fundamental properties, each of which can be one of two
+ * values, making four types of shifts. There is the direction of the shift
+ * (left or right) and the shape of the shift (parallelogram or isoceles
+ * trapezoid (shortened to trapezoid hereafter)). The shape distinction only
+ * applies to shifts of core nodes.
+ *
+ * The names derive from the following imagining of the layout of a node:
+ *
+ * Elements: * * * * * * * ... * * *
+ * Children: * * * * * * * * ... * * *
+ *
+ * This layout follows from the fact that the elements act as separators
+ * between pairs of children, and that children root subtrees "below" the
+ * current node. A left and right shift are fairly self-explanatory; a left
+ * shift moves things to the left, while a right shift moves things to the
+ * right. A parallelogram shift is a shift with the same number of elements
+ * and children being moved, while a trapezoid shift is a shift that moves one
+ * more children than elements. An example follows:
+ *
+ * A parallelogram shift could contain the following:
+ * _______________
+ * \* * * * \ * * * ... * * *
+ * * \ * * * *\ * * * ... * * *
+ * ---------------
+ * A trapezoid shift could contain the following:
+ * ___________
+ * * / * * * \ * * * ... * * *
+ * * / * * * *\ * * * ... * * *
+ * ---------------
+ *
+ * Note that a parellelogram shift is always shaped like a "left-leaning"
+ * parallelogram, where the starting index of the children being moved is
+ * always one higher than the starting index of the elements being moved. No
+ * "right-leaning" parallelogram shifts are needed (shifts where the starting
+ * element index and starting child index being moved are the same) to achieve
+ * any btree operations, so we ignore them.
+ */
+
+enum bt_shift_shape {
+ BSS_TRAPEZOID,
+ BSS_PARALLELOGRAM
+};
+
+enum bt_shift_direction {
+ BSD_LEFT,
+ BSD_RIGHT
+};
+
+/*
+ * Shift elements and children in the provided core node by off spots. The
+ * first element moved is idx, and count elements are moved. The shape of the
+ * shift is determined by shape. The direction is determined by dir.
+ */
+static inline void
+bt_shift_core(zfs_btree_t *tree, zfs_btree_core_t *node, uint64_t idx,
+ uint64_t count, uint64_t off, enum bt_shift_shape shape,
+ enum bt_shift_direction dir)
+{
+ size_t size = tree->bt_elem_size;
+ ASSERT(node->btc_hdr.bth_core);
+
+ uint8_t *e_start = node->btc_elems + idx * size;
+ int sign = (dir == BSD_LEFT ? -1 : +1);
+ uint8_t *e_out = e_start + sign * off * size;
+ uint64_t e_count = count;
+ bmov(e_start, e_out, e_count * size);
+
+ zfs_btree_hdr_t **c_start = node->btc_children + idx +
+ (shape == BSS_TRAPEZOID ? 0 : 1);
+ zfs_btree_hdr_t **c_out = (dir == BSD_LEFT ? c_start - off :
+ c_start + off);
+ uint64_t c_count = count + (shape == BSS_TRAPEZOID ? 1 : 0);
+ bmov(c_start, c_out, c_count * sizeof (*c_start));
+}
+
+/*
+ * Shift elements and children in the provided core node left by one spot.
+ * The first element moved is idx, and count elements are moved. The
+ * shape of the shift is determined by trap; true if the shift is a trapezoid,
+ * false if it is a parallelogram.
+ */
+static inline void
+bt_shift_core_left(zfs_btree_t *tree, zfs_btree_core_t *node, uint64_t idx,
+ uint64_t count, enum bt_shift_shape shape)
+{
+ bt_shift_core(tree, node, idx, count, 1, shape, BSD_LEFT);
+}
+
+/*
+ * Shift elements and children in the provided core node right by one spot.
+ * Starts with elements[idx] and children[idx] and one more child than element.
+ */
+static inline void
+bt_shift_core_right(zfs_btree_t *tree, zfs_btree_core_t *node, uint64_t idx,
+ uint64_t count, enum bt_shift_shape shape)
+{
+ bt_shift_core(tree, node, idx, count, 1, shape, BSD_RIGHT);
+}
+
+/*
+ * Shift elements and children in the provided leaf node by off spots.
+ * The first element moved is idx, and count elements are moved. The direction
+ * is determined by left.
+ */
+static inline void
+bt_shift_leaf(zfs_btree_t *tree, zfs_btree_leaf_t *node, uint64_t idx,
+ uint64_t count, uint64_t off, enum bt_shift_direction dir)
+{
+ size_t size = tree->bt_elem_size;
+ ASSERT(!node->btl_hdr.bth_core);
+
+ uint8_t *start = node->btl_elems + idx * size;
+ int sign = (dir == BSD_LEFT ? -1 : +1);
+ uint8_t *out = start + sign * off * size;
+ bmov(start, out, count * size);
+}
+
+static inline void
+bt_shift_leaf_right(zfs_btree_t *tree, zfs_btree_leaf_t *leaf, uint64_t idx,
+ uint64_t count)
+{
+ bt_shift_leaf(tree, leaf, idx, count, 1, BSD_RIGHT);
+}
+
+static inline void
+bt_shift_leaf_left(zfs_btree_t *tree, zfs_btree_leaf_t *leaf, uint64_t idx,
+ uint64_t count)
+{
+ bt_shift_leaf(tree, leaf, idx, count, 1, BSD_LEFT);
+}
+
+/*
+ * Move children and elements from one core node to another. The shape
+ * parameter behaves the same as it does in the shift logic.
+ */
+static inline void
+bt_transfer_core(zfs_btree_t *tree, zfs_btree_core_t *source, uint64_t sidx,
+ uint64_t count, zfs_btree_core_t *dest, uint64_t didx,
+ enum bt_shift_shape shape)
+{
+ size_t size = tree->bt_elem_size;
+ ASSERT(source->btc_hdr.bth_core);
+ ASSERT(dest->btc_hdr.bth_core);
+
+ bmov(source->btc_elems + sidx * size, dest->btc_elems + didx * size,
+ count * size);
+
+ uint64_t c_count = count + (shape == BSS_TRAPEZOID ? 1 : 0);
+ bmov(source->btc_children + sidx + (shape == BSS_TRAPEZOID ? 0 : 1),
+ dest->btc_children + didx + (shape == BSS_TRAPEZOID ? 0 : 1),
+ c_count * sizeof (*source->btc_children));
+}
+
+static inline void
+bt_transfer_leaf(zfs_btree_t *tree, zfs_btree_leaf_t *source, uint64_t sidx,
+ uint64_t count, zfs_btree_leaf_t *dest, uint64_t didx)
+{
+ size_t size = tree->bt_elem_size;
+ ASSERT(!source->btl_hdr.bth_core);
+ ASSERT(!dest->btl_hdr.bth_core);
+
+ bmov(source->btl_elems + sidx * size, dest->btl_elems + didx * size,
+ count * size);
+}
+
+/*
+ * Find the first element in the subtree rooted at hdr, return its value and
+ * put its location in where if non-null.
+ */
+static void *
+zfs_btree_first_helper(zfs_btree_hdr_t *hdr, zfs_btree_index_t *where)
+{
+ zfs_btree_hdr_t *node;
+
+ for (node = hdr; node->bth_core; node =
+ ((zfs_btree_core_t *)node)->btc_children[0])
+ ;
+
+ ASSERT(!node->bth_core);
+ zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)node;
+ if (where != NULL) {
+ where->bti_node = node;
+ where->bti_offset = 0;
+ where->bti_before = B_FALSE;
+ }
+ return (&leaf->btl_elems[0]);
+}
+
+/* Insert an element and a child into a core node at the given offset. */
+static void
+zfs_btree_insert_core_impl(zfs_btree_t *tree, zfs_btree_core_t *parent,
+ uint64_t offset, zfs_btree_hdr_t *new_node, void *buf)
+{
+ uint64_t size = tree->bt_elem_size;
+ zfs_btree_hdr_t *par_hdr = &parent->btc_hdr;
+ ASSERT3P(par_hdr, ==, new_node->bth_parent);
+ ASSERT3U(par_hdr->bth_count, <, BTREE_CORE_ELEMS);
+
+ if (zfs_btree_verify_intensity >= 5) {
+ zfs_btree_verify_poison_at(tree, par_hdr,
+ par_hdr->bth_count);
+ }
+ /* Shift existing elements and children */
+ uint64_t count = par_hdr->bth_count - offset;
+ bt_shift_core_right(tree, parent, offset, count,
+ BSS_PARALLELOGRAM);
+
+ /* Insert new values */
+ parent->btc_children[offset + 1] = new_node;
+ bmov(buf, parent->btc_elems + offset * size, size);
+ par_hdr->bth_count++;
+}
+
+/*
+ * Insert new_node into the parent of old_node directly after old_node, with
+ * buf as the dividing element between the two.
+ */
+static void
+zfs_btree_insert_into_parent(zfs_btree_t *tree, zfs_btree_hdr_t *old_node,
+ zfs_btree_hdr_t *new_node, void *buf)
+{
+ ASSERT3P(old_node->bth_parent, ==, new_node->bth_parent);
+ uint64_t size = tree->bt_elem_size;
+ zfs_btree_core_t *parent = old_node->bth_parent;
+ zfs_btree_hdr_t *par_hdr = &parent->btc_hdr;
+
+ /*
+ * If this is the root node we were splitting, we create a new root
+ * and increase the height of the tree.
+ */
+ if (parent == NULL) {
+ ASSERT3P(old_node, ==, tree->bt_root);
+ tree->bt_num_nodes++;
+ zfs_btree_core_t *new_root =
+ kmem_alloc(sizeof (zfs_btree_core_t) + BTREE_CORE_ELEMS *
+ size, KM_SLEEP);
+ zfs_btree_hdr_t *new_root_hdr = &new_root->btc_hdr;
+ new_root_hdr->bth_parent = NULL;
+ new_root_hdr->bth_core = B_TRUE;
+ new_root_hdr->bth_count = 1;
+
+ old_node->bth_parent = new_node->bth_parent = new_root;
+ new_root->btc_children[0] = old_node;
+ new_root->btc_children[1] = new_node;
+ bmov(buf, new_root->btc_elems, size);
+
+ tree->bt_height++;
+ tree->bt_root = new_root_hdr;
+ zfs_btree_poison_node(tree, new_root_hdr);
+ return;
+ }
+
+ /*
+ * Since we have the new separator, binary search for where to put
+ * new_node.
+ */
+ zfs_btree_index_t idx;
+ ASSERT(par_hdr->bth_core);
+ VERIFY3P(zfs_btree_find_in_buf(tree, parent->btc_elems,
+ par_hdr->bth_count, buf, &idx), ==, NULL);
+ ASSERT(idx.bti_before);
+ uint64_t offset = idx.bti_offset;
+ ASSERT3U(offset, <=, par_hdr->bth_count);
+ ASSERT3P(parent->btc_children[offset], ==, old_node);
+
+ /*
+ * If the parent isn't full, shift things to accomodate our insertions
+ * and return.
+ */
+ if (par_hdr->bth_count != BTREE_CORE_ELEMS) {
+ zfs_btree_insert_core_impl(tree, parent, offset, new_node, buf);
+ return;
+ }
+
+ /*
+ * We need to split this core node into two. Currently there are
+ * BTREE_CORE_ELEMS + 1 child nodes, and we are adding one for
+ * BTREE_CORE_ELEMS + 2. Some of the children will be part of the
+ * current node, and the others will be moved to the new core node.
+ * There are BTREE_CORE_ELEMS + 1 elements including the new one. One
+ * will be used as the new separator in our parent, and the others
+ * will be split among the two core nodes.
+ *
+ * Usually we will split the node in half evenly, with
+ * BTREE_CORE_ELEMS/2 elements in each node. If we're bulk loading, we
+ * instead move only about a quarter of the elements (and children) to
+ * the new node. Since the average state after a long time is a 3/4
+ * full node, shortcutting directly to that state improves efficiency.
+ *
+ * We do this in two stages: first we split into two nodes, and then we
+ * reuse our existing logic to insert the new element and child.
+ */
+ uint64_t move_count = MAX((BTREE_CORE_ELEMS / (tree->bt_bulk == NULL ?
+ 2 : 4)) - 1, 2);
+ uint64_t keep_count = BTREE_CORE_ELEMS - move_count - 1;
+ ASSERT3U(BTREE_CORE_ELEMS - move_count, >=, 2);
+ tree->bt_num_nodes++;
+ zfs_btree_core_t *new_parent = kmem_alloc(sizeof (zfs_btree_core_t) +
+ BTREE_CORE_ELEMS * size, KM_SLEEP);
+ zfs_btree_hdr_t *new_par_hdr = &new_parent->btc_hdr;
+ new_par_hdr->bth_parent = par_hdr->bth_parent;
+ new_par_hdr->bth_core = B_TRUE;
+ new_par_hdr->bth_count = move_count;
+ zfs_btree_poison_node(tree, new_par_hdr);
+
+ par_hdr->bth_count = keep_count;
+
+ bt_transfer_core(tree, parent, keep_count + 1, move_count, new_parent,
+ 0, BSS_TRAPEZOID);
+
+ /* Store the new separator in a buffer. */
+ uint8_t *tmp_buf = kmem_alloc(size, KM_SLEEP);
+ bmov(parent->btc_elems + keep_count * size, tmp_buf,
+ size);
+ zfs_btree_poison_node(tree, par_hdr);
+
+ if (offset < keep_count) {
+ /* Insert the new node into the left half */
+ zfs_btree_insert_core_impl(tree, parent, offset, new_node,
+ buf);
+
+ /*
+ * Move the new separator to the existing buffer.
+ */
+ bmov(tmp_buf, buf, size);
+ } else if (offset > keep_count) {
+ /* Insert the new node into the right half */
+ new_node->bth_parent = new_parent;
+ zfs_btree_insert_core_impl(tree, new_parent,
+ offset - keep_count - 1, new_node, buf);
+
+ /*
+ * Move the new separator to the existing buffer.
+ */
+ bmov(tmp_buf, buf, size);
+ } else {
+ /*
+ * Move the new separator into the right half, and replace it
+ * with buf. We also need to shift back the elements in the
+ * right half to accomodate new_node.
+ */
+ bt_shift_core_right(tree, new_parent, 0, move_count,
+ BSS_TRAPEZOID);
+ new_parent->btc_children[0] = new_node;
+ bmov(tmp_buf, new_parent->btc_elems, size);
+ new_par_hdr->bth_count++;
+ }
+ kmem_free(tmp_buf, size);
+ zfs_btree_poison_node(tree, par_hdr);
+
+ for (int i = 0; i <= new_parent->btc_hdr.bth_count; i++)
+ new_parent->btc_children[i]->bth_parent = new_parent;
+
+ for (int i = 0; i <= parent->btc_hdr.bth_count; i++)
+ ASSERT3P(parent->btc_children[i]->bth_parent, ==, parent);
+
+ /*
+ * Now that the node is split, we need to insert the new node into its
+ * parent. This may cause further splitting.
+ */
+ zfs_btree_insert_into_parent(tree, &parent->btc_hdr,
+ &new_parent->btc_hdr, buf);
+}
+
+/* Insert an element into a leaf node at the given offset. */
+static void
+zfs_btree_insert_leaf_impl(zfs_btree_t *tree, zfs_btree_leaf_t *leaf,
+ uint64_t idx, const void *value)
+{
+ uint64_t size = tree->bt_elem_size;
+ uint8_t *start = leaf->btl_elems + (idx * size);
+ zfs_btree_hdr_t *hdr = &leaf->btl_hdr;
+ ASSERTV(uint64_t capacity = P2ALIGN((BTREE_LEAF_SIZE -
+ sizeof (zfs_btree_hdr_t)) / size, 2));
+ uint64_t count = leaf->btl_hdr.bth_count - idx;
+ ASSERT3U(leaf->btl_hdr.bth_count, <, capacity);
+
+ if (zfs_btree_verify_intensity >= 5) {
+ zfs_btree_verify_poison_at(tree, &leaf->btl_hdr,
+ leaf->btl_hdr.bth_count);
+ }
+
+ bt_shift_leaf_right(tree, leaf, idx, count);
+ bmov(value, start, size);
+ hdr->bth_count++;
+}
+
+/* Helper function for inserting a new value into leaf at the given index. */
+static void
+zfs_btree_insert_into_leaf(zfs_btree_t *tree, zfs_btree_leaf_t *leaf,
+ const void *value, uint64_t idx)
+{
+ uint64_t size = tree->bt_elem_size;
+ uint64_t capacity = P2ALIGN((BTREE_LEAF_SIZE -
+ sizeof (zfs_btree_hdr_t)) / size, 2);
+
+ /*
+ * If the leaf isn't full, shift the elements after idx and insert
+ * value.
+ */
+ if (leaf->btl_hdr.bth_count != capacity) {
+ zfs_btree_insert_leaf_impl(tree, leaf, idx, value);
+ return;
+ }
+
+ /*
+ * Otherwise, we split the leaf node into two nodes. If we're not bulk
+ * inserting, each is of size (capacity / 2). If we are bulk
+ * inserting, we move a quarter of the elements to the new node so
+ * inserts into the old node don't cause immediate splitting but the
+ * tree stays relatively dense. Since the average state after a long
+ * time is a 3/4 full node, shortcutting directly to that state
+ * improves efficiency. At the end of the bulk insertion process
+ * we'll need to go through and fix up any nodes (the last leaf and
+ * its ancestors, potentially) that are below the minimum.
+ *
+ * In either case, we're left with one extra element. The leftover
+ * element will become the new dividing element between the two nodes.
+ */
+ uint64_t move_count = MAX(capacity / (tree->bt_bulk == NULL ? 2 : 4) -
+ 1, 2);
+ uint64_t keep_count = capacity - move_count - 1;
+ ASSERT3U(capacity - move_count, >=, 2);
+ tree->bt_num_nodes++;
+ zfs_btree_leaf_t *new_leaf = kmem_cache_alloc(zfs_btree_leaf_cache,
+ KM_SLEEP);
+ zfs_btree_hdr_t *new_hdr = &new_leaf->btl_hdr;
+ new_hdr->bth_parent = leaf->btl_hdr.bth_parent;
+ new_hdr->bth_core = B_FALSE;
+ new_hdr->bth_count = move_count;
+ zfs_btree_poison_node(tree, new_hdr);
+
+ leaf->btl_hdr.bth_count = keep_count;
+
+ if (tree->bt_bulk != NULL && leaf == tree->bt_bulk)
+ tree->bt_bulk = new_leaf;
+
+ /* Copy the back part to the new leaf. */
+ bt_transfer_leaf(tree, leaf, keep_count + 1, move_count, new_leaf,
+ 0);
+
+ /* We store the new separator in a buffer we control for simplicity. */
+ uint8_t *buf = kmem_alloc(size, KM_SLEEP);
+ bmov(leaf->btl_elems + (keep_count * size), buf, size);
+ zfs_btree_poison_node(tree, &leaf->btl_hdr);
+
+ if (idx < keep_count) {
+ /* Insert into the existing leaf. */
+ zfs_btree_insert_leaf_impl(tree, leaf, idx, value);
+ } else if (idx > keep_count) {
+ /* Insert into the new leaf. */
+ zfs_btree_insert_leaf_impl(tree, new_leaf, idx - keep_count -
+ 1, value);
+ } else {
+ /*
+ * Shift the elements in the new leaf to make room for the
+ * separator, and use the new value as the new separator.
+ */
+ bt_shift_leaf_right(tree, new_leaf, 0, move_count);
+ bmov(buf, new_leaf->btl_elems, size);
+ bmov(value, buf, size);
+ new_hdr->bth_count++;
+ }
+
+ /*
+ * Now that the node is split, we need to insert the new node into its
+ * parent. This may cause further splitting, bur only of core nodes.
+ */
+ zfs_btree_insert_into_parent(tree, &leaf->btl_hdr, &new_leaf->btl_hdr,
+ buf);
+ kmem_free(buf, size);
+}
+
+static uint64_t
+zfs_btree_find_parent_idx(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
+{
+ void *buf;
+ if (hdr->bth_core) {
+ buf = ((zfs_btree_core_t *)hdr)->btc_elems;
+ } else {
+ buf = ((zfs_btree_leaf_t *)hdr)->btl_elems;
+ }
+ zfs_btree_index_t idx;
+ zfs_btree_core_t *parent = hdr->bth_parent;
+ VERIFY3P(zfs_btree_find_in_buf(tree, parent->btc_elems,
+ parent->btc_hdr.bth_count, buf, &idx), ==, NULL);
+ ASSERT(idx.bti_before);
+ ASSERT3U(idx.bti_offset, <=, parent->btc_hdr.bth_count);
+ ASSERT3P(parent->btc_children[idx.bti_offset], ==, hdr);
+ return (idx.bti_offset);
+}
+
+/*
+ * Take the b-tree out of bulk insert mode. During bulk-insert mode, some
+ * nodes may violate the invariant that non-root nodes must be at least half
+ * full. All nodes violating this invariant should be the last node in their
+ * particular level. To correct the invariant, we take values from their left
+ * neighbor until they are half full. They must have a left neighbor at their
+ * level because the last node at a level is not the first node unless it's
+ * the root.
+ */
+static void
+zfs_btree_bulk_finish(zfs_btree_t *tree)
+{
+ ASSERT3P(tree->bt_bulk, !=, NULL);
+ ASSERT3P(tree->bt_root, !=, NULL);
+ zfs_btree_leaf_t *leaf = tree->bt_bulk;
+ zfs_btree_hdr_t *hdr = &leaf->btl_hdr;
+ zfs_btree_core_t *parent = hdr->bth_parent;
+ uint64_t size = tree->bt_elem_size;
+ uint64_t capacity = P2ALIGN((BTREE_LEAF_SIZE -
+ sizeof (zfs_btree_hdr_t)) / size, 2);
+
+ /*
+ * The invariant doesn't apply to the root node, if that's the only
+ * node in the tree we're done.
+ */
+ if (parent == NULL) {
+ tree->bt_bulk = NULL;
+ return;
+ }
+
+ /* First, take elements to rebalance the leaf node. */
+ if (hdr->bth_count < capacity / 2) {
+ /*
+ * First, find the left neighbor. The simplest way to do this
+ * is to call zfs_btree_prev twice; the first time finds some
+ * ancestor of this node, and the second time finds the left
+ * neighbor. The ancestor found is the lowest common ancestor
+ * of leaf and the neighbor.
+ */
+ zfs_btree_index_t idx = {
+ .bti_node = hdr,
+ .bti_offset = 0
+ };
+ VERIFY3P(zfs_btree_prev(tree, &idx, &idx), !=, NULL);
+ ASSERT(idx.bti_node->bth_core);
+ zfs_btree_core_t *common = (zfs_btree_core_t *)idx.bti_node;
+ uint64_t common_idx = idx.bti_offset;
+
+ VERIFY3P(zfs_btree_prev(tree, &idx, &idx), !=, NULL);
+ ASSERT(!idx.bti_node->bth_core);
+ zfs_btree_leaf_t *l_neighbor = (zfs_btree_leaf_t *)idx.bti_node;
+ zfs_btree_hdr_t *l_hdr = idx.bti_node;
+ uint64_t move_count = (capacity / 2) - hdr->bth_count;
+ ASSERT3U(l_neighbor->btl_hdr.bth_count - move_count, >=,
+ capacity / 2);
+
+ if (zfs_btree_verify_intensity >= 5) {
+ for (int i = 0; i < move_count; i++) {
+ zfs_btree_verify_poison_at(tree, hdr,
+ leaf->btl_hdr.bth_count + i);
+ }
+ }
+
+ /* First, shift elements in leaf back. */
+ bt_shift_leaf(tree, leaf, 0, hdr->bth_count, move_count,
+ BSD_RIGHT);
+
+ /* Next, move the separator from the common ancestor to leaf. */
+ uint8_t *separator = common->btc_elems + (common_idx * size);
+ uint8_t *out = leaf->btl_elems + ((move_count - 1) * size);
+ bmov(separator, out, size);
+ move_count--;
+
+ /*
+ * Now we move elements from the tail of the left neighbor to
+ * fill the remaining spots in leaf.
+ */
+ bt_transfer_leaf(tree, l_neighbor, l_hdr->bth_count -
+ move_count, move_count, leaf, 0);
+
+ /*
+ * Finally, move the new last element in the left neighbor to
+ * the separator.
+ */
+ bmov(l_neighbor->btl_elems + (l_hdr->bth_count -
+ move_count - 1) * size, separator, size);
+
+ /* Adjust the node's counts, and we're done. */
+ l_hdr->bth_count -= move_count + 1;
+ hdr->bth_count += move_count + 1;
+
+ ASSERT3U(l_hdr->bth_count, >=, capacity / 2);
+ ASSERT3U(hdr->bth_count, >=, capacity / 2);
+ zfs_btree_poison_node(tree, l_hdr);
+ }
+
+ /*
+ * Now we have to rebalance any ancestors of leaf that may also
+ * violate the invariant.
+ */
+ capacity = BTREE_CORE_ELEMS;
+ while (parent->btc_hdr.bth_parent != NULL) {
+ zfs_btree_core_t *cur = parent;
+ zfs_btree_hdr_t *hdr = &cur->btc_hdr;
+ parent = hdr->bth_parent;
+ /*
+ * If the invariant isn't violated, move on to the next
+ * ancestor.
+ */
+ if (hdr->bth_count >= capacity / 2)
+ continue;
+
+ /*
+ * Because the smallest number of nodes we can move when
+ * splitting is 2, we never need to worry about not having a
+ * left sibling (a sibling is a neighbor with the same parent).
+ */
+ uint64_t parent_idx = zfs_btree_find_parent_idx(tree, hdr);
+ ASSERT3U(parent_idx, >, 0);
+ zfs_btree_core_t *l_neighbor =
+ (zfs_btree_core_t *)parent->btc_children[parent_idx - 1];
+ uint64_t move_count = (capacity / 2) - hdr->bth_count;
+ ASSERT3U(l_neighbor->btc_hdr.bth_count - move_count, >=,
+ capacity / 2);
+
+ if (zfs_btree_verify_intensity >= 5) {
+ for (int i = 0; i < move_count; i++) {
+ zfs_btree_verify_poison_at(tree, hdr,
+ hdr->bth_count + i);
+ }
+ }
+ /* First, shift things in the right node back. */
+ bt_shift_core(tree, cur, 0, hdr->bth_count, move_count,
+ BSS_TRAPEZOID, BSD_RIGHT);
+
+ /* Next, move the separator to the right node. */
+ uint8_t *separator = parent->btc_elems + ((parent_idx - 1) *
+ size);
+ uint8_t *e_out = cur->btc_elems + ((move_count - 1) * size);
+ bmov(separator, e_out, size);
+
+ /*
+ * Now, move elements and children from the left node to the
+ * right. We move one more child than elements.
+ */
+ move_count--;
+ uint64_t move_idx = l_neighbor->btc_hdr.bth_count - move_count;
+ bt_transfer_core(tree, l_neighbor, move_idx, move_count, cur, 0,
+ BSS_TRAPEZOID);
+
+ /*
+ * Finally, move the last element in the left node to the
+ * separator's position.
+ */
+ move_idx--;
+ bmov(l_neighbor->btc_elems + move_idx * size, separator, size);
+
+ l_neighbor->btc_hdr.bth_count -= move_count + 1;
+ hdr->bth_count += move_count + 1;
+
+ ASSERT3U(l_neighbor->btc_hdr.bth_count, >=, capacity / 2);
+ ASSERT3U(hdr->bth_count, >=, capacity / 2);
+
+ zfs_btree_poison_node(tree, &l_neighbor->btc_hdr);
+
+ for (int i = 0; i <= hdr->bth_count; i++)
+ cur->btc_children[i]->bth_parent = cur;
+ }
+
+ tree->bt_bulk = NULL;
+}
+
+/*
+ * Insert value into tree at the location specified by where.
+ */
+void
+zfs_btree_insert(zfs_btree_t *tree, const void *value,
+ const zfs_btree_index_t *where)
+{
+ zfs_btree_index_t idx = {0};
+
+ /* If we're not inserting in the last leaf, end bulk insert mode. */
+ if (tree->bt_bulk != NULL) {
+ if (where->bti_node != &tree->bt_bulk->btl_hdr) {
+ zfs_btree_bulk_finish(tree);
+ VERIFY3P(zfs_btree_find(tree, value, &idx), ==, NULL);
+ where = &idx;
+ }
+ }
+
+ tree->bt_num_elems++;
+ /*
+ * If this is the first element in the tree, create a leaf root node
+ * and add the value to it.
+ */
+ if (where->bti_node == NULL) {
+ ASSERT3U(tree->bt_num_elems, ==, 1);
+ ASSERT3S(tree->bt_height, ==, -1);
+ ASSERT3P(tree->bt_root, ==, NULL);
+ ASSERT0(where->bti_offset);
+
+ tree->bt_num_nodes++;
+ zfs_btree_leaf_t *leaf = kmem_cache_alloc(zfs_btree_leaf_cache,
+ KM_SLEEP);
+ tree->bt_root = &leaf->btl_hdr;
+ tree->bt_height++;
+
+ zfs_btree_hdr_t *hdr = &leaf->btl_hdr;
+ hdr->bth_parent = NULL;
+ hdr->bth_core = B_FALSE;
+ hdr->bth_count = 0;
+ zfs_btree_poison_node(tree, hdr);
+
+ zfs_btree_insert_into_leaf(tree, leaf, value, 0);
+ tree->bt_bulk = leaf;
+ } else if (!where->bti_node->bth_core) {
+ /*
+ * If we're inserting into a leaf, go directly to the helper
+ * function.
+ */
+ zfs_btree_insert_into_leaf(tree,
+ (zfs_btree_leaf_t *)where->bti_node, value,
+ where->bti_offset);
+ } else {
+ /*
+ * If we're inserting into a core node, we can't just shift
+ * the existing element in that slot in the same node without
+ * breaking our ordering invariants. Instead we place the new
+ * value in the node at that spot and then insert the old
+ * separator into the first slot in the subtree to the right.
+ */
+ ASSERT(where->bti_node->bth_core);
+ zfs_btree_core_t *node = (zfs_btree_core_t *)where->bti_node;
+
+ /*
+ * We can ignore bti_before, because either way the value
+ * should end up in bti_offset.
+ */
+ uint64_t off = where->bti_offset;
+ zfs_btree_hdr_t *subtree = node->btc_children[off + 1];
+ size_t size = tree->bt_elem_size;
+ uint8_t *buf = kmem_alloc(size, KM_SLEEP);
+ bmov(node->btc_elems + off * size, buf, size);
+ bmov(value, node->btc_elems + off * size, size);
+
+ /*
+ * Find the first slot in the subtree to the right, insert
+ * there.
+ */
+ zfs_btree_index_t new_idx;
+ VERIFY3P(zfs_btree_first_helper(subtree, &new_idx), !=, NULL);
+ ASSERT0(new_idx.bti_offset);
+ ASSERT(!new_idx.bti_node->bth_core);
+ zfs_btree_insert_into_leaf(tree,
+ (zfs_btree_leaf_t *)new_idx.bti_node, buf, 0);
+ kmem_free(buf, size);
+ }
+ zfs_btree_verify(tree);
+}
+
+/*
+ * Return the first element in the tree, and put its location in where if
+ * non-null.
+ */
+void *
+zfs_btree_first(zfs_btree_t *tree, zfs_btree_index_t *where)
+{
+ if (tree->bt_height == -1) {
+ ASSERT0(tree->bt_num_elems);
+ return (NULL);
+ }
+ return (zfs_btree_first_helper(tree->bt_root, where));
+}
+
+/*
+ * Find the last element in the subtree rooted at hdr, return its value and
+ * put its location in where if non-null.
+ */
+static void *
+zfs_btree_last_helper(zfs_btree_t *btree, zfs_btree_hdr_t *hdr,
+ zfs_btree_index_t *where)
+{
+ zfs_btree_hdr_t *node;
+
+ for (node = hdr; node->bth_core; node =
+ ((zfs_btree_core_t *)node)->btc_children[node->bth_count])
+ ;
+
+ zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)node;
+ if (where != NULL) {
+ where->bti_node = node;
+ where->bti_offset = node->bth_count - 1;
+ where->bti_before = B_FALSE;
+ }
+ return (leaf->btl_elems + (node->bth_count - 1) * btree->bt_elem_size);
+}
+
+/*
+ * Return the last element in the tree, and put its location in where if
+ * non-null.
+ */
+void *
+zfs_btree_last(zfs_btree_t *tree, zfs_btree_index_t *where)
+{
+ if (tree->bt_height == -1) {
+ ASSERT0(tree->bt_num_elems);
+ return (NULL);
+ }
+ return (zfs_btree_last_helper(tree, tree->bt_root, where));
+}
+
+/*
+ * This function contains the logic to find the next node in the tree. A
+ * helper function is used because there are multiple internal consumemrs of
+ * this logic. The done_func is used by zfs_btree_destroy_nodes to clean up each
+ * node after we've finished with it.
+ */
+static void *
+zfs_btree_next_helper(zfs_btree_t *tree, const zfs_btree_index_t *idx,
+ zfs_btree_index_t *out_idx,
+ void (*done_func)(zfs_btree_t *, zfs_btree_hdr_t *))
+{
+ if (idx->bti_node == NULL) {
+ ASSERT3S(tree->bt_height, ==, -1);
+ return (NULL);
+ }
+
+ uint64_t offset = idx->bti_offset;
+ if (!idx->bti_node->bth_core) {
+ /*
+ * When finding the next element of an element in a leaf,
+ * there are two cases. If the element isn't the last one in
+ * the leaf, in which case we just return the next element in
+ * the leaf. Otherwise, we need to traverse up our parents
+ * until we find one where our ancestor isn't the last child
+ * of its parent. Once we do, the next element is the
+ * separator after our ancestor in its parent.
+ */
+ zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)idx->bti_node;
+ uint64_t new_off = offset + (idx->bti_before ? 0 : 1);
+ if (leaf->btl_hdr.bth_count > new_off) {
+ out_idx->bti_node = &leaf->btl_hdr;
+ out_idx->bti_offset = new_off;
+ out_idx->bti_before = B_FALSE;
+ return (leaf->btl_elems + new_off * tree->bt_elem_size);
+ }
+
+ zfs_btree_hdr_t *prev = &leaf->btl_hdr;
+ for (zfs_btree_core_t *node = leaf->btl_hdr.bth_parent;
+ node != NULL; node = node->btc_hdr.bth_parent) {
+ zfs_btree_hdr_t *hdr = &node->btc_hdr;
+ ASSERT(hdr->bth_core);
+ uint64_t i = zfs_btree_find_parent_idx(tree, prev);
+ if (done_func != NULL)
+ done_func(tree, prev);
+ if (i == hdr->bth_count) {
+ prev = hdr;
+ continue;
+ }
+ out_idx->bti_node = hdr;
+ out_idx->bti_offset = i;
+ out_idx->bti_before = B_FALSE;
+ return (node->btc_elems + i * tree->bt_elem_size);
+ }
+ if (done_func != NULL)
+ done_func(tree, prev);
+ /*
+ * We've traversed all the way up and been at the end of the
+ * node every time, so this was the last element in the tree.
+ */
+ return (NULL);
+ }
+
+ /* If we were before an element in a core node, return that element. */
+ ASSERT(idx->bti_node->bth_core);
+ zfs_btree_core_t *node = (zfs_btree_core_t *)idx->bti_node;
+ if (idx->bti_before) {
+ out_idx->bti_before = B_FALSE;
+ return (node->btc_elems + offset * tree->bt_elem_size);
+ }
+
+ /*
+ * The next element from one in a core node is the first element in
+ * the subtree just to the right of the separator.
+ */
+ zfs_btree_hdr_t *child = node->btc_children[offset + 1];
+ return (zfs_btree_first_helper(child, out_idx));
+}
+
+/*
+ * Return the next valued node in the tree. The same address can be safely
+ * passed for idx and out_idx.
+ */
+void *
+zfs_btree_next(zfs_btree_t *tree, const zfs_btree_index_t *idx,
+ zfs_btree_index_t *out_idx)
+{
+ return (zfs_btree_next_helper(tree, idx, out_idx, NULL));
+}
+
+/*
+ * Return the previous valued node in the tree. The same value can be safely
+ * passed for idx and out_idx.
+ */
+void *
+zfs_btree_prev(zfs_btree_t *tree, const zfs_btree_index_t *idx,
+ zfs_btree_index_t *out_idx)
+{
+ if (idx->bti_node == NULL) {
+ ASSERT3S(tree->bt_height, ==, -1);
+ return (NULL);
+ }
+
+ uint64_t offset = idx->bti_offset;
+ if (!idx->bti_node->bth_core) {
+ /*
+ * When finding the previous element of an element in a leaf,
+ * there are two cases. If the element isn't the first one in
+ * the leaf, in which case we just return the previous element
+ * in the leaf. Otherwise, we need to traverse up our parents
+ * until we find one where our previous ancestor isn't the
+ * first child. Once we do, the previous element is the
+ * separator after our previous ancestor.
+ */
+ zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)idx->bti_node;
+ if (offset != 0) {
+ out_idx->bti_node = &leaf->btl_hdr;
+ out_idx->bti_offset = offset - 1;
+ out_idx->bti_before = B_FALSE;
+ return (leaf->btl_elems + (offset - 1) *
+ tree->bt_elem_size);
+ }
+ zfs_btree_hdr_t *prev = &leaf->btl_hdr;
+ for (zfs_btree_core_t *node = leaf->btl_hdr.bth_parent;
+ node != NULL; node = node->btc_hdr.bth_parent) {
+ zfs_btree_hdr_t *hdr = &node->btc_hdr;
+ ASSERT(hdr->bth_core);
+ uint64_t i = zfs_btree_find_parent_idx(tree, prev);
+ if (i == 0) {
+ prev = hdr;
+ continue;
+ }
+ out_idx->bti_node = hdr;
+ out_idx->bti_offset = i - 1;
+ out_idx->bti_before = B_FALSE;
+ return (node->btc_elems + (i - 1) * tree->bt_elem_size);
+ }
+ /*
+ * We've traversed all the way up and been at the start of the
+ * node every time, so this was the first node in the tree.
+ */
+ return (NULL);
+ }
+
+ /*
+ * The previous element from one in a core node is the last element in
+ * the subtree just to the left of the separator.
+ */
+ ASSERT(idx->bti_node->bth_core);
+ zfs_btree_core_t *node = (zfs_btree_core_t *)idx->bti_node;
+ zfs_btree_hdr_t *child = node->btc_children[offset];
+ return (zfs_btree_last_helper(tree, child, out_idx));
+}
+
+/*
+ * Get the value at the provided index in the tree.
+ *
+ * Note that the value returned from this function can be mutated, but only
+ * if it will not change the ordering of the element with respect to any other
+ * elements that could be in the tree.
+ */
+void *
+zfs_btree_get(zfs_btree_t *tree, zfs_btree_index_t *idx)
+{
+ ASSERT(!idx->bti_before);
+ if (!idx->bti_node->bth_core) {
+ zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)idx->bti_node;
+ return (leaf->btl_elems + idx->bti_offset * tree->bt_elem_size);
+ }
+ ASSERT(idx->bti_node->bth_core);
+ zfs_btree_core_t *node = (zfs_btree_core_t *)idx->bti_node;
+ return (node->btc_elems + idx->bti_offset * tree->bt_elem_size);
+}
+
+/* Add the given value to the tree. Must not already be in the tree. */
+void
+zfs_btree_add(zfs_btree_t *tree, const void *node)
+{
+ zfs_btree_index_t where = {0};
+ VERIFY3P(zfs_btree_find(tree, node, &where), ==, NULL);
+ zfs_btree_insert(tree, node, &where);
+}
+
+/* Helper function to free a tree node. */
+static void
+zfs_btree_node_destroy(zfs_btree_t *tree, zfs_btree_hdr_t *node)
+{
+ tree->bt_num_nodes--;
+ if (!node->bth_core) {
+ kmem_cache_free(zfs_btree_leaf_cache, node);
+ } else {
+ kmem_free(node, sizeof (zfs_btree_core_t) +
+ BTREE_CORE_ELEMS * tree->bt_elem_size);
+ }
+}
+
+/*
+ * Remove the rm_hdr and the separator to its left from the parent node. The
+ * buffer that rm_hdr was stored in may already be freed, so its contents
+ * cannot be accessed.
+ */
+static void
+zfs_btree_remove_from_node(zfs_btree_t *tree, zfs_btree_core_t *node,
+ zfs_btree_hdr_t *rm_hdr)
+{
+ size_t size = tree->bt_elem_size;
+ uint64_t min_count = (BTREE_CORE_ELEMS / 2) - 1;
+ zfs_btree_hdr_t *hdr = &node->btc_hdr;
+ /*
+ * If the node is the root node and rm_hdr is one of two children,
+ * promote the other child to the root.
+ */
+ if (hdr->bth_parent == NULL && hdr->bth_count <= 1) {
+ ASSERT3U(hdr->bth_count, ==, 1);
+ ASSERT3P(tree->bt_root, ==, node);
+ ASSERT3P(node->btc_children[1], ==, rm_hdr);
+ tree->bt_root = node->btc_children[0];
+ node->btc_children[0]->bth_parent = NULL;
+ zfs_btree_node_destroy(tree, hdr);
+ tree->bt_height--;
+ return;
+ }
+
+ uint64_t idx;
+ for (idx = 0; idx <= hdr->bth_count; idx++) {
+ if (node->btc_children[idx] == rm_hdr)
+ break;
+ }
+ ASSERT3U(idx, <=, hdr->bth_count);
+
+ /*
+ * If the node is the root or it has more than the minimum number of
+ * children, just remove the child and separator, and return.
+ */
+ if (hdr->bth_parent == NULL ||
+ hdr->bth_count > min_count) {
+ /*
+ * Shift the element and children to the right of rm_hdr to
+ * the left by one spot.
+ */
+ bt_shift_core_left(tree, node, idx, hdr->bth_count - idx,
+ BSS_PARALLELOGRAM);
+ hdr->bth_count--;
+ zfs_btree_poison_node_at(tree, hdr, hdr->bth_count);
+ return;
+ }
+
+ ASSERT3U(hdr->bth_count, ==, min_count);
+
+ /*
+ * Now we try to take a node from a neighbor. We check left, then
+ * right. If the neighbor exists and has more than the minimum number
+ * of elements, we move the separator betweeen us and them to our
+ * node, move their closest element (last for left, first for right)
+ * to the separator, and move their closest child to our node. Along
+ * the way we need to collapse the gap made by idx, and (for our right
+ * neighbor) the gap made by removing their first element and child.
+ *
+ * Note: this logic currently doesn't support taking from a neighbor
+ * that isn't a sibling (i.e. a neighbor with a different
+ * parent). This isn't critical functionality, but may be worth
+ * implementing in the future for completeness' sake.
+ */
+ zfs_btree_core_t *parent = hdr->bth_parent;
+ uint64_t parent_idx = zfs_btree_find_parent_idx(tree, hdr);
+
+ zfs_btree_hdr_t *l_hdr = (parent_idx == 0 ? NULL :
+ parent->btc_children[parent_idx - 1]);
+ if (l_hdr != NULL && l_hdr->bth_count > min_count) {
+ /* We can take a node from the left neighbor. */
+ ASSERT(l_hdr->bth_core);
+ zfs_btree_core_t *neighbor = (zfs_btree_core_t *)l_hdr;
+
+ /*
+ * Start by shifting the elements and children in the current
+ * node to the right by one spot.
+ */
+ bt_shift_core_right(tree, node, 0, idx - 1, BSS_TRAPEZOID);
+
+ /*
+ * Move the separator between node and neighbor to the first
+ * element slot in the current node.
+ */
+ uint8_t *separator = parent->btc_elems + (parent_idx - 1) *
+ size;
+ bmov(separator, node->btc_elems, size);
+
+ /* Move the last child of neighbor to our first child slot. */
+ zfs_btree_hdr_t **take_child = neighbor->btc_children +
+ l_hdr->bth_count;
+ bmov(take_child, node->btc_children, sizeof (*take_child));
+ node->btc_children[0]->bth_parent = node;
+
+ /* Move the last element of neighbor to the separator spot. */
+ uint8_t *take_elem = neighbor->btc_elems +
+ (l_hdr->bth_count - 1) * size;
+ bmov(take_elem, separator, size);
+ l_hdr->bth_count--;
+ zfs_btree_poison_node_at(tree, l_hdr, l_hdr->bth_count);
+ return;
+ }
+
+ zfs_btree_hdr_t *r_hdr = (parent_idx == parent->btc_hdr.bth_count ?
+ NULL : parent->btc_children[parent_idx + 1]);
+ if (r_hdr != NULL && r_hdr->bth_count > min_count) {
+ /* We can take a node from the right neighbor. */
+ ASSERT(r_hdr->bth_core);
+ zfs_btree_core_t *neighbor = (zfs_btree_core_t *)r_hdr;
+
+ /*
+ * Shift elements in node left by one spot to overwrite rm_hdr
+ * and the separator before it.
+ */
+ bt_shift_core_left(tree, node, idx, hdr->bth_count - idx,
+ BSS_PARALLELOGRAM);
+
+ /*
+ * Move the separator between node and neighbor to the last
+ * element spot in node.
+ */
+ uint8_t *separator = parent->btc_elems + parent_idx * size;
+ bmov(separator, node->btc_elems + (hdr->bth_count - 1) * size,
+ size);
+
+ /*
+ * Move the first child of neighbor to the last child spot in
+ * node.
+ */
+ zfs_btree_hdr_t **take_child = neighbor->btc_children;
+ bmov(take_child, node->btc_children + hdr->bth_count,
+ sizeof (*take_child));
+ node->btc_children[hdr->bth_count]->bth_parent = node;
+
+ /* Move the first element of neighbor to the separator spot. */
+ uint8_t *take_elem = neighbor->btc_elems;
+ bmov(take_elem, separator, size);
+ r_hdr->bth_count--;
+
+ /*
+ * Shift the elements and children of neighbor to cover the
+ * stolen elements.
+ */
+ bt_shift_core_left(tree, neighbor, 1, r_hdr->bth_count,
+ BSS_TRAPEZOID);
+ zfs_btree_poison_node_at(tree, r_hdr, r_hdr->bth_count);
+ return;
+ }
+
+ /*
+ * In this case, neither of our neighbors can spare an element, so we
+ * need to merge with one of them. We prefer the left one,
+ * arabitrarily. Move the separator into the leftmost merging node
+ * (which may be us or the left neighbor), and then move the right
+ * merging node's elements. Once that's done, we go back and delete
+ * the element we're removing. Finally, go into the parent and delete
+ * the right merging node and the separator. This may cause further
+ * merging.
+ */
+ zfs_btree_hdr_t *new_rm_hdr, *keep_hdr;
+ uint64_t new_idx = idx;
+ if (l_hdr != NULL) {
+ keep_hdr = l_hdr;
+ new_rm_hdr = hdr;
+ new_idx += keep_hdr->bth_count + 1;
+ } else {
+ ASSERT3P(r_hdr, !=, NULL);
+ keep_hdr = hdr;
+ new_rm_hdr = r_hdr;
+ parent_idx++;
+ }
+
+ ASSERT(keep_hdr->bth_core);
+ ASSERT(new_rm_hdr->bth_core);
+
+ zfs_btree_core_t *keep = (zfs_btree_core_t *)keep_hdr;
+ zfs_btree_core_t *rm = (zfs_btree_core_t *)new_rm_hdr;
+
+ if (zfs_btree_verify_intensity >= 5) {
+ for (int i = 0; i < new_rm_hdr->bth_count + 1; i++) {
+ zfs_btree_verify_poison_at(tree, keep_hdr,
+ keep_hdr->bth_count + i);
+ }
+ }
+
+ /* Move the separator into the left node. */
+ uint8_t *e_out = keep->btc_elems + keep_hdr->bth_count * size;
+ uint8_t *separator = parent->btc_elems + (parent_idx - 1) *
+ size;
+ bmov(separator, e_out, size);
+ keep_hdr->bth_count++;
+
+ /* Move all our elements and children into the left node. */
+ bt_transfer_core(tree, rm, 0, new_rm_hdr->bth_count, keep,
+ keep_hdr->bth_count, BSS_TRAPEZOID);
+
+ uint64_t old_count = keep_hdr->bth_count;
+
+ /* Update bookkeeping */
+ keep_hdr->bth_count += new_rm_hdr->bth_count;
+ ASSERT3U(keep_hdr->bth_count, ==, (min_count * 2) + 1);
+
+ /*
+ * Shift the element and children to the right of rm_hdr to
+ * the left by one spot.
+ */
+ ASSERT3P(keep->btc_children[new_idx], ==, rm_hdr);
+ bt_shift_core_left(tree, keep, new_idx, keep_hdr->bth_count - new_idx,
+ BSS_PARALLELOGRAM);
+ keep_hdr->bth_count--;
+
+ /* Reparent all our children to point to the left node. */
+ zfs_btree_hdr_t **new_start = keep->btc_children +
+ old_count - 1;
+ for (int i = 0; i < new_rm_hdr->bth_count + 1; i++)
+ new_start[i]->bth_parent = keep;
+ for (int i = 0; i <= keep_hdr->bth_count; i++) {
+ ASSERT3P(keep->btc_children[i]->bth_parent, ==, keep);
+ ASSERT3P(keep->btc_children[i], !=, rm_hdr);
+ }
+ zfs_btree_poison_node_at(tree, keep_hdr, keep_hdr->bth_count);
+
+ new_rm_hdr->bth_count = 0;
+ zfs_btree_node_destroy(tree, new_rm_hdr);
+ zfs_btree_remove_from_node(tree, parent, new_rm_hdr);
+}
+
+/* Remove the element at the specific location. */
+void
+zfs_btree_remove_from(zfs_btree_t *tree, zfs_btree_index_t *where)
+{
+ size_t size = tree->bt_elem_size;
+ zfs_btree_hdr_t *hdr = where->bti_node;
+ uint64_t idx = where->bti_offset;
+ uint64_t capacity = P2ALIGN((BTREE_LEAF_SIZE -
+ sizeof (zfs_btree_hdr_t)) / size, 2);
+
+ ASSERT(!where->bti_before);
+ if (tree->bt_bulk != NULL) {
+ /*
+ * Leave bulk insert mode. Note that our index would be
+ * invalid after we correct the tree, so we copy the value
+ * we're planning to remove and find it again after
+ * bulk_finish.
+ */
+ uint8_t *value = zfs_btree_get(tree, where);
+ uint8_t *tmp = kmem_alloc(size, KM_SLEEP);
+ bmov(value, tmp, size);
+ zfs_btree_bulk_finish(tree);
+ VERIFY3P(zfs_btree_find(tree, tmp, where), !=, NULL);
+ kmem_free(tmp, size);
+ hdr = where->bti_node;
+ idx = where->bti_offset;
+ }
+
+ tree->bt_num_elems--;
+ /*
+ * If the element happens to be in a core node, we move a leaf node's
+ * element into its place and then remove the leaf node element. This
+ * makes the rebalance logic not need to be recursive both upwards and
+ * downwards.
+ */
+ if (hdr->bth_core) {
+ zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
+ zfs_btree_hdr_t *left_subtree = node->btc_children[idx];
+ void *new_value = zfs_btree_last_helper(tree, left_subtree,
+ where);
+ ASSERT3P(new_value, !=, NULL);
+
+ bmov(new_value, node->btc_elems + idx * size, size);
+
+ hdr = where->bti_node;
+ idx = where->bti_offset;
+ ASSERT(!where->bti_before);
+ }
+
+ /*
+ * First, we'll update the leaf's metadata. Then, we shift any
+ * elements after the idx to the left. After that, we rebalance if
+ * needed.
+ */
+ ASSERT(!hdr->bth_core);
+ zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;
+ ASSERT3U(hdr->bth_count, >, 0);
+
+ uint64_t min_count = (capacity / 2) - 1;
+
+ /*
+ * If we're over the minimum size or this is the root, just overwrite
+ * the value and return.
+ */
+ if (hdr->bth_count > min_count || hdr->bth_parent == NULL) {
+ hdr->bth_count--;
+ bt_shift_leaf_left(tree, leaf, idx + 1, hdr->bth_count - idx);
+ if (hdr->bth_parent == NULL) {
+ ASSERT0(tree->bt_height);
+ if (hdr->bth_count == 0) {
+ tree->bt_root = NULL;
+ tree->bt_height--;
+ zfs_btree_node_destroy(tree, &leaf->btl_hdr);
+ }
+ }
+ if (tree->bt_root != NULL)
+ zfs_btree_poison_node_at(tree, hdr, hdr->bth_count);
+ zfs_btree_verify(tree);
+ return;
+ }
+ ASSERT3U(hdr->bth_count, ==, min_count);
+
+ /*
+ * Now we try to take a node from a sibling. We check left, then
+ * right. If they exist and have more than the minimum number of
+ * elements, we move the separator betweeen us and them to our node
+ * and move their closest element (last for left, first for right) to
+ * the separator. Along the way we need to collapse the gap made by
+ * idx, and (for our right neighbor) the gap made by removing their
+ * first element.
+ *
+ * Note: this logic currently doesn't support taking from a neighbor
+ * that isn't a sibling. This isn't critical functionality, but may be
+ * worth implementing in the future for completeness' sake.
+ */
+ zfs_btree_core_t *parent = hdr->bth_parent;
+ uint64_t parent_idx = zfs_btree_find_parent_idx(tree, hdr);
+
+ zfs_btree_hdr_t *l_hdr = (parent_idx == 0 ? NULL :
+ parent->btc_children[parent_idx - 1]);
+ if (l_hdr != NULL && l_hdr->bth_count > min_count) {
+ /* We can take a node from the left neighbor. */
+ ASSERT(!l_hdr->bth_core);
+
+ /*
+ * Move our elements back by one spot to make room for the
+ * stolen element and overwrite the element being removed.
+ */
+ bt_shift_leaf_right(tree, leaf, 0, idx);
+ uint8_t *separator = parent->btc_elems + (parent_idx - 1) *
+ size;
+ uint8_t *take_elem = ((zfs_btree_leaf_t *)l_hdr)->btl_elems +
+ (l_hdr->bth_count - 1) * size;
+ /* Move the separator to our first spot. */
+ bmov(separator, leaf->btl_elems, size);
+
+ /* Move our neighbor's last element to the separator. */
+ bmov(take_elem, separator, size);
+
+ /* Update the bookkeeping. */
+ l_hdr->bth_count--;
+ zfs_btree_poison_node_at(tree, l_hdr, l_hdr->bth_count);
+
+ zfs_btree_verify(tree);
+ return;
+ }
+
+ zfs_btree_hdr_t *r_hdr = (parent_idx == parent->btc_hdr.bth_count ?
+ NULL : parent->btc_children[parent_idx + 1]);
+ if (r_hdr != NULL && r_hdr->bth_count > min_count) {
+ /* We can take a node from the right neighbor. */
+ ASSERT(!r_hdr->bth_core);
+ zfs_btree_leaf_t *neighbor = (zfs_btree_leaf_t *)r_hdr;
+
+ /*
+ * Move our elements after the element being removed forwards
+ * by one spot to make room for the stolen element and
+ * overwrite the element being removed.
+ */
+ bt_shift_leaf_left(tree, leaf, idx + 1, hdr->bth_count - idx -
+ 1);
+
+ uint8_t *separator = parent->btc_elems + parent_idx * size;
+ uint8_t *take_elem = ((zfs_btree_leaf_t *)r_hdr)->btl_elems;
+ /* Move the separator between us to our last spot. */
+ bmov(separator, leaf->btl_elems + (hdr->bth_count - 1) * size,
+ size);
+
+ /* Move our neighbor's first element to the separator. */
+ bmov(take_elem, separator, size);
+
+ /* Update the bookkeeping. */
+ r_hdr->bth_count--;
+
+ /*
+ * Move our neighbors elements forwards to overwrite the
+ * stolen element.
+ */
+ bt_shift_leaf_left(tree, neighbor, 1, r_hdr->bth_count);
+ zfs_btree_poison_node_at(tree, r_hdr, r_hdr->bth_count);
+ zfs_btree_verify(tree);
+ return;
+ }
+
+ /*
+ * In this case, neither of our neighbors can spare an element, so we
+ * need to merge with one of them. We prefer the left one,
+ * arabitrarily. Move the separator into the leftmost merging node
+ * (which may be us or the left neighbor), and then move the right
+ * merging node's elements. Once that's done, we go back and delete
+ * the element we're removing. Finally, go into the parent and delete
+ * the right merging node and the separator. This may cause further
+ * merging.
+ */
+ zfs_btree_hdr_t *rm_hdr, *keep_hdr;
+ uint64_t new_idx = idx;
+ if (l_hdr != NULL) {
+ keep_hdr = l_hdr;
+ rm_hdr = hdr;
+ new_idx += keep_hdr->bth_count + 1; // 449
+ } else {
+ ASSERT3P(r_hdr, !=, NULL);
+ keep_hdr = hdr;
+ rm_hdr = r_hdr;
+ parent_idx++;
+ }
+
+ ASSERT(!keep_hdr->bth_core);
+ ASSERT(!rm_hdr->bth_core);
+ ASSERT3U(keep_hdr->bth_count, ==, min_count);
+ ASSERT3U(rm_hdr->bth_count, ==, min_count);
+
+ zfs_btree_leaf_t *keep = (zfs_btree_leaf_t *)keep_hdr;
+ zfs_btree_leaf_t *rm = (zfs_btree_leaf_t *)rm_hdr;
+
+ if (zfs_btree_verify_intensity >= 5) {
+ for (int i = 0; i < rm_hdr->bth_count + 1; i++) {
+ zfs_btree_verify_poison_at(tree, keep_hdr,
+ keep_hdr->bth_count + i);
+ }
+ }
+ /*
+ * Move the separator into the first open spot in the left
+ * neighbor.
+ */
+ uint8_t *out = keep->btl_elems + keep_hdr->bth_count * size;
+ uint8_t *separator = parent->btc_elems + (parent_idx - 1) *
+ size;
+ bmov(separator, out, size);
+ keep_hdr->bth_count++;
+
+ /* Move our elements to the left neighbor. */
+ bt_transfer_leaf(tree, rm, 0, rm_hdr->bth_count, keep,
+ keep_hdr->bth_count);
+
+ /* Update the bookkeeping. */
+ keep_hdr->bth_count += rm_hdr->bth_count;
+ ASSERT3U(keep_hdr->bth_count, ==, min_count * 2 + 1);
+
+ /* Remove the value from the node */
+ keep_hdr->bth_count--;
+ bt_shift_leaf_left(tree, keep, new_idx + 1, keep_hdr->bth_count -
+ new_idx);
+ zfs_btree_poison_node_at(tree, keep_hdr, keep_hdr->bth_count);
+
+ rm_hdr->bth_count = 0;
+ zfs_btree_node_destroy(tree, rm_hdr);
+ /* Remove the emptied node from the parent. */
+ zfs_btree_remove_from_node(tree, parent, rm_hdr);
+ zfs_btree_verify(tree);
+}
+
+/* Remove the given value from the tree. */
+void
+zfs_btree_remove(zfs_btree_t *tree, const void *value)
+{
+ zfs_btree_index_t where = {0};
+ VERIFY3P(zfs_btree_find(tree, value, &where), !=, NULL);
+ zfs_btree_remove_from(tree, &where);
+}
+
+/* Return the number of elements in the tree. */
+ulong_t
+zfs_btree_numnodes(zfs_btree_t *tree)
+{
+ return (tree->bt_num_elems);
+}
+
+/*
+ * This function is used to visit all the elements in the tree before
+ * destroying the tree. This allows the calling code to perform any cleanup it
+ * needs to do. This is more efficient than just removing the first element
+ * over and over, because it removes all rebalancing. Once the destroy_nodes()
+ * function has been called, no other btree operations are valid until it
+ * returns NULL, which point the only valid operation is zfs_btree_destroy().
+ *
+ * example:
+ *
+ * zfs_btree_index_t *cookie = NULL;
+ * my_data_t *node;
+ *
+ * while ((node = zfs_btree_destroy_nodes(tree, &cookie)) != NULL)
+ * free(node->ptr);
+ * zfs_btree_destroy(tree);
+ *
+ */
+void *
+zfs_btree_destroy_nodes(zfs_btree_t *tree, zfs_btree_index_t **cookie)
+{
+ if (*cookie == NULL) {
+ if (tree->bt_height == -1)
+ return (NULL);
+ *cookie = kmem_alloc(sizeof (**cookie), KM_SLEEP);
+ return (zfs_btree_first(tree, *cookie));
+ }
+
+ void *rval = zfs_btree_next_helper(tree, *cookie, *cookie,
+ zfs_btree_node_destroy);
+ if (rval == NULL) {
+ tree->bt_root = NULL;
+ tree->bt_height = -1;
+ tree->bt_num_elems = 0;
+ kmem_free(*cookie, sizeof (**cookie));
+ tree->bt_bulk = NULL;
+ }
+ return (rval);
+}
+
+static void
+zfs_btree_clear_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
+{
+ if (hdr->bth_core) {
+ zfs_btree_core_t *btc = (zfs_btree_core_t *)hdr;
+ for (int i = 0; i <= hdr->bth_count; i++) {
+ zfs_btree_clear_helper(tree, btc->btc_children[i]);
+ }
+ }
+
+ zfs_btree_node_destroy(tree, hdr);
+}
+
+void
+zfs_btree_clear(zfs_btree_t *tree)
+{
+ if (tree->bt_root == NULL) {
+ ASSERT0(tree->bt_num_elems);
+ return;
+ }
+
+ zfs_btree_clear_helper(tree, tree->bt_root);
+ tree->bt_num_elems = 0;
+ tree->bt_root = NULL;
+ tree->bt_num_nodes = 0;
+ tree->bt_height = -1;
+ tree->bt_bulk = NULL;
+}
+
+void
+zfs_btree_destroy(zfs_btree_t *tree)
+{
+ ASSERT0(tree->bt_num_elems);
+ ASSERT3P(tree->bt_root, ==, NULL);
+}
+
+/* Verify that every child of this node has the correct parent pointer. */
+static void
+zfs_btree_verify_pointers_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
+{
+ if (!hdr->bth_core)
+ return;
+
+ zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
+ for (int i = 0; i <= hdr->bth_count; i++) {
+ VERIFY3P(node->btc_children[i]->bth_parent, ==, hdr);
+ zfs_btree_verify_pointers_helper(tree, node->btc_children[i]);
+ }
+}
+
+/* Verify that every node has the correct parent pointer. */
+static void
+zfs_btree_verify_pointers(zfs_btree_t *tree)
+{
+ if (tree->bt_height == -1) {
+ VERIFY3P(tree->bt_root, ==, NULL);
+ return;
+ }
+ VERIFY3P(tree->bt_root->bth_parent, ==, NULL);
+ zfs_btree_verify_pointers_helper(tree, tree->bt_root);
+}
+
+/*
+ * Verify that all the current node and its children satisfy the count
+ * invariants, and return the total count in the subtree rooted in this node.
+ */
+static uint64_t
+zfs_btree_verify_counts_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
+{
+ if (!hdr->bth_core) {
+ if (tree->bt_root != hdr && hdr != &tree->bt_bulk->btl_hdr) {
+ uint64_t capacity = P2ALIGN((BTREE_LEAF_SIZE -
+ sizeof (zfs_btree_hdr_t)) / tree->bt_elem_size, 2);
+ VERIFY3U(hdr->bth_count, >=, (capacity / 2) - 1);
+ }
+
+ return (hdr->bth_count);
+ } else {
+
+ zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
+ uint64_t ret = hdr->bth_count;
+ if (tree->bt_root != hdr && tree->bt_bulk == NULL)
+ VERIFY3P(hdr->bth_count, >=, BTREE_CORE_ELEMS / 2 - 1);
+ for (int i = 0; i <= hdr->bth_count; i++) {
+ ret += zfs_btree_verify_counts_helper(tree,
+ node->btc_children[i]);
+ }
+
+ return (ret);
+ }
+}
+
+/*
+ * Verify that all nodes satisfy the invariants and that the total number of
+ * elements is correct.
+ */
+static void
+zfs_btree_verify_counts(zfs_btree_t *tree)
+{
+ EQUIV(tree->bt_num_elems == 0, tree->bt_height == -1);
+ if (tree->bt_height == -1) {
+ return;
+ }
+ VERIFY3P(zfs_btree_verify_counts_helper(tree, tree->bt_root), ==,
+ tree->bt_num_elems);
+}
+
+/*
+ * Check that the subtree rooted at this node has a uniform height. Returns
+ * the number of nodes under this node, to help verify bt_num_nodes.
+ */
+static uint64_t
+zfs_btree_verify_height_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr,
+ int64_t height)
+{
+ if (!hdr->bth_core) {
+ VERIFY0(height);
+ return (1);
+ }
+
+ VERIFY(hdr->bth_core);
+ zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
+ uint64_t ret = 1;
+ for (int i = 0; i <= hdr->bth_count; i++) {
+ ret += zfs_btree_verify_height_helper(tree,
+ node->btc_children[i], height - 1);
+ }
+ return (ret);
+}
+
+/*
+ * Check that the tree rooted at this node has a uniform height, and that the
+ * bt_height in the tree is correct.
+ */
+static void
+zfs_btree_verify_height(zfs_btree_t *tree)
+{
+ EQUIV(tree->bt_height == -1, tree->bt_root == NULL);
+ if (tree->bt_height == -1) {
+ return;
+ }
+
+ VERIFY3U(zfs_btree_verify_height_helper(tree, tree->bt_root,
+ tree->bt_height), ==, tree->bt_num_nodes);
+}
+
+/*
+ * Check that the elements in this node are sorted, and that if this is a core
+ * node, the separators are properly between the subtrees they separaate and
+ * that the children also satisfy this requirement.
+ */
+static void
+zfs_btree_verify_order_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
+{
+ size_t size = tree->bt_elem_size;
+ if (!hdr->bth_core) {
+ zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;
+ for (int i = 1; i < hdr->bth_count; i++) {
+ VERIFY3S(tree->bt_compar(leaf->btl_elems + (i - 1) *
+ size, leaf->btl_elems + i * size), ==, -1);
+ }
+ return;
+ }
+
+ zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
+ for (int i = 1; i < hdr->bth_count; i++) {
+ VERIFY3S(tree->bt_compar(node->btc_elems + (i - 1) * size,
+ node->btc_elems + i * size), ==, -1);
+ }
+ for (int i = 0; i < hdr->bth_count; i++) {
+ uint8_t *left_child_last = NULL;
+ zfs_btree_hdr_t *left_child_hdr = node->btc_children[i];
+ if (left_child_hdr->bth_core) {
+ zfs_btree_core_t *left_child =
+ (zfs_btree_core_t *)left_child_hdr;
+ left_child_last = left_child->btc_elems +
+ (left_child_hdr->bth_count - 1) * size;
+ } else {
+ zfs_btree_leaf_t *left_child =
+ (zfs_btree_leaf_t *)left_child_hdr;
+ left_child_last = left_child->btl_elems +
+ (left_child_hdr->bth_count - 1) * size;
+ }
+ if (tree->bt_compar(node->btc_elems + i * size,
+ left_child_last) != 1) {
+ panic("btree: compar returned %d (expected 1) at "
+ "%px %d: compar(%px, %px)", tree->bt_compar(
+ node->btc_elems + i * size, left_child_last),
+ (void *)node, i, (void *)(node->btc_elems + i *
+ size), (void *)left_child_last);
+ }
+
+ uint8_t *right_child_first = NULL;
+ zfs_btree_hdr_t *right_child_hdr = node->btc_children[i + 1];
+ if (right_child_hdr->bth_core) {
+ zfs_btree_core_t *right_child =
+ (zfs_btree_core_t *)right_child_hdr;
+ right_child_first = right_child->btc_elems;
+ } else {
+ zfs_btree_leaf_t *right_child =
+ (zfs_btree_leaf_t *)right_child_hdr;
+ right_child_first = right_child->btl_elems;
+ }
+ if (tree->bt_compar(node->btc_elems + i * size,
+ right_child_first) != -1) {
+ panic("btree: compar returned %d (expected -1) at "
+ "%px %d: compar(%px, %px)", tree->bt_compar(
+ node->btc_elems + i * size, right_child_first),
+ (void *)node, i, (void *)(node->btc_elems + i *
+ size), (void *)right_child_first);
+ }
+ }
+ for (int i = 0; i <= hdr->bth_count; i++) {
+ zfs_btree_verify_order_helper(tree, node->btc_children[i]);
+ }
+}
+
+/* Check that all elements in the tree are in sorted order. */
+static void
+zfs_btree_verify_order(zfs_btree_t *tree)
+{
+ EQUIV(tree->bt_height == -1, tree->bt_root == NULL);
+ if (tree->bt_height == -1) {
+ return;
+ }
+
+ zfs_btree_verify_order_helper(tree, tree->bt_root);
+}
+
+#ifdef ZFS_DEBUG
+/* Check that all unused memory is poisoned correctly. */
+static void
+zfs_btree_verify_poison_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
+{
+ size_t size = tree->bt_elem_size;
+ if (!hdr->bth_core) {
+ zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;
+ uint8_t val = 0x0f;
+ for (int i = hdr->bth_count * size; i < BTREE_LEAF_SIZE -
+ sizeof (zfs_btree_hdr_t); i++) {
+ VERIFY3U(leaf->btl_elems[i], ==, val);
+ }
+ } else {
+ zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
+ uint8_t val = 0x0f;
+ for (int i = hdr->bth_count * size; i < BTREE_CORE_ELEMS * size;
+ i++) {
+ VERIFY3U(node->btc_elems[i], ==, val);
+ }
+
+ for (int i = hdr->bth_count + 1; i <= BTREE_CORE_ELEMS; i++) {
+ VERIFY3P(node->btc_children[i], ==,
+ (zfs_btree_hdr_t *)BTREE_POISON);
+ }
+
+ for (int i = 0; i <= hdr->bth_count; i++) {
+ zfs_btree_verify_poison_helper(tree,
+ node->btc_children[i]);
+ }
+ }
+}
+#endif
+
+/* Check that unused memory in the tree is still poisoned. */
+static void
+zfs_btree_verify_poison(zfs_btree_t *tree)
+{
+#ifdef ZFS_DEBUG
+ if (tree->bt_height == -1)
+ return;
+ zfs_btree_verify_poison_helper(tree, tree->bt_root);
+#endif
+}
+
+void
+zfs_btree_verify(zfs_btree_t *tree)
+{
+ if (zfs_btree_verify_intensity == 0)
+ return;
+ zfs_btree_verify_height(tree);
+ if (zfs_btree_verify_intensity == 1)
+ return;
+ zfs_btree_verify_pointers(tree);
+ if (zfs_btree_verify_intensity == 2)
+ return;
+ zfs_btree_verify_counts(tree);
+ if (zfs_btree_verify_intensity == 3)
+ return;
+ zfs_btree_verify_order(tree);
+
+ if (zfs_btree_verify_intensity == 4)
+ return;
+ zfs_btree_verify_poison(tree);
+}
diff --git a/module/zfs/ddt.c b/module/zfs/ddt.c
index a0f90496a..5e7b31c76 100644
--- a/module/zfs/ddt.c
+++ b/module/zfs/ddt.c
@@ -783,7 +783,7 @@ ddt_entry_compare(const void *x1, const void *x2)
break;
}
- return (AVL_ISIGN(cmp));
+ return (TREE_ISIGN(cmp));
}
static ddt_t *
diff --git a/module/zfs/dmu_objset.c b/module/zfs/dmu_objset.c
index de57b170f..f7498854a 100644
--- a/module/zfs/dmu_objset.c
+++ b/module/zfs/dmu_objset.c
@@ -1788,7 +1788,7 @@ userquota_compare(const void *l, const void *r)
*/
rv = strcmp(luqn->uqn_id, ruqn->uqn_id);
- return (AVL_ISIGN(rv));
+ return (TREE_ISIGN(rv));
}
static void
diff --git a/module/zfs/dmu_recv.c b/module/zfs/dmu_recv.c
index 6249e165f..48c3705c6 100644
--- a/module/zfs/dmu_recv.c
+++ b/module/zfs/dmu_recv.c
@@ -1209,7 +1209,7 @@ guid_compare(const void *arg1, const void *arg2)
const guid_map_entry_t *gmep1 = (const guid_map_entry_t *)arg1;
const guid_map_entry_t *gmep2 = (const guid_map_entry_t *)arg2;
- return (AVL_CMP(gmep1->guid, gmep2->guid));
+ return (TREE_CMP(gmep1->guid, gmep2->guid));
}
static void
diff --git a/module/zfs/dmu_send.c b/module/zfs/dmu_send.c
index 42116a1c3..ae4f91fc3 100644
--- a/module/zfs/dmu_send.c
+++ b/module/zfs/dmu_send.c
@@ -1329,11 +1329,11 @@ send_range_after(const struct send_range *from, const struct send_range *to)
return (-1);
if (from_obj >= to_end_obj)
return (1);
- int64_t cmp = AVL_CMP(to->type == OBJECT_RANGE, from->type ==
+ int64_t cmp = TREE_CMP(to->type == OBJECT_RANGE, from->type ==
OBJECT_RANGE);
if (unlikely(cmp))
return (cmp);
- cmp = AVL_CMP(to->type == OBJECT, from->type == OBJECT);
+ cmp = TREE_CMP(to->type == OBJECT, from->type == OBJECT);
if (unlikely(cmp))
return (cmp);
if (from->end_blkid <= to->start_blkid)
@@ -1402,7 +1402,7 @@ send_range_start_compare(struct send_range *r1, struct send_range *r2)
uint64_t r1_l0equiv = r1->start_blkid;
uint64_t r2_objequiv = r2->object;
uint64_t r2_l0equiv = r2->start_blkid;
- int64_t cmp = AVL_CMP(r1->eos_marker, r2->eos_marker);
+ int64_t cmp = TREE_CMP(r1->eos_marker, r2->eos_marker);
if (unlikely(cmp))
return (cmp);
if (r1->object == 0) {
@@ -1414,17 +1414,17 @@ send_range_start_compare(struct send_range *r1, struct send_range *r2)
r2_l0equiv = 0;
}
- cmp = AVL_CMP(r1_objequiv, r2_objequiv);
+ cmp = TREE_CMP(r1_objequiv, r2_objequiv);
if (likely(cmp))
return (cmp);
- cmp = AVL_CMP(r2->type == OBJECT_RANGE, r1->type == OBJECT_RANGE);
+ cmp = TREE_CMP(r2->type == OBJECT_RANGE, r1->type == OBJECT_RANGE);
if (unlikely(cmp))
return (cmp);
- cmp = AVL_CMP(r2->type == OBJECT, r1->type == OBJECT);
+ cmp = TREE_CMP(r2->type == OBJECT, r1->type == OBJECT);
if (unlikely(cmp))
return (cmp);
- return (AVL_CMP(r1_l0equiv, r2_l0equiv));
+ return (TREE_CMP(r1_l0equiv, r2_l0equiv));
}
enum q_idx {
diff --git a/module/zfs/dnode.c b/module/zfs/dnode.c
index 95132344c..9bca72d53 100644
--- a/module/zfs/dnode.c
+++ b/module/zfs/dnode.c
@@ -20,7 +20,7 @@
*/
/*
* Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
- * Copyright (c) 2012, 2017 by Delphix. All rights reserved.
+ * Copyright (c) 2012, 2019 by Delphix. All rights reserved.
* Copyright (c) 2014 Spectra Logic Corporation, All rights reserved.
*/
@@ -89,11 +89,11 @@ dbuf_compare(const void *x1, const void *x2)
const dmu_buf_impl_t *d1 = x1;
const dmu_buf_impl_t *d2 = x2;
- int cmp = AVL_CMP(d1->db_level, d2->db_level);
+ int cmp = TREE_CMP(d1->db_level, d2->db_level);
if (likely(cmp))
return (cmp);
- cmp = AVL_CMP(d1->db_blkid, d2->db_blkid);
+ cmp = TREE_CMP(d1->db_blkid, d2->db_blkid);
if (likely(cmp))
return (cmp);
@@ -105,7 +105,7 @@ dbuf_compare(const void *x1, const void *x2)
return (1);
}
- return (AVL_PCMP(d1, d2));
+ return (TREE_PCMP(d1, d2));
}
/* ARGSUSED */
@@ -2218,7 +2218,8 @@ done:
{
int txgoff = tx->tx_txg & TXG_MASK;
if (dn->dn_free_ranges[txgoff] == NULL) {
- dn->dn_free_ranges[txgoff] = range_tree_create(NULL, NULL);
+ dn->dn_free_ranges[txgoff] = range_tree_create(NULL,
+ RANGE_SEG64, NULL, 0, 0);
}
range_tree_clear(dn->dn_free_ranges[txgoff], blkid, nblks);
range_tree_add(dn->dn_free_ranges[txgoff], blkid, nblks);
diff --git a/module/zfs/dsl_bookmark.c b/module/zfs/dsl_bookmark.c
index 2126f3d9b..42c612abc 100644
--- a/module/zfs/dsl_bookmark.c
+++ b/module/zfs/dsl_bookmark.c
@@ -595,16 +595,16 @@ dsl_bookmark_compare(const void *l, const void *r)
const dsl_bookmark_node_t *ldbn = l;
const dsl_bookmark_node_t *rdbn = r;
- int64_t cmp = AVL_CMP(ldbn->dbn_phys.zbm_creation_txg,
+ int64_t cmp = TREE_CMP(ldbn->dbn_phys.zbm_creation_txg,
rdbn->dbn_phys.zbm_creation_txg);
if (likely(cmp))
return (cmp);
- cmp = AVL_CMP((ldbn->dbn_phys.zbm_flags & ZBM_FLAG_HAS_FBN),
+ cmp = TREE_CMP((ldbn->dbn_phys.zbm_flags & ZBM_FLAG_HAS_FBN),
(rdbn->dbn_phys.zbm_flags & ZBM_FLAG_HAS_FBN));
if (likely(cmp))
return (cmp);
cmp = strcmp(ldbn->dbn_name, rdbn->dbn_name);
- return (AVL_ISIGN(cmp));
+ return (TREE_ISIGN(cmp));
}
/*
diff --git a/module/zfs/dsl_deadlist.c b/module/zfs/dsl_deadlist.c
index 2e4d18ade..8cb0f90fb 100644
--- a/module/zfs/dsl_deadlist.c
+++ b/module/zfs/dsl_deadlist.c
@@ -118,7 +118,7 @@ dsl_deadlist_compare(const void *arg1, const void *arg2)
const dsl_deadlist_entry_t *dle1 = arg1;
const dsl_deadlist_entry_t *dle2 = arg2;
- return (AVL_CMP(dle1->dle_mintxg, dle2->dle_mintxg));
+ return (TREE_CMP(dle1->dle_mintxg, dle2->dle_mintxg));
}
static int
@@ -127,7 +127,7 @@ dsl_deadlist_cache_compare(const void *arg1, const void *arg2)
const dsl_deadlist_cache_entry_t *dlce1 = arg1;
const dsl_deadlist_cache_entry_t *dlce2 = arg2;
- return (AVL_CMP(dlce1->dlce_mintxg, dlce2->dlce_mintxg));
+ return (TREE_CMP(dlce1->dlce_mintxg, dlce2->dlce_mintxg));
}
static void
@@ -917,14 +917,14 @@ livelist_compare(const void *larg, const void *rarg)
uint64_t r_dva0_vdev = DVA_GET_VDEV(&r->blk_dva[0]);
if (l_dva0_vdev != r_dva0_vdev)
- return (AVL_CMP(l_dva0_vdev, r_dva0_vdev));
+ return (TREE_CMP(l_dva0_vdev, r_dva0_vdev));
/* if vdevs are equal, sort by offsets. */
uint64_t l_dva0_offset = DVA_GET_OFFSET(&l->blk_dva[0]);
uint64_t r_dva0_offset = DVA_GET_OFFSET(&r->blk_dva[0]);
if (l_dva0_offset == r_dva0_offset)
ASSERT3U(l->blk_birth, ==, r->blk_birth);
- return (AVL_CMP(l_dva0_offset, r_dva0_offset));
+ return (TREE_CMP(l_dva0_offset, r_dva0_offset));
}
struct livelist_iter_arg {
diff --git a/module/zfs/dsl_deleg.c b/module/zfs/dsl_deleg.c
index cef460f02..cf8a3c9bb 100644
--- a/module/zfs/dsl_deleg.c
+++ b/module/zfs/dsl_deleg.c
@@ -399,7 +399,7 @@ perm_set_compare(const void *arg1, const void *arg2)
val = strcmp(node1->p_setname, node2->p_setname);
- return (AVL_ISIGN(val));
+ return (TREE_ISIGN(val));
}
/*
diff --git a/module/zfs/dsl_scan.c b/module/zfs/dsl_scan.c
index f1621c9c9..3eacb42f1 100644
--- a/module/zfs/dsl_scan.c
+++ b/module/zfs/dsl_scan.c
@@ -279,7 +279,7 @@ struct dsl_scan_io_queue {
/* trees used for sorting I/Os and extents of I/Os */
range_tree_t *q_exts_by_addr;
- avl_tree_t q_exts_by_size;
+ zfs_btree_t q_exts_by_size;
avl_tree_t q_sios_by_addr;
uint64_t q_sio_memused;
@@ -646,7 +646,8 @@ dsl_scan_sync_state(dsl_scan_t *scn, dmu_tx_t *tx, state_sync_type_t sync_type)
mutex_enter(&vd->vdev_scan_io_queue_lock);
ASSERT3P(avl_first(&q->q_sios_by_addr), ==, NULL);
- ASSERT3P(avl_first(&q->q_exts_by_size), ==, NULL);
+ ASSERT3P(zfs_btree_first(&q->q_exts_by_size, NULL), ==,
+ NULL);
ASSERT3P(range_tree_first(q->q_exts_by_addr), ==, NULL);
mutex_exit(&vd->vdev_scan_io_queue_lock);
}
@@ -1242,7 +1243,7 @@ dsl_scan_should_clear(dsl_scan_t *scn)
queue = tvd->vdev_scan_io_queue;
if (queue != NULL) {
/* # extents in exts_by_size = # in exts_by_addr */
- mused += avl_numnodes(&queue->q_exts_by_size) *
+ mused += zfs_btree_numnodes(&queue->q_exts_by_size) *
sizeof (range_seg_t) + queue->q_sio_memused;
}
mutex_exit(&tvd->vdev_scan_io_queue_lock);
@@ -2847,7 +2848,7 @@ scan_io_queue_gather(dsl_scan_io_queue_t *queue, range_seg_t *rs, list_t *list)
srch_sio = sio_alloc(1);
srch_sio->sio_nr_dvas = 1;
- SIO_SET_OFFSET(srch_sio, rs->rs_start);
+ SIO_SET_OFFSET(srch_sio, rs_get_start(rs, queue->q_exts_by_addr));
/*
* The exact start of the extent might not contain any matching zios,
@@ -2859,10 +2860,12 @@ scan_io_queue_gather(dsl_scan_io_queue_t *queue, range_seg_t *rs, list_t *list)
if (sio == NULL)
sio = avl_nearest(&queue->q_sios_by_addr, idx, AVL_AFTER);
- while (sio != NULL &&
- SIO_GET_OFFSET(sio) < rs->rs_end && num_sios <= 32) {
- ASSERT3U(SIO_GET_OFFSET(sio), >=, rs->rs_start);
- ASSERT3U(SIO_GET_END_OFFSET(sio), <=, rs->rs_end);
+ while (sio != NULL && SIO_GET_OFFSET(sio) < rs_get_end(rs,
+ queue->q_exts_by_addr) && num_sios <= 32) {
+ ASSERT3U(SIO_GET_OFFSET(sio), >=, rs_get_start(rs,
+ queue->q_exts_by_addr));
+ ASSERT3U(SIO_GET_END_OFFSET(sio), <=, rs_get_end(rs,
+ queue->q_exts_by_addr));
next_sio = AVL_NEXT(&queue->q_sios_by_addr, sio);
avl_remove(&queue->q_sios_by_addr, sio);
@@ -2880,16 +2883,19 @@ scan_io_queue_gather(dsl_scan_io_queue_t *queue, range_seg_t *rs, list_t *list)
* in the segment we update it to reflect the work we were able to
* complete. Otherwise, we remove it from the range tree entirely.
*/
- if (sio != NULL && SIO_GET_OFFSET(sio) < rs->rs_end) {
+ if (sio != NULL && SIO_GET_OFFSET(sio) < rs_get_end(rs,
+ queue->q_exts_by_addr)) {
range_tree_adjust_fill(queue->q_exts_by_addr, rs,
-bytes_issued);
range_tree_resize_segment(queue->q_exts_by_addr, rs,
- SIO_GET_OFFSET(sio), rs->rs_end - SIO_GET_OFFSET(sio));
+ SIO_GET_OFFSET(sio), rs_get_end(rs,
+ queue->q_exts_by_addr) - SIO_GET_OFFSET(sio));
return (B_TRUE);
} else {
- range_tree_remove(queue->q_exts_by_addr, rs->rs_start,
- rs->rs_end - rs->rs_start);
+ uint64_t rstart = rs_get_start(rs, queue->q_exts_by_addr);
+ uint64_t rend = rs_get_end(rs, queue->q_exts_by_addr);
+ range_tree_remove(queue->q_exts_by_addr, rstart, rend - rstart);
return (B_FALSE);
}
}
@@ -2909,6 +2915,7 @@ static range_seg_t *
scan_io_queue_fetch_ext(dsl_scan_io_queue_t *queue)
{
dsl_scan_t *scn = queue->q_scn;
+ range_tree_t *rt = queue->q_exts_by_addr;
ASSERT(MUTEX_HELD(&queue->q_vd->vdev_scan_io_queue_lock));
ASSERT(scn->scn_is_sorted);
@@ -2916,9 +2923,16 @@ scan_io_queue_fetch_ext(dsl_scan_io_queue_t *queue)
/* handle tunable overrides */
if (scn->scn_checkpointing || scn->scn_clearing) {
if (zfs_scan_issue_strategy == 1) {
- return (range_tree_first(queue->q_exts_by_addr));
+ return (range_tree_first(rt));
} else if (zfs_scan_issue_strategy == 2) {
- return (avl_first(&queue->q_exts_by_size));
+ range_seg_t *size_rs =
+ zfs_btree_first(&queue->q_exts_by_size, NULL);
+ uint64_t start = rs_get_start(size_rs, rt);
+ uint64_t size = rs_get_end(size_rs, rt) - start;
+ range_seg_t *addr_rs = range_tree_find(rt, start,
+ size);
+ ASSERT3P(addr_rs, !=, NULL);
+ return (addr_rs);
}
}
@@ -2932,9 +2946,15 @@ scan_io_queue_fetch_ext(dsl_scan_io_queue_t *queue)
* In this case, we instead switch to issuing extents in LBA order.
*/
if (scn->scn_checkpointing) {
- return (range_tree_first(queue->q_exts_by_addr));
+ return (range_tree_first(rt));
} else if (scn->scn_clearing) {
- return (avl_first(&queue->q_exts_by_size));
+ range_seg_t *size_rs = zfs_btree_first(&queue->q_exts_by_size,
+ NULL);
+ uint64_t start = rs_get_start(size_rs, rt);
+ uint64_t size = rs_get_end(size_rs, rt) - start;
+ range_seg_t *addr_rs = range_tree_find(rt, start, size);
+ ASSERT3P(addr_rs, !=, NULL);
+ return (addr_rs);
} else {
return (NULL);
}
@@ -4038,9 +4058,10 @@ scan_exec_io(dsl_pool_t *dp, const blkptr_t *bp, int zio_flags,
static int
ext_size_compare(const void *x, const void *y)
{
- const range_seg_t *rsa = x, *rsb = y;
- uint64_t sa = rsa->rs_end - rsa->rs_start,
- sb = rsb->rs_end - rsb->rs_start;
+ const range_seg_gap_t *rsa = x, *rsb = y;
+
+ uint64_t sa = rsa->rs_end - rsa->rs_start;
+ uint64_t sb = rsb->rs_end - rsb->rs_start;
uint64_t score_a, score_b;
score_a = rsa->rs_fill + ((((rsa->rs_fill << 7) / sa) *
@@ -4069,7 +4090,7 @@ sio_addr_compare(const void *x, const void *y)
{
const scan_io_t *a = x, *b = y;
- return (AVL_CMP(SIO_GET_OFFSET(a), SIO_GET_OFFSET(b)));
+ return (TREE_CMP(SIO_GET_OFFSET(a), SIO_GET_OFFSET(b)));
}
/* IO queues are created on demand when they are needed. */
@@ -4083,8 +4104,8 @@ scan_io_queue_create(vdev_t *vd)
q->q_vd = vd;
q->q_sio_memused = 0;
cv_init(&q->q_zio_cv, NULL, CV_DEFAULT, NULL);
- q->q_exts_by_addr = range_tree_create_impl(&rt_avl_ops,
- &q->q_exts_by_size, ext_size_compare, zfs_scan_max_ext_gap);
+ q->q_exts_by_addr = range_tree_create_impl(&rt_btree_ops, RANGE_SEG_GAP,
+ &q->q_exts_by_size, 0, 0, ext_size_compare, zfs_scan_max_ext_gap);
avl_create(&q->q_sios_by_addr, sio_addr_compare,
sizeof (scan_io_t), offsetof(scan_io_t, sio_nodes.sio_addr_node));
diff --git a/module/zfs/metaslab.c b/module/zfs/metaslab.c
index d4dacbc2f..7b8ac91b1 100644
--- a/module/zfs/metaslab.c
+++ b/module/zfs/metaslab.c
@@ -36,6 +36,7 @@
#include <sys/zfeature.h>
#include <sys/vdev_indirect_mapping.h>
#include <sys/zap.h>
+#include <sys/btree.h>
#define WITH_DF_BLOCK_ALLOCATOR
@@ -184,6 +185,13 @@ int metaslab_df_free_pct = 4;
int metaslab_df_max_search = 16 * 1024 * 1024;
/*
+ * Forces the metaslab_block_picker function to search for at least this many
+ * segments forwards until giving up on finding a segment that the allocation
+ * will fit into.
+ */
+uint32_t metaslab_min_search_count = 100;
+
+/*
* If we are not searching forward (due to metaslab_df_max_search,
* metaslab_df_free_pct, or metaslab_df_alloc_threshold), this tunable
* controls what segment is used. If it is set, we will use the largest free
@@ -277,17 +285,32 @@ uint64_t metaslab_trace_max_entries = 5000;
int max_disabled_ms = 3;
/*
+ * Time (in seconds) to respect ms_max_size when the metaslab is not loaded.
+ * To avoid 64-bit overflow, don't set above UINT32_MAX.
+ */
+unsigned long zfs_metaslab_max_size_cache_sec = 3600; /* 1 hour */
+
+/*
* Maximum percentage of memory to use on storing loaded metaslabs. If loading
* a metaslab would take it over this percentage, the oldest selected metaslab
* is automatically unloaded.
*/
-int zfs_metaslab_mem_limit = 25;
+int zfs_metaslab_mem_limit = 75;
/*
- * Time (in seconds) to respect ms_max_size when the metaslab is not loaded.
- * To avoid 64-bit overflow, don't set above UINT32_MAX.
+ * Force the per-metaslab range trees to use 64-bit integers to store
+ * segments. Used for debugging purposes.
*/
-unsigned long zfs_metaslab_max_size_cache_sec = 3600; /* 1 hour */
+boolean_t zfs_metaslab_force_large_segs = B_FALSE;
+
+/*
+ * By default we only store segments over a certain size in the size-sorted
+ * metaslab trees (ms_allocatable_by_size and
+ * ms_unflushed_frees_by_size). This dramatically reduces memory usage and
+ * improves load and unload times at the cost of causing us to use slightly
+ * larger segments than we would otherwise in some cases.
+ */
+uint32_t metaslab_by_size_min_shift = 14;
static uint64_t metaslab_weight(metaslab_t *, boolean_t);
static void metaslab_set_fragmentation(metaslab_t *, boolean_t);
@@ -299,8 +322,66 @@ static uint64_t metaslab_weight_from_range_tree(metaslab_t *msp);
static void metaslab_flush_update(metaslab_t *, dmu_tx_t *);
static unsigned int metaslab_idx_func(multilist_t *, void *);
static void metaslab_evict(metaslab_t *, uint64_t);
+static void metaslab_rt_add(range_tree_t *rt, range_seg_t *rs, void *arg);
#ifdef _METASLAB_TRACING
kmem_cache_t *metaslab_alloc_trace_cache;
+
+typedef struct metaslab_stats {
+ kstat_named_t metaslabstat_trace_over_limit;
+ kstat_named_t metaslabstat_df_find_under_floor;
+ kstat_named_t metaslabstat_reload_tree;
+} metaslab_stats_t;
+
+static metaslab_stats_t metaslab_stats = {
+ { "trace_over_limit", KSTAT_DATA_UINT64 },
+ { "df_find_under_floor", KSTAT_DATA_UINT64 },
+ { "reload_tree", KSTAT_DATA_UINT64 },
+};
+
+#define METASLABSTAT_BUMP(stat) \
+ atomic_inc_64(&metaslab_stats.stat.value.ui64);
+
+
+kstat_t *metaslab_ksp;
+
+void
+metaslab_stat_init(void)
+{
+ ASSERT(metaslab_alloc_trace_cache == NULL);
+ metaslab_alloc_trace_cache = kmem_cache_create(
+ "metaslab_alloc_trace_cache", sizeof (metaslab_alloc_trace_t),
+ 0, NULL, NULL, NULL, NULL, NULL, 0);
+ metaslab_ksp = kstat_create("zfs", 0, "metaslab_stats",
+ "misc", KSTAT_TYPE_NAMED, sizeof (metaslab_stats) /
+ sizeof (kstat_named_t), KSTAT_FLAG_VIRTUAL);
+ if (metaslab_ksp != NULL) {
+ metaslab_ksp->ks_data = &metaslab_stats;
+ kstat_install(metaslab_ksp);
+ }
+}
+
+void
+metaslab_stat_fini(void)
+{
+ if (metaslab_ksp != NULL) {
+ kstat_delete(metaslab_ksp);
+ metaslab_ksp = NULL;
+ }
+
+ kmem_cache_destroy(metaslab_alloc_trace_cache);
+ metaslab_alloc_trace_cache = NULL;
+}
+#else
+
+void
+metaslab_stat_init(void)
+{
+}
+
+void
+metaslab_stat_fini(void)
+{
+}
#endif
/*
@@ -608,13 +689,13 @@ metaslab_compare(const void *x1, const void *x2)
if (sort1 > sort2)
return (1);
- int cmp = AVL_CMP(m2->ms_weight, m1->ms_weight);
+ int cmp = TREE_CMP(m2->ms_weight, m1->ms_weight);
if (likely(cmp))
return (cmp);
- IMPLY(AVL_CMP(m1->ms_start, m2->ms_start) == 0, m1 == m2);
+ IMPLY(TREE_CMP(m1->ms_start, m2->ms_start) == 0, m1 == m2);
- return (AVL_CMP(m1->ms_start, m2->ms_start));
+ return (TREE_CMP(m1->ms_start, m2->ms_start));
}
/*
@@ -711,17 +792,17 @@ metaslab_sort_by_flushed(const void *va, const void *vb)
const metaslab_t *a = va;
const metaslab_t *b = vb;
- int cmp = AVL_CMP(a->ms_unflushed_txg, b->ms_unflushed_txg);
+ int cmp = TREE_CMP(a->ms_unflushed_txg, b->ms_unflushed_txg);
if (likely(cmp))
return (cmp);
uint64_t a_vdev_id = a->ms_group->mg_vd->vdev_id;
uint64_t b_vdev_id = b->ms_group->mg_vd->vdev_id;
- cmp = AVL_CMP(a_vdev_id, b_vdev_id);
+ cmp = TREE_CMP(a_vdev_id, b_vdev_id);
if (cmp)
return (cmp);
- return (AVL_CMP(a->ms_id, b->ms_id));
+ return (TREE_CMP(a->ms_id, b->ms_id));
}
metaslab_group_t *
@@ -1212,25 +1293,170 @@ metaslab_group_allocatable(metaslab_group_t *mg, metaslab_group_t *rotor,
*/
/*
- * Comparison function for the private size-ordered tree. Tree is sorted
- * by size, larger sizes at the end of the tree.
+ * Comparison function for the private size-ordered tree using 32-bit
+ * ranges. Tree is sorted by size, larger sizes at the end of the tree.
+ */
+static int
+metaslab_rangesize32_compare(const void *x1, const void *x2)
+{
+ const range_seg32_t *r1 = x1;
+ const range_seg32_t *r2 = x2;
+
+ uint64_t rs_size1 = r1->rs_end - r1->rs_start;
+ uint64_t rs_size2 = r2->rs_end - r2->rs_start;
+
+ int cmp = TREE_CMP(rs_size1, rs_size2);
+ if (likely(cmp))
+ return (cmp);
+
+ return (TREE_CMP(r1->rs_start, r2->rs_start));
+}
+
+/*
+ * Comparison function for the private size-ordered tree using 64-bit
+ * ranges. Tree is sorted by size, larger sizes at the end of the tree.
*/
static int
-metaslab_rangesize_compare(const void *x1, const void *x2)
+metaslab_rangesize64_compare(const void *x1, const void *x2)
{
- const range_seg_t *r1 = x1;
- const range_seg_t *r2 = x2;
+ const range_seg64_t *r1 = x1;
+ const range_seg64_t *r2 = x2;
+
uint64_t rs_size1 = r1->rs_end - r1->rs_start;
uint64_t rs_size2 = r2->rs_end - r2->rs_start;
- int cmp = AVL_CMP(rs_size1, rs_size2);
+ int cmp = TREE_CMP(rs_size1, rs_size2);
if (likely(cmp))
return (cmp);
- return (AVL_CMP(r1->rs_start, r2->rs_start));
+ return (TREE_CMP(r1->rs_start, r2->rs_start));
+}
+typedef struct metaslab_rt_arg {
+ zfs_btree_t *mra_bt;
+ uint32_t mra_floor_shift;
+} metaslab_rt_arg_t;
+
+struct mssa_arg {
+ range_tree_t *rt;
+ metaslab_rt_arg_t *mra;
+};
+
+static void
+metaslab_size_sorted_add(void *arg, uint64_t start, uint64_t size)
+{
+ struct mssa_arg *mssap = arg;
+ range_tree_t *rt = mssap->rt;
+ metaslab_rt_arg_t *mrap = mssap->mra;
+ range_seg_max_t seg = {0};
+ rs_set_start(&seg, rt, start);
+ rs_set_end(&seg, rt, start + size);
+ metaslab_rt_add(rt, &seg, mrap);
+}
+
+static void
+metaslab_size_tree_full_load(range_tree_t *rt)
+{
+ metaslab_rt_arg_t *mrap = rt->rt_arg;
+#ifdef _METASLAB_TRACING
+ METASLABSTAT_BUMP(metaslabstat_reload_tree);
+#endif
+ ASSERT0(zfs_btree_numnodes(mrap->mra_bt));
+ mrap->mra_floor_shift = 0;
+ struct mssa_arg arg = {0};
+ arg.rt = rt;
+ arg.mra = mrap;
+ range_tree_walk(rt, metaslab_size_sorted_add, &arg);
}
/*
+ * Create any block allocator specific components. The current allocators
+ * rely on using both a size-ordered range_tree_t and an array of uint64_t's.
+ */
+/* ARGSUSED */
+static void
+metaslab_rt_create(range_tree_t *rt, void *arg)
+{
+ metaslab_rt_arg_t *mrap = arg;
+ zfs_btree_t *size_tree = mrap->mra_bt;
+
+ size_t size;
+ int (*compare) (const void *, const void *);
+ switch (rt->rt_type) {
+ case RANGE_SEG32:
+ size = sizeof (range_seg32_t);
+ compare = metaslab_rangesize32_compare;
+ break;
+ case RANGE_SEG64:
+ size = sizeof (range_seg64_t);
+ compare = metaslab_rangesize64_compare;
+ break;
+ default:
+ panic("Invalid range seg type %d", rt->rt_type);
+ }
+ zfs_btree_create(size_tree, compare, size);
+ mrap->mra_floor_shift = metaslab_by_size_min_shift;
+}
+
+/* ARGSUSED */
+static void
+metaslab_rt_destroy(range_tree_t *rt, void *arg)
+{
+ metaslab_rt_arg_t *mrap = arg;
+ zfs_btree_t *size_tree = mrap->mra_bt;
+
+ zfs_btree_destroy(size_tree);
+ kmem_free(mrap, sizeof (*mrap));
+}
+
+/* ARGSUSED */
+static void
+metaslab_rt_add(range_tree_t *rt, range_seg_t *rs, void *arg)
+{
+ metaslab_rt_arg_t *mrap = arg;
+ zfs_btree_t *size_tree = mrap->mra_bt;
+
+ if (rs_get_end(rs, rt) - rs_get_start(rs, rt) <
+ (1 << mrap->mra_floor_shift))
+ return;
+
+ zfs_btree_add(size_tree, rs);
+}
+
+/* ARGSUSED */
+static void
+metaslab_rt_remove(range_tree_t *rt, range_seg_t *rs, void *arg)
+{
+ metaslab_rt_arg_t *mrap = arg;
+ zfs_btree_t *size_tree = mrap->mra_bt;
+
+ if (rs_get_end(rs, rt) - rs_get_start(rs, rt) < (1 <<
+ mrap->mra_floor_shift))
+ return;
+
+ zfs_btree_remove(size_tree, rs);
+}
+
+/* ARGSUSED */
+static void
+metaslab_rt_vacate(range_tree_t *rt, void *arg)
+{
+ metaslab_rt_arg_t *mrap = arg;
+ zfs_btree_t *size_tree = mrap->mra_bt;
+ zfs_btree_clear(size_tree);
+ zfs_btree_destroy(size_tree);
+
+ metaslab_rt_create(rt, arg);
+}
+
+static range_tree_ops_t metaslab_rt_ops = {
+ .rtop_create = metaslab_rt_create,
+ .rtop_destroy = metaslab_rt_destroy,
+ .rtop_add = metaslab_rt_add,
+ .rtop_remove = metaslab_rt_remove,
+ .rtop_vacate = metaslab_rt_vacate
+};
+
+/*
* ==========================================================================
* Common allocator routines
* ==========================================================================
@@ -1242,16 +1468,20 @@ metaslab_rangesize_compare(const void *x1, const void *x2)
uint64_t
metaslab_largest_allocatable(metaslab_t *msp)
{
- avl_tree_t *t = &msp->ms_allocatable_by_size;
+ zfs_btree_t *t = &msp->ms_allocatable_by_size;
range_seg_t *rs;
if (t == NULL)
return (0);
- rs = avl_last(t);
+ if (zfs_btree_numnodes(t) == 0)
+ metaslab_size_tree_full_load(msp->ms_allocatable);
+
+ rs = zfs_btree_last(t, NULL);
if (rs == NULL)
return (0);
- return (rs->rs_end - rs->rs_start);
+ return (rs_get_end(rs, msp->ms_allocatable) - rs_get_start(rs,
+ msp->ms_allocatable));
}
/*
@@ -1266,7 +1496,10 @@ metaslab_largest_unflushed_free(metaslab_t *msp)
if (msp->ms_unflushed_frees == NULL)
return (0);
- range_seg_t *rs = avl_last(&msp->ms_unflushed_frees_by_size);
+ if (zfs_btree_numnodes(&msp->ms_unflushed_frees_by_size) == 0)
+ metaslab_size_tree_full_load(msp->ms_unflushed_frees);
+ range_seg_t *rs = zfs_btree_last(&msp->ms_unflushed_frees_by_size,
+ NULL);
if (rs == NULL)
return (0);
@@ -1293,8 +1526,8 @@ metaslab_largest_unflushed_free(metaslab_t *msp)
* the largest segment; there may be other usable chunks in the
* largest segment, but we ignore them.
*/
- uint64_t rstart = rs->rs_start;
- uint64_t rsize = rs->rs_end - rstart;
+ uint64_t rstart = rs_get_start(rs, msp->ms_unflushed_frees);
+ uint64_t rsize = rs_get_end(rs, msp->ms_unflushed_frees) - rstart;
for (int t = 0; t < TXG_DEFER_SIZE; t++) {
uint64_t start = 0;
uint64_t size = 0;
@@ -1318,17 +1551,18 @@ metaslab_largest_unflushed_free(metaslab_t *msp)
}
static range_seg_t *
-metaslab_block_find(avl_tree_t *t, uint64_t start, uint64_t size)
+metaslab_block_find(zfs_btree_t *t, range_tree_t *rt, uint64_t start,
+ uint64_t size, zfs_btree_index_t *where)
{
- range_seg_t *rs, rsearch;
- avl_index_t where;
+ range_seg_t *rs;
+ range_seg_max_t rsearch;
- rsearch.rs_start = start;
- rsearch.rs_end = start + size;
+ rs_set_start(&rsearch, rt, start);
+ rs_set_end(&rsearch, rt, start + size);
- rs = avl_find(t, &rsearch, &where);
+ rs = zfs_btree_find(t, &rsearch, where);
if (rs == NULL) {
- rs = avl_nearest(t, where, AVL_AFTER);
+ rs = zfs_btree_next(t, where, where);
}
return (rs);
@@ -1337,27 +1571,34 @@ metaslab_block_find(avl_tree_t *t, uint64_t start, uint64_t size)
#if defined(WITH_DF_BLOCK_ALLOCATOR) || \
defined(WITH_CF_BLOCK_ALLOCATOR)
/*
- * This is a helper function that can be used by the allocator to find
- * a suitable block to allocate. This will search the specified AVL
- * tree looking for a block that matches the specified criteria.
+ * This is a helper function that can be used by the allocator to find a
+ * suitable block to allocate. This will search the specified B-tree looking
+ * for a block that matches the specified criteria.
*/
static uint64_t
-metaslab_block_picker(avl_tree_t *t, uint64_t *cursor, uint64_t size,
+metaslab_block_picker(range_tree_t *rt, uint64_t *cursor, uint64_t size,
uint64_t max_search)
{
- range_seg_t *rs = metaslab_block_find(t, *cursor, size);
+ if (*cursor == 0)
+ *cursor = rt->rt_start;
+ zfs_btree_t *bt = &rt->rt_root;
+ zfs_btree_index_t where;
+ range_seg_t *rs = metaslab_block_find(bt, rt, *cursor, size, &where);
uint64_t first_found;
+ int count_searched = 0;
if (rs != NULL)
- first_found = rs->rs_start;
+ first_found = rs_get_start(rs, rt);
- while (rs != NULL && rs->rs_start - first_found <= max_search) {
- uint64_t offset = rs->rs_start;
- if (offset + size <= rs->rs_end) {
+ while (rs != NULL && (rs_get_start(rs, rt) - first_found <=
+ max_search || count_searched < metaslab_min_search_count)) {
+ uint64_t offset = rs_get_start(rs, rt);
+ if (offset + size <= rs_get_end(rs, rt)) {
*cursor = offset + size;
return (offset);
}
- rs = AVL_NEXT(t, rs);
+ rs = zfs_btree_next(bt, &where, &where);
+ count_searched++;
}
*cursor = 0;
@@ -1403,8 +1644,6 @@ metaslab_df_alloc(metaslab_t *msp, uint64_t size)
uint64_t offset;
ASSERT(MUTEX_HELD(&msp->ms_lock));
- ASSERT3U(avl_numnodes(&rt->rt_root), ==,
- avl_numnodes(&msp->ms_allocatable_by_size));
/*
* If we're running low on space, find a segment based on size,
@@ -1414,22 +1653,33 @@ metaslab_df_alloc(metaslab_t *msp, uint64_t size)
free_pct < metaslab_df_free_pct) {
offset = -1;
} else {
- offset = metaslab_block_picker(&rt->rt_root,
+ offset = metaslab_block_picker(rt,
cursor, size, metaslab_df_max_search);
}
if (offset == -1) {
range_seg_t *rs;
+ if (zfs_btree_numnodes(&msp->ms_allocatable_by_size) == 0)
+ metaslab_size_tree_full_load(msp->ms_allocatable);
if (metaslab_df_use_largest_segment) {
/* use largest free segment */
- rs = avl_last(&msp->ms_allocatable_by_size);
+ rs = zfs_btree_last(&msp->ms_allocatable_by_size, NULL);
} else {
+ zfs_btree_index_t where;
/* use segment of this size, or next largest */
+#ifdef _METASLAB_TRACING
+ metaslab_rt_arg_t *mrap = msp->ms_allocatable->rt_arg;
+ if (size < (1 << mrap->mra_floor_shift)) {
+ METASLABSTAT_BUMP(
+ metaslabstat_df_find_under_floor);
+ }
+#endif
rs = metaslab_block_find(&msp->ms_allocatable_by_size,
- 0, size);
+ rt, msp->ms_start, size, &where);
}
- if (rs != NULL && rs->rs_start + size <= rs->rs_end) {
- offset = rs->rs_start;
+ if (rs != NULL && rs_get_start(rs, rt) + size <= rs_get_end(rs,
+ rt)) {
+ offset = rs_get_start(rs, rt);
*cursor = offset + size;
}
}
@@ -1458,25 +1708,27 @@ static uint64_t
metaslab_cf_alloc(metaslab_t *msp, uint64_t size)
{
range_tree_t *rt = msp->ms_allocatable;
- avl_tree_t *t = &msp->ms_allocatable_by_size;
+ zfs_btree_t *t = &msp->ms_allocatable_by_size;
uint64_t *cursor = &msp->ms_lbas[0];
uint64_t *cursor_end = &msp->ms_lbas[1];
uint64_t offset = 0;
ASSERT(MUTEX_HELD(&msp->ms_lock));
- ASSERT3U(avl_numnodes(t), ==, avl_numnodes(&rt->rt_root));
ASSERT3U(*cursor_end, >=, *cursor);
if ((*cursor + size) > *cursor_end) {
range_seg_t *rs;
- rs = avl_last(&msp->ms_allocatable_by_size);
- if (rs == NULL || (rs->rs_end - rs->rs_start) < size)
+ if (zfs_btree_numnodes(t) == 0)
+ metaslab_size_tree_full_load(msp->ms_allocatable);
+ rs = zfs_btree_last(t, NULL);
+ if (rs == NULL || (rs_get_end(rs, rt) - rs_get_start(rs, rt)) <
+ size)
return (-1ULL);
- *cursor = rs->rs_start;
- *cursor_end = rs->rs_end;
+ *cursor = rs_get_start(rs, rt);
+ *cursor_end = rs_get_end(rs, rt);
}
offset = *cursor;
@@ -1511,39 +1763,40 @@ uint64_t metaslab_ndf_clump_shift = 4;
static uint64_t
metaslab_ndf_alloc(metaslab_t *msp, uint64_t size)
{
- avl_tree_t *t = &msp->ms_allocatable->rt_root;
- avl_index_t where;
- range_seg_t *rs, rsearch;
+ zfs_btree_t *t = &msp->ms_allocatable->rt_root;
+ range_tree_t *rt = msp->ms_allocatable;
+ zfs_btree_index_t where;
+ range_seg_t *rs;
+ range_seg_max_t rsearch;
uint64_t hbit = highbit64(size);
uint64_t *cursor = &msp->ms_lbas[hbit - 1];
uint64_t max_size = metaslab_largest_allocatable(msp);
ASSERT(MUTEX_HELD(&msp->ms_lock));
- ASSERT3U(avl_numnodes(t), ==,
- avl_numnodes(&msp->ms_allocatable_by_size));
if (max_size < size)
return (-1ULL);
- rsearch.rs_start = *cursor;
- rsearch.rs_end = *cursor + size;
+ rs_set_start(&rsearch, rt, *cursor);
+ rs_set_end(&rsearch, rt, *cursor + size);
- rs = avl_find(t, &rsearch, &where);
- if (rs == NULL || (rs->rs_end - rs->rs_start) < size) {
+ rs = zfs_btree_find(t, &rsearch, &where);
+ if (rs == NULL || (rs_get_end(rs, rt) - rs_get_start(rs, rt)) < size) {
t = &msp->ms_allocatable_by_size;
- rsearch.rs_start = 0;
- rsearch.rs_end = MIN(max_size,
- 1ULL << (hbit + metaslab_ndf_clump_shift));
- rs = avl_find(t, &rsearch, &where);
+ rs_set_start(&rsearch, rt, 0);
+ rs_set_end(&rsearch, rt, MIN(max_size, 1ULL << (hbit +
+ metaslab_ndf_clump_shift)));
+
+ rs = zfs_btree_find(t, &rsearch, &where);
if (rs == NULL)
- rs = avl_nearest(t, where, AVL_AFTER);
+ rs = zfs_btree_next(t, &where, &where);
ASSERT(rs != NULL);
}
- if ((rs->rs_end - rs->rs_start) >= size) {
- *cursor = rs->rs_start + size;
- return (rs->rs_start);
+ if ((rs_get_end(rs, rt) - rs_get_start(rs, rt)) >= size) {
+ *cursor = rs_get_start(rs, rt) + size;
+ return (rs_get_start(rs, rt));
}
return (-1ULL);
}
@@ -1889,9 +2142,8 @@ metaslab_potentially_evict(metaslab_class_t *mc)
{
#ifdef _KERNEL
uint64_t allmem = arc_all_memory();
- extern kmem_cache_t *range_seg_cache;
- uint64_t inuse = range_seg_cache->skc_obj_total;
- uint64_t size = range_seg_cache->skc_obj_size;
+ uint64_t inuse = zfs_btree_leaf_cache->skc_obj_total;
+ uint64_t size = zfs_btree_leaf_cache->skc_obj_size;
int tries = 0;
for (; allmem * zfs_metaslab_mem_limit / 100 < inuse * size &&
tries < multilist_get_num_sublists(mc->mc_metaslab_txg_list) * 2;
@@ -1928,7 +2180,7 @@ metaslab_potentially_evict(metaslab_class_t *mc)
*/
if (msp->ms_loading) {
msp = next_msp;
- inuse = range_seg_cache->skc_obj_total;
+ inuse = zfs_btree_leaf_cache->skc_obj_total;
continue;
}
/*
@@ -1950,7 +2202,7 @@ metaslab_potentially_evict(metaslab_class_t *mc)
}
mutex_exit(&msp->ms_lock);
msp = next_msp;
- inuse = range_seg_cache->skc_obj_total;
+ inuse = zfs_btree_leaf_cache->skc_obj_total;
}
}
#endif
@@ -1993,11 +2245,40 @@ metaslab_load_impl(metaslab_t *msp)
mutex_exit(&msp->ms_lock);
hrtime_t load_start = gethrtime();
+ metaslab_rt_arg_t *mrap;
+ if (msp->ms_allocatable->rt_arg == NULL) {
+ mrap = kmem_zalloc(sizeof (*mrap), KM_SLEEP);
+ } else {
+ mrap = msp->ms_allocatable->rt_arg;
+ msp->ms_allocatable->rt_ops = NULL;
+ msp->ms_allocatable->rt_arg = NULL;
+ }
+ mrap->mra_bt = &msp->ms_allocatable_by_size;
+ mrap->mra_floor_shift = metaslab_by_size_min_shift;
+
if (msp->ms_sm != NULL) {
error = space_map_load_length(msp->ms_sm, msp->ms_allocatable,
SM_FREE, length);
+
+ /* Now, populate the size-sorted tree. */
+ metaslab_rt_create(msp->ms_allocatable, mrap);
+ msp->ms_allocatable->rt_ops = &metaslab_rt_ops;
+ msp->ms_allocatable->rt_arg = mrap;
+
+ struct mssa_arg arg = {0};
+ arg.rt = msp->ms_allocatable;
+ arg.mra = mrap;
+ range_tree_walk(msp->ms_allocatable, metaslab_size_sorted_add,
+ &arg);
} else {
/*
+ * Add the size-sorted tree first, since we don't need to load
+ * the metaslab from the spacemap.
+ */
+ metaslab_rt_create(msp->ms_allocatable, mrap);
+ msp->ms_allocatable->rt_ops = &metaslab_rt_ops;
+ msp->ms_allocatable->rt_arg = mrap;
+ /*
* The space map has not been allocated yet, so treat
* all the space in the metaslab as free and add it to the
* ms_allocatable tree.
@@ -2252,6 +2533,29 @@ metaslab_unload(metaslab_t *msp)
metaslab_recalculate_weight_and_sort(msp);
}
+/*
+ * We want to optimize the memory use of the per-metaslab range
+ * trees. To do this, we store the segments in the range trees in
+ * units of sectors, zero-indexing from the start of the metaslab. If
+ * the vdev_ms_shift - the vdev_ashift is less than 32, we can store
+ * the ranges using two uint32_ts, rather than two uint64_ts.
+ */
+static range_seg_type_t
+metaslab_calculate_range_tree_type(vdev_t *vdev, metaslab_t *msp,
+ uint64_t *start, uint64_t *shift)
+{
+ if (vdev->vdev_ms_shift - vdev->vdev_ashift < 32 &&
+ !zfs_metaslab_force_large_segs) {
+ *shift = vdev->vdev_ashift;
+ *start = msp->ms_start;
+ return (RANGE_SEG32);
+ } else {
+ *shift = 0;
+ *start = 0;
+ return (RANGE_SEG64);
+ }
+}
+
void
metaslab_set_selected_txg(metaslab_t *msp, uint64_t txg)
{
@@ -2327,6 +2631,10 @@ metaslab_init(metaslab_group_t *mg, uint64_t id, uint64_t object,
ms->ms_allocated_space = space_map_allocated(ms->ms_sm);
}
+ range_seg_type_t type;
+ uint64_t shift, start;
+ type = metaslab_calculate_range_tree_type(vd, ms, &start, &shift);
+
/*
* We create the ms_allocatable here, but we don't create the
* other range trees until metaslab_sync_done(). This serves
@@ -2335,10 +2643,9 @@ metaslab_init(metaslab_group_t *mg, uint64_t id, uint64_t object,
* we'd data fault on any attempt to use this metaslab before
* it's ready.
*/
- ms->ms_allocatable = range_tree_create_impl(&rt_avl_ops,
- &ms->ms_allocatable_by_size, metaslab_rangesize_compare, 0);
+ ms->ms_allocatable = range_tree_create(NULL, type, NULL, start, shift);
- ms->ms_trim = range_tree_create(NULL, NULL);
+ ms->ms_trim = range_tree_create(NULL, type, NULL, start, shift);
metaslab_group_add(mg, ms);
metaslab_set_fragmentation(ms, B_FALSE);
@@ -2393,7 +2700,7 @@ metaslab_unflushed_changes_memused(metaslab_t *ms)
{
return ((range_tree_numsegs(ms->ms_unflushed_allocs) +
range_tree_numsegs(ms->ms_unflushed_frees)) *
- sizeof (range_seg_t));
+ ms->ms_unflushed_allocs->rt_root.bt_elem_size);
}
void
@@ -3187,7 +3494,7 @@ metaslab_should_condense(metaslab_t *msp)
* We always condense metaslabs that are empty and metaslabs for
* which a condense request has been made.
*/
- if (avl_is_empty(&msp->ms_allocatable_by_size) ||
+ if (range_tree_numsegs(msp->ms_allocatable) == 0 ||
msp->ms_condense_wanted)
return (B_TRUE);
@@ -3233,28 +3540,29 @@ metaslab_condense(metaslab_t *msp, dmu_tx_t *tx)
* So to truncate the space map to represent all the entries of
* previous TXGs we do the following:
*
- * 1] We create a range tree (condense tree) that is 100% allocated.
- * 2] We remove from it all segments found in the ms_defer trees
+ * 1] We create a range tree (condense tree) that is 100% empty.
+ * 2] We add to it all segments found in the ms_defer trees
* as those segments are marked as free in the original space
* map. We do the same with the ms_allocating trees for the same
- * reason. Removing these segments should be a relatively
+ * reason. Adding these segments should be a relatively
* inexpensive operation since we expect these trees to have a
* small number of nodes.
- * 3] We vacate any unflushed allocs as they should already exist
- * in the condense tree. Then we vacate any unflushed frees as
- * they should already be part of ms_allocatable.
- * 4] At this point, we would ideally like to remove all segments
+ * 3] We vacate any unflushed allocs, since they are not frees we
+ * need to add to the condense tree. Then we vacate any
+ * unflushed frees as they should already be part of ms_allocatable.
+ * 4] At this point, we would ideally like to add all segments
* in the ms_allocatable tree from the condense tree. This way
* we would write all the entries of the condense tree as the
- * condensed space map, which would only contain allocated
- * segments with everything else assumed to be freed.
+ * condensed space map, which would only contain freeed
+ * segments with everything else assumed to be allocated.
*
* Doing so can be prohibitively expensive as ms_allocatable can
- * be large, and therefore computationally expensive to subtract
- * from the condense_tree. Instead we first sync out the
- * condense_tree and then the ms_allocatable, in the condensed
- * space map. While this is not optimal, it is typically close to
- * optimal and more importantly much cheaper to compute.
+ * be large, and therefore computationally expensive to add to
+ * the condense_tree. Instead we first sync out an entry marking
+ * everything as allocated, then the condense_tree and then the
+ * ms_allocatable, in the condensed space map. While this is not
+ * optimal, it is typically close to optimal and more importantly
+ * much cheaper to compute.
*
* 5] Finally, as both of the unflushed trees were written to our
* new and condensed metaslab space map, we basically flushed
@@ -3268,22 +3576,26 @@ metaslab_condense(metaslab_t *msp, dmu_tx_t *tx)
"spa %s, smp size %llu, segments %lu, forcing condense=%s", txg,
msp->ms_id, msp, msp->ms_group->mg_vd->vdev_id,
spa->spa_name, space_map_length(msp->ms_sm),
- avl_numnodes(&msp->ms_allocatable->rt_root),
+ range_tree_numsegs(msp->ms_allocatable),
msp->ms_condense_wanted ? "TRUE" : "FALSE");
msp->ms_condense_wanted = B_FALSE;
- condense_tree = range_tree_create(NULL, NULL);
- range_tree_add(condense_tree, msp->ms_start, msp->ms_size);
+ range_seg_type_t type;
+ uint64_t shift, start;
+ type = metaslab_calculate_range_tree_type(msp->ms_group->mg_vd, msp,
+ &start, &shift);
+
+ condense_tree = range_tree_create(NULL, type, NULL, start, shift);
for (int t = 0; t < TXG_DEFER_SIZE; t++) {
range_tree_walk(msp->ms_defer[t],
- range_tree_remove, condense_tree);
+ range_tree_add, condense_tree);
}
for (int t = 0; t < TXG_CONCURRENT_STATES; t++) {
range_tree_walk(msp->ms_allocating[(txg + t) & TXG_MASK],
- range_tree_remove, condense_tree);
+ range_tree_add, condense_tree);
}
ASSERT3U(spa->spa_unflushed_stats.sus_memused, >=,
@@ -3331,11 +3643,17 @@ metaslab_condense(metaslab_t *msp, dmu_tx_t *tx)
* followed by FREES (due to space_map_write() in metaslab_sync()) for
* sync pass 1.
*/
- space_map_write(sm, condense_tree, SM_ALLOC, SM_NO_VDEVID, tx);
+ range_tree_t *tmp_tree = range_tree_create(NULL, type, NULL, start,
+ shift);
+ range_tree_add(tmp_tree, msp->ms_start, msp->ms_size);
+ space_map_write(sm, tmp_tree, SM_ALLOC, SM_NO_VDEVID, tx);
space_map_write(sm, msp->ms_allocatable, SM_FREE, SM_NO_VDEVID, tx);
+ space_map_write(sm, condense_tree, SM_FREE, SM_NO_VDEVID, tx);
range_tree_vacate(condense_tree, NULL, NULL);
range_tree_destroy(condense_tree);
+ range_tree_vacate(tmp_tree, NULL, NULL);
+ range_tree_destroy(tmp_tree);
mutex_enter(&msp->ms_lock);
msp->ms_condensing = B_FALSE;
@@ -3578,7 +3896,7 @@ metaslab_sync(metaslab_t *msp, uint64_t txg)
return;
- VERIFY(txg <= spa_final_dirty_txg(spa));
+ VERIFY3U(txg, <=, spa_final_dirty_txg(spa));
/*
* The only state that can actually be changing concurrently
@@ -3867,32 +4185,46 @@ metaslab_sync_done(metaslab_t *msp, uint64_t txg)
* range trees and add its capacity to the vdev.
*/
if (msp->ms_freed == NULL) {
+ range_seg_type_t type;
+ uint64_t shift, start;
+ type = metaslab_calculate_range_tree_type(vd, msp, &start,
+ &shift);
+
for (int t = 0; t < TXG_SIZE; t++) {
ASSERT(msp->ms_allocating[t] == NULL);
- msp->ms_allocating[t] = range_tree_create(NULL, NULL);
+ msp->ms_allocating[t] = range_tree_create(NULL, type,
+ NULL, start, shift);
}
ASSERT3P(msp->ms_freeing, ==, NULL);
- msp->ms_freeing = range_tree_create(NULL, NULL);
+ msp->ms_freeing = range_tree_create(NULL, type, NULL, start,
+ shift);
ASSERT3P(msp->ms_freed, ==, NULL);
- msp->ms_freed = range_tree_create(NULL, NULL);
+ msp->ms_freed = range_tree_create(NULL, type, NULL, start,
+ shift);
for (int t = 0; t < TXG_DEFER_SIZE; t++) {
ASSERT3P(msp->ms_defer[t], ==, NULL);
- msp->ms_defer[t] = range_tree_create(NULL, NULL);
+ msp->ms_defer[t] = range_tree_create(NULL, type, NULL,
+ start, shift);
}
ASSERT3P(msp->ms_checkpointing, ==, NULL);
- msp->ms_checkpointing = range_tree_create(NULL, NULL);
+ msp->ms_checkpointing = range_tree_create(NULL, type, NULL,
+ start, shift);
ASSERT3P(msp->ms_unflushed_allocs, ==, NULL);
- msp->ms_unflushed_allocs = range_tree_create(NULL, NULL);
+ msp->ms_unflushed_allocs = range_tree_create(NULL, type, NULL,
+ start, shift);
+
+ metaslab_rt_arg_t *mrap = kmem_zalloc(sizeof (*mrap), KM_SLEEP);
+ mrap->mra_bt = &msp->ms_unflushed_frees_by_size;
+ mrap->mra_floor_shift = metaslab_by_size_min_shift;
ASSERT3P(msp->ms_unflushed_frees, ==, NULL);
- msp->ms_unflushed_frees = range_tree_create_impl(&rt_avl_ops,
- &msp->ms_unflushed_frees_by_size,
- metaslab_rangesize_compare, 0);
+ msp->ms_unflushed_frees = range_tree_create(&metaslab_rt_ops,
+ type, mrap, start, shift);
metaslab_space_update(vd, mg->mg_class, 0, 0, msp->ms_size);
}
@@ -4052,36 +4384,6 @@ metaslab_is_unique(metaslab_t *msp, dva_t *dva)
* ==========================================================================
*/
#ifdef _METASLAB_TRACING
-kstat_t *metaslab_trace_ksp;
-kstat_named_t metaslab_trace_over_limit;
-
-void
-metaslab_alloc_trace_init(void)
-{
- ASSERT(metaslab_alloc_trace_cache == NULL);
- metaslab_alloc_trace_cache = kmem_cache_create(
- "metaslab_alloc_trace_cache", sizeof (metaslab_alloc_trace_t),
- 0, NULL, NULL, NULL, NULL, NULL, 0);
- metaslab_trace_ksp = kstat_create("zfs", 0, "metaslab_trace_stats",
- "misc", KSTAT_TYPE_NAMED, 1, KSTAT_FLAG_VIRTUAL);
- if (metaslab_trace_ksp != NULL) {
- metaslab_trace_ksp->ks_data = &metaslab_trace_over_limit;
- kstat_named_init(&metaslab_trace_over_limit,
- "metaslab_trace_over_limit", KSTAT_DATA_UINT64);
- kstat_install(metaslab_trace_ksp);
- }
-}
-
-void
-metaslab_alloc_trace_fini(void)
-{
- if (metaslab_trace_ksp != NULL) {
- kstat_delete(metaslab_trace_ksp);
- metaslab_trace_ksp = NULL;
- }
- kmem_cache_destroy(metaslab_alloc_trace_cache);
- metaslab_alloc_trace_cache = NULL;
-}
/*
* Add an allocation trace element to the allocation tracing list.
@@ -4108,7 +4410,7 @@ metaslab_trace_add(zio_alloc_list_t *zal, metaslab_group_t *mg,
#ifdef DEBUG
panic("too many entries in allocation list");
#endif
- atomic_inc_64(&metaslab_trace_over_limit.value.ui64);
+ METASLABSTAT_BUMP(metaslabstat_trace_over_limit);
zal->zal_size--;
mat_next = list_next(&zal->zal_list, list_head(&zal->zal_list));
list_remove(&zal->zal_list, mat_next);
@@ -4161,16 +4463,6 @@ metaslab_trace_fini(zio_alloc_list_t *zal)
#define metaslab_trace_add(zal, mg, msp, psize, id, off, alloc)
void
-metaslab_alloc_trace_init(void)
-{
-}
-
-void
-metaslab_alloc_trace_fini(void)
-{
-}
-
-void
metaslab_trace_init(zio_alloc_list_t *zal)
{
}
diff --git a/module/zfs/range_tree.c b/module/zfs/range_tree.c
index 0e1297214..0b369a438 100644
--- a/module/zfs/range_tree.c
+++ b/module/zfs/range_tree.c
@@ -74,42 +74,38 @@
* support removing complete segments.
*/
-kmem_cache_t *range_seg_cache;
-
-/* Generic ops for managing an AVL tree alongside a range tree */
-struct range_tree_ops rt_avl_ops = {
- .rtop_create = rt_avl_create,
- .rtop_destroy = rt_avl_destroy,
- .rtop_add = rt_avl_add,
- .rtop_remove = rt_avl_remove,
- .rtop_vacate = rt_avl_vacate,
-};
-
-void
-range_tree_init(void)
-{
- ASSERT(range_seg_cache == NULL);
- range_seg_cache = kmem_cache_create("range_seg_cache",
- sizeof (range_seg_t), 0, NULL, NULL, NULL, NULL, NULL, 0);
-}
-
-void
-range_tree_fini(void)
-{
- kmem_cache_destroy(range_seg_cache);
- range_seg_cache = NULL;
+static inline void
+rs_copy(range_seg_t *src, range_seg_t *dest, range_tree_t *rt)
+{
+ ASSERT3U(rt->rt_type, <=, RANGE_SEG_NUM_TYPES);
+ size_t size = 0;
+ switch (rt->rt_type) {
+ case RANGE_SEG32:
+ size = sizeof (range_seg32_t);
+ break;
+ case RANGE_SEG64:
+ size = sizeof (range_seg64_t);
+ break;
+ case RANGE_SEG_GAP:
+ size = sizeof (range_seg_gap_t);
+ break;
+ default:
+ VERIFY(0);
+ }
+ bcopy(src, dest, size);
}
void
range_tree_stat_verify(range_tree_t *rt)
{
range_seg_t *rs;
+ zfs_btree_index_t where;
uint64_t hist[RANGE_TREE_HISTOGRAM_SIZE] = { 0 };
int i;
- for (rs = avl_first(&rt->rt_root); rs != NULL;
- rs = AVL_NEXT(&rt->rt_root, rs)) {
- uint64_t size = rs->rs_end - rs->rs_start;
+ for (rs = zfs_btree_first(&rt->rt_root, &where); rs != NULL;
+ rs = zfs_btree_next(&rt->rt_root, &where, &where)) {
+ uint64_t size = rs_get_end(rs, rt) - rs_get_start(rs, rt);
int idx = highbit64(size) - 1;
hist[idx]++;
@@ -128,7 +124,7 @@ range_tree_stat_verify(range_tree_t *rt)
static void
range_tree_stat_incr(range_tree_t *rt, range_seg_t *rs)
{
- uint64_t size = rs->rs_end - rs->rs_start;
+ uint64_t size = rs_get_end(rs, rt) - rs_get_start(rs, rt);
int idx = highbit64(size) - 1;
ASSERT(size != 0);
@@ -142,7 +138,7 @@ range_tree_stat_incr(range_tree_t *rt, range_seg_t *rs)
static void
range_tree_stat_decr(range_tree_t *rt, range_seg_t *rs)
{
- uint64_t size = rs->rs_end - rs->rs_start;
+ uint64_t size = rs_get_end(rs, rt) - rs_get_start(rs, rt);
int idx = highbit64(size) - 1;
ASSERT(size != 0);
@@ -153,14 +149,35 @@ range_tree_stat_decr(range_tree_t *rt, range_seg_t *rs)
rt->rt_histogram[idx]--;
}
-/*
- * NOTE: caller is responsible for all locking.
- */
static int
-range_tree_seg_compare(const void *x1, const void *x2)
+range_tree_seg32_compare(const void *x1, const void *x2)
+{
+ const range_seg32_t *r1 = x1;
+ const range_seg32_t *r2 = x2;
+
+ ASSERT3U(r1->rs_start, <=, r1->rs_end);
+ ASSERT3U(r2->rs_start, <=, r2->rs_end);
+
+ return ((r1->rs_start >= r2->rs_end) - (r1->rs_end <= r2->rs_start));
+}
+
+static int
+range_tree_seg64_compare(const void *x1, const void *x2)
{
- const range_seg_t *r1 = (const range_seg_t *)x1;
- const range_seg_t *r2 = (const range_seg_t *)x2;
+ const range_seg64_t *r1 = x1;
+ const range_seg64_t *r2 = x2;
+
+ ASSERT3U(r1->rs_start, <=, r1->rs_end);
+ ASSERT3U(r2->rs_start, <=, r2->rs_end);
+
+ return ((r1->rs_start >= r2->rs_end) - (r1->rs_end <= r2->rs_start));
+}
+
+static int
+range_tree_seg_gap_compare(const void *x1, const void *x2)
+{
+ const range_seg_gap_t *r1 = x1;
+ const range_seg_gap_t *r2 = x2;
ASSERT3U(r1->rs_start, <=, r1->rs_end);
ASSERT3U(r2->rs_start, <=, r2->rs_end);
@@ -169,18 +186,42 @@ range_tree_seg_compare(const void *x1, const void *x2)
}
range_tree_t *
-range_tree_create_impl(range_tree_ops_t *ops, void *arg,
- int (*avl_compare) (const void *, const void *), uint64_t gap)
+range_tree_create_impl(range_tree_ops_t *ops, range_seg_type_t type, void *arg,
+ uint64_t start, uint64_t shift,
+ int (*zfs_btree_compare) (const void *, const void *),
+ uint64_t gap)
{
range_tree_t *rt = kmem_zalloc(sizeof (range_tree_t), KM_SLEEP);
- avl_create(&rt->rt_root, range_tree_seg_compare,
- sizeof (range_seg_t), offsetof(range_seg_t, rs_node));
+ ASSERT3U(shift, <, 64);
+ ASSERT3U(type, <=, RANGE_SEG_NUM_TYPES);
+ size_t size;
+ int (*compare) (const void *, const void *);
+ switch (type) {
+ case RANGE_SEG32:
+ size = sizeof (range_seg32_t);
+ compare = range_tree_seg32_compare;
+ break;
+ case RANGE_SEG64:
+ size = sizeof (range_seg64_t);
+ compare = range_tree_seg64_compare;
+ break;
+ case RANGE_SEG_GAP:
+ size = sizeof (range_seg_gap_t);
+ compare = range_tree_seg_gap_compare;
+ break;
+ default:
+ panic("Invalid range seg type %d", type);
+ }
+ zfs_btree_create(&rt->rt_root, compare, size);
rt->rt_ops = ops;
rt->rt_gap = gap;
rt->rt_arg = arg;
- rt->rt_avl_compare = avl_compare;
+ rt->rt_type = type;
+ rt->rt_start = start;
+ rt->rt_shift = shift;
+ rt->rt_btree_compare = zfs_btree_compare;
if (rt->rt_ops != NULL && rt->rt_ops->rtop_create != NULL)
rt->rt_ops->rtop_create(rt, rt->rt_arg);
@@ -189,9 +230,10 @@ range_tree_create_impl(range_tree_ops_t *ops, void *arg,
}
range_tree_t *
-range_tree_create(range_tree_ops_t *ops, void *arg)
+range_tree_create(range_tree_ops_t *ops, range_seg_type_t type,
+ void *arg, uint64_t start, uint64_t shift)
{
- return (range_tree_create_impl(ops, arg, NULL, 0));
+ return (range_tree_create_impl(ops, type, arg, start, shift, NULL, 0));
}
void
@@ -202,19 +244,20 @@ range_tree_destroy(range_tree_t *rt)
if (rt->rt_ops != NULL && rt->rt_ops->rtop_destroy != NULL)
rt->rt_ops->rtop_destroy(rt, rt->rt_arg);
- avl_destroy(&rt->rt_root);
+ zfs_btree_destroy(&rt->rt_root);
kmem_free(rt, sizeof (*rt));
}
void
range_tree_adjust_fill(range_tree_t *rt, range_seg_t *rs, int64_t delta)
{
- ASSERT3U(rs->rs_fill + delta, !=, 0);
- ASSERT3U(rs->rs_fill + delta, <=, rs->rs_end - rs->rs_start);
+ ASSERT3U(rs_get_fill(rs, rt) + delta, !=, 0);
+ ASSERT3U(rs_get_fill(rs, rt) + delta, <=, rs_get_end(rs, rt) -
+ rs_get_start(rs, rt));
if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);
- rs->rs_fill += delta;
+ rs_set_fill(rs, rt, rs_get_fill(rs, rt) + delta);
if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)
rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);
}
@@ -223,28 +266,20 @@ static void
range_tree_add_impl(void *arg, uint64_t start, uint64_t size, uint64_t fill)
{
range_tree_t *rt = arg;
- avl_index_t where;
- range_seg_t rsearch, *rs_before, *rs_after, *rs;
+ zfs_btree_index_t where;
+ range_seg_t *rs_before, *rs_after, *rs;
+ range_seg_max_t tmp, rsearch;
uint64_t end = start + size, gap = rt->rt_gap;
uint64_t bridge_size = 0;
boolean_t merge_before, merge_after;
ASSERT3U(size, !=, 0);
ASSERT3U(fill, <=, size);
+ ASSERT3U(start + size, >, start);
- rsearch.rs_start = start;
- rsearch.rs_end = end;
- rs = avl_find(&rt->rt_root, &rsearch, &where);
-
- if (gap == 0 && rs != NULL &&
- rs->rs_start <= start && rs->rs_end >= end) {
- zfs_panic_recover("zfs: allocating allocated segment"
- "(offset=%llu size=%llu) of (offset=%llu size=%llu)\n",
- (longlong_t)start, (longlong_t)size,
- (longlong_t)rs->rs_start,
- (longlong_t)rs->rs_end - rs->rs_start);
- return;
- }
+ rs_set_start(&rsearch, rt, start);
+ rs_set_end(&rsearch, rt, end);
+ rs = zfs_btree_find(&rt->rt_root, &rsearch, &where);
/*
* If this is a gap-supporting range tree, it is possible that we
@@ -255,27 +290,28 @@ range_tree_add_impl(void *arg, uint64_t start, uint64_t size, uint64_t fill)
* the normal code paths.
*/
if (rs != NULL) {
+ ASSERT3U(rt->rt_gap, !=, 0);
+ uint64_t rstart = rs_get_start(rs, rt);
+ uint64_t rend = rs_get_end(rs, rt);
ASSERT3U(gap, !=, 0);
- if (rs->rs_start <= start && rs->rs_end >= end) {
+ if (rstart <= start && rend >= end) {
range_tree_adjust_fill(rt, rs, fill);
return;
}
- avl_remove(&rt->rt_root, rs);
+ zfs_btree_remove(&rt->rt_root, rs);
if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);
range_tree_stat_decr(rt, rs);
- rt->rt_space -= rs->rs_end - rs->rs_start;
+ rt->rt_space -= rend - rstart;
- fill += rs->rs_fill;
- start = MIN(start, rs->rs_start);
- end = MAX(end, rs->rs_end);
+ fill += rs_get_fill(rs, rt);
+ start = MIN(start, rstart);
+ end = MAX(end, rend);
size = end - start;
range_tree_add_impl(rt, start, size, fill);
-
- kmem_cache_free(range_seg_cache, rs);
return;
}
@@ -286,19 +322,21 @@ range_tree_add_impl(void *arg, uint64_t start, uint64_t size, uint64_t fill)
* If gap != 0, we might need to merge with our neighbors even if we
* aren't directly touching.
*/
- rs_before = avl_nearest(&rt->rt_root, where, AVL_BEFORE);
- rs_after = avl_nearest(&rt->rt_root, where, AVL_AFTER);
+ zfs_btree_index_t where_before, where_after;
+ rs_before = zfs_btree_prev(&rt->rt_root, &where, &where_before);
+ rs_after = zfs_btree_next(&rt->rt_root, &where, &where_after);
- merge_before = (rs_before != NULL && rs_before->rs_end >= start - gap);
- merge_after = (rs_after != NULL && rs_after->rs_start <= end + gap);
+ merge_before = (rs_before != NULL && rs_get_end(rs_before, rt) >=
+ start - gap);
+ merge_after = (rs_after != NULL && rs_get_start(rs_after, rt) <= end +
+ gap);
if (merge_before && gap != 0)
- bridge_size += start - rs_before->rs_end;
+ bridge_size += start - rs_get_end(rs_before, rt);
if (merge_after && gap != 0)
- bridge_size += rs_after->rs_start - end;
+ bridge_size += rs_get_start(rs_after, rt) - end;
if (merge_before && merge_after) {
- avl_remove(&rt->rt_root, rs_before);
if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL) {
rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg);
rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg);
@@ -307,9 +345,19 @@ range_tree_add_impl(void *arg, uint64_t start, uint64_t size, uint64_t fill)
range_tree_stat_decr(rt, rs_before);
range_tree_stat_decr(rt, rs_after);
- rs_after->rs_fill += rs_before->rs_fill + fill;
- rs_after->rs_start = rs_before->rs_start;
- kmem_cache_free(range_seg_cache, rs_before);
+ rs_copy(rs_after, &tmp, rt);
+ uint64_t before_start = rs_get_start_raw(rs_before, rt);
+ uint64_t before_fill = rs_get_fill(rs_before, rt);
+ uint64_t after_fill = rs_get_fill(rs_after, rt);
+ zfs_btree_remove_from(&rt->rt_root, &where_before);
+
+ /*
+ * We have to re-find the node because our old reference is
+ * invalid as soon as we do any mutating btree operations.
+ */
+ rs_after = zfs_btree_find(&rt->rt_root, &tmp, &where_after);
+ rs_set_start_raw(rs_after, rt, before_start);
+ rs_set_fill(rs_after, rt, after_fill + before_fill + fill);
rs = rs_after;
} else if (merge_before) {
if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
@@ -317,8 +365,9 @@ range_tree_add_impl(void *arg, uint64_t start, uint64_t size, uint64_t fill)
range_tree_stat_decr(rt, rs_before);
- rs_before->rs_fill += fill;
- rs_before->rs_end = end;
+ uint64_t before_fill = rs_get_fill(rs_before, rt);
+ rs_set_end(rs_before, rt, end);
+ rs_set_fill(rs_before, rt, before_fill + fill);
rs = rs_before;
} else if (merge_after) {
if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
@@ -326,22 +375,26 @@ range_tree_add_impl(void *arg, uint64_t start, uint64_t size, uint64_t fill)
range_tree_stat_decr(rt, rs_after);
- rs_after->rs_fill += fill;
- rs_after->rs_start = start;
+ uint64_t after_fill = rs_get_fill(rs_after, rt);
+ rs_set_start(rs_after, rt, start);
+ rs_set_fill(rs_after, rt, after_fill + fill);
rs = rs_after;
} else {
- rs = kmem_cache_alloc(range_seg_cache, KM_SLEEP);
+ rs = &tmp;
- rs->rs_fill = fill;
- rs->rs_start = start;
- rs->rs_end = end;
- avl_insert(&rt->rt_root, rs, where);
+ rs_set_start(rs, rt, start);
+ rs_set_end(rs, rt, end);
+ rs_set_fill(rs, rt, fill);
+ zfs_btree_insert(&rt->rt_root, rs, &where);
}
- if (gap != 0)
- ASSERT3U(rs->rs_fill, <=, rs->rs_end - rs->rs_start);
- else
- ASSERT3U(rs->rs_fill, ==, rs->rs_end - rs->rs_start);
+ if (gap != 0) {
+ ASSERT3U(rs_get_fill(rs, rt), <=, rs_get_end(rs, rt) -
+ rs_get_start(rs, rt));
+ } else {
+ ASSERT3U(rs_get_fill(rs, rt), ==, rs_get_end(rs, rt) -
+ rs_get_start(rs, rt));
+ }
if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)
rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);
@@ -360,22 +413,25 @@ static void
range_tree_remove_impl(range_tree_t *rt, uint64_t start, uint64_t size,
boolean_t do_fill)
{
- avl_index_t where;
- range_seg_t rsearch, *rs, *newseg;
+ zfs_btree_index_t where;
+ range_seg_t *rs;
+ range_seg_max_t rsearch, rs_tmp;
uint64_t end = start + size;
boolean_t left_over, right_over;
VERIFY3U(size, !=, 0);
VERIFY3U(size, <=, rt->rt_space);
+ if (rt->rt_type == RANGE_SEG64)
+ ASSERT3U(start + size, >, start);
- rsearch.rs_start = start;
- rsearch.rs_end = end;
- rs = avl_find(&rt->rt_root, &rsearch, &where);
+ rs_set_start(&rsearch, rt, start);
+ rs_set_end(&rsearch, rt, end);
+ rs = zfs_btree_find(&rt->rt_root, &rsearch, &where);
/* Make sure we completely overlap with someone */
if (rs == NULL) {
- zfs_panic_recover("zfs: freeing free segment "
- "(offset=%llu size=%llu)",
+ zfs_panic_recover("zfs: removing nonexistent segment from "
+ "range tree (offset=%llu size=%llu)",
(longlong_t)start, (longlong_t)size);
return;
}
@@ -388,30 +444,32 @@ range_tree_remove_impl(range_tree_t *rt, uint64_t start, uint64_t size,
*/
if (rt->rt_gap != 0) {
if (do_fill) {
- if (rs->rs_fill == size) {
- start = rs->rs_start;
- end = rs->rs_end;
+ if (rs_get_fill(rs, rt) == size) {
+ start = rs_get_start(rs, rt);
+ end = rs_get_end(rs, rt);
size = end - start;
} else {
range_tree_adjust_fill(rt, rs, -size);
return;
}
- } else if (rs->rs_start != start || rs->rs_end != end) {
+ } else if (rs_get_start(rs, rt) != start ||
+ rs_get_end(rs, rt) != end) {
zfs_panic_recover("zfs: freeing partial segment of "
"gap tree (offset=%llu size=%llu) of "
"(offset=%llu size=%llu)",
(longlong_t)start, (longlong_t)size,
- (longlong_t)rs->rs_start,
- (longlong_t)rs->rs_end - rs->rs_start);
+ (longlong_t)rs_get_start(rs, rt),
+ (longlong_t)rs_get_end(rs, rt) - rs_get_start(rs,
+ rt));
return;
}
}
- VERIFY3U(rs->rs_start, <=, start);
- VERIFY3U(rs->rs_end, >=, end);
+ VERIFY3U(rs_get_start(rs, rt), <=, start);
+ VERIFY3U(rs_get_end(rs, rt), >=, end);
- left_over = (rs->rs_start != start);
- right_over = (rs->rs_end != end);
+ left_over = (rs_get_start(rs, rt) != start);
+ right_over = (rs_get_end(rs, rt) != end);
range_tree_stat_decr(rt, rs);
@@ -419,24 +477,33 @@ range_tree_remove_impl(range_tree_t *rt, uint64_t start, uint64_t size,
rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);
if (left_over && right_over) {
- newseg = kmem_cache_alloc(range_seg_cache, KM_SLEEP);
- newseg->rs_start = end;
- newseg->rs_end = rs->rs_end;
- newseg->rs_fill = newseg->rs_end - newseg->rs_start;
- range_tree_stat_incr(rt, newseg);
+ range_seg_max_t newseg;
+ rs_set_start(&newseg, rt, end);
+ rs_set_end_raw(&newseg, rt, rs_get_end_raw(rs, rt));
+ rs_set_fill(&newseg, rt, rs_get_end(rs, rt) - end);
+ range_tree_stat_incr(rt, &newseg);
- rs->rs_end = start;
+ // This modifies the buffer already inside the range tree
+ rs_set_end(rs, rt, start);
+
+ rs_copy(rs, &rs_tmp, rt);
+ if (zfs_btree_next(&rt->rt_root, &where, &where) != NULL)
+ zfs_btree_insert(&rt->rt_root, &newseg, &where);
+ else
+ zfs_btree_add(&rt->rt_root, &newseg);
- avl_insert_here(&rt->rt_root, newseg, rs, AVL_AFTER);
if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)
- rt->rt_ops->rtop_add(rt, newseg, rt->rt_arg);
+ rt->rt_ops->rtop_add(rt, &newseg, rt->rt_arg);
} else if (left_over) {
- rs->rs_end = start;
+ // This modifies the buffer already inside the range tree
+ rs_set_end(rs, rt, start);
+ rs_copy(rs, &rs_tmp, rt);
} else if (right_over) {
- rs->rs_start = end;
+ // This modifies the buffer already inside the range tree
+ rs_set_start(rs, rt, end);
+ rs_copy(rs, &rs_tmp, rt);
} else {
- avl_remove(&rt->rt_root, rs);
- kmem_cache_free(range_seg_cache, rs);
+ zfs_btree_remove_from(&rt->rt_root, &where);
rs = NULL;
}
@@ -446,11 +513,12 @@ range_tree_remove_impl(range_tree_t *rt, uint64_t start, uint64_t size,
* the size, since we do not support removing partial segments
* of range trees with gaps.
*/
- rs->rs_fill = rs->rs_end - rs->rs_start;
- range_tree_stat_incr(rt, rs);
+ rs_set_fill_raw(rs, rt, rs_get_end_raw(rs, rt) -
+ rs_get_start_raw(rs, rt));
+ range_tree_stat_incr(rt, &rs_tmp);
if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)
- rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);
+ rt->rt_ops->rtop_add(rt, &rs_tmp, rt->rt_arg);
}
rt->rt_space -= size;
@@ -472,14 +540,14 @@ void
range_tree_resize_segment(range_tree_t *rt, range_seg_t *rs,
uint64_t newstart, uint64_t newsize)
{
- int64_t delta = newsize - (rs->rs_end - rs->rs_start);
+ int64_t delta = newsize - (rs_get_end(rs, rt) - rs_get_start(rs, rt));
range_tree_stat_decr(rt, rs);
if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);
- rs->rs_start = newstart;
- rs->rs_end = newstart + newsize;
+ rs_set_start(rs, rt, newstart);
+ rs_set_end(rs, rt, newstart + newsize);
range_tree_stat_incr(rt, rs);
if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)
@@ -491,22 +559,27 @@ range_tree_resize_segment(range_tree_t *rt, range_seg_t *rs,
static range_seg_t *
range_tree_find_impl(range_tree_t *rt, uint64_t start, uint64_t size)
{
- range_seg_t rsearch;
+ range_seg_max_t rsearch;
uint64_t end = start + size;
VERIFY(size != 0);
- rsearch.rs_start = start;
- rsearch.rs_end = end;
- return (avl_find(&rt->rt_root, &rsearch, NULL));
+ rs_set_start(&rsearch, rt, start);
+ rs_set_end(&rsearch, rt, end);
+ return (zfs_btree_find(&rt->rt_root, &rsearch, NULL));
}
range_seg_t *
range_tree_find(range_tree_t *rt, uint64_t start, uint64_t size)
{
+ if (rt->rt_type == RANGE_SEG64)
+ ASSERT3U(start + size, >, start);
+
range_seg_t *rs = range_tree_find_impl(rt, start, size);
- if (rs != NULL && rs->rs_start <= start && rs->rs_end >= start + size)
+ if (rs != NULL && rs_get_start(rs, rt) <= start &&
+ rs_get_end(rs, rt) >= start + size) {
return (rs);
+ }
return (NULL);
}
@@ -533,24 +606,28 @@ boolean_t
range_tree_find_in(range_tree_t *rt, uint64_t start, uint64_t size,
uint64_t *ostart, uint64_t *osize)
{
- range_seg_t rsearch;
- rsearch.rs_start = start;
- rsearch.rs_end = start + 1;
+ if (rt->rt_type == RANGE_SEG64)
+ ASSERT3U(start + size, >, start);
- avl_index_t where;
- range_seg_t *rs = avl_find(&rt->rt_root, &rsearch, &where);
+ range_seg_max_t rsearch;
+ rs_set_start(&rsearch, rt, start);
+ rs_set_end_raw(&rsearch, rt, rs_get_start_raw(&rsearch, rt) + 1);
+
+ zfs_btree_index_t where;
+ range_seg_t *rs = zfs_btree_find(&rt->rt_root, &rsearch, &where);
if (rs != NULL) {
*ostart = start;
- *osize = MIN(size, rs->rs_end - start);
+ *osize = MIN(size, rs_get_end(rs, rt) - start);
return (B_TRUE);
}
- rs = avl_nearest(&rt->rt_root, where, AVL_AFTER);
- if (rs == NULL || rs->rs_start > start + size)
+ rs = zfs_btree_next(&rt->rt_root, &where, &where);
+ if (rs == NULL || rs_get_start(rs, rt) > start + size)
return (B_FALSE);
- *ostart = rs->rs_start;
- *osize = MIN(start + size, rs->rs_end) - rs->rs_start;
+ *ostart = rs_get_start(rs, rt);
+ *osize = MIN(start + size, rs_get_end(rs, rt)) -
+ rs_get_start(rs, rt);
return (B_TRUE);
}
@@ -566,9 +643,12 @@ range_tree_clear(range_tree_t *rt, uint64_t start, uint64_t size)
if (size == 0)
return;
+ if (rt->rt_type == RANGE_SEG64)
+ ASSERT3U(start + size, >, start);
+
while ((rs = range_tree_find_impl(rt, start, size)) != NULL) {
- uint64_t free_start = MAX(rs->rs_start, start);
- uint64_t free_end = MIN(rs->rs_end, start + size);
+ uint64_t free_start = MAX(rs_get_start(rs, rt), start);
+ uint64_t free_end = MIN(rs_get_end(rs, rt), start + size);
range_tree_remove(rt, free_start, free_end - free_start);
}
}
@@ -579,7 +659,7 @@ range_tree_swap(range_tree_t **rtsrc, range_tree_t **rtdst)
range_tree_t *rt;
ASSERT0(range_tree_space(*rtdst));
- ASSERT0(avl_numnodes(&(*rtdst)->rt_root));
+ ASSERT0(zfs_btree_numnodes(&(*rtdst)->rt_root));
rt = *rtsrc;
*rtsrc = *rtdst;
@@ -589,16 +669,20 @@ range_tree_swap(range_tree_t **rtsrc, range_tree_t **rtdst)
void
range_tree_vacate(range_tree_t *rt, range_tree_func_t *func, void *arg)
{
- range_seg_t *rs;
- void *cookie = NULL;
-
if (rt->rt_ops != NULL && rt->rt_ops->rtop_vacate != NULL)
rt->rt_ops->rtop_vacate(rt, rt->rt_arg);
- while ((rs = avl_destroy_nodes(&rt->rt_root, &cookie)) != NULL) {
- if (func != NULL)
- func(arg, rs->rs_start, rs->rs_end - rs->rs_start);
- kmem_cache_free(range_seg_cache, rs);
+ if (func != NULL) {
+ range_seg_t *rs;
+ zfs_btree_index_t *cookie = NULL;
+
+ while ((rs = zfs_btree_destroy_nodes(&rt->rt_root, &cookie)) !=
+ NULL) {
+ func(arg, rs_get_start(rs, rt), rs_get_end(rs, rt) -
+ rs_get_start(rs, rt));
+ }
+ } else {
+ zfs_btree_clear(&rt->rt_root);
}
bzero(rt->rt_histogram, sizeof (rt->rt_histogram));
@@ -608,16 +692,18 @@ range_tree_vacate(range_tree_t *rt, range_tree_func_t *func, void *arg)
void
range_tree_walk(range_tree_t *rt, range_tree_func_t *func, void *arg)
{
- for (range_seg_t *rs = avl_first(&rt->rt_root); rs;
- rs = AVL_NEXT(&rt->rt_root, rs)) {
- func(arg, rs->rs_start, rs->rs_end - rs->rs_start);
+ zfs_btree_index_t where;
+ for (range_seg_t *rs = zfs_btree_first(&rt->rt_root, &where);
+ rs != NULL; rs = zfs_btree_next(&rt->rt_root, &where, &where)) {
+ func(arg, rs_get_start(rs, rt), rs_get_end(rs, rt) -
+ rs_get_start(rs, rt));
}
}
range_seg_t *
range_tree_first(range_tree_t *rt)
{
- return (avl_first(&rt->rt_root));
+ return (zfs_btree_first(&rt->rt_root, NULL));
}
uint64_t
@@ -629,7 +715,7 @@ range_tree_space(range_tree_t *rt)
uint64_t
range_tree_numsegs(range_tree_t *rt)
{
- return ((rt == NULL) ? 0 : avl_numnodes(&rt->rt_root));
+ return ((rt == NULL) ? 0 : zfs_btree_numnodes(&rt->rt_root));
}
boolean_t
@@ -639,71 +725,76 @@ range_tree_is_empty(range_tree_t *rt)
return (range_tree_space(rt) == 0);
}
-/* Generic range tree functions for maintaining segments in an AVL tree. */
+/* ARGSUSED */
void
-rt_avl_create(range_tree_t *rt, void *arg)
-{
- avl_tree_t *tree = arg;
-
- avl_create(tree, rt->rt_avl_compare, sizeof (range_seg_t),
- offsetof(range_seg_t, rs_pp_node));
+rt_btree_create(range_tree_t *rt, void *arg)
+{
+ zfs_btree_t *size_tree = arg;
+
+ size_t size;
+ switch (rt->rt_type) {
+ case RANGE_SEG32:
+ size = sizeof (range_seg32_t);
+ break;
+ case RANGE_SEG64:
+ size = sizeof (range_seg64_t);
+ break;
+ case RANGE_SEG_GAP:
+ size = sizeof (range_seg_gap_t);
+ break;
+ default:
+ panic("Invalid range seg type %d", rt->rt_type);
+ }
+ zfs_btree_create(size_tree, rt->rt_btree_compare, size);
}
+/* ARGSUSED */
void
-rt_avl_destroy(range_tree_t *rt, void *arg)
+rt_btree_destroy(range_tree_t *rt, void *arg)
{
- avl_tree_t *tree = arg;
+ zfs_btree_t *size_tree = arg;
+ ASSERT0(zfs_btree_numnodes(size_tree));
- ASSERT0(avl_numnodes(tree));
- avl_destroy(tree);
+ zfs_btree_destroy(size_tree);
}
+/* ARGSUSED */
void
-rt_avl_add(range_tree_t *rt, range_seg_t *rs, void *arg)
+rt_btree_add(range_tree_t *rt, range_seg_t *rs, void *arg)
{
- avl_tree_t *tree = arg;
- avl_add(tree, rs);
-}
+ zfs_btree_t *size_tree = arg;
-void
-rt_avl_remove(range_tree_t *rt, range_seg_t *rs, void *arg)
-{
- avl_tree_t *tree = arg;
- avl_remove(tree, rs);
+ zfs_btree_add(size_tree, rs);
}
+/* ARGSUSED */
void
-rt_avl_vacate(range_tree_t *rt, void *arg)
+rt_btree_remove(range_tree_t *rt, range_seg_t *rs, void *arg)
{
- /*
- * Normally one would walk the tree freeing nodes along the way.
- * Since the nodes are shared with the range trees we can avoid
- * walking all nodes and just reinitialize the avl tree. The nodes
- * will be freed by the range tree, so we don't want to free them here.
- */
- rt_avl_create(rt, arg);
-}
+ zfs_btree_t *size_tree = arg;
-uint64_t
-range_tree_min(range_tree_t *rt)
-{
- range_seg_t *rs = avl_first(&rt->rt_root);
- return (rs != NULL ? rs->rs_start : 0);
+ zfs_btree_remove(size_tree, rs);
}
-uint64_t
-range_tree_max(range_tree_t *rt)
+/* ARGSUSED */
+void
+rt_btree_vacate(range_tree_t *rt, void *arg)
{
- range_seg_t *rs = avl_last(&rt->rt_root);
- return (rs != NULL ? rs->rs_end : 0);
-}
+ zfs_btree_t *size_tree = arg;
+ zfs_btree_clear(size_tree);
+ zfs_btree_destroy(size_tree);
-uint64_t
-range_tree_span(range_tree_t *rt)
-{
- return (range_tree_max(rt) - range_tree_min(rt));
+ rt_btree_create(rt, arg);
}
+range_tree_ops_t rt_btree_ops = {
+ .rtop_create = rt_btree_create,
+ .rtop_destroy = rt_btree_destroy,
+ .rtop_add = rt_btree_add,
+ .rtop_remove = rt_btree_remove,
+ .rtop_vacate = rt_btree_vacate
+};
+
/*
* Remove any overlapping ranges between the given segment [start, end)
* from removefrom. Add non-overlapping leftovers to addto.
@@ -712,42 +803,62 @@ void
range_tree_remove_xor_add_segment(uint64_t start, uint64_t end,
range_tree_t *removefrom, range_tree_t *addto)
{
- avl_index_t where;
- range_seg_t starting_rs = {
- .rs_start = start,
- .rs_end = start + 1
- };
+ zfs_btree_index_t where;
+ range_seg_max_t starting_rs;
+ rs_set_start(&starting_rs, removefrom, start);
+ rs_set_end_raw(&starting_rs, removefrom, rs_get_start_raw(&starting_rs,
+ removefrom) + 1);
- range_seg_t *curr = avl_find(&removefrom->rt_root,
+ range_seg_t *curr = zfs_btree_find(&removefrom->rt_root,
&starting_rs, &where);
if (curr == NULL)
- curr = avl_nearest(&removefrom->rt_root, where, AVL_AFTER);
+ curr = zfs_btree_next(&removefrom->rt_root, &where, &where);
range_seg_t *next;
for (; curr != NULL; curr = next) {
- next = AVL_NEXT(&removefrom->rt_root, curr);
-
if (start == end)
return;
VERIFY3U(start, <, end);
/* there is no overlap */
- if (end <= curr->rs_start) {
+ if (end <= rs_get_start(curr, removefrom)) {
range_tree_add(addto, start, end - start);
return;
}
- uint64_t overlap_start = MAX(curr->rs_start, start);
- uint64_t overlap_end = MIN(curr->rs_end, end);
+ uint64_t overlap_start = MAX(rs_get_start(curr, removefrom),
+ start);
+ uint64_t overlap_end = MIN(rs_get_end(curr, removefrom),
+ end);
uint64_t overlap_size = overlap_end - overlap_start;
ASSERT3S(overlap_size, >, 0);
+ range_seg_max_t rs;
+ rs_copy(curr, &rs, removefrom);
+
range_tree_remove(removefrom, overlap_start, overlap_size);
if (start < overlap_start)
range_tree_add(addto, start, overlap_start - start);
start = overlap_end;
+ next = zfs_btree_find(&removefrom->rt_root, &rs, &where);
+ /*
+ * If we find something here, we only removed part of the
+ * curr segment. Either there's some left at the end
+ * because we've reached the end of the range we're removing,
+ * or there's some left at the start because we started
+ * partway through the range. Either way, we continue with
+ * the loop. If it's the former, we'll return at the start of
+ * the loop, and if it's the latter we'll see if there is more
+ * area to process.
+ */
+ if (next != NULL) {
+ ASSERT(start == end || start == rs_get_end(&rs,
+ removefrom));
+ }
+
+ next = zfs_btree_next(&removefrom->rt_root, &where, &where);
}
VERIFY3P(curr, ==, NULL);
@@ -767,9 +878,30 @@ void
range_tree_remove_xor_add(range_tree_t *rt, range_tree_t *removefrom,
range_tree_t *addto)
{
- for (range_seg_t *rs = avl_first(&rt->rt_root); rs;
- rs = AVL_NEXT(&rt->rt_root, rs)) {
- range_tree_remove_xor_add_segment(rs->rs_start, rs->rs_end,
- removefrom, addto);
+ zfs_btree_index_t where;
+ for (range_seg_t *rs = zfs_btree_first(&rt->rt_root, &where); rs;
+ rs = zfs_btree_next(&rt->rt_root, &where, &where)) {
+ range_tree_remove_xor_add_segment(rs_get_start(rs, rt),
+ rs_get_end(rs, rt), removefrom, addto);
}
}
+
+uint64_t
+range_tree_min(range_tree_t *rt)
+{
+ range_seg_t *rs = zfs_btree_first(&rt->rt_root, NULL);
+ return (rs != NULL ? rs_get_start(rs, rt) : 0);
+}
+
+uint64_t
+range_tree_max(range_tree_t *rt)
+{
+ range_seg_t *rs = zfs_btree_last(&rt->rt_root, NULL);
+ return (rs != NULL ? rs_get_end(rs, rt) : 0);
+}
+
+uint64_t
+range_tree_span(range_tree_t *rt)
+{
+ return (range_tree_max(rt) - range_tree_min(rt));
+}
diff --git a/module/zfs/sa.c b/module/zfs/sa.c
index 98bd2d330..cc2a681bd 100644
--- a/module/zfs/sa.c
+++ b/module/zfs/sa.c
@@ -252,7 +252,7 @@ layout_num_compare(const void *arg1, const void *arg2)
const sa_lot_t *node1 = (const sa_lot_t *)arg1;
const sa_lot_t *node2 = (const sa_lot_t *)arg2;
- return (AVL_CMP(node1->lot_num, node2->lot_num));
+ return (TREE_CMP(node1->lot_num, node2->lot_num));
}
static int
@@ -261,11 +261,11 @@ layout_hash_compare(const void *arg1, const void *arg2)
const sa_lot_t *node1 = (const sa_lot_t *)arg1;
const sa_lot_t *node2 = (const sa_lot_t *)arg2;
- int cmp = AVL_CMP(node1->lot_hash, node2->lot_hash);
+ int cmp = TREE_CMP(node1->lot_hash, node2->lot_hash);
if (likely(cmp))
return (cmp);
- return (AVL_CMP(node1->lot_instance, node2->lot_instance));
+ return (TREE_CMP(node1->lot_instance, node2->lot_instance));
}
boolean_t
diff --git a/module/zfs/spa.c b/module/zfs/spa.c
index 7e5c474eb..529ffc03d 100644
--- a/module/zfs/spa.c
+++ b/module/zfs/spa.c
@@ -939,7 +939,7 @@ spa_error_entry_compare(const void *a, const void *b)
ret = memcmp(&sa->se_bookmark, &sb->se_bookmark,
sizeof (zbookmark_phys_t));
- return (AVL_ISIGN(ret));
+ return (TREE_ISIGN(ret));
}
/*
diff --git a/module/zfs/spa_misc.c b/module/zfs/spa_misc.c
index ac0dd5ba9..78bf110b4 100644
--- a/module/zfs/spa_misc.c
+++ b/module/zfs/spa_misc.c
@@ -58,6 +58,7 @@
#include <sys/ddt.h>
#include <sys/kstat.h>
#include "zfs_prop.h"
+#include <sys/btree.h>
#include <sys/zfeature.h>
#include <sys/qat.h>
@@ -619,7 +620,7 @@ spa_log_sm_sort_by_txg(const void *va, const void *vb)
const spa_log_sm_t *a = va;
const spa_log_sm_t *b = vb;
- return (AVL_CMP(a->sls_txg, b->sls_txg));
+ return (TREE_CMP(a->sls_txg, b->sls_txg));
}
/*
@@ -939,7 +940,7 @@ spa_aux_compare(const void *a, const void *b)
const spa_aux_t *sa = (const spa_aux_t *)a;
const spa_aux_t *sb = (const spa_aux_t *)b;
- return (AVL_CMP(sa->aux_guid, sb->aux_guid));
+ return (TREE_CMP(sa->aux_guid, sb->aux_guid));
}
void
@@ -2270,7 +2271,7 @@ spa_name_compare(const void *a1, const void *a2)
s = strcmp(s1->spa_name, s2->spa_name);
- return (AVL_ISIGN(s));
+ return (TREE_ISIGN(s));
}
void
@@ -2318,8 +2319,8 @@ spa_init(int mode)
fm_init();
zfs_refcount_init();
unique_init();
- range_tree_init();
- metaslab_alloc_trace_init();
+ zfs_btree_init();
+ metaslab_stat_init();
ddt_init();
zio_init();
dmu_init();
@@ -2353,8 +2354,8 @@ spa_fini(void)
dmu_fini();
zio_fini();
ddt_fini();
- metaslab_alloc_trace_fini();
- range_tree_fini();
+ metaslab_stat_fini();
+ zfs_btree_fini();
unique_fini();
zfs_refcount_fini();
fm_fini();
diff --git a/module/zfs/space_map.c b/module/zfs/space_map.c
index b9467b26b..eb2c36942 100644
--- a/module/zfs/space_map.c
+++ b/module/zfs/space_map.c
@@ -523,8 +523,9 @@ space_map_write_intro_debug(space_map_t *sm, maptype_t maptype, dmu_tx_t *tx)
* dbuf must be dirty for the changes in sm_phys to take effect.
*/
static void
-space_map_write_seg(space_map_t *sm, range_seg_t *rs, maptype_t maptype,
- uint64_t vdev_id, uint8_t words, dmu_buf_t **dbp, void *tag, dmu_tx_t *tx)
+space_map_write_seg(space_map_t *sm, uint64_t rstart, uint64_t rend,
+ maptype_t maptype, uint64_t vdev_id, uint8_t words, dmu_buf_t **dbp,
+ void *tag, dmu_tx_t *tx)
{
ASSERT3U(words, !=, 0);
ASSERT3U(words, <=, 2);
@@ -548,14 +549,14 @@ space_map_write_seg(space_map_t *sm, range_seg_t *rs, maptype_t maptype,
ASSERT3P(block_cursor, <=, block_end);
- uint64_t size = (rs->rs_end - rs->rs_start) >> sm->sm_shift;
- uint64_t start = (rs->rs_start - sm->sm_start) >> sm->sm_shift;
+ uint64_t size = (rend - rstart) >> sm->sm_shift;
+ uint64_t start = (rstart - sm->sm_start) >> sm->sm_shift;
uint64_t run_max = (words == 2) ? SM2_RUN_MAX : SM_RUN_MAX;
- ASSERT3U(rs->rs_start, >=, sm->sm_start);
- ASSERT3U(rs->rs_start, <, sm->sm_start + sm->sm_size);
- ASSERT3U(rs->rs_end - rs->rs_start, <=, sm->sm_size);
- ASSERT3U(rs->rs_end, <=, sm->sm_start + sm->sm_size);
+ ASSERT3U(rstart, >=, sm->sm_start);
+ ASSERT3U(rstart, <, sm->sm_start + sm->sm_size);
+ ASSERT3U(rend - rstart, <=, sm->sm_size);
+ ASSERT3U(rend, <=, sm->sm_start + sm->sm_size);
while (size != 0) {
ASSERT3P(block_cursor, <=, block_end);
@@ -673,10 +674,14 @@ space_map_write_impl(space_map_t *sm, range_tree_t *rt, maptype_t maptype,
dmu_buf_will_dirty(db, tx);
- avl_tree_t *t = &rt->rt_root;
- for (range_seg_t *rs = avl_first(t); rs != NULL; rs = AVL_NEXT(t, rs)) {
- uint64_t offset = (rs->rs_start - sm->sm_start) >> sm->sm_shift;
- uint64_t length = (rs->rs_end - rs->rs_start) >> sm->sm_shift;
+ zfs_btree_t *t = &rt->rt_root;
+ zfs_btree_index_t where;
+ for (range_seg_t *rs = zfs_btree_first(t, &where); rs != NULL;
+ rs = zfs_btree_next(t, &where, &where)) {
+ uint64_t offset = (rs_get_start(rs, rt) - sm->sm_start) >>
+ sm->sm_shift;
+ uint64_t length = (rs_get_end(rs, rt) - rs_get_start(rs, rt)) >>
+ sm->sm_shift;
uint8_t words = 1;
/*
@@ -701,8 +706,8 @@ space_map_write_impl(space_map_t *sm, range_tree_t *rt, maptype_t maptype,
spa_get_random(100) == 0)))
words = 2;
- space_map_write_seg(sm, rs, maptype, vdev_id, words,
- &db, FTAG, tx);
+ space_map_write_seg(sm, rs_get_start(rs, rt), rs_get_end(rs,
+ rt), maptype, vdev_id, words, &db, FTAG, tx);
}
dmu_buf_rele(db, FTAG);
@@ -749,7 +754,7 @@ space_map_write(space_map_t *sm, range_tree_t *rt, maptype_t maptype,
else
sm->sm_phys->smp_alloc -= range_tree_space(rt);
- uint64_t nodes = avl_numnodes(&rt->rt_root);
+ uint64_t nodes = zfs_btree_numnodes(&rt->rt_root);
uint64_t rt_space = range_tree_space(rt);
space_map_write_impl(sm, rt, maptype, vdev_id, tx);
@@ -758,7 +763,7 @@ space_map_write(space_map_t *sm, range_tree_t *rt, maptype_t maptype,
* Ensure that the space_map's accounting wasn't changed
* while we were in the middle of writing it out.
*/
- VERIFY3U(nodes, ==, avl_numnodes(&rt->rt_root));
+ VERIFY3U(nodes, ==, zfs_btree_numnodes(&rt->rt_root));
VERIFY3U(range_tree_space(rt), ==, rt_space);
}
diff --git a/module/zfs/space_reftree.c b/module/zfs/space_reftree.c
index aa289ba10..080fc6646 100644
--- a/module/zfs/space_reftree.c
+++ b/module/zfs/space_reftree.c
@@ -23,7 +23,7 @@
* Use is subject to license terms.
*/
/*
- * Copyright (c) 2013, 2015 by Delphix. All rights reserved.
+ * Copyright (c) 2013, 2019 by Delphix. All rights reserved.
*/
#include <sys/zfs_context.h>
@@ -57,11 +57,11 @@ space_reftree_compare(const void *x1, const void *x2)
const space_ref_t *sr1 = (const space_ref_t *)x1;
const space_ref_t *sr2 = (const space_ref_t *)x2;
- int cmp = AVL_CMP(sr1->sr_offset, sr2->sr_offset);
+ int cmp = TREE_CMP(sr1->sr_offset, sr2->sr_offset);
if (likely(cmp))
return (cmp);
- return (AVL_PCMP(sr1, sr2));
+ return (TREE_PCMP(sr1, sr2));
}
void
@@ -109,10 +109,13 @@ space_reftree_add_seg(avl_tree_t *t, uint64_t start, uint64_t end,
void
space_reftree_add_map(avl_tree_t *t, range_tree_t *rt, int64_t refcnt)
{
- range_seg_t *rs;
+ zfs_btree_index_t where;
- for (rs = avl_first(&rt->rt_root); rs; rs = AVL_NEXT(&rt->rt_root, rs))
- space_reftree_add_seg(t, rs->rs_start, rs->rs_end, refcnt);
+ for (range_seg_t *rs = zfs_btree_first(&rt->rt_root, &where); rs; rs =
+ zfs_btree_next(&rt->rt_root, &where, &where)) {
+ space_reftree_add_seg(t, rs_get_start(rs, rt), rs_get_end(rs,
+ rt), refcnt);
+ }
}
/*
diff --git a/module/zfs/unique.c b/module/zfs/unique.c
index 5cdd025f4..0e076797a 100644
--- a/module/zfs/unique.c
+++ b/module/zfs/unique.c
@@ -45,7 +45,7 @@ unique_compare(const void *a, const void *b)
const unique_t *una = (const unique_t *)a;
const unique_t *unb = (const unique_t *)b;
- return (AVL_CMP(una->un_value, unb->un_value));
+ return (TREE_CMP(una->un_value, unb->un_value));
}
void
diff --git a/module/zfs/vdev.c b/module/zfs/vdev.c
index af2d1a25a..3a120b001 100644
--- a/module/zfs/vdev.c
+++ b/module/zfs/vdev.c
@@ -216,7 +216,7 @@ vdev_getops(const char *type)
/* ARGSUSED */
void
-vdev_default_xlate(vdev_t *vd, const range_seg_t *in, range_seg_t *res)
+vdev_default_xlate(vdev_t *vd, const range_seg64_t *in, range_seg64_t *res)
{
res->rs_start = in->rs_start;
res->rs_end = in->rs_end;
@@ -528,7 +528,8 @@ vdev_alloc_common(spa_t *spa, uint_t id, uint64_t guid, vdev_ops_t *ops)
rw_init(&vd->vdev_indirect_rwlock, NULL, RW_DEFAULT, NULL);
mutex_init(&vd->vdev_obsolete_lock, NULL, MUTEX_DEFAULT, NULL);
- vd->vdev_obsolete_segments = range_tree_create(NULL, NULL);
+ vd->vdev_obsolete_segments = range_tree_create(NULL, RANGE_SEG64, NULL,
+ 0, 0);
/*
* Initialize rate limit structs for events. We rate limit ZIO delay
@@ -561,7 +562,8 @@ vdev_alloc_common(spa_t *spa, uint_t id, uint64_t guid, vdev_ops_t *ops)
cv_init(&vd->vdev_trim_io_cv, NULL, CV_DEFAULT, NULL);
for (int t = 0; t < DTL_TYPES; t++) {
- vd->vdev_dtl[t] = range_tree_create(NULL, NULL);
+ vd->vdev_dtl[t] = range_tree_create(NULL, RANGE_SEG64, NULL, 0,
+ 0);
}
txg_list_create(&vd->vdev_ms_list, spa,
offsetof(struct metaslab, ms_txg_node));
@@ -2539,14 +2541,11 @@ vdev_dtl_need_resilver(vdev_t *vd, uint64_t offset, size_t psize)
static uint64_t
vdev_dtl_min(vdev_t *vd)
{
- range_seg_t *rs;
-
ASSERT(MUTEX_HELD(&vd->vdev_dtl_lock));
ASSERT3U(range_tree_space(vd->vdev_dtl[DTL_MISSING]), !=, 0);
ASSERT0(vd->vdev_children);
- rs = avl_first(&vd->vdev_dtl[DTL_MISSING]->rt_root);
- return (rs->rs_start - 1);
+ return (range_tree_min(vd->vdev_dtl[DTL_MISSING]) - 1);
}
/*
@@ -2555,14 +2554,11 @@ vdev_dtl_min(vdev_t *vd)
static uint64_t
vdev_dtl_max(vdev_t *vd)
{
- range_seg_t *rs;
-
ASSERT(MUTEX_HELD(&vd->vdev_dtl_lock));
ASSERT3U(range_tree_space(vd->vdev_dtl[DTL_MISSING]), !=, 0);
ASSERT0(vd->vdev_children);
- rs = avl_last(&vd->vdev_dtl[DTL_MISSING]->rt_root);
- return (rs->rs_end);
+ return (range_tree_max(vd->vdev_dtl[DTL_MISSING]));
}
/*
@@ -2883,7 +2879,7 @@ vdev_dtl_sync(vdev_t *vd, uint64_t txg)
ASSERT(vd->vdev_dtl_sm != NULL);
}
- rtsync = range_tree_create(NULL, NULL);
+ rtsync = range_tree_create(NULL, RANGE_SEG64, NULL, 0, 0);
mutex_enter(&vd->vdev_dtl_lock);
range_tree_walk(rt, range_tree_add, rtsync);
@@ -4730,7 +4726,8 @@ vdev_set_deferred_resilver(spa_t *spa, vdev_t *vd)
* translation function to do the real conversion.
*/
void
-vdev_xlate(vdev_t *vd, const range_seg_t *logical_rs, range_seg_t *physical_rs)
+vdev_xlate(vdev_t *vd, const range_seg64_t *logical_rs,
+ range_seg64_t *physical_rs)
{
/*
* Walk up the vdev tree
@@ -4757,7 +4754,7 @@ vdev_xlate(vdev_t *vd, const range_seg_t *logical_rs, range_seg_t *physical_rs)
* range into its physical components by calling the
* vdev specific translate function.
*/
- range_seg_t intermediate = { { { 0, 0 } } };
+ range_seg64_t intermediate = { 0 };
pvd->vdev_ops->vdev_op_xlate(vd, physical_rs, &intermediate);
physical_rs->rs_start = intermediate.rs_start;
diff --git a/module/zfs/vdev_cache.c b/module/zfs/vdev_cache.c
index 35a5b480b..6cf449d4a 100644
--- a/module/zfs/vdev_cache.c
+++ b/module/zfs/vdev_cache.c
@@ -111,7 +111,7 @@ vdev_cache_offset_compare(const void *a1, const void *a2)
const vdev_cache_entry_t *ve1 = (const vdev_cache_entry_t *)a1;
const vdev_cache_entry_t *ve2 = (const vdev_cache_entry_t *)a2;
- return (AVL_CMP(ve1->ve_offset, ve2->ve_offset));
+ return (TREE_CMP(ve1->ve_offset, ve2->ve_offset));
}
static int
@@ -120,7 +120,7 @@ vdev_cache_lastused_compare(const void *a1, const void *a2)
const vdev_cache_entry_t *ve1 = (const vdev_cache_entry_t *)a1;
const vdev_cache_entry_t *ve2 = (const vdev_cache_entry_t *)a2;
- int cmp = AVL_CMP(ve1->ve_lastused, ve2->ve_lastused);
+ int cmp = TREE_CMP(ve1->ve_lastused, ve2->ve_lastused);
if (likely(cmp))
return (cmp);
diff --git a/module/zfs/vdev_initialize.c b/module/zfs/vdev_initialize.c
index 169b9282d..a27ab3c25 100644
--- a/module/zfs/vdev_initialize.c
+++ b/module/zfs/vdev_initialize.c
@@ -291,11 +291,13 @@ vdev_initialize_block_free(abd_t *data)
static int
vdev_initialize_ranges(vdev_t *vd, abd_t *data)
{
- avl_tree_t *rt = &vd->vdev_initialize_tree->rt_root;
+ range_tree_t *rt = vd->vdev_initialize_tree;
+ zfs_btree_t *bt = &rt->rt_root;
+ zfs_btree_index_t where;
- for (range_seg_t *rs = avl_first(rt); rs != NULL;
- rs = AVL_NEXT(rt, rs)) {
- uint64_t size = rs->rs_end - rs->rs_start;
+ for (range_seg_t *rs = zfs_btree_first(bt, &where); rs != NULL;
+ rs = zfs_btree_next(bt, &where, &where)) {
+ uint64_t size = rs_get_end(rs, rt) - rs_get_start(rs, rt);
/* Split range into legally-sized physical chunks */
uint64_t writes_required =
@@ -305,7 +307,7 @@ vdev_initialize_ranges(vdev_t *vd, abd_t *data)
int error;
error = vdev_initialize_write(vd,
- VDEV_LABEL_START_SIZE + rs->rs_start +
+ VDEV_LABEL_START_SIZE + rs_get_start(rs, rt) +
(w * zfs_initialize_chunk_size),
MIN(size - (w * zfs_initialize_chunk_size),
zfs_initialize_chunk_size), data);
@@ -341,7 +343,7 @@ vdev_initialize_calculate_progress(vdev_t *vd)
* on our vdev. We use this to determine if we are
* in the middle of this metaslab range.
*/
- range_seg_t logical_rs, physical_rs;
+ range_seg64_t logical_rs, physical_rs;
logical_rs.rs_start = msp->ms_start;
logical_rs.rs_end = msp->ms_start + msp->ms_size;
vdev_xlate(vd, &logical_rs, &physical_rs);
@@ -365,10 +367,14 @@ vdev_initialize_calculate_progress(vdev_t *vd)
*/
VERIFY0(metaslab_load(msp));
- for (range_seg_t *rs = avl_first(&msp->ms_allocatable->rt_root);
- rs; rs = AVL_NEXT(&msp->ms_allocatable->rt_root, rs)) {
- logical_rs.rs_start = rs->rs_start;
- logical_rs.rs_end = rs->rs_end;
+ zfs_btree_index_t where;
+ range_tree_t *rt = msp->ms_allocatable;
+ for (range_seg_t *rs =
+ zfs_btree_first(&rt->rt_root, &where); rs;
+ rs = zfs_btree_next(&rt->rt_root, &where,
+ &where)) {
+ logical_rs.rs_start = rs_get_start(rs, rt);
+ logical_rs.rs_end = rs_get_end(rs, rt);
vdev_xlate(vd, &logical_rs, &physical_rs);
uint64_t size = physical_rs.rs_end -
@@ -422,7 +428,7 @@ void
vdev_initialize_range_add(void *arg, uint64_t start, uint64_t size)
{
vdev_t *vd = arg;
- range_seg_t logical_rs, physical_rs;
+ range_seg64_t logical_rs, physical_rs;
logical_rs.rs_start = start;
logical_rs.rs_end = start + size;
@@ -481,7 +487,8 @@ vdev_initialize_thread(void *arg)
abd_t *deadbeef = vdev_initialize_block_alloc();
- vd->vdev_initialize_tree = range_tree_create(NULL, NULL);
+ vd->vdev_initialize_tree = range_tree_create(NULL, RANGE_SEG64, NULL,
+ 0, 0);
for (uint64_t i = 0; !vd->vdev_detached &&
i < vd->vdev_top->vdev_ms_count; i++) {
diff --git a/module/zfs/vdev_label.c b/module/zfs/vdev_label.c
index 6320732ed..6bb3c3c68 100644
--- a/module/zfs/vdev_label.c
+++ b/module/zfs/vdev_label.c
@@ -1197,12 +1197,12 @@ retry:
static int
vdev_uberblock_compare(const uberblock_t *ub1, const uberblock_t *ub2)
{
- int cmp = AVL_CMP(ub1->ub_txg, ub2->ub_txg);
+ int cmp = TREE_CMP(ub1->ub_txg, ub2->ub_txg);
if (likely(cmp))
return (cmp);
- cmp = AVL_CMP(ub1->ub_timestamp, ub2->ub_timestamp);
+ cmp = TREE_CMP(ub1->ub_timestamp, ub2->ub_timestamp);
if (likely(cmp))
return (cmp);
@@ -1226,7 +1226,7 @@ vdev_uberblock_compare(const uberblock_t *ub1, const uberblock_t *ub2)
if (MMP_VALID(ub2) && MMP_SEQ_VALID(ub2))
seq2 = MMP_SEQ(ub2);
- return (AVL_CMP(seq1, seq2));
+ return (TREE_CMP(seq1, seq2));
}
struct ubl_cbdata {
diff --git a/module/zfs/vdev_queue.c b/module/zfs/vdev_queue.c
index 5e4db3df6..e156e2b01 100644
--- a/module/zfs/vdev_queue.c
+++ b/module/zfs/vdev_queue.c
@@ -218,12 +218,12 @@ vdev_queue_offset_compare(const void *x1, const void *x2)
const zio_t *z1 = (const zio_t *)x1;
const zio_t *z2 = (const zio_t *)x2;
- int cmp = AVL_CMP(z1->io_offset, z2->io_offset);
+ int cmp = TREE_CMP(z1->io_offset, z2->io_offset);
if (likely(cmp))
return (cmp);
- return (AVL_PCMP(z1, z2));
+ return (TREE_PCMP(z1, z2));
}
static inline avl_tree_t *
@@ -250,12 +250,12 @@ vdev_queue_timestamp_compare(const void *x1, const void *x2)
const zio_t *z1 = (const zio_t *)x1;
const zio_t *z2 = (const zio_t *)x2;
- int cmp = AVL_CMP(z1->io_timestamp, z2->io_timestamp);
+ int cmp = TREE_CMP(z1->io_timestamp, z2->io_timestamp);
if (likely(cmp))
return (cmp);
- return (AVL_PCMP(z1, z2));
+ return (TREE_PCMP(z1, z2));
}
static int
diff --git a/module/zfs/vdev_raidz.c b/module/zfs/vdev_raidz.c
index f63ccaa94..3408ddf72 100644
--- a/module/zfs/vdev_raidz.c
+++ b/module/zfs/vdev_raidz.c
@@ -21,7 +21,7 @@
/*
* Copyright (c) 2005, 2010, Oracle and/or its affiliates. All rights reserved.
- * Copyright (c) 2012, 2014 by Delphix. All rights reserved.
+ * Copyright (c) 2012, 2019 by Delphix. All rights reserved.
* Copyright (c) 2016 Gvozden Nešković. All rights reserved.
*/
@@ -1638,7 +1638,7 @@ vdev_raidz_io_verify(zio_t *zio, raidz_map_t *rm, int col)
vdev_t *vd = zio->io_vd;
vdev_t *tvd = vd->vdev_top;
- range_seg_t logical_rs, physical_rs;
+ range_seg64_t logical_rs, physical_rs;
logical_rs.rs_start = zio->io_offset;
logical_rs.rs_end = logical_rs.rs_start +
vdev_raidz_asize(zio->io_vd, zio->io_size);
@@ -2372,7 +2372,7 @@ vdev_raidz_need_resilver(vdev_t *vd, uint64_t offset, size_t psize)
}
static void
-vdev_raidz_xlate(vdev_t *cvd, const range_seg_t *in, range_seg_t *res)
+vdev_raidz_xlate(vdev_t *cvd, const range_seg64_t *in, range_seg64_t *res)
{
vdev_t *raidvd = cvd->vdev_parent;
ASSERT(raidvd->vdev_ops == &vdev_raidz_ops);
diff --git a/module/zfs/vdev_removal.c b/module/zfs/vdev_removal.c
index 549087163..a4fac1cc5 100644
--- a/module/zfs/vdev_removal.c
+++ b/module/zfs/vdev_removal.c
@@ -198,11 +198,12 @@ spa_vdev_removal_create(vdev_t *vd)
spa_vdev_removal_t *svr = kmem_zalloc(sizeof (*svr), KM_SLEEP);
mutex_init(&svr->svr_lock, NULL, MUTEX_DEFAULT, NULL);
cv_init(&svr->svr_cv, NULL, CV_DEFAULT, NULL);
- svr->svr_allocd_segs = range_tree_create(NULL, NULL);
+ svr->svr_allocd_segs = range_tree_create(NULL, RANGE_SEG64, NULL, 0, 0);
svr->svr_vdev_id = vd->vdev_id;
for (int i = 0; i < TXG_SIZE; i++) {
- svr->svr_frees[i] = range_tree_create(NULL, NULL);
+ svr->svr_frees[i] = range_tree_create(NULL, RANGE_SEG64, NULL,
+ 0, 0);
list_create(&svr->svr_new_segments[i],
sizeof (vdev_indirect_mapping_entry_t),
offsetof(vdev_indirect_mapping_entry_t, vime_node));
@@ -967,18 +968,15 @@ spa_vdev_copy_segment(vdev_t *vd, range_tree_t *segs,
* the allocation at the end of a segment, thus avoiding
* additional split blocks.
*/
- range_seg_t search;
- avl_index_t where;
- search.rs_start = start + maxalloc;
- search.rs_end = search.rs_start;
- range_seg_t *rs = avl_find(&segs->rt_root, &search, &where);
- if (rs == NULL) {
- rs = avl_nearest(&segs->rt_root, where, AVL_BEFORE);
- } else {
- rs = AVL_PREV(&segs->rt_root, rs);
- }
+ range_seg_max_t search;
+ zfs_btree_index_t where;
+ rs_set_start(&search, segs, start + maxalloc);
+ rs_set_end(&search, segs, start + maxalloc);
+ (void) zfs_btree_find(&segs->rt_root, &search, &where);
+ range_seg_t *rs = zfs_btree_prev(&segs->rt_root, &where,
+ &where);
if (rs != NULL) {
- size = rs->rs_end - start;
+ size = rs_get_end(rs, segs) - start;
} else {
/*
* There are no segments that end before maxalloc.
@@ -1011,20 +1009,22 @@ spa_vdev_copy_segment(vdev_t *vd, range_tree_t *segs,
* relative to the start of the range to be copied (i.e. relative to the
* local variable "start").
*/
- range_tree_t *obsolete_segs = range_tree_create(NULL, NULL);
-
- range_seg_t *rs = avl_first(&segs->rt_root);
- ASSERT3U(rs->rs_start, ==, start);
- uint64_t prev_seg_end = rs->rs_end;
- while ((rs = AVL_NEXT(&segs->rt_root, rs)) != NULL) {
- if (rs->rs_start >= start + size) {
+ range_tree_t *obsolete_segs = range_tree_create(NULL, RANGE_SEG64, NULL,
+ 0, 0);
+
+ zfs_btree_index_t where;
+ range_seg_t *rs = zfs_btree_first(&segs->rt_root, &where);
+ ASSERT3U(rs_get_start(rs, segs), ==, start);
+ uint64_t prev_seg_end = rs_get_end(rs, segs);
+ while ((rs = zfs_btree_next(&segs->rt_root, &where, &where)) != NULL) {
+ if (rs_get_start(rs, segs) >= start + size) {
break;
} else {
range_tree_add(obsolete_segs,
prev_seg_end - start,
- rs->rs_start - prev_seg_end);
+ rs_get_start(rs, segs) - prev_seg_end);
}
- prev_seg_end = rs->rs_end;
+ prev_seg_end = rs_get_end(rs, segs);
}
/* We don't end in the middle of an obsolete range */
ASSERT3U(start + size, <=, prev_seg_end);
@@ -1268,9 +1268,10 @@ spa_vdev_copy_impl(vdev_t *vd, spa_vdev_removal_t *svr, vdev_copy_arg_t *vca,
* allocated segments that we are copying. We may also be copying
* free segments (of up to vdev_removal_max_span bytes).
*/
- range_tree_t *segs = range_tree_create(NULL, NULL);
+ range_tree_t *segs = range_tree_create(NULL, RANGE_SEG64, NULL, 0, 0);
for (;;) {
- range_seg_t *rs = range_tree_first(svr->svr_allocd_segs);
+ range_tree_t *rt = svr->svr_allocd_segs;
+ range_seg_t *rs = range_tree_first(rt);
if (rs == NULL)
break;
@@ -1279,17 +1280,17 @@ spa_vdev_copy_impl(vdev_t *vd, spa_vdev_removal_t *svr, vdev_copy_arg_t *vca,
if (range_tree_is_empty(segs)) {
/* need to truncate the first seg based on max_alloc */
- seg_length =
- MIN(rs->rs_end - rs->rs_start, *max_alloc);
+ seg_length = MIN(rs_get_end(rs, rt) - rs_get_start(rs,
+ rt), *max_alloc);
} else {
- if (rs->rs_start - range_tree_max(segs) >
+ if (rs_get_start(rs, rt) - range_tree_max(segs) >
vdev_removal_max_span) {
/*
* Including this segment would cause us to
* copy a larger unneeded chunk than is allowed.
*/
break;
- } else if (rs->rs_end - range_tree_min(segs) >
+ } else if (rs_get_end(rs, rt) - range_tree_min(segs) >
*max_alloc) {
/*
* This additional segment would extend past
@@ -1298,13 +1299,14 @@ spa_vdev_copy_impl(vdev_t *vd, spa_vdev_removal_t *svr, vdev_copy_arg_t *vca,
*/
break;
} else {
- seg_length = rs->rs_end - rs->rs_start;
+ seg_length = rs_get_end(rs, rt) -
+ rs_get_start(rs, rt);
}
}
- range_tree_add(segs, rs->rs_start, seg_length);
+ range_tree_add(segs, rs_get_start(rs, rt), seg_length);
range_tree_remove(svr->svr_allocd_segs,
- rs->rs_start, seg_length);
+ rs_get_start(rs, rt), seg_length);
}
if (range_tree_is_empty(segs)) {
@@ -1483,7 +1485,7 @@ spa_vdev_remove_thread(void *arg)
vca.vca_msp = msp;
zfs_dbgmsg("copying %llu segments for metaslab %llu",
- avl_numnodes(&svr->svr_allocd_segs->rt_root),
+ zfs_btree_numnodes(&svr->svr_allocd_segs->rt_root),
msp->ms_id);
while (!svr->svr_thread_exit &&
diff --git a/module/zfs/vdev_trim.c b/module/zfs/vdev_trim.c
index 771e7a159..c7c429cbd 100644
--- a/module/zfs/vdev_trim.c
+++ b/module/zfs/vdev_trim.c
@@ -523,7 +523,8 @@ static int
vdev_trim_ranges(trim_args_t *ta)
{
vdev_t *vd = ta->trim_vdev;
- avl_tree_t *rt = &ta->trim_tree->rt_root;
+ zfs_btree_t *t = &ta->trim_tree->rt_root;
+ zfs_btree_index_t idx;
uint64_t extent_bytes_max = ta->trim_extent_bytes_max;
uint64_t extent_bytes_min = ta->trim_extent_bytes_min;
spa_t *spa = vd->vdev_spa;
@@ -531,9 +532,10 @@ vdev_trim_ranges(trim_args_t *ta)
ta->trim_start_time = gethrtime();
ta->trim_bytes_done = 0;
- for (range_seg_t *rs = avl_first(rt); rs != NULL;
- rs = AVL_NEXT(rt, rs)) {
- uint64_t size = rs->rs_end - rs->rs_start;
+ for (range_seg_t *rs = zfs_btree_first(t, &idx); rs != NULL;
+ rs = zfs_btree_next(t, &idx, &idx)) {
+ uint64_t size = rs_get_end(rs, ta->trim_tree) - rs_get_start(rs,
+ ta->trim_tree);
if (extent_bytes_min && size < extent_bytes_min) {
spa_iostats_trim_add(spa, ta->trim_type,
@@ -548,9 +550,9 @@ vdev_trim_ranges(trim_args_t *ta)
int error;
error = vdev_trim_range(ta, VDEV_LABEL_START_SIZE +
- rs->rs_start + (w * extent_bytes_max),
- MIN(size - (w * extent_bytes_max),
- extent_bytes_max));
+ rs_get_start(rs, ta->trim_tree) +
+ (w *extent_bytes_max), MIN(size -
+ (w * extent_bytes_max), extent_bytes_max));
if (error != 0) {
return (error);
}
@@ -588,7 +590,7 @@ vdev_trim_calculate_progress(vdev_t *vd)
* on our vdev. We use this to determine if we are
* in the middle of this metaslab range.
*/
- range_seg_t logical_rs, physical_rs;
+ range_seg64_t logical_rs, physical_rs;
logical_rs.rs_start = msp->ms_start;
logical_rs.rs_end = msp->ms_start + msp->ms_size;
vdev_xlate(vd, &logical_rs, &physical_rs);
@@ -611,10 +613,13 @@ vdev_trim_calculate_progress(vdev_t *vd)
*/
VERIFY0(metaslab_load(msp));
- for (range_seg_t *rs = avl_first(&msp->ms_allocatable->rt_root);
- rs; rs = AVL_NEXT(&msp->ms_allocatable->rt_root, rs)) {
- logical_rs.rs_start = rs->rs_start;
- logical_rs.rs_end = rs->rs_end;
+ range_tree_t *rt = msp->ms_allocatable;
+ zfs_btree_t *bt = &rt->rt_root;
+ zfs_btree_index_t idx;
+ for (range_seg_t *rs = zfs_btree_first(bt, &idx);
+ rs != NULL; rs = zfs_btree_next(bt, &idx, &idx)) {
+ logical_rs.rs_start = rs_get_start(rs, rt);
+ logical_rs.rs_end = rs_get_end(rs, rt);
vdev_xlate(vd, &logical_rs, &physical_rs);
uint64_t size = physical_rs.rs_end -
@@ -706,7 +711,7 @@ vdev_trim_range_add(void *arg, uint64_t start, uint64_t size)
{
trim_args_t *ta = arg;
vdev_t *vd = ta->trim_vdev;
- range_seg_t logical_rs, physical_rs;
+ range_seg64_t logical_rs, physical_rs;
logical_rs.rs_start = start;
logical_rs.rs_end = start + size;
@@ -719,7 +724,7 @@ vdev_trim_range_add(void *arg, uint64_t start, uint64_t size)
metaslab_t *msp = ta->trim_msp;
VERIFY0(metaslab_load(msp));
VERIFY3B(msp->ms_loaded, ==, B_TRUE);
- VERIFY(range_tree_find(msp->ms_allocatable, start, size));
+ VERIFY(range_tree_contains(msp->ms_allocatable, start, size));
}
ASSERT(vd->vdev_ops->vdev_op_leaf);
@@ -798,7 +803,7 @@ vdev_trim_thread(void *arg)
ta.trim_vdev = vd;
ta.trim_extent_bytes_max = zfs_trim_extent_bytes_max;
ta.trim_extent_bytes_min = zfs_trim_extent_bytes_min;
- ta.trim_tree = range_tree_create(NULL, NULL);
+ ta.trim_tree = range_tree_create(NULL, RANGE_SEG64, NULL, 0, 0);
ta.trim_type = TRIM_TYPE_MANUAL;
ta.trim_flags = 0;
@@ -1080,7 +1085,7 @@ vdev_trim_range_verify(void *arg, uint64_t start, uint64_t size)
VERIFY3B(msp->ms_loaded, ==, B_TRUE);
VERIFY3U(msp->ms_disabled, >, 0);
- VERIFY(range_tree_find(msp->ms_allocatable, start, size) != NULL);
+ VERIFY(range_tree_contains(msp->ms_allocatable, start, size));
}
/*
@@ -1178,7 +1183,8 @@ vdev_autotrim_thread(void *arg)
* Allocate an empty range tree which is swapped in
* for the existing ms_trim tree while it is processed.
*/
- trim_tree = range_tree_create(NULL, NULL);
+ trim_tree = range_tree_create(NULL, RANGE_SEG64, NULL,
+ 0, 0);
range_tree_swap(&msp->ms_trim, &trim_tree);
ASSERT(range_tree_is_empty(msp->ms_trim));
@@ -1232,7 +1238,8 @@ vdev_autotrim_thread(void *arg)
if (!cvd->vdev_ops->vdev_op_leaf)
continue;
- ta->trim_tree = range_tree_create(NULL, NULL);
+ ta->trim_tree = range_tree_create(NULL,
+ RANGE_SEG64, NULL, 0, 0);
range_tree_walk(trim_tree,
vdev_trim_range_add, ta);
}
diff --git a/module/zfs/zap_micro.c b/module/zfs/zap_micro.c
index 467812ff6..c3d42d0ee 100644
--- a/module/zfs/zap_micro.c
+++ b/module/zfs/zap_micro.c
@@ -280,11 +280,11 @@ mze_compare(const void *arg1, const void *arg2)
const mzap_ent_t *mze1 = arg1;
const mzap_ent_t *mze2 = arg2;
- int cmp = AVL_CMP(mze1->mze_hash, mze2->mze_hash);
+ int cmp = TREE_CMP(mze1->mze_hash, mze2->mze_hash);
if (likely(cmp))
return (cmp);
- return (AVL_CMP(mze1->mze_cd, mze2->mze_cd));
+ return (TREE_CMP(mze1->mze_cd, mze2->mze_cd));
}
static void
diff --git a/module/zfs/zfs_fuid.c b/module/zfs/zfs_fuid.c
index 78071707a..925d1934f 100644
--- a/module/zfs/zfs_fuid.c
+++ b/module/zfs/zfs_fuid.c
@@ -73,7 +73,7 @@ idx_compare(const void *arg1, const void *arg2)
const fuid_domain_t *node1 = (const fuid_domain_t *)arg1;
const fuid_domain_t *node2 = (const fuid_domain_t *)arg2;
- return (AVL_CMP(node1->f_idx, node2->f_idx));
+ return (TREE_CMP(node1->f_idx, node2->f_idx));
}
/*
@@ -88,7 +88,7 @@ domain_compare(const void *arg1, const void *arg2)
val = strcmp(node1->f_ksid->kd_name, node2->f_ksid->kd_name);
- return (AVL_ISIGN(val));
+ return (TREE_ISIGN(val));
}
void
diff --git a/module/zfs/zfs_rlock.c b/module/zfs/zfs_rlock.c
index 94203a40c..db587c731 100644
--- a/module/zfs/zfs_rlock.c
+++ b/module/zfs/zfs_rlock.c
@@ -109,7 +109,7 @@ zfs_rangelock_compare(const void *arg1, const void *arg2)
const locked_range_t *rl1 = (const locked_range_t *)arg1;
const locked_range_t *rl2 = (const locked_range_t *)arg2;
- return (AVL_CMP(rl1->lr_offset, rl2->lr_offset));
+ return (TREE_CMP(rl1->lr_offset, rl2->lr_offset));
}
/*
diff --git a/module/zfs/zil.c b/module/zfs/zil.c
index 30a73515c..7e65ac090 100644
--- a/module/zfs/zil.c
+++ b/module/zfs/zil.c
@@ -146,11 +146,11 @@ zil_bp_compare(const void *x1, const void *x2)
const dva_t *dva1 = &((zil_bp_node_t *)x1)->zn_dva;
const dva_t *dva2 = &((zil_bp_node_t *)x2)->zn_dva;
- int cmp = AVL_CMP(DVA_GET_VDEV(dva1), DVA_GET_VDEV(dva2));
+ int cmp = TREE_CMP(DVA_GET_VDEV(dva1), DVA_GET_VDEV(dva2));
if (likely(cmp))
return (cmp);
- return (AVL_CMP(DVA_GET_OFFSET(dva1), DVA_GET_OFFSET(dva2)));
+ return (TREE_CMP(DVA_GET_OFFSET(dva1), DVA_GET_OFFSET(dva2)));
}
static void
@@ -535,7 +535,7 @@ zil_lwb_vdev_compare(const void *x1, const void *x2)
const uint64_t v1 = ((zil_vdev_node_t *)x1)->zv_vdev;
const uint64_t v2 = ((zil_vdev_node_t *)x2)->zv_vdev;
- return (AVL_CMP(v1, v2));
+ return (TREE_CMP(v1, v2));
}
static lwb_t *
@@ -1869,7 +1869,7 @@ zil_aitx_compare(const void *x1, const void *x2)
const uint64_t o1 = ((itx_async_node_t *)x1)->ia_foid;
const uint64_t o2 = ((itx_async_node_t *)x2)->ia_foid;
- return (AVL_CMP(o1, o2));
+ return (TREE_CMP(o1, o2));
}
/*