2 * pass5.c --- check block and inode bitmaps against on-disk bitmaps
4 * Copyright (C) 1993, 1994, 1995, 1996, 1997 Theodore Ts'o.
7 * This file may be redistributed under the terms of the GNU Public
14 #include <sys/types.h>
16 #include <sys/ioctl.h>
23 #define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))
25 static void check_block_bitmaps(e2fsck_t ctx);
26 static void check_inode_bitmaps(e2fsck_t ctx);
27 static void check_inode_end(e2fsck_t ctx);
28 static void check_block_end(e2fsck_t ctx);
30 void e2fsck_pass5(e2fsck_t ctx)
33 struct resource_track rtrack;
35 struct problem_context pctx;
38 mtrace_print("Pass 5");
41 init_resource_track(&rtrack, ctx->fs->io);
42 clear_problem_context(&pctx);
44 if (!(ctx->options & E2F_OPT_PREEN))
45 fix_problem(ctx, PR_5_PASS_HEADER, &pctx);
48 if ((ctx->progress)(ctx, 5, 0, ctx->fs->group_desc_count*2))
51 e2fsck_read_bitmaps(ctx);
53 check_block_bitmaps(ctx);
54 if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
56 check_inode_bitmaps(ctx);
57 if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
60 if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
63 if (ctx->flags & E2F_FLAG_SIGNAL_MASK)
66 ext2fs_free_inode_bitmap(ctx->inode_used_map);
67 ctx->inode_used_map = 0;
68 ext2fs_free_inode_bitmap(ctx->inode_dir_map);
69 ctx->inode_dir_map = 0;
70 ext2fs_free_block_bitmap(ctx->block_found_map);
71 ctx->block_found_map = 0;
73 print_resource_track(ctx, _("Pass 5"), &rtrack, ctx->fs->io);
76 static void e2fsck_discard_blocks(e2fsck_t ctx, io_manager manager,
77 blk64_t start, blk64_t count)
79 ext2_filsys fs = ctx->fs;
83 * If the filesystem has changed it means that there was an corruption
84 * which should be repaired, but in some cases just one e2fsck run is
85 * not enough to fix the problem, hence it is not safe to run discard
88 if (ext2fs_test_changed(ctx->fs))
89 ctx->options &= ~E2F_OPT_DISCARD;
91 if ((ctx->options & E2F_OPT_DISCARD) &&
92 (io_channel_discard(fs->io, start, count)))
93 ctx->options &= ~E2F_OPT_DISCARD;
96 #define NO_BLK ((blk64_t) -1)
98 static void print_bitmap_problem(e2fsck_t ctx, int problem,
99 struct problem_context *pctx)
102 case PR_5_BLOCK_UNUSED:
103 if (pctx->blk == pctx->blk2)
106 problem = PR_5_BLOCK_RANGE_UNUSED;
108 case PR_5_BLOCK_USED:
109 if (pctx->blk == pctx->blk2)
112 problem = PR_5_BLOCK_RANGE_USED;
114 case PR_5_INODE_UNUSED:
115 if (pctx->ino == pctx->ino2)
118 problem = PR_5_INODE_RANGE_UNUSED;
120 case PR_5_INODE_USED:
121 if (pctx->ino == pctx->ino2)
124 problem = PR_5_INODE_RANGE_USED;
127 fix_problem(ctx, problem, pctx);
128 pctx->blk = pctx->blk2 = NO_BLK;
129 pctx->ino = pctx->ino2 = 0;
132 static void check_block_bitmaps(e2fsck_t ctx)
134 ext2_filsys fs = ctx->fs;
139 blk64_t free_blocks = 0;
140 blk64_t first_free = ext2fs_blocks_count(fs->super);
143 struct problem_context pctx;
144 int problem, save_problem, fixit, had_problem;
148 int old_desc_blocks = 0;
152 blk64_t super_blk, old_desc_blk, new_desc_blk;
153 io_manager manager = ctx->fs->io->manager;
155 clear_problem_context(&pctx);
156 free_array = (int *) e2fsck_allocate_memory(ctx,
157 fs->group_desc_count * sizeof(int), "free block count array");
159 if ((fs->super->s_first_data_block <
160 ext2fs_get_block_bitmap_start2(ctx->block_found_map)) ||
161 (ext2fs_blocks_count(fs->super)-1 >
162 ext2fs_get_block_bitmap_end2(ctx->block_found_map))) {
164 pctx.blk = fs->super->s_first_data_block;
165 pctx.blk2 = ext2fs_blocks_count(fs->super) -1;
166 pctx.ino = ext2fs_get_block_bitmap_start2(ctx->block_found_map);
167 pctx.ino2 = ext2fs_get_block_bitmap_end2(ctx->block_found_map);
168 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
170 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
174 if ((fs->super->s_first_data_block <
175 ext2fs_get_block_bitmap_start2(fs->block_map)) ||
176 (ext2fs_blocks_count(fs->super)-1 >
177 ext2fs_get_block_bitmap_end2(fs->block_map))) {
179 pctx.blk = fs->super->s_first_data_block;
180 pctx.blk2 = ext2fs_blocks_count(fs->super) -1;
181 pctx.ino = ext2fs_get_block_bitmap_start2(fs->block_map);
182 pctx.ino2 = ext2fs_get_block_bitmap_end2(fs->block_map);
183 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
185 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
189 csum_flag = EXT2_HAS_RO_COMPAT_FEATURE(fs->super,
190 EXT4_FEATURE_RO_COMPAT_GDT_CSUM);
194 pctx.blk = pctx.blk2 = NO_BLK;
196 (ext2fs_bg_flags_test(fs, group, EXT2_BG_BLOCK_UNINIT)))
198 for (i = fs->super->s_first_data_block;
199 i < ext2fs_blocks_count(fs->super);
201 actual = ext2fs_fast_test_block_bitmap2(ctx->block_found_map, i);
204 if ((i - fs->super->s_first_data_block) %
205 fs->super->s_blocks_per_group == 0) {
209 ext2fs_super_and_bgd_loc2(fs, group, &super_blk,
210 &old_desc_blk, &new_desc_blk, 0);
212 if (fs->super->s_feature_incompat &
213 EXT2_FEATURE_INCOMPAT_META_BG)
215 fs->super->s_first_meta_bg;
217 old_desc_blocks = fs->desc_blocks +
218 fs->super->s_reserved_gdt_blocks;
221 cmp_block = fs->super->s_blocks_per_group;
222 if (group == (int)fs->group_desc_count - 1)
224 ext2fs_blocks_count(fs->super) %
225 fs->super->s_blocks_per_group;
229 if ((i == super_blk) ||
230 (old_desc_blk && old_desc_blocks &&
231 (i >= old_desc_blk) &&
232 (i < old_desc_blk + old_desc_blocks)) ||
233 (new_desc_blk && (i == new_desc_blk)) ||
234 (i == ext2fs_block_bitmap_loc(fs, group)) ||
235 (i == ext2fs_inode_bitmap_loc(fs, group)) ||
236 (i >= ext2fs_inode_table_loc(fs, group) &&
237 (i < ext2fs_inode_table_loc(fs, group) +
238 fs->inode_blocks_per_group))) {
240 actual = (actual != 0);
243 } else if ((i - count - fs->super->s_first_data_block) %
244 fs->super->s_blocks_per_group == 0) {
246 * When the compare data blocks in block bitmap
247 * are 0, count the free block,
248 * skip the current block group.
250 if (ext2fs_test_block_bitmap_range2(
251 ctx->block_found_map, i,
254 * -1 means to skip the current block
257 blocks = fs->super->s_blocks_per_group
259 group_free = cmp_block;
260 free_blocks += cmp_block;
262 * The current block group's last block
270 } else if (redo_flag)
273 bitmap = ext2fs_fast_test_block_bitmap2(fs->block_map, i);
275 if (actual == bitmap)
278 if (!actual && bitmap) {
280 * Block not used, but marked in use in the bitmap.
282 problem = PR_5_BLOCK_UNUSED;
285 * Block used, but not marked in use in the bitmap.
287 problem = PR_5_BLOCK_USED;
290 struct problem_context pctx2;
293 if (fix_problem(ctx, PR_5_BLOCK_UNINIT,&pctx2)){
294 ext2fs_bg_flags_clear(fs, group, EXT2_BG_BLOCK_UNINIT);
299 if (pctx.blk == NO_BLK) {
300 pctx.blk = pctx.blk2 = i;
301 save_problem = problem;
303 if ((problem == save_problem) &&
307 print_bitmap_problem(ctx, save_problem, &pctx);
308 pctx.blk = pctx.blk2 = i;
309 save_problem = problem;
312 ctx->flags |= E2F_FLAG_PROG_SUPPRESS;
316 * If there a problem we should turn off the discard so we
317 * do not compromise the filesystem.
319 ctx->options &= ~E2F_OPT_DISCARD;
322 if (!bitmap && (!skip_group || csum_flag)) {
328 if ((i > first_free) &&
329 (ctx->options & E2F_OPT_DISCARD)) {
330 e2fsck_discard_blocks(ctx, manager, first_free,
333 first_free = ext2fs_blocks_count(fs->super);
336 if ((blocks == fs->super->s_blocks_per_group) ||
337 (i == ext2fs_blocks_count(fs->super)-1)) {
338 free_array[group] = group_free;
344 if ((ctx->progress)(ctx, 5, group,
345 fs->group_desc_count*2))
348 (i != ext2fs_blocks_count(fs->super)-1) &&
349 ext2fs_bg_flags_test(fs, group,
350 EXT2_BG_BLOCK_UNINIT))
354 if (pctx.blk != NO_BLK)
355 print_bitmap_problem(ctx, save_problem, &pctx);
357 fixit = end_problem_latch(ctx, PR_LATCH_BBITMAP);
360 ctx->flags &= ~E2F_FLAG_PROG_SUPPRESS;
363 ext2fs_free_block_bitmap(fs->block_map);
364 retval = ext2fs_copy_bitmap(ctx->block_found_map,
367 clear_problem_context(&pctx);
368 fix_problem(ctx, PR_5_COPY_BBITMAP_ERROR, &pctx);
369 ctx->flags |= E2F_FLAG_ABORT;
372 ext2fs_set_bitmap_padding(fs->block_map);
373 ext2fs_mark_bb_dirty(fs);
375 /* Redo the counts */
376 blocks = 0; free_blocks = 0; group_free = 0; group = 0;
377 memset(free_array, 0, fs->group_desc_count * sizeof(int));
380 } else if (fixit == 0)
381 ext2fs_unmark_valid(fs);
383 for (i = 0; i < fs->group_desc_count; i++) {
384 if (free_array[i] != ext2fs_bg_free_blocks_count(fs, i)) {
386 pctx.blk = ext2fs_bg_free_blocks_count(fs, i);
387 pctx.blk2 = free_array[i];
389 if (fix_problem(ctx, PR_5_FREE_BLOCK_COUNT_GROUP,
391 ext2fs_bg_free_blocks_count_set(fs, i, free_array[i]);
392 ext2fs_mark_super_dirty(fs);
394 ext2fs_unmark_valid(fs);
397 if (free_blocks != ext2fs_free_blocks_count(fs->super)) {
399 pctx.blk = ext2fs_free_blocks_count(fs->super);
400 pctx.blk2 = free_blocks;
402 if (fix_problem(ctx, PR_5_FREE_BLOCK_COUNT, &pctx)) {
403 ext2fs_free_blocks_count_set(fs->super, free_blocks);
404 ext2fs_mark_super_dirty(fs);
406 ext2fs_unmark_valid(fs);
409 ext2fs_free_mem(&free_array);
412 static void check_inode_bitmaps(e2fsck_t ctx)
414 ext2_filsys fs = ctx->fs;
416 unsigned int free_inodes = 0;
420 unsigned int inodes = 0;
425 struct problem_context pctx;
426 int problem, save_problem, fixit, had_problem;
430 io_manager manager = ctx->fs->io->manager;
432 clear_problem_context(&pctx);
433 free_array = (int *) e2fsck_allocate_memory(ctx,
434 fs->group_desc_count * sizeof(int), "free inode count array");
436 dir_array = (int *) e2fsck_allocate_memory(ctx,
437 fs->group_desc_count * sizeof(int), "directory count array");
439 if ((1 < ext2fs_get_inode_bitmap_start2(ctx->inode_used_map)) ||
440 (fs->super->s_inodes_count >
441 ext2fs_get_inode_bitmap_end2(ctx->inode_used_map))) {
444 pctx.blk2 = fs->super->s_inodes_count;
445 pctx.ino = ext2fs_get_inode_bitmap_start2(ctx->inode_used_map);
446 pctx.ino2 = ext2fs_get_inode_bitmap_end2(ctx->inode_used_map);
447 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
449 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
452 if ((1 < ext2fs_get_inode_bitmap_start2(fs->inode_map)) ||
453 (fs->super->s_inodes_count >
454 ext2fs_get_inode_bitmap_end2(fs->inode_map))) {
457 pctx.blk2 = fs->super->s_inodes_count;
458 pctx.ino = ext2fs_get_inode_bitmap_start2(fs->inode_map);
459 pctx.ino2 = ext2fs_get_inode_bitmap_end2(fs->inode_map);
460 fix_problem(ctx, PR_5_BMAP_ENDPOINTS, &pctx);
462 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
466 csum_flag = EXT2_HAS_RO_COMPAT_FEATURE(fs->super,
467 EXT4_FEATURE_RO_COMPAT_GDT_CSUM);
471 pctx.ino = pctx.ino2 = 0;
473 (ext2fs_bg_flags_test(fs, group, EXT2_BG_INODE_UNINIT)))
476 /* Protect loop from wrap-around if inodes_count is maxed */
477 for (i = 1; i <= fs->super->s_inodes_count && i > 0; i++) {
480 i % fs->super->s_inodes_per_group == 1) {
482 * Current inode is the first inode
483 * in the current block group.
485 if (ext2fs_test_inode_bitmap_range(
486 ctx->inode_used_map, i,
487 fs->super->s_inodes_per_group)) {
489 * When the compared inodes in inodes bitmap
490 * are 0, count the free inode,
491 * skip the current block group.
493 inodes = fs->super->s_inodes_per_group - 1;
495 free_inodes += inodes;
502 actual = ext2fs_fast_test_inode_bitmap2(ctx->inode_used_map, i);
505 else if (!skip_group)
506 bitmap = ext2fs_fast_test_inode_bitmap2(fs->inode_map, i);
507 if (actual == bitmap)
510 if (!actual && bitmap) {
512 * Inode wasn't used, but marked in bitmap
514 problem = PR_5_INODE_UNUSED;
515 } else /* if (actual && !bitmap) */ {
517 * Inode used, but not in bitmap
519 problem = PR_5_INODE_USED;
521 /* We should never hit this, because it means that
522 * inodes were marked in use that weren't noticed
523 * in pass1 or pass 2. It is easier to fix the problem
524 * than to kill e2fsck and leave the user stuck. */
526 struct problem_context pctx2;
529 if (fix_problem(ctx, PR_5_INODE_UNINIT,&pctx2)){
530 ext2fs_bg_flags_clear(fs, group, EXT2_BG_INODE_UNINIT);
536 pctx.ino = pctx.ino2 = i;
537 save_problem = problem;
539 if ((problem == save_problem) &&
543 print_bitmap_problem(ctx, save_problem, &pctx);
544 pctx.ino = pctx.ino2 = i;
545 save_problem = problem;
548 ctx->flags |= E2F_FLAG_PROG_SUPPRESS;
551 * If there a problem we should turn off the discard so we
552 * do not compromise the filesystem.
554 ctx->options &= ~E2F_OPT_DISCARD;
558 if (ext2fs_test_inode_bitmap2(ctx->inode_dir_map, i))
560 } else if (!skip_group || csum_flag) {
566 if ((inodes == fs->super->s_inodes_per_group) ||
567 (i == fs->super->s_inodes_count)) {
569 free_array[group] = group_free;
570 dir_array[group] = dirs_count;
572 /* Discard inode table */
573 if (ctx->options & E2F_OPT_DISCARD) {
574 blk64_t used_blks, blk, num;
576 used_blks = DIV_ROUND_UP(
577 (EXT2_INODES_PER_GROUP(fs->super) -
579 EXT2_INODES_PER_BLOCK(fs->super));
581 blk = ext2fs_inode_table_loc(fs, group) +
583 num = fs->inode_blocks_per_group -
585 e2fsck_discard_blocks(ctx, manager, blk, num);
589 * If discard zeroes data and the group inode table
590 * was not zeroed yet, set itable as zeroed
592 if ((ctx->options & E2F_OPT_DISCARD) &&
593 (io_channel_discard_zeroes_data(fs->io)) &&
594 !(ext2fs_bg_flags_test(fs, group,
595 EXT2_BG_INODE_ZEROED))) {
596 ext2fs_bg_flags_set(fs, group,
597 EXT2_BG_INODE_ZEROED);
598 ext2fs_group_desc_csum_set(fs, group);
607 if ((ctx->progress)(ctx, 5,
608 group + fs->group_desc_count,
609 fs->group_desc_count*2))
612 (i != fs->super->s_inodes_count) &&
613 (ext2fs_bg_flags_test(fs, group, EXT2_BG_INODE_UNINIT)
619 print_bitmap_problem(ctx, save_problem, &pctx);
622 fixit = end_problem_latch(ctx, PR_LATCH_IBITMAP);
625 ctx->flags &= ~E2F_FLAG_PROG_SUPPRESS;
628 ext2fs_free_inode_bitmap(fs->inode_map);
629 retval = ext2fs_copy_bitmap(ctx->inode_used_map,
632 clear_problem_context(&pctx);
633 fix_problem(ctx, PR_5_COPY_IBITMAP_ERROR, &pctx);
634 ctx->flags |= E2F_FLAG_ABORT;
637 ext2fs_set_bitmap_padding(fs->inode_map);
638 ext2fs_mark_ib_dirty(fs);
641 inodes = 0; free_inodes = 0; group_free = 0;
642 dirs_count = 0; group = 0;
643 memset(free_array, 0, fs->group_desc_count * sizeof(int));
644 memset(dir_array, 0, fs->group_desc_count * sizeof(int));
647 } else if (fixit == 0)
648 ext2fs_unmark_valid(fs);
650 for (i = 0; i < fs->group_desc_count; i++) {
651 if (free_array[i] != ext2fs_bg_free_inodes_count(fs, i)) {
653 pctx.ino = ext2fs_bg_free_inodes_count(fs, i);
654 pctx.ino2 = free_array[i];
655 if (fix_problem(ctx, PR_5_FREE_INODE_COUNT_GROUP,
657 ext2fs_bg_free_inodes_count_set(fs, i, free_array[i]);
658 ext2fs_mark_super_dirty(fs);
660 ext2fs_unmark_valid(fs);
662 if (dir_array[i] != ext2fs_bg_used_dirs_count(fs, i)) {
664 pctx.ino = ext2fs_bg_used_dirs_count(fs, i);
665 pctx.ino2 = dir_array[i];
667 if (fix_problem(ctx, PR_5_FREE_DIR_COUNT_GROUP,
669 ext2fs_bg_used_dirs_count_set(fs, i, dir_array[i]);
670 ext2fs_mark_super_dirty(fs);
672 ext2fs_unmark_valid(fs);
675 if (free_inodes != fs->super->s_free_inodes_count) {
677 pctx.ino = fs->super->s_free_inodes_count;
678 pctx.ino2 = free_inodes;
680 if (fix_problem(ctx, PR_5_FREE_INODE_COUNT, &pctx)) {
681 fs->super->s_free_inodes_count = free_inodes;
682 ext2fs_mark_super_dirty(fs);
684 ext2fs_unmark_valid(fs);
687 ext2fs_free_mem(&free_array);
688 ext2fs_free_mem(&dir_array);
691 static void check_inode_end(e2fsck_t ctx)
693 ext2_filsys fs = ctx->fs;
694 ext2_ino_t end, save_inodes_count, i;
695 struct problem_context pctx;
697 clear_problem_context(&pctx);
699 end = EXT2_INODES_PER_GROUP(fs->super) * fs->group_desc_count;
700 pctx.errcode = ext2fs_fudge_inode_bitmap_end(fs->inode_map, end,
704 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
705 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
708 if (save_inodes_count == end)
711 /* protect loop from wrap-around if end is maxed */
712 for (i = save_inodes_count + 1; i <= end && i > save_inodes_count; i++) {
713 if (!ext2fs_test_inode_bitmap(fs->inode_map, i)) {
714 if (fix_problem(ctx, PR_5_INODE_BMAP_PADDING, &pctx)) {
715 for (; i <= end; i++)
716 ext2fs_mark_inode_bitmap(fs->inode_map,
718 ext2fs_mark_ib_dirty(fs);
720 ext2fs_unmark_valid(fs);
725 pctx.errcode = ext2fs_fudge_inode_bitmap_end(fs->inode_map,
726 save_inodes_count, 0);
729 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
730 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
735 static void check_block_end(e2fsck_t ctx)
737 ext2_filsys fs = ctx->fs;
738 blk64_t end, save_blocks_count, i;
739 struct problem_context pctx;
741 clear_problem_context(&pctx);
743 end = ext2fs_get_block_bitmap_start2(fs->block_map) +
744 ((blk64_t)EXT2_BLOCKS_PER_GROUP(fs->super) * fs->group_desc_count) - 1;
745 pctx.errcode = ext2fs_fudge_block_bitmap_end2(fs->block_map, end,
749 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
750 ctx->flags |= E2F_FLAG_ABORT; /* fatal */
753 if (save_blocks_count == end)
756 /* Protect loop from wrap-around if end is maxed */
757 for (i = save_blocks_count + 1; i <= end && i > save_blocks_count; i++) {
758 if (!ext2fs_test_block_bitmap2(fs->block_map, i)) {
759 if (fix_problem(ctx, PR_5_BLOCK_BMAP_PADDING, &pctx)) {
760 for (; i <= end; i++)
761 ext2fs_mark_block_bitmap2(fs->block_map,
763 ext2fs_mark_bb_dirty(fs);
765 ext2fs_unmark_valid(fs);
770 pctx.errcode = ext2fs_fudge_block_bitmap_end2(fs->block_map,
771 save_blocks_count, 0);
774 fix_problem(ctx, PR_5_FUDGE_BITMAP_ERROR, &pctx);
775 ctx->flags |= E2F_FLAG_ABORT; /* fatal */