1 /* 2 * blkmap64_rb.c --- Simple rb-tree implementation for bitmaps 3 * 4 * (C)2010 Red Hat, Inc., Lukas Czerner <lczerner@redhat.com> 5 * 6 * %Begin-Header% 7 * This file may be redistributed under the terms of the GNU Public 8 * License. 9 * %End-Header% 10 */ 11 12 #include "config.h" 13 #include <stdio.h> 14 #include <string.h> 15 #if HAVE_UNISTD_H 16 #include <unistd.h> 17 #endif 18 #include <fcntl.h> 19 #include <time.h> 20 #if HAVE_SYS_STAT_H 21 #include <sys/stat.h> 22 #endif 23 #if HAVE_SYS_TYPES_H 24 #include <sys/types.h> 25 #endif 26 #if HAVE_LINUX_TYPES_H 27 #include <linux/types.h> 28 #endif 29 30 #include "ext2_fs.h" 31 #include "ext2fsP.h" 32 #include "bmap64.h" 33 #include "rbtree.h" 34 35 #include <limits.h> 36 37 struct bmap_rb_extent { 38 struct rb_node node; 39 __u64 start; 40 __u64 count; 41 }; 42 43 struct ext2fs_rb_private { 44 struct rb_root root; 45 struct bmap_rb_extent *wcursor; 46 struct bmap_rb_extent *rcursor; 47 struct bmap_rb_extent *rcursor_next; 48 #ifdef ENABLE_BMAP_STATS_OPS 49 __u64 mark_hit; 50 __u64 test_hit; 51 #endif 52 }; 53 54 inline static struct bmap_rb_extent *node_to_extent(struct rb_node *node) 55 { 56 /* 57 * This depends on the fact the struct rb_node is at the 58 * beginning of the bmap_rb_extent structure. We use this 59 * instead of the ext2fs_rb_entry macro because it causes gcc 60 * -Wall to generate a huge amount of noise. 61 */ 62 return (struct bmap_rb_extent *) node; 63 } 64 65 static int rb_insert_extent(__u64 start, __u64 count, 66 struct ext2fs_rb_private *); 67 static void rb_get_new_extent(struct bmap_rb_extent **, __u64, __u64); 68 69 /* #define DEBUG_RB */ 70 71 #ifdef DEBUG_RB 72 static void print_tree(struct rb_root *root) 73 { 74 struct rb_node *node = NULL; 75 struct bmap_rb_extent *ext; 76 77 fprintf(stderr, "\t\t\t=================================\n"); 78 node = ext2fs_rb_first(root); 79 for (node = ext2fs_rb_first(root); node != NULL; 80 node = ext2fs_rb_next(node)) { 81 ext = node_to_extent(node); 82 fprintf(stderr, "\t\t\t--> (%llu -> %llu)\n", 83 (unsigned long long) ext->start, 84 (unsigned long long) ext->start + ext->count); 85 } 86 fprintf(stderr, "\t\t\t=================================\n"); 87 } 88 89 static void check_tree(struct rb_root *root, const char *msg) 90 { 91 struct rb_node *node; 92 struct bmap_rb_extent *ext, *old = NULL; 93 94 for (node = ext2fs_rb_first(root); node; 95 node = ext2fs_rb_next(node)) { 96 ext = node_to_extent(node); 97 if (ext->count == 0) { 98 fprintf(stderr, "Tree Error: count is zero\n"); 99 fprintf(stderr, "extent: %llu -> %llu (%llu)\n", 100 (unsigned long long) ext->start, 101 (unsigned long long) ext->start + ext->count, 102 (unsigned long long) ext->count); 103 goto err_out; 104 } 105 if (ext->start + ext->count < ext->start) { 106 fprintf(stderr, 107 "Tree Error: start or count is crazy\n"); 108 fprintf(stderr, "extent: %llu -> %llu (%llu)\n", 109 (unsigned long long) ext->start, 110 (unsigned long long) ext->start + ext->count, 111 (unsigned long long) ext->count); 112 goto err_out; 113 } 114 115 if (old) { 116 if (old->start > ext->start) { 117 fprintf(stderr, "Tree Error: start is crazy\n"); 118 fprintf(stderr, "extent: %llu -> %llu (%llu)\n", 119 (unsigned long long) old->start, 120 (unsigned long long) old->start + old->count, 121 (unsigned long long) old->count); 122 fprintf(stderr, 123 "extent next: %llu -> %llu (%llu)\n", 124 (unsigned long long) ext->start, 125 (unsigned long long) ext->start + ext->count, 126 (unsigned long long) ext->count); 127 goto err_out; 128 } 129 if ((old->start + old->count) >= ext->start) { 130 fprintf(stderr, 131 "Tree Error: extent is crazy\n"); 132 fprintf(stderr, "extent: %llu -> %llu (%llu)\n", 133 (unsigned long long) old->start, 134 (unsigned long long) old->start + old->count, 135 (unsigned long long) old->count); 136 fprintf(stderr, 137 "extent next: %llu -> %llu (%llu)\n", 138 (unsigned long long) ext->start, 139 (unsigned long long) ext->start + ext->count, 140 (unsigned long long) ext->count); 141 goto err_out; 142 } 143 } 144 old = ext; 145 } 146 return; 147 148 err_out: 149 fprintf(stderr, "%s\n", msg); 150 print_tree(root); 151 exit(1); 152 } 153 #else 154 #define check_tree(root, msg) do {} while (0) 155 #define print_tree(root) do {} while (0) 156 #endif 157 158 static void rb_get_new_extent(struct bmap_rb_extent **ext, __u64 start, 159 __u64 count) 160 { 161 struct bmap_rb_extent *new_ext; 162 int retval; 163 164 retval = ext2fs_get_mem(sizeof (struct bmap_rb_extent), 165 &new_ext); 166 if (retval) 167 abort(); 168 169 new_ext->start = start; 170 new_ext->count = count; 171 *ext = new_ext; 172 } 173 174 inline 175 static void rb_free_extent(struct ext2fs_rb_private *bp, 176 struct bmap_rb_extent *ext) 177 { 178 if (bp->wcursor == ext) 179 bp->wcursor = NULL; 180 if (bp->rcursor == ext) 181 bp->rcursor = NULL; 182 if (bp->rcursor_next == ext) 183 bp->rcursor_next = NULL; 184 ext2fs_free_mem(&ext); 185 } 186 187 static errcode_t rb_alloc_private_data (ext2fs_generic_bitmap_64 bitmap) 188 { 189 struct ext2fs_rb_private *bp; 190 errcode_t retval; 191 192 retval = ext2fs_get_mem(sizeof (struct ext2fs_rb_private), &bp); 193 if (retval) 194 return retval; 195 196 bp->root = RB_ROOT; 197 bp->rcursor = NULL; 198 bp->rcursor_next = NULL; 199 bp->wcursor = NULL; 200 201 #ifdef ENABLE_BMAP_STATS_OPS 202 bp->test_hit = 0; 203 bp->mark_hit = 0; 204 #endif 205 206 bitmap->private = (void *) bp; 207 return 0; 208 } 209 210 static errcode_t rb_new_bmap(ext2_filsys fs EXT2FS_ATTR((unused)), 211 ext2fs_generic_bitmap_64 bitmap) 212 { 213 errcode_t retval; 214 215 retval = rb_alloc_private_data (bitmap); 216 if (retval) 217 return retval; 218 219 return 0; 220 } 221 222 static void rb_free_tree(struct rb_root *root) 223 { 224 struct bmap_rb_extent *ext; 225 struct rb_node *node, *next; 226 227 for (node = ext2fs_rb_first(root); node; node = next) { 228 next = ext2fs_rb_next(node); 229 ext = node_to_extent(node); 230 ext2fs_rb_erase(node, root); 231 ext2fs_free_mem(&ext); 232 } 233 } 234 235 static void rb_free_bmap(ext2fs_generic_bitmap_64 bitmap) 236 { 237 struct ext2fs_rb_private *bp; 238 239 bp = (struct ext2fs_rb_private *) bitmap->private; 240 241 rb_free_tree(&bp->root); 242 ext2fs_free_mem(&bp); 243 bp = 0; 244 } 245 246 static errcode_t rb_copy_bmap(ext2fs_generic_bitmap_64 src, 247 ext2fs_generic_bitmap_64 dest) 248 { 249 struct ext2fs_rb_private *src_bp, *dest_bp; 250 struct bmap_rb_extent *src_ext, *dest_ext; 251 struct rb_node *dest_node, *src_node, *dest_last, **n; 252 errcode_t retval = 0; 253 254 retval = rb_alloc_private_data (dest); 255 if (retval) 256 return retval; 257 258 src_bp = (struct ext2fs_rb_private *) src->private; 259 dest_bp = (struct ext2fs_rb_private *) dest->private; 260 src_bp->rcursor = NULL; 261 dest_bp->rcursor = NULL; 262 263 src_node = ext2fs_rb_first(&src_bp->root); 264 while (src_node) { 265 src_ext = node_to_extent(src_node); 266 retval = ext2fs_get_mem(sizeof (struct bmap_rb_extent), 267 &dest_ext); 268 if (retval) 269 break; 270 271 memcpy(dest_ext, src_ext, sizeof(struct bmap_rb_extent)); 272 273 dest_node = &dest_ext->node; 274 n = &dest_bp->root.rb_node; 275 276 dest_last = NULL; 277 if (*n) { 278 dest_last = ext2fs_rb_last(&dest_bp->root); 279 n = &(dest_last)->rb_right; 280 } 281 282 ext2fs_rb_link_node(dest_node, dest_last, n); 283 ext2fs_rb_insert_color(dest_node, &dest_bp->root); 284 285 src_node = ext2fs_rb_next(src_node); 286 } 287 288 return retval; 289 } 290 291 static void rb_truncate(__u64 new_max, struct rb_root *root) 292 { 293 struct bmap_rb_extent *ext; 294 struct rb_node *node; 295 296 node = ext2fs_rb_last(root); 297 while (node) { 298 ext = node_to_extent(node); 299 300 if ((ext->start + ext->count - 1) <= new_max) 301 break; 302 else if (ext->start > new_max) { 303 ext2fs_rb_erase(node, root); 304 ext2fs_free_mem(&ext); 305 node = ext2fs_rb_last(root); 306 continue; 307 } else 308 ext->count = new_max - ext->start + 1; 309 } 310 } 311 312 static errcode_t rb_resize_bmap(ext2fs_generic_bitmap_64 bmap, 313 __u64 new_end, __u64 new_real_end) 314 { 315 struct ext2fs_rb_private *bp; 316 317 bp = (struct ext2fs_rb_private *) bmap->private; 318 bp->rcursor = NULL; 319 bp->wcursor = NULL; 320 321 rb_truncate(((new_end < bmap->end) ? new_end : bmap->end) - bmap->start, 322 &bp->root); 323 324 bmap->end = new_end; 325 bmap->real_end = new_real_end; 326 327 if (bmap->end < bmap->real_end) 328 rb_insert_extent(bmap->end + 1 - bmap->start, 329 bmap->real_end - bmap->end, bp); 330 return 0; 331 332 } 333 334 inline static int 335 rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit) 336 { 337 struct bmap_rb_extent *rcursor, *next_ext = NULL; 338 struct rb_node *parent = NULL, *next; 339 struct rb_node **n = &bp->root.rb_node; 340 struct bmap_rb_extent *ext; 341 342 rcursor = bp->rcursor; 343 if (!rcursor) 344 goto search_tree; 345 346 if (bit >= rcursor->start && bit < rcursor->start + rcursor->count) { 347 #ifdef ENABLE_BMAP_STATS_OPS 348 bp->test_hit++; 349 #endif 350 return 1; 351 } 352 353 next_ext = bp->rcursor_next; 354 if (!next_ext) { 355 next = ext2fs_rb_next(&rcursor->node); 356 if (next) 357 next_ext = node_to_extent(next); 358 bp->rcursor_next = next_ext; 359 } 360 if (next_ext) { 361 if ((bit >= rcursor->start + rcursor->count) && 362 (bit < next_ext->start)) { 363 #ifdef BMAP_STATS_OPS 364 bp->test_hit++; 365 #endif 366 return 0; 367 } 368 } 369 bp->rcursor = NULL; 370 bp->rcursor_next = NULL; 371 372 rcursor = bp->wcursor; 373 if (!rcursor) 374 goto search_tree; 375 376 if (bit >= rcursor->start && bit < rcursor->start + rcursor->count) 377 return 1; 378 379 search_tree: 380 381 while (*n) { 382 parent = *n; 383 ext = node_to_extent(parent); 384 if (bit < ext->start) 385 n = &(*n)->rb_left; 386 else if (bit >= (ext->start + ext->count)) 387 n = &(*n)->rb_right; 388 else { 389 bp->rcursor = ext; 390 bp->rcursor_next = NULL; 391 return 1; 392 } 393 } 394 return 0; 395 } 396 397 static int rb_insert_extent(__u64 start, __u64 count, 398 struct ext2fs_rb_private *bp) 399 { 400 struct rb_root *root = &bp->root; 401 struct rb_node *parent = NULL, **n = &root->rb_node; 402 struct rb_node *new_node, *node, *next; 403 struct bmap_rb_extent *new_ext; 404 struct bmap_rb_extent *ext; 405 int retval = 0; 406 407 if (count == 0) 408 return 0; 409 410 bp->rcursor_next = NULL; 411 ext = bp->wcursor; 412 if (ext) { 413 if (start >= ext->start && 414 start <= (ext->start + ext->count)) { 415 #ifdef ENABLE_BMAP_STATS_OPS 416 bp->mark_hit++; 417 #endif 418 goto got_extent; 419 } 420 } 421 422 while (*n) { 423 parent = *n; 424 ext = node_to_extent(parent); 425 426 if (start < ext->start) { 427 n = &(*n)->rb_left; 428 } else if (start > (ext->start + ext->count)) { 429 n = &(*n)->rb_right; 430 } else { 431 got_extent: 432 if ((start + count) <= (ext->start + ext->count)) 433 return 1; 434 435 if ((ext->start + ext->count) == start) 436 retval = 0; 437 else 438 retval = 1; 439 440 count += (start - ext->start); 441 start = ext->start; 442 new_ext = ext; 443 new_node = &ext->node; 444 445 goto skip_insert; 446 } 447 } 448 449 rb_get_new_extent(&new_ext, start, count); 450 451 new_node = &new_ext->node; 452 ext2fs_rb_link_node(new_node, parent, n); 453 ext2fs_rb_insert_color(new_node, root); 454 bp->wcursor = new_ext; 455 456 node = ext2fs_rb_prev(new_node); 457 if (node) { 458 ext = node_to_extent(node); 459 if ((ext->start + ext->count) == start) { 460 start = ext->start; 461 count += ext->count; 462 ext2fs_rb_erase(node, root); 463 rb_free_extent(bp, ext); 464 } 465 } 466 467 skip_insert: 468 /* See if we can merge extent to the right */ 469 for (node = ext2fs_rb_next(new_node); node != NULL; node = next) { 470 next = ext2fs_rb_next(node); 471 ext = node_to_extent(node); 472 473 if ((ext->start + ext->count) <= start) 474 continue; 475 476 /* No more merging */ 477 if ((start + count) < ext->start) 478 break; 479 480 /* ext is embedded in new_ext interval */ 481 if ((start + count) >= (ext->start + ext->count)) { 482 ext2fs_rb_erase(node, root); 483 rb_free_extent(bp, ext); 484 continue; 485 } else { 486 /* merge ext with new_ext */ 487 count += ((ext->start + ext->count) - 488 (start + count)); 489 ext2fs_rb_erase(node, root); 490 rb_free_extent(bp, ext); 491 break; 492 } 493 } 494 495 new_ext->start = start; 496 new_ext->count = count; 497 498 return retval; 499 } 500 501 static int rb_remove_extent(__u64 start, __u64 count, 502 struct ext2fs_rb_private *bp) 503 { 504 struct rb_root *root = &bp->root; 505 struct rb_node *parent = NULL, **n = &root->rb_node; 506 struct rb_node *node; 507 struct bmap_rb_extent *ext; 508 __u64 new_start, new_count; 509 int retval = 0; 510 511 if (ext2fs_rb_empty_root(root)) 512 return 0; 513 514 while (*n) { 515 parent = *n; 516 ext = node_to_extent(parent); 517 if (start < ext->start) { 518 n = &(*n)->rb_left; 519 continue; 520 } else if (start >= (ext->start + ext->count)) { 521 n = &(*n)->rb_right; 522 continue; 523 } 524 525 if ((start > ext->start) && 526 (start + count) < (ext->start + ext->count)) { 527 /* We have to split extent into two */ 528 new_start = start + count; 529 new_count = (ext->start + ext->count) - new_start; 530 531 ext->count = start - ext->start; 532 533 rb_insert_extent(new_start, new_count, bp); 534 return 1; 535 } 536 537 if ((start + count) >= (ext->start + ext->count)) { 538 ext->count = start - ext->start; 539 retval = 1; 540 } 541 542 if (0 == ext->count) { 543 parent = ext2fs_rb_next(&ext->node); 544 ext2fs_rb_erase(&ext->node, root); 545 rb_free_extent(bp, ext); 546 break; 547 } 548 549 if (start == ext->start) { 550 ext->start += count; 551 ext->count -= count; 552 return 1; 553 } 554 } 555 556 /* See if we should delete or truncate extent on the right */ 557 for (; parent != NULL; parent = node) { 558 node = ext2fs_rb_next(parent); 559 ext = node_to_extent(parent); 560 if ((ext->start + ext->count) <= start) 561 continue; 562 563 /* No more extents to be removed/truncated */ 564 if ((start + count) < ext->start) 565 break; 566 567 /* The entire extent is within the region to be removed */ 568 if ((start + count) >= (ext->start + ext->count)) { 569 ext2fs_rb_erase(parent, root); 570 rb_free_extent(bp, ext); 571 retval = 1; 572 continue; 573 } else { 574 /* modify the last extent in region to be removed */ 575 ext->count -= ((start + count) - ext->start); 576 ext->start = start + count; 577 retval = 1; 578 break; 579 } 580 } 581 582 return retval; 583 } 584 585 static int rb_mark_bmap(ext2fs_generic_bitmap_64 bitmap, __u64 arg) 586 { 587 struct ext2fs_rb_private *bp; 588 int retval; 589 590 bp = (struct ext2fs_rb_private *) bitmap->private; 591 arg -= bitmap->start; 592 593 retval = rb_insert_extent(arg, 1, bp); 594 check_tree(&bp->root, __func__); 595 return retval; 596 } 597 598 static int rb_unmark_bmap(ext2fs_generic_bitmap_64 bitmap, __u64 arg) 599 { 600 struct ext2fs_rb_private *bp; 601 int retval; 602 603 bp = (struct ext2fs_rb_private *) bitmap->private; 604 arg -= bitmap->start; 605 606 retval = rb_remove_extent(arg, 1, bp); 607 check_tree(&bp->root, __func__); 608 609 return retval; 610 } 611 612 inline 613 static int rb_test_bmap(ext2fs_generic_bitmap_64 bitmap, __u64 arg) 614 { 615 struct ext2fs_rb_private *bp; 616 617 bp = (struct ext2fs_rb_private *) bitmap->private; 618 arg -= bitmap->start; 619 620 return rb_test_bit(bp, arg); 621 } 622 623 static void rb_mark_bmap_extent(ext2fs_generic_bitmap_64 bitmap, __u64 arg, 624 unsigned int num) 625 { 626 struct ext2fs_rb_private *bp; 627 628 bp = (struct ext2fs_rb_private *) bitmap->private; 629 arg -= bitmap->start; 630 631 rb_insert_extent(arg, num, bp); 632 check_tree(&bp->root, __func__); 633 } 634 635 static void rb_unmark_bmap_extent(ext2fs_generic_bitmap_64 bitmap, __u64 arg, 636 unsigned int num) 637 { 638 struct ext2fs_rb_private *bp; 639 640 bp = (struct ext2fs_rb_private *) bitmap->private; 641 arg -= bitmap->start; 642 643 rb_remove_extent(arg, num, bp); 644 check_tree(&bp->root, __func__); 645 } 646 647 static int rb_test_clear_bmap_extent(ext2fs_generic_bitmap_64 bitmap, 648 __u64 start, unsigned int len) 649 { 650 struct rb_node *parent = NULL, **n; 651 struct rb_node *node, *next; 652 struct ext2fs_rb_private *bp; 653 struct bmap_rb_extent *ext; 654 int retval = 1; 655 656 bp = (struct ext2fs_rb_private *) bitmap->private; 657 n = &bp->root.rb_node; 658 start -= bitmap->start; 659 660 if (len == 0 || ext2fs_rb_empty_root(&bp->root)) 661 return 1; 662 663 /* 664 * If we find nothing, we should examine whole extent, but 665 * when we find match, the extent is not clean, thus be return 666 * false. 667 */ 668 while (*n) { 669 parent = *n; 670 ext = node_to_extent(parent); 671 if (start < ext->start) { 672 n = &(*n)->rb_left; 673 } else if (start >= (ext->start + ext->count)) { 674 n = &(*n)->rb_right; 675 } else { 676 /* 677 * We found extent int the tree -> extent is not 678 * clean 679 */ 680 return 0; 681 } 682 } 683 684 node = parent; 685 while (node) { 686 next = ext2fs_rb_next(node); 687 ext = node_to_extent(node); 688 node = next; 689 690 if ((ext->start + ext->count) <= start) 691 continue; 692 693 /* No more merging */ 694 if ((start + len) <= ext->start) 695 break; 696 697 retval = 0; 698 break; 699 } 700 return retval; 701 } 702 703 static errcode_t rb_set_bmap_range(ext2fs_generic_bitmap_64 bitmap, 704 __u64 start, size_t num, void *in) 705 { 706 struct ext2fs_rb_private *bp; 707 unsigned char *cp = in; 708 size_t i; 709 int first_set = -1; 710 711 bp = (struct ext2fs_rb_private *) bitmap->private; 712 713 for (i = 0; i < num; i++) { 714 if ((i & 7) == 0) { 715 unsigned char c = cp[i/8]; 716 if (c == 0xFF) { 717 if (first_set == -1) 718 first_set = i; 719 i += 7; 720 continue; 721 } 722 if ((c == 0x00) && (first_set == -1)) { 723 i += 7; 724 continue; 725 } 726 } 727 if (ext2fs_test_bit(i, in)) { 728 if (first_set == -1) 729 first_set = i; 730 continue; 731 } 732 if (first_set == -1) 733 continue; 734 735 rb_insert_extent(start + first_set - bitmap->start, 736 i - first_set, bp); 737 check_tree(&bp->root, __func__); 738 first_set = -1; 739 } 740 if (first_set != -1) { 741 rb_insert_extent(start + first_set - bitmap->start, 742 num - first_set, bp); 743 check_tree(&bp->root, __func__); 744 } 745 746 return 0; 747 } 748 749 static errcode_t rb_get_bmap_range(ext2fs_generic_bitmap_64 bitmap, 750 __u64 start, size_t num, void *out) 751 { 752 753 struct rb_node *parent = NULL, *next, **n; 754 struct ext2fs_rb_private *bp; 755 struct bmap_rb_extent *ext; 756 __u64 count, pos; 757 758 bp = (struct ext2fs_rb_private *) bitmap->private; 759 n = &bp->root.rb_node; 760 start -= bitmap->start; 761 762 if (ext2fs_rb_empty_root(&bp->root)) 763 return 0; 764 765 while (*n) { 766 parent = *n; 767 ext = node_to_extent(parent); 768 if (start < ext->start) { 769 n = &(*n)->rb_left; 770 } else if (start >= (ext->start + ext->count)) { 771 n = &(*n)->rb_right; 772 } else 773 break; 774 } 775 776 memset(out, 0, (num + 7) >> 3); 777 778 for (; parent != NULL; parent = next) { 779 next = ext2fs_rb_next(parent); 780 ext = node_to_extent(parent); 781 782 pos = ext->start; 783 count = ext->count; 784 if (pos >= start + num) 785 break; 786 if (pos < start) { 787 if (pos + count < start) 788 continue; 789 count -= start - pos; 790 pos = start; 791 } 792 if (pos + count > start + num) 793 count = start + num - pos; 794 795 while (count > 0) { 796 if ((count >= 8) && 797 ((pos - start) % 8) == 0) { 798 int nbytes = count >> 3; 799 int offset = (pos - start) >> 3; 800 801 memset(((char *) out) + offset, 0xFF, nbytes); 802 pos += nbytes << 3; 803 count -= nbytes << 3; 804 continue; 805 } 806 ext2fs_fast_set_bit64((pos - start), out); 807 pos++; 808 count--; 809 } 810 } 811 return 0; 812 } 813 814 static void rb_clear_bmap(ext2fs_generic_bitmap_64 bitmap) 815 { 816 struct ext2fs_rb_private *bp; 817 818 bp = (struct ext2fs_rb_private *) bitmap->private; 819 820 rb_free_tree(&bp->root); 821 bp->rcursor = NULL; 822 bp->rcursor_next = NULL; 823 bp->wcursor = NULL; 824 check_tree(&bp->root, __func__); 825 } 826 827 static errcode_t rb_find_first_zero(ext2fs_generic_bitmap_64 bitmap, 828 __u64 start, __u64 end, __u64 *out) 829 { 830 struct rb_node *parent = NULL, **n; 831 struct ext2fs_rb_private *bp; 832 struct bmap_rb_extent *ext; 833 834 bp = (struct ext2fs_rb_private *) bitmap->private; 835 n = &bp->root.rb_node; 836 start -= bitmap->start; 837 end -= bitmap->start; 838 839 if (start > end) 840 return EINVAL; 841 842 if (ext2fs_rb_empty_root(&bp->root)) 843 return ENOENT; 844 845 while (*n) { 846 parent = *n; 847 ext = node_to_extent(parent); 848 if (start < ext->start) { 849 n = &(*n)->rb_left; 850 } else if (start >= (ext->start + ext->count)) { 851 n = &(*n)->rb_right; 852 } else if (ext->start + ext->count <= end) { 853 *out = ext->start + ext->count + bitmap->start; 854 return 0; 855 } else 856 return ENOENT; 857 } 858 859 *out = start + bitmap->start; 860 return 0; 861 } 862 863 static errcode_t rb_find_first_set(ext2fs_generic_bitmap_64 bitmap, 864 __u64 start, __u64 end, __u64 *out) 865 { 866 struct rb_node *parent = NULL, **n; 867 struct rb_node *node; 868 struct ext2fs_rb_private *bp; 869 struct bmap_rb_extent *ext; 870 871 bp = (struct ext2fs_rb_private *) bitmap->private; 872 n = &bp->root.rb_node; 873 start -= bitmap->start; 874 end -= bitmap->start; 875 876 if (start > end) 877 return EINVAL; 878 879 if (ext2fs_rb_empty_root(&bp->root)) 880 return ENOENT; 881 882 while (*n) { 883 parent = *n; 884 ext = node_to_extent(parent); 885 if (start < ext->start) { 886 n = &(*n)->rb_left; 887 } else if (start >= (ext->start + ext->count)) { 888 n = &(*n)->rb_right; 889 } else { 890 /* The start bit is set */ 891 *out = start + bitmap->start; 892 return 0; 893 } 894 } 895 896 node = parent; 897 ext = node_to_extent(node); 898 if (ext->start < start) { 899 node = ext2fs_rb_next(node); 900 if (node == NULL) 901 return ENOENT; 902 ext = node_to_extent(node); 903 } 904 if (ext->start <= end) { 905 *out = ext->start + bitmap->start; 906 return 0; 907 } 908 return ENOENT; 909 } 910 911 #ifdef ENABLE_BMAP_STATS 912 static void rb_print_stats(ext2fs_generic_bitmap_64 bitmap) 913 { 914 struct ext2fs_rb_private *bp; 915 struct rb_node *node = NULL; 916 struct bmap_rb_extent *ext; 917 __u64 count = 0; 918 __u64 max_size = 0; 919 __u64 min_size = ULONG_MAX; 920 __u64 size = 0, avg_size = 0; 921 double eff; 922 #ifdef ENABLE_BMAP_STATS_OPS 923 __u64 mark_all, test_all; 924 double m_hit = 0.0, t_hit = 0.0; 925 #endif 926 927 bp = (struct ext2fs_rb_private *) bitmap->private; 928 929 for (node = ext2fs_rb_first(&bp->root); node != NULL; 930 node = ext2fs_rb_next(node)) { 931 ext = node_to_extent(node); 932 count++; 933 if (ext->count > max_size) 934 max_size = ext->count; 935 if (ext->count < min_size) 936 min_size = ext->count; 937 size += ext->count; 938 } 939 940 if (count) 941 avg_size = size / count; 942 if (min_size == ULONG_MAX) 943 min_size = 0; 944 eff = (double)((count * sizeof(struct bmap_rb_extent)) << 3) / 945 (bitmap->real_end - bitmap->start); 946 #ifdef ENABLE_BMAP_STATS_OPS 947 mark_all = bitmap->stats.mark_count + bitmap->stats.mark_ext_count; 948 test_all = bitmap->stats.test_count + bitmap->stats.test_ext_count; 949 if (mark_all) 950 m_hit = ((double)bp->mark_hit / mark_all) * 100; 951 if (test_all) 952 t_hit = ((double)bp->test_hit / test_all) * 100; 953 954 fprintf(stderr, "%16llu cache hits on test (%.2f%%)\n" 955 "%16llu cache hits on mark (%.2f%%)\n", 956 bp->test_hit, t_hit, bp->mark_hit, m_hit); 957 #endif 958 fprintf(stderr, "%16llu extents (%llu bytes)\n", 959 (unsigned long long) count, (unsigned long long) 960 ((count * sizeof(struct bmap_rb_extent)) + 961 sizeof(struct ext2fs_rb_private))); 962 fprintf(stderr, "%16llu bits minimum size\n", 963 (unsigned long long) min_size); 964 fprintf(stderr, "%16llu bits maximum size\n" 965 "%16llu bits average size\n", 966 (unsigned long long) max_size, (unsigned long long) avg_size); 967 fprintf(stderr, "%16llu bits set in bitmap (out of %llu)\n", 968 (unsigned long long) size, 969 (unsigned long long) bitmap->real_end - bitmap->start); 970 fprintf(stderr, 971 "%16.4lf memory / bitmap bit memory ratio (bitarray = 1)\n", 972 eff); 973 } 974 #else 975 static void rb_print_stats(ext2fs_generic_bitmap_64 bitmap EXT2FS_ATTR((unused))) 976 { 977 } 978 #endif 979 980 struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = { 981 .type = EXT2FS_BMAP64_RBTREE, 982 .new_bmap = rb_new_bmap, 983 .free_bmap = rb_free_bmap, 984 .copy_bmap = rb_copy_bmap, 985 .resize_bmap = rb_resize_bmap, 986 .mark_bmap = rb_mark_bmap, 987 .unmark_bmap = rb_unmark_bmap, 988 .test_bmap = rb_test_bmap, 989 .test_clear_bmap_extent = rb_test_clear_bmap_extent, 990 .mark_bmap_extent = rb_mark_bmap_extent, 991 .unmark_bmap_extent = rb_unmark_bmap_extent, 992 .set_bmap_range = rb_set_bmap_range, 993 .get_bmap_range = rb_get_bmap_range, 994 .clear_bmap = rb_clear_bmap, 995 .print_stats = rb_print_stats, 996 .find_first_zero = rb_find_first_zero, 997 .find_first_set = rb_find_first_set, 998 };