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 /* 2686714001SSerapheim Dimitropoulos * Copyright (c) 2013, 2017 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 3683803b51SGeorge Wilson kmem_cache_t *range_seg_cache; 370713e232SGeorge Wilson 380713e232SGeorge Wilson void 390713e232SGeorge Wilson range_tree_init(void) 400713e232SGeorge Wilson { 410713e232SGeorge Wilson ASSERT(range_seg_cache == NULL); 420713e232SGeorge Wilson range_seg_cache = kmem_cache_create("range_seg_cache", 430713e232SGeorge Wilson sizeof (range_seg_t), 0, NULL, NULL, NULL, NULL, NULL, 0); 440713e232SGeorge Wilson } 450713e232SGeorge Wilson 460713e232SGeorge Wilson void 470713e232SGeorge Wilson range_tree_fini(void) 480713e232SGeorge Wilson { 490713e232SGeorge Wilson kmem_cache_destroy(range_seg_cache); 500713e232SGeorge Wilson range_seg_cache = NULL; 510713e232SGeorge Wilson } 520713e232SGeorge Wilson 530713e232SGeorge Wilson void 540713e232SGeorge Wilson range_tree_stat_verify(range_tree_t *rt) 550713e232SGeorge Wilson { 560713e232SGeorge Wilson range_seg_t *rs; 570713e232SGeorge Wilson uint64_t hist[RANGE_TREE_HISTOGRAM_SIZE] = { 0 }; 580713e232SGeorge Wilson int i; 590713e232SGeorge Wilson 600713e232SGeorge Wilson for (rs = avl_first(&rt->rt_root); rs != NULL; 610713e232SGeorge Wilson rs = AVL_NEXT(&rt->rt_root, rs)) { 620713e232SGeorge Wilson uint64_t size = rs->rs_end - rs->rs_start; 63bf16b11eSMatthew Ahrens int idx = highbit64(size) - 1; 640713e232SGeorge Wilson 650713e232SGeorge Wilson hist[idx]++; 660713e232SGeorge Wilson ASSERT3U(hist[idx], !=, 0); 670713e232SGeorge Wilson } 680713e232SGeorge Wilson 690713e232SGeorge Wilson for (i = 0; i < RANGE_TREE_HISTOGRAM_SIZE; i++) { 700713e232SGeorge Wilson if (hist[i] != rt->rt_histogram[i]) { 710713e232SGeorge Wilson zfs_dbgmsg("i=%d, hist=%p, hist=%llu, rt_hist=%llu", 720713e232SGeorge Wilson i, hist, hist[i], rt->rt_histogram[i]); 730713e232SGeorge Wilson } 740713e232SGeorge Wilson VERIFY3U(hist[i], ==, rt->rt_histogram[i]); 750713e232SGeorge Wilson } 760713e232SGeorge Wilson } 770713e232SGeorge Wilson 780713e232SGeorge Wilson static void 790713e232SGeorge Wilson range_tree_stat_incr(range_tree_t *rt, range_seg_t *rs) 800713e232SGeorge Wilson { 810713e232SGeorge Wilson uint64_t size = rs->rs_end - rs->rs_start; 82bf16b11eSMatthew Ahrens int idx = highbit64(size) - 1; 830713e232SGeorge Wilson 842e4c9986SGeorge Wilson ASSERT(size != 0); 850713e232SGeorge Wilson ASSERT3U(idx, <, 860713e232SGeorge Wilson sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram)); 870713e232SGeorge Wilson 880713e232SGeorge Wilson rt->rt_histogram[idx]++; 890713e232SGeorge Wilson ASSERT3U(rt->rt_histogram[idx], !=, 0); 900713e232SGeorge Wilson } 910713e232SGeorge Wilson 920713e232SGeorge Wilson static void 930713e232SGeorge Wilson range_tree_stat_decr(range_tree_t *rt, range_seg_t *rs) 940713e232SGeorge Wilson { 950713e232SGeorge Wilson uint64_t size = rs->rs_end - rs->rs_start; 96bf16b11eSMatthew Ahrens int idx = highbit64(size) - 1; 970713e232SGeorge Wilson 982e4c9986SGeorge Wilson ASSERT(size != 0); 990713e232SGeorge Wilson ASSERT3U(idx, <, 1000713e232SGeorge Wilson sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram)); 1010713e232SGeorge Wilson 1020713e232SGeorge Wilson ASSERT3U(rt->rt_histogram[idx], !=, 0); 1030713e232SGeorge Wilson rt->rt_histogram[idx]--; 1040713e232SGeorge Wilson } 1050713e232SGeorge Wilson 1060713e232SGeorge Wilson /* 1070713e232SGeorge Wilson * NOTE: caller is responsible for all locking. 1080713e232SGeorge Wilson */ 1090713e232SGeorge Wilson static int 1100713e232SGeorge Wilson range_tree_seg_compare(const void *x1, const void *x2) 1110713e232SGeorge Wilson { 112*c4ab0d3fSGvozden Neskovic const range_seg_t *r1 = (const range_seg_t *)x1; 113*c4ab0d3fSGvozden Neskovic const range_seg_t *r2 = (const range_seg_t *)x2; 1140713e232SGeorge Wilson 115*c4ab0d3fSGvozden Neskovic ASSERT3U(r1->rs_start, <=, r1->rs_end); 116*c4ab0d3fSGvozden Neskovic ASSERT3U(r2->rs_start, <=, r2->rs_end); 117*c4ab0d3fSGvozden Neskovic 118*c4ab0d3fSGvozden Neskovic return ((r1->rs_start >= r2->rs_end) - (r1->rs_end <= r2->rs_start)); 1190713e232SGeorge Wilson } 1200713e232SGeorge Wilson 1210713e232SGeorge Wilson range_tree_t * 1225cabbc6bSPrashanth Sreenivasa range_tree_create(range_tree_ops_t *ops, void *arg) 1230713e232SGeorge Wilson { 1240713e232SGeorge Wilson range_tree_t *rt; 1250713e232SGeorge Wilson 1260713e232SGeorge Wilson rt = kmem_zalloc(sizeof (range_tree_t), KM_SLEEP); 1270713e232SGeorge Wilson 1280713e232SGeorge Wilson avl_create(&rt->rt_root, range_tree_seg_compare, 1290713e232SGeorge Wilson sizeof (range_seg_t), offsetof(range_seg_t, rs_node)); 1300713e232SGeorge Wilson 1310713e232SGeorge Wilson rt->rt_ops = ops; 1320713e232SGeorge Wilson rt->rt_arg = arg; 1330713e232SGeorge Wilson 1340713e232SGeorge Wilson if (rt->rt_ops != NULL) 1350713e232SGeorge Wilson rt->rt_ops->rtop_create(rt, rt->rt_arg); 1360713e232SGeorge Wilson 1370713e232SGeorge Wilson return (rt); 1380713e232SGeorge Wilson } 1390713e232SGeorge Wilson 1400713e232SGeorge Wilson void 1410713e232SGeorge Wilson range_tree_destroy(range_tree_t *rt) 1420713e232SGeorge Wilson { 1430713e232SGeorge Wilson VERIFY0(rt->rt_space); 1440713e232SGeorge Wilson 1450713e232SGeorge Wilson if (rt->rt_ops != NULL) 1460713e232SGeorge Wilson rt->rt_ops->rtop_destroy(rt, rt->rt_arg); 1470713e232SGeorge Wilson 1480713e232SGeorge Wilson avl_destroy(&rt->rt_root); 1490713e232SGeorge Wilson kmem_free(rt, sizeof (*rt)); 1500713e232SGeorge Wilson } 1510713e232SGeorge Wilson 1520713e232SGeorge Wilson void 1530713e232SGeorge Wilson range_tree_add(void *arg, uint64_t start, uint64_t size) 1540713e232SGeorge Wilson { 1550713e232SGeorge Wilson range_tree_t *rt = arg; 1560713e232SGeorge Wilson avl_index_t where; 1570713e232SGeorge Wilson range_seg_t rsearch, *rs_before, *rs_after, *rs; 1580713e232SGeorge Wilson uint64_t end = start + size; 1590713e232SGeorge Wilson boolean_t merge_before, merge_after; 1600713e232SGeorge Wilson 1610713e232SGeorge Wilson VERIFY(size != 0); 1620713e232SGeorge Wilson 1630713e232SGeorge Wilson rsearch.rs_start = start; 1640713e232SGeorge Wilson rsearch.rs_end = end; 1650713e232SGeorge Wilson rs = avl_find(&rt->rt_root, &rsearch, &where); 1660713e232SGeorge Wilson 1670713e232SGeorge Wilson if (rs != NULL && rs->rs_start <= start && rs->rs_end >= end) { 1680713e232SGeorge Wilson zfs_panic_recover("zfs: allocating allocated segment" 1690713e232SGeorge Wilson "(offset=%llu size=%llu)\n", 1700713e232SGeorge Wilson (longlong_t)start, (longlong_t)size); 1710713e232SGeorge Wilson return; 1720713e232SGeorge Wilson } 1730713e232SGeorge Wilson 1740713e232SGeorge Wilson /* Make sure we don't overlap with either of our neighbors */ 17517f11284SSerapheim Dimitropoulos VERIFY3P(rs, ==, NULL); 1760713e232SGeorge Wilson 1770713e232SGeorge Wilson rs_before = avl_nearest(&rt->rt_root, where, AVL_BEFORE); 1780713e232SGeorge Wilson rs_after = avl_nearest(&rt->rt_root, where, AVL_AFTER); 1790713e232SGeorge Wilson 1800713e232SGeorge Wilson merge_before = (rs_before != NULL && rs_before->rs_end == start); 1810713e232SGeorge Wilson merge_after = (rs_after != NULL && rs_after->rs_start == end); 1820713e232SGeorge Wilson 1830713e232SGeorge Wilson if (merge_before && merge_after) { 1840713e232SGeorge Wilson avl_remove(&rt->rt_root, rs_before); 1850713e232SGeorge Wilson if (rt->rt_ops != NULL) { 1860713e232SGeorge Wilson rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg); 1870713e232SGeorge Wilson rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg); 1880713e232SGeorge Wilson } 1890713e232SGeorge Wilson 1900713e232SGeorge Wilson range_tree_stat_decr(rt, rs_before); 1910713e232SGeorge Wilson range_tree_stat_decr(rt, rs_after); 1920713e232SGeorge Wilson 1930713e232SGeorge Wilson rs_after->rs_start = rs_before->rs_start; 1940713e232SGeorge Wilson kmem_cache_free(range_seg_cache, rs_before); 1950713e232SGeorge Wilson rs = rs_after; 1960713e232SGeorge Wilson } else if (merge_before) { 1970713e232SGeorge Wilson if (rt->rt_ops != NULL) 1980713e232SGeorge Wilson rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg); 1990713e232SGeorge Wilson 2000713e232SGeorge Wilson range_tree_stat_decr(rt, rs_before); 2010713e232SGeorge Wilson 2020713e232SGeorge Wilson rs_before->rs_end = end; 2030713e232SGeorge Wilson rs = rs_before; 2040713e232SGeorge Wilson } else if (merge_after) { 2050713e232SGeorge Wilson if (rt->rt_ops != NULL) 2060713e232SGeorge Wilson rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg); 2070713e232SGeorge Wilson 2080713e232SGeorge Wilson range_tree_stat_decr(rt, rs_after); 2090713e232SGeorge Wilson 2100713e232SGeorge Wilson rs_after->rs_start = start; 2110713e232SGeorge Wilson rs = rs_after; 2120713e232SGeorge Wilson } else { 2130713e232SGeorge Wilson rs = kmem_cache_alloc(range_seg_cache, KM_SLEEP); 2140713e232SGeorge Wilson rs->rs_start = start; 2150713e232SGeorge Wilson rs->rs_end = end; 2160713e232SGeorge Wilson avl_insert(&rt->rt_root, rs, where); 2170713e232SGeorge Wilson } 2180713e232SGeorge Wilson 2190713e232SGeorge Wilson if (rt->rt_ops != NULL) 2200713e232SGeorge Wilson rt->rt_ops->rtop_add(rt, rs, rt->rt_arg); 2210713e232SGeorge Wilson 2220713e232SGeorge Wilson range_tree_stat_incr(rt, rs); 2230713e232SGeorge Wilson rt->rt_space += size; 2240713e232SGeorge Wilson } 2250713e232SGeorge Wilson 2260713e232SGeorge Wilson void 2270713e232SGeorge Wilson range_tree_remove(void *arg, uint64_t start, uint64_t size) 2280713e232SGeorge Wilson { 2290713e232SGeorge Wilson range_tree_t *rt = arg; 2300713e232SGeorge Wilson avl_index_t where; 2310713e232SGeorge Wilson range_seg_t rsearch, *rs, *newseg; 2320713e232SGeorge Wilson uint64_t end = start + size; 2330713e232SGeorge Wilson boolean_t left_over, right_over; 2340713e232SGeorge Wilson 2350713e232SGeorge Wilson VERIFY3U(size, !=, 0); 2360713e232SGeorge Wilson VERIFY3U(size, <=, rt->rt_space); 2370713e232SGeorge Wilson 2380713e232SGeorge Wilson rsearch.rs_start = start; 2390713e232SGeorge Wilson rsearch.rs_end = end; 2400713e232SGeorge Wilson rs = avl_find(&rt->rt_root, &rsearch, &where); 2410713e232SGeorge Wilson 2420713e232SGeorge Wilson /* Make sure we completely overlap with someone */ 2430713e232SGeorge Wilson if (rs == NULL) { 2440713e232SGeorge Wilson zfs_panic_recover("zfs: freeing free segment " 2450713e232SGeorge Wilson "(offset=%llu size=%llu)", 2460713e232SGeorge Wilson (longlong_t)start, (longlong_t)size); 2470713e232SGeorge Wilson return; 2480713e232SGeorge Wilson } 2490713e232SGeorge Wilson VERIFY3U(rs->rs_start, <=, start); 2500713e232SGeorge Wilson VERIFY3U(rs->rs_end, >=, end); 2510713e232SGeorge Wilson 2520713e232SGeorge Wilson left_over = (rs->rs_start != start); 2530713e232SGeorge Wilson right_over = (rs->rs_end != end); 2540713e232SGeorge Wilson 2550713e232SGeorge Wilson range_tree_stat_decr(rt, rs); 2560713e232SGeorge Wilson 2570713e232SGeorge Wilson if (rt->rt_ops != NULL) 2580713e232SGeorge Wilson rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg); 2590713e232SGeorge Wilson 2600713e232SGeorge Wilson if (left_over && right_over) { 2610713e232SGeorge Wilson newseg = kmem_cache_alloc(range_seg_cache, KM_SLEEP); 2620713e232SGeorge Wilson newseg->rs_start = end; 2630713e232SGeorge Wilson newseg->rs_end = rs->rs_end; 2640713e232SGeorge Wilson range_tree_stat_incr(rt, newseg); 2650713e232SGeorge Wilson 2660713e232SGeorge Wilson rs->rs_end = start; 2670713e232SGeorge Wilson 2680713e232SGeorge Wilson avl_insert_here(&rt->rt_root, newseg, rs, AVL_AFTER); 2690713e232SGeorge Wilson if (rt->rt_ops != NULL) 2700713e232SGeorge Wilson rt->rt_ops->rtop_add(rt, newseg, rt->rt_arg); 2710713e232SGeorge Wilson } else if (left_over) { 2720713e232SGeorge Wilson rs->rs_end = start; 2730713e232SGeorge Wilson } else if (right_over) { 2740713e232SGeorge Wilson rs->rs_start = end; 2750713e232SGeorge Wilson } else { 2760713e232SGeorge Wilson avl_remove(&rt->rt_root, rs); 2770713e232SGeorge Wilson kmem_cache_free(range_seg_cache, rs); 2780713e232SGeorge Wilson rs = NULL; 2790713e232SGeorge Wilson } 2800713e232SGeorge Wilson 2810713e232SGeorge Wilson if (rs != NULL) { 2820713e232SGeorge Wilson range_tree_stat_incr(rt, rs); 2830713e232SGeorge Wilson 2840713e232SGeorge Wilson if (rt->rt_ops != NULL) 2850713e232SGeorge Wilson rt->rt_ops->rtop_add(rt, rs, rt->rt_arg); 2860713e232SGeorge Wilson } 2870713e232SGeorge Wilson 2880713e232SGeorge Wilson rt->rt_space -= size; 2890713e232SGeorge Wilson } 2900713e232SGeorge Wilson 2910713e232SGeorge Wilson static range_seg_t * 292bf16b11eSMatthew Ahrens range_tree_find_impl(range_tree_t *rt, uint64_t start, uint64_t size) 2930713e232SGeorge Wilson { 294bf16b11eSMatthew Ahrens range_seg_t rsearch; 2950713e232SGeorge Wilson uint64_t end = start + size; 2960713e232SGeorge Wilson 2970713e232SGeorge Wilson VERIFY(size != 0); 2980713e232SGeorge Wilson 2990713e232SGeorge Wilson rsearch.rs_start = start; 3000713e232SGeorge Wilson rsearch.rs_end = end; 301cfd63e1bSMatthew Ahrens return (avl_find(&rt->rt_root, &rsearch, NULL)); 302bf16b11eSMatthew Ahrens } 3030713e232SGeorge Wilson 304bf16b11eSMatthew Ahrens static range_seg_t * 305bf16b11eSMatthew Ahrens range_tree_find(range_tree_t *rt, uint64_t start, uint64_t size) 306bf16b11eSMatthew Ahrens { 307bf16b11eSMatthew Ahrens range_seg_t *rs = range_tree_find_impl(rt, start, size); 308bf16b11eSMatthew Ahrens if (rs != NULL && rs->rs_start <= start && rs->rs_end >= start + size) 3090713e232SGeorge Wilson return (rs); 3100713e232SGeorge Wilson return (NULL); 3110713e232SGeorge Wilson } 3120713e232SGeorge Wilson 3130713e232SGeorge Wilson void 314555d674dSSerapheim Dimitropoulos range_tree_verify_not_present(range_tree_t *rt, uint64_t off, uint64_t size) 3150713e232SGeorge Wilson { 316555d674dSSerapheim Dimitropoulos range_seg_t *rs = range_tree_find(rt, off, size); 3170713e232SGeorge Wilson if (rs != NULL) 318555d674dSSerapheim Dimitropoulos panic("segment already in tree; rs=%p", (void *)rs); 3190713e232SGeorge Wilson } 3200713e232SGeorge Wilson 3210713e232SGeorge Wilson boolean_t 3220713e232SGeorge Wilson range_tree_contains(range_tree_t *rt, uint64_t start, uint64_t size) 3230713e232SGeorge Wilson { 324bf16b11eSMatthew Ahrens return (range_tree_find(rt, start, size) != NULL); 325bf16b11eSMatthew Ahrens } 3260713e232SGeorge Wilson 327bf16b11eSMatthew Ahrens /* 328bf16b11eSMatthew Ahrens * Ensure that this range is not in the tree, regardless of whether 329bf16b11eSMatthew Ahrens * it is currently in the tree. 330bf16b11eSMatthew Ahrens */ 331bf16b11eSMatthew Ahrens void 332bf16b11eSMatthew Ahrens range_tree_clear(range_tree_t *rt, uint64_t start, uint64_t size) 333bf16b11eSMatthew Ahrens { 334bf16b11eSMatthew Ahrens range_seg_t *rs; 335bf16b11eSMatthew Ahrens 3365cabbc6bSPrashanth Sreenivasa if (size == 0) 3375cabbc6bSPrashanth Sreenivasa return; 3385cabbc6bSPrashanth Sreenivasa 339bf16b11eSMatthew Ahrens while ((rs = range_tree_find_impl(rt, start, size)) != NULL) { 340bf16b11eSMatthew Ahrens uint64_t free_start = MAX(rs->rs_start, start); 341bf16b11eSMatthew Ahrens uint64_t free_end = MIN(rs->rs_end, start + size); 342bf16b11eSMatthew Ahrens range_tree_remove(rt, free_start, free_end - free_start); 343bf16b11eSMatthew Ahrens } 3440713e232SGeorge Wilson } 3450713e232SGeorge Wilson 3460713e232SGeorge Wilson void 3470713e232SGeorge Wilson range_tree_swap(range_tree_t **rtsrc, range_tree_t **rtdst) 3480713e232SGeorge Wilson { 3490713e232SGeorge Wilson range_tree_t *rt; 3500713e232SGeorge Wilson 3510713e232SGeorge Wilson ASSERT0(range_tree_space(*rtdst)); 3520713e232SGeorge Wilson ASSERT0(avl_numnodes(&(*rtdst)->rt_root)); 3530713e232SGeorge Wilson 3540713e232SGeorge Wilson rt = *rtsrc; 3550713e232SGeorge Wilson *rtsrc = *rtdst; 3560713e232SGeorge Wilson *rtdst = rt; 3570713e232SGeorge Wilson } 3580713e232SGeorge Wilson 3590713e232SGeorge Wilson void 3600713e232SGeorge Wilson range_tree_vacate(range_tree_t *rt, range_tree_func_t *func, void *arg) 3610713e232SGeorge Wilson { 3620713e232SGeorge Wilson range_seg_t *rs; 3630713e232SGeorge Wilson void *cookie = NULL; 3640713e232SGeorge Wilson 3650713e232SGeorge Wilson 3660713e232SGeorge Wilson if (rt->rt_ops != NULL) 3670713e232SGeorge Wilson rt->rt_ops->rtop_vacate(rt, rt->rt_arg); 3680713e232SGeorge Wilson 3690713e232SGeorge Wilson while ((rs = avl_destroy_nodes(&rt->rt_root, &cookie)) != NULL) { 3700713e232SGeorge Wilson if (func != NULL) 3710713e232SGeorge Wilson func(arg, rs->rs_start, rs->rs_end - rs->rs_start); 3720713e232SGeorge Wilson kmem_cache_free(range_seg_cache, rs); 3730713e232SGeorge Wilson } 3740713e232SGeorge Wilson 3750713e232SGeorge Wilson bzero(rt->rt_histogram, sizeof (rt->rt_histogram)); 3760713e232SGeorge Wilson rt->rt_space = 0; 3770713e232SGeorge Wilson } 3780713e232SGeorge Wilson 3790713e232SGeorge Wilson void 3800713e232SGeorge Wilson range_tree_walk(range_tree_t *rt, range_tree_func_t *func, void *arg) 3810713e232SGeorge Wilson { 3820713e232SGeorge Wilson range_seg_t *rs; 3830713e232SGeorge Wilson 3840713e232SGeorge Wilson for (rs = avl_first(&rt->rt_root); rs; rs = AVL_NEXT(&rt->rt_root, rs)) 3850713e232SGeorge Wilson func(arg, rs->rs_start, rs->rs_end - rs->rs_start); 3860713e232SGeorge Wilson } 3870713e232SGeorge Wilson 3880713e232SGeorge Wilson uint64_t 3890713e232SGeorge Wilson range_tree_space(range_tree_t *rt) 3900713e232SGeorge Wilson { 3910713e232SGeorge Wilson return (rt->rt_space); 3920713e232SGeorge Wilson } 39386714001SSerapheim Dimitropoulos 39486714001SSerapheim Dimitropoulos boolean_t 39586714001SSerapheim Dimitropoulos range_tree_is_empty(range_tree_t *rt) 39686714001SSerapheim Dimitropoulos { 39786714001SSerapheim Dimitropoulos ASSERT(rt != NULL); 39886714001SSerapheim Dimitropoulos return (range_tree_space(rt) == 0); 39986714001SSerapheim Dimitropoulos } 400cfd63e1bSMatthew Ahrens 401cfd63e1bSMatthew Ahrens uint64_t 402cfd63e1bSMatthew Ahrens range_tree_min(range_tree_t *rt) 403cfd63e1bSMatthew Ahrens { 404cfd63e1bSMatthew Ahrens range_seg_t *rs = avl_first(&rt->rt_root); 405cfd63e1bSMatthew Ahrens return (rs != NULL ? rs->rs_start : 0); 406cfd63e1bSMatthew Ahrens } 407cfd63e1bSMatthew Ahrens 408cfd63e1bSMatthew Ahrens uint64_t 409cfd63e1bSMatthew Ahrens range_tree_max(range_tree_t *rt) 410cfd63e1bSMatthew Ahrens { 411cfd63e1bSMatthew Ahrens range_seg_t *rs = avl_last(&rt->rt_root); 412cfd63e1bSMatthew Ahrens return (rs != NULL ? rs->rs_end : 0); 413cfd63e1bSMatthew Ahrens } 414cfd63e1bSMatthew Ahrens 415cfd63e1bSMatthew Ahrens uint64_t 416cfd63e1bSMatthew Ahrens range_tree_span(range_tree_t *rt) 417cfd63e1bSMatthew Ahrens { 418cfd63e1bSMatthew Ahrens return (range_tree_max(rt) - range_tree_min(rt)); 419cfd63e1bSMatthew Ahrens } 420