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