Lines Matching defs:tree
23 #include "print-tree.h"
53 * 2.2 Build data reloc tree and reloc trees
54 * Data reloc tree will contain an inode, recording all newly relocated
56 * There will be only one data reloc tree for one data block group.
58 * Reloc tree will be a special snapshot of its source tree, containing
59 * relocated tree blocks.
60 * Each tree referring to a tree block in target block group will get its
61 * reloc tree built.
63 * 2.3 Swap source tree with its corresponding reloc tree
64 * Each involved tree only refers to new extents after swap.
66 * 3. Cleanup reloc trees and data reloc tree.
78 * map address of tree root to tree
94 * present a tree block to process
118 /* extent tree */
128 /* tree blocks have been processed */
130 /* map start of tree root to corresponding reloc tree */
138 /* size of relocated tree nodes */
172 static void mapping_tree_init(struct mapping_tree *tree)
174 tree->rb_root = RB_ROOT;
175 spin_lock_init(&tree->lock);
179 * walk up backref nodes until reach node presents tree root
256 * lookup. transaction commit changes the extent tree.
304 * Check if this subvolume tree has valid reloc tree.
306 * Reloc tree after swap is considered dead, thus not considered as valid.
327 /* This root has been merged with its reloc tree, we can ignore it */
339 * if there is reloc tree and it was created in previous
340 * transaction backref lookup can find the reloc tree,
341 * so backref node for the fs tree root is useless for
348 * find reloc tree by address of tree root
395 /* Only tree root nodes can be added to @useless_nodes */
427 * Backref nodes for tree leaves are deleted from the cache.
428 * Backref nodes for upper level tree blocks are left in the
443 * Build backref tree for a given tree block. Root of the backref tree
444 * corresponds the tree block, leaves of the backref tree correspond roots of
445 * b-trees that reference the tree block.
449 * these upper level blocks recursively. The recursion stops when tree root is
533 * corresponds to root of source tree
620 * helper to add 'address of tree root -> reloc tree' mapping
642 "Duplicate root found for start=%llu while inserting into relocation tree",
651 * helper to delete the 'address of tree root -> reloc tree'
695 * helper to update the 'address of tree root -> reloc tree'
769 * the source tree is a reloc tree, all tree blocks
825 * create reloc tree for a given fs tree. reloc tree is just a
826 * snapshot of the fs tree with special root objectid.
845 * The subvolume has reloc tree but the swap is finished, no need to
846 * create/update the dead reloc tree
867 * reloc trees never need their own reloc tree.
889 * update root item of reloc tree
917 * Mark the tree as dead before we change reloc_root so
1039 * update file extent items in the tree leaf to point to
1093 * if we are modifying block in fs tree, wait for readpage
1178 * try to replace tree blocks in fs tree with the new blocks
1179 * in reloc tree. tree blocks haven't been modified since the
1180 * reloc tree was create can be replaced.
1335 * the swapped tree blocks.
1346 * swap blocks in fs tree and reloc tree.
1396 * helper to find next relocated block in reloc tree
1433 * walk down reloc tree to find relocated block of lowest level
1589 /* @root must be a subvolume tree root with a valid reloc tree */
1642 /* Orphan reloc tree, just clean it up */
1655 * merge the relocated tree blocks in reloc tree with corresponding
1656 * fs tree.
1712 * tree blocks between reloc tree and subvolume tree. Thus for tree
1713 * block COW, we COW at most from level 1 to root level for each tree.
1802 * handle the case only one block in the fs tree need to be
1803 * relocated and the block is tree root.
1994 * have actually been removed from the reloc_root_tree rb tree. This is
2094 * Select a tree root for relocation.
2099 * Return a tree root pointer if the block is shareable.
2100 * Return -ENOENT if the block is root of reloc tree.
2118 /* No other choice for non-shareable tree */
2214 * relocate a block tree, and then update pointers in upper level
2485 * helper function to relocate a tree block
2501 * to start over and regenerate the tree for it.
2564 /* Kick in readahead for tree blocks with missing keys */
2579 /* Do tree relocation */
2858 * helper to add a tree block to the list.
2920 * helper to add tree blocks for backref of type BTRFS_SHARED_DATA_REF_KEY
2979 "tree block extent item (%llu) is not found in extent tree",
3030 * Locate the free space cache EXTENT_DATA in root tree leaf and delete the
3072 * helper to find all tree blocks that reference a given data extent
3267 * extent tree is not a ref_cow tree and has no reloc_root to
3494 * the inode is in data relocation tree and its link count is 0
3741 * this is important for keeping the sharing of tree blocks
3895 /* cleanup orphan inode in data relocation tree */
4011 * required for relocating tree blocks in the snapshot
4029 * used by merging a reloc tree is twice the size of
4030 * relocated tree nodes in the worst case. half for cowing
4031 * the reloc tree, half for cowing the fs tree. the space
4032 * used by cowing the reloc tree will be freed after the
4033 * tree is dropped. if we create snapshot, cowing the fs
4034 * tree may use more space than it frees. so we need