backref.c 59.5 KB
Newer Older
1
// SPDX-License-Identifier: GPL-2.0
2 3 4 5
/*
 * Copyright (C) 2011 STRATO.  All rights reserved.
 */

6
#include <linux/mm.h>
7
#include <linux/rbtree.h>
8
#include <trace/events/btrfs.h>
9 10 11
#include "ctree.h"
#include "disk-io.h"
#include "backref.h"
12 13 14
#include "ulist.h"
#include "transaction.h"
#include "delayed-ref.h"
15
#include "locking.h"
16

17 18 19
/* Just an arbitrary number so we can be sure this happened */
#define BACKREF_FOUND_SHARED 6

20 21 22 23 24 25
struct extent_inode_elem {
	u64 inum;
	u64 offset;
	struct extent_inode_elem *next;
};

26 27 28 29
static int check_extent_in_eb(const struct btrfs_key *key,
			      const struct extent_buffer *eb,
			      const struct btrfs_file_extent_item *fi,
			      u64 extent_item_pos,
30 31
			      struct extent_inode_elem **eie,
			      bool ignore_offset)
32
{
33
	u64 offset = 0;
34 35
	struct extent_inode_elem *e;

36 37
	if (!ignore_offset &&
	    !btrfs_file_extent_compression(eb, fi) &&
38 39 40 41
	    !btrfs_file_extent_encryption(eb, fi) &&
	    !btrfs_file_extent_other_encoding(eb, fi)) {
		u64 data_offset;
		u64 data_len;
42

43 44 45 46 47 48 49 50
		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;
	}
51 52 53 54 55 56 57

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

	e->next = *eie;
	e->inum = key->objectid;
58
	e->offset = key->offset + offset;
59 60 61 62 63
	*eie = e;

	return 0;
}

64 65 66 67 68 69 70 71 72 73
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);
	}
}

74 75
static int find_extent_in_eb(const struct extent_buffer *eb,
			     u64 wanted_disk_byte, u64 extent_item_pos,
76 77
			     struct extent_inode_elem **eie,
			     bool ignore_offset)
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
{
	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;

106
		ret = check_extent_in_eb(&key, eb, fi, extent_item_pos, eie, ignore_offset);
107 108 109 110 111 112 113
		if (ret < 0)
			return ret;
	}

	return 0;
}

114 115
struct preftree {
	struct rb_root root;
116
	unsigned int count;
117 118
};

119
#define PREFTREE_INIT	{ .root = RB_ROOT, .count = 0 }
120 121 122 123 124 125 126

struct preftrees {
	struct preftree direct;    /* BTRFS_SHARED_[DATA|BLOCK]_REF_KEY */
	struct preftree indirect;  /* BTRFS_[TREE_BLOCK|EXTENT_DATA]_REF_KEY */
	struct preftree indirect_missing_keys;
};

127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145
/*
 * Checks for a shared extent during backref search.
 *
 * The share_count tracks prelim_refs (direct and indirect) having a
 * ref->count >0:
 *  - incremented when a ref->count transitions to >0
 *  - decremented when a ref->count transitions to <1
 */
struct share_check {
	u64 root_objectid;
	u64 inum;
	int share_count;
};

static inline int extent_is_shared(struct share_check *sc)
{
	return (sc && sc->share_count > 1) ? BACKREF_FOUND_SHARED : 0;
}

146 147 148 149 150
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",
151
					sizeof(struct prelim_ref),
152
					0,
153
					SLAB_MEM_SPREAD,
154 155 156 157 158 159
					NULL);
	if (!btrfs_prelim_ref_cache)
		return -ENOMEM;
	return 0;
}

