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