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