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 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 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 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 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 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 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 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 * 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 * 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 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 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 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 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 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 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 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 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 * 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 * 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 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 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 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 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 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 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 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 * 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 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 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 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 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 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 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 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 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 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 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 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 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 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