Lines Matching defs:tree
22 #include "print-tree.h"
33 #include "extent-tree.h"
34 #include "root-tree.h"
38 #include "tree-checker.h"
64 * 2.2 Build data reloc tree and reloc trees
65 * Data reloc tree will contain an inode, recording all newly relocated
67 * There will be only one data reloc tree for one data block group.
69 * Reloc tree will be a special snapshot of its source tree, containing
70 * relocated tree blocks.
71 * Each tree referring to a tree block in target block group will get its
72 * reloc tree built.
74 * 2.3 Swap source tree with its corresponding reloc tree
75 * Each involved tree only refers to new extents after swap.
77 * 3. Cleanup reloc trees and data reloc tree.
89 * map address of tree root to tree
105 * present a tree block to process
130 /* extent tree */
140 /* tree blocks have been processed */
142 /* map start of tree root to corresponding reloc tree */
150 /* size of relocated tree nodes */
184 static void mapping_tree_init(struct mapping_tree *tree)
186 tree->rb_root = RB_ROOT;
187 spin_lock_init(&tree->lock);
191 * walk up backref nodes until reach node presents tree root
268 * lookup. transaction commit changes the extent tree.
316 * Check if this subvolume tree has valid reloc tree.
318 * Reloc tree after swap is considered dead, thus not considered as valid.
339 /* This root has been merged with its reloc tree, we can ignore it */
351 * if there is reloc tree and it was created in previous
352 * transaction backref lookup can find the reloc tree,
353 * so backref node for the fs tree root is useless for
360 * find reloc tree by address of tree root
407 /* Only tree root nodes can be added to @useless_nodes */
439 * Backref nodes for tree leaves are deleted from the cache.
440 * Backref nodes for upper level tree blocks are left in the
455 * Build backref tree for a given tree block. Root of the backref tree
456 * corresponds the tree block, leaves of the backref tree correspond roots of
457 * b-trees that reference the tree block.
461 * these upper level blocks recursively. The recursion stops when tree root is
546 * corresponds to root of source tree
633 * helper to add 'address of tree root -> reloc tree' mapping
655 "Duplicate root found for start=%llu while inserting into relocation tree",
665 * helper to delete the 'address of tree root -> reloc tree'
709 * helper to update the 'address of tree root -> reloc tree'
783 * the source tree is a reloc tree, all tree blocks
839 * create reloc tree for a given fs tree. reloc tree is just a
840 * snapshot of the fs tree with special root objectid.
859 * The subvolume has reloc tree but the swap is finished, no need to
860 * create/update the dead reloc tree
881 * reloc trees never need their own reloc tree.
910 * update root item of reloc tree
938 * Mark the tree as dead before we change reloc_root so
1060 * update file extent items in the tree leaf to point to
1114 * if we are modifying block in fs tree, wait for read_folio
1202 * try to replace tree blocks in fs tree with the new blocks
1203 * in reloc tree. tree blocks haven't been modified since the
1204 * reloc tree was create can be replaced.
1362 * the swapped tree blocks.
1373 * swap blocks in fs tree and reloc tree.
1435 * helper to find next relocated block in reloc tree
1472 * walk down reloc tree to find relocated block of lowest level
1620 /* @root must be a subvolume tree root with a valid reloc tree */
1677 /* Orphan reloc tree, just clean it up */
1690 * merge the relocated tree blocks in reloc tree with corresponding
1691 * fs tree.
1746 * tree blocks between reloc tree and subvolume tree. Thus for tree
1747 * block COW, we COW at most from level 1 to root level for each tree.
1830 * handle the case only one block in the fs tree need to be
1831 * relocated and the block is tree root.
1924 "reloc tree mismatch, root %lld has reloc root key (%lld %u %llu) gen %llu, expect reloc root key (%lld %u %llu) gen %llu",
1938 "reloc tree mismatch, root %lld has no reloc root, expect reloc root key (%lld %u %llu) gen %llu",
2040 * corruption, e.g. bad reloc tree key offset.
2094 * have actually been removed from the reloc_root_tree rb tree. This is
2270 * Select a tree root for relocation.
2275 * Return a tree root pointer if the block is shareable.
2276 * Return -ENOENT if the block is root of reloc tree.
2300 /* No other choice for non-shareable tree */
2396 * relocate a block tree, and then update pointers in upper level
2668 * helper function to relocate a tree block
2684 * to start over and regenerate the tree for it.
2788 /* Kick in readahead for tree blocks with missing keys */
2805 /* Do tree relocation */
3192 * helper to add a tree block to the list.
3263 "unrecognized tree backref at tree block %llu slot %u",
3293 * helper to add tree blocks for backref of type BTRFS_SHARED_DATA_REF_KEY
3352 "tree block extent item (%llu) is not found in extent tree",
3403 * Locate the free space cache EXTENT_DATA in root tree leaf and delete the
3445 * helper to find all tree blocks that reference a given data extent
3632 * extent tree is not a ref_cow tree and has no reloc_root to
3875 * the inode is in data relocation tree and its link count is 0
4202 * this is important for keeping the sharing of tree blocks
4369 /* cleanup orphan inode in data relocation tree */
4479 * required for relocating tree blocks in the snapshot
4497 * used by merging a reloc tree is twice the size of
4498 * relocated tree nodes in the worst case. half for cowing
4499 * the reloc tree, half for cowing the fs tree. the space
4500 * used by cowing the reloc tree will be freed after the
4501 * tree is dropped. if we create snapshot, cowing the fs
4502 * tree may use more space than it frees. so we need