FreeBSD/Linux Kernel Cross Reference
sys/contrib/openzfs/module/zfs/btree.c

     /*
      * 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).
     */
    uint_t zfs_btree_verify_intensity = 0;
    
    /*
     * Convenience functions to silence warnings from memcpy/memmove's
     * return values and change argument order to src, dest.
     */
    static void
    bcpy(const void *src, void *dest, size_t size)
    {
            (void) memcpy(dest, src, size);
    }
    
    static void
    bmov(const void *src, void *dest, size_t size)
    {
            (void) memmove(dest, src, size);
    }
    
    static boolean_t
    zfs_btree_is_core(struct zfs_btree_hdr *hdr)
    {
            return (hdr->bth_first == -1);
    }
    
    #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 (zfs_btree_is_core(hdr)) {
                    zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
                    for (uint32_t 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);
           } else {
                   zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;
                   (void) memset(leaf->btl_elems, 0x0f, hdr->bth_first * size);
                   (void) memset(leaf->btl_elems +
                       (hdr->bth_first + hdr->bth_count) * size, 0x0f,
                       tree->bt_leaf_size - offsetof(zfs_btree_leaf_t, btl_elems) -
                       (hdr->bth_first + hdr->bth_count) * size);
           }
   #endif
   }
   
   static inline void
   zfs_btree_poison_node_at(zfs_btree_t *tree, zfs_btree_hdr_t *hdr,
       uint32_t idx, uint32_t count)
   {
   #ifdef ZFS_DEBUG
           size_t size = tree->bt_elem_size;
           if (zfs_btree_is_core(hdr)) {
                   ASSERT3U(idx, >=, hdr->bth_count);
                   ASSERT3U(idx, <=, BTREE_CORE_ELEMS);
                   ASSERT3U(idx + count, <=, BTREE_CORE_ELEMS);
                   zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
                   for (uint32_t i = 1; i <= count; i++) {
                           node->btc_children[idx + i] =
                               (zfs_btree_hdr_t *)BTREE_POISON;
                   }
                   (void) memset(node->btc_elems + idx * size, 0x0f, count * size);
           } else {
                   ASSERT3U(idx, <=, tree->bt_leaf_cap);
                   ASSERT3U(idx + count, <=, tree->bt_leaf_cap);
                   zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;
                   (void) memset(leaf->btl_elems +
                       (hdr->bth_first + idx) * size, 0x0f, count * size);
           }
   #endif
   }
   
   static inline void
   zfs_btree_verify_poison_at(zfs_btree_t *tree, zfs_btree_hdr_t *hdr,
       uint32_t idx)
   {
   #ifdef ZFS_DEBUG
           size_t size = tree->bt_elem_size;
           if (zfs_btree_is_core(hdr)) {
                   ASSERT3U(idx, <, BTREE_CORE_ELEMS);
                   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[idx + 1], ==, cval);
                   for (size_t i = 0; i < size; i++)
                           VERIFY3U(node->btc_elems[idx * size + i], ==, 0x0f);
           } else  {
                   ASSERT3U(idx, <, tree->bt_leaf_cap);
                   zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;
                   if (idx >= tree->bt_leaf_cap - hdr->bth_first)
                           return;
                   for (size_t i = 0; i < size; i++) {
                           VERIFY3U(leaf->btl_elems[(hdr->bth_first + idx)
                               * size + i], ==, 0x0f);
                   }
           }
   #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);
   }
   
   static void *
   zfs_btree_leaf_alloc(zfs_btree_t *tree)
   {
           if (tree->bt_leaf_size == BTREE_LEAF_SIZE)
                   return (kmem_cache_alloc(zfs_btree_leaf_cache, KM_SLEEP));
           else
                   return (kmem_alloc(tree->bt_leaf_size, KM_SLEEP));
   }
   
   static void
   zfs_btree_leaf_free(zfs_btree_t *tree, void *ptr)
   {
           if (tree->bt_leaf_size == BTREE_LEAF_SIZE)
                   return (kmem_cache_free(zfs_btree_leaf_cache, ptr));
           else
                   return (kmem_free(ptr, tree->bt_leaf_size));
   }
   
   void
   zfs_btree_create(zfs_btree_t *tree, int (*compar) (const void *, const void *),
       size_t size)
   {
           zfs_btree_create_custom(tree, compar, size, BTREE_LEAF_SIZE);
   }
   
   void
   zfs_btree_create_custom(zfs_btree_t *tree,
       int (*compar) (const void *, const void *),
       size_t size, size_t lsize)
   {
           size_t esize = lsize - offsetof(zfs_btree_leaf_t, btl_elems);
   
           ASSERT3U(size, <=, esize / 2);
           memset(tree, 0, sizeof (*tree));
           tree->bt_compar = compar;
           tree->bt_elem_size = size;
           tree->bt_leaf_size = lsize;
           tree->bt_leaf_cap = P2ALIGN(esize / size, 2);
           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, uint32_t nelems,
       const void *value, zfs_btree_index_t *where)
   {
           uint32_t max = nelems;
           uint32_t min = 0;
           while (max > min) {
                   uint32_t idx = (min + max) / 2;
                   uint8_t *cur = buf + idx * tree->bt_elem_size;
                   int comp = tree->bt_compar(cur, value);
                   if (comp < 0) {
                           min = idx + 1;
                   } else if (comp > 0) {
                           max = idx;
                   } else {
                           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;
           size_t size = tree->bt_elem_size;
           if (tree->bt_bulk != NULL) {
                   zfs_btree_leaf_t *last_leaf = tree->bt_bulk;
                   int comp = tree->bt_compar(last_leaf->btl_elems +
                       (last_leaf->btl_hdr.bth_first +
                       last_leaf->btl_hdr.bth_count - 1) * size, value);
                   if (comp < 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 (comp == 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_first +
                               last_leaf->btl_hdr.bth_count - 1) * size);
                   }
                   if (tree->bt_compar(last_leaf->btl_elems +
                       last_leaf->btl_hdr.bth_first * size, 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_first * size,
                               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;
           uint32_t child = 0;
           uint32_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_first * size,
               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 parallelogram 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, uint32_t idx,
       uint32_t count, uint32_t off, enum bt_shift_shape shape,
       enum bt_shift_direction dir)
   {
           size_t size = tree->bt_elem_size;
           ASSERT(zfs_btree_is_core(&node->btc_hdr));
   
           uint8_t *e_start = node->btc_elems + idx * size;
           uint8_t *e_out = (dir == BSD_LEFT ? e_start - off * size :
               e_start + off * size);
           bmov(e_start, e_out, 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);
           uint32_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, uint32_t idx,
       uint32_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, uint32_t idx,
       uint32_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, uint32_t idx,
       uint32_t count, uint32_t off, enum bt_shift_direction dir)
   {
           size_t size = tree->bt_elem_size;
           zfs_btree_hdr_t *hdr = &node->btl_hdr;
           ASSERT(!zfs_btree_is_core(hdr));
   
           if (count == 0)
                   return;
           uint8_t *start = node->btl_elems + (hdr->bth_first + idx) * size;
           uint8_t *out = (dir == BSD_LEFT ? start - off * size :
               start + off * size);
           bmov(start, out, count * size);
   }
   
   /*
    * Grow leaf for n new elements before idx.
    */
   static void
   bt_grow_leaf(zfs_btree_t *tree, zfs_btree_leaf_t *leaf, uint32_t idx,
       uint32_t n)
   {
           zfs_btree_hdr_t *hdr = &leaf->btl_hdr;
           ASSERT(!zfs_btree_is_core(hdr));
           ASSERT3U(idx, <=, hdr->bth_count);
           uint32_t capacity = tree->bt_leaf_cap;
           ASSERT3U(hdr->bth_count + n, <=, capacity);
           boolean_t cl = (hdr->bth_first >= n);
           boolean_t cr = (hdr->bth_first + hdr->bth_count + n <= capacity);
   
           if (cl && (!cr || idx <= hdr->bth_count / 2)) {
                   /* Grow left. */
                   hdr->bth_first -= n;
                   bt_shift_leaf(tree, leaf, n, idx, n, BSD_LEFT);
           } else if (cr) {
                   /* Grow right. */
                   bt_shift_leaf(tree, leaf, idx, hdr->bth_count - idx, n,
                       BSD_RIGHT);
           } else {
                   /* Grow both ways. */
                   uint32_t fn = hdr->bth_first -
                       (capacity - (hdr->bth_count + n)) / 2;
                   hdr->bth_first -= fn;
                   bt_shift_leaf(tree, leaf, fn, idx, fn, BSD_LEFT);
                   bt_shift_leaf(tree, leaf, fn + idx, hdr->bth_count - idx,
                       n - fn, BSD_RIGHT);
           }
           hdr->bth_count += n;
   }
   
   /*
    * Shrink leaf for count elements starting from idx.
    */
   static void
   bt_shrink_leaf(zfs_btree_t *tree, zfs_btree_leaf_t *leaf, uint32_t idx,
       uint32_t n)
   {
           zfs_btree_hdr_t *hdr = &leaf->btl_hdr;
           ASSERT(!zfs_btree_is_core(hdr));
           ASSERT3U(idx, <=, hdr->bth_count);
           ASSERT3U(idx + n, <=, hdr->bth_count);
   
           if (idx <= (hdr->bth_count - n) / 2) {
                   bt_shift_leaf(tree, leaf, 0, idx, n, BSD_RIGHT);
                   zfs_btree_poison_node_at(tree, hdr, 0, n);
                   hdr->bth_first += n;
           } else {
                   bt_shift_leaf(tree, leaf, idx + n, hdr->bth_count - idx - n, n,
                       BSD_LEFT);
                   zfs_btree_poison_node_at(tree, hdr, hdr->bth_count - n, n);
           }
           hdr->bth_count -= n;
   }
   
   /*
    * 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, uint32_t sidx,
       uint32_t count, zfs_btree_core_t *dest, uint32_t didx,
       enum bt_shift_shape shape)
   {
           size_t size = tree->bt_elem_size;
           ASSERT(zfs_btree_is_core(&source->btc_hdr));
           ASSERT(zfs_btree_is_core(&dest->btc_hdr));
   
           bcpy(source->btc_elems + sidx * size, dest->btc_elems + didx * size,
               count * size);
   
           uint32_t c_count = count + (shape == BSS_TRAPEZOID ? 1 : 0);
           bcpy(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, uint32_t sidx,
       uint32_t count, zfs_btree_leaf_t *dest, uint32_t didx)
   {
           size_t size = tree->bt_elem_size;
           ASSERT(!zfs_btree_is_core(&source->btl_hdr));
           ASSERT(!zfs_btree_is_core(&dest->btl_hdr));
   
           bcpy(source->btl_elems + (source->btl_hdr.bth_first + sidx) * size,
               dest->btl_elems + (dest->btl_hdr.bth_first + 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_t *tree, zfs_btree_hdr_t *hdr,
       zfs_btree_index_t *where)
   {
           zfs_btree_hdr_t *node;
   
           for (node = hdr; zfs_btree_is_core(node);
               node = ((zfs_btree_core_t *)node)->btc_children[0])
                   ;
   
           ASSERT(!zfs_btree_is_core(node));
           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[node->bth_first * tree->bt_elem_size]);
   }
   
   /* 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,
       uint32_t offset, zfs_btree_hdr_t *new_node, void *buf)
   {
           size_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 */
           uint32_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;
           bcpy(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);
           size_t size = tree->bt_elem_size;
           zfs_btree_core_t *parent = old_node->bth_parent;
   
           /*
            * 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_first = -1;
                   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;
                   bcpy(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_hdr_t *par_hdr = &parent->btc_hdr;
           zfs_btree_index_t idx;
           ASSERT(zfs_btree_is_core(par_hdr));
           VERIFY3P(zfs_btree_find_in_buf(tree, parent->btc_elems,
               par_hdr->bth_count, buf, &idx), ==, NULL);
           ASSERT(idx.bti_before);
           uint32_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 accommodate 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.
            */
           uint32_t move_count = MAX((BTREE_CORE_ELEMS / (tree->bt_bulk == NULL ?
               2 : 4)) - 1, 2);
           uint32_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_first = -1;
           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);
           bcpy(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.
                    */
                   bcpy(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.
                    */
                   bcpy(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 accommodate new_node.
                    */
                   bt_shift_core_right(tree, new_parent, 0, move_count,
                       BSS_TRAPEZOID);
                   new_parent->btc_children[0] = new_node;
                   bcpy(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 (uint32_t i = 0; i <= new_parent->btc_hdr.bth_count; i++)
                   new_parent->btc_children[i]->bth_parent = new_parent;
   
           for (uint32_t 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,
       uint32_t idx, const void *value)
   {
           size_t size = tree->bt_elem_size;
           zfs_btree_hdr_t *hdr = &leaf->btl_hdr;
           ASSERT3U(leaf->btl_hdr.bth_count, <, tree->bt_leaf_cap);
   
           if (zfs_btree_verify_intensity >= 5) {
                   zfs_btree_verify_poison_at(tree, &leaf->btl_hdr,
                       leaf->btl_hdr.bth_count);
           }
   
           bt_grow_leaf(tree, leaf, idx, 1);
           uint8_t *start = leaf->btl_elems + (hdr->bth_first + idx) * size;
           bcpy(value, start, size);
   }
   
   static void
   zfs_btree_verify_order_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr);
   
   /* 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, uint32_t idx)
   {
           size_t size = tree->bt_elem_size;
           uint32_t capacity = tree->bt_leaf_cap;
   
           /*
            * 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.
            */
           uint32_t move_count = MAX(capacity / (tree->bt_bulk ? 4 : 2), 1) - 1;
           uint32_t keep_count = capacity - move_count - 1;
           ASSERT3U(keep_count, >=, 1);
           /* If we insert on left. move one more to keep leaves balanced.  */
           if (idx < keep_count) {
                   keep_count--;
                   move_count++;
           }
           tree->bt_num_nodes++;
           zfs_btree_leaf_t *new_leaf = zfs_btree_leaf_alloc(tree);
           zfs_btree_hdr_t *new_hdr = &new_leaf->btl_hdr;
           new_hdr->bth_parent = leaf->btl_hdr.bth_parent;
           new_hdr->bth_first = (tree->bt_bulk ? 0 : capacity / 4) +
               (idx >= keep_count && idx <= keep_count + move_count / 2);
           new_hdr->bth_count = move_count;
           zfs_btree_poison_node(tree, new_hdr);
   
           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);
           bcpy(leaf->btl_elems + (leaf->btl_hdr.bth_first + keep_count) * size,
               buf, size);
   
           bt_shrink_leaf(tree, leaf, keep_count, 1 + move_count);
   
           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 {
                   /*
                    * Insert planned separator into the new leaf, and use
                    * the new value as the new separator.
                    */
                   zfs_btree_insert_leaf_impl(tree, new_leaf, 0, buf);
                   bcpy(value, buf, size);
           }
   
           /*
            * 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 uint32_t
   zfs_btree_find_parent_idx(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
   {
           void *buf;
           if (zfs_btree_is_core(hdr)) {
                   buf = ((zfs_btree_core_t *)hdr)->btc_elems;
           } else {
                   buf = ((zfs_btree_leaf_t *)hdr)->btl_elems +
                       hdr->bth_first * tree->bt_elem_size;
           }
           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;
           size_t size = tree->bt_elem_size;
           uint32_t capacity = tree->bt_leaf_cap;
   
           /*
            * 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(zfs_btree_is_core(idx.bti_node));
                   zfs_btree_core_t *common = (zfs_btree_core_t *)idx.bti_node;
                   uint32_t common_idx = idx.bti_offset;
   
                   VERIFY3P(zfs_btree_prev(tree, &idx, &idx), !=, NULL);
                   ASSERT(!zfs_btree_is_core(idx.bti_node));
                   zfs_btree_leaf_t *l_neighbor = (zfs_btree_leaf_t *)idx.bti_node;
                   zfs_btree_hdr_t *l_hdr = idx.bti_node;
                   uint32_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 (uint32_t 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_grow_leaf(tree, leaf, 0, move_count);
   
                   /* 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 +
                       (hdr->bth_first + move_count - 1) * size;
                   bcpy(separator, out, size);
   
                   /*
                    * 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 - 1), move_count - 1, leaf, 0);
   
                   /*
                    * Finally, move the new last element in the left neighbor to
                    * the separator.
                    */
                   bcpy(l_neighbor->btl_elems + (l_hdr->bth_first +
                       l_hdr->bth_count - move_count) * size, separator, size);
   
                   /* Adjust the node's counts, and we're done. */
                   bt_shrink_leaf(tree, l_neighbor, l_hdr->bth_count - move_count,
                       move_count);
   
                   ASSERT3U(l_hdr->bth_count, >=, capacity / 2);
                   ASSERT3U(hdr->bth_count, >=, capacity / 2);
           }
  
          /*
           * 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).
                   */
                  uint32_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];
                  uint32_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 (uint32_t 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);
                  bcpy(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--;
                  uint32_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--;
                  bcpy(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 (uint32_t i = 0; i <= hdr->bth_count; i++)
                          cur->btc_children[i]->bth_parent = cur;
          }
  
          tree->bt_bulk = NULL;
          zfs_btree_verify(tree);
  }
  
  /*
   * Insert value into tree at the location specified by where.
   */
  void
  zfs_btree_add_idx(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 = zfs_btree_leaf_alloc(tree);
                  tree->bt_root = &leaf->btl_hdr;
                  tree->bt_height++;
  
                  zfs_btree_hdr_t *hdr = &leaf->btl_hdr;
                  hdr->bth_parent = NULL;
                  hdr->bth_first = 0;
                  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 (!zfs_btree_is_core(where->bti_node)) {
                  /*
                   * 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.
                   */
                  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.
                   */
                  uint32_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);
                  bcpy(node->btc_elems + off * size, buf, size);
                  bcpy(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(tree, subtree, &new_idx), !=,
                      NULL);
                  ASSERT0(new_idx.bti_offset);
                  ASSERT(!zfs_btree_is_core(new_idx.bti_node));
                  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, 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; zfs_btree_is_core(node); 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_first + 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);
          }
  
          uint32_t offset = idx->bti_offset;
          if (!zfs_btree_is_core(idx->bti_node)) {
                  /*
                   * 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;
                  uint32_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 + (leaf->btl_hdr.bth_first +
                              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(zfs_btree_is_core(hdr));
                          uint32_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(zfs_btree_is_core(idx->bti_node));
          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(tree, 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);
          }
  
          uint32_t offset = idx->bti_offset;
          if (!zfs_btree_is_core(idx->bti_node)) {
                  /*
                   * 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 + (leaf->btl_hdr.bth_first +
                              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(zfs_btree_is_core(hdr));
                          uint32_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(zfs_btree_is_core(idx->bti_node));
          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);
          size_t size = tree->bt_elem_size;
          if (!zfs_btree_is_core(idx->bti_node)) {
                  zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)idx->bti_node;
                  return (leaf->btl_elems + (leaf->btl_hdr.bth_first +
                      idx->bti_offset) * size);
          }
          zfs_btree_core_t *node = (zfs_btree_core_t *)idx->bti_node;
          return (node->btc_elems + idx->bti_offset * 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_add_idx(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 (!zfs_btree_is_core(node)) {
                  zfs_btree_leaf_free(tree, 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;
          uint32_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;
          }
  
          uint32_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, 1);
                  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 between 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;
          uint32_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(zfs_btree_is_core(l_hdr));
                  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;
                  bcpy(separator, node->btc_elems, size);
  
                  /* Move the last child of neighbor to our first child slot. */
                  node->btc_children[0] =
                      neighbor->btc_children[l_hdr->bth_count];
                  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;
                  bcpy(take_elem, separator, size);
                  l_hdr->bth_count--;
                  zfs_btree_poison_node_at(tree, l_hdr, l_hdr->bth_count, 1);
                  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(zfs_btree_is_core(r_hdr));
                  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;
                  bcpy(separator, node->btc_elems + (hdr->bth_count - 1) * size,
                      size);
  
                  /*
                   * Move the first child of neighbor to the last child spot in
                   * node.
                   */
                  node->btc_children[hdr->bth_count] = neighbor->btc_children[0];
                  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;
                  bcpy(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, 1);
                  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,
           * arbitrarily. 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;
          uint32_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(zfs_btree_is_core(keep_hdr));
          ASSERT(zfs_btree_is_core(new_rm_hdr));
  
          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 (uint32_t 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;
          bcpy(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);
  
          uint32_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 (uint32_t i = 0; i < new_rm_hdr->bth_count + 1; i++)
                  new_start[i]->bth_parent = keep;
          for (uint32_t 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, 1);
  
          new_rm_hdr->bth_count = 0;
          zfs_btree_remove_from_node(tree, parent, new_rm_hdr);
          zfs_btree_node_destroy(tree, new_rm_hdr);
  }
  
  /* Remove the element at the specific location. */
  void
  zfs_btree_remove_idx(zfs_btree_t *tree, zfs_btree_index_t *where)
  {
          size_t size = tree->bt_elem_size;
          zfs_btree_hdr_t *hdr = where->bti_node;
          uint32_t idx = where->bti_offset;
  
          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);
                  bcpy(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 (zfs_btree_is_core(hdr)) {
                  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);
  
                  bcpy(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(!zfs_btree_is_core(hdr));
          zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;
          ASSERT3U(hdr->bth_count, >, 0);
  
          uint32_t min_count = (tree->bt_leaf_cap / 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) {
                  bt_shrink_leaf(tree, leaf, idx, 1);
                  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);
                          }
                  }
                  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 between 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;
          uint32_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(!zfs_btree_is_core(l_hdr));
                  zfs_btree_leaf_t *neighbor = (zfs_btree_leaf_t *)l_hdr;
  
                  /*
                   * Move our elements back by one spot to make room for the
                   * stolen element and overwrite the element being removed.
                   */
                  bt_shift_leaf(tree, leaf, 0, idx, 1, BSD_RIGHT);
  
                  /* Move the separator to our first spot. */
                  uint8_t *separator = parent->btc_elems + (parent_idx - 1) *
                      size;
                  bcpy(separator, leaf->btl_elems + hdr->bth_first * size, size);
  
                  /* Move our neighbor's last element to the separator. */
                  uint8_t *take_elem = neighbor->btl_elems +
                      (l_hdr->bth_first + l_hdr->bth_count - 1) * size;
                  bcpy(take_elem, separator, size);
  
                  /* Delete our neighbor's last element. */
                  bt_shrink_leaf(tree, neighbor, l_hdr->bth_count - 1, 1);
                  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(!zfs_btree_is_core(r_hdr));
                  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(tree, leaf, idx + 1, hdr->bth_count - idx - 1,
                      1, BSD_LEFT);
  
                  /* Move the separator between us to our last spot. */
                  uint8_t *separator = parent->btc_elems + parent_idx * size;
                  bcpy(separator, leaf->btl_elems + (hdr->bth_first +
                      hdr->bth_count - 1) * size, size);
  
                  /* Move our neighbor's first element to the separator. */
                  uint8_t *take_elem = neighbor->btl_elems +
                      r_hdr->bth_first * size;
                  bcpy(take_elem, separator, size);
  
                  /* Delete our neighbor's first element. */
                  bt_shrink_leaf(tree, neighbor, 0, 1);
                  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, arbitrarily.
           * After remove we 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, *k_hdr;
          if (l_hdr != NULL) {
                  k_hdr = l_hdr;
                  rm_hdr = hdr;
          } else {
                  ASSERT3P(r_hdr, !=, NULL);
                  k_hdr = hdr;
                  rm_hdr = r_hdr;
                  parent_idx++;
          }
          ASSERT(!zfs_btree_is_core(k_hdr));
          ASSERT(!zfs_btree_is_core(rm_hdr));
          ASSERT3U(k_hdr->bth_count, ==, min_count);
          ASSERT3U(rm_hdr->bth_count, ==, min_count);
          zfs_btree_leaf_t *keep = (zfs_btree_leaf_t *)k_hdr;
          zfs_btree_leaf_t *rm = (zfs_btree_leaf_t *)rm_hdr;
  
          if (zfs_btree_verify_intensity >= 5) {
                  for (uint32_t i = 0; i < rm_hdr->bth_count + 1; i++) {
                          zfs_btree_verify_poison_at(tree, k_hdr,
                              k_hdr->bth_count + i);
                  }
          }
  
          /*
           * Remove the value from the node.  It will go below the minimum,
           * but we'll fix it in no time.
           */
          bt_shrink_leaf(tree, leaf, idx, 1);
  
          /* Prepare space for elements to be moved from the right. */
          uint32_t k_count = k_hdr->bth_count;
          bt_grow_leaf(tree, keep, k_count, 1 + rm_hdr->bth_count);
          ASSERT3U(k_hdr->bth_count, ==, min_count * 2);
  
          /* Move the separator into the first open spot. */
          uint8_t *out = keep->btl_elems + (k_hdr->bth_first + k_count) * size;
          uint8_t *separator = parent->btc_elems + (parent_idx - 1) * size;
          bcpy(separator, out, size);
  
          /* Move our elements to the left neighbor. */
          bt_transfer_leaf(tree, rm, 0, rm_hdr->bth_count, keep, k_count + 1);
  
          /* Remove the emptied node from the parent. */
          zfs_btree_remove_from_node(tree, parent, rm_hdr);
          zfs_btree_node_destroy(tree, 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_idx(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 (zfs_btree_is_core(hdr)) {
                  zfs_btree_core_t *btc = (zfs_btree_core_t *)hdr;
                  for (uint32_t 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 (!zfs_btree_is_core(hdr))
                  return;
  
          zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
          for (uint32_t 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 (!zfs_btree_is_core(hdr)) {
                  if (tree->bt_root != hdr && tree->bt_bulk &&
                      hdr != &tree->bt_bulk->btl_hdr) {
                          VERIFY3U(hdr->bth_count, >=, tree->bt_leaf_cap / 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 (uint32_t 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,
      int32_t height)
  {
          if (!zfs_btree_is_core(hdr)) {
                  VERIFY0(height);
                  return (1);
          }
  
          zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
          uint64_t ret = 1;
          for (uint32_t 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 (!zfs_btree_is_core(hdr)) {
                  zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;
                  for (uint32_t i = 1; i < hdr->bth_count; i++) {
                          VERIFY3S(tree->bt_compar(leaf->btl_elems +
                              (hdr->bth_first + i - 1) * size,
                              leaf->btl_elems +
                              (hdr->bth_first + i) * size), ==, -1);
                  }
                  return;
          }
  
          zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
          for (uint32_t i = 1; i < hdr->bth_count; i++) {
                  VERIFY3S(tree->bt_compar(node->btc_elems + (i - 1) * size,
                      node->btc_elems + i * size), ==, -1);
          }
          for (uint32_t 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 (zfs_btree_is_core(left_child_hdr)) {
                          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_first +
                              left_child_hdr->bth_count - 1) * size;
                  }
                  int comp = tree->bt_compar(node->btc_elems + i * size,
                      left_child_last);
                  if (comp <= 0) {
                          panic("btree: compar returned %d (expected 1) at "
                              "%px %d: compar(%px,  %px)", comp, node, i,
                              node->btc_elems + i * size, left_child_last);
                  }
  
                  uint8_t *right_child_first = NULL;
                  zfs_btree_hdr_t *right_child_hdr = node->btc_children[i + 1];
                  if (zfs_btree_is_core(right_child_hdr)) {
                          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 +
                              right_child_hdr->bth_first * size;
                  }
                  comp = tree->bt_compar(node->btc_elems + i * size,
                      right_child_first);
                  if (comp >= 0) {
                          panic("btree: compar returned %d (expected -1) at "
                              "%px %d: compar(%px,  %px)", comp, node, i,
                              node->btc_elems + i * size, right_child_first);
                  }
          }
          for (uint32_t 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 (!zfs_btree_is_core(hdr)) {
                  zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;
                  for (size_t i = 0; i < hdr->bth_first * size; i++)
                          VERIFY3U(leaf->btl_elems[i], ==, 0x0f);
                  size_t esize = tree->bt_leaf_size -
                      offsetof(zfs_btree_leaf_t, btl_elems);
                  for (size_t i = (hdr->bth_first + hdr->bth_count) * size;
                      i < esize; i++)
                          VERIFY3U(leaf->btl_elems[i], ==, 0x0f);
          } else {
                  zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;
                  for (size_t i = hdr->bth_count * size;
                      i < BTREE_CORE_ELEMS * size; i++)
                          VERIFY3U(node->btc_elems[i], ==, 0x0f);
  
                  for (uint32_t i = hdr->bth_count + 1; i <= BTREE_CORE_ELEMS;
                      i++) {
                          VERIFY3P(node->btc_children[i], ==,
                              (zfs_btree_hdr_t *)BTREE_POISON);
                  }
  
                  for (uint32_t 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);
  }
  
  /* BEGIN CSTYLED */
  ZFS_MODULE_PARAM(zfs, zfs_, btree_verify_intensity, UINT, ZMOD_RW,
          "Enable btree verification. Levels above 4 require ZFS be built "
          "with debugging");
  /* END CSTYLED */

Cache object: 2ebd19c843a6adb5c075935d3166bdb3