Skip to content

btrfs: make lseek and fiemap much more efficient

[email protected] linux-btrfs 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 Latest10 patches 42 repliesIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/10btrfs: allow hole and data seeking to be interruptiblefs/btrfs/file.c+4 -02 replies
2/10btrfs: make hole and data seeking a lot more efficientfs/btrfs/file.c+406 -317 replies
3/10btrfs: remove check for impossible block start for an extent map at fiemapfs/btrfs/extent_io.c+1 -42 replies
4/10btrfs: remove zero length check when entering fiemapfs/btrfs/extent_io.c+0 -32 replies
5/10btrfs: properly flush delalloc when entering fiemapfs/btrfs/inode.c+20 -02 replies
6/10btrfs: allow fiemap to be interruptiblefs/btrfs/extent_io.c+5 -03 replies
7/10btrfs: rename btrfs_check_shared() to a more descriptive namefs/btrfs/backref.c fs/btrfs/backref.h fs/btrfs/extent_io.c+9 -82 replies
8/10btrfs: speedup checking for extent sharedness during fiemapfs/btrfs/backref.c fs/btrfs/backref.h fs/btrfs/ctree.h +2 more+170 -83 replies
9/10btrfs: skip unnecessary extent buffer sharedness checks during fiemapfs/btrfs/backref.c fs/btrfs/backref.h fs/btrfs/extent_io.c+38 -82 replies
10/10btrfs: make fiemap more efficient and accurate reporting extent sharednessfs/btrfs/ctree.h fs/btrfs/extent_io.c fs/btrfs/file.c +1 more+506 -3688 replies

Reviews trailers per patch

All 10 patches have a Reviewed-by or Acked-by.

PatchJosef BacikQu Wenruo
1/10R-b R-b
2/10R-b
3/10R-b R-b
4/10R-b R-b
5/10R-b R-b
6/10R-b R-b
7/10R-b R-b
8/10R-b
9/10R-b R-b
10/10R-b

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v1 thread

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

From: Filipe Manana <[email protected]>

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/[email protected]/
    https://lore.kernel.org/linux-btrfs/[email protected]/

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.

There are a few more things that can be done to speedup fiemap and lseek, but I'll leave those other optimizations I have in mind for some other time.

Filipe Manana (10):
btrfs: allow hole and data seeking to be interruptible
btrfs: make hole and data seeking a lot more efficient
btrfs: remove check for impossible block start for an extent map at fiemap
btrfs: remove zero length check when entering fiemap
btrfs: properly flush delalloc when entering fiemap
btrfs: allow fiemap to be interruptible
btrfs: rename btrfs_check_shared() to a more descriptive name
btrfs: speedup checking for extent sharedness during fiemap
btrfs: skip unnecessary extent buffer sharedness checks during fiemap
btrfs: make fiemap more efficient and accurate reporting extent sharedness

 fs/btrfs/backref.c     | 153 ++++++++-
 fs/btrfs/backref.h     |  20 +-
 fs/btrfs/ctree.h       |  22 +-
 fs/btrfs/extent-tree.c |  10 +-
 fs/btrfs/extent_io.c   | 703 ++++++++++++++++++++++++++++-------------
 fs/btrfs/file.c        | 439 +++++++++++++++++++++++--
 fs/btrfs/inode.c       | 146 ++-------
 7 files changed, 1111 insertions(+), 382 deletions(-)
Signature · 1 line
2.35.1