backref.c 60.1 KB
Newer Older
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
/*
 * Copyright (C) 2011 STRATO.  All rights reserved.
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public
 * License v2 as published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public
 * License along with this program; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
 * Boston, MA 021110-1307, USA.
 */

19
#include <linux/vmalloc.h>
20
#include <linux/rbtree.h>
21 22 23
#include "ctree.h"
#include "disk-io.h"
#include "backref.h"
24 25 26
#include "ulist.h"
#include "transaction.h"
#include "delayed-ref.h"
27
#include "locking.h"
28

29 30 31 32 33
enum merge_mode {
	MERGE_IDENTICAL_KEYS = 1,
	MERGE_IDENTICAL_PARENTS,
};

34 35 36
/* Just an arbitrary number so we can be sure this happened */
#define BACKREF_FOUND_SHARED 6

37 38 39 40 41 42
struct extent_inode_elem {
	u64 inum;
	u64 offset;
	struct extent_inode_elem *next;
};

43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301
/*
 * ref_root is used as the root of the ref tree that hold a collection
 * of unique references.
 */
struct ref_root {
	struct rb_root rb_root;

	/*
	 * The unique_refs represents the number of ref_nodes with a positive
	 * count stored in the tree. Even if a ref_node (the count is greater
	 * than one) is added, the unique_refs will only increase by one.
	 */
	unsigned int unique_refs;
};

/* ref_node is used to store a unique reference to the ref tree. */
struct ref_node {
	struct rb_node rb_node;

	/* For NORMAL_REF, otherwise all these fields should be set to 0 */
	u64 root_id;
	u64 object_id;
	u64 offset;

	/* For SHARED_REF, otherwise parent field should be set to 0 */
	u64 parent;

	/* Ref to the ref_mod of btrfs_delayed_ref_node */
	int ref_mod;
};

/* Dynamically allocate and initialize a ref_root */
static struct ref_root *ref_root_alloc(void)
{
	struct ref_root *ref_tree;

	ref_tree = kmalloc(sizeof(*ref_tree), GFP_NOFS);
	if (!ref_tree)
		return NULL;

	ref_tree->rb_root = RB_ROOT;
	ref_tree->unique_refs = 0;

	return ref_tree;
}

/* Free all nodes in the ref tree, and reinit ref_root */
static void ref_root_fini(struct ref_root *ref_tree)
{
	struct ref_node *node;
	struct rb_node *next;

	while ((next = rb_first(&ref_tree->rb_root)) != NULL) {
		node = rb_entry(next, struct ref_node, rb_node);
		rb_erase(next, &ref_tree->rb_root);
		kfree(node);
	}

	ref_tree->rb_root = RB_ROOT;
	ref_tree->unique_refs = 0;
}

static void ref_root_free(struct ref_root *ref_tree)
{
	if (!ref_tree)
		return;

	ref_root_fini(ref_tree);
	kfree(ref_tree);
}

/*
 * Compare ref_node with (root_id, object_id, offset, parent)
 *
 * The function compares two ref_node a and b. It returns an integer less
 * than, equal to, or greater than zero , respectively, to be less than, to
 * equal, or be greater than b.
 */
static int ref_node_cmp(struct ref_node *a, struct ref_node *b)
{
	if (a->root_id < b->root_id)
		return -1;
	else if (a->root_id > b->root_id)
		return 1;

	if (a->object_id < b->object_id)
		return -1;
	else if (a->object_id > b->object_id)
		return 1;

	if (a->offset < b->offset)
		return -1;
	else if (a->offset > b->offset)
		return 1;

	if (a->parent < b->parent)
		return -1;
	else if (a->parent > b->parent)
		return 1;

	return 0;
}

/*
 * Search ref_node with (root_id, object_id, offset, parent) in the tree
 *
 * if found, the pointer of the ref_node will be returned;
 * if not found, NULL will be returned and pos will point to the rb_node for
 * insert, pos_parent will point to pos'parent for insert;
*/
static struct ref_node *__ref_tree_search(struct ref_root *ref_tree,
					  struct rb_node ***pos,
					  struct rb_node **pos_parent,
					  u64 root_id, u64 object_id,
					  u64 offset, u64 parent)
{
	struct ref_node *cur = NULL;
	struct ref_node entry;
	int ret;

	entry.root_id = root_id;
	entry.object_id = object_id;
	entry.offset = offset;
	entry.parent = parent;

	*pos = &ref_tree->rb_root.rb_node;

	while (**pos) {
		*pos_parent = **pos;
		cur = rb_entry(*pos_parent, struct ref_node, rb_node);

		ret = ref_node_cmp(cur, &entry);
		if (ret > 0)
			*pos = &(**pos)->rb_left;
		else if (ret < 0)
			*pos = &(**pos)->rb_right;
		else
			return cur;
	}

	return NULL;
}

/*
 * Insert a ref_node to the ref tree
 * @pos used for specifiy the position to insert
 * @pos_parent for specifiy pos's parent
 *
 * success, return 0;
 * ref_node already exists, return -EEXIST;
*/
static int ref_tree_insert(struct ref_root *ref_tree, struct rb_node **pos,
			   struct rb_node *pos_parent, struct ref_node *ins)
{
	struct rb_node **p = NULL;
	struct rb_node *parent = NULL;
	struct ref_node *cur = NULL;

	if (!pos) {
		cur = __ref_tree_search(ref_tree, &p, &parent, ins->root_id,
					ins->object_id, ins->offset,
					ins->parent);
		if (cur)
			return -EEXIST;
	} else {
		p = pos;
		parent = pos_parent;
	}

	rb_link_node(&ins->rb_node, parent, p);
	rb_insert_color(&ins->rb_node, &ref_tree->rb_root);

	return 0;
}

/* Erase and free ref_node, caller should update ref_root->unique_refs */
static void ref_tree_remove(struct ref_root *ref_tree, struct ref_node *node)
{
	rb_erase(&node->rb_node, &ref_tree->rb_root);
	kfree(node);
}

/*
 * Update ref_root->unique_refs
 *
 * Call __ref_tree_search
 *	1. if ref_node doesn't exist, ref_tree_insert this node, and update
 *	ref_root->unique_refs:
 *		if ref_node->ref_mod > 0, ref_root->unique_refs++;
 *		if ref_node->ref_mod < 0, do noting;
 *
 *	2. if ref_node is found, then get origin ref_node->ref_mod, and update
 *	ref_node->ref_mod.
 *		if ref_node->ref_mod is equal to 0,then call ref_tree_remove
 *
 *		according to origin_mod and new_mod, update ref_root->items
 *		+----------------+--------------+-------------+
 *		|		 |new_count <= 0|new_count > 0|
 *		+----------------+--------------+-------------+
 *		|origin_count < 0|       0      |      1      |
 *		+----------------+--------------+-------------+
 *		|origin_count > 0|      -1      |      0      |
 *		+----------------+--------------+-------------+
 *
 * In case of allocation failure, -ENOMEM is returned and the ref_tree stays
 * unaltered.
 * Success, return 0
 */
static int ref_tree_add(struct ref_root *ref_tree, u64 root_id, u64 object_id,
			u64 offset, u64 parent, int count)
{
	struct ref_node *node = NULL;
	struct rb_node **pos = NULL;
	struct rb_node *pos_parent = NULL;
	int origin_count;
	int ret;

	if (!count)
		return 0;

	node = __ref_tree_search(ref_tree, &pos, &pos_parent, root_id,
				 object_id, offset, parent);
	if (node == NULL) {
		node = kmalloc(sizeof(*node), GFP_NOFS);
		if (!node)
			return -ENOMEM;

		node->root_id = root_id;
		node->object_id = object_id;
		node->offset = offset;
		node->parent = parent;
		node->ref_mod = count;

		ret = ref_tree_insert(ref_tree, pos, pos_parent, node);
		ASSERT(!ret);
		if (ret) {
			kfree(node);
			return ret;
		}

		ref_tree->unique_refs += node->ref_mod > 0 ? 1 : 0;

		return 0;
	}

	origin_count = node->ref_mod;
	node->ref_mod += count;

	if (node->ref_mod > 0)
		ref_tree->unique_refs += origin_count > 0 ? 0 : 1;
	else if (node->ref_mod <= 0)
		ref_tree->unique_refs += origin_count > 0 ? -1 : 0;

	if (!node->ref_mod)
		ref_tree_remove(ref_tree, node);

	return 0;
}

302 303 304 305 306
static int check_extent_in_eb(struct btrfs_key *key, struct extent_buffer *eb,
				struct btrfs_file_extent_item *fi,
				u64 extent_item_pos,
				struct extent_inode_elem **eie)
{
307
	u64 offset = 0;
308 309
	struct extent_inode_elem *e;

310 311 312 313 314
	if (!btrfs_file_extent_compression(eb, fi) &&
	    !btrfs_file_extent_encryption(eb, fi) &&
	    !btrfs_file_extent_other_encoding(eb, fi)) {
		u64 data_offset;
		u64 data_len;
315

316 317 318 319 320 321 322 323
		data_offset = btrfs_file_extent_offset(eb, fi);
		data_len = btrfs_file_extent_num_bytes(eb, fi);

		if (extent_item_pos < data_offset ||
		    extent_item_pos >= data_offset + data_len)
			return 1;
		offset = extent_item_pos - data_offset;
	}
324 325 326 327 328 329 330

	e = kmalloc(sizeof(*e), GFP_NOFS);
	if (!e)
		return -ENOMEM;

	e->next = *eie;
	e->inum = key->objectid;
331
	e->offset = key->offset + offset;
332 333 334 335 336
	*eie = e;

	return 0;
}

337 338 339 340 341 342 343 344 345 346
static void free_inode_elem_list(struct extent_inode_elem *eie)
{
	struct extent_inode_elem *eie_next;

	for (; eie; eie = eie_next) {
		eie_next = eie->next;
		kfree(eie);
	}
}

347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385
static int find_extent_in_eb(struct extent_buffer *eb, u64 wanted_disk_byte,
				u64 extent_item_pos,
				struct extent_inode_elem **eie)
{
	u64 disk_byte;
	struct btrfs_key key;
	struct btrfs_file_extent_item *fi;
	int slot;
	int nritems;
	int extent_type;
	int ret;

	/*
	 * from the shared data ref, we only have the leaf but we need
	 * the key. thus, we must look into all items and see that we
	 * find one (some) with a reference to our extent item.
	 */
	nritems = btrfs_header_nritems(eb);
	for (slot = 0; slot < nritems; ++slot) {
		btrfs_item_key_to_cpu(eb, &key, slot);
		if (key.type != BTRFS_EXTENT_DATA_KEY)
			continue;
		fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
		extent_type = btrfs_file_extent_type(eb, fi);
		if (extent_type == BTRFS_FILE_EXTENT_INLINE)
			continue;
		/* don't skip BTRFS_FILE_EXTENT_PREALLOC, we can handle that */
		disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);
		if (disk_byte != wanted_disk_byte)
			continue;

