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