Received-SPF: pass (google.com: best guess record for domain of linux-ext4-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
From:   Andreas Dilger <adilger@dilger.ca>
Message-Id: <EAD1A1FC-DCF5-4B2B-BDE9-38E593691E23@dilger.ca>
Content-Type: multipart/signed;
 boundary="Apple-Mail=_10416016-6F18-4F89-9D9B-DADE8F7C9A2E";
 protocol="application/pgp-signature"; micalg=pgp-sha256
Mime-Version: 1.0 (Mac OS X Mail 10.3 \(3273\))
Subject: Re: [PATCH 2/2] ext4: shrink directories on dentry delete
Date:   Thu, 26 Mar 2020 15:07:23 -0600
In-Reply-To: <CAD+ocbxt5E+v8=zWQGuAPwtJMe_Qa8q9BhP1es05unaQ50ckkQ@mail.gmail.com>
Cc:     linux-ext4 <linux-ext4@vger.kernel.org>
To:     harshad shirwadkar <harshadshirwadkar@gmail.com>
References: <20200325093728.204211-1-harshadshirwadkar@gmail.com>
 <20200325093728.204211-2-harshadshirwadkar@gmail.com>
 <04F44879-15DE-42EE-B87A-0690E9B13BB2@dilger.ca>
 <CAD+ocbxt5E+v8=zWQGuAPwtJMe_Qa8q9BhP1es05unaQ50ckkQ@mail.gmail.com>
Sender: linux-ext4-owner@vger.kernel.org
Precedence: bulk


--Apple-Mail=_10416016-6F18-4F89-9D9B-DADE8F7C9A2E
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=us-ascii

On Mar 26, 2020, at 1:49 PM, harshad shirwadkar =
<harshadshirwadkar@gmail.com> wrote:
>=20
> On Wed, Mar 25, 2020 at 3:06 AM Andreas Dilger <adilger@dilger.ca> =
wrote:
>>=20
>> On Mar 25, 2020, at 3:37 AM, Harshad Shirwadkar =
<harshadshirwadkar@gmail.com> wrote:
>>> But note that most of the shrinking happens during last 1-2% =
deletions
>>> in an average case. Therefore, the next step here is to merge dx =
nodes
>>> when possible. That can be achieved by storing the fullness index in
>>> htree nodes. But that's an on-disk format change. We can instead =
build
>>> on tooling added by this patch to perform reverse lookup on a dx
>>> node and then reading adjacent nodes to check their fullness.
>>=20
>> Thank you for updating these patches again.  I haven't had a chance =
to look
>> at them yet, but I hope to review the patches in the near future.
>>=20
>> As for storing the fullness on disk changing the on-disk format...  =
That is
>> true, but the original htree implementation anticipated this and =
reserved
>> space in the htree index to store the fullness, so it would not break =
the
>> ability of older kernels to access directories with the fullness =
information.
>>=20
> Yeah, you are right, good to know that we have bits reserved already
> and that wouldn't break older kernels if we use these in future.
>> I think if you used just a few bits (maybe just 2) to store:
>> 0 =3D unset (every directory today)
>> 1 =3D under 20% full
>> 2 =3D under 40% full
>> 3 =3D under 60% full
>>=20
>> or similar.  It doesn't matter if they are more full since they won't =
be
>> candidates for merging, and then lazily update the htree index =
fullness
>> as entries are removed, this will simplify the shrinking process, and =
will
>> avoid the need to repeatedly scan the leaf blocks to see if they are =
empty
>> enough for merging.  It wouldn't be any worse *not* to store these =
values
>> on disk after the first time a "0 =3D unset" entry was found and not =
merged,
>> or setting the fullness on the merged block if it is merged, and =
running
>> "e2fsck -D" can easily update the fullness values.
>>=20
>> The benefit of using 20%, 40%, and 60% as the fullness markers is =
that it
>> is possible to either merge adjacent 60% and 40% blocks or =
alternately a
>> 60% and two adjacent 20% blocks.  Also, since these values are very =
coarse
>> they would not need to be updated frequently.  If the values are =
slightly
>> outdated, then it is again not worse than the "always scan" model =
(one scan
>> and the fullness would be updated), but more efficient than repeat =
scanning.
>>=20
>> Using only two bits for fullness also leaves two bits free for future =
use.
>=20
> Thanks Andreas, that makes sense. This kind of merging will require
> lot of tooling provided in this patch - for example swapping out freed
> block with last block to not leave any holes. So, my hope is that we
> get this patch in first and thereby get a step closer to coalescing
> solution.

Definitely I *do not* want to block the landing of these initial patches
until a "full featured" directory shrinking is complete.  These patches
at least provide some basic functionality, and will at least shrink a
large directory if it becomes totally empty so I'm in favour of that.

Cheers, Andreas


--Apple-Mail=_10416016-6F18-4F89-9D9B-DADE8F7C9A2E
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+AFAl59GYwACgkQcqXauRfM
H+Dt+A//f7ZPz0S+KTgHIwMEEiVt0aRdnAxDajHVvJgKzrCG8xg5fk87vOVBTK5z
jmpnvyIwp/Srnrv18aGZ31u5LPCgqhGTrWSiMcETv/2vYFd3ZGLbkFc1whIW6DSA
wURdVQvgWI6ST3J8M2h+6YpA5N3vXBMcIJMhgRt89bN+/OEz0KfOPtnu5McDBNZV
G75nXo4yCD+8hAui/aFmP2y2M+Y4ywv33HyBdrw30bvvTZQBxDp/5HAUPN7kftd9
5R4YfchCXPiUpQGNPgYgJjyulZ0qIdtkCyiRN7gvmWrx7Wi6mIouBgDoNctusLL/
F1AxKOLlendy4A6atkN5UmwjY+TQS6oKyBxKMeKBHdrUahbid7esgfwTnWomYP7Q
CzDA+rg5SeA5WGo5mFN7y/+JmOQDALiNpBbDIeQgjsUEcGvepVvlpnCMPJYMs2ig
ae9eUeus8VqqjnmsGaAC/LN5B0AJyVLJGeXnY3fQsHOvsXlYOWE4oRDHRR0EjsHO
Ua448FkuBrqGt5J4d4vyxdl8W90z7WwHq+r9DdhqhWZnz0ksGHk1ACwTy3NlqxVl
KXfBXczubzZgIrB4Ar+xxOsQ/5Xl5whXwzXAnp69HiEZQ/d/TG2o161/LZvGuoLs
XsyHLEfUMglAykdXXffitbXpZniRAAVHMRbOD0rJq26FMfHqjck=
=5q8a
-----END PGP SIGNATURE-----

--Apple-Mail=_10416016-6F18-4F89-9D9B-DADE8F7C9A2E--