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