Re: [PATCH 5/5] ext4: Use buckets for cr 1 block scan instead of rbtree

["Ritesh Harjani (IBM)" <ritesh.list@gmail.com>]

On 22/09/08 11:21AM, Jan Kara wrote:
> Using rbtree for sorting groups by average fragment size is relatively
> expensive (needs rbtree update on every block freeing or allocation) and
> leads to wide spreading of allocations because selection of block group
> is very sentitive both to changes in free space and amount of blocks
> allocated. Furthermore selecting group with the best matching average
> fragment size is not necessary anyway, even more so because the
> variability of fragment sizes within a group is likely large so average
> is not telling much. We just need a group with large enough average
> fragment size so that we have high probability of finding large enough
> free extent and we don't want average fragment size to be too big so
> that we are likely to find free extent only somewhat larger than what we
> need.
> 
> So instead of maintaing rbtree of groups sorted by fragment size keep
> bins (lists) or groups where average fragment size is in the interval
> [2^i, 2^(i+1)). This structure requires less updates on block allocation
> / freeing, generally avoids chaotic spreading of allocations into block
> groups, and still is able to quickly (even faster that the rbtree)
> provide a block group which is likely to have a suitably sized free
> space extent.
> 
> This patch reduces number of block groups used when untarring archive
> with medium sized files (size somewhat above 64k which is default
> mballoc limit for avoiding locality group preallocation) to about half
> and thus improves write speeds for eMMC flash significantly.
> 
> Fixes: 196e402adf2e ("ext4: improve cr 0 / cr 1 group scanning")
> CC: stable@vger.kernel.org
> Reported-and-tested-by: Stefan Wahren <stefan.wahren@i2se.com>
> Tested-by: Ojaswin Mujoo <ojaswin@linux.ibm.com>
> Signed-off-by: Jan Kara <jack@suse.cz>
> ---
>  fs/ext4/ext4.h    |  10 +-
>  fs/ext4/mballoc.c | 249 ++++++++++++++++++++--------------------------
>  fs/ext4/mballoc.h |   1 -
>  3 files changed, 111 insertions(+), 149 deletions(-)

Hello Jan, 

I have reviewed the patch and also verified bb_fragments. That indeed will 
atleast be 1 (ext4_mb_generate_buddy()) as you had mentioned.

The patch looks good to me. Please feel free to add: 
Reviewed-by: Ritesh Harjani (IBM) <ritesh.list@gmail.com>