Skip to content

btrfs: qgroup: Use backref cache based backref walk for commit roots

Qu Wenruo linux-btrfs 2 versions – In review

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v2 Latest39 patches 12 repliesIn review
  2. v140 patches 1 replySuperseded

Changes in v2 from the cover letter

- Rebased to misc-next branch
- Add new reviewed-by tags from v1.

Patches in v2 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/39btrfs: backref: Introduce the skeleton of btrfs_backref_iterfs/btrfs/backref.c fs/btrfs/backref.h+149 -04 replies
2/39btrfs: backref: Implement btrfs_backref_iter_next()fs/btrfs/backref.c fs/btrfs/backref.h+92 -00 replies
3/39btrfs: relocation: Use btrfs_backref_iter infrastructurefs/btrfs/relocation.c+61 -1290 replies
4/39btrfs: relocation: Rename mark_block_processed() and __mark_block_processed()fs/btrfs/relocation.c+22 -340 replies
5/39btrfs: relocation: Add backref_cache::pending_edge and backref_cache::useless_node membersfs/btrfs/relocation.c+46 -280 replies
6/39btrfs: relocation: Add backref_cache::fs_info memberfs/btrfs/relocation.c+6 -20 replies
7/39btrfs: relocation: Make reloc root search specific for relocation backref cachefs/btrfs/ctree.h fs/btrfs/relocation.c+41 -110 replies
8/39btrfs: relocation: Refactor direct tree backref processing into its own functionfs/btrfs/relocation.c+79 -520 replies
9/39btrfs: relocation: Refactor indirect tree backref processing into its own functionfs/btrfs/relocation.c+159 -1350 replies
10/39btrfs: relocation: Use wrapper to replace open-coded edge linkingfs/btrfs/relocation.c+37 -160 replies
11/39btrfs: relocation: Specify essential members for alloc_backref_node()fs/btrfs/relocation.c+19 -200 replies
12/39btrfs: relocation: Remove the open-coded goto loop for breadth-first searchfs/btrfs/relocation.c+88 -800 replies
13/39btrfs: relocation: Refactor the finishing part of upper linkage into finish_upper_links()fs/btrfs/relocation.c+117 -690 replies
14/39btrfs: relocation: Refactor the useless nodes handling into its own functionfs/btrfs/relocation.c+75 -370 replies
15/39btrfs: relocation: Add btrfs_ prefix for backref_node/edge/cachefs/btrfs/relocation.c+143 -1390 replies
16/39btrfs: Move btrfs_backref_(node|edge|cache) structures to backref.hfs/btrfs/backref.h fs/btrfs/relocation.c+119 -1130 replies
17/39btrfs: Rename tree_entry to simple_node and export itfs/btrfs/backref.h fs/btrfs/misc.h fs/btrfs/relocation.c+90 -795 replies
18/39btrfs: Rename backref_cache_init() to btrfs_backref_cache_init() and move it to backref.cfs/btrfs/backref.c fs/btrfs/backref.h fs/btrfs/relocation.c+20 -170 replies
19/39btrfs: Rename alloc_backref_node() to btrfs_backref_alloc_node() and move it backref.cfs/btrfs/backref.c fs/btrfs/backref.h fs/btrfs/relocation.c+28 -250 replies
20/39btrfs: Rename alloc_backref_edge() to btrfs_backref_alloc_edge() and move it backref.cfs/btrfs/backref.c fs/btrfs/backref.h fs/btrfs/relocation.c+16 -140 replies
21/39btrfs: Rename link_backref_edge() to btrfs_backref_link_edge() and move it backref.hfs/btrfs/backref.h fs/btrfs/relocation.c+20 -190 replies
22/39btrfs: Rename free_backref_(node|edge) to btrfs_backref_free_(node|edge) and move them to backref.hfs/btrfs/backref.h fs/btrfs/relocation.c+31 -310 replies
23/39btrfs: Rename drop_backref_node() to btrfs_backref_drop_node() and move its needed facilities to backref.hfs/btrfs/backref.h fs/btrfs/relocation.c+46 -380 replies
24/39btrfs: Rename remove_backref_node() to btrfs_backref_cleanup_node() and move it to backref.cfs/btrfs/backref.c fs/btrfs/backref.h fs/btrfs/relocation.c+52 -480 replies
25/39btrfs: Rename backref_cache_cleanup() to btrfs_backref_release_cache() and move it to backref.cfs/btrfs/backref.c fs/btrfs/backref.h fs/btrfs/relocation.c+34 -310 replies
26/39btrfs: Rename backref_tree_panic() to btrfs_backref_panic(), and move it to backref.cfs/btrfs/backref.h fs/btrfs/relocation.c+18 -200 replies
27/39btrfs: Rename should_ignore_root() to btrfs_should_ignore_reloc_root() and export itfs/btrfs/ctree.h fs/btrfs/relocation.c+7 -40 replies
28/39btrfs: relocation: Open-code read_fs_root() for handle_indirect_tree_backref()fs/btrfs/relocation.c+5 -10 replies
29/39btrfs: Rename handle_one_tree_block() to btrfs_backref_add_tree_node() and move it to backref.cfs/btrfs/backref.c fs/btrfs/backref.h fs/btrfs/relocation.c+373 -3560 replies
30/39btrfs: Rename finish_upper_links() to btrfs_backref_finish_upper_links() and move it to backref.cfs/btrfs/backref.c fs/btrfs/backref.h fs/btrfs/relocation.c+108 -1150 replies
31/39btrfs: relocation: Move error handling of build_backref_tree() to backref.cfs/btrfs/backref.c fs/btrfs/backref.h fs/btrfs/relocation.c+58 -470 replies
32/39btrfs: backref: Only ignore reloc roots for indrect backref resolve if the backref cache is for reloction purposefs/btrfs/backref.c+14 -20 replies
33/39btrfs: qgroup: Introduce qgroup backref cachefs/btrfs/ctree.h fs/btrfs/disk-io.c fs/btrfs/qgroup.c+56 -00 replies
34/39btrfs: qgroup: Introduce qgroup_backref_cache_build() functionfs/btrfs/qgroup.c+154 -00 replies
35/39btrfs: qgroup: Introduce a function to iterate through backref_cache to find all parents for specified nodefs/btrfs/qgroup.c+40 -00 replies
36/39btrfs: qgroup: Introduce helpers to get needed tree block infofs/btrfs/qgroup.c+66 -00 replies
37/39btrfs: qgroup: Introduce verification for function to ensure old roots ulist matches btrfs_find_all_roots() resultfs/btrfs/qgroup.c+72 -00 replies
38/39btrfs: qgroup: Introduce a new function to get old_roots ulist using backref cachefs/btrfs/qgroup.c+109 -00 replies
39/39btrfs: qgroup: Use backref cache to speed up old_roots searchfs/btrfs/qgroup.c+12 -100 replies

