Re: [PATCH 00/10] btrfs: make lseek and fiemap much more efficient

[Filipe Manana <fdmanana@kernel.org>]

On Tue, Sep 06, 2022 at 06:20:06PM +0200, David Sterba wrote:
> On Thu, Sep 01, 2022 at 02:18:20PM +0100, fdmanana@kernel.org wrote:
> > From: Filipe Manana <fdmanana@suse.com>
> > 
> > We often get reports of fiemap and hole/data seeking (lseek) being too slow
> > on btrfs, or even unusable in some cases due to being extremely slow.
> > 
> > Some recent reports for fiemap:
> > 
> >     https://lore.kernel.org/linux-btrfs/21dd32c6-f1f9-f44a-466a-e18fdc6788a7@virtuozzo.com/
> >     https://lore.kernel.org/linux-btrfs/Ysace25wh5BbLd5f@atmark-techno.com/
> > 
> > For lseek (LSF/MM from 2017):
> > 
> >    https://lwn.net/Articles/718805/
> > 
> > Basically both are slow due to very high algorithmic complexity which
> > scales badly with the number of extents in a file and the heigth of
> > subvolume and extent b+trees.
> > 
> > Using Pavel's test case (first Link tag for fiemap), which uses files with
> > many 4K extents and holes before and after each extent (kind of a worst
> > case scenario), the speedup is of several orders of magnitude (for the 1G
> > file, from ~225 seconds down to ~0.1 seconds).
> > 
> > Finally the new algorithm for fiemap also ends up solving a bug with the
> > current algorithm. This happens because we are currently relying on extent
> > maps to report extents, which can be merged, and this may cause us to
> > report 2 different extents as a single one that is not shared but one of
> > them is shared (or the other way around). More details on this on patches
> > 9/10 and 10/10.
> > 
> > Patches 1/10 and 2/10 are for lseek, introducing some code that will later
> > be used by fiemap too (patch 10/10). More details in the changelogs.
> 
> The speedup is unbelievable, thank you very much!

I left something for cleanup in patch 10/10:

diff --git a/fs/btrfs/extent_io.c b/fs/btrfs/extent_io.c
index 50bb2182e795..62a643020e10 100644
--- a/fs/btrfs/extent_io.c
+++ b/fs/btrfs/extent_io.c
@@ -5408,14 +5408,12 @@ static int emit_fiemap_extent(struct fiemap_extent_info *fieinfo,
         *    So truly compressed (physical size smaller than logical size)
         *    extents won't get merged with each other
         *
-        * 3) Share same flags except FIEMAP_EXTENT_LAST
-        *    So regular extent won't get merged with prealloc extent
+        * 3) Share same flags
         */
        if (cache->offset + cache->len  == offset &&
            cache->phys + cache->len == phys  &&
            cache->flags == flags) {
                cache->len += len;
-               cache->flags |= flags;
                return 0;
        }
 

Can you fold this up to 10/10, or do you want to me resend or send separately?
Thanks.