fs/btrfs/backref.c

17 #include "tree-mod-log.h"
20 #include "extent-tree.h"
22 #include "tree-checker.h"
333  * Release the entire tree.  We don't care about internal consistency so
334  * just free everything and then reset the tree root.
360  * information         |   tree |     tree |   data |     data
364  *  tree block logical |    -   |     -    |    -   |     -
373  * information         |   tree |     tree |   data |     data
377  *  tree block logical |    y   |     y    |    y   |     y
435 	struct preftree *tree = &preftrees->indirect;
438 		tree = &preftrees->indirect_missing_keys;
439 	return add_prelim_ref(fs_info, tree, root_id, key, level, 0,
605 	 * other tree nodes.  This happens when qgroups does backref walks when
719  * have a key. Each tree does merge on insertion.
721  * Once all of the references are located, we iterate over the tree of
723  * the ref is moved onto the tree for indirect refs. After all missing
724  * keys are thus located, we iterate over the indirect ref tree, resolve
726  * direct tree (merging there too).
750 	 * the tree, allocating new refs for each insertion, and then
751 	 * freeing the entire indirect tree when we're done.  In some test
752 	 * cases, the tree can grow quite large (~200k objects).
759 			 "BUG: direct ref found in indirect tree")) {
817 		 * Now it's a direct ref, put it in the direct tree. We must
835  * read tree blocks and add keys where required.
842 	struct preftree *tree = &preftrees->indirect_missing_keys;
845 	while ((node = rb_first_cached(&tree->root))) {
849 		rb_erase_cached(node, &tree->root);
923 			/* The owner of a tree block ref is the level. */
940 			 * The owner of a tree block ref is the level.
964 			 * process references from the extent tree (through
968 			 * may cancel that reference in the extent tree.
1354 	 * data extent is increased in the extent item at the extent tree.
1500 	 * processing inline or keyed references from the extent tree.
1504 	 * what's the leaf (or leaves), from a fs tree, that has a file extent
1513 	 * tree (going from the root node down to the leaf that has the file
1523 		 * determining the extent buffers for the path from the fs tree
1537 		 * indirect references for a data extent, since the fs tree path
1577 	 * This walks the tree of merged and resolved refs. Tree blocks are
1581 	 * We release the entire tree in one go before returning.
1598 			/* no parent == root of tree */
1939 		 * tree paths in case the first one is not shared, so we can not
1949 		 *    item gets moved to another leaf due to a b+tree leaf split
1958 		 * 2) level >= 0, a tree node/leaf: We can have a mix of direct
1959 		 *    and indirect references on a b+tree node/leaf, so we have
1962 		 *    during relocation as we may get a shared tree block ref
1963 		 *    (direct ref) and a non-shared tree block ref (indirect
1994 	 * If the path cache is disabled, then it means at some tree level we
2091 		 * in the tree and we can exit.
2194  * 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",
2901 	 * Only support iteration on tree backref yet.
2904 	 * EXTENT_ITEM is also used for tree blocks, that we can only use
2905 	 * extent flags to determine if it's a tree block.
2978 			/* First tree block info */
3111 void btrfs_backref_drop_node(struct btrfs_backref_cache *tree,
3120 		rb_erase(&node->rb_node, &tree->rb_root);
3121 	btrfs_backref_free_node(tree, node);
3209  * Handle direct tree backref
3211  * Direct tree backref means, the backref item shows its parent bytenr
3281  * Handle indirect tree backref
3283  * Indirect tree backref means, we only know which tree the node belongs to.
3284  * We still need to do a tree search to find out the parents. This is for
3289  * @tree_key:	The first key of this tree block.
3341 	/* Search the tree to find parent blocks referring to the block */
3357 "couldn't find block (%llu) (level %d) in tree (%llu) with key (%llu %u %llu)",
3416 			 * tree as we will catch anything else later on.
3457  * @path:	Released path for indirect tree backref lookup
3458  * @iter:	Released backref iter for extent tree search
3459  * @node_key:	The first key of the tree block
3477 	 * stored in it, but fetch it from the tree block
3483 		/* No extra backref? This means the tree block is corrupted */
3560 			 * the tree to get its parent bytenr.
3568 		 * Unrecognized tree backref items (if it can pass tree-checker)
3634 		 * been linked to the cache rb tree.
3661 		/* Only cache non-COW-only (subvolume trees) tree blocks */