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