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

#include <linux/sched.h>
#include <linux/pagemap.h>
#include <linux/writeback.h>
#include <linux/blkdev.h>
#include <linux/rbtree.h>
24
#include <linux/slab.h>
25 26 27 28 29 30 31
#include "ctree.h"
#include "disk-io.h"
#include "transaction.h"
#include "volumes.h"
#include "locking.h"
#include "btrfs_inode.h"
#include "async-thread.h"
32
#include "free-space-cache.h"
33
#include "inode-map.h"
34
#include "qgroup.h"
35 36 37 38 39 40 41 42 43 44 45 46 47 48 49

/*
 * backref_node, mapping_node and tree_block start with this
 */
struct tree_entry {
	struct rb_node rb_node;
	u64 bytenr;
};

/*
 * present a tree block in the backref cache
 */
struct backref_node {
	struct rb_node rb_node;
	u64 bytenr;
50 51 52

	u64 new_bytenr;
	/* objectid of tree block owner, can be not uptodate */
53
	u64 owner;
54 55
	/* link to pending, changed or detached list */
	struct list_head list;
56 57 58 59 60 61 62 63 64 65
	/* list of upper level blocks reference this block */
	struct list_head upper;
	/* list of child blocks in the cache */
	struct list_head lower;
	/* NULL if this node is not tree root */
	struct btrfs_root *root;
	/* extent buffer got by COW the block */
	struct extent_buffer *eb;
	/* level of tree block */
	unsigned int level:8;
66 67 68
	/* is the block in non-reference counted tree */
	unsigned int cowonly:1;
	/* 1 if no child node in the cache */
69 70 71 72 73 74 75
	unsigned int lowest:1;
	/* is the extent buffer locked */
	unsigned int locked:1;
	/* has the block been processed */
	unsigned int processed:1;
	/* have backrefs of this block been checked */
	unsigned int checked:1;
76 77 78 79 80 81 82 83 84 85
	/*
	 * 1 if corresponding block has been cowed but some upper
	 * level block pointers may not point to the new location
	 */
	unsigned int pending:1;
	/*
	 * 1 if the backref node isn't connected to any other
	 * backref node.
	 */
	unsigned int detached:1;
86 87 88 89 90 91 92 93 94 95 96 97
};

/*
 * present a block pointer in the backref cache
 */
struct backref_edge {
	struct list_head list[2];
	struct backref_node *node[2];
};

#define LOWER	0
#define UPPER	1
98
#define RELOCATION_RESERVED_NODES	256
99 100 101 102

struct backref_cache {
	/* red black tree of all backref nodes in the cache */
	struct rb_root rb_root;
103 104 105 106 107 108 109
	/* for passing backref nodes to btrfs_reloc_cow_block */
	struct backref_node *path[BTRFS_MAX_LEVEL];
	/*
	 * list of blocks that have been cowed but some block
	 * pointers in upper level blocks may not reflect the
	 * new location
	 */
110
	struct list_head pending[BTRFS_MAX_LEVEL];
111 112 113 114 115 116 117 118 119 120 121
	/* list of backref nodes with no child node */
	struct list_head leaves;
	/* list of blocks that have been cowed in current transaction */
	struct list_head changed;
	/* list of detached backref node. */
	struct list_head detached;

	u64 last_trans;

	int nr_nodes;
	int nr_edges;
122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148
};

/*
 * map address of tree root to tree
 */
struct mapping_node {
	struct rb_node rb_node;
	u64 bytenr;
	void *data;
};

struct mapping_tree {
	struct rb_root rb_root;
	spinlock_t lock;
};

/*
 * present a tree block to process
 */
struct tree_block {
	struct rb_node rb_node;
	u64 bytenr;
	struct btrfs_key key;
	unsigned int level:8;
	unsigned int key_ready:1;
};

149 150 151 152 153 154 155 156 157
#define MAX_EXTENTS 128

struct file_extent_cluster {
	u64 start;
	u64 end;
	u64 boundary[MAX_EXTENTS];
	unsigned int nr;
};

158 159 160 161 162 163 164
struct reloc_control {
	/* block group to relocate */
	struct btrfs_block_group_cache *block_group;
	/* extent tree */
	struct btrfs_root *extent_root;
	/* inode for moving data */
	struct inode *data_inode;
165 166 167 168 169 170

	struct btrfs_block_rsv *block_rsv;

	struct backref_cache backref_cache;

	struct file_extent_cluster cluster;
171 172 173 174 175 176
	/* tree blocks have been processed */
	struct extent_io_tree processed_blocks;
	/* map start of tree root to corresponding reloc tree */
	struct mapping_tree reloc_root_tree;
	/* list of reloc trees */
	struct list_head reloc_roots;
177 178 179 180
	/* size of metadata reservation for merging reloc trees */
	u64 merging_rsv_size;
	/* size of relocated tree nodes */
	u64 nodes_relocated;
181 182
	/* reserved size for block group relocation*/
	u64 reserved_bytes;
183

184 185
	u64 search_start;
	u64 extents_found;
186 187 188 189

	unsigned int stage:8;
	unsigned int create_reloc_tree:1;
	unsigned int merge_reloc_tree:1;
190 191 192 193 194 195 196
	unsigned int found_file_extent:1;
};

/* stages of data relocation */
#define MOVE_DATA_EXTENTS	0
#define UPDATE_DATA_PTRS	1

197 198 199 200
static void remove_backref_node(struct backref_cache *cache,
				struct backref_node *node);
static void __mark_block_processed(struct reloc_control *rc,
				   struct backref_node *node);
201 202 203

static void mapping_tree_init(struct mapping_tree *tree)
{
204
	tree->rb_root = RB_ROOT;
205 206 207 208 209 210
	spin_lock_init(&tree->lock);
}

static void backref_cache_init(struct backref_cache *cache)
{
	int i;
211
	cache->rb_root = RB_ROOT;
212 213
	for (i = 0; i < BTRFS_MAX_LEVEL; i++)
		INIT_LIST_HEAD(&cache->pending[i]);
214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238
	INIT_LIST_HEAD(&cache->changed);
	INIT_LIST_HEAD(&cache->detached);
	INIT_LIST_HEAD(&cache->leaves);
}

static void backref_cache_cleanup(struct backref_cache *cache)
{
	struct backref_node *node;
	int i;

	while (!list_empty(&cache->detached)) {
		node = list_entry(cache->detached.next,
				  struct backref_node, list);
		remove_backref_node(cache, node);
	}

	while (!list_empty(&cache->leaves)) {
		node = list_entry(cache->leaves.next,
				  struct backref_node, lower);
		remove_backref_node(cache, node);
	}

	cache->last_trans = 0;

	for (i = 0; i < BTRFS_MAX_LEVEL; i++)
239 240 241 242 243 244
		ASSERT(list_empty(&cache->pending[i]));
	ASSERT(list_empty(&cache->changed));
	ASSERT(list_empty(&cache->detached));
	ASSERT(RB_EMPTY_ROOT(&cache->rb_root));
	ASSERT(!cache->nr_nodes);
	ASSERT(!cache->nr_edges);
245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278
}

static struct backref_node *alloc_backref_node(struct backref_cache *cache)
{
	struct backref_node *node;

	node = kzalloc(sizeof(*node), GFP_NOFS);
	if (node) {
		INIT_LIST_HEAD(&node->list);
		INIT_LIST_HEAD(&node->upper);
		INIT_LIST_HEAD(&node->lower);
		RB_CLEAR_NODE(&node->rb_node);
		cache->nr_nodes++;
	}
	return node;
}

static void free_backref_node(struct backref_cache *cache,
			      struct backref_node *node)
{
	if (node) {
		cache->nr_nodes--;
		kfree(node);
	}
}

static struct backref_edge *alloc_backref_edge(struct backref_cache *cache)
{
	struct backref_edge *edge;

	edge = kzalloc(sizeof(*edge), GFP_NOFS);
	if (edge)
		cache->nr_edges++;
	return edge;
279 280
}

281 282
static void free_backref_edge(struct backref_cache *cache,
			      struct backref_edge *edge)
283
{
284 285 286 287
	if (edge) {
		cache->nr_edges--;
		kfree(edge);
	}
288 289 290 291 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 326 327 328 329 330 331
}

static struct rb_node *tree_insert(struct rb_root *root, u64 bytenr,
				   struct rb_node *node)
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *parent = NULL;
	struct tree_entry *entry;

	while (*p) {
		parent = *p;
		entry = rb_entry(parent, struct tree_entry, rb_node);

		if (bytenr < entry->bytenr)
			p = &(*p)->rb_left;
		else if (bytenr > entry->bytenr)
			p = &(*p)->rb_right;
		else
			return parent;
	}

	rb_link_node(node, parent, p);
	rb_insert_color(node, root);
	return NULL;
}

static struct rb_node *tree_search(struct rb_root *root, u64 bytenr)
{
	struct rb_node *n = root->rb_node;
	struct tree_entry *entry;

	while (n) {
		entry = rb_entry(n, struct tree_entry, rb_node);

		if (bytenr < entry->bytenr)
			n = n->rb_left;
		else if (bytenr > entry->bytenr)
			n = n->rb_right;
		else
			return n;
	}
	return NULL;
}

332
static void backref_tree_panic(struct rb_node *rb_node, int errno, u64 bytenr)
333 334 335 336 337 338 339
{

	struct btrfs_fs_info *fs_info = NULL;
	struct backref_node *bnode = rb_entry(rb_node, struct backref_node,
					      rb_node);
	if (bnode->root)
		fs_info = bnode->root->fs_info;
J
Jeff Mahoney 已提交
340 341 342
	btrfs_panic(fs_info, errno,
		    "Inconsistency in backref cache found at offset %llu",
		    bytenr);
343 344
}

345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360
/*
 * walk up backref nodes until reach node presents tree root
 */
static struct backref_node *walk_up_backref(struct backref_node *node,
					    struct backref_edge *edges[],
					    int *index)
{
	struct backref_edge *edge;
	int idx = *index;

	while (!list_empty(&node->upper)) {
		edge = list_entry(node->upper.next,
				  struct backref_edge, list[LOWER]);
		edges[idx++] = edge;
		node = edge->node[UPPER];
	}
361
	BUG_ON(node->detached);
362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392
	*index = idx;
	return node;
}

/*
 * walk down backref nodes to find start of next reference path
 */
static struct backref_node *walk_down_backref(struct backref_edge *edges[],
					      int *index)
{
	struct backref_edge *edge;
	struct backref_node *lower;
	int idx = *index;

	while (idx > 0) {
		edge = edges[idx - 1];
		lower = edge->node[LOWER];
		if (list_is_last(&edge->list[LOWER], &lower->upper)) {
			idx--;
			continue;
		}
		edge = list_entry(edge->list[LOWER].next,
				  struct backref_edge, list[LOWER]);
		edges[idx - 1] = edge;
		*index = idx;
		return edge->node[UPPER];
	}
	*index = 0;
	return NULL;
}

393 394 395 396 397 398 399 400
static void unlock_node_buffer(struct backref_node *node)
{
	if (node->locked) {
		btrfs_tree_unlock(node->eb);
		node->locked = 0;
	}
}

401 402 403
static void drop_node_buffer(struct backref_node *node)
{
	if (node->eb) {
404
		unlock_node_buffer(node);
405 406 407 408 409 410 411 412 413 414 415
		free_extent_buffer(node->eb);
		node->eb = NULL;
	}
}

static void drop_backref_node(struct backref_cache *tree,
			      struct backref_node *node)
{
	BUG_ON(!list_empty(&node->upper));

	drop_node_buffer(node);
416
	list_del(&node->list);
417
	list_del(&node->lower);
418 419 420
	if (!RB_EMPTY_NODE(&node->rb_node))
		rb_erase(&node->rb_node, &tree->rb_root);
	free_backref_node(tree, node);
421 422 423 424 425 426 427 428 429 430 431 432 433 434
}

/*
 * remove a backref node from the backref cache
 */
static void remove_backref_node(struct backref_cache *cache,
				struct backref_node *node)
{
	struct backref_node *upper;
	struct backref_edge *edge;

	if (!node)
		return;

435
	BUG_ON(!node->lowest && !node->detached);
436 437 438 439 440 441
	while (!list_empty(&node->upper)) {
		edge = list_entry(node->upper.next, struct backref_edge,
				  list[LOWER]);
		upper = edge->node[UPPER];
		list_del(&edge->list[LOWER]);
		list_del(&edge->list[UPPER]);
442 443 444 445 446 447 448 449 450
		free_backref_edge(cache, edge);

		if (RB_EMPTY_NODE(&upper->rb_node)) {
			BUG_ON(!list_empty(&node->upper));
			drop_backref_node(cache, node);
			node = upper;
			node->lowest = 1;
			continue;
		}
451
		/*
452
		 * add the node to leaf node list if no other
453 454 455
		 * child block cached.
		 */
		if (list_empty(&upper->lower)) {
456
			list_add_tail(&upper->lower, &cache->leaves);
457 458 459
			upper->lowest = 1;
		}
	}
460

461 462 463
	drop_backref_node(cache, node);
}

464 465 466 467 468 469 470
static void update_backref_node(struct backref_cache *cache,
				struct backref_node *node, u64 bytenr)
{
	struct rb_node *rb_node;
	rb_erase(&node->rb_node, &cache->rb_root);
	node->bytenr = bytenr;
	rb_node = tree_insert(&cache->rb_root, node->bytenr, &node->rb_node);
471 472
	if (rb_node)
		backref_tree_panic(rb_node, -EEXIST, bytenr);
473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527
}

/*
 * update backref cache after a transaction commit
 */
static int update_backref_cache(struct btrfs_trans_handle *trans,
				struct backref_cache *cache)
{
	struct backref_node *node;
	int level = 0;

	if (cache->last_trans == 0) {
		cache->last_trans = trans->transid;
		return 0;
	}

	if (cache->last_trans == trans->transid)
		return 0;

	/*
	 * detached nodes are used to avoid unnecessary backref
	 * lookup. transaction commit changes the extent tree.
	 * so the detached nodes are no longer useful.
	 */
	while (!list_empty(&cache->detached)) {
		node = list_entry(cache->detached.next,
				  struct backref_node, list);
		remove_backref_node(cache, node);
	}

	while (!list_empty(&cache->changed)) {
		node = list_entry(cache->changed.next,
				  struct backref_node, list);
		list_del_init(&node->list);
		BUG_ON(node->pending);
		update_backref_node(cache, node, node->new_bytenr);
	}

	/*
	 * some nodes can be left in the pending list if there were
	 * errors during processing the pending nodes.
	 */
	for (level = 0; level < BTRFS_MAX_LEVEL; level++) {
		list_for_each_entry(node, &cache->pending[level], list) {
			BUG_ON(!node->pending);
			if (node->bytenr == node->new_bytenr)
				continue;
			update_backref_node(cache, node, node->new_bytenr);
		}
	}

	cache->last_trans = 0;
	return 1;
}

528

529 530 531 532
static int should_ignore_root(struct btrfs_root *root)
{
	struct btrfs_root *reloc_root;

533
	if (!test_bit(BTRFS_ROOT_REF_COWS, &root->state))
534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550
		return 0;

	reloc_root = root->reloc_root;
	if (!reloc_root)
		return 0;

	if (btrfs_root_last_snapshot(&reloc_root->root_item) ==
	    root->fs_info->running_transaction->transid - 1)
		return 0;
	/*
	 * if there is reloc tree and it was created in previous
	 * transaction backref lookup can find the reloc tree,
	 * so backref node for the fs tree root is useless for
	 * relocation.
	 */
	return 1;
}
551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577
/*
 * find reloc tree by address of tree root
 */
static struct btrfs_root *find_reloc_root(struct reloc_control *rc,
					  u64 bytenr)
{
	struct rb_node *rb_node;
	struct mapping_node *node;
	struct btrfs_root *root = NULL;

	spin_lock(&rc->reloc_root_tree.lock);
	rb_node = tree_search(&rc->reloc_root_tree.rb_root, bytenr);
	if (rb_node) {
		node = rb_entry(rb_node, struct mapping_node, rb_node);
		root = (struct btrfs_root *)node->data;
	}
	spin_unlock(&rc->reloc_root_tree.lock);
	return root;
}

static int is_cowonly_root(u64 root_objectid)
{
	if (root_objectid == BTRFS_ROOT_TREE_OBJECTID ||
	    root_objectid == BTRFS_EXTENT_TREE_OBJECTID ||
	    root_objectid == BTRFS_CHUNK_TREE_OBJECTID ||
	    root_objectid == BTRFS_DEV_TREE_OBJECTID ||
	    root_objectid == BTRFS_TREE_LOG_OBJECTID ||
578 579
	    root_objectid == BTRFS_CSUM_TREE_OBJECTID ||
	    root_objectid == BTRFS_UUID_TREE_OBJECTID ||
580 581
	    root_objectid == BTRFS_QUOTA_TREE_OBJECTID ||
	    root_objectid == BTRFS_FREE_SPACE_TREE_OBJECTID)
582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597
		return 1;
	return 0;
}

static struct btrfs_root *read_fs_root(struct btrfs_fs_info *fs_info,
					u64 root_objectid)
{
	struct btrfs_key key;

	key.objectid = root_objectid;
	key.type = BTRFS_ROOT_ITEM_KEY;
	if (is_cowonly_root(root_objectid))
		key.offset = 0;
	else
		key.offset = (u64)-1;

598
	return btrfs_get_fs_root(fs_info, &key, false);
599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615
}

#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
static noinline_for_stack
struct btrfs_root *find_tree_root(struct reloc_control *rc,
				  struct extent_buffer *leaf,
				  struct btrfs_extent_ref_v0 *ref0)
{
	struct btrfs_root *root;
	u64 root_objectid = btrfs_ref_root_v0(leaf, ref0);
	u64 generation = btrfs_ref_generation_v0(leaf, ref0);

	BUG_ON(root_objectid == BTRFS_TREE_RELOC_OBJECTID);

	root = read_fs_root(rc->extent_root->fs_info, root_objectid);
	BUG_ON(IS_ERR(root));

616
	if (test_bit(BTRFS_ROOT_REF_COWS, &root->state) &&
617 618 619 620 621 622 623 624 625 626 627
	    generation != btrfs_root_generation(&root->root_item))
		return NULL;

	return root;
}
#endif

static noinline_for_stack
int find_inline_backref(struct extent_buffer *leaf, int slot,
			unsigned long *ptr, unsigned long *end)
{
628
	struct btrfs_key key;
629 630 631 632
	struct btrfs_extent_item *ei;
	struct btrfs_tree_block_info *bi;
	u32 item_size;

633 634
	btrfs_item_key_to_cpu(leaf, &key, slot);

635 636 637 638 639 640 641 642 643 644 645
	item_size = btrfs_item_size_nr(leaf, slot);
#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
	if (item_size < sizeof(*ei)) {
		WARN_ON(item_size != sizeof(struct btrfs_extent_item_v0));
		return 1;
	}
#endif
	ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
	WARN_ON(!(btrfs_extent_flags(leaf, ei) &
		  BTRFS_EXTENT_FLAG_TREE_BLOCK));

646 647
	if (key.type == BTRFS_EXTENT_ITEM_KEY &&
	    item_size <= sizeof(*ei) + sizeof(*bi)) {
648 649 650
		WARN_ON(item_size < sizeof(*ei) + sizeof(*bi));
		return 1;
	}
651 652 653 654 655
	if (key.type == BTRFS_METADATA_ITEM_KEY &&
	    item_size <= sizeof(*ei)) {
		WARN_ON(item_size < sizeof(*ei));
		return 1;
	}
656

657 658 659 660 661 662
	if (key.type == BTRFS_EXTENT_ITEM_KEY) {
		bi = (struct btrfs_tree_block_info *)(ei + 1);
		*ptr = (unsigned long)(bi + 1);
	} else {
		*ptr = (unsigned long)(ei + 1);
	}
663 664 665 666 667 668 669 670 671 672
	*end = (unsigned long)ei + item_size;
	return 0;
}

/*
 * build backref tree for a given tree block. root of the backref tree
 * corresponds the tree block, leaves of the backref tree correspond
 * roots of b-trees that reference the tree block.
 *
 * the basic idea of this function is check backrefs of a given block
673 674
 * to find upper level blocks that reference the block, and then check
 * backrefs of these upper level blocks recursively. the recursion stop
675 676 677 678 679 680
 * when tree root is reached or backrefs for the block is cached.
 *
 * NOTE: if we find backrefs for a block are cached, we know backrefs
 * for all upper level blocks that directly/indirectly reference the
 * block are also cached.
 */
681 682 683 684
static noinline_for_stack
struct backref_node *build_backref_tree(struct reloc_control *rc,
					struct btrfs_key *node_key,
					int level, u64 bytenr)
