linux-ext4 - Re: [PATCH v4 5/6] ext4: improve cr 0 / cr 1 group scanning

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: Windows password security audit tool. GUI, reports in PDF.

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

Date:   Mon, 15 Mar 2021 14:56:53 -0600
From:   Andreas Dilger <adilger@...ger.ca>
To:     Harshad Shirwadkar <harshadshirwadkar@...il.com>
Cc:     Ext4 Developers List <linux-ext4@...r.kernel.org>,
        Theodore Ts'o <tytso@....edu>,
        kernel test robot <lkp@...el.com>,
        Dan Carpenter <dan.carpenter@...cle.com>,
        Благодаренко Артём 
        <artem.blagodarenko@...il.com>
Subject: Re: [PATCH v4 5/6] ext4: improve cr 0 / cr 1 group scanning

On Mar 15, 2021, at 11:37 AM, Harshad Shirwadkar <harshadshirwadkar@...il.com> wrote:
> 
> Instead of traversing through groups linearly, scan groups in specific
> orders at cr 0 and cr 1. At cr 0, we want to find groups that have the
> largest free order >= the order of the request. So, with this patch,
> we maintain lists for each possible order and insert each group into a
> list based on the largest free order in its buddy bitmap. During cr 0
> allocation, we traverse these lists in the increasing order of largest
> free orders. This allows us to find a group with the best available cr
> 0 match in constant time. If nothing can be found, we fallback to cr 1
> immediately.
> 
> At CR1, the story is slightly different. We want to traverse in the
> order of increasing average fragment size. For CR1, we maintain a rb
> tree of groupinfos which is sorted by average fragment size. Instead
> of traversing linearly, at CR1, we traverse in the order of increasing
> average fragment size, starting at the most optimal group. This brings
> down cr 1 search complexity to log(num groups).
> 
> For cr >= 2, we just perform the linear search as before. Also, in
> case of lock contention, we intermittently fallback to linear search
> even in CR 0 and CR 1 cases. This allows us to proceed during the
> allocation path even in case of high contention.
> 
> There is an opportunity to do optimization at CR2 too. That's because
> at CR2 we only consider groups where bb_free counter (number of free
> blocks) is greater than the request extent size. That's left as future
> work.
> 
> All the changes introduced in this patch are protected under a new
> mount option "mb_optimize_scan".
> 
> Signed-off-by: Harshad Shirwadkar <harshadshirwadkar@...il.com>
> Reported-by: kernel test robot <lkp@...el.com>
> Reported-by: Dan Carpenter <dan.carpenter@...cle.com>

Reviewed-by: Andreas Dilger <adilger@...ger.ca>

Cheers, Andreas






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