linux-btrfs.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH 00/10] btrfs: make lseek and fiemap much more efficient
@ 2022-09-01 13:18 fdmanana
  2022-09-01 13:18 ` [PATCH 01/10] btrfs: allow hole and data seeking to be interruptible fdmanana
                   ` (12 more replies)
  0 siblings, 13 replies; 53+ messages in thread
From: fdmanana @ 2022-09-01 13:18 UTC (permalink / raw)
  To: linux-btrfs

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.

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(-)

-- 
2.35.1


^ permalink raw reply	[flat|nested] 53+ messages in thread

end of thread, other threads:[~2022-09-12  8:38 UTC | newest]

Thread overview: 53+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2022-09-01 13:18 [PATCH 00/10] btrfs: make lseek and fiemap much more efficient fdmanana
2022-09-01 13:18 ` [PATCH 01/10] btrfs: allow hole and data seeking to be interruptible fdmanana
2022-09-01 13:58   ` Josef Bacik
2022-09-01 21:49   ` Qu Wenruo
2022-09-01 13:18 ` [PATCH 02/10] btrfs: make hole and data seeking a lot more efficient fdmanana
2022-09-01 14:03   ` Josef Bacik
2022-09-01 15:00     ` Filipe Manana
2022-09-02 13:26       ` Josef Bacik
2022-09-01 22:18   ` Qu Wenruo
2022-09-02  8:36     ` Filipe Manana
2022-09-11 22:12   ` Qu Wenruo
2022-09-12  8:38     ` Filipe Manana
2022-09-01 13:18 ` [PATCH 03/10] btrfs: remove check for impossible block start for an extent map at fiemap fdmanana
2022-09-01 14:03   ` Josef Bacik
2022-09-01 22:19   ` Qu Wenruo
2022-09-01 13:18 ` [PATCH 04/10] btrfs: remove zero length check when entering fiemap fdmanana
2022-09-01 14:04   ` Josef Bacik
2022-09-01 22:24   ` Qu Wenruo
2022-09-01 13:18 ` [PATCH 05/10] btrfs: properly flush delalloc " fdmanana
2022-09-01 14:06   ` Josef Bacik
2022-09-01 22:38   ` Qu Wenruo
2022-09-01 13:18 ` [PATCH 06/10] btrfs: allow fiemap to be interruptible fdmanana
2022-09-01 14:07   ` Josef Bacik
2022-09-01 22:42   ` Qu Wenruo
2022-09-02  8:38     ` Filipe Manana
2022-09-01 13:18 ` [PATCH 07/10] btrfs: rename btrfs_check_shared() to a more descriptive name fdmanana
2022-09-01 14:08   ` Josef Bacik
2022-09-01 22:45   ` Qu Wenruo
2022-09-01 13:18 ` [PATCH 08/10] btrfs: speedup checking for extent sharedness during fiemap fdmanana
2022-09-01 14:23   ` Josef Bacik
2022-09-01 22:50   ` Qu Wenruo
2022-09-02  8:46     ` Filipe Manana
2022-09-01 13:18 ` [PATCH 09/10] btrfs: skip unnecessary extent buffer sharedness checks " fdmanana
2022-09-01 14:26   ` Josef Bacik
2022-09-01 23:01   ` Qu Wenruo
2022-09-01 13:18 ` [PATCH 10/10] btrfs: make fiemap more efficient and accurate reporting extent sharedness fdmanana
2022-09-01 14:35   ` Josef Bacik
2022-09-01 15:04     ` Filipe Manana
2022-09-02 13:25       ` Josef Bacik
2022-09-01 23:27   ` Qu Wenruo
2022-09-02  8:59     ` Filipe Manana
2022-09-02  9:34       ` Qu Wenruo
2022-09-02  9:41         ` Filipe Manana
2022-09-02  9:50           ` Qu Wenruo
2022-09-02  0:53 ` [PATCH 00/10] btrfs: make lseek and fiemap much more efficient Wang Yugui
2022-09-02  8:24   ` Filipe Manana
2022-09-02 11:41     ` Wang Yugui
2022-09-02 11:45     ` Filipe Manana
2022-09-05 14:39       ` Filipe Manana
2022-09-06 16:20 ` David Sterba
2022-09-06 17:13   ` Filipe Manana
2022-09-07  9:12 ` Christoph Hellwig
2022-09-07  9:47   ` Filipe Manana

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).