160
void __cold btrfs_prelim_ref_exit(void)
161
{
162
	kmem_cache_destroy(btrfs_prelim_ref_cache);
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
static void free_pref(struct prelim_ref *ref)
{
	kmem_cache_free(btrfs_prelim_ref_cache, ref);
}

/*
 * Return 0 when both refs are for the same block (and can be merged).
 * A -1 return indicates ref1 is a 'lower' block than ref2, while 1
 * indicates a 'higher' block.
 */
static int prelim_ref_compare(struct prelim_ref *ref1,
			      struct prelim_ref *ref2)
{
	if (ref1->level < ref2->level)
		return -1;
	if (ref1->level > ref2->level)
		return 1;
	if (ref1->root_id < ref2->root_id)
		return -1;
	if (ref1->root_id > ref2->root_id)
		return 1;
	if (ref1->key_for_search.type < ref2->key_for_search.type)
		return -1;
	if (ref1->key_for_search.type > ref2->key_for_search.type)
		return 1;
	if (ref1->key_for_search.objectid < ref2->key_for_search.objectid)
		return -1;
	if (ref1->key_for_search.objectid > ref2->key_for_search.objectid)
		return 1;
	if (ref1->key_for_search.offset < ref2->key_for_search.offset)
		return -1;
	if (ref1->key_for_search.offset > ref2->key_for_search.offset)
		return 1;
	if (ref1->parent < ref2->parent)
		return -1;
	if (ref1->parent > ref2->parent)
		return 1;

	return 0;
}

206 207
static void update_share_count(struct share_check *sc, int oldcount,
			       int newcount)
208 209 210 211 212 213 214 215 216 217
{
	if ((!sc) || (oldcount == 0 && newcount < 1))
		return;

	if (oldcount > 0 && newcount < 1)
		sc->share_count--;
	else if (oldcount < 1 && newcount > 0)
		sc->share_count++;
}

218 219 220
/*
 * Add @newref to the @root rbtree, merging identical refs.
 *
221
 * Callers should assume that newref has been freed after calling.
222
 */
223 224
static void prelim_ref_insert(const struct btrfs_fs_info *fs_info,
			      struct preftree *preftree,
225 226
			      struct prelim_ref *newref,
			      struct share_check *sc)
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
{
	struct rb_root *root;
	struct rb_node **p;
	struct rb_node *parent = NULL;
	struct prelim_ref *ref;
	int result;

	root = &preftree->root;
	p = &root->rb_node;

	while (*p) {
		parent = *p;
		ref = rb_entry(parent, struct prelim_ref, rbnode);
		result = prelim_ref_compare(ref, newref);
		if (result < 0) {
			p = &(*p)->rb_left;
		} else if (result > 0) {
			p = &(*p)->rb_right;
		} else {
			/* Identical refs, merge them and free @newref */
			struct extent_inode_elem *eie = ref->inode_list;

			while (eie && eie->next)
				eie = eie->next;

			if (!eie)
				ref->inode_list = newref->inode_list;
			else
				eie->next = newref->inode_list;
256 257
			trace_btrfs_prelim_ref_merge(fs_info, ref, newref,
						     preftree->count);
258 259 260 261 262 263 264
			/*
			 * A delayed ref can have newref->count < 0.
			 * The ref->count is updated to follow any
			 * BTRFS_[ADD|DROP]_DELAYED_REF actions.
			 */
			update_share_count(sc, ref->count,
					   ref->count + newref->count);
265 266 267 268 269 270
			ref->count += newref->count;
			free_pref(newref);
			return;
		}
	}

271
	update_share_count(sc, 0, newref->count);
272
	preftree->count++;
273
	trace_btrfs_prelim_ref_insert(fs_info, newref, NULL, preftree->count);
274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290
	rb_link_node(&newref->rbnode, parent, p);
	rb_insert_color(&newref->rbnode, root);
}

/*
 * Release the entire tree.  We don't care about internal consistency so
 * just free everything and then reset the tree root.
 */
static void prelim_release(struct preftree *preftree)
{
	struct prelim_ref *ref, *next_ref;

	rbtree_postorder_for_each_entry_safe(ref, next_ref, &preftree->root,
					     rbnode)
		free_pref(ref);

	preftree->root = RB_ROOT;
291
	preftree->count = 0;
292 293
}

294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325
/*
 * 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
326
 *                (see add_missing_keys)
327 328 329 330 331
 * - 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.
 */
332 333
static int add_prelim_ref(const struct btrfs_fs_info *fs_info,
			  struct preftree *preftree, u64 root_id,
334
			  const struct btrfs_key *key, int level, u64 parent,
335 336
			  u64 wanted_disk_byte, int count,
			  struct share_check *sc, gfp_t gfp_mask)
337
{
338
	struct prelim_ref *ref;
339

340 341 342
	if (root_id == BTRFS_DATA_RELOC_TREE_OBJECTID)
		return 0;

343
	ref = kmem_cache_alloc(btrfs_prelim_ref_cache, gfp_mask);
344 345 346 347
	if (!ref)
		return -ENOMEM;

	ref->root_id = root_id;
348
	if (key) {
349
		ref->key_for_search = *key;
350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372
		/*
		 * 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 {
373
		memset(&ref->key_for_search, 0, sizeof(ref->key_for_search));
374
	}
375

376
	ref->inode_list = NULL;
377 378 379 380
	ref->level = level;
	ref->count = count;
	ref->parent = parent;
	ref->wanted_disk_byte = wanted_disk_byte;
381 382
	prelim_ref_insert(fs_info, preftree, ref, sc);
	return extent_is_shared(sc);
383 384
}

385
/* direct refs use root == 0, key == NULL */
386 387
static int add_direct_ref(const struct btrfs_fs_info *fs_info,
			  struct preftrees *preftrees, int level, u64 parent,
388 389
			  u64 wanted_disk_byte, int count,
			  struct share_check *sc, gfp_t gfp_mask)
390
{
391
	return add_prelim_ref(fs_info, &preftrees->direct, 0, NULL, level,
392
			      parent, wanted_disk_byte, count, sc, gfp_mask);
393 394 395
}

/* indirect refs use parent == 0 */
396 397
static int add_indirect_ref(const struct btrfs_fs_info *fs_info,
			    struct preftrees *preftrees, u64 root_id,
398
			    const struct btrfs_key *key, int level,
399 400
			    u64 wanted_disk_byte, int count,
			    struct share_check *sc, gfp_t gfp_mask)
401 402 403 404 405
{
	struct preftree *tree = &preftrees->indirect;

	if (!key)
		tree = &preftrees->indirect_missing_keys;
406
	return add_prelim_ref(fs_info, tree, root_id, key, level, 0,
407
			      wanted_disk_byte, count, sc, gfp_mask);
408 409
}

410
static int add_all_parents(struct btrfs_root *root, struct btrfs_path *path,
411
			   struct ulist *parents, struct prelim_ref *ref,
412
			   int level, u64 time_seq, const u64 *extent_item_pos,
413
			   u64 total_refs, bool ignore_offset)
414
{
415 416 417 418
	int ret = 0;
	int slot;
	struct extent_buffer *eb;
	struct btrfs_key key;
419
	struct btrfs_key *key_for_search = &ref->key_for_search;
420
	struct btrfs_file_extent_item *fi;
421
	struct extent_inode_elem *eie = NULL, *old = NULL;
422
	u64 disk_byte;
423 424
	u64 wanted_disk_byte = ref->wanted_disk_byte;
	u64 count = 0;
425

426 427 428
	if (level != 0) {
		eb = path->nodes[level];
		ret = ulist_add(parents, eb->start, 0, GFP_NOFS);
429 430
		if (ret < 0)
			return ret;
431
		return 0;
432
	}
433 434

	/*
435 436 437
	 * 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.
438
	 */
439
	if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
440
		if (time_seq == SEQ_LAST)
441 442 443 444
			ret = btrfs_next_leaf(root, path);
		else
			ret = btrfs_next_old_leaf(root, path, time_seq);
	}
445

446
	while (!ret && count < total_refs) {
447
		eb = path->nodes[0];
448 449 450 451 452 453 454 455 456 457 458 459 460
		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;
461
			old = NULL;
462
			count++;
463 464 465
			if (extent_item_pos) {
				ret = check_extent_in_eb(&key, eb, fi,
						*extent_item_pos,
466
						&eie, ignore_offset);
467 468 469
				if (ret < 0)
					break;
			}
470 471
			if (ret > 0)
				goto next;
472 473
			ret = ulist_add_merge_ptr(parents, eb->start,
						  eie, (void **)&old, GFP_NOFS);
474 475 476 477 478 479
			if (ret < 0)
				break;
			if (!ret && extent_item_pos) {
				while (old->next)
					old = old->next;
				old->next = eie;
480
			}
481
			eie = NULL;
482
		}
483
next:
484
		if (time_seq == SEQ_LAST)
485 486 487
			ret = btrfs_next_item(root, path);
		else
			ret = btrfs_next_old_item(root, path, time_seq);
488 489
	}

490 491
	if (ret > 0)
		ret = 0;
492 493
	else if (ret < 0)
		free_inode_elem_list(eie);
494
	return ret;
495 496 497 498 499 500
}

/*
 * resolve an indirect backref in the form (root_id, key, level)
 * to a logical address
 */
501 502 503
static int resolve_indirect_ref(struct btrfs_fs_info *fs_info,
				struct btrfs_path *path, u64 time_seq,
				struct prelim_ref *ref, struct ulist *parents,
504 505
				const u64 *extent_item_pos, u64 total_refs,
				bool ignore_offset)
506 507 508 509 510 511 512
{
	struct btrfs_root *root;
	struct btrfs_key root_key;
	struct extent_buffer *eb;
	int ret = 0;
	int root_level;
	int level = ref->level;
513
	int index;
514 515 516 517

	root_key.objectid = ref->root_id;
	root_key.type = BTRFS_ROOT_ITEM_KEY;
	root_key.offset = (u64)-1;
518 519 520

	index = srcu_read_lock(&fs_info->subvol_srcu);

521
	root = btrfs_get_fs_root(fs_info, &root_key, false);
522
	if (IS_ERR(root)) {
523
		srcu_read_unlock(&fs_info->subvol_srcu, index);
524 525 526 527
		ret = PTR_ERR(root);
		goto out;
	}

528
	if (btrfs_is_testing(fs_info)) {
J
Josef Bacik 已提交
529 530 531 532 533
		srcu_read_unlock(&fs_info->subvol_srcu, index);
		ret = -ENOENT;
		goto out;
	}

534 535
	if (path->search_commit_root)
		root_level = btrfs_header_level(root->commit_root);
536
	else if (time_seq == SEQ_LAST)
537
		root_level = btrfs_header_level(root->node);
538 539
	else
		root_level = btrfs_old_root_level(root, time_seq);
540

541 542
	if (root_level + 1 == level) {
		srcu_read_unlock(&fs_info->subvol_srcu, index);
543
		goto out;
544
	}
545 546

	path->lowest_level = level;
547
	if (time_seq == SEQ_LAST)
548 549 550 551 552
		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);
553 554 555 556

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

557 558
	btrfs_debug(fs_info,
		"search slot in root %llu (level %d, ref count %d) returned %d for key (%llu %u %llu)",
559 560 561
		 ref->root_id, level, ref->count, ret,
		 ref->key_for_search.objectid, ref->key_for_search.type,
		 ref->key_for_search.offset);
562 563 564 565
	if (ret < 0)
		goto out;

	eb = path->nodes[level];
566
	while (!eb) {
567
		if (WARN_ON(!level)) {
568 569 570 571 572
			ret = 1;
			goto out;
		}
		level--;
		eb = path->nodes[level];
573 574
	}

575
	ret = add_all_parents(root, path, parents, ref, level, time_seq,
576
			      extent_item_pos, total_refs, ignore_offset);
577
out:
578 579
	path->lowest_level = 0;
	btrfs_release_path(path);
580 581 582
	return ret;
}

