btrfs: make lseek and fiemap much more efficient
Get series with b4
b4 am [email protected]Versions newest first
- v1 Latest10 patches 42 repliesIn review
Patches in v1 No applies recorded yet
Reviews trailers per patch
All 10 patches have a Reviewed-by or Acked-by.
| Patch | Josef Bacik | Qu Wenruo |
|---|---|---|
| 1/10 | R-b | R-b |
| 2/10 | R-b | |
| 3/10 | R-b | R-b |
| 4/10 | R-b | R-b |
| 5/10 | R-b | R-b |
| 6/10 | R-b | R-b |
| 7/10 | R-b | R-b |
| 8/10 | R-b | |
| 9/10 | R-b | R-b |
| 10/10 | R-b |
Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.
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