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