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