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
  29 #include "ext2_fs.h"
  30 #include "ext2fsP.h"
  31 #include "bmap64.h"
  32
  33 /*
  34  * Design of 64-bit bitmaps
  35  *
  36  * In order maintain ABI compatibility with programs that don't
  37  * understand about 64-bit blocks/inodes,
  38  * ext2fs_allocate_inode_bitmap() and ext2fs_allocate_block_bitmap()
  39  * will create old-style bitmaps unless the application passes the
  40  * flag EXT2_FLAG_64BITS to ext2fs_open().  If this flag is
  41  * passed, then we know the application has been recompiled, so we can
  42  * use the new-style bitmaps.  If it is not passed, we have to return
  43  * an error if trying to open a filesystem which needs 64-bit bitmaps.
  44  *
  45  * The new bitmaps use a new set of structure magic numbers, so that
  46  * both the old-style and new-style interfaces can identify which
  47  * version of the data structure was used.  Both the old-style and
  48  * new-style interfaces will support either type of bitmap, although
  49  * of course 64-bit operation will only be possible when both the
  50  * new-style interface and the new-style bitmap are used.
  51  *
  52  * For example, the new bitmap interfaces will check the structure
  53  * magic numbers and so will be able to detect old-stype bitmap.  If
  54  * they see an old-style bitmap, they will pass it to the gen_bitmap.c
  55  * functions for handling.  The same will be true for the old
  56  * interfaces as well.
  57  *
  58  * The new-style interfaces will have several different back-end
  59  * implementations, so we can support different encodings that are
  60  * appropriate for different applications.  In general the default
  61  * should be whatever makes sense, and what the application/library
  62  * will use.  However, e2fsck may need specialized implementations for
  63  * its own uses.  For example, when doing parent directory pointer
  64  * loop detections in pass 3, the bitmap will *always* be sparse, so
  65  * e2fsck can request an encoding which is optimized for that.
  66  */
  67
  68 static void warn_bitmap(ext2fs_generic_bitmap bitmap,
  69                         int code, __u64 arg)
  70 {
  71 #ifndef OMIT_COM_ERR
  72         if (bitmap->description)
  73                 com_err(0, bitmap->base_error_code+code,
  74                         "#%llu for %s", arg, bitmap->description);
  75         else
  76                 com_err(0, bitmap->base_error_code + code, "#%llu", arg);
  77 #endif
  78 }
  79
  80
  81 errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
  82                                     int type, __u64 start, __u64 end,
  83                                     __u64 real_end,
  84                                     const char *descr,
  85                                     ext2fs_generic_bitmap *ret)
  86 {
  87         ext2fs_generic_bitmap   bitmap;
  88         struct ext2_bitmap_ops  *ops;
  89         errcode_t retval;
  90
  91         if (!type)
  92                 type = EXT2FS_BMAP64_BITARRAY;
  93
  94         switch (type) {
  95         case EXT2FS_BMAP64_BITARRAY:
  96                 ops = &ext2fs_blkmap64_bitarray;
  97                 break;
  98         case EXT2FS_BMAP64_RBTREE:
  99                 ops = &ext2fs_blkmap64_rbtree;
 100                 break;
 101         default:
 102                 return EINVAL;
 103         }
 104
 105         retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap),
 106                                 &bitmap);
 107         if (retval)
 108                 return retval;
 109
 110         /* XXX factor out, repeated in copy_bmap */
 111         bitmap->magic = magic;
 112         bitmap->fs = fs;
 113         bitmap->start = start;
 114         bitmap->end = end;
 115         bitmap->real_end = real_end;
 116         bitmap->bitmap_ops = ops;
 117         bitmap->cluster_bits = 0;
 118         switch (magic) {
 119         case EXT2_ET_MAGIC_INODE_BITMAP64:
 120                 bitmap->base_error_code = EXT2_ET_BAD_INODE_MARK;
 121                 break;
 122         case EXT2_ET_MAGIC_BLOCK_BITMAP64:
 123                 bitmap->base_error_code = EXT2_ET_BAD_BLOCK_MARK;
 124                 bitmap->cluster_bits = fs->cluster_ratio_bits;
 125                 break;
 126         default:
 127                 bitmap->base_error_code = EXT2_ET_BAD_GENERIC_MARK;
 128         }
 129         if (descr) {
 130                 retval = ext2fs_get_mem(strlen(descr)+1, &bitmap->description);
 131                 if (retval) {
 132                         ext2fs_free_mem(&bitmap);
 133                         return retval;
 134                 }
 135                 strcpy(bitmap->description, descr);
 136         } else
 137                 bitmap->description = 0;
 138
 139         retval = bitmap->bitmap_ops->new_bmap(fs, bitmap);
 140         if (retval) {
 141                 ext2fs_free_mem(&bitmap->description);
 142                 ext2fs_free_mem(&bitmap);
 143                 return retval;
 144         }
 145
 146         *ret = bitmap;
 147         return 0;
 148 }
 149
 150 void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap)
 151 {
 152         if (!bmap)
 153                 return;
 154
 155         if (EXT2FS_IS_32_BITMAP(bmap)) {
 156                 ext2fs_free_generic_bitmap(bmap);
 157                 return;
 158         }
 159
 160         if (!EXT2FS_IS_64_BITMAP(bmap))
 161                 return;
 162
 163         bmap->bitmap_ops->free_bmap(bmap);
 164
 165         if (bmap->description) {
 166                 ext2fs_free_mem(&bmap->description);
 167                 bmap->description = 0;
 168         }
 169         bmap->magic = 0;
 170         ext2fs_free_mem(&bmap);
 171 }
 172
 173 errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap src,
 174                                    ext2fs_generic_bitmap *dest)
 175 {
 176         char *descr, *new_descr;
 177         ext2fs_generic_bitmap   new_bmap;
 178         errcode_t retval;
 179
 180         if (!src)
 181                 return EINVAL;
 182
 183         if (EXT2FS_IS_32_BITMAP(src))
 184                 return ext2fs_copy_generic_bitmap(src, dest);
 185
 186         if (!EXT2FS_IS_64_BITMAP(src))
 187                 return EINVAL;
 188
 189         /* Allocate a new bitmap struct */
 190         retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap),
 191                                 &new_bmap);
 192         if (retval)
 193                 return retval;
 194
 195         /* Copy all the high-level parts over */
 196         new_bmap->magic = src->magic;
 197         new_bmap->fs = src->fs;
 198         new_bmap->start = src->start;
 199         new_bmap->end = src->end;
 200         new_bmap->real_end = src->real_end;
 201         new_bmap->bitmap_ops = src->bitmap_ops;
 202         new_bmap->base_error_code = src->base_error_code;
 203         new_bmap->cluster_bits = src->cluster_bits;
 204
 205         descr = src->description;
 206         if (descr) {
 207                 retval = ext2fs_get_mem(strlen(descr)+1, &new_descr);
 208                 if (retval) {
 209                         ext2fs_free_mem(&new_bmap);
 210                         return retval;
 211                 }
 212                 strcpy(new_descr, descr);
 213                 new_bmap->description = new_descr;
 214         }
 215
 216         retval = src->bitmap_ops->copy_bmap(src, new_bmap);
 217         if (retval) {
 218                 ext2fs_free_mem(&new_bmap->description);
 219                 ext2fs_free_mem(&new_bmap);
 220                 return retval;
 221         }
 222
 223         *dest = new_bmap;
 224
 225         return 0;
 226 }
 227
 228 errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap bmap,
 229                                      __u64 new_end,
 230                                      __u64 new_real_end)
 231 {
 232         if (!bmap)
 233                 return EINVAL;
 234
 235         if (EXT2FS_IS_32_BITMAP(bmap))
 236                 return ext2fs_resize_generic_bitmap(bmap->magic, new_end,
 237                                                     new_real_end, bmap);
 238
 239         if (!EXT2FS_IS_64_BITMAP(bmap))
 240                 return EINVAL;
 241
 242         return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end);
 243 }
 244
 245 errcode_t ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap bitmap,
 246                                         errcode_t neq,
 247                                         __u64 end, __u64 *oend)
 248 {
 249         if (!bitmap)
 250                 return EINVAL;
 251
 252         if (EXT2FS_IS_32_BITMAP(bitmap)) {
 253                 ext2_ino_t tmp_oend;
 254                 int retval;
 255
 256                 retval = ext2fs_fudge_generic_bitmap_end(bitmap, bitmap->magic,
 257                                                          neq, end, &tmp_oend);
 258                 if (oend)
 259                         *oend = tmp_oend;
 260                 return retval;
 261         }
 262
 263         if (!EXT2FS_IS_64_BITMAP(bitmap))
 264                 return EINVAL;
 265
 266         if (end > bitmap->real_end)
 267                 return neq;
 268         if (oend)
 269                 *oend = bitmap->end;
 270         bitmap->end = end;
 271         return 0;
 272 }
 273
 274 __u64 ext2fs_get_generic_bmap_start(ext2fs_generic_bitmap bitmap)
 275 {
 276         if (!bitmap)
 277                 return EINVAL;
 278
 279         if (EXT2FS_IS_32_BITMAP(bitmap))
 280                 return ext2fs_get_generic_bitmap_start(bitmap);
 281
 282         if (!EXT2FS_IS_64_BITMAP(bitmap))
 283                 return EINVAL;
 284
 285         return bitmap->start;
 286 }
 287
 288 __u64 ext2fs_get_generic_bmap_end(ext2fs_generic_bitmap bitmap)
 289 {
 290         if (!bitmap)
 291                 return EINVAL;
 292
 293         if (EXT2FS_IS_32_BITMAP(bitmap))
 294                 return ext2fs_get_generic_bitmap_end(bitmap);
 295
 296         if (!EXT2FS_IS_64_BITMAP(bitmap))
 297                 return EINVAL;
 298
 299         return bitmap->end;
 300 }
 301
 302 void ext2fs_clear_generic_bmap(ext2fs_generic_bitmap bitmap)
 303 {
 304         if (EXT2FS_IS_32_BITMAP(bitmap))
 305                 ext2fs_clear_generic_bitmap(bitmap);
 306         else
 307                 bitmap->bitmap_ops->clear_bmap (bitmap);
 308 }
 309
 310 int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap bitmap,
 311                              __u64 arg)
 312 {
 313         if (!bitmap)
 314                 return 0;
 315
 316         if (EXT2FS_IS_32_BITMAP(bitmap)) {
 317                 if (arg & ~0xffffffffULL) {
 318                         ext2fs_warn_bitmap2(bitmap,
 319                                             EXT2FS_MARK_ERROR, 0xffffffff);
 320                         return 0;
 321                 }
 322                 return ext2fs_mark_generic_bitmap(bitmap, arg);
 323         }
 324
 325         if (!EXT2FS_IS_64_BITMAP(bitmap))
 326                 return 0;
 327
 328         arg >>= bitmap->cluster_bits;
 329
 330         if ((arg < bitmap->start) || (arg > bitmap->end)) {
 331                 warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg);
 332                 return 0;
 333         }
 334
 335         return bitmap->bitmap_ops->mark_bmap(bitmap, arg);
 336 }
 337
 338 int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap bitmap,
 339                                __u64 arg)
 340 {
 341         if (!bitmap)
 342                 return 0;
 343
 344         if (EXT2FS_IS_32_BITMAP(bitmap)) {
 345                 if (arg & ~0xffffffffULL) {
 346                         ext2fs_warn_bitmap2(bitmap, EXT2FS_UNMARK_ERROR,
 347                                             0xffffffff);
 348                         return 0;
 349                 }
 350                 return ext2fs_unmark_generic_bitmap(bitmap, arg);
 351         }
 352
 353         if (!EXT2FS_IS_64_BITMAP(bitmap))
 354                 return 0;
 355
 356         arg >>= bitmap->cluster_bits;
 357
 358         if ((arg < bitmap->start) || (arg > bitmap->end)) {
 359                 warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg);
 360                 return 0;
 361         }
 362
 363         return bitmap->bitmap_ops->unmark_bmap(bitmap, arg);
 364 }
 365
 366 int ext2fs_test_generic_bmap(ext2fs_generic_bitmap bitmap,
 367                              __u64 arg)
 368 {
 369         if (!bitmap)
 370                 return 0;
 371
 372         if (EXT2FS_IS_32_BITMAP(bitmap)) {
 373                 if (arg & ~0xffffffffULL) {
 374                         ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR,
 375                                             0xffffffff);
 376                         return 0;
 377                 }
 378                 return ext2fs_test_generic_bitmap(bitmap, arg);
 379         }
 380
 381         if (!EXT2FS_IS_64_BITMAP(bitmap))
 382                 return 0;
 383
 384         arg >>= bitmap->cluster_bits;
 385
 386         if ((arg < bitmap->start) || (arg > bitmap->end)) {
 387                 warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg);
 388                 return 0;
 389         }
 390
 391         return bitmap->bitmap_ops->test_bmap(bitmap, arg);
 392 }
 393
 394 errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap bmap,
 395                                         __u64 start, unsigned int num,
 396                                         void *in)
 397 {
 398         if (!bmap)
 399                 return EINVAL;
 400
 401         if (EXT2FS_IS_32_BITMAP(bmap)) {
 402                 if ((start+num-1) & ~0xffffffffULL) {
 403                         ext2fs_warn_bitmap2(bmap, EXT2FS_UNMARK_ERROR,
 404                                             0xffffffff);
 405                         return EINVAL;
 406                 }
 407                 return ext2fs_set_generic_bitmap_range(bmap, bmap->magic,
 408                                                        start, num, in);
 409         }
 410
 411         if (!EXT2FS_IS_64_BITMAP(bmap))
 412                 return EINVAL;
 413
 414         return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in);
 415 }
 416
 417 errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap bmap,
 418                                         __u64 start, unsigned int num,
 419                                         void *out)
 420 {
 421         if (!bmap)
 422                 return EINVAL;
 423
 424         if (EXT2FS_IS_32_BITMAP(bmap)) {
 425                 if ((start+num-1) & ~0xffffffffULL) {
 426                         ext2fs_warn_bitmap2(bmap,
 427                                             EXT2FS_UNMARK_ERROR, 0xffffffff);
 428                         return EINVAL;
 429                 }
 430                 return ext2fs_get_generic_bitmap_range(bmap, bmap->magic,
 431                                                        start, num, out);
 432         }
 433
 434         if (!EXT2FS_IS_64_BITMAP(bmap))
 435                 return EINVAL;
 436
 437         return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out);
 438 }
 439
 440 errcode_t ext2fs_compare_generic_bmap(errcode_t neq,
 441                                       ext2fs_generic_bitmap bm1,
 442                                       ext2fs_generic_bitmap bm2)
 443 {
 444         blk64_t i;
 445
 446         if (!bm1 || !bm2)
 447                 return EINVAL;
 448         if (bm1->magic != bm2->magic)
 449                 return EINVAL;
 450
 451         /* Now we know both bitmaps have the same magic */
 452         if (EXT2FS_IS_32_BITMAP(bm1))
 453                 return ext2fs_compare_generic_bitmap(bm1->magic, neq, bm1, bm2);
 454
 455         if (!EXT2FS_IS_64_BITMAP(bm1))
 456                 return EINVAL;
 457
 458         if ((bm1->start != bm2->start) ||
 459             (bm1->end != bm2->end))
 460                 return neq;
 461
 462         for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++)
 463                 if (ext2fs_test_generic_bmap(bm1, i) !=
 464                     ext2fs_test_generic_bmap(bm2, i))
 465                         return neq;
 466
 467         return 0;
 468 }
 469
 470 void ext2fs_set_generic_bmap_padding(ext2fs_generic_bitmap bmap)
 471 {
 472         __u64   start, num;
 473
 474         if (EXT2FS_IS_32_BITMAP(bmap)) {
 475                 ext2fs_set_generic_bitmap_padding(bmap);
 476                 return;
 477         }
 478
 479         start = bmap->end + 1;
 480         num = bmap->real_end - bmap->end;
 481         bmap->bitmap_ops->mark_bmap_extent(bmap, start, num);
 482         /* XXX ought to warn on error */
 483 }
 484
 485 int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap bmap,
 486                                     blk64_t block, unsigned int num)
 487 {
 488         if (!bmap)
 489                 return EINVAL;
 490
 491         if (num == 1)
 492                 return !ext2fs_test_generic_bmap((ext2fs_generic_bitmap)
 493                                                  bmap, block);
 494
 495         if (EXT2FS_IS_32_BITMAP(bmap)) {
 496                 if ((block+num-1) & ~0xffffffffULL) {
 497                         ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
 498                                             EXT2FS_UNMARK_ERROR, 0xffffffff);
 499                         return EINVAL;
 500                 }
 501                 return ext2fs_test_block_bitmap_range(
 502                         (ext2fs_generic_bitmap) bmap, block, num);
 503         }
 504
 505         if (!EXT2FS_IS_64_BITMAP(bmap))
 506                 return EINVAL;
 507
 508         return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num);
 509 }
 510
 511 void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap bmap,
 512                                      blk64_t block, unsigned int num)
 513 {
 514         if (!bmap)
 515                 return;
 516
 517         if (EXT2FS_IS_32_BITMAP(bmap)) {
 518                 if ((block+num-1) & ~0xffffffffULL) {
 519                         ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
 520                                             EXT2FS_UNMARK_ERROR, 0xffffffff);
 521                         return;
 522                 }
 523                 ext2fs_mark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
 524                                                block, num);
 525         }
 526
 527         if (!EXT2FS_IS_64_BITMAP(bmap))
 528                 return;
 529
 530         if ((block < bmap->start) || (block+num-1 > bmap->end)) {
 531                 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
 532                                    bmap->description);
 533                 return;
 534         }
 535
 536         bmap->bitmap_ops->mark_bmap_extent(bmap, block, num);
 537 }
 538
 539 void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap bmap,
 540                                        blk64_t block, unsigned int num)
 541 {
 542         if (!bmap)
 543                 return;
 544
 545         if (EXT2FS_IS_32_BITMAP(bmap)) {
 546                 if ((block+num-1) & ~0xffffffffULL) {
 547                         ext2fs_warn_bitmap2((ext2fs_generic_bitmap) bmap,
 548                                             EXT2FS_UNMARK_ERROR, 0xffffffff);
 549                         return;
 550                 }
 551                 ext2fs_unmark_block_bitmap_range((ext2fs_generic_bitmap) bmap,
 552                                                  block, num);
 553         }
 554
 555         if (!EXT2FS_IS_64_BITMAP(bmap))
 556                 return;
 557
 558         if ((block < bmap->start) || (block+num-1 > bmap->end)) {
 559                 ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
 560                                    bmap->description);
 561                 return;
 562         }
 563
 564         bmap->bitmap_ops->unmark_bmap_extent(bmap, block, num);
 565 }
 566
 567 void ext2fs_warn_bitmap32(ext2fs_generic_bitmap bitmap, const char *func)
 568 {
 569 #ifndef OMIT_COM_ERR
 570         if (bitmap && bitmap->description)
 571                 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
 572                         "called %s with 64-bit bitmap for %s", func,
 573                         bitmap->description);
 574         else
 575                 com_err(0, EXT2_ET_MAGIC_GENERIC_BITMAP,
 576                         "called %s with 64-bit bitmap", func);
 577 #endif
 578 }
 579
 580 errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs,
 581                                            ext2fs_block_bitmap *bitmap)
 582 {
 583         ext2fs_block_bitmap     cmap, bmap;
 584         errcode_t               retval;
 585         blk64_t                 i, b_end, c_end;
 586         int                     n, ratio;
 587
 588         bmap = *bitmap;
 589
 590         if (fs->cluster_ratio_bits == ext2fs_get_bitmap_granularity(bmap))
 591                 return 0;       /* Nothing to do */
 592
 593         retval = ext2fs_allocate_block_bitmap(fs, "converted cluster bitmap",
 594                                               &cmap);
 595         if (retval)
 596                 return retval;
 597
 598         i = bmap->start;
 599         b_end = bmap->end;
 600         bmap->end = bmap->real_end;
 601         c_end = cmap->end;
 602         cmap->end = cmap->real_end;
 603         n = 0;
 604         ratio = 1 << fs->cluster_ratio_bits;
 605         while (i < bmap->real_end) {
 606                 if (ext2fs_test_block_bitmap2(bmap, i)) {
 607                         ext2fs_mark_block_bitmap2(cmap, i);
 608                         i += ratio - n;
 609                         n = 0;
 610                         continue;
 611                 }
 612                 i++; n++;
 613                 if (n >= ratio)
 614                         n = 0;
 615         }
 616         bmap->end = b_end;
 617         cmap->end = c_end;
 618         ext2fs_free_block_bitmap(bmap);
 619         *bitmap = cmap;
 620         return 0;
 621 }