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