xref: /linux/fs/btrfs/relocation.c (revision 36f353a1ebf88280f58d1ebfe2731251d9159456)
1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  * Copyright (C) 2009 Oracle.  All rights reserved.
4  */
5 
6 #include <linux/sched.h>
7 #include <linux/pagemap.h>
8 #include <linux/writeback.h>
9 #include <linux/blkdev.h>
10 #include <linux/rbtree.h>
11 #include <linux/slab.h>
12 #include <linux/error-injection.h>
13 #include "ctree.h"
14 #include "disk-io.h"
15 #include "transaction.h"
16 #include "volumes.h"
17 #include "locking.h"
18 #include "btrfs_inode.h"
19 #include "async-thread.h"
20 #include "free-space-cache.h"
21 #include "qgroup.h"
22 #include "print-tree.h"
23 #include "delalloc-space.h"
24 #include "block-group.h"
25 #include "backref.h"
26 #include "misc.h"
27 #include "subpage.h"
28 #include "zoned.h"
29 #include "inode-item.h"
30 #include "space-info.h"
31 #include "fs.h"
32 #include "accessors.h"
33 #include "extent-tree.h"
34 #include "root-tree.h"
35 #include "file-item.h"
36 #include "relocation.h"
37 #include "super.h"
38 #include "tree-checker.h"
39 
40 /*
41  * Relocation overview
42  *
43  * [What does relocation do]
44  *
45  * The objective of relocation is to relocate all extents of the target block
46  * group to other block groups.
47  * This is utilized by resize (shrink only), profile converting, compacting
48  * space, or balance routine to spread chunks over devices.
49  *
50  * 		Before		|		After
51  * ------------------------------------------------------------------
52  *  BG A: 10 data extents	| BG A: deleted
53  *  BG B:  2 data extents	| BG B: 10 data extents (2 old + 8 relocated)
54  *  BG C:  1 extents		| BG C:  3 data extents (1 old + 2 relocated)
55  *
56  * [How does relocation work]
57  *
58  * 1.   Mark the target block group read-only
59  *      New extents won't be allocated from the target block group.
60  *
61  * 2.1  Record each extent in the target block group
62  *      To build a proper map of extents to be relocated.
63  *
64  * 2.2  Build data reloc tree and reloc trees
65  *      Data reloc tree will contain an inode, recording all newly relocated
66  *      data extents.
67  *      There will be only one data reloc tree for one data block group.
68  *
69  *      Reloc tree will be a special snapshot of its source tree, containing
70  *      relocated tree blocks.
71  *      Each tree referring to a tree block in target block group will get its
72  *      reloc tree built.
73  *
74  * 2.3  Swap source tree with its corresponding reloc tree
75  *      Each involved tree only refers to new extents after swap.
76  *
77  * 3.   Cleanup reloc trees and data reloc tree.
78  *      As old extents in the target block group are still referenced by reloc
79  *      trees, we need to clean them up before really freeing the target block
80  *      group.
81  *
82  * The main complexity is in steps 2.2 and 2.3.
83  *
84  * The entry point of relocation is relocate_block_group() function.
85  */
86 
87 #define RELOCATION_RESERVED_NODES	256
88 /*
89  * map address of tree root to tree
90  */
91 struct mapping_node {
92 	struct {
93 		struct rb_node rb_node;
94 		u64 bytenr;
95 	}; /* Use rb_simle_node for search/insert */
96 	void *data;
97 };
98 
99 struct mapping_tree {
100 	struct rb_root rb_root;
101 	spinlock_t lock;
102 };
103 
104 /*
105  * present a tree block to process
106  */
107 struct tree_block {
108 	struct {
109 		struct rb_node rb_node;
110 		u64 bytenr;
111 	}; /* Use rb_simple_node for search/insert */
112 	u64 owner;
113 	struct btrfs_key key;
114 	u8 level;
115 	bool key_ready;
116 };
117 
118 #define MAX_EXTENTS 128
119 
120 struct file_extent_cluster {
121 	u64 start;
122 	u64 end;
123 	u64 boundary[MAX_EXTENTS];
124 	unsigned int nr;
125 	u64 owning_root;
126 };
127 
128 /* Stages of data relocation. */
129 enum reloc_stage {
130 	MOVE_DATA_EXTENTS,
131 	UPDATE_DATA_PTRS
132 };
133 
134 struct reloc_control {
135 	/* block group to relocate */
136 	struct btrfs_block_group *block_group;
137 	/* extent tree */
138 	struct btrfs_root *extent_root;
139 	/* inode for moving data */
140 	struct inode *data_inode;
141 
142 	struct btrfs_block_rsv *block_rsv;
143 
144 	struct btrfs_backref_cache backref_cache;
145 
146 	struct file_extent_cluster cluster;
147 	/* tree blocks have been processed */
148 	struct extent_io_tree processed_blocks;
149 	/* map start of tree root to corresponding reloc tree */
150 	struct mapping_tree reloc_root_tree;
151 	/* list of reloc trees */
152 	struct list_head reloc_roots;
153 	/* list of subvolume trees that get relocated */
154 	struct list_head dirty_subvol_roots;
155 	/* size of metadata reservation for merging reloc trees */
156 	u64 merging_rsv_size;
157 	/* size of relocated tree nodes */
158 	u64 nodes_relocated;
159 	/* reserved size for block group relocation*/
160 	u64 reserved_bytes;
161 
162 	u64 search_start;
163 	u64 extents_found;
164 
165 	enum reloc_stage stage;
166 	bool create_reloc_tree;
167 	bool merge_reloc_tree;
168 	bool found_file_extent;
169 };
170 
171 static void mark_block_processed(struct reloc_control *rc,
172 				 struct btrfs_backref_node *node)
173 {
174 	u32 blocksize;
175 
176 	if (node->level == 0 ||
177 	    in_range(node->bytenr, rc->block_group->start,
178 		     rc->block_group->length)) {
179 		blocksize = rc->extent_root->fs_info->nodesize;
180 		set_extent_bit(&rc->processed_blocks, node->bytenr,
181 			       node->bytenr + blocksize - 1, EXTENT_DIRTY, NULL);
182 	}
183 	node->processed = 1;
184 }
185 
186 /*
187  * walk up backref nodes until reach node presents tree root
188  */
189 static struct btrfs_backref_node *walk_up_backref(
190 		struct btrfs_backref_node *node,
191 		struct btrfs_backref_edge *edges[], int *index)
192 {
193 	struct btrfs_backref_edge *edge;
194 	int idx = *index;
195 
196 	while (!list_empty(&node->upper)) {
197 		edge = list_entry(node->upper.next,
198 				  struct btrfs_backref_edge, list[LOWER]);
199 		edges[idx++] = edge;
200 		node = edge->node[UPPER];
201 	}
202 	BUG_ON(node->detached);
203 	*index = idx;
204 	return node;
205 }
206 
207 /*
208  * walk down backref nodes to find start of next reference path
209  */
210 static struct btrfs_backref_node *walk_down_backref(
211 		struct btrfs_backref_edge *edges[], int *index)
212 {
213 	struct btrfs_backref_edge *edge;
214 	struct btrfs_backref_node *lower;
215 	int idx = *index;
216 
217 	while (idx > 0) {
218 		edge = edges[idx - 1];
219 		lower = edge->node[LOWER];
220 		if (list_is_last(&edge->list[LOWER], &lower->upper)) {
221 			idx--;
222 			continue;
223 		}
224 		edge = list_entry(edge->list[LOWER].next,
225 				  struct btrfs_backref_edge, list[LOWER]);
226 		edges[idx - 1] = edge;
227 		*index = idx;
228 		return edge->node[UPPER];
229 	}
230 	*index = 0;
231 	return NULL;
232 }
233 
234 static void update_backref_node(struct btrfs_backref_cache *cache,
235 				struct btrfs_backref_node *node, u64 bytenr)
236 {
237 	struct rb_node *rb_node;
238 	rb_erase(&node->rb_node, &cache->rb_root);
239 	node->bytenr = bytenr;
240 	rb_node = rb_simple_insert(&cache->rb_root, node->bytenr, &node->rb_node);
241 	if (rb_node)
242 		btrfs_backref_panic(cache->fs_info, bytenr, -EEXIST);
243 }
244 
245 /*
246  * update backref cache after a transaction commit
247  */
248 static int update_backref_cache(struct btrfs_trans_handle *trans,
249 				struct btrfs_backref_cache *cache)
250 {
251 	struct btrfs_backref_node *node;
252 	int level = 0;
253 
254 	if (cache->last_trans == 0) {
255 		cache->last_trans = trans->transid;
256 		return 0;
257 	}
258 
259 	if (cache->last_trans == trans->transid)
260 		return 0;
261 
262 	/*
263 	 * detached nodes are used to avoid unnecessary backref
264 	 * lookup. transaction commit changes the extent tree.
265 	 * so the detached nodes are no longer useful.
266 	 */
267 	while (!list_empty(&cache->detached)) {
268 		node = list_entry(cache->detached.next,
269 				  struct btrfs_backref_node, list);
270 		btrfs_backref_cleanup_node(cache, node);
271 	}
272 
273 	while (!list_empty(&cache->changed)) {
274 		node = list_entry(cache->changed.next,
275 				  struct btrfs_backref_node, list);
276 		list_del_init(&node->list);
277 		BUG_ON(node->pending);
278 		update_backref_node(cache, node, node->new_bytenr);
279 	}
280 
281 	/*
282 	 * some nodes can be left in the pending list if there were
283 	 * errors during processing the pending nodes.
284 	 */
285 	for (level = 0; level < BTRFS_MAX_LEVEL; level++) {
286 		list_for_each_entry(node, &cache->pending[level], list) {
287 			BUG_ON(!node->pending);
288 			if (node->bytenr == node->new_bytenr)
289 				continue;
290 			update_backref_node(cache, node, node->new_bytenr);
291 		}
292 	}
293 
294 	cache->last_trans = 0;
295 	return 1;
296 }
297 
298 static bool reloc_root_is_dead(const struct btrfs_root *root)
299 {
300 	/*
301 	 * Pair with set_bit/clear_bit in clean_dirty_subvols and
302 	 * btrfs_update_reloc_root. We need to see the updated bit before
303 	 * trying to access reloc_root
304 	 */
305 	smp_rmb();
306 	if (test_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state))
307 		return true;
308 	return false;
309 }
310 
311 /*
312  * Check if this subvolume tree has valid reloc tree.
313  *
314  * Reloc tree after swap is considered dead, thus not considered as valid.
315  * This is enough for most callers, as they don't distinguish dead reloc root
316  * from no reloc root.  But btrfs_should_ignore_reloc_root() below is a
317  * special case.
318  */
319 static bool have_reloc_root(const struct btrfs_root *root)
320 {
321 	if (reloc_root_is_dead(root))
322 		return false;
323 	if (!root->reloc_root)
324 		return false;
325 	return true;
326 }
327 
328 bool btrfs_should_ignore_reloc_root(const struct btrfs_root *root)
329 {
330 	struct btrfs_root *reloc_root;
331 
332 	if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state))
333 		return false;
334 
335 	/* This root has been merged with its reloc tree, we can ignore it */
336 	if (reloc_root_is_dead(root))
337 		return true;
338 
339 	reloc_root = root->reloc_root;
340 	if (!reloc_root)
341 		return false;
342 
343 	if (btrfs_header_generation(reloc_root->commit_root) ==
344 	    root->fs_info->running_transaction->transid)
345 		return false;
346 	/*
347 	 * If there is reloc tree and it was created in previous transaction
348 	 * backref lookup can find the reloc tree, so backref node for the fs
349 	 * tree root is useless for relocation.
350 	 */
351 	return true;
352 }
353 
354 /*
355  * find reloc tree by address of tree root
356  */
357 struct btrfs_root *find_reloc_root(struct btrfs_fs_info *fs_info, u64 bytenr)
358 {
359 	struct reloc_control *rc = fs_info->reloc_ctl;
360 	struct rb_node *rb_node;
361 	struct mapping_node *node;
362 	struct btrfs_root *root = NULL;
363 
364 	ASSERT(rc);
365 	spin_lock(&rc->reloc_root_tree.lock);
366 	rb_node = rb_simple_search(&rc->reloc_root_tree.rb_root, bytenr);
367 	if (rb_node) {
368 		node = rb_entry(rb_node, struct mapping_node, rb_node);
369 		root = node->data;
370 	}
371 	spin_unlock(&rc->reloc_root_tree.lock);
372 	return btrfs_grab_root(root);
373 }
374 
375 /*
376  * For useless nodes, do two major clean ups:
377  *
378  * - Cleanup the children edges and nodes
379  *   If child node is also orphan (no parent) during cleanup, then the child
380  *   node will also be cleaned up.
381  *
382  * - Freeing up leaves (level 0), keeps nodes detached
383  *   For nodes, the node is still cached as "detached"
384  *
385  * Return false if @node is not in the @useless_nodes list.
386  * Return true if @node is in the @useless_nodes list.
387  */
388 static bool handle_useless_nodes(struct reloc_control *rc,
389 				 struct btrfs_backref_node *node)
390 {
391 	struct btrfs_backref_cache *cache = &rc->backref_cache;
392 	struct list_head *useless_node = &cache->useless_node;
393 	bool ret = false;
394 
395 	while (!list_empty(useless_node)) {
396 		struct btrfs_backref_node *cur;
397 
398 		cur = list_first_entry(useless_node, struct btrfs_backref_node,
399 				 list);
400 		list_del_init(&cur->list);
401 
402 		/* Only tree root nodes can be added to @useless_nodes */
403 		ASSERT(list_empty(&cur->upper));
404 
405 		if (cur == node)
406 			ret = true;
407 
408 		/* The node is the lowest node */
409 		if (cur->lowest) {
410 			list_del_init(&cur->lower);
411 			cur->lowest = 0;
412 		}
413 
414 		/* Cleanup the lower edges */
415 		while (!list_empty(&cur->lower)) {
416 			struct btrfs_backref_edge *edge;
417 			struct btrfs_backref_node *lower;
418 
419 			edge = list_entry(cur->lower.next,
420 					struct btrfs_backref_edge, list[UPPER]);
421 			list_del(&edge->list[UPPER]);
422 			list_del(&edge->list[LOWER]);
423 			lower = edge->node[LOWER];
424 			btrfs_backref_free_edge(cache, edge);
425 
426 			/* Child node is also orphan, queue for cleanup */
427 			if (list_empty(&lower->upper))
428 				list_add(&lower->list, useless_node);
429 		}
430 		/* Mark this block processed for relocation */
431 		mark_block_processed(rc, cur);
432 
433 		/*
434 		 * Backref nodes for tree leaves are deleted from the cache.
435 		 * Backref nodes for upper level tree blocks are left in the
436 		 * cache to avoid unnecessary backref lookup.
437 		 */
438 		if (cur->level > 0) {
439 			list_add(&cur->list, &cache->detached);
440 			cur->detached = 1;
441 		} else {
442 			rb_erase(&cur->rb_node, &cache->rb_root);
443 			btrfs_backref_free_node(cache, cur);
444 		}
445 	}
446 	return ret;
447 }
448 
449 /*
450  * Build backref tree for a given tree block. Root of the backref tree
451  * corresponds the tree block, leaves of the backref tree correspond roots of
452  * b-trees that reference the tree block.
453  *
454  * The basic idea of this function is check backrefs of a given block to find
455  * upper level blocks that reference the block, and then check backrefs of
456  * these upper level blocks recursively. The recursion stops when tree root is
457  * reached or backrefs for the block is cached.
458  *
459  * NOTE: if we find that backrefs for a block are cached, we know backrefs for
460  * all upper level blocks that directly/indirectly reference the block are also
461  * cached.
462  */
463 static noinline_for_stack struct btrfs_backref_node *build_backref_tree(
464 			struct btrfs_trans_handle *trans,
465 			struct reloc_control *rc, struct btrfs_key *node_key,
466 			int level, u64 bytenr)
467 {
468 	struct btrfs_backref_iter *iter;
469 	struct btrfs_backref_cache *cache = &rc->backref_cache;
470 	/* For searching parent of TREE_BLOCK_REF */
471 	struct btrfs_path *path;
472 	struct btrfs_backref_node *cur;
473 	struct btrfs_backref_node *node = NULL;
474 	struct btrfs_backref_edge *edge;
475 	int ret;
476 	int err = 0;
477 
478 	iter = btrfs_backref_iter_alloc(rc->extent_root->fs_info);
479 	if (!iter)
480 		return ERR_PTR(-ENOMEM);
481 	path = btrfs_alloc_path();
482 	if (!path) {
483 		err = -ENOMEM;
484 		goto out;
485 	}
486 
487 	node = btrfs_backref_alloc_node(cache, bytenr, level);
488 	if (!node) {
489 		err = -ENOMEM;
490 		goto out;
491 	}
492 
493 	node->lowest = 1;
494 	cur = node;
495 
496 	/* Breadth-first search to build backref cache */
497 	do {
498 		ret = btrfs_backref_add_tree_node(trans, cache, path, iter,
499 						  node_key, cur);
500 		if (ret < 0) {
501 			err = ret;
502 			goto out;
503 		}
504 		edge = list_first_entry_or_null(&cache->pending_edge,
505 				struct btrfs_backref_edge, list[UPPER]);
506 		/*
507 		 * The pending list isn't empty, take the first block to
508 		 * process
509 		 */
510 		if (edge) {
511 			list_del_init(&edge->list[UPPER]);
512 			cur = edge->node[UPPER];
513 		}
514 	} while (edge);
515 
516 	/* Finish the upper linkage of newly added edges/nodes */
517 	ret = btrfs_backref_finish_upper_links(cache, node);
518 	if (ret < 0) {
519 		err = ret;
520 		goto out;
521 	}
522 
523 	if (handle_useless_nodes(rc, node))
524 		node = NULL;
525 out:
526 	btrfs_free_path(iter->path);
527 	kfree(iter);
528 	btrfs_free_path(path);
529 	if (err) {
530 		btrfs_backref_error_cleanup(cache, node);
531 		return ERR_PTR(err);
532 	}
533 	ASSERT(!node || !node->detached);
534 	ASSERT(list_empty(&cache->useless_node) &&
535 	       list_empty(&cache->pending_edge));
536 	return node;
537 }
538 
539 /*
540  * helper to add backref node for the newly created snapshot.
541  * the backref node is created by cloning backref node that
542  * corresponds to root of source tree
543  */
544 static int clone_backref_node(struct btrfs_trans_handle *trans,
545 			      struct reloc_control *rc,
546 			      const struct btrfs_root *src,
547 			      struct btrfs_root *dest)
548 {
549 	struct btrfs_root *reloc_root = src->reloc_root;
550 	struct btrfs_backref_cache *cache = &rc->backref_cache;
551 	struct btrfs_backref_node *node = NULL;
552 	struct btrfs_backref_node *new_node;
553 	struct btrfs_backref_edge *edge;
554 	struct btrfs_backref_edge *new_edge;
555 	struct rb_node *rb_node;
556 
557 	if (cache->last_trans > 0)
558 		update_backref_cache(trans, cache);
559 
560 	rb_node = rb_simple_search(&cache->rb_root, src->commit_root->start);
561 	if (rb_node) {
562 		node = rb_entry(rb_node, struct btrfs_backref_node, rb_node);
563 		if (node->detached)
564 			node = NULL;
565 		else
566 			BUG_ON(node->new_bytenr != reloc_root->node->start);
567 	}
568 
569 	if (!node) {
570 		rb_node = rb_simple_search(&cache->rb_root,
571 					   reloc_root->commit_root->start);
572 		if (rb_node) {
573 			node = rb_entry(rb_node, struct btrfs_backref_node,
574 					rb_node);
575 			BUG_ON(node->detached);
576 		}
577 	}
578 
579 	if (!node)
580 		return 0;
581 
582 	new_node = btrfs_backref_alloc_node(cache, dest->node->start,
583 					    node->level);
584 	if (!new_node)
585 		return -ENOMEM;
586 
587 	new_node->lowest = node->lowest;
588 	new_node->checked = 1;
589 	new_node->root = btrfs_grab_root(dest);
590 	ASSERT(new_node->root);
591 
592 	if (!node->lowest) {
593 		list_for_each_entry(edge, &node->lower, list[UPPER]) {
594 			new_edge = btrfs_backref_alloc_edge(cache);
595 			if (!new_edge)
596 				goto fail;
597 
598 			btrfs_backref_link_edge(new_edge, edge->node[LOWER],
599 						new_node, LINK_UPPER);
600 		}
601 	} else {
602 		list_add_tail(&new_node->lower, &cache->leaves);
603 	}
604 
605 	rb_node = rb_simple_insert(&cache->rb_root, new_node->bytenr,
606 				   &new_node->rb_node);
607 	if (rb_node)
608 		btrfs_backref_panic(trans->fs_info, new_node->bytenr, -EEXIST);
609 
610 	if (!new_node->lowest) {
611 		list_for_each_entry(new_edge, &new_node->lower, list[UPPER]) {
612 			list_add_tail(&new_edge->list[LOWER],
613 				      &new_edge->node[LOWER]->upper);
614 		}
615 	}
616 	return 0;
617 fail:
618 	while (!list_empty(&new_node->lower)) {
619 		new_edge = list_entry(new_node->lower.next,
620 				      struct btrfs_backref_edge, list[UPPER]);
621 		list_del(&new_edge->list[UPPER]);
622 		btrfs_backref_free_edge(cache, new_edge);
623 	}
624 	btrfs_backref_free_node(cache, new_node);
625 	return -ENOMEM;
626 }
627 
628 /*
629  * helper to add 'address of tree root -> reloc tree' mapping
630  */
631 static int __add_reloc_root(struct btrfs_root *root)
632 {
633 	struct btrfs_fs_info *fs_info = root->fs_info;
634 	struct rb_node *rb_node;
635 	struct mapping_node *node;
636 	struct reloc_control *rc = fs_info->reloc_ctl;
637 
638 	node = kmalloc(sizeof(*node), GFP_NOFS);
639 	if (!node)
640 		return -ENOMEM;
641 
642 	node->bytenr = root->commit_root->start;
643 	node->data = root;
644 
645 	spin_lock(&rc->reloc_root_tree.lock);
646 	rb_node = rb_simple_insert(&rc->reloc_root_tree.rb_root,
647 				   node->bytenr, &node->rb_node);
648 	spin_unlock(&rc->reloc_root_tree.lock);
649 	if (rb_node) {
650 		btrfs_err(fs_info,
651 			    "Duplicate root found for start=%llu while inserting into relocation tree",
652 			    node->bytenr);
653 		return -EEXIST;
654 	}
655 
656 	list_add_tail(&root->root_list, &rc->reloc_roots);
657 	return 0;
658 }
659 
660 /*
661  * helper to delete the 'address of tree root -> reloc tree'
662  * mapping
663  */
664 static void __del_reloc_root(struct btrfs_root *root)
665 {
666 	struct btrfs_fs_info *fs_info = root->fs_info;
667 	struct rb_node *rb_node;
668 	struct mapping_node *node = NULL;
669 	struct reloc_control *rc = fs_info->reloc_ctl;
670 	bool put_ref = false;
671 
672 	if (rc && root->node) {
673 		spin_lock(&rc->reloc_root_tree.lock);
674 		rb_node = rb_simple_search(&rc->reloc_root_tree.rb_root,
675 					   root->commit_root->start);
676 		if (rb_node) {
677 			node = rb_entry(rb_node, struct mapping_node, rb_node);
678 			rb_erase(&node->rb_node, &rc->reloc_root_tree.rb_root);
679 			RB_CLEAR_NODE(&node->rb_node);
680 		}
681 		spin_unlock(&rc->reloc_root_tree.lock);
682 		ASSERT(!node || (struct btrfs_root *)node->data == root);
683 	}
684 
685 	/*
686 	 * We only put the reloc root here if it's on the list.  There's a lot
687 	 * of places where the pattern is to splice the rc->reloc_roots, process
688 	 * the reloc roots, and then add the reloc root back onto
689 	 * rc->reloc_roots.  If we call __del_reloc_root while it's off of the
690 	 * list we don't want the reference being dropped, because the guy
691 	 * messing with the list is in charge of the reference.
692 	 */
693 	spin_lock(&fs_info->trans_lock);
694 	if (!list_empty(&root->root_list)) {
695 		put_ref = true;
696 		list_del_init(&root->root_list);
697 	}
698 	spin_unlock(&fs_info->trans_lock);
699 	if (put_ref)
700 		btrfs_put_root(root);
701 	kfree(node);
702 }
703 
704 /*
705  * helper to update the 'address of tree root -> reloc tree'
706  * mapping
707  */
708 static int __update_reloc_root(struct btrfs_root *root)
709 {
710 	struct btrfs_fs_info *fs_info = root->fs_info;
711 	struct rb_node *rb_node;
712 	struct mapping_node *node = NULL;
713 	struct reloc_control *rc = fs_info->reloc_ctl;
714 
715 	spin_lock(&rc->reloc_root_tree.lock);
716 	rb_node = rb_simple_search(&rc->reloc_root_tree.rb_root,
717 				   root->commit_root->start);
718 	if (rb_node) {
719 		node = rb_entry(rb_node, struct mapping_node, rb_node);
720 		rb_erase(&node->rb_node, &rc->reloc_root_tree.rb_root);
721 	}
722 	spin_unlock(&rc->reloc_root_tree.lock);
723 
724 	if (!node)
725 		return 0;
726 	BUG_ON((struct btrfs_root *)node->data != root);
727 
728 	spin_lock(&rc->reloc_root_tree.lock);
729 	node->bytenr = root->node->start;
730 	rb_node = rb_simple_insert(&rc->reloc_root_tree.rb_root,
731 				   node->bytenr, &node->rb_node);
732 	spin_unlock(&rc->reloc_root_tree.lock);
733 	if (rb_node)
734 		btrfs_backref_panic(fs_info, node->bytenr, -EEXIST);
735 	return 0;
736 }
737 
738 static struct btrfs_root *create_reloc_root(struct btrfs_trans_handle *trans,
739 					struct btrfs_root *root, u64 objectid)
740 {
741 	struct btrfs_fs_info *fs_info = root->fs_info;
742 	struct btrfs_root *reloc_root;
743 	struct extent_buffer *eb;
744 	struct btrfs_root_item *root_item;
745 	struct btrfs_key root_key;
746 	int ret = 0;
747 	bool must_abort = false;
748 
749 	root_item = kmalloc(sizeof(*root_item), GFP_NOFS);
750 	if (!root_item)
751 		return ERR_PTR(-ENOMEM);
752 
753 	root_key.objectid = BTRFS_TREE_RELOC_OBJECTID;
754 	root_key.type = BTRFS_ROOT_ITEM_KEY;
755 	root_key.offset = objectid;
756 
757 	if (root->root_key.objectid == objectid) {
758 		u64 commit_root_gen;
759 
760 		/* called by btrfs_init_reloc_root */
761 		ret = btrfs_copy_root(trans, root, root->commit_root, &eb,
762 				      BTRFS_TREE_RELOC_OBJECTID);
763 		if (ret)
764 			goto fail;
765 
766 		/*
767 		 * Set the last_snapshot field to the generation of the commit
768 		 * root - like this ctree.c:btrfs_block_can_be_shared() behaves
769 		 * correctly (returns true) when the relocation root is created
770 		 * either inside the critical section of a transaction commit
771 		 * (through transaction.c:qgroup_account_snapshot()) and when
772 		 * it's created before the transaction commit is started.
773 		 */
774 		commit_root_gen = btrfs_header_generation(root->commit_root);
775 		btrfs_set_root_last_snapshot(&root->root_item, commit_root_gen);
776 	} else {
777 		/*
778 		 * called by btrfs_reloc_post_snapshot_hook.
779 		 * the source tree is a reloc tree, all tree blocks
780 		 * modified after it was created have RELOC flag
781 		 * set in their headers. so it's OK to not update
782 		 * the 'last_snapshot'.
783 		 */
784 		ret = btrfs_copy_root(trans, root, root->node, &eb,
785 				      BTRFS_TREE_RELOC_OBJECTID);
786 		if (ret)
787 			goto fail;
788 	}
789 
790 	/*
791 	 * We have changed references at this point, we must abort the
792 	 * transaction if anything fails.
793 	 */
794 	must_abort = true;
795 
796 	memcpy(root_item, &root->root_item, sizeof(*root_item));
797 	btrfs_set_root_bytenr(root_item, eb->start);
798 	btrfs_set_root_level(root_item, btrfs_header_level(eb));
799 	btrfs_set_root_generation(root_item, trans->transid);
800 
801 	if (root->root_key.objectid == objectid) {
802 		btrfs_set_root_refs(root_item, 0);
803 		memset(&root_item->drop_progress, 0,
804 		       sizeof(struct btrfs_disk_key));
805 		btrfs_set_root_drop_level(root_item, 0);
806 	}
807 
808 	btrfs_tree_unlock(eb);
809 	free_extent_buffer(eb);
810 
811 	ret = btrfs_insert_root(trans, fs_info->tree_root,
812 				&root_key, root_item);
813 	if (ret)
814 		goto fail;
815 
816 	kfree(root_item);
817 
818 	reloc_root = btrfs_read_tree_root(fs_info->tree_root, &root_key);
819 	if (IS_ERR(reloc_root)) {
820 		ret = PTR_ERR(reloc_root);
821 		goto abort;
822 	}
823 	set_bit(BTRFS_ROOT_SHAREABLE, &reloc_root->state);
824 	reloc_root->last_trans = trans->transid;
825 	return reloc_root;
826 fail:
827 	kfree(root_item);
828 abort:
829 	if (must_abort)
830 		btrfs_abort_transaction(trans, ret);
831 	return ERR_PTR(ret);
832 }
833 
834 /*
835  * create reloc tree for a given fs tree. reloc tree is just a
836  * snapshot of the fs tree with special root objectid.
837  *
838  * The reloc_root comes out of here with two references, one for
839  * root->reloc_root, and another for being on the rc->reloc_roots list.
840  */
841 int btrfs_init_reloc_root(struct btrfs_trans_handle *trans,
842 			  struct btrfs_root *root)
843 {
844 	struct btrfs_fs_info *fs_info = root->fs_info;
845 	struct btrfs_root *reloc_root;
846 	struct reloc_control *rc = fs_info->reloc_ctl;
847 	struct btrfs_block_rsv *rsv;
848 	int clear_rsv = 0;
849 	int ret;
850 
851 	if (!rc)
852 		return 0;
853 
854 	/*
855 	 * The subvolume has reloc tree but the swap is finished, no need to
856 	 * create/update the dead reloc tree
857 	 */
858 	if (reloc_root_is_dead(root))
859 		return 0;
860 
861 	/*
862 	 * This is subtle but important.  We do not do
863 	 * record_root_in_transaction for reloc roots, instead we record their
864 	 * corresponding fs root, and then here we update the last trans for the
865 	 * reloc root.  This means that we have to do this for the entire life
866 	 * of the reloc root, regardless of which stage of the relocation we are
867 	 * in.
868 	 */
869 	if (root->reloc_root) {
870 		reloc_root = root->reloc_root;
871 		reloc_root->last_trans = trans->transid;
872 		return 0;
873 	}
874 
875 	/*
876 	 * We are merging reloc roots, we do not need new reloc trees.  Also
877 	 * reloc trees never need their own reloc tree.
878 	 */
879 	if (!rc->create_reloc_tree ||
880 	    root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
881 		return 0;
882 
883 	if (!trans->reloc_reserved) {
884 		rsv = trans->block_rsv;
885 		trans->block_rsv = rc->block_rsv;
886 		clear_rsv = 1;
887 	}
888 	reloc_root = create_reloc_root(trans, root, root->root_key.objectid);
889 	if (clear_rsv)
890 		trans->block_rsv = rsv;
891 	if (IS_ERR(reloc_root))
892 		return PTR_ERR(reloc_root);
893 
894 	ret = __add_reloc_root(reloc_root);
895 	ASSERT(ret != -EEXIST);
896 	if (ret) {
897 		/* Pairs with create_reloc_root */
898 		btrfs_put_root(reloc_root);
899 		return ret;
900 	}
901 	root->reloc_root = btrfs_grab_root(reloc_root);
902 	return 0;
903 }
904 
905 /*
906  * update root item of reloc tree
907  */
908 int btrfs_update_reloc_root(struct btrfs_trans_handle *trans,
909 			    struct btrfs_root *root)
910 {
911 	struct btrfs_fs_info *fs_info = root->fs_info;
912 	struct btrfs_root *reloc_root;
913 	struct btrfs_root_item *root_item;
914 	int ret;
915 
916 	if (!have_reloc_root(root))
917 		return 0;
918 
919 	reloc_root = root->reloc_root;
920 	root_item = &reloc_root->root_item;
921 
922 	/*
923 	 * We are probably ok here, but __del_reloc_root() will drop its ref of
924 	 * the root.  We have the ref for root->reloc_root, but just in case
925 	 * hold it while we update the reloc root.
926 	 */
927 	btrfs_grab_root(reloc_root);
928 
929 	/* root->reloc_root will stay until current relocation finished */
930 	if (fs_info->reloc_ctl->merge_reloc_tree &&
931 	    btrfs_root_refs(root_item) == 0) {
932 		set_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state);
933 		/*
934 		 * Mark the tree as dead before we change reloc_root so
935 		 * have_reloc_root will not touch it from now on.
936 		 */
937 		smp_wmb();
938 		__del_reloc_root(reloc_root);
939 	}
940 
941 	if (reloc_root->commit_root != reloc_root->node) {
942 		__update_reloc_root(reloc_root);
943 		btrfs_set_root_node(root_item, reloc_root->node);
944 		free_extent_buffer(reloc_root->commit_root);
945 		reloc_root->commit_root = btrfs_root_node(reloc_root);
946 	}
947 
948 	ret = btrfs_update_root(trans, fs_info->tree_root,
949 				&reloc_root->root_key, root_item);
950 	btrfs_put_root(reloc_root);
951 	return ret;
952 }
953 
954 /*
955  * helper to find first cached inode with inode number >= objectid
956  * in a subvolume
957  */
958 static struct inode *find_next_inode(struct btrfs_root *root, u64 objectid)
959 {
960 	struct rb_node *node;
961 	struct rb_node *prev;
962 	struct btrfs_inode *entry;
963 	struct inode *inode;
964 
965 	spin_lock(&root->inode_lock);
966 again:
967 	node = root->inode_tree.rb_node;
968 	prev = NULL;
969 	while (node) {
970 		prev = node;
971 		entry = rb_entry(node, struct btrfs_inode, rb_node);
972 
973 		if (objectid < btrfs_ino(entry))
974 			node = node->rb_left;
975 		else if (objectid > btrfs_ino(entry))
976 			node = node->rb_right;
977 		else
978 			break;
979 	}
980 	if (!node) {
981 		while (prev) {
982 			entry = rb_entry(prev, struct btrfs_inode, rb_node);
983 			if (objectid <= btrfs_ino(entry)) {
984 				node = prev;
985 				break;
986 			}
987 			prev = rb_next(prev);
988 		}
989 	}
990 	while (node) {
991 		entry = rb_entry(node, struct btrfs_inode, rb_node);
992 		inode = igrab(&entry->vfs_inode);
993 		if (inode) {
994 			spin_unlock(&root->inode_lock);
995 			return inode;
996 		}
997 
998 		objectid = btrfs_ino(entry) + 1;
999 		if (cond_resched_lock(&root->inode_lock))
1000 			goto again;
1001 
1002 		node = rb_next(node);
1003 	}
1004 	spin_unlock(&root->inode_lock);
1005 	return NULL;
1006 }
1007 
1008 /*
1009  * get new location of data
1010  */
1011 static int get_new_location(struct inode *reloc_inode, u64 *new_bytenr,
1012 			    u64 bytenr, u64 num_bytes)
1013 {
1014 	struct btrfs_root *root = BTRFS_I(reloc_inode)->root;
1015 	struct btrfs_path *path;
1016 	struct btrfs_file_extent_item *fi;
1017 	struct extent_buffer *leaf;
1018 	int ret;
1019 
1020 	path = btrfs_alloc_path();
1021 	if (!path)
1022 		return -ENOMEM;
1023 
1024 	bytenr -= BTRFS_I(reloc_inode)->index_cnt;
1025 	ret = btrfs_lookup_file_extent(NULL, root, path,
1026 			btrfs_ino(BTRFS_I(reloc_inode)), bytenr, 0);
1027 	if (ret < 0)
1028 		goto out;
1029 	if (ret > 0) {
1030 		ret = -ENOENT;
1031 		goto out;
1032 	}
1033 
1034 	leaf = path->nodes[0];
1035 	fi = btrfs_item_ptr(leaf, path->slots[0],
1036 			    struct btrfs_file_extent_item);
1037 
1038 	BUG_ON(btrfs_file_extent_offset(leaf, fi) ||
1039 	       btrfs_file_extent_compression(leaf, fi) ||
1040 	       btrfs_file_extent_encryption(leaf, fi) ||
1041 	       btrfs_file_extent_other_encoding(leaf, fi));
1042 
1043 	if (num_bytes != btrfs_file_extent_disk_num_bytes(leaf, fi)) {
1044 		ret = -EINVAL;
1045 		goto out;
1046 	}
1047 
1048 	*new_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
1049 	ret = 0;
1050 out:
1051 	btrfs_free_path(path);
1052 	return ret;
1053 }
1054 
1055 /*
1056  * update file extent items in the tree leaf to point to
1057  * the new locations.
1058  */
1059 static noinline_for_stack
1060 int replace_file_extents(struct btrfs_trans_handle *trans,
1061 			 struct reloc_control *rc,
1062 			 struct btrfs_root *root,
1063 			 struct extent_buffer *leaf)
1064 {
1065 	struct btrfs_fs_info *fs_info = root->fs_info;
1066 	struct btrfs_key key;
1067 	struct btrfs_file_extent_item *fi;
1068 	struct inode *inode = NULL;
1069 	u64 parent;
1070 	u64 bytenr;
1071 	u64 new_bytenr = 0;
1072 	u64 num_bytes;
1073 	u64 end;
1074 	u32 nritems;
1075 	u32 i;
1076 	int ret = 0;
1077 	int first = 1;
1078 	int dirty = 0;
1079 
1080 	if (rc->stage != UPDATE_DATA_PTRS)
1081 		return 0;
1082 
1083 	/* reloc trees always use full backref */
1084 	if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID)
1085 		parent = leaf->start;
1086 	else
1087 		parent = 0;
1088 
1089 	nritems = btrfs_header_nritems(leaf);
1090 	for (i = 0; i < nritems; i++) {
1091 		struct btrfs_ref ref = { 0 };
1092 
1093 		cond_resched();
1094 		btrfs_item_key_to_cpu(leaf, &key, i);
1095 		if (key.type != BTRFS_EXTENT_DATA_KEY)
1096 			continue;
1097 		fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
1098 		if (btrfs_file_extent_type(leaf, fi) ==
1099 		    BTRFS_FILE_EXTENT_INLINE)
1100 			continue;
1101 		bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
1102 		num_bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
1103 		if (bytenr == 0)
1104 			continue;
1105 		if (!in_range(bytenr, rc->block_group->start,
1106 			      rc->block_group->length))
1107 			continue;
1108 
1109 		/*
1110 		 * if we are modifying block in fs tree, wait for read_folio
1111 		 * to complete and drop the extent cache
1112 		 */
1113 		if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
1114 			if (first) {
1115 				inode = find_next_inode(root, key.objectid);
1116 				first = 0;
1117 			} else if (inode && btrfs_ino(BTRFS_I(inode)) < key.objectid) {
1118 				btrfs_add_delayed_iput(BTRFS_I(inode));
1119 				inode = find_next_inode(root, key.objectid);
1120 			}
1121 			if (inode && btrfs_ino(BTRFS_I(inode)) == key.objectid) {
1122 				struct extent_state *cached_state = NULL;
1123 
1124 				end = key.offset +
1125 				      btrfs_file_extent_num_bytes(leaf, fi);
1126 				WARN_ON(!IS_ALIGNED(key.offset,
1127 						    fs_info->sectorsize));
1128 				WARN_ON(!IS_ALIGNED(end, fs_info->sectorsize));
1129 				end--;
1130 				ret = try_lock_extent(&BTRFS_I(inode)->io_tree,
1131 						      key.offset, end,
1132 						      &cached_state);
1133 				if (!ret)
1134 					continue;
1135 
1136 				btrfs_drop_extent_map_range(BTRFS_I(inode),
1137 							    key.offset, end, true);
1138 				unlock_extent(&BTRFS_I(inode)->io_tree,
1139 					      key.offset, end, &cached_state);
1140 			}
1141 		}
1142 
1143 		ret = get_new_location(rc->data_inode, &new_bytenr,
1144 				       bytenr, num_bytes);
1145 		if (ret) {
1146 			/*
1147 			 * Don't have to abort since we've not changed anything
1148 			 * in the file extent yet.
1149 			 */
1150 			break;
1151 		}
1152 
1153 		btrfs_set_file_extent_disk_bytenr(leaf, fi, new_bytenr);
1154 		dirty = 1;
1155 
1156 		key.offset -= btrfs_file_extent_offset(leaf, fi);
1157 		btrfs_init_generic_ref(&ref, BTRFS_ADD_DELAYED_REF, new_bytenr,
1158 				       num_bytes, parent, root->root_key.objectid);
1159 		btrfs_init_data_ref(&ref, btrfs_header_owner(leaf),
1160 				    key.objectid, key.offset,
1161 				    root->root_key.objectid, false);
1162 		ret = btrfs_inc_extent_ref(trans, &ref);
1163 		if (ret) {
1164 			btrfs_abort_transaction(trans, ret);
1165 			break;
1166 		}
1167 
1168 		btrfs_init_generic_ref(&ref, BTRFS_DROP_DELAYED_REF, bytenr,
1169 				       num_bytes, parent, root->root_key.objectid);
1170 		btrfs_init_data_ref(&ref, btrfs_header_owner(leaf),
1171 				    key.objectid, key.offset,
1172 				    root->root_key.objectid, false);
1173 		ret = btrfs_free_extent(trans, &ref);
1174 		if (ret) {
1175 			btrfs_abort_transaction(trans, ret);
1176 			break;
1177 		}
1178 	}
1179 	if (dirty)
1180 		btrfs_mark_buffer_dirty(trans, leaf);
1181 	if (inode)
1182 		btrfs_add_delayed_iput(BTRFS_I(inode));
1183 	return ret;
1184 }
1185 
1186 static noinline_for_stack int memcmp_node_keys(const struct extent_buffer *eb,
1187 					       int slot, const struct btrfs_path *path,
1188 					       int level)
1189 {
1190 	struct btrfs_disk_key key1;
1191 	struct btrfs_disk_key key2;
1192 	btrfs_node_key(eb, &key1, slot);
1193 	btrfs_node_key(path->nodes[level], &key2, path->slots[level]);
1194 	return memcmp(&key1, &key2, sizeof(key1));
1195 }
1196 
1197 /*
1198  * try to replace tree blocks in fs tree with the new blocks
1199  * in reloc tree. tree blocks haven't been modified since the
1200  * reloc tree was create can be replaced.
1201  *
1202  * if a block was replaced, level of the block + 1 is returned.
1203  * if no block got replaced, 0 is returned. if there are other
1204  * errors, a negative error number is returned.
1205  */
1206 static noinline_for_stack
1207 int replace_path(struct btrfs_trans_handle *trans, struct reloc_control *rc,
1208 		 struct btrfs_root *dest, struct btrfs_root *src,
1209 		 struct btrfs_path *path, struct btrfs_key *next_key,
1210 		 int lowest_level, int max_level)
1211 {
1212 	struct btrfs_fs_info *fs_info = dest->fs_info;
1213 	struct extent_buffer *eb;
1214 	struct extent_buffer *parent;
1215 	struct btrfs_ref ref = { 0 };
1216 	struct btrfs_key key;
1217 	u64 old_bytenr;
1218 	u64 new_bytenr;
1219 	u64 old_ptr_gen;
1220 	u64 new_ptr_gen;
1221 	u64 last_snapshot;
1222 	u32 blocksize;
1223 	int cow = 0;
1224 	int level;
1225 	int ret;
1226 	int slot;
1227 
1228 	ASSERT(src->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID);
1229 	ASSERT(dest->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID);
1230 
1231 	last_snapshot = btrfs_root_last_snapshot(&src->root_item);
1232 again:
1233 	slot = path->slots[lowest_level];
1234 	btrfs_node_key_to_cpu(path->nodes[lowest_level], &key, slot);
1235 
1236 	eb = btrfs_lock_root_node(dest);
1237 	level = btrfs_header_level(eb);
1238 
1239 	if (level < lowest_level) {
1240 		btrfs_tree_unlock(eb);
1241 		free_extent_buffer(eb);
1242 		return 0;
1243 	}
1244 
1245 	if (cow) {
1246 		ret = btrfs_cow_block(trans, dest, eb, NULL, 0, &eb,
1247 				      BTRFS_NESTING_COW);
1248 		if (ret) {
1249 			btrfs_tree_unlock(eb);
1250 			free_extent_buffer(eb);
1251 			return ret;
1252 		}
1253 	}
1254 
1255 	if (next_key) {
1256 		next_key->objectid = (u64)-1;
1257 		next_key->type = (u8)-1;
1258 		next_key->offset = (u64)-1;
1259 	}
1260 
1261 	parent = eb;
1262 	while (1) {
1263 		level = btrfs_header_level(parent);
1264 		ASSERT(level >= lowest_level);
1265 
1266 		ret = btrfs_bin_search(parent, 0, &key, &slot);
1267 		if (ret < 0)
1268 			break;
1269 		if (ret && slot > 0)
1270 			slot--;
1271 
1272 		if (next_key && slot + 1 < btrfs_header_nritems(parent))
1273 			btrfs_node_key_to_cpu(parent, next_key, slot + 1);
1274 
1275 		old_bytenr = btrfs_node_blockptr(parent, slot);
1276 		blocksize = fs_info->nodesize;
1277 		old_ptr_gen = btrfs_node_ptr_generation(parent, slot);
1278 
1279 		if (level <= max_level) {
1280 			eb = path->nodes[level];
1281 			new_bytenr = btrfs_node_blockptr(eb,
1282 							path->slots[level]);
1283 			new_ptr_gen = btrfs_node_ptr_generation(eb,
1284 							path->slots[level]);
1285 		} else {
1286 			new_bytenr = 0;
1287 			new_ptr_gen = 0;
1288 		}
1289 
1290 		if (WARN_ON(new_bytenr > 0 && new_bytenr == old_bytenr)) {
1291 			ret = level;
1292 			break;
1293 		}
1294 
1295 		if (new_bytenr == 0 || old_ptr_gen > last_snapshot ||
1296 		    memcmp_node_keys(parent, slot, path, level)) {
1297 			if (level <= lowest_level) {
1298 				ret = 0;
1299 				break;
1300 			}
1301 
1302 			eb = btrfs_read_node_slot(parent, slot);
1303 			if (IS_ERR(eb)) {
1304 				ret = PTR_ERR(eb);
1305 				break;
1306 			}
1307 			btrfs_tree_lock(eb);
1308 			if (cow) {
1309 				ret = btrfs_cow_block(trans, dest, eb, parent,
1310 						      slot, &eb,
1311 						      BTRFS_NESTING_COW);
1312 				if (ret) {
1313 					btrfs_tree_unlock(eb);
1314 					free_extent_buffer(eb);
1315 					break;
1316 				}
1317 			}
1318 
1319 			btrfs_tree_unlock(parent);
1320 			free_extent_buffer(parent);
1321 
1322 			parent = eb;
1323 			continue;
1324 		}
1325 
1326 		if (!cow) {
1327 			btrfs_tree_unlock(parent);
1328 			free_extent_buffer(parent);
1329 			cow = 1;
1330 			goto again;
1331 		}
1332 
1333 		btrfs_node_key_to_cpu(path->nodes[level], &key,
1334 				      path->slots[level]);
1335 		btrfs_release_path(path);
1336 
1337 		path->lowest_level = level;
1338 		set_bit(BTRFS_ROOT_RESET_LOCKDEP_CLASS, &src->state);
1339 		ret = btrfs_search_slot(trans, src, &key, path, 0, 1);
1340 		clear_bit(BTRFS_ROOT_RESET_LOCKDEP_CLASS, &src->state);
1341 		path->lowest_level = 0;
1342 		if (ret) {
1343 			if (ret > 0)
1344 				ret = -ENOENT;
1345 			break;
1346 		}
1347 
1348 		/*
1349 		 * Info qgroup to trace both subtrees.
1350 		 *
1351 		 * We must trace both trees.
1352 		 * 1) Tree reloc subtree
1353 		 *    If not traced, we will leak data numbers
1354 		 * 2) Fs subtree
1355 		 *    If not traced, we will double count old data
1356 		 *
1357 		 * We don't scan the subtree right now, but only record
1358 		 * the swapped tree blocks.
1359 		 * The real subtree rescan is delayed until we have new
1360 		 * CoW on the subtree root node before transaction commit.
1361 		 */
1362 		ret = btrfs_qgroup_add_swapped_blocks(trans, dest,
1363 				rc->block_group, parent, slot,
1364 				path->nodes[level], path->slots[level],
1365 				last_snapshot);
1366 		if (ret < 0)
1367 			break;
1368 		/*
1369 		 * swap blocks in fs tree and reloc tree.
1370 		 */
1371 		btrfs_set_node_blockptr(parent, slot, new_bytenr);
1372 		btrfs_set_node_ptr_generation(parent, slot, new_ptr_gen);
1373 		btrfs_mark_buffer_dirty(trans, parent);
1374 
1375 		btrfs_set_node_blockptr(path->nodes[level],
1376 					path->slots[level], old_bytenr);
1377 		btrfs_set_node_ptr_generation(path->nodes[level],
1378 					      path->slots[level], old_ptr_gen);
1379 		btrfs_mark_buffer_dirty(trans, path->nodes[level]);
1380 
1381 		btrfs_init_generic_ref(&ref, BTRFS_ADD_DELAYED_REF, old_bytenr,
1382 				       blocksize, path->nodes[level]->start,
1383 				       src->root_key.objectid);
1384 		btrfs_init_tree_ref(&ref, level - 1, src->root_key.objectid,
1385 				    0, true);
1386 		ret = btrfs_inc_extent_ref(trans, &ref);
1387 		if (ret) {
1388 			btrfs_abort_transaction(trans, ret);
1389 			break;
1390 		}
1391 		btrfs_init_generic_ref(&ref, BTRFS_ADD_DELAYED_REF, new_bytenr,
1392 				       blocksize, 0, dest->root_key.objectid);
1393 		btrfs_init_tree_ref(&ref, level - 1, dest->root_key.objectid, 0,
1394 				    true);
1395 		ret = btrfs_inc_extent_ref(trans, &ref);
1396 		if (ret) {
1397 			btrfs_abort_transaction(trans, ret);
1398 			break;
1399 		}
1400 
1401 		/* We don't know the real owning_root, use 0. */
1402 		btrfs_init_generic_ref(&ref, BTRFS_DROP_DELAYED_REF, new_bytenr,
1403 				       blocksize, path->nodes[level]->start, 0);
1404 		btrfs_init_tree_ref(&ref, level - 1, src->root_key.objectid,
1405 				    0, true);
1406 		ret = btrfs_free_extent(trans, &ref);
1407 		if (ret) {
1408 			btrfs_abort_transaction(trans, ret);
1409 			break;
1410 		}
1411 
1412 		/* We don't know the real owning_root, use 0. */
1413 		btrfs_init_generic_ref(&ref, BTRFS_DROP_DELAYED_REF, old_bytenr,
1414 				       blocksize, 0, 0);
1415 		btrfs_init_tree_ref(&ref, level - 1, dest->root_key.objectid,
1416 				    0, true);
1417 		ret = btrfs_free_extent(trans, &ref);
1418 		if (ret) {
1419 			btrfs_abort_transaction(trans, ret);
1420 			break;
1421 		}
1422 
1423 		btrfs_unlock_up_safe(path, 0);
1424 
1425 		ret = level;
1426 		break;
1427 	}
1428 	btrfs_tree_unlock(parent);
1429 	free_extent_buffer(parent);
1430 	return ret;
1431 }
1432 
1433 /*
1434  * helper to find next relocated block in reloc tree
1435  */
1436 static noinline_for_stack
1437 int walk_up_reloc_tree(struct btrfs_root *root, struct btrfs_path *path,
1438 		       int *level)
1439 {
1440 	struct extent_buffer *eb;
1441 	int i;
1442 	u64 last_snapshot;
1443 	u32 nritems;
1444 
1445 	last_snapshot = btrfs_root_last_snapshot(&root->root_item);
1446 
1447 	for (i = 0; i < *level; i++) {
1448 		free_extent_buffer(path->nodes[i]);
1449 		path->nodes[i] = NULL;
1450 	}
1451 
1452 	for (i = *level; i < BTRFS_MAX_LEVEL && path->nodes[i]; i++) {
1453 		eb = path->nodes[i];
1454 		nritems = btrfs_header_nritems(eb);
1455 		while (path->slots[i] + 1 < nritems) {
1456 			path->slots[i]++;
1457 			if (btrfs_node_ptr_generation(eb, path->slots[i]) <=
1458 			    last_snapshot)
1459 				continue;
1460 
1461 			*level = i;
1462 			return 0;
1463 		}
1464 		free_extent_buffer(path->nodes[i]);
1465 		path->nodes[i] = NULL;
1466 	}
1467 	return 1;
1468 }
1469 
1470 /*
1471  * walk down reloc tree to find relocated block of lowest level
1472  */
1473 static noinline_for_stack
1474 int walk_down_reloc_tree(struct btrfs_root *root, struct btrfs_path *path,
1475 			 int *level)
1476 {
1477 	struct extent_buffer *eb = NULL;
1478 	int i;
1479 	u64 ptr_gen = 0;
1480 	u64 last_snapshot;
1481 	u32 nritems;
1482 
1483 	last_snapshot = btrfs_root_last_snapshot(&root->root_item);
1484 
1485 	for (i = *level; i > 0; i--) {
1486 		eb = path->nodes[i];
1487 		nritems = btrfs_header_nritems(eb);
1488 		while (path->slots[i] < nritems) {
1489 			ptr_gen = btrfs_node_ptr_generation(eb, path->slots[i]);
1490 			if (ptr_gen > last_snapshot)
1491 				break;
1492 			path->slots[i]++;
1493 		}
1494 		if (path->slots[i] >= nritems) {
1495 			if (i == *level)
1496 				break;
1497 			*level = i + 1;
1498 			return 0;
1499 		}
1500 		if (i == 1) {
1501 			*level = i;
1502 			return 0;
1503 		}
1504 
1505 		eb = btrfs_read_node_slot(eb, path->slots[i]);
1506 		if (IS_ERR(eb))
1507 			return PTR_ERR(eb);
1508 		BUG_ON(btrfs_header_level(eb) != i - 1);
1509 		path->nodes[i - 1] = eb;
1510 		path->slots[i - 1] = 0;
1511 	}
1512 	return 1;
1513 }
1514 
1515 /*
1516  * invalidate extent cache for file extents whose key in range of
1517  * [min_key, max_key)
1518  */
1519 static int invalidate_extent_cache(struct btrfs_root *root,
1520 				   const struct btrfs_key *min_key,
1521 				   const struct btrfs_key *max_key)
1522 {
1523 	struct btrfs_fs_info *fs_info = root->fs_info;
1524 	struct inode *inode = NULL;
1525 	u64 objectid;
1526 	u64 start, end;
1527 	u64 ino;
1528 
1529 	objectid = min_key->objectid;
1530 	while (1) {
1531 		struct extent_state *cached_state = NULL;
1532 
1533 		cond_resched();
1534 		iput(inode);
1535 
1536 		if (objectid > max_key->objectid)
1537 			break;
1538 
1539 		inode = find_next_inode(root, objectid);
1540 		if (!inode)
1541 			break;
1542 		ino = btrfs_ino(BTRFS_I(inode));
1543 
1544 		if (ino > max_key->objectid) {
1545 			iput(inode);
1546 			break;
1547 		}
1548 
1549 		objectid = ino + 1;
1550 		if (!S_ISREG(inode->i_mode))
1551 			continue;
1552 
1553 		if (unlikely(min_key->objectid == ino)) {
1554 			if (min_key->type > BTRFS_EXTENT_DATA_KEY)
1555 				continue;
1556 			if (min_key->type < BTRFS_EXTENT_DATA_KEY)
1557 				start = 0;
1558 			else {
1559 				start = min_key->offset;
1560 				WARN_ON(!IS_ALIGNED(start, fs_info->sectorsize));
1561 			}
1562 		} else {
1563 			start = 0;
1564 		}
1565 
1566 		if (unlikely(max_key->objectid == ino)) {
1567 			if (max_key->type < BTRFS_EXTENT_DATA_KEY)
1568 				continue;
1569 			if (max_key->type > BTRFS_EXTENT_DATA_KEY) {
1570 				end = (u64)-1;
1571 			} else {
1572 				if (max_key->offset == 0)
1573 					continue;
1574 				end = max_key->offset;
1575 				WARN_ON(!IS_ALIGNED(end, fs_info->sectorsize));
1576 				end--;
1577 			}
1578 		} else {
1579 			end = (u64)-1;
1580 		}
1581 
1582 		/* the lock_extent waits for read_folio to complete */
1583 		lock_extent(&BTRFS_I(inode)->io_tree, start, end, &cached_state);
1584 		btrfs_drop_extent_map_range(BTRFS_I(inode), start, end, true);
1585 		unlock_extent(&BTRFS_I(inode)->io_tree, start, end, &cached_state);
1586 	}
1587 	return 0;
1588 }
1589 
1590 static int find_next_key(struct btrfs_path *path, int level,
1591 			 struct btrfs_key *key)
1592 
1593 {
1594 	while (level < BTRFS_MAX_LEVEL) {
1595 		if (!path->nodes[level])
1596 			break;
1597 		if (path->slots[level] + 1 <
1598 		    btrfs_header_nritems(path->nodes[level])) {
1599 			btrfs_node_key_to_cpu(path->nodes[level], key,
1600 					      path->slots[level] + 1);
1601 			return 0;
1602 		}
1603 		level++;
1604 	}
1605 	return 1;
1606 }
1607 
1608 /*
1609  * Insert current subvolume into reloc_control::dirty_subvol_roots
1610  */
1611 static int insert_dirty_subvol(struct btrfs_trans_handle *trans,
1612 			       struct reloc_control *rc,
1613 			       struct btrfs_root *root)
1614 {
1615 	struct btrfs_root *reloc_root = root->reloc_root;
1616 	struct btrfs_root_item *reloc_root_item;
1617 	int ret;
1618 
1619 	/* @root must be a subvolume tree root with a valid reloc tree */
1620 	ASSERT(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID);
1621 	ASSERT(reloc_root);
1622 
1623 	reloc_root_item = &reloc_root->root_item;
1624 	memset(&reloc_root_item->drop_progress, 0,
1625 		sizeof(reloc_root_item->drop_progress));
1626 	btrfs_set_root_drop_level(reloc_root_item, 0);
1627 	btrfs_set_root_refs(reloc_root_item, 0);
1628 	ret = btrfs_update_reloc_root(trans, root);
1629 	if (ret)
1630 		return ret;
1631 
1632 	if (list_empty(&root->reloc_dirty_list)) {
1633 		btrfs_grab_root(root);
1634 		list_add_tail(&root->reloc_dirty_list, &rc->dirty_subvol_roots);
1635 	}
1636 
1637 	return 0;
1638 }
1639 
1640 static int clean_dirty_subvols(struct reloc_control *rc)
1641 {
1642 	struct btrfs_root *root;
1643 	struct btrfs_root *next;
1644 	int ret = 0;
1645 	int ret2;
1646 
1647 	list_for_each_entry_safe(root, next, &rc->dirty_subvol_roots,
1648 				 reloc_dirty_list) {
1649 		if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
1650 			/* Merged subvolume, cleanup its reloc root */
1651 			struct btrfs_root *reloc_root = root->reloc_root;
1652 
1653 			list_del_init(&root->reloc_dirty_list);
1654 			root->reloc_root = NULL;
1655 			/*
1656 			 * Need barrier to ensure clear_bit() only happens after
1657 			 * root->reloc_root = NULL. Pairs with have_reloc_root.
1658 			 */
1659 			smp_wmb();
1660 			clear_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state);
1661 			if (reloc_root) {
1662 				/*
1663 				 * btrfs_drop_snapshot drops our ref we hold for
1664 				 * ->reloc_root.  If it fails however we must
1665 				 * drop the ref ourselves.
1666 				 */
1667 				ret2 = btrfs_drop_snapshot(reloc_root, 0, 1);
1668 				if (ret2 < 0) {
1669 					btrfs_put_root(reloc_root);
1670 					if (!ret)
1671 						ret = ret2;
1672 				}
1673 			}
1674 			btrfs_put_root(root);
1675 		} else {
1676 			/* Orphan reloc tree, just clean it up */
1677 			ret2 = btrfs_drop_snapshot(root, 0, 1);
1678 			if (ret2 < 0) {
1679 				btrfs_put_root(root);
1680 				if (!ret)
1681 					ret = ret2;
1682 			}
1683 		}
1684 	}
1685 	return ret;
1686 }
1687 
1688 /*
1689  * merge the relocated tree blocks in reloc tree with corresponding
1690  * fs tree.
1691  */
1692 static noinline_for_stack int merge_reloc_root(struct reloc_control *rc,
1693 					       struct btrfs_root *root)
1694 {
1695 	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
1696 	struct btrfs_key key;
1697 	struct btrfs_key next_key;
1698 	struct btrfs_trans_handle *trans = NULL;
1699 	struct btrfs_root *reloc_root;
1700 	struct btrfs_root_item *root_item;
1701 	struct btrfs_path *path;
1702 	struct extent_buffer *leaf;
1703 	int reserve_level;
1704 	int level;
1705 	int max_level;
1706 	int replaced = 0;
1707 	int ret = 0;
1708 	u32 min_reserved;
1709 
1710 	path = btrfs_alloc_path();
1711 	if (!path)
1712 		return -ENOMEM;
1713 	path->reada = READA_FORWARD;
1714 
1715 	reloc_root = root->reloc_root;
1716 	root_item = &reloc_root->root_item;
1717 
1718 	if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
1719 		level = btrfs_root_level(root_item);
1720 		atomic_inc(&reloc_root->node->refs);
1721 		path->nodes[level] = reloc_root->node;
1722 		path->slots[level] = 0;
1723 	} else {
1724 		btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
1725 
1726 		level = btrfs_root_drop_level(root_item);
1727 		BUG_ON(level == 0);
1728 		path->lowest_level = level;
1729 		ret = btrfs_search_slot(NULL, reloc_root, &key, path, 0, 0);
1730 		path->lowest_level = 0;
1731 		if (ret < 0) {
1732 			btrfs_free_path(path);
1733 			return ret;
1734 		}
1735 
1736 		btrfs_node_key_to_cpu(path->nodes[level], &next_key,
1737 				      path->slots[level]);
1738 		WARN_ON(memcmp(&key, &next_key, sizeof(key)));
1739 
1740 		btrfs_unlock_up_safe(path, 0);
1741 	}
1742 
1743 	/*
1744 	 * In merge_reloc_root(), we modify the upper level pointer to swap the
1745 	 * tree blocks between reloc tree and subvolume tree.  Thus for tree
1746 	 * block COW, we COW at most from level 1 to root level for each tree.
1747 	 *
1748 	 * Thus the needed metadata size is at most root_level * nodesize,
1749 	 * and * 2 since we have two trees to COW.
1750 	 */
1751 	reserve_level = max_t(int, 1, btrfs_root_level(root_item));
1752 	min_reserved = fs_info->nodesize * reserve_level * 2;
1753 	memset(&next_key, 0, sizeof(next_key));
1754 
1755 	while (1) {
1756 		ret = btrfs_block_rsv_refill(fs_info, rc->block_rsv,
1757 					     min_reserved,
1758 					     BTRFS_RESERVE_FLUSH_LIMIT);
1759 		if (ret)
1760 			goto out;
1761 		trans = btrfs_start_transaction(root, 0);
1762 		if (IS_ERR(trans)) {
1763 			ret = PTR_ERR(trans);
1764 			trans = NULL;
1765 			goto out;
1766 		}
1767 
1768 		/*
1769 		 * At this point we no longer have a reloc_control, so we can't
1770 		 * depend on btrfs_init_reloc_root to update our last_trans.
1771 		 *
1772 		 * But that's ok, we started the trans handle on our
1773 		 * corresponding fs_root, which means it's been added to the
1774 		 * dirty list.  At commit time we'll still call
1775 		 * btrfs_update_reloc_root() and update our root item
1776 		 * appropriately.
1777 		 */
1778 		reloc_root->last_trans = trans->transid;
1779 		trans->block_rsv = rc->block_rsv;
1780 
1781 		replaced = 0;
1782 		max_level = level;
1783 
1784 		ret = walk_down_reloc_tree(reloc_root, path, &level);
1785 		if (ret < 0)
1786 			goto out;
1787 		if (ret > 0)
1788 			break;
1789 
1790 		if (!find_next_key(path, level, &key) &&
1791 		    btrfs_comp_cpu_keys(&next_key, &key) >= 0) {
1792 			ret = 0;
1793 		} else {
1794 			ret = replace_path(trans, rc, root, reloc_root, path,
1795 					   &next_key, level, max_level);
1796 		}
1797 		if (ret < 0)
1798 			goto out;
1799 		if (ret > 0) {
1800 			level = ret;
1801 			btrfs_node_key_to_cpu(path->nodes[level], &key,
1802 					      path->slots[level]);
1803 			replaced = 1;
1804 		}
1805 
1806 		ret = walk_up_reloc_tree(reloc_root, path, &level);
1807 		if (ret > 0)
1808 			break;
1809 
1810 		BUG_ON(level == 0);
1811 		/*
1812 		 * save the merging progress in the drop_progress.
1813 		 * this is OK since root refs == 1 in this case.
1814 		 */
1815 		btrfs_node_key(path->nodes[level], &root_item->drop_progress,
1816 			       path->slots[level]);
1817 		btrfs_set_root_drop_level(root_item, level);
1818 
1819 		btrfs_end_transaction_throttle(trans);
1820 		trans = NULL;
1821 
1822 		btrfs_btree_balance_dirty(fs_info);
1823 
1824 		if (replaced && rc->stage == UPDATE_DATA_PTRS)
1825 			invalidate_extent_cache(root, &key, &next_key);
1826 	}
1827 
1828 	/*
1829 	 * handle the case only one block in the fs tree need to be
1830 	 * relocated and the block is tree root.
1831 	 */
1832 	leaf = btrfs_lock_root_node(root);
1833 	ret = btrfs_cow_block(trans, root, leaf, NULL, 0, &leaf,
1834 			      BTRFS_NESTING_COW);
1835 	btrfs_tree_unlock(leaf);
1836 	free_extent_buffer(leaf);
1837 out:
1838 	btrfs_free_path(path);
1839 
1840 	if (ret == 0) {
1841 		ret = insert_dirty_subvol(trans, rc, root);
1842 		if (ret)
1843 			btrfs_abort_transaction(trans, ret);
1844 	}
1845 
1846 	if (trans)
1847 		btrfs_end_transaction_throttle(trans);
1848 
1849 	btrfs_btree_balance_dirty(fs_info);
1850 
1851 	if (replaced && rc->stage == UPDATE_DATA_PTRS)
1852 		invalidate_extent_cache(root, &key, &next_key);
1853 
1854 	return ret;
1855 }
1856 
1857 static noinline_for_stack
1858 int prepare_to_merge(struct reloc_control *rc, int err)
1859 {
1860 	struct btrfs_root *root = rc->extent_root;
1861 	struct btrfs_fs_info *fs_info = root->fs_info;
1862 	struct btrfs_root *reloc_root;
1863 	struct btrfs_trans_handle *trans;
1864 	LIST_HEAD(reloc_roots);
1865 	u64 num_bytes = 0;
1866 	int ret;
1867 
1868 	mutex_lock(&fs_info->reloc_mutex);
1869 	rc->merging_rsv_size += fs_info->nodesize * (BTRFS_MAX_LEVEL - 1) * 2;
1870 	rc->merging_rsv_size += rc->nodes_relocated * 2;
1871 	mutex_unlock(&fs_info->reloc_mutex);
1872 
1873 again:
1874 	if (!err) {
1875 		num_bytes = rc->merging_rsv_size;
1876 		ret = btrfs_block_rsv_add(fs_info, rc->block_rsv, num_bytes,
1877 					  BTRFS_RESERVE_FLUSH_ALL);
1878 		if (ret)
1879 			err = ret;
1880 	}
1881 
1882 	trans = btrfs_join_transaction(rc->extent_root);
1883 	if (IS_ERR(trans)) {
1884 		if (!err)
1885 			btrfs_block_rsv_release(fs_info, rc->block_rsv,
1886 						num_bytes, NULL);
1887 		return PTR_ERR(trans);
1888 	}
1889 
1890 	if (!err) {
1891 		if (num_bytes != rc->merging_rsv_size) {
1892 			btrfs_end_transaction(trans);
1893 			btrfs_block_rsv_release(fs_info, rc->block_rsv,
1894 						num_bytes, NULL);
1895 			goto again;
1896 		}
1897 	}
1898 
1899 	rc->merge_reloc_tree = true;
1900 
1901 	while (!list_empty(&rc->reloc_roots)) {
1902 		reloc_root = list_entry(rc->reloc_roots.next,
1903 					struct btrfs_root, root_list);
1904 		list_del_init(&reloc_root->root_list);
1905 
1906 		root = btrfs_get_fs_root(fs_info, reloc_root->root_key.offset,
1907 				false);
1908 		if (IS_ERR(root)) {
1909 			/*
1910 			 * Even if we have an error we need this reloc root
1911 			 * back on our list so we can clean up properly.
1912 			 */
1913 			list_add(&reloc_root->root_list, &reloc_roots);
1914 			btrfs_abort_transaction(trans, (int)PTR_ERR(root));
1915 			if (!err)
1916 				err = PTR_ERR(root);
1917 			break;
1918 		}
1919 
1920 		if (unlikely(root->reloc_root != reloc_root)) {
1921 			if (root->reloc_root) {
1922 				btrfs_err(fs_info,
1923 "reloc tree mismatch, root %lld has reloc root key (%lld %u %llu) gen %llu, expect reloc root key (%lld %u %llu) gen %llu",
1924 					  root->root_key.objectid,
1925 					  root->reloc_root->root_key.objectid,
1926 					  root->reloc_root->root_key.type,
1927 					  root->reloc_root->root_key.offset,
1928 					  btrfs_root_generation(
1929 						  &root->reloc_root->root_item),
1930 					  reloc_root->root_key.objectid,
1931 					  reloc_root->root_key.type,
1932 					  reloc_root->root_key.offset,
1933 					  btrfs_root_generation(
1934 						  &reloc_root->root_item));
1935 			} else {
1936 				btrfs_err(fs_info,
1937 "reloc tree mismatch, root %lld has no reloc root, expect reloc root key (%lld %u %llu) gen %llu",
1938 					  root->root_key.objectid,
1939 					  reloc_root->root_key.objectid,
1940 					  reloc_root->root_key.type,
1941 					  reloc_root->root_key.offset,
1942 					  btrfs_root_generation(
1943 						  &reloc_root->root_item));
1944 			}
1945 			list_add(&reloc_root->root_list, &reloc_roots);
1946 			btrfs_put_root(root);
1947 			btrfs_abort_transaction(trans, -EUCLEAN);
1948 			if (!err)
1949 				err = -EUCLEAN;
1950 			break;
1951 		}
1952 
1953 		/*
1954 		 * set reference count to 1, so btrfs_recover_relocation
1955 		 * knows it should resumes merging
1956 		 */
1957 		if (!err)
1958 			btrfs_set_root_refs(&reloc_root->root_item, 1);
1959 		ret = btrfs_update_reloc_root(trans, root);
1960 
1961 		/*
1962 		 * Even if we have an error we need this reloc root back on our
1963 		 * list so we can clean up properly.
1964 		 */
1965 		list_add(&reloc_root->root_list, &reloc_roots);
1966 		btrfs_put_root(root);
1967 
1968 		if (ret) {
1969 			btrfs_abort_transaction(trans, ret);
1970 			if (!err)
1971 				err = ret;
1972 			break;
1973 		}
1974 	}
1975 
1976 	list_splice(&reloc_roots, &rc->reloc_roots);
1977 
1978 	if (!err)
1979 		err = btrfs_commit_transaction(trans);
1980 	else
1981 		btrfs_end_transaction(trans);
1982 	return err;
1983 }
1984 
1985 static noinline_for_stack
1986 void free_reloc_roots(struct list_head *list)
1987 {
1988 	struct btrfs_root *reloc_root, *tmp;
1989 
1990 	list_for_each_entry_safe(reloc_root, tmp, list, root_list)
1991 		__del_reloc_root(reloc_root);
1992 }
1993 
1994 static noinline_for_stack
1995 void merge_reloc_roots(struct reloc_control *rc)
1996 {
1997 	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
1998 	struct btrfs_root *root;
1999 	struct btrfs_root *reloc_root;
2000 	LIST_HEAD(reloc_roots);
2001 	int found = 0;
2002 	int ret = 0;
2003 again:
2004 	root = rc->extent_root;
2005 
2006 	/*
2007 	 * this serializes us with btrfs_record_root_in_transaction,
2008 	 * we have to make sure nobody is in the middle of
2009 	 * adding their roots to the list while we are
2010 	 * doing this splice
2011 	 */
2012 	mutex_lock(&fs_info->reloc_mutex);
2013 	list_splice_init(&rc->reloc_roots, &reloc_roots);
2014 	mutex_unlock(&fs_info->reloc_mutex);
2015 
2016 	while (!list_empty(&reloc_roots)) {
2017 		found = 1;
2018 		reloc_root = list_entry(reloc_roots.next,
2019 					struct btrfs_root, root_list);
2020 
2021 		root = btrfs_get_fs_root(fs_info, reloc_root->root_key.offset,
2022 					 false);
2023 		if (btrfs_root_refs(&reloc_root->root_item) > 0) {
2024 			if (WARN_ON(IS_ERR(root))) {
2025 				/*
2026 				 * For recovery we read the fs roots on mount,
2027 				 * and if we didn't find the root then we marked
2028 				 * the reloc root as a garbage root.  For normal
2029 				 * relocation obviously the root should exist in
2030 				 * memory.  However there's no reason we can't
2031 				 * handle the error properly here just in case.
2032 				 */
2033 				ret = PTR_ERR(root);
2034 				goto out;
2035 			}
2036 			if (WARN_ON(root->reloc_root != reloc_root)) {
2037 				/*
2038 				 * This can happen if on-disk metadata has some
2039 				 * corruption, e.g. bad reloc tree key offset.
2040 				 */
2041 				ret = -EINVAL;
2042 				goto out;
2043 			}
2044 			ret = merge_reloc_root(rc, root);
2045 			btrfs_put_root(root);
2046 			if (ret) {
2047 				if (list_empty(&reloc_root->root_list))
2048 					list_add_tail(&reloc_root->root_list,
2049 						      &reloc_roots);
2050 				goto out;
2051 			}
2052 		} else {
2053 			if (!IS_ERR(root)) {
2054 				if (root->reloc_root == reloc_root) {
2055 					root->reloc_root = NULL;
2056 					btrfs_put_root(reloc_root);
2057 				}
2058 				clear_bit(BTRFS_ROOT_DEAD_RELOC_TREE,
2059 					  &root->state);
2060 				btrfs_put_root(root);
2061 			}
2062 
2063 			list_del_init(&reloc_root->root_list);
2064 			/* Don't forget to queue this reloc root for cleanup */
2065 			list_add_tail(&reloc_root->reloc_dirty_list,
2066 				      &rc->dirty_subvol_roots);
2067 		}
2068 	}
2069 
2070 	if (found) {
2071 		found = 0;
2072 		goto again;
2073 	}
2074 out:
2075 	if (ret) {
2076 		btrfs_handle_fs_error(fs_info, ret, NULL);
2077 		free_reloc_roots(&reloc_roots);
2078 
2079 		/* new reloc root may be added */
2080 		mutex_lock(&fs_info->reloc_mutex);
2081 		list_splice_init(&rc->reloc_roots, &reloc_roots);
2082 		mutex_unlock(&fs_info->reloc_mutex);
2083 		free_reloc_roots(&reloc_roots);
2084 	}
2085 
2086 	/*
2087 	 * We used to have
2088 	 *
2089 	 * BUG_ON(!RB_EMPTY_ROOT(&rc->reloc_root_tree.rb_root));
2090 	 *
2091 	 * here, but it's wrong.  If we fail to start the transaction in
2092 	 * prepare_to_merge() we will have only 0 ref reloc roots, none of which
2093 	 * have actually been removed from the reloc_root_tree rb tree.  This is
2094 	 * fine because we're bailing here, and we hold a reference on the root
2095 	 * for the list that holds it, so these roots will be cleaned up when we
2096 	 * do the reloc_dirty_list afterwards.  Meanwhile the root->reloc_root
2097 	 * will be cleaned up on unmount.
2098 	 *
2099 	 * The remaining nodes will be cleaned up by free_reloc_control.
2100 	 */
2101 }
2102 
2103 static void free_block_list(struct rb_root *blocks)
2104 {
2105 	struct tree_block *block;
2106 	struct rb_node *rb_node;
2107 	while ((rb_node = rb_first(blocks))) {
2108 		block = rb_entry(rb_node, struct tree_block, rb_node);
2109 		rb_erase(rb_node, blocks);
2110 		kfree(block);
2111 	}
2112 }
2113 
2114 static int record_reloc_root_in_trans(struct btrfs_trans_handle *trans,
2115 				      struct btrfs_root *reloc_root)
2116 {
2117 	struct btrfs_fs_info *fs_info = reloc_root->fs_info;
2118 	struct btrfs_root *root;
2119 	int ret;
2120 
2121 	if (reloc_root->last_trans == trans->transid)
2122 		return 0;
2123 
2124 	root = btrfs_get_fs_root(fs_info, reloc_root->root_key.offset, false);
2125 
2126 	/*
2127 	 * This should succeed, since we can't have a reloc root without having
2128 	 * already looked up the actual root and created the reloc root for this
2129 	 * root.
2130 	 *
2131 	 * However if there's some sort of corruption where we have a ref to a
2132 	 * reloc root without a corresponding root this could return ENOENT.
2133 	 */
2134 	if (IS_ERR(root)) {
2135 		ASSERT(0);
2136 		return PTR_ERR(root);
2137 	}
2138 	if (root->reloc_root != reloc_root) {
2139 		ASSERT(0);
2140 		btrfs_err(fs_info,
2141 			  "root %llu has two reloc roots associated with it",
2142 			  reloc_root->root_key.offset);
2143 		btrfs_put_root(root);
2144 		return -EUCLEAN;
2145 	}
2146 	ret = btrfs_record_root_in_trans(trans, root);
2147 	btrfs_put_root(root);
2148 
2149 	return ret;
2150 }
2151 
2152 static noinline_for_stack
2153 struct btrfs_root *select_reloc_root(struct btrfs_trans_handle *trans,
2154 				     struct reloc_control *rc,
2155 				     struct btrfs_backref_node *node,
2156 				     struct btrfs_backref_edge *edges[])
2157 {
2158 	struct btrfs_backref_node *next;
2159 	struct btrfs_root *root;
2160 	int index = 0;
2161 	int ret;
2162 
2163 	next = node;
2164 	while (1) {
2165 		cond_resched();
2166 		next = walk_up_backref(next, edges, &index);
2167 		root = next->root;
2168 
2169 		/*
2170 		 * If there is no root, then our references for this block are
2171 		 * incomplete, as we should be able to walk all the way up to a
2172 		 * block that is owned by a root.
2173 		 *
2174 		 * This path is only for SHAREABLE roots, so if we come upon a
2175 		 * non-SHAREABLE root then we have backrefs that resolve
2176 		 * improperly.
2177 		 *
2178 		 * Both of these cases indicate file system corruption, or a bug
2179 		 * in the backref walking code.
2180 		 */
2181 		if (!root) {
2182 			ASSERT(0);
2183 			btrfs_err(trans->fs_info,
2184 		"bytenr %llu doesn't have a backref path ending in a root",
2185 				  node->bytenr);
2186 			return ERR_PTR(-EUCLEAN);
2187 		}
2188 		if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) {
2189 			ASSERT(0);
2190 			btrfs_err(trans->fs_info,
2191 	"bytenr %llu has multiple refs with one ending in a non-shareable root",
2192 				  node->bytenr);
2193 			return ERR_PTR(-EUCLEAN);
2194 		}
2195 
2196 		if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
2197 			ret = record_reloc_root_in_trans(trans, root);
2198 			if (ret)
2199 				return ERR_PTR(ret);
2200 			break;
2201 		}
2202 
2203 		ret = btrfs_record_root_in_trans(trans, root);
2204 		if (ret)
2205 			return ERR_PTR(ret);
2206 		root = root->reloc_root;
2207 
2208 		/*
2209 		 * We could have raced with another thread which failed, so
2210 		 * root->reloc_root may not be set, return ENOENT in this case.
2211 		 */
2212 		if (!root)
2213 			return ERR_PTR(-ENOENT);
2214 
2215 		if (next->new_bytenr != root->node->start) {
2216 			/*
2217 			 * We just created the reloc root, so we shouldn't have
2218 			 * ->new_bytenr set and this shouldn't be in the changed
2219 			 *  list.  If it is then we have multiple roots pointing
2220 			 *  at the same bytenr which indicates corruption, or
2221 			 *  we've made a mistake in the backref walking code.
2222 			 */
2223 			ASSERT(next->new_bytenr == 0);
2224 			ASSERT(list_empty(&next->list));
2225 			if (next->new_bytenr || !list_empty(&next->list)) {
2226 				btrfs_err(trans->fs_info,
2227 	"bytenr %llu possibly has multiple roots pointing at the same bytenr %llu",
2228 					  node->bytenr, next->bytenr);
2229 				return ERR_PTR(-EUCLEAN);
2230 			}
2231 
2232 			next->new_bytenr = root->node->start;
2233 			btrfs_put_root(next->root);
2234 			next->root = btrfs_grab_root(root);
2235 			ASSERT(next->root);
2236 			list_add_tail(&next->list,
2237 				      &rc->backref_cache.changed);
2238 			mark_block_processed(rc, next);
2239 			break;
2240 		}
2241 
2242 		WARN_ON(1);
2243 		root = NULL;
2244 		next = walk_down_backref(edges, &index);
2245 		if (!next || next->level <= node->level)
2246 			break;
2247 	}
2248 	if (!root) {
2249 		/*
2250 		 * This can happen if there's fs corruption or if there's a bug
2251 		 * in the backref lookup code.
2252 		 */
2253 		ASSERT(0);
2254 		return ERR_PTR(-ENOENT);
2255 	}
2256 
2257 	next = node;
2258 	/* setup backref node path for btrfs_reloc_cow_block */
2259 	while (1) {
2260 		rc->backref_cache.path[next->level] = next;
2261 		if (--index < 0)
2262 			break;
2263 		next = edges[index]->node[UPPER];
2264 	}
2265 	return root;
2266 }
2267 
2268 /*
2269  * Select a tree root for relocation.
2270  *
2271  * Return NULL if the block is not shareable. We should use do_relocation() in
2272  * this case.
2273  *
2274  * Return a tree root pointer if the block is shareable.
2275  * Return -ENOENT if the block is root of reloc tree.
2276  */
2277 static noinline_for_stack
2278 struct btrfs_root *select_one_root(struct btrfs_backref_node *node)
2279 {
2280 	struct btrfs_backref_node *next;
2281 	struct btrfs_root *root;
2282 	struct btrfs_root *fs_root = NULL;
2283 	struct btrfs_backref_edge *edges[BTRFS_MAX_LEVEL - 1];
2284 	int index = 0;
2285 
2286 	next = node;
2287 	while (1) {
2288 		cond_resched();
2289 		next = walk_up_backref(next, edges, &index);
2290 		root = next->root;
2291 
2292 		/*
2293 		 * This can occur if we have incomplete extent refs leading all
2294 		 * the way up a particular path, in this case return -EUCLEAN.
2295 		 */
2296 		if (!root)
2297 			return ERR_PTR(-EUCLEAN);
2298 
2299 		/* No other choice for non-shareable tree */
2300 		if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state))
2301 			return root;
2302 
2303 		if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID)
2304 			fs_root = root;
2305 
2306 		if (next != node)
2307 			return NULL;
2308 
2309 		next = walk_down_backref(edges, &index);
2310 		if (!next || next->level <= node->level)
2311 			break;
2312 	}
2313 
2314 	if (!fs_root)
2315 		return ERR_PTR(-ENOENT);
2316 	return fs_root;
2317 }
2318 
2319 static noinline_for_stack
2320 u64 calcu_metadata_size(struct reloc_control *rc,
2321 			struct btrfs_backref_node *node, int reserve)
2322 {
2323 	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
2324 	struct btrfs_backref_node *next = node;
2325 	struct btrfs_backref_edge *edge;
2326 	struct btrfs_backref_edge *edges[BTRFS_MAX_LEVEL - 1];
2327 	u64 num_bytes = 0;
2328 	int index = 0;
2329 
2330 	BUG_ON(reserve && node->processed);
2331 
2332 	while (next) {
2333 		cond_resched();
2334 		while (1) {
2335 			if (next->processed && (reserve || next != node))
2336 				break;
2337 
2338 			num_bytes += fs_info->nodesize;
2339 
2340 			if (list_empty(&next->upper))
2341 				break;
2342 
2343 			edge = list_entry(next->upper.next,
2344 					struct btrfs_backref_edge, list[LOWER]);
2345 			edges[index++] = edge;
2346 			next = edge->node[UPPER];
2347 		}
2348 		next = walk_down_backref(edges, &index);
2349 	}
2350 	return num_bytes;
2351 }
2352 
2353 static int reserve_metadata_space(struct btrfs_trans_handle *trans,
2354 				  struct reloc_control *rc,
2355 				  struct btrfs_backref_node *node)
2356 {
2357 	struct btrfs_root *root = rc->extent_root;
2358 	struct btrfs_fs_info *fs_info = root->fs_info;
2359 	u64 num_bytes;
2360 	int ret;
2361 	u64 tmp;
2362 
2363 	num_bytes = calcu_metadata_size(rc, node, 1) * 2;
2364 
2365 	trans->block_rsv = rc->block_rsv;
2366 	rc->reserved_bytes += num_bytes;
2367 
2368 	/*
2369 	 * We are under a transaction here so we can only do limited flushing.
2370 	 * If we get an enospc just kick back -EAGAIN so we know to drop the
2371 	 * transaction and try to refill when we can flush all the things.
2372 	 */
2373 	ret = btrfs_block_rsv_refill(fs_info, rc->block_rsv, num_bytes,
2374 				     BTRFS_RESERVE_FLUSH_LIMIT);
2375 	if (ret) {
2376 		tmp = fs_info->nodesize * RELOCATION_RESERVED_NODES;
2377 		while (tmp <= rc->reserved_bytes)
2378 			tmp <<= 1;
2379 		/*
2380 		 * only one thread can access block_rsv at this point,
2381 		 * so we don't need hold lock to protect block_rsv.
2382 		 * we expand more reservation size here to allow enough
2383 		 * space for relocation and we will return earlier in
2384 		 * enospc case.
2385 		 */
2386 		rc->block_rsv->size = tmp + fs_info->nodesize *
2387 				      RELOCATION_RESERVED_NODES;
2388 		return -EAGAIN;
2389 	}
2390 
2391 	return 0;
2392 }
2393 
2394 /*
2395  * relocate a block tree, and then update pointers in upper level
2396  * blocks that reference the block to point to the new location.
2397  *
2398  * if called by link_to_upper, the block has already been relocated.
2399  * in that case this function just updates pointers.
2400  */
2401 static int do_relocation(struct btrfs_trans_handle *trans,
2402 			 struct reloc_control *rc,
2403 			 struct btrfs_backref_node *node,
2404 			 struct btrfs_key *key,
2405 			 struct btrfs_path *path, int lowest)
2406 {
2407 	struct btrfs_backref_node *upper;
2408 	struct btrfs_backref_edge *edge;
2409 	struct btrfs_backref_edge *edges[BTRFS_MAX_LEVEL - 1];
2410 	struct btrfs_root *root;
2411 	struct extent_buffer *eb;
2412 	u32 blocksize;
2413 	u64 bytenr;
2414 	int slot;
2415 	int ret = 0;
2416 
2417 	/*
2418 	 * If we are lowest then this is the first time we're processing this
2419 	 * block, and thus shouldn't have an eb associated with it yet.
2420 	 */
2421 	ASSERT(!lowest || !node->eb);
2422 
2423 	path->lowest_level = node->level + 1;
2424 	rc->backref_cache.path[node->level] = node;
2425 	list_for_each_entry(edge, &node->upper, list[LOWER]) {
2426 		struct btrfs_ref ref = { 0 };
2427 
2428 		cond_resched();
2429 
2430 		upper = edge->node[UPPER];
2431 		root = select_reloc_root(trans, rc, upper, edges);
2432 		if (IS_ERR(root)) {
2433 			ret = PTR_ERR(root);
2434 			goto next;
2435 		}
2436 
2437 		if (upper->eb && !upper->locked) {
2438 			if (!lowest) {
2439 				ret = btrfs_bin_search(upper->eb, 0, key, &slot);
2440 				if (ret < 0)
2441 					goto next;
2442 				BUG_ON(ret);
2443 				bytenr = btrfs_node_blockptr(upper->eb, slot);
2444 				if (node->eb->start == bytenr)
2445 					goto next;
2446 			}
2447 			btrfs_backref_drop_node_buffer(upper);
2448 		}
2449 
2450 		if (!upper->eb) {
2451 			ret = btrfs_search_slot(trans, root, key, path, 0, 1);
2452 			if (ret) {
2453 				if (ret > 0)
2454 					ret = -ENOENT;
2455 
2456 				btrfs_release_path(path);
2457 				break;
2458 			}
2459 
2460 			if (!upper->eb) {
2461 				upper->eb = path->nodes[upper->level];
2462 				path->nodes[upper->level] = NULL;
2463 			} else {
2464 				BUG_ON(upper->eb != path->nodes[upper->level]);
2465 			}
2466 
2467 			upper->locked = 1;
2468 			path->locks[upper->level] = 0;
2469 
2470 			slot = path->slots[upper->level];
2471 			btrfs_release_path(path);
2472 		} else {
2473 			ret = btrfs_bin_search(upper->eb, 0, key, &slot);
2474 			if (ret < 0)
2475 				goto next;
2476 			BUG_ON(ret);
2477 		}
2478 
2479 		bytenr = btrfs_node_blockptr(upper->eb, slot);
2480 		if (lowest) {
2481 			if (bytenr != node->bytenr) {
2482 				btrfs_err(root->fs_info,
2483 		"lowest leaf/node mismatch: bytenr %llu node->bytenr %llu slot %d upper %llu",
2484 					  bytenr, node->bytenr, slot,
2485 					  upper->eb->start);
2486 				ret = -EIO;
2487 				goto next;
2488 			}
2489 		} else {
2490 			if (node->eb->start == bytenr)
2491 				goto next;
2492 		}
2493 
2494 		blocksize = root->fs_info->nodesize;
2495 		eb = btrfs_read_node_slot(upper->eb, slot);
2496 		if (IS_ERR(eb)) {
2497 			ret = PTR_ERR(eb);
2498 			goto next;
2499 		}
2500 		btrfs_tree_lock(eb);
2501 
2502 		if (!node->eb) {
2503 			ret = btrfs_cow_block(trans, root, eb, upper->eb,
2504 					      slot, &eb, BTRFS_NESTING_COW);
2505 			btrfs_tree_unlock(eb);
2506 			free_extent_buffer(eb);
2507 			if (ret < 0)
2508 				goto next;
2509 			/*
2510 			 * We've just COWed this block, it should have updated
2511 			 * the correct backref node entry.
2512 			 */
2513 			ASSERT(node->eb == eb);
2514 		} else {
2515 			btrfs_set_node_blockptr(upper->eb, slot,
2516 						node->eb->start);
2517 			btrfs_set_node_ptr_generation(upper->eb, slot,
2518 						      trans->transid);
2519 			btrfs_mark_buffer_dirty(trans, upper->eb);
2520 
2521 			btrfs_init_generic_ref(&ref, BTRFS_ADD_DELAYED_REF,
2522 					       node->eb->start, blocksize,
2523 					       upper->eb->start,
2524 					       btrfs_header_owner(upper->eb));
2525 			btrfs_init_tree_ref(&ref, node->level,
2526 					    btrfs_header_owner(upper->eb),
2527 					    root->root_key.objectid, false);
2528 			ret = btrfs_inc_extent_ref(trans, &ref);
2529 			if (!ret)
2530 				ret = btrfs_drop_subtree(trans, root, eb,
2531 							 upper->eb);
2532 			if (ret)
2533 				btrfs_abort_transaction(trans, ret);
2534 		}
2535 next:
2536 		if (!upper->pending)
2537 			btrfs_backref_drop_node_buffer(upper);
2538 		else
2539 			btrfs_backref_unlock_node_buffer(upper);
2540 		if (ret)
2541 			break;
2542 	}
2543 
2544 	if (!ret && node->pending) {
2545 		btrfs_backref_drop_node_buffer(node);
2546 		list_move_tail(&node->list, &rc->backref_cache.changed);
2547 		node->pending = 0;
2548 	}
2549 
2550 	path->lowest_level = 0;
2551 
2552 	/*
2553 	 * We should have allocated all of our space in the block rsv and thus
2554 	 * shouldn't ENOSPC.
2555 	 */
2556 	ASSERT(ret != -ENOSPC);
2557 	return ret;
2558 }
2559 
2560 static int link_to_upper(struct btrfs_trans_handle *trans,
2561 			 struct reloc_control *rc,
2562 			 struct btrfs_backref_node *node,
2563 			 struct btrfs_path *path)
2564 {
2565 	struct btrfs_key key;
2566 
2567 	btrfs_node_key_to_cpu(node->eb, &key, 0);
2568 	return do_relocation(trans, rc, node, &key, path, 0);
2569 }
2570 
2571 static int finish_pending_nodes(struct btrfs_trans_handle *trans,
2572 				struct reloc_control *rc,
2573 				struct btrfs_path *path, int err)
2574 {
2575 	LIST_HEAD(list);
2576 	struct btrfs_backref_cache *cache = &rc->backref_cache;
2577 	struct btrfs_backref_node *node;
2578 	int level;
2579 	int ret;
2580 
2581 	for (level = 0; level < BTRFS_MAX_LEVEL; level++) {
2582 		while (!list_empty(&cache->pending[level])) {
2583 			node = list_entry(cache->pending[level].next,
2584 					  struct btrfs_backref_node, list);
2585 			list_move_tail(&node->list, &list);
2586 			BUG_ON(!node->pending);
2587 
2588 			if (!err) {
2589 				ret = link_to_upper(trans, rc, node, path);
2590 				if (ret < 0)
2591 					err = ret;
2592 			}
2593 		}
2594 		list_splice_init(&list, &cache->pending[level]);
2595 	}
2596 	return err;
2597 }
2598 
2599 /*
2600  * mark a block and all blocks directly/indirectly reference the block
2601  * as processed.
2602  */
2603 static void update_processed_blocks(struct reloc_control *rc,
2604 				    struct btrfs_backref_node *node)
2605 {
2606 	struct btrfs_backref_node *next = node;
2607 	struct btrfs_backref_edge *edge;
2608 	struct btrfs_backref_edge *edges[BTRFS_MAX_LEVEL - 1];
2609 	int index = 0;
2610 
2611 	while (next) {
2612 		cond_resched();
2613 		while (1) {
2614 			if (next->processed)
2615 				break;
2616 
2617 			mark_block_processed(rc, next);
2618 
2619 			if (list_empty(&next->upper))
2620 				break;
2621 
2622 			edge = list_entry(next->upper.next,
2623 					struct btrfs_backref_edge, list[LOWER]);
2624 			edges[index++] = edge;
2625 			next = edge->node[UPPER];
2626 		}
2627 		next = walk_down_backref(edges, &index);
2628 	}
2629 }
2630 
2631 static int tree_block_processed(u64 bytenr, struct reloc_control *rc)
2632 {
2633 	u32 blocksize = rc->extent_root->fs_info->nodesize;
2634 
2635 	if (test_range_bit(&rc->processed_blocks, bytenr,
2636 			   bytenr + blocksize - 1, EXTENT_DIRTY, NULL))
2637 		return 1;
2638 	return 0;
2639 }
2640 
2641 static int get_tree_block_key(struct btrfs_fs_info *fs_info,
2642 			      struct tree_block *block)
2643 {
2644 	struct btrfs_tree_parent_check check = {
2645 		.level = block->level,
2646 		.owner_root = block->owner,
2647 		.transid = block->key.offset
2648 	};
2649 	struct extent_buffer *eb;
2650 
2651 	eb = read_tree_block(fs_info, block->bytenr, &check);
2652 	if (IS_ERR(eb))
2653 		return PTR_ERR(eb);
2654 	if (!extent_buffer_uptodate(eb)) {
2655 		free_extent_buffer(eb);
2656 		return -EIO;
2657 	}
2658 	if (block->level == 0)
2659 		btrfs_item_key_to_cpu(eb, &block->key, 0);
2660 	else
2661 		btrfs_node_key_to_cpu(eb, &block->key, 0);
2662 	free_extent_buffer(eb);
2663 	block->key_ready = true;
2664 	return 0;
2665 }
2666 
2667 /*
2668  * helper function to relocate a tree block
2669  */
2670 static int relocate_tree_block(struct btrfs_trans_handle *trans,
2671 				struct reloc_control *rc,
2672 				struct btrfs_backref_node *node,
2673 				struct btrfs_key *key,
2674 				struct btrfs_path *path)
2675 {
2676 	struct btrfs_root *root;
2677 	int ret = 0;
2678 
2679 	if (!node)
2680 		return 0;
2681 
2682 	/*
2683 	 * If we fail here we want to drop our backref_node because we are going
2684 	 * to start over and regenerate the tree for it.
2685 	 */
2686 	ret = reserve_metadata_space(trans, rc, node);
2687 	if (ret)
2688 		goto out;
2689 
2690 	BUG_ON(node->processed);
2691 	root = select_one_root(node);
2692 	if (IS_ERR(root)) {
2693 		ret = PTR_ERR(root);
2694 
2695 		/* See explanation in select_one_root for the -EUCLEAN case. */
2696 		ASSERT(ret == -ENOENT);
2697 		if (ret == -ENOENT) {
2698 			ret = 0;
2699 			update_processed_blocks(rc, node);
2700 		}
2701 		goto out;
2702 	}
2703 
2704 	if (root) {
2705 		if (test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) {
2706 			/*
2707 			 * This block was the root block of a root, and this is
2708 			 * the first time we're processing the block and thus it
2709 			 * should not have had the ->new_bytenr modified and
2710 			 * should have not been included on the changed list.
2711 			 *
2712 			 * However in the case of corruption we could have
2713 			 * multiple refs pointing to the same block improperly,
2714 			 * and thus we would trip over these checks.  ASSERT()
2715 			 * for the developer case, because it could indicate a
2716 			 * bug in the backref code, however error out for a
2717 			 * normal user in the case of corruption.
2718 			 */
2719 			ASSERT(node->new_bytenr == 0);
2720 			ASSERT(list_empty(&node->list));
2721 			if (node->new_bytenr || !list_empty(&node->list)) {
2722 				btrfs_err(root->fs_info,
2723 				  "bytenr %llu has improper references to it",
2724 					  node->bytenr);
2725 				ret = -EUCLEAN;
2726 				goto out;
2727 			}
2728 			ret = btrfs_record_root_in_trans(trans, root);
2729 			if (ret)
2730 				goto out;
2731 			/*
2732 			 * Another thread could have failed, need to check if we
2733 			 * have reloc_root actually set.
2734 			 */
2735 			if (!root->reloc_root) {
2736 				ret = -ENOENT;
2737 				goto out;
2738 			}
2739 			root = root->reloc_root;
2740 			node->new_bytenr = root->node->start;
2741 			btrfs_put_root(node->root);
2742 			node->root = btrfs_grab_root(root);
2743 			ASSERT(node->root);
2744 			list_add_tail(&node->list, &rc->backref_cache.changed);
2745 		} else {
2746 			path->lowest_level = node->level;
2747 			if (root == root->fs_info->chunk_root)
2748 				btrfs_reserve_chunk_metadata(trans, false);
2749 			ret = btrfs_search_slot(trans, root, key, path, 0, 1);
2750 			btrfs_release_path(path);
2751 			if (root == root->fs_info->chunk_root)
2752 				btrfs_trans_release_chunk_metadata(trans);
2753 			if (ret > 0)
2754 				ret = 0;
2755 		}
2756 		if (!ret)
2757 			update_processed_blocks(rc, node);
2758 	} else {
2759 		ret = do_relocation(trans, rc, node, key, path, 1);
2760 	}
2761 out:
2762 	if (ret || node->level == 0 || node->cowonly)
2763 		btrfs_backref_cleanup_node(&rc->backref_cache, node);
2764 	return ret;
2765 }
2766 
2767 /*
2768  * relocate a list of blocks
2769  */
2770 static noinline_for_stack
2771 int relocate_tree_blocks(struct btrfs_trans_handle *trans,
2772 			 struct reloc_control *rc, struct rb_root *blocks)
2773 {
2774 	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
2775 	struct btrfs_backref_node *node;
2776 	struct btrfs_path *path;
2777 	struct tree_block *block;
2778 	struct tree_block *next;
2779 	int ret;
2780 	int err = 0;
2781 
2782 	path = btrfs_alloc_path();
2783 	if (!path) {
2784 		err = -ENOMEM;
2785 		goto out_free_blocks;
2786 	}
2787 
2788 	/* Kick in readahead for tree blocks with missing keys */
2789 	rbtree_postorder_for_each_entry_safe(block, next, blocks, rb_node) {
2790 		if (!block->key_ready)
2791 			btrfs_readahead_tree_block(fs_info, block->bytenr,
2792 						   block->owner, 0,
2793 						   block->level);
2794 	}
2795 
2796 	/* Get first keys */
2797 	rbtree_postorder_for_each_entry_safe(block, next, blocks, rb_node) {
2798 		if (!block->key_ready) {
2799 			err = get_tree_block_key(fs_info, block);
2800 			if (err)
2801 				goto out_free_path;
2802 		}
2803 	}
2804 
2805 	/* Do tree relocation */
2806 	rbtree_postorder_for_each_entry_safe(block, next, blocks, rb_node) {
2807 		node = build_backref_tree(trans, rc, &block->key,
2808 					  block->level, block->bytenr);
2809 		if (IS_ERR(node)) {
2810 			err = PTR_ERR(node);
2811 			goto out;
2812 		}
2813 
2814 		ret = relocate_tree_block(trans, rc, node, &block->key,
2815 					  path);
2816 		if (ret < 0) {
2817 			err = ret;
2818 			break;
2819 		}
2820 	}
2821 out:
2822 	err = finish_pending_nodes(trans, rc, path, err);
2823 
2824 out_free_path:
2825 	btrfs_free_path(path);
2826 out_free_blocks:
2827 	free_block_list(blocks);
2828 	return err;
2829 }
2830 
2831 static noinline_for_stack int prealloc_file_extent_cluster(
2832 				struct btrfs_inode *inode,
2833 				const struct file_extent_cluster *cluster)
2834 {
2835 	u64 alloc_hint = 0;
2836 	u64 start;
2837 	u64 end;
2838 	u64 offset = inode->index_cnt;
2839 	u64 num_bytes;
2840 	int nr;
2841 	int ret = 0;
2842 	u64 i_size = i_size_read(&inode->vfs_inode);
2843 	u64 prealloc_start = cluster->start - offset;
2844 	u64 prealloc_end = cluster->end - offset;
2845 	u64 cur_offset = prealloc_start;
2846 
2847 	/*
2848 	 * For subpage case, previous i_size may not be aligned to PAGE_SIZE.
2849 	 * This means the range [i_size, PAGE_END + 1) is filled with zeros by
2850 	 * btrfs_do_readpage() call of previously relocated file cluster.
2851 	 *
2852 	 * If the current cluster starts in the above range, btrfs_do_readpage()
2853 	 * will skip the read, and relocate_one_page() will later writeback
2854 	 * the padding zeros as new data, causing data corruption.
2855 	 *
2856 	 * Here we have to manually invalidate the range (i_size, PAGE_END + 1).
2857 	 */
2858 	if (!PAGE_ALIGNED(i_size)) {
2859 		struct address_space *mapping = inode->vfs_inode.i_mapping;
2860 		struct btrfs_fs_info *fs_info = inode->root->fs_info;
2861 		const u32 sectorsize = fs_info->sectorsize;
2862 		struct page *page;
2863 
2864 		ASSERT(sectorsize < PAGE_SIZE);
2865 		ASSERT(IS_ALIGNED(i_size, sectorsize));
2866 
2867 		/*
2868 		 * Subpage can't handle page with DIRTY but without UPTODATE
2869 		 * bit as it can lead to the following deadlock:
2870 		 *
2871 		 * btrfs_read_folio()
2872 		 * | Page already *locked*
2873 		 * |- btrfs_lock_and_flush_ordered_range()
2874 		 *    |- btrfs_start_ordered_extent()
2875 		 *       |- extent_write_cache_pages()
2876 		 *          |- lock_page()
2877 		 *             We try to lock the page we already hold.
2878 		 *
2879 		 * Here we just writeback the whole data reloc inode, so that
2880 		 * we will be ensured to have no dirty range in the page, and
2881 		 * are safe to clear the uptodate bits.
2882 		 *
2883 		 * This shouldn't cause too much overhead, as we need to write
2884 		 * the data back anyway.
2885 		 */
2886 		ret = filemap_write_and_wait(mapping);
2887 		if (ret < 0)
2888 			return ret;
2889 
2890 		clear_extent_bits(&inode->io_tree, i_size,
2891 				  round_up(i_size, PAGE_SIZE) - 1,
2892 				  EXTENT_UPTODATE);
2893 		page = find_lock_page(mapping, i_size >> PAGE_SHIFT);
2894 		/*
2895 		 * If page is freed we don't need to do anything then, as we
2896 		 * will re-read the whole page anyway.
2897 		 */
2898 		if (page) {
2899 			btrfs_subpage_clear_uptodate(fs_info, page_folio(page), i_size,
2900 					round_up(i_size, PAGE_SIZE) - i_size);
2901 			unlock_page(page);
2902 			put_page(page);
2903 		}
2904 	}
2905 
2906 	BUG_ON(cluster->start != cluster->boundary[0]);
2907 	ret = btrfs_alloc_data_chunk_ondemand(inode,
2908 					      prealloc_end + 1 - prealloc_start);
2909 	if (ret)
2910 		return ret;
2911 
2912 	btrfs_inode_lock(inode, 0);
2913 	for (nr = 0; nr < cluster->nr; nr++) {
2914 		struct extent_state *cached_state = NULL;
2915 
2916 		start = cluster->boundary[nr] - offset;
2917 		if (nr + 1 < cluster->nr)
2918 			end = cluster->boundary[nr + 1] - 1 - offset;
2919 		else
2920 			end = cluster->end - offset;
2921 
2922 		lock_extent(&inode->io_tree, start, end, &cached_state);
2923 		num_bytes = end + 1 - start;
2924 		ret = btrfs_prealloc_file_range(&inode->vfs_inode, 0, start,
2925 						num_bytes, num_bytes,
2926 						end + 1, &alloc_hint);
2927 		cur_offset = end + 1;
2928 		unlock_extent(&inode->io_tree, start, end, &cached_state);
2929 		if (ret)
2930 			break;
2931 	}
2932 	btrfs_inode_unlock(inode, 0);
2933 
2934 	if (cur_offset < prealloc_end)
2935 		btrfs_free_reserved_data_space_noquota(inode->root->fs_info,
2936 					       prealloc_end + 1 - cur_offset);
2937 	return ret;
2938 }
2939 
2940 static noinline_for_stack int setup_relocation_extent_mapping(struct inode *inode,
2941 				u64 start, u64 end, u64 block_start)
2942 {
2943 	struct extent_map *em;
2944 	struct extent_state *cached_state = NULL;
2945 	int ret = 0;
2946 
2947 	em = alloc_extent_map();
2948 	if (!em)
2949 		return -ENOMEM;
2950 
2951 	em->start = start;
2952 	em->len = end + 1 - start;
2953 	em->block_len = em->len;
2954 	em->block_start = block_start;
2955 	em->flags |= EXTENT_FLAG_PINNED;
2956 
2957 	lock_extent(&BTRFS_I(inode)->io_tree, start, end, &cached_state);
2958 	ret = btrfs_replace_extent_map_range(BTRFS_I(inode), em, false);
2959 	unlock_extent(&BTRFS_I(inode)->io_tree, start, end, &cached_state);
2960 	free_extent_map(em);
2961 
2962 	return ret;
2963 }
2964 
2965 /*
2966  * Allow error injection to test balance/relocation cancellation
2967  */
2968 noinline int btrfs_should_cancel_balance(const struct btrfs_fs_info *fs_info)
2969 {
2970 	return atomic_read(&fs_info->balance_cancel_req) ||
2971 		atomic_read(&fs_info->reloc_cancel_req) ||
2972 		fatal_signal_pending(current);
2973 }
2974 ALLOW_ERROR_INJECTION(btrfs_should_cancel_balance, TRUE);
2975 
2976 static u64 get_cluster_boundary_end(const struct file_extent_cluster *cluster,
2977 				    int cluster_nr)
2978 {
2979 	/* Last extent, use cluster end directly */
2980 	if (cluster_nr >= cluster->nr - 1)
2981 		return cluster->end;
2982 
2983 	/* Use next boundary start*/
2984 	return cluster->boundary[cluster_nr + 1] - 1;
2985 }
2986 
2987 static int relocate_one_page(struct inode *inode, struct file_ra_state *ra,
2988 			     const struct file_extent_cluster *cluster,
2989 			     int *cluster_nr, unsigned long page_index)
2990 {
2991 	struct btrfs_fs_info *fs_info = inode_to_fs_info(inode);
2992 	u64 offset = BTRFS_I(inode)->index_cnt;
2993 	const unsigned long last_index = (cluster->end - offset) >> PAGE_SHIFT;
2994 	gfp_t mask = btrfs_alloc_write_mask(inode->i_mapping);
2995 	struct page *page;
2996 	u64 page_start;
2997 	u64 page_end;
2998 	u64 cur;
2999 	int ret;
3000 
3001 	ASSERT(page_index <= last_index);
3002 	page = find_lock_page(inode->i_mapping, page_index);
3003 	if (!page) {
3004 		page_cache_sync_readahead(inode->i_mapping, ra, NULL,
3005 				page_index, last_index + 1 - page_index);
3006 		page = find_or_create_page(inode->i_mapping, page_index, mask);
3007 		if (!page)
3008 			return -ENOMEM;
3009 	}
3010 
3011 	if (PageReadahead(page))
3012 		page_cache_async_readahead(inode->i_mapping, ra, NULL,
3013 				page_folio(page), page_index,
3014 				last_index + 1 - page_index);
3015 
3016 	if (!PageUptodate(page)) {
3017 		btrfs_read_folio(NULL, page_folio(page));
3018 		lock_page(page);
3019 		if (!PageUptodate(page)) {
3020 			ret = -EIO;
3021 			goto release_page;
3022 		}
3023 	}
3024 
3025 	/*
3026 	 * We could have lost page private when we dropped the lock to read the
3027 	 * page above, make sure we set_page_extent_mapped here so we have any
3028 	 * of the subpage blocksize stuff we need in place.
3029 	 */
3030 	ret = set_page_extent_mapped(page);
3031 	if (ret < 0)
3032 		goto release_page;
3033 
3034 	page_start = page_offset(page);
3035 	page_end = page_start + PAGE_SIZE - 1;
3036 
3037 	/*
3038 	 * Start from the cluster, as for subpage case, the cluster can start
3039 	 * inside the page.
3040 	 */
3041 	cur = max(page_start, cluster->boundary[*cluster_nr] - offset);
3042 	while (cur <= page_end) {
3043 		struct extent_state *cached_state = NULL;
3044 		u64 extent_start = cluster->boundary[*cluster_nr] - offset;
3045 		u64 extent_end = get_cluster_boundary_end(cluster,
3046 						*cluster_nr) - offset;
3047 		u64 clamped_start = max(page_start, extent_start);
3048 		u64 clamped_end = min(page_end, extent_end);
3049 		u32 clamped_len = clamped_end + 1 - clamped_start;
3050 
3051 		/* Reserve metadata for this range */
3052 		ret = btrfs_delalloc_reserve_metadata(BTRFS_I(inode),
3053 						      clamped_len, clamped_len,
3054 						      false);
3055 		if (ret)
3056 			goto release_page;
3057 
3058 		/* Mark the range delalloc and dirty for later writeback */
3059 		lock_extent(&BTRFS_I(inode)->io_tree, clamped_start, clamped_end,
3060 			    &cached_state);
3061 		ret = btrfs_set_extent_delalloc(BTRFS_I(inode), clamped_start,
3062 						clamped_end, 0, &cached_state);
3063 		if (ret) {
3064 			clear_extent_bit(&BTRFS_I(inode)->io_tree,
3065 					 clamped_start, clamped_end,
3066 					 EXTENT_LOCKED | EXTENT_BOUNDARY,
3067 					 &cached_state);
3068 			btrfs_delalloc_release_metadata(BTRFS_I(inode),
3069 							clamped_len, true);
3070 			btrfs_delalloc_release_extents(BTRFS_I(inode),
3071 						       clamped_len);
3072 			goto release_page;
3073 		}
3074 		btrfs_folio_set_dirty(fs_info, page_folio(page),
3075 				      clamped_start, clamped_len);
3076 
3077 		/*
3078 		 * Set the boundary if it's inside the page.
3079 		 * Data relocation requires the destination extents to have the
3080 		 * same size as the source.
3081 		 * EXTENT_BOUNDARY bit prevents current extent from being merged
3082 		 * with previous extent.
3083 		 */
3084 		if (in_range(cluster->boundary[*cluster_nr] - offset,
3085 			     page_start, PAGE_SIZE)) {
3086 			u64 boundary_start = cluster->boundary[*cluster_nr] -
3087 						offset;
3088 			u64 boundary_end = boundary_start +
3089 					   fs_info->sectorsize - 1;
3090 
3091 			set_extent_bit(&BTRFS_I(inode)->io_tree,
3092 				       boundary_start, boundary_end,
3093 				       EXTENT_BOUNDARY, NULL);
3094 		}
3095 		unlock_extent(&BTRFS_I(inode)->io_tree, clamped_start, clamped_end,
3096 			      &cached_state);
3097 		btrfs_delalloc_release_extents(BTRFS_I(inode), clamped_len);
3098 		cur += clamped_len;
3099 
3100 		/* Crossed extent end, go to next extent */
3101 		if (cur >= extent_end) {
3102 			(*cluster_nr)++;
3103 			/* Just finished the last extent of the cluster, exit. */
3104 			if (*cluster_nr >= cluster->nr)
3105 				break;
3106 		}
3107 	}
3108 	unlock_page(page);
3109 	put_page(page);
3110 
3111 	balance_dirty_pages_ratelimited(inode->i_mapping);
3112 	btrfs_throttle(fs_info);
3113 	if (btrfs_should_cancel_balance(fs_info))
3114 		ret = -ECANCELED;
3115 	return ret;
3116 
3117 release_page:
3118 	unlock_page(page);
3119 	put_page(page);
3120 	return ret;
3121 }
3122 
3123 static int relocate_file_extent_cluster(struct inode *inode,
3124 					const struct file_extent_cluster *cluster)
3125 {
3126 	u64 offset = BTRFS_I(inode)->index_cnt;
3127 	unsigned long index;
3128 	unsigned long last_index;
3129 	struct file_ra_state *ra;
3130 	int cluster_nr = 0;
3131 	int ret = 0;
3132 
3133 	if (!cluster->nr)
3134 		return 0;
3135 
3136 	ra = kzalloc(sizeof(*ra), GFP_NOFS);
3137 	if (!ra)
3138 		return -ENOMEM;
3139 
3140 	ret = prealloc_file_extent_cluster(BTRFS_I(inode), cluster);
3141 	if (ret)
3142 		goto out;
3143 
3144 	file_ra_state_init(ra, inode->i_mapping);
3145 
3146 	ret = setup_relocation_extent_mapping(inode, cluster->start - offset,
3147 				   cluster->end - offset, cluster->start);
3148 	if (ret)
3149 		goto out;
3150 
3151 	last_index = (cluster->end - offset) >> PAGE_SHIFT;
3152 	for (index = (cluster->start - offset) >> PAGE_SHIFT;
3153 	     index <= last_index && !ret; index++)
3154 		ret = relocate_one_page(inode, ra, cluster, &cluster_nr, index);
3155 	if (ret == 0)
3156 		WARN_ON(cluster_nr != cluster->nr);
3157 out:
3158 	kfree(ra);
3159 	return ret;
3160 }
3161 
3162 static noinline_for_stack int relocate_data_extent(struct inode *inode,
3163 				const struct btrfs_key *extent_key,
3164 				struct file_extent_cluster *cluster)
3165 {
3166 	int ret;
3167 	struct btrfs_root *root = BTRFS_I(inode)->root;
3168 
3169 	if (cluster->nr > 0 && extent_key->objectid != cluster->end + 1) {
3170 		ret = relocate_file_extent_cluster(inode, cluster);
3171 		if (ret)
3172 			return ret;
3173 		cluster->nr = 0;
3174 	}
3175 
3176 	/*
3177 	 * Under simple quotas, we set root->relocation_src_root when we find
3178 	 * the extent. If adjacent extents have different owners, we can't merge
3179 	 * them while relocating. Handle this by storing the owning root that
3180 	 * started a cluster and if we see an extent from a different root break
3181 	 * cluster formation (just like the above case of non-adjacent extents).
3182 	 *
3183 	 * Without simple quotas, relocation_src_root is always 0, so we should
3184 	 * never see a mismatch, and it should have no effect on relocation
3185 	 * clusters.
3186 	 */
3187 	if (cluster->nr > 0 && cluster->owning_root != root->relocation_src_root) {
3188 		u64 tmp = root->relocation_src_root;
3189 
3190 		/*
3191 		 * root->relocation_src_root is the state that actually affects
3192 		 * the preallocation we do here, so set it to the root owning
3193 		 * the cluster we need to relocate.
3194 		 */
3195 		root->relocation_src_root = cluster->owning_root;
3196 		ret = relocate_file_extent_cluster(inode, cluster);
3197 		if (ret)
3198 			return ret;
3199 		cluster->nr = 0;
3200 		/* And reset it back for the current extent's owning root. */
3201 		root->relocation_src_root = tmp;
3202 	}
3203 
3204 	if (!cluster->nr) {
3205 		cluster->start = extent_key->objectid;
3206 		cluster->owning_root = root->relocation_src_root;
3207 	}
3208 	else
3209 		BUG_ON(cluster->nr >= MAX_EXTENTS);
3210 	cluster->end = extent_key->objectid + extent_key->offset - 1;
3211 	cluster->boundary[cluster->nr] = extent_key->objectid;
3212 	cluster->nr++;
3213 
3214 	if (cluster->nr >= MAX_EXTENTS) {
3215 		ret = relocate_file_extent_cluster(inode, cluster);
3216 		if (ret)
3217 			return ret;
3218 		cluster->nr = 0;
3219 	}
3220 	return 0;
3221 }
3222 
3223 /*
3224  * helper to add a tree block to the list.
3225  * the major work is getting the generation and level of the block
3226  */
3227 static int add_tree_block(struct reloc_control *rc,
3228 			  const struct btrfs_key *extent_key,
3229 			  struct btrfs_path *path,
3230 			  struct rb_root *blocks)
3231 {
3232 	struct extent_buffer *eb;
3233 	struct btrfs_extent_item *ei;
3234 	struct btrfs_tree_block_info *bi;
3235 	struct tree_block *block;
3236 	struct rb_node *rb_node;
3237 	u32 item_size;
3238 	int level = -1;
3239 	u64 generation;
3240 	u64 owner = 0;
3241 
3242 	eb =  path->nodes[0];
3243 	item_size = btrfs_item_size(eb, path->slots[0]);
3244 
3245 	if (extent_key->type == BTRFS_METADATA_ITEM_KEY ||
3246 	    item_size >= sizeof(*ei) + sizeof(*bi)) {
3247 		unsigned long ptr = 0, end;
3248 
3249 		ei = btrfs_item_ptr(eb, path->slots[0],
3250 				struct btrfs_extent_item);
3251 		end = (unsigned long)ei + item_size;
3252 		if (extent_key->type == BTRFS_EXTENT_ITEM_KEY) {
3253 			bi = (struct btrfs_tree_block_info *)(ei + 1);
3254 			level = btrfs_tree_block_level(eb, bi);
3255 			ptr = (unsigned long)(bi + 1);
3256 		} else {
3257 			level = (int)extent_key->offset;
3258 			ptr = (unsigned long)(ei + 1);
3259 		}
3260 		generation = btrfs_extent_generation(eb, ei);
3261 
3262 		/*
3263 		 * We're reading random blocks without knowing their owner ahead
3264 		 * of time.  This is ok most of the time, as all reloc roots and
3265 		 * fs roots have the same lock type.  However normal trees do
3266 		 * not, and the only way to know ahead of time is to read the
3267 		 * inline ref offset.  We know it's an fs root if
3268 		 *
3269 		 * 1. There's more than one ref.
3270 		 * 2. There's a SHARED_DATA_REF_KEY set.
3271 		 * 3. FULL_BACKREF is set on the flags.
3272 		 *
3273 		 * Otherwise it's safe to assume that the ref offset == the
3274 		 * owner of this block, so we can use that when calling
3275 		 * read_tree_block.
3276 		 */
3277 		if (btrfs_extent_refs(eb, ei) == 1 &&
3278 		    !(btrfs_extent_flags(eb, ei) &
3279 		      BTRFS_BLOCK_FLAG_FULL_BACKREF) &&
3280 		    ptr < end) {
3281 			struct btrfs_extent_inline_ref *iref;
3282 			int type;
3283 
3284 			iref = (struct btrfs_extent_inline_ref *)ptr;
3285 			type = btrfs_get_extent_inline_ref_type(eb, iref,
3286 							BTRFS_REF_TYPE_BLOCK);
3287 			if (type == BTRFS_REF_TYPE_INVALID)
3288 				return -EINVAL;
3289 			if (type == BTRFS_TREE_BLOCK_REF_KEY)
3290 				owner = btrfs_extent_inline_ref_offset(eb, iref);
3291 		}
3292 	} else {
3293 		btrfs_print_leaf(eb);
3294 		btrfs_err(rc->block_group->fs_info,
3295 			  "unrecognized tree backref at tree block %llu slot %u",
3296 			  eb->start, path->slots[0]);
3297 		btrfs_release_path(path);
3298 		return -EUCLEAN;
3299 	}
3300 
3301 	btrfs_release_path(path);
3302 
3303 	BUG_ON(level == -1);
3304 
3305 	block = kmalloc(sizeof(*block), GFP_NOFS);
3306 	if (!block)
3307 		return -ENOMEM;
3308 
3309 	block->bytenr = extent_key->objectid;
3310 	block->key.objectid = rc->extent_root->fs_info->nodesize;
3311 	block->key.offset = generation;
3312 	block->level = level;
3313 	block->key_ready = false;
3314 	block->owner = owner;
3315 
3316 	rb_node = rb_simple_insert(blocks, block->bytenr, &block->rb_node);
3317 	if (rb_node)
3318 		btrfs_backref_panic(rc->extent_root->fs_info, block->bytenr,
3319 				    -EEXIST);
3320 
3321 	return 0;
3322 }
3323 
3324 /*
3325  * helper to add tree blocks for backref of type BTRFS_SHARED_DATA_REF_KEY
3326  */
3327 static int __add_tree_block(struct reloc_control *rc,
3328 			    u64 bytenr, u32 blocksize,
3329 			    struct rb_root *blocks)
3330 {
3331 	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
3332 	struct btrfs_path *path;
3333 	struct btrfs_key key;
3334 	int ret;
3335 	bool skinny = btrfs_fs_incompat(fs_info, SKINNY_METADATA);
3336 
3337 	if (tree_block_processed(bytenr, rc))
3338 		return 0;
3339 
3340 	if (rb_simple_search(blocks, bytenr))
3341 		return 0;
3342 
3343 	path = btrfs_alloc_path();
3344 	if (!path)
3345 		return -ENOMEM;
3346 again:
3347 	key.objectid = bytenr;
3348 	if (skinny) {
3349 		key.type = BTRFS_METADATA_ITEM_KEY;
3350 		key.offset = (u64)-1;
3351 	} else {
3352 		key.type = BTRFS_EXTENT_ITEM_KEY;
3353 		key.offset = blocksize;
3354 	}
3355 
3356 	path->search_commit_root = 1;
3357 	path->skip_locking = 1;
3358 	ret = btrfs_search_slot(NULL, rc->extent_root, &key, path, 0, 0);
3359 	if (ret < 0)
3360 		goto out;
3361 
3362 	if (ret > 0 && skinny) {
3363 		if (path->slots[0]) {
3364 			path->slots[0]--;
3365 			btrfs_item_key_to_cpu(path->nodes[0], &key,
3366 					      path->slots[0]);
3367 			if (key.objectid == bytenr &&
3368 			    (key.type == BTRFS_METADATA_ITEM_KEY ||
3369 			     (key.type == BTRFS_EXTENT_ITEM_KEY &&
3370 			      key.offset == blocksize)))
3371 				ret = 0;
3372 		}
3373 
3374 		if (ret) {
3375 			skinny = false;
3376 			btrfs_release_path(path);
3377 			goto again;
3378 		}
3379 	}
3380 	if (ret) {
3381 		ASSERT(ret == 1);
3382 		btrfs_print_leaf(path->nodes[0]);
3383 		btrfs_err(fs_info,
3384 	     "tree block extent item (%llu) is not found in extent tree",
3385 		     bytenr);
3386 		WARN_ON(1);
3387 		ret = -EINVAL;
3388 		goto out;
3389 	}
3390 
3391 	ret = add_tree_block(rc, &key, path, blocks);
3392 out:
3393 	btrfs_free_path(path);
3394 	return ret;
3395 }
3396 
3397 static int delete_block_group_cache(struct btrfs_fs_info *fs_info,
3398 				    struct btrfs_block_group *block_group,
3399 				    struct inode *inode,
3400 				    u64 ino)
3401 {
3402 	struct btrfs_root *root = fs_info->tree_root;
3403 	struct btrfs_trans_handle *trans;
3404 	int ret = 0;
3405 
3406 	if (inode)
3407 		goto truncate;
3408 
3409 	inode = btrfs_iget(fs_info->sb, ino, root);
3410 	if (IS_ERR(inode))
3411 		return -ENOENT;
3412 
3413 truncate:
3414 	ret = btrfs_check_trunc_cache_free_space(fs_info,
3415 						 &fs_info->global_block_rsv);
3416 	if (ret)
3417 		goto out;
3418 
3419 	trans = btrfs_join_transaction(root);
3420 	if (IS_ERR(trans)) {
3421 		ret = PTR_ERR(trans);
3422 		goto out;
3423 	}
3424 
3425 	ret = btrfs_truncate_free_space_cache(trans, block_group, inode);
3426 
3427 	btrfs_end_transaction(trans);
3428 	btrfs_btree_balance_dirty(fs_info);
3429 out:
3430 	iput(inode);
3431 	return ret;
3432 }
3433 
3434 /*
3435  * Locate the free space cache EXTENT_DATA in root tree leaf and delete the
3436  * cache inode, to avoid free space cache data extent blocking data relocation.
3437  */
3438 static int delete_v1_space_cache(struct extent_buffer *leaf,
3439 				 struct btrfs_block_group *block_group,
3440 				 u64 data_bytenr)
3441 {
3442 	u64 space_cache_ino;
3443 	struct btrfs_file_extent_item *ei;
3444 	struct btrfs_key key;
3445 	bool found = false;
3446 	int i;
3447 	int ret;
3448 
3449 	if (btrfs_header_owner(leaf) != BTRFS_ROOT_TREE_OBJECTID)
3450 		return 0;
3451 
3452 	for (i = 0; i < btrfs_header_nritems(leaf); i++) {
3453 		u8 type;
3454 
3455 		btrfs_item_key_to_cpu(leaf, &key, i);
3456 		if (key.type != BTRFS_EXTENT_DATA_KEY)
3457 			continue;
3458 		ei = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
3459 		type = btrfs_file_extent_type(leaf, ei);
3460 
3461 		if ((type == BTRFS_FILE_EXTENT_REG ||
3462 		     type == BTRFS_FILE_EXTENT_PREALLOC) &&
3463 		    btrfs_file_extent_disk_bytenr(leaf, ei) == data_bytenr) {
3464 			found = true;
3465 			space_cache_ino = key.objectid;
3466 			break;
3467 		}
3468 	}
3469 	if (!found)
3470 		return -ENOENT;
3471 	ret = delete_block_group_cache(leaf->fs_info, block_group, NULL,
3472 					space_cache_ino);
3473 	return ret;
3474 }
3475 
3476 /*
3477  * helper to find all tree blocks that reference a given data extent
3478  */
3479 static noinline_for_stack int add_data_references(struct reloc_control *rc,
3480 						  const struct btrfs_key *extent_key,
3481 						  struct btrfs_path *path,
3482 						  struct rb_root *blocks)
3483 {
3484 	struct btrfs_backref_walk_ctx ctx = { 0 };
3485 	struct ulist_iterator leaf_uiter;
3486 	struct ulist_node *ref_node = NULL;
3487 	const u32 blocksize = rc->extent_root->fs_info->nodesize;
3488 	int ret = 0;
3489 
3490 	btrfs_release_path(path);
3491 
3492 	ctx.bytenr = extent_key->objectid;
3493 	ctx.skip_inode_ref_list = true;
3494 	ctx.fs_info = rc->extent_root->fs_info;
3495 
3496 	ret = btrfs_find_all_leafs(&ctx);
3497 	if (ret < 0)
3498 		return ret;
3499 
3500 	ULIST_ITER_INIT(&leaf_uiter);
3501 	while ((ref_node = ulist_next(ctx.refs, &leaf_uiter))) {
3502 		struct btrfs_tree_parent_check check = { 0 };
3503 		struct extent_buffer *eb;
3504 
3505 		eb = read_tree_block(ctx.fs_info, ref_node->val, &check);
3506 		if (IS_ERR(eb)) {
3507 			ret = PTR_ERR(eb);
3508 			break;
3509 		}
3510 		ret = delete_v1_space_cache(eb, rc->block_group,
3511 					    extent_key->objectid);
3512 		free_extent_buffer(eb);
3513 		if (ret < 0)
3514 			break;
3515 		ret = __add_tree_block(rc, ref_node->val, blocksize, blocks);
3516 		if (ret < 0)
3517 			break;
3518 	}
3519 	if (ret < 0)
3520 		free_block_list(blocks);
3521 	ulist_free(ctx.refs);
3522 	return ret;
3523 }
3524 
3525 /*
3526  * helper to find next unprocessed extent
3527  */
3528 static noinline_for_stack
3529 int find_next_extent(struct reloc_control *rc, struct btrfs_path *path,
3530 		     struct btrfs_key *extent_key)
3531 {
3532 	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
3533 	struct btrfs_key key;
3534 	struct extent_buffer *leaf;
3535 	u64 start, end, last;
3536 	int ret;
3537 
3538 	last = rc->block_group->start + rc->block_group->length;
3539 	while (1) {
3540 		bool block_found;
3541 
3542 		cond_resched();
3543 		if (rc->search_start >= last) {
3544 			ret = 1;
3545 			break;
3546 		}
3547 
3548 		key.objectid = rc->search_start;
3549 		key.type = BTRFS_EXTENT_ITEM_KEY;
3550 		key.offset = 0;
3551 
3552 		path->search_commit_root = 1;
3553 		path->skip_locking = 1;
3554 		ret = btrfs_search_slot(NULL, rc->extent_root, &key, path,
3555 					0, 0);
3556 		if (ret < 0)
3557 			break;
3558 next:
3559 		leaf = path->nodes[0];
3560 		if (path->slots[0] >= btrfs_header_nritems(leaf)) {
3561 			ret = btrfs_next_leaf(rc->extent_root, path);
3562 			if (ret != 0)
3563 				break;
3564 			leaf = path->nodes[0];
3565 		}
3566 
3567 		btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
3568 		if (key.objectid >= last) {
3569 			ret = 1;
3570 			break;
3571 		}
3572 
3573 		if (key.type != BTRFS_EXTENT_ITEM_KEY &&
3574 		    key.type != BTRFS_METADATA_ITEM_KEY) {
3575 			path->slots[0]++;
3576 			goto next;
3577 		}
3578 
3579 		if (key.type == BTRFS_EXTENT_ITEM_KEY &&
3580 		    key.objectid + key.offset <= rc->search_start) {
3581 			path->slots[0]++;
3582 			goto next;
3583 		}
3584 
3585 		if (key.type == BTRFS_METADATA_ITEM_KEY &&
3586 		    key.objectid + fs_info->nodesize <=
3587 		    rc->search_start) {
3588 			path->slots[0]++;
3589 			goto next;
3590 		}
3591 
3592 		block_found = find_first_extent_bit(&rc->processed_blocks,
3593 						    key.objectid, &start, &end,
3594 						    EXTENT_DIRTY, NULL);
3595 
3596 		if (block_found && start <= key.objectid) {
3597 			btrfs_release_path(path);
3598 			rc->search_start = end + 1;
3599 		} else {
3600 			if (key.type == BTRFS_EXTENT_ITEM_KEY)
3601 				rc->search_start = key.objectid + key.offset;
3602 			else
3603 				rc->search_start = key.objectid +
3604 					fs_info->nodesize;
3605 			memcpy(extent_key, &key, sizeof(key));
3606 			return 0;
3607 		}
3608 	}
3609 	btrfs_release_path(path);
3610 	return ret;
3611 }
3612 
3613 static void set_reloc_control(struct reloc_control *rc)
3614 {
3615 	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
3616 
3617 	mutex_lock(&fs_info->reloc_mutex);
3618 	fs_info->reloc_ctl = rc;
3619 	mutex_unlock(&fs_info->reloc_mutex);
3620 }
3621 
3622 static void unset_reloc_control(struct reloc_control *rc)
3623 {
3624 	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
3625 
3626 	mutex_lock(&fs_info->reloc_mutex);
3627 	fs_info->reloc_ctl = NULL;
3628 	mutex_unlock(&fs_info->reloc_mutex);
3629 }
3630 
3631 static noinline_for_stack
3632 int prepare_to_relocate(struct reloc_control *rc)
3633 {
3634 	struct btrfs_trans_handle *trans;
3635 	int ret;
3636 
3637 	rc->block_rsv = btrfs_alloc_block_rsv(rc->extent_root->fs_info,
3638 					      BTRFS_BLOCK_RSV_TEMP);
3639 	if (!rc->block_rsv)
3640 		return -ENOMEM;
3641 
3642 	memset(&rc->cluster, 0, sizeof(rc->cluster));
3643 	rc->search_start = rc->block_group->start;
3644 	rc->extents_found = 0;
3645 	rc->nodes_relocated = 0;
3646 	rc->merging_rsv_size = 0;
3647 	rc->reserved_bytes = 0;
3648 	rc->block_rsv->size = rc->extent_root->fs_info->nodesize *
3649 			      RELOCATION_RESERVED_NODES;
3650 	ret = btrfs_block_rsv_refill(rc->extent_root->fs_info,
3651 				     rc->block_rsv, rc->block_rsv->size,
3652 				     BTRFS_RESERVE_FLUSH_ALL);
3653 	if (ret)
3654 		return ret;
3655 
3656 	rc->create_reloc_tree = true;
3657 	set_reloc_control(rc);
3658 
3659 	trans = btrfs_join_transaction(rc->extent_root);
3660 	if (IS_ERR(trans)) {
3661 		unset_reloc_control(rc);
3662 		/*
3663 		 * extent tree is not a ref_cow tree and has no reloc_root to
3664 		 * cleanup.  And callers are responsible to free the above
3665 		 * block rsv.
3666 		 */
3667 		return PTR_ERR(trans);
3668 	}
3669 
3670 	ret = btrfs_commit_transaction(trans);
3671 	if (ret)
3672 		unset_reloc_control(rc);
3673 
3674 	return ret;
3675 }
3676 
3677 static noinline_for_stack int relocate_block_group(struct reloc_control *rc)
3678 {
3679 	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
3680 	struct rb_root blocks = RB_ROOT;
3681 	struct btrfs_key key;
3682 	struct btrfs_trans_handle *trans = NULL;
3683 	struct btrfs_path *path;
3684 	struct btrfs_extent_item *ei;
3685 	u64 flags;
3686 	int ret;
3687 	int err = 0;
3688 	int progress = 0;
3689 
3690 	path = btrfs_alloc_path();
3691 	if (!path)
3692 		return -ENOMEM;
3693 	path->reada = READA_FORWARD;
3694 
3695 	ret = prepare_to_relocate(rc);
3696 	if (ret) {
3697 		err = ret;
3698 		goto out_free;
3699 	}
3700 
3701 	while (1) {
3702 		rc->reserved_bytes = 0;
3703 		ret = btrfs_block_rsv_refill(fs_info, rc->block_rsv,
3704 					     rc->block_rsv->size,
3705 					     BTRFS_RESERVE_FLUSH_ALL);
3706 		if (ret) {
3707 			err = ret;
3708 			break;
3709 		}
3710 		progress++;
3711 		trans = btrfs_start_transaction(rc->extent_root, 0);
3712 		if (IS_ERR(trans)) {
3713 			err = PTR_ERR(trans);
3714 			trans = NULL;
3715 			break;
3716 		}
3717 restart:
3718 		if (update_backref_cache(trans, &rc->backref_cache)) {
3719 			btrfs_end_transaction(trans);
3720 			trans = NULL;
3721 			continue;
3722 		}
3723 
3724 		ret = find_next_extent(rc, path, &key);
3725 		if (ret < 0)
3726 			err = ret;
3727 		if (ret != 0)
3728 			break;
3729 
3730 		rc->extents_found++;
3731 
3732 		ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
3733 				    struct btrfs_extent_item);
3734 		flags = btrfs_extent_flags(path->nodes[0], ei);
3735 
3736 		/*
3737 		 * If we are relocating a simple quota owned extent item, we
3738 		 * need to note the owner on the reloc data root so that when
3739 		 * we allocate the replacement item, we can attribute it to the
3740 		 * correct eventual owner (rather than the reloc data root).
3741 		 */
3742 		if (btrfs_qgroup_mode(fs_info) == BTRFS_QGROUP_MODE_SIMPLE) {
3743 			struct btrfs_root *root = BTRFS_I(rc->data_inode)->root;
3744 			u64 owning_root_id = btrfs_get_extent_owner_root(fs_info,
3745 								 path->nodes[0],
3746 								 path->slots[0]);
3747 
3748 			root->relocation_src_root = owning_root_id;
3749 		}
3750 
3751 		if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
3752 			ret = add_tree_block(rc, &key, path, &blocks);
3753 		} else if (rc->stage == UPDATE_DATA_PTRS &&
3754 			   (flags & BTRFS_EXTENT_FLAG_DATA)) {
3755 			ret = add_data_references(rc, &key, path, &blocks);
3756 		} else {
3757 			btrfs_release_path(path);
3758 			ret = 0;
3759 		}
3760 		if (ret < 0) {
3761 			err = ret;
3762 			break;
3763 		}
3764 
3765 		if (!RB_EMPTY_ROOT(&blocks)) {
3766 			ret = relocate_tree_blocks(trans, rc, &blocks);
3767 			if (ret < 0) {
3768 				if (ret != -EAGAIN) {
3769 					err = ret;
3770 					break;
3771 				}
3772 				rc->extents_found--;
3773 				rc->search_start = key.objectid;
3774 			}
3775 		}
3776 
3777 		btrfs_end_transaction_throttle(trans);
3778 		btrfs_btree_balance_dirty(fs_info);
3779 		trans = NULL;
3780 
3781 		if (rc->stage == MOVE_DATA_EXTENTS &&
3782 		    (flags & BTRFS_EXTENT_FLAG_DATA)) {
3783 			rc->found_file_extent = true;
3784 			ret = relocate_data_extent(rc->data_inode,
3785 						   &key, &rc->cluster);
3786 			if (ret < 0) {
3787 				err = ret;
3788 				break;
3789 			}
3790 		}
3791 		if (btrfs_should_cancel_balance(fs_info)) {
3792 			err = -ECANCELED;
3793 			break;
3794 		}
3795 	}
3796 	if (trans && progress && err == -ENOSPC) {
3797 		ret = btrfs_force_chunk_alloc(trans, rc->block_group->flags);
3798 		if (ret == 1) {
3799 			err = 0;
3800 			progress = 0;
3801 			goto restart;
3802 		}
3803 	}
3804 
3805 	btrfs_release_path(path);
3806 	clear_extent_bits(&rc->processed_blocks, 0, (u64)-1, EXTENT_DIRTY);
3807 
3808 	if (trans) {
3809 		btrfs_end_transaction_throttle(trans);
3810 		btrfs_btree_balance_dirty(fs_info);
3811 	}
3812 
3813 	if (!err) {
3814 		ret = relocate_file_extent_cluster(rc->data_inode,
3815 						   &rc->cluster);
3816 		if (ret < 0)
3817 			err = ret;
3818 	}
3819 
3820 	rc->create_reloc_tree = false;
3821 	set_reloc_control(rc);
3822 
3823 	btrfs_backref_release_cache(&rc->backref_cache);
3824 	btrfs_block_rsv_release(fs_info, rc->block_rsv, (u64)-1, NULL);
3825 
3826 	/*
3827 	 * Even in the case when the relocation is cancelled, we should all go
3828 	 * through prepare_to_merge() and merge_reloc_roots().
3829 	 *
3830 	 * For error (including cancelled balance), prepare_to_merge() will
3831 	 * mark all reloc trees orphan, then queue them for cleanup in
3832 	 * merge_reloc_roots()
3833 	 */
3834 	err = prepare_to_merge(rc, err);
3835 
3836 	merge_reloc_roots(rc);
3837 
3838 	rc->merge_reloc_tree = false;
3839 	unset_reloc_control(rc);
3840 	btrfs_block_rsv_release(fs_info, rc->block_rsv, (u64)-1, NULL);
3841 
3842 	/* get rid of pinned extents */
3843 	trans = btrfs_join_transaction(rc->extent_root);
3844 	if (IS_ERR(trans)) {
3845 		err = PTR_ERR(trans);
3846 		goto out_free;
3847 	}
3848 	ret = btrfs_commit_transaction(trans);
3849 	if (ret && !err)
3850 		err = ret;
3851 out_free:
3852 	ret = clean_dirty_subvols(rc);
3853 	if (ret < 0 && !err)
3854 		err = ret;
3855 	btrfs_free_block_rsv(fs_info, rc->block_rsv);
3856 	btrfs_free_path(path);
3857 	return err;
3858 }
3859 
3860 static int __insert_orphan_inode(struct btrfs_trans_handle *trans,
3861 				 struct btrfs_root *root, u64 objectid)
3862 {
3863 	struct btrfs_path *path;
3864 	struct btrfs_inode_item *item;
3865 	struct extent_buffer *leaf;
3866 	int ret;
3867 
3868 	path = btrfs_alloc_path();
3869 	if (!path)
3870 		return -ENOMEM;
3871 
3872 	ret = btrfs_insert_empty_inode(trans, root, path, objectid);
3873 	if (ret)
3874 		goto out;
3875 
3876 	leaf = path->nodes[0];
3877 	item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_inode_item);
3878 	memzero_extent_buffer(leaf, (unsigned long)item, sizeof(*item));
3879 	btrfs_set_inode_generation(leaf, item, 1);
3880 	btrfs_set_inode_size(leaf, item, 0);
3881 	btrfs_set_inode_mode(leaf, item, S_IFREG | 0600);
3882 	btrfs_set_inode_flags(leaf, item, BTRFS_INODE_NOCOMPRESS |
3883 					  BTRFS_INODE_PREALLOC);
3884 	btrfs_mark_buffer_dirty(trans, leaf);
3885 out:
3886 	btrfs_free_path(path);
3887 	return ret;
3888 }
3889 
3890 static void delete_orphan_inode(struct btrfs_trans_handle *trans,
3891 				struct btrfs_root *root, u64 objectid)
3892 {
3893 	struct btrfs_path *path;
3894 	struct btrfs_key key;
3895 	int ret = 0;
3896 
3897 	path = btrfs_alloc_path();
3898 	if (!path) {
3899 		ret = -ENOMEM;
3900 		goto out;
3901 	}
3902 
3903 	key.objectid = objectid;
3904 	key.type = BTRFS_INODE_ITEM_KEY;
3905 	key.offset = 0;
3906 	ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
3907 	if (ret) {
3908 		if (ret > 0)
3909 			ret = -ENOENT;
3910 		goto out;
3911 	}
3912 	ret = btrfs_del_item(trans, root, path);
3913 out:
3914 	if (ret)
3915 		btrfs_abort_transaction(trans, ret);
3916 	btrfs_free_path(path);
3917 }
3918 
3919 /*
3920  * helper to create inode for data relocation.
3921  * the inode is in data relocation tree and its link count is 0
3922  */
3923 static noinline_for_stack struct inode *create_reloc_inode(
3924 					struct btrfs_fs_info *fs_info,
3925 					const struct btrfs_block_group *group)
3926 {
3927 	struct inode *inode = NULL;
3928 	struct btrfs_trans_handle *trans;
3929 	struct btrfs_root *root;
3930 	u64 objectid;
3931 	int err = 0;
3932 
3933 	root = btrfs_grab_root(fs_info->data_reloc_root);
3934 	trans = btrfs_start_transaction(root, 6);
3935 	if (IS_ERR(trans)) {
3936 		btrfs_put_root(root);
3937 		return ERR_CAST(trans);
3938 	}
3939 
3940 	err = btrfs_get_free_objectid(root, &objectid);
3941 	if (err)
3942 		goto out;
3943 
3944 	err = __insert_orphan_inode(trans, root, objectid);
3945 	if (err)
3946 		goto out;
3947 
3948 	inode = btrfs_iget(fs_info->sb, objectid, root);
3949 	if (IS_ERR(inode)) {
3950 		delete_orphan_inode(trans, root, objectid);
3951 		err = PTR_ERR(inode);
3952 		inode = NULL;
3953 		goto out;
3954 	}
3955 	BTRFS_I(inode)->index_cnt = group->start;
3956 
3957 	err = btrfs_orphan_add(trans, BTRFS_I(inode));
3958 out:
3959 	btrfs_put_root(root);
3960 	btrfs_end_transaction(trans);
3961 	btrfs_btree_balance_dirty(fs_info);
3962 	if (err) {
3963 		iput(inode);
3964 		inode = ERR_PTR(err);
3965 	}
3966 	return inode;
3967 }
3968 
3969 /*
3970  * Mark start of chunk relocation that is cancellable. Check if the cancellation
3971  * has been requested meanwhile and don't start in that case.
3972  *
3973  * Return:
3974  *   0             success
3975  *   -EINPROGRESS  operation is already in progress, that's probably a bug
3976  *   -ECANCELED    cancellation request was set before the operation started
3977  */
3978 static int reloc_chunk_start(struct btrfs_fs_info *fs_info)
3979 {
3980 	if (test_and_set_bit(BTRFS_FS_RELOC_RUNNING, &fs_info->flags)) {
3981 		/* This should not happen */
3982 		btrfs_err(fs_info, "reloc already running, cannot start");
3983 		return -EINPROGRESS;
3984 	}
3985 
3986 	if (atomic_read(&fs_info->reloc_cancel_req) > 0) {
3987 		btrfs_info(fs_info, "chunk relocation canceled on start");
3988 		/*
3989 		 * On cancel, clear all requests but let the caller mark
3990 		 * the end after cleanup operations.
3991 		 */
3992 		atomic_set(&fs_info->reloc_cancel_req, 0);
3993 		return -ECANCELED;
3994 	}
3995 	return 0;
3996 }
3997 
3998 /*
3999  * Mark end of chunk relocation that is cancellable and wake any waiters.
4000  */
4001 static void reloc_chunk_end(struct btrfs_fs_info *fs_info)
4002 {
4003 	/* Requested after start, clear bit first so any waiters can continue */
4004 	if (atomic_read(&fs_info->reloc_cancel_req) > 0)
4005 		btrfs_info(fs_info, "chunk relocation canceled during operation");
4006 	clear_and_wake_up_bit(BTRFS_FS_RELOC_RUNNING, &fs_info->flags);
4007 	atomic_set(&fs_info->reloc_cancel_req, 0);
4008 }
4009 
4010 static struct reloc_control *alloc_reloc_control(struct btrfs_fs_info *fs_info)
4011 {
4012 	struct reloc_control *rc;
4013 
4014 	rc = kzalloc(sizeof(*rc), GFP_NOFS);
4015 	if (!rc)
4016 		return NULL;
4017 
4018 	INIT_LIST_HEAD(&rc->reloc_roots);
4019 	INIT_LIST_HEAD(&rc->dirty_subvol_roots);
4020 	btrfs_backref_init_cache(fs_info, &rc->backref_cache, true);
4021 	rc->reloc_root_tree.rb_root = RB_ROOT;
4022 	spin_lock_init(&rc->reloc_root_tree.lock);
4023 	extent_io_tree_init(fs_info, &rc->processed_blocks, IO_TREE_RELOC_BLOCKS);
4024 	return rc;
4025 }
4026 
4027 static void free_reloc_control(struct reloc_control *rc)
4028 {
4029 	struct mapping_node *node, *tmp;
4030 
4031 	free_reloc_roots(&rc->reloc_roots);
4032 	rbtree_postorder_for_each_entry_safe(node, tmp,
4033 			&rc->reloc_root_tree.rb_root, rb_node)
4034 		kfree(node);
4035 
4036 	kfree(rc);
4037 }
4038 
4039 /*
4040  * Print the block group being relocated
4041  */
4042 static void describe_relocation(struct btrfs_fs_info *fs_info,
4043 				struct btrfs_block_group *block_group)
4044 {
4045 	char buf[128] = {'\0'};
4046 
4047 	btrfs_describe_block_groups(block_group->flags, buf, sizeof(buf));
4048 
4049 	btrfs_info(fs_info,
4050 		   "relocating block group %llu flags %s",
4051 		   block_group->start, buf);
4052 }
4053 
4054 static const char *stage_to_string(enum reloc_stage stage)
4055 {
4056 	if (stage == MOVE_DATA_EXTENTS)
4057 		return "move data extents";
4058 	if (stage == UPDATE_DATA_PTRS)
4059 		return "update data pointers";
4060 	return "unknown";
4061 }
4062 
4063 /*
4064  * function to relocate all extents in a block group.
4065  */
4066 int btrfs_relocate_block_group(struct btrfs_fs_info *fs_info, u64 group_start)
4067 {
4068 	struct btrfs_block_group *bg;
4069 	struct btrfs_root *extent_root = btrfs_extent_root(fs_info, group_start);
4070 	struct reloc_control *rc;
4071 	struct inode *inode;
4072 	struct btrfs_path *path;
4073 	int ret;
4074 	int rw = 0;
4075 	int err = 0;
4076 
4077 	/*
4078 	 * This only gets set if we had a half-deleted snapshot on mount.  We
4079 	 * cannot allow relocation to start while we're still trying to clean up
4080 	 * these pending deletions.
4081 	 */
4082 	ret = wait_on_bit(&fs_info->flags, BTRFS_FS_UNFINISHED_DROPS, TASK_INTERRUPTIBLE);
4083 	if (ret)
4084 		return ret;
4085 
4086 	/* We may have been woken up by close_ctree, so bail if we're closing. */
4087 	if (btrfs_fs_closing(fs_info))
4088 		return -EINTR;
4089 
4090 	bg = btrfs_lookup_block_group(fs_info, group_start);
4091 	if (!bg)
4092 		return -ENOENT;
4093 
4094 	/*
4095 	 * Relocation of a data block group creates ordered extents.  Without
4096 	 * sb_start_write(), we can freeze the filesystem while unfinished
4097 	 * ordered extents are left. Such ordered extents can cause a deadlock
4098 	 * e.g. when syncfs() is waiting for their completion but they can't
4099 	 * finish because they block when joining a transaction, due to the
4100 	 * fact that the freeze locks are being held in write mode.
4101 	 */
4102 	if (bg->flags & BTRFS_BLOCK_GROUP_DATA)
4103 		ASSERT(sb_write_started(fs_info->sb));
4104 
4105 	if (btrfs_pinned_by_swapfile(fs_info, bg)) {
4106 		btrfs_put_block_group(bg);
4107 		return -ETXTBSY;
4108 	}
4109 
4110 	rc = alloc_reloc_control(fs_info);
4111 	if (!rc) {
4112 		btrfs_put_block_group(bg);
4113 		return -ENOMEM;
4114 	}
4115 
4116 	ret = reloc_chunk_start(fs_info);
4117 	if (ret < 0) {
4118 		err = ret;
4119 		goto out_put_bg;
4120 	}
4121 
4122 	rc->extent_root = extent_root;
4123 	rc->block_group = bg;
4124 
4125 	ret = btrfs_inc_block_group_ro(rc->block_group, true);
4126 	if (ret) {
4127 		err = ret;
4128 		goto out;
4129 	}
4130 	rw = 1;
4131 
4132 	path = btrfs_alloc_path();
4133 	if (!path) {
4134 		err = -ENOMEM;
4135 		goto out;
4136 	}
4137 
4138 	inode = lookup_free_space_inode(rc->block_group, path);
4139 	btrfs_free_path(path);
4140 
4141 	if (!IS_ERR(inode))
4142 		ret = delete_block_group_cache(fs_info, rc->block_group, inode, 0);
4143 	else
4144 		ret = PTR_ERR(inode);
4145 
4146 	if (ret && ret != -ENOENT) {
4147 		err = ret;
4148 		goto out;
4149 	}
4150 
4151 	rc->data_inode = create_reloc_inode(fs_info, rc->block_group);
4152 	if (IS_ERR(rc->data_inode)) {
4153 		err = PTR_ERR(rc->data_inode);
4154 		rc->data_inode = NULL;
4155 		goto out;
4156 	}
4157 
4158 	describe_relocation(fs_info, rc->block_group);
4159 
4160 	btrfs_wait_block_group_reservations(rc->block_group);
4161 	btrfs_wait_nocow_writers(rc->block_group);
4162 	btrfs_wait_ordered_roots(fs_info, U64_MAX,
4163 				 rc->block_group->start,
4164 				 rc->block_group->length);
4165 
4166 	ret = btrfs_zone_finish(rc->block_group);
4167 	WARN_ON(ret && ret != -EAGAIN);
4168 
4169 	while (1) {
4170 		enum reloc_stage finishes_stage;
4171 
4172 		mutex_lock(&fs_info->cleaner_mutex);
4173 		ret = relocate_block_group(rc);
4174 		mutex_unlock(&fs_info->cleaner_mutex);
4175 		if (ret < 0)
4176 			err = ret;
4177 
4178 		finishes_stage = rc->stage;
4179 		/*
4180 		 * We may have gotten ENOSPC after we already dirtied some
4181 		 * extents.  If writeout happens while we're relocating a
4182 		 * different block group we could end up hitting the
4183 		 * BUG_ON(rc->stage == UPDATE_DATA_PTRS) in
4184 		 * btrfs_reloc_cow_block.  Make sure we write everything out
4185 		 * properly so we don't trip over this problem, and then break
4186 		 * out of the loop if we hit an error.
4187 		 */
4188 		if (rc->stage == MOVE_DATA_EXTENTS && rc->found_file_extent) {
4189 			ret = btrfs_wait_ordered_range(rc->data_inode, 0,
4190 						       (u64)-1);
4191 			if (ret)
4192 				err = ret;
4193 			invalidate_mapping_pages(rc->data_inode->i_mapping,
4194 						 0, -1);
4195 			rc->stage = UPDATE_DATA_PTRS;
4196 		}
4197 
4198 		if (err < 0)
4199 			goto out;
4200 
4201 		if (rc->extents_found == 0)
4202 			break;
4203 
4204 		btrfs_info(fs_info, "found %llu extents, stage: %s",
4205 			   rc->extents_found, stage_to_string(finishes_stage));
4206 	}
4207 
4208 	WARN_ON(rc->block_group->pinned > 0);
4209 	WARN_ON(rc->block_group->reserved > 0);
4210 	WARN_ON(rc->block_group->used > 0);
4211 out:
4212 	if (err && rw)
4213 		btrfs_dec_block_group_ro(rc->block_group);
4214 	iput(rc->data_inode);
4215 out_put_bg:
4216 	btrfs_put_block_group(bg);
4217 	reloc_chunk_end(fs_info);
4218 	free_reloc_control(rc);
4219 	return err;
4220 }
4221 
4222 static noinline_for_stack int mark_garbage_root(struct btrfs_root *root)
4223 {
4224 	struct btrfs_fs_info *fs_info = root->fs_info;
4225 	struct btrfs_trans_handle *trans;
4226 	int ret, err;
4227 
4228 	trans = btrfs_start_transaction(fs_info->tree_root, 0);
4229 	if (IS_ERR(trans))
4230 		return PTR_ERR(trans);
4231 
4232 	memset(&root->root_item.drop_progress, 0,
4233 		sizeof(root->root_item.drop_progress));
4234 	btrfs_set_root_drop_level(&root->root_item, 0);
4235 	btrfs_set_root_refs(&root->root_item, 0);
4236 	ret = btrfs_update_root(trans, fs_info->tree_root,
4237 				&root->root_key, &root->root_item);
4238 
4239 	err = btrfs_end_transaction(trans);
4240 	if (err)
4241 		return err;
4242 	return ret;
4243 }
4244 
4245 /*
4246  * recover relocation interrupted by system crash.
4247  *
4248  * this function resumes merging reloc trees with corresponding fs trees.
4249  * this is important for keeping the sharing of tree blocks
4250  */
4251 int btrfs_recover_relocation(struct btrfs_fs_info *fs_info)
4252 {
4253 	LIST_HEAD(reloc_roots);
4254 	struct btrfs_key key;
4255 	struct btrfs_root *fs_root;
4256 	struct btrfs_root *reloc_root;
4257 	struct btrfs_path *path;
4258 	struct extent_buffer *leaf;
4259 	struct reloc_control *rc = NULL;
4260 	struct btrfs_trans_handle *trans;
4261 	int ret;
4262 	int err = 0;
4263 
4264 	path = btrfs_alloc_path();
4265 	if (!path)
4266 		return -ENOMEM;
4267 	path->reada = READA_BACK;
4268 
4269 	key.objectid = BTRFS_TREE_RELOC_OBJECTID;
4270 	key.type = BTRFS_ROOT_ITEM_KEY;
4271 	key.offset = (u64)-1;
4272 
4273 	while (1) {
4274 		ret = btrfs_search_slot(NULL, fs_info->tree_root, &key,
4275 					path, 0, 0);
4276 		if (ret < 0) {
4277 			err = ret;
4278 			goto out;
4279 		}
4280 		if (ret > 0) {
4281 			if (path->slots[0] == 0)
4282 				break;
4283 			path->slots[0]--;
4284 		}
4285 		leaf = path->nodes[0];
4286 		btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
4287 		btrfs_release_path(path);
4288 
4289 		if (key.objectid != BTRFS_TREE_RELOC_OBJECTID ||
4290 		    key.type != BTRFS_ROOT_ITEM_KEY)
4291 			break;
4292 
4293 		reloc_root = btrfs_read_tree_root(fs_info->tree_root, &key);
4294 		if (IS_ERR(reloc_root)) {
4295 			err = PTR_ERR(reloc_root);
4296 			goto out;
4297 		}
4298 
4299 		set_bit(BTRFS_ROOT_SHAREABLE, &reloc_root->state);
4300 		list_add(&reloc_root->root_list, &reloc_roots);
4301 
4302 		if (btrfs_root_refs(&reloc_root->root_item) > 0) {
4303 			fs_root = btrfs_get_fs_root(fs_info,
4304 					reloc_root->root_key.offset, false);
4305 			if (IS_ERR(fs_root)) {
4306 				ret = PTR_ERR(fs_root);
4307 				if (ret != -ENOENT) {
4308 					err = ret;
4309 					goto out;
4310 				}
4311 				ret = mark_garbage_root(reloc_root);
4312 				if (ret < 0) {
4313 					err = ret;
4314 					goto out;
4315 				}
4316 			} else {
4317 				btrfs_put_root(fs_root);
4318 			}
4319 		}
4320 
4321 		if (key.offset == 0)
4322 			break;
4323 
4324 		key.offset--;
4325 	}
4326 	btrfs_release_path(path);
4327 
4328 	if (list_empty(&reloc_roots))
4329 		goto out;
4330 
4331 	rc = alloc_reloc_control(fs_info);
4332 	if (!rc) {
4333 		err = -ENOMEM;
4334 		goto out;
4335 	}
4336 
4337 	ret = reloc_chunk_start(fs_info);
4338 	if (ret < 0) {
4339 		err = ret;
4340 		goto out_end;
4341 	}
4342 
4343 	rc->extent_root = btrfs_extent_root(fs_info, 0);
4344 
4345 	set_reloc_control(rc);
4346 
4347 	trans = btrfs_join_transaction(rc->extent_root);
4348 	if (IS_ERR(trans)) {
4349 		err = PTR_ERR(trans);
4350 		goto out_unset;
4351 	}
4352 
4353 	rc->merge_reloc_tree = true;
4354 
4355 	while (!list_empty(&reloc_roots)) {
4356 		reloc_root = list_entry(reloc_roots.next,
4357 					struct btrfs_root, root_list);
4358 		list_del(&reloc_root->root_list);
4359 
4360 		if (btrfs_root_refs(&reloc_root->root_item) == 0) {
4361 			list_add_tail(&reloc_root->root_list,
4362 				      &rc->reloc_roots);
4363 			continue;
4364 		}
4365 
4366 		fs_root = btrfs_get_fs_root(fs_info, reloc_root->root_key.offset,
4367 					    false);
4368 		if (IS_ERR(fs_root)) {
4369 			err = PTR_ERR(fs_root);
4370 			list_add_tail(&reloc_root->root_list, &reloc_roots);
4371 			btrfs_end_transaction(trans);
4372 			goto out_unset;
4373 		}
4374 
4375 		err = __add_reloc_root(reloc_root);
4376 		ASSERT(err != -EEXIST);
4377 		if (err) {
4378 			list_add_tail(&reloc_root->root_list, &reloc_roots);
4379 			btrfs_put_root(fs_root);
4380 			btrfs_end_transaction(trans);
4381 			goto out_unset;
4382 		}
4383 		fs_root->reloc_root = btrfs_grab_root(reloc_root);
4384 		btrfs_put_root(fs_root);
4385 	}
4386 
4387 	err = btrfs_commit_transaction(trans);
4388 	if (err)
4389 		goto out_unset;
4390 
4391 	merge_reloc_roots(rc);
4392 
4393 	unset_reloc_control(rc);
4394 
4395 	trans = btrfs_join_transaction(rc->extent_root);
4396 	if (IS_ERR(trans)) {
4397 		err = PTR_ERR(trans);
4398 		goto out_clean;
4399 	}
4400 	err = btrfs_commit_transaction(trans);
4401 out_clean:
4402 	ret = clean_dirty_subvols(rc);
4403 	if (ret < 0 && !err)
4404 		err = ret;
4405 out_unset:
4406 	unset_reloc_control(rc);
4407 out_end:
4408 	reloc_chunk_end(fs_info);
4409 	free_reloc_control(rc);
4410 out:
4411 	free_reloc_roots(&reloc_roots);
4412 
4413 	btrfs_free_path(path);
4414 
4415 	if (err == 0) {
4416 		/* cleanup orphan inode in data relocation tree */
4417 		fs_root = btrfs_grab_root(fs_info->data_reloc_root);
4418 		ASSERT(fs_root);
4419 		err = btrfs_orphan_cleanup(fs_root);
4420 		btrfs_put_root(fs_root);
4421 	}
4422 	return err;
4423 }
4424 
4425 /*
4426  * helper to add ordered checksum for data relocation.
4427  *
4428  * cloning checksum properly handles the nodatasum extents.
4429  * it also saves CPU time to re-calculate the checksum.
4430  */
4431 int btrfs_reloc_clone_csums(struct btrfs_ordered_extent *ordered)
4432 {
4433 	struct btrfs_inode *inode = BTRFS_I(ordered->inode);
4434 	struct btrfs_fs_info *fs_info = inode->root->fs_info;
4435 	u64 disk_bytenr = ordered->file_offset + inode->index_cnt;
4436 	struct btrfs_root *csum_root = btrfs_csum_root(fs_info, disk_bytenr);
4437 	LIST_HEAD(list);
4438 	int ret;
4439 
4440 	ret = btrfs_lookup_csums_list(csum_root, disk_bytenr,
4441 				      disk_bytenr + ordered->num_bytes - 1,
4442 				      &list, 0, false);
4443 	if (ret)
4444 		return ret;
4445 
4446 	while (!list_empty(&list)) {
4447 		struct btrfs_ordered_sum *sums =
4448 			list_entry(list.next, struct btrfs_ordered_sum, list);
4449 
4450 		list_del_init(&sums->list);
4451 
4452 		/*
4453 		 * We need to offset the new_bytenr based on where the csum is.
4454 		 * We need to do this because we will read in entire prealloc
4455 		 * extents but we may have written to say the middle of the
4456 		 * prealloc extent, so we need to make sure the csum goes with
4457 		 * the right disk offset.
4458 		 *
4459 		 * We can do this because the data reloc inode refers strictly
4460 		 * to the on disk bytes, so we don't have to worry about
4461 		 * disk_len vs real len like with real inodes since it's all
4462 		 * disk length.
4463 		 */
4464 		sums->logical = ordered->disk_bytenr + sums->logical - disk_bytenr;
4465 		btrfs_add_ordered_sum(ordered, sums);
4466 	}
4467 
4468 	return 0;
4469 }
4470 
4471 int btrfs_reloc_cow_block(struct btrfs_trans_handle *trans,
4472 			  struct btrfs_root *root,
4473 			  const struct extent_buffer *buf,
4474 			  struct extent_buffer *cow)
4475 {
4476 	struct btrfs_fs_info *fs_info = root->fs_info;
4477 	struct reloc_control *rc;
4478 	struct btrfs_backref_node *node;
4479 	int first_cow = 0;
4480 	int level;
4481 	int ret = 0;
4482 
4483 	rc = fs_info->reloc_ctl;
4484 	if (!rc)
4485 		return 0;
4486 
4487 	BUG_ON(rc->stage == UPDATE_DATA_PTRS && btrfs_is_data_reloc_root(root));
4488 
4489 	level = btrfs_header_level(buf);
4490 	if (btrfs_header_generation(buf) <=
4491 	    btrfs_root_last_snapshot(&root->root_item))
4492 		first_cow = 1;
4493 
4494 	if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID &&
4495 	    rc->create_reloc_tree) {
4496 		WARN_ON(!first_cow && level == 0);
4497 
4498 		node = rc->backref_cache.path[level];
4499 		BUG_ON(node->bytenr != buf->start &&
4500 		       node->new_bytenr != buf->start);
4501 
4502 		btrfs_backref_drop_node_buffer(node);
4503 		atomic_inc(&cow->refs);
4504 		node->eb = cow;
4505 		node->new_bytenr = cow->start;
4506 
4507 		if (!node->pending) {
4508 			list_move_tail(&node->list,
4509 				       &rc->backref_cache.pending[level]);
4510 			node->pending = 1;
4511 		}
4512 
4513 		if (first_cow)
4514 			mark_block_processed(rc, node);
4515 
4516 		if (first_cow && level > 0)
4517 			rc->nodes_relocated += buf->len;
4518 	}
4519 
4520 	if (level == 0 && first_cow && rc->stage == UPDATE_DATA_PTRS)
4521 		ret = replace_file_extents(trans, rc, root, cow);
4522 	return ret;
4523 }
4524 
4525 /*
4526  * called before creating snapshot. it calculates metadata reservation
4527  * required for relocating tree blocks in the snapshot
4528  */
4529 void btrfs_reloc_pre_snapshot(struct btrfs_pending_snapshot *pending,
4530 			      u64 *bytes_to_reserve)
4531 {
4532 	struct btrfs_root *root = pending->root;
4533 	struct reloc_control *rc = root->fs_info->reloc_ctl;
4534 
4535 	if (!rc || !have_reloc_root(root))
4536 		return;
4537 
4538 	if (!rc->merge_reloc_tree)
4539 		return;
4540 
4541 	root = root->reloc_root;
4542 	BUG_ON(btrfs_root_refs(&root->root_item) == 0);
4543 	/*
4544 	 * relocation is in the stage of merging trees. the space
4545 	 * used by merging a reloc tree is twice the size of
4546 	 * relocated tree nodes in the worst case. half for cowing
4547 	 * the reloc tree, half for cowing the fs tree. the space
4548 	 * used by cowing the reloc tree will be freed after the
4549 	 * tree is dropped. if we create snapshot, cowing the fs
4550 	 * tree may use more space than it frees. so we need
4551 	 * reserve extra space.
4552 	 */
4553 	*bytes_to_reserve += rc->nodes_relocated;
4554 }
4555 
4556 /*
4557  * called after snapshot is created. migrate block reservation
4558  * and create reloc root for the newly created snapshot
4559  *
4560  * This is similar to btrfs_init_reloc_root(), we come out of here with two
4561  * references held on the reloc_root, one for root->reloc_root and one for
4562  * rc->reloc_roots.
4563  */
4564 int btrfs_reloc_post_snapshot(struct btrfs_trans_handle *trans,
4565 			       struct btrfs_pending_snapshot *pending)
4566 {
4567 	struct btrfs_root *root = pending->root;
4568 	struct btrfs_root *reloc_root;
4569 	struct btrfs_root *new_root;
4570 	struct reloc_control *rc = root->fs_info->reloc_ctl;
4571 	int ret;
4572 
4573 	if (!rc || !have_reloc_root(root))
4574 		return 0;
4575 
4576 	rc = root->fs_info->reloc_ctl;
4577 	rc->merging_rsv_size += rc->nodes_relocated;
4578 
4579 	if (rc->merge_reloc_tree) {
4580 		ret = btrfs_block_rsv_migrate(&pending->block_rsv,
4581 					      rc->block_rsv,
4582 					      rc->nodes_relocated, true);
4583 		if (ret)
4584 			return ret;
4585 	}
4586 
4587 	new_root = pending->snap;
4588 	reloc_root = create_reloc_root(trans, root->reloc_root,
4589 				       new_root->root_key.objectid);
4590 	if (IS_ERR(reloc_root))
4591 		return PTR_ERR(reloc_root);
4592 
4593 	ret = __add_reloc_root(reloc_root);
4594 	ASSERT(ret != -EEXIST);
4595 	if (ret) {
4596 		/* Pairs with create_reloc_root */
4597 		btrfs_put_root(reloc_root);
4598 		return ret;
4599 	}
4600 	new_root->reloc_root = btrfs_grab_root(reloc_root);
4601 
4602 	if (rc->create_reloc_tree)
4603 		ret = clone_backref_node(trans, rc, root, reloc_root);
4604 	return ret;
4605 }
4606 
4607 /*
4608  * Get the current bytenr for the block group which is being relocated.
4609  *
4610  * Return U64_MAX if no running relocation.
4611  */
4612 u64 btrfs_get_reloc_bg_bytenr(const struct btrfs_fs_info *fs_info)
4613 {
4614 	u64 logical = U64_MAX;
4615 
4616 	lockdep_assert_held(&fs_info->reloc_mutex);
4617 
4618 	if (fs_info->reloc_ctl && fs_info->reloc_ctl->block_group)
4619 		logical = fs_info->reloc_ctl->block_group->start;
4620 	return logical;
4621 }
4622