685
{
686
	struct backref_cache *cache = &rc->backref_cache;
687 688 689 690 691 692 693 694 695 696 697 698 699 700 701
	struct btrfs_path *path1;
	struct btrfs_path *path2;
	struct extent_buffer *eb;
	struct btrfs_root *root;
	struct backref_node *cur;
	struct backref_node *upper;
	struct backref_node *lower;
	struct backref_node *node = NULL;
	struct backref_node *exist = NULL;
	struct backref_edge *edge;
	struct rb_node *rb_node;
	struct btrfs_key key;
	unsigned long end;
	unsigned long ptr;
	LIST_HEAD(list);
702 703
	LIST_HEAD(useless);
	int cowonly;
704 705
	int ret;
	int err = 0;
706
	bool need_check = true;
707 708 709 710 711 712 713

	path1 = btrfs_alloc_path();
	path2 = btrfs_alloc_path();
	if (!path1 || !path2) {
		err = -ENOMEM;
		goto out;
	}
714 715
	path1->reada = READA_FORWARD;
	path2->reada = READA_FORWARD;
716

717
	node = alloc_backref_node(cache);
718 719 720 721 722 723 724 725 726 727 728 729 730
	if (!node) {
		err = -ENOMEM;
		goto out;
	}

	node->bytenr = bytenr;
	node->level = level;
	node->lowest = 1;
	cur = node;
again:
	end = 0;
	ptr = 0;
	key.objectid = cur->bytenr;
731
	key.type = BTRFS_METADATA_ITEM_KEY;
732 733 734 735 736 737 738 739 740 741
	key.offset = (u64)-1;

	path1->search_commit_root = 1;
	path1->skip_locking = 1;
	ret = btrfs_search_slot(NULL, rc->extent_root, &key, path1,
				0, 0);
	if (ret < 0) {
		err = ret;
		goto out;
	}
742 743
	ASSERT(ret);
	ASSERT(path1->slots[0]);
744 745 746 747 748 749

	path1->slots[0]--;

	WARN_ON(cur->checked);
	if (!list_empty(&cur->upper)) {
		/*
750
		 * the backref was added previously when processing
751 752
		 * backref of type BTRFS_TREE_BLOCK_REF_KEY
		 */
753
		ASSERT(list_is_singular(&cur->upper));
754 755
		edge = list_entry(cur->upper.next, struct backref_edge,
				  list[LOWER]);
756
		ASSERT(list_empty(&edge->list[UPPER]));
757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789
		exist = edge->node[UPPER];
		/*
		 * add the upper level block to pending list if we need
		 * check its backrefs
		 */
		if (!exist->checked)
			list_add_tail(&edge->list[UPPER], &list);
	} else {
		exist = NULL;
	}

	while (1) {
		cond_resched();
		eb = path1->nodes[0];

		if (ptr >= end) {
			if (path1->slots[0] >= btrfs_header_nritems(eb)) {
				ret = btrfs_next_leaf(rc->extent_root, path1);
				if (ret < 0) {
					err = ret;
					goto out;
				}
				if (ret > 0)
					break;
				eb = path1->nodes[0];
			}

			btrfs_item_key_to_cpu(eb, &key, path1->slots[0]);
			if (key.objectid != cur->bytenr) {
				WARN_ON(exist);
				break;
			}

790 791
			if (key.type == BTRFS_EXTENT_ITEM_KEY ||
			    key.type == BTRFS_METADATA_ITEM_KEY) {
792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820
				ret = find_inline_backref(eb, path1->slots[0],
							  &ptr, &end);
				if (ret)
					goto next;
			}
		}

		if (ptr < end) {
			/* update key for inline back ref */
			struct btrfs_extent_inline_ref *iref;
			iref = (struct btrfs_extent_inline_ref *)ptr;
			key.type = btrfs_extent_inline_ref_type(eb, iref);
			key.offset = btrfs_extent_inline_ref_offset(eb, iref);
			WARN_ON(key.type != BTRFS_TREE_BLOCK_REF_KEY &&
				key.type != BTRFS_SHARED_BLOCK_REF_KEY);
		}

		if (exist &&
		    ((key.type == BTRFS_TREE_BLOCK_REF_KEY &&
		      exist->owner == key.offset) ||
		     (key.type == BTRFS_SHARED_BLOCK_REF_KEY &&
		      exist->bytenr == key.offset))) {
			exist = NULL;
			goto next;
		}

#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
		if (key.type == BTRFS_SHARED_BLOCK_REF_KEY ||
		    key.type == BTRFS_EXTENT_REF_V0_KEY) {
821
			if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
822 823 824
				struct btrfs_extent_ref_v0 *ref0;
				ref0 = btrfs_item_ptr(eb, path1->slots[0],
						struct btrfs_extent_ref_v0);
825
				if (key.objectid == key.offset) {
826
					root = find_tree_root(rc, eb, ref0);
827 828 829 830 831 832
					if (root && !should_ignore_root(root))
						cur->root = root;
					else
						list_add(&cur->list, &useless);
					break;
				}
833 834 835
				if (is_cowonly_root(btrfs_ref_root_v0(eb,
								      ref0)))
					cur->cowonly = 1;
836 837
			}
#else
838
		ASSERT(key.type != BTRFS_EXTENT_REF_V0_KEY);
839 840 841 842 843 844 845 846
		if (key.type == BTRFS_SHARED_BLOCK_REF_KEY) {
#endif
			if (key.objectid == key.offset) {
				/*
				 * only root blocks of reloc trees use
				 * backref of this type.
				 */
				root = find_reloc_root(rc, cur->bytenr);
847
				ASSERT(root);
848 849 850 851
				cur->root = root;
				break;
			}

852
			edge = alloc_backref_edge(cache);
853 854 855 856 857 858
			if (!edge) {
				err = -ENOMEM;
				goto out;
			}
			rb_node = tree_search(&cache->rb_root, key.offset);
			if (!rb_node) {
859
				upper = alloc_backref_node(cache);
860
				if (!upper) {
861
					free_backref_edge(cache, edge);
862 863 864 865 866 867 868 869 870 871 872 873 874
					err = -ENOMEM;
					goto out;
				}
				upper->bytenr = key.offset;
				upper->level = cur->level + 1;
				/*
				 *  backrefs for the upper level block isn't
				 *  cached, add the block to pending list
				 */
				list_add_tail(&edge->list[UPPER], &list);
			} else {
				upper = rb_entry(rb_node, struct backref_node,
						 rb_node);
875
				ASSERT(upper->checked);
876 877
				INIT_LIST_HEAD(&edge->list[UPPER]);
			}
878
			list_add_tail(&edge->list[LOWER], &cur->upper);
879
			edge->node[LOWER] = cur;
880
			edge->node[UPPER] = upper;
881 882 883 884 885 886 887 888 889 890 891 892 893

			goto next;
		} else if (key.type != BTRFS_TREE_BLOCK_REF_KEY) {
			goto next;
		}

		/* key.type == BTRFS_TREE_BLOCK_REF_KEY */
		root = read_fs_root(rc->extent_root->fs_info, key.offset);
		if (IS_ERR(root)) {
			err = PTR_ERR(root);
			goto out;
		}

894
		if (!test_bit(BTRFS_ROOT_REF_COWS, &root->state))
895 896
			cur->cowonly = 1;

897 898
		if (btrfs_root_level(&root->root_item) == cur->level) {
			/* tree root */
899
			ASSERT(btrfs_root_bytenr(&root->root_item) ==
900
			       cur->bytenr);
901 902 903 904
			if (should_ignore_root(root))
				list_add(&cur->list, &useless);
			else
				cur->root = root;
905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922
			break;
		}

		level = cur->level + 1;

		/*
		 * searching the tree to find upper level blocks
		 * reference the block.
		 */
		path2->search_commit_root = 1;
		path2->skip_locking = 1;
		path2->lowest_level = level;
		ret = btrfs_search_slot(NULL, root, node_key, path2, 0, 0);
		path2->lowest_level = 0;
		if (ret < 0) {
			err = ret;
			goto out;
		}
923 924
		if (ret > 0 && path2->slots[level] > 0)
			path2->slots[level]--;
925 926

		eb = path2->nodes[level];
927 928 929 930 931 932 933 934 935 936
		if (btrfs_node_blockptr(eb, path2->slots[level]) !=
		    cur->bytenr) {
			btrfs_err(root->fs_info,
	"couldn't find block (%llu) (level %d) in tree (%llu) with key (%llu %u %llu)",
				  cur->bytenr, level - 1, root->objectid,
				  node_key->objectid, node_key->type,
				  node_key->offset);
			err = -ENOENT;
			goto out;
		}
937
		lower = cur;
938
		need_check = true;
939 940
		for (; level < BTRFS_MAX_LEVEL; level++) {
			if (!path2->nodes[level]) {
941
				ASSERT(btrfs_root_bytenr(&root->root_item) ==
942
				       lower->bytenr);
943 944 945 946
				if (should_ignore_root(root))
					list_add(&lower->list, &useless);
				else
					lower->root = root;
947 948 949
				break;
			}

950
			edge = alloc_backref_edge(cache);
951 952 953 954 955 956 957 958
			if (!edge) {
				err = -ENOMEM;
				goto out;
			}

			eb = path2->nodes[level];
			rb_node = tree_search(&cache->rb_root, eb->start);
			if (!rb_node) {
959
				upper = alloc_backref_node(cache);
960
				if (!upper) {
961
					free_backref_edge(cache, edge);
962 963 964 965 966 967
					err = -ENOMEM;
					goto out;
				}
				upper->bytenr = eb->start;
				upper->owner = btrfs_header_owner(eb);
				upper->level = lower->level + 1;
968 969
				if (!test_bit(BTRFS_ROOT_REF_COWS,
					      &root->state))
970
					upper->cowonly = 1;
971 972 973 974 975 976 977 978 979 980 981 982

				/*
				 * if we know the block isn't shared
				 * we can void checking its backrefs.
				 */
				if (btrfs_block_can_be_shared(root, eb))
					upper->checked = 0;
				else
					upper->checked = 1;

				/*
				 * add the block to pending list if we
983 984 985
				 * need check its backrefs, we only do this once
				 * while walking up a tree as we will catch
				 * anything else later on.
986
				 */
987 988
				if (!upper->checked && need_check) {
					need_check = false;
989 990
					list_add_tail(&edge->list[UPPER],
						      &list);
991 992 993
				} else {
					if (upper->checked)
						need_check = true;
994
					INIT_LIST_HEAD(&edge->list[UPPER]);
995
				}
996 997 998
			} else {
				upper = rb_entry(rb_node, struct backref_node,
						 rb_node);
999
				ASSERT(upper->checked);
1000
				INIT_LIST_HEAD(&edge->list[UPPER]);
1001 1002
				if (!upper->owner)
					upper->owner = btrfs_header_owner(eb);
1003 1004 1005
			}
			list_add_tail(&edge->list[LOWER], &lower->upper);
			edge->node[LOWER] = lower;
1006
			edge->node[UPPER] = upper;
1007 1008 1009 1010 1011 1012

			if (rb_node)
				break;
			lower = upper;
			upper = NULL;
		}
1013
		btrfs_release_path(path2);
1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025
next:
		if (ptr < end) {
			ptr += btrfs_extent_inline_ref_size(key.type);
			if (ptr >= end) {
				WARN_ON(ptr > end);
				ptr = 0;
				end = 0;
			}
		}
		if (ptr >= end)
			path1->slots[0]++;
	}
1026
	btrfs_release_path(path1);
1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042

	cur->checked = 1;
	WARN_ON(exist);

	/* the pending list isn't empty, take the first block to process */
	if (!list_empty(&list)) {
		edge = list_entry(list.next, struct backref_edge, list[UPPER]);
		list_del_init(&edge->list[UPPER]);
		cur = edge->node[UPPER];
		goto again;
	}

	/*
	 * everything goes well, connect backref nodes and insert backref nodes
	 * into the cache.
	 */
1043
	ASSERT(node->checked);
1044 1045 1046 1047
	cowonly = node->cowonly;
	if (!cowonly) {
		rb_node = tree_insert(&cache->rb_root, node->bytenr,
				      &node->rb_node);
1048 1049
		if (rb_node)
			backref_tree_panic(rb_node, -EEXIST, node->bytenr);
1050 1051
		list_add_tail(&node->lower, &cache->leaves);
	}
1052 1053 1054 1055 1056 1057 1058 1059

	list_for_each_entry(edge, &node->upper, list[LOWER])
		list_add_tail(&edge->list[UPPER], &list);

	while (!list_empty(&list)) {
		edge = list_entry(list.next, struct backref_edge, list[UPPER]);
		list_del_init(&edge->list[UPPER]);
		upper = edge->node[UPPER];
1060 1061 1062 1063 1064 1065 1066 1067
		if (upper->detached) {
			list_del(&edge->list[LOWER]);
			lower = edge->node[LOWER];
			free_backref_edge(cache, edge);
			if (list_empty(&lower->upper))
				list_add(&lower->list, &useless);
			continue;
		}
1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078

		if (!RB_EMPTY_NODE(&upper->rb_node)) {
			if (upper->lowest) {
				list_del_init(&upper->lower);
				upper->lowest = 0;
			}

			list_add_tail(&edge->list[UPPER], &upper->lower);
			continue;
		}

1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093
		if (!upper->checked) {
			/*
			 * Still want to blow up for developers since this is a
			 * logic bug.
			 */
			ASSERT(0);
			err = -EINVAL;
			goto out;
		}
		if (cowonly != upper->cowonly) {
			ASSERT(0);
			err = -EINVAL;
			goto out;
		}

1094 1095 1096
		if (!cowonly) {
			rb_node = tree_insert(&cache->rb_root, upper->bytenr,
					      &upper->rb_node);
1097 1098 1099
			if (rb_node)
				backref_tree_panic(rb_node, -EEXIST,
						   upper->bytenr);
1100
		}
1101 1102 1103 1104 1105 1106

		list_add_tail(&edge->list[UPPER], &upper->lower);

		list_for_each_entry(edge, &upper->upper, list[LOWER])
			list_add_tail(&edge->list[UPPER], &list);
	}
1107 1108 1109 1110 1111 1112 1113 1114 1115
	/*
	 * process useless backref nodes. backref nodes for tree leaves
	 * are deleted from the cache. backref nodes for upper level
	 * tree blocks are left in the cache to avoid unnecessary backref
	 * lookup.
	 */
	while (!list_empty(&useless)) {
		upper = list_entry(useless.next, struct backref_node, list);
		list_del_init(&upper->list);
1116
		ASSERT(list_empty(&upper->upper));
1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142
		if (upper == node)
			node = NULL;
		if (upper->lowest) {
			list_del_init(&upper->lower);
			upper->lowest = 0;
		}
		while (!list_empty(&upper->lower)) {
			edge = list_entry(upper->lower.next,
					  struct backref_edge, list[UPPER]);
			list_del(&edge->list[UPPER]);
			list_del(&edge->list[LOWER]);
			lower = edge->node[LOWER];
			free_backref_edge(cache, edge);

			if (list_empty(&lower->upper))
				list_add(&lower->list, &useless);
		}
		__mark_block_processed(rc, upper);
		if (upper->level > 0) {
			list_add(&upper->list, &cache->detached);
			upper->detached = 1;
		} else {
			rb_erase(&upper->rb_node, &cache->rb_root);
			free_backref_node(cache, upper);
		}
	}
1143 1144 1145 1146
out:
	btrfs_free_path(path1);
	btrfs_free_path(path2);
	if (err) {
1147 1148
		while (!list_empty(&useless)) {
			lower = list_entry(useless.next,
1149 1150
					   struct backref_node, list);
			list_del_init(&lower->list);
1151
		}
1152 1153 1154 1155
		while (!list_empty(&list)) {
			edge = list_first_entry(&list, struct backref_edge,
						list[UPPER]);
			list_del(&edge->list[UPPER]);
1156
			list_del(&edge->list[LOWER]);
1157
			lower = edge->node[LOWER];
1158
			upper = edge->node[UPPER];
1159
			free_backref_edge(cache, edge);
1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171

			/*
			 * Lower is no longer linked to any upper backref nodes
			 * and isn't in the cache, we can free it ourselves.
			 */
			if (list_empty(&lower->upper) &&
			    RB_EMPTY_NODE(&lower->rb_node))
				list_add(&lower->list, &useless);

			if (!RB_EMPTY_NODE(&upper->rb_node))
				continue;

1172
			/* Add this guy's upper edges to the list to process */
1173 1174 1175 1176 1177 1178 1179 1180 1181 1182
			list_for_each_entry(edge, &upper->upper, list[LOWER])
				list_add_tail(&edge->list[UPPER], &list);
			if (list_empty(&upper->upper))
				list_add(&upper->list, &useless);
		}

		while (!list_empty(&useless)) {
			lower = list_entry(useless.next,
					   struct backref_node, list);
			list_del_init(&lower->list);
L
Liu Bo 已提交
1183 1184
			if (lower == node)
				node = NULL;
1185
			free_backref_node(cache, lower);
1186
		}
L
Liu Bo 已提交
1187 1188

		free_backref_node(cache, node);
1189 1190
		return ERR_PTR(err);
	}
1191
	ASSERT(!node || !node->detached);
1192 1193 1194
	return node;
}

1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244
/*
 * helper to add backref node for the newly created snapshot.
 * the backref node is created by cloning backref node that
 * corresponds to root of source tree
 */
static int clone_backref_node(struct btrfs_trans_handle *trans,
			      struct reloc_control *rc,
			      struct btrfs_root *src,
			      struct btrfs_root *dest)
{
	struct btrfs_root *reloc_root = src->reloc_root;
	struct backref_cache *cache = &rc->backref_cache;
	struct backref_node *node = NULL;
	struct backref_node *new_node;
	struct backref_edge *edge;
	struct backref_edge *new_edge;
	struct rb_node *rb_node;

	if (cache->last_trans > 0)
		update_backref_cache(trans, cache);

	rb_node = tree_search(&cache->rb_root, src->commit_root->start);
	if (rb_node) {
		node = rb_entry(rb_node, struct backref_node, rb_node);
		if (node->detached)
			node = NULL;
		else
			BUG_ON(node->new_bytenr != reloc_root->node->start);
	}

	if (!node) {
		rb_node = tree_search(&cache->rb_root,
				      reloc_root->commit_root->start);
		if (rb_node) {
			node = rb_entry(rb_node, struct backref_node,
					rb_node);
			BUG_ON(node->detached);
		}
	}

	if (!node)
		return 0;

	new_node = alloc_backref_node(cache);
	if (!new_node)
		return -ENOMEM;

	new_node->bytenr = dest->node->start;
	new_node->level = node->level;
	new_node->lowest = node->lowest;
Y
Yan, Zheng 已提交
1245
	new_node->checked = 1;
1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258
	new_node->root = dest;

	if (!node->lowest) {
		list_for_each_entry(edge, &node->lower, list[UPPER]) {
			new_edge = alloc_backref_edge(cache);
			if (!new_edge)
				goto fail;

			new_edge->node[UPPER] = new_node;
			new_edge->node[LOWER] = edge->node[LOWER];
			list_add_tail(&new_edge->list[UPPER],
				      &new_node->lower);
		}
M
Miao Xie 已提交
1259 1260
	} else {
		list_add_tail(&new_node->lower, &cache->leaves);
1261 1262 1263 1264
	}

	rb_node = tree_insert(&cache->rb_root, new_node->bytenr,
			      &new_node->rb_node);
1265 1266
	if (rb_node)
		backref_tree_panic(rb_node, -EEXIST, new_node->bytenr);
1267 1268 1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282 1283 1284 1285

	if (!new_node->lowest) {
		list_for_each_entry(new_edge, &new_node->lower, list[UPPER]) {
			list_add_tail(&new_edge->list[LOWER],
				      &new_edge->node[LOWER]->upper);
		}
	}
	return 0;
fail:
	while (!list_empty(&new_node->lower)) {
		new_edge = list_entry(new_node->lower.next,
				      struct backref_edge, list[UPPER]);
		list_del(&new_edge->list[UPPER]);
		free_backref_edge(cache, new_edge);
	}
	free_backref_node(cache, new_node);
	return -ENOMEM;
}

1286 1287 1288
/*
 * helper to add 'address of tree root -> reloc tree' mapping
 */
1289
static int __must_check __add_reloc_root(struct btrfs_root *root)
1290
{
1291
	struct btrfs_fs_info *fs_info = root->fs_info;
1292 1293
	struct rb_node *rb_node;
	struct mapping_node *node;
1294
	struct reloc_control *rc = fs_info->reloc_ctl;
1295 1296

	node = kmalloc(sizeof(*node), GFP_NOFS);
1297 1298
	if (!node)
		return -ENOMEM;
1299 1300 1301 1302 1303 1304 1305 1306

	node->bytenr = root->node->start;
	node->data = root;

	spin_lock(&rc->reloc_root_tree.lock);
	rb_node = tree_insert(&rc->reloc_root_tree.rb_root,
			      node->bytenr, &node->rb_node);
	spin_unlock(&rc->reloc_root_tree.lock);
1307
	if (rb_node) {
1308
		btrfs_panic(fs_info, -EEXIST,
J
Jeff Mahoney 已提交
1309 1310
			    "Duplicate root found for start=%llu while inserting into relocation tree",
			    node->bytenr);
1311 1312
		kfree(node);
		return -EEXIST;
1313
	}
1314 1315 1316 1317 1318 1319

	list_add_tail(&root->root_list, &rc->reloc_roots);
	return 0;
}

