[mirror_zfs.git] / module / zfs / range_tree.c

/*
 * CDDL HEADER START
 *
 * The contents of this file are subject to the terms of the
 * Common Development and Distribution License (the "License").
 * You may not use this file except in compliance with the License.
 *
 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
 * or http://www.opensolaris.org/os/licensing.
 * See the License for the specific language governing permissions
 * and limitations under the License.
 *
 * When distributing Covered Code, include this CDDL HEADER in each
 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
 * If applicable, add the following below this CDDL HEADER, with the
 * fields enclosed by brackets "[]" replaced with your own identifying
 * information: Portions Copyright [yyyy] [name of copyright owner]
 *
 * CDDL HEADER END
 */
/*
 * Copyright 2009 Sun Microsystems, Inc.  All rights reserved.
 * Use is subject to license terms.
 */
/*
 * Copyright (c) 2013 by Delphix. All rights reserved.
 */

#include <sys/zfs_context.h>
#include <sys/spa.h>
#include <sys/dmu.h>
#include <sys/dnode.h>
#include <sys/zio.h>
#include <sys/range_tree.h>

static kmem_cache_t *range_seg_cache;

void
range_tree_init(void)
{
	ASSERT(range_seg_cache == NULL);
	range_seg_cache = kmem_cache_create("range_seg_cache",
	    sizeof (range_seg_t), 0, NULL, NULL, NULL, NULL, NULL, 0);
}

void
range_tree_fini(void)
{
	kmem_cache_destroy(range_seg_cache);
	range_seg_cache = NULL;
}

void
range_tree_stat_verify(range_tree_t *rt)
{
	range_seg_t *rs;
	uint64_t hist[RANGE_TREE_HISTOGRAM_SIZE] = { 0 };
	int i;

	for (rs = avl_first(&rt->rt_root); rs != NULL;
	    rs = AVL_NEXT(&rt->rt_root, rs)) {
		uint64_t size = rs->rs_end - rs->rs_start;
		int idx	= highbit(size) - 1;

		hist[idx]++;
		ASSERT3U(hist[idx], !=, 0);
	}

	for (i = 0; i < RANGE_TREE_HISTOGRAM_SIZE; i++) {
		if (hist[i] != rt->rt_histogram[i]) {
			zfs_dbgmsg("i=%d, hist=%p, hist=%llu, rt_hist=%llu",
			    i, hist, hist[i], rt->rt_histogram[i]);
		}
		VERIFY3U(hist[i], ==, rt->rt_histogram[i]);
	}
}

static void
range_tree_stat_incr(range_tree_t *rt, range_seg_t *rs)
{
	uint64_t size = rs->rs_end - rs->rs_start;
	int idx = highbit(size) - 1;

	ASSERT3U(idx, <,
	    sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram));

	ASSERT(MUTEX_HELD(rt->rt_lock));
	rt->rt_histogram[idx]++;
	ASSERT3U(rt->rt_histogram[idx], !=, 0);
}

static void
range_tree_stat_decr(range_tree_t *rt, range_seg_t *rs)
{
	uint64_t size = rs->rs_end - rs->rs_start;
	int idx = highbit(size) - 1;

	ASSERT3U(idx, <,
	    sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram));

	ASSERT(MUTEX_HELD(rt->rt_lock));
	ASSERT3U(rt->rt_histogram[idx], !=, 0);
	rt->rt_histogram[idx]--;
}

/*
 * NOTE: caller is responsible for all locking.
 */
static int
range_tree_seg_compare(const void *x1, const void *x2)
{
	const range_seg_t *r1 = x1;
	const range_seg_t *r2 = x2;

	if (r1->rs_start < r2->rs_start) {
		if (r1->rs_end > r2->rs_start)
			return (0);
		return (-1);
	}
	if (r1->rs_start > r2->rs_start) {
		if (r1->rs_start < r2->rs_end)
			return (0);
		return (1);
	}
	return (0);
}

range_tree_t *
range_tree_create(range_tree_ops_t *ops, void *arg, kmutex_t *lp)
{
	range_tree_t *rt;

	rt = kmem_zalloc(sizeof (range_tree_t), KM_PUSHPAGE);

	avl_create(&rt->rt_root, range_tree_seg_compare,
	    sizeof (range_seg_t), offsetof(range_seg_t, rs_node));

	rt->rt_lock = lp;
	rt->rt_ops = ops;
	rt->rt_arg = arg;

	if (rt->rt_ops != NULL)
		rt->rt_ops->rtop_create(rt, rt->rt_arg);

	return (rt);
}

