adam900710 btrfs: qgroup: Use backref cache to speed up old_roots search
7f0e747 Mar 26, 2020
btrfs: qgroup: Use backref cache to speed up old_roots search
Now use the backref cache backed backref walk mechanism.

This mechanism is trading memory usage for faster, and more qgroup
specific backref walk.

Compared to original btrfs_find_all_roots(), it has the extra behavior
difference:
- Skip non-subvolume tress from the very beginning
  Since only subvolume trees contribute to qgroup numbers, skipping them
  would save us time.

- Skip reloc trees earlier
  Reloc trees doesn't contribute to qgroup, and btrfs_find_all_roots()
  also doesn't account them, thus we don't need to account them.
  Here we use the detached nodes in backref cache to skip them faster
  and earlier.

- Cached results
  Well, backref cache is obviously cached, right.

The major performance improvement happens for backref walk in commit
tree, one of the most obvious user is qgroup rescan.

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 %

Signed-off-by: Qu Wenruo <wqu@suse.com>
7f0e747