[PATCH v2 00/10] btrfs: relocation: Refactor build_backref_tree()

[Qu Wenruo <wqu@suse.com>]

This branch can be fetched from github:
https://github.com/adam900710/linux/tree/backref_cache_refactor

The basis is:
10f3586f65b0d0 (david/misc-next) btrfs: fix btrfs_calc_reclaim_metadata_size calculation

The main objective of this patchset is to refactor build_backref_tree()
and get myself more familiar with the backref cache.

The refactor also add quite some comments explaining how the backref
cache is built, but I'm also working on crafting a new dev doc for the
backref cache.

As some more example would greatly help reader to go through the
somewhat weird code.

Patch 1~8 haven already been sent to the mail list. This time they are
included for a better review.

There are 3 main structures involved:
- backref_cache
  The main cache structure, store all the existing cached map.

- backref_node
  Represent one tree block.
  It can have multiple parent and multiple children backref_edges
  related.

- backref_edge
  Represent one parent-child relationship between two backref_node.
  Both parent (upper) and child (lower) backref_node can iterate through
  their list to locate the edge.

The objective build_backref_cache() is to build a map, starting from
specified node, to reach all its parents. E.g:

  build_backref_tree() is called on bytenr X, then the following map
  is added to backref_cache:
     Root 257   Root 258
	  A      B
          |    /
          |  /
	  |/  
	  C
	  |
	  X
  We will have backref_nodes for X, A, B, C in the backref_cache, and
  3 edges between (X, C), (C, A), (C, B).


The short workflow of build_backref_tree() is:

- Iterate through all parent nodes of the specified node
  (ITERATION)

  Here we go breadth first search. We go through direct parent of
  current node. The iteration is bottom-up.

  For how each backref item is handled, check handle_one_tree_backref()
  for details.

  When a direct parent is found, we check if the direct parent is
  cached:
  * Cached:
    Allocate the edge between this node and parent. Call it a day, and
    process next parent.
  * Not cached:
    Allocate both edges and nodes. And queue the parent node for
    iteration.

  During this stage, new nodes are only allocated, not yet added to
  cache, and new edges are only linked to lower nodes.

  After this step, we have reached all roots referring to the specified
  node.
  Some root nodes may be useless (reloc tree root), they will be queued
  for later cleanup.

- Finish the linkage between newly added nodes and edges.
  (WEAVING)
  Since previous step only allocated new nodes, and only linked edges
  with its lower node, we still need to add the nodes to cache, and
  finish the linkage.

  See finish_upper_links() for details.

- Cleanup the useless trees
  (CLEANUP)
  For reloc trees, we only cache the backref nodes for higher tree
  nodes. And don't keep any edges. So such backref nodes are marked
  detached.
  Tree leaves for reloc trees are not cached.

  Such behavior is to reduce memory usage for useless trees, but still
  allow backref cache hit, to avoid unnecessary cache search.

  And also mark the useless nodes as processed for relocation.


With the refactor, only the CLEANUP part of build_backref_tree() is
really coupled with relocation.
And now build_backref_tree() is only 125 lines, it's a pretty good start
point for us to reuse backref_cache for other workload, like qgroups.

Changelog:
v2:
- Rebased to misc-next branch
  There are some small conflicts due to Josef's root ref count patches.
  To make sure everything is fine, the main code move part is re-written
  from scratch to ensure no btrfs_put_fs_root() is missing

- Better handling mark_block_processed()
  Now uses in_range() macro, and remove the set_extent_bit() wrapper
  which only get called in one location.

Qu Wenruo (10):
  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: Refactor 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

 fs/btrfs/backref.c    | 145 +++++++
 fs/btrfs/backref.h    |  94 ++++
 fs/btrfs/relocation.c | 968 ++++++++++++++++++++++--------------------
 3 files changed, 749 insertions(+), 458 deletions(-)

-- 
2.25.1