		ret = check_extent_in_eb(&key, eb, fi, extent_item_pos, eie);
		if (ret < 0)
			return ret;
	}

	return 0;
}

386 387 388 389 390 391
/*
 * this structure records all encountered refs on the way up to the root
 */
struct __prelim_ref {
	struct list_head list;
	u64 root_id;
392
	struct btrfs_key key_for_search;
393 394
	int level;
	int count;
395
	struct extent_inode_elem *inode_list;
396 397 398 399
	u64 parent;
	u64 wanted_disk_byte;
};

400 401 402 403 404 405 406
static struct kmem_cache *btrfs_prelim_ref_cache;

int __init btrfs_prelim_ref_init(void)
{
	btrfs_prelim_ref_cache = kmem_cache_create("btrfs_prelim_ref",
					sizeof(struct __prelim_ref),
					0,
407
					SLAB_MEM_SPREAD,
408 409 410 411 412 413 414 415
					NULL);
	if (!btrfs_prelim_ref_cache)
		return -ENOMEM;
	return 0;
}

void btrfs_prelim_ref_exit(void)
{
416
	kmem_cache_destroy(btrfs_prelim_ref_cache);
417 418
}

419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457
/*
 * the rules for all callers of this function are:
 * - obtaining the parent is the goal
 * - if you add a key, you must know that it is a correct key
 * - if you cannot add the parent or a correct key, then we will look into the
 *   block later to set a correct key
 *
 * delayed refs
 * ============
 *        backref type | shared | indirect | shared | indirect
 * information         |   tree |     tree |   data |     data
 * --------------------+--------+----------+--------+----------
 *      parent logical |    y   |     -    |    -   |     -
 *      key to resolve |    -   |     y    |    y   |     y
 *  tree block logical |    -   |     -    |    -   |     -
 *  root for resolving |    y   |     y    |    y   |     y
 *
 * - column 1:       we've the parent -> done
 * - column 2, 3, 4: we use the key to find the parent
 *
 * on disk refs (inline or keyed)
 * ==============================
 *        backref type | shared | indirect | shared | indirect
 * information         |   tree |     tree |   data |     data
 * --------------------+--------+----------+--------+----------
 *      parent logical |    y   |     -    |    y   |     -
 *      key to resolve |    -   |     -    |    -   |     y
 *  tree block logical |    y   |     y    |    y   |     y
 *  root for resolving |    -   |     y    |    y   |     y
 *
 * - column 1, 3: we've the parent -> done
 * - column 2:    we take the first key from the block to find the parent
 *                (see __add_missing_keys)
 * - column 4:    we use the key to find the parent
 *
 * additional information that's available but not required to find the parent
 * block might help in merging entries to gain some speed.
 */

458
static int __add_prelim_ref(struct list_head *head, u64 root_id,
459
			    struct btrfs_key *key, int level,
460 461
			    u64 parent, u64 wanted_disk_byte, int count,
			    gfp_t gfp_mask)
462 463 464
{
	struct __prelim_ref *ref;

465 466 467
	if (root_id == BTRFS_DATA_RELOC_TREE_OBJECTID)
		return 0;

468
	ref = kmem_cache_alloc(btrfs_prelim_ref_cache, gfp_mask);
469 470 471 472
	if (!ref)
		return -ENOMEM;

	ref->root_id = root_id;
473
	if (key) {
474
		ref->key_for_search = *key;
475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497
		/*
		 * We can often find data backrefs with an offset that is too
		 * large (>= LLONG_MAX, maximum allowed file offset) due to
		 * underflows when subtracting a file's offset with the data
		 * offset of its corresponding extent data item. This can
		 * happen for example in the clone ioctl.
		 * So if we detect such case we set the search key's offset to
		 * zero to make sure we will find the matching file extent item
		 * at add_all_parents(), otherwise we will miss it because the
		 * offset taken form the backref is much larger then the offset
		 * of the file extent item. This can make us scan a very large
		 * number of file extent items, but at least it will not make
		 * us miss any.
		 * This is an ugly workaround for a behaviour that should have
		 * never existed, but it does and a fix for the clone ioctl
		 * would touch a lot of places, cause backwards incompatibility
		 * and would not fix the problem for extents cloned with older
		 * kernels.
		 */
		if (ref->key_for_search.type == BTRFS_EXTENT_DATA_KEY &&
		    ref->key_for_search.offset >= LLONG_MAX)
			ref->key_for_search.offset = 0;
	} else {
498
		memset(&ref->key_for_search, 0, sizeof(ref->key_for_search));
499
	}
500

501
	ref->inode_list = NULL;
502 503 504 505 506 507 508 509 510 511
	ref->level = level;
	ref->count = count;
	ref->parent = parent;
	ref->wanted_disk_byte = wanted_disk_byte;
	list_add_tail(&ref->list, head);

	return 0;
}

static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path,
512
			   struct ulist *parents, struct __prelim_ref *ref,
513 514
			   int level, u64 time_seq, const u64 *extent_item_pos,
			   u64 total_refs)
515
{
516 517 518 519
	int ret = 0;
	int slot;
	struct extent_buffer *eb;
	struct btrfs_key key;
520
	struct btrfs_key *key_for_search = &ref->key_for_search;
521
	struct btrfs_file_extent_item *fi;
522
	struct extent_inode_elem *eie = NULL, *old = NULL;
523
	u64 disk_byte;
524 525
	u64 wanted_disk_byte = ref->wanted_disk_byte;
	u64 count = 0;
526

527 528 529
	if (level != 0) {
		eb = path->nodes[level];
		ret = ulist_add(parents, eb->start, 0, GFP_NOFS);
530 531
		if (ret < 0)
			return ret;
532
		return 0;
533
	}
534 535

	/*
536 537 538
	 * We normally enter this function with the path already pointing to
	 * the first item to check. But sometimes, we may enter it with
	 * slot==nritems. In that case, go to the next leaf before we continue.
539
	 */
540
	if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
541
		if (time_seq == SEQ_LAST)
542 543 544 545
			ret = btrfs_next_leaf(root, path);
		else
			ret = btrfs_next_old_leaf(root, path, time_seq);
	}
546

547
	while (!ret && count < total_refs) {
548
		eb = path->nodes[0];
549 550 551 552 553 554 555 556 557 558 559 560 561
		slot = path->slots[0];

		btrfs_item_key_to_cpu(eb, &key, slot);

		if (key.objectid != key_for_search->objectid ||
		    key.type != BTRFS_EXTENT_DATA_KEY)
			break;

		fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
		disk_byte = btrfs_file_extent_disk_bytenr(eb, fi);

		if (disk_byte == wanted_disk_byte) {
			eie = NULL;
562
			old = NULL;
563
			count++;
564 565 566 567 568 569 570
			if (extent_item_pos) {
				ret = check_extent_in_eb(&key, eb, fi,
						*extent_item_pos,
						&eie);
				if (ret < 0)
					break;
			}
571 572
			if (ret > 0)
				goto next;
573 574
			ret = ulist_add_merge_ptr(parents, eb->start,
						  eie, (void **)&old, GFP_NOFS);
575 576 577 578 579 580
			if (ret < 0)
				break;
			if (!ret && extent_item_pos) {
				while (old->next)
					old = old->next;
				old->next = eie;
581
			}
582
			eie = NULL;
583
		}
584
next:
585
		if (time_seq == SEQ_LAST)
586 587 588
			ret = btrfs_next_item(root, path);
		else
			ret = btrfs_next_old_item(root, path, time_seq);
589 590
	}

591 592
	if (ret > 0)
		ret = 0;
593 594
	else if (ret < 0)
		free_inode_elem_list(eie);
595
	return ret;
596 597 598 599 600 601 602
}

/*
 * resolve an indirect backref in the form (root_id, key, level)
 * to a logical address
 */
static int __resolve_indirect_ref(struct btrfs_fs_info *fs_info,
603 604 605
				  struct btrfs_path *path, u64 time_seq,
				  struct __prelim_ref *ref,
				  struct ulist *parents,
606
				  const u64 *extent_item_pos, u64 total_refs)
607 608 609 610 611 612 613
{
	struct btrfs_root *root;
	struct btrfs_key root_key;
	struct extent_buffer *eb;
	int ret = 0;
	int root_level;
	int level = ref->level;
614
	int index;
615 616 617 618

	root_key.objectid = ref->root_id;
	root_key.type = BTRFS_ROOT_ITEM_KEY;
	root_key.offset = (u64)-1;
619 620 621

	index = srcu_read_lock(&fs_info->subvol_srcu);

622
	root = btrfs_get_fs_root(fs_info, &root_key, false);
623
	if (IS_ERR(root)) {
624
		srcu_read_unlock(&fs_info->subvol_srcu, index);
625 626 627 628
		ret = PTR_ERR(root);
		goto out;
	}

629
	if (btrfs_is_testing(fs_info)) {
J
Josef Bacik 已提交
630 631 632 633 634
		srcu_read_unlock(&fs_info->subvol_srcu, index);
		ret = -ENOENT;
		goto out;
	}

635 636
	if (path->search_commit_root)
		root_level = btrfs_header_level(root->commit_root);
637
	else if (time_seq == SEQ_LAST)
638
		root_level = btrfs_header_level(root->node);
639 640
	else
		root_level = btrfs_old_root_level(root, time_seq);
641

642 643
	if (root_level + 1 == level) {
		srcu_read_unlock(&fs_info->subvol_srcu, index);
644
		goto out;
645
	}
646 647

	path->lowest_level = level;
648
	if (time_seq == SEQ_LAST)
649 650 651 652 653
		ret = btrfs_search_slot(NULL, root, &ref->key_for_search, path,
					0, 0);
	else
		ret = btrfs_search_old_slot(root, &ref->key_for_search, path,
					    time_seq);
654 655 656 657

	/* root node has been locked, we can release @subvol_srcu safely here */
	srcu_read_unlock(&fs_info->subvol_srcu, index);

658 659
	btrfs_debug(fs_info,
		"search slot in root %llu (level %d, ref count %d) returned %d for key (%llu %u %llu)",
660 661 662
		 ref->root_id, level, ref->count, ret,
		 ref->key_for_search.objectid, ref->key_for_search.type,
		 ref->key_for_search.offset);
663 664 665 666
	if (ret < 0)
		goto out;

	eb = path->nodes[level];
667
	while (!eb) {
668
		if (WARN_ON(!level)) {
669 670 671 672 673
			ret = 1;
			goto out;
		}
		level--;
		eb = path->nodes[level];
674 675
	}

676
	ret = add_all_parents(root, path, parents, ref, level, time_seq,
677
			      extent_item_pos, total_refs);
678
out:
679 680
	path->lowest_level = 0;
	btrfs_release_path(path);
681 682 683 684 685 686 687
	return ret;
}

