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

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 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:   Fri, 9 Sep 2022 11:42:39 +0530
From:   "Ritesh Harjani (IBM)" <ritesh.list@...il.com>
To:     Jan Kara <jack@...e.cz>
Cc:     Ted Tso <tytso@....edu>, linux-ext4@...r.kernel.org,
        Thorsten Leemhuis <regressions@...mhuis.info>,
        Ojaswin Mujoo <ojaswin@...ux.ibm.com>,
        Stefan Wahren <stefan.wahren@...e.com>,
        Harshad Shirwadkar <harshadshirwadkar@...il.com>,
        stable@...r.kernel.org
Subject: Re: [PATCH 5/5] ext4: Use buckets for cr 1 block scan instead of
 rbtree

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@...r.kernel.org
> Reported-and-tested-by: Stefan Wahren <stefan.wahren@...e.com>
> Tested-by: Ojaswin Mujoo <ojaswin@...ux.ibm.com>
> Signed-off-by: Jan Kara <jack@...e.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@...il.com>