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