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*bf16b11eSMatthew Ahrens * Copyright (c) 2013, 2014 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 360713e232SGeorge Wilson static 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; 63*bf16b11eSMatthew 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; 82*bf16b11eSMatthew Ahrens int idx = highbit64(size) - 1; 830713e232SGeorge Wilson 840713e232SGeorge Wilson ASSERT3U(idx, <, 850713e232SGeorge Wilson sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram)); 860713e232SGeorge Wilson 870713e232SGeorge Wilson ASSERT(MUTEX_HELD(rt->rt_lock)); 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; 96*bf16b11eSMatthew Ahrens int idx = highbit64(size) - 1; 970713e232SGeorge Wilson 980713e232SGeorge Wilson ASSERT3U(idx, <, 990713e232SGeorge Wilson sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram)); 1000713e232SGeorge Wilson 1010713e232SGeorge Wilson ASSERT(MUTEX_HELD(rt->rt_lock)); 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 * 1290713e232SGeorge Wilson range_tree_create(range_tree_ops_t *ops, void *arg, kmutex_t *lp) 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_lock = lp; 1390713e232SGeorge Wilson rt->rt_ops = ops; 1400713e232SGeorge Wilson rt->rt_arg = arg; 1410713e232SGeorge Wilson 1420713e232SGeorge Wilson if (rt->rt_ops != NULL) 1430713e232SGeorge Wilson rt->rt_ops->rtop_create(rt, rt->rt_arg); 1440713e232SGeorge Wilson 1450713e232SGeorge Wilson return (rt); 1460713e232SGeorge Wilson } 1470713e232SGeorge Wilson 1480713e232SGeorge Wilson void 1490713e232SGeorge Wilson range_tree_destroy(range_tree_t *rt) 1500713e232SGeorge Wilson { 1510713e232SGeorge Wilson VERIFY0(rt->rt_space); 1520713e232SGeorge Wilson 1530713e232SGeorge Wilson if (rt->rt_ops != NULL) 1540713e232SGeorge Wilson rt->rt_ops->rtop_destroy(rt, rt->rt_arg); 1550713e232SGeorge Wilson 1560713e232SGeorge Wilson avl_destroy(&rt->rt_root); 1570713e232SGeorge Wilson kmem_free(rt, sizeof (*rt)); 1580713e232SGeorge Wilson } 1590713e232SGeorge Wilson 1600713e232SGeorge Wilson void 1610713e232SGeorge Wilson range_tree_add(void *arg, uint64_t start, uint64_t size) 1620713e232SGeorge Wilson { 1630713e232SGeorge Wilson range_tree_t *rt = arg; 1640713e232SGeorge Wilson avl_index_t where; 1650713e232SGeorge Wilson range_seg_t rsearch, *rs_before, *rs_after, *rs; 1660713e232SGeorge Wilson uint64_t end = start + size; 1670713e232SGeorge Wilson boolean_t merge_before, merge_after; 1680713e232SGeorge Wilson 1690713e232SGeorge Wilson ASSERT(MUTEX_HELD(rt->rt_lock)); 1700713e232SGeorge Wilson VERIFY(size != 0); 1710713e232SGeorge Wilson 1720713e232SGeorge Wilson rsearch.rs_start = start; 1730713e232SGeorge Wilson rsearch.rs_end = end; 1740713e232SGeorge Wilson rs = avl_find(&rt->rt_root, &rsearch, &where); 1750713e232SGeorge Wilson 1760713e232SGeorge Wilson if (rs != NULL && rs->rs_start <= start && rs->rs_end >= end) { 1770713e232SGeorge Wilson zfs_panic_recover("zfs: allocating allocated segment" 1780713e232SGeorge Wilson "(offset=%llu size=%llu)\n", 1790713e232SGeorge Wilson (longlong_t)start, (longlong_t)size); 1800713e232SGeorge Wilson return; 1810713e232SGeorge Wilson } 1820713e232SGeorge Wilson 1830713e232SGeorge Wilson /* Make sure we don't overlap with either of our neighbors */ 1840713e232SGeorge Wilson VERIFY(rs == NULL); 1850713e232SGeorge Wilson 1860713e232SGeorge Wilson rs_before = avl_nearest(&rt->rt_root, where, AVL_BEFORE); 1870713e232SGeorge Wilson rs_after = avl_nearest(&rt->rt_root, where, AVL_AFTER); 1880713e232SGeorge Wilson 1890713e232SGeorge Wilson merge_before = (rs_before != NULL && rs_before->rs_end == start); 1900713e232SGeorge Wilson merge_after = (rs_after != NULL && rs_after->rs_start == end); 1910713e232SGeorge Wilson 1920713e232SGeorge Wilson if (merge_before && merge_after) { 1930713e232SGeorge Wilson avl_remove(&rt->rt_root, rs_before); 1940713e232SGeorge Wilson if (rt->rt_ops != NULL) { 1950713e232SGeorge Wilson rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg); 1960713e232SGeorge Wilson rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg); 1970713e232SGeorge Wilson } 1980713e232SGeorge Wilson 1990713e232SGeorge Wilson range_tree_stat_decr(rt, rs_before); 2000713e232SGeorge Wilson range_tree_stat_decr(rt, rs_after); 2010713e232SGeorge Wilson 2020713e232SGeorge Wilson rs_after->rs_start = rs_before->rs_start; 2030713e232SGeorge Wilson kmem_cache_free(range_seg_cache, rs_before); 2040713e232SGeorge Wilson rs = rs_after; 2050713e232SGeorge Wilson } else if (merge_before) { 2060713e232SGeorge Wilson if (rt->rt_ops != NULL) 2070713e232SGeorge Wilson rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg); 2080713e232SGeorge Wilson 2090713e232SGeorge Wilson range_tree_stat_decr(rt, rs_before); 2100713e232SGeorge Wilson 2110713e232SGeorge Wilson rs_before->rs_end = end; 2120713e232SGeorge Wilson rs = rs_before; 2130713e232SGeorge Wilson } else if (merge_after) { 2140713e232SGeorge Wilson if (rt->rt_ops != NULL) 2150713e232SGeorge Wilson rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg); 2160713e232SGeorge Wilson 2170713e232SGeorge Wilson range_tree_stat_decr(rt, rs_after); 2180713e232SGeorge Wilson 2190713e232SGeorge Wilson rs_after->rs_start = start; 2200713e232SGeorge Wilson rs = rs_after; 2210713e232SGeorge Wilson } else { 2220713e232SGeorge Wilson rs = kmem_cache_alloc(range_seg_cache, KM_SLEEP); 2230713e232SGeorge Wilson rs->rs_start = start; 2240713e232SGeorge Wilson rs->rs_end = end; 2250713e232SGeorge Wilson avl_insert(&rt->rt_root, rs, where); 2260713e232SGeorge Wilson } 2270713e232SGeorge Wilson 2280713e232SGeorge Wilson if (rt->rt_ops != NULL) 2290713e232SGeorge Wilson rt->rt_ops->rtop_add(rt, rs, rt->rt_arg); 2300713e232SGeorge Wilson 2310713e232SGeorge Wilson range_tree_stat_incr(rt, rs); 2320713e232SGeorge Wilson rt->rt_space += size; 2330713e232SGeorge Wilson } 2340713e232SGeorge Wilson 2350713e232SGeorge Wilson void 2360713e232SGeorge Wilson range_tree_remove(void *arg, uint64_t start, uint64_t size) 2370713e232SGeorge Wilson { 2380713e232SGeorge Wilson range_tree_t *rt = arg; 2390713e232SGeorge Wilson avl_index_t where; 2400713e232SGeorge Wilson range_seg_t rsearch, *rs, *newseg; 2410713e232SGeorge Wilson uint64_t end = start + size; 2420713e232SGeorge Wilson boolean_t left_over, right_over; 2430713e232SGeorge Wilson 2440713e232SGeorge Wilson ASSERT(MUTEX_HELD(rt->rt_lock)); 2450713e232SGeorge Wilson VERIFY3U(size, !=, 0); 2460713e232SGeorge Wilson VERIFY3U(size, <=, rt->rt_space); 2470713e232SGeorge Wilson 2480713e232SGeorge Wilson rsearch.rs_start = start; 2490713e232SGeorge Wilson rsearch.rs_end = end; 2500713e232SGeorge Wilson rs = avl_find(&rt->rt_root, &rsearch, &where); 2510713e232SGeorge Wilson 2520713e232SGeorge Wilson /* Make sure we completely overlap with someone */ 2530713e232SGeorge Wilson if (rs == NULL) { 2540713e232SGeorge Wilson zfs_panic_recover("zfs: freeing free segment " 2550713e232SGeorge Wilson "(offset=%llu size=%llu)", 2560713e232SGeorge Wilson (longlong_t)start, (longlong_t)size); 2570713e232SGeorge Wilson return; 2580713e232SGeorge Wilson } 2590713e232SGeorge Wilson VERIFY3U(rs->rs_start, <=, start); 2600713e232SGeorge Wilson VERIFY3U(rs->rs_end, >=, end); 2610713e232SGeorge Wilson 2620713e232SGeorge Wilson left_over = (rs->rs_start != start); 2630713e232SGeorge Wilson right_over = (rs->rs_end != end); 2640713e232SGeorge Wilson 2650713e232SGeorge Wilson range_tree_stat_decr(rt, rs); 2660713e232SGeorge Wilson 2670713e232SGeorge Wilson if (rt->rt_ops != NULL) 2680713e232SGeorge Wilson rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg); 2690713e232SGeorge Wilson 2700713e232SGeorge Wilson if (left_over && right_over) { 2710713e232SGeorge Wilson newseg = kmem_cache_alloc(range_seg_cache, KM_SLEEP); 2720713e232SGeorge Wilson newseg->rs_start = end; 2730713e232SGeorge Wilson newseg->rs_end = rs->rs_end; 2740713e232SGeorge Wilson range_tree_stat_incr(rt, newseg); 2750713e232SGeorge Wilson 2760713e232SGeorge Wilson rs->rs_end = start; 2770713e232SGeorge Wilson 2780713e232SGeorge Wilson avl_insert_here(&rt->rt_root, newseg, rs, AVL_AFTER); 2790713e232SGeorge Wilson if (rt->rt_ops != NULL) 2800713e232SGeorge Wilson rt->rt_ops->rtop_add(rt, newseg, rt->rt_arg); 2810713e232SGeorge Wilson } else if (left_over) { 2820713e232SGeorge Wilson rs->rs_end = start; 2830713e232SGeorge Wilson } else if (right_over) { 2840713e232SGeorge Wilson rs->rs_start = end; 2850713e232SGeorge Wilson } else { 2860713e232SGeorge Wilson avl_remove(&rt->rt_root, rs); 2870713e232SGeorge Wilson kmem_cache_free(range_seg_cache, rs); 2880713e232SGeorge Wilson rs = NULL; 2890713e232SGeorge Wilson } 2900713e232SGeorge Wilson 2910713e232SGeorge Wilson if (rs != NULL) { 2920713e232SGeorge Wilson range_tree_stat_incr(rt, rs); 2930713e232SGeorge Wilson 2940713e232SGeorge Wilson if (rt->rt_ops != NULL) 2950713e232SGeorge Wilson rt->rt_ops->rtop_add(rt, rs, rt->rt_arg); 2960713e232SGeorge Wilson } 2970713e232SGeorge Wilson 2980713e232SGeorge Wilson rt->rt_space -= size; 2990713e232SGeorge Wilson } 3000713e232SGeorge Wilson 3010713e232SGeorge Wilson static range_seg_t * 302*bf16b11eSMatthew Ahrens range_tree_find_impl(range_tree_t *rt, uint64_t start, uint64_t size) 3030713e232SGeorge Wilson { 304*bf16b11eSMatthew Ahrens avl_index_t where; 305*bf16b11eSMatthew Ahrens range_seg_t rsearch; 3060713e232SGeorge Wilson uint64_t end = start + size; 3070713e232SGeorge Wilson 3080713e232SGeorge Wilson ASSERT(MUTEX_HELD(rt->rt_lock)); 3090713e232SGeorge Wilson VERIFY(size != 0); 3100713e232SGeorge Wilson 3110713e232SGeorge Wilson rsearch.rs_start = start; 3120713e232SGeorge Wilson rsearch.rs_end = end; 313*bf16b11eSMatthew Ahrens return (avl_find(&rt->rt_root, &rsearch, &where)); 314*bf16b11eSMatthew Ahrens } 3150713e232SGeorge Wilson 316*bf16b11eSMatthew Ahrens static range_seg_t * 317*bf16b11eSMatthew Ahrens range_tree_find(range_tree_t *rt, uint64_t start, uint64_t size) 318*bf16b11eSMatthew Ahrens { 319*bf16b11eSMatthew Ahrens range_seg_t *rs = range_tree_find_impl(rt, start, size); 320*bf16b11eSMatthew Ahrens if (rs != NULL && rs->rs_start <= start && rs->rs_end >= start + size) 3210713e232SGeorge Wilson return (rs); 3220713e232SGeorge Wilson return (NULL); 3230713e232SGeorge Wilson } 3240713e232SGeorge Wilson 3250713e232SGeorge Wilson void 3260713e232SGeorge Wilson range_tree_verify(range_tree_t *rt, uint64_t off, uint64_t size) 3270713e232SGeorge Wilson { 3280713e232SGeorge Wilson range_seg_t *rs; 3290713e232SGeorge Wilson 3300713e232SGeorge Wilson mutex_enter(rt->rt_lock); 331*bf16b11eSMatthew Ahrens rs = range_tree_find(rt, off, size); 3320713e232SGeorge Wilson if (rs != NULL) 3330713e232SGeorge Wilson panic("freeing free block; rs=%p", (void *)rs); 3340713e232SGeorge Wilson mutex_exit(rt->rt_lock); 3350713e232SGeorge Wilson } 3360713e232SGeorge Wilson 3370713e232SGeorge Wilson boolean_t 3380713e232SGeorge Wilson range_tree_contains(range_tree_t *rt, uint64_t start, uint64_t size) 3390713e232SGeorge Wilson { 340*bf16b11eSMatthew Ahrens return (range_tree_find(rt, start, size) != NULL); 341*bf16b11eSMatthew Ahrens } 3420713e232SGeorge Wilson 343*bf16b11eSMatthew Ahrens /* 344*bf16b11eSMatthew Ahrens * Ensure that this range is not in the tree, regardless of whether 345*bf16b11eSMatthew Ahrens * it is currently in the tree. 346*bf16b11eSMatthew Ahrens */ 347*bf16b11eSMatthew Ahrens void 348*bf16b11eSMatthew Ahrens range_tree_clear(range_tree_t *rt, uint64_t start, uint64_t size) 349*bf16b11eSMatthew Ahrens { 350*bf16b11eSMatthew Ahrens range_seg_t *rs; 351*bf16b11eSMatthew Ahrens 352*bf16b11eSMatthew Ahrens while ((rs = range_tree_find_impl(rt, start, size)) != NULL) { 353*bf16b11eSMatthew Ahrens uint64_t free_start = MAX(rs->rs_start, start); 354*bf16b11eSMatthew Ahrens uint64_t free_end = MIN(rs->rs_end, start + size); 355*bf16b11eSMatthew Ahrens range_tree_remove(rt, free_start, free_end - free_start); 356*bf16b11eSMatthew Ahrens } 3570713e232SGeorge Wilson } 3580713e232SGeorge Wilson 3590713e232SGeorge Wilson void 3600713e232SGeorge Wilson range_tree_swap(range_tree_t **rtsrc, range_tree_t **rtdst) 3610713e232SGeorge Wilson { 3620713e232SGeorge Wilson range_tree_t *rt; 3630713e232SGeorge Wilson 3640713e232SGeorge Wilson ASSERT(MUTEX_HELD((*rtsrc)->rt_lock)); 3650713e232SGeorge Wilson ASSERT0(range_tree_space(*rtdst)); 3660713e232SGeorge Wilson ASSERT0(avl_numnodes(&(*rtdst)->rt_root)); 3670713e232SGeorge Wilson 3680713e232SGeorge Wilson rt = *rtsrc; 3690713e232SGeorge Wilson *rtsrc = *rtdst; 3700713e232SGeorge Wilson *rtdst = rt; 3710713e232SGeorge Wilson } 3720713e232SGeorge Wilson 3730713e232SGeorge Wilson void 3740713e232SGeorge Wilson range_tree_vacate(range_tree_t *rt, range_tree_func_t *func, void *arg) 3750713e232SGeorge Wilson { 3760713e232SGeorge Wilson range_seg_t *rs; 3770713e232SGeorge Wilson void *cookie = NULL; 3780713e232SGeorge Wilson 3790713e232SGeorge Wilson ASSERT(MUTEX_HELD(rt->rt_lock)); 3800713e232SGeorge Wilson 3810713e232SGeorge Wilson if (rt->rt_ops != NULL) 3820713e232SGeorge Wilson rt->rt_ops->rtop_vacate(rt, rt->rt_arg); 3830713e232SGeorge Wilson 3840713e232SGeorge Wilson while ((rs = avl_destroy_nodes(&rt->rt_root, &cookie)) != NULL) { 3850713e232SGeorge Wilson if (func != NULL) 3860713e232SGeorge Wilson func(arg, rs->rs_start, rs->rs_end - rs->rs_start); 3870713e232SGeorge Wilson kmem_cache_free(range_seg_cache, rs); 3880713e232SGeorge Wilson } 3890713e232SGeorge Wilson 3900713e232SGeorge Wilson bzero(rt->rt_histogram, sizeof (rt->rt_histogram)); 3910713e232SGeorge Wilson rt->rt_space = 0; 3920713e232SGeorge Wilson } 3930713e232SGeorge Wilson 3940713e232SGeorge Wilson void 3950713e232SGeorge Wilson range_tree_walk(range_tree_t *rt, range_tree_func_t *func, void *arg) 3960713e232SGeorge Wilson { 3970713e232SGeorge Wilson range_seg_t *rs; 3980713e232SGeorge Wilson 3990713e232SGeorge Wilson ASSERT(MUTEX_HELD(rt->rt_lock)); 4000713e232SGeorge Wilson 4010713e232SGeorge Wilson for (rs = avl_first(&rt->rt_root); rs; rs = AVL_NEXT(&rt->rt_root, rs)) 4020713e232SGeorge Wilson func(arg, rs->rs_start, rs->rs_end - rs->rs_start); 4030713e232SGeorge Wilson } 4040713e232SGeorge Wilson 4050713e232SGeorge Wilson uint64_t 4060713e232SGeorge Wilson range_tree_space(range_tree_t *rt) 4070713e232SGeorge Wilson { 4080713e232SGeorge Wilson return (rt->rt_space); 4090713e232SGeorge Wilson } 410