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