10713e232SGeorge Wilson /*
20713e232SGeorge Wilson * CDDL HEADER START
30713e232SGeorge Wilson *
40713e232SGeorge Wilson * The contents of this file are subject to the terms of the
50713e232SGeorge Wilson * Common Development and Distribution License (the "License").
60713e232SGeorge Wilson * You may not use this file except in compliance with the License.
70713e232SGeorge Wilson *
80713e232SGeorge Wilson * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
90713e232SGeorge Wilson * or http://www.opensolaris.org/os/licensing.
100713e232SGeorge Wilson * See the License for the specific language governing permissions
110713e232SGeorge Wilson * and limitations under the License.
120713e232SGeorge Wilson *
130713e232SGeorge Wilson * When distributing Covered Code, include this CDDL HEADER in each
140713e232SGeorge Wilson * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
150713e232SGeorge Wilson * If applicable, add the following below this CDDL HEADER, with the
160713e232SGeorge Wilson * fields enclosed by brackets "[]" replaced with your own identifying
170713e232SGeorge Wilson * information: Portions Copyright [yyyy] [name of copyright owner]
180713e232SGeorge Wilson *
190713e232SGeorge Wilson * CDDL HEADER END
200713e232SGeorge Wilson */
210713e232SGeorge Wilson /*
220713e232SGeorge Wilson * Copyright 2009 Sun Microsystems, Inc. All rights reserved.
230713e232SGeorge Wilson * Use is subject to license terms.
240713e232SGeorge Wilson */
250713e232SGeorge Wilson /*
26814dcd43SSerapheim Dimitropoulos * Copyright (c) 2013, 2019 by Delphix. All rights reserved.
270713e232SGeorge Wilson */
280713e232SGeorge Wilson
290713e232SGeorge Wilson #include <sys/zfs_context.h>
300713e232SGeorge Wilson #include <sys/spa.h>
310713e232SGeorge Wilson #include <sys/dmu.h>
320713e232SGeorge Wilson #include <sys/dnode.h>
330713e232SGeorge Wilson #include <sys/zio.h>
340713e232SGeorge Wilson #include <sys/range_tree.h>
350713e232SGeorge Wilson
36a3874b8bSToomas Soome /*
37a3874b8bSToomas Soome * Range trees are tree-based data structures that can be used to
38a3874b8bSToomas Soome * track free space or generally any space allocation information.
39a3874b8bSToomas Soome * A range tree keeps track of individual segments and automatically
40a3874b8bSToomas Soome * provides facilities such as adjacent extent merging and extent
41a3874b8bSToomas Soome * splitting in response to range add/remove requests.
42a3874b8bSToomas Soome *
43a3874b8bSToomas Soome * A range tree starts out completely empty, with no segments in it.
44a3874b8bSToomas Soome * Adding an allocation via range_tree_add to the range tree can either:
45a3874b8bSToomas Soome * 1) create a new extent
46a3874b8bSToomas Soome * 2) extend an adjacent extent
47a3874b8bSToomas Soome * 3) merge two adjacent extents
48a3874b8bSToomas Soome * Conversely, removing an allocation via range_tree_remove can:
49a3874b8bSToomas Soome * 1) completely remove an extent
50a3874b8bSToomas Soome * 2) shorten an extent (if the allocation was near one of its ends)
51a3874b8bSToomas Soome * 3) split an extent into two extents, in effect punching a hole
52a3874b8bSToomas Soome *
53a3874b8bSToomas Soome * A range tree is also capable of 'bridging' gaps when adding
54a3874b8bSToomas Soome * allocations. This is useful for cases when close proximity of
55a3874b8bSToomas Soome * allocations is an important detail that needs to be represented
56a3874b8bSToomas Soome * in the range tree. See range_tree_set_gap(). The default behavior
57a3874b8bSToomas Soome * is not to bridge gaps (i.e. the maximum allowed gap size is 0).
58a3874b8bSToomas Soome *
59a3874b8bSToomas Soome * In order to traverse a range tree, use either the range_tree_walk()
60a3874b8bSToomas Soome * or range_tree_vacate() functions.
61a3874b8bSToomas Soome *
62a3874b8bSToomas Soome * To obtain more accurate information on individual segment
63a3874b8bSToomas Soome * operations that the range tree performs "under the hood", you can
64a3874b8bSToomas Soome * specify a set of callbacks by passing a range_tree_ops_t structure
65a3874b8bSToomas Soome * to the range_tree_create function. Any callbacks that are non-NULL
66a3874b8bSToomas Soome * are then called at the appropriate times.
67a3874b8bSToomas Soome *
68a3874b8bSToomas Soome * The range tree code also supports a special variant of range trees
69a3874b8bSToomas Soome * that can bridge small gaps between segments. This kind of tree is used
70a3874b8bSToomas Soome * by the dsl scanning code to group I/Os into mostly sequential chunks to
71a3874b8bSToomas Soome * optimize disk performance. The code here attempts to do this with as
72a3874b8bSToomas Soome * little memory and computational overhead as possible. One limitation of
73a3874b8bSToomas Soome * this implementation is that segments of range trees with gaps can only
74a3874b8bSToomas Soome * support removing complete segments.
75a3874b8bSToomas Soome */
76a3874b8bSToomas Soome
774d7988d6SPaul Dagnelie static inline void
rs_copy(range_seg_t * src,range_seg_t * dest,range_tree_t * rt)784d7988d6SPaul Dagnelie rs_copy(range_seg_t *src, range_seg_t *dest, range_tree_t *rt)
794d7988d6SPaul Dagnelie {
804d7988d6SPaul Dagnelie ASSERT3U(rt->rt_type, <=, RANGE_SEG_NUM_TYPES);
814d7988d6SPaul Dagnelie size_t size = 0;
824d7988d6SPaul Dagnelie switch (rt->rt_type) {
834d7988d6SPaul Dagnelie case RANGE_SEG32:
844d7988d6SPaul Dagnelie size = sizeof (range_seg32_t);
854d7988d6SPaul Dagnelie break;
864d7988d6SPaul Dagnelie case RANGE_SEG64:
874d7988d6SPaul Dagnelie size = sizeof (range_seg64_t);
884d7988d6SPaul Dagnelie break;
894d7988d6SPaul Dagnelie case RANGE_SEG_GAP:
904d7988d6SPaul Dagnelie size = sizeof (range_seg_gap_t);
914d7988d6SPaul Dagnelie break;
924d7988d6SPaul Dagnelie default:
934d7988d6SPaul Dagnelie VERIFY(0);
944d7988d6SPaul Dagnelie }
954d7988d6SPaul Dagnelie bcopy(src, dest, size);
960713e232SGeorge Wilson }
970713e232SGeorge Wilson
980713e232SGeorge Wilson void
range_tree_stat_verify(range_tree_t * rt)990713e232SGeorge Wilson range_tree_stat_verify(range_tree_t *rt)
1000713e232SGeorge Wilson {
1010713e232SGeorge Wilson range_seg_t *rs;
1024d7988d6SPaul Dagnelie zfs_btree_index_t where;
1030713e232SGeorge Wilson uint64_t hist[RANGE_TREE_HISTOGRAM_SIZE] = { 0 };
1040713e232SGeorge Wilson int i;
1050713e232SGeorge Wilson
1064d7988d6SPaul Dagnelie for (rs = zfs_btree_first(&rt->rt_root, &where); rs != NULL;
1074d7988d6SPaul Dagnelie rs = zfs_btree_next(&rt->rt_root, &where, &where)) {
1084d7988d6SPaul Dagnelie uint64_t size = rs_get_end(rs, rt) - rs_get_start(rs, rt);
109bf16b11eSMatthew Ahrens int idx = highbit64(size) - 1;
1100713e232SGeorge Wilson
1110713e232SGeorge Wilson hist[idx]++;
1120713e232SGeorge Wilson ASSERT3U(hist[idx], !=, 0);
1130713e232SGeorge Wilson }
1140713e232SGeorge Wilson
1150713e232SGeorge Wilson for (i = 0; i < RANGE_TREE_HISTOGRAM_SIZE; i++) {
1160713e232SGeorge Wilson if (hist[i] != rt->rt_histogram[i]) {
1170713e232SGeorge Wilson zfs_dbgmsg("i=%d, hist=%p, hist=%llu, rt_hist=%llu",
1180713e232SGeorge Wilson i, hist, hist[i], rt->rt_histogram[i]);
1190713e232SGeorge Wilson }
1200713e232SGeorge Wilson VERIFY3U(hist[i], ==, rt->rt_histogram[i]);
1210713e232SGeorge Wilson }
1220713e232SGeorge Wilson }
1230713e232SGeorge Wilson
1240713e232SGeorge Wilson static void
range_tree_stat_incr(range_tree_t * rt,range_seg_t * rs)1250713e232SGeorge Wilson range_tree_stat_incr(range_tree_t *rt, range_seg_t *rs)
1260713e232SGeorge Wilson {
1274d7988d6SPaul Dagnelie uint64_t size = rs_get_end(rs, rt) - rs_get_start(rs, rt);
128bf16b11eSMatthew Ahrens int idx = highbit64(size) - 1;
1290713e232SGeorge Wilson
1302e4c9986SGeorge Wilson ASSERT(size != 0);
1310713e232SGeorge Wilson ASSERT3U(idx, <,
1320713e232SGeorge Wilson sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram));
1330713e232SGeorge Wilson
1340713e232SGeorge Wilson rt->rt_histogram[idx]++;
1350713e232SGeorge Wilson ASSERT3U(rt->rt_histogram[idx], !=, 0);
1360713e232SGeorge Wilson }
1370713e232SGeorge Wilson
1380713e232SGeorge Wilson static void
range_tree_stat_decr(range_tree_t * rt,range_seg_t * rs)1390713e232SGeorge Wilson range_tree_stat_decr(range_tree_t *rt, range_seg_t *rs)
1400713e232SGeorge Wilson {
1414d7988d6SPaul Dagnelie uint64_t size = rs_get_end(rs, rt) - rs_get_start(rs, rt);
142bf16b11eSMatthew Ahrens int idx = highbit64(size) - 1;
1430713e232SGeorge Wilson
1442e4c9986SGeorge Wilson ASSERT(size != 0);
1450713e232SGeorge Wilson ASSERT3U(idx, <,
1460713e232SGeorge Wilson sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram));
1470713e232SGeorge Wilson
1480713e232SGeorge Wilson ASSERT3U(rt->rt_histogram[idx], !=, 0);
1490713e232SGeorge Wilson rt->rt_histogram[idx]--;
1500713e232SGeorge Wilson }
1510713e232SGeorge Wilson
1520713e232SGeorge Wilson static int
range_tree_seg32_compare(const void * x1,const void * x2)1534d7988d6SPaul Dagnelie range_tree_seg32_compare(const void *x1, const void *x2)
1544d7988d6SPaul Dagnelie {
1554d7988d6SPaul Dagnelie const range_seg32_t *r1 = x1;
1564d7988d6SPaul Dagnelie const range_seg32_t *r2 = x2;
1574d7988d6SPaul Dagnelie
1584d7988d6SPaul Dagnelie ASSERT3U(r1->rs_start, <=, r1->rs_end);
1594d7988d6SPaul Dagnelie ASSERT3U(r2->rs_start, <=, r2->rs_end);
1604d7988d6SPaul Dagnelie
1614d7988d6SPaul Dagnelie return ((r1->rs_start >= r2->rs_end) - (r1->rs_end <= r2->rs_start));
1624d7988d6SPaul Dagnelie }
1634d7988d6SPaul Dagnelie
1644d7988d6SPaul Dagnelie static int
range_tree_seg64_compare(const void * x1,const void * x2)1654d7988d6SPaul Dagnelie range_tree_seg64_compare(const void *x1, const void *x2)
1664d7988d6SPaul Dagnelie {
1674d7988d6SPaul Dagnelie const range_seg64_t *r1 = x1;
1684d7988d6SPaul Dagnelie const range_seg64_t *r2 = x2;
1694d7988d6SPaul Dagnelie
1704d7988d6SPaul Dagnelie ASSERT3U(r1->rs_start, <=, r1->rs_end);
1714d7988d6SPaul Dagnelie ASSERT3U(r2->rs_start, <=, r2->rs_end);
1724d7988d6SPaul Dagnelie
1734d7988d6SPaul Dagnelie return ((r1->rs_start >= r2->rs_end) - (r1->rs_end <= r2->rs_start));
1744d7988d6SPaul Dagnelie }
1754d7988d6SPaul Dagnelie
1764d7988d6SPaul Dagnelie static int
range_tree_seg_gap_compare(const void * x1,const void * x2)1774d7988d6SPaul Dagnelie range_tree_seg_gap_compare(const void *x1, const void *x2)
1780713e232SGeorge Wilson {
1794d7988d6SPaul Dagnelie const range_seg_gap_t *r1 = x1;
1804d7988d6SPaul Dagnelie const range_seg_gap_t *r2 = x2;
1810713e232SGeorge Wilson
182c4ab0d3fSGvozden Neskovic ASSERT3U(r1->rs_start, <=, r1->rs_end);
183c4ab0d3fSGvozden Neskovic ASSERT3U(r2->rs_start, <=, r2->rs_end);
184c4ab0d3fSGvozden Neskovic
185c4ab0d3fSGvozden Neskovic return ((r1->rs_start >= r2->rs_end) - (r1->rs_end <= r2->rs_start));
1860713e232SGeorge Wilson }
1870713e232SGeorge Wilson
1880713e232SGeorge Wilson range_tree_t *
range_tree_create_impl(range_tree_ops_t * ops,range_seg_type_t type,void * arg,uint64_t start,uint64_t shift,int (* zfs_btree_compare)(const void *,const void *),uint64_t gap)1894d7988d6SPaul Dagnelie range_tree_create_impl(range_tree_ops_t *ops, range_seg_type_t type, void *arg,
1904d7988d6SPaul Dagnelie uint64_t start, uint64_t shift,
1914d7988d6SPaul Dagnelie int (*zfs_btree_compare) (const void *, const void *),
1924d7988d6SPaul Dagnelie uint64_t gap)
1930713e232SGeorge Wilson {
194a3874b8bSToomas Soome range_tree_t *rt = kmem_zalloc(sizeof (range_tree_t), KM_SLEEP);
1950713e232SGeorge Wilson
1964d7988d6SPaul Dagnelie ASSERT3U(shift, <, 64);
1974d7988d6SPaul Dagnelie ASSERT3U(type, <=, RANGE_SEG_NUM_TYPES);
1984d7988d6SPaul Dagnelie size_t size;
1994d7988d6SPaul Dagnelie int (*compare) (const void *, const void *);
2004d7988d6SPaul Dagnelie switch (type) {
2014d7988d6SPaul Dagnelie case RANGE_SEG32:
2024d7988d6SPaul Dagnelie size = sizeof (range_seg32_t);
2034d7988d6SPaul Dagnelie compare = range_tree_seg32_compare;
2044d7988d6SPaul Dagnelie break;
2054d7988d6SPaul Dagnelie case RANGE_SEG64:
2064d7988d6SPaul Dagnelie size = sizeof (range_seg64_t);
2074d7988d6SPaul Dagnelie compare = range_tree_seg64_compare;
2084d7988d6SPaul Dagnelie break;
2094d7988d6SPaul Dagnelie case RANGE_SEG_GAP:
2104d7988d6SPaul Dagnelie size = sizeof (range_seg_gap_t);
2114d7988d6SPaul Dagnelie compare = range_tree_seg_gap_compare;
2124d7988d6SPaul Dagnelie break;
2134d7988d6SPaul Dagnelie default:
2144d7988d6SPaul Dagnelie panic("Invalid range seg type %d", type);
2154d7988d6SPaul Dagnelie }
2164d7988d6SPaul Dagnelie zfs_btree_create(&rt->rt_root, compare, size);
2170713e232SGeorge Wilson
2180713e232SGeorge Wilson rt->rt_ops = ops;
2190713e232SGeorge Wilson rt->rt_arg = arg;
220a3874b8bSToomas Soome rt->rt_gap = gap;
2214d7988d6SPaul Dagnelie rt->rt_type = type;
2224d7988d6SPaul Dagnelie rt->rt_start = start;
2234d7988d6SPaul Dagnelie rt->rt_shift = shift;
2244d7988d6SPaul Dagnelie rt->rt_btree_compare = zfs_btree_compare;
2250713e232SGeorge Wilson
226a3874b8bSToomas Soome if (rt->rt_ops != NULL && rt->rt_ops->rtop_create != NULL)
2270713e232SGeorge Wilson rt->rt_ops->rtop_create(rt, rt->rt_arg);
2280713e232SGeorge Wilson
2290713e232SGeorge Wilson return (rt);
2300713e232SGeorge Wilson }
2310713e232SGeorge Wilson
232a3874b8bSToomas Soome range_tree_t *
range_tree_create(range_tree_ops_t * ops,range_seg_type_t type,void * arg,uint64_t start,uint64_t shift)2334d7988d6SPaul Dagnelie range_tree_create(range_tree_ops_t *ops, range_seg_type_t type,
2344d7988d6SPaul Dagnelie void *arg, uint64_t start, uint64_t shift)
235a3874b8bSToomas Soome {
2364d7988d6SPaul Dagnelie return (range_tree_create_impl(ops, type, arg, start, shift, NULL, 0));
237a3874b8bSToomas Soome }
238a3874b8bSToomas Soome
2390713e232SGeorge Wilson void
range_tree_destroy(range_tree_t * rt)2400713e232SGeorge Wilson range_tree_destroy(range_tree_t *rt)
2410713e232SGeorge Wilson {
2420713e232SGeorge Wilson VERIFY0(rt->rt_space);
2430713e232SGeorge Wilson
244a3874b8bSToomas Soome if (rt->rt_ops != NULL && rt->rt_ops->rtop_destroy != NULL)
2450713e232SGeorge Wilson rt->rt_ops->rtop_destroy(rt, rt->rt_arg);
2460713e232SGeorge Wilson
2474d7988d6SPaul Dagnelie zfs_btree_destroy(&rt->rt_root);
2480713e232SGeorge Wilson kmem_free(rt, sizeof (*rt));
2490713e232SGeorge Wilson }
2500713e232SGeorge Wilson
2510713e232SGeorge Wilson void
range_tree_adjust_fill(range_tree_t * rt,range_seg_t * rs,int64_t delta)252a3874b8bSToomas Soome range_tree_adjust_fill(range_tree_t *rt, range_seg_t *rs, int64_t delta)
253a3874b8bSToomas Soome {
2544d7988d6SPaul Dagnelie ASSERT3U(rs_get_fill(rs, rt) + delta, !=, 0);
2554d7988d6SPaul Dagnelie ASSERT3U(rs_get_fill(rs, rt) + delta, <=, rs_get_end(rs, rt) -
2564d7988d6SPaul Dagnelie rs_get_start(rs, rt));
257a3874b8bSToomas Soome
258a3874b8bSToomas Soome if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
259a3874b8bSToomas Soome rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);
2604d7988d6SPaul Dagnelie rs_set_fill(rs, rt, rs_get_fill(rs, rt) + delta);
261a3874b8bSToomas Soome if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)
262a3874b8bSToomas Soome rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);
263a3874b8bSToomas Soome }
264a3874b8bSToomas Soome
265a3874b8bSToomas Soome static void
range_tree_add_impl(void * arg,uint64_t start,uint64_t size,uint64_t fill)266a3874b8bSToomas Soome range_tree_add_impl(void *arg, uint64_t start, uint64_t size, uint64_t fill)
2670713e232SGeorge Wilson {
2680713e232SGeorge Wilson range_tree_t *rt = arg;
2694d7988d6SPaul Dagnelie zfs_btree_index_t where;
2704d7988d6SPaul Dagnelie range_seg_t *rs_before, *rs_after, *rs;
2714d7988d6SPaul Dagnelie range_seg_max_t tmp, rsearch;
272a3874b8bSToomas Soome uint64_t end = start + size, gap = rt->rt_gap;
273a3874b8bSToomas Soome uint64_t bridge_size = 0;
2740713e232SGeorge Wilson boolean_t merge_before, merge_after;
2750713e232SGeorge Wilson
276a3874b8bSToomas Soome ASSERT3U(size, !=, 0);
277a3874b8bSToomas Soome ASSERT3U(fill, <=, size);
2784d7988d6SPaul Dagnelie ASSERT3U(start + size, >, start);
2790713e232SGeorge Wilson
2804d7988d6SPaul Dagnelie rs_set_start(&rsearch, rt, start);
2814d7988d6SPaul Dagnelie rs_set_end(&rsearch, rt, end);
2824d7988d6SPaul Dagnelie rs = zfs_btree_find(&rt->rt_root, &rsearch, &where);
2830713e232SGeorge Wilson
284a3874b8bSToomas Soome /*
285a3874b8bSToomas Soome * If this is a gap-supporting range tree, it is possible that we
286a3874b8bSToomas Soome * are inserting into an existing segment. In this case simply
287a3874b8bSToomas Soome * bump the fill count and call the remove / add callbacks. If the
288a3874b8bSToomas Soome * new range will extend an existing segment, we remove the
289a3874b8bSToomas Soome * existing one, apply the new extent to it and re-insert it using
290a3874b8bSToomas Soome * the normal code paths.
291a3874b8bSToomas Soome */
292a3874b8bSToomas Soome if (rs != NULL) {
2934d7988d6SPaul Dagnelie ASSERT3U(rt->rt_gap, !=, 0);
2944d7988d6SPaul Dagnelie uint64_t rstart = rs_get_start(rs, rt);
2954d7988d6SPaul Dagnelie uint64_t rend = rs_get_end(rs, rt);
296a3874b8bSToomas Soome ASSERT3U(gap, !=, 0);
2974d7988d6SPaul Dagnelie if (rstart <= start && rend >= end) {
298a3874b8bSToomas Soome range_tree_adjust_fill(rt, rs, fill);
299a3874b8bSToomas Soome return;
300a3874b8bSToomas Soome }
301a3874b8bSToomas Soome
3024d7988d6SPaul Dagnelie zfs_btree_remove(&rt->rt_root, rs);
303a3874b8bSToomas Soome if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
304a3874b8bSToomas Soome rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);
305a3874b8bSToomas Soome
306a3874b8bSToomas Soome range_tree_stat_decr(rt, rs);
3074d7988d6SPaul Dagnelie rt->rt_space -= rend - rstart;
308a3874b8bSToomas Soome
3094d7988d6SPaul Dagnelie fill += rs_get_fill(rs, rt);
3104d7988d6SPaul Dagnelie start = MIN(start, rstart);
3114d7988d6SPaul Dagnelie end = MAX(end, rend);
312a3874b8bSToomas Soome size = end - start;
313a3874b8bSToomas Soome
314a3874b8bSToomas Soome range_tree_add_impl(rt, start, size, fill);
315a3874b8bSToomas Soome return;
316a3874b8bSToomas Soome }
3170713e232SGeorge Wilson
318a3874b8bSToomas Soome ASSERT3P(rs, ==, NULL);
319a3874b8bSToomas Soome
320a3874b8bSToomas Soome /*
321a3874b8bSToomas Soome * Determine whether or not we will have to merge with our neighbors.
322a3874b8bSToomas Soome * If gap != 0, we might need to merge with our neighbors even if we
323a3874b8bSToomas Soome * aren't directly touching.
324a3874b8bSToomas Soome */
3254d7988d6SPaul Dagnelie zfs_btree_index_t where_before, where_after;
3264d7988d6SPaul Dagnelie rs_before = zfs_btree_prev(&rt->rt_root, &where, &where_before);
3274d7988d6SPaul Dagnelie rs_after = zfs_btree_next(&rt->rt_root, &where, &where_after);
3280713e232SGeorge Wilson
3294d7988d6SPaul Dagnelie merge_before = (rs_before != NULL && rs_get_end(rs_before, rt) >=
3304d7988d6SPaul Dagnelie start - gap);
3314d7988d6SPaul Dagnelie merge_after = (rs_after != NULL && rs_get_start(rs_after, rt) <= end +
3324d7988d6SPaul Dagnelie gap);
333a3874b8bSToomas Soome
334a3874b8bSToomas Soome if (merge_before && gap != 0)
3354d7988d6SPaul Dagnelie bridge_size += start - rs_get_end(rs_before, rt);
336a3874b8bSToomas Soome if (merge_after && gap != 0)
3374d7988d6SPaul Dagnelie bridge_size += rs_get_start(rs_after, rt) - end;
3380713e232SGeorge Wilson
3390713e232SGeorge Wilson if (merge_before && merge_after) {
340a3874b8bSToomas Soome if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL) {
3410713e232SGeorge Wilson rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg);
3420713e232SGeorge Wilson rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg);
3430713e232SGeorge Wilson }
3440713e232SGeorge Wilson
3450713e232SGeorge Wilson range_tree_stat_decr(rt, rs_before);
3460713e232SGeorge Wilson range_tree_stat_decr(rt, rs_after);
3470713e232SGeorge Wilson
3484d7988d6SPaul Dagnelie rs_copy(rs_after, &tmp, rt);
3494d7988d6SPaul Dagnelie uint64_t before_start = rs_get_start_raw(rs_before, rt);
3504d7988d6SPaul Dagnelie uint64_t before_fill = rs_get_fill(rs_before, rt);
3514d7988d6SPaul Dagnelie uint64_t after_fill = rs_get_fill(rs_after, rt);
352*bfb9edc9SPaul Dagnelie zfs_btree_remove_idx(&rt->rt_root, &where_before);
3534d7988d6SPaul Dagnelie
3544d7988d6SPaul Dagnelie /*
3554d7988d6SPaul Dagnelie * We have to re-find the node because our old reference is
3564d7988d6SPaul Dagnelie * invalid as soon as we do any mutating btree operations.
3574d7988d6SPaul Dagnelie */
3584d7988d6SPaul Dagnelie rs_after = zfs_btree_find(&rt->rt_root, &tmp, &where_after);
3594d7988d6SPaul Dagnelie rs_set_start_raw(rs_after, rt, before_start);
3604d7988d6SPaul Dagnelie rs_set_fill(rs_after, rt, after_fill + before_fill + fill);
3610713e232SGeorge Wilson rs = rs_after;
3620713e232SGeorge Wilson } else if (merge_before) {
363a3874b8bSToomas Soome if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
3640713e232SGeorge Wilson rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg);
3650713e232SGeorge Wilson
3660713e232SGeorge Wilson range_tree_stat_decr(rt, rs_before);
3670713e232SGeorge Wilson
3684d7988d6SPaul Dagnelie uint64_t before_fill = rs_get_fill(rs_before, rt);
3694d7988d6SPaul Dagnelie rs_set_end(rs_before, rt, end);
3704d7988d6SPaul Dagnelie rs_set_fill(rs_before, rt, before_fill + fill);
3710713e232SGeorge Wilson rs = rs_before;
3720713e232SGeorge Wilson } else if (merge_after) {
373a3874b8bSToomas Soome if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
3740713e232SGeorge Wilson rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg);
3750713e232SGeorge Wilson
3760713e232SGeorge Wilson range_tree_stat_decr(rt, rs_after);
3770713e232SGeorge Wilson
3784d7988d6SPaul Dagnelie uint64_t after_fill = rs_get_fill(rs_after, rt);
3794d7988d6SPaul Dagnelie rs_set_start(rs_after, rt, start);
3804d7988d6SPaul Dagnelie rs_set_fill(rs_after, rt, after_fill + fill);
3810713e232SGeorge Wilson rs = rs_after;
3820713e232SGeorge Wilson } else {
3834d7988d6SPaul Dagnelie rs = &tmp;
384a3874b8bSToomas Soome
3854d7988d6SPaul Dagnelie rs_set_start(rs, rt, start);
3864d7988d6SPaul Dagnelie rs_set_end(rs, rt, end);
3874d7988d6SPaul Dagnelie rs_set_fill(rs, rt, fill);
388*bfb9edc9SPaul Dagnelie zfs_btree_add_idx(&rt->rt_root, rs, &where);
3890713e232SGeorge Wilson }
3900713e232SGeorge Wilson
3914d7988d6SPaul Dagnelie if (gap != 0) {
3924d7988d6SPaul Dagnelie ASSERT3U(rs_get_fill(rs, rt), <=, rs_get_end(rs, rt) -
3934d7988d6SPaul Dagnelie rs_get_start(rs, rt));
3944d7988d6SPaul Dagnelie } else {
3954d7988d6SPaul Dagnelie ASSERT3U(rs_get_fill(rs, rt), ==, rs_get_end(rs, rt) -
3964d7988d6SPaul Dagnelie rs_get_start(rs, rt));
3974d7988d6SPaul Dagnelie }
398a3874b8bSToomas Soome
399a3874b8bSToomas Soome if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)
4000713e232SGeorge Wilson rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);
4010713e232SGeorge Wilson
4020713e232SGeorge Wilson range_tree_stat_incr(rt, rs);
403a3874b8bSToomas Soome rt->rt_space += size + bridge_size;
4040713e232SGeorge Wilson }
4050713e232SGeorge Wilson
4060713e232SGeorge Wilson void
range_tree_add(void * arg,uint64_t start,uint64_t size)407a3874b8bSToomas Soome range_tree_add(void *arg, uint64_t start, uint64_t size)
408a3874b8bSToomas Soome {
409a3874b8bSToomas Soome range_tree_add_impl(arg, start, size, size);
410a3874b8bSToomas Soome }
411a3874b8bSToomas Soome
412a3874b8bSToomas Soome static void
range_tree_remove_impl(range_tree_t * rt,uint64_t start,uint64_t size,boolean_t do_fill)413a3874b8bSToomas Soome range_tree_remove_impl(range_tree_t *rt, uint64_t start, uint64_t size,
414a3874b8bSToomas Soome boolean_t do_fill)
4150713e232SGeorge Wilson {
4164d7988d6SPaul Dagnelie zfs_btree_index_t where;
4174d7988d6SPaul Dagnelie range_seg_t *rs;
4184d7988d6SPaul Dagnelie range_seg_max_t rsearch, rs_tmp;
4190713e232SGeorge Wilson uint64_t end = start + size;
4200713e232SGeorge Wilson boolean_t left_over, right_over;
4210713e232SGeorge Wilson
4220713e232SGeorge Wilson VERIFY3U(size, !=, 0);
4230713e232SGeorge Wilson VERIFY3U(size, <=, rt->rt_space);
4244d7988d6SPaul Dagnelie if (rt->rt_type == RANGE_SEG64)
4254d7988d6SPaul Dagnelie ASSERT3U(start + size, >, start);
4260713e232SGeorge Wilson
4274d7988d6SPaul Dagnelie rs_set_start(&rsearch, rt, start);
4284d7988d6SPaul Dagnelie rs_set_end(&rsearch, rt, end);
4294d7988d6SPaul Dagnelie rs = zfs_btree_find(&rt->rt_root, &rsearch, &where);
4300713e232SGeorge Wilson
4310713e232SGeorge Wilson /* Make sure we completely overlap with someone */
4320713e232SGeorge Wilson if (rs == NULL) {
4334d7988d6SPaul Dagnelie zfs_panic_recover("zfs: removing nonexistent segment from "
4344d7988d6SPaul Dagnelie "range tree (offset=%llu size=%llu)",
4350713e232SGeorge Wilson (longlong_t)start, (longlong_t)size);
4360713e232SGeorge Wilson return;
4370713e232SGeorge Wilson }
438a3874b8bSToomas Soome
439a3874b8bSToomas Soome /*
440a3874b8bSToomas Soome * Range trees with gap support must only remove complete segments
441a3874b8bSToomas Soome * from the tree. This allows us to maintain accurate fill accounting
442a3874b8bSToomas Soome * and to ensure that bridged sections are not leaked. If we need to
443a3874b8bSToomas Soome * remove less than the full segment, we can only adjust the fill count.
444a3874b8bSToomas Soome */
445a3874b8bSToomas Soome if (rt->rt_gap != 0) {
446a3874b8bSToomas Soome if (do_fill) {
4474d7988d6SPaul Dagnelie if (rs_get_fill(rs, rt) == size) {
4484d7988d6SPaul Dagnelie start = rs_get_start(rs, rt);
4494d7988d6SPaul Dagnelie end = rs_get_end(rs, rt);
450a3874b8bSToomas Soome size = end - start;
451a3874b8bSToomas Soome } else {
452a3874b8bSToomas Soome range_tree_adjust_fill(rt, rs, -size);
453a3874b8bSToomas Soome return;
454a3874b8bSToomas Soome }
4554d7988d6SPaul Dagnelie } else if (rs_get_start(rs, rt) != start ||
4564d7988d6SPaul Dagnelie rs_get_end(rs, rt) != end) {
457a3874b8bSToomas Soome zfs_panic_recover("zfs: freeing partial segment of "
458a3874b8bSToomas Soome "gap tree (offset=%llu size=%llu) of "
459a3874b8bSToomas Soome "(offset=%llu size=%llu)",
460a3874b8bSToomas Soome (longlong_t)start, (longlong_t)size,
4614d7988d6SPaul Dagnelie (longlong_t)rs_get_start(rs, rt),
4624d7988d6SPaul Dagnelie (longlong_t)rs_get_end(rs, rt) - rs_get_start(rs,
4634d7988d6SPaul Dagnelie rt));
464a3874b8bSToomas Soome return;
465a3874b8bSToomas Soome }
466a3874b8bSToomas Soome }
467a3874b8bSToomas Soome
4684d7988d6SPaul Dagnelie VERIFY3U(rs_get_start(rs, rt), <=, start);
4694d7988d6SPaul Dagnelie VERIFY3U(rs_get_end(rs, rt), >=, end);
4700713e232SGeorge Wilson
4714d7988d6SPaul Dagnelie left_over = (rs_get_start(rs, rt) != start);
4724d7988d6SPaul Dagnelie right_over = (rs_get_end(rs, rt) != end);
4730713e232SGeorge Wilson
4740713e232SGeorge Wilson range_tree_stat_decr(rt, rs);
4750713e232SGeorge Wilson
476a3874b8bSToomas Soome if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
4770713e232SGeorge Wilson rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);
4780713e232SGeorge Wilson
4790713e232SGeorge Wilson if (left_over && right_over) {
4804d7988d6SPaul Dagnelie range_seg_max_t newseg;
4814d7988d6SPaul Dagnelie rs_set_start(&newseg, rt, end);
4824d7988d6SPaul Dagnelie rs_set_end_raw(&newseg, rt, rs_get_end_raw(rs, rt));
4834d7988d6SPaul Dagnelie rs_set_fill(&newseg, rt, rs_get_end(rs, rt) - end);
4844d7988d6SPaul Dagnelie range_tree_stat_incr(rt, &newseg);
4850713e232SGeorge Wilson
4864d7988d6SPaul Dagnelie // This modifies the buffer already inside the range tree
4874d7988d6SPaul Dagnelie rs_set_end(rs, rt, start);
4884d7988d6SPaul Dagnelie
4894d7988d6SPaul Dagnelie rs_copy(rs, &rs_tmp, rt);
4904d7988d6SPaul Dagnelie if (zfs_btree_next(&rt->rt_root, &where, &where) != NULL)
491*bfb9edc9SPaul Dagnelie zfs_btree_add_idx(&rt->rt_root, &newseg, &where);
4924d7988d6SPaul Dagnelie else
4934d7988d6SPaul Dagnelie zfs_btree_add(&rt->rt_root, &newseg);
4940713e232SGeorge Wilson
495a3874b8bSToomas Soome if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)
4964d7988d6SPaul Dagnelie rt->rt_ops->rtop_add(rt, &newseg, rt->rt_arg);
4970713e232SGeorge Wilson } else if (left_over) {
4984d7988d6SPaul Dagnelie // This modifies the buffer already inside the range tree
4994d7988d6SPaul Dagnelie rs_set_end(rs, rt, start);
5004d7988d6SPaul Dagnelie rs_copy(rs, &rs_tmp, rt);
5010713e232SGeorge Wilson } else if (right_over) {
5024d7988d6SPaul Dagnelie // This modifies the buffer already inside the range tree
5034d7988d6SPaul Dagnelie rs_set_start(rs, rt, end);
5044d7988d6SPaul Dagnelie rs_copy(rs, &rs_tmp, rt);
5050713e232SGeorge Wilson } else {
506*bfb9edc9SPaul Dagnelie zfs_btree_remove_idx(&rt->rt_root, &where);
5070713e232SGeorge Wilson rs = NULL;
5080713e232SGeorge Wilson }
5090713e232SGeorge Wilson
5100713e232SGeorge Wilson if (rs != NULL) {
511a3874b8bSToomas Soome /*
512a3874b8bSToomas Soome * The fill of the leftover segment will always be equal to
513a3874b8bSToomas Soome * the size, since we do not support removing partial segments
514a3874b8bSToomas Soome * of range trees with gaps.
515a3874b8bSToomas Soome */
5164d7988d6SPaul Dagnelie rs_set_fill_raw(rs, rt, rs_get_end_raw(rs, rt) -
5174d7988d6SPaul Dagnelie rs_get_start_raw(rs, rt));
5184d7988d6SPaul Dagnelie range_tree_stat_incr(rt, &rs_tmp);
5190713e232SGeorge Wilson
520a3874b8bSToomas Soome if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)
5214d7988d6SPaul Dagnelie rt->rt_ops->rtop_add(rt, &rs_tmp, rt->rt_arg);
5220713e232SGeorge Wilson }
5230713e232SGeorge Wilson
5240713e232SGeorge Wilson rt->rt_space -= size;
5250713e232SGeorge Wilson }
5260713e232SGeorge Wilson
527a3874b8bSToomas Soome void
range_tree_remove(void * arg,uint64_t start,uint64_t size)528a3874b8bSToomas Soome range_tree_remove(void *arg, uint64_t start, uint64_t size)
529a3874b8bSToomas Soome {
530a3874b8bSToomas Soome range_tree_remove_impl(arg, start, size, B_FALSE);
531a3874b8bSToomas Soome }
532a3874b8bSToomas Soome
533a3874b8bSToomas Soome void
range_tree_remove_fill(range_tree_t * rt,uint64_t start,uint64_t size)534a3874b8bSToomas Soome range_tree_remove_fill(range_tree_t *rt, uint64_t start, uint64_t size)
535a3874b8bSToomas Soome {
536a3874b8bSToomas Soome range_tree_remove_impl(rt, start, size, B_TRUE);
537a3874b8bSToomas Soome }
538a3874b8bSToomas Soome
539a3874b8bSToomas Soome void
range_tree_resize_segment(range_tree_t * rt,range_seg_t * rs,uint64_t newstart,uint64_t newsize)540a3874b8bSToomas Soome range_tree_resize_segment(range_tree_t *rt, range_seg_t *rs,
541a3874b8bSToomas Soome uint64_t newstart, uint64_t newsize)
542a3874b8bSToomas Soome {
5434d7988d6SPaul Dagnelie int64_t delta = newsize - (rs_get_end(rs, rt) - rs_get_start(rs, rt));
544a3874b8bSToomas Soome
545a3874b8bSToomas Soome range_tree_stat_decr(rt, rs);
546a3874b8bSToomas Soome if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
547a3874b8bSToomas Soome rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);
548a3874b8bSToomas Soome
5494d7988d6SPaul Dagnelie rs_set_start(rs, rt, newstart);
5504d7988d6SPaul Dagnelie rs_set_end(rs, rt, newstart + newsize);
551a3874b8bSToomas Soome
552a3874b8bSToomas Soome range_tree_stat_incr(rt, rs);
553a3874b8bSToomas Soome if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)
554a3874b8bSToomas Soome rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);
555a3874b8bSToomas Soome
556a3874b8bSToomas Soome rt->rt_space += delta;
557a3874b8bSToomas Soome }
558a3874b8bSToomas Soome
5590713e232SGeorge Wilson static range_seg_t *
range_tree_find_impl(range_tree_t * rt,uint64_t start,uint64_t size)560bf16b11eSMatthew Ahrens range_tree_find_impl(range_tree_t *rt, uint64_t start, uint64_t size)
5610713e232SGeorge Wilson {
5624d7988d6SPaul Dagnelie range_seg_max_t rsearch;
5630713e232SGeorge Wilson uint64_t end = start + size;
5640713e232SGeorge Wilson
5650713e232SGeorge Wilson VERIFY(size != 0);
5660713e232SGeorge Wilson
5674d7988d6SPaul Dagnelie rs_set_start(&rsearch, rt, start);
5684d7988d6SPaul Dagnelie rs_set_end(&rsearch, rt, end);
5694d7988d6SPaul Dagnelie return (zfs_btree_find(&rt->rt_root, &rsearch, NULL));
570bf16b11eSMatthew Ahrens }
5710713e232SGeorge Wilson
572a3874b8bSToomas Soome range_seg_t *
range_tree_find(range_tree_t * rt,uint64_t start,uint64_t size)573bf16b11eSMatthew Ahrens range_tree_find(range_tree_t *rt, uint64_t start, uint64_t size)
574bf16b11eSMatthew Ahrens {
5754d7988d6SPaul Dagnelie if (rt->rt_type == RANGE_SEG64)
5764d7988d6SPaul Dagnelie ASSERT3U(start + size, >, start);
5774d7988d6SPaul Dagnelie
578bf16b11eSMatthew Ahrens range_seg_t *rs = range_tree_find_impl(rt, start, size);
5794d7988d6SPaul Dagnelie if (rs != NULL && rs_get_start(rs, rt) <= start &&
5804d7988d6SPaul Dagnelie rs_get_end(rs, rt) >= start + size) {
5810713e232SGeorge Wilson return (rs);
5824d7988d6SPaul Dagnelie }
5830713e232SGeorge Wilson return (NULL);
5840713e232SGeorge Wilson }
5850713e232SGeorge Wilson
5860713e232SGeorge Wilson void
range_tree_verify_not_present(range_tree_t * rt,uint64_t off,uint64_t size)587555d674dSSerapheim Dimitropoulos range_tree_verify_not_present(range_tree_t *rt, uint64_t off, uint64_t size)
5880713e232SGeorge Wilson {
589555d674dSSerapheim Dimitropoulos range_seg_t *rs = range_tree_find(rt, off, size);
5900713e232SGeorge Wilson if (rs != NULL)
591555d674dSSerapheim Dimitropoulos panic("segment already in tree; rs=%p", (void *)rs);
5920713e232SGeorge Wilson }
5930713e232SGeorge Wilson
5940713e232SGeorge Wilson boolean_t
range_tree_contains(range_tree_t * rt,uint64_t start,uint64_t size)5950713e232SGeorge Wilson range_tree_contains(range_tree_t *rt, uint64_t start, uint64_t size)
5960713e232SGeorge Wilson {
597bf16b11eSMatthew Ahrens return (range_tree_find(rt, start, size) != NULL);
598bf16b11eSMatthew Ahrens }
5990713e232SGeorge Wilson
600af1d63abSPaul Dagnelie /*
601af1d63abSPaul Dagnelie * Returns the first subset of the given range which overlaps with the range
602af1d63abSPaul Dagnelie * tree. Returns true if there is a segment in the range, and false if there
603af1d63abSPaul Dagnelie * isn't.
604af1d63abSPaul Dagnelie */
605af1d63abSPaul Dagnelie boolean_t
range_tree_find_in(range_tree_t * rt,uint64_t start,uint64_t size,uint64_t * ostart,uint64_t * osize)606af1d63abSPaul Dagnelie range_tree_find_in(range_tree_t *rt, uint64_t start, uint64_t size,
607af1d63abSPaul Dagnelie uint64_t *ostart, uint64_t *osize)
608af1d63abSPaul Dagnelie {
6094d7988d6SPaul Dagnelie if (rt->rt_type == RANGE_SEG64)
6104d7988d6SPaul Dagnelie ASSERT3U(start + size, >, start);
6114d7988d6SPaul Dagnelie
6124d7988d6SPaul Dagnelie range_seg_max_t rsearch;
6134d7988d6SPaul Dagnelie rs_set_start(&rsearch, rt, start);
6144d7988d6SPaul Dagnelie rs_set_end_raw(&rsearch, rt, rs_get_start_raw(&rsearch, rt) + 1);
615af1d63abSPaul Dagnelie
6164d7988d6SPaul Dagnelie zfs_btree_index_t where;
6174d7988d6SPaul Dagnelie range_seg_t *rs = zfs_btree_find(&rt->rt_root, &rsearch, &where);
618af1d63abSPaul Dagnelie if (rs != NULL) {
619af1d63abSPaul Dagnelie *ostart = start;
6204d7988d6SPaul Dagnelie *osize = MIN(size, rs_get_end(rs, rt) - start);
621af1d63abSPaul Dagnelie return (B_TRUE);
622af1d63abSPaul Dagnelie }
623af1d63abSPaul Dagnelie
6244d7988d6SPaul Dagnelie rs = zfs_btree_next(&rt->rt_root, &where, &where);
6254d7988d6SPaul Dagnelie if (rs == NULL || rs_get_start(rs, rt) > start + size)
626af1d63abSPaul Dagnelie return (B_FALSE);
627af1d63abSPaul Dagnelie
6284d7988d6SPaul Dagnelie *ostart = rs_get_start(rs, rt);
6294d7988d6SPaul Dagnelie *osize = MIN(start + size, rs_get_end(rs, rt)) -
6304d7988d6SPaul Dagnelie rs_get_start(rs, rt);
631af1d63abSPaul Dagnelie return (B_TRUE);
632af1d63abSPaul Dagnelie }
633af1d63abSPaul Dagnelie
634bf16b11eSMatthew Ahrens /*
635bf16b11eSMatthew Ahrens * Ensure that this range is not in the tree, regardless of whether
636bf16b11eSMatthew Ahrens * it is currently in the tree.
637bf16b11eSMatthew Ahrens */
638bf16b11eSMatthew Ahrens void
range_tree_clear(range_tree_t * rt,uint64_t start,uint64_t size)639bf16b11eSMatthew Ahrens range_tree_clear(range_tree_t *rt, uint64_t start, uint64_t size)
640bf16b11eSMatthew Ahrens {
641bf16b11eSMatthew Ahrens range_seg_t *rs;
642bf16b11eSMatthew Ahrens
6435cabbc6bSPrashanth Sreenivasa if (size == 0)
6445cabbc6bSPrashanth Sreenivasa return;
6455cabbc6bSPrashanth Sreenivasa
6464d7988d6SPaul Dagnelie if (rt->rt_type == RANGE_SEG64)
6474d7988d6SPaul Dagnelie ASSERT3U(start + size, >, start);
6484d7988d6SPaul Dagnelie
649bf16b11eSMatthew Ahrens while ((rs = range_tree_find_impl(rt, start, size)) != NULL) {
6504d7988d6SPaul Dagnelie uint64_t free_start = MAX(rs_get_start(rs, rt), start);
6514d7988d6SPaul Dagnelie uint64_t free_end = MIN(rs_get_end(rs, rt), start + size);
652bf16b11eSMatthew Ahrens range_tree_remove(rt, free_start, free_end - free_start);
653bf16b11eSMatthew Ahrens }
6540713e232SGeorge Wilson }
6550713e232SGeorge Wilson
6560713e232SGeorge Wilson void
range_tree_swap(range_tree_t ** rtsrc,range_tree_t ** rtdst)6570713e232SGeorge Wilson range_tree_swap(range_tree_t **rtsrc, range_tree_t **rtdst)
6580713e232SGeorge Wilson {
6590713e232SGeorge Wilson range_tree_t *rt;
6600713e232SGeorge Wilson
6610713e232SGeorge Wilson ASSERT0(range_tree_space(*rtdst));
6624d7988d6SPaul Dagnelie ASSERT0(zfs_btree_numnodes(&(*rtdst)->rt_root));
6630713e232SGeorge Wilson
6640713e232SGeorge Wilson rt = *rtsrc;
6650713e232SGeorge Wilson *rtsrc = *rtdst;
6660713e232SGeorge Wilson *rtdst = rt;
6670713e232SGeorge Wilson }
6680713e232SGeorge Wilson
6690713e232SGeorge Wilson void
range_tree_vacate(range_tree_t * rt,range_tree_func_t * func,void * arg)6700713e232SGeorge Wilson range_tree_vacate(range_tree_t *rt, range_tree_func_t *func, void *arg)
6710713e232SGeorge Wilson {
6720713e232SGeorge Wilson
673a3874b8bSToomas Soome if (rt->rt_ops != NULL && rt->rt_ops->rtop_vacate != NULL)
6740713e232SGeorge Wilson rt->rt_ops->rtop_vacate(rt, rt->rt_arg);
6750713e232SGeorge Wilson
6764d7988d6SPaul Dagnelie if (func != NULL) {
6774d7988d6SPaul Dagnelie range_seg_t *rs;
6784d7988d6SPaul Dagnelie zfs_btree_index_t *cookie = NULL;
6794d7988d6SPaul Dagnelie
6804d7988d6SPaul Dagnelie while ((rs = zfs_btree_destroy_nodes(&rt->rt_root, &cookie)) !=
6814d7988d6SPaul Dagnelie NULL) {
6824d7988d6SPaul Dagnelie func(arg, rs_get_start(rs, rt), rs_get_end(rs, rt) -
6834d7988d6SPaul Dagnelie rs_get_start(rs, rt));
6844d7988d6SPaul Dagnelie }
6854d7988d6SPaul Dagnelie } else {
6864d7988d6SPaul Dagnelie zfs_btree_clear(&rt->rt_root);
6870713e232SGeorge Wilson }
6880713e232SGeorge Wilson
6890713e232SGeorge Wilson bzero(rt->rt_histogram, sizeof (rt->rt_histogram));
6900713e232SGeorge Wilson rt->rt_space = 0;
6910713e232SGeorge Wilson }
6920713e232SGeorge Wilson
6930713e232SGeorge Wilson void
range_tree_walk(range_tree_t * rt,range_tree_func_t * func,void * arg)6940713e232SGeorge Wilson range_tree_walk(range_tree_t *rt, range_tree_func_t *func, void *arg)
6950713e232SGeorge Wilson {
6964d7988d6SPaul Dagnelie zfs_btree_index_t where;
6974d7988d6SPaul Dagnelie for (range_seg_t *rs = zfs_btree_first(&rt->rt_root, &where);
6984d7988d6SPaul Dagnelie rs != NULL; rs = zfs_btree_next(&rt->rt_root, &where, &where)) {
6994d7988d6SPaul Dagnelie func(arg, rs_get_start(rs, rt), rs_get_end(rs, rt) -
7004d7988d6SPaul Dagnelie rs_get_start(rs, rt));
701814dcd43SSerapheim Dimitropoulos }
7020713e232SGeorge Wilson }
7030713e232SGeorge Wilson
704a3874b8bSToomas Soome range_seg_t *
range_tree_first(range_tree_t * rt)705a3874b8bSToomas Soome range_tree_first(range_tree_t *rt)
706a3874b8bSToomas Soome {
7074d7988d6SPaul Dagnelie return (zfs_btree_first(&rt->rt_root, NULL));
708a3874b8bSToomas Soome }
709a3874b8bSToomas Soome
7100713e232SGeorge Wilson uint64_t
range_tree_space(range_tree_t * rt)7110713e232SGeorge Wilson range_tree_space(range_tree_t *rt)
7120713e232SGeorge Wilson {
7130713e232SGeorge Wilson return (rt->rt_space);
7140713e232SGeorge Wilson }
71586714001SSerapheim Dimitropoulos
716814dcd43SSerapheim Dimitropoulos uint64_t
range_tree_numsegs(range_tree_t * rt)717814dcd43SSerapheim Dimitropoulos range_tree_numsegs(range_tree_t *rt)
718814dcd43SSerapheim Dimitropoulos {
7194d7988d6SPaul Dagnelie return ((rt == NULL) ? 0 : zfs_btree_numnodes(&rt->rt_root));
720814dcd43SSerapheim Dimitropoulos }
721814dcd43SSerapheim Dimitropoulos
7224d7988d6SPaul Dagnelie boolean_t
range_tree_is_empty(range_tree_t * rt)7234d7988d6SPaul Dagnelie range_tree_is_empty(range_tree_t *rt)
724a3874b8bSToomas Soome {
7254d7988d6SPaul Dagnelie ASSERT(rt != NULL);
7264d7988d6SPaul Dagnelie return (range_tree_space(rt) == 0);
727a3874b8bSToomas Soome }
728a3874b8bSToomas Soome
7294d7988d6SPaul Dagnelie /* ARGSUSED */
730a3874b8bSToomas Soome void
rt_btree_create(range_tree_t * rt,void * arg)7314d7988d6SPaul Dagnelie rt_btree_create(range_tree_t *rt, void *arg)
7324d7988d6SPaul Dagnelie {
7334d7988d6SPaul Dagnelie zfs_btree_t *size_tree = arg;
7344d7988d6SPaul Dagnelie
7354d7988d6SPaul Dagnelie size_t size;
7364d7988d6SPaul Dagnelie switch (rt->rt_type) {
7374d7988d6SPaul Dagnelie case RANGE_SEG32:
7384d7988d6SPaul Dagnelie size = sizeof (range_seg32_t);
7394d7988d6SPaul Dagnelie break;
7404d7988d6SPaul Dagnelie case RANGE_SEG64:
7414d7988d6SPaul Dagnelie size = sizeof (range_seg64_t);
7424d7988d6SPaul Dagnelie break;
7434d7988d6SPaul Dagnelie case RANGE_SEG_GAP:
7444d7988d6SPaul Dagnelie size = sizeof (range_seg_gap_t);
7454d7988d6SPaul Dagnelie break;
7464d7988d6SPaul Dagnelie default:
7474d7988d6SPaul Dagnelie panic("Invalid range seg type %d", rt->rt_type);
7484d7988d6SPaul Dagnelie }
7494d7988d6SPaul Dagnelie zfs_btree_create(size_tree, rt->rt_btree_compare, size);
750a3874b8bSToomas Soome }
751a3874b8bSToomas Soome
7524d7988d6SPaul Dagnelie /* ARGSUSED */
753a3874b8bSToomas Soome void
rt_btree_destroy(range_tree_t * rt,void * arg)7544d7988d6SPaul Dagnelie rt_btree_destroy(range_tree_t *rt, void *arg)
755a3874b8bSToomas Soome {
7564d7988d6SPaul Dagnelie zfs_btree_t *size_tree = arg;
7574d7988d6SPaul Dagnelie ASSERT0(zfs_btree_numnodes(size_tree));
7584d7988d6SPaul Dagnelie
7594d7988d6SPaul Dagnelie zfs_btree_destroy(size_tree);
760a3874b8bSToomas Soome }
761a3874b8bSToomas Soome
7624d7988d6SPaul Dagnelie /* ARGSUSED */
763a3874b8bSToomas Soome void
rt_btree_add(range_tree_t * rt,range_seg_t * rs,void * arg)7644d7988d6SPaul Dagnelie rt_btree_add(range_tree_t *rt, range_seg_t *rs, void *arg)
765a3874b8bSToomas Soome {
7664d7988d6SPaul Dagnelie zfs_btree_t *size_tree = arg;
7674d7988d6SPaul Dagnelie
7684d7988d6SPaul Dagnelie zfs_btree_add(size_tree, rs);
769a3874b8bSToomas Soome }
770a3874b8bSToomas Soome
7714d7988d6SPaul Dagnelie /* ARGSUSED */
772a3874b8bSToomas Soome void
rt_btree_remove(range_tree_t * rt,range_seg_t * rs,void * arg)7734d7988d6SPaul Dagnelie rt_btree_remove(range_tree_t *rt, range_seg_t *rs, void *arg)
774a3874b8bSToomas Soome {
7754d7988d6SPaul Dagnelie zfs_btree_t *size_tree = arg;
776a3874b8bSToomas Soome
7774d7988d6SPaul Dagnelie zfs_btree_remove(size_tree, rs);
77886714001SSerapheim Dimitropoulos }
779cfd63e1bSMatthew Ahrens
7804d7988d6SPaul Dagnelie /* ARGSUSED */
7814d7988d6SPaul Dagnelie void
rt_btree_vacate(range_tree_t * rt,void * arg)7824d7988d6SPaul Dagnelie rt_btree_vacate(range_tree_t *rt, void *arg)
783cfd63e1bSMatthew Ahrens {
7844d7988d6SPaul Dagnelie zfs_btree_t *size_tree = arg;
7854d7988d6SPaul Dagnelie zfs_btree_clear(size_tree);
7864d7988d6SPaul Dagnelie zfs_btree_destroy(size_tree);
787cfd63e1bSMatthew Ahrens
7884d7988d6SPaul Dagnelie rt_btree_create(rt, arg);
789cfd63e1bSMatthew Ahrens }
790cfd63e1bSMatthew Ahrens
7914d7988d6SPaul Dagnelie range_tree_ops_t rt_btree_ops = {
7924d7988d6SPaul Dagnelie .rtop_create = rt_btree_create,
7934d7988d6SPaul Dagnelie .rtop_destroy = rt_btree_destroy,
7944d7988d6SPaul Dagnelie .rtop_add = rt_btree_add,
7954d7988d6SPaul Dagnelie .rtop_remove = rt_btree_remove,
7964d7988d6SPaul Dagnelie .rtop_vacate = rt_btree_vacate
7974d7988d6SPaul Dagnelie };
798814dcd43SSerapheim Dimitropoulos
799814dcd43SSerapheim Dimitropoulos /*
800814dcd43SSerapheim Dimitropoulos * Remove any overlapping ranges between the given segment [start, end)
801814dcd43SSerapheim Dimitropoulos * from removefrom. Add non-overlapping leftovers to addto.
802814dcd43SSerapheim Dimitropoulos */
803814dcd43SSerapheim Dimitropoulos void
range_tree_remove_xor_add_segment(uint64_t start,uint64_t end,range_tree_t * removefrom,range_tree_t * addto)804814dcd43SSerapheim Dimitropoulos range_tree_remove_xor_add_segment(uint64_t start, uint64_t end,
805814dcd43SSerapheim Dimitropoulos range_tree_t *removefrom, range_tree_t *addto)
806814dcd43SSerapheim Dimitropoulos {
8074d7988d6SPaul Dagnelie zfs_btree_index_t where;
8084d7988d6SPaul Dagnelie range_seg_max_t starting_rs;
8094d7988d6SPaul Dagnelie rs_set_start(&starting_rs, removefrom, start);
8104d7988d6SPaul Dagnelie rs_set_end_raw(&starting_rs, removefrom, rs_get_start_raw(&starting_rs,
8114d7988d6SPaul Dagnelie removefrom) + 1);
812814dcd43SSerapheim Dimitropoulos
8134d7988d6SPaul Dagnelie range_seg_t *curr = zfs_btree_find(&removefrom->rt_root,
814814dcd43SSerapheim Dimitropoulos &starting_rs, &where);
815814dcd43SSerapheim Dimitropoulos
816814dcd43SSerapheim Dimitropoulos if (curr == NULL)
8174d7988d6SPaul Dagnelie curr = zfs_btree_next(&removefrom->rt_root, &where, &where);
818814dcd43SSerapheim Dimitropoulos
819814dcd43SSerapheim Dimitropoulos range_seg_t *next;
820814dcd43SSerapheim Dimitropoulos for (; curr != NULL; curr = next) {
821814dcd43SSerapheim Dimitropoulos if (start == end)
822814dcd43SSerapheim Dimitropoulos return;
823814dcd43SSerapheim Dimitropoulos VERIFY3U(start, <, end);
824814dcd43SSerapheim Dimitropoulos
825814dcd43SSerapheim Dimitropoulos /* there is no overlap */
8264d7988d6SPaul Dagnelie if (end <= rs_get_start(curr, removefrom)) {
827814dcd43SSerapheim Dimitropoulos range_tree_add(addto, start, end - start);
828814dcd43SSerapheim Dimitropoulos return;
829814dcd43SSerapheim Dimitropoulos }
830814dcd43SSerapheim Dimitropoulos
8314d7988d6SPaul Dagnelie uint64_t overlap_start = MAX(rs_get_start(curr, removefrom),
8324d7988d6SPaul Dagnelie start);
8334d7988d6SPaul Dagnelie uint64_t overlap_end = MIN(rs_get_end(curr, removefrom),
8344d7988d6SPaul Dagnelie end);
835814dcd43SSerapheim Dimitropoulos uint64_t overlap_size = overlap_end - overlap_start;
836814dcd43SSerapheim Dimitropoulos ASSERT3S(overlap_size, >, 0);
8374d7988d6SPaul Dagnelie range_seg_max_t rs;
8384d7988d6SPaul Dagnelie rs_copy(curr, &rs, removefrom);
8394d7988d6SPaul Dagnelie
840814dcd43SSerapheim Dimitropoulos range_tree_remove(removefrom, overlap_start, overlap_size);
841814dcd43SSerapheim Dimitropoulos
842814dcd43SSerapheim Dimitropoulos if (start < overlap_start)
843814dcd43SSerapheim Dimitropoulos range_tree_add(addto, start, overlap_start - start);
844814dcd43SSerapheim Dimitropoulos
845814dcd43SSerapheim Dimitropoulos start = overlap_end;
8464d7988d6SPaul Dagnelie next = zfs_btree_find(&removefrom->rt_root, &rs, &where);
8474d7988d6SPaul Dagnelie /*
8484d7988d6SPaul Dagnelie * If we find something here, we only removed part of the
8494d7988d6SPaul Dagnelie * curr segment. Either there's some left at the end
8504d7988d6SPaul Dagnelie * because we've reached the end of the range we're removing,
8514d7988d6SPaul Dagnelie * or there's some left at the start because we started
8524d7988d6SPaul Dagnelie * partway through the range. Either way, we continue with
8534d7988d6SPaul Dagnelie * the loop. If it's the former, we'll return at the start of
8544d7988d6SPaul Dagnelie * the loop, and if it's the latter we'll see if there is more
8554d7988d6SPaul Dagnelie * area to process.
8564d7988d6SPaul Dagnelie */
8574d7988d6SPaul Dagnelie if (next != NULL) {
8584d7988d6SPaul Dagnelie ASSERT(start == end || start == rs_get_end(&rs,
8594d7988d6SPaul Dagnelie removefrom));
8604d7988d6SPaul Dagnelie }
8614d7988d6SPaul Dagnelie
8624d7988d6SPaul Dagnelie next = zfs_btree_next(&removefrom->rt_root, &where, &where);
863814dcd43SSerapheim Dimitropoulos }
864814dcd43SSerapheim Dimitropoulos VERIFY3P(curr, ==, NULL);
865814dcd43SSerapheim Dimitropoulos
866814dcd43SSerapheim Dimitropoulos if (start != end) {
867814dcd43SSerapheim Dimitropoulos VERIFY3U(start, <, end);
868814dcd43SSerapheim Dimitropoulos range_tree_add(addto, start, end - start);
869814dcd43SSerapheim Dimitropoulos } else {
870814dcd43SSerapheim Dimitropoulos VERIFY3U(start, ==, end);
871814dcd43SSerapheim Dimitropoulos }
872814dcd43SSerapheim Dimitropoulos }
873814dcd43SSerapheim Dimitropoulos
874814dcd43SSerapheim Dimitropoulos /*
875814dcd43SSerapheim Dimitropoulos * For each entry in rt, if it exists in removefrom, remove it
876814dcd43SSerapheim Dimitropoulos * from removefrom. Otherwise, add it to addto.
877814dcd43SSerapheim Dimitropoulos */
878814dcd43SSerapheim Dimitropoulos void
range_tree_remove_xor_add(range_tree_t * rt,range_tree_t * removefrom,range_tree_t * addto)879814dcd43SSerapheim Dimitropoulos range_tree_remove_xor_add(range_tree_t *rt, range_tree_t *removefrom,
880814dcd43SSerapheim Dimitropoulos range_tree_t *addto)
881814dcd43SSerapheim Dimitropoulos {
8824d7988d6SPaul Dagnelie zfs_btree_index_t where;
8834d7988d6SPaul Dagnelie for (range_seg_t *rs = zfs_btree_first(&rt->rt_root, &where); rs;
8844d7988d6SPaul Dagnelie rs = zfs_btree_next(&rt->rt_root, &where, &where)) {
8854d7988d6SPaul Dagnelie range_tree_remove_xor_add_segment(rs_get_start(rs, rt),
8864d7988d6SPaul Dagnelie rs_get_end(rs, rt), removefrom, addto);
887814dcd43SSerapheim Dimitropoulos }
888814dcd43SSerapheim Dimitropoulos }
8894d7988d6SPaul Dagnelie
8904d7988d6SPaul Dagnelie uint64_t
range_tree_min(range_tree_t * rt)8914d7988d6SPaul Dagnelie range_tree_min(range_tree_t *rt)
8924d7988d6SPaul Dagnelie {
8934d7988d6SPaul Dagnelie range_seg_t *rs = zfs_btree_first(&rt->rt_root, NULL);
8944d7988d6SPaul Dagnelie return (rs != NULL ? rs_get_start(rs, rt) : 0);
8954d7988d6SPaul Dagnelie }
8964d7988d6SPaul Dagnelie
8974d7988d6SPaul Dagnelie uint64_t
range_tree_max(range_tree_t * rt)8984d7988d6SPaul Dagnelie range_tree_max(range_tree_t *rt)
8994d7988d6SPaul Dagnelie {
9004d7988d6SPaul Dagnelie range_seg_t *rs = zfs_btree_last(&rt->rt_root, NULL);
9014d7988d6SPaul Dagnelie return (rs != NULL ? rs_get_end(rs, rt) : 0);
9024d7988d6SPaul Dagnelie }
9034d7988d6SPaul Dagnelie
9044d7988d6SPaul Dagnelie uint64_t
range_tree_span(range_tree_t * rt)9054d7988d6SPaul Dagnelie range_tree_span(range_tree_t *rt)
9064d7988d6SPaul Dagnelie {
9074d7988d6SPaul Dagnelie return (range_tree_max(rt) - range_tree_min(rt));
9084d7988d6SPaul Dagnelie }
909