79 rs_copy(range_seg_t *src, range_seg_t *dest, range_tree_t *rt)  in rs_copy()  argument
81 	ASSERT3U(rt->rt_type, <, RANGE_SEG_NUM_TYPES);  in rs_copy()
83 	switch (rt->rt_type) {  in rs_copy()
100 range_tree_stat_verify(range_tree_t *rt)  in range_tree_stat_verify()  argument
107 	for (rs = zfs_btree_first(&rt->rt_root, &where); rs != NULL;  in range_tree_stat_verify()
108 	    rs = zfs_btree_next(&rt->rt_root, &where, &where)) {  in range_tree_stat_verify()
109 		uint64_t size = rs_get_end(rs, rt) - rs_get_start(rs, rt);  in range_tree_stat_verify()
117 		if (hist[i] != rt->rt_histogram[i]) {  in range_tree_stat_verify()
120 			    (u_longlong_t)rt->rt_histogram[i]);  in range_tree_stat_verify()
122 		VERIFY3U(hist[i], ==, rt->rt_histogram[i]);  in range_tree_stat_verify()
127 range_tree_stat_incr(range_tree_t *rt, range_seg_t *rs)  in range_tree_stat_incr()  argument
129 	uint64_t size = rs_get_end(rs, rt) - rs_get_start(rs, rt);  in range_tree_stat_incr()
134 	    sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram));  in range_tree_stat_incr()
136 	rt->rt_histogram[idx]++;  in range_tree_stat_incr()
137 	ASSERT3U(rt->rt_histogram[idx], !=, 0);  in range_tree_stat_incr()
141 range_tree_stat_decr(range_tree_t *rt, range_seg_t *rs)  in range_tree_stat_decr()  argument
143 	uint64_t size = rs_get_end(rs, rt) - rs_get_start(rs, rt);  in range_tree_stat_decr()
148 	    sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram));  in range_tree_stat_decr()
150 	ASSERT3U(rt->rt_histogram[idx], !=, 0);  in range_tree_stat_decr()
151 	rt->rt_histogram[idx]--;  in range_tree_stat_decr()
206 	range_tree_t *rt = kmem_zalloc(sizeof (range_tree_t), KM_SLEEP);  in ZFS_BTREE_FIND_IN_BUF_FUNC()  local
232 	zfs_btree_create(&rt->rt_root, compare, bt_find, size);  in ZFS_BTREE_FIND_IN_BUF_FUNC()
234 	rt->rt_ops = ops;  in ZFS_BTREE_FIND_IN_BUF_FUNC()
235 	rt->rt_gap = gap;  in ZFS_BTREE_FIND_IN_BUF_FUNC()
236 	rt->rt_arg = arg;  in ZFS_BTREE_FIND_IN_BUF_FUNC()
237 	rt->rt_type = type;  in ZFS_BTREE_FIND_IN_BUF_FUNC()
238 	rt->rt_start = start;  in ZFS_BTREE_FIND_IN_BUF_FUNC()
239 	rt->rt_shift = shift;  in ZFS_BTREE_FIND_IN_BUF_FUNC()
241 	if (rt->rt_ops != NULL && rt->rt_ops->rtop_create != NULL)  in ZFS_BTREE_FIND_IN_BUF_FUNC()
242 		rt->rt_ops->rtop_create(rt, rt->rt_arg);  in ZFS_BTREE_FIND_IN_BUF_FUNC()
244 	return (rt);  in ZFS_BTREE_FIND_IN_BUF_FUNC()
255 range_tree_destroy(range_tree_t *rt)  in range_tree_destroy()  argument
257 	VERIFY0(rt->rt_space);  in range_tree_destroy()
259 	if (rt->rt_ops != NULL && rt->rt_ops->rtop_destroy != NULL)  in range_tree_destroy()
260 		rt->rt_ops->rtop_destroy(rt, rt->rt_arg);  in range_tree_destroy()
262 	zfs_btree_destroy(&rt->rt_root);  in range_tree_destroy()
263 	kmem_free(rt, sizeof (*rt));  in range_tree_destroy()
267 range_tree_adjust_fill(range_tree_t *rt, range_seg_t *rs, int64_t delta)  in range_tree_adjust_fill()  argument
269 	if (delta < 0 && delta * -1 >= rs_get_fill(rs, rt)) {  in range_tree_adjust_fill()
272 		    (longlong_t)rs_get_start(rs, rt),  in range_tree_adjust_fill()
273 		    (longlong_t)rs_get_end(rs, rt));  in range_tree_adjust_fill()
275 	if (rs_get_fill(rs, rt) + delta > rs_get_end(rs, rt) -  in range_tree_adjust_fill()
276 	    rs_get_start(rs, rt)) {  in range_tree_adjust_fill()
279 		    (longlong_t)rs_get_start(rs, rt),  in range_tree_adjust_fill()
280 		    (longlong_t)rs_get_end(rs, rt));  in range_tree_adjust_fill()
283 	if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)  in range_tree_adjust_fill()
284 		rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);  in range_tree_adjust_fill()
285 	rs_set_fill(rs, rt, rs_get_fill(rs, rt) + delta);  in range_tree_adjust_fill()
286 	if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)  in range_tree_adjust_fill()
287 		rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);  in range_tree_adjust_fill()
293 	range_tree_t *rt = arg;  in range_tree_add_impl()  local
297 	uint64_t end = start + size, gap = rt->rt_gap;  in range_tree_add_impl()
305 	rs_set_start(&rsearch, rt, start);  in range_tree_add_impl()
306 	rs_set_end(&rsearch, rt, end);  in range_tree_add_impl()
307 	rs = zfs_btree_find(&rt->rt_root, &rsearch, &where);  in range_tree_add_impl()
324 		uint64_t rstart = rs_get_start(rs, rt);  in range_tree_add_impl()
325 		uint64_t rend = rs_get_end(rs, rt);  in range_tree_add_impl()
327 			range_tree_adjust_fill(rt, rs, fill);  in range_tree_add_impl()
331 		if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)  in range_tree_add_impl()
332 			rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);  in range_tree_add_impl()
334 		range_tree_stat_decr(rt, rs);  in range_tree_add_impl()
335 		rt->rt_space -= rend - rstart;  in range_tree_add_impl()
337 		fill += rs_get_fill(rs, rt);  in range_tree_add_impl()
342 		zfs_btree_remove(&rt->rt_root, rs);  in range_tree_add_impl()
343 		range_tree_add_impl(rt, start, size, fill);  in range_tree_add_impl()
355 	rs_before = zfs_btree_prev(&rt->rt_root, &where, &where_before);  in range_tree_add_impl()
356 	rs_after = zfs_btree_next(&rt->rt_root, &where, &where_after);  in range_tree_add_impl()
358 	merge_before = (rs_before != NULL && rs_get_end(rs_before, rt) >=  in range_tree_add_impl()
360 	merge_after = (rs_after != NULL && rs_get_start(rs_after, rt) <= end +  in range_tree_add_impl()
364 		bridge_size += start - rs_get_end(rs_before, rt);  in range_tree_add_impl()
366 		bridge_size += rs_get_start(rs_after, rt) - end;  in range_tree_add_impl()
369 		if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL) {  in range_tree_add_impl()
370 			rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg);  in range_tree_add_impl()
371 			rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg);  in range_tree_add_impl()
374 		range_tree_stat_decr(rt, rs_before);  in range_tree_add_impl()
375 		range_tree_stat_decr(rt, rs_after);  in range_tree_add_impl()
377 		rs_copy(rs_after, &tmp, rt);  in range_tree_add_impl()
378 		uint64_t before_start = rs_get_start_raw(rs_before, rt);  in range_tree_add_impl()
379 		uint64_t before_fill = rs_get_fill(rs_before, rt);  in range_tree_add_impl()
380 		uint64_t after_fill = rs_get_fill(rs_after, rt);  in range_tree_add_impl()
381 		zfs_btree_remove_idx(&rt->rt_root, &where_before);  in range_tree_add_impl()
387 		rs_after = zfs_btree_find(&rt->rt_root, &tmp, &where_after);  in range_tree_add_impl()
389 		rs_set_start_raw(rs_after, rt, before_start);  in range_tree_add_impl()
390 		rs_set_fill(rs_after, rt, after_fill + before_fill + fill);  in range_tree_add_impl()
393 		if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)  in range_tree_add_impl()
394 			rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg);  in range_tree_add_impl()
396 		range_tree_stat_decr(rt, rs_before);  in range_tree_add_impl()
398 		uint64_t before_fill = rs_get_fill(rs_before, rt);  in range_tree_add_impl()
399 		rs_set_end(rs_before, rt, end);  in range_tree_add_impl()
400 		rs_set_fill(rs_before, rt, before_fill + fill);  in range_tree_add_impl()
403 		if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)  in range_tree_add_impl()
404 			rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg);  in range_tree_add_impl()
406 		range_tree_stat_decr(rt, rs_after);  in range_tree_add_impl()
408 		uint64_t after_fill = rs_get_fill(rs_after, rt);  in range_tree_add_impl()
409 		rs_set_start(rs_after, rt, start);  in range_tree_add_impl()
410 		rs_set_fill(rs_after, rt, after_fill + fill);  in range_tree_add_impl()
415 		rs_set_start(rs, rt, start);  in range_tree_add_impl()
416 		rs_set_end(rs, rt, end);  in range_tree_add_impl()
417 		rs_set_fill(rs, rt, fill);  in range_tree_add_impl()
418 		zfs_btree_add_idx(&rt->rt_root, rs, &where);  in range_tree_add_impl()
422 		ASSERT3U(rs_get_fill(rs, rt), <=, rs_get_end(rs, rt) -  in range_tree_add_impl()
423 		    rs_get_start(rs, rt));  in range_tree_add_impl()
425 		ASSERT3U(rs_get_fill(rs, rt), ==, rs_get_end(rs, rt) -  in range_tree_add_impl()
426 		    rs_get_start(rs, rt));  in range_tree_add_impl()
429 	if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)  in range_tree_add_impl()
430 		rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);  in range_tree_add_impl()
432 	range_tree_stat_incr(rt, rs);  in range_tree_add_impl()
433 	rt->rt_space += size + bridge_size;  in range_tree_add_impl()
443 range_tree_remove_impl(range_tree_t *rt, uint64_t start, uint64_t size,  in range_tree_remove_impl()  argument
453 	VERIFY3U(size, <=, rt->rt_space);  in range_tree_remove_impl()
454 	if (rt->rt_type == RANGE_SEG64)  in range_tree_remove_impl()
457 	rs_set_start(&rsearch, rt, start);  in range_tree_remove_impl()
458 	rs_set_end(&rsearch, rt, end);  in range_tree_remove_impl()
459 	rs = zfs_btree_find(&rt->rt_root, &rsearch, &where);  in range_tree_remove_impl()
475 	if (rt->rt_gap != 0) {  in range_tree_remove_impl()
477 			if (rs_get_fill(rs, rt) == size) {  in range_tree_remove_impl()
478 				start = rs_get_start(rs, rt);  in range_tree_remove_impl()
479 				end = rs_get_end(rs, rt);  in range_tree_remove_impl()
482 				range_tree_adjust_fill(rt, rs, -size);  in range_tree_remove_impl()
485 		} else if (rs_get_start(rs, rt) != start ||  in range_tree_remove_impl()
486 		    rs_get_end(rs, rt) != end) {  in range_tree_remove_impl()
491 			    (longlong_t)rs_get_start(rs, rt),  in range_tree_remove_impl()
492 			    (longlong_t)rs_get_end(rs, rt) - rs_get_start(rs,  in range_tree_remove_impl()
493 			    rt));  in range_tree_remove_impl()
498 	VERIFY3U(rs_get_start(rs, rt), <=, start);  in range_tree_remove_impl()
499 	VERIFY3U(rs_get_end(rs, rt), >=, end);  in range_tree_remove_impl()
501 	left_over = (rs_get_start(rs, rt) != start);  in range_tree_remove_impl()
502 	right_over = (rs_get_end(rs, rt) != end);  in range_tree_remove_impl()
504 	range_tree_stat_decr(rt, rs);  in range_tree_remove_impl()
506 	if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)  in range_tree_remove_impl()
507 		rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);  in range_tree_remove_impl()
511 		rs_set_start(&newseg, rt, end);  in range_tree_remove_impl()
512 		rs_set_end_raw(&newseg, rt, rs_get_end_raw(rs, rt));  in range_tree_remove_impl()
513 		rs_set_fill(&newseg, rt, rs_get_end(rs, rt) - end);  in range_tree_remove_impl()
514 		range_tree_stat_incr(rt, &newseg);  in range_tree_remove_impl()
517 		rs_set_end(rs, rt, start);  in range_tree_remove_impl()
519 		rs_copy(rs, &rs_tmp, rt);  in range_tree_remove_impl()
520 		if (zfs_btree_next(&rt->rt_root, &where, &where) != NULL)  in range_tree_remove_impl()
521 			zfs_btree_add_idx(&rt->rt_root, &newseg, &where);  in range_tree_remove_impl()
523 			zfs_btree_add(&rt->rt_root, &newseg);  in range_tree_remove_impl()
525 		if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)  in range_tree_remove_impl()
526 			rt->rt_ops->rtop_add(rt, &newseg, rt->rt_arg);  in range_tree_remove_impl()
529 		rs_set_end(rs, rt, start);  in range_tree_remove_impl()
530 		rs_copy(rs, &rs_tmp, rt);  in range_tree_remove_impl()
533 		rs_set_start(rs, rt, end);  in range_tree_remove_impl()
534 		rs_copy(rs, &rs_tmp, rt);  in range_tree_remove_impl()
536 		zfs_btree_remove_idx(&rt->rt_root, &where);  in range_tree_remove_impl()
546 		rs_set_fill_raw(rs, rt, rs_get_end_raw(rs, rt) -  in range_tree_remove_impl()
547 		    rs_get_start_raw(rs, rt));  in range_tree_remove_impl()
548 		range_tree_stat_incr(rt, &rs_tmp);  in range_tree_remove_impl()
550 		if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)  in range_tree_remove_impl()
551 			rt->rt_ops->rtop_add(rt, &rs_tmp, rt->rt_arg);  in range_tree_remove_impl()
554 	rt->rt_space -= size;  in range_tree_remove_impl()
564 range_tree_remove_fill(range_tree_t *rt, uint64_t start, uint64_t size)  in range_tree_remove_fill()  argument
566 	range_tree_remove_impl(rt, start, size, B_TRUE);  in range_tree_remove_fill()
570 range_tree_resize_segment(range_tree_t *rt, range_seg_t *rs,  in range_tree_resize_segment()  argument
573 	int64_t delta = newsize - (rs_get_end(rs, rt) - rs_get_start(rs, rt));  in range_tree_resize_segment()
575 	range_tree_stat_decr(rt, rs);  in range_tree_resize_segment()
576 	if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)  in range_tree_resize_segment()
577 		rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);  in range_tree_resize_segment()
579 	rs_set_start(rs, rt, newstart);  in range_tree_resize_segment()
580 	rs_set_end(rs, rt, newstart + newsize);  in range_tree_resize_segment()
582 	range_tree_stat_incr(rt, rs);  in range_tree_resize_segment()
583 	if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)  in range_tree_resize_segment()
584 		rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);  in range_tree_resize_segment()
586 	rt->rt_space += delta;  in range_tree_resize_segment()
590 range_tree_find_impl(range_tree_t *rt, uint64_t start, uint64_t size)  in range_tree_find_impl()  argument
597 	rs_set_start(&rsearch, rt, start);  in range_tree_find_impl()
598 	rs_set_end(&rsearch, rt, end);  in range_tree_find_impl()
599 	return (zfs_btree_find(&rt->rt_root, &rsearch, NULL));  in range_tree_find_impl()
603 range_tree_find(range_tree_t *rt, uint64_t start, uint64_t size)  in range_tree_find()  argument
605 	if (rt->rt_type == RANGE_SEG64)  in range_tree_find()
608 	range_seg_t *rs = range_tree_find_impl(rt, start, size);  in range_tree_find()
609 	if (rs != NULL && rs_get_start(rs, rt) <= start &&  in range_tree_find()
610 	    rs_get_end(rs, rt) >= start + size) {  in range_tree_find()
617 range_tree_verify_not_present(range_tree_t *rt, uint64_t off, uint64_t size)  in range_tree_verify_not_present()  argument
619 	range_seg_t *rs = range_tree_find(rt, off, size);  in range_tree_verify_not_present()
625 range_tree_contains(range_tree_t *rt, uint64_t start, uint64_t size)  in range_tree_contains()  argument
627 	return (range_tree_find(rt, start, size) != NULL);  in range_tree_contains()
636 range_tree_find_in(range_tree_t *rt, uint64_t start, uint64_t size,  in range_tree_find_in()  argument
639 	if (rt->rt_type == RANGE_SEG64)  in range_tree_find_in()
643 	rs_set_start(&rsearch, rt, start);  in range_tree_find_in()
644 	rs_set_end_raw(&rsearch, rt, rs_get_start_raw(&rsearch, rt) + 1);  in range_tree_find_in()
647 	range_seg_t *rs = zfs_btree_find(&rt->rt_root, &rsearch, &where);  in range_tree_find_in()
650 		*osize = MIN(size, rs_get_end(rs, rt) - start);  in range_tree_find_in()
654 	rs = zfs_btree_next(&rt->rt_root, &where, &where);  in range_tree_find_in()
655 	if (rs == NULL || rs_get_start(rs, rt) > start + size)  in range_tree_find_in()
658 	*ostart = rs_get_start(rs, rt);  in range_tree_find_in()
659 	*osize = MIN(start + size, rs_get_end(rs, rt)) -  in range_tree_find_in()
660 	    rs_get_start(rs, rt);  in range_tree_find_in()
669 range_tree_clear(range_tree_t *rt, uint64_t start, uint64_t size)  in range_tree_clear()  argument
676 	if (rt->rt_type == RANGE_SEG64)  in range_tree_clear()
679 	while ((rs = range_tree_find_impl(rt, start, size)) != NULL) {  in range_tree_clear()
680 		uint64_t free_start = MAX(rs_get_start(rs, rt), start);  in range_tree_clear()
681 		uint64_t free_end = MIN(rs_get_end(rs, rt), start + size);  in range_tree_clear()
682 		range_tree_remove(rt, free_start, free_end - free_start);  in range_tree_clear()
689 	range_tree_t *rt;  in range_tree_swap()  local
694 	rt = *rtsrc;  in range_tree_swap()
696 	*rtdst = rt;  in range_tree_swap()
700 range_tree_vacate(range_tree_t *rt, range_tree_func_t *func, void *arg)  in range_tree_vacate()  argument
702 	if (rt->rt_ops != NULL && rt->rt_ops->rtop_vacate != NULL)  in range_tree_vacate()
703 		rt->rt_ops->rtop_vacate(rt, rt->rt_arg);  in range_tree_vacate()
709 		while ((rs = zfs_btree_destroy_nodes(&rt->rt_root, &cookie)) !=  in range_tree_vacate()
711 			func(arg, rs_get_start(rs, rt), rs_get_end(rs, rt) -  in range_tree_vacate()
712 			    rs_get_start(rs, rt));  in range_tree_vacate()
715 		zfs_btree_clear(&rt->rt_root);  in range_tree_vacate()
718 	memset(rt->rt_histogram, 0, sizeof (rt->rt_histogram));  in range_tree_vacate()
719 	rt->rt_space = 0;  in range_tree_vacate()
723 range_tree_walk(range_tree_t *rt, range_tree_func_t *func, void *arg)  in range_tree_walk()  argument
726 	for (range_seg_t *rs = zfs_btree_first(&rt->rt_root, &where);  in range_tree_walk()
727 	    rs != NULL; rs = zfs_btree_next(&rt->rt_root, &where, &where)) {  in range_tree_walk()
728 		func(arg, rs_get_start(rs, rt), rs_get_end(rs, rt) -  in range_tree_walk()
729 		    rs_get_start(rs, rt));  in range_tree_walk()
734 range_tree_first(range_tree_t *rt)  in range_tree_first()  argument
736 	return (zfs_btree_first(&rt->rt_root, NULL));  in range_tree_first()
740 range_tree_space(range_tree_t *rt)  in range_tree_space()  argument
742 	return (rt->rt_space);  in range_tree_space()
746 range_tree_numsegs(range_tree_t *rt)  in range_tree_numsegs()  argument
748 	return ((rt == NULL) ? 0 : zfs_btree_numnodes(&rt->rt_root));  in range_tree_numsegs()
752 range_tree_is_empty(range_tree_t *rt)  in range_tree_is_empty()  argument
754 	ASSERT(rt != NULL);  in range_tree_is_empty()
755 	return (range_tree_space(rt) == 0);  in range_tree_is_empty()
838 range_tree_remove_xor_add(range_tree_t *rt, range_tree_t *removefrom,  in range_tree_remove_xor_add()  argument
842 	for (range_seg_t *rs = zfs_btree_first(&rt->rt_root, &where); rs;  in range_tree_remove_xor_add()
843 	    rs = zfs_btree_next(&rt->rt_root, &where, &where)) {  in range_tree_remove_xor_add()
844 		range_tree_remove_xor_add_segment(rs_get_start(rs, rt),  in range_tree_remove_xor_add()
845 		    rs_get_end(rs, rt), removefrom, addto);  in range_tree_remove_xor_add()
850 range_tree_min(range_tree_t *rt)  in range_tree_min()  argument
852 	range_seg_t *rs = zfs_btree_first(&rt->rt_root, NULL);  in range_tree_min()
853 	return (rs != NULL ? rs_get_start(rs, rt) : 0);  in range_tree_min()
857 range_tree_max(range_tree_t *rt)  in range_tree_max()  argument
859 	range_seg_t *rs = zfs_btree_last(&rt->rt_root, NULL);  in range_tree_max()
860 	return (rs != NULL ? rs_get_end(rs, rt) : 0);  in range_tree_max()
864 range_tree_span(range_tree_t *rt)  in range_tree_span()  argument
866 	return (range_tree_max(rt) - range_tree_min(rt));  in range_tree_span()