resize/resize2fs.c

   1 /*
   2  * resize2fs.c --- ext2 main routine
   3  *
   4  * Copyright (C) 1997 Theodore Ts'o
   5  *
   6  * %Begin-Header%
   7  * All rights reserved.
   8  * %End-Header%
   9  */
  10
  11 /*
  12  * Resizing a filesystem consists of the following phases:
  13  *
  14  *      1.  Adjust superblock and write out new parts of the inode
  15  *              table
  16  *      2.  Determine blocks which need to be relocated, and copy the
  17  *              contents of blocks from their old locations to the new ones.
  18  *      3.  Scan the inode table, doing the following:
  19  *              a.  If blocks have been moved, update the block
  20  *                      pointers in the inodes and indirect blocks to
  21  *                      point at the new block locations.
  22  *              b.  If parts of the inode table need to be evacuated,
  23  *                      copy inodes from their old locations to their
  24  *                      new ones.
  25  *              c.  If (b) needs to be done, note which blocks contain
  26  *                      directory information, since we will need to
  27  *                      update the directory information.
  28  *      4.  Update the directory blocks with the new inode locations.
  29  *      5.  Move the inode tables, if necessary.
  30  */
  31
  32 #include "resize2fs.h"
  33
  34 #ifdef linux                    /* Kludge for debugging */
  35 #define RESIZE2FS_DEBUG
  36 #endif
  37
  38 static errcode_t adjust_superblock(ext2_resize_t rfs, blk_t new_size);
  39 static errcode_t blocks_to_move(ext2_resize_t rfs);
  40 static errcode_t block_mover(ext2_resize_t rfs);
  41 static errcode_t inode_scan_and_fix(ext2_resize_t rfs);
  42 static errcode_t inode_ref_fix(ext2_resize_t rfs);
  43 static errcode_t move_itables(ext2_resize_t rfs);
  44 static errcode_t ext2fs_calculate_summary_stats(ext2_filsys fs);
  45
  46 /*
  47  * Some helper CPP macros
  48  */
  49 #define FS_BLOCK_BM(fs, i) ((fs)->group_desc[(i)].bg_block_bitmap)
  50 #define FS_INODE_BM(fs, i) ((fs)->group_desc[(i)].bg_inode_bitmap)
  51 #define FS_INODE_TB(fs, i) ((fs)->group_desc[(i)].bg_inode_table)
  52
  53 #define IS_BLOCK_BM(fs, i, blk) ((blk) == FS_BLOCK_BM((fs),(i)))
  54 #define IS_INODE_BM(fs, i, blk) ((blk) == FS_INODE_BM((fs),(i)))
  55
  56 #define IS_INODE_TB(fs, i, blk) (((blk) >= FS_INODE_TB((fs), (i))) && \
  57                                  ((blk) < (FS_INODE_TB((fs), (i)) + \
  58                                            (fs)->inode_blocks_per_group)))
  59
  60
  61
  62 /*
  63  * This is the top-level routine which does the dirty deed....
  64  */
  65 errcode_t resize_fs(ext2_filsys fs, blk_t new_size, int flags,
  66                     void (*progress)(ext2_resize_t rfs, int pass,
  67                                      unsigned long cur,
  68                                      unsigned long max))
  69 {
  70         ext2_resize_t   rfs;
  71         errcode_t       retval;
  72
  73         retval = ext2fs_read_bitmaps(fs);
  74         if (retval)
  75                 return retval;
  76
  77         /*
  78          * Create the data structure
  79          */
  80         retval = ext2fs_get_mem(sizeof(struct ext2_resize_struct),
  81                                 (void **) &rfs);
  82         if (retval)
  83                 return retval;
  84         memset(rfs, 0, sizeof(struct ext2_resize_struct));
  85
  86         rfs->old_fs = fs;
  87         rfs->flags = flags;
  88         rfs->itable_buf  = 0;
  89         rfs->progress = progress;
  90         retval = ext2fs_dup_handle(fs, &rfs->new_fs);
  91         if (retval)
  92                 goto errout;
  93
  94         retval = adjust_superblock(rfs, new_size);
  95         if (retval)
  96                 goto errout;
  97
  98         retval = blocks_to_move(rfs);
  99         if (retval)
 100                 goto errout;
 101
 102 #ifdef RESIZE2FS_DEBUG
 103         if (rfs->flags & RESIZE_DEBUG_BMOVE)
 104                 printf("Number of free blocks: %d/%d, Needed: %d\n",
 105                        rfs->old_fs->super->s_free_blocks_count,
 106                        rfs->new_fs->super->s_free_blocks_count,
 107                        rfs->needed_blocks);
 108 #endif
 109
 110         retval = block_mover(rfs);
 111         if (retval)
 112                 goto errout;
 113
 114         retval = inode_scan_and_fix(rfs);
 115         if (retval)
 116                 goto errout;
 117
 118         retval = inode_ref_fix(rfs);
 119         if (retval)
 120                 goto errout;
 121
 122         retval = ext2fs_calculate_summary_stats(rfs->new_fs);
 123         if (retval)
 124                 goto errout;
 125
 126         retval = move_itables(rfs);
 127         if (retval)
 128                 goto errout;
 129
 130         retval = ext2fs_close(rfs->new_fs);
 131         if (retval)
 132                 goto errout;
 133
 134         rfs->flags = flags;
 135
 136         ext2fs_free(rfs->old_fs);
 137         if (rfs->itable_buf)
 138                 ext2fs_free_mem((void **) &rfs->itable_buf);
 139         ext2fs_free_mem((void **) &rfs);
 140
 141         return 0;
 142
 143 errout:
 144         if (rfs->new_fs)
 145                 ext2fs_free(rfs->new_fs);
 146         if (rfs->itable_buf)
 147                 ext2fs_free_mem((void **) &rfs->itable_buf);
 148         ext2fs_free_mem((void **) &rfs);
 149         return retval;
 150 }
 151
 152 /* --------------------------------------------------------------------
 153  *
 154  * Resize processing, phase 1.
 155  *
 156  * In this phase we adjust the in-memory superblock information, and
 157  * initialize any new parts of the inode table.  The new parts of the
 158  * inode table are created in virgin disk space, so we can abort here
 159  * without any side effects.
 160  * --------------------------------------------------------------------
 161  */
 162
 163 /*
 164  * This routine adjusts the superblock and other data structures...
 165  */
 166 static errcode_t adjust_superblock(ext2_resize_t rfs, blk_t new_size)
 167 {
 168         ext2_filsys fs;
 169         int             overhead = 0;
 170         int             rem, adj = 0;
 171         errcode_t       retval;
 172         ino_t           real_end;
 173         blk_t           blk, group_block;
 174         unsigned long   i, j;
 175         int             old_numblocks, numblocks, adjblocks;
 176         unsigned long   max_group;
 177
 178         fs = rfs->new_fs;
 179         fs->super->s_blocks_count = new_size;
 180         ext2fs_mark_super_dirty(fs);
 181         ext2fs_mark_bb_dirty(fs);
 182         ext2fs_mark_ib_dirty(fs);
 183
 184 retry:
 185         fs->group_desc_count = (fs->super->s_blocks_count -
 186                                 fs->super->s_first_data_block +
 187                                 EXT2_BLOCKS_PER_GROUP(fs->super) - 1)
 188                 / EXT2_BLOCKS_PER_GROUP(fs->super);
 189         if (fs->group_desc_count == 0)
 190                 return EXT2_ET_TOOSMALL;
 191         fs->desc_blocks = (fs->group_desc_count +
 192                            EXT2_DESC_PER_BLOCK(fs->super) - 1)
 193                 / EXT2_DESC_PER_BLOCK(fs->super);
 194
 195         /*
 196          * Overhead is the number of bookkeeping blocks per group.  It
 197          * includes the superblock backup, the group descriptor
 198          * backups, the inode bitmap, the block bitmap, and the inode
 199          * table.
 200          *
 201          * XXX Not all block groups need the descriptor blocks, but
 202          * being clever is tricky...
 203          */
 204         overhead = 3 + fs->desc_blocks + fs->inode_blocks_per_group;
 205
 206         /*
 207          * See if the last group is big enough to support the
 208          * necessary data structures.  If not, we need to get rid of
 209          * it.
 210          */
 211         rem = (fs->super->s_blocks_count - fs->super->s_first_data_block) %
 212                 fs->super->s_blocks_per_group;
 213         if ((fs->group_desc_count == 1) && rem && (rem < overhead))
 214                 return EXT2_ET_TOOSMALL;
 215         if (rem && (rem < overhead+50)) {
 216                 fs->super->s_blocks_count -= rem;
 217                 goto retry;
 218         }
 219         /*
 220          * Adjust the number of inodes
 221          */
 222         fs->super->s_inodes_count = fs->super->s_inodes_per_group *
 223                 fs->group_desc_count;
 224
 225         /*
 226          * Adjust the number of free blocks
 227          */
 228         blk = rfs->old_fs->super->s_blocks_count;
 229         if (blk > fs->super->s_blocks_count)
 230                 fs->super->s_free_blocks_count -=
 231                         (blk - fs->super->s_blocks_count);
 232         else
 233                 fs->super->s_free_blocks_count +=
 234                         (fs->super->s_blocks_count - blk);
 235
 236         /*
 237          * Adjust the number of reserved blocks
 238          */
 239         blk = rfs->old_fs->super->s_r_blocks_count * 100 /
 240                 rfs->old_fs->super->s_blocks_count;
 241         fs->super->s_r_blocks_count = ((fs->super->s_blocks_count * blk)
 242                                        / 100);
 243
 244         /*
 245          * Adjust the bitmaps for size
 246          */
 247         retval = ext2fs_resize_inode_bitmap(fs->super->s_inodes_count,
 248                                             fs->super->s_inodes_count,
 249                                             fs->inode_map);
 250         if (retval) goto errout;
 251
 252         real_end = ((EXT2_BLOCKS_PER_GROUP(fs->super)
 253                      * fs->group_desc_count)) - 1 +
 254                              fs->super->s_first_data_block;
 255         retval = ext2fs_resize_block_bitmap(fs->super->s_blocks_count-1,
 256                                             real_end, fs->block_map);
 257
 258         if (retval) goto errout;
 259
 260         /*
 261          * Reallocate the group descriptors as necessary.
 262          */
 263         if (rfs->old_fs->desc_blocks != fs->desc_blocks) {
 264                 retval = ext2fs_resize_mem(fs->desc_blocks * fs->blocksize,
 265                                            (void **) &fs->group_desc);
 266                 if (retval)
 267                         goto errout;
 268         }
 269
 270         /*
 271          * Check to make sure there are enough inodes
 272          */
 273         if ((rfs->old_fs->super->s_inodes_count -
 274              rfs->old_fs->super->s_free_inodes_count) >
 275             rfs->new_fs->super->s_inodes_count) {
 276                 retval = ENOSPC;
 277                 goto errout;
 278         }
 279
 280         /*
 281          * If we are shrinking the number block groups, we're done and
 282          * can exit now.
 283          */
 284         if (rfs->old_fs->group_desc_count > fs->group_desc_count) {
 285                 retval = 0;
 286                 goto errout;
 287         }
 288         /*
 289          * Fix the count of the last (old) block group
 290          */
 291         old_numblocks = (rfs->old_fs->super->s_blocks_count -
 292                          rfs->old_fs->super->s_first_data_block) %
 293                                  rfs->old_fs->super->s_blocks_per_group;
 294         if (!old_numblocks)
 295                 old_numblocks = rfs->old_fs->super->s_blocks_per_group;
 296         if (rfs->old_fs->group_desc_count == fs->group_desc_count) {
 297                 numblocks = (rfs->new_fs->super->s_blocks_count -
 298                              rfs->new_fs->super->s_first_data_block) %
 299                                      rfs->new_fs->super->s_blocks_per_group;
 300                 if (!numblocks)
 301                         numblocks = rfs->new_fs->super->s_blocks_per_group;
 302         } else
 303                 numblocks = rfs->new_fs->super->s_blocks_per_group;
 304         i = rfs->old_fs->group_desc_count - 1;
 305         fs->group_desc[i].bg_free_blocks_count += (numblocks-old_numblocks);
 306
 307         /*
 308          * If the number of block groups is staying the same, we're
 309          * done and can exit now.  (If the number block groups is
 310          * shrinking, we had exited earlier.)
 311          */
 312         if (rfs->old_fs->group_desc_count >= fs->group_desc_count) {
 313                 retval = 0;
 314                 goto errout;
 315         }
 316         /*
 317          * Initialize the new block group descriptors
 318          */
 319         retval = ext2fs_get_mem(fs->blocksize * fs->inode_blocks_per_group,
 320                                 (void **) &rfs->itable_buf);
 321         if (retval)
 322                 goto errout;
 323
 324         memset(rfs->itable_buf, 0, fs->blocksize * fs->inode_blocks_per_group);
 325         group_block = fs->super->s_first_data_block +
 326                 rfs->old_fs->group_desc_count * fs->super->s_blocks_per_group;
 327
 328         adj = rfs->old_fs->group_desc_count;
 329         max_group = fs->group_desc_count - adj;
 330         if (rfs->progress)
 331                 rfs->progress(rfs, E2_RSZ_EXTEND_ITABLE_PASS,
 332                               0, max_group);
 333         for (i = rfs->old_fs->group_desc_count;
 334              i < fs->group_desc_count; i++) {
 335                 memset(&fs->group_desc[i], 0,
 336                        sizeof(struct ext2_group_desc));
 337                 adjblocks = 0;
 338
 339                 if (i == fs->group_desc_count-1) {
 340                         numblocks = (fs->super->s_blocks_count -
 341                                      fs->super->s_first_data_block) %
 342                                              fs->super->s_blocks_per_group;
 343                         if (!numblocks)
 344                                 numblocks = fs->super->s_blocks_per_group;
 345                 } else
 346                         numblocks = fs->super->s_blocks_per_group;
 347
 348                 if (ext2fs_bg_has_super(fs, i)) {
 349                         for (j=0; j < fs->desc_blocks+1; j++)
 350                                 ext2fs_mark_block_bitmap(fs->block_map,
 351                                                          group_block + j);
 352                         adjblocks = 1 + fs->desc_blocks;
 353                 }
 354                 adjblocks += 2 + fs->inode_blocks_per_group;
 355
 356                 numblocks -= adjblocks;
 357                 fs->super->s_free_blocks_count -= adjblocks;
 358                 fs->super->s_free_inodes_count +=
 359                         fs->super->s_inodes_per_group;
 360                 fs->group_desc[i].bg_free_blocks_count = numblocks;
 361                 fs->group_desc[i].bg_free_inodes_count =
 362                         fs->super->s_inodes_per_group;
 363                 fs->group_desc[i].bg_used_dirs_count = 0;
 364
 365                 retval = ext2fs_allocate_group_table(fs, i, 0);
 366                 if (retval) goto errout;
 367
 368                 /*
 369                  * Write out the new inode table
 370                  */
 371                 retval = io_channel_write_blk(fs->io,
 372                                               fs->group_desc[i].bg_inode_table,
 373                                               fs->inode_blocks_per_group,
 374                                               rfs->itable_buf);
 375                 if (retval) goto errout;
 376
 377                 io_channel_flush(fs->io);
 378                 if (rfs->progress)
 379                         rfs->progress(rfs, E2_RSZ_EXTEND_ITABLE_PASS,
 380                                       i - adj + 1, max_group);
 381
 382                 group_block += fs->super->s_blocks_per_group;
 383         }
 384         io_channel_flush(fs->io);
 385         retval = 0;
 386
 387 errout:
 388         return retval;
 389 }
 390
 391 /* --------------------------------------------------------------------
 392  *
 393  * Resize processing, phase 2.
 394  *
 395  * In this phase we adjust determine which blocks need to be moved, in
 396  * blocks_to_move().  We then copy the blocks to their ultimate new
 397  * destinations using block_mover().  Since we are copying blocks to
 398  * their new locations, again during this pass we can abort without
 399  * any problems.
 400  * --------------------------------------------------------------------
 401  */
 402
 403 /*
 404  * This helper function creates a block bitmap with all of the
 405  * filesystem meta-data blocks.
 406  */
 407 static errcode_t mark_table_blocks(ext2_filsys fs,
 408                                    ext2fs_block_bitmap *ret_bmap)
 409 {
 410         blk_t                   block, b;
 411         int                     i,j;
 412         ext2fs_block_bitmap     bmap;
 413         errcode_t               retval;
 414
 415         retval = ext2fs_allocate_block_bitmap(fs, "meta-data blocks", &bmap);
 416         if (retval)
 417                 return retval;
 418
 419         block = fs->super->s_first_data_block;
 420         for (i = 0; i < fs->group_desc_count; i++) {
 421                 if (ext2fs_bg_has_super(fs, i)) {
 422                         /*
 423                          * Mark this group's copy of the superblock
 424                          */
 425                         ext2fs_mark_block_bitmap(bmap, block);
 426
 427                         /*
 428                          * Mark this group's copy of the descriptors
 429                          */
 430                         for (j = 0; j < fs->desc_blocks; j++)
 431                                 ext2fs_mark_block_bitmap(bmap, block + j + 1);
 432                 }
 433
 434                 /*
 435                  * Mark the blocks used for the inode table
 436                  */
 437                 for (j = 0, b = fs->group_desc[i].bg_inode_table;
 438                      j < fs->inode_blocks_per_group;
 439                      j++, b++)
 440                         ext2fs_mark_block_bitmap(bmap, b);
 441
 442                 /*
 443                  * Mark block used for the block bitmap
 444                  */
 445                 ext2fs_mark_block_bitmap(bmap,
 446                                          fs->group_desc[i].bg_block_bitmap);
 447                 /*
 448                  * Mark block used for the inode bitmap
 449                  */
 450                 ext2fs_mark_block_bitmap(bmap,
 451                                          fs->group_desc[i].bg_inode_bitmap);
 452                 block += fs->super->s_blocks_per_group;
 453         }
 454         *ret_bmap = bmap;
 455         return 0;
 456 }
 457
 458 /*
 459  * This routine marks and unmarks reserved blocks in the new block
 460  * bitmap.  It also determines which blocks need to be moved and
 461  * places this information into the move_blocks bitmap.
 462  */
 463 static errcode_t blocks_to_move(ext2_resize_t rfs)
 464 {
 465         int     i, j, max;
 466         blk_t   blk, group_blk;
 467         unsigned long old_blocks, new_blocks;
 468         errcode_t       retval;
 469         ext2_filsys     fs, old_fs;
 470         ext2fs_block_bitmap     meta_bmap;
 471
 472         fs = rfs->new_fs;
 473         old_fs = rfs->old_fs;
 474         if (old_fs->super->s_blocks_count > fs->super->s_blocks_count)
 475                 fs = rfs->old_fs;
 476
 477         retval = ext2fs_allocate_block_bitmap(fs, "reserved blocks",
 478                                               &rfs->reserve_blocks);
 479         if (retval)
 480                 return retval;
 481
 482         retval = ext2fs_allocate_block_bitmap(fs, "blocks to be moved",
 483                                               &rfs->move_blocks);
 484         if (retval)
 485                 return retval;
 486
 487         retval = mark_table_blocks(fs, &meta_bmap);
 488         if (retval)
 489                 return retval;
 490
 491         fs = rfs->new_fs;
 492
 493         /*
 494          * If we're shrinking the filesystem, we need to move all of
 495          * the blocks that don't fit any more
 496          */
 497         for (blk = fs->super->s_blocks_count;
 498              blk < old_fs->super->s_blocks_count; blk++) {
 499                 if (ext2fs_test_block_bitmap(old_fs->block_map, blk) &&
 500                     !ext2fs_test_block_bitmap(meta_bmap, blk)) {
 501                         ext2fs_mark_block_bitmap(rfs->move_blocks, blk);
 502                         rfs->needed_blocks++;
 503                 }
 504                 ext2fs_mark_block_bitmap(rfs->reserve_blocks, blk);
 505         }
 506
 507         old_blocks = old_fs->desc_blocks;
 508         new_blocks = fs->desc_blocks;
 509
 510         if (old_blocks == new_blocks) {
 511                 retval = 0;
 512                 goto errout;
 513         }
 514
 515         max = fs->group_desc_count;
 516         if (max > old_fs->group_desc_count)
 517                 max = old_fs->group_desc_count;
 518         group_blk = old_fs->super->s_first_data_block;
 519         /*
 520          * If we're reducing the number of descriptor blocks, this
 521          * makes life easy.  :-)   We just have to mark some extra
 522          * blocks as free.
 523          */
 524         if (old_blocks > new_blocks) {
 525                 for (i = 0; i < max; i++) {
 526                         if (!ext2fs_bg_has_super(fs, i)) {
 527                                 group_blk += fs->super->s_blocks_per_group;
 528                                 continue;
 529                         }
 530                         for (blk = group_blk+1+new_blocks;
 531                              blk < group_blk+1+old_blocks; blk++) {
 532                                 ext2fs_unmark_block_bitmap(fs->block_map,
 533                                                            blk);
 534                                 rfs->needed_blocks--;
 535                         }
 536                         group_blk += fs->super->s_blocks_per_group;
 537                 }
 538                 retval = 0;
 539                 goto errout;
 540         }
 541         /*
 542          * If we're increasing the number of descriptor blocks, life
 543          * gets interesting....
 544          */
 545         for (i = 0; i < max; i++) {
 546                 if (!ext2fs_bg_has_super(fs, i))
 547                         goto next_group;
 548
 549                 for (blk = group_blk;
 550                      blk < group_blk + 1 + new_blocks; blk++) {
 551                         ext2fs_mark_block_bitmap(rfs->reserve_blocks, blk);
 552                         ext2fs_mark_block_bitmap(fs->block_map, blk);
 553
 554                         /*
 555                          * Check to see if we overlap with the inode
 556                          * or block bitmap, or the inode tables.  If
 557                          * not, and the block is in use, then mark it
 558                          * as a block to be moved.
 559                          */
 560                         if (IS_BLOCK_BM(fs, i, blk)) {
 561                                 FS_BLOCK_BM(fs, i) = 0;
 562                                 rfs->needed_blocks++;
 563                         } else if (IS_INODE_BM(fs, i, blk)) {
 564                                 FS_INODE_BM(fs, i) = 0;
 565                                 rfs->needed_blocks++;
 566                         } else if (IS_INODE_TB(fs, i, blk)) {
 567                                 FS_INODE_TB(fs, i) = 0;
 568                                 rfs->needed_blocks++;
 569                         } else if (ext2fs_test_block_bitmap(old_fs->block_map,
 570                                                             blk) &&
 571                                    !ext2fs_test_block_bitmap(meta_bmap, blk)) {
 572                                 ext2fs_mark_block_bitmap(rfs->move_blocks,
 573                                                          blk);
 574                                 rfs->needed_blocks++;
 575                         }
 576                 }
 577                 if (fs->group_desc[i].bg_inode_table &&
 578                     fs->group_desc[i].bg_inode_bitmap &&
 579                     fs->group_desc[i].bg_block_bitmap)
 580                         goto next_group;
 581
 582                 /*
 583                  * Reserve the existing meta blocks that we know
 584                  * aren't to be moved.
 585                  */
 586                 if (fs->group_desc[i].bg_block_bitmap)
 587                         ext2fs_mark_block_bitmap(rfs->reserve_blocks,
 588                                  fs->group_desc[i].bg_block_bitmap);
 589                 if (fs->group_desc[i].bg_inode_bitmap)
 590                         ext2fs_mark_block_bitmap(rfs->reserve_blocks,
 591                                  fs->group_desc[i].bg_inode_bitmap);
 592                 if (fs->group_desc[i].bg_inode_table)
 593                         for (blk = fs->group_desc[i].bg_inode_table, j=0;
 594                              j < fs->inode_blocks_per_group ; j++, blk++)
 595                                 ext2fs_mark_block_bitmap(rfs->reserve_blocks,
 596                                                          blk);
 597
 598                 /*
 599                  * Allocate the missing data structures
 600                  */
 601                 retval = ext2fs_allocate_group_table(fs, i,
 602                                                      rfs->reserve_blocks);
 603                 if (retval)
 604                         goto errout;
 605
 606                 /*
 607                  * For those structures that have changed, we need to
 608                  * do bookkeepping.
 609                  */
 610                 if (FS_BLOCK_BM(old_fs, i) !=
 611                     (blk = FS_BLOCK_BM(fs, i))) {
 612                         ext2fs_mark_block_bitmap(fs->block_map, blk);
 613                         if (ext2fs_test_block_bitmap(old_fs->block_map, blk) &&
 614                             !ext2fs_test_block_bitmap(meta_bmap, blk))
 615                                 ext2fs_mark_block_bitmap(rfs->move_blocks,
 616                                                          blk);
 617                 }
 618                 if (FS_INODE_BM(old_fs, i) !=
 619                     (blk = FS_INODE_BM(fs, i))) {
 620                         ext2fs_mark_block_bitmap(fs->block_map, blk);
 621                         if (ext2fs_test_block_bitmap(old_fs->block_map, blk) &&
 622                             !ext2fs_test_block_bitmap(meta_bmap, blk))
 623                                 ext2fs_mark_block_bitmap(rfs->move_blocks,
 624                                                          blk);
 625                 }
 626
 627                 /*
 628                  * The inode table, if we need to relocate it, is
 629                  * handled specially.  We have to reserve the blocks
 630                  * for both the old and the new inode table, since we
 631                  * can't have the inode table be destroyed during the
 632                  * block relocation phase.
 633                  */
 634                 if (FS_INODE_TB(fs, i) == FS_INODE_TB(old_fs, i))
 635                         goto next_group; /* inode table not moved */
 636
 637                 rfs->needed_blocks += fs->inode_blocks_per_group;
 638
 639                 /*
 640                  * Mark the new inode table as in use in the new block
 641                  * allocation bitmap, and move any blocks that might
 642                  * be necessary.
 643                  */
 644                 for (blk = fs->group_desc[i].bg_inode_table, j=0;
 645                      j < fs->inode_blocks_per_group ; j++, blk++) {
 646                         ext2fs_mark_block_bitmap(fs->block_map, blk);
 647                         if (ext2fs_test_block_bitmap(old_fs->block_map, blk) &&
 648                             !ext2fs_test_block_bitmap(meta_bmap, blk))
 649                                 ext2fs_mark_block_bitmap(rfs->move_blocks,
 650                                                          blk);
 651                 }
 652
 653                 /*
 654                  * Make sure the old inode table is reserved in the
 655                  * block reservation bitmap.
 656                  */
 657                 for (blk = rfs->old_fs->group_desc[i].bg_inode_table, j=0;
 658                      j < fs->inode_blocks_per_group ; j++, blk++)
 659                         ext2fs_mark_block_bitmap(rfs->reserve_blocks, blk);
 660
 661         next_group:
 662                 group_blk += rfs->new_fs->super->s_blocks_per_group;
 663         }
 664         retval = 0;
 665
 666 errout:
 667         if (meta_bmap)
 668                 ext2fs_free_block_bitmap(meta_bmap);
 669
 670         return retval;
 671 }
 672
 673 /*
 674  * This helper function tries to allocate a new block.  We try to
 675  * avoid hitting the original group descriptor blocks at least at
 676  * first, since we want to make it possible to recover from a badly
 677  * aborted resize operation as much as possible.
 678  *
 679  * In the future, I may further modify this routine to balance out
 680  * where we get the new blocks across the various block groups.
 681  * Ideally we would allocate blocks that corresponded with the block
 682  * group of the containing inode, and keep contiguous blocks
 683  * together.  However, this very difficult to do efficiently, since we
 684  * don't have the necessary information up front.
 685  */
 686
 687 #define AVOID_OLD       1
 688 #define DESPERATION     2
 689
 690 static void init_block_alloc(ext2_resize_t rfs)
 691 {
 692         rfs->alloc_state = AVOID_OLD;
 693         rfs->new_blk = rfs->new_fs->super->s_first_data_block;
 694 }
 695
 696 static blk_t get_new_block(ext2_resize_t rfs)
 697 {
 698         ext2_filsys     fs = rfs->new_fs;
 699
 700         while (1) {
 701                 if (rfs->new_blk >= fs->super->s_blocks_count) {
 702                         if (rfs->alloc_state == DESPERATION)
 703                                 return 0;
 704
 705 #ifdef RESIZE2FS_DEBUG
 706                         if (rfs->flags & RESIZE_DEBUG_BMOVE)
 707                                 printf("Going into desperation "
 708                                        "mode for block allocations\n");
 709 #endif
 710                         rfs->alloc_state = DESPERATION;
 711                         rfs->new_blk = fs->super->s_first_data_block;
 712                         continue;
 713                 }
 714                 if (ext2fs_test_block_bitmap(fs->block_map, rfs->new_blk) ||
 715                     ext2fs_test_block_bitmap(rfs->reserve_blocks,
 716                                              rfs->new_blk) ||
 717                     ((rfs->alloc_state == AVOID_OLD) &&
 718                      ext2fs_test_block_bitmap(rfs->old_fs->block_map,
 719                                               rfs->new_blk))) {
 720                         rfs->new_blk++;
 721                         continue;
 722                 }
 723                 return rfs->new_blk;
 724         }
 725 }
 726
 727 static errcode_t block_mover(ext2_resize_t rfs)
 728 {
 729         blk_t                   blk, old_blk, new_blk;
 730         ext2_filsys             fs = rfs->new_fs;
 731         ext2_filsys             old_fs = rfs->old_fs;
 732         errcode_t               retval;
 733         int                     size, c;
 734         int                     to_move, moved;
 735
 736         new_blk = fs->super->s_first_data_block;
 737         if (!rfs->itable_buf) {
 738                 retval = ext2fs_get_mem(fs->blocksize *
 739                                         fs->inode_blocks_per_group,
 740                                         (void **) &rfs->itable_buf);
 741                 if (retval)
 742                         return retval;
 743         }
 744         retval = ext2fs_create_extent_table(&rfs->bmap, 0);
 745         if (retval)
 746                 return retval;
 747
 748         /*
 749          * The first step is to figure out where all of the blocks
 750          * will go.
 751          */
 752         to_move = moved = 0;
 753         init_block_alloc(rfs);
 754         for (blk = old_fs->super->s_first_data_block;
 755              blk < old_fs->super->s_blocks_count; blk++) {
 756                 if (!ext2fs_test_block_bitmap(old_fs->block_map, blk))
 757                         continue;
 758                 if (!ext2fs_test_block_bitmap(rfs->move_blocks, blk))
 759                         continue;
 760
 761                 new_blk = get_new_block(rfs);
 762                 if (!new_blk) {
 763                         retval = ENOSPC;
 764                         goto errout;
 765                 }
 766                 ext2fs_mark_block_bitmap(fs->block_map, new_blk);
 767                 ext2fs_add_extent_entry(rfs->bmap, blk, new_blk);
 768                 to_move++;
 769         }
 770
 771         if (to_move == 0) {
 772                 retval = 0;
 773                 goto errout;
 774         }
 775
 776         /*
 777          * Step two is to actually move the blocks
 778          */
 779         retval =  ext2fs_iterate_extent(rfs->bmap, 0, 0, 0);
 780         if (retval) goto errout;
 781
 782         if (rfs->progress)
 783                 (rfs->progress)(rfs, E2_RSZ_BLOCK_RELOC_PASS, 0, to_move);
 784
 785         while (1) {
 786                 retval = ext2fs_iterate_extent(rfs->bmap, &old_blk, &new_blk, &size);
 787                 if (retval) goto errout;
 788                 if (!size)
 789                         break;
 790 #ifdef RESIZE2FS_DEBUG
 791                 if (rfs->flags & RESIZE_DEBUG_BMOVE)
 792                         printf("Moving %d blocks %u->%u\n", size,
 793                                old_blk, new_blk);
 794 #endif
 795                 do {
 796                         c = size;
 797                         if (c > fs->inode_blocks_per_group)
 798                                 c = fs->inode_blocks_per_group;
 799                         retval = io_channel_read_blk(fs->io, old_blk, c,
 800                                                      rfs->itable_buf);
 801                         if (retval) goto errout;
 802                         retval = io_channel_write_blk(fs->io, new_blk, c,
 803                                                       rfs->itable_buf);
 804                         if (retval) goto errout;
 805                         size -= c;
 806                         new_blk += c;
 807                         old_blk += c;
 808                         moved += c;
 809                         if (rfs->progress) {
 810                                 io_channel_flush(fs->io);
 811                                 (rfs->progress)(rfs, E2_RSZ_BLOCK_RELOC_PASS,
 812                                                 moved, to_move);
 813                         }
 814                 } while (size > 0);
 815                 io_channel_flush(fs->io);
 816         }
 817
 818 errout:
 819         return retval;
 820 }
 821
 822
 823 /* --------------------------------------------------------------------
 824  *
 825  * Resize processing, phase 3
 826  *
 827  * --------------------------------------------------------------------
 828  */
 829
 830
 831 struct process_block_struct {
 832         ext2_resize_t           rfs;
 833         ino_t                   ino;
 834         struct ext2_inode *     inode;
 835         errcode_t               error;
 836         int                     is_dir;
 837         int                     changed;
 838 };
 839
 840 static int process_block(ext2_filsys fs, blk_t  *block_nr,
 841                          int blockcnt, blk_t ref_block,
 842                          int ref_offset, void *priv_data)
 843 {
 844         struct process_block_struct *pb;
 845         errcode_t       retval;
 846         blk_t           block, new_block;
 847         int             ret = 0;
 848
 849         pb = (struct process_block_struct *) priv_data;
 850         block = *block_nr;
 851         if (pb->rfs->bmap) {
 852                 new_block = ext2fs_extent_translate(pb->rfs->bmap, block);
 853                 if (new_block) {
 854                         *block_nr = new_block;
 855                         ret |= BLOCK_CHANGED;
 856                         pb->changed = 1;
 857 #ifdef RESIZE2FS_DEBUG
 858                         if (pb->rfs->flags & RESIZE_DEBUG_BMOVE)
 859                                 printf("ino=%ld, blockcnt=%d, %u->%u\n",
 860                                        pb->ino, blockcnt, block, new_block);
 861 #endif
 862                         block = new_block;
 863                 }
 864         }
 865         if (pb->is_dir) {
 866                 retval = ext2fs_add_dir_block(fs->dblist, pb->ino,
 867                                               block, blockcnt);
 868                 if (retval) {
 869                         pb->error = retval;
 870                         ret |= BLOCK_ABORT;
 871                 }
 872         }
 873         return ret;
 874 }
 875
 876 /*
 877  * Progress callback
 878  */
 879 static errcode_t progress_callback(ext2_filsys fs, ext2_inode_scan scan,
 880                                    dgrp_t group, void * priv_data)
 881 {
 882         ext2_resize_t rfs = (ext2_resize_t) priv_data;
 883
 884         /*
 885          * This check is to protect against old ext2 libraries.  It
 886          * shouldn't be needed against new libraries.
 887          */
 888         if ((group+1) == 0)
 889                 return 0;
 890
 891         if (rfs->progress) {
 892                 io_channel_flush(fs->io);
 893                 (rfs->progress)(rfs, E2_RSZ_INODE_SCAN_PASS,
 894                                 group+1, fs->group_desc_count);
 895         }
 896
 897         return 0;
 898 }
 899
 900 static errcode_t inode_scan_and_fix(ext2_resize_t rfs)
 901 {
 902         struct process_block_struct     pb;
 903         ino_t                   ino, new_inode;
 904         struct ext2_inode       inode;
 905         ext2_inode_scan         scan = NULL;
 906         errcode_t               retval;
 907         int                     group;
 908         char                    *block_buf = 0;
 909         ino_t                   start_to_move;
 910
 911         if ((rfs->old_fs->group_desc_count <=
 912              rfs->new_fs->group_desc_count) &&
 913             !rfs->bmap)
 914                 return 0;
 915
 916         retval = ext2fs_open_inode_scan(rfs->old_fs, 0, &scan);
 917         if (retval) goto errout;
 918
 919         retval = ext2fs_init_dblist(rfs->old_fs, 0);
 920         if (retval) goto errout;
 921         retval = ext2fs_get_mem(rfs->old_fs->blocksize * 3,
 922                                 (void **) &block_buf);
 923         if (retval) goto errout;
 924
 925         start_to_move = (rfs->new_fs->group_desc_count *
 926                          rfs->new_fs->super->s_inodes_per_group);
 927
 928         if (rfs->progress)
 929                 (rfs->progress)(rfs, E2_RSZ_INODE_SCAN_PASS,
 930                                 0, rfs->old_fs->group_desc_count);
 931
 932         ext2fs_set_inode_callback(scan, progress_callback, (void *) rfs);
 933         pb.rfs = rfs;
 934         pb.inode = &inode;
 935         pb.error = 0;
 936         new_inode = EXT2_FIRST_INODE(rfs->new_fs->super);
 937         /*
 938          * First, copy all of the inodes that need to be moved
 939          * elsewhere in the inode table
 940          */
 941         while (1) {
 942                 retval = ext2fs_get_next_inode(scan, &ino, &inode);
 943                 if (retval) goto errout;
 944                 if (!ino)
 945                         break;
 946
 947                 if (inode.i_links_count == 0)
 948                         continue; /* inode not in use */
 949
 950                 pb.is_dir = LINUX_S_ISDIR(inode.i_mode);
 951                 pb.changed = 0;
 952
 953                 if (ext2fs_inode_has_valid_blocks(&inode) &&
 954                     (rfs->bmap || pb.is_dir)) {
 955                         pb.ino = ino;
 956                         retval = ext2fs_block_iterate2(rfs->old_fs,
 957                                                        ino, 0, block_buf,
 958                                                        process_block, &pb);
 959                         if (retval)
 960                                 goto errout;
 961                         if (pb.error) {
 962                                 retval = pb.error;
 963                                 goto errout;
 964                         }
 965                 }
 966
 967                 if (ino <= start_to_move)
 968                         continue; /* Don't need to move it. */
 969
 970                 /*
 971                  * Find a new inode
 972                  */
 973                 while (1) {
 974                         if (!ext2fs_test_inode_bitmap(rfs->new_fs->inode_map,
 975                                                       new_inode))
 976                                 break;
 977                         new_inode++;
 978                         if (new_inode > rfs->new_fs->super->s_inodes_count) {
 979                                 retval = ENOSPC;
 980                                 goto errout;
 981                         }
 982                 }
 983                 ext2fs_mark_inode_bitmap(rfs->new_fs->inode_map, new_inode);
 984                 if (pb.changed) {
 985                         /* Get the new version of the inode */
 986                         retval = ext2fs_read_inode(rfs->old_fs, ino, &inode);
 987                         if (retval) goto errout;
 988                 }
 989                 retval = ext2fs_write_inode(rfs->old_fs, new_inode, &inode);
 990                 if (retval) goto errout;
 991
 992                 group = (new_inode-1) / EXT2_INODES_PER_GROUP(rfs->new_fs->super);
 993                 if (LINUX_S_ISDIR(inode.i_mode))
 994                         rfs->new_fs->group_desc[group].bg_used_dirs_count++;
 995
 996 #ifdef RESIZE2FS_DEBUG
 997                 if (rfs->flags & RESIZE_DEBUG_INODEMAP)
 998                         printf("Inode moved %ld->%ld\n", ino, new_inode);
 999 #endif
1000                 if (!rfs->imap) {
1001                         retval = ext2fs_create_extent_table(&rfs->imap, 0);
1002                         if (retval)
1003                                 goto errout;
1004                 }
1005                 ext2fs_add_extent_entry(rfs->imap, ino, new_inode);
1006         }
1007         io_channel_flush(rfs->old_fs->io);
1008
1009 errout:
1010         if (rfs->bmap) {
1011                 ext2fs_free_extent_table(rfs->bmap);
1012                 rfs->bmap = 0;
1013         }
1014         if (scan)
1015                 ext2fs_close_inode_scan(scan);
1016         if (block_buf)
1017                 ext2fs_free_mem((void **) &block_buf);
1018         return retval;
1019 }
1020
1021 /* --------------------------------------------------------------------
1022  *
1023  * Resize processing, phase 4.
1024  *
1025  * --------------------------------------------------------------------
1026  */
1027
1028 struct istruct {
1029         ext2_resize_t rfs;
1030         unsigned long   max;
1031         int             num;
1032 };
1033
1034 static int check_and_change_inodes(ino_t dir, int entry,
1035                                    struct ext2_dir_entry *dirent, int offset,
1036                                    int  blocksize, char *buf, void *priv_data)
1037 {
1038         struct istruct *is = (struct istruct *) priv_data;
1039         ino_t   new_inode;
1040
1041         if (is->rfs->progress && offset == 0) {
1042                 io_channel_flush(is->rfs->old_fs->io);
1043                 (is->rfs->progress)(is->rfs, E2_RSZ_INODE_REF_UPD_PASS,
1044                                 ++is->num, is->max);
1045         }
1046
1047         if (!dirent->inode)
1048                 return 0;
1049
1050         new_inode = ext2fs_extent_translate(is->rfs->imap, dirent->inode);
1051
1052         if (!new_inode)
1053                 return 0;
1054 #ifdef RESIZE2FS_DEBUG
1055         if (is->rfs->flags & RESIZE_DEBUG_INODEMAP)
1056                 printf("Inode translate (dir=%ld, name=%.*s, %u->%ld)\n",
1057                        dir, dirent->name_len, dirent->name,
1058                        dirent->inode, new_inode);
1059 #endif
1060
1061         dirent->inode = new_inode;
1062
1063         return DIRENT_CHANGED;
1064 }
1065
1066 static errcode_t inode_ref_fix(ext2_resize_t rfs)
1067 {
1068         errcode_t               retval;
1069         struct istruct          is;
1070
1071         if (!rfs->imap)
1072                 return 0;
1073
1074         /*
1075          * Now, we iterate over all of the directories to update the
1076          * inode references
1077          */
1078         is.num = 0;
1079         is.max = ext2fs_dblist_count(rfs->old_fs->dblist);
1080         is.rfs = rfs;
1081
1082         if (rfs->progress)
1083                 (rfs->progress)(rfs, E2_RSZ_INODE_REF_UPD_PASS,
1084                                 0, is.max);
1085
1086         retval = ext2fs_dblist_dir_iterate(rfs->old_fs->dblist,
1087                                            DIRENT_FLAG_INCLUDE_EMPTY, 0,
1088                                            check_and_change_inodes, &is);
1089
1090         ext2fs_free_extent_table(rfs->imap);
1091         rfs->imap = 0;
1092         return retval;
1093 }
1094
1095
1096 /* --------------------------------------------------------------------
1097  *
1098  * Resize processing, phase 5.
1099  *
1100  * In this phase we actually move the inode table around, and then
1101  * update the summary statistics.  This is scary, since aborting here
1102  * will potentially scramble the filesystem.  (We are moving the
1103  * inode tables around in place, and so the potential for lost data,
1104  * or at the very least scrambling the mapping between filenames and
1105  * inode numbers is very high in case of a power failure here.)
1106  * --------------------------------------------------------------------
1107  */
1108
1109
1110 /*
1111  * A very scary routine --- this one moves the inode table around!!!
1112  *
1113  * After this you have to use the rfs->new_fs file handle to read and
1114  * write inodes.
1115  */
1116 static errcode_t move_itables(ext2_resize_t rfs)
1117 {
1118         int             i, n, num, max, size, diff;
1119         ext2_filsys     fs = rfs->new_fs;
1120         char            *cp;
1121         blk_t           old_blk, new_blk;
1122         errcode_t       retval;
1123         int             to_move, moved;
1124
1125         max = fs->group_desc_count;
1126         if (max > rfs->old_fs->group_desc_count)
1127                 max = rfs->old_fs->group_desc_count;
1128
1129         size = fs->blocksize * fs->inode_blocks_per_group;
1130         if (!rfs->itable_buf) {
1131                 retval = ext2fs_get_mem(size, (void **) &rfs->itable_buf);
1132                 if (retval)
1133                         return retval;
1134         }
1135
1136         /*
1137          * Figure out how many inode tables we need to move
1138          */
1139         to_move = moved = 0;
1140         for (i=0; i < max; i++)
1141                 if (rfs->old_fs->group_desc[i].bg_inode_table !=
1142                     fs->group_desc[i].bg_inode_table)
1143                         to_move++;
1144
1145         if (to_move == 0)
1146                 return 0;
1147
1148         if (rfs->progress)
1149                 rfs->progress(rfs, E2_RSZ_MOVE_ITABLE_PASS, 0, to_move);
1150
1151         rfs->old_fs->flags |= EXT2_FLAG_MASTER_SB_ONLY;
1152
1153         for (i=0; i < max; i++) {
1154                 old_blk = rfs->old_fs->group_desc[i].bg_inode_table;
1155                 new_blk = fs->group_desc[i].bg_inode_table;
1156                 diff = new_blk - old_blk;
1157
1158 #ifdef RESIZE2FS_DEBUG
1159                 if (rfs->flags & RESIZE_DEBUG_ITABLEMOVE)
1160                         printf("Itable move group %d block "
1161                                "%u->%u (diff %d)\n",
1162                                i, old_blk, new_blk, diff);
1163 #endif
1164
1165                 if (!diff)
1166                         continue;
1167
1168                 retval = io_channel_read_blk(fs->io, old_blk,
1169                                              fs->inode_blocks_per_group,
1170                                              rfs->itable_buf);
1171                 if (retval)
1172                         goto errout;
1173                 /*
1174                  * The end of the inode table segment often contains
1175                  * all zeros, and we're often only moving the inode
1176                  * table down a block or two.  If so, we can optimize
1177                  * things by not rewriting blocks that we know to be zero
1178                  * already.
1179                  */
1180                 for (cp = rfs->itable_buf+size, n=0; n < size; n++, cp--)
1181                         if (*cp)
1182                                 break;
1183                 n = n >> EXT2_BLOCK_SIZE_BITS(fs->super);
1184 #ifdef RESIZE2FS_DEBUG
1185                 if (rfs->flags & RESIZE_DEBUG_ITABLEMOVE)
1186                         printf("%d blocks of zeros...\n", n);
1187 #endif
1188                 num = fs->inode_blocks_per_group;
1189                 if (n > diff)
1190                         num -= n;
1191
1192                 retval = io_channel_write_blk(fs->io, new_blk,
1193                                               num, rfs->itable_buf);
1194                 if (retval) {
1195                         io_channel_write_blk(fs->io, old_blk,
1196                                              num, rfs->itable_buf);
1197                         goto errout;
1198                 }
1199                 if (n > diff) {
1200                         retval = io_channel_write_blk(fs->io,
1201                               old_blk + fs->inode_blocks_per_group,
1202                               diff, (rfs->itable_buf +
1203                                      (fs->inode_blocks_per_group - diff) *
1204                                      fs->blocksize));
1205                         if (retval)
1206                                 goto errout;
1207                 }
1208                 rfs->old_fs->group_desc[i].bg_inode_table = new_blk;
1209                 ext2fs_mark_super_dirty(rfs->old_fs);
1210                 if (rfs->progress) {
1211                         ext2fs_flush(rfs->old_fs);
1212                         rfs->progress(rfs, E2_RSZ_MOVE_ITABLE_PASS,
1213                                       ++moved, to_move);
1214                 }
1215         }
1216         ext2fs_flush(fs);
1217 #ifdef RESIZE2FS_DEBUG
1218         if (rfs->flags & RESIZE_DEBUG_ITABLEMOVE)
1219                 printf("Inode table move finished.\n");
1220 #endif
1221         return 0;
1222
1223 errout:
1224         return retval;
1225 }
1226
1227 /*
1228  * Finally, recalculate the summary information
1229  */
1230 static errcode_t ext2fs_calculate_summary_stats(ext2_filsys fs)
1231 {
1232         blk_t   blk;
1233         ino_t   ino;
1234         int     group = 0;
1235         int     count = 0;
1236         int     total_free = 0;
1237         int     group_free = 0;
1238
1239         /*
1240          * First calculate the block statistics
1241          */
1242         for (blk = fs->super->s_first_data_block;
1243              blk < fs->super->s_blocks_count; blk++) {
1244                 if (!ext2fs_fast_test_block_bitmap(fs->block_map, blk)) {
1245                         group_free++;
1246                         total_free++;
1247                 }
1248                 count++;
1249                 if ((count == fs->super->s_blocks_per_group) ||
1250                     (blk == fs->super->s_blocks_count-1)) {
1251                         fs->group_desc[group++].bg_free_blocks_count =
1252                                 group_free;
1253                         count = 0;
1254                         group_free = 0;
1255                 }
1256         }
1257         fs->super->s_free_blocks_count = total_free;
1258
1259         /*
1260          * Next, calculate the inode statistics
1261          */
1262         group_free = 0;
1263         total_free = 0;
1264         count = 0;
1265         group = 0;
1266         for (ino = 1; ino <= fs->super->s_inodes_count; ino++) {
1267                 if (!ext2fs_fast_test_inode_bitmap(fs->inode_map, ino)) {
1268                         group_free++;
1269                         total_free++;
1270                 }
1271                 count++;
1272                 if ((count == fs->super->s_inodes_per_group) ||
1273                     (ino == fs->super->s_inodes_count)) {
1274                         fs->group_desc[group++].bg_free_inodes_count =
1275                                 group_free;
1276                         count = 0;
1277                         group_free = 0;
1278                 }
1279         }
1280         fs->super->s_free_inodes_count = total_free;
1281         ext2fs_mark_super_dirty(fs);
1282         return 0;
1283 }