583 584 585 586 587 588 589 590
static struct extent_inode_elem *
unode_aux_to_inode_list(struct ulist_node *node)
{
	if (!node)
		return NULL;
	return (struct extent_inode_elem *)(uintptr_t)node->aux;
}

591
/*
592 593 594 595 596 597 598 599 600 601 602 603 604 605
 * We maintain three seperate rbtrees: one for direct refs, one for
 * indirect refs which have a key, and one for indirect refs which do not
 * have a key. Each tree does merge on insertion.
 *
 * Once all of the references are located, we iterate over the tree of
 * indirect refs with missing keys. An appropriate key is located and
 * the ref is moved onto the tree for indirect refs. After all missing
 * keys are thus located, we iterate over the indirect ref tree, resolve
 * each reference, and then insert the resolved reference onto the
 * direct tree (merging there too).
 *
 * New backrefs (i.e., for parent nodes) are added to the appropriate
 * rbtree as they are encountered. The new backrefs are subsequently
 * resolved as above.
606
 */
607 608
static int resolve_indirect_refs(struct btrfs_fs_info *fs_info,
				 struct btrfs_path *path, u64 time_seq,
609
				 struct preftrees *preftrees,
610
				 const u64 *extent_item_pos, u64 total_refs,
611
				 struct share_check *sc, bool ignore_offset)
612 613 614 615 616
{
	int err;
	int ret = 0;
	struct ulist *parents;
	struct ulist_node *node;
J
Jan Schmidt 已提交
617
	struct ulist_iterator uiter;
618
	struct rb_node *rnode;
619 620 621 622 623 624

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

	/*
625 626 627 628
	 * We could trade memory usage for performance here by iterating
	 * the tree, allocating new refs for each insertion, and then
	 * freeing the entire indirect tree when we're done.  In some test
	 * cases, the tree can grow quite large (~200k objects).
629
	 */
630 631 632 633 634 635 636 637 638 639 640
	while ((rnode = rb_first(&preftrees->indirect.root))) {
		struct prelim_ref *ref;

		ref = rb_entry(rnode, struct prelim_ref, rbnode);
		if (WARN(ref->parent,
			 "BUG: direct ref found in indirect tree")) {
			ret = -EINVAL;
			goto out;
		}

		rb_erase(&ref->rbnode, &preftrees->indirect.root);
641
		preftrees->indirect.count--;
642 643 644

		if (ref->count == 0) {
			free_pref(ref);
645
			continue;
646 647
		}

648 649
		if (sc && sc->root_objectid &&
		    ref->root_id != sc->root_objectid) {
650
			free_pref(ref);
651 652 653
			ret = BACKREF_FOUND_SHARED;
			goto out;
		}
654 655
		err = resolve_indirect_ref(fs_info, path, time_seq, ref,
					   parents, extent_item_pos,
656
					   total_refs, ignore_offset);
657 658 659 660 661
		/*
		 * we can only tolerate ENOENT,otherwise,we should catch error
		 * and return directly.
		 */
		if (err == -ENOENT) {
662 663
			prelim_ref_insert(fs_info, &preftrees->direct, ref,
					  NULL);
664
			continue;
665
		} else if (err) {
666
			free_pref(ref);
667 668 669
			ret = err;
			goto out;
		}
670 671

		/* we put the first parent into the ref at hand */
J
Jan Schmidt 已提交
672 673
		ULIST_ITER_INIT(&uiter);
		node = ulist_next(parents, &uiter);
674
		ref->parent = node ? node->val : 0;
675
		ref->inode_list = unode_aux_to_inode_list(node);
676

677
		/* Add a prelim_ref(s) for any other parent(s). */
J
Jan Schmidt 已提交
678
		while ((node = ulist_next(parents, &uiter))) {
679 680
			struct prelim_ref *new_ref;

681 682
			new_ref = kmem_cache_alloc(btrfs_prelim_ref_cache,
						   GFP_NOFS);
683
			if (!new_ref) {
684
				free_pref(ref);
685
				ret = -ENOMEM;
686
				goto out;
687 688 689
			}
			memcpy(new_ref, ref, sizeof(*ref));
			new_ref->parent = node->val;
690
			new_ref->inode_list = unode_aux_to_inode_list(node);
691 692
			prelim_ref_insert(fs_info, &preftrees->direct,
					  new_ref, NULL);
693
		}
694

695 696 697 698 699
		/*
		 * Now it's a direct ref, put it in the the direct tree. We must
		 * do this last because the ref could be merged/freed here.
		 */
		prelim_ref_insert(fs_info, &preftrees->direct, ref, NULL);
700

701
		ulist_reinit(parents);
702
		cond_resched();
703
	}
704
out:
705 706 707 708
	ulist_free(parents);
	return ret;
}

709 710 711
/*
 * read tree blocks and add keys where required.
 */
712
static int add_missing_keys(struct btrfs_fs_info *fs_info,
713
			    struct preftrees *preftrees, bool lock)
714
{
715
	struct prelim_ref *ref;
716
	struct extent_buffer *eb;
717 718
	struct preftree *tree = &preftrees->indirect_missing_keys;
	struct rb_node *node;
719

720 721 722 723 724 725
	while ((node = rb_first(&tree->root))) {
		ref = rb_entry(node, struct prelim_ref, rbnode);
		rb_erase(node, &tree->root);

		BUG_ON(ref->parent);	/* should not be a direct ref */
		BUG_ON(ref->key_for_search.type);
726
		BUG_ON(!ref->wanted_disk_byte);
727

728 729
		eb = read_tree_block(fs_info, ref->wanted_disk_byte, 0,
				     ref->level - 1, NULL);
730
		if (IS_ERR(eb)) {
731
			free_pref(ref);
732 733
			return PTR_ERR(eb);
		} else if (!extent_buffer_uptodate(eb)) {
734
			free_pref(ref);
735 736 737
			free_extent_buffer(eb);
			return -EIO;
		}
738 739
		if (lock)
			btrfs_tree_read_lock(eb);
740 741 742 743
		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);
744 745
		if (lock)
			btrfs_tree_read_unlock(eb);
746
		free_extent_buffer(eb);
747
		prelim_ref_insert(fs_info, &preftrees->indirect, ref, NULL);
748
		cond_resched();
749 750 751 752
	}
	return 0;
}

753 754 755 756
/*
 * add all currently queued delayed refs from this head whose seq nr is
 * smaller or equal that seq to the list
 */
757 758
static int add_delayed_refs(const struct btrfs_fs_info *fs_info,
			    struct btrfs_delayed_ref_head *head, u64 seq,
759
			    struct preftrees *preftrees, u64 *total_refs,
760
			    struct share_check *sc)
