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 "e2fsck.h"
  14 #include "problem.h"
  15
  16 static void check_block_bitmaps(e2fsck_t ctx);
  17 static void check_inode_bitmaps(e2fsck_t ctx);
  18 static void check_inode_end(e2fsck_t ctx);
  19 static void check_block_end(e2fsck_t ctx);
  20
  21 void e2fsck_pass5(e2fsck_t ctx)
  22 {
  23 #ifdef RESOURCE_TRACK
  24         struct resource_track   rtrack;
  25 #endif
  26         struct problem_context  pctx;
  27
  28 #ifdef MTRACE
  29         mtrace_print("Pass 5");
  30 #endif
  31
  32 #ifdef RESOURCE_TRACK
  33         init_resource_track(&rtrack);
  34 #endif
  35
  36         clear_problem_context(&pctx);
  37
  38         if (!(ctx->options & E2F_OPT_PREEN))
  39                 fix_problem(ctx, PR_5_PASS_HEADER, &pctx);
  40
  41         if (ctx->progress)
  42                 if ((ctx->progress)(ctx, 5, 0, ctx->fs->group_desc_count*2))
  43                         return;
  44
  45         e2fsck_read_bitmaps(ctx);
  46
  47         check_block_bitmaps(ctx);
  48         if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
  49                 return;
  50         check_inode_bitmaps(ctx);
  51         if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
  52                 return;
  53         check_inode_end(ctx);
  54         if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
  55                 return;
  56         check_block_end(ctx);
  57         if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
  58                 return;
  59
  60         ext2fs_free_inode_bitmap(ctx->inode_used_map);
  61         ctx->inode_used_map = 0;
  62         ext2fs_free_inode_bitmap(ctx->inode_dir_map);
  63         ctx->inode_dir_map = 0;
  64         ext2fs_free_block_bitmap(ctx->block_found_map);
  65         ctx->block_found_map = 0;
  66
  67 #ifdef RESOURCE_TRACK
  68         if (ctx->options & E2F_OPT_TIME2) {
  69                 e2fsck_clear_progbar(ctx);
  70                 print_resource_track(_("Pass 5"), &rtrack);
  71         }
  72 #endif
  73 }
  74
  75 #define NO_BLK ((blk_t) -1)
  76
  77 static void print_bitmap_problem(e2fsck_t ctx, int problem,
  78                             struct problem_context *pctx)
  79 {
  80         switch (problem) {
  81         case PR_5_BLOCK_UNUSED:
  82                 if (pctx->blk == pctx->blk2)
  83                         pctx->blk2 = 0;
  84                 else
  85                         problem = PR_5_BLOCK_RANGE_UNUSED;
  86                 break;
  87         case PR_5_BLOCK_USED:
  88                 if (pctx->blk == pctx->blk2)
  89                         pctx->blk2 = 0;
  90                 else
  91                         problem = PR_5_BLOCK_RANGE_USED;
  92                 break;
  93         case PR_5_INODE_UNUSED:
  94                 if (pctx->ino == pctx->ino2)
  95                         pctx->ino2 = 0;
  96                 else
  97                         problem = PR_5_INODE_RANGE_UNUSED;
  98                 break;
  99         case PR_5_INODE_USED:
 100                 if (pctx->ino == pctx->ino2)
 101                         pctx->ino2 = 0;
 102                 else
 103                         problem = PR_5_INODE_RANGE_USED;
 104                 break;
 105         }
 106         fix_problem(ctx, problem, pctx);
 107         pctx->blk = pctx->blk2 = NO_BLK;
 108         pctx->ino = pctx->ino2 = 0;
 109 }
 110
 111 static void check_block_bitmaps(e2fsck_t ctx)
 112 {
 113         ext2_filsys fs = ctx->fs;
 114         blk_t   i;
 115         int     *free_array;
 116         int     group = 0;
 117         int     blocks = 0;
 118         int     free_blocks = 0;
 119         int     group_free = 0;
 120         int     actual, bitmap;
 121         struct problem_context  pctx;
 122         int     problem, save_problem, fixit, had_problem;
 123         errcode_t       retval;
 124
 125         clear_problem_context(&pctx);
 126         free_array = (int *) e2fsck_allocate_memory(ctx,
 127             fs->group_desc_count * sizeof(int), "free block count array");
 128
 129         if ((fs->super->s_first_data_block <
 130              ext2fs_get_block_bitmap_start(ctx->block_found_map)) ||
 131             (fs->super->s_blocks_count-1 >
 132              ext2fs_get_block_bitmap_end(ctx->block_found_map))) {
 133                 pctx.num = 1;
 134                 pctx.blk = fs->super->s_first_data_block;
 135                 pctx.blk2 = fs->super->s_blocks_count -1;
 136                 pctx.ino = ext2fs_get_block_bitmap_start(ctx->block_found_map);
 137                 pctx.ino2 = ext2fs_get_block_bitmap_end(ctx->block_found_map);
 138                 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
 139
 140                 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
 141                 return;
 142         }
 143
 144         if ((fs->super->s_first_data_block <
 145              ext2fs_get_block_bitmap_start(fs->block_map)) ||
 146             (fs->super->s_blocks_count-1 >
 147              ext2fs_get_block_bitmap_end(fs->block_map))) {
 148                 pctx.num = 2;
 149                 pctx.blk = fs->super->s_first_data_block;
 150                 pctx.blk2 = fs->super->s_blocks_count -1;
 151                 pctx.ino = ext2fs_get_block_bitmap_start(fs->block_map);
 152                 pctx.ino2 = ext2fs_get_block_bitmap_end(fs->block_map);
 153                 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
 154
 155                 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
 156                 return;
 157         }
 158
 159 redo_counts:
 160         had_problem = 0;
 161         save_problem = 0;
 162         pctx.blk = pctx.blk2 = NO_BLK;
 163         for (i = fs->super->s_first_data_block;
 164              i < fs->super->s_blocks_count;
 165              i++) {
 166                 actual = ext2fs_fast_test_block_bitmap(ctx->block_found_map, i);
 167                 bitmap = ext2fs_fast_test_block_bitmap(fs->block_map, i);
 168
 169                 if (actual == bitmap)
 170                         goto do_counts;
 171
 172                 if (!actual && bitmap) {
 173                         /*
 174                          * Block not used, but marked in use in the bitmap.
 175                          */
 176                         problem = PR_5_BLOCK_UNUSED;
 177                 } else {
 178                         /*
 179                          * Block used, but not marked in use in the bitmap.
 180                          */
 181                         problem = PR_5_BLOCK_USED;
 182                 }
 183                 if (pctx.blk == NO_BLK) {
 184                         pctx.blk = pctx.blk2 = i;
 185                         save_problem = problem;
 186                 } else {
 187                         if ((problem == save_problem) &&
 188                             (pctx.blk2 == i-1))
 189                                 pctx.blk2++;
 190                         else {
 191                                 print_bitmap_problem(ctx, save_problem, &pctx);
 192                                 pctx.blk = pctx.blk2 = i;
 193                                 save_problem = problem;
 194                         }
 195                 }
 196                 ctx->flags |= E2F_FLAG_PROG_SUPPRESS;
 197                 had_problem++;
 198
 199         do_counts:
 200                 if (!bitmap) {
 201                         group_free++;
 202                         free_blocks++;
 203                 }
 204                 blocks ++;
 205                 if ((blocks == fs->super->s_blocks_per_group) ||
 206                     (i == fs->super->s_blocks_count-1)) {
 207                         free_array[group] = group_free;
 208                         group ++;
 209                         blocks = 0;
 210                         group_free = 0;
 211                         if (ctx->progress)
 212                                 if ((ctx->progress)(ctx, 5, group,
 213                                                     fs->group_desc_count*2))
 214                                         return;
 215                 }
 216         }
 217         if (pctx.blk != NO_BLK)
 218                 print_bitmap_problem(ctx, save_problem, &pctx);
 219         if (had_problem)
 220                 fixit = end_problem_latch(ctx, PR_LATCH_BBITMAP);
 221         else
 222                 fixit = -1;
 223         ctx->flags &= ~E2F_FLAG_PROG_SUPPRESS;
 224
 225         if (fixit == 1) {
 226                 ext2fs_free_block_bitmap(fs->block_map);
 227                 retval = ext2fs_copy_bitmap(ctx->block_found_map,
 228                                                   &fs->block_map);
 229                 if (retval) {
 230                         clear_problem_context(&pctx);
 231                         fix_problem(ctx, PR_5_COPY_BBITMAP_ERROR, &pctx);
 232                         ctx->flags |= E2F_FLAG_ABORT;
 233                         return;
 234                 }
 235                 ext2fs_set_bitmap_padding(fs->block_map);
 236                 ext2fs_mark_bb_dirty(fs);
 237
 238                 /* Redo the counts */
 239                 blocks = 0; free_blocks = 0; group_free = 0; group = 0;
 240                 memset(free_array, 0, fs->group_desc_count * sizeof(int));
 241                 goto redo_counts;
 242         } else if (fixit == 0)
 243                 ext2fs_unmark_valid(fs);
 244
 245         for (i = 0; i < fs->group_desc_count; i++) {
 246                 if (free_array[i] != fs->group_desc[i].bg_free_blocks_count) {
 247                         pctx.group = i;
 248                         pctx.blk = fs->group_desc[i].bg_free_blocks_count;
 249                         pctx.blk2 = free_array[i];
 250
 251                         if (fix_problem(ctx, PR_5_FREE_BLOCK_COUNT_GROUP,
 252                                         &pctx)) {
 253                                 fs->group_desc[i].bg_free_blocks_count =
 254                                         free_array[i];
 255                                 ext2fs_mark_super_dirty(fs);
 256                         } else
 257                                 ext2fs_unmark_valid(fs);
 258                 }
 259         }
 260         if (free_blocks != fs->super->s_free_blocks_count) {
 261                 pctx.group = 0;
 262                 pctx.blk = fs->super->s_free_blocks_count;
 263                 pctx.blk2 = free_blocks;
 264
 265                 if (fix_problem(ctx, PR_5_FREE_BLOCK_COUNT, &pctx)) {
 266                         fs->super->s_free_blocks_count = free_blocks;
 267                         ext2fs_mark_super_dirty(fs);
 268                 } else
 269                         ext2fs_unmark_valid(fs);
 270         }
 271         ext2fs_free_mem((void **) &free_array);
 272 }
 273
 274 static void check_inode_bitmaps(e2fsck_t ctx)
 275 {
 276         ext2_filsys fs = ctx->fs;
 277         ext2_ino_t      i;
 278         int     free_inodes = 0;
 279         int     group_free = 0;
 280         int     dirs_count = 0;
 281         int     group = 0;
 282         int     inodes = 0;
 283         int     *free_array;
 284         int     *dir_array;
 285         int     actual, bitmap;
 286         errcode_t       retval;
 287         struct problem_context  pctx;
 288         int     problem, save_problem, fixit, had_problem;
 289
 290         clear_problem_context(&pctx);
 291         free_array = (int *) e2fsck_allocate_memory(ctx,
 292             fs->group_desc_count * sizeof(int), "free inode count array");
 293
 294         dir_array = (int *) e2fsck_allocate_memory(ctx,
 295            fs->group_desc_count * sizeof(int), "directory count array");
 296
 297         if ((1 < ext2fs_get_inode_bitmap_start(ctx->inode_used_map)) ||
 298             (fs->super->s_inodes_count >
 299              ext2fs_get_inode_bitmap_end(ctx->inode_used_map))) {
 300                 pctx.num = 3;
 301                 pctx.blk = 1;
 302                 pctx.blk2 = fs->super->s_inodes_count;
 303                 pctx.ino = ext2fs_get_inode_bitmap_start(ctx->inode_used_map);
 304                 pctx.ino2 = ext2fs_get_inode_bitmap_end(ctx->inode_used_map);
 305                 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
 306
 307                 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
 308                 return;
 309         }
 310         if ((1 < ext2fs_get_inode_bitmap_start(fs->inode_map)) ||
 311             (fs->super->s_inodes_count >
 312              ext2fs_get_inode_bitmap_end(fs->inode_map))) {
 313                 pctx.num = 4;
 314                 pctx.blk = 1;
 315                 pctx.blk2 = fs->super->s_inodes_count;
 316                 pctx.ino = ext2fs_get_inode_bitmap_start(fs->inode_map);
 317                 pctx.ino2 = ext2fs_get_inode_bitmap_end(fs->inode_map);
 318                 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
 319
 320                 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
 321                 return;
 322         }
 323
 324 redo_counts:
 325         had_problem = 0;
 326         save_problem = 0;
 327         pctx.ino = pctx.ino2 = 0;
 328         for (i = 1; i <= fs->super->s_inodes_count; i++) {
 329                 actual = ext2fs_fast_test_inode_bitmap(ctx->inode_used_map, i);
 330                 bitmap = ext2fs_fast_test_inode_bitmap(fs->inode_map, i);
 331
 332                 if (actual == bitmap)
 333                         goto do_counts;
 334
 335                 if (!actual && bitmap) {
 336                         /*
 337                          * Inode wasn't used, but marked in bitmap
 338                          */
 339                         problem = PR_5_INODE_UNUSED;
 340                 } else /* if (actual && !bitmap) */ {
 341                         /*
 342                          * Inode used, but not in bitmap
 343                          */
 344                         problem = PR_5_INODE_USED;
 345                 }
 346                 if (pctx.ino == 0) {
 347                         pctx.ino = pctx.ino2 = i;
 348                         save_problem = problem;
 349                 } else {
 350                         if ((problem == save_problem) &&
 351                             (pctx.ino2 == i-1))
 352                                 pctx.ino2++;
 353                         else {
 354                                 print_bitmap_problem(ctx, save_problem, &pctx);
 355                                 pctx.ino = pctx.ino2 = i;
 356                                 save_problem = problem;
 357                         }
 358                 }
 359                 ctx->flags |= E2F_FLAG_PROG_SUPPRESS;
 360                 had_problem++;
 361
 362 do_counts:
 363                 if (!bitmap) {
 364                         group_free++;
 365                         free_inodes++;
 366                 } else {
 367                         if (ext2fs_test_inode_bitmap(ctx->inode_dir_map, i))
 368                                 dirs_count++;
 369                 }
 370                 inodes++;
 371                 if ((inodes == fs->super->s_inodes_per_group) ||
 372                     (i == fs->super->s_inodes_count)) {
 373                         free_array[group] = group_free;
 374                         dir_array[group] = dirs_count;
 375                         group ++;
 376                         inodes = 0;
 377                         group_free = 0;
 378                         dirs_count = 0;
 379                         if (ctx->progress)
 380                                 if ((ctx->progress)(ctx, 5,
 381                                             group + fs->group_desc_count,
 382                                             fs->group_desc_count*2))
 383                                         return;
 384                 }
 385         }
 386         if (pctx.ino)
 387                 print_bitmap_problem(ctx, save_problem, &pctx);
 388
 389         if (had_problem)
 390                 fixit = end_problem_latch(ctx, PR_LATCH_IBITMAP);
 391         else
 392                 fixit = -1;
 393         ctx->flags &= ~E2F_FLAG_PROG_SUPPRESS;
 394
 395         if (fixit == 1) {
 396                 ext2fs_free_inode_bitmap(fs->inode_map);
 397                 retval = ext2fs_copy_bitmap(ctx->inode_used_map,
 398                                                   &fs->inode_map);
 399                 if (retval) {
 400                         clear_problem_context(&pctx);
 401                         fix_problem(ctx, PR_5_COPY_IBITMAP_ERROR, &pctx);
 402                         ctx->flags |= E2F_FLAG_ABORT;
 403                         return;
 404                 }
 405                 ext2fs_set_bitmap_padding(fs->inode_map);
 406                 ext2fs_mark_ib_dirty(fs);
 407
 408                 /* redo counts */
 409                 inodes = 0; free_inodes = 0; group_free = 0;
 410                 dirs_count = 0; group = 0;
 411                 memset(free_array, 0, fs->group_desc_count * sizeof(int));
 412                 memset(dir_array, 0, fs->group_desc_count * sizeof(int));
 413                 goto redo_counts;
 414         } else if (fixit == 0)
 415                 ext2fs_unmark_valid(fs);
 416
 417         for (i = 0; i < fs->group_desc_count; i++) {
 418                 if (free_array[i] != fs->group_desc[i].bg_free_inodes_count) {
 419                         pctx.group = i;
 420                         pctx.ino = fs->group_desc[i].bg_free_inodes_count;
 421                         pctx.ino2 = free_array[i];
 422                         if (fix_problem(ctx, PR_5_FREE_INODE_COUNT_GROUP,
 423                                         &pctx)) {
 424                                 fs->group_desc[i].bg_free_inodes_count =
 425                                         free_array[i];
 426                                 ext2fs_mark_super_dirty(fs);
 427                         } else
 428                                 ext2fs_unmark_valid(fs);
 429                 }
 430                 if (dir_array[i] != fs->group_desc[i].bg_used_dirs_count) {
 431                         pctx.group = i;
 432                         pctx.ino = fs->group_desc[i].bg_used_dirs_count;
 433                         pctx.ino2 = dir_array[i];
 434
 435                         if (fix_problem(ctx, PR_5_FREE_DIR_COUNT_GROUP,
 436                                         &pctx)) {
 437                                 fs->group_desc[i].bg_used_dirs_count =
 438                                         dir_array[i];
 439                                 ext2fs_mark_super_dirty(fs);
 440                         } else
 441                                 ext2fs_unmark_valid(fs);
 442                 }
 443         }
 444         if (free_inodes != fs->super->s_free_inodes_count) {
 445                 pctx.group = -1;
 446                 pctx.ino = fs->super->s_free_inodes_count;
 447                 pctx.ino2 = free_inodes;
 448
 449                 if (fix_problem(ctx, PR_5_FREE_INODE_COUNT, &pctx)) {
 450                         fs->super->s_free_inodes_count = free_inodes;
 451                         ext2fs_mark_super_dirty(fs);
 452                 } else
 453                         ext2fs_unmark_valid(fs);
 454         }
 455         ext2fs_free_mem((void **) &free_array);
 456         ext2fs_free_mem((void **) &dir_array);
 457 }
 458
 459 static void check_inode_end(e2fsck_t ctx)
 460 {
 461         ext2_filsys fs = ctx->fs;
 462         ext2_ino_t      end, save_inodes_count, i;
 463         struct problem_context  pctx;
 464
 465         clear_problem_context(&pctx);
 466
 467         end = EXT2_INODES_PER_GROUP(fs->super) * fs->group_desc_count;
 468         pctx.errcode = ext2fs_fudge_inode_bitmap_end(fs->inode_map, end,
 469                                                      &save_inodes_count);
 470         if (pctx.errcode) {
 471                 pctx.num = 1;
 472                 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
 473                 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
 474                 return;
 475         }
 476         if (save_inodes_count == end)
 477                 return;
 478
 479         for (i = save_inodes_count + 1; i <= end; i++) {
 480                 if (!ext2fs_test_inode_bitmap(fs->inode_map, i)) {
 481                         if (fix_problem(ctx, PR_5_INODE_BMAP_PADDING, &pctx)) {
 482                                 for (i = save_inodes_count + 1; i <= end; i++)
 483                                         ext2fs_mark_inode_bitmap(fs->inode_map,
 484                                                                  i);
 485                                 ext2fs_mark_ib_dirty(fs);
 486                         } else
 487                                 ext2fs_unmark_valid(fs);
 488                         break;
 489                 }
 490         }
 491
 492         pctx.errcode = ext2fs_fudge_inode_bitmap_end(fs->inode_map,
 493                                                      save_inodes_count, 0);
 494         if (pctx.errcode) {
 495                 pctx.num = 2;
 496                 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
 497                 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
 498                 return;
 499         }
 500 }
 501
 502 static void check_block_end(e2fsck_t ctx)
 503 {
 504         ext2_filsys fs = ctx->fs;
 505         blk_t   end, save_blocks_count, i;
 506         struct problem_context  pctx;
 507
 508         clear_problem_context(&pctx);
 509
 510         end = fs->block_map->start +
 511                 (EXT2_BLOCKS_PER_GROUP(fs->super) * fs->group_desc_count) - 1;
 512         pctx.errcode = ext2fs_fudge_block_bitmap_end(fs->block_map, end,
 513                                                      &save_blocks_count);
 514         if (pctx.errcode) {
 515                 pctx.num = 3;
 516                 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
 517                 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
 518                 return;
 519         }
 520         if (save_blocks_count == end)
 521                 return;
 522
 523         for (i = save_blocks_count + 1; i <= end; i++) {
 524                 if (!ext2fs_test_block_bitmap(fs->block_map, i)) {
 525                         if (fix_problem(ctx, PR_5_BLOCK_BMAP_PADDING, &pctx)) {
 526                                 for (i = save_blocks_count + 1; i <= end; i++)
 527                                         ext2fs_mark_block_bitmap(fs->block_map,
 528                                                                  i);
 529                                 ext2fs_mark_bb_dirty(fs);
 530                         } else
 531                                 ext2fs_unmark_valid(fs);
 532                         break;
 533                 }
 534         }
 535
 536         pctx.errcode = ext2fs_fudge_block_bitmap_end(fs->block_map,
 537                                                      save_blocks_count, 0);
 538         if (pctx.errcode) {
 539                 pctx.num = 4;
 540                 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
 541                 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
 542                 return;
 543         }
 544 }
 545
 546
 547