Reviews trailers per patch

14 of 39 patches have a Reviewed-by or Acked-by.

PatchJohannes ThumshirnJosef BacikNikolay Borisov
1/39R-b R-b
2/39R-b R-b
3/39R-b R-b
4/39R-b R-b
5/39R-b
6/39R-b
7/39R-b
8/39R-b
9/39R-b
10/39R-b R-b
11/39R-b R-b
12/39R-b
13/39R-b
14/39R-b
15/39
16/39
17/39
18/39
19/39
20/39
21/39
22/39
23/39
24/39
25/39
26/39
27/39
28/39
29/39
30/39
31/39
32/39
33/39
34/39
35/39
36/39
37/39
38/39
39/39

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes. Scroll the table sideways for all 3 reviewers.

Read the v2 thread

Cover letter [PATCH v2 00/39] btrfs: qgroup: Use backref cache based backref walk for commit roots

This patchset is based on misc-5.7 branch.

The branch can be fetched from github for review/testing.
https://github.com/adam900710/linux/tree/backref_cache_all

The patchset survives all the existing qgroup/volume/replace/balance tests.

=== BACKGROUND ===
One of the biggest problem for qgroup is its performance impact. Although we have improved it in since v5.0 kernel, there is still something slowing down qgroup, the backref walk.

Before this patchset, we use btrfs_find_all_roots() to iterate all roots referring to one extent.
That function is doing a pretty good job, but it doesn't has any cache, which means even we're looking up the same extent, we still need to do the full backref walk.

On the other hand, relocation is doing its own backref cache, and provides a much faster backref walk.

So the patchset is mostly trying to make qgroup backref walk (at least commit root backref walk) to use the same mechanism provided by relocation.

=== BENCHMARK ===
For the performance improvement, the last patch has a benchmark. The following content is completely copied from that patch:
------
Here is a small script to test it:

mkfs.btrfs -f $dev
mount $dev -o space_cache=v2 $mnt

btrfs subvolume create $mnt/src

  for ((i = 0; i < 64; i++)); do
          for (( j = 0; j < 16; j++)); do
                  xfs_io -f -c "pwrite 0 2k" $mnt/src/file_inline_$(($i * 16 + $j)) > /dev/null
          done
          xfs_io -f -c "pwrite 0 1M" $mnt/src/file_reg_$i > /dev/null
          sync
          btrfs subvol snapshot $mnt/src $mnt/snapshot_$i
  done
  sync

btrfs quota enable $mnt
btrfs quota rescan -w $mnt

Here is the benchmark for above small tests.
The performance material is the total execution time of get_old_roots() for patched kernel (*), and find_all_roots() for original kernel.

*: With CONFIG_BTRFS_FS_CHECK_INTEGRITY disabled, as get_old_roots()
will call find_all_roots() to verify the result if that config is enabled.