void
range_tree_destroy(range_tree_t *rt)
{
	VERIFY0(rt->rt_space);

	if (rt->rt_ops != NULL)
		rt->rt_ops->rtop_destroy(rt, rt->rt_arg);

	avl_destroy(&rt->rt_root);
	kmem_free(rt, sizeof (*rt));
}

void
range_tree_add(void *arg, uint64_t start, uint64_t size)
{
	range_tree_t *rt = arg;
	avl_index_t where;
	range_seg_t rsearch, *rs_before, *rs_after, *rs;
	uint64_t end = start + size;
	boolean_t merge_before, merge_after;

	ASSERT(MUTEX_HELD(rt->rt_lock));
	VERIFY(size != 0);

	rsearch.rs_start = start;
	rsearch.rs_end = end;
	rs = avl_find(&rt->rt_root, &rsearch, &where);

	if (rs != NULL && rs->rs_start <= start && rs->rs_end >= end) {
		zfs_panic_recover("zfs: allocating allocated segment"
		    "(offset=%llu size=%llu)\n",
		    (longlong_t)start, (longlong_t)size);
		return;
	}

	/* Make sure we don't overlap with either of our neighbors */
	VERIFY(rs == NULL);

	rs_before = avl_nearest(&rt->rt_root, where, AVL_BEFORE);
	rs_after = avl_nearest(&rt->rt_root, where, AVL_AFTER);

	merge_before = (rs_before != NULL && rs_before->rs_end == start);
	merge_after = (rs_after != NULL && rs_after->rs_start == end);

	if (merge_before && merge_after) {
		avl_remove(&rt->rt_root, rs_before);
		if (rt->rt_ops != NULL) {
			rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg);
			rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg);
		}

		range_tree_stat_decr(rt, rs_before);
		range_tree_stat_decr(rt, rs_after);

		rs_after->rs_start = rs_before->rs_start;
		kmem_cache_free(range_seg_cache, rs_before);
		rs = rs_after;
	} else if (merge_before) {
		if (rt->rt_ops != NULL)
			rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg);

		range_tree_stat_decr(rt, rs_before);

		rs_before->rs_end = end;
		rs = rs_before;
	} else if (merge_after) {
		if (rt->rt_ops != NULL)
			rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg);

		range_tree_stat_decr(rt, rs_after);

		rs_after->rs_start = start;
		rs = rs_after;
	} else {
		rs = kmem_cache_alloc(range_seg_cache, KM_PUSHPAGE);
		rs->rs_start = start;
		rs->rs_end = end;
		avl_insert(&rt->rt_root, rs, where);
	}

	if (rt->rt_ops != NULL)
		rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);

	range_tree_stat_incr(rt, rs);
	rt->rt_space += size;
}

void
range_tree_remove(void *arg, uint64_t start, uint64_t size)
{
	range_tree_t *rt = arg;
	avl_index_t where;
	range_seg_t rsearch, *rs, *newseg;
	uint64_t end = start + size;
	boolean_t left_over, right_over;

	ASSERT(MUTEX_HELD(rt->rt_lock));
	VERIFY3U(size, !=, 0);
	VERIFY3U(size, <=, rt->rt_space);

	rsearch.rs_start = start;
	rsearch.rs_end = end;
	rs = avl_find(&rt->rt_root, &rsearch, &where);

	/* Make sure we completely overlap with someone */
	if (rs == NULL) {
		zfs_panic_recover("zfs: freeing free segment "
		    "(offset=%llu size=%llu)",
		    (longlong_t)start, (longlong_t)size);
		return;
	}
	VERIFY3U(rs->rs_start, <=, start);
	VERIFY3U(rs->rs_end, >=, end);

	left_over = (rs->rs_start != start);
	right_over = (rs->rs_end != end);

	range_tree_stat_decr(rt, rs);

	if (rt->rt_ops != NULL)
		rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);

	if (left_over && right_over) {
		newseg = kmem_cache_alloc(range_seg_cache, KM_PUSHPAGE);
		newseg->rs_start = end;
		newseg->rs_end = rs->rs_end;
		range_tree_stat_incr(rt, newseg);

		rs->rs_end = start;

		avl_insert_here(&rt->rt_root, newseg, rs, AVL_AFTER);
		if (rt->rt_ops != NULL)
			rt->rt_ops->rtop_add(rt, newseg, rt->rt_arg);
	} else if (left_over) {
		rs->rs_end = start;
	} else if (right_over) {
		rs->rs_start = end;
	} else {
		avl_remove(&rt->rt_root, rs);
		kmem_cache_free(range_seg_cache, rs);
		rs = NULL;
	}

	if (rs != NULL) {
		range_tree_stat_incr(rt, rs);

		if (rt->rt_ops != NULL)
			rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);
	}

	rt->rt_space -= size;
}

