fs/btrfs/extent-tree.c

   1 /*
   2  * Copyright (C) 2007 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 #include <linux/sched.h>
  19 #include <linux/pagemap.h>
  20 #include <linux/writeback.h>
  21 #include <linux/blkdev.h>
  22 #include "hash.h"
  23 #include "crc32c.h"
  24 #include "ctree.h"
  25 #include "disk-io.h"
  26 #include "print-tree.h"
  27 #include "transaction.h"
  28 #include "volumes.h"
  29 #include "locking.h"
  30 #include "ref-cache.h"
  31
  32 #define PENDING_EXTENT_INSERT 0
  33 #define PENDING_EXTENT_DELETE 1
  34 #define PENDING_BACKREF_UPDATE 2
  35
  36 struct pending_extent_op {
  37         int type;
  38         u64 bytenr;
  39         u64 num_bytes;
  40         u64 parent;
  41         u64 orig_parent;
  42         u64 generation;
  43         u64 orig_generation;
  44         int level;
  45 };
  46
  47 static int finish_current_insert(struct btrfs_trans_handle *trans, struct
  48                                  btrfs_root *extent_root);
  49 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
  50                                btrfs_root *extent_root);
  51 static struct btrfs_block_group_cache *
  52 __btrfs_find_block_group(struct btrfs_root *root,
  53                          struct btrfs_block_group_cache *hint,
  54                          u64 search_start, int data, int owner);
  55
  56 void maybe_lock_mutex(struct btrfs_root *root)
  57 {
  58         if (root != root->fs_info->extent_root &&
  59             root != root->fs_info->chunk_root &&
  60             root != root->fs_info->dev_root) {
  61                 mutex_lock(&root->fs_info->alloc_mutex);
  62         }
  63 }
  64
  65 void maybe_unlock_mutex(struct btrfs_root *root)
  66 {
  67         if (root != root->fs_info->extent_root &&
  68             root != root->fs_info->chunk_root &&
  69             root != root->fs_info->dev_root) {
  70                 mutex_unlock(&root->fs_info->alloc_mutex);
  71         }
  72 }
  73
  74 static int block_group_bits(struct btrfs_block_group_cache *cache, u64 bits)
  75 {
  76         return (cache->flags & bits) == bits;
  77 }
  78
  79 /*
  80  * this adds the block group to the fs_info rb tree for the block group
  81  * cache
  82  */
  83 int btrfs_add_block_group_cache(struct btrfs_fs_info *info,
  84                                 struct btrfs_block_group_cache *block_group)
  85 {
  86         struct rb_node **p;
  87         struct rb_node *parent = NULL;
  88         struct btrfs_block_group_cache *cache;
  89
  90         spin_lock(&info->block_group_cache_lock);
  91         p = &info->block_group_cache_tree.rb_node;
  92
  93         while (*p) {
  94                 parent = *p;
  95                 cache = rb_entry(parent, struct btrfs_block_group_cache,
  96                                  cache_node);
  97                 if (block_group->key.objectid < cache->key.objectid) {
  98                         p = &(*p)->rb_left;
  99                 } else if (block_group->key.objectid > cache->key.objectid) {
 100                         p = &(*p)->rb_right;
 101                 } else {
 102                         spin_unlock(&info->block_group_cache_lock);
 103                         return -EEXIST;
 104                 }
 105         }
 106
 107         rb_link_node(&block_group->cache_node, parent, p);
 108         rb_insert_color(&block_group->cache_node,
 109                         &info->block_group_cache_tree);
 110         spin_unlock(&info->block_group_cache_lock);
 111
 112         return 0;
 113 }
 114
 115 /*
 116  * This will return the block group at or after bytenr if contains is 0, else
 117  * it will return the block group that contains the bytenr
 118  */
 119 static struct btrfs_block_group_cache *
 120 block_group_cache_tree_search(struct btrfs_fs_info *info, u64 bytenr,
 121                               int contains)
 122 {
 123         struct btrfs_block_group_cache *cache, *ret = NULL;
 124         struct rb_node *n;
 125         u64 end, start;
 126
 127         spin_lock(&info->block_group_cache_lock);
 128         n = info->block_group_cache_tree.rb_node;
 129
 130         while (n) {
 131                 cache = rb_entry(n, struct btrfs_block_group_cache,
 132                                  cache_node);
 133                 end = cache->key.objectid + cache->key.offset - 1;
 134                 start = cache->key.objectid;
 135
 136                 if (bytenr < start) {
 137                         if (!contains && (!ret || start < ret->key.objectid))
 138                                 ret = cache;
 139                         n = n->rb_left;
 140                 } else if (bytenr > start) {
 141                         if (contains && bytenr <= end) {
 142                                 ret = cache;
 143                                 break;
 144                         }
 145                         n = n->rb_right;
 146                 } else {
 147                         ret = cache;
 148                         break;
 149                 }
 150         }
 151         spin_unlock(&info->block_group_cache_lock);
 152
 153         return ret;
 154 }
 155
 156 /*
 157  * this is only called by cache_block_group, since we could have freed extents
 158  * we need to check the pinned_extents for any extents that can't be used yet
 159  * since their free space will be released as soon as the transaction commits.
 160  */
 161 static int add_new_free_space(struct btrfs_block_group_cache *block_group,
 162                               struct btrfs_fs_info *info, u64 start, u64 end)
 163 {
 164         u64 extent_start, extent_end, size;
 165         int ret;
 166
 167         while (start < end) {
 168                 ret = find_first_extent_bit(&info->pinned_extents, start,
 169                                             &extent_start, &extent_end,
 170                                             EXTENT_DIRTY);
 171                 if (ret)
 172                         break;
 173
 174                 if (extent_start == start) {
 175                         start = extent_end + 1;
 176                 } else if (extent_start > start && extent_start < end) {
 177                         size = extent_start - start;
 178                         ret = btrfs_add_free_space(block_group, start, size);
 179                         BUG_ON(ret);
 180                         start = extent_end + 1;
 181                 } else {
 182                         break;
 183                 }
 184         }
 185
 186         if (start < end) {
 187                 size = end - start;
 188                 ret = btrfs_add_free_space(block_group, start, size);
 189                 BUG_ON(ret);
 190         }
 191
 192         return 0;
 193 }
 194
 195 static int cache_block_group(struct btrfs_root *root,
 196                              struct btrfs_block_group_cache *block_group)
 197 {
 198         struct btrfs_path *path;
 199         int ret = 0;
 200         struct btrfs_key key;
 201         struct extent_buffer *leaf;
 202         int slot;
 203         u64 last = 0;
 204         u64 first_free;
 205         int found = 0;
 206
 207         if (!block_group)
 208                 return 0;
 209
 210         root = root->fs_info->extent_root;
 211
 212         if (block_group->cached)
 213                 return 0;
 214
 215         path = btrfs_alloc_path();
 216         if (!path)
 217                 return -ENOMEM;
 218
 219         path->reada = 2;
 220         /*
 221          * we get into deadlocks with paths held by callers of this function.
 222          * since the alloc_mutex is protecting things right now, just
 223          * skip the locking here
 224          */
 225         path->skip_locking = 1;
 226         first_free = max_t(u64, block_group->key.objectid,
 227                            BTRFS_SUPER_INFO_OFFSET + BTRFS_SUPER_INFO_SIZE);
 228         key.objectid = block_group->key.objectid;
 229         key.offset = 0;
 230         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 231         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 232         if (ret < 0)
 233                 goto err;
 234         ret = btrfs_previous_item(root, path, 0, BTRFS_EXTENT_ITEM_KEY);
 235         if (ret < 0)
 236                 goto err;
 237         if (ret == 0) {
 238                 leaf = path->nodes[0];
 239                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 240                 if (key.objectid + key.offset > first_free)
 241                         first_free = key.objectid + key.offset;
 242         }
 243         while(1) {
 244                 leaf = path->nodes[0];
 245                 slot = path->slots[0];
 246                 if (slot >= btrfs_header_nritems(leaf)) {
 247                         ret = btrfs_next_leaf(root, path);
 248                         if (ret < 0)
 249                                 goto err;
 250                         if (ret == 0)
 251                                 continue;
 252                         else
 253                                 break;
 254                 }
 255                 btrfs_item_key_to_cpu(leaf, &key, slot);
 256                 if (key.objectid < block_group->key.objectid)
 257                         goto next;
 258
 259                 if (key.objectid >= block_group->key.objectid +
 260                     block_group->key.offset)
 261                         break;
 262
 263                 if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
 264                         if (!found) {
 265                                 last = first_free;
 266                                 found = 1;
 267                         }
 268
 269                         add_new_free_space(block_group, root->fs_info, last,
 270                                            key.objectid);
 271
 272                         last = key.objectid + key.offset;
 273                 }
 274 next:
 275                 path->slots[0]++;
 276         }
 277
 278         if (!found)
 279                 last = first_free;
 280
 281         add_new_free_space(block_group, root->fs_info, last,
 282                            block_group->key.objectid +
 283                            block_group->key.offset);
 284
 285         block_group->cached = 1;
 286         ret = 0;
 287 err:
 288         btrfs_free_path(path);
 289         return ret;
 290 }
 291
 292 /*
 293  * return the block group that starts at or after bytenr
 294  */
 295 struct btrfs_block_group_cache *btrfs_lookup_first_block_group(struct
 296                                                        btrfs_fs_info *info,
 297                                                          u64 bytenr)
 298 {
 299         struct btrfs_block_group_cache *cache;
 300
 301         cache = block_group_cache_tree_search(info, bytenr, 0);
 302
 303         return cache;
 304 }
 305
 306 /*
 307  * return the block group that contains teh given bytenr
 308  */
 309 struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
 310                                                          btrfs_fs_info *info,
 311                                                          u64 bytenr)
 312 {
 313         struct btrfs_block_group_cache *cache;
 314
 315         cache = block_group_cache_tree_search(info, bytenr, 1);
 316
 317         return cache;
 318 }
 319
 320 static int noinline find_free_space(struct btrfs_root *root,
 321                                     struct btrfs_block_group_cache **cache_ret,
 322                                     u64 *start_ret, u64 num, int data)
 323 {
 324         int ret;
 325         struct btrfs_block_group_cache *cache = *cache_ret;
 326         struct btrfs_free_space *info = NULL;
 327         u64 last;
 328         u64 search_start = *start_ret;
 329
 330         WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
 331         if (!cache)
 332                 goto out;
 333
 334         last = max(search_start, cache->key.objectid);
 335
 336 again:
 337         ret = cache_block_group(root, cache);
 338         if (ret)
 339                 goto out;
 340
 341         if (cache->ro || !block_group_bits(cache, data))
 342                 goto new_group;
 343
 344         info = btrfs_find_free_space(cache, last, num);
 345         if (info) {
 346                 *start_ret = info->offset;
 347                 return 0;
 348         }
 349
 350 new_group:
 351         last = cache->key.objectid + cache->key.offset;
 352
 353         cache = btrfs_lookup_first_block_group(root->fs_info, last);
 354         if (!cache)
 355                 goto out;
 356
 357         *cache_ret = cache;
 358         goto again;
 359
 360 out:
 361         return -ENOSPC;
 362 }
 363
 364 static u64 div_factor(u64 num, int factor)
 365 {
 366         if (factor == 10)
 367                 return num;
 368         num *= factor;
 369         do_div(num, 10);
 370         return num;
 371 }
 372
 373 static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
 374                                                   u64 flags)
 375 {
 376         struct list_head *head = &info->space_info;
 377         struct list_head *cur;
 378         struct btrfs_space_info *found;
 379         list_for_each(cur, head) {
 380                 found = list_entry(cur, struct btrfs_space_info, list);
 381                 if (found->flags == flags)
 382                         return found;
 383         }
 384         return NULL;
 385 }
 386
 387 static struct btrfs_block_group_cache *
 388 __btrfs_find_block_group(struct btrfs_root *root,
 389                          struct btrfs_block_group_cache *hint,
 390                          u64 search_start, int data, int owner)
 391 {
 392         struct btrfs_block_group_cache *cache;
 393         struct btrfs_block_group_cache *found_group = NULL;
 394         struct btrfs_fs_info *info = root->fs_info;
 395         u64 used;
 396         u64 last = 0;
 397         u64 free_check;
 398         int full_search = 0;
 399         int factor = 10;
 400         int wrapped = 0;
 401
 402         if (data & BTRFS_BLOCK_GROUP_METADATA)
 403                 factor = 9;
 404
 405         if (search_start) {
 406                 struct btrfs_block_group_cache *shint;
 407                 shint = btrfs_lookup_first_block_group(info, search_start);
 408                 if (shint && block_group_bits(shint, data) && !shint->ro) {
 409                         spin_lock(&shint->lock);
 410                         used = btrfs_block_group_used(&shint->item);
 411                         if (used + shint->pinned + shint->reserved <
 412                             div_factor(shint->key.offset, factor)) {
 413                                 spin_unlock(&shint->lock);
 414                                 return shint;
 415                         }
 416                         spin_unlock(&shint->lock);
 417                 }
 418         }
 419         if (hint && !hint->ro && block_group_bits(hint, data)) {
 420                 spin_lock(&hint->lock);
 421                 used = btrfs_block_group_used(&hint->item);
 422                 if (used + hint->pinned + hint->reserved <
 423                     div_factor(hint->key.offset, factor)) {
 424                         spin_unlock(&hint->lock);
 425                         return hint;
 426                 }
 427                 spin_unlock(&hint->lock);
 428                 last = hint->key.objectid + hint->key.offset;
 429         } else {
 430                 if (hint)
 431                         last = max(hint->key.objectid, search_start);
 432                 else
 433                         last = search_start;
 434         }
 435 again:
 436         while (1) {
 437                 cache = btrfs_lookup_first_block_group(root->fs_info, last);
 438                 if (!cache)
 439                         break;
 440
 441                 spin_lock(&cache->lock);
 442                 last = cache->key.objectid + cache->key.offset;
 443                 used = btrfs_block_group_used(&cache->item);
 444
 445                 if (!cache->ro && block_group_bits(cache, data)) {
 446                         free_check = div_factor(cache->key.offset, factor);
 447                         if (used + cache->pinned + cache->reserved <
 448                             free_check) {
 449                                 found_group = cache;
 450                                 spin_unlock(&cache->lock);
 451                                 goto found;
 452                         }
 453                 }
 454                 spin_unlock(&cache->lock);
 455                 cond_resched();
 456         }
 457         if (!wrapped) {
 458                 last = search_start;
 459                 wrapped = 1;
 460                 goto again;
 461         }
 462         if (!full_search && factor < 10) {
 463                 last = search_start;
 464                 full_search = 1;
 465                 factor = 10;
 466                 goto again;
 467         }
 468 found:
 469         return found_group;
 470 }
 471
 472 struct btrfs_block_group_cache *btrfs_find_block_group(struct btrfs_root *root,
 473                                                  struct btrfs_block_group_cache
 474                                                  *hint, u64 search_start,
 475                                                  int data, int owner)
 476 {
 477
 478         struct btrfs_block_group_cache *ret;
 479         ret = __btrfs_find_block_group(root, hint, search_start, data, owner);
 480         return ret;
 481 }
 482
 483 /* simple helper to search for an existing extent at a given offset */
 484 int btrfs_lookup_extent(struct btrfs_root *root, u64 start, u64 len)
 485 {
 486         int ret;
 487         struct btrfs_key key;
 488         struct btrfs_path *path;
 489
 490         path = btrfs_alloc_path();
 491         BUG_ON(!path);
 492         maybe_lock_mutex(root);
 493         key.objectid = start;
 494         key.offset = len;
 495         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 496         ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, path,
 497                                 0, 0);
 498         maybe_unlock_mutex(root);
 499         btrfs_free_path(path);
 500         return ret;
 501 }
 502
 503 /*
 504  * Back reference rules.  Back refs have three main goals:
 505  *
 506  * 1) differentiate between all holders of references to an extent so that
 507  *    when a reference is dropped we can make sure it was a valid reference
 508  *    before freeing the extent.
 509  *
 510  * 2) Provide enough information to quickly find the holders of an extent
 511  *    if we notice a given block is corrupted or bad.
 512  *
 513  * 3) Make it easy to migrate blocks for FS shrinking or storage pool
 514  *    maintenance.  This is actually the same as #2, but with a slightly
 515  *    different use case.
 516  *
 517  * File extents can be referenced by:
 518  *
 519  * - multiple snapshots, subvolumes, or different generations in one subvol
 520  * - different files inside a single subvolume
 521  * - different offsets inside a file (bookend extents in file.c)
 522  *
 523  * The extent ref structure has fields for:
 524  *
 525  * - Objectid of the subvolume root
 526  * - Generation number of the tree holding the reference
 527  * - objectid of the file holding the reference
 528  * - number of references holding by parent node (alway 1 for tree blocks)
 529  *
 530  * Btree leaf may hold multiple references to a file extent. In most cases,
 531  * these references are from same file and the corresponding offsets inside
 532  * the file are close together.
 533  *
 534  * When a file extent is allocated the fields are filled in:
 535  *     (root_key.objectid, trans->transid, inode objectid, 1)
 536  *
 537  * When a leaf is cow'd new references are added for every file extent found
 538  * in the leaf.  It looks similar to the create case, but trans->transid will
 539  * be different when the block is cow'd.
 540  *
 541  *     (root_key.objectid, trans->transid, inode objectid,
 542  *      number of references in the leaf)
 543  *
 544  * When a file extent is removed either during snapshot deletion or
 545  * file truncation, we find the corresponding back reference and check
 546  * the following fields:
 547  *
 548  *     (btrfs_header_owner(leaf), btrfs_header_generation(leaf),
 549  *      inode objectid)
 550  *
 551  * Btree extents can be referenced by:
 552  *
 553  * - Different subvolumes
 554  * - Different generations of the same subvolume
 555  *
 556  * When a tree block is created, back references are inserted:
 557  *
 558  * (root->root_key.objectid, trans->transid, level, 1)
 559  *
 560  * When a tree block is cow'd, new back references are added for all the
 561  * blocks it points to. If the tree block isn't in reference counted root,
 562  * the old back references are removed. These new back references are of
 563  * the form (trans->transid will have increased since creation):
 564  *
 565  * (root->root_key.objectid, trans->transid, level, 1)
 566  *
 567  * When a backref is in deleting, the following fields are checked:
 568  *
 569  * if backref was for a tree root:
 570  *     (btrfs_header_owner(itself), btrfs_header_generation(itself), level)
 571  * else
 572  *     (btrfs_header_owner(parent), btrfs_header_generation(parent), level)
 573  *
 574  * Back Reference Key composing:
 575  *
 576  * The key objectid corresponds to the first byte in the extent, the key
 577  * type is set to BTRFS_EXTENT_REF_KEY, and the key offset is the first
 578  * byte of parent extent. If a extent is tree root, the key offset is set
 579  * to the key objectid.
 580  */
 581
 582 static int noinline lookup_extent_backref(struct btrfs_trans_handle *trans,
 583                                           struct btrfs_root *root,
 584                                           struct btrfs_path *path,
 585                                           u64 bytenr, u64 parent,
 586                                           u64 ref_root, u64 ref_generation,
 587                                           u64 owner_objectid, int del)
 588 {
 589         struct btrfs_key key;
 590         struct btrfs_extent_ref *ref;
 591         struct extent_buffer *leaf;
 592         u64 ref_objectid;
 593         int ret;
 594
 595         key.objectid = bytenr;
 596         key.type = BTRFS_EXTENT_REF_KEY;
 597         key.offset = parent;
 598
 599         ret = btrfs_search_slot(trans, root, &key, path, del ? -1 : 0, 1);
 600         if (ret < 0)
 601                 goto out;
 602         if (ret > 0) {
 603                 ret = -ENOENT;
 604                 goto out;
 605         }
 606
 607         leaf = path->nodes[0];
 608         ref = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_ref);
 609         ref_objectid = btrfs_ref_objectid(leaf, ref);
 610         if (btrfs_ref_root(leaf, ref) != ref_root ||
 611             btrfs_ref_generation(leaf, ref) != ref_generation ||
 612             (ref_objectid != owner_objectid &&
 613              ref_objectid != BTRFS_MULTIPLE_OBJECTIDS)) {
 614                 ret = -EIO;
 615                 WARN_ON(1);
 616                 goto out;
 617         }
 618         ret = 0;
 619 out:
 620         return ret;
 621 }
 622
 623 static int noinline insert_extent_backref(struct btrfs_trans_handle *trans,
 624                                           struct btrfs_root *root,
 625                                           struct btrfs_path *path,
 626                                           u64 bytenr, u64 parent,
 627                                           u64 ref_root, u64 ref_generation,
 628                                           u64 owner_objectid)
 629 {
 630         struct btrfs_key key;
 631         struct extent_buffer *leaf;
 632         struct btrfs_extent_ref *ref;
 633         u32 num_refs;
 634         int ret;
 635
 636         key.objectid = bytenr;
 637         key.type = BTRFS_EXTENT_REF_KEY;
 638         key.offset = parent;
 639
 640         ret = btrfs_insert_empty_item(trans, root, path, &key, sizeof(*ref));
 641         if (ret == 0) {
 642                 leaf = path->nodes[0];
 643                 ref = btrfs_item_ptr(leaf, path->slots[0],
 644                                      struct btrfs_extent_ref);
 645                 btrfs_set_ref_root(leaf, ref, ref_root);
 646                 btrfs_set_ref_generation(leaf, ref, ref_generation);
 647                 btrfs_set_ref_objectid(leaf, ref, owner_objectid);
 648                 btrfs_set_ref_num_refs(leaf, ref, 1);
 649         } else if (ret == -EEXIST) {
 650                 u64 existing_owner;
 651                 BUG_ON(owner_objectid < BTRFS_FIRST_FREE_OBJECTID);
 652                 leaf = path->nodes[0];
 653                 ref = btrfs_item_ptr(leaf, path->slots[0],
 654                                      struct btrfs_extent_ref);
 655                 if (btrfs_ref_root(leaf, ref) != ref_root ||
 656                     btrfs_ref_generation(leaf, ref) != ref_generation) {
 657                         ret = -EIO;
 658                         WARN_ON(1);
 659                         goto out;
 660                 }
 661
 662                 num_refs = btrfs_ref_num_refs(leaf, ref);
 663                 BUG_ON(num_refs == 0);
 664                 btrfs_set_ref_num_refs(leaf, ref, num_refs + 1);
 665
 666                 existing_owner = btrfs_ref_objectid(leaf, ref);
 667                 if (existing_owner != owner_objectid &&
 668                     existing_owner != BTRFS_MULTIPLE_OBJECTIDS) {
 669                         btrfs_set_ref_objectid(leaf, ref,
 670                                         BTRFS_MULTIPLE_OBJECTIDS);
 671                 }
 672                 ret = 0;
 673         } else {
 674                 goto out;
 675         }
 676         btrfs_mark_buffer_dirty(path->nodes[0]);
 677 out:
 678         btrfs_release_path(root, path);
 679         return ret;
 680 }
 681
 682 static int noinline remove_extent_backref(struct btrfs_trans_handle *trans,
 683                                           struct btrfs_root *root,
 684                                           struct btrfs_path *path)
 685 {
 686         struct extent_buffer *leaf;
 687         struct btrfs_extent_ref *ref;
 688         u32 num_refs;
 689         int ret = 0;
 690
 691         leaf = path->nodes[0];
 692         ref = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_ref);
 693         num_refs = btrfs_ref_num_refs(leaf, ref);
 694         BUG_ON(num_refs == 0);
 695         num_refs -= 1;
 696         if (num_refs == 0) {
 697                 ret = btrfs_del_item(trans, root, path);
 698         } else {
 699                 btrfs_set_ref_num_refs(leaf, ref, num_refs);
 700                 btrfs_mark_buffer_dirty(leaf);
 701         }
 702         btrfs_release_path(root, path);
 703         return ret;
 704 }
 705
 706 static int __btrfs_update_extent_ref(struct btrfs_trans_handle *trans,
 707                                      struct btrfs_root *root, u64 bytenr,
 708                                      u64 orig_parent, u64 parent,
 709                                      u64 orig_root, u64 ref_root,
 710                                      u64 orig_generation, u64 ref_generation,
 711                                      u64 owner_objectid)
 712 {
 713         int ret;
 714         struct btrfs_root *extent_root = root->fs_info->extent_root;
 715         struct btrfs_path *path;
 716
 717         if (root == root->fs_info->extent_root) {
 718                 struct pending_extent_op *extent_op;
 719                 u64 num_bytes;
 720
 721                 BUG_ON(owner_objectid >= BTRFS_MAX_LEVEL);
 722                 num_bytes = btrfs_level_size(root, (int)owner_objectid);
 723                 if (test_range_bit(&root->fs_info->extent_ins, bytenr,
 724                                 bytenr + num_bytes - 1, EXTENT_LOCKED, 0)) {
 725                         u64 priv;
 726                         ret = get_state_private(&root->fs_info->extent_ins,
 727                                                 bytenr, &priv);
 728                         BUG_ON(ret);
 729                         extent_op = (struct pending_extent_op *)
 730                                                         (unsigned long)priv;
 731                         BUG_ON(extent_op->parent != orig_parent);
 732                         BUG_ON(extent_op->generation != orig_generation);
 733                         extent_op->parent = parent;
 734                         extent_op->generation = ref_generation;
 735                 } else {
 736                         extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
 737                         BUG_ON(!extent_op);
 738
 739                         extent_op->type = PENDING_BACKREF_UPDATE;
 740                         extent_op->bytenr = bytenr;
 741                         extent_op->num_bytes = num_bytes;
 742                         extent_op->parent = parent;
 743                         extent_op->orig_parent = orig_parent;
 744                         extent_op->generation = ref_generation;
 745                         extent_op->orig_generation = orig_generation;
 746                         extent_op->level = (int)owner_objectid;
 747
 748                         set_extent_bits(&root->fs_info->extent_ins,
 749                                         bytenr, bytenr + num_bytes - 1,
 750                                         EXTENT_LOCKED, GFP_NOFS);
 751                         set_state_private(&root->fs_info->extent_ins,
 752                                           bytenr, (unsigned long)extent_op);
 753                 }
 754                 return 0;
 755         }
 756
 757         path = btrfs_alloc_path();
 758         if (!path)
 759                 return -ENOMEM;
 760         ret = lookup_extent_backref(trans, extent_root, path,
 761                                     bytenr, orig_parent, orig_root,
 762                                     orig_generation, owner_objectid, 1);
 763         if (ret)
 764                 goto out;
 765         ret = remove_extent_backref(trans, extent_root, path);
 766         if (ret)
 767                 goto out;
 768         ret = insert_extent_backref(trans, extent_root, path, bytenr,
 769                                     parent, ref_root, ref_generation,
 770                                     owner_objectid);
 771         BUG_ON(ret);
 772         finish_current_insert(trans, extent_root);
 773         del_pending_extents(trans, extent_root);
 774 out:
 775         btrfs_free_path(path);
 776         return ret;
 777 }
 778
 779 int btrfs_update_extent_ref(struct btrfs_trans_handle *trans,
 780                             struct btrfs_root *root, u64 bytenr,
 781                             u64 orig_parent, u64 parent,
 782                             u64 ref_root, u64 ref_generation,
 783                             u64 owner_objectid)
 784 {
 785         int ret;
 786         if (ref_root == BTRFS_TREE_LOG_OBJECTID &&
 787             owner_objectid < BTRFS_FIRST_FREE_OBJECTID)
 788                 return 0;
 789         maybe_lock_mutex(root);
 790         ret = __btrfs_update_extent_ref(trans, root, bytenr, orig_parent,
 791                                         parent, ref_root, ref_root,
 792                                         ref_generation, ref_generation,
 793                                         owner_objectid);
 794         maybe_unlock_mutex(root);
 795         return ret;
 796 }
 797
 798 static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 799                                   struct btrfs_root *root, u64 bytenr,
 800                                   u64 orig_parent, u64 parent,
 801                                   u64 orig_root, u64 ref_root,
 802                                   u64 orig_generation, u64 ref_generation,
 803                                   u64 owner_objectid)
 804 {
 805         struct btrfs_path *path;
 806         int ret;
 807         struct btrfs_key key;
 808         struct extent_buffer *l;
 809         struct btrfs_extent_item *item;
 810         u32 refs;
 811
 812         path = btrfs_alloc_path();
 813         if (!path)
 814                 return -ENOMEM;
 815
 816         path->reada = 1;
 817         key.objectid = bytenr;
 818         key.type = BTRFS_EXTENT_ITEM_KEY;
 819         key.offset = (u64)-1;
 820
 821         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
 822                                 0, 1);
 823         if (ret < 0)
 824                 return ret;
 825         BUG_ON(ret == 0 || path->slots[0] == 0);
 826
 827         path->slots[0]--;
 828         l = path->nodes[0];
 829
 830         btrfs_item_key_to_cpu(l, &key, path->slots[0]);
 831         BUG_ON(key.objectid != bytenr);
 832         BUG_ON(key.type != BTRFS_EXTENT_ITEM_KEY);
 833
 834         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
 835         refs = btrfs_extent_refs(l, item);
 836         btrfs_set_extent_refs(l, item, refs + 1);
 837         btrfs_mark_buffer_dirty(path->nodes[0]);
 838
 839         btrfs_release_path(root->fs_info->extent_root, path);
 840
 841         path->reada = 1;
 842         ret = insert_extent_backref(trans, root->fs_info->extent_root,
 843                                     path, bytenr, parent,
 844                                     ref_root, ref_generation,
 845                                     owner_objectid);
 846         BUG_ON(ret);
 847         finish_current_insert(trans, root->fs_info->extent_root);
 848         del_pending_extents(trans, root->fs_info->extent_root);
 849
 850         btrfs_free_path(path);
 851         return 0;
 852 }
 853
 854 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 855                          struct btrfs_root *root,
 856                          u64 bytenr, u64 num_bytes, u64 parent,
 857                          u64 ref_root, u64 ref_generation,
 858                          u64 owner_objectid)
 859 {
 860         int ret;
 861         if (ref_root == BTRFS_TREE_LOG_OBJECTID &&
 862             owner_objectid < BTRFS_FIRST_FREE_OBJECTID)
 863                 return 0;
 864         maybe_lock_mutex(root);
 865         ret = __btrfs_inc_extent_ref(trans, root, bytenr, 0, parent,
 866                                      0, ref_root, 0, ref_generation,
 867                                      owner_objectid);
 868         maybe_unlock_mutex(root);
 869         return ret;
 870 }
 871
 872 int btrfs_extent_post_op(struct btrfs_trans_handle *trans,
 873                          struct btrfs_root *root)
 874 {
 875         finish_current_insert(trans, root->fs_info->extent_root);
 876         del_pending_extents(trans, root->fs_info->extent_root);
 877         return 0;
 878 }
 879
 880 int btrfs_lookup_extent_ref(struct btrfs_trans_handle *trans,
 881                             struct btrfs_root *root, u64 bytenr,
 882                             u64 num_bytes, u32 *refs)
 883 {
 884         struct btrfs_path *path;
 885         int ret;
 886         struct btrfs_key key;
 887         struct extent_buffer *l;
 888         struct btrfs_extent_item *item;
 889
 890         WARN_ON(num_bytes < root->sectorsize);
 891         path = btrfs_alloc_path();
 892         path->reada = 1;
 893         key.objectid = bytenr;
 894         key.offset = num_bytes;
 895         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 896         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key, path,
 897                                 0, 0);
 898         if (ret < 0)
 899                 goto out;
 900         if (ret != 0) {
 901                 btrfs_print_leaf(root, path->nodes[0]);
 902                 printk("failed to find block number %Lu\n", bytenr);
 903                 BUG();
 904         }
 905         l = path->nodes[0];
 906         item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
 907         *refs = btrfs_extent_refs(l, item);
 908 out:
 909         btrfs_free_path(path);
 910         return 0;
 911 }
 912
 913 static int get_reference_status(struct btrfs_root *root, u64 bytenr,
 914                                 u64 parent_gen, u64 ref_objectid,
 915                                 u64 *min_generation, u32 *ref_count)
 916 {
 917         struct btrfs_root *extent_root = root->fs_info->extent_root;
 918         struct btrfs_path *path;
 919         struct extent_buffer *leaf;
 920         struct btrfs_extent_ref *ref_item;
 921         struct btrfs_key key;
 922         struct btrfs_key found_key;
 923         u64 root_objectid = root->root_key.objectid;
 924         u64 ref_generation;
 925         u32 nritems;
 926         int ret;
 927
 928         key.objectid = bytenr;
 929         key.offset = (u64)-1;
 930         key.type = BTRFS_EXTENT_ITEM_KEY;
 931
 932         path = btrfs_alloc_path();
 933         mutex_lock(&root->fs_info->alloc_mutex);
 934         ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
 935         if (ret < 0)
 936                 goto out;
 937         BUG_ON(ret == 0);
 938         if (ret < 0 || path->slots[0] == 0)
 939                 goto out;
 940
 941         path->slots[0]--;
 942         leaf = path->nodes[0];
 943         btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
 944
 945         if (found_key.objectid != bytenr ||
 946             found_key.type != BTRFS_EXTENT_ITEM_KEY) {
 947                 ret = 1;
 948                 goto out;
 949         }
 950
 951         *ref_count = 0;
 952         *min_generation = (u64)-1;
 953
 954         while (1) {
 955                 leaf = path->nodes[0];
 956                 nritems = btrfs_header_nritems(leaf);
 957                 if (path->slots[0] >= nritems) {
 958                         ret = btrfs_next_leaf(extent_root, path);
 959                         if (ret < 0)
 960                                 goto out;
 961                         if (ret == 0)
 962                                 continue;
 963                         break;
 964                 }
 965                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
 966                 if (found_key.objectid != bytenr)
 967                         break;
 968
 969                 if (found_key.type != BTRFS_EXTENT_REF_KEY) {
 970                         path->slots[0]++;
 971                         continue;
 972                 }
 973
 974                 ref_item = btrfs_item_ptr(leaf, path->slots[0],
 975                                           struct btrfs_extent_ref);
 976                 ref_generation = btrfs_ref_generation(leaf, ref_item);
 977                 /*
 978                  * For (parent_gen > 0 && parent_gen > ref_generation):
 979                  *
 980                  * we reach here through the oldest root, therefore
 981                  * all other reference from same snapshot should have
 982                  * a larger generation.
 983                  */
 984                 if ((root_objectid != btrfs_ref_root(leaf, ref_item)) ||
 985                     (parent_gen > 0 && parent_gen > ref_generation) ||
 986                     (ref_objectid >= BTRFS_FIRST_FREE_OBJECTID &&
 987                      ref_objectid != btrfs_ref_objectid(leaf, ref_item))) {
 988                         *ref_count = 2;
 989                         break;
 990                 }
 991
 992                 *ref_count = 1;
 993                 if (*min_generation > ref_generation)
 994                         *min_generation = ref_generation;
 995
 996                 path->slots[0]++;
 997         }
 998         ret = 0;
 999 out:
1000         mutex_unlock(&root->fs_info->alloc_mutex);
1001         btrfs_free_path(path);
1002         return ret;
1003 }
1004
1005 int btrfs_cross_ref_exists(struct btrfs_trans_handle *trans,
1006                            struct btrfs_root *root,
1007                            struct btrfs_key *key, u64 bytenr)
1008 {
1009         struct btrfs_root *old_root;
1010         struct btrfs_path *path = NULL;
1011         struct extent_buffer *eb;
1012         struct btrfs_file_extent_item *item;
1013         u64 ref_generation;
1014         u64 min_generation;
1015         u64 extent_start;
1016         u32 ref_count;
1017         int level;
1018         int ret;
1019
1020         BUG_ON(trans == NULL);
1021         BUG_ON(key->type != BTRFS_EXTENT_DATA_KEY);
1022         ret = get_reference_status(root, bytenr, 0, key->objectid,
1023                                    &min_generation, &ref_count);
1024         if (ret)
1025                 return ret;
1026
1027         if (ref_count != 1)
1028                 return 1;
1029
1030         old_root = root->dirty_root->root;
1031         ref_generation = old_root->root_key.offset;
1032
1033         /* all references are created in running transaction */
1034         if (min_generation > ref_generation) {
1035                 ret = 0;
1036                 goto out;
1037         }
1038
1039         path = btrfs_alloc_path();
1040         if (!path) {
1041                 ret = -ENOMEM;
1042                 goto out;
1043         }
1044
1045         path->skip_locking = 1;
1046         /* if no item found, the extent is referenced by other snapshot */
1047         ret = btrfs_search_slot(NULL, old_root, key, path, 0, 0);
1048         if (ret)
1049                 goto out;
1050
1051         eb = path->nodes[0];
1052         item = btrfs_item_ptr(eb, path->slots[0],
1053                               struct btrfs_file_extent_item);
1054         if (btrfs_file_extent_type(eb, item) != BTRFS_FILE_EXTENT_REG ||
1055             btrfs_file_extent_disk_bytenr(eb, item) != bytenr) {
1056                 ret = 1;
1057                 goto out;
1058         }
1059
1060         for (level = BTRFS_MAX_LEVEL - 1; level >= -1; level--) {
1061                 if (level >= 0) {
1062                         eb = path->nodes[level];
1063                         if (!eb)
1064                                 continue;
1065                         extent_start = eb->start;
1066                 } else
1067                         extent_start = bytenr;
1068
1069                 ret = get_reference_status(root, extent_start, ref_generation,
1070                                            0, &min_generation, &ref_count);
1071                 if (ret)
1072                         goto out;
1073
1074                 if (ref_count != 1) {
1075                         ret = 1;
1076                         goto out;
1077                 }
1078                 if (level >= 0)
1079                         ref_generation = btrfs_header_generation(eb);
1080         }
1081         ret = 0;
1082 out:
1083         if (path)
1084                 btrfs_free_path(path);
1085         return ret;
1086 }
1087
1088 int btrfs_cache_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
1089                     struct extent_buffer *buf, u32 nr_extents)
1090 {
1091         struct btrfs_key key;
1092         struct btrfs_file_extent_item *fi;
1093         u64 root_gen;
1094         u32 nritems;
1095         int i;
1096         int level;
1097         int ret = 0;
1098         int shared = 0;
1099
1100         if (!root->ref_cows)
1101                 return 0;
1102
1103         if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
1104                 shared = 0;
1105                 root_gen = root->root_key.offset;
1106         } else {
1107                 shared = 1;
1108                 root_gen = trans->transid - 1;
1109         }
1110
1111         level = btrfs_header_level(buf);
1112         nritems = btrfs_header_nritems(buf);
1113
1114         if (level == 0) {
1115                 struct btrfs_leaf_ref *ref;
1116                 struct btrfs_extent_info *info;
1117
1118                 ref = btrfs_alloc_leaf_ref(root, nr_extents);
1119                 if (!ref) {
1120                         ret = -ENOMEM;
1121                         goto out;
1122                 }
1123
1124                 ref->root_gen = root_gen;
1125                 ref->bytenr = buf->start;
1126                 ref->owner = btrfs_header_owner(buf);
1127                 ref->generation = btrfs_header_generation(buf);
1128                 ref->nritems = nr_extents;
1129                 info = ref->extents;
1130
1131                 for (i = 0; nr_extents > 0 && i < nritems; i++) {
1132                         u64 disk_bytenr;
1133                         btrfs_item_key_to_cpu(buf, &key, i);
1134                         if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1135                                 continue;
1136                         fi = btrfs_item_ptr(buf, i,
1137                                             struct btrfs_file_extent_item);
1138                         if (btrfs_file_extent_type(buf, fi) ==
1139                             BTRFS_FILE_EXTENT_INLINE)
1140                                 continue;
1141                         disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
1142                         if (disk_bytenr == 0)
1143                                 continue;
1144
1145                         info->bytenr = disk_bytenr;
1146                         info->num_bytes =
1147                                 btrfs_file_extent_disk_num_bytes(buf, fi);
1148                         info->objectid = key.objectid;
1149                         info->offset = key.offset;
1150                         info++;
1151                 }
1152
1153                 ret = btrfs_add_leaf_ref(root, ref, shared);
1154                 if (ret == -EEXIST && shared) {
1155                         struct btrfs_leaf_ref *old;
1156                         old = btrfs_lookup_leaf_ref(root, ref->bytenr);
1157                         BUG_ON(!old);
1158                         btrfs_remove_leaf_ref(root, old);
1159                         btrfs_free_leaf_ref(root, old);
1160                         ret = btrfs_add_leaf_ref(root, ref, shared);
1161                 }
1162                 WARN_ON(ret);
1163                 btrfs_free_leaf_ref(root, ref);
1164         }
1165 out:
1166         return ret;
1167 }
1168
1169 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
1170                   struct extent_buffer *orig_buf, struct extent_buffer *buf,
1171                   u32 *nr_extents)
1172 {
1173         u64 bytenr;
1174         u64 ref_root;
1175         u64 orig_root;
1176         u64 ref_generation;
1177         u64 orig_generation;
1178         u32 nritems;
1179         u32 nr_file_extents = 0;
1180         struct btrfs_key key;
1181         struct btrfs_file_extent_item *fi;
1182         int i;
1183         int level;
1184         int ret = 0;
1185         int faili = 0;
1186         int (*process_func)(struct btrfs_trans_handle *, struct btrfs_root *,
1187                             u64, u64, u64, u64, u64, u64, u64, u64);
1188
1189         ref_root = btrfs_header_owner(buf);
1190         ref_generation = btrfs_header_generation(buf);
1191         orig_root = btrfs_header_owner(orig_buf);
1192         orig_generation = btrfs_header_generation(orig_buf);
1193
1194         nritems = btrfs_header_nritems(buf);
1195         level = btrfs_header_level(buf);
1196
1197         if (root->ref_cows) {
1198                 process_func = __btrfs_inc_extent_ref;
1199         } else {
1200                 if (level == 0 &&
1201                     root->root_key.objectid != BTRFS_TREE_LOG_OBJECTID)
1202                         goto out;
1203                 if (level != 0 &&
1204                     root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID)
1205                         goto out;
1206                 process_func = __btrfs_update_extent_ref;
1207         }
1208
1209         for (i = 0; i < nritems; i++) {
1210                 cond_resched();
1211                 if (level == 0) {
1212                         btrfs_item_key_to_cpu(buf, &key, i);
1213                         if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1214                                 continue;
1215                         fi = btrfs_item_ptr(buf, i,
1216                                             struct btrfs_file_extent_item);
1217                         if (btrfs_file_extent_type(buf, fi) ==
1218                             BTRFS_FILE_EXTENT_INLINE)
1219                                 continue;
1220                         bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
1221                         if (bytenr == 0)
1222                                 continue;
1223
1224                         nr_file_extents++;
1225
1226                         maybe_lock_mutex(root);
1227                         ret = process_func(trans, root, bytenr,
1228                                            orig_buf->start, buf->start,
1229                                            orig_root, ref_root,
1230                                            orig_generation, ref_generation,
1231                                            key.objectid);
1232                         maybe_unlock_mutex(root);
1233
1234                         if (ret) {
1235                                 faili = i;
1236                                 WARN_ON(1);
1237                                 goto fail;
1238                         }
1239                 } else {
1240                         bytenr = btrfs_node_blockptr(buf, i);
1241                         maybe_lock_mutex(root);
1242                         ret = process_func(trans, root, bytenr,
1243                                            orig_buf->start, buf->start,
1244                                            orig_root, ref_root,
1245                                            orig_generation, ref_generation,
1246                                            level - 1);
1247                         maybe_unlock_mutex(root);
1248                         if (ret) {
1249                                 faili = i;
1250                                 WARN_ON(1);
1251                                 goto fail;
1252                         }
1253                 }
1254         }
1255 out:
1256         if (nr_extents) {
1257                 if (level == 0)
1258                         *nr_extents = nr_file_extents;
1259                 else
1260                         *nr_extents = nritems;
1261         }
1262         return 0;
1263 fail:
1264         WARN_ON(1);
1265         return ret;
1266 }
1267
1268 int btrfs_update_ref(struct btrfs_trans_handle *trans,
1269                      struct btrfs_root *root, struct extent_buffer *orig_buf,
1270                      struct extent_buffer *buf, int start_slot, int nr)
1271
1272 {
1273         u64 bytenr;
1274         u64 ref_root;
1275         u64 orig_root;
1276         u64 ref_generation;
1277         u64 orig_generation;
1278         struct btrfs_key key;
1279         struct btrfs_file_extent_item *fi;
1280         int i;
1281         int ret;
1282         int slot;
1283         int level;
1284
1285         BUG_ON(start_slot < 0);
1286         BUG_ON(start_slot + nr > btrfs_header_nritems(buf));
1287
1288         ref_root = btrfs_header_owner(buf);
1289         ref_generation = btrfs_header_generation(buf);
1290         orig_root = btrfs_header_owner(orig_buf);
1291         orig_generation = btrfs_header_generation(orig_buf);
1292         level = btrfs_header_level(buf);
1293
1294         if (!root->ref_cows) {
1295                 if (level == 0 &&
1296                     root->root_key.objectid != BTRFS_TREE_LOG_OBJECTID)
1297                         return 0;
1298                 if (level != 0 &&
1299                     root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID)
1300                         return 0;
1301         }
1302
1303         for (i = 0, slot = start_slot; i < nr; i++, slot++) {
1304                 cond_resched();
1305                 if (level == 0) {
1306                         btrfs_item_key_to_cpu(buf, &key, slot);
1307                         if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
1308                                 continue;
1309                         fi = btrfs_item_ptr(buf, slot,
1310                                             struct btrfs_file_extent_item);
1311                         if (btrfs_file_extent_type(buf, fi) ==
1312                             BTRFS_FILE_EXTENT_INLINE)
1313                                 continue;
1314                         bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
1315                         if (bytenr == 0)
1316                                 continue;
1317                         maybe_lock_mutex(root);
1318                         ret = __btrfs_update_extent_ref(trans, root, bytenr,
1319                                             orig_buf->start, buf->start,
1320                                             orig_root, ref_root,
1321                                             orig_generation, ref_generation,
1322                                             key.objectid);
1323                         maybe_unlock_mutex(root);
1324                         if (ret)
1325                                 goto fail;
1326                 } else {
1327                         bytenr = btrfs_node_blockptr(buf, slot);
1328                         maybe_lock_mutex(root);
1329                         ret = __btrfs_update_extent_ref(trans, root, bytenr,
1330                                             orig_buf->start, buf->start,
1331                                             orig_root, ref_root,
1332                                             orig_generation, ref_generation,
1333                                             level - 1);
1334                         maybe_unlock_mutex(root);
1335                         if (ret)
1336                                 goto fail;
1337                 }
1338         }
1339         return 0;
1340 fail:
1341         WARN_ON(1);
1342         return -1;
1343 }
1344
1345 static int write_one_cache_group(struct btrfs_trans_handle *trans,
1346                                  struct btrfs_root *root,
1347                                  struct btrfs_path *path,
1348                                  struct btrfs_block_group_cache *cache)
1349 {
1350         int ret;
1351         int pending_ret;
1352         struct btrfs_root *extent_root = root->fs_info->extent_root;
1353         unsigned long bi;
1354         struct extent_buffer *leaf;
1355
1356         ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
1357         if (ret < 0)
1358                 goto fail;
1359         BUG_ON(ret);
1360
1361         leaf = path->nodes[0];
1362         bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
1363         write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
1364         btrfs_mark_buffer_dirty(leaf);
1365         btrfs_release_path(extent_root, path);
1366 fail:
1367         finish_current_insert(trans, extent_root);
1368         pending_ret = del_pending_extents(trans, extent_root);
1369         if (ret)
1370                 return ret;
1371         if (pending_ret)
1372                 return pending_ret;
1373         return 0;
1374
1375 }
1376
1377 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
1378                                    struct btrfs_root *root)
1379 {
1380         struct btrfs_block_group_cache *cache, *entry;
1381         struct rb_node *n;
1382         int err = 0;
1383         int werr = 0;
1384         struct btrfs_path *path;
1385         u64 last = 0;
1386
1387         path = btrfs_alloc_path();
1388         if (!path)
1389                 return -ENOMEM;
1390
1391         mutex_lock(&root->fs_info->alloc_mutex);
1392         while(1) {
1393                 cache = NULL;
1394                 spin_lock(&root->fs_info->block_group_cache_lock);
1395                 for (n = rb_first(&root->fs_info->block_group_cache_tree);
1396                      n; n = rb_next(n)) {
1397                         entry = rb_entry(n, struct btrfs_block_group_cache,
1398                                          cache_node);
1399                         if (entry->dirty) {
1400                                 cache = entry;
1401                                 break;
1402                         }
1403                 }
1404                 spin_unlock(&root->fs_info->block_group_cache_lock);
1405
1406                 if (!cache)
1407                         break;
1408
1409                 cache->dirty = 0;
1410                 last += cache->key.offset;
1411
1412                 err = write_one_cache_group(trans, root,
1413                                             path, cache);
1414                 /*
1415                  * if we fail to write the cache group, we want
1416                  * to keep it marked dirty in hopes that a later
1417                  * write will work
1418                  */
1419                 if (err) {
1420                         werr = err;
1421                         continue;
1422                 }
1423         }
1424         btrfs_free_path(path);
1425         mutex_unlock(&root->fs_info->alloc_mutex);
1426         return werr;
1427 }
1428
1429 static int update_space_info(struct btrfs_fs_info *info, u64 flags,
1430                              u64 total_bytes, u64 bytes_used,
1431                              struct btrfs_space_info **space_info)
1432 {
1433         struct btrfs_space_info *found;
1434
1435         found = __find_space_info(info, flags);
1436         if (found) {
1437                 found->total_bytes += total_bytes;
1438                 found->bytes_used += bytes_used;
1439                 found->full = 0;
1440                 *space_info = found;
1441                 return 0;
1442         }
1443         found = kmalloc(sizeof(*found), GFP_NOFS);
1444         if (!found)
1445                 return -ENOMEM;
1446
1447         list_add(&found->list, &info->space_info);
1448         INIT_LIST_HEAD(&found->block_groups);
1449         spin_lock_init(&found->lock);
1450         found->flags = flags;
1451         found->total_bytes = total_bytes;
1452         found->bytes_used = bytes_used;
1453         found->bytes_pinned = 0;
1454         found->bytes_reserved = 0;
1455         found->full = 0;
1456         found->force_alloc = 0;
1457         *space_info = found;
1458         return 0;
1459 }
1460
1461 static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
1462 {
1463         u64 extra_flags = flags & (BTRFS_BLOCK_GROUP_RAID0 |
1464                                    BTRFS_BLOCK_GROUP_RAID1 |
1465                                    BTRFS_BLOCK_GROUP_RAID10 |
1466                                    BTRFS_BLOCK_GROUP_DUP);
1467         if (extra_flags) {
1468                 if (flags & BTRFS_BLOCK_GROUP_DATA)
1469                         fs_info->avail_data_alloc_bits |= extra_flags;
1470                 if (flags & BTRFS_BLOCK_GROUP_METADATA)
1471                         fs_info->avail_metadata_alloc_bits |= extra_flags;
1472                 if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
1473                         fs_info->avail_system_alloc_bits |= extra_flags;
1474         }
1475 }
1476
1477 static u64 reduce_alloc_profile(struct btrfs_root *root, u64 flags)
1478 {
1479         u64 num_devices = root->fs_info->fs_devices->num_devices;
1480
1481         if (num_devices == 1)
1482                 flags &= ~(BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_RAID0);
1483         if (num_devices < 4)
1484                 flags &= ~BTRFS_BLOCK_GROUP_RAID10;
1485
1486         if ((flags & BTRFS_BLOCK_GROUP_DUP) &&
1487             (flags & (BTRFS_BLOCK_GROUP_RAID1 |
1488                       BTRFS_BLOCK_GROUP_RAID10))) {
1489                 flags &= ~BTRFS_BLOCK_GROUP_DUP;
1490         }
1491
1492         if ((flags & BTRFS_BLOCK_GROUP_RAID1) &&
1493             (flags & BTRFS_BLOCK_GROUP_RAID10)) {
1494                 flags &= ~BTRFS_BLOCK_GROUP_RAID1;
1495         }
1496
1497         if ((flags & BTRFS_BLOCK_GROUP_RAID0) &&
1498             ((flags & BTRFS_BLOCK_GROUP_RAID1) |
1499              (flags & BTRFS_BLOCK_GROUP_RAID10) |
1500              (flags & BTRFS_BLOCK_GROUP_DUP)))
1501                 flags &= ~BTRFS_BLOCK_GROUP_RAID0;
1502         return flags;
1503 }
1504
1505 static int do_chunk_alloc(struct btrfs_trans_handle *trans,
1506                           struct btrfs_root *extent_root, u64 alloc_bytes,
1507                           u64 flags, int force)
1508 {
1509         struct btrfs_space_info *space_info;
1510         u64 thresh;
1511         u64 start;
1512         u64 num_bytes;
1513         int ret = 0, waited = 0;
1514
1515         flags = reduce_alloc_profile(extent_root, flags);
1516
1517         space_info = __find_space_info(extent_root->fs_info, flags);
1518         if (!space_info) {
1519                 ret = update_space_info(extent_root->fs_info, flags,
1520                                         0, 0, &space_info);
1521                 BUG_ON(ret);
1522         }
1523         BUG_ON(!space_info);
1524
1525         if (space_info->force_alloc) {
1526                 force = 1;
1527                 space_info->force_alloc = 0;
1528         }
1529         if (space_info->full)
1530                 goto out;
1531
1532         thresh = div_factor(space_info->total_bytes, 6);
1533         if (!force &&
1534            (space_info->bytes_used + space_info->bytes_pinned +
1535             space_info->bytes_reserved + alloc_bytes) < thresh)
1536                 goto out;
1537
1538         while (!mutex_trylock(&extent_root->fs_info->chunk_mutex)) {
1539                 if (!force)
1540                         goto out;
1541                 mutex_unlock(&extent_root->fs_info->alloc_mutex);
1542                 cond_resched();
1543                 mutex_lock(&extent_root->fs_info->alloc_mutex);
1544                 waited = 1;
1545         }
1546
1547         if (waited && space_info->full)
1548                 goto out_unlock;
1549
1550         ret = btrfs_alloc_chunk(trans, extent_root, &start, &num_bytes, flags);
1551         if (ret == -ENOSPC) {
1552 printk("space info full %Lu\n", flags);
1553                 space_info->full = 1;
1554                 goto out_unlock;
1555         }
1556         BUG_ON(ret);
1557
1558         ret = btrfs_make_block_group(trans, extent_root, 0, flags,
1559                      BTRFS_FIRST_CHUNK_TREE_OBJECTID, start, num_bytes);
1560         BUG_ON(ret);
1561
1562 out_unlock:
1563         mutex_unlock(&extent_root->fs_info->chunk_mutex);
1564 out:
1565         return ret;
1566 }
1567
1568 static int update_block_group(struct btrfs_trans_handle *trans,
1569                               struct btrfs_root *root,
1570                               u64 bytenr, u64 num_bytes, int alloc,
1571                               int mark_free)
1572 {
1573         struct btrfs_block_group_cache *cache;
1574         struct btrfs_fs_info *info = root->fs_info;
1575         u64 total = num_bytes;
1576         u64 old_val;
1577         u64 byte_in_group;
1578
1579         WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
1580         while(total) {
1581                 cache = btrfs_lookup_block_group(info, bytenr);
1582                 if (!cache) {
1583                         return -1;
1584                 }
1585                 byte_in_group = bytenr - cache->key.objectid;
1586                 WARN_ON(byte_in_group > cache->key.offset);
1587
1588                 spin_lock(&cache->lock);
1589                 cache->dirty = 1;
1590                 old_val = btrfs_block_group_used(&cache->item);
1591                 num_bytes = min(total, cache->key.offset - byte_in_group);
1592                 if (alloc) {
1593                         old_val += num_bytes;
1594                         cache->space_info->bytes_used += num_bytes;
1595                         btrfs_set_block_group_used(&cache->item, old_val);
1596                         spin_unlock(&cache->lock);
1597                 } else {
1598                         old_val -= num_bytes;
1599                         cache->space_info->bytes_used -= num_bytes;
1600                         btrfs_set_block_group_used(&cache->item, old_val);
1601                         spin_unlock(&cache->lock);
1602                         if (mark_free) {
1603                                 int ret;
1604                                 ret = btrfs_add_free_space(cache, bytenr,
1605                                                            num_bytes);
1606                                 if (ret)
1607                                         return -1;
1608                         }
1609                 }
1610                 total -= num_bytes;
1611                 bytenr += num_bytes;
1612         }
1613         return 0;
1614 }
1615
1616 static u64 first_logical_byte(struct btrfs_root *root, u64 search_start)
1617 {
1618         struct btrfs_block_group_cache *cache;
1619
1620         cache = btrfs_lookup_first_block_group(root->fs_info, search_start);
1621         if (!cache)
1622                 return 0;
1623
1624         return cache->key.objectid;
1625 }
1626
1627 int btrfs_update_pinned_extents(struct btrfs_root *root,
1628                                 u64 bytenr, u64 num, int pin)
1629 {
1630         u64 len;
1631         struct btrfs_block_group_cache *cache;
1632         struct btrfs_fs_info *fs_info = root->fs_info;
1633
1634         WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
1635         if (pin) {
1636                 set_extent_dirty(&fs_info->pinned_extents,
1637                                 bytenr, bytenr + num - 1, GFP_NOFS);
1638         } else {
1639                 clear_extent_dirty(&fs_info->pinned_extents,
1640                                 bytenr, bytenr + num - 1, GFP_NOFS);
1641         }
1642         while (num > 0) {
1643                 cache = btrfs_lookup_block_group(fs_info, bytenr);
1644                 BUG_ON(!cache);
1645                 len = min(num, cache->key.offset -
1646                           (bytenr - cache->key.objectid));
1647                 if (pin) {
1648                         spin_lock(&cache->lock);
1649                         cache->pinned += len;
1650                         cache->space_info->bytes_pinned += len;
1651                         spin_unlock(&cache->lock);
1652                         fs_info->total_pinned += len;
1653                 } else {
1654                         spin_lock(&cache->lock);
1655                         cache->pinned -= len;
1656                         cache->space_info->bytes_pinned -= len;
1657                         spin_unlock(&cache->lock);
1658                         fs_info->total_pinned -= len;
1659                 }
1660                 bytenr += len;
1661                 num -= len;
1662         }
1663         return 0;
1664 }
1665
1666 static int update_reserved_extents(struct btrfs_root *root,
1667                                    u64 bytenr, u64 num, int reserve)
1668 {
1669         u64 len;
1670         struct btrfs_block_group_cache *cache;
1671         struct btrfs_fs_info *fs_info = root->fs_info;
1672
1673         WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
1674         while (num > 0) {
1675                 cache = btrfs_lookup_block_group(fs_info, bytenr);
1676                 BUG_ON(!cache);
1677                 len = min(num, cache->key.offset -
1678                           (bytenr - cache->key.objectid));
1679                 if (reserve) {
1680                         spin_lock(&cache->lock);
1681                         cache->reserved += len;
1682                         cache->space_info->bytes_reserved += len;
1683                         spin_unlock(&cache->lock);
1684                 } else {
1685                         spin_lock(&cache->lock);
1686                         cache->reserved -= len;
1687                         cache->space_info->bytes_reserved -= len;
1688                         spin_unlock(&cache->lock);
1689                 }
1690                 bytenr += len;
1691                 num -= len;
1692         }
1693         return 0;
1694 }
1695
1696 int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy)
1697 {
1698         u64 last = 0;
1699         u64 start;
1700         u64 end;
1701         struct extent_io_tree *pinned_extents = &root->fs_info->pinned_extents;
1702         int ret;
1703
1704         while(1) {
1705                 ret = find_first_extent_bit(pinned_extents, last,
1706                                             &start, &end, EXTENT_DIRTY);
1707                 if (ret)
1708                         break;
1709                 set_extent_dirty(copy, start, end, GFP_NOFS);
1710                 last = end + 1;
1711         }
1712         return 0;
1713 }
1714
1715 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
1716                                struct btrfs_root *root,
1717                                struct extent_io_tree *unpin)
1718 {
1719         u64 start;
1720         u64 end;
1721         int ret;
1722         struct btrfs_block_group_cache *cache;
1723
1724         mutex_lock(&root->fs_info->alloc_mutex);
1725         while(1) {
1726                 ret = find_first_extent_bit(unpin, 0, &start, &end,
1727                                             EXTENT_DIRTY);
1728                 if (ret)
1729                         break;
1730                 btrfs_update_pinned_extents(root, start, end + 1 - start, 0);
1731                 clear_extent_dirty(unpin, start, end, GFP_NOFS);
1732                 cache = btrfs_lookup_block_group(root->fs_info, start);
1733                 if (cache->cached)
1734                         btrfs_add_free_space(cache, start, end - start + 1);
1735                 if (need_resched()) {
1736                         mutex_unlock(&root->fs_info->alloc_mutex);
1737                         cond_resched();
1738                         mutex_lock(&root->fs_info->alloc_mutex);
1739                 }
1740         }
1741         mutex_unlock(&root->fs_info->alloc_mutex);
1742         return 0;
1743 }
1744
1745 static int finish_current_insert(struct btrfs_trans_handle *trans,
1746                                  struct btrfs_root *extent_root)
1747 {
1748         u64 start;
1749         u64 end;
1750         u64 priv;
1751         struct btrfs_fs_info *info = extent_root->fs_info;
1752         struct btrfs_path *path;
1753         struct btrfs_extent_ref *ref;
1754         struct pending_extent_op *extent_op;
1755         struct btrfs_key key;
1756         struct btrfs_extent_item extent_item;
1757         int ret;
1758         int err = 0;
1759
1760         WARN_ON(!mutex_is_locked(&extent_root->fs_info->alloc_mutex));
1761         btrfs_set_stack_extent_refs(&extent_item, 1);
1762         path = btrfs_alloc_path();
1763
1764         while(1) {
1765                 ret = find_first_extent_bit(&info->extent_ins, 0, &start,
1766                                             &end, EXTENT_LOCKED);
1767                 if (ret)
1768                         break;
1769
1770                 ret = get_state_private(&info->extent_ins, start, &priv);
1771                 BUG_ON(ret);
1772                 extent_op = (struct pending_extent_op *)(unsigned long)priv;
1773
1774                 if (extent_op->type == PENDING_EXTENT_INSERT) {
1775                         key.objectid = start;
1776                         key.offset = end + 1 - start;
1777                         key.type = BTRFS_EXTENT_ITEM_KEY;
1778                         err = btrfs_insert_item(trans, extent_root, &key,
1779                                         &extent_item, sizeof(extent_item));
1780                         BUG_ON(err);
1781
1782                         clear_extent_bits(&info->extent_ins, start, end,
1783                                           EXTENT_LOCKED, GFP_NOFS);
1784
1785                         err = insert_extent_backref(trans, extent_root, path,
1786                                                 start, extent_op->parent,
1787                                                 extent_root->root_key.objectid,
1788                                                 extent_op->generation,
1789                                                 extent_op->level);
1790                         BUG_ON(err);
1791                 } else if (extent_op->type == PENDING_BACKREF_UPDATE) {
1792                         err = lookup_extent_backref(trans, extent_root, path,
1793                                                 start, extent_op->orig_parent,
1794                                                 extent_root->root_key.objectid,
1795                                                 extent_op->orig_generation,
1796                                                 extent_op->level, 0);
1797                         BUG_ON(err);
1798
1799                         clear_extent_bits(&info->extent_ins, start, end,
1800                                           EXTENT_LOCKED, GFP_NOFS);
1801
1802                         key.objectid = start;
1803                         key.offset = extent_op->parent;
1804                         key.type = BTRFS_EXTENT_REF_KEY;
1805                         err = btrfs_set_item_key_safe(trans, extent_root, path,
1806                                                       &key);
1807                         BUG_ON(err);
1808                         ref = btrfs_item_ptr(path->nodes[0], path->slots[0],
1809                                              struct btrfs_extent_ref);
1810                         btrfs_set_ref_generation(path->nodes[0], ref,
1811                                                  extent_op->generation);
1812                         btrfs_mark_buffer_dirty(path->nodes[0]);
1813                         btrfs_release_path(extent_root, path);
1814                 } else {
1815                         BUG_ON(1);
1816                 }
1817                 kfree(extent_op);
1818
1819                 if (need_resched()) {
1820                         mutex_unlock(&extent_root->fs_info->alloc_mutex);
1821                         cond_resched();
1822                         mutex_lock(&extent_root->fs_info->alloc_mutex);
1823                 }
1824         }
1825         btrfs_free_path(path);
1826         return 0;
1827 }
1828
1829 static int pin_down_bytes(struct btrfs_trans_handle *trans,
1830                           struct btrfs_root *root,
1831                           u64 bytenr, u64 num_bytes, int is_data)
1832 {
1833         int err = 0;
1834         struct extent_buffer *buf;
1835
1836         WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
1837         if (is_data)
1838                 goto pinit;
1839
1840         buf = btrfs_find_tree_block(root, bytenr, num_bytes);
1841         if (!buf)
1842                 goto pinit;
1843
1844         /* we can reuse a block if it hasn't been written
1845          * and it is from this transaction.  We can't
1846          * reuse anything from the tree log root because
1847          * it has tiny sub-transactions.
1848          */
1849         if (btrfs_buffer_uptodate(buf, 0) &&
1850             btrfs_try_tree_lock(buf)) {
1851                 u64 header_owner = btrfs_header_owner(buf);
1852                 u64 header_transid = btrfs_header_generation(buf);
1853                 if (header_owner != BTRFS_TREE_LOG_OBJECTID &&
1854                     header_owner != BTRFS_TREE_RELOC_OBJECTID &&
1855                     header_transid == trans->transid &&
1856                     !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
1857                         clean_tree_block(NULL, root, buf);
1858                         btrfs_tree_unlock(buf);
1859                         free_extent_buffer(buf);
1860                         return 1;
1861                 }
1862                 btrfs_tree_unlock(buf);
1863         }
1864         free_extent_buffer(buf);
1865 pinit:
1866         btrfs_update_pinned_extents(root, bytenr, num_bytes, 1);
1867
1868         BUG_ON(err < 0);
1869         return 0;
1870 }
1871
1872 /*
1873  * remove an extent from the root, returns 0 on success
1874  */
1875 static int __free_extent(struct btrfs_trans_handle *trans,
1876                          struct btrfs_root *root,
1877                          u64 bytenr, u64 num_bytes, u64 parent,
1878                          u64 root_objectid, u64 ref_generation,
1879                          u64 owner_objectid, int pin, int mark_free)
1880 {
1881         struct btrfs_path *path;
1882         struct btrfs_key key;
1883         struct btrfs_fs_info *info = root->fs_info;
1884         struct btrfs_root *extent_root = info->extent_root;
1885         struct extent_buffer *leaf;
1886         int ret;
1887         int extent_slot = 0;
1888         int found_extent = 0;
1889         int num_to_del = 1;
1890         struct btrfs_extent_item *ei;
1891         u32 refs;
1892
1893         WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
1894         key.objectid = bytenr;
1895         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
1896         key.offset = num_bytes;
1897         path = btrfs_alloc_path();
1898         if (!path)
1899                 return -ENOMEM;
1900
1901         path->reada = 1;
1902         ret = lookup_extent_backref(trans, extent_root, path,
1903                                     bytenr, parent, root_objectid,
1904                                     ref_generation, owner_objectid, 1);
1905         if (ret == 0) {
1906                 struct btrfs_key found_key;
1907                 extent_slot = path->slots[0];
1908                 while(extent_slot > 0) {
1909                         extent_slot--;
1910                         btrfs_item_key_to_cpu(path->nodes[0], &found_key,
1911                                               extent_slot);
1912                         if (found_key.objectid != bytenr)
1913                                 break;
1914                         if (found_key.type == BTRFS_EXTENT_ITEM_KEY &&
1915                             found_key.offset == num_bytes) {
1916                                 found_extent = 1;
1917                                 break;
1918                         }
1919                         if (path->slots[0] - extent_slot > 5)
1920                                 break;
1921                 }
1922                 if (!found_extent) {
1923                         ret = remove_extent_backref(trans, extent_root, path);
1924                         BUG_ON(ret);
1925                         btrfs_release_path(extent_root, path);
1926                         ret = btrfs_search_slot(trans, extent_root,
1927                                                 &key, path, -1, 1);
1928                         BUG_ON(ret);
1929                         extent_slot = path->slots[0];
1930                 }
1931         } else {
1932                 btrfs_print_leaf(extent_root, path->nodes[0]);
1933                 WARN_ON(1);
1934                 printk("Unable to find ref byte nr %Lu root %Lu "
1935                        "gen %Lu owner %Lu\n", bytenr,
1936                        root_objectid, ref_generation, owner_objectid);
1937         }
1938
1939         leaf = path->nodes[0];
1940         ei = btrfs_item_ptr(leaf, extent_slot,
1941                             struct btrfs_extent_item);
1942         refs = btrfs_extent_refs(leaf, ei);
1943         BUG_ON(refs == 0);
1944         refs -= 1;
1945         btrfs_set_extent_refs(leaf, ei, refs);
1946
1947         btrfs_mark_buffer_dirty(leaf);
1948
1949         if (refs == 0 && found_extent && path->slots[0] == extent_slot + 1) {
1950                 struct btrfs_extent_ref *ref;
1951                 ref = btrfs_item_ptr(leaf, path->slots[0],
1952                                      struct btrfs_extent_ref);
1953                 BUG_ON(btrfs_ref_num_refs(leaf, ref) != 1);
1954                 /* if the back ref and the extent are next to each other
1955                  * they get deleted below in one shot
1956                  */
1957                 path->slots[0] = extent_slot;
1958                 num_to_del = 2;
1959         } else if (found_extent) {
1960                 /* otherwise delete the extent back ref */
1961                 ret = remove_extent_backref(trans, extent_root, path);
1962                 BUG_ON(ret);
1963                 /* if refs are 0, we need to setup the path for deletion */
1964                 if (refs == 0) {
1965                         btrfs_release_path(extent_root, path);
1966                         ret = btrfs_search_slot(trans, extent_root, &key, path,
1967                                                 -1, 1);
1968                         BUG_ON(ret);
1969                 }
1970         }
1971
1972         if (refs == 0) {
1973                 u64 super_used;
1974                 u64 root_used;
1975 #ifdef BIO_RW_DISCARD
1976                 u64 map_length = num_bytes;
1977                 struct btrfs_multi_bio *multi = NULL;
1978 #endif
1979
1980                 if (pin) {
1981                         ret = pin_down_bytes(trans, root, bytenr, num_bytes,
1982                                 owner_objectid >= BTRFS_FIRST_FREE_OBJECTID);
1983                         if (ret > 0)
1984                                 mark_free = 1;
1985                         BUG_ON(ret < 0);
1986                 }
1987
1988                 /* block accounting for super block */
1989                 spin_lock_irq(&info->delalloc_lock);
1990                 super_used = btrfs_super_bytes_used(&info->super_copy);
1991                 btrfs_set_super_bytes_used(&info->super_copy,
1992                                            super_used - num_bytes);
1993                 spin_unlock_irq(&info->delalloc_lock);
1994
1995                 /* block accounting for root item */
1996                 root_used = btrfs_root_used(&root->root_item);
1997                 btrfs_set_root_used(&root->root_item,
1998                                            root_used - num_bytes);
1999                 ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
2000                                       num_to_del);
2001                 BUG_ON(ret);
2002                 ret = update_block_group(trans, root, bytenr, num_bytes, 0,
2003                                          mark_free);
2004                 BUG_ON(ret);
2005
2006 #ifdef BIO_RW_DISCARD
2007                 /* Tell the block device(s) that the sectors can be discarded */
2008                 ret = btrfs_map_block(&root->fs_info->mapping_tree, READ,
2009                                       bytenr, &map_length, &multi, 0);
2010                 if (!ret) {
2011                         struct btrfs_bio_stripe *stripe = multi->stripes;
2012                         int i;
2013
2014                         if (map_length > num_bytes)
2015                                 map_length = num_bytes;
2016
2017                         for (i = 0; i < multi->num_stripes; i++, stripe++) {
2018                                 blkdev_issue_discard(stripe->dev->bdev,
2019                                                      stripe->physical >> 9,
2020                                                      map_length >> 9);
2021                         }
2022                         kfree(multi);
2023                 }
2024 #endif
2025         }
2026         btrfs_free_path(path);
2027         finish_current_insert(trans, extent_root);
2028         return ret;
2029 }
2030
2031 /*
2032  * find all the blocks marked as pending in the radix tree and remove
2033  * them from the extent map
2034  */
2035 static int del_pending_extents(struct btrfs_trans_handle *trans, struct
2036                                btrfs_root *extent_root)
2037 {
2038         int ret;
2039         int err = 0;
2040         int mark_free = 0;
2041         u64 start;
2042         u64 end;
2043         u64 priv;
2044         struct extent_io_tree *pending_del;
2045         struct extent_io_tree *extent_ins;
2046         struct pending_extent_op *extent_op;
2047
2048         WARN_ON(!mutex_is_locked(&extent_root->fs_info->alloc_mutex));
2049         extent_ins = &extent_root->fs_info->extent_ins;
2050         pending_del = &extent_root->fs_info->pending_del;
2051
2052         while(1) {
2053                 ret = find_first_extent_bit(pending_del, 0, &start, &end,
2054                                             EXTENT_LOCKED);
2055                 if (ret)
2056                         break;
2057
2058                 ret = get_state_private(pending_del, start, &priv);
2059                 BUG_ON(ret);
2060                 extent_op = (struct pending_extent_op *)(unsigned long)priv;
2061
2062                 clear_extent_bits(pending_del, start, end, EXTENT_LOCKED,
2063                                   GFP_NOFS);
2064
2065                 ret = pin_down_bytes(trans, extent_root, start,
2066                                      end + 1 - start, 0);
2067                 mark_free = ret > 0;
2068                 if (!test_range_bit(extent_ins, start, end,
2069                                     EXTENT_LOCKED, 0)) {
2070 free_extent:
2071                         ret = __free_extent(trans, extent_root,
2072                                             start, end + 1 - start,
2073                                             extent_op->orig_parent,
2074                                             extent_root->root_key.objectid,
2075                                             extent_op->orig_generation,
2076                                             extent_op->level, 0, mark_free);
2077                         kfree(extent_op);
2078                 } else {
2079                         kfree(extent_op);
2080                         ret = get_state_private(extent_ins, start, &priv);
2081                         BUG_ON(ret);
2082                         extent_op = (struct pending_extent_op *)
2083                                                         (unsigned long)priv;
2084
2085                         clear_extent_bits(extent_ins, start, end,
2086                                           EXTENT_LOCKED, GFP_NOFS);
2087
2088                         if (extent_op->type == PENDING_BACKREF_UPDATE)
2089                                 goto free_extent;
2090
2091                         ret = update_block_group(trans, extent_root, start,
2092                                                 end + 1 - start, 0, mark_free);
2093                         BUG_ON(ret);
2094                         kfree(extent_op);
2095                 }
2096                 if (ret)
2097                         err = ret;
2098
2099                 if (need_resched()) {
2100                         mutex_unlock(&extent_root->fs_info->alloc_mutex);
2101                         cond_resched();
2102                         mutex_lock(&extent_root->fs_info->alloc_mutex);
2103                 }
2104         }
2105         return err;
2106 }
2107
2108 /*
2109  * remove an extent from the root, returns 0 on success
2110  */
2111 static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
2112                                struct btrfs_root *root,
2113                                u64 bytenr, u64 num_bytes, u64 parent,
2114                                u64 root_objectid, u64 ref_generation,
2115                                u64 owner_objectid, int pin)
2116 {
2117         struct btrfs_root *extent_root = root->fs_info->extent_root;
2118         int pending_ret;
2119         int ret;
2120
2121         WARN_ON(num_bytes < root->sectorsize);
2122         if (root == extent_root) {
2123                 struct pending_extent_op *extent_op;
2124
2125                 extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
2126                 BUG_ON(!extent_op);
2127
2128                 extent_op->type = PENDING_EXTENT_DELETE;
2129                 extent_op->bytenr = bytenr;
2130                 extent_op->num_bytes = num_bytes;
2131                 extent_op->parent = parent;
2132                 extent_op->orig_parent = parent;
2133                 extent_op->generation = ref_generation;
2134                 extent_op->orig_generation = ref_generation;
2135                 extent_op->level = (int)owner_objectid;
2136
2137                 set_extent_bits(&root->fs_info->pending_del,
2138                                 bytenr, bytenr + num_bytes - 1,
2139                                 EXTENT_LOCKED, GFP_NOFS);
2140                 set_state_private(&root->fs_info->pending_del,
2141                                   bytenr, (unsigned long)extent_op);
2142                 return 0;
2143         }
2144         /* if metadata always pin */
2145         if (owner_objectid < BTRFS_FIRST_FREE_OBJECTID) {
2146                 if (root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID) {
2147                         struct btrfs_block_group_cache *cache;
2148
2149                         /* btrfs_free_reserved_extent */
2150                         cache = btrfs_lookup_block_group(root->fs_info, bytenr);
2151                         BUG_ON(!cache);
2152                         btrfs_add_free_space(cache, bytenr, num_bytes);
2153                         update_reserved_extents(root, bytenr, num_bytes, 0);
2154                         return 0;
2155                 }
2156                 pin = 1;
2157         }
2158
2159         /* if data pin when any transaction has committed this */
2160         if (ref_generation != trans->transid)
2161                 pin = 1;
2162
2163         ret = __free_extent(trans, root, bytenr, num_bytes, parent,
2164                             root_objectid, ref_generation,
2165                             owner_objectid, pin, pin == 0);
2166
2167         finish_current_insert(trans, root->fs_info->extent_root);
2168         pending_ret = del_pending_extents(trans, root->fs_info->extent_root);
2169         return ret ? ret : pending_ret;
2170 }
2171
2172 int btrfs_free_extent(struct btrfs_trans_handle *trans,
2173                       struct btrfs_root *root,
2174                       u64 bytenr, u64 num_bytes, u64 parent,
2175                       u64 root_objectid, u64 ref_generation,
2176                       u64 owner_objectid, int pin)
2177 {
2178         int ret;
2179
2180         maybe_lock_mutex(root);
2181         ret = __btrfs_free_extent(trans, root, bytenr, num_bytes, parent,
2182                                   root_objectid, ref_generation,
2183                                   owner_objectid, pin);
2184         maybe_unlock_mutex(root);
2185         return ret;
2186 }
2187
2188 static u64 stripe_align(struct btrfs_root *root, u64 val)
2189 {
2190         u64 mask = ((u64)root->stripesize - 1);
2191         u64 ret = (val + mask) & ~mask;
2192         return ret;
2193 }
2194
2195 /*
2196  * walks the btree of allocated extents and find a hole of a given size.
2197  * The key ins is changed to record the hole:
2198  * ins->objectid == block start
2199  * ins->flags = BTRFS_EXTENT_ITEM_KEY
2200  * ins->offset == number of blocks
2201  * Any available blocks before search_start are skipped.
2202  */
2203 static int noinline find_free_extent(struct btrfs_trans_handle *trans,
2204                                      struct btrfs_root *orig_root,
2205                                      u64 num_bytes, u64 empty_size,
2206                                      u64 search_start, u64 search_end,
2207                                      u64 hint_byte, struct btrfs_key *ins,
2208                                      u64 exclude_start, u64 exclude_nr,
2209                                      int data)
2210 {
2211         int ret;
2212         u64 orig_search_start;
2213         struct btrfs_root * root = orig_root->fs_info->extent_root;
2214         struct btrfs_fs_info *info = root->fs_info;
2215         u64 total_needed = num_bytes;
2216         u64 *last_ptr = NULL;
2217         struct btrfs_block_group_cache *block_group;
2218         int chunk_alloc_done = 0;
2219         int empty_cluster = 2 * 1024 * 1024;
2220         int allowed_chunk_alloc = 0;
2221
2222         WARN_ON(num_bytes < root->sectorsize);
2223         btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
2224
2225         if (orig_root->ref_cows || empty_size)
2226                 allowed_chunk_alloc = 1;
2227
2228         if (data & BTRFS_BLOCK_GROUP_METADATA) {
2229                 last_ptr = &root->fs_info->last_alloc;
2230                 empty_cluster = 256 * 1024;
2231         }
2232
2233         if ((data & BTRFS_BLOCK_GROUP_DATA) && btrfs_test_opt(root, SSD))
2234                 last_ptr = &root->fs_info->last_data_alloc;
2235
2236         if (last_ptr) {
2237                 if (*last_ptr)
2238                         hint_byte = *last_ptr;
2239                 else
2240                         empty_size += empty_cluster;
2241         }
2242
2243         search_start = max(search_start, first_logical_byte(root, 0));
2244         orig_search_start = search_start;
2245
2246         search_start = max(search_start, hint_byte);
2247         total_needed += empty_size;
2248
2249 new_group:
2250         block_group = btrfs_lookup_block_group(info, search_start);
2251         if (!block_group)
2252                 block_group = btrfs_lookup_first_block_group(info,
2253                                                              search_start);
2254
2255         /*
2256          * Ok this looks a little tricky, buts its really simple.  First if we
2257          * didn't find a block group obviously we want to start over.
2258          * Secondly, if the block group we found does not match the type we
2259          * need, and we have a last_ptr and its not 0, chances are the last
2260          * allocation we made was at the end of the block group, so lets go
2261          * ahead and skip the looking through the rest of the block groups and
2262          * start at the beginning.  This helps with metadata allocations,
2263          * since you are likely to have a bunch of data block groups to search
2264          * through first before you realize that you need to start over, so go
2265          * ahead and start over and save the time.
2266          */
2267         if (!block_group || (!block_group_bits(block_group, data) &&
2268                              last_ptr && *last_ptr)) {
2269                 if (search_start != orig_search_start) {
2270                         if (last_ptr && *last_ptr) {
2271                                 total_needed += empty_cluster;
2272                                 *last_ptr = 0;
2273                         }
2274                         search_start = orig_search_start;
2275                         goto new_group;
2276                 } else if (!chunk_alloc_done && allowed_chunk_alloc) {
2277                         ret = do_chunk_alloc(trans, root,
2278                                              num_bytes + 2 * 1024 * 1024,
2279                                              data, 1);
2280                         if (ret < 0)
2281                                 goto error;
2282                         BUG_ON(ret);
2283                         chunk_alloc_done = 1;
2284                         search_start = orig_search_start;
2285                         goto new_group;
2286                 } else {
2287                         ret = -ENOSPC;
2288                         goto error;
2289                 }
2290         }
2291
2292         /*
2293          * this is going to seach through all of the existing block groups it
2294          * can find, so if we don't find something we need to see if we can
2295          * allocate what we need.
2296          */
2297         ret = find_free_space(root, &block_group, &search_start,
2298                               total_needed, data);
2299         if (ret == -ENOSPC) {
2300                 /*
2301                  * instead of allocating, start at the original search start
2302                  * and see if there is something to be found, if not then we
2303                  * allocate
2304                  */
2305                 if (search_start != orig_search_start) {
2306                         if (last_ptr && *last_ptr) {
2307                                 *last_ptr = 0;
2308                                 total_needed += empty_cluster;
2309                         }
2310                         search_start = orig_search_start;
2311                         goto new_group;
2312                 }
2313
2314                 /*
2315                  * we've already allocated, we're pretty screwed
2316                  */
2317                 if (chunk_alloc_done) {
2318                         goto error;
2319                 } else if (!allowed_chunk_alloc && block_group &&
2320                            block_group_bits(block_group, data)) {
2321                         block_group->space_info->force_alloc = 1;
2322                         goto error;
2323                 } else if (!allowed_chunk_alloc) {
2324                         goto error;
2325                 }
2326
2327                 ret = do_chunk_alloc(trans, root, num_bytes + 2 * 1024 * 1024,
2328                                      data, 1);
2329                 if (ret < 0)
2330                         goto error;
2331
2332                 BUG_ON(ret);
2333                 chunk_alloc_done = 1;
2334                 if (block_group)
2335                         search_start = block_group->key.objectid +
2336                                 block_group->key.offset;
2337                 else
2338                         search_start = orig_search_start;
2339                 goto new_group;
2340         }
2341
2342         if (ret)
2343                 goto error;
2344
2345         search_start = stripe_align(root, search_start);
2346         ins->objectid = search_start;
2347         ins->offset = num_bytes;
2348
2349         if (ins->objectid + num_bytes >= search_end) {
2350                 search_start = orig_search_start;
2351                 if (chunk_alloc_done) {
2352                         ret = -ENOSPC;
2353                         goto error;
2354                 }
2355                 goto new_group;
2356         }
2357
2358         if (ins->objectid + num_bytes >
2359             block_group->key.objectid + block_group->key.offset) {
2360                 if (search_start == orig_search_start && chunk_alloc_done) {
2361                         ret = -ENOSPC;
2362                         goto error;
2363                 }
2364                 search_start = block_group->key.objectid +
2365                         block_group->key.offset;
2366                 goto new_group;
2367         }
2368
2369         if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
2370             ins->objectid < exclude_start + exclude_nr)) {
2371                 search_start = exclude_start + exclude_nr;
2372                 goto new_group;
2373         }
2374
2375         if (!(data & BTRFS_BLOCK_GROUP_DATA))
2376                 trans->block_group = block_group;
2377
2378         ins->offset = num_bytes;
2379         if (last_ptr) {
2380                 *last_ptr = ins->objectid + ins->offset;
2381                 if (*last_ptr ==
2382                     btrfs_super_total_bytes(&root->fs_info->super_copy))
2383                         *last_ptr = 0;
2384         }
2385
2386         ret = 0;
2387 error:
2388         return ret;
2389 }
2390
2391 static void dump_space_info(struct btrfs_space_info *info, u64 bytes)
2392 {
2393         struct btrfs_block_group_cache *cache;
2394         struct list_head *l;
2395
2396         printk(KERN_INFO "space_info has %Lu free, is %sfull\n",
2397                info->total_bytes - info->bytes_used - info->bytes_pinned -
2398                info->bytes_reserved, (info->full) ? "" : "not ");
2399
2400         spin_lock(&info->lock);
2401         list_for_each(l, &info->block_groups) {
2402                 cache = list_entry(l, struct btrfs_block_group_cache, list);
2403                 spin_lock(&cache->lock);
2404                 printk(KERN_INFO "block group %Lu has %Lu bytes, %Lu used "
2405                        "%Lu pinned %Lu reserved\n",
2406                        cache->key.objectid, cache->key.offset,
2407                        btrfs_block_group_used(&cache->item),
2408                        cache->pinned, cache->reserved);
2409                 btrfs_dump_free_space(cache, bytes);
2410                 spin_unlock(&cache->lock);
2411         }
2412         spin_unlock(&info->lock);
2413 }
2414
2415 static int __btrfs_reserve_extent(struct btrfs_trans_handle *trans,
2416                                   struct btrfs_root *root,
2417                                   u64 num_bytes, u64 min_alloc_size,
2418                                   u64 empty_size, u64 hint_byte,
2419                                   u64 search_end, struct btrfs_key *ins,
2420                                   u64 data)
2421 {
2422         int ret;
2423         u64 search_start = 0;
2424         u64 alloc_profile;
2425         struct btrfs_fs_info *info = root->fs_info;
2426         struct btrfs_block_group_cache *cache;
2427
2428         if (data) {
2429                 alloc_profile = info->avail_data_alloc_bits &
2430                                 info->data_alloc_profile;
2431                 data = BTRFS_BLOCK_GROUP_DATA | alloc_profile;
2432         } else if (root == root->fs_info->chunk_root) {
2433                 alloc_profile = info->avail_system_alloc_bits &
2434                                 info->system_alloc_profile;
2435                 data = BTRFS_BLOCK_GROUP_SYSTEM | alloc_profile;
2436         } else {
2437                 alloc_profile = info->avail_metadata_alloc_bits &
2438                                 info->metadata_alloc_profile;
2439                 data = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
2440         }
2441 again:
2442         data = reduce_alloc_profile(root, data);
2443         /*
2444          * the only place that sets empty_size is btrfs_realloc_node, which
2445          * is not called recursively on allocations
2446          */
2447         if (empty_size || root->ref_cows) {
2448                 if (!(data & BTRFS_BLOCK_GROUP_METADATA)) {
2449                         ret = do_chunk_alloc(trans, root->fs_info->extent_root,
2450                                      2 * 1024 * 1024,
2451                                      BTRFS_BLOCK_GROUP_METADATA |
2452                                      (info->metadata_alloc_profile &
2453                                       info->avail_metadata_alloc_bits), 0);
2454                 }
2455                 ret = do_chunk_alloc(trans, root->fs_info->extent_root,
2456                                      num_bytes + 2 * 1024 * 1024, data, 0);
2457         }
2458
2459         WARN_ON(num_bytes < root->sectorsize);
2460         ret = find_free_extent(trans, root, num_bytes, empty_size,
2461                                search_start, search_end, hint_byte, ins,
2462                                trans->alloc_exclude_start,
2463                                trans->alloc_exclude_nr, data);
2464
2465         if (ret == -ENOSPC && num_bytes > min_alloc_size) {
2466                 num_bytes = num_bytes >> 1;
2467                 num_bytes = num_bytes & ~(root->sectorsize - 1);
2468                 num_bytes = max(num_bytes, min_alloc_size);
2469                 do_chunk_alloc(trans, root->fs_info->extent_root,
2470                                num_bytes, data, 1);
2471                 goto again;
2472         }
2473         if (ret) {
2474                 struct btrfs_space_info *sinfo;
2475
2476                 sinfo = __find_space_info(root->fs_info, data);
2477                 printk("allocation failed flags %Lu, wanted %Lu\n",
2478                        data, num_bytes);
2479                 dump_space_info(sinfo, num_bytes);
2480                 BUG();
2481         }
2482         cache = btrfs_lookup_block_group(root->fs_info, ins->objectid);
2483         if (!cache) {
2484                 printk(KERN_ERR "Unable to find block group for %Lu\n", ins->objectid);
2485                 return -ENOSPC;
2486         }
2487
2488         ret = btrfs_remove_free_space(cache, ins->objectid, ins->offset);
2489
2490         return ret;
2491 }
2492
2493 int btrfs_free_reserved_extent(struct btrfs_root *root, u64 start, u64 len)
2494 {
2495         struct btrfs_block_group_cache *cache;
2496
2497         maybe_lock_mutex(root);
2498         cache = btrfs_lookup_block_group(root->fs_info, start);
2499         if (!cache) {
2500                 printk(KERN_ERR "Unable to find block group for %Lu\n", start);
2501                 maybe_unlock_mutex(root);
2502                 return -ENOSPC;
2503         }
2504         btrfs_add_free_space(cache, start, len);
2505         update_reserved_extents(root, start, len, 0);
2506         maybe_unlock_mutex(root);
2507         return 0;
2508 }
2509
2510 int btrfs_reserve_extent(struct btrfs_trans_handle *trans,
2511                                   struct btrfs_root *root,
2512                                   u64 num_bytes, u64 min_alloc_size,
2513                                   u64 empty_size, u64 hint_byte,
2514                                   u64 search_end, struct btrfs_key *ins,
2515                                   u64 data)
2516 {
2517         int ret;
2518         maybe_lock_mutex(root);
2519         ret = __btrfs_reserve_extent(trans, root, num_bytes, min_alloc_size,
2520                                      empty_size, hint_byte, search_end, ins,
2521                                      data);
2522         update_reserved_extents(root, ins->objectid, ins->offset, 1);
2523         maybe_unlock_mutex(root);
2524         return ret;
2525 }
2526
2527 static int __btrfs_alloc_reserved_extent(struct btrfs_trans_handle *trans,
2528                                          struct btrfs_root *root, u64 parent,
2529                                          u64 root_objectid, u64 ref_generation,
2530                                          u64 owner, struct btrfs_key *ins)
2531 {
2532         int ret;
2533         int pending_ret;
2534         u64 super_used;
2535         u64 root_used;
2536         u64 num_bytes = ins->offset;
2537         u32 sizes[2];
2538         struct btrfs_fs_info *info = root->fs_info;
2539         struct btrfs_root *extent_root = info->extent_root;
2540         struct btrfs_extent_item *extent_item;
2541         struct btrfs_extent_ref *ref;
2542         struct btrfs_path *path;
2543         struct btrfs_key keys[2];
2544
2545         if (parent == 0)
2546                 parent = ins->objectid;
2547
2548         /* block accounting for super block */
2549         spin_lock_irq(&info->delalloc_lock);
2550         super_used = btrfs_super_bytes_used(&info->super_copy);
2551         btrfs_set_super_bytes_used(&info->super_copy, super_used + num_bytes);
2552         spin_unlock_irq(&info->delalloc_lock);
2553
2554         /* block accounting for root item */
2555         root_used = btrfs_root_used(&root->root_item);
2556         btrfs_set_root_used(&root->root_item, root_used + num_bytes);
2557
2558         if (root == extent_root) {
2559                 struct pending_extent_op *extent_op;
2560
2561                 extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
2562                 BUG_ON(!extent_op);
2563
2564                 extent_op->type = PENDING_EXTENT_INSERT;
2565                 extent_op->bytenr = ins->objectid;
2566                 extent_op->num_bytes = ins->offset;
2567                 extent_op->parent = parent;
2568                 extent_op->orig_parent = 0;
2569                 extent_op->generation = ref_generation;
2570                 extent_op->orig_generation = 0;
2571                 extent_op->level = (int)owner;
2572
2573                 set_extent_bits(&root->fs_info->extent_ins, ins->objectid,
2574                                 ins->objectid + ins->offset - 1,
2575                                 EXTENT_LOCKED, GFP_NOFS);
2576                 set_state_private(&root->fs_info->extent_ins,
2577                                   ins->objectid, (unsigned long)extent_op);
2578                 goto update_block;
2579         }
2580
2581         memcpy(&keys[0], ins, sizeof(*ins));
2582         keys[1].objectid = ins->objectid;
2583         keys[1].type = BTRFS_EXTENT_REF_KEY;
2584         keys[1].offset = parent;
2585         sizes[0] = sizeof(*extent_item);
2586         sizes[1] = sizeof(*ref);
2587
2588         path = btrfs_alloc_path();
2589         BUG_ON(!path);
2590
2591         ret = btrfs_insert_empty_items(trans, extent_root, path, keys,
2592                                        sizes, 2);
2593         BUG_ON(ret);
2594
2595         extent_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
2596                                      struct btrfs_extent_item);
2597         btrfs_set_extent_refs(path->nodes[0], extent_item, 1);
2598         ref = btrfs_item_ptr(path->nodes[0], path->slots[0] + 1,
2599                              struct btrfs_extent_ref);
2600
2601         btrfs_set_ref_root(path->nodes[0], ref, root_objectid);
2602         btrfs_set_ref_generation(path->nodes[0], ref, ref_generation);
2603         btrfs_set_ref_objectid(path->nodes[0], ref, owner);
2604         btrfs_set_ref_num_refs(path->nodes[0], ref, 1);
2605
2606         btrfs_mark_buffer_dirty(path->nodes[0]);
2607
2608         trans->alloc_exclude_start = 0;
2609         trans->alloc_exclude_nr = 0;
2610         btrfs_free_path(path);
2611         finish_current_insert(trans, extent_root);
2612         pending_ret = del_pending_extents(trans, extent_root);
2613
2614         if (ret)
2615                 goto out;
2616         if (pending_ret) {
2617                 ret = pending_ret;
2618                 goto out;
2619         }
2620
2621 update_block:
2622         ret = update_block_group(trans, root, ins->objectid, ins->offset, 1, 0);
2623         if (ret) {
2624                 printk("update block group failed for %Lu %Lu\n",
2625                        ins->objectid, ins->offset);
2626                 BUG();
2627         }
2628 out:
2629         return ret;
2630 }
2631
2632 int btrfs_alloc_reserved_extent(struct btrfs_trans_handle *trans,
2633                                 struct btrfs_root *root, u64 parent,
2634                                 u64 root_objectid, u64 ref_generation,
2635                                 u64 owner, struct btrfs_key *ins)
2636 {
2637         int ret;
2638
2639         if (root_objectid == BTRFS_TREE_LOG_OBJECTID)
2640                 return 0;
2641         maybe_lock_mutex(root);
2642         ret = __btrfs_alloc_reserved_extent(trans, root, parent, root_objectid,
2643                                             ref_generation, owner, ins);
2644         update_reserved_extents(root, ins->objectid, ins->offset, 0);
2645         maybe_unlock_mutex(root);
2646         return ret;
2647 }
2648
2649 /*
2650  * this is used by the tree logging recovery code.  It records that
2651  * an extent has been allocated and makes sure to clear the free
2652  * space cache bits as well
2653  */
2654 int btrfs_alloc_logged_extent(struct btrfs_trans_handle *trans,
2655                                 struct btrfs_root *root, u64 parent,
2656                                 u64 root_objectid, u64 ref_generation,
2657                                 u64 owner, struct btrfs_key *ins)
2658 {
2659         int ret;
2660         struct btrfs_block_group_cache *block_group;
2661
2662         maybe_lock_mutex(root);
2663         block_group = btrfs_lookup_block_group(root->fs_info, ins->objectid);
2664         cache_block_group(root, block_group);
2665
2666         ret = btrfs_remove_free_space(block_group, ins->objectid, ins->offset);
2667         BUG_ON(ret);
2668         ret = __btrfs_alloc_reserved_extent(trans, root, parent, root_objectid,
2669                                             ref_generation, owner, ins);
2670         maybe_unlock_mutex(root);
2671         return ret;
2672 }
2673
2674 /*
2675  * finds a free extent and does all the dirty work required for allocation
2676  * returns the key for the extent through ins, and a tree buffer for
2677  * the first block of the extent through buf.
2678  *
2679  * returns 0 if everything worked, non-zero otherwise.
2680  */
2681 int btrfs_alloc_extent(struct btrfs_trans_handle *trans,
2682                        struct btrfs_root *root,
2683                        u64 num_bytes, u64 parent, u64 min_alloc_size,
2684                        u64 root_objectid, u64 ref_generation,
2685                        u64 owner_objectid, u64 empty_size, u64 hint_byte,
2686                        u64 search_end, struct btrfs_key *ins, u64 data)
2687 {
2688         int ret;
2689
2690         maybe_lock_mutex(root);
2691
2692         ret = __btrfs_reserve_extent(trans, root, num_bytes,
2693                                      min_alloc_size, empty_size, hint_byte,
2694                                      search_end, ins, data);
2695         BUG_ON(ret);
2696         if (root_objectid != BTRFS_TREE_LOG_OBJECTID) {
2697                 ret = __btrfs_alloc_reserved_extent(trans, root, parent,
2698                                         root_objectid, ref_generation,
2699                                         owner_objectid, ins);
2700                 BUG_ON(ret);
2701
2702         } else {
2703                 update_reserved_extents(root, ins->objectid, ins->offset, 1);
2704         }
2705         maybe_unlock_mutex(root);
2706         return ret;
2707 }
2708
2709 struct extent_buffer *btrfs_init_new_buffer(struct btrfs_trans_handle *trans,
2710                                             struct btrfs_root *root,
2711                                             u64 bytenr, u32 blocksize)
2712 {
2713         struct extent_buffer *buf;
2714
2715         buf = btrfs_find_create_tree_block(root, bytenr, blocksize);
2716         if (!buf)
2717                 return ERR_PTR(-ENOMEM);
2718         btrfs_set_header_generation(buf, trans->transid);
2719         btrfs_tree_lock(buf);
2720         clean_tree_block(trans, root, buf);
2721         btrfs_set_buffer_uptodate(buf);
2722         if (root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID) {
2723                 set_extent_dirty(&root->dirty_log_pages, buf->start,
2724                          buf->start + buf->len - 1, GFP_NOFS);
2725         } else {
2726                 set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
2727                          buf->start + buf->len - 1, GFP_NOFS);
2728         }
2729         trans->blocks_used++;
2730         return buf;
2731 }
2732
2733 /*
2734  * helper function to allocate a block for a given tree
2735  * returns the tree buffer or NULL.
2736  */
2737 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
2738                                              struct btrfs_root *root,
2739                                              u32 blocksize, u64 parent,
2740                                              u64 root_objectid,
2741                                              u64 ref_generation,
2742                                              int level,
2743                                              u64 hint,
2744                                              u64 empty_size)
2745 {
2746         struct btrfs_key ins;
2747         int ret;
2748         struct extent_buffer *buf;
2749
2750         ret = btrfs_alloc_extent(trans, root, blocksize, parent, blocksize,
2751                                  root_objectid, ref_generation, level,
2752                                  empty_size, hint, (u64)-1, &ins, 0);
2753         if (ret) {
2754                 BUG_ON(ret > 0);
2755                 return ERR_PTR(ret);
2756         }
2757
2758         buf = btrfs_init_new_buffer(trans, root, ins.objectid, blocksize);
2759         return buf;
2760 }
2761
2762 int btrfs_drop_leaf_ref(struct btrfs_trans_handle *trans,
2763                         struct btrfs_root *root, struct extent_buffer *leaf)
2764 {
2765         u64 leaf_owner;
2766         u64 leaf_generation;
2767         struct btrfs_key key;
2768         struct btrfs_file_extent_item *fi;
2769         int i;
2770         int nritems;
2771         int ret;
2772
2773         BUG_ON(!btrfs_is_leaf(leaf));
2774         nritems = btrfs_header_nritems(leaf);
2775         leaf_owner = btrfs_header_owner(leaf);
2776         leaf_generation = btrfs_header_generation(leaf);
2777
2778         for (i = 0; i < nritems; i++) {
2779                 u64 disk_bytenr;
2780                 cond_resched();
2781
2782                 btrfs_item_key_to_cpu(leaf, &key, i);
2783                 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
2784                         continue;
2785                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
2786                 if (btrfs_file_extent_type(leaf, fi) ==
2787                     BTRFS_FILE_EXTENT_INLINE)
2788                         continue;
2789                 /*
2790                  * FIXME make sure to insert a trans record that
2791                  * repeats the snapshot del on crash
2792                  */
2793                 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
2794                 if (disk_bytenr == 0)
2795                         continue;
2796
2797                 mutex_lock(&root->fs_info->alloc_mutex);
2798                 ret = __btrfs_free_extent(trans, root, disk_bytenr,
2799                                 btrfs_file_extent_disk_num_bytes(leaf, fi),
2800                                 leaf->start, leaf_owner, leaf_generation,
2801                                 key.objectid, 0);
2802                 mutex_unlock(&root->fs_info->alloc_mutex);
2803                 BUG_ON(ret);
2804
2805                 atomic_inc(&root->fs_info->throttle_gen);
2806                 wake_up(&root->fs_info->transaction_throttle);
2807                 cond_resched();
2808         }
2809         return 0;
2810 }
2811
2812 static int noinline cache_drop_leaf_ref(struct btrfs_trans_handle *trans,
2813                                         struct btrfs_root *root,
2814                                         struct btrfs_leaf_ref *ref)
2815 {
2816         int i;
2817         int ret;
2818         struct btrfs_extent_info *info = ref->extents;
2819
2820         for (i = 0; i < ref->nritems; i++) {
2821                 mutex_lock(&root->fs_info->alloc_mutex);
2822                 ret = __btrfs_free_extent(trans, root, info->bytenr,
2823                                           info->num_bytes, ref->bytenr,
2824                                           ref->owner, ref->generation,
2825                                           info->objectid, 0);
2826                 mutex_unlock(&root->fs_info->alloc_mutex);
2827
2828                 atomic_inc(&root->fs_info->throttle_gen);
2829                 wake_up(&root->fs_info->transaction_throttle);
2830                 cond_resched();
2831
2832                 BUG_ON(ret);
2833                 info++;
2834         }
2835
2836         return 0;
2837 }
2838
2839 int drop_snap_lookup_refcount(struct btrfs_root *root, u64 start, u64 len,
2840                               u32 *refs)
2841 {
2842         int ret;
2843
2844         ret = btrfs_lookup_extent_ref(NULL, root, start, len, refs);
2845         BUG_ON(ret);
2846
2847 #if 0 // some debugging code in case we see problems here
2848         /* if the refs count is one, it won't get increased again.  But
2849          * if the ref count is > 1, someone may be decreasing it at
2850          * the same time we are.
2851          */
2852         if (*refs != 1) {
2853                 struct extent_buffer *eb = NULL;
2854                 eb = btrfs_find_create_tree_block(root, start, len);
2855                 if (eb)
2856                         btrfs_tree_lock(eb);
2857
2858                 mutex_lock(&root->fs_info->alloc_mutex);
2859                 ret = lookup_extent_ref(NULL, root, start, len, refs);
2860                 BUG_ON(ret);
2861                 mutex_unlock(&root->fs_info->alloc_mutex);
2862
2863                 if (eb) {
2864                         btrfs_tree_unlock(eb);
2865                         free_extent_buffer(eb);
2866                 }
2867                 if (*refs == 1) {
2868                         printk("block %llu went down to one during drop_snap\n",
2869                                (unsigned long long)start);
2870                 }
2871
2872         }
2873 #endif
2874
2875         cond_resched();
2876         return ret;
2877 }
2878
2879 /*
2880  * helper function for drop_snapshot, this walks down the tree dropping ref
2881  * counts as it goes.
2882  */
2883 static int noinline walk_down_tree(struct btrfs_trans_handle *trans,
2884                                    struct btrfs_root *root,
2885                                    struct btrfs_path *path, int *level)
2886 {
2887         u64 root_owner;
2888         u64 root_gen;
2889         u64 bytenr;
2890         u64 ptr_gen;
2891         struct extent_buffer *next;
2892         struct extent_buffer *cur;
2893         struct extent_buffer *parent;
2894         struct btrfs_leaf_ref *ref;
2895         u32 blocksize;
2896         int ret;
2897         u32 refs;
2898
2899         WARN_ON(*level < 0);
2900         WARN_ON(*level >= BTRFS_MAX_LEVEL);
2901         ret = drop_snap_lookup_refcount(root, path->nodes[*level]->start,
2902                                 path->nodes[*level]->len, &refs);
2903         BUG_ON(ret);
2904         if (refs > 1)
2905                 goto out;
2906
2907         /*
2908          * walk down to the last node level and free all the leaves
2909          */
2910         while(*level >= 0) {
2911                 WARN_ON(*level < 0);
2912                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
2913                 cur = path->nodes[*level];
2914
2915                 if (btrfs_header_level(cur) != *level)
2916                         WARN_ON(1);
2917
2918                 if (path->slots[*level] >=
2919                     btrfs_header_nritems(cur))
2920                         break;
2921                 if (*level == 0) {
2922                         ret = btrfs_drop_leaf_ref(trans, root, cur);
2923                         BUG_ON(ret);
2924                         break;
2925                 }
2926                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
2927                 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
2928                 blocksize = btrfs_level_size(root, *level - 1);
2929
2930                 ret = drop_snap_lookup_refcount(root, bytenr, blocksize, &refs);
2931                 BUG_ON(ret);
2932                 if (refs != 1) {
2933                         parent = path->nodes[*level];
2934                         root_owner = btrfs_header_owner(parent);
2935                         root_gen = btrfs_header_generation(parent);
2936                         path->slots[*level]++;
2937
2938                         mutex_lock(&root->fs_info->alloc_mutex);
2939                         ret = __btrfs_free_extent(trans, root, bytenr,
2940                                                 blocksize, parent->start,
2941                                                 root_owner, root_gen,
2942                                                 *level - 1, 1);
2943                         BUG_ON(ret);
2944                         mutex_unlock(&root->fs_info->alloc_mutex);
2945
2946                         atomic_inc(&root->fs_info->throttle_gen);
2947                         wake_up(&root->fs_info->transaction_throttle);
2948                         cond_resched();
2949
2950                         continue;
2951                 }
2952                 /*
2953                  * at this point, we have a single ref, and since the
2954                  * only place referencing this extent is a dead root
2955                  * the reference count should never go higher.
2956                  * So, we don't need to check it again
2957                  */
2958                 if (*level == 1) {
2959                         ref = btrfs_lookup_leaf_ref(root, bytenr);
2960                         if (ref && ref->generation != ptr_gen) {
2961                                 btrfs_free_leaf_ref(root, ref);
2962                                 ref = NULL;
2963                         }
2964                         if (ref) {
2965                                 ret = cache_drop_leaf_ref(trans, root, ref);
2966                                 BUG_ON(ret);
2967                                 btrfs_remove_leaf_ref(root, ref);
2968                                 btrfs_free_leaf_ref(root, ref);
2969                                 *level = 0;
2970                                 break;
2971                         }
2972                         if (printk_ratelimit()) {
2973                                 printk("leaf ref miss for bytenr %llu\n",
2974                                        (unsigned long long)bytenr);
2975                         }
2976                 }
2977                 next = btrfs_find_tree_block(root, bytenr, blocksize);
2978                 if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
2979                         free_extent_buffer(next);
2980
2981                         next = read_tree_block(root, bytenr, blocksize,
2982                                                ptr_gen);
2983                         cond_resched();
2984 #if 0
2985                         /*
2986                          * this is a debugging check and can go away
2987                          * the ref should never go all the way down to 1
2988                          * at this point
2989                          */
2990                         ret = lookup_extent_ref(NULL, root, bytenr, blocksize,
2991                                                 &refs);
2992                         BUG_ON(ret);
2993                         WARN_ON(refs != 1);
2994 #endif
2995                 }
2996                 WARN_ON(*level <= 0);
2997                 if (path->nodes[*level-1])
2998                         free_extent_buffer(path->nodes[*level-1]);
2999                 path->nodes[*level-1] = next;
3000                 *level = btrfs_header_level(next);
3001                 path->slots[*level] = 0;
3002                 cond_resched();
3003         }
3004 out:
3005         WARN_ON(*level < 0);
3006         WARN_ON(*level >= BTRFS_MAX_LEVEL);
3007
3008         if (path->nodes[*level] == root->node) {
3009                 parent = path->nodes[*level];
3010                 bytenr = path->nodes[*level]->start;
3011         } else {
3012                 parent = path->nodes[*level + 1];
3013                 bytenr = btrfs_node_blockptr(parent, path->slots[*level + 1]);
3014         }
3015
3016         blocksize = btrfs_level_size(root, *level);
3017         root_owner = btrfs_header_owner(parent);
3018         root_gen = btrfs_header_generation(parent);
3019
3020         mutex_lock(&root->fs_info->alloc_mutex);
3021         ret = __btrfs_free_extent(trans, root, bytenr, blocksize,
3022                                   parent->start, root_owner, root_gen,
3023                                   *level, 1);
3024         mutex_unlock(&root->fs_info->alloc_mutex);
3025         free_extent_buffer(path->nodes[*level]);
3026         path->nodes[*level] = NULL;
3027         *level += 1;
3028         BUG_ON(ret);
3029
3030         cond_resched();
3031         return 0;
3032 }
3033
3034 /*
3035  * helper function for drop_subtree, this function is similar to
3036  * walk_down_tree. The main difference is that it checks reference
3037  * counts while tree blocks are locked.
3038  */
3039 static int noinline walk_down_subtree(struct btrfs_trans_handle *trans,
3040                                       struct btrfs_root *root,
3041                                       struct btrfs_path *path, int *level)
3042 {
3043         struct extent_buffer *next;
3044         struct extent_buffer *cur;
3045         struct extent_buffer *parent;
3046         u64 bytenr;
3047         u64 ptr_gen;
3048         u32 blocksize;
3049         u32 refs;
3050         int ret;
3051
3052         cur = path->nodes[*level];
3053         ret = btrfs_lookup_extent_ref(trans, root, cur->start, cur->len,
3054                                       &refs);
3055         BUG_ON(ret);
3056         if (refs > 1)
3057                 goto out;
3058
3059         while (*level >= 0) {
3060                 cur = path->nodes[*level];
3061                 if (*level == 0) {
3062                         ret = btrfs_drop_leaf_ref(trans, root, cur);
3063                         BUG_ON(ret);
3064                         clean_tree_block(trans, root, cur);
3065                         break;
3066                 }
3067                 if (path->slots[*level] >= btrfs_header_nritems(cur)) {
3068                         clean_tree_block(trans, root, cur);
3069                         break;
3070                 }
3071
3072                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
3073                 blocksize = btrfs_level_size(root, *level - 1);
3074                 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
3075
3076                 next = read_tree_block(root, bytenr, blocksize, ptr_gen);
3077                 btrfs_tree_lock(next);
3078
3079                 ret = btrfs_lookup_extent_ref(trans, root, bytenr, blocksize,
3080                                               &refs);
3081                 BUG_ON(ret);
3082                 if (refs > 1) {
3083                         parent = path->nodes[*level];
3084                         ret = btrfs_free_extent(trans, root, bytenr,
3085                                         blocksize, parent->start,
3086                                         btrfs_header_owner(parent),
3087                                         btrfs_header_generation(parent),
3088                                         *level - 1, 1);
3089                         BUG_ON(ret);
3090                         path->slots[*level]++;
3091                         btrfs_tree_unlock(next);
3092                         free_extent_buffer(next);
3093                         continue;
3094                 }
3095
3096                 *level = btrfs_header_level(next);
3097                 path->nodes[*level] = next;
3098                 path->slots[*level] = 0;
3099                 path->locks[*level] = 1;
3100                 cond_resched();
3101         }
3102 out:
3103         parent = path->nodes[*level + 1];
3104         bytenr = path->nodes[*level]->start;
3105         blocksize = path->nodes[*level]->len;
3106
3107         ret = btrfs_free_extent(trans, root, bytenr, blocksize,
3108                         parent->start, btrfs_header_owner(parent),
3109                         btrfs_header_generation(parent), *level, 1);
3110         BUG_ON(ret);
3111
3112         if (path->locks[*level]) {
3113                 btrfs_tree_unlock(path->nodes[*level]);
3114                 path->locks[*level] = 0;
3115         }
3116         free_extent_buffer(path->nodes[*level]);
3117         path->nodes[*level] = NULL;
3118         *level += 1;
3119         cond_resched();
3120         return 0;
3121 }
3122
3123 /*
3124  * helper for dropping snapshots.  This walks back up the tree in the path
3125  * to find the first node higher up where we haven't yet gone through
3126  * all the slots
3127  */
3128 static int noinline walk_up_tree(struct btrfs_trans_handle *trans,
3129                                  struct btrfs_root *root,
3130                                  struct btrfs_path *path,
3131                                  int *level, int max_level)
3132 {
3133         u64 root_owner;
3134         u64 root_gen;
3135         struct btrfs_root_item *root_item = &root->root_item;
3136         int i;
3137         int slot;
3138         int ret;
3139
3140         for (i = *level; i < max_level && path->nodes[i]; i++) {
3141                 slot = path->slots[i];
3142                 if (slot < btrfs_header_nritems(path->nodes[i]) - 1) {
3143                         struct extent_buffer *node;
3144                         struct btrfs_disk_key disk_key;
3145                         node = path->nodes[i];
3146                         path->slots[i]++;
3147                         *level = i;
3148                         WARN_ON(*level == 0);
3149                         btrfs_node_key(node, &disk_key, path->slots[i]);
3150                         memcpy(&root_item->drop_progress,
3151                                &disk_key, sizeof(disk_key));
3152                         root_item->drop_level = i;
3153                         return 0;
3154                 } else {
3155                         struct extent_buffer *parent;
3156                         if (path->nodes[*level] == root->node)
3157                                 parent = path->nodes[*level];
3158                         else
3159                                 parent = path->nodes[*level + 1];
3160
3161                         root_owner = btrfs_header_owner(parent);
3162                         root_gen = btrfs_header_generation(parent);
3163
3164                         clean_tree_block(trans, root, path->nodes[*level]);
3165                         ret = btrfs_free_extent(trans, root,
3166                                                 path->nodes[*level]->start,
3167                                                 path->nodes[*level]->len,
3168                                                 parent->start, root_owner,
3169                                                 root_gen, *level, 1);
3170                         BUG_ON(ret);
3171                         if (path->locks[*level]) {
3172                                 btrfs_tree_unlock(path->nodes[*level]);
3173                                 path->locks[*level] = 0;
3174                         }
3175                         free_extent_buffer(path->nodes[*level]);
3176                         path->nodes[*level] = NULL;
3177                         *level = i + 1;
3178                 }
3179         }
3180         return 1;
3181 }
3182
3183 /*
3184  * drop the reference count on the tree rooted at 'snap'.  This traverses
3185  * the tree freeing any blocks that have a ref count of zero after being
3186  * decremented.
3187  */
3188 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
3189                         *root)
3190 {
3191         int ret = 0;
3192         int wret;
3193         int level;
3194         struct btrfs_path *path;
3195         int i;
3196         int orig_level;
3197         struct btrfs_root_item *root_item = &root->root_item;
3198
3199         WARN_ON(!mutex_is_locked(&root->fs_info->drop_mutex));
3200         path = btrfs_alloc_path();
3201         BUG_ON(!path);
3202
3203         level = btrfs_header_level(root->node);
3204         orig_level = level;
3205         if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
3206                 path->nodes[level] = root->node;
3207                 extent_buffer_get(root->node);
3208                 path->slots[level] = 0;
3209         } else {
3210                 struct btrfs_key key;
3211                 struct btrfs_disk_key found_key;
3212                 struct extent_buffer *node;
3213
3214                 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
3215                 level = root_item->drop_level;
3216                 path->lowest_level = level;
3217                 wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
3218                 if (wret < 0) {
3219                         ret = wret;
3220                         goto out;
3221                 }
3222                 node = path->nodes[level];
3223                 btrfs_node_key(node, &found_key, path->slots[level]);
3224                 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
3225                                sizeof(found_key)));
3226                 /*
3227                  * unlock our path, this is safe because only this
3228                  * function is allowed to delete this snapshot
3229                  */
3230                 for (i = 0; i < BTRFS_MAX_LEVEL; i++) {
3231                         if (path->nodes[i] && path->locks[i]) {
3232                                 path->locks[i] = 0;
3233                                 btrfs_tree_unlock(path->nodes[i]);
3234                         }
3235                 }
3236         }
3237         while(1) {
3238                 wret = walk_down_tree(trans, root, path, &level);
3239                 if (wret > 0)
3240                         break;
3241                 if (wret < 0)
3242                         ret = wret;
3243
3244                 wret = walk_up_tree(trans, root, path, &level,
3245                                     BTRFS_MAX_LEVEL);
3246                 if (wret > 0)
3247                         break;
3248                 if (wret < 0)
3249                         ret = wret;
3250                 if (trans->transaction->in_commit) {
3251                         ret = -EAGAIN;
3252                         break;
3253                 }
3254                 atomic_inc(&root->fs_info->throttle_gen);
3255                 wake_up(&root->fs_info->transaction_throttle);
3256         }
3257         for (i = 0; i <= orig_level; i++) {
3258                 if (path->nodes[i]) {
3259                         free_extent_buffer(path->nodes[i]);
3260                         path->nodes[i] = NULL;
3261                 }
3262         }
3263 out:
3264         btrfs_free_path(path);
3265         return ret;
3266 }
3267
3268 int btrfs_drop_subtree(struct btrfs_trans_handle *trans,
3269                         struct btrfs_root *root,
3270                         struct extent_buffer *node,
3271                         struct extent_buffer *parent)
3272 {
3273         struct btrfs_path *path;
3274         int level;
3275         int parent_level;
3276         int ret = 0;
3277         int wret;
3278
3279         path = btrfs_alloc_path();
3280         BUG_ON(!path);
3281
3282         BUG_ON(!btrfs_tree_locked(parent));
3283         parent_level = btrfs_header_level(parent);
3284         extent_buffer_get(parent);
3285         path->nodes[parent_level] = parent;
3286         path->slots[parent_level] = btrfs_header_nritems(parent);
3287
3288         BUG_ON(!btrfs_tree_locked(node));
3289         level = btrfs_header_level(node);
3290         extent_buffer_get(node);
3291         path->nodes[level] = node;
3292         path->slots[level] = 0;
3293
3294         while (1) {
3295                 wret = walk_down_subtree(trans, root, path, &level);
3296                 if (wret < 0)
3297                         ret = wret;
3298                 if (wret != 0)
3299                         break;
3300
3301                 wret = walk_up_tree(trans, root, path, &level, parent_level);
3302                 if (wret < 0)
3303                         ret = wret;
3304                 if (wret != 0)
3305                         break;
3306         }
3307
3308         btrfs_free_path(path);
3309         return ret;
3310 }
3311
3312 static unsigned long calc_ra(unsigned long start, unsigned long last,
3313                              unsigned long nr)
3314 {
3315         return min(last, start + nr - 1);
3316 }
3317
3318 static int noinline relocate_inode_pages(struct inode *inode, u64 start,
3319                                          u64 len)
3320 {
3321         u64 page_start;
3322         u64 page_end;
3323         unsigned long first_index;
3324         unsigned long last_index;
3325         unsigned long i;
3326         struct page *page;
3327         struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
3328         struct file_ra_state *ra;
3329         struct btrfs_ordered_extent *ordered;
3330         unsigned int total_read = 0;
3331         unsigned int total_dirty = 0;
3332         int ret = 0;
3333
3334         ra = kzalloc(sizeof(*ra), GFP_NOFS);
3335
3336         mutex_lock(&inode->i_mutex);
3337         first_index = start >> PAGE_CACHE_SHIFT;
3338         last_index = (start + len - 1) >> PAGE_CACHE_SHIFT;
3339
3340         /* make sure the dirty trick played by the caller work */
3341         ret = invalidate_inode_pages2_range(inode->i_mapping,
3342                                             first_index, last_index);
3343         if (ret)
3344                 goto out_unlock;
3345
3346         file_ra_state_init(ra, inode->i_mapping);
3347
3348         for (i = first_index ; i <= last_index; i++) {
3349                 if (total_read % ra->ra_pages == 0) {
3350                         btrfs_force_ra(inode->i_mapping, ra, NULL, i,
3351                                        calc_ra(i, last_index, ra->ra_pages));
3352                 }
3353                 total_read++;
3354 again:
3355                 if (((u64)i << PAGE_CACHE_SHIFT) > i_size_read(inode))
3356                         BUG_ON(1);
3357                 page = grab_cache_page(inode->i_mapping, i);
3358                 if (!page) {
3359                         ret = -ENOMEM;
3360                         goto out_unlock;
3361                 }
3362                 if (!PageUptodate(page)) {
3363                         btrfs_readpage(NULL, page);
3364                         lock_page(page);
3365                         if (!PageUptodate(page)) {
3366                                 unlock_page(page);
3367                                 page_cache_release(page);
3368                                 ret = -EIO;
3369                                 goto out_unlock;
3370                         }
3371                 }
3372                 wait_on_page_writeback(page);
3373
3374                 page_start = (u64)page->index << PAGE_CACHE_SHIFT;
3375                 page_end = page_start + PAGE_CACHE_SIZE - 1;
3376                 lock_extent(io_tree, page_start, page_end, GFP_NOFS);
3377
3378                 ordered = btrfs_lookup_ordered_extent(inode, page_start);
3379                 if (ordered) {
3380                         unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
3381                         unlock_page(page);
3382                         page_cache_release(page);
3383                         btrfs_start_ordered_extent(inode, ordered, 1);
3384                         btrfs_put_ordered_extent(ordered);
3385                         goto again;
3386                 }
3387                 set_page_extent_mapped(page);
3388
3389                 btrfs_set_extent_delalloc(inode, page_start, page_end);
3390                 if (i == first_index)
3391                         set_extent_bits(io_tree, page_start, page_end,
3392                                         EXTENT_BOUNDARY, GFP_NOFS);
3393
3394                 set_page_dirty(page);
3395                 total_dirty++;
3396
3397                 unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
3398                 unlock_page(page);
3399                 page_cache_release(page);
3400         }
3401
3402 out_unlock:
3403         kfree(ra);
3404         mutex_unlock(&inode->i_mutex);
3405         balance_dirty_pages_ratelimited_nr(inode->i_mapping, total_dirty);
3406         return ret;
3407 }
3408
3409 static int noinline relocate_data_extent(struct inode *reloc_inode,
3410                                          struct btrfs_key *extent_key,
3411                                          u64 offset)
3412 {
3413         struct btrfs_root *root = BTRFS_I(reloc_inode)->root;
3414         struct extent_map_tree *em_tree = &BTRFS_I(reloc_inode)->extent_tree;
3415         struct extent_map *em;
3416
3417         em = alloc_extent_map(GFP_NOFS);
3418         BUG_ON(!em || IS_ERR(em));
3419
3420         em->start = extent_key->objectid - offset;
3421         em->len = extent_key->offset;
3422         em->block_len = extent_key->offset;
3423         em->block_start = extent_key->objectid;
3424         em->bdev = root->fs_info->fs_devices->latest_bdev;
3425         set_bit(EXTENT_FLAG_PINNED, &em->flags);
3426
3427         /* setup extent map to cheat btrfs_readpage */
3428         mutex_lock(&BTRFS_I(reloc_inode)->extent_mutex);
3429         while (1) {
3430                 int ret;
3431                 spin_lock(&em_tree->lock);
3432                 ret = add_extent_mapping(em_tree, em);
3433                 spin_unlock(&em_tree->lock);
3434                 if (ret != -EEXIST) {
3435                         free_extent_map(em);
3436                         break;
3437                 }
3438                 btrfs_drop_extent_cache(reloc_inode, em->start,
3439                                         em->start + em->len - 1, 0);
3440         }
3441         mutex_unlock(&BTRFS_I(reloc_inode)->extent_mutex);
3442
3443         return relocate_inode_pages(reloc_inode, extent_key->objectid - offset,
3444                                     extent_key->offset);
3445 }
3446
3447 struct btrfs_ref_path {
3448         u64 extent_start;
3449         u64 nodes[BTRFS_MAX_LEVEL];
3450         u64 root_objectid;
3451         u64 root_generation;
3452         u64 owner_objectid;
3453         u32 num_refs;
3454         int lowest_level;
3455         int current_level;
3456         int shared_level;
3457
3458         struct btrfs_key node_keys[BTRFS_MAX_LEVEL];
3459         u64 new_nodes[BTRFS_MAX_LEVEL];
3460 };
3461
3462 struct disk_extent {
3463         u64 ram_bytes;
3464         u64 disk_bytenr;
3465         u64 disk_num_bytes;
3466         u64 offset;
3467         u64 num_bytes;
3468         u8 compression;
3469         u8 encryption;
3470         u16 other_encoding;
3471 };
3472
3473 static int is_cowonly_root(u64 root_objectid)
3474 {
3475         if (root_objectid == BTRFS_ROOT_TREE_OBJECTID ||
3476             root_objectid == BTRFS_EXTENT_TREE_OBJECTID ||
3477             root_objectid == BTRFS_CHUNK_TREE_OBJECTID ||
3478             root_objectid == BTRFS_DEV_TREE_OBJECTID ||
3479             root_objectid == BTRFS_TREE_LOG_OBJECTID)
3480                 return 1;
3481         return 0;
3482 }
3483
3484 static int noinline __next_ref_path(struct btrfs_trans_handle *trans,
3485                                     struct btrfs_root *extent_root,
3486                                     struct btrfs_ref_path *ref_path,
3487                                     int first_time)
3488 {
3489         struct extent_buffer *leaf;
3490         struct btrfs_path *path;
3491         struct btrfs_extent_ref *ref;
3492         struct btrfs_key key;
3493         struct btrfs_key found_key;
3494         u64 bytenr;
3495         u32 nritems;
3496         int level;
3497         int ret = 1;
3498
3499         path = btrfs_alloc_path();
3500         if (!path)
3501                 return -ENOMEM;
3502
3503         mutex_lock(&extent_root->fs_info->alloc_mutex);
3504
3505         if (first_time) {
3506                 ref_path->lowest_level = -1;
3507                 ref_path->current_level = -1;
3508                 ref_path->shared_level = -1;
3509                 goto walk_up;
3510         }
3511 walk_down:
3512         level = ref_path->current_level - 1;
3513         while (level >= -1) {
3514                 u64 parent;
3515                 if (level < ref_path->lowest_level)
3516                         break;
3517
3518                 if (level >= 0) {
3519                         bytenr = ref_path->nodes[level];
3520                 } else {
3521                         bytenr = ref_path->extent_start;
3522                 }
3523                 BUG_ON(bytenr == 0);
3524
3525                 parent = ref_path->nodes[level + 1];
3526                 ref_path->nodes[level + 1] = 0;
3527                 ref_path->current_level = level;
3528                 BUG_ON(parent == 0);
3529
3530                 key.objectid = bytenr;
3531                 key.offset = parent + 1;
3532                 key.type = BTRFS_EXTENT_REF_KEY;
3533
3534                 ret = btrfs_search_slot(trans, extent_root, &key, path, 0, 0);
3535                 if (ret < 0)
3536                         goto out;
3537                 BUG_ON(ret == 0);
3538
3539                 leaf = path->nodes[0];
3540                 nritems = btrfs_header_nritems(leaf);
3541                 if (path->slots[0] >= nritems) {
3542                         ret = btrfs_next_leaf(extent_root, path);
3543                         if (ret < 0)
3544                                 goto out;
3545                         if (ret > 0)
3546                                 goto next;
3547                         leaf = path->nodes[0];
3548                 }
3549
3550                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
3551                 if (found_key.objectid == bytenr &&
3552                     found_key.type == BTRFS_EXTENT_REF_KEY) {
3553                         if (level < ref_path->shared_level)
3554                                 ref_path->shared_level = level;
3555                         goto found;
3556                 }
3557 next:
3558                 level--;
3559                 btrfs_release_path(extent_root, path);
3560                 if (need_resched()) {
3561                         mutex_unlock(&extent_root->fs_info->alloc_mutex);
3562                         cond_resched();
3563                         mutex_lock(&extent_root->fs_info->alloc_mutex);
3564                 }
3565         }
3566         /* reached lowest level */
3567         ret = 1;
3568         goto out;
3569 walk_up:
3570         level = ref_path->current_level;
3571         while (level < BTRFS_MAX_LEVEL - 1) {
3572                 u64 ref_objectid;
3573                 if (level >= 0) {
3574                         bytenr = ref_path->nodes[level];
3575                 } else {
3576                         bytenr = ref_path->extent_start;
3577                 }
3578                 BUG_ON(bytenr == 0);
3579
3580                 key.objectid = bytenr;
3581                 key.offset = 0;
3582                 key.type = BTRFS_EXTENT_REF_KEY;
3583
3584                 ret = btrfs_search_slot(trans, extent_root, &key, path, 0, 0);
3585                 if (ret < 0)
3586                         goto out;
3587
3588                 leaf = path->nodes[0];
3589                 nritems = btrfs_header_nritems(leaf);
3590                 if (path->slots[0] >= nritems) {
3591                         ret = btrfs_next_leaf(extent_root, path);
3592                         if (ret < 0)
3593                                 goto out;
3594                         if (ret > 0) {
3595                                 /* the extent was freed by someone */
3596                                 if (ref_path->lowest_level == level)
3597                                         goto out;
3598                                 btrfs_release_path(extent_root, path);
3599                                 goto walk_down;
3600                         }
3601                         leaf = path->nodes[0];
3602                 }
3603
3604                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
3605                 if (found_key.objectid != bytenr ||
3606                                 found_key.type != BTRFS_EXTENT_REF_KEY) {
3607                         /* the extent was freed by someone */
3608                         if (ref_path->lowest_level == level) {
3609                                 ret = 1;
3610                                 goto out;
3611                         }
3612                         btrfs_release_path(extent_root, path);
3613                         goto walk_down;
3614                 }
3615 found:
3616                 ref = btrfs_item_ptr(leaf, path->slots[0],
3617                                 struct btrfs_extent_ref);
3618                 ref_objectid = btrfs_ref_objectid(leaf, ref);
3619                 if (ref_objectid < BTRFS_FIRST_FREE_OBJECTID) {
3620                         if (first_time) {
3621                                 level = (int)ref_objectid;
3622                                 BUG_ON(level >= BTRFS_MAX_LEVEL);
3623                                 ref_path->lowest_level = level;
3624                                 ref_path->current_level = level;
3625                                 ref_path->nodes[level] = bytenr;
3626                         } else {
3627                                 WARN_ON(ref_objectid != level);
3628                         }
3629                 } else {
3630                         WARN_ON(level != -1);
3631                 }
3632                 first_time = 0;
3633
3634                 if (ref_path->lowest_level == level) {
3635                         ref_path->owner_objectid = ref_objectid;
3636                         ref_path->num_refs = btrfs_ref_num_refs(leaf, ref);
3637                 }
3638
3639                 /*
3640                  * the block is tree root or the block isn't in reference
3641                  * counted tree.
3642                  */
3643                 if (found_key.objectid == found_key.offset ||
3644                     is_cowonly_root(btrfs_ref_root(leaf, ref))) {
3645                         ref_path->root_objectid = btrfs_ref_root(leaf, ref);
3646                         ref_path->root_generation =
3647                                 btrfs_ref_generation(leaf, ref);
3648                         if (level < 0) {
3649                                 /* special reference from the tree log */
3650                                 ref_path->nodes[0] = found_key.offset;
3651                                 ref_path->current_level = 0;
3652                         }
3653                         ret = 0;
3654                         goto out;
3655                 }
3656
3657                 level++;
3658                 BUG_ON(ref_path->nodes[level] != 0);
3659                 ref_path->nodes[level] = found_key.offset;
3660                 ref_path->current_level = level;
3661
3662                 /*
3663                  * the reference was created in the running transaction,
3664                  * no need to continue walking up.
3665                  */
3666                 if (btrfs_ref_generation(leaf, ref) == trans->transid) {
3667                         ref_path->root_objectid = btrfs_ref_root(leaf, ref);
3668                         ref_path->root_generation =
3669                                 btrfs_ref_generation(leaf, ref);
3670                         ret = 0;
3671                         goto out;
3672                 }
3673
3674                 btrfs_release_path(extent_root, path);
3675                 if (need_resched()) {
3676                         mutex_unlock(&extent_root->fs_info->alloc_mutex);
3677                         cond_resched();
3678                         mutex_lock(&extent_root->fs_info->alloc_mutex);
3679                 }
3680         }
3681         /* reached max tree level, but no tree root found. */
3682         BUG();
3683 out:
3684         mutex_unlock(&extent_root->fs_info->alloc_mutex);
3685         btrfs_free_path(path);
3686         return ret;
3687 }
3688
3689 static int btrfs_first_ref_path(struct btrfs_trans_handle *trans,
3690                                 struct btrfs_root *extent_root,
3691                                 struct btrfs_ref_path *ref_path,
3692                                 u64 extent_start)
3693 {
3694         memset(ref_path, 0, sizeof(*ref_path));
3695         ref_path->extent_start = extent_start;
3696
3697         return __next_ref_path(trans, extent_root, ref_path, 1);
3698 }
3699
3700 static int btrfs_next_ref_path(struct btrfs_trans_handle *trans,
3701                                struct btrfs_root *extent_root,
3702                                struct btrfs_ref_path *ref_path)
3703 {
3704         return __next_ref_path(trans, extent_root, ref_path, 0);
3705 }
3706
3707 static int noinline get_new_locations(struct inode *reloc_inode,
3708                                       struct btrfs_key *extent_key,
3709                                       u64 offset, int no_fragment,
3710                                       struct disk_extent **extents,
3711                                       int *nr_extents)
3712 {
3713         struct btrfs_root *root = BTRFS_I(reloc_inode)->root;
3714         struct btrfs_path *path;
3715         struct btrfs_file_extent_item *fi;
3716         struct extent_buffer *leaf;
3717         struct disk_extent *exts = *extents;
3718         struct btrfs_key found_key;
3719         u64 cur_pos;
3720         u64 last_byte;
3721         u32 nritems;
3722         int nr = 0;
3723         int max = *nr_extents;
3724         int ret;
3725
3726         WARN_ON(!no_fragment && *extents);
3727         if (!exts) {
3728                 max = 1;
3729                 exts = kmalloc(sizeof(*exts) * max, GFP_NOFS);
3730                 if (!exts)
3731                         return -ENOMEM;
3732         }
3733
3734         path = btrfs_alloc_path();
3735         BUG_ON(!path);
3736
3737         cur_pos = extent_key->objectid - offset;
3738         last_byte = extent_key->objectid + extent_key->offset;
3739         ret = btrfs_lookup_file_extent(NULL, root, path, reloc_inode->i_ino,
3740                                        cur_pos, 0);
3741         if (ret < 0)
3742                 goto out;
3743         if (ret > 0) {
3744                 ret = -ENOENT;
3745                 goto out;
3746         }
3747
3748         while (1) {
3749                 leaf = path->nodes[0];
3750                 nritems = btrfs_header_nritems(leaf);
3751                 if (path->slots[0] >= nritems) {
3752                         ret = btrfs_next_leaf(root, path);
3753                         if (ret < 0)
3754                                 goto out;
3755                         if (ret > 0)
3756                                 break;
3757                         leaf = path->nodes[0];
3758                 }
3759
3760                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
3761                 if (found_key.offset != cur_pos ||
3762                     found_key.type != BTRFS_EXTENT_DATA_KEY ||
3763                     found_key.objectid != reloc_inode->i_ino)
3764                         break;
3765
3766                 fi = btrfs_item_ptr(leaf, path->slots[0],
3767                                     struct btrfs_file_extent_item);
3768                 if (btrfs_file_extent_type(leaf, fi) !=
3769                     BTRFS_FILE_EXTENT_REG ||
3770                     btrfs_file_extent_disk_bytenr(leaf, fi) == 0)
3771                         break;
3772
3773                 if (nr == max) {
3774                         struct disk_extent *old = exts;
3775                         max *= 2;
3776                         exts = kzalloc(sizeof(*exts) * max, GFP_NOFS);
3777                         memcpy(exts, old, sizeof(*exts) * nr);
3778                         if (old != *extents)
3779                                 kfree(old);
3780                 }
3781
3782                 exts[nr].disk_bytenr =
3783                         btrfs_file_extent_disk_bytenr(leaf, fi);
3784                 exts[nr].disk_num_bytes =
3785                         btrfs_file_extent_disk_num_bytes(leaf, fi);
3786                 exts[nr].offset = btrfs_file_extent_offset(leaf, fi);
3787                 exts[nr].num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
3788                 exts[nr].ram_bytes = btrfs_file_extent_ram_bytes(leaf, fi);
3789                 exts[nr].compression = btrfs_file_extent_compression(leaf, fi);
3790                 exts[nr].encryption = btrfs_file_extent_encryption(leaf, fi);
3791                 exts[nr].other_encoding = btrfs_file_extent_other_encoding(leaf,
3792                                                                            fi);
3793                 WARN_ON(exts[nr].offset > 0);
3794                 WARN_ON(exts[nr].num_bytes != exts[nr].disk_num_bytes);
3795
3796                 cur_pos += exts[nr].num_bytes;
3797                 nr++;
3798
3799                 if (cur_pos + offset >= last_byte)
3800                         break;
3801
3802                 if (no_fragment) {
3803                         ret = 1;
3804                         goto out;
3805                 }
3806                 path->slots[0]++;
3807         }
3808
3809         WARN_ON(cur_pos + offset > last_byte);
3810         if (cur_pos + offset < last_byte) {
3811                 ret = -ENOENT;
3812                 goto out;
3813         }
3814         ret = 0;
3815 out:
3816         btrfs_free_path(path);
3817         if (ret) {
3818                 if (exts != *extents)
3819                         kfree(exts);
3820         } else {
3821                 *extents = exts;
3822                 *nr_extents = nr;
3823         }
3824         return ret;
3825 }
3826
3827 static int noinline replace_one_extent(struct btrfs_trans_handle *trans,
3828                                         struct btrfs_root *root,
3829                                         struct btrfs_path *path,
3830                                         struct btrfs_key *extent_key,
3831                                         struct btrfs_key *leaf_key,
3832                                         struct btrfs_ref_path *ref_path,
3833                                         struct disk_extent *new_extents,
3834                                         int nr_extents)
3835 {
3836         struct extent_buffer *leaf;
3837         struct btrfs_file_extent_item *fi;
3838         struct inode *inode = NULL;
3839         struct btrfs_key key;
3840         u64 lock_start = 0;
3841         u64 lock_end = 0;
3842         u64 num_bytes;
3843         u64 ext_offset;
3844         u64 first_pos;
3845         u32 nritems;
3846         int nr_scaned = 0;
3847         int extent_locked = 0;
3848         int ret;
3849
3850         memcpy(&key, leaf_key, sizeof(key));
3851         first_pos = INT_LIMIT(loff_t) - extent_key->offset;
3852         if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS) {
3853                 if (key.objectid < ref_path->owner_objectid ||
3854                     (key.objectid == ref_path->owner_objectid &&
3855                      key.type < BTRFS_EXTENT_DATA_KEY)) {
3856                         key.objectid = ref_path->owner_objectid;
3857                         key.type = BTRFS_EXTENT_DATA_KEY;
3858                         key.offset = 0;
3859                 }
3860         }
3861
3862         while (1) {
3863                 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
3864                 if (ret < 0)
3865                         goto out;
3866
3867                 leaf = path->nodes[0];
3868                 nritems = btrfs_header_nritems(leaf);
3869 next:
3870                 if (extent_locked && ret > 0) {
3871                         /*
3872                          * the file extent item was modified by someone
3873                          * before the extent got locked.
3874                          */
3875                         mutex_unlock(&BTRFS_I(inode)->extent_mutex);
3876                         unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
3877                                       lock_end, GFP_NOFS);
3878                         extent_locked = 0;
3879                 }
3880
3881                 if (path->slots[0] >= nritems) {
3882                         if (++nr_scaned > 2)
3883                                 break;
3884
3885                         BUG_ON(extent_locked);
3886                         ret = btrfs_next_leaf(root, path);
3887                         if (ret < 0)
3888                                 goto out;
3889                         if (ret > 0)
3890                                 break;
3891                         leaf = path->nodes[0];
3892                         nritems = btrfs_header_nritems(leaf);
3893                 }
3894
3895                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
3896
3897                 if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS) {
3898                         if ((key.objectid > ref_path->owner_objectid) ||
3899                             (key.objectid == ref_path->owner_objectid &&
3900                              key.type > BTRFS_EXTENT_DATA_KEY) ||
3901                             (key.offset >= first_pos + extent_key->offset))
3902                                 break;
3903                 }
3904
3905                 if (inode && key.objectid != inode->i_ino) {
3906                         BUG_ON(extent_locked);
3907                         btrfs_release_path(root, path);
3908                         mutex_unlock(&inode->i_mutex);
3909                         iput(inode);
3910                         inode = NULL;
3911                         continue;
3912                 }
3913
3914                 if (key.type != BTRFS_EXTENT_DATA_KEY) {
3915                         path->slots[0]++;
3916                         ret = 1;
3917                         goto next;
3918                 }
3919                 fi = btrfs_item_ptr(leaf, path->slots[0],
3920                                     struct btrfs_file_extent_item);
3921                 if ((btrfs_file_extent_type(leaf, fi) !=
3922                      BTRFS_FILE_EXTENT_REG) ||
3923                     (btrfs_file_extent_disk_bytenr(leaf, fi) !=
3924                      extent_key->objectid)) {
3925                         path->slots[0]++;
3926                         ret = 1;
3927                         goto next;
3928                 }
3929
3930                 num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
3931                 ext_offset = btrfs_file_extent_offset(leaf, fi);
3932
3933                 if (first_pos > key.offset - ext_offset)
3934                         first_pos = key.offset - ext_offset;
3935
3936                 if (!extent_locked) {
3937                         lock_start = key.offset;
3938                         lock_end = lock_start + num_bytes - 1;
3939                 } else {
3940                         BUG_ON(lock_start != key.offset);
3941                         BUG_ON(lock_end - lock_start + 1 < num_bytes);
3942                 }
3943
3944                 if (!inode) {
3945                         btrfs_release_path(root, path);
3946
3947                         inode = btrfs_iget_locked(root->fs_info->sb,
3948                                                   key.objectid, root);
3949                         if (inode->i_state & I_NEW) {
3950                                 BTRFS_I(inode)->root = root;
3951                                 BTRFS_I(inode)->location.objectid =
3952                                         key.objectid;
3953                                 BTRFS_I(inode)->location.type =
3954                                         BTRFS_INODE_ITEM_KEY;
3955                                 BTRFS_I(inode)->location.offset = 0;
3956                                 btrfs_read_locked_inode(inode);
3957                                 unlock_new_inode(inode);
3958                         }
3959                         /*
3960                          * some code call btrfs_commit_transaction while
3961                          * holding the i_mutex, so we can't use mutex_lock
3962                          * here.
3963                          */
3964                         if (is_bad_inode(inode) ||
3965                             !mutex_trylock(&inode->i_mutex)) {
3966                                 iput(inode);
3967                                 inode = NULL;
3968                                 key.offset = (u64)-1;
3969                                 goto skip;
3970                         }
3971                 }
3972
3973                 if (!extent_locked) {
3974                         struct btrfs_ordered_extent *ordered;
3975
3976                         btrfs_release_path(root, path);
3977
3978                         lock_extent(&BTRFS_I(inode)->io_tree, lock_start,
3979                                     lock_end, GFP_NOFS);
3980                         ordered = btrfs_lookup_first_ordered_extent(inode,
3981                                                                     lock_end);
3982                         if (ordered &&
3983                             ordered->file_offset <= lock_end &&
3984                             ordered->file_offset + ordered->len > lock_start) {
3985                                 unlock_extent(&BTRFS_I(inode)->io_tree,
3986                                               lock_start, lock_end, GFP_NOFS);
3987                                 btrfs_start_ordered_extent(inode, ordered, 1);
3988                                 btrfs_put_ordered_extent(ordered);
3989                                 key.offset += num_bytes;
3990                                 goto skip;
3991                         }
3992                         if (ordered)
3993                                 btrfs_put_ordered_extent(ordered);
3994
3995                         mutex_lock(&BTRFS_I(inode)->extent_mutex);
3996                         extent_locked = 1;
3997                         continue;
3998                 }
3999
4000                 if (nr_extents == 1) {
4001                         /* update extent pointer in place */
4002                         btrfs_set_file_extent_generation(leaf, fi,
4003                                                 trans->transid);
4004                         btrfs_set_file_extent_disk_bytenr(leaf, fi,
4005                                                 new_extents[0].disk_bytenr);
4006                         btrfs_set_file_extent_disk_num_bytes(leaf, fi,
4007                                                 new_extents[0].disk_num_bytes);
4008                         btrfs_set_file_extent_ram_bytes(leaf, fi,
4009                                                 new_extents[0].ram_bytes);
4010                         ext_offset += new_extents[0].offset;
4011                         btrfs_set_file_extent_offset(leaf, fi, ext_offset);
4012                         btrfs_mark_buffer_dirty(leaf);
4013
4014                         btrfs_drop_extent_cache(inode, key.offset,
4015                                                 key.offset + num_bytes - 1, 0);
4016
4017                         ret = btrfs_inc_extent_ref(trans, root,
4018                                                 new_extents[0].disk_bytenr,
4019                                                 new_extents[0].disk_num_bytes,
4020                                                 leaf->start,
4021                                                 root->root_key.objectid,
4022                                                 trans->transid,
4023                                                 key.objectid);
4024                         BUG_ON(ret);
4025
4026                         ret = btrfs_free_extent(trans, root,
4027                                                 extent_key->objectid,
4028                                                 extent_key->offset,
4029                                                 leaf->start,
4030                                                 btrfs_header_owner(leaf),
4031                                                 btrfs_header_generation(leaf),
4032                                                 key.objectid, 0);
4033                         BUG_ON(ret);
4034
4035                         btrfs_release_path(root, path);
4036                         key.offset += num_bytes;
4037                 } else {
4038                         u64 alloc_hint;
4039                         u64 extent_len;
4040                         int i;
4041                         /*
4042                          * drop old extent pointer at first, then insert the
4043                          * new pointers one bye one
4044                          */
4045                         btrfs_release_path(root, path);
4046                         ret = btrfs_drop_extents(trans, root, inode, key.offset,
4047                                                  key.offset + num_bytes,
4048                                                  key.offset, &alloc_hint);
4049                         BUG_ON(ret);
4050
4051                         for (i = 0; i < nr_extents; i++) {
4052                                 if (ext_offset >= new_extents[i].num_bytes) {
4053                                         ext_offset -= new_extents[i].num_bytes;
4054                                         continue;
4055                                 }
4056                                 extent_len = min(new_extents[i].num_bytes -
4057                                                  ext_offset, num_bytes);
4058
4059                                 ret = btrfs_insert_empty_item(trans, root,
4060                                                               path, &key,
4061                                                               sizeof(*fi));
4062                                 BUG_ON(ret);
4063
4064                                 leaf = path->nodes[0];
4065                                 fi = btrfs_item_ptr(leaf, path->slots[0],
4066                                                 struct btrfs_file_extent_item);
4067                                 btrfs_set_file_extent_generation(leaf, fi,
4068                                                         trans->transid);
4069                                 btrfs_set_file_extent_type(leaf, fi,
4070                                                         BTRFS_FILE_EXTENT_REG);
4071                                 btrfs_set_file_extent_disk_bytenr(leaf, fi,
4072                                                 new_extents[i].disk_bytenr);
4073                                 btrfs_set_file_extent_disk_num_bytes(leaf, fi,
4074                                                 new_extents[i].disk_num_bytes);
4075                                 btrfs_set_file_extent_ram_bytes(leaf, fi,
4076                                                 new_extents[i].ram_bytes);
4077
4078                                 btrfs_set_file_extent_compression(leaf, fi,
4079                                                 new_extents[i].compression);
4080                                 btrfs_set_file_extent_encryption(leaf, fi,
4081                                                 new_extents[i].encryption);
4082                                 btrfs_set_file_extent_other_encoding(leaf, fi,
4083                                                 new_extents[i].other_encoding);
4084
4085                                 btrfs_set_file_extent_num_bytes(leaf, fi,
4086                                                         extent_len);
4087                                 ext_offset += new_extents[i].offset;
4088                                 btrfs_set_file_extent_offset(leaf, fi,
4089                                                         ext_offset);
4090                                 btrfs_mark_buffer_dirty(leaf);
4091
4092                                 btrfs_drop_extent_cache(inode, key.offset,
4093                                                 key.offset + extent_len - 1, 0);
4094
4095                                 ret = btrfs_inc_extent_ref(trans, root,
4096                                                 new_extents[i].disk_bytenr,
4097                                                 new_extents[i].disk_num_bytes,
4098                                                 leaf->start,
4099                                                 root->root_key.objectid,
4100                                                 trans->transid, key.objectid);
4101                                 BUG_ON(ret);
4102                                 btrfs_release_path(root, path);
4103
4104                                 inode_add_bytes(inode, extent_len);
4105
4106                                 ext_offset = 0;
4107                                 num_bytes -= extent_len;
4108                                 key.offset += extent_len;
4109
4110                                 if (num_bytes == 0)
4111                                         break;
4112                         }
4113                         BUG_ON(i >= nr_extents);
4114                 }
4115
4116                 if (extent_locked) {
4117                         mutex_unlock(&BTRFS_I(inode)->extent_mutex);
4118                         unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
4119                                       lock_end, GFP_NOFS);
4120                         extent_locked = 0;
4121                 }
4122 skip:
4123                 if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS &&
4124                     key.offset >= first_pos + extent_key->offset)
4125                         break;
4126
4127                 cond_resched();
4128         }
4129         ret = 0;
4130 out:
4131         btrfs_release_path(root, path);
4132         if (inode) {
4133                 mutex_unlock(&inode->i_mutex);
4134                 if (extent_locked) {
4135                         mutex_unlock(&BTRFS_I(inode)->extent_mutex);
4136                         unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
4137                                       lock_end, GFP_NOFS);
4138                 }
4139                 iput(inode);
4140         }
4141         return ret;
4142 }
4143
4144 int btrfs_reloc_tree_cache_ref(struct btrfs_trans_handle *trans,
4145                                struct btrfs_root *root,
4146                                struct extent_buffer *buf, u64 orig_start)
4147 {
4148         int level;
4149         int ret;
4150
4151         BUG_ON(btrfs_header_generation(buf) != trans->transid);
4152         BUG_ON(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID);
4153
4154         level = btrfs_header_level(buf);
4155         if (level == 0) {
4156                 struct btrfs_leaf_ref *ref;
4157                 struct btrfs_leaf_ref *orig_ref;
4158
4159                 orig_ref = btrfs_lookup_leaf_ref(root, orig_start);
4160                 if (!orig_ref)
4161                         return -ENOENT;
4162
4163                 ref = btrfs_alloc_leaf_ref(root, orig_ref->nritems);
4164                 if (!ref) {
4165                         btrfs_free_leaf_ref(root, orig_ref);
4166                         return -ENOMEM;
4167                 }
4168
4169                 ref->nritems = orig_ref->nritems;
4170                 memcpy(ref->extents, orig_ref->extents,
4171                         sizeof(ref->extents[0]) * ref->nritems);
4172
4173                 btrfs_free_leaf_ref(root, orig_ref);
4174
4175                 ref->root_gen = trans->transid;
4176                 ref->bytenr = buf->start;
4177                 ref->owner = btrfs_header_owner(buf);
4178                 ref->generation = btrfs_header_generation(buf);
4179                 ret = btrfs_add_leaf_ref(root, ref, 0);
4180                 WARN_ON(ret);
4181                 btrfs_free_leaf_ref(root, ref);
4182         }
4183         return 0;
4184 }
4185
4186 static int noinline invalidate_extent_cache(struct btrfs_root *root,
4187                                         struct extent_buffer *leaf,
4188                                         struct btrfs_block_group_cache *group,
4189                                         struct btrfs_root *target_root)
4190 {
4191         struct btrfs_key key;
4192         struct inode *inode = NULL;
4193         struct btrfs_file_extent_item *fi;
4194         u64 num_bytes;
4195         u64 skip_objectid = 0;
4196         u32 nritems;
4197         u32 i;
4198
4199         nritems = btrfs_header_nritems(leaf);
4200         for (i = 0; i < nritems; i++) {
4201                 btrfs_item_key_to_cpu(leaf, &key, i);
4202                 if (key.objectid == skip_objectid ||
4203                     key.type != BTRFS_EXTENT_DATA_KEY)
4204                         continue;
4205                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
4206                 if (btrfs_file_extent_type(leaf, fi) ==
4207                     BTRFS_FILE_EXTENT_INLINE)
4208                         continue;
4209                 if (btrfs_file_extent_disk_bytenr(leaf, fi) == 0)
4210                         continue;
4211                 if (!inode || inode->i_ino != key.objectid) {
4212                         iput(inode);
4213                         inode = btrfs_ilookup(target_root->fs_info->sb,
4214                                               key.objectid, target_root, 1);
4215                 }
4216                 if (!inode) {
4217                         skip_objectid = key.objectid;
4218                         continue;
4219                 }
4220                 num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
4221
4222                 lock_extent(&BTRFS_I(inode)->io_tree, key.offset,
4223                             key.offset + num_bytes - 1, GFP_NOFS);
4224                 mutex_lock(&BTRFS_I(inode)->extent_mutex);
4225                 btrfs_drop_extent_cache(inode, key.offset,
4226                                         key.offset + num_bytes - 1, 1);
4227                 mutex_unlock(&BTRFS_I(inode)->extent_mutex);
4228                 unlock_extent(&BTRFS_I(inode)->io_tree, key.offset,
4229                               key.offset + num_bytes - 1, GFP_NOFS);
4230                 cond_resched();
4231         }
4232         iput(inode);
4233         return 0;
4234 }
4235
4236 static int noinline replace_extents_in_leaf(struct btrfs_trans_handle *trans,
4237                                         struct btrfs_root *root,
4238                                         struct extent_buffer *leaf,
4239                                         struct btrfs_block_group_cache *group,
4240                                         struct inode *reloc_inode)
4241 {
4242         struct btrfs_key key;
4243         struct btrfs_key extent_key;
4244         struct btrfs_file_extent_item *fi;
4245         struct btrfs_leaf_ref *ref;
4246         struct disk_extent *new_extent;
4247         u64 bytenr;
4248         u64 num_bytes;
4249         u32 nritems;
4250         u32 i;
4251         int ext_index;
4252         int nr_extent;
4253         int ret;
4254
4255         new_extent = kmalloc(sizeof(*new_extent), GFP_NOFS);
4256         BUG_ON(!new_extent);
4257
4258         ref = btrfs_lookup_leaf_ref(root, leaf->start);
4259         BUG_ON(!ref);
4260
4261         ext_index = -1;
4262         nritems = btrfs_header_nritems(leaf);
4263         for (i = 0; i < nritems; i++) {
4264                 btrfs_item_key_to_cpu(leaf, &key, i);
4265                 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
4266                         continue;
4267                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
4268                 if (btrfs_file_extent_type(leaf, fi) ==
4269                     BTRFS_FILE_EXTENT_INLINE)
4270                         continue;
4271                 bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
4272                 num_bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
4273                 if (bytenr == 0)
4274                         continue;
4275
4276                 ext_index++;
4277                 if (bytenr >= group->key.objectid + group->key.offset ||
4278                     bytenr + num_bytes <= group->key.objectid)
4279                         continue;
4280
4281                 extent_key.objectid = bytenr;
4282                 extent_key.offset = num_bytes;
4283                 extent_key.type = BTRFS_EXTENT_ITEM_KEY;
4284                 nr_extent = 1;
4285                 ret = get_new_locations(reloc_inode, &extent_key,
4286                                         group->key.objectid, 1,
4287                                         &new_extent, &nr_extent);
4288                 if (ret > 0)
4289                         continue;
4290                 BUG_ON(ret < 0);
4291
4292                 BUG_ON(ref->extents[ext_index].bytenr != bytenr);
4293                 BUG_ON(ref->extents[ext_index].num_bytes != num_bytes);
4294                 ref->extents[ext_index].bytenr = new_extent->disk_bytenr;
4295                 ref->extents[ext_index].num_bytes = new_extent->disk_num_bytes;
4296
4297                 btrfs_set_file_extent_generation(leaf, fi, trans->transid);
4298                 btrfs_set_file_extent_ram_bytes(leaf, fi,
4299                                                 new_extent->ram_bytes);
4300                 btrfs_set_file_extent_disk_bytenr(leaf, fi,
4301                                                 new_extent->disk_bytenr);
4302                 btrfs_set_file_extent_disk_num_bytes(leaf, fi,
4303                                                 new_extent->disk_num_bytes);
4304                 new_extent->offset += btrfs_file_extent_offset(leaf, fi);
4305                 btrfs_set_file_extent_offset(leaf, fi, new_extent->offset);
4306                 btrfs_mark_buffer_dirty(leaf);
4307
4308                 ret = btrfs_inc_extent_ref(trans, root,
4309                                         new_extent->disk_bytenr,
4310                                         new_extent->disk_num_bytes,
4311                                         leaf->start,
4312                                         root->root_key.objectid,
4313                                         trans->transid, key.objectid);
4314                 BUG_ON(ret);
4315                 ret = btrfs_free_extent(trans, root,
4316                                         bytenr, num_bytes, leaf->start,
4317                                         btrfs_header_owner(leaf),
4318                                         btrfs_header_generation(leaf),
4319                                         key.objectid, 0);
4320                 BUG_ON(ret);
4321                 cond_resched();
4322         }
4323         kfree(new_extent);
4324         BUG_ON(ext_index + 1 != ref->nritems);
4325         btrfs_free_leaf_ref(root, ref);
4326         return 0;
4327 }
4328
4329 int btrfs_free_reloc_root(struct btrfs_trans_handle *trans,
4330                           struct btrfs_root *root)
4331 {
4332         struct btrfs_root *reloc_root;
4333         int ret;
4334
4335         if (root->reloc_root) {
4336                 reloc_root = root->reloc_root;
4337                 root->reloc_root = NULL;
4338                 list_add(&reloc_root->dead_list,
4339                          &root->fs_info->dead_reloc_roots);
4340
4341                 btrfs_set_root_bytenr(&reloc_root->root_item,
4342                                       reloc_root->node->start);
4343                 btrfs_set_root_level(&root->root_item,
4344                                      btrfs_header_level(reloc_root->node));
4345                 memset(&reloc_root->root_item.drop_progress, 0,
4346                         sizeof(struct btrfs_disk_key));
4347                 reloc_root->root_item.drop_level = 0;
4348
4349                 ret = btrfs_update_root(trans, root->fs_info->tree_root,
4350                                         &reloc_root->root_key,
4351                                         &reloc_root->root_item);
4352                 BUG_ON(ret);
4353         }
4354         return 0;
4355 }
4356
4357 int btrfs_drop_dead_reloc_roots(struct btrfs_root *root)
4358 {
4359         struct btrfs_trans_handle *trans;
4360         struct btrfs_root *reloc_root;
4361         struct btrfs_root *prev_root = NULL;
4362         struct list_head dead_roots;
4363         int ret;
4364         unsigned long nr;
4365
4366         INIT_LIST_HEAD(&dead_roots);
4367         list_splice_init(&root->fs_info->dead_reloc_roots, &dead_roots);
4368
4369         while (!list_empty(&dead_roots)) {
4370                 reloc_root = list_entry(dead_roots.prev,
4371                                         struct btrfs_root, dead_list);
4372                 list_del_init(&reloc_root->dead_list);
4373
4374                 BUG_ON(reloc_root->commit_root != NULL);
4375                 while (1) {
4376                         trans = btrfs_join_transaction(root, 1);
4377                         BUG_ON(!trans);
4378
4379                         mutex_lock(&root->fs_info->drop_mutex);
4380                         ret = btrfs_drop_snapshot(trans, reloc_root);
4381                         if (ret != -EAGAIN)
4382                                 break;
4383                         mutex_unlock(&root->fs_info->drop_mutex);
4384
4385                         nr = trans->blocks_used;
4386                         ret = btrfs_end_transaction(trans, root);
4387                         BUG_ON(ret);
4388                         btrfs_btree_balance_dirty(root, nr);
4389                 }
4390
4391                 free_extent_buffer(reloc_root->node);
4392
4393                 ret = btrfs_del_root(trans, root->fs_info->tree_root,
4394                                      &reloc_root->root_key);
4395                 BUG_ON(ret);
4396                 mutex_unlock(&root->fs_info->drop_mutex);
4397
4398                 nr = trans->blocks_used;
4399                 ret = btrfs_end_transaction(trans, root);
4400                 BUG_ON(ret);
4401                 btrfs_btree_balance_dirty(root, nr);
4402
4403                 kfree(prev_root);
4404                 prev_root = reloc_root;
4405         }
4406         if (prev_root) {
4407                 btrfs_remove_leaf_refs(prev_root, (u64)-1, 0);
4408                 kfree(prev_root);
4409         }
4410         return 0;
4411 }
4412
4413 int btrfs_add_dead_reloc_root(struct btrfs_root *root)
4414 {
4415         list_add(&root->dead_list, &root->fs_info->dead_reloc_roots);
4416         return 0;
4417 }
4418
4419 int btrfs_cleanup_reloc_trees(struct btrfs_root *root)
4420 {
4421         struct btrfs_root *reloc_root;
4422         struct btrfs_trans_handle *trans;
4423         struct btrfs_key location;
4424         int found;
4425         int ret;
4426
4427         mutex_lock(&root->fs_info->tree_reloc_mutex);
4428         ret = btrfs_find_dead_roots(root, BTRFS_TREE_RELOC_OBJECTID, NULL);
4429         BUG_ON(ret);
4430         found = !list_empty(&root->fs_info->dead_reloc_roots);
4431         mutex_unlock(&root->fs_info->tree_reloc_mutex);
4432
4433         if (found) {
4434                 trans = btrfs_start_transaction(root, 1);
4435                 BUG_ON(!trans);
4436                 ret = btrfs_commit_transaction(trans, root);
4437                 BUG_ON(ret);
4438         }
4439
4440         location.objectid = BTRFS_DATA_RELOC_TREE_OBJECTID;
4441         location.offset = (u64)-1;
4442         location.type = BTRFS_ROOT_ITEM_KEY;
4443
4444         reloc_root = btrfs_read_fs_root_no_name(root->fs_info, &location);
4445         BUG_ON(!reloc_root);
4446         btrfs_orphan_cleanup(reloc_root);
4447         return 0;
4448 }
4449
4450 static int noinline init_reloc_tree(struct btrfs_trans_handle *trans,
4451                                     struct btrfs_root *root)
4452 {
4453         struct btrfs_root *reloc_root;
4454         struct extent_buffer *eb;
4455         struct btrfs_root_item *root_item;
4456         struct btrfs_key root_key;
4457         int ret;
4458
4459         BUG_ON(!root->ref_cows);
4460         if (root->reloc_root)
4461                 return 0;
4462
4463         root_item = kmalloc(sizeof(*root_item), GFP_NOFS);
4464         BUG_ON(!root_item);
4465
4466         ret = btrfs_copy_root(trans, root, root->commit_root,
4467                               &eb, BTRFS_TREE_RELOC_OBJECTID);
4468         BUG_ON(ret);
4469
4470         root_key.objectid = BTRFS_TREE_RELOC_OBJECTID;
4471         root_key.offset = root->root_key.objectid;
4472         root_key.type = BTRFS_ROOT_ITEM_KEY;
4473
4474         memcpy(root_item, &root->root_item, sizeof(root_item));
4475         btrfs_set_root_refs(root_item, 0);
4476         btrfs_set_root_bytenr(root_item, eb->start);
4477         btrfs_set_root_level(root_item, btrfs_header_level(eb));
4478
4479         btrfs_tree_unlock(eb);
4480         free_extent_buffer(eb);
4481
4482         ret = btrfs_insert_root(trans, root->fs_info->tree_root,
4483                                 &root_key, root_item);
4484         BUG_ON(ret);
4485         kfree(root_item);
4486
4487         reloc_root = btrfs_read_fs_root_no_radix(root->fs_info->tree_root,
4488                                                  &root_key);
4489         BUG_ON(!reloc_root);
4490         reloc_root->last_trans = trans->transid;
4491         reloc_root->commit_root = NULL;
4492         reloc_root->ref_tree = &root->fs_info->reloc_ref_tree;
4493
4494         root->reloc_root = reloc_root;
4495         return 0;
4496 }
4497
4498 /*
4499  * Core function of space balance.
4500  *
4501  * The idea is using reloc trees to relocate tree blocks in reference
4502  * counted roots. There is one reloc tree for each subvol, and all
4503  * reloc trees share same root key objectid. Reloc trees are snapshots
4504  * of the latest committed roots of subvols (root->commit_root).
4505  *
4506  * To relocate a tree block referenced by a subvol, there are two steps.
4507  * COW the block through subvol's reloc tree, then update block pointer
4508  * in the subvol to point to the new block. Since all reloc trees share
4509  * same root key objectid, doing special handing for tree blocks owned
4510  * by them is easy. Once a tree block has been COWed in one reloc tree,
4511  * we can use the resulting new block directly when the same block is
4512  * required to COW again through other reloc trees. By this way, relocated
4513  * tree blocks are shared between reloc trees, so they are also shared
4514  * between subvols.
4515  */
4516 static int noinline relocate_one_path(struct btrfs_trans_handle *trans,
4517                                       struct btrfs_root *root,
4518                                       struct btrfs_path *path,
4519                                       struct btrfs_key *first_key,
4520                                       struct btrfs_ref_path *ref_path,
4521                                       struct btrfs_block_group_cache *group,
4522                                       struct inode *reloc_inode)
4523 {
4524         struct btrfs_root *reloc_root;
4525         struct extent_buffer *eb = NULL;
4526         struct btrfs_key *keys;
4527         u64 *nodes;
4528         int level;
4529         int shared_level;
4530         int lowest_level = 0;
4531         int ret;
4532
4533         if (ref_path->owner_objectid < BTRFS_FIRST_FREE_OBJECTID)
4534                 lowest_level = ref_path->owner_objectid;
4535
4536         if (!root->ref_cows) {
4537                 path->lowest_level = lowest_level;
4538                 ret = btrfs_search_slot(trans, root, first_key, path, 0, 1);
4539                 BUG_ON(ret < 0);
4540                 path->lowest_level = 0;
4541                 btrfs_release_path(root, path);
4542                 return 0;
4543         }
4544
4545         mutex_lock(&root->fs_info->tree_reloc_mutex);
4546         ret = init_reloc_tree(trans, root);
4547         BUG_ON(ret);
4548         reloc_root = root->reloc_root;
4549
4550         shared_level = ref_path->shared_level;
4551         ref_path->shared_level = BTRFS_MAX_LEVEL - 1;
4552
4553         keys = ref_path->node_keys;
4554         nodes = ref_path->new_nodes;
4555         memset(&keys[shared_level + 1], 0,
4556                sizeof(*keys) * (BTRFS_MAX_LEVEL - shared_level - 1));
4557         memset(&nodes[shared_level + 1], 0,
4558                sizeof(*nodes) * (BTRFS_MAX_LEVEL - shared_level - 1));
4559
4560         if (nodes[lowest_level] == 0) {
4561                 path->lowest_level = lowest_level;
4562                 ret = btrfs_search_slot(trans, reloc_root, first_key, path,
4563                                         0, 1);
4564                 BUG_ON(ret);
4565                 for (level = lowest_level; level < BTRFS_MAX_LEVEL; level++) {
4566                         eb = path->nodes[level];
4567                         if (!eb || eb == reloc_root->node)
4568                                 break;
4569                         nodes[level] = eb->start;
4570                         if (level == 0)
4571                                 btrfs_item_key_to_cpu(eb, &keys[level], 0);
4572                         else
4573                                 btrfs_node_key_to_cpu(eb, &keys[level], 0);
4574                 }
4575                 if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
4576                         eb = path->nodes[0];
4577                         ret = replace_extents_in_leaf(trans, reloc_root, eb,
4578                                                       group, reloc_inode);
4579                         BUG_ON(ret);
4580                 }
4581                 btrfs_release_path(reloc_root, path);
4582         } else {
4583                 ret = btrfs_merge_path(trans, reloc_root, keys, nodes,
4584                                        lowest_level);
4585                 BUG_ON(ret);
4586         }
4587
4588         /*
4589          * replace tree blocks in the fs tree with tree blocks in
4590          * the reloc tree.
4591          */
4592         ret = btrfs_merge_path(trans, root, keys, nodes, lowest_level);
4593         BUG_ON(ret < 0);
4594
4595         if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
4596                 ret = btrfs_search_slot(trans, reloc_root, first_key, path,
4597                                         0, 0);
4598                 BUG_ON(ret);
4599                 extent_buffer_get(path->nodes[0]);
4600                 eb = path->nodes[0];
4601                 btrfs_release_path(reloc_root, path);
4602                 ret = invalidate_extent_cache(reloc_root, eb, group, root);
4603                 BUG_ON(ret);
4604                 free_extent_buffer(eb);
4605         }
4606
4607         mutex_unlock(&root->fs_info->tree_reloc_mutex);
4608         path->lowest_level = 0;
4609         return 0;
4610 }
4611
4612 static int noinline relocate_tree_block(struct btrfs_trans_handle *trans,
4613                                         struct btrfs_root *root,
4614                                         struct btrfs_path *path,
4615                                         struct btrfs_key *first_key,
4616                                         struct btrfs_ref_path *ref_path)
4617 {
4618         int ret;
4619         int needs_lock = 0;
4620
4621         if (root == root->fs_info->extent_root ||
4622             root == root->fs_info->chunk_root ||
4623             root == root->fs_info->dev_root) {
4624                 needs_lock = 1;
4625                 mutex_lock(&root->fs_info->alloc_mutex);
4626         }
4627
4628         ret = relocate_one_path(trans, root, path, first_key,
4629                                 ref_path, NULL, NULL);
4630         BUG_ON(ret);
4631
4632         if (root == root->fs_info->extent_root)
4633                 btrfs_extent_post_op(trans, root);
4634         if (needs_lock)
4635                 mutex_unlock(&root->fs_info->alloc_mutex);
4636
4637         return 0;
4638 }
4639
4640 static int noinline del_extent_zero(struct btrfs_trans_handle *trans,
4641                                     struct btrfs_root *extent_root,
4642                                     struct btrfs_path *path,
4643                                     struct btrfs_key *extent_key)
4644 {
4645         int ret;
4646
4647         mutex_lock(&extent_root->fs_info->alloc_mutex);
4648         ret = btrfs_search_slot(trans, extent_root, extent_key, path, -1, 1);
4649         if (ret)
4650                 goto out;
4651         ret = btrfs_del_item(trans, extent_root, path);
4652 out:
4653         btrfs_release_path(extent_root, path);
4654         mutex_unlock(&extent_root->fs_info->alloc_mutex);
4655         return ret;
4656 }
4657
4658 static struct btrfs_root noinline *read_ref_root(struct btrfs_fs_info *fs_info,
4659                                                 struct btrfs_ref_path *ref_path)
4660 {
4661         struct btrfs_key root_key;
4662
4663         root_key.objectid = ref_path->root_objectid;
4664         root_key.type = BTRFS_ROOT_ITEM_KEY;
4665         if (is_cowonly_root(ref_path->root_objectid))
4666                 root_key.offset = 0;
4667         else
4668                 root_key.offset = (u64)-1;
4669
4670         return btrfs_read_fs_root_no_name(fs_info, &root_key);
4671 }
4672
4673 static int noinline relocate_one_extent(struct btrfs_root *extent_root,
4674                                         struct btrfs_path *path,
4675                                         struct btrfs_key *extent_key,
4676                                         struct btrfs_block_group_cache *group,
4677                                         struct inode *reloc_inode, int pass)
4678 {
4679         struct btrfs_trans_handle *trans;
4680         struct btrfs_root *found_root;
4681         struct btrfs_ref_path *ref_path = NULL;
4682         struct disk_extent *new_extents = NULL;
4683         int nr_extents = 0;
4684         int loops;
4685         int ret;
4686         int level;
4687         struct btrfs_key first_key;
4688         u64 prev_block = 0;
4689
4690         mutex_unlock(&extent_root->fs_info->alloc_mutex);
4691
4692         trans = btrfs_start_transaction(extent_root, 1);
4693         BUG_ON(!trans);
4694
4695         if (extent_key->objectid == 0) {
4696                 ret = del_extent_zero(trans, extent_root, path, extent_key);
4697                 goto out;
4698         }
4699
4700         ref_path = kmalloc(sizeof(*ref_path), GFP_NOFS);
4701         if (!ref_path) {
4702                ret = -ENOMEM;
4703                goto out;
4704         }
4705
4706         for (loops = 0; ; loops++) {
4707                 if (loops == 0) {
4708                         ret = btrfs_first_ref_path(trans, extent_root, ref_path,
4709                                                    extent_key->objectid);
4710                 } else {
4711                         ret = btrfs_next_ref_path(trans, extent_root, ref_path);
4712                 }
4713                 if (ret < 0)
4714                         goto out;
4715                 if (ret > 0)
4716                         break;
4717
4718                 if (ref_path->root_objectid == BTRFS_TREE_LOG_OBJECTID ||
4719                     ref_path->root_objectid == BTRFS_TREE_RELOC_OBJECTID)
4720                         continue;
4721
4722                 found_root = read_ref_root(extent_root->fs_info, ref_path);
4723                 BUG_ON(!found_root);
4724                 /*
4725                  * for reference counted tree, only process reference paths
4726                  * rooted at the latest committed root.
4727                  */
4728                 if (found_root->ref_cows &&
4729                     ref_path->root_generation != found_root->root_key.offset)
4730                         continue;
4731
4732                 if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
4733                         if (pass == 0) {
4734                                 /*
4735                                  * copy data extents to new locations
4736                                  */
4737                                 u64 group_start = group->key.objectid;
4738                                 ret = relocate_data_extent(reloc_inode,
4739                                                            extent_key,
4740                                                            group_start);
4741                                 if (ret < 0)
4742                                         goto out;
4743                                 break;
4744                         }
4745                         level = 0;
4746                 } else {
4747                         level = ref_path->owner_objectid;
4748                 }
4749
4750                 if (prev_block != ref_path->nodes[level]) {
4751                         struct extent_buffer *eb;
4752                         u64 block_start = ref_path->nodes[level];
4753                         u64 block_size = btrfs_level_size(found_root, level);
4754
4755                         eb = read_tree_block(found_root, block_start,
4756                                              block_size, 0);
4757                         btrfs_tree_lock(eb);
4758                         BUG_ON(level != btrfs_header_level(eb));
4759
4760                         if (level == 0)
4761                                 btrfs_item_key_to_cpu(eb, &first_key, 0);
4762                         else
4763                                 btrfs_node_key_to_cpu(eb, &first_key, 0);
4764
4765                         btrfs_tree_unlock(eb);
4766                         free_extent_buffer(eb);
4767                         prev_block = block_start;
4768                 }
4769
4770                 if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID &&
4771                     pass >= 2) {
4772                         /*
4773                          * use fallback method to process the remaining
4774                          * references.
4775                          */
4776                         if (!new_extents) {
4777                                 u64 group_start = group->key.objectid;
4778                                 ret = get_new_locations(reloc_inode,
4779                                                         extent_key,
4780                                                         group_start, 0,
4781                                                         &new_extents,
4782                                                         &nr_extents);
4783                                 if (ret < 0)
4784                                         goto out;
4785                         }
4786                         btrfs_record_root_in_trans(found_root);
4787                         ret = replace_one_extent(trans, found_root,
4788                                                 path, extent_key,
4789                                                 &first_key, ref_path,
4790                                                 new_extents, nr_extents);
4791                         if (ret < 0)
4792                                 goto out;
4793                         continue;
4794                 }
4795
4796                 btrfs_record_root_in_trans(found_root);
4797                 if (ref_path->owner_objectid < BTRFS_FIRST_FREE_OBJECTID) {
4798                         ret = relocate_tree_block(trans, found_root, path,
4799                                                   &first_key, ref_path);
4800                 } else {
4801                         /*
4802                          * try to update data extent references while
4803                          * keeping metadata shared between snapshots.
4804                          */
4805                         ret = relocate_one_path(trans, found_root, path,
4806                                                 &first_key, ref_path,
4807                                                 group, reloc_inode);
4808                 }
4809                 if (ret < 0)
4810                         goto out;
4811         }
4812         ret = 0;
4813 out:
4814         btrfs_end_transaction(trans, extent_root);
4815         kfree(new_extents);
4816         kfree(ref_path);
4817         mutex_lock(&extent_root->fs_info->alloc_mutex);
4818         return ret;
4819 }
4820
4821 static u64 update_block_group_flags(struct btrfs_root *root, u64 flags)
4822 {
4823         u64 num_devices;
4824         u64 stripped = BTRFS_BLOCK_GROUP_RAID0 |
4825                 BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_RAID10;
4826
4827         num_devices = root->fs_info->fs_devices->num_devices;
4828         if (num_devices == 1) {
4829                 stripped |= BTRFS_BLOCK_GROUP_DUP;
4830                 stripped = flags & ~stripped;
4831
4832                 /* turn raid0 into single device chunks */
4833                 if (flags & BTRFS_BLOCK_GROUP_RAID0)
4834                         return stripped;
4835
4836                 /* turn mirroring into duplication */
4837                 if (flags & (BTRFS_BLOCK_GROUP_RAID1 |
4838                              BTRFS_BLOCK_GROUP_RAID10))
4839                         return stripped | BTRFS_BLOCK_GROUP_DUP;
4840                 return flags;
4841         } else {
4842                 /* they already had raid on here, just return */
4843                 if (flags & stripped)
4844                         return flags;
4845
4846                 stripped |= BTRFS_BLOCK_GROUP_DUP;
4847                 stripped = flags & ~stripped;
4848
4849                 /* switch duplicated blocks with raid1 */
4850                 if (flags & BTRFS_BLOCK_GROUP_DUP)
4851                         return stripped | BTRFS_BLOCK_GROUP_RAID1;
4852
4853                 /* turn single device chunks into raid0 */
4854                 return stripped | BTRFS_BLOCK_GROUP_RAID0;
4855         }
4856         return flags;
4857 }
4858
4859 int __alloc_chunk_for_shrink(struct btrfs_root *root,
4860                      struct btrfs_block_group_cache *shrink_block_group,
4861                      int force)
4862 {
4863         struct btrfs_trans_handle *trans;
4864         u64 new_alloc_flags;
4865         u64 calc;
4866
4867         spin_lock(&shrink_block_group->lock);
4868         if (btrfs_block_group_used(&shrink_block_group->item) > 0) {
4869                 spin_unlock(&shrink_block_group->lock);
4870                 mutex_unlock(&root->fs_info->alloc_mutex);
4871
4872                 trans = btrfs_start_transaction(root, 1);
4873                 mutex_lock(&root->fs_info->alloc_mutex);
4874                 spin_lock(&shrink_block_group->lock);
4875
4876                 new_alloc_flags = update_block_group_flags(root,
4877                                                    shrink_block_group->flags);
4878                 if (new_alloc_flags != shrink_block_group->flags) {
4879                         calc =
4880                              btrfs_block_group_used(&shrink_block_group->item);
4881                 } else {
4882                         calc = shrink_block_group->key.offset;
4883                 }
4884                 spin_unlock(&shrink_block_group->lock);
4885
4886                 do_chunk_alloc(trans, root->fs_info->extent_root,
4887                                calc + 2 * 1024 * 1024, new_alloc_flags, force);
4888
4889                 mutex_unlock(&root->fs_info->alloc_mutex);
4890                 btrfs_end_transaction(trans, root);
4891                 mutex_lock(&root->fs_info->alloc_mutex);
4892         } else
4893                 spin_unlock(&shrink_block_group->lock);
4894         return 0;
4895 }
4896
4897 static int __insert_orphan_inode(struct btrfs_trans_handle *trans,
4898                                  struct btrfs_root *root,
4899                                  u64 objectid, u64 size)
4900 {
4901         struct btrfs_path *path;
4902         struct btrfs_inode_item *item;
4903         struct extent_buffer *leaf;
4904         int ret;
4905
4906         path = btrfs_alloc_path();
4907         if (!path)
4908                 return -ENOMEM;
4909
4910         ret = btrfs_insert_empty_inode(trans, root, path, objectid);
4911         if (ret)
4912                 goto out;
4913
4914         leaf = path->nodes[0];
4915         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_inode_item);
4916         memset_extent_buffer(leaf, 0, (unsigned long)item, sizeof(*item));
4917         btrfs_set_inode_generation(leaf, item, 1);
4918         btrfs_set_inode_size(leaf, item, size);
4919         btrfs_set_inode_mode(leaf, item, S_IFREG | 0600);
4920         btrfs_set_inode_flags(leaf, item, BTRFS_INODE_NODATASUM);
4921         btrfs_mark_buffer_dirty(leaf);
4922         btrfs_release_path(root, path);
4923 out:
4924         btrfs_free_path(path);
4925         return ret;
4926 }
4927
4928 static struct inode noinline *create_reloc_inode(struct btrfs_fs_info *fs_info,
4929                                         struct btrfs_block_group_cache *group)
4930 {
4931         struct inode *inode = NULL;
4932         struct btrfs_trans_handle *trans;
4933         struct btrfs_root *root;
4934         struct btrfs_key root_key;
4935         u64 objectid = BTRFS_FIRST_FREE_OBJECTID;
4936         int err = 0;
4937
4938         root_key.objectid = BTRFS_DATA_RELOC_TREE_OBJECTID;
4939         root_key.type = BTRFS_ROOT_ITEM_KEY;
4940         root_key.offset = (u64)-1;
4941         root = btrfs_read_fs_root_no_name(fs_info, &root_key);
4942         if (IS_ERR(root))
4943                 return ERR_CAST(root);
4944
4945         trans = btrfs_start_transaction(root, 1);
4946         BUG_ON(!trans);
4947
4948         err = btrfs_find_free_objectid(trans, root, objectid, &objectid);
4949         if (err)
4950                 goto out;
4951
4952         err = __insert_orphan_inode(trans, root, objectid, group->key.offset);
4953         BUG_ON(err);
4954
4955         err = btrfs_insert_file_extent(trans, root, objectid, 0, 0, 0,
4956                                        group->key.offset, 0, group->key.offset,
4957                                        0, 0, 0);
4958         BUG_ON(err);
4959
4960         inode = btrfs_iget_locked(root->fs_info->sb, objectid, root);
4961         if (inode->i_state & I_NEW) {
4962                 BTRFS_I(inode)->root = root;
4963                 BTRFS_I(inode)->location.objectid = objectid;
4964                 BTRFS_I(inode)->location.type = BTRFS_INODE_ITEM_KEY;
4965                 BTRFS_I(inode)->location.offset = 0;
4966                 btrfs_read_locked_inode(inode);
4967                 unlock_new_inode(inode);
4968                 BUG_ON(is_bad_inode(inode));
4969         } else {
4970                 BUG_ON(1);
4971         }
4972
4973         err = btrfs_orphan_add(trans, inode);
4974 out:
4975         btrfs_end_transaction(trans, root);
4976         if (err) {
4977                 if (inode)
4978                         iput(inode);
4979                 inode = ERR_PTR(err);
4980         }
4981         return inode;
4982 }
4983
4984 int btrfs_relocate_block_group(struct btrfs_root *root, u64 group_start)
4985 {
4986         struct btrfs_trans_handle *trans;
4987         struct btrfs_path *path;
4988         struct btrfs_fs_info *info = root->fs_info;
4989         struct extent_buffer *leaf;
4990         struct inode *reloc_inode;
4991         struct btrfs_block_group_cache *block_group;
4992         struct btrfs_key key;
4993         u64 cur_byte;
4994         u64 total_found;
4995         u32 nritems;
4996         int ret;
4997         int progress;
4998         int pass = 0;
4999
5000         root = root->fs_info->extent_root;
5001
5002         block_group = btrfs_lookup_block_group(info, group_start);
5003         BUG_ON(!block_group);
5004
5005         printk("btrfs relocating block group %llu flags %llu\n",
5006                (unsigned long long)block_group->key.objectid,
5007                (unsigned long long)block_group->flags);
5008
5009         path = btrfs_alloc_path();
5010         BUG_ON(!path);
5011
5012         reloc_inode = create_reloc_inode(info, block_group);
5013         BUG_ON(IS_ERR(reloc_inode));
5014
5015         mutex_lock(&root->fs_info->alloc_mutex);
5016
5017         __alloc_chunk_for_shrink(root, block_group, 1);
5018         block_group->ro = 1;
5019         block_group->space_info->total_bytes -= block_group->key.offset;
5020
5021         mutex_unlock(&root->fs_info->alloc_mutex);
5022
5023         btrfs_start_delalloc_inodes(info->tree_root);
5024         btrfs_wait_ordered_extents(info->tree_root, 0);
5025 again:
5026         total_found = 0;
5027         progress = 0;
5028         key.objectid = block_group->key.objectid;
5029         key.offset = 0;
5030         key.type = 0;
5031         cur_byte = key.objectid;
5032
5033         trans = btrfs_start_transaction(info->tree_root, 1);
5034         btrfs_commit_transaction(trans, info->tree_root);
5035
5036         mutex_lock(&root->fs_info->cleaner_mutex);
5037         btrfs_clean_old_snapshots(info->tree_root);
5038         btrfs_remove_leaf_refs(info->tree_root, (u64)-1, 1);
5039         mutex_unlock(&root->fs_info->cleaner_mutex);
5040
5041         mutex_lock(&root->fs_info->alloc_mutex);
5042
5043         while(1) {
5044                 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
5045                 if (ret < 0)
5046                         goto out;
5047 next:
5048                 leaf = path->nodes[0];
5049                 nritems = btrfs_header_nritems(leaf);
5050                 if (path->slots[0] >= nritems) {
5051                         ret = btrfs_next_leaf(root, path);
5052                         if (ret < 0)
5053                                 goto out;
5054                         if (ret == 1) {
5055                                 ret = 0;
5056                                 break;
5057                         }
5058                         leaf = path->nodes[0];
5059                         nritems = btrfs_header_nritems(leaf);
5060                 }
5061
5062                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
5063
5064                 if (key.objectid >= block_group->key.objectid +
5065                     block_group->key.offset)
5066                         break;
5067
5068                 if (progress && need_resched()) {
5069                         btrfs_release_path(root, path);
5070                         mutex_unlock(&root->fs_info->alloc_mutex);
5071                         cond_resched();
5072                         mutex_lock(&root->fs_info->alloc_mutex);
5073                         progress = 0;
5074                         continue;
5075                 }
5076                 progress = 1;
5077
5078                 if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY ||
5079                     key.objectid + key.offset <= cur_byte) {
5080                         path->slots[0]++;
5081                         goto next;
5082                 }
5083
5084                 total_found++;
5085                 cur_byte = key.objectid + key.offset;
5086                 btrfs_release_path(root, path);
5087
5088                 __alloc_chunk_for_shrink(root, block_group, 0);
5089                 ret = relocate_one_extent(root, path, &key, block_group,
5090                                           reloc_inode, pass);
5091                 BUG_ON(ret < 0);
5092
5093                 key.objectid = cur_byte;
5094                 key.type = 0;
5095                 key.offset = 0;
5096         }
5097
5098         btrfs_release_path(root, path);
5099         mutex_unlock(&root->fs_info->alloc_mutex);
5100
5101         if (pass == 0) {
5102                 btrfs_wait_ordered_range(reloc_inode, 0, (u64)-1);
5103                 invalidate_mapping_pages(reloc_inode->i_mapping, 0, -1);
5104                 WARN_ON(reloc_inode->i_mapping->nrpages);
5105         }
5106
5107         if (total_found > 0) {
5108                 printk("btrfs found %llu extents in pass %d\n",
5109                        (unsigned long long)total_found, pass);
5110                 pass++;
5111                 goto again;
5112         }
5113
5114         /* delete reloc_inode */
5115         iput(reloc_inode);
5116
5117         /* unpin extents in this range */
5118         trans = btrfs_start_transaction(info->tree_root, 1);
5119         btrfs_commit_transaction(trans, info->tree_root);
5120
5121         mutex_lock(&root->fs_info->alloc_mutex);
5122
5123         spin_lock(&block_group->lock);
5124         WARN_ON(block_group->pinned > 0);
5125         WARN_ON(block_group->reserved > 0);
5126         WARN_ON(btrfs_block_group_used(&block_group->item) > 0);
5127         spin_unlock(&block_group->lock);
5128         ret = 0;
5129 out:
5130         mutex_unlock(&root->fs_info->alloc_mutex);
5131         btrfs_free_path(path);
5132         return ret;
5133 }
5134
5135 int find_first_block_group(struct btrfs_root *root, struct btrfs_path *path,
5136                            struct btrfs_key *key)
5137 {
5138         int ret = 0;
5139         struct btrfs_key found_key;
5140         struct extent_buffer *leaf;
5141         int slot;
5142
5143         ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
5144         if (ret < 0)
5145                 goto out;
5146
5147         while(1) {
5148                 slot = path->slots[0];
5149                 leaf = path->nodes[0];
5150                 if (slot >= btrfs_header_nritems(leaf)) {
5151                         ret = btrfs_next_leaf(root, path);
5152                         if (ret == 0)
5153                                 continue;
5154                         if (ret < 0)
5155                                 goto out;
5156                         break;
5157                 }
5158                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
5159
5160                 if (found_key.objectid >= key->objectid &&
5161                     found_key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
5162                         ret = 0;
5163                         goto out;
5164                 }
5165                 path->slots[0]++;
5166         }
5167         ret = -ENOENT;
5168 out:
5169         return ret;
5170 }
5171
5172 int btrfs_free_block_groups(struct btrfs_fs_info *info)
5173 {
5174         struct btrfs_block_group_cache *block_group;
5175         struct rb_node *n;
5176
5177         mutex_lock(&info->alloc_mutex);
5178         spin_lock(&info->block_group_cache_lock);
5179         while ((n = rb_last(&info->block_group_cache_tree)) != NULL) {
5180                 block_group = rb_entry(n, struct btrfs_block_group_cache,
5181                                        cache_node);
5182
5183                 spin_unlock(&info->block_group_cache_lock);
5184                 btrfs_remove_free_space_cache(block_group);
5185                 spin_lock(&info->block_group_cache_lock);
5186
5187                 rb_erase(&block_group->cache_node,
5188                          &info->block_group_cache_tree);
5189                 spin_lock(&block_group->space_info->lock);
5190                 list_del(&block_group->list);
5191                 spin_unlock(&block_group->space_info->lock);
5192                 kfree(block_group);
5193         }
5194         spin_unlock(&info->block_group_cache_lock);
5195         mutex_unlock(&info->alloc_mutex);
5196         return 0;
5197 }
5198
5199 int btrfs_read_block_groups(struct btrfs_root *root)
5200 {
5201         struct btrfs_path *path;
5202         int ret;
5203         struct btrfs_block_group_cache *cache;
5204         struct btrfs_fs_info *info = root->fs_info;
5205         struct btrfs_space_info *space_info;
5206         struct btrfs_key key;
5207         struct btrfs_key found_key;
5208         struct extent_buffer *leaf;
5209
5210         root = info->extent_root;
5211         key.objectid = 0;
5212         key.offset = 0;
5213         btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
5214         path = btrfs_alloc_path();
5215         if (!path)
5216                 return -ENOMEM;
5217
5218         mutex_lock(&root->fs_info->alloc_mutex);
5219         while(1) {
5220                 ret = find_first_block_group(root, path, &key);
5221                 if (ret > 0) {
5222                         ret = 0;
5223                         goto error;
5224                 }
5225                 if (ret != 0)
5226                         goto error;
5227
5228                 leaf = path->nodes[0];
5229                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5230                 cache = kzalloc(sizeof(*cache), GFP_NOFS);
5231                 if (!cache) {
5232                         ret = -ENOMEM;
5233                         break;
5234                 }
5235
5236                 spin_lock_init(&cache->lock);
5237                 INIT_LIST_HEAD(&cache->list);
5238                 read_extent_buffer(leaf, &cache->item,
5239                                    btrfs_item_ptr_offset(leaf, path->slots[0]),
5240                                    sizeof(cache->item));
5241                 memcpy(&cache->key, &found_key, sizeof(found_key));
5242
5243                 key.objectid = found_key.objectid + found_key.offset;
5244                 btrfs_release_path(root, path);
5245                 cache->flags = btrfs_block_group_flags(&cache->item);
5246
5247                 ret = update_space_info(info, cache->flags, found_key.offset,
5248                                         btrfs_block_group_used(&cache->item),
5249                                         &space_info);
5250                 BUG_ON(ret);
5251                 cache->space_info = space_info;
5252                 spin_lock(&space_info->lock);
5253                 list_add(&cache->list, &space_info->block_groups);
5254                 spin_unlock(&space_info->lock);
5255
5256                 ret = btrfs_add_block_group_cache(root->fs_info, cache);
5257                 BUG_ON(ret);
5258
5259                 set_avail_alloc_bits(root->fs_info, cache->flags);
5260         }
5261         ret = 0;
5262 error:
5263         btrfs_free_path(path);
5264         mutex_unlock(&root->fs_info->alloc_mutex);
5265         return ret;
5266 }
5267
5268 int btrfs_make_block_group(struct btrfs_trans_handle *trans,
5269                            struct btrfs_root *root, u64 bytes_used,
5270                            u64 type, u64 chunk_objectid, u64 chunk_offset,
5271                            u64 size)
5272 {
5273         int ret;
5274         struct btrfs_root *extent_root;
5275         struct btrfs_block_group_cache *cache;
5276
5277         WARN_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
5278         extent_root = root->fs_info->extent_root;
5279
5280         root->fs_info->last_trans_new_blockgroup = trans->transid;
5281
5282         cache = kzalloc(sizeof(*cache), GFP_NOFS);
5283         if (!cache)
5284                 return -ENOMEM;
5285
5286         cache->key.objectid = chunk_offset;
5287         cache->key.offset = size;
5288         spin_lock_init(&cache->lock);
5289         INIT_LIST_HEAD(&cache->list);
5290         btrfs_set_key_type(&cache->key, BTRFS_BLOCK_GROUP_ITEM_KEY);
5291
5292         btrfs_set_block_group_used(&cache->item, bytes_used);
5293         btrfs_set_block_group_chunk_objectid(&cache->item, chunk_objectid);
5294         cache->flags = type;
5295         btrfs_set_block_group_flags(&cache->item, type);
5296
5297         ret = update_space_info(root->fs_info, cache->flags, size, bytes_used,
5298                                 &cache->space_info);
5299         BUG_ON(ret);
5300         spin_lock(&cache->space_info->lock);
5301         list_add(&cache->list, &cache->space_info->block_groups);
5302         spin_unlock(&cache->space_info->lock);
5303
5304         ret = btrfs_add_block_group_cache(root->fs_info, cache);
5305         BUG_ON(ret);
5306
5307         ret = btrfs_insert_item(trans, extent_root, &cache->key, &cache->item,
5308                                 sizeof(cache->item));
5309         BUG_ON(ret);
5310
5311         finish_current_insert(trans, extent_root);
5312         ret = del_pending_extents(trans, extent_root);
5313         BUG_ON(ret);
5314         set_avail_alloc_bits(extent_root->fs_info, type);
5315
5316         return 0;
5317 }
5318
5319 int btrfs_remove_block_group(struct btrfs_trans_handle *trans,
5320                              struct btrfs_root *root, u64 group_start)
5321 {
5322         struct btrfs_path *path;
5323         struct btrfs_block_group_cache *block_group;
5324         struct btrfs_key key;
5325         int ret;
5326
5327         BUG_ON(!mutex_is_locked(&root->fs_info->alloc_mutex));
5328         root = root->fs_info->extent_root;
5329
5330         block_group = btrfs_lookup_block_group(root->fs_info, group_start);
5331         BUG_ON(!block_group);
5332
5333         memcpy(&key, &block_group->key, sizeof(key));
5334
5335         path = btrfs_alloc_path();
5336         BUG_ON(!path);
5337
5338         btrfs_remove_free_space_cache(block_group);
5339         rb_erase(&block_group->cache_node,
5340                  &root->fs_info->block_group_cache_tree);
5341         spin_lock(&block_group->space_info->lock);
5342         list_del(&block_group->list);
5343         spin_unlock(&block_group->space_info->lock);
5344
5345         /*
5346         memset(shrink_block_group, 0, sizeof(*shrink_block_group));
5347         kfree(shrink_block_group);
5348         */
5349
5350         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
5351         if (ret > 0)
5352                 ret = -EIO;
5353         if (ret < 0)
5354                 goto out;
5355
5356         ret = btrfs_del_item(trans, root, path);
5357 out:
5358         btrfs_free_path(path);
5359         return ret;
5360 }