1/*
   2 * Copyright (C) 2011 STRATO.  All rights reserved.
   3 *
   4 * This program is free software; you can redistribute it and/or
   5 * modify it under the terms of the GNU General Public
   6 * License v2 as published by the Free Software Foundation.
   7 *
   8 * This program is distributed in the hope that it will be useful,
   9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11 * General Public License for more details.
  12 *
  13 * You should have received a copy of the GNU General Public
  14 * License along with this program; if not, write to the
  15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16 * Boston, MA 021110-1307, USA.
  17 */
  18
  19#include <linux/vmalloc.h>
  20#include <linux/rbtree.h>
  21#include "ctree.h"
  22#include "disk-io.h"
  23#include "backref.h"
  24#include "ulist.h"
  25#include "transaction.h"
  26#include "delayed-ref.h"
  27#include "locking.h"
  28
  29/* Just an arbitrary number so we can be sure this happened */
  30#define BACKREF_FOUND_SHARED 6
  31
  32struct extent_inode_elem {
  33	u64 inum;
  34	u64 offset;
  35	struct extent_inode_elem *next;
  36};
  37
  38/*
  39 * ref_root is used as the root of the ref tree that hold a collection
  40 * of unique references.
  41 */
  42struct ref_root {
  43	struct rb_root rb_root;
  44
  45	/*
  46	 * The unique_refs represents the number of ref_nodes with a positive
  47	 * count stored in the tree. Even if a ref_node (the count is greater
  48	 * than one) is added, the unique_refs will only increase by one.
  49	 */
  50	unsigned int unique_refs;
  51};
  52
  53/* ref_node is used to store a unique reference to the ref tree. */
  54struct ref_node {
  55	struct rb_node rb_node;
  56
  57	/* For NORMAL_REF, otherwise all these fields should be set to 0 */
  58	u64 root_id;
  59	u64 object_id;
  60	u64 offset;
  61
  62	/* For SHARED_REF, otherwise parent field should be set to 0 */
  63	u64 parent;
  64
  65	/* Ref to the ref_mod of btrfs_delayed_ref_node */
  66	int ref_mod;
  67};
  68
  69/* Dynamically allocate and initialize a ref_root */
  70static struct ref_root *ref_root_alloc(void)
  71{
  72	struct ref_root *ref_tree;
  73
  74	ref_tree = kmalloc(sizeof(*ref_tree), GFP_NOFS);
  75	if (!ref_tree)
  76		return NULL;
  77
  78	ref_tree->rb_root = RB_ROOT;
  79	ref_tree->unique_refs = 0;
  80
  81	return ref_tree;
  82}
  83
  84/* Free all nodes in the ref tree, and reinit ref_root */
  85static void ref_root_fini(struct ref_root *ref_tree)
  86{
  87	struct ref_node *node;
  88	struct rb_node *next;
  89
  90	while ((next = rb_first(&ref_tree->rb_root)) != NULL) {
  91		node = rb_entry(next, struct ref_node, rb_node);
  92		rb_erase(next, &ref_tree->rb_root);
  93		kfree(node);
  94	}
  95
  96	ref_tree->rb_root = RB_ROOT;
  97	ref_tree->unique_refs = 0;
  98}
  99
 100static void ref_root_free(struct ref_root *ref_tree)
 101{
 102	if (!ref_tree)
 103		return;
 104
 105	ref_root_fini(ref_tree);
 106	kfree(ref_tree);
 107}
 108
 109/*
 110 * Compare ref_node with (root_id, object_id, offset, parent)
 111 *
 112 * The function compares two ref_node a and b. It returns an integer less
 113 * than, equal to, or greater than zero , respectively, to be less than, to
 114 * equal, or be greater than b.
 115 */
 116static int ref_node_cmp(struct ref_node *a, struct ref_node *b)
 117{
 118	if (a->root_id < b->root_id)
 119		return -1;
 120	else if (a->root_id > b->root_id)
 121		return 1;
 122
 123	if (a->object_id < b->object_id)
 124		return -1;
 125	else if (a->object_id > b->object_id)
 126		return 1;
 127
 128	if (a->offset < b->offset)
 129		return -1;
 130	else if (a->offset > b->offset)
 131		return 1;
 132
 133	if (a->parent < b->parent)
 134		return -1;
 135	else if (a->parent > b->parent)
 136		return 1;
 137
 138	return 0;
 139}
 140
 141/*
 142 * Search ref_node with (root_id, object_id, offset, parent) in the tree
 143 *
 144 * if found, the pointer of the ref_node will be returned;
 145 * if not found, NULL will be returned and pos will point to the rb_node for
 146 * insert, pos_parent will point to pos'parent for insert;
 147*/
 148static struct ref_node *__ref_tree_search(struct ref_root *ref_tree,
 149					  struct rb_node ***pos,
 150					  struct rb_node **pos_parent,
 151					  u64 root_id, u64 object_id,
 152					  u64 offset, u64 parent)
 153{
 154	struct ref_node *cur = NULL;
 155	struct ref_node entry;
 156	int ret;
 157
 158	entry.root_id = root_id;
 159	entry.object_id = object_id;
 160	entry.offset = offset;
 161	entry.parent = parent;
 162
 163	*pos = &ref_tree->rb_root.rb_node;
 164
 165	while (**pos) {
 166		*pos_parent = **pos;
 167		cur = rb_entry(*pos_parent, struct ref_node, rb_node);
 168
 169		ret = ref_node_cmp(cur, &entry);
 170		if (ret > 0)
 171			*pos = &(**pos)->rb_left;
 172		else if (ret < 0)
 173			*pos = &(**pos)->rb_right;
 174		else
 175			return cur;
 176	}
 177
 178	return NULL;
 179}
 180
 181/*
 182 * Insert a ref_node to the ref tree
 183 * @pos used for specifiy the position to insert
 184 * @pos_parent for specifiy pos's parent
 185 *
 186 * success, return 0;
 187 * ref_node already exists, return -EEXIST;
 188*/
 189static int ref_tree_insert(struct ref_root *ref_tree, struct rb_node **pos,
 190			   struct rb_node *pos_parent, struct ref_node *ins)
 191{
 192	struct rb_node **p = NULL;
 193	struct rb_node *parent = NULL;
 194	struct ref_node *cur = NULL;
 195
 196	if (!pos) {
 197		cur = __ref_tree_search(ref_tree, &p, &parent, ins->root_id,
 198					ins->object_id, ins->offset,
 199					ins->parent);
 200		if (cur)
 201			return -EEXIST;
 202	} else {
 203		p = pos;
 204		parent = pos_parent;
 205	}
 206
 207	rb_link_node(&ins->rb_node, parent, p);
 208	rb_insert_color(&ins->rb_node, &ref_tree->rb_root);
 209
 210	return 0;
 211}
 212
 213/* Erase and free ref_node, caller should update ref_root->unique_refs */
 214static void ref_tree_remove(struct ref_root *ref_tree, struct ref_node *node)
 215{
 216	rb_erase(&node->rb_node, &ref_tree->rb_root);
 217	kfree(node);
 218}
 219
 220/*
 221 * Update ref_root->unique_refs
 222 *
 223 * Call __ref_tree_search
 224 *	1. if ref_node doesn't exist, ref_tree_insert this node, and update
 225 *	ref_root->unique_refs:
 226 *		if ref_node->ref_mod > 0, ref_root->unique_refs++;
 227 *		if ref_node->ref_mod < 0, do noting;
 228 *
 229 *	2. if ref_node is found, then get origin ref_node->ref_mod, and update
 230 *	ref_node->ref_mod.
 231 *		if ref_node->ref_mod is equal to 0,then call ref_tree_remove
 232 *
 233 *		according to origin_mod and new_mod, update ref_root->items
 234 *		+----------------+--------------+-------------+
 235 *		|		 |new_count <= 0|new_count > 0|
 236 *		+----------------+--------------+-------------+
 237 *		|origin_count < 0|       0      |      1      |
 238 *		+----------------+--------------+-------------+
 239 *		|origin_count > 0|      -1      |      0      |
 240 *		+----------------+--------------+-------------+
 241 *
 242 * In case of allocation failure, -ENOMEM is returned and the ref_tree stays
 243 * unaltered.
 244 * Success, return 0
 245 */
 246static int ref_tree_add(struct ref_root *ref_tree, u64 root_id, u64 object_id,
 247			u64 offset, u64 parent, int count)
 248{
 249	struct ref_node *node = NULL;
 250	struct rb_node **pos = NULL;
 251	struct rb_node *pos_parent = NULL;
 252	int origin_count;
 253	int ret;
 254
 255	if (!count)
 256		return 0;
 257
 258	node = __ref_tree_search(ref_tree, &pos, &pos_parent, root_id,
 259				 object_id, offset, parent);
 260	if (node == NULL) {
 261		node = kmalloc(sizeof(*node), GFP_NOFS);
 262		if (!node)
 263			return -ENOMEM;
 264
 265		node->root_id = root_id;
 266		node->object_id = object_id;
 267		node->offset = offset;
 268		node->parent = parent;
 269		node->ref_mod = count;
 270
 271		ret = ref_tree_insert(ref_tree, pos, pos_parent, node);
 272		ASSERT(!ret);
 273		if (ret) {
 274			kfree(node);
 275			return ret;
 276		}
 277
 278		ref_tree->unique_refs += node->ref_mod > 0 ? 1 : 0;
 279
 280		return 0;
 281	}
 282
 283	origin_count = node->ref_mod;
 284	node->ref_mod += count;
 285
 286	if (node->ref_mod > 0)
 287		ref_tree->unique_refs += origin_count > 0 ? 0 : 1;
 288	else if (node->ref_mod <= 0)
 289		ref_tree->unique_refs += origin_count > 0 ? -1 : 0;
 290
 291	if (!node->ref_mod)
 292		ref_tree_remove(ref_tree, node);
 293
 294	return 0;
 295}
 296
 297static int check_extent_in_eb(struct btrfs_key *key, struct extent_buffer *eb,
 298				struct btrfs_file_extent_item *fi,
 299				u64 extent_item_pos,
 300				struct extent_inode_elem **eie)
 301{
 302	u64 offset = 0;
 303	struct extent_inode_elem *e;
 304
 305	if (!btrfs_file_extent_compression(eb, fi) &&
 306	    !btrfs_file_extent_encryption(eb, fi) &&
 307	    !btrfs_file_extent_other_encoding(eb, fi)) {
 308		u64 data_offset;
 309		u64 data_len;
 310
 311		data_offset = btrfs_file_extent_offset(eb, fi);
 312		data_len = btrfs_file_extent_num_bytes(eb, fi);
 313
 314		if (extent_item_pos < data_offset ||
 315		    extent_item_pos >= data_offset + data_len)
 316			return 1;
 317		offset = extent_item_pos - data_offset;
 318	}
 319
 320	e = kmalloc(sizeof(*e), GFP_NOFS);
 321	if (!e)
 322		return -ENOMEM;
 323
 324	e->next = *eie;
 325	e->inum = key->objectid;
 326	e->offset = key->offset + offset;
 327	*eie = e;
 328
 329	return 0;
 330}
 331
 332static void free_inode_elem_list(struct extent_inode_elem *eie)
 333{
 334	struct extent_inode_elem *eie_next;
 335
 336	for (; eie; eie = eie_next) {
 337		eie_next = eie->next;
 338		kfree(eie);
 339	}
 340}
 341
 342static int find_extent_in_eb(struct extent_buffer *eb, u64 wanted_disk_byte,
 343				u64 extent_item_pos,
 344				struct extent_inode_elem **eie)
 345{
 346	u64 disk_byte;
 347	struct btrfs_key key;
 348	struct btrfs_file_extent_item *fi;
 349	int slot;
 350	int nritems;
 351	int extent_type;
 352	int ret;
 353
 354	/*
 355	 * from the shared data ref, we only have the leaf but we need
 356	 * the key. thus, we must look into all items and see that we
 357	 * find one (some) with a reference to our extent item.
 358	 */
 359	nritems = btrfs_header_nritems(eb);
 360	for (slot = 0; slot < nritems; ++slot) {
 361		btrfs_item_key_to_cpu(eb, &key, slot);
 362		if (key.type != BTRFS_EXTENT_DATA_KEY)
 363			continue;
 364		fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
 365		extent_type = btrfs_file_extent_type(eb, fi);
 366		if (extent_type == BTRFS_FILE_EXTENT_INLINE)
 367			continue;
 368		/* don't skip BTRFS_FILE_EXTENT_PREALLOC, we can handle that */
 369		disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);
 370		if (disk_byte != wanted_disk_byte)
 371			continue;
 372
 373		ret = check_extent_in_eb(&key, eb, fi, extent_item_pos, eie);
 374		if (ret < 0)
 375			return ret;
 376	}
 377
 378	return 0;
 379}
 380
 381/*
 382 * this structure records all encountered refs on the way up to the root
 383 */
 384struct __prelim_ref {
 385	struct list_head list;
 386	u64 root_id;
 387	struct btrfs_key key_for_search;
 388	int level;
 389	int count;
 390	struct extent_inode_elem *inode_list;
 391	u64 parent;
 392	u64 wanted_disk_byte;
 393};
 394
 395static struct kmem_cache *btrfs_prelim_ref_cache;
 396
 397int __init btrfs_prelim_ref_init(void)
 398{
 399	btrfs_prelim_ref_cache = kmem_cache_create("btrfs_prelim_ref",
 400					sizeof(struct __prelim_ref),
 401					0,
 402					SLAB_MEM_SPREAD,
 403					NULL);
 404	if (!btrfs_prelim_ref_cache)
 405		return -ENOMEM;
 406	return 0;
 407}
 408
 409void btrfs_prelim_ref_exit(void)
 410{
 411	kmem_cache_destroy(btrfs_prelim_ref_cache);
 412}
 413
 414/*
 415 * the rules for all callers of this function are:
 416 * - obtaining the parent is the goal
 417 * - if you add a key, you must know that it is a correct key
 418 * - if you cannot add the parent or a correct key, then we will look into the
 419 *   block later to set a correct key
 420 *
 421 * delayed refs
 422 * ============
 423 *        backref type | shared | indirect | shared | indirect
 424 * information         |   tree |     tree |   data |     data
 425 * --------------------+--------+----------+--------+----------
 426 *      parent logical |    y   |     -    |    -   |     -
 427 *      key to resolve |    -   |     y    |    y   |     y
 428 *  tree block logical |    -   |     -    |    -   |     -
 429 *  root for resolving |    y   |     y    |    y   |     y
 430 *
 431 * - column 1:       we've the parent -> done
 432 * - column 2, 3, 4: we use the key to find the parent
 433 *
 434 * on disk refs (inline or keyed)
 435 * ==============================
 436 *        backref type | shared | indirect | shared | indirect
 437 * information         |   tree |     tree |   data |     data
 438 * --------------------+--------+----------+--------+----------
 439 *      parent logical |    y   |     -    |    y   |     -
 440 *      key to resolve |    -   |     -    |    -   |     y
 441 *  tree block logical |    y   |     y    |    y   |     y
 442 *  root for resolving |    -   |     y    |    y   |     y
 443 *
 444 * - column 1, 3: we've the parent -> done
 445 * - column 2:    we take the first key from the block to find the parent
 446 *                (see __add_missing_keys)
 447 * - column 4:    we use the key to find the parent
 448 *
 449 * additional information that's available but not required to find the parent
 450 * block might help in merging entries to gain some speed.
 451 */
 452
 453static int __add_prelim_ref(struct list_head *head, u64 root_id,
 454			    struct btrfs_key *key, int level,
 455			    u64 parent, u64 wanted_disk_byte, int count,
 456			    gfp_t gfp_mask)
 457{
 458	struct __prelim_ref *ref;
 459
 460	if (root_id == BTRFS_DATA_RELOC_TREE_OBJECTID)
 461		return 0;
 462
 463	ref = kmem_cache_alloc(btrfs_prelim_ref_cache, gfp_mask);
 464	if (!ref)
 465		return -ENOMEM;
 466
 467	ref->root_id = root_id;
 468	if (key) {
 469		ref->key_for_search = *key;
 470		/*
 471		 * We can often find data backrefs with an offset that is too
 472		 * large (>= LLONG_MAX, maximum allowed file offset) due to
 473		 * underflows when subtracting a file's offset with the data
 474		 * offset of its corresponding extent data item. This can
 475		 * happen for example in the clone ioctl.
 476		 * So if we detect such case we set the search key's offset to
 477		 * zero to make sure we will find the matching file extent item
 478		 * at add_all_parents(), otherwise we will miss it because the
 479		 * offset taken form the backref is much larger then the offset
 480		 * of the file extent item. This can make us scan a very large
 481		 * number of file extent items, but at least it will not make
 482		 * us miss any.
 483		 * This is an ugly workaround for a behaviour that should have
 484		 * never existed, but it does and a fix for the clone ioctl
 485		 * would touch a lot of places, cause backwards incompatibility
 486		 * and would not fix the problem for extents cloned with older
 487		 * kernels.
 488		 */
 489		if (ref->key_for_search.type == BTRFS_EXTENT_DATA_KEY &&
 490		    ref->key_for_search.offset >= LLONG_MAX)
 491			ref->key_for_search.offset = 0;
 492	} else {
 493		memset(&ref->key_for_search, 0, sizeof(ref->key_for_search));
 494	}
 495
 496	ref->inode_list = NULL;
 497	ref->level = level;
 498	ref->count = count;
 499	ref->parent = parent;
 500	ref->wanted_disk_byte = wanted_disk_byte;
 501	list_add_tail(&ref->list, head);
 502
 503	return 0;
 504}
 505
 506static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path,
 507			   struct ulist *parents, struct __prelim_ref *ref,
 508			   int level, u64 time_seq, const u64 *extent_item_pos,
 509			   u64 total_refs)
 510{
 511	int ret = 0;
 512	int slot;
 513	struct extent_buffer *eb;
 514	struct btrfs_key key;
 515	struct btrfs_key *key_for_search = &ref->key_for_search;
 516	struct btrfs_file_extent_item *fi;
 517	struct extent_inode_elem *eie = NULL, *old = NULL;
 518	u64 disk_byte;
 519	u64 wanted_disk_byte = ref->wanted_disk_byte;
 520	u64 count = 0;
 521
 522	if (level != 0) {
 523		eb = path->nodes[level];
 524		ret = ulist_add(parents, eb->start, 0, GFP_NOFS);
 525		if (ret < 0)
 526			return ret;
 527		return 0;
 528	}
 529
 530	/*
 531	 * We normally enter this function with the path already pointing to
 532	 * the first item to check. But sometimes, we may enter it with
 533	 * slot==nritems. In that case, go to the next leaf before we continue.
 534	 */
 535	if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
 536		if (time_seq == (u64)-1)
 537			ret = btrfs_next_leaf(root, path);
 538		else
 539			ret = btrfs_next_old_leaf(root, path, time_seq);
 540	}
 541
 542	while (!ret && count < total_refs) {
 543		eb = path->nodes[0];
 544		slot = path->slots[0];
 545
 546		btrfs_item_key_to_cpu(eb, &key, slot);
 547
 548		if (key.objectid != key_for_search->objectid ||
 549		    key.type != BTRFS_EXTENT_DATA_KEY)
 550			break;
 551
 552		fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
 553		disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);
 554
 555		if (disk_byte == wanted_disk_byte) {
 556			eie = NULL;
 557			old = NULL;
 558			count++;
 559			if (extent_item_pos) {
 560				ret = check_extent_in_eb(&key, eb, fi,
 561						*extent_item_pos,
 562						&eie);
 563				if (ret < 0)
 564					break;
 565			}
 566			if (ret > 0)
 567				goto next;
 568			ret = ulist_add_merge_ptr(parents, eb->start,
 569						  eie, (void **)&old, GFP_NOFS);
 570			if (ret < 0)
 571				break;
 572			if (!ret && extent_item_pos) {
 573				while (old->next)
 574					old = old->next;
 575				old->next = eie;
 576			}
 577			eie = NULL;
 578		}
 579next:
 580		if (time_seq == (u64)-1)
 581			ret = btrfs_next_item(root, path);
 582		else
 583			ret = btrfs_next_old_item(root, path, time_seq);
 584	}
 585
 586	if (ret > 0)
 587		ret = 0;
 588	else if (ret < 0)
 589		free_inode_elem_list(eie);
 590	return ret;
 591}
 592
 593/*
 594 * resolve an indirect backref in the form (root_id, key, level)
 595 * to a logical address
 596 */
 597static int __resolve_indirect_ref(struct btrfs_fs_info *fs_info,
 598				  struct btrfs_path *path, u64 time_seq,
 599				  struct __prelim_ref *ref,
 600				  struct ulist *parents,
 601				  const u64 *extent_item_pos, u64 total_refs)
 602{
 603	struct btrfs_root *root;
 604	struct btrfs_key root_key;
 605	struct extent_buffer *eb;
 606	int ret = 0;
 607	int root_level;
 608	int level = ref->level;
 609	int index;
 610
 611	root_key.objectid = ref->root_id;
 612	root_key.type = BTRFS_ROOT_ITEM_KEY;
 613	root_key.offset = (u64)-1;
 614
 615	index = srcu_read_lock(&fs_info->subvol_srcu);
 616
 617	root = btrfs_get_fs_root(fs_info, &root_key, false);
 618	if (IS_ERR(root)) {
 619		srcu_read_unlock(&fs_info->subvol_srcu, index);
 620		ret = PTR_ERR(root);
 621		goto out;
 622	}
 623
 624	if (btrfs_is_testing(fs_info)) {
 625		srcu_read_unlock(&fs_info->subvol_srcu, index);
 626		ret = -ENOENT;
 627		goto out;
 628	}
 629
 630	if (path->search_commit_root)
 631		root_level = btrfs_header_level(root->commit_root);
 632	else if (time_seq == (u64)-1)
 633		root_level = btrfs_header_level(root->node);
 634	else
 635		root_level = btrfs_old_root_level(root, time_seq);
 636
 637	if (root_level + 1 == level) {
 638		srcu_read_unlock(&fs_info->subvol_srcu, index);
 639		goto out;
 640	}
 641
 642	path->lowest_level = level;
 643	if (time_seq == (u64)-1)
 644		ret = btrfs_search_slot(NULL, root, &ref->key_for_search, path,
 645					0, 0);
 646	else
 647		ret = btrfs_search_old_slot(root, &ref->key_for_search, path,
 648					    time_seq);
 649
 650	/* root node has been locked, we can release @subvol_srcu safely here */
 651	srcu_read_unlock(&fs_info->subvol_srcu, index);
 652
 653	btrfs_debug(fs_info,
 654		"search slot in root %llu (level %d, ref count %d) returned %d for key (%llu %u %llu)",
 655		 ref->root_id, level, ref->count, ret,
 656		 ref->key_for_search.objectid, ref->key_for_search.type,
 657		 ref->key_for_search.offset);
 658	if (ret < 0)
 659		goto out;
 660
 661	eb = path->nodes[level];
 662	while (!eb) {
 663		if (WARN_ON(!level)) {
 664			ret = 1;
 665			goto out;
 666		}
 667		level--;
 668		eb = path->nodes[level];
 669	}
 670
 671	ret = add_all_parents(root, path, parents, ref, level, time_seq,
 672			      extent_item_pos, total_refs);
 673out:
 674	path->lowest_level = 0;
 675	btrfs_release_path(path);
 676	return ret;
 677}
 678
 679/*
 680 * resolve all indirect backrefs from the list
 681 */
 682static int __resolve_indirect_refs(struct btrfs_fs_info *fs_info,
 683				   struct btrfs_path *path, u64 time_seq,
 684				   struct list_head *head,
 685				   const u64 *extent_item_pos, u64 total_refs,
 686				   u64 root_objectid)
 687{
 688	int err;
 689	int ret = 0;
 690	struct __prelim_ref *ref;
 691	struct __prelim_ref *ref_safe;
 692	struct __prelim_ref *new_ref;
 693	struct ulist *parents;
 694	struct ulist_node *node;
 695	struct ulist_iterator uiter;
 696
 697	parents = ulist_alloc(GFP_NOFS);
 698	if (!parents)
 699		return -ENOMEM;
 700
 701	/*
 702	 * _safe allows us to insert directly after the current item without
 703	 * iterating over the newly inserted items.
 704	 * we're also allowed to re-assign ref during iteration.
 705	 */
 706	list_for_each_entry_safe(ref, ref_safe, head, list) {
 707		if (ref->parent)	/* already direct */
 708			continue;
 709		if (ref->count == 0)
 710			continue;
 711		if (root_objectid && ref->root_id != root_objectid) {
 712			ret = BACKREF_FOUND_SHARED;
 713			goto out;
 714		}
 715		err = __resolve_indirect_ref(fs_info, path, time_seq, ref,
 716					     parents, extent_item_pos,
 717					     total_refs);
 718		/*
 719		 * we can only tolerate ENOENT,otherwise,we should catch error
 720		 * and return directly.
 721		 */
 722		if (err == -ENOENT) {
 723			continue;
 724		} else if (err) {
 725			ret = err;
 726			goto out;
 727		}
 728
 729		/* we put the first parent into the ref at hand */
 730		ULIST_ITER_INIT(&uiter);
 731		node = ulist_next(parents, &uiter);
 732		ref->parent = node ? node->val : 0;
 733		ref->inode_list = node ?
 734			(struct extent_inode_elem *)(uintptr_t)node->aux : NULL;
 735
 736		/* additional parents require new refs being added here */
 737		while ((node = ulist_next(parents, &uiter))) {
 738			new_ref = kmem_cache_alloc(btrfs_prelim_ref_cache,
 739						   GFP_NOFS);
 740			if (!new_ref) {
 741				ret = -ENOMEM;
 742				goto out;
 743			}
 744			memcpy(new_ref, ref, sizeof(*ref));
 745			new_ref->parent = node->val;
 746			new_ref->inode_list = (struct extent_inode_elem *)
 747							(uintptr_t)node->aux;
 748			list_add(&new_ref->list, &ref->list);
 749		}
 750		ulist_reinit(parents);
 751	}
 752out:
 753	ulist_free(parents);
 754	return ret;
 755}
 756
 757static inline int ref_for_same_block(struct __prelim_ref *ref1,
 758				     struct __prelim_ref *ref2)
 759{
 760	if (ref1->level != ref2->level)
 761		return 0;
 762	if (ref1->root_id != ref2->root_id)
 763		return 0;
 764	if (ref1->key_for_search.type != ref2->key_for_search.type)
 765		return 0;
 766	if (ref1->key_for_search.objectid != ref2->key_for_search.objectid)
 767		return 0;
 768	if (ref1->key_for_search.offset != ref2->key_for_search.offset)
 769		return 0;
 770	if (ref1->parent != ref2->parent)
 771		return 0;
 772
 773	return 1;
 774}
 775
 776/*
 777 * read tree blocks and add keys where required.
 778 */
 779static int __add_missing_keys(struct btrfs_fs_info *fs_info,
 780			      struct list_head *head)
 781{
 782	struct __prelim_ref *ref;
 783	struct extent_buffer *eb;
 784
 785	list_for_each_entry(ref, head, list) {
 786		if (ref->parent)
 787			continue;
 788		if (ref->key_for_search.type)
 789			continue;
 790		BUG_ON(!ref->wanted_disk_byte);
 791		eb = read_tree_block(fs_info, ref->wanted_disk_byte, 0);
 
 792		if (IS_ERR(eb)) {
 793			return PTR_ERR(eb);
 794		} else if (!extent_buffer_uptodate(eb)) {
 795			free_extent_buffer(eb);
 796			return -EIO;
 797		}
 798		btrfs_tree_read_lock(eb);
 799		if (btrfs_header_level(eb) == 0)
 800			btrfs_item_key_to_cpu(eb, &ref->key_for_search, 0);
 801		else
 802			btrfs_node_key_to_cpu(eb, &ref->key_for_search, 0);
 803		btrfs_tree_read_unlock(eb);
 804		free_extent_buffer(eb);
 805	}
 806	return 0;
 807}
 808
 809/*
 810 * merge backrefs and adjust counts accordingly
 811 *
 812 * mode = 1: merge identical keys, if key is set
 813 *    FIXME: if we add more keys in __add_prelim_ref, we can merge more here.
 814 *           additionally, we could even add a key range for the blocks we
 815 *           looked into to merge even more (-> replace unresolved refs by those
 816 *           having a parent).
 817 * mode = 2: merge identical parents
 818 */
 819static void __merge_refs(struct list_head *head, int mode)
 820{
 821	struct __prelim_ref *pos1;
 822
 823	list_for_each_entry(pos1, head, list) {
 824		struct __prelim_ref *pos2 = pos1, *tmp;
 825
 826		list_for_each_entry_safe_continue(pos2, tmp, head, list) {
 827			struct __prelim_ref *ref1 = pos1, *ref2 = pos2;
 828			struct extent_inode_elem *eie;
 829
 830			if (!ref_for_same_block(ref1, ref2))
 831				continue;
 832			if (mode == 1) {
 833				if (!ref1->parent && ref2->parent)
 834					swap(ref1, ref2);
 835			} else {
 836				if (ref1->parent != ref2->parent)
 837					continue;
 838			}
 839
 840			eie = ref1->inode_list;
 841			while (eie && eie->next)
 842				eie = eie->next;
 843			if (eie)
 844				eie->next = ref2->inode_list;
 845			else
 846				ref1->inode_list = ref2->inode_list;
 847			ref1->count += ref2->count;
 848
 849			list_del(&ref2->list);
 850			kmem_cache_free(btrfs_prelim_ref_cache, ref2);
 851			cond_resched();
 852		}
 853
 854	}
 855}
 856
 857/*
 858 * add all currently queued delayed refs from this head whose seq nr is
 859 * smaller or equal that seq to the list
 860 */
 861static int __add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
 862			      struct list_head *prefs, u64 *total_refs,
 863			      u64 inum)
 864{
 865	struct btrfs_delayed_ref_node *node;
 866	struct btrfs_delayed_extent_op *extent_op = head->extent_op;
 867	struct btrfs_key key;
 868	struct btrfs_key op_key = {0};
 869	int sgn;
 870	int ret = 0;
 871
 872	if (extent_op && extent_op->update_key)
 873		btrfs_disk_key_to_cpu(&op_key, &extent_op->key);
 874
 875	spin_lock(&head->lock);
 876	list_for_each_entry(node, &head->ref_list, list) {
 877		if (node->seq > seq)
 878			continue;
 879
 880		switch (node->action) {
 881		case BTRFS_ADD_DELAYED_EXTENT:
 882		case BTRFS_UPDATE_DELAYED_HEAD:
 883			WARN_ON(1);
 884			continue;
 885		case BTRFS_ADD_DELAYED_REF:
 886			sgn = 1;
 887			break;
 888		case BTRFS_DROP_DELAYED_REF:
 889			sgn = -1;
 890			break;
 891		default:
 892			BUG_ON(1);
 893		}
 894		*total_refs += (node->ref_mod * sgn);
 895		switch (node->type) {
 896		case BTRFS_TREE_BLOCK_REF_KEY: {
 897			struct btrfs_delayed_tree_ref *ref;
 898
 899			ref = btrfs_delayed_node_to_tree_ref(node);
 900			ret = __add_prelim_ref(prefs, ref->root, &op_key,
 901					       ref->level + 1, 0, node->bytenr,
 902					       node->ref_mod * sgn, GFP_ATOMIC);
 903			break;
 904		}
 905		case BTRFS_SHARED_BLOCK_REF_KEY: {
 906			struct btrfs_delayed_tree_ref *ref;
 907
 908			ref = btrfs_delayed_node_to_tree_ref(node);
 909			ret = __add_prelim_ref(prefs, 0, NULL,
 910					       ref->level + 1, ref->parent,
 911					       node->bytenr,
 912					       node->ref_mod * sgn, GFP_ATOMIC);
 913			break;
 914		}
 915		case BTRFS_EXTENT_DATA_REF_KEY: {
 916			struct btrfs_delayed_data_ref *ref;
 917			ref = btrfs_delayed_node_to_data_ref(node);
 918
 919			key.objectid = ref->objectid;
 920			key.type = BTRFS_EXTENT_DATA_KEY;
 921			key.offset = ref->offset;
 922
 923			/*
 924			 * Found a inum that doesn't match our known inum, we
 925			 * know it's shared.
 926			 */
 927			if (inum && ref->objectid != inum) {
 928				ret = BACKREF_FOUND_SHARED;
 929				break;
 930			}
 931
 932			ret = __add_prelim_ref(prefs, ref->root, &key, 0, 0,
 933					       node->bytenr,
 934					       node->ref_mod * sgn, GFP_ATOMIC);
 935			break;
 936		}
 937		case BTRFS_SHARED_DATA_REF_KEY: {
 938			struct btrfs_delayed_data_ref *ref;
 939
 940			ref = btrfs_delayed_node_to_data_ref(node);
 941			ret = __add_prelim_ref(prefs, 0, NULL, 0,
 942					       ref->parent, node->bytenr,
 943					       node->ref_mod * sgn, GFP_ATOMIC);
 944			break;
 945		}
 946		default:
 947			WARN_ON(1);
 948		}
 949		if (ret)
 950			break;
 951	}
 952	spin_unlock(&head->lock);
 953	return ret;
 954}
 955
 956/*
 957 * add all inline backrefs for bytenr to the list
 958 */
 959static int __add_inline_refs(struct btrfs_fs_info *fs_info,
 960			     struct btrfs_path *path, u64 bytenr,
 961			     int *info_level, struct list_head *prefs,
 962			     struct ref_root *ref_tree,
 963			     u64 *total_refs, u64 inum)
 964{
 965	int ret = 0;
 966	int slot;
 967	struct extent_buffer *leaf;
 968	struct btrfs_key key;
 969	struct btrfs_key found_key;
 970	unsigned long ptr;
 971	unsigned long end;
 972	struct btrfs_extent_item *ei;
 973	u64 flags;
 974	u64 item_size;
 975
 976	/*
 977	 * enumerate all inline refs
 978	 */
 979	leaf = path->nodes[0];
 980	slot = path->slots[0];
 981
 982	item_size = btrfs_item_size_nr(leaf, slot);
 983	BUG_ON(item_size < sizeof(*ei));
 984
 985	ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
 986	flags = btrfs_extent_flags(leaf, ei);
 987	*total_refs += btrfs_extent_refs(leaf, ei);
 988	btrfs_item_key_to_cpu(leaf, &found_key, slot);
 989
 990	ptr = (unsigned long)(ei + 1);
 991	end = (unsigned long)ei + item_size;
 992
 993	if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
 994	    flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
 995		struct btrfs_tree_block_info *info;
 996
 997		info = (struct btrfs_tree_block_info *)ptr;
 998		*info_level = btrfs_tree_block_level(leaf, info);
 999		ptr += sizeof(struct btrfs_tree_block_info);
1000		BUG_ON(ptr > end);
1001	} else if (found_key.type == BTRFS_METADATA_ITEM_KEY) {
1002		*info_level = found_key.offset;
1003	} else {
1004		BUG_ON(!(flags & BTRFS_EXTENT_FLAG_DATA));
1005	}
1006
1007	while (ptr < end) {
1008		struct btrfs_extent_inline_ref *iref;
1009		u64 offset;
1010		int type;
1011
1012		iref = (struct btrfs_extent_inline_ref *)ptr;
1013		type = btrfs_extent_inline_ref_type(leaf, iref);
1014		offset = btrfs_extent_inline_ref_offset(leaf, iref);
1015
1016		switch (type) {
1017		case BTRFS_SHARED_BLOCK_REF_KEY:
1018			ret = __add_prelim_ref(prefs, 0, NULL,
1019						*info_level + 1, offset,
1020						bytenr, 1, GFP_NOFS);
1021			break;
1022		case BTRFS_SHARED_DATA_REF_KEY: {
1023			struct btrfs_shared_data_ref *sdref;
1024			int count;
1025
1026			sdref = (struct btrfs_shared_data_ref *)(iref + 1);
1027			count = btrfs_shared_data_ref_count(leaf, sdref);
1028			ret = __add_prelim_ref(prefs, 0, NULL, 0, offset,
1029					       bytenr, count, GFP_NOFS);
1030			if (ref_tree) {
1031				if (!ret)
1032					ret = ref_tree_add(ref_tree, 0, 0, 0,
1033							   bytenr, count);
1034				if (!ret && ref_tree->unique_refs > 1)
1035					ret = BACKREF_FOUND_SHARED;
1036			}
1037			break;
1038		}
1039		case BTRFS_TREE_BLOCK_REF_KEY:
1040			ret = __add_prelim_ref(prefs, offset, NULL,
1041					       *info_level + 1, 0,
1042					       bytenr, 1, GFP_NOFS);
1043			break;
1044		case BTRFS_EXTENT_DATA_REF_KEY: {
1045			struct btrfs_extent_data_ref *dref;
1046			int count;
1047			u64 root;
1048
1049			dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1050			count = btrfs_extent_data_ref_count(leaf, dref);
1051			key.objectid = btrfs_extent_data_ref_objectid(leaf,
1052								      dref);
1053			key.type = BTRFS_EXTENT_DATA_KEY;
1054			key.offset = btrfs_extent_data_ref_offset(leaf, dref);
1055
1056			if (inum && key.objectid != inum) {
1057				ret = BACKREF_FOUND_SHARED;
1058				break;
1059			}
1060
1061			root = btrfs_extent_data_ref_root(leaf, dref);
1062			ret = __add_prelim_ref(prefs, root, &key, 0, 0,
1063					       bytenr, count, GFP_NOFS);
1064			if (ref_tree) {
1065				if (!ret)
1066					ret = ref_tree_add(ref_tree, root,
1067							   key.objectid,
1068							   key.offset, 0,
1069							   count);
1070				if (!ret && ref_tree->unique_refs > 1)
1071					ret = BACKREF_FOUND_SHARED;
1072			}
1073			break;
1074		}
1075		default:
1076			WARN_ON(1);
1077		}
1078		if (ret)
1079			return ret;
1080		ptr += btrfs_extent_inline_ref_size(type);
1081	}
1082
1083	return 0;
1084}
1085
1086/*
1087 * add all non-inline backrefs for bytenr to the list
1088 */
1089static int __add_keyed_refs(struct btrfs_fs_info *fs_info,
1090			    struct btrfs_path *path, u64 bytenr,
1091			    int info_level, struct list_head *prefs,
1092			    struct ref_root *ref_tree, u64 inum)
1093{
1094	struct btrfs_root *extent_root = fs_info->extent_root;
1095	int ret;
1096	int slot;
1097	struct extent_buffer *leaf;
1098	struct btrfs_key key;
1099
1100	while (1) {
1101		ret = btrfs_next_item(extent_root, path);
1102		if (ret < 0)
1103			break;
1104		if (ret) {
1105			ret = 0;
1106			break;
1107		}
1108
1109		slot = path->slots[0];
1110		leaf = path->nodes[0];
1111		btrfs_item_key_to_cpu(leaf, &key, slot);
1112
1113		if (key.objectid != bytenr)
1114			break;
1115		if (key.type < BTRFS_TREE_BLOCK_REF_KEY)
1116			continue;
1117		if (key.type > BTRFS_SHARED_DATA_REF_KEY)
1118			break;
1119
1120		switch (key.type) {
1121		case BTRFS_SHARED_BLOCK_REF_KEY:
1122			ret = __add_prelim_ref(prefs, 0, NULL,
1123						info_level + 1, key.offset,
1124						bytenr, 1, GFP_NOFS);
1125			break;
1126		case BTRFS_SHARED_DATA_REF_KEY: {
1127			struct btrfs_shared_data_ref *sdref;
1128			int count;
1129
1130			sdref = btrfs_item_ptr(leaf, slot,
1131					      struct btrfs_shared_data_ref);
1132			count = btrfs_shared_data_ref_count(leaf, sdref);
1133			ret = __add_prelim_ref(prefs, 0, NULL, 0, key.offset,
1134						bytenr, count, GFP_NOFS);
1135			if (ref_tree) {
1136				if (!ret)
1137					ret = ref_tree_add(ref_tree, 0, 0, 0,
1138							   bytenr, count);
1139				if (!ret && ref_tree->unique_refs > 1)
1140					ret = BACKREF_FOUND_SHARED;
1141			}
1142			break;
1143		}
1144		case BTRFS_TREE_BLOCK_REF_KEY:
1145			ret = __add_prelim_ref(prefs, key.offset, NULL,
1146					       info_level + 1, 0,
1147					       bytenr, 1, GFP_NOFS);
1148			break;
1149		case BTRFS_EXTENT_DATA_REF_KEY: {
1150			struct btrfs_extent_data_ref *dref;
1151			int count;
1152			u64 root;
1153
1154			dref = btrfs_item_ptr(leaf, slot,
1155					      struct btrfs_extent_data_ref);
1156			count = btrfs_extent_data_ref_count(leaf, dref);
1157			key.objectid = btrfs_extent_data_ref_objectid(leaf,
1158								      dref);
1159			key.type = BTRFS_EXTENT_DATA_KEY;
1160			key.offset = btrfs_extent_data_ref_offset(leaf, dref);
1161
1162			if (inum && key.objectid != inum) {
1163				ret = BACKREF_FOUND_SHARED;
1164				break;
1165			}
1166
1167			root = btrfs_extent_data_ref_root(leaf, dref);
1168			ret = __add_prelim_ref(prefs, root, &key, 0, 0,
1169					       bytenr, count, GFP_NOFS);
1170			if (ref_tree) {
1171				if (!ret)
1172					ret = ref_tree_add(ref_tree, root,
1173							   key.objectid,
1174							   key.offset, 0,
1175							   count);
1176				if (!ret && ref_tree->unique_refs > 1)
1177					ret = BACKREF_FOUND_SHARED;
1178			}
1179			break;
1180		}
1181		default:
1182			WARN_ON(1);
1183		}
1184		if (ret)
1185			return ret;
1186
1187	}
1188
1189	return ret;
1190}
1191
1192/*
1193 * this adds all existing backrefs (inline backrefs, backrefs and delayed
1194 * refs) for the given bytenr to the refs list, merges duplicates and resolves
1195 * indirect refs to their parent bytenr.
1196 * When roots are found, they're added to the roots list
1197 *
1198 * NOTE: This can return values > 0
1199 *
1200 * If time_seq is set to (u64)-1, it will not search delayed_refs, and behave
1201 * much like trans == NULL case, the difference only lies in it will not
1202 * commit root.
1203 * The special case is for qgroup to search roots in commit_transaction().
1204 *
1205 * If check_shared is set to 1, any extent has more than one ref item, will
1206 * be returned BACKREF_FOUND_SHARED immediately.
1207 *
1208 * FIXME some caching might speed things up
1209 */
1210static int find_parent_nodes(struct btrfs_trans_handle *trans,
1211			     struct btrfs_fs_info *fs_info, u64 bytenr,
1212			     u64 time_seq, struct ulist *refs,
1213			     struct ulist *roots, const u64 *extent_item_pos,
1214			     u64 root_objectid, u64 inum, int check_shared)
1215{
1216	struct btrfs_key key;
1217	struct btrfs_path *path;
1218	struct btrfs_delayed_ref_root *delayed_refs = NULL;
1219	struct btrfs_delayed_ref_head *head;
1220	int info_level = 0;
1221	int ret;
1222	struct list_head prefs_delayed;
1223	struct list_head prefs;
1224	struct __prelim_ref *ref;
1225	struct extent_inode_elem *eie = NULL;
1226	struct ref_root *ref_tree = NULL;
1227	u64 total_refs = 0;
1228
1229	INIT_LIST_HEAD(&prefs);
1230	INIT_LIST_HEAD(&prefs_delayed);
1231
1232	key.objectid = bytenr;
1233	key.offset = (u64)-1;
1234	if (btrfs_fs_incompat(fs_info, SKINNY_METADATA))
1235		key.type = BTRFS_METADATA_ITEM_KEY;
1236	else
1237		key.type = BTRFS_EXTENT_ITEM_KEY;
1238
1239	path = btrfs_alloc_path();
1240	if (!path)
1241		return -ENOMEM;
1242	if (!trans) {
1243		path->search_commit_root = 1;
1244		path->skip_locking = 1;
1245	}
1246
1247	if (time_seq == (u64)-1)
1248		path->skip_locking = 1;
1249
1250	/*
1251	 * grab both a lock on the path and a lock on the delayed ref head.
1252	 * We need both to get a consistent picture of how the refs look
1253	 * at a specified point in time
1254	 */
1255again:
1256	head = NULL;
1257
1258	if (check_shared) {
1259		if (!ref_tree) {
1260			ref_tree = ref_root_alloc();
1261			if (!ref_tree) {
1262				ret = -ENOMEM;
1263				goto out;
1264			}
1265		} else {
1266			ref_root_fini(ref_tree);
1267		}
1268	}
1269
1270	ret = btrfs_search_slot(trans, fs_info->extent_root, &key, path, 0, 0);
1271	if (ret < 0)
1272		goto out;
1273	BUG_ON(ret == 0);
1274
1275#ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
1276	if (trans && likely(trans->type != __TRANS_DUMMY) &&
1277	    time_seq != (u64)-1) {
1278#else
1279	if (trans && time_seq != (u64)-1) {
1280#endif
1281		/*
1282		 * look if there are updates for this ref queued and lock the
1283		 * head
1284		 */
1285		delayed_refs = &trans->transaction->delayed_refs;
1286		spin_lock(&delayed_refs->lock);
1287		head = btrfs_find_delayed_ref_head(trans, bytenr);
1288		if (head) {
1289			if (!mutex_trylock(&head->mutex)) {
1290				atomic_inc(&head->node.refs);
1291				spin_unlock(&delayed_refs->lock);
1292
1293				btrfs_release_path(path);
1294
1295				/*
1296				 * Mutex was contended, block until it's
1297				 * released and try again
1298				 */
1299				mutex_lock(&head->mutex);
1300				mutex_unlock(&head->mutex);
1301				btrfs_put_delayed_ref(&head->node);
1302				goto again;
1303			}
1304			spin_unlock(&delayed_refs->lock);
1305			ret = __add_delayed_refs(head, time_seq,
1306						 &prefs_delayed, &total_refs,
1307						 inum);
1308			mutex_unlock(&head->mutex);
1309			if (ret)
1310				goto out;
1311		} else {
1312			spin_unlock(&delayed_refs->lock);
1313		}
1314
1315		if (check_shared && !list_empty(&prefs_delayed)) {
1316			/*
1317			 * Add all delay_ref to the ref_tree and check if there
1318			 * are multiple ref items added.
1319			 */
1320			list_for_each_entry(ref, &prefs_delayed, list) {
1321				if (ref->key_for_search.type) {
1322					ret = ref_tree_add(ref_tree,
1323						ref->root_id,
1324						ref->key_for_search.objectid,
1325						ref->key_for_search.offset,
1326						0, ref->count);
1327					if (ret)
1328						goto out;
1329				} else {
1330					ret = ref_tree_add(ref_tree, 0, 0, 0,
1331						     ref->parent, ref->count);
1332					if (ret)
1333						goto out;
1334				}
1335
1336			}
1337
1338			if (ref_tree->unique_refs > 1) {
1339				ret = BACKREF_FOUND_SHARED;
1340				goto out;
1341			}
1342
1343		}
1344	}
1345
1346	if (path->slots[0]) {
1347		struct extent_buffer *leaf;
1348		int slot;
1349
1350		path->slots[0]--;
1351		leaf = path->nodes[0];
1352		slot = path->slots[0];
1353		btrfs_item_key_to_cpu(leaf, &key, slot);
1354		if (key.objectid == bytenr &&
1355		    (key.type == BTRFS_EXTENT_ITEM_KEY ||
1356		     key.type == BTRFS_METADATA_ITEM_KEY)) {
1357			ret = __add_inline_refs(fs_info, path, bytenr,
1358						&info_level, &prefs,
1359						ref_tree, &total_refs,
1360						inum);
1361			if (ret)
1362				goto out;
1363			ret = __add_keyed_refs(fs_info, path, bytenr,
1364					       info_level, &prefs,
1365					       ref_tree, inum);
1366			if (ret)
1367				goto out;
1368		}
1369	}
1370	btrfs_release_path(path);
1371
1372	list_splice_init(&prefs_delayed, &prefs);
1373
1374	ret = __add_missing_keys(fs_info, &prefs);
1375	if (ret)
1376		goto out;
1377
1378	__merge_refs(&prefs, 1);
1379
1380	ret = __resolve_indirect_refs(fs_info, path, time_seq, &prefs,
1381				      extent_item_pos, total_refs,
1382				      root_objectid);
1383	if (ret)
1384		goto out;
1385
1386	__merge_refs(&prefs, 2);
1387
1388	while (!list_empty(&prefs)) {
1389		ref = list_first_entry(&prefs, struct __prelim_ref, list);
1390		WARN_ON(ref->count < 0);
1391		if (roots && ref->count && ref->root_id && ref->parent == 0) {
1392			if (root_objectid && ref->root_id != root_objectid) {
1393				ret = BACKREF_FOUND_SHARED;
1394				goto out;
1395			}
1396
1397			/* no parent == root of tree */
1398			ret = ulist_add(roots, ref->root_id, 0, GFP_NOFS);
1399			if (ret < 0)
1400				goto out;
1401		}
1402		if (ref->count && ref->parent) {
1403			if (extent_item_pos && !ref->inode_list &&
1404			    ref->level == 0) {
1405				struct extent_buffer *eb;
1406
1407				eb = read_tree_block(fs_info, ref->parent, 0);
 
1408				if (IS_ERR(eb)) {
1409					ret = PTR_ERR(eb);
1410					goto out;
1411				} else if (!extent_buffer_uptodate(eb)) {
1412					free_extent_buffer(eb);
1413					ret = -EIO;
1414					goto out;
1415				}
1416				btrfs_tree_read_lock(eb);
1417				btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
1418				ret = find_extent_in_eb(eb, bytenr,
1419							*extent_item_pos, &eie);
1420				btrfs_tree_read_unlock_blocking(eb);
1421				free_extent_buffer(eb);
1422				if (ret < 0)
1423					goto out;
1424				ref->inode_list = eie;
1425			}
1426			ret = ulist_add_merge_ptr(refs, ref->parent,
1427						  ref->inode_list,
1428						  (void **)&eie, GFP_NOFS);
1429			if (ret < 0)
1430				goto out;
1431			if (!ret && extent_item_pos) {
1432				/*
1433				 * we've recorded that parent, so we must extend
1434				 * its inode list here
1435				 */
1436				BUG_ON(!eie);
1437				while (eie->next)
1438					eie = eie->next;
1439				eie->next = ref->inode_list;
1440			}
1441			eie = NULL;
1442		}
1443		list_del(&ref->list);
1444		kmem_cache_free(btrfs_prelim_ref_cache, ref);
1445	}
1446
1447out:
1448	btrfs_free_path(path);
1449	ref_root_free(ref_tree);
1450	while (!list_empty(&prefs)) {
1451		ref = list_first_entry(&prefs, struct __prelim_ref, list);
1452		list_del(&ref->list);
1453		kmem_cache_free(btrfs_prelim_ref_cache, ref);
1454	}
1455	while (!list_empty(&prefs_delayed)) {
1456		ref = list_first_entry(&prefs_delayed, struct __prelim_ref,
1457				       list);
1458		list_del(&ref->list);
1459		kmem_cache_free(btrfs_prelim_ref_cache, ref);
1460	}
1461	if (ret < 0)
1462		free_inode_elem_list(eie);
1463	return ret;
1464}
1465
1466static void free_leaf_list(struct ulist *blocks)
1467{
1468	struct ulist_node *node = NULL;
1469	struct extent_inode_elem *eie;
1470	struct ulist_iterator uiter;
1471
1472	ULIST_ITER_INIT(&uiter);
1473	while ((node = ulist_next(blocks, &uiter))) {
1474		if (!node->aux)
1475			continue;
1476		eie = (struct extent_inode_elem *)(uintptr_t)node->aux;
1477		free_inode_elem_list(eie);
1478		node->aux = 0;
1479	}
1480
1481	ulist_free(blocks);
1482}
1483
1484/*
1485 * Finds all leafs with a reference to the specified combination of bytenr and
1486 * offset. key_list_head will point to a list of corresponding keys (caller must
1487 * free each list element). The leafs will be stored in the leafs ulist, which
1488 * must be freed with ulist_free.
1489 *
1490 * returns 0 on success, <0 on error
1491 */
1492static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
1493				struct btrfs_fs_info *fs_info, u64 bytenr,
1494				u64 time_seq, struct ulist **leafs,
1495				const u64 *extent_item_pos)
1496{
1497	int ret;
1498
1499	*leafs = ulist_alloc(GFP_NOFS);
1500	if (!*leafs)
1501		return -ENOMEM;
1502
1503	ret = find_parent_nodes(trans, fs_info, bytenr, time_seq,
1504				*leafs, NULL, extent_item_pos, 0, 0, 0);
1505	if (ret < 0 && ret != -ENOENT) {
1506		free_leaf_list(*leafs);
1507		return ret;
1508	}
1509
1510	return 0;
1511}
1512
1513/*
1514 * walk all backrefs for a given extent to find all roots that reference this
1515 * extent. Walking a backref means finding all extents that reference this
1516 * extent and in turn walk the backrefs of those, too. Naturally this is a
1517 * recursive process, but here it is implemented in an iterative fashion: We
1518 * find all referencing extents for the extent in question and put them on a
1519 * list. In turn, we find all referencing extents for those, further appending
1520 * to the list. The way we iterate the list allows adding more elements after
1521 * the current while iterating. The process stops when we reach the end of the
1522 * list. Found roots are added to the roots list.
1523 *
1524 * returns 0 on success, < 0 on error.
1525 */
1526static int __btrfs_find_all_roots(struct btrfs_trans_handle *trans,
1527				  struct btrfs_fs_info *fs_info, u64 bytenr,
1528				  u64 time_seq, struct ulist **roots)
1529{
1530	struct ulist *tmp;
1531	struct ulist_node *node = NULL;
1532	struct ulist_iterator uiter;
1533	int ret;
1534
1535	tmp = ulist_alloc(GFP_NOFS);
1536	if (!tmp)
1537		return -ENOMEM;
1538	*roots = ulist_alloc(GFP_NOFS);
1539	if (!*roots) {
1540		ulist_free(tmp);
1541		return -ENOMEM;
1542	}
1543
1544	ULIST_ITER_INIT(&uiter);
1545	while (1) {
1546		ret = find_parent_nodes(trans, fs_info, bytenr, time_seq,
1547					tmp, *roots, NULL, 0, 0, 0);
1548		if (ret < 0 && ret != -ENOENT) {
1549			ulist_free(tmp);
1550			ulist_free(*roots);
1551			return ret;
1552		}
1553		node = ulist_next(tmp, &uiter);
1554		if (!node)
1555			break;
1556		bytenr = node->val;
1557		cond_resched();
1558	}
1559
1560	ulist_free(tmp);
1561	return 0;
1562}
1563
1564int btrfs_find_all_roots(struct btrfs_trans_handle *trans,
1565			 struct btrfs_fs_info *fs_info, u64 bytenr,
1566			 u64 time_seq, struct ulist **roots)
1567{
1568	int ret;
1569
1570	if (!trans)
1571		down_read(&fs_info->commit_root_sem);
1572	ret = __btrfs_find_all_roots(trans, fs_info, bytenr, time_seq, roots);
1573	if (!trans)
1574		up_read(&fs_info->commit_root_sem);
1575	return ret;
1576}
1577
1578/**
1579 * btrfs_check_shared - tell us whether an extent is shared
1580 *
1581 * @trans: optional trans handle
1582 *
1583 * btrfs_check_shared uses the backref walking code but will short
1584 * circuit as soon as it finds a root or inode that doesn't match the
1585 * one passed in. This provides a significant performance benefit for
1586 * callers (such as fiemap) which want to know whether the extent is
1587 * shared but do not need a ref count.
1588 *
1589 * Return: 0 if extent is not shared, 1 if it is shared, < 0 on error.
1590 */
1591int btrfs_check_shared(struct btrfs_trans_handle *trans,
1592		       struct btrfs_fs_info *fs_info, u64 root_objectid,
1593		       u64 inum, u64 bytenr)
1594{
1595	struct ulist *tmp = NULL;
1596	struct ulist *roots = NULL;
1597	struct ulist_iterator uiter;
1598	struct ulist_node *node;
1599	struct seq_list elem = SEQ_LIST_INIT(elem);
1600	int ret = 0;
1601
1602	tmp = ulist_alloc(GFP_NOFS);
1603	roots = ulist_alloc(GFP_NOFS);
1604	if (!tmp || !roots) {
1605		ulist_free(tmp);
1606		ulist_free(roots);
1607		return -ENOMEM;
1608	}
1609
1610	if (trans)
1611		btrfs_get_tree_mod_seq(fs_info, &elem);
1612	else
1613		down_read(&fs_info->commit_root_sem);
1614	ULIST_ITER_INIT(&uiter);
1615	while (1) {
1616		ret = find_parent_nodes(trans, fs_info, bytenr, elem.seq, tmp,
1617					roots, NULL, root_objectid, inum, 1);
1618		if (ret == BACKREF_FOUND_SHARED) {
1619			/* this is the only condition under which we return 1 */
1620			ret = 1;
1621			break;
1622		}
1623		if (ret < 0 && ret != -ENOENT)
1624			break;
1625		ret = 0;
1626		node = ulist_next(tmp, &uiter);
1627		if (!node)
1628			break;
1629		bytenr = node->val;
1630		cond_resched();
1631	}
1632	if (trans)
1633		btrfs_put_tree_mod_seq(fs_info, &elem);
1634	else
1635		up_read(&fs_info->commit_root_sem);
1636	ulist_free(tmp);
1637	ulist_free(roots);
1638	return ret;
1639}
1640
1641int btrfs_find_one_extref(struct btrfs_root *root, u64 inode_objectid,
1642			  u64 start_off, struct btrfs_path *path,
1643			  struct btrfs_inode_extref **ret_extref,
1644			  u64 *found_off)
1645{
1646	int ret, slot;
1647	struct btrfs_key key;
1648	struct btrfs_key found_key;
1649	struct btrfs_inode_extref *extref;
1650	struct extent_buffer *leaf;
1651	unsigned long ptr;
1652
1653	key.objectid = inode_objectid;
1654	key.type = BTRFS_INODE_EXTREF_KEY;
1655	key.offset = start_off;
1656
1657	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1658	if (ret < 0)
1659		return ret;
1660
1661	while (1) {
1662		leaf = path->nodes[0];
1663		slot = path->slots[0];
1664		if (slot >= btrfs_header_nritems(leaf)) {
1665			/*
1666			 * If the item at offset is not found,
1667			 * btrfs_search_slot will point us to the slot
1668			 * where it should be inserted. In our case
1669			 * that will be the slot directly before the
1670			 * next INODE_REF_KEY_V2 item. In the case
1671			 * that we're pointing to the last slot in a
1672			 * leaf, we must move one leaf over.
1673			 */
1674			ret = btrfs_next_leaf(root, path);
1675			if (ret) {
1676				if (ret >= 1)
1677					ret = -ENOENT;
1678				break;
1679			}
1680			continue;
1681		}
1682
1683		btrfs_item_key_to_cpu(leaf, &found_key, slot);
1684
1685		/*
1686		 * Check that we're still looking at an extended ref key for
1687		 * this particular objectid. If we have different
1688		 * objectid or type then there are no more to be found
1689		 * in the tree and we can exit.
1690		 */
1691		ret = -ENOENT;
1692		if (found_key.objectid != inode_objectid)
1693			break;
1694		if (found_key.type != BTRFS_INODE_EXTREF_KEY)
1695			break;
1696
1697		ret = 0;
1698		ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
1699		extref = (struct btrfs_inode_extref *)ptr;
1700		*ret_extref = extref;
1701		if (found_off)
1702			*found_off = found_key.offset;
1703		break;
1704	}
1705
1706	return ret;
1707}
1708
1709/*
1710 * this iterates to turn a name (from iref/extref) into a full filesystem path.
1711 * Elements of the path are separated by '/' and the path is guaranteed to be
1712 * 0-terminated. the path is only given within the current file system.
1713 * Therefore, it never starts with a '/'. the caller is responsible to provide
1714 * "size" bytes in "dest". the dest buffer will be filled backwards. finally,
1715 * the start point of the resulting string is returned. this pointer is within
1716 * dest, normally.
1717 * in case the path buffer would overflow, the pointer is decremented further
1718 * as if output was written to the buffer, though no more output is actually
1719 * generated. that way, the caller can determine how much space would be
1720 * required for the path to fit into the buffer. in that case, the returned
1721 * value will be smaller than dest. callers must check this!
1722 */
1723char *btrfs_ref_to_path(struct btrfs_root *fs_root, struct btrfs_path *path,
1724			u32 name_len, unsigned long name_off,
1725			struct extent_buffer *eb_in, u64 parent,
1726			char *dest, u32 size)
1727{
1728	int slot;
1729	u64 next_inum;
1730	int ret;
1731	s64 bytes_left = ((s64)size) - 1;
1732	struct extent_buffer *eb = eb_in;
1733	struct btrfs_key found_key;
1734	int leave_spinning = path->leave_spinning;
1735	struct btrfs_inode_ref *iref;
1736
1737	if (bytes_left >= 0)
1738		dest[bytes_left] = '\0';
1739
1740	path->leave_spinning = 1;
1741	while (1) {
1742		bytes_left -= name_len;
1743		if (bytes_left >= 0)
1744			read_extent_buffer(eb, dest + bytes_left,
1745					   name_off, name_len);
1746		if (eb != eb_in) {
1747			if (!path->skip_locking)
1748				btrfs_tree_read_unlock_blocking(eb);
1749			free_extent_buffer(eb);
1750		}
1751		ret = btrfs_find_item(fs_root, path, parent, 0,
1752				BTRFS_INODE_REF_KEY, &found_key);
1753		if (ret > 0)
1754			ret = -ENOENT;
1755		if (ret)
1756			break;
1757
1758		next_inum = found_key.offset;
1759
1760		/* regular exit ahead */
1761		if (parent == next_inum)
1762			break;
1763
1764		slot = path->slots[0];
1765		eb = path->nodes[0];
1766		/* make sure we can use eb after releasing the path */
1767		if (eb != eb_in) {
1768			if (!path->skip_locking)
1769				btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
1770			path->nodes[0] = NULL;
1771			path->locks[0] = 0;
1772		}
1773		btrfs_release_path(path);
1774		iref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
1775
1776		name_len = btrfs_inode_ref_name_len(eb, iref);
1777		name_off = (unsigned long)(iref + 1);
1778
1779		parent = next_inum;
1780		--bytes_left;
1781		if (bytes_left >= 0)
1782			dest[bytes_left] = '/';
1783	}
1784
1785	btrfs_release_path(path);
1786	path->leave_spinning = leave_spinning;
1787
1788	if (ret)
1789		return ERR_PTR(ret);
1790
1791	return dest + bytes_left;
1792}
1793
1794/*
1795 * this makes the path point to (logical EXTENT_ITEM *)
1796 * returns BTRFS_EXTENT_FLAG_DATA for data, BTRFS_EXTENT_FLAG_TREE_BLOCK for
1797 * tree blocks and <0 on error.
1798 */
1799int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical,
1800			struct btrfs_path *path, struct btrfs_key *found_key,
1801			u64 *flags_ret)
1802{
1803	int ret;
1804	u64 flags;
1805	u64 size = 0;
1806	u32 item_size;
1807	struct extent_buffer *eb;
1808	struct btrfs_extent_item *ei;
1809	struct btrfs_key key;
1810
1811	if (btrfs_fs_incompat(fs_info, SKINNY_METADATA))
1812		key.type = BTRFS_METADATA_ITEM_KEY;
1813	else
1814		key.type = BTRFS_EXTENT_ITEM_KEY;
1815	key.objectid = logical;
1816	key.offset = (u64)-1;
1817
1818	ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, path, 0, 0);
1819	if (ret < 0)
1820		return ret;
1821
1822	ret = btrfs_previous_extent_item(fs_info->extent_root, path, 0);
1823	if (ret) {
1824		if (ret > 0)
1825			ret = -ENOENT;
1826		return ret;
1827	}
1828	btrfs_item_key_to_cpu(path->nodes[0], found_key, path->slots[0]);
1829	if (found_key->type == BTRFS_METADATA_ITEM_KEY)
1830		size = fs_info->nodesize;
1831	else if (found_key->type == BTRFS_EXTENT_ITEM_KEY)
1832		size = found_key->offset;
1833
1834	if (found_key->objectid > logical ||
1835	    found_key->objectid + size <= logical) {
1836		btrfs_debug(fs_info,
1837			"logical %llu is not within any extent", logical);
1838		return -ENOENT;
1839	}
1840
1841	eb = path->nodes[0];
1842	item_size = btrfs_item_size_nr(eb, path->slots[0]);
1843	BUG_ON(item_size < sizeof(*ei));
1844
1845	ei = btrfs_item_ptr(eb, path->slots[0], struct btrfs_extent_item);
1846	flags = btrfs_extent_flags(eb, ei);
1847
1848	btrfs_debug(fs_info,
1849		"logical %llu is at position %llu within the extent (%llu EXTENT_ITEM %llu) flags %#llx size %u",
1850		 logical, logical - found_key->objectid, found_key->objectid,
1851		 found_key->offset, flags, item_size);
1852
1853	WARN_ON(!flags_ret);
1854	if (flags_ret) {
1855		if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)
1856			*flags_ret = BTRFS_EXTENT_FLAG_TREE_BLOCK;
1857		else if (flags & BTRFS_EXTENT_FLAG_DATA)
1858			*flags_ret = BTRFS_EXTENT_FLAG_DATA;
1859		else
1860			BUG_ON(1);
1861		return 0;
1862	}
1863
1864	return -EIO;
1865}
1866
1867/*
1868 * helper function to iterate extent inline refs. ptr must point to a 0 value
1869 * for the first call and may be modified. it is used to track state.
1870 * if more refs exist, 0 is returned and the next call to
1871 * __get_extent_inline_ref must pass the modified ptr parameter to get the
1872 * next ref. after the last ref was processed, 1 is returned.
1873 * returns <0 on error
1874 */
1875static int __get_extent_inline_ref(unsigned long *ptr, struct extent_buffer *eb,
1876				   struct btrfs_key *key,
1877				   struct btrfs_extent_item *ei, u32 item_size,
1878				   struct btrfs_extent_inline_ref **out_eiref,
1879				   int *out_type)
1880{
1881	unsigned long end;
1882	u64 flags;
1883	struct btrfs_tree_block_info *info;
1884
1885	if (!*ptr) {
1886		/* first call */
1887		flags = btrfs_extent_flags(eb, ei);
1888		if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
1889			if (key->type == BTRFS_METADATA_ITEM_KEY) {
1890				/* a skinny metadata extent */
1891				*out_eiref =
1892				     (struct btrfs_extent_inline_ref *)(ei + 1);
1893			} else {
1894				WARN_ON(key->type != BTRFS_EXTENT_ITEM_KEY);
1895				info = (struct btrfs_tree_block_info *)(ei + 1);
1896				*out_eiref =
1897				   (struct btrfs_extent_inline_ref *)(info + 1);
1898			}
1899		} else {
1900			*out_eiref = (struct btrfs_extent_inline_ref *)(ei + 1);
1901		}
1902		*ptr = (unsigned long)*out_eiref;
1903		if ((unsigned long)(*ptr) >= (unsigned long)ei + item_size)
1904			return -ENOENT;
1905	}
1906
1907	end = (unsigned long)ei + item_size;
1908	*out_eiref = (struct btrfs_extent_inline_ref *)(*ptr);
1909	*out_type = btrfs_extent_inline_ref_type(eb, *out_eiref);
1910
1911	*ptr += btrfs_extent_inline_ref_size(*out_type);
1912	WARN_ON(*ptr > end);
1913	if (*ptr == end)
1914		return 1; /* last */
1915
1916	return 0;
1917}
1918
1919/*
1920 * reads the tree block backref for an extent. tree level and root are returned
1921 * through out_level and out_root. ptr must point to a 0 value for the first
1922 * call and may be modified (see __get_extent_inline_ref comment).
1923 * returns 0 if data was provided, 1 if there was no more data to provide or
1924 * <0 on error.
1925 */
1926int tree_backref_for_extent(unsigned long *ptr, struct extent_buffer *eb,
1927			    struct btrfs_key *key, struct btrfs_extent_item *ei,
1928			    u32 item_size, u64 *out_root, u8 *out_level)
1929{
1930	int ret;
1931	int type;
1932	struct btrfs_extent_inline_ref *eiref;
1933
1934	if (*ptr == (unsigned long)-1)
1935		return 1;
1936
1937	while (1) {
1938		ret = __get_extent_inline_ref(ptr, eb, key, ei, item_size,
1939					      &eiref, &type);
1940		if (ret < 0)
1941			return ret;
1942
1943		if (type == BTRFS_TREE_BLOCK_REF_KEY ||
1944		    type == BTRFS_SHARED_BLOCK_REF_KEY)
1945			break;
1946
1947		if (ret == 1)
1948			return 1;
1949	}
1950
1951	/* we can treat both ref types equally here */
1952	*out_root = btrfs_extent_inline_ref_offset(eb, eiref);
1953
1954	if (key->type == BTRFS_EXTENT_ITEM_KEY) {
1955		struct btrfs_tree_block_info *info;
1956
1957		info = (struct btrfs_tree_block_info *)(ei + 1);
1958		*out_level = btrfs_tree_block_level(eb, info);
1959	} else {
1960		ASSERT(key->type == BTRFS_METADATA_ITEM_KEY);
1961		*out_level = (u8)key->offset;
1962	}
1963
1964	if (ret == 1)
1965		*ptr = (unsigned long)-1;
1966
1967	return 0;
1968}
1969
1970static int iterate_leaf_refs(struct btrfs_fs_info *fs_info,
1971			     struct extent_inode_elem *inode_list,
1972			     u64 root, u64 extent_item_objectid,
1973			     iterate_extent_inodes_t *iterate, void *ctx)
1974{
1975	struct extent_inode_elem *eie;
1976	int ret = 0;
1977
1978	for (eie = inode_list; eie; eie = eie->next) {
1979		btrfs_debug(fs_info,
1980			    "ref for %llu resolved, key (%llu EXTEND_DATA %llu), root %llu",
1981			    extent_item_objectid, eie->inum,
1982			    eie->offset, root);
1983		ret = iterate(eie->inum, eie->offset, root, ctx);
1984		if (ret) {
1985			btrfs_debug(fs_info,
1986				    "stopping iteration for %llu due to ret=%d",
1987				    extent_item_objectid, ret);
1988			break;
1989		}
1990	}
1991
1992	return ret;
1993}
1994
1995/*
1996 * calls iterate() for every inode that references the extent identified by
1997 * the given parameters.
1998 * when the iterator function returns a non-zero value, iteration stops.
1999 */
2000int iterate_extent_inodes(struct btrfs_fs_info *fs_info,
2001				u64 extent_item_objectid, u64 extent_item_pos,
2002				int search_commit_root,
2003				iterate_extent_inodes_t *iterate, void *ctx)
2004{
2005	int ret;
2006	struct btrfs_trans_handle *trans = NULL;
2007	struct ulist *refs = NULL;
2008	struct ulist *roots = NULL;
2009	struct ulist_node *ref_node = NULL;
2010	struct ulist_node *root_node = NULL;
2011	struct seq_list tree_mod_seq_elem = SEQ_LIST_INIT(tree_mod_seq_elem);
2012	struct ulist_iterator ref_uiter;
2013	struct ulist_iterator root_uiter;
2014
2015	btrfs_debug(fs_info, "resolving all inodes for extent %llu",
2016			extent_item_objectid);
2017
2018	if (!search_commit_root) {
2019		trans = btrfs_join_transaction(fs_info->extent_root);
2020		if (IS_ERR(trans))
2021			return PTR_ERR(trans);
2022		btrfs_get_tree_mod_seq(fs_info, &tree_mod_seq_elem);
2023	} else {
2024		down_read(&fs_info->commit_root_sem);
2025	}
2026
2027	ret = btrfs_find_all_leafs(trans, fs_info, extent_item_objectid,
2028				   tree_mod_seq_elem.seq, &refs,
2029				   &extent_item_pos);
2030	if (ret)
2031		goto out;
2032
2033	ULIST_ITER_INIT(&ref_uiter);
2034	while (!ret && (ref_node = ulist_next(refs, &ref_uiter))) {
2035		ret = __btrfs_find_all_roots(trans, fs_info, ref_node->val,
2036					     tree_mod_seq_elem.seq, &roots);
2037		if (ret)
2038			break;
2039		ULIST_ITER_INIT(&root_uiter);
2040		while (!ret && (root_node = ulist_next(roots, &root_uiter))) {
2041			btrfs_debug(fs_info,
2042				    "root %llu references leaf %llu, data list %#llx",
2043				    root_node->val, ref_node->val,
2044				    ref_node->aux);
2045			ret = iterate_leaf_refs(fs_info,
2046						(struct extent_inode_elem *)
2047						(uintptr_t)ref_node->aux,
2048						root_node->val,
2049						extent_item_objectid,
2050						iterate, ctx);
2051		}
2052		ulist_free(roots);
2053	}
2054
2055	free_leaf_list(refs);
2056out:
2057	if (!search_commit_root) {
2058		btrfs_put_tree_mod_seq(fs_info, &tree_mod_seq_elem);
2059		btrfs_end_transaction(trans);
2060	} else {
2061		up_read(&fs_info->commit_root_sem);
2062	}
2063
2064	return ret;
2065}
2066
2067int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info,
2068				struct btrfs_path *path,
2069				iterate_extent_inodes_t *iterate, void *ctx)
2070{
2071	int ret;
2072	u64 extent_item_pos;
2073	u64 flags = 0;
2074	struct btrfs_key found_key;
2075	int search_commit_root = path->search_commit_root;
2076
2077	ret = extent_from_logical(fs_info, logical, path, &found_key, &flags);
2078	btrfs_release_path(path);
2079	if (ret < 0)
2080		return ret;
2081	if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)
2082		return -EINVAL;
2083
2084	extent_item_pos = logical - found_key.objectid;
2085	ret = iterate_extent_inodes(fs_info, found_key.objectid,
2086					extent_item_pos, search_commit_root,
2087					iterate, ctx);
2088
2089	return ret;
2090}
2091
2092typedef int (iterate_irefs_t)(u64 parent, u32 name_len, unsigned long name_off,
2093			      struct extent_buffer *eb, void *ctx);
2094
2095static int iterate_inode_refs(u64 inum, struct btrfs_root *fs_root,
2096			      struct btrfs_path *path,
2097			      iterate_irefs_t *iterate, void *ctx)
2098{
2099	int ret = 0;
2100	int slot;
2101	u32 cur;
2102	u32 len;
2103	u32 name_len;
2104	u64 parent = 0;
2105	int found = 0;
2106	struct extent_buffer *eb;
2107	struct btrfs_item *item;
2108	struct btrfs_inode_ref *iref;
2109	struct btrfs_key found_key;
2110
2111	while (!ret) {
2112		ret = btrfs_find_item(fs_root, path, inum,
2113				parent ? parent + 1 : 0, BTRFS_INODE_REF_KEY,
2114				&found_key);
2115
2116		if (ret < 0)
2117			break;
2118		if (ret) {
2119			ret = found ? 0 : -ENOENT;
2120			break;
2121		}
2122		++found;
2123
2124		parent = found_key.offset;
2125		slot = path->slots[0];
2126		eb = btrfs_clone_extent_buffer(path->nodes[0]);
2127		if (!eb) {
2128			ret = -ENOMEM;
2129			break;
2130		}
2131		extent_buffer_get(eb);
2132		btrfs_tree_read_lock(eb);
2133		btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
2134		btrfs_release_path(path);
2135
2136		item = btrfs_item_nr(slot);
2137		iref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
2138
2139		for (cur = 0; cur < btrfs_item_size(eb, item); cur += len) {
2140			name_len = btrfs_inode_ref_name_len(eb, iref);
2141			/* path must be released before calling iterate()! */
2142			btrfs_debug(fs_root->fs_info,
2143				"following ref at offset %u for inode %llu in tree %llu",
2144				cur, found_key.objectid, fs_root->objectid);
2145			ret = iterate(parent, name_len,
2146				      (unsigned long)(iref + 1), eb, ctx);
2147			if (ret)
2148				break;
2149			len = sizeof(*iref) + name_len;
2150			iref = (struct btrfs_inode_ref *)((char *)iref + len);
2151		}
2152		btrfs_tree_read_unlock_blocking(eb);
2153		free_extent_buffer(eb);
2154	}
2155
2156	btrfs_release_path(path);
2157
2158	return ret;
2159}
2160
2161static int iterate_inode_extrefs(u64 inum, struct btrfs_root *fs_root,
2162				 struct btrfs_path *path,
2163				 iterate_irefs_t *iterate, void *ctx)
2164{
2165	int ret;
2166	int slot;
2167	u64 offset = 0;
2168	u64 parent;
2169	int found = 0;
2170	struct extent_buffer *eb;
2171	struct btrfs_inode_extref *extref;
2172	u32 item_size;
2173	u32 cur_offset;
2174	unsigned long ptr;
2175
2176	while (1) {
2177		ret = btrfs_find_one_extref(fs_root, inum, offset, path, &extref,
2178					    &offset);
2179		if (ret < 0)
2180			break;
2181		if (ret) {
2182			ret = found ? 0 : -ENOENT;
2183			break;
2184		}
2185		++found;
2186
2187		slot = path->slots[0];
2188		eb = btrfs_clone_extent_buffer(path->nodes[0]);
2189		if (!eb) {
2190			ret = -ENOMEM;
2191			break;
2192		}
2193		extent_buffer_get(eb);
2194
2195		btrfs_tree_read_lock(eb);
2196		btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
2197		btrfs_release_path(path);
2198
2199		item_size = btrfs_item_size_nr(eb, slot);
2200		ptr = btrfs_item_ptr_offset(eb, slot);
2201		cur_offset = 0;
2202
2203		while (cur_offset < item_size) {
2204			u32 name_len;
2205
2206			extref = (struct btrfs_inode_extref *)(ptr + cur_offset);
2207			parent = btrfs_inode_extref_parent(eb, extref);
2208			name_len = btrfs_inode_extref_name_len(eb, extref);
2209			ret = iterate(parent, name_len,
2210				      (unsigned long)&extref->name, eb, ctx);
2211			if (ret)
2212				break;
2213
2214			cur_offset += btrfs_inode_extref_name_len(eb, extref);
2215			cur_offset += sizeof(*extref);
2216		}
2217		btrfs_tree_read_unlock_blocking(eb);
2218		free_extent_buffer(eb);
2219
2220		offset++;
2221	}
2222
2223	btrfs_release_path(path);
2224
2225	return ret;
2226}
2227
2228static int iterate_irefs(u64 inum, struct btrfs_root *fs_root,
2229			 struct btrfs_path *path, iterate_irefs_t *iterate,
2230			 void *ctx)
2231{
2232	int ret;
2233	int found_refs = 0;
2234
2235	ret = iterate_inode_refs(inum, fs_root, path, iterate, ctx);
2236	if (!ret)
2237		++found_refs;
2238	else if (ret != -ENOENT)
2239		return ret;
2240
2241	ret = iterate_inode_extrefs(inum, fs_root, path, iterate, ctx);
2242	if (ret == -ENOENT && found_refs)
2243		return 0;
2244
2245	return ret;
2246}
2247
2248/*
2249 * returns 0 if the path could be dumped (probably truncated)
2250 * returns <0 in case of an error
2251 */
2252static int inode_to_path(u64 inum, u32 name_len, unsigned long name_off,
2253			 struct extent_buffer *eb, void *ctx)
2254{
2255	struct inode_fs_paths *ipath = ctx;
2256	char *fspath;
2257	char *fspath_min;
2258	int i = ipath->fspath->elem_cnt;
2259	const int s_ptr = sizeof(char *);
2260	u32 bytes_left;
2261
2262	bytes_left = ipath->fspath->bytes_left > s_ptr ?
2263					ipath->fspath->bytes_left - s_ptr : 0;
2264
2265	fspath_min = (char *)ipath->fspath->val + (i + 1) * s_ptr;
2266	fspath = btrfs_ref_to_path(ipath->fs_root, ipath->btrfs_path, name_len,
2267				   name_off, eb, inum, fspath_min, bytes_left);
2268	if (IS_ERR(fspath))
2269		return PTR_ERR(fspath);
2270
2271	if (fspath > fspath_min) {
2272		ipath->fspath->val[i] = (u64)(unsigned long)fspath;
2273		++ipath->fspath->elem_cnt;
2274		ipath->fspath->bytes_left = fspath - fspath_min;
2275	} else {
2276		++ipath->fspath->elem_missed;
2277		ipath->fspath->bytes_missing += fspath_min - fspath;
2278		ipath->fspath->bytes_left = 0;
2279	}
2280
2281	return 0;
2282}
2283
2284/*
2285 * this dumps all file system paths to the inode into the ipath struct, provided
2286 * is has been created large enough. each path is zero-terminated and accessed
2287 * from ipath->fspath->val[i].
2288 * when it returns, there are ipath->fspath->elem_cnt number of paths available
2289 * in ipath->fspath->val[]. when the allocated space wasn't sufficient, the
2290 * number of missed paths is recorded in ipath->fspath->elem_missed, otherwise,
2291 * it's zero. ipath->fspath->bytes_missing holds the number of bytes that would
2292 * have been needed to return all paths.
2293 */
2294int paths_from_inode(u64 inum, struct inode_fs_paths *ipath)
2295{
2296	return iterate_irefs(inum, ipath->fs_root, ipath->btrfs_path,
2297			     inode_to_path, ipath);
2298}
2299
2300struct btrfs_data_container *init_data_container(u32 total_bytes)
2301{
2302	struct btrfs_data_container *data;
2303	size_t alloc_bytes;
2304
2305	alloc_bytes = max_t(size_t, total_bytes, sizeof(*data));
2306	data = vmalloc(alloc_bytes);
2307	if (!data)
2308		return ERR_PTR(-ENOMEM);
2309
2310	if (total_bytes >= sizeof(*data)) {
2311		data->bytes_left = total_bytes - sizeof(*data);
2312		data->bytes_missing = 0;
2313	} else {
2314		data->bytes_missing = sizeof(*data) - total_bytes;
2315		data->bytes_left = 0;
2316	}
2317
2318	data->elem_cnt = 0;
2319	data->elem_missed = 0;
2320
2321	return data;
2322}
2323
2324/*
2325 * allocates space to return multiple file system paths for an inode.
2326 * total_bytes to allocate are passed, note that space usable for actual path
2327 * information will be total_bytes - sizeof(struct inode_fs_paths).
2328 * the returned pointer must be freed with free_ipath() in the end.
2329 */
2330struct inode_fs_paths *init_ipath(s32 total_bytes, struct btrfs_root *fs_root,
2331					struct btrfs_path *path)
2332{
2333	struct inode_fs_paths *ifp;
2334	struct btrfs_data_container *fspath;
2335
2336	fspath = init_data_container(total_bytes);
2337	if (IS_ERR(fspath))
2338		return (void *)fspath;
2339
2340	ifp = kmalloc(sizeof(*ifp), GFP_NOFS);
2341	if (!ifp) {
2342		vfree(fspath);
2343		return ERR_PTR(-ENOMEM);
2344	}
2345
2346	ifp->btrfs_path = path;
2347	ifp->fspath = fspath;
2348	ifp->fs_root = fs_root;
2349
2350	return ifp;
2351}
2352
2353void free_ipath(struct inode_fs_paths *ipath)
2354{
2355	if (!ipath)
2356		return;
2357	vfree(ipath->fspath);
2358	kfree(ipath);
2359}