fs/btrfs/extent-tree.c

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