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