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: <04F44879-15DE-42EE-B87A-0690E9B13BB2@dilger.ca>
Content-Type: multipart/signed;
 boundary="Apple-Mail=_01895461-6364-4EFB-940F-A6D8C3D78409";
 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:   Wed, 25 Mar 2020 04:06:52 -0600
In-Reply-To: <20200325093728.204211-2-harshadshirwadkar@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>
Sender: linux-ext4-owner@vger.kernel.org
Precedence: bulk


--Apple-Mail=_01895461-6364-4EFB-940F-A6D8C3D78409
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=us-ascii

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.

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.

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.

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

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.

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.

Using only two bits for fullness also leaves two bits free for future =
use.

Cheers, Andreas


--Apple-Mail=_01895461-6364-4EFB-940F-A6D8C3D78409
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+AFAl57LT0ACgkQcqXauRfM
H+BuUBAAn8KVagRN08QANiqnAa9/6pTTlVRDQ9yq4eUqIaO+cXth9HMKnwpzQp+9
PY4duashMDWOeAaGXE9tW6MiMYlZaoINguECnrU1OZjwmTnJIfAIQEU2fzt0MoMb
l5IQKRQOBKQ7D/sslgzalQ0IOFaLLUlh9G6jEphX7FrpaKEe/qL7hEXb2HsGHHjj
q4lv4+x3Zr1iMlQyU1gJ572WOzfybyl0NfhJxRy6P2nE0VLo1fB5uGZVOLmG1aWG
KN9oYo3809fKcSm3pr7HNx/84mKyzHWCuW/Pz4IUqZR4gwnATQENmLqXCaJ7cgau
uNMU39XC+2MV6DsEgPvE46OPnmFX8FJddhKH+wE9X0oeDvRpOD8vPXFNGw+Uubw5
1FmraqRcRBGY3EJhTCyC9HGcwKg5cmb4k1LqcjfmCJMEfQEweRfUa0O0kbY0ml0f
aTtvTffMC0dY1B448nHcgdnJk8PUCQNx+tsDQucmZZqxCB1BpKLloIWnZ/avYe5z
Vid7BRcvSk3ahZmkAejnhf7kTH4NIbvixo7UGuAggamfIlwEtvzcVywVR0rjwheI
S3ACfMUcM3gzO/cTACOKU4aQio19ely6lwM/VYJgJV8Vmqe+iHnH0uvy0dGQ09Oh
hphMvLTWuznSmdA8BaTi5oofi1rVc7v7GxlZwFWsE7TOe8L6iY0=
=CMPI
-----END PGP SIGNATURE-----

--Apple-Mail=_01895461-6364-4EFB-940F-A6D8C3D78409--