Lines Matching refs:rt
78 rs_copy(range_seg_t *src, range_seg_t *dest, range_tree_t *rt) in rs_copy() argument
80 ASSERT3U(rt->rt_type, <=, RANGE_SEG_NUM_TYPES); in rs_copy()
82 switch (rt->rt_type) { in rs_copy()
99 range_tree_stat_verify(range_tree_t *rt) in range_tree_stat_verify() argument
106 for (rs = zfs_btree_first(&rt->rt_root, &where); rs != NULL; in range_tree_stat_verify()
107 rs = zfs_btree_next(&rt->rt_root, &where, &where)) { in range_tree_stat_verify()
108 uint64_t size = rs_get_end(rs, rt) - rs_get_start(rs, rt); in range_tree_stat_verify()
116 if (hist[i] != rt->rt_histogram[i]) { in range_tree_stat_verify()
118 i, hist, hist[i], rt->rt_histogram[i]); in range_tree_stat_verify()
120 VERIFY3U(hist[i], ==, rt->rt_histogram[i]); in range_tree_stat_verify()
125 range_tree_stat_incr(range_tree_t *rt, range_seg_t *rs) in range_tree_stat_incr() argument
127 uint64_t size = rs_get_end(rs, rt) - rs_get_start(rs, rt); in range_tree_stat_incr()
132 sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram)); in range_tree_stat_incr()
134 rt->rt_histogram[idx]++; in range_tree_stat_incr()
135 ASSERT3U(rt->rt_histogram[idx], !=, 0); in range_tree_stat_incr()
139 range_tree_stat_decr(range_tree_t *rt, range_seg_t *rs) in range_tree_stat_decr() argument
141 uint64_t size = rs_get_end(rs, rt) - rs_get_start(rs, rt); in range_tree_stat_decr()
146 sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram)); in range_tree_stat_decr()
148 ASSERT3U(rt->rt_histogram[idx], !=, 0); in range_tree_stat_decr()
149 rt->rt_histogram[idx]--; in range_tree_stat_decr()
194 range_tree_t *rt = kmem_zalloc(sizeof (range_tree_t), KM_SLEEP); in range_tree_create_impl() local
216 zfs_btree_create(&rt->rt_root, compare, size); in range_tree_create_impl()
218 rt->rt_ops = ops; in range_tree_create_impl()
219 rt->rt_arg = arg; in range_tree_create_impl()
220 rt->rt_gap = gap; in range_tree_create_impl()
221 rt->rt_type = type; in range_tree_create_impl()
222 rt->rt_start = start; in range_tree_create_impl()
223 rt->rt_shift = shift; in range_tree_create_impl()
224 rt->rt_btree_compare = zfs_btree_compare; in range_tree_create_impl()
226 if (rt->rt_ops != NULL && rt->rt_ops->rtop_create != NULL) in range_tree_create_impl()
227 rt->rt_ops->rtop_create(rt, rt->rt_arg); in range_tree_create_impl()
229 return (rt); in range_tree_create_impl()
240 range_tree_destroy(range_tree_t *rt) in range_tree_destroy() argument
242 VERIFY0(rt->rt_space); in range_tree_destroy()
244 if (rt->rt_ops != NULL && rt->rt_ops->rtop_destroy != NULL) in range_tree_destroy()
245 rt->rt_ops->rtop_destroy(rt, rt->rt_arg); in range_tree_destroy()
247 zfs_btree_destroy(&rt->rt_root); in range_tree_destroy()
248 kmem_free(rt, sizeof (*rt)); in range_tree_destroy()
252 range_tree_adjust_fill(range_tree_t *rt, range_seg_t *rs, int64_t delta) in range_tree_adjust_fill() argument
254 ASSERT3U(rs_get_fill(rs, rt) + delta, !=, 0); in range_tree_adjust_fill()
255 ASSERT3U(rs_get_fill(rs, rt) + delta, <=, rs_get_end(rs, rt) - in range_tree_adjust_fill()
256 rs_get_start(rs, rt)); in range_tree_adjust_fill()
258 if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL) in range_tree_adjust_fill()
259 rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg); in range_tree_adjust_fill()
260 rs_set_fill(rs, rt, rs_get_fill(rs, rt) + delta); in range_tree_adjust_fill()
261 if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL) in range_tree_adjust_fill()
262 rt->rt_ops->rtop_add(rt, rs, rt->rt_arg); in range_tree_adjust_fill()
268 range_tree_t *rt = arg; in range_tree_add_impl() local
272 uint64_t end = start + size, gap = rt->rt_gap; in range_tree_add_impl()
280 rs_set_start(&rsearch, rt, start); in range_tree_add_impl()
281 rs_set_end(&rsearch, rt, end); in range_tree_add_impl()
282 rs = zfs_btree_find(&rt->rt_root, &rsearch, &where); in range_tree_add_impl()
293 ASSERT3U(rt->rt_gap, !=, 0); in range_tree_add_impl()
294 uint64_t rstart = rs_get_start(rs, rt); in range_tree_add_impl()
295 uint64_t rend = rs_get_end(rs, rt); in range_tree_add_impl()
298 range_tree_adjust_fill(rt, rs, fill); in range_tree_add_impl()
302 zfs_btree_remove(&rt->rt_root, rs); in range_tree_add_impl()
303 if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL) in range_tree_add_impl()
304 rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg); in range_tree_add_impl()
306 range_tree_stat_decr(rt, rs); in range_tree_add_impl()
307 rt->rt_space -= rend - rstart; in range_tree_add_impl()
309 fill += rs_get_fill(rs, rt); in range_tree_add_impl()
314 range_tree_add_impl(rt, start, size, fill); in range_tree_add_impl()
326 rs_before = zfs_btree_prev(&rt->rt_root, &where, &where_before); in range_tree_add_impl()
327 rs_after = zfs_btree_next(&rt->rt_root, &where, &where_after); in range_tree_add_impl()
329 merge_before = (rs_before != NULL && rs_get_end(rs_before, rt) >= in range_tree_add_impl()
331 merge_after = (rs_after != NULL && rs_get_start(rs_after, rt) <= end + in range_tree_add_impl()
335 bridge_size += start - rs_get_end(rs_before, rt); in range_tree_add_impl()
337 bridge_size += rs_get_start(rs_after, rt) - end; in range_tree_add_impl()
340 if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL) { in range_tree_add_impl()
341 rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg); in range_tree_add_impl()
342 rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg); in range_tree_add_impl()
345 range_tree_stat_decr(rt, rs_before); in range_tree_add_impl()
346 range_tree_stat_decr(rt, rs_after); in range_tree_add_impl()
348 rs_copy(rs_after, &tmp, rt); in range_tree_add_impl()
349 uint64_t before_start = rs_get_start_raw(rs_before, rt); in range_tree_add_impl()
350 uint64_t before_fill = rs_get_fill(rs_before, rt); in range_tree_add_impl()
351 uint64_t after_fill = rs_get_fill(rs_after, rt); in range_tree_add_impl()
352 zfs_btree_remove_idx(&rt->rt_root, &where_before); in range_tree_add_impl()
358 rs_after = zfs_btree_find(&rt->rt_root, &tmp, &where_after); in range_tree_add_impl()
359 rs_set_start_raw(rs_after, rt, before_start); in range_tree_add_impl()
360 rs_set_fill(rs_after, rt, after_fill + before_fill + fill); in range_tree_add_impl()
363 if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL) in range_tree_add_impl()
364 rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg); in range_tree_add_impl()
366 range_tree_stat_decr(rt, rs_before); in range_tree_add_impl()
368 uint64_t before_fill = rs_get_fill(rs_before, rt); in range_tree_add_impl()
369 rs_set_end(rs_before, rt, end); in range_tree_add_impl()
370 rs_set_fill(rs_before, rt, before_fill + fill); in range_tree_add_impl()
373 if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL) in range_tree_add_impl()
374 rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg); in range_tree_add_impl()
376 range_tree_stat_decr(rt, rs_after); in range_tree_add_impl()
378 uint64_t after_fill = rs_get_fill(rs_after, rt); in range_tree_add_impl()
379 rs_set_start(rs_after, rt, start); in range_tree_add_impl()
380 rs_set_fill(rs_after, rt, after_fill + fill); in range_tree_add_impl()
385 rs_set_start(rs, rt, start); in range_tree_add_impl()
386 rs_set_end(rs, rt, end); in range_tree_add_impl()
387 rs_set_fill(rs, rt, fill); in range_tree_add_impl()
388 zfs_btree_add_idx(&rt->rt_root, rs, &where); in range_tree_add_impl()
392 ASSERT3U(rs_get_fill(rs, rt), <=, rs_get_end(rs, rt) - in range_tree_add_impl()
393 rs_get_start(rs, rt)); in range_tree_add_impl()
395 ASSERT3U(rs_get_fill(rs, rt), ==, rs_get_end(rs, rt) - in range_tree_add_impl()
396 rs_get_start(rs, rt)); in range_tree_add_impl()
399 if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL) in range_tree_add_impl()
400 rt->rt_ops->rtop_add(rt, rs, rt->rt_arg); in range_tree_add_impl()
402 range_tree_stat_incr(rt, rs); in range_tree_add_impl()
403 rt->rt_space += size + bridge_size; in range_tree_add_impl()
413 range_tree_remove_impl(range_tree_t *rt, uint64_t start, uint64_t size, in range_tree_remove_impl() argument
423 VERIFY3U(size, <=, rt->rt_space); in range_tree_remove_impl()
424 if (rt->rt_type == RANGE_SEG64) in range_tree_remove_impl()
427 rs_set_start(&rsearch, rt, start); in range_tree_remove_impl()
428 rs_set_end(&rsearch, rt, end); in range_tree_remove_impl()
429 rs = zfs_btree_find(&rt->rt_root, &rsearch, &where); in range_tree_remove_impl()
445 if (rt->rt_gap != 0) { in range_tree_remove_impl()
447 if (rs_get_fill(rs, rt) == size) { in range_tree_remove_impl()
448 start = rs_get_start(rs, rt); in range_tree_remove_impl()
449 end = rs_get_end(rs, rt); in range_tree_remove_impl()
452 range_tree_adjust_fill(rt, rs, -size); in range_tree_remove_impl()
455 } else if (rs_get_start(rs, rt) != start || in range_tree_remove_impl()
456 rs_get_end(rs, rt) != end) { in range_tree_remove_impl()
461 (longlong_t)rs_get_start(rs, rt), in range_tree_remove_impl()
462 (longlong_t)rs_get_end(rs, rt) - rs_get_start(rs, in range_tree_remove_impl()
463 rt)); in range_tree_remove_impl()
468 VERIFY3U(rs_get_start(rs, rt), <=, start); in range_tree_remove_impl()
469 VERIFY3U(rs_get_end(rs, rt), >=, end); in range_tree_remove_impl()
471 left_over = (rs_get_start(rs, rt) != start); in range_tree_remove_impl()
472 right_over = (rs_get_end(rs, rt) != end); in range_tree_remove_impl()
474 range_tree_stat_decr(rt, rs); in range_tree_remove_impl()
476 if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL) in range_tree_remove_impl()
477 rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg); in range_tree_remove_impl()
481 rs_set_start(&newseg, rt, end); in range_tree_remove_impl()
482 rs_set_end_raw(&newseg, rt, rs_get_end_raw(rs, rt)); in range_tree_remove_impl()
483 rs_set_fill(&newseg, rt, rs_get_end(rs, rt) - end); in range_tree_remove_impl()
484 range_tree_stat_incr(rt, &newseg); in range_tree_remove_impl()
487 rs_set_end(rs, rt, start); in range_tree_remove_impl()
489 rs_copy(rs, &rs_tmp, rt); in range_tree_remove_impl()
490 if (zfs_btree_next(&rt->rt_root, &where, &where) != NULL) in range_tree_remove_impl()
491 zfs_btree_add_idx(&rt->rt_root, &newseg, &where); in range_tree_remove_impl()
493 zfs_btree_add(&rt->rt_root, &newseg); in range_tree_remove_impl()
495 if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL) in range_tree_remove_impl()
496 rt->rt_ops->rtop_add(rt, &newseg, rt->rt_arg); in range_tree_remove_impl()
499 rs_set_end(rs, rt, start); in range_tree_remove_impl()
500 rs_copy(rs, &rs_tmp, rt); in range_tree_remove_impl()
503 rs_set_start(rs, rt, end); in range_tree_remove_impl()
504 rs_copy(rs, &rs_tmp, rt); in range_tree_remove_impl()
506 zfs_btree_remove_idx(&rt->rt_root, &where); in range_tree_remove_impl()
516 rs_set_fill_raw(rs, rt, rs_get_end_raw(rs, rt) - in range_tree_remove_impl()
517 rs_get_start_raw(rs, rt)); in range_tree_remove_impl()
518 range_tree_stat_incr(rt, &rs_tmp); in range_tree_remove_impl()
520 if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL) in range_tree_remove_impl()
521 rt->rt_ops->rtop_add(rt, &rs_tmp, rt->rt_arg); in range_tree_remove_impl()
524 rt->rt_space -= size; in range_tree_remove_impl()
534 range_tree_remove_fill(range_tree_t *rt, uint64_t start, uint64_t size) in range_tree_remove_fill() argument
536 range_tree_remove_impl(rt, start, size, B_TRUE); in range_tree_remove_fill()
540 range_tree_resize_segment(range_tree_t *rt, range_seg_t *rs, in range_tree_resize_segment() argument
543 int64_t delta = newsize - (rs_get_end(rs, rt) - rs_get_start(rs, rt)); in range_tree_resize_segment()
545 range_tree_stat_decr(rt, rs); in range_tree_resize_segment()
546 if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL) in range_tree_resize_segment()
547 rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg); in range_tree_resize_segment()
549 rs_set_start(rs, rt, newstart); in range_tree_resize_segment()
550 rs_set_end(rs, rt, newstart + newsize); in range_tree_resize_segment()
552 range_tree_stat_incr(rt, rs); in range_tree_resize_segment()
553 if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL) in range_tree_resize_segment()
554 rt->rt_ops->rtop_add(rt, rs, rt->rt_arg); in range_tree_resize_segment()
556 rt->rt_space += delta; in range_tree_resize_segment()
560 range_tree_find_impl(range_tree_t *rt, uint64_t start, uint64_t size) in range_tree_find_impl() argument
567 rs_set_start(&rsearch, rt, start); in range_tree_find_impl()
568 rs_set_end(&rsearch, rt, end); in range_tree_find_impl()
569 return (zfs_btree_find(&rt->rt_root, &rsearch, NULL)); in range_tree_find_impl()
573 range_tree_find(range_tree_t *rt, uint64_t start, uint64_t size) in range_tree_find() argument
575 if (rt->rt_type == RANGE_SEG64) in range_tree_find()
578 range_seg_t *rs = range_tree_find_impl(rt, start, size); in range_tree_find()
579 if (rs != NULL && rs_get_start(rs, rt) <= start && in range_tree_find()
580 rs_get_end(rs, rt) >= start + size) { in range_tree_find()
587 range_tree_verify_not_present(range_tree_t *rt, uint64_t off, uint64_t size) in range_tree_verify_not_present() argument
589 range_seg_t *rs = range_tree_find(rt, off, size); in range_tree_verify_not_present()
595 range_tree_contains(range_tree_t *rt, uint64_t start, uint64_t size) in range_tree_contains() argument
597 return (range_tree_find(rt, start, size) != NULL); in range_tree_contains()
606 range_tree_find_in(range_tree_t *rt, uint64_t start, uint64_t size, in range_tree_find_in() argument
609 if (rt->rt_type == RANGE_SEG64) in range_tree_find_in()
613 rs_set_start(&rsearch, rt, start); in range_tree_find_in()
614 rs_set_end_raw(&rsearch, rt, rs_get_start_raw(&rsearch, rt) + 1); in range_tree_find_in()
617 range_seg_t *rs = zfs_btree_find(&rt->rt_root, &rsearch, &where); in range_tree_find_in()
620 *osize = MIN(size, rs_get_end(rs, rt) - start); in range_tree_find_in()
624 rs = zfs_btree_next(&rt->rt_root, &where, &where); in range_tree_find_in()
625 if (rs == NULL || rs_get_start(rs, rt) > start + size) in range_tree_find_in()
628 *ostart = rs_get_start(rs, rt); in range_tree_find_in()
629 *osize = MIN(start + size, rs_get_end(rs, rt)) - in range_tree_find_in()
630 rs_get_start(rs, rt); in range_tree_find_in()
639 range_tree_clear(range_tree_t *rt, uint64_t start, uint64_t size) in range_tree_clear() argument
646 if (rt->rt_type == RANGE_SEG64) in range_tree_clear()
649 while ((rs = range_tree_find_impl(rt, start, size)) != NULL) { in range_tree_clear()
650 uint64_t free_start = MAX(rs_get_start(rs, rt), start); in range_tree_clear()
651 uint64_t free_end = MIN(rs_get_end(rs, rt), start + size); in range_tree_clear()
652 range_tree_remove(rt, free_start, free_end - free_start); in range_tree_clear()
659 range_tree_t *rt; in range_tree_swap() local
664 rt = *rtsrc; in range_tree_swap()
666 *rtdst = rt; in range_tree_swap()
670 range_tree_vacate(range_tree_t *rt, range_tree_func_t *func, void *arg) in range_tree_vacate() argument
673 if (rt->rt_ops != NULL && rt->rt_ops->rtop_vacate != NULL) in range_tree_vacate()
674 rt->rt_ops->rtop_vacate(rt, rt->rt_arg); in range_tree_vacate()
680 while ((rs = zfs_btree_destroy_nodes(&rt->rt_root, &cookie)) != in range_tree_vacate()
682 func(arg, rs_get_start(rs, rt), rs_get_end(rs, rt) - in range_tree_vacate()
683 rs_get_start(rs, rt)); in range_tree_vacate()
686 zfs_btree_clear(&rt->rt_root); in range_tree_vacate()
689 bzero(rt->rt_histogram, sizeof (rt->rt_histogram)); in range_tree_vacate()
690 rt->rt_space = 0; in range_tree_vacate()
694 range_tree_walk(range_tree_t *rt, range_tree_func_t *func, void *arg) in range_tree_walk() argument
697 for (range_seg_t *rs = zfs_btree_first(&rt->rt_root, &where); in range_tree_walk()
698 rs != NULL; rs = zfs_btree_next(&rt->rt_root, &where, &where)) { in range_tree_walk()
699 func(arg, rs_get_start(rs, rt), rs_get_end(rs, rt) - in range_tree_walk()
700 rs_get_start(rs, rt)); in range_tree_walk()
705 range_tree_first(range_tree_t *rt) in range_tree_first() argument
707 return (zfs_btree_first(&rt->rt_root, NULL)); in range_tree_first()
711 range_tree_space(range_tree_t *rt) in range_tree_space() argument
713 return (rt->rt_space); in range_tree_space()
717 range_tree_numsegs(range_tree_t *rt) in range_tree_numsegs() argument
719 return ((rt == NULL) ? 0 : zfs_btree_numnodes(&rt->rt_root)); in range_tree_numsegs()
723 range_tree_is_empty(range_tree_t *rt) in range_tree_is_empty() argument
725 ASSERT(rt != NULL); in range_tree_is_empty()
726 return (range_tree_space(rt) == 0); in range_tree_is_empty()
731 rt_btree_create(range_tree_t *rt, void *arg) in rt_btree_create() argument
736 switch (rt->rt_type) { in rt_btree_create()
747 panic("Invalid range seg type %d", rt->rt_type); in rt_btree_create()
749 zfs_btree_create(size_tree, rt->rt_btree_compare, size); in rt_btree_create()
754 rt_btree_destroy(range_tree_t *rt, void *arg) in rt_btree_destroy() argument
764 rt_btree_add(range_tree_t *rt, range_seg_t *rs, void *arg) in rt_btree_add() argument
773 rt_btree_remove(range_tree_t *rt, range_seg_t *rs, void *arg) in rt_btree_remove() argument
782 rt_btree_vacate(range_tree_t *rt, void *arg) in rt_btree_vacate() argument
788 rt_btree_create(rt, arg); in rt_btree_vacate()
879 range_tree_remove_xor_add(range_tree_t *rt, range_tree_t *removefrom, in range_tree_remove_xor_add() argument
883 for (range_seg_t *rs = zfs_btree_first(&rt->rt_root, &where); rs; in range_tree_remove_xor_add()
884 rs = zfs_btree_next(&rt->rt_root, &where, &where)) { in range_tree_remove_xor_add()
885 range_tree_remove_xor_add_segment(rs_get_start(rs, rt), in range_tree_remove_xor_add()
886 rs_get_end(rs, rt), removefrom, addto); in range_tree_remove_xor_add()
891 range_tree_min(range_tree_t *rt) in range_tree_min() argument
893 range_seg_t *rs = zfs_btree_first(&rt->rt_root, NULL); in range_tree_min()
894 return (rs != NULL ? rs_get_start(rs, rt) : 0); in range_tree_min()
898 range_tree_max(range_tree_t *rt) in range_tree_max() argument
900 range_seg_t *rs = zfs_btree_last(&rt->rt_root, NULL); in range_tree_max()
901 return (rs != NULL ? rs_get_end(rs, rt) : 0); in range_tree_max()
905 range_tree_span(range_tree_t *rt) in range_tree_span() argument
907 return (range_tree_max(rt) - range_tree_min(rt)); in range_tree_span()