/*
 * resolve all indirect backrefs from the list
 */
static int __resolve_indirect_refs(struct btrfs_fs_info *fs_info,
688
				   struct btrfs_path *path, u64 time_seq,
689
				   struct list_head *head,
690 691
				   const u64 *extent_item_pos, u64 total_refs,
				   u64 root_objectid)
692 693 694 695 696 697 698 699
{
	int err;
	int ret = 0;
	struct __prelim_ref *ref;
	struct __prelim_ref *ref_safe;
	struct __prelim_ref *new_ref;
	struct ulist *parents;
	struct ulist_node *node;
J
Jan Schmidt 已提交
700
	struct ulist_iterator uiter;
701 702 703 704 705 706 707 708 709 710 711 712 713 714 715

	parents = ulist_alloc(GFP_NOFS);
	if (!parents)
		return -ENOMEM;

	/*
	 * _safe allows us to insert directly after the current item without
	 * iterating over the newly inserted items.
	 * we're also allowed to re-assign ref during iteration.
	 */
	list_for_each_entry_safe(ref, ref_safe, head, list) {
		if (ref->parent)	/* already direct */
			continue;
		if (ref->count == 0)
			continue;
716 717 718 719
		if (root_objectid && ref->root_id != root_objectid) {
			ret = BACKREF_FOUND_SHARED;
			goto out;
		}
720
		err = __resolve_indirect_ref(fs_info, path, time_seq, ref,
721 722
					     parents, extent_item_pos,
					     total_refs);
723 724 725 726 727
		/*
		 * we can only tolerate ENOENT,otherwise,we should catch error
		 * and return directly.
		 */
		if (err == -ENOENT) {
728
			continue;
729 730 731 732
		} else if (err) {
			ret = err;
			goto out;
		}
733 734

		/* we put the first parent into the ref at hand */
J
Jan Schmidt 已提交
735 736
		ULIST_ITER_INIT(&uiter);
		node = ulist_next(parents, &uiter);
737
		ref->parent = node ? node->val : 0;
738
		ref->inode_list = node ?
739
			(struct extent_inode_elem *)(uintptr_t)node->aux : NULL;
740 741

		/* additional parents require new refs being added here */
J
Jan Schmidt 已提交
742
		while ((node = ulist_next(parents, &uiter))) {
743 744
			new_ref = kmem_cache_alloc(btrfs_prelim_ref_cache,
						   GFP_NOFS);
745 746
			if (!new_ref) {
				ret = -ENOMEM;
747
				goto out;
748 749 750
			}
			memcpy(new_ref, ref, sizeof(*ref));
			new_ref->parent = node->val;
751 752
			new_ref->inode_list = (struct extent_inode_elem *)
							(uintptr_t)node->aux;
753 754 755 756
			list_add(&new_ref->list, &ref->list);
		}
		ulist_reinit(parents);
	}
757
out:
758 759 760 761
	ulist_free(parents);
	return ret;
}

762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786
static inline int ref_for_same_block(struct __prelim_ref *ref1,
				     struct __prelim_ref *ref2)
{
	if (ref1->level != ref2->level)
		return 0;
	if (ref1->root_id != ref2->root_id)
		return 0;
	if (ref1->key_for_search.type != ref2->key_for_search.type)
		return 0;
	if (ref1->key_for_search.objectid != ref2->key_for_search.objectid)
		return 0;
	if (ref1->key_for_search.offset != ref2->key_for_search.offset)
		return 0;
	if (ref1->parent != ref2->parent)
		return 0;

	return 1;
}

/*
 * read tree blocks and add keys where required.
 */
static int __add_missing_keys(struct btrfs_fs_info *fs_info,
			      struct list_head *head)
{
787
	struct __prelim_ref *ref;
788 789
	struct extent_buffer *eb;

790
	list_for_each_entry(ref, head, list) {
791 792 793 794 795
		if (ref->parent)
			continue;
		if (ref->key_for_search.type)
			continue;
		BUG_ON(!ref->wanted_disk_byte);
796
		eb = read_tree_block(fs_info, ref->wanted_disk_byte, 0);
797 798 799
		if (IS_ERR(eb)) {
			return PTR_ERR(eb);
		} else if (!extent_buffer_uptodate(eb)) {
800 801 802
			free_extent_buffer(eb);
			return -EIO;
		}
803 804 805 806 807 808 809 810 811 812 813
		btrfs_tree_read_lock(eb);
		if (btrfs_header_level(eb) == 0)
			btrfs_item_key_to_cpu(eb, &ref->key_for_search, 0);
		else
			btrfs_node_key_to_cpu(eb, &ref->key_for_search, 0);
		btrfs_tree_read_unlock(eb);
		free_extent_buffer(eb);
	}
	return 0;
}

814
/*
815
 * merge backrefs and adjust counts accordingly
816
 *
817 818 819 820
 *    FIXME: For MERGE_IDENTICAL_KEYS, if we add more keys in __add_prelim_ref
 *           then we can merge more here. Additionally, we could even add a key
 *           range for the blocks we looked into to merge even more (-> replace
 *           unresolved refs by those having a parent).
821
 */
822
static void __merge_refs(struct list_head *head, enum merge_mode mode)
823
{
824
	struct __prelim_ref *pos1;
825

826 827
	list_for_each_entry(pos1, head, list) {
		struct __prelim_ref *pos2 = pos1, *tmp;
828

829
		list_for_each_entry_safe_continue(pos2, tmp, head, list) {
830
			struct __prelim_ref *ref1 = pos1, *ref2 = pos2;
831
			struct extent_inode_elem *eie;
832

833 834
			if (!ref_for_same_block(ref1, ref2))
				continue;
835
			if (mode == MERGE_IDENTICAL_KEYS) {
836 837
				if (!ref1->parent && ref2->parent)
					swap(ref1, ref2);
838 839 840 841
			} else {
				if (ref1->parent != ref2->parent)
					continue;
			}
842 843 844 845 846 847 848 849 850 851

			eie = ref1->inode_list;
			while (eie && eie->next)
				eie = eie->next;
			if (eie)
				eie->next = ref2->inode_list;
			else
				ref1->inode_list = ref2->inode_list;
			ref1->count += ref2->count;

852
			list_del(&ref2->list);
853
			kmem_cache_free(btrfs_prelim_ref_cache, ref2);
854
			cond_resched();
855 856 857 858 859 860 861 862 863 864
		}

	}
}

/*
 * add all currently queued delayed refs from this head whose seq nr is
 * smaller or equal that seq to the list
 */
static int __add_delayed_refs(struct btrfs_delayed_ref_head *head, u64 seq,
865 866
			      struct list_head *prefs, u64 *total_refs,
			      u64 inum)
867
{
868
	struct btrfs_delayed_ref_node *node;
869
	struct btrfs_delayed_extent_op *extent_op = head->extent_op;
870 871
	struct btrfs_key key;
	struct btrfs_key op_key = {0};
872
	int sgn;
873
	int ret = 0;
874 875

	if (extent_op && extent_op->update_key)
876
		btrfs_disk_key_to_cpu(&op_key, &extent_op->key);
877

878
	spin_lock(&head->lock);
879
	list_for_each_entry(node, &head->ref_list, list) {
880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896
		if (node->seq > seq)
			continue;

		switch (node->action) {
		case BTRFS_ADD_DELAYED_EXTENT:
		case BTRFS_UPDATE_DELAYED_HEAD:
			WARN_ON(1);
			continue;
		case BTRFS_ADD_DELAYED_REF:
			sgn = 1;
			break;
		case BTRFS_DROP_DELAYED_REF:
			sgn = -1;
			break;
		default:
			BUG_ON(1);
		}
897
		*total_refs += (node->ref_mod * sgn);
898 899 900 901 902
		switch (node->type) {
		case BTRFS_TREE_BLOCK_REF_KEY: {
			struct btrfs_delayed_tree_ref *ref;

			ref = btrfs_delayed_node_to_tree_ref(node);
903
			ret = __add_prelim_ref(prefs, ref->root, &op_key,
904
					       ref->level + 1, 0, node->bytenr,
905
					       node->ref_mod * sgn, GFP_ATOMIC);
906 907 908 909 910 911
			break;
		}
		case BTRFS_SHARED_BLOCK_REF_KEY: {
			struct btrfs_delayed_tree_ref *ref;

			ref = btrfs_delayed_node_to_tree_ref(node);
L
Liu Bo 已提交
912
			ret = __add_prelim_ref(prefs, 0, NULL,
913 914
					       ref->level + 1, ref->parent,
					       node->bytenr,
915
					       node->ref_mod * sgn, GFP_ATOMIC);
916 917 918 919 920 921 922 923 924
			break;
		}
		case BTRFS_EXTENT_DATA_REF_KEY: {
			struct btrfs_delayed_data_ref *ref;
			ref = btrfs_delayed_node_to_data_ref(node);

			key.objectid = ref->objectid;
			key.type = BTRFS_EXTENT_DATA_KEY;
			key.offset = ref->offset;
925 926 927 928 929 930 931 932 933 934

			/*
			 * Found a inum that doesn't match our known inum, we
			 * know it's shared.
			 */
			if (inum && ref->objectid != inum) {
				ret = BACKREF_FOUND_SHARED;
				break;
			}

935 936
			ret = __add_prelim_ref(prefs, ref->root, &key, 0, 0,
					       node->bytenr,
937
					       node->ref_mod * sgn, GFP_ATOMIC);
938 939 940 941 942 943
			break;
		}
		case BTRFS_SHARED_DATA_REF_KEY: {
			struct btrfs_delayed_data_ref *ref;

			ref = btrfs_delayed_node_to_data_ref(node);
L
Liu Bo 已提交
944
			ret = __add_prelim_ref(prefs, 0, NULL, 0,
945
					       ref->parent, node->bytenr,
946
					       node->ref_mod * sgn, GFP_ATOMIC);
947 948 949 950 951
			break;
		}
		default:
			WARN_ON(1);
		}
952
		if (ret)
953
			break;
954
	}
955 956
	spin_unlock(&head->lock);
	return ret;
957 958 959 960 961
}

/*
 * add all inline backrefs for bytenr to the list
 */
962
static int __add_inline_refs(struct btrfs_path *path, u64 bytenr,
963
			     int *info_level, struct list_head *prefs,
964
			     struct ref_root *ref_tree,
965
			     u64 *total_refs, u64 inum)
