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