linux-ext4 - Re: [PATCH 6/6] e2fsck: optimize pass 5 for CPU utilization

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Mon, 26 Nov 2012 12:59:12 +0100 (CET)
From:	Lukáš Czerner <lczerner@...hat.com>
To:	"Theodore Ts'o" <tytso@....edu>
cc:	Ext4 Developers List <linux-ext4@...r.kernel.org>
Subject: Re: [PATCH 6/6] e2fsck: optimize pass 5 for CPU utilization

On Sat, 24 Nov 2012, Theodore Ts'o wrote:

> Date: Sat, 24 Nov 2012 19:36:34 -0500
> From: Theodore Ts'o <tytso@....edu>
> To: Ext4 Developers List <linux-ext4@...r.kernel.org>
> Cc: Theodore Ts'o <tytso@....edu>
> Subject: [PATCH 6/6] e2fsck: optimize pass 5 for CPU utilization
> 
> Add a fast past optimization in e2fsck's pass 5 for the common case
> where the block bitmap is correct.  The optimization works by
> extracting each block group's block allocation bitmap into a memory
> buffer, and comparing it with the expected allocation bitmap using
> memcmp().  If it matches, then we can just update the free block
> counts and be on our way, and skip checking each bit individually.
> 
> Addresses-Google-Bug: #7534813

Looks good, we can always move the discard operation at the end of
the function before we free the bitmap, but that's further
optimization.

Reviewed-by: Lukas Czerner <lczerner@...hat.com>

> 
> Signed-off-by: "Theodore Ts'o" <tytso@....edu>
> ---
>  e2fsck/pass5.c | 55 +++++++++++++++++++++++++++++++++++++++++++++++++++++--
>  1 file changed, 53 insertions(+), 2 deletions(-)
> 
> diff --git a/e2fsck/pass5.c b/e2fsck/pass5.c
> index 8312fe0..5aff55c 100644
> --- a/e2fsck/pass5.c
> +++ b/e2fsck/pass5.c
> @@ -212,6 +212,12 @@ static void check_block_bitmaps(e2fsck_t ctx)
>  	int	cmp_block = 0;
>  	int	redo_flag = 0;
>  	blk64_t	super_blk, old_desc_blk, new_desc_blk;
> +	char *actual_buf, *bitmap_buf;
> +
> +	actual_buf = (char *) e2fsck_allocate_memory(ctx, fs->blocksize,
> +						     "actual bitmap buffer");
> +	bitmap_buf = (char *) e2fsck_allocate_memory(ctx, fs->blocksize,
> +						     "bitmap block buffer");
>  
>  	clear_problem_context(&pctx);
>  	free_array = (unsigned int *) e2fsck_allocate_memory(ctx,
> @@ -259,11 +265,53 @@ redo_counts:
>  	for (i = B2C(fs->super->s_first_data_block);
>  	     i < ext2fs_blocks_count(fs->super);
>  	     i += EXT2FS_CLUSTER_RATIO(fs)) {
> +		int first_block_in_bg = (B2C(i) -
> +					 B2C(fs->super->s_first_data_block)) %
> +			fs->super->s_clusters_per_group == 0;
> +		int n, nbytes = fs->super->s_clusters_per_group / 8;
> +
>  		actual = ext2fs_fast_test_block_bitmap2(ctx->block_found_map, i);
>  
> +		/*
> +		 * Try to optimize pass5 by extracting a bitmap block
> +		 * as expected from what we have on disk, and then
> +		 * comparing the two.  If they are identical, then
> +		 * update the free block counts and go on to the next
> +		 * block group.  This is much faster than doing the
> +		 * individual bit-by-bit comparison.  The one downside
> +		 * is that this doesn't work if we are asking e2fsck
> +		 * to do a discard operation.
> +		 */
> +		if (!first_block_in_bg ||
> +		    (group == (int)fs->group_desc_count - 1) ||
> +		    (ctx->options & E2F_OPT_DISCARD))
> +			goto no_optimize;
> +
> +		retval = ext2fs_get_block_bitmap_range2(ctx->block_found_map,
> +				B2C(i), fs->super->s_clusters_per_group,
> +				actual_buf);
> +		if (retval)
> +			goto no_optimize;
> +		if (ext2fs_bg_flags_test(fs, group, EXT2_BG_BLOCK_UNINIT))
> +			memset(bitmap_buf, 0, nbytes);
> +		else {
> +			retval = ext2fs_get_block_bitmap_range2(fs->block_map,
> +					B2C(i), fs->super->s_clusters_per_group,
> +					bitmap_buf);
> +			if (retval)
> +				goto no_optimize;
> +		}
> +		if (memcmp(actual_buf, bitmap_buf, nbytes) != 0)
> +			goto no_optimize;
> +		n = ext2fs_bitcount(actual_buf, nbytes);
> +		group_free = fs->super->s_clusters_per_group - n;
> +		free_blocks += group_free;
> +		i += fs->super->s_clusters_per_group - 1;
> +		goto next_group;
> +	no_optimize:
> +
>  		if (skip_group) {
> -			if ((B2C(i) - B2C(fs->super->s_first_data_block)) %
> -			    fs->super->s_clusters_per_group == 0) {
> +			if (first_block_in_bg) {
>  				super_blk = 0;
>  				old_desc_blk = 0;
>  				new_desc_blk = 0;
> @@ -401,6 +449,7 @@ redo_counts:
>  			if (!bitmap && i >= first_free)
>  				e2fsck_discard_blocks(ctx, first_free,
>  						      (i - first_free) + 1);
> +		next_group:
>  			first_free = ext2fs_blocks_count(fs->super);
>  
>  			free_array[group] = group_free;
> @@ -475,6 +524,8 @@ redo_counts:
>  	}
>  errout:
>  	ext2fs_free_mem(&free_array);
> +	ext2fs_free_mem(&actual_buf);
> +	ext2fs_free_mem(&bitmap_buf);
>  }
>  
>  static void check_inode_bitmaps(e2fsck_t ctx)
> 
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html