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 /* 26*5cabbc6bSPrashanth Sreenivasa * Copyright (c) 2013, 2015 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 { 1120713e232SGeorge Wilson const range_seg_t *r1 = x1; 1130713e232SGeorge Wilson const range_seg_t *r2 = x2; 1140713e232SGeorge Wilson 1150713e232SGeorge Wilson if (r1->rs_start < r2->rs_start) { 1160713e232SGeorge Wilson if (r1->rs_end > r2->rs_start) 1170713e232SGeorge Wilson return (0); 1180713e232SGeorge Wilson return (-1); 1190713e232SGeorge Wilson } 1200713e232SGeorge Wilson if (r1->rs_start > r2->rs_start) { 1210713e232SGeorge Wilson if (r1->rs_start < r2->rs_end) 1220713e232SGeorge Wilson return (0); 1230713e232SGeorge Wilson return (1); 1240713e232SGeorge Wilson } 1250713e232SGeorge Wilson return (0); 1260713e232SGeorge Wilson } 1270713e232SGeorge Wilson 1280713e232SGeorge Wilson range_tree_t * 129*5cabbc6bSPrashanth Sreenivasa range_tree_create(range_tree_ops_t *ops, void *arg) 1300713e232SGeorge Wilson { 1310713e232SGeorge Wilson range_tree_t *rt; 1320713e232SGeorge Wilson 1330713e232SGeorge Wilson rt = kmem_zalloc(sizeof (range_tree_t), KM_SLEEP); 1340713e232SGeorge Wilson 1350713e232SGeorge Wilson avl_create(&rt->rt_root, range_tree_seg_compare, 1360713e232SGeorge Wilson sizeof (range_seg_t), offsetof(range_seg_t, rs_node)); 1370713e232SGeorge Wilson 1380713e232SGeorge Wilson rt->rt_ops = ops; 1390713e232SGeorge Wilson rt->rt_arg = arg; 1400713e232SGeorge Wilson 1410713e232SGeorge Wilson if (rt->rt_ops != NULL) 1420713e232SGeorge Wilson rt->rt_ops->rtop_create(rt, rt->rt_arg); 1430713e232SGeorge Wilson 1440713e232SGeorge Wilson return (rt); 1450713e232SGeorge Wilson } 1460713e232SGeorge Wilson 1470713e232SGeorge Wilson void 1480713e232SGeorge Wilson range_tree_destroy(range_tree_t *rt) 1490713e232SGeorge Wilson { 1500713e232SGeorge Wilson VERIFY0(rt->rt_space); 1510713e232SGeorge Wilson 1520713e232SGeorge Wilson if (rt->rt_ops != NULL) 1530713e232SGeorge Wilson rt->rt_ops->rtop_destroy(rt, rt->rt_arg); 1540713e232SGeorge Wilson 1550713e232SGeorge Wilson avl_destroy(&rt->rt_root); 1560713e232SGeorge Wilson kmem_free(rt, sizeof (*rt)); 1570713e232SGeorge Wilson } 1580713e232SGeorge Wilson 1590713e232SGeorge Wilson void 1600713e232SGeorge Wilson range_tree_add(void *arg, uint64_t start, uint64_t size) 1610713e232SGeorge Wilson { 1620713e232SGeorge Wilson range_tree_t *rt = arg; 1630713e232SGeorge Wilson avl_index_t where; 1640713e232SGeorge Wilson range_seg_t rsearch, *rs_before, *rs_after, *rs; 1650713e232SGeorge Wilson uint64_t end = start + size; 1660713e232SGeorge Wilson boolean_t merge_before, merge_after; 1670713e232SGeorge Wilson 1680713e232SGeorge Wilson VERIFY(size != 0); 1690713e232SGeorge Wilson 1700713e232SGeorge Wilson rsearch.rs_start = start; 1710713e232SGeorge Wilson rsearch.rs_end = end; 1720713e232SGeorge Wilson rs = avl_find(&rt->rt_root, &rsearch, &where); 1730713e232SGeorge Wilson 1740713e232SGeorge Wilson if (rs != NULL && rs->rs_start <= start && rs->rs_end >= end) { 1750713e232SGeorge Wilson zfs_panic_recover("zfs: allocating allocated segment" 1760713e232SGeorge Wilson "(offset=%llu size=%llu)\n", 1770713e232SGeorge Wilson (longlong_t)start, (longlong_t)size); 1780713e232SGeorge Wilson return; 1790713e232SGeorge Wilson } 1800713e232SGeorge Wilson 1810713e232SGeorge Wilson /* Make sure we don't overlap with either of our neighbors */ 1820713e232SGeorge Wilson VERIFY(rs == NULL); 1830713e232SGeorge Wilson 1840713e232SGeorge Wilson rs_before = avl_nearest(&rt->rt_root, where, AVL_BEFORE); 1850713e232SGeorge Wilson rs_after = avl_nearest(&rt->rt_root, where, AVL_AFTER); 1860713e232SGeorge Wilson 1870713e232SGeorge Wilson merge_before = (rs_before != NULL && rs_before->rs_end == start); 1880713e232SGeorge Wilson merge_after = (rs_after != NULL && rs_after->rs_start == end); 1890713e232SGeorge Wilson 1900713e232SGeorge Wilson if (merge_before && merge_after) { 1910713e232SGeorge Wilson avl_remove(&rt->rt_root, rs_before); 1920713e232SGeorge Wilson if (rt->rt_ops != NULL) { 1930713e232SGeorge Wilson rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg); 1940713e232SGeorge Wilson rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg); 1950713e232SGeorge Wilson } 1960713e232SGeorge Wilson 1970713e232SGeorge Wilson range_tree_stat_decr(rt, rs_before); 1980713e232SGeorge Wilson range_tree_stat_decr(rt, rs_after); 1990713e232SGeorge Wilson 2000713e232SGeorge Wilson rs_after->rs_start = rs_before->rs_start; 2010713e232SGeorge Wilson kmem_cache_free(range_seg_cache, rs_before); 2020713e232SGeorge Wilson rs = rs_after; 2030713e232SGeorge Wilson } else if (merge_before) { 2040713e232SGeorge Wilson if (rt->rt_ops != NULL) 2050713e232SGeorge Wilson rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg); 2060713e232SGeorge Wilson 2070713e232SGeorge Wilson range_tree_stat_decr(rt, rs_before); 2080713e232SGeorge Wilson 2090713e232SGeorge Wilson rs_before->rs_end = end; 2100713e232SGeorge Wilson rs = rs_before; 2110713e232SGeorge Wilson } else if (merge_after) { 2120713e232SGeorge Wilson if (rt->rt_ops != NULL) 2130713e232SGeorge Wilson rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg); 2140713e232SGeorge Wilson 2150713e232SGeorge Wilson range_tree_stat_decr(rt, rs_after); 2160713e232SGeorge Wilson 2170713e232SGeorge Wilson rs_after->rs_start = start; 2180713e232SGeorge Wilson rs = rs_after; 2190713e232SGeorge Wilson } else { 2200713e232SGeorge Wilson rs = kmem_cache_alloc(range_seg_cache, KM_SLEEP); 2210713e232SGeorge Wilson rs->rs_start = start; 2220713e232SGeorge Wilson rs->rs_end = end; 2230713e232SGeorge Wilson avl_insert(&rt->rt_root, rs, where); 2240713e232SGeorge Wilson } 2250713e232SGeorge Wilson 2260713e232SGeorge Wilson if (rt->rt_ops != NULL) 2270713e232SGeorge Wilson rt->rt_ops->rtop_add(rt, rs, rt->rt_arg); 2280713e232SGeorge Wilson 2290713e232SGeorge Wilson range_tree_stat_incr(rt, rs); 2300713e232SGeorge Wilson rt->rt_space += size; 2310713e232SGeorge Wilson } 2320713e232SGeorge Wilson 2330713e232SGeorge Wilson void 2340713e232SGeorge Wilson range_tree_remove(void *arg, uint64_t start, uint64_t size) 2350713e232SGeorge Wilson { 2360713e232SGeorge Wilson range_tree_t *rt = arg; 2370713e232SGeorge Wilson avl_index_t where; 2380713e232SGeorge Wilson range_seg_t rsearch, *rs, *newseg; 2390713e232SGeorge Wilson uint64_t end = start + size; 2400713e232SGeorge Wilson boolean_t left_over, right_over; 2410713e232SGeorge Wilson 2420713e232SGeorge Wilson VERIFY3U(size, !=, 0); 2430713e232SGeorge Wilson VERIFY3U(size, <=, rt->rt_space); 2440713e232SGeorge Wilson 2450713e232SGeorge Wilson rsearch.rs_start = start; 2460713e232SGeorge Wilson rsearch.rs_end = end; 2470713e232SGeorge Wilson rs = avl_find(&rt->rt_root, &rsearch, &where); 2480713e232SGeorge Wilson 2490713e232SGeorge Wilson /* Make sure we completely overlap with someone */ 2500713e232SGeorge Wilson if (rs == NULL) { 2510713e232SGeorge Wilson zfs_panic_recover("zfs: freeing free segment " 2520713e232SGeorge Wilson "(offset=%llu size=%llu)", 2530713e232SGeorge Wilson (longlong_t)start, (longlong_t)size); 2540713e232SGeorge Wilson return; 2550713e232SGeorge Wilson } 2560713e232SGeorge Wilson VERIFY3U(rs->rs_start, <=, start); 2570713e232SGeorge Wilson VERIFY3U(rs->rs_end, >=, end); 2580713e232SGeorge Wilson 2590713e232SGeorge Wilson left_over = (rs->rs_start != start); 2600713e232SGeorge Wilson right_over = (rs->rs_end != end); 2610713e232SGeorge Wilson 2620713e232SGeorge Wilson range_tree_stat_decr(rt, rs); 2630713e232SGeorge Wilson 2640713e232SGeorge Wilson if (rt->rt_ops != NULL) 2650713e232SGeorge Wilson rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg); 2660713e232SGeorge Wilson 2670713e232SGeorge Wilson if (left_over && right_over) { 2680713e232SGeorge Wilson newseg = kmem_cache_alloc(range_seg_cache, KM_SLEEP); 2690713e232SGeorge Wilson newseg->rs_start = end; 2700713e232SGeorge Wilson newseg->rs_end = rs->rs_end; 2710713e232SGeorge Wilson range_tree_stat_incr(rt, newseg); 2720713e232SGeorge Wilson 2730713e232SGeorge Wilson rs->rs_end = start; 2740713e232SGeorge Wilson 2750713e232SGeorge Wilson avl_insert_here(&rt->rt_root, newseg, rs, AVL_AFTER); 2760713e232SGeorge Wilson if (rt->rt_ops != NULL) 2770713e232SGeorge Wilson rt->rt_ops->rtop_add(rt, newseg, rt->rt_arg); 2780713e232SGeorge Wilson } else if (left_over) { 2790713e232SGeorge Wilson rs->rs_end = start; 2800713e232SGeorge Wilson } else if (right_over) { 2810713e232SGeorge Wilson rs->rs_start = end; 2820713e232SGeorge Wilson } else { 2830713e232SGeorge Wilson avl_remove(&rt->rt_root, rs); 2840713e232SGeorge Wilson kmem_cache_free(range_seg_cache, rs); 2850713e232SGeorge Wilson rs = NULL; 2860713e232SGeorge Wilson } 2870713e232SGeorge Wilson 2880713e232SGeorge Wilson if (rs != NULL) { 2890713e232SGeorge Wilson range_tree_stat_incr(rt, rs); 2900713e232SGeorge Wilson 2910713e232SGeorge Wilson if (rt->rt_ops != NULL) 2920713e232SGeorge Wilson rt->rt_ops->rtop_add(rt, rs, rt->rt_arg); 2930713e232SGeorge Wilson } 2940713e232SGeorge Wilson 2950713e232SGeorge Wilson rt->rt_space -= size; 2960713e232SGeorge Wilson } 2970713e232SGeorge Wilson 2980713e232SGeorge Wilson static range_seg_t * 299bf16b11eSMatthew Ahrens range_tree_find_impl(range_tree_t *rt, uint64_t start, uint64_t size) 3000713e232SGeorge Wilson { 301bf16b11eSMatthew Ahrens avl_index_t where; 302bf16b11eSMatthew Ahrens range_seg_t rsearch; 3030713e232SGeorge Wilson uint64_t end = start + size; 3040713e232SGeorge Wilson 3050713e232SGeorge Wilson VERIFY(size != 0); 3060713e232SGeorge Wilson 3070713e232SGeorge Wilson rsearch.rs_start = start; 3080713e232SGeorge Wilson rsearch.rs_end = end; 309bf16b11eSMatthew Ahrens return (avl_find(&rt->rt_root, &rsearch, &where)); 310bf16b11eSMatthew Ahrens } 3110713e232SGeorge Wilson 312bf16b11eSMatthew Ahrens static range_seg_t * 313bf16b11eSMatthew Ahrens range_tree_find(range_tree_t *rt, uint64_t start, uint64_t size) 314bf16b11eSMatthew Ahrens { 315bf16b11eSMatthew Ahrens range_seg_t *rs = range_tree_find_impl(rt, start, size); 316bf16b11eSMatthew Ahrens if (rs != NULL && rs->rs_start <= start && rs->rs_end >= start + size) 3170713e232SGeorge Wilson return (rs); 3180713e232SGeorge Wilson return (NULL); 3190713e232SGeorge Wilson } 3200713e232SGeorge Wilson 3210713e232SGeorge Wilson void 3220713e232SGeorge Wilson range_tree_verify(range_tree_t *rt, uint64_t off, uint64_t size) 3230713e232SGeorge Wilson { 3240713e232SGeorge Wilson range_seg_t *rs; 3250713e232SGeorge Wilson 326bf16b11eSMatthew Ahrens rs = range_tree_find(rt, off, size); 3270713e232SGeorge Wilson if (rs != NULL) 3280713e232SGeorge Wilson panic("freeing free block; rs=%p", (void *)rs); 3290713e232SGeorge Wilson } 3300713e232SGeorge Wilson 3310713e232SGeorge Wilson boolean_t 3320713e232SGeorge Wilson range_tree_contains(range_tree_t *rt, uint64_t start, uint64_t size) 3330713e232SGeorge Wilson { 334bf16b11eSMatthew Ahrens return (range_tree_find(rt, start, size) != NULL); 335bf16b11eSMatthew Ahrens } 3360713e232SGeorge Wilson 337bf16b11eSMatthew Ahrens /* 338bf16b11eSMatthew Ahrens * Ensure that this range is not in the tree, regardless of whether 339bf16b11eSMatthew Ahrens * it is currently in the tree. 340bf16b11eSMatthew Ahrens */ 341bf16b11eSMatthew Ahrens void 342bf16b11eSMatthew Ahrens range_tree_clear(range_tree_t *rt, uint64_t start, uint64_t size) 343bf16b11eSMatthew Ahrens { 344bf16b11eSMatthew Ahrens range_seg_t *rs; 345bf16b11eSMatthew Ahrens 346*5cabbc6bSPrashanth Sreenivasa if (size == 0) 347*5cabbc6bSPrashanth Sreenivasa return; 348*5cabbc6bSPrashanth Sreenivasa 349bf16b11eSMatthew Ahrens while ((rs = range_tree_find_impl(rt, start, size)) != NULL) { 350bf16b11eSMatthew Ahrens uint64_t free_start = MAX(rs->rs_start, start); 351bf16b11eSMatthew Ahrens uint64_t free_end = MIN(rs->rs_end, start + size); 352bf16b11eSMatthew Ahrens range_tree_remove(rt, free_start, free_end - free_start); 353bf16b11eSMatthew Ahrens } 3540713e232SGeorge Wilson } 3550713e232SGeorge Wilson 3560713e232SGeorge Wilson void 3570713e232SGeorge Wilson range_tree_swap(range_tree_t **rtsrc, range_tree_t **rtdst) 3580713e232SGeorge Wilson { 3590713e232SGeorge Wilson range_tree_t *rt; 3600713e232SGeorge Wilson 3610713e232SGeorge Wilson ASSERT0(range_tree_space(*rtdst)); 3620713e232SGeorge Wilson ASSERT0(avl_numnodes(&(*rtdst)->rt_root)); 3630713e232SGeorge Wilson 3640713e232SGeorge Wilson rt = *rtsrc; 3650713e232SGeorge Wilson *rtsrc = *rtdst; 3660713e232SGeorge Wilson *rtdst = rt; 3670713e232SGeorge Wilson } 3680713e232SGeorge Wilson 3690713e232SGeorge Wilson void 3700713e232SGeorge Wilson range_tree_vacate(range_tree_t *rt, range_tree_func_t *func, void *arg) 3710713e232SGeorge Wilson { 3720713e232SGeorge Wilson range_seg_t *rs; 3730713e232SGeorge Wilson void *cookie = NULL; 3740713e232SGeorge Wilson 3750713e232SGeorge Wilson 3760713e232SGeorge Wilson if (rt->rt_ops != NULL) 3770713e232SGeorge Wilson rt->rt_ops->rtop_vacate(rt, rt->rt_arg); 3780713e232SGeorge Wilson 3790713e232SGeorge Wilson while ((rs = avl_destroy_nodes(&rt->rt_root, &cookie)) != NULL) { 3800713e232SGeorge Wilson if (func != NULL) 3810713e232SGeorge Wilson func(arg, rs->rs_start, rs->rs_end - rs->rs_start); 3820713e232SGeorge Wilson kmem_cache_free(range_seg_cache, rs); 3830713e232SGeorge Wilson } 3840713e232SGeorge Wilson 3850713e232SGeorge Wilson bzero(rt->rt_histogram, sizeof (rt->rt_histogram)); 3860713e232SGeorge Wilson rt->rt_space = 0; 3870713e232SGeorge Wilson } 3880713e232SGeorge Wilson 3890713e232SGeorge Wilson void 3900713e232SGeorge Wilson range_tree_walk(range_tree_t *rt, range_tree_func_t *func, void *arg) 3910713e232SGeorge Wilson { 3920713e232SGeorge Wilson range_seg_t *rs; 3930713e232SGeorge Wilson 3940713e232SGeorge Wilson 3950713e232SGeorge Wilson for (rs = avl_first(&rt->rt_root); rs; rs = AVL_NEXT(&rt->rt_root, rs)) 3960713e232SGeorge Wilson func(arg, rs->rs_start, rs->rs_end - rs->rs_start); 3970713e232SGeorge Wilson } 3980713e232SGeorge Wilson 3990713e232SGeorge Wilson uint64_t 4000713e232SGeorge Wilson range_tree_space(range_tree_t *rt) 4010713e232SGeorge Wilson { 4020713e232SGeorge Wilson return (rt->rt_space); 4030713e232SGeorge Wilson } 404