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 16static void check_block_bitmaps(e2fsck_t ctx); 17static void check_inode_bitmaps(e2fsck_t ctx); 18static void check_inode_end(e2fsck_t ctx); 19static void check_block_end(e2fsck_t ctx); 20 21void 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 init_resource_track(&rtrack, ctx->fs->io); 33 clear_problem_context(&pctx); 34 35 if (!(ctx->options & E2F_OPT_PREEN)) 36 fix_problem(ctx, PR_5_PASS_HEADER, &pctx); 37 38 if (ctx->progress) 39 if ((ctx->progress)(ctx, 5, 0, ctx->fs->group_desc_count*2)) 40 return; 41 42 e2fsck_read_bitmaps(ctx); 43 44 check_block_bitmaps(ctx); 45 if (ctx->flags & E2F_FLAG_SIGNAL_MASK) 46 return; 47 check_inode_bitmaps(ctx); 48 if (ctx->flags & E2F_FLAG_SIGNAL_MASK) 49 return; 50 check_inode_end(ctx); 51 if (ctx->flags & E2F_FLAG_SIGNAL_MASK) 52 return; 53 check_block_end(ctx); 54 if (ctx->flags & E2F_FLAG_SIGNAL_MASK) 55 return; 56 57 ext2fs_free_inode_bitmap(ctx->inode_used_map); 58 ctx->inode_used_map = 0; 59 ext2fs_free_inode_bitmap(ctx->inode_dir_map); 60 ctx->inode_dir_map = 0; 61 ext2fs_free_block_bitmap(ctx->block_found_map); 62 ctx->block_found_map = 0; 63 64 print_resource_track(ctx, _("Pass 5"), &rtrack, ctx->fs->io); 65} 66 67#define NO_BLK ((blk_t) -1) 68 69static void print_bitmap_problem(e2fsck_t ctx, int problem, 70 struct problem_context *pctx) 71{ 72 switch (problem) { 73 case PR_5_BLOCK_UNUSED: 74 if (pctx->blk == pctx->blk2) 75 pctx->blk2 = 0; 76 else 77 problem = PR_5_BLOCK_RANGE_UNUSED; 78 break; 79 case PR_5_BLOCK_USED: 80 if (pctx->blk == pctx->blk2) 81 pctx->blk2 = 0; 82 else 83 problem = PR_5_BLOCK_RANGE_USED; 84 break; 85 case PR_5_INODE_UNUSED: 86 if (pctx->ino == pctx->ino2) 87 pctx->ino2 = 0; 88 else 89 problem = PR_5_INODE_RANGE_UNUSED; 90 break; 91 case PR_5_INODE_USED: 92 if (pctx->ino == pctx->ino2) 93 pctx->ino2 = 0; 94 else 95 problem = PR_5_INODE_RANGE_USED; 96 break; 97 } 98 fix_problem(ctx, problem, pctx); 99 pctx->blk = pctx->blk2 = NO_BLK; 100 pctx->ino = pctx->ino2 = 0; 101} 102 103static void check_block_bitmaps(e2fsck_t ctx) 104{ 105 ext2_filsys fs = ctx->fs; 106 blk_t i; 107 int *free_array; 108 int group = 0; 109 blk_t blocks = 0; 110 blk_t free_blocks = 0; 111 int group_free = 0; 112 int actual, bitmap; 113 struct problem_context pctx; 114 int problem, save_problem, fixit, had_problem; 115 errcode_t retval; 116 int csum_flag; 117 int skip_group = 0; 118 119 clear_problem_context(&pctx); 120 free_array = (int *) e2fsck_allocate_memory(ctx, 121 fs->group_desc_count * sizeof(int), "free block count array"); 122 123 if ((fs->super->s_first_data_block < 124 ext2fs_get_block_bitmap_start(ctx->block_found_map)) || 125 (fs->super->s_blocks_count-1 > 126 ext2fs_get_block_bitmap_end(ctx->block_found_map))) { 127 pctx.num = 1; 128 pctx.blk = fs->super->s_first_data_block; 129 pctx.blk2 = fs->super->s_blocks_count -1; 130 pctx.ino = ext2fs_get_block_bitmap_start(ctx->block_found_map); 131 pctx.ino2 = ext2fs_get_block_bitmap_end(ctx->block_found_map); 132 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx); 133 134 ctx->flags |= E2F_FLAG_ABORT; /* fatal */ 135 goto errout; 136 } 137 138 if ((fs->super->s_first_data_block < 139 ext2fs_get_block_bitmap_start(fs->block_map)) || 140 (fs->super->s_blocks_count-1 > 141 ext2fs_get_block_bitmap_end(fs->block_map))) { 142 pctx.num = 2; 143 pctx.blk = fs->super->s_first_data_block; 144 pctx.blk2 = fs->super->s_blocks_count -1; 145 pctx.ino = ext2fs_get_block_bitmap_start(fs->block_map); 146 pctx.ino2 = ext2fs_get_block_bitmap_end(fs->block_map); 147 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx); 148 149 ctx->flags |= E2F_FLAG_ABORT; /* fatal */ 150 goto errout; 151 } 152 153 csum_flag = EXT2_HAS_RO_COMPAT_FEATURE(fs->super, 154 EXT4_FEATURE_RO_COMPAT_GDT_CSUM); 155redo_counts: 156 had_problem = 0; 157 save_problem = 0; 158 pctx.blk = pctx.blk2 = NO_BLK; 159 if (csum_flag && 160 (fs->group_desc[group].bg_flags & EXT2_BG_BLOCK_UNINIT)) 161 skip_group++; 162 for (i = fs->super->s_first_data_block; 163 i < fs->super->s_blocks_count; 164 i++) { 165 actual = ext2fs_fast_test_block_bitmap(ctx->block_found_map, i); 166 167 if (skip_group) { 168 blk_t super_blk, old_desc_blk, new_desc_blk; 169 int old_desc_blocks; 170 171 ext2fs_super_and_bgd_loc(fs, group, &super_blk, 172 &old_desc_blk, &new_desc_blk, 0); 173 174 if (fs->super->s_feature_incompat & 175 EXT2_FEATURE_INCOMPAT_META_BG) 176 old_desc_blocks = fs->super->s_first_meta_bg; 177 else 178 old_desc_blocks = fs->desc_blocks + 179 fs->super->s_reserved_gdt_blocks; 180 181 bitmap = 0; 182 if (i == super_blk) 183 bitmap = 1; 184 if (old_desc_blk && old_desc_blocks && 185 (i >= old_desc_blk) && 186 (i < old_desc_blk + old_desc_blocks)) 187 bitmap = 1; 188 if (new_desc_blk && 189 (i == new_desc_blk)) 190 bitmap = 1; 191 if (i == fs->group_desc[group].bg_block_bitmap) 192 bitmap = 1; 193 else if (i == fs->group_desc[group].bg_inode_bitmap) 194 bitmap = 1; 195 else if (i >= fs->group_desc[group].bg_inode_table && 196 (i < fs->group_desc[group].bg_inode_table 197 + fs->inode_blocks_per_group)) 198 bitmap = 1; 199 actual = (actual != 0); 200 } else 201 bitmap = ext2fs_fast_test_block_bitmap(fs->block_map, i); 202 203 if (actual == bitmap) 204 goto do_counts; 205 206 if (!actual && bitmap) { 207 /* 208 * Block not used, but marked in use in the bitmap. 209 */ 210 problem = PR_5_BLOCK_UNUSED; 211 } else { 212 /* 213 * Block used, but not marked in use in the bitmap. 214 */ 215 problem = PR_5_BLOCK_USED; 216 217 if (skip_group) { 218 struct problem_context pctx2; 219 pctx2.blk = i; 220 pctx2.group = group; 221 if (fix_problem(ctx, PR_5_BLOCK_UNINIT,&pctx2)){ 222 fs->group_desc[group].bg_flags &= 223 ~EXT2_BG_BLOCK_UNINIT; 224 skip_group = 0; 225 } 226 } 227 } 228 if (pctx.blk == NO_BLK) { 229 pctx.blk = pctx.blk2 = i; 230 save_problem = problem; 231 } else { 232 if ((problem == save_problem) && 233 (pctx.blk2 == i-1)) 234 pctx.blk2++; 235 else { 236 print_bitmap_problem(ctx, save_problem, &pctx); 237 pctx.blk = pctx.blk2 = i; 238 save_problem = problem; 239 } 240 } 241 ctx->flags |= E2F_FLAG_PROG_SUPPRESS; 242 had_problem++; 243 244 do_counts: 245 if (!bitmap && (!skip_group || csum_flag)) { 246 group_free++; 247 free_blocks++; 248 } 249 blocks ++; 250 if ((blocks == fs->super->s_blocks_per_group) || 251 (i == fs->super->s_blocks_count-1)) { 252 free_array[group] = group_free; 253 group ++; 254 blocks = 0; 255 group_free = 0; 256 skip_group = 0; 257 if (ctx->progress) 258 if ((ctx->progress)(ctx, 5, group, 259 fs->group_desc_count*2)) 260 goto errout; 261 if (csum_flag && 262 (i != fs->super->s_blocks_count-1) && 263 (fs->group_desc[group].bg_flags & 264 EXT2_BG_BLOCK_UNINIT)) 265 skip_group++; 266 } 267 } 268 if (pctx.blk != NO_BLK) 269 print_bitmap_problem(ctx, save_problem, &pctx); 270 if (had_problem) 271 fixit = end_problem_latch(ctx, PR_LATCH_BBITMAP); 272 else 273 fixit = -1; 274 ctx->flags &= ~E2F_FLAG_PROG_SUPPRESS; 275 276 if (fixit == 1) { 277 ext2fs_free_block_bitmap(fs->block_map); 278 retval = ext2fs_copy_bitmap(ctx->block_found_map, 279 &fs->block_map); 280 if (retval) { 281 clear_problem_context(&pctx); 282 fix_problem(ctx, PR_5_COPY_BBITMAP_ERROR, &pctx); 283 ctx->flags |= E2F_FLAG_ABORT; 284 goto errout; 285 } 286 ext2fs_set_bitmap_padding(fs->block_map); 287 ext2fs_mark_bb_dirty(fs); 288 289 /* Redo the counts */ 290 blocks = 0; free_blocks = 0; group_free = 0; group = 0; 291 memset(free_array, 0, fs->group_desc_count * sizeof(int)); 292 goto redo_counts; 293 } else if (fixit == 0) 294 ext2fs_unmark_valid(fs); 295 296 for (i = 0; i < fs->group_desc_count; i++) { 297 if (free_array[i] != fs->group_desc[i].bg_free_blocks_count) { 298 pctx.group = i; 299 pctx.blk = fs->group_desc[i].bg_free_blocks_count; 300 pctx.blk2 = free_array[i]; 301 302 if (fix_problem(ctx, PR_5_FREE_BLOCK_COUNT_GROUP, 303 &pctx)) { 304 fs->group_desc[i].bg_free_blocks_count = 305 free_array[i]; 306 ext2fs_mark_super_dirty(fs); 307 } else 308 ext2fs_unmark_valid(fs); 309 } 310 } 311 if (free_blocks != fs->super->s_free_blocks_count) { 312 pctx.group = 0; 313 pctx.blk = fs->super->s_free_blocks_count; 314 pctx.blk2 = free_blocks; 315 316 if (fix_problem(ctx, PR_5_FREE_BLOCK_COUNT, &pctx)) { 317 fs->super->s_free_blocks_count = free_blocks; 318 ext2fs_mark_super_dirty(fs); 319 } else 320 ext2fs_unmark_valid(fs); 321 } 322errout: 323 ext2fs_free_mem(&free_array); 324} 325 326static void check_inode_bitmaps(e2fsck_t ctx) 327{ 328 ext2_filsys fs = ctx->fs; 329 ext2_ino_t i; 330 unsigned int free_inodes = 0; 331 int group_free = 0; 332 int dirs_count = 0; 333 int group = 0; 334 unsigned int inodes = 0; 335 int *free_array; 336 int *dir_array; 337 int actual, bitmap; 338 errcode_t retval; 339 struct problem_context pctx; 340 int problem, save_problem, fixit, had_problem; 341 int csum_flag; 342 int skip_group = 0; 343 344 clear_problem_context(&pctx); 345 free_array = (int *) e2fsck_allocate_memory(ctx, 346 fs->group_desc_count * sizeof(int), "free inode count array"); 347 348 dir_array = (int *) e2fsck_allocate_memory(ctx, 349 fs->group_desc_count * sizeof(int), "directory count array"); 350 351 if ((1 < ext2fs_get_inode_bitmap_start(ctx->inode_used_map)) || 352 (fs->super->s_inodes_count > 353 ext2fs_get_inode_bitmap_end(ctx->inode_used_map))) { 354 pctx.num = 3; 355 pctx.blk = 1; 356 pctx.blk2 = fs->super->s_inodes_count; 357 pctx.ino = ext2fs_get_inode_bitmap_start(ctx->inode_used_map); 358 pctx.ino2 = ext2fs_get_inode_bitmap_end(ctx->inode_used_map); 359 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx); 360 361 ctx->flags |= E2F_FLAG_ABORT; /* fatal */ 362 goto errout; 363 } 364 if ((1 < ext2fs_get_inode_bitmap_start(fs->inode_map)) || 365 (fs->super->s_inodes_count > 366 ext2fs_get_inode_bitmap_end(fs->inode_map))) { 367 pctx.num = 4; 368 pctx.blk = 1; 369 pctx.blk2 = fs->super->s_inodes_count; 370 pctx.ino = ext2fs_get_inode_bitmap_start(fs->inode_map); 371 pctx.ino2 = ext2fs_get_inode_bitmap_end(fs->inode_map); 372 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx); 373 374 ctx->flags |= E2F_FLAG_ABORT; /* fatal */ 375 goto errout; 376 } 377 378 csum_flag = EXT2_HAS_RO_COMPAT_FEATURE(fs->super, 379 EXT4_FEATURE_RO_COMPAT_GDT_CSUM); 380redo_counts: 381 had_problem = 0; 382 save_problem = 0; 383 pctx.ino = pctx.ino2 = 0; 384 if (csum_flag && 385 (fs->group_desc[group].bg_flags & EXT2_BG_INODE_UNINIT)) 386 skip_group++; 387 388 /* Protect loop from wrap-around if inodes_count is maxed */ 389 for (i = 1; i <= fs->super->s_inodes_count && i > 0; i++) { 390 actual = ext2fs_fast_test_inode_bitmap(ctx->inode_used_map, i); 391 if (skip_group) 392 bitmap = 0; 393 else 394 bitmap = ext2fs_fast_test_inode_bitmap(fs->inode_map, i); 395 if (actual == bitmap) 396 goto do_counts; 397 398 if (!actual && bitmap) { 399 /* 400 * Inode wasn't used, but marked in bitmap 401 */ 402 problem = PR_5_INODE_UNUSED; 403 } else /* if (actual && !bitmap) */ { 404 /* 405 * Inode used, but not in bitmap 406 */ 407 problem = PR_5_INODE_USED; 408 409 /* We should never hit this, because it means that 410 * inodes were marked in use that weren't noticed 411 * in pass1 or pass 2. It is easier to fix the problem 412 * than to kill e2fsck and leave the user stuck. */ 413 if (skip_group) { 414 struct problem_context pctx2; 415 pctx2.blk = i; 416 pctx2.group = group; 417 if (fix_problem(ctx, PR_5_INODE_UNINIT,&pctx2)){ 418 fs->group_desc[group].bg_flags &= 419 ~EXT2_BG_INODE_UNINIT; 420 skip_group = 0; 421 } 422 } 423 } 424 if (pctx.ino == 0) { 425 pctx.ino = pctx.ino2 = i; 426 save_problem = problem; 427 } else { 428 if ((problem == save_problem) && 429 (pctx.ino2 == i-1)) 430 pctx.ino2++; 431 else { 432 print_bitmap_problem(ctx, save_problem, &pctx); 433 pctx.ino = pctx.ino2 = i; 434 save_problem = problem; 435 } 436 } 437 ctx->flags |= E2F_FLAG_PROG_SUPPRESS; 438 had_problem++; 439 440do_counts: 441 if (bitmap) { 442 if (ext2fs_test_inode_bitmap(ctx->inode_dir_map, i)) 443 dirs_count++; 444 } else if (!skip_group || csum_flag) { 445 group_free++; 446 free_inodes++; 447 } 448 inodes++; 449 if ((inodes == fs->super->s_inodes_per_group) || 450 (i == fs->super->s_inodes_count)) { 451 free_array[group] = group_free; 452 dir_array[group] = dirs_count; 453 group ++; 454 inodes = 0; 455 skip_group = 0; 456 group_free = 0; 457 dirs_count = 0; 458 if (ctx->progress) 459 if ((ctx->progress)(ctx, 5, 460 group + fs->group_desc_count, 461 fs->group_desc_count*2)) 462 goto errout; 463 if (csum_flag && 464 (i != fs->super->s_inodes_count) && 465 (fs->group_desc[group].bg_flags & 466 EXT2_BG_INODE_UNINIT)) 467 skip_group++; 468 } 469 } 470 if (pctx.ino) 471 print_bitmap_problem(ctx, save_problem, &pctx); 472 473 if (had_problem) 474 fixit = end_problem_latch(ctx, PR_LATCH_IBITMAP); 475 else 476 fixit = -1; 477 ctx->flags &= ~E2F_FLAG_PROG_SUPPRESS; 478 479 if (fixit == 1) { 480 ext2fs_free_inode_bitmap(fs->inode_map); 481 retval = ext2fs_copy_bitmap(ctx->inode_used_map, 482 &fs->inode_map); 483 if (retval) { 484 clear_problem_context(&pctx); 485 fix_problem(ctx, PR_5_COPY_IBITMAP_ERROR, &pctx); 486 ctx->flags |= E2F_FLAG_ABORT; 487 goto errout; 488 } 489 ext2fs_set_bitmap_padding(fs->inode_map); 490 ext2fs_mark_ib_dirty(fs); 491 492 /* redo counts */ 493 inodes = 0; free_inodes = 0; group_free = 0; 494 dirs_count = 0; group = 0; 495 memset(free_array, 0, fs->group_desc_count * sizeof(int)); 496 memset(dir_array, 0, fs->group_desc_count * sizeof(int)); 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] != fs->group_desc[i].bg_free_inodes_count) { 503 pctx.group = i; 504 pctx.ino = fs->group_desc[i].bg_free_inodes_count; 505 pctx.ino2 = free_array[i]; 506 if (fix_problem(ctx, PR_5_FREE_INODE_COUNT_GROUP, 507 &pctx)) { 508 fs->group_desc[i].bg_free_inodes_count = 509 free_array[i]; 510 ext2fs_mark_super_dirty(fs); 511 } else 512 ext2fs_unmark_valid(fs); 513 } 514 if (dir_array[i] != fs->group_desc[i].bg_used_dirs_count) { 515 pctx.group = i; 516 pctx.ino = fs->group_desc[i].bg_used_dirs_count; 517 pctx.ino2 = dir_array[i]; 518 519 if (fix_problem(ctx, PR_5_FREE_DIR_COUNT_GROUP, 520 &pctx)) { 521 fs->group_desc[i].bg_used_dirs_count = 522 dir_array[i]; 523 ext2fs_mark_super_dirty(fs); 524 } else 525 ext2fs_unmark_valid(fs); 526 } 527 } 528 if (free_inodes != fs->super->s_free_inodes_count) { 529 pctx.group = -1; 530 pctx.ino = fs->super->s_free_inodes_count; 531 pctx.ino2 = free_inodes; 532 533 if (fix_problem(ctx, PR_5_FREE_INODE_COUNT, &pctx)) { 534 fs->super->s_free_inodes_count = free_inodes; 535 ext2fs_mark_super_dirty(fs); 536 } else 537 ext2fs_unmark_valid(fs); 538 } 539errout: 540 ext2fs_free_mem(&free_array); 541 ext2fs_free_mem(&dir_array); 542} 543 544static void check_inode_end(e2fsck_t ctx) 545{ 546 ext2_filsys fs = ctx->fs; 547 ext2_ino_t end, save_inodes_count, i; 548 struct problem_context pctx; 549 550 clear_problem_context(&pctx); 551 552 end = EXT2_INODES_PER_GROUP(fs->super) * fs->group_desc_count; 553 pctx.errcode = ext2fs_fudge_inode_bitmap_end(fs->inode_map, end, 554 &save_inodes_count); 555 if (pctx.errcode) { 556 pctx.num = 1; 557 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx); 558 ctx->flags |= E2F_FLAG_ABORT; /* fatal */ 559 return; 560 } 561 if (save_inodes_count == end) 562 return; 563 564 /* protect loop from wrap-around if end is maxed */ 565 for (i = save_inodes_count + 1; i <= end && i > save_inodes_count; i++) { 566 if (!ext2fs_test_inode_bitmap(fs->inode_map, i)) { 567 if (fix_problem(ctx, PR_5_INODE_BMAP_PADDING, &pctx)) { 568 for (; i <= end; i++) 569 ext2fs_mark_inode_bitmap(fs->inode_map, 570 i); 571 ext2fs_mark_ib_dirty(fs); 572 } else 573 ext2fs_unmark_valid(fs); 574 break; 575 } 576 } 577 578 pctx.errcode = ext2fs_fudge_inode_bitmap_end(fs->inode_map, 579 save_inodes_count, 0); 580 if (pctx.errcode) { 581 pctx.num = 2; 582 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx); 583 ctx->flags |= E2F_FLAG_ABORT; /* fatal */ 584 return; 585 } 586} 587 588static void check_block_end(e2fsck_t ctx) 589{ 590 ext2_filsys fs = ctx->fs; 591 blk_t end, save_blocks_count, i; 592 struct problem_context pctx; 593 594 clear_problem_context(&pctx); 595 596 end = ext2fs_get_block_bitmap_start(fs->block_map) + 597 (EXT2_BLOCKS_PER_GROUP(fs->super) * fs->group_desc_count) - 1; 598 pctx.errcode = ext2fs_fudge_block_bitmap_end(fs->block_map, end, 599 &save_blocks_count); 600 if (pctx.errcode) { 601 pctx.num = 3; 602 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx); 603 ctx->flags |= E2F_FLAG_ABORT; /* fatal */ 604 return; 605 } 606 if (save_blocks_count == end) 607 return; 608 609 /* Protect loop from wrap-around if end is maxed */ 610 for (i = save_blocks_count + 1; i <= end && i > save_blocks_count; i++) { 611 if (!ext2fs_test_block_bitmap(fs->block_map, i)) { 612 if (fix_problem(ctx, PR_5_BLOCK_BMAP_PADDING, &pctx)) { 613 for (; i <= end; i++) 614 ext2fs_mark_block_bitmap(fs->block_map, 615 i); 616 ext2fs_mark_bb_dirty(fs); 617 } else 618 ext2fs_unmark_valid(fs); 619 break; 620 } 621 } 622 623 pctx.errcode = ext2fs_fudge_block_bitmap_end(fs->block_map, 624 save_blocks_count, 0); 625 if (pctx.errcode) { 626 pctx.num = 4; 627 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx); 628 ctx->flags |= E2F_FLAG_ABORT; /* fatal */ 629 return; 630 } 631} 632 633 634 635