| Number of calls | Total exec time |
------------------------------------------------------

find_all_roots()|  732		   | 529991034ns
get_old_roots() |  732		   | 127998312ns

------------------------------------------------------
diff | 0.00 % | -75.8 %
------

=== PATCHSET STRUCTURE ===
Patch 01~14 are refactors of relocation backref. Patch 15~31 are code move.
Patch 32 is the patch that is already in misc-next. Patch 33 is the final preparation for qgroup backref. Patch 34~40 are the qgroup backref cache implementation.

=== CHANGELOG ===
v1:
- Use btrfs_backref_ prefix for exported structure/function
- Add one extra patch to rename backref_(node/edge/cache) The renaming itself is not small, thus better to do the rename first then move them to backref.[ch].
- Add extra Reviewed-by tags.

v2:
- Rebased to misc-next branch
- Add new reviewed-by tags from v1.

Qu Wenruo (39):
btrfs: backref: Introduce the skeleton of btrfs_backref_iter
btrfs: backref: Implement btrfs_backref_iter_next()
btrfs: relocation: Use btrfs_backref_iter infrastructure
btrfs: relocation: Rename mark_block_processed() and
__mark_block_processed()
btrfs: relocation: Add backref_cache::pending_edge and
backref_cache::useless_node members
btrfs: relocation: Add backref_cache::fs_info member
btrfs: relocation: Make reloc root search specific for relocation
backref cache
btrfs: relocation: Refactor direct tree backref processing into its
own function
btrfs: relocation: Refactor indirect tree backref processing into its
own function
btrfs: relocation: Use wrapper to replace open-coded edge linking
btrfs: relocation: Specify essential members for alloc_backref_node()
btrfs: relocation: Remove the open-coded goto loop for breadth-first
search
btrfs: relocation: Refactor the finishing part of upper linkage into
finish_upper_links()
btrfs: relocation: Refactor the useless nodes handling into its own
function
btrfs: relocation: Add btrfs_ prefix for backref_node/edge/cache
btrfs: Move btrfs_backref_(node|edge|cache) structures to backref.h
btrfs: Rename tree_entry to simple_node and export it
btrfs: Rename backref_cache_init() to btrfs_backref_cache_init() and
move it to backref.c
btrfs: Rename alloc_backref_node() to btrfs_backref_alloc_node() and
move it backref.c
btrfs: Rename alloc_backref_edge() to btrfs_backref_alloc_edge() and
move it backref.c
btrfs: Rename link_backref_edge() to btrfs_backref_link_edge() and
move it backref.h
btrfs: Rename free_backref_(node|edge) to
btrfs_backref_free_(node|edge) and move them to backref.h
btrfs: Rename drop_backref_node() to btrfs_backref_drop_node() and
move its needed facilities to backref.h
btrfs: Rename remove_backref_node() to btrfs_backref_cleanup_node()
and move it to backref.c
btrfs: Rename backref_cache_cleanup() to btrfs_backref_release_cache()
and move it to backref.c
btrfs: Rename backref_tree_panic() to btrfs_backref_panic(), and move
it to backref.c
btrfs: Rename should_ignore_root() to btrfs_should_ignore_reloc_root()
and export it
btrfs: relocation: Open-code read_fs_root() for
handle_indirect_tree_backref()
btrfs: Rename handle_one_tree_block() to btrfs_backref_add_tree_node()
and move it to backref.c
btrfs: Rename finish_upper_links() to
btrfs_backref_finish_upper_links() and move it to backref.c
btrfs: relocation: Move error handling of build_backref_tree() to
backref.c
btrfs: backref: Only ignore reloc roots for indrect backref resolve if
the backref cache is for reloction purpose
btrfs: qgroup: Introduce qgroup backref cache
btrfs: qgroup: Introduce qgroup_backref_cache_build() function
btrfs: qgroup: Introduce a function to iterate through backref_cache
to find all parents for specified node
btrfs: qgroup: Introduce helpers to get needed tree block info
btrfs: qgroup: Introduce verification for function to ensure old roots
ulist matches btrfs_find_all_roots() result
btrfs: qgroup: Introduce a new function to get old_roots ulist using
backref cache
btrfs: qgroup: Use backref cache to speed up old_roots search

 fs/btrfs/backref.c    |  808 ++++++++++++++++++++++++++++
 fs/btrfs/backref.h    |  319 +++++++++++
 fs/btrfs/ctree.h      |    5 +
 fs/btrfs/disk-io.c    |    1 +
 fs/btrfs/misc.h       |   54 ++
 fs/btrfs/qgroup.c     |  516 +++++++++++++++++-
 fs/btrfs/relocation.c | 1187 ++++++++---------------------------------
 7 files changed, 1925 insertions(+), 965 deletions(-)
Signature · 1 line
2.26.0