966
{
967
	int ret = 0;
968 969 970
	int slot;
	struct extent_buffer *leaf;
	struct btrfs_key key;
971
	struct btrfs_key found_key;
972 973 974 975 976 977 978 979 980 981
	unsigned long ptr;
	unsigned long end;
	struct btrfs_extent_item *ei;
	u64 flags;
	u64 item_size;

	/*
	 * enumerate all inline refs
	 */
	leaf = path->nodes[0];
982
	slot = path->slots[0];
983 984 985 986 987 988

	item_size = btrfs_item_size_nr(leaf, slot);
	BUG_ON(item_size < sizeof(*ei));

	ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
	flags = btrfs_extent_flags(leaf, ei);
989
	*total_refs += btrfs_extent_refs(leaf, ei);
990
	btrfs_item_key_to_cpu(leaf, &found_key, slot);
991 992 993 994

	ptr = (unsigned long)(ei + 1);
	end = (unsigned long)ei + item_size;

995 996
	if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
	    flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
997 998 999 1000 1001 1002
		struct btrfs_tree_block_info *info;

		info = (struct btrfs_tree_block_info *)ptr;
		*info_level = btrfs_tree_block_level(leaf, info);
		ptr += sizeof(struct btrfs_tree_block_info);
		BUG_ON(ptr > end);
1003 1004
	} else if (found_key.type == BTRFS_METADATA_ITEM_KEY) {
		*info_level = found_key.offset;
1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019
	} else {
		BUG_ON(!(flags & BTRFS_EXTENT_FLAG_DATA));
	}

	while (ptr < end) {
		struct btrfs_extent_inline_ref *iref;
		u64 offset;
		int type;

		iref = (struct btrfs_extent_inline_ref *)ptr;
		type = btrfs_extent_inline_ref_type(leaf, iref);
		offset = btrfs_extent_inline_ref_offset(leaf, iref);

		switch (type) {
		case BTRFS_SHARED_BLOCK_REF_KEY:
1020
			ret = __add_prelim_ref(prefs, 0, NULL,
1021
						*info_level + 1, offset,
1022
						bytenr, 1, GFP_NOFS);
1023 1024 1025 1026 1027 1028 1029 1030
			break;
		case BTRFS_SHARED_DATA_REF_KEY: {
			struct btrfs_shared_data_ref *sdref;
			int count;

			sdref = (struct btrfs_shared_data_ref *)(iref + 1);
			count = btrfs_shared_data_ref_count(leaf, sdref);
			ret = __add_prelim_ref(prefs, 0, NULL, 0, offset,
1031
					       bytenr, count, GFP_NOFS);
1032 1033 1034 1035 1036 1037 1038
			if (ref_tree) {
				if (!ret)
					ret = ref_tree_add(ref_tree, 0, 0, 0,
							   bytenr, count);
				if (!ret && ref_tree->unique_refs > 1)
					ret = BACKREF_FOUND_SHARED;
			}
1039 1040 1041
			break;
		}
		case BTRFS_TREE_BLOCK_REF_KEY:
1042 1043
			ret = __add_prelim_ref(prefs, offset, NULL,
					       *info_level + 1, 0,
1044
					       bytenr, 1, GFP_NOFS);
1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056
			break;
		case BTRFS_EXTENT_DATA_REF_KEY: {
			struct btrfs_extent_data_ref *dref;
			int count;
			u64 root;

			dref = (struct btrfs_extent_data_ref *)(&iref->offset);
			count = btrfs_extent_data_ref_count(leaf, dref);
			key.objectid = btrfs_extent_data_ref_objectid(leaf,
								      dref);
			key.type = BTRFS_EXTENT_DATA_KEY;
			key.offset = btrfs_extent_data_ref_offset(leaf, dref);
1057 1058 1059 1060 1061 1062

			if (inum && key.objectid != inum) {
				ret = BACKREF_FOUND_SHARED;
				break;
			}

1063
			root = btrfs_extent_data_ref_root(leaf, dref);
1064
			ret = __add_prelim_ref(prefs, root, &key, 0, 0,
1065
					       bytenr, count, GFP_NOFS);
1066 1067 1068 1069 1070 1071 1072 1073 1074
			if (ref_tree) {
				if (!ret)
					ret = ref_tree_add(ref_tree, root,
							   key.objectid,
							   key.offset, 0,
							   count);
				if (!ret && ref_tree->unique_refs > 1)
					ret = BACKREF_FOUND_SHARED;
			}
1075 1076 1077 1078 1079
			break;
		}
		default:
			WARN_ON(1);
		}
1080 1081
		if (ret)
			return ret;
1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092
		ptr += btrfs_extent_inline_ref_size(type);
	}

	return 0;
}

/*
 * add all non-inline backrefs for bytenr to the list
 */
static int __add_keyed_refs(struct btrfs_fs_info *fs_info,
			    struct btrfs_path *path, u64 bytenr,
1093 1094
			    int info_level, struct list_head *prefs,
			    struct ref_root *ref_tree, u64 inum)
1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123
{
	struct btrfs_root *extent_root = fs_info->extent_root;
	int ret;
	int slot;
	struct extent_buffer *leaf;
	struct btrfs_key key;

	while (1) {
		ret = btrfs_next_item(extent_root, path);
		if (ret < 0)
			break;
		if (ret) {
			ret = 0;
			break;
		}

		slot = path->slots[0];
		leaf = path->nodes[0];
		btrfs_item_key_to_cpu(leaf, &key, slot);

		if (key.objectid != bytenr)
			break;
		if (key.type < BTRFS_TREE_BLOCK_REF_KEY)
			continue;
		if (key.type > BTRFS_SHARED_DATA_REF_KEY)
			break;

		switch (key.type) {
		case BTRFS_SHARED_BLOCK_REF_KEY:
1124
			ret = __add_prelim_ref(prefs, 0, NULL,
1125
						info_level + 1, key.offset,
1126
						bytenr, 1, GFP_NOFS);
1127 1128 1129 1130 1131 1132 1133 1134 1135
			break;
		case BTRFS_SHARED_DATA_REF_KEY: {
			struct btrfs_shared_data_ref *sdref;
			int count;

			sdref = btrfs_item_ptr(leaf, slot,
					      struct btrfs_shared_data_ref);
			count = btrfs_shared_data_ref_count(leaf, sdref);
			ret = __add_prelim_ref(prefs, 0, NULL, 0, key.offset,
1136
						bytenr, count, GFP_NOFS);
1137 1138 1139 1140 1141 1142 1143
			if (ref_tree) {
				if (!ret)
					ret = ref_tree_add(ref_tree, 0, 0, 0,
							   bytenr, count);
				if (!ret && ref_tree->unique_refs > 1)
					ret = BACKREF_FOUND_SHARED;
			}
1144 1145 1146
			break;
		}
		case BTRFS_TREE_BLOCK_REF_KEY:
1147 1148
			ret = __add_prelim_ref(prefs, key.offset, NULL,
					       info_level + 1, 0,
1149
					       bytenr, 1, GFP_NOFS);
1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162
			break;
		case BTRFS_EXTENT_DATA_REF_KEY: {
			struct btrfs_extent_data_ref *dref;
			int count;
			u64 root;

			dref = btrfs_item_ptr(leaf, slot,
					      struct btrfs_extent_data_ref);
			count = btrfs_extent_data_ref_count(leaf, dref);
			key.objectid = btrfs_extent_data_ref_objectid(leaf,
								      dref);
			key.type = BTRFS_EXTENT_DATA_KEY;
			key.offset = btrfs_extent_data_ref_offset(leaf, dref);
1163 1164 1165 1166 1167 1168

			if (inum && key.objectid != inum) {
				ret = BACKREF_FOUND_SHARED;
				break;
			}

1169 1170
			root = btrfs_extent_data_ref_root(leaf, dref);
			ret = __add_prelim_ref(prefs, root, &key, 0, 0,
1171
					       bytenr, count, GFP_NOFS);
1172 1173 1174 1175 1176 1177 1178 1179 1180
			if (ref_tree) {
				if (!ret)
					ret = ref_tree_add(ref_tree, root,
							   key.objectid,
							   key.offset, 0,
							   count);
				if (!ret && ref_tree->unique_refs > 1)
					ret = BACKREF_FOUND_SHARED;
			}
1181 1182 1183 1184 1185
			break;
		}
		default:
			WARN_ON(1);
		}
1186 1187 1188
		if (ret)
			return ret;

1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199
	}

	return ret;
}

/*
 * this adds all existing backrefs (inline backrefs, backrefs and delayed
 * refs) for the given bytenr to the refs list, merges duplicates and resolves
 * indirect refs to their parent bytenr.
 * When roots are found, they're added to the roots list
 *
1200 1201
 * NOTE: This can return values > 0
 *
1202
 * If time_seq is set to SEQ_LAST, it will not search delayed_refs, and behave
1203 1204 1205 1206
 * much like trans == NULL case, the difference only lies in it will not
 * commit root.
 * The special case is for qgroup to search roots in commit_transaction().
 *
1207 1208 1209
 * If check_shared is set to 1, any extent has more than one ref item, will
 * be returned BACKREF_FOUND_SHARED immediately.
 *
1210 1211 1212 1213
 * FIXME some caching might speed things up
 */
static int find_parent_nodes(struct btrfs_trans_handle *trans,
			     struct btrfs_fs_info *fs_info, u64 bytenr,
1214
			     u64 time_seq, struct ulist *refs,
1215
			     struct ulist *roots, const u64 *extent_item_pos,
1216
			     u64 root_objectid, u64 inum, int check_shared)
