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