fs/btrfs/relocation.c

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