761
{
762
	struct btrfs_delayed_ref_node *node;
763
	struct btrfs_delayed_extent_op *extent_op = head->extent_op;
764
	struct btrfs_key key;
765
	struct btrfs_key tmp_op_key;
766
	struct rb_node *n;
767
	int count;
768
	int ret = 0;
769

770
	if (extent_op && extent_op->update_key)
771
		btrfs_disk_key_to_cpu(&tmp_op_key, &extent_op->key);
772

773
	spin_lock(&head->lock);
774 775 776
	for (n = rb_first(&head->ref_tree); n; n = rb_next(n)) {
		node = rb_entry(n, struct btrfs_delayed_ref_node,
				ref_node);
777 778 779 780 781 782 783 784 785
		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:
786
			count = node->ref_mod;
787 788
			break;
		case BTRFS_DROP_DELAYED_REF:
789
			count = node->ref_mod * -1;
790 791 792 793
			break;
		default:
			BUG_ON(1);
		}
794
		*total_refs += count;
795 796
		switch (node->type) {
		case BTRFS_TREE_BLOCK_REF_KEY: {
797
			/* NORMAL INDIRECT METADATA backref */
798 799 800
			struct btrfs_delayed_tree_ref *ref;

			ref = btrfs_delayed_node_to_tree_ref(node);
801 802
			ret = add_indirect_ref(fs_info, preftrees, ref->root,
					       &tmp_op_key, ref->level + 1,
803 804
					       node->bytenr, count, sc,
					       GFP_ATOMIC);
805 806 807
			break;
		}
		case BTRFS_SHARED_BLOCK_REF_KEY: {
808
			/* SHARED DIRECT METADATA backref */
809 810 811
			struct btrfs_delayed_tree_ref *ref;

			ref = btrfs_delayed_node_to_tree_ref(node);
812

813 814
			ret = add_direct_ref(fs_info, preftrees, ref->level + 1,
					     ref->parent, node->bytenr, count,
815
					     sc, GFP_ATOMIC);
816 817 818
			break;
		}
		case BTRFS_EXTENT_DATA_REF_KEY: {
819
			/* NORMAL INDIRECT DATA backref */
820 821 822 823 824 825
			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;
826 827 828 829 830

			/*
			 * Found a inum that doesn't match our known inum, we
			 * know it's shared.
			 */
831
			if (sc && sc->inum && ref->objectid != sc->inum) {
832
				ret = BACKREF_FOUND_SHARED;
833
				goto out;
834 835
			}

836
			ret = add_indirect_ref(fs_info, preftrees, ref->root,
837 838
					       &key, 0, node->bytenr, count, sc,
					       GFP_ATOMIC);
839 840 841
			break;
		}
		case BTRFS_SHARED_DATA_REF_KEY: {
842
			/* SHARED DIRECT FULL backref */
843 844 845
			struct btrfs_delayed_data_ref *ref;

			ref = btrfs_delayed_node_to_data_ref(node);
846

847 848 849
			ret = add_direct_ref(fs_info, preftrees, 0, ref->parent,
					     node->bytenr, count, sc,
					     GFP_ATOMIC);
850 851 852 853 854
			break;
		}
		default:
			WARN_ON(1);
		}
855 856 857 858 859
		/*
		 * We must ignore BACKREF_FOUND_SHARED until all delayed
		 * refs have been checked.
		 */
		if (ret && (ret != BACKREF_FOUND_SHARED))
860
			break;
861
	}
862 863 864
	if (!ret)
		ret = extent_is_shared(sc);
out:
865 866
	spin_unlock(&head->lock);
	return ret;
867 868 869 870
}

/*
 * add all inline backrefs for bytenr to the list
871 872
 *
 * Returns 0 on success, <0 on error, or BACKREF_FOUND_SHARED.
873
 */
874 875
static int add_inline_refs(const struct btrfs_fs_info *fs_info,
			   struct btrfs_path *path, u64 bytenr,
876
			   int *info_level, struct preftrees *preftrees,
877
			   u64 *total_refs, struct share_check *sc)
878
{
879
	int ret = 0;
880 881 882
	int slot;
	struct extent_buffer *leaf;
	struct btrfs_key key;
883
	struct btrfs_key found_key;
884 885 886 887 888 889 890 891 892 893
	unsigned long ptr;
	unsigned long end;
	struct btrfs_extent_item *ei;
	u64 flags;
	u64 item_size;

	/*
	 * enumerate all inline refs
	 */
	leaf = path->nodes[0];
894
	slot = path->slots[0];
895 896 897 898 899 900

	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);
901
	*total_refs += btrfs_extent_refs(leaf, ei);
902
	btrfs_item_key_to_cpu(leaf, &found_key, slot);
903 904 905 906

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

907 908
	if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
	    flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
909 910 911 912 913 914
		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);
915 916
	} else if (found_key.type == BTRFS_METADATA_ITEM_KEY) {
		*info_level = found_key.offset;
917 918 919 920 921 922 923 924 925 926
	} 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;
927 928 929
		type = btrfs_get_extent_inline_ref_type(leaf, iref,
							BTRFS_REF_TYPE_ANY);
		if (type == BTRFS_REF_TYPE_INVALID)
930
			return -EUCLEAN;
931

932 933 934 935
		offset = btrfs_extent_inline_ref_offset(leaf, iref);

		switch (type) {
		case BTRFS_SHARED_BLOCK_REF_KEY:
936 937
			ret = add_direct_ref(fs_info, preftrees,
					     *info_level + 1, offset,
938
					     bytenr, 1, NULL, GFP_NOFS);
939 940 941 942 943 944 945
			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);
946

947
			ret = add_direct_ref(fs_info, preftrees, 0, offset,
948
					     bytenr, count, sc, GFP_NOFS);
949 950 951
			break;
		}
		case BTRFS_TREE_BLOCK_REF_KEY:
952 953
			ret = add_indirect_ref(fs_info, preftrees, offset,
					       NULL, *info_level + 1,
954
					       bytenr, 1, NULL, GFP_NOFS);
955 956 957 958 959 960 961 962 963 964 965 966
			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);
967

968
			if (sc && sc->inum && key.objectid != sc->inum) {
969 970 971 972
				ret = BACKREF_FOUND_SHARED;
				break;
			}

973
			root = btrfs_extent_data_ref_root(leaf, dref);
974

975 976
			ret = add_indirect_ref(fs_info, preftrees, root,
					       &key, 0, bytenr, count,
977
					       sc, GFP_NOFS);
978 979 980 981 982
			break;
		}
		default:
			WARN_ON(1);
		}
983 984
		if (ret)
			return ret;
985 986 987 988 989 990 991 992
		ptr += btrfs_extent_inline_ref_size(type);
	}

	return 0;
}

/*
 * add all non-inline backrefs for bytenr to the list
993 994
 *
 * Returns 0 on success, <0 on error, or BACKREF_FOUND_SHARED.
995
 */
996 997
static int add_keyed_refs(struct btrfs_fs_info *fs_info,
			  struct btrfs_path *path, u64 bytenr,
998
			  int info_level, struct preftrees *preftrees,
999
			  struct share_check *sc)
1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028
{
	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:
1029
			/* SHARED DIRECT METADATA backref */
1030 1031
			ret = add_direct_ref(fs_info, preftrees,
					     info_level + 1, key.offset,
1032
					     bytenr, 1, NULL, GFP_NOFS);
1033 1034
			break;
		case BTRFS_SHARED_DATA_REF_KEY: {
1035
			/* SHARED DIRECT FULL backref */
1036 1037 1038 1039 1040 1041
			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);
1042 1043
			ret = add_direct_ref(fs_info, preftrees, 0,
					     key.offset, bytenr, count,
1044
					     sc, GFP_NOFS);
1045 1046 1047
			break;
		}
		case BTRFS_TREE_BLOCK_REF_KEY:
1048
			/* NORMAL INDIRECT METADATA backref */
1049 1050
			ret = add_indirect_ref(fs_info, preftrees, key.offset,
					       NULL, info_level + 1, bytenr,
1051
					       1, NULL, GFP_NOFS);
1052 1053
			break;
		case BTRFS_EXTENT_DATA_REF_KEY: {
1054
			/* NORMAL INDIRECT DATA backref */
1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065
			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);
1066

1067
			if (sc && sc->inum && key.objectid != sc->inum) {
1068 1069 1070 1071
				ret = BACKREF_FOUND_SHARED;
				break;
			}

1072
			root = btrfs_extent_data_ref_root(leaf, dref);
1073 1074
			ret = add_indirect_ref(fs_info, preftrees, root,
					       &key, 0, bytenr, count,
1075
					       sc, GFP_NOFS);
1076 1077 1078 1079 1080
			break;
		}
		default:
			WARN_ON(1);
		}
1081 1082 1083
		if (ret)
			return ret;

1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094
	}

	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
 *
