From 479463aaf641d9b2c46bd4cda4e5e941fd767c73 Mon Sep 17 00:00:00 2001 From: Kazuya Mio Date: Thu, 9 Jul 2009 13:46:59 -0400 Subject: [PATCH] e2fsck: Speed up pass 5 processing for ext4 filesystems e2fsck_pass5() checks whether the inode and block allocation bitmaps are consistent. However, if EXT2_BG_[INODE/BLOCK]_BITMAP is set to a ext4's block group, most of its bitmap is uninitialized (0). In that case, we can optimize e2fsck's pass 5 by checking the entire range of an uninitalized block group instead of checking bit by bit. This can speed up e2fsck pass 5 by up to 80%: +-----+--------------------+--------------------+ | | old e2fsck | new e2fsck | |Pass | time(s) | time(s) | | | real | user |system| real | user |system| +-----+------+------+------+------+------+------+ | 1 | 5.70| 3.29| 0.50| 5.66| 3.21| 0.54| | 2 | 3.33| 0.80| 0.19| 3.40| 0.82| 0.23| | 3 | 0.01| 0.00| 0.00| 0.01| 0.00| 0.00| | 4 | 1.04| 1.04| 0.00| 1.05| 1.04| 0.00| | 5 | 19.60| 17.27| 0.06| 3.53| 1.21| 0.05| +-----+------+------+------+------+------+------+ |Total| 29.94| 22.57| 0.80| 13.90| 6.47| 0.86| +-----+------+------+------+------+------+------+ Comparison of e2fsck time on an ext4 500GB partition (20% blocks used) Machine environment: CPU: Intel(R) Xeon(TM) CPU 3.00GHz Memory: 1GB Kernel: linux-2.6.29-git2 Signed-off-by: Kazuya Mio Signed-off-by: "Theodore Ts'o" --- e2fsck/pass5.c | 128 +++++++++++++++++++++++++++++++++++++++++++-------------- 1 file changed, 98 insertions(+), 30 deletions(-) diff --git a/e2fsck/pass5.c b/e2fsck/pass5.c index bc3bf02..f844738 100644 --- a/e2fsck/pass5.c +++ b/e2fsck/pass5.c @@ -115,6 +115,11 @@ static void check_block_bitmaps(e2fsck_t ctx) errcode_t retval; int csum_flag; int skip_group = 0; + int old_desc_blocks = 0; + int count = 0; + int cmp_block = 0; + int redo_flag = 0; + blk_t super_blk, old_desc_blk, new_desc_blk; clear_problem_context(&pctx); free_array = (int *) e2fsck_allocate_memory(ctx, @@ -165,39 +170,75 @@ redo_counts: actual = ext2fs_fast_test_block_bitmap(ctx->block_found_map, i); if (skip_group) { - blk_t super_blk, old_desc_blk, new_desc_blk; - int old_desc_blocks; - - ext2fs_super_and_bgd_loc(fs, group, &super_blk, + if ((i - fs->super->s_first_data_block) % + fs->super->s_blocks_per_group == 0) { + super_blk = 0; + old_desc_blk = 0; + new_desc_blk = 0; + ext2fs_super_and_bgd_loc(fs, group, &super_blk, &old_desc_blk, &new_desc_blk, 0); - if (fs->super->s_feature_incompat & - EXT2_FEATURE_INCOMPAT_META_BG) - old_desc_blocks = fs->super->s_first_meta_bg; - else - old_desc_blocks = fs->desc_blocks + + if (fs->super->s_feature_incompat & + EXT2_FEATURE_INCOMPAT_META_BG) + old_desc_blocks = + fs->super->s_first_meta_bg; + else + old_desc_blocks = fs->desc_blocks + fs->super->s_reserved_gdt_blocks; + count = 0; + cmp_block = fs->super->s_blocks_per_group; + if (group == (int)fs->group_desc_count - 1) + cmp_block = + fs->super->s_blocks_count % + fs->super->s_blocks_per_group; + } + bitmap = 0; - if (i == super_blk) - bitmap = 1; - if (old_desc_blk && old_desc_blocks && - (i >= old_desc_blk) && - (i < old_desc_blk + old_desc_blocks)) - bitmap = 1; - if (new_desc_blk && - (i == new_desc_blk)) + if ((i == super_blk) || + (old_desc_blk && old_desc_blocks && + (i >= old_desc_blk) && + (i < old_desc_blk + old_desc_blocks)) || + (new_desc_blk && (i == new_desc_blk)) || + (i == fs->group_desc[group].bg_block_bitmap) || + (i == fs->group_desc[group].bg_inode_bitmap) || + (i >= fs->group_desc[group].bg_inode_table && + (i < fs->group_desc[group].bg_inode_table + + fs->inode_blocks_per_group))) { bitmap = 1; - if (i == fs->group_desc[group].bg_block_bitmap) - bitmap = 1; - else if (i == fs->group_desc[group].bg_inode_bitmap) - bitmap = 1; - else if (i >= fs->group_desc[group].bg_inode_table && - (i < fs->group_desc[group].bg_inode_table - + fs->inode_blocks_per_group)) - bitmap = 1; - actual = (actual != 0); - } else + actual = (actual != 0); + count++; + cmp_block--; + } else if ((i - count - fs->super->s_first_data_block) % + fs->super->s_blocks_per_group == 0) { + /* + * When the compare data blocks in block bitmap + * are 0, count the free block, + * skip the current block group. + */ + if (ext2fs_test_block_bitmap_range( + ctx->block_found_map, i, + cmp_block)) { + /* + * -1 means to skip the current block + * group. + */ + blocks = fs->super->s_blocks_per_group + - 1; + group_free = cmp_block; + free_blocks += cmp_block; + /* + * The current block group's last block + * is set to i. + */ + i += cmp_block - 1; + bitmap = 1; + goto do_counts; + } + } + } else if (redo_flag) + bitmap = actual; + else bitmap = ext2fs_fast_test_block_bitmap(fs->block_map, i); if (actual == bitmap) @@ -289,6 +330,7 @@ redo_counts: /* Redo the counts */ blocks = 0; free_blocks = 0; group_free = 0; group = 0; memset(free_array, 0, fs->group_desc_count * sizeof(int)); + redo_flag++; goto redo_counts; } else if (fixit == 0) ext2fs_unmark_valid(fs); @@ -340,6 +382,7 @@ static void check_inode_bitmaps(e2fsck_t ctx) int problem, save_problem, fixit, had_problem; int csum_flag; int skip_group = 0; + int redo_flag = 0; clear_problem_context(&pctx); free_array = (int *) e2fsck_allocate_memory(ctx, @@ -387,10 +430,34 @@ redo_counts: /* Protect loop from wrap-around if inodes_count is maxed */ for (i = 1; i <= fs->super->s_inodes_count && i > 0; i++) { + bitmap = 0; + if (skip_group && + i % fs->super->s_inodes_per_group == 1) { + /* + * Current inode is the first inode + * in the current block group. + */ + if (ext2fs_test_inode_bitmap_range( + ctx->inode_used_map, i, + fs->super->s_inodes_per_group)) { + /* + * When the compared inodes in inodes bitmap + * are 0, count the free inode, + * skip the current block group. + */ + inodes = fs->super->s_inodes_per_group - 1; + group_free = inodes; + free_inodes += inodes; + i += inodes; + skip_group = 0; + goto do_counts; + } + } + actual = ext2fs_fast_test_inode_bitmap(ctx->inode_used_map, i); - if (skip_group) - bitmap = 0; - else + if (redo_flag) + bitmap = actual; + else if (!skip_group) bitmap = ext2fs_fast_test_inode_bitmap(fs->inode_map, i); if (actual == bitmap) goto do_counts; @@ -494,6 +561,7 @@ do_counts: dirs_count = 0; group = 0; memset(free_array, 0, fs->group_desc_count * sizeof(int)); memset(dir_array, 0, fs->group_desc_count * sizeof(int)); + redo_flag++; goto redo_counts; } else if (fixit == 0) ext2fs_unmark_valid(fs); -- 1.8.3.1