Received-SPF: pass (google.com: domain of linux-ext4-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18;
From:   Andreas Dilger <adilger@dilger.ca>
Message-Id: <097F004D-AA61-4732-85BE-5CC3611B9B9A@dilger.ca>
Content-Type: multipart/signed;
 boundary="Apple-Mail=_8C826B41-FC7F-4492-99B5-49F369B87E46";
 protocol="application/pgp-signature"; micalg=pgp-sha256
Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\))
Subject: Re: [PATCH v4 5/6] ext4: improve cr 0 / cr 1 group scanning
Date:   Mon, 15 Mar 2021 14:56:53 -0600
In-Reply-To: <20210315173716.360726-6-harshadshirwadkar@gmail.com>
Cc:     Ext4 Developers List <linux-ext4@vger.kernel.org>,
        Theodore Ts'o <tytso@mit.edu>,
        kernel test robot <lkp@intel.com>,
        Dan Carpenter <dan.carpenter@oracle.com>,
        =?utf-8?B?0JHQu9Cw0LPQvtC00LDRgNC10L3QutC+INCQ0YDRgtGR0Lw=?= 
        <artem.blagodarenko@gmail.com>
To:     Harshad Shirwadkar <harshadshirwadkar@gmail.com>
References: <20210315173716.360726-1-harshadshirwadkar@gmail.com>
 <20210315173716.360726-6-harshadshirwadkar@gmail.com>
Precedence: bulk


--Apple-Mail=_8C826B41-FC7F-4492-99B5-49F369B87E46
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=us-ascii

On Mar 15, 2021, at 11:37 AM, Harshad Shirwadkar =
<harshadshirwadkar@gmail.com> wrote:
>=20
> 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 >=3D 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.
>=20
> 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).
>=20
> For cr >=3D 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.
>=20
> 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.
>=20
> All the changes introduced in this patch are protected under a new
> mount option "mb_optimize_scan".
>=20
> Signed-off-by: Harshad Shirwadkar <harshadshirwadkar@gmail.com>
> Reported-by: kernel test robot <lkp@intel.com>
> Reported-by: Dan Carpenter <dan.carpenter@oracle.com>

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

Cheers, Andreas


--Apple-Mail=_8C826B41-FC7F-4492-99B5-49F369B87E46
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
	filename=signature.asc
Content-Type: application/pgp-signature;
	name=signature.asc
Content-Description: Message signed with OpenPGP

-----BEGIN PGP SIGNATURE-----
Comment: GPGTools - http://gpgtools.org

iQIzBAEBCAAdFiEEDb73u6ZejP5ZMprvcqXauRfMH+AFAmBPyhYACgkQcqXauRfM
H+DUmRAAkFJcjahASN4B4WS33yDLIpldOKai+I79pTMKLyE5gkKMQA6uGukZ0yzG
HyVc6h/Wi+Hm4j9zJ8aaWpR8Xu6Qv57d7RBdEt0ap/ppinw0B7qzrat1QM4mbGRr
VOCyg/gOj3aL6VonOzCMv8jWhtfilRpS7JwyHLq+5rcKEb9HYfrChG4sUHMXvyn5
oPUmHoRGMuNatfY8yalo1AFE3X22/MVUNDN8vJKPbW356TuxTkEOmJuZrXzkaumR
NacrcWZuTVL/g3o7Yl0fvxmq9NBZKVG7CHGSfOsOyyconybTY403EQJ/RvRo9+XU
YSqnUU57qVyK4eOyIhpVMdEQe4mIzU1PzY8qoib9HxSeP4Th5CBfRIONGN6X5tkX
8iRPg8duzZGsLYfIaqFXeEPAbUqcnnIorJvENjJlbw5kv54LwhdVDa8AYMAGW8hE
76bLaQyAboUwvnUfhFJVHD9M4WKOCPXmreFk9V7N0lvAz+3qAljl34OOJhOw3U0X
Yj3lgIGNRVzIx8sEzE3nZWW3AgG4C49i6+D1Dr1wPQrEtgwMt5UGowSvFAn610iL
+6jEuyR6gOyCn7JV75Wxqg7wdoVgyDHBXwFqcfx/jmBbYh6dZMO7p+eUIQJ02zJP
t8596G1WuY9dBK8cbGKPhfq1YRfs8ahq5BK1fo7yjnkMsnfPwjs=
=Tsfp
-----END PGP SIGNATURE-----

--Apple-Mail=_8C826B41-FC7F-4492-99B5-49F369B87E46--