lib/ext2fs/gen_bitmap64.c

   1 /*
   2  * gen_bitmap64.c --- routines to read, write, and manipulate the new qinode and
   3  * block bitmaps.
   4  *
   5  * Copyright (C) 2007, 2008 Theodore Ts'o.
   6  *
   7  * %Begin-Header%
   8  * This file may be redistributed under the terms of the GNU Public
   9  * License.
  10  * %End-Header%
  11  */
  12
  13 #include "config.h"
  14 #include <stdio.h>
  15 #include <string.h>
  16 #if HAVE_UNISTD_H
  17 #include <unistd.h>
  18 #endif
  19 #include <fcntl.h>
  20 #include <time.h>
  21 #include <errno.h>
  22 #if HAVE_SYS_STAT_H
  23 #include <sys/stat.h>
  24 #endif
  25 #if HAVE_SYS_TYPES_H
  26 #include <sys/types.h>
  27 #endif
  28 #ifdef HAVE_SYS_TIME_H
  29 #include <sys/time.h>
  30 #endif
  31
  32 #include "ext2_fs.h"
  33 #include "ext2fsP.h"
  34 #include "bmap64.h"
  35
  36 /*
  37  * Design of 64-bit bitmaps
  38  *
  39  * In order maintain ABI compatibility with programs that don't
  40  * understand about 64-bit blocks/inodes,
  41  * ext2fs_allocate_inode_bitmap() and ext2fs_allocate_block_bitmap()
  42  * will create old-style bitmaps unless the application passes the
  43  * flag EXT2_FLAG_64BITS to ext2fs_open().  If this flag is
  44  * passed, then we know the application has been recompiled, so we can
  45  * use the new-style bitmaps.  If it is not passed, we have to return
  46  * an error if trying to open a filesystem which needs 64-bit bitmaps.
  47  *
  48  * The new bitmaps use a new set of structure magic numbers, so that
  49  * both the old-style and new-style interfaces can identify which
  50  * version of the data structure was used.  Both the old-style and
  51  * new-style interfaces will support either type of bitmap, although
  52  * of course 64-bit operation will only be possible when both the
  53  * new-style interface and the new-style bitmap are used.
  54  *
  55  * For example, the new bitmap interfaces will check the structure
  56  * magic numbers and so will be able to detect old-stype bitmap.  If
  57  * they see an old-style bitmap, they will pass it to the gen_bitmap.c
  58  * functions for handling.  The same will be true for the old
  59  * interfaces as well.
  60  *
  61  * The new-style interfaces will have several different back-end
  62  * implementations, so we can support different encodings that are
  63  * appropriate for different applications.  In general the default
  64  * should be whatever makes sense, and what the application/library
  65  * will use.  However, e2fsck may need specialized implementations for
  66  * its own uses.  For example, when doing parent directory pointer
  67  * loop detections in pass 3, the bitmap will *always* be sparse, so
  68  * e2fsck can request an encoding which is optimized for that.
  69  */
  70
  71 static void warn_bitmap(ext2fs_generic_bitmap_64 bitmap,
  72                         int code, __u64 arg)
  73 {
  74 #ifndef OMIT_COM_ERR
  75         if (bitmap->description)
  76                 com_err(0, bitmap->base_error_code+code,
  77                         "#%llu for %s", arg, bitmap->description);
  78         else
  79                 com_err(0, bitmap->base_error_code + code, "#%llu", arg);
  80 #endif
  81 }
  82
  83 #ifdef ENABLE_BMAP_STATS_OPS
  84 #define INC_STAT(map, name) map->stats.name
  85 #else
  86 #define INC_STAT(map, name) ;;
  87 #endif
  88
  89
  90 errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
  91                                     int type, __u64 start, __u64 end,
  92                                     __u64 real_end,
  93                                     const char *descr,
  94                                     ext2fs_generic_bitmap *ret)
  95 {
  96         ext2fs_generic_bitmap_64 bitmap;
  97         struct ext2_bitmap_ops  *ops;
  98         ext2_ino_t num_dirs;
  99         errcode_t retval;
 100
 101         if (!type)
 102                 type = EXT2FS_BMAP64_BITARRAY;
 103
 104         switch (type) {
 105         case EXT2FS_BMAP64_BITARRAY:
 106                 ops = &ext2fs_blkmap64_bitarray;
 107                 break;
 108         case EXT2FS_BMAP64_RBTREE:
 109                 ops = &ext2fs_blkmap64_rbtree;
 110                 break;
 111         case EXT2FS_BMAP64_AUTODIR:
 112                 retval = ext2fs_get_num_dirs(fs, &num_dirs);
 113                 if (retval || num_dirs > (fs->super->s_inodes_count / 320))
 114                         ops = &ext2fs_blkmap64_bitarray;
 115                 else
 116                         ops = &ext2fs_blkmap64_rbtree;
 117                 break;
 118         default:
 119                 return EINVAL;
 120         }
 121
 122         retval = ext2fs_get_memzero(sizeof(struct ext2fs_struct_generic_bitmap_64),
 123                                     &bitmap);
 124         if (retval)
 125                 return retval;
 126
 127 #ifdef ENABLE_BMAP_STATS
 128         if (gettimeofday(&bitmap->stats.created,
 129                          (struct timezone *) NULL) == -1) {
 130                 perror("gettimeofday");
 131                 ext2fs_free_mem(&bitmap);
 132                 return 1;
 133         }
 134         bitmap->stats.type = type;
 135 #endif
 136
 137         /* XXX factor out, repeated in copy_bmap */
 138         bitmap->magic = magic;
 139         bitmap->fs = fs;
 140         bitmap->start = start;
 141         bitmap->end = end;
 142         bitmap->real_end = real_end;
 143         bitmap->bitmap_ops = ops;
 144         bitmap->cluster_bits = 0;
 145         switch (magic) {
 146         case EXT2_ET_MAGIC_INODE_BITMAP64:
 147                 bitmap->base_error_code = EXT2_ET_BAD_INODE_MARK;
 148                 break;
 149         case EXT2_ET_MAGIC_BLOCK_BITMAP64:
 150                 bitmap->base_error_code = EXT2_ET_BAD_BLOCK_MARK;
 151                 bitmap->cluster_bits = fs->cluster_ratio_bits;
 152                 break;
 153         default:
 154                 bitmap->base_error_code = EXT2_ET_BAD_GENERIC_MARK;
 155         }
 156         if (descr) {
 157                 retval = ext2fs_get_mem(strlen(descr)+1, &bitmap->description);
 158                 if (retval) {
 159                         ext2fs_free_mem(&bitmap);
 160                         return retval;
 161                 }
 162                 strcpy(bitmap->description, descr);
 163         } else
 164                 bitmap->description = 0;
 165
 166         retval = bitmap->bitmap_ops->new_bmap(fs, bitmap);
 167         if (retval) {
 168                 ext2fs_free_mem(&bitmap->description);
 169                 ext2fs_free_mem(&bitmap);
 170                 return retval;
 171         }
 172
 173         *ret = (ext2fs_generic_bitmap) bitmap;
 174         return 0;
 175 }
 176
 177 #ifdef ENABLE_BMAP_STATS
 178 static void ext2fs_print_bmap_statistics(ext2fs_generic_bitmap_64 bitmap)
 179 {
 180         struct ext2_bmap_statistics *stats = &bitmap->stats;
 181 #ifdef ENABLE_BMAP_STATS_OPS
 182         float mark_seq_perc = 0.0, test_seq_perc = 0.0;
 183         float mark_back_perc = 0.0, test_back_perc = 0.0;
 184 #endif
 185         double inuse;
 186         struct timeval now;
 187
 188 #ifdef ENABLE_BMAP_STATS_OPS
 189         if (stats->test_count) {
 190                 test_seq_perc = ((float)stats->test_seq /
 191                                  stats->test_count) * 100;
 192                 test_back_perc = ((float)stats->test_back /
 193                                   stats->test_count) * 100;
 194         }
 195
 196         if (stats->mark_count) {
 197                 mark_seq_perc = ((float)stats->mark_seq /
 198                                  stats->mark_count) * 100;
 199                 mark_back_perc = ((float)stats->mark_back /
 200                                   stats->mark_count) * 100;
 201         }
 202 #endif
 203
 204         if (gettimeofday(&now, (struct timezone *) NULL) == -1) {
 205                 perror("gettimeofday");
 206                 return;
 207         }
 208
 209         inuse = (double) now.tv_sec + \
 210                 (((double) now.tv_usec) * 0.000001);
 211         inuse -= (double) stats->created.tv_sec + \
 212                 (((double) stats->created.tv_usec) * 0.000001);
 213
 214         fprintf(stderr, "\n[+] %s bitmap (type %d)\n", bitmap->description,
 215                 stats->type);
 216         fprintf(stderr, "=================================================\n");
 217 #ifdef ENABLE_BMAP_STATS_OPS
 218         fprintf(stderr, "%16llu bits long\n",
 219                 bitmap->real_end - bitmap->start);
 220         fprintf(stderr, "%16lu copy_bmap\n%16lu resize_bmap\n",
 221                 stats->copy_count, stats->resize_count);
 222         fprintf(stderr, "%16lu mark bmap\n%16lu unmark_bmap\n",
 223                 stats->mark_count, stats->unmark_count);
 224         fprintf(stderr, "%16lu test_bmap\n%16lu mark_bmap_extent\n",
 225                 stats->test_count, stats->mark_ext_count);
 226         fprintf(stderr, "%16lu unmark_bmap_extent\n"
 227                 "%16lu test_clear_bmap_extent\n",
 228                 stats->unmark_ext_count, stats->test_ext_count);
 229         fprintf(stderr, "%16lu set_bmap_range\n%16lu set_bmap_range\n",
 230                 stats->set_range_count, stats->get_range_count);
 231         fprintf(stderr, "%16lu clear_bmap\n%16lu contiguous bit test (%.2f%%)\n",
 232                 stats->clear_count, stats->test_seq, test_seq_perc);
 233         fprintf(stderr, "%16lu contiguous bit mark (%.2f%%)\n"
 234                 "%16llu bits tested backwards (%.2f%%)\n",
 235                 stats->mark_seq, mark_seq_perc,
 236                 stats->test_back, test_back_perc);
 237         fprintf(stderr, "%16llu bits marked backwards (%.2f%%)\n"
 238                 "%16.2f seconds in use\n",
 239                 stats->mark_back, mark_back_perc, inuse);
 240 #endif /* ENABLE_BMAP_STATS_OPS */
 241 }
 242 #endif
 243
 244 void ext2fs_free_generic_bmap(ext2fs_generic_bitmap gen_bmap)
 245 {
 246         ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
 247
 248         if (!bmap)
 249                 return;
 250
 251         if (EXT2FS_IS_32_BITMAP(bmap)) {
 252                 ext2fs_free_generic_bitmap(gen_bmap);
 253                 return;
 254         }
 255
 256         if (!EXT2FS_IS_64_BITMAP(bmap))
 257                 return;
 258
 259 #ifdef ENABLE_BMAP_STATS
 260         if (getenv("E2FSPROGS_BITMAP_STATS")) {
 261                 ext2fs_print_bmap_statistics(bmap);
 262                 bmap->bitmap_ops->print_stats(bmap);
 263         }
 264 #endif
 265
 266         bmap->bitmap_ops->free_bmap(bmap);
 267
 268         if (bmap->description) {
 269                 ext2fs_free_mem(&bmap->description);
 270                 bmap->description = 0;
 271         }
 272         bmap->magic = 0;
 273         ext2fs_free_mem(&bmap);
 274 }
 275
 276 errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap gen_src,
 277                                    ext2fs_generic_bitmap *dest)
 278 {
 279         ext2fs_generic_bitmap_64 src = (ext2fs_generic_bitmap_64) gen_src;
 280         char *descr, *new_descr;
 281         ext2fs_generic_bitmap_64 new_bmap;
 282         errcode_t retval;
 283
 284         if (!src)
 285                 return EINVAL;
 286
 287         if (EXT2FS_IS_32_BITMAP(src))
 288                 return ext2fs_copy_generic_bitmap(gen_src, dest);
 289
 290         if (!EXT2FS_IS_64_BITMAP(src))
 291                 return EINVAL;
 292
 293         /* Allocate a new bitmap struct */
 294         retval = ext2fs_get_memzero(sizeof(struct ext2fs_struct_generic_bitmap_64),
 295                                     &new_bmap);
 296         if (retval)
 297                 return retval;
 298
 299
 300 #ifdef ENABLE_BMAP_STATS_OPS
 301         src->stats.copy_count++;
 302 #endif
 303 #ifdef ENABLE_BMAP_STATS
 304         if (gettimeofday(&new_bmap->stats.created,
 305                          (struct timezone *) NULL) == -1) {
 306                 perror("gettimeofday");
 307                 ext2fs_free_mem(&new_bmap);
 308                 return 1;
 309         }
 310         new_bmap->stats.type = src->stats.type;
 311 #endif
 312
 313         /* Copy all the high-level parts over */
 314         new_bmap->magic = src->magic;
 315         new_bmap->fs = src->fs;
 316         new_bmap->start = src->start;
 317         new_bmap->end = src->end;
 318         new_bmap->real_end = src->real_end;
 319         new_bmap->bitmap_ops = src->bitmap_ops;
 320         new_bmap->base_error_code = src->base_error_code;
 321         new_bmap->cluster_bits = src->cluster_bits;
 322
 323         descr = src->description;
 324         if (descr) {
 325                 retval = ext2fs_get_mem(strlen(descr)+10, &new_descr);
 326                 if (retval) {
 327                         ext2fs_free_mem(&new_bmap);
 328                         return retval;
 329                 }
 330                 strcpy(new_descr, "copy of ");
 331                 strcat(new_descr, descr);
 332                 new_bmap->description = new_descr;
 333         }
 334
 335         retval = src->bitmap_ops->copy_bmap(src, new_bmap);
 336         if (retval) {
 337                 ext2fs_free_mem(&new_bmap->description);
 338                 ext2fs_free_mem(&new_bmap);
 339                 return retval;
 340         }
 341
 342         *dest = (ext2fs_generic_bitmap) new_bmap;
 343
 344         return 0;
 345 }
 346
 347 errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap gen_bmap,
 348                                      __u64 new_end,
 349                                      __u64 new_real_end)
 350 {
 351         ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
 352
 353         if (!bmap)
 354                 return EINVAL;
 355
 356         if (EXT2FS_IS_32_BITMAP(bmap))
 357                 return ext2fs_resize_generic_bitmap(gen_bmap->magic, new_end,
 358                                                     new_real_end, gen_bmap);
 359
 360         if (!EXT2FS_IS_64_BITMAP(bmap))
 361                 return EINVAL;
 362
 363         INC_STAT(bmap, resize_count);
 364
 365         return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end);
 366 }
 367
 368 errcode_t ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap gen_bitmap,
 369                                         errcode_t neq,
 370                                         __u64 end, __u64 *oend)
 371 {
 372         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
 373
 374         if (!bitmap)
 375                 return EINVAL;
 376
 377         if (EXT2FS_IS_32_BITMAP(bitmap)) {
 378                 ext2_ino_t tmp_oend;
 379                 int retval;
 380
 381                 retval = ext2fs_fudge_generic_bitmap_end(gen_bitmap,
 382                                                          bitmap->magic,
 383                                                          neq, end, &tmp_oend);
 384                 if (oend)
 385                         *oend = tmp_oend;
 386                 return retval;
 387         }
 388
 389         if (!EXT2FS_IS_64_BITMAP(bitmap))
 390                 return EINVAL;
 391
 392         if (end > bitmap->real_end)
 393                 return neq;
 394         if (oend)
 395                 *oend = bitmap->end;
 396         bitmap->end = end;
 397         return 0;
 398 }
 399
 400 __u64 ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap gen_bitmap)
 401 {
 402         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
 403
 404         if (!bitmap)
 405                 return EINVAL;
 406
 407         if (EXT2FS_IS_32_BITMAP(bitmap))
 408                 return ext2fs_get_generic_bitmap_start(gen_bitmap);
 409
 410         if (!EXT2FS_IS_64_BITMAP(bitmap))
 411                 return EINVAL;
 412
 413         return bitmap->start;
 414 }
 415
 416 __u64 ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap gen_bitmap)
 417 {
 418         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
 419
 420         if (!bitmap)
 421                 return EINVAL;
 422
 423         if (EXT2FS_IS_32_BITMAP(bitmap))
 424                 return ext2fs_get_generic_bitmap_end(gen_bitmap);
 425
 426         if (!EXT2FS_IS_64_BITMAP(bitmap))
 427                 return EINVAL;
 428
 429         return bitmap->end;
 430 }
 431
 432 void ext2fs_clear_generic_bmap(ext2fs_generic_bitmap gen_bitmap)
 433 {
 434         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
 435
 436         if (EXT2FS_IS_32_BITMAP(bitmap))
 437                 ext2fs_clear_generic_bitmap(gen_bitmap);
 438         else
 439                 bitmap->bitmap_ops->clear_bmap(bitmap);
 440 }
 441
 442 int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap gen_bitmap,
 443                              __u64 arg)
 444 {
 445         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
 446
 447         if (!bitmap)
 448                 return 0;
 449
 450         if (EXT2FS_IS_32_BITMAP(bitmap)) {
 451                 if (arg & ~0xffffffffULL) {
 452                         ext2fs_warn_bitmap2(gen_bitmap,
 453                                             EXT2FS_MARK_ERROR, 0xffffffff);
 454                         return 0;
 455                 }
 456                 return ext2fs_mark_generic_bitmap(gen_bitmap, arg);
 457         }
 458
 459         if (!EXT2FS_IS_64_BITMAP(bitmap))
 460                 return 0;
 461
 462         arg >>= bitmap->cluster_bits;
 463
 464 #ifdef ENABLE_BMAP_STATS_OPS
 465         if (arg == bitmap->stats.last_marked + 1)
 466                 bitmap->stats.mark_seq++;
 467         if (arg < bitmap->stats.last_marked)
 468                 bitmap->stats.mark_back++;
 469         bitmap->stats.last_marked = arg;
 470         bitmap->stats.mark_count++;
 471 #endif
 472
 473         if ((arg < bitmap->start) || (arg > bitmap->end)) {
 474                 warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg);
 475                 return 0;
 476         }
 477
 478         return bitmap->bitmap_ops->mark_bmap(bitmap, arg);
 479 }
 480
 481 int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap gen_bitmap,
 482                                __u64 arg)
 483 {
 484         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
 485
 486         if (!bitmap)
 487                 return 0;
 488
 489         if (EXT2FS_IS_32_BITMAP(bitmap)) {
 490                 if (arg & ~0xffffffffULL) {
 491                         ext2fs_warn_bitmap2(gen_bitmap, EXT2FS_UNMARK_ERROR,
 492                                             0xffffffff);
 493                         return 0;
 494                 }
 495                 return ext2fs_unmark_generic_bitmap(gen_bitmap, arg);
 496         }
 497
 498         if (!EXT2FS_IS_64_BITMAP(bitmap))
 499                 return 0;
 500
 501         arg >>= bitmap->cluster_bits;
 502
 503         INC_STAT(bitmap, unmark_count);
 504
 505         if ((arg < bitmap->start) || (arg > bitmap->end)) {
 506                 warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg);
 507                 return 0;
 508         }
 509
 510         return bitmap->bitmap_ops->unmark_bmap(bitmap, arg);
 511 }
 512
 513 int ext2fs_test_generic_bmap(ext2fs_generic_bitmap gen_bitmap,
 514                              __u64 arg)
 515 {
 516         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
 517         if (!bitmap)
 518                 return 0;
 519
 520         if (EXT2FS_IS_32_BITMAP(bitmap)) {
 521                 if (arg & ~0xffffffffULL) {
 522                         ext2fs_warn_bitmap2(gen_bitmap, EXT2FS_TEST_ERROR,
 523                                             0xffffffff);
 524                         return 0;
 525                 }
 526                 return ext2fs_test_generic_bitmap(gen_bitmap, arg);
 527         }
 528
 529         if (!EXT2FS_IS_64_BITMAP(bitmap))
 530                 return 0;
 531
 532         arg >>= bitmap->cluster_bits;
 533
 534 #ifdef ENABLE_BMAP_STATS_OPS
 535         bitmap->stats.test_count++;
 536         if (arg == bitmap->stats.last_tested + 1)
 537                 bitmap->stats.test_seq++;
 538         if (arg < bitmap->stats.last_tested)
 539                 bitmap->stats.test_back++;
 540         bitmap->stats.last_tested = arg;
 541 #endif
 542
 543         if ((arg < bitmap->start) || (arg > bitmap->end)) {
 544                 warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg);
 545                 return 0;
 546         }
 547
 548         return bitmap->bitmap_ops->test_bmap(bitmap, arg);
 549 }
 550
 551 errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap gen_bmap,
 552                                         __u64 start, unsigned int num,
 553                                         void *in)
 554 {
 555         ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
 556
 557         if (!bmap)
 558                 return EINVAL;
 559
 560         if (EXT2FS_IS_32_BITMAP(bmap)) {
 561                 if ((start+num-1) & ~0xffffffffULL) {
 562                         ext2fs_warn_bitmap2(gen_bmap, EXT2FS_UNMARK_ERROR,
 563                                             0xffffffff);
 564                         return EINVAL;
 565                 }
 566                 return ext2fs_set_generic_bitmap_range(gen_bmap, bmap->magic,
 567                                                        start, num, in);
 568         }
 569
 570         if (!EXT2FS_IS_64_BITMAP(bmap))
 571                 return EINVAL;
 572
 573         INC_STAT(bmap, set_range_count);
 574
 575         return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in);
 576 }
 577
 578 errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap gen_bmap,
 579                                         __u64 start, unsigned int num,
 580                                         void *out)
 581 {
 582         ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
 583
 584         if (!bmap)
 585                 return EINVAL;
 586
 587         if (EXT2FS_IS_32_BITMAP(bmap)) {
 588                 if ((start+num-1) & ~0xffffffffULL) {
 589                         ext2fs_warn_bitmap2(gen_bmap,
 590                                             EXT2FS_UNMARK_ERROR, 0xffffffff);
 591                         return EINVAL;
 592                 }
 593                 return ext2fs_get_generic_bitmap_range(gen_bmap, bmap->magic,
 594                                                        start, num, out);
 595         }
 596
 597         if (!EXT2FS_IS_64_BITMAP(bmap))
 598                 return EINVAL;
 599
 600         INC_STAT(bmap, get_range_count);
 601
 602         return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out);
 603 }
 604
 605 errcode_t ext2fs_compare_generic_bmap(errcode_t neq,
 606                                       ext2fs_generic_bitmap gen_bm1,
 607                                       ext2fs_generic_bitmap gen_bm2)
 608 {
 609         ext2fs_generic_bitmap_64 bm1 = (ext2fs_generic_bitmap_64) gen_bm1;
 610         ext2fs_generic_bitmap_64 bm2 = (ext2fs_generic_bitmap_64) gen_bm2;
 611         blk64_t i;
 612
 613         if (!bm1 || !bm2)
 614                 return EINVAL;
 615         if (bm1->magic != bm2->magic)
 616                 return EINVAL;
 617
 618         /* Now we know both bitmaps have the same magic */
 619         if (EXT2FS_IS_32_BITMAP(bm1))
 620                 return ext2fs_compare_generic_bitmap(bm1->magic, neq,
 621                                                      gen_bm1, gen_bm2);
 622
 623         if (!EXT2FS_IS_64_BITMAP(bm1))
 624                 return EINVAL;
 625
 626         if ((bm1->start != bm2->start) ||
 627             (bm1->end != bm2->end))
 628                 return neq;
 629
 630         for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++)
 631                 if (ext2fs_test_generic_bmap(gen_bm1, i) !=
 632                     ext2fs_test_generic_bmap(gen_bm2, i))
 633                         return neq;
 634
 635         return 0;
 636 }
 637
 638 void ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap gen_bmap)
 639 {
 640         ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
 641         __u64   start, num;
 642
 643         if (EXT2FS_IS_32_BITMAP(bmap)) {
 644                 ext2fs_set_generic_bitmap_padding(gen_bmap);
 645                 return;
 646         }
 647
 648         start = bmap->end + 1;
 649         num = bmap->real_end - bmap->end;
 650         bmap->bitmap_ops->mark_bmap_extent(bmap, start, num);
 651         /* XXX ought to warn on error */
 652 }
 653
 654 int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,
 655                                     blk64_t block, unsigned int num)
 656 {
 657         ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
 658         __u64   end = block + num;
 659
 660         if (!bmap)
 661                 return EINVAL;
 662
 663         if (num == 1)
 664                 return !ext2fs_test_generic_bmap((ext2fs_generic_bitmap)
 665                                                  bmap, block);
 666
 667         if (EXT2FS_IS_32_BITMAP(bmap)) {
 668                 if ((block & ~0xffffffffULL) ||
 669                     ((block+num-1) & ~0xffffffffULL)) {
 670                         ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
 671                                             EXT2FS_UNMARK_ERROR, 0xffffffff);
 672                         return EINVAL;
 673                 }
 674                 return ext2fs_test_block_bitmap_range(
 675                         (ext2fs_generic_bitmap) bmap, block, num);
 676         }
 677
 678         if (!EXT2FS_IS_64_BITMAP(bmap))
 679                 return EINVAL;
 680
 681         INC_STAT(bmap, test_ext_count);
 682
 683         /* convert to clusters if necessary */
 684         block >>= bmap->cluster_bits;
 685         end += (1 << bmap->cluster_bits) - 1;
 686         end >>= bmap->cluster_bits;
 687         num = end - block;
 688
 689         if ((block < bmap->start) || (block > bmap->end) ||
 690             (block+num-1 > bmap->end)) {
 691                 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST, block,
 692                                    bmap->description);
 693                 return EINVAL;
 694         }
 695
 696         return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num);
 697 }
 698
 699 void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,
 700                                      blk64_t block, unsigned int num)
 701 {
 702         ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
 703         __u64   end = block + num;
 704
 705         if (!bmap)
 706                 return;
 707
 708         if (EXT2FS_IS_32_BITMAP(bmap)) {
 709                 if ((block & ~0xffffffffULL) ||
 710                     ((block+num-1) & ~0xffffffffULL)) {
 711                         ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
 712                                             EXT2FS_UNMARK_ERROR, 0xffffffff);
 713                         return;
 714                 }
 715                 ext2fs_mark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
 716                                                block, num);
 717         }
 718
 719         if (!EXT2FS_IS_64_BITMAP(bmap))
 720                 return;
 721
 722         INC_STAT(bmap, mark_ext_count);
 723
 724         /* convert to clusters if necessary */
 725         block >>= bmap->cluster_bits;
 726         end += (1 << bmap->cluster_bits) - 1;
 727         end >>= bmap->cluster_bits;
 728         num = end - block;
 729
 730         if ((block < bmap->start) || (block > bmap->end) ||
 731             (block+num-1 > bmap->end)) {
 732                 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
 733                                    bmap->description);
 734                 return;
 735         }
 736
 737         bmap->bitmap_ops->mark_bmap_extent(bmap, block, num);
 738 }
 739
 740 void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,
 741                                        blk64_t block, unsigned int num)
 742 {
 743         ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
 744         __u64   end = block + num;
 745
 746         if (!bmap)
 747                 return;
 748
 749         if (EXT2FS_IS_32_BITMAP(bmap)) {
 750                 if ((block & ~0xffffffffULL) ||
 751                     ((block+num-1) & ~0xffffffffULL)) {
 752                         ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
 753                                             EXT2FS_UNMARK_ERROR, 0xffffffff);
 754                         return;
 755                 }
 756                 ext2fs_unmark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
 757                                                  block, num);
 758         }
 759
 760         if (!EXT2FS_IS_64_BITMAP(bmap))
 761                 return;
 762
 763         INC_STAT(bmap, unmark_ext_count);
 764
 765         /* convert to clusters if necessary */
 766         block >>= bmap->cluster_bits;
 767         end += (1 << bmap->cluster_bits) - 1;
 768         end >>= bmap->cluster_bits;
 769         num = end - block;
 770
 771         if ((block < bmap->start) || (block > bmap->end) ||
 772             (block+num-1 > bmap->end)) {
 773                 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
 774                                    bmap->description);
 775                 return;
 776         }
 777
 778         bmap->bitmap_ops->unmark_bmap_extent(bmap, block, num);
 779 }
 780
 781 void ext2fs_warn_bitmap32(ext2fs_generic_bitmap gen_bitmap, const char *func)
 782 {
 783         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
 784
 785 #ifndef OMIT_COM_ERR
 786         if (bitmap && bitmap->description)
 787                 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
 788                         "called %s with 64-bit bitmap for %s", func,
 789                         bitmap->description);
 790         else
 791                 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
 792                         "called %s with 64-bit bitmap", func);
 793 #endif
 794 }
 795
 796 errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs,
 797                                            ext2fs_block_bitmap *bitmap)
 798 {
 799         ext2fs_generic_bitmap_64 bmap, cmap;
 800         ext2fs_block_bitmap     gen_bmap = *bitmap, gen_cmap;
 801         errcode_t               retval;
 802         blk64_t                 i, next, b_end, c_end;
 803
 804         bmap = (ext2fs_generic_bitmap_64) gen_bmap;
 805         if (fs->cluster_ratio_bits == ext2fs_get_bitmap_granularity(gen_bmap))
 806                 return 0;       /* Nothing to do */
 807
 808         retval = ext2fs_allocate_block_bitmap(fs, "converted cluster bitmap",
 809                                               &gen_cmap);
 810         if (retval)
 811                 return retval;
 812
 813         cmap = (ext2fs_generic_bitmap_64) gen_cmap;
 814         i = bmap->start;
 815         b_end = bmap->end;
 816         bmap->end = bmap->real_end;
 817         c_end = cmap->end;
 818         cmap->end = cmap->real_end;
 819         while (i < bmap->real_end) {
 820                 retval = ext2fs_find_first_set_block_bitmap2(gen_bmap,
 821                                                 i, bmap->real_end, &next);
 822                 if (retval)
 823                         break;
 824                 ext2fs_mark_block_bitmap2(gen_cmap, next);
 825                 i = EXT2FS_C2B(fs, EXT2FS_B2C(fs, next) + 1);
 826         }
 827         bmap->end = b_end;
 828         cmap->end = c_end;
 829         ext2fs_free_block_bitmap(gen_bmap);
 830         *bitmap = (ext2fs_block_bitmap) cmap;
 831         return 0;
 832 }
 833
 834 errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
 835                                               __u64 start, __u64 end, __u64 *out)
 836 {
 837         ext2fs_generic_bitmap_64 bmap64 = (ext2fs_generic_bitmap_64) bitmap;
 838         __u64 cstart, cend, cout;
 839         errcode_t retval;
 840
 841         if (!bitmap)
 842                 return EINVAL;
 843
 844         if (EXT2FS_IS_32_BITMAP(bitmap)) {
 845                 blk_t blk = 0;
 846
 847                 if (((start) & ~0xffffffffULL) ||
 848                     ((end) & ~0xffffffffULL)) {
 849                         ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
 850                         return EINVAL;
 851                 }
 852
 853                 retval = ext2fs_find_first_zero_generic_bitmap(bitmap, start,
 854                                                                end, &blk);
 855                 if (retval == 0)
 856                         *out = blk;
 857                 return retval;
 858         }
 859
 860         if (!EXT2FS_IS_64_BITMAP(bitmap))
 861                 return EINVAL;
 862
 863         cstart = start >> bmap64->cluster_bits;
 864         cend = end >> bmap64->cluster_bits;
 865
 866         if (cstart < bmap64->start || cend > bmap64->end || start > end) {
 867                 warn_bitmap(bmap64, EXT2FS_TEST_ERROR, start);
 868                 return EINVAL;
 869         }
 870
 871         if (bmap64->bitmap_ops->find_first_zero) {
 872                 retval = bmap64->bitmap_ops->find_first_zero(bmap64, cstart,
 873                                                              cend, &cout);
 874                 if (retval)
 875                         return retval;
 876         found:
 877                 cout <<= bmap64->cluster_bits;
 878                 *out = (cout >= start) ? cout : start;
 879                 return 0;
 880         }
 881
 882         for (cout = cstart; cout <= cend; cout++)
 883                 if (!bmap64->bitmap_ops->test_bmap(bmap64, cout))
 884                         goto found;
 885
 886         return ENOENT;
 887 }
 888
 889 errcode_t ext2fs_find_first_set_generic_bmap(ext2fs_generic_bitmap bitmap,
 890                                              __u64 start, __u64 end, __u64 *out)
 891 {
 892         ext2fs_generic_bitmap_64 bmap64 = (ext2fs_generic_bitmap_64) bitmap;
 893         __u64 cstart, cend, cout;
 894         errcode_t retval;
 895
 896         if (!bitmap)
 897                 return EINVAL;
 898
 899         if (EXT2FS_IS_32_BITMAP(bitmap)) {
 900                 blk_t blk = 0;
 901
 902                 if (((start) & ~0xffffffffULL) ||
 903                     ((end) & ~0xffffffffULL)) {
 904                         ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
 905                         return EINVAL;
 906                 }
 907
 908                 retval = ext2fs_find_first_set_generic_bitmap(bitmap, start,
 909                                                               end, &blk);
 910                 if (retval == 0)
 911                         *out = blk;
 912                 return retval;
 913         }
 914
 915         if (!EXT2FS_IS_64_BITMAP(bitmap))
 916                 return EINVAL;
 917
 918         cstart = start >> bmap64->cluster_bits;
 919         cend = end >> bmap64->cluster_bits;
 920
 921         if (cstart < bmap64->start || cend > bmap64->end || start > end) {
 922                 warn_bitmap(bmap64, EXT2FS_TEST_ERROR, start);
 923                 return EINVAL;
 924         }
 925
 926         if (bmap64->bitmap_ops->find_first_set) {
 927                 retval = bmap64->bitmap_ops->find_first_set(bmap64, cstart,
 928                                                             cend, &cout);
 929                 if (retval)
 930                         return retval;
 931         found:
 932                 cout <<= bmap64->cluster_bits;
 933                 *out = (cout >= start) ? cout : start;
 934                 return 0;
 935         }
 936
 937         for (cout = cstart; cout <= cend; cout++)
 938                 if (bmap64->bitmap_ops->test_bmap(bmap64, cout))
 939                         goto found;
 940
 941         return ENOENT;
 942 }
 943
 944 errcode_t ext2fs_count_used_clusters(ext2_filsys fs, blk64_t start,
 945                                      blk64_t end, blk64_t *out)
 946 {
 947         blk64_t         next;
 948         blk64_t         tot_set = 0;
 949         errcode_t       retval;
 950
 951         while (start < end) {
 952                 retval = ext2fs_find_first_set_block_bitmap2(fs->block_map,
 953                                                         start, end, &next);
 954                 if (retval) {
 955                         if (retval == ENOENT)
 956                                 retval = 0;
 957                         break;
 958                 }
 959                 start = next;
 960
 961                 retval = ext2fs_find_first_zero_block_bitmap2(fs->block_map,
 962                                                         start, end, &next);
 963                 if (retval == 0) {
 964                         tot_set += next - start;
 965                         start  = next + 1;
 966                 } else if (retval == ENOENT) {
 967                         retval = 0;
 968                         tot_set += end - start + 1;
 969                         break;
 970                 } else
 971                         break;
 972         }
 973
 974         if (!retval)
 975                 *out = EXT2FS_NUM_B2C(fs, tot_set);
 976         return retval;
 977 }