git.oblomov.eu Git - linux-2.6/blob - 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 <linux/sort.h>
  23 #include <linux/rcupdate.h>
  24 #include "compat.h"
  25 #include "hash.h"
  26 #include "crc32c.h"
  27 #include "ctree.h"
  28 #include "disk-io.h"
  29 #include "print-tree.h"
  30 #include "transaction.h"
  31 #include "volumes.h"
  32 #include "locking.h"
  33 #include "free-space-cache.h"
  34
  35 static int update_reserved_extents(struct btrfs_root *root,
  36                                    u64 bytenr, u64 num, int reserve);
  37 static int update_block_group(struct btrfs_trans_handle *trans,
  38                               struct btrfs_root *root,
  39                               u64 bytenr, u64 num_bytes, int alloc,
  40                               int mark_free);
  41 static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
  42                                 struct btrfs_root *root,
  43                                 u64 bytenr, u64 num_bytes, u64 parent,
  44                                 u64 root_objectid, u64 owner_objectid,
  45                                 u64 owner_offset, int refs_to_drop,
  46                                 struct btrfs_delayed_extent_op *extra_op);
  47 static void __run_delayed_extent_op(struct btrfs_delayed_extent_op *extent_op,
  48                                     struct extent_buffer *leaf,
  49                                     struct btrfs_extent_item *ei);
  50 static int alloc_reserved_file_extent(struct btrfs_trans_handle *trans,
  51                                       struct btrfs_root *root,
  52                                       u64 parent, u64 root_objectid,
  53                                       u64 flags, u64 owner, u64 offset,
  54                                       struct btrfs_key *ins, int ref_mod);
  55 static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
  56                                      struct btrfs_root *root,
  57                                      u64 parent, u64 root_objectid,
  58                                      u64 flags, struct btrfs_disk_key *key,
  59                                      int level, struct btrfs_key *ins);
  60
  61 static int do_chunk_alloc(struct btrfs_trans_handle *trans,
  62                           struct btrfs_root *extent_root, u64 alloc_bytes,
  63                           u64 flags, int force);
  64
  65 static int block_group_bits(struct btrfs_block_group_cache *cache, u64 bits)
  66 {
  67         return (cache->flags & bits) == bits;
  68 }
  69
  70 /*
  71  * this adds the block group to the fs_info rb tree for the block group
  72  * cache
  73  */
  74 static int btrfs_add_block_group_cache(struct btrfs_fs_info *info,
  75                                 struct btrfs_block_group_cache *block_group)
  76 {
  77         struct rb_node **p;
  78         struct rb_node *parent = NULL;
  79         struct btrfs_block_group_cache *cache;
  80
  81         spin_lock(&info->block_group_cache_lock);
  82         p = &info->block_group_cache_tree.rb_node;
  83
  84         while (*p) {
  85                 parent = *p;
  86                 cache = rb_entry(parent, struct btrfs_block_group_cache,
  87                                  cache_node);
  88                 if (block_group->key.objectid < cache->key.objectid) {
  89                         p = &(*p)->rb_left;
  90                 } else if (block_group->key.objectid > cache->key.objectid) {
  91                         p = &(*p)->rb_right;
  92                 } else {
  93                         spin_unlock(&info->block_group_cache_lock);
  94                         return -EEXIST;
  95                 }
  96         }
  97
  98         rb_link_node(&block_group->cache_node, parent, p);
  99         rb_insert_color(&block_group->cache_node,
 100                         &info->block_group_cache_tree);
 101         spin_unlock(&info->block_group_cache_lock);
 102
 103         return 0;
 104 }
 105
 106 /*
 107  * This will return the block group at or after bytenr if contains is 0, else
 108  * it will return the block group that contains the bytenr
 109  */
 110 static struct btrfs_block_group_cache *
 111 block_group_cache_tree_search(struct btrfs_fs_info *info, u64 bytenr,
 112                               int contains)
 113 {
 114         struct btrfs_block_group_cache *cache, *ret = NULL;
 115         struct rb_node *n;
 116         u64 end, start;
 117
 118         spin_lock(&info->block_group_cache_lock);
 119         n = info->block_group_cache_tree.rb_node;
 120
 121         while (n) {
 122                 cache = rb_entry(n, struct btrfs_block_group_cache,
 123                                  cache_node);
 124                 end = cache->key.objectid + cache->key.offset - 1;
 125                 start = cache->key.objectid;
 126
 127                 if (bytenr < start) {
 128                         if (!contains && (!ret || start < ret->key.objectid))
 129                                 ret = cache;
 130                         n = n->rb_left;
 131                 } else if (bytenr > start) {
 132                         if (contains && bytenr <= end) {
 133                                 ret = cache;
 134                                 break;
 135                         }
 136                         n = n->rb_right;
 137                 } else {
 138                         ret = cache;
 139                         break;
 140                 }
 141         }
 142         if (ret)
 143                 atomic_inc(&ret->count);
 144         spin_unlock(&info->block_group_cache_lock);
 145
 146         return ret;
 147 }
 148
 149 /*
 150  * this is only called by cache_block_group, since we could have freed extents
 151  * we need to check the pinned_extents for any extents that can't be used yet
 152  * since their free space will be released as soon as the transaction commits.
 153  */
 154 static int add_new_free_space(struct btrfs_block_group_cache *block_group,
 155                               struct btrfs_fs_info *info, u64 start, u64 end)
 156 {
 157         u64 extent_start, extent_end, size;
 158         int ret;
 159
 160         while (start < end) {
 161                 ret = find_first_extent_bit(&info->pinned_extents, start,
 162                                             &extent_start, &extent_end,
 163                                             EXTENT_DIRTY);
 164                 if (ret)
 165                         break;
 166
 167                 if (extent_start == start) {
 168                         start = extent_end + 1;
 169                 } else if (extent_start > start && extent_start < end) {
 170                         size = extent_start - start;
 171                         ret = btrfs_add_free_space(block_group, start,
 172                                                    size);
 173                         BUG_ON(ret);
 174                         start = extent_end + 1;
 175                 } else {
 176                         break;
 177                 }
 178         }
 179
 180         if (start < end) {
 181                 size = end - start;
 182                 ret = btrfs_add_free_space(block_group, start, size);
 183                 BUG_ON(ret);
 184         }
 185
 186         return 0;
 187 }
 188
 189 static int remove_sb_from_cache(struct btrfs_root *root,
 190                                 struct btrfs_block_group_cache *cache)
 191 {
 192         u64 bytenr;
 193         u64 *logical;
 194         int stripe_len;
 195         int i, nr, ret;
 196
 197         for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
 198                 bytenr = btrfs_sb_offset(i);
 199                 ret = btrfs_rmap_block(&root->fs_info->mapping_tree,
 200                                        cache->key.objectid, bytenr, 0,
 201                                        &logical, &nr, &stripe_len);
 202                 BUG_ON(ret);
 203                 while (nr--) {
 204                         btrfs_remove_free_space(cache, logical[nr],
 205                                                 stripe_len);
 206                 }
 207                 kfree(logical);
 208         }
 209         return 0;
 210 }
 211
 212 static int cache_block_group(struct btrfs_root *root,
 213                              struct btrfs_block_group_cache *block_group)
 214 {
 215         struct btrfs_path *path;
 216         int ret = 0;
 217         struct btrfs_key key;
 218         struct extent_buffer *leaf;
 219         int slot;
 220         u64 last;
 221
 222         if (!block_group)
 223                 return 0;
 224
 225         root = root->fs_info->extent_root;
 226
 227         if (block_group->cached)
 228                 return 0;
 229
 230         path = btrfs_alloc_path();
 231         if (!path)
 232                 return -ENOMEM;
 233
 234         path->reada = 2;
 235         /*
 236          * we get into deadlocks with paths held by callers of this function.
 237          * since the alloc_mutex is protecting things right now, just
 238          * skip the locking here
 239          */
 240         path->skip_locking = 1;
 241         last = max_t(u64, block_group->key.objectid, BTRFS_SUPER_INFO_OFFSET);
 242         key.objectid = last;
 243         key.offset = 0;
 244         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 245         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 246         if (ret < 0)
 247                 goto err;
 248
 249         while (1) {
 250                 leaf = path->nodes[0];
 251                 slot = path->slots[0];
 252                 if (slot >= btrfs_header_nritems(leaf)) {
 253                         ret = btrfs_next_leaf(root, path);
 254                         if (ret < 0)
 255                                 goto err;
 256                         if (ret == 0)
 257                                 continue;
 258                         else
 259                                 break;
 260                 }
 261                 btrfs_item_key_to_cpu(leaf, &key, slot);
 262                 if (key.objectid < block_group->key.objectid)
 263                         goto next;
 264
 265                 if (key.objectid >= block_group->key.objectid +
 266                     block_group->key.offset)
 267                         break;
 268
 269                 if (btrfs_key_type(&key) == BTRFS_EXTENT_ITEM_KEY) {
 270                         add_new_free_space(block_group, root->fs_info, last,
 271                                            key.objectid);
 272
 273                         last = key.objectid + key.offset;
 274                 }
 275 next:
 276                 path->slots[0]++;
 277         }
 278
 279         add_new_free_space(block_group, root->fs_info, last,
 280                            block_group->key.objectid +
 281                            block_group->key.offset);
 282
 283         block_group->cached = 1;
 284         remove_sb_from_cache(root, block_group);
 285         ret = 0;
 286 err:
 287         btrfs_free_path(path);
 288         return ret;
 289 }
 290
 291 /*
 292  * return the block group that starts at or after bytenr
 293  */
 294 static struct btrfs_block_group_cache *
 295 btrfs_lookup_first_block_group(struct btrfs_fs_info *info, u64 bytenr)
 296 {
 297         struct btrfs_block_group_cache *cache;
 298
 299         cache = block_group_cache_tree_search(info, bytenr, 0);
 300
 301         return cache;
 302 }
 303
 304 /*
 305  * return the block group that contains the given bytenr
 306  */
 307 struct btrfs_block_group_cache *btrfs_lookup_block_group(
 308                                                  struct btrfs_fs_info *info,
 309                                                  u64 bytenr)
 310 {
 311         struct btrfs_block_group_cache *cache;
 312
 313         cache = block_group_cache_tree_search(info, bytenr, 1);
 314
 315         return cache;
 316 }
 317
 318 void btrfs_put_block_group(struct btrfs_block_group_cache *cache)
 319 {
 320         if (atomic_dec_and_test(&cache->count))
 321                 kfree(cache);
 322 }
 323
 324 static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
 325                                                   u64 flags)
 326 {
 327         struct list_head *head = &info->space_info;
 328         struct btrfs_space_info *found;
 329
 330         rcu_read_lock();
 331         list_for_each_entry_rcu(found, head, list) {
 332                 if (found->flags == flags) {
 333                         rcu_read_unlock();
 334                         return found;
 335                 }
 336         }
 337         rcu_read_unlock();
 338         return NULL;
 339 }
 340
 341 /*
 342  * after adding space to the filesystem, we need to clear the full flags
 343  * on all the space infos.
 344  */
 345 void btrfs_clear_space_info_full(struct btrfs_fs_info *info)
 346 {
 347         struct list_head *head = &info->space_info;
 348         struct btrfs_space_info *found;
 349
 350         rcu_read_lock();
 351         list_for_each_entry_rcu(found, head, list)
 352                 found->full = 0;
 353         rcu_read_unlock();
 354 }
 355
 356 static u64 div_factor(u64 num, int factor)
 357 {
 358         if (factor == 10)
 359                 return num;
 360         num *= factor;
 361         do_div(num, 10);
 362         return num;
 363 }
 364
 365 u64 btrfs_find_block_group(struct btrfs_root *root,
 366                            u64 search_start, u64 search_hint, int owner)
 367 {
 368         struct btrfs_block_group_cache *cache;
 369         u64 used;
 370         u64 last = max(search_hint, search_start);
 371         u64 group_start = 0;
 372         int full_search = 0;
 373         int factor = 9;
 374         int wrapped = 0;
 375 again:
 376         while (1) {
 377                 cache = btrfs_lookup_first_block_group(root->fs_info, last);
 378                 if (!cache)
 379                         break;
 380
 381                 spin_lock(&cache->lock);
 382                 last = cache->key.objectid + cache->key.offset;
 383                 used = btrfs_block_group_used(&cache->item);
 384
 385                 if ((full_search || !cache->ro) &&
 386                     block_group_bits(cache, BTRFS_BLOCK_GROUP_METADATA)) {
 387                         if (used + cache->pinned + cache->reserved <
 388                             div_factor(cache->key.offset, factor)) {
 389                                 group_start = cache->key.objectid;
 390                                 spin_unlock(&cache->lock);
 391                                 btrfs_put_block_group(cache);
 392                                 goto found;
 393                         }
 394                 }
 395                 spin_unlock(&cache->lock);
 396                 btrfs_put_block_group(cache);
 397                 cond_resched();
 398         }
 399         if (!wrapped) {
 400                 last = search_start;
 401                 wrapped = 1;
 402                 goto again;
 403         }
 404         if (!full_search && factor < 10) {
 405                 last = search_start;
 406                 full_search = 1;
 407                 factor = 10;
 408                 goto again;
 409         }
 410 found:
 411         return group_start;
 412 }
 413
 414 /* simple helper to search for an existing extent at a given offset */
 415 int btrfs_lookup_extent(struct btrfs_root *root, u64 start, u64 len)
 416 {
 417         int ret;
 418         struct btrfs_key key;
 419         struct btrfs_path *path;
 420
 421         path = btrfs_alloc_path();
 422         BUG_ON(!path);
 423         key.objectid = start;
 424         key.offset = len;
 425         btrfs_set_key_type(&key, BTRFS_EXTENT_ITEM_KEY);
 426         ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, path,
 427                                 0, 0);
 428         btrfs_free_path(path);
 429         return ret;
 430 }
 431
 432 /*
 433  * Back reference rules.  Back refs have three main goals:
 434  *
 435  * 1) differentiate between all holders of references to an extent so that
 436  *    when a reference is dropped we can make sure it was a valid reference
 437  *    before freeing the extent.
 438  *
 439  * 2) Provide enough information to quickly find the holders of an extent
 440  *    if we notice a given block is corrupted or bad.
 441  *
 442  * 3) Make it easy to migrate blocks for FS shrinking or storage pool
 443  *    maintenance.  This is actually the same as #2, but with a slightly
 444  *    different use case.
 445  *
 446  * There are two kinds of back refs. The implicit back refs is optimized
 447  * for pointers in non-shared tree blocks. For a given pointer in a block,
 448  * back refs of this kind provide information about the block's owner tree
 449  * and the pointer's key. These information allow us to find the block by
 450  * b-tree searching. The full back refs is for pointers in tree blocks not
 451  * referenced by their owner trees. The location of tree block is recorded
 452  * in the back refs. Actually the full back refs is generic, and can be
 453  * used in all cases the implicit back refs is used. The major shortcoming
 454  * of the full back refs is its overhead. Every time a tree block gets
 455  * COWed, we have to update back refs entry for all pointers in it.
 456  *
 457  * For a newly allocated tree block, we use implicit back refs for
 458  * pointers in it. This means most tree related operations only involve
 459  * implicit back refs. For a tree block created in old transaction, the
 460  * only way to drop a reference to it is COW it. So we can detect the
 461  * event that tree block loses its owner tree's reference and do the
 462  * back refs conversion.
 463  *
 464  * When a tree block is COW'd through a tree, there are four cases:
 465  *
 466  * The reference count of the block is one and the tree is the block's
 467  * owner tree. Nothing to do in this case.
 468  *
 469  * The reference count of the block is one and the tree is not the
 470  * block's owner tree. In this case, full back refs is used for pointers
 471  * in the block. Remove these full back refs, add implicit back refs for
 472  * every pointers in the new block.
 473  *
 474  * The reference count of the block is greater than one and the tree is
 475  * the block's owner tree. In this case, implicit back refs is used for
 476  * pointers in the block. Add full back refs for every pointers in the
 477  * block, increase lower level extents' reference counts. The original
 478  * implicit back refs are entailed to the new block.
 479  *
 480  * The reference count of the block is greater than one and the tree is
 481  * not the block's owner tree. Add implicit back refs for every pointer in
 482  * the new block, increase lower level extents' reference count.
 483  *
 484  * Back Reference Key composing:
 485  *
 486  * The key objectid corresponds to the first byte in the extent,
 487  * The key type is used to differentiate between types of back refs.
 488  * There are different meanings of the key offset for different types
 489  * of back refs.
 490  *
 491  * File extents can be referenced by:
 492  *
 493  * - multiple snapshots, subvolumes, or different generations in one subvol
 494  * - different files inside a single subvolume
 495  * - different offsets inside a file (bookend extents in file.c)
 496  *
 497  * The extent ref structure for the implicit back refs has fields for:
 498  *
 499  * - Objectid of the subvolume root
 500  * - objectid of the file holding the reference
 501  * - original offset in the file
 502  * - how many bookend extents
 503  *
 504  * The key offset for the implicit back refs is hash of the first
 505  * three fields.
 506  *
 507  * The extent ref structure for the full back refs has field for:
 508  *
 509  * - number of pointers in the tree leaf
 510  *
 511  * The key offset for the implicit back refs is the first byte of
 512  * the tree leaf
 513  *
 514  * When a file extent is allocated, The implicit back refs is used.
 515  * the fields are filled in:
 516  *
 517  *     (root_key.objectid, inode objectid, offset in file, 1)
 518  *
 519  * When a file extent is removed file truncation, we find the
 520  * corresponding implicit back refs and check the following fields:
 521  *
 522  *     (btrfs_header_owner(leaf), inode objectid, offset in file)
 523  *
 524  * Btree extents can be referenced by:
 525  *
 526  * - Different subvolumes
 527  *
 528  * Both the implicit back refs and the full back refs for tree blocks
 529  * only consist of key. The key offset for the implicit back refs is
 530  * objectid of block's owner tree. The key offset for the full back refs
 531  * is the first byte of parent block.
 532  *
 533  * When implicit back refs is used, information about the lowest key and
 534  * level of the tree block are required. These information are stored in
 535  * tree block info structure.
 536  */
 537
 538 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 539 static int convert_extent_item_v0(struct btrfs_trans_handle *trans,
 540                                   struct btrfs_root *root,
 541                                   struct btrfs_path *path,
 542                                   u64 owner, u32 extra_size)
 543 {
 544         struct btrfs_extent_item *item;
 545         struct btrfs_extent_item_v0 *ei0;
 546         struct btrfs_extent_ref_v0 *ref0;
 547         struct btrfs_tree_block_info *bi;
 548         struct extent_buffer *leaf;
 549         struct btrfs_key key;
 550         struct btrfs_key found_key;
 551         u32 new_size = sizeof(*item);
 552         u64 refs;
 553         int ret;
 554
 555         leaf = path->nodes[0];
 556         BUG_ON(btrfs_item_size_nr(leaf, path->slots[0]) != sizeof(*ei0));
 557
 558         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 559         ei0 = btrfs_item_ptr(leaf, path->slots[0],
 560                              struct btrfs_extent_item_v0);
 561         refs = btrfs_extent_refs_v0(leaf, ei0);
 562
 563         if (owner == (u64)-1) {
 564                 while (1) {
 565                         if (path->slots[0] >= btrfs_header_nritems(leaf)) {
 566                                 ret = btrfs_next_leaf(root, path);
 567                                 if (ret < 0)
 568                                         return ret;
 569                                 BUG_ON(ret > 0);
 570                                 leaf = path->nodes[0];
 571                         }
 572                         btrfs_item_key_to_cpu(leaf, &found_key,
 573                                               path->slots[0]);
 574                         BUG_ON(key.objectid != found_key.objectid);
 575                         if (found_key.type != BTRFS_EXTENT_REF_V0_KEY) {
 576                                 path->slots[0]++;
 577                                 continue;
 578                         }
 579                         ref0 = btrfs_item_ptr(leaf, path->slots[0],
 580                                               struct btrfs_extent_ref_v0);
 581                         owner = btrfs_ref_objectid_v0(leaf, ref0);
 582                         break;
 583                 }
 584         }
 585         btrfs_release_path(root, path);
 586
 587         if (owner < BTRFS_FIRST_FREE_OBJECTID)
 588                 new_size += sizeof(*bi);
 589
 590         new_size -= sizeof(*ei0);
 591         ret = btrfs_search_slot(trans, root, &key, path,
 592                                 new_size + extra_size, 1);
 593         if (ret < 0)
 594                 return ret;
 595         BUG_ON(ret);
 596
 597         ret = btrfs_extend_item(trans, root, path, new_size);
 598         BUG_ON(ret);
 599
 600         leaf = path->nodes[0];
 601         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
 602         btrfs_set_extent_refs(leaf, item, refs);
 603         /* FIXME: get real generation */
 604         btrfs_set_extent_generation(leaf, item, 0);
 605         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
 606                 btrfs_set_extent_flags(leaf, item,
 607                                        BTRFS_EXTENT_FLAG_TREE_BLOCK |
 608                                        BTRFS_BLOCK_FLAG_FULL_BACKREF);
 609                 bi = (struct btrfs_tree_block_info *)(item + 1);
 610                 /* FIXME: get first key of the block */
 611                 memset_extent_buffer(leaf, 0, (unsigned long)bi, sizeof(*bi));
 612                 btrfs_set_tree_block_level(leaf, bi, (int)owner);
 613         } else {
 614                 btrfs_set_extent_flags(leaf, item, BTRFS_EXTENT_FLAG_DATA);
 615         }
 616         btrfs_mark_buffer_dirty(leaf);
 617         return 0;
 618 }
 619 #endif
 620
 621 static u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset)
 622 {
 623         u32 high_crc = ~(u32)0;
 624         u32 low_crc = ~(u32)0;
 625         __le64 lenum;
 626
 627         lenum = cpu_to_le64(root_objectid);
 628         high_crc = btrfs_crc32c(high_crc, &lenum, sizeof(lenum));
 629         lenum = cpu_to_le64(owner);
 630         low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
 631         lenum = cpu_to_le64(offset);
 632         low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
 633
 634         return ((u64)high_crc << 31) ^ (u64)low_crc;
 635 }
 636
 637 static u64 hash_extent_data_ref_item(struct extent_buffer *leaf,
 638                                      struct btrfs_extent_data_ref *ref)
 639 {
 640         return hash_extent_data_ref(btrfs_extent_data_ref_root(leaf, ref),
 641                                     btrfs_extent_data_ref_objectid(leaf, ref),
 642                                     btrfs_extent_data_ref_offset(leaf, ref));
 643 }
 644
 645 static int match_extent_data_ref(struct extent_buffer *leaf,
 646                                  struct btrfs_extent_data_ref *ref,
 647                                  u64 root_objectid, u64 owner, u64 offset)
 648 {
 649         if (btrfs_extent_data_ref_root(leaf, ref) != root_objectid ||
 650             btrfs_extent_data_ref_objectid(leaf, ref) != owner ||
 651             btrfs_extent_data_ref_offset(leaf, ref) != offset)
 652                 return 0;
 653         return 1;
 654 }
 655
 656 static noinline int lookup_extent_data_ref(struct btrfs_trans_handle *trans,
 657                                            struct btrfs_root *root,
 658                                            struct btrfs_path *path,
 659                                            u64 bytenr, u64 parent,
 660                                            u64 root_objectid,
 661                                            u64 owner, u64 offset)
 662 {
 663         struct btrfs_key key;
 664         struct btrfs_extent_data_ref *ref;
 665         struct extent_buffer *leaf;
 666         u32 nritems;
 667         int ret;
 668         int recow;
 669         int err = -ENOENT;
 670
 671         key.objectid = bytenr;
 672         if (parent) {
 673                 key.type = BTRFS_SHARED_DATA_REF_KEY;
 674                 key.offset = parent;
 675         } else {
 676                 key.type = BTRFS_EXTENT_DATA_REF_KEY;
 677                 key.offset = hash_extent_data_ref(root_objectid,
 678                                                   owner, offset);
 679         }
 680 again:
 681         recow = 0;
 682         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 683         if (ret < 0) {
 684                 err = ret;
 685                 goto fail;
 686         }
 687
 688         if (parent) {
 689                 if (!ret)
 690                         return 0;
 691 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 692                 key.type = BTRFS_EXTENT_REF_V0_KEY;
 693                 btrfs_release_path(root, path);
 694                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 695                 if (ret < 0) {
 696                         err = ret;
 697                         goto fail;
 698                 }
 699                 if (!ret)
 700                         return 0;
 701 #endif
 702                 goto fail;
 703         }
 704
 705         leaf = path->nodes[0];
 706         nritems = btrfs_header_nritems(leaf);
 707         while (1) {
 708                 if (path->slots[0] >= nritems) {
 709                         ret = btrfs_next_leaf(root, path);
 710                         if (ret < 0)
 711                                 err = ret;
 712                         if (ret)
 713                                 goto fail;
 714
 715                         leaf = path->nodes[0];
 716                         nritems = btrfs_header_nritems(leaf);
 717                         recow = 1;
 718                 }
 719
 720                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 721                 if (key.objectid != bytenr ||
 722                     key.type != BTRFS_EXTENT_DATA_REF_KEY)
 723                         goto fail;
 724
 725                 ref = btrfs_item_ptr(leaf, path->slots[0],
 726                                      struct btrfs_extent_data_ref);
 727
 728                 if (match_extent_data_ref(leaf, ref, root_objectid,
 729                                           owner, offset)) {
 730                         if (recow) {
 731                                 btrfs_release_path(root, path);
 732                                 goto again;
 733                         }
 734                         err = 0;
 735                         break;
 736                 }
 737                 path->slots[0]++;
 738         }
 739 fail:
 740         return err;
 741 }
 742
 743 static noinline int insert_extent_data_ref(struct btrfs_trans_handle *trans,
 744                                            struct btrfs_root *root,
 745                                            struct btrfs_path *path,
 746                                            u64 bytenr, u64 parent,
 747                                            u64 root_objectid, u64 owner,
 748                                            u64 offset, int refs_to_add)
 749 {
 750         struct btrfs_key key;
 751         struct extent_buffer *leaf;
 752         u32 size;
 753         u32 num_refs;
 754         int ret;
 755
 756         key.objectid = bytenr;
 757         if (parent) {
 758                 key.type = BTRFS_SHARED_DATA_REF_KEY;
 759                 key.offset = parent;
 760                 size = sizeof(struct btrfs_shared_data_ref);
 761         } else {
 762                 key.type = BTRFS_EXTENT_DATA_REF_KEY;
 763                 key.offset = hash_extent_data_ref(root_objectid,
 764                                                   owner, offset);
 765                 size = sizeof(struct btrfs_extent_data_ref);
 766         }
 767
 768         ret = btrfs_insert_empty_item(trans, root, path, &key, size);
 769         if (ret && ret != -EEXIST)
 770                 goto fail;
 771
 772         leaf = path->nodes[0];
 773         if (parent) {
 774                 struct btrfs_shared_data_ref *ref;
 775                 ref = btrfs_item_ptr(leaf, path->slots[0],
 776                                      struct btrfs_shared_data_ref);
 777                 if (ret == 0) {
 778                         btrfs_set_shared_data_ref_count(leaf, ref, refs_to_add);
 779                 } else {
 780                         num_refs = btrfs_shared_data_ref_count(leaf, ref);
 781                         num_refs += refs_to_add;
 782                         btrfs_set_shared_data_ref_count(leaf, ref, num_refs);
 783                 }
 784         } else {
 785                 struct btrfs_extent_data_ref *ref;
 786                 while (ret == -EEXIST) {
 787                         ref = btrfs_item_ptr(leaf, path->slots[0],
 788                                              struct btrfs_extent_data_ref);
 789                         if (match_extent_data_ref(leaf, ref, root_objectid,
 790                                                   owner, offset))
 791                                 break;
 792                         btrfs_release_path(root, path);
 793                         key.offset++;
 794                         ret = btrfs_insert_empty_item(trans, root, path, &key,
 795                                                       size);
 796                         if (ret && ret != -EEXIST)
 797                                 goto fail;
 798
 799                         leaf = path->nodes[0];
 800                 }
 801                 ref = btrfs_item_ptr(leaf, path->slots[0],
 802                                      struct btrfs_extent_data_ref);
 803                 if (ret == 0) {
 804                         btrfs_set_extent_data_ref_root(leaf, ref,
 805                                                        root_objectid);
 806                         btrfs_set_extent_data_ref_objectid(leaf, ref, owner);
 807                         btrfs_set_extent_data_ref_offset(leaf, ref, offset);
 808                         btrfs_set_extent_data_ref_count(leaf, ref, refs_to_add);
 809                 } else {
 810                         num_refs = btrfs_extent_data_ref_count(leaf, ref);
 811                         num_refs += refs_to_add;
 812                         btrfs_set_extent_data_ref_count(leaf, ref, num_refs);
 813                 }
 814         }
 815         btrfs_mark_buffer_dirty(leaf);
 816         ret = 0;
 817 fail:
 818         btrfs_release_path(root, path);
 819         return ret;
 820 }
 821
 822 static noinline int remove_extent_data_ref(struct btrfs_trans_handle *trans,
 823                                            struct btrfs_root *root,
 824                                            struct btrfs_path *path,
 825                                            int refs_to_drop)
 826 {
 827         struct btrfs_key key;
 828         struct btrfs_extent_data_ref *ref1 = NULL;
 829         struct btrfs_shared_data_ref *ref2 = NULL;
 830         struct extent_buffer *leaf;
 831         u32 num_refs = 0;
 832         int ret = 0;
 833
 834         leaf = path->nodes[0];
 835         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 836
 837         if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
 838                 ref1 = btrfs_item_ptr(leaf, path->slots[0],
 839                                       struct btrfs_extent_data_ref);
 840                 num_refs = btrfs_extent_data_ref_count(leaf, ref1);
 841         } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
 842                 ref2 = btrfs_item_ptr(leaf, path->slots[0],
 843                                       struct btrfs_shared_data_ref);
 844                 num_refs = btrfs_shared_data_ref_count(leaf, ref2);
 845 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 846         } else if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
 847                 struct btrfs_extent_ref_v0 *ref0;
 848                 ref0 = btrfs_item_ptr(leaf, path->slots[0],
 849                                       struct btrfs_extent_ref_v0);
 850                 num_refs = btrfs_ref_count_v0(leaf, ref0);
 851 #endif
 852         } else {
 853                 BUG();
 854         }
 855
 856         BUG_ON(num_refs < refs_to_drop);
 857         num_refs -= refs_to_drop;
 858
 859         if (num_refs == 0) {
 860                 ret = btrfs_del_item(trans, root, path);
 861         } else {
 862                 if (key.type == BTRFS_EXTENT_DATA_REF_KEY)
 863                         btrfs_set_extent_data_ref_count(leaf, ref1, num_refs);
 864                 else if (key.type == BTRFS_SHARED_DATA_REF_KEY)
 865                         btrfs_set_shared_data_ref_count(leaf, ref2, num_refs);
 866 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 867                 else {
 868                         struct btrfs_extent_ref_v0 *ref0;
 869                         ref0 = btrfs_item_ptr(leaf, path->slots[0],
 870                                         struct btrfs_extent_ref_v0);
 871                         btrfs_set_ref_count_v0(leaf, ref0, num_refs);
 872                 }
 873 #endif
 874                 btrfs_mark_buffer_dirty(leaf);
 875         }
 876         return ret;
 877 }
 878
 879 static noinline u32 extent_data_ref_count(struct btrfs_root *root,
 880                                           struct btrfs_path *path,
 881                                           struct btrfs_extent_inline_ref *iref)
 882 {
 883         struct btrfs_key key;
 884         struct extent_buffer *leaf;
 885         struct btrfs_extent_data_ref *ref1;
 886         struct btrfs_shared_data_ref *ref2;
 887         u32 num_refs = 0;
 888
 889         leaf = path->nodes[0];
 890         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 891         if (iref) {
 892                 if (btrfs_extent_inline_ref_type(leaf, iref) ==
 893                     BTRFS_EXTENT_DATA_REF_KEY) {
 894                         ref1 = (struct btrfs_extent_data_ref *)(&iref->offset);
 895                         num_refs = btrfs_extent_data_ref_count(leaf, ref1);
 896                 } else {
 897                         ref2 = (struct btrfs_shared_data_ref *)(iref + 1);
 898                         num_refs = btrfs_shared_data_ref_count(leaf, ref2);
 899                 }
 900         } else if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
 901                 ref1 = btrfs_item_ptr(leaf, path->slots[0],
 902                                       struct btrfs_extent_data_ref);
 903                 num_refs = btrfs_extent_data_ref_count(leaf, ref1);
 904         } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
 905                 ref2 = btrfs_item_ptr(leaf, path->slots[0],
 906                                       struct btrfs_shared_data_ref);
 907                 num_refs = btrfs_shared_data_ref_count(leaf, ref2);
 908 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 909         } else if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
 910                 struct btrfs_extent_ref_v0 *ref0;
 911                 ref0 = btrfs_item_ptr(leaf, path->slots[0],
 912                                       struct btrfs_extent_ref_v0);
 913                 num_refs = btrfs_ref_count_v0(leaf, ref0);
 914 #endif
 915         } else {
 916                 WARN_ON(1);
 917         }
 918         return num_refs;
 919 }
 920
 921 static noinline int lookup_tree_block_ref(struct btrfs_trans_handle *trans,
 922                                           struct btrfs_root *root,
 923                                           struct btrfs_path *path,
 924                                           u64 bytenr, u64 parent,
 925                                           u64 root_objectid)
 926 {
 927         struct btrfs_key key;
 928         int ret;
 929
 930         key.objectid = bytenr;
 931         if (parent) {
 932                 key.type = BTRFS_SHARED_BLOCK_REF_KEY;
 933                 key.offset = parent;
 934         } else {
 935                 key.type = BTRFS_TREE_BLOCK_REF_KEY;
 936                 key.offset = root_objectid;
 937         }
 938
 939         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 940         if (ret > 0)
 941                 ret = -ENOENT;
 942 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 943         if (ret == -ENOENT && parent) {
 944                 btrfs_release_path(root, path);
 945                 key.type = BTRFS_EXTENT_REF_V0_KEY;
 946                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 947                 if (ret > 0)
 948                         ret = -ENOENT;
 949         }
 950 #endif
 951         return ret;
 952 }
 953
 954 static noinline int insert_tree_block_ref(struct btrfs_trans_handle *trans,
 955                                           struct btrfs_root *root,
 956                                           struct btrfs_path *path,
 957                                           u64 bytenr, u64 parent,
 958                                           u64 root_objectid)
 959 {
 960         struct btrfs_key key;
 961         int ret;
 962
 963         key.objectid = bytenr;
 964         if (parent) {
 965                 key.type = BTRFS_SHARED_BLOCK_REF_KEY;
 966                 key.offset = parent;
 967         } else {
 968                 key.type = BTRFS_TREE_BLOCK_REF_KEY;
 969                 key.offset = root_objectid;
 970         }
 971
 972         ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
 973         btrfs_release_path(root, path);
 974         return ret;
 975 }
 976
 977 static inline int extent_ref_type(u64 parent, u64 owner)
 978 {
 979         int type;
 980         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
 981                 if (parent > 0)
 982                         type = BTRFS_SHARED_BLOCK_REF_KEY;
 983                 else
 984                         type = BTRFS_TREE_BLOCK_REF_KEY;
 985         } else {
 986                 if (parent > 0)
 987                         type = BTRFS_SHARED_DATA_REF_KEY;
 988                 else
 989                         type = BTRFS_EXTENT_DATA_REF_KEY;
 990         }
 991         return type;
 992 }
 993
 994 static int find_next_key(struct btrfs_path *path, struct btrfs_key *key)
 995
 996 {
 997         int level;
 998         BUG_ON(!path->keep_locks);
 999         for (level = 0; level < BTRFS_MAX_LEVEL; level++) {
1000                 if (!path->nodes[level])
1001                         break;
1002                 btrfs_assert_tree_locked(path->nodes[level]);
1003                 if (path->slots[level] + 1 >=
1004                     btrfs_header_nritems(path->nodes[level]))
1005                         continue;
1006                 if (level == 0)
1007                         btrfs_item_key_to_cpu(path->nodes[level], key,
1008                                               path->slots[level] + 1);
1009                 else
1010                         btrfs_node_key_to_cpu(path->nodes[level], key,
1011                                               path->slots[level] + 1);
1012                 return 0;
1013         }
1014         return 1;
1015 }
1016
1017 /*
1018  * look for inline back ref. if back ref is found, *ref_ret is set
1019  * to the address of inline back ref, and 0 is returned.
1020  *
1021  * if back ref isn't found, *ref_ret is set to the address where it
1022  * should be inserted, and -ENOENT is returned.
1023  *
1024  * if insert is true and there are too many inline back refs, the path
1025  * points to the extent item, and -EAGAIN is returned.
1026  *
1027  * NOTE: inline back refs are ordered in the same way that back ref
1028  *       items in the tree are ordered.
1029  */
1030 static noinline_for_stack
1031 int lookup_inline_extent_backref(struct btrfs_trans_handle *trans,
1032                                  struct btrfs_root *root,
1033                                  struct btrfs_path *path,
1034                                  struct btrfs_extent_inline_ref **ref_ret,
1035                                  u64 bytenr, u64 num_bytes,
1036                                  u64 parent, u64 root_objectid,
1037                                  u64 owner, u64 offset, int insert)
1038 {
1039         struct btrfs_key key;
1040         struct extent_buffer *leaf;
1041         struct btrfs_extent_item *ei;
1042         struct btrfs_extent_inline_ref *iref;
1043         u64 flags;
1044         u64 item_size;
1045         unsigned long ptr;
1046         unsigned long end;
1047         int extra_size;
1048         int type;
1049         int want;
1050         int ret;
1051         int err = 0;
1052
1053         key.objectid = bytenr;
1054         key.type = BTRFS_EXTENT_ITEM_KEY;
1055         key.offset = num_bytes;
1056
1057         want = extent_ref_type(parent, owner);
1058         if (insert) {
1059                 extra_size = btrfs_extent_inline_ref_size(want);
1060                 if (owner >= BTRFS_FIRST_FREE_OBJECTID)
1061                         path->keep_locks = 1;
1062         } else
1063                 extra_size = -1;
1064         ret = btrfs_search_slot(trans, root, &key, path, extra_size, 1);
1065         if (ret < 0) {
1066                 err = ret;
1067                 goto out;
1068         }
1069         BUG_ON(ret);
1070
1071         leaf = path->nodes[0];
1072         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1073 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
1074         if (item_size < sizeof(*ei)) {
1075                 if (!insert) {
1076                         err = -ENOENT;
1077                         goto out;
1078                 }
1079                 ret = convert_extent_item_v0(trans, root, path, owner,
1080                                              extra_size);
1081                 if (ret < 0) {
1082                         err = ret;
1083                         goto out;
1084                 }
1085                 leaf = path->nodes[0];
1086                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1087         }
1088 #endif
1089         BUG_ON(item_size < sizeof(*ei));
1090
1091         if (owner < BTRFS_FIRST_FREE_OBJECTID && insert &&
1092             item_size + extra_size >= BTRFS_MAX_EXTENT_ITEM_SIZE(root)) {
1093                 err = -EAGAIN;
1094                 goto out;
1095         }
1096
1097         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1098         flags = btrfs_extent_flags(leaf, ei);
1099
1100         ptr = (unsigned long)(ei + 1);
1101         end = (unsigned long)ei + item_size;
1102
1103         if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
1104                 ptr += sizeof(struct btrfs_tree_block_info);
1105                 BUG_ON(ptr > end);
1106         } else {
1107                 BUG_ON(!(flags & BTRFS_EXTENT_FLAG_DATA));
1108         }
1109
1110         err = -ENOENT;
1111         while (1) {
1112                 if (ptr >= end) {
1113                         WARN_ON(ptr > end);
1114                         break;
1115                 }
1116                 iref = (struct btrfs_extent_inline_ref *)ptr;
1117                 type = btrfs_extent_inline_ref_type(leaf, iref);
1118                 if (want < type)
1119                         break;
1120                 if (want > type) {
1121                         ptr += btrfs_extent_inline_ref_size(type);
1122                         continue;
1123                 }
1124
1125                 if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1126                         struct btrfs_extent_data_ref *dref;
1127                         dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1128                         if (match_extent_data_ref(leaf, dref, root_objectid,
1129                                                   owner, offset)) {
1130                                 err = 0;
1131                                 break;
1132                         }
1133                         if (hash_extent_data_ref_item(leaf, dref) <
1134                             hash_extent_data_ref(root_objectid, owner, offset))
1135                                 break;
1136                 } else {
1137                         u64 ref_offset;
1138                         ref_offset = btrfs_extent_inline_ref_offset(leaf, iref);
1139                         if (parent > 0) {
1140                                 if (parent == ref_offset) {
1141                                         err = 0;
1142                                         break;
1143                                 }
1144                                 if (ref_offset < parent)
1145                                         break;
1146                         } else {
1147                                 if (root_objectid == ref_offset) {
1148                                         err = 0;
1149                                         break;
1150                                 }
1151                                 if (ref_offset < root_objectid)
1152                                         break;
1153                         }
1154                 }
1155                 ptr += btrfs_extent_inline_ref_size(type);
1156         }
1157         if (err == -ENOENT && insert) {
1158                 if (item_size + extra_size >=
1159                     BTRFS_MAX_EXTENT_ITEM_SIZE(root)) {
1160                         err = -EAGAIN;
1161                         goto out;
1162                 }
1163                 /*
1164                  * To add new inline back ref, we have to make sure
1165                  * there is no corresponding back ref item.
1166                  * For simplicity, we just do not add new inline back
1167                  * ref if there is any kind of item for this block
1168                  */
1169                 if (owner >= BTRFS_FIRST_FREE_OBJECTID &&
1170                     find_next_key(path, &key) == 0 && key.objectid == bytenr) {
1171                         err = -EAGAIN;
1172                         goto out;
1173                 }
1174         }
1175         *ref_ret = (struct btrfs_extent_inline_ref *)ptr;
1176 out:
1177         if (insert && owner >= BTRFS_FIRST_FREE_OBJECTID) {
1178                 path->keep_locks = 0;
1179                 btrfs_unlock_up_safe(path, 1);
1180         }
1181         return err;
1182 }
1183
1184 /*
1185  * helper to add new inline back ref
1186  */
1187 static noinline_for_stack
1188 int setup_inline_extent_backref(struct btrfs_trans_handle *trans,
1189                                 struct btrfs_root *root,
1190                                 struct btrfs_path *path,
1191                                 struct btrfs_extent_inline_ref *iref,
1192                                 u64 parent, u64 root_objectid,
1193                                 u64 owner, u64 offset, int refs_to_add,
1194                                 struct btrfs_delayed_extent_op *extent_op)
1195 {
1196         struct extent_buffer *leaf;
1197         struct btrfs_extent_item *ei;
1198         unsigned long ptr;
1199         unsigned long end;
1200         unsigned long item_offset;
1201         u64 refs;
1202         int size;
1203         int type;
1204         int ret;
1205
1206         leaf = path->nodes[0];
1207         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1208         item_offset = (unsigned long)iref - (unsigned long)ei;
1209
1210         type = extent_ref_type(parent, owner);
1211         size = btrfs_extent_inline_ref_size(type);
1212
1213         ret = btrfs_extend_item(trans, root, path, size);
1214         BUG_ON(ret);
1215
1216         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1217         refs = btrfs_extent_refs(leaf, ei);
1218         refs += refs_to_add;
1219         btrfs_set_extent_refs(leaf, ei, refs);
1220         if (extent_op)
1221                 __run_delayed_extent_op(extent_op, leaf, ei);
1222
1223         ptr = (unsigned long)ei + item_offset;
1224         end = (unsigned long)ei + btrfs_item_size_nr(leaf, path->slots[0]);
1225         if (ptr < end - size)
1226                 memmove_extent_buffer(leaf, ptr + size, ptr,
1227                                       end - size - ptr);
1228
1229         iref = (struct btrfs_extent_inline_ref *)ptr;
1230         btrfs_set_extent_inline_ref_type(leaf, iref, type);
1231         if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1232                 struct btrfs_extent_data_ref *dref;
1233                 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1234                 btrfs_set_extent_data_ref_root(leaf, dref, root_objectid);
1235                 btrfs_set_extent_data_ref_objectid(leaf, dref, owner);
1236                 btrfs_set_extent_data_ref_offset(leaf, dref, offset);
1237                 btrfs_set_extent_data_ref_count(leaf, dref, refs_to_add);
1238         } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
1239                 struct btrfs_shared_data_ref *sref;
1240                 sref = (struct btrfs_shared_data_ref *)(iref + 1);
1241                 btrfs_set_shared_data_ref_count(leaf, sref, refs_to_add);
1242                 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
1243         } else if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
1244                 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
1245         } else {
1246                 btrfs_set_extent_inline_ref_offset(leaf, iref, root_objectid);
1247         }
1248         btrfs_mark_buffer_dirty(leaf);
1249         return 0;
1250 }
1251
1252 static int lookup_extent_backref(struct btrfs_trans_handle *trans,
1253                                  struct btrfs_root *root,
1254                                  struct btrfs_path *path,
1255                                  struct btrfs_extent_inline_ref **ref_ret,
1256                                  u64 bytenr, u64 num_bytes, u64 parent,
1257                                  u64 root_objectid, u64 owner, u64 offset)
1258 {
1259         int ret;
1260
1261         ret = lookup_inline_extent_backref(trans, root, path, ref_ret,
1262                                            bytenr, num_bytes, parent,
1263                                            root_objectid, owner, offset, 0);
1264         if (ret != -ENOENT)
1265                 return ret;
1266
1267         btrfs_release_path(root, path);
1268         *ref_ret = NULL;
1269
1270         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1271                 ret = lookup_tree_block_ref(trans, root, path, bytenr, parent,
1272                                             root_objectid);
1273         } else {
1274                 ret = lookup_extent_data_ref(trans, root, path, bytenr, parent,
1275                                              root_objectid, owner, offset);
1276         }
1277         return ret;
1278 }
1279
1280 /*
1281  * helper to update/remove inline back ref
1282  */
1283 static noinline_for_stack
1284 int update_inline_extent_backref(struct btrfs_trans_handle *trans,
1285                                  struct btrfs_root *root,
1286                                  struct btrfs_path *path,
1287                                  struct btrfs_extent_inline_ref *iref,
1288                                  int refs_to_mod,
1289                                  struct btrfs_delayed_extent_op *extent_op)
1290 {
1291         struct extent_buffer *leaf;
1292         struct btrfs_extent_item *ei;
1293         struct btrfs_extent_data_ref *dref = NULL;
1294         struct btrfs_shared_data_ref *sref = NULL;
1295         unsigned long ptr;
1296         unsigned long end;
1297         u32 item_size;
1298         int size;
1299         int type;
1300         int ret;
1301         u64 refs;
1302
1303         leaf = path->nodes[0];
1304         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1305         refs = btrfs_extent_refs(leaf, ei);
1306         WARN_ON(refs_to_mod < 0 && refs + refs_to_mod <= 0);
1307         refs += refs_to_mod;
1308         btrfs_set_extent_refs(leaf, ei, refs);
1309         if (extent_op)
1310                 __run_delayed_extent_op(extent_op, leaf, ei);
1311
1312         type = btrfs_extent_inline_ref_type(leaf, iref);
1313
1314         if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1315                 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1316                 refs = btrfs_extent_data_ref_count(leaf, dref);
1317         } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
1318                 sref = (struct btrfs_shared_data_ref *)(iref + 1);
1319                 refs = btrfs_shared_data_ref_count(leaf, sref);
1320         } else {
1321                 refs = 1;
1322                 BUG_ON(refs_to_mod != -1);
1323         }
1324
1325         BUG_ON(refs_to_mod < 0 && refs < -refs_to_mod);
1326         refs += refs_to_mod;
1327
1328         if (refs > 0) {
1329                 if (type == BTRFS_EXTENT_DATA_REF_KEY)
1330                         btrfs_set_extent_data_ref_count(leaf, dref, refs);
1331                 else
1332                         btrfs_set_shared_data_ref_count(leaf, sref, refs);
1333         } else {
1334                 size =  btrfs_extent_inline_ref_size(type);
1335                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1336                 ptr = (unsigned long)iref;
1337                 end = (unsigned long)ei + item_size;
1338                 if (ptr + size < end)
1339                         memmove_extent_buffer(leaf, ptr, ptr + size,
1340                                               end - ptr - size);
1341                 item_size -= size;
1342                 ret = btrfs_truncate_item(trans, root, path, item_size, 1);
1343                 BUG_ON(ret);
1344         }
1345         btrfs_mark_buffer_dirty(leaf);
1346         return 0;
1347 }
1348
1349 static noinline_for_stack
1350 int insert_inline_extent_backref(struct btrfs_trans_handle *trans,
1351                                  struct btrfs_root *root,
1352                                  struct btrfs_path *path,
1353                                  u64 bytenr, u64 num_bytes, u64 parent,
1354                                  u64 root_objectid, u64 owner,
1355                                  u64 offset, int refs_to_add,
1356                                  struct btrfs_delayed_extent_op *extent_op)
1357 {
1358         struct btrfs_extent_inline_ref *iref;
1359         int ret;
1360
1361         ret = lookup_inline_extent_backref(trans, root, path, &iref,
1362                                            bytenr, num_bytes, parent,
1363                                            root_objectid, owner, offset, 1);
1364         if (ret == 0) {
1365                 BUG_ON(owner < BTRFS_FIRST_FREE_OBJECTID);
1366                 ret = update_inline_extent_backref(trans, root, path, iref,
1367                                                    refs_to_add, extent_op);
1368         } else if (ret == -ENOENT) {
1369                 ret = setup_inline_extent_backref(trans, root, path, iref,
1370                                                   parent, root_objectid,
1371                                                   owner, offset, refs_to_add,
1372                                                   extent_op);
1373         }
1374         return ret;
1375 }
1376
1377 static int insert_extent_backref(struct btrfs_trans_handle *trans,
1378                                  struct btrfs_root *root,
1379                                  struct btrfs_path *path,
1380                                  u64 bytenr, u64 parent, u64 root_objectid,
1381                                  u64 owner, u64 offset, int refs_to_add)
1382 {
1383         int ret;
1384         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1385                 BUG_ON(refs_to_add != 1);
1386                 ret = insert_tree_block_ref(trans, root, path, bytenr,
1387                                             parent, root_objectid);
1388         } else {
1389                 ret = insert_extent_data_ref(trans, root, path, bytenr,
1390                                              parent, root_objectid,
1391                                              owner, offset, refs_to_add);
1392         }
1393         return ret;
1394 }
1395
1396 static int remove_extent_backref(struct btrfs_trans_handle *trans,
1397                                  struct btrfs_root *root,
1398                                  struct btrfs_path *path,
1399                                  struct btrfs_extent_inline_ref *iref,
1400                                  int refs_to_drop, int is_data)
1401 {
1402         int ret;
1403
1404         BUG_ON(!is_data && refs_to_drop != 1);
1405         if (iref) {
1406                 ret = update_inline_extent_backref(trans, root, path, iref,
1407                                                    -refs_to_drop, NULL);
1408         } else if (is_data) {
1409                 ret = remove_extent_data_ref(trans, root, path, refs_to_drop);
1410         } else {
1411                 ret = btrfs_del_item(trans, root, path);
1412         }
1413         return ret;
1414 }
1415
1416 #ifdef BIO_RW_DISCARD
1417 static void btrfs_issue_discard(struct block_device *bdev,
1418                                 u64 start, u64 len)
1419 {
1420         blkdev_issue_discard(bdev, start >> 9, len >> 9, GFP_KERNEL);
1421 }
1422 #endif
1423
1424 static int btrfs_discard_extent(struct btrfs_root *root, u64 bytenr,
1425                                 u64 num_bytes)
1426 {
1427 #ifdef BIO_RW_DISCARD
1428         int ret;
1429         u64 map_length = num_bytes;
1430         struct btrfs_multi_bio *multi = NULL;
1431
1432         /* Tell the block device(s) that the sectors can be discarded */
1433         ret = btrfs_map_block(&root->fs_info->mapping_tree, READ,
1434                               bytenr, &map_length, &multi, 0);
1435         if (!ret) {
1436                 struct btrfs_bio_stripe *stripe = multi->stripes;
1437                 int i;
1438
1439                 if (map_length > num_bytes)
1440                         map_length = num_bytes;
1441
1442                 for (i = 0; i < multi->num_stripes; i++, stripe++) {
1443                         btrfs_issue_discard(stripe->dev->bdev,
1444                                             stripe->physical,
1445                                             map_length);
1446                 }
1447                 kfree(multi);
1448         }
1449
1450         return ret;
1451 #else
1452         return 0;
1453 #endif
1454 }
1455
1456 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
1457                          struct btrfs_root *root,
1458                          u64 bytenr, u64 num_bytes, u64 parent,
1459                          u64 root_objectid, u64 owner, u64 offset)
1460 {
1461         int ret;
1462         BUG_ON(owner < BTRFS_FIRST_FREE_OBJECTID &&
1463                root_objectid == BTRFS_TREE_LOG_OBJECTID);
1464
1465         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1466                 ret = btrfs_add_delayed_tree_ref(trans, bytenr, num_bytes,
1467                                         parent, root_objectid, (int)owner,
1468                                         BTRFS_ADD_DELAYED_REF, NULL);
1469         } else {
1470                 ret = btrfs_add_delayed_data_ref(trans, bytenr, num_bytes,
1471                                         parent, root_objectid, owner, offset,
1472                                         BTRFS_ADD_DELAYED_REF, NULL);
1473         }
1474         return ret;
1475 }
1476
1477 static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
1478                                   struct btrfs_root *root,
1479                                   u64 bytenr, u64 num_bytes,
1480                                   u64 parent, u64 root_objectid,
1481                                   u64 owner, u64 offset, int refs_to_add,
1482                                   struct btrfs_delayed_extent_op *extent_op)
1483 {
1484         struct btrfs_path *path;
1485         struct extent_buffer *leaf;
1486         struct btrfs_extent_item *item;
1487         u64 refs;
1488         int ret;
1489         int err = 0;
1490
1491         path = btrfs_alloc_path();
1492         if (!path)
1493                 return -ENOMEM;
1494
1495         path->reada = 1;
1496         path->leave_spinning = 1;
1497         /* this will setup the path even if it fails to insert the back ref */
1498         ret = insert_inline_extent_backref(trans, root->fs_info->extent_root,
1499                                            path, bytenr, num_bytes, parent,
1500                                            root_objectid, owner, offset,
1501                                            refs_to_add, extent_op);
1502         if (ret == 0)
1503                 goto out;
1504
1505         if (ret != -EAGAIN) {
1506                 err = ret;
1507                 goto out;
1508         }
1509
1510         leaf = path->nodes[0];
1511         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1512         refs = btrfs_extent_refs(leaf, item);
1513         btrfs_set_extent_refs(leaf, item, refs + refs_to_add);
1514         if (extent_op)
1515                 __run_delayed_extent_op(extent_op, leaf, item);
1516
1517         btrfs_mark_buffer_dirty(leaf);
1518         btrfs_release_path(root->fs_info->extent_root, path);
1519
1520         path->reada = 1;
1521         path->leave_spinning = 1;
1522
1523         /* now insert the actual backref */
1524         ret = insert_extent_backref(trans, root->fs_info->extent_root,
1525                                     path, bytenr, parent, root_objectid,
1526                                     owner, offset, refs_to_add);
1527         BUG_ON(ret);
1528 out:
1529         btrfs_free_path(path);
1530         return err;
1531 }
1532
1533 static int run_delayed_data_ref(struct btrfs_trans_handle *trans,
1534                                 struct btrfs_root *root,
1535                                 struct btrfs_delayed_ref_node *node,
1536                                 struct btrfs_delayed_extent_op *extent_op,
1537                                 int insert_reserved)
1538 {
1539         int ret = 0;
1540         struct btrfs_delayed_data_ref *ref;
1541         struct btrfs_key ins;
1542         u64 parent = 0;
1543         u64 ref_root = 0;
1544         u64 flags = 0;
1545
1546         ins.objectid = node->bytenr;
1547         ins.offset = node->num_bytes;
1548         ins.type = BTRFS_EXTENT_ITEM_KEY;
1549
1550         ref = btrfs_delayed_node_to_data_ref(node);
1551         if (node->type == BTRFS_SHARED_DATA_REF_KEY)
1552                 parent = ref->parent;
1553         else
1554                 ref_root = ref->root;
1555
1556         if (node->action == BTRFS_ADD_DELAYED_REF && insert_reserved) {
1557                 if (extent_op) {
1558                         BUG_ON(extent_op->update_key);
1559                         flags |= extent_op->flags_to_set;
1560                 }
1561                 ret = alloc_reserved_file_extent(trans, root,
1562                                                  parent, ref_root, flags,
1563                                                  ref->objectid, ref->offset,
1564                                                  &ins, node->ref_mod);
1565                 update_reserved_extents(root, ins.objectid, ins.offset, 0);
1566         } else if (node->action == BTRFS_ADD_DELAYED_REF) {
1567                 ret = __btrfs_inc_extent_ref(trans, root, node->bytenr,
1568                                              node->num_bytes, parent,
1569                                              ref_root, ref->objectid,
1570                                              ref->offset, node->ref_mod,
1571                                              extent_op);
1572         } else if (node->action == BTRFS_DROP_DELAYED_REF) {
1573                 ret = __btrfs_free_extent(trans, root, node->bytenr,
1574                                           node->num_bytes, parent,
1575                                           ref_root, ref->objectid,
1576                                           ref->offset, node->ref_mod,
1577                                           extent_op);
1578         } else {
1579                 BUG();
1580         }
1581         return ret;
1582 }
1583
1584 static void __run_delayed_extent_op(struct btrfs_delayed_extent_op *extent_op,
1585                                     struct extent_buffer *leaf,
1586                                     struct btrfs_extent_item *ei)
1587 {
1588         u64 flags = btrfs_extent_flags(leaf, ei);
1589         if (extent_op->update_flags) {
1590                 flags |= extent_op->flags_to_set;
1591                 btrfs_set_extent_flags(leaf, ei, flags);
1592         }
1593
1594         if (extent_op->update_key) {
1595                 struct btrfs_tree_block_info *bi;
1596                 BUG_ON(!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK));
1597                 bi = (struct btrfs_tree_block_info *)(ei + 1);
1598                 btrfs_set_tree_block_key(leaf, bi, &extent_op->key);
1599         }
1600 }
1601
1602 static int run_delayed_extent_op(struct btrfs_trans_handle *trans,
1603                                  struct btrfs_root *root,
1604                                  struct btrfs_delayed_ref_node *node,
1605                                  struct btrfs_delayed_extent_op *extent_op)
1606 {
1607         struct btrfs_key key;
1608         struct btrfs_path *path;
1609         struct btrfs_extent_item *ei;
1610         struct extent_buffer *leaf;
1611         u32 item_size;
1612         int ret;
1613         int err = 0;
1614
1615         path = btrfs_alloc_path();
1616         if (!path)
1617                 return -ENOMEM;
1618
1619         key.objectid = node->bytenr;
1620         key.type = BTRFS_EXTENT_ITEM_KEY;
1621         key.offset = node->num_bytes;
1622
1623         path->reada = 1;
1624         path->leave_spinning = 1;
1625         ret = btrfs_search_slot(trans, root->fs_info->extent_root, &key,
1626                                 path, 0, 1);
1627         if (ret < 0) {
1628                 err = ret;
1629                 goto out;
1630         }
1631         if (ret > 0) {
1632                 err = -EIO;
1633                 goto out;
1634         }
1635
1636         leaf = path->nodes[0];
1637         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1638 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
1639         if (item_size < sizeof(*ei)) {
1640                 ret = convert_extent_item_v0(trans, root->fs_info->extent_root,
1641                                              path, (u64)-1, 0);
1642                 if (ret < 0) {
1643                         err = ret;
1644                         goto out;
1645                 }
1646                 leaf = path->nodes[0];
1647                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1648         }
1649 #endif
1650         BUG_ON(item_size < sizeof(*ei));
1651         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1652         __run_delayed_extent_op(extent_op, leaf, ei);
1653
1654         btrfs_mark_buffer_dirty(leaf);
1655 out:
1656         btrfs_free_path(path);
1657         return err;
1658 }
1659
1660 static int run_delayed_tree_ref(struct btrfs_trans_handle *trans,
1661                                 struct btrfs_root *root,
1662                                 struct btrfs_delayed_ref_node *node,
1663                                 struct btrfs_delayed_extent_op *extent_op,
1664                                 int insert_reserved)
1665 {
1666         int ret = 0;
1667         struct btrfs_delayed_tree_ref *ref;
1668         struct btrfs_key ins;
1669         u64 parent = 0;
1670         u64 ref_root = 0;
1671
1672         ins.objectid = node->bytenr;
1673         ins.offset = node->num_bytes;
1674         ins.type = BTRFS_EXTENT_ITEM_KEY;
1675
1676         ref = btrfs_delayed_node_to_tree_ref(node);
1677         if (node->type == BTRFS_SHARED_BLOCK_REF_KEY)
1678                 parent = ref->parent;
1679         else
1680                 ref_root = ref->root;
1681
1682         BUG_ON(node->ref_mod != 1);
1683         if (node->action == BTRFS_ADD_DELAYED_REF && insert_reserved) {
1684                 BUG_ON(!extent_op || !extent_op->update_flags ||
1685                        !extent_op->update_key);
1686                 ret = alloc_reserved_tree_block(trans, root,
1687                                                 parent, ref_root,
1688                                                 extent_op->flags_to_set,
1689                                                 &extent_op->key,
1690                                                 ref->level, &ins);
1691                 update_reserved_extents(root, ins.objectid, ins.offset, 0);
1692         } else if (node->action == BTRFS_ADD_DELAYED_REF) {
1693                 ret = __btrfs_inc_extent_ref(trans, root, node->bytenr,
1694                                              node->num_bytes, parent, ref_root,
1695                                              ref->level, 0, 1, extent_op);
1696         } else if (node->action == BTRFS_DROP_DELAYED_REF) {
1697                 ret = __btrfs_free_extent(trans, root, node->bytenr,
1698                                           node->num_bytes, parent, ref_root,
1699                                           ref->level, 0, 1, extent_op);
1700         } else {
1701                 BUG();
1702         }
1703         return ret;
1704 }
1705
1706
1707 /* helper function to actually process a single delayed ref entry */
1708 static int run_one_delayed_ref(struct btrfs_trans_handle *trans,
1709                                struct btrfs_root *root,
1710                                struct btrfs_delayed_ref_node *node,
1711                                struct btrfs_delayed_extent_op *extent_op,
1712                                int insert_reserved)
1713 {
1714         int ret;
1715         if (btrfs_delayed_ref_is_head(node)) {
1716                 struct btrfs_delayed_ref_head *head;
1717                 /*
1718                  * we've hit the end of the chain and we were supposed
1719                  * to insert this extent into the tree.  But, it got
1720                  * deleted before we ever needed to insert it, so all
1721                  * we have to do is clean up the accounting
1722                  */
1723                 BUG_ON(extent_op);
1724                 head = btrfs_delayed_node_to_head(node);
1725                 if (insert_reserved) {
1726                         if (head->is_data) {
1727                                 ret = btrfs_del_csums(trans, root,
1728                                                       node->bytenr,
1729                                                       node->num_bytes);
1730                                 BUG_ON(ret);
1731                         }
1732                         btrfs_update_pinned_extents(root, node->bytenr,
1733                                                     node->num_bytes, 1);
1734                         update_reserved_extents(root, node->bytenr,
1735                                                 node->num_bytes, 0);
1736                 }
1737                 mutex_unlock(&head->mutex);
1738                 return 0;
1739         }
1740
1741         if (node->type == BTRFS_TREE_BLOCK_REF_KEY ||
1742             node->type == BTRFS_SHARED_BLOCK_REF_KEY)
1743                 ret = run_delayed_tree_ref(trans, root, node, extent_op,
1744                                            insert_reserved);
1745         else if (node->type == BTRFS_EXTENT_DATA_REF_KEY ||
1746                  node->type == BTRFS_SHARED_DATA_REF_KEY)
1747                 ret = run_delayed_data_ref(trans, root, node, extent_op,
1748                                            insert_reserved);
1749         else
1750                 BUG();
1751         return ret;
1752 }
1753
1754 static noinline struct btrfs_delayed_ref_node *
1755 select_delayed_ref(struct btrfs_delayed_ref_head *head)
1756 {
1757         struct rb_node *node;
1758         struct btrfs_delayed_ref_node *ref;
1759         int action = BTRFS_ADD_DELAYED_REF;
1760 again:
1761         /*
1762          * select delayed ref of type BTRFS_ADD_DELAYED_REF first.
1763          * this prevents ref count from going down to zero when
1764          * there still are pending delayed ref.
1765          */
1766         node = rb_prev(&head->node.rb_node);
1767         while (1) {
1768                 if (!node)
1769                         break;
1770                 ref = rb_entry(node, struct btrfs_delayed_ref_node,
1771                                 rb_node);
1772                 if (ref->bytenr != head->node.bytenr)
1773                         break;
1774                 if (ref->action == action)
1775                         return ref;
1776                 node = rb_prev(node);
1777         }
1778         if (action == BTRFS_ADD_DELAYED_REF) {
1779                 action = BTRFS_DROP_DELAYED_REF;
1780                 goto again;
1781         }
1782         return NULL;
1783 }
1784
1785 static noinline int run_clustered_refs(struct btrfs_trans_handle *trans,
1786                                        struct btrfs_root *root,
1787                                        struct list_head *cluster)
1788 {
1789         struct btrfs_delayed_ref_root *delayed_refs;
1790         struct btrfs_delayed_ref_node *ref;
1791         struct btrfs_delayed_ref_head *locked_ref = NULL;
1792         struct btrfs_delayed_extent_op *extent_op;
1793         int ret;
1794         int count = 0;
1795         int must_insert_reserved = 0;
1796
1797         delayed_refs = &trans->transaction->delayed_refs;
1798         while (1) {
1799                 if (!locked_ref) {
1800                         /* pick a new head ref from the cluster list */
1801                         if (list_empty(cluster))
1802                                 break;
1803
1804                         locked_ref = list_entry(cluster->next,
1805                                      struct btrfs_delayed_ref_head, cluster);
1806
1807                         /* grab the lock that says we are going to process
1808                          * all the refs for this head */
1809                         ret = btrfs_delayed_ref_lock(trans, locked_ref);
1810
1811                         /*
1812                          * we may have dropped the spin lock to get the head
1813                          * mutex lock, and that might have given someone else
1814                          * time to free the head.  If that's true, it has been
1815                          * removed from our list and we can move on.
1816                          */
1817                         if (ret == -EAGAIN) {
1818                                 locked_ref = NULL;
1819                                 count++;
1820                                 continue;
1821                         }
1822                 }
1823
1824                 /*
1825                  * record the must insert reserved flag before we
1826                  * drop the spin lock.
1827                  */
1828                 must_insert_reserved = locked_ref->must_insert_reserved;
1829                 locked_ref->must_insert_reserved = 0;
1830
1831                 extent_op = locked_ref->extent_op;
1832                 locked_ref->extent_op = NULL;
1833
1834                 /*
1835                  * locked_ref is the head node, so we have to go one
1836                  * node back for any delayed ref updates
1837                  */
1838                 ref = select_delayed_ref(locked_ref);
1839                 if (!ref) {
1840                         /* All delayed refs have been processed, Go ahead
1841                          * and send the head node to run_one_delayed_ref,
1842                          * so that any accounting fixes can happen
1843                          */
1844                         ref = &locked_ref->node;
1845
1846                         if (extent_op && must_insert_reserved) {
1847                                 kfree(extent_op);
1848                                 extent_op = NULL;
1849                         }
1850
1851                         if (extent_op) {
1852                                 spin_unlock(&delayed_refs->lock);
1853
1854                                 ret = run_delayed_extent_op(trans, root,
1855                                                             ref, extent_op);
1856                                 BUG_ON(ret);
1857                                 kfree(extent_op);
1858
1859                                 cond_resched();
1860                                 spin_lock(&delayed_refs->lock);
1861                                 continue;
1862                         }
1863
1864                         list_del_init(&locked_ref->cluster);
1865                         locked_ref = NULL;
1866                 }
1867
1868                 ref->in_tree = 0;
1869                 rb_erase(&ref->rb_node, &delayed_refs->root);
1870                 delayed_refs->num_entries--;
1871
1872                 spin_unlock(&delayed_refs->lock);
1873
1874                 ret = run_one_delayed_ref(trans, root, ref, extent_op,
1875                                           must_insert_reserved);
1876                 BUG_ON(ret);
1877
1878                 btrfs_put_delayed_ref(ref);
1879                 kfree(extent_op);
1880                 count++;
1881
1882                 cond_resched();
1883                 spin_lock(&delayed_refs->lock);
1884         }
1885         return count;
1886 }
1887
1888 /*
1889  * this starts processing the delayed reference count updates and
1890  * extent insertions we have queued up so far.  count can be
1891  * 0, which means to process everything in the tree at the start
1892  * of the run (but not newly added entries), or it can be some target
1893  * number you'd like to process.
1894  */
1895 int btrfs_run_delayed_refs(struct btrfs_trans_handle *trans,
1896                            struct btrfs_root *root, unsigned long count)
1897 {
1898         struct rb_node *node;
1899         struct btrfs_delayed_ref_root *delayed_refs;
1900         struct btrfs_delayed_ref_node *ref;
1901         struct list_head cluster;
1902         int ret;
1903         int run_all = count == (unsigned long)-1;
1904         int run_most = 0;
1905
1906         if (root == root->fs_info->extent_root)
1907                 root = root->fs_info->tree_root;
1908
1909         delayed_refs = &trans->transaction->delayed_refs;
1910         INIT_LIST_HEAD(&cluster);
1911 again:
1912         spin_lock(&delayed_refs->lock);
1913         if (count == 0) {
1914                 count = delayed_refs->num_entries * 2;
1915                 run_most = 1;
1916         }
1917         while (1) {
1918                 if (!(run_all || run_most) &&
1919                     delayed_refs->num_heads_ready < 64)
1920                         break;
1921
1922                 /*
1923                  * go find something we can process in the rbtree.  We start at
1924                  * the beginning of the tree, and then build a cluster
1925                  * of refs to process starting at the first one we are able to
1926                  * lock
1927                  */
1928                 ret = btrfs_find_ref_cluster(trans, &cluster,
1929                                              delayed_refs->run_delayed_start);
1930                 if (ret)
1931                         break;
1932
1933                 ret = run_clustered_refs(trans, root, &cluster);
1934                 BUG_ON(ret < 0);
1935
1936                 count -= min_t(unsigned long, ret, count);
1937
1938                 if (count == 0)
1939                         break;
1940         }
1941
1942         if (run_all) {
1943                 node = rb_first(&delayed_refs->root);
1944                 if (!node)
1945                         goto out;
1946                 count = (unsigned long)-1;
1947
1948                 while (node) {
1949                         ref = rb_entry(node, struct btrfs_delayed_ref_node,
1950                                        rb_node);
1951                         if (btrfs_delayed_ref_is_head(ref)) {
1952                                 struct btrfs_delayed_ref_head *head;
1953
1954                                 head = btrfs_delayed_node_to_head(ref);
1955                                 atomic_inc(&ref->refs);
1956
1957                                 spin_unlock(&delayed_refs->lock);
1958                                 mutex_lock(&head->mutex);
1959                                 mutex_unlock(&head->mutex);
1960
1961                                 btrfs_put_delayed_ref(ref);
1962                                 cond_resched();
1963                                 goto again;
1964                         }
1965                         node = rb_next(node);
1966                 }
1967                 spin_unlock(&delayed_refs->lock);
1968                 schedule_timeout(1);
1969                 goto again;
1970         }
1971 out:
1972         spin_unlock(&delayed_refs->lock);
1973         return 0;
1974 }
1975
1976 int btrfs_set_disk_extent_flags(struct btrfs_trans_handle *trans,
1977                                 struct btrfs_root *root,
1978                                 u64 bytenr, u64 num_bytes, u64 flags,
1979                                 int is_data)
1980 {
1981         struct btrfs_delayed_extent_op *extent_op;
1982         int ret;
1983
1984         extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
1985         if (!extent_op)
1986                 return -ENOMEM;
1987
1988         extent_op->flags_to_set = flags;
1989         extent_op->update_flags = 1;
1990         extent_op->update_key = 0;
1991         extent_op->is_data = is_data ? 1 : 0;
1992
1993         ret = btrfs_add_delayed_extent_op(trans, bytenr, num_bytes, extent_op);
1994         if (ret)
1995                 kfree(extent_op);
1996         return ret;
1997 }
1998
1999 static noinline int check_delayed_ref(struct btrfs_trans_handle *trans,
2000                                       struct btrfs_root *root,
2001                                       struct btrfs_path *path,
2002                                       u64 objectid, u64 offset, u64 bytenr)
2003 {
2004         struct btrfs_delayed_ref_head *head;
2005         struct btrfs_delayed_ref_node *ref;
2006         struct btrfs_delayed_data_ref *data_ref;
2007         struct btrfs_delayed_ref_root *delayed_refs;
2008         struct rb_node *node;
2009         int ret = 0;
2010
2011         ret = -ENOENT;
2012         delayed_refs = &trans->transaction->delayed_refs;
2013         spin_lock(&delayed_refs->lock);
2014         head = btrfs_find_delayed_ref_head(trans, bytenr);
2015         if (!head)
2016                 goto out;
2017
2018         if (!mutex_trylock(&head->mutex)) {
2019                 atomic_inc(&head->node.refs);
2020                 spin_unlock(&delayed_refs->lock);
2021
2022                 btrfs_release_path(root->fs_info->extent_root, path);
2023
2024                 mutex_lock(&head->mutex);
2025                 mutex_unlock(&head->mutex);
2026                 btrfs_put_delayed_ref(&head->node);
2027                 return -EAGAIN;
2028         }
2029
2030         node = rb_prev(&head->node.rb_node);
2031         if (!node)
2032                 goto out_unlock;
2033
2034         ref = rb_entry(node, struct btrfs_delayed_ref_node, rb_node);
2035
2036         if (ref->bytenr != bytenr)
2037                 goto out_unlock;
2038
2039         ret = 1;
2040         if (ref->type != BTRFS_EXTENT_DATA_REF_KEY)
2041                 goto out_unlock;
2042
2043         data_ref = btrfs_delayed_node_to_data_ref(ref);
2044
2045         node = rb_prev(node);
2046         if (node) {
2047                 ref = rb_entry(node, struct btrfs_delayed_ref_node, rb_node);
2048                 if (ref->bytenr == bytenr)
2049                         goto out_unlock;
2050         }
2051
2052         if (data_ref->root != root->root_key.objectid ||
2053             data_ref->objectid != objectid || data_ref->offset != offset)
2054                 goto out_unlock;
2055
2056         ret = 0;
2057 out_unlock:
2058         mutex_unlock(&head->mutex);
2059 out:
2060         spin_unlock(&delayed_refs->lock);
2061         return ret;
2062 }
2063
2064 static noinline int check_committed_ref(struct btrfs_trans_handle *trans,
2065                                         struct btrfs_root *root,
2066                                         struct btrfs_path *path,
2067                                         u64 objectid, u64 offset, u64 bytenr)
2068 {
2069         struct btrfs_root *extent_root = root->fs_info->extent_root;
2070         struct extent_buffer *leaf;
2071         struct btrfs_extent_data_ref *ref;
2072         struct btrfs_extent_inline_ref *iref;
2073         struct btrfs_extent_item *ei;
2074         struct btrfs_key key;
2075         u32 item_size;
2076         int ret;
2077
2078         key.objectid = bytenr;
2079         key.offset = (u64)-1;
2080         key.type = BTRFS_EXTENT_ITEM_KEY;
2081
2082         ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
2083         if (ret < 0)
2084                 goto out;
2085         BUG_ON(ret == 0);
2086
2087         ret = -ENOENT;
2088         if (path->slots[0] == 0)
2089                 goto out;
2090
2091         path->slots[0]--;
2092         leaf = path->nodes[0];
2093         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
2094
2095         if (key.objectid != bytenr || key.type != BTRFS_EXTENT_ITEM_KEY)
2096                 goto out;
2097
2098         ret = 1;
2099         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
2100 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2101         if (item_size < sizeof(*ei)) {
2102                 WARN_ON(item_size != sizeof(struct btrfs_extent_item_v0));
2103                 goto out;
2104         }
2105 #endif
2106         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
2107
2108         if (item_size != sizeof(*ei) +
2109             btrfs_extent_inline_ref_size(BTRFS_EXTENT_DATA_REF_KEY))
2110                 goto out;
2111
2112         if (btrfs_extent_generation(leaf, ei) <=
2113             btrfs_root_last_snapshot(&root->root_item))
2114                 goto out;
2115
2116         iref = (struct btrfs_extent_inline_ref *)(ei + 1);
2117         if (btrfs_extent_inline_ref_type(leaf, iref) !=
2118             BTRFS_EXTENT_DATA_REF_KEY)
2119                 goto out;
2120
2121         ref = (struct btrfs_extent_data_ref *)(&iref->offset);
2122         if (btrfs_extent_refs(leaf, ei) !=
2123             btrfs_extent_data_ref_count(leaf, ref) ||
2124             btrfs_extent_data_ref_root(leaf, ref) !=
2125             root->root_key.objectid ||
2126             btrfs_extent_data_ref_objectid(leaf, ref) != objectid ||
2127             btrfs_extent_data_ref_offset(leaf, ref) != offset)
2128                 goto out;
2129
2130         ret = 0;
2131 out:
2132         return ret;
2133 }
2134
2135 int btrfs_cross_ref_exist(struct btrfs_trans_handle *trans,
2136                           struct btrfs_root *root,
2137                           u64 objectid, u64 offset, u64 bytenr)
2138 {
2139         struct btrfs_path *path;
2140         int ret;
2141         int ret2;
2142
2143         path = btrfs_alloc_path();
2144         if (!path)
2145                 return -ENOENT;
2146
2147         do {
2148                 ret = check_committed_ref(trans, root, path, objectid,
2149                                           offset, bytenr);
2150                 if (ret && ret != -ENOENT)
2151                         goto out;
2152
2153                 ret2 = check_delayed_ref(trans, root, path, objectid,
2154                                          offset, bytenr);
2155         } while (ret2 == -EAGAIN);
2156
2157         if (ret2 && ret2 != -ENOENT) {
2158                 ret = ret2;
2159                 goto out;
2160         }
2161
2162         if (ret != -ENOENT || ret2 != -ENOENT)
2163                 ret = 0;
2164 out:
2165         btrfs_free_path(path);
2166         return ret;
2167 }
2168
2169 #if 0
2170 int btrfs_cache_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2171                     struct extent_buffer *buf, u32 nr_extents)
2172 {
2173         struct btrfs_key key;
2174         struct btrfs_file_extent_item *fi;
2175         u64 root_gen;
2176         u32 nritems;
2177         int i;
2178         int level;
2179         int ret = 0;
2180         int shared = 0;
2181
2182         if (!root->ref_cows)
2183                 return 0;
2184
2185         if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
2186                 shared = 0;
2187                 root_gen = root->root_key.offset;
2188         } else {
2189                 shared = 1;
2190                 root_gen = trans->transid - 1;
2191         }
2192
2193         level = btrfs_header_level(buf);
2194         nritems = btrfs_header_nritems(buf);
2195
2196         if (level == 0) {
2197                 struct btrfs_leaf_ref *ref;
2198                 struct btrfs_extent_info *info;
2199
2200                 ref = btrfs_alloc_leaf_ref(root, nr_extents);
2201                 if (!ref) {
2202                         ret = -ENOMEM;
2203                         goto out;
2204                 }
2205
2206                 ref->root_gen = root_gen;
2207                 ref->bytenr = buf->start;
2208                 ref->owner = btrfs_header_owner(buf);
2209                 ref->generation = btrfs_header_generation(buf);
2210                 ref->nritems = nr_extents;
2211                 info = ref->extents;
2212
2213                 for (i = 0; nr_extents > 0 && i < nritems; i++) {
2214                         u64 disk_bytenr;
2215                         btrfs_item_key_to_cpu(buf, &key, i);
2216                         if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
2217                                 continue;
2218                         fi = btrfs_item_ptr(buf, i,
2219                                             struct btrfs_file_extent_item);
2220                         if (btrfs_file_extent_type(buf, fi) ==
2221                             BTRFS_FILE_EXTENT_INLINE)
2222                                 continue;
2223                         disk_bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
2224                         if (disk_bytenr == 0)
2225                                 continue;
2226
2227                         info->bytenr = disk_bytenr;
2228                         info->num_bytes =
2229                                 btrfs_file_extent_disk_num_bytes(buf, fi);
2230                         info->objectid = key.objectid;
2231                         info->offset = key.offset;
2232                         info++;
2233                 }
2234
2235                 ret = btrfs_add_leaf_ref(root, ref, shared);
2236                 if (ret == -EEXIST && shared) {
2237                         struct btrfs_leaf_ref *old;
2238                         old = btrfs_lookup_leaf_ref(root, ref->bytenr);
2239                         BUG_ON(!old);
2240                         btrfs_remove_leaf_ref(root, old);
2241                         btrfs_free_leaf_ref(root, old);
2242                         ret = btrfs_add_leaf_ref(root, ref, shared);
2243                 }
2244                 WARN_ON(ret);
2245                 btrfs_free_leaf_ref(root, ref);
2246         }
2247 out:
2248         return ret;
2249 }
2250
2251 /* when a block goes through cow, we update the reference counts of
2252  * everything that block points to.  The internal pointers of the block
2253  * can be in just about any order, and it is likely to have clusters of
2254  * things that are close together and clusters of things that are not.
2255  *
2256  * To help reduce the seeks that come with updating all of these reference
2257  * counts, sort them by byte number before actual updates are done.
2258  *
2259  * struct refsort is used to match byte number to slot in the btree block.
2260  * we sort based on the byte number and then use the slot to actually
2261  * find the item.
2262  *
2263  * struct refsort is smaller than strcut btrfs_item and smaller than
2264  * struct btrfs_key_ptr.  Since we're currently limited to the page size
2265  * for a btree block, there's no way for a kmalloc of refsorts for a
2266  * single node to be bigger than a page.
2267  */
2268 struct refsort {
2269         u64 bytenr;
2270         u32 slot;
2271 };
2272
2273 /*
2274  * for passing into sort()
2275  */
2276 static int refsort_cmp(const void *a_void, const void *b_void)
2277 {
2278         const struct refsort *a = a_void;
2279         const struct refsort *b = b_void;
2280
2281         if (a->bytenr < b->bytenr)
2282                 return -1;
2283         if (a->bytenr > b->bytenr)
2284                 return 1;
2285         return 0;
2286 }
2287 #endif
2288
2289 static int __btrfs_mod_ref(struct btrfs_trans_handle *trans,
2290                            struct btrfs_root *root,
2291                            struct extent_buffer *buf,
2292                            int full_backref, int inc)
2293 {
2294         u64 bytenr;
2295         u64 num_bytes;
2296         u64 parent;
2297         u64 ref_root;
2298         u32 nritems;
2299         struct btrfs_key key;
2300         struct btrfs_file_extent_item *fi;
2301         int i;
2302         int level;
2303         int ret = 0;
2304         int (*process_func)(struct btrfs_trans_handle *, struct btrfs_root *,
2305                             u64, u64, u64, u64, u64, u64);
2306
2307         ref_root = btrfs_header_owner(buf);
2308         nritems = btrfs_header_nritems(buf);
2309         level = btrfs_header_level(buf);
2310
2311         if (!root->ref_cows && level == 0)
2312                 return 0;
2313
2314         if (inc)
2315                 process_func = btrfs_inc_extent_ref;
2316         else
2317                 process_func = btrfs_free_extent;
2318
2319         if (full_backref)
2320                 parent = buf->start;
2321         else
2322                 parent = 0;
2323
2324         for (i = 0; i < nritems; i++) {
2325                 if (level == 0) {
2326                         btrfs_item_key_to_cpu(buf, &key, i);
2327                         if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
2328                                 continue;
2329                         fi = btrfs_item_ptr(buf, i,
2330                                             struct btrfs_file_extent_item);
2331                         if (btrfs_file_extent_type(buf, fi) ==
2332                             BTRFS_FILE_EXTENT_INLINE)
2333                                 continue;
2334                         bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
2335                         if (bytenr == 0)
2336                                 continue;
2337
2338                         num_bytes = btrfs_file_extent_disk_num_bytes(buf, fi);
2339                         key.offset -= btrfs_file_extent_offset(buf, fi);
2340                         ret = process_func(trans, root, bytenr, num_bytes,
2341                                            parent, ref_root, key.objectid,
2342                                            key.offset);
2343                         if (ret)
2344                                 goto fail;
2345                 } else {
2346                         bytenr = btrfs_node_blockptr(buf, i);
2347                         num_bytes = btrfs_level_size(root, level - 1);
2348                         ret = process_func(trans, root, bytenr, num_bytes,
2349                                            parent, ref_root, level - 1, 0);
2350                         if (ret)
2351                                 goto fail;
2352                 }
2353         }
2354         return 0;
2355 fail:
2356         BUG();
2357         return ret;
2358 }
2359
2360 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2361                   struct extent_buffer *buf, int full_backref)
2362 {
2363         return __btrfs_mod_ref(trans, root, buf, full_backref, 1);
2364 }
2365
2366 int btrfs_dec_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2367                   struct extent_buffer *buf, int full_backref)
2368 {
2369         return __btrfs_mod_ref(trans, root, buf, full_backref, 0);
2370 }
2371
2372 static int write_one_cache_group(struct btrfs_trans_handle *trans,
2373                                  struct btrfs_root *root,
2374                                  struct btrfs_path *path,
2375                                  struct btrfs_block_group_cache *cache)
2376 {
2377         int ret;
2378         struct btrfs_root *extent_root = root->fs_info->extent_root;
2379         unsigned long bi;
2380         struct extent_buffer *leaf;
2381
2382         ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
2383         if (ret < 0)
2384                 goto fail;
2385         BUG_ON(ret);
2386
2387         leaf = path->nodes[0];
2388         bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
2389         write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
2390         btrfs_mark_buffer_dirty(leaf);
2391         btrfs_release_path(extent_root, path);
2392 fail:
2393         if (ret)
2394                 return ret;
2395         return 0;
2396
2397 }
2398
2399 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans,
2400                                    struct btrfs_root *root)
2401 {
2402         struct btrfs_block_group_cache *cache, *entry;
2403         struct rb_node *n;
2404         int err = 0;
2405         int werr = 0;
2406         struct btrfs_path *path;
2407         u64 last = 0;
2408
2409         path = btrfs_alloc_path();
2410         if (!path)
2411                 return -ENOMEM;
2412
2413         while (1) {
2414                 cache = NULL;
2415                 spin_lock(&root->fs_info->block_group_cache_lock);
2416                 for (n = rb_first(&root->fs_info->block_group_cache_tree);
2417                      n; n = rb_next(n)) {
2418                         entry = rb_entry(n, struct btrfs_block_group_cache,
2419                                          cache_node);
2420                         if (entry->dirty) {
2421                                 cache = entry;
2422                                 break;
2423                         }
2424                 }
2425                 spin_unlock(&root->fs_info->block_group_cache_lock);
2426
2427                 if (!cache)
2428                         break;
2429
2430                 cache->dirty = 0;
2431                 last += cache->key.offset;
2432
2433                 err = write_one_cache_group(trans, root,
2434                                             path, cache);
2435                 /*
2436                  * if we fail to write the cache group, we want
2437                  * to keep it marked dirty in hopes that a later
2438                  * write will work
2439                  */
2440                 if (err) {
2441                         werr = err;
2442                         continue;
2443                 }
2444         }
2445         btrfs_free_path(path);
2446         return werr;
2447 }
2448
2449 int btrfs_extent_readonly(struct btrfs_root *root, u64 bytenr)
2450 {
2451         struct btrfs_block_group_cache *block_group;
2452         int readonly = 0;
2453
2454         block_group = btrfs_lookup_block_group(root->fs_info, bytenr);
2455         if (!block_group || block_group->ro)
2456                 readonly = 1;
2457         if (block_group)
2458                 btrfs_put_block_group(block_group);
2459         return readonly;
2460 }
2461
2462 static int update_space_info(struct btrfs_fs_info *info, u64 flags,
2463                              u64 total_bytes, u64 bytes_used,
2464                              struct btrfs_space_info **space_info)
2465 {
2466         struct btrfs_space_info *found;
2467
2468         found = __find_space_info(info, flags);
2469         if (found) {
2470                 spin_lock(&found->lock);
2471                 found->total_bytes += total_bytes;
2472                 found->bytes_used += bytes_used;
2473                 found->full = 0;
2474                 spin_unlock(&found->lock);
2475                 *space_info = found;
2476                 return 0;
2477         }
2478         found = kzalloc(sizeof(*found), GFP_NOFS);
2479         if (!found)
2480                 return -ENOMEM;
2481
2482         INIT_LIST_HEAD(&found->block_groups);
2483         init_rwsem(&found->groups_sem);
2484         spin_lock_init(&found->lock);
2485         found->flags = flags;
2486         found->total_bytes = total_bytes;
2487         found->bytes_used = bytes_used;
2488         found->bytes_pinned = 0;
2489         found->bytes_reserved = 0;
2490         found->bytes_readonly = 0;
2491         found->bytes_delalloc = 0;
2492         found->full = 0;
2493         found->force_alloc = 0;
2494         *space_info = found;
2495         list_add_rcu(&found->list, &info->space_info);
2496         return 0;
2497 }
2498
2499 static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
2500 {
2501         u64 extra_flags = flags & (BTRFS_BLOCK_GROUP_RAID0 |
2502                                    BTRFS_BLOCK_GROUP_RAID1 |
2503                                    BTRFS_BLOCK_GROUP_RAID10 |
2504                                    BTRFS_BLOCK_GROUP_DUP);
2505         if (extra_flags) {
2506                 if (flags & BTRFS_BLOCK_GROUP_DATA)
2507                         fs_info->avail_data_alloc_bits |= extra_flags;
2508                 if (flags & BTRFS_BLOCK_GROUP_METADATA)
2509                         fs_info->avail_metadata_alloc_bits |= extra_flags;
2510                 if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
2511                         fs_info->avail_system_alloc_bits |= extra_flags;
2512         }
2513 }
2514
2515 static void set_block_group_readonly(struct btrfs_block_group_cache *cache)
2516 {
2517         spin_lock(&cache->space_info->lock);
2518         spin_lock(&cache->lock);
2519         if (!cache->ro) {
2520                 cache->space_info->bytes_readonly += cache->key.offset -
2521                                         btrfs_block_group_used(&cache->item);
2522                 cache->ro = 1;
2523         }
2524         spin_unlock(&cache->lock);
2525         spin_unlock(&cache->space_info->lock);
2526 }
2527
2528 u64 btrfs_reduce_alloc_profile(struct btrfs_root *root, u64 flags)
2529 {
2530         u64 num_devices = root->fs_info->fs_devices->rw_devices;
2531
2532         if (num_devices == 1)
2533                 flags &= ~(BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_RAID0);
2534         if (num_devices < 4)
2535                 flags &= ~BTRFS_BLOCK_GROUP_RAID10;
2536
2537         if ((flags & BTRFS_BLOCK_GROUP_DUP) &&
2538             (flags & (BTRFS_BLOCK_GROUP_RAID1 |
2539                       BTRFS_BLOCK_GROUP_RAID10))) {
2540                 flags &= ~BTRFS_BLOCK_GROUP_DUP;
2541         }
2542
2543         if ((flags & BTRFS_BLOCK_GROUP_RAID1) &&
2544             (flags & BTRFS_BLOCK_GROUP_RAID10)) {
2545                 flags &= ~BTRFS_BLOCK_GROUP_RAID1;
2546         }
2547
2548         if ((flags & BTRFS_BLOCK_GROUP_RAID0) &&
2549             ((flags & BTRFS_BLOCK_GROUP_RAID1) |
2550              (flags & BTRFS_BLOCK_GROUP_RAID10) |
2551              (flags & BTRFS_BLOCK_GROUP_DUP)))
2552                 flags &= ~BTRFS_BLOCK_GROUP_RAID0;
2553         return flags;
2554 }
2555
2556 static u64 btrfs_get_alloc_profile(struct btrfs_root *root, u64 data)
2557 {
2558         struct btrfs_fs_info *info = root->fs_info;
2559         u64 alloc_profile;
2560
2561         if (data) {
2562                 alloc_profile = info->avail_data_alloc_bits &
2563                         info->data_alloc_profile;
2564                 data = BTRFS_BLOCK_GROUP_DATA | alloc_profile;
2565         } else if (root == root->fs_info->chunk_root) {
2566                 alloc_profile = info->avail_system_alloc_bits &
2567                         info->system_alloc_profile;
2568                 data = BTRFS_BLOCK_GROUP_SYSTEM | alloc_profile;
2569         } else {
2570                 alloc_profile = info->avail_metadata_alloc_bits &
2571                         info->metadata_alloc_profile;
2572                 data = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
2573         }
2574
2575         return btrfs_reduce_alloc_profile(root, data);
2576 }
2577
2578 void btrfs_set_inode_space_info(struct btrfs_root *root, struct inode *inode)
2579 {
2580         u64 alloc_target;
2581
2582         alloc_target = btrfs_get_alloc_profile(root, 1);
2583         BTRFS_I(inode)->space_info = __find_space_info(root->fs_info,
2584                                                        alloc_target);
2585 }
2586
2587 /*
2588  * for now this just makes sure we have at least 5% of our metadata space free
2589  * for use.
2590  */
2591 int btrfs_check_metadata_free_space(struct btrfs_root *root)
2592 {
2593         struct btrfs_fs_info *info = root->fs_info;
2594         struct btrfs_space_info *meta_sinfo;
2595         u64 alloc_target, thresh;
2596         int committed = 0, ret;
2597
2598         /* get the space info for where the metadata will live */
2599         alloc_target = btrfs_get_alloc_profile(root, 0);
2600         meta_sinfo = __find_space_info(info, alloc_target);
2601
2602 again:
2603         spin_lock(&meta_sinfo->lock);
2604         if (!meta_sinfo->full)
2605                 thresh = meta_sinfo->total_bytes * 80;
2606         else
2607                 thresh = meta_sinfo->total_bytes * 95;
2608
2609         do_div(thresh, 100);
2610
2611         if (meta_sinfo->bytes_used + meta_sinfo->bytes_reserved +
2612             meta_sinfo->bytes_pinned + meta_sinfo->bytes_readonly > thresh) {
2613                 struct btrfs_trans_handle *trans;
2614                 if (!meta_sinfo->full) {
2615                         meta_sinfo->force_alloc = 1;
2616                         spin_unlock(&meta_sinfo->lock);
2617
2618                         trans = btrfs_start_transaction(root, 1);
2619                         if (!trans)
2620                                 return -ENOMEM;
2621
2622                         ret = do_chunk_alloc(trans, root->fs_info->extent_root,
2623                                              2 * 1024 * 1024, alloc_target, 0);
2624                         btrfs_end_transaction(trans, root);
2625                         goto again;
2626                 }
2627                 spin_unlock(&meta_sinfo->lock);
2628
2629                 if (!committed) {
2630                         committed = 1;
2631                         trans = btrfs_join_transaction(root, 1);
2632                         if (!trans)
2633                                 return -ENOMEM;
2634                         ret = btrfs_commit_transaction(trans, root);
2635                         if (ret)
2636                                 return ret;
2637                         goto again;
2638                 }
2639                 return -ENOSPC;
2640         }
2641         spin_unlock(&meta_sinfo->lock);
2642
2643         return 0;
2644 }
2645
2646 /*
2647  * This will check the space that the inode allocates from to make sure we have
2648  * enough space for bytes.
2649  */
2650 int btrfs_check_data_free_space(struct btrfs_root *root, struct inode *inode,
2651                                 u64 bytes)
2652 {
2653         struct btrfs_space_info *data_sinfo;
2654         int ret = 0, committed = 0;
2655
2656         /* make sure bytes are sectorsize aligned */
2657         bytes = (bytes + root->sectorsize - 1) & ~((u64)root->sectorsize - 1);
2658
2659         data_sinfo = BTRFS_I(inode)->space_info;
2660 again:
2661         /* make sure we have enough space to handle the data first */
2662         spin_lock(&data_sinfo->lock);
2663         if (data_sinfo->total_bytes - data_sinfo->bytes_used -
2664             data_sinfo->bytes_delalloc - data_sinfo->bytes_reserved -
2665             data_sinfo->bytes_pinned - data_sinfo->bytes_readonly -
2666             data_sinfo->bytes_may_use < bytes) {
2667                 struct btrfs_trans_handle *trans;
2668
2669                 /*
2670                  * if we don't have enough free bytes in this space then we need
2671                  * to alloc a new chunk.
2672                  */
2673                 if (!data_sinfo->full) {
2674                         u64 alloc_target;
2675
2676                         data_sinfo->force_alloc = 1;
2677                         spin_unlock(&data_sinfo->lock);
2678
2679                         alloc_target = btrfs_get_alloc_profile(root, 1);
2680                         trans = btrfs_start_transaction(root, 1);
2681                         if (!trans)
2682                                 return -ENOMEM;
2683
2684                         ret = do_chunk_alloc(trans, root->fs_info->extent_root,
2685                                              bytes + 2 * 1024 * 1024,
2686                                              alloc_target, 0);
2687                         btrfs_end_transaction(trans, root);
2688                         if (ret)
2689                                 return ret;
2690                         goto again;
2691                 }
2692                 spin_unlock(&data_sinfo->lock);
2693
2694                 /* commit the current transaction and try again */
2695                 if (!committed) {
2696                         committed = 1;
2697                         trans = btrfs_join_transaction(root, 1);
2698                         if (!trans)
2699                                 return -ENOMEM;
2700                         ret = btrfs_commit_transaction(trans, root);
2701                         if (ret)
2702                                 return ret;
2703                         goto again;
2704                 }
2705
2706                 printk(KERN_ERR "no space left, need %llu, %llu delalloc bytes"
2707                        ", %llu bytes_used, %llu bytes_reserved, "
2708                        "%llu bytes_pinned, %llu bytes_readonly, %llu may use"
2709                        "%llu total\n", (unsigned long long)bytes,
2710                        (unsigned long long)data_sinfo->bytes_delalloc,
2711                        (unsigned long long)data_sinfo->bytes_used,
2712                        (unsigned long long)data_sinfo->bytes_reserved,
2713                        (unsigned long long)data_sinfo->bytes_pinned,
2714                        (unsigned long long)data_sinfo->bytes_readonly,
2715                        (unsigned long long)data_sinfo->bytes_may_use,
2716                        (unsigned long long)data_sinfo->total_bytes);
2717                 return -ENOSPC;
2718         }
2719         data_sinfo->bytes_may_use += bytes;
2720         BTRFS_I(inode)->reserved_bytes += bytes;
2721         spin_unlock(&data_sinfo->lock);
2722
2723         return btrfs_check_metadata_free_space(root);
2724 }
2725
2726 /*
2727  * if there was an error for whatever reason after calling
2728  * btrfs_check_data_free_space, call this so we can cleanup the counters.
2729  */
2730 void btrfs_free_reserved_data_space(struct btrfs_root *root,
2731                                     struct inode *inode, u64 bytes)
2732 {
2733         struct btrfs_space_info *data_sinfo;
2734
2735         /* make sure bytes are sectorsize aligned */
2736         bytes = (bytes + root->sectorsize - 1) & ~((u64)root->sectorsize - 1);
2737
2738         data_sinfo = BTRFS_I(inode)->space_info;
2739         spin_lock(&data_sinfo->lock);
2740         data_sinfo->bytes_may_use -= bytes;
2741         BTRFS_I(inode)->reserved_bytes -= bytes;
2742         spin_unlock(&data_sinfo->lock);
2743 }
2744
2745 /* called when we are adding a delalloc extent to the inode's io_tree */
2746 void btrfs_delalloc_reserve_space(struct btrfs_root *root, struct inode *inode,
2747                                   u64 bytes)
2748 {
2749         struct btrfs_space_info *data_sinfo;
2750
2751         /* get the space info for where this inode will be storing its data */
2752         data_sinfo = BTRFS_I(inode)->space_info;
2753
2754         /* make sure we have enough space to handle the data first */
2755         spin_lock(&data_sinfo->lock);
2756         data_sinfo->bytes_delalloc += bytes;
2757
2758         /*
2759          * we are adding a delalloc extent without calling
2760          * btrfs_check_data_free_space first.  This happens on a weird
2761          * writepage condition, but shouldn't hurt our accounting
2762          */
2763         if (unlikely(bytes > BTRFS_I(inode)->reserved_bytes)) {
2764                 data_sinfo->bytes_may_use -= BTRFS_I(inode)->reserved_bytes;
2765                 BTRFS_I(inode)->reserved_bytes = 0;
2766         } else {
2767                 data_sinfo->bytes_may_use -= bytes;
2768                 BTRFS_I(inode)->reserved_bytes -= bytes;
2769         }
2770
2771         spin_unlock(&data_sinfo->lock);
2772 }
2773
2774 /* called when we are clearing an delalloc extent from the inode's io_tree */
2775 void btrfs_delalloc_free_space(struct btrfs_root *root, struct inode *inode,
2776                               u64 bytes)
2777 {
2778         struct btrfs_space_info *info;
2779
2780         info = BTRFS_I(inode)->space_info;
2781
2782         spin_lock(&info->lock);
2783         info->bytes_delalloc -= bytes;
2784         spin_unlock(&info->lock);
2785 }
2786
2787 static void force_metadata_allocation(struct btrfs_fs_info *info)
2788 {
2789         struct list_head *head = &info->space_info;
2790         struct btrfs_space_info *found;
2791
2792         rcu_read_lock();
2793         list_for_each_entry_rcu(found, head, list) {
2794                 if (found->flags & BTRFS_BLOCK_GROUP_METADATA)
2795                         found->force_alloc = 1;
2796         }
2797         rcu_read_unlock();
2798 }
2799
2800 static int do_chunk_alloc(struct btrfs_trans_handle *trans,
2801                           struct btrfs_root *extent_root, u64 alloc_bytes,
2802                           u64 flags, int force)
2803 {
2804         struct btrfs_space_info *space_info;
2805         struct btrfs_fs_info *fs_info = extent_root->fs_info;
2806         u64 thresh;
2807         int ret = 0;
2808
2809         mutex_lock(&fs_info->chunk_mutex);
2810
2811         flags = btrfs_reduce_alloc_profile(extent_root, flags);
2812
2813         space_info = __find_space_info(extent_root->fs_info, flags);
2814         if (!space_info) {
2815                 ret = update_space_info(extent_root->fs_info, flags,
2816                                         0, 0, &space_info);
2817                 BUG_ON(ret);
2818         }
2819         BUG_ON(!space_info);
2820
2821         spin_lock(&space_info->lock);
2822         if (space_info->force_alloc) {
2823                 force = 1;
2824                 space_info->force_alloc = 0;
2825         }
2826         if (space_info->full) {
2827                 spin_unlock(&space_info->lock);
2828                 goto out;
2829         }
2830
2831         thresh = space_info->total_bytes - space_info->bytes_readonly;
2832         thresh = div_factor(thresh, 6);
2833         if (!force &&
2834            (space_info->bytes_used + space_info->bytes_pinned +
2835             space_info->bytes_reserved + alloc_bytes) < thresh) {
2836                 spin_unlock(&space_info->lock);
2837                 goto out;
2838         }
2839         spin_unlock(&space_info->lock);
2840
2841         /*
2842          * if we're doing a data chunk, go ahead and make sure that
2843          * we keep a reasonable number of metadata chunks allocated in the
2844          * FS as well.
2845          */
2846         if (flags & BTRFS_BLOCK_GROUP_DATA) {
2847                 fs_info->data_chunk_allocations++;
2848                 if (!(fs_info->data_chunk_allocations %
2849                       fs_info->metadata_ratio))
2850                         force_metadata_allocation(fs_info);
2851         }
2852
2853         ret = btrfs_alloc_chunk(trans, extent_root, flags);
2854         if (ret)
2855                 space_info->full = 1;
2856 out:
2857         mutex_unlock(&extent_root->fs_info->chunk_mutex);
2858         return ret;
2859 }
2860
2861 static int update_block_group(struct btrfs_trans_handle *trans,
2862                               struct btrfs_root *root,
2863                               u64 bytenr, u64 num_bytes, int alloc,
2864                               int mark_free)
2865 {
2866         struct btrfs_block_group_cache *cache;
2867         struct btrfs_fs_info *info = root->fs_info;
2868         u64 total = num_bytes;
2869         u64 old_val;
2870         u64 byte_in_group;
2871
2872         /* block accounting for super block */
2873         spin_lock(&info->delalloc_lock);
2874         old_val = btrfs_super_bytes_used(&info->super_copy);
2875         if (alloc)
2876                 old_val += num_bytes;
2877         else
2878                 old_val -= num_bytes;
2879         btrfs_set_super_bytes_used(&info->super_copy, old_val);
2880
2881         /* block accounting for root item */
2882         old_val = btrfs_root_used(&root->root_item);
2883         if (alloc)
2884                 old_val += num_bytes;
2885         else
2886                 old_val -= num_bytes;
2887         btrfs_set_root_used(&root->root_item, old_val);
2888         spin_unlock(&info->delalloc_lock);
2889
2890         while (total) {
2891                 cache = btrfs_lookup_block_group(info, bytenr);
2892                 if (!cache)
2893                         return -1;
2894                 byte_in_group = bytenr - cache->key.objectid;
2895                 WARN_ON(byte_in_group > cache->key.offset);
2896
2897                 spin_lock(&cache->space_info->lock);
2898                 spin_lock(&cache->lock);
2899                 cache->dirty = 1;
2900                 old_val = btrfs_block_group_used(&cache->item);
2901                 num_bytes = min(total, cache->key.offset - byte_in_group);
2902                 if (alloc) {
2903                         old_val += num_bytes;
2904                         cache->space_info->bytes_used += num_bytes;
2905                         if (cache->ro)
2906                                 cache->space_info->bytes_readonly -= num_bytes;
2907                         btrfs_set_block_group_used(&cache->item, old_val);
2908                         spin_unlock(&cache->lock);
2909                         spin_unlock(&cache->space_info->lock);
2910                 } else {
2911                         old_val -= num_bytes;
2912                         cache->space_info->bytes_used -= num_bytes;
2913                         if (cache->ro)
2914                                 cache->space_info->bytes_readonly += num_bytes;
2915                         btrfs_set_block_group_used(&cache->item, old_val);
2916                         spin_unlock(&cache->lock);
2917                         spin_unlock(&cache->space_info->lock);
2918                         if (mark_free) {
2919                                 int ret;
2920
2921                                 ret = btrfs_discard_extent(root, bytenr,
2922                                                            num_bytes);
2923                                 WARN_ON(ret);
2924
2925                                 ret = btrfs_add_free_space(cache, bytenr,
2926                                                            num_bytes);
2927                                 WARN_ON(ret);
2928                         }
2929                 }
2930                 btrfs_put_block_group(cache);
2931                 total -= num_bytes;
2932                 bytenr += num_bytes;
2933         }
2934         return 0;
2935 }
2936
2937 static u64 first_logical_byte(struct btrfs_root *root, u64 search_start)
2938 {
2939         struct btrfs_block_group_cache *cache;
2940         u64 bytenr;
2941
2942         cache = btrfs_lookup_first_block_group(root->fs_info, search_start);
2943         if (!cache)
2944                 return 0;
2945
2946         bytenr = cache->key.objectid;
2947         btrfs_put_block_group(cache);
2948
2949         return bytenr;
2950 }
2951
2952 int btrfs_update_pinned_extents(struct btrfs_root *root,
2953                                 u64 bytenr, u64 num, int pin)
2954 {
2955         u64 len;
2956         struct btrfs_block_group_cache *cache;
2957         struct btrfs_fs_info *fs_info = root->fs_info;
2958
2959         if (pin) {
2960                 set_extent_dirty(&fs_info->pinned_extents,
2961                                 bytenr, bytenr + num - 1, GFP_NOFS);
2962         } else {
2963                 clear_extent_dirty(&fs_info->pinned_extents,
2964                                 bytenr, bytenr + num - 1, GFP_NOFS);
2965         }
2966
2967         while (num > 0) {
2968                 cache = btrfs_lookup_block_group(fs_info, bytenr);
2969                 BUG_ON(!cache);
2970                 len = min(num, cache->key.offset -
2971                           (bytenr - cache->key.objectid));
2972                 if (pin) {
2973                         spin_lock(&cache->space_info->lock);
2974                         spin_lock(&cache->lock);
2975                         cache->pinned += len;
2976                         cache->space_info->bytes_pinned += len;
2977                         spin_unlock(&cache->lock);
2978                         spin_unlock(&cache->space_info->lock);
2979                         fs_info->total_pinned += len;
2980                 } else {
2981                         spin_lock(&cache->space_info->lock);
2982                         spin_lock(&cache->lock);
2983                         cache->pinned -= len;
2984                         cache->space_info->bytes_pinned -= len;
2985                         spin_unlock(&cache->lock);
2986                         spin_unlock(&cache->space_info->lock);
2987                         fs_info->total_pinned -= len;
2988                         if (cache->cached)
2989                                 btrfs_add_free_space(cache, bytenr, len);
2990                 }
2991                 btrfs_put_block_group(cache);
2992                 bytenr += len;
2993                 num -= len;
2994         }
2995         return 0;
2996 }
2997
2998 static int update_reserved_extents(struct btrfs_root *root,
2999                                    u64 bytenr, u64 num, int reserve)
3000 {
3001         u64 len;
3002         struct btrfs_block_group_cache *cache;
3003         struct btrfs_fs_info *fs_info = root->fs_info;
3004
3005         while (num > 0) {
3006                 cache = btrfs_lookup_block_group(fs_info, bytenr);
3007                 BUG_ON(!cache);
3008                 len = min(num, cache->key.offset -
3009                           (bytenr - cache->key.objectid));
3010
3011                 spin_lock(&cache->space_info->lock);
3012                 spin_lock(&cache->lock);
3013                 if (reserve) {
3014                         cache->reserved += len;
3015                         cache->space_info->bytes_reserved += len;
3016                 } else {
3017                         cache->reserved -= len;
3018                         cache->space_info->bytes_reserved -= len;
3019                 }
3020                 spin_unlock(&cache->lock);
3021                 spin_unlock(&cache->space_info->lock);
3022                 btrfs_put_block_group(cache);
3023                 bytenr += len;
3024                 num -= len;
3025         }
3026         return 0;
3027 }
3028
3029 int btrfs_copy_pinned(struct btrfs_root *root, struct extent_io_tree *copy)
3030 {
3031         u64 last = 0;
3032         u64 start;
3033         u64 end;
3034         struct extent_io_tree *pinned_extents = &root->fs_info->pinned_extents;
3035         int ret;
3036
3037         while (1) {
3038                 ret = find_first_extent_bit(pinned_extents, last,
3039                                             &start, &end, EXTENT_DIRTY);
3040                 if (ret)
3041                         break;
3042                 set_extent_dirty(copy, start, end, GFP_NOFS);
3043                 last = end + 1;
3044         }
3045         return 0;
3046 }
3047
3048 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans,
3049                                struct btrfs_root *root,
3050                                struct extent_io_tree *unpin)
3051 {
3052         u64 start;
3053         u64 end;
3054         int ret;
3055
3056         while (1) {
3057                 ret = find_first_extent_bit(unpin, 0, &start, &end,
3058                                             EXTENT_DIRTY);
3059                 if (ret)
3060                         break;
3061
3062                 ret = btrfs_discard_extent(root, start, end + 1 - start);
3063
3064                 /* unlocks the pinned mutex */
3065                 btrfs_update_pinned_extents(root, start, end + 1 - start, 0);
3066                 clear_extent_dirty(unpin, start, end, GFP_NOFS);
3067
3068                 cond_resched();
3069         }
3070         return ret;
3071 }
3072
3073 static int pin_down_bytes(struct btrfs_trans_handle *trans,
3074                           struct btrfs_root *root,
3075                           struct btrfs_path *path,
3076                           u64 bytenr, u64 num_bytes, int is_data,
3077                           struct extent_buffer **must_clean)
3078 {
3079         int err = 0;
3080         struct extent_buffer *buf;
3081
3082         if (is_data)
3083                 goto pinit;
3084
3085         buf = btrfs_find_tree_block(root, bytenr, num_bytes);
3086         if (!buf)
3087                 goto pinit;
3088
3089         /* we can reuse a block if it hasn't been written
3090          * and it is from this transaction.  We can't
3091          * reuse anything from the tree log root because
3092          * it has tiny sub-transactions.
3093          */
3094         if (btrfs_buffer_uptodate(buf, 0) &&
3095             btrfs_try_tree_lock(buf)) {
3096                 u64 header_owner = btrfs_header_owner(buf);
3097                 u64 header_transid = btrfs_header_generation(buf);
3098                 if (header_owner != BTRFS_TREE_LOG_OBJECTID &&
3099                     header_transid == trans->transid &&
3100                     !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
3101                         *must_clean = buf;
3102                         return 1;
3103                 }
3104                 btrfs_tree_unlock(buf);
3105         }
3106         free_extent_buffer(buf);
3107 pinit:
3108         btrfs_set_path_blocking(path);
3109         /* unlocks the pinned mutex */
3110         btrfs_update_pinned_extents(root, bytenr, num_bytes, 1);
3111
3112         BUG_ON(err < 0);
3113         return 0;
3114 }
3115
3116
3117 static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
3118                                 struct btrfs_root *root,
3119                                 u64 bytenr, u64 num_bytes, u64 parent,
3120                                 u64 root_objectid, u64 owner_objectid,
3121                                 u64 owner_offset, int refs_to_drop,
3122                                 struct btrfs_delayed_extent_op *extent_op)
3123 {
3124         struct btrfs_key key;
3125         struct btrfs_path *path;
3126         struct btrfs_fs_info *info = root->fs_info;
3127         struct btrfs_root *extent_root = info->extent_root;
3128         struct extent_buffer *leaf;
3129         struct btrfs_extent_item *ei;
3130         struct btrfs_extent_inline_ref *iref;
3131         int ret;
3132         int is_data;
3133         int extent_slot = 0;
3134         int found_extent = 0;
3135         int num_to_del = 1;
3136         u32 item_size;
3137         u64 refs;
3138
3139         path = btrfs_alloc_path();
3140         if (!path)
3141                 return -ENOMEM;
3142
3143         path->reada = 1;
3144         path->leave_spinning = 1;
3145
3146         is_data = owner_objectid >= BTRFS_FIRST_FREE_OBJECTID;
3147         BUG_ON(!is_data && refs_to_drop != 1);
3148
3149         ret = lookup_extent_backref(trans, extent_root, path, &iref,
3150                                     bytenr, num_bytes, parent,
3151                                     root_objectid, owner_objectid,
3152                                     owner_offset);
3153         if (ret == 0) {
3154                 extent_slot = path->slots[0];
3155                 while (extent_slot >= 0) {
3156                         btrfs_item_key_to_cpu(path->nodes[0], &key,
3157                                               extent_slot);
3158                         if (key.objectid != bytenr)
3159                                 break;
3160                         if (key.type == BTRFS_EXTENT_ITEM_KEY &&
3161                             key.offset == num_bytes) {
3162                                 found_extent = 1;
3163                                 break;
3164                         }
3165                         if (path->slots[0] - extent_slot > 5)
3166                                 break;
3167                         extent_slot--;
3168                 }
3169 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
3170                 item_size = btrfs_item_size_nr(path->nodes[0], extent_slot);
3171                 if (found_extent && item_size < sizeof(*ei))
3172                         found_extent = 0;
3173 #endif
3174                 if (!found_extent) {
3175                         BUG_ON(iref);
3176                         ret = remove_extent_backref(trans, extent_root, path,
3177                                                     NULL, refs_to_drop,
3178                                                     is_data);
3179                         BUG_ON(ret);
3180                         btrfs_release_path(extent_root, path);
3181                         path->leave_spinning = 1;
3182
3183                         key.objectid = bytenr;
3184                         key.type = BTRFS_EXTENT_ITEM_KEY;
3185                         key.offset = num_bytes;
3186
3187                         ret = btrfs_search_slot(trans, extent_root,
3188                                                 &key, path, -1, 1);
3189                         if (ret) {
3190                                 printk(KERN_ERR "umm, got %d back from search"
3191                                        ", was looking for %llu\n", ret,
3192                                        (unsigned long long)bytenr);
3193                                 btrfs_print_leaf(extent_root, path->nodes[0]);
3194                         }
3195                         BUG_ON(ret);
3196                         extent_slot = path->slots[0];
3197                 }
3198         } else {
3199                 btrfs_print_leaf(extent_root, path->nodes[0]);
3200                 WARN_ON(1);
3201                 printk(KERN_ERR "btrfs unable to find ref byte nr %llu "
3202                        "parent %llu root %llu  owner %llu offset %llu\n",
3203                        (unsigned long long)bytenr,
3204                        (unsigned long long)parent,
3205                        (unsigned long long)root_objectid,
3206                        (unsigned long long)owner_objectid,
3207                        (unsigned long long)owner_offset);
3208         }
3209
3210         leaf = path->nodes[0];
3211         item_size = btrfs_item_size_nr(leaf, extent_slot);
3212 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
3213         if (item_size < sizeof(*ei)) {
3214                 BUG_ON(found_extent || extent_slot != path->slots[0]);
3215                 ret = convert_extent_item_v0(trans, extent_root, path,
3216                                              owner_objectid, 0);
3217                 BUG_ON(ret < 0);
3218
3219                 btrfs_release_path(extent_root, path);
3220                 path->leave_spinning = 1;
3221
3222                 key.objectid = bytenr;
3223                 key.type = BTRFS_EXTENT_ITEM_KEY;
3224                 key.offset = num_bytes;
3225
3226                 ret = btrfs_search_slot(trans, extent_root, &key, path,
3227                                         -1, 1);
3228                 if (ret) {
3229                         printk(KERN_ERR "umm, got %d back from search"
3230                                ", was looking for %llu\n", ret,
3231                                (unsigned long long)bytenr);
3232                         btrfs_print_leaf(extent_root, path->nodes[0]);
3233                 }
3234                 BUG_ON(ret);
3235                 extent_slot = path->slots[0];
3236                 leaf = path->nodes[0];
3237                 item_size = btrfs_item_size_nr(leaf, extent_slot);
3238         }
3239 #endif
3240         BUG_ON(item_size < sizeof(*ei));
3241         ei = btrfs_item_ptr(leaf, extent_slot,
3242                             struct btrfs_extent_item);
3243         if (owner_objectid < BTRFS_FIRST_FREE_OBJECTID) {
3244                 struct btrfs_tree_block_info *bi;
3245                 BUG_ON(item_size < sizeof(*ei) + sizeof(*bi));
3246                 bi = (struct btrfs_tree_block_info *)(ei + 1);
3247                 WARN_ON(owner_objectid != btrfs_tree_block_level(leaf, bi));
3248         }
3249
3250         refs = btrfs_extent_refs(leaf, ei);
3251         BUG_ON(refs < refs_to_drop);
3252         refs -= refs_to_drop;
3253
3254         if (refs > 0) {
3255                 if (extent_op)
3256                         __run_delayed_extent_op(extent_op, leaf, ei);
3257                 /*
3258                  * In the case of inline back ref, reference count will
3259                  * be updated by remove_extent_backref
3260                  */
3261                 if (iref) {
3262                         BUG_ON(!found_extent);
3263                 } else {
3264                         btrfs_set_extent_refs(leaf, ei, refs);
3265                         btrfs_mark_buffer_dirty(leaf);
3266                 }
3267                 if (found_extent) {
3268                         ret = remove_extent_backref(trans, extent_root, path,
3269                                                     iref, refs_to_drop,
3270                                                     is_data);
3271                         BUG_ON(ret);
3272                 }
3273         } else {
3274                 int mark_free = 0;
3275                 struct extent_buffer *must_clean = NULL;
3276
3277                 if (found_extent) {
3278                         BUG_ON(is_data && refs_to_drop !=
3279                                extent_data_ref_count(root, path, iref));
3280                         if (iref) {
3281                                 BUG_ON(path->slots[0] != extent_slot);
3282                         } else {
3283                                 BUG_ON(path->slots[0] != extent_slot + 1);
3284                                 path->slots[0] = extent_slot;
3285                                 num_to_del = 2;
3286                         }
3287                 }
3288
3289                 ret = pin_down_bytes(trans, root, path, bytenr,
3290                                      num_bytes, is_data, &must_clean);
3291                 if (ret > 0)
3292                         mark_free = 1;
3293                 BUG_ON(ret < 0);
3294                 /*
3295                  * it is going to be very rare for someone to be waiting
3296                  * on the block we're freeing.  del_items might need to
3297                  * schedule, so rather than get fancy, just force it
3298                  * to blocking here
3299                  */
3300                 if (must_clean)
3301                         btrfs_set_lock_blocking(must_clean);
3302
3303                 ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
3304                                       num_to_del);
3305                 BUG_ON(ret);
3306                 btrfs_release_path(extent_root, path);
3307
3308                 if (must_clean) {
3309                         clean_tree_block(NULL, root, must_clean);
3310                         btrfs_tree_unlock(must_clean);
3311                         free_extent_buffer(must_clean);
3312                 }
3313
3314                 if (is_data) {
3315                         ret = btrfs_del_csums(trans, root, bytenr, num_bytes);
3316                         BUG_ON(ret);
3317                 } else {
3318                         invalidate_mapping_pages(info->btree_inode->i_mapping,
3319                              bytenr >> PAGE_CACHE_SHIFT,
3320                              (bytenr + num_bytes - 1) >> PAGE_CACHE_SHIFT);
3321                 }
3322
3323                 ret = update_block_group(trans, root, bytenr, num_bytes, 0,
3324                                          mark_free);
3325                 BUG_ON(ret);
3326         }
3327         btrfs_free_path(path);
3328         return ret;
3329 }
3330
3331 /*
3332  * when we free an extent, it is possible (and likely) that we free the last
3333  * delayed ref for that extent as well.  This searches the delayed ref tree for
3334  * a given extent, and if there are no other delayed refs to be processed, it
3335  * removes it from the tree.
3336  */
3337 static noinline int check_ref_cleanup(struct btrfs_trans_handle *trans,
3338                                       struct btrfs_root *root, u64 bytenr)
3339 {
3340         struct btrfs_delayed_ref_head *head;
3341         struct btrfs_delayed_ref_root *delayed_refs;
3342         struct btrfs_delayed_ref_node *ref;
3343         struct rb_node *node;
3344         int ret;
3345
3346         delayed_refs = &trans->transaction->delayed_refs;
3347         spin_lock(&delayed_refs->lock);
3348         head = btrfs_find_delayed_ref_head(trans, bytenr);
3349         if (!head)
3350                 goto out;
3351
3352         node = rb_prev(&head->node.rb_node);
3353         if (!node)
3354                 goto out;
3355
3356         ref = rb_entry(node, struct btrfs_delayed_ref_node, rb_node);
3357
3358         /* there are still entries for this ref, we can't drop it */
3359         if (ref->bytenr == bytenr)
3360                 goto out;
3361
3362         if (head->extent_op) {
3363                 if (!head->must_insert_reserved)
3364                         goto out;
3365                 kfree(head->extent_op);
3366                 head->extent_op = NULL;
3367         }
3368
3369         /*
3370          * waiting for the lock here would deadlock.  If someone else has it
3371          * locked they are already in the process of dropping it anyway
3372          */
3373         if (!mutex_trylock(&head->mutex))
3374                 goto out;
3375
3376         /*
3377          * at this point we have a head with no other entries.  Go
3378          * ahead and process it.
3379          */
3380         head->node.in_tree = 0;
3381         rb_erase(&head->node.rb_node, &delayed_refs->root);
3382
3383         delayed_refs->num_entries--;
3384
3385         /*
3386          * we don't take a ref on the node because we're removing it from the
3387          * tree, so we just steal the ref the tree was holding.
3388          */
3389         delayed_refs->num_heads--;
3390         if (list_empty(&head->cluster))
3391                 delayed_refs->num_heads_ready--;
3392
3393         list_del_init(&head->cluster);
3394         spin_unlock(&delayed_refs->lock);
3395
3396         ret = run_one_delayed_ref(trans, root->fs_info->tree_root,
3397                                   &head->node, head->extent_op,
3398                                   head->must_insert_reserved);
3399         BUG_ON(ret);
3400         btrfs_put_delayed_ref(&head->node);
3401         return 0;
3402 out:
3403         spin_unlock(&delayed_refs->lock);
3404         return 0;
3405 }
3406
3407 int btrfs_free_extent(struct btrfs_trans_handle *trans,
3408                       struct btrfs_root *root,
3409                       u64 bytenr, u64 num_bytes, u64 parent,
3410                       u64 root_objectid, u64 owner, u64 offset)
3411 {
3412         int ret;
3413
3414         /*
3415          * tree log blocks never actually go into the extent allocation
3416          * tree, just update pinning info and exit early.
3417          */
3418         if (root_objectid == BTRFS_TREE_LOG_OBJECTID) {
3419                 WARN_ON(owner >= BTRFS_FIRST_FREE_OBJECTID);
3420                 /* unlocks the pinned mutex */
3421                 btrfs_update_pinned_extents(root, bytenr, num_bytes, 1);
3422                 update_reserved_extents(root, bytenr, num_bytes, 0);
3423                 ret = 0;
3424         } else if (owner < BTRFS_FIRST_FREE_OBJECTID) {
3425                 ret = btrfs_add_delayed_tree_ref(trans, bytenr, num_bytes,
3426                                         parent, root_objectid, (int)owner,
3427                                         BTRFS_DROP_DELAYED_REF, NULL);
3428                 BUG_ON(ret);
3429                 ret = check_ref_cleanup(trans, root, bytenr);
3430                 BUG_ON(ret);
3431         } else {
3432                 ret = btrfs_add_delayed_data_ref(trans, bytenr, num_bytes,
3433                                         parent, root_objectid, owner,
3434                                         offset, BTRFS_DROP_DELAYED_REF, NULL);
3435                 BUG_ON(ret);
3436         }
3437         return ret;
3438 }
3439
3440 static u64 stripe_align(struct btrfs_root *root, u64 val)
3441 {
3442         u64 mask = ((u64)root->stripesize - 1);
3443         u64 ret = (val + mask) & ~mask;
3444         return ret;
3445 }
3446
3447 /*
3448  * walks the btree of allocated extents and find a hole of a given size.
3449  * The key ins is changed to record the hole:
3450  * ins->objectid == block start
3451  * ins->flags = BTRFS_EXTENT_ITEM_KEY
3452  * ins->offset == number of blocks
3453  * Any available blocks before search_start are skipped.
3454  */
3455 static noinline int find_free_extent(struct btrfs_trans_handle *trans,
3456                                      struct btrfs_root *orig_root,
3457                                      u64 num_bytes, u64 empty_size,
3458                                      u64 search_start, u64 search_end,
3459                                      u64 hint_byte, struct btrfs_key *ins,
3460                                      u64 exclude_start, u64 exclude_nr,
3461                                      int data)
3462 {
3463         int ret = 0;
3464         struct btrfs_root *root = orig_root->fs_info->extent_root;
3465         struct btrfs_free_cluster *last_ptr = NULL;
3466         struct btrfs_block_group_cache *block_group = NULL;
3467         int empty_cluster = 2 * 1024 * 1024;
3468         int allowed_chunk_alloc = 0;
3469         struct btrfs_space_info *space_info;
3470         int last_ptr_loop = 0;
3471         int loop = 0;
3472
3473         WARN_ON(num_bytes < root->sectorsize);
3474         btrfs_set_key_type(ins, BTRFS_EXTENT_ITEM_KEY);
3475         ins->objectid = 0;
3476         ins->offset = 0;
3477
3478         space_info = __find_space_info(root->fs_info, data);
3479
3480         if (orig_root->ref_cows || empty_size)
3481                 allowed_chunk_alloc = 1;
3482
3483         if (data & BTRFS_BLOCK_GROUP_METADATA) {
3484                 last_ptr = &root->fs_info->meta_alloc_cluster;
3485                 if (!btrfs_test_opt(root, SSD))
3486                         empty_cluster = 64 * 1024;
3487         }
3488
3489         if ((data & BTRFS_BLOCK_GROUP_DATA) && btrfs_test_opt(root, SSD)) {
3490                 last_ptr = &root->fs_info->data_alloc_cluster;
3491         }
3492
3493         if (last_ptr) {
3494                 spin_lock(&last_ptr->lock);
3495                 if (last_ptr->block_group)
3496                         hint_byte = last_ptr->window_start;
3497                 spin_unlock(&last_ptr->lock);
3498         }
3499
3500         search_start = max(search_start, first_logical_byte(root, 0));
3501         search_start = max(search_start, hint_byte);
3502
3503         if (!last_ptr) {
3504                 empty_cluster = 0;
3505                 loop = 1;
3506         }
3507
3508         if (search_start == hint_byte) {
3509                 block_group = btrfs_lookup_block_group(root->fs_info,
3510                                                        search_start);
3511                 if (block_group && block_group_bits(block_group, data)) {
3512                         down_read(&space_info->groups_sem);
3513                         if (list_empty(&block_group->list) ||
3514                             block_group->ro) {
3515                                 /*
3516                                  * someone is removing this block group,
3517                                  * we can't jump into the have_block_group
3518                                  * target because our list pointers are not
3519                                  * valid
3520                                  */
3521                                 btrfs_put_block_group(block_group);
3522                                 up_read(&space_info->groups_sem);
3523                         } else
3524                                 goto have_block_group;
3525                 } else if (block_group) {
3526                         btrfs_put_block_group(block_group);
3527                 }
3528         }
3529
3530 search:
3531         down_read(&space_info->groups_sem);
3532         list_for_each_entry(block_group, &space_info->block_groups, list) {
3533                 u64 offset;
3534
3535                 atomic_inc(&block_group->count);
3536                 search_start = block_group->key.objectid;
3537
3538 have_block_group:
3539                 if (unlikely(!block_group->cached)) {
3540                         mutex_lock(&block_group->cache_mutex);
3541                         ret = cache_block_group(root, block_group);
3542                         mutex_unlock(&block_group->cache_mutex);
3543                         if (ret) {
3544                                 btrfs_put_block_group(block_group);
3545                                 break;
3546                         }
3547                 }
3548
3549                 if (unlikely(block_group->ro))
3550                         goto loop;
3551
3552                 if (last_ptr) {
3553                         /*
3554                          * the refill lock keeps out other
3555                          * people trying to start a new cluster
3556                          */
3557                         spin_lock(&last_ptr->refill_lock);
3558                         if (last_ptr->block_group &&
3559                             (last_ptr->block_group->ro ||
3560                             !block_group_bits(last_ptr->block_group, data))) {
3561                                 offset = 0;
3562                                 goto refill_cluster;
3563                         }
3564
3565                         offset = btrfs_alloc_from_cluster(block_group, last_ptr,
3566                                                  num_bytes, search_start);
3567                         if (offset) {
3568                                 /* we have a block, we're done */
3569                                 spin_unlock(&last_ptr->refill_lock);
3570                                 goto checks;
3571                         }
3572
3573                         spin_lock(&last_ptr->lock);
3574                         /*
3575                          * whoops, this cluster doesn't actually point to
3576                          * this block group.  Get a ref on the block
3577                          * group is does point to and try again
3578                          */
3579                         if (!last_ptr_loop && last_ptr->block_group &&
3580                             last_ptr->block_group != block_group) {
3581
3582                                 btrfs_put_block_group(block_group);
3583                                 block_group = last_ptr->block_group;
3584                                 atomic_inc(&block_group->count);
3585                                 spin_unlock(&last_ptr->lock);
3586                                 spin_unlock(&last_ptr->refill_lock);
3587
3588                                 last_ptr_loop = 1;
3589                                 search_start = block_group->key.objectid;
3590                                 /*
3591                                  * we know this block group is properly
3592                                  * in the list because
3593                                  * btrfs_remove_block_group, drops the
3594                                  * cluster before it removes the block
3595                                  * group from the list
3596                                  */
3597                                 goto have_block_group;
3598                         }
3599                         spin_unlock(&last_ptr->lock);
3600 refill_cluster:
3601                         /*
3602                          * this cluster didn't work out, free it and
3603                          * start over
3604                          */
3605                         btrfs_return_cluster_to_free_space(NULL, last_ptr);
3606
3607                         last_ptr_loop = 0;
3608
3609                         /* allocate a cluster in this block group */
3610                         ret = btrfs_find_space_cluster(trans, root,
3611                                                block_group, last_ptr,
3612                                                offset, num_bytes,
3613                                                empty_cluster + empty_size);
3614                         if (ret == 0) {
3615                                 /*
3616                                  * now pull our allocation out of this
3617                                  * cluster
3618                                  */
3619                                 offset = btrfs_alloc_from_cluster(block_group,
3620                                                   last_ptr, num_bytes,
3621                                                   search_start);
3622                                 if (offset) {
3623                                         /* we found one, proceed */
3624                                         spin_unlock(&last_ptr->refill_lock);
3625                                         goto checks;
3626                                 }
3627                         }
3628                         /*
3629                          * at this point we either didn't find a cluster
3630                          * or we weren't able to allocate a block from our
3631                          * cluster.  Free the cluster we've been trying
3632                          * to use, and go to the next block group
3633                          */
3634                         if (loop < 2) {
3635                                 btrfs_return_cluster_to_free_space(NULL,
3636                                                                    last_ptr);
3637                                 spin_unlock(&last_ptr->refill_lock);
3638                                 goto loop;
3639                         }
3640                         spin_unlock(&last_ptr->refill_lock);
3641                 }
3642
3643                 offset = btrfs_find_space_for_alloc(block_group, search_start,
3644                                                     num_bytes, empty_size);
3645                 if (!offset)
3646                         goto loop;
3647 checks:
3648                 search_start = stripe_align(root, offset);
3649
3650                 /* move on to the next group */
3651                 if (search_start + num_bytes >= search_end) {
3652                         btrfs_add_free_space(block_group, offset, num_bytes);
3653                         goto loop;
3654                 }
3655
3656                 /* move on to the next group */
3657                 if (search_start + num_bytes >
3658                     block_group->key.objectid + block_group->key.offset) {
3659                         btrfs_add_free_space(block_group, offset, num_bytes);
3660                         goto loop;
3661                 }
3662
3663                 if (exclude_nr > 0 &&
3664                     (search_start + num_bytes > exclude_start &&
3665                      search_start < exclude_start + exclude_nr)) {
3666                         search_start = exclude_start + exclude_nr;
3667
3668                         btrfs_add_free_space(block_group, offset, num_bytes);
3669                         /*
3670                          * if search_start is still in this block group
3671                          * then we just re-search this block group
3672                          */
3673                         if (search_start >= block_group->key.objectid &&
3674                             search_start < (block_group->key.objectid +
3675                                             block_group->key.offset))
3676                                 goto have_block_group;
3677                         goto loop;
3678                 }
3679
3680                 ins->objectid = search_start;
3681                 ins->offset = num_bytes;
3682
3683                 if (offset < search_start)
3684                         btrfs_add_free_space(block_group, offset,
3685                                              search_start - offset);
3686                 BUG_ON(offset > search_start);
3687
3688                 /* we are all good, lets return */
3689                 break;
3690 loop:
3691                 btrfs_put_block_group(block_group);
3692         }
3693         up_read(&space_info->groups_sem);
3694
3695         /* loop == 0, try to find a clustered alloc in every block group
3696          * loop == 1, try again after forcing a chunk allocation
3697          * loop == 2, set empty_size and empty_cluster to 0 and try again
3698          */
3699         if (!ins->objectid && loop < 3 &&
3700             (empty_size || empty_cluster || allowed_chunk_alloc)) {
3701                 if (loop >= 2) {
3702                         empty_size = 0;
3703                         empty_cluster = 0;
3704                 }
3705
3706                 if (allowed_chunk_alloc) {
3707                         ret = do_chunk_alloc(trans, root, num_bytes +
3708                                              2 * 1024 * 1024, data, 1);
3709                         allowed_chunk_alloc = 0;
3710                 } else {
3711                         space_info->force_alloc = 1;
3712                 }
3713
3714                 if (loop < 3) {
3715                         loop++;
3716                         goto search;
3717                 }
3718                 ret = -ENOSPC;
3719         } else if (!ins->objectid) {
3720                 ret = -ENOSPC;
3721         }
3722
3723         /* we found what we needed */
3724         if (ins->objectid) {
3725                 if (!(data & BTRFS_BLOCK_GROUP_DATA))
3726                         trans->block_group = block_group->key.objectid;
3727
3728                 btrfs_put_block_group(block_group);
3729                 ret = 0;
3730         }
3731
3732         return ret;
3733 }
3734
3735 static void dump_space_info(struct btrfs_space_info *info, u64 bytes)
3736 {
3737         struct btrfs_block_group_cache *cache;
3738
3739         printk(KERN_INFO "space_info has %llu free, is %sfull\n",
3740                (unsigned long long)(info->total_bytes - info->bytes_used -
3741                                     info->bytes_pinned - info->bytes_reserved),
3742                (info->full) ? "" : "not ");
3743         printk(KERN_INFO "space_info total=%llu, pinned=%llu, delalloc=%llu,"
3744                " may_use=%llu, used=%llu\n",
3745                (unsigned long long)info->total_bytes,
3746                (unsigned long long)info->bytes_pinned,
3747                (unsigned long long)info->bytes_delalloc,
3748                (unsigned long long)info->bytes_may_use,
3749                (unsigned long long)info->bytes_used);
3750
3751         down_read(&info->groups_sem);
3752         list_for_each_entry(cache, &info->block_groups, list) {
3753                 spin_lock(&cache->lock);
3754                 printk(KERN_INFO "block group %llu has %llu bytes, %llu used "
3755                        "%llu pinned %llu reserved\n",
3756                        (unsigned long long)cache->key.objectid,
3757                        (unsigned long long)cache->key.offset,
3758                        (unsigned long long)btrfs_block_group_used(&cache->item),
3759                        (unsigned long long)cache->pinned,
3760                        (unsigned long long)cache->reserved);
3761                 btrfs_dump_free_space(cache, bytes);
3762                 spin_unlock(&cache->lock);
3763         }
3764         up_read(&info->groups_sem);
3765 }
3766
3767 static int __btrfs_reserve_extent(struct btrfs_trans_handle *trans,
3768                                   struct btrfs_root *root,
3769                                   u64 num_bytes, u64 min_alloc_size,
3770                                   u64 empty_size, u64 hint_byte,
3771                                   u64 search_end, struct btrfs_key *ins,
3772                                   u64 data)
3773 {
3774         int ret;
3775         u64 search_start = 0;
3776         struct btrfs_fs_info *info = root->fs_info;
3777
3778         data = btrfs_get_alloc_profile(root, data);
3779 again:
3780         /*
3781          * the only place that sets empty_size is btrfs_realloc_node, which
3782          * is not called recursively on allocations
3783          */
3784         if (empty_size || root->ref_cows) {
3785                 if (!(data & BTRFS_BLOCK_GROUP_METADATA)) {
3786                         ret = do_chunk_alloc(trans, root->fs_info->extent_root,
3787                                      2 * 1024 * 1024,
3788                                      BTRFS_BLOCK_GROUP_METADATA |
3789                                      (info->metadata_alloc_profile &
3790                                       info->avail_metadata_alloc_bits), 0);
3791                 }
3792                 ret = do_chunk_alloc(trans, root->fs_info->extent_root,
3793                                      num_bytes + 2 * 1024 * 1024, data, 0);
3794         }
3795
3796         WARN_ON(num_bytes < root->sectorsize);
3797         ret = find_free_extent(trans, root, num_bytes, empty_size,
3798                                search_start, search_end, hint_byte, ins,
3799                                trans->alloc_exclude_start,
3800                                trans->alloc_exclude_nr, data);
3801
3802         if (ret == -ENOSPC && num_bytes > min_alloc_size) {
3803                 num_bytes = num_bytes >> 1;
3804                 num_bytes = num_bytes & ~(root->sectorsize - 1);
3805                 num_bytes = max(num_bytes, min_alloc_size);
3806                 do_chunk_alloc(trans, root->fs_info->extent_root,
3807                                num_bytes, data, 1);
3808                 goto again;
3809         }
3810         if (ret) {
3811                 struct btrfs_space_info *sinfo;
3812
3813                 sinfo = __find_space_info(root->fs_info, data);
3814                 printk(KERN_ERR "btrfs allocation failed flags %llu, "
3815                        "wanted %llu\n", (unsigned long long)data,
3816                        (unsigned long long)num_bytes);
3817                 dump_space_info(sinfo, num_bytes);
3818                 BUG();
3819         }
3820
3821         return ret;
3822 }
3823
3824 int btrfs_free_reserved_extent(struct btrfs_root *root, u64 start, u64 len)
3825 {
3826         struct btrfs_block_group_cache *cache;
3827         int ret = 0;
3828
3829         cache = btrfs_lookup_block_group(root->fs_info, start);
3830         if (!cache) {
3831                 printk(KERN_ERR "Unable to find block group for %llu\n",
3832                        (unsigned long long)start);
3833                 return -ENOSPC;
3834         }
3835
3836         ret = btrfs_discard_extent(root, start, len);
3837
3838         btrfs_add_free_space(cache, start, len);
3839         btrfs_put_block_group(cache);
3840         update_reserved_extents(root, start, len, 0);
3841
3842         return ret;
3843 }
3844
3845 int btrfs_reserve_extent(struct btrfs_trans_handle *trans,
3846                                   struct btrfs_root *root,
3847                                   u64 num_bytes, u64 min_alloc_size,
3848                                   u64 empty_size, u64 hint_byte,
3849                                   u64 search_end, struct btrfs_key *ins,
3850                                   u64 data)
3851 {
3852         int ret;
3853         ret = __btrfs_reserve_extent(trans, root, num_bytes, min_alloc_size,
3854                                      empty_size, hint_byte, search_end, ins,
3855                                      data);
3856         update_reserved_extents(root, ins->objectid, ins->offset, 1);
3857         return ret;
3858 }
3859
3860 static int alloc_reserved_file_extent(struct btrfs_trans_handle *trans,
3861                                       struct btrfs_root *root,
3862                                       u64 parent, u64 root_objectid,
3863                                       u64 flags, u64 owner, u64 offset,
3864                                       struct btrfs_key *ins, int ref_mod)
3865 {
3866         int ret;
3867         struct btrfs_fs_info *fs_info = root->fs_info;
3868         struct btrfs_extent_item *extent_item;
3869         struct btrfs_extent_inline_ref *iref;
3870         struct btrfs_path *path;
3871         struct extent_buffer *leaf;
3872         int type;
3873         u32 size;
3874
3875         if (parent > 0)
3876                 type = BTRFS_SHARED_DATA_REF_KEY;
3877         else
3878                 type = BTRFS_EXTENT_DATA_REF_KEY;
3879
3880         size = sizeof(*extent_item) + btrfs_extent_inline_ref_size(type);
3881
3882         path = btrfs_alloc_path();
3883         BUG_ON(!path);
3884
3885         path->leave_spinning = 1;
3886         ret = btrfs_insert_empty_item(trans, fs_info->extent_root, path,
3887                                       ins, size);
3888         BUG_ON(ret);
3889
3890         leaf = path->nodes[0];
3891         extent_item = btrfs_item_ptr(leaf, path->slots[0],
3892                                      struct btrfs_extent_item);
3893         btrfs_set_extent_refs(leaf, extent_item, ref_mod);
3894         btrfs_set_extent_generation(leaf, extent_item, trans->transid);
3895         btrfs_set_extent_flags(leaf, extent_item,
3896                                flags | BTRFS_EXTENT_FLAG_DATA);
3897
3898         iref = (struct btrfs_extent_inline_ref *)(extent_item + 1);
3899         btrfs_set_extent_inline_ref_type(leaf, iref, type);
3900         if (parent > 0) {
3901                 struct btrfs_shared_data_ref *ref;
3902                 ref = (struct btrfs_shared_data_ref *)(iref + 1);
3903                 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
3904                 btrfs_set_shared_data_ref_count(leaf, ref, ref_mod);
3905         } else {
3906                 struct btrfs_extent_data_ref *ref;
3907                 ref = (struct btrfs_extent_data_ref *)(&iref->offset);
3908                 btrfs_set_extent_data_ref_root(leaf, ref, root_objectid);
3909                 btrfs_set_extent_data_ref_objectid(leaf, ref, owner);
3910                 btrfs_set_extent_data_ref_offset(leaf, ref, offset);
3911                 btrfs_set_extent_data_ref_count(leaf, ref, ref_mod);
3912         }
3913
3914         btrfs_mark_buffer_dirty(path->nodes[0]);
3915         btrfs_free_path(path);
3916
3917         ret = update_block_group(trans, root, ins->objectid, ins->offset,
3918                                  1, 0);
3919         if (ret) {
3920                 printk(KERN_ERR "btrfs update block group failed for %llu "
3921                        "%llu\n", (unsigned long long)ins->objectid,
3922                        (unsigned long long)ins->offset);
3923                 BUG();
3924         }
3925         return ret;
3926 }
3927
3928 static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
3929                                      struct btrfs_root *root,
3930                                      u64 parent, u64 root_objectid,
3931                                      u64 flags, struct btrfs_disk_key *key,
3932                                      int level, struct btrfs_key *ins)
3933 {
3934         int ret;
3935         struct btrfs_fs_info *fs_info = root->fs_info;
3936         struct btrfs_extent_item *extent_item;
3937         struct btrfs_tree_block_info *block_info;
3938         struct btrfs_extent_inline_ref *iref;
3939         struct btrfs_path *path;
3940         struct extent_buffer *leaf;
3941         u32 size = sizeof(*extent_item) + sizeof(*block_info) + sizeof(*iref);
3942
3943         path = btrfs_alloc_path();
3944         BUG_ON(!path);
3945
3946         path->leave_spinning = 1;
3947         ret = btrfs_insert_empty_item(trans, fs_info->extent_root, path,
3948                                       ins, size);
3949         BUG_ON(ret);
3950
3951         leaf = path->nodes[0];
3952         extent_item = btrfs_item_ptr(leaf, path->slots[0],
3953                                      struct btrfs_extent_item);
3954         btrfs_set_extent_refs(leaf, extent_item, 1);
3955         btrfs_set_extent_generation(leaf, extent_item, trans->transid);
3956         btrfs_set_extent_flags(leaf, extent_item,
3957                                flags | BTRFS_EXTENT_FLAG_TREE_BLOCK);
3958         block_info = (struct btrfs_tree_block_info *)(extent_item + 1);
3959
3960         btrfs_set_tree_block_key(leaf, block_info, key);
3961         btrfs_set_tree_block_level(leaf, block_info, level);
3962
3963         iref = (struct btrfs_extent_inline_ref *)(block_info + 1);
3964         if (parent > 0) {
3965                 BUG_ON(!(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF));
3966                 btrfs_set_extent_inline_ref_type(leaf, iref,
3967                                                  BTRFS_SHARED_BLOCK_REF_KEY);
3968                 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
3969         } else {
3970                 btrfs_set_extent_inline_ref_type(leaf, iref,
3971                                                  BTRFS_TREE_BLOCK_REF_KEY);
3972                 btrfs_set_extent_inline_ref_offset(leaf, iref, root_objectid);
3973         }
3974
3975         btrfs_mark_buffer_dirty(leaf);
3976         btrfs_free_path(path);
3977
3978         ret = update_block_group(trans, root, ins->objectid, ins->offset,
3979                                  1, 0);
3980         if (ret) {
3981                 printk(KERN_ERR "btrfs update block group failed for %llu "
3982                        "%llu\n", (unsigned long long)ins->objectid,
3983                        (unsigned long long)ins->offset);
3984                 BUG();
3985         }
3986         return ret;
3987 }
3988
3989 int btrfs_alloc_reserved_file_extent(struct btrfs_trans_handle *trans,
3990                                      struct btrfs_root *root,
3991                                      u64 root_objectid, u64 owner,
3992                                      u64 offset, struct btrfs_key *ins)
3993 {
3994         int ret;
3995
3996         BUG_ON(root_objectid == BTRFS_TREE_LOG_OBJECTID);
3997
3998         ret = btrfs_add_delayed_data_ref(trans, ins->objectid, ins->offset,
3999                                          0, root_objectid, owner, offset,
4000                                          BTRFS_ADD_DELAYED_EXTENT, NULL);
4001         return ret;
4002 }
4003
4004 /*
4005  * this is used by the tree logging recovery code.  It records that
4006  * an extent has been allocated and makes sure to clear the free
4007  * space cache bits as well
4008  */
4009 int btrfs_alloc_logged_file_extent(struct btrfs_trans_handle *trans,
4010                                    struct btrfs_root *root,
4011                                    u64 root_objectid, u64 owner, u64 offset,
4012                                    struct btrfs_key *ins)
4013 {
4014         int ret;
4015         struct btrfs_block_group_cache *block_group;
4016
4017         block_group = btrfs_lookup_block_group(root->fs_info, ins->objectid);
4018         mutex_lock(&block_group->cache_mutex);
4019         cache_block_group(root, block_group);
4020         mutex_unlock(&block_group->cache_mutex);
4021
4022         ret = btrfs_remove_free_space(block_group, ins->objectid,
4023                                       ins->offset);
4024         BUG_ON(ret);
4025         btrfs_put_block_group(block_group);
4026         ret = alloc_reserved_file_extent(trans, root, 0, root_objectid,
4027                                          0, owner, offset, ins, 1);
4028         return ret;
4029 }
4030
4031 /*
4032  * finds a free extent and does all the dirty work required for allocation
4033  * returns the key for the extent through ins, and a tree buffer for
4034  * the first block of the extent through buf.
4035  *
4036  * returns 0 if everything worked, non-zero otherwise.
4037  */
4038 static int alloc_tree_block(struct btrfs_trans_handle *trans,
4039                             struct btrfs_root *root,
4040                             u64 num_bytes, u64 parent, u64 root_objectid,
4041                             struct btrfs_disk_key *key, int level,
4042                             u64 empty_size, u64 hint_byte, u64 search_end,
4043                             struct btrfs_key *ins)
4044 {
4045         int ret;
4046         u64 flags = 0;
4047
4048         ret = __btrfs_reserve_extent(trans, root, num_bytes, num_bytes,
4049                                      empty_size, hint_byte, search_end,
4050                                      ins, 0);
4051         BUG_ON(ret);
4052
4053         if (root_objectid == BTRFS_TREE_RELOC_OBJECTID) {
4054                 if (parent == 0)
4055                         parent = ins->objectid;
4056                 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
4057         } else
4058                 BUG_ON(parent > 0);
4059
4060         update_reserved_extents(root, ins->objectid, ins->offset, 1);
4061         if (root_objectid != BTRFS_TREE_LOG_OBJECTID) {
4062                 struct btrfs_delayed_extent_op *extent_op;
4063                 extent_op = kmalloc(sizeof(*extent_op), GFP_NOFS);
4064                 BUG_ON(!extent_op);
4065                 if (key)
4066                         memcpy(&extent_op->key, key, sizeof(extent_op->key));
4067                 else
4068                         memset(&extent_op->key, 0, sizeof(extent_op->key));
4069                 extent_op->flags_to_set = flags;
4070                 extent_op->update_key = 1;
4071                 extent_op->update_flags = 1;
4072                 extent_op->is_data = 0;
4073
4074                 ret = btrfs_add_delayed_tree_ref(trans, ins->objectid,
4075                                         ins->offset, parent, root_objectid,
4076                                         level, BTRFS_ADD_DELAYED_EXTENT,
4077                                         extent_op);
4078                 BUG_ON(ret);
4079         }
4080         return ret;
4081 }
4082
4083 struct extent_buffer *btrfs_init_new_buffer(struct btrfs_trans_handle *trans,
4084                                             struct btrfs_root *root,
4085                                             u64 bytenr, u32 blocksize,
4086                                             int level)
4087 {
4088         struct extent_buffer *buf;
4089
4090         buf = btrfs_find_create_tree_block(root, bytenr, blocksize);
4091         if (!buf)
4092                 return ERR_PTR(-ENOMEM);
4093         btrfs_set_header_generation(buf, trans->transid);
4094         btrfs_set_buffer_lockdep_class(buf, level);
4095         btrfs_tree_lock(buf);
4096         clean_tree_block(trans, root, buf);
4097
4098         btrfs_set_lock_blocking(buf);
4099         btrfs_set_buffer_uptodate(buf);
4100
4101         if (root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID) {
4102                 set_extent_dirty(&root->dirty_log_pages, buf->start,
4103                          buf->start + buf->len - 1, GFP_NOFS);
4104         } else {
4105                 set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
4106                          buf->start + buf->len - 1, GFP_NOFS);
4107         }
4108         trans->blocks_used++;
4109         /* this returns a buffer locked for blocking */
4110         return buf;
4111 }
4112
4113 /*
4114  * helper function to allocate a block for a given tree
4115  * returns the tree buffer or NULL.
4116  */
4117 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
4118                                         struct btrfs_root *root, u32 blocksize,
4119                                         u64 parent, u64 root_objectid,
4120                                         struct btrfs_disk_key *key, int level,
4121                                         u64 hint, u64 empty_size)
4122 {
4123         struct btrfs_key ins;
4124         int ret;
4125         struct extent_buffer *buf;
4126
4127         ret = alloc_tree_block(trans, root, blocksize, parent, root_objectid,
4128                                key, level, empty_size, hint, (u64)-1, &ins);
4129         if (ret) {
4130                 BUG_ON(ret > 0);
4131                 return ERR_PTR(ret);
4132         }
4133
4134         buf = btrfs_init_new_buffer(trans, root, ins.objectid,
4135                                     blocksize, level);
4136         return buf;
4137 }
4138
4139 int btrfs_drop_leaf_ref(struct btrfs_trans_handle *trans,
4140                         struct btrfs_root *root, struct extent_buffer *leaf)
4141 {
4142         u64 disk_bytenr;
4143         u64 num_bytes;
4144         struct btrfs_key key;
4145         struct btrfs_file_extent_item *fi;
4146         u32 nritems;
4147         int i;
4148         int ret;
4149
4150         BUG_ON(!btrfs_is_leaf(leaf));
4151         nritems = btrfs_header_nritems(leaf);
4152
4153         for (i = 0; i < nritems; i++) {
4154                 cond_resched();
4155                 btrfs_item_key_to_cpu(leaf, &key, i);
4156
4157                 /* only extents have references, skip everything else */
4158                 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
4159                         continue;
4160
4161                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
4162
4163                 /* inline extents live in the btree, they don't have refs */
4164                 if (btrfs_file_extent_type(leaf, fi) ==
4165                     BTRFS_FILE_EXTENT_INLINE)
4166                         continue;
4167
4168                 disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
4169
4170                 /* holes don't have refs */
4171                 if (disk_bytenr == 0)
4172                         continue;
4173
4174                 num_bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
4175                 ret = btrfs_free_extent(trans, root, disk_bytenr, num_bytes,
4176                                         leaf->start, 0, key.objectid, 0);
4177                 BUG_ON(ret);
4178         }
4179         return 0;
4180 }
4181
4182 #if 0
4183
4184 static noinline int cache_drop_leaf_ref(struct btrfs_trans_handle *trans,
4185                                         struct btrfs_root *root,
4186                                         struct btrfs_leaf_ref *ref)
4187 {
4188         int i;
4189         int ret;
4190         struct btrfs_extent_info *info;
4191         struct refsort *sorted;
4192
4193         if (ref->nritems == 0)
4194                 return 0;
4195
4196         sorted = kmalloc(sizeof(*sorted) * ref->nritems, GFP_NOFS);
4197         for (i = 0; i < ref->nritems; i++) {
4198                 sorted[i].bytenr = ref->extents[i].bytenr;
4199                 sorted[i].slot = i;
4200         }
4201         sort(sorted, ref->nritems, sizeof(struct refsort), refsort_cmp, NULL);
4202
4203         /*
4204          * the items in the ref were sorted when the ref was inserted
4205          * into the ref cache, so this is already in order
4206          */
4207         for (i = 0; i < ref->nritems; i++) {
4208                 info = ref->extents + sorted[i].slot;
4209                 ret = btrfs_free_extent(trans, root, info->bytenr,
4210                                           info->num_bytes, ref->bytenr,
4211                                           ref->owner, ref->generation,
4212                                           info->objectid, 0);
4213
4214                 atomic_inc(&root->fs_info->throttle_gen);
4215                 wake_up(&root->fs_info->transaction_throttle);
4216                 cond_resched();
4217
4218                 BUG_ON(ret);
4219                 info++;
4220         }
4221
4222         kfree(sorted);
4223         return 0;
4224 }
4225
4226
4227 static int drop_snap_lookup_refcount(struct btrfs_trans_handle *trans,
4228                                      struct btrfs_root *root, u64 start,
4229                                      u64 len, u32 *refs)
4230 {
4231         int ret;
4232
4233         ret = btrfs_lookup_extent_refs(trans, root, start, len, refs);
4234         BUG_ON(ret);
4235
4236 #if 0 /* some debugging code in case we see problems here */
4237         /* if the refs count is one, it won't get increased again.  But
4238          * if the ref count is > 1, someone may be decreasing it at
4239          * the same time we are.
4240          */
4241         if (*refs != 1) {
4242                 struct extent_buffer *eb = NULL;
4243                 eb = btrfs_find_create_tree_block(root, start, len);
4244                 if (eb)
4245                         btrfs_tree_lock(eb);
4246
4247                 mutex_lock(&root->fs_info->alloc_mutex);
4248                 ret = lookup_extent_ref(NULL, root, start, len, refs);
4249                 BUG_ON(ret);
4250                 mutex_unlock(&root->fs_info->alloc_mutex);
4251
4252                 if (eb) {
4253                         btrfs_tree_unlock(eb);
4254                         free_extent_buffer(eb);
4255                 }
4256                 if (*refs == 1) {
4257                         printk(KERN_ERR "btrfs block %llu went down to one "
4258                                "during drop_snap\n", (unsigned long long)start);
4259                 }
4260
4261         }
4262 #endif
4263
4264         cond_resched();
4265         return ret;
4266 }
4267
4268
4269 /*
4270  * this is used while deleting old snapshots, and it drops the refs
4271  * on a whole subtree starting from a level 1 node.
4272  *
4273  * The idea is to sort all the leaf pointers, and then drop the
4274  * ref on all the leaves in order.  Most of the time the leaves
4275  * will have ref cache entries, so no leaf IOs will be required to
4276  * find the extents they have references on.
4277  *
4278  * For each leaf, any references it has are also dropped in order
4279  *
4280  * This ends up dropping the references in something close to optimal
4281  * order for reading and modifying the extent allocation tree.
4282  */
4283 static noinline int drop_level_one_refs(struct btrfs_trans_handle *trans,
4284                                         struct btrfs_root *root,
4285                                         struct btrfs_path *path)
4286 {
4287         u64 bytenr;
4288         u64 root_owner;
4289         u64 root_gen;
4290         struct extent_buffer *eb = path->nodes[1];
4291         struct extent_buffer *leaf;
4292         struct btrfs_leaf_ref *ref;
4293         struct refsort *sorted = NULL;
4294         int nritems = btrfs_header_nritems(eb);
4295         int ret;
4296         int i;
4297         int refi = 0;
4298         int slot = path->slots[1];
4299         u32 blocksize = btrfs_level_size(root, 0);
4300         u32 refs;
4301
4302         if (nritems == 0)
4303                 goto out;
4304
4305         root_owner = btrfs_header_owner(eb);
4306         root_gen = btrfs_header_generation(eb);
4307         sorted = kmalloc(sizeof(*sorted) * nritems, GFP_NOFS);
4308
4309         /*
4310          * step one, sort all the leaf pointers so we don't scribble
4311          * randomly into the extent allocation tree
4312          */
4313         for (i = slot; i < nritems; i++) {
4314                 sorted[refi].bytenr = btrfs_node_blockptr(eb, i);
4315                 sorted[refi].slot = i;
4316                 refi++;
4317         }
4318
4319         /*
4320          * nritems won't be zero, but if we're picking up drop_snapshot
4321          * after a crash, slot might be > 0, so double check things
4322          * just in case.
4323          */
4324         if (refi == 0)
4325                 goto out;
4326
4327         sort(sorted, refi, sizeof(struct refsort), refsort_cmp, NULL);
4328
4329         /*
4330          * the first loop frees everything the leaves point to
4331          */
4332         for (i = 0; i < refi; i++) {
4333                 u64 ptr_gen;
4334
4335                 bytenr = sorted[i].bytenr;
4336
4337                 /*
4338                  * check the reference count on this leaf.  If it is > 1
4339                  * we just decrement it below and don't update any
4340                  * of the refs the leaf points to.
4341                  */
4342                 ret = drop_snap_lookup_refcount(trans, root, bytenr,
4343                                                 blocksize, &refs);
4344                 BUG_ON(ret);
4345                 if (refs != 1)
4346                         continue;
4347
4348                 ptr_gen = btrfs_node_ptr_generation(eb, sorted[i].slot);
4349
4350                 /*
4351                  * the leaf only had one reference, which means the
4352                  * only thing pointing to this leaf is the snapshot
4353                  * we're deleting.  It isn't possible for the reference
4354                  * count to increase again later
4355                  *
4356                  * The reference cache is checked for the leaf,
4357                  * and if found we'll be able to drop any refs held by
4358                  * the leaf without needing to read it in.
4359                  */
4360                 ref = btrfs_lookup_leaf_ref(root, bytenr);
4361                 if (ref && ref->generation != ptr_gen) {
4362                         btrfs_free_leaf_ref(root, ref);
4363                         ref = NULL;
4364                 }
4365                 if (ref) {
4366                         ret = cache_drop_leaf_ref(trans, root, ref);
4367                         BUG_ON(ret);
4368                         btrfs_remove_leaf_ref(root, ref);
4369                         btrfs_free_leaf_ref(root, ref);
4370                 } else {
4371                         /*
4372                          * the leaf wasn't in the reference cache, so
4373                          * we have to read it.
4374                          */
4375                         leaf = read_tree_block(root, bytenr, blocksize,
4376                                                ptr_gen);
4377                         ret = btrfs_drop_leaf_ref(trans, root, leaf);
4378                         BUG_ON(ret);
4379                         free_extent_buffer(leaf);
4380                 }
4381                 atomic_inc(&root->fs_info->throttle_gen);
4382                 wake_up(&root->fs_info->transaction_throttle);
4383                 cond_resched();
4384         }
4385
4386         /*
4387          * run through the loop again to free the refs on the leaves.
4388          * This is faster than doing it in the loop above because
4389          * the leaves are likely to be clustered together.  We end up
4390          * working in nice chunks on the extent allocation tree.
4391          */
4392         for (i = 0; i < refi; i++) {
4393                 bytenr = sorted[i].bytenr;
4394                 ret = btrfs_free_extent(trans, root, bytenr,
4395                                         blocksize, eb->start,
4396                                         root_owner, root_gen, 0, 1);
4397                 BUG_ON(ret);
4398
4399                 atomic_inc(&root->fs_info->throttle_gen);
4400                 wake_up(&root->fs_info->transaction_throttle);
4401                 cond_resched();
4402         }
4403 out:
4404         kfree(sorted);
4405
4406         /*
4407          * update the path to show we've processed the entire level 1
4408          * node.  This will get saved into the root's drop_snapshot_progress
4409          * field so these drops are not repeated again if this transaction
4410          * commits.
4411          */
4412         path->slots[1] = nritems;
4413         return 0;
4414 }
4415
4416 /*
4417  * helper function for drop_snapshot, this walks down the tree dropping ref
4418  * counts as it goes.
4419  */
4420 static noinline int walk_down_tree(struct btrfs_trans_handle *trans,
4421                                    struct btrfs_root *root,
4422                                    struct btrfs_path *path, int *level)
4423 {
4424         u64 root_owner;
4425         u64 root_gen;
4426         u64 bytenr;
4427         u64 ptr_gen;
4428         struct extent_buffer *next;
4429         struct extent_buffer *cur;
4430         struct extent_buffer *parent;
4431         u32 blocksize;
4432         int ret;
4433         u32 refs;
4434
4435         WARN_ON(*level < 0);
4436         WARN_ON(*level >= BTRFS_MAX_LEVEL);
4437         ret = drop_snap_lookup_refcount(trans, root, path->nodes[*level]->start,
4438                                 path->nodes[*level]->len, &refs);
4439         BUG_ON(ret);
4440         if (refs > 1)
4441                 goto out;
4442
4443         /*
4444          * walk down to the last node level and free all the leaves
4445          */
4446         while (*level >= 0) {
4447                 WARN_ON(*level < 0);
4448                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
4449                 cur = path->nodes[*level];
4450
4451                 if (btrfs_header_level(cur) != *level)
4452                         WARN_ON(1);
4453
4454                 if (path->slots[*level] >=
4455                     btrfs_header_nritems(cur))
4456                         break;
4457
4458                 /* the new code goes down to level 1 and does all the
4459                  * leaves pointed to that node in bulk.  So, this check
4460                  * for level 0 will always be false.
4461                  *
4462                  * But, the disk format allows the drop_snapshot_progress
4463                  * field in the root to leave things in a state where
4464                  * a leaf will need cleaning up here.  If someone crashes
4465                  * with the old code and then boots with the new code,
4466                  * we might find a leaf here.
4467                  */
4468                 if (*level == 0) {
4469                         ret = btrfs_drop_leaf_ref(trans, root, cur);
4470                         BUG_ON(ret);
4471                         break;
4472                 }
4473
4474                 /*
4475                  * once we get to level one, process the whole node
4476                  * at once, including everything below it.
4477                  */
4478                 if (*level == 1) {
4479                         ret = drop_level_one_refs(trans, root, path);
4480                         BUG_ON(ret);
4481                         break;
4482                 }
4483
4484                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
4485                 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
4486                 blocksize = btrfs_level_size(root, *level - 1);
4487
4488                 ret = drop_snap_lookup_refcount(trans, root, bytenr,
4489                                                 blocksize, &refs);
4490                 BUG_ON(ret);
4491
4492                 /*
4493                  * if there is more than one reference, we don't need
4494                  * to read that node to drop any references it has.  We
4495                  * just drop the ref we hold on that node and move on to the
4496                  * next slot in this level.
4497                  */
4498                 if (refs != 1) {
4499                         parent = path->nodes[*level];
4500                         root_owner = btrfs_header_owner(parent);
4501                         root_gen = btrfs_header_generation(parent);
4502                         path->slots[*level]++;
4503
4504                         ret = btrfs_free_extent(trans, root, bytenr,
4505                                                 blocksize, parent->start,
4506                                                 root_owner, root_gen,
4507                                                 *level - 1, 1);
4508                         BUG_ON(ret);
4509
4510                         atomic_inc(&root->fs_info->throttle_gen);
4511                         wake_up(&root->fs_info->transaction_throttle);
4512                         cond_resched();
4513
4514                         continue;
4515                 }
4516
4517                 /*
4518                  * we need to keep freeing things in the next level down.
4519                  * read the block and loop around to process it
4520                  */
4521                 next = read_tree_block(root, bytenr, blocksize, ptr_gen);
4522                 WARN_ON(*level <= 0);
4523                 if (path->nodes[*level-1])
4524                         free_extent_buffer(path->nodes[*level-1]);
4525                 path->nodes[*level-1] = next;
4526                 *level = btrfs_header_level(next);
4527                 path->slots[*level] = 0;
4528                 cond_resched();
4529         }
4530 out:
4531         WARN_ON(*level < 0);
4532         WARN_ON(*level >= BTRFS_MAX_LEVEL);
4533
4534         if (path->nodes[*level] == root->node) {
4535                 parent = path->nodes[*level];
4536                 bytenr = path->nodes[*level]->start;
4537         } else {
4538                 parent = path->nodes[*level + 1];
4539                 bytenr = btrfs_node_blockptr(parent, path->slots[*level + 1]);
4540         }
4541
4542         blocksize = btrfs_level_size(root, *level);
4543         root_owner = btrfs_header_owner(parent);
4544         root_gen = btrfs_header_generation(parent);
4545
4546         /*
4547          * cleanup and free the reference on the last node
4548          * we processed
4549          */
4550         ret = btrfs_free_extent(trans, root, bytenr, blocksize,
4551                                   parent->start, root_owner, root_gen,
4552                                   *level, 1);
4553         free_extent_buffer(path->nodes[*level]);
4554         path->nodes[*level] = NULL;
4555
4556         *level += 1;
4557         BUG_ON(ret);
4558
4559         cond_resched();
4560         return 0;
4561 }
4562 #endif
4563
4564 /*
4565  * helper function for drop_subtree, this function is similar to
4566  * walk_down_tree. The main difference is that it checks reference
4567  * counts while tree blocks are locked.
4568  */
4569 static noinline int walk_down_tree(struct btrfs_trans_handle *trans,
4570                                    struct btrfs_root *root,
4571                                    struct btrfs_path *path, int *level)
4572 {
4573         struct extent_buffer *next;
4574         struct extent_buffer *cur;
4575         struct extent_buffer *parent;
4576         u64 bytenr;
4577         u64 ptr_gen;
4578         u64 refs;
4579         u64 flags;
4580         u32 blocksize;
4581         int ret;
4582
4583         cur = path->nodes[*level];
4584         ret = btrfs_lookup_extent_info(trans, root, cur->start, cur->len,
4585                                        &refs, &flags);
4586         BUG_ON(ret);
4587         if (refs > 1)
4588                 goto out;
4589
4590         BUG_ON(!(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF));
4591
4592         while (*level >= 0) {
4593                 cur = path->nodes[*level];
4594                 if (*level == 0) {
4595                         ret = btrfs_drop_leaf_ref(trans, root, cur);
4596                         BUG_ON(ret);
4597                         clean_tree_block(trans, root, cur);
4598                         break;
4599                 }
4600                 if (path->slots[*level] >= btrfs_header_nritems(cur)) {
4601                         clean_tree_block(trans, root, cur);
4602                         break;
4603                 }
4604
4605                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
4606                 blocksize = btrfs_level_size(root, *level - 1);
4607                 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
4608
4609                 next = read_tree_block(root, bytenr, blocksize, ptr_gen);
4610                 btrfs_tree_lock(next);
4611                 btrfs_set_lock_blocking(next);
4612
4613                 ret = btrfs_lookup_extent_info(trans, root, bytenr, blocksize,
4614                                                &refs, &flags);
4615                 BUG_ON(ret);
4616                 if (refs > 1) {
4617                         parent = path->nodes[*level];
4618                         ret = btrfs_free_extent(trans, root, bytenr,
4619                                                 blocksize, parent->start,
4620                                                 btrfs_header_owner(parent),
4621                                                 *level - 1, 0);
4622                         BUG_ON(ret);
4623                         path->slots[*level]++;
4624                         btrfs_tree_unlock(next);
4625                         free_extent_buffer(next);
4626                         continue;
4627                 }
4628
4629                 BUG_ON(!(flags & BTRFS_BLOCK_FLAG_FULL_BACKREF));
4630
4631                 *level = btrfs_header_level(next);
4632                 path->nodes[*level] = next;
4633                 path->slots[*level] = 0;
4634                 path->locks[*level] = 1;
4635                 cond_resched();
4636         }
4637 out:
4638         if (path->nodes[*level] == root->node)
4639                 parent = path->nodes[*level];
4640         else
4641                 parent = path->nodes[*level + 1];
4642         bytenr = path->nodes[*level]->start;
4643         blocksize = path->nodes[*level]->len;
4644
4645         ret = btrfs_free_extent(trans, root, bytenr, blocksize, parent->start,
4646                                 btrfs_header_owner(parent), *level, 0);
4647         BUG_ON(ret);
4648
4649         if (path->locks[*level]) {
4650                 btrfs_tree_unlock(path->nodes[*level]);
4651                 path->locks[*level] = 0;
4652         }
4653         free_extent_buffer(path->nodes[*level]);
4654         path->nodes[*level] = NULL;
4655         *level += 1;
4656         cond_resched();
4657         return 0;
4658 }
4659
4660 /*
4661  * helper for dropping snapshots.  This walks back up the tree in the path
4662  * to find the first node higher up where we haven't yet gone through
4663  * all the slots
4664  */
4665 static noinline int walk_up_tree(struct btrfs_trans_handle *trans,
4666                                  struct btrfs_root *root,
4667                                  struct btrfs_path *path,
4668                                  int *level, int max_level)
4669 {
4670         struct btrfs_root_item *root_item = &root->root_item;
4671         int i;
4672         int slot;
4673         int ret;
4674
4675         for (i = *level; i < max_level && path->nodes[i]; i++) {
4676                 slot = path->slots[i];
4677                 if (slot + 1 < btrfs_header_nritems(path->nodes[i])) {
4678                         /*
4679                          * there is more work to do in this level.
4680                          * Update the drop_progress marker to reflect
4681                          * the work we've done so far, and then bump
4682                          * the slot number
4683                          */
4684                         path->slots[i]++;
4685                         WARN_ON(*level == 0);
4686                         if (max_level == BTRFS_MAX_LEVEL) {
4687                                 btrfs_node_key(path->nodes[i],
4688                                                &root_item->drop_progress,
4689                                                path->slots[i]);
4690                                 root_item->drop_level = i;
4691                         }
4692                         *level = i;
4693                         return 0;
4694                 } else {
4695                         struct extent_buffer *parent;
4696
4697                         /*
4698                          * this whole node is done, free our reference
4699                          * on it and go up one level
4700                          */
4701                         if (path->nodes[*level] == root->node)
4702                                 parent = path->nodes[*level];
4703                         else
4704                                 parent = path->nodes[*level + 1];
4705
4706                         clean_tree_block(trans, root, path->nodes[i]);
4707                         ret = btrfs_free_extent(trans, root,
4708                                                 path->nodes[i]->start,
4709                                                 path->nodes[i]->len,
4710                                                 parent->start,
4711                                                 btrfs_header_owner(parent),
4712                                                 *level, 0);
4713                         BUG_ON(ret);
4714                         if (path->locks[*level]) {
4715                                 btrfs_tree_unlock(path->nodes[i]);
4716                                 path->locks[i] = 0;
4717                         }
4718                         free_extent_buffer(path->nodes[i]);
4719                         path->nodes[i] = NULL;
4720                         *level = i + 1;
4721                 }
4722         }
4723         return 1;
4724 }
4725
4726 /*
4727  * drop the reference count on the tree rooted at 'snap'.  This traverses
4728  * the tree freeing any blocks that have a ref count of zero after being
4729  * decremented.
4730  */
4731 int btrfs_drop_snapshot(struct btrfs_trans_handle *trans, struct btrfs_root
4732                         *root)
4733 {
4734         int ret = 0;
4735         int wret;
4736         int level;
4737         struct btrfs_path *path;
4738         int update_count;
4739         struct btrfs_root_item *root_item = &root->root_item;
4740
4741         path = btrfs_alloc_path();
4742         BUG_ON(!path);
4743
4744         level = btrfs_header_level(root->node);
4745         if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
4746                 path->nodes[level] = btrfs_lock_root_node(root);
4747                 btrfs_set_lock_blocking(path->nodes[level]);
4748                 path->slots[level] = 0;
4749                 path->locks[level] = 1;
4750         } else {
4751                 struct btrfs_key key;
4752                 struct btrfs_disk_key found_key;
4753                 struct extent_buffer *node;
4754
4755                 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
4756                 level = root_item->drop_level;
4757                 path->lowest_level = level;
4758                 wret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4759                 if (wret < 0) {
4760                         ret = wret;
4761                         goto out;
4762                 }
4763                 node = path->nodes[level];
4764                 btrfs_node_key(node, &found_key, path->slots[level]);
4765                 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
4766                                sizeof(found_key)));
4767                 /*
4768                  * unlock our path, this is safe because only this
4769                  * function is allowed to delete this snapshot
4770                  */
4771                 btrfs_unlock_up_safe(path, 0);
4772         }
4773         while (1) {
4774                 unsigned long update;
4775                 wret = walk_down_tree(trans, root, path, &level);
4776                 if (wret > 0)
4777                         break;
4778                 if (wret < 0)
4779                         ret = wret;
4780
4781                 wret = walk_up_tree(trans, root, path, &level,
4782                                     BTRFS_MAX_LEVEL);
4783                 if (wret > 0)
4784                         break;
4785                 if (wret < 0)
4786                         ret = wret;
4787                 if (trans->transaction->in_commit ||
4788                     trans->transaction->delayed_refs.flushing) {
4789                         ret = -EAGAIN;
4790                         break;
4791                 }
4792                 for (update_count = 0; update_count < 16; update_count++) {
4793                         update = trans->delayed_ref_updates;
4794                         trans->delayed_ref_updates = 0;
4795                         if (update)
4796                                 btrfs_run_delayed_refs(trans, root, update);
4797                         else
4798                                 break;
4799                 }
4800         }
4801 out:
4802         btrfs_free_path(path);
4803         return ret;
4804 }
4805
4806 int btrfs_drop_subtree(struct btrfs_trans_handle *trans,
4807                         struct btrfs_root *root,
4808                         struct extent_buffer *node,
4809                         struct extent_buffer *parent)
4810 {
4811         struct btrfs_path *path;
4812         int level;
4813         int parent_level;
4814         int ret = 0;
4815         int wret;
4816
4817         path = btrfs_alloc_path();
4818         BUG_ON(!path);
4819
4820         btrfs_assert_tree_locked(parent);
4821         parent_level = btrfs_header_level(parent);
4822         extent_buffer_get(parent);
4823         path->nodes[parent_level] = parent;
4824         path->slots[parent_level] = btrfs_header_nritems(parent);
4825
4826         btrfs_assert_tree_locked(node);
4827         level = btrfs_header_level(node);
4828         extent_buffer_get(node);
4829         path->nodes[level] = node;
4830         path->slots[level] = 0;
4831
4832         while (1) {
4833                 wret = walk_down_tree(trans, root, path, &level);
4834                 if (wret < 0)
4835                         ret = wret;
4836                 if (wret != 0)
4837                         break;
4838
4839                 wret = walk_up_tree(trans, root, path, &level, parent_level);
4840                 if (wret < 0)
4841                         ret = wret;
4842                 if (wret != 0)
4843                         break;
4844         }
4845
4846         btrfs_free_path(path);
4847         return ret;
4848 }
4849
4850 #if 0
4851 static unsigned long calc_ra(unsigned long start, unsigned long last,
4852                              unsigned long nr)
4853 {
4854         return min(last, start + nr - 1);
4855 }
4856
4857 static noinline int relocate_inode_pages(struct inode *inode, u64 start,
4858                                          u64 len)
4859 {
4860         u64 page_start;
4861         u64 page_end;
4862         unsigned long first_index;
4863         unsigned long last_index;
4864         unsigned long i;
4865         struct page *page;
4866         struct extent_io_tree *io_tree = &BTRFS_I(inode)->io_tree;
4867         struct file_ra_state *ra;
4868         struct btrfs_ordered_extent *ordered;
4869         unsigned int total_read = 0;
4870         unsigned int total_dirty = 0;
4871         int ret = 0;
4872
4873         ra = kzalloc(sizeof(*ra), GFP_NOFS);
4874
4875         mutex_lock(&inode->i_mutex);
4876         first_index = start >> PAGE_CACHE_SHIFT;
4877         last_index = (start + len - 1) >> PAGE_CACHE_SHIFT;
4878
4879         /* make sure the dirty trick played by the caller work */
4880         ret = invalidate_inode_pages2_range(inode->i_mapping,
4881                                             first_index, last_index);
4882         if (ret)
4883                 goto out_unlock;
4884
4885         file_ra_state_init(ra, inode->i_mapping);
4886
4887         for (i = first_index ; i <= last_index; i++) {
4888                 if (total_read % ra->ra_pages == 0) {
4889                         btrfs_force_ra(inode->i_mapping, ra, NULL, i,
4890                                        calc_ra(i, last_index, ra->ra_pages));
4891                 }
4892                 total_read++;
4893 again:
4894                 if (((u64)i << PAGE_CACHE_SHIFT) > i_size_read(inode))
4895                         BUG_ON(1);
4896                 page = grab_cache_page(inode->i_mapping, i);
4897                 if (!page) {
4898                         ret = -ENOMEM;
4899                         goto out_unlock;
4900                 }
4901                 if (!PageUptodate(page)) {
4902                         btrfs_readpage(NULL, page);
4903                         lock_page(page);
4904                         if (!PageUptodate(page)) {
4905                                 unlock_page(page);
4906                                 page_cache_release(page);
4907                                 ret = -EIO;
4908                                 goto out_unlock;
4909                         }
4910                 }
4911                 wait_on_page_writeback(page);
4912
4913                 page_start = (u64)page->index << PAGE_CACHE_SHIFT;
4914                 page_end = page_start + PAGE_CACHE_SIZE - 1;
4915                 lock_extent(io_tree, page_start, page_end, GFP_NOFS);
4916
4917                 ordered = btrfs_lookup_ordered_extent(inode, page_start);
4918                 if (ordered) {
4919                         unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
4920                         unlock_page(page);
4921                         page_cache_release(page);
4922                         btrfs_start_ordered_extent(inode, ordered, 1);
4923                         btrfs_put_ordered_extent(ordered);
4924                         goto again;
4925                 }
4926                 set_page_extent_mapped(page);
4927
4928                 if (i == first_index)
4929                         set_extent_bits(io_tree, page_start, page_end,
4930                                         EXTENT_BOUNDARY, GFP_NOFS);
4931                 btrfs_set_extent_delalloc(inode, page_start, page_end);
4932
4933                 set_page_dirty(page);
4934                 total_dirty++;
4935
4936                 unlock_extent(io_tree, page_start, page_end, GFP_NOFS);
4937                 unlock_page(page);
4938                 page_cache_release(page);
4939         }
4940
4941 out_unlock:
4942         kfree(ra);
4943         mutex_unlock(&inode->i_mutex);
4944         balance_dirty_pages_ratelimited_nr(inode->i_mapping, total_dirty);
4945         return ret;
4946 }
4947
4948 static noinline int relocate_data_extent(struct inode *reloc_inode,
4949                                          struct btrfs_key *extent_key,
4950                                          u64 offset)
4951 {
4952         struct btrfs_root *root = BTRFS_I(reloc_inode)->root;
4953         struct extent_map_tree *em_tree = &BTRFS_I(reloc_inode)->extent_tree;
4954         struct extent_map *em;
4955         u64 start = extent_key->objectid - offset;
4956         u64 end = start + extent_key->offset - 1;
4957
4958         em = alloc_extent_map(GFP_NOFS);
4959         BUG_ON(!em || IS_ERR(em));
4960
4961         em->start = start;
4962         em->len = extent_key->offset;
4963         em->block_len = extent_key->offset;
4964         em->block_start = extent_key->objectid;
4965         em->bdev = root->fs_info->fs_devices->latest_bdev;
4966         set_bit(EXTENT_FLAG_PINNED, &em->flags);
4967
4968         /* setup extent map to cheat btrfs_readpage */
4969         lock_extent(&BTRFS_I(reloc_inode)->io_tree, start, end, GFP_NOFS);
4970         while (1) {
4971                 int ret;
4972                 spin_lock(&em_tree->lock);
4973                 ret = add_extent_mapping(em_tree, em);
4974                 spin_unlock(&em_tree->lock);
4975                 if (ret != -EEXIST) {
4976                         free_extent_map(em);
4977                         break;
4978                 }
4979                 btrfs_drop_extent_cache(reloc_inode, start, end, 0);
4980         }
4981         unlock_extent(&BTRFS_I(reloc_inode)->io_tree, start, end, GFP_NOFS);
4982
4983         return relocate_inode_pages(reloc_inode, start, extent_key->offset);
4984 }
4985
4986 struct btrfs_ref_path {
4987         u64 extent_start;
4988         u64 nodes[BTRFS_MAX_LEVEL];
4989         u64 root_objectid;
4990         u64 root_generation;
4991         u64 owner_objectid;
4992         u32 num_refs;
4993         int lowest_level;
4994         int current_level;
4995         int shared_level;
4996
4997         struct btrfs_key node_keys[BTRFS_MAX_LEVEL];
4998         u64 new_nodes[BTRFS_MAX_LEVEL];
4999 };
5000
5001 struct disk_extent {
5002         u64 ram_bytes;
5003         u64 disk_bytenr;
5004         u64 disk_num_bytes;
5005         u64 offset;
5006         u64 num_bytes;
5007         u8 compression;
5008         u8 encryption;
5009         u16 other_encoding;
5010 };
5011
5012 static int is_cowonly_root(u64 root_objectid)
5013 {
5014         if (root_objectid == BTRFS_ROOT_TREE_OBJECTID ||
5015             root_objectid == BTRFS_EXTENT_TREE_OBJECTID ||
5016             root_objectid == BTRFS_CHUNK_TREE_OBJECTID ||
5017             root_objectid == BTRFS_DEV_TREE_OBJECTID ||
5018             root_objectid == BTRFS_TREE_LOG_OBJECTID ||
5019             root_objectid == BTRFS_CSUM_TREE_OBJECTID)
5020                 return 1;
5021         return 0;
5022 }
5023
5024 static noinline int __next_ref_path(struct btrfs_trans_handle *trans,
5025                                     struct btrfs_root *extent_root,
5026                                     struct btrfs_ref_path *ref_path,
5027                                     int first_time)
5028 {
5029         struct extent_buffer *leaf;
5030         struct btrfs_path *path;
5031         struct btrfs_extent_ref *ref;
5032         struct btrfs_key key;
5033         struct btrfs_key found_key;
5034         u64 bytenr;
5035         u32 nritems;
5036         int level;
5037         int ret = 1;
5038
5039         path = btrfs_alloc_path();
5040         if (!path)
5041                 return -ENOMEM;
5042
5043         if (first_time) {
5044                 ref_path->lowest_level = -1;
5045                 ref_path->current_level = -1;
5046                 ref_path->shared_level = -1;
5047                 goto walk_up;
5048         }
5049 walk_down:
5050         level = ref_path->current_level - 1;
5051         while (level >= -1) {
5052                 u64 parent;
5053                 if (level < ref_path->lowest_level)
5054                         break;
5055
5056                 if (level >= 0)
5057                         bytenr = ref_path->nodes[level];
5058                 else
5059                         bytenr = ref_path->extent_start;
5060                 BUG_ON(bytenr == 0);
5061
5062                 parent = ref_path->nodes[level + 1];
5063                 ref_path->nodes[level + 1] = 0;
5064                 ref_path->current_level = level;
5065                 BUG_ON(parent == 0);
5066
5067                 key.objectid = bytenr;
5068                 key.offset = parent + 1;
5069                 key.type = BTRFS_EXTENT_REF_KEY;
5070
5071                 ret = btrfs_search_slot(trans, extent_root, &key, path, 0, 0);
5072                 if (ret < 0)
5073                         goto out;
5074                 BUG_ON(ret == 0);
5075
5076                 leaf = path->nodes[0];
5077                 nritems = btrfs_header_nritems(leaf);
5078                 if (path->slots[0] >= nritems) {
5079                         ret = btrfs_next_leaf(extent_root, path);
5080                         if (ret < 0)
5081                                 goto out;
5082                         if (ret > 0)
5083                                 goto next;
5084                         leaf = path->nodes[0];
5085                 }
5086
5087                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5088                 if (found_key.objectid == bytenr &&
5089                     found_key.type == BTRFS_EXTENT_REF_KEY) {
5090                         if (level < ref_path->shared_level)
5091                                 ref_path->shared_level = level;
5092                         goto found;
5093                 }
5094 next:
5095                 level--;
5096                 btrfs_release_path(extent_root, path);
5097                 cond_resched();
5098         }
5099         /* reached lowest level */
5100         ret = 1;
5101         goto out;
5102 walk_up:
5103         level = ref_path->current_level;
5104         while (level < BTRFS_MAX_LEVEL - 1) {
5105                 u64 ref_objectid;
5106
5107                 if (level >= 0)
5108                         bytenr = ref_path->nodes[level];
5109                 else
5110                         bytenr = ref_path->extent_start;
5111
5112                 BUG_ON(bytenr == 0);
5113
5114                 key.objectid = bytenr;
5115                 key.offset = 0;
5116                 key.type = BTRFS_EXTENT_REF_KEY;
5117
5118                 ret = btrfs_search_slot(trans, extent_root, &key, path, 0, 0);
5119                 if (ret < 0)
5120                         goto out;
5121
5122                 leaf = path->nodes[0];
5123                 nritems = btrfs_header_nritems(leaf);
5124                 if (path->slots[0] >= nritems) {
5125                         ret = btrfs_next_leaf(extent_root, path);
5126                         if (ret < 0)
5127                                 goto out;
5128                         if (ret > 0) {
5129                                 /* the extent was freed by someone */
5130                                 if (ref_path->lowest_level == level)
5131                                         goto out;
5132                                 btrfs_release_path(extent_root, path);
5133                                 goto walk_down;
5134                         }
5135                         leaf = path->nodes[0];
5136                 }
5137
5138                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5139                 if (found_key.objectid != bytenr ||
5140                                 found_key.type != BTRFS_EXTENT_REF_KEY) {
5141                         /* the extent was freed by someone */
5142                         if (ref_path->lowest_level == level) {
5143                                 ret = 1;
5144                                 goto out;
5145                         }
5146                         btrfs_release_path(extent_root, path);
5147                         goto walk_down;
5148                 }
5149 found:
5150                 ref = btrfs_item_ptr(leaf, path->slots[0],
5151                                 struct btrfs_extent_ref);
5152                 ref_objectid = btrfs_ref_objectid(leaf, ref);
5153                 if (ref_objectid < BTRFS_FIRST_FREE_OBJECTID) {
5154                         if (first_time) {
5155                                 level = (int)ref_objectid;
5156                                 BUG_ON(level >= BTRFS_MAX_LEVEL);
5157                                 ref_path->lowest_level = level;
5158                                 ref_path->current_level = level;
5159                                 ref_path->nodes[level] = bytenr;
5160                         } else {
5161                                 WARN_ON(ref_objectid != level);
5162                         }
5163                 } else {
5164                         WARN_ON(level != -1);
5165                 }
5166                 first_time = 0;
5167
5168                 if (ref_path->lowest_level == level) {
5169                         ref_path->owner_objectid = ref_objectid;
5170                         ref_path->num_refs = btrfs_ref_num_refs(leaf, ref);
5171                 }
5172
5173                 /*
5174                  * the block is tree root or the block isn't in reference
5175                  * counted tree.
5176                  */
5177                 if (found_key.objectid == found_key.offset ||
5178                     is_cowonly_root(btrfs_ref_root(leaf, ref))) {
5179                         ref_path->root_objectid = btrfs_ref_root(leaf, ref);
5180                         ref_path->root_generation =
5181                                 btrfs_ref_generation(leaf, ref);
5182                         if (level < 0) {
5183                                 /* special reference from the tree log */
5184                                 ref_path->nodes[0] = found_key.offset;
5185                                 ref_path->current_level = 0;
5186                         }
5187                         ret = 0;
5188                         goto out;
5189                 }
5190
5191                 level++;
5192                 BUG_ON(ref_path->nodes[level] != 0);
5193                 ref_path->nodes[level] = found_key.offset;
5194                 ref_path->current_level = level;
5195
5196                 /*
5197                  * the reference was created in the running transaction,
5198                  * no need to continue walking up.
5199                  */
5200                 if (btrfs_ref_generation(leaf, ref) == trans->transid) {
5201                         ref_path->root_objectid = btrfs_ref_root(leaf, ref);
5202                         ref_path->root_generation =
5203                                 btrfs_ref_generation(leaf, ref);
5204                         ret = 0;
5205                         goto out;
5206                 }
5207
5208                 btrfs_release_path(extent_root, path);
5209                 cond_resched();
5210         }
5211         /* reached max tree level, but no tree root found. */
5212         BUG();
5213 out:
5214         btrfs_free_path(path);
5215         return ret;
5216 }
5217
5218 static int btrfs_first_ref_path(struct btrfs_trans_handle *trans,
5219                                 struct btrfs_root *extent_root,
5220                                 struct btrfs_ref_path *ref_path,
5221                                 u64 extent_start)
5222 {
5223         memset(ref_path, 0, sizeof(*ref_path));
5224         ref_path->extent_start = extent_start;
5225
5226         return __next_ref_path(trans, extent_root, ref_path, 1);
5227 }
5228
5229 static int btrfs_next_ref_path(struct btrfs_trans_handle *trans,
5230                                struct btrfs_root *extent_root,
5231                                struct btrfs_ref_path *ref_path)
5232 {
5233         return __next_ref_path(trans, extent_root, ref_path, 0);
5234 }
5235
5236 static noinline int get_new_locations(struct inode *reloc_inode,
5237                                       struct btrfs_key *extent_key,
5238                                       u64 offset, int no_fragment,
5239                                       struct disk_extent **extents,
5240                                       int *nr_extents)
5241 {
5242         struct btrfs_root *root = BTRFS_I(reloc_inode)->root;
5243         struct btrfs_path *path;
5244         struct btrfs_file_extent_item *fi;
5245         struct extent_buffer *leaf;
5246         struct disk_extent *exts = *extents;
5247         struct btrfs_key found_key;
5248         u64 cur_pos;
5249         u64 last_byte;
5250         u32 nritems;
5251         int nr = 0;
5252         int max = *nr_extents;
5253         int ret;
5254
5255         WARN_ON(!no_fragment && *extents);
5256         if (!exts) {
5257                 max = 1;
5258                 exts = kmalloc(sizeof(*exts) * max, GFP_NOFS);
5259                 if (!exts)
5260                         return -ENOMEM;
5261         }
5262
5263         path = btrfs_alloc_path();
5264         BUG_ON(!path);
5265
5266         cur_pos = extent_key->objectid - offset;
5267         last_byte = extent_key->objectid + extent_key->offset;
5268         ret = btrfs_lookup_file_extent(NULL, root, path, reloc_inode->i_ino,
5269                                        cur_pos, 0);
5270         if (ret < 0)
5271                 goto out;
5272         if (ret > 0) {
5273                 ret = -ENOENT;
5274                 goto out;
5275         }
5276
5277         while (1) {
5278                 leaf = path->nodes[0];
5279                 nritems = btrfs_header_nritems(leaf);
5280                 if (path->slots[0] >= nritems) {
5281                         ret = btrfs_next_leaf(root, path);
5282                         if (ret < 0)
5283                                 goto out;
5284                         if (ret > 0)
5285                                 break;
5286                         leaf = path->nodes[0];
5287                 }
5288
5289                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
5290                 if (found_key.offset != cur_pos ||
5291                     found_key.type != BTRFS_EXTENT_DATA_KEY ||
5292                     found_key.objectid != reloc_inode->i_ino)
5293                         break;
5294
5295                 fi = btrfs_item_ptr(leaf, path->slots[0],
5296                                     struct btrfs_file_extent_item);
5297                 if (btrfs_file_extent_type(leaf, fi) !=
5298                     BTRFS_FILE_EXTENT_REG ||
5299                     btrfs_file_extent_disk_bytenr(leaf, fi) == 0)
5300                         break;
5301
5302                 if (nr == max) {
5303                         struct disk_extent *old = exts;
5304                         max *= 2;
5305                         exts = kzalloc(sizeof(*exts) * max, GFP_NOFS);
5306                         memcpy(exts, old, sizeof(*exts) * nr);
5307                         if (old != *extents)
5308                                 kfree(old);
5309                 }
5310
5311                 exts[nr].disk_bytenr =
5312                         btrfs_file_extent_disk_bytenr(leaf, fi);
5313                 exts[nr].disk_num_bytes =
5314                         btrfs_file_extent_disk_num_bytes(leaf, fi);
5315                 exts[nr].offset = btrfs_file_extent_offset(leaf, fi);
5316                 exts[nr].num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
5317                 exts[nr].ram_bytes = btrfs_file_extent_ram_bytes(leaf, fi);
5318                 exts[nr].compression = btrfs_file_extent_compression(leaf, fi);
5319                 exts[nr].encryption = btrfs_file_extent_encryption(leaf, fi);
5320                 exts[nr].other_encoding = btrfs_file_extent_other_encoding(leaf,
5321                                                                            fi);
5322                 BUG_ON(exts[nr].offset > 0);
5323                 BUG_ON(exts[nr].compression || exts[nr].encryption);
5324                 BUG_ON(exts[nr].num_bytes != exts[nr].disk_num_bytes);
5325
5326                 cur_pos += exts[nr].num_bytes;
5327                 nr++;
5328
5329                 if (cur_pos + offset >= last_byte)
5330                         break;
5331
5332                 if (no_fragment) {
5333                         ret = 1;
5334                         goto out;
5335                 }
5336                 path->slots[0]++;
5337         }
5338
5339         BUG_ON(cur_pos + offset > last_byte);
5340         if (cur_pos + offset < last_byte) {
5341                 ret = -ENOENT;
5342                 goto out;
5343         }
5344         ret = 0;
5345 out:
5346         btrfs_free_path(path);
5347         if (ret) {
5348                 if (exts != *extents)
5349                         kfree(exts);
5350         } else {
5351                 *extents = exts;
5352                 *nr_extents = nr;
5353         }
5354         return ret;
5355 }
5356
5357 static noinline int replace_one_extent(struct btrfs_trans_handle *trans,
5358                                         struct btrfs_root *root,
5359                                         struct btrfs_path *path,
5360                                         struct btrfs_key *extent_key,
5361                                         struct btrfs_key *leaf_key,
5362                                         struct btrfs_ref_path *ref_path,
5363                                         struct disk_extent *new_extents,
5364                                         int nr_extents)
5365 {
5366         struct extent_buffer *leaf;
5367         struct btrfs_file_extent_item *fi;
5368         struct inode *inode = NULL;
5369         struct btrfs_key key;
5370         u64 lock_start = 0;
5371         u64 lock_end = 0;
5372         u64 num_bytes;
5373         u64 ext_offset;
5374         u64 search_end = (u64)-1;
5375         u32 nritems;
5376         int nr_scaned = 0;
5377         int extent_locked = 0;
5378         int extent_type;
5379         int ret;
5380
5381         memcpy(&key, leaf_key, sizeof(key));
5382         if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS) {
5383                 if (key.objectid < ref_path->owner_objectid ||
5384                     (key.objectid == ref_path->owner_objectid &&
5385                      key.type < BTRFS_EXTENT_DATA_KEY)) {
5386                         key.objectid = ref_path->owner_objectid;
5387                         key.type = BTRFS_EXTENT_DATA_KEY;
5388                         key.offset = 0;
5389                 }
5390         }
5391
5392         while (1) {
5393                 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
5394                 if (ret < 0)
5395                         goto out;
5396
5397                 leaf = path->nodes[0];
5398                 nritems = btrfs_header_nritems(leaf);
5399 next:
5400                 if (extent_locked && ret > 0) {
5401                         /*
5402                          * the file extent item was modified by someone
5403                          * before the extent got locked.
5404                          */
5405                         unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
5406                                       lock_end, GFP_NOFS);
5407                         extent_locked = 0;
5408                 }
5409
5410                 if (path->slots[0] >= nritems) {
5411                         if (++nr_scaned > 2)
5412                                 break;
5413
5414                         BUG_ON(extent_locked);
5415                         ret = btrfs_next_leaf(root, path);
5416                         if (ret < 0)
5417                                 goto out;
5418                         if (ret > 0)
5419                                 break;
5420                         leaf = path->nodes[0];
5421                         nritems = btrfs_header_nritems(leaf);
5422                 }
5423
5424                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
5425
5426                 if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS) {
5427                         if ((key.objectid > ref_path->owner_objectid) ||
5428                             (key.objectid == ref_path->owner_objectid &&
5429                              key.type > BTRFS_EXTENT_DATA_KEY) ||
5430                             key.offset >= search_end)
5431                                 break;
5432                 }
5433
5434                 if (inode && key.objectid != inode->i_ino) {
5435                         BUG_ON(extent_locked);
5436                         btrfs_release_path(root, path);
5437                         mutex_unlock(&inode->i_mutex);
5438                         iput(inode);
5439                         inode = NULL;
5440                         continue;
5441                 }
5442
5443                 if (key.type != BTRFS_EXTENT_DATA_KEY) {
5444                         path->slots[0]++;
5445                         ret = 1;
5446                         goto next;
5447                 }
5448                 fi = btrfs_item_ptr(leaf, path->slots[0],
5449                                     struct btrfs_file_extent_item);
5450                 extent_type = btrfs_file_extent_type(leaf, fi);
5451                 if ((extent_type != BTRFS_FILE_EXTENT_REG &&
5452                      extent_type != BTRFS_FILE_EXTENT_PREALLOC) ||
5453                     (btrfs_file_extent_disk_bytenr(leaf, fi) !=
5454                      extent_key->objectid)) {
5455                         path->slots[0]++;
5456                         ret = 1;
5457                         goto next;
5458                 }
5459
5460                 num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
5461                 ext_offset = btrfs_file_extent_offset(leaf, fi);
5462
5463                 if (search_end == (u64)-1) {
5464                         search_end = key.offset - ext_offset +
5465                                 btrfs_file_extent_ram_bytes(leaf, fi);
5466                 }
5467
5468                 if (!extent_locked) {
5469                         lock_start = key.offset;
5470                         lock_end = lock_start + num_bytes - 1;
5471                 } else {
5472                         if (lock_start > key.offset ||
5473                             lock_end + 1 < key.offset + num_bytes) {
5474                                 unlock_extent(&BTRFS_I(inode)->io_tree,
5475                                               lock_start, lock_end, GFP_NOFS);
5476                                 extent_locked = 0;
5477                         }
5478                 }
5479
5480                 if (!inode) {
5481                         btrfs_release_path(root, path);
5482
5483                         inode = btrfs_iget_locked(root->fs_info->sb,
5484                                                   key.objectid, root);
5485                         if (inode->i_state & I_NEW) {
5486                                 BTRFS_I(inode)->root = root;
5487                                 BTRFS_I(inode)->location.objectid =
5488                                         key.objectid;
5489                                 BTRFS_I(inode)->location.type =
5490                                         BTRFS_INODE_ITEM_KEY;
5491                                 BTRFS_I(inode)->location.offset = 0;
5492                                 btrfs_read_locked_inode(inode);
5493                                 unlock_new_inode(inode);
5494                         }
5495                         /*
5496                          * some code call btrfs_commit_transaction while
5497                          * holding the i_mutex, so we can't use mutex_lock
5498                          * here.
5499                          */
5500                         if (is_bad_inode(inode) ||
5501                             !mutex_trylock(&inode->i_mutex)) {
5502                                 iput(inode);
5503                                 inode = NULL;
5504                                 key.offset = (u64)-1;
5505                                 goto skip;
5506                         }
5507                 }
5508
5509                 if (!extent_locked) {
5510                         struct btrfs_ordered_extent *ordered;
5511
5512                         btrfs_release_path(root, path);
5513
5514                         lock_extent(&BTRFS_I(inode)->io_tree, lock_start,
5515                                     lock_end, GFP_NOFS);
5516                         ordered = btrfs_lookup_first_ordered_extent(inode,
5517                                                                     lock_end);
5518                         if (ordered &&
5519                             ordered->file_offset <= lock_end &&
5520                             ordered->file_offset + ordered->len > lock_start) {
5521                                 unlock_extent(&BTRFS_I(inode)->io_tree,
5522                                               lock_start, lock_end, GFP_NOFS);
5523                                 btrfs_start_ordered_extent(inode, ordered, 1);
5524                                 btrfs_put_ordered_extent(ordered);
5525                                 key.offset += num_bytes;
5526                                 goto skip;
5527                         }
5528                         if (ordered)
5529                                 btrfs_put_ordered_extent(ordered);
5530
5531                         extent_locked = 1;
5532                         continue;
5533                 }
5534
5535                 if (nr_extents == 1) {
5536                         /* update extent pointer in place */
5537                         btrfs_set_file_extent_disk_bytenr(leaf, fi,
5538                                                 new_extents[0].disk_bytenr);
5539                         btrfs_set_file_extent_disk_num_bytes(leaf, fi,
5540                                                 new_extents[0].disk_num_bytes);
5541                         btrfs_mark_buffer_dirty(leaf);
5542
5543                         btrfs_drop_extent_cache(inode, key.offset,
5544                                                 key.offset + num_bytes - 1, 0);
5545
5546                         ret = btrfs_inc_extent_ref(trans, root,
5547                                                 new_extents[0].disk_bytenr,
5548                                                 new_extents[0].disk_num_bytes,
5549                                                 leaf->start,
5550                                                 root->root_key.objectid,
5551                                                 trans->transid,
5552                                                 key.objectid);
5553                         BUG_ON(ret);
5554
5555                         ret = btrfs_free_extent(trans, root,
5556                                                 extent_key->objectid,
5557                                                 extent_key->offset,
5558                                                 leaf->start,
5559                                                 btrfs_header_owner(leaf),
5560                                                 btrfs_header_generation(leaf),
5561                                                 key.objectid, 0);
5562                         BUG_ON(ret);
5563
5564                         btrfs_release_path(root, path);
5565                         key.offset += num_bytes;
5566                 } else {
5567                         BUG_ON(1);
5568 #if 0
5569                         u64 alloc_hint;
5570                         u64 extent_len;
5571                         int i;
5572                         /*
5573                          * drop old extent pointer at first, then insert the
5574                          * new pointers one bye one
5575                          */
5576                         btrfs_release_path(root, path);
5577                         ret = btrfs_drop_extents(trans, root, inode, key.offset,
5578                                                  key.offset + num_bytes,
5579                                                  key.offset, &alloc_hint);
5580                         BUG_ON(ret);
5581
5582                         for (i = 0; i < nr_extents; i++) {
5583                                 if (ext_offset >= new_extents[i].num_bytes) {
5584                                         ext_offset -= new_extents[i].num_bytes;
5585                                         continue;
5586                                 }
5587                                 extent_len = min(new_extents[i].num_bytes -
5588                                                  ext_offset, num_bytes);
5589
5590                                 ret = btrfs_insert_empty_item(trans, root,
5591                                                               path, &key,
5592                                                               sizeof(*fi));
5593                                 BUG_ON(ret);
5594
5595                                 leaf = path->nodes[0];
5596                                 fi = btrfs_item_ptr(leaf, path->slots[0],
5597                                                 struct btrfs_file_extent_item);
5598                                 btrfs_set_file_extent_generation(leaf, fi,
5599                                                         trans->transid);
5600                                 btrfs_set_file_extent_type(leaf, fi,
5601                                                         BTRFS_FILE_EXTENT_REG);
5602                                 btrfs_set_file_extent_disk_bytenr(leaf, fi,
5603                                                 new_extents[i].disk_bytenr);
5604                                 btrfs_set_file_extent_disk_num_bytes(leaf, fi,
5605                                                 new_extents[i].disk_num_bytes);
5606                                 btrfs_set_file_extent_ram_bytes(leaf, fi,
5607                                                 new_extents[i].ram_bytes);
5608
5609                                 btrfs_set_file_extent_compression(leaf, fi,
5610                                                 new_extents[i].compression);
5611                                 btrfs_set_file_extent_encryption(leaf, fi,
5612                                                 new_extents[i].encryption);
5613                                 btrfs_set_file_extent_other_encoding(leaf, fi,
5614                                                 new_extents[i].other_encoding);
5615
5616                                 btrfs_set_file_extent_num_bytes(leaf, fi,
5617                                                         extent_len);
5618                                 ext_offset += new_extents[i].offset;
5619                                 btrfs_set_file_extent_offset(leaf, fi,
5620                                                         ext_offset);
5621                                 btrfs_mark_buffer_dirty(leaf);
5622
5623                                 btrfs_drop_extent_cache(inode, key.offset,
5624                                                 key.offset + extent_len - 1, 0);
5625
5626                                 ret = btrfs_inc_extent_ref(trans, root,
5627                                                 new_extents[i].disk_bytenr,
5628                                                 new_extents[i].disk_num_bytes,
5629                                                 leaf->start,
5630                                                 root->root_key.objectid,
5631                                                 trans->transid, key.objectid);
5632                                 BUG_ON(ret);
5633                                 btrfs_release_path(root, path);
5634
5635                                 inode_add_bytes(inode, extent_len);
5636
5637                                 ext_offset = 0;
5638                                 num_bytes -= extent_len;
5639                                 key.offset += extent_len;
5640
5641                                 if (num_bytes == 0)
5642                                         break;
5643                         }
5644                         BUG_ON(i >= nr_extents);
5645 #endif
5646                 }
5647
5648                 if (extent_locked) {
5649                         unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
5650                                       lock_end, GFP_NOFS);
5651                         extent_locked = 0;
5652                 }
5653 skip:
5654                 if (ref_path->owner_objectid != BTRFS_MULTIPLE_OBJECTIDS &&
5655                     key.offset >= search_end)
5656                         break;
5657
5658                 cond_resched();
5659         }
5660         ret = 0;
5661 out:
5662         btrfs_release_path(root, path);
5663         if (inode) {
5664                 mutex_unlock(&inode->i_mutex);
5665                 if (extent_locked) {
5666                         unlock_extent(&BTRFS_I(inode)->io_tree, lock_start,
5667                                       lock_end, GFP_NOFS);
5668                 }
5669                 iput(inode);
5670         }
5671         return ret;
5672 }
5673
5674 int btrfs_reloc_tree_cache_ref(struct btrfs_trans_handle *trans,
5675                                struct btrfs_root *root,
5676                                struct extent_buffer *buf, u64 orig_start)
5677 {
5678         int level;
5679         int ret;
5680
5681         BUG_ON(btrfs_header_generation(buf) != trans->transid);
5682         BUG_ON(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID);
5683
5684         level = btrfs_header_level(buf);
5685         if (level == 0) {
5686                 struct btrfs_leaf_ref *ref;
5687                 struct btrfs_leaf_ref *orig_ref;
5688
5689                 orig_ref = btrfs_lookup_leaf_ref(root, orig_start);
5690                 if (!orig_ref)
5691                         return -ENOENT;
5692
5693                 ref = btrfs_alloc_leaf_ref(root, orig_ref->nritems);
5694                 if (!ref) {
5695                         btrfs_free_leaf_ref(root, orig_ref);
5696                         return -ENOMEM;
5697                 }
5698
5699                 ref->nritems = orig_ref->nritems;
5700                 memcpy(ref->extents, orig_ref->extents,
5701                         sizeof(ref->extents[0]) * ref->nritems);
5702
5703                 btrfs_free_leaf_ref(root, orig_ref);
5704
5705                 ref->root_gen = trans->transid;
5706                 ref->bytenr = buf->start;
5707                 ref->owner = btrfs_header_owner(buf);
5708                 ref->generation = btrfs_header_generation(buf);
5709
5710                 ret = btrfs_add_leaf_ref(root, ref, 0);
5711                 WARN_ON(ret);
5712                 btrfs_free_leaf_ref(root, ref);
5713         }
5714         return 0;
5715 }
5716
5717 static noinline int invalidate_extent_cache(struct btrfs_root *root,
5718                                         struct extent_buffer *leaf,
5719                                         struct btrfs_block_group_cache *group,
5720                                         struct btrfs_root *target_root)
5721 {
5722         struct btrfs_key key;
5723         struct inode *inode = NULL;
5724         struct btrfs_file_extent_item *fi;
5725         u64 num_bytes;
5726         u64 skip_objectid = 0;
5727         u32 nritems;
5728         u32 i;
5729
5730         nritems = btrfs_header_nritems(leaf);
5731         for (i = 0; i < nritems; i++) {
5732                 btrfs_item_key_to_cpu(leaf, &key, i);
5733                 if (key.objectid == skip_objectid ||
5734                     key.type != BTRFS_EXTENT_DATA_KEY)
5735                         continue;
5736                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
5737                 if (btrfs_file_extent_type(leaf, fi) ==
5738                     BTRFS_FILE_EXTENT_INLINE)
5739                         continue;
5740                 if (btrfs_file_extent_disk_bytenr(leaf, fi) == 0)
5741                         continue;
5742                 if (!inode || inode->i_ino != key.objectid) {
5743                         iput(inode);
5744                         inode = btrfs_ilookup(target_root->fs_info->sb,
5745                                               key.objectid, target_root, 1);
5746                 }
5747                 if (!inode) {
5748                         skip_objectid = key.objectid;
5749                         continue;
5750                 }
5751                 num_bytes = btrfs_file_extent_num_bytes(leaf, fi);
5752
5753                 lock_extent(&BTRFS_I(inode)->io_tree, key.offset,
5754                             key.offset + num_bytes - 1, GFP_NOFS);
5755                 btrfs_drop_extent_cache(inode, key.offset,
5756                                         key.offset + num_bytes - 1, 1);
5757                 unlock_extent(&BTRFS_I(inode)->io_tree, key.offset,
5758                               key.offset + num_bytes - 1, GFP_NOFS);
5759                 cond_resched();
5760         }
5761         iput(inode);
5762         return 0;
5763 }
5764
5765 static noinline int replace_extents_in_leaf(struct btrfs_trans_handle *trans,
5766                                         struct btrfs_root *root,
5767                                         struct extent_buffer *leaf,
5768                                         struct btrfs_block_group_cache *group,
5769                                         struct inode *reloc_inode)
5770 {
5771         struct btrfs_key key;
5772         struct btrfs_key extent_key;
5773         struct btrfs_file_extent_item *fi;
5774         struct btrfs_leaf_ref *ref;
5775         struct disk_extent *new_extent;
5776         u64 bytenr;
5777         u64 num_bytes;
5778         u32 nritems;
5779         u32 i;
5780         int ext_index;
5781         int nr_extent;
5782         int ret;
5783
5784         new_extent = kmalloc(sizeof(*new_extent), GFP_NOFS);
5785         BUG_ON(!new_extent);
5786
5787         ref = btrfs_lookup_leaf_ref(root, leaf->start);
5788         BUG_ON(!ref);
5789
5790         ext_index = -1;
5791         nritems = btrfs_header_nritems(leaf);
5792         for (i = 0; i < nritems; i++) {
5793                 btrfs_item_key_to_cpu(leaf, &key, i);
5794                 if (btrfs_key_type(&key) != BTRFS_EXTENT_DATA_KEY)
5795                         continue;
5796                 fi = btrfs_item_ptr(leaf, i, struct btrfs_file_extent_item);
5797                 if (btrfs_file_extent_type(leaf, fi) ==
5798                     BTRFS_FILE_EXTENT_INLINE)
5799                         continue;
5800                 bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
5801                 num_bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
5802                 if (bytenr == 0)
5803                         continue;
5804
5805                 ext_index++;
5806                 if (bytenr >= group->key.objectid + group->key.offset ||
5807                     bytenr + num_bytes <= group->key.objectid)
5808                         continue;
5809
5810                 extent_key.objectid = bytenr;
5811                 extent_key.offset = num_bytes;
5812                 extent_key.type = BTRFS_EXTENT_ITEM_KEY;
5813                 nr_extent = 1;
5814                 ret = get_new_locations(reloc_inode, &extent_key,
5815                                         group->key.objectid, 1,
5816                                         &new_extent, &nr_extent);
5817                 if (ret > 0)
5818                         continue;
5819                 BUG_ON(ret < 0);
5820
5821                 BUG_ON(ref->extents[ext_index].bytenr != bytenr);
5822                 BUG_ON(ref->extents[ext_index].num_bytes != num_bytes);
5823                 ref->extents[ext_index].bytenr = new_extent->disk_bytenr;
5824                 ref->extents[ext_index].num_bytes = new_extent->disk_num_bytes;
5825
5826                 btrfs_set_file_extent_disk_bytenr(leaf, fi,
5827                                                 new_extent->disk_bytenr);
5828                 btrfs_set_file_extent_disk_num_bytes(leaf, fi,
5829                                                 new_extent->disk_num_bytes);
5830                 btrfs_mark_buffer_dirty(leaf);
5831
5832                 ret = btrfs_inc_extent_ref(trans, root,
5833                                         new_extent->disk_bytenr,
5834                                         new_extent->disk_num_bytes,
5835                                         leaf->start,
5836                                         root->root_key.objectid,
5837                                         trans->transid, key.objectid);
5838                 BUG_ON(ret);
5839
5840                 ret = btrfs_free_extent(trans, root,
5841                                         bytenr, num_bytes, leaf->start,
5842                                         btrfs_header_owner(leaf),
5843                                         btrfs_header_generation(leaf),
5844                                         key.objectid, 0);
5845                 BUG_ON(ret);
5846                 cond_resched();
5847         }
5848         kfree(new_extent);
5849         BUG_ON(ext_index + 1 != ref->nritems);
5850         btrfs_free_leaf_ref(root, ref);
5851         return 0;
5852 }
5853
5854 int btrfs_free_reloc_root(struct btrfs_trans_handle *trans,
5855                           struct btrfs_root *root)
5856 {
5857         struct btrfs_root *reloc_root;
5858         int ret;
5859
5860         if (root->reloc_root) {
5861                 reloc_root = root->reloc_root;
5862                 root->reloc_root = NULL;
5863                 list_add(&reloc_root->dead_list,
5864                          &root->fs_info->dead_reloc_roots);
5865
5866                 btrfs_set_root_bytenr(&reloc_root->root_item,
5867                                       reloc_root->node->start);
5868                 btrfs_set_root_level(&root->root_item,
5869                                      btrfs_header_level(reloc_root->node));
5870                 memset(&reloc_root->root_item.drop_progress, 0,
5871                         sizeof(struct btrfs_disk_key));
5872                 reloc_root->root_item.drop_level = 0;
5873
5874                 ret = btrfs_update_root(trans, root->fs_info->tree_root,
5875                                         &reloc_root->root_key,
5876                                         &reloc_root->root_item);
5877                 BUG_ON(ret);
5878         }
5879         return 0;
5880 }
5881
5882 int btrfs_drop_dead_reloc_roots(struct btrfs_root *root)
5883 {
5884         struct btrfs_trans_handle *trans;
5885         struct btrfs_root *reloc_root;
5886         struct btrfs_root *prev_root = NULL;
5887         struct list_head dead_roots;
5888         int ret;
5889         unsigned long nr;
5890
5891         INIT_LIST_HEAD(&dead_roots);
5892         list_splice_init(&root->fs_info->dead_reloc_roots, &dead_roots);
5893
5894         while (!list_empty(&dead_roots)) {
5895                 reloc_root = list_entry(dead_roots.prev,
5896                                         struct btrfs_root, dead_list);
5897                 list_del_init(&reloc_root->dead_list);
5898
5899                 BUG_ON(reloc_root->commit_root != NULL);
5900                 while (1) {
5901                         trans = btrfs_join_transaction(root, 1);
5902                         BUG_ON(!trans);
5903
5904                         mutex_lock(&root->fs_info->drop_mutex);
5905                         ret = btrfs_drop_snapshot(trans, reloc_root);
5906                         if (ret != -EAGAIN)
5907                                 break;
5908                         mutex_unlock(&root->fs_info->drop_mutex);
5909
5910                         nr = trans->blocks_used;
5911                         ret = btrfs_end_transaction(trans, root);
5912                         BUG_ON(ret);
5913                         btrfs_btree_balance_dirty(root, nr);
5914                 }
5915
5916                 free_extent_buffer(reloc_root->node);
5917
5918                 ret = btrfs_del_root(trans, root->fs_info->tree_root,
5919                                      &reloc_root->root_key);
5920                 BUG_ON(ret);
5921                 mutex_unlock(&root->fs_info->drop_mutex);
5922
5923                 nr = trans->blocks_used;
5924                 ret = btrfs_end_transaction(trans, root);
5925                 BUG_ON(ret);
5926                 btrfs_btree_balance_dirty(root, nr);
5927
5928                 kfree(prev_root);
5929                 prev_root = reloc_root;
5930         }
5931         if (prev_root) {
5932                 btrfs_remove_leaf_refs(prev_root, (u64)-1, 0);
5933                 kfree(prev_root);
5934         }
5935         return 0;
5936 }
5937
5938 int btrfs_add_dead_reloc_root(struct btrfs_root *root)
5939 {
5940         list_add(&root->dead_list, &root->fs_info->dead_reloc_roots);
5941         return 0;
5942 }
5943
5944 int btrfs_cleanup_reloc_trees(struct btrfs_root *root)
5945 {
5946         struct btrfs_root *reloc_root;
5947         struct btrfs_trans_handle *trans;
5948         struct btrfs_key location;
5949         int found;
5950         int ret;
5951
5952         mutex_lock(&root->fs_info->tree_reloc_mutex);
5953         ret = btrfs_find_dead_roots(root, BTRFS_TREE_RELOC_OBJECTID, NULL);
5954         BUG_ON(ret);
5955         found = !list_empty(&root->fs_info->dead_reloc_roots);
5956         mutex_unlock(&root->fs_info->tree_reloc_mutex);
5957
5958         if (found) {
5959                 trans = btrfs_start_transaction(root, 1);
5960                 BUG_ON(!trans);
5961                 ret = btrfs_commit_transaction(trans, root);
5962                 BUG_ON(ret);
5963         }
5964
5965         location.objectid = BTRFS_DATA_RELOC_TREE_OBJECTID;
5966         location.offset = (u64)-1;
5967         location.type = BTRFS_ROOT_ITEM_KEY;
5968
5969         reloc_root = btrfs_read_fs_root_no_name(root->fs_info, &location);
5970         BUG_ON(!reloc_root);
5971         btrfs_orphan_cleanup(reloc_root);
5972         return 0;
5973 }
5974
5975 static noinline int init_reloc_tree(struct btrfs_trans_handle *trans,
5976                                     struct btrfs_root *root)
5977 {
5978         struct btrfs_root *reloc_root;
5979         struct extent_buffer *eb;
5980         struct btrfs_root_item *root_item;
5981         struct btrfs_key root_key;
5982         int ret;
5983
5984         BUG_ON(!root->ref_cows);
5985         if (root->reloc_root)
5986                 return 0;
5987
5988         root_item = kmalloc(sizeof(*root_item), GFP_NOFS);
5989         BUG_ON(!root_item);
5990
5991         ret = btrfs_copy_root(trans, root, root->commit_root,
5992                               &eb, BTRFS_TREE_RELOC_OBJECTID);
5993         BUG_ON(ret);
5994
5995         root_key.objectid = BTRFS_TREE_RELOC_OBJECTID;
5996         root_key.offset = root->root_key.objectid;
5997         root_key.type = BTRFS_ROOT_ITEM_KEY;
5998
5999         memcpy(root_item, &root->root_item, sizeof(root_item));
6000         btrfs_set_root_refs(root_item, 0);
6001         btrfs_set_root_bytenr(root_item, eb->start);
6002         btrfs_set_root_level(root_item, btrfs_header_level(eb));
6003         btrfs_set_root_generation(root_item, trans->transid);
6004
6005         btrfs_tree_unlock(eb);
6006         free_extent_buffer(eb);
6007
6008         ret = btrfs_insert_root(trans, root->fs_info->tree_root,
6009                                 &root_key, root_item);
6010         BUG_ON(ret);
6011         kfree(root_item);
6012
6013         reloc_root = btrfs_read_fs_root_no_radix(root->fs_info->tree_root,
6014                                                  &root_key);
6015         BUG_ON(!reloc_root);
6016         reloc_root->last_trans = trans->transid;
6017         reloc_root->commit_root = NULL;
6018         reloc_root->ref_tree = &root->fs_info->reloc_ref_tree;
6019
6020         root->reloc_root = reloc_root;
6021         return 0;
6022 }
6023
6024 /*
6025  * Core function of space balance.
6026  *
6027  * The idea is using reloc trees to relocate tree blocks in reference
6028  * counted roots. There is one reloc tree for each subvol, and all
6029  * reloc trees share same root key objectid. Reloc trees are snapshots
6030  * of the latest committed roots of subvols (root->commit_root).
6031  *
6032  * To relocate a tree block referenced by a subvol, there are two steps.
6033  * COW the block through subvol's reloc tree, then update block pointer
6034  * in the subvol to point to the new block. Since all reloc trees share
6035  * same root key objectid, doing special handing for tree blocks owned
6036  * by them is easy. Once a tree block has been COWed in one reloc tree,
6037  * we can use the resulting new block directly when the same block is
6038  * required to COW again through other reloc trees. By this way, relocated
6039  * tree blocks are shared between reloc trees, so they are also shared
6040  * between subvols.
6041  */
6042 static noinline int relocate_one_path(struct btrfs_trans_handle *trans,
6043                                       struct btrfs_root *root,
6044                                       struct btrfs_path *path,
6045                                       struct btrfs_key *first_key,
6046                                       struct btrfs_ref_path *ref_path,
6047                                       struct btrfs_block_group_cache *group,
6048                                       struct inode *reloc_inode)
6049 {
6050         struct btrfs_root *reloc_root;
6051         struct extent_buffer *eb = NULL;
6052         struct btrfs_key *keys;
6053         u64 *nodes;
6054         int level;
6055         int shared_level;
6056         int lowest_level = 0;
6057         int ret;
6058
6059         if (ref_path->owner_objectid < BTRFS_FIRST_FREE_OBJECTID)
6060                 lowest_level = ref_path->owner_objectid;
6061
6062         if (!root->ref_cows) {
6063                 path->lowest_level = lowest_level;
6064                 ret = btrfs_search_slot(trans, root, first_key, path, 0, 1);
6065                 BUG_ON(ret < 0);
6066                 path->lowest_level = 0;
6067                 btrfs_release_path(root, path);
6068                 return 0;
6069         }
6070
6071         mutex_lock(&root->fs_info->tree_reloc_mutex);
6072         ret = init_reloc_tree(trans, root);
6073         BUG_ON(ret);
6074         reloc_root = root->reloc_root;
6075
6076         shared_level = ref_path->shared_level;
6077         ref_path->shared_level = BTRFS_MAX_LEVEL - 1;
6078
6079         keys = ref_path->node_keys;
6080         nodes = ref_path->new_nodes;
6081         memset(&keys[shared_level + 1], 0,
6082                sizeof(*keys) * (BTRFS_MAX_LEVEL - shared_level - 1));
6083         memset(&nodes[shared_level + 1], 0,
6084                sizeof(*nodes) * (BTRFS_MAX_LEVEL - shared_level - 1));
6085
6086         if (nodes[lowest_level] == 0) {
6087                 path->lowest_level = lowest_level;
6088                 ret = btrfs_search_slot(trans, reloc_root, first_key, path,
6089                                         0, 1);
6090                 BUG_ON(ret);
6091                 for (level = lowest_level; level < BTRFS_MAX_LEVEL; level++) {
6092                         eb = path->nodes[level];
6093                         if (!eb || eb == reloc_root->node)
6094                                 break;
6095                         nodes[level] = eb->start;
6096                         if (level == 0)
6097                                 btrfs_item_key_to_cpu(eb, &keys[level], 0);
6098                         else
6099                                 btrfs_node_key_to_cpu(eb, &keys[level], 0);
6100                 }
6101                 if (nodes[0] &&
6102                     ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
6103                         eb = path->nodes[0];
6104                         ret = replace_extents_in_leaf(trans, reloc_root, eb,
6105                                                       group, reloc_inode);
6106                         BUG_ON(ret);
6107                 }
6108                 btrfs_release_path(reloc_root, path);
6109         } else {
6110                 ret = btrfs_merge_path(trans, reloc_root, keys, nodes,
6111                                        lowest_level);
6112                 BUG_ON(ret);
6113         }
6114
6115         /*
6116          * replace tree blocks in the fs tree with tree blocks in
6117          * the reloc tree.
6118          */
6119         ret = btrfs_merge_path(trans, root, keys, nodes, lowest_level);
6120         BUG_ON(ret < 0);
6121
6122         if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
6123                 ret = btrfs_search_slot(trans, reloc_root, first_key, path,
6124                                         0, 0);
6125                 BUG_ON(ret);
6126                 extent_buffer_get(path->nodes[0]);
6127                 eb = path->nodes[0];
6128                 btrfs_release_path(reloc_root, path);
6129                 ret = invalidate_extent_cache(reloc_root, eb, group, root);
6130                 BUG_ON(ret);
6131                 free_extent_buffer(eb);
6132         }
6133
6134         mutex_unlock(&root->fs_info->tree_reloc_mutex);
6135         path->lowest_level = 0;
6136         return 0;
6137 }
6138
6139 static noinline int relocate_tree_block(struct btrfs_trans_handle *trans,
6140                                         struct btrfs_root *root,
6141                                         struct btrfs_path *path,
6142                                         struct btrfs_key *first_key,
6143                                         struct btrfs_ref_path *ref_path)
6144 {
6145         int ret;
6146
6147         ret = relocate_one_path(trans, root, path, first_key,
6148                                 ref_path, NULL, NULL);
6149         BUG_ON(ret);
6150
6151         return 0;
6152 }
6153
6154 static noinline int del_extent_zero(struct btrfs_trans_handle *trans,
6155                                     struct btrfs_root *extent_root,
6156                                     struct btrfs_path *path,
6157                                     struct btrfs_key *extent_key)
6158 {
6159         int ret;
6160
6161         ret = btrfs_search_slot(trans, extent_root, extent_key, path, -1, 1);
6162         if (ret)
6163                 goto out;
6164         ret = btrfs_del_item(trans, extent_root, path);
6165 out:
6166         btrfs_release_path(extent_root, path);
6167         return ret;
6168 }
6169
6170 static noinline struct btrfs_root *read_ref_root(struct btrfs_fs_info *fs_info,
6171                                                 struct btrfs_ref_path *ref_path)
6172 {
6173         struct btrfs_key root_key;
6174
6175         root_key.objectid = ref_path->root_objectid;
6176         root_key.type = BTRFS_ROOT_ITEM_KEY;
6177         if (is_cowonly_root(ref_path->root_objectid))
6178                 root_key.offset = 0;
6179         else
6180                 root_key.offset = (u64)-1;
6181
6182         return btrfs_read_fs_root_no_name(fs_info, &root_key);
6183 }
6184
6185 static noinline int relocate_one_extent(struct btrfs_root *extent_root,
6186                                         struct btrfs_path *path,
6187                                         struct btrfs_key *extent_key,
6188                                         struct btrfs_block_group_cache *group,
6189                                         struct inode *reloc_inode, int pass)
6190 {
6191         struct btrfs_trans_handle *trans;
6192         struct btrfs_root *found_root;
6193         struct btrfs_ref_path *ref_path = NULL;
6194         struct disk_extent *new_extents = NULL;
6195         int nr_extents = 0;
6196         int loops;
6197         int ret;
6198         int level;
6199         struct btrfs_key first_key;
6200         u64 prev_block = 0;
6201
6202
6203         trans = btrfs_start_transaction(extent_root, 1);
6204         BUG_ON(!trans);
6205
6206         if (extent_key->objectid == 0) {
6207                 ret = del_extent_zero(trans, extent_root, path, extent_key);
6208                 goto out;
6209         }
6210
6211         ref_path = kmalloc(sizeof(*ref_path), GFP_NOFS);
6212         if (!ref_path) {
6213                 ret = -ENOMEM;
6214                 goto out;
6215         }
6216
6217         for (loops = 0; ; loops++) {
6218                 if (loops == 0) {
6219                         ret = btrfs_first_ref_path(trans, extent_root, ref_path,
6220                                                    extent_key->objectid);
6221                 } else {
6222                         ret = btrfs_next_ref_path(trans, extent_root, ref_path);
6223                 }
6224                 if (ret < 0)
6225                         goto out;
6226                 if (ret > 0)
6227                         break;
6228
6229                 if (ref_path->root_objectid == BTRFS_TREE_LOG_OBJECTID ||
6230                     ref_path->root_objectid == BTRFS_TREE_RELOC_OBJECTID)
6231                         continue;
6232
6233                 found_root = read_ref_root(extent_root->fs_info, ref_path);
6234                 BUG_ON(!found_root);
6235                 /*
6236                  * for reference counted tree, only process reference paths
6237                  * rooted at the latest committed root.
6238                  */
6239                 if (found_root->ref_cows &&
6240                     ref_path->root_generation != found_root->root_key.offset)
6241                         continue;
6242
6243                 if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
6244                         if (pass == 0) {
6245                                 /*
6246                                  * copy data extents to new locations
6247                                  */
6248                                 u64 group_start = group->key.objectid;
6249                                 ret = relocate_data_extent(reloc_inode,
6250                                                            extent_key,
6251                                                            group_start);
6252                                 if (ret < 0)
6253                                         goto out;
6254                                 break;
6255                         }
6256                         level = 0;
6257                 } else {
6258                         level = ref_path->owner_objectid;
6259                 }
6260
6261                 if (prev_block != ref_path->nodes[level]) {
6262                         struct extent_buffer *eb;
6263                         u64 block_start = ref_path->nodes[level];
6264                         u64 block_size = btrfs_level_size(found_root, level);
6265
6266                         eb = read_tree_block(found_root, block_start,
6267                                              block_size, 0);
6268                         btrfs_tree_lock(eb);
6269                         BUG_ON(level != btrfs_header_level(eb));
6270
6271                         if (level == 0)
6272                                 btrfs_item_key_to_cpu(eb, &first_key, 0);
6273                         else
6274                                 btrfs_node_key_to_cpu(eb, &first_key, 0);
6275
6276                         btrfs_tree_unlock(eb);
6277                         free_extent_buffer(eb);
6278                         prev_block = block_start;
6279                 }
6280
6281                 mutex_lock(&extent_root->fs_info->trans_mutex);
6282                 btrfs_record_root_in_trans(found_root);
6283                 mutex_unlock(&extent_root->fs_info->trans_mutex);
6284                 if (ref_path->owner_objectid >= BTRFS_FIRST_FREE_OBJECTID) {
6285                         /*
6286                          * try to update data extent references while
6287                          * keeping metadata shared between snapshots.
6288                          */
6289                         if (pass == 1) {
6290                                 ret = relocate_one_path(trans, found_root,
6291                                                 path, &first_key, ref_path,
6292                                                 group, reloc_inode);
6293                                 if (ret < 0)
6294                                         goto out;
6295                                 continue;
6296                         }
6297                         /*
6298                          * use fallback method to process the remaining
6299                          * references.
6300                          */
6301                         if (!new_extents) {
6302                                 u64 group_start = group->key.objectid;
6303                                 new_extents = kmalloc(sizeof(*new_extents),
6304                                                       GFP_NOFS);
6305                                 nr_extents = 1;
6306                                 ret = get_new_locations(reloc_inode,
6307                                                         extent_key,
6308                                                         group_start, 1,
6309                                                         &new_extents,
6310                                                         &nr_extents);
6311                                 if (ret)
6312                                         goto out;
6313                         }
6314                         ret = replace_one_extent(trans, found_root,
6315                                                 path, extent_key,
6316                                                 &first_key, ref_path,
6317                                                 new_extents, nr_extents);
6318                 } else {
6319                         ret = relocate_tree_block(trans, found_root, path,
6320                                                   &first_key, ref_path);
6321                 }
6322                 if (ret < 0)
6323                         goto out;
6324         }
6325         ret = 0;
6326 out:
6327         btrfs_end_transaction(trans, extent_root);
6328         kfree(new_extents);
6329         kfree(ref_path);
6330         return ret;
6331 }
6332 #endif
6333
6334 static u64 update_block_group_flags(struct btrfs_root *root, u64 flags)
6335 {
6336         u64 num_devices;
6337         u64 stripped = BTRFS_BLOCK_GROUP_RAID0 |
6338                 BTRFS_BLOCK_GROUP_RAID1 | BTRFS_BLOCK_GROUP_RAID10;
6339
6340         num_devices = root->fs_info->fs_devices->rw_devices;
6341         if (num_devices == 1) {
6342                 stripped |= BTRFS_BLOCK_GROUP_DUP;
6343                 stripped = flags & ~stripped;
6344
6345                 /* turn raid0 into single device chunks */
6346                 if (flags & BTRFS_BLOCK_GROUP_RAID0)
6347                         return stripped;
6348
6349                 /* turn mirroring into duplication */
6350                 if (flags & (BTRFS_BLOCK_GROUP_RAID1 |
6351                              BTRFS_BLOCK_GROUP_RAID10))
6352                         return stripped | BTRFS_BLOCK_GROUP_DUP;
6353                 return flags;
6354         } else {
6355                 /* they already had raid on here, just return */
6356                 if (flags & stripped)
6357                         return flags;
6358
6359                 stripped |= BTRFS_BLOCK_GROUP_DUP;
6360                 stripped = flags & ~stripped;
6361
6362                 /* switch duplicated blocks with raid1 */
6363                 if (flags & BTRFS_BLOCK_GROUP_DUP)
6364                         return stripped | BTRFS_BLOCK_GROUP_RAID1;
6365
6366                 /* turn single device chunks into raid0 */
6367                 return stripped | BTRFS_BLOCK_GROUP_RAID0;
6368         }
6369         return flags;
6370 }
6371
6372 static int __alloc_chunk_for_shrink(struct btrfs_root *root,
6373                      struct btrfs_block_group_cache *shrink_block_group,
6374                      int force)
6375 {
6376         struct btrfs_trans_handle *trans;
6377         u64 new_alloc_flags;
6378         u64 calc;
6379
6380         spin_lock(&shrink_block_group->lock);
6381         if (btrfs_block_group_used(&shrink_block_group->item) +
6382             shrink_block_group->reserved > 0) {
6383                 spin_unlock(&shrink_block_group->lock);
6384
6385                 trans = btrfs_start_transaction(root, 1);
6386                 spin_lock(&shrink_block_group->lock);
6387
6388                 new_alloc_flags = update_block_group_flags(root,
6389                                                    shrink_block_group->flags);
6390                 if (new_alloc_flags != shrink_block_group->flags) {
6391                         calc =
6392                              btrfs_block_group_used(&shrink_block_group->item);
6393                 } else {
6394                         calc = shrink_block_group->key.offset;
6395                 }
6396                 spin_unlock(&shrink_block_group->lock);
6397
6398                 do_chunk_alloc(trans, root->fs_info->extent_root,
6399                                calc + 2 * 1024 * 1024, new_alloc_flags, force);
6400
6401                 btrfs_end_transaction(trans, root);
6402         } else
6403                 spin_unlock(&shrink_block_group->lock);
6404         return 0;
6405 }
6406
6407
6408 int btrfs_prepare_block_group_relocation(struct btrfs_root *root,
6409                                          struct btrfs_block_group_cache *group)
6410
6411 {
6412         __alloc_chunk_for_shrink(root, group, 1);
6413         set_block_group_readonly(group);
6414         return 0;
6415 }
6416
6417 #if 0
6418 static int __insert_orphan_inode(struct btrfs_trans_handle *trans,
6419                                  struct btrfs_root *root,
6420                                  u64 objectid, u64 size)
6421 {
6422         struct btrfs_path *path;
6423         struct btrfs_inode_item *item;
6424         struct extent_buffer *leaf;
6425         int ret;
6426
6427         path = btrfs_alloc_path();
6428         if (!path)
6429                 return -ENOMEM;
6430
6431         path->leave_spinning = 1;
6432         ret = btrfs_insert_empty_inode(trans, root, path, objectid);
6433         if (ret)
6434                 goto out;
6435
6436         leaf = path->nodes[0];
6437         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_inode_item);
6438         memset_extent_buffer(leaf, 0, (unsigned long)item, sizeof(*item));
6439         btrfs_set_inode_generation(leaf, item, 1);
6440         btrfs_set_inode_size(leaf, item, size);
6441         btrfs_set_inode_mode(leaf, item, S_IFREG | 0600);
6442         btrfs_set_inode_flags(leaf, item, BTRFS_INODE_NOCOMPRESS);
6443         btrfs_mark_buffer_dirty(leaf);
6444         btrfs_release_path(root, path);
6445 out:
6446         btrfs_free_path(path);
6447         return ret;
6448 }
6449
6450 static noinline struct inode *create_reloc_inode(struct btrfs_fs_info *fs_info,
6451                                         struct btrfs_block_group_cache *group)
6452 {
6453         struct inode *inode = NULL;
6454         struct btrfs_trans_handle *trans;
6455         struct btrfs_root *root;
6456         struct btrfs_key root_key;
6457         u64 objectid = BTRFS_FIRST_FREE_OBJECTID;
6458         int err = 0;
6459
6460         root_key.objectid = BTRFS_DATA_RELOC_TREE_OBJECTID;
6461         root_key.type = BTRFS_ROOT_ITEM_KEY;
6462         root_key.offset = (u64)-1;
6463         root = btrfs_read_fs_root_no_name(fs_info, &root_key);
6464         if (IS_ERR(root))
6465                 return ERR_CAST(root);
6466
6467         trans = btrfs_start_transaction(root, 1);
6468         BUG_ON(!trans);
6469
6470         err = btrfs_find_free_objectid(trans, root, objectid, &objectid);
6471         if (err)
6472                 goto out;
6473
6474         err = __insert_orphan_inode(trans, root, objectid, group->key.offset);
6475         BUG_ON(err);
6476
6477         err = btrfs_insert_file_extent(trans, root, objectid, 0, 0, 0,
6478                                        group->key.offset, 0, group->key.offset,
6479                                        0, 0, 0);
6480         BUG_ON(err);
6481
6482         inode = btrfs_iget_locked(root->fs_info->sb, objectid, root);
6483         if (inode->i_state & I_NEW) {
6484                 BTRFS_I(inode)->root = root;
6485                 BTRFS_I(inode)->location.objectid = objectid;
6486                 BTRFS_I(inode)->location.type = BTRFS_INODE_ITEM_KEY;
6487                 BTRFS_I(inode)->location.offset = 0;
6488                 btrfs_read_locked_inode(inode);
6489                 unlock_new_inode(inode);
6490                 BUG_ON(is_bad_inode(inode));
6491         } else {
6492                 BUG_ON(1);
6493         }
6494         BTRFS_I(inode)->index_cnt = group->key.objectid;
6495
6496         err = btrfs_orphan_add(trans, inode);
6497 out:
6498         btrfs_end_transaction(trans, root);
6499         if (err) {
6500                 if (inode)
6501                         iput(inode);
6502                 inode = ERR_PTR(err);
6503         }
6504         return inode;
6505 }
6506
6507 int btrfs_reloc_clone_csums(struct inode *inode, u64 file_pos, u64 len)
6508 {
6509
6510         struct btrfs_ordered_sum *sums;
6511         struct btrfs_sector_sum *sector_sum;
6512         struct btrfs_ordered_extent *ordered;
6513         struct btrfs_root *root = BTRFS_I(inode)->root;
6514         struct list_head list;
6515         size_t offset;
6516         int ret;
6517         u64 disk_bytenr;
6518
6519         INIT_LIST_HEAD(&list);
6520
6521         ordered = btrfs_lookup_ordered_extent(inode, file_pos);
6522         BUG_ON(ordered->file_offset != file_pos || ordered->len != len);
6523
6524         disk_bytenr = file_pos + BTRFS_I(inode)->index_cnt;
6525         ret = btrfs_lookup_csums_range(root->fs_info->csum_root, disk_bytenr,
6526                                        disk_bytenr + len - 1, &list);
6527
6528         while (!list_empty(&list)) {
6529                 sums = list_entry(list.next, struct btrfs_ordered_sum, list);
6530                 list_del_init(&sums->list);
6531
6532                 sector_sum = sums->sums;
6533                 sums->bytenr = ordered->start;
6534
6535                 offset = 0;
6536                 while (offset < sums->len) {
6537                         sector_sum->bytenr += ordered->start - disk_bytenr;
6538                         sector_sum++;
6539                         offset += root->sectorsize;
6540                 }
6541
6542                 btrfs_add_ordered_sum(inode, ordered, sums);
6543         }
6544         btrfs_put_ordered_extent(ordered);
6545         return 0;
6546 }
6547
6548 int btrfs_relocate_block_group(struct btrfs_root *root, u64 group_start)
6549 {
6550         struct btrfs_trans_handle *trans;
6551         struct btrfs_path *path;
6552         struct btrfs_fs_info *info = root->fs_info;
6553         struct extent_buffer *leaf;
6554         struct inode *reloc_inode;
6555         struct btrfs_block_group_cache *block_group;
6556         struct btrfs_key key;
6557         u64 skipped;
6558         u64 cur_byte;
6559         u64 total_found;
6560         u32 nritems;
6561         int ret;
6562         int progress;
6563         int pass = 0;
6564
6565         root = root->fs_info->extent_root;
6566
6567         block_group = btrfs_lookup_block_group(info, group_start);
6568         BUG_ON(!block_group);
6569
6570         printk(KERN_INFO "btrfs relocating block group %llu flags %llu\n",
6571                (unsigned long long)block_group->key.objectid,
6572                (unsigned long long)block_group->flags);
6573
6574         path = btrfs_alloc_path();
6575         BUG_ON(!path);
6576
6577         reloc_inode = create_reloc_inode(info, block_group);
6578         BUG_ON(IS_ERR(reloc_inode));
6579
6580         __alloc_chunk_for_shrink(root, block_group, 1);
6581         set_block_group_readonly(block_group);
6582
6583         btrfs_start_delalloc_inodes(info->tree_root);
6584         btrfs_wait_ordered_extents(info->tree_root, 0);
6585 again:
6586         skipped = 0;
6587         total_found = 0;
6588         progress = 0;
6589         key.objectid = block_group->key.objectid;
6590         key.offset = 0;
6591         key.type = 0;
6592         cur_byte = key.objectid;
6593
6594         trans = btrfs_start_transaction(info->tree_root, 1);
6595         btrfs_commit_transaction(trans, info->tree_root);
6596
6597         mutex_lock(&root->fs_info->cleaner_mutex);
6598         btrfs_clean_old_snapshots(info->tree_root);
6599         btrfs_remove_leaf_refs(info->tree_root, (u64)-1, 1);
6600         mutex_unlock(&root->fs_info->cleaner_mutex);
6601
6602         trans = btrfs_start_transaction(info->tree_root, 1);
6603         btrfs_commit_transaction(trans, info->tree_root);
6604
6605         while (1) {
6606                 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
6607                 if (ret < 0)
6608                         goto out;
6609 next:
6610                 leaf = path->nodes[0];
6611                 nritems = btrfs_header_nritems(leaf);
6612                 if (path->slots[0] >= nritems) {
6613                         ret = btrfs_next_leaf(root, path);
6614                         if (ret < 0)
6615                                 goto out;
6616                         if (ret == 1) {
6617                                 ret = 0;
6618                                 break;
6619                         }
6620                         leaf = path->nodes[0];
6621                         nritems = btrfs_header_nritems(leaf);
6622                 }
6623
6624                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
6625
6626                 if (key.objectid >= block_group->key.objectid +
6627                     block_group->key.offset)
6628                         break;
6629
6630                 if (progress && need_resched()) {
6631                         btrfs_release_path(root, path);
6632                         cond_resched();
6633                         progress = 0;
6634                         continue;
6635                 }
6636                 progress = 1;
6637
6638                 if (btrfs_key_type(&key) != BTRFS_EXTENT_ITEM_KEY ||
6639                     key.objectid + key.offset <= cur_byte) {
6640                         path->slots[0]++;
6641                         goto next;
6642                 }
6643
6644                 total_found++;
6645                 cur_byte = key.objectid + key.offset;
6646                 btrfs_release_path(root, path);
6647
6648                 __alloc_chunk_for_shrink(root, block_group, 0);
6649                 ret = relocate_one_extent(root, path, &key, block_group,
6650                                           reloc_inode, pass);
6651                 BUG_ON(ret < 0);
6652                 if (ret > 0)
6653                         skipped++;
6654
6655                 key.objectid = cur_byte;
6656                 key.type = 0;
6657                 key.offset = 0;
6658         }
6659
6660         btrfs_release_path(root, path);
6661
6662         if (pass == 0) {
6663                 btrfs_wait_ordered_range(reloc_inode, 0, (u64)-1);
6664                 invalidate_mapping_pages(reloc_inode->i_mapping, 0, -1);
6665         }
6666
6667         if (total_found > 0) {
6668                 printk(KERN_INFO "btrfs found %llu extents in pass %d\n",
6669                        (unsigned long long)total_found, pass);
6670                 pass++;
6671                 if (total_found == skipped && pass > 2) {
6672                         iput(reloc_inode);
6673                         reloc_inode = create_reloc_inode(info, block_group);
6674                         pass = 0;
6675                 }
6676                 goto again;
6677         }
6678
6679         /* delete reloc_inode */
6680         iput(reloc_inode);
6681
6682         /* unpin extents in this range */
6683         trans = btrfs_start_transaction(info->tree_root, 1);
6684         btrfs_commit_transaction(trans, info->tree_root);
6685
6686         spin_lock(&block_group->lock);
6687         WARN_ON(block_group->pinned > 0);
6688         WARN_ON(block_group->reserved > 0);
6689         WARN_ON(btrfs_block_group_used(&block_group->item) > 0);
6690         spin_unlock(&block_group->lock);
6691         btrfs_put_block_group(block_group);
6692         ret = 0;
6693 out:
6694         btrfs_free_path(path);
6695         return ret;
6696 }
6697 #endif
6698
6699 static int find_first_block_group(struct btrfs_root *root,
6700                 struct btrfs_path *path, struct btrfs_key *key)
6701 {
6702         int ret = 0;
6703         struct btrfs_key found_key;
6704         struct extent_buffer *leaf;
6705         int slot;
6706
6707         ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
6708         if (ret < 0)
6709                 goto out;
6710
6711         while (1) {
6712                 slot = path->slots[0];
6713                 leaf = path->nodes[0];
6714                 if (slot >= btrfs_header_nritems(leaf)) {
6715                         ret = btrfs_next_leaf(root, path);
6716                         if (ret == 0)
6717                                 continue;
6718                         if (ret < 0)
6719                                 goto out;
6720                         break;
6721                 }
6722                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
6723
6724                 if (found_key.objectid >= key->objectid &&
6725                     found_key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
6726                         ret = 0;
6727                         goto out;
6728                 }
6729                 path->slots[0]++;
6730         }
6731         ret = -ENOENT;
6732 out:
6733         return ret;
6734 }
6735
6736 int btrfs_free_block_groups(struct btrfs_fs_info *info)
6737 {
6738         struct btrfs_block_group_cache *block_group;
6739         struct btrfs_space_info *space_info;
6740         struct rb_node *n;
6741
6742         spin_lock(&info->block_group_cache_lock);
6743         while ((n = rb_last(&info->block_group_cache_tree)) != NULL) {
6744                 block_group = rb_entry(n, struct btrfs_block_group_cache,
6745                                        cache_node);
6746                 rb_erase(&block_group->cache_node,
6747                          &info->block_group_cache_tree);
6748                 spin_unlock(&info->block_group_cache_lock);
6749
6750                 btrfs_remove_free_space_cache(block_group);
6751                 down_write(&block_group->space_info->groups_sem);
6752                 list_del(&block_group->list);
6753                 up_write(&block_group->space_info->groups_sem);
6754
6755                 WARN_ON(atomic_read(&block_group->count) != 1);
6756                 kfree(block_group);
6757
6758                 spin_lock(&info->block_group_cache_lock);
6759         }
6760         spin_unlock(&info->block_group_cache_lock);
6761
6762         /* now that all the block groups are freed, go through and
6763          * free all the space_info structs.  This is only called during
6764          * the final stages of unmount, and so we know nobody is
6765          * using them.  We call synchronize_rcu() once before we start,
6766          * just to be on the safe side.
6767          */
6768         synchronize_rcu();
6769
6770         while(!list_empty(&info->space_info)) {
6771                 space_info = list_entry(info->space_info.next,
6772                                         struct btrfs_space_info,
6773                                         list);
6774
6775                 list_del(&space_info->list);
6776                 kfree(space_info);
6777         }
6778         return 0;
6779 }
6780
6781 int btrfs_read_block_groups(struct btrfs_root *root)
6782 {
6783         struct btrfs_path *path;
6784         int ret;
6785         struct btrfs_block_group_cache *cache;
6786         struct btrfs_fs_info *info = root->fs_info;
6787         struct btrfs_space_info *space_info;
6788         struct btrfs_key key;
6789         struct btrfs_key found_key;
6790         struct extent_buffer *leaf;
6791
6792         root = info->extent_root;
6793         key.objectid = 0;
6794         key.offset = 0;
6795         btrfs_set_key_type(&key, BTRFS_BLOCK_GROUP_ITEM_KEY);
6796         path = btrfs_alloc_path();
6797         if (!path)
6798                 return -ENOMEM;
6799
6800         while (1) {
6801                 ret = find_first_block_group(root, path, &key);
6802                 if (ret > 0) {
6803                         ret = 0;
6804                         goto error;
6805                 }
6806                 if (ret != 0)
6807                         goto error;
6808
6809                 leaf = path->nodes[0];
6810                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
6811                 cache = kzalloc(sizeof(*cache), GFP_NOFS);
6812                 if (!cache) {
6813                         ret = -ENOMEM;
6814                         break;
6815                 }
6816
6817                 atomic_set(&cache->count, 1);
6818                 spin_lock_init(&cache->lock);
6819                 spin_lock_init(&cache->tree_lock);
6820                 mutex_init(&cache->cache_mutex);
6821                 INIT_LIST_HEAD(&cache->list);
6822                 INIT_LIST_HEAD(&cache->cluster_list);
6823                 read_extent_buffer(leaf, &cache->item,
6824                                    btrfs_item_ptr_offset(leaf, path->slots[0]),
6825                                    sizeof(cache->item));
6826                 memcpy(&cache->key, &found_key, sizeof(found_key));
6827
6828                 key.objectid = found_key.objectid + found_key.offset;
6829                 btrfs_release_path(root, path);
6830                 cache->flags = btrfs_block_group_flags(&cache->item);
6831
6832                 ret = update_space_info(info, cache->flags, found_key.offset,
6833                                         btrfs_block_group_used(&cache->item),
6834                                         &space_info);
6835                 BUG_ON(ret);
6836                 cache->space_info = space_info;
6837                 down_write(&space_info->groups_sem);
6838                 list_add_tail(&cache->list, &space_info->block_groups);
6839                 up_write(&space_info->groups_sem);
6840
6841                 ret = btrfs_add_block_group_cache(root->fs_info, cache);
6842                 BUG_ON(ret);
6843
6844                 set_avail_alloc_bits(root->fs_info, cache->flags);
6845                 if (btrfs_chunk_readonly(root, cache->key.objectid))
6846                         set_block_group_readonly(cache);
6847         }
6848         ret = 0;
6849 error:
6850         btrfs_free_path(path);
6851         return ret;
6852 }
6853
6854 int btrfs_make_block_group(struct btrfs_trans_handle *trans,
6855                            struct btrfs_root *root, u64 bytes_used,
6856                            u64 type, u64 chunk_objectid, u64 chunk_offset,
6857                            u64 size)
6858 {
6859         int ret;
6860         struct btrfs_root *extent_root;
6861         struct btrfs_block_group_cache *cache;
6862
6863         extent_root = root->fs_info->extent_root;
6864
6865         root->fs_info->last_trans_log_full_commit = trans->transid;
6866
6867         cache = kzalloc(sizeof(*cache), GFP_NOFS);
6868         if (!cache)
6869                 return -ENOMEM;
6870
6871         cache->key.objectid = chunk_offset;
6872         cache->key.offset = size;
6873         cache->key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
6874         atomic_set(&cache->count, 1);
6875         spin_lock_init(&cache->lock);
6876         spin_lock_init(&cache->tree_lock);
6877         mutex_init(&cache->cache_mutex);
6878         INIT_LIST_HEAD(&cache->list);
6879         INIT_LIST_HEAD(&cache->cluster_list);
6880
6881         btrfs_set_block_group_used(&cache->item, bytes_used);
6882         btrfs_set_block_group_chunk_objectid(&cache->item, chunk_objectid);
6883         cache->flags = type;
6884         btrfs_set_block_group_flags(&cache->item, type);
6885
6886         ret = update_space_info(root->fs_info, cache->flags, size, bytes_used,
6887                                 &cache->space_info);
6888         BUG_ON(ret);
6889         down_write(&cache->space_info->groups_sem);
6890         list_add_tail(&cache->list, &cache->space_info->block_groups);
6891         up_write(&cache->space_info->groups_sem);
6892
6893         ret = btrfs_add_block_group_cache(root->fs_info, cache);
6894         BUG_ON(ret);
6895
6896         ret = btrfs_insert_item(trans, extent_root, &cache->key, &cache->item,
6897                                 sizeof(cache->item));
6898         BUG_ON(ret);
6899
6900         set_avail_alloc_bits(extent_root->fs_info, type);
6901
6902         return 0;
6903 }
6904
6905 int btrfs_remove_block_group(struct btrfs_trans_handle *trans,
6906                              struct btrfs_root *root, u64 group_start)
6907 {
6908         struct btrfs_path *path;
6909         struct btrfs_block_group_cache *block_group;
6910         struct btrfs_free_cluster *cluster;
6911         struct btrfs_key key;
6912         int ret;
6913
6914         root = root->fs_info->extent_root;
6915
6916         block_group = btrfs_lookup_block_group(root->fs_info, group_start);
6917         BUG_ON(!block_group);
6918         BUG_ON(!block_group->ro);
6919
6920         memcpy(&key, &block_group->key, sizeof(key));
6921
6922         /* make sure this block group isn't part of an allocation cluster */
6923         cluster = &root->fs_info->data_alloc_cluster;
6924         spin_lock(&cluster->refill_lock);
6925         btrfs_return_cluster_to_free_space(block_group, cluster);
6926         spin_unlock(&cluster->refill_lock);
6927
6928         /*
6929          * make sure this block group isn't part of a metadata
6930          * allocation cluster
6931          */
6932         cluster = &root->fs_info->meta_alloc_cluster;
6933         spin_lock(&cluster->refill_lock);
6934         btrfs_return_cluster_to_free_space(block_group, cluster);
6935         spin_unlock(&cluster->refill_lock);
6936
6937         path = btrfs_alloc_path();
6938         BUG_ON(!path);
6939
6940         spin_lock(&root->fs_info->block_group_cache_lock);
6941         rb_erase(&block_group->cache_node,
6942                  &root->fs_info->block_group_cache_tree);
6943         spin_unlock(&root->fs_info->block_group_cache_lock);
6944         btrfs_remove_free_space_cache(block_group);
6945         down_write(&block_group->space_info->groups_sem);
6946         /*
6947          * we must use list_del_init so people can check to see if they
6948          * are still on the list after taking the semaphore
6949          */
6950         list_del_init(&block_group->list);
6951         up_write(&block_group->space_info->groups_sem);
6952
6953         spin_lock(&block_group->space_info->lock);
6954         block_group->space_info->total_bytes -= block_group->key.offset;
6955         block_group->space_info->bytes_readonly -= block_group->key.offset;
6956         spin_unlock(&block_group->space_info->lock);
6957         block_group->space_info->full = 0;
6958
6959         btrfs_put_block_group(block_group);
6960         btrfs_put_block_group(block_group);
6961
6962         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
6963         if (ret > 0)
6964                 ret = -EIO;
6965         if (ret < 0)
6966                 goto out;
6967
6968         ret = btrfs_del_item(trans, root, path);
6969 out:
6970         btrfs_free_path(path);
6971         return ret;
6972 }