brintos / linux-shallow public Read only

1// SPDX-License-Identifier: GPL-2.02/*3 * Copyright (C) 2011 STRATO.  All rights reserved.4 */5 6#include <linux/mm.h>7#include <linux/rbtree.h>8#include <trace/events/btrfs.h>9#include "ctree.h"10#include "disk-io.h"11#include "backref.h"12#include "ulist.h"13#include "transaction.h"14#include "delayed-ref.h"15#include "locking.h"16#include "misc.h"17#include "tree-mod-log.h"18#include "fs.h"19#include "accessors.h"20#include "extent-tree.h"21#include "relocation.h"22#include "tree-checker.h"23 24/* Just arbitrary numbers so we can be sure one of these happened. */25#define BACKREF_FOUND_SHARED     626#define BACKREF_FOUND_NOT_SHARED 727 28struct extent_inode_elem {29	u64 inum;30	u64 offset;31	u64 num_bytes;32	struct extent_inode_elem *next;33};34 35static int check_extent_in_eb(struct btrfs_backref_walk_ctx *ctx,36			      const struct btrfs_key *key,37			      const struct extent_buffer *eb,38			      const struct btrfs_file_extent_item *fi,39			      struct extent_inode_elem **eie)40{41	const u64 data_len = btrfs_file_extent_num_bytes(eb, fi);42	u64 offset = key->offset;43	struct extent_inode_elem *e;44	const u64 *root_ids;45	int root_count;46	bool cached;47 48	if (!ctx->ignore_extent_item_pos &&49	    !btrfs_file_extent_compression(eb, fi) &&50	    !btrfs_file_extent_encryption(eb, fi) &&51	    !btrfs_file_extent_other_encoding(eb, fi)) {52		u64 data_offset;53 54		data_offset = btrfs_file_extent_offset(eb, fi);55 56		if (ctx->extent_item_pos < data_offset ||57		    ctx->extent_item_pos >= data_offset + data_len)58			return 1;59		offset += ctx->extent_item_pos - data_offset;60	}61 62	if (!ctx->indirect_ref_iterator || !ctx->cache_lookup)63		goto add_inode_elem;64 65	cached = ctx->cache_lookup(eb->start, ctx->user_ctx, &root_ids,66				   &root_count);67	if (!cached)68		goto add_inode_elem;69 70	for (int i = 0; i < root_count; i++) {71		int ret;72 73		ret = ctx->indirect_ref_iterator(key->objectid, offset,74						 data_len, root_ids[i],75						 ctx->user_ctx);76		if (ret)77			return ret;78	}79 80add_inode_elem:81	e = kmalloc(sizeof(*e), GFP_NOFS);82	if (!e)83		return -ENOMEM;84 85	e->next = *eie;86	e->inum = key->objectid;87	e->offset = offset;88	e->num_bytes = data_len;89	*eie = e;90 91	return 0;92}93 94static void free_inode_elem_list(struct extent_inode_elem *eie)95{96	struct extent_inode_elem *eie_next;97 98	for (; eie; eie = eie_next) {99		eie_next = eie->next;100		kfree(eie);101	}102}103 104static int find_extent_in_eb(struct btrfs_backref_walk_ctx *ctx,105			     const struct extent_buffer *eb,106			     struct extent_inode_elem **eie)107{108	u64 disk_byte;109	struct btrfs_key key;110	struct btrfs_file_extent_item *fi;111	int slot;112	int nritems;113	int extent_type;114	int ret;115 116	/*117	 * from the shared data ref, we only have the leaf but we need118	 * the key. thus, we must look into all items and see that we119	 * find one (some) with a reference to our extent item.120	 */121	nritems = btrfs_header_nritems(eb);122	for (slot = 0; slot < nritems; ++slot) {123		btrfs_item_key_to_cpu(eb, &key, slot);124		if (key.type != BTRFS_EXTENT_DATA_KEY)125			continue;126		fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);127		extent_type = btrfs_file_extent_type(eb, fi);128		if (extent_type == BTRFS_FILE_EXTENT_INLINE)129			continue;130		/* don't skip BTRFS_FILE_EXTENT_PREALLOC, we can handle that */131		disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);132		if (disk_byte != ctx->bytenr)133			continue;134 135		ret = check_extent_in_eb(ctx, &key, eb, fi, eie);136		if (ret == BTRFS_ITERATE_EXTENT_INODES_STOP || ret < 0)137			return ret;138	}139 140	return 0;141}142 143struct preftree {144	struct rb_root_cached root;145	unsigned int count;146};147 148#define PREFTREE_INIT	{ .root = RB_ROOT_CACHED, .count = 0 }149 150struct preftrees {151	struct preftree direct;    /* BTRFS_SHARED_[DATA|BLOCK]_REF_KEY */152	struct preftree indirect;  /* BTRFS_[TREE_BLOCK|EXTENT_DATA]_REF_KEY */153	struct preftree indirect_missing_keys;154};155 156/*157 * Checks for a shared extent during backref search.158 *159 * The share_count tracks prelim_refs (direct and indirect) having a160 * ref->count >0:161 *  - incremented when a ref->count transitions to >0162 *  - decremented when a ref->count transitions to <1163 */164struct share_check {165	struct btrfs_backref_share_check_ctx *ctx;166	struct btrfs_root *root;167	u64 inum;168	u64 data_bytenr;169	u64 data_extent_gen;170	/*171	 * Counts number of inodes that refer to an extent (different inodes in172	 * the same root or different roots) that we could find. The sharedness173	 * check typically stops once this counter gets greater than 1, so it174	 * may not reflect the total number of inodes.175	 */176	int share_count;177	/*178	 * The number of times we found our inode refers to the data extent we179	 * are determining the sharedness. In other words, how many file extent180	 * items we could find for our inode that point to our target data181	 * extent. The value we get here after finishing the extent sharedness182	 * check may be smaller than reality, but if it ends up being greater183	 * than 1, then we know for sure the inode has multiple file extent184	 * items that point to our inode, and we can safely assume it's useful185	 * to cache the sharedness check result.186	 */187	int self_ref_count;188	bool have_delayed_delete_refs;189};190 191static inline int extent_is_shared(struct share_check *sc)192{193	return (sc && sc->share_count > 1) ? BACKREF_FOUND_SHARED : 0;194}195 196static struct kmem_cache *btrfs_prelim_ref_cache;197 198int __init btrfs_prelim_ref_init(void)199{200	btrfs_prelim_ref_cache = kmem_cache_create("btrfs_prelim_ref",201					sizeof(struct prelim_ref), 0, 0, NULL);202	if (!btrfs_prelim_ref_cache)203		return -ENOMEM;204	return 0;205}206 207void __cold btrfs_prelim_ref_exit(void)208{209	kmem_cache_destroy(btrfs_prelim_ref_cache);210}211 212static void free_pref(struct prelim_ref *ref)213{214	kmem_cache_free(btrfs_prelim_ref_cache, ref);215}216 217/*218 * Return 0 when both refs are for the same block (and can be merged).219 * A -1 return indicates ref1 is a 'lower' block than ref2, while 1220 * indicates a 'higher' block.221 */222static int prelim_ref_compare(const struct prelim_ref *ref1,223			      const struct prelim_ref *ref2)224{225	if (ref1->level < ref2->level)226		return -1;227	if (ref1->level > ref2->level)228		return 1;229	if (ref1->root_id < ref2->root_id)230		return -1;231	if (ref1->root_id > ref2->root_id)232		return 1;233	if (ref1->key_for_search.type < ref2->key_for_search.type)234		return -1;235	if (ref1->key_for_search.type > ref2->key_for_search.type)236		return 1;237	if (ref1->key_for_search.objectid < ref2->key_for_search.objectid)238		return -1;239	if (ref1->key_for_search.objectid > ref2->key_for_search.objectid)240		return 1;241	if (ref1->key_for_search.offset < ref2->key_for_search.offset)242		return -1;243	if (ref1->key_for_search.offset > ref2->key_for_search.offset)244		return 1;245	if (ref1->parent < ref2->parent)246		return -1;247	if (ref1->parent > ref2->parent)248		return 1;249 250	return 0;251}252 253static void update_share_count(struct share_check *sc, int oldcount,254			       int newcount, const struct prelim_ref *newref)255{256	if ((!sc) || (oldcount == 0 && newcount < 1))257		return;258 259	if (oldcount > 0 && newcount < 1)260		sc->share_count--;261	else if (oldcount < 1 && newcount > 0)262		sc->share_count++;263 264	if (newref->root_id == btrfs_root_id(sc->root) &&265	    newref->wanted_disk_byte == sc->data_bytenr &&266	    newref->key_for_search.objectid == sc->inum)267		sc->self_ref_count += newref->count;268}269 270/*271 * Add @newref to the @root rbtree, merging identical refs.272 *273 * Callers should assume that newref has been freed after calling.274 */275static void prelim_ref_insert(const struct btrfs_fs_info *fs_info,276			      struct preftree *preftree,277			      struct prelim_ref *newref,278			      struct share_check *sc)279{280	struct rb_root_cached *root;281	struct rb_node **p;282	struct rb_node *parent = NULL;283	struct prelim_ref *ref;284	int result;285	bool leftmost = true;286 287	root = &preftree->root;288	p = &root->rb_root.rb_node;289 290	while (*p) {291		parent = *p;292		ref = rb_entry(parent, struct prelim_ref, rbnode);293		result = prelim_ref_compare(ref, newref);294		if (result < 0) {295			p = &(*p)->rb_left;296		} else if (result > 0) {297			p = &(*p)->rb_right;298			leftmost = false;299		} else {300			/* Identical refs, merge them and free @newref */301			struct extent_inode_elem *eie = ref->inode_list;302 303			while (eie && eie->next)304				eie = eie->next;305 306			if (!eie)307				ref->inode_list = newref->inode_list;308			else309				eie->next = newref->inode_list;310			trace_btrfs_prelim_ref_merge(fs_info, ref, newref,311						     preftree->count);312			/*313			 * A delayed ref can have newref->count < 0.314			 * The ref->count is updated to follow any315			 * BTRFS_[ADD|DROP]_DELAYED_REF actions.316			 */317			update_share_count(sc, ref->count,318					   ref->count + newref->count, newref);319			ref->count += newref->count;320			free_pref(newref);321			return;322		}323	}324 325	update_share_count(sc, 0, newref->count, newref);326	preftree->count++;327	trace_btrfs_prelim_ref_insert(fs_info, newref, NULL, preftree->count);328	rb_link_node(&newref->rbnode, parent, p);329	rb_insert_color_cached(&newref->rbnode, root, leftmost);330}331 332/*333 * Release the entire tree.  We don't care about internal consistency so334 * just free everything and then reset the tree root.335 */336static void prelim_release(struct preftree *preftree)337{338	struct prelim_ref *ref, *next_ref;339 340	rbtree_postorder_for_each_entry_safe(ref, next_ref,341					     &preftree->root.rb_root, rbnode) {342		free_inode_elem_list(ref->inode_list);343		free_pref(ref);344	}345 346	preftree->root = RB_ROOT_CACHED;347	preftree->count = 0;348}349 350/*351 * the rules for all callers of this function are:352 * - obtaining the parent is the goal353 * - if you add a key, you must know that it is a correct key354 * - if you cannot add the parent or a correct key, then we will look into the355 *   block later to set a correct key356 *357 * delayed refs358 * ============359 *        backref type | shared | indirect | shared | indirect360 * information         |   tree |     tree |   data |     data361 * --------------------+--------+----------+--------+----------362 *      parent logical |    y   |     -    |    -   |     -363 *      key to resolve |    -   |     y    |    y   |     y364 *  tree block logical |    -   |     -    |    -   |     -365 *  root for resolving |    y   |     y    |    y   |     y366 *367 * - column 1:       we've the parent -> done368 * - column 2, 3, 4: we use the key to find the parent369 *370 * on disk refs (inline or keyed)371 * ==============================372 *        backref type | shared | indirect | shared | indirect373 * information         |   tree |     tree |   data |     data374 * --------------------+--------+----------+--------+----------375 *      parent logical |    y   |     -    |    y   |     -376 *      key to resolve |    -   |     -    |    -   |     y377 *  tree block logical |    y   |     y    |    y   |     y378 *  root for resolving |    -   |     y    |    y   |     y379 *380 * - column 1, 3: we've the parent -> done381 * - column 2:    we take the first key from the block to find the parent382 *                (see add_missing_keys)383 * - column 4:    we use the key to find the parent384 *385 * additional information that's available but not required to find the parent386 * block might help in merging entries to gain some speed.387 */388static int add_prelim_ref(const struct btrfs_fs_info *fs_info,389			  struct preftree *preftree, u64 root_id,390			  const struct btrfs_key *key, int level, u64 parent,391			  u64 wanted_disk_byte, int count,392			  struct share_check *sc, gfp_t gfp_mask)393{394	struct prelim_ref *ref;395 396	if (root_id == BTRFS_DATA_RELOC_TREE_OBJECTID)397		return 0;398 399	ref = kmem_cache_alloc(btrfs_prelim_ref_cache, gfp_mask);400	if (!ref)401		return -ENOMEM;402 403	ref->root_id = root_id;404	if (key)405		ref->key_for_search = *key;406	else407		memset(&ref->key_for_search, 0, sizeof(ref->key_for_search));408 409	ref->inode_list = NULL;410	ref->level = level;411	ref->count = count;412	ref->parent = parent;413	ref->wanted_disk_byte = wanted_disk_byte;414	prelim_ref_insert(fs_info, preftree, ref, sc);415	return extent_is_shared(sc);416}417 418/* direct refs use root == 0, key == NULL */419static int add_direct_ref(const struct btrfs_fs_info *fs_info,420			  struct preftrees *preftrees, int level, u64 parent,421			  u64 wanted_disk_byte, int count,422			  struct share_check *sc, gfp_t gfp_mask)423{424	return add_prelim_ref(fs_info, &preftrees->direct, 0, NULL, level,425			      parent, wanted_disk_byte, count, sc, gfp_mask);426}427 428/* indirect refs use parent == 0 */429static int add_indirect_ref(const struct btrfs_fs_info *fs_info,430			    struct preftrees *preftrees, u64 root_id,431			    const struct btrfs_key *key, int level,432			    u64 wanted_disk_byte, int count,433			    struct share_check *sc, gfp_t gfp_mask)434{435	struct preftree *tree = &preftrees->indirect;436 437	if (!key)438		tree = &preftrees->indirect_missing_keys;439	return add_prelim_ref(fs_info, tree, root_id, key, level, 0,440			      wanted_disk_byte, count, sc, gfp_mask);441}442 443static int is_shared_data_backref(struct preftrees *preftrees, u64 bytenr)444{445	struct rb_node **p = &preftrees->direct.root.rb_root.rb_node;446	struct rb_node *parent = NULL;447	struct prelim_ref *ref = NULL;448	struct prelim_ref target = {};449	int result;450 451	target.parent = bytenr;452 453	while (*p) {454		parent = *p;455		ref = rb_entry(parent, struct prelim_ref, rbnode);456		result = prelim_ref_compare(ref, &target);457 458		if (result < 0)459			p = &(*p)->rb_left;460		else if (result > 0)461			p = &(*p)->rb_right;462		else463			return 1;464	}465	return 0;466}467 468static int add_all_parents(struct btrfs_backref_walk_ctx *ctx,469			   struct btrfs_root *root, struct btrfs_path *path,470			   struct ulist *parents,471			   struct preftrees *preftrees, struct prelim_ref *ref,472			   int level)473{474	int ret = 0;475	int slot;476	struct extent_buffer *eb;477	struct btrfs_key key;478	struct btrfs_key *key_for_search = &ref->key_for_search;479	struct btrfs_file_extent_item *fi;480	struct extent_inode_elem *eie = NULL, *old = NULL;481	u64 disk_byte;482	u64 wanted_disk_byte = ref->wanted_disk_byte;483	u64 count = 0;484	u64 data_offset;485	u8 type;486 487	if (level != 0) {488		eb = path->nodes[level];489		ret = ulist_add(parents, eb->start, 0, GFP_NOFS);490		if (ret < 0)491			return ret;492		return 0;493	}494 495	/*496	 * 1. We normally enter this function with the path already pointing to497	 *    the first item to check. But sometimes, we may enter it with498	 *    slot == nritems.499	 * 2. We are searching for normal backref but bytenr of this leaf500	 *    matches shared data backref501	 * 3. The leaf owner is not equal to the root we are searching502	 *503	 * For these cases, go to the next leaf before we continue.504	 */505	eb = path->nodes[0];506	if (path->slots[0] >= btrfs_header_nritems(eb) ||507	    is_shared_data_backref(preftrees, eb->start) ||508	    ref->root_id != btrfs_header_owner(eb)) {509		if (ctx->time_seq == BTRFS_SEQ_LAST)510			ret = btrfs_next_leaf(root, path);511		else512			ret = btrfs_next_old_leaf(root, path, ctx->time_seq);513	}514 515	while (!ret && count < ref->count) {516		eb = path->nodes[0];517		slot = path->slots[0];518 519		btrfs_item_key_to_cpu(eb, &key, slot);520 521		if (key.objectid != key_for_search->objectid ||522		    key.type != BTRFS_EXTENT_DATA_KEY)523			break;524 525		/*526		 * We are searching for normal backref but bytenr of this leaf527		 * matches shared data backref, OR528		 * the leaf owner is not equal to the root we are searching for529		 */530		if (slot == 0 &&531		    (is_shared_data_backref(preftrees, eb->start) ||532		     ref->root_id != btrfs_header_owner(eb))) {533			if (ctx->time_seq == BTRFS_SEQ_LAST)534				ret = btrfs_next_leaf(root, path);535			else536				ret = btrfs_next_old_leaf(root, path, ctx->time_seq);537			continue;538		}539		fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);540		type = btrfs_file_extent_type(eb, fi);541		if (type == BTRFS_FILE_EXTENT_INLINE)542			goto next;543		disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);544		data_offset = btrfs_file_extent_offset(eb, fi);545 546		if (disk_byte == wanted_disk_byte) {547			eie = NULL;548			old = NULL;549			if (ref->key_for_search.offset == key.offset - data_offset)550				count++;551			else552				goto next;553			if (!ctx->skip_inode_ref_list) {554				ret = check_extent_in_eb(ctx, &key, eb, fi, &eie);555				if (ret == BTRFS_ITERATE_EXTENT_INODES_STOP ||556				    ret < 0)557					break;558			}559			if (ret > 0)560				goto next;561			ret = ulist_add_merge_ptr(parents, eb->start,562						  eie, (void **)&old, GFP_NOFS);563			if (ret < 0)564				break;565			if (!ret && !ctx->skip_inode_ref_list) {566				while (old->next)567					old = old->next;568				old->next = eie;569			}570			eie = NULL;571		}572next:573		if (ctx->time_seq == BTRFS_SEQ_LAST)574			ret = btrfs_next_item(root, path);575		else576			ret = btrfs_next_old_item(root, path, ctx->time_seq);577	}578 579	if (ret == BTRFS_ITERATE_EXTENT_INODES_STOP || ret < 0)580		free_inode_elem_list(eie);581	else if (ret > 0)582		ret = 0;583 584	return ret;585}586 587/*588 * resolve an indirect backref in the form (root_id, key, level)589 * to a logical address590 */591static int resolve_indirect_ref(struct btrfs_backref_walk_ctx *ctx,592				struct btrfs_path *path,593				struct preftrees *preftrees,594				struct prelim_ref *ref, struct ulist *parents)595{596	struct btrfs_root *root;597	struct extent_buffer *eb;598	int ret = 0;599	int root_level;600	int level = ref->level;601	struct btrfs_key search_key = ref->key_for_search;602 603	/*604	 * If we're search_commit_root we could possibly be holding locks on605	 * other tree nodes.  This happens when qgroups does backref walks when606	 * adding new delayed refs.  To deal with this we need to look in cache607	 * for the root, and if we don't find it then we need to search the608	 * tree_root's commit root, thus the btrfs_get_fs_root_commit_root usage609	 * here.610	 */611	if (path->search_commit_root)612		root = btrfs_get_fs_root_commit_root(ctx->fs_info, path, ref->root_id);613	else614		root = btrfs_get_fs_root(ctx->fs_info, ref->root_id, false);615	if (IS_ERR(root)) {616		ret = PTR_ERR(root);617		goto out_free;618	}619 620	if (!path->search_commit_root &&621	    test_bit(BTRFS_ROOT_DELETING, &root->state)) {622		ret = -ENOENT;623		goto out;624	}625 626	if (btrfs_is_testing(ctx->fs_info)) {627		ret = -ENOENT;628		goto out;629	}630 631	if (path->search_commit_root)632		root_level = btrfs_header_level(root->commit_root);633	else if (ctx->time_seq == BTRFS_SEQ_LAST)634		root_level = btrfs_header_level(root->node);635	else636		root_level = btrfs_old_root_level(root, ctx->time_seq);637 638	if (root_level + 1 == level)639		goto out;640 641	/*642	 * We can often find data backrefs with an offset that is too large643	 * (>= LLONG_MAX, maximum allowed file offset) due to underflows when644	 * subtracting a file's offset with the data offset of its645	 * corresponding extent data item. This can happen for example in the646	 * clone ioctl.647	 *648	 * So if we detect such case we set the search key's offset to zero to649	 * make sure we will find the matching file extent item at650	 * add_all_parents(), otherwise we will miss it because the offset651	 * taken form the backref is much larger then the offset of the file652	 * extent item. This can make us scan a very large number of file653	 * extent items, but at least it will not make us miss any.654	 *655	 * This is an ugly workaround for a behaviour that should have never656	 * existed, but it does and a fix for the clone ioctl would touch a lot657	 * of places, cause backwards incompatibility and would not fix the658	 * problem for extents cloned with older kernels.659	 */660	if (search_key.type == BTRFS_EXTENT_DATA_KEY &&661	    search_key.offset >= LLONG_MAX)662		search_key.offset = 0;663	path->lowest_level = level;664	if (ctx->time_seq == BTRFS_SEQ_LAST)665		ret = btrfs_search_slot(NULL, root, &search_key, path, 0, 0);666	else667		ret = btrfs_search_old_slot(root, &search_key, path, ctx->time_seq);668 669	btrfs_debug(ctx->fs_info,670		"search slot in root %llu (level %d, ref count %d) returned %d for key (%llu %u %llu)",671		 ref->root_id, level, ref->count, ret,672		 ref->key_for_search.objectid, ref->key_for_search.type,673		 ref->key_for_search.offset);674	if (ret < 0)675		goto out;676 677	eb = path->nodes[level];678	while (!eb) {679		if (WARN_ON(!level)) {680			ret = 1;681			goto out;682		}683		level--;684		eb = path->nodes[level];685	}686 687	ret = add_all_parents(ctx, root, path, parents, preftrees, ref, level);688out:689	btrfs_put_root(root);690out_free:691	path->lowest_level = 0;692	btrfs_release_path(path);693	return ret;694}695 696static struct extent_inode_elem *697unode_aux_to_inode_list(struct ulist_node *node)698{699	if (!node)700		return NULL;701	return (struct extent_inode_elem *)(uintptr_t)node->aux;702}703 704static void free_leaf_list(struct ulist *ulist)705{706	struct ulist_node *node;707	struct ulist_iterator uiter;708 709	ULIST_ITER_INIT(&uiter);710	while ((node = ulist_next(ulist, &uiter)))711		free_inode_elem_list(unode_aux_to_inode_list(node));712 713	ulist_free(ulist);714}715 716/*717 * We maintain three separate rbtrees: one for direct refs, one for718 * indirect refs which have a key, and one for indirect refs which do not719 * have a key. Each tree does merge on insertion.720 *721 * Once all of the references are located, we iterate over the tree of722 * indirect refs with missing keys. An appropriate key is located and723 * the ref is moved onto the tree for indirect refs. After all missing724 * keys are thus located, we iterate over the indirect ref tree, resolve725 * each reference, and then insert the resolved reference onto the726 * direct tree (merging there too).727 *728 * New backrefs (i.e., for parent nodes) are added to the appropriate729 * rbtree as they are encountered. The new backrefs are subsequently730 * resolved as above.731 */732static int resolve_indirect_refs(struct btrfs_backref_walk_ctx *ctx,733				 struct btrfs_path *path,734				 struct preftrees *preftrees,735				 struct share_check *sc)736{737	int err;738	int ret = 0;739	struct ulist *parents;740	struct ulist_node *node;741	struct ulist_iterator uiter;742	struct rb_node *rnode;743 744	parents = ulist_alloc(GFP_NOFS);745	if (!parents)746		return -ENOMEM;747 748	/*749	 * We could trade memory usage for performance here by iterating750	 * the tree, allocating new refs for each insertion, and then751	 * freeing the entire indirect tree when we're done.  In some test752	 * cases, the tree can grow quite large (~200k objects).753	 */754	while ((rnode = rb_first_cached(&preftrees->indirect.root))) {755		struct prelim_ref *ref;756 757		ref = rb_entry(rnode, struct prelim_ref, rbnode);758		if (WARN(ref->parent,759			 "BUG: direct ref found in indirect tree")) {760			ret = -EINVAL;761			goto out;762		}763 764		rb_erase_cached(&ref->rbnode, &preftrees->indirect.root);765		preftrees->indirect.count--;766 767		if (ref->count == 0) {768			free_pref(ref);769			continue;770		}771 772		if (sc && ref->root_id != btrfs_root_id(sc->root)) {773			free_pref(ref);774			ret = BACKREF_FOUND_SHARED;775			goto out;776		}777		err = resolve_indirect_ref(ctx, path, preftrees, ref, parents);778		/*779		 * we can only tolerate ENOENT,otherwise,we should catch error780		 * and return directly.781		 */782		if (err == -ENOENT) {783			prelim_ref_insert(ctx->fs_info, &preftrees->direct, ref,784					  NULL);785			continue;786		} else if (err) {787			free_pref(ref);788			ret = err;789			goto out;790		}791 792		/* we put the first parent into the ref at hand */793		ULIST_ITER_INIT(&uiter);794		node = ulist_next(parents, &uiter);795		ref->parent = node ? node->val : 0;796		ref->inode_list = unode_aux_to_inode_list(node);797 798		/* Add a prelim_ref(s) for any other parent(s). */799		while ((node = ulist_next(parents, &uiter))) {800			struct prelim_ref *new_ref;801 802			new_ref = kmem_cache_alloc(btrfs_prelim_ref_cache,803						   GFP_NOFS);804			if (!new_ref) {805				free_pref(ref);806				ret = -ENOMEM;807				goto out;808			}809			memcpy(new_ref, ref, sizeof(*ref));810			new_ref->parent = node->val;811			new_ref->inode_list = unode_aux_to_inode_list(node);812			prelim_ref_insert(ctx->fs_info, &preftrees->direct,813					  new_ref, NULL);814		}815 816		/*817		 * Now it's a direct ref, put it in the direct tree. We must818		 * do this last because the ref could be merged/freed here.819		 */820		prelim_ref_insert(ctx->fs_info, &preftrees->direct, ref, NULL);821 822		ulist_reinit(parents);823		cond_resched();824	}825out:826	/*827	 * We may have inode lists attached to refs in the parents ulist, so we828	 * must free them before freeing the ulist and its refs.829	 */830	free_leaf_list(parents);831	return ret;832}833 834/*835 * read tree blocks and add keys where required.836 */837static int add_missing_keys(struct btrfs_fs_info *fs_info,838			    struct preftrees *preftrees, bool lock)839{840	struct prelim_ref *ref;841	struct extent_buffer *eb;842	struct preftree *tree = &preftrees->indirect_missing_keys;843	struct rb_node *node;844 845	while ((node = rb_first_cached(&tree->root))) {846		struct btrfs_tree_parent_check check = { 0 };847 848		ref = rb_entry(node, struct prelim_ref, rbnode);849		rb_erase_cached(node, &tree->root);850 851		BUG_ON(ref->parent);	/* should not be a direct ref */852		BUG_ON(ref->key_for_search.type);853		BUG_ON(!ref->wanted_disk_byte);854 855		check.level = ref->level - 1;856		check.owner_root = ref->root_id;857 858		eb = read_tree_block(fs_info, ref->wanted_disk_byte, &check);859		if (IS_ERR(eb)) {860			free_pref(ref);861			return PTR_ERR(eb);862		}863		if (!extent_buffer_uptodate(eb)) {864			free_pref(ref);865			free_extent_buffer(eb);866			return -EIO;867		}868 869		if (lock)870			btrfs_tree_read_lock(eb);871		if (btrfs_header_level(eb) == 0)872			btrfs_item_key_to_cpu(eb, &ref->key_for_search, 0);873		else874			btrfs_node_key_to_cpu(eb, &ref->key_for_search, 0);875		if (lock)876			btrfs_tree_read_unlock(eb);877		free_extent_buffer(eb);878		prelim_ref_insert(fs_info, &preftrees->indirect, ref, NULL);879		cond_resched();880	}881	return 0;882}883 884/*885 * add all currently queued delayed refs from this head whose seq nr is886 * smaller or equal that seq to the list887 */888static int add_delayed_refs(const struct btrfs_fs_info *fs_info,889			    struct btrfs_delayed_ref_head *head, u64 seq,890			    struct preftrees *preftrees, struct share_check *sc)891{892	struct btrfs_delayed_ref_node *node;893	struct btrfs_key key;894	struct rb_node *n;895	int count;896	int ret = 0;897 898	spin_lock(&head->lock);899	for (n = rb_first_cached(&head->ref_tree); n; n = rb_next(n)) {900		node = rb_entry(n, struct btrfs_delayed_ref_node,901				ref_node);902		if (node->seq > seq)903			continue;904 905		switch (node->action) {906		case BTRFS_ADD_DELAYED_EXTENT:907		case BTRFS_UPDATE_DELAYED_HEAD:908			WARN_ON(1);909			continue;910		case BTRFS_ADD_DELAYED_REF:911			count = node->ref_mod;912			break;913		case BTRFS_DROP_DELAYED_REF:914			count = node->ref_mod * -1;915			break;916		default:917			BUG();918		}919		switch (node->type) {920		case BTRFS_TREE_BLOCK_REF_KEY: {921			/* NORMAL INDIRECT METADATA backref */922			struct btrfs_key *key_ptr = NULL;923			/* The owner of a tree block ref is the level. */924			int level = btrfs_delayed_ref_owner(node);925 926			if (head->extent_op && head->extent_op->update_key) {927				btrfs_disk_key_to_cpu(&key, &head->extent_op->key);928				key_ptr = &key;929			}930 931			ret = add_indirect_ref(fs_info, preftrees, node->ref_root,932					       key_ptr, level + 1, node->bytenr,933					       count, sc, GFP_ATOMIC);934			break;935		}936		case BTRFS_SHARED_BLOCK_REF_KEY: {937			/*938			 * SHARED DIRECT METADATA backref939			 *940			 * The owner of a tree block ref is the level.941			 */942			int level = btrfs_delayed_ref_owner(node);943 944			ret = add_direct_ref(fs_info, preftrees, level + 1,945					     node->parent, node->bytenr, count,946					     sc, GFP_ATOMIC);947			break;948		}949		case BTRFS_EXTENT_DATA_REF_KEY: {950			/* NORMAL INDIRECT DATA backref */951			key.objectid = btrfs_delayed_ref_owner(node);952			key.type = BTRFS_EXTENT_DATA_KEY;953			key.offset = btrfs_delayed_ref_offset(node);954 955			/*956			 * If we have a share check context and a reference for957			 * another inode, we can't exit immediately. This is958			 * because even if this is a BTRFS_ADD_DELAYED_REF959			 * reference we may find next a BTRFS_DROP_DELAYED_REF960			 * which cancels out this ADD reference.961			 *962			 * If this is a DROP reference and there was no previous963			 * ADD reference, then we need to signal that when we964			 * process references from the extent tree (through965			 * add_inline_refs() and add_keyed_refs()), we should966			 * not exit early if we find a reference for another967			 * inode, because one of the delayed DROP references968			 * may cancel that reference in the extent tree.969			 */970			if (sc && count < 0)971				sc->have_delayed_delete_refs = true;972 973			ret = add_indirect_ref(fs_info, preftrees, node->ref_root,974					       &key, 0, node->bytenr, count, sc,975					       GFP_ATOMIC);976			break;977		}978		case BTRFS_SHARED_DATA_REF_KEY: {979			/* SHARED DIRECT FULL backref */980			ret = add_direct_ref(fs_info, preftrees, 0, node->parent,981					     node->bytenr, count, sc,982					     GFP_ATOMIC);983			break;984		}985		default:986			WARN_ON(1);987		}988		/*989		 * We must ignore BACKREF_FOUND_SHARED until all delayed990		 * refs have been checked.991		 */992		if (ret && (ret != BACKREF_FOUND_SHARED))993			break;994	}995	if (!ret)996		ret = extent_is_shared(sc);997 998	spin_unlock(&head->lock);999	return ret;1000}1001 1002/*1003 * add all inline backrefs for bytenr to the list1004 *1005 * Returns 0 on success, <0 on error, or BACKREF_FOUND_SHARED.1006 */1007static int add_inline_refs(struct btrfs_backref_walk_ctx *ctx,1008			   struct btrfs_path *path,1009			   int *info_level, struct preftrees *preftrees,1010			   struct share_check *sc)1011{1012	int ret = 0;1013	int slot;1014	struct extent_buffer *leaf;1015	struct btrfs_key key;1016	struct btrfs_key found_key;1017	unsigned long ptr;1018	unsigned long end;1019	struct btrfs_extent_item *ei;1020	u64 flags;1021	u64 item_size;1022 1023	/*1024	 * enumerate all inline refs1025	 */1026	leaf = path->nodes[0];1027	slot = path->slots[0];1028 1029	item_size = btrfs_item_size(leaf, slot);1030	ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);1031 1032	if (ctx->check_extent_item) {1033		ret = ctx->check_extent_item(ctx->bytenr, ei, leaf, ctx->user_ctx);1034		if (ret)1035			return ret;1036	}1037 1038	flags = btrfs_extent_flags(leaf, ei);1039	btrfs_item_key_to_cpu(leaf, &found_key, slot);1040 1041	ptr = (unsigned long)(ei + 1);1042	end = (unsigned long)ei + item_size;1043 1044	if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&1045	    flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {1046		struct btrfs_tree_block_info *info;1047 1048		info = (struct btrfs_tree_block_info *)ptr;1049		*info_level = btrfs_tree_block_level(leaf, info);1050		ptr += sizeof(struct btrfs_tree_block_info);1051		BUG_ON(ptr > end);1052	} else if (found_key.type == BTRFS_METADATA_ITEM_KEY) {1053		*info_level = found_key.offset;1054	} else {1055		BUG_ON(!(flags & BTRFS_EXTENT_FLAG_DATA));1056	}1057 1058	while (ptr < end) {1059		struct btrfs_extent_inline_ref *iref;1060		u64 offset;1061		int type;1062 1063		iref = (struct btrfs_extent_inline_ref *)ptr;1064		type = btrfs_get_extent_inline_ref_type(leaf, iref,1065							BTRFS_REF_TYPE_ANY);1066		if (type == BTRFS_REF_TYPE_INVALID)1067			return -EUCLEAN;1068 1069		offset = btrfs_extent_inline_ref_offset(leaf, iref);1070 1071		switch (type) {1072		case BTRFS_SHARED_BLOCK_REF_KEY:1073			ret = add_direct_ref(ctx->fs_info, preftrees,1074					     *info_level + 1, offset,1075					     ctx->bytenr, 1, NULL, GFP_NOFS);1076			break;1077		case BTRFS_SHARED_DATA_REF_KEY: {1078			struct btrfs_shared_data_ref *sdref;1079			int count;1080 1081			sdref = (struct btrfs_shared_data_ref *)(iref + 1);1082			count = btrfs_shared_data_ref_count(leaf, sdref);1083 1084			ret = add_direct_ref(ctx->fs_info, preftrees, 0, offset,1085					     ctx->bytenr, count, sc, GFP_NOFS);1086			break;1087		}1088		case BTRFS_TREE_BLOCK_REF_KEY:1089			ret = add_indirect_ref(ctx->fs_info, preftrees, offset,1090					       NULL, *info_level + 1,1091					       ctx->bytenr, 1, NULL, GFP_NOFS);1092			break;1093		case BTRFS_EXTENT_DATA_REF_KEY: {1094			struct btrfs_extent_data_ref *dref;1095			int count;1096			u64 root;1097 1098			dref = (struct btrfs_extent_data_ref *)(&iref->offset);1099			count = btrfs_extent_data_ref_count(leaf, dref);1100			key.objectid = btrfs_extent_data_ref_objectid(leaf,1101								      dref);1102			key.type = BTRFS_EXTENT_DATA_KEY;1103			key.offset = btrfs_extent_data_ref_offset(leaf, dref);1104 1105			if (sc && key.objectid != sc->inum &&1106			    !sc->have_delayed_delete_refs) {1107				ret = BACKREF_FOUND_SHARED;1108				break;1109			}1110 1111			root = btrfs_extent_data_ref_root(leaf, dref);1112 1113			if (!ctx->skip_data_ref ||1114			    !ctx->skip_data_ref(root, key.objectid, key.offset,1115						ctx->user_ctx))1116				ret = add_indirect_ref(ctx->fs_info, preftrees,1117						       root, &key, 0, ctx->bytenr,1118						       count, sc, GFP_NOFS);1119			break;1120		}1121		case BTRFS_EXTENT_OWNER_REF_KEY:1122			ASSERT(btrfs_fs_incompat(ctx->fs_info, SIMPLE_QUOTA));1123			break;1124		default:1125			WARN_ON(1);1126		}1127		if (ret)1128			return ret;1129		ptr += btrfs_extent_inline_ref_size(type);1130	}1131 1132	return 0;1133}1134 1135/*1136 * add all non-inline backrefs for bytenr to the list1137 *1138 * Returns 0 on success, <0 on error, or BACKREF_FOUND_SHARED.1139 */1140static int add_keyed_refs(struct btrfs_backref_walk_ctx *ctx,1141			  struct btrfs_root *extent_root,1142			  struct btrfs_path *path,1143			  int info_level, struct preftrees *preftrees,1144			  struct share_check *sc)1145{1146	struct btrfs_fs_info *fs_info = extent_root->fs_info;1147	int ret;1148	int slot;1149	struct extent_buffer *leaf;1150	struct btrfs_key key;1151 1152	while (1) {1153		ret = btrfs_next_item(extent_root, path);1154		if (ret < 0)1155			break;1156		if (ret) {1157			ret = 0;1158			break;1159		}1160 1161		slot = path->slots[0];1162		leaf = path->nodes[0];1163		btrfs_item_key_to_cpu(leaf, &key, slot);1164 1165		if (key.objectid != ctx->bytenr)1166			break;1167		if (key.type < BTRFS_TREE_BLOCK_REF_KEY)1168			continue;1169		if (key.type > BTRFS_SHARED_DATA_REF_KEY)1170			break;1171 1172		switch (key.type) {1173		case BTRFS_SHARED_BLOCK_REF_KEY:1174			/* SHARED DIRECT METADATA backref */1175			ret = add_direct_ref(fs_info, preftrees,1176					     info_level + 1, key.offset,1177					     ctx->bytenr, 1, NULL, GFP_NOFS);1178			break;1179		case BTRFS_SHARED_DATA_REF_KEY: {1180			/* SHARED DIRECT FULL backref */1181			struct btrfs_shared_data_ref *sdref;1182			int count;1183 1184			sdref = btrfs_item_ptr(leaf, slot,1185					      struct btrfs_shared_data_ref);1186			count = btrfs_shared_data_ref_count(leaf, sdref);1187			ret = add_direct_ref(fs_info, preftrees, 0,1188					     key.offset, ctx->bytenr, count,1189					     sc, GFP_NOFS);1190			break;1191		}1192		case BTRFS_TREE_BLOCK_REF_KEY:1193			/* NORMAL INDIRECT METADATA backref */1194			ret = add_indirect_ref(fs_info, preftrees, key.offset,1195					       NULL, info_level + 1, ctx->bytenr,1196					       1, NULL, GFP_NOFS);1197			break;1198		case BTRFS_EXTENT_DATA_REF_KEY: {1199			/* NORMAL INDIRECT DATA backref */1200			struct btrfs_extent_data_ref *dref;1201			int count;1202			u64 root;1203 1204			dref = btrfs_item_ptr(leaf, slot,1205					      struct btrfs_extent_data_ref);1206			count = btrfs_extent_data_ref_count(leaf, dref);1207			key.objectid = btrfs_extent_data_ref_objectid(leaf,1208								      dref);1209			key.type = BTRFS_EXTENT_DATA_KEY;1210			key.offset = btrfs_extent_data_ref_offset(leaf, dref);1211 1212			if (sc && key.objectid != sc->inum &&1213			    !sc->have_delayed_delete_refs) {1214				ret = BACKREF_FOUND_SHARED;1215				break;1216			}1217 1218			root = btrfs_extent_data_ref_root(leaf, dref);1219 1220			if (!ctx->skip_data_ref ||1221			    !ctx->skip_data_ref(root, key.objectid, key.offset,1222						ctx->user_ctx))1223				ret = add_indirect_ref(fs_info, preftrees, root,1224						       &key, 0, ctx->bytenr,1225						       count, sc, GFP_NOFS);1226			break;1227		}1228		default:1229			WARN_ON(1);1230		}1231		if (ret)1232			return ret;1233 1234	}1235 1236	return ret;1237}1238 1239/*1240 * The caller has joined a transaction or is holding a read lock on the1241 * fs_info->commit_root_sem semaphore, so no need to worry about the root's last1242 * snapshot field changing while updating or checking the cache.1243 */1244static bool lookup_backref_shared_cache(struct btrfs_backref_share_check_ctx *ctx,1245					struct btrfs_root *root,1246					u64 bytenr, int level, bool *is_shared)1247{1248	const struct btrfs_fs_info *fs_info = root->fs_info;1249	struct btrfs_backref_shared_cache_entry *entry;1250 1251	if (!current->journal_info)1252		lockdep_assert_held(&fs_info->commit_root_sem);1253 1254	if (!ctx->use_path_cache)1255		return false;1256 1257	if (WARN_ON_ONCE(level >= BTRFS_MAX_LEVEL))1258		return false;1259 1260	/*1261	 * Level -1 is used for the data extent, which is not reliable to cache1262	 * because its reference count can increase or decrease without us1263	 * realizing. We cache results only for extent buffers that lead from1264	 * the root node down to the leaf with the file extent item.1265	 */1266	ASSERT(level >= 0);1267 1268	entry = &ctx->path_cache_entries[level];1269 1270	/* Unused cache entry or being used for some other extent buffer. */1271	if (entry->bytenr != bytenr)1272		return false;1273 1274	/*1275	 * We cached a false result, but the last snapshot generation of the1276	 * root changed, so we now have a snapshot. Don't trust the result.1277	 */1278	if (!entry->is_shared &&1279	    entry->gen != btrfs_root_last_snapshot(&root->root_item))1280		return false;1281 1282	/*1283	 * If we cached a true result and the last generation used for dropping1284	 * a root changed, we can not trust the result, because the dropped root1285	 * could be a snapshot sharing this extent buffer.1286	 */1287	if (entry->is_shared &&1288	    entry->gen != btrfs_get_last_root_drop_gen(fs_info))1289		return false;1290 1291	*is_shared = entry->is_shared;1292	/*1293	 * If the node at this level is shared, than all nodes below are also1294	 * shared. Currently some of the nodes below may be marked as not shared1295	 * because we have just switched from one leaf to another, and switched1296	 * also other nodes above the leaf and below the current level, so mark1297	 * them as shared.1298	 */1299	if (*is_shared) {1300		for (int i = 0; i < level; i++) {1301			ctx->path_cache_entries[i].is_shared = true;1302			ctx->path_cache_entries[i].gen = entry->gen;1303		}1304	}1305 1306	return true;1307}1308 1309/*1310 * The caller has joined a transaction or is holding a read lock on the1311 * fs_info->commit_root_sem semaphore, so no need to worry about the root's last1312 * snapshot field changing while updating or checking the cache.1313 */1314static void store_backref_shared_cache(struct btrfs_backref_share_check_ctx *ctx,1315				       struct btrfs_root *root,1316				       u64 bytenr, int level, bool is_shared)1317{1318	const struct btrfs_fs_info *fs_info = root->fs_info;1319	struct btrfs_backref_shared_cache_entry *entry;1320	u64 gen;1321 1322	if (!current->journal_info)1323		lockdep_assert_held(&fs_info->commit_root_sem);1324 1325	if (!ctx->use_path_cache)1326		return;1327 1328	if (WARN_ON_ONCE(level >= BTRFS_MAX_LEVEL))1329		return;1330 1331	/*1332	 * Level -1 is used for the data extent, which is not reliable to cache1333	 * because its reference count can increase or decrease without us1334	 * realizing. We cache results only for extent buffers that lead from1335	 * the root node down to the leaf with the file extent item.1336	 */1337	ASSERT(level >= 0);1338 1339	if (is_shared)1340		gen = btrfs_get_last_root_drop_gen(fs_info);1341	else1342		gen = btrfs_root_last_snapshot(&root->root_item);1343 1344	entry = &ctx->path_cache_entries[level];1345	entry->bytenr = bytenr;1346	entry->is_shared = is_shared;1347	entry->gen = gen;1348 1349	/*1350	 * If we found an extent buffer is shared, set the cache result for all1351	 * extent buffers below it to true. As nodes in the path are COWed,1352	 * their sharedness is moved to their children, and if a leaf is COWed,1353	 * then the sharedness of a data extent becomes direct, the refcount of1354	 * data extent is increased in the extent item at the extent tree.1355	 */1356	if (is_shared) {1357		for (int i = 0; i < level; i++) {1358			entry = &ctx->path_cache_entries[i];1359			entry->is_shared = is_shared;1360			entry->gen = gen;1361		}1362	}1363}1364 1365/*1366 * this adds all existing backrefs (inline backrefs, backrefs and delayed1367 * refs) for the given bytenr to the refs list, merges duplicates and resolves1368 * indirect refs to their parent bytenr.1369 * When roots are found, they're added to the roots list1370 *1371 * @ctx:     Backref walking context object, must be not NULL.1372 * @sc:      If !NULL, then immediately return BACKREF_FOUND_SHARED when a1373 *           shared extent is detected.1374 *1375 * Otherwise this returns 0 for success and <0 for an error.1376 *1377 * FIXME some caching might speed things up1378 */1379static int find_parent_nodes(struct btrfs_backref_walk_ctx *ctx,1380			     struct share_check *sc)1381{1382	struct btrfs_root *root = btrfs_extent_root(ctx->fs_info, ctx->bytenr);1383	struct btrfs_key key;1384	struct btrfs_path *path;1385	struct btrfs_delayed_ref_root *delayed_refs = NULL;1386	struct btrfs_delayed_ref_head *head;1387	int info_level = 0;1388	int ret;1389	struct prelim_ref *ref;1390	struct rb_node *node;1391	struct extent_inode_elem *eie = NULL;1392	struct preftrees preftrees = {1393		.direct = PREFTREE_INIT,1394		.indirect = PREFTREE_INIT,1395		.indirect_missing_keys = PREFTREE_INIT1396	};1397 1398	/* Roots ulist is not needed when using a sharedness check context. */1399	if (sc)1400		ASSERT(ctx->roots == NULL);1401 1402	key.objectid = ctx->bytenr;1403	key.offset = (u64)-1;1404	if (btrfs_fs_incompat(ctx->fs_info, SKINNY_METADATA))1405		key.type = BTRFS_METADATA_ITEM_KEY;1406	else1407		key.type = BTRFS_EXTENT_ITEM_KEY;1408 1409	path = btrfs_alloc_path();1410	if (!path)1411		return -ENOMEM;1412	if (!ctx->trans) {1413		path->search_commit_root = 1;1414		path->skip_locking = 1;1415	}1416 1417	if (ctx->time_seq == BTRFS_SEQ_LAST)1418		path->skip_locking = 1;1419 1420again:1421	head = NULL;1422 1423	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);1424	if (ret < 0)1425		goto out;1426	if (ret == 0) {1427		/*1428		 * Key with offset -1 found, there would have to exist an extent1429		 * item with such offset, but this is out of the valid range.1430		 */1431		ret = -EUCLEAN;1432		goto out;1433	}1434 1435	if (ctx->trans && likely(ctx->trans->type != __TRANS_DUMMY) &&1436	    ctx->time_seq != BTRFS_SEQ_LAST) {1437		/*1438		 * We have a specific time_seq we care about and trans which1439		 * means we have the path lock, we need to grab the ref head and1440		 * lock it so we have a consistent view of the refs at the given1441		 * time.1442		 */1443		delayed_refs = &ctx->trans->transaction->delayed_refs;1444		spin_lock(&delayed_refs->lock);1445		head = btrfs_find_delayed_ref_head(delayed_refs, ctx->bytenr);1446		if (head) {1447			if (!mutex_trylock(&head->mutex)) {1448				refcount_inc(&head->refs);1449				spin_unlock(&delayed_refs->lock);1450 1451				btrfs_release_path(path);1452 1453				/*1454				 * Mutex was contended, block until it's1455				 * released and try again1456				 */1457				mutex_lock(&head->mutex);1458				mutex_unlock(&head->mutex);1459				btrfs_put_delayed_ref_head(head);1460				goto again;1461			}1462			spin_unlock(&delayed_refs->lock);1463			ret = add_delayed_refs(ctx->fs_info, head, ctx->time_seq,1464					       &preftrees, sc);1465			mutex_unlock(&head->mutex);1466			if (ret)1467				goto out;1468		} else {1469			spin_unlock(&delayed_refs->lock);1470		}1471	}1472 1473	if (path->slots[0]) {1474		struct extent_buffer *leaf;1475		int slot;1476 1477		path->slots[0]--;1478		leaf = path->nodes[0];1479		slot = path->slots[0];1480		btrfs_item_key_to_cpu(leaf, &key, slot);1481		if (key.objectid == ctx->bytenr &&1482		    (key.type == BTRFS_EXTENT_ITEM_KEY ||1483		     key.type == BTRFS_METADATA_ITEM_KEY)) {1484			ret = add_inline_refs(ctx, path, &info_level,1485					      &preftrees, sc);1486			if (ret)1487				goto out;1488			ret = add_keyed_refs(ctx, root, path, info_level,1489					     &preftrees, sc);1490			if (ret)1491				goto out;1492		}1493	}1494 1495	/*1496	 * If we have a share context and we reached here, it means the extent1497	 * is not directly shared (no multiple reference items for it),1498	 * otherwise we would have exited earlier with a return value of1499	 * BACKREF_FOUND_SHARED after processing delayed references or while1500	 * processing inline or keyed references from the extent tree.1501	 * The extent may however be indirectly shared through shared subtrees1502	 * as a result from creating snapshots, so we determine below what is1503	 * its parent node, in case we are dealing with a metadata extent, or1504	 * what's the leaf (or leaves), from a fs tree, that has a file extent1505	 * item pointing to it in case we are dealing with a data extent.1506	 */1507	ASSERT(extent_is_shared(sc) == 0);1508 1509	/*1510	 * If we are here for a data extent and we have a share_check structure1511	 * it means the data extent is not directly shared (does not have1512	 * multiple reference items), so we have to check if a path in the fs1513	 * tree (going from the root node down to the leaf that has the file1514	 * extent item pointing to the data extent) is shared, that is, if any1515	 * of the extent buffers in the path is referenced by other trees.1516	 */1517	if (sc && ctx->bytenr == sc->data_bytenr) {1518		/*1519		 * If our data extent is from a generation more recent than the1520		 * last generation used to snapshot the root, then we know that1521		 * it can not be shared through subtrees, so we can skip1522		 * resolving indirect references, there's no point in1523		 * determining the extent buffers for the path from the fs tree1524		 * root node down to the leaf that has the file extent item that1525		 * points to the data extent.1526		 */1527		if (sc->data_extent_gen >1528		    btrfs_root_last_snapshot(&sc->root->root_item)) {1529			ret = BACKREF_FOUND_NOT_SHARED;1530			goto out;1531		}1532 1533		/*1534		 * If we are only determining if a data extent is shared or not1535		 * and the corresponding file extent item is located in the same1536		 * leaf as the previous file extent item, we can skip resolving1537		 * indirect references for a data extent, since the fs tree path1538		 * is the same (same leaf, so same path). We skip as long as the1539		 * cached result for the leaf is valid and only if there's only1540		 * one file extent item pointing to the data extent, because in1541		 * the case of multiple file extent items, they may be located1542		 * in different leaves and therefore we have multiple paths.1543		 */1544		if (sc->ctx->curr_leaf_bytenr == sc->ctx->prev_leaf_bytenr &&1545		    sc->self_ref_count == 1) {1546			bool cached;1547			bool is_shared;1548 1549			cached = lookup_backref_shared_cache(sc->ctx, sc->root,1550						     sc->ctx->curr_leaf_bytenr,1551						     0, &is_shared);1552			if (cached) {1553				if (is_shared)1554					ret = BACKREF_FOUND_SHARED;1555				else1556					ret = BACKREF_FOUND_NOT_SHARED;1557				goto out;1558			}1559		}1560	}1561 1562	btrfs_release_path(path);1563 1564	ret = add_missing_keys(ctx->fs_info, &preftrees, path->skip_locking == 0);1565	if (ret)1566		goto out;1567 1568	WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect_missing_keys.root.rb_root));1569 1570	ret = resolve_indirect_refs(ctx, path, &preftrees, sc);1571	if (ret)1572		goto out;1573 1574	WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect.root.rb_root));1575 1576	/*1577	 * This walks the tree of merged and resolved refs. Tree blocks are1578	 * read in as needed. Unique entries are added to the ulist, and1579	 * the list of found roots is updated.1580	 *1581	 * We release the entire tree in one go before returning.1582	 */1583	node = rb_first_cached(&preftrees.direct.root);1584	while (node) {1585		ref = rb_entry(node, struct prelim_ref, rbnode);1586		node = rb_next(&ref->rbnode);1587		/*1588		 * ref->count < 0 can happen here if there are delayed1589		 * refs with a node->action of BTRFS_DROP_DELAYED_REF.1590		 * prelim_ref_insert() relies on this when merging1591		 * identical refs to keep the overall count correct.1592		 * prelim_ref_insert() will merge only those refs1593		 * which compare identically.  Any refs having1594		 * e.g. different offsets would not be merged,1595		 * and would retain their original ref->count < 0.1596		 */1597		if (ctx->roots && ref->count && ref->root_id && ref->parent == 0) {1598			/* no parent == root of tree */1599			ret = ulist_add(ctx->roots, ref->root_id, 0, GFP_NOFS);1600			if (ret < 0)1601				goto out;1602		}1603		if (ref->count && ref->parent) {1604			if (!ctx->skip_inode_ref_list && !ref->inode_list &&1605			    ref->level == 0) {1606				struct btrfs_tree_parent_check check = { 0 };1607				struct extent_buffer *eb;1608 1609				check.level = ref->level;1610 1611				eb = read_tree_block(ctx->fs_info, ref->parent,1612						     &check);1613				if (IS_ERR(eb)) {1614					ret = PTR_ERR(eb);1615					goto out;1616				}1617				if (!extent_buffer_uptodate(eb)) {1618					free_extent_buffer(eb);1619					ret = -EIO;1620					goto out;1621				}1622 1623				if (!path->skip_locking)1624					btrfs_tree_read_lock(eb);1625				ret = find_extent_in_eb(ctx, eb, &eie);1626				if (!path->skip_locking)1627					btrfs_tree_read_unlock(eb);1628				free_extent_buffer(eb);1629				if (ret == BTRFS_ITERATE_EXTENT_INODES_STOP ||1630				    ret < 0)1631					goto out;1632				ref->inode_list = eie;1633				/*1634				 * We transferred the list ownership to the ref,1635				 * so set to NULL to avoid a double free in case1636				 * an error happens after this.1637				 */1638				eie = NULL;1639			}1640			ret = ulist_add_merge_ptr(ctx->refs, ref->parent,1641						  ref->inode_list,1642						  (void **)&eie, GFP_NOFS);1643			if (ret < 0)1644				goto out;1645			if (!ret && !ctx->skip_inode_ref_list) {1646				/*1647				 * We've recorded that parent, so we must extend1648				 * its inode list here.1649				 *1650				 * However if there was corruption we may not1651				 * have found an eie, return an error in this1652				 * case.1653				 */1654				ASSERT(eie);1655				if (!eie) {1656					ret = -EUCLEAN;1657					goto out;1658				}1659				while (eie->next)1660					eie = eie->next;1661				eie->next = ref->inode_list;1662			}1663			eie = NULL;1664			/*1665			 * We have transferred the inode list ownership from1666			 * this ref to the ref we added to the 'refs' ulist.1667			 * So set this ref's inode list to NULL to avoid1668			 * use-after-free when our caller uses it or double1669			 * frees in case an error happens before we return.1670			 */1671			ref->inode_list = NULL;1672		}1673		cond_resched();1674	}1675 1676out:1677	btrfs_free_path(path);1678 1679	prelim_release(&preftrees.direct);1680	prelim_release(&preftrees.indirect);1681	prelim_release(&preftrees.indirect_missing_keys);1682 1683	if (ret == BTRFS_ITERATE_EXTENT_INODES_STOP || ret < 0)1684		free_inode_elem_list(eie);1685	return ret;1686}1687 1688/*1689 * Finds all leaves with a reference to the specified combination of1690 * @ctx->bytenr and @ctx->extent_item_pos. The bytenr of the found leaves are1691 * added to the ulist at @ctx->refs, and that ulist is allocated by this1692 * function. The caller should free the ulist with free_leaf_list() if1693 * @ctx->ignore_extent_item_pos is false, otherwise a fimple ulist_free() is1694 * enough.1695 *1696 * Returns 0 on success and < 0 on error. On error @ctx->refs is not allocated.1697 */1698int btrfs_find_all_leafs(struct btrfs_backref_walk_ctx *ctx)1699{1700	int ret;1701 1702	ASSERT(ctx->refs == NULL);1703 1704	ctx->refs = ulist_alloc(GFP_NOFS);1705	if (!ctx->refs)1706		return -ENOMEM;1707 1708	ret = find_parent_nodes(ctx, NULL);1709	if (ret == BTRFS_ITERATE_EXTENT_INODES_STOP ||1710	    (ret < 0 && ret != -ENOENT)) {1711		free_leaf_list(ctx->refs);1712		ctx->refs = NULL;1713		return ret;1714	}1715 1716	return 0;1717}1718 1719/*1720 * Walk all backrefs for a given extent to find all roots that reference this1721 * extent. Walking a backref means finding all extents that reference this1722 * extent and in turn walk the backrefs of those, too. Naturally this is a1723 * recursive process, but here it is implemented in an iterative fashion: We1724 * find all referencing extents for the extent in question and put them on a1725 * list. In turn, we find all referencing extents for those, further appending1726 * to the list. The way we iterate the list allows adding more elements after1727 * the current while iterating. The process stops when we reach the end of the1728 * list.1729 *1730 * Found roots are added to @ctx->roots, which is allocated by this function if1731 * it points to NULL, in which case the caller is responsible for freeing it1732 * after it's not needed anymore.1733 * This function requires @ctx->refs to be NULL, as it uses it for allocating a1734 * ulist to do temporary work, and frees it before returning.1735 *1736 * Returns 0 on success, < 0 on error.1737 */1738static int btrfs_find_all_roots_safe(struct btrfs_backref_walk_ctx *ctx)1739{1740	const u64 orig_bytenr = ctx->bytenr;1741	const bool orig_skip_inode_ref_list = ctx->skip_inode_ref_list;1742	bool roots_ulist_allocated = false;1743	struct ulist_iterator uiter;1744	int ret = 0;1745 1746	ASSERT(ctx->refs == NULL);1747 1748	ctx->refs = ulist_alloc(GFP_NOFS);1749	if (!ctx->refs)1750		return -ENOMEM;1751 1752	if (!ctx->roots) {1753		ctx->roots = ulist_alloc(GFP_NOFS);1754		if (!ctx->roots) {1755			ulist_free(ctx->refs);1756			ctx->refs = NULL;1757			return -ENOMEM;1758		}1759		roots_ulist_allocated = true;1760	}1761 1762	ctx->skip_inode_ref_list = true;1763 1764	ULIST_ITER_INIT(&uiter);1765	while (1) {1766		struct ulist_node *node;1767 1768		ret = find_parent_nodes(ctx, NULL);1769		if (ret < 0 && ret != -ENOENT) {1770			if (roots_ulist_allocated) {1771				ulist_free(ctx->roots);1772				ctx->roots = NULL;1773			}1774			break;1775		}1776		ret = 0;1777		node = ulist_next(ctx->refs, &uiter);1778		if (!node)1779			break;1780		ctx->bytenr = node->val;1781		cond_resched();1782	}1783 1784	ulist_free(ctx->refs);1785	ctx->refs = NULL;1786	ctx->bytenr = orig_bytenr;1787	ctx->skip_inode_ref_list = orig_skip_inode_ref_list;1788 1789	return ret;1790}1791 1792int btrfs_find_all_roots(struct btrfs_backref_walk_ctx *ctx,1793			 bool skip_commit_root_sem)1794{1795	int ret;1796 1797	if (!ctx->trans && !skip_commit_root_sem)1798		down_read(&ctx->fs_info->commit_root_sem);1799	ret = btrfs_find_all_roots_safe(ctx);1800	if (!ctx->trans && !skip_commit_root_sem)1801		up_read(&ctx->fs_info->commit_root_sem);1802	return ret;1803}1804 1805struct btrfs_backref_share_check_ctx *btrfs_alloc_backref_share_check_ctx(void)1806{1807	struct btrfs_backref_share_check_ctx *ctx;1808 1809	ctx = kzalloc(sizeof(*ctx), GFP_KERNEL);1810	if (!ctx)1811		return NULL;1812 1813	ulist_init(&ctx->refs);1814 1815	return ctx;1816}1817 1818void btrfs_free_backref_share_ctx(struct btrfs_backref_share_check_ctx *ctx)1819{1820	if (!ctx)1821		return;1822 1823	ulist_release(&ctx->refs);1824	kfree(ctx);1825}1826 1827/*1828 * Check if a data extent is shared or not.1829 *1830 * @inode:       The inode whose extent we are checking.1831 * @bytenr:      Logical bytenr of the extent we are checking.1832 * @extent_gen:  Generation of the extent (file extent item) or 0 if it is1833 *               not known.1834 * @ctx:         A backref sharedness check context.1835 *1836 * btrfs_is_data_extent_shared uses the backref walking code but will short1837 * circuit as soon as it finds a root or inode that doesn't match the1838 * one passed in. This provides a significant performance benefit for1839 * callers (such as fiemap) which want to know whether the extent is1840 * shared but do not need a ref count.1841 *1842 * This attempts to attach to the running transaction in order to account for1843 * delayed refs, but continues on even when no running transaction exists.1844 *1845 * Return: 0 if extent is not shared, 1 if it is shared, < 0 on error.1846 */1847int btrfs_is_data_extent_shared(struct btrfs_inode *inode, u64 bytenr,1848				u64 extent_gen,1849				struct btrfs_backref_share_check_ctx *ctx)1850{1851	struct btrfs_backref_walk_ctx walk_ctx = { 0 };1852	struct btrfs_root *root = inode->root;1853	struct btrfs_fs_info *fs_info = root->fs_info;1854	struct btrfs_trans_handle *trans;1855	struct ulist_iterator uiter;1856	struct ulist_node *node;1857	struct btrfs_seq_list elem = BTRFS_SEQ_LIST_INIT(elem);1858	int ret = 0;1859	struct share_check shared = {1860		.ctx = ctx,1861		.root = root,1862		.inum = btrfs_ino(inode),1863		.data_bytenr = bytenr,1864		.data_extent_gen = extent_gen,1865		.share_count = 0,1866		.self_ref_count = 0,1867		.have_delayed_delete_refs = false,1868	};1869	int level;1870	bool leaf_cached;1871	bool leaf_is_shared;1872 1873	for (int i = 0; i < BTRFS_BACKREF_CTX_PREV_EXTENTS_SIZE; i++) {1874		if (ctx->prev_extents_cache[i].bytenr == bytenr)1875			return ctx->prev_extents_cache[i].is_shared;1876	}1877 1878	ulist_init(&ctx->refs);1879 1880	trans = btrfs_join_transaction_nostart(root);1881	if (IS_ERR(trans)) {1882		if (PTR_ERR(trans) != -ENOENT && PTR_ERR(trans) != -EROFS) {1883			ret = PTR_ERR(trans);1884			goto out;1885		}1886		trans = NULL;1887		down_read(&fs_info->commit_root_sem);1888	} else {1889		btrfs_get_tree_mod_seq(fs_info, &elem);1890		walk_ctx.time_seq = elem.seq;1891	}1892 1893	ctx->use_path_cache = true;1894 1895	/*1896	 * We may have previously determined that the current leaf is shared.1897	 * If it is, then we have a data extent that is shared due to a shared1898	 * subtree (caused by snapshotting) and we don't need to check for data1899	 * backrefs. If the leaf is not shared, then we must do backref walking1900	 * to determine if the data extent is shared through reflinks.1901	 */1902	leaf_cached = lookup_backref_shared_cache(ctx, root,1903						  ctx->curr_leaf_bytenr, 0,1904						  &leaf_is_shared);1905	if (leaf_cached && leaf_is_shared) {1906		ret = 1;1907		goto out_trans;1908	}1909 1910	walk_ctx.skip_inode_ref_list = true;1911	walk_ctx.trans = trans;1912	walk_ctx.fs_info = fs_info;1913	walk_ctx.refs = &ctx->refs;1914 1915	/* -1 means we are in the bytenr of the data extent. */1916	level = -1;1917	ULIST_ITER_INIT(&uiter);1918	while (1) {1919		const unsigned long prev_ref_count = ctx->refs.nnodes;1920 1921		walk_ctx.bytenr = bytenr;1922		ret = find_parent_nodes(&walk_ctx, &shared);1923		if (ret == BACKREF_FOUND_SHARED ||1924		    ret == BACKREF_FOUND_NOT_SHARED) {1925			/* If shared must return 1, otherwise return 0. */1926			ret = (ret == BACKREF_FOUND_SHARED) ? 1 : 0;1927			if (level >= 0)1928				store_backref_shared_cache(ctx, root, bytenr,1929							   level, ret == 1);1930			break;1931		}1932		if (ret < 0 && ret != -ENOENT)1933			break;1934		ret = 0;1935 1936		/*1937		 * More than one extent buffer (bytenr) may have been added to1938		 * the ctx->refs ulist, in which case we have to check multiple1939		 * tree paths in case the first one is not shared, so we can not1940		 * use the path cache which is made for a single path. Multiple1941		 * extent buffers at the current level happen when:1942		 *1943		 * 1) level -1, the data extent: If our data extent was not1944		 *    directly shared (without multiple reference items), then1945		 *    it might have a single reference item with a count > 1 for1946		 *    the same offset, which means there are 2 (or more) file1947		 *    extent items that point to the data extent - this happens1948		 *    when a file extent item needs to be split and then one1949		 *    item gets moved to another leaf due to a b+tree leaf split1950		 *    when inserting some item. In this case the file extent1951		 *    items may be located in different leaves and therefore1952		 *    some of the leaves may be referenced through shared1953		 *    subtrees while others are not. Since our extent buffer1954		 *    cache only works for a single path (by far the most common1955		 *    case and simpler to deal with), we can not use it if we1956		 *    have multiple leaves (which implies multiple paths).1957		 *1958		 * 2) level >= 0, a tree node/leaf: We can have a mix of direct1959		 *    and indirect references on a b+tree node/leaf, so we have1960		 *    to check multiple paths, and the extent buffer (the1961		 *    current bytenr) may be shared or not. One example is1962		 *    during relocation as we may get a shared tree block ref1963		 *    (direct ref) and a non-shared tree block ref (indirect1964		 *    ref) for the same node/leaf.1965		 */1966		if ((ctx->refs.nnodes - prev_ref_count) > 1)1967			ctx->use_path_cache = false;1968 1969		if (level >= 0)1970			store_backref_shared_cache(ctx, root, bytenr,1971						   level, false);1972		node = ulist_next(&ctx->refs, &uiter);1973		if (!node)1974			break;1975		bytenr = node->val;1976		if (ctx->use_path_cache) {1977			bool is_shared;1978			bool cached;1979 1980			level++;1981			cached = lookup_backref_shared_cache(ctx, root, bytenr,1982							     level, &is_shared);1983			if (cached) {1984				ret = (is_shared ? 1 : 0);1985				break;1986			}1987		}1988		shared.share_count = 0;1989		shared.have_delayed_delete_refs = false;1990		cond_resched();1991	}1992 1993	/*1994	 * If the path cache is disabled, then it means at some tree level we1995	 * got multiple parents due to a mix of direct and indirect backrefs or1996	 * multiple leaves with file extent items pointing to the same data1997	 * extent. We have to invalidate the cache and cache only the sharedness1998	 * result for the levels where we got only one node/reference.1999	 */2000	if (!ctx->use_path_cache) {2001		int i = 0;2002 2003		level--;2004		if (ret >= 0 && level >= 0) {2005			bytenr = ctx->path_cache_entries[level].bytenr;2006			ctx->use_path_cache = true;2007			store_backref_shared_cache(ctx, root, bytenr, level, ret);2008			i = level + 1;2009		}2010 2011		for ( ; i < BTRFS_MAX_LEVEL; i++)2012			ctx->path_cache_entries[i].bytenr = 0;2013	}2014 2015	/*2016	 * Cache the sharedness result for the data extent if we know our inode2017	 * has more than 1 file extent item that refers to the data extent.2018	 */2019	if (ret >= 0 && shared.self_ref_count > 1) {2020		int slot = ctx->prev_extents_cache_slot;2021 2022		ctx->prev_extents_cache[slot].bytenr = shared.data_bytenr;2023		ctx->prev_extents_cache[slot].is_shared = (ret == 1);2024 2025		slot = (slot + 1) % BTRFS_BACKREF_CTX_PREV_EXTENTS_SIZE;2026		ctx->prev_extents_cache_slot = slot;2027	}2028 2029out_trans:2030	if (trans) {2031		btrfs_put_tree_mod_seq(fs_info, &elem);2032		btrfs_end_transaction(trans);2033	} else {2034		up_read(&fs_info->commit_root_sem);2035	}2036out:2037	ulist_release(&ctx->refs);2038	ctx->prev_leaf_bytenr = ctx->curr_leaf_bytenr;2039 2040	return ret;2041}2042 2043int btrfs_find_one_extref(struct btrfs_root *root, u64 inode_objectid,2044			  u64 start_off, struct btrfs_path *path,2045			  struct btrfs_inode_extref **ret_extref,2046			  u64 *found_off)2047{2048	int ret, slot;2049	struct btrfs_key key;2050	struct btrfs_key found_key;2051	struct btrfs_inode_extref *extref;2052	const struct extent_buffer *leaf;2053	unsigned long ptr;2054 2055	key.objectid = inode_objectid;2056	key.type = BTRFS_INODE_EXTREF_KEY;2057	key.offset = start_off;2058 2059	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);2060	if (ret < 0)2061		return ret;2062 2063	while (1) {2064		leaf = path->nodes[0];2065		slot = path->slots[0];2066		if (slot >= btrfs_header_nritems(leaf)) {2067			/*2068			 * If the item at offset is not found,2069			 * btrfs_search_slot will point us to the slot2070			 * where it should be inserted. In our case2071			 * that will be the slot directly before the2072			 * next INODE_REF_KEY_V2 item. In the case2073			 * that we're pointing to the last slot in a2074			 * leaf, we must move one leaf over.2075			 */2076			ret = btrfs_next_leaf(root, path);2077			if (ret) {2078				if (ret >= 1)2079					ret = -ENOENT;2080				break;2081			}2082			continue;2083		}2084 2085		btrfs_item_key_to_cpu(leaf, &found_key, slot);2086 2087		/*2088		 * Check that we're still looking at an extended ref key for2089		 * this particular objectid. If we have different2090		 * objectid or type then there are no more to be found2091		 * in the tree and we can exit.2092		 */2093		ret = -ENOENT;2094		if (found_key.objectid != inode_objectid)2095			break;2096		if (found_key.type != BTRFS_INODE_EXTREF_KEY)2097			break;2098 2099		ret = 0;2100		ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);2101		extref = (struct btrfs_inode_extref *)ptr;2102		*ret_extref = extref;2103		if (found_off)2104			*found_off = found_key.offset;2105		break;2106	}2107 2108	return ret;2109}2110 2111/*2112 * this iterates to turn a name (from iref/extref) into a full filesystem path.2113 * Elements of the path are separated by '/' and the path is guaranteed to be2114 * 0-terminated. the path is only given within the current file system.2115 * Therefore, it never starts with a '/'. the caller is responsible to provide2116 * "size" bytes in "dest". the dest buffer will be filled backwards. finally,2117 * the start point of the resulting string is returned. this pointer is within2118 * dest, normally.2119 * in case the path buffer would overflow, the pointer is decremented further2120 * as if output was written to the buffer, though no more output is actually2121 * generated. that way, the caller can determine how much space would be2122 * required for the path to fit into the buffer. in that case, the returned2123 * value will be smaller than dest. callers must check this!2124 */2125char *btrfs_ref_to_path(struct btrfs_root *fs_root, struct btrfs_path *path,2126			u32 name_len, unsigned long name_off,2127			struct extent_buffer *eb_in, u64 parent,2128			char *dest, u32 size)2129{2130	int slot;2131	u64 next_inum;2132	int ret;2133	s64 bytes_left = ((s64)size) - 1;2134	struct extent_buffer *eb = eb_in;2135	struct btrfs_key found_key;2136	struct btrfs_inode_ref *iref;2137 2138	if (bytes_left >= 0)2139		dest[bytes_left] = '\0';2140 2141	while (1) {2142		bytes_left -= name_len;2143		if (bytes_left >= 0)2144			read_extent_buffer(eb, dest + bytes_left,2145					   name_off, name_len);2146		if (eb != eb_in) {2147			if (!path->skip_locking)2148				btrfs_tree_read_unlock(eb);2149			free_extent_buffer(eb);2150		}2151		ret = btrfs_find_item(fs_root, path, parent, 0,2152				BTRFS_INODE_REF_KEY, &found_key);2153		if (ret > 0)2154			ret = -ENOENT;2155		if (ret)2156			break;2157 2158		next_inum = found_key.offset;2159 2160		/* regular exit ahead */2161		if (parent == next_inum)2162			break;2163 2164		slot = path->slots[0];2165		eb = path->nodes[0];2166		/* make sure we can use eb after releasing the path */2167		if (eb != eb_in) {2168			path->nodes[0] = NULL;2169			path->locks[0] = 0;2170		}2171		btrfs_release_path(path);2172		iref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);2173 2174		name_len = btrfs_inode_ref_name_len(eb, iref);2175		name_off = (unsigned long)(iref + 1);2176 2177		parent = next_inum;2178		--bytes_left;2179		if (bytes_left >= 0)2180			dest[bytes_left] = '/';2181	}2182 2183	btrfs_release_path(path);2184 2185	if (ret)2186		return ERR_PTR(ret);2187 2188	return dest + bytes_left;2189}2190 2191/*2192 * this makes the path point to (logical EXTENT_ITEM *)2193 * returns BTRFS_EXTENT_FLAG_DATA for data, BTRFS_EXTENT_FLAG_TREE_BLOCK for2194 * tree blocks and <0 on error.2195 */2196int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical,2197			struct btrfs_path *path, struct btrfs_key *found_key,2198			u64 *flags_ret)2199{2200	struct btrfs_root *extent_root = btrfs_extent_root(fs_info, logical);2201	int ret;2202	u64 flags;2203	u64 size = 0;2204	u32 item_size;2205	const struct extent_buffer *eb;2206	struct btrfs_extent_item *ei;2207	struct btrfs_key key;2208 2209	if (btrfs_fs_incompat(fs_info, SKINNY_METADATA))2210		key.type = BTRFS_METADATA_ITEM_KEY;2211	else2212		key.type = BTRFS_EXTENT_ITEM_KEY;2213	key.objectid = logical;2214	key.offset = (u64)-1;2215 2216	ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);2217	if (ret < 0)2218		return ret;2219	if (ret == 0) {2220		/*2221		 * Key with offset -1 found, there would have to exist an extent2222		 * item with such offset, but this is out of the valid range.2223		 */2224		return -EUCLEAN;2225	}2226 2227	ret = btrfs_previous_extent_item(extent_root, path, 0);2228	if (ret) {2229		if (ret > 0)2230			ret = -ENOENT;2231		return ret;2232	}2233	btrfs_item_key_to_cpu(path->nodes[0], found_key, path->slots[0]);2234	if (found_key->type == BTRFS_METADATA_ITEM_KEY)2235		size = fs_info->nodesize;2236	else if (found_key->type == BTRFS_EXTENT_ITEM_KEY)2237		size = found_key->offset;2238 2239	if (found_key->objectid > logical ||2240	    found_key->objectid + size <= logical) {2241		btrfs_debug(fs_info,2242			"logical %llu is not within any extent", logical);2243		return -ENOENT;2244	}2245 2246	eb = path->nodes[0];2247	item_size = btrfs_item_size(eb, path->slots[0]);2248 2249	ei = btrfs_item_ptr(eb, path->slots[0], struct btrfs_extent_item);2250	flags = btrfs_extent_flags(eb, ei);2251 2252	btrfs_debug(fs_info,2253		"logical %llu is at position %llu within the extent (%llu EXTENT_ITEM %llu) flags %#llx size %u",2254		 logical, logical - found_key->objectid, found_key->objectid,2255		 found_key->offset, flags, item_size);2256 2257	WARN_ON(!flags_ret);2258	if (flags_ret) {2259		if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)2260			*flags_ret = BTRFS_EXTENT_FLAG_TREE_BLOCK;2261		else if (flags & BTRFS_EXTENT_FLAG_DATA)2262			*flags_ret = BTRFS_EXTENT_FLAG_DATA;2263		else2264			BUG();2265		return 0;2266	}2267 2268	return -EIO;2269}2270 2271/*2272 * helper function to iterate extent inline refs. ptr must point to a 0 value2273 * for the first call and may be modified. it is used to track state.2274 * if more refs exist, 0 is returned and the next call to2275 * get_extent_inline_ref must pass the modified ptr parameter to get the2276 * next ref. after the last ref was processed, 1 is returned.2277 * returns <0 on error2278 */2279static int get_extent_inline_ref(unsigned long *ptr,2280				 const struct extent_buffer *eb,2281				 const struct btrfs_key *key,2282				 const struct btrfs_extent_item *ei,2283				 u32 item_size,2284				 struct btrfs_extent_inline_ref **out_eiref,2285				 int *out_type)2286{2287	unsigned long end;2288	u64 flags;2289	struct btrfs_tree_block_info *info;2290 2291	if (!*ptr) {2292		/* first call */2293		flags = btrfs_extent_flags(eb, ei);2294		if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {2295			if (key->type == BTRFS_METADATA_ITEM_KEY) {2296				/* a skinny metadata extent */2297				*out_eiref =2298				     (struct btrfs_extent_inline_ref *)(ei + 1);2299			} else {2300				WARN_ON(key->type != BTRFS_EXTENT_ITEM_KEY);2301				info = (struct btrfs_tree_block_info *)(ei + 1);2302				*out_eiref =2303				   (struct btrfs_extent_inline_ref *)(info + 1);2304			}2305		} else {2306			*out_eiref = (struct btrfs_extent_inline_ref *)(ei + 1);2307		}2308		*ptr = (unsigned long)*out_eiref;2309		if ((unsigned long)(*ptr) >= (unsigned long)ei + item_size)2310			return -ENOENT;2311	}2312 2313	end = (unsigned long)ei + item_size;2314	*out_eiref = (struct btrfs_extent_inline_ref *)(*ptr);2315	*out_type = btrfs_get_extent_inline_ref_type(eb, *out_eiref,2316						     BTRFS_REF_TYPE_ANY);2317	if (*out_type == BTRFS_REF_TYPE_INVALID)2318		return -EUCLEAN;2319 2320	*ptr += btrfs_extent_inline_ref_size(*out_type);2321	WARN_ON(*ptr > end);2322	if (*ptr == end)2323		return 1; /* last */2324 2325	return 0;2326}2327 2328/*2329 * reads the tree block backref for an extent. tree level and root are returned2330 * through out_level and out_root. ptr must point to a 0 value for the first2331 * call and may be modified (see get_extent_inline_ref comment).2332 * returns 0 if data was provided, 1 if there was no more data to provide or2333 * <0 on error.2334 */2335int tree_backref_for_extent(unsigned long *ptr, struct extent_buffer *eb,2336			    struct btrfs_key *key, struct btrfs_extent_item *ei,2337			    u32 item_size, u64 *out_root, u8 *out_level)2338{2339	int ret;2340	int type;2341	struct btrfs_extent_inline_ref *eiref;2342 2343	if (*ptr == (unsigned long)-1)2344		return 1;2345 2346	while (1) {2347		ret = get_extent_inline_ref(ptr, eb, key, ei, item_size,2348					      &eiref, &type);2349		if (ret < 0)2350			return ret;2351 2352		if (type == BTRFS_TREE_BLOCK_REF_KEY ||2353		    type == BTRFS_SHARED_BLOCK_REF_KEY)2354			break;2355 2356		if (ret == 1)2357			return 1;2358	}2359 2360	/* we can treat both ref types equally here */2361	*out_root = btrfs_extent_inline_ref_offset(eb, eiref);2362 2363	if (key->type == BTRFS_EXTENT_ITEM_KEY) {2364		struct btrfs_tree_block_info *info;2365 2366		info = (struct btrfs_tree_block_info *)(ei + 1);2367		*out_level = btrfs_tree_block_level(eb, info);2368	} else {2369		ASSERT(key->type == BTRFS_METADATA_ITEM_KEY);2370		*out_level = (u8)key->offset;2371	}2372 2373	if (ret == 1)2374		*ptr = (unsigned long)-1;2375 2376	return 0;2377}2378 2379static int iterate_leaf_refs(struct btrfs_fs_info *fs_info,2380			     struct extent_inode_elem *inode_list,2381			     u64 root, u64 extent_item_objectid,2382			     iterate_extent_inodes_t *iterate, void *ctx)2383{2384	struct extent_inode_elem *eie;2385	int ret = 0;2386 2387	for (eie = inode_list; eie; eie = eie->next) {2388		btrfs_debug(fs_info,2389			    "ref for %llu resolved, key (%llu EXTEND_DATA %llu), root %llu",2390			    extent_item_objectid, eie->inum,2391			    eie->offset, root);2392		ret = iterate(eie->inum, eie->offset, eie->num_bytes, root, ctx);2393		if (ret) {2394			btrfs_debug(fs_info,2395				    "stopping iteration for %llu due to ret=%d",2396				    extent_item_objectid, ret);2397			break;2398		}2399	}2400 2401	return ret;2402}2403 2404/*2405 * calls iterate() for every inode that references the extent identified by2406 * the given parameters.2407 * when the iterator function returns a non-zero value, iteration stops.2408 */2409int iterate_extent_inodes(struct btrfs_backref_walk_ctx *ctx,2410			  bool search_commit_root,2411			  iterate_extent_inodes_t *iterate, void *user_ctx)2412{2413	int ret;2414	struct ulist *refs;2415	struct ulist_node *ref_node;2416	struct btrfs_seq_list seq_elem = BTRFS_SEQ_LIST_INIT(seq_elem);2417	struct ulist_iterator ref_uiter;2418 2419	btrfs_debug(ctx->fs_info, "resolving all inodes for extent %llu",2420		    ctx->bytenr);2421 2422	ASSERT(ctx->trans == NULL);2423	ASSERT(ctx->roots == NULL);2424 2425	if (!search_commit_root) {2426		struct btrfs_trans_handle *trans;2427 2428		trans = btrfs_attach_transaction(ctx->fs_info->tree_root);2429		if (IS_ERR(trans)) {2430			if (PTR_ERR(trans) != -ENOENT &&2431			    PTR_ERR(trans) != -EROFS)2432				return PTR_ERR(trans);2433			trans = NULL;2434		}2435		ctx->trans = trans;2436	}2437 2438	if (ctx->trans) {2439		btrfs_get_tree_mod_seq(ctx->fs_info, &seq_elem);2440		ctx->time_seq = seq_elem.seq;2441	} else {2442		down_read(&ctx->fs_info->commit_root_sem);2443	}2444 2445	ret = btrfs_find_all_leafs(ctx);2446	if (ret)2447		goto out;2448	refs = ctx->refs;2449	ctx->refs = NULL;2450 2451	ULIST_ITER_INIT(&ref_uiter);2452	while (!ret && (ref_node = ulist_next(refs, &ref_uiter))) {2453		const u64 leaf_bytenr = ref_node->val;2454		struct ulist_node *root_node;2455		struct ulist_iterator root_uiter;2456		struct extent_inode_elem *inode_list;2457 2458		inode_list = (struct extent_inode_elem *)(uintptr_t)ref_node->aux;2459 2460		if (ctx->cache_lookup) {2461			const u64 *root_ids;2462			int root_count;2463			bool cached;2464 2465			cached = ctx->cache_lookup(leaf_bytenr, ctx->user_ctx,2466						   &root_ids, &root_count);2467			if (cached) {2468				for (int i = 0; i < root_count; i++) {2469					ret = iterate_leaf_refs(ctx->fs_info,2470								inode_list,2471								root_ids[i],2472								leaf_bytenr,2473								iterate,2474								user_ctx);2475					if (ret)2476						break;2477				}2478				continue;2479			}2480		}2481 2482		if (!ctx->roots) {2483			ctx->roots = ulist_alloc(GFP_NOFS);2484			if (!ctx->roots) {2485				ret = -ENOMEM;2486				break;2487			}2488		}2489 2490		ctx->bytenr = leaf_bytenr;2491		ret = btrfs_find_all_roots_safe(ctx);2492		if (ret)2493			break;2494 2495		if (ctx->cache_store)2496			ctx->cache_store(leaf_bytenr, ctx->roots, ctx->user_ctx);2497 2498		ULIST_ITER_INIT(&root_uiter);2499		while (!ret && (root_node = ulist_next(ctx->roots, &root_uiter))) {2500			btrfs_debug(ctx->fs_info,2501				    "root %llu references leaf %llu, data list %#llx",2502				    root_node->val, ref_node->val,2503				    ref_node->aux);2504			ret = iterate_leaf_refs(ctx->fs_info, inode_list,2505						root_node->val, ctx->bytenr,2506						iterate, user_ctx);2507		}2508		ulist_reinit(ctx->roots);2509	}2510 2511	free_leaf_list(refs);2512out:2513	if (ctx->trans) {2514		btrfs_put_tree_mod_seq(ctx->fs_info, &seq_elem);2515		btrfs_end_transaction(ctx->trans);2516		ctx->trans = NULL;2517	} else {2518		up_read(&ctx->fs_info->commit_root_sem);2519	}2520 2521	ulist_free(ctx->roots);2522	ctx->roots = NULL;2523 2524	if (ret == BTRFS_ITERATE_EXTENT_INODES_STOP)2525		ret = 0;2526 2527	return ret;2528}2529 2530static int build_ino_list(u64 inum, u64 offset, u64 num_bytes, u64 root, void *ctx)2531{2532	struct btrfs_data_container *inodes = ctx;2533	const size_t c = 3 * sizeof(u64);2534 2535	if (inodes->bytes_left >= c) {2536		inodes->bytes_left -= c;2537		inodes->val[inodes->elem_cnt] = inum;2538		inodes->val[inodes->elem_cnt + 1] = offset;2539		inodes->val[inodes->elem_cnt + 2] = root;2540		inodes->elem_cnt += 3;2541	} else {2542		inodes->bytes_missing += c - inodes->bytes_left;2543		inodes->bytes_left = 0;2544		inodes->elem_missed += 3;2545	}2546 2547	return 0;2548}2549 2550int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info,2551				struct btrfs_path *path,2552				void *ctx, bool ignore_offset)2553{2554	struct btrfs_backref_walk_ctx walk_ctx = { 0 };2555	int ret;2556	u64 flags = 0;2557	struct btrfs_key found_key;2558	int search_commit_root = path->search_commit_root;2559 2560	ret = extent_from_logical(fs_info, logical, path, &found_key, &flags);2561	btrfs_release_path(path);2562	if (ret < 0)2563		return ret;2564	if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)2565		return -EINVAL;2566 2567	walk_ctx.bytenr = found_key.objectid;2568	if (ignore_offset)2569		walk_ctx.ignore_extent_item_pos = true;2570	else2571		walk_ctx.extent_item_pos = logical - found_key.objectid;2572	walk_ctx.fs_info = fs_info;2573 2574	return iterate_extent_inodes(&walk_ctx, search_commit_root,2575				     build_ino_list, ctx);2576}2577 2578static int inode_to_path(u64 inum, u32 name_len, unsigned long name_off,2579			 struct extent_buffer *eb, struct inode_fs_paths *ipath);2580 2581static int iterate_inode_refs(u64 inum, struct inode_fs_paths *ipath)2582{2583	int ret = 0;2584	int slot;2585	u32 cur;2586	u32 len;2587	u32 name_len;2588	u64 parent = 0;2589	int found = 0;2590	struct btrfs_root *fs_root = ipath->fs_root;2591	struct btrfs_path *path = ipath->btrfs_path;2592	struct extent_buffer *eb;2593	struct btrfs_inode_ref *iref;2594	struct btrfs_key found_key;2595 2596	while (!ret) {2597		ret = btrfs_find_item(fs_root, path, inum,2598				parent ? parent + 1 : 0, BTRFS_INODE_REF_KEY,2599				&found_key);2600 2601		if (ret < 0)2602			break;2603		if (ret) {2604			ret = found ? 0 : -ENOENT;2605			break;2606		}2607		++found;2608 2609		parent = found_key.offset;2610		slot = path->slots[0];2611		eb = btrfs_clone_extent_buffer(path->nodes[0]);2612		if (!eb) {2613			ret = -ENOMEM;2614			break;2615		}2616		btrfs_release_path(path);2617 2618		iref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);2619 2620		for (cur = 0; cur < btrfs_item_size(eb, slot); cur += len) {2621			name_len = btrfs_inode_ref_name_len(eb, iref);2622			/* path must be released before calling iterate()! */2623			btrfs_debug(fs_root->fs_info,2624				"following ref at offset %u for inode %llu in tree %llu",2625				cur, found_key.objectid,2626				btrfs_root_id(fs_root));2627			ret = inode_to_path(parent, name_len,2628				      (unsigned long)(iref + 1), eb, ipath);2629			if (ret)2630				break;2631			len = sizeof(*iref) + name_len;2632			iref = (struct btrfs_inode_ref *)((char *)iref + len);2633		}2634		free_extent_buffer(eb);2635	}2636 2637	btrfs_release_path(path);2638 2639	return ret;2640}2641 2642static int iterate_inode_extrefs(u64 inum, struct inode_fs_paths *ipath)2643{2644	int ret;2645	int slot;2646	u64 offset = 0;2647	u64 parent;2648	int found = 0;2649	struct btrfs_root *fs_root = ipath->fs_root;2650	struct btrfs_path *path = ipath->btrfs_path;2651	struct extent_buffer *eb;2652	struct btrfs_inode_extref *extref;2653	u32 item_size;2654	u32 cur_offset;2655	unsigned long ptr;2656 2657	while (1) {2658		ret = btrfs_find_one_extref(fs_root, inum, offset, path, &extref,2659					    &offset);2660		if (ret < 0)2661			break;2662		if (ret) {2663			ret = found ? 0 : -ENOENT;2664			break;2665		}2666		++found;2667 2668		slot = path->slots[0];2669		eb = btrfs_clone_extent_buffer(path->nodes[0]);2670		if (!eb) {2671			ret = -ENOMEM;2672			break;2673		}2674		btrfs_release_path(path);2675 2676		item_size = btrfs_item_size(eb, slot);2677		ptr = btrfs_item_ptr_offset(eb, slot);2678		cur_offset = 0;2679 2680		while (cur_offset < item_size) {2681			u32 name_len;2682 2683			extref = (struct btrfs_inode_extref *)(ptr + cur_offset);2684			parent = btrfs_inode_extref_parent(eb, extref);2685			name_len = btrfs_inode_extref_name_len(eb, extref);2686			ret = inode_to_path(parent, name_len,2687				      (unsigned long)&extref->name, eb, ipath);2688			if (ret)2689				break;2690 2691			cur_offset += btrfs_inode_extref_name_len(eb, extref);2692			cur_offset += sizeof(*extref);2693		}2694		free_extent_buffer(eb);2695 2696		offset++;2697	}2698 2699	btrfs_release_path(path);2700 2701	return ret;2702}2703 2704/*2705 * returns 0 if the path could be dumped (probably truncated)2706 * returns <0 in case of an error2707 */2708static int inode_to_path(u64 inum, u32 name_len, unsigned long name_off,2709			 struct extent_buffer *eb, struct inode_fs_paths *ipath)2710{2711	char *fspath;2712	char *fspath_min;2713	int i = ipath->fspath->elem_cnt;2714	const int s_ptr = sizeof(char *);2715	u32 bytes_left;2716 2717	bytes_left = ipath->fspath->bytes_left > s_ptr ?2718					ipath->fspath->bytes_left - s_ptr : 0;2719 2720	fspath_min = (char *)ipath->fspath->val + (i + 1) * s_ptr;2721	fspath = btrfs_ref_to_path(ipath->fs_root, ipath->btrfs_path, name_len,2722				   name_off, eb, inum, fspath_min, bytes_left);2723	if (IS_ERR(fspath))2724		return PTR_ERR(fspath);2725 2726	if (fspath > fspath_min) {2727		ipath->fspath->val[i] = (u64)(unsigned long)fspath;2728		++ipath->fspath->elem_cnt;2729		ipath->fspath->bytes_left = fspath - fspath_min;2730	} else {2731		++ipath->fspath->elem_missed;2732		ipath->fspath->bytes_missing += fspath_min - fspath;2733		ipath->fspath->bytes_left = 0;2734	}2735 2736	return 0;2737}2738 2739/*2740 * this dumps all file system paths to the inode into the ipath struct, provided2741 * is has been created large enough. each path is zero-terminated and accessed2742 * from ipath->fspath->val[i].2743 * when it returns, there are ipath->fspath->elem_cnt number of paths available2744 * in ipath->fspath->val[]. when the allocated space wasn't sufficient, the2745 * number of missed paths is recorded in ipath->fspath->elem_missed, otherwise,2746 * it's zero. ipath->fspath->bytes_missing holds the number of bytes that would2747 * have been needed to return all paths.2748 */2749int paths_from_inode(u64 inum, struct inode_fs_paths *ipath)2750{2751	int ret;2752	int found_refs = 0;2753 2754	ret = iterate_inode_refs(inum, ipath);2755	if (!ret)2756		++found_refs;2757	else if (ret != -ENOENT)2758		return ret;2759 2760	ret = iterate_inode_extrefs(inum, ipath);2761	if (ret == -ENOENT && found_refs)2762		return 0;2763 2764	return ret;2765}2766 2767struct btrfs_data_container *init_data_container(u32 total_bytes)2768{2769	struct btrfs_data_container *data;2770	size_t alloc_bytes;2771 2772	alloc_bytes = max_t(size_t, total_bytes, sizeof(*data));2773	data = kvzalloc(alloc_bytes, GFP_KERNEL);2774	if (!data)2775		return ERR_PTR(-ENOMEM);2776 2777	if (total_bytes >= sizeof(*data))2778		data->bytes_left = total_bytes - sizeof(*data);2779	else2780		data->bytes_missing = sizeof(*data) - total_bytes;2781 2782	return data;2783}2784 2785/*2786 * allocates space to return multiple file system paths for an inode.2787 * total_bytes to allocate are passed, note that space usable for actual path2788 * information will be total_bytes - sizeof(struct inode_fs_paths).2789 * the returned pointer must be freed with free_ipath() in the end.2790 */2791struct inode_fs_paths *init_ipath(s32 total_bytes, struct btrfs_root *fs_root,2792					struct btrfs_path *path)2793{2794	struct inode_fs_paths *ifp;2795	struct btrfs_data_container *fspath;2796 2797	fspath = init_data_container(total_bytes);2798	if (IS_ERR(fspath))2799		return ERR_CAST(fspath);2800 2801	ifp = kmalloc(sizeof(*ifp), GFP_KERNEL);2802	if (!ifp) {2803		kvfree(fspath);2804		return ERR_PTR(-ENOMEM);2805	}2806 2807	ifp->btrfs_path = path;2808	ifp->fspath = fspath;2809	ifp->fs_root = fs_root;2810 2811	return ifp;2812}2813 2814void free_ipath(struct inode_fs_paths *ipath)2815{2816	if (!ipath)2817		return;2818	kvfree(ipath->fspath);2819	kfree(ipath);2820}2821 2822struct btrfs_backref_iter *btrfs_backref_iter_alloc(struct btrfs_fs_info *fs_info)2823{2824	struct btrfs_backref_iter *ret;2825 2826	ret = kzalloc(sizeof(*ret), GFP_NOFS);2827	if (!ret)2828		return NULL;2829 2830	ret->path = btrfs_alloc_path();2831	if (!ret->path) {2832		kfree(ret);2833		return NULL;2834	}2835 2836	/* Current backref iterator only supports iteration in commit root */2837	ret->path->search_commit_root = 1;2838	ret->path->skip_locking = 1;2839	ret->fs_info = fs_info;2840 2841	return ret;2842}2843 2844static void btrfs_backref_iter_release(struct btrfs_backref_iter *iter)2845{2846	iter->bytenr = 0;2847	iter->item_ptr = 0;2848	iter->cur_ptr = 0;2849	iter->end_ptr = 0;2850	btrfs_release_path(iter->path);2851	memset(&iter->cur_key, 0, sizeof(iter->cur_key));2852}2853 2854int btrfs_backref_iter_start(struct btrfs_backref_iter *iter, u64 bytenr)2855{2856	struct btrfs_fs_info *fs_info = iter->fs_info;2857	struct btrfs_root *extent_root = btrfs_extent_root(fs_info, bytenr);2858	struct btrfs_path *path = iter->path;2859	struct btrfs_extent_item *ei;2860	struct btrfs_key key;2861	int ret;2862 2863	key.objectid = bytenr;2864	key.type = BTRFS_METADATA_ITEM_KEY;2865	key.offset = (u64)-1;2866	iter->bytenr = bytenr;2867 2868	ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);2869	if (ret < 0)2870		return ret;2871	if (ret == 0) {2872		/*2873		 * Key with offset -1 found, there would have to exist an extent2874		 * item with such offset, but this is out of the valid range.2875		 */2876		ret = -EUCLEAN;2877		goto release;2878	}2879	if (path->slots[0] == 0) {2880		WARN_ON(IS_ENABLED(CONFIG_BTRFS_DEBUG));2881		ret = -EUCLEAN;2882		goto release;2883	}2884	path->slots[0]--;2885 2886	btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);2887	if ((key.type != BTRFS_EXTENT_ITEM_KEY &&2888	     key.type != BTRFS_METADATA_ITEM_KEY) || key.objectid != bytenr) {2889		ret = -ENOENT;2890		goto release;2891	}2892	memcpy(&iter->cur_key, &key, sizeof(key));2893	iter->item_ptr = (u32)btrfs_item_ptr_offset(path->nodes[0],2894						    path->slots[0]);2895	iter->end_ptr = (u32)(iter->item_ptr +2896			btrfs_item_size(path->nodes[0], path->slots[0]));2897	ei = btrfs_item_ptr(path->nodes[0], path->slots[0],2898			    struct btrfs_extent_item);2899 2900	/*2901	 * Only support iteration on tree backref yet.2902	 *2903	 * This is an extra precaution for non skinny-metadata, where2904	 * EXTENT_ITEM is also used for tree blocks, that we can only use2905	 * extent flags to determine if it's a tree block.2906	 */2907	if (btrfs_extent_flags(path->nodes[0], ei) & BTRFS_EXTENT_FLAG_DATA) {2908		ret = -ENOTSUPP;2909		goto release;2910	}2911	iter->cur_ptr = (u32)(iter->item_ptr + sizeof(*ei));2912 2913	/* If there is no inline backref, go search for keyed backref */2914	if (iter->cur_ptr >= iter->end_ptr) {2915		ret = btrfs_next_item(extent_root, path);2916 2917		/* No inline nor keyed ref */2918		if (ret > 0) {2919			ret = -ENOENT;2920			goto release;2921		}2922		if (ret < 0)2923			goto release;2924 2925		btrfs_item_key_to_cpu(path->nodes[0], &iter->cur_key,2926				path->slots[0]);2927		if (iter->cur_key.objectid != bytenr ||2928		    (iter->cur_key.type != BTRFS_SHARED_BLOCK_REF_KEY &&2929		     iter->cur_key.type != BTRFS_TREE_BLOCK_REF_KEY)) {2930			ret = -ENOENT;2931			goto release;2932		}2933		iter->cur_ptr = (u32)btrfs_item_ptr_offset(path->nodes[0],2934							   path->slots[0]);2935		iter->item_ptr = iter->cur_ptr;2936		iter->end_ptr = (u32)(iter->item_ptr + btrfs_item_size(2937				      path->nodes[0], path->slots[0]));2938	}2939 2940	return 0;2941release:2942	btrfs_backref_iter_release(iter);2943	return ret;2944}2945 2946static bool btrfs_backref_iter_is_inline_ref(struct btrfs_backref_iter *iter)2947{2948	if (iter->cur_key.type == BTRFS_EXTENT_ITEM_KEY ||2949	    iter->cur_key.type == BTRFS_METADATA_ITEM_KEY)2950		return true;2951	return false;2952}2953 2954/*2955 * Go to the next backref item of current bytenr, can be either inlined or2956 * keyed.2957 *2958 * Caller needs to check whether it's inline ref or not by iter->cur_key.2959 *2960 * Return 0 if we get next backref without problem.2961 * Return >0 if there is no extra backref for this bytenr.2962 * Return <0 if there is something wrong happened.2963 */2964int btrfs_backref_iter_next(struct btrfs_backref_iter *iter)2965{2966	struct extent_buffer *eb = iter->path->nodes[0];2967	struct btrfs_root *extent_root;2968	struct btrfs_path *path = iter->path;2969	struct btrfs_extent_inline_ref *iref;2970	int ret;2971	u32 size;2972 2973	if (btrfs_backref_iter_is_inline_ref(iter)) {2974		/* We're still inside the inline refs */2975		ASSERT(iter->cur_ptr < iter->end_ptr);2976 2977		if (btrfs_backref_has_tree_block_info(iter)) {2978			/* First tree block info */2979			size = sizeof(struct btrfs_tree_block_info);2980		} else {2981			/* Use inline ref type to determine the size */2982			int type;2983 2984			iref = (struct btrfs_extent_inline_ref *)2985				((unsigned long)iter->cur_ptr);2986			type = btrfs_extent_inline_ref_type(eb, iref);2987 2988			size = btrfs_extent_inline_ref_size(type);2989		}2990		iter->cur_ptr += size;2991		if (iter->cur_ptr < iter->end_ptr)2992			return 0;2993 2994		/* All inline items iterated, fall through */2995	}2996 2997	/* We're at keyed items, there is no inline item, go to the next one */2998	extent_root = btrfs_extent_root(iter->fs_info, iter->bytenr);2999	ret = btrfs_next_item(extent_root, iter->path);3000	if (ret)3001		return ret;3002 3003	btrfs_item_key_to_cpu(path->nodes[0], &iter->cur_key, path->slots[0]);3004	if (iter->cur_key.objectid != iter->bytenr ||3005	    (iter->cur_key.type != BTRFS_TREE_BLOCK_REF_KEY &&3006	     iter->cur_key.type != BTRFS_SHARED_BLOCK_REF_KEY))3007		return 1;3008	iter->item_ptr = (u32)btrfs_item_ptr_offset(path->nodes[0],3009					path->slots[0]);3010	iter->cur_ptr = iter->item_ptr;3011	iter->end_ptr = iter->item_ptr + (u32)btrfs_item_size(path->nodes[0],3012						path->slots[0]);3013	return 0;3014}3015 3016void btrfs_backref_init_cache(struct btrfs_fs_info *fs_info,3017			      struct btrfs_backref_cache *cache, bool is_reloc)3018{3019	int i;3020 3021	cache->rb_root = RB_ROOT;3022	for (i = 0; i < BTRFS_MAX_LEVEL; i++)3023		INIT_LIST_HEAD(&cache->pending[i]);3024	INIT_LIST_HEAD(&cache->changed);3025	INIT_LIST_HEAD(&cache->detached);3026	INIT_LIST_HEAD(&cache->leaves);3027	INIT_LIST_HEAD(&cache->pending_edge);3028	INIT_LIST_HEAD(&cache->useless_node);3029	cache->fs_info = fs_info;3030	cache->is_reloc = is_reloc;3031}3032 3033struct btrfs_backref_node *btrfs_backref_alloc_node(3034		struct btrfs_backref_cache *cache, u64 bytenr, int level)3035{3036	struct btrfs_backref_node *node;3037 3038	ASSERT(level >= 0 && level < BTRFS_MAX_LEVEL);3039	node = kzalloc(sizeof(*node), GFP_NOFS);3040	if (!node)3041		return node;3042 3043	INIT_LIST_HEAD(&node->list);3044	INIT_LIST_HEAD(&node->upper);3045	INIT_LIST_HEAD(&node->lower);3046	RB_CLEAR_NODE(&node->rb_node);3047	cache->nr_nodes++;3048	node->level = level;3049	node->bytenr = bytenr;3050 3051	return node;3052}3053 3054void btrfs_backref_free_node(struct btrfs_backref_cache *cache,3055			     struct btrfs_backref_node *node)3056{3057	if (node) {3058		ASSERT(list_empty(&node->list));3059		ASSERT(list_empty(&node->lower));3060		ASSERT(node->eb == NULL);3061		cache->nr_nodes--;3062		btrfs_put_root(node->root);3063		kfree(node);3064	}3065}3066 3067struct btrfs_backref_edge *btrfs_backref_alloc_edge(3068		struct btrfs_backref_cache *cache)3069{3070	struct btrfs_backref_edge *edge;3071 3072	edge = kzalloc(sizeof(*edge), GFP_NOFS);3073	if (edge)3074		cache->nr_edges++;3075	return edge;3076}3077 3078void btrfs_backref_free_edge(struct btrfs_backref_cache *cache,3079			     struct btrfs_backref_edge *edge)3080{3081	if (edge) {3082		cache->nr_edges--;3083		kfree(edge);3084	}3085}3086 3087void btrfs_backref_unlock_node_buffer(struct btrfs_backref_node *node)3088{3089	if (node->locked) {3090		btrfs_tree_unlock(node->eb);3091		node->locked = 0;3092	}3093}3094 3095void btrfs_backref_drop_node_buffer(struct btrfs_backref_node *node)3096{3097	if (node->eb) {3098		btrfs_backref_unlock_node_buffer(node);3099		free_extent_buffer(node->eb);3100		node->eb = NULL;3101	}3102}3103 3104/*3105 * Drop the backref node from cache without cleaning up its children3106 * edges.3107 *3108 * This can only be called on node without parent edges.3109 * The children edges are still kept as is.3110 */3111void btrfs_backref_drop_node(struct btrfs_backref_cache *tree,3112			     struct btrfs_backref_node *node)3113{3114	ASSERT(list_empty(&node->upper));3115 3116	btrfs_backref_drop_node_buffer(node);3117	list_del_init(&node->list);3118	list_del_init(&node->lower);3119	if (!RB_EMPTY_NODE(&node->rb_node))3120		rb_erase(&node->rb_node, &tree->rb_root);3121	btrfs_backref_free_node(tree, node);3122}3123 3124/*3125 * Drop the backref node from cache, also cleaning up all its3126 * upper edges and any uncached nodes in the path.3127 *3128 * This cleanup happens bottom up, thus the node should either3129 * be the lowest node in the cache or a detached node.3130 */3131void btrfs_backref_cleanup_node(struct btrfs_backref_cache *cache,3132				struct btrfs_backref_node *node)3133{3134	struct btrfs_backref_node *upper;3135	struct btrfs_backref_edge *edge;3136 3137	if (!node)3138		return;3139 3140	BUG_ON(!node->lowest && !node->detached);3141	while (!list_empty(&node->upper)) {3142		edge = list_entry(node->upper.next, struct btrfs_backref_edge,3143				  list[LOWER]);3144		upper = edge->node[UPPER];3145		list_del(&edge->list[LOWER]);3146		list_del(&edge->list[UPPER]);3147		btrfs_backref_free_edge(cache, edge);3148 3149		/*3150		 * Add the node to leaf node list if no other child block3151		 * cached.3152		 */3153		if (list_empty(&upper->lower)) {3154			list_add_tail(&upper->lower, &cache->leaves);3155			upper->lowest = 1;3156		}3157	}3158 3159	btrfs_backref_drop_node(cache, node);3160}3161 3162/*3163 * Release all nodes/edges from current cache3164 */3165void btrfs_backref_release_cache(struct btrfs_backref_cache *cache)3166{3167	struct btrfs_backref_node *node;3168	int i;3169 3170	while (!list_empty(&cache->detached)) {3171		node = list_entry(cache->detached.next,3172				  struct btrfs_backref_node, list);3173		btrfs_backref_cleanup_node(cache, node);3174	}3175 3176	while (!list_empty(&cache->leaves)) {3177		node = list_entry(cache->leaves.next,3178				  struct btrfs_backref_node, lower);3179		btrfs_backref_cleanup_node(cache, node);3180	}3181 3182	for (i = 0; i < BTRFS_MAX_LEVEL; i++) {3183		while (!list_empty(&cache->pending[i])) {3184			node = list_first_entry(&cache->pending[i],3185						struct btrfs_backref_node,3186						list);3187			btrfs_backref_cleanup_node(cache, node);3188		}3189	}3190	ASSERT(list_empty(&cache->pending_edge));3191	ASSERT(list_empty(&cache->useless_node));3192	ASSERT(list_empty(&cache->changed));3193	ASSERT(list_empty(&cache->detached));3194	ASSERT(RB_EMPTY_ROOT(&cache->rb_root));3195	ASSERT(!cache->nr_nodes);3196	ASSERT(!cache->nr_edges);3197}3198 3199void btrfs_backref_link_edge(struct btrfs_backref_edge *edge,3200			     struct btrfs_backref_node *lower,3201			     struct btrfs_backref_node *upper,3202			     int link_which)3203{3204	ASSERT(upper && lower && upper->level == lower->level + 1);3205	edge->node[LOWER] = lower;3206	edge->node[UPPER] = upper;3207	if (link_which & LINK_LOWER)3208		list_add_tail(&edge->list[LOWER], &lower->upper);3209	if (link_which & LINK_UPPER)3210		list_add_tail(&edge->list[UPPER], &upper->lower);3211}3212/*3213 * Handle direct tree backref3214 *3215 * Direct tree backref means, the backref item shows its parent bytenr3216 * directly. This is for SHARED_BLOCK_REF backref (keyed or inlined).3217 *3218 * @ref_key:	The converted backref key.3219 *		For keyed backref, it's the item key.3220 *		For inlined backref, objectid is the bytenr,3221 *		type is btrfs_inline_ref_type, offset is3222 *		btrfs_inline_ref_offset.3223 */3224static int handle_direct_tree_backref(struct btrfs_backref_cache *cache,3225				      struct btrfs_key *ref_key,3226				      struct btrfs_backref_node *cur)3227{3228	struct btrfs_backref_edge *edge;3229	struct btrfs_backref_node *upper;3230	struct rb_node *rb_node;3231 3232	ASSERT(ref_key->type == BTRFS_SHARED_BLOCK_REF_KEY);3233 3234	/* Only reloc root uses backref pointing to itself */3235	if (ref_key->objectid == ref_key->offset) {3236		struct btrfs_root *root;3237 3238		cur->is_reloc_root = 1;3239		/* Only reloc backref cache cares about a specific root */3240		if (cache->is_reloc) {3241			root = find_reloc_root(cache->fs_info, cur->bytenr);3242			if (!root)3243				return -ENOENT;3244			cur->root = root;3245		} else {3246			/*3247			 * For generic purpose backref cache, reloc root node3248			 * is useless.3249			 */3250			list_add(&cur->list, &cache->useless_node);3251		}3252		return 0;3253	}3254 3255	edge = btrfs_backref_alloc_edge(cache);3256	if (!edge)3257		return -ENOMEM;3258 3259	rb_node = rb_simple_search(&cache->rb_root, ref_key->offset);3260	if (!rb_node) {3261		/* Parent node not yet cached */3262		upper = btrfs_backref_alloc_node(cache, ref_key->offset,3263					   cur->level + 1);3264		if (!upper) {3265			btrfs_backref_free_edge(cache, edge);3266			return -ENOMEM;3267		}3268 3269		/*3270		 *  Backrefs for the upper level block isn't cached, add the3271		 *  block to pending list3272		 */3273		list_add_tail(&edge->list[UPPER], &cache->pending_edge);3274	} else {3275		/* Parent node already cached */3276		upper = rb_entry(rb_node, struct btrfs_backref_node, rb_node);3277		ASSERT(upper->checked);3278		INIT_LIST_HEAD(&edge->list[UPPER]);3279	}3280	btrfs_backref_link_edge(edge, cur, upper, LINK_LOWER);3281	return 0;3282}3283 3284/*3285 * Handle indirect tree backref3286 *3287 * Indirect tree backref means, we only know which tree the node belongs to.3288 * We still need to do a tree search to find out the parents. This is for3289 * TREE_BLOCK_REF backref (keyed or inlined).3290 *3291 * @trans:	Transaction handle.3292 * @ref_key:	The same as @ref_key in  handle_direct_tree_backref()3293 * @tree_key:	The first key of this tree block.3294 * @path:	A clean (released) path, to avoid allocating path every time3295 *		the function get called.3296 */3297static int handle_indirect_tree_backref(struct btrfs_trans_handle *trans,3298					struct btrfs_backref_cache *cache,3299					struct btrfs_path *path,3300					struct btrfs_key *ref_key,3301					struct btrfs_key *tree_key,3302					struct btrfs_backref_node *cur)3303{3304	struct btrfs_fs_info *fs_info = cache->fs_info;3305	struct btrfs_backref_node *upper;3306	struct btrfs_backref_node *lower;3307	struct btrfs_backref_edge *edge;3308	struct extent_buffer *eb;3309	struct btrfs_root *root;3310	struct rb_node *rb_node;3311	int level;3312	bool need_check = true;3313	int ret;3314 3315	root = btrfs_get_fs_root(fs_info, ref_key->offset, false);3316	if (IS_ERR(root))3317		return PTR_ERR(root);3318	if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state))3319		cur->cowonly = 1;3320 3321	if (btrfs_root_level(&root->root_item) == cur->level) {3322		/* Tree root */3323		ASSERT(btrfs_root_bytenr(&root->root_item) == cur->bytenr);3324		/*3325		 * For reloc backref cache, we may ignore reloc root.  But for3326		 * general purpose backref cache, we can't rely on3327		 * btrfs_should_ignore_reloc_root() as it may conflict with3328		 * current running relocation and lead to missing root.3329		 *3330		 * For general purpose backref cache, reloc root detection is3331		 * completely relying on direct backref (key->offset is parent3332		 * bytenr), thus only do such check for reloc cache.3333		 */3334		if (btrfs_should_ignore_reloc_root(root) && cache->is_reloc) {3335			btrfs_put_root(root);3336			list_add(&cur->list, &cache->useless_node);3337		} else {3338			cur->root = root;3339		}3340		return 0;3341	}3342 3343	level = cur->level + 1;3344 3345	/* Search the tree to find parent blocks referring to the block */3346	path->search_commit_root = 1;3347	path->skip_locking = 1;3348	path->lowest_level = level;3349	ret = btrfs_search_slot(NULL, root, tree_key, path, 0, 0);3350	path->lowest_level = 0;3351	if (ret < 0) {3352		btrfs_put_root(root);3353		return ret;3354	}3355	if (ret > 0 && path->slots[level] > 0)3356		path->slots[level]--;3357 3358	eb = path->nodes[level];3359	if (btrfs_node_blockptr(eb, path->slots[level]) != cur->bytenr) {3360		btrfs_err(fs_info,3361"couldn't find block (%llu) (level %d) in tree (%llu) with key (%llu %u %llu)",3362			  cur->bytenr, level - 1, btrfs_root_id(root),3363			  tree_key->objectid, tree_key->type, tree_key->offset);3364		btrfs_put_root(root);3365		ret = -ENOENT;3366		goto out;3367	}3368	lower = cur;3369 3370	/* Add all nodes and edges in the path */3371	for (; level < BTRFS_MAX_LEVEL; level++) {3372		if (!path->nodes[level]) {3373			ASSERT(btrfs_root_bytenr(&root->root_item) ==3374			       lower->bytenr);3375			/* Same as previous should_ignore_reloc_root() call */3376			if (btrfs_should_ignore_reloc_root(root) &&3377			    cache->is_reloc) {3378				btrfs_put_root(root);3379				list_add(&lower->list, &cache->useless_node);3380			} else {3381				lower->root = root;3382			}3383			break;3384		}3385 3386		edge = btrfs_backref_alloc_edge(cache);3387		if (!edge) {3388			btrfs_put_root(root);3389			ret = -ENOMEM;3390			goto out;3391		}3392 3393		eb = path->nodes[level];3394		rb_node = rb_simple_search(&cache->rb_root, eb->start);3395		if (!rb_node) {3396			upper = btrfs_backref_alloc_node(cache, eb->start,3397							 lower->level + 1);3398			if (!upper) {3399				btrfs_put_root(root);3400				btrfs_backref_free_edge(cache, edge);3401				ret = -ENOMEM;3402				goto out;3403			}3404			upper->owner = btrfs_header_owner(eb);3405			if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state))3406				upper->cowonly = 1;3407 3408			/*3409			 * If we know the block isn't shared we can avoid3410			 * checking its backrefs.3411			 */3412			if (btrfs_block_can_be_shared(trans, root, eb))3413				upper->checked = 0;3414			else3415				upper->checked = 1;3416 3417			/*3418			 * Add the block to pending list if we need to check its3419			 * backrefs, we only do this once while walking up a3420			 * tree as we will catch anything else later on.3421			 */3422			if (!upper->checked && need_check) {3423				need_check = false;3424				list_add_tail(&edge->list[UPPER],3425					      &cache->pending_edge);3426			} else {3427				if (upper->checked)3428					need_check = true;3429				INIT_LIST_HEAD(&edge->list[UPPER]);3430			}3431		} else {3432			upper = rb_entry(rb_node, struct btrfs_backref_node,3433					 rb_node);3434			ASSERT(upper->checked);3435			INIT_LIST_HEAD(&edge->list[UPPER]);3436			if (!upper->owner)3437				upper->owner = btrfs_header_owner(eb);3438		}3439		btrfs_backref_link_edge(edge, lower, upper, LINK_LOWER);3440 3441		if (rb_node) {3442			btrfs_put_root(root);3443			break;3444		}3445		lower = upper;3446		upper = NULL;3447	}3448out:3449	btrfs_release_path(path);3450	return ret;3451}3452 3453/*3454 * Add backref node @cur into @cache.3455 *3456 * NOTE: Even if the function returned 0, @cur is not yet cached as its upper3457 *	 links aren't yet bi-directional. Needs to finish such links.3458 *	 Use btrfs_backref_finish_upper_links() to finish such linkage.3459 *3460 * @trans:	Transaction handle.3461 * @path:	Released path for indirect tree backref lookup3462 * @iter:	Released backref iter for extent tree search3463 * @node_key:	The first key of the tree block3464 */3465int btrfs_backref_add_tree_node(struct btrfs_trans_handle *trans,3466				struct btrfs_backref_cache *cache,3467				struct btrfs_path *path,3468				struct btrfs_backref_iter *iter,3469				struct btrfs_key *node_key,3470				struct btrfs_backref_node *cur)3471{3472	struct btrfs_backref_edge *edge;3473	struct btrfs_backref_node *exist;3474	int ret;3475 3476	ret = btrfs_backref_iter_start(iter, cur->bytenr);3477	if (ret < 0)3478		return ret;3479	/*3480	 * We skip the first btrfs_tree_block_info, as we don't use the key3481	 * stored in it, but fetch it from the tree block3482	 */3483	if (btrfs_backref_has_tree_block_info(iter)) {3484		ret = btrfs_backref_iter_next(iter);3485		if (ret < 0)3486			goto out;3487		/* No extra backref? This means the tree block is corrupted */3488		if (ret > 0) {3489			ret = -EUCLEAN;3490			goto out;3491		}3492	}3493	WARN_ON(cur->checked);3494	if (!list_empty(&cur->upper)) {3495		/*3496		 * The backref was added previously when processing backref of3497		 * type BTRFS_TREE_BLOCK_REF_KEY3498		 */3499		ASSERT(list_is_singular(&cur->upper));3500		edge = list_entry(cur->upper.next, struct btrfs_backref_edge,3501				  list[LOWER]);3502		ASSERT(list_empty(&edge->list[UPPER]));3503		exist = edge->node[UPPER];3504		/*3505		 * Add the upper level block to pending list if we need check3506		 * its backrefs3507		 */3508		if (!exist->checked)3509			list_add_tail(&edge->list[UPPER], &cache->pending_edge);3510	} else {3511		exist = NULL;3512	}3513 3514	for (; ret == 0; ret = btrfs_backref_iter_next(iter)) {3515		struct extent_buffer *eb;3516		struct btrfs_key key;3517		int type;3518 3519		cond_resched();3520		eb = iter->path->nodes[0];3521 3522		key.objectid = iter->bytenr;3523		if (btrfs_backref_iter_is_inline_ref(iter)) {3524			struct btrfs_extent_inline_ref *iref;3525 3526			/* Update key for inline backref */3527			iref = (struct btrfs_extent_inline_ref *)3528				((unsigned long)iter->cur_ptr);3529			type = btrfs_get_extent_inline_ref_type(eb, iref,3530							BTRFS_REF_TYPE_BLOCK);3531			if (type == BTRFS_REF_TYPE_INVALID) {3532				ret = -EUCLEAN;3533				goto out;3534			}3535			key.type = type;3536			key.offset = btrfs_extent_inline_ref_offset(eb, iref);3537		} else {3538			key.type = iter->cur_key.type;3539			key.offset = iter->cur_key.offset;3540		}3541 3542		/*3543		 * Parent node found and matches current inline ref, no need to3544		 * rebuild this node for this inline ref3545		 */3546		if (exist &&3547		    ((key.type == BTRFS_TREE_BLOCK_REF_KEY &&3548		      exist->owner == key.offset) ||3549		     (key.type == BTRFS_SHARED_BLOCK_REF_KEY &&3550		      exist->bytenr == key.offset))) {3551			exist = NULL;3552			continue;3553		}3554 3555		/* SHARED_BLOCK_REF means key.offset is the parent bytenr */3556		if (key.type == BTRFS_SHARED_BLOCK_REF_KEY) {3557			ret = handle_direct_tree_backref(cache, &key, cur);3558			if (ret < 0)3559				goto out;3560		} else if (key.type == BTRFS_TREE_BLOCK_REF_KEY) {3561			/*3562			 * key.type == BTRFS_TREE_BLOCK_REF_KEY, inline ref3563			 * offset means the root objectid. We need to search3564			 * the tree to get its parent bytenr.3565			 */3566			ret = handle_indirect_tree_backref(trans, cache, path,3567							   &key, node_key, cur);3568			if (ret < 0)3569				goto out;3570		}3571		/*3572		 * Unrecognized tree backref items (if it can pass tree-checker)3573		 * would be ignored.3574		 */3575	}3576	ret = 0;3577	cur->checked = 1;3578	WARN_ON(exist);3579out:3580	btrfs_backref_iter_release(iter);3581	return ret;3582}3583 3584/*3585 * Finish the upwards linkage created by btrfs_backref_add_tree_node()3586 */3587int btrfs_backref_finish_upper_links(struct btrfs_backref_cache *cache,3588				     struct btrfs_backref_node *start)3589{3590	struct list_head *useless_node = &cache->useless_node;3591	struct btrfs_backref_edge *edge;3592	struct rb_node *rb_node;3593	LIST_HEAD(pending_edge);3594 3595	ASSERT(start->checked);3596 3597	/* Insert this node to cache if it's not COW-only */3598	if (!start->cowonly) {3599		rb_node = rb_simple_insert(&cache->rb_root, start->bytenr,3600					   &start->rb_node);3601		if (rb_node)3602			btrfs_backref_panic(cache->fs_info, start->bytenr,3603					    -EEXIST);3604		list_add_tail(&start->lower, &cache->leaves);3605	}3606 3607	/*3608	 * Use breadth first search to iterate all related edges.3609	 *3610	 * The starting points are all the edges of this node3611	 */3612	list_for_each_entry(edge, &start->upper, list[LOWER])3613		list_add_tail(&edge->list[UPPER], &pending_edge);3614 3615	while (!list_empty(&pending_edge)) {3616		struct btrfs_backref_node *upper;3617		struct btrfs_backref_node *lower;3618 3619		edge = list_first_entry(&pending_edge,3620				struct btrfs_backref_edge, list[UPPER]);3621		list_del_init(&edge->list[UPPER]);3622		upper = edge->node[UPPER];3623		lower = edge->node[LOWER];3624 3625		/* Parent is detached, no need to keep any edges */3626		if (upper->detached) {3627			list_del(&edge->list[LOWER]);3628			btrfs_backref_free_edge(cache, edge);3629 3630			/* Lower node is orphan, queue for cleanup */3631			if (list_empty(&lower->upper))3632				list_add(&lower->list, useless_node);3633			continue;3634		}3635 3636		/*3637		 * All new nodes added in current build_backref_tree() haven't3638		 * been linked to the cache rb tree.3639		 * So if we have upper->rb_node populated, this means a cache3640		 * hit. We only need to link the edge, as @upper and all its3641		 * parents have already been linked.3642		 */3643		if (!RB_EMPTY_NODE(&upper->rb_node)) {3644			if (upper->lowest) {3645				list_del_init(&upper->lower);3646				upper->lowest = 0;3647			}3648 3649			list_add_tail(&edge->list[UPPER], &upper->lower);3650			continue;3651		}3652 3653		/* Sanity check, we shouldn't have any unchecked nodes */3654		if (!upper->checked) {3655			ASSERT(0);3656			return -EUCLEAN;3657		}3658 3659		/* Sanity check, COW-only node has non-COW-only parent */3660		if (start->cowonly != upper->cowonly) {3661			ASSERT(0);3662			return -EUCLEAN;3663		}3664 3665		/* Only cache non-COW-only (subvolume trees) tree blocks */3666		if (!upper->cowonly) {3667			rb_node = rb_simple_insert(&cache->rb_root, upper->bytenr,3668						   &upper->rb_node);3669			if (rb_node) {3670				btrfs_backref_panic(cache->fs_info,3671						upper->bytenr, -EEXIST);3672				return -EUCLEAN;3673			}3674		}3675 3676		list_add_tail(&edge->list[UPPER], &upper->lower);3677 3678		/*3679		 * Also queue all the parent edges of this uncached node3680		 * to finish the upper linkage3681		 */3682		list_for_each_entry(edge, &upper->upper, list[LOWER])3683			list_add_tail(&edge->list[UPPER], &pending_edge);3684	}3685	return 0;3686}3687 3688void btrfs_backref_error_cleanup(struct btrfs_backref_cache *cache,3689				 struct btrfs_backref_node *node)3690{3691	struct btrfs_backref_node *lower;3692	struct btrfs_backref_node *upper;3693	struct btrfs_backref_edge *edge;3694 3695	while (!list_empty(&cache->useless_node)) {3696		lower = list_first_entry(&cache->useless_node,3697				   struct btrfs_backref_node, list);3698		list_del_init(&lower->list);3699	}3700	while (!list_empty(&cache->pending_edge)) {3701		edge = list_first_entry(&cache->pending_edge,3702				struct btrfs_backref_edge, list[UPPER]);3703		list_del(&edge->list[UPPER]);3704		list_del(&edge->list[LOWER]);3705		lower = edge->node[LOWER];3706		upper = edge->node[UPPER];3707		btrfs_backref_free_edge(cache, edge);3708 3709		/*3710		 * Lower is no longer linked to any upper backref nodes and3711		 * isn't in the cache, we can free it ourselves.3712		 */3713		if (list_empty(&lower->upper) &&3714		    RB_EMPTY_NODE(&lower->rb_node))3715			list_add(&lower->list, &cache->useless_node);3716 3717		if (!RB_EMPTY_NODE(&upper->rb_node))3718			continue;3719 3720		/* Add this guy's upper edges to the list to process */3721		list_for_each_entry(edge, &upper->upper, list[LOWER])3722			list_add_tail(&edge->list[UPPER],3723				      &cache->pending_edge);3724		if (list_empty(&upper->upper))3725			list_add(&upper->list, &cache->useless_node);3726	}3727 3728	while (!list_empty(&cache->useless_node)) {3729		lower = list_first_entry(&cache->useless_node,3730				   struct btrfs_backref_node, list);3731		list_del_init(&lower->list);3732		if (lower == node)3733			node = NULL;3734		btrfs_backref_drop_node(cache, lower);3735	}3736 3737	btrfs_backref_cleanup_node(cache, node);3738	ASSERT(list_empty(&cache->useless_node) &&3739	       list_empty(&cache->pending_edge));3740}3741