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