1217 1218 1219 1220
{
	struct btrfs_key key;
	struct btrfs_path *path;
	struct btrfs_delayed_ref_root *delayed_refs = NULL;
1221
	struct btrfs_delayed_ref_head *head;
1222 1223 1224 1225 1226
	int info_level = 0;
	int ret;
	struct list_head prefs_delayed;
	struct list_head prefs;
	struct __prelim_ref *ref;
1227
	struct extent_inode_elem *eie = NULL;
1228
	struct ref_root *ref_tree = NULL;
1229
	u64 total_refs = 0;
1230 1231 1232 1233 1234 1235

	INIT_LIST_HEAD(&prefs);
	INIT_LIST_HEAD(&prefs_delayed);

	key.objectid = bytenr;
	key.offset = (u64)-1;
1236 1237 1238 1239
	if (btrfs_fs_incompat(fs_info, SKINNY_METADATA))
		key.type = BTRFS_METADATA_ITEM_KEY;
	else
		key.type = BTRFS_EXTENT_ITEM_KEY;
1240 1241 1242 1243

	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;
1244
	if (!trans) {
1245
		path->search_commit_root = 1;
1246 1247
		path->skip_locking = 1;
	}
1248

1249
	if (time_seq == SEQ_LAST)
1250 1251
		path->skip_locking = 1;

1252 1253 1254 1255 1256 1257
	/*
	 * grab both a lock on the path and a lock on the delayed ref head.
	 * We need both to get a consistent picture of how the refs look
	 * at a specified point in time
	 */
again:
1258 1259
	head = NULL;

1260 1261 1262 1263 1264 1265 1266 1267 1268 1269 1270 1271
	if (check_shared) {
		if (!ref_tree) {
			ref_tree = ref_root_alloc();
			if (!ref_tree) {
				ret = -ENOMEM;
				goto out;
			}
		} else {
			ref_root_fini(ref_tree);
		}
	}

1272 1273 1274 1275 1276
	ret = btrfs_search_slot(trans, fs_info->extent_root, &key, path, 0, 0);
	if (ret < 0)
		goto out;
	BUG_ON(ret == 0);

1277
#ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
1278
	if (trans && likely(trans->type != __TRANS_DUMMY) &&
1279
	    time_seq != SEQ_LAST) {
1280
#else
1281
	if (trans && time_seq != SEQ_LAST) {
1282
#endif
1283 1284 1285 1286 1287 1288
		/*
		 * look if there are updates for this ref queued and lock the
		 * head
		 */
		delayed_refs = &trans->transaction->delayed_refs;
		spin_lock(&delayed_refs->lock);
1289
		head = btrfs_find_delayed_ref_head(delayed_refs, bytenr);
1290 1291
		if (head) {
			if (!mutex_trylock(&head->mutex)) {
1292
				refcount_inc(&head->node.refs);
1293 1294 1295 1296 1297 1298 1299 1300 1301 1302 1303 1304 1305
				spin_unlock(&delayed_refs->lock);

				btrfs_release_path(path);

				/*
				 * Mutex was contended, block until it's
				 * released and try again
				 */
				mutex_lock(&head->mutex);
				mutex_unlock(&head->mutex);
				btrfs_put_delayed_ref(&head->node);
				goto again;
			}
1306
			spin_unlock(&delayed_refs->lock);
1307
			ret = __add_delayed_refs(head, time_seq,
1308 1309
						 &prefs_delayed, &total_refs,
						 inum);
1310
			mutex_unlock(&head->mutex);
1311
			if (ret)
1312
				goto out;
1313 1314
		} else {
			spin_unlock(&delayed_refs->lock);
1315
		}
1316 1317 1318 1319 1320 1321 1322 1323 1324 1325 1326 1327 1328 1329 1330 1331 1332 1333 1334 1335 1336 1337 1338 1339 1340 1341 1342 1343 1344 1345

		if (check_shared && !list_empty(&prefs_delayed)) {
			/*
			 * Add all delay_ref to the ref_tree and check if there
			 * are multiple ref items added.
			 */
			list_for_each_entry(ref, &prefs_delayed, list) {
				if (ref->key_for_search.type) {
					ret = ref_tree_add(ref_tree,
						ref->root_id,
						ref->key_for_search.objectid,
						ref->key_for_search.offset,
						0, ref->count);
					if (ret)
						goto out;
				} else {
					ret = ref_tree_add(ref_tree, 0, 0, 0,
						     ref->parent, ref->count);
					if (ret)
						goto out;
				}

			}

			if (ref_tree->unique_refs > 1) {
				ret = BACKREF_FOUND_SHARED;
				goto out;
			}

		}
1346 1347 1348 1349 1350 1351
	}

	if (path->slots[0]) {
		struct extent_buffer *leaf;
		int slot;

1352
		path->slots[0]--;
1353
		leaf = path->nodes[0];
1354
		slot = path->slots[0];
1355 1356
		btrfs_item_key_to_cpu(leaf, &key, slot);
		if (key.objectid == bytenr &&
1357 1358
		    (key.type == BTRFS_EXTENT_ITEM_KEY ||
		     key.type == BTRFS_METADATA_ITEM_KEY)) {
1359
			ret = __add_inline_refs(path, bytenr,
1360
						&info_level, &prefs,
1361 1362
						ref_tree, &total_refs,
						inum);
1363 1364
			if (ret)
				goto out;
1365
			ret = __add_keyed_refs(fs_info, path, bytenr,
1366 1367
					       info_level, &prefs,
					       ref_tree, inum);
1368 1369 1370 1371 1372 1373 1374 1375
			if (ret)
				goto out;
		}
	}
	btrfs_release_path(path);

	list_splice_init(&prefs_delayed, &prefs);

1376 1377 1378 1379
	ret = __add_missing_keys(fs_info, &prefs);
	if (ret)
		goto out;

1380
	__merge_refs(&prefs, MERGE_IDENTICAL_KEYS);
1381

1382
	ret = __resolve_indirect_refs(fs_info, path, time_seq, &prefs,
1383 1384
				      extent_item_pos, total_refs,
				      root_objectid);
1385 1386 1387
	if (ret)
		goto out;

1388
	__merge_refs(&prefs, MERGE_IDENTICAL_PARENTS);
1389 1390 1391

	while (!list_empty(&prefs)) {
		ref = list_first_entry(&prefs, struct __prelim_ref, list);
J
Julia Lawall 已提交
1392
		WARN_ON(ref->count < 0);
1393
		if (roots && ref->count && ref->root_id && ref->parent == 0) {
1394 1395 1396 1397 1398
			if (root_objectid && ref->root_id != root_objectid) {
				ret = BACKREF_FOUND_SHARED;
				goto out;
			}

1399 1400
			/* no parent == root of tree */
			ret = ulist_add(roots, ref->root_id, 0, GFP_NOFS);
1401 1402
			if (ret < 0)
				goto out;
1403 1404
		}
		if (ref->count && ref->parent) {
1405 1406
			if (extent_item_pos && !ref->inode_list &&
			    ref->level == 0) {
1407
				struct extent_buffer *eb;
1408

1409
				eb = read_tree_block(fs_info, ref->parent, 0);
1410 1411 1412 1413
				if (IS_ERR(eb)) {
					ret = PTR_ERR(eb);
					goto out;
				} else if (!extent_buffer_uptodate(eb)) {
1414
					free_extent_buffer(eb);
1415 1416
					ret = -EIO;
					goto out;
1417
				}
1418 1419
				btrfs_tree_read_lock(eb);
				btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
1420 1421
				ret = find_extent_in_eb(eb, bytenr,
							*extent_item_pos, &eie);
1422
				btrfs_tree_read_unlock_blocking(eb);
1423
				free_extent_buffer(eb);
1424 1425 1426
				if (ret < 0)
					goto out;
				ref->inode_list = eie;
1427
			}
1428 1429 1430
			ret = ulist_add_merge_ptr(refs, ref->parent,
						  ref->inode_list,
						  (void **)&eie, GFP_NOFS);
1431 1432
			if (ret < 0)
				goto out;
1433 1434 1435 1436 1437 1438 1439 1440 1441 1442
			if (!ret && extent_item_pos) {
				/*
				 * we've recorded that parent, so we must extend
				 * its inode list here
				 */
				BUG_ON(!eie);
				while (eie->next)
					eie = eie->next;
				eie->next = ref->inode_list;
			}
1443
			eie = NULL;
1444
		}
1445
		list_del(&ref->list);
1446
		kmem_cache_free(btrfs_prelim_ref_cache, ref);
1447 1448 1449 1450
	}

out:
	btrfs_free_path(path);
1451
	ref_root_free(ref_tree);
1452 1453 1454
	while (!list_empty(&prefs)) {
		ref = list_first_entry(&prefs, struct __prelim_ref, list);
		list_del(&ref->list);
1455
		kmem_cache_free(btrfs_prelim_ref_cache, ref);
1456 1457 1458 1459 1460
	}
	while (!list_empty(&prefs_delayed)) {
		ref = list_first_entry(&prefs_delayed, struct __prelim_ref,
				       list);
		list_del(&ref->list);
1461
		kmem_cache_free(btrfs_prelim_ref_cache, ref);
1462
	}
1463 1464
	if (ret < 0)
		free_inode_elem_list(eie);
1465 1466 1467
	return ret;
}

1468 1469 1470 1471 1472 1473 1474 1475 1476 1477
static void free_leaf_list(struct ulist *blocks)
{
	struct ulist_node *node = NULL;
	struct extent_inode_elem *eie;
	struct ulist_iterator uiter;

	ULIST_ITER_INIT(&uiter);
	while ((node = ulist_next(blocks, &uiter))) {
		if (!node->aux)
			continue;
1478
		eie = (struct extent_inode_elem *)(uintptr_t)node->aux;
1479
		free_inode_elem_list(eie);
1480 1481 1482 1483 1484 1485
		node->aux = 0;
	}

	ulist_free(blocks);
}

1486 1487 1488 1489 1490 1491 1492 1493 1494 1495
/*
 * Finds all leafs with a reference to the specified combination of bytenr and
 * offset. key_list_head will point to a list of corresponding keys (caller must
 * free each list element). The leafs will be stored in the leafs ulist, which
 * must be freed with ulist_free.
 *
 * returns 0 on success, <0 on error
 */
static int btrfs_find_all_leafs(struct btrfs_trans_handle *trans,
				struct btrfs_fs_info *fs_info, u64 bytenr,
1496
				u64 time_seq, struct ulist **leafs,
1497
				const u64 *extent_item_pos)
1498 1499 1500 1501
{
	int ret;

	*leafs = ulist_alloc(GFP_NOFS);
1502
	if (!*leafs)
1503 1504
		return -ENOMEM;

1505 1506
	ret = find_parent_nodes(trans, fs_info, bytenr, time_seq,
				*leafs, NULL, extent_item_pos, 0, 0, 0);
1507
	if (ret < 0 && ret != -ENOENT) {
1508
		free_leaf_list(*leafs);
1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 1526 1527
		return ret;
	}

	return 0;
}

/*
 * walk all backrefs for a given extent to find all roots that reference this
 * extent. Walking a backref means finding all extents that reference this
 * extent and in turn walk the backrefs of those, too. Naturally this is a
 * recursive process, but here it is implemented in an iterative fashion: We
 * find all referencing extents for the extent in question and put them on a
 * list. In turn, we find all referencing extents for those, further appending
 * to the list. The way we iterate the list allows adding more elements after
 * the current while iterating. The process stops when we reach the end of the
 * list. Found roots are added to the roots list.
 *
 * returns 0 on success, < 0 on error.
 */
1528 1529 1530
static int __btrfs_find_all_roots(struct btrfs_trans_handle *trans,
				  struct btrfs_fs_info *fs_info, u64 bytenr,
				  u64 time_seq, struct ulist **roots)
1531 1532 1533
{
	struct ulist *tmp;
	struct ulist_node *node = NULL;
J
Jan Schmidt 已提交
1534
	struct ulist_iterator uiter;
1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545
	int ret;

	tmp = ulist_alloc(GFP_NOFS);
	if (!tmp)
		return -ENOMEM;
	*roots = ulist_alloc(GFP_NOFS);
	if (!*roots) {
		ulist_free(tmp);
		return -ENOMEM;
	}

J
Jan Schmidt 已提交
1546
	ULIST_ITER_INIT(&uiter);
1547
	while (1) {
1548 1549
		ret = find_parent_nodes(trans, fs_info, bytenr, time_seq,
					tmp, *roots, NULL, 0, 0, 0);
1550 1551 1552 1553 1554
		if (ret < 0 && ret != -ENOENT) {
			ulist_free(tmp);
			ulist_free(*roots);
			return ret;
		}
J
Jan Schmidt 已提交
1555
		node = ulist_next(tmp, &uiter);
1556 1557 1558
		if (!node)
			break;
		bytenr = node->val;
1559
		cond_resched();
1560 1561 1562 1563 1564 1565
	}

	ulist_free(tmp);
	return 0;
}

1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579
int btrfs_find_all_roots(struct btrfs_trans_handle *trans,
			 struct btrfs_fs_info *fs_info, u64 bytenr,
			 u64 time_seq, struct ulist **roots)
{
	int ret;

	if (!trans)
		down_read(&fs_info->commit_root_sem);
	ret = __btrfs_find_all_roots(trans, fs_info, bytenr, time_seq, roots);
	if (!trans)
		up_read(&fs_info->commit_root_sem);
	return ret;
}

1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592
/**
 * btrfs_check_shared - tell us whether an extent is shared
 *
 * @trans: optional trans handle
 *
 * btrfs_check_shared uses the backref walking code but will short
 * circuit as soon as it finds a root or inode that doesn't match the
 * one passed in. This provides a significant performance benefit for
 * callers (such as fiemap) which want to know whether the extent is
 * shared but do not need a ref count.
 *
 * Return: 0 if extent is not shared, 1 if it is shared, < 0 on error.
 */
1593 1594 1595 1596 1597 1598 1599 1600
int btrfs_check_shared(struct btrfs_trans_handle *trans,
		       struct btrfs_fs_info *fs_info, u64 root_objectid,
		       u64 inum, u64 bytenr)
{
	struct ulist *tmp = NULL;
	struct ulist *roots = NULL;
	struct ulist_iterator uiter;
	struct ulist_node *node;
1601
	struct seq_list elem = SEQ_LIST_INIT(elem);
1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613 1614 1615 1616 1617 1618
	int ret = 0;

	tmp = ulist_alloc(GFP_NOFS);
	roots = ulist_alloc(GFP_NOFS);
	if (!tmp || !roots) {
		ulist_free(tmp);
		ulist_free(roots);
		return -ENOMEM;
	}

	if (trans)
		btrfs_get_tree_mod_seq(fs_info, &elem);
	else
		down_read(&fs_info->commit_root_sem);
	ULIST_ITER_INIT(&uiter);
	while (1) {
		ret = find_parent_nodes(trans, fs_info, bytenr, elem.seq, tmp,
1619
					roots, NULL, root_objectid, inum, 1);
1620
		if (ret == BACKREF_FOUND_SHARED) {
1621
			/* this is the only condition under which we return 1 */
1622 1623 1624 1625 1626
			ret = 1;
			break;
		}
		if (ret < 0 && ret != -ENOENT)
			break;
1627
		ret = 0;
1628 1629 1630 1631 1632 1633 1634 1635 1636 1637 1638 1639 1640 1641 1642
		node = ulist_next(tmp, &uiter);
		if (!node)
			break;
		bytenr = node->val;
		cond_resched();
	}
	if (trans)
		btrfs_put_tree_mod_seq(fs_info, &elem);
	else
		up_read(&fs_info->commit_root_sem);
	ulist_free(tmp);
	ulist_free(roots);
	return ret;
}

M
Mark Fasheh 已提交
1643 1644 1645 1646 1647 1648 1649 1650 1651 1652 1653 1654 1655
int btrfs_find_one_extref(struct btrfs_root *root, u64 inode_objectid,
			  u64 start_off, struct btrfs_path *path,
			  struct btrfs_inode_extref **ret_extref,
			  u64 *found_off)
{
	int ret, slot;
	struct btrfs_key key;
	struct btrfs_key found_key;
	struct btrfs_inode_extref *extref;
	struct extent_buffer *leaf;
	unsigned long ptr;

	key.objectid = inode_objectid;
1656
	key.type = BTRFS_INODE_EXTREF_KEY;
M
Mark Fasheh 已提交
1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695
	key.offset = start_off;

	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
	if (ret < 0)
		return ret;

	while (1) {
		leaf = path->nodes[0];
		slot = path->slots[0];
		if (slot >= btrfs_header_nritems(leaf)) {
			/*
			 * If the item at offset is not found,
			 * btrfs_search_slot will point us to the slot
			 * where it should be inserted. In our case
			 * that will be the slot directly before the
			 * next INODE_REF_KEY_V2 item. In the case
			 * that we're pointing to the last slot in a
			 * leaf, we must move one leaf over.
			 */
			ret = btrfs_next_leaf(root, path);
			if (ret) {
				if (ret >= 1)
					ret = -ENOENT;
				break;
			}
			continue;
		}

		btrfs_item_key_to_cpu(leaf, &found_key, slot);

		/*
		 * Check that we're still looking at an extended ref key for
		 * this particular objectid. If we have different
		 * objectid or type then there are no more to be found
		 * in the tree and we can exit.
		 */
		ret = -ENOENT;
		if (found_key.objectid != inode_objectid)
			break;
1696
		if (found_key.type != BTRFS_INODE_EXTREF_KEY)
M
Mark Fasheh 已提交
1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710
			break;

		ret = 0;
		ptr = btrfs_item_ptr_offset(leaf, path->slots[0]);
		extref = (struct btrfs_inode_extref *)ptr;
		*ret_extref = extref;
		if (found_off)
			*found_off = found_key.offset;
		break;
	}

	return ret;
}

1711 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724
/*
 * this iterates to turn a name (from iref/extref) into a full filesystem path.
 * Elements of the path are separated by '/' and the path is guaranteed to be
 * 0-terminated. the path is only given within the current file system.
 * Therefore, it never starts with a '/'. the caller is responsible to provide
 * "size" bytes in "dest". the dest buffer will be filled backwards. finally,
 * the start point of the resulting string is returned. this pointer is within
 * dest, normally.
 * in case the path buffer would overflow, the pointer is decremented further
 * as if output was written to the buffer, though no more output is actually
 * generated. that way, the caller can determine how much space would be
 * required for the path to fit into the buffer. in that case, the returned
 * value will be smaller than dest. callers must check this!
 */
1725 1726 1727 1728
char *btrfs_ref_to_path(struct btrfs_root *fs_root, struct btrfs_path *path,
			u32 name_len, unsigned long name_off,
			struct extent_buffer *eb_in, u64 parent,
			char *dest, u32 size)
1729 1730 1731 1732
{
	int slot;
	u64 next_inum;
	int ret;
1733
	s64 bytes_left = ((s64)size) - 1;
1734 1735
	struct extent_buffer *eb = eb_in;
	struct btrfs_key found_key;
1736
	int leave_spinning = path->leave_spinning;
M
Mark Fasheh 已提交
1737
	struct btrfs_inode_ref *iref;
1738 1739 1740 1741

	if (bytes_left >= 0)
		dest[bytes_left] = '\0';

1742
	path->leave_spinning = 1;
1743
	while (1) {
M
Mark Fasheh 已提交
1744
		bytes_left -= name_len;
1745 1746
		if (bytes_left >= 0)
			read_extent_buffer(eb, dest + bytes_left,
M
Mark Fasheh 已提交
1747
					   name_off, name_len);
1748
		if (eb != eb_in) {
1749 1750
			if (!path->skip_locking)
				btrfs_tree_read_unlock_blocking(eb);
1751
			free_extent_buffer(eb);
1752
		}
1753 1754
		ret = btrfs_find_item(fs_root, path, parent, 0,
				BTRFS_INODE_REF_KEY, &found_key);
1755 1756
		if (ret > 0)
			ret = -ENOENT;
1757 1758
		if (ret)
			break;
M
Mark Fasheh 已提交
1759

1760 1761 1762 1763 1764 1765 1766 1767 1768
		next_inum = found_key.offset;

		/* regular exit ahead */
		if (parent == next_inum)
			break;

		slot = path->slots[0];
		eb = path->nodes[0];
		/* make sure we can use eb after releasing the path */
1769
		if (eb != eb_in) {
1770 1771 1772 1773
			if (!path->skip_locking)
				btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
			path->nodes[0] = NULL;
			path->locks[0] = 0;
1774
		}
1775 1776
		btrfs_release_path(path);
		iref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
M
Mark Fasheh 已提交
1777 1778 1779 1780

		name_len = btrfs_inode_ref_name_len(eb, iref);
		name_off = (unsigned long)(iref + 1);

1781 1782 1783 1784 1785 1786 1787
		parent = next_inum;
		--bytes_left;
		if (bytes_left >= 0)
			dest[bytes_left] = '/';
	}

	btrfs_release_path(path);
1788
	path->leave_spinning = leave_spinning;
1789 1790 1791 1792 1793 1794 1795 1796 1797 1798 1799 1800 1801

	if (ret)
		return ERR_PTR(ret);

	return dest + bytes_left;
}

/*
 * this makes the path point to (logical EXTENT_ITEM *)
 * returns BTRFS_EXTENT_FLAG_DATA for data, BTRFS_EXTENT_FLAG_TREE_BLOCK for
 * tree blocks and <0 on error.
 */
int extent_from_logical(struct btrfs_fs_info *fs_info, u64 logical,
1802 1803
			struct btrfs_path *path, struct btrfs_key *found_key,
			u64 *flags_ret)
1804 1805 1806
{
	int ret;
	u64 flags;
1807
	u64 size = 0;
1808 1809 1810 1811 1812
	u32 item_size;
	struct extent_buffer *eb;
	struct btrfs_extent_item *ei;
	struct btrfs_key key;

1813 1814 1815 1816
	if (btrfs_fs_incompat(fs_info, SKINNY_METADATA))
		key.type = BTRFS_METADATA_ITEM_KEY;
	else
		key.type = BTRFS_EXTENT_ITEM_KEY;
1817 1818 1819 1820 1821 1822 1823
	key.objectid = logical;
	key.offset = (u64)-1;

	ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, path, 0, 0);
	if (ret < 0)
		return ret;

1824 1825 1826 1827 1828
	ret = btrfs_previous_extent_item(fs_info->extent_root, path, 0);
	if (ret) {
		if (ret > 0)
			ret = -ENOENT;
		return ret;
1829
	}
1830
	btrfs_item_key_to_cpu(path->nodes[0], found_key, path->slots[0]);
1831
	if (found_key->type == BTRFS_METADATA_ITEM_KEY)
1832
		size = fs_info->nodesize;
1833 1834 1835
	else if (found_key->type == BTRFS_EXTENT_ITEM_KEY)
		size = found_key->offset;

1836
	if (found_key->objectid > logical ||
1837
	    found_key->objectid + size <= logical) {
1838 1839
		btrfs_debug(fs_info,
			"logical %llu is not within any extent", logical);
1840
		return -ENOENT;
J
Jan Schmidt 已提交
1841
	}
1842 1843 1844 1845 1846 1847 1848 1849

	eb = path->nodes[0];
	item_size = btrfs_item_size_nr(eb, path->slots[0]);
	BUG_ON(item_size < sizeof(*ei));

	ei = btrfs_item_ptr(eb, path->slots[0], struct btrfs_extent_item);
	flags = btrfs_extent_flags(eb, ei);

1850 1851
	btrfs_debug(fs_info,
		"logical %llu is at position %llu within the extent (%llu EXTENT_ITEM %llu) flags %#llx size %u",
1852 1853
		 logical, logical - found_key->objectid, found_key->objectid,
		 found_key->offset, flags, item_size);
1854 1855 1856 1857 1858 1859 1860 1861 1862 1863 1864

	WARN_ON(!flags_ret);
	if (flags_ret) {
		if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)
			*flags_ret = BTRFS_EXTENT_FLAG_TREE_BLOCK;
		else if (flags & BTRFS_EXTENT_FLAG_DATA)
			*flags_ret = BTRFS_EXTENT_FLAG_DATA;
		else
			BUG_ON(1);
		return 0;
	}
