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