/*
1320
 * helper to delete the 'address of tree root -> reloc tree'
1321 1322
 * mapping
 */
1323
static void __del_reloc_root(struct btrfs_root *root)
1324
{
1325
	struct btrfs_fs_info *fs_info = root->fs_info;
1326 1327
	struct rb_node *rb_node;
	struct mapping_node *node = NULL;
1328
	struct reloc_control *rc = fs_info->reloc_ctl;
1329 1330 1331

	spin_lock(&rc->reloc_root_tree.lock);
	rb_node = tree_search(&rc->reloc_root_tree.rb_root,
1332
			      root->node->start);
1333 1334 1335 1336 1337 1338
	if (rb_node) {
		node = rb_entry(rb_node, struct mapping_node, rb_node);
		rb_erase(&node->rb_node, &rc->reloc_root_tree.rb_root);
	}
	spin_unlock(&rc->reloc_root_tree.lock);

1339
	if (!node)
1340
		return;
1341 1342
	BUG_ON((struct btrfs_root *)node->data != root);

1343
	spin_lock(&fs_info->trans_lock);
1344
	list_del_init(&root->root_list);
1345
	spin_unlock(&fs_info->trans_lock);
1346 1347 1348 1349 1350 1351 1352 1353 1354
	kfree(node);
}

/*
 * helper to update the 'address of tree root -> reloc tree'
 * mapping
 */
static int __update_reloc_root(struct btrfs_root *root, u64 new_bytenr)
{
1355
	struct btrfs_fs_info *fs_info = root->fs_info;
1356 1357
	struct rb_node *rb_node;
	struct mapping_node *node = NULL;
1358
	struct reloc_control *rc = fs_info->reloc_ctl;
1359 1360 1361 1362 1363 1364 1365

	spin_lock(&rc->reloc_root_tree.lock);
	rb_node = tree_search(&rc->reloc_root_tree.rb_root,
			      root->node->start);
	if (rb_node) {
		node = rb_entry(rb_node, struct mapping_node, rb_node);
		rb_erase(&node->rb_node, &rc->reloc_root_tree.rb_root);
1366
	}
1367 1368 1369 1370 1371 1372 1373 1374 1375 1376 1377 1378 1379
	spin_unlock(&rc->reloc_root_tree.lock);

	if (!node)
		return 0;
	BUG_ON((struct btrfs_root *)node->data != root);

	spin_lock(&rc->reloc_root_tree.lock);
	node->bytenr = new_bytenr;
	rb_node = tree_insert(&rc->reloc_root_tree.rb_root,
			      node->bytenr, &node->rb_node);
	spin_unlock(&rc->reloc_root_tree.lock);
	if (rb_node)
		backref_tree_panic(rb_node, -EEXIST, node->bytenr);
1380 1381 1382
	return 0;
}

1383 1384
static struct btrfs_root *create_reloc_root(struct btrfs_trans_handle *trans,
					struct btrfs_root *root, u64 objectid)
1385
{
1386
	struct btrfs_fs_info *fs_info = root->fs_info;
1387 1388 1389 1390 1391 1392 1393 1394 1395 1396 1397
	struct btrfs_root *reloc_root;
	struct extent_buffer *eb;
	struct btrfs_root_item *root_item;
	struct btrfs_key root_key;
	int ret;

	root_item = kmalloc(sizeof(*root_item), GFP_NOFS);
	BUG_ON(!root_item);

	root_key.objectid = BTRFS_TREE_RELOC_OBJECTID;
	root_key.type = BTRFS_ROOT_ITEM_KEY;
1398
	root_key.offset = objectid;
1399

1400
	if (root->root_key.objectid == objectid) {
1401 1402
		u64 commit_root_gen;

1403 1404 1405 1406
		/* called by btrfs_init_reloc_root */
		ret = btrfs_copy_root(trans, root, root->commit_root, &eb,
				      BTRFS_TREE_RELOC_OBJECTID);
		BUG_ON(ret);
1407 1408 1409 1410 1411 1412 1413 1414 1415 1416
		/*
		 * Set the last_snapshot field to the generation of the commit
		 * root - like this ctree.c:btrfs_block_can_be_shared() behaves
		 * correctly (returns true) when the relocation root is created
		 * either inside the critical section of a transaction commit
		 * (through transaction.c:qgroup_account_snapshot()) and when
		 * it's created before the transaction commit is started.
		 */
		commit_root_gen = btrfs_header_generation(root->commit_root);
		btrfs_set_root_last_snapshot(&root->root_item, commit_root_gen);
1417 1418 1419 1420 1421 1422 1423 1424 1425 1426 1427 1428
	} else {
		/*
		 * called by btrfs_reloc_post_snapshot_hook.
		 * the source tree is a reloc tree, all tree blocks
		 * modified after it was created have RELOC flag
		 * set in their headers. so it's OK to not update
		 * the 'last_snapshot'.
		 */
		ret = btrfs_copy_root(trans, root, root->node, &eb,
				      BTRFS_TREE_RELOC_OBJECTID);
		BUG_ON(ret);
	}
1429 1430 1431 1432 1433

	memcpy(root_item, &root->root_item, sizeof(*root_item));
	btrfs_set_root_bytenr(root_item, eb->start);
	btrfs_set_root_level(root_item, btrfs_header_level(eb));
	btrfs_set_root_generation(root_item, trans->transid);
1434 1435 1436 1437 1438 1439 1440

	if (root->root_key.objectid == objectid) {
		btrfs_set_root_refs(root_item, 0);
		memset(&root_item->drop_progress, 0,
		       sizeof(struct btrfs_disk_key));
		root_item->drop_level = 0;
	}
1441 1442 1443 1444

	btrfs_tree_unlock(eb);
	free_extent_buffer(eb);

1445
	ret = btrfs_insert_root(trans, fs_info->tree_root,
1446 1447 1448 1449
				&root_key, root_item);
	BUG_ON(ret);
	kfree(root_item);

1450
	reloc_root = btrfs_read_fs_root(fs_info->tree_root, &root_key);
1451 1452
	BUG_ON(IS_ERR(reloc_root));
	reloc_root->last_trans = trans->transid;
1453 1454 1455 1456 1457 1458 1459 1460 1461 1462
	return reloc_root;
}

/*
 * create reloc tree for a given fs tree. reloc tree is just a
 * snapshot of the fs tree with special root objectid.
 */
int btrfs_init_reloc_root(struct btrfs_trans_handle *trans,
			  struct btrfs_root *root)
{
1463
	struct btrfs_fs_info *fs_info = root->fs_info;
1464
	struct btrfs_root *reloc_root;
1465
	struct reloc_control *rc = fs_info->reloc_ctl;
1466
	struct btrfs_block_rsv *rsv;
1467
	int clear_rsv = 0;
1468
	int ret;
1469 1470 1471 1472 1473 1474 1475 1476 1477 1478 1479

	if (root->reloc_root) {
		reloc_root = root->reloc_root;
		reloc_root->last_trans = trans->transid;
		return 0;
	}

	if (!rc || !rc->create_reloc_tree ||
	    root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
		return 0;

1480 1481
	if (!trans->reloc_reserved) {
		rsv = trans->block_rsv;
1482 1483 1484 1485 1486
		trans->block_rsv = rc->block_rsv;
		clear_rsv = 1;
	}
	reloc_root = create_reloc_root(trans, root, root->root_key.objectid);
	if (clear_rsv)
1487
		trans->block_rsv = rsv;
1488

1489 1490
	ret = __add_reloc_root(reloc_root);
	BUG_ON(ret < 0);
1491 1492 1493 1494 1495 1496 1497 1498 1499 1500
	root->reloc_root = reloc_root;
	return 0;
}

/*
 * update root item of reloc tree
 */
int btrfs_update_reloc_root(struct btrfs_trans_handle *trans,
			    struct btrfs_root *root)
{
1501
	struct btrfs_fs_info *fs_info = root->fs_info;
1502 1503 1504 1505 1506
	struct btrfs_root *reloc_root;
	struct btrfs_root_item *root_item;
	int ret;

	if (!root->reloc_root)
C
Chris Mason 已提交
1507
		goto out;
1508 1509 1510 1511

	reloc_root = root->reloc_root;
	root_item = &reloc_root->root_item;

1512
	if (fs_info->reloc_ctl->merge_reloc_tree &&
1513
	    btrfs_root_refs(root_item) == 0) {
1514
		root->reloc_root = NULL;
1515
		__del_reloc_root(reloc_root);
1516 1517 1518 1519 1520 1521 1522 1523
	}

	if (reloc_root->commit_root != reloc_root->node) {
		btrfs_set_root_node(root_item, reloc_root->node);
		free_extent_buffer(reloc_root->commit_root);
		reloc_root->commit_root = btrfs_root_node(reloc_root);
	}

1524
	ret = btrfs_update_root(trans, fs_info->tree_root,
1525 1526
				&reloc_root->root_key, root_item);
	BUG_ON(ret);
C
Chris Mason 已提交
1527 1528

out:
1529 1530 1531 1532 1533 1534 1535 1536 1537 1538 1539 1540 1541 1542 1543 1544 1545 1546 1547 1548 1549 1550
	return 0;
}

/*
 * helper to find first cached inode with inode number >= objectid
 * in a subvolume
 */
static struct inode *find_next_inode(struct btrfs_root *root, u64 objectid)
{
	struct rb_node *node;
	struct rb_node *prev;
	struct btrfs_inode *entry;
	struct inode *inode;

	spin_lock(&root->inode_lock);
again:
	node = root->inode_tree.rb_node;
	prev = NULL;
	while (node) {
		prev = node;
		entry = rb_entry(node, struct btrfs_inode, rb_node);

1551
		if (objectid < btrfs_ino(entry))
1552
			node = node->rb_left;
1553
		else if (objectid > btrfs_ino(entry))
1554 1555 1556 1557 1558 1559 1560
			node = node->rb_right;
		else
			break;
	}
	if (!node) {
		while (prev) {
			entry = rb_entry(prev, struct btrfs_inode, rb_node);
1561
			if (objectid <= btrfs_ino(entry)) {
1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575
				node = prev;
				break;
			}
			prev = rb_next(prev);
		}
	}
	while (node) {
		entry = rb_entry(node, struct btrfs_inode, rb_node);
		inode = igrab(&entry->vfs_inode);
		if (inode) {
			spin_unlock(&root->inode_lock);
			return inode;
		}

1576
		objectid = btrfs_ino(entry) + 1;
1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 1588 1589 1590 1591 1592 1593 1594 1595 1596 1597 1598 1599 1600 1601 1602 1603 1604 1605 1606 1607 1608 1609 1610 1611
		if (cond_resched_lock(&root->inode_lock))
			goto again;

		node = rb_next(node);
	}
	spin_unlock(&root->inode_lock);
	return NULL;
}

static int in_block_group(u64 bytenr,
			  struct btrfs_block_group_cache *block_group)
{
	if (bytenr >= block_group->key.objectid &&
	    bytenr < block_group->key.objectid + block_group->key.offset)
		return 1;
	return 0;
}

/*
 * get new location of data
 */
static int get_new_location(struct inode *reloc_inode, u64 *new_bytenr,
			    u64 bytenr, u64 num_bytes)
{
	struct btrfs_root *root = BTRFS_I(reloc_inode)->root;
	struct btrfs_path *path;
	struct btrfs_file_extent_item *fi;
	struct extent_buffer *leaf;
	int ret;

	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;

	bytenr -= BTRFS_I(reloc_inode)->index_cnt;
1612 1613
	ret = btrfs_lookup_file_extent(NULL, root, path,
			btrfs_ino(BTRFS_I(reloc_inode)), bytenr, 0);
1614 1615 1616 1617 1618 1619 1620 1621 1622 1623 1624 1625 1626 1627 1628 1629 1630
	if (ret < 0)
		goto out;
	if (ret > 0) {
		ret = -ENOENT;
		goto out;
	}

	leaf = path->nodes[0];
	fi = btrfs_item_ptr(leaf, path->slots[0],
			    struct btrfs_file_extent_item);

	BUG_ON(btrfs_file_extent_offset(leaf, fi) ||
	       btrfs_file_extent_compression(leaf, fi) ||
	       btrfs_file_extent_encryption(leaf, fi) ||
	       btrfs_file_extent_other_encoding(leaf, fi));

	if (num_bytes != btrfs_file_extent_disk_num_bytes(leaf, fi)) {
1631
		ret = -EINVAL;
1632 1633 1634
		goto out;
	}

1635
	*new_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
1636 1637 1638 1639 1640 1641 1642 1643 1644 1645
	ret = 0;
out:
	btrfs_free_path(path);
	return ret;
}

/*
 * update file extent items in the tree leaf to point to
 * the new locations.
 */
1646 1647 1648 1649 1650
static noinline_for_stack
int replace_file_extents(struct btrfs_trans_handle *trans,
			 struct reloc_control *rc,
			 struct btrfs_root *root,
			 struct extent_buffer *leaf)
1651
{
1652
	struct btrfs_fs_info *fs_info = root->fs_info;
1653 1654 1655 1656 1657
	struct btrfs_key key;
	struct btrfs_file_extent_item *fi;
	struct inode *inode = NULL;
	u64 parent;
	u64 bytenr;
1658
	u64 new_bytenr = 0;
1659 1660 1661 1662
	u64 num_bytes;
	u64 end;
	u32 nritems;
	u32 i;
1663
	int ret = 0;
1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700
	int first = 1;
	int dirty = 0;

	if (rc->stage != UPDATE_DATA_PTRS)
		return 0;

	/* reloc trees always use full backref */
	if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
		parent = leaf->start;
	else
		parent = 0;

	nritems = btrfs_header_nritems(leaf);
	for (i = 0; i < nritems; i++) {
		cond_resched();
		btrfs_item_key_to_cpu(leaf, &key, i);
		if (key.type != BTRFS_EXTENT_DATA_KEY)
			continue;
		fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
		if (btrfs_file_extent_type(leaf, fi) ==
		    BTRFS_FILE_EXTENT_INLINE)
			continue;
		bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
		num_bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
		if (bytenr == 0)
			continue;
		if (!in_block_group(bytenr, rc->block_group))
			continue;

		/*
		 * if we are modifying block in fs tree, wait for readpage
		 * to complete and drop the extent cache
		 */
		if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
			if (first) {
				inode = find_next_inode(root, key.objectid);
				first = 0;
1701
			} else if (inode && btrfs_ino(BTRFS_I(inode)) < key.objectid) {
1702
				btrfs_add_delayed_iput(inode);
1703 1704
				inode = find_next_inode(root, key.objectid);
			}
1705
			if (inode && btrfs_ino(BTRFS_I(inode)) == key.objectid) {
1706 1707 1708
				end = key.offset +
				      btrfs_file_extent_num_bytes(leaf, fi);
				WARN_ON(!IS_ALIGNED(key.offset,
1709 1710
						    fs_info->sectorsize));
				WARN_ON(!IS_ALIGNED(end, fs_info->sectorsize));
1711 1712
				end--;
				ret = try_lock_extent(&BTRFS_I(inode)->io_tree,
1713
						      key.offset, end);
1714 1715 1716 1717 1718 1719
				if (!ret)
					continue;

				btrfs_drop_extent_cache(inode, key.offset, end,
							1);
				unlock_extent(&BTRFS_I(inode)->io_tree,
1720
					      key.offset, end);
1721 1722 1723 1724 1725
			}
		}

		ret = get_new_location(rc->data_inode, &new_bytenr,
				       bytenr, num_bytes);
1726 1727 1728 1729 1730 1731
		if (ret) {
			/*
			 * Don't have to abort since we've not changed anything
			 * in the file extent yet.
			 */
			break;
1732
		}
1733 1734 1735 1736 1737

		btrfs_set_file_extent_disk_bytenr(leaf, fi, new_bytenr);
		dirty = 1;

		key.offset -= btrfs_file_extent_offset(leaf, fi);
1738
		ret = btrfs_inc_extent_ref(trans, fs_info, new_bytenr,
1739 1740
					   num_bytes, parent,
					   btrfs_header_owner(leaf),
1741
					   key.objectid, key.offset);
1742
		if (ret) {
1743
			btrfs_abort_transaction(trans, ret);
1744 1745
			break;
		}
1746

1747
		ret = btrfs_free_extent(trans, fs_info, bytenr, num_bytes,
1748
					parent, btrfs_header_owner(leaf),
1749
					key.objectid, key.offset);
1750
		if (ret) {
1751
			btrfs_abort_transaction(trans, ret);
1752 1753
			break;
		}
1754 1755 1756
	}
	if (dirty)
		btrfs_mark_buffer_dirty(leaf);
1757 1758
	if (inode)
		btrfs_add_delayed_iput(inode);
1759
	return ret;
1760 1761 1762 1763 1764 1765 1766 1767 1768 1769 1770 1771 1772 1773 1774 1775 1776 1777 1778 1779 1780 1781
}

static noinline_for_stack
int memcmp_node_keys(struct extent_buffer *eb, int slot,
		     struct btrfs_path *path, int level)
{
	struct btrfs_disk_key key1;
	struct btrfs_disk_key key2;
	btrfs_node_key(eb, &key1, slot);
	btrfs_node_key(path->nodes[level], &key2, path->slots[level]);
	return memcmp(&key1, &key2, sizeof(key1));
}

/*
 * try to replace tree blocks in fs tree with the new blocks
 * in reloc tree. tree blocks haven't been modified since the
 * reloc tree was create can be replaced.
 *
 * if a block was replaced, level of the block + 1 is returned.
 * if no block got replaced, 0 is returned. if there are other
 * errors, a negative error number is returned.
 */
1782 1783 1784 1785 1786
static noinline_for_stack
int replace_path(struct btrfs_trans_handle *trans,
		 struct btrfs_root *dest, struct btrfs_root *src,
		 struct btrfs_path *path, struct btrfs_key *next_key,
		 int lowest_level, int max_level)
