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