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, super; 115 int *free_array; 116 int group = 0; 117 unsigned int blocks = 0; 118 unsigned 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 int lazy_bg = 0; 125 int skip_group = 0; 126 127 clear_problem_context(&pctx); 128 free_array = (int *) e2fsck_allocate_memory(ctx, 129 fs->group_desc_count * sizeof(int), "free block count array"); 130 131 if ((fs->super->s_first_data_block < 132 ext2fs_get_block_bitmap_start(ctx->block_found_map)) || 133 (fs->super->s_blocks_count-1 > 134 ext2fs_get_block_bitmap_end(ctx->block_found_map))) { 135 pctx.num = 1; 136 pctx.blk = fs->super->s_first_data_block; 137 pctx.blk2 = fs->super->s_blocks_count -1; 138 pctx.ino = ext2fs_get_block_bitmap_start(ctx->block_found_map); 139 pctx.ino2 = ext2fs_get_block_bitmap_end(ctx->block_found_map); 140 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx); 141 142 ctx->flags |= E2F_FLAG_ABORT; /* fatal */ 143 goto errout; 144 } 145 146 if ((fs->super->s_first_data_block < 147 ext2fs_get_block_bitmap_start(fs->block_map)) || 148 (fs->super->s_blocks_count-1 > 149 ext2fs_get_block_bitmap_end(fs->block_map))) { 150 pctx.num = 2; 151 pctx.blk = fs->super->s_first_data_block; 152 pctx.blk2 = fs->super->s_blocks_count -1; 153 pctx.ino = ext2fs_get_block_bitmap_start(fs->block_map); 154 pctx.ino2 = ext2fs_get_block_bitmap_end(fs->block_map); 155 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx); 156 157 ctx->flags |= E2F_FLAG_ABORT; /* fatal */ 158 goto errout; 159 } 160 161 if (EXT2_HAS_COMPAT_FEATURE(fs->super, EXT2_FEATURE_COMPAT_LAZY_BG)) 162 lazy_bg++; 163 164 redo_counts: 165 had_problem = 0; 166 save_problem = 0; 167 pctx.blk = pctx.blk2 = NO_BLK; 168 if (lazy_bg && (fs->group_desc[group].bg_flags & 169 EXT2_BG_BLOCK_UNINIT)) 170 skip_group++; 171 super = fs->super->s_first_data_block; 172 for (i = fs->super->s_first_data_block; 173 i < fs->super->s_blocks_count; 174 i++) { 175 actual = ext2fs_fast_test_block_bitmap(ctx->block_found_map, i); 176 177 if (skip_group) { 178 if ((i >= super) && 179 (i <= super + fs->desc_blocks) && 180 ext2fs_bg_has_super(fs, group)) 181 bitmap = 1; 182 else if (i == fs->group_desc[group].bg_block_bitmap) 183 bitmap = 1; 184 else if (i == fs->group_desc[group].bg_inode_bitmap) 185 bitmap = 1; 186 else if (i >= fs->group_desc[group].bg_inode_table && 187 (i < fs->group_desc[group].bg_inode_table 188 + fs->inode_blocks_per_group)) 189 bitmap = 1; 190 else 191 bitmap = 0; 192 actual = (actual != 0); 193 } else 194 bitmap = ext2fs_fast_test_block_bitmap(fs->block_map, i); 195 196 if (actual == bitmap) 197 goto do_counts; 198 199 if (!actual && bitmap) { 200 /* 201 * Block not used, but marked in use in the bitmap. 202 */ 203 problem = PR_5_BLOCK_UNUSED; 204 } else { 205 /* 206 * Block used, but not marked in use in the bitmap. 207 */ 208 problem = PR_5_BLOCK_USED; 209 } 210 if (pctx.blk == NO_BLK) { 211 pctx.blk = pctx.blk2 = i; 212 save_problem = problem; 213 } else { 214 if ((problem == save_problem) && 215 (pctx.blk2 == i-1)) 216 pctx.blk2++; 217 else { 218 print_bitmap_problem(ctx, save_problem, &pctx); 219 pctx.blk = pctx.blk2 = i; 220 save_problem = problem; 221 } 222 } 223 ctx->flags |= E2F_FLAG_PROG_SUPPRESS; 224 had_problem++; 225 226 do_counts: 227 if (!bitmap && !skip_group) { 228 group_free++; 229 free_blocks++; 230 } 231 blocks ++; 232 if ((blocks == fs->super->s_blocks_per_group) || 233 (i == fs->super->s_blocks_count-1)) { 234 free_array[group] = group_free; 235 group ++; 236 blocks = 0; 237 group_free = 0; 238 skip_group = 0; 239 super += fs->super->s_blocks_per_group; 240 if (ctx->progress) 241 if ((ctx->progress)(ctx, 5, group, 242 fs->group_desc_count*2)) 243 goto errout; 244 if (lazy_bg && 245 (i != fs->super->s_blocks_count-1) && 246 (fs->group_desc[group].bg_flags & 247 EXT2_BG_BLOCK_UNINIT)) 248 skip_group++; 249 } 250 } 251 if (pctx.blk != NO_BLK) 252 print_bitmap_problem(ctx, save_problem, &pctx); 253 if (had_problem) 254 fixit = end_problem_latch(ctx, PR_LATCH_BBITMAP); 255 else 256 fixit = -1; 257 ctx->flags &= ~E2F_FLAG_PROG_SUPPRESS; 258 259 if (fixit == 1) { 260 ext2fs_free_block_bitmap(fs->block_map); 261 retval = ext2fs_copy_bitmap(ctx->block_found_map, 262 &fs->block_map); 263 if (retval) { 264 clear_problem_context(&pctx); 265 fix_problem(ctx, PR_5_COPY_BBITMAP_ERROR, &pctx); 266 ctx->flags |= E2F_FLAG_ABORT; 267 goto errout; 268 } 269 ext2fs_set_bitmap_padding(fs->block_map); 270 ext2fs_mark_bb_dirty(fs); 271 272 /* Redo the counts */ 273 blocks = 0; free_blocks = 0; group_free = 0; group = 0; 274 memset(free_array, 0, fs->group_desc_count * sizeof(int)); 275 goto redo_counts; 276 } else if (fixit == 0) 277 ext2fs_unmark_valid(fs); 278 279 for (i = 0; i < fs->group_desc_count; i++) { 280 if (free_array[i] != fs->group_desc[i].bg_free_blocks_count) { 281 pctx.group = i; 282 pctx.blk = fs->group_desc[i].bg_free_blocks_count; 283 pctx.blk2 = free_array[i]; 284 285 if (fix_problem(ctx, PR_5_FREE_BLOCK_COUNT_GROUP, 286 &pctx)) { 287 fs->group_desc[i].bg_free_blocks_count = 288 free_array[i]; 289 ext2fs_mark_super_dirty(fs); 290 } else 291 ext2fs_unmark_valid(fs); 292 } 293 } 294 if (free_blocks != fs->super->s_free_blocks_count) { 295 pctx.group = 0; 296 pctx.blk = fs->super->s_free_blocks_count; 297 pctx.blk2 = free_blocks; 298 299 if (fix_problem(ctx, PR_5_FREE_BLOCK_COUNT, &pctx)) { 300 fs->super->s_free_blocks_count = free_blocks; 301 ext2fs_mark_super_dirty(fs); 302 } else 303 ext2fs_unmark_valid(fs); 304 } 305 errout: 306 ext2fs_free_mem(&free_array); 307 } 308 309 static void check_inode_bitmaps(e2fsck_t ctx) 310 { 311 ext2_filsys fs = ctx->fs; 312 ext2_ino_t i; 313 unsigned int free_inodes = 0; 314 int group_free = 0; 315 int dirs_count = 0; 316 int group = 0; 317 unsigned int inodes = 0; 318 int *free_array; 319 int *dir_array; 320 int actual, bitmap; 321 errcode_t retval; 322 struct problem_context pctx; 323 int problem, save_problem, fixit, had_problem; 324 int lazy_bg = 0; 325 int skip_group = 0; 326 327 clear_problem_context(&pctx); 328 free_array = (int *) e2fsck_allocate_memory(ctx, 329 fs->group_desc_count * sizeof(int), "free inode count array"); 330 331 dir_array = (int *) e2fsck_allocate_memory(ctx, 332 fs->group_desc_count * sizeof(int), "directory count array"); 333 334 if ((1 < ext2fs_get_inode_bitmap_start(ctx->inode_used_map)) || 335 (fs->super->s_inodes_count > 336 ext2fs_get_inode_bitmap_end(ctx->inode_used_map))) { 337 pctx.num = 3; 338 pctx.blk = 1; 339 pctx.blk2 = fs->super->s_inodes_count; 340 pctx.ino = ext2fs_get_inode_bitmap_start(ctx->inode_used_map); 341 pctx.ino2 = ext2fs_get_inode_bitmap_end(ctx->inode_used_map); 342 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx); 343 344 ctx->flags |= E2F_FLAG_ABORT; /* fatal */ 345 goto errout; 346 } 347 if ((1 < ext2fs_get_inode_bitmap_start(fs->inode_map)) || 348 (fs->super->s_inodes_count > 349 ext2fs_get_inode_bitmap_end(fs->inode_map))) { 350 pctx.num = 4; 351 pctx.blk = 1; 352 pctx.blk2 = fs->super->s_inodes_count; 353 pctx.ino = ext2fs_get_inode_bitmap_start(fs->inode_map); 354 pctx.ino2 = ext2fs_get_inode_bitmap_end(fs->inode_map); 355 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx); 356 357 ctx->flags |= E2F_FLAG_ABORT; /* fatal */ 358 goto errout; 359 } 360 361 if (EXT2_HAS_COMPAT_FEATURE(fs->super, 362 EXT2_FEATURE_COMPAT_LAZY_BG)) 363 lazy_bg++; 364 365 redo_counts: 366 had_problem = 0; 367 save_problem = 0; 368 pctx.ino = pctx.ino2 = 0; 369 if (lazy_bg && (fs->group_desc[group].bg_flags & 370 EXT2_BG_INODE_UNINIT)) 371 skip_group++; 372 373 /* Protect loop from wrap-around if inodes_count is maxed */ 374 for (i = 1; i <= fs->super->s_inodes_count && i > 0; i++) { 375 actual = ext2fs_fast_test_inode_bitmap(ctx->inode_used_map, i); 376 if (skip_group) 377 bitmap = 0; 378 else 379 bitmap = ext2fs_fast_test_inode_bitmap(fs->inode_map, i); 380 if (actual == bitmap) 381 goto do_counts; 382 383 if (!actual && bitmap) { 384 /* 385 * Inode wasn't used, but marked in bitmap 386 */ 387 problem = PR_5_INODE_UNUSED; 388 } else /* if (actual && !bitmap) */ { 389 /* 390 * Inode used, but not in bitmap 391 */ 392 problem = PR_5_INODE_USED; 393 } 394 if (pctx.ino == 0) { 395 pctx.ino = pctx.ino2 = i; 396 save_problem = problem; 397 } else { 398 if ((problem == save_problem) && 399 (pctx.ino2 == i-1)) 400 pctx.ino2++; 401 else { 402 print_bitmap_problem(ctx, save_problem, &pctx); 403 pctx.ino = pctx.ino2 = i; 404 save_problem = problem; 405 } 406 } 407 ctx->flags |= E2F_FLAG_PROG_SUPPRESS; 408 had_problem++; 409 410 do_counts: 411 if (bitmap) { 412 if (ext2fs_test_inode_bitmap(ctx->inode_dir_map, i)) 413 dirs_count++; 414 } else if (!skip_group) { 415 group_free++; 416 free_inodes++; 417 } 418 inodes++; 419 if ((inodes == fs->super->s_inodes_per_group) || 420 (i == fs->super->s_inodes_count)) { 421 free_array[group] = group_free; 422 dir_array[group] = dirs_count; 423 group ++; 424 inodes = 0; 425 skip_group = 0; 426 group_free = 0; 427 dirs_count = 0; 428 if (ctx->progress) 429 if ((ctx->progress)(ctx, 5, 430 group + fs->group_desc_count, 431 fs->group_desc_count*2)) 432 goto errout; 433 if (lazy_bg && 434 (i != fs->super->s_inodes_count) && 435 (fs->group_desc[group].bg_flags & 436 EXT2_BG_INODE_UNINIT)) 437 skip_group++; 438 } 439 } 440 if (pctx.ino) 441 print_bitmap_problem(ctx, save_problem, &pctx); 442 443 if (had_problem) 444 fixit = end_problem_latch(ctx, PR_LATCH_IBITMAP); 445 else 446 fixit = -1; 447 ctx->flags &= ~E2F_FLAG_PROG_SUPPRESS; 448 449 if (fixit == 1) { 450 ext2fs_free_inode_bitmap(fs->inode_map); 451 retval = ext2fs_copy_bitmap(ctx->inode_used_map, 452 &fs->inode_map); 453 if (retval) { 454 clear_problem_context(&pctx); 455 fix_problem(ctx, PR_5_COPY_IBITMAP_ERROR, &pctx); 456 ctx->flags |= E2F_FLAG_ABORT; 457 goto errout; 458 } 459 ext2fs_set_bitmap_padding(fs->inode_map); 460 ext2fs_mark_ib_dirty(fs); 461 462 /* redo counts */ 463 inodes = 0; free_inodes = 0; group_free = 0; 464 dirs_count = 0; group = 0; 465 memset(free_array, 0, fs->group_desc_count * sizeof(int)); 466 memset(dir_array, 0, fs->group_desc_count * sizeof(int)); 467 goto redo_counts; 468 } else if (fixit == 0) 469 ext2fs_unmark_valid(fs); 470 471 for (i = 0; i < fs->group_desc_count; i++) { 472 if (free_array[i] != fs->group_desc[i].bg_free_inodes_count) { 473 pctx.group = i; 474 pctx.ino = fs->group_desc[i].bg_free_inodes_count; 475 pctx.ino2 = free_array[i]; 476 if (fix_problem(ctx, PR_5_FREE_INODE_COUNT_GROUP, 477 &pctx)) { 478 fs->group_desc[i].bg_free_inodes_count = 479 free_array[i]; 480 ext2fs_mark_super_dirty(fs); 481 } else 482 ext2fs_unmark_valid(fs); 483 } 484 if (dir_array[i] != fs->group_desc[i].bg_used_dirs_count) { 485 pctx.group = i; 486 pctx.ino = fs->group_desc[i].bg_used_dirs_count; 487 pctx.ino2 = dir_array[i]; 488 489 if (fix_problem(ctx, PR_5_FREE_DIR_COUNT_GROUP, 490 &pctx)) { 491 fs->group_desc[i].bg_used_dirs_count = 492 dir_array[i]; 493 ext2fs_mark_super_dirty(fs); 494 } else 495 ext2fs_unmark_valid(fs); 496 } 497 } 498 if (free_inodes != fs->super->s_free_inodes_count) { 499 pctx.group = -1; 500 pctx.ino = fs->super->s_free_inodes_count; 501 pctx.ino2 = free_inodes; 502 503 if (fix_problem(ctx, PR_5_FREE_INODE_COUNT, &pctx)) { 504 fs->super->s_free_inodes_count = free_inodes; 505 ext2fs_mark_super_dirty(fs); 506 } else 507 ext2fs_unmark_valid(fs); 508 } 509 errout: 510 ext2fs_free_mem(&free_array); 511 ext2fs_free_mem(&dir_array); 512 } 513 514 static void check_inode_end(e2fsck_t ctx) 515 { 516 ext2_filsys fs = ctx->fs; 517 ext2_ino_t end, save_inodes_count, i; 518 struct problem_context pctx; 519 520 clear_problem_context(&pctx); 521 522 end = EXT2_INODES_PER_GROUP(fs->super) * fs->group_desc_count; 523 pctx.errcode = ext2fs_fudge_inode_bitmap_end(fs->inode_map, end, 524 &save_inodes_count); 525 if (pctx.errcode) { 526 pctx.num = 1; 527 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx); 528 ctx->flags |= E2F_FLAG_ABORT; /* fatal */ 529 return; 530 } 531 if (save_inodes_count == end) 532 return; 533 534 /* protect loop from wrap-around if end is maxed */ 535 for (i = save_inodes_count + 1; i <= end && i > save_inodes_count; i++) { 536 if (!ext2fs_test_inode_bitmap(fs->inode_map, i)) { 537 if (fix_problem(ctx, PR_5_INODE_BMAP_PADDING, &pctx)) { 538 for (i = save_inodes_count + 1; i <= end; i++) 539 ext2fs_mark_inode_bitmap(fs->inode_map, 540 i); 541 ext2fs_mark_ib_dirty(fs); 542 } else 543 ext2fs_unmark_valid(fs); 544 break; 545 } 546 } 547 548 pctx.errcode = ext2fs_fudge_inode_bitmap_end(fs->inode_map, 549 save_inodes_count, 0); 550 if (pctx.errcode) { 551 pctx.num = 2; 552 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx); 553 ctx->flags |= E2F_FLAG_ABORT; /* fatal */ 554 return; 555 } 556 } 557 558 static void check_block_end(e2fsck_t ctx) 559 { 560 ext2_filsys fs = ctx->fs; 561 blk_t end, save_blocks_count, i; 562 struct problem_context pctx; 563 564 clear_problem_context(&pctx); 565 566 end = fs->block_map->start + 567 (EXT2_BLOCKS_PER_GROUP(fs->super) * fs->group_desc_count) - 1; 568 pctx.errcode = ext2fs_fudge_block_bitmap_end(fs->block_map, end, 569 &save_blocks_count); 570 if (pctx.errcode) { 571 pctx.num = 3; 572 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx); 573 ctx->flags |= E2F_FLAG_ABORT; /* fatal */ 574 return; 575 } 576 if (save_blocks_count == end) 577 return; 578 579 /* Protect loop from wrap-around if end is maxed */ 580 for (i = save_blocks_count + 1; i <= end && i > save_blocks_count; i++) { 581 if (!ext2fs_test_block_bitmap(fs->block_map, i)) { 582 if (fix_problem(ctx, PR_5_BLOCK_BMAP_PADDING, &pctx)) { 583 for (i = save_blocks_count + 1; i <= end; i++) 584 ext2fs_mark_block_bitmap(fs->block_map, 585 i); 586 ext2fs_mark_bb_dirty(fs); 587 } else 588 ext2fs_unmark_valid(fs); 589 break; 590 } 591 } 592 593 pctx.errcode = ext2fs_fudge_block_bitmap_end(fs->block_map, 594 save_blocks_count, 0); 595 if (pctx.errcode) { 596 pctx.num = 4; 597 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx); 598 ctx->flags |= E2F_FLAG_ABORT; /* fatal */ 599 return; 600 } 601 } 602 603 604 605