1787
{
1788
	struct btrfs_fs_info *fs_info = dest->fs_info;
1789 1790 1791 1792 1793 1794 1795 1796 1797
	struct extent_buffer *eb;
	struct extent_buffer *parent;
	struct btrfs_key key;
	u64 old_bytenr;
	u64 new_bytenr;
	u64 old_ptr_gen;
	u64 new_ptr_gen;
	u64 last_snapshot;
	u32 blocksize;
1798
	int cow = 0;
1799 1800 1801 1802 1803 1804 1805 1806
	int level;
	int ret;
	int slot;

	BUG_ON(src->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID);
	BUG_ON(dest->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID);

	last_snapshot = btrfs_root_last_snapshot(&src->root_item);
1807
again:
1808 1809 1810 1811 1812 1813 1814 1815 1816 1817 1818 1819 1820
	slot = path->slots[lowest_level];
	btrfs_node_key_to_cpu(path->nodes[lowest_level], &key, slot);

	eb = btrfs_lock_root_node(dest);
	btrfs_set_lock_blocking(eb);
	level = btrfs_header_level(eb);

	if (level < lowest_level) {
		btrfs_tree_unlock(eb);
		free_extent_buffer(eb);
		return 0;
	}

1821 1822 1823 1824
	if (cow) {
		ret = btrfs_cow_block(trans, dest, eb, NULL, 0, &eb);
		BUG_ON(ret);
	}
1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845
	btrfs_set_lock_blocking(eb);

	if (next_key) {
		next_key->objectid = (u64)-1;
		next_key->type = (u8)-1;
		next_key->offset = (u64)-1;
	}

	parent = eb;
	while (1) {
		level = btrfs_header_level(parent);
		BUG_ON(level < lowest_level);

		ret = btrfs_bin_search(parent, &key, level, &slot);
		if (ret && slot > 0)
			slot--;

		if (next_key && slot + 1 < btrfs_header_nritems(parent))
			btrfs_node_key_to_cpu(parent, next_key, slot + 1);

		old_bytenr = btrfs_node_blockptr(parent, slot);
1846
		blocksize = fs_info->nodesize;
1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 1858 1859
		old_ptr_gen = btrfs_node_ptr_generation(parent, slot);

		if (level <= max_level) {
			eb = path->nodes[level];
			new_bytenr = btrfs_node_blockptr(eb,
							path->slots[level]);
			new_ptr_gen = btrfs_node_ptr_generation(eb,
							path->slots[level]);
		} else {
			new_bytenr = 0;
			new_ptr_gen = 0;
		}

1860
		if (WARN_ON(new_bytenr > 0 && new_bytenr == old_bytenr)) {
1861 1862 1863 1864 1865 1866
			ret = level;
			break;
		}

		if (new_bytenr == 0 || old_ptr_gen > last_snapshot ||
		    memcmp_node_keys(parent, slot, path, level)) {
1867
			if (level <= lowest_level) {
1868 1869 1870 1871
				ret = 0;
				break;
			}

1872
			eb = read_tree_block(fs_info, old_bytenr, old_ptr_gen);
1873 1874
			if (IS_ERR(eb)) {
				ret = PTR_ERR(eb);
1875
				break;
1876 1877
			} else if (!extent_buffer_uptodate(eb)) {
				ret = -EIO;
1878
				free_extent_buffer(eb);
1879
				break;
1880
			}
1881
			btrfs_tree_lock(eb);
1882 1883 1884 1885
			if (cow) {
				ret = btrfs_cow_block(trans, dest, eb, parent,
						      slot, &eb);
				BUG_ON(ret);
1886
			}
1887
			btrfs_set_lock_blocking(eb);
1888 1889 1890 1891 1892 1893 1894 1895

			btrfs_tree_unlock(parent);
			free_extent_buffer(parent);

			parent = eb;
			continue;
		}

1896 1897 1898 1899 1900 1901 1902
		if (!cow) {
			btrfs_tree_unlock(parent);
			free_extent_buffer(parent);
			cow = 1;
			goto again;
		}

1903 1904
		btrfs_node_key_to_cpu(path->nodes[level], &key,
				      path->slots[level]);
1905
		btrfs_release_path(path);
1906 1907 1908 1909 1910 1911

		path->lowest_level = level;
		ret = btrfs_search_slot(trans, src, &key, path, 0, 1);
		path->lowest_level = 0;
		BUG_ON(ret);

1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 1929 1930 1931 1932 1933 1934
		/*
		 * Info qgroup to trace both subtrees.
		 *
		 * We must trace both trees.
		 * 1) Tree reloc subtree
		 *    If not traced, we will leak data numbers
		 * 2) Fs subtree
		 *    If not traced, we will double count old data
		 *    and tree block numbers, if current trans doesn't free
		 *    data reloc tree inode.
		 */
		ret = btrfs_qgroup_trace_subtree(trans, src, parent,
				btrfs_header_generation(parent),
				btrfs_header_level(parent));
		if (ret < 0)
			break;
		ret = btrfs_qgroup_trace_subtree(trans, dest,
				path->nodes[level],
				btrfs_header_generation(path->nodes[level]),
				btrfs_header_level(path->nodes[level]));
		if (ret < 0)
			break;

1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947
		/*
		 * swap blocks in fs tree and reloc tree.
		 */
		btrfs_set_node_blockptr(parent, slot, new_bytenr);
		btrfs_set_node_ptr_generation(parent, slot, new_ptr_gen);
		btrfs_mark_buffer_dirty(parent);

		btrfs_set_node_blockptr(path->nodes[level],
					path->slots[level], old_bytenr);
		btrfs_set_node_ptr_generation(path->nodes[level],
					      path->slots[level], old_ptr_gen);
		btrfs_mark_buffer_dirty(path->nodes[level]);

1948 1949
		ret = btrfs_inc_extent_ref(trans, fs_info, old_bytenr,
					blocksize, path->nodes[level]->start,
1950
					src->root_key.objectid, level - 1, 0);
1951
		BUG_ON(ret);
1952 1953 1954
		ret = btrfs_inc_extent_ref(trans, fs_info, new_bytenr,
					blocksize, 0, dest->root_key.objectid,
					level - 1, 0);
1955 1956
		BUG_ON(ret);

1957
		ret = btrfs_free_extent(trans, fs_info, new_bytenr, blocksize,
1958
					path->nodes[level]->start,
1959
					src->root_key.objectid, level - 1, 0);
1960 1961
		BUG_ON(ret);

1962
		ret = btrfs_free_extent(trans, fs_info, old_bytenr, blocksize,
1963
					0, dest->root_key.objectid, level - 1,
1964
					0);
1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020
		BUG_ON(ret);

		btrfs_unlock_up_safe(path, 0);

		ret = level;
		break;
	}
	btrfs_tree_unlock(parent);
	free_extent_buffer(parent);
	return ret;
}

/*
 * helper to find next relocated block in reloc tree
 */
static noinline_for_stack
int walk_up_reloc_tree(struct btrfs_root *root, struct btrfs_path *path,
		       int *level)
{
	struct extent_buffer *eb;
	int i;
	u64 last_snapshot;
	u32 nritems;

	last_snapshot = btrfs_root_last_snapshot(&root->root_item);

	for (i = 0; i < *level; i++) {
		free_extent_buffer(path->nodes[i]);
		path->nodes[i] = NULL;
	}

	for (i = *level; i < BTRFS_MAX_LEVEL && path->nodes[i]; i++) {
		eb = path->nodes[i];
		nritems = btrfs_header_nritems(eb);
		while (path->slots[i] + 1 < nritems) {
			path->slots[i]++;
			if (btrfs_node_ptr_generation(eb, path->slots[i]) <=
			    last_snapshot)
				continue;

			*level = i;
			return 0;
		}
		free_extent_buffer(path->nodes[i]);
		path->nodes[i] = NULL;
	}
	return 1;
}

/*
 * walk down reloc tree to find relocated block of lowest level
 */
static noinline_for_stack
int walk_down_reloc_tree(struct btrfs_root *root, struct btrfs_path *path,
			 int *level)
{
2021
	struct btrfs_fs_info *fs_info = root->fs_info;
2022 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 2049 2050 2051
	struct extent_buffer *eb = NULL;
	int i;
	u64 bytenr;
	u64 ptr_gen = 0;
	u64 last_snapshot;
	u32 nritems;

	last_snapshot = btrfs_root_last_snapshot(&root->root_item);

	for (i = *level; i > 0; i--) {
		eb = path->nodes[i];
		nritems = btrfs_header_nritems(eb);
		while (path->slots[i] < nritems) {
			ptr_gen = btrfs_node_ptr_generation(eb, path->slots[i]);
			if (ptr_gen > last_snapshot)
				break;
			path->slots[i]++;
		}
		if (path->slots[i] >= nritems) {
			if (i == *level)
				break;
			*level = i + 1;
			return 0;
		}
		if (i == 1) {
			*level = i;
			return 0;
		}

		bytenr = btrfs_node_blockptr(eb, path->slots[i]);
2052
		eb = read_tree_block(fs_info, bytenr, ptr_gen);
2053 2054 2055
		if (IS_ERR(eb)) {
			return PTR_ERR(eb);
		} else if (!extent_buffer_uptodate(eb)) {
2056 2057 2058
			free_extent_buffer(eb);
			return -EIO;
		}
2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073
		BUG_ON(btrfs_header_level(eb) != i - 1);
		path->nodes[i - 1] = eb;
		path->slots[i - 1] = 0;
	}
	return 1;
}

/*
 * invalidate extent cache for file extents whose key in range of
 * [min_key, max_key)
 */
static int invalidate_extent_cache(struct btrfs_root *root,
				   struct btrfs_key *min_key,
				   struct btrfs_key *max_key)
{
2074
	struct btrfs_fs_info *fs_info = root->fs_info;
2075 2076 2077
	struct inode *inode = NULL;
	u64 objectid;
	u64 start, end;
L
Li Zefan 已提交
2078
	u64 ino;
2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090

	objectid = min_key->objectid;
	while (1) {
		cond_resched();
		iput(inode);

		if (objectid > max_key->objectid)
			break;

		inode = find_next_inode(root, objectid);
		if (!inode)
			break;
2091
		ino = btrfs_ino(BTRFS_I(inode));
2092

L
Li Zefan 已提交
2093
		if (ino > max_key->objectid) {
2094 2095 2096 2097
			iput(inode);
			break;
		}

L
Li Zefan 已提交
2098
		objectid = ino + 1;
2099 2100 2101
		if (!S_ISREG(inode->i_mode))
			continue;

L
Li Zefan 已提交
2102
		if (unlikely(min_key->objectid == ino)) {
2103 2104 2105 2106 2107 2108
			if (min_key->type > BTRFS_EXTENT_DATA_KEY)
				continue;
			if (min_key->type < BTRFS_EXTENT_DATA_KEY)
				start = 0;
			else {
				start = min_key->offset;
2109
				WARN_ON(!IS_ALIGNED(start, fs_info->sectorsize));
2110 2111 2112 2113 2114
			}
		} else {
			start = 0;
		}

L
Li Zefan 已提交
2115
		if (unlikely(max_key->objectid == ino)) {
2116 2117 2118 2119 2120 2121 2122 2123
			if (max_key->type < BTRFS_EXTENT_DATA_KEY)
				continue;
			if (max_key->type > BTRFS_EXTENT_DATA_KEY) {
				end = (u64)-1;
			} else {
				if (max_key->offset == 0)
					continue;
				end = max_key->offset;
2124
				WARN_ON(!IS_ALIGNED(end, fs_info->sectorsize));
2125 2126 2127 2128 2129 2130 2131
				end--;
			}
		} else {
			end = (u64)-1;
		}

		/* the lock_extent waits for readpage to complete */
2132
		lock_extent(&BTRFS_I(inode)->io_tree, start, end);
2133
		btrfs_drop_extent_cache(inode, start, end, 1);
2134
		unlock_extent(&BTRFS_I(inode)->io_tree, start, end);
2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163
	}
	return 0;
}

static int find_next_key(struct btrfs_path *path, int level,
			 struct btrfs_key *key)

{
	while (level < BTRFS_MAX_LEVEL) {
		if (!path->nodes[level])
			break;
		if (path->slots[level] + 1 <
		    btrfs_header_nritems(path->nodes[level])) {
			btrfs_node_key_to_cpu(path->nodes[level], key,
					      path->slots[level] + 1);
			return 0;
		}
		level++;
	}
	return 1;
}

/*
 * merge the relocated tree blocks in reloc tree with corresponding
 * fs tree.
 */
static noinline_for_stack int merge_reloc_root(struct reloc_control *rc,
					       struct btrfs_root *root)
{
2164
	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
2165 2166 2167
	LIST_HEAD(inode_list);
	struct btrfs_key key;
	struct btrfs_key next_key;
2168
	struct btrfs_trans_handle *trans = NULL;
2169 2170 2171
	struct btrfs_root *reloc_root;
	struct btrfs_root_item *root_item;
	struct btrfs_path *path;
2172
	struct extent_buffer *leaf;
2173 2174 2175 2176 2177
	int level;
	int max_level;
	int replaced = 0;
	int ret;
	int err = 0;
2178
	u32 min_reserved;
2179 2180 2181 2182

	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;
2183
	path->reada = READA_FORWARD;
2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199

	reloc_root = root->reloc_root;
	root_item = &reloc_root->root_item;

	if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
		level = btrfs_root_level(root_item);
		extent_buffer_get(reloc_root->node);
		path->nodes[level] = reloc_root->node;
		path->slots[level] = 0;
	} else {
		btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);

		level = root_item->drop_level;
		BUG_ON(level == 0);
		path->lowest_level = level;
		ret = btrfs_search_slot(NULL, reloc_root, &key, path, 0, 0);
2200
		path->lowest_level = 0;
2201 2202 2203 2204 2205 2206 2207 2208 2209 2210 2211 2212
		if (ret < 0) {
			btrfs_free_path(path);
			return ret;
		}

		btrfs_node_key_to_cpu(path->nodes[level], &next_key,
				      path->slots[level]);
		WARN_ON(memcmp(&key, &next_key, sizeof(key)));

		btrfs_unlock_up_safe(path, 0);
	}

2213
	min_reserved = fs_info->nodesize * (BTRFS_MAX_LEVEL - 1) * 2;
2214
	memset(&next_key, 0, sizeof(next_key));
2215

2216
	while (1) {
M
Miao Xie 已提交
2217 2218
		ret = btrfs_block_rsv_refill(root, rc->block_rsv, min_reserved,
					     BTRFS_RESERVE_FLUSH_ALL);
2219
		if (ret) {
2220 2221
			err = ret;
			goto out;
2222
		}
2223 2224 2225 2226 2227 2228 2229
		trans = btrfs_start_transaction(root, 0);
		if (IS_ERR(trans)) {
			err = PTR_ERR(trans);
			trans = NULL;
			goto out;
		}
		trans->block_rsv = rc->block_rsv;
2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245

		replaced = 0;
		max_level = level;

		ret = walk_down_reloc_tree(reloc_root, path, &level);
		if (ret < 0) {
			err = ret;
			goto out;
		}
		if (ret > 0)
			break;

		if (!find_next_key(path, level, &key) &&
		    btrfs_comp_cpu_keys(&next_key, &key) >= 0) {
			ret = 0;
		} else {
2246 2247
			ret = replace_path(trans, root, reloc_root, path,
					   &next_key, level, max_level);
2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273
		}
		if (ret < 0) {
			err = ret;
			goto out;
		}

		if (ret > 0) {
			level = ret;
			btrfs_node_key_to_cpu(path->nodes[level], &key,
					      path->slots[level]);
			replaced = 1;
		}

		ret = walk_up_reloc_tree(reloc_root, path, &level);
		if (ret > 0)
			break;

		BUG_ON(level == 0);
		/*
		 * save the merging progress in the drop_progress.
		 * this is OK since root refs == 1 in this case.
		 */
		btrfs_node_key(path->nodes[level], &root_item->drop_progress,
			       path->slots[level]);
		root_item->drop_level = level;

2274
		btrfs_end_transaction_throttle(trans);
2275
		trans = NULL;
2276

2277
		btrfs_btree_balance_dirty(fs_info);
2278 2279 2280 2281 2282 2283 2284 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300

		if (replaced && rc->stage == UPDATE_DATA_PTRS)
			invalidate_extent_cache(root, &key, &next_key);
	}

	/*
	 * handle the case only one block in the fs tree need to be
	 * relocated and the block is tree root.
	 */
	leaf = btrfs_lock_root_node(root);
	ret = btrfs_cow_block(trans, root, leaf, NULL, 0, &leaf);
	btrfs_tree_unlock(leaf);
	free_extent_buffer(leaf);
	if (ret < 0)
		err = ret;
out:
	btrfs_free_path(path);

	if (err == 0) {
		memset(&root_item->drop_progress, 0,
		       sizeof(root_item->drop_progress));
		root_item->drop_level = 0;
		btrfs_set_root_refs(root_item, 0);
2301
		btrfs_update_reloc_root(trans, root);
2302 2303
	}

2304
	if (trans)
2305
		btrfs_end_transaction_throttle(trans);
2306

2307
	btrfs_btree_balance_dirty(fs_info);
2308 2309 2310 2311 2312 2313 2314

	if (replaced && rc->stage == UPDATE_DATA_PTRS)
		invalidate_extent_cache(root, &key, &next_key);

	return err;
}

2315 2316
static noinline_for_stack
int prepare_to_merge(struct reloc_control *rc, int err)
2317
{
2318
	struct btrfs_root *root = rc->extent_root;
2319
	struct btrfs_fs_info *fs_info = root->fs_info;
2320
	struct btrfs_root *reloc_root;
2321 2322 2323 2324 2325
	struct btrfs_trans_handle *trans;
	LIST_HEAD(reloc_roots);
	u64 num_bytes = 0;
	int ret;

2326 2327
	mutex_lock(&fs_info->reloc_mutex);
	rc->merging_rsv_size += fs_info->nodesize * (BTRFS_MAX_LEVEL - 1) * 2;
2328
	rc->merging_rsv_size += rc->nodes_relocated * 2;
2329
	mutex_unlock(&fs_info->reloc_mutex);
C
Chris Mason 已提交
2330

2331 2332 2333
again:
	if (!err) {
		num_bytes = rc->merging_rsv_size;
M
Miao Xie 已提交
2334 2335
		ret = btrfs_block_rsv_add(root, rc->block_rsv, num_bytes,
					  BTRFS_RESERVE_FLUSH_ALL);
2336 2337 2338 2339
		if (ret)
			err = ret;
	}

2340
	trans = btrfs_join_transaction(rc->extent_root);
2341 2342
	if (IS_ERR(trans)) {
		if (!err)
2343 2344
			btrfs_block_rsv_release(fs_info, rc->block_rsv,
						num_bytes);
2345 2346
		return PTR_ERR(trans);
	}
2347 2348 2349

	if (!err) {
		if (num_bytes != rc->merging_rsv_size) {
2350
			btrfs_end_transaction(trans);
2351 2352
			btrfs_block_rsv_release(fs_info, rc->block_rsv,
						num_bytes);
2353 2354 2355
			goto again;
		}
	}
2356

2357 2358 2359 2360 2361 2362
	rc->merge_reloc_tree = 1;

	while (!list_empty(&rc->reloc_roots)) {
		reloc_root = list_entry(rc->reloc_roots.next,
					struct btrfs_root, root_list);
		list_del_init(&reloc_root->root_list);
2363

2364
		root = read_fs_root(fs_info, reloc_root->root_key.offset);
2365 2366 2367
		BUG_ON(IS_ERR(root));
		BUG_ON(root->reloc_root != reloc_root);

2368 2369 2370 2371 2372 2373
		/*
		 * set reference count to 1, so btrfs_recover_relocation
		 * knows it should resumes merging
		 */
		if (!err)
			btrfs_set_root_refs(&reloc_root->root_item, 1);
2374 2375
		btrfs_update_reloc_root(trans, root);

2376 2377
		list_add(&reloc_root->root_list, &reloc_roots);
	}
2378

2379
	list_splice(&reloc_roots, &rc->reloc_roots);
2380

2381
	if (!err)
2382
		btrfs_commit_transaction(trans);
2383
	else
2384
		btrfs_end_transaction(trans);
2385
	return err;
2386 2387
}

2388 2389 2390 2391 2392 2393 2394 2395
static noinline_for_stack
void free_reloc_roots(struct list_head *list)
{
	struct btrfs_root *reloc_root;

	while (!list_empty(list)) {
		reloc_root = list_entry(list->next, struct btrfs_root,
					root_list);
2396 2397 2398 2399
		free_extent_buffer(reloc_root->node);
		free_extent_buffer(reloc_root->commit_root);
		reloc_root->node = NULL;
		reloc_root->commit_root = NULL;
2400
		__del_reloc_root(reloc_root);
2401 2402 2403
	}
}

2404
static noinline_for_stack
2405
void merge_reloc_roots(struct reloc_control *rc)
2406
{
2407
	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
2408
	struct btrfs_root *root;
2409 2410 2411
	struct btrfs_root *reloc_root;
	LIST_HEAD(reloc_roots);
	int found = 0;
2412
	int ret = 0;
2413 2414
again:
	root = rc->extent_root;
C
Chris Mason 已提交
2415 2416 2417 2418 2419 2420 2421

	/*
	 * this serializes us with btrfs_record_root_in_transaction,
	 * we have to make sure nobody is in the middle of
	 * adding their roots to the list while we are
	 * doing this splice
	 */
2422
	mutex_lock(&fs_info->reloc_mutex);
2423
	list_splice_init(&rc->reloc_roots, &reloc_roots);
2424
	mutex_unlock(&fs_info->reloc_mutex);
2425

2426 2427 2428 2429
	while (!list_empty(&reloc_roots)) {
		found = 1;
		reloc_root = list_entry(reloc_roots.next,
					struct btrfs_root, root_list);
2430

2431
		if (btrfs_root_refs(&reloc_root->root_item) > 0) {
2432
			root = read_fs_root(fs_info,
2433 2434 2435
					    reloc_root->root_key.offset);
			BUG_ON(IS_ERR(root));
			BUG_ON(root->reloc_root != reloc_root);
2436

2437
			ret = merge_reloc_root(rc, root);
2438
			if (ret) {
2439 2440 2441
				if (list_empty(&reloc_root->root_list))
					list_add_tail(&reloc_root->root_list,
						      &reloc_roots);
2442
				goto out;
2443
			}
2444 2445 2446
		} else {
			list_del_init(&reloc_root->root_list);
		}
M
Miao Xie 已提交
2447

2448
		ret = btrfs_drop_snapshot(reloc_root, rc->block_rsv, 0, 1);
2449 2450 2451 2452 2453 2454
		if (ret < 0) {
			if (list_empty(&reloc_root->root_list))
				list_add_tail(&reloc_root->root_list,
					      &reloc_roots);
			goto out;
		}
2455 2456
	}

2457 2458 2459 2460
	if (found) {
		found = 0;
		goto again;
	}
2461 2462
out:
	if (ret) {
2463
		btrfs_handle_fs_error(fs_info, ret, NULL);
2464 2465
		if (!list_empty(&reloc_roots))
			free_reloc_roots(&reloc_roots);
2466 2467

		/* new reloc root may be added */
2468
		mutex_lock(&fs_info->reloc_mutex);
2469
		list_splice_init(&rc->reloc_roots, &reloc_roots);
2470
		mutex_unlock(&fs_info->reloc_mutex);
2471 2472
		if (!list_empty(&reloc_roots))
			free_reloc_roots(&reloc_roots);
2473 2474
	}

2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 2489 2490 2491
	BUG_ON(!RB_EMPTY_ROOT(&rc->reloc_root_tree.rb_root));
}