1095
 * If time_seq is set to SEQ_LAST, it will not search delayed_refs, and behave
1096 1097 1098 1099
 * 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().
 *
1100 1101 1102 1103 1104
 * @sc - if !NULL, then immediately return BACKREF_FOUND_SHARED when a
 * shared extent is detected.
 *
 * Otherwise this returns 0 for success and <0 for an error.
 *
1105 1106 1107 1108
 * If ignore_offset is set to false, only extent refs whose offsets match
 * extent_item_pos are returned.  If true, every extent ref is returned
 * and extent_item_pos is ignored.
 *
1109 1110 1111 1112
 * 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,
1113
			     u64 time_seq, struct ulist *refs,
1114
			     struct ulist *roots, const u64 *extent_item_pos,
1115
			     struct share_check *sc, bool ignore_offset)
1116 1117 1118 1119
{
	struct btrfs_key key;
	struct btrfs_path *path;
	struct btrfs_delayed_ref_root *delayed_refs = NULL;
1120
	struct btrfs_delayed_ref_head *head;
1121 1122
	int info_level = 0;
	int ret;
1123
	struct prelim_ref *ref;
1124
	struct rb_node *node;
1125
	struct extent_inode_elem *eie = NULL;
1126
	/* total of both direct AND indirect refs! */
1127
	u64 total_refs = 0;
1128 1129 1130 1131 1132
	struct preftrees preftrees = {
		.direct = PREFTREE_INIT,
		.indirect = PREFTREE_INIT,
		.indirect_missing_keys = PREFTREE_INIT
	};
1133 1134 1135

	key.objectid = bytenr;
	key.offset = (u64)-1;
1136 1137 1138 1139
	if (btrfs_fs_incompat(fs_info, SKINNY_METADATA))
		key.type = BTRFS_METADATA_ITEM_KEY;
	else
		key.type = BTRFS_EXTENT_ITEM_KEY;
1140 1141 1142 1143

	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;
1144
	if (!trans) {
1145
		path->search_commit_root = 1;
1146 1147
		path->skip_locking = 1;
	}
1148

1149
	if (time_seq == SEQ_LAST)
1150 1151
		path->skip_locking = 1;

1152 1153 1154 1155 1156 1157
	/*
	 * 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:
1158 1159
	head = NULL;

1160 1161 1162 1163 1164
	ret = btrfs_search_slot(trans, fs_info->extent_root, &key, path, 0, 0);
	if (ret < 0)
		goto out;
	BUG_ON(ret == 0);

1165
#ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
1166
	if (trans && likely(trans->type != __TRANS_DUMMY) &&
1167
	    time_seq != SEQ_LAST) {
1168
#else
1169
	if (trans && time_seq != SEQ_LAST) {
1170
#endif
1171 1172 1173 1174 1175 1176
		/*
		 * look if there are updates for this ref queued and lock the
		 * head
		 */
		delayed_refs = &trans->transaction->delayed_refs;
		spin_lock(&delayed_refs->lock);
1177
		head = btrfs_find_delayed_ref_head(delayed_refs, bytenr);
1178 1179
		if (head) {
			if (!mutex_trylock(&head->mutex)) {
1180
				refcount_inc(&head->refs);
1181 1182 1183 1184 1185 1186 1187 1188 1189 1190
				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);
1191
				btrfs_put_delayed_ref_head(head);
1192 1193
				goto again;
			}
1194
			spin_unlock(&delayed_refs->lock);
1195
			ret = add_delayed_refs(fs_info, head, time_seq,
1196
					       &preftrees, &total_refs, sc);
1197
			mutex_unlock(&head->mutex);
1198
			if (ret)
1199
				goto out;
1200 1201
		} else {
			spin_unlock(&delayed_refs->lock);
1202
		}
1203 1204 1205 1206 1207 1208
	}

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

1209
		path->slots[0]--;
1210
		leaf = path->nodes[0];
1211
		slot = path->slots[0];
1212 1213
		btrfs_item_key_to_cpu(leaf, &key, slot);
		if (key.objectid == bytenr &&
1214 1215
		    (key.type == BTRFS_EXTENT_ITEM_KEY ||
		     key.type == BTRFS_METADATA_ITEM_KEY)) {
1216 1217
			ret = add_inline_refs(fs_info, path, bytenr,
					      &info_level, &preftrees,
1218
					      &total_refs, sc);
1219 1220
			if (ret)
				goto out;
1221
			ret = add_keyed_refs(fs_info, path, bytenr, info_level,
1222
					     &preftrees, sc);
1223 1224 1225 1226 1227
			if (ret)
				goto out;
		}
	}

1228
	btrfs_release_path(path);
1229

1230
	ret = add_missing_keys(fs_info, &preftrees, path->skip_locking == 0);
1231 1232 1233
	if (ret)
		goto out;

1234
	WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect_missing_keys.root));
1235

1236
	ret = resolve_indirect_refs(fs_info, path, time_seq, &preftrees,
1237
				    extent_item_pos, total_refs, sc, ignore_offset);
1238 1239 1240
	if (ret)
		goto out;

1241
	WARN_ON(!RB_EMPTY_ROOT(&preftrees.indirect.root));
1242

1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253
	/*
	 * This walks the tree of merged and resolved refs. Tree blocks are
	 * read in as needed. Unique entries are added to the ulist, and
	 * the list of found roots is updated.
	 *
	 * We release the entire tree in one go before returning.
	 */
	node = rb_first(&preftrees.direct.root);
	while (node) {
		ref = rb_entry(node, struct prelim_ref, rbnode);
		node = rb_next(&ref->rbnode);
1254 1255 1256 1257 1258 1259 1260 1261 1262 1263
		/*
		 * ref->count < 0 can happen here if there are delayed
		 * refs with a node->action of BTRFS_DROP_DELAYED_REF.
		 * prelim_ref_insert() relies on this when merging
		 * identical refs to keep the overall count correct.
		 * prelim_ref_insert() will merge only those refs
		 * which compare identically.  Any refs having
		 * e.g. different offsets would not be merged,
		 * and would retain their original ref->count < 0.
		 */
1264
		if (roots && ref->count && ref->root_id && ref->parent == 0) {
1265 1266
			if (sc && sc->root_objectid &&
			    ref->root_id != sc->root_objectid) {
1267 1268 1269 1270
				ret = BACKREF_FOUND_SHARED;
				goto out;
			}

1271 1272
			/* no parent == root of tree */
			ret = ulist_add(roots, ref->root_id, 0, GFP_NOFS);
1273 1274
			if (ret < 0)
				goto out;
1275 1276
		}
		if (ref->count && ref->parent) {
1277 1278
			if (extent_item_pos && !ref->inode_list &&
			    ref->level == 0) {
1279
				struct extent_buffer *eb;
1280

1281 1282
				eb = read_tree_block(fs_info, ref->parent, 0,
						     ref->level, NULL);
1283 1284 1285 1286
				if (IS_ERR(eb)) {
					ret = PTR_ERR(eb);
					goto out;
				} else if (!extent_buffer_uptodate(eb)) {
1287
					free_extent_buffer(eb);
1288 1289
					ret = -EIO;
					goto out;
1290
				}
1291 1292 1293 1294
				if (!path->skip_locking) {
					btrfs_tree_read_lock(eb);
					btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
				}
1295
				ret = find_extent_in_eb(eb, bytenr,
1296
							*extent_item_pos, &eie, ignore_offset);
1297 1298
				if (!path->skip_locking)
					btrfs_tree_read_unlock_blocking(eb);
1299
				free_extent_buffer(eb);
1300 1301 1302
				if (ret < 0)
					goto out;
				ref->inode_list = eie;
1303
			}
1304 1305 1306
			ret = ulist_add_merge_ptr(refs, ref->parent,
						  ref->inode_list,
						  (void **)&eie, GFP_NOFS);
1307 1308
			if (ret < 0)
				goto out;
1309 1310 1311 1312 1313 1314 1315 1316 1317 1318
			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;
			}
1319
			eie = NULL;
1320
		}
