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