static void free_block_list(struct rb_root *blocks)
{
	struct tree_block *block;
	struct rb_node *rb_node;
	while ((rb_node = rb_first(blocks))) {
		block = rb_entry(rb_node, struct tree_block, rb_node);
		rb_erase(rb_node, blocks);
		kfree(block);
	}
}

static int record_reloc_root_in_trans(struct btrfs_trans_handle *trans,
				      struct btrfs_root *reloc_root)
{
2492
	struct btrfs_fs_info *fs_info = reloc_root->fs_info;
2493 2494 2495 2496 2497
	struct btrfs_root *root;

	if (reloc_root->last_trans == trans->transid)
		return 0;

2498
	root = read_fs_root(fs_info, reloc_root->root_key.offset);
2499 2500 2501 2502 2503 2504
	BUG_ON(IS_ERR(root));
	BUG_ON(root->reloc_root != reloc_root);

	return btrfs_record_root_in_trans(trans, root);
}

2505 2506 2507 2508
static noinline_for_stack
struct btrfs_root *select_reloc_root(struct btrfs_trans_handle *trans,
				     struct reloc_control *rc,
				     struct backref_node *node,
2509
				     struct backref_edge *edges[])
2510 2511 2512
{
	struct backref_node *next;
	struct btrfs_root *root;
2513 2514
	int index = 0;

2515 2516 2517 2518 2519
	next = node;
	while (1) {
		cond_resched();
		next = walk_up_backref(next, edges, &index);
		root = next->root;
2520
		BUG_ON(!root);
2521
		BUG_ON(!test_bit(BTRFS_ROOT_REF_COWS, &root->state));
2522 2523 2524 2525 2526 2527

		if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
			record_reloc_root_in_trans(trans, root);
			break;
		}

2528 2529 2530 2531 2532 2533 2534 2535 2536 2537 2538
		btrfs_record_root_in_trans(trans, root);
		root = root->reloc_root;

		if (next->new_bytenr != root->node->start) {
			BUG_ON(next->new_bytenr);
			BUG_ON(!list_empty(&next->list));
			next->new_bytenr = root->node->start;
			next->root = root;
			list_add_tail(&next->list,
				      &rc->backref_cache.changed);
			__mark_block_processed(rc, next);
2539 2540 2541
			break;
		}

2542
		WARN_ON(1);
2543 2544 2545 2546 2547
		root = NULL;
		next = walk_down_backref(edges, &index);
		if (!next || next->level <= node->level)
			break;
	}
2548 2549
	if (!root)
		return NULL;
2550

2551 2552 2553 2554 2555 2556 2557
	next = node;
	/* setup backref node path for btrfs_reloc_cow_block */
	while (1) {
		rc->backref_cache.path[next->level] = next;
		if (--index < 0)
			break;
		next = edges[index]->node[UPPER];
2558 2559 2560 2561
	}
	return root;
}

2562 2563 2564 2565 2566 2567
/*
 * select a tree root for relocation. return NULL if the block
 * is reference counted. we should use do_relocation() in this
 * case. return a tree root pointer if the block isn't reference
 * counted. return -ENOENT if the block is root of reloc tree.
 */
2568
static noinline_for_stack
2569
struct btrfs_root *select_one_root(struct backref_node *node)
2570
{
2571 2572 2573
	struct backref_node *next;
	struct btrfs_root *root;
	struct btrfs_root *fs_root = NULL;
2574
	struct backref_edge *edges[BTRFS_MAX_LEVEL - 1];
2575 2576 2577 2578 2579 2580 2581 2582 2583
	int index = 0;

	next = node;
	while (1) {
		cond_resched();
		next = walk_up_backref(next, edges, &index);
		root = next->root;
		BUG_ON(!root);

L
Lucas De Marchi 已提交
2584
		/* no other choice for non-references counted tree */
2585
		if (!test_bit(BTRFS_ROOT_REF_COWS, &root->state))
2586 2587 2588 2589 2590 2591 2592 2593 2594 2595 2596 2597 2598 2599 2600 2601
			return root;

		if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID)
			fs_root = root;

		if (next != node)
			return NULL;

		next = walk_down_backref(edges, &index);
		if (!next || next->level <= node->level)
			break;
	}

	if (!fs_root)
		return ERR_PTR(-ENOENT);
	return fs_root;
2602 2603 2604
}

static noinline_for_stack
2605 2606
u64 calcu_metadata_size(struct reloc_control *rc,
			struct backref_node *node, int reserve)
2607
{
2608
	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
2609 2610 2611 2612 2613 2614 2615 2616 2617 2618 2619 2620 2621 2622
	struct backref_node *next = node;
	struct backref_edge *edge;
	struct backref_edge *edges[BTRFS_MAX_LEVEL - 1];
	u64 num_bytes = 0;
	int index = 0;

	BUG_ON(reserve && node->processed);

	while (next) {
		cond_resched();
		while (1) {
			if (next->processed && (reserve || next != node))
				break;

2623
			num_bytes += fs_info->nodesize;
2624 2625 2626 2627 2628 2629 2630 2631 2632 2633 2634 2635

			if (list_empty(&next->upper))
				break;

			edge = list_entry(next->upper.next,
					  struct backref_edge, list[LOWER]);
			edges[index++] = edge;
			next = edge->node[UPPER];
		}
		next = walk_down_backref(edges, &index);
	}
	return num_bytes;
2636 2637
}

2638 2639 2640
static int reserve_metadata_space(struct btrfs_trans_handle *trans,
				  struct reloc_control *rc,
				  struct backref_node *node)
2641
{
2642
	struct btrfs_root *root = rc->extent_root;
2643
	struct btrfs_fs_info *fs_info = root->fs_info;
2644 2645
	u64 num_bytes;
	int ret;
2646
	u64 tmp;
2647 2648

	num_bytes = calcu_metadata_size(rc, node, 1) * 2;
2649

2650
	trans->block_rsv = rc->block_rsv;
2651
	rc->reserved_bytes += num_bytes;
2652 2653 2654 2655 2656 2657

	/*
	 * We are under a transaction here so we can only do limited flushing.
	 * If we get an enospc just kick back -EAGAIN so we know to drop the
	 * transaction and try to refill when we can flush all the things.
	 */
2658
	ret = btrfs_block_rsv_refill(root, rc->block_rsv, num_bytes,
2659
				BTRFS_RESERVE_FLUSH_LIMIT);
2660
	if (ret) {
2661
		tmp = fs_info->nodesize * RELOCATION_RESERVED_NODES;
2662 2663 2664 2665 2666 2667 2668 2669 2670
		while (tmp <= rc->reserved_bytes)
			tmp <<= 1;
		/*
		 * only one thread can access block_rsv at this point,
		 * so we don't need hold lock to protect block_rsv.
		 * we expand more reservation size here to allow enough
		 * space for relocation and we will return eailer in
		 * enospc case.
		 */
2671 2672
		rc->block_rsv->size = tmp + fs_info->nodesize *
				      RELOCATION_RESERVED_NODES;
2673
		return -EAGAIN;
2674
	}
2675 2676 2677 2678

	return 0;
}

2679 2680 2681 2682 2683 2684 2685 2686
/*
 * relocate a block tree, and then update pointers in upper level
 * blocks that reference the block to point to the new location.
 *
 * if called by link_to_upper, the block has already been relocated.
 * in that case this function just updates pointers.
 */
static int do_relocation(struct btrfs_trans_handle *trans,
2687
			 struct reloc_control *rc,
2688 2689 2690 2691
			 struct backref_node *node,
			 struct btrfs_key *key,
			 struct btrfs_path *path, int lowest)
{
2692
	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
2693 2694 2695 2696 2697 2698 2699 2700 2701 2702 2703 2704 2705 2706 2707
	struct backref_node *upper;
	struct backref_edge *edge;
	struct backref_edge *edges[BTRFS_MAX_LEVEL - 1];
	struct btrfs_root *root;
	struct extent_buffer *eb;
	u32 blocksize;
	u64 bytenr;
	u64 generation;
	int slot;
	int ret;
	int err = 0;

	BUG_ON(lowest && node->eb);

	path->lowest_level = node->level + 1;
2708
	rc->backref_cache.path[node->level] = node;
2709 2710 2711 2712
	list_for_each_entry(edge, &node->upper, list[LOWER]) {
		cond_resched();

		upper = edge->node[UPPER];
2713
		root = select_reloc_root(trans, rc, upper, edges);
2714 2715 2716 2717 2718 2719 2720 2721 2722 2723 2724
		BUG_ON(!root);

		if (upper->eb && !upper->locked) {
			if (!lowest) {
				ret = btrfs_bin_search(upper->eb, key,
						       upper->level, &slot);
				BUG_ON(ret);
				bytenr = btrfs_node_blockptr(upper->eb, slot);
				if (node->eb->start == bytenr)
					goto next;
			}
2725
			drop_node_buffer(upper);
2726
		}
2727 2728 2729

		if (!upper->eb) {
			ret = btrfs_search_slot(trans, root, key, path, 0, 1);
2730 2731 2732 2733 2734 2735 2736
			if (ret) {
				if (ret < 0)
					err = ret;
				else
					err = -ENOENT;

				btrfs_release_path(path);
2737 2738 2739
				break;
			}

2740 2741 2742 2743 2744 2745
			if (!upper->eb) {
				upper->eb = path->nodes[upper->level];
				path->nodes[upper->level] = NULL;
			} else {
				BUG_ON(upper->eb != path->nodes[upper->level]);
			}
2746

2747 2748
			upper->locked = 1;
			path->locks[upper->level] = 0;
2749

2750
			slot = path->slots[upper->level];
2751
			btrfs_release_path(path);
2752 2753 2754 2755 2756 2757 2758
		} else {
			ret = btrfs_bin_search(upper->eb, key, upper->level,
					       &slot);
			BUG_ON(ret);
		}

		bytenr = btrfs_node_blockptr(upper->eb, slot);
2759
		if (lowest) {
L
Liu Bo 已提交
2760 2761 2762 2763 2764 2765 2766 2767
			if (bytenr != node->bytenr) {
				btrfs_err(root->fs_info,
		"lowest leaf/node mismatch: bytenr %llu node->bytenr %llu slot %d upper %llu",
					  bytenr, node->bytenr, slot,
					  upper->eb->start);
				err = -EIO;
				goto next;
			}
2768
		} else {
2769 2770
			if (node->eb->start == bytenr)
				goto next;
2771 2772
		}

2773
		blocksize = root->fs_info->nodesize;
2774
		generation = btrfs_node_ptr_generation(upper->eb, slot);
2775
		eb = read_tree_block(fs_info, bytenr, generation);
2776 2777 2778 2779
		if (IS_ERR(eb)) {
			err = PTR_ERR(eb);
			goto next;
		} else if (!extent_buffer_uptodate(eb)) {
2780
			free_extent_buffer(eb);
2781 2782 2783
			err = -EIO;
			goto next;
		}
2784 2785 2786 2787 2788 2789
		btrfs_tree_lock(eb);
		btrfs_set_lock_blocking(eb);

		if (!node->eb) {
			ret = btrfs_cow_block(trans, root, eb, upper->eb,
					      slot, &eb);
2790 2791
			btrfs_tree_unlock(eb);
			free_extent_buffer(eb);
2792 2793
			if (ret < 0) {
				err = ret;
2794
				goto next;
2795
			}
2796
			BUG_ON(node->eb != eb);
2797 2798 2799 2800 2801 2802 2803
		} else {
			btrfs_set_node_blockptr(upper->eb, slot,
						node->eb->start);
			btrfs_set_node_ptr_generation(upper->eb, slot,
						      trans->transid);
			btrfs_mark_buffer_dirty(upper->eb);

2804
			ret = btrfs_inc_extent_ref(trans, root->fs_info,
2805 2806 2807
						node->eb->start, blocksize,
						upper->eb->start,
						btrfs_header_owner(upper->eb),
2808
						node->level, 0);
2809 2810 2811 2812 2813
			BUG_ON(ret);

			ret = btrfs_drop_subtree(trans, root, eb, upper->eb);
			BUG_ON(ret);
		}
2814 2815 2816 2817 2818 2819 2820
next:
		if (!upper->pending)
			drop_node_buffer(upper);
		else
			unlock_node_buffer(upper);
		if (err)
			break;
2821
	}
2822 2823 2824 2825 2826 2827 2828

	if (!err && node->pending) {
		drop_node_buffer(node);
		list_move_tail(&node->list, &rc->backref_cache.changed);
		node->pending = 0;
	}

2829
	path->lowest_level = 0;
2830
	BUG_ON(err == -ENOSPC);
2831 2832 2833 2834
	return err;
}

static int link_to_upper(struct btrfs_trans_handle *trans,
2835
			 struct reloc_control *rc,
2836 2837 2838 2839 2840 2841
			 struct backref_node *node,
			 struct btrfs_path *path)
{
	struct btrfs_key key;

	btrfs_node_key_to_cpu(node->eb, &key, 0);
2842
	return do_relocation(trans, rc, node, &key, path, 0);
2843 2844 2845
}

static int finish_pending_nodes(struct btrfs_trans_handle *trans,
2846 2847
				struct reloc_control *rc,
				struct btrfs_path *path, int err)
2848
{
2849 2850
	LIST_HEAD(list);
	struct backref_cache *cache = &rc->backref_cache;
2851 2852 2853 2854 2855 2856 2857
	struct backref_node *node;
	int level;
	int ret;

	for (level = 0; level < BTRFS_MAX_LEVEL; level++) {
		while (!list_empty(&cache->pending[level])) {
			node = list_entry(cache->pending[level].next,
2858 2859 2860
					  struct backref_node, list);
			list_move_tail(&node->list, &list);
			BUG_ON(!node->pending);
2861

2862 2863 2864 2865 2866
			if (!err) {
				ret = link_to_upper(trans, rc, node, path);
				if (ret < 0)
					err = ret;
			}
2867
		}
2868
		list_splice_init(&list, &cache->pending[level]);
2869 2870 2871 2872 2873
	}
	return err;
}

static void mark_block_processed(struct reloc_control *rc,
2874 2875 2876
				 u64 bytenr, u32 blocksize)
{
	set_extent_bits(&rc->processed_blocks, bytenr, bytenr + blocksize - 1,
2877
			EXTENT_DIRTY);
2878 2879 2880 2881
}

static void __mark_block_processed(struct reloc_control *rc,
				   struct backref_node *node)
2882 2883 2884 2885
{
	u32 blocksize;
	if (node->level == 0 ||
	    in_block_group(node->bytenr, rc->block_group)) {
2886
		blocksize = rc->extent_root->fs_info->nodesize;
2887
		mark_block_processed(rc, node->bytenr, blocksize);
2888 2889 2890 2891 2892 2893 2894 2895 2896 2897 2898 2899 2900 2901 2902 2903 2904 2905 2906 2907 2908 2909
	}
	node->processed = 1;
}

/*
 * mark a block and all blocks directly/indirectly reference the block
 * as processed.
 */
static void update_processed_blocks(struct reloc_control *rc,
				    struct backref_node *node)
{
	struct backref_node *next = node;
	struct backref_edge *edge;
	struct backref_edge *edges[BTRFS_MAX_LEVEL - 1];
	int index = 0;

	while (next) {
		cond_resched();
		while (1) {
			if (next->processed)
				break;

2910
			__mark_block_processed(rc, next);
2911 2912 2913 2914 2915 2916 2917 2918 2919 2920 2921 2922 2923

			if (list_empty(&next->upper))
				break;

			edge = list_entry(next->upper.next,
					  struct backref_edge, list[LOWER]);
			edges[index++] = edge;
			next = edge->node[UPPER];
		}
		next = walk_down_backref(edges, &index);
	}
}

2924
static int tree_block_processed(u64 bytenr, struct reloc_control *rc)
2925
{
2926
	u32 blocksize = rc->extent_root->fs_info->nodesize;
2927

2928 2929 2930 2931
	if (test_range_bit(&rc->processed_blocks, bytenr,
			   bytenr + blocksize - 1, EXTENT_DIRTY, 1, NULL))
		return 1;
	return 0;
2932 2933
}

2934
static int get_tree_block_key(struct btrfs_fs_info *fs_info,
2935 2936 2937 2938 2939
			      struct tree_block *block)
{
	struct extent_buffer *eb;

	BUG_ON(block->key_ready);
2940
	eb = read_tree_block(fs_info, block->bytenr, block->key.offset);
2941 2942 2943
	if (IS_ERR(eb)) {
		return PTR_ERR(eb);
	} else if (!extent_buffer_uptodate(eb)) {
2944 2945 2946
		free_extent_buffer(eb);
		return -EIO;
	}
2947 2948 2949 2950 2951 2952 2953 2954 2955 2956 2957 2958 2959 2960 2961 2962 2963 2964 2965 2966
	WARN_ON(btrfs_header_level(eb) != block->level);
	if (block->level == 0)
		btrfs_item_key_to_cpu(eb, &block->key, 0);
	else
		btrfs_node_key_to_cpu(eb, &block->key, 0);
	free_extent_buffer(eb);
	block->key_ready = 1;
	return 0;
}

/*
 * helper function to relocate a tree block
 */
static int relocate_tree_block(struct btrfs_trans_handle *trans,
				struct reloc_control *rc,
				struct backref_node *node,
				struct btrfs_key *key,
				struct btrfs_path *path)
{
	struct btrfs_root *root;
2967 2968 2969 2970
	int ret = 0;

	if (!node)
		return 0;
2971

2972
	BUG_ON(node->processed);
2973
	root = select_one_root(node);
2974
	if (root == ERR_PTR(-ENOENT)) {
2975
		update_processed_blocks(rc, node);
2976
		goto out;
2977 2978
	}

2979
	if (!root || test_bit(BTRFS_ROOT_REF_COWS, &root->state)) {
2980 2981
		ret = reserve_metadata_space(trans, rc, node);
		if (ret)
2982 2983 2984
			goto out;
	}

2985
	if (root) {
2986
		if (test_bit(BTRFS_ROOT_REF_COWS, &root->state)) {
2987 2988 2989 2990 2991 2992 2993 2994 2995 2996
			BUG_ON(node->new_bytenr);
			BUG_ON(!list_empty(&node->list));
			btrfs_record_root_in_trans(trans, root);
			root = root->reloc_root;
			node->new_bytenr = root->node->start;
			node->root = root;
			list_add_tail(&node->list, &rc->backref_cache.changed);
		} else {
			path->lowest_level = node->level;
			ret = btrfs_search_slot(trans, root, key, path, 0, 1);
2997
			btrfs_release_path(path);
2998 2999 3000 3001 3002 3003 3004 3005
			if (ret > 0)
				ret = 0;
		}
		if (!ret)
			update_processed_blocks(rc, node);
	} else {
		ret = do_relocation(trans, rc, node, key, path, 1);
	}
3006
out:
3007
	if (ret || node->level == 0 || node->cowonly)
3008
		remove_backref_node(&rc->backref_cache, node);
3009 3010 3011 3012 3013 3014 3015 3016 3017 3018
	return ret;
}

/*
 * relocate a list of blocks
 */
static noinline_for_stack
int relocate_tree_blocks(struct btrfs_trans_handle *trans,
			 struct reloc_control *rc, struct rb_root *blocks)
{
3019
	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
3020 3021 3022 3023 3024 3025 3026 3027
	struct backref_node *node;
	struct btrfs_path *path;
	struct tree_block *block;
	struct rb_node *rb_node;
	int ret;
	int err = 0;

	path = btrfs_alloc_path();
3028 3029
	if (!path) {
		err = -ENOMEM;
3030
		goto out_free_blocks;
3031
	}
3032 3033 3034 3035 3036

	rb_node = rb_first(blocks);
	while (rb_node) {
		block = rb_entry(rb_node, struct tree_block, rb_node);
		if (!block->key_ready)
3037
			readahead_tree_block(fs_info, block->bytenr);
3038 3039 3040 3041 3042 3043
		rb_node = rb_next(rb_node);
	}

	rb_node = rb_first(blocks);
	while (rb_node) {
		block = rb_entry(rb_node, struct tree_block, rb_node);
3044
		if (!block->key_ready) {
3045
			err = get_tree_block_key(fs_info, block);
3046 3047 3048
			if (err)
				goto out_free_path;
		}
3049 3050 3051 3052 3053 3054 3055
		rb_node = rb_next(rb_node);
	}

