e2fsck: Improve consistency check of uninit block group
PATCH v2 1/1 e2fsck: Improve consistency check of uninit block group
Hi,
I have addressed Ted's comments.
(http://kerneltrap.org/mailarchive/linux-ext4/2009/7/3/6132903)
e2fsck_pass5() checks whether inode/block is consistency each. 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, e2fsck pass 5 becomes faster if it checks consistency of uninitialized block group each 256 bytes.
This patch cuts e2fsck pass 5 time by up to 80%. The following results show the e2fsck time.
Comparison of e2fsck time on an ext4 500GB partition (20% blocks used)
-------------------------------------------------
| | 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|
-------------------------------------------------
Machine environment:
CPU: Intel(R) Xeon(TM) CPU 3.00GHz Memory: 1GB Kernel: linux-2.6.29-git2 e2fsprogs: 1.41.6
The following patch can be applied to e2fsprogs git tree (master branch).
Regards,
Kazuya Mio
--- e2fsck/pass5.c | 135 +++++++++++++++++++++++++++++++++++++----------- lib/ext2fs/ext2fs.h | 2 lib/ext2fs/gen_bitmap.c | 94 +++++++++++++++++++++++++++++++++ 3 files changed, 201 insertions(+), 30 deletions(-)
e2fsck/pass5.c +105 -30
@@ -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,
@@ -166,39 +171,82 @@ 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; + } 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)) - bitmap =1 ; -if (i == fs->group_desc[group].bg_block_bitmap) +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 ; -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++; + }else if ((i - count - fs->super->s_first_data_block) % + fs->super->s_blocks_per_group ==0 ) { +/* +* Count the number of compare data blocks in +* every block group.The last block group's +* count is different, because that the last +* blockgroup is not saturation is possible. +*/ +if (group == (int )fs->group_desc_count -1 ) + cmp_block = fs->super->s_blocks_count - + i + + fs->super->s_first_data_block; +else + cmp_block = fs->super-> + s_blocks_per_group - count; + +/* +* When the compare data blocks in block bitmap +* are 0, count the free block, +* skip the current block group. +*/ +if (ext2fs_test_zero_range (i, cmp_block, + (ext2fs_generic_bitmap ) + ctx->block_found_map)) { +/* +* -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 ; + count =0 ; + 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)
@@ -291,6 +339,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);
@@ -342,6 +391,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,
@@ -389,10 +439,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_zero_range (i, + fs->super->s_inodes_per_group, + (ext2fs_generic_bitmap)(ctx->inode_used_map))) { +/* +* 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;
@@ -496,6 +570,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);
lib/ext2fs/ext2fs.h +0 -0
@@ -933,6 +933,8 @@ extern errcode_t
ext2fs_set_generic_bitmap_range(ext2fs_generic_bitmap bmap,
errcode_t magic, __u32 start, __u32 num, void *in);
+extern int ext2fs_test_zero_range(unsigned int start, unsigned int len,
+ ext2fs_generic_bitmap bitmap);
/* getsize.c */
extern errcode_t ext2fs_get_device_size(const char *file, int blocksize,
lib/ext2fs/gen_bitmap.c +94 -0
100 lines not on this page · raw message
Quoted 4 lines · Kazuya Mio
Hi,
I have addressed Ted's comments.
(http://kerneltrap.org/mailarchive/linux-ext4/2009/7/3/6132903)
I fixed it up a bit before applying it. It turns out we already had a function specific to block bitmaps, ext2fs_test_block_bitmap_range() which provides this functionality. So I added the optimized version of the generic bitmap test_range() function, and used it to speed upext2fs_test_block_bitmap_range(). This got placed into the maint branch.
The changes to e2fsck's pass5 has been checked into the 'master' branch of e2fsprogs.
- Ted