linux-ext4 - Re: [PATCH 09/12] libext2: optimize ext2fs_new

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 for Android: free password hash cracker in your pocket

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

Message-Id: <85FC5E41-56C5-43A4-8514-CEADC36FE5C3@dilger.ca>
Date:	Mon, 20 Jan 2014 14:52:43 -0700
From:	Andreas Dilger <adilger@...ger.ca>
To:	Theodore Ts'o <tytso@....edu>
Cc:	Ext4 Developers List <linux-ext4@...r.kernel.org>
Subject: Re: [PATCH 09/12] libext2: optimize ext2fs_new_block2()

On Jan 19, 2014, at 10:54 PM, Theodore Ts'o <tytso@....edu> wrote:
> If there are hundreds of thousands of blocks which are in use before
> the first free block, it is much, MUCH faster to use
> ext2fs_find_first_zero_block_bitmap2() instead of searching the
> allocation bitmap bit by bit.

Excellent.  The libext2fs block allocator has typically been unusable
for filesystems with allocated blocks, so it is good to see this.

This could be further improved by skipping full groups entirely, but
that doesn't detract from the benefits of this patch.

Cheers, Andreas

> Signed-off-by: "Theodore Ts'o" <tytso@....edu>
> ---
> lib/ext2fs/alloc.c | 34 +++++++++++++++++-----------------
> 1 file changed, 17 insertions(+), 17 deletions(-)
> 
> diff --git a/lib/ext2fs/alloc.c b/lib/ext2fs/alloc.c
> index 91637dd..7dcfd3c 100644
> --- a/lib/ext2fs/alloc.c
> +++ b/lib/ext2fs/alloc.c
> @@ -137,8 +137,8 @@ errcode_t ext2fs_new_inode(ext2_filsys fs, ext2_ino_t dir,
> errcode_t ext2fs_new_block2(ext2_filsys fs, blk64_t goal,
> 			   ext2fs_block_bitmap map, blk64_t *ret)
> {
> -	blk64_t	i;
> -	int	c_ratio;
> +	errcode_t retval;
> +	blk64_t	b;
> 
> 	EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
> 
> @@ -148,21 +148,21 @@ errcode_t ext2fs_new_block2(ext2_filsys fs, blk64_t goal,
> 		return EXT2_ET_NO_BLOCK_BITMAP;
> 	if (!goal || (goal >= ext2fs_blocks_count(fs->super)))
> 		goal = fs->super->s_first_data_block;
> -	i = goal;
> -	c_ratio = 1 << ext2fs_get_bitmap_granularity(map);
> -	if (c_ratio > 1)
> -		goal &= ~EXT2FS_CLUSTER_MASK(fs);
> -	do {
> -		if (!ext2fs_fast_test_block_bitmap2(map, i)) {
> -			clear_block_uninit(fs, ext2fs_group_of_blk2(fs, i));
> -			*ret = i;
> -			return 0;
> -		}
> -		i = (i + c_ratio) & ~(c_ratio - 1);
> -		if (i >= ext2fs_blocks_count(fs->super))
> -			i = fs->super->s_first_data_block;
> -	} while (i != goal);
> -	return EXT2_ET_BLOCK_ALLOC_FAIL;
> +	goal &= ~EXT2FS_CLUSTER_MASK(fs);
> +
> +	retval = ext2fs_find_first_zero_block_bitmap2(map,
> +			goal, ext2fs_blocks_count(fs->super) - 1, &b);
> +	if ((retval == ENOENT) && (goal != fs->super->s_first_data_block))
> +		retval = ext2fs_find_first_zero_block_bitmap2(map,
> +			fs->super->s_first_data_block, goal - 1, &b);
> +	if (retval == ENOENT)
> +		return EXT2_ET_BLOCK_ALLOC_FAIL;
> +	if (retval)
> +		return retval;
> +
> +	clear_block_uninit(fs, ext2fs_group_of_blk2(fs, b));
> +	*ret = b;
> +	return 0;
> }
> 
> errcode_t ext2fs_new_block(ext2_filsys fs, blk_t goal,
> -- 
> 1.8.5.rc3.362.gdf10213
> 
> --
> 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


Cheers, Andreas






Download attachment "signature.asc" of type "application/pgp-signature" (834 bytes)