	rb_node = rb_first(blocks);
	while (rb_node) {
		block = rb_entry(rb_node, struct tree_block, rb_node);

3056
		node = build_backref_tree(rc, &block->key,
3057 3058 3059 3060 3061 3062 3063 3064 3065
					  block->level, block->bytenr);
		if (IS_ERR(node)) {
			err = PTR_ERR(node);
			goto out;
		}

		ret = relocate_tree_block(trans, rc, node, &block->key,
					  path);
		if (ret < 0) {
3066 3067
			if (ret != -EAGAIN || rb_node == rb_first(blocks))
				err = ret;
3068 3069 3070 3071 3072
			goto out;
		}
		rb_node = rb_next(rb_node);
	}
out:
3073
	err = finish_pending_nodes(trans, rc, path, err);
3074

3075
out_free_path:
3076
	btrfs_free_path(path);
3077
out_free_blocks:
3078
	free_block_list(blocks);
3079 3080 3081
	return err;
}

3082 3083 3084 3085 3086 3087 3088 3089 3090 3091 3092
static noinline_for_stack
int prealloc_file_extent_cluster(struct inode *inode,
				 struct file_extent_cluster *cluster)
{
	u64 alloc_hint = 0;
	u64 start;
	u64 end;
	u64 offset = BTRFS_I(inode)->index_cnt;
	u64 num_bytes;
	int nr = 0;
	int ret = 0;
3093 3094
	u64 prealloc_start = cluster->start - offset;
	u64 prealloc_end = cluster->end - offset;
3095
	u64 cur_offset;
3096 3097

	BUG_ON(cluster->start != cluster->boundary[0]);
A
Al Viro 已提交
3098
	inode_lock(inode);
3099

3100 3101
	ret = btrfs_check_data_free_space(inode, prealloc_start,
					  prealloc_end + 1 - prealloc_start);
3102 3103 3104
	if (ret)
		goto out;

3105
	cur_offset = prealloc_start;
3106 3107 3108 3109 3110 3111 3112
	while (nr < cluster->nr) {
		start = cluster->boundary[nr] - offset;
		if (nr + 1 < cluster->nr)
			end = cluster->boundary[nr + 1] - 1 - offset;
		else
			end = cluster->end - offset;

3113
		lock_extent(&BTRFS_I(inode)->io_tree, start, end);
3114
		num_bytes = end + 1 - start;
3115 3116 3117
		if (cur_offset < start)
			btrfs_free_reserved_data_space(inode, cur_offset,
					start - cur_offset);
3118 3119 3120
		ret = btrfs_prealloc_file_range(inode, 0, start,
						num_bytes, num_bytes,
						end + 1, &alloc_hint);
3121
		cur_offset = end + 1;
3122
		unlock_extent(&BTRFS_I(inode)->io_tree, start, end);
3123 3124 3125 3126
		if (ret)
			break;
		nr++;
	}
3127 3128 3129
	if (cur_offset < prealloc_end)
		btrfs_free_reserved_data_space(inode, cur_offset,
				       prealloc_end + 1 - cur_offset);
3130
out:
A
Al Viro 已提交
3131
	inode_unlock(inode);
3132 3133 3134
	return ret;
}

3135
static noinline_for_stack
3136 3137 3138
int setup_extent_mapping(struct inode *inode, u64 start, u64 end,
			 u64 block_start)
{
3139
	struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
3140 3141 3142 3143
	struct extent_map_tree *em_tree = &BTRFS_I(inode)->extent_tree;
	struct extent_map *em;
	int ret = 0;

3144
	em = alloc_extent_map();
3145 3146 3147 3148 3149 3150 3151
	if (!em)
		return -ENOMEM;

	em->start = start;
	em->len = end + 1 - start;
	em->block_len = em->len;
	em->block_start = block_start;
3152
	em->bdev = fs_info->fs_devices->latest_bdev;
3153 3154
	set_bit(EXTENT_FLAG_PINNED, &em->flags);

3155
	lock_extent(&BTRFS_I(inode)->io_tree, start, end);
3156 3157
	while (1) {
		write_lock(&em_tree->lock);
J
Josef Bacik 已提交
3158
		ret = add_extent_mapping(em_tree, em, 0);
3159 3160 3161 3162 3163 3164 3165
		write_unlock(&em_tree->lock);
		if (ret != -EEXIST) {
			free_extent_map(em);
			break;
		}
		btrfs_drop_extent_cache(inode, start, end, 0);
	}
3166
	unlock_extent(&BTRFS_I(inode)->io_tree, start, end);
3167 3168 3169 3170 3171
	return ret;
}

static int relocate_file_extent_cluster(struct inode *inode,
					struct file_extent_cluster *cluster)
3172
{
3173
	struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
3174 3175
	u64 page_start;
	u64 page_end;
3176 3177
	u64 offset = BTRFS_I(inode)->index_cnt;
	unsigned long index;
3178 3179 3180
	unsigned long last_index;
	struct page *page;
	struct file_ra_state *ra;
3181
	gfp_t mask = btrfs_alloc_write_mask(inode->i_mapping);
3182
	int nr = 0;
3183 3184
	int ret = 0;

3185 3186 3187
	if (!cluster->nr)
		return 0;

3188 3189 3190 3191
	ra = kzalloc(sizeof(*ra), GFP_NOFS);
	if (!ra)
		return -ENOMEM;

3192 3193 3194
	ret = prealloc_file_extent_cluster(inode, cluster);
	if (ret)
		goto out;
3195

3196
	file_ra_state_init(ra, inode->i_mapping);
3197

3198 3199
	ret = setup_extent_mapping(inode, cluster->start - offset,
				   cluster->end - offset, cluster->start);
3200
	if (ret)
3201
		goto out;
3202

3203 3204
	index = (cluster->start - offset) >> PAGE_SHIFT;
	last_index = (cluster->end - offset) >> PAGE_SHIFT;
3205
	while (index <= last_index) {
3206 3207
		ret = btrfs_delalloc_reserve_metadata(BTRFS_I(inode),
				PAGE_SIZE);
3208 3209 3210
		if (ret)
			goto out;

3211
		page = find_lock_page(inode->i_mapping, index);
3212
		if (!page) {
3213 3214 3215
			page_cache_sync_readahead(inode->i_mapping,
						  ra, NULL, index,
						  last_index + 1 - index);
3216
			page = find_or_create_page(inode->i_mapping, index,
3217
						   mask);
3218
			if (!page) {
3219
				btrfs_delalloc_release_metadata(BTRFS_I(inode),
3220
							PAGE_SIZE);
3221
				ret = -ENOMEM;
3222
				goto out;
3223
			}
3224
		}
3225 3226 3227 3228 3229 3230 3231

		if (PageReadahead(page)) {
			page_cache_async_readahead(inode->i_mapping,
						   ra, NULL, page, index,
						   last_index + 1 - index);
		}

3232 3233 3234 3235 3236
		if (!PageUptodate(page)) {
			btrfs_readpage(NULL, page);
			lock_page(page);
			if (!PageUptodate(page)) {
				unlock_page(page);
3237
				put_page(page);
3238
				btrfs_delalloc_release_metadata(BTRFS_I(inode),
3239
							PAGE_SIZE);
3240
				ret = -EIO;
3241
				goto out;
3242 3243 3244
			}
		}

M
Miao Xie 已提交
3245
		page_start = page_offset(page);
3246
		page_end = page_start + PAGE_SIZE - 1;
3247

3248
		lock_extent(&BTRFS_I(inode)->io_tree, page_start, page_end);
3249

3250 3251
		set_page_extent_mapped(page);

3252 3253 3254 3255
		if (nr < cluster->nr &&
		    page_start + offset == cluster->boundary[nr]) {
			set_extent_bits(&BTRFS_I(inode)->io_tree,
					page_start, page_end,
3256
					EXTENT_BOUNDARY);
3257 3258
			nr++;
		}
3259

3260
		btrfs_set_extent_delalloc(inode, page_start, page_end, NULL, 0);
3261 3262
		set_page_dirty(page);

3263
		unlock_extent(&BTRFS_I(inode)->io_tree,
3264
			      page_start, page_end);
3265
		unlock_page(page);
3266
		put_page(page);
3267 3268

		index++;
3269
		balance_dirty_pages_ratelimited(inode->i_mapping);
3270
		btrfs_throttle(fs_info);
3271
	}
3272
	WARN_ON(nr != cluster->nr);
3273
out:
3274 3275 3276 3277 3278
	kfree(ra);
	return ret;
}

static noinline_for_stack
3279 3280
int relocate_data_extent(struct inode *inode, struct btrfs_key *extent_key,
			 struct file_extent_cluster *cluster)
3281
{
3282
	int ret;
3283

3284 3285 3286 3287 3288
	if (cluster->nr > 0 && extent_key->objectid != cluster->end + 1) {
		ret = relocate_file_extent_cluster(inode, cluster);
		if (ret)
			return ret;
		cluster->nr = 0;
3289 3290
	}

3291 3292 3293 3294 3295 3296 3297 3298 3299 3300 3301 3302 3303 3304 3305
	if (!cluster->nr)
		cluster->start = extent_key->objectid;
	else
		BUG_ON(cluster->nr >= MAX_EXTENTS);
	cluster->end = extent_key->objectid + extent_key->offset - 1;
	cluster->boundary[cluster->nr] = extent_key->objectid;
	cluster->nr++;

	if (cluster->nr >= MAX_EXTENTS) {
		ret = relocate_file_extent_cluster(inode, cluster);
		if (ret)
			return ret;
		cluster->nr = 0;
	}
	return 0;
3306 3307 3308 3309 3310 3311 3312 3313 3314 3315 3316 3317 3318 3319 3320 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 3331 3332 3333 3334 3335 3336 3337 3338 3339 3340 3341 3342 3343 3344 3345 3346 3347 3348 3349 3350 3351 3352 3353 3354 3355 3356 3357 3358 3359 3360 3361 3362 3363 3364 3365
}

#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
static int get_ref_objectid_v0(struct reloc_control *rc,
			       struct btrfs_path *path,
			       struct btrfs_key *extent_key,
			       u64 *ref_objectid, int *path_change)
{
	struct btrfs_key key;
	struct extent_buffer *leaf;
	struct btrfs_extent_ref_v0 *ref0;
	int ret;
	int slot;

	leaf = path->nodes[0];
	slot = path->slots[0];
	while (1) {
		if (slot >= btrfs_header_nritems(leaf)) {
			ret = btrfs_next_leaf(rc->extent_root, path);
			if (ret < 0)
				return ret;
			BUG_ON(ret > 0);
			leaf = path->nodes[0];
			slot = path->slots[0];
			if (path_change)
				*path_change = 1;
		}
		btrfs_item_key_to_cpu(leaf, &key, slot);
		if (key.objectid != extent_key->objectid)
			return -ENOENT;

		if (key.type != BTRFS_EXTENT_REF_V0_KEY) {
			slot++;
			continue;
		}
		ref0 = btrfs_item_ptr(leaf, slot,
				struct btrfs_extent_ref_v0);
		*ref_objectid = btrfs_ref_objectid_v0(leaf, ref0);
		break;
	}
	return 0;
}
#endif

/*
 * helper to add a tree block to the list.
 * the major work is getting the generation and level of the block
 */
static int add_tree_block(struct reloc_control *rc,
			  struct btrfs_key *extent_key,
			  struct btrfs_path *path,
			  struct rb_root *blocks)
{
	struct extent_buffer *eb;
	struct btrfs_extent_item *ei;
	struct btrfs_tree_block_info *bi;
	struct tree_block *block;
	struct rb_node *rb_node;
	u32 item_size;
	int level = -1;
3366
	u64 generation;
3367 3368 3369 3370

	eb =  path->nodes[0];
	item_size = btrfs_item_size_nr(eb, path->slots[0]);

3371 3372
	if (extent_key->type == BTRFS_METADATA_ITEM_KEY ||
	    item_size >= sizeof(*ei) + sizeof(*bi)) {
3373 3374
		ei = btrfs_item_ptr(eb, path->slots[0],
				struct btrfs_extent_item);
3375 3376 3377 3378 3379 3380
		if (extent_key->type == BTRFS_EXTENT_ITEM_KEY) {
			bi = (struct btrfs_tree_block_info *)(ei + 1);
			level = btrfs_tree_block_level(eb, bi);
		} else {
			level = (int)extent_key->offset;
		}
3381 3382 3383 3384 3385 3386 3387 3388 3389
		generation = btrfs_extent_generation(eb, ei);
	} else {
#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
		u64 ref_owner;
		int ret;

		BUG_ON(item_size != sizeof(struct btrfs_extent_item_v0));
		ret = get_ref_objectid_v0(rc, path, extent_key,
					  &ref_owner, NULL);
3390 3391
		if (ret < 0)
			return ret;
3392 3393 3394 3395 3396 3397 3398 3399 3400
		BUG_ON(ref_owner >= BTRFS_MAX_LEVEL);
		level = (int)ref_owner;
		/* FIXME: get real generation */
		generation = 0;
#else
		BUG();
#endif
	}

3401
	btrfs_release_path(path);
3402 3403 3404 3405 3406 3407 3408 3409

	BUG_ON(level == -1);

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

	block->bytenr = extent_key->objectid;
3410
	block->key.objectid = rc->extent_root->fs_info->nodesize;
3411 3412 3413 3414 3415
	block->key.offset = generation;
	block->level = level;
	block->key_ready = 0;

	rb_node = tree_insert(blocks, block->bytenr, &block->rb_node);
3416 3417
	if (rb_node)
		backref_tree_panic(rb_node, -EEXIST, block->bytenr);
3418 3419 3420 3421 3422 3423 3424 3425 3426 3427 3428

	return 0;
}

/*
 * helper to add tree blocks for backref of type BTRFS_SHARED_DATA_REF_KEY
 */
static int __add_tree_block(struct reloc_control *rc,
			    u64 bytenr, u32 blocksize,
			    struct rb_root *blocks)
{
3429
	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
3430 3431 3432
	struct btrfs_path *path;
	struct btrfs_key key;
	int ret;
3433
	bool skinny = btrfs_fs_incompat(fs_info, SKINNY_METADATA);
3434

3435
	if (tree_block_processed(bytenr, rc))
3436 3437 3438 3439 3440 3441 3442 3443
		return 0;

	if (tree_search(blocks, bytenr))
		return 0;

	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;
3444
again:
3445
	key.objectid = bytenr;
3446 3447 3448 3449 3450 3451 3452
	if (skinny) {
		key.type = BTRFS_METADATA_ITEM_KEY;
		key.offset = (u64)-1;
	} else {
		key.type = BTRFS_EXTENT_ITEM_KEY;
		key.offset = blocksize;
	}
3453 3454 3455 3456 3457 3458 3459

	path->search_commit_root = 1;
	path->skip_locking = 1;
	ret = btrfs_search_slot(NULL, rc->extent_root, &key, path, 0, 0);
	if (ret < 0)
		goto out;

3460 3461 3462 3463 3464 3465 3466 3467 3468 3469 3470 3471 3472 3473 3474 3475 3476
	if (ret > 0 && skinny) {
		if (path->slots[0]) {
			path->slots[0]--;
			btrfs_item_key_to_cpu(path->nodes[0], &key,
					      path->slots[0]);
			if (key.objectid == bytenr &&
			    (key.type == BTRFS_METADATA_ITEM_KEY ||
			     (key.type == BTRFS_EXTENT_ITEM_KEY &&
			      key.offset == blocksize)))
				ret = 0;
		}

		if (ret) {
			skinny = false;
			btrfs_release_path(path);
			goto again;
		}
3477 3478 3479
	}
	BUG_ON(ret);

3480 3481 3482 3483 3484 3485 3486 3487 3488 3489 3490 3491 3492 3493 3494 3495 3496 3497 3498
	ret = add_tree_block(rc, &key, path, blocks);
out:
	btrfs_free_path(path);
	return ret;
}

/*
 * helper to check if the block use full backrefs for pointers in it
 */
static int block_use_full_backref(struct reloc_control *rc,
				  struct extent_buffer *eb)
{
	u64 flags;
	int ret;

	if (btrfs_header_flag(eb, BTRFS_HEADER_FLAG_RELOC) ||
	    btrfs_header_backref_rev(eb) < BTRFS_MIXED_BACKREF_REV)
		return 1;

3499
	ret = btrfs_lookup_extent_info(NULL, rc->extent_root->fs_info,
3500 3501
				       eb->start, btrfs_header_level(eb), 1,
				       NULL, &flags);
3502 3503 3504 3505 3506 3507 3508 3509 3510
	BUG_ON(ret);

	if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)
		ret = 1;
	else
		ret = 0;
	return ret;
}

3511
static int delete_block_group_cache(struct btrfs_fs_info *fs_info,
3512 3513 3514
				    struct btrfs_block_group_cache *block_group,
				    struct inode *inode,
				    u64 ino)
3515 3516 3517 3518 3519 3520 3521 3522 3523 3524 3525 3526 3527 3528
{
	struct btrfs_key key;
	struct btrfs_root *root = fs_info->tree_root;
	struct btrfs_trans_handle *trans;
	int ret = 0;

	if (inode)
		goto truncate;

	key.objectid = ino;
	key.type = BTRFS_INODE_ITEM_KEY;
	key.offset = 0;

	inode = btrfs_iget(fs_info->sb, &key, root, NULL);
3529 3530
	if (IS_ERR(inode) || is_bad_inode(inode)) {
		if (!IS_ERR(inode))
3531 3532 3533 3534 3535
			iput(inode);
		return -ENOENT;
	}

truncate:
3536
	ret = btrfs_check_trunc_cache_free_space(fs_info,
3537 3538 3539 3540
						 &fs_info->global_block_rsv);
	if (ret)
		goto out;

3541
	trans = btrfs_join_transaction(root);
3542
	if (IS_ERR(trans)) {
3543
		ret = PTR_ERR(trans);
3544 3545 3546
		goto out;
	}

3547
	ret = btrfs_truncate_free_space_cache(trans, block_group, inode);
3548

3549
	btrfs_end_transaction(trans);
3550
	btrfs_btree_balance_dirty(fs_info);
3551 3552 3553 3554 3555
out:
	iput(inode);
	return ret;
}

3556 3557 3558 3559 3560 3561 3562 3563 3564 3565
/*
 * helper to add tree blocks for backref of type BTRFS_EXTENT_DATA_REF_KEY
 * this function scans fs tree to find blocks reference the data extent
 */
static int find_data_references(struct reloc_control *rc,
				struct btrfs_key *extent_key,
				struct extent_buffer *leaf,
				struct btrfs_extent_data_ref *ref,
				struct rb_root *blocks)
{
3566
	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
3567 3568 3569 3570 3571 3572 3573 3574 3575 3576 3577 3578 3579 3580 3581 3582 3583 3584 3585 3586 3587
	struct btrfs_path *path;
	struct tree_block *block;
	struct btrfs_root *root;
	struct btrfs_file_extent_item *fi;
	struct rb_node *rb_node;
	struct btrfs_key key;
	u64 ref_root;
	u64 ref_objectid;
	u64 ref_offset;
	u32 ref_count;
	u32 nritems;
	int err = 0;
	int added = 0;
	int counted;
	int ret;

	ref_root = btrfs_extent_data_ref_root(leaf, ref);
	ref_objectid = btrfs_extent_data_ref_objectid(leaf, ref);
	ref_offset = btrfs_extent_data_ref_offset(leaf, ref);
	ref_count = btrfs_extent_data_ref_count(leaf, ref);

3588 3589 3590 3591 3592
	/*
	 * This is an extent belonging to the free space cache, lets just delete
	 * it and redo the search.
	 */
	if (ref_root == BTRFS_ROOT_TREE_OBJECTID) {
3593
		ret = delete_block_group_cache(fs_info, rc->block_group,
3594 3595 3596 3597 3598 3599 3600 3601 3602
					       NULL, ref_objectid);
		if (ret != -ENOENT)
			return ret;
		ret = 0;
	}

	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;
3603
	path->reada = READA_FORWARD;
3604

3605
	root = read_fs_root(fs_info, ref_root);
3606 3607 3608 3609 3610 3611 3612
	if (IS_ERR(root)) {
		err = PTR_ERR(root);
		goto out;
	}

	key.objectid = ref_objectid;
	key.type = BTRFS_EXTENT_DATA_KEY;
3613 3614 3615 3616
	if (ref_offset > ((u64)-1 << 32))
		key.offset = 0;
	else
		key.offset = ref_offset;
3617 3618 3619 3620 3621 3622 3623 3624 3625 3626 3627 3628 3629 3630 3631 3632 3633 3634 3635 3636 3637 3638 3639 3640 3641 3642 3643 3644 3645 3646 3647 3648 3649 3650

	path->search_commit_root = 1;
	path->skip_locking = 1;
	ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
	if (ret < 0) {
		err = ret;
		goto out;
	}

	leaf = path->nodes[0];
	nritems = btrfs_header_nritems(leaf);
	/*
	 * the references in tree blocks that use full backrefs
	 * are not counted in
	 */
	if (block_use_full_backref(rc, leaf))
		counted = 0;
	else
		counted = 1;
	rb_node = tree_search(blocks, leaf->start);
	if (rb_node) {
		if (counted)
			added = 1;
		else
			path->slots[0] = nritems;
	}

