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
