e2fsck/pass5.c

   1 /*
   2  * pass5.c --- check block and inode bitmaps against on-disk bitmaps
   3  *
   4  * Copyright (C) 1993, 1994, 1995, 1996, 1997 Theodore Ts'o.
   5  *
   6  * %Begin-Header%
   7  * This file may be redistributed under the terms of the GNU Public
   8  * License.
   9  * %End-Header%
  10  *
  11  */
  12
  13 #include "config.h"
  14 #include <stdint.h>
  15 #include <sys/types.h>
  16 #include <sys/stat.h>
  17 #include <sys/ioctl.h>
  18 #include <fcntl.h>
  19 #include <errno.h>
  20
  21 #include "e2fsck.h"
  22 #include "problem.h"
  23
  24 #define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))
  25
  26 static void check_block_bitmaps(e2fsck_t ctx);
  27 static void check_inode_bitmaps(e2fsck_t ctx);
  28 static void check_inode_end(e2fsck_t ctx);
  29 static void check_block_end(e2fsck_t ctx);
  30 static void check_inode_bitmap_checksum(e2fsck_t ctx);
  31 static void check_block_bitmap_checksum(e2fsck_t ctx);
  32
  33 void e2fsck_pass5(e2fsck_t ctx)
  34 {
  35 #ifdef RESOURCE_TRACK
  36         struct resource_track   rtrack;
  37 #endif
  38         struct problem_context  pctx;
  39
  40 #ifdef MTRACE
  41         mtrace_print("Pass 5");
  42 #endif
  43
  44         init_resource_track(&rtrack, ctx->fs->io);
  45         clear_problem_context(&pctx);
  46
  47         if (!(ctx->options & E2F_OPT_PREEN))
  48                 fix_problem(ctx, PR_5_PASS_HEADER, &pctx);
  49
  50         if (ctx->progress)
  51                 if ((ctx->progress)(ctx, 5, 0, ctx->fs->group_desc_count*2))
  52                         return;
  53
  54         e2fsck_read_bitmaps(ctx);
  55
  56         check_block_bitmaps(ctx);
  57         if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
  58                 return;
  59         check_inode_bitmaps(ctx);
  60         if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
  61                 return;
  62         check_inode_end(ctx);
  63         if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
  64                 return;
  65         check_block_end(ctx);
  66         if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
  67                 return;
  68
  69         check_inode_bitmap_checksum(ctx);
  70         check_block_bitmap_checksum(ctx);
  71
  72         ext2fs_free_inode_bitmap(ctx->inode_used_map);
  73         ctx->inode_used_map = 0;
  74         ext2fs_free_inode_bitmap(ctx->inode_dir_map);
  75         ctx->inode_dir_map = 0;
  76         ext2fs_free_block_bitmap(ctx->block_found_map);
  77         ctx->block_found_map = 0;
  78
  79         print_resource_track(ctx, _("Pass 5"), &rtrack, ctx->fs->io);
  80 }
  81
  82 static void check_inode_bitmap_checksum(e2fsck_t ctx)
  83 {
  84         struct problem_context  pctx;
  85         char            *buf;
  86         dgrp_t          i;
  87         int             nbytes;
  88         ext2_ino_t      ino_itr;
  89         errcode_t       retval;
  90
  91         if (!EXT2_HAS_RO_COMPAT_FEATURE(ctx->fs->super,
  92                                         EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
  93                 return;
  94
  95         /* If bitmap is dirty from being fixed, checksum will be corrected */
  96         if (ext2fs_test_ib_dirty(ctx->fs))
  97                 return;
  98
  99         nbytes = (size_t)(EXT2_INODES_PER_GROUP(ctx->fs->super) / 8);
 100         retval = ext2fs_get_memalign(ctx->fs->blocksize, ctx->fs->blocksize,
 101                                      &buf);
 102         if (retval) {
 103                 com_err(ctx->program_name, 0,
 104                     _("check_inode_bitmap_checksum: Memory allocation error"));
 105                 fatal_error(ctx, 0);
 106         }
 107
 108         clear_problem_context(&pctx);
 109         for (i = 0; i < ctx->fs->group_desc_count; i++) {
 110                 if (ext2fs_bg_flags_test(ctx->fs, i, EXT2_BG_INODE_UNINIT))
 111                         continue;
 112
 113                 ino_itr = 1 + (i * (nbytes << 3));
 114                 retval = ext2fs_get_inode_bitmap_range2(ctx->fs->inode_map,
 115                                                         ino_itr, nbytes << 3,
 116                                                         buf);
 117                 if (retval)
 118                         break;
 119
 120                 if (ext2fs_inode_bitmap_csum_verify(ctx->fs, i, buf, nbytes))
 121                         continue;
 122                 pctx.group = i;
 123                 if (!fix_problem(ctx, PR_5_INODE_BITMAP_CSUM_INVALID, &pctx))
 124                         continue;
 125
 126                 /*
 127                  * Fixing one checksum will rewrite all of them.  The bitmap
 128                  * will be checked against the one we made during pass1 for
 129                  * discrepancies, and fixed if need be.
 130                  */
 131                 ext2fs_mark_ib_dirty(ctx->fs);
 132                 break;
 133         }
 134
 135         ext2fs_free_mem(&buf);
 136 }
 137
 138 static void check_block_bitmap_checksum(e2fsck_t ctx)
 139 {
 140         struct problem_context  pctx;
 141         char            *buf;
 142         dgrp_t          i;
 143         int             nbytes;
 144         blk64_t         blk_itr;
 145         errcode_t       retval;
 146
 147         if (!EXT2_HAS_RO_COMPAT_FEATURE(ctx->fs->super,
 148                                         EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
 149                 return;
 150
 151         /* If bitmap is dirty from being fixed, checksum will be corrected */
 152         if (ext2fs_test_bb_dirty(ctx->fs))
 153                 return;
 154
 155         nbytes = (size_t)(EXT2_CLUSTERS_PER_GROUP(ctx->fs->super) / 8);
 156         retval = ext2fs_get_memalign(ctx->fs->blocksize, ctx->fs->blocksize,
 157                                      &buf);
 158         if (retval) {
 159                 com_err(ctx->program_name, 0,
 160                     _("check_block_bitmap_checksum: Memory allocation error"));
 161                 fatal_error(ctx, 0);
 162         }
 163
 164         clear_problem_context(&pctx);
 165         for (i = 0; i < ctx->fs->group_desc_count; i++) {
 166                 if (ext2fs_bg_flags_test(ctx->fs, i, EXT2_BG_BLOCK_UNINIT))
 167                         continue;
 168
 169                 blk_itr = EXT2FS_B2C(ctx->fs,
 170                                      ctx->fs->super->s_first_data_block) +
 171                           ((blk64_t) i * (nbytes << 3));
 172                 retval = ext2fs_get_block_bitmap_range2(ctx->fs->block_map,
 173                                                         blk_itr, nbytes << 3,
 174                                                         buf);
 175                 if (retval)
 176                         break;
 177
 178                 if (ext2fs_block_bitmap_csum_verify(ctx->fs, i, buf, nbytes))
 179                         continue;
 180                 pctx.group = i;
 181                 if (!fix_problem(ctx, PR_5_BLOCK_BITMAP_CSUM_INVALID, &pctx))
 182                         continue;
 183
 184                 /*
 185                  * Fixing one checksum will rewrite all of them.  The bitmap
 186                  * will be checked against the one we made during pass1 for
 187                  * discrepancies, and fixed if need be.
 188                  */
 189                 ext2fs_mark_bb_dirty(ctx->fs);
 190                 break;
 191         }
 192
 193         ext2fs_free_mem(&buf);
 194 }
 195
 196 static void e2fsck_discard_blocks(e2fsck_t ctx, blk64_t start,
 197                                   blk64_t count)
 198 {
 199         ext2_filsys fs = ctx->fs;
 200
 201         /*
 202          * If the filesystem has changed it means that there was an corruption
 203          * which should be repaired, but in some cases just one e2fsck run is
 204          * not enough to fix the problem, hence it is not safe to run discard
 205          * in this case.
 206          */
 207         if (ext2fs_test_changed(fs))
 208                 ctx->options &= ~E2F_OPT_DISCARD;
 209
 210         if ((ctx->options & E2F_OPT_DISCARD) &&
 211             (io_channel_discard(fs->io, start, count)))
 212                 ctx->options &= ~E2F_OPT_DISCARD;
 213 }
 214
 215 /*
 216  * This will try to discard number 'count' inodes starting at
 217  * inode number 'start' within the 'group'. Note that 'start'
 218  * is 1-based, it means that we need to adjust it by -1 in this
 219  * function to compute right offset in the particular inode table.
 220  */
 221 static void e2fsck_discard_inodes(e2fsck_t ctx, dgrp_t group,
 222                                   ext2_ino_t start, int count)
 223 {
 224         ext2_filsys fs = ctx->fs;
 225         blk64_t blk, num;
 226
 227         /*
 228          * Sanity check for 'start'
 229          */
 230         if ((start < 1) || (start > EXT2_INODES_PER_GROUP(fs->super))) {
 231                 printf("PROGRAMMING ERROR: Got start %d outside of group %d!"
 232                        " Disabling discard\n",
 233                         start, group);
 234                 ctx->options &= ~E2F_OPT_DISCARD;
 235         }
 236
 237         /*
 238          * Do not attempt to discard if E2F_OPT_DISCARD is not set. And also
 239          * skip the discard on this group if discard does not zero data.
 240          * The reason is that if the inode table is not zeroed discard would
 241          * no help us since we need to zero it anyway, or if the inode table
 242          * is zeroed then the read after discard would not be deterministic
 243          * anyway and we would not be able to assume that this inode table
 244          * was zeroed anymore so we would have to zero it again, which does
 245          * not really make sense.
 246          */
 247         if (!(ctx->options & E2F_OPT_DISCARD) ||
 248             !io_channel_discard_zeroes_data(fs->io))
 249                 return;
 250
 251         /*
 252          * Start is inode number within the group which starts
 253          * counting from 1, so we need to adjust it.
 254          */
 255         start -= 1;
 256
 257         /*
 258          * We can discard only blocks containing only unused
 259          * inodes in the table.
 260          */
 261         blk = DIV_ROUND_UP(start,
 262                 EXT2_INODES_PER_BLOCK(fs->super));
 263         count -= (blk * EXT2_INODES_PER_BLOCK(fs->super) - start);
 264         blk += ext2fs_inode_table_loc(fs, group);
 265         num = count / EXT2_INODES_PER_BLOCK(fs->super);
 266
 267         if (num > 0)
 268                 e2fsck_discard_blocks(ctx, blk, num);
 269 }
 270
 271 #define NO_BLK ((blk64_t) -1)
 272
 273 static void print_bitmap_problem(e2fsck_t ctx, problem_t problem,
 274                             struct problem_context *pctx)
 275 {
 276         switch (problem) {
 277         case PR_5_BLOCK_UNUSED:
 278                 if (pctx->blk == pctx->blk2)
 279                         pctx->blk2 = 0;
 280                 else
 281                         problem = PR_5_BLOCK_RANGE_UNUSED;
 282                 break;
 283         case PR_5_BLOCK_USED:
 284                 if (pctx->blk == pctx->blk2)
 285                         pctx->blk2 = 0;
 286                 else
 287                         problem = PR_5_BLOCK_RANGE_USED;
 288                 break;
 289         case PR_5_INODE_UNUSED:
 290                 if (pctx->ino == pctx->ino2)
 291                         pctx->ino2 = 0;
 292                 else
 293                         problem = PR_5_INODE_RANGE_UNUSED;
 294                 break;
 295         case PR_5_INODE_USED:
 296                 if (pctx->ino == pctx->ino2)
 297                         pctx->ino2 = 0;
 298                 else
 299                         problem = PR_5_INODE_RANGE_USED;
 300                 break;
 301         }
 302         fix_problem(ctx, problem, pctx);
 303         pctx->blk = pctx->blk2 = NO_BLK;
 304         pctx->ino = pctx->ino2 = 0;
 305 }
 306
 307 /* Just to be more succint */
 308 #define B2C(x)  EXT2FS_B2C(fs, (x))
 309 #define EQ_CLSTR(x, y) (B2C(x) == B2C(y))
 310 #define LE_CLSTR(x, y) (B2C(x) <= B2C(y))
 311 #define GE_CLSTR(x, y) (B2C(x) >= B2C(y))
 312
 313 static void check_block_bitmaps(e2fsck_t ctx)
 314 {
 315         ext2_filsys fs = ctx->fs;
 316         blk64_t i;
 317         unsigned int    *free_array;
 318         dgrp_t          g, group = 0;
 319         unsigned int    blocks = 0;
 320         blk64_t free_blocks = 0;
 321         blk64_t first_free = ext2fs_blocks_count(fs->super);
 322         unsigned int    group_free = 0;
 323         int     actual, bitmap;
 324         struct problem_context  pctx;
 325         problem_t       problem, save_problem;
 326         int             fixit, had_problem;
 327         errcode_t       retval;
 328         int             csum_flag;
 329         int             skip_group = 0;
 330         int     old_desc_blocks = 0;
 331         int     count = 0;
 332         int     cmp_block = 0;
 333         int     redo_flag = 0;
 334         blk64_t super_blk, old_desc_blk, new_desc_blk;
 335         char *actual_buf, *bitmap_buf;
 336
 337         actual_buf = (char *) e2fsck_allocate_memory(ctx, fs->blocksize,
 338                                                      "actual bitmap buffer");
 339         bitmap_buf = (char *) e2fsck_allocate_memory(ctx, fs->blocksize,
 340                                                      "bitmap block buffer");
 341
 342         clear_problem_context(&pctx);
 343         free_array = (unsigned int *) e2fsck_allocate_memory(ctx,
 344             fs->group_desc_count * sizeof(unsigned int), "free block count array");
 345
 346         if ((B2C(fs->super->s_first_data_block) <
 347              ext2fs_get_block_bitmap_start2(ctx->block_found_map)) ||
 348             (B2C(ext2fs_blocks_count(fs->super)-1) >
 349              ext2fs_get_block_bitmap_end2(ctx->block_found_map))) {
 350                 pctx.num = 1;
 351                 pctx.blk = B2C(fs->super->s_first_data_block);
 352                 pctx.blk2 = B2C(ext2fs_blocks_count(fs->super) - 1);
 353                 pctx.ino = ext2fs_get_block_bitmap_start2(ctx->block_found_map);
 354                 pctx.ino2 = ext2fs_get_block_bitmap_end2(ctx->block_found_map);
 355                 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
 356
 357                 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
 358                 goto errout;
 359         }
 360
 361         if ((B2C(fs->super->s_first_data_block) <
 362              ext2fs_get_block_bitmap_start2(fs->block_map)) ||
 363             (B2C(ext2fs_blocks_count(fs->super)-1) >
 364              ext2fs_get_block_bitmap_end2(fs->block_map))) {
 365                 pctx.num = 2;
 366                 pctx.blk = B2C(fs->super->s_first_data_block);
 367                 pctx.blk2 = B2C(ext2fs_blocks_count(fs->super) - 1);
 368                 pctx.ino = ext2fs_get_block_bitmap_start2(fs->block_map);
 369                 pctx.ino2 = ext2fs_get_block_bitmap_end2(fs->block_map);
 370                 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
 371
 372                 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
 373                 goto errout;
 374         }
 375
 376         csum_flag = ext2fs_has_group_desc_csum(fs);
 377 redo_counts:
 378         had_problem = 0;
 379         save_problem = 0;
 380         pctx.blk = pctx.blk2 = NO_BLK;
 381         if (csum_flag &&
 382             (ext2fs_bg_flags_test(fs, group, EXT2_BG_BLOCK_UNINIT)))
 383                 skip_group++;
 384         for (i = B2C(fs->super->s_first_data_block);
 385              i < ext2fs_blocks_count(fs->super);
 386              i += EXT2FS_CLUSTER_RATIO(fs)) {
 387                 int first_block_in_bg = (B2C(i) -
 388                                          B2C(fs->super->s_first_data_block)) %
 389                         fs->super->s_clusters_per_group == 0;
 390                 int n, nbytes = fs->super->s_clusters_per_group / 8;
 391
 392                 actual = ext2fs_fast_test_block_bitmap2(ctx->block_found_map, i);
 393
 394                 /*
 395                  * Try to optimize pass5 by extracting a bitmap block
 396                  * as expected from what we have on disk, and then
 397                  * comparing the two.  If they are identical, then
 398                  * update the free block counts and go on to the next
 399                  * block group.  This is much faster than doing the
 400                  * individual bit-by-bit comparison.  The one downside
 401                  * is that this doesn't work if we are asking e2fsck
 402                  * to do a discard operation.
 403                  */
 404                 if (!first_block_in_bg ||
 405                     (group == (int)fs->group_desc_count - 1) ||
 406                     (ctx->options & E2F_OPT_DISCARD))
 407                         goto no_optimize;
 408
 409                 retval = ext2fs_get_block_bitmap_range2(ctx->block_found_map,
 410                                 B2C(i), fs->super->s_clusters_per_group,
 411                                 actual_buf);
 412                 if (retval)
 413                         goto no_optimize;
 414                 if (ext2fs_bg_flags_test(fs, group, EXT2_BG_BLOCK_UNINIT))
 415                         memset(bitmap_buf, 0, nbytes);
 416                 else {
 417                         retval = ext2fs_get_block_bitmap_range2(fs->block_map,
 418                                         B2C(i), fs->super->s_clusters_per_group,
 419                                         bitmap_buf);
 420                         if (retval)
 421                                 goto no_optimize;
 422                 }
 423                 if (memcmp(actual_buf, bitmap_buf, nbytes) != 0)
 424                         goto no_optimize;
 425                 n = ext2fs_bitcount(actual_buf, nbytes);
 426                 group_free = fs->super->s_clusters_per_group - n;
 427                 free_blocks += group_free;
 428                 i += EXT2FS_C2B(fs, fs->super->s_clusters_per_group - 1);
 429                 goto next_group;
 430         no_optimize:
 431
 432                 if (skip_group) {
 433                         if (first_block_in_bg) {
 434                                 super_blk = 0;
 435                                 old_desc_blk = 0;
 436                                 new_desc_blk = 0;
 437                                 ext2fs_super_and_bgd_loc2(fs, group, &super_blk,
 438                                          &old_desc_blk, &new_desc_blk, 0);
 439
 440                                 if (fs->super->s_feature_incompat &
 441                                                 EXT2_FEATURE_INCOMPAT_META_BG)
 442                                         old_desc_blocks =
 443                                                 fs->super->s_first_meta_bg;
 444                                 else
 445                                         old_desc_blocks = fs->desc_blocks +
 446                                         fs->super->s_reserved_gdt_blocks;
 447
 448                                 count = 0;
 449                                 cmp_block = fs->super->s_clusters_per_group;
 450                                 if (group == (int)fs->group_desc_count - 1)
 451                                         cmp_block = EXT2FS_NUM_B2C(fs,
 452                                                     ext2fs_group_blocks_count(fs, group));
 453                         }
 454
 455                         bitmap = 0;
 456                         if (EQ_CLSTR(i, super_blk) ||
 457                             (old_desc_blk && old_desc_blocks &&
 458                              GE_CLSTR(i, old_desc_blk) &&
 459                              LE_CLSTR(i, old_desc_blk + old_desc_blocks-1)) ||
 460                             (new_desc_blk && EQ_CLSTR(i, new_desc_blk)) ||
 461                             EQ_CLSTR(i, ext2fs_block_bitmap_loc(fs, group)) ||
 462                             EQ_CLSTR(i, ext2fs_inode_bitmap_loc(fs, group)) ||
 463                             (GE_CLSTR(i, ext2fs_inode_table_loc(fs, group)) &&
 464                              LE_CLSTR(i, (ext2fs_inode_table_loc(fs, group) +
 465                                           fs->inode_blocks_per_group - 1)))) {
 466                                 bitmap = 1;
 467                                 actual = (actual != 0);
 468                                 count++;
 469                                 cmp_block--;
 470                         } else if ((EXT2FS_B2C(fs, i) - count -
 471                                     EXT2FS_B2C(fs, fs->super->s_first_data_block)) %
 472                                    fs->super->s_clusters_per_group == 0) {
 473                                 /*
 474                                  * When the compare data blocks in block bitmap
 475                                  * are 0, count the free block,
 476                                  * skip the current block group.
 477                                  */
 478                                 if (ext2fs_test_block_bitmap_range2(
 479                                             ctx->block_found_map,
 480                                             EXT2FS_B2C(fs, i),
 481                                             cmp_block)) {
 482                                         /*
 483                                          * -1 means to skip the current block
 484                                          * group.
 485                                          */
 486                                         blocks = fs->super->s_clusters_per_group - 1;
 487                                         group_free = cmp_block;
 488                                         free_blocks += cmp_block;
 489                                         /*
 490                                          * The current block group's last block
 491                                          * is set to i.
 492                                          */
 493                                         i += EXT2FS_C2B(fs, cmp_block - 1);
 494                                         bitmap = 1;
 495                                         goto do_counts;
 496                                 }
 497                         }
 498                 } else if (redo_flag)
 499                         bitmap = actual;
 500                 else
 501                         bitmap = ext2fs_fast_test_block_bitmap2(fs->block_map, i);
 502
 503                 if (!actual == !bitmap)
 504                         goto do_counts;
 505
 506                 if (!actual && bitmap) {
 507                         /*
 508                          * Block not used, but marked in use in the bitmap.
 509                          */
 510                         problem = PR_5_BLOCK_UNUSED;
 511                 } else {
 512                         /*
 513                          * Block used, but not marked in use in the bitmap.
 514                          */
 515                         problem = PR_5_BLOCK_USED;
 516
 517                         if (skip_group) {
 518                                 struct problem_context pctx2;
 519                                 pctx2.blk = i;
 520                                 pctx2.group = group;
 521                                 if (fix_problem(ctx, PR_5_BLOCK_UNINIT,&pctx2)){
 522                                         ext2fs_bg_flags_clear(fs, group, EXT2_BG_BLOCK_UNINIT);
 523                                         skip_group = 0;
 524                                 }
 525                         }
 526                 }
 527                 if (pctx.blk == NO_BLK) {
 528                         pctx.blk = pctx.blk2 = i;
 529                         save_problem = problem;
 530                 } else {
 531                         if ((problem == save_problem) &&
 532                             (pctx.blk2 == i-1))
 533                                 pctx.blk2++;
 534                         else {
 535                                 print_bitmap_problem(ctx, save_problem, &pctx);
 536                                 pctx.blk = pctx.blk2 = i;
 537                                 save_problem = problem;
 538                         }
 539                 }
 540                 ctx->flags |= E2F_FLAG_PROG_SUPPRESS;
 541                 had_problem++;
 542
 543                 /*
 544                  * If there a problem we should turn off the discard so we
 545                  * do not compromise the filesystem.
 546                  */
 547                 ctx->options &= ~E2F_OPT_DISCARD;
 548
 549         do_counts:
 550                 if (!bitmap) {
 551                         group_free++;
 552                         free_blocks++;
 553                         if (first_free > i)
 554                                 first_free = i;
 555                 } else if (i > first_free) {
 556                         e2fsck_discard_blocks(ctx, first_free,
 557                                               (i - first_free));
 558                         first_free = ext2fs_blocks_count(fs->super);
 559                 }
 560                 blocks ++;
 561                 if ((blocks == fs->super->s_clusters_per_group) ||
 562                     (EXT2FS_B2C(fs, i) ==
 563                      EXT2FS_B2C(fs, ext2fs_blocks_count(fs->super)-1))) {
 564                         /*
 565                          * If the last block of this group is free, then we can
 566                          * discard it as well.
 567                          */
 568                         if (!bitmap && i >= first_free)
 569                                 e2fsck_discard_blocks(ctx, first_free,
 570                                                       (i - first_free) + 1);
 571                 next_group:
 572                         first_free = ext2fs_blocks_count(fs->super);
 573
 574                         free_array[group] = group_free;
 575                         group ++;
 576                         blocks = 0;
 577                         group_free = 0;
 578                         skip_group = 0;
 579                         if (ctx->progress)
 580                                 if ((ctx->progress)(ctx, 5, group,
 581                                                     fs->group_desc_count*2))
 582                                         goto errout;
 583                         if (csum_flag &&
 584                             (i != ext2fs_blocks_count(fs->super)-1) &&
 585                             ext2fs_bg_flags_test(fs, group,
 586                                                 EXT2_BG_BLOCK_UNINIT))
 587                                 skip_group++;
 588                 }
 589         }
 590         if (pctx.blk != NO_BLK)
 591                 print_bitmap_problem(ctx, save_problem, &pctx);
 592         if (had_problem)
 593                 fixit = end_problem_latch(ctx, PR_LATCH_BBITMAP);
 594         else
 595                 fixit = -1;
 596         ctx->flags &= ~E2F_FLAG_PROG_SUPPRESS;
 597
 598         if (fixit == 1) {
 599                 ext2fs_free_block_bitmap(fs->block_map);
 600                 retval = ext2fs_copy_bitmap(ctx->block_found_map,
 601                                                   &fs->block_map);
 602                 if (retval) {
 603                         clear_problem_context(&pctx);
 604                         fix_problem(ctx, PR_5_COPY_BBITMAP_ERROR, &pctx);
 605                         ctx->flags |= E2F_FLAG_ABORT;
 606                         goto errout;
 607                 }
 608                 ext2fs_set_bitmap_padding(fs->block_map);
 609                 ext2fs_mark_bb_dirty(fs);
 610
 611                 /* Redo the counts */
 612                 blocks = 0; free_blocks = 0; group_free = 0; group = 0;
 613                 memset(free_array, 0, fs->group_desc_count * sizeof(int));
 614                 redo_flag++;
 615                 goto redo_counts;
 616         } else if (fixit == 0)
 617                 ext2fs_unmark_valid(fs);
 618
 619         for (g = 0; g < fs->group_desc_count; g++) {
 620                 if (free_array[g] != ext2fs_bg_free_blocks_count(fs, g)) {
 621                         pctx.group = g;
 622                         pctx.blk = ext2fs_bg_free_blocks_count(fs, g);
 623                         pctx.blk2 = free_array[g];
 624
 625                         if (fix_problem(ctx, PR_5_FREE_BLOCK_COUNT_GROUP,
 626                                         &pctx)) {
 627                                 ext2fs_bg_free_blocks_count_set(fs, g, free_array[g]);
 628                                 ext2fs_mark_super_dirty(fs);
 629                         } else
 630                                 ext2fs_unmark_valid(fs);
 631                 }
 632         }
 633         free_blocks = EXT2FS_C2B(fs, free_blocks);
 634         if (free_blocks != ext2fs_free_blocks_count(fs->super)) {
 635                 pctx.group = 0;
 636                 pctx.blk = ext2fs_free_blocks_count(fs->super);
 637                 pctx.blk2 = free_blocks;
 638
 639                 if (fix_problem(ctx, PR_5_FREE_BLOCK_COUNT, &pctx)) {
 640                         ext2fs_free_blocks_count_set(fs->super, free_blocks);
 641                         ext2fs_mark_super_dirty(fs);
 642                 }
 643         }
 644 errout:
 645         ext2fs_free_mem(&free_array);
 646         ext2fs_free_mem(&actual_buf);
 647         ext2fs_free_mem(&bitmap_buf);
 648 }
 649
 650 static void check_inode_bitmaps(e2fsck_t ctx)
 651 {
 652         ext2_filsys fs = ctx->fs;
 653         ext2_ino_t      i;
 654         unsigned int    free_inodes = 0;
 655         int             group_free = 0;
 656         int             dirs_count = 0;
 657         dgrp_t          group = 0;
 658         unsigned int    inodes = 0;
 659         ext2_ino_t      *free_array;
 660         ext2_ino_t      *dir_array;
 661         int             actual, bitmap;
 662         errcode_t       retval;
 663         struct problem_context  pctx;
 664         problem_t       problem, save_problem;
 665         int             fixit, had_problem;
 666         int             csum_flag;
 667         int             skip_group = 0;
 668         int             redo_flag = 0;
 669         ext2_ino_t              first_free = fs->super->s_inodes_per_group + 1;
 670
 671         clear_problem_context(&pctx);
 672         free_array = (ext2_ino_t *) e2fsck_allocate_memory(ctx,
 673             fs->group_desc_count * sizeof(ext2_ino_t), "free inode count array");
 674
 675         dir_array = (ext2_ino_t *) e2fsck_allocate_memory(ctx,
 676            fs->group_desc_count * sizeof(ext2_ino_t), "directory count array");
 677
 678         if ((1 < ext2fs_get_inode_bitmap_start2(ctx->inode_used_map)) ||
 679             (fs->super->s_inodes_count >
 680              ext2fs_get_inode_bitmap_end2(ctx->inode_used_map))) {
 681                 pctx.num = 3;
 682                 pctx.blk = 1;
 683                 pctx.blk2 = fs->super->s_inodes_count;
 684                 pctx.ino = ext2fs_get_inode_bitmap_start2(ctx->inode_used_map);
 685                 pctx.ino2 = ext2fs_get_inode_bitmap_end2(ctx->inode_used_map);
 686                 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
 687
 688                 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
 689                 goto errout;
 690         }
 691         if ((1 < ext2fs_get_inode_bitmap_start2(fs->inode_map)) ||
 692             (fs->super->s_inodes_count >
 693              ext2fs_get_inode_bitmap_end2(fs->inode_map))) {
 694                 pctx.num = 4;
 695                 pctx.blk = 1;
 696                 pctx.blk2 = fs->super->s_inodes_count;
 697                 pctx.ino = ext2fs_get_inode_bitmap_start2(fs->inode_map);
 698                 pctx.ino2 = ext2fs_get_inode_bitmap_end2(fs->inode_map);
 699                 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
 700
 701                 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
 702                 goto errout;
 703         }
 704
 705         csum_flag = ext2fs_has_group_desc_csum(fs);
 706 redo_counts:
 707         had_problem = 0;
 708         save_problem = 0;
 709         pctx.ino = pctx.ino2 = 0;
 710         if (csum_flag &&
 711             (ext2fs_bg_flags_test(fs, group, EXT2_BG_INODE_UNINIT)))
 712                 skip_group++;
 713
 714         /* Protect loop from wrap-around if inodes_count is maxed */
 715         for (i = 1; i <= fs->super->s_inodes_count && i > 0; i++) {
 716                 bitmap = 0;
 717                 if (skip_group &&
 718                     i % fs->super->s_inodes_per_group == 1) {
 719                         /*
 720                          * Current inode is the first inode
 721                          * in the current block group.
 722                          */
 723                         if (ext2fs_test_inode_bitmap_range(
 724                                     ctx->inode_used_map, i,
 725                                     fs->super->s_inodes_per_group)) {
 726                                 /*
 727                                  * When the compared inodes in inodes bitmap
 728                                  * are 0, count the free inode,
 729                                  * skip the current block group.
 730                                  */
 731                                 first_free = 1;
 732                                 inodes = fs->super->s_inodes_per_group - 1;
 733                                 group_free = inodes;
 734                                 free_inodes += inodes;
 735                                 i += inodes;
 736                                 skip_group = 0;
 737                                 goto do_counts;
 738                         }
 739                 }
 740
 741                 actual = ext2fs_fast_test_inode_bitmap2(ctx->inode_used_map, i);
 742                 if (redo_flag)
 743                         bitmap = actual;
 744                 else if (!skip_group)
 745                         bitmap = ext2fs_fast_test_inode_bitmap2(fs->inode_map, i);
 746                 if (!actual == !bitmap)
 747                         goto do_counts;
 748
 749                 if (!actual && bitmap) {
 750                         /*
 751                          * Inode wasn't used, but marked in bitmap
 752                          */
 753                         problem = PR_5_INODE_UNUSED;
 754                 } else /* if (actual && !bitmap) */ {
 755                         /*
 756                          * Inode used, but not in bitmap
 757                          */
 758                         problem = PR_5_INODE_USED;
 759
 760                         /* We should never hit this, because it means that
 761                          * inodes were marked in use that weren't noticed
 762                          * in pass1 or pass 2. It is easier to fix the problem
 763                          * than to kill e2fsck and leave the user stuck. */
 764                         if (skip_group) {
 765                                 struct problem_context pctx2;
 766                                 pctx2.blk = i;
 767                                 pctx2.group = group;
 768                                 if (fix_problem(ctx, PR_5_INODE_UNINIT,&pctx2)){
 769                                         ext2fs_bg_flags_clear(fs, group, EXT2_BG_INODE_UNINIT);
 770                                         skip_group = 0;
 771                                 }
 772                         }
 773                 }
 774                 if (pctx.ino == 0) {
 775                         pctx.ino = pctx.ino2 = i;
 776                         save_problem = problem;
 777                 } else {
 778                         if ((problem == save_problem) &&
 779                             (pctx.ino2 == i-1))
 780                                 pctx.ino2++;
 781                         else {
 782                                 print_bitmap_problem(ctx, save_problem, &pctx);
 783                                 pctx.ino = pctx.ino2 = i;
 784                                 save_problem = problem;
 785                         }
 786                 }
 787                 ctx->flags |= E2F_FLAG_PROG_SUPPRESS;
 788                 had_problem++;
 789                 /*
 790                  * If there a problem we should turn off the discard so we
 791                  * do not compromise the filesystem.
 792                  */
 793                 ctx->options &= ~E2F_OPT_DISCARD;
 794
 795 do_counts:
 796                 inodes++;
 797                 if (bitmap) {
 798                         if (ext2fs_test_inode_bitmap2(ctx->inode_dir_map, i))
 799                                 dirs_count++;
 800                         if (inodes > first_free) {
 801                                 e2fsck_discard_inodes(ctx, group, first_free,
 802                                                       inodes - first_free);
 803                                 first_free = fs->super->s_inodes_per_group + 1;
 804                         }
 805                 } else {
 806                         group_free++;
 807                         free_inodes++;
 808                         if (first_free > inodes)
 809                                 first_free = inodes;
 810                 }
 811
 812                 if ((inodes == fs->super->s_inodes_per_group) ||
 813                     (i == fs->super->s_inodes_count)) {
 814                         /*
 815                          * If the last inode is free, we can discard it as well.
 816                          */
 817                         if (!bitmap && inodes >= first_free)
 818                                 e2fsck_discard_inodes(ctx, group, first_free,
 819                                                       inodes - first_free + 1);
 820                         /*
 821                          * If discard zeroes data and the group inode table
 822                          * was not zeroed yet, set itable as zeroed
 823                          */
 824                         if ((ctx->options & E2F_OPT_DISCARD) &&
 825                             io_channel_discard_zeroes_data(fs->io) &&
 826                             !(ext2fs_bg_flags_test(fs, group,
 827                                                    EXT2_BG_INODE_ZEROED))) {
 828                                 ext2fs_bg_flags_set(fs, group,
 829                                                     EXT2_BG_INODE_ZEROED);
 830                                 ext2fs_group_desc_csum_set(fs, group);
 831                         }
 832
 833                         first_free = fs->super->s_inodes_per_group + 1;
 834                         free_array[group] = group_free;
 835                         dir_array[group] = dirs_count;
 836                         group ++;
 837                         inodes = 0;
 838                         skip_group = 0;
 839                         group_free = 0;
 840                         dirs_count = 0;
 841                         if (ctx->progress)
 842                                 if ((ctx->progress)(ctx, 5,
 843                                             group + fs->group_desc_count,
 844                                             fs->group_desc_count*2))
 845                                         goto errout;
 846                         if (csum_flag &&
 847                             (i != fs->super->s_inodes_count) &&
 848                             (ext2fs_bg_flags_test(fs, group, EXT2_BG_INODE_UNINIT)
 849                              ))
 850                                 skip_group++;
 851                 }
 852         }
 853         if (pctx.ino)
 854                 print_bitmap_problem(ctx, save_problem, &pctx);
 855
 856         if (had_problem)
 857                 fixit = end_problem_latch(ctx, PR_LATCH_IBITMAP);
 858         else
 859                 fixit = -1;
 860         ctx->flags &= ~E2F_FLAG_PROG_SUPPRESS;
 861
 862         if (fixit == 1) {
 863                 ext2fs_free_inode_bitmap(fs->inode_map);
 864                 retval = ext2fs_copy_bitmap(ctx->inode_used_map,
 865                                                   &fs->inode_map);
 866                 if (retval) {
 867                         clear_problem_context(&pctx);
 868                         fix_problem(ctx, PR_5_COPY_IBITMAP_ERROR, &pctx);
 869                         ctx->flags |= E2F_FLAG_ABORT;
 870                         goto errout;
 871                 }
 872                 ext2fs_set_bitmap_padding(fs->inode_map);
 873                 ext2fs_mark_ib_dirty(fs);
 874
 875                 /* redo counts */
 876                 inodes = 0; free_inodes = 0; group_free = 0;
 877                 dirs_count = 0; group = 0;
 878                 memset(free_array, 0, fs->group_desc_count * sizeof(int));
 879                 memset(dir_array, 0, fs->group_desc_count * sizeof(int));
 880                 redo_flag++;
 881                 goto redo_counts;
 882         } else if (fixit == 0)
 883                 ext2fs_unmark_valid(fs);
 884
 885         for (i = 0; i < fs->group_desc_count; i++) {
 886                 if (free_array[i] != ext2fs_bg_free_inodes_count(fs, i)) {
 887                         pctx.group = i;
 888                         pctx.ino = ext2fs_bg_free_inodes_count(fs, i);
 889                         pctx.ino2 = free_array[i];
 890                         if (fix_problem(ctx, PR_5_FREE_INODE_COUNT_GROUP,
 891                                         &pctx)) {
 892                                 ext2fs_bg_free_inodes_count_set(fs, i, free_array[i]);
 893                                 ext2fs_mark_super_dirty(fs);
 894                         } else
 895                                 ext2fs_unmark_valid(fs);
 896                 }
 897                 if (dir_array[i] != ext2fs_bg_used_dirs_count(fs, i)) {
 898                         pctx.group = i;
 899                         pctx.ino = ext2fs_bg_used_dirs_count(fs, i);
 900                         pctx.ino2 = dir_array[i];
 901
 902                         if (fix_problem(ctx, PR_5_FREE_DIR_COUNT_GROUP,
 903                                         &pctx)) {
 904                                 ext2fs_bg_used_dirs_count_set(fs, i, dir_array[i]);
 905                                 ext2fs_mark_super_dirty(fs);
 906                         } else
 907                                 ext2fs_unmark_valid(fs);
 908                 }
 909         }
 910         if (free_inodes != fs->super->s_free_inodes_count) {
 911                 pctx.group = -1;
 912                 pctx.ino = fs->super->s_free_inodes_count;
 913                 pctx.ino2 = free_inodes;
 914
 915                 if (fix_problem(ctx, PR_5_FREE_INODE_COUNT, &pctx)) {
 916                         fs->super->s_free_inodes_count = free_inodes;
 917                         ext2fs_mark_super_dirty(fs);
 918                 }
 919         }
 920 errout:
 921         ext2fs_free_mem(&free_array);
 922         ext2fs_free_mem(&dir_array);
 923 }
 924
 925 static void check_inode_end(e2fsck_t ctx)
 926 {
 927         ext2_filsys fs = ctx->fs;
 928         ext2_ino_t      end, save_inodes_count, i;
 929         struct problem_context  pctx;
 930
 931         clear_problem_context(&pctx);
 932
 933         end = EXT2_INODES_PER_GROUP(fs->super) * fs->group_desc_count;
 934         pctx.errcode = ext2fs_fudge_inode_bitmap_end(fs->inode_map, end,
 935                                                      &save_inodes_count);
 936         if (pctx.errcode) {
 937                 pctx.num = 1;
 938                 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
 939                 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
 940                 return;
 941         }
 942         if (save_inodes_count == end)
 943                 return;
 944
 945         /* protect loop from wrap-around if end is maxed */
 946         for (i = save_inodes_count + 1; i <= end && i > save_inodes_count; i++) {
 947                 if (!ext2fs_test_inode_bitmap(fs->inode_map, i)) {
 948                         if (fix_problem(ctx, PR_5_INODE_BMAP_PADDING, &pctx)) {
 949                                 for (; i <= end; i++)
 950                                         ext2fs_mark_inode_bitmap(fs->inode_map,
 951                                                                  i);
 952                                 ext2fs_mark_ib_dirty(fs);
 953                         } else
 954                                 ext2fs_unmark_valid(fs);
 955                         break;
 956                 }
 957         }
 958
 959         pctx.errcode = ext2fs_fudge_inode_bitmap_end(fs->inode_map,
 960                                                      save_inodes_count, 0);
 961         if (pctx.errcode) {
 962                 pctx.num = 2;
 963                 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
 964                 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
 965                 return;
 966         }
 967 }
 968
 969 static void check_block_end(e2fsck_t ctx)
 970 {
 971         ext2_filsys fs = ctx->fs;
 972         blk64_t end, save_blocks_count, i;
 973         struct problem_context  pctx;
 974
 975         clear_problem_context(&pctx);
 976
 977         end = ext2fs_get_block_bitmap_start2(fs->block_map) +
 978                 ((blk64_t)EXT2_CLUSTERS_PER_GROUP(fs->super) * fs->group_desc_count) - 1;
 979         pctx.errcode = ext2fs_fudge_block_bitmap_end2(fs->block_map, end,
 980                                                      &save_blocks_count);
 981         if (pctx.errcode) {
 982                 pctx.num = 3;
 983                 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
 984                 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
 985                 return;
 986         }
 987         if (save_blocks_count == end)
 988                 return;
 989
 990         /* Protect loop from wrap-around if end is maxed */
 991         for (i = save_blocks_count + 1; i <= end && i > save_blocks_count; i++) {
 992                 if (!ext2fs_test_block_bitmap2(fs->block_map,
 993                                                EXT2FS_C2B(fs, i))) {
 994                         if (fix_problem(ctx, PR_5_BLOCK_BMAP_PADDING, &pctx)) {
 995                                 for (; i <= end; i++)
 996                                         ext2fs_mark_block_bitmap2(fs->block_map,
 997                                                         EXT2FS_C2B(fs, i));
 998                                 ext2fs_mark_bb_dirty(fs);
 999                         } else
1000                                 ext2fs_unmark_valid(fs);
1001                         break;
1002                 }
1003         }
1004
1005         pctx.errcode = ext2fs_fudge_block_bitmap_end2(fs->block_map,
1006                                                      save_blocks_count, 0);
1007         if (pctx.errcode) {
1008                 pctx.num = 4;
1009                 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
1010                 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
1011                 return;
1012         }
1013 }
1014
1015
1016