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