1321
		cond_resched();
1322 1323 1324 1325
	}

out:
	btrfs_free_path(path);
1326 1327 1328 1329 1330

	prelim_release(&preftrees.direct);
	prelim_release(&preftrees.indirect);
	prelim_release(&preftrees.indirect_missing_keys);

1331 1332
	if (ret < 0)
		free_inode_elem_list(eie);
1333 1334 1335
	return ret;
}

1336 1337 1338 1339 1340 1341 1342 1343 1344 1345
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;
1346
		eie = unode_aux_to_inode_list(node);
1347
		free_inode_elem_list(eie);
1348 1349 1350 1351 1352 1353
		node->aux = 0;
	}

	ulist_free(blocks);
}

1354 1355 1356 1357 1358 1359 1360 1361 1362 1363
/*
 * 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,
1364
				u64 time_seq, struct ulist **leafs,
1365
				const u64 *extent_item_pos, bool ignore_offset)
1366 1367 1368 1369
{
	int ret;

	*leafs = ulist_alloc(GFP_NOFS);
1370
	if (!*leafs)
1371 1372
		return -ENOMEM;

1373
	ret = find_parent_nodes(trans, fs_info, bytenr, time_seq,
1374
				*leafs, NULL, extent_item_pos, NULL, ignore_offset);
1375
	if (ret < 0 && ret != -ENOENT) {
1376
		free_leaf_list(*leafs);
1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388 1389 1390 1391 1392 1393 1394 1395
		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.
 */
1396 1397
static int btrfs_find_all_roots_safe(struct btrfs_trans_handle *trans,
				     struct btrfs_fs_info *fs_info, u64 bytenr,
1398 1399
				     u64 time_seq, struct ulist **roots,
				     bool ignore_offset)
1400 1401 1402
{
	struct ulist *tmp;
	struct ulist_node *node = NULL;
J
Jan Schmidt 已提交
1403
	struct ulist_iterator uiter;
1404 1405 1406 1407 1408 1409 1410 1411 1412 1413 1414
	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 已提交
1415
	ULIST_ITER_INIT(&uiter);
1416
	while (1) {
1417
		ret = find_parent_nodes(trans, fs_info, bytenr, time_seq,
1418
					tmp, *roots, NULL, NULL, ignore_offset);
1419 1420 1421 1422 1423
		if (ret < 0 && ret != -ENOENT) {
			ulist_free(tmp);
			ulist_free(*roots);
			return ret;
		}
J
Jan Schmidt 已提交
1424
		node = ulist_next(tmp, &uiter);
1425 1426 1427
		if (!node)
			break;
		bytenr = node->val;
1428
		cond_resched();
1429 1430 1431 1432 1433 1434
	}

	ulist_free(tmp);
	return 0;
}

1435 1436
int btrfs_find_all_roots(struct btrfs_trans_handle *trans,
			 struct btrfs_fs_info *fs_info, u64 bytenr,
1437 1438
			 u64 time_seq, struct ulist **roots,
			 bool ignore_offset)
1439 1440 1441 1442 1443
{
	int ret;

	if (!trans)
		down_read(&fs_info->commit_root_sem);
1444
	ret = btrfs_find_all_roots_safe(trans, fs_info, bytenr,
1445
					time_seq, roots, ignore_offset);
1446 1447 1448 1449 1450
	if (!trans)
		up_read(&fs_info->commit_root_sem);
	return ret;
}

1451 1452 1453 1454 1455 1456 1457 1458 1459
/**
 * btrfs_check_shared - tell us whether an extent is shared
 *
 * 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.
 *
1460 1461
 * This attempts to attach to the running transaction in order to account for
 * delayed refs, but continues on even when no running transaction exists.
1462
 *
1463 1464
 * Return: 0 if extent is not shared, 1 if it is shared, < 0 on error.
 */
1465
int btrfs_check_shared(struct btrfs_root *root, u64 inum, u64 bytenr)
1466
{
1467 1468
	struct btrfs_fs_info *fs_info = root->fs_info;
	struct btrfs_trans_handle *trans;
1469 1470 1471 1472
	struct ulist *tmp = NULL;
	struct ulist *roots = NULL;
	struct ulist_iterator uiter;
	struct ulist_node *node;
1473
	struct seq_list elem = SEQ_LIST_INIT(elem);
1474
	int ret = 0;
1475 1476 1477 1478 1479
	struct share_check shared = {
		.root_objectid = root->objectid,
		.inum = inum,
		.share_count = 0,
	};
1480 1481 1482 1483

	tmp = ulist_alloc(GFP_NOFS);
	roots = ulist_alloc(GFP_NOFS);
	if (!tmp || !roots) {
1484 1485
		ret = -ENOMEM;
		goto out;
1486 1487
	}

1488
	trans = btrfs_join_transaction_nostart(root);
1489
	if (IS_ERR(trans)) {
1490 1491 1492 1493
		if (PTR_ERR(trans) != -ENOENT && PTR_ERR(trans) != -EROFS) {
			ret = PTR_ERR(trans);
			goto out;
		}
1494
		trans = NULL;
1495
		down_read(&fs_info->commit_root_sem);
1496 1497 1498 1499
	} else {
		btrfs_get_tree_mod_seq(fs_info, &elem);
	}

1500 1501 1502
	ULIST_ITER_INIT(&uiter);
	while (1) {
		ret = find_parent_nodes(trans, fs_info, bytenr, elem.seq, tmp,
1503
					roots, NULL, &shared, false);
1504
		if (ret == BACKREF_FOUND_SHARED) {
1505
			/* this is the only condition under which we return 1 */
1506 1507 1508 1509 1510
			ret = 1;
			break;
		}
		if (ret < 0 && ret != -ENOENT)
			break;
1511
		ret = 0;
1512 1513 1514 1515
		node = ulist_next(tmp, &uiter);
		if (!node)
			break;
		bytenr = node->val;
1516
		shared.share_count = 0;
1517 1518
		cond_resched();
	}
1519 1520

	if (trans) {
1521
		btrfs_put_tree_mod_seq(fs_info, &elem);
1522 1523
		btrfs_end_transaction(trans);
	} else {
1524
		up_read(&fs_info->commit_root_sem);
1525
	}
1526
out:
1527 1528 1529 1530 1531
	ulist_free(tmp);
	ulist_free(roots);
	return ret;
}

M
Mark Fasheh 已提交
1532 1533 1534 1535 1536 1537 1538 1539 1540
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;
1541
	const struct extent_buffer *leaf;
M
Mark Fasheh 已提交
1542 1543 1544
	unsigned long ptr;

	key.objectid = inode_objectid;
1545
	key.type = BTRFS_INODE_EXTREF_KEY;
M
Mark Fasheh 已提交
1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584
	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;
1585
		if (found_key.type != BTRFS_INODE_EXTREF_KEY)
M
Mark Fasheh 已提交
1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599
			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;
}

1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611 1612 1613
/*
 * 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!
 */
