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@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