1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877

	return -EIO;
}

/*
 * helper function to iterate extent inline refs. ptr must point to a 0 value
 * for the first call and may be modified. it is used to track state.
 * if more refs exist, 0 is returned and the next call to
 * __get_extent_inline_ref must pass the modified ptr parameter to get the
 * next ref. after the last ref was processed, 1 is returned.
 * returns <0 on error
 */
static int __get_extent_inline_ref(unsigned long *ptr, struct extent_buffer *eb,
1878 1879 1880 1881
				   struct btrfs_key *key,
				   struct btrfs_extent_item *ei, u32 item_size,
				   struct btrfs_extent_inline_ref **out_eiref,
				   int *out_type)
1882 1883 1884 1885 1886 1887 1888 1889 1890
{
	unsigned long end;
	u64 flags;
	struct btrfs_tree_block_info *info;

	if (!*ptr) {
		/* first call */
		flags = btrfs_extent_flags(eb, ei);
		if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
1891 1892 1893 1894 1895 1896 1897 1898 1899 1900
			if (key->type == BTRFS_METADATA_ITEM_KEY) {
				/* a skinny metadata extent */
				*out_eiref =
				     (struct btrfs_extent_inline_ref *)(ei + 1);
			} else {
				WARN_ON(key->type != BTRFS_EXTENT_ITEM_KEY);
				info = (struct btrfs_tree_block_info *)(ei + 1);
				*out_eiref =
				   (struct btrfs_extent_inline_ref *)(info + 1);
			}
1901 1902 1903 1904
		} else {
			*out_eiref = (struct btrfs_extent_inline_ref *)(ei + 1);
		}
		*ptr = (unsigned long)*out_eiref;
1905
		if ((unsigned long)(*ptr) >= (unsigned long)ei + item_size)
1906 1907 1908 1909
			return -ENOENT;
	}

	end = (unsigned long)ei + item_size;
