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