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