fs/btrfs/relocation.c

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