static range_seg_t *
range_tree_find(range_tree_t *rt, uint64_t start, uint64_t size,
    avl_index_t *wherep)
{
	range_seg_t rsearch, *rs;
	uint64_t end = start + size;

	ASSERT(MUTEX_HELD(rt->rt_lock));
	VERIFY(size != 0);

	rsearch.rs_start = start;
	rsearch.rs_end = end;
	rs = avl_find(&rt->rt_root, &rsearch, wherep);

	if (rs != NULL && rs->rs_start <= start && rs->rs_end >= end)
		return (rs);
	return (NULL);
}

void
range_tree_verify(range_tree_t *rt, uint64_t off, uint64_t size)
{
	range_seg_t *rs;
	avl_index_t where;

	mutex_enter(rt->rt_lock);
	rs = range_tree_find(rt, off, size, &where);
	if (rs != NULL)
		panic("freeing free block; rs=%p", (void *)rs);
	mutex_exit(rt->rt_lock);
}

boolean_t
range_tree_contains(range_tree_t *rt, uint64_t start, uint64_t size)
{
	avl_index_t where;

	return (range_tree_find(rt, start, size, &where) != NULL);
}

void
range_tree_swap(range_tree_t **rtsrc, range_tree_t **rtdst)
{
	range_tree_t *rt;

	ASSERT(MUTEX_HELD((*rtsrc)->rt_lock));
	ASSERT0(range_tree_space(*rtdst));
	ASSERT0(avl_numnodes(&(*rtdst)->rt_root));

	rt = *rtsrc;
	*rtsrc = *rtdst;
	*rtdst = rt;
}

void
range_tree_vacate(range_tree_t *rt, range_tree_func_t *func, void *arg)
{
	range_seg_t *rs;
	void *cookie = NULL;

	ASSERT(MUTEX_HELD(rt->rt_lock));

	if (rt->rt_ops != NULL)
		rt->rt_ops->rtop_vacate(rt, rt->rt_arg);

	while ((rs = avl_destroy_nodes(&rt->rt_root, &cookie)) != NULL) {
		if (func != NULL)
			func(arg, rs->rs_start, rs->rs_end - rs->rs_start);
		kmem_cache_free(range_seg_cache, rs);
	}

	bzero(rt->rt_histogram, sizeof (rt->rt_histogram));
	rt->rt_space = 0;
}

void
range_tree_walk(range_tree_t *rt, range_tree_func_t *func, void *arg)
{
	range_seg_t *rs;

	ASSERT(MUTEX_HELD(rt->rt_lock));

	for (rs = avl_first(&rt->rt_root); rs; rs = AVL_NEXT(&rt->rt_root, rs))
		func(arg, rs->rs_start, rs->rs_end - rs->rs_start);
}

