Lines Matching defs:tree
17 #include "tree-mod-log.h"
20 #include "extent-tree.h"
22 #include "tree-checker.h"
336 * Release the entire tree. We don't care about internal consistency so
337 * just free everything and then reset the tree root.
363 * information | tree | tree | data | data
367 * tree block logical | - | - | - | -
376 * information | tree | tree | data | data
380 * tree block logical | y | y | y | y
438 struct preftree *tree = &preftrees->indirect;
441 tree = &preftrees->indirect_missing_keys;
442 return add_prelim_ref(fs_info, tree, root_id, key, level, 0,
608 * other tree nodes. This happens when qgroups does backref walks when
722 * have a key. Each tree does merge on insertion.
724 * Once all of the references are located, we iterate over the tree of
726 * the ref is moved onto the tree for indirect refs. After all missing
727 * keys are thus located, we iterate over the indirect ref tree, resolve
729 * direct tree (merging there too).
753 * the tree, allocating new refs for each insertion, and then
754 * freeing the entire indirect tree when we're done. In some test
755 * cases, the tree can grow quite large (~200k objects).
762 "BUG: direct ref found in indirect tree")) {
820 * Now it's a direct ref, put it in the direct tree. We must
838 * read tree blocks and add keys where required.
845 struct preftree *tree = &preftrees->indirect_missing_keys;
848 while ((node = rb_first_cached(&tree->root))) {
852 rb_erase_cached(node, &tree->root);
969 * process references from the extent tree (through
973 * may cancel that reference in the extent tree.
1362 * data extent is increased in the extent item at the extent tree.
1506 * processing inline or keyed references from the extent tree.
1510 * what's the leaf (or leaves), from a fs tree, that has a file extent
1519 * tree (going from the root node down to the leaf that has the file
1529 * determining the extent buffers for the path from the fs tree
1543 * indirect references for a data extent, since the fs tree path
1583 * This walks the tree of merged and resolved refs. Tree blocks are
1587 * We release the entire tree in one go before returning.
1604 /* no parent == root of tree */
1945 * tree paths in case the first one is not shared, so we can not
1955 * item gets moved to another leaf due to a b+tree leaf split
1964 * 2) level >= 0, a tree node/leaf: We can have a mix of direct
1965 * and indirect references on a b+tree node/leaf, so we have
1968 * during relocation as we may get a shared tree block ref
1969 * (direct ref) and a non-shared tree block ref (indirect
2000 * If the path cache is disabled, then it means at some tree level we
2097 * in the tree and we can exit.
2200 * tree blocks and <0 on error.
2329 * reads the tree block backref for an extent. tree level and root are returned
2624 "following ref at offset %u for inode %llu in tree %llu",
2893 * Only support iteration on tree backref yet.
2896 * EXTENT_ITEM is also used for tree blocks, that we can only use
2897 * extent flags to determine if it's a tree block.
2962 /* First tree block info */
3121 * Handle direct tree backref
3123 * Direct tree backref means, the backref item shows its parent bytenr
3193 * Handle indirect tree backref
3195 * Indirect tree backref means, we only know which tree the node belongs to.
3196 * We still need to do a tree search to find out the parents. This is for
3201 * @tree_key: The first key of this tree block.
3253 /* Search the tree to find parent blocks referring to the block */
3269 "couldn't find block (%llu) (level %d) in tree (%llu) with key (%llu %u %llu)",
3328 * tree as we will catch anything else later on.
3369 * @path: Released path for indirect tree backref lookup
3370 * @iter: Released backref iter for extent tree search
3371 * @node_key: The first key of the tree block
3389 * stored in it, but fetch it from the tree block
3395 /* No extra backref? This means the tree block is corrupted */
3472 * the tree to get its parent bytenr.
3480 * Unrecognized tree backref items (if it can pass tree-checker)
3546 * been linked to the cache rb tree.
3573 /* Only cache non-COW-only (subvolume trees) tree blocks */