linux - fs/btrfs/relocation.c

6280 lines · 158.4 KiB

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	#include "raid-stripe-tree.h"
40	#include "free-space-tree.h"
41
42	/*
43	* Relocation overview
44	*
45	* [What does relocation do]
46	*
47	* The objective of relocation is to relocate all extents of the target block
48	* group to other block groups.
49	* This is utilized by resize (shrink only), profile converting, compacting
50	* space, or balance routine to spread chunks over devices.
51	*
52	* Before \| After
53	* ------------------------------------------------------------------
54	* BG A: 10 data extents \| BG A: deleted
55	* BG B: 2 data extents \| BG B: 10 data extents (2 old + 8 relocated)
56	* BG C: 1 extents \| BG C: 3 data extents (1 old + 2 relocated)
57	*
58	* [How does relocation work]
59	*
60	* 1. Mark the target block group read-only
61	* New extents won't be allocated from the target block group.
62	*
63	* 2.1 Record each extent in the target block group
64	* To build a proper map of extents to be relocated.
65	*
66	* 2.2 Build data reloc tree and reloc trees
67	* Data reloc tree will contain an inode, recording all newly relocated
68	* data extents.
69	* There will be only one data reloc tree for one data block group.
70	*
71	* Reloc tree will be a special snapshot of its source tree, containing
72	* relocated tree blocks.
73	* Each tree referring to a tree block in target block group will get its
74	* reloc tree built.
75	*
76	* 2.3 Swap source tree with its corresponding reloc tree
77	* Each involved tree only refers to new extents after swap.
78	*
79	* 3. Cleanup reloc trees and data reloc tree.
80	* As old extents in the target block group are still referenced by reloc
81	* trees, we need to clean them up before really freeing the target block
82	* group.
83	*
84	* The main complexity is in steps 2.2 and 2.3.
85	*
86	* The entry point of relocation is relocate_block_group() function.
87	*/
88
89	#define RELOCATION_RESERVED_NODES 256
90	/*
91	* map address of tree root to tree
92	*/
93	struct mapping_node {
94	union {
95	/* Use rb_simple_node for search/insert */
96	struct {
97	struct rb_node rb_node;
98	u64 bytenr;
99	};
100
101	struct rb_simple_node simple_node;
102	};
103	void *data;
104	};
105
106	struct mapping_tree {
107	struct rb_root rb_root;
108	spinlock_t lock;
109	};
110
111	/*
112	* present a tree block to process
113	*/
114	struct tree_block {
115	union {
116	/* Use rb_simple_node for search/insert */
117	struct {
118	struct rb_node rb_node;
119	u64 bytenr;
120	};
121
122	struct rb_simple_node simple_node;
123	};
124	u64 owner;
125	struct btrfs_key key;
126	u8 level;
127	bool key_ready;
128	};
129
130	#define MAX_EXTENTS 128
131
132	struct file_extent_cluster {
133	u64 start;
134	u64 end;
135	u64 boundary[MAX_EXTENTS];
136	unsigned int nr;
137	u64 owning_root;
138	};
139
140	/* Stages of data relocation. */
141	enum reloc_stage {
142	MOVE_DATA_EXTENTS,
143	UPDATE_DATA_PTRS
144	};
145
146	struct reloc_control {
147	/* block group to relocate */
148	struct btrfs_block_group *block_group;
149	/* extent tree */
150	struct btrfs_root *extent_root;
151	/* inode for moving data */
152	struct inode *data_inode;
153
154	struct btrfs_block_rsv *block_rsv;
155
156	struct btrfs_backref_cache backref_cache;
157
158	struct file_extent_cluster cluster;
159	/* tree blocks have been processed */
160	struct extent_io_tree processed_blocks;
161	/* map start of tree root to corresponding reloc tree */
162	struct mapping_tree reloc_root_tree;
163	/* list of reloc trees */
164	struct list_head reloc_roots;
165	/* list of subvolume trees that get relocated */
166	struct list_head dirty_subvol_roots;
167	/* size of metadata reservation for merging reloc trees */
168	u64 merging_rsv_size;
169	/* size of relocated tree nodes */
170	u64 nodes_relocated;
171	/* reserved size for block group relocation*/
172	u64 reserved_bytes;
173
174	u64 search_start;
175	u64 extents_found;
176
177	enum reloc_stage stage;
178	bool create_reloc_tree;
179	bool merge_reloc_tree;
180	bool found_file_extent;
181
182	refcount_t refs;
183	};
184
185	static struct reloc_control get_reloc_control(struct btrfs_fs_info fs_info)
186	{
187	struct reloc_control *rc;
188
189	/* Quick path, avoid lock contention on fs_info->reloc_ctl_lock. */
190	if (!data_race(fs_info->reloc_ctl))
191	return NULL;
192
193	spin_lock(&fs_info->reloc_ctl_lock);
194	rc = fs_info->reloc_ctl;
195	if (rc)
196	refcount_inc(&rc->refs);
197	spin_unlock(&fs_info->reloc_ctl_lock);
198
199	return rc;
200	}
201
202	static void __del_reloc_root(struct btrfs_root *root);
203
204	static noinline_for_stack void free_reloc_roots(struct list_head *list)
205	{
206	struct btrfs_root reloc_root, tmp;
207
208	list_for_each_entry_safe(reloc_root, tmp, list, root_list)
209	__del_reloc_root(reloc_root);
210	}
211
212	static void put_reloc_control(struct reloc_control *rc)
213	{
214	if (refcount_dec_and_test(&rc->refs)) {
215	struct mapping_node node, tmp;
216
217	if (rc->extent_root)
218	ASSERT(rc->extent_root->fs_info->reloc_ctl != rc);
219
220	free_reloc_roots(&rc->reloc_roots);
221	rbtree_postorder_for_each_entry_safe(node, tmp,
222	&rc->reloc_root_tree.rb_root,
223	rb_node)
224	kfree(node);
225
226	if (rc->block_group)
227	btrfs_put_block_group(rc->block_group);
228
229	kfree(rc);
230	}
231	}
232
233	/* Helper to delete the 'address of tree root -> reloc tree' mapping. */
234	static void __del_reloc_root(struct btrfs_root *root)
235	{
236	struct btrfs_fs_info *fs_info = root->fs_info;
237	struct rb_node *rb_node;
238	struct mapping_node AUTO_KFREE(node);
239	struct reloc_control *rc;
240	bool put_ref = false;
241
242	rc = get_reloc_control(fs_info);
243	if (rc && root->node) {
244	spin_lock(&rc->reloc_root_tree.lock);
245	rb_node = rb_simple_search(&rc->reloc_root_tree.rb_root,
246	root->commit_root->start);
247	if (rb_node) {
248	node = rb_entry(rb_node, struct mapping_node, rb_node);
249	rb_erase(&node->rb_node, &rc->reloc_root_tree.rb_root);
250	RB_CLEAR_NODE(&node->rb_node);
251	}
252	spin_unlock(&rc->reloc_root_tree.lock);
253	ASSERT(!node \|\| (struct btrfs_root *)node->data == root);
254	}
255
256	/*
257	* We only put the reloc root here if it's on the list. There's a lot
258	* of places where the pattern is to splice the rc->reloc_roots, process
259	* the reloc roots, and then add the reloc root back onto
260	* rc->reloc_roots. If we call __del_reloc_root while it's off of the
261	* list we don't want the reference being dropped, because the guy
262	* messing with the list is in charge of the reference.
263	*/
264	spin_lock(&fs_info->trans_lock);
265	if (!list_empty(&root->root_list)) {
266	put_ref = true;
267	list_del_init(&root->root_list);
268	}
269	spin_unlock(&fs_info->trans_lock);
270	if (put_ref)
271	btrfs_put_root(root);
272	if (rc)
273	put_reloc_control(rc);
274	}
275
276	static void mark_block_processed(struct reloc_control *rc,
277	struct btrfs_backref_node *node)
278	{
279	u32 blocksize;
280
281	if (node->level == 0 \|\|
282	in_range(node->bytenr, rc->block_group->start,
283	rc->block_group->length)) {
284	blocksize = rc->extent_root->fs_info->nodesize;
285	btrfs_set_extent_bit(&rc->processed_blocks, node->bytenr,
286	node->bytenr + blocksize - 1, EXTENT_DIRTY,
287	NULL);
288	}
289	node->processed = 1;
290	}
291
292	/*
293	* walk up backref nodes until reach node presents tree root
294	*/
295	static struct btrfs_backref_node *walk_up_backref(
296	struct btrfs_backref_node *node,
297	struct btrfs_backref_edge edges[], int index)
298	{
299	struct btrfs_backref_edge *edge;
300	int idx = *index;
301
302	while (!list_empty(&node->upper)) {
303	edge = list_first_entry(&node->upper, struct btrfs_backref_edge,
304	list[LOWER]);
305	edges[idx++] = edge;
306	node = edge->node[UPPER];
307	}
308	BUG_ON(node->detached);
309	*index = idx;
310	return node;
311	}
312
313	/*
314	* walk down backref nodes to find start of next reference path
315	*/
316	static struct btrfs_backref_node *walk_down_backref(
317	struct btrfs_backref_edge edges[], int index)
318	{
319	struct btrfs_backref_edge *edge;
320	struct btrfs_backref_node *lower;
321	int idx = *index;
322
323	while (idx > 0) {
324	edge = edges[idx - 1];
325	lower = edge->node[LOWER];
326	if (list_is_last(&edge->list[LOWER], &lower->upper)) {
327	idx--;
328	continue;
329	}
330	edge = list_first_entry(&edge->list[LOWER], struct btrfs_backref_edge,
331	list[LOWER]);
332	edges[idx - 1] = edge;
333	*index = idx;
334	return edge->node[UPPER];
335	}
336	*index = 0;
337	return NULL;
338	}
339
340	static bool reloc_root_is_dead(const struct btrfs_root *root)
341	{
342	if (test_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state))
343	return true;
344	/*
345	* Pairs with set_bit/clear_bit in clear_reloc_root() and
346	* btrfs_update_reloc_root(). We need to see the updated bit before
347	* trying to access root->reloc_root in our callers.
348	*/
349	smp_rmb();
350
351	return false;
352	}
353
354	/*
355	* Check if this subvolume tree has valid reloc tree.
356	*
357	* Reloc tree after swap is considered dead, thus not considered as valid.
358	* This is enough for most callers, as they don't distinguish dead reloc root
359	* from no reloc root. But btrfs_should_ignore_reloc_root() below is a
360	* special case.
361	*/
362	static bool have_reloc_root(const struct btrfs_root *root)
363	{
364	if (reloc_root_is_dead(root))
365	return false;
366	if (!root->reloc_root)
367	return false;
368	return true;
369	}
370
371	bool btrfs_should_ignore_reloc_root(const struct btrfs_root *root)
372	{
373	struct btrfs_root *reloc_root;
374
375	if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state))
376	return false;
377
378	/* This root has been merged with its reloc tree, we can ignore it */
379	if (reloc_root_is_dead(root))
380	return true;
381
382	reloc_root = root->reloc_root;
383	if (!reloc_root)
384	return false;
385
386	if (btrfs_header_generation(reloc_root->commit_root) ==
387	root->fs_info->running_transaction->transid)
388	return false;
389	/*
390	* If there is reloc tree and it was created in previous transaction
391	* backref lookup can find the reloc tree, so backref node for the fs
392	* tree root is useless for relocation.
393	*/
394	return true;
395	}
396
397	/*
398	* find reloc tree by address of tree root
399	*/
400	struct btrfs_root find_reloc_root(struct btrfs_fs_info fs_info, u64 bytenr)
401	{
402	struct reloc_control *rc = fs_info->reloc_ctl;
403	struct rb_node *rb_node;
404	struct mapping_node *node;
405	struct btrfs_root *root = NULL;
406
407	ASSERT(rc);
408	spin_lock(&rc->reloc_root_tree.lock);
409	rb_node = rb_simple_search(&rc->reloc_root_tree.rb_root, bytenr);
410	if (rb_node) {
411	node = rb_entry(rb_node, struct mapping_node, rb_node);
412	root = node->data;
413	}
414	spin_unlock(&rc->reloc_root_tree.lock);
415	return btrfs_grab_root(root);
416	}
417
418	/*
419	* For useless nodes, do two major clean ups:
420	*
421	* - Cleanup the children edges and nodes
422	* If child node is also orphan (no parent) during cleanup, then the child
423	* node will also be cleaned up.
424	*
425	* - Freeing up leaves (level 0), keeps nodes detached
426	* For nodes, the node is still cached as "detached"
427	*
428	* Return false if @node is not in the @useless_nodes list.
429	* Return true if @node is in the @useless_nodes list.
430	*/
431	static bool handle_useless_nodes(struct reloc_control *rc,
432	struct btrfs_backref_node *node)
433	{
434	struct btrfs_backref_cache *cache = &rc->backref_cache;
435	struct list_head *useless_node = &cache->useless_node;
436	bool ret = false;
437
438	while (!list_empty(useless_node)) {
439	struct btrfs_backref_node *cur;
440
441	cur = list_first_entry(useless_node, struct btrfs_backref_node,
442	list);
443	list_del_init(&cur->list);
444
445	/* Only tree root nodes can be added to @useless_nodes */
446	ASSERT(list_empty(&cur->upper));
447
448	if (cur == node)
449	ret = true;
450
451	/* Cleanup the lower edges */
452	while (!list_empty(&cur->lower)) {
453	struct btrfs_backref_edge *edge;
454	struct btrfs_backref_node *lower;
455
456	edge = list_first_entry(&cur->lower, struct btrfs_backref_edge,
457	list[UPPER]);
458	list_del(&edge->list[UPPER]);
459	list_del(&edge->list[LOWER]);
460	lower = edge->node[LOWER];
461	btrfs_backref_free_edge(cache, edge);
462
463	/* Child node is also orphan, queue for cleanup */
464	if (list_empty(&lower->upper))
465	list_add(&lower->list, useless_node);
466	}
467	/* Mark this block processed for relocation */
468	mark_block_processed(rc, cur);
469
470	/*
471	* Backref nodes for tree leaves are deleted from the cache.
472	* Backref nodes for upper level tree blocks are left in the
473	* cache to avoid unnecessary backref lookup.
474	*/
475	if (cur->level > 0) {
476	cur->detached = 1;
477	} else {
478	rb_erase(&cur->rb_node, &cache->rb_root);
479	btrfs_backref_free_node(cache, cur);
480	}
481	}
482	return ret;
483	}
484
485	/*
486	* Build backref tree for a given tree block. Root of the backref tree
487	* corresponds the tree block, leaves of the backref tree correspond roots of
488	* b-trees that reference the tree block.
489	*
490	* The basic idea of this function is check backrefs of a given block to find
491	* upper level blocks that reference the block, and then check backrefs of
492	* these upper level blocks recursively. The recursion stops when tree root is
493	* reached or backrefs for the block is cached.
494	*
495	* NOTE: if we find that backrefs for a block are cached, we know backrefs for
496	* all upper level blocks that directly/indirectly reference the block are also
497	* cached.
498	*/
499	static noinline_for_stack struct btrfs_backref_node *build_backref_tree(
500	struct btrfs_trans_handle *trans,
501	struct reloc_control rc, struct btrfs_key node_key,
502	int level, u64 bytenr)
503	{
504	struct btrfs_backref_iter iter;
505	struct btrfs_backref_cache *cache = &rc->backref_cache;
506	/* For searching parent of TREE_BLOCK_REF */
507	struct btrfs_path *path;
508	struct btrfs_backref_node *cur;
509	struct btrfs_backref_node *node = NULL;
510	struct btrfs_backref_edge *edge;
511	int ret;
512
513	ret = btrfs_backref_iter_init(&iter);
514	if (ret < 0)
515	return ERR_PTR(ret);
516	path = btrfs_alloc_path();
517	if (!path) {
518	ret = -ENOMEM;
519	goto out;
520	}
521
522	node = btrfs_backref_alloc_node(cache, bytenr, level);
523	if (!node) {
524	ret = -ENOMEM;
525	goto out;
526	}
527
528	cur = node;
529
530	/* Breadth-first search to build backref cache */
531	do {
532	ret = btrfs_backref_add_tree_node(trans, cache, path, &iter,
533	node_key, cur);
534	if (ret < 0)
535	goto out;
536
537	edge = list_first_entry_or_null(&cache->pending_edge,
538	struct btrfs_backref_edge, list[UPPER]);
539	/*
540	* The pending list isn't empty, take the first block to
541	* process
542	*/
543	if (edge) {
544	list_del_init(&edge->list[UPPER]);
545	cur = edge->node[UPPER];
546	}
547	} while (edge);
548
549	/* Finish the upper linkage of newly added edges/nodes */
550	ret = btrfs_backref_finish_upper_links(cache, node);
551	if (ret < 0)
552	goto out;
553
554	if (handle_useless_nodes(rc, node))
555	node = NULL;
556	out:
557	btrfs_free_path(iter.path);
558	btrfs_free_path(path);
559	if (ret) {
560	btrfs_backref_error_cleanup(cache, node);
561	return ERR_PTR(ret);
562	}
563	ASSERT(!node \|\| !node->detached);
564	ASSERT(list_empty(&cache->useless_node) &&
565	list_empty(&cache->pending_edge));
566	return node;
567	}
568
569	/*
570	* helper to add 'address of tree root -> reloc tree' mapping
571	*/
572	static int __add_reloc_root(struct btrfs_root root, struct reloc_control rc)
573	{
574	struct btrfs_fs_info *fs_info = root->fs_info;
575	struct rb_node *rb_node;
576	struct mapping_node *node;
577
578	node = kmalloc_obj(*node, GFP_NOFS);
579	if (!node)
580	return -ENOMEM;
581
582	node->bytenr = root->commit_root->start;
583	node->data = root;
584
585	spin_lock(&rc->reloc_root_tree.lock);
586	rb_node = rb_simple_insert(&rc->reloc_root_tree.rb_root, &node->simple_node);
587	spin_unlock(&rc->reloc_root_tree.lock);
588	if (rb_node) {
589	btrfs_err(fs_info,
590	"Duplicate root found for start=%llu while inserting into relocation tree",
591	node->bytenr);
592	kfree(node);
593	return -EEXIST;
594	}
595
596	list_add_tail(&root->root_list, &rc->reloc_roots);
597	return 0;
598	}
599
600	/*
601	* helper to update the 'address of tree root -> reloc tree'
602	* mapping
603	*/
604	static int __update_reloc_root(struct btrfs_root *root)
605	{
606	struct btrfs_fs_info *fs_info = root->fs_info;
607	struct rb_node *rb_node;
608	struct mapping_node *node = NULL;
609	struct reloc_control *rc = fs_info->reloc_ctl;
610
611	spin_lock(&rc->reloc_root_tree.lock);
612	rb_node = rb_simple_search(&rc->reloc_root_tree.rb_root,
613	root->commit_root->start);
614	if (rb_node) {
615	node = rb_entry(rb_node, struct mapping_node, rb_node);
616	rb_erase(&node->rb_node, &rc->reloc_root_tree.rb_root);
617	}
618	spin_unlock(&rc->reloc_root_tree.lock);
619
620	if (!node)
621	return 0;
622	BUG_ON((struct btrfs_root *)node->data != root);
623
624	spin_lock(&rc->reloc_root_tree.lock);
625	node->bytenr = root->node->start;
626	rb_node = rb_simple_insert(&rc->reloc_root_tree.rb_root, &node->simple_node);
627	spin_unlock(&rc->reloc_root_tree.lock);
628	if (rb_node)
629	btrfs_backref_panic(fs_info, node->bytenr, -EEXIST);
630	return 0;
631	}
632
633	static struct btrfs_root create_reloc_root(struct btrfs_trans_handle trans,
634	struct btrfs_root *root, u64 objectid)
635	{
636	struct btrfs_fs_info *fs_info = root->fs_info;
637	struct btrfs_root *reloc_root;
638	struct extent_buffer *eb;
639	struct btrfs_root_item AUTO_KFREE(root_item);
640	struct btrfs_key root_key;
641	int ret = 0;
642
643	root_item = kmalloc_obj(*root_item, GFP_NOFS);
644	if (!root_item)
645	return ERR_PTR(-ENOMEM);
646
647	root_key.objectid = BTRFS_TREE_RELOC_OBJECTID;
648	root_key.type = BTRFS_ROOT_ITEM_KEY;
649	root_key.offset = objectid;
650
651	if (btrfs_root_id(root) == objectid) {
652	u64 commit_root_gen;
653
654	/*
655	* Relocation will wait for cleaner thread, and any half-dropped
656	* subvolume will be fully cleaned up at mount time.
657	* So here we shouldn't hit a subvolume with non-zero drop_progress.
658	*
659	* If this isn't the case, error out since it can make us attempt to
660	* drop references for extents that were already dropped before.
661	*/
662	if (unlikely(btrfs_disk_key_objectid(&root->root_item.drop_progress))) {
663	struct btrfs_key cpu_key;
664
665	btrfs_disk_key_to_cpu(&cpu_key, &root->root_item.drop_progress);
666	btrfs_err(fs_info,
667	"cannot relocate partially dropped subvolume %llu, drop progress key " BTRFS_KEY_FMT,
668	objectid, BTRFS_KEY_FMT_VALUE(&cpu_key));
669	return ERR_PTR(-EUCLEAN);
670	}
671
672	/* called by btrfs_init_reloc_root */
673	ret = btrfs_copy_root(trans, root, root->commit_root, &eb,
674	BTRFS_TREE_RELOC_OBJECTID);
675	if (ret)
676	return ERR_PTR(ret);
677
678	/*
679	* Set the last_snapshot field to the generation of the commit
680	* root - like this ctree.c:btrfs_block_can_be_shared() behaves
681	* correctly (returns true) when the relocation root is created
682	* either inside the critical section of a transaction commit
683	* (through transaction.c:qgroup_account_snapshot()) and when
684	* it's created before the transaction commit is started.
685	*/
686	commit_root_gen = btrfs_header_generation(root->commit_root);
687	btrfs_set_root_last_snapshot(&root->root_item, commit_root_gen);
688	} else {
689	/*
690	* called by btrfs_reloc_post_snapshot_hook.
691	* the source tree is a reloc tree, all tree blocks
692	* modified after it was created have RELOC flag
693	* set in their headers. so it's OK to not update
694	* the 'last_snapshot'.
695	*/
696	ret = btrfs_copy_root(trans, root, root->node, &eb,
697	BTRFS_TREE_RELOC_OBJECTID);
698	if (ret)
699	return ERR_PTR(ret);
700	}
701
702	/*
703	* We have changed references at this point, we must abort the
704	* transaction if anything fails (i.e. 'goto abort').
705	*/
706
707	memcpy(root_item, &root->root_item, sizeof(*root_item));
708	btrfs_set_root_bytenr(root_item, eb->start);
709	btrfs_set_root_level(root_item, btrfs_header_level(eb));
710	btrfs_set_root_generation(root_item, trans->transid);
711
712	if (btrfs_root_id(root) == objectid) {
713	btrfs_set_root_refs(root_item, 0);
714	memset(&root_item->drop_progress, 0,
715	sizeof(struct btrfs_disk_key));
716	btrfs_set_root_drop_level(root_item, 0);
717	}
718
719	btrfs_tree_unlock(eb);
720	free_extent_buffer(eb);
721
722	ret = btrfs_insert_root(trans, fs_info->tree_root,
723	&root_key, root_item);
724	if (unlikely(ret)) {
725	btrfs_abort_transaction(trans, ret);
726	return ERR_PTR(ret);
727	}
728
729	reloc_root = btrfs_read_tree_root(fs_info->tree_root, &root_key);
730	if (IS_ERR(reloc_root)) {
731	btrfs_abort_transaction(trans, PTR_ERR(reloc_root));
732	return ERR_CAST(reloc_root);
733	}
734	set_bit(BTRFS_ROOT_SHAREABLE, &reloc_root->state);
735	btrfs_set_root_last_trans(reloc_root, trans->transid);
736	return reloc_root;
737	}
738
739	/*
740	* create reloc tree for a given fs tree. reloc tree is just a
741	* snapshot of the fs tree with special root objectid.
742	*
743	* The reloc_root comes out of here with two references, one for
744	* root->reloc_root, and another for being on the rc->reloc_roots list.
745	*/
746	int btrfs_init_reloc_root(struct btrfs_trans_handle *trans,
747	struct btrfs_root *root)
748	{
749	struct btrfs_fs_info *fs_info = root->fs_info;
750	struct btrfs_root *reloc_root;
751	struct reloc_control *rc;
752	struct btrfs_block_rsv *rsv;
753	bool clear_rsv = false;
754	int ret = 0;
755
756	rc = get_reloc_control(fs_info);
757	if (!rc)
758	return 0;
759
760	/*
761	* The subvolume has reloc tree but the swap is finished, no need to
762	* create/update the dead reloc tree
763	*/
764	if (reloc_root_is_dead(root))
765	goto out;
766
767	/*
768	* This is subtle but important. We do not do
769	* record_root_in_transaction for reloc roots, instead we record their
770	* corresponding fs root, and then here we update the last trans for the
771	* reloc root. This means that we have to do this for the entire life
772	* of the reloc root, regardless of which stage of the relocation we are
773	* in.
774	*/
775	if (root->reloc_root) {
776	btrfs_set_root_last_trans(root->reloc_root, trans->transid);
777	goto out;
778	}
779
780	/*
781	* We are merging reloc roots, we do not need new reloc trees. Also
782	* reloc trees never need their own reloc tree.
783	*/
784	if (!rc->create_reloc_tree \|\| btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID)
785	goto out;
786
787	if (!trans->reloc_reserved) {
788	rsv = trans->block_rsv;
789	trans->block_rsv = rc->block_rsv;
790	clear_rsv = true;
791	}
792	reloc_root = create_reloc_root(trans, root, btrfs_root_id(root));
793	if (clear_rsv)
794	trans->block_rsv = rsv;
795	if (IS_ERR(reloc_root)) {
796	ret = PTR_ERR(reloc_root);
797	goto out;
798	}
799
800	ret = __add_reloc_root(reloc_root, rc);
801	ASSERT(ret != -EEXIST);
802	if (ret) {
803	/* Pairs with create_reloc_root */
804	btrfs_put_root(reloc_root);
805	goto out;
806	}
807	root->reloc_root = btrfs_grab_root(reloc_root);
808	out:
809	put_reloc_control(rc);
810
811	return ret;
812	}
813
814	/*
815	* update root item of reloc tree
816	*/
817	int btrfs_update_reloc_root(struct btrfs_trans_handle *trans,
818	struct btrfs_root *root)
819	{
820	struct btrfs_fs_info *fs_info = root->fs_info;
821	struct btrfs_root *reloc_root;
822	struct btrfs_root_item *root_item;
823	struct reloc_control *rc;
824	int ret;
825
826	if (!have_reloc_root(root))
827	return 0;
828
829	reloc_root = root->reloc_root;
830	root_item = &reloc_root->root_item;
831
832	/*
833	* We are probably ok here, but __del_reloc_root() will drop its ref of
834	* the root. We have the ref for root->reloc_root, but just in case
835	* hold it while we update the reloc root.
836	*/
837	btrfs_grab_root(reloc_root);
838
839	rc = get_reloc_control(fs_info);
840	/* root->reloc_root will stay until current relocation finished */
841	if (rc && rc->merge_reloc_tree && btrfs_root_refs(root_item) == 0) {
842	set_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state);
843	/*
844	* Mark the tree as dead before we change reloc_root so
845	* have_reloc_root will not touch it from now on.
846	*/
847	smp_wmb();
848	__del_reloc_root(reloc_root);
849	}
850
851	if (reloc_root->commit_root != reloc_root->node) {
852	__update_reloc_root(reloc_root);
853	btrfs_set_root_node(root_item, reloc_root->node);
854	free_extent_buffer(reloc_root->commit_root);
855	reloc_root->commit_root = btrfs_root_node(reloc_root);
856	}
857
858	ret = btrfs_update_root(trans, fs_info->tree_root,
859	&reloc_root->root_key, root_item);
860	btrfs_put_root(reloc_root);
861	if (rc)
862	put_reloc_control(rc);
863
864	return ret;
865	}
866
867	/*
868	* get new location of data
869	*/
870	static int get_new_location(struct inode reloc_inode, u64 new_bytenr,
871	u64 bytenr, u64 num_bytes)
872	{
873	struct btrfs_root *root = BTRFS_I(reloc_inode)->root;
874	struct btrfs_fs_info *fs_info = root->fs_info;
875	BTRFS_PATH_AUTO_FREE(path);
876	struct btrfs_file_extent_item *fi;
877	struct extent_buffer *leaf;
878	int ret;
879
880	path = btrfs_alloc_path();
881	if (!path)
882	return -ENOMEM;
883
884	bytenr -= BTRFS_I(reloc_inode)->reloc_block_group_start;
885	ret = btrfs_lookup_file_extent(NULL, root, path,
886	btrfs_ino(BTRFS_I(reloc_inode)), bytenr, 0);
887	if (ret < 0)
888	return ret;
889	if (ret > 0)
890	return -ENOENT;
891
892	leaf = path->nodes[0];
893	fi = btrfs_item_ptr(leaf, path->slots[0],
894	struct btrfs_file_extent_item);
895	if (unlikely(btrfs_file_extent_type(leaf, fi) == BTRFS_FILE_EXTENT_INLINE)) {
896	btrfs_print_leaf(leaf);
897	btrfs_err(fs_info,
898	"unexpected inline file extent item for data reloc inode %llu key offset %llu",
899	btrfs_ino(BTRFS_I(reloc_inode)), bytenr);
900	return -EUCLEAN;
901	}
902
903	/*
904	* The cluster-boundary key searched above is always written by
905	* relocation with offset 0: either by insert_prealloc_file_extent()
906	* (memsets the stack item to 0) or by the front portion of a partial
907	* writeback (offset=0 by construction). A non-zero value here means
908	* the on-disk leaf does not match what relocation wrote, i.e.
909	* corruption. The other encoding fields are caught earlier by
910	* tree-checker's check_extent_data_item().
911	*/
912	if (unlikely(btrfs_file_extent_offset(leaf, fi))) {
913	btrfs_print_leaf(leaf);
914	btrfs_err(fs_info,
915	"unexpected non-zero offset in file extent item for data reloc inode %llu key offset %llu offset %llu",
916	btrfs_ino(BTRFS_I(reloc_inode)), bytenr,
917	btrfs_file_extent_offset(leaf, fi));
918	return -EUCLEAN;
919	}
920
921	if (num_bytes != btrfs_file_extent_disk_num_bytes(leaf, fi))
922	return -EINVAL;
923
924	*new_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
925	return 0;
926	}
927
928	/*
929	* update file extent items in the tree leaf to point to
930	* the new locations.
931	*/
932	static noinline_for_stack
933	int replace_file_extents(struct btrfs_trans_handle *trans,
934	struct reloc_control *rc,
935	struct btrfs_root *root,
936	struct extent_buffer *leaf)
937	{
938	struct btrfs_fs_info *fs_info = root->fs_info;
939	struct btrfs_key key;
940	struct btrfs_file_extent_item *fi;
941	struct btrfs_inode *inode = NULL;
942	u64 parent;
943	u64 bytenr;
944	u64 new_bytenr = 0;
945	u64 num_bytes;
946	u64 end;
947	u32 nritems;
948	u32 i;
949	int ret = 0;
950	bool first = true;
951
952	if (rc->stage != UPDATE_DATA_PTRS)
953	return 0;
954
955	/* reloc trees always use full backref */
956	if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID)
957	parent = leaf->start;
958	else
959	parent = 0;
960
961	nritems = btrfs_header_nritems(leaf);
962	for (i = 0; i < nritems; i++) {
963	struct btrfs_ref ref = { 0 };
964
965	cond_resched();
966	btrfs_item_key_to_cpu(leaf, &key, i);
967	if (key.type != BTRFS_EXTENT_DATA_KEY)
968	continue;
969	fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
970	if (btrfs_file_extent_type(leaf, fi) ==
971	BTRFS_FILE_EXTENT_INLINE)
972	continue;
973	bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
974	num_bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
975	if (bytenr == 0)
976	continue;
977	if (!in_range(bytenr, rc->block_group->start,
978	rc->block_group->length))
979	continue;
980
981	/*
982	* if we are modifying block in fs tree, wait for read_folio
983	* to complete and drop the extent cache
984	*/
985	if (btrfs_root_id(root) != BTRFS_TREE_RELOC_OBJECTID) {
986	if (first) {
987	inode = btrfs_find_first_inode(root, key.objectid);
988	first = false;
989	} else if (inode && btrfs_ino(inode) < key.objectid) {
990	btrfs_add_delayed_iput(inode);
991	inode = btrfs_find_first_inode(root, key.objectid);
992	}
993	if (inode && btrfs_ino(inode) == key.objectid) {
994	struct extent_state *cached_state = NULL;
995
996	end = key.offset +
997	btrfs_file_extent_num_bytes(leaf, fi);
998	WARN_ON(!IS_ALIGNED(key.offset,
999	fs_info->sectorsize));
1000	WARN_ON(!IS_ALIGNED(end, fs_info->sectorsize));
1001	end--;
1002	/* Take mmap lock to serialize with reflinks. */
1003	if (!down_read_trylock(&inode->i_mmap_lock))
1004	continue;
1005	ret = btrfs_try_lock_extent(&inode->io_tree, key.offset,
1006	end, &cached_state);
1007	if (!ret) {
1008	up_read(&inode->i_mmap_lock);
1009	continue;
1010	}
1011
1012	btrfs_drop_extent_map_range(inode, key.offset, end, true);
1013	btrfs_unlock_extent(&inode->io_tree, key.offset, end,
1014	&cached_state);
1015	up_read(&inode->i_mmap_lock);
1016	}
1017	}
1018
1019	ret = get_new_location(rc->data_inode, &new_bytenr,
1020	bytenr, num_bytes);
1021	if (ret) {
1022	/*
1023	* Don't have to abort since we've not changed anything
1024	* in the file extent yet.
1025	*/
1026	break;
1027	}
1028
1029	btrfs_set_file_extent_disk_bytenr(leaf, fi, new_bytenr);
1030
1031	key.offset -= btrfs_file_extent_offset(leaf, fi);
1032	ref.action = BTRFS_ADD_DELAYED_REF;
1033	ref.bytenr = new_bytenr;
1034	ref.num_bytes = num_bytes;
1035	ref.parent = parent;
1036	ref.owning_root = btrfs_root_id(root);
1037	ref.ref_root = btrfs_header_owner(leaf);
1038	btrfs_init_data_ref(&ref, key.objectid, key.offset,
1039	btrfs_root_id(root), false);
1040	ret = btrfs_inc_extent_ref(trans, &ref);
1041	if (unlikely(ret)) {
1042	btrfs_abort_transaction(trans, ret);
1043	break;
1044	}
1045
1046	ref.action = BTRFS_DROP_DELAYED_REF;
1047	ref.bytenr = bytenr;
1048	ref.num_bytes = num_bytes;
1049	ref.parent = parent;
1050	ref.owning_root = btrfs_root_id(root);
1051	ref.ref_root = btrfs_header_owner(leaf);
1052	btrfs_init_data_ref(&ref, key.objectid, key.offset,
1053	btrfs_root_id(root), false);
1054	ret = btrfs_free_extent(trans, &ref);
1055	if (unlikely(ret)) {
1056	btrfs_abort_transaction(trans, ret);
1057	break;
1058	}
1059	}
1060	if (inode)
1061	btrfs_add_delayed_iput(inode);
1062	return ret;
1063	}
1064
1065	static noinline_for_stack int memcmp_node_keys(const struct extent_buffer *eb,
1066	int slot, const struct btrfs_path *path,
1067	int level)
1068	{
1069	struct btrfs_disk_key key1;
1070	struct btrfs_disk_key key2;
1071	btrfs_node_key(eb, &key1, slot);
1072	btrfs_node_key(path->nodes[level], &key2, path->slots[level]);
1073	return memcmp(&key1, &key2, sizeof(key1));
1074	}
1075
1076	/*
1077	* try to replace tree blocks in fs tree with the new blocks
1078	* in reloc tree. tree blocks haven't been modified since the
1079	* reloc tree was create can be replaced.
1080	*
1081	* if a block was replaced, level of the block + 1 is returned.
1082	* if no block got replaced, 0 is returned. if there are other
1083	* errors, a negative error number is returned.
1084	*/
1085	static noinline_for_stack
1086	int replace_path(struct btrfs_trans_handle trans, struct reloc_control rc,
1087	struct btrfs_root dest, struct btrfs_root src,
1088	struct btrfs_path path, struct btrfs_key next_key,
1089	int lowest_level, int max_level)
1090	{
1091	struct btrfs_fs_info *fs_info = dest->fs_info;
1092	struct extent_buffer *eb;
1093	struct extent_buffer *parent;
1094	struct btrfs_ref ref = { 0 };
1095	struct btrfs_key key;
1096	u64 old_bytenr;
1097	u64 new_bytenr;
1098	u64 old_ptr_gen;
1099	u64 new_ptr_gen;
1100	u64 last_snapshot;
1101	u32 blocksize;
1102	bool cow = false;
1103	int level;
1104	int ret;
1105	int slot;
1106
1107	ASSERT(btrfs_root_id(src) == BTRFS_TREE_RELOC_OBJECTID);
1108	ASSERT(btrfs_root_id(dest) != BTRFS_TREE_RELOC_OBJECTID);
1109
1110	last_snapshot = btrfs_root_last_snapshot(&src->root_item);
1111	again:
1112	slot = path->slots[lowest_level];
1113	btrfs_node_key_to_cpu(path->nodes[lowest_level], &key, slot);
1114
1115	eb = btrfs_lock_root_node(dest);
1116	level = btrfs_header_level(eb);
1117
1118	if (level < lowest_level) {
1119	btrfs_tree_unlock(eb);
1120	free_extent_buffer(eb);
1121	return 0;
1122	}
1123
1124	if (cow) {
1125	ret = btrfs_cow_block(trans, dest, eb, NULL, 0, &eb,
1126	BTRFS_NESTING_COW);
1127	if (ret) {
1128	btrfs_tree_unlock(eb);
1129	free_extent_buffer(eb);
1130	return ret;
1131	}
1132	}
1133
1134	if (next_key) {
1135	next_key->objectid = (u64)-1;
1136	next_key->type = (u8)-1;
1137	next_key->offset = (u64)-1;
1138	}
1139
1140	parent = eb;
1141	while (1) {
1142	level = btrfs_header_level(parent);
1143	ASSERT(level >= lowest_level);
1144
1145	ret = btrfs_bin_search(parent, 0, &key, &slot);
1146	if (ret < 0)
1147	break;
1148	if (ret && slot > 0)
1149	slot--;
1150
1151	if (next_key && slot + 1 < btrfs_header_nritems(parent))
1152	btrfs_node_key_to_cpu(parent, next_key, slot + 1);
1153
1154	old_bytenr = btrfs_node_blockptr(parent, slot);
1155	blocksize = fs_info->nodesize;
1156	old_ptr_gen = btrfs_node_ptr_generation(parent, slot);
1157
1158	if (level <= max_level) {
1159	eb = path->nodes[level];
1160	new_bytenr = btrfs_node_blockptr(eb,
1161	path->slots[level]);
1162	new_ptr_gen = btrfs_node_ptr_generation(eb,
1163	path->slots[level]);
1164	} else {
1165	new_bytenr = 0;
1166	new_ptr_gen = 0;
1167	}
1168
1169	if (WARN_ON(new_bytenr > 0 && new_bytenr == old_bytenr)) {
1170	ret = level;
1171	break;
1172	}
1173
1174	if (new_bytenr == 0 \|\| old_ptr_gen > last_snapshot \|\|
1175	memcmp_node_keys(parent, slot, path, level)) {
1176	if (level <= lowest_level) {
1177	ret = 0;
1178	break;
1179	}
1180
1181	eb = btrfs_read_node_slot(parent, slot);
1182	if (IS_ERR(eb)) {
1183	ret = PTR_ERR(eb);
1184	break;
1185	}
1186	btrfs_tree_lock(eb);
1187	if (cow) {
1188	ret = btrfs_cow_block(trans, dest, eb, parent,
1189	slot, &eb,
1190	BTRFS_NESTING_COW);
1191	if (ret) {
1192	btrfs_tree_unlock(eb);
1193	free_extent_buffer(eb);
1194	break;
1195	}
1196	}
1197
1198	btrfs_tree_unlock(parent);
1199	free_extent_buffer(parent);
1200
1201	parent = eb;
1202	continue;
1203	}
1204
1205	if (!cow) {
1206	btrfs_tree_unlock(parent);
1207	free_extent_buffer(parent);
1208	cow = true;
1209	goto again;
1210	}
1211
1212	btrfs_node_key_to_cpu(path->nodes[level], &key,
1213	path->slots[level]);
1214	btrfs_release_path(path);
1215
1216	path->lowest_level = level;
1217	set_bit(BTRFS_ROOT_RESET_LOCKDEP_CLASS, &src->state);
1218	ret = btrfs_search_slot(trans, src, &key, path, 0, 1);
1219	clear_bit(BTRFS_ROOT_RESET_LOCKDEP_CLASS, &src->state);
1220	path->lowest_level = 0;
1221	if (ret) {
1222	if (ret > 0)
1223	ret = -ENOENT;
1224	break;
1225	}
1226
1227	/*
1228	* Info qgroup to trace both subtrees.
1229	*
1230	* We must trace both trees.
1231	* 1) Tree reloc subtree
1232	* If not traced, we will leak data numbers
1233	* 2) Fs subtree
1234	* If not traced, we will double count old data
1235	*
1236	* We don't scan the subtree right now, but only record
1237	* the swapped tree blocks.
1238	* The real subtree rescan is delayed until we have new
1239	* CoW on the subtree root node before transaction commit.
1240	*/
1241	ret = btrfs_qgroup_add_swapped_blocks(dest,
1242	rc->block_group, parent, slot,
1243	path->nodes[level], path->slots[level],
1244	last_snapshot);
1245	if (ret < 0)
1246	break;
1247	/*
1248	* swap blocks in fs tree and reloc tree.
1249	*/
1250	btrfs_set_node_blockptr(parent, slot, new_bytenr);
1251	btrfs_set_node_ptr_generation(parent, slot, new_ptr_gen);
1252
1253	btrfs_set_node_blockptr(path->nodes[level],
1254	path->slots[level], old_bytenr);
1255	btrfs_set_node_ptr_generation(path->nodes[level],
1256	path->slots[level], old_ptr_gen);
1257
1258	ref.action = BTRFS_ADD_DELAYED_REF;
1259	ref.bytenr = old_bytenr;
1260	ref.num_bytes = blocksize;
1261	ref.parent = path->nodes[level]->start;
1262	ref.owning_root = btrfs_root_id(src);
1263	ref.ref_root = btrfs_root_id(src);
1264	btrfs_init_tree_ref(&ref, level - 1, 0, true);
1265	ret = btrfs_inc_extent_ref(trans, &ref);
1266	if (unlikely(ret)) {
1267	btrfs_abort_transaction(trans, ret);
1268	break;
1269	}
1270
1271	ref.action = BTRFS_ADD_DELAYED_REF;
1272	ref.bytenr = new_bytenr;
1273	ref.num_bytes = blocksize;
1274	ref.parent = 0;
1275	ref.owning_root = btrfs_root_id(dest);
1276	ref.ref_root = btrfs_root_id(dest);
1277	btrfs_init_tree_ref(&ref, level - 1, 0, true);
1278	ret = btrfs_inc_extent_ref(trans, &ref);
1279	if (unlikely(ret)) {
1280	btrfs_abort_transaction(trans, ret);
1281	break;
1282	}
1283
1284	/* We don't know the real owning_root, use 0. */
1285	ref.action = BTRFS_DROP_DELAYED_REF;
1286	ref.bytenr = new_bytenr;
1287	ref.num_bytes = blocksize;
1288	ref.parent = path->nodes[level]->start;
1289	ref.owning_root = 0;
1290	ref.ref_root = btrfs_root_id(src);
1291	btrfs_init_tree_ref(&ref, level - 1, 0, true);
1292	ret = btrfs_free_extent(trans, &ref);
1293	if (unlikely(ret)) {
1294	btrfs_abort_transaction(trans, ret);
1295	break;
1296	}
1297
1298	/* We don't know the real owning_root, use 0. */
1299	ref.action = BTRFS_DROP_DELAYED_REF;
1300	ref.bytenr = old_bytenr;
1301	ref.num_bytes = blocksize;
1302	ref.parent = 0;
1303	ref.owning_root = 0;
1304	ref.ref_root = btrfs_root_id(dest);
1305	btrfs_init_tree_ref(&ref, level - 1, 0, true);
1306	ret = btrfs_free_extent(trans, &ref);
1307	if (unlikely(ret)) {
1308	btrfs_abort_transaction(trans, ret);
1309	break;
1310	}
1311
1312	btrfs_unlock_up_safe(path, 0);
1313
1314	ret = level;
1315	break;
1316	}
1317	btrfs_tree_unlock(parent);
1318	free_extent_buffer(parent);
1319	return ret;
1320	}
1321
1322	/*
1323	* helper to find next relocated block in reloc tree
1324	*/
1325	static noinline_for_stack
1326	int walk_up_reloc_tree(struct btrfs_root root, struct btrfs_path path,
1327	int *level)
1328	{
1329	struct extent_buffer *eb;
1330	int i;
1331	u64 last_snapshot;
1332	u32 nritems;
1333
1334	last_snapshot = btrfs_root_last_snapshot(&root->root_item);
1335
1336	for (i = 0; i < *level; i++) {
1337	free_extent_buffer(path->nodes[i]);
1338	path->nodes[i] = NULL;
1339	}
1340
1341	for (i = *level; i < BTRFS_MAX_LEVEL && path->nodes[i]; i++) {
1342	eb = path->nodes[i];
1343	nritems = btrfs_header_nritems(eb);
1344	while (path->slots[i] + 1 < nritems) {
1345	path->slots[i]++;
1346	if (btrfs_node_ptr_generation(eb, path->slots[i]) <=
1347	last_snapshot)
1348	continue;
1349
1350	*level = i;
1351	return 0;
1352	}
1353	free_extent_buffer(path->nodes[i]);
1354	path->nodes[i] = NULL;
1355	}
1356	return 1;
1357	}
1358
1359	/*
1360	* walk down reloc tree to find relocated block of lowest level
1361	*/
1362	static noinline_for_stack
1363	int walk_down_reloc_tree(struct btrfs_root root, struct btrfs_path path,
1364	int *level)
1365	{
1366	struct extent_buffer *eb = NULL;
1367	int i;
1368	u64 ptr_gen = 0;
1369	u64 last_snapshot;
1370	u32 nritems;
1371
1372	last_snapshot = btrfs_root_last_snapshot(&root->root_item);
1373
1374	for (i = *level; i > 0; i--) {
1375	eb = path->nodes[i];
1376	nritems = btrfs_header_nritems(eb);
1377	while (path->slots[i] < nritems) {
1378	ptr_gen = btrfs_node_ptr_generation(eb, path->slots[i]);
1379	if (ptr_gen > last_snapshot)
1380	break;
1381	path->slots[i]++;
1382	}
1383	if (path->slots[i] >= nritems) {
1384	if (i == *level)
1385	break;
1386	*level = i + 1;
1387	return 0;
1388	}
1389	if (i == 1) {
1390	*level = i;
1391	return 0;
1392	}
1393
1394	eb = btrfs_read_node_slot(eb, path->slots[i]);
1395	if (IS_ERR(eb))
1396	return PTR_ERR(eb);
1397	BUG_ON(btrfs_header_level(eb) != i - 1);
1398	path->nodes[i - 1] = eb;
1399	path->slots[i - 1] = 0;
1400	}
1401	return 1;
1402	}
1403
1404	/*
1405	* invalidate extent cache for file extents whose key in range of
1406	* [min_key, max_key)
1407	*/
1408	static int invalidate_extent_cache(struct btrfs_root *root,
1409	const struct btrfs_key *min_key,
1410	const struct btrfs_key *max_key)
1411	{
1412	struct btrfs_fs_info *fs_info = root->fs_info;
1413	struct btrfs_inode *inode = NULL;
1414	u64 objectid;
1415	u64 start, end;
1416	u64 ino;
1417
1418	objectid = min_key->objectid;
1419	while (1) {
1420	struct extent_state *cached_state = NULL;
1421
1422	cond_resched();
1423	if (inode)
1424	iput(&inode->vfs_inode);
1425
1426	if (objectid > max_key->objectid)
1427	break;
1428
1429	inode = btrfs_find_first_inode(root, objectid);
1430	if (!inode)
1431	break;
1432	ino = btrfs_ino(inode);
1433
1434	if (ino > max_key->objectid) {
1435	iput(&inode->vfs_inode);
1436	break;
1437	}
1438
1439	objectid = ino + 1;
1440	if (!S_ISREG(inode->vfs_inode.i_mode))
1441	continue;
1442
1443	if (unlikely(min_key->objectid == ino)) {
1444	if (min_key->type > BTRFS_EXTENT_DATA_KEY)
1445	continue;
1446	if (min_key->type < BTRFS_EXTENT_DATA_KEY)
1447	start = 0;
1448	else {
1449	start = min_key->offset;
1450	WARN_ON(!IS_ALIGNED(start, fs_info->sectorsize));
1451	}
1452	} else {
1453	start = 0;
1454	}
1455
1456	if (unlikely(max_key->objectid == ino)) {
1457	if (max_key->type < BTRFS_EXTENT_DATA_KEY)
1458	continue;
1459	if (max_key->type > BTRFS_EXTENT_DATA_KEY) {
1460	end = (u64)-1;
1461	} else {
1462	if (max_key->offset == 0)
1463	continue;
1464	end = max_key->offset;
1465	WARN_ON(!IS_ALIGNED(end, fs_info->sectorsize));
1466	end--;
1467	}
1468	} else {
1469	end = (u64)-1;
1470	}
1471
1472	/* the lock_extent waits for read_folio to complete */
1473	btrfs_lock_extent(&inode->io_tree, start, end, &cached_state);
1474	btrfs_drop_extent_map_range(inode, start, end, true);
1475	btrfs_unlock_extent(&inode->io_tree, start, end, &cached_state);
1476	}
1477	return 0;
1478	}
1479
1480	static int find_next_key(struct btrfs_path *path, int level,
1481	struct btrfs_key *key)
1482
1483	{
1484	while (level < BTRFS_MAX_LEVEL) {
1485	if (!path->nodes[level])
1486	break;
1487	if (path->slots[level] + 1 <
1488	btrfs_header_nritems(path->nodes[level])) {
1489	btrfs_node_key_to_cpu(path->nodes[level], key,
1490	path->slots[level] + 1);
1491	return 0;
1492	}
1493	level++;
1494	}
1495	return 1;
1496	}
1497
1498	/*
1499	* Insert current subvolume into reloc_control::dirty_subvol_roots
1500	*/
1501	static int insert_dirty_subvol(struct btrfs_trans_handle *trans,
1502	struct reloc_control *rc,
1503	struct btrfs_root *root)
1504	{
1505	struct btrfs_root *reloc_root = root->reloc_root;
1506	struct btrfs_root_item *reloc_root_item;
1507	int ret;
1508
1509	/* @root must be a subvolume tree root with a valid reloc tree */
1510	ASSERT(btrfs_root_id(root) != BTRFS_TREE_RELOC_OBJECTID);
1511	ASSERT(reloc_root);
1512
1513	reloc_root_item = &reloc_root->root_item;
1514	memset(&reloc_root_item->drop_progress, 0,
1515	sizeof(reloc_root_item->drop_progress));
1516	btrfs_set_root_drop_level(reloc_root_item, 0);
1517	btrfs_set_root_refs(reloc_root_item, 0);
1518	ret = btrfs_update_reloc_root(trans, root);
1519	if (ret)
1520	return ret;
1521
1522	if (list_empty(&root->reloc_dirty_list)) {
1523	btrfs_grab_root(root);
1524	list_add_tail(&root->reloc_dirty_list, &rc->dirty_subvol_roots);
1525	}
1526
1527	return 0;
1528	}
1529
1530	static void clear_reloc_root(struct btrfs_root *root)
1531	{
1532	root->reloc_root = NULL;
1533	/*
1534	* Need barrier to ensure clear_bit() only happens after
1535	* root->reloc_root = NULL. Pairs with have_reloc_root().
1536	*/
1537	smp_wmb();
1538	clear_bit(BTRFS_ROOT_DEAD_RELOC_TREE, &root->state);
1539	}
1540
1541	/* Drop the reloc trees of a relocation that is being deferred and retried. */
1542	static void abort_reloc_roots(struct reloc_control rc, struct list_head list)
1543	{
1544	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
1545	struct btrfs_root reloc_root, tmp;
1546
1547	list_for_each_entry_safe(reloc_root, tmp, list, root_list) {
1548	struct btrfs_root *root;
1549
1550	root = btrfs_get_fs_root(fs_info, reloc_root->root_key.offset, false);
1551	if (!IS_ERR(root)) {
1552	if (root->reloc_root == reloc_root) {
1553	clear_reloc_root(root);
1554	btrfs_put_root(reloc_root);
1555	}
1556	btrfs_put_root(root);
1557	}
1558
1559	btrfs_set_root_refs(&reloc_root->root_item, 0);
1560	memset(&reloc_root->root_item.drop_progress, 0, sizeof(struct btrfs_disk_key));
1561	btrfs_set_root_drop_level(&reloc_root->root_item, 0);
1562
1563	list_del_init(&reloc_root->root_list);
1564	list_add_tail(&reloc_root->reloc_dirty_list, &rc->dirty_subvol_roots);
1565	}
1566	}
1567
1568	static int clean_dirty_subvols(struct reloc_control *rc)
1569	{
1570	struct btrfs_root *root;
1571	struct btrfs_root *next;
1572	int ret = 0;
1573	int ret2;
1574
1575	list_for_each_entry_safe(root, next, &rc->dirty_subvol_roots,
1576	reloc_dirty_list) {
1577	if (btrfs_root_id(root) != BTRFS_TREE_RELOC_OBJECTID) {
1578	/* Merged subvolume, cleanup its reloc root */
1579	struct btrfs_root *reloc_root = root->reloc_root;
1580
1581	list_del_init(&root->reloc_dirty_list);
1582	clear_reloc_root(root);
1583	if (reloc_root) {
1584	/*
1585	* btrfs_drop_snapshot drops our ref we hold for
1586	* ->reloc_root. If it fails however we must
1587	* drop the ref ourselves.
1588	*/
1589	ret2 = btrfs_drop_snapshot(reloc_root, false, true);
1590	if (ret2 < 0) {
1591	btrfs_put_root(reloc_root);
1592	if (!ret)
1593	ret = ret2;
1594	}
1595	}
1596	btrfs_put_root(root);
1597	} else {
1598	/* Orphan reloc tree, just clean it up */
1599	ret2 = btrfs_drop_snapshot(root, false, true);
1600	if (ret2 < 0) {
1601	btrfs_put_root(root);
1602	if (!ret)
1603	ret = ret2;
1604	}
1605	}
1606	}
1607	return ret;
1608	}
1609
1610	/*
1611	* merge the relocated tree blocks in reloc tree with corresponding
1612	* fs tree.
1613	*/
1614	static noinline_for_stack int merge_reloc_root(struct reloc_control *rc,
1615	struct btrfs_root *root)
1616	{
1617	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
1618	struct btrfs_key key;
1619	struct btrfs_key next_key;
1620	struct btrfs_trans_handle *trans = NULL;
1621	struct btrfs_root *reloc_root;
1622	struct btrfs_root_item *root_item;
1623	struct btrfs_path *path;
1624	struct extent_buffer *leaf;
1625	int reserve_level;
1626	int level;
1627	int max_level;
1628	bool replaced = false;
1629	int ret = 0;
1630	u32 min_reserved;
1631
1632	path = btrfs_alloc_path();
1633	if (!path)
1634	return -ENOMEM;
1635	path->reada = READA_FORWARD;
1636
1637	reloc_root = root->reloc_root;
1638	root_item = &reloc_root->root_item;
1639
1640	if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
1641	level = btrfs_root_level(root_item);
1642	refcount_inc(&reloc_root->node->refs);
1643	path->nodes[level] = reloc_root->node;
1644	path->slots[level] = 0;
1645	} else {
1646	btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
1647
1648	level = btrfs_root_drop_level(root_item);
1649	BUG_ON(level == 0);
1650	path->lowest_level = level;
1651	ret = btrfs_search_slot(NULL, reloc_root, &key, path, 0, 0);
1652	path->lowest_level = 0;
1653	if (ret < 0) {
1654	btrfs_free_path(path);
1655	return ret;
1656	}
1657
1658	btrfs_node_key_to_cpu(path->nodes[level], &next_key,
1659	path->slots[level]);
1660	WARN_ON(memcmp(&key, &next_key, sizeof(key)));
1661
1662	btrfs_unlock_up_safe(path, 0);
1663	}
1664
1665	/*
1666	* In merge_reloc_root(), we modify the upper level pointer to swap the
1667	* tree blocks between reloc tree and subvolume tree. Thus for tree
1668	* block COW, we COW at most from level 1 to root level for each tree.
1669	*
1670	* Thus the needed metadata size is at most root_level * nodesize,
1671	* and * 2 since we have two trees to COW.
1672	*/
1673	reserve_level = max_t(int, 1, btrfs_root_level(root_item));
1674	min_reserved = (reserve_level << fs_info->nodesize_bits) * 2;
1675	memset(&next_key, 0, sizeof(next_key));
1676
1677	while (1) {
1678	ret = btrfs_block_rsv_refill(rc->block_rsv, min_reserved,
1679	BTRFS_RESERVE_FLUSH_LIMIT);
1680	if (ret)
1681	goto out;
1682	trans = btrfs_start_transaction(root, 0);
1683	if (IS_ERR(trans)) {
1684	ret = PTR_ERR(trans);
1685	trans = NULL;
1686	goto out;
1687	}
1688
1689	/*
1690	* At this point we no longer have a reloc_control, so we can't
1691	* depend on btrfs_init_reloc_root to update our last_trans.
1692	*
1693	* But that's ok, we started the trans handle on our
1694	* corresponding fs_root, which means it's been added to the
1695	* dirty list. At commit time we'll still call
1696	* btrfs_update_reloc_root() and update our root item
1697	* appropriately.
1698	*/
1699	btrfs_set_root_last_trans(reloc_root, trans->transid);
1700	trans->block_rsv = rc->block_rsv;
1701
1702	replaced = false;
1703	max_level = level;
1704
1705	ret = walk_down_reloc_tree(reloc_root, path, &level);
1706	if (ret < 0)
1707	goto out;
1708	if (ret > 0)
1709	break;
1710
1711	if (!find_next_key(path, level, &key) &&
1712	btrfs_comp_cpu_keys(&next_key, &key) >= 0) {
1713	ret = 0;
1714	} else {
1715	ret = replace_path(trans, rc, root, reloc_root, path,
1716	&next_key, level, max_level);
1717	}
1718	if (ret < 0)
1719	goto out;
1720	if (ret > 0) {
1721	level = ret;
1722	btrfs_node_key_to_cpu(path->nodes[level], &key,
1723	path->slots[level]);
1724	replaced = true;
1725	}
1726
1727	ret = walk_up_reloc_tree(reloc_root, path, &level);
1728	if (ret > 0)
1729	break;
1730
1731	BUG_ON(level == 0);
1732	/*
1733	* save the merging progress in the drop_progress.
1734	* this is OK since root refs == 1 in this case.
1735	*/
1736	btrfs_node_key(path->nodes[level], &root_item->drop_progress,
1737	path->slots[level]);
1738	btrfs_set_root_drop_level(root_item, level);
1739
1740	btrfs_end_transaction_throttle(trans);
1741	trans = NULL;
1742
1743	btrfs_btree_balance_dirty(fs_info);
1744
1745	if (replaced && rc->stage == UPDATE_DATA_PTRS)
1746	invalidate_extent_cache(root, &key, &next_key);
1747	}
1748
1749	/*
1750	* handle the case only one block in the fs tree need to be
1751	* relocated and the block is tree root.
1752	*/
1753	leaf = btrfs_lock_root_node(root);
1754	ret = btrfs_cow_block(trans, root, leaf, NULL, 0, &leaf,
1755	BTRFS_NESTING_COW);
1756	btrfs_tree_unlock(leaf);
1757	free_extent_buffer(leaf);
1758	out:
1759	btrfs_free_path(path);
1760
1761	if (ret == 0) {
1762	ret = insert_dirty_subvol(trans, rc, root);
1763	if (ret)
1764	btrfs_abort_transaction(trans, ret);
1765	}
1766
1767	if (trans)
1768	btrfs_end_transaction_throttle(trans);
1769
1770	btrfs_btree_balance_dirty(fs_info);
1771
1772	if (replaced && rc->stage == UPDATE_DATA_PTRS)
1773	invalidate_extent_cache(root, &key, &next_key);
1774
1775	return ret;
1776	}
1777
1778	static noinline_for_stack
1779	int prepare_to_merge(struct reloc_control *rc, int err)
1780	{
1781	struct btrfs_root *root = rc->extent_root;
1782	struct btrfs_fs_info *fs_info = root->fs_info;
1783	struct btrfs_root *reloc_root;
1784	struct btrfs_trans_handle *trans;
1785	LIST_HEAD(reloc_roots);
1786	u64 num_bytes = 0;
1787	int ret;
1788
1789	mutex_lock(&fs_info->reloc_mutex);
1790	rc->merging_rsv_size += fs_info->nodesize * (BTRFS_MAX_LEVEL - 1) * 2;
1791	rc->merging_rsv_size += rc->nodes_relocated * 2;
1792	mutex_unlock(&fs_info->reloc_mutex);
1793
1794	again:
1795	if (!err) {
1796	num_bytes = rc->merging_rsv_size;
1797	ret = btrfs_block_rsv_add(rc->block_rsv, num_bytes,
1798	BTRFS_RESERVE_FLUSH_ALL);
1799	if (ret)
1800	err = ret;
1801	}
1802
1803	trans = btrfs_join_transaction(rc->extent_root);
1804	if (IS_ERR(trans)) {
1805	if (!err)
1806	btrfs_block_rsv_release(fs_info, rc->block_rsv,
1807	num_bytes, NULL);
1808	return PTR_ERR(trans);
1809	}
1810
1811	if (!err) {
1812	if (num_bytes != rc->merging_rsv_size) {
1813	btrfs_end_transaction(trans);
1814	btrfs_block_rsv_release(fs_info, rc->block_rsv,
1815	num_bytes, NULL);
1816	goto again;
1817	}
1818	}
1819
1820	rc->merge_reloc_tree = true;
1821
1822	while (!list_empty(&rc->reloc_roots)) {
1823	reloc_root = list_first_entry(&rc->reloc_roots,
1824	struct btrfs_root, root_list);
1825	list_del_init(&reloc_root->root_list);
1826
1827	root = btrfs_get_fs_root(fs_info, reloc_root->root_key.offset,
1828	false);
1829	if (IS_ERR(root)) {
1830	/*
1831	* Even if we have an error we need this reloc root
1832	* back on our list so we can clean up properly.
1833	*/
1834	list_add(&reloc_root->root_list, &reloc_roots);
1835	btrfs_abort_transaction(trans, (int)PTR_ERR(root));
1836	if (!err)
1837	err = PTR_ERR(root);
1838	break;
1839	}
1840
1841	if (unlikely(root->reloc_root != reloc_root)) {
1842	if (root->reloc_root) {
1843	btrfs_err(fs_info,
1844	"reloc tree mismatch, root %lld has reloc root key (%lld %u %llu) gen %llu, expect reloc root key (%lld %u %llu) gen %llu",
1845	btrfs_root_id(root),
1846	btrfs_root_id(root->reloc_root),
1847	root->reloc_root->root_key.type,
1848	root->reloc_root->root_key.offset,
1849	btrfs_root_generation(
1850	&root->reloc_root->root_item),
1851	btrfs_root_id(reloc_root),
1852	reloc_root->root_key.type,
1853	reloc_root->root_key.offset,
1854	btrfs_root_generation(
1855	&reloc_root->root_item));
1856	} else {
1857	btrfs_err(fs_info,
1858	"reloc tree mismatch, root %lld has no reloc root, expect reloc root key (%lld %u %llu) gen %llu",
1859	btrfs_root_id(root),
1860	btrfs_root_id(reloc_root),
1861	reloc_root->root_key.type,
1862	reloc_root->root_key.offset,
1863	btrfs_root_generation(
1864	&reloc_root->root_item));
1865	}
1866	list_add(&reloc_root->root_list, &reloc_roots);
1867	btrfs_put_root(root);
1868	btrfs_abort_transaction(trans, -EUCLEAN);
1869	if (!err)
1870	err = -EUCLEAN;
1871	break;
1872	}
1873
1874	/*
1875	* set reference count to 1, so btrfs_recover_relocation
1876	* knows it should resumes merging
1877	*/
1878	if (!err)
1879	btrfs_set_root_refs(&reloc_root->root_item, 1);
1880	ret = btrfs_update_reloc_root(trans, root);
1881
1882	/*
1883	* Even if we have an error we need this reloc root back on our
1884	* list so we can clean up properly.
1885	*/
1886	list_add(&reloc_root->root_list, &reloc_roots);
1887	btrfs_put_root(root);
1888
1889	if (unlikely(ret)) {
1890	btrfs_abort_transaction(trans, ret);
1891	if (!err)
1892	err = ret;
1893	break;
1894	}
1895	}
1896
1897	list_splice(&reloc_roots, &rc->reloc_roots);
1898
1899	if (!err)
1900	err = btrfs_commit_transaction(trans);
1901	else
1902	btrfs_end_transaction(trans);
1903	return err;
1904	}
1905
1906	static noinline_for_stack int merge_reloc_roots(struct reloc_control *rc)
1907	{
1908	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
1909	struct btrfs_root *root;
1910	struct btrfs_root *reloc_root;
1911	LIST_HEAD(reloc_roots);
1912	bool found = false;
1913	int ret = 0;
1914	again:
1915	root = rc->extent_root;
1916
1917	/*
1918	* this serializes us with btrfs_record_root_in_transaction,
1919	* we have to make sure nobody is in the middle of
1920	* adding their roots to the list while we are
1921	* doing this splice
1922	*/
1923	mutex_lock(&fs_info->reloc_mutex);
1924	list_splice_init(&rc->reloc_roots, &reloc_roots);
1925	mutex_unlock(&fs_info->reloc_mutex);
1926
1927	while (!list_empty(&reloc_roots)) {
1928	found = true;
1929	reloc_root = list_first_entry(&reloc_roots, struct btrfs_root, root_list);
1930
1931	root = btrfs_get_fs_root(fs_info, reloc_root->root_key.offset,
1932	false);
1933	if (btrfs_root_refs(&reloc_root->root_item) > 0) {
1934	if (WARN_ON(IS_ERR(root))) {
1935	/*
1936	* For recovery we read the fs roots on mount,
1937	* and if we didn't find the root then we marked
1938	* the reloc root as a garbage root. For normal
1939	* relocation obviously the root should exist in
1940	* memory. However there's no reason we can't
1941	* handle the error properly here just in case.
1942	*/
1943	ret = PTR_ERR(root);
1944	goto out;
1945	}
1946	if (WARN_ON(root->reloc_root != reloc_root)) {
1947	/*
1948	* This can happen if on-disk metadata has some
1949	* corruption, e.g. bad reloc tree key offset.
1950	*/
1951	ret = -EINVAL;
1952	btrfs_put_root(root);
1953	goto out;
1954	}
1955	ret = merge_reloc_root(rc, root);
1956	if (ret) {
1957	/*
1958	* Clear the reloc root since below we will call
1959	* free_reloc_roots(), otherwise we leave
1960	* root->reloc_root pointing to a freed reloc
1961	* root and trigger a use-after-free during
1962	* unmount or elsewhere.
1963	*/
1964	clear_reloc_root(root);
1965	btrfs_put_root(root);
1966	/*
1967	* We are adding the reloc_root to the local
1968	* reloc_roots list, so we add a ref for this
1969	* list which will be dropped below by the call
1970	* to free_reloc_roots().
1971	*/
1972	if (list_empty(&reloc_root->root_list)) {
1973	list_add_tail(&reloc_root->root_list,
1974	&reloc_roots);
1975	btrfs_grab_root(reloc_root);
1976	}
1977	/* Now drop the ref for root->reloc_root. */
1978	btrfs_put_root(reloc_root);
1979	goto out;
1980	}
1981	btrfs_put_root(root);
1982	} else {
1983	if (!IS_ERR(root)) {
1984	if (root->reloc_root == reloc_root) {
1985	clear_reloc_root(root);
1986	/* Drop the ref for root->reloc_root. */
1987	btrfs_put_root(reloc_root);
1988	}
1989	btrfs_put_root(root);
1990	}
1991
1992	list_del_init(&reloc_root->root_list);
1993	/* Don't forget to queue this reloc root for cleanup */
1994	list_add_tail(&reloc_root->reloc_dirty_list,
1995	&rc->dirty_subvol_roots);
1996	}
1997	}
1998
1999	if (found) {
2000	found = false;
2001	goto again;
2002	}
2003	out:
2004	if (btrfs_is_zoned(fs_info) && ret == -EAGAIN) {
2005	abort_reloc_roots(rc, &reloc_roots);
2006
2007	/* New reloc root may be added. */
2008	mutex_lock(&fs_info->reloc_mutex);
2009	list_splice_init(&rc->reloc_roots, &reloc_roots);
2010	mutex_unlock(&fs_info->reloc_mutex);
2011	abort_reloc_roots(rc, &reloc_roots);
2012	} else if (ret) {
2013	btrfs_handle_fs_error(fs_info, ret, NULL);
2014	free_reloc_roots(&reloc_roots);
2015
2016	/* new reloc root may be added */
2017	mutex_lock(&fs_info->reloc_mutex);
2018	list_splice_init(&rc->reloc_roots, &reloc_roots);
2019	mutex_unlock(&fs_info->reloc_mutex);
2020	free_reloc_roots(&reloc_roots);
2021	}
2022
2023	/*
2024	* We used to have
2025	*
2026	* BUG_ON(!RB_EMPTY_ROOT(&rc->reloc_root_tree.rb_root));
2027	*
2028	* here, but it's wrong. If we fail to start the transaction in
2029	* prepare_to_merge() we will have only 0 ref reloc roots, none of which
2030	* have actually been removed from the reloc_root_tree rb tree. This is
2031	* fine because we're bailing here, and we hold a reference on the root
2032	* for the list that holds it, so these roots will be cleaned up when we
2033	* do the reloc_dirty_list afterwards. Meanwhile the root->reloc_root
2034	* will be cleaned up on unmount.
2035	*
2036	* The remaining nodes will be cleaned up by put_reloc_control().
2037	*/
2038	return ret;
2039	}
2040
2041	static void free_block_list(struct rb_root *blocks)
2042	{
2043	struct tree_block *block;
2044	struct rb_node *rb_node;
2045	while ((rb_node = rb_first(blocks))) {
2046	block = rb_entry(rb_node, struct tree_block, rb_node);
2047	rb_erase(rb_node, blocks);
2048	kfree(block);
2049	}
2050	}
2051
2052	static int record_reloc_root_in_trans(struct btrfs_trans_handle *trans,
2053	struct btrfs_root *reloc_root)
2054	{
2055	struct btrfs_fs_info *fs_info = reloc_root->fs_info;
2056	struct btrfs_root *root;
2057	int ret;
2058
2059	if (btrfs_get_root_last_trans(reloc_root) == trans->transid)
2060	return 0;
2061
2062	root = btrfs_get_fs_root(fs_info, reloc_root->root_key.offset, false);
2063
2064	/*
2065	* This should succeed, since we can't have a reloc root without having
2066	* already looked up the actual root and created the reloc root for this
2067	* root.
2068	*
2069	* However if there's some sort of corruption where we have a ref to a
2070	* reloc root without a corresponding root this could return ENOENT.
2071	*/
2072	if (IS_ERR(root)) {
2073	DEBUG_WARN("error %ld reading root for reloc root", PTR_ERR(root));
2074	return PTR_ERR(root);
2075	}
2076	if (unlikely(root->reloc_root != reloc_root)) {
2077	DEBUG_WARN("unexpected reloc root found");
2078	btrfs_err(fs_info,
2079	"root %llu has two reloc roots associated with it",
2080	reloc_root->root_key.offset);
2081	btrfs_put_root(root);
2082	return -EUCLEAN;
2083	}
2084	ret = btrfs_record_root_in_trans(trans, root);
2085	btrfs_put_root(root);
2086
2087	return ret;
2088	}
2089
2090	static noinline_for_stack
2091	struct btrfs_root select_reloc_root(struct btrfs_trans_handle trans,
2092	struct reloc_control *rc,
2093	struct btrfs_backref_node *node,
2094	struct btrfs_backref_edge *edges[])
2095	{
2096	struct btrfs_backref_node *next;
2097	struct btrfs_root *root;
2098	int index = 0;
2099	int ret;
2100
2101	next = walk_up_backref(node, edges, &index);
2102	root = next->root;
2103
2104	/*
2105	* If there is no root, then our references for this block are
2106	* incomplete, as we should be able to walk all the way up to a block
2107	* that is owned by a root.
2108	*
2109	* This path is only for SHAREABLE roots, so if we come upon a
2110	* non-SHAREABLE root then we have backrefs that resolve improperly.
2111	*
2112	* Both of these cases indicate file system corruption, or a bug in the
2113	* backref walking code.
2114	*/
2115	if (unlikely(!root)) {
2116	btrfs_err(trans->fs_info,
2117	"bytenr %llu doesn't have a backref path ending in a root",
2118	node->bytenr);
2119	return ERR_PTR(-EUCLEAN);
2120	}
2121	if (unlikely(!test_bit(BTRFS_ROOT_SHAREABLE, &root->state))) {
2122	btrfs_err(trans->fs_info,
2123	"bytenr %llu has multiple refs with one ending in a non-shareable root",
2124	node->bytenr);
2125	return ERR_PTR(-EUCLEAN);
2126	}
2127
2128	if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID) {
2129	ret = record_reloc_root_in_trans(trans, root);
2130	if (ret)
2131	return ERR_PTR(ret);
2132	goto found;
2133	}
2134
2135	ret = btrfs_record_root_in_trans(trans, root);
2136	if (ret)
2137	return ERR_PTR(ret);
2138	root = root->reloc_root;
2139
2140	/*
2141	* We could have raced with another thread which failed, so
2142	* root->reloc_root may not be set, return ENOENT in this case.
2143	*/
2144	if (!root)
2145	return ERR_PTR(-ENOENT);
2146
2147	if (unlikely(next->new_bytenr)) {
2148	/*
2149	* We just created the reloc root, so we shouldn't have
2150	* ->new_bytenr set yet. If it is then we have multiple roots
2151	* pointing at the same bytenr which indicates corruption, or
2152	* we've made a mistake in the backref walking code.
2153	*/
2154	ASSERT(next->new_bytenr == 0);
2155	btrfs_err(trans->fs_info,
2156	"bytenr %llu possibly has multiple roots pointing at the same bytenr %llu",
2157	node->bytenr, next->bytenr);
2158	return ERR_PTR(-EUCLEAN);
2159	}
2160
2161	next->new_bytenr = root->node->start;
2162	btrfs_put_root(next->root);
2163	next->root = btrfs_grab_root(root);
2164	ASSERT(next->root);
2165	mark_block_processed(rc, next);
2166	found:
2167	next = node;
2168	/* setup backref node path for btrfs_reloc_cow_block */
2169	while (1) {
2170	rc->backref_cache.path[next->level] = next;
2171	if (--index < 0)
2172	break;
2173	next = edges[index]->node[UPPER];
2174	}
2175	return root;
2176	}
2177
2178	/*
2179	* Select a tree root for relocation.
2180	*
2181	* Return NULL if the block is not shareable. We should use do_relocation() in
2182	* this case.
2183	*
2184	* Return a tree root pointer if the block is shareable.
2185	* Return -ENOENT if the block is root of reloc tree.
2186	*/
2187	static noinline_for_stack
2188	struct btrfs_root select_one_root(struct btrfs_backref_node node)
2189	{
2190	struct btrfs_backref_node *next;
2191	struct btrfs_root *root;
2192	struct btrfs_root *fs_root = NULL;
2193	struct btrfs_backref_edge *edges[BTRFS_MAX_LEVEL - 1];
2194	int index = 0;
2195
2196	next = node;
2197	while (1) {
2198	cond_resched();
2199	next = walk_up_backref(next, edges, &index);
2200	root = next->root;
2201
2202	/*
2203	* This can occur if we have incomplete extent refs leading all
2204	* the way up a particular path, in this case return -EUCLEAN.
2205	*/
2206	if (unlikely(!root))
2207	return ERR_PTR(-EUCLEAN);
2208
2209	/* No other choice for non-shareable tree */
2210	if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state))
2211	return root;
2212
2213	if (btrfs_root_id(root) != BTRFS_TREE_RELOC_OBJECTID)
2214	fs_root = root;
2215
2216	if (next != node)
2217	return NULL;
2218
2219	next = walk_down_backref(edges, &index);
2220	if (!next \|\| next->level <= node->level)
2221	break;
2222	}
2223
2224	if (!fs_root)
2225	return ERR_PTR(-ENOENT);
2226	return fs_root;
2227	}
2228
2229	static noinline_for_stack u64 calcu_metadata_size(struct reloc_control *rc,
2230	struct btrfs_backref_node *node)
2231	{
2232	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
2233	struct btrfs_backref_node *next = node;
2234	struct btrfs_backref_edge *edge;
2235	struct btrfs_backref_edge *edges[BTRFS_MAX_LEVEL - 1];
2236	u64 num_bytes = 0;
2237	int index = 0;
2238
2239	BUG_ON(node->processed);
2240
2241	while (next) {
2242	cond_resched();
2243	while (1) {
2244	if (next->processed)
2245	break;
2246
2247	num_bytes += fs_info->nodesize;
2248
2249	if (list_empty(&next->upper))
2250	break;
2251
2252	edge = list_first_entry(&next->upper, struct btrfs_backref_edge,
2253	list[LOWER]);
2254	edges[index++] = edge;
2255	next = edge->node[UPPER];
2256	}
2257	next = walk_down_backref(edges, &index);
2258	}
2259	return num_bytes;
2260	}
2261
2262	static int refill_metadata_space(struct btrfs_trans_handle *trans,
2263	struct reloc_control *rc, u64 num_bytes)
2264	{
2265	struct btrfs_fs_info *fs_info = trans->fs_info;
2266	int ret;
2267
2268	trans->block_rsv = rc->block_rsv;
2269	rc->reserved_bytes += num_bytes;
2270
2271	/*
2272	* We are under a transaction here so we can only do limited flushing.
2273	* If we get an enospc just kick back -EAGAIN so we know to drop the
2274	* transaction and try to refill when we can flush all the things.
2275	*/
2276	ret = btrfs_block_rsv_refill(rc->block_rsv, num_bytes,
2277	BTRFS_RESERVE_FLUSH_LIMIT);
2278	if (ret) {
2279	u64 tmp = fs_info->nodesize * RELOCATION_RESERVED_NODES;
2280
2281	while (tmp <= rc->reserved_bytes)
2282	tmp <<= 1;
2283	/*
2284	* only one thread can access block_rsv at this point,
2285	* so we don't need hold lock to protect block_rsv.
2286	* we expand more reservation size here to allow enough
2287	* space for relocation and we will return earlier in
2288	* enospc case.
2289	*/
2290	rc->block_rsv->size = tmp + fs_info->nodesize *
2291	RELOCATION_RESERVED_NODES;
2292	return -EAGAIN;
2293	}
2294
2295	return 0;
2296	}
2297
2298	static int reserve_metadata_space(struct btrfs_trans_handle *trans,
2299	struct reloc_control *rc,
2300	struct btrfs_backref_node *node)
2301	{
2302	u64 num_bytes;
2303
2304	num_bytes = calcu_metadata_size(rc, node) * 2;
2305	return refill_metadata_space(trans, rc, num_bytes);
2306	}
2307
2308	/*
2309	* relocate a block tree, and then update pointers in upper level
2310	* blocks that reference the block to point to the new location.
2311	*
2312	* if called by link_to_upper, the block has already been relocated.
2313	* in that case this function just updates pointers.
2314	*/
2315	static int do_relocation(struct btrfs_trans_handle *trans,
2316	struct reloc_control *rc,
2317	struct btrfs_backref_node *node,
2318	struct btrfs_key *key,
2319	struct btrfs_path *path, int lowest)
2320	{
2321	struct btrfs_backref_node *upper;
2322	struct btrfs_backref_edge *edge;
2323	struct btrfs_backref_edge *edges[BTRFS_MAX_LEVEL - 1];
2324	struct btrfs_root *root;
2325	struct extent_buffer *eb;
2326	u32 blocksize;
2327	u64 bytenr;
2328	int slot;
2329	int ret = 0;
2330
2331	/*
2332	* If we are lowest then this is the first time we're processing this
2333	* block, and thus shouldn't have an eb associated with it yet.
2334	*/
2335	ASSERT(!lowest \|\| !node->eb);
2336
2337	path->lowest_level = node->level + 1;
2338	rc->backref_cache.path[node->level] = node;
2339	list_for_each_entry(edge, &node->upper, list[LOWER]) {
2340	cond_resched();
2341
2342	upper = edge->node[UPPER];
2343	root = select_reloc_root(trans, rc, upper, edges);
2344	if (IS_ERR(root)) {
2345	ret = PTR_ERR(root);
2346	goto next;
2347	}
2348
2349	if (upper->eb && !upper->locked) {
2350	if (!lowest) {
2351	ret = btrfs_bin_search(upper->eb, 0, key, &slot);
2352	if (ret < 0)
2353	goto next;
2354	BUG_ON(ret);
2355	bytenr = btrfs_node_blockptr(upper->eb, slot);
2356	if (node->eb->start == bytenr)
2357	goto next;
2358	}
2359	btrfs_backref_drop_node_buffer(upper);
2360	}
2361
2362	if (!upper->eb) {
2363	ret = btrfs_search_slot(trans, root, key, path, 0, 1);
2364	if (ret) {
2365	if (ret > 0)
2366	ret = -ENOENT;
2367
2368	btrfs_release_path(path);
2369	break;
2370	}
2371
2372	if (!upper->eb) {
2373	upper->eb = path->nodes[upper->level];
2374	path->nodes[upper->level] = NULL;
2375	} else {
2376	BUG_ON(upper->eb != path->nodes[upper->level]);
2377	}
2378
2379	upper->locked = 1;
2380	path->locks[upper->level] = 0;
2381
2382	slot = path->slots[upper->level];
2383	btrfs_release_path(path);
2384	} else {
2385	ret = btrfs_bin_search(upper->eb, 0, key, &slot);
2386	if (ret < 0)
2387	goto next;
2388	BUG_ON(ret);
2389	}
2390
2391	bytenr = btrfs_node_blockptr(upper->eb, slot);
2392	if (lowest) {
2393	if (unlikely(bytenr != node->bytenr)) {
2394	btrfs_err(root->fs_info,
2395	"lowest leaf/node mismatch: bytenr %llu node->bytenr %llu slot %d upper %llu",
2396	bytenr, node->bytenr, slot,
2397	upper->eb->start);
2398	ret = -EIO;
2399	goto next;
2400	}
2401	} else {
2402	if (node->eb->start == bytenr)
2403	goto next;
2404	}
2405
2406	blocksize = root->fs_info->nodesize;
2407	eb = btrfs_read_node_slot(upper->eb, slot);
2408	if (IS_ERR(eb)) {
2409	ret = PTR_ERR(eb);
2410	goto next;
2411	}
2412	btrfs_tree_lock(eb);
2413
2414	if (!node->eb) {
2415	ret = btrfs_cow_block(trans, root, eb, upper->eb,
2416	slot, &eb, BTRFS_NESTING_COW);
2417	btrfs_tree_unlock(eb);
2418	free_extent_buffer(eb);
2419	if (ret < 0)
2420	goto next;
2421	/*
2422	* We've just COWed this block, it should have updated
2423	* the correct backref node entry.
2424	*/
2425	ASSERT(node->eb == eb);
2426	} else {
2427	struct btrfs_ref ref = {
2428	.action = BTRFS_ADD_DELAYED_REF,
2429	.bytenr = node->eb->start,
2430	.num_bytes = blocksize,
2431	.parent = upper->eb->start,
2432	.owning_root = btrfs_header_owner(upper->eb),
2433	.ref_root = btrfs_header_owner(upper->eb),
2434	};
2435
2436	btrfs_set_node_blockptr(upper->eb, slot,
2437	node->eb->start);
2438	btrfs_set_node_ptr_generation(upper->eb, slot,
2439	trans->transid);
2440	btrfs_mark_buffer_dirty(trans, upper->eb);
2441
2442	btrfs_init_tree_ref(&ref, node->level,
2443	btrfs_root_id(root), false);
2444	ret = btrfs_inc_extent_ref(trans, &ref);
2445	if (!ret)
2446	ret = btrfs_drop_subtree(trans, root, eb,
2447	upper->eb);
2448	if (unlikely(ret))
2449	btrfs_abort_transaction(trans, ret);
2450	}
2451	next:
2452	if (!upper->pending)
2453	btrfs_backref_drop_node_buffer(upper);
2454	else
2455	btrfs_backref_unlock_node_buffer(upper);
2456	if (ret)
2457	break;
2458	}
2459
2460	if (!ret && node->pending) {
2461	btrfs_backref_drop_node_buffer(node);
2462	list_del_init(&node->list);
2463	node->pending = 0;
2464	}
2465
2466	path->lowest_level = 0;
2467
2468	/*
2469	* We should have allocated all of our space in the block rsv and thus
2470	* shouldn't ENOSPC.
2471	*/
2472	ASSERT(ret != -ENOSPC);
2473	return ret;
2474	}
2475
2476	static int link_to_upper(struct btrfs_trans_handle *trans,
2477	struct reloc_control *rc,
2478	struct btrfs_backref_node *node,
2479	struct btrfs_path *path)
2480	{
2481	struct btrfs_key key;
2482
2483	btrfs_node_key_to_cpu(node->eb, &key, 0);
2484	return do_relocation(trans, rc, node, &key, path, 0);
2485	}
2486
2487	static int finish_pending_nodes(struct btrfs_trans_handle *trans,
2488	struct reloc_control *rc,
2489	struct btrfs_path *path, int err)
2490	{
2491	LIST_HEAD(list);
2492	struct btrfs_backref_cache *cache = &rc->backref_cache;
2493	struct btrfs_backref_node *node;
2494	int level;
2495	int ret;
2496
2497	for (level = 0; level < BTRFS_MAX_LEVEL; level++) {
2498	while (!list_empty(&cache->pending[level])) {
2499	node = list_first_entry(&cache->pending[level],
2500	struct btrfs_backref_node, list);
2501	list_move_tail(&node->list, &list);
2502	BUG_ON(!node->pending);
2503
2504	if (!err) {
2505	ret = link_to_upper(trans, rc, node, path);
2506	if (ret < 0)
2507	err = ret;
2508	}
2509	}
2510	list_splice_init(&list, &cache->pending[level]);
2511	}
2512	return err;
2513	}
2514
2515	/*
2516	* mark a block and all blocks directly/indirectly reference the block
2517	* as processed.
2518	*/
2519	static void update_processed_blocks(struct reloc_control *rc,
2520	struct btrfs_backref_node *node)
2521	{
2522	struct btrfs_backref_node *next = node;
2523	struct btrfs_backref_edge *edge;
2524	struct btrfs_backref_edge *edges[BTRFS_MAX_LEVEL - 1];
2525	int index = 0;
2526
2527	while (next) {
2528	cond_resched();
2529	while (1) {
2530	if (next->processed)
2531	break;
2532
2533	mark_block_processed(rc, next);
2534
2535	if (list_empty(&next->upper))
2536	break;
2537
2538	edge = list_first_entry(&next->upper, struct btrfs_backref_edge,
2539	list[LOWER]);
2540	edges[index++] = edge;
2541	next = edge->node[UPPER];
2542	}
2543	next = walk_down_backref(edges, &index);
2544	}
2545	}
2546
2547	static int tree_block_processed(u64 bytenr, struct reloc_control *rc)
2548	{
2549	u32 blocksize = rc->extent_root->fs_info->nodesize;
2550
2551	if (btrfs_test_range_bit(&rc->processed_blocks, bytenr,
2552	bytenr + blocksize - 1, EXTENT_DIRTY, NULL))
2553	return 1;
2554	return 0;
2555	}
2556
2557	static int get_tree_block_key(struct btrfs_fs_info *fs_info,
2558	struct tree_block *block)
2559	{
2560	struct btrfs_tree_parent_check check = {
2561	.level = block->level,
2562	.owner_root = block->owner,
2563	.transid = block->key.offset
2564	};
2565	struct extent_buffer *eb;
2566
2567	eb = read_tree_block(fs_info, block->bytenr, &check);
2568	if (IS_ERR(eb))
2569	return PTR_ERR(eb);
2570
2571	if (block->level == 0)
2572	btrfs_item_key_to_cpu(eb, &block->key, 0);
2573	else
2574	btrfs_node_key_to_cpu(eb, &block->key, 0);
2575	free_extent_buffer(eb);
2576	block->key_ready = true;
2577	return 0;
2578	}
2579
2580	/*
2581	* helper function to relocate a tree block
2582	*/
2583	static int relocate_tree_block(struct btrfs_trans_handle *trans,
2584	struct reloc_control *rc,
2585	struct btrfs_backref_node *node,
2586	struct btrfs_key *key,
2587	struct btrfs_path *path)
2588	{
2589	struct btrfs_root *root;
2590	int ret = 0;
2591
2592	if (!node)
2593	return 0;
2594
2595	/*
2596	* If we fail here we want to drop our backref_node because we are going
2597	* to start over and regenerate the tree for it.
2598	*/
2599	ret = reserve_metadata_space(trans, rc, node);
2600	if (ret)
2601	goto out;
2602
2603	BUG_ON(node->processed);
2604	root = select_one_root(node);
2605	if (IS_ERR(root)) {
2606	ret = PTR_ERR(root);
2607
2608	/* See explanation in select_one_root for the -EUCLEAN case. */
2609	ASSERT(ret == -ENOENT);
2610	if (ret == -ENOENT) {
2611	ret = 0;
2612	update_processed_blocks(rc, node);
2613	}
2614	goto out;
2615	}
2616
2617	if (root) {
2618	if (test_bit(BTRFS_ROOT_SHAREABLE, &root->state)) {
2619	/*
2620	* This block was the root block of a root, and this is
2621	* the first time we're processing the block and thus it
2622	* should not have had the ->new_bytenr modified.
2623	*
2624	* However in the case of corruption we could have
2625	* multiple refs pointing to the same block improperly,
2626	* and thus we would trip over these checks. ASSERT()
2627	* for the developer case, because it could indicate a
2628	* bug in the backref code, however error out for a
2629	* normal user in the case of corruption.
2630	*/
2631	ASSERT(node->new_bytenr == 0);
2632	if (unlikely(node->new_bytenr)) {
2633	btrfs_err(root->fs_info,
2634	"bytenr %llu has improper references to it",
2635	node->bytenr);
2636	ret = -EUCLEAN;
2637	goto out;
2638	}
2639	ret = btrfs_record_root_in_trans(trans, root);
2640	if (ret)
2641	goto out;
2642	/*
2643	* Another thread could have failed, need to check if we
2644	* have reloc_root actually set.
2645	*/
2646	if (!root->reloc_root) {
2647	ret = -ENOENT;
2648	goto out;
2649	}
2650	root = root->reloc_root;
2651	node->new_bytenr = root->node->start;
2652	btrfs_put_root(node->root);
2653	node->root = btrfs_grab_root(root);
2654	ASSERT(node->root);
2655	} else {
2656	btrfs_err(root->fs_info,
2657	"bytenr %llu resolved to a non-shareable root",
2658	node->bytenr);
2659	ret = -EUCLEAN;
2660	goto out;
2661	}
2662	if (!ret)
2663	update_processed_blocks(rc, node);
2664	} else {
2665	ret = do_relocation(trans, rc, node, key, path, 1);
2666	}
2667	out:
2668	if (ret \|\| node->level == 0)
2669	btrfs_backref_cleanup_node(&rc->backref_cache, node);
2670	return ret;
2671	}
2672
2673	static int relocate_cowonly_block(struct btrfs_trans_handle *trans,
2674	struct reloc_control rc, struct tree_block block,
2675	struct btrfs_path *path)
2676	{
2677	struct btrfs_fs_info *fs_info = trans->fs_info;
2678	struct btrfs_root *root;
2679	u64 num_bytes;
2680	int nr_levels;
2681	int ret;
2682
2683	root = btrfs_get_fs_root(fs_info, block->owner, true);
2684	if (IS_ERR(root))
2685	return PTR_ERR(root);
2686
2687	nr_levels = max(btrfs_header_level(root->node) - block->level, 0) + 1;
2688
2689	num_bytes = (nr_levels << fs_info->nodesize_bits);
2690	ret = refill_metadata_space(trans, rc, num_bytes);
2691	if (ret) {
2692	btrfs_put_root(root);
2693	return ret;
2694	}
2695	path->lowest_level = block->level;
2696	if (root == root->fs_info->chunk_root)
2697	btrfs_reserve_chunk_metadata(trans, false);
2698
2699	ret = btrfs_search_slot(trans, root, &block->key, path, 0, 1);
2700	path->lowest_level = 0;
2701	btrfs_release_path(path);
2702
2703	if (root == root->fs_info->chunk_root)
2704	btrfs_trans_release_chunk_metadata(trans);
2705	if (ret > 0)
2706	ret = 0;
2707	btrfs_put_root(root);
2708
2709	return ret;
2710	}
2711
2712	/*
2713	* relocate a list of blocks
2714	*/
2715	static noinline_for_stack
2716	int relocate_tree_blocks(struct btrfs_trans_handle *trans,
2717	struct reloc_control rc, struct rb_root blocks)
2718	{
2719	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
2720	struct btrfs_backref_node *node;
2721	struct btrfs_path *path;
2722	struct tree_block *block;
2723	struct tree_block *next;
2724	int ret = 0;
2725
2726	path = btrfs_alloc_path();
2727	if (!path) {
2728	ret = -ENOMEM;
2729	goto out_free_blocks;
2730	}
2731
2732	/* Kick in readahead for tree blocks with missing keys */
2733	rbtree_postorder_for_each_entry_safe(block, next, blocks, rb_node) {
2734	if (!block->key_ready)
2735	btrfs_readahead_tree_block(fs_info, block->bytenr,
2736	block->owner, 0,
2737	block->level, NULL);
2738	}
2739
2740	/* Get first keys */
2741	rbtree_postorder_for_each_entry_safe(block, next, blocks, rb_node) {
2742	if (!block->key_ready) {
2743	ret = get_tree_block_key(fs_info, block);
2744	if (ret)
2745	goto out_free_path;
2746	}
2747	}
2748
2749	/* Do tree relocation */
2750	rbtree_postorder_for_each_entry_safe(block, next, blocks, rb_node) {
2751	/*
2752	* For COWonly blocks, or the data reloc tree, we only need to
2753	* COW down to the block, there's no need to generate a backref
2754	* tree.
2755	*/
2756	if (block->owner &&
2757	(!btrfs_is_fstree(block->owner) \|\|
2758	block->owner == BTRFS_DATA_RELOC_TREE_OBJECTID)) {
2759	ret = relocate_cowonly_block(trans, rc, block, path);
2760	if (ret)
2761	break;
2762	continue;
2763	}
2764
2765	node = build_backref_tree(trans, rc, &block->key,
2766	block->level, block->bytenr);
2767	if (IS_ERR(node)) {
2768	ret = PTR_ERR(node);
2769	goto out;
2770	}
2771
2772	ret = relocate_tree_block(trans, rc, node, &block->key,
2773	path);
2774	if (ret < 0)
2775	break;
2776	}
2777	out:
2778	ret = finish_pending_nodes(trans, rc, path, ret);
2779
2780	out_free_path:
2781	btrfs_free_path(path);
2782	out_free_blocks:
2783	free_block_list(blocks);
2784	return ret;
2785	}
2786
2787	static noinline_for_stack int prealloc_file_extent_cluster(struct reloc_control *rc)
2788	{
2789	const struct file_extent_cluster *cluster = &rc->cluster;
2790	struct btrfs_inode *inode = BTRFS_I(rc->data_inode);
2791	u64 alloc_hint = 0;
2792	u64 start;
2793	u64 end;
2794	u64 offset = inode->reloc_block_group_start;
2795	u64 num_bytes;
2796	int nr;
2797	int ret = 0;
2798	u64 prealloc_start = cluster->start - offset;
2799	u64 prealloc_end = cluster->end - offset;
2800	u64 cur_offset = prealloc_start;
2801
2802	/*
2803	* For blocksize < folio size case (either bs < page size or large folios),
2804	* beyond i_size, all blocks are filled with zero.
2805	*
2806	* If the current cluster covers the above range, btrfs_do_readpage()
2807	* will skip the read, and relocate_one_folio() will later writeback
2808	* the padding zeros as new data, causing data corruption.
2809	*
2810	* Here we have to invalidate the cache covering our cluster.
2811	*/
2812	ret = filemap_invalidate_inode(&inode->vfs_inode, true, prealloc_start,
2813	prealloc_end);
2814	if (ret < 0)
2815	return ret;
2816
2817	BUG_ON(cluster->start != cluster->boundary[0]);
2818	ret = btrfs_alloc_data_chunk_ondemand(inode,
2819	prealloc_end + 1 - prealloc_start);
2820	if (ret)
2821	return ret;
2822
2823	btrfs_inode_lock(inode, 0);
2824	for (nr = 0; nr < cluster->nr; nr++) {
2825	struct extent_state *cached_state = NULL;
2826
2827	start = cluster->boundary[nr] - offset;
2828	if (nr + 1 < cluster->nr)
2829	end = cluster->boundary[nr + 1] - 1 - offset;
2830	else
2831	end = cluster->end - offset;
2832
2833	btrfs_lock_extent(&inode->io_tree, start, end, &cached_state);
2834	num_bytes = end + 1 - start;
2835	ret = btrfs_prealloc_file_range(&inode->vfs_inode, 0, start,
2836	num_bytes, num_bytes,
2837	end + 1, &alloc_hint);
2838	cur_offset = end + 1;
2839	btrfs_unlock_extent(&inode->io_tree, start, end, &cached_state);
2840	if (ret)
2841	break;
2842	}
2843	btrfs_inode_unlock(inode, 0);
2844
2845	if (cur_offset < prealloc_end)
2846	btrfs_free_reserved_data_space_noquota(inode,
2847	prealloc_end + 1 - cur_offset);
2848	return ret;
2849	}
2850
2851	static noinline_for_stack int setup_relocation_extent_mapping(struct reloc_control *rc)
2852	{
2853	struct btrfs_inode *inode = BTRFS_I(rc->data_inode);
2854	struct extent_map *em;
2855	struct extent_state *cached_state = NULL;
2856	u64 offset = inode->reloc_block_group_start;
2857	u64 start = rc->cluster.start - offset;
2858	u64 end = rc->cluster.end - offset;
2859	int ret = 0;
2860
2861	em = btrfs_alloc_extent_map();
2862	if (!em)
2863	return -ENOMEM;
2864
2865	em->start = start;
2866	em->len = end + 1 - start;
2867	em->disk_bytenr = rc->cluster.start;
2868	em->disk_num_bytes = em->len;
2869	em->ram_bytes = em->len;
2870	em->flags \|= EXTENT_FLAG_PINNED;
2871
2872	btrfs_lock_extent(&inode->io_tree, start, end, &cached_state);
2873	ret = btrfs_replace_extent_map_range(inode, em, false);
2874	btrfs_unlock_extent(&inode->io_tree, start, end, &cached_state);
2875	btrfs_free_extent_map(em);
2876
2877	return ret;
2878	}
2879
2880	/*
2881	* Allow error injection to test balance/relocation cancellation
2882	*/
2883	noinline int btrfs_should_cancel_balance(const struct btrfs_fs_info *fs_info)
2884	{
2885	return atomic_read(&fs_info->balance_cancel_req) \|\|
2886	atomic_read(&fs_info->reloc_cancel_req) \|\|
2887	fatal_signal_pending(current);
2888	}
2889	ALLOW_ERROR_INJECTION(btrfs_should_cancel_balance, TRUE);
2890
2891	static u64 get_cluster_boundary_end(const struct file_extent_cluster *cluster,
2892	int cluster_nr)
2893	{
2894	/* Last extent, use cluster end directly */
2895	if (cluster_nr >= cluster->nr - 1)
2896	return cluster->end;
2897
2898	/* Use next boundary start*/
2899	return cluster->boundary[cluster_nr + 1] - 1;
2900	}
2901
2902	static int relocate_one_folio(struct reloc_control *rc,
2903	struct file_ra_state *ra,
2904	int cluster_nr, u64 file_offset_ret)
2905	{
2906	const struct file_extent_cluster *cluster = &rc->cluster;
2907	struct inode *inode = rc->data_inode;
2908	struct btrfs_fs_info *fs_info = inode_to_fs_info(inode);
2909	const u64 orig_file_offset = *file_offset_ret;
2910	u64 offset = BTRFS_I(inode)->reloc_block_group_start;
2911	const pgoff_t last_index = (cluster->end - offset) >> PAGE_SHIFT;
2912	const pgoff_t index = orig_file_offset >> PAGE_SHIFT;
2913	gfp_t mask = btrfs_alloc_write_mask(inode->i_mapping);
2914	struct folio *folio;
2915	u64 folio_start;
2916	u64 folio_end;
2917	u64 cur;
2918	int ret;
2919	const bool use_rst = btrfs_need_stripe_tree_update(fs_info, rc->block_group->flags);
2920
2921	ASSERT(index <= last_index);
2922	again:
2923	folio = filemap_lock_folio(inode->i_mapping, index);
2924	if (IS_ERR(folio)) {
2925
2926	/*
2927	* On relocation we're doing readahead on the relocation inode,
2928	* but if the filesystem is backed by a RAID stripe tree we can
2929	* get ENOENT (e.g. due to preallocated extents not being
2930	* mapped in the RST) from the lookup.
2931	*
2932	* But readahead doesn't handle the error and submits invalid
2933	* reads to the device, causing a assertion failures.
2934	*/
2935	if (!use_rst)
2936	page_cache_sync_readahead(inode->i_mapping, ra, NULL,
2937	index, last_index + 1 - index);
2938	folio = __filemap_get_folio(inode->i_mapping, index,
2939	FGP_LOCK \| FGP_ACCESSED \| FGP_CREAT,
2940	mask);
2941	if (IS_ERR(folio))
2942	return PTR_ERR(folio);
2943	}
2944
2945	if (folio_test_readahead(folio) && !use_rst)
2946	page_cache_async_readahead(inode->i_mapping, ra, NULL,
2947	folio, last_index + 1 - index);
2948
2949	if (!folio_test_uptodate(folio)) {
2950	btrfs_read_folio(NULL, folio);
2951	folio_lock(folio);
2952	if (unlikely(!folio_test_uptodate(folio))) {
2953	ret = -EIO;
2954	goto release_folio;
2955	}
2956	if (folio->mapping != inode->i_mapping) {
2957	folio_unlock(folio);
2958	folio_put(folio);
2959	goto again;
2960	}
2961	}
2962
2963	/*
2964	* We could have lost folio private when we dropped the lock to read the
2965	* folio above, make sure we set_folio_extent_mapped() here so we have any
2966	* of the subpage blocksize stuff we need in place.
2967	*/
2968	ret = set_folio_extent_mapped(folio);
2969	if (ret < 0)
2970	goto release_folio;
2971
2972	folio_start = folio_pos(folio);
2973	folio_end = folio_start + folio_size(folio) - 1;
2974
2975	/*
2976	* Start from the cluster, as for subpage case, the cluster can start
2977	* inside the folio.
2978	*/
2979	cur = max(folio_start, cluster->boundary[*cluster_nr] - offset);
2980	while (cur <= folio_end) {
2981	struct extent_state *cached_state = NULL;
2982	u64 extent_start = cluster->boundary[*cluster_nr] - offset;
2983	u64 extent_end = get_cluster_boundary_end(cluster,
2984	*cluster_nr) - offset;
2985	u64 clamped_start = max(folio_start, extent_start);
2986	u64 clamped_end = min(folio_end, extent_end);
2987	u32 clamped_len = clamped_end + 1 - clamped_start;
2988
2989	/* Reserve metadata for this range */
2990	ret = btrfs_delalloc_reserve_metadata(BTRFS_I(inode),
2991	clamped_len, clamped_len,
2992	false);
2993	if (ret)
2994	goto release_folio;
2995
2996	/* Mark the range delalloc and dirty for later writeback */
2997	btrfs_lock_extent(&BTRFS_I(inode)->io_tree, clamped_start,
2998	clamped_end, &cached_state);
2999	ret = btrfs_set_extent_delalloc(BTRFS_I(inode), clamped_start,
3000	clamped_end, 0, &cached_state);
3001	if (ret) {
3002	btrfs_clear_extent_bit(&BTRFS_I(inode)->io_tree,
3003	clamped_start, clamped_end,
3004	EXTENT_LOCKED \| EXTENT_BOUNDARY,
3005	&cached_state);
3006	btrfs_delalloc_release_metadata(BTRFS_I(inode),
3007	clamped_len, true);
3008	btrfs_delalloc_release_extents(BTRFS_I(inode),
3009	clamped_len);
3010	goto release_folio;
3011	}
3012	btrfs_folio_set_dirty(fs_info, folio, clamped_start, clamped_len);
3013
3014	/*
3015	* Set the boundary if it's inside the folio.
3016	* Data relocation requires the destination extents to have the
3017	* same size as the source.
3018	* EXTENT_BOUNDARY bit prevents current extent from being merged
3019	* with previous extent.
3020	*/
3021	if (in_range(cluster->boundary[*cluster_nr] - offset,
3022	folio_start, folio_size(folio))) {
3023	u64 boundary_start = cluster->boundary[*cluster_nr] -
3024	offset;
3025	u64 boundary_end = boundary_start +
3026	fs_info->sectorsize - 1;
3027
3028	btrfs_set_extent_bit(&BTRFS_I(inode)->io_tree,
3029	boundary_start, boundary_end,
3030	EXTENT_BOUNDARY, NULL);
3031	}
3032	btrfs_unlock_extent(&BTRFS_I(inode)->io_tree, clamped_start, clamped_end,
3033	&cached_state);
3034	btrfs_delalloc_release_extents(BTRFS_I(inode), clamped_len);
3035	cur += clamped_len;
3036
3037	/* Crossed extent end, go to next extent */
3038	if (cur >= extent_end) {
3039	(*cluster_nr)++;
3040	/* Just finished the last extent of the cluster, exit. */
3041	if (*cluster_nr >= cluster->nr)
3042	break;
3043	}
3044	}
3045	folio_unlock(folio);
3046	folio_put(folio);
3047
3048	balance_dirty_pages_ratelimited(inode->i_mapping);
3049	btrfs_throttle(fs_info);
3050	if (btrfs_should_cancel_balance(fs_info))
3051	ret = -ECANCELED;
3052	*file_offset_ret = folio_end + 1;
3053	return ret;
3054
3055	release_folio:
3056	folio_unlock(folio);
3057	folio_put(folio);
3058	return ret;
3059	}
3060
3061	static int relocate_file_extent_cluster(struct reloc_control *rc)
3062	{
3063	struct inode *inode = rc->data_inode;
3064	const struct file_extent_cluster *cluster = &rc->cluster;
3065	u64 offset = BTRFS_I(inode)->reloc_block_group_start;
3066	u64 cur_file_offset = cluster->start - offset;
3067	struct file_ra_state AUTO_KFREE(ra);
3068	int cluster_nr = 0;
3069	int ret = 0;
3070
3071	if (!cluster->nr)
3072	return 0;
3073
3074	ra = kzalloc_obj(*ra, GFP_NOFS);
3075	if (!ra)
3076	return -ENOMEM;
3077
3078	ret = prealloc_file_extent_cluster(rc);
3079	if (ret)
3080	return ret;
3081
3082	file_ra_state_init(ra, inode->i_mapping);
3083
3084	ret = setup_relocation_extent_mapping(rc);
3085	if (ret)
3086	return ret;
3087
3088	while (cur_file_offset < cluster->end - offset) {
3089	ret = relocate_one_folio(rc, ra, &cluster_nr, &cur_file_offset);
3090	if (ret)
3091	break;
3092	}
3093	if (ret == 0)
3094	WARN_ON(cluster_nr != cluster->nr);
3095	return ret;
3096	}
3097
3098	static noinline_for_stack int relocate_data_extent(struct reloc_control *rc,
3099	const struct btrfs_key *extent_key)
3100	{
3101	struct inode *inode = rc->data_inode;
3102	struct file_extent_cluster *cluster = &rc->cluster;
3103	int ret;
3104	struct btrfs_root *root = BTRFS_I(inode)->root;
3105
3106	if (cluster->nr > 0 && extent_key->objectid != cluster->end + 1) {
3107	ret = relocate_file_extent_cluster(rc);
3108	if (ret)
3109	return ret;
3110	cluster->nr = 0;
3111	}
3112
3113	/*
3114	* Under simple quotas, we set root->relocation_src_root when we find
3115	* the extent. If adjacent extents have different owners, we can't merge
3116	* them while relocating. Handle this by storing the owning root that
3117	* started a cluster and if we see an extent from a different root break
3118	* cluster formation (just like the above case of non-adjacent extents).
3119	*
3120	* Without simple quotas, relocation_src_root is always 0, so we should
3121	* never see a mismatch, and it should have no effect on relocation
3122	* clusters.
3123	*/
3124	if (cluster->nr > 0 && cluster->owning_root != root->relocation_src_root) {
3125	u64 tmp = root->relocation_src_root;
3126
3127	/*
3128	* root->relocation_src_root is the state that actually affects
3129	* the preallocation we do here, so set it to the root owning
3130	* the cluster we need to relocate.
3131	*/
3132	root->relocation_src_root = cluster->owning_root;
3133	ret = relocate_file_extent_cluster(rc);
3134	if (ret)
3135	return ret;
3136	cluster->nr = 0;
3137	/* And reset it back for the current extent's owning root. */
3138	root->relocation_src_root = tmp;
3139	}
3140
3141	if (!cluster->nr) {
3142	cluster->start = extent_key->objectid;
3143	cluster->owning_root = root->relocation_src_root;
3144	}
3145	else
3146	BUG_ON(cluster->nr >= MAX_EXTENTS);
3147	cluster->end = extent_key->objectid + extent_key->offset - 1;
3148	cluster->boundary[cluster->nr] = extent_key->objectid;
3149	cluster->nr++;
3150
3151	if (cluster->nr >= MAX_EXTENTS) {
3152	ret = relocate_file_extent_cluster(rc);
3153	if (ret)
3154	return ret;
3155	cluster->nr = 0;
3156	}
3157	return 0;
3158	}
3159
3160	/*
3161	* helper to add a tree block to the list.
3162	* the major work is getting the generation and level of the block
3163	*/
3164	static int add_tree_block(struct reloc_control *rc,
3165	const struct btrfs_key *extent_key,
3166	struct btrfs_path *path,
3167	struct rb_root *blocks)
3168	{
3169	struct extent_buffer *eb;
3170	struct btrfs_extent_item *ei;
3171	struct btrfs_tree_block_info *bi;
3172	struct tree_block *block;
3173	struct rb_node *rb_node;
3174	u32 item_size;
3175	int level = -1;
3176	u64 generation;
3177	u64 owner = 0;
3178
3179	eb = path->nodes[0];
3180	item_size = btrfs_item_size(eb, path->slots[0]);
3181
3182	if (extent_key->type == BTRFS_METADATA_ITEM_KEY \|\|
3183	item_size >= sizeof(ei) + sizeof(bi)) {
3184	unsigned long ptr = 0, end;
3185
3186	ei = btrfs_item_ptr(eb, path->slots[0],
3187	struct btrfs_extent_item);
3188	end = (unsigned long)ei + item_size;
3189	if (extent_key->type == BTRFS_EXTENT_ITEM_KEY) {
3190	bi = (struct btrfs_tree_block_info *)(ei + 1);
3191	level = btrfs_tree_block_level(eb, bi);
3192	ptr = (unsigned long)(bi + 1);
3193	} else {
3194	level = (int)extent_key->offset;
3195	ptr = (unsigned long)(ei + 1);
3196	}
3197	generation = btrfs_extent_generation(eb, ei);
3198
3199	/*
3200	* We're reading random blocks without knowing their owner ahead
3201	* of time. This is ok most of the time, as all reloc roots and
3202	* fs roots have the same lock type. However normal trees do
3203	* not, and the only way to know ahead of time is to read the
3204	* inline ref offset. We know it's an fs root if
3205	*
3206	* 1. There's more than one ref.
3207	* 2. There's a SHARED_DATA_REF_KEY set.
3208	* 3. FULL_BACKREF is set on the flags.
3209	*
3210	* Otherwise it's safe to assume that the ref offset == the
3211	* owner of this block, so we can use that when calling
3212	* read_tree_block.
3213	*/
3214	if (btrfs_extent_refs(eb, ei) == 1 &&
3215	!(btrfs_extent_flags(eb, ei) &
3216	BTRFS_BLOCK_FLAG_FULL_BACKREF) &&
3217	ptr < end) {
3218	struct btrfs_extent_inline_ref *iref;
3219	int type;
3220
3221	iref = (struct btrfs_extent_inline_ref *)ptr;
3222	type = btrfs_get_extent_inline_ref_type(eb, iref,
3223	BTRFS_REF_TYPE_BLOCK);
3224	if (type == BTRFS_REF_TYPE_INVALID)
3225	return -EINVAL;
3226	if (type == BTRFS_TREE_BLOCK_REF_KEY)
3227	owner = btrfs_extent_inline_ref_offset(eb, iref);
3228	}
3229	} else {
3230	btrfs_print_leaf(eb);
3231	btrfs_err(rc->block_group->fs_info,
3232	"unrecognized tree backref at tree block %llu slot %u",
3233	eb->start, path->slots[0]);
3234	btrfs_release_path(path);
3235	return -EUCLEAN;
3236	}
3237
3238	btrfs_release_path(path);
3239
3240	BUG_ON(level == -1);
3241
3242	block = kmalloc_obj(*block, GFP_NOFS);
3243	if (!block)
3244	return -ENOMEM;
3245
3246	block->bytenr = extent_key->objectid;
3247	block->key.objectid = rc->extent_root->fs_info->nodesize;
3248	block->key.offset = generation;
3249	block->level = level;
3250	block->key_ready = false;
3251	block->owner = owner;
3252
3253	rb_node = rb_simple_insert(blocks, &block->simple_node);
3254	if (rb_node)
3255	btrfs_backref_panic(rc->extent_root->fs_info, block->bytenr,
3256	-EEXIST);
3257
3258	return 0;
3259	}
3260
3261	/*
3262	* helper to add tree blocks for backref of type BTRFS_SHARED_DATA_REF_KEY
3263	*/
3264	static int __add_tree_block(struct reloc_control *rc,
3265	u64 bytenr, u32 blocksize,
3266	struct rb_root *blocks)
3267	{
3268	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
3269	BTRFS_PATH_AUTO_FREE(path);
3270	struct btrfs_key key;
3271	int ret;
3272	bool skinny = btrfs_fs_incompat(fs_info, SKINNY_METADATA);
3273
3274	if (tree_block_processed(bytenr, rc))
3275	return 0;
3276
3277	if (rb_simple_search(blocks, bytenr))
3278	return 0;
3279
3280	path = btrfs_alloc_path();
3281	if (!path)
3282	return -ENOMEM;
3283	again:
3284	key.objectid = bytenr;
3285	if (skinny) {
3286	key.type = BTRFS_METADATA_ITEM_KEY;
3287	key.offset = (u64)-1;
3288	} else {
3289	key.type = BTRFS_EXTENT_ITEM_KEY;
3290	key.offset = blocksize;
3291	}
3292
3293	path->search_commit_root = true;
3294	path->skip_locking = true;
3295	ret = btrfs_search_slot(NULL, rc->extent_root, &key, path, 0, 0);
3296	if (ret < 0)
3297	return ret;
3298
3299	if (ret > 0 && skinny) {
3300	if (path->slots[0]) {
3301	path->slots[0]--;
3302	btrfs_item_key_to_cpu(path->nodes[0], &key,
3303	path->slots[0]);
3304	if (key.objectid == bytenr &&
3305	(key.type == BTRFS_METADATA_ITEM_KEY \|\|
3306	(key.type == BTRFS_EXTENT_ITEM_KEY &&
3307	key.offset == blocksize)))
3308	ret = 0;
3309	}
3310
3311	if (ret) {
3312	skinny = false;
3313	btrfs_release_path(path);
3314	goto again;
3315	}
3316	}
3317	if (WARN_ON(ret)) {
3318	ASSERT(ret == 1);
3319	btrfs_print_leaf(path->nodes[0]);
3320	btrfs_err(fs_info,
3321	"tree block extent item (%llu) is not found in extent tree",
3322	bytenr);
3323	return -EINVAL;
3324	}
3325
3326	return add_tree_block(rc, &key, path, blocks);
3327	}
3328
3329	static int delete_block_group_cache(struct btrfs_block_group *block_group,
3330	struct inode *inode,
3331	u64 ino)
3332	{
3333	struct btrfs_fs_info *fs_info = block_group->fs_info;
3334	struct btrfs_root *root = fs_info->tree_root;
3335	struct btrfs_trans_handle *trans;
3336	struct btrfs_inode *btrfs_inode;
3337	int ret = 0;
3338
3339	if (inode)
3340	goto truncate;
3341
3342	btrfs_inode = btrfs_iget(ino, root);
3343	if (IS_ERR(btrfs_inode))
3344	return -ENOENT;
3345	inode = &btrfs_inode->vfs_inode;
3346
3347	truncate:
3348	ret = btrfs_check_trunc_cache_free_space(fs_info,
3349	&fs_info->global_block_rsv);
3350	if (ret)
3351	goto out;
3352
3353	trans = btrfs_join_transaction(root);
3354	if (IS_ERR(trans)) {
3355	ret = PTR_ERR(trans);
3356	goto out;
3357	}
3358
3359	ret = btrfs_truncate_free_space_cache(trans, block_group, inode);
3360
3361	btrfs_end_transaction(trans);
3362	btrfs_btree_balance_dirty(fs_info);
3363	out:
3364	iput(inode);
3365	return ret;
3366	}
3367
3368	/*
3369	* Locate the free space cache EXTENT_DATA in root tree leaf and delete the
3370	* cache inode, to avoid free space cache data extent blocking data relocation.
3371	*/
3372	static int delete_v1_space_cache(struct extent_buffer *leaf,
3373	struct btrfs_block_group *block_group,
3374	u64 data_bytenr)
3375	{
3376	u64 space_cache_ino;
3377	struct btrfs_file_extent_item *ei;
3378	struct btrfs_key key;
3379	bool found = false;
3380	int i;
3381
3382	if (btrfs_header_owner(leaf) != BTRFS_ROOT_TREE_OBJECTID)
3383	return 0;
3384
3385	for (i = 0; i < btrfs_header_nritems(leaf); i++) {
3386	u8 type;
3387
3388	btrfs_item_key_to_cpu(leaf, &key, i);
3389	if (key.type != BTRFS_EXTENT_DATA_KEY)
3390	continue;
3391	ei = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
3392	type = btrfs_file_extent_type(leaf, ei);
3393
3394	if ((type == BTRFS_FILE_EXTENT_REG \|\|
3395	type == BTRFS_FILE_EXTENT_PREALLOC) &&
3396	btrfs_file_extent_disk_bytenr(leaf, ei) == data_bytenr) {
3397	found = true;
3398	space_cache_ino = key.objectid;
3399	break;
3400	}
3401	}
3402	if (!found)
3403	return -ENOENT;
3404
3405	return delete_block_group_cache(block_group, NULL, space_cache_ino);
3406	}
3407
3408	/*
3409	* helper to find all tree blocks that reference a given data extent
3410	*/
3411	static noinline_for_stack int add_data_references(struct reloc_control *rc,
3412	const struct btrfs_key *extent_key,
3413	struct btrfs_path *path,
3414	struct rb_root *blocks)
3415	{
3416	struct btrfs_backref_walk_ctx ctx = { 0 };
3417	struct ulist_iterator leaf_uiter;
3418	struct ulist_node *ref_node = NULL;
3419	const u32 blocksize = rc->extent_root->fs_info->nodesize;
3420	int ret = 0;
3421
3422	btrfs_release_path(path);
3423
3424	ctx.bytenr = extent_key->objectid;
3425	ctx.skip_inode_ref_list = true;
3426	ctx.fs_info = rc->extent_root->fs_info;
3427
3428	ret = btrfs_find_all_leafs(&ctx);
3429	if (ret < 0)
3430	return ret;
3431
3432	ULIST_ITER_INIT(&leaf_uiter);
3433	while ((ref_node = ulist_next(ctx.refs, &leaf_uiter))) {
3434	struct btrfs_tree_parent_check check = { 0 };
3435	struct extent_buffer *eb;
3436
3437	eb = read_tree_block(ctx.fs_info, ref_node->val, &check);
3438	if (IS_ERR(eb)) {
3439	ret = PTR_ERR(eb);
3440	break;
3441	}
3442	ret = delete_v1_space_cache(eb, rc->block_group,
3443	extent_key->objectid);
3444	free_extent_buffer(eb);
3445	if (ret < 0)
3446	break;
3447	ret = __add_tree_block(rc, ref_node->val, blocksize, blocks);
3448	if (ret < 0)
3449	break;
3450	}
3451	if (ret < 0)
3452	free_block_list(blocks);
3453	ulist_free(ctx.refs);
3454	return ret;
3455	}
3456
3457	/*
3458	* helper to find next unprocessed extent
3459	*/
3460	static noinline_for_stack
3461	int find_next_extent(struct reloc_control rc, struct btrfs_path path,
3462	struct btrfs_key *extent_key)
3463	{
3464	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
3465	struct btrfs_key key;
3466	struct extent_buffer *leaf;
3467	u64 start, end, last;
3468	int ret;
3469
3470	last = rc->block_group->start + rc->block_group->length;
3471	while (1) {
3472	bool block_found;
3473
3474	cond_resched();
3475	if (rc->search_start >= last) {
3476	ret = 1;
3477	break;
3478	}
3479
3480	key.objectid = rc->search_start;
3481	key.type = BTRFS_EXTENT_ITEM_KEY;
3482	key.offset = 0;
3483
3484	path->search_commit_root = true;
3485	path->skip_locking = true;
3486	ret = btrfs_search_slot(NULL, rc->extent_root, &key, path,
3487	0, 0);
3488	if (ret < 0)
3489	break;
3490	next:
3491	leaf = path->nodes[0];
3492	if (path->slots[0] >= btrfs_header_nritems(leaf)) {
3493	ret = btrfs_next_leaf(rc->extent_root, path);
3494	if (ret != 0)
3495	break;
3496	leaf = path->nodes[0];
3497	}
3498
3499	btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
3500	if (key.objectid >= last) {
3501	ret = 1;
3502	break;
3503	}
3504
3505	if (key.type != BTRFS_EXTENT_ITEM_KEY &&
3506	key.type != BTRFS_METADATA_ITEM_KEY) {
3507	path->slots[0]++;
3508	goto next;
3509	}
3510
3511	if (key.type == BTRFS_EXTENT_ITEM_KEY &&
3512	key.objectid + key.offset <= rc->search_start) {
3513	path->slots[0]++;
3514	goto next;
3515	}
3516
3517	if (key.type == BTRFS_METADATA_ITEM_KEY &&
3518	key.objectid + fs_info->nodesize <=
3519	rc->search_start) {
3520	path->slots[0]++;
3521	goto next;
3522	}
3523
3524	block_found = btrfs_find_first_extent_bit(&rc->processed_blocks,
3525	key.objectid, &start, &end,
3526	EXTENT_DIRTY, NULL);
3527
3528	if (block_found && start <= key.objectid) {
3529	btrfs_release_path(path);
3530	rc->search_start = end + 1;
3531	} else {
3532	if (key.type == BTRFS_EXTENT_ITEM_KEY)
3533	rc->search_start = key.objectid + key.offset;
3534	else
3535	rc->search_start = key.objectid +
3536	fs_info->nodesize;
3537	memcpy(extent_key, &key, sizeof(key));
3538	return 0;
3539	}
3540	}
3541	btrfs_release_path(path);
3542	return ret;
3543	}
3544
3545	static void set_reloc_control(struct reloc_control *rc)
3546	{
3547	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
3548
3549	mutex_lock(&fs_info->reloc_mutex);
3550	spin_lock(&fs_info->reloc_ctl_lock);
3551	fs_info->reloc_ctl = rc;
3552	spin_unlock(&fs_info->reloc_ctl_lock);
3553	mutex_unlock(&fs_info->reloc_mutex);
3554	}
3555
3556	static void unset_reloc_control(struct reloc_control *rc)
3557	{
3558	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
3559
3560	mutex_lock(&fs_info->reloc_mutex);
3561	spin_lock(&fs_info->reloc_ctl_lock);
3562	fs_info->reloc_ctl = NULL;
3563	spin_unlock(&fs_info->reloc_ctl_lock);
3564	mutex_unlock(&fs_info->reloc_mutex);
3565	}
3566
3567	static noinline_for_stack
3568	int prepare_to_relocate(struct reloc_control *rc)
3569	{
3570	struct btrfs_trans_handle *trans;
3571	int ret;
3572
3573	rc->block_rsv = btrfs_alloc_block_rsv(rc->extent_root->fs_info,
3574	BTRFS_BLOCK_RSV_TEMP);
3575	if (!rc->block_rsv)
3576	return -ENOMEM;
3577
3578	memset(&rc->cluster, 0, sizeof(rc->cluster));
3579	rc->search_start = rc->block_group->start;
3580	rc->extents_found = 0;
3581	rc->nodes_relocated = 0;
3582	rc->merging_rsv_size = 0;
3583	rc->reserved_bytes = 0;
3584	rc->block_rsv->size = rc->extent_root->fs_info->nodesize *
3585	RELOCATION_RESERVED_NODES;
3586	ret = btrfs_block_rsv_refill(rc->block_rsv, rc->block_rsv->size,
3587	BTRFS_RESERVE_FLUSH_ALL);
3588	if (ret)
3589	return ret;
3590
3591	rc->create_reloc_tree = true;
3592	set_reloc_control(rc);
3593
3594	trans = btrfs_join_transaction(rc->extent_root);
3595	if (IS_ERR(trans)) {
3596	unset_reloc_control(rc);
3597	/*
3598	* extent tree is not a ref_cow tree and has no reloc_root to
3599	* cleanup. And callers are responsible to free the above
3600	* block rsv.
3601	*/
3602	return PTR_ERR(trans);
3603	}
3604
3605	ret = btrfs_commit_transaction(trans);
3606	if (ret)
3607	unset_reloc_control(rc);
3608
3609	return ret;
3610	}
3611
3612	static noinline_for_stack int relocate_block_group(struct reloc_control *rc)
3613	{
3614	struct btrfs_fs_info *fs_info = rc->extent_root->fs_info;
3615	struct rb_root blocks = RB_ROOT;
3616	struct btrfs_key key;
3617	struct btrfs_trans_handle *trans = NULL;
3618	BTRFS_PATH_AUTO_FREE(path);
3619	struct btrfs_extent_item *ei;
3620	u64 flags;
3621	int ret;
3622	int err = 0;
3623	int progress = 0;
3624
3625	path = btrfs_alloc_path();
3626	if (!path)
3627	return -ENOMEM;
3628	path->reada = READA_FORWARD;
3629
3630	ret = prepare_to_relocate(rc);
3631	if (ret) {
3632	err = ret;
3633	goto out_free;
3634	}
3635
3636	while (1) {
3637	rc->reserved_bytes = 0;
3638	ret = btrfs_block_rsv_refill(rc->block_rsv, rc->block_rsv->size,
3639	BTRFS_RESERVE_FLUSH_ALL);
3640	if (ret) {
3641	err = ret;
3642	break;
3643	}
3644	progress++;
3645	trans = btrfs_start_transaction(rc->extent_root, 0);
3646	if (IS_ERR(trans)) {
3647	err = PTR_ERR(trans);
3648	trans = NULL;
3649	break;
3650	}
3651	restart:
3652	if (rc->backref_cache.last_trans != trans->transid)
3653	btrfs_backref_release_cache(&rc->backref_cache);
3654	rc->backref_cache.last_trans = trans->transid;
3655
3656	ret = find_next_extent(rc, path, &key);
3657	if (ret < 0)
3658	err = ret;
3659	if (ret != 0)
3660	break;
3661
3662	rc->extents_found++;
3663
3664	ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
3665	struct btrfs_extent_item);
3666	flags = btrfs_extent_flags(path->nodes[0], ei);
3667
3668	/*
3669	* If we are relocating a simple quota owned extent item, we
3670	* need to note the owner on the reloc data root so that when
3671	* we allocate the replacement item, we can attribute it to the
3672	* correct eventual owner (rather than the reloc data root).
3673	*/
3674	if (btrfs_qgroup_mode(fs_info) == BTRFS_QGROUP_MODE_SIMPLE) {
3675	struct btrfs_root *root = BTRFS_I(rc->data_inode)->root;
3676	u64 owning_root_id = btrfs_get_extent_owner_root(fs_info,
3677	path->nodes[0],
3678	path->slots[0]);
3679
3680	root->relocation_src_root = owning_root_id;
3681	}
3682
3683	if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
3684	ret = add_tree_block(rc, &key, path, &blocks);
3685	} else if (rc->stage == UPDATE_DATA_PTRS &&
3686	(flags & BTRFS_EXTENT_FLAG_DATA)) {
3687	ret = add_data_references(rc, &key, path, &blocks);
3688	} else {
3689	btrfs_release_path(path);
3690	ret = 0;
3691	}
3692	if (ret < 0) {
3693	err = ret;
3694	break;
3695	}
3696
3697	if (!RB_EMPTY_ROOT(&blocks)) {
3698	ret = relocate_tree_blocks(trans, rc, &blocks);
3699	if (ret < 0) {
3700	if (ret != -EAGAIN) {
3701	err = ret;
3702	break;
3703	}
3704	rc->extents_found--;
3705	rc->search_start = key.objectid;
3706	}
3707	}
3708
3709	btrfs_end_transaction_throttle(trans);
3710	btrfs_btree_balance_dirty(fs_info);
3711	trans = NULL;
3712
3713	if (rc->stage == MOVE_DATA_EXTENTS &&
3714	(flags & BTRFS_EXTENT_FLAG_DATA)) {
3715	rc->found_file_extent = true;
3716	ret = relocate_data_extent(rc, &key);
3717	if (ret < 0) {
3718	err = ret;
3719	break;
3720	}
3721	}
3722	if (btrfs_should_cancel_balance(fs_info)) {
3723	err = -ECANCELED;
3724	break;
3725	}
3726	}
3727	if (trans && progress && err == -ENOSPC) {
3728	ret = btrfs_force_chunk_alloc(trans, rc->block_group->flags);
3729	if (ret == 1) {
3730	err = 0;
3731	progress = 0;
3732	goto restart;
3733	}
3734	}
3735
3736	btrfs_release_path(path);
3737	btrfs_clear_extent_bit(&rc->processed_blocks, 0, (u64)-1, EXTENT_DIRTY, NULL);
3738
3739	if (trans) {
3740	btrfs_end_transaction_throttle(trans);
3741	btrfs_btree_balance_dirty(fs_info);
3742	}
3743
3744	if (!err && !btrfs_fs_incompat(fs_info, REMAP_TREE)) {
3745	ret = relocate_file_extent_cluster(rc);
3746	if (ret < 0)
3747	err = ret;
3748	}
3749
3750	rc->create_reloc_tree = false;
3751	set_reloc_control(rc);
3752
3753	btrfs_backref_release_cache(&rc->backref_cache);
3754	btrfs_block_rsv_release(fs_info, rc->block_rsv, (u64)-1, NULL);
3755
3756	/*
3757	* Even in the case when the relocation is cancelled, we should all go
3758	* through prepare_to_merge() and merge_reloc_roots().
3759	*
3760	* For error (including cancelled balance), prepare_to_merge() will
3761	* mark all reloc trees orphan, then queue them for cleanup in
3762	* merge_reloc_roots()
3763	*/
3764	err = prepare_to_merge(rc, err);
3765
3766	ret = merge_reloc_roots(rc);
3767	if (ret && !err)
3768	err = ret;
3769
3770	rc->merge_reloc_tree = false;
3771	unset_reloc_control(rc);
3772	btrfs_block_rsv_release(fs_info, rc->block_rsv, (u64)-1, NULL);
3773
3774	/* get rid of pinned extents */
3775	ret = btrfs_commit_current_transaction(rc->extent_root);
3776	if (ret && !err)
3777	err = ret;
3778	out_free:
3779	ret = clean_dirty_subvols(rc);
3780	if (ret < 0 && !err)
3781	err = ret;
3782	btrfs_free_block_rsv(fs_info, rc->block_rsv);
3783	return err;
3784	}
3785
3786	static int __insert_orphan_inode(struct btrfs_trans_handle *trans,
3787	struct btrfs_root *root, u64 objectid)
3788	{
3789	BTRFS_PATH_AUTO_FREE(path);
3790	struct btrfs_inode_item *item;
3791	struct extent_buffer *leaf;
3792	int ret;
3793
3794	path = btrfs_alloc_path();
3795	if (!path)
3796	return -ENOMEM;
3797
3798	ret = btrfs_insert_empty_inode(trans, root, path, objectid);
3799	if (ret)
3800	return ret;
3801
3802	leaf = path->nodes[0];
3803	item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_inode_item);
3804	memzero_extent_buffer(leaf, (unsigned long)item, sizeof(*item));
3805	btrfs_set_inode_generation(leaf, item, 1);
3806	btrfs_set_inode_size(leaf, item, 0);
3807	btrfs_set_inode_mode(leaf, item, S_IFREG \| 0600);
3808	btrfs_set_inode_flags(leaf, item, BTRFS_INODE_NOCOMPRESS \|
3809	BTRFS_INODE_PREALLOC);
3810	return 0;
3811	}
3812
3813	static void delete_orphan_inode(struct btrfs_trans_handle *trans,
3814	struct btrfs_root *root, u64 objectid)
3815	{
3816	BTRFS_PATH_AUTO_FREE(path);
3817	struct btrfs_key key;
3818	int ret = 0;
3819
3820	path = btrfs_alloc_path();
3821	if (!path) {
3822	ret = -ENOMEM;
3823	goto out;
3824	}
3825
3826	key.objectid = objectid;
3827	key.type = BTRFS_INODE_ITEM_KEY;
3828	key.offset = 0;
3829	ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
3830	if (ret) {
3831	if (ret > 0)
3832	ret = -ENOENT;
3833	goto out;
3834	}
3835	ret = btrfs_del_item(trans, root, path);
3836	out:
3837	if (ret)
3838	btrfs_abort_transaction(trans, ret);
3839	}
3840
3841	/*
3842	* helper to create inode for data relocation.
3843	* the inode is in data relocation tree and its link count is 0
3844	*/
3845	static noinline_for_stack struct inode *create_reloc_inode(
3846	const struct btrfs_block_group *group)
3847	{
3848	struct btrfs_fs_info *fs_info = group->fs_info;
3849	struct btrfs_inode *inode = NULL;
3850	struct btrfs_trans_handle *trans;
3851	struct btrfs_root *root;
3852	u64 objectid;
3853	int ret = 0;
3854
3855	root = btrfs_grab_root(fs_info->data_reloc_root);
3856	trans = btrfs_start_transaction(root, 6);
3857	if (IS_ERR(trans)) {
3858	btrfs_put_root(root);
3859	return ERR_CAST(trans);
3860	}
3861
3862	ret = btrfs_get_free_objectid(root, &objectid);
3863	if (ret)
3864	goto out;
3865
3866	ret = __insert_orphan_inode(trans, root, objectid);
3867	if (ret)
3868	goto out;
3869
3870	inode = btrfs_iget(objectid, root);
3871	if (IS_ERR(inode)) {
3872	delete_orphan_inode(trans, root, objectid);
3873	ret = PTR_ERR(inode);
3874	inode = NULL;
3875	goto out;
3876	}
3877	inode->reloc_block_group_start = group->start;
3878
3879	ret = btrfs_orphan_add(trans, inode);
3880	out:
3881	btrfs_put_root(root);
3882	btrfs_end_transaction(trans);
3883	btrfs_btree_balance_dirty(fs_info);
3884	if (ret) {
3885	if (inode)
3886	iput(&inode->vfs_inode);
3887	return ERR_PTR(ret);
3888	}
3889	return &inode->vfs_inode;
3890	}
3891
3892	/*
3893	* Mark start of chunk relocation that is cancellable. Check if the cancellation
3894	* has been requested meanwhile and don't start in that case.
3895	* NOTE: if this returns an error, reloc_chunk_end() must not be called.
3896	*
3897	* Return:
3898	* 0 success
3899	* -EINPROGRESS operation is already in progress, that's probably a bug
3900	* -ECANCELED cancellation request was set before the operation started
3901	*/
3902	static int reloc_chunk_start(struct btrfs_fs_info *fs_info)
3903	{
3904	if (test_and_set_bit(BTRFS_FS_RELOC_RUNNING, &fs_info->flags)) {
3905	/* This should not happen */
3906	btrfs_err(fs_info, "reloc already running, cannot start");
3907	return -EINPROGRESS;
3908	}
3909
3910	if (atomic_read(&fs_info->reloc_cancel_req) > 0) {
3911	btrfs_info(fs_info, "chunk relocation canceled on start");
3912	/* On cancel, clear all requests. */
3913	clear_and_wake_up_bit(BTRFS_FS_RELOC_RUNNING, &fs_info->flags);
3914	atomic_set(&fs_info->reloc_cancel_req, 0);
3915	return -ECANCELED;
3916	}
3917	return 0;
3918	}
3919
3920	/*
3921	* Mark end of chunk relocation that is cancellable and wake any waiters.
3922	* NOTE: call only if a previous call to reloc_chunk_start() succeeded.
3923	*/
3924	static void reloc_chunk_end(struct btrfs_fs_info *fs_info)
3925	{
3926	ASSERT(test_bit(BTRFS_FS_RELOC_RUNNING, &fs_info->flags));
3927	/* Requested after start, clear bit first so any waiters can continue */
3928	if (atomic_read(&fs_info->reloc_cancel_req) > 0)
3929	btrfs_info(fs_info, "chunk relocation canceled during operation");
3930	clear_and_wake_up_bit(BTRFS_FS_RELOC_RUNNING, &fs_info->flags);
3931	atomic_set(&fs_info->reloc_cancel_req, 0);
3932	}
3933
3934	static struct reloc_control alloc_reloc_control(struct btrfs_fs_info fs_info)
3935	{
3936	struct reloc_control *rc;
3937
3938	rc = kzalloc_obj(*rc, GFP_NOFS);
3939	if (!rc)
3940	return NULL;
3941
3942	INIT_LIST_HEAD(&rc->reloc_roots);
3943	INIT_LIST_HEAD(&rc->dirty_subvol_roots);
3944	btrfs_backref_init_cache(fs_info, &rc->backref_cache, true);
3945	rc->reloc_root_tree.rb_root = RB_ROOT;
3946	spin_lock_init(&rc->reloc_root_tree.lock);
3947	btrfs_extent_io_tree_init(fs_info, &rc->processed_blocks, IO_TREE_RELOC_BLOCKS);
3948	refcount_set(&rc->refs, 1);
3949
3950	return rc;
3951	}
3952
3953	/*
3954	* Print the block group being relocated
3955	*/
3956	static void describe_relocation(struct btrfs_block_group *block_group)
3957	{
3958	char buf[128] = "NONE";
3959
3960	btrfs_describe_block_groups(block_group->flags, buf, sizeof(buf));
3961
3962	btrfs_info(block_group->fs_info, "relocating block group %llu flags %s",
3963	block_group->start, buf);
3964	}
3965
3966	static const char *stage_to_string(enum reloc_stage stage)
3967	{
3968	if (stage == MOVE_DATA_EXTENTS)
3969	return "move data extents";
3970	if (stage == UPDATE_DATA_PTRS)
3971	return "update data pointers";
3972	return "unknown";
3973	}
3974
3975	static int add_remap_tree_entries(struct btrfs_trans_handle trans, struct btrfs_path path,
3976	struct btrfs_key *entries, unsigned int num_entries)
3977	{
3978	int ret;
3979	struct btrfs_fs_info *fs_info = trans->fs_info;
3980	struct btrfs_item_batch batch;
3981	u32 *data_sizes;
3982	u32 max_items;
3983
3984	max_items = BTRFS_LEAF_DATA_SIZE(trans->fs_info) / sizeof(struct btrfs_item);
3985
3986	data_sizes = kzalloc_objs(u32, min_t(u32, num_entries, max_items), GFP_NOFS);
3987	if (!data_sizes)
3988	return -ENOMEM;
3989
3990	while (true) {
3991	batch.keys = entries;
3992	batch.data_sizes = data_sizes;
3993	batch.total_data_size = 0;
3994	batch.nr = min_t(u32, num_entries, max_items);
3995
3996	ret = btrfs_insert_empty_items(trans, fs_info->remap_root, path, &batch);
3997	btrfs_release_path(path);
3998
3999	if (ret \|\| num_entries <= max_items)
4000	break;
4001
4002	num_entries -= max_items;
4003	entries += max_items;
4004	}
4005
4006	kfree(data_sizes);
4007
4008	return ret;
4009	}
4010
4011	struct space_run {
4012	u64 start;
4013	u64 end;
4014	};
4015
4016	static void parse_bitmap(u64 block_size, const unsigned long *bitmap,
4017	unsigned long size, u64 address, struct space_run *space_runs,
4018	unsigned int *num_space_runs)
4019	{
4020	unsigned long pos, end;
4021	u64 run_start, run_length;
4022
4023	pos = find_first_bit(bitmap, size);
4024	if (pos == size)
4025	return;
4026
4027	while (true) {
4028	end = find_next_zero_bit(bitmap, size, pos);
4029
4030	run_start = address + (pos * block_size);
4031	run_length = (end - pos) * block_size;
4032
4033	if (*num_space_runs != 0 &&
4034	space_runs[*num_space_runs - 1].end == run_start) {
4035	space_runs[*num_space_runs - 1].end += run_length;
4036	} else {
4037	space_runs[*num_space_runs].start = run_start;
4038	space_runs[*num_space_runs].end = run_start + run_length;
4039
4040	(*num_space_runs)++;
4041	}
4042
4043	if (end == size)
4044	break;
4045
4046	pos = find_next_bit(bitmap, size, end + 1);
4047	if (pos == size)
4048	break;
4049	}
4050	}
4051
4052	static void adjust_block_group_remap_bytes(struct btrfs_trans_handle *trans,
4053	struct btrfs_block_group *bg, s64 diff)
4054	{
4055	struct btrfs_fs_info *fs_info = trans->fs_info;
4056	bool bg_already_dirty = true;
4057	bool mark_unused = false;
4058
4059	spin_lock(&bg->lock);
4060	bg->remap_bytes += diff;
4061	if (bg->used == 0 && bg->remap_bytes == 0)
4062	mark_unused = true;
4063	spin_unlock(&bg->lock);
4064
4065	if (mark_unused)
4066	btrfs_mark_bg_unused(bg);
4067
4068	spin_lock(&trans->transaction->dirty_bgs_lock);
4069	if (list_empty(&bg->dirty_list)) {
4070	list_add_tail(&bg->dirty_list, &trans->transaction->dirty_bgs);
4071	bg_already_dirty = false;
4072	btrfs_get_block_group(bg);
4073	}
4074	spin_unlock(&trans->transaction->dirty_bgs_lock);
4075
4076	/* Modified block groups are accounted for in the delayed_refs_rsv. */
4077	if (!bg_already_dirty)
4078	btrfs_inc_delayed_refs_rsv_bg_updates(fs_info);
4079	}
4080
4081	/* Private structure for I/O from copy_remapped_data(). */
4082	struct reloc_io_private {
4083	struct completion done;
4084	refcount_t pending_refs;
4085	blk_status_t status;
4086	};
4087
4088	static void reloc_endio(struct btrfs_bio *bbio)
4089	{
4090	struct reloc_io_private *priv = bbio->private;
4091
4092	if (bbio->bio.bi_status)
4093	WRITE_ONCE(priv->status, bbio->bio.bi_status);
4094
4095	if (refcount_dec_and_test(&priv->pending_refs))
4096	complete(&priv->done);
4097
4098	bio_put(&bbio->bio);
4099	}
4100
4101	static int copy_remapped_data_io(struct btrfs_fs_info *fs_info,
4102	struct reloc_io_private *priv,
4103	struct page **pages, u64 addr, u64 length,
4104	blk_opf_t op)
4105	{
4106	struct btrfs_bio *bbio;
4107	int i;
4108
4109	init_completion(&priv->done);
4110	refcount_set(&priv->pending_refs, 1);
4111	priv->status = 0;
4112
4113	bbio = btrfs_bio_alloc(BIO_MAX_VECS, op, BTRFS_I(fs_info->btree_inode),
4114	addr, reloc_endio, priv);
4115	bbio->bio.bi_iter.bi_sector = (addr >> SECTOR_SHIFT);
4116	bbio->is_remap = true;
4117
4118	i = 0;
4119	do {
4120	size_t bytes = min_t(u64, length, PAGE_SIZE);
4121
4122	if (bio_add_page(&bbio->bio, pages[i], bytes, 0) < bytes) {
4123	refcount_inc(&priv->pending_refs);
4124	btrfs_submit_bbio(bbio, 0);
4125
4126	bbio = btrfs_bio_alloc(BIO_MAX_VECS, op,
4127	BTRFS_I(fs_info->btree_inode),
4128	addr, reloc_endio, priv);
4129	bbio->bio.bi_iter.bi_sector = (addr >> SECTOR_SHIFT);
4130	bbio->is_remap = true;
4131	continue;
4132	}
4133
4134	i++;
4135	addr += bytes;
4136	length -= bytes;
4137	} while (length);
4138
4139	refcount_inc(&priv->pending_refs);
4140	btrfs_submit_bbio(bbio, 0);
4141
4142	if (!refcount_dec_and_test(&priv->pending_refs))
4143	wait_for_completion_io(&priv->done);
4144
4145	return blk_status_to_errno(READ_ONCE(priv->status));
4146	}
4147
4148	static int copy_remapped_data(struct btrfs_fs_info *fs_info, u64 old_addr,
4149	u64 new_addr, u64 length)
4150	{
4151	int ret;
4152	const u64 copy_len = min_t(u64, length, SZ_1M);
4153	struct page **pages;
4154	struct reloc_io_private priv;
4155	const unsigned int nr_pages = DIV_ROUND_UP(copy_len, PAGE_SIZE);
4156
4157	pages = kzalloc_objs(struct page *, nr_pages, GFP_NOFS);
4158	if (!pages)
4159	return -ENOMEM;
4160
4161	ret = btrfs_alloc_page_array(nr_pages, pages, GFP_NOFS);
4162	if (ret) {
4163	ret = -ENOMEM;
4164	goto end;
4165	}
4166
4167	/* Copy 1MB at a time, to avoid using too much memory. */
4168	do {
4169	u64 to_copy = min_t(u64, length, copy_len);
4170
4171	/* Limit to one bio. */
4172	to_copy = min_t(u64, to_copy, BIO_MAX_VECS << PAGE_SHIFT);
4173
4174	ret = copy_remapped_data_io(fs_info, &priv, pages, old_addr,
4175	to_copy, REQ_OP_READ);
4176	if (ret)
4177	goto end;
4178
4179	ret = copy_remapped_data_io(fs_info, &priv, pages, new_addr,
4180	to_copy, REQ_OP_WRITE);
4181	if (ret)
4182	goto end;
4183
4184	if (to_copy == length)
4185	break;
4186
4187	old_addr += to_copy;
4188	new_addr += to_copy;
4189	length -= to_copy;
4190	} while (true);
4191
4192	ret = 0;
4193	end:
4194	for (int i = 0; i < nr_pages; i++) {
4195	if (pages[i])
4196	__free_page(pages[i]);
4197	}
4198	kfree(pages);
4199
4200	return ret;
4201	}
4202
4203	static int add_remap_item(struct btrfs_trans_handle *trans,
4204	struct btrfs_path *path, u64 new_addr, u64 length,
4205	u64 old_addr)
4206	{
4207	struct btrfs_fs_info *fs_info = trans->fs_info;
4208	struct btrfs_remap_item remap = { 0 };
4209	struct btrfs_key key;
4210	struct extent_buffer *leaf;
4211	int ret;
4212
4213	key.objectid = old_addr;
4214	key.type = BTRFS_REMAP_KEY;
4215	key.offset = length;
4216
4217	ret = btrfs_insert_empty_item(trans, fs_info->remap_root, path,
4218	&key, sizeof(struct btrfs_remap_item));
4219	if (ret)
4220	return ret;
4221
4222	leaf = path->nodes[0];
4223	btrfs_set_stack_remap_address(&remap, new_addr);
4224	write_extent_buffer(leaf, &remap, btrfs_item_ptr_offset(leaf, path->slots[0]),
4225	sizeof(struct btrfs_remap_item));
4226
4227	btrfs_release_path(path);
4228
4229	return 0;
4230	}
4231
4232	static int add_remap_backref_item(struct btrfs_trans_handle *trans,
4233	struct btrfs_path *path, u64 new_addr,
4234	u64 length, u64 old_addr)
4235	{
4236	struct btrfs_fs_info *fs_info = trans->fs_info;
4237	struct btrfs_remap_item remap = { 0 };
4238	struct btrfs_key key;
4239	struct extent_buffer *leaf;
4240	int ret;
4241
4242	key.objectid = new_addr;
4243	key.type = BTRFS_REMAP_BACKREF_KEY;
4244	key.offset = length;
4245
4246	ret = btrfs_insert_empty_item(trans, fs_info->remap_root, path, &key,
4247	sizeof(struct btrfs_remap_item));
4248	if (ret)
4249	return ret;
4250
4251	leaf = path->nodes[0];
4252	btrfs_set_stack_remap_address(&remap, old_addr);
4253	write_extent_buffer(leaf, &remap, btrfs_item_ptr_offset(leaf, path->slots[0]),
4254	sizeof(struct btrfs_remap_item));
4255
4256	btrfs_release_path(path);
4257
4258	return 0;
4259	}
4260
4261	static int move_existing_remap(struct btrfs_fs_info *fs_info,
4262	struct btrfs_path *path,
4263	struct btrfs_block_group *bg, u64 new_addr,
4264	u64 length, u64 old_addr)
4265	{
4266	struct btrfs_trans_handle *trans;
4267	struct extent_buffer *leaf;
4268	struct btrfs_remap_item *remap_ptr;
4269	struct btrfs_remap_item remap = { 0 };
4270	struct btrfs_key key, ins;
4271	u64 dest_addr, dest_length, min_size;
4272	struct btrfs_block_group *dest_bg;
4273	int ret;
4274	const bool is_data = (bg->flags & BTRFS_BLOCK_GROUP_DATA);
4275	struct btrfs_space_info *sinfo = bg->space_info;
4276	bool mutex_taken = false;
4277	bool bg_needs_free_space;
4278
4279	spin_lock(&sinfo->lock);
4280	btrfs_space_info_update_bytes_may_use(sinfo, length);
4281	spin_unlock(&sinfo->lock);
4282
4283	if (is_data)
4284	min_size = fs_info->sectorsize;
4285	else
4286	min_size = fs_info->nodesize;
4287
4288	ret = btrfs_reserve_extent(fs_info->fs_root, length, length, min_size,
4289	0, 0, &ins, is_data, false);
4290	if (unlikely(ret)) {
4291	spin_lock(&sinfo->lock);
4292	btrfs_space_info_update_bytes_may_use(sinfo, -length);
4293	spin_unlock(&sinfo->lock);
4294	return ret;
4295	}
4296
4297	if (ins.offset < length) {
4298	spin_lock(&sinfo->lock);
4299	btrfs_space_info_update_bytes_may_use(sinfo, ins.offset - length);
4300	spin_unlock(&sinfo->lock);
4301	}
4302
4303	dest_addr = ins.objectid;
4304	dest_length = ins.offset;
4305
4306	dest_bg = btrfs_lookup_block_group(fs_info, dest_addr);
4307
4308	if (!is_data && !IS_ALIGNED(dest_length, fs_info->nodesize)) {
4309	u64 new_length = ALIGN_DOWN(dest_length, fs_info->nodesize);
4310
4311	btrfs_free_reserved_extent(fs_info, dest_addr + new_length,
4312	dest_length - new_length, 0);
4313
4314	dest_length = new_length;
4315	}
4316
4317	trans = btrfs_join_transaction(fs_info->remap_root);
4318	if (IS_ERR(trans)) {
4319	ret = PTR_ERR(trans);
4320	trans = NULL;
4321	goto end;
4322	}
4323
4324	mutex_lock(&fs_info->remap_mutex);
4325	mutex_taken = true;
4326
4327	/* Find old remap entry. */
4328	key.objectid = old_addr;
4329	key.type = BTRFS_REMAP_KEY;
4330	key.offset = length;
4331
4332	ret = btrfs_search_slot(trans, fs_info->remap_root, &key, path, 0, 1);
4333	if (ret == 1) {
4334	/*
4335	* Not a problem if the remap entry wasn't found: that means
4336	* that another transaction has deallocated the data.
4337	* move_existing_remaps() loops until the BG contains no
4338	* remaps, so we can just return 0 in this case.
4339	*/
4340	btrfs_release_path(path);
4341	ret = 0;
4342	goto end;
4343	} else if (unlikely(ret)) {
4344	goto end;
4345	}
4346
4347	ret = copy_remapped_data(fs_info, new_addr, dest_addr, dest_length);
4348	if (unlikely(ret))
4349	goto end;
4350
4351	/* Change data of old remap entry. */
4352	leaf = path->nodes[0];
4353	remap_ptr = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_remap_item);
4354	btrfs_set_remap_address(leaf, remap_ptr, dest_addr);
4355	btrfs_mark_buffer_dirty(trans, leaf);
4356
4357	if (dest_length != length) {
4358	key.offset = dest_length;
4359	btrfs_set_item_key_safe(trans, path, &key);
4360	}
4361
4362	btrfs_release_path(path);
4363
4364	if (dest_length != length) {
4365	/* Add remap item for remainder. */
4366	ret = add_remap_item(trans, path, new_addr + dest_length,
4367	length - dest_length, old_addr + dest_length);
4368	if (unlikely(ret))
4369	goto end;
4370	}
4371
4372	/* Change or remove old backref. */
4373	key.objectid = new_addr;
4374	key.type = BTRFS_REMAP_BACKREF_KEY;
4375	key.offset = length;
4376
4377	ret = btrfs_search_slot(trans, fs_info->remap_root, &key, path, -1, 1);
4378	if (unlikely(ret)) {
4379	if (ret == 1) {
4380	btrfs_release_path(path);
4381	ret = -ENOENT;
4382	}
4383	goto end;
4384	}
4385
4386	leaf = path->nodes[0];
4387
4388	if (dest_length == length) {
4389	ret = btrfs_del_item(trans, fs_info->remap_root, path);
4390	if (unlikely(ret)) {
4391	btrfs_release_path(path);
4392	goto end;
4393	}
4394	} else {
4395	key.objectid += dest_length;
4396	key.offset -= dest_length;
4397	btrfs_set_item_key_safe(trans, path, &key);
4398	btrfs_set_stack_remap_address(&remap, old_addr + dest_length);
4399
4400	write_extent_buffer(leaf, &remap,
4401	btrfs_item_ptr_offset(leaf, path->slots[0]),
4402	sizeof(struct btrfs_remap_item));
4403	}
4404
4405	btrfs_release_path(path);
4406
4407	/* Add new backref. */
4408	ret = add_remap_backref_item(trans, path, dest_addr, dest_length, old_addr);
4409	if (unlikely(ret))
4410	goto end;
4411
4412	adjust_block_group_remap_bytes(trans, bg, -dest_length);
4413
4414	ret = btrfs_add_to_free_space_tree(trans, new_addr, dest_length);
4415	if (unlikely(ret))
4416	goto end;
4417
4418	adjust_block_group_remap_bytes(trans, dest_bg, dest_length);
4419
4420	mutex_lock(&dest_bg->free_space_lock);
4421	bg_needs_free_space = test_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE,
4422	&dest_bg->runtime_flags);
4423	mutex_unlock(&dest_bg->free_space_lock);
4424
4425	if (bg_needs_free_space) {
4426	ret = btrfs_add_block_group_free_space(trans, dest_bg);
4427	if (unlikely(ret))
4428	goto end;
4429	}
4430
4431	ret = btrfs_remove_from_free_space_tree(trans, dest_addr, dest_length);
4432	if (unlikely(ret)) {
4433	btrfs_remove_from_free_space_tree(trans, new_addr, dest_length);
4434	goto end;
4435	}
4436
4437	ret = 0;
4438
4439	end:
4440	if (mutex_taken)
4441	mutex_unlock(&fs_info->remap_mutex);
4442
4443	btrfs_dec_block_group_reservations(fs_info, dest_addr);
4444
4445	if (unlikely(ret)) {
4446	btrfs_free_reserved_extent(fs_info, dest_addr, dest_length, 0);
4447
4448	if (trans) {
4449	btrfs_abort_transaction(trans, ret);
4450	btrfs_end_transaction(trans);
4451	}
4452	} else {
4453	btrfs_free_reserved_bytes(dest_bg, dest_length, 0);
4454
4455	ret = btrfs_commit_transaction(trans);
4456	}
4457
4458	btrfs_put_block_group(dest_bg);
4459
4460	return ret;
4461	}
4462
4463	static int move_existing_remaps(struct btrfs_fs_info *fs_info,
4464	struct btrfs_block_group *bg,
4465	struct btrfs_path *path)
4466	{
4467	int ret;
4468	struct btrfs_key key;
4469	struct extent_buffer *leaf;
4470	struct btrfs_remap_item *remap;
4471	u64 old_addr;
4472
4473	/* Look for backrefs in remap tree. */
4474	while (bg->remap_bytes > 0) {
4475	key.objectid = bg->start;
4476	key.type = BTRFS_REMAP_BACKREF_KEY;
4477	key.offset = 0;
4478
4479	ret = btrfs_search_slot(NULL, fs_info->remap_root, &key, path, 0, 0);
4480	if (ret < 0)
4481	return ret;
4482
4483	leaf = path->nodes[0];
4484
4485	if (path->slots[0] >= btrfs_header_nritems(leaf)) {
4486	ret = btrfs_next_leaf(fs_info->remap_root, path);
4487	if (ret < 0) {
4488	btrfs_release_path(path);
4489	return ret;
4490	}
4491
4492	if (ret) {
4493	btrfs_release_path(path);
4494	break;
4495	}
4496
4497	leaf = path->nodes[0];
4498	}
4499
4500	btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
4501
4502	if (key.type != BTRFS_REMAP_BACKREF_KEY) {
4503	path->slots[0]++;
4504
4505	if (path->slots[0] >= btrfs_header_nritems(leaf)) {
4506	ret = btrfs_next_leaf(fs_info->remap_root, path);
4507	if (ret < 0) {
4508	btrfs_release_path(path);
4509	return ret;
4510	}
4511
4512	if (ret) {
4513	btrfs_release_path(path);
4514	break;
4515	}
4516
4517	leaf = path->nodes[0];
4518	}
4519
4520	btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
4521	}
4522
4523	remap = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_remap_item);
4524	old_addr = btrfs_remap_address(leaf, remap);
4525
4526	btrfs_release_path(path);
4527
4528	ret = move_existing_remap(fs_info, path, bg, key.objectid,
4529	key.offset, old_addr);
4530	if (ret)
4531	return ret;
4532	}
4533
4534	ASSERT(bg->remap_bytes == 0);
4535
4536	return 0;
4537	}
4538
4539	static int create_remap_tree_entries(struct btrfs_trans_handle *trans,
4540	struct btrfs_path *path,
4541	struct btrfs_block_group *bg)
4542	{
4543	struct btrfs_fs_info *fs_info = trans->fs_info;
4544	struct btrfs_free_space_info *fsi;
4545	struct btrfs_key key, found_key;
4546	struct extent_buffer *leaf;
4547	struct btrfs_root *space_root;
4548	u32 extent_count;
4549	struct space_run *space_runs = NULL;
4550	unsigned int num_space_runs = 0;
4551	struct btrfs_key *entries = NULL;
4552	unsigned int max_entries, num_entries;
4553	int ret;
4554
4555	mutex_lock(&bg->free_space_lock);
4556
4557	if (test_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE, &bg->runtime_flags)) {
4558	mutex_unlock(&bg->free_space_lock);
4559
4560	ret = btrfs_add_block_group_free_space(trans, bg);
4561	if (ret)
4562	return ret;
4563
4564	mutex_lock(&bg->free_space_lock);
4565	}
4566
4567	fsi = btrfs_search_free_space_info(trans, bg, path, 0);
4568	if (IS_ERR(fsi)) {
4569	mutex_unlock(&bg->free_space_lock);
4570	return PTR_ERR(fsi);
4571	}
4572
4573	extent_count = btrfs_free_space_extent_count(path->nodes[0], fsi);
4574
4575	btrfs_release_path(path);
4576
4577	space_runs = kmalloc_objs(*space_runs, extent_count, GFP_NOFS);
4578	if (!space_runs) {
4579	mutex_unlock(&bg->free_space_lock);
4580	return -ENOMEM;
4581	}
4582
4583	key.objectid = bg->start;
4584	key.type = 0;
4585	key.offset = 0;
4586
4587	space_root = btrfs_free_space_root(bg);
4588
4589	ret = btrfs_search_slot(trans, space_root, &key, path, 0, 0);
4590	if (ret < 0) {
4591	mutex_unlock(&bg->free_space_lock);
4592	goto out;
4593	}
4594
4595	ret = 0;
4596
4597	while (true) {
4598	leaf = path->nodes[0];
4599
4600	btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
4601
4602	if (found_key.objectid >= bg->start + bg->length)
4603	break;
4604
4605	if (found_key.type == BTRFS_FREE_SPACE_EXTENT_KEY) {
4606	if (num_space_runs != 0 &&
4607	space_runs[num_space_runs - 1].end == found_key.objectid) {
4608	space_runs[num_space_runs - 1].end =
4609	found_key.objectid + found_key.offset;
4610	} else {
4611	ASSERT(num_space_runs < extent_count);
4612
4613	space_runs[num_space_runs].start = found_key.objectid;
4614	space_runs[num_space_runs].end =
4615	found_key.objectid + found_key.offset;
4616
4617	num_space_runs++;
4618	}
4619	} else if (found_key.type == BTRFS_FREE_SPACE_BITMAP_KEY) {
4620	void *bitmap;
4621	unsigned long offset;
4622	u32 data_size;
4623
4624	offset = btrfs_item_ptr_offset(leaf, path->slots[0]);
4625	data_size = btrfs_item_size(leaf, path->slots[0]);
4626
4627	if (data_size != 0) {
4628	bitmap = kmalloc(data_size, GFP_NOFS);
4629	if (!bitmap) {
4630	mutex_unlock(&bg->free_space_lock);
4631	ret = -ENOMEM;
4632	goto out;
4633	}
4634
4635	read_extent_buffer(leaf, bitmap, offset, data_size);
4636
4637	parse_bitmap(fs_info->sectorsize, bitmap,
4638	data_size * BITS_PER_BYTE,
4639	found_key.objectid, space_runs,
4640	&num_space_runs);
4641
4642	ASSERT(num_space_runs <= extent_count);
4643
4644	kfree(bitmap);
4645	}
4646	}
4647
4648	path->slots[0]++;
4649
4650	if (path->slots[0] >= btrfs_header_nritems(leaf)) {
4651	ret = btrfs_next_leaf(space_root, path);
4652	if (ret != 0) {
4653	if (ret == 1)
4654	ret = 0;
4655	break;
4656	}
4657	leaf = path->nodes[0];
4658	}
4659	}
4660
4661	btrfs_release_path(path);
4662
4663	mutex_unlock(&bg->free_space_lock);
4664
4665	max_entries = extent_count + 2;
4666	entries = kmalloc_objs(*entries, max_entries, GFP_NOFS);
4667	if (!entries) {
4668	ret = -ENOMEM;
4669	goto out;
4670	}
4671
4672	num_entries = 0;
4673
4674	if (num_space_runs == 0) {
4675	entries[num_entries].objectid = bg->start;
4676	entries[num_entries].type = BTRFS_IDENTITY_REMAP_KEY;
4677	entries[num_entries].offset = bg->length;
4678	num_entries++;
4679	} else {
4680	if (space_runs[0].start > bg->start) {
4681	entries[num_entries].objectid = bg->start;
4682	entries[num_entries].type = BTRFS_IDENTITY_REMAP_KEY;
4683	entries[num_entries].offset = space_runs[0].start - bg->start;
4684	num_entries++;
4685	}
4686
4687	for (unsigned int i = 1; i < num_space_runs; i++) {
4688	entries[num_entries].objectid = space_runs[i - 1].end;
4689	entries[num_entries].type = BTRFS_IDENTITY_REMAP_KEY;
4690	entries[num_entries].offset =
4691	space_runs[i].start - space_runs[i - 1].end;
4692	num_entries++;
4693	}
4694
4695	if (space_runs[num_space_runs - 1].end < bg->start + bg->length) {
4696	entries[num_entries].objectid =
4697	space_runs[num_space_runs - 1].end;
4698	entries[num_entries].type = BTRFS_IDENTITY_REMAP_KEY;
4699	entries[num_entries].offset =
4700	bg->start + bg->length - space_runs[num_space_runs - 1].end;
4701	num_entries++;
4702	}
4703
4704	if (num_entries == 0)
4705	goto out;
4706	}
4707
4708	bg->identity_remap_count = num_entries;
4709
4710	ret = add_remap_tree_entries(trans, path, entries, num_entries);
4711
4712	out:
4713	kfree(entries);
4714	kfree(space_runs);
4715
4716	return ret;
4717	}
4718
4719	static int find_next_identity_remap(struct btrfs_trans_handle *trans,
4720	struct btrfs_path *path, u64 bg_end,
4721	u64 last_start, u64 start, u64 length)
4722	{
4723	int ret;
4724	struct btrfs_key key, found_key;
4725	struct btrfs_root *remap_root = trans->fs_info->remap_root;
4726	struct extent_buffer *leaf;
4727
4728	key.objectid = last_start;
4729	key.type = BTRFS_IDENTITY_REMAP_KEY;
4730	key.offset = 0;
4731
4732	ret = btrfs_search_slot(trans, remap_root, &key, path, 0, 0);
4733	if (ret < 0)
4734	goto out;
4735
4736	leaf = path->nodes[0];
4737	while (true) {
4738	if (path->slots[0] >= btrfs_header_nritems(leaf)) {
4739	ret = btrfs_next_leaf(remap_root, path);
4740
4741	if (ret != 0) {
4742	if (ret == 1)
4743	ret = -ENOENT;
4744	goto out;
4745	}
4746
4747	leaf = path->nodes[0];
4748	}
4749
4750	btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
4751
4752	if (found_key.objectid >= bg_end) {
4753	ret = -ENOENT;
4754	goto out;
4755	}
4756
4757	if (found_key.type == BTRFS_IDENTITY_REMAP_KEY) {
4758	*start = found_key.objectid;
4759	*length = found_key.offset;
4760	ret = 0;
4761	goto out;
4762	}
4763
4764	path->slots[0]++;
4765	}
4766
4767	out:
4768	btrfs_release_path(path);
4769
4770	return ret;
4771	}
4772
4773	static int remove_chunk_stripes(struct btrfs_trans_handle *trans,
4774	struct btrfs_chunk_map *chunk_map,
4775	struct btrfs_path *path)
4776	{
4777	struct btrfs_fs_info *fs_info = trans->fs_info;
4778	struct btrfs_key key;
4779	struct extent_buffer *leaf;
4780	struct btrfs_chunk *chunk;
4781	int ret;
4782
4783	key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
4784	key.type = BTRFS_CHUNK_ITEM_KEY;
4785	key.offset = chunk_map->start;
4786
4787	btrfs_reserve_chunk_metadata(trans, false);
4788
4789	ret = btrfs_search_slot(trans, fs_info->chunk_root, &key, path, 0, 1);
4790	if (ret) {
4791	if (ret == 1) {
4792	btrfs_release_path(path);
4793	ret = -ENOENT;
4794	}
4795	btrfs_trans_release_chunk_metadata(trans);
4796	return ret;
4797	}
4798
4799	leaf = path->nodes[0];
4800
4801	chunk = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_chunk);
4802	btrfs_set_chunk_num_stripes(leaf, chunk, 0);
4803	btrfs_set_chunk_sub_stripes(leaf, chunk, 0);
4804
4805	btrfs_truncate_item(trans, path, offsetof(struct btrfs_chunk, stripe), 1);
4806
4807	btrfs_mark_buffer_dirty(trans, leaf);
4808
4809	btrfs_release_path(path);
4810	btrfs_trans_release_chunk_metadata(trans);
4811
4812	return 0;
4813	}
4814
4815	int btrfs_last_identity_remap_gone(struct btrfs_chunk_map *chunk_map,
4816	struct btrfs_block_group *bg)
4817	{
4818	struct btrfs_fs_info *fs_info = bg->fs_info;
4819	struct btrfs_trans_handle *trans;
4820	int ret;
4821	unsigned int num_items;
4822	BTRFS_PATH_AUTO_FREE(path);
4823
4824	path = btrfs_alloc_path();
4825	if (!path)
4826	return -ENOMEM;
4827
4828	/*
4829	* One item for each entry we're removing in the dev extents tree, and
4830	* another for each device. DUP chunks are all on one device,
4831	* everything else has one device per stripe.
4832	*/
4833	if (bg->flags & BTRFS_BLOCK_GROUP_DUP)
4834	num_items = chunk_map->num_stripes + 1;
4835	else
4836	num_items = 2 * chunk_map->num_stripes;
4837
4838	trans = btrfs_start_transaction_fallback_global_rsv(fs_info->tree_root, num_items);
4839	if (IS_ERR(trans))
4840	return PTR_ERR(trans);
4841
4842	ret = btrfs_remove_dev_extents(trans, chunk_map);
4843	if (unlikely(ret)) {
4844	btrfs_abort_transaction(trans, ret);
4845	btrfs_end_transaction(trans);
4846	return ret;
4847	}
4848
4849	mutex_lock(&trans->fs_info->chunk_mutex);
4850	for (unsigned int i = 0; i < chunk_map->num_stripes; i++) {
4851	ret = btrfs_update_device(trans, chunk_map->stripes[i].dev);
4852	if (unlikely(ret)) {
4853	mutex_unlock(&trans->fs_info->chunk_mutex);
4854	btrfs_abort_transaction(trans, ret);
4855	btrfs_end_transaction(trans);
4856	return ret;
4857	}
4858	}
4859	mutex_unlock(&trans->fs_info->chunk_mutex);
4860
4861	write_lock(&trans->fs_info->mapping_tree_lock);
4862	btrfs_chunk_map_device_clear_bits(chunk_map, CHUNK_ALLOCATED);
4863	write_unlock(&trans->fs_info->mapping_tree_lock);
4864
4865	btrfs_remove_bg_from_sinfo(bg);
4866
4867	spin_lock(&bg->lock);
4868	clear_bit(BLOCK_GROUP_FLAG_STRIPE_REMOVAL_PENDING, &bg->runtime_flags);
4869	spin_unlock(&bg->lock);
4870
4871	ret = remove_chunk_stripes(trans, chunk_map, path);
4872	if (unlikely(ret)) {
4873	btrfs_abort_transaction(trans, ret);
4874	btrfs_end_transaction(trans);
4875	return ret;
4876	}
4877
4878	ret = btrfs_commit_transaction(trans);
4879	if (ret)
4880	return ret;
4881
4882	return 0;
4883	}
4884
4885	static void adjust_identity_remap_count(struct btrfs_trans_handle *trans,
4886	struct btrfs_block_group *bg, int delta)
4887	{
4888	struct btrfs_fs_info *fs_info = trans->fs_info;
4889	bool bg_already_dirty = true;
4890	bool mark_fully_remapped = false;
4891
4892	WARN_ON(delta < 0 && -delta > bg->identity_remap_count);
4893
4894	spin_lock(&bg->lock);
4895
4896	bg->identity_remap_count += delta;
4897
4898	if (bg->identity_remap_count == 0 &&
4899	!test_bit(BLOCK_GROUP_FLAG_FULLY_REMAPPED, &bg->runtime_flags)) {
4900	set_bit(BLOCK_GROUP_FLAG_FULLY_REMAPPED, &bg->runtime_flags);
4901	mark_fully_remapped = true;
4902	}
4903
4904	spin_unlock(&bg->lock);
4905
4906	spin_lock(&trans->transaction->dirty_bgs_lock);
4907	if (list_empty(&bg->dirty_list)) {
4908	list_add_tail(&bg->dirty_list, &trans->transaction->dirty_bgs);
4909	bg_already_dirty = false;
4910	btrfs_get_block_group(bg);
4911	}
4912	spin_unlock(&trans->transaction->dirty_bgs_lock);
4913
4914	/* Modified block groups are accounted for in the delayed_refs_rsv. */
4915	if (!bg_already_dirty)
4916	btrfs_inc_delayed_refs_rsv_bg_updates(fs_info);
4917
4918	if (mark_fully_remapped)
4919	btrfs_mark_bg_fully_remapped(bg, trans);
4920	}
4921
4922	static int add_remap_entry(struct btrfs_trans_handle *trans,
4923	struct btrfs_path *path,
4924	struct btrfs_block_group *src_bg, u64 old_addr,
4925	u64 new_addr, u64 length)
4926	{
4927	struct btrfs_fs_info *fs_info = trans->fs_info;
4928	struct btrfs_key key, new_key;
4929	int ret;
4930	int identity_count_delta = 0;
4931
4932	key.objectid = old_addr;
4933	key.type = (u8)-1;
4934	key.offset = (u64)-1;
4935
4936	ret = btrfs_search_slot(trans, fs_info->remap_root, &key, path, -1, 1);
4937	if (ret < 0)
4938	goto end;
4939
4940	if (path->slots[0] == 0) {
4941	ret = -ENOENT;
4942	goto end;
4943	}
4944
4945	path->slots[0]--;
4946
4947	btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
4948
4949	if (key.type != BTRFS_IDENTITY_REMAP_KEY \|\|
4950	key.objectid > old_addr \|\|
4951	key.objectid + key.offset <= old_addr) {
4952	ret = -ENOENT;
4953	goto end;
4954	}
4955
4956	/* Shorten or delete identity mapping entry. */
4957	if (key.objectid == old_addr) {
4958	ret = btrfs_del_item(trans, fs_info->remap_root, path);
4959	if (ret)
4960	goto end;
4961
4962	identity_count_delta--;
4963	} else {
4964	new_key.objectid = key.objectid;
4965	new_key.type = BTRFS_IDENTITY_REMAP_KEY;
4966	new_key.offset = old_addr - key.objectid;
4967
4968	btrfs_set_item_key_safe(trans, path, &new_key);
4969	}
4970
4971	btrfs_release_path(path);
4972
4973	/* Create new remap entry. */
4974	ret = add_remap_item(trans, path, new_addr, length, old_addr);
4975	if (ret)
4976	goto end;
4977
4978	/* Add entry for remainder of identity mapping, if necessary. */
4979	if (key.objectid + key.offset != old_addr + length) {
4980	new_key.objectid = old_addr + length;
4981	new_key.type = BTRFS_IDENTITY_REMAP_KEY;
4982	new_key.offset = key.objectid + key.offset - old_addr - length;
4983
4984	ret = btrfs_insert_empty_item(trans, fs_info->remap_root,
4985	path, &new_key, 0);
4986	if (ret)
4987	goto end;
4988
4989	btrfs_release_path(path);
4990
4991	identity_count_delta++;
4992	}
4993
4994	/* Add backref. */
4995	ret = add_remap_backref_item(trans, path, new_addr, length, old_addr);
4996	if (ret)
4997	goto end;
4998
4999	if (identity_count_delta != 0)
5000	adjust_identity_remap_count(trans, src_bg, identity_count_delta);
5001
5002	end:
5003	btrfs_release_path(path);
5004
5005	return ret;
5006	}
5007
5008	static int mark_chunk_remapped(struct btrfs_trans_handle *trans,
5009	struct btrfs_path *path, u64 start)
5010	{
5011	struct btrfs_fs_info *fs_info = trans->fs_info;
5012	struct btrfs_chunk_map *chunk_map;
5013	struct btrfs_key key;
5014	u64 type;
5015	int ret;
5016	struct extent_buffer *leaf;
5017	struct btrfs_chunk *chunk;
5018
5019	read_lock(&fs_info->mapping_tree_lock);
5020
5021	chunk_map = btrfs_find_chunk_map_nolock(fs_info, start, 1);
5022	if (!chunk_map) {
5023	read_unlock(&fs_info->mapping_tree_lock);
5024	return -ENOENT;
5025	}
5026
5027	chunk_map->type \|= BTRFS_BLOCK_GROUP_REMAPPED;
5028	type = chunk_map->type;
5029
5030	read_unlock(&fs_info->mapping_tree_lock);
5031
5032	key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
5033	key.type = BTRFS_CHUNK_ITEM_KEY;
5034	key.offset = start;
5035
5036	ret = btrfs_search_slot(trans, fs_info->chunk_root, &key, path, 0, 1);
5037	if (ret == 1) {
5038	ret = -ENOENT;
5039	goto end;
5040	} else if (ret < 0)
5041	goto end;
5042
5043	leaf = path->nodes[0];
5044
5045	chunk = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_chunk);
5046	btrfs_set_chunk_type(leaf, chunk, type);
5047	btrfs_mark_buffer_dirty(trans, leaf);
5048
5049	ret = 0;
5050	end:
5051	btrfs_free_chunk_map(chunk_map);
5052	btrfs_release_path(path);
5053
5054	return ret;
5055	}
5056
5057	static int do_remap_reloc_trans(struct btrfs_fs_info *fs_info,
5058	struct btrfs_block_group *src_bg,
5059	struct btrfs_path path, u64 last_start)
5060	{
5061	struct btrfs_trans_handle *trans;
5062	struct btrfs_root *extent_root;
5063	struct btrfs_key ins;
5064	struct btrfs_block_group *dest_bg = NULL;
5065	u64 start = 0, remap_length = 0;
5066	u64 length, new_addr, min_size;
5067	int ret;
5068	const bool is_data = (src_bg->flags & BTRFS_BLOCK_GROUP_DATA);
5069	bool no_more = false;
5070	bool made_reservation = false, bg_needs_free_space;
5071	struct btrfs_space_info *sinfo = src_bg->space_info;
5072
5073	extent_root = btrfs_extent_root(fs_info, src_bg->start);
5074	if (unlikely(!extent_root)) {
5075	btrfs_err(fs_info,
5076	"missing extent root for block group at offset %llu",
5077	src_bg->start);
5078	return -EUCLEAN;
5079	}
5080
5081	trans = btrfs_start_transaction(extent_root, 0);
5082	if (IS_ERR(trans))
5083	return PTR_ERR(trans);
5084
5085	mutex_lock(&fs_info->remap_mutex);
5086
5087	ret = find_next_identity_remap(trans, path, src_bg->start + src_bg->length,
5088	*last_start, &start, &remap_length);
5089	if (ret == -ENOENT) {
5090	no_more = true;
5091	goto next;
5092	} else if (ret) {
5093	mutex_unlock(&fs_info->remap_mutex);
5094	btrfs_end_transaction(trans);
5095	return ret;
5096	}
5097
5098	/* Try to reserve enough space for block. */
5099	spin_lock(&sinfo->lock);
5100	btrfs_space_info_update_bytes_may_use(sinfo, remap_length);
5101	spin_unlock(&sinfo->lock);
5102
5103	if (is_data)
5104	min_size = fs_info->sectorsize;
5105	else
5106	min_size = fs_info->nodesize;
5107
5108	/*
5109	* We're using btrfs_reserve_extent() to allocate a contiguous
5110	* logical address range, but this will become a remap item rather than
5111	* an extent in the extent tree.
5112	*
5113	* Short allocations are fine: it means that we chop off the beginning
5114	* of the identity remap that we're processing, and will tackle the
5115	* rest of it the next time round.
5116	*/
5117	ret = btrfs_reserve_extent(fs_info->fs_root, remap_length, remap_length,
5118	min_size, 0, 0, &ins, is_data, false);
5119	if (ret) {
5120	spin_lock(&sinfo->lock);
5121	btrfs_space_info_update_bytes_may_use(sinfo, -remap_length);
5122	spin_unlock(&sinfo->lock);
5123
5124	mutex_unlock(&fs_info->remap_mutex);
5125	btrfs_end_transaction(trans);
5126	return ret;
5127	}
5128
5129	if (ins.offset < remap_length) {
5130	spin_lock(&sinfo->lock);
5131	btrfs_space_info_update_bytes_may_use(sinfo, ins.offset - remap_length);
5132	spin_unlock(&sinfo->lock);
5133	}
5134
5135	made_reservation = true;
5136
5137	new_addr = ins.objectid;
5138	length = ins.offset;
5139
5140	if (!is_data && !IS_ALIGNED(length, fs_info->nodesize)) {
5141	u64 new_length = ALIGN_DOWN(length, fs_info->nodesize);
5142
5143	btrfs_free_reserved_extent(fs_info, new_addr + new_length,
5144	length - new_length, 0);
5145
5146	length = new_length;
5147	}
5148
5149	dest_bg = btrfs_lookup_block_group(fs_info, new_addr);
5150
5151	mutex_lock(&dest_bg->free_space_lock);
5152	bg_needs_free_space = test_bit(BLOCK_GROUP_FLAG_NEEDS_FREE_SPACE,
5153	&dest_bg->runtime_flags);
5154	mutex_unlock(&dest_bg->free_space_lock);
5155
5156	if (bg_needs_free_space) {
5157	ret = btrfs_add_block_group_free_space(trans, dest_bg);
5158	if (ret) {
5159	btrfs_abort_transaction(trans, ret);
5160	goto fail;
5161	}
5162	}
5163
5164	ret = copy_remapped_data(fs_info, start, new_addr, length);
5165	if (ret) {
5166	btrfs_abort_transaction(trans, ret);
5167	goto fail;
5168	}
5169
5170	ret = btrfs_remove_from_free_space_tree(trans, new_addr, length);
5171	if (ret) {
5172	btrfs_abort_transaction(trans, ret);
5173	goto fail;
5174	}
5175
5176	ret = add_remap_entry(trans, path, src_bg, start, new_addr, length);
5177	if (ret) {
5178	btrfs_abort_transaction(trans, ret);
5179	goto fail;
5180	}
5181
5182	adjust_block_group_remap_bytes(trans, dest_bg, length);
5183	btrfs_free_reserved_bytes(dest_bg, length, 0);
5184
5185	spin_lock(&sinfo->lock);
5186	sinfo->bytes_readonly += length;
5187	spin_unlock(&sinfo->lock);
5188
5189	next:
5190	if (dest_bg)
5191	btrfs_put_block_group(dest_bg);
5192
5193	if (made_reservation)
5194	btrfs_dec_block_group_reservations(fs_info, new_addr);
5195
5196	mutex_unlock(&fs_info->remap_mutex);
5197
5198	if (src_bg->identity_remap_count == 0) {
5199	bool mark_fully_remapped = false;
5200
5201	spin_lock(&src_bg->lock);
5202	if (!test_bit(BLOCK_GROUP_FLAG_FULLY_REMAPPED, &src_bg->runtime_flags)) {
5203	mark_fully_remapped = true;
5204	set_bit(BLOCK_GROUP_FLAG_FULLY_REMAPPED, &src_bg->runtime_flags);
5205	}
5206	spin_unlock(&src_bg->lock);
5207
5208	if (mark_fully_remapped)
5209	btrfs_mark_bg_fully_remapped(src_bg, trans);
5210	}
5211
5212	ret = btrfs_end_transaction(trans);
5213	if (ret)
5214	return ret;
5215
5216	if (no_more)
5217	return 1;
5218
5219	*last_start = start;
5220
5221	return 0;
5222
5223	fail:
5224	if (dest_bg)
5225	btrfs_put_block_group(dest_bg);
5226
5227	btrfs_free_reserved_extent(fs_info, new_addr, length, 0);
5228
5229	mutex_unlock(&fs_info->remap_mutex);
5230	btrfs_end_transaction(trans);
5231
5232	return ret;
5233	}
5234
5235	static int do_remap_reloc(struct btrfs_fs_info fs_info, struct btrfs_path path,
5236	struct btrfs_block_group *bg)
5237	{
5238	u64 last_start = bg->start;
5239	int ret;
5240
5241	while (true) {
5242	ret = do_remap_reloc_trans(fs_info, bg, path, &last_start);
5243	if (ret) {
5244	if (ret == 1)
5245	ret = 0;
5246	break;
5247	}
5248	}
5249
5250	return ret;
5251	}
5252
5253	int btrfs_translate_remap(struct btrfs_fs_info fs_info, u64 logical, u64 *length)
5254	{
5255	int ret;
5256	struct btrfs_key key, found_key;
5257	struct extent_buffer *leaf;
5258	struct btrfs_remap_item *remap;
5259	BTRFS_PATH_AUTO_FREE(path);
5260
5261	path = btrfs_alloc_path();
5262	if (!path)
5263	return -ENOMEM;
5264
5265	key.objectid = *logical;
5266	key.type = (u8)-1;
5267	key.offset = (u64)-1;
5268
5269	ret = btrfs_search_slot(NULL, fs_info->remap_root, &key, path, 0, 0);
5270	if (ret < 0)
5271	return ret;
5272
5273	leaf = path->nodes[0];
5274	if (path->slots[0] == 0)
5275	return -ENOENT;
5276
5277	path->slots[0]--;
5278
5279	btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5280
5281	if (found_key.type != BTRFS_REMAP_KEY &&
5282	found_key.type != BTRFS_IDENTITY_REMAP_KEY) {
5283	return -ENOENT;
5284	}
5285
5286	if (found_key.objectid > *logical \|\|
5287	found_key.objectid + found_key.offset <= *logical) {
5288	return -ENOENT;
5289	}
5290
5291	if (logical + length > found_key.objectid + found_key.offset)
5292	length = found_key.objectid + found_key.offset - logical;
5293
5294	if (found_key.type == BTRFS_IDENTITY_REMAP_KEY)
5295	return 0;
5296
5297	remap = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_remap_item);
5298	*logical += btrfs_remap_address(leaf, remap) - found_key.objectid;
5299
5300	return 0;
5301	}
5302
5303	static int start_block_group_remapping(struct btrfs_fs_info *fs_info,
5304	struct btrfs_path *path,
5305	struct btrfs_block_group *bg)
5306	{
5307	struct btrfs_trans_handle *trans;
5308	bool bg_already_dirty = true;
5309	int ret, ret2;
5310
5311	ret = btrfs_cache_block_group(bg, true);
5312	if (ret)
5313	return ret;
5314
5315	trans = btrfs_start_transaction(fs_info->remap_root, 0);
5316	if (IS_ERR(trans))
5317	return PTR_ERR(trans);
5318
5319	/* We need to run delayed refs, to make sure FST is up to date. */
5320	ret = btrfs_run_delayed_refs(trans, U64_MAX);
5321	if (ret) {
5322	btrfs_end_transaction(trans);
5323	return ret;
5324	}
5325
5326	mutex_lock(&fs_info->remap_mutex);
5327
5328	if (bg->flags & BTRFS_BLOCK_GROUP_REMAPPED) {
5329	ret = 0;
5330	goto end;
5331	}
5332
5333	ret = create_remap_tree_entries(trans, path, bg);
5334	if (unlikely(ret)) {
5335	btrfs_abort_transaction(trans, ret);
5336	goto end;
5337	}
5338
5339	spin_lock(&bg->lock);
5340	bg->flags \|= BTRFS_BLOCK_GROUP_REMAPPED;
5341	spin_unlock(&bg->lock);
5342
5343	spin_lock(&trans->transaction->dirty_bgs_lock);
5344	if (list_empty(&bg->dirty_list)) {
5345	list_add_tail(&bg->dirty_list, &trans->transaction->dirty_bgs);
5346	bg_already_dirty = false;
5347	btrfs_get_block_group(bg);
5348	}
5349	spin_unlock(&trans->transaction->dirty_bgs_lock);
5350
5351	/* Modified block groups are accounted for in the delayed_refs_rsv. */
5352	if (!bg_already_dirty)
5353	btrfs_inc_delayed_refs_rsv_bg_updates(fs_info);
5354
5355	ret = mark_chunk_remapped(trans, path, bg->start);
5356	if (unlikely(ret)) {
5357	btrfs_abort_transaction(trans, ret);
5358	goto end;
5359	}
5360
5361	ret = btrfs_remove_block_group_free_space(trans, bg);
5362	if (unlikely(ret)) {
5363	btrfs_abort_transaction(trans, ret);
5364	goto end;
5365	}
5366
5367	btrfs_remove_free_space_cache(bg);
5368
5369	end:
5370	mutex_unlock(&fs_info->remap_mutex);
5371
5372	ret2 = btrfs_end_transaction(trans);
5373	if (!ret)
5374	ret = ret2;
5375
5376	return ret;
5377	}
5378
5379	static int do_nonremap_reloc(struct btrfs_fs_info *fs_info, bool verbose,
5380	struct reloc_control *rc)
5381	{
5382	int ret;
5383
5384	while (1) {
5385	enum reloc_stage finishes_stage;
5386
5387	mutex_lock(&fs_info->cleaner_mutex);
5388	ret = relocate_block_group(rc);
5389	mutex_unlock(&fs_info->cleaner_mutex);
5390
5391	finishes_stage = rc->stage;
5392	/*
5393	* We may have gotten ENOSPC after we already dirtied some
5394	* extents. If writeout happens while we're relocating a
5395	* different block group we could end up hitting the
5396	* BUG_ON(rc->stage == UPDATE_DATA_PTRS) in
5397	* btrfs_reloc_cow_block. Make sure we write everything out
5398	* properly so we don't trip over this problem, and then break
5399	* out of the loop if we hit an error.
5400	*/
5401	if (rc->stage == MOVE_DATA_EXTENTS && rc->found_file_extent) {
5402	int wb_ret;
5403
5404	wb_ret = btrfs_wait_ordered_range(BTRFS_I(rc->data_inode),
5405	0, (u64)-1);
5406	if (wb_ret && ret == 0)
5407	ret = wb_ret;
5408	invalidate_mapping_pages(rc->data_inode->i_mapping, 0, -1);
5409	rc->stage = UPDATE_DATA_PTRS;
5410	}
5411
5412	if (ret < 0)
5413	return ret;
5414
5415	if (rc->extents_found == 0)
5416	break;
5417
5418	if (verbose)
5419	btrfs_info(fs_info, "found %llu extents, stage: %s",
5420	rc->extents_found, stage_to_string(finishes_stage));
5421	}
5422
5423	WARN_ON(rc->block_group->pinned > 0);
5424	WARN_ON(rc->block_group->reserved > 0);
5425	WARN_ON(rc->block_group->used > 0);
5426
5427	return 0;
5428	}
5429
5430	/*
5431	* function to relocate all extents in a block group.
5432	*/
5433	int btrfs_relocate_block_group(struct btrfs_fs_info *fs_info, u64 group_start,
5434	bool verbose)
5435	{
5436	struct btrfs_block_group *bg;
5437	struct btrfs_root *extent_root = btrfs_extent_root(fs_info, group_start);
5438	struct reloc_control *rc;
5439	struct inode *inode;
5440	struct btrfs_path *path = NULL;
5441	int ret;
5442	bool bg_is_ro = false;
5443
5444	if (unlikely(!extent_root)) {
5445	btrfs_err(fs_info,
5446	"missing extent root for block group at offset %llu",
5447	group_start);
5448	return -EUCLEAN;
5449	}
5450
5451	/*
5452	* This only gets set if we had a half-deleted snapshot on mount. We
5453	* cannot allow relocation to start while we're still trying to clean up
5454	* these pending deletions.
5455	*/
5456	ret = wait_on_bit(&fs_info->flags, BTRFS_FS_UNFINISHED_DROPS, TASK_INTERRUPTIBLE);
5457	if (ret)
5458	return ret;
5459
5460	/* We may have been woken up by close_ctree, so bail if we're closing. */
5461	if (btrfs_fs_closing(fs_info))
5462	return -EINTR;
5463
5464	bg = btrfs_lookup_block_group(fs_info, group_start);
5465	if (!bg)
5466	return -ENOENT;
5467
5468	/*
5469	* Relocation of a data block group creates ordered extents. Without
5470	* sb_start_write(), we can freeze the filesystem while unfinished
5471	* ordered extents are left. Such ordered extents can cause a deadlock
5472	* e.g. when syncfs() is waiting for their completion but they can't
5473	* finish because they block when joining a transaction, due to the
5474	* fact that the freeze locks are being held in write mode.
5475	*/
5476	if (bg->flags & BTRFS_BLOCK_GROUP_DATA)
5477	ASSERT(sb_write_started(fs_info->sb));
5478
5479	if (btrfs_pinned_by_swapfile(fs_info, bg)) {
5480	btrfs_put_block_group(bg);
5481	return -ETXTBSY;
5482	}
5483
5484	rc = alloc_reloc_control(fs_info);
5485	if (!rc) {
5486	btrfs_put_block_group(bg);
5487	return -ENOMEM;
5488	}
5489
5490	rc->extent_root = extent_root;
5491	/* Block group ref now owned by rc, put_reloc_control() will drop it. */
5492	rc->block_group = bg;
5493
5494	ret = reloc_chunk_start(fs_info);
5495	if (ret < 0)
5496	goto out_put_rc;
5497
5498	ret = btrfs_inc_block_group_ro(rc->block_group, true);
5499	if (ret)
5500	goto out;
5501	bg_is_ro = true;
5502
5503	path = btrfs_alloc_path();
5504	if (!path) {
5505	ret = -ENOMEM;
5506	goto out;
5507	}
5508
5509	inode = lookup_free_space_inode(rc->block_group, path);
5510	btrfs_release_path(path);
5511
5512	if (!IS_ERR(inode))
5513	ret = delete_block_group_cache(rc->block_group, inode, 0);
5514	else
5515	ret = PTR_ERR(inode);
5516
5517	if (ret && ret != -ENOENT)
5518	goto out;
5519
5520	if (!btrfs_fs_incompat(fs_info, REMAP_TREE)) {
5521	rc->data_inode = create_reloc_inode(rc->block_group);
5522	if (IS_ERR(rc->data_inode)) {
5523	ret = PTR_ERR(rc->data_inode);
5524	rc->data_inode = NULL;
5525	goto out;
5526	}
5527	}
5528
5529	if (verbose)
5530	describe_relocation(rc->block_group);
5531
5532	btrfs_wait_block_group_reservations(rc->block_group);
5533	btrfs_wait_nocow_writers(rc->block_group);
5534	btrfs_wait_ordered_roots(fs_info, U64_MAX, rc->block_group);
5535
5536	ret = btrfs_zone_finish(rc->block_group);
5537	WARN_ON(ret && ret != -EAGAIN);
5538
5539	if (should_relocate_using_remap_tree(bg)) {
5540	if (bg->remap_bytes != 0) {
5541	ret = move_existing_remaps(fs_info, bg, path);
5542	if (ret)
5543	goto out;
5544	}
5545	ret = start_block_group_remapping(fs_info, path, bg);
5546	if (ret)
5547	goto out;
5548
5549	ret = do_remap_reloc(fs_info, path, rc->block_group);
5550	if (ret)
5551	goto out;
5552
5553	btrfs_delete_unused_bgs(fs_info);
5554	} else {
5555	ret = do_nonremap_reloc(fs_info, verbose, rc);
5556	}
5557
5558	out:
5559	if (ret && bg_is_ro)
5560	btrfs_dec_block_group_ro(rc->block_group);
5561	if (!btrfs_fs_incompat(fs_info, REMAP_TREE))
5562	iput(rc->data_inode);
5563	btrfs_free_path(path);
5564	reloc_chunk_end(fs_info);
5565	out_put_rc:
5566	put_reloc_control(rc);
5567	return ret;
5568	}
5569
5570	static noinline_for_stack int mark_garbage_root(struct btrfs_root *root)
5571	{
5572	struct btrfs_fs_info *fs_info = root->fs_info;
5573	struct btrfs_trans_handle *trans;
5574	int ret, err;
5575
5576	trans = btrfs_start_transaction(fs_info->tree_root, 0);
5577	if (IS_ERR(trans))
5578	return PTR_ERR(trans);
5579
5580	memset(&root->root_item.drop_progress, 0,
5581	sizeof(root->root_item.drop_progress));
5582	btrfs_set_root_drop_level(&root->root_item, 0);
5583	btrfs_set_root_refs(&root->root_item, 0);
5584	ret = btrfs_update_root(trans, fs_info->tree_root,
5585	&root->root_key, &root->root_item);
5586
5587	err = btrfs_end_transaction(trans);
5588	if (err)
5589	return err;
5590	return ret;
5591	}
5592
5593	static void release_recovered_fs_roots(struct list_head *roots, bool drop_reloc_refs)
5594	{
5595	struct btrfs_root *root;
5596	struct btrfs_root *next;
5597
5598	list_for_each_entry_safe(root, next, roots, reloc_dirty_list) {
5599	list_del_init(&root->reloc_dirty_list);
5600	if (drop_reloc_refs) {
5601	struct btrfs_root *reloc_root = root->reloc_root;
5602
5603	ASSERT(reloc_root);
5604	root->reloc_root = NULL;
5605	btrfs_put_root(reloc_root);
5606	}
5607	btrfs_put_root(root);
5608	}
5609	}
5610
5611	/*
5612	* recover relocation interrupted by system crash.
5613	*
5614	* this function resumes merging reloc trees with corresponding fs trees.
5615	* this is important for keeping the sharing of tree blocks
5616	*/
5617	int btrfs_recover_relocation(struct btrfs_fs_info *fs_info)
5618	{
5619	LIST_HEAD(reloc_roots);
5620	LIST_HEAD(recovered_roots);
5621	struct btrfs_key key;
5622	struct btrfs_root *fs_root;
5623	struct btrfs_root *reloc_root;
5624	struct btrfs_path *path;
5625	struct extent_buffer *leaf;
5626	struct reloc_control *rc = NULL;
5627	struct btrfs_trans_handle *trans;
5628	int ret2;
5629	int ret = 0;
5630
5631	path = btrfs_alloc_path();
5632	if (!path)
5633	return -ENOMEM;
5634	path->reada = READA_BACK;
5635
5636	key.objectid = BTRFS_TREE_RELOC_OBJECTID;
5637	key.type = BTRFS_ROOT_ITEM_KEY;
5638	key.offset = (u64)-1;
5639
5640	while (1) {
5641	ret = btrfs_search_slot(NULL, fs_info->tree_root, &key,
5642	path, 0, 0);
5643	if (ret < 0)
5644	goto out;
5645	if (ret > 0) {
5646	if (path->slots[0] == 0)
5647	break;
5648	path->slots[0]--;
5649	}
5650	ret = 0;
5651	leaf = path->nodes[0];
5652	btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
5653	btrfs_release_path(path);
5654
5655	if (key.objectid != BTRFS_TREE_RELOC_OBJECTID \|\|
5656	key.type != BTRFS_ROOT_ITEM_KEY)
5657	break;
5658
5659	reloc_root = btrfs_read_tree_root(fs_info->tree_root, &key);
5660	if (IS_ERR(reloc_root)) {
5661	ret = PTR_ERR(reloc_root);
5662	goto out;
5663	}
5664
5665	set_bit(BTRFS_ROOT_SHAREABLE, &reloc_root->state);
5666	list_add(&reloc_root->root_list, &reloc_roots);
5667
5668	if (btrfs_root_refs(&reloc_root->root_item) > 0) {
5669	fs_root = btrfs_get_fs_root(fs_info,
5670	reloc_root->root_key.offset, false);
5671	if (IS_ERR(fs_root)) {
5672	ret = PTR_ERR(fs_root);
5673	if (ret != -ENOENT)
5674	goto out;
5675	ret = mark_garbage_root(reloc_root);
5676	if (ret < 0)
5677	goto out;
5678	ret = 0;
5679	} else {
5680	btrfs_put_root(fs_root);
5681	}
5682	}
5683
5684	if (key.offset == 0)
5685	break;
5686
5687	key.offset--;
5688	}
5689	btrfs_release_path(path);
5690
5691	if (list_empty(&reloc_roots))
5692	goto out;
5693
5694	rc = alloc_reloc_control(fs_info);
5695	if (!rc) {
5696	ret = -ENOMEM;
5697	goto out;
5698	}
5699
5700	rc->extent_root = btrfs_extent_root(fs_info, 0);
5701	if (unlikely(!rc->extent_root)) {
5702	btrfs_err(fs_info, "missing extent root for extent at bytenr 0");
5703	ret = -EUCLEAN;
5704	goto out;
5705	}
5706
5707	ret = reloc_chunk_start(fs_info);
5708	if (ret < 0)
5709	goto out_end;
5710
5711	set_reloc_control(rc);
5712
5713	trans = btrfs_join_transaction(rc->extent_root);
5714	if (IS_ERR(trans)) {
5715	ret = PTR_ERR(trans);
5716	goto out_unset;
5717	}
5718
5719	rc->merge_reloc_tree = true;
5720
5721	while (!list_empty(&reloc_roots)) {
5722	reloc_root = list_first_entry(&reloc_roots, struct btrfs_root, root_list);
5723	list_del(&reloc_root->root_list);
5724
5725	if (btrfs_root_refs(&reloc_root->root_item) == 0) {
5726	list_add_tail(&reloc_root->root_list,
5727	&rc->reloc_roots);
5728	continue;
5729	}
5730
5731	fs_root = btrfs_get_fs_root(fs_info, reloc_root->root_key.offset,
5732	false);
5733	if (IS_ERR(fs_root)) {
5734	ret = PTR_ERR(fs_root);
5735	list_add_tail(&reloc_root->root_list, &reloc_roots);
5736	btrfs_end_transaction(trans);
5737	goto out_drop_reloc_refs;
5738	}
5739
5740	ret = __add_reloc_root(reloc_root, rc);
5741	ASSERT(ret != -EEXIST);
5742	if (ret) {
5743	list_add_tail(&reloc_root->root_list, &reloc_roots);
5744	btrfs_put_root(fs_root);
5745	btrfs_end_transaction(trans);
5746	goto out_drop_reloc_refs;
5747	}
5748	ASSERT(list_empty(&fs_root->reloc_dirty_list));
5749	fs_root->reloc_root = btrfs_grab_root(reloc_root);
5750	list_add_tail(&fs_root->reloc_dirty_list, &recovered_roots);
5751	}
5752
5753	ret = btrfs_commit_transaction(trans);
5754	if (ret)
5755	goto out_drop_reloc_refs;
5756	release_recovered_fs_roots(&recovered_roots, false);
5757
5758	ret = merge_reloc_roots(rc);
5759	if (ret)
5760	goto out_unset;
5761
5762	unset_reloc_control(rc);
5763
5764	trans = btrfs_join_transaction(rc->extent_root);
5765	if (IS_ERR(trans)) {
5766	ret = PTR_ERR(trans);
5767	goto out_clean;
5768	}
5769	ret = btrfs_commit_transaction(trans);
5770	out_clean:
5771	ret2 = clean_dirty_subvols(rc);
5772	if (ret2 < 0 && !ret)
5773	ret = ret2;
5774	out_drop_reloc_refs:
5775	release_recovered_fs_roots(&recovered_roots, true);
5776	out_unset:
5777	unset_reloc_control(rc);
5778	reloc_chunk_end(fs_info);
5779	out_end:
5780	put_reloc_control(rc);
5781	out:
5782	free_reloc_roots(&reloc_roots);
5783
5784	btrfs_free_path(path);
5785
5786	if (ret == 0 && !btrfs_fs_incompat(fs_info, REMAP_TREE)) {
5787	/* cleanup orphan inode in data relocation tree */
5788	fs_root = btrfs_grab_root(fs_info->data_reloc_root);
5789	ASSERT(fs_root);
5790	ret = btrfs_orphan_cleanup(fs_root);
5791	btrfs_put_root(fs_root);
5792	}
5793	return ret;
5794	}
5795
5796	/*
5797	* helper to add ordered checksum for data relocation.
5798	*
5799	* cloning checksum properly handles the nodatasum extents.
5800	* it also saves CPU time to re-calculate the checksum.
5801	*/
5802	int btrfs_reloc_clone_csums(struct btrfs_ordered_extent *ordered)
5803	{
5804	struct btrfs_inode *inode = ordered->inode;
5805	struct btrfs_fs_info *fs_info = inode->root->fs_info;
5806	u64 disk_bytenr = ordered->file_offset + inode->reloc_block_group_start;
5807	struct btrfs_root *csum_root = btrfs_csum_root(fs_info, disk_bytenr);
5808	LIST_HEAD(list);
5809	int ret;
5810
5811	if (unlikely(!csum_root)) {
5812	btrfs_mark_ordered_extent_error(ordered);
5813	btrfs_err(fs_info,
5814	"missing csum root for extent at bytenr %llu",
5815	disk_bytenr);
5816	return -EUCLEAN;
5817	}
5818
5819	ret = btrfs_lookup_csums_list(csum_root, disk_bytenr,
5820	disk_bytenr + ordered->num_bytes - 1,
5821	&list, false);
5822	if (ret < 0) {
5823	btrfs_mark_ordered_extent_error(ordered);
5824	return ret;
5825	}
5826
5827	while (!list_empty(&list)) {
5828	struct btrfs_ordered_sum *sums =
5829	list_first_entry(&list, struct btrfs_ordered_sum, list);
5830
5831	list_del_init(&sums->list);
5832
5833	/*
5834	* We need to offset the new_bytenr based on where the csum is.
5835	* We need to do this because we will read in entire prealloc
5836	* extents but we may have written to say the middle of the
5837	* prealloc extent, so we need to make sure the csum goes with
5838	* the right disk offset.
5839	*
5840	* We can do this because the data reloc inode refers strictly
5841	* to the on disk bytes, so we don't have to worry about
5842	* disk_len vs real len like with real inodes since it's all
5843	* disk length.
5844	*/
5845	sums->logical = ordered->disk_bytenr + sums->logical - disk_bytenr;
5846	btrfs_add_ordered_sum(ordered, sums);
5847	}
5848
5849	return 0;
5850	}
5851
5852	int btrfs_reloc_cow_block(struct btrfs_trans_handle *trans,
5853	struct btrfs_root *root,
5854	const struct extent_buffer *buf,
5855	struct extent_buffer *cow)
5856	{
5857	struct btrfs_fs_info *fs_info = root->fs_info;
5858	struct reloc_control *rc;
5859	struct btrfs_backref_node *node;
5860	bool first_cow = false;
5861	int level;
5862	int ret = 0;
5863
5864	rc = get_reloc_control(fs_info);
5865	if (!rc)
5866	return 0;
5867
5868	BUG_ON(rc->stage == UPDATE_DATA_PTRS && btrfs_is_data_reloc_root(root));
5869
5870	level = btrfs_header_level(buf);
5871	if (btrfs_header_generation(buf) <=
5872	btrfs_root_last_snapshot(&root->root_item))
5873	first_cow = true;
5874
5875	if (btrfs_root_id(root) == BTRFS_TREE_RELOC_OBJECTID && rc->create_reloc_tree) {
5876	WARN_ON(!first_cow && level == 0);
5877
5878	node = rc->backref_cache.path[level];
5879
5880	/*
5881	* If node->bytenr != buf->start and node->new_bytenr !=
5882	* buf->start then we've got the wrong backref node for what we
5883	* expected to see here and the cache is incorrect.
5884	*/
5885	if (unlikely(node->bytenr != buf->start && node->new_bytenr != buf->start)) {
5886	btrfs_err(fs_info,
5887	"bytenr %llu was found but our backref cache was expecting %llu or %llu",
5888	buf->start, node->bytenr, node->new_bytenr);
5889	ret = -EUCLEAN;
5890	goto out;
5891	}
5892
5893	btrfs_backref_drop_node_buffer(node);
5894	refcount_inc(&cow->refs);
5895	node->eb = cow;
5896	node->new_bytenr = cow->start;
5897
5898	if (!node->pending) {
5899	list_move_tail(&node->list,
5900	&rc->backref_cache.pending[level]);
5901	node->pending = 1;
5902	}
5903
5904	if (first_cow)
5905	mark_block_processed(rc, node);
5906
5907	if (first_cow && level > 0)
5908	rc->nodes_relocated += buf->len;
5909	}
5910
5911	if (level == 0 && first_cow && rc->stage == UPDATE_DATA_PTRS)
5912	ret = replace_file_extents(trans, rc, root, cow);
5913	out:
5914	put_reloc_control(rc);
5915
5916	return ret;
5917	}
5918
5919	/*
5920	* called before creating snapshot. it calculates metadata reservation
5921	* required for relocating tree blocks in the snapshot
5922	*/
5923	void btrfs_reloc_pre_snapshot(struct btrfs_pending_snapshot *pending,
5924	u64 *bytes_to_reserve)
5925	{
5926	struct btrfs_root *root = pending->root;
5927	struct reloc_control *rc = root->fs_info->reloc_ctl;
5928
5929	if (!rc \|\| !have_reloc_root(root))
5930	return;
5931
5932	if (!rc->merge_reloc_tree)
5933	return;
5934
5935	root = root->reloc_root;
5936	BUG_ON(btrfs_root_refs(&root->root_item) == 0);
5937	/*
5938	* relocation is in the stage of merging trees. the space
5939	* used by merging a reloc tree is twice the size of
5940	* relocated tree nodes in the worst case. half for cowing
5941	* the reloc tree, half for cowing the fs tree. the space
5942	* used by cowing the reloc tree will be freed after the
5943	* tree is dropped. if we create snapshot, cowing the fs
5944	* tree may use more space than it frees. so we need
5945	* reserve extra space.
5946	*/
5947	*bytes_to_reserve += rc->nodes_relocated;
5948	}
5949
5950	/*
5951	* called after snapshot is created. migrate block reservation
5952	* and create reloc root for the newly created snapshot
5953	*
5954	* This is similar to btrfs_init_reloc_root(), we come out of here with two
5955	* references held on the reloc_root, one for root->reloc_root and one for
5956	* rc->reloc_roots.
5957	*/
5958	int btrfs_reloc_post_snapshot(struct btrfs_trans_handle *trans,
5959	struct btrfs_pending_snapshot *pending)
5960	{
5961	struct btrfs_root *root = pending->root;
5962	struct btrfs_root *reloc_root;
5963	struct btrfs_root *new_root;
5964	struct reloc_control *rc;
5965	int ret = 0;
5966
5967	rc = get_reloc_control(trans->fs_info);
5968	if (!rc)
5969	return 0;
5970
5971	if (!have_reloc_root(root))
5972	goto out;
5973
5974	rc->merging_rsv_size += rc->nodes_relocated;
5975
5976	if (rc->merge_reloc_tree) {
5977	ret = btrfs_block_rsv_migrate(&pending->block_rsv,
5978	rc->block_rsv,
5979	rc->nodes_relocated, true);
5980	if (ret)
5981	goto out;
5982	}
5983
5984	new_root = pending->snap;
5985	reloc_root = create_reloc_root(trans, root->reloc_root, btrfs_root_id(new_root));
5986	if (IS_ERR(reloc_root)) {
5987	ret = PTR_ERR(reloc_root);
5988	goto out;
5989	}
5990
5991	ret = __add_reloc_root(reloc_root, rc);
5992	ASSERT(ret != -EEXIST);
5993	if (ret) {
5994	/* Pairs with create_reloc_root */
5995	btrfs_put_root(reloc_root);
5996	goto out;
5997	}
5998	new_root->reloc_root = btrfs_grab_root(reloc_root);
5999	out:
6000	put_reloc_control(rc);
6001
6002	return ret;
6003	}
6004
6005	/*
6006	* Get the current bytenr for the block group which is being relocated.
6007	*
6008	* Return U64_MAX if no running relocation.
6009	*/
6010	u64 btrfs_get_reloc_bg_bytenr(struct btrfs_fs_info *fs_info)
6011	{
6012	u64 logical = U64_MAX;
6013
6014	mutex_lock(&fs_info->reloc_mutex);
6015	if (fs_info->reloc_ctl && fs_info->reloc_ctl->block_group)
6016	logical = fs_info->reloc_ctl->block_group->start;
6017	mutex_unlock(&fs_info->reloc_mutex);
6018
6019	return logical;
6020	}
6021
6022	static int insert_remap_item(struct btrfs_trans_handle trans, struct btrfs_path path,
6023	u64 old_addr, u64 length, u64 new_addr)
6024	{
6025	int ret;
6026	struct btrfs_fs_info *fs_info = trans->fs_info;
6027	struct btrfs_key key;
6028	struct btrfs_remap_item remap = { 0 };
6029
6030	if (old_addr == new_addr) {
6031	/* Add new identity remap item. */
6032	key.objectid = old_addr;
6033	key.type = BTRFS_IDENTITY_REMAP_KEY;
6034	key.offset = length;
6035
6036	ret = btrfs_insert_empty_item(trans, fs_info->remap_root, path,
6037	&key, 0);
6038	if (ret)
6039	return ret;
6040	} else {
6041	/* Add new remap item. */
6042	key.objectid = old_addr;
6043	key.type = BTRFS_REMAP_KEY;
6044	key.offset = length;
6045
6046	ret = btrfs_insert_empty_item(trans, fs_info->remap_root,
6047	path, &key, sizeof(struct btrfs_remap_item));
6048	if (ret)
6049	return ret;
6050
6051	btrfs_set_stack_remap_address(&remap, new_addr);
6052
6053	write_extent_buffer(path->nodes[0], &remap,
6054	btrfs_item_ptr_offset(path->nodes[0], path->slots[0]),
6055	sizeof(struct btrfs_remap_item));
6056
6057	btrfs_release_path(path);
6058
6059	/* Add new backref item. */
6060	key.objectid = new_addr;
6061	key.type = BTRFS_REMAP_BACKREF_KEY;
6062	key.offset = length;
6063
6064	ret = btrfs_insert_empty_item(trans, fs_info->remap_root,
6065	path, &key,
6066	sizeof(struct btrfs_remap_item));
6067	if (ret)
6068	return ret;
6069
6070	btrfs_set_stack_remap_address(&remap, old_addr);
6071
6072	write_extent_buffer(path->nodes[0], &remap,
6073	btrfs_item_ptr_offset(path->nodes[0], path->slots[0]),
6074	sizeof(struct btrfs_remap_item));
6075	}
6076
6077	btrfs_release_path(path);
6078
6079	return 0;
6080	}
6081
6082	/*
6083	* Punch a hole in the remap item or identity remap item pointed to by path,
6084	* for the range [hole_start, hole_start + hole_length).
6085	*/
6086	static int remove_range_from_remap_tree(struct btrfs_trans_handle *trans,
6087	struct btrfs_path *path,
6088	struct btrfs_block_group *bg,
6089	u64 hole_start, u64 hole_length)
6090	{
6091	int ret;
6092	struct btrfs_fs_info *fs_info = trans->fs_info;
6093	struct extent_buffer *leaf = path->nodes[0];
6094	struct btrfs_key key;
6095	u64 hole_end, new_addr, remap_start, remap_length, remap_end;
6096	u64 overlap_length;
6097	bool is_identity_remap;
6098	int identity_count_delta = 0;
6099
6100	hole_end = hole_start + hole_length;
6101
6102	btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
6103
6104	is_identity_remap = (key.type == BTRFS_IDENTITY_REMAP_KEY);
6105
6106	remap_start = key.objectid;
6107	remap_length = key.offset;
6108	remap_end = remap_start + remap_length;
6109
6110	if (is_identity_remap) {
6111	new_addr = remap_start;
6112	} else {
6113	struct btrfs_remap_item *remap_ptr;
6114
6115	remap_ptr = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_remap_item);
6116	new_addr = btrfs_remap_address(leaf, remap_ptr);
6117	}
6118
6119	/* Delete old item. */
6120	ret = btrfs_del_item(trans, fs_info->remap_root, path);
6121	btrfs_release_path(path);
6122	if (ret)
6123	return ret;
6124
6125	if (is_identity_remap) {
6126	identity_count_delta = -1;
6127	} else {
6128	/* Remove backref. */
6129	key.objectid = new_addr;
6130	key.type = BTRFS_REMAP_BACKREF_KEY;
6131	key.offset = remap_length;
6132
6133	ret = btrfs_search_slot(trans, fs_info->remap_root, &key, path, -1, 1);
6134	if (ret) {
6135	if (ret == 1) {
6136	btrfs_release_path(path);
6137	ret = -ENOENT;
6138	}
6139	return ret;
6140	}
6141
6142	ret = btrfs_del_item(trans, fs_info->remap_root, path);
6143
6144	btrfs_release_path(path);
6145
6146	if (ret)
6147	return ret;
6148	}
6149
6150	/* If hole_start > remap_start, re-add the start of the remap item. */
6151	if (hole_start > remap_start) {
6152	ret = insert_remap_item(trans, path, remap_start,
6153	hole_start - remap_start, new_addr);
6154	if (ret)
6155	return ret;
6156
6157	if (is_identity_remap)
6158	identity_count_delta++;
6159	}
6160
6161	/* If hole_end < remap_end, re-add the end of the remap item. */
6162	if (hole_end < remap_end) {
6163	ret = insert_remap_item(trans, path, hole_end,
6164	remap_end - hole_end,
6165	hole_end - remap_start + new_addr);
6166	if (ret)
6167	return ret;
6168
6169	if (is_identity_remap)
6170	identity_count_delta++;
6171	}
6172
6173	if (identity_count_delta != 0)
6174	adjust_identity_remap_count(trans, bg, identity_count_delta);
6175
6176	overlap_length = min_t(u64, hole_end, remap_end) -
6177	max_t(u64, hole_start, remap_start);
6178
6179	if (!is_identity_remap) {
6180	struct btrfs_block_group *dest_bg;
6181
6182	dest_bg = btrfs_lookup_block_group(fs_info, new_addr);
6183	if (unlikely(!dest_bg))
6184	return -EUCLEAN;
6185
6186	adjust_block_group_remap_bytes(trans, dest_bg, -overlap_length);
6187	btrfs_put_block_group(dest_bg);
6188	ret = btrfs_add_to_free_space_tree(trans,
6189	hole_start - remap_start + new_addr,
6190	overlap_length);
6191	if (ret)
6192	return ret;
6193	}
6194
6195	ret = overlap_length;
6196
6197	return ret;
6198	}
6199
6200	/*
6201	* Return 1 if remove_range_from_remap_tree() has been called successfully,
6202	* 0 if block group wasn't remapped, and a negative number on error.
6203	*/
6204	int btrfs_remove_extent_from_remap_tree(struct btrfs_trans_handle *trans,
6205	struct btrfs_path *path,
6206	u64 bytenr, u64 num_bytes)
6207	{
6208	struct btrfs_fs_info *fs_info = trans->fs_info;
6209	struct btrfs_key key, found_key;
6210	struct extent_buffer *leaf;
6211	struct btrfs_block_group *bg;
6212	int ret, length;
6213
6214	if (!(btrfs_super_incompat_flags(fs_info->super_copy) &
6215	BTRFS_FEATURE_INCOMPAT_REMAP_TREE))
6216	return 0;
6217
6218	bg = btrfs_lookup_block_group(fs_info, bytenr);
6219	if (!bg)
6220	return 0;
6221
6222	mutex_lock(&fs_info->remap_mutex);
6223
6224	if (!(bg->flags & BTRFS_BLOCK_GROUP_REMAPPED)) {
6225	mutex_unlock(&fs_info->remap_mutex);
6226	btrfs_put_block_group(bg);
6227	return 0;
6228	}
6229
6230	do {
6231	key.objectid = bytenr;
6232	key.type = (u8)-1;
6233	key.offset = (u64)-1;
6234
6235	ret = btrfs_search_slot(trans, fs_info->remap_root, &key, path, -1, 1);
6236	if (ret < 0)
6237	goto end;
6238
6239	leaf = path->nodes[0];
6240	if (path->slots[0] == 0) {
6241	ret = -ENOENT;
6242	goto end;
6243	}
6244
6245	path->slots[0]--;
6246
6247	btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
6248
6249	if (found_key.type != BTRFS_IDENTITY_REMAP_KEY &&
6250	found_key.type != BTRFS_REMAP_KEY) {
6251	ret = -ENOENT;
6252	goto end;
6253	}
6254
6255	if (bytenr < found_key.objectid \|\|
6256	bytenr >= found_key.objectid + found_key.offset) {
6257	ret = -ENOENT;
6258	goto end;
6259	}
6260
6261	length = remove_range_from_remap_tree(trans, path, bg, bytenr, num_bytes);
6262	if (length < 0) {
6263	ret = length;
6264	goto end;
6265	}
6266
6267	bytenr += length;
6268	num_bytes -= length;
6269	} while (num_bytes > 0);
6270
6271	ret = 1;
6272
6273	end:
6274	mutex_unlock(&fs_info->remap_mutex);
6275
6276	btrfs_put_block_group(bg);
6277	btrfs_release_path(path);
6278
6279	return ret;
6280	}