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         struct timeval now;
 187         double inuse;
 188
 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
 203         if (gettimeofday(&now, (struct timezone *) NULL) == -1) {
 204                 perror("gettimeofday");
 205                 return;
 206         }
 207
 208         inuse = (double) now.tv_sec + \
 209                 (((double) now.tv_usec) * 0.000001);
 210         inuse -= (double) stats->created.tv_sec + \
 211                 (((double) stats->created.tv_usec) * 0.000001);
 212 #endif /* ENABLE_BMAP_STATS_OPS */
 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_merge_generic_bmap(ext2fs_generic_bitmap gen_src,
 348                                     ext2fs_generic_bitmap gen_dest,
 349                                     ext2fs_generic_bitmap gen_dup,
 350                                     ext2fs_generic_bitmap gen_dup_allowed)
 351 {
 352         ext2fs_generic_bitmap_64 src = (ext2fs_generic_bitmap_64)gen_src;
 353         ext2fs_generic_bitmap_64 dest = (ext2fs_generic_bitmap_64)gen_dest;
 354         ext2fs_generic_bitmap_64 dup = (ext2fs_generic_bitmap_64)gen_dup;
 355         ext2fs_generic_bitmap_64 dup_allowed = (ext2fs_generic_bitmap_64)gen_dup_allowed;
 356
 357         if (!src || !dest)
 358                 return EINVAL;
 359
 360         if (!EXT2FS_IS_64_BITMAP(src) || !EXT2FS_IS_64_BITMAP(dest) ||
 361             (dup && !EXT2FS_IS_64_BITMAP(dup)) ||
 362                 (dup_allowed && !EXT2FS_IS_64_BITMAP(dup_allowed)))
 363                 return EINVAL;
 364
 365         if (src->bitmap_ops != dest->bitmap_ops ||
 366             (dup && src->bitmap_ops != dup->bitmap_ops) ||
 367             (dup_allowed && src->bitmap_ops != dup_allowed->bitmap_ops))
 368                 return EINVAL;
 369
 370         if (src->bitmap_ops->merge_bmap == NULL)
 371                 return EOPNOTSUPP;
 372
 373         return src->bitmap_ops->merge_bmap(src, dest, dup, dup_allowed);
 374 }
 375
 376 errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap gen_bmap,
 377                                      __u64 new_end,
 378                                      __u64 new_real_end)
 379 {
 380         ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
 381
 382         if (!bmap)
 383                 return EINVAL;
 384
 385         if (EXT2FS_IS_32_BITMAP(bmap))
 386                 return ext2fs_resize_generic_bitmap(gen_bmap->magic, new_end,
 387                                                     new_real_end, gen_bmap);
 388
 389         if (!EXT2FS_IS_64_BITMAP(bmap))
 390                 return EINVAL;
 391
 392         INC_STAT(bmap, resize_count);
 393
 394         return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end);
 395 }
 396
 397 errcode_t ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap gen_bitmap,
 398                                         errcode_t neq,
 399                                         __u64 end, __u64 *oend)
 400 {
 401         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
 402
 403         if (!bitmap)
 404                 return EINVAL;
 405
 406         if (EXT2FS_IS_32_BITMAP(bitmap)) {
 407                 ext2_ino_t tmp_oend;
 408                 int retval;
 409
 410                 retval = ext2fs_fudge_generic_bitmap_end(gen_bitmap,
 411                                                          bitmap->magic,
 412                                                          neq, end, &tmp_oend);
 413                 if (oend)
 414                         *oend = tmp_oend;
 415                 return retval;
 416         }
 417
 418         if (!EXT2FS_IS_64_BITMAP(bitmap))
 419                 return EINVAL;
 420
 421         if (end > bitmap->real_end)
 422                 return neq;
 423         if (oend)
 424                 *oend = bitmap->end;
 425         bitmap->end = end;
 426         return 0;
 427 }
 428
 429 __u64 ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap gen_bitmap)
 430 {
 431         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
 432
 433         if (!bitmap)
 434                 return EINVAL;
 435
 436         if (EXT2FS_IS_32_BITMAP(bitmap))
 437                 return ext2fs_get_generic_bitmap_start(gen_bitmap);
 438
 439         if (!EXT2FS_IS_64_BITMAP(bitmap))
 440                 return EINVAL;
 441
 442         return bitmap->start;
 443 }
 444
 445 __u64 ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap gen_bitmap)
 446 {
 447         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
 448
 449         if (!bitmap)
 450                 return EINVAL;
 451
 452         if (EXT2FS_IS_32_BITMAP(bitmap))
 453                 return ext2fs_get_generic_bitmap_end(gen_bitmap);
 454
 455         if (!EXT2FS_IS_64_BITMAP(bitmap))
 456                 return EINVAL;
 457
 458         return bitmap->end;
 459 }
 460
 461 void ext2fs_clear_generic_bmap(ext2fs_generic_bitmap gen_bitmap)
 462 {
 463         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
 464
 465         if (EXT2FS_IS_32_BITMAP(bitmap))
 466                 ext2fs_clear_generic_bitmap(gen_bitmap);
 467         else
 468                 bitmap->bitmap_ops->clear_bmap(bitmap);
 469 }
 470
 471 int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap gen_bitmap,
 472                              __u64 arg)
 473 {
 474         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
 475
 476         if (!bitmap)
 477                 return 0;
 478
 479         if (EXT2FS_IS_32_BITMAP(bitmap)) {
 480                 if (arg & ~0xffffffffULL) {
 481                         ext2fs_warn_bitmap2(gen_bitmap,
 482                                             EXT2FS_MARK_ERROR, 0xffffffff);
 483                         return 0;
 484                 }
 485                 return ext2fs_mark_generic_bitmap(gen_bitmap, arg);
 486         }
 487
 488         if (!EXT2FS_IS_64_BITMAP(bitmap))
 489                 return 0;
 490
 491         arg >>= bitmap->cluster_bits;
 492
 493 #ifdef ENABLE_BMAP_STATS_OPS
 494         if (arg == bitmap->stats.last_marked + 1)
 495                 bitmap->stats.mark_seq++;
 496         if (arg < bitmap->stats.last_marked)
 497                 bitmap->stats.mark_back++;
 498         bitmap->stats.last_marked = arg;
 499         bitmap->stats.mark_count++;
 500 #endif
 501
 502         if ((arg < bitmap->start) || (arg > bitmap->end)) {
 503                 warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg);
 504                 return 0;
 505         }
 506
 507         return bitmap->bitmap_ops->mark_bmap(bitmap, arg);
 508 }
 509
 510 int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap gen_bitmap,
 511                                __u64 arg)
 512 {
 513         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
 514
 515         if (!bitmap)
 516                 return 0;
 517
 518         if (EXT2FS_IS_32_BITMAP(bitmap)) {
 519                 if (arg & ~0xffffffffULL) {
 520                         ext2fs_warn_bitmap2(gen_bitmap, EXT2FS_UNMARK_ERROR,
 521                                             0xffffffff);
 522                         return 0;
 523                 }
 524                 return ext2fs_unmark_generic_bitmap(gen_bitmap, arg);
 525         }
 526
 527         if (!EXT2FS_IS_64_BITMAP(bitmap))
 528                 return 0;
 529
 530         arg >>= bitmap->cluster_bits;
 531
 532         INC_STAT(bitmap, unmark_count);
 533
 534         if ((arg < bitmap->start) || (arg > bitmap->end)) {
 535                 warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg);
 536                 return 0;
 537         }
 538
 539         return bitmap->bitmap_ops->unmark_bmap(bitmap, arg);
 540 }
 541
 542 int ext2fs_test_generic_bmap(ext2fs_generic_bitmap gen_bitmap,
 543                              __u64 arg)
 544 {
 545         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
 546         if (!bitmap)
 547                 return 0;
 548
 549         if (EXT2FS_IS_32_BITMAP(bitmap)) {
 550                 if (arg & ~0xffffffffULL) {
 551                         ext2fs_warn_bitmap2(gen_bitmap, EXT2FS_TEST_ERROR,
 552                                             0xffffffff);
 553                         return 0;
 554                 }
 555                 return ext2fs_test_generic_bitmap(gen_bitmap, arg);
 556         }
 557
 558         if (!EXT2FS_IS_64_BITMAP(bitmap))
 559                 return 0;
 560
 561         arg >>= bitmap->cluster_bits;
 562
 563 #ifdef ENABLE_BMAP_STATS_OPS
 564         bitmap->stats.test_count++;
 565         if (arg == bitmap->stats.last_tested + 1)
 566                 bitmap->stats.test_seq++;
 567         if (arg < bitmap->stats.last_tested)
 568                 bitmap->stats.test_back++;
 569         bitmap->stats.last_tested = arg;
 570 #endif
 571
 572         if ((arg < bitmap->start) || (arg > bitmap->end)) {
 573                 warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg);
 574                 return 0;
 575         }
 576
 577         return bitmap->bitmap_ops->test_bmap(bitmap, arg);
 578 }
 579
 580 errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap gen_bmap,
 581                                         __u64 start, unsigned int num,
 582                                         void *in)
 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, EXT2FS_UNMARK_ERROR,
 592                                             0xffffffff);
 593                         return EINVAL;
 594                 }
 595                 return ext2fs_set_generic_bitmap_range(gen_bmap, bmap->magic,
 596                                                        start, num, in);
 597         }
 598
 599         if (!EXT2FS_IS_64_BITMAP(bmap))
 600                 return EINVAL;
 601
 602         INC_STAT(bmap, set_range_count);
 603
 604         return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in);
 605 }
 606
 607 errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap gen_bmap,
 608                                         __u64 start, unsigned int num,
 609                                         void *out)
 610 {
 611         ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
 612
 613         if (!bmap)
 614                 return EINVAL;
 615
 616         if (EXT2FS_IS_32_BITMAP(bmap)) {
 617                 if ((start+num-1) & ~0xffffffffULL) {
 618                         ext2fs_warn_bitmap2(gen_bmap,
 619                                             EXT2FS_UNMARK_ERROR, 0xffffffff);
 620                         return EINVAL;
 621                 }
 622                 return ext2fs_get_generic_bitmap_range(gen_bmap, bmap->magic,
 623                                                        start, num, out);
 624         }
 625
 626         if (!EXT2FS_IS_64_BITMAP(bmap))
 627                 return EINVAL;
 628
 629         INC_STAT(bmap, get_range_count);
 630
 631         return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out);
 632 }
 633
 634 errcode_t ext2fs_compare_generic_bmap(errcode_t neq,
 635                                       ext2fs_generic_bitmap gen_bm1,
 636                                       ext2fs_generic_bitmap gen_bm2)
 637 {
 638         ext2fs_generic_bitmap_64 bm1 = (ext2fs_generic_bitmap_64) gen_bm1;
 639         ext2fs_generic_bitmap_64 bm2 = (ext2fs_generic_bitmap_64) gen_bm2;
 640         blk64_t i;
 641
 642         if (!bm1 || !bm2)
 643                 return EINVAL;
 644         if (bm1->magic != bm2->magic)
 645                 return EINVAL;
 646
 647         /* Now we know both bitmaps have the same magic */
 648         if (EXT2FS_IS_32_BITMAP(bm1))
 649                 return ext2fs_compare_generic_bitmap(bm1->magic, neq,
 650                                                      gen_bm1, gen_bm2);
 651
 652         if (!EXT2FS_IS_64_BITMAP(bm1))
 653                 return EINVAL;
 654
 655         if ((bm1->start != bm2->start) ||
 656             (bm1->end != bm2->end))
 657                 return neq;
 658
 659         for (i = bm1->start; i < bm1->end; i++) {
 660                 int ret1, ret2;
 661                 ret1 = !!ext2fs_test_generic_bmap(gen_bm1, i);
 662                 ret2 = !!ext2fs_test_generic_bmap(gen_bm2, i);
 663                 if (ret1 != ret2) {
 664                         return neq;
 665                 }
 666         }
 667
 668         return 0;
 669 }
 670
 671 void ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap gen_bmap)
 672 {
 673         ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
 674         __u64   start, num;
 675
 676         if (EXT2FS_IS_32_BITMAP(bmap)) {
 677                 ext2fs_set_generic_bitmap_padding(gen_bmap);
 678                 return;
 679         }
 680
 681         start = bmap->end + 1;
 682         num = bmap->real_end - bmap->end;
 683         bmap->bitmap_ops->mark_bmap_extent(bmap, start, num);
 684         /* XXX ought to warn on error */
 685 }
 686
 687 int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,
 688                                     blk64_t block, unsigned int num)
 689 {
 690         ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
 691         __u64   end = block + num;
 692
 693         if (!bmap)
 694                 return EINVAL;
 695
 696         if (num == 1)
 697                 return !ext2fs_test_generic_bmap((ext2fs_generic_bitmap)
 698                                                  bmap, block);
 699
 700         if (EXT2FS_IS_32_BITMAP(bmap)) {
 701                 if ((block & ~0xffffffffULL) ||
 702                     ((block+num-1) & ~0xffffffffULL)) {
 703                         ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
 704                                             EXT2FS_UNMARK_ERROR, 0xffffffff);
 705                         return EINVAL;
 706                 }
 707                 return ext2fs_test_block_bitmap_range(
 708                         (ext2fs_generic_bitmap) bmap, block, num);
 709         }
 710
 711         if (!EXT2FS_IS_64_BITMAP(bmap))
 712                 return EINVAL;
 713
 714         INC_STAT(bmap, test_ext_count);
 715
 716         /* convert to clusters if necessary */
 717         block >>= bmap->cluster_bits;
 718         end += (1ULL << bmap->cluster_bits) - 1;
 719         end >>= bmap->cluster_bits;
 720         num = end - block;
 721
 722         if ((block < bmap->start) || (block > bmap->end) ||
 723             (block+num-1 > bmap->end)) {
 724                 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_TEST, block,
 725                                    bmap->description);
 726                 return EINVAL;
 727         }
 728
 729         return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num);
 730 }
 731
 732 int ext2fs_test_block_bitmap_range2_valid(ext2fs_block_bitmap bitmap,
 733                                           blk64_t block, unsigned int num)
 734 {
 735         ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64)bitmap;
 736         __u64   end = block + num;
 737
 738         if (!bmap)
 739                 return 0;
 740
 741         if (EXT2FS_IS_32_BITMAP(bmap)) {
 742                 if ((block & ~0xffffffffULL) ||
 743                     ((block+num-1) & ~0xffffffffULL)) {
 744                         return 0;
 745                 }
 746         }
 747
 748         if (!EXT2FS_IS_64_BITMAP(bmap))
 749                 return 0;
 750
 751         /* convert to clusters if necessary */
 752         block >>= bmap->cluster_bits;
 753         end += (1 << bmap->cluster_bits) - 1;
 754         end >>= bmap->cluster_bits;
 755         num = end - block;
 756
 757         if ((block < bmap->start) || (block > bmap->end) ||
 758             (block+num-1 > bmap->end))
 759                 return 0;
 760
 761         return 1;
 762 }
 763
 764
 765 void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,
 766                                      blk64_t block, unsigned int num)
 767 {
 768         ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
 769         __u64   end = block + num;
 770
 771         if (!bmap)
 772                 return;
 773
 774         if (EXT2FS_IS_32_BITMAP(bmap)) {
 775                 if ((block & ~0xffffffffULL) ||
 776                     ((block+num-1) & ~0xffffffffULL)) {
 777                         ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
 778                                             EXT2FS_UNMARK_ERROR, 0xffffffff);
 779                         return;
 780                 }
 781                 ext2fs_mark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
 782                                                block, num);
 783         }
 784
 785         if (!EXT2FS_IS_64_BITMAP(bmap))
 786                 return;
 787
 788         INC_STAT(bmap, mark_ext_count);
 789
 790         /* convert to clusters if necessary */
 791         block >>= bmap->cluster_bits;
 792         end += (1ULL << bmap->cluster_bits) - 1;
 793         end >>= bmap->cluster_bits;
 794         num = end - block;
 795
 796         if ((block < bmap->start) || (block > bmap->end) ||
 797             (block+num-1 > bmap->end)) {
 798                 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
 799                                    bmap->description);
 800                 return;
 801         }
 802
 803         bmap->bitmap_ops->mark_bmap_extent(bmap, block, num);
 804 }
 805
 806 void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap gen_bmap,
 807                                        blk64_t block, unsigned int num)
 808 {
 809         ext2fs_generic_bitmap_64 bmap = (ext2fs_generic_bitmap_64) gen_bmap;
 810         __u64   end = block + num;
 811
 812         if (!bmap)
 813                 return;
 814
 815         if (EXT2FS_IS_32_BITMAP(bmap)) {
 816                 if ((block & ~0xffffffffULL) ||
 817                     ((block+num-1) & ~0xffffffffULL)) {
 818                         ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
 819                                             EXT2FS_UNMARK_ERROR, 0xffffffff);
 820                         return;
 821                 }
 822                 ext2fs_unmark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
 823                                                  block, num);
 824         }
 825
 826         if (!EXT2FS_IS_64_BITMAP(bmap))
 827                 return;
 828
 829         INC_STAT(bmap, unmark_ext_count);
 830
 831         /* convert to clusters if necessary */
 832         block >>= bmap->cluster_bits;
 833         end += (1ULL << bmap->cluster_bits) - 1;
 834         end >>= bmap->cluster_bits;
 835         num = end - block;
 836
 837         if ((block < bmap->start) || (block > bmap->end) ||
 838             (block+num-1 > bmap->end)) {
 839                 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
 840                                    bmap->description);
 841                 return;
 842         }
 843
 844         bmap->bitmap_ops->unmark_bmap_extent(bmap, block, num);
 845 }
 846
 847 void ext2fs_warn_bitmap32(ext2fs_generic_bitmap gen_bitmap, const char *func)
 848 {
 849         ext2fs_generic_bitmap_64 bitmap = (ext2fs_generic_bitmap_64) gen_bitmap;
 850
 851 #ifndef OMIT_COM_ERR
 852         if (bitmap && bitmap->description)
 853                 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
 854                         "called %s with 64-bit bitmap for %s", func,
 855                         bitmap->description);
 856         else
 857                 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
 858                         "called %s with 64-bit bitmap", func);
 859 #endif
 860 }
 861
 862 errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs,
 863                                            ext2fs_block_bitmap *bitmap)
 864 {
 865         ext2fs_generic_bitmap_64 bmap, cmap;
 866         ext2fs_block_bitmap     gen_bmap = *bitmap, gen_cmap;
 867         errcode_t               retval;
 868         blk64_t                 i, next, b_end, c_end;
 869
 870         bmap = (ext2fs_generic_bitmap_64) gen_bmap;
 871         if (fs->cluster_ratio_bits == ext2fs_get_bitmap_granularity(gen_bmap))
 872                 return 0;       /* Nothing to do */
 873
 874         retval = ext2fs_allocate_block_bitmap(fs, "converted cluster bitmap",
 875                                               &gen_cmap);
 876         if (retval)
 877                 return retval;
 878
 879         cmap = (ext2fs_generic_bitmap_64) gen_cmap;
 880         i = bmap->start;
 881         b_end = bmap->end;
 882         bmap->end = bmap->real_end;
 883         c_end = cmap->end;
 884         cmap->end = cmap->real_end;
 885         while (i < bmap->real_end) {
 886                 retval = ext2fs_find_first_set_block_bitmap2(gen_bmap,
 887                                                 i, bmap->real_end, &next);
 888                 if (retval)
 889                         break;
 890                 ext2fs_mark_block_bitmap2(gen_cmap, next);
 891                 i = EXT2FS_C2B(fs, EXT2FS_B2C(fs, next) + 1);
 892         }
 893         bmap->end = b_end;
 894         cmap->end = c_end;
 895         ext2fs_free_block_bitmap(gen_bmap);
 896         *bitmap = (ext2fs_block_bitmap) cmap;
 897         return 0;
 898 }
 899
 900 errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
 901                                               __u64 start, __u64 end, __u64 *out)
 902 {
 903         ext2fs_generic_bitmap_64 bmap64 = (ext2fs_generic_bitmap_64) bitmap;
 904         __u64 cstart, cend, cout;
 905         errcode_t retval;
 906
 907         if (!bitmap)
 908                 return EINVAL;
 909
 910         if (EXT2FS_IS_32_BITMAP(bitmap)) {
 911                 blk_t blk = 0;
 912
 913                 if (((start) & ~0xffffffffULL) ||
 914                     ((end) & ~0xffffffffULL)) {
 915                         ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
 916                         return EINVAL;
 917                 }
 918
 919                 retval = ext2fs_find_first_zero_generic_bitmap(bitmap, start,
 920                                                                end, &blk);
 921                 if (retval == 0)
 922                         *out = blk;
 923                 return retval;
 924         }
 925
 926         if (!EXT2FS_IS_64_BITMAP(bitmap))
 927                 return EINVAL;
 928
 929         cstart = start >> bmap64->cluster_bits;
 930         cend = end >> bmap64->cluster_bits;
 931
 932         if (cstart < bmap64->start || cend > bmap64->end || start > end) {
 933                 warn_bitmap(bmap64, EXT2FS_TEST_ERROR, start);
 934                 return EINVAL;
 935         }
 936
 937         if (bmap64->bitmap_ops->find_first_zero) {
 938                 retval = bmap64->bitmap_ops->find_first_zero(bmap64, cstart,
 939                                                              cend, &cout);
 940                 if (retval)
 941                         return retval;
 942         found:
 943                 cout <<= bmap64->cluster_bits;
 944                 *out = (cout >= start) ? cout : start;
 945                 return 0;
 946         }
 947
 948         for (cout = cstart; cout <= cend; cout++)
 949                 if (!bmap64->bitmap_ops->test_bmap(bmap64, cout))
 950                         goto found;
 951
 952         return ENOENT;
 953 }
 954
 955 errcode_t ext2fs_find_first_set_generic_bmap(ext2fs_generic_bitmap bitmap,
 956                                              __u64 start, __u64 end, __u64 *out)
 957 {
 958         ext2fs_generic_bitmap_64 bmap64 = (ext2fs_generic_bitmap_64) bitmap;
 959         __u64 cstart, cend, cout;
 960         errcode_t retval;
 961
 962         if (!bitmap)
 963                 return EINVAL;
 964
 965         if (EXT2FS_IS_32_BITMAP(bitmap)) {
 966                 blk_t blk = 0;
 967
 968                 if (((start) & ~0xffffffffULL) ||
 969                     ((end) & ~0xffffffffULL)) {
 970                         ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
 971                         return EINVAL;
 972                 }
 973
 974                 retval = ext2fs_find_first_set_generic_bitmap(bitmap, start,
 975                                                               end, &blk);
 976                 if (retval == 0)
 977                         *out = blk;
 978                 return retval;
 979         }
 980
 981         if (!EXT2FS_IS_64_BITMAP(bitmap))
 982                 return EINVAL;
 983
 984         cstart = start >> bmap64->cluster_bits;
 985         cend = end >> bmap64->cluster_bits;
 986
 987         if (cstart < bmap64->start || cend > bmap64->end || start > end) {
 988                 warn_bitmap(bmap64, EXT2FS_TEST_ERROR, start);
 989                 return EINVAL;
 990         }
 991
 992         if (bmap64->bitmap_ops->find_first_set) {
 993                 retval = bmap64->bitmap_ops->find_first_set(bmap64, cstart,
 994                                                             cend, &cout);
 995                 if (retval)
 996                         return retval;
 997         found:
 998                 cout <<= bmap64->cluster_bits;
 999                 *out = (cout >= start) ? cout : start;
1000                 return 0;
1001         }
1002
1003         for (cout = cstart; cout <= cend; cout++)
1004                 if (bmap64->bitmap_ops->test_bmap(bmap64, cout))
1005                         goto found;
1006
1007         return ENOENT;
1008 }
1009
1010 errcode_t ext2fs_count_used_clusters(ext2_filsys fs, blk64_t start,
1011                                      blk64_t end, blk64_t *out)
1012 {
1013         blk64_t         next;
1014         blk64_t         tot_set = 0;
1015         errcode_t       retval = 0;
1016
1017         while (start < end) {
1018                 retval = ext2fs_find_first_set_block_bitmap2(fs->block_map,
1019                                                         start, end, &next);
1020                 if (retval) {
1021                         if (retval == ENOENT)
1022                                 retval = 0;
1023                         break;
1024                 }
1025                 start = next;
1026
1027                 retval = ext2fs_find_first_zero_block_bitmap2(fs->block_map,
1028                                                         start, end, &next);
1029                 if (retval == 0) {
1030                         tot_set += next - start;
1031                         start  = next + 1;
1032                 } else if (retval == ENOENT) {
1033                         retval = 0;
1034                         tot_set += end - start + 1;
1035                         break;
1036                 } else
1037                         break;
1038         }
1039
1040         if (!retval)
1041                 *out = EXT2FS_NUM_B2C(fs, tot_set);
1042         return retval;
1043 }