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         struct bmap_rb_extent *rcursor_next;
  44 #ifdef BMAP_STATS_OPS
  45         __u64 mark_hit;
  46         __u64 test_hit;
  47 #endif
  48 };
  49
  50 static int rb_insert_extent(__u64 start, __u64 count,
  51                             struct ext2fs_rb_private *);
  52 static void rb_get_new_extent(struct bmap_rb_extent **, __u64, __u64);
  53
  54 /* #define DEBUG_RB */
  55
  56 #ifdef DEBUG_RB
  57 static 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
  73 static int 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 0;
 119
 120 err_out:
 121         printf("%s\n", msg);
 122         print_tree(root);
 123         exit(1);
 124 }
 125 #else
 126 #define check_tree(root, msg) 0
 127 #define print_tree(root, msg) 0
 128 #endif
 129
 130 static 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
 148 inline
 149 static 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
 161 static 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
 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);
 217         bp = 0;
 218 }
 219
 220 static 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
 265 static 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
 286 static 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
 310 inline static int
 311 rb_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
 356 search_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
 374 static 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 {
 405 got_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
 441 skip_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
 475 static 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
 559 static 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
 569 static 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
 583 inline
 584 static 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
 594 static 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
 605 static 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
 617 static 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
 673 static 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         int ret;
 681
 682         bp = (struct ext2fs_rb_private *) bitmap->private;
 683
 684         for (i = 0; i < num; i++) {
 685                 if (i & 7 == 0) {
 686                         unsigned char c = cp[i/8];
 687                         if (c == 0xFF) {
 688                                 if (first_set == -1)
 689                                         first_set = i;
 690                                 i += 7;
 691                                 continue;
 692                         }
 693                         if ((c == 0x00) && (first_set == -1)) {
 694                                 i += 7;
 695                                 continue;
 696                         }
 697                 }
 698                 if (ext2fs_test_bit(i, in)) {
 699                         if (first_set == -1)
 700                                 first_set = i;
 701                         continue;
 702                 }
 703                 if (first_set == -1)
 704                         continue;
 705
 706                 rb_insert_extent(start + first_set - bitmap->start,
 707                                  i - first_set, bp);
 708                 first_set = -1;
 709         }
 710         if (first_set != -1)
 711                 rb_insert_extent(start + first_set - bitmap->start,
 712                                  num - first_set, bp);
 713
 714         return 0;
 715 }
 716
 717 static errcode_t rb_get_bmap_range(ext2fs_generic_bitmap bitmap,
 718                                      __u64 start, size_t num, void *out)
 719 {
 720
 721         struct rb_node *parent = NULL, *next, **n;
 722         struct ext2fs_rb_private *bp;
 723         struct bmap_rb_extent *ext;
 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                 if (pos < start)
 752                         pos = start;
 753
 754                 while (pos < (ext->start + ext->count)) {
 755                         if ((pos - start) >= num)
 756                                 return 0;
 757                         ext2fs_fast_set_bit64((pos - start), out);
 758                         pos++;
 759                 }
 760         }
 761         return 0;
 762 }
 763
 764 static void rb_clear_bmap(ext2fs_generic_bitmap bitmap)
 765 {
 766         struct ext2fs_rb_private *bp;
 767
 768         bp = (struct ext2fs_rb_private *) bitmap->private;
 769
 770         rb_free_tree(&bp->root);
 771         bp->rcursor = NULL;
 772         bp->rcursor_next = NULL;
 773         bp->wcursor = NULL;
 774 }
 775
 776 #ifdef BMAP_STATS
 777 static void rb_print_stats(ext2fs_generic_bitmap bitmap)
 778 {
 779         struct ext2fs_rb_private *bp;
 780         struct rb_node *node = NULL;
 781         struct bmap_rb_extent *ext;
 782         __u64 count = 0;
 783         __u64 max_size = 0;
 784         __u64 min_size = ULONG_MAX;
 785         __u64 size = 0, avg_size = 0;
 786         double eff;
 787 #ifdef BMAP_STATS_OPS
 788         __u64 mark_all, test_all;
 789         double m_hit = 0.0, t_hit = 0.0;
 790 #endif
 791
 792         bp = (struct ext2fs_rb_private *) bitmap->private;
 793
 794         node = ext2fs_rb_first(&bp->root);
 795         for (node = ext2fs_rb_first(&bp->root); node != NULL;
 796              node = ext2fs_rb_next(node)) {
 797                 ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
 798                 count++;
 799                 if (ext->count > max_size)
 800                         max_size = ext->count;
 801                 if (ext->count < min_size)
 802                         min_size = ext->count;
 803                 size += ext->count;
 804         }
 805
 806         if (count)
 807                 avg_size = size / count;
 808         if (min_size == ULONG_MAX)
 809                 min_size = 0;
 810         eff = (double)((count * sizeof(struct bmap_rb_extent)) << 3) /
 811               (bitmap->real_end - bitmap->start);
 812 #ifdef BMAP_STATS_OPS
 813         mark_all = bitmap->stats.mark_count + bitmap->stats.mark_ext_count;
 814         test_all = bitmap->stats.test_count + bitmap->stats.test_ext_count;
 815         if (mark_all)
 816                 m_hit = ((double)bp->mark_hit / mark_all) * 100;
 817         if (test_all)
 818                 t_hit = ((double)bp->test_hit / test_all) * 100;
 819
 820         fprintf(stderr, "%16llu cache hits on test (%.2f%%)\n"
 821                 "%16llu cache hits on mark (%.2f%%)\n",
 822                 bp->test_hit, t_hit, bp->mark_hit, m_hit);
 823 #endif
 824         fprintf(stderr, "%16llu extents (%llu bytes)\n",
 825                 count, ((count * sizeof(struct bmap_rb_extent)) +
 826                         sizeof(struct ext2fs_rb_private)));
 827         fprintf(stderr, "%16llu bits minimum size\n",
 828                 min_size);
 829         fprintf(stderr, "%16llu bits maximum size\n"
 830                 "%16llu bits average size\n",
 831                 max_size, avg_size);
 832         fprintf(stderr, "%16llu bits set in bitmap (out of %llu)\n", size,
 833                 bitmap->real_end - bitmap->start);
 834         fprintf(stderr,
 835                 "%16.4lf memory / bitmap bit memory ratio (bitarray = 1)\n",
 836                 eff);
 837 }
 838 #else
 839 static void rb_print_stats(ext2fs_generic_bitmap bitmap){}
 840 #endif
 841
 842 struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = {
 843         .type = EXT2FS_BMAP64_RBTREE,
 844         .new_bmap = rb_new_bmap,
 845         .free_bmap = rb_free_bmap,
 846         .copy_bmap = rb_copy_bmap,
 847         .resize_bmap = rb_resize_bmap,
 848         .mark_bmap = rb_mark_bmap,
 849         .unmark_bmap = rb_unmark_bmap,
 850         .test_bmap = rb_test_bmap,
 851         .test_clear_bmap_extent = rb_test_clear_bmap_extent,
 852         .mark_bmap_extent = rb_mark_bmap_extent,
 853         .unmark_bmap_extent = rb_unmark_bmap_extent,
 854         .set_bmap_range = rb_set_bmap_range,
 855         .get_bmap_range = rb_get_bmap_range,
 856         .clear_bmap = rb_clear_bmap,
 857         .print_stats = rb_print_stats,
 858 };