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