10713e23George Wilson/*
20713e23George Wilson * CDDL HEADER START
30713e23George Wilson *
40713e23George Wilson * The contents of this file are subject to the terms of the
50713e23George Wilson * Common Development and Distribution License (the "License").
60713e23George Wilson * You may not use this file except in compliance with the License.
70713e23George Wilson *
80713e23George Wilson * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
90713e23George Wilson * or http://www.opensolaris.org/os/licensing.
100713e23George Wilson * See the License for the specific language governing permissions
110713e23George Wilson * and limitations under the License.
120713e23George Wilson *
130713e23George Wilson * When distributing Covered Code, include this CDDL HEADER in each
140713e23George Wilson * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
150713e23George Wilson * If applicable, add the following below this CDDL HEADER, with the
160713e23George Wilson * fields enclosed by brackets "[]" replaced with your own identifying
170713e23George Wilson * information: Portions Copyright [yyyy] [name of copyright owner]
180713e23George Wilson *
190713e23George Wilson * CDDL HEADER END
200713e23George Wilson */
210713e23George Wilson/*
220713e23George Wilson * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
230713e23George Wilson * Use is subject to license terms.
240713e23George Wilson */
250713e23George Wilson/*
26814dcd4Serapheim Dimitropoulos * Copyright (c) 2013, 2019 by Delphix. All rights reserved.
270713e23George Wilson */
280713e23George Wilson
290713e23George Wilson#include <sys/zfs_context.h>
300713e23George Wilson#include <sys/spa.h>
310713e23George Wilson#include <sys/dmu.h>
320713e23George Wilson#include <sys/dnode.h>
330713e23George Wilson#include <sys/zio.h>
340713e23George Wilson#include <sys/range_tree.h>
350713e23George Wilson
36a3874b8Toomas Soome/*
37a3874b8Toomas Soome * Range trees are tree-based data structures that can be used to
38a3874b8Toomas Soome * track free space or generally any space allocation information.
39a3874b8Toomas Soome * A range tree keeps track of individual segments and automatically
40a3874b8Toomas Soome * provides facilities such as adjacent extent merging and extent
41a3874b8Toomas Soome * splitting in response to range add/remove requests.
42a3874b8Toomas Soome *
43a3874b8Toomas Soome * A range tree starts out completely empty, with no segments in it.
44a3874b8Toomas Soome * Adding an allocation via range_tree_add to the range tree can either:
45a3874b8Toomas Soome * 1) create a new extent
46a3874b8Toomas Soome * 2) extend an adjacent extent
47a3874b8Toomas Soome * 3) merge two adjacent extents
48a3874b8Toomas Soome * Conversely, removing an allocation via range_tree_remove can:
49a3874b8Toomas Soome * 1) completely remove an extent
50a3874b8Toomas Soome * 2) shorten an extent (if the allocation was near one of its ends)
51a3874b8Toomas Soome * 3) split an extent into two extents, in effect punching a hole
52a3874b8Toomas Soome *
53a3874b8Toomas Soome * A range tree is also capable of 'bridging' gaps when adding
54a3874b8Toomas Soome * allocations. This is useful for cases when close proximity of
55a3874b8Toomas Soome * allocations is an important detail that needs to be represented
56a3874b8Toomas Soome * in the range tree. See range_tree_set_gap(). The default behavior
57a3874b8Toomas Soome * is not to bridge gaps (i.e. the maximum allowed gap size is 0).
58a3874b8Toomas Soome *
59a3874b8Toomas Soome * In order to traverse a range tree, use either the range_tree_walk()
60a3874b8Toomas Soome * or range_tree_vacate() functions.
61a3874b8Toomas Soome *
62a3874b8Toomas Soome * To obtain more accurate information on individual segment
63a3874b8Toomas Soome * operations that the range tree performs "under the hood", you can
64a3874b8Toomas Soome * specify a set of callbacks by passing a range_tree_ops_t structure
65a3874b8Toomas Soome * to the range_tree_create function. Any callbacks that are non-NULL
66a3874b8Toomas Soome * are then called at the appropriate times.
67a3874b8Toomas Soome *
68a3874b8Toomas Soome * The range tree code also supports a special variant of range trees
69a3874b8Toomas Soome * that can bridge small gaps between segments. This kind of tree is used
70a3874b8Toomas Soome * by the dsl scanning code to group I/Os into mostly sequential chunks to
71a3874b8Toomas Soome * optimize disk performance. The code here attempts to do this with as
72a3874b8Toomas Soome * little memory and computational overhead as possible. One limitation of
73a3874b8Toomas Soome * this implementation is that segments of range trees with gaps can only
74a3874b8Toomas Soome * support removing complete segments.
75a3874b8Toomas Soome */
76a3874b8Toomas Soome
774d7988dPaul Dagneliestatic inline void
784d7988dPaul Dagneliers_copy(range_seg_t *src, range_seg_t *dest, range_tree_t *rt)
794d7988dPaul Dagnelie{
804d7988dPaul Dagnelie	ASSERT3U(rt->rt_type, <=, RANGE_SEG_NUM_TYPES);
814d7988dPaul Dagnelie	size_t size = 0;
824d7988dPaul Dagnelie	switch (rt->rt_type) {
834d7988dPaul Dagnelie	case RANGE_SEG32:
844d7988dPaul Dagnelie		size = sizeof (range_seg32_t);
854d7988dPaul Dagnelie		break;
864d7988dPaul Dagnelie	case RANGE_SEG64:
874d7988dPaul Dagnelie		size = sizeof (range_seg64_t);
884d7988dPaul Dagnelie		break;
894d7988dPaul Dagnelie	case RANGE_SEG_GAP:
904d7988dPaul Dagnelie		size = sizeof (range_seg_gap_t);
914d7988dPaul Dagnelie		break;
924d7988dPaul Dagnelie	default:
934d7988dPaul Dagnelie		VERIFY(0);
944d7988dPaul Dagnelie	}
954d7988dPaul Dagnelie	bcopy(src, dest, size);
960713e23George Wilson}
970713e23George Wilson
980713e23George Wilsonvoid
990713e23George Wilsonrange_tree_stat_verify(range_tree_t *rt)
1000713e23George Wilson{
1010713e23George Wilson	range_seg_t *rs;
1024d7988dPaul Dagnelie	zfs_btree_index_t where;
1030713e23George Wilson	uint64_t hist[RANGE_TREE_HISTOGRAM_SIZE] = { 0 };
1040713e23George Wilson	int i;
1050713e23George Wilson
1064d7988dPaul Dagnelie	for (rs = zfs_btree_first(&rt->rt_root, &where); rs != NULL;
1074d7988dPaul Dagnelie	    rs = zfs_btree_next(&rt->rt_root, &where, &where)) {
1084d7988dPaul Dagnelie		uint64_t size = rs_get_end(rs, rt) - rs_get_start(rs, rt);
109bf16b11Matthew Ahrens		int idx	= highbit64(size) - 1;
1100713e23George Wilson
1110713e23George Wilson		hist[idx]++;
1120713e23George Wilson		ASSERT3U(hist[idx], !=, 0);
1130713e23George Wilson	}
1140713e23George Wilson
1150713e23George Wilson	for (i = 0; i < RANGE_TREE_HISTOGRAM_SIZE; i++) {
1160713e23George Wilson		if (hist[i] != rt->rt_histogram[i]) {
1170713e23George Wilson			zfs_dbgmsg("i=%d, hist=%p, hist=%llu, rt_hist=%llu",
1180713e23George Wilson			    i, hist, hist[i], rt->rt_histogram[i]);
1190713e23George Wilson		}
1200713e23George Wilson		VERIFY3U(hist[i], ==, rt->rt_histogram[i]);
1210713e23George Wilson	}
1220713e23George Wilson}
1230713e23George Wilson
1240713e23George Wilsonstatic void
1250713e23George Wilsonrange_tree_stat_incr(range_tree_t *rt, range_seg_t *rs)
1260713e23George Wilson{
1274d7988dPaul Dagnelie	uint64_t size = rs_get_end(rs, rt) - rs_get_start(rs, rt);
128bf16b11Matthew Ahrens	int idx = highbit64(size) - 1;
1290713e23George Wilson
1302e4c998George Wilson	ASSERT(size != 0);
1310713e23George Wilson	ASSERT3U(idx, <,
1320713e23George Wilson	    sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram));
1330713e23George Wilson
1340713e23George Wilson	rt->rt_histogram[idx]++;
1350713e23George Wilson	ASSERT3U(rt->rt_histogram[idx], !=, 0);
1360713e23George Wilson}
1370713e23George Wilson
1380713e23George Wilsonstatic void
1390713e23George Wilsonrange_tree_stat_decr(range_tree_t *rt, range_seg_t *rs)
1400713e23George Wilson{
1414d7988dPaul Dagnelie	uint64_t size = rs_get_end(rs, rt) - rs_get_start(rs, rt);
142bf16b11Matthew Ahrens	int idx = highbit64(size) - 1;
1430713e23George Wilson
1442e4c998George Wilson	ASSERT(size != 0);
1450713e23George Wilson	ASSERT3U(idx, <,
1460713e23George Wilson	    sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram));
1470713e23George Wilson
1480713e23George Wilson	ASSERT3U(rt->rt_histogram[idx], !=, 0);
1490713e23George Wilson	rt->rt_histogram[idx]--;
1500713e23George Wilson}
1510713e23George Wilson
1520713e23George Wilsonstatic int
1534d7988dPaul Dagnelierange_tree_seg32_compare(const void *x1, const void *x2)
1544d7988dPaul Dagnelie{
1554d7988dPaul Dagnelie	const range_seg32_t *r1 = x1;
1564d7988dPaul Dagnelie	const range_seg32_t *r2 = x2;
1574d7988dPaul Dagnelie
1584d7988dPaul Dagnelie	ASSERT3U(r1->rs_start, <=, r1->rs_end);
1594d7988dPaul Dagnelie	ASSERT3U(r2->rs_start, <=, r2->rs_end);
1604d7988dPaul Dagnelie
1614d7988dPaul Dagnelie	return ((r1->rs_start >= r2->rs_end) - (r1->rs_end <= r2->rs_start));
1624d7988dPaul Dagnelie}
1634d7988dPaul Dagnelie
1644d7988dPaul Dagneliestatic int
1654d7988dPaul Dagnelierange_tree_seg64_compare(const void *x1, const void *x2)
1664d7988dPaul Dagnelie{
1674d7988dPaul Dagnelie	const range_seg64_t *r1 = x1;
1684d7988dPaul Dagnelie	const range_seg64_t *r2 = x2;
1694d7988dPaul Dagnelie
1704d7988dPaul Dagnelie	ASSERT3U(r1->rs_start, <=, r1->rs_end);
1714d7988dPaul Dagnelie	ASSERT3U(r2->rs_start, <=, r2->rs_end);
1724d7988dPaul Dagnelie
1734d7988dPaul Dagnelie	return ((r1->rs_start >= r2->rs_end) - (r1->rs_end <= r2->rs_start));
1744d7988dPaul Dagnelie}
1754d7988dPaul Dagnelie
1764d7988dPaul Dagneliestatic int
1774d7988dPaul Dagnelierange_tree_seg_gap_compare(const void *x1, const void *x2)
1780713e23George Wilson{
1794d7988dPaul Dagnelie	const range_seg_gap_t *r1 = x1;
1804d7988dPaul Dagnelie	const range_seg_gap_t *r2 = x2;
1810713e23George Wilson
182c4ab0d3Gvozden Neskovic	ASSERT3U(r1->rs_start, <=, r1->rs_end);
183c4ab0d3Gvozden Neskovic	ASSERT3U(r2->rs_start, <=, r2->rs_end);
184c4ab0d3Gvozden Neskovic
185c4ab0d3Gvozden Neskovic	return ((r1->rs_start >= r2->rs_end) - (r1->rs_end <= r2->rs_start));
1860713e23George Wilson}
1870713e23George Wilson
1880713e23George Wilsonrange_tree_t *
1894d7988dPaul Dagnelierange_tree_create_impl(range_tree_ops_t *ops, range_seg_type_t type, void *arg,
1904d7988dPaul Dagnelie    uint64_t start, uint64_t shift,
1914d7988dPaul Dagnelie    int (*zfs_btree_compare) (const void *, const void *),
1924d7988dPaul Dagnelie    uint64_t gap)
1930713e23George Wilson{
194a3874b8Toomas Soome	range_tree_t *rt = kmem_zalloc(sizeof (range_tree_t), KM_SLEEP);
1950713e23George Wilson
1964d7988dPaul Dagnelie	ASSERT3U(shift, <, 64);
1974d7988dPaul Dagnelie	ASSERT3U(type, <=, RANGE_SEG_NUM_TYPES);
1984d7988dPaul Dagnelie	size_t size;
1994d7988dPaul Dagnelie	int (*compare) (const void *, const void *);
2004d7988dPaul Dagnelie	switch (type) {
2014d7988dPaul Dagnelie	case RANGE_SEG32:
2024d7988dPaul Dagnelie		size = sizeof (range_seg32_t);
2034d7988dPaul Dagnelie		compare = range_tree_seg32_compare;
2044d7988dPaul Dagnelie		break;
2054d7988dPaul Dagnelie	case RANGE_SEG64:
2064d7988dPaul Dagnelie		size = sizeof (range_seg64_t);
2074d7988dPaul Dagnelie		compare = range_tree_seg64_compare;
2084d7988dPaul Dagnelie		break;
2094d7988dPaul Dagnelie	case RANGE_SEG_GAP:
2104d7988dPaul Dagnelie		size = sizeof (range_seg_gap_t);
2114d7988dPaul Dagnelie		compare = range_tree_seg_gap_compare;
2124d7988dPaul Dagnelie		break;
2134d7988dPaul Dagnelie	default:
2144d7988dPaul Dagnelie		panic("Invalid range seg type %d", type);
2154d7988dPaul Dagnelie	}
2164d7988dPaul Dagnelie	zfs_btree_create(&rt->rt_root, compare, size);
2170713e23George Wilson
2180713e23George Wilson	rt->rt_ops = ops;
2190713e23George Wilson	rt->rt_arg = arg;
220a3874b8Toomas Soome	rt->rt_gap = gap;
2214d7988dPaul Dagnelie	rt->rt_type = type;
2224d7988dPaul Dagnelie	rt->rt_start = start;
2234d7988dPaul Dagnelie	rt->rt_shift = shift;
2244d7988dPaul Dagnelie	rt->rt_btree_compare = zfs_btree_compare;
2250713e23George Wilson
226a3874b8Toomas Soome	if (rt->rt_ops != NULL && rt->rt_ops->rtop_create != NULL)
2270713e23George Wilson		rt->rt_ops->rtop_create(rt, rt->rt_arg);
2280713e23George Wilson
2290713e23George Wilson	return (rt);
2300713e23George Wilson}
2310713e23George Wilson
232a3874b8Toomas Soomerange_tree_t *
2334d7988dPaul Dagnelierange_tree_create(range_tree_ops_t *ops, range_seg_type_t type,
2344d7988dPaul Dagnelie    void *arg, uint64_t start, uint64_t shift)
235a3874b8Toomas Soome{
2364d7988dPaul Dagnelie	return (range_tree_create_impl(ops, type, arg, start, shift, NULL, 0));
237a3874b8Toomas Soome}
238a3874b8Toomas Soome
2390713e23George Wilsonvoid
2400713e23George Wilsonrange_tree_destroy(range_tree_t *rt)
2410713e23George Wilson{
2420713e23George Wilson	VERIFY0(rt->rt_space);
2430713e23George Wilson
244a3874b8Toomas Soome	if (rt->rt_ops != NULL && rt->rt_ops->rtop_destroy != NULL)
2450713e23George Wilson		rt->rt_ops->rtop_destroy(rt, rt->rt_arg);
2460713e23George Wilson
2474d7988dPaul Dagnelie	zfs_btree_destroy(&rt->rt_root);
2480713e23George Wilson	kmem_free(rt, sizeof (*rt));
2490713e23George Wilson}
2500713e23George Wilson
2510713e23George Wilsonvoid
252a3874b8Toomas Soomerange_tree_adjust_fill(range_tree_t *rt, range_seg_t *rs, int64_t delta)
253a3874b8Toomas Soome{
2544d7988dPaul Dagnelie	ASSERT3U(rs_get_fill(rs, rt) + delta, !=, 0);
2554d7988dPaul Dagnelie	ASSERT3U(rs_get_fill(rs, rt) + delta, <=, rs_get_end(rs, rt) -
2564d7988dPaul Dagnelie	    rs_get_start(rs, rt));
257a3874b8Toomas Soome
258a3874b8Toomas Soome	if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
259a3874b8Toomas Soome		rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);
2604d7988dPaul Dagnelie	rs_set_fill(rs, rt, rs_get_fill(rs, rt) + delta);
261a3874b8Toomas Soome	if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)
262a3874b8Toomas Soome		rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);
263a3874b8Toomas Soome}
264a3874b8Toomas Soome
265a3874b8Toomas Soomestatic void
266a3874b8Toomas Soomerange_tree_add_impl(void *arg, uint64_t start, uint64_t size, uint64_t fill)
2670713e23George Wilson{
2680713e23George Wilson	range_tree_t *rt = arg;
2694d7988dPaul Dagnelie	zfs_btree_index_t where;
2704d7988dPaul Dagnelie	range_seg_t *rs_before, *rs_after, *rs;
2714d7988dPaul Dagnelie	range_seg_max_t tmp, rsearch;
272a3874b8Toomas Soome	uint64_t end = start + size, gap = rt->rt_gap;
273a3874b8Toomas Soome	uint64_t bridge_size = 0;
2740713e23George Wilson	boolean_t merge_before, merge_after;
2750713e23George Wilson
276a3874b8Toomas Soome	ASSERT3U(size, !=, 0);
277a3874b8Toomas Soome	ASSERT3U(fill, <=, size);
2784d7988dPaul Dagnelie	ASSERT3U(start + size, >, start);
2790713e23George Wilson
2804d7988dPaul Dagnelie	rs_set_start(&rsearch, rt, start);
2814d7988dPaul Dagnelie	rs_set_end(&rsearch, rt, end);
2824d7988dPaul Dagnelie	rs = zfs_btree_find(&rt->rt_root, &rsearch, &where);
2830713e23George Wilson
284a3874b8Toomas Soome	/*
285a3874b8Toomas Soome	 * If this is a gap-supporting range tree, it is possible that we
286a3874b8Toomas Soome	 * are inserting into an existing segment. In this case simply
287a3874b8Toomas Soome	 * bump the fill count and call the remove / add callbacks. If the
288a3874b8Toomas Soome	 * new range will extend an existing segment, we remove the
289a3874b8Toomas Soome	 * existing one, apply the new extent to it and re-insert it using
290a3874b8Toomas Soome	 * the normal code paths.
291a3874b8Toomas Soome	 */
292a3874b8Toomas Soome	if (rs != NULL) {
2934d7988dPaul Dagnelie		ASSERT3U(rt->rt_gap, !=, 0);
2944d7988dPaul Dagnelie		uint64_t rstart = rs_get_start(rs, rt);
2954d7988dPaul Dagnelie		uint64_t rend = rs_get_end(rs, rt);
296a3874b8Toomas Soome		ASSERT3U(gap, !=, 0);
2974d7988dPaul Dagnelie		if (rstart <= start && rend >= end) {
298a3874b8Toomas Soome			range_tree_adjust_fill(rt, rs, fill);
299a3874b8Toomas Soome			return;
300a3874b8Toomas Soome		}
301a3874b8Toomas Soome
3024d7988dPaul Dagnelie		zfs_btree_remove(&rt->rt_root, rs);
303a3874b8Toomas Soome		if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
304a3874b8Toomas Soome			rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);
305a3874b8Toomas Soome
306a3874b8Toomas Soome		range_tree_stat_decr(rt, rs);
3074d7988dPaul Dagnelie		rt->rt_space -= rend - rstart;
308a3874b8Toomas Soome
3094d7988dPaul Dagnelie		fill += rs_get_fill(rs, rt);
3104d7988dPaul Dagnelie		start = MIN(start, rstart);
3114d7988dPaul Dagnelie		end = MAX(end, rend);
312a3874b8Toomas Soome		size = end - start;
313a3874b8Toomas Soome
314a3874b8Toomas Soome		range_tree_add_impl(rt, start, size, fill);
315a3874b8Toomas Soome		return;
316a3874b8Toomas Soome	}
3170713e23George Wilson
318a3874b8Toomas Soome	ASSERT3P(rs, ==, NULL);
319a3874b8Toomas Soome
320a3874b8Toomas Soome	/*
321a3874b8Toomas Soome	 * Determine whether or not we will have to merge with our neighbors.
322a3874b8Toomas Soome	 * If gap != 0, we might need to merge with our neighbors even if we
323a3874b8Toomas Soome	 * aren't directly touching.
324a3874b8Toomas Soome	 */
3254d7988dPaul Dagnelie	zfs_btree_index_t where_before, where_after;
3264d7988dPaul Dagnelie	rs_before = zfs_btree_prev(&rt->rt_root, &where, &where_before);
3274d7988dPaul Dagnelie	rs_after = zfs_btree_next(&rt->rt_root, &where, &where_after);
3280713e23George Wilson
3294d7988dPaul Dagnelie	merge_before = (rs_before != NULL && rs_get_end(rs_before, rt) >=
3304d7988dPaul Dagnelie	    start - gap);
3314d7988dPaul Dagnelie	merge_after = (rs_after != NULL && rs_get_start(rs_after, rt) <= end +
3324d7988dPaul Dagnelie	    gap);
333a3874b8Toomas Soome
334a3874b8Toomas Soome	if (merge_before && gap != 0)
3354d7988dPaul Dagnelie		bridge_size += start - rs_get_end(rs_before, rt);
336a3874b8Toomas Soome	if (merge_after && gap != 0)
3374d7988dPaul Dagnelie		bridge_size += rs_get_start(rs_after, rt) - end;
3380713e23George Wilson
3390713e23George Wilson	if (merge_before && merge_after) {
340a3874b8Toomas Soome		if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL) {
3410713e23George Wilson			rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg);
3420713e23George Wilson			rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg);
3430713e23George Wilson		}
3440713e23George Wilson
3450713e23George Wilson		range_tree_stat_decr(rt, rs_before);
3460713e23George Wilson		range_tree_stat_decr(rt, rs_after);
3470713e23George Wilson
3484d7988dPaul Dagnelie		rs_copy(rs_after, &tmp, rt);
3494d7988dPaul Dagnelie		uint64_t before_start = rs_get_start_raw(rs_before, rt);
3504d7988dPaul Dagnelie		uint64_t before_fill = rs_get_fill(rs_before, rt);
3514d7988dPaul Dagnelie		uint64_t after_fill = rs_get_fill(rs_after, rt);
352bfb9edcPaul Dagnelie		zfs_btree_remove_idx(&rt->rt_root, &where_before);
3534d7988dPaul Dagnelie
3544d7988dPaul Dagnelie		/*
3554d7988dPaul Dagnelie		 * We have to re-find the node because our old reference is
3564d7988dPaul Dagnelie		 * invalid as soon as we do any mutating btree operations.
3574d7988dPaul Dagnelie		 */
3584d7988dPaul Dagnelie		rs_after = zfs_btree_find(&rt->rt_root, &tmp, &where_after);
3594d7988dPaul Dagnelie		rs_set_start_raw(rs_after, rt, before_start);
3604d7988dPaul Dagnelie		rs_set_fill(rs_after, rt, after_fill + before_fill + fill);
3610713e23George Wilson		rs = rs_after;
3620713e23George Wilson	} else if (merge_before) {
363a3874b8Toomas Soome		if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
3640713e23George Wilson			rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg);
3650713e23George Wilson
3660713e23George Wilson		range_tree_stat_decr(rt, rs_before);
3670713e23George Wilson
3684d7988dPaul Dagnelie		uint64_t before_fill = rs_get_fill(rs_before, rt);
3694d7988dPaul Dagnelie		rs_set_end(rs_before, rt, end);
3704d7988dPaul Dagnelie		rs_set_fill(rs_before, rt, before_fill + fill);
3710713e23George Wilson		rs = rs_before;
3720713e23George Wilson	} else if (merge_after) {
373a3874b8Toomas Soome		if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
3740713e23George Wilson			rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg);
3750713e23George Wilson
3760713e23George Wilson		range_tree_stat_decr(rt, rs_after);
3770713e23George Wilson
3784d7988dPaul Dagnelie		uint64_t after_fill = rs_get_fill(rs_after, rt);
3794d7988dPaul Dagnelie		rs_set_start(rs_after, rt, start);
3804d7988dPaul Dagnelie		rs_set_fill(rs_after, rt, after_fill + fill);
3810713e23George Wilson		rs = rs_after;
3820713e23George Wilson	} else {
3834d7988dPaul Dagnelie		rs = &tmp;
384a3874b8Toomas Soome
3854d7988dPaul Dagnelie		rs_set_start(rs, rt, start);
3864d7988dPaul Dagnelie		rs_set_end(rs, rt, end);
3874d7988dPaul Dagnelie		rs_set_fill(rs, rt, fill);
388bfb9edcPaul Dagnelie		zfs_btree_add_idx(&rt->rt_root, rs, &where);
3890713e23George Wilson	}
3900713e23George Wilson
3914d7988dPaul Dagnelie	if (gap != 0) {
3924d7988dPaul Dagnelie		ASSERT3U(rs_get_fill(rs, rt), <=, rs_get_end(rs, rt) -
3934d7988dPaul Dagnelie		    rs_get_start(rs, rt));
3944d7988dPaul Dagnelie	} else {
3954d7988dPaul Dagnelie		ASSERT3U(rs_get_fill(rs, rt), ==, rs_get_end(rs, rt) -
3964d7988dPaul Dagnelie		    rs_get_start(rs, rt));
3974d7988dPaul Dagnelie	}
398a3874b8Toomas Soome
399a3874b8Toomas Soome	if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)
4000713e23George Wilson		rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);
4010713e23George Wilson
4020713e23George Wilson	range_tree_stat_incr(rt, rs);
403a3874b8Toomas Soome	rt->rt_space += size + bridge_size;
4040713e23George Wilson}
4050713e23George Wilson
4060713e23George Wilsonvoid
407a3874b8Toomas Soomerange_tree_add(void *arg, uint64_t start, uint64_t size)
408a3874b8Toomas Soome{
409a3874b8Toomas Soome	range_tree_add_impl(arg, start, size, size);
410a3874b8Toomas Soome}
411a3874b8Toomas Soome
412a3874b8Toomas Soomestatic void
413a3874b8Toomas Soomerange_tree_remove_impl(range_tree_t *rt, uint64_t start, uint64_t size,
414a3874b8Toomas Soome    boolean_t do_fill)
4150713e23George Wilson{
4164d7988dPaul Dagnelie	zfs_btree_index_t where;
4174d7988dPaul Dagnelie	range_seg_t *rs;
4184d7988dPaul Dagnelie	range_seg_max_t rsearch, rs_tmp;
4190713e23George Wilson	uint64_t end = start + size;
4200713e23George Wilson	boolean_t left_over, right_over;
4210713e23George Wilson
4220713e23George Wilson	VERIFY3U(size, !=, 0);
4230713e23George Wilson	VERIFY3U(size, <=, rt->rt_space);
4244d7988dPaul Dagnelie	if (rt->rt_type == RANGE_SEG64)
4254d7988dPaul Dagnelie		ASSERT3U(start + size, >, start);
4260713e23George Wilson
4274d7988dPaul Dagnelie	rs_set_start(&rsearch, rt, start);
4284d7988dPaul Dagnelie	rs_set_end(&rsearch, rt, end);
4294d7988dPaul Dagnelie	rs = zfs_btree_find(&rt->rt_root, &rsearch, &where);
4300713e23George Wilson
4310713e23George Wilson	/* Make sure we completely overlap with someone */
4320713e23George Wilson	if (rs == NULL) {
4334d7988dPaul Dagnelie		zfs_panic_recover("zfs: removing nonexistent segment from "
4344d7988dPaul Dagnelie		    "range tree (offset=%llu size=%llu)",
4350713e23George Wilson		    (longlong_t)start, (longlong_t)size);
4360713e23George Wilson		return;
4370713e23George Wilson	}
438a3874b8Toomas Soome
439a3874b8Toomas Soome	/*
440a3874b8Toomas Soome	 * Range trees with gap support must only remove complete segments
441a3874b8Toomas Soome	 * from the tree. This allows us to maintain accurate fill accounting
442a3874b8Toomas Soome	 * and to ensure that bridged sections are not leaked. If we need to
443a3874b8Toomas Soome	 * remove less than the full segment, we can only adjust the fill count.
444a3874b8Toomas Soome	 */
445a3874b8Toomas Soome	if (rt->rt_gap != 0) {
446a3874b8Toomas Soome		if (do_fill) {
4474d7988dPaul Dagnelie			if (rs_get_fill(rs, rt) == size) {
4484d7988dPaul Dagnelie				start = rs_get_start(rs, rt);
4494d7988dPaul Dagnelie				end = rs_get_end(rs, rt);
450a3874b8Toomas Soome				size = end - start;
451a3874b8Toomas Soome			} else {
452a3874b8Toomas Soome				range_tree_adjust_fill(rt, rs, -size);
453a3874b8Toomas Soome				return;
454a3874b8Toomas Soome			}
4554d7988dPaul Dagnelie		} else if (rs_get_start(rs, rt) != start ||
4564d7988dPaul Dagnelie		    rs_get_end(rs, rt) != end) {
457a3874b8Toomas Soome			zfs_panic_recover("zfs: freeing partial segment of "
458a3874b8Toomas Soome			    "gap tree (offset=%llu size=%llu) of "
459a3874b8Toomas Soome			    "(offset=%llu size=%llu)",
460a3874b8Toomas Soome			    (longlong_t)start, (longlong_t)size,
4614d7988dPaul Dagnelie			    (longlong_t)rs_get_start(rs, rt),
4624d7988dPaul Dagnelie			    (longlong_t)rs_get_end(rs, rt) - rs_get_start(rs,
4634d7988dPaul Dagnelie			    rt));
464a3874b8Toomas Soome			return;
465a3874b8Toomas Soome		}
466a3874b8Toomas Soome	}
467a3874b8Toomas Soome
4684d7988dPaul Dagnelie	VERIFY3U(rs_get_start(rs, rt), <=, start);
4694d7988dPaul Dagnelie	VERIFY3U(rs_get_end(rs, rt), >=, end);
4700713e23George Wilson
4714d7988dPaul Dagnelie	left_over = (rs_get_start(rs, rt) != start);
4724d7988dPaul Dagnelie	right_over = (rs_get_end(rs, rt) != end);
4730713e23George Wilson
4740713e23George Wilson	range_tree_stat_decr(rt, rs);
4750713e23George Wilson
476a3874b8Toomas Soome	if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
4770713e23George Wilson		rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);
4780713e23George Wilson
4790713e23George Wilson	if (left_over && right_over) {
4804d7988dPaul Dagnelie		range_seg_max_t newseg;
4814d7988dPaul Dagnelie		rs_set_start(&newseg, rt, end);
4824d7988dPaul Dagnelie		rs_set_end_raw(&newseg, rt, rs_get_end_raw(rs, rt));
4834d7988dPaul Dagnelie		rs_set_fill(&newseg, rt, rs_get_end(rs, rt) - end);
4844d7988dPaul Dagnelie		range_tree_stat_incr(rt, &newseg);
4850713e23George Wilson
4864d7988dPaul Dagnelie		// This modifies the buffer already inside the range tree
4874d7988dPaul Dagnelie		rs_set_end(rs, rt, start);
4884d7988dPaul Dagnelie
4894d7988dPaul Dagnelie		rs_copy(rs, &rs_tmp, rt);
4904d7988dPaul Dagnelie		if (zfs_btree_next(&rt->rt_root, &where, &where) != NULL)
491bfb9edcPaul Dagnelie			zfs_btree_add_idx(&rt->rt_root, &newseg, &where);
4924d7988dPaul Dagnelie		else
4934d7988dPaul Dagnelie			zfs_btree_add(&rt->rt_root, &newseg);
4940713e23George Wilson
495a3874b8Toomas Soome		if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)
4964d7988dPaul Dagnelie			rt->rt_ops->rtop_add(rt, &newseg, rt->rt_arg);
4970713e23George Wilson	} else if (left_over) {
4984d7988dPaul Dagnelie		// This modifies the buffer already inside the range tree
4994d7988dPaul Dagnelie		rs_set_end(rs, rt, start);
5004d7988dPaul Dagnelie		rs_copy(rs, &rs_tmp, rt);
5010713e23George Wilson	} else if (right_over) {
5024d7988dPaul Dagnelie		// This modifies the buffer already inside the range tree
5034d7988dPaul Dagnelie		rs_set_start(rs, rt, end);
5044d7988dPaul Dagnelie		rs_copy(rs, &rs_tmp, rt);
5050713e23George Wilson	} else {
506bfb9edcPaul Dagnelie		zfs_btree_remove_idx(&rt->rt_root, &where);
5070713e23George Wilson		rs = NULL;
5080713e23George Wilson	}
5090713e23George Wilson
5100713e23George Wilson	if (rs != NULL) {
511a3874b8Toomas Soome		/*
512a3874b8Toomas Soome		 * The fill of the leftover segment will always be equal to
513a3874b8Toomas Soome		 * the size, since we do not support removing partial segments
514a3874b8Toomas Soome		 * of range trees with gaps.
515a3874b8Toomas Soome		 */
5164d7988dPaul Dagnelie		rs_set_fill_raw(rs, rt, rs_get_end_raw(rs, rt) -
5174d7988dPaul Dagnelie		    rs_get_start_raw(rs, rt));
5184d7988dPaul Dagnelie		range_tree_stat_incr(rt, &rs_tmp);
5190713e23George Wilson
520a3874b8Toomas Soome		if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)
5214d7988dPaul Dagnelie			rt->rt_ops->rtop_add(rt, &rs_tmp, rt->rt_arg);
5220713e23George Wilson	}
5230713e23George Wilson
5240713e23George Wilson	rt->rt_space -= size;
5250713e23George Wilson}
5260713e23George Wilson
527a3874b8Toomas Soomevoid
528a3874b8Toomas Soomerange_tree_remove(void *arg, uint64_t start, uint64_t size)
529a3874b8Toomas Soome{
530a3874b8Toomas Soome	range_tree_remove_impl(arg, start, size, B_FALSE);
531a3874b8Toomas Soome}
532a3874b8Toomas Soome
533a3874b8Toomas Soomevoid
534a3874b8Toomas Soomerange_tree_remove_fill(range_tree_t *rt, uint64_t start, uint64_t size)
535a3874b8Toomas Soome{
536a3874b8Toomas Soome	range_tree_remove_impl(rt, start, size, B_TRUE);
537a3874b8Toomas Soome}
538a3874b8Toomas Soome
539a3874b8Toomas Soomevoid
540a3874b8Toomas Soomerange_tree_resize_segment(range_tree_t *rt, range_seg_t *rs,
541a3874b8Toomas Soome    uint64_t newstart, uint64_t newsize)
542a3874b8Toomas Soome{
5434d7988dPaul Dagnelie	int64_t delta = newsize - (rs_get_end(rs, rt) - rs_get_start(rs, rt));
544a3874b8Toomas Soome
545a3874b8Toomas Soome	range_tree_stat_decr(rt, rs);
546a3874b8Toomas Soome	if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
547a3874b8Toomas Soome		rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);
548a3874b8Toomas Soome
5494d7988dPaul Dagnelie	rs_set_start(rs, rt, newstart);
5504d7988dPaul Dagnelie	rs_set_end(rs, rt, newstart + newsize);
551a3874b8Toomas Soome
552a3874b8Toomas Soome	range_tree_stat_incr(rt, rs);
553a3874b8Toomas Soome	if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)
554a3874b8Toomas Soome		rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);
555a3874b8Toomas Soome
556a3874b8Toomas Soome	rt->rt_space += delta;
557a3874b8Toomas Soome}
558a3874b8Toomas Soome
5590713e23George Wilsonstatic range_seg_t *
560bf16b11Matthew Ahrensrange_tree_find_impl(range_tree_t *rt, uint64_t start, uint64_t size)
5610713e23George Wilson{
5624d7988dPaul Dagnelie	range_seg_max_t rsearch;
5630713e23George Wilson	uint64_t end = start + size;
5640713e23George Wilson
5650713e23George Wilson	VERIFY(size != 0);
5660713e23George Wilson
5674d7988dPaul Dagnelie	rs_set_start(&rsearch, rt, start);
5684d7988dPaul Dagnelie	rs_set_end(&rsearch, rt, end);
5694d7988dPaul Dagnelie	return (zfs_btree_find(&rt->rt_root, &rsearch, NULL));
570bf16b11Matthew Ahrens}
5710713e23George Wilson
572a3874b8Toomas Soomerange_seg_t *
573bf16b11Matthew Ahrensrange_tree_find(range_tree_t *rt, uint64_t start, uint64_t size)
574bf16b11Matthew Ahrens{
5754d7988dPaul Dagnelie	if (rt->rt_type == RANGE_SEG64)
5764d7988dPaul Dagnelie		ASSERT3U(start + size, >, start);
5774d7988dPaul Dagnelie
578bf16b11Matthew Ahrens	range_seg_t *rs = range_tree_find_impl(rt, start, size);
5794d7988dPaul Dagnelie	if (rs != NULL && rs_get_start(rs, rt) <= start &&
5804d7988dPaul Dagnelie	    rs_get_end(rs, rt) >= start + size) {
5810713e23George Wilson		return (rs);
5824d7988dPaul Dagnelie	}
5830713e23George Wilson	return (NULL);
5840713e23George Wilson}
5850713e23George Wilson
5860713e23George Wilsonvoid
587555d674Serapheim Dimitropoulosrange_tree_verify_not_present(range_tree_t *rt, uint64_t off, uint64_t size)
5880713e23George Wilson{
589555d674Serapheim Dimitropoulos	range_seg_t *rs = range_tree_find(rt, off, size);
5900713e23George Wilson	if (rs != NULL)
591555d674Serapheim Dimitropoulos		panic("segment already in tree; rs=%p", (void *)rs);
5920713e23George Wilson}
5930713e23George Wilson
5940713e23George Wilsonboolean_t
5950713e23George Wilsonrange_tree_contains(range_tree_t *rt, uint64_t start, uint64_t size)
5960713e23George Wilson{
597bf16b11Matthew Ahrens	return (range_tree_find(rt, start, size) != NULL);
598bf16b11Matthew Ahrens}
5990713e23George Wilson
600bf16b11Matthew Ahrens/*
601af1d63aPaul Dagnelie * Returns the first subset of the given range which overlaps with the range
602af1d63aPaul Dagnelie * tree. Returns true if there is a segment in the range, and false if there
603af1d63aPaul Dagnelie * isn't.
604af1d63aPaul Dagnelie */
605af1d63aPaul Dagnelieboolean_t
606af1d63aPaul Dagnelierange_tree_find_in(range_tree_t *rt, uint64_t start, uint64_t size,
607af1d63aPaul Dagnelie    uint64_t *ostart, uint64_t *osize)
608af1d63aPaul Dagnelie{
6094d7988dPaul Dagnelie	if (rt->rt_type == RANGE_SEG64)
6104d7988dPaul Dagnelie		ASSERT3U(start + size, >, start);
6114d7988dPaul Dagnelie
6124d7988dPaul Dagnelie	range_seg_max_t rsearch;
6134d7988dPaul Dagnelie	rs_set_start(&rsearch, rt, start);
6144d7988dPaul Dagnelie	rs_set_end_raw(&rsearch, rt, rs_get_start_raw(&rsearch, rt) + 1);
615af1d63aPaul Dagnelie
6164d7988dPaul Dagnelie	zfs_btree_index_t where;
6174d7988dPaul Dagnelie	range_seg_t *rs = zfs_btree_find(&rt->rt_root, &rsearch, &where);
618af1d63aPaul Dagnelie	if (rs != NULL) {
619af1d63aPaul Dagnelie		*ostart = start;
6204d7988dPaul Dagnelie		*osize = MIN(size, rs_get_end(rs, rt) - start);
621af1d63aPaul Dagnelie		return (B_TRUE);
622af1d63aPaul Dagnelie	}
623af1d63aPaul Dagnelie
6244d7988dPaul Dagnelie	rs = zfs_btree_next(&rt->rt_root, &where, &where);
6254d7988dPaul Dagnelie	if (rs == NULL || rs_get_start(rs, rt) > start + size)
626af1d63aPaul Dagnelie		return (B_FALSE);
627af1d63aPaul Dagnelie
6284d7988dPaul Dagnelie	*ostart = rs_get_start(rs, rt);
6294d7988dPaul Dagnelie	*osize = MIN(start + size, rs_get_end(rs, rt)) -
6304d7988dPaul Dagnelie	    rs_get_start(rs, rt);
631af1d63aPaul Dagnelie	return (B_TRUE);
632af1d63aPaul Dagnelie}
633af1d63aPaul Dagnelie
634af1d63aPaul Dagnelie/*
635bf16b11Matthew Ahrens * Ensure that this range is not in the tree, regardless of whether
636bf16b11Matthew Ahrens * it is currently in the tree.
637bf16b11Matthew Ahrens */
638bf16b11Matthew Ahrensvoid
639bf16b11Matthew Ahrensrange_tree_clear(range_tree_t *rt, uint64_t start, uint64_t size)
640bf16b11Matthew Ahrens{
641bf16b11Matthew Ahrens	range_seg_t *rs;
642bf16b11Matthew Ahrens
6435cabbc6Prashanth Sreenivasa	if (size == 0)
6445cabbc6Prashanth Sreenivasa		return;
6455cabbc6Prashanth Sreenivasa
6464d7988dPaul Dagnelie	if (rt->rt_type == RANGE_SEG64)
6474d7988dPaul Dagnelie		ASSERT3U(start + size, >, start);
6484d7988dPaul Dagnelie
649bf16b11Matthew Ahrens	while ((rs = range_tree_find_impl(rt, start, size)) != NULL) {
6504d7988dPaul Dagnelie		uint64_t free_start = MAX(rs_get_start(rs, rt), start);
6514d7988dPaul Dagnelie		uint64_t free_end = MIN(rs_get_end(rs, rt), start + size);
652bf16b11Matthew Ahrens		range_tree_remove(rt, free_start, free_end - free_start);
653bf16b11Matthew Ahrens	}
6540713e23George Wilson}
6550713e23George Wilson
6560713e23George Wilsonvoid
6570713e23George Wilsonrange_tree_swap(range_tree_t **rtsrc, range_tree_t **rtdst)
6580713e23George Wilson{
6590713e23George Wilson	range_tree_t *rt;
6600713e23George Wilson
6610713e23George Wilson	ASSERT0(range_tree_space(*rtdst));
6624d7988dPaul Dagnelie	ASSERT0(zfs_btree_numnodes(&(*rtdst)->rt_root));
6630713e23George Wilson
6640713e23George Wilson	rt = *rtsrc;
6650713e23George Wilson	*rtsrc = *rtdst;
6660713e23George Wilson	*rtdst = rt;
6670713e23George Wilson}
6680713e23George Wilson
6690713e23George Wilsonvoid
6700713e23George Wilsonrange_tree_vacate(range_tree_t *rt, range_tree_func_t *func, void *arg)
6710713e23George Wilson{