module/zfs/range_tree.c

   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 https://opensource.org/licenses/CDDL-1.0.
  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, 2019 by Delphix. All rights reserved.
  27  * Copyright (c) 2015, Nexenta Systems, Inc. All rights reserved.
  28  */
  29
  30 #include <sys/zfs_context.h>
  31 #include <sys/spa.h>
  32 #include <sys/dmu.h>
  33 #include <sys/dnode.h>
  34 #include <sys/zio.h>
  35 #include <sys/range_tree.h>
  36
  37 /*
  38  * Range trees are tree-based data structures that can be used to
  39  * track free space or generally any space allocation information.
  40  * A range tree keeps track of individual segments and automatically
  41  * provides facilities such as adjacent extent merging and extent
  42  * splitting in response to range add/remove requests.
  43  *
  44  * A range tree starts out completely empty, with no segments in it.
  45  * Adding an allocation via range_tree_add to the range tree can either:
  46  * 1) create a new extent
  47  * 2) extend an adjacent extent
  48  * 3) merge two adjacent extents
  49  * Conversely, removing an allocation via range_tree_remove can:
  50  * 1) completely remove an extent
  51  * 2) shorten an extent (if the allocation was near one of its ends)
  52  * 3) split an extent into two extents, in effect punching a hole
  53  *
  54  * A range tree is also capable of 'bridging' gaps when adding
  55  * allocations. This is useful for cases when close proximity of
  56  * allocations is an important detail that needs to be represented
  57  * in the range tree. See range_tree_set_gap(). The default behavior
  58  * is not to bridge gaps (i.e. the maximum allowed gap size is 0).
  59  *
  60  * In order to traverse a range tree, use either the range_tree_walk()
  61  * or range_tree_vacate() functions.
  62  *
  63  * To obtain more accurate information on individual segment
  64  * operations that the range tree performs "under the hood", you can
  65  * specify a set of callbacks by passing a range_tree_ops_t structure
  66  * to the range_tree_create function. Any callbacks that are non-NULL
  67  * are then called at the appropriate times.
  68  *
  69  * The range tree code also supports a special variant of range trees
  70  * that can bridge small gaps between segments. This kind of tree is used
  71  * by the dsl scanning code to group I/Os into mostly sequential chunks to
  72  * optimize disk performance. The code here attempts to do this with as
  73  * little memory and computational overhead as possible. One limitation of
  74  * this implementation is that segments of range trees with gaps can only
  75  * support removing complete segments.
  76  */
  77
  78 static inline void
  79 rs_copy(range_seg_t *src, range_seg_t *dest, range_tree_t *rt)
  80 {
  81         ASSERT3U(rt->rt_type, <, RANGE_SEG_NUM_TYPES);
  82         size_t size = 0;
  83         switch (rt->rt_type) {
  84         case RANGE_SEG32:
  85                 size = sizeof (range_seg32_t);
  86                 break;
  87         case RANGE_SEG64:
  88                 size = sizeof (range_seg64_t);
  89                 break;
  90         case RANGE_SEG_GAP:
  91                 size = sizeof (range_seg_gap_t);
  92                 break;
  93         default:
  94                 __builtin_unreachable();
  95         }
  96         memcpy(dest, src, size);
  97 }
  98
  99 void
 100 range_tree_stat_verify(range_tree_t *rt)
 101 {
 102         range_seg_t *rs;
 103         zfs_btree_index_t where;
 104         uint64_t hist[RANGE_TREE_HISTOGRAM_SIZE] = { 0 };
 105         int i;
 106
 107         for (rs = zfs_btree_first(&rt->rt_root, &where); rs != NULL;
 108             rs = zfs_btree_next(&rt->rt_root, &where, &where)) {
 109                 uint64_t size = rs_get_end(rs, rt) - rs_get_start(rs, rt);
 110                 int idx = highbit64(size) - 1;
 111
 112                 hist[idx]++;
 113                 ASSERT3U(hist[idx], !=, 0);
 114         }
 115
 116         for (i = 0; i < RANGE_TREE_HISTOGRAM_SIZE; i++) {
 117                 if (hist[i] != rt->rt_histogram[i]) {
 118                         zfs_dbgmsg("i=%d, hist=%px, hist=%llu, rt_hist=%llu",
 119                             i, hist, (u_longlong_t)hist[i],
 120                             (u_longlong_t)rt->rt_histogram[i]);
 121                 }
 122                 VERIFY3U(hist[i], ==, rt->rt_histogram[i]);
 123         }
 124 }
 125
 126 static void
 127 range_tree_stat_incr(range_tree_t *rt, range_seg_t *rs)
 128 {
 129         uint64_t size = rs_get_end(rs, rt) - rs_get_start(rs, rt);
 130         int idx = highbit64(size) - 1;
 131
 132         ASSERT(size != 0);
 133         ASSERT3U(idx, <,
 134             sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram));
 135
 136         rt->rt_histogram[idx]++;
 137         ASSERT3U(rt->rt_histogram[idx], !=, 0);
 138 }
 139
 140 static void
 141 range_tree_stat_decr(range_tree_t *rt, range_seg_t *rs)
 142 {
 143         uint64_t size = rs_get_end(rs, rt) - rs_get_start(rs, rt);
 144         int idx = highbit64(size) - 1;
 145
 146         ASSERT(size != 0);
 147         ASSERT3U(idx, <,
 148             sizeof (rt->rt_histogram) / sizeof (*rt->rt_histogram));
 149
 150         ASSERT3U(rt->rt_histogram[idx], !=, 0);
 151         rt->rt_histogram[idx]--;
 152 }
 153
 154 static int
 155 range_tree_seg32_compare(const void *x1, const void *x2)
 156 {
 157         const range_seg32_t *r1 = x1;
 158         const range_seg32_t *r2 = x2;
 159
 160         ASSERT3U(r1->rs_start, <=, r1->rs_end);
 161         ASSERT3U(r2->rs_start, <=, r2->rs_end);
 162
 163         return ((r1->rs_start >= r2->rs_end) - (r1->rs_end <= r2->rs_start));
 164 }
 165
 166 static int
 167 range_tree_seg64_compare(const void *x1, const void *x2)
 168 {
 169         const range_seg64_t *r1 = x1;
 170         const range_seg64_t *r2 = x2;
 171
 172         ASSERT3U(r1->rs_start, <=, r1->rs_end);
 173         ASSERT3U(r2->rs_start, <=, r2->rs_end);
 174
 175         return ((r1->rs_start >= r2->rs_end) - (r1->rs_end <= r2->rs_start));
 176 }
 177
 178 static int
 179 range_tree_seg_gap_compare(const void *x1, const void *x2)
 180 {
 181         const range_seg_gap_t *r1 = x1;
 182         const range_seg_gap_t *r2 = x2;
 183
 184         ASSERT3U(r1->rs_start, <=, r1->rs_end);
 185         ASSERT3U(r2->rs_start, <=, r2->rs_end);
 186
 187         return ((r1->rs_start >= r2->rs_end) - (r1->rs_end <= r2->rs_start));
 188 }
 189
 190 range_tree_t *
 191 range_tree_create_gap(const range_tree_ops_t *ops, range_seg_type_t type,
 192     void *arg, uint64_t start, uint64_t shift, uint64_t gap)
 193 {
 194         range_tree_t *rt = kmem_zalloc(sizeof (range_tree_t), KM_SLEEP);
 195
 196         ASSERT3U(shift, <, 64);
 197         ASSERT3U(type, <=, RANGE_SEG_NUM_TYPES);
 198         size_t size;
 199         int (*compare) (const void *, const void *);
 200         switch (type) {
 201         case RANGE_SEG32:
 202                 size = sizeof (range_seg32_t);
 203                 compare = range_tree_seg32_compare;
 204                 break;
 205         case RANGE_SEG64:
 206                 size = sizeof (range_seg64_t);
 207                 compare = range_tree_seg64_compare;
 208                 break;
 209         case RANGE_SEG_GAP:
 210                 size = sizeof (range_seg_gap_t);
 211                 compare = range_tree_seg_gap_compare;
 212                 break;
 213         default:
 214                 panic("Invalid range seg type %d", type);
 215         }
 216         zfs_btree_create(&rt->rt_root, compare, size);
 217
 218         rt->rt_ops = ops;
 219         rt->rt_gap = gap;
 220         rt->rt_arg = arg;
 221         rt->rt_type = type;
 222         rt->rt_start = start;
 223         rt->rt_shift = shift;
 224
 225         if (rt->rt_ops != NULL && rt->rt_ops->rtop_create != NULL)
 226                 rt->rt_ops->rtop_create(rt, rt->rt_arg);
 227
 228         return (rt);
 229 }
 230
 231 range_tree_t *
 232 range_tree_create(const range_tree_ops_t *ops, range_seg_type_t type,
 233     void *arg, uint64_t start, uint64_t shift)
 234 {
 235         return (range_tree_create_gap(ops, type, arg, start, shift, 0));
 236 }
 237
 238 void
 239 range_tree_destroy(range_tree_t *rt)
 240 {
 241         VERIFY0(rt->rt_space);
 242
 243         if (rt->rt_ops != NULL && rt->rt_ops->rtop_destroy != NULL)
 244                 rt->rt_ops->rtop_destroy(rt, rt->rt_arg);
 245
 246         zfs_btree_destroy(&rt->rt_root);
 247         kmem_free(rt, sizeof (*rt));
 248 }
 249
 250 void
 251 range_tree_adjust_fill(range_tree_t *rt, range_seg_t *rs, int64_t delta)
 252 {
 253         if (delta < 0 && delta * -1 >= rs_get_fill(rs, rt)) {
 254                 zfs_panic_recover("zfs: attempting to decrease fill to or "
 255                     "below 0; probable double remove in segment [%llx:%llx]",
 256                     (longlong_t)rs_get_start(rs, rt),
 257                     (longlong_t)rs_get_end(rs, rt));
 258         }
 259         if (rs_get_fill(rs, rt) + delta > rs_get_end(rs, rt) -
 260             rs_get_start(rs, rt)) {
 261                 zfs_panic_recover("zfs: attempting to increase fill beyond "
 262                     "max; probable double add in segment [%llx:%llx]",
 263                     (longlong_t)rs_get_start(rs, rt),
 264                     (longlong_t)rs_get_end(rs, rt));
 265         }
 266
 267         if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
 268                 rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);
 269         rs_set_fill(rs, rt, rs_get_fill(rs, rt) + delta);
 270         if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)
 271                 rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);
 272 }
 273
 274 static void
 275 range_tree_add_impl(void *arg, uint64_t start, uint64_t size, uint64_t fill)
 276 {
 277         range_tree_t *rt = arg;
 278         zfs_btree_index_t where;
 279         range_seg_t *rs_before, *rs_after, *rs;
 280         range_seg_max_t tmp, rsearch;
 281         uint64_t end = start + size, gap = rt->rt_gap;
 282         uint64_t bridge_size = 0;
 283         boolean_t merge_before, merge_after;
 284
 285         ASSERT3U(size, !=, 0);
 286         ASSERT3U(fill, <=, size);
 287         ASSERT3U(start + size, >, start);
 288
 289         rs_set_start(&rsearch, rt, start);
 290         rs_set_end(&rsearch, rt, end);
 291         rs = zfs_btree_find(&rt->rt_root, &rsearch, &where);
 292
 293         /*
 294          * If this is a gap-supporting range tree, it is possible that we
 295          * are inserting into an existing segment. In this case simply
 296          * bump the fill count and call the remove / add callbacks. If the
 297          * new range will extend an existing segment, we remove the
 298          * existing one, apply the new extent to it and re-insert it using
 299          * the normal code paths.
 300          */
 301         if (rs != NULL) {
 302                 if (gap == 0) {
 303                         zfs_panic_recover("zfs: adding existent segment to "
 304                             "range tree (offset=%llx size=%llx)",
 305                             (longlong_t)start, (longlong_t)size);
 306                         return;
 307                 }
 308                 uint64_t rstart = rs_get_start(rs, rt);
 309                 uint64_t rend = rs_get_end(rs, rt);
 310                 if (rstart <= start && rend >= end) {
 311                         range_tree_adjust_fill(rt, rs, fill);
 312                         return;
 313                 }
 314
 315                 if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
 316                         rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);
 317
 318                 range_tree_stat_decr(rt, rs);
 319                 rt->rt_space -= rend - rstart;
 320
 321                 fill += rs_get_fill(rs, rt);
 322                 start = MIN(start, rstart);
 323                 end = MAX(end, rend);
 324                 size = end - start;
 325
 326                 zfs_btree_remove(&rt->rt_root, rs);
 327                 range_tree_add_impl(rt, start, size, fill);
 328                 return;
 329         }
 330
 331         ASSERT3P(rs, ==, NULL);
 332
 333         /*
 334          * Determine whether or not we will have to merge with our neighbors.
 335          * If gap != 0, we might need to merge with our neighbors even if we
 336          * aren't directly touching.
 337          */
 338         zfs_btree_index_t where_before, where_after;
 339         rs_before = zfs_btree_prev(&rt->rt_root, &where, &where_before);
 340         rs_after = zfs_btree_next(&rt->rt_root, &where, &where_after);
 341
 342         merge_before = (rs_before != NULL && rs_get_end(rs_before, rt) >=
 343             start - gap);
 344         merge_after = (rs_after != NULL && rs_get_start(rs_after, rt) <= end +
 345             gap);
 346
 347         if (merge_before && gap != 0)
 348                 bridge_size += start - rs_get_end(rs_before, rt);
 349         if (merge_after && gap != 0)
 350                 bridge_size += rs_get_start(rs_after, rt) - end;
 351
 352         if (merge_before && merge_after) {
 353                 if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL) {
 354                         rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg);
 355                         rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg);
 356                 }
 357
 358                 range_tree_stat_decr(rt, rs_before);
 359                 range_tree_stat_decr(rt, rs_after);
 360
 361                 rs_copy(rs_after, &tmp, rt);
 362                 uint64_t before_start = rs_get_start_raw(rs_before, rt);
 363                 uint64_t before_fill = rs_get_fill(rs_before, rt);
 364                 uint64_t after_fill = rs_get_fill(rs_after, rt);
 365                 zfs_btree_remove_idx(&rt->rt_root, &where_before);
 366
 367                 /*
 368                  * We have to re-find the node because our old reference is
 369                  * invalid as soon as we do any mutating btree operations.
 370                  */
 371                 rs_after = zfs_btree_find(&rt->rt_root, &tmp, &where_after);
 372                 ASSERT3P(rs_after, !=, NULL);
 373                 rs_set_start_raw(rs_after, rt, before_start);
 374                 rs_set_fill(rs_after, rt, after_fill + before_fill + fill);
 375                 rs = rs_after;
 376         } else if (merge_before) {
 377                 if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
 378                         rt->rt_ops->rtop_remove(rt, rs_before, rt->rt_arg);
 379
 380                 range_tree_stat_decr(rt, rs_before);
 381
 382                 uint64_t before_fill = rs_get_fill(rs_before, rt);
 383                 rs_set_end(rs_before, rt, end);
 384                 rs_set_fill(rs_before, rt, before_fill + fill);
 385                 rs = rs_before;
 386         } else if (merge_after) {
 387                 if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
 388                         rt->rt_ops->rtop_remove(rt, rs_after, rt->rt_arg);
 389
 390                 range_tree_stat_decr(rt, rs_after);
 391
 392                 uint64_t after_fill = rs_get_fill(rs_after, rt);
 393                 rs_set_start(rs_after, rt, start);
 394                 rs_set_fill(rs_after, rt, after_fill + fill);
 395                 rs = rs_after;
 396         } else {
 397                 rs = &tmp;
 398
 399                 rs_set_start(rs, rt, start);
 400                 rs_set_end(rs, rt, end);
 401                 rs_set_fill(rs, rt, fill);
 402                 zfs_btree_add_idx(&rt->rt_root, rs, &where);
 403         }
 404
 405         if (gap != 0) {
 406                 ASSERT3U(rs_get_fill(rs, rt), <=, rs_get_end(rs, rt) -
 407                     rs_get_start(rs, rt));
 408         } else {
 409                 ASSERT3U(rs_get_fill(rs, rt), ==, rs_get_end(rs, rt) -
 410                     rs_get_start(rs, rt));
 411         }
 412
 413         if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)
 414                 rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);
 415
 416         range_tree_stat_incr(rt, rs);
 417         rt->rt_space += size + bridge_size;
 418 }
 419
 420 void
 421 range_tree_add(void *arg, uint64_t start, uint64_t size)
 422 {
 423         range_tree_add_impl(arg, start, size, size);
 424 }
 425
 426 static void
 427 range_tree_remove_impl(range_tree_t *rt, uint64_t start, uint64_t size,
 428     boolean_t do_fill)
 429 {
 430         zfs_btree_index_t where;
 431         range_seg_t *rs;
 432         range_seg_max_t rsearch, rs_tmp;
 433         uint64_t end = start + size;
 434         boolean_t left_over, right_over;
 435
 436         VERIFY3U(size, !=, 0);
 437         VERIFY3U(size, <=, rt->rt_space);
 438         if (rt->rt_type == RANGE_SEG64)
 439                 ASSERT3U(start + size, >, start);
 440
 441         rs_set_start(&rsearch, rt, start);
 442         rs_set_end(&rsearch, rt, end);
 443         rs = zfs_btree_find(&rt->rt_root, &rsearch, &where);
 444
 445         /* Make sure we completely overlap with someone */
 446         if (rs == NULL) {
 447                 zfs_panic_recover("zfs: removing nonexistent segment from "
 448                     "range tree (offset=%llx size=%llx)",
 449                     (longlong_t)start, (longlong_t)size);
 450                 return;
 451         }
 452
 453         /*
 454          * Range trees with gap support must only remove complete segments
 455          * from the tree. This allows us to maintain accurate fill accounting
 456          * and to ensure that bridged sections are not leaked. If we need to
 457          * remove less than the full segment, we can only adjust the fill count.
 458          */
 459         if (rt->rt_gap != 0) {
 460                 if (do_fill) {
 461                         if (rs_get_fill(rs, rt) == size) {
 462                                 start = rs_get_start(rs, rt);
 463                                 end = rs_get_end(rs, rt);
 464                                 size = end - start;
 465                         } else {
 466                                 range_tree_adjust_fill(rt, rs, -size);
 467                                 return;
 468                         }
 469                 } else if (rs_get_start(rs, rt) != start ||
 470                     rs_get_end(rs, rt) != end) {
 471                         zfs_panic_recover("zfs: freeing partial segment of "
 472                             "gap tree (offset=%llx size=%llx) of "
 473                             "(offset=%llx size=%llx)",
 474                             (longlong_t)start, (longlong_t)size,
 475                             (longlong_t)rs_get_start(rs, rt),
 476                             (longlong_t)rs_get_end(rs, rt) - rs_get_start(rs,
 477                             rt));
 478                         return;
 479                 }
 480         }
 481
 482         VERIFY3U(rs_get_start(rs, rt), <=, start);
 483         VERIFY3U(rs_get_end(rs, rt), >=, end);
 484
 485         left_over = (rs_get_start(rs, rt) != start);
 486         right_over = (rs_get_end(rs, rt) != end);
 487
 488         range_tree_stat_decr(rt, rs);
 489
 490         if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
 491                 rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);
 492
 493         if (left_over && right_over) {
 494                 range_seg_max_t newseg;
 495                 rs_set_start(&newseg, rt, end);
 496                 rs_set_end_raw(&newseg, rt, rs_get_end_raw(rs, rt));
 497                 rs_set_fill(&newseg, rt, rs_get_end(rs, rt) - end);
 498                 range_tree_stat_incr(rt, &newseg);
 499
 500                 // This modifies the buffer already inside the range tree
 501                 rs_set_end(rs, rt, start);
 502
 503                 rs_copy(rs, &rs_tmp, rt);
 504                 if (zfs_btree_next(&rt->rt_root, &where, &where) != NULL)
 505                         zfs_btree_add_idx(&rt->rt_root, &newseg, &where);
 506                 else
 507                         zfs_btree_add(&rt->rt_root, &newseg);
 508
 509                 if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)
 510                         rt->rt_ops->rtop_add(rt, &newseg, rt->rt_arg);
 511         } else if (left_over) {
 512                 // This modifies the buffer already inside the range tree
 513                 rs_set_end(rs, rt, start);
 514                 rs_copy(rs, &rs_tmp, rt);
 515         } else if (right_over) {
 516                 // This modifies the buffer already inside the range tree
 517                 rs_set_start(rs, rt, end);
 518                 rs_copy(rs, &rs_tmp, rt);
 519         } else {
 520                 zfs_btree_remove_idx(&rt->rt_root, &where);
 521                 rs = NULL;
 522         }
 523
 524         if (rs != NULL) {
 525                 /*
 526                  * The fill of the leftover segment will always be equal to
 527                  * the size, since we do not support removing partial segments
 528                  * of range trees with gaps.
 529                  */
 530                 rs_set_fill_raw(rs, rt, rs_get_end_raw(rs, rt) -
 531                     rs_get_start_raw(rs, rt));
 532                 range_tree_stat_incr(rt, &rs_tmp);
 533
 534                 if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)
 535                         rt->rt_ops->rtop_add(rt, &rs_tmp, rt->rt_arg);
 536         }
 537
 538         rt->rt_space -= size;
 539 }
 540
 541 void
 542 range_tree_remove(void *arg, uint64_t start, uint64_t size)
 543 {
 544         range_tree_remove_impl(arg, start, size, B_FALSE);
 545 }
 546
 547 void
 548 range_tree_remove_fill(range_tree_t *rt, uint64_t start, uint64_t size)
 549 {
 550         range_tree_remove_impl(rt, start, size, B_TRUE);
 551 }
 552
 553 void
 554 range_tree_resize_segment(range_tree_t *rt, range_seg_t *rs,
 555     uint64_t newstart, uint64_t newsize)
 556 {
 557         int64_t delta = newsize - (rs_get_end(rs, rt) - rs_get_start(rs, rt));
 558
 559         range_tree_stat_decr(rt, rs);
 560         if (rt->rt_ops != NULL && rt->rt_ops->rtop_remove != NULL)
 561                 rt->rt_ops->rtop_remove(rt, rs, rt->rt_arg);
 562
 563         rs_set_start(rs, rt, newstart);
 564         rs_set_end(rs, rt, newstart + newsize);
 565
 566         range_tree_stat_incr(rt, rs);
 567         if (rt->rt_ops != NULL && rt->rt_ops->rtop_add != NULL)
 568                 rt->rt_ops->rtop_add(rt, rs, rt->rt_arg);
 569
 570         rt->rt_space += delta;
 571 }
 572
 573 static range_seg_t *
 574 range_tree_find_impl(range_tree_t *rt, uint64_t start, uint64_t size)
 575 {
 576         range_seg_max_t rsearch;
 577         uint64_t end = start + size;
 578
 579         VERIFY(size != 0);
 580
 581         rs_set_start(&rsearch, rt, start);
 582         rs_set_end(&rsearch, rt, end);
 583         return (zfs_btree_find(&rt->rt_root, &rsearch, NULL));
 584 }
 585
 586 range_seg_t *
 587 range_tree_find(range_tree_t *rt, uint64_t start, uint64_t size)
 588 {
 589         if (rt->rt_type == RANGE_SEG64)
 590                 ASSERT3U(start + size, >, start);
 591
 592         range_seg_t *rs = range_tree_find_impl(rt, start, size);
 593         if (rs != NULL && rs_get_start(rs, rt) <= start &&
 594             rs_get_end(rs, rt) >= start + size) {
 595                 return (rs);
 596         }
 597         return (NULL);
 598 }
 599
 600 void
 601 range_tree_verify_not_present(range_tree_t *rt, uint64_t off, uint64_t size)
 602 {
 603         range_seg_t *rs = range_tree_find(rt, off, size);
 604         if (rs != NULL)
 605                 panic("segment already in tree; rs=%p", (void *)rs);
 606 }
 607
 608 boolean_t
 609 range_tree_contains(range_tree_t *rt, uint64_t start, uint64_t size)
 610 {
 611         return (range_tree_find(rt, start, size) != NULL);
 612 }
 613
 614 /*
 615  * Returns the first subset of the given range which overlaps with the range
 616  * tree. Returns true if there is a segment in the range, and false if there
 617  * isn't.
 618  */
 619 boolean_t
 620 range_tree_find_in(range_tree_t *rt, uint64_t start, uint64_t size,
 621     uint64_t *ostart, uint64_t *osize)
 622 {
 623         if (rt->rt_type == RANGE_SEG64)
 624                 ASSERT3U(start + size, >, start);
 625
 626         range_seg_max_t rsearch;
 627         rs_set_start(&rsearch, rt, start);
 628         rs_set_end_raw(&rsearch, rt, rs_get_start_raw(&rsearch, rt) + 1);
 629
 630         zfs_btree_index_t where;
 631         range_seg_t *rs = zfs_btree_find(&rt->rt_root, &rsearch, &where);
 632         if (rs != NULL) {
 633                 *ostart = start;
 634                 *osize = MIN(size, rs_get_end(rs, rt) - start);
 635                 return (B_TRUE);
 636         }
 637
 638         rs = zfs_btree_next(&rt->rt_root, &where, &where);
 639         if (rs == NULL || rs_get_start(rs, rt) > start + size)
 640                 return (B_FALSE);
 641
 642         *ostart = rs_get_start(rs, rt);
 643         *osize = MIN(start + size, rs_get_end(rs, rt)) -
 644             rs_get_start(rs, rt);
 645         return (B_TRUE);
 646 }
 647
 648 /*
 649  * Ensure that this range is not in the tree, regardless of whether
 650  * it is currently in the tree.
 651  */
 652 void
 653 range_tree_clear(range_tree_t *rt, uint64_t start, uint64_t size)
 654 {
 655         range_seg_t *rs;
 656
 657         if (size == 0)
 658                 return;
 659
 660         if (rt->rt_type == RANGE_SEG64)
 661                 ASSERT3U(start + size, >, start);
 662
 663         while ((rs = range_tree_find_impl(rt, start, size)) != NULL) {
 664                 uint64_t free_start = MAX(rs_get_start(rs, rt), start);
 665                 uint64_t free_end = MIN(rs_get_end(rs, rt), start + size);
 666                 range_tree_remove(rt, free_start, free_end - free_start);
 667         }
 668 }
 669
 670 void
 671 range_tree_swap(range_tree_t **rtsrc, range_tree_t **rtdst)
 672 {
 673         range_tree_t *rt;
 674
 675         ASSERT0(range_tree_space(*rtdst));
 676         ASSERT0(zfs_btree_numnodes(&(*rtdst)->rt_root));
 677
 678         rt = *rtsrc;
 679         *rtsrc = *rtdst;
 680         *rtdst = rt;
 681 }
 682
 683 void
 684 range_tree_vacate(range_tree_t *rt, range_tree_func_t *func, void *arg)
 685 {
 686         if (rt->rt_ops != NULL && rt->rt_ops->rtop_vacate != NULL)
 687                 rt->rt_ops->rtop_vacate(rt, rt->rt_arg);
 688
 689         if (func != NULL) {
 690                 range_seg_t *rs;
 691                 zfs_btree_index_t *cookie = NULL;
 692
 693                 while ((rs = zfs_btree_destroy_nodes(&rt->rt_root, &cookie)) !=
 694                     NULL) {
 695                         func(arg, rs_get_start(rs, rt), rs_get_end(rs, rt) -
 696                             rs_get_start(rs, rt));
 697                 }
 698         } else {
 699                 zfs_btree_clear(&rt->rt_root);
 700         }
 701
 702         memset(rt->rt_histogram, 0, sizeof (rt->rt_histogram));
 703         rt->rt_space = 0;
 704 }
 705
 706 void
 707 range_tree_walk(range_tree_t *rt, range_tree_func_t *func, void *arg)
 708 {
 709         zfs_btree_index_t where;
 710         for (range_seg_t *rs = zfs_btree_first(&rt->rt_root, &where);
 711             rs != NULL; rs = zfs_btree_next(&rt->rt_root, &where, &where)) {
 712                 func(arg, rs_get_start(rs, rt), rs_get_end(rs, rt) -
 713                     rs_get_start(rs, rt));
 714         }
 715 }
 716
 717 range_seg_t *
 718 range_tree_first(range_tree_t *rt)
 719 {
 720         return (zfs_btree_first(&rt->rt_root, NULL));
 721 }
 722
 723 uint64_t
 724 range_tree_space(range_tree_t *rt)
 725 {
 726         return (rt->rt_space);
 727 }
 728
 729 uint64_t
 730 range_tree_numsegs(range_tree_t *rt)
 731 {
 732         return ((rt == NULL) ? 0 : zfs_btree_numnodes(&rt->rt_root));
 733 }
 734
 735 boolean_t
 736 range_tree_is_empty(range_tree_t *rt)
 737 {
 738         ASSERT(rt != NULL);
 739         return (range_tree_space(rt) == 0);
 740 }
 741
 742 /*
 743  * Remove any overlapping ranges between the given segment [start, end)
 744  * from removefrom. Add non-overlapping leftovers to addto.
 745  */
 746 void
 747 range_tree_remove_xor_add_segment(uint64_t start, uint64_t end,
 748     range_tree_t *removefrom, range_tree_t *addto)
 749 {
 750         zfs_btree_index_t where;
 751         range_seg_max_t starting_rs;
 752         rs_set_start(&starting_rs, removefrom, start);
 753         rs_set_end_raw(&starting_rs, removefrom, rs_get_start_raw(&starting_rs,
 754             removefrom) + 1);
 755
 756         range_seg_t *curr = zfs_btree_find(&removefrom->rt_root,
 757             &starting_rs, &where);
 758
 759         if (curr == NULL)
 760                 curr = zfs_btree_next(&removefrom->rt_root, &where, &where);
 761
 762         range_seg_t *next;
 763         for (; curr != NULL; curr = next) {
 764                 if (start == end)
 765                         return;
 766                 VERIFY3U(start, <, end);
 767
 768                 /* there is no overlap */
 769                 if (end <= rs_get_start(curr, removefrom)) {
 770                         range_tree_add(addto, start, end - start);
 771                         return;
 772                 }
 773
 774                 uint64_t overlap_start = MAX(rs_get_start(curr, removefrom),
 775                     start);
 776                 uint64_t overlap_end = MIN(rs_get_end(curr, removefrom),
 777                     end);
 778                 uint64_t overlap_size = overlap_end - overlap_start;
 779                 ASSERT3S(overlap_size, >, 0);
 780                 range_seg_max_t rs;
 781                 rs_copy(curr, &rs, removefrom);
 782
 783                 range_tree_remove(removefrom, overlap_start, overlap_size);
 784
 785                 if (start < overlap_start)
 786                         range_tree_add(addto, start, overlap_start - start);
 787
 788                 start = overlap_end;
 789                 next = zfs_btree_find(&removefrom->rt_root, &rs, &where);
 790                 /*
 791                  * If we find something here, we only removed part of the
 792                  * curr segment. Either there's some left at the end
 793                  * because we've reached the end of the range we're removing,
 794                  * or there's some left at the start because we started
 795                  * partway through the range.  Either way, we continue with
 796                  * the loop. If it's the former, we'll return at the start of
 797                  * the loop, and if it's the latter we'll see if there is more
 798                  * area to process.
 799                  */
 800                 if (next != NULL) {
 801                         ASSERT(start == end || start == rs_get_end(&rs,
 802                             removefrom));
 803                 }
 804
 805                 next = zfs_btree_next(&removefrom->rt_root, &where, &where);
 806         }
 807         VERIFY3P(curr, ==, NULL);
 808
 809         if (start != end) {
 810                 VERIFY3U(start, <, end);
 811                 range_tree_add(addto, start, end - start);
 812         } else {
 813                 VERIFY3U(start, ==, end);
 814         }
 815 }
 816
 817 /*
 818  * For each entry in rt, if it exists in removefrom, remove it
 819  * from removefrom. Otherwise, add it to addto.
 820  */
 821 void
 822 range_tree_remove_xor_add(range_tree_t *rt, range_tree_t *removefrom,
 823     range_tree_t *addto)
 824 {
 825         zfs_btree_index_t where;
 826         for (range_seg_t *rs = zfs_btree_first(&rt->rt_root, &where); rs;
 827             rs = zfs_btree_next(&rt->rt_root, &where, &where)) {
 828                 range_tree_remove_xor_add_segment(rs_get_start(rs, rt),
 829                     rs_get_end(rs, rt), removefrom, addto);
 830         }
 831 }
 832
 833 uint64_t
 834 range_tree_min(range_tree_t *rt)
 835 {
 836         range_seg_t *rs = zfs_btree_first(&rt->rt_root, NULL);
 837         return (rs != NULL ? rs_get_start(rs, rt) : 0);
 838 }
 839
 840 uint64_t
 841 range_tree_max(range_tree_t *rt)
 842 {
 843         range_seg_t *rs = zfs_btree_last(&rt->rt_root, NULL);
 844         return (rs != NULL ? rs_get_end(rs, rt) : 0);
 845 }
 846
 847 uint64_t
 848 range_tree_span(range_tree_t *rt)
 849 {
 850         return (range_tree_max(rt) - range_tree_min(rt));
 851 }