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;
MIME-Version: 1.0
References: <20200325093728.204211-1-harshadshirwadkar@gmail.com>
 <20200325093728.204211-2-harshadshirwadkar@gmail.com> <04F44879-15DE-42EE-B87A-0690E9B13BB2@dilger.ca>
In-Reply-To: <04F44879-15DE-42EE-B87A-0690E9B13BB2@dilger.ca>
From:   harshad shirwadkar <harshadshirwadkar@gmail.com>
Date:   Thu, 26 Mar 2020 12:49:35 -0700
Message-ID: <CAD+ocbxt5E+v8=zWQGuAPwtJMe_Qa8q9BhP1es05unaQ50ckkQ@mail.gmail.com>
Subject: Re: [PATCH 2/2] ext4: shrink directories on dentry delete
To:     Andreas Dilger <adilger@dilger.ca>
Cc:     linux-ext4 <linux-ext4@vger.kernel.org>
Content-Type: text/plain; charset="UTF-8"
Sender: linux-ext4-owner@vger.kernel.org
Precedence: bulk

On Wed, Mar 25, 2020 at 3:06 AM Andreas Dilger <adilger@dilger.ca> wrote:
>
> 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.
>
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 = unset (every directory today)
> 1 = under 20% full
> 2 = under 40% full
> 3 = 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 = 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.

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.

Thanks,
Harshad
>
> Cheers, Andreas
>
>
>
>
>