1614 1615 1616 1617
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)
1618 1619 1620 1621
{
	int slot;
	u64 next_inum;
	int ret;
1622
	s64 bytes_left = ((s64)size) - 1;
1623 1624
	struct extent_buffer *eb = eb_in;
	struct btrfs_key found_key;
1625
	int leave_spinning = path->leave_spinning;
M
Mark Fasheh 已提交
1626
	struct btrfs_inode_ref *iref;
1627 1628 1629 1630

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

1631
	path->leave_spinning = 1;
1632
	while (1) {
M
Mark Fasheh 已提交
1633
		bytes_left -= name_len;
1634 1635
		if (bytes_left >= 0)
			read_extent_buffer(eb, dest + bytes_left,
M
Mark Fasheh 已提交
1636
					   name_off, name_len);
1637
		if (eb != eb_in) {
1638 1639
			if (!path->skip_locking)
				btrfs_tree_read_unlock_blocking(eb);
1640
			free_extent_buffer(eb);
1641
		}
1642 1643
		ret = btrfs_find_item(fs_root, path, parent, 0,
				BTRFS_INODE_REF_KEY, &found_key);
1644 1645
		if (ret > 0)
			ret = -ENOENT;
1646 1647
		if (ret)
			break;
M
Mark Fasheh 已提交
1648

1649 1650 1651 1652 1653 1654 1655 1656 1657
		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 */
1658
		if (eb != eb_in) {
1659 1660 1661 1662
			if (!path->skip_locking)
				btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
			path->nodes[0] = NULL;
			path->locks[0] = 0;
1663
		}
1664 1665
		btrfs_release_path(path);
		iref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
M
Mark Fasheh 已提交
1666 1667 1668 1669

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

1670 1671 1672 1673 1674 1675 1676
		parent = next_inum;
		--bytes_left;
		if (bytes_left >= 0)
			dest[bytes_left] = '/';
	}

	btrfs_release_path(path);
1677
	path->leave_spinning = leave_spinning;
1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690

	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,
1691 1692
			struct btrfs_path *path, struct btrfs_key *found_key,
			u64 *flags_ret)
1693 1694 1695
{
	int ret;
	u64 flags;
1696
	u64 size = 0;
1697
	u32 item_size;
1698
	const struct extent_buffer *eb;
1699 1700 1701
	struct btrfs_extent_item *ei;
	struct btrfs_key key;

1702 1703 1704 1705
	if (btrfs_fs_incompat(fs_info, SKINNY_METADATA))
		key.type = BTRFS_METADATA_ITEM_KEY;
	else
		key.type = BTRFS_EXTENT_ITEM_KEY;
1706 1707 1708 1709 1710 1711 1712
	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;

1713 1714 1715 1716 1717
	ret = btrfs_previous_extent_item(fs_info->extent_root, path, 0);
	if (ret) {
		if (ret > 0)
			ret = -ENOENT;
		return ret;
1718
	}
1719
	btrfs_item_key_to_cpu(path->nodes[0], found_key, path->slots[0]);
1720
	if (found_key->type == BTRFS_METADATA_ITEM_KEY)
1721
		size = fs_info->nodesize;
1722 1723 1724
	else if (found_key->type == BTRFS_EXTENT_ITEM_KEY)
		size = found_key->offset;

1725
	if (found_key->objectid > logical ||
1726
	    found_key->objectid + size <= logical) {
1727 1728
		btrfs_debug(fs_info,
			"logical %llu is not within any extent", logical);
1729
		return -ENOENT;
J
Jan Schmidt 已提交
1730
	}
1731 1732 1733 1734 1735 1736 1737 1738

	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);

1739 1740
	btrfs_debug(fs_info,
		"logical %llu is at position %llu within the extent (%llu EXTENT_ITEM %llu) flags %#llx size %u",
1741 1742
		 logical, logical - found_key->objectid, found_key->objectid,
		 found_key->offset, flags, item_size);
1743 1744 1745 1746 1747 1748 1749 1750 1751 1752 1753

	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;
	}
1754 1755 1756 1757 1758 1759 1760 1761

	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
1762
 * get_extent_inline_ref must pass the modified ptr parameter to get the
1763 1764 1765
 * next ref. after the last ref was processed, 1 is returned.
 * returns <0 on error
 */
1766 1767 1768 1769 1770 1771 1772
static int get_extent_inline_ref(unsigned long *ptr,
				 const struct extent_buffer *eb,
				 const struct btrfs_key *key,
				 const struct btrfs_extent_item *ei,
				 u32 item_size,
				 struct btrfs_extent_inline_ref **out_eiref,
				 int *out_type)
1773 1774 1775 1776 1777 1778 1779 1780 1781
{
	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) {
1782 1783 1784 1785 1786 1787 1788 1789 1790 1791
			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);
			}
1792 1793 1794 1795
		} else {
			*out_eiref = (struct btrfs_extent_inline_ref *)(ei + 1);
		}
		*ptr = (unsigned long)*out_eiref;
1796
		if ((unsigned long)(*ptr) >= (unsigned long)ei + item_size)
1797 1798 1799 1800
			return -ENOENT;
	}

	end = (unsigned long)ei + item_size;
1801
	*out_eiref = (struct btrfs_extent_inline_ref *)(*ptr);
1802 1803 1804
	*out_type = btrfs_get_extent_inline_ref_type(eb, *out_eiref,
						     BTRFS_REF_TYPE_ANY);
	if (*out_type == BTRFS_REF_TYPE_INVALID)
1805
		return -EUCLEAN;
1806 1807 1808 1809 1810 1811 1812 1813 1814 1815 1816 1817

	*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
1818
 * call and may be modified (see get_extent_inline_ref comment).
1819 1820 1821 1822
 * 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,
1823 1824
			    struct btrfs_key *key, struct btrfs_extent_item *ei,
			    u32 item_size, u64 *out_root, u8 *out_level)
1825 1826 1827 1828 1829 1830 1831 1832 1833
{
	int ret;
	int type;
	struct btrfs_extent_inline_ref *eiref;

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

	while (1) {
1834
		ret = get_extent_inline_ref(ptr, eb, key, ei, item_size,
1835
					      &eiref, &type);
1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848
		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);
1849 1850 1851 1852 1853 1854 1855 1856 1857 1858

	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;
	}
1859 1860 1861 1862 1863 1864 1865

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

	return 0;
}

1866 1867 1868 1869
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)
1870
{
1871
	struct extent_inode_elem *eie;
J
Jan Schmidt 已提交
1872 1873
	int ret = 0;

1874
	for (eie = inode_list; eie; eie = eie->next) {
1875 1876 1877 1878
		btrfs_debug(fs_info,
			    "ref for %llu resolved, key (%llu EXTEND_DATA %llu), root %llu",
			    extent_item_objectid, eie->inum,
			    eie->offset, root);
1879
		ret = iterate(eie->inum, eie->offset, root, ctx);
J
Jan Schmidt 已提交
1880
		if (ret) {
1881 1882 1883
			btrfs_debug(fs_info,
				    "stopping iteration for %llu due to ret=%d",
				    extent_item_objectid, ret);
J
Jan Schmidt 已提交
1884 1885
			break;
		}
1886 1887 1888 1889 1890 1891 1892
	}

	return ret;
}

/*
 * calls iterate() for every inode that references the extent identified by
J
Jan Schmidt 已提交
1893
 * the given parameters.
1894 1895 1896
 * when the iterator function returns a non-zero value, iteration stops.
 */
int iterate_extent_inodes(struct btrfs_fs_info *fs_info,
J
Jan Schmidt 已提交
1897
				u64 extent_item_objectid, u64 extent_item_pos,
1898
				int search_commit_root,
1899 1900
				iterate_extent_inodes_t *iterate, void *ctx,
				bool ignore_offset)