	while (ref_count > 0) {
		while (path->slots[0] >= nritems) {
			ret = btrfs_next_leaf(root, path);
			if (ret < 0) {
				err = ret;
				goto out;
			}
3651
			if (WARN_ON(ret > 0))
3652 3653 3654 3655 3656 3657 3658 3659 3660 3661 3662 3663 3664 3665 3666 3667 3668 3669 3670 3671
				goto out;

			leaf = path->nodes[0];
			nritems = btrfs_header_nritems(leaf);
			added = 0;

			if (block_use_full_backref(rc, leaf))
				counted = 0;
			else
				counted = 1;
			rb_node = tree_search(blocks, leaf->start);
			if (rb_node) {
				if (counted)
					added = 1;
				else
					path->slots[0] = nritems;
			}
		}

		btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
3672 3673
		if (WARN_ON(key.objectid != ref_objectid ||
		    key.type != BTRFS_EXTENT_DATA_KEY))
3674 3675 3676 3677 3678 3679 3680 3681 3682 3683 3684 3685 3686 3687 3688 3689 3690 3691 3692 3693 3694 3695
			break;

		fi = btrfs_item_ptr(leaf, path->slots[0],
				    struct btrfs_file_extent_item);

		if (btrfs_file_extent_type(leaf, fi) ==
		    BTRFS_FILE_EXTENT_INLINE)
			goto next;

		if (btrfs_file_extent_disk_bytenr(leaf, fi) !=
		    extent_key->objectid)
			goto next;

		key.offset -= btrfs_file_extent_offset(leaf, fi);
		if (key.offset != ref_offset)
			goto next;

		if (counted)
			ref_count--;
		if (added)
			goto next;

3696
		if (!tree_block_processed(leaf->start, rc)) {
3697 3698 3699 3700 3701 3702 3703 3704 3705 3706 3707
			block = kmalloc(sizeof(*block), GFP_NOFS);
			if (!block) {
				err = -ENOMEM;
				break;
			}
			block->bytenr = leaf->start;
			btrfs_item_key_to_cpu(leaf, &block->key, 0);
			block->level = 0;
			block->key_ready = 1;
			rb_node = tree_insert(blocks, block->bytenr,
					      &block->rb_node);
3708 3709 3710
			if (rb_node)
				backref_tree_panic(rb_node, -EEXIST,
						   block->bytenr);
3711 3712 3713 3714 3715 3716 3717 3718 3719 3720 3721 3722 3723 3724 3725
		}
		if (counted)
			added = 1;
		else
			path->slots[0] = nritems;
next:
		path->slots[0]++;

	}
out:
	btrfs_free_path(path);
	return err;
}

/*
L
Liu Bo 已提交
3726
 * helper to find all tree blocks that reference a given data extent
3727 3728 3729 3730 3731 3732 3733 3734 3735 3736 3737 3738 3739
 */
static noinline_for_stack
int add_data_references(struct reloc_control *rc,
			struct btrfs_key *extent_key,
			struct btrfs_path *path,
			struct rb_root *blocks)
{
	struct btrfs_key key;
	struct extent_buffer *eb;
	struct btrfs_extent_data_ref *dref;
	struct btrfs_extent_inline_ref *iref;
	unsigned long ptr;
	unsigned long end;
3740
	u32 blocksize = rc->extent_root->fs_info->nodesize;
3741
	int ret = 0;
3742 3743 3744 3745 3746 3747 3748 3749 3750 3751 3752 3753 3754 3755 3756 3757 3758 3759 3760 3761 3762 3763 3764 3765 3766 3767
	int err = 0;

	eb = path->nodes[0];
	ptr = btrfs_item_ptr_offset(eb, path->slots[0]);
	end = ptr + btrfs_item_size_nr(eb, path->slots[0]);
#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
	if (ptr + sizeof(struct btrfs_extent_item_v0) == end)
		ptr = end;
	else
#endif
		ptr += sizeof(struct btrfs_extent_item);

	while (ptr < end) {
		iref = (struct btrfs_extent_inline_ref *)ptr;
		key.type = btrfs_extent_inline_ref_type(eb, iref);
		if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
			key.offset = btrfs_extent_inline_ref_offset(eb, iref);
			ret = __add_tree_block(rc, key.offset, blocksize,
					       blocks);
		} else if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
			dref = (struct btrfs_extent_data_ref *)(&iref->offset);
			ret = find_data_references(rc, extent_key,
						   eb, dref, blocks);
		} else {
			BUG();
		}
3768 3769 3770 3771
		if (ret) {
			err = ret;
			goto out;
		}
3772 3773 3774 3775 3776 3777 3778 3779 3780 3781 3782 3783 3784 3785 3786 3787 3788 3789 3790 3791 3792 3793 3794 3795 3796 3797 3798 3799 3800 3801 3802 3803 3804 3805 3806 3807 3808 3809 3810 3811 3812 3813 3814 3815 3816
		ptr += btrfs_extent_inline_ref_size(key.type);
	}
	WARN_ON(ptr > end);

	while (1) {
		cond_resched();
		eb = path->nodes[0];
		if (path->slots[0] >= btrfs_header_nritems(eb)) {
			ret = btrfs_next_leaf(rc->extent_root, path);
			if (ret < 0) {
				err = ret;
				break;
			}
			if (ret > 0)
				break;
			eb = path->nodes[0];
		}

		btrfs_item_key_to_cpu(eb, &key, path->slots[0]);
		if (key.objectid != extent_key->objectid)
			break;

#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
		if (key.type == BTRFS_SHARED_DATA_REF_KEY ||
		    key.type == BTRFS_EXTENT_REF_V0_KEY) {
#else
		BUG_ON(key.type == BTRFS_EXTENT_REF_V0_KEY);
		if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
#endif
			ret = __add_tree_block(rc, key.offset, blocksize,
					       blocks);
		} else if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
			dref = btrfs_item_ptr(eb, path->slots[0],
					      struct btrfs_extent_data_ref);
			ret = find_data_references(rc, extent_key,
						   eb, dref, blocks);
		} else {
			ret = 0;
		}
		if (ret) {
			err = ret;
			break;
		}
		path->slots[0]++;
	}
3817
out:
3818
	btrfs_release_path(path);
3819 3820 3821 3822 3823 3824
	if (err)
		free_block_list(blocks);
	return err;
}

/*
L
Liu Bo 已提交
3825
 * helper to find next unprocessed extent
3826 3827
 */
static noinline_for_stack
3828
int find_next_extent(struct reloc_control *rc, struct btrfs_path *path,
3829
		     struct btrfs_key *extent_key)
3830
{
3831
	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
3832 3833 3834 3835 3836 3837 3838 3839 3840 3841 3842 3843 3844 3845 3846 3847 3848 3849 3850 3851 3852 3853 3854 3855 3856 3857 3858 3859 3860 3861 3862 3863 3864 3865 3866 3867 3868 3869
	struct btrfs_key key;
	struct extent_buffer *leaf;
	u64 start, end, last;
	int ret;

	last = rc->block_group->key.objectid + rc->block_group->key.offset;
	while (1) {
		cond_resched();
		if (rc->search_start >= last) {
			ret = 1;
			break;
		}

		key.objectid = rc->search_start;
		key.type = BTRFS_EXTENT_ITEM_KEY;
		key.offset = 0;

		path->search_commit_root = 1;
		path->skip_locking = 1;
		ret = btrfs_search_slot(NULL, rc->extent_root, &key, path,
					0, 0);
		if (ret < 0)
			break;
next:
		leaf = path->nodes[0];
		if (path->slots[0] >= btrfs_header_nritems(leaf)) {
			ret = btrfs_next_leaf(rc->extent_root, path);
			if (ret != 0)
				break;
			leaf = path->nodes[0];
		}

		btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
		if (key.objectid >= last) {
			ret = 1;
			break;
		}

3870 3871 3872 3873 3874 3875 3876
		if (key.type != BTRFS_EXTENT_ITEM_KEY &&
		    key.type != BTRFS_METADATA_ITEM_KEY) {
			path->slots[0]++;
			goto next;
		}

		if (key.type == BTRFS_EXTENT_ITEM_KEY &&
3877 3878 3879 3880 3881
		    key.objectid + key.offset <= rc->search_start) {
			path->slots[0]++;
			goto next;
		}

3882
		if (key.type == BTRFS_METADATA_ITEM_KEY &&
3883
		    key.objectid + fs_info->nodesize <=
3884 3885 3886 3887 3888
		    rc->search_start) {
			path->slots[0]++;
			goto next;
		}

3889 3890
		ret = find_first_extent_bit(&rc->processed_blocks,
					    key.objectid, &start, &end,
3891
					    EXTENT_DIRTY, NULL);
3892 3893

		if (ret == 0 && start <= key.objectid) {
3894
			btrfs_release_path(path);
3895 3896
			rc->search_start = end + 1;
		} else {
3897 3898 3899 3900
			if (key.type == BTRFS_EXTENT_ITEM_KEY)
				rc->search_start = key.objectid + key.offset;
			else
				rc->search_start = key.objectid +
3901
					fs_info->nodesize;
3902
			memcpy(extent_key, &key, sizeof(key));
3903 3904 3905
			return 0;
		}
	}
3906
	btrfs_release_path(path);
3907 3908 3909 3910 3911 3912
	return ret;
}

static void set_reloc_control(struct reloc_control *rc)
{
	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
C
Chris Mason 已提交
3913 3914

	mutex_lock(&fs_info->reloc_mutex);
3915
	fs_info->reloc_ctl = rc;
C
Chris Mason 已提交
3916
	mutex_unlock(&fs_info->reloc_mutex);
3917 3918 3919 3920 3921
}

static void unset_reloc_control(struct reloc_control *rc)
{
	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
C
Chris Mason 已提交
3922 3923

	mutex_lock(&fs_info->reloc_mutex);
3924
	fs_info->reloc_ctl = NULL;
C
Chris Mason 已提交
3925
	mutex_unlock(&fs_info->reloc_mutex);
3926 3927 3928 3929 3930 3931 3932 3933 3934 3935 3936 3937 3938 3939 3940 3941
}

static int check_extent_flags(u64 flags)
{
	if ((flags & BTRFS_EXTENT_FLAG_DATA) &&
	    (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK))
		return 1;
	if (!(flags & BTRFS_EXTENT_FLAG_DATA) &&
	    !(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK))
		return 1;
	if ((flags & BTRFS_EXTENT_FLAG_DATA) &&
	    (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF))
		return 1;
	return 0;
}

3942 3943 3944 3945
static noinline_for_stack
int prepare_to_relocate(struct reloc_control *rc)
{
	struct btrfs_trans_handle *trans;
3946
	int ret;
3947

3948
	rc->block_rsv = btrfs_alloc_block_rsv(rc->extent_root->fs_info,
3949
					      BTRFS_BLOCK_RSV_TEMP);
3950 3951 3952 3953 3954 3955 3956 3957
	if (!rc->block_rsv)
		return -ENOMEM;

	memset(&rc->cluster, 0, sizeof(rc->cluster));
	rc->search_start = rc->block_group->key.objectid;
	rc->extents_found = 0;
	rc->nodes_relocated = 0;
	rc->merging_rsv_size = 0;
3958
	rc->reserved_bytes = 0;
3959
	rc->block_rsv->size = rc->extent_root->fs_info->nodesize *
3960
			      RELOCATION_RESERVED_NODES;
3961 3962 3963 3964 3965
	ret = btrfs_block_rsv_refill(rc->extent_root,
				     rc->block_rsv, rc->block_rsv->size,
				     BTRFS_RESERVE_FLUSH_ALL);
	if (ret)
		return ret;
3966 3967 3968 3969

	rc->create_reloc_tree = 1;
	set_reloc_control(rc);

3970
	trans = btrfs_join_transaction(rc->extent_root);
3971 3972 3973 3974 3975 3976 3977 3978 3979
	if (IS_ERR(trans)) {
		unset_reloc_control(rc);
		/*
		 * extent tree is not a ref_cow tree and has no reloc_root to
		 * cleanup.  And callers are responsible to free the above
		 * block rsv.
		 */
		return PTR_ERR(trans);
	}
3980
	btrfs_commit_transaction(trans);
3981 3982
	return 0;
}
3983

3984 3985
static noinline_for_stack int relocate_block_group(struct reloc_control *rc)
{
3986
	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
3987 3988 3989 3990 3991 3992 3993 3994 3995
	struct rb_root blocks = RB_ROOT;
	struct btrfs_key key;
	struct btrfs_trans_handle *trans = NULL;
	struct btrfs_path *path;
	struct btrfs_extent_item *ei;
	u64 flags;
	u32 item_size;
	int ret;
	int err = 0;
3996
	int progress = 0;
3997 3998

	path = btrfs_alloc_path();
3999
	if (!path)
4000
		return -ENOMEM;
4001
	path->reada = READA_FORWARD;
4002

4003 4004 4005 4006 4007
	ret = prepare_to_relocate(rc);
	if (ret) {
		err = ret;
		goto out_free;
	}
4008 4009

	while (1) {
4010 4011 4012 4013 4014 4015 4016 4017
		rc->reserved_bytes = 0;
		ret = btrfs_block_rsv_refill(rc->extent_root,
					rc->block_rsv, rc->block_rsv->size,
					BTRFS_RESERVE_FLUSH_ALL);
		if (ret) {
			err = ret;
			break;
		}
4018
		progress++;
4019
		trans = btrfs_start_transaction(rc->extent_root, 0);
4020 4021 4022 4023 4024
		if (IS_ERR(trans)) {
			err = PTR_ERR(trans);
			trans = NULL;
			break;
		}
4025
restart:
4026
		if (update_backref_cache(trans, &rc->backref_cache)) {
4027
			btrfs_end_transaction(trans);
4028 4029 4030
			continue;
		}

4031
		ret = find_next_extent(rc, path, &key);
4032 4033 4034 4035 4036 4037 4038 4039 4040
		if (ret < 0)
			err = ret;
		if (ret != 0)
			break;

		rc->extents_found++;

		ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
				    struct btrfs_extent_item);
4041
		item_size = btrfs_item_size_nr(path->nodes[0], path->slots[0]);
4042 4043 4044 4045 4046 4047 4048 4049 4050 4051 4052 4053 4054 4055
		if (item_size >= sizeof(*ei)) {
			flags = btrfs_extent_flags(path->nodes[0], ei);
			ret = check_extent_flags(flags);
			BUG_ON(ret);

		} else {
#ifdef BTRFS_COMPAT_EXTENT_TREE_V0
			u64 ref_owner;
			int path_change = 0;

			BUG_ON(item_size !=
			       sizeof(struct btrfs_extent_item_v0));
			ret = get_ref_objectid_v0(rc, path, &key, &ref_owner,
						  &path_change);
4056 4057 4058 4059
			if (ret < 0) {
				err = ret;
				break;
			}
4060 4061 4062 4063 4064 4065
			if (ref_owner < BTRFS_FIRST_FREE_OBJECTID)
				flags = BTRFS_EXTENT_FLAG_TREE_BLOCK;
			else
				flags = BTRFS_EXTENT_FLAG_DATA;

			if (path_change) {
4066
				btrfs_release_path(path);
4067 4068 4069 4070 4071 4072 4073 4074 4075 4076 4077 4078 4079 4080 4081 4082 4083 4084 4085

				path->search_commit_root = 1;
				path->skip_locking = 1;
				ret = btrfs_search_slot(NULL, rc->extent_root,
							&key, path, 0, 0);
				if (ret < 0) {
					err = ret;
					break;
				}
				BUG_ON(ret > 0);
			}
#else
			BUG();
#endif
		}

		if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
			ret = add_tree_block(rc, &key, path, &blocks);
		} else if (rc->stage == UPDATE_DATA_PTRS &&
4086
			   (flags & BTRFS_EXTENT_FLAG_DATA)) {
4087 4088
			ret = add_data_references(rc, &key, path, &blocks);
		} else {
4089
			btrfs_release_path(path);
4090 4091 4092
			ret = 0;
		}
		if (ret < 0) {
4093
			err = ret;
4094 4095 4096 4097 4098 4099
			break;
		}

		if (!RB_EMPTY_ROOT(&blocks)) {
			ret = relocate_tree_blocks(trans, rc, &blocks);
			if (ret < 0) {
4100 4101 4102 4103 4104 4105
				/*
				 * if we fail to relocate tree blocks, force to update
				 * backref cache when committing transaction.
				 */
				rc->backref_cache.last_trans = trans->transid - 1;

4106 4107 4108 4109 4110 4111 4112 4113 4114
				if (ret != -EAGAIN) {
					err = ret;
					break;
				}
				rc->extents_found--;
				rc->search_start = key.objectid;
			}
		}

4115
		btrfs_end_transaction_throttle(trans);
4116
		btrfs_btree_balance_dirty(fs_info);
4117 4118 4119 4120 4121
		trans = NULL;

		if (rc->stage == MOVE_DATA_EXTENTS &&
		    (flags & BTRFS_EXTENT_FLAG_DATA)) {
			rc->found_file_extent = 1;
4122
			ret = relocate_data_extent(rc->data_inode,
4123
						   &key, &rc->cluster);
4124 4125 4126 4127 4128 4129
			if (ret < 0) {
				err = ret;
				break;
			}
		}
	}
4130
	if (trans && progress && err == -ENOSPC) {
4131
		ret = btrfs_force_chunk_alloc(trans, fs_info,
4132
					      rc->block_group->flags);
4133
		if (ret == 1) {
4134 4135 4136 4137 4138
			err = 0;
			progress = 0;
			goto restart;
		}
	}
4139

4140
	btrfs_release_path(path);
4141
	clear_extent_bits(&rc->processed_blocks, 0, (u64)-1, EXTENT_DIRTY);
4142 4143

	if (trans) {
4144
		btrfs_end_transaction_throttle(trans);
4145
		btrfs_btree_balance_dirty(fs_info);
4146 4147
	}

4148
	if (!err) {
4149 4150
		ret = relocate_file_extent_cluster(rc->data_inode,
						   &rc->cluster);
4151 4152 4153 4154
		if (ret < 0)
			err = ret;
	}

4155 4156
	rc->create_reloc_tree = 0;
	set_reloc_control(rc);
4157

4158
	backref_cache_cleanup(&rc->backref_cache);
4159
	btrfs_block_rsv_release(fs_info, rc->block_rsv, (u64)-1);
4160

4161
	err = prepare_to_merge(rc, err);
4162 4163 4164

	merge_reloc_roots(rc);

4165
	rc->merge_reloc_tree = 0;
4166
	unset_reloc_control(rc);
4167
	btrfs_block_rsv_release(fs_info, rc->block_rsv, (u64)-1);
4168 4169

	/* get rid of pinned extents */
4170
	trans = btrfs_join_transaction(rc->extent_root);
4171
	if (IS_ERR(trans)) {
4172
		err = PTR_ERR(trans);
4173 4174
		goto out_free;
	}
4175
	btrfs_commit_transaction(trans);
4176
out_free:
4177
	btrfs_free_block_rsv(fs_info, rc->block_rsv);
4178
	btrfs_free_path(path);
4179 4180 4181 4182
	return err;
}

static int __insert_orphan_inode(struct btrfs_trans_handle *trans,
4183
				 struct btrfs_root *root, u64 objectid)
4184 4185 4186 4187 4188 4189 4190 4191 4192 4193 4194 4195 4196 4197 4198 4199
{
	struct btrfs_path *path;
	struct btrfs_inode_item *item;
	struct extent_buffer *leaf;
	int ret;

	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;

	ret = btrfs_insert_empty_inode(trans, root, path, objectid);
	if (ret)
		goto out;

	leaf = path->nodes[0];
	item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_inode_item);
4200
	memzero_extent_buffer(leaf, (unsigned long)item, sizeof(*item));
4201
	btrfs_set_inode_generation(leaf, item, 1);
4202
	btrfs_set_inode_size(leaf, item, 0);
4203
	btrfs_set_inode_mode(leaf, item, S_IFREG | 0600);
4204 4205
	btrfs_set_inode_flags(leaf, item, BTRFS_INODE_NOCOMPRESS |
					  BTRFS_INODE_PREALLOC);
4206 4207 4208 4209 4210 4211 4212 4213 4214 4215
	btrfs_mark_buffer_dirty(leaf);
out:
	btrfs_free_path(path);
	return ret;
}

/*
 * helper to create inode for data relocation.
 * the inode is in data relocation tree and its link count is 0
 */
4216 4217 4218
static noinline_for_stack
struct inode *create_reloc_inode(struct btrfs_fs_info *fs_info,
				 struct btrfs_block_group_cache *group)
