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: <C2D84F9E-374E-4B3C-8E2E-30A7CD5A0A0C@dilger.ca>
Content-Type: multipart/signed;
 boundary="Apple-Mail=_4A375A78-71CC-44FF-B87E-660AABFACABB";
 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:   Sat, 28 Mar 2020 18:01:05 -0600
In-Reply-To: <20200325093728.204211-2-harshadshirwadkar@gmail.com>
Cc:     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=_4A375A78-71CC-44FF-B87E-660AABFACABB
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:
>=20
> This patch adds shrinking support for htree based directories. The
> high level algorithm is as follows:
>=20
> * If after dentry removal the dirent block (let's call it B) becomes
>  empty, then remove its references in its dx parent.
> * Swap its contents with that of the last block (L) in directory.
> * Update L's parents to point to B instead.
> * Remove L
> * Repeat this for all the ancestors of B.
>=20
> We add variants of dx_probe that allow us perform reverse lookups from
> a logical block to its dx parents.
>=20
> Ran kvm-xfstests smoke and verified that no new failures are
> introduced. Ran shrinking for directories with following number of
> files and then deleted files one by one:
> * 1000 (size before deletion 36K, after deletion 4K)
> * 10000 (size before deletion 196K, after deletion 4K)
> * 100000 (size before deletion 2.1M, after deletion 4K)
> * 200000 (size before deletion 4.2M, after deletion 4K)
>=20
> In all cases directory shrunk significantly. We fallback to linear
> directories if the directory becomes empty.
>=20
> 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
> This patch supersedes the other directory shrinking patch sent in Aug
> 2019 ("ext4: attempt to shrink directory on dentry removal").
>=20
> Signed-off-by: Harshad Shirwadkar <harshadshirwadkar@gmail.com>
> ---
> fs/ext4/ext4_jbd2.h |   7 +
> fs/ext4/namei.c     | 355 ++++++++++++++++++++++++++++++++++++++++++--
> 2 files changed, 353 insertions(+), 9 deletions(-)
>=20
> diff --git a/fs/ext4/namei.c b/fs/ext4/namei.c
> index d567b9589875..b78c6f9a6eba 100644
> --- a/fs/ext4/namei.c
> +++ b/fs/ext4/namei.c
>=20
> +/*
> + * dx_probe with relaxed checks. This function is used in the =
directory
> + * shrinking code since we can run into intermediate states where we =
have
> + * internal dx nodes with count =3D 0.
> + */
> +static inline struct dx_frame *
> +dx_probe_relaxed(struct ext4_filename *fname, struct inode *dir,
> +		struct dx_hash_info *hinfo, struct dx_frame *frame_in)
> +{
> +	return __dx_probe(fname, dir, hinfo, frame_in, 0, false);
> +}
> +
> +/*
> + * Perform only a parttial dx_probe until we find block end_lblk.

(typo) "partial"

> +static inline struct dx_frame *
> +dx_probe_partial(struct ext4_filename *fname, struct inode *dir,
> +		 struct dx_hash_info *hinfo, struct dx_frame *frame_in,
> +		 ext4_lblk_t end_lblk)
> +{
> +	return __dx_probe(fname, dir, hinfo, frame_in, end_lblk, false);
> +}
> +
[snip]
> +/*
> + * This function tries to remove the entry of a dirent block (which =
was just
> + * emptied by the caller) from the dx frame. It does so by reducing =
the count by
> + * 1 and left shifting all the entries after the deleted entry.
> + */
> +int
> +ext4_remove_dx_entry(handle_t *handle, struct inode *dir,
> +		     struct dx_frame *dx_frame)
> +{
> +	err =3D ext4_journal_get_write_access(handle, dx_frame->bh);
> +	if (err) {
> +		ext4_std_error(dir->i_sb, err);
> +		return -EINVAL;
> +	}
> +
> +	for (; i < count - 1; i++)
> +		entries[i] =3D entries[i + 1];

It would be more efficient to do this with "memmove()" rather than =
copying
each entry separately.

> +	/*
> +	 * If i was 0 when we began above loop, we would have =
overwritten count
> +	 * and limit values since those values live in dx_entry->hash of =
the
> +	 * first entry. We need to update count but we should set limit =
as well.
> +	 */
> +	dx_set_count(entries, count - 1);
> +	dx_set_limit(entries, limit);

How hard is it to avoid clobbering these fields in the first place?
I'm just thinking that "clobber + fixup" is subject to race conditions
at various times in the past, and may become an issue in the future
(e.g. with parallel directory operations).

> static inline bool is_empty_dirent_block(struct inode *dir,
> +					 struct buffer_head *bh)
> +{

This should be combined with ext4_empty_dir() to avoid code duplication.

> +	struct ext4_dir_entry_2 *de =3D (struct ext4_dir_entry_2 =
*)bh->b_data;
> +	int	csum_size =3D 0;
> +
> +	if (ext4_has_metadata_csum(dir->i_sb) && is_dx(dir))
> +		csum_size =3D sizeof(struct ext4_dir_entry_tail);
> +
> +	return ext4_rec_len_from_disk(de->rec_len, =
dir->i_sb->s_blocksize) =3D=3D
> +			dir->i_sb->s_blocksize - csum_size && de->inode =
=3D=3D 0;
> +}

This looks like a low cost way to determine the leaf block is empty,
but checking this for every unlink likely has a non-zero cost.

> @@ -2530,6 +2864,9 @@ static int ext4_delete_entry(handle_t *handle,
> 	if (unlikely(err))
> 		goto out;
>=20
> +	if (is_dx(dir))
> +		ext4_try_dir_shrink(handle, dir, lblk, bh);
> +
> 	return 0;

It would be useful to run a comparison benchmark between the patched =
ext4
and unpatched when deleting a large number of entries that checks both =
CPU
usage and performance.  That will give us an idea of how much this costs
to be checked for every entry.

Also, rather than calling ext4_try_dir_shrink() and =
is_empty_dirent_block()
for every entry, couldn't this be returned from =
ext4_generic_delete_entry(),
since it has that information already.

Cheers, Andreas


--Apple-Mail=_4A375A78-71CC-44FF-B87E-660AABFACABB
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+AFAl5/5UEACgkQcqXauRfM
H+CPcRAAs5paI4YWetY8z5M7c7JvjEkvlpAv5A9GVmzVIwUZ6NXnhyjGbC1g24mt
sURpZucW2bUszfmjNZicR4dsMmj/iKfkxY5euh3NBTv1tvL7rV1CLmKMPoIKE7So
3LsHzqzQZERQvwc+X5PcVwSP6U2DS0HqMqKxO4bbUnJIsS2ePuypUpyIBRyZn42J
g82YY36/yrJbZ95gTGqNa9JJz4OFrycglqkg7+fMjXHZNEy5p7K8uDvBiv/9eaaO
UiA7JufKf2xFwf+rEPEyPHunCGk0pbg3wH7tA8D1QHea2Pign9TTf3EFPMY0J89T
cL4nnsKmfTw4mbChTOFWhepAuu9sJ8lQ2cHxOuWyW6EdbO2ExV8P8TkmbrbzknYl
0t3CVzNUZ7q5Wk8GfpEmLA/ZrAq5tJPXhxhV6H4thyjbASh+42HEYb0xcnoNr1iJ
rCcJfidw5F4WG0N2p+965ADbjchT+bC2IbABiM+2VMeSRyhyutFbKEIWPwYfkJgj
3gAEcZjgM+0Y6rAMdm13Plone1cHX3NH/f161tLYR8Lk/FOAjGJhrsqhivOpcjas
3CHttv/0eBkbHalRWL5BScqDsLusA4Pmd6ER5K9itQIxN2XzJ5TXkxekBT312LgN
pM739MlP4g42ywQn9DQsSTrDoxookDknCblF5YotZWOsB7vePMo=
=KC7q
-----END PGP SIGNATURE-----

--Apple-Mail=_4A375A78-71CC-44FF-B87E-660AABFACABB--