1 // SPDX-License-Identifier: GPL-2.0
12 #include <linux/error-injection.h>
14 #include "disk-io.h"
19 #include "async-thread.h"
20 #include "free-space-cache.h"
22 #include "print-tree.h"
23 #include "delalloc-space.h"
24 #include "block-group.h"
29 #include "inode-item.h"
30 #include "space-info.h"
33 #include "extent-tree.h"
34 #include "root-tree.h"
35 #include "file-item.h"
38 #include "tree-checker.h"
39 #include "raid-stripe-tree.h"
52  * ------------------------------------------------------------------
59  * 1.   Mark the target block group read-only
90  * map address of tree root to tree
150 	/* map start of tree root to corresponding reloc tree */
173 				 struct btrfs_backref_node *node)  in mark_block_processed()  argument
177 	if (node->level == 0 ||  in mark_block_processed()
178 	    in_range(node->bytenr, rc->block_group->start,  in mark_block_processed()
179 		     rc->block_group->length)) {  in mark_block_processed()
180 		blocksize = rc->extent_root->fs_info->nodesize;  in mark_block_processed()
181 		set_extent_bit(&rc->processed_blocks, node->bytenr,  in mark_block_processed()
182 			       node->bytenr + blocksize - 1, EXTENT_DIRTY, NULL);  in mark_block_processed()
184 	node->processed = 1;  in mark_block_processed()
188  * walk up backref nodes until reach node presents tree root
191 		struct btrfs_backref_node *node,  in walk_up_backref()  argument
197 	while (!list_empty(&node->upper)) {  in walk_up_backref()
198 		edge = list_entry(node->upper.next,  in walk_up_backref()
201 		node = edge->node[UPPER];  in walk_up_backref()
203 	BUG_ON(node->detached);  in walk_up_backref()
205 	return node;  in walk_up_backref()
219 		edge = edges[idx - 1];  in walk_down_backref()
220 		lower = edge->node[LOWER];  in walk_down_backref()
221 		if (list_is_last(&edge->list[LOWER], &lower->upper)) {  in walk_down_backref()
222 			idx--;  in walk_down_backref()
225 		edge = list_entry(edge->list[LOWER].next,  in walk_down_backref()
227 		edges[idx - 1] = edge;  in walk_down_backref()
229 		return edge->node[UPPER];  in walk_down_backref()
235 static bool reloc_root_is_dead(const struct btrfs_root *root)  in reloc_root_is_dead()  argument
243 	if (test_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state))  in reloc_root_is_dead()
252  * This is enough for most callers, as they don't distinguish dead reloc root
253  * from no reloc root.  But btrfs_should_ignore_reloc_root() below is a
256 static bool have_reloc_root(const struct btrfs_root *root)  in have_reloc_root()  argument
258 	if (reloc_root_is_dead(root))  in have_reloc_root()
260 	if (!root->reloc_root)  in have_reloc_root()
265 bool btrfs_should_ignore_reloc_root(const struct btrfs_root *root)  in btrfs_should_ignore_reloc_root()  argument
269 	if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state))  in btrfs_should_ignore_reloc_root()
272 	/* This root has been merged with its reloc tree, we can ignore it */  in btrfs_should_ignore_reloc_root()
273 	if (reloc_root_is_dead(root))  in btrfs_should_ignore_reloc_root()
276 	reloc_root = root->reloc_root;  in btrfs_should_ignore_reloc_root()
280 	if (btrfs_header_generation(reloc_root->commit_root) ==  in btrfs_should_ignore_reloc_root()
281 	    root->fs_info->running_transaction->transid)  in btrfs_should_ignore_reloc_root()
285 	 * backref lookup can find the reloc tree, so backref node for the fs  in btrfs_should_ignore_reloc_root()
286 	 * tree root is useless for relocation.  in btrfs_should_ignore_reloc_root()
292  * find reloc tree by address of tree root
296 	struct reloc_control *rc = fs_info->reloc_ctl;  in find_reloc_root()
298 	struct mapping_node *node;  in find_reloc_root()  local
299 	struct btrfs_root *root = NULL;  in find_reloc_root()  local
302 	spin_lock(&rc->reloc_root_tree.lock);  in find_reloc_root()
303 	rb_node = rb_simple_search(&rc->reloc_root_tree.rb_root, bytenr);  in find_reloc_root()
305 		node = rb_entry(rb_node, struct mapping_node, rb_node);  in find_reloc_root()
306 		root = node->data;  in find_reloc_root()
308 	spin_unlock(&rc->reloc_root_tree.lock);  in find_reloc_root()
309 	return btrfs_grab_root(root);  in find_reloc_root()
315  * - Cleanup the children edges and nodes
316  *   If child node is also orphan (no parent) during cleanup, then the child
317  *   node will also be cleaned up.
319  * - Freeing up leaves (level 0), keeps nodes detached
320  *   For nodes, the node is still cached as "detached"
322  * Return false if @node is not in the @useless_nodes list.
323  * Return true if @node is in the @useless_nodes list.
326 				 struct btrfs_backref_node *node)  in handle_useless_nodes()  argument
328 	struct btrfs_backref_cache *cache = &rc->backref_cache;  in handle_useless_nodes()
329 	struct list_head *useless_node = &cache->useless_node;  in handle_useless_nodes()
337 		list_del_init(&cur->list);  in handle_useless_nodes()
339 		/* Only tree root nodes can be added to @useless_nodes */  in handle_useless_nodes()
340 		ASSERT(list_empty(&cur->upper));  in handle_useless_nodes()
342 		if (cur == node)  in handle_useless_nodes()
345 		/* The node is the lowest node */  in handle_useless_nodes()
346 		if (cur->lowest) {  in handle_useless_nodes()
347 			list_del_init(&cur->lower);  in handle_useless_nodes()
348 			cur->lowest = 0;  in handle_useless_nodes()
352 		while (!list_empty(&cur->lower)) {  in handle_useless_nodes()
356 			edge = list_entry(cur->lower.next,  in handle_useless_nodes()
358 			list_del(&edge->list[UPPER]);  in handle_useless_nodes()
359 			list_del(&edge->list[LOWER]);  in handle_useless_nodes()
360 			lower = edge->node[LOWER];  in handle_useless_nodes()
363 			/* Child node is also orphan, queue for cleanup */  in handle_useless_nodes()
364 			if (list_empty(&lower->upper))  in handle_useless_nodes()
365 				list_add(&lower->list, useless_node);  in handle_useless_nodes()
375 		if (cur->level > 0) {  in handle_useless_nodes()
376 			list_add(&cur->list, &cache->detached);  in handle_useless_nodes()
377 			cur->detached = 1;  in handle_useless_nodes()
379 			rb_erase(&cur->rb_node, &cache->rb_root);  in handle_useless_nodes()
387  * Build backref tree for a given tree block. Root of the backref tree
389  * b-trees that reference the tree block.
393  * these upper level blocks recursively. The recursion stops when tree root is
406 	struct btrfs_backref_cache *cache = &rc->backref_cache;  in build_backref_tree()
410 	struct btrfs_backref_node *node = NULL;  in build_backref_tree()  local
414 	iter = btrfs_backref_iter_alloc(rc->extent_root->fs_info);  in build_backref_tree()
416 		return ERR_PTR(-ENOMEM);  in build_backref_tree()
419 		ret = -ENOMEM;  in build_backref_tree()
423 	node = btrfs_backref_alloc_node(cache, bytenr, level);  in build_backref_tree()
424 	if (!node) {  in build_backref_tree()
425 		ret = -ENOMEM;  in build_backref_tree()
429 	node->lowest = 1;  in build_backref_tree()
430 	cur = node;  in build_backref_tree()
432 	/* Breadth-first search to build backref cache */  in build_backref_tree()
439 		edge = list_first_entry_or_null(&cache->pending_edge,  in build_backref_tree()
446 			list_del_init(&edge->list[UPPER]);  in build_backref_tree()
447 			cur = edge->node[UPPER];  in build_backref_tree()
452 	ret = btrfs_backref_finish_upper_links(cache, node);  in build_backref_tree()
456 	if (handle_useless_nodes(rc, node))  in build_backref_tree()
457 		node = NULL;  in build_backref_tree()
459 	btrfs_free_path(iter->path);  in build_backref_tree()
463 		btrfs_backref_error_cleanup(cache, node);  in build_backref_tree()
466 	ASSERT(!node || !node->detached);  in build_backref_tree()
467 	ASSERT(list_empty(&cache->useless_node) &&  in build_backref_tree()
468 	       list_empty(&cache->pending_edge));  in build_backref_tree()
469 	return node;  in build_backref_tree()
473  * helper to add backref node for the newly created snapshot.
474  * the backref node is created by cloning backref node that
475  * corresponds to root of source tree
482 	struct btrfs_root *reloc_root = src->reloc_root;  in clone_backref_node()
483 	struct btrfs_backref_cache *cache = &rc->backref_cache;  in clone_backref_node()
484 	struct btrfs_backref_node *node = NULL;  in clone_backref_node()  local
490 	rb_node = rb_simple_search(&cache->rb_root, src->commit_root->start);  in clone_backref_node()
492 		node = rb_entry(rb_node, struct btrfs_backref_node, rb_node);  in clone_backref_node()
493 		if (node->detached)  in clone_backref_node()
494 			node = NULL;  in clone_backref_node()
496 			BUG_ON(node->new_bytenr != reloc_root->node->start);  in clone_backref_node()
499 	if (!node) {  in clone_backref_node()
500 		rb_node = rb_simple_search(&cache->rb_root,  in clone_backref_node()
501 					   reloc_root->commit_root->start);  in clone_backref_node()
503 			node = rb_entry(rb_node, struct btrfs_backref_node,  in clone_backref_node()
505 			BUG_ON(node->detached);  in clone_backref_node()
509 	if (!node)  in clone_backref_node()
512 	new_node = btrfs_backref_alloc_node(cache, dest->node->start,  in clone_backref_node()
513 					    node->level);  in clone_backref_node()
515 		return -ENOMEM;  in clone_backref_node()
517 	new_node->lowest = node->lowest;  in clone_backref_node()
518 	new_node->checked = 1;  in clone_backref_node()
519 	new_node->root = btrfs_grab_root(dest);  in clone_backref_node()
520 	ASSERT(new_node->root);  in clone_backref_node()
522 	if (!node->lowest) {  in clone_backref_node()
523 		list_for_each_entry(edge, &node->lower, list[UPPER]) {  in clone_backref_node()
528 			btrfs_backref_link_edge(new_edge, edge->node[LOWER],  in clone_backref_node()
532 		list_add_tail(&new_node->lower, &cache->leaves);  in clone_backref_node()
535 	rb_node = rb_simple_insert(&cache->rb_root, new_node->bytenr,  in clone_backref_node()
536 				   &new_node->rb_node);  in clone_backref_node()
538 		btrfs_backref_panic(trans->fs_info, new_node->bytenr, -EEXIST);  in clone_backref_node()
540 	if (!new_node->lowest) {  in clone_backref_node()
541 		list_for_each_entry(new_edge, &new_node->lower, list[UPPER]) {  in clone_backref_node()
542 			list_add_tail(&new_edge->list[LOWER],  in clone_backref_node()
543 				      &new_edge->node[LOWER]->upper);  in clone_backref_node()
548 	while (!list_empty(&new_node->lower)) {  in clone_backref_node()
549 		new_edge = list_entry(new_node->lower.next,  in clone_backref_node()
551 		list_del(&new_edge->list[UPPER]);  in clone_backref_node()
555 	return -ENOMEM;  in clone_backref_node()
559  * helper to add 'address of tree root -> reloc tree' mapping
561 static int __add_reloc_root(struct btrfs_root *root)  in __add_reloc_root()  argument
563 	struct btrfs_fs_info *fs_info = root->fs_info;  in __add_reloc_root()
565 	struct mapping_node *node;  in __add_reloc_root()  local
566 	struct reloc_control *rc = fs_info->reloc_ctl;  in __add_reloc_root()
568 	node = kmalloc(sizeof(*node), GFP_NOFS);  in __add_reloc_root()
569 	if (!node)  in __add_reloc_root()
570 		return -ENOMEM;  in __add_reloc_root()
572 	node->bytenr = root->commit_root->start;  in __add_reloc_root()
573 	node->data = root;  in __add_reloc_root()
575 	spin_lock(&rc->reloc_root_tree.lock);  in __add_reloc_root()
576 	rb_node = rb_simple_insert(&rc->reloc_root_tree.rb_root,  in __add_reloc_root()
577 				   node->bytenr, &node->rb_node);  in __add_reloc_root()
578 	spin_unlock(&rc->reloc_root_tree.lock);  in __add_reloc_root()
581 			    "Duplicate root found for start=%llu while inserting into relocation tree",  in __add_reloc_root()
582 			    node->bytenr);  in __add_reloc_root()
583 		return -EEXIST;  in __add_reloc_root()
586 	list_add_tail(&root->root_list, &rc->reloc_roots);  in __add_reloc_root()
591  * helper to delete the 'address of tree root -> reloc tree'
594 static void __del_reloc_root(struct btrfs_root *root)  in __del_reloc_root()  argument
596 	struct btrfs_fs_info *fs_info = root->fs_info;  in __del_reloc_root()
598 	struct mapping_node *node = NULL;  in __del_reloc_root()  local
599 	struct reloc_control *rc = fs_info->reloc_ctl;  in __del_reloc_root()
602 	if (rc && root->node) {  in __del_reloc_root()
603 		spin_lock(&rc->reloc_root_tree.lock);  in __del_reloc_root()
604 		rb_node = rb_simple_search(&rc->reloc_root_tree.rb_root,  in __del_reloc_root()
605 					   root->commit_root->start);  in __del_reloc_root()
607 			node = rb_entry(rb_node, struct mapping_node, rb_node);  in __del_reloc_root()
608 			rb_erase(&node->rb_node, &rc->reloc_root_tree.rb_root);  in __del_reloc_root()
609 			RB_CLEAR_NODE(&node->rb_node);  in __del_reloc_root()
611 		spin_unlock(&rc->reloc_root_tree.lock);  in __del_reloc_root()
612 		ASSERT(!node || (struct btrfs_root *)node->data == root);  in __del_reloc_root()
616 	 * We only put the reloc root here if it's on the list.  There's a lot  in __del_reloc_root()
617 	 * of places where the pattern is to splice the rc->reloc_roots, process  in __del_reloc_root()
618 	 * the reloc roots, and then add the reloc root back onto  in __del_reloc_root()
619 	 * rc->reloc_roots.  If we call __del_reloc_root while it's off of the  in __del_reloc_root()
623 	spin_lock(&fs_info->trans_lock);  in __del_reloc_root()
624 	if (!list_empty(&root->root_list)) {  in __del_reloc_root()
626 		list_del_init(&root->root_list);  in __del_reloc_root()
628 	spin_unlock(&fs_info->trans_lock);  in __del_reloc_root()
630 		btrfs_put_root(root);  in __del_reloc_root()
631 	kfree(node);  in __del_reloc_root()
635  * helper to update the 'address of tree root -> reloc tree'
638 static int __update_reloc_root(struct btrfs_root *root)  in __update_reloc_root()  argument
640 	struct btrfs_fs_info *fs_info = root->fs_info;  in __update_reloc_root()
642 	struct mapping_node *node = NULL;  in __update_reloc_root()  local
643 	struct reloc_control *rc = fs_info->reloc_ctl;  in __update_reloc_root()
645 	spin_lock(&rc->reloc_root_tree.lock);  in __update_reloc_root()
646 	rb_node = rb_simple_search(&rc->reloc_root_tree.rb_root,  in __update_reloc_root()
647 				   root->commit_root->start);  in __update_reloc_root()
649 		node = rb_entry(rb_node, struct mapping_node, rb_node);  in __update_reloc_root()
650 		rb_erase(&node->rb_node, &rc->reloc_root_tree.rb_root);  in __update_reloc_root()
652 	spin_unlock(&rc->reloc_root_tree.lock);  in __update_reloc_root()
654 	if (!node)  in __update_reloc_root()
656 	BUG_ON((struct btrfs_root *)node->data != root);  in __update_reloc_root()
658 	spin_lock(&rc->reloc_root_tree.lock);  in __update_reloc_root()
659 	node->bytenr = root->node->start;  in __update_reloc_root()
660 	rb_node = rb_simple_insert(&rc->reloc_root_tree.rb_root,  in __update_reloc_root()
661 				   node->bytenr, &node->rb_node);  in __update_reloc_root()
662 	spin_unlock(&rc->reloc_root_tree.lock);  in __update_reloc_root()
664 		btrfs_backref_panic(fs_info, node->bytenr, -EEXIST);  in __update_reloc_root()
669 					struct btrfs_root *root, u64 objectid)  in create_reloc_root()  argument
671 	struct btrfs_fs_info *fs_info = root->fs_info;  in create_reloc_root()
681 		return ERR_PTR(-ENOMEM);  in create_reloc_root()
687 	if (btrfs_root_id(root) == objectid) {  in create_reloc_root()
691 		ret = btrfs_copy_root(trans, root, root->commit_root, &eb,  in create_reloc_root()
698 		 * root - like this ctree.c:btrfs_block_can_be_shared() behaves  in create_reloc_root()
699 		 * correctly (returns true) when the relocation root is created  in create_reloc_root()
704 		commit_root_gen = btrfs_header_generation(root->commit_root);  in create_reloc_root()
705 		btrfs_set_root_last_snapshot(&root->root_item, commit_root_gen);  in create_reloc_root()
714 		ret = btrfs_copy_root(trans, root, root->node, &eb,  in create_reloc_root()
726 	memcpy(root_item, &root->root_item, sizeof(*root_item));  in create_reloc_root()
727 	btrfs_set_root_bytenr(root_item, eb->start);  in create_reloc_root()
729 	btrfs_set_root_generation(root_item, trans->transid);  in create_reloc_root()
731 	if (btrfs_root_id(root) == objectid) {  in create_reloc_root()
733 		memset(&root_item->drop_progress, 0,  in create_reloc_root()
741 	ret = btrfs_insert_root(trans, fs_info->tree_root,  in create_reloc_root()
748 	reloc_root = btrfs_read_tree_root(fs_info->tree_root, &root_key);  in create_reloc_root()
753 	set_bit(BTRFS_ROOT_SHAREABLE, &reloc_root->state);  in create_reloc_root()
754 	btrfs_set_root_last_trans(reloc_root, trans->transid);  in create_reloc_root()
766  * snapshot of the fs tree with special root objectid.
769  * root->reloc_root, and another for being on the rc->reloc_roots list.
772 			  struct btrfs_root *root)  in btrfs_init_reloc_root()  argument
774 	struct btrfs_fs_info *fs_info = root->fs_info;  in btrfs_init_reloc_root()
776 	struct reloc_control *rc = fs_info->reloc_ctl;  in btrfs_init_reloc_root()
788 	if (reloc_root_is_dead(root))  in btrfs_init_reloc_root()
794 	 * corresponding fs root, and then here we update the last trans for the  in btrfs_init_reloc_root()
795 	 * reloc root.  This means that we have to do this for the entire life  in btrfs_init_reloc_root()
796 	 * of the reloc root, regardless of which stage of the relocation we are  in btrfs_init_reloc_root()
799 	if (root->reloc_root) {  in btrfs_init_reloc_root()
800 		reloc_root = root->reloc_root;  in btrfs_init_reloc_root()
801 		btrfs_set_root_last_trans(reloc_root, trans->transid);  in btrfs_init_reloc_root()
809 	if (!rc->create_reloc_tree || btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID)  in btrfs_init_reloc_root()
812 	if (!trans->reloc_reserved) {  in btrfs_init_reloc_root()
813 		rsv = trans->block_rsv;  in btrfs_init_reloc_root()
814 		trans->block_rsv = rc->block_rsv;  in btrfs_init_reloc_root()
817 	reloc_root = create_reloc_root(trans, root, btrfs_root_id(root));  in btrfs_init_reloc_root()
819 		trans->block_rsv = rsv;  in btrfs_init_reloc_root()
824 	ASSERT(ret != -EEXIST);  in btrfs_init_reloc_root()
830 	root->reloc_root = btrfs_grab_root(reloc_root);  in btrfs_init_reloc_root()
835  * update root item of reloc tree
838 			    struct btrfs_root *root)  in btrfs_update_reloc_root()  argument
840 	struct btrfs_fs_info *fs_info = root->fs_info;  in btrfs_update_reloc_root()
845 	if (!have_reloc_root(root))  in btrfs_update_reloc_root()
848 	reloc_root = root->reloc_root;  in btrfs_update_reloc_root()
849 	root_item = &reloc_root->root_item;  in btrfs_update_reloc_root()
853 	 * the root.  We have the ref for root->reloc_root, but just in case  in btrfs_update_reloc_root()
854 	 * hold it while we update the reloc root.  in btrfs_update_reloc_root()
858 	/* root->reloc_root will stay until current relocation finished */  in btrfs_update_reloc_root()
859 	if (fs_info->reloc_ctl && fs_info->reloc_ctl->merge_reloc_tree &&  in btrfs_update_reloc_root()
861 		set_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state);  in btrfs_update_reloc_root()
870 	if (reloc_root->commit_root != reloc_root->node) {  in btrfs_update_reloc_root()
872 		btrfs_set_root_node(root_item, reloc_root->node);  in btrfs_update_reloc_root()
873 		free_extent_buffer(reloc_root->commit_root);  in btrfs_update_reloc_root()
874 		reloc_root->commit_root = btrfs_root_node(reloc_root);  in btrfs_update_reloc_root()
877 	ret = btrfs_update_root(trans, fs_info->tree_root,  in btrfs_update_reloc_root()
878 				&reloc_root->root_key, root_item);  in btrfs_update_reloc_root()
889 	struct btrfs_root *root = BTRFS_I(reloc_inode)->root;  in get_new_location()  local
897 		return -ENOMEM;  in get_new_location()
899 	bytenr -= BTRFS_I(reloc_inode)->reloc_block_group_start;  in get_new_location()
900 	ret = btrfs_lookup_file_extent(NULL, root, path,  in get_new_location()
905 		ret = -ENOENT;  in get_new_location()
909 	leaf = path->nodes[0];  in get_new_location()
910 	fi = btrfs_item_ptr(leaf, path->slots[0],  in get_new_location()
919 		ret = -EINVAL;  in get_new_location()
937 			 struct btrfs_root *root,  in replace_file_extents()  argument
940 	struct btrfs_fs_info *fs_info = root->fs_info;  in replace_file_extents()
955 	if (rc->stage != UPDATE_DATA_PTRS)  in replace_file_extents()
959 	if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID)  in replace_file_extents()
960 		parent = leaf->start;  in replace_file_extents()
980 		if (!in_range(bytenr, rc->block_group->start,  in replace_file_extents()
981 			      rc->block_group->length))  in replace_file_extents()
988 		if (btrfs_root_id(root) != BTRFS_TREE_RELOC_OBJECTID) {  in replace_file_extents()
990 				inode = btrfs_find_first_inode(root, key.objectid);  in replace_file_extents()
994 				inode = btrfs_find_first_inode(root, key.objectid);  in replace_file_extents()
1002 						    fs_info->sectorsize));  in replace_file_extents()
1003 				WARN_ON(!IS_ALIGNED(end, fs_info->sectorsize));  in replace_file_extents()
1004 				end--;  in replace_file_extents()
1006 				if (!down_read_trylock(&inode->i_mmap_lock))  in replace_file_extents()
1008 				ret = try_lock_extent(&inode->io_tree, key.offset,  in replace_file_extents()
1011 					up_read(&inode->i_mmap_lock);  in replace_file_extents()
1016 				unlock_extent(&inode->io_tree, key.offset, end,  in replace_file_extents()
1018 				up_read(&inode->i_mmap_lock);  in replace_file_extents()
1022 		ret = get_new_location(rc->data_inode, &new_bytenr,  in replace_file_extents()
1035 		key.offset -= btrfs_file_extent_offset(leaf, fi);  in replace_file_extents()
1040 		ref.owning_root = btrfs_root_id(root);  in replace_file_extents()
1043 				    btrfs_root_id(root), false);  in replace_file_extents()
1054 		ref.owning_root = btrfs_root_id(root);  in replace_file_extents()
1057 				    btrfs_root_id(root), false);  in replace_file_extents()
1078 	btrfs_node_key(path->nodes[level], &key2, path->slots[level]);  in memcmp_node_keys()
1097 	struct btrfs_fs_info *fs_info = dest->fs_info;  in replace_path()
1116 	last_snapshot = btrfs_root_last_snapshot(&src->root_item);  in replace_path()
1118 	slot = path->slots[lowest_level];  in replace_path()
1119 	btrfs_node_key_to_cpu(path->nodes[lowest_level], &key, slot);  in replace_path()
1141 		next_key->objectid = (u64)-1;  in replace_path()
1142 		next_key->type = (u8)-1;  in replace_path()
1143 		next_key->offset = (u64)-1;  in replace_path()
1155 			slot--;  in replace_path()
1161 		blocksize = fs_info->nodesize;  in replace_path()
1165 			eb = path->nodes[level];  in replace_path()
1167 							path->slots[level]);  in replace_path()
1169 							path->slots[level]);  in replace_path()
1218 		btrfs_node_key_to_cpu(path->nodes[level], &key,  in replace_path()
1219 				      path->slots[level]);  in replace_path()
1222 		path->lowest_level = level;  in replace_path()
1223 		set_bit(BTRFS_ROOT_RESET_LOCKDEP_CLASS, &src->state);  in replace_path()
1225 		clear_bit(BTRFS_ROOT_RESET_LOCKDEP_CLASS, &src->state);  in replace_path()
1226 		path->lowest_level = 0;  in replace_path()
1229 				ret = -ENOENT;  in replace_path()
1245 		 * CoW on the subtree root node before transaction commit.  in replace_path()
1248 				rc->block_group, parent, slot,  in replace_path()
1249 				path->nodes[level], path->slots[level],  in replace_path()
1260 		btrfs_set_node_blockptr(path->nodes[level],  in replace_path()
1261 					path->slots[level], old_bytenr);  in replace_path()
1262 		btrfs_set_node_ptr_generation(path->nodes[level],  in replace_path()
1263 					      path->slots[level], old_ptr_gen);  in replace_path()
1264 		btrfs_mark_buffer_dirty(trans, path->nodes[level]);  in replace_path()
1269 		ref.parent = path->nodes[level]->start;  in replace_path()
1272 		btrfs_init_tree_ref(&ref, level - 1, 0, true);  in replace_path()
1285 		btrfs_init_tree_ref(&ref, level - 1, 0, true);  in replace_path()
1296 		ref.parent = path->nodes[level]->start;  in replace_path()
1299 		btrfs_init_tree_ref(&ref, level - 1, 0, true);  in replace_path()
1313 		btrfs_init_tree_ref(&ref, level - 1, 0, true);  in replace_path()
1334 int walk_up_reloc_tree(struct btrfs_root *root, struct btrfs_path *path,  in walk_up_reloc_tree()  argument
1342 	last_snapshot = btrfs_root_last_snapshot(&root->root_item);  in walk_up_reloc_tree()
1345 		free_extent_buffer(path->nodes[i]);  in walk_up_reloc_tree()
1346 		path->nodes[i] = NULL;  in walk_up_reloc_tree()
1349 	for (i = *level; i < BTRFS_MAX_LEVEL && path->nodes[i]; i++) {  in walk_up_reloc_tree()
1350 		eb = path->nodes[i];  in walk_up_reloc_tree()
1352 		while (path->slots[i] + 1 < nritems) {  in walk_up_reloc_tree()
1353 			path->slots[i]++;  in walk_up_reloc_tree()
1354 			if (btrfs_node_ptr_generation(eb, path->slots[i]) <=  in walk_up_reloc_tree()
1361 		free_extent_buffer(path->nodes[i]);  in walk_up_reloc_tree()
1362 		path->nodes[i] = NULL;  in walk_up_reloc_tree()
1371 int walk_down_reloc_tree(struct btrfs_root *root, struct btrfs_path *path,  in walk_down_reloc_tree()  argument
1380 	last_snapshot = btrfs_root_last_snapshot(&root->root_item);  in walk_down_reloc_tree()
1382 	for (i = *level; i > 0; i--) {  in walk_down_reloc_tree()
1383 		eb = path->nodes[i];  in walk_down_reloc_tree()
1385 		while (path->slots[i] < nritems) {  in walk_down_reloc_tree()
1386 			ptr_gen = btrfs_node_ptr_generation(eb, path->slots[i]);  in walk_down_reloc_tree()
1389 			path->slots[i]++;  in walk_down_reloc_tree()
1391 		if (path->slots[i] >= nritems) {  in walk_down_reloc_tree()
1402 		eb = btrfs_read_node_slot(eb, path->slots[i]);  in walk_down_reloc_tree()
1405 		BUG_ON(btrfs_header_level(eb) != i - 1);  in walk_down_reloc_tree()
1406 		path->nodes[i - 1] = eb;  in walk_down_reloc_tree()
1407 		path->slots[i - 1] = 0;  in walk_down_reloc_tree()
1416 static int invalidate_extent_cache(struct btrfs_root *root,  in invalidate_extent_cache()  argument
1420 	struct btrfs_fs_info *fs_info = root->fs_info;  in invalidate_extent_cache()
1426 	objectid = min_key->objectid;  in invalidate_extent_cache()
1432 			iput(&inode->vfs_inode);  in invalidate_extent_cache()
1434 		if (objectid > max_key->objectid)  in invalidate_extent_cache()
1437 		inode = btrfs_find_first_inode(root, objectid);  in invalidate_extent_cache()
1442 		if (ino > max_key->objectid) {  in invalidate_extent_cache()
1443 			iput(&inode->vfs_inode);  in invalidate_extent_cache()
1448 		if (!S_ISREG(inode->vfs_inode.i_mode))  in invalidate_extent_cache()
1451 		if (unlikely(min_key->objectid == ino)) {  in invalidate_extent_cache()
1452 			if (min_key->type > BTRFS_EXTENT_DATA_KEY)  in invalidate_extent_cache()
1454 			if (min_key->type < BTRFS_EXTENT_DATA_KEY)  in invalidate_extent_cache()
1457 				start = min_key->offset;  in invalidate_extent_cache()
1458 				WARN_ON(!IS_ALIGNED(start, fs_info->sectorsize));  in invalidate_extent_cache()
1464 		if (unlikely(max_key->objectid == ino)) {  in invalidate_extent_cache()
1465 			if (max_key->type < BTRFS_EXTENT_DATA_KEY)  in invalidate_extent_cache()
1467 			if (max_key->type > BTRFS_EXTENT_DATA_KEY) {  in invalidate_extent_cache()
1468 				end = (u64)-1;  in invalidate_extent_cache()
1470 				if (max_key->offset == 0)  in invalidate_extent_cache()
1472 				end = max_key->offset;  in invalidate_extent_cache()
1473 				WARN_ON(!IS_ALIGNED(end, fs_info->sectorsize));  in invalidate_extent_cache()
1474 				end--;  in invalidate_extent_cache()
1477 			end = (u64)-1;  in invalidate_extent_cache()
1481 		lock_extent(&inode->io_tree, start, end, &cached_state);  in invalidate_extent_cache()
1483 		unlock_extent(&inode->io_tree, start, end, &cached_state);  in invalidate_extent_cache()
1493 		if (!path->nodes[level])  in find_next_key()
1495 		if (path->slots[level] + 1 <  in find_next_key()
1496 		    btrfs_header_nritems(path->nodes[level])) {  in find_next_key()
1497 			btrfs_node_key_to_cpu(path->nodes[level], key,  in find_next_key()
1498 					      path->slots[level] + 1);  in find_next_key()
1511 			       struct btrfs_root *root)  in insert_dirty_subvol()  argument
1513 	struct btrfs_root *reloc_root = root->reloc_root;  in insert_dirty_subvol()
1517 	/* @root must be a subvolume tree root with a valid reloc tree */  in insert_dirty_subvol()
1518 	ASSERT(btrfs_root_id(root) != BTRFS_TREE_RELOC_OBJECTID);  in insert_dirty_subvol()
1521 	reloc_root_item = &reloc_root->root_item;  in insert_dirty_subvol()
1522 	memset(&reloc_root_item->drop_progress, 0,  in insert_dirty_subvol()
1523 		sizeof(reloc_root_item->drop_progress));  in insert_dirty_subvol()
1526 	ret = btrfs_update_reloc_root(trans, root);  in insert_dirty_subvol()
1530 	if (list_empty(&root->reloc_dirty_list)) {  in insert_dirty_subvol()
1531 		btrfs_grab_root(root);  in insert_dirty_subvol()
1532 		list_add_tail(&root->reloc_dirty_list, &rc->dirty_subvol_roots);  in insert_dirty_subvol()
1540 	struct btrfs_root *root;  in clean_dirty_subvols()  local
1545 	list_for_each_entry_safe(root, next, &rc->dirty_subvol_roots,  in clean_dirty_subvols()
1547 		if (btrfs_root_id(root) != BTRFS_TREE_RELOC_OBJECTID) {  in clean_dirty_subvols()
1548 			/* Merged subvolume, cleanup its reloc root */  in clean_dirty_subvols()
1549 			struct btrfs_root *reloc_root = root->reloc_root;  in clean_dirty_subvols()
1551 			list_del_init(&root->reloc_dirty_list);  in clean_dirty_subvols()
1552 			root->reloc_root = NULL;  in clean_dirty_subvols()
1555 			 * root->reloc_root = NULL. Pairs with have_reloc_root.  in clean_dirty_subvols()
1558 			clear_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state);  in clean_dirty_subvols()
1562 				 * ->reloc_root.  If it fails however we must  in clean_dirty_subvols()
1572 			btrfs_put_root(root);  in clean_dirty_subvols()
1575 			ret2 = btrfs_drop_snapshot(root, 0, 1);  in clean_dirty_subvols()
1577 				btrfs_put_root(root);  in clean_dirty_subvols()
1591 					       struct btrfs_root *root)  in merge_reloc_root()  argument
1593 	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;  in merge_reloc_root()
1610 		return -ENOMEM;  in merge_reloc_root()
1611 	path->reada = READA_FORWARD;  in merge_reloc_root()
1613 	reloc_root = root->reloc_root;  in merge_reloc_root()
1614 	root_item = &reloc_root->root_item;  in merge_reloc_root()
1616 	if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {  in merge_reloc_root()
1618 		atomic_inc(&reloc_root->node->refs);  in merge_reloc_root()
1619 		path->nodes[level] = reloc_root->node;  in merge_reloc_root()
1620 		path->slots[level] = 0;  in merge_reloc_root()
1622 		btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);  in merge_reloc_root()
1626 		path->lowest_level = level;  in merge_reloc_root()
1628 		path->lowest_level = 0;  in merge_reloc_root()
1634 		btrfs_node_key_to_cpu(path->nodes[level], &next_key,  in merge_reloc_root()
1635 				      path->slots[level]);  in merge_reloc_root()
1644 	 * block COW, we COW at most from level 1 to root level for each tree.  in merge_reloc_root()
1650 	min_reserved = fs_info->nodesize * reserve_level * 2;  in merge_reloc_root()
1654 		ret = btrfs_block_rsv_refill(fs_info, rc->block_rsv,  in merge_reloc_root()
1659 		trans = btrfs_start_transaction(root, 0);  in merge_reloc_root()
1673 		 * btrfs_update_reloc_root() and update our root item  in merge_reloc_root()
1676 		btrfs_set_root_last_trans(reloc_root, trans->transid);  in merge_reloc_root()
1677 		trans->block_rsv = rc->block_rsv;  in merge_reloc_root()
1692 			ret = replace_path(trans, rc, root, reloc_root, path,  in merge_reloc_root()
1699 			btrfs_node_key_to_cpu(path->nodes[level], &key,  in merge_reloc_root()
1700 					      path->slots[level]);  in merge_reloc_root()
1711 		 * this is OK since root refs == 1 in this case.  in merge_reloc_root()
1713 		btrfs_node_key(path->nodes[level], &root_item->drop_progress,  in merge_reloc_root()
1714 			       path->slots[level]);  in merge_reloc_root()
1722 		if (replaced && rc->stage == UPDATE_DATA_PTRS)  in merge_reloc_root()
1723 			invalidate_extent_cache(root, &key, &next_key);  in merge_reloc_root()
1728 	 * relocated and the block is tree root.  in merge_reloc_root()
1730 	leaf = btrfs_lock_root_node(root);  in merge_reloc_root()
1731 	ret = btrfs_cow_block(trans, root, leaf, NULL, 0, &leaf,  in merge_reloc_root()
1739 		ret = insert_dirty_subvol(trans, rc, root);  in merge_reloc_root()
1749 	if (replaced && rc->stage == UPDATE_DATA_PTRS)  in merge_reloc_root()
1750 		invalidate_extent_cache(root, &key, &next_key);  in merge_reloc_root()
1758 	struct btrfs_root *root = rc->extent_root;  in prepare_to_merge()  local
1759 	struct btrfs_fs_info *fs_info = root->fs_info;  in prepare_to_merge()
1766 	mutex_lock(&fs_info->reloc_mutex);  in prepare_to_merge()
1767 	rc->merging_rsv_size += fs_info->nodesize * (BTRFS_MAX_LEVEL - 1) * 2;  in prepare_to_merge()
1768 	rc->merging_rsv_size += rc->nodes_relocated * 2;  in prepare_to_merge()
1769 	mutex_unlock(&fs_info->reloc_mutex);  in prepare_to_merge()
1773 		num_bytes = rc->merging_rsv_size;  in prepare_to_merge()
1774 		ret = btrfs_block_rsv_add(fs_info, rc->block_rsv, num_bytes,  in prepare_to_merge()
1780 	trans = btrfs_join_transaction(rc->extent_root);  in prepare_to_merge()
1783 			btrfs_block_rsv_release(fs_info, rc->block_rsv,  in prepare_to_merge()
1789 		if (num_bytes != rc->merging_rsv_size) {  in prepare_to_merge()
1791 			btrfs_block_rsv_release(fs_info, rc->block_rsv,  in prepare_to_merge()
1797 	rc->merge_reloc_tree = true;  in prepare_to_merge()
1799 	while (!list_empty(&rc->reloc_roots)) {  in prepare_to_merge()
1800 		reloc_root = list_entry(rc->reloc_roots.next,  in prepare_to_merge()
1802 		list_del_init(&reloc_root->root_list);  in prepare_to_merge()
1804 		root = btrfs_get_fs_root(fs_info, reloc_root->root_key.offset,  in prepare_to_merge()
1806 		if (IS_ERR(root)) {  in prepare_to_merge()
1808 			 * Even if we have an error we need this reloc root  in prepare_to_merge()
1811 			list_add(&reloc_root->root_list, &reloc_roots);  in prepare_to_merge()
1812 			btrfs_abort_transaction(trans, (int)PTR_ERR(root));  in prepare_to_merge()
1814 				err = PTR_ERR(root);  in prepare_to_merge()
1818 		if (unlikely(root->reloc_root != reloc_root)) {  in prepare_to_merge()
1819 			if (root->reloc_root) {  in prepare_to_merge()
1821 "reloc tree mismatch, root %lld has reloc root key (%lld %u %llu) gen %llu, expect reloc root key (…  in prepare_to_merge()
1822 					  btrfs_root_id(root),  in prepare_to_merge()
1823 					  btrfs_root_id(root->reloc_root),  in prepare_to_merge()
1824 					  root->reloc_root->root_key.type,  in prepare_to_merge()
1825 					  root->reloc_root->root_key.offset,  in prepare_to_merge()
1827 						  &root->reloc_root->root_item),  in prepare_to_merge()
1829 					  reloc_root->root_key.type,  in prepare_to_merge()
1830 					  reloc_root->root_key.offset,  in prepare_to_merge()
1832 						  &reloc_root->root_item));  in prepare_to_merge()
1835 "reloc tree mismatch, root %lld has no reloc root, expect reloc root key (%lld %u %llu) gen %llu",  in prepare_to_merge()
1836 					  btrfs_root_id(root),  in prepare_to_merge()
1838 					  reloc_root->root_key.type,  in prepare_to_merge()
1839 					  reloc_root->root_key.offset,  in prepare_to_merge()
1841 						  &reloc_root->root_item));  in prepare_to_merge()
1843 			list_add(&reloc_root->root_list, &reloc_roots);  in prepare_to_merge()
1844 			btrfs_put_root(root);  in prepare_to_merge()
1845 			btrfs_abort_transaction(trans, -EUCLEAN);  in prepare_to_merge()
1847 				err = -EUCLEAN;  in prepare_to_merge()
1856 			btrfs_set_root_refs(&reloc_root->root_item, 1);  in prepare_to_merge()
1857 		ret = btrfs_update_reloc_root(trans, root);  in prepare_to_merge()
1860 		 * Even if we have an error we need this reloc root back on our  in prepare_to_merge()
1863 		list_add(&reloc_root->root_list, &reloc_roots);  in prepare_to_merge()
1864 		btrfs_put_root(root);  in prepare_to_merge()
1874 	list_splice(&reloc_roots, &rc->reloc_roots);  in prepare_to_merge()
1895 	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;  in merge_reloc_roots()
1896 	struct btrfs_root *root;  in merge_reloc_roots()  local
1902 	root = rc->extent_root;  in merge_reloc_roots()
1910 	mutex_lock(&fs_info->reloc_mutex);  in merge_reloc_roots()
1911 	list_splice_init(&rc->reloc_roots, &reloc_roots);  in merge_reloc_roots()
1912 	mutex_unlock(&fs_info->reloc_mutex);  in merge_reloc_roots()
1919 		root = btrfs_get_fs_root(fs_info, reloc_root->root_key.offset,  in merge_reloc_roots()
1921 		if (btrfs_root_refs(&reloc_root->root_item) > 0) {  in merge_reloc_roots()
1922 			if (WARN_ON(IS_ERR(root))) {  in merge_reloc_roots()
1925 				 * and if we didn't find the root then we marked  in merge_reloc_roots()
1926 				 * the reloc root as a garbage root.  For normal  in merge_reloc_roots()
1927 				 * relocation obviously the root should exist in  in merge_reloc_roots()
1931 				ret = PTR_ERR(root);  in merge_reloc_roots()
1934 			if (WARN_ON(root->reloc_root != reloc_root)) {  in merge_reloc_roots()
1936 				 * This can happen if on-disk metadata has some  in merge_reloc_roots()
1939 				ret = -EINVAL;  in merge_reloc_roots()
1942 			ret = merge_reloc_root(rc, root);  in merge_reloc_roots()
1943 			btrfs_put_root(root);  in merge_reloc_roots()
1945 				if (list_empty(&reloc_root->root_list))  in merge_reloc_roots()
1946 					list_add_tail(&reloc_root->root_list,  in merge_reloc_roots()
1951 			if (!IS_ERR(root)) {  in merge_reloc_roots()
1952 				if (root->reloc_root == reloc_root) {  in merge_reloc_roots()
1953 					root->reloc_root = NULL;  in merge_reloc_roots()
1957 					  &root->state);  in merge_reloc_roots()
1958 				btrfs_put_root(root);  in merge_reloc_roots()
1961 			list_del_init(&reloc_root->root_list);  in merge_reloc_roots()
1962 			/* Don't forget to queue this reloc root for cleanup */  in merge_reloc_roots()
1963 			list_add_tail(&reloc_root->reloc_dirty_list,  in merge_reloc_roots()
1964 				      &rc->dirty_subvol_roots);  in merge_reloc_roots()
1977 		/* new reloc root may be added */  in merge_reloc_roots()
1978 		mutex_lock(&fs_info->reloc_mutex);  in merge_reloc_roots()
1979 		list_splice_init(&rc->reloc_roots, &reloc_roots);  in merge_reloc_roots()
1980 		mutex_unlock(&fs_info->reloc_mutex);  in merge_reloc_roots()
1987 	 * BUG_ON(!RB_EMPTY_ROOT(&rc->reloc_root_tree.rb_root));  in merge_reloc_roots()
1992 	 * fine because we're bailing here, and we hold a reference on the root  in merge_reloc_roots()
1994 	 * do the reloc_dirty_list afterwards.  Meanwhile the root->reloc_root  in merge_reloc_roots()
2015 	struct btrfs_fs_info *fs_info = reloc_root->fs_info;  in record_reloc_root_in_trans()
2016 	struct btrfs_root *root;  in record_reloc_root_in_trans()  local
2019 	if (btrfs_get_root_last_trans(reloc_root) == trans->transid)  in record_reloc_root_in_trans()
2022 	root = btrfs_get_fs_root(fs_info, reloc_root->root_key.offset, false);  in record_reloc_root_in_trans()
2025 	 * This should succeed, since we can't have a reloc root without having  in record_reloc_root_in_trans()
2026 	 * already looked up the actual root and created the reloc root for this  in record_reloc_root_in_trans()
2027 	 * root.  in record_reloc_root_in_trans()
2030 	 * reloc root without a corresponding root this could return ENOENT.  in record_reloc_root_in_trans()
2032 	if (IS_ERR(root)) {  in record_reloc_root_in_trans()
2034 		return PTR_ERR(root);  in record_reloc_root_in_trans()
2036 	if (root->reloc_root != reloc_root) {  in record_reloc_root_in_trans()
2039 			  "root %llu has two reloc roots associated with it",  in record_reloc_root_in_trans()
2040 			  reloc_root->root_key.offset);  in record_reloc_root_in_trans()
2041 		btrfs_put_root(root);  in record_reloc_root_in_trans()
2042 		return -EUCLEAN;  in record_reloc_root_in_trans()
2044 	ret = btrfs_record_root_in_trans(trans, root);  in record_reloc_root_in_trans()
2045 	btrfs_put_root(root);  in record_reloc_root_in_trans()
2053 				     struct btrfs_backref_node *node,  in select_reloc_root()  argument
2057 	struct btrfs_root *root;  in select_reloc_root()  local
2061 	next = node;  in select_reloc_root()
2065 		root = next->root;  in select_reloc_root()
2068 		 * If there is no root, then our references for this block are  in select_reloc_root()
2070 		 * block that is owned by a root.  in select_reloc_root()
2073 		 * non-SHAREABLE root then we have backrefs that resolve  in select_reloc_root()
2079 		if (!root) {  in select_reloc_root()
2081 			btrfs_err(trans->fs_info,  in select_reloc_root()
2082 		"bytenr %llu doesn't have a backref path ending in a root",  in select_reloc_root()
2083 				  node->bytenr);  in select_reloc_root()
2084 			return ERR_PTR(-EUCLEAN);  in select_reloc_root()
2086 		if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) {  in select_reloc_root()
2088 			btrfs_err(trans->fs_info,  in select_reloc_root()
2089 	"bytenr %llu has multiple refs with one ending in a non-shareable root",  in select_reloc_root()
2090 				  node->bytenr);  in select_reloc_root()
2091 			return ERR_PTR(-EUCLEAN);  in select_reloc_root()
2094 		if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID) {  in select_reloc_root()
2095 			ret = record_reloc_root_in_trans(trans, root);  in select_reloc_root()
2101 		ret = btrfs_record_root_in_trans(trans, root);  in select_reloc_root()
2104 		root = root->reloc_root;  in select_reloc_root()
2108 		 * root->reloc_root may not be set, return ENOENT in this case.  in select_reloc_root()
2110 		if (!root)  in select_reloc_root()
2111 			return ERR_PTR(-ENOENT);  in select_reloc_root()
2113 		if (next->new_bytenr != root->node->start) {  in select_reloc_root()
2115 			 * We just created the reloc root, so we shouldn't have  in select_reloc_root()
2116 			 * ->new_bytenr set and this shouldn't be in the changed  in select_reloc_root()
2121 			ASSERT(next->new_bytenr == 0);  in select_reloc_root()
2122 			ASSERT(list_empty(&next->list));  in select_reloc_root()
2123 			if (next->new_bytenr || !list_empty(&next->list)) {  in select_reloc_root()
2124 				btrfs_err(trans->fs_info,  in select_reloc_root()
2126 					  node->bytenr, next->bytenr);  in select_reloc_root()
2127 				return ERR_PTR(-EUCLEAN);  in select_reloc_root()
2130 			next->new_bytenr = root->node->start;  in select_reloc_root()
2131 			btrfs_put_root(next->root);  in select_reloc_root()
2132 			next->root = btrfs_grab_root(root);  in select_reloc_root()
2133 			ASSERT(next->root);  in select_reloc_root()
2134 			list_add_tail(&next->list,  in select_reloc_root()
2135 				      &rc->backref_cache.changed);  in select_reloc_root()
2141 		root = NULL;  in select_reloc_root()
2143 		if (!next || next->level <= node->level)  in select_reloc_root()
2146 	if (!root) {  in select_reloc_root()
2152 		return ERR_PTR(-ENOENT);  in select_reloc_root()
2155 	next = node;  in select_reloc_root()
2156 	/* setup backref node path for btrfs_reloc_cow_block */  in select_reloc_root()
2158 		rc->backref_cache.path[next->level] = next;  in select_reloc_root()
2159 		if (--index < 0)  in select_reloc_root()
2161 		next = edges[index]->node[UPPER];  in select_reloc_root()
2163 	return root;  in select_reloc_root()
2167  * Select a tree root for relocation.
2172  * Return a tree root pointer if the block is shareable.
2173  * Return -ENOENT if the block is root of reloc tree.
2176 struct btrfs_root *select_one_root(struct btrfs_backref_node *node)  in select_one_root()  argument
2179 	struct btrfs_root *root;  in select_one_root()  local
2181 	struct btrfs_backref_edge *edges[BTRFS_MAX_LEVEL - 1];  in select_one_root()
2184 	next = node;  in select_one_root()
2188 		root = next->root;  in select_one_root()
2192 		 * the way up a particular path, in this case return -EUCLEAN.  in select_one_root()
2194 		if (!root)  in select_one_root()
2195 			return ERR_PTR(-EUCLEAN);  in select_one_root()
2197 		/* No other choice for non-shareable tree */  in select_one_root()
2198 		if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state))  in select_one_root()
2199 			return root;  in select_one_root()
2201 		if (btrfs_root_id(root) != BTRFS_TREE_RELOC_OBJECTID)  in select_one_root()
2202 			fs_root = root;  in select_one_root()
2204 		if (next != node)  in select_one_root()
2208 		if (!next || next->level <= node->level)  in select_one_root()
2213 		return ERR_PTR(-ENOENT);  in select_one_root()
2218 						  struct btrfs_backref_node *node)  in calcu_metadata_size()  argument
2220 	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;  in calcu_metadata_size()
2221 	struct btrfs_backref_node *next = node;  in calcu_metadata_size()
2223 	struct btrfs_backref_edge *edges[BTRFS_MAX_LEVEL - 1];  in calcu_metadata_size()
2227 	BUG_ON(node->processed);  in calcu_metadata_size()
2232 			if (next->processed)  in calcu_metadata_size()
2235 			num_bytes += fs_info->nodesize;  in calcu_metadata_size()
2237 			if (list_empty(&next->upper))  in calcu_metadata_size()
2240 			edge = list_entry(next->upper.next,  in calcu_metadata_size()
2243 			next = edge->node[UPPER];  in calcu_metadata_size()
2252 				  struct btrfs_backref_node *node)  in reserve_metadata_space()  argument
2254 	struct btrfs_root *root = rc->extent_root;  in reserve_metadata_space()  local
2255 	struct btrfs_fs_info *fs_info = root->fs_info;  in reserve_metadata_space()
2260 	num_bytes = calcu_metadata_size(rc, node) * 2;  in reserve_metadata_space()
2262 	trans->block_rsv = rc->block_rsv;  in reserve_metadata_space()
2263 	rc->reserved_bytes += num_bytes;  in reserve_metadata_space()
2267 	 * If we get an enospc just kick back -EAGAIN so we know to drop the  in reserve_metadata_space()
2270 	ret = btrfs_block_rsv_refill(fs_info, rc->block_rsv, num_bytes,  in reserve_metadata_space()
2273 		tmp = fs_info->nodesize * RELOCATION_RESERVED_NODES;  in reserve_metadata_space()
2274 		while (tmp <= rc->reserved_bytes)  in reserve_metadata_space()
2283 		rc->block_rsv->size = tmp + fs_info->nodesize *  in reserve_metadata_space()
2285 		return -EAGAIN;  in reserve_metadata_space()
2300 			 struct btrfs_backref_node *node,  in do_relocation()  argument
2306 	struct btrfs_backref_edge *edges[BTRFS_MAX_LEVEL - 1];  in do_relocation()
2307 	struct btrfs_root *root;  in do_relocation()  local
2318 	ASSERT(!lowest || !node->eb);  in do_relocation()
2320 	path->lowest_level = node->level + 1;  in do_relocation()
2321 	rc->backref_cache.path[node->level] = node;  in do_relocation()
2322 	list_for_each_entry(edge, &node->upper, list[LOWER]) {  in do_relocation()
2325 		upper = edge->node[UPPER];  in do_relocation()
2326 		root = select_reloc_root(trans, rc, upper, edges);  in do_relocation()
2327 		if (IS_ERR(root)) {  in do_relocation()
2328 			ret = PTR_ERR(root);  in do_relocation()
2332 		if (upper->eb && !upper->locked) {  in do_relocation()
2334 				ret = btrfs_bin_search(upper->eb, 0, key, &slot);  in do_relocation()
2338 				bytenr = btrfs_node_blockptr(upper->eb, slot);  in do_relocation()
2339 				if (node->eb->start == bytenr)  in do_relocation()
2345 		if (!upper->eb) {  in do_relocation()
2346 			ret = btrfs_search_slot(trans, root, key, path, 0, 1);  in do_relocation()
2349 					ret = -ENOENT;  in do_relocation()
2355 			if (!upper->eb) {  in do_relocation()
2356 				upper->eb = path->nodes[upper->level];  in do_relocation()
2357 				path->nodes[upper->level] = NULL;  in do_relocation()
2359 				BUG_ON(upper->eb != path->nodes[upper->level]);  in do_relocation()
2362 			upper->locked = 1;  in do_relocation()
2363 			path->locks[upper->level] = 0;  in do_relocation()
2365 			slot = path->slots[upper->level];  in do_relocation()
2368 			ret = btrfs_bin_search(upper->eb, 0, key, &slot);  in do_relocation()
2374 		bytenr = btrfs_node_blockptr(upper->eb, slot);  in do_relocation()
2376 			if (bytenr != node->bytenr) {  in do_relocation()
2377 				btrfs_err(root->fs_info,  in do_relocation()
2378 		"lowest leaf/node mismatch: bytenr %llu node->bytenr %llu slot %d upper %llu",  in do_relocation()
2379 					  bytenr, node->bytenr, slot,  in do_relocation()
2380 					  upper->eb->start);  in do_relocation()
2381 				ret = -EIO;  in do_relocation()
2385 			if (node->eb->start == bytenr)  in do_relocation()
2389 		blocksize = root->fs_info->nodesize;  in do_relocation()
2390 		eb = btrfs_read_node_slot(upper->eb, slot);  in do_relocation()
2397 		if (!node->eb) {  in do_relocation()
2398 			ret = btrfs_cow_block(trans, root, eb, upper->eb,  in do_relocation()
2406 			 * the correct backref node entry.  in do_relocation()
2408 			ASSERT(node->eb == eb);  in do_relocation()
2412 				.bytenr = node->eb->start,  in do_relocation()
2414 				.parent = upper->eb->start,  in do_relocation()
2415 				.owning_root = btrfs_header_owner(upper->eb),  in do_relocation()
2416 				.ref_root = btrfs_header_owner(upper->eb),  in do_relocation()
2419 			btrfs_set_node_blockptr(upper->eb, slot,  in do_relocation()
2420 						node->eb->start);  in do_relocation()
2421 			btrfs_set_node_ptr_generation(upper->eb, slot,  in do_relocation()
2422 						      trans->transid);  in do_relocation()
2423 			btrfs_mark_buffer_dirty(trans, upper->eb);  in do_relocation()
2425 			btrfs_init_tree_ref(&ref, node->level,  in do_relocation()
2426 					    btrfs_root_id(root), false);  in do_relocation()
2429 				ret = btrfs_drop_subtree(trans, root, eb,  in do_relocation()
2430 							 upper->eb);  in do_relocation()
2435 		if (!upper->pending)  in do_relocation()
2443 	if (!ret && node->pending) {  in do_relocation()
2444 		btrfs_backref_drop_node_buffer(node);  in do_relocation()
2445 		list_move_tail(&node->list, &rc->backref_cache.changed);  in do_relocation()
2446 		node->pending = 0;  in do_relocation()
2449 	path->lowest_level = 0;  in do_relocation()
2455 	ASSERT(ret != -ENOSPC);  in do_relocation()
2461 			 struct btrfs_backref_node *node,  in link_to_upper()  argument
2466 	btrfs_node_key_to_cpu(node->eb, &key, 0);  in link_to_upper()
2467 	return do_relocation(trans, rc, node, &key, path, 0);  in link_to_upper()
2475 	struct btrfs_backref_cache *cache = &rc->backref_cache;  in finish_pending_nodes()
2476 	struct btrfs_backref_node *node;  in finish_pending_nodes()  local
2481 		while (!list_empty(&cache->pending[level])) {  in finish_pending_nodes()
2482 			node = list_entry(cache->pending[level].next,  in finish_pending_nodes()
2484 			list_move_tail(&node->list, &list);  in finish_pending_nodes()
2485 			BUG_ON(!node->pending);  in finish_pending_nodes()
2488 				ret = link_to_upper(trans, rc, node, path);  in finish_pending_nodes()
2493 		list_splice_init(&list, &cache->pending[level]);  in finish_pending_nodes()
2503 				    struct btrfs_backref_node *node)  in update_processed_blocks()  argument
2505 	struct btrfs_backref_node *next = node;  in update_processed_blocks()
2507 	struct btrfs_backref_edge *edges[BTRFS_MAX_LEVEL - 1];  in update_processed_blocks()
2513 			if (next->processed)  in update_processed_blocks()
2518 			if (list_empty(&next->upper))  in update_processed_blocks()
2521 			edge = list_entry(next->upper.next,  in update_processed_blocks()
2524 			next = edge->node[UPPER];  in update_processed_blocks()
2532 	u32 blocksize = rc->extent_root->fs_info->nodesize;  in tree_block_processed()
2534 	if (test_range_bit(&rc->processed_blocks, bytenr,  in tree_block_processed()
2535 			   bytenr + blocksize - 1, EXTENT_DIRTY, NULL))  in tree_block_processed()
2544 		.level = block->level,  in get_tree_block_key()
2545 		.owner_root = block->owner,  in get_tree_block_key()
2546 		.transid = block->key.offset  in get_tree_block_key()
2550 	eb = read_tree_block(fs_info, block->bytenr, &check);  in get_tree_block_key()
2555 		return -EIO;  in get_tree_block_key()
2557 	if (block->level == 0)  in get_tree_block_key()
2558 		btrfs_item_key_to_cpu(eb, &block->key, 0);  in get_tree_block_key()
2560 		btrfs_node_key_to_cpu(eb, &block->key, 0);  in get_tree_block_key()
2562 	block->key_ready = true;  in get_tree_block_key()
2571 				struct btrfs_backref_node *node,  in relocate_tree_block()  argument
2575 	struct btrfs_root *root;  in relocate_tree_block()  local
2578 	if (!node)  in relocate_tree_block()
2585 	ret = reserve_metadata_space(trans, rc, node);  in relocate_tree_block()
2589 	BUG_ON(node->processed);  in relocate_tree_block()
2590 	root = select_one_root(node);  in relocate_tree_block()
2591 	if (IS_ERR(root)) {  in relocate_tree_block()
2592 		ret = PTR_ERR(root);  in relocate_tree_block()
2594 		/* See explanation in select_one_root for the -EUCLEAN case. */  in relocate_tree_block()
2595 		ASSERT(ret == -ENOENT);  in relocate_tree_block()
2596 		if (ret == -ENOENT) {  in relocate_tree_block()
2598 			update_processed_blocks(rc, node);  in relocate_tree_block()
2603 	if (root) {  in relocate_tree_block()
2604 		if (test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) {  in relocate_tree_block()
2606 			 * This block was the root block of a root, and this is  in relocate_tree_block()
2608 			 * should not have had the ->new_bytenr modified and  in relocate_tree_block()
2618 			ASSERT(node->new_bytenr == 0);  in relocate_tree_block()
2619 			ASSERT(list_empty(&node->list));  in relocate_tree_block()
2620 			if (node->new_bytenr || !list_empty(&node->list)) {  in relocate_tree_block()
2621 				btrfs_err(root->fs_info,  in relocate_tree_block()
2623 					  node->bytenr);  in relocate_tree_block()
2624 				ret = -EUCLEAN;  in relocate_tree_block()
2627 			ret = btrfs_record_root_in_trans(trans, root);  in relocate_tree_block()
2634 			if (!root->reloc_root) {  in relocate_tree_block()
2635 				ret = -ENOENT;  in relocate_tree_block()
2638 			root = root->reloc_root;  in relocate_tree_block()
2639 			node->new_bytenr = root->node->start;  in relocate_tree_block()
2640 			btrfs_put_root(node->root);  in relocate_tree_block()
2641 			node->root = btrfs_grab_root(root);  in relocate_tree_block()
2642 			ASSERT(node->root);  in relocate_tree_block()
2643 			list_add_tail(&node->list, &rc->backref_cache.changed);  in relocate_tree_block()
2645 			path->lowest_level = node->level;  in relocate_tree_block()
2646 			if (root == root->fs_info->chunk_root)  in relocate_tree_block()
2648 			ret = btrfs_search_slot(trans, root, key, path, 0, 1);  in relocate_tree_block()
2650 			if (root == root->fs_info->chunk_root)  in relocate_tree_block()
2656 			update_processed_blocks(rc, node);  in relocate_tree_block()
2658 		ret = do_relocation(trans, rc, node, key, path, 1);  in relocate_tree_block()
2661 	if (ret || node->level == 0 || node->cowonly)  in relocate_tree_block()
2662 		btrfs_backref_cleanup_node(&rc->backref_cache, node);  in relocate_tree_block()
2673 	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;  in relocate_tree_blocks()
2674 	struct btrfs_backref_node *node;  in relocate_tree_blocks()  local
2682 		ret = -ENOMEM;  in relocate_tree_blocks()
2688 		if (!block->key_ready)  in relocate_tree_blocks()
2689 			btrfs_readahead_tree_block(fs_info, block->bytenr,  in relocate_tree_blocks()
2690 						   block->owner, 0,  in relocate_tree_blocks()
2691 						   block->level);  in relocate_tree_blocks()
2696 		if (!block->key_ready) {  in relocate_tree_blocks()
2705 		node = build_backref_tree(trans, rc, &block->key,  in relocate_tree_blocks()
2706 					  block->level, block->bytenr);  in relocate_tree_blocks()
2707 		if (IS_ERR(node)) {  in relocate_tree_blocks()
2708 			ret = PTR_ERR(node);  in relocate_tree_blocks()
2712 		ret = relocate_tree_block(trans, rc, node, &block->key,  in relocate_tree_blocks()
2729 	const struct file_extent_cluster *cluster = &rc->cluster;  in prealloc_file_extent_cluster()
2730 	struct btrfs_inode *inode = BTRFS_I(rc->data_inode);  in prealloc_file_extent_cluster()
2734 	u64 offset = inode->reloc_block_group_start;  in prealloc_file_extent_cluster()
2738 	u64 i_size = i_size_read(&inode->vfs_inode);  in prealloc_file_extent_cluster()
2739 	u64 prealloc_start = cluster->start - offset;  in prealloc_file_extent_cluster()
2740 	u64 prealloc_end = cluster->end - offset;  in prealloc_file_extent_cluster()
2755 		struct address_space *mapping = inode->vfs_inode.i_mapping;  in prealloc_file_extent_cluster()
2756 		struct btrfs_fs_info *fs_info = inode->root->fs_info;  in prealloc_file_extent_cluster()
2757 		const u32 sectorsize = fs_info->sectorsize;  in prealloc_file_extent_cluster()
2769 		 * |- btrfs_lock_and_flush_ordered_range()  in prealloc_file_extent_cluster()
2770 		 *    |- btrfs_start_ordered_extent()  in prealloc_file_extent_cluster()
2771 		 *       |- extent_write_cache_pages()  in prealloc_file_extent_cluster()
2772 		 *          |- lock_page()  in prealloc_file_extent_cluster()
2786 		clear_extent_bits(&inode->io_tree, i_size,  in prealloc_file_extent_cluster()
2787 				  round_up(i_size, PAGE_SIZE) - 1,  in prealloc_file_extent_cluster()
2792 		 * will re-read the whole page anyway.  in prealloc_file_extent_cluster()
2796 					round_up(i_size, PAGE_SIZE) - i_size);  in prealloc_file_extent_cluster()
2802 	BUG_ON(cluster->start != cluster->boundary[0]);  in prealloc_file_extent_cluster()
2804 					      prealloc_end + 1 - prealloc_start);  in prealloc_file_extent_cluster()
2809 	for (nr = 0; nr < cluster->nr; nr++) {  in prealloc_file_extent_cluster()
2812 		start = cluster->boundary[nr] - offset;  in prealloc_file_extent_cluster()
2813 		if (nr + 1 < cluster->nr)  in prealloc_file_extent_cluster()
2814 			end = cluster->boundary[nr + 1] - 1 - offset;  in prealloc_file_extent_cluster()
2816 			end = cluster->end - offset;  in prealloc_file_extent_cluster()
2818 		lock_extent(&inode->io_tree, start, end, &cached_state);  in prealloc_file_extent_cluster()
2819 		num_bytes = end + 1 - start;  in prealloc_file_extent_cluster()
2820 		ret = btrfs_prealloc_file_range(&inode->vfs_inode, 0, start,  in prealloc_file_extent_cluster()
2824 		unlock_extent(&inode->io_tree, start, end, &cached_state);  in prealloc_file_extent_cluster()
2831 		btrfs_free_reserved_data_space_noquota(inode->root->fs_info,  in prealloc_file_extent_cluster()
2832 					       prealloc_end + 1 - cur_offset);  in prealloc_file_extent_cluster()
2838 	struct btrfs_inode *inode = BTRFS_I(rc->data_inode);  in setup_relocation_extent_mapping()
2841 	u64 offset = inode->reloc_block_group_start;  in setup_relocation_extent_mapping()
2842 	u64 start = rc->cluster.start - offset;  in setup_relocation_extent_mapping()
2843 	u64 end = rc->cluster.end - offset;  in setup_relocation_extent_mapping()
2848 		return -ENOMEM;  in setup_relocation_extent_mapping()
2850 	em->start = start;  in setup_relocation_extent_mapping()
2851 	em->len = end + 1 - start;  in setup_relocation_extent_mapping()
2852 	em->disk_bytenr = rc->cluster.start;  in setup_relocation_extent_mapping()
2853 	em->disk_num_bytes = em->len;  in setup_relocation_extent_mapping()
2854 	em->ram_bytes = em->len;  in setup_relocation_extent_mapping()
2855 	em->flags |= EXTENT_FLAG_PINNED;  in setup_relocation_extent_mapping()
2857 	lock_extent(&inode->io_tree, start, end, &cached_state);  in setup_relocation_extent_mapping()
2859 	unlock_extent(&inode->io_tree, start, end, &cached_state);  in setup_relocation_extent_mapping()
2870 	return atomic_read(&fs_info->balance_cancel_req) ||  in btrfs_should_cancel_balance()
2871 		atomic_read(&fs_info->reloc_cancel_req) ||  in btrfs_should_cancel_balance()
2880 	if (cluster_nr >= cluster->nr - 1)  in get_cluster_boundary_end()
2881 		return cluster->end;  in get_cluster_boundary_end()
2884 	return cluster->boundary[cluster_nr + 1] - 1;  in get_cluster_boundary_end()
2891 	const struct file_extent_cluster *cluster = &rc->cluster;  in relocate_one_folio()
2892 	struct inode *inode = rc->data_inode;  in relocate_one_folio()
2894 	u64 offset = BTRFS_I(inode)->reloc_block_group_start;  in relocate_one_folio()
2895 	const unsigned long last_index = (cluster->end - offset) >> PAGE_SHIFT;  in relocate_one_folio()
2896 	gfp_t mask = btrfs_alloc_write_mask(inode->i_mapping);  in relocate_one_folio()
2902 	const bool use_rst = btrfs_need_stripe_tree_update(fs_info, rc->block_group->flags);  in relocate_one_folio()
2905 	folio = filemap_lock_folio(inode->i_mapping, index);  in relocate_one_folio()
2918 			page_cache_sync_readahead(inode->i_mapping, ra, NULL,  in relocate_one_folio()
2919 						  index, last_index + 1 - index);  in relocate_one_folio()
2920 		folio = __filemap_get_folio(inode->i_mapping, index,  in relocate_one_folio()
2930 		page_cache_async_readahead(inode->i_mapping, ra, NULL,  in relocate_one_folio()
2931 					   folio, last_index + 1 - index);  in relocate_one_folio()
2937 			ret = -EIO;  in relocate_one_folio()
2952 	folio_end = folio_start + PAGE_SIZE - 1;  in relocate_one_folio()
2958 	cur = max(folio_start, cluster->boundary[*cluster_nr] - offset);  in relocate_one_folio()
2961 		u64 extent_start = cluster->boundary[*cluster_nr] - offset;  in relocate_one_folio()
2963 						*cluster_nr) - offset;  in relocate_one_folio()
2966 		u32 clamped_len = clamped_end + 1 - clamped_start;  in relocate_one_folio()
2976 		lock_extent(&BTRFS_I(inode)->io_tree, clamped_start, clamped_end,  in relocate_one_folio()
2981 			clear_extent_bit(&BTRFS_I(inode)->io_tree,  in relocate_one_folio()
3000 		if (in_range(cluster->boundary[*cluster_nr] - offset, folio_start, PAGE_SIZE)) {  in relocate_one_folio()
3001 			u64 boundary_start = cluster->boundary[*cluster_nr] -  in relocate_one_folio()
3004 					   fs_info->sectorsize - 1;  in relocate_one_folio()
3006 			set_extent_bit(&BTRFS_I(inode)->io_tree,  in relocate_one_folio()
3010 		unlock_extent(&BTRFS_I(inode)->io_tree, clamped_start, clamped_end,  in relocate_one_folio()
3019 			if (*cluster_nr >= cluster->nr)  in relocate_one_folio()
3026 	balance_dirty_pages_ratelimited(inode->i_mapping);  in relocate_one_folio()
3029 		ret = -ECANCELED;  in relocate_one_folio()
3040 	struct inode *inode = rc->data_inode;  in relocate_file_extent_cluster()
3041 	const struct file_extent_cluster *cluster = &rc->cluster;  in relocate_file_extent_cluster()
3042 	u64 offset = BTRFS_I(inode)->reloc_block_group_start;  in relocate_file_extent_cluster()
3049 	if (!cluster->nr)  in relocate_file_extent_cluster()
3054 		return -ENOMEM;  in relocate_file_extent_cluster()
3060 	file_ra_state_init(ra, inode->i_mapping);  in relocate_file_extent_cluster()
3066 	last_index = (cluster->end - offset) >> PAGE_SHIFT;  in relocate_file_extent_cluster()
3067 	for (index = (cluster->start - offset) >> PAGE_SHIFT;  in relocate_file_extent_cluster()
3071 		WARN_ON(cluster_nr != cluster->nr);  in relocate_file_extent_cluster()
3080 	struct inode *inode = rc->data_inode;  in relocate_data_extent()
3081 	struct file_extent_cluster *cluster = &rc->cluster;  in relocate_data_extent()
3083 	struct btrfs_root *root = BTRFS_I(inode)->root;  in relocate_data_extent()  local
3085 	if (cluster->nr > 0 && extent_key->objectid != cluster->end + 1) {  in relocate_data_extent()
3089 		cluster->nr = 0;  in relocate_data_extent()
3093 	 * Under simple quotas, we set root->relocation_src_root when we find  in relocate_data_extent()
3095 	 * them while relocating. Handle this by storing the owning root that  in relocate_data_extent()
3096 	 * started a cluster and if we see an extent from a different root break  in relocate_data_extent()
3097 	 * cluster formation (just like the above case of non-adjacent extents).  in relocate_data_extent()
3103 	if (cluster->nr > 0 && cluster->owning_root != root->relocation_src_root) {  in relocate_data_extent()
3104 		u64 tmp = root->relocation_src_root;  in relocate_data_extent()
3107 		 * root->relocation_src_root is the state that actually affects  in relocate_data_extent()
3108 		 * the preallocation we do here, so set it to the root owning  in relocate_data_extent()
3111 		root->relocation_src_root = cluster->owning_root;  in relocate_data_extent()
3115 		cluster->nr = 0;  in relocate_data_extent()
3116 		/* And reset it back for the current extent's owning root. */  in relocate_data_extent()
3117 		root->relocation_src_root = tmp;  in relocate_data_extent()
3120 	if (!cluster->nr) {  in relocate_data_extent()
3121 		cluster->start = extent_key->objectid;  in relocate_data_extent()
3122 		cluster->owning_root = root->relocation_src_root;  in relocate_data_extent()
3125 		BUG_ON(cluster->nr >= MAX_EXTENTS);  in relocate_data_extent()
3126 	cluster->end = extent_key->objectid + extent_key->offset - 1;  in relocate_data_extent()
3127 	cluster->boundary[cluster->nr] = extent_key->objectid;  in relocate_data_extent()
3128 	cluster->nr++;  in relocate_data_extent()
3130 	if (cluster->nr >= MAX_EXTENTS) {  in relocate_data_extent()
3134 		cluster->nr = 0;  in relocate_data_extent()
3154 	int level = -1;  in add_tree_block()
3158 	eb =  path->nodes[0];  in add_tree_block()
3159 	item_size = btrfs_item_size(eb, path->slots[0]);  in add_tree_block()
3161 	if (extent_key->type == BTRFS_METADATA_ITEM_KEY ||  in add_tree_block()
3165 		ei = btrfs_item_ptr(eb, path->slots[0],  in add_tree_block()
3168 		if (extent_key->type == BTRFS_EXTENT_ITEM_KEY) {  in add_tree_block()
3173 			level = (int)extent_key->offset;  in add_tree_block()
3183 		 * inline ref offset.  We know it's an fs root if  in add_tree_block()
3204 				return -EINVAL;  in add_tree_block()
3210 		btrfs_err(rc->block_group->fs_info,  in add_tree_block()
3212 			  eb->start, path->slots[0]);  in add_tree_block()
3214 		return -EUCLEAN;  in add_tree_block()
3219 	BUG_ON(level == -1);  in add_tree_block()
3223 		return -ENOMEM;  in add_tree_block()
3225 	block->bytenr = extent_key->objectid;  in add_tree_block()
3226 	block->key.objectid = rc->extent_root->fs_info->nodesize;  in add_tree_block()
3227 	block->key.offset = generation;  in add_tree_block()
3228 	block->level = level;  in add_tree_block()
3229 	block->key_ready = false;  in add_tree_block()
3230 	block->owner = owner;  in add_tree_block()
3232 	rb_node = rb_simple_insert(blocks, block->bytenr, &block->rb_node);  in add_tree_block()
3234 		btrfs_backref_panic(rc->extent_root->fs_info, block->bytenr,  in add_tree_block()
3235 				    -EEXIST);  in add_tree_block()
3247 	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;  in __add_tree_block()
3261 		return -ENOMEM;  in __add_tree_block()
3266 		key.offset = (u64)-1;  in __add_tree_block()
3272 	path->search_commit_root = 1;  in __add_tree_block()
3273 	path->skip_locking = 1;  in __add_tree_block()
3274 	ret = btrfs_search_slot(NULL, rc->extent_root, &key, path, 0, 0);  in __add_tree_block()
3279 		if (path->slots[0]) {  in __add_tree_block()
3280 			path->slots[0]--;  in __add_tree_block()
3281 			btrfs_item_key_to_cpu(path->nodes[0], &key,  in __add_tree_block()
3282 					      path->slots[0]);  in __add_tree_block()
3298 		btrfs_print_leaf(path->nodes[0]);  in __add_tree_block()
3303 		ret = -EINVAL;  in __add_tree_block()
3318 	struct btrfs_root *root = fs_info->tree_root;  in delete_block_group_cache()  local
3325 	inode = btrfs_iget(ino, root);  in delete_block_group_cache()
3327 		return -ENOENT;  in delete_block_group_cache()
3331 						 &fs_info->global_block_rsv);  in delete_block_group_cache()
3335 	trans = btrfs_join_transaction(root);  in delete_block_group_cache()
3351  * Locate the free space cache EXTENT_DATA in root tree leaf and delete the
3386 		return -ENOENT;  in delete_v1_space_cache()
3387 	ret = delete_block_group_cache(leaf->fs_info, block_group, NULL,  in delete_v1_space_cache()
3403 	const u32 blocksize = rc->extent_root->fs_info->nodesize;  in add_data_references()
3408 	ctx.bytenr = extent_key->objectid;  in add_data_references()
3410 	ctx.fs_info = rc->extent_root->fs_info;  in add_data_references()
3421 		eb = read_tree_block(ctx.fs_info, ref_node->val, &check);  in add_data_references()
3426 		ret = delete_v1_space_cache(eb, rc->block_group,  in add_data_references()
3427 					    extent_key->objectid);  in add_data_references()
3431 		ret = __add_tree_block(rc, ref_node->val, blocksize, blocks);  in add_data_references()
3448 	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;  in find_next_extent()
3454 	last = rc->block_group->start + rc->block_group->length;  in find_next_extent()
3459 		if (rc->search_start >= last) {  in find_next_extent()
3464 		key.objectid = rc->search_start;  in find_next_extent()
3468 		path->search_commit_root = 1;  in find_next_extent()
3469 		path->skip_locking = 1;  in find_next_extent()
3470 		ret = btrfs_search_slot(NULL, rc->extent_root, &key, path,  in find_next_extent()
3475 		leaf = path->nodes[0];  in find_next_extent()
3476 		if (path->slots[0] >= btrfs_header_nritems(leaf)) {  in find_next_extent()
3477 			ret = btrfs_next_leaf(rc->extent_root, path);  in find_next_extent()
3480 			leaf = path->nodes[0];  in find_next_extent()
3483 		btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);  in find_next_extent()
3491 			path->slots[0]++;  in find_next_extent()
3496 		    key.objectid + key.offset <= rc->search_start) {  in find_next_extent()
3497 			path->slots[0]++;  in find_next_extent()
3502 		    key.objectid + fs_info->nodesize <=  in find_next_extent()
3503 		    rc->search_start) {  in find_next_extent()
3504 			path->slots[0]++;  in find_next_extent()
3508 		block_found = find_first_extent_bit(&rc->processed_blocks,  in find_next_extent()
3514 			rc->search_start = end + 1;  in find_next_extent()
3517 				rc->search_start = key.objectid + key.offset;  in find_next_extent()
3519 				rc->search_start = key.objectid +  in find_next_extent()
3520 					fs_info->nodesize;  in find_next_extent()
3531 	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;  in set_reloc_control()
3533 	mutex_lock(&fs_info->reloc_mutex);  in set_reloc_control()
3534 	fs_info->reloc_ctl = rc;  in set_reloc_control()
3535 	mutex_unlock(&fs_info->reloc_mutex);  in set_reloc_control()
3540 	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;  in unset_reloc_control()
3542 	mutex_lock(&fs_info->reloc_mutex);  in unset_reloc_control()
3543 	fs_info->reloc_ctl = NULL;  in unset_reloc_control()
3544 	mutex_unlock(&fs_info->reloc_mutex);  in unset_reloc_control()
3553 	rc->block_rsv = btrfs_alloc_block_rsv(rc->extent_root->fs_info,  in prepare_to_relocate()
3555 	if (!rc->block_rsv)  in prepare_to_relocate()
3556 		return -ENOMEM;  in prepare_to_relocate()
3558 	memset(&rc->cluster, 0, sizeof(rc->cluster));  in prepare_to_relocate()
3559 	rc->search_start = rc->block_group->start;  in prepare_to_relocate()
3560 	rc->extents_found = 0;  in prepare_to_relocate()
3561 	rc->nodes_relocated = 0;  in prepare_to_relocate()
3562 	rc->merging_rsv_size = 0;  in prepare_to_relocate()
3563 	rc->reserved_bytes = 0;  in prepare_to_relocate()
3564 	rc->block_rsv->size = rc->extent_root->fs_info->nodesize *  in prepare_to_relocate()
3566 	ret = btrfs_block_rsv_refill(rc->extent_root->fs_info,  in prepare_to_relocate()
3567 				     rc->block_rsv, rc->block_rsv->size,  in prepare_to_relocate()
3572 	rc->create_reloc_tree = true;  in prepare_to_relocate()
3575 	trans = btrfs_join_transaction(rc->extent_root);  in prepare_to_relocate()
3595 	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;  in relocate_block_group()
3608 		return -ENOMEM;  in relocate_block_group()
3609 	path->reada = READA_FORWARD;  in relocate_block_group()
3618 		rc->reserved_bytes = 0;  in relocate_block_group()
3619 		ret = btrfs_block_rsv_refill(fs_info, rc->block_rsv,  in relocate_block_group()
3620 					     rc->block_rsv->size,  in relocate_block_group()
3627 		trans = btrfs_start_transaction(rc->extent_root, 0);  in relocate_block_group()
3634 		if (rc->backref_cache.last_trans != trans->transid)  in relocate_block_group()
3635 			btrfs_backref_release_cache(&rc->backref_cache);  in relocate_block_group()
3636 		rc->backref_cache.last_trans = trans->transid;  in relocate_block_group()
3644 		rc->extents_found++;  in relocate_block_group()
3646 		ei = btrfs_item_ptr(path->nodes[0], path->slots[0],  in relocate_block_group()
3648 		flags = btrfs_extent_flags(path->nodes[0], ei);  in relocate_block_group()
3652 		 * need to note the owner on the reloc data root so that when  in relocate_block_group()
3654 		 * correct eventual owner (rather than the reloc data root).  in relocate_block_group()
3657 			struct btrfs_root *root = BTRFS_I(rc->data_inode)->root;  in relocate_block_group()  local
3659 								 path->nodes[0],  in relocate_block_group()
3660 								 path->slots[0]);  in relocate_block_group()
3662 			root->relocation_src_root = owning_root_id;  in relocate_block_group()
3667 		} else if (rc->stage == UPDATE_DATA_PTRS &&  in relocate_block_group()
3682 				if (ret != -EAGAIN) {  in relocate_block_group()
3686 				rc->extents_found--;  in relocate_block_group()
3687 				rc->search_start = key.objectid;  in relocate_block_group()
3695 		if (rc->stage == MOVE_DATA_EXTENTS &&  in relocate_block_group()
3697 			rc->found_file_extent = true;  in relocate_block_group()
3705 			err = -ECANCELED;  in relocate_block_group()
3709 	if (trans && progress && err == -ENOSPC) {  in relocate_block_group()
3710 		ret = btrfs_force_chunk_alloc(trans, rc->block_group->flags);  in relocate_block_group()
3719 	clear_extent_bits(&rc->processed_blocks, 0, (u64)-1, EXTENT_DIRTY);  in relocate_block_group()
3732 	rc->create_reloc_tree = false;  in relocate_block_group()
3735 	btrfs_backref_release_cache(&rc->backref_cache);  in relocate_block_group()
3736 	btrfs_block_rsv_release(fs_info, rc->block_rsv, (u64)-1, NULL);  in relocate_block_group()
3750 	rc->merge_reloc_tree = false;  in relocate_block_group()
3752 	btrfs_block_rsv_release(fs_info, rc->block_rsv, (u64)-1, NULL);  in relocate_block_group()
3755 	trans = btrfs_join_transaction(rc->extent_root);  in relocate_block_group()
3767 	btrfs_free_block_rsv(fs_info, rc->block_rsv);  in relocate_block_group()
3773 				 struct btrfs_root *root, u64 objectid)  in __insert_orphan_inode()  argument
3782 		return -ENOMEM;  in __insert_orphan_inode()
3784 	ret = btrfs_insert_empty_inode(trans, root, path, objectid);  in __insert_orphan_inode()
3788 	leaf = path->nodes[0];  in __insert_orphan_inode()
3789 	item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_inode_item);  in __insert_orphan_inode()
3803 				struct btrfs_root *root, u64 objectid)  in delete_orphan_inode()  argument
3811 		ret = -ENOMEM;  in delete_orphan_inode()
3818 	ret = btrfs_search_slot(trans, root, &key, path, -1, 1);  in delete_orphan_inode()
3821 			ret = -ENOENT;  in delete_orphan_inode()
3824 	ret = btrfs_del_item(trans, root, path);  in delete_orphan_inode()
3841 	struct btrfs_root *root;  in create_reloc_inode()  local
3845 	root = btrfs_grab_root(fs_info->data_reloc_root);  in create_reloc_inode()
3846 	trans = btrfs_start_transaction(root, 6);  in create_reloc_inode()
3848 		btrfs_put_root(root);  in create_reloc_inode()
3852 	ret = btrfs_get_free_objectid(root, &objectid);  in create_reloc_inode()
3856 	ret = __insert_orphan_inode(trans, root, objectid);  in create_reloc_inode()
3860 	inode = btrfs_iget(objectid, root);  in create_reloc_inode()
3862 		delete_orphan_inode(trans, root, objectid);  in create_reloc_inode()
3867 	BTRFS_I(inode)->reloc_block_group_start = group->start;  in create_reloc_inode()
3871 	btrfs_put_root(root);  in create_reloc_inode()
3887  *   -EINPROGRESS  operation is already in progress, that's probably a bug
3888  *   -ECANCELED    cancellation request was set before the operation started
3892 	if (test_and_set_bit(BTRFS_FS_RELOC_RUNNING, &fs_info->flags)) {  in reloc_chunk_start()
3895 		return -EINPROGRESS;  in reloc_chunk_start()
3898 	if (atomic_read(&fs_info->reloc_cancel_req) > 0) {  in reloc_chunk_start()
3904 		atomic_set(&fs_info->reloc_cancel_req, 0);  in reloc_chunk_start()
3905 		return -ECANCELED;  in reloc_chunk_start()
3916 	if (atomic_read(&fs_info->reloc_cancel_req) > 0)  in reloc_chunk_end()
3918 	clear_and_wake_up_bit(BTRFS_FS_RELOC_RUNNING, &fs_info->flags);  in reloc_chunk_end()
3919 	atomic_set(&fs_info->reloc_cancel_req, 0);  in reloc_chunk_end()
3930 	INIT_LIST_HEAD(&rc->reloc_roots);  in alloc_reloc_control()
3931 	INIT_LIST_HEAD(&rc->dirty_subvol_roots);  in alloc_reloc_control()
3932 	btrfs_backref_init_cache(fs_info, &rc->backref_cache, true);  in alloc_reloc_control()
3933 	rc->reloc_root_tree.rb_root = RB_ROOT;  in alloc_reloc_control()
3934 	spin_lock_init(&rc->reloc_root_tree.lock);  in alloc_reloc_control()
3935 	extent_io_tree_init(fs_info, &rc->processed_blocks, IO_TREE_RELOC_BLOCKS);  in alloc_reloc_control()
3941 	struct mapping_node *node, *tmp;  in free_reloc_control()  local
3943 	free_reloc_roots(&rc->reloc_roots);  in free_reloc_control()
3944 	rbtree_postorder_for_each_entry_safe(node, tmp,  in free_reloc_control()
3945 			&rc->reloc_root_tree.rb_root, rb_node)  in free_reloc_control()
3946 		kfree(node);  in free_reloc_control()
3958 	btrfs_describe_block_groups(block_group->flags, buf, sizeof(buf));  in describe_relocation()
3960 	btrfs_info(block_group->fs_info, "relocating block group %llu flags %s",  in describe_relocation()
3961 		   block_group->start, buf);  in describe_relocation()
3988 	 * This only gets set if we had a half-deleted snapshot on mount.  We  in btrfs_relocate_block_group()
3992 	ret = wait_on_bit(&fs_info->flags, BTRFS_FS_UNFINISHED_DROPS, TASK_INTERRUPTIBLE);  in btrfs_relocate_block_group()
3998 		return -EINTR;  in btrfs_relocate_block_group()
4002 		return -ENOENT;  in btrfs_relocate_block_group()
4012 	if (bg->flags & BTRFS_BLOCK_GROUP_DATA)  in btrfs_relocate_block_group()
4013 		ASSERT(sb_write_started(fs_info->sb));  in btrfs_relocate_block_group()
4017 		return -ETXTBSY;  in btrfs_relocate_block_group()
4023 		return -ENOMEM;  in btrfs_relocate_block_group()
4032 	rc->extent_root = extent_root;  in btrfs_relocate_block_group()
4033 	rc->block_group = bg;  in btrfs_relocate_block_group()
4035 	ret = btrfs_inc_block_group_ro(rc->block_group, true);  in btrfs_relocate_block_group()
4044 		err = -ENOMEM;  in btrfs_relocate_block_group()
4048 	inode = lookup_free_space_inode(rc->block_group, path);  in btrfs_relocate_block_group()
4052 		ret = delete_block_group_cache(fs_info, rc->block_group, inode, 0);  in btrfs_relocate_block_group()
4056 	if (ret && ret != -ENOENT) {  in btrfs_relocate_block_group()
4061 	rc->data_inode = create_reloc_inode(fs_info, rc->block_group);  in btrfs_relocate_block_group()
4062 	if (IS_ERR(rc->data_inode)) {  in btrfs_relocate_block_group()
4063 		err = PTR_ERR(rc->data_inode);  in btrfs_relocate_block_group()
4064 		rc->data_inode = NULL;  in btrfs_relocate_block_group()
4068 	describe_relocation(rc->block_group);  in btrfs_relocate_block_group()
4070 	btrfs_wait_block_group_reservations(rc->block_group);  in btrfs_relocate_block_group()
4071 	btrfs_wait_nocow_writers(rc->block_group);  in btrfs_relocate_block_group()
4072 	btrfs_wait_ordered_roots(fs_info, U64_MAX, rc->block_group);  in btrfs_relocate_block_group()
4074 	ret = btrfs_zone_finish(rc->block_group);  in btrfs_relocate_block_group()
4075 	WARN_ON(ret && ret != -EAGAIN);  in btrfs_relocate_block_group()
4080 		mutex_lock(&fs_info->cleaner_mutex);  in btrfs_relocate_block_group()
4082 		mutex_unlock(&fs_info->cleaner_mutex);  in btrfs_relocate_block_group()
4086 		finishes_stage = rc->stage;  in btrfs_relocate_block_group()
4091 		 * BUG_ON(rc->stage == UPDATE_DATA_PTRS) in  in btrfs_relocate_block_group()
4096 		if (rc->stage == MOVE_DATA_EXTENTS && rc->found_file_extent) {  in btrfs_relocate_block_group()
4097 			ret = btrfs_wait_ordered_range(BTRFS_I(rc->data_inode), 0,  in btrfs_relocate_block_group()
4098 						       (u64)-1);  in btrfs_relocate_block_group()
4101 			invalidate_mapping_pages(rc->data_inode->i_mapping,  in btrfs_relocate_block_group()
4102 						 0, -1);  in btrfs_relocate_block_group()
4103 			rc->stage = UPDATE_DATA_PTRS;  in btrfs_relocate_block_group()
4109 		if (rc->extents_found == 0)  in btrfs_relocate_block_group()
4113 			   rc->extents_found, stage_to_string(finishes_stage));  in btrfs_relocate_block_group()
4116 	WARN_ON(rc->block_group->pinned > 0);  in btrfs_relocate_block_group()
4117 	WARN_ON(rc->block_group->reserved > 0);  in btrfs_relocate_block_group()
4118 	WARN_ON(rc->block_group->used > 0);  in btrfs_relocate_block_group()
4121 		btrfs_dec_block_group_ro(rc->block_group);  in btrfs_relocate_block_group()
4122 	iput(rc->data_inode);  in btrfs_relocate_block_group()
4130 static noinline_for_stack int mark_garbage_root(struct btrfs_root *root)  in mark_garbage_root()  argument
4132 	struct btrfs_fs_info *fs_info = root->fs_info;  in mark_garbage_root()
4136 	trans = btrfs_start_transaction(fs_info->tree_root, 0);  in mark_garbage_root()
4140 	memset(&root->root_item.drop_progress, 0,  in mark_garbage_root()
4141 		sizeof(root->root_item.drop_progress));  in mark_garbage_root()
4142 	btrfs_set_root_drop_level(&root->root_item, 0);  in mark_garbage_root()
4143 	btrfs_set_root_refs(&root->root_item, 0);  in mark_garbage_root()
4144 	ret = btrfs_update_root(trans, fs_info->tree_root,  in mark_garbage_root()
4145 				&root->root_key, &root->root_item);  in mark_garbage_root()
4174 		return -ENOMEM;  in btrfs_recover_relocation()
4175 	path->reada = READA_BACK;  in btrfs_recover_relocation()
4179 	key.offset = (u64)-1;  in btrfs_recover_relocation()
4182 		ret = btrfs_search_slot(NULL, fs_info->tree_root, &key,  in btrfs_recover_relocation()
4187 			if (path->slots[0] == 0)  in btrfs_recover_relocation()
4189 			path->slots[0]--;  in btrfs_recover_relocation()
4192 		leaf = path->nodes[0];  in btrfs_recover_relocation()
4193 		btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);  in btrfs_recover_relocation()
4200 		reloc_root = btrfs_read_tree_root(fs_info->tree_root, &key);  in btrfs_recover_relocation()
4206 		set_bit(BTRFS_ROOT_SHAREABLE, &reloc_root->state);  in btrfs_recover_relocation()
4207 		list_add(&reloc_root->root_list, &reloc_roots);  in btrfs_recover_relocation()
4209 		if (btrfs_root_refs(&reloc_root->root_item) > 0) {  in btrfs_recover_relocation()
4211 					reloc_root->root_key.offset, false);  in btrfs_recover_relocation()
4214 				if (ret != -ENOENT)  in btrfs_recover_relocation()
4228 		key.offset--;  in btrfs_recover_relocation()
4237 		ret = -ENOMEM;  in btrfs_recover_relocation()
4245 	rc->extent_root = btrfs_extent_root(fs_info, 0);  in btrfs_recover_relocation()
4249 	trans = btrfs_join_transaction(rc->extent_root);  in btrfs_recover_relocation()
4255 	rc->merge_reloc_tree = true;  in btrfs_recover_relocation()
4260 		list_del(&reloc_root->root_list);  in btrfs_recover_relocation()
4262 		if (btrfs_root_refs(&reloc_root->root_item) == 0) {  in btrfs_recover_relocation()
4263 			list_add_tail(&reloc_root->root_list,  in btrfs_recover_relocation()
4264 				      &rc->reloc_roots);  in btrfs_recover_relocation()
4268 		fs_root = btrfs_get_fs_root(fs_info, reloc_root->root_key.offset,  in btrfs_recover_relocation()
4272 			list_add_tail(&reloc_root->root_list, &reloc_roots);  in btrfs_recover_relocation()
4278 		ASSERT(ret != -EEXIST);  in btrfs_recover_relocation()
4280 			list_add_tail(&reloc_root->root_list, &reloc_roots);  in btrfs_recover_relocation()
4285 		fs_root->reloc_root = btrfs_grab_root(reloc_root);  in btrfs_recover_relocation()
4297 	trans = btrfs_join_transaction(rc->extent_root);  in btrfs_recover_relocation()
4319 		fs_root = btrfs_grab_root(fs_info->data_reloc_root);  in btrfs_recover_relocation()
4331  * it also saves CPU time to re-calculate the checksum.
4335 	struct btrfs_inode *inode = ordered->inode;  in btrfs_reloc_clone_csums()
4336 	struct btrfs_fs_info *fs_info = inode->root->fs_info;  in btrfs_reloc_clone_csums()
4337 	u64 disk_bytenr = ordered->file_offset + inode->reloc_block_group_start;  in btrfs_reloc_clone_csums()
4343 				      disk_bytenr + ordered->num_bytes - 1,  in btrfs_reloc_clone_csums()
4354 		list_del_init(&sums->list);  in btrfs_reloc_clone_csums()
4368 		sums->logical = ordered->disk_bytenr + sums->logical - disk_bytenr;  in btrfs_reloc_clone_csums()
4376 			  struct btrfs_root *root,  in btrfs_reloc_cow_block()  argument
4380 	struct btrfs_fs_info *fs_info = root->fs_info;  in btrfs_reloc_cow_block()
4382 	struct btrfs_backref_node *node;  in btrfs_reloc_cow_block()  local
4387 	rc = fs_info->reloc_ctl;  in btrfs_reloc_cow_block()
4391 	BUG_ON(rc->stage == UPDATE_DATA_PTRS && btrfs_is_data_reloc_root(root));  in btrfs_reloc_cow_block()
4395 	    btrfs_root_last_snapshot(&root->root_item))  in btrfs_reloc_cow_block()
4398 	if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID && rc->create_reloc_tree) {  in btrfs_reloc_cow_block()
4401 		node = rc->backref_cache.path[level];  in btrfs_reloc_cow_block()
4402 		BUG_ON(node->bytenr != buf->start &&  in btrfs_reloc_cow_block()
4403 		       node->new_bytenr != buf->start);  in btrfs_reloc_cow_block()
4405 		btrfs_backref_drop_node_buffer(node);  in btrfs_reloc_cow_block()
4406 		atomic_inc(&cow->refs);  in btrfs_reloc_cow_block()
4407 		node->eb = cow;  in btrfs_reloc_cow_block()
4408 		node->new_bytenr = cow->start;  in btrfs_reloc_cow_block()
4410 		if (!node->pending) {  in btrfs_reloc_cow_block()
4411 			list_move_tail(&node->list,  in btrfs_reloc_cow_block()
4412 				       &rc->backref_cache.pending[level]);  in btrfs_reloc_cow_block()
4413 			node->pending = 1;  in btrfs_reloc_cow_block()
4417 			mark_block_processed(rc, node);  in btrfs_reloc_cow_block()
4420 			rc->nodes_relocated += buf->len;  in btrfs_reloc_cow_block()
4423 	if (level == 0 && first_cow && rc->stage == UPDATE_DATA_PTRS)  in btrfs_reloc_cow_block()
4424 		ret = replace_file_extents(trans, rc, root, cow);  in btrfs_reloc_cow_block()
4435 	struct btrfs_root *root = pending->root;  in btrfs_reloc_pre_snapshot()  local
4436 	struct reloc_control *rc = root->fs_info->reloc_ctl;  in btrfs_reloc_pre_snapshot()
4438 	if (!rc || !have_reloc_root(root))  in btrfs_reloc_pre_snapshot()
4441 	if (!rc->merge_reloc_tree)  in btrfs_reloc_pre_snapshot()
4444 	root = root->reloc_root;  in btrfs_reloc_pre_snapshot()
4445 	BUG_ON(btrfs_root_refs(&root->root_item) == 0);  in btrfs_reloc_pre_snapshot()
4456 	*bytes_to_reserve += rc->nodes_relocated;  in btrfs_reloc_pre_snapshot()
4461  * and create reloc root for the newly created snapshot
4464  * references held on the reloc_root, one for root->reloc_root and one for
4465  * rc->reloc_roots.
4470 	struct btrfs_root *root = pending->root;  in btrfs_reloc_post_snapshot()  local
4473 	struct reloc_control *rc = root->fs_info->reloc_ctl;  in btrfs_reloc_post_snapshot()
4476 	if (!rc || !have_reloc_root(root))  in btrfs_reloc_post_snapshot()
4479 	rc = root->fs_info->reloc_ctl;  in btrfs_reloc_post_snapshot()
4480 	rc->merging_rsv_size += rc->nodes_relocated;  in btrfs_reloc_post_snapshot()
4482 	if (rc->merge_reloc_tree) {  in btrfs_reloc_post_snapshot()
4483 		ret = btrfs_block_rsv_migrate(&pending->block_rsv,  in btrfs_reloc_post_snapshot()
4484 					      rc->block_rsv,  in btrfs_reloc_post_snapshot()
4485 					      rc->nodes_relocated, true);  in btrfs_reloc_post_snapshot()
4490 	new_root = pending->snap;  in btrfs_reloc_post_snapshot()
4491 	reloc_root = create_reloc_root(trans, root->reloc_root, btrfs_root_id(new_root));  in btrfs_reloc_post_snapshot()
4496 	ASSERT(ret != -EEXIST);  in btrfs_reloc_post_snapshot()
4502 	new_root->reloc_root = btrfs_grab_root(reloc_root);  in btrfs_reloc_post_snapshot()
4504 	if (rc->create_reloc_tree)  in btrfs_reloc_post_snapshot()
4505 		ret = clone_backref_node(trans, rc, root, reloc_root);  in btrfs_reloc_post_snapshot()
4518 	lockdep_assert_held(&fs_info->reloc_mutex);  in btrfs_get_reloc_bg_bytenr()
4520 	if (fs_info->reloc_ctl && fs_info->reloc_ctl->block_group)  in btrfs_get_reloc_bg_bytenr()
4521 		logical = fs_info->reloc_ctl->block_group->start;  in btrfs_get_reloc_bg_bytenr()