• Qu Wenruo's avatar
    btrfs: qgroup: Introduce function to trace two swaped extents · 25982561
    Qu Wenruo authored
    Introduce a new function, qgroup_trace_extent_swap(), which will be used
    later for balance qgroup speedup.
    The basis idea of balance is swapping tree blocks between reloc tree and
    the real file tree.
    The swap will happen in highest tree block, but there may be a lot of
    tree blocks involved.
    For example:
     OO = Old tree blocks
     NN = New tree blocks allocated during balance
              File tree (257)                  Reloc tree for 257
    L2              OO                                NN
                  /    \                            /    \
    L1          OO      OO (a)                    OO      NN (a)
               / \     / \                       / \     / \
    L0       OO   OO OO   OO                   OO   OO NN   NN
                     (b)  (c)                          (b)  (c)
    When calling qgroup_trace_extent_swap(), we will pass:
    @src_eb = OO(a)
    @dst_path = [ nodes[1] = NN(a), nodes[0] = NN(c) ]
    @dst_level = 0
    @root_level = 1
    In that case, qgroup_trace_extent_swap() will search from OO(a) to
    reach OO(c), then mark both OO(c) and NN(c) as qgroup dirty.
    The main work of qgroup_trace_extent_swap() can be split into 3 parts:
    1) Tree search from @src_eb
       It should acts as a simplified btrfs_search_slot().
       The key for search can be extracted from @dst_path->nodes[dst_level]
       (first key).
    2) Mark the final tree blocks in @src_path and @dst_path qgroup dirty
       NOTE: In above case, OO(a) and NN(a) won't be marked qgroup dirty.
       They should be marked during preivous (@dst_level = 1) iteration.
    3) Mark file extents in leaves dirty
       We don't have good way to pick out new file extents only.
       So we still follow the old method by scanning all file extents in
       the leave.
    This function can free us from keeping two pathes, thus later we only need
    to care about how to iterate all new tree blocks in reloc tree.
    Signed-off-by: default avatarQu Wenruo <wqu@suse.com>
    [ copy changelog to function comment ]
    Signed-off-by: default avatarDavid Sterba <dsterba@suse.com>