linux-ext4 - Re: [PATCH 13/47] libext2fs: add a way to check the theoretical maximum extent tree depth

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: <20141214022357.GC29787@thunk.org>
Date:	Sat, 13 Dec 2014 21:23:57 -0500
From:	Theodore Ts'o <tytso@....edu>
To:	"Darrick J. Wong" <darrick.wong@...cle.com>
Cc:	linux-ext4@...r.kernel.org
Subject: Re: [PATCH 13/47] libext2fs: add a way to check the theoretical
 maximum extent tree depth

On Fri, Nov 07, 2014 at 01:52:12PM -0800, Darrick J. Wong wrote:
> Add an API so that client programs can discover a reasonable maximum
> extent tree depth.  This will eventually be used by e2fsck as one of
> the criteria to decide if an extent-based file should have its extent
> tree rebuilt.
> 
> +size_t ext2fs_max_extent_depth(ext2_extent_handle_t handle)
> +{
> +	size_t iblock_sz = sizeof(((struct ext2_inode *)NULL)->i_block);
> +	size_t iblock_extents = (iblock_sz - sizeof(struct ext3_extent_header)) /
> +				sizeof(struct ext3_extent);
> +	size_t extents_per_block = (handle->fs->blocksize -
> +				    sizeof(struct ext3_extent_header)) /
> +				   sizeof(struct ext3_extent);
> +
> +	return 1 + ((ul_log2(EXT_MAX_EXTENT_LBLK) - ul_log2(iblock_extents)) /
> +		    ul_log2(extents_per_block));
> +}
> +

This patch is only used by patch #33, and it gets called for every
single inode which is extent-mapped.

But if you look at the above code, there is nothing which is inode or
handle specific.  The value is only dependent on fs->blocksize.  But
to calculate this value the function calls ul_log2 three times, which
is implemented using a looping construct.  So we will be recalculating
what is effectively a constant value every single inode in an ext4
file system, which seems very unfortunate.

BTW, there are some ways we could accelerate the log2 function, and
I've considered implementing an ext2fs_log2_u32() and
ext2fs_log2_u64() using something like this:

int log2i(unsigned int x)
{
	if (!x)
		return 0;

	return sizeof(unsigned int) * 8 - __builtin_clz(x) - 1;
}

or

int log2u64(unsigned long long x)
{
	if (!x)
		return 0;

	return sizeof(unsigned long long) * 8 - __builtin_clzll(x) - 1;
}

or

int generic_log2(unsigned int x)
{
	int r = 0;

	if (x >= ((unsigned int)(1) << 16)) {
		r += 16;
		x >>= 16;
	}
	if (x >= ((unsigned int)(1) << 8)) {
		r += 8;
		x >>= 8;
	}
	if (x >= ((unsigned int)(1) << 4)) {
		r += 4;
		x >>= 4;
	}
	if (x >= ((unsigned int)(1) << 2)) {
		r += 2;
		x >>= 2;
	}
	if (x >= ((unsigned int)(1) << 1)) {
		r += 1;
		x >>= 1;
	}
	return r;
}

But it's not at all clear it's worth doing this because I haven't seen
any place in e2fsprogs where we really should be calculating an
integer log2 in a tight loop where performance should make a
difference.  If we are, we're probably doing something wrong....

	     	   	      	       	     	       - Ted
--
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