resize/resize2fs.c

   1 /*
   2  * resize2fs.c --- ext2 main routine
   3  *
   4  * Copyright (C) 1997, 1998 by Theodore Ts'o and
   5  *      PowerQuest, Inc.
   6  *
   7  * Copyright (C) 1999, 2000 by Theosore Ts'o
   8  *
   9  * %Begin-Header%
  10  * This file may be redistributed under the terms of the GNU Public
  11  * License.
  12  * %End-Header%
  13  */
  14
  15 /*
  16  * Resizing a filesystem consists of the following phases:
  17  *
  18  *      1.  Adjust superblock and write out new parts of the inode
  19  *              table
  20  *      2.  Determine blocks which need to be relocated, and copy the
  21  *              contents of blocks from their old locations to the new ones.
  22  *      3.  Scan the inode table, doing the following:
  23  *              a.  If blocks have been moved, update the block
  24  *                      pointers in the inodes and indirect blocks to
  25  *                      point at the new block locations.
  26  *              b.  If parts of the inode table need to be evacuated,
  27  *                      copy inodes from their old locations to their
  28  *                      new ones.
  29  *              c.  If (b) needs to be done, note which blocks contain
  30  *                      directory information, since we will need to
  31  *                      update the directory information.
  32  *      4.  Update the directory blocks with the new inode locations.
  33  *      5.  Move the inode tables, if necessary.
  34  */
  35
  36 #include "resize2fs.h"
  37 #include <time.h>
  38
  39 #ifdef __linux__                        /* Kludge for debugging */
  40 #define RESIZE2FS_DEBUG
  41 #endif
  42
  43 static void fix_uninit_block_bitmaps(ext2_filsys fs);
  44 static errcode_t adjust_superblock(ext2_resize_t rfs, blk_t new_size);
  45 static errcode_t blocks_to_move(ext2_resize_t rfs);
  46 static errcode_t block_mover(ext2_resize_t rfs);
  47 static errcode_t inode_scan_and_fix(ext2_resize_t rfs);
  48 static errcode_t inode_ref_fix(ext2_resize_t rfs);
  49 static errcode_t move_itables(ext2_resize_t rfs);
  50 static errcode_t fix_resize_inode(ext2_filsys fs);
  51 static errcode_t ext2fs_calculate_summary_stats(ext2_filsys fs);
  52
  53 /*
  54  * Some helper CPP macros
  55  */
  56 #define FS_BLOCK_BM(fs, i) ((fs)->group_desc[(i)].bg_block_bitmap)
  57 #define FS_INODE_BM(fs, i) ((fs)->group_desc[(i)].bg_inode_bitmap)
  58 #define FS_INODE_TB(fs, i) ((fs)->group_desc[(i)].bg_inode_table)
  59
  60 #define IS_BLOCK_BM(fs, i, blk) ((blk) == FS_BLOCK_BM((fs),(i)))
  61 #define IS_INODE_BM(fs, i, blk) ((blk) == FS_INODE_BM((fs),(i)))
  62
  63 #define IS_INODE_TB(fs, i, blk) (((blk) >= FS_INODE_TB((fs), (i))) && \
  64                                  ((blk) < (FS_INODE_TB((fs), (i)) + \
  65                                            (fs)->inode_blocks_per_group)))
  66
  67 #define META_OVERHEAD(fs) (2 + (fs)->inode_blocks_per_group)
  68 #define SUPER_OVERHEAD(fs) (1 + (fs)->desc_blocks +\
  69                             (fs)->super->s_reserved_gdt_blocks)
  70
  71 /*
  72  * This is the top-level routine which does the dirty deed....
  73  */
  74 errcode_t resize_fs(ext2_filsys fs, blk_t *new_size, int flags,
  75                     errcode_t (*progress)(ext2_resize_t rfs, int pass,
  76                                           unsigned long cur,
  77                                           unsigned long max_val))
  78 {
  79         ext2_resize_t   rfs;
  80         errcode_t       retval;
  81
  82         retval = ext2fs_read_bitmaps(fs);
  83         if (retval)
  84                 return retval;
  85
  86         /*
  87          * Create the data structure
  88          */
  89         retval = ext2fs_get_mem(sizeof(struct ext2_resize_struct), &rfs);
  90         if (retval)
  91                 return retval;
  92         memset(rfs, 0, sizeof(struct ext2_resize_struct));
  93
  94         fix_uninit_block_bitmaps(fs);
  95         fs->priv_data = rfs;
  96         rfs->old_fs = fs;
  97         rfs->flags = flags;
  98         rfs->itable_buf  = 0;
  99         rfs->progress = progress;
 100         retval = ext2fs_dup_handle(fs, &rfs->new_fs);
 101         if (retval)
 102                 goto errout;
 103
 104         retval = adjust_superblock(rfs, *new_size);
 105         if (retval)
 106                 goto errout;
 107
 108         fix_uninit_block_bitmaps(rfs->new_fs);
 109         /* Clear the block bitmap uninit flag for the last block group */
 110         rfs->new_fs->group_desc[rfs->new_fs->group_desc_count-1].bg_flags &=
 111                 ~EXT2_BG_BLOCK_UNINIT;
 112
 113         *new_size = rfs->new_fs->super->s_blocks_count;
 114
 115         retval = blocks_to_move(rfs);
 116         if (retval)
 117                 goto errout;
 118
 119 #ifdef RESIZE2FS_DEBUG
 120         if (rfs->flags & RESIZE_DEBUG_BMOVE)
 121                 printf("Number of free blocks: %u/%u, Needed: %d\n",
 122                        rfs->old_fs->super->s_free_blocks_count,
 123                        rfs->new_fs->super->s_free_blocks_count,
 124                        rfs->needed_blocks);
 125 #endif
 126
 127         retval = block_mover(rfs);
 128         if (retval)
 129                 goto errout;
 130
 131         retval = inode_scan_and_fix(rfs);
 132         if (retval)
 133                 goto errout;
 134
 135         retval = inode_ref_fix(rfs);
 136         if (retval)
 137                 goto errout;
 138
 139         retval = move_itables(rfs);
 140         if (retval)
 141                 goto errout;
 142
 143         retval = ext2fs_calculate_summary_stats(rfs->new_fs);
 144         if (retval)
 145                 goto errout;
 146
 147         retval = fix_resize_inode(rfs->new_fs);
 148         if (retval)
 149                 goto errout;
 150
 151         rfs->new_fs->flags &= ~EXT2_FLAG_MASTER_SB_ONLY;
 152         retval = ext2fs_close(rfs->new_fs);
 153         if (retval)
 154                 goto errout;
 155
 156         rfs->flags = flags;
 157
 158         ext2fs_free(rfs->old_fs);
 159         if (rfs->itable_buf)
 160                 ext2fs_free_mem(&rfs->itable_buf);
 161         if (rfs->reserve_blocks)
 162                 ext2fs_free_block_bitmap(rfs->reserve_blocks);
 163         if (rfs->move_blocks)
 164                 ext2fs_free_block_bitmap(rfs->move_blocks);
 165         ext2fs_free_mem(&rfs);
 166
 167         return 0;
 168
 169 errout:
 170         if (rfs->new_fs)
 171                 ext2fs_free(rfs->new_fs);
 172         if (rfs->itable_buf)
 173                 ext2fs_free_mem(&rfs->itable_buf);
 174         ext2fs_free_mem(&rfs);
 175         return retval;
 176 }
 177
 178 /*
 179  * Clean up the bitmaps for unitialized bitmaps
 180  */
 181 static void fix_uninit_block_bitmaps(ext2_filsys fs)
 182 {
 183         blk_t           i, blk, super_blk, old_desc_blk, new_desc_blk;
 184         int             old_desc_blocks;
 185         dgrp_t          g;
 186
 187         if (!(EXT2_HAS_RO_COMPAT_FEATURE(fs->super,
 188                                          EXT4_FEATURE_RO_COMPAT_GDT_CSUM)))
 189                 return;
 190
 191         for (g=0; g < fs->group_desc_count; g++) {
 192                 if (!(fs->group_desc[g].bg_flags & EXT2_BG_BLOCK_UNINIT))
 193                         continue;
 194
 195                 blk = (g * fs->super->s_blocks_per_group) +
 196                         fs->super->s_first_data_block;
 197
 198                 ext2fs_super_and_bgd_loc(fs, g, &super_blk,
 199                                          &old_desc_blk, &new_desc_blk, 0);
 200
 201                 if (fs->super->s_feature_incompat & EXT2_FEATURE_INCOMPAT_META_BG)
 202                         old_desc_blocks = fs->super->s_first_meta_bg;
 203                 else
 204                         old_desc_blocks = fs->desc_blocks +
 205                                 fs->super->s_reserved_gdt_blocks;
 206
 207                 for (i=0; i < fs->super->s_blocks_per_group; i++, blk++) {
 208                         if (blk >= fs->super->s_blocks_count)
 209                                 break;
 210                         if ((blk == super_blk) ||
 211                             (old_desc_blk && old_desc_blocks &&
 212                              (blk >= old_desc_blk) &&
 213                              (blk < old_desc_blk + old_desc_blocks)) ||
 214                             (new_desc_blk && (blk == new_desc_blk)) ||
 215                             (blk == fs->group_desc[g].bg_block_bitmap) ||
 216                             (blk == fs->group_desc[g].bg_inode_bitmap) ||
 217                             (blk >= fs->group_desc[g].bg_inode_table &&
 218                              (blk < fs->group_desc[g].bg_inode_table
 219                               + fs->inode_blocks_per_group)))
 220                                 ext2fs_fast_mark_block_bitmap(fs->block_map, blk);
 221                         else
 222                                 ext2fs_fast_unmark_block_bitmap(fs->block_map, blk);
 223                 }
 224         }
 225 }
 226
 227 /* --------------------------------------------------------------------
 228  *
 229  * Resize processing, phase 1.
 230  *
 231  * In this phase we adjust the in-memory superblock information, and
 232  * initialize any new parts of the inode table.  The new parts of the
 233  * inode table are created in virgin disk space, so we can abort here
 234  * without any side effects.
 235  * --------------------------------------------------------------------
 236  */
 237
 238 /*
 239  * If the group descriptor's bitmap and inode table blocks are valid,
 240  * release them in the new filesystem data structure, and mark them as
 241  * reserved so the old inode table blocks don't get overwritten.
 242  */
 243 static void free_gdp_blocks(ext2_filsys fs,
 244                             ext2fs_block_bitmap reserve_blocks,
 245                             struct ext2_group_desc *gdp)
 246 {
 247         blk_t   blk;
 248         int     j;
 249
 250         if (gdp->bg_block_bitmap &&
 251             (gdp->bg_block_bitmap < fs->super->s_blocks_count)) {
 252                 ext2fs_block_alloc_stats(fs, gdp->bg_block_bitmap, -1);
 253                 ext2fs_mark_block_bitmap(reserve_blocks,
 254                                          gdp->bg_block_bitmap);
 255         }
 256
 257         if (gdp->bg_inode_bitmap &&
 258             (gdp->bg_inode_bitmap < fs->super->s_blocks_count)) {
 259                 ext2fs_block_alloc_stats(fs, gdp->bg_inode_bitmap, -1);
 260                 ext2fs_mark_block_bitmap(reserve_blocks,
 261                                          gdp->bg_inode_bitmap);
 262         }
 263
 264         if (gdp->bg_inode_table == 0 ||
 265             (gdp->bg_inode_table >= fs->super->s_blocks_count))
 266                 return;
 267
 268         for (blk = gdp->bg_inode_table, j = 0;
 269              j < fs->inode_blocks_per_group; j++, blk++) {
 270                 if (blk >= fs->super->s_blocks_count)
 271                         break;
 272                 ext2fs_block_alloc_stats(fs, blk, -1);
 273                 ext2fs_mark_block_bitmap(reserve_blocks, blk);
 274         }
 275 }
 276
 277 /*
 278  * This routine is shared by the online and offline resize routines.
 279  * All of the information which is adjusted in memory is done here.
 280  *
 281  * The reserve_blocks parameter is only needed when shrinking the
 282  * filesystem.
 283  */
 284 errcode_t adjust_fs_info(ext2_filsys fs, ext2_filsys old_fs,
 285                          ext2fs_block_bitmap reserve_blocks, blk_t new_size)
 286 {
 287         errcode_t       retval;
 288         int             overhead = 0;
 289         int             rem;
 290         blk_t           blk, group_block;
 291         ext2_ino_t      real_end;
 292         int             adj, old_numblocks, numblocks, adjblocks;
 293         unsigned long   i, j, old_desc_blocks, max_group;
 294         unsigned int    meta_bg, meta_bg_size;
 295         int             has_super, csum_flag;
 296         unsigned long long new_inodes;  /* u64 to check for overflow */
 297         double          percent;
 298
 299         fs->super->s_blocks_count = new_size;
 300
 301 retry:
 302         fs->group_desc_count = ext2fs_div_ceil(fs->super->s_blocks_count -
 303                                        fs->super->s_first_data_block,
 304                                        EXT2_BLOCKS_PER_GROUP(fs->super));
 305         if (fs->group_desc_count == 0)
 306                 return EXT2_ET_TOOSMALL;
 307         fs->desc_blocks = ext2fs_div_ceil(fs->group_desc_count,
 308                                           EXT2_DESC_PER_BLOCK(fs->super));
 309
 310         /*
 311          * Overhead is the number of bookkeeping blocks per group.  It
 312          * includes the superblock backup, the group descriptor
 313          * backups, the inode bitmap, the block bitmap, and the inode
 314          * table.
 315          */
 316         overhead = (int) (2 + fs->inode_blocks_per_group);
 317
 318         if (ext2fs_bg_has_super(fs, fs->group_desc_count - 1))
 319                 overhead += 1 + fs->desc_blocks +
 320                         fs->super->s_reserved_gdt_blocks;
 321
 322         /*
 323          * See if the last group is big enough to support the
 324          * necessary data structures.  If not, we need to get rid of
 325          * it.
 326          */
 327         rem = (fs->super->s_blocks_count - fs->super->s_first_data_block) %
 328                 fs->super->s_blocks_per_group;
 329         if ((fs->group_desc_count == 1) && rem && (rem < overhead))
 330                 return EXT2_ET_TOOSMALL;
 331         if (rem && (rem < overhead+50)) {
 332                 fs->super->s_blocks_count -= rem;
 333                 goto retry;
 334         }
 335         /*
 336          * Adjust the number of inodes
 337          */
 338         new_inodes =(unsigned long long) fs->super->s_inodes_per_group * fs->group_desc_count;
 339         if (new_inodes > ~0U) {
 340                 fprintf(stderr, _("inodes (%llu) must be less than %u"),
 341                                    new_inodes, ~0U);
 342                 return EXT2_ET_TOO_MANY_INODES;
 343         }
 344         fs->super->s_inodes_count = fs->super->s_inodes_per_group *
 345                 fs->group_desc_count;
 346
 347         /*
 348          * Adjust the number of free blocks
 349          */
 350         blk = old_fs->super->s_blocks_count;
 351         if (blk > fs->super->s_blocks_count)
 352                 fs->super->s_free_blocks_count -=
 353                         (blk - fs->super->s_blocks_count);
 354         else
 355                 fs->super->s_free_blocks_count +=
 356                         (fs->super->s_blocks_count - blk);
 357
 358         /*
 359          * Adjust the number of reserved blocks
 360          */
 361         percent = (old_fs->super->s_r_blocks_count * 100.0) /
 362                 old_fs->super->s_blocks_count;
 363         fs->super->s_r_blocks_count = (unsigned int) (percent *
 364                                         fs->super->s_blocks_count / 100.0);
 365
 366         /*
 367          * Adjust the bitmaps for size
 368          */
 369         retval = ext2fs_resize_inode_bitmap(fs->super->s_inodes_count,
 370                                             fs->super->s_inodes_count,
 371                                             fs->inode_map);
 372         if (retval) goto errout;
 373
 374         real_end = ((EXT2_BLOCKS_PER_GROUP(fs->super)
 375                      * fs->group_desc_count)) - 1 +
 376                              fs->super->s_first_data_block;
 377         retval = ext2fs_resize_block_bitmap(fs->super->s_blocks_count-1,
 378                                             real_end, fs->block_map);
 379
 380         if (retval) goto errout;
 381
 382         /*
 383          * Reallocate the group descriptors as necessary.
 384          */
 385         if (old_fs->desc_blocks != fs->desc_blocks) {
 386                 retval = ext2fs_resize_mem(old_fs->desc_blocks *
 387                                            fs->blocksize,
 388                                            fs->desc_blocks * fs->blocksize,
 389                                            &fs->group_desc);
 390                 if (retval)
 391                         goto errout;
 392                 if (fs->desc_blocks > old_fs->desc_blocks)
 393                         memset((char *) fs->group_desc +
 394                                (old_fs->desc_blocks * fs->blocksize), 0,
 395                                (fs->desc_blocks - old_fs->desc_blocks) *
 396                                fs->blocksize);
 397         }
 398
 399         /*
 400          * If the resize_inode feature is set, and we are changing the
 401          * number of descriptor blocks, then adjust
 402          * s_reserved_gdt_blocks if possible to avoid needing to move
 403          * the inode table either now or in the future.
 404          */
 405         if ((fs->super->s_feature_compat &
 406              EXT2_FEATURE_COMPAT_RESIZE_INODE) &&
 407             (old_fs->desc_blocks != fs->desc_blocks)) {
 408                 int new;
 409
 410                 new = ((int) fs->super->s_reserved_gdt_blocks) +
 411                         (old_fs->desc_blocks - fs->desc_blocks);
 412                 if (new < 0)
 413                         new = 0;
 414                 if (new > (int) fs->blocksize/4)
 415                         new = fs->blocksize/4;
 416                 fs->super->s_reserved_gdt_blocks = new;
 417         }
 418
 419         /*
 420          * If we are shrinking the number of block groups, we're done
 421          * and can exit now.
 422          */
 423         if (old_fs->group_desc_count > fs->group_desc_count) {
 424                 /*
 425                  * Check the block groups that we are chopping off
 426                  * and free any blocks associated with their metadata
 427                  */
 428                 for (i = fs->group_desc_count;
 429                      i < old_fs->group_desc_count; i++) {
 430                         free_gdp_blocks(fs, reserve_blocks,
 431                                         &old_fs->group_desc[i]);
 432                 }
 433                 retval = 0;
 434                 goto errout;
 435         }
 436
 437         /*
 438          * Fix the count of the last (old) block group
 439          */
 440         old_numblocks = (old_fs->super->s_blocks_count -
 441                          old_fs->super->s_first_data_block) %
 442                                  old_fs->super->s_blocks_per_group;
 443         if (!old_numblocks)
 444                 old_numblocks = old_fs->super->s_blocks_per_group;
 445         if (old_fs->group_desc_count == fs->group_desc_count) {
 446                 numblocks = (fs->super->s_blocks_count -
 447                              fs->super->s_first_data_block) %
 448                         fs->super->s_blocks_per_group;
 449                 if (!numblocks)
 450                         numblocks = fs->super->s_blocks_per_group;
 451         } else
 452                 numblocks = fs->super->s_blocks_per_group;
 453         i = old_fs->group_desc_count - 1;
 454         fs->group_desc[i].bg_free_blocks_count += (numblocks-old_numblocks);
 455         ext2fs_group_desc_csum_set(fs, i);
 456
 457         /*
 458          * If the number of block groups is staying the same, we're
 459          * done and can exit now.  (If the number block groups is
 460          * shrinking, we had exited earlier.)
 461          */
 462         if (old_fs->group_desc_count >= fs->group_desc_count) {
 463                 retval = 0;
 464                 goto errout;
 465         }
 466
 467         /*
 468          * Initialize the new block group descriptors
 469          */
 470         group_block = fs->super->s_first_data_block +
 471                 old_fs->group_desc_count * fs->super->s_blocks_per_group;
 472
 473         csum_flag = EXT2_HAS_RO_COMPAT_FEATURE(fs->super,
 474                                                EXT4_FEATURE_RO_COMPAT_GDT_CSUM);
 475         adj = old_fs->group_desc_count;
 476         max_group = fs->group_desc_count - adj;
 477         if (fs->super->s_feature_incompat & EXT2_FEATURE_INCOMPAT_META_BG)
 478                 old_desc_blocks = fs->super->s_first_meta_bg;
 479         else
 480                 old_desc_blocks = fs->desc_blocks +
 481                         fs->super->s_reserved_gdt_blocks;
 482         for (i = old_fs->group_desc_count;
 483              i < fs->group_desc_count; i++) {
 484                 memset(&fs->group_desc[i], 0,
 485                        sizeof(struct ext2_group_desc));
 486                 adjblocks = 0;
 487
 488                 fs->group_desc[i].bg_flags = 0;
 489                 if (csum_flag)
 490                         fs->group_desc[i].bg_flags |= EXT2_BG_INODE_UNINIT |
 491                                 EXT2_BG_INODE_ZEROED;
 492                 if (i == fs->group_desc_count-1) {
 493                         numblocks = (fs->super->s_blocks_count -
 494                                      fs->super->s_first_data_block) %
 495                                              fs->super->s_blocks_per_group;
 496                         if (!numblocks)
 497                                 numblocks = fs->super->s_blocks_per_group;
 498                 } else {
 499                         numblocks = fs->super->s_blocks_per_group;
 500                         if (csum_flag)
 501                                 fs->group_desc[i].bg_flags |=
 502                                         EXT2_BG_BLOCK_UNINIT;
 503                 }
 504
 505                 has_super = ext2fs_bg_has_super(fs, i);
 506                 if (has_super) {
 507                         ext2fs_block_alloc_stats(fs, group_block, +1);
 508                         adjblocks++;
 509                 }
 510                 meta_bg_size = EXT2_DESC_PER_BLOCK(fs->super);
 511                 meta_bg = i / meta_bg_size;
 512                 if (!(fs->super->s_feature_incompat &
 513                       EXT2_FEATURE_INCOMPAT_META_BG) ||
 514                     (meta_bg < fs->super->s_first_meta_bg)) {
 515                         if (has_super) {
 516                                 for (j=0; j < old_desc_blocks; j++)
 517                                         ext2fs_block_alloc_stats(fs,
 518                                                  group_block + 1 + j, +1);
 519                                 adjblocks += old_desc_blocks;
 520                         }
 521                 } else {
 522                         if (has_super)
 523                                 has_super = 1;
 524                         if (((i % meta_bg_size) == 0) ||
 525                             ((i % meta_bg_size) == 1) ||
 526                             ((i % meta_bg_size) == (meta_bg_size-1)))
 527                                 ext2fs_block_alloc_stats(fs,
 528                                                  group_block + has_super, +1);
 529                 }
 530
 531                 adjblocks += 2 + fs->inode_blocks_per_group;
 532
 533                 numblocks -= adjblocks;
 534                 fs->super->s_free_blocks_count -= adjblocks;
 535                 fs->super->s_free_inodes_count +=
 536                         fs->super->s_inodes_per_group;
 537                 fs->group_desc[i].bg_free_blocks_count = numblocks;
 538                 fs->group_desc[i].bg_free_inodes_count =
 539                         fs->super->s_inodes_per_group;
 540                 fs->group_desc[i].bg_used_dirs_count = 0;
 541                 ext2fs_group_desc_csum_set(fs, i);
 542
 543                 retval = ext2fs_allocate_group_table(fs, i, 0);
 544                 if (retval) goto errout;
 545
 546                 group_block += fs->super->s_blocks_per_group;
 547         }
 548         retval = 0;
 549
 550 errout:
 551         return (retval);
 552 }
 553
 554 /*
 555  * This routine adjusts the superblock and other data structures, both
 556  * in disk as well as in memory...
 557  */
 558 static errcode_t adjust_superblock(ext2_resize_t rfs, blk_t new_size)
 559 {
 560         ext2_filsys fs;
 561         int             adj = 0;
 562         errcode_t       retval;
 563         blk_t           group_block;
 564         unsigned long   i;
 565         unsigned long   max_group;
 566
 567         fs = rfs->new_fs;
 568         ext2fs_mark_super_dirty(fs);
 569         ext2fs_mark_bb_dirty(fs);
 570         ext2fs_mark_ib_dirty(fs);
 571
 572         retval = ext2fs_allocate_block_bitmap(fs, _("reserved blocks"),
 573                                               &rfs->reserve_blocks);
 574         if (retval)
 575                 return retval;
 576
 577         retval = adjust_fs_info(fs, rfs->old_fs, rfs->reserve_blocks, new_size);
 578         if (retval)
 579                 goto errout;
 580
 581         /*
 582          * Check to make sure there are enough inodes
 583          */
 584         if ((rfs->old_fs->super->s_inodes_count -
 585              rfs->old_fs->super->s_free_inodes_count) >
 586             rfs->new_fs->super->s_inodes_count) {
 587                 retval = ENOSPC;
 588                 goto errout;
 589         }
 590
 591         /*
 592          * If we are shrinking the number block groups, we're done and
 593          * can exit now.
 594          */
 595         if (rfs->old_fs->group_desc_count > fs->group_desc_count) {
 596                 retval = 0;
 597                 goto errout;
 598         }
 599
 600         /*
 601          * If the number of block groups is staying the same, we're
 602          * done and can exit now.  (If the number block groups is
 603          * shrinking, we had exited earlier.)
 604          */
 605         if (rfs->old_fs->group_desc_count >= fs->group_desc_count) {
 606                 retval = 0;
 607                 goto errout;
 608         }
 609
 610         /*
 611          * Initialize the new block group descriptors
 612          */
 613         retval = ext2fs_get_array(fs->blocksize, fs->inode_blocks_per_group,
 614                                 &rfs->itable_buf);
 615         if (retval)
 616                 goto errout;
 617
 618         memset(rfs->itable_buf, 0, fs->blocksize * fs->inode_blocks_per_group);
 619         group_block = fs->super->s_first_data_block +
 620                 rfs->old_fs->group_desc_count * fs->super->s_blocks_per_group;
 621
 622         adj = rfs->old_fs->group_desc_count;
 623         max_group = fs->group_desc_count - adj;
 624         if (rfs->progress) {
 625                 retval = rfs->progress(rfs, E2_RSZ_EXTEND_ITABLE_PASS,
 626                                        0, max_group);
 627                 if (retval)
 628                         goto errout;
 629         }
 630         for (i = rfs->old_fs->group_desc_count;
 631              i < fs->group_desc_count; i++) {
 632                 /*
 633                  * Write out the new inode table
 634                  */
 635                 retval = io_channel_write_blk(fs->io,
 636                                               fs->group_desc[i].bg_inode_table,
 637                                               fs->inode_blocks_per_group,
 638                                               rfs->itable_buf);
 639                 if (retval) goto errout;
 640
 641                 io_channel_flush(fs->io);
 642                 if (rfs->progress) {
 643                         retval = rfs->progress(rfs, E2_RSZ_EXTEND_ITABLE_PASS,
 644                                                i - adj + 1, max_group);
 645                         if (retval)
 646                                 goto errout;
 647                 }
 648                 group_block += fs->super->s_blocks_per_group;
 649         }
 650         io_channel_flush(fs->io);
 651         retval = 0;
 652
 653 errout:
 654         return retval;
 655 }
 656
 657 /* --------------------------------------------------------------------
 658  *
 659  * Resize processing, phase 2.
 660  *
 661  * In this phase we adjust determine which blocks need to be moved, in
 662  * blocks_to_move().  We then copy the blocks to their ultimate new
 663  * destinations using block_mover().  Since we are copying blocks to
 664  * their new locations, again during this pass we can abort without
 665  * any problems.
 666  * --------------------------------------------------------------------
 667  */
 668
 669 /*
 670  * This helper function creates a block bitmap with all of the
 671  * filesystem meta-data blocks.
 672  */
 673 static errcode_t mark_table_blocks(ext2_filsys fs,
 674                                    ext2fs_block_bitmap bmap)
 675 {
 676         blk_t                   b;
 677         unsigned int            j;
 678         dgrp_t                  i;
 679         unsigned long           meta_bg_size;
 680         unsigned int            old_desc_blocks;
 681
 682         meta_bg_size = EXT2_DESC_PER_BLOCK(fs->super);
 683         if (fs->super->s_feature_incompat & EXT2_FEATURE_INCOMPAT_META_BG)
 684                 old_desc_blocks = fs->super->s_first_meta_bg;
 685         else
 686                 old_desc_blocks = fs->desc_blocks +
 687                         fs->super->s_reserved_gdt_blocks;
 688         for (i = 0; i < fs->group_desc_count; i++) {
 689                 ext2fs_reserve_super_and_bgd(fs, i, bmap);
 690
 691                 /*
 692                  * Mark the blocks used for the inode table
 693                  */
 694                 for (j = 0, b = fs->group_desc[i].bg_inode_table;
 695                      j < (unsigned int) fs->inode_blocks_per_group;
 696                      j++, b++)
 697                         ext2fs_mark_block_bitmap(bmap, b);
 698
 699                 /*
 700                  * Mark block used for the block bitmap
 701                  */
 702                 ext2fs_mark_block_bitmap(bmap,
 703                                          fs->group_desc[i].bg_block_bitmap);
 704
 705                 /*
 706                  * Mark block used for the inode bitmap
 707                  */
 708                 ext2fs_mark_block_bitmap(bmap,
 709                                          fs->group_desc[i].bg_inode_bitmap);
 710         }
 711         return 0;
 712 }
 713
 714 /*
 715  * This function checks to see if a particular block (either a
 716  * superblock or a block group descriptor) overlaps with an inode or
 717  * block bitmap block, or with the inode table.
 718  */
 719 static void mark_fs_metablock(ext2_resize_t rfs,
 720                               ext2fs_block_bitmap meta_bmap,
 721                               int group, blk_t blk)
 722 {
 723         ext2_filsys     fs = rfs->new_fs;
 724
 725         ext2fs_mark_block_bitmap(rfs->reserve_blocks, blk);
 726         ext2fs_block_alloc_stats(fs, blk, +1);
 727
 728         /*
 729          * Check to see if we overlap with the inode or block bitmap,
 730          * or the inode tables.  If not, and the block is in use, then
 731          * mark it as a block to be moved.
 732          */
 733         if (IS_BLOCK_BM(fs, group, blk)) {
 734                 FS_BLOCK_BM(fs, group) = 0;
 735                 rfs->needed_blocks++;
 736         } else if (IS_INODE_BM(fs, group, blk)) {
 737                 FS_INODE_BM(fs, group) = 0;
 738                 rfs->needed_blocks++;
 739         } else if (IS_INODE_TB(fs, group, blk)) {
 740                 FS_INODE_TB(fs, group) = 0;
 741                 rfs->needed_blocks++;
 742         } else if (EXT2_HAS_RO_COMPAT_FEATURE(fs->super,
 743                                               EXT4_FEATURE_RO_COMPAT_GDT_CSUM) &&
 744                    (fs->group_desc[group].bg_flags & EXT2_BG_BLOCK_UNINIT)) {
 745                 /*
 746                  * If the block bitmap is uninitialized, which means
 747                  * nothing other than standard metadata in use.
 748                  */
 749                 return;
 750         } else if (ext2fs_test_block_bitmap(rfs->old_fs->block_map, blk) &&
 751                    !ext2fs_test_block_bitmap(meta_bmap, blk)) {
 752                 ext2fs_mark_block_bitmap(rfs->move_blocks, blk);
 753                 rfs->needed_blocks++;
 754         }
 755 }
 756
 757
 758 /*
 759  * This routine marks and unmarks reserved blocks in the new block
 760  * bitmap.  It also determines which blocks need to be moved and
 761  * places this information into the move_blocks bitmap.
 762  */
 763 static errcode_t blocks_to_move(ext2_resize_t rfs)
 764 {
 765         int             j, has_super;
 766         dgrp_t          i, max_groups, g;
 767         blk_t           blk, group_blk;
 768         unsigned long   old_blocks, new_blocks;
 769         unsigned int    meta_bg, meta_bg_size;
 770         errcode_t       retval;
 771         ext2_filsys     fs, old_fs;
 772         ext2fs_block_bitmap     meta_bmap;
 773         __u32           save_incompat_flag;
 774
 775         fs = rfs->new_fs;
 776         old_fs = rfs->old_fs;
 777         if (old_fs->super->s_blocks_count > fs->super->s_blocks_count)
 778                 fs = rfs->old_fs;
 779
 780         retval = ext2fs_allocate_block_bitmap(fs, _("blocks to be moved"),
 781                                               &rfs->move_blocks);
 782         if (retval)
 783                 return retval;
 784
 785         retval = ext2fs_allocate_block_bitmap(fs, _("meta-data blocks"),
 786                                               &meta_bmap);
 787         if (retval)
 788                 return retval;
 789
 790         retval = mark_table_blocks(old_fs, meta_bmap);
 791         if (retval)
 792                 return retval;
 793
 794         fs = rfs->new_fs;
 795
 796         /*
 797          * If we're shrinking the filesystem, we need to move all of
 798          * the blocks that don't fit any more
 799          */
 800         for (blk = fs->super->s_blocks_count;
 801              blk < old_fs->super->s_blocks_count; blk++) {
 802                 g = ext2fs_group_of_blk(fs, blk);
 803                 if (EXT2_HAS_RO_COMPAT_FEATURE(fs->super,
 804                                                EXT4_FEATURE_RO_COMPAT_GDT_CSUM) &&
 805                     (old_fs->group_desc[g].bg_flags & EXT2_BG_BLOCK_UNINIT)) {
 806                         /*
 807                          * The block bitmap is uninitialized, so skip
 808                          * to the next block group.
 809                          */
 810                         blk = ((g+1) * fs->super->s_blocks_per_group) +
 811                                 fs->super->s_first_data_block - 1;
 812                         continue;
 813                 }
 814                 if (ext2fs_test_block_bitmap(old_fs->block_map, blk) &&
 815                     !ext2fs_test_block_bitmap(meta_bmap, blk)) {
 816                         ext2fs_mark_block_bitmap(rfs->move_blocks, blk);
 817                         rfs->needed_blocks++;
 818                 }
 819                 ext2fs_mark_block_bitmap(rfs->reserve_blocks, blk);
 820         }
 821
 822         if (fs->super->s_feature_incompat & EXT2_FEATURE_INCOMPAT_META_BG) {
 823                 old_blocks = old_fs->super->s_first_meta_bg;
 824                 new_blocks = fs->super->s_first_meta_bg;
 825         } else {
 826                 old_blocks = old_fs->desc_blocks + old_fs->super->s_reserved_gdt_blocks;
 827                 new_blocks = fs->desc_blocks + fs->super->s_reserved_gdt_blocks;
 828         }
 829
 830         if (old_blocks == new_blocks) {
 831                 retval = 0;
 832                 goto errout;
 833         }
 834
 835         max_groups = fs->group_desc_count;
 836         if (max_groups > old_fs->group_desc_count)
 837                 max_groups = old_fs->group_desc_count;
 838         group_blk = old_fs->super->s_first_data_block;
 839         /*
 840          * If we're reducing the number of descriptor blocks, this
 841          * makes life easy.  :-)   We just have to mark some extra
 842          * blocks as free.
 843          */
 844         if (old_blocks > new_blocks) {
 845                 for (i = 0; i < max_groups; i++) {
 846                         if (!ext2fs_bg_has_super(fs, i)) {
 847                                 group_blk += fs->super->s_blocks_per_group;
 848                                 continue;
 849                         }
 850                         for (blk = group_blk+1+new_blocks;
 851                              blk < group_blk+1+old_blocks; blk++) {
 852                                 ext2fs_block_alloc_stats(fs, blk, -1);
 853                                 rfs->needed_blocks--;
 854                         }
 855                         group_blk += fs->super->s_blocks_per_group;
 856                 }
 857                 retval = 0;
 858                 goto errout;
 859         }
 860         /*
 861          * If we're increasing the number of descriptor blocks, life
 862          * gets interesting....
 863          */
 864         meta_bg_size = EXT2_DESC_PER_BLOCK(fs->super);
 865         for (i = 0; i < max_groups; i++) {
 866                 has_super = ext2fs_bg_has_super(fs, i);
 867                 if (has_super)
 868                         mark_fs_metablock(rfs, meta_bmap, i, group_blk);
 869
 870                 meta_bg = i / meta_bg_size;
 871                 if (!(fs->super->s_feature_incompat &
 872                       EXT2_FEATURE_INCOMPAT_META_BG) ||
 873                     (meta_bg < fs->super->s_first_meta_bg)) {
 874                         if (has_super) {
 875                                 for (blk = group_blk+1;
 876                                      blk < group_blk + 1 + new_blocks; blk++)
 877                                         mark_fs_metablock(rfs, meta_bmap,
 878                                                           i, blk);
 879                         }
 880                 } else {
 881                         if (has_super)
 882                                 has_super = 1;
 883                         if (((i % meta_bg_size) == 0) ||
 884                             ((i % meta_bg_size) == 1) ||
 885                             ((i % meta_bg_size) == (meta_bg_size-1)))
 886                                 mark_fs_metablock(rfs, meta_bmap, i,
 887                                                   group_blk + has_super);
 888                 }
 889
 890                 if (fs->group_desc[i].bg_inode_table &&
 891                     fs->group_desc[i].bg_inode_bitmap &&
 892                     fs->group_desc[i].bg_block_bitmap)
 893                         goto next_group;
 894
 895                 /*
 896                  * Reserve the existing meta blocks that we know
 897                  * aren't to be moved.
 898                  */
 899                 if (fs->group_desc[i].bg_block_bitmap)
 900                         ext2fs_mark_block_bitmap(rfs->reserve_blocks,
 901                                  fs->group_desc[i].bg_block_bitmap);
 902                 if (fs->group_desc[i].bg_inode_bitmap)
 903                         ext2fs_mark_block_bitmap(rfs->reserve_blocks,
 904                                  fs->group_desc[i].bg_inode_bitmap);
 905                 if (fs->group_desc[i].bg_inode_table)
 906                         for (blk = fs->group_desc[i].bg_inode_table, j=0;
 907                              j < fs->inode_blocks_per_group ; j++, blk++)
 908                                 ext2fs_mark_block_bitmap(rfs->reserve_blocks,
 909                                                          blk);
 910
 911                 /*
 912                  * Allocate the missing data structures
 913                  *
 914                  * XXX We have a problem with FLEX_BG and off-line
 915                  * resizing where we are growing the size of the
 916                  * filesystem.  ext2fs_allocate_group_table() will try
 917                  * to reserve the inode table in the desired flex_bg
 918                  * location.  However, passing rfs->reserve_blocks
 919                  * doesn't work since it only has reserved the blocks
 920                  * that will be used in the new block group -- and
 921                  * with flex_bg, we can and will allocate the tables
 922                  * outside of the block group.  And we can't pass in
 923                  * the fs->block_map because it doesn't handle
 924                  * overlapping inode table movements right.  So for
 925                  * now, we temporarily disable flex_bg to force
 926                  * ext2fs_allocate_group_tables() to allocate the bg
 927                  * metadata in side the block group, and the restore
 928                  * it afterwards.  Ugly, until we can fix this up
 929                  * right later.
 930                  */
 931                 save_incompat_flag = fs->super->s_feature_incompat;
 932                 fs->super->s_feature_incompat &= ~EXT4_FEATURE_INCOMPAT_FLEX_BG;
 933                 retval = ext2fs_allocate_group_table(fs, i,
 934                                                      rfs->reserve_blocks);
 935                 fs->super->s_feature_incompat = save_incompat_flag;
 936                 if (retval)
 937                         goto errout;
 938
 939                 /*
 940                  * For those structures that have changed, we need to
 941                  * do bookkeepping.
 942                  */
 943                 if (FS_BLOCK_BM(old_fs, i) !=
 944                     (blk = FS_BLOCK_BM(fs, i))) {
 945                         ext2fs_block_alloc_stats(fs, blk, +1);
 946                         if (ext2fs_test_block_bitmap(old_fs->block_map, blk) &&
 947                             !ext2fs_test_block_bitmap(meta_bmap, blk))
 948                                 ext2fs_mark_block_bitmap(rfs->move_blocks,
 949                                                          blk);
 950                 }
 951                 if (FS_INODE_BM(old_fs, i) !=
 952                     (blk = FS_INODE_BM(fs, i))) {
 953                         ext2fs_block_alloc_stats(fs, blk, +1);
 954                         if (ext2fs_test_block_bitmap(old_fs->block_map, blk) &&
 955                             !ext2fs_test_block_bitmap(meta_bmap, blk))
 956                                 ext2fs_mark_block_bitmap(rfs->move_blocks,
 957                                                          blk);
 958                 }
 959
 960                 /*
 961                  * The inode table, if we need to relocate it, is
 962                  * handled specially.  We have to reserve the blocks
 963                  * for both the old and the new inode table, since we
 964                  * can't have the inode table be destroyed during the
 965                  * block relocation phase.
 966                  */
 967                 if (FS_INODE_TB(fs, i) == FS_INODE_TB(old_fs, i))
 968                         goto next_group; /* inode table not moved */
 969
 970                 rfs->needed_blocks += fs->inode_blocks_per_group;
 971
 972                 /*
 973                  * Mark the new inode table as in use in the new block
 974                  * allocation bitmap, and move any blocks that might
 975                  * be necessary.
 976                  */
 977                 for (blk = fs->group_desc[i].bg_inode_table, j=0;
 978                      j < fs->inode_blocks_per_group ; j++, blk++) {
 979                         ext2fs_block_alloc_stats(fs, blk, +1);
 980                         if (ext2fs_test_block_bitmap(old_fs->block_map, blk) &&
 981                             !ext2fs_test_block_bitmap(meta_bmap, blk))
 982                                 ext2fs_mark_block_bitmap(rfs->move_blocks,
 983                                                          blk);
 984                 }
 985
 986                 /*
 987                  * Make sure the old inode table is reserved in the
 988                  * block reservation bitmap.
 989                  */
 990                 for (blk = rfs->old_fs->group_desc[i].bg_inode_table, j=0;
 991                      j < fs->inode_blocks_per_group ; j++, blk++)
 992                         ext2fs_mark_block_bitmap(rfs->reserve_blocks, blk);
 993
 994         next_group:
 995                 group_blk += rfs->new_fs->super->s_blocks_per_group;
 996         }
 997         retval = 0;
 998
 999 errout:
1000         if (meta_bmap)
1001                 ext2fs_free_block_bitmap(meta_bmap);
1002
1003         return retval;
1004 }
1005
1006 /*
1007  * This helper function tries to allocate a new block.  We try to
1008  * avoid hitting the original group descriptor blocks at least at
1009  * first, since we want to make it possible to recover from a badly
1010  * aborted resize operation as much as possible.
1011  *
1012  * In the future, I may further modify this routine to balance out
1013  * where we get the new blocks across the various block groups.
1014  * Ideally we would allocate blocks that corresponded with the block
1015  * group of the containing inode, and keep contiguous blocks
1016  * together.  However, this very difficult to do efficiently, since we
1017  * don't have the necessary information up front.
1018  */
1019
1020 #define AVOID_OLD       1
1021 #define DESPERATION     2
1022
1023 static void init_block_alloc(ext2_resize_t rfs)
1024 {
1025         rfs->alloc_state = AVOID_OLD;
1026         rfs->new_blk = rfs->new_fs->super->s_first_data_block;
1027 #if 0
1028         /* HACK for testing */
1029         if (rfs->new_fs->super->s_blocks_count >
1030             rfs->old_fs->super->s_blocks_count)
1031                 rfs->new_blk = rfs->old_fs->super->s_blocks_count;
1032 #endif
1033 }
1034
1035 static blk_t get_new_block(ext2_resize_t rfs)
1036 {
1037         ext2_filsys     fs = rfs->new_fs;
1038
1039         while (1) {
1040                 if (rfs->new_blk >= fs->super->s_blocks_count) {
1041                         if (rfs->alloc_state == DESPERATION)
1042                                 return 0;
1043
1044 #ifdef RESIZE2FS_DEBUG
1045                         if (rfs->flags & RESIZE_DEBUG_BMOVE)
1046                                 printf("Going into desperation mode "
1047                                        "for block allocations\n");
1048 #endif
1049                         rfs->alloc_state = DESPERATION;
1050                         rfs->new_blk = fs->super->s_first_data_block;
1051                         continue;
1052                 }
1053                 if (ext2fs_test_block_bitmap(fs->block_map, rfs->new_blk) ||
1054                     ext2fs_test_block_bitmap(rfs->reserve_blocks,
1055                                              rfs->new_blk) ||
1056                     ((rfs->alloc_state == AVOID_OLD) &&
1057                      (rfs->new_blk < rfs->old_fs->super->s_blocks_count) &&
1058                      ext2fs_test_block_bitmap(rfs->old_fs->block_map,
1059                                               rfs->new_blk))) {
1060                         rfs->new_blk++;
1061                         continue;
1062                 }
1063                 return rfs->new_blk;
1064         }
1065 }
1066
1067 static errcode_t resize2fs_get_alloc_block(ext2_filsys fs, blk64_t goal,
1068                                            blk64_t *ret)
1069 {
1070         ext2_resize_t rfs = (ext2_resize_t) fs->priv_data;
1071         blk_t blk;
1072
1073         blk = get_new_block(rfs);
1074         if (!blk)
1075                 return ENOSPC;
1076
1077 #ifdef RESIZE2FS_DEBUG
1078         if (rfs->flags & 0xF)
1079                 printf("get_alloc_block allocating %u\n", blk);
1080 #endif
1081
1082         ext2fs_mark_block_bitmap(rfs->old_fs->block_map, blk);
1083         ext2fs_mark_block_bitmap(rfs->new_fs->block_map, blk);
1084         *ret = (blk64_t) blk;
1085         return 0;
1086 }
1087
1088 static errcode_t block_mover(ext2_resize_t rfs)
1089 {
1090         blk_t                   blk, old_blk, new_blk;
1091         ext2_filsys             fs = rfs->new_fs;
1092         ext2_filsys             old_fs = rfs->old_fs;
1093         errcode_t               retval;
1094         int                     size, c;
1095         int                     to_move, moved;
1096         ext2_badblocks_list     badblock_list = 0;
1097         int                     bb_modified = 0;
1098
1099         fs->get_alloc_block = resize2fs_get_alloc_block;
1100         old_fs->get_alloc_block = resize2fs_get_alloc_block;
1101
1102         retval = ext2fs_read_bb_inode(old_fs, &badblock_list);
1103         if (retval)
1104                 return retval;
1105
1106         new_blk = fs->super->s_first_data_block;
1107         if (!rfs->itable_buf) {
1108                 retval = ext2fs_get_array(fs->blocksize,
1109                                         fs->inode_blocks_per_group,
1110                                         &rfs->itable_buf);
1111                 if (retval)
1112                         return retval;
1113         }
1114         retval = ext2fs_create_extent_table(&rfs->bmap, 0);
1115         if (retval)
1116                 return retval;
1117
1118         /*
1119          * The first step is to figure out where all of the blocks
1120          * will go.
1121          */
1122         to_move = moved = 0;
1123         init_block_alloc(rfs);
1124         for (blk = old_fs->super->s_first_data_block;
1125              blk < old_fs->super->s_blocks_count; blk++) {
1126                 if (!ext2fs_test_block_bitmap(old_fs->block_map, blk))
1127                         continue;
1128                 if (!ext2fs_test_block_bitmap(rfs->move_blocks, blk))
1129                         continue;
1130                 if (ext2fs_badblocks_list_test(badblock_list, blk)) {
1131                         ext2fs_badblocks_list_del(badblock_list, blk);
1132                         bb_modified++;
1133                         continue;
1134                 }
1135
1136                 new_blk = get_new_block(rfs);
1137                 if (!new_blk) {
1138                         retval = ENOSPC;
1139                         goto errout;
1140                 }
1141                 ext2fs_block_alloc_stats(fs, new_blk, +1);
1142                 ext2fs_add_extent_entry(rfs->bmap, blk, new_blk);
1143                 to_move++;
1144         }
1145
1146         if (to_move == 0) {
1147                 if (rfs->bmap) {
1148                         ext2fs_free_extent_table(rfs->bmap);
1149                         rfs->bmap = 0;
1150                 }
1151                 retval = 0;
1152                 goto errout;
1153         }
1154
1155         /*
1156          * Step two is to actually move the blocks
1157          */
1158         retval =  ext2fs_iterate_extent(rfs->bmap, 0, 0, 0);
1159         if (retval) goto errout;
1160
1161         if (rfs->progress) {
1162                 retval = (rfs->progress)(rfs, E2_RSZ_BLOCK_RELOC_PASS,
1163                                          0, to_move);
1164                 if (retval)
1165                         goto errout;
1166         }
1167         while (1) {
1168                 retval = ext2fs_iterate_extent(rfs->bmap, &old_blk, &new_blk, &size);
1169                 if (retval) goto errout;
1170                 if (!size)
1171                         break;
1172 #ifdef RESIZE2FS_DEBUG
1173                 if (rfs->flags & RESIZE_DEBUG_BMOVE)
1174                         printf("Moving %d blocks %u->%u\n",
1175                                size, old_blk, new_blk);
1176 #endif
1177                 do {
1178                         c = size;
1179                         if (c > fs->inode_blocks_per_group)
1180                                 c = fs->inode_blocks_per_group;
1181                         retval = io_channel_read_blk(fs->io, old_blk, c,
1182                                                      rfs->itable_buf);
1183                         if (retval) goto errout;
1184                         retval = io_channel_write_blk(fs->io, new_blk, c,
1185                                                       rfs->itable_buf);
1186                         if (retval) goto errout;
1187                         size -= c;
1188                         new_blk += c;
1189                         old_blk += c;
1190                         moved += c;
1191                         if (rfs->progress) {
1192                                 io_channel_flush(fs->io);
1193                                 retval = (rfs->progress)(rfs,
1194                                                 E2_RSZ_BLOCK_RELOC_PASS,
1195                                                 moved, to_move);
1196                                 if (retval)
1197                                         goto errout;
1198                         }
1199                 } while (size > 0);
1200                 io_channel_flush(fs->io);
1201         }
1202
1203 errout:
1204         if (badblock_list) {
1205                 if (!retval && bb_modified)
1206                         retval = ext2fs_update_bb_inode(old_fs,
1207                                                         badblock_list);
1208                 ext2fs_badblocks_list_free(badblock_list);
1209         }
1210         return retval;
1211 }
1212
1213
1214 /* --------------------------------------------------------------------
1215  *
1216  * Resize processing, phase 3
1217  *
1218  * --------------------------------------------------------------------
1219  */
1220
1221
1222 struct process_block_struct {
1223         ext2_resize_t           rfs;
1224         ext2_ino_t              ino;
1225         struct ext2_inode *     inode;
1226         errcode_t               error;
1227         int                     is_dir;
1228         int                     changed;
1229 };
1230
1231 static int process_block(ext2_filsys fs, blk_t  *block_nr,
1232                          e2_blkcnt_t blockcnt,
1233                          blk_t ref_block EXT2FS_ATTR((unused)),
1234                          int ref_offset EXT2FS_ATTR((unused)), void *priv_data)
1235 {
1236         struct process_block_struct *pb;
1237         errcode_t       retval;
1238         blk_t           block, new_block;
1239         int             ret = 0;
1240
1241         pb = (struct process_block_struct *) priv_data;
1242         block = *block_nr;
1243         if (pb->rfs->bmap) {
1244                 new_block = ext2fs_extent_translate(pb->rfs->bmap, block);
1245                 if (new_block) {
1246                         *block_nr = new_block;
1247                         ret |= BLOCK_CHANGED;
1248                         pb->changed = 1;
1249 #ifdef RESIZE2FS_DEBUG
1250                         if (pb->rfs->flags & RESIZE_DEBUG_BMOVE)
1251                                 printf("ino=%u, blockcnt=%lld, %u->%u\n",
1252                                        pb->ino, blockcnt, block, new_block);
1253 #endif
1254                         block = new_block;
1255                 }
1256         }
1257         if (pb->is_dir) {
1258                 retval = ext2fs_add_dir_block(fs->dblist, pb->ino,
1259                                               block, (int) blockcnt);
1260                 if (retval) {
1261                         pb->error = retval;
1262                         ret |= BLOCK_ABORT;
1263                 }
1264         }
1265         return ret;
1266 }
1267
1268 /*
1269  * Progress callback
1270  */
1271 static errcode_t progress_callback(ext2_filsys fs,
1272                                    ext2_inode_scan scan EXT2FS_ATTR((unused)),
1273                                    dgrp_t group, void * priv_data)
1274 {
1275         ext2_resize_t rfs = (ext2_resize_t) priv_data;
1276         errcode_t               retval;
1277
1278         /*
1279          * This check is to protect against old ext2 libraries.  It
1280          * shouldn't be needed against new libraries.
1281          */
1282         if ((group+1) == 0)
1283                 return 0;
1284
1285         if (rfs->progress) {
1286                 io_channel_flush(fs->io);
1287                 retval = (rfs->progress)(rfs, E2_RSZ_INODE_SCAN_PASS,
1288                                          group+1, fs->group_desc_count);
1289                 if (retval)
1290                         return retval;
1291         }
1292
1293         return 0;
1294 }
1295
1296 static errcode_t inode_scan_and_fix(ext2_resize_t rfs)
1297 {
1298         struct process_block_struct     pb;
1299         ext2_ino_t              ino, new_inode;
1300         struct ext2_inode       *inode = NULL;
1301         ext2_inode_scan         scan = NULL;
1302         errcode_t               retval;
1303         char                    *block_buf = 0;
1304         ext2_ino_t              start_to_move;
1305         blk_t                   orig_size, new_block;
1306         int                     inode_size;
1307
1308         if ((rfs->old_fs->group_desc_count <=
1309              rfs->new_fs->group_desc_count) &&
1310             !rfs->bmap)
1311                 return 0;
1312
1313         /*
1314          * Save the original size of the old filesystem, and
1315          * temporarily set the size to be the new size if the new size
1316          * is larger.  We need to do this to avoid catching an error
1317          * by the block iterator routines
1318          */
1319         orig_size = rfs->old_fs->super->s_blocks_count;
1320         if (orig_size < rfs->new_fs->super->s_blocks_count)
1321                 rfs->old_fs->super->s_blocks_count =
1322                         rfs->new_fs->super->s_blocks_count;
1323
1324         retval = ext2fs_open_inode_scan(rfs->old_fs, 0, &scan);
1325         if (retval) goto errout;
1326
1327         retval = ext2fs_init_dblist(rfs->old_fs, 0);
1328         if (retval) goto errout;
1329         retval = ext2fs_get_array(rfs->old_fs->blocksize, 3, &block_buf);
1330         if (retval) goto errout;
1331
1332         start_to_move = (rfs->new_fs->group_desc_count *
1333                          rfs->new_fs->super->s_inodes_per_group);
1334
1335         if (rfs->progress) {
1336                 retval = (rfs->progress)(rfs, E2_RSZ_INODE_SCAN_PASS,
1337                                          0, rfs->old_fs->group_desc_count);
1338                 if (retval)
1339                         goto errout;
1340         }
1341         ext2fs_set_inode_callback(scan, progress_callback, (void *) rfs);
1342         pb.rfs = rfs;
1343         pb.inode = inode;
1344         pb.error = 0;
1345         new_inode = EXT2_FIRST_INODE(rfs->new_fs->super);
1346         inode_size = EXT2_INODE_SIZE(rfs->new_fs->super);
1347         inode = malloc(inode_size);
1348         if (!inode) {
1349                 retval = ENOMEM;
1350                 goto errout;
1351         }
1352         /*
1353          * First, copy all of the inodes that need to be moved
1354          * elsewhere in the inode table
1355          */
1356         while (1) {
1357                 retval = ext2fs_get_next_inode_full(scan, &ino, inode, inode_size);
1358                 if (retval) goto errout;
1359                 if (!ino)
1360                         break;
1361
1362                 if (inode->i_links_count == 0 && ino != EXT2_RESIZE_INO)
1363                         continue; /* inode not in use */
1364
1365                 pb.is_dir = LINUX_S_ISDIR(inode->i_mode);
1366                 pb.changed = 0;
1367
1368                 if (inode->i_file_acl && rfs->bmap) {
1369                         new_block = ext2fs_extent_translate(rfs->bmap,
1370                                                             inode->i_file_acl);
1371                         if (new_block) {
1372                                 inode->i_file_acl = new_block;
1373                                 retval = ext2fs_write_inode_full(rfs->old_fs,
1374                                                             ino, inode, inode_size);
1375                                 if (retval) goto errout;
1376                         }
1377                 }
1378
1379                 if (ext2fs_inode_has_valid_blocks(inode) &&
1380                     (rfs->bmap || pb.is_dir)) {
1381                         pb.ino = ino;
1382                         retval = ext2fs_block_iterate2(rfs->old_fs,
1383                                                        ino, 0, block_buf,
1384                                                        process_block, &pb);
1385                         if (retval)
1386                                 goto errout;
1387                         if (pb.error) {
1388                                 retval = pb.error;
1389                                 goto errout;
1390                         }
1391                 }
1392
1393                 if (ino <= start_to_move)
1394                         continue; /* Don't need to move it. */
1395
1396                 /*
1397                  * Find a new inode
1398                  */
1399                 retval = ext2fs_new_inode(rfs->new_fs, 0, 0, 0, &new_inode);
1400                 if (retval)
1401                         goto errout;
1402
1403                 ext2fs_inode_alloc_stats2(rfs->new_fs, new_inode, +1,
1404                                           pb.is_dir);
1405                 if (pb.changed) {
1406                         /* Get the new version of the inode */
1407                         retval = ext2fs_read_inode_full(rfs->old_fs, ino,
1408                                                 inode, inode_size);
1409                         if (retval) goto errout;
1410                 }
1411                 inode->i_ctime = time(0);
1412                 retval = ext2fs_write_inode_full(rfs->old_fs, new_inode,
1413                                                 inode, inode_size);
1414                 if (retval) goto errout;
1415
1416 #ifdef RESIZE2FS_DEBUG
1417                 if (rfs->flags & RESIZE_DEBUG_INODEMAP)
1418                         printf("Inode moved %u->%u\n", ino, new_inode);
1419 #endif
1420                 if (!rfs->imap) {
1421                         retval = ext2fs_create_extent_table(&rfs->imap, 0);
1422                         if (retval)
1423                                 goto errout;
1424                 }
1425                 ext2fs_add_extent_entry(rfs->imap, ino, new_inode);
1426         }
1427         io_channel_flush(rfs->old_fs->io);
1428
1429 errout:
1430         rfs->old_fs->super->s_blocks_count = orig_size;
1431         if (rfs->bmap) {
1432                 ext2fs_free_extent_table(rfs->bmap);
1433                 rfs->bmap = 0;
1434         }
1435         if (scan)
1436                 ext2fs_close_inode_scan(scan);
1437         if (block_buf)
1438                 ext2fs_free_mem(&block_buf);
1439         free(inode);
1440         return retval;
1441 }
1442
1443 /* --------------------------------------------------------------------
1444  *
1445  * Resize processing, phase 4.
1446  *
1447  * --------------------------------------------------------------------
1448  */
1449
1450 struct istruct {
1451         ext2_resize_t rfs;
1452         errcode_t       err;
1453         unsigned int    max_dirs;
1454         unsigned int    num;
1455 };
1456
1457 static int check_and_change_inodes(ext2_ino_t dir,
1458                                    int entry EXT2FS_ATTR((unused)),
1459                                    struct ext2_dir_entry *dirent, int offset,
1460                                    int  blocksize EXT2FS_ATTR((unused)),
1461                                    char *buf EXT2FS_ATTR((unused)),
1462                                    void *priv_data)
1463 {
1464         struct istruct *is = (struct istruct *) priv_data;
1465         struct ext2_inode       inode;
1466         ext2_ino_t              new_inode;
1467         errcode_t               retval;
1468
1469         if (is->rfs->progress && offset == 0) {
1470                 io_channel_flush(is->rfs->old_fs->io);
1471                 is->err = (is->rfs->progress)(is->rfs,
1472                                               E2_RSZ_INODE_REF_UPD_PASS,
1473                                               ++is->num, is->max_dirs);
1474                 if (is->err)
1475                         return DIRENT_ABORT;
1476         }
1477
1478         if (!dirent->inode)
1479                 return 0;
1480
1481         new_inode = ext2fs_extent_translate(is->rfs->imap, dirent->inode);
1482
1483         if (!new_inode)
1484                 return 0;
1485 #ifdef RESIZE2FS_DEBUG
1486         if (is->rfs->flags & RESIZE_DEBUG_INODEMAP)
1487                 printf("Inode translate (dir=%u, name=%.*s, %u->%u)\n",
1488                        dir, dirent->name_len&0xFF, dirent->name,
1489                        dirent->inode, new_inode);
1490 #endif
1491
1492         dirent->inode = new_inode;
1493
1494         /* Update the directory mtime and ctime */
1495         retval = ext2fs_read_inode(is->rfs->old_fs, dir, &inode);
1496         if (retval == 0) {
1497                 inode.i_mtime = inode.i_ctime = time(0);
1498                 is->err = ext2fs_write_inode(is->rfs->old_fs, dir, &inode);
1499                 if (is->err)
1500                         return DIRENT_ABORT;
1501         }
1502
1503         return DIRENT_CHANGED;
1504 }
1505
1506 static errcode_t inode_ref_fix(ext2_resize_t rfs)
1507 {
1508         errcode_t               retval;
1509         struct istruct          is;
1510
1511         if (!rfs->imap)
1512                 return 0;
1513
1514         /*
1515          * Now, we iterate over all of the directories to update the
1516          * inode references
1517          */
1518         is.num = 0;
1519         is.max_dirs = ext2fs_dblist_count(rfs->old_fs->dblist);
1520         is.rfs = rfs;
1521         is.err = 0;
1522
1523         if (rfs->progress) {
1524                 retval = (rfs->progress)(rfs, E2_RSZ_INODE_REF_UPD_PASS,
1525                                          0, is.max_dirs);
1526                 if (retval)
1527                         goto errout;
1528         }
1529
1530         retval = ext2fs_dblist_dir_iterate(rfs->old_fs->dblist,
1531                                            DIRENT_FLAG_INCLUDE_EMPTY, 0,
1532                                            check_and_change_inodes, &is);
1533         if (retval)
1534                 goto errout;
1535         if (is.err) {
1536                 retval = is.err;
1537                 goto errout;
1538         }
1539
1540         if (rfs->progress && (is.num < is.max_dirs))
1541                 (rfs->progress)(rfs, E2_RSZ_INODE_REF_UPD_PASS,
1542                                 is.max_dirs, is.max_dirs);
1543
1544 errout:
1545         ext2fs_free_extent_table(rfs->imap);
1546         rfs->imap = 0;
1547         return retval;
1548 }
1549
1550
1551 /* --------------------------------------------------------------------
1552  *
1553  * Resize processing, phase 5.
1554  *
1555  * In this phase we actually move the inode table around, and then
1556  * update the summary statistics.  This is scary, since aborting here
1557  * will potentially scramble the filesystem.  (We are moving the
1558  * inode tables around in place, and so the potential for lost data,
1559  * or at the very least scrambling the mapping between filenames and
1560  * inode numbers is very high in case of a power failure here.)
1561  * --------------------------------------------------------------------
1562  */
1563
1564
1565 /*
1566  * A very scary routine --- this one moves the inode table around!!!
1567  *
1568  * After this you have to use the rfs->new_fs file handle to read and
1569  * write inodes.
1570  */
1571 static errcode_t move_itables(ext2_resize_t rfs)
1572 {
1573         int             n, num, size, diff;
1574         dgrp_t          i, max_groups;
1575         ext2_filsys     fs = rfs->new_fs;
1576         char            *cp;
1577         blk_t           old_blk, new_blk, blk;
1578         errcode_t       retval;
1579         int             j, to_move, moved;
1580
1581         max_groups = fs->group_desc_count;
1582         if (max_groups > rfs->old_fs->group_desc_count)
1583                 max_groups = rfs->old_fs->group_desc_count;
1584
1585         size = fs->blocksize * fs->inode_blocks_per_group;
1586         if (!rfs->itable_buf) {
1587                 retval = ext2fs_get_mem(size, &rfs->itable_buf);
1588                 if (retval)
1589                         return retval;
1590         }
1591
1592         /*
1593          * Figure out how many inode tables we need to move
1594          */
1595         to_move = moved = 0;
1596         for (i=0; i < max_groups; i++)
1597                 if (rfs->old_fs->group_desc[i].bg_inode_table !=
1598                     fs->group_desc[i].bg_inode_table)
1599                         to_move++;
1600
1601         if (to_move == 0)
1602                 return 0;
1603
1604         if (rfs->progress) {
1605                 retval = rfs->progress(rfs, E2_RSZ_MOVE_ITABLE_PASS,
1606                                        0, to_move);
1607                 if (retval)
1608                         goto errout;
1609         }
1610
1611         rfs->old_fs->flags |= EXT2_FLAG_MASTER_SB_ONLY;
1612
1613         for (i=0; i < max_groups; i++) {
1614                 old_blk = rfs->old_fs->group_desc[i].bg_inode_table;
1615                 new_blk = fs->group_desc[i].bg_inode_table;
1616                 diff = new_blk - old_blk;
1617
1618 #ifdef RESIZE2FS_DEBUG
1619                 if (rfs->flags & RESIZE_DEBUG_ITABLEMOVE)
1620                         printf("Itable move group %d block %u->%u (diff %d)\n",
1621                                i, old_blk, new_blk, diff);
1622 #endif
1623
1624                 if (!diff)
1625                         continue;
1626
1627                 retval = io_channel_read_blk(fs->io, old_blk,
1628                                              fs->inode_blocks_per_group,
1629                                              rfs->itable_buf);
1630                 if (retval)
1631                         goto errout;
1632                 /*
1633                  * The end of the inode table segment often contains
1634                  * all zeros, and we're often only moving the inode
1635                  * table down a block or two.  If so, we can optimize
1636                  * things by not rewriting blocks that we know to be zero
1637                  * already.
1638                  */
1639                 for (cp = rfs->itable_buf+size-1, n=0; n < size; n++, cp--)
1640                         if (*cp)
1641                                 break;
1642                 n = n >> EXT2_BLOCK_SIZE_BITS(fs->super);
1643 #ifdef RESIZE2FS_DEBUG
1644                 if (rfs->flags & RESIZE_DEBUG_ITABLEMOVE)
1645                         printf("%d blocks of zeros...\n", n);
1646 #endif
1647                 num = fs->inode_blocks_per_group;
1648                 if (n > diff)
1649                         num -= n;
1650
1651                 retval = io_channel_write_blk(fs->io, new_blk,
1652                                               num, rfs->itable_buf);
1653                 if (retval) {
1654                         io_channel_write_blk(fs->io, old_blk,
1655                                              num, rfs->itable_buf);
1656                         goto errout;
1657                 }
1658                 if (n > diff) {
1659                         retval = io_channel_write_blk(fs->io,
1660                               old_blk + fs->inode_blocks_per_group,
1661                               diff, (rfs->itable_buf +
1662                                      (fs->inode_blocks_per_group - diff) *
1663                                      fs->blocksize));
1664                         if (retval)
1665                                 goto errout;
1666                 }
1667
1668                 for (blk = rfs->old_fs->group_desc[i].bg_inode_table, j=0;
1669                      j < fs->inode_blocks_per_group ; j++, blk++)
1670                         ext2fs_block_alloc_stats(fs, blk, -1);
1671
1672                 rfs->old_fs->group_desc[i].bg_inode_table = new_blk;
1673                 ext2fs_group_desc_csum_set(rfs->old_fs, i);
1674                 ext2fs_mark_super_dirty(rfs->old_fs);
1675                 ext2fs_flush(rfs->old_fs);
1676
1677                 if (rfs->progress) {
1678                         retval = rfs->progress(rfs, E2_RSZ_MOVE_ITABLE_PASS,
1679                                                ++moved, to_move);
1680                         if (retval)
1681                                 goto errout;
1682                 }
1683         }
1684         mark_table_blocks(fs, fs->block_map);
1685         ext2fs_flush(fs);
1686 #ifdef RESIZE2FS_DEBUG
1687         if (rfs->flags & RESIZE_DEBUG_ITABLEMOVE)
1688                 printf("Inode table move finished.\n");
1689 #endif
1690         return 0;
1691
1692 errout:
1693         return retval;
1694 }
1695
1696 /*
1697  * Fix the resize inode
1698  */
1699 static errcode_t fix_resize_inode(ext2_filsys fs)
1700 {
1701         struct ext2_inode       inode;
1702         errcode_t               retval;
1703         char *                  block_buf;
1704         blk_t                   blk;
1705
1706         if (!(fs->super->s_feature_compat &
1707               EXT2_FEATURE_COMPAT_RESIZE_INODE))
1708                 return 0;
1709
1710         retval = ext2fs_get_mem(fs->blocksize, &block_buf);
1711         if (retval) goto errout;
1712
1713         retval = ext2fs_read_inode(fs, EXT2_RESIZE_INO, &inode);
1714         if (retval) goto errout;
1715
1716         if (fs->super->s_reserved_gdt_blocks == 0) {
1717                 fs->super->s_feature_compat &=
1718                         ~EXT2_FEATURE_COMPAT_RESIZE_INODE;
1719                 ext2fs_mark_super_dirty(fs);
1720
1721                 if ((blk = inode.i_block[EXT2_DIND_BLOCK]) != 0)
1722                         ext2fs_block_alloc_stats(fs, blk, -1);
1723
1724                 memset(&inode, 0, sizeof(inode));
1725
1726                 retval = ext2fs_write_inode(fs, EXT2_RESIZE_INO, &inode);
1727                 goto errout;
1728         }
1729
1730         ext2fs_iblk_set(fs, &inode, 1);
1731
1732         retval = ext2fs_write_inode(fs, EXT2_RESIZE_INO, &inode);
1733         if (retval) goto errout;
1734
1735         if (!inode.i_block[EXT2_DIND_BLOCK]) {
1736                 /*
1737                  * Avoid zeroing out block #0; that's rude.  This
1738                  * should never happen anyway since the filesystem
1739                  * should be fsck'ed and we assume it is consistent.
1740                  */
1741                 fprintf(stderr,
1742                         _("Should never happen: resize inode corrupt!\n"));
1743                 exit(1);
1744         }
1745
1746         memset(block_buf, 0, fs->blocksize);
1747
1748         retval = io_channel_write_blk(fs->io, inode.i_block[EXT2_DIND_BLOCK],
1749                                       1, block_buf);
1750         if (retval) goto errout;
1751
1752         retval = ext2fs_create_resize_inode(fs);
1753         if (retval)
1754                 goto errout;
1755
1756 errout:
1757         if (block_buf)
1758                 ext2fs_free_mem(&block_buf);
1759         return retval;
1760 }
1761
1762 /*
1763  * Finally, recalculate the summary information
1764  */
1765 static errcode_t ext2fs_calculate_summary_stats(ext2_filsys fs)
1766 {
1767         blk_t           blk;
1768         ext2_ino_t      ino;
1769         unsigned int    group = 0;
1770         unsigned int    count = 0;
1771         int             total_free = 0;
1772         int             group_free = 0;
1773         int             uninit = 0;
1774         blk_t           super_blk, old_desc_blk, new_desc_blk;
1775         int             old_desc_blocks;
1776
1777         /*
1778          * First calculate the block statistics
1779          */
1780         uninit = fs->group_desc[group].bg_flags & EXT2_BG_BLOCK_UNINIT;
1781         ext2fs_super_and_bgd_loc(fs, group, &super_blk, &old_desc_blk,
1782                                  &new_desc_blk, 0);
1783         if (fs->super->s_feature_incompat & EXT2_FEATURE_INCOMPAT_META_BG)
1784                 old_desc_blocks = fs->super->s_first_meta_bg;
1785         else
1786                 old_desc_blocks = fs->desc_blocks +
1787                         fs->super->s_reserved_gdt_blocks;
1788         for (blk = fs->super->s_first_data_block;
1789              blk < fs->super->s_blocks_count; blk++) {
1790                 if ((uninit &&
1791                      !((blk == super_blk) ||
1792                        ((old_desc_blk && old_desc_blocks &&
1793                          (blk >= old_desc_blk) &&
1794                          (blk < old_desc_blk + old_desc_blocks))) ||
1795                        ((new_desc_blk && (blk == new_desc_blk))) ||
1796                        (blk == fs->group_desc[group].bg_block_bitmap) ||
1797                        (blk == fs->group_desc[group].bg_inode_bitmap) ||
1798                        ((blk >= fs->group_desc[group].bg_inode_table &&
1799                          (blk < fs->group_desc[group].bg_inode_table
1800                           + fs->inode_blocks_per_group))))) ||
1801                     (!ext2fs_fast_test_block_bitmap(fs->block_map, blk))) {
1802                         group_free++;
1803                         total_free++;
1804                 }
1805                 count++;
1806                 if ((count == fs->super->s_blocks_per_group) ||
1807                     (blk == fs->super->s_blocks_count-1)) {
1808                         fs->group_desc[group].bg_free_blocks_count =
1809                                 group_free;
1810                         ext2fs_group_desc_csum_set(fs, group);
1811                         group++;
1812                         count = 0;
1813                         group_free = 0;
1814                         uninit = (fs->group_desc[group].bg_flags &
1815                                   EXT2_BG_BLOCK_UNINIT);
1816                         ext2fs_super_and_bgd_loc(fs, group, &super_blk,
1817                                                  &old_desc_blk,
1818                                                  &new_desc_blk, 0);
1819                         if (fs->super->s_feature_incompat &
1820                             EXT2_FEATURE_INCOMPAT_META_BG)
1821                                 old_desc_blocks = fs->super->s_first_meta_bg;
1822                         else
1823                                 old_desc_blocks = fs->desc_blocks +
1824                                         fs->super->s_reserved_gdt_blocks;
1825                 }
1826         }
1827         fs->super->s_free_blocks_count = total_free;
1828
1829         /*
1830          * Next, calculate the inode statistics
1831          */
1832         group_free = 0;
1833         total_free = 0;
1834         count = 0;
1835         group = 0;
1836
1837         /* Protect loop from wrap-around if s_inodes_count maxed */
1838         uninit = fs->group_desc[group].bg_flags & EXT2_BG_INODE_UNINIT;
1839         for (ino = 1; ino <= fs->super->s_inodes_count && ino > 0; ino++) {
1840                 if (uninit ||
1841                     !ext2fs_fast_test_inode_bitmap(fs->inode_map, ino)) {
1842                         group_free++;
1843                         total_free++;
1844                 }
1845                 count++;
1846                 if ((count == fs->super->s_inodes_per_group) ||
1847                     (ino == fs->super->s_inodes_count)) {
1848                         fs->group_desc[group].bg_free_inodes_count =
1849                                 group_free;
1850                         ext2fs_group_desc_csum_set(fs, group);
1851                         group++;
1852                         count = 0;
1853                         group_free = 0;
1854                         uninit = (fs->group_desc[group].bg_flags &
1855                                   EXT2_BG_INODE_UNINIT);
1856                 }
1857         }
1858         fs->super->s_free_inodes_count = total_free;
1859         ext2fs_mark_super_dirty(fs);
1860         return 0;
1861 }
1862
1863 /*
1864  * calcluate the minimum number of blocks the given fs can be resized to
1865  */
1866 blk_t calculate_minimum_resize_size(ext2_filsys fs)
1867 {
1868         blk_t inode_count, blks_needed, groups, data_blocks;
1869         blk_t grp, data_needed, last_start;
1870         int overhead = 0, num_of_superblocks = 0;
1871
1872         /*
1873          * first figure out how many group descriptors we need to
1874          * handle the number of inodes we have
1875          */
1876         inode_count = fs->super->s_inodes_count -
1877                 fs->super->s_free_inodes_count;
1878         blks_needed = ext2fs_div_ceil(inode_count,
1879                                       fs->super->s_inodes_per_group) *
1880                 EXT2_BLOCKS_PER_GROUP(fs->super);
1881         groups = ext2fs_div_ceil(blks_needed,
1882                                  EXT2_BLOCKS_PER_GROUP(fs->super));
1883
1884         /*
1885          * we need to figure out how many backup superblocks we have so we can
1886          * account for that in the metadata
1887          */
1888         for (grp = 0; grp < fs->group_desc_count; grp++) {
1889                 if (ext2fs_bg_has_super(fs, grp))
1890                         num_of_superblocks++;
1891         }
1892
1893         /* calculate how many blocks are needed for data */
1894         data_needed = fs->super->s_blocks_count -
1895                 fs->super->s_free_blocks_count;
1896         data_needed -= SUPER_OVERHEAD(fs) * num_of_superblocks;
1897         data_needed -= META_OVERHEAD(fs) * fs->group_desc_count;
1898
1899         if (fs->super->s_feature_incompat & EXT4_FEATURE_INCOMPAT_FLEX_BG) {
1900                 /*
1901                  * For ext4 we need to allow for up to a flex_bg worth
1902                  * of inode tables of slack space so the resize
1903                  * operation can be guaranteed to finish.
1904                  */
1905                 int flexbg_size = 1 << fs->super->s_log_groups_per_flex;
1906                 int extra_groups;
1907
1908                 extra_groups = flexbg_size - (groups & (flexbg_size - 1));
1909                 data_needed += META_OVERHEAD(fs) * extra_groups;
1910         }
1911
1912         /*
1913          * figure out how many data blocks we have given the number of groups
1914          * we need for our inodes
1915          */
1916         data_blocks = groups * EXT2_BLOCKS_PER_GROUP(fs->super);
1917         last_start = 0;
1918         for (grp = 0; grp < groups; grp++) {
1919                 overhead = META_OVERHEAD(fs);
1920
1921                 if (ext2fs_bg_has_super(fs, grp))
1922                         overhead += SUPER_OVERHEAD(fs);
1923
1924                 /*
1925                  * we want to keep track of how much data we can store in
1926                  * the groups leading up to the last group so we can determine
1927                  * how big the last group needs to be
1928                  */
1929                 if (grp != (groups - 1))
1930                         last_start += EXT2_BLOCKS_PER_GROUP(fs->super) -
1931                                 overhead;
1932
1933                 data_blocks -= overhead;
1934         }
1935
1936         /*
1937          * if we need more group descriptors in order to accomodate our data
1938          * then we need to add them here
1939          */
1940         while (data_needed > data_blocks) {
1941                 blk_t remainder = data_needed - data_blocks;
1942                 blk_t extra_grps;
1943
1944                 /* figure out how many more groups we need for the data */
1945                 extra_grps = ext2fs_div_ceil(remainder,
1946                                              EXT2_BLOCKS_PER_GROUP(fs->super));
1947
1948                 data_blocks += extra_grps * EXT2_BLOCKS_PER_GROUP(fs->super);
1949
1950                 /* ok we have to account for the last group */
1951                 overhead = META_OVERHEAD(fs);
1952                 if (ext2fs_bg_has_super(fs, groups-1))
1953                         overhead += SUPER_OVERHEAD(fs);
1954                 last_start += EXT2_BLOCKS_PER_GROUP(fs->super) - overhead;
1955
1956                 for (grp = groups; grp < groups+extra_grps; grp++) {
1957                         overhead = META_OVERHEAD(fs);
1958                         if (ext2fs_bg_has_super(fs, grp))
1959                                 overhead += SUPER_OVERHEAD(fs);
1960
1961                         /*
1962                          * again, we need to see how much data we cram into
1963                          * all of the groups leading up to the last group
1964                          */
1965                         if (grp != (groups + extra_grps - 1))
1966                                 last_start += EXT2_BLOCKS_PER_GROUP(fs->super)
1967                                         - overhead;
1968
1969                         data_blocks -= overhead;
1970                 }
1971
1972                 groups += extra_grps;
1973         }
1974
1975         /* now for the fun voodoo */
1976         overhead = META_OVERHEAD(fs);
1977
1978         /*
1979          * if this is the case then the last group is going to have data in it
1980          * so we need to adjust the size of the last group accordingly
1981          */
1982         if (last_start < data_needed) {
1983                 blk_t remainder = data_needed - last_start;
1984
1985                 /*
1986                  * 50 is a magic number that mkfs/resize uses to see if its
1987                  * even worth making/resizing the fs.  basically you need to
1988                  * have at least 50 blocks in addition to the blocks needed
1989                  * for the metadata in the last group
1990                  */
1991                 if (remainder > 50)
1992                         overhead += remainder;
1993                 else
1994                         overhead += 50;
1995         } else
1996                 overhead += 50;
1997
1998         if (ext2fs_bg_has_super(fs, groups-1))
1999                 overhead += SUPER_OVERHEAD(fs);
2000
2001         /*
2002          * since our last group doesn't have to be BLOCKS_PER_GROUP large, we
2003          * only do groups-1, and then add the number of blocks needed to
2004          * handle the group descriptor metadata+data that we need
2005          */
2006         blks_needed = (groups-1) * EXT2_BLOCKS_PER_GROUP(fs->super);
2007         blks_needed += overhead;
2008
2009         /*
2010          * If at this point we've already added up more "needed" than
2011          * the current size, just return current size as minimum.
2012          */
2013         if (blks_needed >= fs->super->s_blocks_count)
2014                 return fs->super->s_blocks_count;
2015         /*
2016          * We need to reserve a few extra blocks if extents are
2017          * enabled, in case we need to grow the extent tree.  The more
2018          * we shrink the file system, the more space we need.
2019          */
2020         if (fs->super->s_feature_incompat & EXT3_FEATURE_INCOMPAT_EXTENTS)
2021                 blks_needed += (fs->super->s_blocks_count - blks_needed)/500;
2022
2023         return blks_needed;
2024 }