Lines Matching full:tree
32 * Intensity 1: Verify that the tree's height is consistent throughout.
35 * Intensity 3: Verify that the total number of elements in the tree matches the
87 zfs_btree_poison_node(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
90 size_t size = tree->bt_elem_size;
105 tree->bt_leaf_size - offsetof(zfs_btree_leaf_t, btl_elems) -
112 zfs_btree_poison_node_at(zfs_btree_t *tree, zfs_btree_hdr_t *hdr,
116 size_t size = tree->bt_elem_size;
128 ASSERT3U(idx, <=, tree->bt_leaf_cap);
129 ASSERT3U(idx + count, <=, tree->bt_leaf_cap);
138 zfs_btree_verify_poison_at(zfs_btree_t *tree, zfs_btree_hdr_t *hdr,
142 size_t size = tree->bt_elem_size;
151 ASSERT3U(idx, <, tree->bt_leaf_cap);
153 if (idx >= tree->bt_leaf_cap - hdr->bth_first)
177 zfs_btree_leaf_alloc(zfs_btree_t *tree)
179 if (tree->bt_leaf_size == BTREE_LEAF_SIZE)
182 return (kmem_alloc(tree->bt_leaf_size, KM_SLEEP));
186 zfs_btree_leaf_free(zfs_btree_t *tree, void *ptr)
188 if (tree->bt_leaf_size == BTREE_LEAF_SIZE)
191 return (kmem_free(ptr, tree->bt_leaf_size));
195 zfs_btree_create(zfs_btree_t *tree, int (*compar) (const void *, const void *),
198 zfs_btree_create_custom(tree, compar, bt_find_in_buf, size,
203 zfs_btree_find_in_buf(zfs_btree_t *tree, uint8_t *buf, uint32_t nelems,
207 zfs_btree_create_custom(zfs_btree_t *tree,
215 memset(tree, 0, sizeof (*tree));
216 tree->bt_compar = compar;
217 tree->bt_find_in_buf = (bt_find_in_buf == NULL) ?
219 tree->bt_elem_size = size;
220 tree->bt_leaf_size = lsize;
221 tree->bt_leaf_cap = P2ALIGN_TYPED(esize / size, 2, size_t);
222 tree->bt_height = -1;
223 tree->bt_bulk = NULL;
230 zfs_btree_find_in_buf(zfs_btree_t *tree, uint8_t *buf, uint32_t nelems,
237 uint8_t *cur = buf + idx * tree->bt_elem_size;
238 int comp = tree->bt_compar(cur, value);
256 * Find the given value in the tree. where may be passed as null to use as a
260 zfs_btree_find(zfs_btree_t *tree, const void *value, zfs_btree_index_t *where)
262 if (tree->bt_height == -1) {
267 ASSERT0(tree->bt_num_elems);
272 * If we're in bulk-insert mode, we check the last spot in the tree
273 * and the last leaf in the tree before doing the normal search,
278 size_t size = tree->bt_elem_size;
279 if (tree->bt_bulk != NULL) {
280 zfs_btree_leaf_t *last_leaf = tree->bt_bulk;
281 int comp = tree->bt_compar(last_leaf->btl_elems +
287 * element, it's not in the tree.
307 if (tree->bt_compar(last_leaf->btl_elems +
312 * it's not in the tree.
314 void *d = tree->bt_find_in_buf(tree,
332 * Iterate down the tree, finding which child the value should be in
335 for (node = (zfs_btree_core_t *)tree->bt_root; depth < tree->bt_height;
338 void *d = tree->bt_find_in_buf(tree, node->btc_elems,
354 * tree. Find its proper location and return it.
357 (zfs_btree_leaf_t *)tree->bt_root : (zfs_btree_leaf_t *)node);
358 void *d = tree->bt_find_in_buf(tree, leaf->btl_elems +
429 bt_shift_core(zfs_btree_t *tree, zfs_btree_core_t *node, uint32_t idx,
433 size_t size = tree->bt_elem_size;
456 bt_shift_core_left(zfs_btree_t *tree, zfs_btree_core_t *node, uint32_t idx,
459 bt_shift_core(tree, node, idx, count, 1, shape, BSD_LEFT);
467 bt_shift_core_right(zfs_btree_t *tree, zfs_btree_core_t *node, uint32_t idx,
470 bt_shift_core(tree, node, idx, count, 1, shape, BSD_RIGHT);
479 bt_shift_leaf(zfs_btree_t *tree, zfs_btree_leaf_t *node, uint32_t idx,
482 size_t size = tree->bt_elem_size;
498 bt_grow_leaf(zfs_btree_t *tree, zfs_btree_leaf_t *leaf, uint32_t idx,
504 uint32_t capacity = tree->bt_leaf_cap;
512 bt_shift_leaf(tree, leaf, n, idx, n, BSD_LEFT);
515 bt_shift_leaf(tree, leaf, idx, hdr->bth_count - idx, n,
522 bt_shift_leaf(tree, leaf, fn, idx, fn, BSD_LEFT);
523 bt_shift_leaf(tree, leaf, fn + idx, hdr->bth_count - idx,
533 bt_shrink_leaf(zfs_btree_t *tree, zfs_btree_leaf_t *leaf, uint32_t idx,
542 bt_shift_leaf(tree, leaf, 0, idx, n, BSD_RIGHT);
543 zfs_btree_poison_node_at(tree, hdr, 0, n);
546 bt_shift_leaf(tree, leaf, idx + n, hdr->bth_count - idx - n, n,
548 zfs_btree_poison_node_at(tree, hdr, hdr->bth_count - n, n);
558 bt_transfer_core(zfs_btree_t *tree, zfs_btree_core_t *source, uint32_t sidx,
562 size_t size = tree->bt_elem_size;
576 bt_transfer_leaf(zfs_btree_t *tree, zfs_btree_leaf_t *source, uint32_t sidx,
579 size_t size = tree->bt_elem_size;
593 zfs_btree_first_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr,
609 return (&leaf->btl_elems[node->bth_first * tree->bt_elem_size]);
614 zfs_btree_insert_core_impl(zfs_btree_t *tree, zfs_btree_core_t *parent,
617 size_t size = tree->bt_elem_size;
623 zfs_btree_verify_poison_at(tree, par_hdr,
628 bt_shift_core_right(tree, parent, offset, count,
642 zfs_btree_insert_into_parent(zfs_btree_t *tree, zfs_btree_hdr_t *old_node,
646 size_t size = tree->bt_elem_size;
651 * and increase the height of the tree.
654 ASSERT3P(old_node, ==, tree->bt_root);
655 tree->bt_num_nodes++;
669 tree->bt_height++;
670 tree->bt_root = new_root_hdr;
671 zfs_btree_poison_node(tree, new_root_hdr);
682 VERIFY3P(tree->bt_find_in_buf(tree, parent->btc_elems,
694 zfs_btree_insert_core_impl(tree, parent, offset, new_node, buf);
716 uint32_t move_count = MAX((BTREE_CORE_ELEMS / (tree->bt_bulk == NULL ?
720 tree->bt_num_nodes++;
727 zfs_btree_poison_node(tree, new_par_hdr);
731 bt_transfer_core(tree, parent, keep_count + 1, move_count, new_parent,
738 zfs_btree_poison_node(tree, par_hdr);
742 zfs_btree_insert_core_impl(tree, parent, offset, new_node,
752 zfs_btree_insert_core_impl(tree, new_parent,
765 bt_shift_core_right(tree, new_parent, 0, move_count,
772 zfs_btree_poison_node(tree, par_hdr);
784 zfs_btree_insert_into_parent(tree, &parent->btc_hdr,
790 zfs_btree_insert_leaf_impl(zfs_btree_t *tree, zfs_btree_leaf_t *leaf,
793 size_t size = tree->bt_elem_size;
795 ASSERT3U(leaf->btl_hdr.bth_count, <, tree->bt_leaf_cap);
798 zfs_btree_verify_poison_at(tree, &leaf->btl_hdr,
802 bt_grow_leaf(tree, leaf, idx, 1);
808 zfs_btree_verify_order_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr);
812 zfs_btree_insert_into_leaf(zfs_btree_t *tree, zfs_btree_leaf_t *leaf,
815 size_t size = tree->bt_elem_size;
816 uint32_t capacity = tree->bt_leaf_cap;
823 zfs_btree_insert_leaf_impl(tree, leaf, idx, value);
832 * tree stays relatively dense. Since the average state after a long
841 uint32_t move_count = MAX(capacity / (tree->bt_bulk ? 4 : 2), 1) - 1;
849 tree->bt_num_nodes++;
850 zfs_btree_leaf_t *new_leaf = zfs_btree_leaf_alloc(tree);
853 new_hdr->bth_first = (tree->bt_bulk ? 0 : capacity / 4) +
856 zfs_btree_poison_node(tree, new_hdr);
858 if (tree->bt_bulk != NULL && leaf == tree->bt_bulk)
859 tree->bt_bulk = new_leaf;
862 bt_transfer_leaf(tree, leaf, keep_count + 1, move_count, new_leaf, 0);
869 bt_shrink_leaf(tree, leaf, keep_count, 1 + move_count);
873 zfs_btree_insert_leaf_impl(tree, leaf, idx, value);
876 zfs_btree_insert_leaf_impl(tree, new_leaf, idx - keep_count -
883 zfs_btree_insert_leaf_impl(tree, new_leaf, 0, buf);
891 zfs_btree_insert_into_parent(tree, &leaf->btl_hdr, &new_leaf->btl_hdr,
897 zfs_btree_find_parent_idx(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
904 hdr->bth_first * tree->bt_elem_size;
908 VERIFY3P(tree->bt_find_in_buf(tree, parent->btc_elems,
917 * Take the b-tree out of bulk insert mode. During bulk-insert mode, some
926 zfs_btree_bulk_finish(zfs_btree_t *tree)
928 ASSERT3P(tree->bt_bulk, !=, NULL);
929 ASSERT3P(tree->bt_root, !=, NULL);
930 zfs_btree_leaf_t *leaf = tree->bt_bulk;
933 size_t size = tree->bt_elem_size;
934 uint32_t capacity = tree->bt_leaf_cap;
938 * node in the tree we're done.
941 tree->bt_bulk = NULL;
958 VERIFY3P(zfs_btree_prev(tree, &idx, &idx), !=, NULL);
963 VERIFY3P(zfs_btree_prev(tree, &idx, &idx), !=, NULL);
973 zfs_btree_verify_poison_at(tree, hdr,
979 bt_grow_leaf(tree, leaf, 0, move_count);
991 bt_transfer_leaf(tree, l_neighbor, l_hdr->bth_count -
1002 bt_shrink_leaf(tree, l_neighbor, l_hdr->bth_count - move_count,
1030 uint32_t parent_idx = zfs_btree_find_parent_idx(tree, hdr);
1040 zfs_btree_verify_poison_at(tree, hdr,
1045 bt_shift_core(tree, cur, 0, hdr->bth_count, move_count,
1060 bt_transfer_core(tree, l_neighbor, move_idx, move_count, cur, 0,
1076 zfs_btree_poison_node(tree, &l_neighbor->btc_hdr);
1082 tree->bt_bulk = NULL;
1083 zfs_btree_verify(tree);
1087 * Insert value into tree at the location specified by where.
1090 zfs_btree_add_idx(zfs_btree_t *tree, const void *value,
1096 if (tree->bt_bulk != NULL) {
1097 if (where->bti_node != &tree->bt_bulk->btl_hdr) {
1098 zfs_btree_bulk_finish(tree);
1099 VERIFY3P(zfs_btree_find(tree, value, &idx), ==, NULL);
1104 tree->bt_num_elems++;
1106 * If this is the first element in the tree, create a leaf root node
1110 ASSERT3U(tree->bt_num_elems, ==, 1);
1111 ASSERT3S(tree->bt_height, ==, -1);
1112 ASSERT3P(tree->bt_root, ==, NULL);
1115 tree->bt_num_nodes++;
1116 zfs_btree_leaf_t *leaf = zfs_btree_leaf_alloc(tree);
1117 tree->bt_root = &leaf->btl_hdr;
1118 tree->bt_height++;
1124 zfs_btree_poison_node(tree, hdr);
1126 zfs_btree_insert_into_leaf(tree, leaf, value, 0);
1127 tree->bt_bulk = leaf;
1133 zfs_btree_insert_into_leaf(tree,
1152 size_t size = tree->bt_elem_size;
1162 VERIFY3P(zfs_btree_first_helper(tree, subtree, &new_idx), !=,
1166 zfs_btree_insert_into_leaf(tree,
1170 zfs_btree_verify(tree);
1174 * Return the first element in the tree, and put its location in where if
1178 zfs_btree_first(zfs_btree_t *tree, zfs_btree_index_t *where)
1180 if (tree->bt_height == -1) {
1181 ASSERT0(tree->bt_num_elems);
1184 return (zfs_btree_first_helper(tree, tree->bt_root, where));
1212 * Return the last element in the tree, and put its location in where if
1216 zfs_btree_last(zfs_btree_t *tree, zfs_btree_index_t *where)
1218 if (tree->bt_height == -1) {
1219 ASSERT0(tree->bt_num_elems);
1222 return (zfs_btree_last_helper(tree, tree->bt_root, where));
1226 * This function contains the logic to find the next node in the tree. A
1232 zfs_btree_next_helper(zfs_btree_t *tree, const zfs_btree_index_t *idx,
1237 ASSERT3S(tree->bt_height, ==, -1);
1259 new_off) * tree->bt_elem_size);
1267 uint32_t i = zfs_btree_find_parent_idx(tree, prev);
1269 done_func(tree, prev);
1277 return (node->btc_elems + i * tree->bt_elem_size);
1280 done_func(tree, prev);
1283 * node every time, so this was the last element in the tree.
1293 return (node->btc_elems + offset * tree->bt_elem_size);
1301 return (zfs_btree_first_helper(tree, child, out_idx));
1305 * Return the next valued node in the tree. The same address can be safely
1309 zfs_btree_next(zfs_btree_t *tree, const zfs_btree_index_t *idx,
1312 return (zfs_btree_next_helper(tree, idx, out_idx, NULL));
1316 * Return the previous valued node in the tree. The same value can be safely
1320 zfs_btree_prev(zfs_btree_t *tree, const zfs_btree_index_t *idx,
1324 ASSERT3S(tree->bt_height, ==, -1);
1345 offset - 1) * tree->bt_elem_size);
1352 uint32_t i = zfs_btree_find_parent_idx(tree, prev);
1360 return (node->btc_elems + (i - 1) * tree->bt_elem_size);
1364 * node every time, so this was the first node in the tree.
1376 return (zfs_btree_last_helper(tree, child, out_idx));
1380 * Get the value at the provided index in the tree.
1384 * elements that could be in the tree.
1387 zfs_btree_get(zfs_btree_t *tree, zfs_btree_index_t *idx)
1390 size_t size = tree->bt_elem_size;
1400 /* Add the given value to the tree. Must not already be in the tree. */
1402 zfs_btree_add(zfs_btree_t *tree, const void *node)
1405 VERIFY3P(zfs_btree_find(tree, node, &where), ==, NULL);
1406 zfs_btree_add_idx(tree, node, &where);
1409 /* Helper function to free a tree node. */
1411 zfs_btree_node_destroy(zfs_btree_t *tree, zfs_btree_hdr_t *node)
1413 tree->bt_num_nodes--;
1415 zfs_btree_leaf_free(tree, node);
1418 BTREE_CORE_ELEMS * tree->bt_elem_size);
1428 zfs_btree_remove_from_node(zfs_btree_t *tree, zfs_btree_core_t *node,
1431 size_t size = tree->bt_elem_size;
1440 ASSERT3P(tree->bt_root, ==, node);
1442 tree->bt_root = node->btc_children[0];
1444 zfs_btree_node_destroy(tree, hdr);
1445 tree->bt_height--;
1466 bt_shift_core_left(tree, node, idx, hdr->bth_count - idx,
1469 zfs_btree_poison_node_at(tree, hdr, hdr->bth_count, 1);
1490 uint32_t parent_idx = zfs_btree_find_parent_idx(tree, hdr);
1503 bt_shift_core_right(tree, node, 0, idx - 1, BSS_TRAPEZOID);
1523 zfs_btree_poison_node_at(tree, l_hdr, l_hdr->bth_count, 1);
1538 bt_shift_core_left(tree, node, idx, hdr->bth_count - idx,
1565 bt_shift_core_left(tree, neighbor, 1, r_hdr->bth_count,
1567 zfs_btree_poison_node_at(tree, r_hdr, r_hdr->bth_count, 1);
1602 zfs_btree_verify_poison_at(tree, keep_hdr,
1615 bt_transfer_core(tree, rm, 0, new_rm_hdr->bth_count, keep,
1629 bt_shift_core_left(tree, keep, new_idx, keep_hdr->bth_count - new_idx,
1642 zfs_btree_poison_node_at(tree, keep_hdr, keep_hdr->bth_count, 1);
1645 zfs_btree_remove_from_node(tree, parent, new_rm_hdr);
1646 zfs_btree_node_destroy(tree, new_rm_hdr);
1651 zfs_btree_remove_idx(zfs_btree_t *tree, zfs_btree_index_t *where)
1653 size_t size = tree->bt_elem_size;
1658 if (tree->bt_bulk != NULL) {
1661 * invalid after we correct the tree, so we copy the value
1665 uint8_t *value = zfs_btree_get(tree, where);
1668 zfs_btree_bulk_finish(tree);
1669 VERIFY3P(zfs_btree_find(tree, tmp, where), !=, NULL);
1675 tree->bt_num_elems--;
1685 void *new_value = zfs_btree_last_helper(tree, left_subtree,
1705 uint32_t min_count = (tree->bt_leaf_cap / 2) - 1;
1712 bt_shrink_leaf(tree, leaf, idx, 1);
1714 ASSERT0(tree->bt_height);
1716 tree->bt_root = NULL;
1717 tree->bt_height--;
1718 zfs_btree_node_destroy(tree, &leaf->btl_hdr);
1721 zfs_btree_verify(tree);
1740 uint32_t parent_idx = zfs_btree_find_parent_idx(tree, hdr);
1753 bt_shift_leaf(tree, leaf, 0, idx, 1, BSD_RIGHT);
1766 bt_shrink_leaf(tree, neighbor, l_hdr->bth_count - 1, 1);
1767 zfs_btree_verify(tree);
1783 bt_shift_leaf(tree, leaf, idx + 1, hdr->bth_count - idx - 1,
1797 bt_shrink_leaf(tree, neighbor, 0, 1);
1798 zfs_btree_verify(tree);
1831 zfs_btree_verify_poison_at(tree, k_hdr,
1840 bt_shrink_leaf(tree, leaf, idx, 1);
1844 bt_grow_leaf(tree, keep, k_count, 1 + rm_hdr->bth_count);
1853 bt_transfer_leaf(tree, rm, 0, rm_hdr->bth_count, keep, k_count + 1);
1856 zfs_btree_remove_from_node(tree, parent, rm_hdr);
1857 zfs_btree_node_destroy(tree, rm_hdr);
1858 zfs_btree_verify(tree);
1861 /* Remove the given value from the tree. */
1863 zfs_btree_remove(zfs_btree_t *tree, const void *value)
1866 VERIFY3P(zfs_btree_find(tree, value, &where), !=, NULL);
1867 zfs_btree_remove_idx(tree, &where);
1870 /* Return the number of elements in the tree. */
1872 zfs_btree_numnodes(zfs_btree_t *tree)
1874 return (tree->bt_num_elems);
1878 * This function is used to visit all the elements in the tree before
1879 * destroying the tree. This allows the calling code to perform any cleanup it
1890 * while ((node = zfs_btree_destroy_nodes(tree, &cookie)) != NULL)
1892 * zfs_btree_destroy(tree);
1896 zfs_btree_destroy_nodes(zfs_btree_t *tree, zfs_btree_index_t **cookie)
1899 if (tree->bt_height == -1)
1902 return (zfs_btree_first(tree, *cookie));
1905 void *rval = zfs_btree_next_helper(tree, *cookie, *cookie,
1908 tree->bt_root = NULL;
1909 tree->bt_height = -1;
1910 tree->bt_num_elems = 0;
1912 tree->bt_bulk = NULL;
1918 zfs_btree_clear_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
1923 zfs_btree_clear_helper(tree, btc->btc_children[i]);
1926 zfs_btree_node_destroy(tree, hdr);
1930 zfs_btree_clear(zfs_btree_t *tree)
1932 if (tree->bt_root == NULL) {
1933 ASSERT0(tree->bt_num_elems);
1937 zfs_btree_clear_helper(tree, tree->bt_root);
1938 tree->bt_num_elems = 0;
1939 tree->bt_root = NULL;
1940 tree->bt_num_nodes = 0;
1941 tree->bt_height = -1;
1942 tree->bt_bulk = NULL;
1946 zfs_btree_destroy(zfs_btree_t *tree)
1948 ASSERT0(tree->bt_num_elems);
1949 ASSERT3P(tree->bt_root, ==, NULL);
1954 zfs_btree_verify_pointers_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
1962 zfs_btree_verify_pointers_helper(tree, node->btc_children[i]);
1968 zfs_btree_verify_pointers(zfs_btree_t *tree)
1970 if (tree->bt_height == -1) {
1971 VERIFY3P(tree->bt_root, ==, NULL);
1974 VERIFY3P(tree->bt_root->bth_parent, ==, NULL);
1975 zfs_btree_verify_pointers_helper(tree, tree->bt_root);
1983 zfs_btree_verify_counts_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
1986 if (tree->bt_root != hdr && tree->bt_bulk &&
1987 hdr != &tree->bt_bulk->btl_hdr) {
1988 VERIFY3U(hdr->bth_count, >=, tree->bt_leaf_cap / 2 - 1);
1996 if (tree->bt_root != hdr && tree->bt_bulk == NULL)
1999 ret += zfs_btree_verify_counts_helper(tree,
2012 zfs_btree_verify_counts(zfs_btree_t *tree)
2014 EQUIV(tree->bt_num_elems == 0, tree->bt_height == -1);
2015 if (tree->bt_height == -1) {
2018 VERIFY3P(zfs_btree_verify_counts_helper(tree, tree->bt_root), ==,
2019 tree->bt_num_elems);
2027 zfs_btree_verify_height_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr,
2038 ret += zfs_btree_verify_height_helper(tree,
2045 * Check that the tree rooted at this node has a uniform height, and that the
2046 * bt_height in the tree is correct.
2049 zfs_btree_verify_height(zfs_btree_t *tree)
2051 EQUIV(tree->bt_height == -1, tree->bt_root == NULL);
2052 if (tree->bt_height == -1) {
2056 VERIFY3U(zfs_btree_verify_height_helper(tree, tree->bt_root,
2057 tree->bt_height), ==, tree->bt_num_nodes);
2066 zfs_btree_verify_order_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
2068 size_t size = tree->bt_elem_size;
2072 VERIFY3S(tree->bt_compar(leaf->btl_elems +
2082 VERIFY3S(tree->bt_compar(node->btc_elems + (i - 1) * size,
2100 int comp = tree->bt_compar(node->btc_elems + i * size,
2120 comp = tree->bt_compar(node->btc_elems + i * size,
2129 zfs_btree_verify_order_helper(tree, node->btc_children[i]);
2132 /* Check that all elements in the tree are in sorted order. */
2134 zfs_btree_verify_order(zfs_btree_t *tree)
2136 EQUIV(tree->bt_height == -1, tree->bt_root == NULL);
2137 if (tree->bt_height == -1) {
2141 zfs_btree_verify_order_helper(tree, tree->bt_root);
2147 zfs_btree_verify_poison_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)
2149 size_t size = tree->bt_elem_size;
2154 size_t esize = tree->bt_leaf_size -
2172 zfs_btree_verify_poison_helper(tree,
2179 /* Check that unused memory in the tree is still poisoned. */
2181 zfs_btree_verify_poison(zfs_btree_t *tree)
2184 if (tree->bt_height == -1)
2186 zfs_btree_verify_poison_helper(tree, tree->bt_root);
2191 zfs_btree_verify(zfs_btree_t *tree)
2195 zfs_btree_verify_height(tree);
2198 zfs_btree_verify_pointers(tree);
2201 zfs_btree_verify_counts(tree);
2204 zfs_btree_verify_order(tree);
2208 zfs_btree_verify_poison(tree);