[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-Id: <097F004D-AA61-4732-85BE-5CC3611B9B9A@dilger.ca>
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)
Powered by blists - more mailing lists