uint64_t
range_tree_space(range_tree_t *rt)
{
	return (rt->rt_space);
}
Commit	Line	Data
93cf2076 GW	1	/*
	2	* CDDL HEADER START
	3	*
	4	* The contents of this file are subject to the terms of the
	5	* Common Development and Distribution License (the "License").
	6	* You may not use this file except in compliance with the License.
	7	*
	8	* You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
	9	* or http://www.opensolaris.org/os/licensing.
	10	* See the License for the specific language governing permissions
	11	* and limitations under the License.
	12	*
	13	* When distributing Covered Code, include this CDDL HEADER in each
	14	* file and include the License file at usr/src/OPENSOLARIS.LICENSE.
	15	* If applicable, add the following below this CDDL HEADER, with the
	16	* fields enclosed by brackets "[]" replaced with your own identifying
	17	* information: Portions Copyright [yyyy] [name of copyright owner]
	18	*
	19	* CDDL HEADER END
	20	*/
	21	/*
	22	* Copyright 2009 Sun Microsystems, Inc. All rights reserved.
	23	* Use is subject to license terms.
	24	*/
	25	/*
	26	* Copyright (c) 2013 by Delphix. All rights reserved.
	27	*/
	28
	29	#include <sys/zfs_context.h>
	30	#include <sys/spa.h>
	31	#include <sys/dmu.h>
	32	#include <sys/dnode.h>
	33	#include <sys/zio.h>
	34	#include <sys/range_tree.h>
	35
	36	static kmem_cache_t *range_seg_cache;
	37
	38	void
	39	range_tree_init(void)
	40	{
	41	ASSERT(range_seg_cache == NULL);
	42	range_seg_cache = kmem_cache_create("range_seg_cache",
	43	sizeof (range_seg_t), 0, NULL, NULL, NULL, NULL, NULL, 0);
	44	}
	45
	46	void
	47	range_tree_fini(void)
	48	{
	49	kmem_cache_destroy(range_seg_cache);
	50	range_seg_cache = NULL;
	51	}
	52
	53	void
	54	range_tree_stat_verify(range_tree_t *rt)
	55	{
	56	range_seg_t *rs;
	57	uint64_t hist[RANGE_TREE_HISTOGRAM_SIZE] = { 0 };
	58	int i;
	59
	60	for (rs = avl_first(&rt->rt_root); rs != NULL;
	61	rs = AVL_NEXT(&rt->rt_root, rs)) {
	62	uint64_t size = rs->rs_end - rs->rs_start;
	63	int idx = highbit(size) - 1;
	64
65	hist[idx]++;
66	ASSERT3U(hist[idx], !=, 0);
67	}
68
69	for (i = 0; i < RANGE_TREE_HISTOGRAM_SIZE; i++) {
70	if (hist[i] != rt->rt_histogram[i]) {
71	zfs_dbgmsg("i=%d, hist=%p, hist=%llu, rt_hist=%llu",
72	i, hist, hist[i], rt->rt_histogram[i]);
73	}
74	VERIFY3U(hist[i], ==, rt->rt_histogram[i]);
75	}
76	}
77
78	static void
79	range_tree_stat_incr(range_tree_t rt, range_seg_t rs)
80	{
81	uint64_t size = rs->rs_end - rs->rs_start;
82	int idx = highbit(size) - 1;
83
84	ASSERT3U(idx, <,
85	sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram));
86
87	ASSERT(MUTEX_HELD(rt->rt_lock));
88	rt->rt_histogram[idx]++;
89	ASSERT3U(rt->rt_histogram[idx], !=, 0);
90	}
91
92	static void
93	range_tree_stat_decr(range_tree_t rt, range_seg_t rs)
94	{
95	uint64_t size = rs->rs_end - rs->rs_start;
96	int idx = highbit(size) - 1;
97
98	ASSERT3U(idx, <,
99	sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram));
100
101	ASSERT(MUTEX_HELD(rt->rt_lock));
102	ASSERT3U(rt->rt_histogram[idx], !=, 0);
103	rt->rt_histogram[idx]--;
104	}
105
106	/*
107	* NOTE: caller is responsible for all locking.
108	*/
109	static int
110	range_tree_seg_compare(const void x1, const void x2)
111	{
112	const range_seg_t *r1 = x1;
113	const range_seg_t *r2 = x2;
114
115	if (r1->rs_start < r2->rs_start) {
116	if (r1->rs_end > r2->rs_start)
117	return (0);
118	return (-1);
119	}
120	if (r1->rs_start > r2->rs_start) {
121	if (r1->rs_start < r2->rs_end)
122	return (0);
123	return (1);
124	}
125	return (0);
126	}
127
128	range_tree_t *
129	range_tree_create(range_tree_ops_t ops, void arg, kmutex_t *lp)
130	{
131	range_tree_t *rt;
132
133	rt = kmem_zalloc(sizeof (range_tree_t), KM_PUSHPAGE);
134
135	avl_create(&rt->rt_root, range_tree_seg_compare,
136	sizeof (range_seg_t), offsetof(range_seg_t, rs_node));
137
138	rt->rt_lock = lp;
139	rt->rt_ops = ops;
140	rt->rt_arg = arg;
141
142	if (rt->rt_ops != NULL)
143	rt->rt_ops->rtop_create(rt, rt->rt_arg);
144
145	return (rt);
146	}
147
148	void
149	range_tree_destroy(range_tree_t *rt)
150	{
151	VERIFY0(rt->rt_space);
152
153	if (rt->rt_ops != NULL)
154	rt->rt_ops->rtop_destroy(rt, rt->rt_arg);
155
156	avl_destroy(&rt->rt_root);
157	kmem_free(rt, sizeof (*rt));
158	}
159
160	void
161	range_tree_add(void *arg, uint64_t start, uint64_t size)
162	{
163	range_tree_t *rt = arg;
164	avl_index_t where;
165	range_seg_t rsearch, rs_before, rs_after, *rs;
166	uint64_t end = start + size;
167	boolean_t merge_before, merge_after;
168
169	ASSERT(MUTEX_HELD(rt->rt_lock));
170	VERIFY(size != 0);
171
172	rsearch.rs_start = start;
173	rsearch.rs_end = end;
174	rs = avl_find(&rt->rt_root, &rsearch, &where);
175
176	if (rs != NULL && rs->rs_start <= start && rs->rs_end >= end) {
177	zfs_panic_recover("zfs: allocating allocated segment"
178	"(offset=%llu size=%llu)\n",
179	(longlong_t)start, (longlong_t)size);
180	return;
181	}
182
183	/* Make sure we don't overlap with either of our neighbors */
184	VERIFY(rs == NULL);
185
186	rs_before = avl_nearest(&rt->rt_root, where, AVL_BEFORE);
187	rs_after = avl_nearest(&rt->rt_root, where, AVL_AFTER);
188
189	merge_before = (rs_before != NULL && rs_before->rs_end == start);
190	merge_after = (rs_after != NULL && rs_after->rs_start == end);
191
192	if (merge_before && merge_after) {
193	avl_remove(&rt->rt_root, rs_before);
194	if (rt->rt_ops != NULL) {
195	rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg);
196	rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg);
197	}
198
199	range_tree_stat_decr(rt, rs_before);
200	range_tree_stat_decr(rt, rs_after);
201
202	rs_after->rs_start = rs_before->rs_start;
203	kmem_cache_free(range_seg_cache, rs_before);
204	rs = rs_after;
205	} else if (merge_before) {
206	if (rt->rt_ops != NULL)
207	rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg);
208
209	range_tree_stat_decr(rt, rs_before);
210
211	rs_before->rs_end = end;
212	rs = rs_before;
213	} else if (merge_after) {
214	if (rt->rt_ops != NULL)
215	rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg);
216
217	range_tree_stat_decr(rt, rs_after);
218
219	rs_after->rs_start = start;
220	rs = rs_after;
221	} else {
222	rs = kmem_cache_alloc(range_seg_cache, KM_PUSHPAGE);
223	rs->rs_start = start;
224	rs->rs_end = end;
225	avl_insert(&rt->rt_root, rs, where);
226	}
227
228	if (rt->rt_ops != NULL)
229	rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);
230
231	range_tree_stat_incr(rt, rs);
232	rt->rt_space += size;
233	}
234
235	void
236	range_tree_remove(void *arg, uint64_t start, uint64_t size)
237	{
238	range_tree_t *rt = arg;
239	avl_index_t where;
240	range_seg_t rsearch, rs, newseg;
241	uint64_t end = start + size;
242	boolean_t left_over, right_over;
243
244	ASSERT(MUTEX_HELD(rt->rt_lock));
245	VERIFY3U(size, !=, 0);
246	VERIFY3U(size, <=, rt->rt_space);
247
248	rsearch.rs_start = start;
249	rsearch.rs_end = end;
250	rs = avl_find(&rt->rt_root, &rsearch, &where);
251
252	/* Make sure we completely overlap with someone */
253	if (rs == NULL) {
254	zfs_panic_recover("zfs: freeing free segment "
255	"(offset=%llu size=%llu)",
256	(longlong_t)start, (longlong_t)size);
257	return;
258	}
259	VERIFY3U(rs->rs_start, <=, start);
260	VERIFY3U(rs->rs_end, >=, end);
261
262	left_over = (rs->rs_start != start);
263	right_over = (rs->rs_end != end);
264
265	range_tree_stat_decr(rt, rs);
266
267	if (rt->rt_ops != NULL)
268	rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);
269
270	if (left_over && right_over) {
271	newseg = kmem_cache_alloc(range_seg_cache, KM_PUSHPAGE);
272	newseg->rs_start = end;
273	newseg->rs_end = rs->rs_end;
274	range_tree_stat_incr(rt, newseg);
275
276	rs->rs_end = start;
277
278	avl_insert_here(&rt->rt_root, newseg, rs, AVL_AFTER);
279	if (rt->rt_ops != NULL)
280	rt->rt_ops->rtop_add(rt, newseg, rt->rt_arg);
281	} else if (left_over) {
282	rs->rs_end = start;
283	} else if (right_over) {
284	rs->rs_start = end;
285	} else {
286	avl_remove(&rt->rt_root, rs);
287	kmem_cache_free(range_seg_cache, rs);
288	rs = NULL;
289	}
290
291	if (rs != NULL) {
292	range_tree_stat_incr(rt, rs);
293
294	if (rt->rt_ops != NULL)
295	rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);
296	}
297
298	rt->rt_space -= size;
299	}
300
301	static range_seg_t *
302	range_tree_find(range_tree_t *rt, uint64_t start, uint64_t size,
303	avl_index_t *wherep)
304	{
305	range_seg_t rsearch, *rs;
306	uint64_t end = start + size;
307
308	ASSERT(MUTEX_HELD(rt->rt_lock));
309	VERIFY(size != 0);
310
311	rsearch.rs_start = start;
312	rsearch.rs_end = end;
313	rs = avl_find(&rt->rt_root, &rsearch, wherep);
314
315	if (rs != NULL && rs->rs_start <= start && rs->rs_end >= end)
316	return (rs);
317	return (NULL);
318	}
319
320	void
321	range_tree_verify(range_tree_t *rt, uint64_t off, uint64_t size)
322	{
323	range_seg_t *rs;
324	avl_index_t where;
325
326	mutex_enter(rt->rt_lock);
327	rs = range_tree_find(rt, off, size, &where);
328	if (rs != NULL)
329	panic("freeing free block; rs=%p", (void *)rs);
330	mutex_exit(rt->rt_lock);
331	}
332
333	boolean_t
334	range_tree_contains(range_tree_t *rt, uint64_t start, uint64_t size)
335	{
336	avl_index_t where;
337
338	return (range_tree_find(rt, start, size, &where) != NULL);
339	}
340
341	void
342	range_tree_swap(range_tree_t rtsrc, range_tree_t rtdst)
343	{
344	range_tree_t *rt;
345
346	ASSERT(MUTEX_HELD((*rtsrc)->rt_lock));
347	ASSERT0(range_tree_space(*rtdst));
348	ASSERT0(avl_numnodes(&(*rtdst)->rt_root));
349
350	rt = *rtsrc;
351	rtsrc = rtdst;
352	*rtdst = rt;
353	}
354
355	void
356	range_tree_vacate(range_tree_t rt, range_tree_func_t func, void *arg)
357	{
358	range_seg_t *rs;
359	void *cookie = NULL;
360
361	ASSERT(MUTEX_HELD(rt->rt_lock));
362
363	if (rt->rt_ops != NULL)
364	rt->rt_ops->rtop_vacate(rt, rt->rt_arg);
365
366	while ((rs = avl_destroy_nodes(&rt->rt_root, &cookie)) != NULL) {
367	if (func != NULL)
368	func(arg, rs->rs_start, rs->rs_end - rs->rs_start);
369	kmem_cache_free(range_seg_cache, rs);
370	}
371
372	bzero(rt->rt_histogram, sizeof (rt->rt_histogram));
373	rt->rt_space = 0;
374	}
375
376	void
377	range_tree_walk(range_tree_t rt, range_tree_func_t func, void *arg)
378	{
379	range_seg_t *rs;
380
381	ASSERT(MUTEX_HELD(rt->rt_lock));
382
383	for (rs = avl_first(&rt->rt_root); rs; rs = AVL_NEXT(&rt->rt_root, rs))
384	func(arg, rs->rs_start, rs->rs_end - rs->rs_start);
385	}
386
387	uint64_t
388	range_tree_space(range_tree_t *rt)
389	{
390	return (rt->rt_space);
391	}