75 zfs_btree_is_core(struct zfs_btree_hdr *hdr)  in zfs_btree_is_core()  argument
77 	return (hdr->bth_first == -1);  in zfs_btree_is_core()
87 zfs_btree_poison_node(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)  in zfs_btree_poison_node()  argument
91 	if (zfs_btree_is_core(hdr)) {  in zfs_btree_poison_node()
92 		zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;  in zfs_btree_poison_node()
93 		for (uint32_t i = hdr->bth_count + 1; i <= BTREE_CORE_ELEMS;  in zfs_btree_poison_node()
98 		(void) memset(node->btc_elems + hdr->bth_count * size, 0x0f,  in zfs_btree_poison_node()
99 		    (BTREE_CORE_ELEMS - hdr->bth_count) * size);  in zfs_btree_poison_node()
101 		zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;  in zfs_btree_poison_node()
102 		(void) memset(leaf->btl_elems, 0x0f, hdr->bth_first * size);  in zfs_btree_poison_node()
104 		    (hdr->bth_first + hdr->bth_count) * size, 0x0f,  in zfs_btree_poison_node()
106 		    (hdr->bth_first + hdr->bth_count) * size);  in zfs_btree_poison_node()
112 zfs_btree_poison_node_at(zfs_btree_t *tree, zfs_btree_hdr_t *hdr,  in zfs_btree_poison_node_at()  argument
117 	if (zfs_btree_is_core(hdr)) {  in zfs_btree_poison_node_at()
118 		ASSERT3U(idx, >=, hdr->bth_count);  in zfs_btree_poison_node_at()
121 		zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;  in zfs_btree_poison_node_at()
130 		zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;  in zfs_btree_poison_node_at()
132 		    (hdr->bth_first + idx) * size, 0x0f, count * size);  in zfs_btree_poison_node_at()
138 zfs_btree_verify_poison_at(zfs_btree_t *tree, zfs_btree_hdr_t *hdr,  in zfs_btree_verify_poison_at()  argument
143 	if (zfs_btree_is_core(hdr)) {  in zfs_btree_verify_poison_at()
145 		zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;  in zfs_btree_verify_poison_at()
152 		zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;  in zfs_btree_verify_poison_at()
153 		if (idx >= tree->bt_leaf_cap - hdr->bth_first)  in zfs_btree_verify_poison_at()
156 			VERIFY3U(leaf->btl_elems[(hdr->bth_first + idx)  in zfs_btree_verify_poison_at()
447 	zfs_btree_hdr_t *hdr = &node->btl_hdr;  in bt_shift_leaf()  local
448 	ASSERT(!zfs_btree_is_core(hdr));  in bt_shift_leaf()
452 	uint8_t *start = node->btl_elems + (hdr->bth_first + idx) * size;  in bt_shift_leaf()
465 	zfs_btree_hdr_t *hdr = &leaf->btl_hdr;  in bt_grow_leaf()  local
466 	ASSERT(!zfs_btree_is_core(hdr));  in bt_grow_leaf()
467 	ASSERT3U(idx, <=, hdr->bth_count);  in bt_grow_leaf()
469 	ASSERT3U(hdr->bth_count + n, <=, capacity);  in bt_grow_leaf()
470 	boolean_t cl = (hdr->bth_first >= n);  in bt_grow_leaf()
471 	boolean_t cr = (hdr->bth_first + hdr->bth_count + n <= capacity);  in bt_grow_leaf()
473 	if (cl && (!cr || idx <= hdr->bth_count / 2)) {  in bt_grow_leaf()
475 		hdr->bth_first -= n;  in bt_grow_leaf()
479 		bt_shift_leaf(tree, leaf, idx, hdr->bth_count - idx, n,  in bt_grow_leaf()
483 		uint32_t fn = hdr->bth_first -  in bt_grow_leaf()
484 		    (capacity - (hdr->bth_count + n)) / 2;  in bt_grow_leaf()
485 		hdr->bth_first -= fn;  in bt_grow_leaf()
487 		bt_shift_leaf(tree, leaf, fn + idx, hdr->bth_count - idx,  in bt_grow_leaf()
490 	hdr->bth_count += n;  in bt_grow_leaf()
500 	zfs_btree_hdr_t *hdr = &leaf->btl_hdr;  in bt_shrink_leaf()  local
501 	ASSERT(!zfs_btree_is_core(hdr));  in bt_shrink_leaf()
502 	ASSERT3U(idx, <=, hdr->bth_count);  in bt_shrink_leaf()
503 	ASSERT3U(idx + n, <=, hdr->bth_count);  in bt_shrink_leaf()
505 	if (idx <= (hdr->bth_count - n) / 2) {  in bt_shrink_leaf()
507 		zfs_btree_poison_node_at(tree, hdr, 0, n);  in bt_shrink_leaf()
508 		hdr->bth_first += n;  in bt_shrink_leaf()
510 		bt_shift_leaf(tree, leaf, idx + n, hdr->bth_count - idx - n, n,  in bt_shrink_leaf()
512 		zfs_btree_poison_node_at(tree, hdr, hdr->bth_count - n, n);  in bt_shrink_leaf()
514 	hdr->bth_count -= n;  in bt_shrink_leaf()
557 zfs_btree_first_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr,  in zfs_btree_first_helper()  argument
562 	for (node = hdr; zfs_btree_is_core(node);  in zfs_btree_first_helper()
758 	zfs_btree_hdr_t *hdr = &leaf->btl_hdr;  in zfs_btree_insert_leaf_impl()  local
767 	uint8_t *start = leaf->btl_elems + (hdr->bth_first + idx) * size;  in zfs_btree_insert_leaf_impl()
772 zfs_btree_verify_order_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr);
862 zfs_btree_find_parent_idx(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)  in zfs_btree_find_parent_idx()  argument
865 	if (zfs_btree_is_core(hdr)) {  in zfs_btree_find_parent_idx()
866 		buf = ((zfs_btree_core_t *)hdr)->btc_elems;  in zfs_btree_find_parent_idx()
868 		buf = ((zfs_btree_leaf_t *)hdr)->btl_elems +  in zfs_btree_find_parent_idx()
869 		    hdr->bth_first * tree->bt_elem_size;  in zfs_btree_find_parent_idx()
872 	zfs_btree_core_t *parent = hdr->bth_parent;  in zfs_btree_find_parent_idx()
877 	ASSERT3P(parent->btc_children[idx.bti_offset], ==, hdr);  in zfs_btree_find_parent_idx()
896 	zfs_btree_hdr_t *hdr = &leaf->btl_hdr;  in zfs_btree_bulk_finish()  local
897 	zfs_btree_core_t *parent = hdr->bth_parent;  in zfs_btree_bulk_finish()
911 	if (hdr->bth_count < capacity / 2) {  in zfs_btree_bulk_finish()
920 			.bti_node = hdr,  in zfs_btree_bulk_finish()
932 		uint32_t move_count = (capacity / 2) - hdr->bth_count;  in zfs_btree_bulk_finish()
938 				zfs_btree_verify_poison_at(tree, hdr,  in zfs_btree_bulk_finish()
949 		    (hdr->bth_first + move_count - 1) * size;  in zfs_btree_bulk_finish()
971 		ASSERT3U(hdr->bth_count, >=, capacity / 2);  in zfs_btree_bulk_finish()
981 		zfs_btree_hdr_t *hdr = &cur->btc_hdr;  in zfs_btree_bulk_finish()  local
982 		parent = hdr->bth_parent;  in zfs_btree_bulk_finish()
987 		if (hdr->bth_count >= capacity / 2)  in zfs_btree_bulk_finish()
995 		uint32_t parent_idx = zfs_btree_find_parent_idx(tree, hdr);  in zfs_btree_bulk_finish()
999 		uint32_t move_count = (capacity / 2) - hdr->bth_count;  in zfs_btree_bulk_finish()
1005 				zfs_btree_verify_poison_at(tree, hdr,  in zfs_btree_bulk_finish()
1006 				    hdr->bth_count + i);  in zfs_btree_bulk_finish()
1010 		bt_shift_core(tree, cur, 0, hdr->bth_count, move_count,  in zfs_btree_bulk_finish()
1036 		hdr->bth_count += move_count + 1;  in zfs_btree_bulk_finish()
1039 		ASSERT3U(hdr->bth_count, >=, capacity / 2);  in zfs_btree_bulk_finish()
1043 		for (uint32_t i = 0; i <= hdr->bth_count; i++)  in zfs_btree_bulk_finish()
1086 		zfs_btree_hdr_t *hdr = &leaf->btl_hdr;  in zfs_btree_add_idx()  local
1087 		hdr->bth_parent = NULL;  in zfs_btree_add_idx()
1088 		hdr->bth_first = 0;  in zfs_btree_add_idx()
1089 		hdr->bth_count = 0;  in zfs_btree_add_idx()
1090 		zfs_btree_poison_node(tree, hdr);  in zfs_btree_add_idx()
1158 zfs_btree_last_helper(zfs_btree_t *btree, zfs_btree_hdr_t *hdr,  in zfs_btree_last_helper()  argument
1163 	for (node = hdr; zfs_btree_is_core(node); node =  in zfs_btree_last_helper()
1231 			zfs_btree_hdr_t *hdr = &node->btc_hdr;  in zfs_btree_next_helper()  local
1232 			ASSERT(zfs_btree_is_core(hdr));  in zfs_btree_next_helper()
1236 			if (i == hdr->bth_count) {  in zfs_btree_next_helper()
1237 				prev = hdr;  in zfs_btree_next_helper()
1240 			out_idx->bti_node = hdr;  in zfs_btree_next_helper()
1316 			zfs_btree_hdr_t *hdr = &node->btc_hdr;  in zfs_btree_prev()  local
1317 			ASSERT(zfs_btree_is_core(hdr));  in zfs_btree_prev()
1320 				prev = hdr;  in zfs_btree_prev()
1323 			out_idx->bti_node = hdr;  in zfs_btree_prev()
1399 	zfs_btree_hdr_t *hdr = &node->btc_hdr;  in zfs_btree_remove_from_node()  local
1404 	if (hdr->bth_parent == NULL && hdr->bth_count <= 1) {  in zfs_btree_remove_from_node()
1405 		ASSERT3U(hdr->bth_count, ==, 1);  in zfs_btree_remove_from_node()
1410 		zfs_btree_node_destroy(tree, hdr);  in zfs_btree_remove_from_node()
1416 	for (idx = 0; idx <= hdr->bth_count; idx++) {  in zfs_btree_remove_from_node()
1420 	ASSERT3U(idx, <=, hdr->bth_count);  in zfs_btree_remove_from_node()
1426 	if (hdr->bth_parent == NULL ||  in zfs_btree_remove_from_node()
1427 	    hdr->bth_count > min_count) {  in zfs_btree_remove_from_node()
1432 		bt_shift_core_left(tree, node, idx, hdr->bth_count - idx,  in zfs_btree_remove_from_node()
1434 		hdr->bth_count--;  in zfs_btree_remove_from_node()
1435 		zfs_btree_poison_node_at(tree, hdr, hdr->bth_count, 1);  in zfs_btree_remove_from_node()
1439 	ASSERT3U(hdr->bth_count, ==, min_count);  in zfs_btree_remove_from_node()
1455 	zfs_btree_core_t *parent = hdr->bth_parent;  in zfs_btree_remove_from_node()
1456 	uint32_t parent_idx = zfs_btree_find_parent_idx(tree, hdr);  in zfs_btree_remove_from_node()
1504 		bt_shift_core_left(tree, node, idx, hdr->bth_count - idx,  in zfs_btree_remove_from_node()
1512 		bcpy(separator, node->btc_elems + (hdr->bth_count - 1) * size,  in zfs_btree_remove_from_node()
1519 		node->btc_children[hdr->bth_count] = neighbor->btc_children[0];  in zfs_btree_remove_from_node()
1520 		node->btc_children[hdr->bth_count]->bth_parent = node;  in zfs_btree_remove_from_node()
1551 		new_rm_hdr = hdr;  in zfs_btree_remove_from_node()
1555 		keep_hdr = hdr;  in zfs_btree_remove_from_node()
1620 	zfs_btree_hdr_t *hdr = where->bti_node;  in zfs_btree_remove_idx()  local
1637 		hdr = where->bti_node;  in zfs_btree_remove_idx()
1648 	if (zfs_btree_is_core(hdr)) {  in zfs_btree_remove_idx()
1649 		zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;  in zfs_btree_remove_idx()
1657 		hdr = where->bti_node;  in zfs_btree_remove_idx()
1667 	ASSERT(!zfs_btree_is_core(hdr));  in zfs_btree_remove_idx()
1668 	zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;  in zfs_btree_remove_idx()
1669 	ASSERT3U(hdr->bth_count, >, 0);  in zfs_btree_remove_idx()
1677 	if (hdr->bth_count > min_count || hdr->bth_parent == NULL) {  in zfs_btree_remove_idx()
1679 		if (hdr->bth_parent == NULL) {  in zfs_btree_remove_idx()
1681 			if (hdr->bth_count == 0) {  in zfs_btree_remove_idx()
1690 	ASSERT3U(hdr->bth_count, ==, min_count);  in zfs_btree_remove_idx()
1705 	zfs_btree_core_t *parent = hdr->bth_parent;  in zfs_btree_remove_idx()
1706 	uint32_t parent_idx = zfs_btree_find_parent_idx(tree, hdr);  in zfs_btree_remove_idx()
1724 		bcpy(separator, leaf->btl_elems + hdr->bth_first * size, size);  in zfs_btree_remove_idx()
1749 		bt_shift_leaf(tree, leaf, idx + 1, hdr->bth_count - idx - 1,  in zfs_btree_remove_idx()
1754 		bcpy(separator, leaf->btl_elems + (hdr->bth_first +  in zfs_btree_remove_idx()
1755 		    hdr->bth_count - 1) * size, size);  in zfs_btree_remove_idx()
1781 		rm_hdr = hdr;  in zfs_btree_remove_idx()
1784 		k_hdr = hdr;  in zfs_btree_remove_idx()
1884 zfs_btree_clear_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)  in zfs_btree_clear_helper()  argument
1886 	if (zfs_btree_is_core(hdr)) {  in zfs_btree_clear_helper()
1887 		zfs_btree_core_t *btc = (zfs_btree_core_t *)hdr;  in zfs_btree_clear_helper()
1888 		for (uint32_t i = 0; i <= hdr->bth_count; i++)  in zfs_btree_clear_helper()
1892 	zfs_btree_node_destroy(tree, hdr);  in zfs_btree_clear_helper()
1920 zfs_btree_verify_pointers_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)  in zfs_btree_verify_pointers_helper()  argument
1922 	if (!zfs_btree_is_core(hdr))  in zfs_btree_verify_pointers_helper()
1925 	zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;  in zfs_btree_verify_pointers_helper()
1926 	for (uint32_t i = 0; i <= hdr->bth_count; i++) {  in zfs_btree_verify_pointers_helper()
1927 		VERIFY3P(node->btc_children[i]->bth_parent, ==, hdr);  in zfs_btree_verify_pointers_helper()
1949 zfs_btree_verify_counts_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)  in zfs_btree_verify_counts_helper()  argument
1951 	if (!zfs_btree_is_core(hdr)) {  in zfs_btree_verify_counts_helper()
1952 		if (tree->bt_root != hdr && tree->bt_bulk &&  in zfs_btree_verify_counts_helper()
1953 		    hdr != &tree->bt_bulk->btl_hdr) {  in zfs_btree_verify_counts_helper()
1954 			VERIFY3U(hdr->bth_count, >=, tree->bt_leaf_cap / 2 - 1);  in zfs_btree_verify_counts_helper()
1957 		return (hdr->bth_count);  in zfs_btree_verify_counts_helper()
1960 		zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;  in zfs_btree_verify_counts_helper()
1961 		uint64_t ret = hdr->bth_count;  in zfs_btree_verify_counts_helper()
1962 		if (tree->bt_root != hdr && tree->bt_bulk == NULL)  in zfs_btree_verify_counts_helper()
1963 			VERIFY3P(hdr->bth_count, >=, BTREE_CORE_ELEMS / 2 - 1);  in zfs_btree_verify_counts_helper()
1964 		for (uint32_t i = 0; i <= hdr->bth_count; i++) {  in zfs_btree_verify_counts_helper()
1993 zfs_btree_verify_height_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr,  in zfs_btree_verify_height_helper()  argument
1996 	if (!zfs_btree_is_core(hdr)) {  in zfs_btree_verify_height_helper()
2001 	zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;  in zfs_btree_verify_height_helper()
2003 	for (uint32_t i = 0; i <= hdr->bth_count; i++) {  in zfs_btree_verify_height_helper()
2032 zfs_btree_verify_order_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)  in zfs_btree_verify_order_helper()  argument
2035 	if (!zfs_btree_is_core(hdr)) {  in zfs_btree_verify_order_helper()
2036 		zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;  in zfs_btree_verify_order_helper()
2037 		for (uint32_t i = 1; i < hdr->bth_count; i++) {  in zfs_btree_verify_order_helper()
2039 			    (hdr->bth_first + i - 1) * size,  in zfs_btree_verify_order_helper()
2041 			    (hdr->bth_first + i) * size), ==, -1);  in zfs_btree_verify_order_helper()
2046 	zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;  in zfs_btree_verify_order_helper()
2047 	for (uint32_t i = 1; i < hdr->bth_count; i++) {  in zfs_btree_verify_order_helper()
2051 	for (uint32_t i = 0; i < hdr->bth_count; i++) {  in zfs_btree_verify_order_helper()
2094 	for (uint32_t i = 0; i <= hdr->bth_count; i++)  in zfs_btree_verify_order_helper()
2113 zfs_btree_verify_poison_helper(zfs_btree_t *tree, zfs_btree_hdr_t *hdr)  in zfs_btree_verify_poison_helper()  argument
2116 	if (!zfs_btree_is_core(hdr)) {  in zfs_btree_verify_poison_helper()
2117 		zfs_btree_leaf_t *leaf = (zfs_btree_leaf_t *)hdr;  in zfs_btree_verify_poison_helper()
2118 		for (size_t i = 0; i < hdr->bth_first * size; i++)  in zfs_btree_verify_poison_helper()
2120 		for (size_t i = (hdr->bth_first + hdr->bth_count) * size;  in zfs_btree_verify_poison_helper()
2124 		zfs_btree_core_t *node = (zfs_btree_core_t *)hdr;  in zfs_btree_verify_poison_helper()
2125 		for (size_t i = hdr->bth_count * size;  in zfs_btree_verify_poison_helper()
2129 		for (uint32_t i = hdr->bth_count + 1; i <= BTREE_CORE_ELEMS;  in zfs_btree_verify_poison_helper()
2135 		for (uint32_t i = 0; i <= hdr->bth_count; i++) {  in zfs_btree_verify_poison_helper()