4219 4220 4221 4222 4223
{
	struct inode *inode = NULL;
	struct btrfs_trans_handle *trans;
	struct btrfs_root *root;
	struct btrfs_key key;
4224
	u64 objectid;
4225 4226 4227 4228 4229 4230
	int err = 0;

	root = read_fs_root(fs_info, BTRFS_DATA_RELOC_TREE_OBJECTID);
	if (IS_ERR(root))
		return ERR_CAST(root);

4231
	trans = btrfs_start_transaction(root, 6);
4232 4233
	if (IS_ERR(trans))
		return ERR_CAST(trans);
4234

4235
	err = btrfs_find_free_objectid(root, &objectid);
4236 4237 4238
	if (err)
		goto out;

4239
	err = __insert_orphan_inode(trans, root, objectid);
4240 4241 4242 4243 4244
	BUG_ON(err);

	key.objectid = objectid;
	key.type = BTRFS_INODE_ITEM_KEY;
	key.offset = 0;
4245
	inode = btrfs_iget(fs_info->sb, &key, root, NULL);
4246 4247 4248 4249 4250
	BUG_ON(IS_ERR(inode) || is_bad_inode(inode));
	BTRFS_I(inode)->index_cnt = group->key.objectid;

	err = btrfs_orphan_add(trans, inode);
out:
4251
	btrfs_end_transaction(trans);
4252
	btrfs_btree_balance_dirty(fs_info);
4253 4254 4255 4256 4257 4258 4259 4260
	if (err) {
		if (inode)
			iput(inode);
		inode = ERR_PTR(err);
	}
	return inode;
}

4261
static struct reloc_control *alloc_reloc_control(struct btrfs_fs_info *fs_info)
4262 4263 4264 4265 4266 4267 4268 4269 4270 4271
{
	struct reloc_control *rc;

	rc = kzalloc(sizeof(*rc), GFP_NOFS);
	if (!rc)
		return NULL;

	INIT_LIST_HEAD(&rc->reloc_roots);
	backref_cache_init(&rc->backref_cache);
	mapping_tree_init(&rc->reloc_root_tree);
4272 4273
	extent_io_tree_init(&rc->processed_blocks,
			    fs_info->btree_inode->i_mapping);
4274 4275 4276
	return rc;
}

4277 4278 4279 4280 4281 4282 4283 4284 4285 4286 4287 4288 4289 4290 4291 4292 4293 4294 4295 4296 4297 4298 4299 4300 4301 4302 4303 4304 4305 4306 4307 4308 4309 4310 4311 4312 4313 4314 4315
/*
 * Print the block group being relocated
 */
static void describe_relocation(struct btrfs_fs_info *fs_info,
				struct btrfs_block_group_cache *block_group)
{
	char buf[128];		/* prefixed by a '|' that'll be dropped */
	u64 flags = block_group->flags;

	/* Shouldn't happen */
	if (!flags) {
		strcpy(buf, "|NONE");
	} else {
		char *bp = buf;

#define DESCRIBE_FLAG(f, d) \
		if (flags & BTRFS_BLOCK_GROUP_##f) { \
			bp += snprintf(bp, buf - bp + sizeof(buf), "|%s", d); \
			flags &= ~BTRFS_BLOCK_GROUP_##f; \
		}
		DESCRIBE_FLAG(DATA,     "data");
		DESCRIBE_FLAG(SYSTEM,   "system");
		DESCRIBE_FLAG(METADATA, "metadata");
		DESCRIBE_FLAG(RAID0,    "raid0");
		DESCRIBE_FLAG(RAID1,    "raid1");
		DESCRIBE_FLAG(DUP,      "dup");
		DESCRIBE_FLAG(RAID10,   "raid10");
		DESCRIBE_FLAG(RAID5,    "raid5");
		DESCRIBE_FLAG(RAID6,    "raid6");
		if (flags)
			snprintf(buf, buf - bp + sizeof(buf), "|0x%llx", flags);
#undef DESCRIBE_FLAG
	}

	btrfs_info(fs_info,
		   "relocating block group %llu flags %s",
		   block_group->key.objectid, buf + 1);
}

4316 4317 4318
/*
 * function to relocate all extents in a block group.
 */
4319
int btrfs_relocate_block_group(struct btrfs_fs_info *fs_info, u64 group_start)
4320
{
4321
	struct btrfs_root *extent_root = fs_info->extent_root;
4322
	struct reloc_control *rc;
4323 4324
	struct inode *inode;
	struct btrfs_path *path;
4325
	int ret;
4326
	int rw = 0;
4327 4328
	int err = 0;

4329
	rc = alloc_reloc_control(fs_info);
4330 4331 4332
	if (!rc)
		return -ENOMEM;

4333
	rc->extent_root = extent_root;
4334

4335 4336 4337
	rc->block_group = btrfs_lookup_block_group(fs_info, group_start);
	BUG_ON(!rc->block_group);

4338
	ret = btrfs_inc_block_group_ro(fs_info, rc->block_group);
4339 4340 4341
	if (ret) {
		err = ret;
		goto out;
4342
	}
4343
	rw = 1;
4344

4345 4346 4347 4348 4349 4350
	path = btrfs_alloc_path();
	if (!path) {
		err = -ENOMEM;
		goto out;
	}

4351
	inode = lookup_free_space_inode(fs_info, rc->block_group, path);
4352 4353 4354
	btrfs_free_path(path);

	if (!IS_ERR(inode))
4355
		ret = delete_block_group_cache(fs_info, rc->block_group, inode, 0);
4356 4357 4358 4359 4360 4361 4362 4363
	else
		ret = PTR_ERR(inode);

	if (ret && ret != -ENOENT) {
		err = ret;
		goto out;
	}

4364 4365 4366 4367 4368 4369 4370
	rc->data_inode = create_reloc_inode(fs_info, rc->block_group);
	if (IS_ERR(rc->data_inode)) {
		err = PTR_ERR(rc->data_inode);
		rc->data_inode = NULL;
		goto out;
	}

4371
	describe_relocation(fs_info, rc->block_group);
4372

4373
	btrfs_wait_block_group_reservations(rc->block_group);
4374
	btrfs_wait_nocow_writers(rc->block_group);
4375 4376 4377
	btrfs_wait_ordered_roots(fs_info, -1,
				 rc->block_group->key.objectid,
				 rc->block_group->key.offset);
4378 4379

	while (1) {
4380
		mutex_lock(&fs_info->cleaner_mutex);
4381
		ret = relocate_block_group(rc);
4382
		mutex_unlock(&fs_info->cleaner_mutex);
4383 4384
		if (ret < 0) {
			err = ret;
4385
			goto out;
4386 4387 4388 4389 4390
		}

		if (rc->extents_found == 0)
			break;

4391
		btrfs_info(fs_info, "found %llu extents", rc->extents_found);
4392 4393

		if (rc->stage == MOVE_DATA_EXTENTS && rc->found_file_extent) {
4394 4395 4396 4397 4398 4399
			ret = btrfs_wait_ordered_range(rc->data_inode, 0,
						       (u64)-1);
			if (ret) {
				err = ret;
				goto out;
			}
4400 4401 4402 4403 4404 4405 4406 4407 4408 4409
			invalidate_mapping_pages(rc->data_inode->i_mapping,
						 0, -1);
			rc->stage = UPDATE_DATA_PTRS;
		}
	}

	WARN_ON(rc->block_group->pinned > 0);
	WARN_ON(rc->block_group->reserved > 0);
	WARN_ON(btrfs_block_group_used(&rc->block_group->item) > 0);
out:
4410
	if (err && rw)
4411
		btrfs_dec_block_group_ro(rc->block_group);
4412 4413 4414 4415 4416 4417
	iput(rc->data_inode);
	btrfs_put_block_group(rc->block_group);
	kfree(rc);
	return err;
}

4418 4419
static noinline_for_stack int mark_garbage_root(struct btrfs_root *root)
{
4420
	struct btrfs_fs_info *fs_info = root->fs_info;
4421
	struct btrfs_trans_handle *trans;
4422
	int ret, err;
4423

4424
	trans = btrfs_start_transaction(fs_info->tree_root, 0);
4425 4426
	if (IS_ERR(trans))
		return PTR_ERR(trans);
4427 4428 4429 4430 4431

	memset(&root->root_item.drop_progress, 0,
		sizeof(root->root_item.drop_progress));
	root->root_item.drop_level = 0;
	btrfs_set_root_refs(&root->root_item, 0);
4432
	ret = btrfs_update_root(trans, fs_info->tree_root,
4433 4434
				&root->root_key, &root->root_item);

4435
	err = btrfs_end_transaction(trans);
4436 4437 4438
	if (err)
		return err;
	return ret;
4439 4440
}

4441 4442 4443 4444 4445 4446 4447 4448
/*
 * recover relocation interrupted by system crash.
 *
 * this function resumes merging reloc trees with corresponding fs trees.
 * this is important for keeping the sharing of tree blocks
 */
int btrfs_recover_relocation(struct btrfs_root *root)
{
4449
	struct btrfs_fs_info *fs_info = root->fs_info;
4450 4451 4452 4453 4454 4455 4456 4457 4458 4459 4460 4461 4462 4463
	LIST_HEAD(reloc_roots);
	struct btrfs_key key;
	struct btrfs_root *fs_root;
	struct btrfs_root *reloc_root;
	struct btrfs_path *path;
	struct extent_buffer *leaf;
	struct reloc_control *rc = NULL;
	struct btrfs_trans_handle *trans;
	int ret;
	int err = 0;

	path = btrfs_alloc_path();
	if (!path)
		return -ENOMEM;
4464
	path->reada = READA_BACK;
4465 4466 4467 4468 4469 4470

	key.objectid = BTRFS_TREE_RELOC_OBJECTID;
	key.type = BTRFS_ROOT_ITEM_KEY;
	key.offset = (u64)-1;

	while (1) {
4471
		ret = btrfs_search_slot(NULL, fs_info->tree_root, &key,
4472 4473 4474 4475 4476 4477 4478 4479 4480 4481 4482 4483
					path, 0, 0);
		if (ret < 0) {
			err = ret;
			goto out;
		}
		if (ret > 0) {
			if (path->slots[0] == 0)
				break;
			path->slots[0]--;
		}
		leaf = path->nodes[0];
		btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
4484
		btrfs_release_path(path);
4485 4486 4487 4488 4489

		if (key.objectid != BTRFS_TREE_RELOC_OBJECTID ||
		    key.type != BTRFS_ROOT_ITEM_KEY)
			break;

4490
		reloc_root = btrfs_read_fs_root(root, &key);
4491 4492 4493 4494 4495 4496 4497 4498
		if (IS_ERR(reloc_root)) {
			err = PTR_ERR(reloc_root);
			goto out;
		}

		list_add(&reloc_root->root_list, &reloc_roots);

		if (btrfs_root_refs(&reloc_root->root_item) > 0) {
4499
			fs_root = read_fs_root(fs_info,
4500 4501
					       reloc_root->root_key.offset);
			if (IS_ERR(fs_root)) {
4502 4503 4504 4505 4506
				ret = PTR_ERR(fs_root);
				if (ret != -ENOENT) {
					err = ret;
					goto out;
				}
4507 4508 4509 4510 4511
				ret = mark_garbage_root(reloc_root);
				if (ret < 0) {
					err = ret;
					goto out;
				}
4512 4513 4514 4515 4516 4517 4518 4519
			}
		}

		if (key.offset == 0)
			break;

		key.offset--;
	}
4520
	btrfs_release_path(path);
4521 4522 4523 4524

	if (list_empty(&reloc_roots))
		goto out;

4525
	rc = alloc_reloc_control(fs_info);
4526 4527 4528 4529 4530
	if (!rc) {
		err = -ENOMEM;
		goto out;
	}

4531
	rc->extent_root = fs_info->extent_root;
4532 4533 4534

	set_reloc_control(rc);

4535
	trans = btrfs_join_transaction(rc->extent_root);
4536 4537 4538 4539 4540
	if (IS_ERR(trans)) {
		unset_reloc_control(rc);
		err = PTR_ERR(trans);
		goto out_free;
	}
4541 4542 4543

	rc->merge_reloc_tree = 1;

4544 4545 4546 4547 4548 4549 4550 4551 4552 4553 4554
	while (!list_empty(&reloc_roots)) {
		reloc_root = list_entry(reloc_roots.next,
					struct btrfs_root, root_list);
		list_del(&reloc_root->root_list);

		if (btrfs_root_refs(&reloc_root->root_item) == 0) {
			list_add_tail(&reloc_root->root_list,
				      &rc->reloc_roots);
			continue;
		}

4555
		fs_root = read_fs_root(fs_info, reloc_root->root_key.offset);
4556 4557 4558 4559
		if (IS_ERR(fs_root)) {
			err = PTR_ERR(fs_root);
			goto out_free;
		}
4560

4561
		err = __add_reloc_root(reloc_root);
4562
		BUG_ON(err < 0); /* -ENOMEM or logic error */
4563 4564 4565
		fs_root->reloc_root = reloc_root;
	}

4566
	err = btrfs_commit_transaction(trans);
4567 4568
	if (err)
		goto out_free;
4569 4570 4571 4572 4573

	merge_reloc_roots(rc);

	unset_reloc_control(rc);

4574
	trans = btrfs_join_transaction(rc->extent_root);
4575
	if (IS_ERR(trans)) {
4576
		err = PTR_ERR(trans);
4577 4578
		goto out_free;
	}
4579
	err = btrfs_commit_transaction(trans);
4580
out_free:
4581
	kfree(rc);
4582
out:
4583 4584 4585
	if (!list_empty(&reloc_roots))
		free_reloc_roots(&reloc_roots);

4586 4587 4588 4589
	btrfs_free_path(path);

	if (err == 0) {
		/* cleanup orphan inode in data relocation tree */
4590
		fs_root = read_fs_root(fs_info, BTRFS_DATA_RELOC_TREE_OBJECTID);
4591 4592
		if (IS_ERR(fs_root))
			err = PTR_ERR(fs_root);
4593
		else
4594
			err = btrfs_orphan_cleanup(fs_root);
4595 4596 4597 4598 4599 4600 4601 4602 4603 4604 4605 4606
	}
	return err;
}

/*
 * helper to add ordered checksum for data relocation.
 *
 * cloning checksum properly handles the nodatasum extents.
 * it also saves CPU time to re-calculate the checksum.
 */
int btrfs_reloc_clone_csums(struct inode *inode, u64 file_pos, u64 len)
{
4607
	struct btrfs_fs_info *fs_info = btrfs_sb(inode->i_sb);
4608 4609 4610 4611
	struct btrfs_ordered_sum *sums;
	struct btrfs_ordered_extent *ordered;
	int ret;
	u64 disk_bytenr;
4612
	u64 new_bytenr;
4613 4614 4615 4616 4617 4618
	LIST_HEAD(list);

	ordered = btrfs_lookup_ordered_extent(inode, file_pos);
	BUG_ON(ordered->file_offset != file_pos || ordered->len != len);

	disk_bytenr = file_pos + BTRFS_I(inode)->index_cnt;
4619
	ret = btrfs_lookup_csums_range(fs_info->csum_root, disk_bytenr,
A
Arne Jansen 已提交
4620
				       disk_bytenr + len - 1, &list, 0);
4621 4622
	if (ret)
		goto out;
4623 4624 4625 4626 4627

	while (!list_empty(&list)) {
		sums = list_entry(list.next, struct btrfs_ordered_sum, list);
		list_del_init(&sums->list);

4628 4629 4630 4631 4632 4633 4634 4635 4636 4637 4638 4639 4640 4641
		/*
		 * We need to offset the new_bytenr based on where the csum is.
		 * We need to do this because we will read in entire prealloc
		 * extents but we may have written to say the middle of the
		 * prealloc extent, so we need to make sure the csum goes with
		 * the right disk offset.
		 *
		 * We can do this because the data reloc inode refers strictly
		 * to the on disk bytes, so we don't have to worry about
		 * disk_len vs real len like with real inodes since it's all
		 * disk length.
		 */
		new_bytenr = ordered->start + (sums->bytenr - disk_bytenr);
		sums->bytenr = new_bytenr;
4642 4643 4644

		btrfs_add_ordered_sum(inode, ordered, sums);
	}
4645
out:
4646
	btrfs_put_ordered_extent(ordered);
4647
	return ret;
4648
}
4649

4650 4651 4652
int btrfs_reloc_cow_block(struct btrfs_trans_handle *trans,
			  struct btrfs_root *root, struct extent_buffer *buf,
			  struct extent_buffer *cow)
4653
{
4654
	struct btrfs_fs_info *fs_info = root->fs_info;
4655 4656 4657 4658
	struct reloc_control *rc;
	struct backref_node *node;
	int first_cow = 0;
	int level;
4659
	int ret = 0;
4660

4661
	rc = fs_info->reloc_ctl;
4662
	if (!rc)
4663
		return 0;
4664 4665 4666 4667

	BUG_ON(rc->stage == UPDATE_DATA_PTRS &&
	       root->root_key.objectid == BTRFS_DATA_RELOC_TREE_OBJECTID);

4668 4669 4670 4671 4672
	if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
		if (buf == root->node)
			__update_reloc_root(root, cow->start);
	}

4673 4674 4675 4676 4677 4678 4679 4680 4681 4682 4683 4684 4685 4686 4687 4688 4689 4690 4691 4692 4693 4694 4695 4696 4697 4698 4699 4700 4701 4702 4703
	level = btrfs_header_level(buf);
	if (btrfs_header_generation(buf) <=
	    btrfs_root_last_snapshot(&root->root_item))
		first_cow = 1;

	if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID &&
	    rc->create_reloc_tree) {
		WARN_ON(!first_cow && level == 0);

		node = rc->backref_cache.path[level];
		BUG_ON(node->bytenr != buf->start &&
		       node->new_bytenr != buf->start);

		drop_node_buffer(node);
		extent_buffer_get(cow);
		node->eb = cow;
		node->new_bytenr = cow->start;

		if (!node->pending) {
			list_move_tail(&node->list,
				       &rc->backref_cache.pending[level]);
			node->pending = 1;
		}

		if (first_cow)
			__mark_block_processed(rc, node);

		if (first_cow && level > 0)
			rc->nodes_relocated += buf->len;
	}

4704
	if (level == 0 && first_cow && rc->stage == UPDATE_DATA_PTRS)
4705
		ret = replace_file_extents(trans, rc, root, cow);
4706
	return ret;
4707 4708 4709 4710
}

/*
 * called before creating snapshot. it calculates metadata reservation
4711
 * required for relocating tree blocks in the snapshot
4712
 */
4713
void btrfs_reloc_pre_snapshot(struct btrfs_pending_snapshot *pending,
4714 4715 4716 4717 4718 4719 4720 4721 4722 4723 4724 4725 4726 4727 4728 4729 4730 4731 4732 4733 4734 4735 4736 4737 4738 4739 4740 4741 4742 4743 4744 4745
			      u64 *bytes_to_reserve)
{
	struct btrfs_root *root;
	struct reloc_control *rc;

	root = pending->root;
	if (!root->reloc_root)
		return;

	rc = root->fs_info->reloc_ctl;
	if (!rc->merge_reloc_tree)
		return;

	root = root->reloc_root;
	BUG_ON(btrfs_root_refs(&root->root_item) == 0);
	/*
	 * relocation is in the stage of merging trees. the space
	 * used by merging a reloc tree is twice the size of
	 * relocated tree nodes in the worst case. half for cowing
	 * the reloc tree, half for cowing the fs tree. the space
	 * used by cowing the reloc tree will be freed after the
	 * tree is dropped. if we create snapshot, cowing the fs
	 * tree may use more space than it frees. so we need
	 * reserve extra space.
	 */
	*bytes_to_reserve += rc->nodes_relocated;
}

/*
 * called after snapshot is created. migrate block reservation
 * and create reloc root for the newly created snapshot
 */
4746
int btrfs_reloc_post_snapshot(struct btrfs_trans_handle *trans,
4747 4748 4749 4750 4751 4752 4753 4754 4755
			       struct btrfs_pending_snapshot *pending)
{
	struct btrfs_root *root = pending->root;
	struct btrfs_root *reloc_root;
	struct btrfs_root *new_root;
	struct reloc_control *rc;
	int ret;

	if (!root->reloc_root)
4756
		return 0;
4757 4758 4759 4760 4761 4762 4763

	rc = root->fs_info->reloc_ctl;
	rc->merging_rsv_size += rc->nodes_relocated;

	if (rc->merge_reloc_tree) {
		ret = btrfs_block_rsv_migrate(&pending->block_rsv,
					      rc->block_rsv,
4764
					      rc->nodes_relocated, 1);
4765 4766
		if (ret)
			return ret;
4767 4768 4769 4770 4771
	}

	new_root = pending->snap;
	reloc_root = create_reloc_root(trans, root->reloc_root,
				       new_root->root_key.objectid);
4772 4773
	if (IS_ERR(reloc_root))
		return PTR_ERR(reloc_root);
4774

4775 4776
	ret = __add_reloc_root(reloc_root);
	BUG_ON(ret < 0);
4777 4778
	new_root->reloc_root = reloc_root;

4779
	if (rc->create_reloc_tree)
4780
		ret = clone_backref_node(trans, rc, root, reloc_root);
4781
	return ret;
4782
}