fs/btrfs/extent-tree.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Copyright (C) 2007 Oracle.  All rights reserved.
   4  */
   5
   6 #include <linux/sched.h>
   7 #include <linux/sched/signal.h>
   8 #include <linux/pagemap.h>
   9 #include <linux/writeback.h>
  10 #include <linux/blkdev.h>
  11 #include <linux/sort.h>
  12 #include <linux/rcupdate.h>
  13 #include <linux/kthread.h>
  14 #include <linux/slab.h>
  15 #include <linux/ratelimit.h>
  16 #include <linux/percpu_counter.h>
  17 #include <linux/lockdep.h>
  18 #include <linux/crc32c.h>
  19 #include "tree-log.h"
  20 #include "disk-io.h"
  21 #include "print-tree.h"
  22 #include "volumes.h"
  23 #include "raid56.h"
  24 #include "locking.h"
  25 #include "free-space-cache.h"
  26 #include "free-space-tree.h"
  27 #include "math.h"
  28 #include "sysfs.h"
  29 #include "qgroup.h"
  30 #include "ref-verify.h"
  31
  32 #undef SCRAMBLE_DELAYED_REFS
  33
  34 /*
  35  * control flags for do_chunk_alloc's force field
  36  * CHUNK_ALLOC_NO_FORCE means to only allocate a chunk
  37  * if we really need one.
  38  *
  39  * CHUNK_ALLOC_LIMITED means to only try and allocate one
  40  * if we have very few chunks already allocated.  This is
  41  * used as part of the clustering code to help make sure
  42  * we have a good pool of storage to cluster in, without
  43  * filling the FS with empty chunks
  44  *
  45  * CHUNK_ALLOC_FORCE means it must try to allocate one
  46  *
  47  */
  48 enum {
  49         CHUNK_ALLOC_NO_FORCE = 0,
  50         CHUNK_ALLOC_LIMITED = 1,
  51         CHUNK_ALLOC_FORCE = 2,
  52 };
  53
  54 /*
  55  * Declare a helper function to detect underflow of various space info members
  56  */
  57 #define DECLARE_SPACE_INFO_UPDATE(name)                                 \
  58 static inline void update_##name(struct btrfs_space_info *sinfo,        \
  59                                  s64 bytes)                             \
  60 {                                                                       \
  61         if (bytes < 0 && sinfo->name < -bytes) {                        \
  62                 WARN_ON(1);                                             \
  63                 sinfo->name = 0;                                        \
  64                 return;                                                 \
  65         }                                                               \
  66         sinfo->name += bytes;                                           \
  67 }
  68
  69 DECLARE_SPACE_INFO_UPDATE(bytes_may_use);
  70 DECLARE_SPACE_INFO_UPDATE(bytes_pinned);
  71
  72 static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
  73                                struct btrfs_delayed_ref_node *node, u64 parent,
  74                                u64 root_objectid, u64 owner_objectid,
  75                                u64 owner_offset, int refs_to_drop,
  76                                struct btrfs_delayed_extent_op *extra_op);
  77 static void __run_delayed_extent_op(struct btrfs_delayed_extent_op *extent_op,
  78                                     struct extent_buffer *leaf,
  79                                     struct btrfs_extent_item *ei);
  80 static int alloc_reserved_file_extent(struct btrfs_trans_handle *trans,
  81                                       u64 parent, u64 root_objectid,
  82                                       u64 flags, u64 owner, u64 offset,
  83                                       struct btrfs_key *ins, int ref_mod);
  84 static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
  85                                      struct btrfs_delayed_ref_node *node,
  86                                      struct btrfs_delayed_extent_op *extent_op);
  87 static int do_chunk_alloc(struct btrfs_trans_handle *trans, u64 flags,
  88                           int force);
  89 static int find_next_key(struct btrfs_path *path, int level,
  90                          struct btrfs_key *key);
  91 static void dump_space_info(struct btrfs_fs_info *fs_info,
  92                             struct btrfs_space_info *info, u64 bytes,
  93                             int dump_block_groups);
  94 static int block_rsv_use_bytes(struct btrfs_block_rsv *block_rsv,
  95                                u64 num_bytes);
  96 static void space_info_add_new_bytes(struct btrfs_fs_info *fs_info,
  97                                      struct btrfs_space_info *space_info,
  98                                      u64 num_bytes);
  99 static void space_info_add_old_bytes(struct btrfs_fs_info *fs_info,
 100                                      struct btrfs_space_info *space_info,
 101                                      u64 num_bytes);
 102
 103 static noinline int
 104 block_group_cache_done(struct btrfs_block_group_cache *cache)
 105 {
 106         smp_mb();
 107         return cache->cached == BTRFS_CACHE_FINISHED ||
 108                 cache->cached == BTRFS_CACHE_ERROR;
 109 }
 110
 111 static int block_group_bits(struct btrfs_block_group_cache *cache, u64 bits)
 112 {
 113         return (cache->flags & bits) == bits;
 114 }
 115
 116 void btrfs_get_block_group(struct btrfs_block_group_cache *cache)
 117 {
 118         atomic_inc(&cache->count);
 119 }
 120
 121 void btrfs_put_block_group(struct btrfs_block_group_cache *cache)
 122 {
 123         if (atomic_dec_and_test(&cache->count)) {
 124                 WARN_ON(cache->pinned > 0);
 125                 WARN_ON(cache->reserved > 0);
 126
 127                 /*
 128                  * If not empty, someone is still holding mutex of
 129                  * full_stripe_lock, which can only be released by caller.
 130                  * And it will definitely cause use-after-free when caller
 131                  * tries to release full stripe lock.
 132                  *
 133                  * No better way to resolve, but only to warn.
 134                  */
 135                 WARN_ON(!RB_EMPTY_ROOT(&cache->full_stripe_locks_root.root));
 136                 kfree(cache->free_space_ctl);
 137                 kfree(cache);
 138         }
 139 }
 140
 141 /*
 142  * this adds the block group to the fs_info rb tree for the block group
 143  * cache
 144  */
 145 static int btrfs_add_block_group_cache(struct btrfs_fs_info *info,
 146                                 struct btrfs_block_group_cache *block_group)
 147 {
 148         struct rb_node **p;
 149         struct rb_node *parent = NULL;
 150         struct btrfs_block_group_cache *cache;
 151
 152         spin_lock(&info->block_group_cache_lock);
 153         p = &info->block_group_cache_tree.rb_node;
 154
 155         while (*p) {
 156                 parent = *p;
 157                 cache = rb_entry(parent, struct btrfs_block_group_cache,
 158                                  cache_node);
 159                 if (block_group->key.objectid < cache->key.objectid) {
 160                         p = &(*p)->rb_left;
 161                 } else if (block_group->key.objectid > cache->key.objectid) {
 162                         p = &(*p)->rb_right;
 163                 } else {
 164                         spin_unlock(&info->block_group_cache_lock);
 165                         return -EEXIST;
 166                 }
 167         }
 168
 169         rb_link_node(&block_group->cache_node, parent, p);
 170         rb_insert_color(&block_group->cache_node,
 171                         &info->block_group_cache_tree);
 172
 173         if (info->first_logical_byte > block_group->key.objectid)
 174                 info->first_logical_byte = block_group->key.objectid;
 175
 176         spin_unlock(&info->block_group_cache_lock);
 177
 178         return 0;
 179 }
 180
 181 /*
 182  * This will return the block group at or after bytenr if contains is 0, else
 183  * it will return the block group that contains the bytenr
 184  */
 185 static struct btrfs_block_group_cache *
 186 block_group_cache_tree_search(struct btrfs_fs_info *info, u64 bytenr,
 187                               int contains)
 188 {
 189         struct btrfs_block_group_cache *cache, *ret = NULL;
 190         struct rb_node *n;
 191         u64 end, start;
 192
 193         spin_lock(&info->block_group_cache_lock);
 194         n = info->block_group_cache_tree.rb_node;
 195
 196         while (n) {
 197                 cache = rb_entry(n, struct btrfs_block_group_cache,
 198                                  cache_node);
 199                 end = cache->key.objectid + cache->key.offset - 1;
 200                 start = cache->key.objectid;
 201
 202                 if (bytenr < start) {
 203                         if (!contains && (!ret || start < ret->key.objectid))
 204                                 ret = cache;
 205                         n = n->rb_left;
 206                 } else if (bytenr > start) {
 207                         if (contains && bytenr <= end) {
 208                                 ret = cache;
 209                                 break;
 210                         }
 211                         n = n->rb_right;
 212                 } else {
 213                         ret = cache;
 214                         break;
 215                 }
 216         }
 217         if (ret) {
 218                 btrfs_get_block_group(ret);
 219                 if (bytenr == 0 && info->first_logical_byte > ret->key.objectid)
 220                         info->first_logical_byte = ret->key.objectid;
 221         }
 222         spin_unlock(&info->block_group_cache_lock);
 223
 224         return ret;
 225 }
 226
 227 static int add_excluded_extent(struct btrfs_fs_info *fs_info,
 228                                u64 start, u64 num_bytes)
 229 {
 230         u64 end = start + num_bytes - 1;
 231         set_extent_bits(&fs_info->freed_extents[0],
 232                         start, end, EXTENT_UPTODATE);
 233         set_extent_bits(&fs_info->freed_extents[1],
 234                         start, end, EXTENT_UPTODATE);
 235         return 0;
 236 }
 237
 238 static void free_excluded_extents(struct btrfs_block_group_cache *cache)
 239 {
 240         struct btrfs_fs_info *fs_info = cache->fs_info;
 241         u64 start, end;
 242
 243         start = cache->key.objectid;
 244         end = start + cache->key.offset - 1;
 245
 246         clear_extent_bits(&fs_info->freed_extents[0],
 247                           start, end, EXTENT_UPTODATE);
 248         clear_extent_bits(&fs_info->freed_extents[1],
 249                           start, end, EXTENT_UPTODATE);
 250 }
 251
 252 static int exclude_super_stripes(struct btrfs_block_group_cache *cache)
 253 {
 254         struct btrfs_fs_info *fs_info = cache->fs_info;
 255         u64 bytenr;
 256         u64 *logical;
 257         int stripe_len;
 258         int i, nr, ret;
 259
 260         if (cache->key.objectid < BTRFS_SUPER_INFO_OFFSET) {
 261                 stripe_len = BTRFS_SUPER_INFO_OFFSET - cache->key.objectid;
 262                 cache->bytes_super += stripe_len;
 263                 ret = add_excluded_extent(fs_info, cache->key.objectid,
 264                                           stripe_len);
 265                 if (ret)
 266                         return ret;
 267         }
 268
 269         for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
 270                 bytenr = btrfs_sb_offset(i);
 271                 ret = btrfs_rmap_block(fs_info, cache->key.objectid,
 272                                        bytenr, &logical, &nr, &stripe_len);
 273                 if (ret)
 274                         return ret;
 275
 276                 while (nr--) {
 277                         u64 start, len;
 278
 279                         if (logical[nr] > cache->key.objectid +
 280                             cache->key.offset)
 281                                 continue;
 282
 283                         if (logical[nr] + stripe_len <= cache->key.objectid)
 284                                 continue;
 285
 286                         start = logical[nr];
 287                         if (start < cache->key.objectid) {
 288                                 start = cache->key.objectid;
 289                                 len = (logical[nr] + stripe_len) - start;
 290                         } else {
 291                                 len = min_t(u64, stripe_len,
 292                                             cache->key.objectid +
 293                                             cache->key.offset - start);
 294                         }
 295
 296                         cache->bytes_super += len;
 297                         ret = add_excluded_extent(fs_info, start, len);
 298                         if (ret) {
 299                                 kfree(logical);
 300                                 return ret;
 301                         }
 302                 }
 303
 304                 kfree(logical);
 305         }
 306         return 0;
 307 }
 308
 309 static struct btrfs_caching_control *
 310 get_caching_control(struct btrfs_block_group_cache *cache)
 311 {
 312         struct btrfs_caching_control *ctl;
 313
 314         spin_lock(&cache->lock);
 315         if (!cache->caching_ctl) {
 316                 spin_unlock(&cache->lock);
 317                 return NULL;
 318         }
 319
 320         ctl = cache->caching_ctl;
 321         refcount_inc(&ctl->count);
 322         spin_unlock(&cache->lock);
 323         return ctl;
 324 }
 325
 326 static void put_caching_control(struct btrfs_caching_control *ctl)
 327 {
 328         if (refcount_dec_and_test(&ctl->count))
 329                 kfree(ctl);
 330 }
 331
 332 #ifdef CONFIG_BTRFS_DEBUG
 333 static void fragment_free_space(struct btrfs_block_group_cache *block_group)
 334 {
 335         struct btrfs_fs_info *fs_info = block_group->fs_info;
 336         u64 start = block_group->key.objectid;
 337         u64 len = block_group->key.offset;
 338         u64 chunk = block_group->flags & BTRFS_BLOCK_GROUP_METADATA ?
 339                 fs_info->nodesize : fs_info->sectorsize;
 340         u64 step = chunk << 1;
 341
 342         while (len > chunk) {
 343                 btrfs_remove_free_space(block_group, start, chunk);
 344                 start += step;
 345                 if (len < step)
 346                         len = 0;
 347                 else
 348                         len -= step;
 349         }
 350 }
 351 #endif
 352
 353 /*
 354  * this is only called by cache_block_group, since we could have freed extents
 355  * we need to check the pinned_extents for any extents that can't be used yet
 356  * since their free space will be released as soon as the transaction commits.
 357  */
 358 u64 add_new_free_space(struct btrfs_block_group_cache *block_group,
 359                        u64 start, u64 end)
 360 {
 361         struct btrfs_fs_info *info = block_group->fs_info;
 362         u64 extent_start, extent_end, size, total_added = 0;
 363         int ret;
 364
 365         while (start < end) {
 366                 ret = find_first_extent_bit(info->pinned_extents, start,
 367                                             &extent_start, &extent_end,
 368                                             EXTENT_DIRTY | EXTENT_UPTODATE,
 369                                             NULL);
 370                 if (ret)
 371                         break;
 372
 373                 if (extent_start <= start) {
 374                         start = extent_end + 1;
 375                 } else if (extent_start > start && extent_start < end) {
 376                         size = extent_start - start;
 377                         total_added += size;
 378                         ret = btrfs_add_free_space(block_group, start,
 379                                                    size);
 380                         BUG_ON(ret); /* -ENOMEM or logic error */
 381                         start = extent_end + 1;
 382                 } else {
 383                         break;
 384                 }
 385         }
 386
 387         if (start < end) {
 388                 size = end - start;
 389                 total_added += size;
 390                 ret = btrfs_add_free_space(block_group, start, size);
 391                 BUG_ON(ret); /* -ENOMEM or logic error */
 392         }
 393
 394         return total_added;
 395 }
 396
 397 static int load_extent_tree_free(struct btrfs_caching_control *caching_ctl)
 398 {
 399         struct btrfs_block_group_cache *block_group = caching_ctl->block_group;
 400         struct btrfs_fs_info *fs_info = block_group->fs_info;
 401         struct btrfs_root *extent_root = fs_info->extent_root;
 402         struct btrfs_path *path;
 403         struct extent_buffer *leaf;
 404         struct btrfs_key key;
 405         u64 total_found = 0;
 406         u64 last = 0;
 407         u32 nritems;
 408         int ret;
 409         bool wakeup = true;
 410
 411         path = btrfs_alloc_path();
 412         if (!path)
 413                 return -ENOMEM;
 414
 415         last = max_t(u64, block_group->key.objectid, BTRFS_SUPER_INFO_OFFSET);
 416
 417 #ifdef CONFIG_BTRFS_DEBUG
 418         /*
 419          * If we're fragmenting we don't want to make anybody think we can
 420          * allocate from this block group until we've had a chance to fragment
 421          * the free space.
 422          */
 423         if (btrfs_should_fragment_free_space(block_group))
 424                 wakeup = false;
 425 #endif
 426         /*
 427          * We don't want to deadlock with somebody trying to allocate a new
 428          * extent for the extent root while also trying to search the extent
 429          * root to add free space.  So we skip locking and search the commit
 430          * root, since its read-only
 431          */
 432         path->skip_locking = 1;
 433         path->search_commit_root = 1;
 434         path->reada = READA_FORWARD;
 435
 436         key.objectid = last;
 437         key.offset = 0;
 438         key.type = BTRFS_EXTENT_ITEM_KEY;
 439
 440 next:
 441         ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
 442         if (ret < 0)
 443                 goto out;
 444
 445         leaf = path->nodes[0];
 446         nritems = btrfs_header_nritems(leaf);
 447
 448         while (1) {
 449                 if (btrfs_fs_closing(fs_info) > 1) {
 450                         last = (u64)-1;
 451                         break;
 452                 }
 453
 454                 if (path->slots[0] < nritems) {
 455                         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 456                 } else {
 457                         ret = find_next_key(path, 0, &key);
 458                         if (ret)
 459                                 break;
 460
 461                         if (need_resched() ||
 462                             rwsem_is_contended(&fs_info->commit_root_sem)) {
 463                                 if (wakeup)
 464                                         caching_ctl->progress = last;
 465                                 btrfs_release_path(path);
 466                                 up_read(&fs_info->commit_root_sem);
 467                                 mutex_unlock(&caching_ctl->mutex);
 468                                 cond_resched();
 469                                 mutex_lock(&caching_ctl->mutex);
 470                                 down_read(&fs_info->commit_root_sem);
 471                                 goto next;
 472                         }
 473
 474                         ret = btrfs_next_leaf(extent_root, path);
 475                         if (ret < 0)
 476                                 goto out;
 477                         if (ret)
 478                                 break;
 479                         leaf = path->nodes[0];
 480                         nritems = btrfs_header_nritems(leaf);
 481                         continue;
 482                 }
 483
 484                 if (key.objectid < last) {
 485                         key.objectid = last;
 486                         key.offset = 0;
 487                         key.type = BTRFS_EXTENT_ITEM_KEY;
 488
 489                         if (wakeup)
 490                                 caching_ctl->progress = last;
 491                         btrfs_release_path(path);
 492                         goto next;
 493                 }
 494
 495                 if (key.objectid < block_group->key.objectid) {
 496                         path->slots[0]++;
 497                         continue;
 498                 }
 499
 500                 if (key.objectid >= block_group->key.objectid +
 501                     block_group->key.offset)
 502                         break;
 503
 504                 if (key.type == BTRFS_EXTENT_ITEM_KEY ||
 505                     key.type == BTRFS_METADATA_ITEM_KEY) {
 506                         total_found += add_new_free_space(block_group, last,
 507                                                           key.objectid);
 508                         if (key.type == BTRFS_METADATA_ITEM_KEY)
 509                                 last = key.objectid +
 510                                         fs_info->nodesize;
 511                         else
 512                                 last = key.objectid + key.offset;
 513
 514                         if (total_found > CACHING_CTL_WAKE_UP) {
 515                                 total_found = 0;
 516                                 if (wakeup)
 517                                         wake_up(&caching_ctl->wait);
 518                         }
 519                 }
 520                 path->slots[0]++;
 521         }
 522         ret = 0;
 523
 524         total_found += add_new_free_space(block_group, last,
 525                                           block_group->key.objectid +
 526                                           block_group->key.offset);
 527         caching_ctl->progress = (u64)-1;
 528
 529 out:
 530         btrfs_free_path(path);
 531         return ret;
 532 }
 533
 534 static noinline void caching_thread(struct btrfs_work *work)
 535 {
 536         struct btrfs_block_group_cache *block_group;
 537         struct btrfs_fs_info *fs_info;
 538         struct btrfs_caching_control *caching_ctl;
 539         int ret;
 540
 541         caching_ctl = container_of(work, struct btrfs_caching_control, work);
 542         block_group = caching_ctl->block_group;
 543         fs_info = block_group->fs_info;
 544
 545         mutex_lock(&caching_ctl->mutex);
 546         down_read(&fs_info->commit_root_sem);
 547
 548         if (btrfs_fs_compat_ro(fs_info, FREE_SPACE_TREE))
 549                 ret = load_free_space_tree(caching_ctl);
 550         else
 551                 ret = load_extent_tree_free(caching_ctl);
 552
 553         spin_lock(&block_group->lock);
 554         block_group->caching_ctl = NULL;
 555         block_group->cached = ret ? BTRFS_CACHE_ERROR : BTRFS_CACHE_FINISHED;
 556         spin_unlock(&block_group->lock);
 557
 558 #ifdef CONFIG_BTRFS_DEBUG
 559         if (btrfs_should_fragment_free_space(block_group)) {
 560                 u64 bytes_used;
 561
 562                 spin_lock(&block_group->space_info->lock);
 563                 spin_lock(&block_group->lock);
 564                 bytes_used = block_group->key.offset -
 565                         btrfs_block_group_used(&block_group->item);
 566                 block_group->space_info->bytes_used += bytes_used >> 1;
 567                 spin_unlock(&block_group->lock);
 568                 spin_unlock(&block_group->space_info->lock);
 569                 fragment_free_space(block_group);
 570         }
 571 #endif
 572
 573         caching_ctl->progress = (u64)-1;
 574
 575         up_read(&fs_info->commit_root_sem);
 576         free_excluded_extents(block_group);
 577         mutex_unlock(&caching_ctl->mutex);
 578
 579         wake_up(&caching_ctl->wait);
 580
 581         put_caching_control(caching_ctl);
 582         btrfs_put_block_group(block_group);
 583 }
 584
 585 static int cache_block_group(struct btrfs_block_group_cache *cache,
 586                              int load_cache_only)
 587 {
 588         DEFINE_WAIT(wait);
 589         struct btrfs_fs_info *fs_info = cache->fs_info;
 590         struct btrfs_caching_control *caching_ctl;
 591         int ret = 0;
 592
 593         caching_ctl = kzalloc(sizeof(*caching_ctl), GFP_NOFS);
 594         if (!caching_ctl)
 595                 return -ENOMEM;
 596
 597         INIT_LIST_HEAD(&caching_ctl->list);
 598         mutex_init(&caching_ctl->mutex);
 599         init_waitqueue_head(&caching_ctl->wait);
 600         caching_ctl->block_group = cache;
 601         caching_ctl->progress = cache->key.objectid;
 602         refcount_set(&caching_ctl->count, 1);
 603         btrfs_init_work(&caching_ctl->work, btrfs_cache_helper,
 604                         caching_thread, NULL, NULL);
 605
 606         spin_lock(&cache->lock);
 607         /*
 608          * This should be a rare occasion, but this could happen I think in the
 609          * case where one thread starts to load the space cache info, and then
 610          * some other thread starts a transaction commit which tries to do an
 611          * allocation while the other thread is still loading the space cache
 612          * info.  The previous loop should have kept us from choosing this block
 613          * group, but if we've moved to the state where we will wait on caching
 614          * block groups we need to first check if we're doing a fast load here,
 615          * so we can wait for it to finish, otherwise we could end up allocating
 616          * from a block group who's cache gets evicted for one reason or
 617          * another.
 618          */
 619         while (cache->cached == BTRFS_CACHE_FAST) {
 620                 struct btrfs_caching_control *ctl;
 621
 622                 ctl = cache->caching_ctl;
 623                 refcount_inc(&ctl->count);
 624                 prepare_to_wait(&ctl->wait, &wait, TASK_UNINTERRUPTIBLE);
 625                 spin_unlock(&cache->lock);
 626
 627                 schedule();
 628
 629                 finish_wait(&ctl->wait, &wait);
 630                 put_caching_control(ctl);
 631                 spin_lock(&cache->lock);
 632         }
 633
 634         if (cache->cached != BTRFS_CACHE_NO) {
 635                 spin_unlock(&cache->lock);
 636                 kfree(caching_ctl);
 637                 return 0;
 638         }
 639         WARN_ON(cache->caching_ctl);
 640         cache->caching_ctl = caching_ctl;
 641         cache->cached = BTRFS_CACHE_FAST;
 642         spin_unlock(&cache->lock);
 643
 644         if (btrfs_test_opt(fs_info, SPACE_CACHE)) {
 645                 mutex_lock(&caching_ctl->mutex);
 646                 ret = load_free_space_cache(fs_info, cache);
 647
 648                 spin_lock(&cache->lock);
 649                 if (ret == 1) {
 650                         cache->caching_ctl = NULL;
 651                         cache->cached = BTRFS_CACHE_FINISHED;
 652                         cache->last_byte_to_unpin = (u64)-1;
 653                         caching_ctl->progress = (u64)-1;
 654                 } else {
 655                         if (load_cache_only) {
 656                                 cache->caching_ctl = NULL;
 657                                 cache->cached = BTRFS_CACHE_NO;
 658                         } else {
 659                                 cache->cached = BTRFS_CACHE_STARTED;
 660                                 cache->has_caching_ctl = 1;
 661                         }
 662                 }
 663                 spin_unlock(&cache->lock);
 664 #ifdef CONFIG_BTRFS_DEBUG
 665                 if (ret == 1 &&
 666                     btrfs_should_fragment_free_space(cache)) {
 667                         u64 bytes_used;
 668
 669                         spin_lock(&cache->space_info->lock);
 670                         spin_lock(&cache->lock);
 671                         bytes_used = cache->key.offset -
 672                                 btrfs_block_group_used(&cache->item);
 673                         cache->space_info->bytes_used += bytes_used >> 1;
 674                         spin_unlock(&cache->lock);
 675                         spin_unlock(&cache->space_info->lock);
 676                         fragment_free_space(cache);
 677                 }
 678 #endif
 679                 mutex_unlock(&caching_ctl->mutex);
 680
 681                 wake_up(&caching_ctl->wait);
 682                 if (ret == 1) {
 683                         put_caching_control(caching_ctl);
 684                         free_excluded_extents(cache);
 685                         return 0;
 686                 }
 687         } else {
 688                 /*
 689                  * We're either using the free space tree or no caching at all.
 690                  * Set cached to the appropriate value and wakeup any waiters.
 691                  */
 692                 spin_lock(&cache->lock);
 693                 if (load_cache_only) {
 694                         cache->caching_ctl = NULL;
 695                         cache->cached = BTRFS_CACHE_NO;
 696                 } else {
 697                         cache->cached = BTRFS_CACHE_STARTED;
 698                         cache->has_caching_ctl = 1;
 699                 }
 700                 spin_unlock(&cache->lock);
 701                 wake_up(&caching_ctl->wait);
 702         }
 703
 704         if (load_cache_only) {
 705                 put_caching_control(caching_ctl);
 706                 return 0;
 707         }
 708
 709         down_write(&fs_info->commit_root_sem);
 710         refcount_inc(&caching_ctl->count);
 711         list_add_tail(&caching_ctl->list, &fs_info->caching_block_groups);
 712         up_write(&fs_info->commit_root_sem);
 713
 714         btrfs_get_block_group(cache);
 715
 716         btrfs_queue_work(fs_info->caching_workers, &caching_ctl->work);
 717
 718         return ret;
 719 }
 720
 721 /*
 722  * return the block group that starts at or after bytenr
 723  */
 724 static struct btrfs_block_group_cache *
 725 btrfs_lookup_first_block_group(struct btrfs_fs_info *info, u64 bytenr)
 726 {
 727         return block_group_cache_tree_search(info, bytenr, 0);
 728 }
 729
 730 /*
 731  * return the block group that contains the given bytenr
 732  */
 733 struct btrfs_block_group_cache *btrfs_lookup_block_group(
 734                                                  struct btrfs_fs_info *info,
 735                                                  u64 bytenr)
 736 {
 737         return block_group_cache_tree_search(info, bytenr, 1);
 738 }
 739
 740 static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
 741                                                   u64 flags)
 742 {
 743         struct list_head *head = &info->space_info;
 744         struct btrfs_space_info *found;
 745
 746         flags &= BTRFS_BLOCK_GROUP_TYPE_MASK;
 747
 748         rcu_read_lock();
 749         list_for_each_entry_rcu(found, head, list) {
 750                 if (found->flags & flags) {
 751                         rcu_read_unlock();
 752                         return found;
 753                 }
 754         }
 755         rcu_read_unlock();
 756         return NULL;
 757 }
 758
 759 static void add_pinned_bytes(struct btrfs_fs_info *fs_info, s64 num_bytes,
 760                              bool metadata, u64 root_objectid)
 761 {
 762         struct btrfs_space_info *space_info;
 763         u64 flags;
 764
 765         if (metadata) {
 766                 if (root_objectid == BTRFS_CHUNK_TREE_OBJECTID)
 767                         flags = BTRFS_BLOCK_GROUP_SYSTEM;
 768                 else
 769                         flags = BTRFS_BLOCK_GROUP_METADATA;
 770         } else {
 771                 flags = BTRFS_BLOCK_GROUP_DATA;
 772         }
 773
 774         space_info = __find_space_info(fs_info, flags);
 775         ASSERT(space_info);
 776         percpu_counter_add_batch(&space_info->total_bytes_pinned, num_bytes,
 777                     BTRFS_TOTAL_BYTES_PINNED_BATCH);
 778 }
 779
 780 /*
 781  * after adding space to the filesystem, we need to clear the full flags
 782  * on all the space infos.
 783  */
 784 void btrfs_clear_space_info_full(struct btrfs_fs_info *info)
 785 {
 786         struct list_head *head = &info->space_info;
 787         struct btrfs_space_info *found;
 788
 789         rcu_read_lock();
 790         list_for_each_entry_rcu(found, head, list)
 791                 found->full = 0;
 792         rcu_read_unlock();
 793 }
 794
 795 /* simple helper to search for an existing data extent at a given offset */
 796 int btrfs_lookup_data_extent(struct btrfs_fs_info *fs_info, u64 start, u64 len)
 797 {
 798         int ret;
 799         struct btrfs_key key;
 800         struct btrfs_path *path;
 801
 802         path = btrfs_alloc_path();
 803         if (!path)
 804                 return -ENOMEM;
 805
 806         key.objectid = start;
 807         key.offset = len;
 808         key.type = BTRFS_EXTENT_ITEM_KEY;
 809         ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, path, 0, 0);
 810         btrfs_free_path(path);
 811         return ret;
 812 }
 813
 814 /*
 815  * helper function to lookup reference count and flags of a tree block.
 816  *
 817  * the head node for delayed ref is used to store the sum of all the
 818  * reference count modifications queued up in the rbtree. the head
 819  * node may also store the extent flags to set. This way you can check
 820  * to see what the reference count and extent flags would be if all of
 821  * the delayed refs are not processed.
 822  */
 823 int btrfs_lookup_extent_info(struct btrfs_trans_handle *trans,
 824                              struct btrfs_fs_info *fs_info, u64 bytenr,
 825                              u64 offset, int metadata, u64 *refs, u64 *flags)
 826 {
 827         struct btrfs_delayed_ref_head *head;
 828         struct btrfs_delayed_ref_root *delayed_refs;
 829         struct btrfs_path *path;
 830         struct btrfs_extent_item *ei;
 831         struct extent_buffer *leaf;
 832         struct btrfs_key key;
 833         u32 item_size;
 834         u64 num_refs;
 835         u64 extent_flags;
 836         int ret;
 837
 838         /*
 839          * If we don't have skinny metadata, don't bother doing anything
 840          * different
 841          */
 842         if (metadata && !btrfs_fs_incompat(fs_info, SKINNY_METADATA)) {
 843                 offset = fs_info->nodesize;
 844                 metadata = 0;
 845         }
 846
 847         path = btrfs_alloc_path();
 848         if (!path)
 849                 return -ENOMEM;
 850
 851         if (!trans) {
 852                 path->skip_locking = 1;
 853                 path->search_commit_root = 1;
 854         }
 855
 856 search_again:
 857         key.objectid = bytenr;
 858         key.offset = offset;
 859         if (metadata)
 860                 key.type = BTRFS_METADATA_ITEM_KEY;
 861         else
 862                 key.type = BTRFS_EXTENT_ITEM_KEY;
 863
 864         ret = btrfs_search_slot(trans, fs_info->extent_root, &key, path, 0, 0);
 865         if (ret < 0)
 866                 goto out_free;
 867
 868         if (ret > 0 && metadata && key.type == BTRFS_METADATA_ITEM_KEY) {
 869                 if (path->slots[0]) {
 870                         path->slots[0]--;
 871                         btrfs_item_key_to_cpu(path->nodes[0], &key,
 872                                               path->slots[0]);
 873                         if (key.objectid == bytenr &&
 874                             key.type == BTRFS_EXTENT_ITEM_KEY &&
 875                             key.offset == fs_info->nodesize)
 876                                 ret = 0;
 877                 }
 878         }
 879
 880         if (ret == 0) {
 881                 leaf = path->nodes[0];
 882                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
 883                 if (item_size >= sizeof(*ei)) {
 884                         ei = btrfs_item_ptr(leaf, path->slots[0],
 885                                             struct btrfs_extent_item);
 886                         num_refs = btrfs_extent_refs(leaf, ei);
 887                         extent_flags = btrfs_extent_flags(leaf, ei);
 888                 } else {
 889                         ret = -EINVAL;
 890                         btrfs_print_v0_err(fs_info);
 891                         if (trans)
 892                                 btrfs_abort_transaction(trans, ret);
 893                         else
 894                                 btrfs_handle_fs_error(fs_info, ret, NULL);
 895
 896                         goto out_free;
 897                 }
 898
 899                 BUG_ON(num_refs == 0);
 900         } else {
 901                 num_refs = 0;
 902                 extent_flags = 0;
 903                 ret = 0;
 904         }
 905
 906         if (!trans)
 907                 goto out;
 908
 909         delayed_refs = &trans->transaction->delayed_refs;
 910         spin_lock(&delayed_refs->lock);
 911         head = btrfs_find_delayed_ref_head(delayed_refs, bytenr);
 912         if (head) {
 913                 if (!mutex_trylock(&head->mutex)) {
 914                         refcount_inc(&head->refs);
 915                         spin_unlock(&delayed_refs->lock);
 916
 917                         btrfs_release_path(path);
 918
 919                         /*
 920                          * Mutex was contended, block until it's released and try
 921                          * again
 922                          */
 923                         mutex_lock(&head->mutex);
 924                         mutex_unlock(&head->mutex);
 925                         btrfs_put_delayed_ref_head(head);
 926                         goto search_again;
 927                 }
 928                 spin_lock(&head->lock);
 929                 if (head->extent_op && head->extent_op->update_flags)
 930                         extent_flags |= head->extent_op->flags_to_set;
 931                 else
 932                         BUG_ON(num_refs == 0);
 933
 934                 num_refs += head->ref_mod;
 935                 spin_unlock(&head->lock);
 936                 mutex_unlock(&head->mutex);
 937         }
 938         spin_unlock(&delayed_refs->lock);
 939 out:
 940         WARN_ON(num_refs == 0);
 941         if (refs)
 942                 *refs = num_refs;
 943         if (flags)
 944                 *flags = extent_flags;
 945 out_free:
 946         btrfs_free_path(path);
 947         return ret;
 948 }
 949
 950 /*
 951  * Back reference rules.  Back refs have three main goals:
 952  *
 953  * 1) differentiate between all holders of references to an extent so that
 954  *    when a reference is dropped we can make sure it was a valid reference
 955  *    before freeing the extent.
 956  *
 957  * 2) Provide enough information to quickly find the holders of an extent
 958  *    if we notice a given block is corrupted or bad.
 959  *
 960  * 3) Make it easy to migrate blocks for FS shrinking or storage pool
 961  *    maintenance.  This is actually the same as #2, but with a slightly
 962  *    different use case.
 963  *
 964  * There are two kinds of back refs. The implicit back refs is optimized
 965  * for pointers in non-shared tree blocks. For a given pointer in a block,
 966  * back refs of this kind provide information about the block's owner tree
 967  * and the pointer's key. These information allow us to find the block by
 968  * b-tree searching. The full back refs is for pointers in tree blocks not
 969  * referenced by their owner trees. The location of tree block is recorded
 970  * in the back refs. Actually the full back refs is generic, and can be
 971  * used in all cases the implicit back refs is used. The major shortcoming
 972  * of the full back refs is its overhead. Every time a tree block gets
 973  * COWed, we have to update back refs entry for all pointers in it.
 974  *
 975  * For a newly allocated tree block, we use implicit back refs for
 976  * pointers in it. This means most tree related operations only involve
 977  * implicit back refs. For a tree block created in old transaction, the
 978  * only way to drop a reference to it is COW it. So we can detect the
 979  * event that tree block loses its owner tree's reference and do the
 980  * back refs conversion.
 981  *
 982  * When a tree block is COWed through a tree, there are four cases:
 983  *
 984  * The reference count of the block is one and the tree is the block's
 985  * owner tree. Nothing to do in this case.
 986  *
 987  * The reference count of the block is one and the tree is not the
 988  * block's owner tree. In this case, full back refs is used for pointers
 989  * in the block. Remove these full back refs, add implicit back refs for
 990  * every pointers in the new block.
 991  *
 992  * The reference count of the block is greater than one and the tree is
 993  * the block's owner tree. In this case, implicit back refs is used for
 994  * pointers in the block. Add full back refs for every pointers in the
 995  * block, increase lower level extents' reference counts. The original
 996  * implicit back refs are entailed to the new block.
 997  *
 998  * The reference count of the block is greater than one and the tree is
 999  * not the block's owner tree. Add implicit back refs for every pointer in
1000  * the new block, increase lower level extents' reference count.
1001  *
1002  * Back Reference Key composing:
1003  *
1004  * The key objectid corresponds to the first byte in the extent,
1005  * The key type is used to differentiate between types of back refs.
1006  * There are different meanings of the key offset for different types
1007  * of back refs.
1008  *
1009  * File extents can be referenced by:
1010  *
1011  * - multiple snapshots, subvolumes, or different generations in one subvol
1012  * - different files inside a single subvolume
1013  * - different offsets inside a file (bookend extents in file.c)
1014  *
1015  * The extent ref structure for the implicit back refs has fields for:
1016  *
1017  * - Objectid of the subvolume root
1018  * - objectid of the file holding the reference
1019  * - original offset in the file
1020  * - how many bookend extents
1021  *
1022  * The key offset for the implicit back refs is hash of the first
1023  * three fields.
1024  *
1025  * The extent ref structure for the full back refs has field for:
1026  *
1027  * - number of pointers in the tree leaf
1028  *
1029  * The key offset for the implicit back refs is the first byte of
1030  * the tree leaf
1031  *
1032  * When a file extent is allocated, The implicit back refs is used.
1033  * the fields are filled in:
1034  *
1035  *     (root_key.objectid, inode objectid, offset in file, 1)
1036  *
1037  * When a file extent is removed file truncation, we find the
1038  * corresponding implicit back refs and check the following fields:
1039  *
1040  *     (btrfs_header_owner(leaf), inode objectid, offset in file)
1041  *
1042  * Btree extents can be referenced by:
1043  *
1044  * - Different subvolumes
1045  *
1046  * Both the implicit back refs and the full back refs for tree blocks
1047  * only consist of key. The key offset for the implicit back refs is
1048  * objectid of block's owner tree. The key offset for the full back refs
1049  * is the first byte of parent block.
1050  *
1051  * When implicit back refs is used, information about the lowest key and
1052  * level of the tree block are required. These information are stored in
1053  * tree block info structure.
1054  */
1055
1056 /*
1057  * is_data == BTRFS_REF_TYPE_BLOCK, tree block type is required,
1058  * is_data == BTRFS_REF_TYPE_DATA, data type is requiried,
1059  * is_data == BTRFS_REF_TYPE_ANY, either type is OK.
1060  */
1061 int btrfs_get_extent_inline_ref_type(const struct extent_buffer *eb,
1062                                      struct btrfs_extent_inline_ref *iref,
1063                                      enum btrfs_inline_ref_type is_data)
1064 {
1065         int type = btrfs_extent_inline_ref_type(eb, iref);
1066         u64 offset = btrfs_extent_inline_ref_offset(eb, iref);
1067
1068         if (type == BTRFS_TREE_BLOCK_REF_KEY ||
1069             type == BTRFS_SHARED_BLOCK_REF_KEY ||
1070             type == BTRFS_SHARED_DATA_REF_KEY ||
1071             type == BTRFS_EXTENT_DATA_REF_KEY) {
1072                 if (is_data == BTRFS_REF_TYPE_BLOCK) {
1073                         if (type == BTRFS_TREE_BLOCK_REF_KEY)
1074                                 return type;
1075                         if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
1076                                 ASSERT(eb->fs_info);
1077                                 /*
1078                                  * Every shared one has parent tree
1079                                  * block, which must be aligned to
1080                                  * nodesize.
1081                                  */
1082                                 if (offset &&
1083                                     IS_ALIGNED(offset, eb->fs_info->nodesize))
1084                                         return type;
1085                         }
1086                 } else if (is_data == BTRFS_REF_TYPE_DATA) {
1087                         if (type == BTRFS_EXTENT_DATA_REF_KEY)
1088                                 return type;
1089                         if (type == BTRFS_SHARED_DATA_REF_KEY) {
1090                                 ASSERT(eb->fs_info);
1091                                 /*
1092                                  * Every shared one has parent tree
1093                                  * block, which must be aligned to
1094                                  * nodesize.
1095                                  */
1096                                 if (offset &&
1097                                     IS_ALIGNED(offset, eb->fs_info->nodesize))
1098                                         return type;
1099                         }
1100                 } else {
1101                         ASSERT(is_data == BTRFS_REF_TYPE_ANY);
1102                         return type;
1103                 }
1104         }
1105
1106         btrfs_print_leaf((struct extent_buffer *)eb);
1107         btrfs_err(eb->fs_info, "eb %llu invalid extent inline ref type %d",
1108                   eb->start, type);
1109         WARN_ON(1);
1110
1111         return BTRFS_REF_TYPE_INVALID;
1112 }
1113
1114 static u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset)
1115 {
1116         u32 high_crc = ~(u32)0;
1117         u32 low_crc = ~(u32)0;
1118         __le64 lenum;
1119
1120         lenum = cpu_to_le64(root_objectid);
1121         high_crc = crc32c(high_crc, &lenum, sizeof(lenum));
1122         lenum = cpu_to_le64(owner);
1123         low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
1124         lenum = cpu_to_le64(offset);
1125         low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
1126
1127         return ((u64)high_crc << 31) ^ (u64)low_crc;
1128 }
1129
1130 static u64 hash_extent_data_ref_item(struct extent_buffer *leaf,
1131                                      struct btrfs_extent_data_ref *ref)
1132 {
1133         return hash_extent_data_ref(btrfs_extent_data_ref_root(leaf, ref),
1134                                     btrfs_extent_data_ref_objectid(leaf, ref),
1135                                     btrfs_extent_data_ref_offset(leaf, ref));
1136 }
1137
1138 static int match_extent_data_ref(struct extent_buffer *leaf,
1139                                  struct btrfs_extent_data_ref *ref,
1140                                  u64 root_objectid, u64 owner, u64 offset)
1141 {
1142         if (btrfs_extent_data_ref_root(leaf, ref) != root_objectid ||
1143             btrfs_extent_data_ref_objectid(leaf, ref) != owner ||
1144             btrfs_extent_data_ref_offset(leaf, ref) != offset)
1145                 return 0;
1146         return 1;
1147 }
1148
1149 static noinline int lookup_extent_data_ref(struct btrfs_trans_handle *trans,
1150                                            struct btrfs_path *path,
1151                                            u64 bytenr, u64 parent,
1152                                            u64 root_objectid,
1153                                            u64 owner, u64 offset)
1154 {
1155         struct btrfs_root *root = trans->fs_info->extent_root;
1156         struct btrfs_key key;
1157         struct btrfs_extent_data_ref *ref;
1158         struct extent_buffer *leaf;
1159         u32 nritems;
1160         int ret;
1161         int recow;
1162         int err = -ENOENT;
1163
1164         key.objectid = bytenr;
1165         if (parent) {
1166                 key.type = BTRFS_SHARED_DATA_REF_KEY;
1167                 key.offset = parent;
1168         } else {
1169                 key.type = BTRFS_EXTENT_DATA_REF_KEY;
1170                 key.offset = hash_extent_data_ref(root_objectid,
1171                                                   owner, offset);
1172         }
1173 again:
1174         recow = 0;
1175         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1176         if (ret < 0) {
1177                 err = ret;
1178                 goto fail;
1179         }
1180
1181         if (parent) {
1182                 if (!ret)
1183                         return 0;
1184                 goto fail;
1185         }
1186
1187         leaf = path->nodes[0];
1188         nritems = btrfs_header_nritems(leaf);
1189         while (1) {
1190                 if (path->slots[0] >= nritems) {
1191                         ret = btrfs_next_leaf(root, path);
1192                         if (ret < 0)
1193                                 err = ret;
1194                         if (ret)
1195                                 goto fail;
1196
1197                         leaf = path->nodes[0];
1198                         nritems = btrfs_header_nritems(leaf);
1199                         recow = 1;
1200                 }
1201
1202                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
1203                 if (key.objectid != bytenr ||
1204                     key.type != BTRFS_EXTENT_DATA_REF_KEY)
1205                         goto fail;
1206
1207                 ref = btrfs_item_ptr(leaf, path->slots[0],
1208                                      struct btrfs_extent_data_ref);
1209
1210                 if (match_extent_data_ref(leaf, ref, root_objectid,
1211                                           owner, offset)) {
1212                         if (recow) {
1213                                 btrfs_release_path(path);
1214                                 goto again;
1215                         }
1216                         err = 0;
1217                         break;
1218                 }
1219                 path->slots[0]++;
1220         }
1221 fail:
1222         return err;
1223 }
1224
1225 static noinline int insert_extent_data_ref(struct btrfs_trans_handle *trans,
1226                                            struct btrfs_path *path,
1227                                            u64 bytenr, u64 parent,
1228                                            u64 root_objectid, u64 owner,
1229                                            u64 offset, int refs_to_add)
1230 {
1231         struct btrfs_root *root = trans->fs_info->extent_root;
1232         struct btrfs_key key;
1233         struct extent_buffer *leaf;
1234         u32 size;
1235         u32 num_refs;
1236         int ret;
1237
1238         key.objectid = bytenr;
1239         if (parent) {
1240                 key.type = BTRFS_SHARED_DATA_REF_KEY;
1241                 key.offset = parent;
1242                 size = sizeof(struct btrfs_shared_data_ref);
1243         } else {
1244                 key.type = BTRFS_EXTENT_DATA_REF_KEY;
1245                 key.offset = hash_extent_data_ref(root_objectid,
1246                                                   owner, offset);
1247                 size = sizeof(struct btrfs_extent_data_ref);
1248         }
1249
1250         ret = btrfs_insert_empty_item(trans, root, path, &key, size);
1251         if (ret && ret != -EEXIST)
1252                 goto fail;
1253
1254         leaf = path->nodes[0];
1255         if (parent) {
1256                 struct btrfs_shared_data_ref *ref;
1257                 ref = btrfs_item_ptr(leaf, path->slots[0],
1258                                      struct btrfs_shared_data_ref);
1259                 if (ret == 0) {
1260                         btrfs_set_shared_data_ref_count(leaf, ref, refs_to_add);
1261                 } else {
1262                         num_refs = btrfs_shared_data_ref_count(leaf, ref);
1263                         num_refs += refs_to_add;
1264                         btrfs_set_shared_data_ref_count(leaf, ref, num_refs);
1265                 }
1266         } else {
1267                 struct btrfs_extent_data_ref *ref;
1268                 while (ret == -EEXIST) {
1269                         ref = btrfs_item_ptr(leaf, path->slots[0],
1270                                              struct btrfs_extent_data_ref);
1271                         if (match_extent_data_ref(leaf, ref, root_objectid,
1272                                                   owner, offset))
1273                                 break;
1274                         btrfs_release_path(path);
1275                         key.offset++;
1276                         ret = btrfs_insert_empty_item(trans, root, path, &key,
1277                                                       size);
1278                         if (ret && ret != -EEXIST)
1279                                 goto fail;
1280
1281                         leaf = path->nodes[0];
1282                 }
1283                 ref = btrfs_item_ptr(leaf, path->slots[0],
1284                                      struct btrfs_extent_data_ref);
1285                 if (ret == 0) {
1286                         btrfs_set_extent_data_ref_root(leaf, ref,
1287                                                        root_objectid);
1288                         btrfs_set_extent_data_ref_objectid(leaf, ref, owner);
1289                         btrfs_set_extent_data_ref_offset(leaf, ref, offset);
1290                         btrfs_set_extent_data_ref_count(leaf, ref, refs_to_add);
1291                 } else {
1292                         num_refs = btrfs_extent_data_ref_count(leaf, ref);
1293                         num_refs += refs_to_add;
1294                         btrfs_set_extent_data_ref_count(leaf, ref, num_refs);
1295                 }
1296         }
1297         btrfs_mark_buffer_dirty(leaf);
1298         ret = 0;
1299 fail:
1300         btrfs_release_path(path);
1301         return ret;
1302 }
1303
1304 static noinline int remove_extent_data_ref(struct btrfs_trans_handle *trans,
1305                                            struct btrfs_path *path,
1306                                            int refs_to_drop, int *last_ref)
1307 {
1308         struct btrfs_key key;
1309         struct btrfs_extent_data_ref *ref1 = NULL;
1310         struct btrfs_shared_data_ref *ref2 = NULL;
1311         struct extent_buffer *leaf;
1312         u32 num_refs = 0;
1313         int ret = 0;
1314
1315         leaf = path->nodes[0];
1316         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
1317
1318         if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
1319                 ref1 = btrfs_item_ptr(leaf, path->slots[0],
1320                                       struct btrfs_extent_data_ref);
1321                 num_refs = btrfs_extent_data_ref_count(leaf, ref1);
1322         } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
1323                 ref2 = btrfs_item_ptr(leaf, path->slots[0],
1324                                       struct btrfs_shared_data_ref);
1325                 num_refs = btrfs_shared_data_ref_count(leaf, ref2);
1326         } else if (unlikely(key.type == BTRFS_EXTENT_REF_V0_KEY)) {
1327                 btrfs_print_v0_err(trans->fs_info);
1328                 btrfs_abort_transaction(trans, -EINVAL);
1329                 return -EINVAL;
1330         } else {
1331                 BUG();
1332         }
1333
1334         BUG_ON(num_refs < refs_to_drop);
1335         num_refs -= refs_to_drop;
1336
1337         if (num_refs == 0) {
1338                 ret = btrfs_del_item(trans, trans->fs_info->extent_root, path);
1339                 *last_ref = 1;
1340         } else {
1341                 if (key.type == BTRFS_EXTENT_DATA_REF_KEY)
1342                         btrfs_set_extent_data_ref_count(leaf, ref1, num_refs);
1343                 else if (key.type == BTRFS_SHARED_DATA_REF_KEY)
1344                         btrfs_set_shared_data_ref_count(leaf, ref2, num_refs);
1345                 btrfs_mark_buffer_dirty(leaf);
1346         }
1347         return ret;
1348 }
1349
1350 static noinline u32 extent_data_ref_count(struct btrfs_path *path,
1351                                           struct btrfs_extent_inline_ref *iref)
1352 {
1353         struct btrfs_key key;
1354         struct extent_buffer *leaf;
1355         struct btrfs_extent_data_ref *ref1;
1356         struct btrfs_shared_data_ref *ref2;
1357         u32 num_refs = 0;
1358         int type;
1359
1360         leaf = path->nodes[0];
1361         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
1362
1363         BUG_ON(key.type == BTRFS_EXTENT_REF_V0_KEY);
1364         if (iref) {
1365                 /*
1366                  * If type is invalid, we should have bailed out earlier than
1367                  * this call.
1368                  */
1369                 type = btrfs_get_extent_inline_ref_type(leaf, iref, BTRFS_REF_TYPE_DATA);
1370                 ASSERT(type != BTRFS_REF_TYPE_INVALID);
1371                 if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1372                         ref1 = (struct btrfs_extent_data_ref *)(&iref->offset);
1373                         num_refs = btrfs_extent_data_ref_count(leaf, ref1);
1374                 } else {
1375                         ref2 = (struct btrfs_shared_data_ref *)(iref + 1);
1376                         num_refs = btrfs_shared_data_ref_count(leaf, ref2);
1377                 }
1378         } else if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
1379                 ref1 = btrfs_item_ptr(leaf, path->slots[0],
1380                                       struct btrfs_extent_data_ref);
1381                 num_refs = btrfs_extent_data_ref_count(leaf, ref1);
1382         } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
1383                 ref2 = btrfs_item_ptr(leaf, path->slots[0],
1384                                       struct btrfs_shared_data_ref);
1385                 num_refs = btrfs_shared_data_ref_count(leaf, ref2);
1386         } else {
1387                 WARN_ON(1);
1388         }
1389         return num_refs;
1390 }
1391
1392 static noinline int lookup_tree_block_ref(struct btrfs_trans_handle *trans,
1393                                           struct btrfs_path *path,
1394                                           u64 bytenr, u64 parent,
1395                                           u64 root_objectid)
1396 {
1397         struct btrfs_root *root = trans->fs_info->extent_root;
1398         struct btrfs_key key;
1399         int ret;
1400
1401         key.objectid = bytenr;
1402         if (parent) {
1403                 key.type = BTRFS_SHARED_BLOCK_REF_KEY;
1404                 key.offset = parent;
1405         } else {
1406                 key.type = BTRFS_TREE_BLOCK_REF_KEY;
1407                 key.offset = root_objectid;
1408         }
1409
1410         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
1411         if (ret > 0)
1412                 ret = -ENOENT;
1413         return ret;
1414 }
1415
1416 static noinline int insert_tree_block_ref(struct btrfs_trans_handle *trans,
1417                                           struct btrfs_path *path,
1418                                           u64 bytenr, u64 parent,
1419                                           u64 root_objectid)
1420 {
1421         struct btrfs_key key;
1422         int ret;
1423
1424         key.objectid = bytenr;
1425         if (parent) {
1426                 key.type = BTRFS_SHARED_BLOCK_REF_KEY;
1427                 key.offset = parent;
1428         } else {
1429                 key.type = BTRFS_TREE_BLOCK_REF_KEY;
1430                 key.offset = root_objectid;
1431         }
1432
1433         ret = btrfs_insert_empty_item(trans, trans->fs_info->extent_root,
1434                                       path, &key, 0);
1435         btrfs_release_path(path);
1436         return ret;
1437 }
1438
1439 static inline int extent_ref_type(u64 parent, u64 owner)
1440 {
1441         int type;
1442         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1443                 if (parent > 0)
1444                         type = BTRFS_SHARED_BLOCK_REF_KEY;
1445                 else
1446                         type = BTRFS_TREE_BLOCK_REF_KEY;
1447         } else {
1448                 if (parent > 0)
1449                         type = BTRFS_SHARED_DATA_REF_KEY;
1450                 else
1451                         type = BTRFS_EXTENT_DATA_REF_KEY;
1452         }
1453         return type;
1454 }
1455
1456 static int find_next_key(struct btrfs_path *path, int level,
1457                          struct btrfs_key *key)
1458
1459 {
1460         for (; level < BTRFS_MAX_LEVEL; level++) {
1461                 if (!path->nodes[level])
1462                         break;
1463                 if (path->slots[level] + 1 >=
1464                     btrfs_header_nritems(path->nodes[level]))
1465                         continue;
1466                 if (level == 0)
1467                         btrfs_item_key_to_cpu(path->nodes[level], key,
1468                                               path->slots[level] + 1);
1469                 else
1470                         btrfs_node_key_to_cpu(path->nodes[level], key,
1471                                               path->slots[level] + 1);
1472                 return 0;
1473         }
1474         return 1;
1475 }
1476
1477 /*
1478  * look for inline back ref. if back ref is found, *ref_ret is set
1479  * to the address of inline back ref, and 0 is returned.
1480  *
1481  * if back ref isn't found, *ref_ret is set to the address where it
1482  * should be inserted, and -ENOENT is returned.
1483  *
1484  * if insert is true and there are too many inline back refs, the path
1485  * points to the extent item, and -EAGAIN is returned.
1486  *
1487  * NOTE: inline back refs are ordered in the same way that back ref
1488  *       items in the tree are ordered.
1489  */
1490 static noinline_for_stack
1491 int lookup_inline_extent_backref(struct btrfs_trans_handle *trans,
1492                                  struct btrfs_path *path,
1493                                  struct btrfs_extent_inline_ref **ref_ret,
1494                                  u64 bytenr, u64 num_bytes,
1495                                  u64 parent, u64 root_objectid,
1496                                  u64 owner, u64 offset, int insert)
1497 {
1498         struct btrfs_fs_info *fs_info = trans->fs_info;
1499         struct btrfs_root *root = fs_info->extent_root;
1500         struct btrfs_key key;
1501         struct extent_buffer *leaf;
1502         struct btrfs_extent_item *ei;
1503         struct btrfs_extent_inline_ref *iref;
1504         u64 flags;
1505         u64 item_size;
1506         unsigned long ptr;
1507         unsigned long end;
1508         int extra_size;
1509         int type;
1510         int want;
1511         int ret;
1512         int err = 0;
1513         bool skinny_metadata = btrfs_fs_incompat(fs_info, SKINNY_METADATA);
1514         int needed;
1515
1516         key.objectid = bytenr;
1517         key.type = BTRFS_EXTENT_ITEM_KEY;
1518         key.offset = num_bytes;
1519
1520         want = extent_ref_type(parent, owner);
1521         if (insert) {
1522                 extra_size = btrfs_extent_inline_ref_size(want);
1523                 path->keep_locks = 1;
1524         } else
1525                 extra_size = -1;
1526
1527         /*
1528          * Owner is our level, so we can just add one to get the level for the
1529          * block we are interested in.
1530          */
1531         if (skinny_metadata && owner < BTRFS_FIRST_FREE_OBJECTID) {
1532                 key.type = BTRFS_METADATA_ITEM_KEY;
1533                 key.offset = owner;
1534         }
1535
1536 again:
1537         ret = btrfs_search_slot(trans, root, &key, path, extra_size, 1);
1538         if (ret < 0) {
1539                 err = ret;
1540                 goto out;
1541         }
1542
1543         /*
1544          * We may be a newly converted file system which still has the old fat
1545          * extent entries for metadata, so try and see if we have one of those.
1546          */
1547         if (ret > 0 && skinny_metadata) {
1548                 skinny_metadata = false;
1549                 if (path->slots[0]) {
1550                         path->slots[0]--;
1551                         btrfs_item_key_to_cpu(path->nodes[0], &key,
1552                                               path->slots[0]);
1553                         if (key.objectid == bytenr &&
1554                             key.type == BTRFS_EXTENT_ITEM_KEY &&
1555                             key.offset == num_bytes)
1556                                 ret = 0;
1557                 }
1558                 if (ret) {
1559                         key.objectid = bytenr;
1560                         key.type = BTRFS_EXTENT_ITEM_KEY;
1561                         key.offset = num_bytes;
1562                         btrfs_release_path(path);
1563                         goto again;
1564                 }
1565         }
1566
1567         if (ret && !insert) {
1568                 err = -ENOENT;
1569                 goto out;
1570         } else if (WARN_ON(ret)) {
1571                 err = -EIO;
1572                 goto out;
1573         }
1574
1575         leaf = path->nodes[0];
1576         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1577         if (unlikely(item_size < sizeof(*ei))) {
1578                 err = -EINVAL;
1579                 btrfs_print_v0_err(fs_info);
1580                 btrfs_abort_transaction(trans, err);
1581                 goto out;
1582         }
1583
1584         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1585         flags = btrfs_extent_flags(leaf, ei);
1586
1587         ptr = (unsigned long)(ei + 1);
1588         end = (unsigned long)ei + item_size;
1589
1590         if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK && !skinny_metadata) {
1591                 ptr += sizeof(struct btrfs_tree_block_info);
1592                 BUG_ON(ptr > end);
1593         }
1594
1595         if (owner >= BTRFS_FIRST_FREE_OBJECTID)
1596                 needed = BTRFS_REF_TYPE_DATA;
1597         else
1598                 needed = BTRFS_REF_TYPE_BLOCK;
1599
1600         err = -ENOENT;
1601         while (1) {
1602                 if (ptr >= end) {
1603                         WARN_ON(ptr > end);
1604                         break;
1605                 }
1606                 iref = (struct btrfs_extent_inline_ref *)ptr;
1607                 type = btrfs_get_extent_inline_ref_type(leaf, iref, needed);
1608                 if (type == BTRFS_REF_TYPE_INVALID) {
1609                         err = -EUCLEAN;
1610                         goto out;
1611                 }
1612
1613                 if (want < type)
1614                         break;
1615                 if (want > type) {
1616                         ptr += btrfs_extent_inline_ref_size(type);
1617                         continue;
1618                 }
1619
1620                 if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1621                         struct btrfs_extent_data_ref *dref;
1622                         dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1623                         if (match_extent_data_ref(leaf, dref, root_objectid,
1624                                                   owner, offset)) {
1625                                 err = 0;
1626                                 break;
1627                         }
1628                         if (hash_extent_data_ref_item(leaf, dref) <
1629                             hash_extent_data_ref(root_objectid, owner, offset))
1630                                 break;
1631                 } else {
1632                         u64 ref_offset;
1633                         ref_offset = btrfs_extent_inline_ref_offset(leaf, iref);
1634                         if (parent > 0) {
1635                                 if (parent == ref_offset) {
1636                                         err = 0;
1637                                         break;
1638                                 }
1639                                 if (ref_offset < parent)
1640                                         break;
1641                         } else {
1642                                 if (root_objectid == ref_offset) {
1643                                         err = 0;
1644                                         break;
1645                                 }
1646                                 if (ref_offset < root_objectid)
1647                                         break;
1648                         }
1649                 }
1650                 ptr += btrfs_extent_inline_ref_size(type);
1651         }
1652         if (err == -ENOENT && insert) {
1653                 if (item_size + extra_size >=
1654                     BTRFS_MAX_EXTENT_ITEM_SIZE(root)) {
1655                         err = -EAGAIN;
1656                         goto out;
1657                 }
1658                 /*
1659                  * To add new inline back ref, we have to make sure
1660                  * there is no corresponding back ref item.
1661                  * For simplicity, we just do not add new inline back
1662                  * ref if there is any kind of item for this block
1663                  */
1664                 if (find_next_key(path, 0, &key) == 0 &&
1665                     key.objectid == bytenr &&
1666                     key.type < BTRFS_BLOCK_GROUP_ITEM_KEY) {
1667                         err = -EAGAIN;
1668                         goto out;
1669                 }
1670         }
1671         *ref_ret = (struct btrfs_extent_inline_ref *)ptr;
1672 out:
1673         if (insert) {
1674                 path->keep_locks = 0;
1675                 btrfs_unlock_up_safe(path, 1);
1676         }
1677         return err;
1678 }
1679
1680 /*
1681  * helper to add new inline back ref
1682  */
1683 static noinline_for_stack
1684 void setup_inline_extent_backref(struct btrfs_fs_info *fs_info,
1685                                  struct btrfs_path *path,
1686                                  struct btrfs_extent_inline_ref *iref,
1687                                  u64 parent, u64 root_objectid,
1688                                  u64 owner, u64 offset, int refs_to_add,
1689                                  struct btrfs_delayed_extent_op *extent_op)
1690 {
1691         struct extent_buffer *leaf;
1692         struct btrfs_extent_item *ei;
1693         unsigned long ptr;
1694         unsigned long end;
1695         unsigned long item_offset;
1696         u64 refs;
1697         int size;
1698         int type;
1699
1700         leaf = path->nodes[0];
1701         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1702         item_offset = (unsigned long)iref - (unsigned long)ei;
1703
1704         type = extent_ref_type(parent, owner);
1705         size = btrfs_extent_inline_ref_size(type);
1706
1707         btrfs_extend_item(fs_info, path, size);
1708
1709         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1710         refs = btrfs_extent_refs(leaf, ei);
1711         refs += refs_to_add;
1712         btrfs_set_extent_refs(leaf, ei, refs);
1713         if (extent_op)
1714                 __run_delayed_extent_op(extent_op, leaf, ei);
1715
1716         ptr = (unsigned long)ei + item_offset;
1717         end = (unsigned long)ei + btrfs_item_size_nr(leaf, path->slots[0]);
1718         if (ptr < end - size)
1719                 memmove_extent_buffer(leaf, ptr + size, ptr,
1720                                       end - size - ptr);
1721
1722         iref = (struct btrfs_extent_inline_ref *)ptr;
1723         btrfs_set_extent_inline_ref_type(leaf, iref, type);
1724         if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1725                 struct btrfs_extent_data_ref *dref;
1726                 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1727                 btrfs_set_extent_data_ref_root(leaf, dref, root_objectid);
1728                 btrfs_set_extent_data_ref_objectid(leaf, dref, owner);
1729                 btrfs_set_extent_data_ref_offset(leaf, dref, offset);
1730                 btrfs_set_extent_data_ref_count(leaf, dref, refs_to_add);
1731         } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
1732                 struct btrfs_shared_data_ref *sref;
1733                 sref = (struct btrfs_shared_data_ref *)(iref + 1);
1734                 btrfs_set_shared_data_ref_count(leaf, sref, refs_to_add);
1735                 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
1736         } else if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
1737                 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
1738         } else {
1739                 btrfs_set_extent_inline_ref_offset(leaf, iref, root_objectid);
1740         }
1741         btrfs_mark_buffer_dirty(leaf);
1742 }
1743
1744 static int lookup_extent_backref(struct btrfs_trans_handle *trans,
1745                                  struct btrfs_path *path,
1746                                  struct btrfs_extent_inline_ref **ref_ret,
1747                                  u64 bytenr, u64 num_bytes, u64 parent,
1748                                  u64 root_objectid, u64 owner, u64 offset)
1749 {
1750         int ret;
1751
1752         ret = lookup_inline_extent_backref(trans, path, ref_ret, bytenr,
1753                                            num_bytes, parent, root_objectid,
1754                                            owner, offset, 0);
1755         if (ret != -ENOENT)
1756                 return ret;
1757
1758         btrfs_release_path(path);
1759         *ref_ret = NULL;
1760
1761         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1762                 ret = lookup_tree_block_ref(trans, path, bytenr, parent,
1763                                             root_objectid);
1764         } else {
1765                 ret = lookup_extent_data_ref(trans, path, bytenr, parent,
1766                                              root_objectid, owner, offset);
1767         }
1768         return ret;
1769 }
1770
1771 /*
1772  * helper to update/remove inline back ref
1773  */
1774 static noinline_for_stack
1775 void update_inline_extent_backref(struct btrfs_path *path,
1776                                   struct btrfs_extent_inline_ref *iref,
1777                                   int refs_to_mod,
1778                                   struct btrfs_delayed_extent_op *extent_op,
1779                                   int *last_ref)
1780 {
1781         struct extent_buffer *leaf = path->nodes[0];
1782         struct btrfs_fs_info *fs_info = leaf->fs_info;
1783         struct btrfs_extent_item *ei;
1784         struct btrfs_extent_data_ref *dref = NULL;
1785         struct btrfs_shared_data_ref *sref = NULL;
1786         unsigned long ptr;
1787         unsigned long end;
1788         u32 item_size;
1789         int size;
1790         int type;
1791         u64 refs;
1792
1793         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1794         refs = btrfs_extent_refs(leaf, ei);
1795         WARN_ON(refs_to_mod < 0 && refs + refs_to_mod <= 0);
1796         refs += refs_to_mod;
1797         btrfs_set_extent_refs(leaf, ei, refs);
1798         if (extent_op)
1799                 __run_delayed_extent_op(extent_op, leaf, ei);
1800
1801         /*
1802          * If type is invalid, we should have bailed out after
1803          * lookup_inline_extent_backref().
1804          */
1805         type = btrfs_get_extent_inline_ref_type(leaf, iref, BTRFS_REF_TYPE_ANY);
1806         ASSERT(type != BTRFS_REF_TYPE_INVALID);
1807
1808         if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1809                 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1810                 refs = btrfs_extent_data_ref_count(leaf, dref);
1811         } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
1812                 sref = (struct btrfs_shared_data_ref *)(iref + 1);
1813                 refs = btrfs_shared_data_ref_count(leaf, sref);
1814         } else {
1815                 refs = 1;
1816                 BUG_ON(refs_to_mod != -1);
1817         }
1818
1819         BUG_ON(refs_to_mod < 0 && refs < -refs_to_mod);
1820         refs += refs_to_mod;
1821
1822         if (refs > 0) {
1823                 if (type == BTRFS_EXTENT_DATA_REF_KEY)
1824                         btrfs_set_extent_data_ref_count(leaf, dref, refs);
1825                 else
1826                         btrfs_set_shared_data_ref_count(leaf, sref, refs);
1827         } else {
1828                 *last_ref = 1;
1829                 size =  btrfs_extent_inline_ref_size(type);
1830                 item_size = btrfs_item_size_nr(leaf, path->slots[0]);
1831                 ptr = (unsigned long)iref;
1832                 end = (unsigned long)ei + item_size;
1833                 if (ptr + size < end)
1834                         memmove_extent_buffer(leaf, ptr, ptr + size,
1835                                               end - ptr - size);
1836                 item_size -= size;
1837                 btrfs_truncate_item(fs_info, path, item_size, 1);
1838         }
1839         btrfs_mark_buffer_dirty(leaf);
1840 }
1841
1842 static noinline_for_stack
1843 int insert_inline_extent_backref(struct btrfs_trans_handle *trans,
1844                                  struct btrfs_path *path,
1845                                  u64 bytenr, u64 num_bytes, u64 parent,
1846                                  u64 root_objectid, u64 owner,
1847                                  u64 offset, int refs_to_add,
1848                                  struct btrfs_delayed_extent_op *extent_op)
1849 {
1850         struct btrfs_extent_inline_ref *iref;
1851         int ret;
1852
1853         ret = lookup_inline_extent_backref(trans, path, &iref, bytenr,
1854                                            num_bytes, parent, root_objectid,
1855                                            owner, offset, 1);
1856         if (ret == 0) {
1857                 BUG_ON(owner < BTRFS_FIRST_FREE_OBJECTID);
1858                 update_inline_extent_backref(path, iref, refs_to_add,
1859                                              extent_op, NULL);
1860         } else if (ret == -ENOENT) {
1861                 setup_inline_extent_backref(trans->fs_info, path, iref, parent,
1862                                             root_objectid, owner, offset,
1863                                             refs_to_add, extent_op);
1864                 ret = 0;
1865         }
1866         return ret;
1867 }
1868
1869 static int insert_extent_backref(struct btrfs_trans_handle *trans,
1870                                  struct btrfs_path *path,
1871                                  u64 bytenr, u64 parent, u64 root_objectid,
1872                                  u64 owner, u64 offset, int refs_to_add)
1873 {
1874         int ret;
1875         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1876                 BUG_ON(refs_to_add != 1);
1877                 ret = insert_tree_block_ref(trans, path, bytenr, parent,
1878                                             root_objectid);
1879         } else {
1880                 ret = insert_extent_data_ref(trans, path, bytenr, parent,
1881                                              root_objectid, owner, offset,
1882                                              refs_to_add);
1883         }
1884         return ret;
1885 }
1886
1887 static int remove_extent_backref(struct btrfs_trans_handle *trans,
1888                                  struct btrfs_path *path,
1889                                  struct btrfs_extent_inline_ref *iref,
1890                                  int refs_to_drop, int is_data, int *last_ref)
1891 {
1892         int ret = 0;
1893
1894         BUG_ON(!is_data && refs_to_drop != 1);
1895         if (iref) {
1896                 update_inline_extent_backref(path, iref, -refs_to_drop, NULL,
1897                                              last_ref);
1898         } else if (is_data) {
1899                 ret = remove_extent_data_ref(trans, path, refs_to_drop,
1900                                              last_ref);
1901         } else {
1902                 *last_ref = 1;
1903                 ret = btrfs_del_item(trans, trans->fs_info->extent_root, path);
1904         }
1905         return ret;
1906 }
1907
1908 static int btrfs_issue_discard(struct block_device *bdev, u64 start, u64 len,
1909                                u64 *discarded_bytes)
1910 {
1911         int j, ret = 0;
1912         u64 bytes_left, end;
1913         u64 aligned_start = ALIGN(start, 1 << 9);
1914
1915         if (WARN_ON(start != aligned_start)) {
1916                 len -= aligned_start - start;
1917                 len = round_down(len, 1 << 9);
1918                 start = aligned_start;
1919         }
1920
1921         *discarded_bytes = 0;
1922
1923         if (!len)
1924                 return 0;
1925
1926         end = start + len;
1927         bytes_left = len;
1928
1929         /* Skip any superblocks on this device. */
1930         for (j = 0; j < BTRFS_SUPER_MIRROR_MAX; j++) {
1931                 u64 sb_start = btrfs_sb_offset(j);
1932                 u64 sb_end = sb_start + BTRFS_SUPER_INFO_SIZE;
1933                 u64 size = sb_start - start;
1934
1935                 if (!in_range(sb_start, start, bytes_left) &&
1936                     !in_range(sb_end, start, bytes_left) &&
1937                     !in_range(start, sb_start, BTRFS_SUPER_INFO_SIZE))
1938                         continue;
1939
1940                 /*
1941                  * Superblock spans beginning of range.  Adjust start and
1942                  * try again.
1943                  */
1944                 if (sb_start <= start) {
1945                         start += sb_end - start;
1946                         if (start > end) {
1947                                 bytes_left = 0;
1948                                 break;
1949                         }
1950                         bytes_left = end - start;
1951                         continue;
1952                 }
1953
1954                 if (size) {
1955                         ret = blkdev_issue_discard(bdev, start >> 9, size >> 9,
1956                                                    GFP_NOFS, 0);
1957                         if (!ret)
1958                                 *discarded_bytes += size;
1959                         else if (ret != -EOPNOTSUPP)
1960                                 return ret;
1961                 }
1962
1963                 start = sb_end;
1964                 if (start > end) {
1965                         bytes_left = 0;
1966                         break;
1967                 }
1968                 bytes_left = end - start;
1969         }
1970
1971         if (bytes_left) {
1972                 ret = blkdev_issue_discard(bdev, start >> 9, bytes_left >> 9,
1973                                            GFP_NOFS, 0);
1974                 if (!ret)
1975                         *discarded_bytes += bytes_left;
1976         }
1977         return ret;
1978 }
1979
1980 int btrfs_discard_extent(struct btrfs_fs_info *fs_info, u64 bytenr,
1981                          u64 num_bytes, u64 *actual_bytes)
1982 {
1983         int ret;
1984         u64 discarded_bytes = 0;
1985         struct btrfs_bio *bbio = NULL;
1986
1987
1988         /*
1989          * Avoid races with device replace and make sure our bbio has devices
1990          * associated to its stripes that don't go away while we are discarding.
1991          */
1992         btrfs_bio_counter_inc_blocked(fs_info);
1993         /* Tell the block device(s) that the sectors can be discarded */
1994         ret = btrfs_map_block(fs_info, BTRFS_MAP_DISCARD, bytenr, &num_bytes,
1995                               &bbio, 0);
1996         /* Error condition is -ENOMEM */
1997         if (!ret) {
1998                 struct btrfs_bio_stripe *stripe = bbio->stripes;
1999                 int i;
2000
2001
2002                 for (i = 0; i < bbio->num_stripes; i++, stripe++) {
2003                         u64 bytes;
2004                         struct request_queue *req_q;
2005
2006                         if (!stripe->dev->bdev) {
2007                                 ASSERT(btrfs_test_opt(fs_info, DEGRADED));
2008                                 continue;
2009                         }
2010                         req_q = bdev_get_queue(stripe->dev->bdev);
2011                         if (!blk_queue_discard(req_q))
2012                                 continue;
2013
2014                         ret = btrfs_issue_discard(stripe->dev->bdev,
2015                                                   stripe->physical,
2016                                                   stripe->length,
2017                                                   &bytes);
2018                         if (!ret)
2019                                 discarded_bytes += bytes;
2020                         else if (ret != -EOPNOTSUPP)
2021                                 break; /* Logic errors or -ENOMEM, or -EIO but I don't know how that could happen JDM */
2022
2023                         /*
2024                          * Just in case we get back EOPNOTSUPP for some reason,
2025                          * just ignore the return value so we don't screw up
2026                          * people calling discard_extent.
2027                          */
2028                         ret = 0;
2029                 }
2030                 btrfs_put_bbio(bbio);
2031         }
2032         btrfs_bio_counter_dec(fs_info);
2033
2034         if (actual_bytes)
2035                 *actual_bytes = discarded_bytes;
2036
2037
2038         if (ret == -EOPNOTSUPP)
2039                 ret = 0;
2040         return ret;
2041 }
2042
2043 /* Can return -ENOMEM */
2044 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
2045                          struct btrfs_root *root,
2046                          u64 bytenr, u64 num_bytes, u64 parent,
2047                          u64 root_objectid, u64 owner, u64 offset)
2048 {
2049         struct btrfs_fs_info *fs_info = root->fs_info;
2050         int old_ref_mod, new_ref_mod;
2051         int ret;
2052
2053         BUG_ON(owner < BTRFS_FIRST_FREE_OBJECTID &&
2054                root_objectid == BTRFS_TREE_LOG_OBJECTID);
2055
2056         btrfs_ref_tree_mod(root, bytenr, num_bytes, parent, root_objectid,
2057                            owner, offset, BTRFS_ADD_DELAYED_REF);
2058
2059         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
2060                 ret = btrfs_add_delayed_tree_ref(trans, bytenr,
2061                                                  num_bytes, parent,
2062                                                  root_objectid, (int)owner,
2063                                                  BTRFS_ADD_DELAYED_REF, NULL,
2064                                                  &old_ref_mod, &new_ref_mod);
2065         } else {
2066                 ret = btrfs_add_delayed_data_ref(trans, bytenr,
2067                                                  num_bytes, parent,
2068                                                  root_objectid, owner, offset,
2069                                                  0, BTRFS_ADD_DELAYED_REF,
2070                                                  &old_ref_mod, &new_ref_mod);
2071         }
2072
2073         if (ret == 0 && old_ref_mod < 0 && new_ref_mod >= 0) {
2074                 bool metadata = owner < BTRFS_FIRST_FREE_OBJECTID;
2075
2076                 add_pinned_bytes(fs_info, -num_bytes, metadata, root_objectid);
2077         }
2078
2079         return ret;
2080 }
2081
2082 /*
2083  * __btrfs_inc_extent_ref - insert backreference for a given extent
2084  *
2085  * @trans:          Handle of transaction
2086  *
2087  * @node:           The delayed ref node used to get the bytenr/length for
2088  *                  extent whose references are incremented.
2089  *
2090  * @parent:         If this is a shared extent (BTRFS_SHARED_DATA_REF_KEY/
2091  *                  BTRFS_SHARED_BLOCK_REF_KEY) then it holds the logical
2092  *                  bytenr of the parent block. Since new extents are always
2093  *                  created with indirect references, this will only be the case
2094  *                  when relocating a shared extent. In that case, root_objectid
2095  *                  will be BTRFS_TREE_RELOC_OBJECTID. Otheriwse, parent must
2096  *                  be 0
2097  *
2098  * @root_objectid:  The id of the root where this modification has originated,
2099  *                  this can be either one of the well-known metadata trees or
2100  *                  the subvolume id which references this extent.
2101  *
2102  * @owner:          For data extents it is the inode number of the owning file.
2103  *                  For metadata extents this parameter holds the level in the
2104  *                  tree of the extent.
2105  *
2106  * @offset:         For metadata extents the offset is ignored and is currently
2107  *                  always passed as 0. For data extents it is the fileoffset
2108  *                  this extent belongs to.
2109  *
2110  * @refs_to_add     Number of references to add
2111  *
2112  * @extent_op       Pointer to a structure, holding information necessary when
2113  *                  updating a tree block's flags
2114  *
2115  */
2116 static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
2117                                   struct btrfs_delayed_ref_node *node,
2118                                   u64 parent, u64 root_objectid,
2119                                   u64 owner, u64 offset, int refs_to_add,
2120                                   struct btrfs_delayed_extent_op *extent_op)
2121 {
2122         struct btrfs_path *path;
2123         struct extent_buffer *leaf;
2124         struct btrfs_extent_item *item;
2125         struct btrfs_key key;
2126         u64 bytenr = node->bytenr;
2127         u64 num_bytes = node->num_bytes;
2128         u64 refs;
2129         int ret;
2130
2131         path = btrfs_alloc_path();
2132         if (!path)
2133                 return -ENOMEM;
2134
2135         path->reada = READA_FORWARD;
2136         path->leave_spinning = 1;
2137         /* this will setup the path even if it fails to insert the back ref */
2138         ret = insert_inline_extent_backref(trans, path, bytenr, num_bytes,
2139                                            parent, root_objectid, owner,
2140                                            offset, refs_to_add, extent_op);
2141         if ((ret < 0 && ret != -EAGAIN) || !ret)
2142                 goto out;
2143
2144         /*
2145          * Ok we had -EAGAIN which means we didn't have space to insert and
2146          * inline extent ref, so just update the reference count and add a
2147          * normal backref.
2148          */
2149         leaf = path->nodes[0];
2150         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
2151         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
2152         refs = btrfs_extent_refs(leaf, item);
2153         btrfs_set_extent_refs(leaf, item, refs + refs_to_add);
2154         if (extent_op)
2155                 __run_delayed_extent_op(extent_op, leaf, item);
2156
2157         btrfs_mark_buffer_dirty(leaf);
2158         btrfs_release_path(path);
2159
2160         path->reada = READA_FORWARD;
2161         path->leave_spinning = 1;
2162         /* now insert the actual backref */
2163         ret = insert_extent_backref(trans, path, bytenr, parent, root_objectid,
2164                                     owner, offset, refs_to_add);
2165         if (ret)
2166                 btrfs_abort_transaction(trans, ret);
2167 out:
2168         btrfs_free_path(path);
2169         return ret;
2170 }
2171
2172 static int run_delayed_data_ref(struct btrfs_trans_handle *trans,
2173                                 struct btrfs_delayed_ref_node *node,
2174                                 struct btrfs_delayed_extent_op *extent_op,
2175                                 int insert_reserved)
2176 {
2177         int ret = 0;
2178         struct btrfs_delayed_data_ref *ref;
2179         struct btrfs_key ins;
2180         u64 parent = 0;
2181         u64 ref_root = 0;
2182         u64 flags = 0;
2183
2184         ins.objectid = node->bytenr;
2185         ins.offset = node->num_bytes;
2186         ins.type = BTRFS_EXTENT_ITEM_KEY;
2187
2188         ref = btrfs_delayed_node_to_data_ref(node);
2189         trace_run_delayed_data_ref(trans->fs_info, node, ref, node->action);
2190
2191         if (node->type == BTRFS_SHARED_DATA_REF_KEY)
2192                 parent = ref->parent;
2193         ref_root = ref->root;
2194
2195         if (node->action == BTRFS_ADD_DELAYED_REF && insert_reserved) {
2196                 if (extent_op)
2197                         flags |= extent_op->flags_to_set;
2198                 ret = alloc_reserved_file_extent(trans, parent, ref_root,
2199                                                  flags, ref->objectid,
2200                                                  ref->offset, &ins,
2201                                                  node->ref_mod);
2202         } else if (node->action == BTRFS_ADD_DELAYED_REF) {
2203                 ret = __btrfs_inc_extent_ref(trans, node, parent, ref_root,
2204                                              ref->objectid, ref->offset,
2205                                              node->ref_mod, extent_op);
2206         } else if (node->action == BTRFS_DROP_DELAYED_REF) {
2207                 ret = __btrfs_free_extent(trans, node, parent,
2208                                           ref_root, ref->objectid,
2209                                           ref->offset, node->ref_mod,
2210                                           extent_op);
2211         } else {
2212                 BUG();
2213         }
2214         return ret;
2215 }
2216
2217 static void __run_delayed_extent_op(struct btrfs_delayed_extent_op *extent_op,
2218                                     struct extent_buffer *leaf,
2219                                     struct btrfs_extent_item *ei)
2220 {
2221         u64 flags = btrfs_extent_flags(leaf, ei);
2222         if (extent_op->update_flags) {
2223                 flags |= extent_op->flags_to_set;
2224                 btrfs_set_extent_flags(leaf, ei, flags);
2225         }
2226
2227         if (extent_op->update_key) {
2228                 struct btrfs_tree_block_info *bi;
2229                 BUG_ON(!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK));
2230                 bi = (struct btrfs_tree_block_info *)(ei + 1);
2231                 btrfs_set_tree_block_key(leaf, bi, &extent_op->key);
2232         }
2233 }
2234
2235 static int run_delayed_extent_op(struct btrfs_trans_handle *trans,
2236                                  struct btrfs_delayed_ref_head *head,
2237                                  struct btrfs_delayed_extent_op *extent_op)
2238 {
2239         struct btrfs_fs_info *fs_info = trans->fs_info;
2240         struct btrfs_key key;
2241         struct btrfs_path *path;
2242         struct btrfs_extent_item *ei;
2243         struct extent_buffer *leaf;
2244         u32 item_size;
2245         int ret;
2246         int err = 0;
2247         int metadata = !extent_op->is_data;
2248
2249         if (trans->aborted)
2250                 return 0;
2251
2252         if (metadata && !btrfs_fs_incompat(fs_info, SKINNY_METADATA))
2253                 metadata = 0;
2254
2255         path = btrfs_alloc_path();
2256         if (!path)
2257                 return -ENOMEM;
2258
2259         key.objectid = head->bytenr;
2260
2261         if (metadata) {
2262                 key.type = BTRFS_METADATA_ITEM_KEY;
2263                 key.offset = extent_op->level;
2264         } else {
2265                 key.type = BTRFS_EXTENT_ITEM_KEY;
2266                 key.offset = head->num_bytes;
2267         }
2268
2269 again:
2270         path->reada = READA_FORWARD;
2271         path->leave_spinning = 1;
2272         ret = btrfs_search_slot(trans, fs_info->extent_root, &key, path, 0, 1);
2273         if (ret < 0) {
2274                 err = ret;
2275                 goto out;
2276         }
2277         if (ret > 0) {
2278                 if (metadata) {
2279                         if (path->slots[0] > 0) {
2280                                 path->slots[0]--;
2281                                 btrfs_item_key_to_cpu(path->nodes[0], &key,
2282                                                       path->slots[0]);
2283                                 if (key.objectid == head->bytenr &&
2284                                     key.type == BTRFS_EXTENT_ITEM_KEY &&
2285                                     key.offset == head->num_bytes)
2286                                         ret = 0;
2287                         }
2288                         if (ret > 0) {
2289                                 btrfs_release_path(path);
2290                                 metadata = 0;
2291
2292                                 key.objectid = head->bytenr;
2293                                 key.offset = head->num_bytes;
2294                                 key.type = BTRFS_EXTENT_ITEM_KEY;
2295                                 goto again;
2296                         }
2297                 } else {
2298                         err = -EIO;
2299                         goto out;
2300                 }
2301         }
2302
2303         leaf = path->nodes[0];
2304         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
2305
2306         if (unlikely(item_size < sizeof(*ei))) {
2307                 err = -EINVAL;
2308                 btrfs_print_v0_err(fs_info);
2309                 btrfs_abort_transaction(trans, err);
2310                 goto out;
2311         }
2312
2313         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
2314         __run_delayed_extent_op(extent_op, leaf, ei);
2315
2316         btrfs_mark_buffer_dirty(leaf);
2317 out:
2318         btrfs_free_path(path);
2319         return err;
2320 }
2321
2322 static int run_delayed_tree_ref(struct btrfs_trans_handle *trans,
2323                                 struct btrfs_delayed_ref_node *node,
2324                                 struct btrfs_delayed_extent_op *extent_op,
2325                                 int insert_reserved)
2326 {
2327         int ret = 0;
2328         struct btrfs_delayed_tree_ref *ref;
2329         u64 parent = 0;
2330         u64 ref_root = 0;
2331
2332         ref = btrfs_delayed_node_to_tree_ref(node);
2333         trace_run_delayed_tree_ref(trans->fs_info, node, ref, node->action);
2334
2335         if (node->type == BTRFS_SHARED_BLOCK_REF_KEY)
2336                 parent = ref->parent;
2337         ref_root = ref->root;
2338
2339         if (node->ref_mod != 1) {
2340                 btrfs_err(trans->fs_info,
2341         "btree block(%llu) has %d references rather than 1: action %d ref_root %llu parent %llu",
2342                           node->bytenr, node->ref_mod, node->action, ref_root,
2343                           parent);
2344                 return -EIO;
2345         }
2346         if (node->action == BTRFS_ADD_DELAYED_REF && insert_reserved) {
2347                 BUG_ON(!extent_op || !extent_op->update_flags);
2348                 ret = alloc_reserved_tree_block(trans, node, extent_op);
2349         } else if (node->action == BTRFS_ADD_DELAYED_REF) {
2350                 ret = __btrfs_inc_extent_ref(trans, node, parent, ref_root,
2351                                              ref->level, 0, 1, extent_op);
2352         } else if (node->action == BTRFS_DROP_DELAYED_REF) {
2353                 ret = __btrfs_free_extent(trans, node, parent, ref_root,
2354                                           ref->level, 0, 1, extent_op);
2355         } else {
2356                 BUG();
2357         }
2358         return ret;
2359 }
2360
2361 /* helper function to actually process a single delayed ref entry */
2362 static int run_one_delayed_ref(struct btrfs_trans_handle *trans,
2363                                struct btrfs_delayed_ref_node *node,
2364                                struct btrfs_delayed_extent_op *extent_op,
2365                                int insert_reserved)
2366 {
2367         int ret = 0;
2368
2369         if (trans->aborted) {
2370                 if (insert_reserved)
2371                         btrfs_pin_extent(trans->fs_info, node->bytenr,
2372                                          node->num_bytes, 1);
2373                 return 0;
2374         }
2375
2376         if (node->type == BTRFS_TREE_BLOCK_REF_KEY ||
2377             node->type == BTRFS_SHARED_BLOCK_REF_KEY)
2378                 ret = run_delayed_tree_ref(trans, node, extent_op,
2379                                            insert_reserved);
2380         else if (node->type == BTRFS_EXTENT_DATA_REF_KEY ||
2381                  node->type == BTRFS_SHARED_DATA_REF_KEY)
2382                 ret = run_delayed_data_ref(trans, node, extent_op,
2383                                            insert_reserved);
2384         else
2385                 BUG();
2386         if (ret && insert_reserved)
2387                 btrfs_pin_extent(trans->fs_info, node->bytenr,
2388                                  node->num_bytes, 1);
2389         return ret;
2390 }
2391
2392 static inline struct btrfs_delayed_ref_node *
2393 select_delayed_ref(struct btrfs_delayed_ref_head *head)
2394 {
2395         struct btrfs_delayed_ref_node *ref;
2396
2397         if (RB_EMPTY_ROOT(&head->ref_tree.rb_root))
2398                 return NULL;
2399
2400         /*
2401          * Select a delayed ref of type BTRFS_ADD_DELAYED_REF first.
2402          * This is to prevent a ref count from going down to zero, which deletes
2403          * the extent item from the extent tree, when there still are references
2404          * to add, which would fail because they would not find the extent item.
2405          */
2406         if (!list_empty(&head->ref_add_list))
2407                 return list_first_entry(&head->ref_add_list,
2408                                 struct btrfs_delayed_ref_node, add_list);
2409
2410         ref = rb_entry(rb_first_cached(&head->ref_tree),
2411                        struct btrfs_delayed_ref_node, ref_node);
2412         ASSERT(list_empty(&ref->add_list));
2413         return ref;
2414 }
2415
2416 static void unselect_delayed_ref_head(struct btrfs_delayed_ref_root *delayed_refs,
2417                                       struct btrfs_delayed_ref_head *head)
2418 {
2419         spin_lock(&delayed_refs->lock);
2420         head->processing = 0;
2421         delayed_refs->num_heads_ready++;
2422         spin_unlock(&delayed_refs->lock);
2423         btrfs_delayed_ref_unlock(head);
2424 }
2425
2426 static struct btrfs_delayed_extent_op *cleanup_extent_op(
2427                                 struct btrfs_delayed_ref_head *head)
2428 {
2429         struct btrfs_delayed_extent_op *extent_op = head->extent_op;
2430
2431         if (!extent_op)
2432                 return NULL;
2433
2434         if (head->must_insert_reserved) {
2435                 head->extent_op = NULL;
2436                 btrfs_free_delayed_extent_op(extent_op);
2437                 return NULL;
2438         }
2439         return extent_op;
2440 }
2441
2442 static int run_and_cleanup_extent_op(struct btrfs_trans_handle *trans,
2443                                      struct btrfs_delayed_ref_head *head)
2444 {
2445         struct btrfs_delayed_extent_op *extent_op;
2446         int ret;
2447
2448         extent_op = cleanup_extent_op(head);
2449         if (!extent_op)
2450                 return 0;
2451         head->extent_op = NULL;
2452         spin_unlock(&head->lock);
2453         ret = run_delayed_extent_op(trans, head, extent_op);
2454         btrfs_free_delayed_extent_op(extent_op);
2455         return ret ? ret : 1;
2456 }
2457
2458 void btrfs_cleanup_ref_head_accounting(struct btrfs_fs_info *fs_info,
2459                                   struct btrfs_delayed_ref_root *delayed_refs,
2460                                   struct btrfs_delayed_ref_head *head)
2461 {
2462         int nr_items = 1;       /* Dropping this ref head update. */
2463
2464         if (head->total_ref_mod < 0) {
2465                 struct btrfs_space_info *space_info;
2466                 u64 flags;
2467
2468                 if (head->is_data)
2469                         flags = BTRFS_BLOCK_GROUP_DATA;
2470                 else if (head->is_system)
2471                         flags = BTRFS_BLOCK_GROUP_SYSTEM;
2472                 else
2473                         flags = BTRFS_BLOCK_GROUP_METADATA;
2474                 space_info = __find_space_info(fs_info, flags);
2475                 ASSERT(space_info);
2476                 percpu_counter_add_batch(&space_info->total_bytes_pinned,
2477                                    -head->num_bytes,
2478                                    BTRFS_TOTAL_BYTES_PINNED_BATCH);
2479
2480                 /*
2481                  * We had csum deletions accounted for in our delayed refs rsv,
2482                  * we need to drop the csum leaves for this update from our
2483                  * delayed_refs_rsv.
2484                  */
2485                 if (head->is_data) {
2486                         spin_lock(&delayed_refs->lock);
2487                         delayed_refs->pending_csums -= head->num_bytes;
2488                         spin_unlock(&delayed_refs->lock);
2489                         nr_items += btrfs_csum_bytes_to_leaves(fs_info,
2490                                 head->num_bytes);
2491                 }
2492         }
2493
2494         btrfs_delayed_refs_rsv_release(fs_info, nr_items);
2495 }
2496
2497 static int cleanup_ref_head(struct btrfs_trans_handle *trans,
2498                             struct btrfs_delayed_ref_head *head)
2499 {
2500
2501         struct btrfs_fs_info *fs_info = trans->fs_info;
2502         struct btrfs_delayed_ref_root *delayed_refs;
2503         int ret;
2504
2505         delayed_refs = &trans->transaction->delayed_refs;
2506
2507         ret = run_and_cleanup_extent_op(trans, head);
2508         if (ret < 0) {
2509                 unselect_delayed_ref_head(delayed_refs, head);
2510                 btrfs_debug(fs_info, "run_delayed_extent_op returned %d", ret);
2511                 return ret;
2512         } else if (ret) {
2513                 return ret;
2514         }
2515
2516         /*
2517          * Need to drop our head ref lock and re-acquire the delayed ref lock
2518          * and then re-check to make sure nobody got added.
2519          */
2520         spin_unlock(&head->lock);
2521         spin_lock(&delayed_refs->lock);
2522         spin_lock(&head->lock);
2523         if (!RB_EMPTY_ROOT(&head->ref_tree.rb_root) || head->extent_op) {
2524                 spin_unlock(&head->lock);
2525                 spin_unlock(&delayed_refs->lock);
2526                 return 1;
2527         }
2528         btrfs_delete_ref_head(delayed_refs, head);
2529         spin_unlock(&head->lock);
2530         spin_unlock(&delayed_refs->lock);
2531
2532         if (head->must_insert_reserved) {
2533                 btrfs_pin_extent(fs_info, head->bytenr,
2534                                  head->num_bytes, 1);
2535                 if (head->is_data) {
2536                         ret = btrfs_del_csums(trans, fs_info, head->bytenr,
2537                                               head->num_bytes);
2538                 }
2539         }
2540
2541         btrfs_cleanup_ref_head_accounting(fs_info, delayed_refs, head);
2542
2543         trace_run_delayed_ref_head(fs_info, head, 0);
2544         btrfs_delayed_ref_unlock(head);
2545         btrfs_put_delayed_ref_head(head);
2546         return 0;
2547 }
2548
2549 static struct btrfs_delayed_ref_head *btrfs_obtain_ref_head(
2550                                         struct btrfs_trans_handle *trans)
2551 {
2552         struct btrfs_delayed_ref_root *delayed_refs =
2553                 &trans->transaction->delayed_refs;
2554         struct btrfs_delayed_ref_head *head = NULL;
2555         int ret;
2556
2557         spin_lock(&delayed_refs->lock);
2558         head = btrfs_select_ref_head(delayed_refs);
2559         if (!head) {
2560                 spin_unlock(&delayed_refs->lock);
2561                 return head;
2562         }
2563
2564         /*
2565          * Grab the lock that says we are going to process all the refs for
2566          * this head
2567          */
2568         ret = btrfs_delayed_ref_lock(delayed_refs, head);
2569         spin_unlock(&delayed_refs->lock);
2570
2571         /*
2572          * We may have dropped the spin lock to get the head mutex lock, and
2573          * that might have given someone else time to free the head.  If that's
2574          * true, it has been removed from our list and we can move on.
2575          */
2576         if (ret == -EAGAIN)
2577                 head = ERR_PTR(-EAGAIN);
2578
2579         return head;
2580 }
2581
2582 static int btrfs_run_delayed_refs_for_head(struct btrfs_trans_handle *trans,
2583                                     struct btrfs_delayed_ref_head *locked_ref,
2584                                     unsigned long *run_refs)
2585 {
2586         struct btrfs_fs_info *fs_info = trans->fs_info;
2587         struct btrfs_delayed_ref_root *delayed_refs;
2588         struct btrfs_delayed_extent_op *extent_op;
2589         struct btrfs_delayed_ref_node *ref;
2590         int must_insert_reserved = 0;
2591         int ret;
2592
2593         delayed_refs = &trans->transaction->delayed_refs;
2594
2595         lockdep_assert_held(&locked_ref->mutex);
2596         lockdep_assert_held(&locked_ref->lock);
2597
2598         while ((ref = select_delayed_ref(locked_ref))) {
2599                 if (ref->seq &&
2600                     btrfs_check_delayed_seq(fs_info, ref->seq)) {
2601                         spin_unlock(&locked_ref->lock);
2602                         unselect_delayed_ref_head(delayed_refs, locked_ref);
2603                         return -EAGAIN;
2604                 }
2605
2606                 (*run_refs)++;
2607                 ref->in_tree = 0;
2608                 rb_erase_cached(&ref->ref_node, &locked_ref->ref_tree);
2609                 RB_CLEAR_NODE(&ref->ref_node);
2610                 if (!list_empty(&ref->add_list))
2611                         list_del(&ref->add_list);
2612                 /*
2613                  * When we play the delayed ref, also correct the ref_mod on
2614                  * head
2615                  */
2616                 switch (ref->action) {
2617                 case BTRFS_ADD_DELAYED_REF:
2618                 case BTRFS_ADD_DELAYED_EXTENT:
2619                         locked_ref->ref_mod -= ref->ref_mod;
2620                         break;
2621                 case BTRFS_DROP_DELAYED_REF:
2622                         locked_ref->ref_mod += ref->ref_mod;
2623                         break;
2624                 default:
2625                         WARN_ON(1);
2626                 }
2627                 atomic_dec(&delayed_refs->num_entries);
2628
2629                 /*
2630                  * Record the must_insert_reserved flag before we drop the
2631                  * spin lock.
2632                  */
2633                 must_insert_reserved = locked_ref->must_insert_reserved;
2634                 locked_ref->must_insert_reserved = 0;
2635
2636                 extent_op = locked_ref->extent_op;
2637                 locked_ref->extent_op = NULL;
2638                 spin_unlock(&locked_ref->lock);
2639
2640                 ret = run_one_delayed_ref(trans, ref, extent_op,
2641                                           must_insert_reserved);
2642
2643                 btrfs_free_delayed_extent_op(extent_op);
2644                 if (ret) {
2645                         unselect_delayed_ref_head(delayed_refs, locked_ref);
2646                         btrfs_put_delayed_ref(ref);
2647                         btrfs_debug(fs_info, "run_one_delayed_ref returned %d",
2648                                     ret);
2649                         return ret;
2650                 }
2651
2652                 btrfs_put_delayed_ref(ref);
2653                 cond_resched();
2654
2655                 spin_lock(&locked_ref->lock);
2656                 btrfs_merge_delayed_refs(trans, delayed_refs, locked_ref);
2657         }
2658
2659         return 0;
2660 }
2661
2662 /*
2663  * Returns 0 on success or if called with an already aborted transaction.
2664  * Returns -ENOMEM or -EIO on failure and will abort the transaction.
2665  */
2666 static noinline int __btrfs_run_delayed_refs(struct btrfs_trans_handle *trans,
2667                                              unsigned long nr)
2668 {
2669         struct btrfs_fs_info *fs_info = trans->fs_info;
2670         struct btrfs_delayed_ref_root *delayed_refs;
2671         struct btrfs_delayed_ref_head *locked_ref = NULL;
2672         ktime_t start = ktime_get();
2673         int ret;
2674         unsigned long count = 0;
2675         unsigned long actual_count = 0;
2676
2677         delayed_refs = &trans->transaction->delayed_refs;
2678         do {
2679                 if (!locked_ref) {
2680                         locked_ref = btrfs_obtain_ref_head(trans);
2681                         if (IS_ERR_OR_NULL(locked_ref)) {
2682                                 if (PTR_ERR(locked_ref) == -EAGAIN) {
2683                                         continue;
2684                                 } else {
2685                                         break;
2686                                 }
2687                         }
2688                         count++;
2689                 }
2690                 /*
2691                  * We need to try and merge add/drops of the same ref since we
2692                  * can run into issues with relocate dropping the implicit ref
2693                  * and then it being added back again before the drop can
2694                  * finish.  If we merged anything we need to re-loop so we can
2695                  * get a good ref.
2696                  * Or we can get node references of the same type that weren't
2697                  * merged when created due to bumps in the tree mod seq, and
2698                  * we need to merge them to prevent adding an inline extent
2699                  * backref before dropping it (triggering a BUG_ON at
2700                  * insert_inline_extent_backref()).
2701                  */
2702                 spin_lock(&locked_ref->lock);
2703                 btrfs_merge_delayed_refs(trans, delayed_refs, locked_ref);
2704
2705                 ret = btrfs_run_delayed_refs_for_head(trans, locked_ref,
2706                                                       &actual_count);
2707                 if (ret < 0 && ret != -EAGAIN) {
2708                         /*
2709                          * Error, btrfs_run_delayed_refs_for_head already
2710                          * unlocked everything so just bail out
2711                          */
2712                         return ret;
2713                 } else if (!ret) {
2714                         /*
2715                          * Success, perform the usual cleanup of a processed
2716                          * head
2717                          */
2718                         ret = cleanup_ref_head(trans, locked_ref);
2719                         if (ret > 0 ) {
2720                                 /* We dropped our lock, we need to loop. */
2721                                 ret = 0;
2722                                 continue;
2723                         } else if (ret) {
2724                                 return ret;
2725                         }
2726                 }
2727
2728                 /*
2729                  * Either success case or btrfs_run_delayed_refs_for_head
2730                  * returned -EAGAIN, meaning we need to select another head
2731                  */
2732
2733                 locked_ref = NULL;
2734                 cond_resched();
2735         } while ((nr != -1 && count < nr) || locked_ref);
2736
2737         /*
2738          * We don't want to include ref heads since we can have empty ref heads
2739          * and those will drastically skew our runtime down since we just do
2740          * accounting, no actual extent tree updates.
2741          */
2742         if (actual_count > 0) {
2743                 u64 runtime = ktime_to_ns(ktime_sub(ktime_get(), start));
2744                 u64 avg;
2745
2746                 /*
2747                  * We weigh the current average higher than our current runtime
2748                  * to avoid large swings in the average.
2749                  */
2750                 spin_lock(&delayed_refs->lock);
2751                 avg = fs_info->avg_delayed_ref_runtime * 3 + runtime;
2752                 fs_info->avg_delayed_ref_runtime = avg >> 2;    /* div by 4 */
2753                 spin_unlock(&delayed_refs->lock);
2754         }
2755         return 0;
2756 }
2757
2758 #ifdef SCRAMBLE_DELAYED_REFS
2759 /*
2760  * Normally delayed refs get processed in ascending bytenr order. This
2761  * correlates in most cases to the order added. To expose dependencies on this
2762  * order, we start to process the tree in the middle instead of the beginning
2763  */
2764 static u64 find_middle(struct rb_root *root)
2765 {
2766         struct rb_node *n = root->rb_node;
2767         struct btrfs_delayed_ref_node *entry;
2768         int alt = 1;
2769         u64 middle;
2770         u64 first = 0, last = 0;
2771
2772         n = rb_first(root);
2773         if (n) {
2774                 entry = rb_entry(n, struct btrfs_delayed_ref_node, rb_node);
2775                 first = entry->bytenr;
2776         }
2777         n = rb_last(root);
2778         if (n) {
2779                 entry = rb_entry(n, struct btrfs_delayed_ref_node, rb_node);
2780                 last = entry->bytenr;
2781         }
2782         n = root->rb_node;
2783
2784         while (n) {
2785                 entry = rb_entry(n, struct btrfs_delayed_ref_node, rb_node);
2786                 WARN_ON(!entry->in_tree);
2787
2788                 middle = entry->bytenr;
2789
2790                 if (alt)
2791                         n = n->rb_left;
2792                 else
2793                         n = n->rb_right;
2794
2795                 alt = 1 - alt;
2796         }
2797         return middle;
2798 }
2799 #endif
2800
2801 static inline u64 heads_to_leaves(struct btrfs_fs_info *fs_info, u64 heads)
2802 {
2803         u64 num_bytes;
2804
2805         num_bytes = heads * (sizeof(struct btrfs_extent_item) +
2806                              sizeof(struct btrfs_extent_inline_ref));
2807         if (!btrfs_fs_incompat(fs_info, SKINNY_METADATA))
2808                 num_bytes += heads * sizeof(struct btrfs_tree_block_info);
2809
2810         /*
2811          * We don't ever fill up leaves all the way so multiply by 2 just to be
2812          * closer to what we're really going to want to use.
2813          */
2814         return div_u64(num_bytes, BTRFS_LEAF_DATA_SIZE(fs_info));
2815 }
2816
2817 /*
2818  * Takes the number of bytes to be csumm'ed and figures out how many leaves it
2819  * would require to store the csums for that many bytes.
2820  */
2821 u64 btrfs_csum_bytes_to_leaves(struct btrfs_fs_info *fs_info, u64 csum_bytes)
2822 {
2823         u64 csum_size;
2824         u64 num_csums_per_leaf;
2825         u64 num_csums;
2826
2827         csum_size = BTRFS_MAX_ITEM_SIZE(fs_info);
2828         num_csums_per_leaf = div64_u64(csum_size,
2829                         (u64)btrfs_super_csum_size(fs_info->super_copy));
2830         num_csums = div64_u64(csum_bytes, fs_info->sectorsize);
2831         num_csums += num_csums_per_leaf - 1;
2832         num_csums = div64_u64(num_csums, num_csums_per_leaf);
2833         return num_csums;
2834 }
2835
2836 bool btrfs_check_space_for_delayed_refs(struct btrfs_fs_info *fs_info)
2837 {
2838         struct btrfs_block_rsv *delayed_refs_rsv = &fs_info->delayed_refs_rsv;
2839         struct btrfs_block_rsv *global_rsv = &fs_info->global_block_rsv;
2840         bool ret = false;
2841         u64 reserved;
2842
2843         spin_lock(&global_rsv->lock);
2844         reserved = global_rsv->reserved;
2845         spin_unlock(&global_rsv->lock);
2846
2847         /*
2848          * Since the global reserve is just kind of magic we don't really want
2849          * to rely on it to save our bacon, so if our size is more than the
2850          * delayed_refs_rsv and the global rsv then it's time to think about
2851          * bailing.
2852          */
2853         spin_lock(&delayed_refs_rsv->lock);
2854         reserved += delayed_refs_rsv->reserved;
2855         if (delayed_refs_rsv->size >= reserved)
2856                 ret = true;
2857         spin_unlock(&delayed_refs_rsv->lock);
2858         return ret;
2859 }
2860
2861 int btrfs_should_throttle_delayed_refs(struct btrfs_trans_handle *trans)
2862 {
2863         u64 num_entries =
2864                 atomic_read(&trans->transaction->delayed_refs.num_entries);
2865         u64 avg_runtime;
2866         u64 val;
2867
2868         smp_mb();
2869         avg_runtime = trans->fs_info->avg_delayed_ref_runtime;
2870         val = num_entries * avg_runtime;
2871         if (val >= NSEC_PER_SEC)
2872                 return 1;
2873         if (val >= NSEC_PER_SEC / 2)
2874                 return 2;
2875
2876         return btrfs_check_space_for_delayed_refs(trans->fs_info);
2877 }
2878
2879 /*
2880  * this starts processing the delayed reference count updates and
2881  * extent insertions we have queued up so far.  count can be
2882  * 0, which means to process everything in the tree at the start
2883  * of the run (but not newly added entries), or it can be some target
2884  * number you'd like to process.
2885  *
2886  * Returns 0 on success or if called with an aborted transaction
2887  * Returns <0 on error and aborts the transaction
2888  */
2889 int btrfs_run_delayed_refs(struct btrfs_trans_handle *trans,
2890                            unsigned long count)
2891 {
2892         struct btrfs_fs_info *fs_info = trans->fs_info;
2893         struct rb_node *node;
2894         struct btrfs_delayed_ref_root *delayed_refs;
2895         struct btrfs_delayed_ref_head *head;
2896         int ret;
2897         int run_all = count == (unsigned long)-1;
2898
2899         /* We'll clean this up in btrfs_cleanup_transaction */
2900         if (trans->aborted)
2901                 return 0;
2902
2903         if (test_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags))
2904                 return 0;
2905
2906         delayed_refs = &trans->transaction->delayed_refs;
2907         if (count == 0)
2908                 count = atomic_read(&delayed_refs->num_entries) * 2;
2909
2910 again:
2911 #ifdef SCRAMBLE_DELAYED_REFS
2912         delayed_refs->run_delayed_start = find_middle(&delayed_refs->root);
2913 #endif
2914         ret = __btrfs_run_delayed_refs(trans, count);
2915         if (ret < 0) {
2916                 btrfs_abort_transaction(trans, ret);
2917                 return ret;
2918         }
2919
2920         if (run_all) {
2921                 btrfs_create_pending_block_groups(trans);
2922
2923                 spin_lock(&delayed_refs->lock);
2924                 node = rb_first_cached(&delayed_refs->href_root);
2925                 if (!node) {
2926                         spin_unlock(&delayed_refs->lock);
2927                         goto out;
2928                 }
2929                 head = rb_entry(node, struct btrfs_delayed_ref_head,
2930                                 href_node);
2931                 refcount_inc(&head->refs);
2932                 spin_unlock(&delayed_refs->lock);
2933
2934                 /* Mutex was contended, block until it's released and retry. */
2935                 mutex_lock(&head->mutex);
2936                 mutex_unlock(&head->mutex);
2937
2938                 btrfs_put_delayed_ref_head(head);
2939                 cond_resched();
2940                 goto again;
2941         }
2942 out:
2943         return 0;
2944 }
2945
2946 int btrfs_set_disk_extent_flags(struct btrfs_trans_handle *trans,
2947                                 struct btrfs_fs_info *fs_info,
2948                                 u64 bytenr, u64 num_bytes, u64 flags,
2949                                 int level, int is_data)
2950 {
2951         struct btrfs_delayed_extent_op *extent_op;
2952         int ret;
2953
2954         extent_op = btrfs_alloc_delayed_extent_op();
2955         if (!extent_op)
2956                 return -ENOMEM;
2957
2958         extent_op->flags_to_set = flags;
2959         extent_op->update_flags = true;
2960         extent_op->update_key = false;
2961         extent_op->is_data = is_data ? true : false;
2962         extent_op->level = level;
2963
2964         ret = btrfs_add_delayed_extent_op(fs_info, trans, bytenr,
2965                                           num_bytes, extent_op);
2966         if (ret)
2967                 btrfs_free_delayed_extent_op(extent_op);
2968         return ret;
2969 }
2970
2971 static noinline int check_delayed_ref(struct btrfs_root *root,
2972                                       struct btrfs_path *path,
2973                                       u64 objectid, u64 offset, u64 bytenr)
2974 {
2975         struct btrfs_delayed_ref_head *head;
2976         struct btrfs_delayed_ref_node *ref;
2977         struct btrfs_delayed_data_ref *data_ref;
2978         struct btrfs_delayed_ref_root *delayed_refs;
2979         struct btrfs_transaction *cur_trans;
2980         struct rb_node *node;
2981         int ret = 0;
2982
2983         spin_lock(&root->fs_info->trans_lock);
2984         cur_trans = root->fs_info->running_transaction;
2985         if (cur_trans)
2986                 refcount_inc(&cur_trans->use_count);
2987         spin_unlock(&root->fs_info->trans_lock);
2988         if (!cur_trans)
2989                 return 0;
2990
2991         delayed_refs = &cur_trans->delayed_refs;
2992         spin_lock(&delayed_refs->lock);
2993         head = btrfs_find_delayed_ref_head(delayed_refs, bytenr);
2994         if (!head) {
2995                 spin_unlock(&delayed_refs->lock);
2996                 btrfs_put_transaction(cur_trans);
2997                 return 0;
2998         }
2999
3000         if (!mutex_trylock(&head->mutex)) {
3001                 refcount_inc(&head->refs);
3002                 spin_unlock(&delayed_refs->lock);
3003
3004                 btrfs_release_path(path);
3005
3006                 /*
3007                  * Mutex was contended, block until it's released and let
3008                  * caller try again
3009                  */
3010                 mutex_lock(&head->mutex);
3011                 mutex_unlock(&head->mutex);
3012                 btrfs_put_delayed_ref_head(head);
3013                 btrfs_put_transaction(cur_trans);
3014                 return -EAGAIN;
3015         }
3016         spin_unlock(&delayed_refs->lock);
3017
3018         spin_lock(&head->lock);
3019         /*
3020          * XXX: We should replace this with a proper search function in the
3021          * future.
3022          */
3023         for (node = rb_first_cached(&head->ref_tree); node;
3024              node = rb_next(node)) {
3025                 ref = rb_entry(node, struct btrfs_delayed_ref_node, ref_node);
3026                 /* If it's a shared ref we know a cross reference exists */
3027                 if (ref->type != BTRFS_EXTENT_DATA_REF_KEY) {
3028                         ret = 1;
3029                         break;
3030                 }
3031
3032                 data_ref = btrfs_delayed_node_to_data_ref(ref);
3033
3034                 /*
3035                  * If our ref doesn't match the one we're currently looking at
3036                  * then we have a cross reference.
3037                  */
3038                 if (data_ref->root != root->root_key.objectid ||
3039                     data_ref->objectid != objectid ||
3040                     data_ref->offset != offset) {
3041                         ret = 1;
3042                         break;
3043                 }
3044         }
3045         spin_unlock(&head->lock);
3046         mutex_unlock(&head->mutex);
3047         btrfs_put_transaction(cur_trans);
3048         return ret;
3049 }
3050
3051 static noinline int check_committed_ref(struct btrfs_root *root,
3052                                         struct btrfs_path *path,
3053                                         u64 objectid, u64 offset, u64 bytenr)
3054 {
3055         struct btrfs_fs_info *fs_info = root->fs_info;
3056         struct btrfs_root *extent_root = fs_info->extent_root;
3057         struct extent_buffer *leaf;
3058         struct btrfs_extent_data_ref *ref;
3059         struct btrfs_extent_inline_ref *iref;
3060         struct btrfs_extent_item *ei;
3061         struct btrfs_key key;
3062         u32 item_size;
3063         int type;
3064         int ret;
3065
3066         key.objectid = bytenr;
3067         key.offset = (u64)-1;
3068         key.type = BTRFS_EXTENT_ITEM_KEY;
3069
3070         ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
3071         if (ret < 0)
3072                 goto out;
3073         BUG_ON(ret == 0); /* Corruption */
3074
3075         ret = -ENOENT;
3076         if (path->slots[0] == 0)
3077                 goto out;
3078
3079         path->slots[0]--;
3080         leaf = path->nodes[0];
3081         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
3082
3083         if (key.objectid != bytenr || key.type != BTRFS_EXTENT_ITEM_KEY)
3084                 goto out;
3085
3086         ret = 1;
3087         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
3088         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
3089
3090         if (item_size != sizeof(*ei) +
3091             btrfs_extent_inline_ref_size(BTRFS_EXTENT_DATA_REF_KEY))
3092                 goto out;
3093
3094         if (btrfs_extent_generation(leaf, ei) <=
3095             btrfs_root_last_snapshot(&root->root_item))
3096                 goto out;
3097
3098         iref = (struct btrfs_extent_inline_ref *)(ei + 1);
3099
3100         type = btrfs_get_extent_inline_ref_type(leaf, iref, BTRFS_REF_TYPE_DATA);
3101         if (type != BTRFS_EXTENT_DATA_REF_KEY)
3102                 goto out;
3103
3104         ref = (struct btrfs_extent_data_ref *)(&iref->offset);
3105         if (btrfs_extent_refs(leaf, ei) !=
3106             btrfs_extent_data_ref_count(leaf, ref) ||
3107             btrfs_extent_data_ref_root(leaf, ref) !=
3108             root->root_key.objectid ||
3109             btrfs_extent_data_ref_objectid(leaf, ref) != objectid ||
3110             btrfs_extent_data_ref_offset(leaf, ref) != offset)
3111                 goto out;
3112
3113         ret = 0;
3114 out:
3115         return ret;
3116 }
3117
3118 int btrfs_cross_ref_exist(struct btrfs_root *root, u64 objectid, u64 offset,
3119                           u64 bytenr)
3120 {
3121         struct btrfs_path *path;
3122         int ret;
3123
3124         path = btrfs_alloc_path();
3125         if (!path)
3126                 return -ENOMEM;
3127
3128         do {
3129                 ret = check_committed_ref(root, path, objectid,
3130                                           offset, bytenr);
3131                 if (ret && ret != -ENOENT)
3132                         goto out;
3133
3134                 ret = check_delayed_ref(root, path, objectid, offset, bytenr);
3135         } while (ret == -EAGAIN);
3136
3137 out:
3138         btrfs_free_path(path);
3139         if (root->root_key.objectid == BTRFS_DATA_RELOC_TREE_OBJECTID)
3140                 WARN_ON(ret > 0);
3141         return ret;
3142 }
3143
3144 static int __btrfs_mod_ref(struct btrfs_trans_handle *trans,
3145                            struct btrfs_root *root,
3146                            struct extent_buffer *buf,
3147                            int full_backref, int inc)
3148 {
3149         struct btrfs_fs_info *fs_info = root->fs_info;
3150         u64 bytenr;
3151         u64 num_bytes;
3152         u64 parent;
3153         u64 ref_root;
3154         u32 nritems;
3155         struct btrfs_key key;
3156         struct btrfs_file_extent_item *fi;
3157         int i;
3158         int level;
3159         int ret = 0;
3160         int (*process_func)(struct btrfs_trans_handle *,
3161                             struct btrfs_root *,
3162                             u64, u64, u64, u64, u64, u64);
3163
3164
3165         if (btrfs_is_testing(fs_info))
3166                 return 0;
3167
3168         ref_root = btrfs_header_owner(buf);
3169         nritems = btrfs_header_nritems(buf);
3170         level = btrfs_header_level(buf);
3171
3172         if (!test_bit(BTRFS_ROOT_REF_COWS, &root->state) && level == 0)
3173                 return 0;
3174
3175         if (inc)
3176                 process_func = btrfs_inc_extent_ref;
3177         else
3178                 process_func = btrfs_free_extent;
3179
3180         if (full_backref)
3181                 parent = buf->start;
3182         else
3183                 parent = 0;
3184
3185         for (i = 0; i < nritems; i++) {
3186                 if (level == 0) {
3187                         btrfs_item_key_to_cpu(buf, &key, i);
3188                         if (key.type != BTRFS_EXTENT_DATA_KEY)
3189                                 continue;
3190                         fi = btrfs_item_ptr(buf, i,
3191                                             struct btrfs_file_extent_item);
3192                         if (btrfs_file_extent_type(buf, fi) ==
3193                             BTRFS_FILE_EXTENT_INLINE)
3194                                 continue;
3195                         bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
3196                         if (bytenr == 0)
3197                                 continue;
3198
3199                         num_bytes = btrfs_file_extent_disk_num_bytes(buf, fi);
3200                         key.offset -= btrfs_file_extent_offset(buf, fi);
3201                         ret = process_func(trans, root, bytenr, num_bytes,
3202                                            parent, ref_root, key.objectid,
3203                                            key.offset);
3204                         if (ret)
3205                                 goto fail;
3206                 } else {
3207                         bytenr = btrfs_node_blockptr(buf, i);
3208                         num_bytes = fs_info->nodesize;
3209                         ret = process_func(trans, root, bytenr, num_bytes,
3210                                            parent, ref_root, level - 1, 0);
3211                         if (ret)
3212                                 goto fail;
3213                 }
3214         }
3215         return 0;
3216 fail:
3217         return ret;
3218 }
3219
3220 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
3221                   struct extent_buffer *buf, int full_backref)
3222 {
3223         return __btrfs_mod_ref(trans, root, buf, full_backref, 1);
3224 }
3225
3226 int btrfs_dec_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
3227                   struct extent_buffer *buf, int full_backref)
3228 {
3229         return __btrfs_mod_ref(trans, root, buf, full_backref, 0);
3230 }
3231
3232 static int write_one_cache_group(struct btrfs_trans_handle *trans,
3233                                  struct btrfs_path *path,
3234                                  struct btrfs_block_group_cache *cache)
3235 {
3236         struct btrfs_fs_info *fs_info = trans->fs_info;
3237         int ret;
3238         struct btrfs_root *extent_root = fs_info->extent_root;
3239         unsigned long bi;
3240         struct extent_buffer *leaf;
3241
3242         ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
3243         if (ret) {
3244                 if (ret > 0)
3245                         ret = -ENOENT;
3246                 goto fail;
3247         }
3248
3249         leaf = path->nodes[0];
3250         bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
3251         write_extent_buffer(leaf, &cache->item, bi, sizeof(cache->item));
3252         btrfs_mark_buffer_dirty(leaf);
3253 fail:
3254         btrfs_release_path(path);
3255         return ret;
3256
3257 }
3258
3259 static struct btrfs_block_group_cache *
3260 next_block_group(struct btrfs_fs_info *fs_info,
3261                  struct btrfs_block_group_cache *cache)
3262 {
3263         struct rb_node *node;
3264
3265         spin_lock(&fs_info->block_group_cache_lock);
3266
3267         /* If our block group was removed, we need a full search. */
3268         if (RB_EMPTY_NODE(&cache->cache_node)) {
3269                 const u64 next_bytenr = cache->key.objectid + cache->key.offset;
3270
3271                 spin_unlock(&fs_info->block_group_cache_lock);
3272                 btrfs_put_block_group(cache);
3273                 cache = btrfs_lookup_first_block_group(fs_info, next_bytenr); return cache;
3274         }
3275         node = rb_next(&cache->cache_node);
3276         btrfs_put_block_group(cache);
3277         if (node) {
3278                 cache = rb_entry(node, struct btrfs_block_group_cache,
3279                                  cache_node);
3280                 btrfs_get_block_group(cache);
3281         } else
3282                 cache = NULL;
3283         spin_unlock(&fs_info->block_group_cache_lock);
3284         return cache;
3285 }
3286
3287 static int cache_save_setup(struct btrfs_block_group_cache *block_group,
3288                             struct btrfs_trans_handle *trans,
3289                             struct btrfs_path *path)
3290 {
3291         struct btrfs_fs_info *fs_info = block_group->fs_info;
3292         struct btrfs_root *root = fs_info->tree_root;
3293         struct inode *inode = NULL;
3294         struct extent_changeset *data_reserved = NULL;
3295         u64 alloc_hint = 0;
3296         int dcs = BTRFS_DC_ERROR;
3297         u64 num_pages = 0;
3298         int retries = 0;
3299         int ret = 0;
3300
3301         /*
3302          * If this block group is smaller than 100 megs don't bother caching the
3303          * block group.
3304          */
3305         if (block_group->key.offset < (100 * SZ_1M)) {
3306                 spin_lock(&block_group->lock);
3307                 block_group->disk_cache_state = BTRFS_DC_WRITTEN;
3308                 spin_unlock(&block_group->lock);
3309                 return 0;
3310         }
3311
3312         if (trans->aborted)
3313                 return 0;
3314 again:
3315         inode = lookup_free_space_inode(fs_info, block_group, path);
3316         if (IS_ERR(inode) && PTR_ERR(inode) != -ENOENT) {
3317                 ret = PTR_ERR(inode);
3318                 btrfs_release_path(path);
3319                 goto out;
3320         }
3321
3322         if (IS_ERR(inode)) {
3323                 BUG_ON(retries);
3324                 retries++;
3325
3326                 if (block_group->ro)
3327                         goto out_free;
3328
3329                 ret = create_free_space_inode(trans, block_group, path);
3330                 if (ret)
3331                         goto out_free;
3332                 goto again;
3333         }
3334
3335         /*
3336          * We want to set the generation to 0, that way if anything goes wrong
3337          * from here on out we know not to trust this cache when we load up next
3338          * time.
3339          */
3340         BTRFS_I(inode)->generation = 0;
3341         ret = btrfs_update_inode(trans, root, inode);
3342         if (ret) {
3343                 /*
3344                  * So theoretically we could recover from this, simply set the
3345                  * super cache generation to 0 so we know to invalidate the
3346                  * cache, but then we'd have to keep track of the block groups
3347                  * that fail this way so we know we _have_ to reset this cache
3348                  * before the next commit or risk reading stale cache.  So to
3349                  * limit our exposure to horrible edge cases lets just abort the
3350                  * transaction, this only happens in really bad situations
3351                  * anyway.
3352                  */
3353                 btrfs_abort_transaction(trans, ret);
3354                 goto out_put;
3355         }
3356         WARN_ON(ret);
3357
3358         /* We've already setup this transaction, go ahead and exit */
3359         if (block_group->cache_generation == trans->transid &&
3360             i_size_read(inode)) {
3361                 dcs = BTRFS_DC_SETUP;
3362                 goto out_put;
3363         }
3364
3365         if (i_size_read(inode) > 0) {
3366                 ret = btrfs_check_trunc_cache_free_space(fs_info,
3367                                         &fs_info->global_block_rsv);
3368                 if (ret)
3369                         goto out_put;
3370
3371                 ret = btrfs_truncate_free_space_cache(trans, NULL, inode);
3372                 if (ret)
3373                         goto out_put;
3374         }
3375
3376         spin_lock(&block_group->lock);
3377         if (block_group->cached != BTRFS_CACHE_FINISHED ||
3378             !btrfs_test_opt(fs_info, SPACE_CACHE)) {
3379                 /*
3380                  * don't bother trying to write stuff out _if_
3381                  * a) we're not cached,
3382                  * b) we're with nospace_cache mount option,
3383                  * c) we're with v2 space_cache (FREE_SPACE_TREE).
3384                  */
3385                 dcs = BTRFS_DC_WRITTEN;
3386                 spin_unlock(&block_group->lock);
3387                 goto out_put;
3388         }
3389         spin_unlock(&block_group->lock);
3390
3391         /*
3392          * We hit an ENOSPC when setting up the cache in this transaction, just
3393          * skip doing the setup, we've already cleared the cache so we're safe.
3394          */
3395         if (test_bit(BTRFS_TRANS_CACHE_ENOSPC, &trans->transaction->flags)) {
3396                 ret = -ENOSPC;
3397                 goto out_put;
3398         }
3399
3400         /*
3401          * Try to preallocate enough space based on how big the block group is.
3402          * Keep in mind this has to include any pinned space which could end up
3403          * taking up quite a bit since it's not folded into the other space
3404          * cache.
3405          */
3406         num_pages = div_u64(block_group->key.offset, SZ_256M);
3407         if (!num_pages)
3408                 num_pages = 1;
3409
3410         num_pages *= 16;
3411         num_pages *= PAGE_SIZE;
3412
3413         ret = btrfs_check_data_free_space(inode, &data_reserved, 0, num_pages);
3414         if (ret)
3415                 goto out_put;
3416
3417         ret = btrfs_prealloc_file_range_trans(inode, trans, 0, 0, num_pages,
3418                                               num_pages, num_pages,
3419                                               &alloc_hint);
3420         /*
3421          * Our cache requires contiguous chunks so that we don't modify a bunch
3422          * of metadata or split extents when writing the cache out, which means
3423          * we can enospc if we are heavily fragmented in addition to just normal
3424          * out of space conditions.  So if we hit this just skip setting up any
3425          * other block groups for this transaction, maybe we'll unpin enough
3426          * space the next time around.
3427          */
3428         if (!ret)
3429                 dcs = BTRFS_DC_SETUP;
3430         else if (ret == -ENOSPC)
3431                 set_bit(BTRFS_TRANS_CACHE_ENOSPC, &trans->transaction->flags);
3432
3433 out_put:
3434         iput(inode);
3435 out_free:
3436         btrfs_release_path(path);
3437 out:
3438         spin_lock(&block_group->lock);
3439         if (!ret && dcs == BTRFS_DC_SETUP)
3440                 block_group->cache_generation = trans->transid;
3441         block_group->disk_cache_state = dcs;
3442         spin_unlock(&block_group->lock);
3443
3444         extent_changeset_free(data_reserved);
3445         return ret;
3446 }
3447
3448 int btrfs_setup_space_cache(struct btrfs_trans_handle *trans)
3449 {
3450         struct btrfs_fs_info *fs_info = trans->fs_info;
3451         struct btrfs_block_group_cache *cache, *tmp;
3452         struct btrfs_transaction *cur_trans = trans->transaction;
3453         struct btrfs_path *path;
3454
3455         if (list_empty(&cur_trans->dirty_bgs) ||
3456             !btrfs_test_opt(fs_info, SPACE_CACHE))
3457                 return 0;
3458
3459         path = btrfs_alloc_path();
3460         if (!path)
3461                 return -ENOMEM;
3462
3463         /* Could add new block groups, use _safe just in case */
3464         list_for_each_entry_safe(cache, tmp, &cur_trans->dirty_bgs,
3465                                  dirty_list) {
3466                 if (cache->disk_cache_state == BTRFS_DC_CLEAR)
3467                         cache_save_setup(cache, trans, path);
3468         }
3469
3470         btrfs_free_path(path);
3471         return 0;
3472 }
3473
3474 /*
3475  * transaction commit does final block group cache writeback during a
3476  * critical section where nothing is allowed to change the FS.  This is
3477  * required in order for the cache to actually match the block group,
3478  * but can introduce a lot of latency into the commit.
3479  *
3480  * So, btrfs_start_dirty_block_groups is here to kick off block group
3481  * cache IO.  There's a chance we'll have to redo some of it if the
3482  * block group changes again during the commit, but it greatly reduces
3483  * the commit latency by getting rid of the easy block groups while
3484  * we're still allowing others to join the commit.
3485  */
3486 int btrfs_start_dirty_block_groups(struct btrfs_trans_handle *trans)
3487 {
3488         struct btrfs_fs_info *fs_info = trans->fs_info;
3489         struct btrfs_block_group_cache *cache;
3490         struct btrfs_transaction *cur_trans = trans->transaction;
3491         int ret = 0;
3492         int should_put;
3493         struct btrfs_path *path = NULL;
3494         LIST_HEAD(dirty);
3495         struct list_head *io = &cur_trans->io_bgs;
3496         int num_started = 0;
3497         int loops = 0;
3498
3499         spin_lock(&cur_trans->dirty_bgs_lock);
3500         if (list_empty(&cur_trans->dirty_bgs)) {
3501                 spin_unlock(&cur_trans->dirty_bgs_lock);
3502                 return 0;
3503         }
3504         list_splice_init(&cur_trans->dirty_bgs, &dirty);
3505         spin_unlock(&cur_trans->dirty_bgs_lock);
3506
3507 again:
3508         /*
3509          * make sure all the block groups on our dirty list actually
3510          * exist
3511          */
3512         btrfs_create_pending_block_groups(trans);
3513
3514         if (!path) {
3515                 path = btrfs_alloc_path();
3516                 if (!path)
3517                         return -ENOMEM;
3518         }
3519
3520         /*
3521          * cache_write_mutex is here only to save us from balance or automatic
3522          * removal of empty block groups deleting this block group while we are
3523          * writing out the cache
3524          */
3525         mutex_lock(&trans->transaction->cache_write_mutex);
3526         while (!list_empty(&dirty)) {
3527                 bool drop_reserve = true;
3528
3529                 cache = list_first_entry(&dirty,
3530                                          struct btrfs_block_group_cache,
3531                                          dirty_list);
3532                 /*
3533                  * this can happen if something re-dirties a block
3534                  * group that is already under IO.  Just wait for it to
3535                  * finish and then do it all again
3536                  */
3537                 if (!list_empty(&cache->io_list)) {
3538                         list_del_init(&cache->io_list);
3539                         btrfs_wait_cache_io(trans, cache, path);
3540                         btrfs_put_block_group(cache);
3541                 }
3542
3543
3544                 /*
3545                  * btrfs_wait_cache_io uses the cache->dirty_list to decide
3546                  * if it should update the cache_state.  Don't delete
3547                  * until after we wait.
3548                  *
3549                  * Since we're not running in the commit critical section
3550                  * we need the dirty_bgs_lock to protect from update_block_group
3551                  */
3552                 spin_lock(&cur_trans->dirty_bgs_lock);
3553                 list_del_init(&cache->dirty_list);
3554                 spin_unlock(&cur_trans->dirty_bgs_lock);
3555
3556                 should_put = 1;
3557
3558                 cache_save_setup(cache, trans, path);
3559
3560                 if (cache->disk_cache_state == BTRFS_DC_SETUP) {
3561                         cache->io_ctl.inode = NULL;