1910
	*out_eiref = (struct btrfs_extent_inline_ref *)(*ptr);
1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928
	*out_type = btrfs_extent_inline_ref_type(eb, *out_eiref);

	*ptr += btrfs_extent_inline_ref_size(*out_type);
	WARN_ON(*ptr > end);
	if (*ptr == end)
		return 1; /* last */

	return 0;
}

/*
 * reads the tree block backref for an extent. tree level and root are returned
 * through out_level and out_root. ptr must point to a 0 value for the first
 * call and may be modified (see __get_extent_inline_ref comment).
 * returns 0 if data was provided, 1 if there was no more data to provide or
 * <0 on error.
 */
int tree_backref_for_extent(unsigned long *ptr, struct extent_buffer *eb,
1929 1930
			    struct btrfs_key *key, struct btrfs_extent_item *ei,
			    u32 item_size, u64 *out_root, u8 *out_level)
1931 1932 1933 1934 1935 1936 1937 1938 1939
{
	int ret;
	int type;
	struct btrfs_extent_inline_ref *eiref;

	if (*ptr == (unsigned long)-1)
		return 1;

	while (1) {
1940 1941
		ret = __get_extent_inline_ref(ptr, eb, key, ei, item_size,
					      &eiref, &type);
1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954
		if (ret < 0)
			return ret;

		if (type == BTRFS_TREE_BLOCK_REF_KEY ||
		    type == BTRFS_SHARED_BLOCK_REF_KEY)
			break;

		if (ret == 1)
			return 1;
	}

	/* we can treat both ref types equally here */
	*out_root = btrfs_extent_inline_ref_offset(eb, eiref);
1955 1956 1957 1958 1959 1960 1961 1962 1963 1964

	if (key->type == BTRFS_EXTENT_ITEM_KEY) {
		struct btrfs_tree_block_info *info;

		info = (struct btrfs_tree_block_info *)(ei + 1);
		*out_level = btrfs_tree_block_level(eb, info);
	} else {
		ASSERT(key->type == BTRFS_METADATA_ITEM_KEY);
		*out_level = (u8)key->offset;
	}
1965 1966 1967 1968 1969 1970 1971

	if (ret == 1)
		*ptr = (unsigned long)-1;

	return 0;
}

1972 1973 1974 1975
static int iterate_leaf_refs(struct btrfs_fs_info *fs_info,
			     struct extent_inode_elem *inode_list,
			     u64 root, u64 extent_item_objectid,
			     iterate_extent_inodes_t *iterate, void *ctx)
1976
{
1977
	struct extent_inode_elem *eie;
J
Jan Schmidt 已提交
1978 1979
	int ret = 0;

1980
	for (eie = inode_list; eie; eie = eie->next) {
1981 1982 1983 1984
		btrfs_debug(fs_info,
			    "ref for %llu resolved, key (%llu EXTEND_DATA %llu), root %llu",
			    extent_item_objectid, eie->inum,
			    eie->offset, root);
1985
		ret = iterate(eie->inum, eie->offset, root, ctx);
J
Jan Schmidt 已提交
1986
		if (ret) {
1987 1988 1989
			btrfs_debug(fs_info,
				    "stopping iteration for %llu due to ret=%d",
				    extent_item_objectid, ret);
J
Jan Schmidt 已提交
1990 1991
			break;
		}
1992 1993 1994 1995 1996 1997 1998
	}

	return ret;
}

/*
 * calls iterate() for every inode that references the extent identified by
J
Jan Schmidt 已提交
1999
 * the given parameters.
2000 2001 2002
 * when the iterator function returns a non-zero value, iteration stops.
 */
int iterate_extent_inodes(struct btrfs_fs_info *fs_info,
J
Jan Schmidt 已提交
2003
				u64 extent_item_objectid, u64 extent_item_pos,
2004
				int search_commit_root,
2005 2006 2007
				iterate_extent_inodes_t *iterate, void *ctx)
{
	int ret;
2008
	struct btrfs_trans_handle *trans = NULL;
2009 2010
	struct ulist *refs = NULL;
	struct ulist *roots = NULL;
J
Jan Schmidt 已提交
2011 2012
	struct ulist_node *ref_node = NULL;
	struct ulist_node *root_node = NULL;
2013
	struct seq_list tree_mod_seq_elem = SEQ_LIST_INIT(tree_mod_seq_elem);
J
Jan Schmidt 已提交
2014 2015
	struct ulist_iterator ref_uiter;
	struct ulist_iterator root_uiter;
2016

2017
	btrfs_debug(fs_info, "resolving all inodes for extent %llu",
J
Jan Schmidt 已提交
2018
			extent_item_objectid);
2019

2020
	if (!search_commit_root) {
2021 2022 2023
		trans = btrfs_join_transaction(fs_info->extent_root);
		if (IS_ERR(trans))
			return PTR_ERR(trans);
2024
		btrfs_get_tree_mod_seq(fs_info, &tree_mod_seq_elem);
2025 2026
	} else {
		down_read(&fs_info->commit_root_sem);
2027
	}
2028

J
Jan Schmidt 已提交
2029
	ret = btrfs_find_all_leafs(trans, fs_info, extent_item_objectid,
2030
				   tree_mod_seq_elem.seq, &refs,
2031
				   &extent_item_pos);
J
Jan Schmidt 已提交
2032 2033
	if (ret)
		goto out;
2034

J
Jan Schmidt 已提交
2035 2036
	ULIST_ITER_INIT(&ref_uiter);
	while (!ret && (ref_node = ulist_next(refs, &ref_uiter))) {
2037 2038
		ret = __btrfs_find_all_roots(trans, fs_info, ref_node->val,
					     tree_mod_seq_elem.seq, &roots);
J
Jan Schmidt 已提交
2039 2040
		if (ret)
			break;
J
Jan Schmidt 已提交
2041 2042
		ULIST_ITER_INIT(&root_uiter);
		while (!ret && (root_node = ulist_next(roots, &root_uiter))) {
2043 2044 2045 2046 2047 2048
			btrfs_debug(fs_info,
				    "root %llu references leaf %llu, data list %#llx",
				    root_node->val, ref_node->val,
				    ref_node->aux);
			ret = iterate_leaf_refs(fs_info,
						(struct extent_inode_elem *)
2049 2050 2051 2052
						(uintptr_t)ref_node->aux,
						root_node->val,
						extent_item_objectid,
						iterate, ctx);
J
Jan Schmidt 已提交
2053
		}
2054
		ulist_free(roots);
2055 2056
	}

2057
	free_leaf_list(refs);
J
Jan Schmidt 已提交
2058
out:
2059
	if (!search_commit_root) {
2060
		btrfs_put_tree_mod_seq(fs_info, &tree_mod_seq_elem);
2061
		btrfs_end_transaction(trans);
2062 2063
	} else {
		up_read(&fs_info->commit_root_sem);
2064 2065
	}

2066 2067 2068 2069 2070 2071 2072 2073
	return ret;
}

