fs/btrfs/backref.c

144 	struct rb_root_cached root;
148 #define PREFTREE_INIT	{ .root = RB_ROOT_CACHED, .count = 0 }
166 	struct btrfs_root *root;
172 	 * the same root or different roots) that we could find. The sharedness
264 	if (newref->root_id == btrfs_root_id(sc->root) &&
271  * Add @newref to the @root rbtree, merging identical refs.
280 	struct rb_root_cached *root;
287 	root = &preftree->root;
288 	p = &root->rb_root.rb_node;
329 	rb_insert_color_cached(&newref->rbnode, root, leftmost);
334  * just free everything and then reset the tree root.
341 					     &preftree->root.rb_root, rbnode) {
346 	preftree->root = RB_ROOT_CACHED;
365  *  root for resolving |    y   |     y    |    y   |     y
378  *  root for resolving |    -   |     y    |    y   |     y
418 /* direct refs use root == 0, key == NULL */
445 	struct rb_node **p = &preftrees->direct.root.rb_root.rb_node;
469 			   struct btrfs_root *root, struct btrfs_path *path,
501 	 * 3. The leaf owner is not equal to the root we are searching
510 			ret = btrfs_next_leaf(root, path);
512 			ret = btrfs_next_old_leaf(root, path, ctx->time_seq);
528 		 * the leaf owner is not equal to the root we are searching for
534 				ret = btrfs_next_leaf(root, path);
536 				ret = btrfs_next_old_leaf(root, path, ctx->time_seq);
574 			ret = btrfs_next_item(root, path);
576 			ret = btrfs_next_old_item(root, path, ctx->time_seq);
596 	struct btrfs_root *root;
607 	 * for the root, and if we don't find it then we need to search the
608 	 * tree_root's commit root, thus the btrfs_get_fs_root_commit_root usage
612 		root = btrfs_get_fs_root_commit_root(ctx->fs_info, path, ref->root_id);
614 		root = btrfs_get_fs_root(ctx->fs_info, ref->root_id, false);
615 	if (IS_ERR(root)) {
616 		ret = PTR_ERR(root);
621 	    test_bit(BTRFS_ROOT_DELETING, &root->state)) {
632 		root_level = btrfs_header_level(root->commit_root);
634 		root_level = btrfs_header_level(root->node);
636 		root_level = btrfs_old_root_level(root, ctx->time_seq);
665 		ret = btrfs_search_slot(NULL, root, &search_key, path, 0, 0);
667 		ret = btrfs_search_old_slot(root, &search_key, path, ctx->time_seq);
670 		"search slot in root %llu (level %d, ref count %d) returned %d for key (%llu %u %llu)",
687 	ret = add_all_parents(ctx, root, path, parents, preftrees, ref, level);
689 	btrfs_put_root(root);
754 	while ((rnode = rb_first_cached(&preftrees->indirect.root))) {
764 		rb_erase_cached(&ref->rbnode, &preftrees->indirect.root);
772 		if (sc && ref->root_id != btrfs_root_id(sc->root)) {
845 	while ((node = rb_first_cached(&tree->root))) {
849 		rb_erase_cached(node, &tree->root);
1096 			u64 root;
1111 			root = btrfs_extent_data_ref_root(leaf, dref);
1114 			    !ctx->skip_data_ref(root, key.objectid, key.offset,
1117 						       root, &key, 0, ctx->bytenr,
1202 			u64 root;
1218 			root = btrfs_extent_data_ref_root(leaf, dref);
1221 			    !ctx->skip_data_ref(root, key.objectid, key.offset,
1223 				ret = add_indirect_ref(fs_info, preftrees, root,
1241  * fs_info->commit_root_sem semaphore, so no need to worry about the root's last
1245 					struct btrfs_root *root,
1248 	const struct btrfs_fs_info *fs_info = root->fs_info;
1264 	 * the root node down to the leaf with the file extent item.
1276 	 * root changed, so we now have a snapshot. Don't trust the result.
1279 	    entry->gen != btrfs_root_last_snapshot(&root->root_item))
1284 	 * a root changed, we can not trust the result, because the dropped root
1311  * fs_info->commit_root_sem semaphore, so no need to worry about the root's last
1315 				       struct btrfs_root *root,
1318 	const struct btrfs_fs_info *fs_info = root->fs_info;
1335 	 * the root node down to the leaf with the file extent item.
1342 		gen = btrfs_root_last_snapshot(&root->root_item);
1382 	struct btrfs_root *root = btrfs_extent_root(ctx->fs_info, ctx->bytenr);
1423 	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1488 			ret = add_keyed_refs(ctx, root, path, info_level,
1513 	 * tree (going from the root node down to the leaf that has the file
1520 		 * last generation used to snapshot the root, then we know that
1524 		 * root node down to the leaf that has the file extent item that
1528 		    btrfs_root_last_snapshot(&sc->root->root_item)) {
1549 			cached = lookup_backref_shared_cache(sc->ctx, sc->root,
1568 	WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect_missing_keys.root.rb_root));
1574 	WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect.root.rb_root));
1583 	node = rb_first_cached(&preftrees.direct.root);
1598 			/* no parent == root of tree */
1837  * circuit as soon as it finds a root or inode that doesn't match the
1852 	struct btrfs_root *root = inode->root;
1853 	struct btrfs_fs_info *fs_info = root->fs_info;
1861 		.root = root,
1880 	trans = btrfs_join_transaction_nostart(root);
1902 	leaf_cached = lookup_backref_shared_cache(ctx, root,
1928 				store_backref_shared_cache(ctx, root, bytenr,
1970 			store_backref_shared_cache(ctx, root, bytenr,
1981 			cached = lookup_backref_shared_cache(ctx, root, bytenr,
2007 			store_backref_shared_cache(ctx, root, bytenr, level, ret);
2043 int btrfs_find_one_extref(struct btrfs_root *root, u64 inode_objectid,
2059 	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
2076 			ret = btrfs_next_leaf(root, path);
2329  * reads the tree block backref for an extent. tree level and root are returned
2381 			     u64 root, u64 extent_item_objectid,
2389 			    "ref for %llu resolved, key (%llu EXTEND_DATA %llu), root %llu",
2391 			    eie->offset, root);
2392 		ret = iterate(eie->inum, eie->offset, eie->num_bytes, root, ctx);
2501 				    "root %llu references leaf %llu, data list %#llx",
2530 static int build_ino_list(u64 inum, u64 offset, u64 num_bytes, u64 root, void *ctx)
2539 		inodes->val[inodes->elem_cnt + 2] = root;
2836 	/* Current backref iterator only supports iteration in commit root */
3062 		btrfs_put_root(node->root);
3230 	/* Only reloc root uses backref pointing to itself */
3232 		struct btrfs_root *root;
3235 		/* Only reloc backref cache cares about a specific root */
3237 			root = find_reloc_root(cache->fs_info, cur->bytenr);
3238 			if (!root)
3240 			cur->root = root;
3243 			 * For generic purpose backref cache, reloc root node
3305 	struct btrfs_root *root;
3311 	root = btrfs_get_fs_root(fs_info, ref_key->offset, false);
3312 	if (IS_ERR(root))
3313 		return PTR_ERR(root);
3314 	if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state))
3317 	if (btrfs_root_level(&root->root_item) == cur->level) {
3318 		/* Tree root */
3319 		ASSERT(btrfs_root_bytenr(&root->root_item) == cur->bytenr);
3321 		 * For reloc backref cache, we may ignore reloc root.  But for
3324 		 * current running relocation and lead to missing root.
3326 		 * For general purpose backref cache, reloc root detection is
3330 		if (btrfs_should_ignore_reloc_root(root) && cache->is_reloc) {
3331 			btrfs_put_root(root);
3334 			cur->root = root;
3345 	ret = btrfs_search_slot(NULL, root, tree_key, path, 0, 0);
3348 		btrfs_put_root(root);
3358 			  cur->bytenr, level - 1, btrfs_root_id(root),
3360 		btrfs_put_root(root);
3369 			ASSERT(btrfs_root_bytenr(&root->root_item) ==
3372 			if (btrfs_should_ignore_reloc_root(root) &&
3374 				btrfs_put_root(root);
3377 				lower->root = root;
3384 			btrfs_put_root(root);
3395 				btrfs_put_root(root);
3401 			if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state))
3408 			if (btrfs_block_can_be_shared(trans, root, eb))
3438 			btrfs_put_root(root);
3559 			 * offset means the root objectid. We need to search