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