int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info,
				struct btrfs_path *path,
				iterate_extent_inodes_t *iterate, void *ctx)
{
	int ret;
J
Jan Schmidt 已提交
2074
	u64 extent_item_pos;
2075
	u64 flags = 0;
2076
	struct btrfs_key found_key;
2077
	int search_commit_root = path->search_commit_root;
2078

2079
	ret = extent_from_logical(fs_info, logical, path, &found_key, &flags);
J
Jan Schmidt 已提交
2080
	btrfs_release_path(path);
2081 2082
	if (ret < 0)
		return ret;
2083
	if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)
2084
		return -EINVAL;
2085

J
Jan Schmidt 已提交
2086
	extent_item_pos = logical - found_key.objectid;
2087 2088 2089
	ret = iterate_extent_inodes(fs_info, found_key.objectid,
					extent_item_pos, search_commit_root,
					iterate, ctx);
2090 2091 2092 2093

	return ret;
}

M
Mark Fasheh 已提交
2094 2095 2096 2097 2098 2099
typedef int (iterate_irefs_t)(u64 parent, u32 name_len, unsigned long name_off,
			      struct extent_buffer *eb, void *ctx);

static int iterate_inode_refs(u64 inum, struct btrfs_root *fs_root,
			      struct btrfs_path *path,
			      iterate_irefs_t *iterate, void *ctx)
2100
{
2101
	int ret = 0;
2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112
	int slot;
	u32 cur;
	u32 len;
	u32 name_len;
	u64 parent = 0;
	int found = 0;
	struct extent_buffer *eb;
	struct btrfs_item *item;
	struct btrfs_inode_ref *iref;
	struct btrfs_key found_key;

2113
	while (!ret) {
2114 2115 2116 2117
		ret = btrfs_find_item(fs_root, path, inum,
				parent ? parent + 1 : 0, BTRFS_INODE_REF_KEY,
				&found_key);

2118 2119 2120 2121 2122 2123 2124 2125 2126 2127
		if (ret < 0)
			break;
		if (ret) {
			ret = found ? 0 : -ENOENT;
			break;
		}
		++found;

		parent = found_key.offset;
		slot = path->slots[0];
2128 2129 2130 2131 2132 2133
		eb = btrfs_clone_extent_buffer(path->nodes[0]);
		if (!eb) {
			ret = -ENOMEM;
			break;
		}
		extent_buffer_get(eb);
2134 2135
		btrfs_tree_read_lock(eb);
		btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
2136 2137
		btrfs_release_path(path);

2138
		item = btrfs_item_nr(slot);
2139 2140 2141 2142 2143
		iref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);

		for (cur = 0; cur < btrfs_item_size(eb, item); cur += len) {
			name_len = btrfs_inode_ref_name_len(eb, iref);
			/* path must be released before calling iterate()! */
2144 2145 2146
			btrfs_debug(fs_root->fs_info,
				"following ref at offset %u for inode %llu in tree %llu",
				cur, found_key.objectid, fs_root->objectid);
M
Mark Fasheh 已提交
2147 2148
			ret = iterate(parent, name_len,
				      (unsigned long)(iref + 1), eb, ctx);
2149
			if (ret)
2150 2151 2152 2153
				break;
			len = sizeof(*iref) + name_len;
			iref = (struct btrfs_inode_ref *)((char *)iref + len);
		}
2154
		btrfs_tree_read_unlock_blocking(eb);
2155 2156 2157 2158 2159 2160 2161 2162
		free_extent_buffer(eb);
	}

	btrfs_release_path(path);

	return ret;
}

M
Mark Fasheh 已提交
2163 2164 2165 2166 2167 2168 2169 2170 2171 2172 2173 2174 2175 2176 2177 2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189
static int iterate_inode_extrefs(u64 inum, struct btrfs_root *fs_root,
				 struct btrfs_path *path,
				 iterate_irefs_t *iterate, void *ctx)
{
	int ret;
	int slot;
	u64 offset = 0;
	u64 parent;
	int found = 0;
	struct extent_buffer *eb;
	struct btrfs_inode_extref *extref;
	u32 item_size;
	u32 cur_offset;
	unsigned long ptr;

	while (1) {
		ret = btrfs_find_one_extref(fs_root, inum, offset, path, &extref,
					    &offset);
		if (ret < 0)
			break;
		if (ret) {
			ret = found ? 0 : -ENOENT;
			break;
		}
		++found;

		slot = path->slots[0];
2190 2191 2192 2193 2194 2195
		eb = btrfs_clone_extent_buffer(path->nodes[0]);
		if (!eb) {
			ret = -ENOMEM;
			break;
		}
		extent_buffer_get(eb);
M
Mark Fasheh 已提交
2196 2197 2198 2199 2200

		btrfs_tree_read_lock(eb);
		btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
		btrfs_release_path(path);

2201 2202
		item_size = btrfs_item_size_nr(eb, slot);
		ptr = btrfs_item_ptr_offset(eb, slot);
M
Mark Fasheh 已提交
2203 2204 2205 2206 2207 2208 2209 2210 2211 2212 2213 2214 2215
		cur_offset = 0;

		while (cur_offset < item_size) {
			u32 name_len;

			extref = (struct btrfs_inode_extref *)(ptr + cur_offset);
			parent = btrfs_inode_extref_parent(eb, extref);
			name_len = btrfs_inode_extref_name_len(eb, extref);
			ret = iterate(parent, name_len,
				      (unsigned long)&extref->name, eb, ctx);
			if (ret)
				break;

2216
			cur_offset += btrfs_inode_extref_name_len(eb, extref);
M
Mark Fasheh 已提交
2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249
			cur_offset += sizeof(*extref);
		}
		btrfs_tree_read_unlock_blocking(eb);
		free_extent_buffer(eb);

		offset++;
	}

	btrfs_release_path(path);

	return ret;
}

static int iterate_irefs(u64 inum, struct btrfs_root *fs_root,
			 struct btrfs_path *path, iterate_irefs_t *iterate,
			 void *ctx)
{
	int ret;
	int found_refs = 0;

	ret = iterate_inode_refs(inum, fs_root, path, iterate, ctx);
	if (!ret)
		++found_refs;
	else if (ret != -ENOENT)
		return ret;

	ret = iterate_inode_extrefs(inum, fs_root, path, iterate, ctx);
	if (ret == -ENOENT && found_refs)
		return 0;

	return ret;
}

2250 2251 2252 2253
/*
 * returns 0 if the path could be dumped (probably truncated)
 * returns <0 in case of an error
 */
M
Mark Fasheh 已提交
2254 2255
static int inode_to_path(u64 inum, u32 name_len, unsigned long name_off,
			 struct extent_buffer *eb, void *ctx)
2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266
{
	struct inode_fs_paths *ipath = ctx;
	char *fspath;
	char *fspath_min;
	int i = ipath->fspath->elem_cnt;
	const int s_ptr = sizeof(char *);
	u32 bytes_left;

	bytes_left = ipath->fspath->bytes_left > s_ptr ?
					ipath->fspath->bytes_left - s_ptr : 0;

2267
	fspath_min = (char *)ipath->fspath->val + (i + 1) * s_ptr;
2268 2269
	fspath = btrfs_ref_to_path(ipath->fs_root, ipath->btrfs_path, name_len,
				   name_off, eb, inum, fspath_min, bytes_left);
2270 2271 2272 2273
	if (IS_ERR(fspath))
		return PTR_ERR(fspath);

	if (fspath > fspath_min) {
2274
		ipath->fspath->val[i] = (u64)(unsigned long)fspath;
2275 2276 2277 2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288
		++ipath->fspath->elem_cnt;
		ipath->fspath->bytes_left = fspath - fspath_min;
	} else {
		++ipath->fspath->elem_missed;
		ipath->fspath->bytes_missing += fspath_min - fspath;
		ipath->fspath->bytes_left = 0;
	}

	return 0;
}

/*
 * this dumps all file system paths to the inode into the ipath struct, provided
 * is has been created large enough. each path is zero-terminated and accessed
2289
 * from ipath->fspath->val[i].
2290
 * when it returns, there are ipath->fspath->elem_cnt number of paths available
2291
 * in ipath->fspath->val[]. when the allocated space wasn't sufficient, the
2292
 * number of missed paths is recorded in ipath->fspath->elem_missed, otherwise,
2293 2294 2295 2296 2297 2298
 * it's zero. ipath->fspath->bytes_missing holds the number of bytes that would
 * have been needed to return all paths.
 */
int paths_from_inode(u64 inum, struct inode_fs_paths *ipath)
{
	return iterate_irefs(inum, ipath->fs_root, ipath->btrfs_path,
M
Mark Fasheh 已提交
2299
			     inode_to_path, ipath);
2300 2301 2302 2303 2304 2305 2306 2307
}

struct btrfs_data_container *init_data_container(u32 total_bytes)
{
	struct btrfs_data_container *data;
	size_t alloc_bytes;

	alloc_bytes = max_t(size_t, total_bytes, sizeof(*data));
2308
	data = vmalloc(alloc_bytes);
2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343
	if (!data)
		return ERR_PTR(-ENOMEM);

	if (total_bytes >= sizeof(*data)) {
		data->bytes_left = total_bytes - sizeof(*data);
		data->bytes_missing = 0;
	} else {
		data->bytes_missing = sizeof(*data) - total_bytes;
		data->bytes_left = 0;
	}

	data->elem_cnt = 0;
	data->elem_missed = 0;

	return data;
}

/*
 * allocates space to return multiple file system paths for an inode.
 * total_bytes to allocate are passed, note that space usable for actual path
 * information will be total_bytes - sizeof(struct inode_fs_paths).
 * the returned pointer must be freed with free_ipath() in the end.
 */
struct inode_fs_paths *init_ipath(s32 total_bytes, struct btrfs_root *fs_root,
					struct btrfs_path *path)
{
	struct inode_fs_paths *ifp;
	struct btrfs_data_container *fspath;

	fspath = init_data_container(total_bytes);
	if (IS_ERR(fspath))
		return (void *)fspath;

	ifp = kmalloc(sizeof(*ifp), GFP_NOFS);
	if (!ifp) {
2344
		vfree(fspath);
2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356
		return ERR_PTR(-ENOMEM);
	}

	ifp->btrfs_path = path;
	ifp->fspath = fspath;
	ifp->fs_root = fs_root;

	return ifp;
}

void free_ipath(struct inode_fs_paths *ipath)
{
2357 2358
	if (!ipath)
		return;
2359
	vfree(ipath->fspath);
2360 2361
	kfree(ipath);
}