lib/ext2fs/blkmap64_rb.c

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