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