1901 1902
{
	int ret;
1903
	struct btrfs_trans_handle *trans = NULL;
1904 1905
	struct ulist *refs = NULL;
	struct ulist *roots = NULL;
J
Jan Schmidt 已提交
1906 1907
	struct ulist_node *ref_node = NULL;
	struct ulist_node *root_node = NULL;
1908
	struct seq_list tree_mod_seq_elem = SEQ_LIST_INIT(tree_mod_seq_elem);
J
Jan Schmidt 已提交
1909 1910
	struct ulist_iterator ref_uiter;
	struct ulist_iterator root_uiter;
1911

1912
	btrfs_debug(fs_info, "resolving all inodes for extent %llu",
J
Jan Schmidt 已提交
1913
			extent_item_objectid);
1914

1915
	if (!search_commit_root) {
1916 1917 1918 1919 1920 1921 1922 1923 1924 1925
		trans = btrfs_attach_transaction(fs_info->extent_root);
		if (IS_ERR(trans)) {
			if (PTR_ERR(trans) != -ENOENT &&
			    PTR_ERR(trans) != -EROFS)
				return PTR_ERR(trans);
			trans = NULL;
		}
	}

	if (trans)
1926
		btrfs_get_tree_mod_seq(fs_info, &tree_mod_seq_elem);
1927
	else
1928
		down_read(&fs_info->commit_root_sem);
1929

J
Jan Schmidt 已提交
1930
	ret = btrfs_find_all_leafs(trans, fs_info, extent_item_objectid,
1931
				   tree_mod_seq_elem.seq, &refs,
1932
				   &extent_item_pos, ignore_offset);
J
Jan Schmidt 已提交
1933 1934
	if (ret)
		goto out;
1935

J
Jan Schmidt 已提交
1936 1937
	ULIST_ITER_INIT(&ref_uiter);
	while (!ret && (ref_node = ulist_next(refs, &ref_uiter))) {
1938
		ret = btrfs_find_all_roots_safe(trans, fs_info, ref_node->val,
1939 1940
						tree_mod_seq_elem.seq, &roots,
						ignore_offset);
J
Jan Schmidt 已提交
1941 1942
		if (ret)
			break;
J
Jan Schmidt 已提交
1943 1944
		ULIST_ITER_INIT(&root_uiter);
		while (!ret && (root_node = ulist_next(roots, &root_uiter))) {
1945 1946 1947 1948 1949 1950
			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 *)
1951 1952 1953 1954
						(uintptr_t)ref_node->aux,
						root_node->val,
						extent_item_objectid,
						iterate, ctx);
J
Jan Schmidt 已提交
1955
		}
1956
		ulist_free(roots);
1957 1958
	}

1959
	free_leaf_list(refs);
J
Jan Schmidt 已提交
1960
out:
1961
	if (trans) {
1962
		btrfs_put_tree_mod_seq(fs_info, &tree_mod_seq_elem);
1963
		btrfs_end_transaction(trans);
1964 1965
	} else {
		up_read(&fs_info->commit_root_sem);
1966 1967
	}

1968 1969 1970 1971 1972
	return ret;
}

int iterate_inodes_from_logical(u64 logical, struct btrfs_fs_info *fs_info,
				struct btrfs_path *path,
1973 1974
				iterate_extent_inodes_t *iterate, void *ctx,
				bool ignore_offset)
1975 1976
{
	int ret;
J
Jan Schmidt 已提交
1977
	u64 extent_item_pos;
1978
	u64 flags = 0;
1979
	struct btrfs_key found_key;
1980
	int search_commit_root = path->search_commit_root;
1981

1982
	ret = extent_from_logical(fs_info, logical, path, &found_key, &flags);
J
Jan Schmidt 已提交
1983
	btrfs_release_path(path);
1984 1985
	if (ret < 0)
		return ret;
1986
	if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)
1987
		return -EINVAL;
1988

J
Jan Schmidt 已提交
1989
	extent_item_pos = logical - found_key.objectid;
1990 1991
	ret = iterate_extent_inodes(fs_info, found_key.objectid,
					extent_item_pos, search_commit_root,
1992
					iterate, ctx, ignore_offset);
1993 1994 1995 1996

	return ret;
}

M
Mark Fasheh 已提交
1997 1998 1999 2000 2001 2002
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)
2003
{
2004
	int ret = 0;
2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015
	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;

2016
	while (!ret) {
2017 2018 2019 2020
		ret = btrfs_find_item(fs_root, path, inum,
				parent ? parent + 1 : 0, BTRFS_INODE_REF_KEY,
				&found_key);

2021 2022 2023 2024 2025 2026 2027 2028 2029 2030
		if (ret < 0)
			break;
		if (ret) {
			ret = found ? 0 : -ENOENT;
			break;
		}
		++found;

		parent = found_key.offset;
		slot = path->slots[0];
2031 2032 2033 2034 2035 2036
		eb = btrfs_clone_extent_buffer(path->nodes[0]);
		if (!eb) {
			ret = -ENOMEM;
			break;
		}
		extent_buffer_get(eb);
2037 2038
		btrfs_tree_read_lock(eb);
		btrfs_set_lock_blocking_rw(eb, BTRFS_READ_LOCK);
2039 2040
		btrfs_release_path(path);

2041
		item = btrfs_item_nr(slot);
2042 2043 2044 2045 2046
		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()! */
2047 2048 2049
			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 已提交
2050 2051
			ret = iterate(parent, name_len,
				      (unsigned long)(iref + 1), eb, ctx);
2052
			if (ret)
2053 2054 2055 2056
				break;
			len = sizeof(*iref) + name_len;
			iref = (struct btrfs_inode_ref *)((char *)iref + len);
		}
2057
		btrfs_tree_read_unlock_blocking(eb);
2058 2059 2060 2061 2062 2063 2064 2065
		free_extent_buffer(eb);
	}

	btrfs_release_path(path);

	return ret;
}

M
Mark Fasheh 已提交
2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092
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];
2093 2094 2095 2096 2097 2098
		eb = btrfs_clone_extent_buffer(path->nodes[0]);
		if (!eb) {
			ret = -ENOMEM;
			break;
		}
		extent_buffer_get(eb);
M
Mark Fasheh 已提交
2099 2100 2101 2102 2103

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

2104 2105
		item_size = btrfs_item_size_nr(eb, slot);
		ptr = btrfs_item_ptr_offset(eb, slot);
M
Mark Fasheh 已提交
2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118
		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;

2119
			cur_offset += btrfs_inode_extref_name_len(eb, extref);
M
Mark Fasheh 已提交
2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152
			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;
}

2153 2154 2155 2156
/*
 * returns 0 if the path could be dumped (probably truncated)
 * returns <0 in case of an error
 */
M
Mark Fasheh 已提交
2157 2158
static int inode_to_path(u64 inum, u32 name_len, unsigned long name_off,
			 struct extent_buffer *eb, void *ctx)
2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 2169
{
	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;

2170
	fspath_min = (char *)ipath->fspath->val + (i + 1) * s_ptr;
2171 2172
	fspath = btrfs_ref_to_path(ipath->fs_root, ipath->btrfs_path, name_len,
				   name_off, eb, inum, fspath_min, bytes_left);
2173 2174 2175 2176
	if (IS_ERR(fspath))
		return PTR_ERR(fspath);

	if (fspath > fspath_min) {
2177
		ipath->fspath->val[i] = (u64)(unsigned long)fspath;
2178 2179 2180 2181 2182 2183 2184 2185 2186 2187 2188 2189 2190 2191
		++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
2192
 * from ipath->fspath->val[i].
2193
 * when it returns, there are ipath->fspath->elem_cnt number of paths available
2194
 * in ipath->fspath->val[]. when the allocated space wasn't sufficient, the
2195
 * number of missed paths is recorded in ipath->fspath->elem_missed, otherwise,
2196 2197 2198 2199 2200 2201
 * 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 已提交
2202
			     inode_to_path, ipath);
2203 2204 2205 2206 2207 2208 2209 2210
}

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));
2211
	data = kvmalloc(alloc_bytes, GFP_KERNEL);
2212 2213 2214 2215 2216 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
	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))
2243
		return ERR_CAST(fspath);
2244

2245
	ifp = kmalloc(sizeof(*ifp), GFP_KERNEL);
2246
	if (!ifp) {
2247
		kvfree(fspath);
2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259
		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)
{
2260 2261
	if (!ipath)
		return;
2262
	kvfree(ipath->fspath);
2263 2264
	kfree(ipath);
}