fs/btrfs/extent-tree.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Copyright (C) 2007 Oracle.  All rights reserved.
   4  */
   5
   6 #include <linux/sched.h>
   7 #include <linux/sched/signal.h>
   8 #include <linux/pagemap.h>
   9 #include <linux/writeback.h>
  10 #include <linux/blkdev.h>
  11 #include <linux/sort.h>
  12 #include <linux/rcupdate.h>
  13 #include <linux/kthread.h>
  14 #include <linux/slab.h>
  15 #include <linux/ratelimit.h>
  16 #include <linux/percpu_counter.h>
  17 #include <linux/lockdep.h>
  18 #include <linux/crc32c.h>
  19 #include "misc.h"
  20 #include "tree-log.h"
  21 #include "disk-io.h"
  22 #include "print-tree.h"
  23 #include "volumes.h"
  24 #include "raid56.h"
  25 #include "locking.h"
  26 #include "free-space-cache.h"
  27 #include "free-space-tree.h"
  28 #include "sysfs.h"
  29 #include "qgroup.h"
  30 #include "ref-verify.h"
  31 #include "space-info.h"
  32 #include "block-rsv.h"
  33 #include "delalloc-space.h"
  34 #include "block-group.h"
  35 #include "discard.h"
  36 #include "rcu-string.h"
  37 #include "zoned.h"
  38 #include "dev-replace.h"
  39
  40 #undef SCRAMBLE_DELAYED_REFS
  41
  42
  43 static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
  44                                struct btrfs_delayed_ref_node *node, u64 parent,
  45                                u64 root_objectid, u64 owner_objectid,
  46                                u64 owner_offset, int refs_to_drop,
  47                                struct btrfs_delayed_extent_op *extra_op);
  48 static void __run_delayed_extent_op(struct btrfs_delayed_extent_op *extent_op,
  49                                     struct extent_buffer *leaf,
  50                                     struct btrfs_extent_item *ei);
  51 static int alloc_reserved_file_extent(struct btrfs_trans_handle *trans,
  52                                       u64 parent, u64 root_objectid,
  53                                       u64 flags, u64 owner, u64 offset,
  54                                       struct btrfs_key *ins, int ref_mod);
  55 static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
  56                                      struct btrfs_delayed_ref_node *node,
  57                                      struct btrfs_delayed_extent_op *extent_op);
  58 static int find_next_key(struct btrfs_path *path, int level,
  59                          struct btrfs_key *key);
  60
  61 static int block_group_bits(struct btrfs_block_group *cache, u64 bits)
  62 {
  63         return (cache->flags & bits) == bits;
  64 }
  65
  66 int btrfs_add_excluded_extent(struct btrfs_fs_info *fs_info,
  67                               u64 start, u64 num_bytes)
  68 {
  69         u64 end = start + num_bytes - 1;
  70         set_extent_bits(&fs_info->excluded_extents, start, end,
  71                         EXTENT_UPTODATE);
  72         return 0;
  73 }
  74
  75 void btrfs_free_excluded_extents(struct btrfs_block_group *cache)
  76 {
  77         struct btrfs_fs_info *fs_info = cache->fs_info;
  78         u64 start, end;
  79
  80         start = cache->start;
  81         end = start + cache->length - 1;
  82
  83         clear_extent_bits(&fs_info->excluded_extents, start, end,
  84                           EXTENT_UPTODATE);
  85 }
  86
  87 /* simple helper to search for an existing data extent at a given offset */
  88 int btrfs_lookup_data_extent(struct btrfs_fs_info *fs_info, u64 start, u64 len)
  89 {
  90         struct btrfs_root *root = btrfs_extent_root(fs_info, start);
  91         int ret;
  92         struct btrfs_key key;
  93         struct btrfs_path *path;
  94
  95         path = btrfs_alloc_path();
  96         if (!path)
  97                 return -ENOMEM;
  98
  99         key.objectid = start;
 100         key.offset = len;
 101         key.type = BTRFS_EXTENT_ITEM_KEY;
 102         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 103         btrfs_free_path(path);
 104         return ret;
 105 }
 106
 107 /*
 108  * helper function to lookup reference count and flags of a tree block.
 109  *
 110  * the head node for delayed ref is used to store the sum of all the
 111  * reference count modifications queued up in the rbtree. the head
 112  * node may also store the extent flags to set. This way you can check
 113  * to see what the reference count and extent flags would be if all of
 114  * the delayed refs are not processed.
 115  */
 116 int btrfs_lookup_extent_info(struct btrfs_trans_handle *trans,
 117                              struct btrfs_fs_info *fs_info, u64 bytenr,
 118                              u64 offset, int metadata, u64 *refs, u64 *flags)
 119 {
 120         struct btrfs_root *extent_root;
 121         struct btrfs_delayed_ref_head *head;
 122         struct btrfs_delayed_ref_root *delayed_refs;
 123         struct btrfs_path *path;
 124         struct btrfs_extent_item *ei;
 125         struct extent_buffer *leaf;
 126         struct btrfs_key key;
 127         u32 item_size;
 128         u64 num_refs;
 129         u64 extent_flags;
 130         int ret;
 131
 132         /*
 133          * If we don't have skinny metadata, don't bother doing anything
 134          * different
 135          */
 136         if (metadata && !btrfs_fs_incompat(fs_info, SKINNY_METADATA)) {
 137                 offset = fs_info->nodesize;
 138                 metadata = 0;
 139         }
 140
 141         path = btrfs_alloc_path();
 142         if (!path)
 143                 return -ENOMEM;
 144
 145         if (!trans) {
 146                 path->skip_locking = 1;
 147                 path->search_commit_root = 1;
 148         }
 149
 150 search_again:
 151         key.objectid = bytenr;
 152         key.offset = offset;
 153         if (metadata)
 154                 key.type = BTRFS_METADATA_ITEM_KEY;
 155         else
 156                 key.type = BTRFS_EXTENT_ITEM_KEY;
 157
 158         extent_root = btrfs_extent_root(fs_info, bytenr);
 159         ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
 160         if (ret < 0)
 161                 goto out_free;
 162
 163         if (ret > 0 && metadata && key.type == BTRFS_METADATA_ITEM_KEY) {
 164                 if (path->slots[0]) {
 165                         path->slots[0]--;
 166                         btrfs_item_key_to_cpu(path->nodes[0], &key,
 167                                               path->slots[0]);
 168                         if (key.objectid == bytenr &&
 169                             key.type == BTRFS_EXTENT_ITEM_KEY &&
 170                             key.offset == fs_info->nodesize)
 171                                 ret = 0;
 172                 }
 173         }
 174
 175         if (ret == 0) {
 176                 leaf = path->nodes[0];
 177                 item_size = btrfs_item_size(leaf, path->slots[0]);
 178                 if (item_size >= sizeof(*ei)) {
 179                         ei = btrfs_item_ptr(leaf, path->slots[0],
 180                                             struct btrfs_extent_item);
 181                         num_refs = btrfs_extent_refs(leaf, ei);
 182                         extent_flags = btrfs_extent_flags(leaf, ei);
 183                 } else {
 184                         ret = -EINVAL;
 185                         btrfs_print_v0_err(fs_info);
 186                         if (trans)
 187                                 btrfs_abort_transaction(trans, ret);
 188                         else
 189                                 btrfs_handle_fs_error(fs_info, ret, NULL);
 190
 191                         goto out_free;
 192                 }
 193
 194                 BUG_ON(num_refs == 0);
 195         } else {
 196                 num_refs = 0;
 197                 extent_flags = 0;
 198                 ret = 0;
 199         }
 200
 201         if (!trans)
 202                 goto out;
 203
 204         delayed_refs = &trans->transaction->delayed_refs;
 205         spin_lock(&delayed_refs->lock);
 206         head = btrfs_find_delayed_ref_head(delayed_refs, bytenr);
 207         if (head) {
 208                 if (!mutex_trylock(&head->mutex)) {
 209                         refcount_inc(&head->refs);
 210                         spin_unlock(&delayed_refs->lock);
 211
 212                         btrfs_release_path(path);
 213
 214                         /*
 215                          * Mutex was contended, block until it's released and try
 216                          * again
 217                          */
 218                         mutex_lock(&head->mutex);
 219                         mutex_unlock(&head->mutex);
 220                         btrfs_put_delayed_ref_head(head);
 221                         goto search_again;
 222                 }
 223                 spin_lock(&head->lock);
 224                 if (head->extent_op && head->extent_op->update_flags)
 225                         extent_flags |= head->extent_op->flags_to_set;
 226                 else
 227                         BUG_ON(num_refs == 0);
 228
 229                 num_refs += head->ref_mod;
 230                 spin_unlock(&head->lock);
 231                 mutex_unlock(&head->mutex);
 232         }
 233         spin_unlock(&delayed_refs->lock);
 234 out:
 235         WARN_ON(num_refs == 0);
 236         if (refs)
 237                 *refs = num_refs;
 238         if (flags)
 239                 *flags = extent_flags;
 240 out_free:
 241         btrfs_free_path(path);
 242         return ret;
 243 }
 244
 245 /*
 246  * Back reference rules.  Back refs have three main goals:
 247  *
 248  * 1) differentiate between all holders of references to an extent so that
 249  *    when a reference is dropped we can make sure it was a valid reference
 250  *    before freeing the extent.
 251  *
 252  * 2) Provide enough information to quickly find the holders of an extent
 253  *    if we notice a given block is corrupted or bad.
 254  *
 255  * 3) Make it easy to migrate blocks for FS shrinking or storage pool
 256  *    maintenance.  This is actually the same as #2, but with a slightly
 257  *    different use case.
 258  *
 259  * There are two kinds of back refs. The implicit back refs is optimized
 260  * for pointers in non-shared tree blocks. For a given pointer in a block,
 261  * back refs of this kind provide information about the block's owner tree
 262  * and the pointer's key. These information allow us to find the block by
 263  * b-tree searching. The full back refs is for pointers in tree blocks not
 264  * referenced by their owner trees. The location of tree block is recorded
 265  * in the back refs. Actually the full back refs is generic, and can be
 266  * used in all cases the implicit back refs is used. The major shortcoming
 267  * of the full back refs is its overhead. Every time a tree block gets
 268  * COWed, we have to update back refs entry for all pointers in it.
 269  *
 270  * For a newly allocated tree block, we use implicit back refs for
 271  * pointers in it. This means most tree related operations only involve
 272  * implicit back refs. For a tree block created in old transaction, the
 273  * only way to drop a reference to it is COW it. So we can detect the
 274  * event that tree block loses its owner tree's reference and do the
 275  * back refs conversion.
 276  *
 277  * When a tree block is COWed through a tree, there are four cases:
 278  *
 279  * The reference count of the block is one and the tree is the block's
 280  * owner tree. Nothing to do in this case.
 281  *
 282  * The reference count of the block is one and the tree is not the
 283  * block's owner tree. In this case, full back refs is used for pointers
 284  * in the block. Remove these full back refs, add implicit back refs for
 285  * every pointers in the new block.
 286  *
 287  * The reference count of the block is greater than one and the tree is
 288  * the block's owner tree. In this case, implicit back refs is used for
 289  * pointers in the block. Add full back refs for every pointers in the
 290  * block, increase lower level extents' reference counts. The original
 291  * implicit back refs are entailed to the new block.
 292  *
 293  * The reference count of the block is greater than one and the tree is
 294  * not the block's owner tree. Add implicit back refs for every pointer in
 295  * the new block, increase lower level extents' reference count.
 296  *
 297  * Back Reference Key composing:
 298  *
 299  * The key objectid corresponds to the first byte in the extent,
 300  * The key type is used to differentiate between types of back refs.
 301  * There are different meanings of the key offset for different types
 302  * of back refs.
 303  *
 304  * File extents can be referenced by:
 305  *
 306  * - multiple snapshots, subvolumes, or different generations in one subvol
 307  * - different files inside a single subvolume
 308  * - different offsets inside a file (bookend extents in file.c)
 309  *
 310  * The extent ref structure for the implicit back refs has fields for:
 311  *
 312  * - Objectid of the subvolume root
 313  * - objectid of the file holding the reference
 314  * - original offset in the file
 315  * - how many bookend extents
 316  *
 317  * The key offset for the implicit back refs is hash of the first
 318  * three fields.
 319  *
 320  * The extent ref structure for the full back refs has field for:
 321  *
 322  * - number of pointers in the tree leaf
 323  *
 324  * The key offset for the implicit back refs is the first byte of
 325  * the tree leaf
 326  *
 327  * When a file extent is allocated, The implicit back refs is used.
 328  * the fields are filled in:
 329  *
 330  *     (root_key.objectid, inode objectid, offset in file, 1)
 331  *
 332  * When a file extent is removed file truncation, we find the
 333  * corresponding implicit back refs and check the following fields:
 334  *
 335  *     (btrfs_header_owner(leaf), inode objectid, offset in file)
 336  *
 337  * Btree extents can be referenced by:
 338  *
 339  * - Different subvolumes
 340  *
 341  * Both the implicit back refs and the full back refs for tree blocks
 342  * only consist of key. The key offset for the implicit back refs is
 343  * objectid of block's owner tree. The key offset for the full back refs
 344  * is the first byte of parent block.
 345  *
 346  * When implicit back refs is used, information about the lowest key and
 347  * level of the tree block are required. These information are stored in
 348  * tree block info structure.
 349  */
 350
 351 /*
 352  * is_data == BTRFS_REF_TYPE_BLOCK, tree block type is required,
 353  * is_data == BTRFS_REF_TYPE_DATA, data type is requiried,
 354  * is_data == BTRFS_REF_TYPE_ANY, either type is OK.
 355  */
 356 int btrfs_get_extent_inline_ref_type(const struct extent_buffer *eb,
 357                                      struct btrfs_extent_inline_ref *iref,
 358                                      enum btrfs_inline_ref_type is_data)
 359 {
 360         int type = btrfs_extent_inline_ref_type(eb, iref);
 361         u64 offset = btrfs_extent_inline_ref_offset(eb, iref);
 362
 363         if (type == BTRFS_TREE_BLOCK_REF_KEY ||
 364             type == BTRFS_SHARED_BLOCK_REF_KEY ||
 365             type == BTRFS_SHARED_DATA_REF_KEY ||
 366             type == BTRFS_EXTENT_DATA_REF_KEY) {
 367                 if (is_data == BTRFS_REF_TYPE_BLOCK) {
 368                         if (type == BTRFS_TREE_BLOCK_REF_KEY)
 369                                 return type;
 370                         if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
 371                                 ASSERT(eb->fs_info);
 372                                 /*
 373                                  * Every shared one has parent tree block,
 374                                  * which must be aligned to sector size.
 375                                  */
 376                                 if (offset &&
 377                                     IS_ALIGNED(offset, eb->fs_info->sectorsize))
 378                                         return type;
 379                         }
 380                 } else if (is_data == BTRFS_REF_TYPE_DATA) {
 381                         if (type == BTRFS_EXTENT_DATA_REF_KEY)
 382                                 return type;
 383                         if (type == BTRFS_SHARED_DATA_REF_KEY) {
 384                                 ASSERT(eb->fs_info);
 385                                 /*
 386                                  * Every shared one has parent tree block,
 387                                  * which must be aligned to sector size.
 388                                  */
 389                                 if (offset &&
 390                                     IS_ALIGNED(offset, eb->fs_info->sectorsize))
 391                                         return type;
 392                         }
 393                 } else {
 394                         ASSERT(is_data == BTRFS_REF_TYPE_ANY);
 395                         return type;
 396                 }
 397         }
 398
 399         btrfs_print_leaf((struct extent_buffer *)eb);
 400         btrfs_err(eb->fs_info,
 401                   "eb %llu iref 0x%lx invalid extent inline ref type %d",
 402                   eb->start, (unsigned long)iref, type);
 403         WARN_ON(1);
 404
 405         return BTRFS_REF_TYPE_INVALID;
 406 }
 407
 408 u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset)
 409 {
 410         u32 high_crc = ~(u32)0;
 411         u32 low_crc = ~(u32)0;
 412         __le64 lenum;
 413
 414         lenum = cpu_to_le64(root_objectid);
 415         high_crc = btrfs_crc32c(high_crc, &lenum, sizeof(lenum));
 416         lenum = cpu_to_le64(owner);
 417         low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
 418         lenum = cpu_to_le64(offset);
 419         low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
 420
 421         return ((u64)high_crc << 31) ^ (u64)low_crc;
 422 }
 423
 424 static u64 hash_extent_data_ref_item(struct extent_buffer *leaf,
 425                                      struct btrfs_extent_data_ref *ref)
 426 {
 427         return hash_extent_data_ref(btrfs_extent_data_ref_root(leaf, ref),
 428                                     btrfs_extent_data_ref_objectid(leaf, ref),
 429                                     btrfs_extent_data_ref_offset(leaf, ref));
 430 }
 431
 432 static int match_extent_data_ref(struct extent_buffer *leaf,
 433                                  struct btrfs_extent_data_ref *ref,
 434                                  u64 root_objectid, u64 owner, u64 offset)
 435 {
 436         if (btrfs_extent_data_ref_root(leaf, ref) != root_objectid ||
 437             btrfs_extent_data_ref_objectid(leaf, ref) != owner ||
 438             btrfs_extent_data_ref_offset(leaf, ref) != offset)
 439                 return 0;
 440         return 1;
 441 }
 442
 443 static noinline int lookup_extent_data_ref(struct btrfs_trans_handle *trans,
 444                                            struct btrfs_path *path,
 445                                            u64 bytenr, u64 parent,
 446                                            u64 root_objectid,
 447                                            u64 owner, u64 offset)
 448 {
 449         struct btrfs_root *root = btrfs_extent_root(trans->fs_info, bytenr);
 450         struct btrfs_key key;
 451         struct btrfs_extent_data_ref *ref;
 452         struct extent_buffer *leaf;
 453         u32 nritems;
 454         int ret;
 455         int recow;
 456         int err = -ENOENT;
 457
 458         key.objectid = bytenr;
 459         if (parent) {
 460                 key.type = BTRFS_SHARED_DATA_REF_KEY;
 461                 key.offset = parent;
 462         } else {
 463                 key.type = BTRFS_EXTENT_DATA_REF_KEY;
 464                 key.offset = hash_extent_data_ref(root_objectid,
 465                                                   owner, offset);
 466         }
 467 again:
 468         recow = 0;
 469         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 470         if (ret < 0) {
 471                 err = ret;
 472                 goto fail;
 473         }
 474
 475         if (parent) {
 476                 if (!ret)
 477                         return 0;
 478                 goto fail;
 479         }
 480
 481         leaf = path->nodes[0];
 482         nritems = btrfs_header_nritems(leaf);
 483         while (1) {
 484                 if (path->slots[0] >= nritems) {
 485                         ret = btrfs_next_leaf(root, path);
 486                         if (ret < 0)
 487                                 err = ret;
 488                         if (ret)
 489                                 goto fail;
 490
 491                         leaf = path->nodes[0];
 492                         nritems = btrfs_header_nritems(leaf);
 493                         recow = 1;
 494                 }
 495
 496                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 497                 if (key.objectid != bytenr ||
 498                     key.type != BTRFS_EXTENT_DATA_REF_KEY)
 499                         goto fail;
 500
 501                 ref = btrfs_item_ptr(leaf, path->slots[0],
 502                                      struct btrfs_extent_data_ref);
 503
 504                 if (match_extent_data_ref(leaf, ref, root_objectid,
 505                                           owner, offset)) {
 506                         if (recow) {
 507                                 btrfs_release_path(path);
 508                                 goto again;
 509                         }
 510                         err = 0;
 511                         break;
 512                 }
 513                 path->slots[0]++;
 514         }
 515 fail:
 516         return err;
 517 }
 518
 519 static noinline int insert_extent_data_ref(struct btrfs_trans_handle *trans,
 520                                            struct btrfs_path *path,
 521                                            u64 bytenr, u64 parent,
 522                                            u64 root_objectid, u64 owner,
 523                                            u64 offset, int refs_to_add)
 524 {
 525         struct btrfs_root *root = btrfs_extent_root(trans->fs_info, bytenr);
 526         struct btrfs_key key;
 527         struct extent_buffer *leaf;
 528         u32 size;
 529         u32 num_refs;
 530         int ret;
 531
 532         key.objectid = bytenr;
 533         if (parent) {
 534                 key.type = BTRFS_SHARED_DATA_REF_KEY;
 535                 key.offset = parent;
 536                 size = sizeof(struct btrfs_shared_data_ref);
 537         } else {
 538                 key.type = BTRFS_EXTENT_DATA_REF_KEY;
 539                 key.offset = hash_extent_data_ref(root_objectid,
 540                                                   owner, offset);
 541                 size = sizeof(struct btrfs_extent_data_ref);
 542         }
 543
 544         ret = btrfs_insert_empty_item(trans, root, path, &key, size);
 545         if (ret && ret != -EEXIST)
 546                 goto fail;
 547
 548         leaf = path->nodes[0];
 549         if (parent) {
 550                 struct btrfs_shared_data_ref *ref;
 551                 ref = btrfs_item_ptr(leaf, path->slots[0],
 552                                      struct btrfs_shared_data_ref);
 553                 if (ret == 0) {
 554                         btrfs_set_shared_data_ref_count(leaf, ref, refs_to_add);
 555                 } else {
 556                         num_refs = btrfs_shared_data_ref_count(leaf, ref);
 557                         num_refs += refs_to_add;
 558                         btrfs_set_shared_data_ref_count(leaf, ref, num_refs);
 559                 }
 560         } else {
 561                 struct btrfs_extent_data_ref *ref;
 562                 while (ret == -EEXIST) {
 563                         ref = btrfs_item_ptr(leaf, path->slots[0],
 564                                              struct btrfs_extent_data_ref);
 565                         if (match_extent_data_ref(leaf, ref, root_objectid,
 566                                                   owner, offset))
 567                                 break;
 568                         btrfs_release_path(path);
 569                         key.offset++;
 570                         ret = btrfs_insert_empty_item(trans, root, path, &key,
 571                                                       size);
 572                         if (ret && ret != -EEXIST)
 573                                 goto fail;
 574
 575                         leaf = path->nodes[0];
 576                 }
 577                 ref = btrfs_item_ptr(leaf, path->slots[0],
 578                                      struct btrfs_extent_data_ref);
 579                 if (ret == 0) {
 580                         btrfs_set_extent_data_ref_root(leaf, ref,
 581                                                        root_objectid);
 582                         btrfs_set_extent_data_ref_objectid(leaf, ref, owner);
 583                         btrfs_set_extent_data_ref_offset(leaf, ref, offset);
 584                         btrfs_set_extent_data_ref_count(leaf, ref, refs_to_add);
 585                 } else {
 586                         num_refs = btrfs_extent_data_ref_count(leaf, ref);
 587                         num_refs += refs_to_add;
 588                         btrfs_set_extent_data_ref_count(leaf, ref, num_refs);
 589                 }
 590         }
 591         btrfs_mark_buffer_dirty(leaf);
 592         ret = 0;
 593 fail:
 594         btrfs_release_path(path);
 595         return ret;
 596 }
 597
 598 static noinline int remove_extent_data_ref(struct btrfs_trans_handle *trans,
 599                                            struct btrfs_root *root,
 600                                            struct btrfs_path *path,
 601                                            int refs_to_drop)
 602 {
 603         struct btrfs_key key;
 604         struct btrfs_extent_data_ref *ref1 = NULL;
 605         struct btrfs_shared_data_ref *ref2 = NULL;
 606         struct extent_buffer *leaf;
 607         u32 num_refs = 0;
 608         int ret = 0;
 609
 610         leaf = path->nodes[0];
 611         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 612
 613         if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
 614                 ref1 = btrfs_item_ptr(leaf, path->slots[0],
 615                                       struct btrfs_extent_data_ref);
 616                 num_refs = btrfs_extent_data_ref_count(leaf, ref1);
 617         } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
 618                 ref2 = btrfs_item_ptr(leaf, path->slots[0],
 619                                       struct btrfs_shared_data_ref);
 620                 num_refs = btrfs_shared_data_ref_count(leaf, ref2);
 621         } else if (unlikely(key.type == BTRFS_EXTENT_REF_V0_KEY)) {
 622                 btrfs_print_v0_err(trans->fs_info);
 623                 btrfs_abort_transaction(trans, -EINVAL);
 624                 return -EINVAL;
 625         } else {
 626                 BUG();
 627         }
 628
 629         BUG_ON(num_refs < refs_to_drop);
 630         num_refs -= refs_to_drop;
 631
 632         if (num_refs == 0) {
 633                 ret = btrfs_del_item(trans, root, path);
 634         } else {
 635                 if (key.type == BTRFS_EXTENT_DATA_REF_KEY)
 636                         btrfs_set_extent_data_ref_count(leaf, ref1, num_refs);
 637                 else if (key.type == BTRFS_SHARED_DATA_REF_KEY)
 638                         btrfs_set_shared_data_ref_count(leaf, ref2, num_refs);
 639                 btrfs_mark_buffer_dirty(leaf);
 640         }
 641         return ret;
 642 }
 643
 644 static noinline u32 extent_data_ref_count(struct btrfs_path *path,
 645                                           struct btrfs_extent_inline_ref *iref)
 646 {
 647         struct btrfs_key key;
 648         struct extent_buffer *leaf;
 649         struct btrfs_extent_data_ref *ref1;
 650         struct btrfs_shared_data_ref *ref2;
 651         u32 num_refs = 0;
 652         int type;
 653
 654         leaf = path->nodes[0];
 655         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 656
 657         BUG_ON(key.type == BTRFS_EXTENT_REF_V0_KEY);
 658         if (iref) {
 659                 /*
 660                  * If type is invalid, we should have bailed out earlier than
 661                  * this call.
 662                  */
 663                 type = btrfs_get_extent_inline_ref_type(leaf, iref, BTRFS_REF_TYPE_DATA);
 664                 ASSERT(type != BTRFS_REF_TYPE_INVALID);
 665                 if (type == BTRFS_EXTENT_DATA_REF_KEY) {
 666                         ref1 = (struct btrfs_extent_data_ref *)(&iref->offset);
 667                         num_refs = btrfs_extent_data_ref_count(leaf, ref1);
 668                 } else {
 669                         ref2 = (struct btrfs_shared_data_ref *)(iref + 1);
 670                         num_refs = btrfs_shared_data_ref_count(leaf, ref2);
 671                 }
 672         } else if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
 673                 ref1 = btrfs_item_ptr(leaf, path->slots[0],
 674                                       struct btrfs_extent_data_ref);
 675                 num_refs = btrfs_extent_data_ref_count(leaf, ref1);
 676         } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
 677                 ref2 = btrfs_item_ptr(leaf, path->slots[0],
 678                                       struct btrfs_shared_data_ref);
 679                 num_refs = btrfs_shared_data_ref_count(leaf, ref2);
 680         } else {
 681                 WARN_ON(1);
 682         }
 683         return num_refs;
 684 }
 685
 686 static noinline int lookup_tree_block_ref(struct btrfs_trans_handle *trans,
 687                                           struct btrfs_path *path,
 688                                           u64 bytenr, u64 parent,
 689                                           u64 root_objectid)
 690 {
 691         struct btrfs_root *root = btrfs_extent_root(trans->fs_info, bytenr);
 692         struct btrfs_key key;
 693         int ret;
 694
 695         key.objectid = bytenr;
 696         if (parent) {
 697                 key.type = BTRFS_SHARED_BLOCK_REF_KEY;
 698                 key.offset = parent;
 699         } else {
 700                 key.type = BTRFS_TREE_BLOCK_REF_KEY;
 701                 key.offset = root_objectid;
 702         }
 703
 704         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 705         if (ret > 0)
 706                 ret = -ENOENT;
 707         return ret;
 708 }
 709
 710 static noinline int insert_tree_block_ref(struct btrfs_trans_handle *trans,
 711                                           struct btrfs_path *path,
 712                                           u64 bytenr, u64 parent,
 713                                           u64 root_objectid)
 714 {
 715         struct btrfs_root *root = btrfs_extent_root(trans->fs_info, bytenr);
 716         struct btrfs_key key;
 717         int ret;
 718
 719         key.objectid = bytenr;
 720         if (parent) {
 721                 key.type = BTRFS_SHARED_BLOCK_REF_KEY;
 722                 key.offset = parent;
 723         } else {
 724                 key.type = BTRFS_TREE_BLOCK_REF_KEY;
 725                 key.offset = root_objectid;
 726         }
 727
 728         ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
 729         btrfs_release_path(path);
 730         return ret;
 731 }
 732
 733 static inline int extent_ref_type(u64 parent, u64 owner)
 734 {
 735         int type;
 736         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
 737                 if (parent > 0)
 738                         type = BTRFS_SHARED_BLOCK_REF_KEY;
 739                 else
 740                         type = BTRFS_TREE_BLOCK_REF_KEY;
 741         } else {
 742                 if (parent > 0)
 743                         type = BTRFS_SHARED_DATA_REF_KEY;
 744                 else
 745                         type = BTRFS_EXTENT_DATA_REF_KEY;
 746         }
 747         return type;
 748 }
 749
 750 static int find_next_key(struct btrfs_path *path, int level,
 751                          struct btrfs_key *key)
 752
 753 {
 754         for (; level < BTRFS_MAX_LEVEL; level++) {
 755                 if (!path->nodes[level])
 756                         break;
 757                 if (path->slots[level] + 1 >=
 758                     btrfs_header_nritems(path->nodes[level]))
 759                         continue;
 760                 if (level == 0)
 761                         btrfs_item_key_to_cpu(path->nodes[level], key,
 762                                               path->slots[level] + 1);
 763                 else
 764                         btrfs_node_key_to_cpu(path->nodes[level], key,
 765                                               path->slots[level] + 1);
 766                 return 0;
 767         }
 768         return 1;
 769 }
 770
 771 /*
 772  * look for inline back ref. if back ref is found, *ref_ret is set
 773  * to the address of inline back ref, and 0 is returned.
 774  *
 775  * if back ref isn't found, *ref_ret is set to the address where it
 776  * should be inserted, and -ENOENT is returned.
 777  *
 778  * if insert is true and there are too many inline back refs, the path
 779  * points to the extent item, and -EAGAIN is returned.
 780  *
 781  * NOTE: inline back refs are ordered in the same way that back ref
 782  *       items in the tree are ordered.
 783  */
 784 static noinline_for_stack
 785 int lookup_inline_extent_backref(struct btrfs_trans_handle *trans,
 786                                  struct btrfs_path *path,
 787                                  struct btrfs_extent_inline_ref **ref_ret,
 788                                  u64 bytenr, u64 num_bytes,
 789                                  u64 parent, u64 root_objectid,
 790                                  u64 owner, u64 offset, int insert)
 791 {
 792         struct btrfs_fs_info *fs_info = trans->fs_info;
 793         struct btrfs_root *root = btrfs_extent_root(fs_info, bytenr);
 794         struct btrfs_key key;
 795         struct extent_buffer *leaf;
 796         struct btrfs_extent_item *ei;
 797         struct btrfs_extent_inline_ref *iref;
 798         u64 flags;
 799         u64 item_size;
 800         unsigned long ptr;
 801         unsigned long end;
 802         int extra_size;
 803         int type;
 804         int want;
 805         int ret;
 806         int err = 0;
 807         bool skinny_metadata = btrfs_fs_incompat(fs_info, SKINNY_METADATA);
 808         int needed;
 809
 810         key.objectid = bytenr;
 811         key.type = BTRFS_EXTENT_ITEM_KEY;
 812         key.offset = num_bytes;
 813
 814         want = extent_ref_type(parent, owner);
 815         if (insert) {
 816                 extra_size = btrfs_extent_inline_ref_size(want);
 817                 path->search_for_extension = 1;
 818                 path->keep_locks = 1;
 819         } else
 820                 extra_size = -1;
 821
 822         /*
 823          * Owner is our level, so we can just add one to get the level for the
 824          * block we are interested in.
 825          */
 826         if (skinny_metadata && owner < BTRFS_FIRST_FREE_OBJECTID) {
 827                 key.type = BTRFS_METADATA_ITEM_KEY;
 828                 key.offset = owner;
 829         }
 830
 831 again:
 832         ret = btrfs_search_slot(trans, root, &key, path, extra_size, 1);
 833         if (ret < 0) {
 834                 err = ret;
 835                 goto out;
 836         }
 837
 838         /*
 839          * We may be a newly converted file system which still has the old fat
 840          * extent entries for metadata, so try and see if we have one of those.
 841          */
 842         if (ret > 0 && skinny_metadata) {
 843                 skinny_metadata = false;
 844                 if (path->slots[0]) {
 845                         path->slots[0]--;
 846                         btrfs_item_key_to_cpu(path->nodes[0], &key,
 847                                               path->slots[0]);
 848                         if (key.objectid == bytenr &&
 849                             key.type == BTRFS_EXTENT_ITEM_KEY &&
 850                             key.offset == num_bytes)
 851                                 ret = 0;
 852                 }
 853                 if (ret) {
 854                         key.objectid = bytenr;
 855                         key.type = BTRFS_EXTENT_ITEM_KEY;
 856                         key.offset = num_bytes;
 857                         btrfs_release_path(path);
 858                         goto again;
 859                 }
 860         }
 861
 862         if (ret && !insert) {
 863                 err = -ENOENT;
 864                 goto out;
 865         } else if (WARN_ON(ret)) {
 866                 err = -EIO;
 867                 goto out;
 868         }
 869
 870         leaf = path->nodes[0];
 871         item_size = btrfs_item_size(leaf, path->slots[0]);
 872         if (unlikely(item_size < sizeof(*ei))) {
 873                 err = -EINVAL;
 874                 btrfs_print_v0_err(fs_info);
 875                 btrfs_abort_transaction(trans, err);
 876                 goto out;
 877         }
 878
 879         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
 880         flags = btrfs_extent_flags(leaf, ei);
 881
 882         ptr = (unsigned long)(ei + 1);
 883         end = (unsigned long)ei + item_size;
 884
 885         if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK && !skinny_metadata) {
 886                 ptr += sizeof(struct btrfs_tree_block_info);
 887                 BUG_ON(ptr > end);
 888         }
 889
 890         if (owner >= BTRFS_FIRST_FREE_OBJECTID)
 891                 needed = BTRFS_REF_TYPE_DATA;
 892         else
 893                 needed = BTRFS_REF_TYPE_BLOCK;
 894
 895         err = -ENOENT;
 896         while (1) {
 897                 if (ptr >= end) {
 898                         WARN_ON(ptr > end);
 899                         break;
 900                 }
 901                 iref = (struct btrfs_extent_inline_ref *)ptr;
 902                 type = btrfs_get_extent_inline_ref_type(leaf, iref, needed);
 903                 if (type == BTRFS_REF_TYPE_INVALID) {
 904                         err = -EUCLEAN;
 905                         goto out;
 906                 }
 907
 908                 if (want < type)
 909                         break;
 910                 if (want > type) {
 911                         ptr += btrfs_extent_inline_ref_size(type);
 912                         continue;
 913                 }
 914
 915                 if (type == BTRFS_EXTENT_DATA_REF_KEY) {
 916                         struct btrfs_extent_data_ref *dref;
 917                         dref = (struct btrfs_extent_data_ref *)(&iref->offset);
 918                         if (match_extent_data_ref(leaf, dref, root_objectid,
 919                                                   owner, offset)) {
 920                                 err = 0;
 921                                 break;
 922                         }
 923                         if (hash_extent_data_ref_item(leaf, dref) <
 924                             hash_extent_data_ref(root_objectid, owner, offset))
 925                                 break;
 926                 } else {
 927                         u64 ref_offset;
 928                         ref_offset = btrfs_extent_inline_ref_offset(leaf, iref);
 929                         if (parent > 0) {
 930                                 if (parent == ref_offset) {
 931                                         err = 0;
 932                                         break;
 933                                 }
 934                                 if (ref_offset < parent)
 935                                         break;
 936                         } else {
 937                                 if (root_objectid == ref_offset) {
 938                                         err = 0;
 939                                         break;
 940                                 }
 941                                 if (ref_offset < root_objectid)
 942                                         break;
 943                         }
 944                 }
 945                 ptr += btrfs_extent_inline_ref_size(type);
 946         }
 947         if (err == -ENOENT && insert) {
 948                 if (item_size + extra_size >=
 949                     BTRFS_MAX_EXTENT_ITEM_SIZE(root)) {
 950                         err = -EAGAIN;
 951                         goto out;
 952                 }
 953                 /*
 954                  * To add new inline back ref, we have to make sure
 955                  * there is no corresponding back ref item.
 956                  * For simplicity, we just do not add new inline back
 957                  * ref if there is any kind of item for this block
 958                  */
 959                 if (find_next_key(path, 0, &key) == 0 &&
 960                     key.objectid == bytenr &&
 961                     key.type < BTRFS_BLOCK_GROUP_ITEM_KEY) {
 962                         err = -EAGAIN;
 963                         goto out;
 964                 }
 965         }
 966         *ref_ret = (struct btrfs_extent_inline_ref *)ptr;
 967 out:
 968         if (insert) {
 969                 path->keep_locks = 0;
 970                 path->search_for_extension = 0;
 971                 btrfs_unlock_up_safe(path, 1);
 972         }
 973         return err;
 974 }
 975
 976 /*
 977  * helper to add new inline back ref
 978  */
 979 static noinline_for_stack
 980 void setup_inline_extent_backref(struct btrfs_fs_info *fs_info,
 981                                  struct btrfs_path *path,
 982                                  struct btrfs_extent_inline_ref *iref,
 983                                  u64 parent, u64 root_objectid,
 984                                  u64 owner, u64 offset, int refs_to_add,
 985                                  struct btrfs_delayed_extent_op *extent_op)
 986 {
 987         struct extent_buffer *leaf;
 988         struct btrfs_extent_item *ei;
 989         unsigned long ptr;
 990         unsigned long end;
 991         unsigned long item_offset;
 992         u64 refs;
 993         int size;
 994         int type;
 995
 996         leaf = path->nodes[0];
 997         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
 998         item_offset = (unsigned long)iref - (unsigned long)ei;
 999
1000         type = extent_ref_type(parent, owner);
1001         size = btrfs_extent_inline_ref_size(type);
1002
1003         btrfs_extend_item(path, size);
1004
1005         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1006         refs = btrfs_extent_refs(leaf, ei);
1007         refs += refs_to_add;
1008         btrfs_set_extent_refs(leaf, ei, refs);
1009         if (extent_op)
1010                 __run_delayed_extent_op(extent_op, leaf, ei);
1011
1012         ptr = (unsigned long)ei + item_offset;
1013         end = (unsigned long)ei + btrfs_item_size(leaf, path->slots[0]);
1014         if (ptr < end - size)
1015                 memmove_extent_buffer(leaf, ptr + size, ptr,
1016                                       end - size - ptr);
1017
1018         iref = (struct btrfs_extent_inline_ref *)ptr;
1019         btrfs_set_extent_inline_ref_type(leaf, iref, type);
1020         if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1021                 struct btrfs_extent_data_ref *dref;
1022                 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1023                 btrfs_set_extent_data_ref_root(leaf, dref, root_objectid);
1024                 btrfs_set_extent_data_ref_objectid(leaf, dref, owner);
1025                 btrfs_set_extent_data_ref_offset(leaf, dref, offset);
1026                 btrfs_set_extent_data_ref_count(leaf, dref, refs_to_add);
1027         } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
1028                 struct btrfs_shared_data_ref *sref;
1029                 sref = (struct btrfs_shared_data_ref *)(iref + 1);
1030                 btrfs_set_shared_data_ref_count(leaf, sref, refs_to_add);
1031                 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
1032         } else if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
1033                 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
1034         } else {
1035                 btrfs_set_extent_inline_ref_offset(leaf, iref, root_objectid);
1036         }
1037         btrfs_mark_buffer_dirty(leaf);
1038 }
1039
1040 static int lookup_extent_backref(struct btrfs_trans_handle *trans,
1041                                  struct btrfs_path *path,
1042                                  struct btrfs_extent_inline_ref **ref_ret,
1043                                  u64 bytenr, u64 num_bytes, u64 parent,
1044                                  u64 root_objectid, u64 owner, u64 offset)
1045 {
1046         int ret;
1047
1048         ret = lookup_inline_extent_backref(trans, path, ref_ret, bytenr,
1049                                            num_bytes, parent, root_objectid,
1050                                            owner, offset, 0);
1051         if (ret != -ENOENT)
1052                 return ret;
1053
1054         btrfs_release_path(path);
1055         *ref_ret = NULL;
1056
1057         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1058                 ret = lookup_tree_block_ref(trans, path, bytenr, parent,
1059                                             root_objectid);
1060         } else {
1061                 ret = lookup_extent_data_ref(trans, path, bytenr, parent,
1062                                              root_objectid, owner, offset);
1063         }
1064         return ret;
1065 }
1066
1067 /*
1068  * helper to update/remove inline back ref
1069  */
1070 static noinline_for_stack
1071 void update_inline_extent_backref(struct btrfs_path *path,
1072                                   struct btrfs_extent_inline_ref *iref,
1073                                   int refs_to_mod,
1074                                   struct btrfs_delayed_extent_op *extent_op)
1075 {
1076         struct extent_buffer *leaf = path->nodes[0];
1077         struct btrfs_extent_item *ei;
1078         struct btrfs_extent_data_ref *dref = NULL;
1079         struct btrfs_shared_data_ref *sref = NULL;
1080         unsigned long ptr;
1081         unsigned long end;
1082         u32 item_size;
1083         int size;
1084         int type;
1085         u64 refs;
1086
1087         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1088         refs = btrfs_extent_refs(leaf, ei);
1089         WARN_ON(refs_to_mod < 0 && refs + refs_to_mod <= 0);
1090         refs += refs_to_mod;
1091         btrfs_set_extent_refs(leaf, ei, refs);
1092         if (extent_op)
1093                 __run_delayed_extent_op(extent_op, leaf, ei);
1094
1095         /*
1096          * If type is invalid, we should have bailed out after
1097          * lookup_inline_extent_backref().
1098          */
1099         type = btrfs_get_extent_inline_ref_type(leaf, iref, BTRFS_REF_TYPE_ANY);
1100         ASSERT(type != BTRFS_REF_TYPE_INVALID);
1101
1102         if (type == BTRFS_EXTENT_DATA_REF_KEY) {
1103                 dref = (struct btrfs_extent_data_ref *)(&iref->offset);
1104                 refs = btrfs_extent_data_ref_count(leaf, dref);
1105         } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
1106                 sref = (struct btrfs_shared_data_ref *)(iref + 1);
1107                 refs = btrfs_shared_data_ref_count(leaf, sref);
1108         } else {
1109                 refs = 1;
1110                 BUG_ON(refs_to_mod != -1);
1111         }
1112
1113         BUG_ON(refs_to_mod < 0 && refs < -refs_to_mod);
1114         refs += refs_to_mod;
1115
1116         if (refs > 0) {
1117                 if (type == BTRFS_EXTENT_DATA_REF_KEY)
1118                         btrfs_set_extent_data_ref_count(leaf, dref, refs);
1119                 else
1120                         btrfs_set_shared_data_ref_count(leaf, sref, refs);
1121         } else {
1122                 size =  btrfs_extent_inline_ref_size(type);
1123                 item_size = btrfs_item_size(leaf, path->slots[0]);
1124                 ptr = (unsigned long)iref;
1125                 end = (unsigned long)ei + item_size;
1126                 if (ptr + size < end)
1127                         memmove_extent_buffer(leaf, ptr, ptr + size,
1128                                               end - ptr - size);
1129                 item_size -= size;
1130                 btrfs_truncate_item(path, item_size, 1);
1131         }
1132         btrfs_mark_buffer_dirty(leaf);
1133 }
1134
1135 static noinline_for_stack
1136 int insert_inline_extent_backref(struct btrfs_trans_handle *trans,
1137                                  struct btrfs_path *path,
1138                                  u64 bytenr, u64 num_bytes, u64 parent,
1139                                  u64 root_objectid, u64 owner,
1140                                  u64 offset, int refs_to_add,
1141                                  struct btrfs_delayed_extent_op *extent_op)
1142 {
1143         struct btrfs_extent_inline_ref *iref;
1144         int ret;
1145
1146         ret = lookup_inline_extent_backref(trans, path, &iref, bytenr,
1147                                            num_bytes, parent, root_objectid,
1148                                            owner, offset, 1);
1149         if (ret == 0) {
1150                 /*
1151                  * We're adding refs to a tree block we already own, this
1152                  * should not happen at all.
1153                  */
1154                 if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1155                         btrfs_crit(trans->fs_info,
1156 "adding refs to an existing tree ref, bytenr %llu num_bytes %llu root_objectid %llu",
1157                                    bytenr, num_bytes, root_objectid);
1158                         if (IS_ENABLED(CONFIG_BTRFS_DEBUG)) {
1159                                 WARN_ON(1);
1160                                 btrfs_crit(trans->fs_info,
1161                         "path->slots[0]=%d path->nodes[0]:", path->slots[0]);
1162                                 btrfs_print_leaf(path->nodes[0]);
1163                         }
1164                         return -EUCLEAN;
1165                 }
1166                 update_inline_extent_backref(path, iref, refs_to_add, extent_op);
1167         } else if (ret == -ENOENT) {
1168                 setup_inline_extent_backref(trans->fs_info, path, iref, parent,
1169                                             root_objectid, owner, offset,
1170                                             refs_to_add, extent_op);
1171                 ret = 0;
1172         }
1173         return ret;
1174 }
1175
1176 static int remove_extent_backref(struct btrfs_trans_handle *trans,
1177                                  struct btrfs_root *root,
1178                                  struct btrfs_path *path,
1179                                  struct btrfs_extent_inline_ref *iref,
1180                                  int refs_to_drop, int is_data)
1181 {
1182         int ret = 0;
1183
1184         BUG_ON(!is_data && refs_to_drop != 1);
1185         if (iref)
1186                 update_inline_extent_backref(path, iref, -refs_to_drop, NULL);
1187         else if (is_data)
1188                 ret = remove_extent_data_ref(trans, root, path, refs_to_drop);
1189         else
1190                 ret = btrfs_del_item(trans, root, path);
1191         return ret;
1192 }
1193
1194 static int btrfs_issue_discard(struct block_device *bdev, u64 start, u64 len,
1195                                u64 *discarded_bytes)
1196 {
1197         int j, ret = 0;
1198         u64 bytes_left, end;
1199         u64 aligned_start = ALIGN(start, 1 << 9);
1200
1201         if (WARN_ON(start != aligned_start)) {
1202                 len -= aligned_start - start;
1203                 len = round_down(len, 1 << 9);
1204                 start = aligned_start;
1205         }
1206
1207         *discarded_bytes = 0;
1208
1209         if (!len)
1210                 return 0;
1211
1212         end = start + len;
1213         bytes_left = len;
1214
1215         /* Skip any superblocks on this device. */
1216         for (j = 0; j < BTRFS_SUPER_MIRROR_MAX; j++) {
1217                 u64 sb_start = btrfs_sb_offset(j);
1218                 u64 sb_end = sb_start + BTRFS_SUPER_INFO_SIZE;
1219                 u64 size = sb_start - start;
1220
1221                 if (!in_range(sb_start, start, bytes_left) &&
1222                     !in_range(sb_end, start, bytes_left) &&
1223                     !in_range(start, sb_start, BTRFS_SUPER_INFO_SIZE))
1224                         continue;
1225
1226                 /*
1227                  * Superblock spans beginning of range.  Adjust start and
1228                  * try again.
1229                  */
1230                 if (sb_start <= start) {
1231                         start += sb_end - start;
1232                         if (start > end) {
1233                                 bytes_left = 0;
1234                                 break;
1235                         }
1236                         bytes_left = end - start;
1237                         continue;
1238                 }
1239
1240                 if (size) {
1241                         ret = blkdev_issue_discard(bdev, start >> 9, size >> 9,
1242                                                    GFP_NOFS, 0);
1243                         if (!ret)
1244                                 *discarded_bytes += size;
1245                         else if (ret != -EOPNOTSUPP)
1246                                 return ret;
1247                 }
1248
1249                 start = sb_end;
1250                 if (start > end) {
1251                         bytes_left = 0;
1252                         break;
1253                 }
1254                 bytes_left = end - start;
1255         }
1256
1257         if (bytes_left) {
1258                 ret = blkdev_issue_discard(bdev, start >> 9, bytes_left >> 9,
1259                                            GFP_NOFS, 0);
1260                 if (!ret)
1261                         *discarded_bytes += bytes_left;
1262         }
1263         return ret;
1264 }
1265
1266 static int do_discard_extent(struct btrfs_io_stripe *stripe, u64 *bytes)
1267 {
1268         struct btrfs_device *dev = stripe->dev;
1269         struct btrfs_fs_info *fs_info = dev->fs_info;
1270         struct btrfs_dev_replace *dev_replace = &fs_info->dev_replace;
1271         u64 phys = stripe->physical;
1272         u64 len = stripe->length;
1273         u64 discarded = 0;
1274         int ret = 0;
1275
1276         /* Zone reset on a zoned filesystem */
1277         if (btrfs_can_zone_reset(dev, phys, len)) {
1278                 u64 src_disc;
1279
1280                 ret = btrfs_reset_device_zone(dev, phys, len, &discarded);
1281                 if (ret)
1282                         goto out;
1283
1284                 if (!btrfs_dev_replace_is_ongoing(dev_replace) ||
1285                     dev != dev_replace->srcdev)
1286                         goto out;
1287
1288                 src_disc = discarded;
1289
1290                 /* Send to replace target as well */
1291                 ret = btrfs_reset_device_zone(dev_replace->tgtdev, phys, len,
1292                                               &discarded);
1293                 discarded += src_disc;
1294         } else if (blk_queue_discard(bdev_get_queue(stripe->dev->bdev))) {
1295                 ret = btrfs_issue_discard(dev->bdev, phys, len, &discarded);
1296         } else {
1297                 ret = 0;
1298                 *bytes = 0;
1299         }
1300
1301 out:
1302         *bytes = discarded;
1303         return ret;
1304 }
1305
1306 int btrfs_discard_extent(struct btrfs_fs_info *fs_info, u64 bytenr,
1307                          u64 num_bytes, u64 *actual_bytes)
1308 {
1309         int ret = 0;
1310         u64 discarded_bytes = 0;
1311         u64 end = bytenr + num_bytes;
1312         u64 cur = bytenr;
1313         struct btrfs_io_context *bioc = NULL;
1314
1315         /*
1316          * Avoid races with device replace and make sure our bioc has devices
1317          * associated to its stripes that don't go away while we are discarding.
1318          */
1319         btrfs_bio_counter_inc_blocked(fs_info);
1320         while (cur < end) {
1321                 struct btrfs_io_stripe *stripe;
1322                 int i;
1323
1324                 num_bytes = end - cur;
1325                 /* Tell the block device(s) that the sectors can be discarded */
1326                 ret = btrfs_map_block(fs_info, BTRFS_MAP_DISCARD, cur,
1327                                       &num_bytes, &bioc, 0);
1328                 /*
1329                  * Error can be -ENOMEM, -ENOENT (no such chunk mapping) or
1330                  * -EOPNOTSUPP. For any such error, @num_bytes is not updated,
1331                  * thus we can't continue anyway.
1332                  */
1333                 if (ret < 0)
1334                         goto out;
1335
1336                 stripe = bioc->stripes;
1337                 for (i = 0; i < bioc->num_stripes; i++, stripe++) {
1338                         u64 bytes;
1339                         struct btrfs_device *device = stripe->dev;
1340
1341                         if (!device->bdev) {
1342                                 ASSERT(btrfs_test_opt(fs_info, DEGRADED));
1343                                 continue;
1344                         }
1345
1346                         if (!test_bit(BTRFS_DEV_STATE_WRITEABLE, &device->dev_state))
1347                                 continue;
1348
1349                         ret = do_discard_extent(stripe, &bytes);
1350                         if (!ret) {
1351                                 discarded_bytes += bytes;
1352                         } else if (ret != -EOPNOTSUPP) {
1353                                 /*
1354                                  * Logic errors or -ENOMEM, or -EIO, but
1355                                  * unlikely to happen.
1356                                  *
1357                                  * And since there are two loops, explicitly
1358                                  * go to out to avoid confusion.
1359                                  */
1360                                 btrfs_put_bioc(bioc);
1361                                 goto out;
1362                         }
1363
1364                         /*
1365                          * Just in case we get back EOPNOTSUPP for some reason,
1366                          * just ignore the return value so we don't screw up
1367                          * people calling discard_extent.
1368                          */
1369                         ret = 0;
1370                 }
1371                 btrfs_put_bioc(bioc);
1372                 cur += num_bytes;
1373         }
1374 out:
1375         btrfs_bio_counter_dec(fs_info);
1376
1377         if (actual_bytes)
1378                 *actual_bytes = discarded_bytes;
1379
1380
1381         if (ret == -EOPNOTSUPP)
1382                 ret = 0;
1383         return ret;
1384 }
1385
1386 /* Can return -ENOMEM */
1387 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
1388                          struct btrfs_ref *generic_ref)
1389 {
1390         struct btrfs_fs_info *fs_info = trans->fs_info;
1391         int ret;
1392
1393         ASSERT(generic_ref->type != BTRFS_REF_NOT_SET &&
1394                generic_ref->action);
1395         BUG_ON(generic_ref->type == BTRFS_REF_METADATA &&
1396                generic_ref->tree_ref.owning_root == BTRFS_TREE_LOG_OBJECTID);
1397
1398         if (generic_ref->type == BTRFS_REF_METADATA)
1399                 ret = btrfs_add_delayed_tree_ref(trans, generic_ref, NULL);
1400         else
1401                 ret = btrfs_add_delayed_data_ref(trans, generic_ref, 0);
1402
1403         btrfs_ref_tree_mod(fs_info, generic_ref);
1404
1405         return ret;
1406 }
1407
1408 /*
1409  * __btrfs_inc_extent_ref - insert backreference for a given extent
1410  *
1411  * The counterpart is in __btrfs_free_extent(), with examples and more details
1412  * how it works.
1413  *
1414  * @trans:          Handle of transaction
1415  *
1416  * @node:           The delayed ref node used to get the bytenr/length for
1417  *                  extent whose references are incremented.
1418  *
1419  * @parent:         If this is a shared extent (BTRFS_SHARED_DATA_REF_KEY/
1420  *                  BTRFS_SHARED_BLOCK_REF_KEY) then it holds the logical
1421  *                  bytenr of the parent block. Since new extents are always
1422  *                  created with indirect references, this will only be the case
1423  *                  when relocating a shared extent. In that case, root_objectid
1424  *                  will be BTRFS_TREE_RELOC_OBJECTID. Otherwise, parent must
1425  *                  be 0
1426  *
1427  * @root_objectid:  The id of the root where this modification has originated,
1428  *                  this can be either one of the well-known metadata trees or
1429  *                  the subvolume id which references this extent.
1430  *
1431  * @owner:          For data extents it is the inode number of the owning file.
1432  *                  For metadata extents this parameter holds the level in the
1433  *                  tree of the extent.
1434  *
1435  * @offset:         For metadata extents the offset is ignored and is currently
1436  *                  always passed as 0. For data extents it is the fileoffset
1437  *                  this extent belongs to.
1438  *
1439  * @refs_to_add     Number of references to add
1440  *
1441  * @extent_op       Pointer to a structure, holding information necessary when
1442  *                  updating a tree block's flags
1443  *
1444  */
1445 static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
1446                                   struct btrfs_delayed_ref_node *node,
1447                                   u64 parent, u64 root_objectid,
1448                                   u64 owner, u64 offset, int refs_to_add,
1449                                   struct btrfs_delayed_extent_op *extent_op)
1450 {
1451         struct btrfs_path *path;
1452         struct extent_buffer *leaf;
1453         struct btrfs_extent_item *item;
1454         struct btrfs_key key;
1455         u64 bytenr = node->bytenr;
1456         u64 num_bytes = node->num_bytes;
1457         u64 refs;
1458         int ret;
1459
1460         path = btrfs_alloc_path();
1461         if (!path)
1462                 return -ENOMEM;
1463
1464         /* this will setup the path even if it fails to insert the back ref */
1465         ret = insert_inline_extent_backref(trans, path, bytenr, num_bytes,
1466                                            parent, root_objectid, owner,
1467                                            offset, refs_to_add, extent_op);
1468         if ((ret < 0 && ret != -EAGAIN) || !ret)
1469                 goto out;
1470
1471         /*
1472          * Ok we had -EAGAIN which means we didn't have space to insert and
1473          * inline extent ref, so just update the reference count and add a
1474          * normal backref.
1475          */
1476         leaf = path->nodes[0];
1477         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
1478         item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1479         refs = btrfs_extent_refs(leaf, item);
1480         btrfs_set_extent_refs(leaf, item, refs + refs_to_add);
1481         if (extent_op)
1482                 __run_delayed_extent_op(extent_op, leaf, item);
1483
1484         btrfs_mark_buffer_dirty(leaf);
1485         btrfs_release_path(path);
1486
1487         /* now insert the actual backref */
1488         if (owner < BTRFS_FIRST_FREE_OBJECTID) {
1489                 BUG_ON(refs_to_add != 1);
1490                 ret = insert_tree_block_ref(trans, path, bytenr, parent,
1491                                             root_objectid);
1492         } else {
1493                 ret = insert_extent_data_ref(trans, path, bytenr, parent,
1494                                              root_objectid, owner, offset,
1495                                              refs_to_add);
1496         }
1497         if (ret)
1498                 btrfs_abort_transaction(trans, ret);
1499 out:
1500         btrfs_free_path(path);
1501         return ret;
1502 }
1503
1504 static int run_delayed_data_ref(struct btrfs_trans_handle *trans,
1505                                 struct btrfs_delayed_ref_node *node,
1506                                 struct btrfs_delayed_extent_op *extent_op,
1507                                 int insert_reserved)
1508 {
1509         int ret = 0;
1510         struct btrfs_delayed_data_ref *ref;
1511         struct btrfs_key ins;
1512         u64 parent = 0;
1513         u64 ref_root = 0;
1514         u64 flags = 0;
1515
1516         ins.objectid = node->bytenr;
1517         ins.offset = node->num_bytes;
1518         ins.type = BTRFS_EXTENT_ITEM_KEY;
1519
1520         ref = btrfs_delayed_node_to_data_ref(node);
1521         trace_run_delayed_data_ref(trans->fs_info, node, ref, node->action);
1522
1523         if (node->type == BTRFS_SHARED_DATA_REF_KEY)
1524                 parent = ref->parent;
1525         ref_root = ref->root;
1526
1527         if (node->action == BTRFS_ADD_DELAYED_REF && insert_reserved) {
1528                 if (extent_op)
1529                         flags |= extent_op->flags_to_set;
1530                 ret = alloc_reserved_file_extent(trans, parent, ref_root,
1531                                                  flags, ref->objectid,
1532                                                  ref->offset, &ins,
1533                                                  node->ref_mod);
1534         } else if (node->action == BTRFS_ADD_DELAYED_REF) {
1535                 ret = __btrfs_inc_extent_ref(trans, node, parent, ref_root,
1536                                              ref->objectid, ref->offset,
1537                                              node->ref_mod, extent_op);
1538         } else if (node->action == BTRFS_DROP_DELAYED_REF) {
1539                 ret = __btrfs_free_extent(trans, node, parent,
1540                                           ref_root, ref->objectid,
1541                                           ref->offset, node->ref_mod,
1542                                           extent_op);
1543         } else {
1544                 BUG();
1545         }
1546         return ret;
1547 }
1548
1549 static void __run_delayed_extent_op(struct btrfs_delayed_extent_op *extent_op,
1550                                     struct extent_buffer *leaf,
1551                                     struct btrfs_extent_item *ei)
1552 {
1553         u64 flags = btrfs_extent_flags(leaf, ei);
1554         if (extent_op->update_flags) {
1555                 flags |= extent_op->flags_to_set;
1556                 btrfs_set_extent_flags(leaf, ei, flags);
1557         }
1558
1559         if (extent_op->update_key) {
1560                 struct btrfs_tree_block_info *bi;
1561                 BUG_ON(!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK));
1562                 bi = (struct btrfs_tree_block_info *)(ei + 1);
1563                 btrfs_set_tree_block_key(leaf, bi, &extent_op->key);
1564         }
1565 }
1566
1567 static int run_delayed_extent_op(struct btrfs_trans_handle *trans,
1568                                  struct btrfs_delayed_ref_head *head,
1569                                  struct btrfs_delayed_extent_op *extent_op)
1570 {
1571         struct btrfs_fs_info *fs_info = trans->fs_info;
1572         struct btrfs_root *root;
1573         struct btrfs_key key;
1574         struct btrfs_path *path;
1575         struct btrfs_extent_item *ei;
1576         struct extent_buffer *leaf;
1577         u32 item_size;
1578         int ret;
1579         int err = 0;
1580         int metadata = !extent_op->is_data;
1581
1582         if (TRANS_ABORTED(trans))
1583                 return 0;
1584
1585         if (metadata && !btrfs_fs_incompat(fs_info, SKINNY_METADATA))
1586                 metadata = 0;
1587
1588         path = btrfs_alloc_path();
1589         if (!path)
1590                 return -ENOMEM;
1591
1592         key.objectid = head->bytenr;
1593
1594         if (metadata) {
1595                 key.type = BTRFS_METADATA_ITEM_KEY;
1596                 key.offset = extent_op->level;
1597         } else {
1598                 key.type = BTRFS_EXTENT_ITEM_KEY;
1599                 key.offset = head->num_bytes;
1600         }
1601
1602         root = btrfs_extent_root(fs_info, key.objectid);
1603 again:
1604         ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
1605         if (ret < 0) {
1606                 err = ret;
1607                 goto out;
1608         }
1609         if (ret > 0) {
1610                 if (metadata) {
1611                         if (path->slots[0] > 0) {
1612                                 path->slots[0]--;
1613                                 btrfs_item_key_to_cpu(path->nodes[0], &key,
1614                                                       path->slots[0]);
1615                                 if (key.objectid == head->bytenr &&
1616                                     key.type == BTRFS_EXTENT_ITEM_KEY &&
1617                                     key.offset == head->num_bytes)
1618                                         ret = 0;
1619                         }
1620                         if (ret > 0) {
1621                                 btrfs_release_path(path);
1622                                 metadata = 0;
1623
1624                                 key.objectid = head->bytenr;
1625                                 key.offset = head->num_bytes;
1626                                 key.type = BTRFS_EXTENT_ITEM_KEY;
1627                                 goto again;
1628                         }
1629                 } else {
1630                         err = -EIO;
1631                         goto out;
1632                 }
1633         }
1634
1635         leaf = path->nodes[0];
1636         item_size = btrfs_item_size(leaf, path->slots[0]);
1637
1638         if (unlikely(item_size < sizeof(*ei))) {
1639                 err = -EINVAL;
1640                 btrfs_print_v0_err(fs_info);
1641                 btrfs_abort_transaction(trans, err);
1642                 goto out;
1643         }
1644
1645         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
1646         __run_delayed_extent_op(extent_op, leaf, ei);
1647
1648         btrfs_mark_buffer_dirty(leaf);
1649 out:
1650         btrfs_free_path(path);
1651         return err;
1652 }
1653
1654 static int run_delayed_tree_ref(struct btrfs_trans_handle *trans,
1655                                 struct btrfs_delayed_ref_node *node,
1656                                 struct btrfs_delayed_extent_op *extent_op,
1657                                 int insert_reserved)
1658 {
1659         int ret = 0;
1660         struct btrfs_delayed_tree_ref *ref;
1661         u64 parent = 0;
1662         u64 ref_root = 0;
1663
1664         ref = btrfs_delayed_node_to_tree_ref(node);
1665         trace_run_delayed_tree_ref(trans->fs_info, node, ref, node->action);
1666
1667         if (node->type == BTRFS_SHARED_BLOCK_REF_KEY)
1668                 parent = ref->parent;
1669         ref_root = ref->root;
1670
1671         if (node->ref_mod != 1) {
1672                 btrfs_err(trans->fs_info,
1673         "btree block(%llu) has %d references rather than 1: action %d ref_root %llu parent %llu",
1674                           node->bytenr, node->ref_mod, node->action, ref_root,
1675                           parent);
1676                 return -EIO;
1677         }
1678         if (node->action == BTRFS_ADD_DELAYED_REF && insert_reserved) {
1679                 BUG_ON(!extent_op || !extent_op->update_flags);
1680                 ret = alloc_reserved_tree_block(trans, node, extent_op);
1681         } else if (node->action == BTRFS_ADD_DELAYED_REF) {
1682                 ret = __btrfs_inc_extent_ref(trans, node, parent, ref_root,
1683                                              ref->level, 0, 1, extent_op);
1684         } else if (node->action == BTRFS_DROP_DELAYED_REF) {
1685                 ret = __btrfs_free_extent(trans, node, parent, ref_root,
1686                                           ref->level, 0, 1, extent_op);
1687         } else {
1688                 BUG();
1689         }
1690         return ret;
1691 }
1692
1693 /* helper function to actually process a single delayed ref entry */
1694 static int run_one_delayed_ref(struct btrfs_trans_handle *trans,
1695                                struct btrfs_delayed_ref_node *node,
1696                                struct btrfs_delayed_extent_op *extent_op,
1697                                int insert_reserved)
1698 {
1699         int ret = 0;
1700
1701         if (TRANS_ABORTED(trans)) {
1702                 if (insert_reserved)
1703                         btrfs_pin_extent(trans, node->bytenr, node->num_bytes, 1);
1704                 return 0;
1705         }
1706
1707         if (node->type == BTRFS_TREE_BLOCK_REF_KEY ||
1708             node->type == BTRFS_SHARED_BLOCK_REF_KEY)
1709                 ret = run_delayed_tree_ref(trans, node, extent_op,
1710                                            insert_reserved);
1711         else if (node->type == BTRFS_EXTENT_DATA_REF_KEY ||
1712                  node->type == BTRFS_SHARED_DATA_REF_KEY)
1713                 ret = run_delayed_data_ref(trans, node, extent_op,
1714                                            insert_reserved);
1715         else
1716                 BUG();
1717         if (ret && insert_reserved)
1718                 btrfs_pin_extent(trans, node->bytenr, node->num_bytes, 1);
1719         return ret;
1720 }
1721
1722 static inline struct btrfs_delayed_ref_node *
1723 select_delayed_ref(struct btrfs_delayed_ref_head *head)
1724 {
1725         struct btrfs_delayed_ref_node *ref;
1726
1727         if (RB_EMPTY_ROOT(&head->ref_tree.rb_root))
1728                 return NULL;
1729
1730         /*
1731          * Select a delayed ref of type BTRFS_ADD_DELAYED_REF first.
1732          * This is to prevent a ref count from going down to zero, which deletes
1733          * the extent item from the extent tree, when there still are references
1734          * to add, which would fail because they would not find the extent item.
1735          */
1736         if (!list_empty(&head->ref_add_list))
1737                 return list_first_entry(&head->ref_add_list,
1738                                 struct btrfs_delayed_ref_node, add_list);
1739
1740         ref = rb_entry(rb_first_cached(&head->ref_tree),
1741                        struct btrfs_delayed_ref_node, ref_node);
1742         ASSERT(list_empty(&ref->add_list));
1743         return ref;
1744 }
1745
1746 static void unselect_delayed_ref_head(struct btrfs_delayed_ref_root *delayed_refs,
1747                                       struct btrfs_delayed_ref_head *head)
1748 {
1749         spin_lock(&delayed_refs->lock);
1750         head->processing = 0;
1751         delayed_refs->num_heads_ready++;
1752         spin_unlock(&delayed_refs->lock);
1753         btrfs_delayed_ref_unlock(head);
1754 }
1755
1756 static struct btrfs_delayed_extent_op *cleanup_extent_op(
1757                                 struct btrfs_delayed_ref_head *head)
1758 {
1759         struct btrfs_delayed_extent_op *extent_op = head->extent_op;
1760
1761         if (!extent_op)
1762                 return NULL;
1763
1764         if (head->must_insert_reserved) {
1765                 head->extent_op = NULL;
1766                 btrfs_free_delayed_extent_op(extent_op);
1767                 return NULL;
1768         }
1769         return extent_op;
1770 }
1771
1772 static int run_and_cleanup_extent_op(struct btrfs_trans_handle *trans,
1773                                      struct btrfs_delayed_ref_head *head)
1774 {
1775         struct btrfs_delayed_extent_op *extent_op;
1776         int ret;
1777
1778         extent_op = cleanup_extent_op(head);
1779         if (!extent_op)
1780                 return 0;
1781         head->extent_op = NULL;
1782         spin_unlock(&head->lock);
1783         ret = run_delayed_extent_op(trans, head, extent_op);
1784         btrfs_free_delayed_extent_op(extent_op);
1785         return ret ? ret : 1;
1786 }
1787
1788 void btrfs_cleanup_ref_head_accounting(struct btrfs_fs_info *fs_info,
1789                                   struct btrfs_delayed_ref_root *delayed_refs,
1790                                   struct btrfs_delayed_ref_head *head)
1791 {
1792         int nr_items = 1;       /* Dropping this ref head update. */
1793
1794         /*
1795          * We had csum deletions accounted for in our delayed refs rsv, we need
1796          * to drop the csum leaves for this update from our delayed_refs_rsv.
1797          */
1798         if (head->total_ref_mod < 0 && head->is_data) {
1799                 spin_lock(&delayed_refs->lock);
1800                 delayed_refs->pending_csums -= head->num_bytes;
1801                 spin_unlock(&delayed_refs->lock);
1802                 nr_items += btrfs_csum_bytes_to_leaves(fs_info, head->num_bytes);
1803         }
1804
1805         btrfs_delayed_refs_rsv_release(fs_info, nr_items);
1806 }
1807
1808 static int cleanup_ref_head(struct btrfs_trans_handle *trans,
1809                             struct btrfs_delayed_ref_head *head)
1810 {
1811
1812         struct btrfs_fs_info *fs_info = trans->fs_info;
1813         struct btrfs_delayed_ref_root *delayed_refs;
1814         int ret;
1815
1816         delayed_refs = &trans->transaction->delayed_refs;
1817
1818         ret = run_and_cleanup_extent_op(trans, head);
1819         if (ret < 0) {
1820                 unselect_delayed_ref_head(delayed_refs, head);
1821                 btrfs_debug(fs_info, "run_delayed_extent_op returned %d", ret);
1822                 return ret;
1823         } else if (ret) {
1824                 return ret;
1825         }
1826
1827         /*
1828          * Need to drop our head ref lock and re-acquire the delayed ref lock
1829          * and then re-check to make sure nobody got added.
1830          */
1831         spin_unlock(&head->lock);
1832         spin_lock(&delayed_refs->lock);
1833         spin_lock(&head->lock);
1834         if (!RB_EMPTY_ROOT(&head->ref_tree.rb_root) || head->extent_op) {
1835                 spin_unlock(&head->lock);
1836                 spin_unlock(&delayed_refs->lock);
1837                 return 1;
1838         }
1839         btrfs_delete_ref_head(delayed_refs, head);
1840         spin_unlock(&head->lock);
1841         spin_unlock(&delayed_refs->lock);
1842
1843         if (head->must_insert_reserved) {
1844                 btrfs_pin_extent(trans, head->bytenr, head->num_bytes, 1);
1845                 if (head->is_data) {
1846                         struct btrfs_root *csum_root;
1847
1848                         csum_root = btrfs_csum_root(fs_info, head->bytenr);
1849                         ret = btrfs_del_csums(trans, csum_root, head->bytenr,
1850                                               head->num_bytes);
1851                 }
1852         }
1853
1854         btrfs_cleanup_ref_head_accounting(fs_info, delayed_refs, head);
1855
1856         trace_run_delayed_ref_head(fs_info, head, 0);
1857         btrfs_delayed_ref_unlock(head);
1858         btrfs_put_delayed_ref_head(head);
1859         return ret;
1860 }
1861
1862 static struct btrfs_delayed_ref_head *btrfs_obtain_ref_head(
1863                                         struct btrfs_trans_handle *trans)
1864 {
1865         struct btrfs_delayed_ref_root *delayed_refs =
1866                 &trans->transaction->delayed_refs;
1867         struct btrfs_delayed_ref_head *head = NULL;
1868         int ret;
1869
1870         spin_lock(&delayed_refs->lock);
1871         head = btrfs_select_ref_head(delayed_refs);
1872         if (!head) {
1873                 spin_unlock(&delayed_refs->lock);
1874                 return head;
1875         }
1876
1877         /*
1878          * Grab the lock that says we are going to process all the refs for
1879          * this head
1880          */
1881         ret = btrfs_delayed_ref_lock(delayed_refs, head);
1882         spin_unlock(&delayed_refs->lock);
1883
1884         /*
1885          * We may have dropped the spin lock to get the head mutex lock, and
1886          * that might have given someone else time to free the head.  If that's
1887          * true, it has been removed from our list and we can move on.
1888          */
1889         if (ret == -EAGAIN)
1890                 head = ERR_PTR(-EAGAIN);
1891
1892         return head;
1893 }
1894
1895 static int btrfs_run_delayed_refs_for_head(struct btrfs_trans_handle *trans,
1896                                     struct btrfs_delayed_ref_head *locked_ref,
1897                                     unsigned long *run_refs)
1898 {
1899         struct btrfs_fs_info *fs_info = trans->fs_info;
1900         struct btrfs_delayed_ref_root *delayed_refs;
1901         struct btrfs_delayed_extent_op *extent_op;
1902         struct btrfs_delayed_ref_node *ref;
1903         int must_insert_reserved = 0;
1904         int ret;
1905
1906         delayed_refs = &trans->transaction->delayed_refs;
1907
1908         lockdep_assert_held(&locked_ref->mutex);
1909         lockdep_assert_held(&locked_ref->lock);
1910
1911         while ((ref = select_delayed_ref(locked_ref))) {
1912                 if (ref->seq &&
1913                     btrfs_check_delayed_seq(fs_info, ref->seq)) {
1914                         spin_unlock(&locked_ref->lock);
1915                         unselect_delayed_ref_head(delayed_refs, locked_ref);
1916                         return -EAGAIN;
1917                 }
1918
1919                 (*run_refs)++;
1920                 ref->in_tree = 0;
1921                 rb_erase_cached(&ref->ref_node, &locked_ref->ref_tree);
1922                 RB_CLEAR_NODE(&ref->ref_node);
1923                 if (!list_empty(&ref->add_list))
1924                         list_del(&ref->add_list);
1925                 /*
1926                  * When we play the delayed ref, also correct the ref_mod on
1927                  * head
1928                  */
1929                 switch (ref->action) {
1930                 case BTRFS_ADD_DELAYED_REF:
1931                 case BTRFS_ADD_DELAYED_EXTENT:
1932                         locked_ref->ref_mod -= ref->ref_mod;
1933                         break;
1934                 case BTRFS_DROP_DELAYED_REF:
1935                         locked_ref->ref_mod += ref->ref_mod;
1936                         break;
1937                 default:
1938                         WARN_ON(1);
1939                 }
1940                 atomic_dec(&delayed_refs->num_entries);
1941
1942                 /*
1943                  * Record the must_insert_reserved flag before we drop the
1944                  * spin lock.
1945                  */
1946                 must_insert_reserved = locked_ref->must_insert_reserved;
1947                 locked_ref->must_insert_reserved = 0;
1948
1949                 extent_op = locked_ref->extent_op;
1950                 locked_ref->extent_op = NULL;
1951                 spin_unlock(&locked_ref->lock);
1952
1953                 ret = run_one_delayed_ref(trans, ref, extent_op,
1954                                           must_insert_reserved);
1955
1956                 btrfs_free_delayed_extent_op(extent_op);
1957                 if (ret) {
1958                         unselect_delayed_ref_head(delayed_refs, locked_ref);
1959                         btrfs_put_delayed_ref(ref);
1960                         btrfs_debug(fs_info, "run_one_delayed_ref returned %d",
1961                                     ret);
1962                         return ret;
1963                 }
1964
1965                 btrfs_put_delayed_ref(ref);
1966                 cond_resched();
1967
1968                 spin_lock(&locked_ref->lock);
1969                 btrfs_merge_delayed_refs(trans, delayed_refs, locked_ref);
1970         }
1971
1972         return 0;
1973 }
1974
1975 /*
1976  * Returns 0 on success or if called with an already aborted transaction.
1977  * Returns -ENOMEM or -EIO on failure and will abort the transaction.
1978  */
1979 static noinline int __btrfs_run_delayed_refs(struct btrfs_trans_handle *trans,
1980                                              unsigned long nr)
1981 {
1982         struct btrfs_fs_info *fs_info = trans->fs_info;
1983         struct btrfs_delayed_ref_root *delayed_refs;
1984         struct btrfs_delayed_ref_head *locked_ref = NULL;
1985         ktime_t start = ktime_get();
1986         int ret;
1987         unsigned long count = 0;
1988         unsigned long actual_count = 0;
1989
1990         delayed_refs = &trans->transaction->delayed_refs;
1991         do {
1992                 if (!locked_ref) {
1993                         locked_ref = btrfs_obtain_ref_head(trans);
1994                         if (IS_ERR_OR_NULL(locked_ref)) {
1995                                 if (PTR_ERR(locked_ref) == -EAGAIN) {
1996                                         continue;
1997                                 } else {
1998                                         break;
1999                                 }
2000                         }
2001                         count++;
2002                 }
2003                 /*
2004                  * We need to try and merge add/drops of the same ref since we
2005                  * can run into issues with relocate dropping the implicit ref
2006                  * and then it being added back again before the drop can
2007                  * finish.  If we merged anything we need to re-loop so we can
2008                  * get a good ref.
2009                  * Or we can get node references of the same type that weren't
2010                  * merged when created due to bumps in the tree mod seq, and
2011                  * we need to merge them to prevent adding an inline extent
2012                  * backref before dropping it (triggering a BUG_ON at
2013                  * insert_inline_extent_backref()).
2014                  */
2015                 spin_lock(&locked_ref->lock);
2016                 btrfs_merge_delayed_refs(trans, delayed_refs, locked_ref);
2017
2018                 ret = btrfs_run_delayed_refs_for_head(trans, locked_ref,
2019                                                       &actual_count);
2020                 if (ret < 0 && ret != -EAGAIN) {
2021                         /*
2022                          * Error, btrfs_run_delayed_refs_for_head already
2023                          * unlocked everything so just bail out
2024                          */
2025                         return ret;
2026                 } else if (!ret) {
2027                         /*
2028                          * Success, perform the usual cleanup of a processed
2029                          * head
2030                          */
2031                         ret = cleanup_ref_head(trans, locked_ref);
2032                         if (ret > 0 ) {
2033                                 /* We dropped our lock, we need to loop. */
2034                                 ret = 0;
2035                                 continue;
2036                         } else if (ret) {
2037                                 return ret;
2038                         }
2039                 }
2040
2041                 /*
2042                  * Either success case or btrfs_run_delayed_refs_for_head
2043                  * returned -EAGAIN, meaning we need to select another head
2044                  */
2045
2046                 locked_ref = NULL;
2047                 cond_resched();
2048         } while ((nr != -1 && count < nr) || locked_ref);
2049
2050         /*
2051          * We don't want to include ref heads since we can have empty ref heads
2052          * and those will drastically skew our runtime down since we just do
2053          * accounting, no actual extent tree updates.
2054          */
2055         if (actual_count > 0) {
2056                 u64 runtime = ktime_to_ns(ktime_sub(ktime_get(), start));
2057                 u64 avg;
2058
2059                 /*
2060                  * We weigh the current average higher than our current runtime
2061                  * to avoid large swings in the average.
2062                  */
2063                 spin_lock(&delayed_refs->lock);
2064                 avg = fs_info->avg_delayed_ref_runtime * 3 + runtime;
2065                 fs_info->avg_delayed_ref_runtime = avg >> 2;    /* div by 4 */
2066                 spin_unlock(&delayed_refs->lock);
2067         }
2068         return 0;
2069 }
2070
2071 #ifdef SCRAMBLE_DELAYED_REFS
2072 /*
2073  * Normally delayed refs get processed in ascending bytenr order. This
2074  * correlates in most cases to the order added. To expose dependencies on this
2075  * order, we start to process the tree in the middle instead of the beginning
2076  */
2077 static u64 find_middle(struct rb_root *root)
2078 {
2079         struct rb_node *n = root->rb_node;
2080         struct btrfs_delayed_ref_node *entry;
2081         int alt = 1;
2082         u64 middle;
2083         u64 first = 0, last = 0;
2084
2085         n = rb_first(root);
2086         if (n) {
2087                 entry = rb_entry(n, struct btrfs_delayed_ref_node, rb_node);
2088                 first = entry->bytenr;
2089         }
2090         n = rb_last(root);
2091         if (n) {
2092                 entry = rb_entry(n, struct btrfs_delayed_ref_node, rb_node);
2093                 last = entry->bytenr;
2094         }
2095         n = root->rb_node;
2096
2097         while (n) {
2098                 entry = rb_entry(n, struct btrfs_delayed_ref_node, rb_node);
2099                 WARN_ON(!entry->in_tree);
2100
2101                 middle = entry->bytenr;
2102
2103                 if (alt)
2104                         n = n->rb_left;
2105                 else
2106                         n = n->rb_right;
2107
2108                 alt = 1 - alt;
2109         }
2110         return middle;
2111 }
2112 #endif
2113
2114 /*
2115  * this starts processing the delayed reference count updates and
2116  * extent insertions we have queued up so far.  count can be
2117  * 0, which means to process everything in the tree at the start
2118  * of the run (but not newly added entries), or it can be some target
2119  * number you'd like to process.
2120  *
2121  * Returns 0 on success or if called with an aborted transaction
2122  * Returns <0 on error and aborts the transaction
2123  */
2124 int btrfs_run_delayed_refs(struct btrfs_trans_handle *trans,
2125                            unsigned long count)
2126 {
2127         struct btrfs_fs_info *fs_info = trans->fs_info;
2128         struct rb_node *node;
2129         struct btrfs_delayed_ref_root *delayed_refs;
2130         struct btrfs_delayed_ref_head *head;
2131         int ret;
2132         int run_all = count == (unsigned long)-1;
2133
2134         /* We'll clean this up in btrfs_cleanup_transaction */
2135         if (TRANS_ABORTED(trans))
2136                 return 0;
2137
2138         if (test_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags))
2139                 return 0;
2140
2141         delayed_refs = &trans->transaction->delayed_refs;
2142         if (count == 0)
2143                 count = delayed_refs->num_heads_ready;
2144
2145 again:
2146 #ifdef SCRAMBLE_DELAYED_REFS
2147         delayed_refs->run_delayed_start = find_middle(&delayed_refs->root);
2148 #endif
2149         ret = __btrfs_run_delayed_refs(trans, count);
2150         if (ret < 0) {
2151                 btrfs_abort_transaction(trans, ret);
2152                 return ret;
2153         }
2154
2155         if (run_all) {
2156                 btrfs_create_pending_block_groups(trans);
2157
2158                 spin_lock(&delayed_refs->lock);
2159                 node = rb_first_cached(&delayed_refs->href_root);
2160                 if (!node) {
2161                         spin_unlock(&delayed_refs->lock);
2162                         goto out;
2163                 }
2164                 head = rb_entry(node, struct btrfs_delayed_ref_head,
2165                                 href_node);
2166                 refcount_inc(&head->refs);
2167                 spin_unlock(&delayed_refs->lock);
2168
2169                 /* Mutex was contended, block until it's released and retry. */
2170                 mutex_lock(&head->mutex);
2171                 mutex_unlock(&head->mutex);
2172
2173                 btrfs_put_delayed_ref_head(head);
2174                 cond_resched();
2175                 goto again;
2176         }
2177 out:
2178         return 0;
2179 }
2180
2181 int btrfs_set_disk_extent_flags(struct btrfs_trans_handle *trans,
2182                                 struct extent_buffer *eb, u64 flags,
2183                                 int level, int is_data)
2184 {
2185         struct btrfs_delayed_extent_op *extent_op;
2186         int ret;
2187
2188         extent_op = btrfs_alloc_delayed_extent_op();
2189         if (!extent_op)
2190                 return -ENOMEM;
2191
2192         extent_op->flags_to_set = flags;
2193         extent_op->update_flags = true;
2194         extent_op->update_key = false;
2195         extent_op->is_data = is_data ? true : false;
2196         extent_op->level = level;
2197
2198         ret = btrfs_add_delayed_extent_op(trans, eb->start, eb->len, extent_op);
2199         if (ret)
2200                 btrfs_free_delayed_extent_op(extent_op);
2201         return ret;
2202 }
2203
2204 static noinline int check_delayed_ref(struct btrfs_root *root,
2205                                       struct btrfs_path *path,
2206                                       u64 objectid, u64 offset, u64 bytenr)
2207 {
2208         struct btrfs_delayed_ref_head *head;
2209         struct btrfs_delayed_ref_node *ref;
2210         struct btrfs_delayed_data_ref *data_ref;
2211         struct btrfs_delayed_ref_root *delayed_refs;
2212         struct btrfs_transaction *cur_trans;
2213         struct rb_node *node;
2214         int ret = 0;
2215
2216         spin_lock(&root->fs_info->trans_lock);
2217         cur_trans = root->fs_info->running_transaction;
2218         if (cur_trans)
2219                 refcount_inc(&cur_trans->use_count);
2220         spin_unlock(&root->fs_info->trans_lock);
2221         if (!cur_trans)
2222                 return 0;
2223
2224         delayed_refs = &cur_trans->delayed_refs;
2225         spin_lock(&delayed_refs->lock);
2226         head = btrfs_find_delayed_ref_head(delayed_refs, bytenr);
2227         if (!head) {
2228                 spin_unlock(&delayed_refs->lock);
2229                 btrfs_put_transaction(cur_trans);
2230                 return 0;
2231         }
2232
2233         if (!mutex_trylock(&head->mutex)) {
2234                 refcount_inc(&head->refs);
2235                 spin_unlock(&delayed_refs->lock);
2236
2237                 btrfs_release_path(path);
2238
2239                 /*
2240                  * Mutex was contended, block until it's released and let
2241                  * caller try again
2242                  */
2243                 mutex_lock(&head->mutex);
2244                 mutex_unlock(&head->mutex);
2245                 btrfs_put_delayed_ref_head(head);
2246                 btrfs_put_transaction(cur_trans);
2247                 return -EAGAIN;
2248         }
2249         spin_unlock(&delayed_refs->lock);
2250
2251         spin_lock(&head->lock);
2252         /*
2253          * XXX: We should replace this with a proper search function in the
2254          * future.
2255          */
2256         for (node = rb_first_cached(&head->ref_tree); node;
2257              node = rb_next(node)) {
2258                 ref = rb_entry(node, struct btrfs_delayed_ref_node, ref_node);
2259                 /* If it's a shared ref we know a cross reference exists */
2260                 if (ref->type != BTRFS_EXTENT_DATA_REF_KEY) {
2261                         ret = 1;
2262                         break;
2263                 }
2264
2265                 data_ref = btrfs_delayed_node_to_data_ref(ref);
2266
2267                 /*
2268                  * If our ref doesn't match the one we're currently looking at
2269                  * then we have a cross reference.
2270                  */
2271                 if (data_ref->root != root->root_key.objectid ||
2272                     data_ref->objectid != objectid ||
2273                     data_ref->offset != offset) {
2274                         ret = 1;
2275                         break;
2276                 }
2277         }
2278         spin_unlock(&head->lock);
2279         mutex_unlock(&head->mutex);
2280         btrfs_put_transaction(cur_trans);
2281         return ret;
2282 }
2283
2284 static noinline int check_committed_ref(struct btrfs_root *root,
2285                                         struct btrfs_path *path,
2286                                         u64 objectid, u64 offset, u64 bytenr,
2287                                         bool strict)
2288 {
2289         struct btrfs_fs_info *fs_info = root->fs_info;
2290         struct btrfs_root *extent_root = btrfs_extent_root(fs_info, bytenr);
2291         struct extent_buffer *leaf;
2292         struct btrfs_extent_data_ref *ref;
2293         struct btrfs_extent_inline_ref *iref;
2294         struct btrfs_extent_item *ei;
2295         struct btrfs_key key;
2296         u32 item_size;
2297         int type;
2298         int ret;
2299
2300         key.objectid = bytenr;
2301         key.offset = (u64)-1;
2302         key.type = BTRFS_EXTENT_ITEM_KEY;
2303
2304         ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
2305         if (ret < 0)
2306                 goto out;
2307         BUG_ON(ret == 0); /* Corruption */
2308
2309         ret = -ENOENT;
2310         if (path->slots[0] == 0)
2311                 goto out;
2312
2313         path->slots[0]--;
2314         leaf = path->nodes[0];
2315         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
2316
2317         if (key.objectid != bytenr || key.type != BTRFS_EXTENT_ITEM_KEY)
2318                 goto out;
2319
2320         ret = 1;
2321         item_size = btrfs_item_size(leaf, path->slots[0]);
2322         ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
2323
2324         /* If extent item has more than 1 inline ref then it's shared */
2325         if (item_size != sizeof(*ei) +
2326             btrfs_extent_inline_ref_size(BTRFS_EXTENT_DATA_REF_KEY))
2327                 goto out;
2328
2329         /*
2330          * If extent created before last snapshot => it's shared unless the
2331          * snapshot has been deleted. Use the heuristic if strict is false.
2332          */
2333         if (!strict &&
2334             (btrfs_extent_generation(leaf, ei) <=
2335              btrfs_root_last_snapshot(&root->root_item)))
2336                 goto out;
2337
2338         iref = (struct btrfs_extent_inline_ref *)(ei + 1);
2339
2340         /* If this extent has SHARED_DATA_REF then it's shared */
2341         type = btrfs_get_extent_inline_ref_type(leaf, iref, BTRFS_REF_TYPE_DATA);
2342         if (type != BTRFS_EXTENT_DATA_REF_KEY)
2343                 goto out;
2344
2345         ref = (struct btrfs_extent_data_ref *)(&iref->offset);
2346         if (btrfs_extent_refs(leaf, ei) !=
2347             btrfs_extent_data_ref_count(leaf, ref) ||
2348             btrfs_extent_data_ref_root(leaf, ref) !=
2349             root->root_key.objectid ||
2350             btrfs_extent_data_ref_objectid(leaf, ref) != objectid ||
2351             btrfs_extent_data_ref_offset(leaf, ref) != offset)
2352                 goto out;
2353
2354         ret = 0;
2355 out:
2356         return ret;
2357 }
2358
2359 int btrfs_cross_ref_exist(struct btrfs_root *root, u64 objectid, u64 offset,
2360                           u64 bytenr, bool strict)
2361 {
2362         struct btrfs_path *path;
2363         int ret;
2364
2365         path = btrfs_alloc_path();
2366         if (!path)
2367                 return -ENOMEM;
2368
2369         do {
2370                 ret = check_committed_ref(root, path, objectid,
2371                                           offset, bytenr, strict);
2372                 if (ret && ret != -ENOENT)
2373                         goto out;
2374
2375                 ret = check_delayed_ref(root, path, objectid, offset, bytenr);
2376         } while (ret == -EAGAIN);
2377
2378 out:
2379         btrfs_free_path(path);
2380         if (btrfs_is_data_reloc_root(root))
2381                 WARN_ON(ret > 0);
2382         return ret;
2383 }
2384
2385 static int __btrfs_mod_ref(struct btrfs_trans_handle *trans,
2386                            struct btrfs_root *root,
2387                            struct extent_buffer *buf,
2388                            int full_backref, int inc)
2389 {
2390         struct btrfs_fs_info *fs_info = root->fs_info;
2391         u64 bytenr;
2392         u64 num_bytes;
2393         u64 parent;
2394         u64 ref_root;
2395         u32 nritems;
2396         struct btrfs_key key;
2397         struct btrfs_file_extent_item *fi;
2398         struct btrfs_ref generic_ref = { 0 };
2399         bool for_reloc = btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC);
2400         int i;
2401         int action;
2402         int level;
2403         int ret = 0;
2404
2405         if (btrfs_is_testing(fs_info))
2406                 return 0;
2407
2408         ref_root = btrfs_header_owner(buf);
2409         nritems = btrfs_header_nritems(buf);
2410         level = btrfs_header_level(buf);
2411
2412         if (!test_bit(BTRFS_ROOT_SHAREABLE, &root->state) && level == 0)
2413                 return 0;
2414
2415         if (full_backref)
2416                 parent = buf->start;
2417         else
2418                 parent = 0;
2419         if (inc)
2420                 action = BTRFS_ADD_DELAYED_REF;
2421         else
2422                 action = BTRFS_DROP_DELAYED_REF;
2423
2424         for (i = 0; i < nritems; i++) {
2425                 if (level == 0) {
2426                         btrfs_item_key_to_cpu(buf, &key, i);
2427                         if (key.type != BTRFS_EXTENT_DATA_KEY)
2428                                 continue;
2429                         fi = btrfs_item_ptr(buf, i,
2430                                             struct btrfs_file_extent_item);
2431                         if (btrfs_file_extent_type(buf, fi) ==
2432                             BTRFS_FILE_EXTENT_INLINE)
2433                                 continue;
2434                         bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
2435                         if (bytenr == 0)
2436                                 continue;
2437
2438                         num_bytes = btrfs_file_extent_disk_num_bytes(buf, fi);
2439                         key.offset -= btrfs_file_extent_offset(buf, fi);
2440                         btrfs_init_generic_ref(&generic_ref, action, bytenr,
2441                                                num_bytes, parent);
2442                         btrfs_init_data_ref(&generic_ref, ref_root, key.objectid,
2443                                             key.offset, root->root_key.objectid,
2444                                             for_reloc);
2445                         if (inc)
2446                                 ret = btrfs_inc_extent_ref(trans, &generic_ref);
2447                         else
2448                                 ret = btrfs_free_extent(trans, &generic_ref);
2449                         if (ret)
2450                                 goto fail;
2451                 } else {
2452                         bytenr = btrfs_node_blockptr(buf, i);
2453                         num_bytes = fs_info->nodesize;
2454                         btrfs_init_generic_ref(&generic_ref, action, bytenr,
2455                                                num_bytes, parent);
2456                         btrfs_init_tree_ref(&generic_ref, level - 1, ref_root,
2457                                             root->root_key.objectid, for_reloc);
2458                         if (inc)
2459                                 ret = btrfs_inc_extent_ref(trans, &generic_ref);
2460                         else
2461                                 ret = btrfs_free_extent(trans, &generic_ref);
2462                         if (ret)
2463                                 goto fail;
2464                 }
2465         }
2466         return 0;
2467 fail:
2468         return ret;
2469 }
2470
2471 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2472                   struct extent_buffer *buf, int full_backref)
2473 {
2474         return __btrfs_mod_ref(trans, root, buf, full_backref, 1);
2475 }
2476
2477 int btrfs_dec_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
2478                   struct extent_buffer *buf, int full_backref)
2479 {
2480         return __btrfs_mod_ref(trans, root, buf, full_backref, 0);
2481 }
2482
2483 static u64 get_alloc_profile_by_root(struct btrfs_root *root, int data)
2484 {
2485         struct btrfs_fs_info *fs_info = root->fs_info;
2486         u64 flags;
2487         u64 ret;
2488
2489         if (data)
2490                 flags = BTRFS_BLOCK_GROUP_DATA;
2491         else if (root == fs_info->chunk_root)
2492                 flags = BTRFS_BLOCK_GROUP_SYSTEM;
2493         else
2494                 flags = BTRFS_BLOCK_GROUP_METADATA;
2495
2496         ret = btrfs_get_alloc_profile(fs_info, flags);
2497         return ret;
2498 }
2499
2500 static u64 first_logical_byte(struct btrfs_fs_info *fs_info, u64 search_start)
2501 {
2502         struct btrfs_block_group *cache;
2503         u64 bytenr;
2504
2505         spin_lock(&fs_info->block_group_cache_lock);
2506         bytenr = fs_info->first_logical_byte;
2507         spin_unlock(&fs_info->block_group_cache_lock);
2508
2509         if (bytenr < (u64)-1)
2510                 return bytenr;
2511
2512         cache = btrfs_lookup_first_block_group(fs_info, search_start);
2513         if (!cache)
2514                 return 0;
2515
2516         bytenr = cache->start;
2517         btrfs_put_block_group(cache);
2518
2519         return bytenr;
2520 }
2521
2522 static int pin_down_extent(struct btrfs_trans_handle *trans,
2523                            struct btrfs_block_group *cache,
2524                            u64 bytenr, u64 num_bytes, int reserved)
2525 {
2526         struct btrfs_fs_info *fs_info = cache->fs_info;
2527
2528         spin_lock(&cache->space_info->lock);
2529         spin_lock(&cache->lock);
2530         cache->pinned += num_bytes;
2531         btrfs_space_info_update_bytes_pinned(fs_info, cache->space_info,
2532                                              num_bytes);
2533         if (reserved) {
2534                 cache->reserved -= num_bytes;
2535                 cache->space_info->bytes_reserved -= num_bytes;
2536         }
2537         spin_unlock(&cache->lock);
2538         spin_unlock(&cache->space_info->lock);
2539
2540         set_extent_dirty(&trans->transaction->pinned_extents, bytenr,
2541                          bytenr + num_bytes - 1, GFP_NOFS | __GFP_NOFAIL);
2542         return 0;
2543 }
2544
2545 int btrfs_pin_extent(struct btrfs_trans_handle *trans,
2546                      u64 bytenr, u64 num_bytes, int reserved)
2547 {
2548         struct btrfs_block_group *cache;
2549
2550         cache = btrfs_lookup_block_group(trans->fs_info, bytenr);
2551         BUG_ON(!cache); /* Logic error */
2552
2553         pin_down_extent(trans, cache, bytenr, num_bytes, reserved);
2554
2555         btrfs_put_block_group(cache);
2556         return 0;
2557 }
2558
2559 /*
2560  * this function must be called within transaction
2561  */
2562 int btrfs_pin_extent_for_log_replay(struct btrfs_trans_handle *trans,
2563                                     u64 bytenr, u64 num_bytes)
2564 {
2565         struct btrfs_block_group *cache;
2566         int ret;
2567
2568         cache = btrfs_lookup_block_group(trans->fs_info, bytenr);
2569         if (!cache)
2570                 return -EINVAL;
2571
2572         /*
2573          * pull in the free space cache (if any) so that our pin
2574          * removes the free space from the cache.  We have load_only set
2575          * to one because the slow code to read in the free extents does check
2576          * the pinned extents.
2577          */
2578         btrfs_cache_block_group(cache, 1);
2579         /*
2580          * Make sure we wait until the cache is completely built in case it is
2581          * missing or is invalid and therefore needs to be rebuilt.
2582          */
2583         ret = btrfs_wait_block_group_cache_done(cache);
2584         if (ret)
2585                 goto out;
2586
2587         pin_down_extent(trans, cache, bytenr, num_bytes, 0);
2588
2589         /* remove us from the free space cache (if we're there at all) */
2590         ret = btrfs_remove_free_space(cache, bytenr, num_bytes);
2591 out:
2592         btrfs_put_block_group(cache);
2593         return ret;
2594 }
2595
2596 static int __exclude_logged_extent(struct btrfs_fs_info *fs_info,
2597                                    u64 start, u64 num_bytes)
2598 {
2599         int ret;
2600         struct btrfs_block_group *block_group;
2601
2602         block_group = btrfs_lookup_block_group(fs_info, start);
2603         if (!block_group)
2604                 return -EINVAL;
2605
2606         btrfs_cache_block_group(block_group, 1);
2607         /*
2608          * Make sure we wait until the cache is completely built in case it is
2609          * missing or is invalid and therefore needs to be rebuilt.
2610          */
2611         ret = btrfs_wait_block_group_cache_done(block_group);
2612         if (ret)
2613                 goto out;
2614
2615         ret = btrfs_remove_free_space(block_group, start, num_bytes);
2616 out:
2617         btrfs_put_block_group(block_group);
2618         return ret;
2619 }
2620
2621 int btrfs_exclude_logged_extents(struct extent_buffer *eb)
2622 {
2623         struct btrfs_fs_info *fs_info = eb->fs_info;
2624         struct btrfs_file_extent_item *item;
2625         struct btrfs_key key;
2626         int found_type;
2627         int i;
2628         int ret = 0;
2629
2630         if (!btrfs_fs_incompat(fs_info, MIXED_GROUPS))
2631                 return 0;
2632
2633         for (i = 0; i < btrfs_header_nritems(eb); i++) {
2634                 btrfs_item_key_to_cpu(eb, &key, i);
2635                 if (key.type != BTRFS_EXTENT_DATA_KEY)
2636                         continue;
2637                 item = btrfs_item_ptr(eb, i, struct btrfs_file_extent_item);
2638                 found_type = btrfs_file_extent_type(eb, item);
2639                 if (found_type == BTRFS_FILE_EXTENT_INLINE)
2640                         continue;
2641                 if (btrfs_file_extent_disk_bytenr(eb, item) == 0)
2642                         continue;
2643                 key.objectid = btrfs_file_extent_disk_bytenr(eb, item);
2644                 key.offset = btrfs_file_extent_disk_num_bytes(eb, item);
2645                 ret = __exclude_logged_extent(fs_info, key.objectid, key.offset);
2646                 if (ret)
2647                         break;
2648         }
2649
2650         return ret;
2651 }
2652
2653 static void
2654 btrfs_inc_block_group_reservations(struct btrfs_block_group *bg)
2655 {
2656         atomic_inc(&bg->reservations);
2657 }
2658
2659 /*
2660  * Returns the free cluster for the given space info and sets empty_cluster to
2661  * what it should be based on the mount options.
2662  */
2663 static struct btrfs_free_cluster *
2664 fetch_cluster_info(struct btrfs_fs_info *fs_info,
2665                    struct btrfs_space_info *space_info, u64 *empty_cluster)
2666 {
2667         struct btrfs_free_cluster *ret = NULL;
2668
2669         *empty_cluster = 0;
2670         if (btrfs_mixed_space_info(space_info))
2671                 return ret;
2672
2673         if (space_info->flags & BTRFS_BLOCK_GROUP_METADATA) {
2674                 ret = &fs_info->meta_alloc_cluster;
2675                 if (btrfs_test_opt(fs_info, SSD))
2676                         *empty_cluster = SZ_2M;
2677                 else
2678                         *empty_cluster = SZ_64K;
2679         } else if ((space_info->flags & BTRFS_BLOCK_GROUP_DATA) &&
2680                    btrfs_test_opt(fs_info, SSD_SPREAD)) {
2681                 *empty_cluster = SZ_2M;
2682                 ret = &fs_info->data_alloc_cluster;
2683         }
2684
2685         return ret;
2686 }
2687
2688 static int unpin_extent_range(struct btrfs_fs_info *fs_info,
2689                               u64 start, u64 end,
2690                               const bool return_free_space)
2691 {
2692         struct btrfs_block_group *cache = NULL;
2693         struct btrfs_space_info *space_info;
2694         struct btrfs_block_rsv *global_rsv = &fs_info->global_block_rsv;
2695         struct btrfs_free_cluster *cluster = NULL;
2696         u64 len;
2697         u64 total_unpinned = 0;
2698         u64 empty_cluster = 0;
2699         bool readonly;
2700
2701         while (start <= end) {
2702                 readonly = false;
2703                 if (!cache ||
2704                     start >= cache->start + cache->length) {
2705                         if (cache)
2706                                 btrfs_put_block_group(cache);
2707                         total_unpinned = 0;
2708                         cache = btrfs_lookup_block_group(fs_info, start);
2709                         BUG_ON(!cache); /* Logic error */
2710
2711                         cluster = fetch_cluster_info(fs_info,
2712                                                      cache->space_info,
2713                                                      &empty_cluster);
2714                         empty_cluster <<= 1;
2715                 }
2716
2717                 len = cache->start + cache->length - start;
2718                 len = min(len, end + 1 - start);
2719
2720                 down_read(&fs_info->commit_root_sem);
2721                 if (start < cache->last_byte_to_unpin && return_free_space) {
2722                         u64 add_len = min(len, cache->last_byte_to_unpin - start);
2723
2724                         btrfs_add_free_space(cache, start, add_len);
2725                 }
2726                 up_read(&fs_info->commit_root_sem);
2727
2728                 start += len;
2729                 total_unpinned += len;
2730                 space_info = cache->space_info;
2731
2732                 /*
2733                  * If this space cluster has been marked as fragmented and we've
2734                  * unpinned enough in this block group to potentially allow a
2735                  * cluster to be created inside of it go ahead and clear the
2736                  * fragmented check.
2737                  */
2738                 if (cluster && cluster->fragmented &&
2739                     total_unpinned > empty_cluster) {
2740                         spin_lock(&cluster->lock);
2741                         cluster->fragmented = 0;
2742                         spin_unlock(&cluster->lock);
2743                 }
2744
2745                 spin_lock(&space_info->lock);
2746                 spin_lock(&cache->lock);
2747                 cache->pinned -= len;
2748                 btrfs_space_info_update_bytes_pinned(fs_info, space_info, -len);
2749                 space_info->max_extent_size = 0;
2750                 if (cache->ro) {
2751                         space_info->bytes_readonly += len;
2752                         readonly = true;
2753                 } else if (btrfs_is_zoned(fs_info)) {
2754                         /* Need reset before reusing in a zoned block group */
2755                         space_info->bytes_zone_unusable += len;
2756                         readonly = true;
2757                 }
2758                 spin_unlock(&cache->lock);
2759                 if (!readonly && return_free_space &&
2760                     global_rsv->space_info == space_info) {
2761                         spin_lock(&global_rsv->lock);
2762                         if (!global_rsv->full) {
2763                                 u64 to_add = min(len, global_rsv->size -
2764                                                       global_rsv->reserved);
2765
2766                                 global_rsv->reserved += to_add;
2767                                 btrfs_space_info_update_bytes_may_use(fs_info,
2768                                                 space_info, to_add);
2769                                 if (global_rsv->reserved >= global_rsv->size)
2770                                         global_rsv->full = 1;
2771                                 len -= to_add;
2772                         }
2773                         spin_unlock(&global_rsv->lock);
2774                 }
2775                 /* Add to any tickets we may have */
2776                 if (!readonly && return_free_space && len)
2777                         btrfs_try_granting_tickets(fs_info, space_info);
2778                 spin_unlock(&space_info->lock);
2779         }
2780
2781         if (cache)
2782                 btrfs_put_block_group(cache);
2783         return 0;
2784 }
2785
2786 int btrfs_finish_extent_commit(struct btrfs_trans_handle *trans)
2787 {
2788         struct btrfs_fs_info *fs_info = trans->fs_info;
2789         struct btrfs_block_group *block_group, *tmp;
2790         struct list_head *deleted_bgs;
2791         struct extent_io_tree *unpin;
2792         u64 start;
2793         u64 end;
2794         int ret;
2795
2796         unpin = &trans->transaction->pinned_extents;
2797
2798         while (!TRANS_ABORTED(trans)) {
2799                 struct extent_state *cached_state = NULL;
2800
2801                 mutex_lock(&fs_info->unused_bg_unpin_mutex);
2802                 ret = find_first_extent_bit(unpin, 0, &start, &end,
2803                                             EXTENT_DIRTY, &cached_state);
2804                 if (ret) {
2805                         mutex_unlock(&fs_info->unused_bg_unpin_mutex);
2806                         break;
2807                 }
2808
2809                 if (btrfs_test_opt(fs_info, DISCARD_SYNC))
2810                         ret = btrfs_discard_extent(fs_info, start,
2811                                                    end + 1 - start, NULL);
2812
2813                 clear_extent_dirty(unpin, start, end, &cached_state);
2814                 unpin_extent_range(fs_info, start, end, true);
2815                 mutex_unlock(&fs_info->unused_bg_unpin_mutex);
2816                 free_extent_state(cached_state);
2817                 cond_resched();
2818         }
2819
2820         if (btrfs_test_opt(fs_info, DISCARD_ASYNC)) {
2821                 btrfs_discard_calc_delay(&fs_info->discard_ctl);
2822                 btrfs_discard_schedule_work(&fs_info->discard_ctl, true);
2823         }
2824
2825         /*
2826          * Transaction is finished.  We don't need the lock anymore.  We
2827          * do need to clean up the block groups in case of a transaction
2828          * abort.
2829          */
2830         deleted_bgs = &trans->transaction->deleted_bgs;
2831         list_for_each_entry_safe(block_group, tmp, deleted_bgs, bg_list) {
2832                 u64 trimmed = 0;
2833
2834                 ret = -EROFS;
2835                 if (!TRANS_ABORTED(trans))
2836                         ret = btrfs_discard_extent(fs_info,
2837                                                    block_group->start,
2838                                                    block_group->length,
2839                                                    &trimmed);
2840
2841                 list_del_init(&block_group->bg_list);
2842                 btrfs_unfreeze_block_group(block_group);
2843                 btrfs_put_block_group(block_group);
2844
2845                 if (ret) {
2846                         const char *errstr = btrfs_decode_error(ret);
2847                         btrfs_warn(fs_info,
2848                            "discard failed while removing blockgroup: errno=%d %s",
2849                                    ret, errstr);
2850                 }
2851         }
2852
2853         return 0;
2854 }
2855
2856 static int do_free_extent_accounting(struct btrfs_trans_handle *trans,
2857                                      u64 bytenr, u64 num_bytes, bool is_data)
2858 {
2859         int ret;
2860
2861         if (is_data) {
2862                 struct btrfs_root *csum_root;
2863
2864                 csum_root = btrfs_csum_root(trans->fs_info, bytenr);
2865                 ret = btrfs_del_csums(trans, csum_root, bytenr, num_bytes);
2866                 if (ret) {
2867                         btrfs_abort_transaction(trans, ret);
2868                         return ret;
2869                 }
2870         }
2871
2872         ret = add_to_free_space_tree(trans, bytenr, num_bytes);
2873         if (ret) {
2874                 btrfs_abort_transaction(trans, ret);
2875                 return ret;
2876         }
2877
2878         ret = btrfs_update_block_group(trans, bytenr, num_bytes, false);
2879         if (ret)
2880                 btrfs_abort_transaction(trans, ret);
2881
2882         return ret;
2883 }
2884
2885 /*
2886  * Drop one or more refs of @node.
2887  *
2888  * 1. Locate the extent refs.
2889  *    It's either inline in EXTENT/METADATA_ITEM or in keyed SHARED_* item.
2890  *    Locate it, then reduce the refs number or remove the ref line completely.
2891  *
2892  * 2. Update the refs count in EXTENT/METADATA_ITEM
2893  *
2894  * Inline backref case:
2895  *
2896  * in extent tree we have:
2897  *
2898  *      item 0 key (13631488 EXTENT_ITEM 1048576) itemoff 16201 itemsize 82
2899  *              refs 2 gen 6 flags DATA
2900  *              extent data backref root FS_TREE objectid 258 offset 0 count 1
2901  *              extent data backref root FS_TREE objectid 257 offset 0 count 1
2902  *
2903  * This function gets called with:
2904  *
2905  *    node->bytenr = 13631488
2906  *    node->num_bytes = 1048576
2907  *    root_objectid = FS_TREE
2908  *    owner_objectid = 257
2909  *    owner_offset = 0
2910  *    refs_to_drop = 1
2911  *
2912  * Then we should get some like:
2913  *
2914  *      item 0 key (13631488 EXTENT_ITEM 1048576) itemoff 16201 itemsize 82
2915  *              refs 1 gen 6 flags DATA
2916  *              extent data backref root FS_TREE objectid 258 offset 0 count 1
2917  *
2918  * Keyed backref case:
2919  *
2920  * in extent tree we have:
2921  *
2922  *      item 0 key (13631488 EXTENT_ITEM 1048576) itemoff 3971 itemsize 24
2923  *              refs 754 gen 6 flags DATA
2924  *      [...]
2925  *      item 2 key (13631488 EXTENT_DATA_REF <HASH>) itemoff 3915 itemsize 28
2926  *              extent data backref root FS_TREE objectid 866 offset 0 count 1
2927  *
2928  * This function get called with:
2929  *
2930  *    node->bytenr = 13631488
2931  *    node->num_bytes = 1048576
2932  *    root_objectid = FS_TREE
2933  *    owner_objectid = 866
2934  *    owner_offset = 0
2935  *    refs_to_drop = 1
2936  *
2937  * Then we should get some like:
2938  *
2939  *      item 0 key (13631488 EXTENT_ITEM 1048576) itemoff 3971 itemsize 24
2940  *              refs 753 gen 6 flags DATA
2941  *
2942  * And that (13631488 EXTENT_DATA_REF <HASH>) gets removed.
2943  */
2944 static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
2945                                struct btrfs_delayed_ref_node *node, u64 parent,
2946                                u64 root_objectid, u64 owner_objectid,
2947                                u64 owner_offset, int refs_to_drop,
2948                                struct btrfs_delayed_extent_op *extent_op)
2949 {
2950         struct btrfs_fs_info *info = trans->fs_info;
2951         struct btrfs_key key;
2952         struct btrfs_path *path;
2953         struct btrfs_root *extent_root;
2954         struct extent_buffer *leaf;
2955         struct btrfs_extent_item *ei;
2956         struct btrfs_extent_inline_ref *iref;
2957         int ret;
2958         int is_data;
2959         int extent_slot = 0;
2960         int found_extent = 0;
2961         int num_to_del = 1;
2962         u32 item_size;
2963         u64 refs;
2964         u64 bytenr = node->bytenr;
2965         u64 num_bytes = node->num_bytes;
2966         bool skinny_metadata = btrfs_fs_incompat(info, SKINNY_METADATA);
2967
2968         extent_root = btrfs_extent_root(info, bytenr);
2969         ASSERT(extent_root);
2970
2971         path = btrfs_alloc_path();
2972         if (!path)
2973                 return -ENOMEM;
2974
2975         is_data = owner_objectid >= BTRFS_FIRST_FREE_OBJECTID;
2976
2977         if (!is_data && refs_to_drop != 1) {
2978                 btrfs_crit(info,
2979 "invalid refs_to_drop, dropping more than 1 refs for tree block %llu refs_to_drop %u",
2980                            node->bytenr, refs_to_drop);
2981                 ret = -EINVAL;
2982                 btrfs_abort_transaction(trans, ret);
2983                 goto out;
2984         }
2985
2986         if (is_data)
2987                 skinny_metadata = false;
2988
2989         ret = lookup_extent_backref(trans, path, &iref, bytenr, num_bytes,
2990                                     parent, root_objectid, owner_objectid,
2991                                     owner_offset);
2992         if (ret == 0) {
2993                 /*
2994                  * Either the inline backref or the SHARED_DATA_REF/
2995                  * SHARED_BLOCK_REF is found
2996                  *
2997                  * Here is a quick path to locate EXTENT/METADATA_ITEM.
2998                  * It's possible the EXTENT/METADATA_ITEM is near current slot.
2999                  */
3000                 extent_slot = path->slots[0];
3001                 while (extent_slot >= 0) {
3002                         btrfs_item_key_to_cpu(path->nodes[0], &key,
3003                                               extent_slot);
3004                         if (key.objectid != bytenr)
3005                                 break;
3006                         if (key.type == BTRFS_EXTENT_ITEM_KEY &&
3007                             key.offset == num_bytes) {
3008                                 found_extent = 1;
3009                                 break;
3010                         }
3011                         if (key.type == BTRFS_METADATA_ITEM_KEY &&
3012                             key.offset == owner_objectid) {
3013                                 found_extent = 1;
3014                                 break;
3015                         }
3016
3017                         /* Quick path didn't find the EXTEMT/METADATA_ITEM */
3018                         if (path->slots[0] - extent_slot > 5)
3019                                 break;
3020                         extent_slot--;
3021                 }
3022
3023                 if (!found_extent) {
3024                         if (iref) {
3025                                 btrfs_crit(info,
3026 "invalid iref, no EXTENT/METADATA_ITEM found but has inline extent ref");
3027                                 btrfs_abort_transaction(trans, -EUCLEAN);
3028                                 goto err_dump;
3029                         }
3030                         /* Must be SHARED_* item, remove the backref first */
3031                         ret = remove_extent_backref(trans, extent_root, path,
3032                                                     NULL, refs_to_drop, is_data);
3033                         if (ret) {
3034                                 btrfs_abort_transaction(trans, ret);
3035                                 goto out;
3036                         }
3037                         btrfs_release_path(path);
3038
3039                         /* Slow path to locate EXTENT/METADATA_ITEM */
3040                         key.objectid = bytenr;
3041                         key.type = BTRFS_EXTENT_ITEM_KEY;
3042                         key.offset = num_bytes;
3043
3044                         if (!is_data && skinny_metadata) {
3045                                 key.type = BTRFS_METADATA_ITEM_KEY;
3046                                 key.offset = owner_objectid;
3047                         }
3048
3049                         ret = btrfs_search_slot(trans, extent_root,
3050                                                 &key, path, -1, 1);
3051                         if (ret > 0 && skinny_metadata && path->slots[0]) {
3052                                 /*
3053                                  * Couldn't find our skinny metadata item,
3054                                  * see if we have ye olde extent item.
3055                                  */
3056                                 path->slots[0]--;
3057                                 btrfs_item_key_to_cpu(path->nodes[0], &key,
3058                                                       path->slots[0]);
3059                                 if (key.objectid == bytenr &&
3060                                     key.type == BTRFS_EXTENT_ITEM_KEY &&
3061                                     key.offset == num_bytes)
3062                                         ret = 0;
3063                         }
3064
3065                         if (ret > 0 && skinny_metadata) {
3066                                 skinny_metadata = false;
3067                                 key.objectid = bytenr;
3068                                 key.type = BTRFS_EXTENT_ITEM_KEY;
3069                                 key.offset = num_bytes;
3070                                 btrfs_release_path(path);
3071                                 ret = btrfs_search_slot(trans, extent_root,
3072                                                         &key, path, -1, 1);
3073                         }
3074
3075                         if (ret) {
3076                                 btrfs_err(info,
3077                                           "umm, got %d back from search, was looking for %llu",
3078                                           ret, bytenr);
3079                                 if (ret > 0)
3080                                         btrfs_print_leaf(path->nodes[0]);
3081                         }
3082                         if (ret < 0) {
3083                                 btrfs_abort_transaction(trans, ret);
3084                                 goto out;
3085                         }
3086                         extent_slot = path->slots[0];
3087                 }
3088         } else if (WARN_ON(ret == -ENOENT)) {
3089                 btrfs_print_leaf(path->nodes[0]);
3090                 btrfs_err(info,
3091                         "unable to find ref byte nr %llu parent %llu root %llu  owner %llu offset %llu",
3092                         bytenr, parent, root_objectid, owner_objectid,
3093                         owner_offset);
3094                 btrfs_abort_transaction(trans, ret);
3095                 goto out;
3096         } else {
3097                 btrfs_abort_transaction(trans, ret);
3098                 goto out;
3099         }
3100
3101         leaf = path->nodes[0];
3102         item_size = btrfs_item_size(leaf, extent_slot);
3103         if (unlikely(item_size < sizeof(*ei))) {
3104                 ret = -EINVAL;
3105                 btrfs_print_v0_err(info);
3106                 btrfs_abort_transaction(trans, ret);
3107                 goto out;
3108         }
3109         ei = btrfs_item_ptr(leaf, extent_slot,
3110                             struct btrfs_extent_item);
3111         if (owner_objectid < BTRFS_FIRST_FREE_OBJECTID &&
3112             key.type == BTRFS_EXTENT_ITEM_KEY) {
3113                 struct btrfs_tree_block_info *bi;
3114                 if (item_size < sizeof(*ei) + sizeof(*bi)) {
3115                         btrfs_crit(info,
3116 "invalid extent item size for key (%llu, %u, %llu) owner %llu, has %u expect >= %zu",
3117                                    key.objectid, key.type, key.offset,
3118                                    owner_objectid, item_size,
3119                                    sizeof(*ei) + sizeof(*bi));
3120                         btrfs_abort_transaction(trans, -EUCLEAN);
3121                         goto err_dump;
3122                 }
3123                 bi = (struct btrfs_tree_block_info *)(ei + 1);
3124                 WARN_ON(owner_objectid != btrfs_tree_block_level(leaf, bi));
3125         }
3126
3127         refs = btrfs_extent_refs(leaf, ei);
3128         if (refs < refs_to_drop) {
3129                 btrfs_crit(info,
3130                 "trying to drop %d refs but we only have %llu for bytenr %llu",
3131                           refs_to_drop, refs, bytenr);
3132                 btrfs_abort_transaction(trans, -EUCLEAN);
3133                 goto err_dump;
3134         }
3135         refs -= refs_to_drop;
3136
3137         if (refs > 0) {
3138                 if (extent_op)
3139                         __run_delayed_extent_op(extent_op, leaf, ei);
3140                 /*
3141                  * In the case of inline back ref, reference count will
3142                  * be updated by remove_extent_backref
3143                  */
3144                 if (iref) {
3145                         if (!found_extent) {
3146                                 btrfs_crit(info,
3147 "invalid iref, got inlined extent ref but no EXTENT/METADATA_ITEM found");
3148                                 btrfs_abort_transaction(trans, -EUCLEAN);
3149                                 goto err_dump;
3150                         }
3151                 } else {
3152                         btrfs_set_extent_refs(leaf, ei, refs);
3153                         btrfs_mark_buffer_dirty(leaf);
3154                 }
3155                 if (found_extent) {
3156                         ret = remove_extent_backref(trans, extent_root, path,
3157                                                     iref, refs_to_drop, is_data);
3158                         if (ret) {
3159                                 btrfs_abort_transaction(trans, ret);
3160                                 goto out;
3161                         }
3162                 }
3163         } else {
3164                 /* In this branch refs == 1 */
3165                 if (found_extent) {
3166                         if (is_data && refs_to_drop !=
3167                             extent_data_ref_count(path, iref)) {
3168                                 btrfs_crit(info,
3169                 "invalid refs_to_drop, current refs %u refs_to_drop %u",
3170                                            extent_data_ref_count(path, iref),
3171                                            refs_to_drop);
3172                                 btrfs_abort_transaction(trans, -EUCLEAN);
3173                                 goto err_dump;
3174                         }
3175                         if (iref) {
3176                                 if (path->slots[0] != extent_slot) {
3177                                         btrfs_crit(info,
3178 "invalid iref, extent item key (%llu %u %llu) doesn't have wanted iref",
3179                                                    key.objectid, key.type,
3180                                                    key.offset);
3181                                         btrfs_abort_transaction(trans, -EUCLEAN);
3182                                         goto err_dump;
3183                                 }
3184                         } else {
3185                                 /*
3186                                  * No inline ref, we must be at SHARED_* item,
3187                                  * And it's single ref, it must be:
3188                                  * |    extent_slot       ||extent_slot + 1|
3189                                  * [ EXTENT/METADATA_ITEM ][ SHARED_* ITEM ]
3190                                  */
3191                                 if (path->slots[0] != extent_slot + 1) {
3192                                         btrfs_crit(info,
3193         "invalid SHARED_* item, previous item is not EXTENT/METADATA_ITEM");
3194                                         btrfs_abort_transaction(trans, -EUCLEAN);
3195                                         goto err_dump;
3196                                 }
3197                                 path->slots[0] = extent_slot;
3198                                 num_to_del = 2;
3199                         }
3200                 }
3201
3202                 ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
3203                                       num_to_del);
3204                 if (ret) {
3205                         btrfs_abort_transaction(trans, ret);
3206                         goto out;
3207                 }
3208                 btrfs_release_path(path);
3209
3210                 ret = do_free_extent_accounting(trans, bytenr, num_bytes, is_data);
3211         }
3212         btrfs_release_path(path);
3213
3214 out:
3215         btrfs_free_path(path);
3216         return ret;
3217 err_dump:
3218         /*
3219          * Leaf dump can take up a lot of log buffer, so we only do full leaf
3220          * dump for debug build.
3221          */
3222         if (IS_ENABLED(CONFIG_BTRFS_DEBUG)) {
3223                 btrfs_crit(info, "path->slots[0]=%d extent_slot=%d",
3224                            path->slots[0], extent_slot);
3225                 btrfs_print_leaf(path->nodes[0]);
3226         }
3227
3228         btrfs_free_path(path);
3229         return -EUCLEAN;
3230 }
3231
3232 /*
3233  * when we free an block, it is possible (and likely) that we free the last
3234  * delayed ref for that extent as well.  This searches the delayed ref tree for
3235  * a given extent, and if there are no other delayed refs to be processed, it
3236  * removes it from the tree.
3237  */
3238 static noinline int check_ref_cleanup(struct btrfs_trans_handle *trans,
3239                                       u64 bytenr)
3240 {
3241         struct btrfs_delayed_ref_head *head;
3242         struct btrfs_delayed_ref_root *delayed_refs;
3243         int ret = 0;
3244
3245         delayed_refs = &trans->transaction->delayed_refs;
3246         spin_lock(&delayed_refs->lock);
3247         head = btrfs_find_delayed_ref_head(delayed_refs, bytenr);
3248         if (!head)
3249                 goto out_delayed_unlock;
3250
3251         spin_lock(&head->lock);
3252         if (!RB_EMPTY_ROOT(&head->ref_tree.rb_root))
3253                 goto out;
3254
3255         if (cleanup_extent_op(head) != NULL)
3256                 goto out;
3257
3258         /*
3259          * waiting for the lock here would deadlock.  If someone else has it
3260          * locked they are already in the process of dropping it anyway
3261          */
3262         if (!mutex_trylock(&head->mutex))
3263                 goto out;
3264
3265         btrfs_delete_ref_head(delayed_refs, head);
3266         head->processing = 0;
3267
3268         spin_unlock(&head->lock);
3269         spin_unlock(&delayed_refs->lock);
3270
3271         BUG_ON(head->extent_op);
3272         if (head->must_insert_reserved)
3273                 ret = 1;
3274
3275         btrfs_cleanup_ref_head_accounting(trans->fs_info, delayed_refs, head);
3276         mutex_unlock(&head->mutex);
3277         btrfs_put_delayed_ref_head(head);
3278         return ret;
3279 out:
3280         spin_unlock(&head->lock);
3281
3282 out_delayed_unlock:
3283         spin_unlock(&delayed_refs->lock);
3284         return 0;
3285 }
3286
3287 void btrfs_free_tree_block(struct btrfs_trans_handle *trans,
3288                            u64 root_id,
3289                            struct extent_buffer *buf,
3290                            u64 parent, int last_ref)
3291 {
3292         struct btrfs_fs_info *fs_info = trans->fs_info;
3293         struct btrfs_ref generic_ref = { 0 };
3294         int ret;
3295
3296         btrfs_init_generic_ref(&generic_ref, BTRFS_DROP_DELAYED_REF,
3297                                buf->start, buf->len, parent);
3298         btrfs_init_tree_ref(&generic_ref, btrfs_header_level(buf),
3299                             root_id, 0, false);
3300
3301         if (root_id != BTRFS_TREE_LOG_OBJECTID) {
3302                 btrfs_ref_tree_mod(fs_info, &generic_ref);
3303                 ret = btrfs_add_delayed_tree_ref(trans, &generic_ref, NULL);
3304                 BUG_ON(ret); /* -ENOMEM */
3305         }
3306
3307         if (last_ref && btrfs_header_generation(buf) == trans->transid) {
3308                 struct btrfs_block_group *cache;
3309                 bool must_pin = false;
3310
3311                 if (root_id != BTRFS_TREE_LOG_OBJECTID) {
3312                         ret = check_ref_cleanup(trans, buf->start);
3313                         if (!ret) {
3314                                 btrfs_redirty_list_add(trans->transaction, buf);
3315                                 goto out;
3316                         }
3317                 }
3318
3319                 cache = btrfs_lookup_block_group(fs_info, buf->start);
3320
3321                 if (btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
3322                         pin_down_extent(trans, cache, buf->start, buf->len, 1);
3323                         btrfs_put_block_group(cache);
3324                         goto out;
3325                 }
3326
3327                 /*
3328                  * If this is a leaf and there are tree mod log users, we may
3329                  * have recorded mod log operations that point to this leaf.
3330                  * So we must make sure no one reuses this leaf's extent before
3331                  * mod log operations are applied to a node, otherwise after
3332                  * rewinding a node using the mod log operations we get an
3333                  * inconsistent btree, as the leaf's extent may now be used as
3334                  * a node or leaf for another different btree.
3335                  * We are safe from races here because at this point no other
3336                  * node or root points to this extent buffer, so if after this
3337                  * check a new tree mod log user joins, it will not be able to
3338                  * find a node pointing to this leaf and record operations that
3339                  * point to this leaf.
3340                  */
3341                 if (btrfs_header_level(buf) == 0 &&
3342                     test_bit(BTRFS_FS_TREE_MOD_LOG_USERS, &fs_info->flags))
3343                         must_pin = true;
3344
3345                 if (must_pin || btrfs_is_zoned(fs_info)) {
3346                         btrfs_redirty_list_add(trans->transaction, buf);
3347                         pin_down_extent(trans, cache, buf->start, buf->len, 1);
3348                         btrfs_put_block_group(cache);
3349                         goto out;
3350                 }
3351
3352                 WARN_ON(test_bit(EXTENT_BUFFER_DIRTY, &buf->bflags));
3353
3354                 btrfs_add_free_space(cache, buf->start, buf->len);
3355                 btrfs_free_reserved_bytes(cache, buf->len, 0);
3356                 btrfs_put_block_group(cache);
3357                 trace_btrfs_reserved_extent_free(fs_info, buf->start, buf->len);
3358         }
3359 out:
3360         if (last_ref) {
3361                 /*
3362                  * Deleting the buffer, clear the corrupt flag since it doesn't
3363                  * matter anymore.
3364                  */
3365                 clear_bit(EXTENT_BUFFER_CORRUPT, &buf->bflags);
3366         }
3367 }
3368
3369 /* Can return -ENOMEM */
3370 int btrfs_free_extent(struct btrfs_trans_handle *trans, struct btrfs_ref *ref)
3371 {
3372         struct btrfs_fs_info *fs_info = trans->fs_info;
3373         int ret;
3374
3375         if (btrfs_is_testing(fs_info))
3376                 return 0;
3377
3378         /*
3379          * tree log blocks never actually go into the extent allocation
3380          * tree, just update pinning info and exit early.
3381          */
3382         if ((ref->type == BTRFS_REF_METADATA &&
3383              ref->tree_ref.owning_root == BTRFS_TREE_LOG_OBJECTID) ||
3384             (ref->type == BTRFS_REF_DATA &&
3385              ref->data_ref.owning_root == BTRFS_TREE_LOG_OBJECTID)) {
3386                 /* unlocks the pinned mutex */
3387                 btrfs_pin_extent(trans, ref->bytenr, ref->len, 1);
3388                 ret = 0;
3389         } else if (ref->type == BTRFS_REF_METADATA) {
3390                 ret = btrfs_add_delayed_tree_ref(trans, ref, NULL);
3391         } else {
3392                 ret = btrfs_add_delayed_data_ref(trans, ref, 0);
3393         }
3394
3395         if (!((ref->type == BTRFS_REF_METADATA &&
3396                ref->tree_ref.owning_root == BTRFS_TREE_LOG_OBJECTID) ||
3397               (ref->type == BTRFS_REF_DATA &&
3398                ref->data_ref.owning_root == BTRFS_TREE_LOG_OBJECTID)))
3399                 btrfs_ref_tree_mod(fs_info, ref);
3400
3401         return ret;
3402 }
3403
3404 enum btrfs_loop_type {
3405         LOOP_CACHING_NOWAIT,
3406         LOOP_CACHING_WAIT,
3407         LOOP_ALLOC_CHUNK,
3408         LOOP_NO_EMPTY_SIZE,
3409 };
3410
3411 static inline void
3412 btrfs_lock_block_group(struct btrfs_block_group *cache,
3413                        int delalloc)
3414 {
3415         if (delalloc)
3416                 down_read(&cache->data_rwsem);
3417 }
3418
3419 static inline void btrfs_grab_block_group(struct btrfs_block_group *cache,
3420                        int delalloc)
3421 {
3422         btrfs_get_block_group(cache);
3423         if (delalloc)
3424                 down_read(&cache->data_rwsem);
3425 }
3426
3427 static struct btrfs_block_group *btrfs_lock_cluster(
3428                    struct btrfs_block_group *block_group,
3429                    struct btrfs_free_cluster *cluster,
3430                    int delalloc)
3431         __acquires(&cluster->refill_lock)
3432 {
3433         struct btrfs_block_group *used_bg = NULL;
3434
3435         spin_lock(&cluster->refill_lock);
3436         while (1) {
3437                 used_bg = cluster->block_group;
3438                 if (!used_bg)
3439                         return NULL;
3440
3441                 if (used_bg == block_group)
3442                         return used_bg;
3443
3444                 btrfs_get_block_group(used_bg);
3445
3446                 if (!delalloc)
3447                         return used_bg;
3448
3449                 if (down_read_trylock(&used_bg->data_rwsem))
3450                         return used_bg;
3451
3452                 spin_unlock(&cluster->refill_lock);
3453
3454                 /* We should only have one-level nested. */
3455                 down_read_nested(&used_bg->data_rwsem, SINGLE_DEPTH_NESTING);
3456
3457                 spin_lock(&cluster->refill_lock);
3458                 if (used_bg == cluster->block_group)
3459                         return used_bg;
3460
3461                 up_read(&used_bg->data_rwsem);
3462                 btrfs_put_block_group(used_bg);
3463         }
3464 }
3465
3466 static inline void
3467 btrfs_release_block_group(struct btrfs_block_group *cache,
3468                          int delalloc)
3469 {
3470         if (delalloc)
3471                 up_read(&cache->data_rwsem);
3472         btrfs_put_block_group(cache);
3473 }
3474
3475 enum btrfs_extent_allocation_policy {
3476         BTRFS_EXTENT_ALLOC_CLUSTERED,
3477         BTRFS_EXTENT_ALLOC_ZONED,
3478 };
3479
3480 /*
3481  * Structure used internally for find_free_extent() function.  Wraps needed
3482  * parameters.
3483  */
3484 struct find_free_extent_ctl {
3485         /* Basic allocation info */
3486         u64 ram_bytes;
3487         u64 num_bytes;
3488         u64 min_alloc_size;
3489         u64 empty_size;
3490         u64 flags;
3491         int delalloc;
3492
3493         /* Where to start the search inside the bg */
3494         u64 search_start;
3495
3496         /* For clustered allocation */
3497         u64 empty_cluster;
3498         struct btrfs_free_cluster *last_ptr;
3499         bool use_cluster;
3500
3501         bool have_caching_bg;
3502         bool orig_have_caching_bg;
3503
3504         /* Allocation is called for tree-log */
3505         bool for_treelog;
3506
3507         /* Allocation is called for data relocation */
3508         bool for_data_reloc;
3509
3510         /* RAID index, converted from flags */
3511         int index;
3512
3513         /*
3514          * Current loop number, check find_free_extent_update_loop() for details
3515          */
3516         int loop;
3517
3518         /*
3519          * Whether we're refilling a cluster, if true we need to re-search
3520          * current block group but don't try to refill the cluster again.
3521          */
3522         bool retry_clustered;
3523
3524         /*
3525          * Whether we're updating free space cache, if true we need to re-search
3526          * current block group but don't try updating free space cache again.
3527          */
3528         bool retry_unclustered;
3529
3530         /* If current block group is cached */
3531         int cached;
3532
3533         /* Max contiguous hole found */
3534         u64 max_extent_size;
3535
3536         /* Total free space from free space cache, not always contiguous */
3537         u64 total_free_space;
3538
3539         /* Found result */
3540         u64 found_offset;
3541
3542         /* Hint where to start looking for an empty space */
3543         u64 hint_byte;
3544
3545         /* Allocation policy */
3546         enum btrfs_extent_allocation_policy policy;
3547 };
3548
3549
3550 /*
3551  * Helper function for find_free_extent().
3552  *
3553  * Return -ENOENT to inform caller that we need fallback to unclustered mode.
3554  * Return -EAGAIN to inform caller that we need to re-search this block group
3555  * Return >0 to inform caller that we find nothing
3556  * Return 0 means we have found a location and set ffe_ctl->found_offset.
3557  */
3558 static int find_free_extent_clustered(struct btrfs_block_group *bg,
3559                                       struct find_free_extent_ctl *ffe_ctl,
3560                                       struct btrfs_block_group **cluster_bg_ret)
3561 {
3562         struct btrfs_block_group *cluster_bg;
3563         struct btrfs_free_cluster *last_ptr = ffe_ctl->last_ptr;
3564         u64 aligned_cluster;
3565         u64 offset;
3566         int ret;
3567
3568         cluster_bg = btrfs_lock_cluster(bg, last_ptr, ffe_ctl->delalloc);
3569         if (!cluster_bg)
3570                 goto refill_cluster;
3571         if (cluster_bg != bg && (cluster_bg->ro ||
3572             !block_group_bits(cluster_bg, ffe_ctl->flags)))
3573                 goto release_cluster;
3574
3575         offset = btrfs_alloc_from_cluster(cluster_bg, last_ptr,
3576                         ffe_ctl->num_bytes, cluster_bg->start,
3577                         &ffe_ctl->max_extent_size);
3578         if (offset) {
3579                 /* We have a block, we're done */
3580                 spin_unlock(&last_ptr->refill_lock);
3581                 trace_btrfs_reserve_extent_cluster(cluster_bg,
3582                                 ffe_ctl->search_start, ffe_ctl->num_bytes);
3583                 *cluster_bg_ret = cluster_bg;
3584                 ffe_ctl->found_offset = offset;
3585                 return 0;
3586         }
3587         WARN_ON(last_ptr->block_group != cluster_bg);
3588
3589 release_cluster:
3590         /*
3591          * If we are on LOOP_NO_EMPTY_SIZE, we can't set up a new clusters, so
3592          * lets just skip it and let the allocator find whatever block it can
3593          * find. If we reach this point, we will have tried the cluster
3594          * allocator plenty of times and not have found anything, so we are
3595          * likely way too fragmented for the clustering stuff to find anything.
3596          *
3597          * However, if the cluster is taken from the current block group,
3598          * release the cluster first, so that we stand a better chance of
3599          * succeeding in the unclustered allocation.
3600          */
3601         if (ffe_ctl->loop >= LOOP_NO_EMPTY_SIZE && cluster_bg != bg) {
3602                 spin_unlock(&last_ptr->refill_lock);
3603                 btrfs_release_block_group(cluster_bg, ffe_ctl->delalloc);
3604                 return -ENOENT;
3605         }
3606
3607         /* This cluster didn't work out, free it and start over */
3608         btrfs_return_cluster_to_free_space(NULL, last_ptr);
3609
3610         if (cluster_bg != bg)
3611                 btrfs_release_block_group(cluster_bg, ffe_ctl->delalloc);
3612
3613 refill_cluster:
3614         if (ffe_ctl->loop >= LOOP_NO_EMPTY_SIZE) {
3615                 spin_unlock(&last_ptr->refill_lock);
3616                 return -ENOENT;
3617         }
3618
3619         aligned_cluster = max_t(u64,
3620                         ffe_ctl->empty_cluster + ffe_ctl->empty_size,
3621                         bg->full_stripe_len);
3622         ret = btrfs_find_space_cluster(bg, last_ptr, ffe_ctl->search_start,
3623                         ffe_ctl->num_bytes, aligned_cluster);
3624         if (ret == 0) {
3625                 /* Now pull our allocation out of this cluster */
3626                 offset = btrfs_alloc_from_cluster(bg, last_ptr,
3627                                 ffe_ctl->num_bytes, ffe_ctl->search_start,
3628                                 &ffe_ctl->max_extent_size);
3629                 if (offset) {
3630                         /* We found one, proceed */
3631                         spin_unlock(&last_ptr->refill_lock);
3632                         trace_btrfs_reserve_extent_cluster(bg,
3633                                         ffe_ctl->search_start,
3634                                         ffe_ctl->num_bytes);
3635                         ffe_ctl->found_offset = offset;
3636                         return 0;
3637                 }
3638         } else if (!ffe_ctl->cached && ffe_ctl->loop > LOOP_CACHING_NOWAIT &&
3639                    !ffe_ctl->retry_clustered) {
3640                 spin_unlock(&last_ptr->refill_lock);
3641
3642                 ffe_ctl->retry_clustered = true;
3643                 btrfs_wait_block_group_cache_progress(bg, ffe_ctl->num_bytes +
3644                                 ffe_ctl->empty_cluster + ffe_ctl->empty_size);
3645                 return -EAGAIN;
3646         }
3647         /*
3648          * At this point we either didn't find a cluster or we weren't able to
3649          * allocate a block from our cluster.  Free the cluster we've been
3650          * trying to use, and go to the next block group.
3651          */
3652         btrfs_return_cluster_to_free_space(NULL, last_ptr);
3653         spin_unlock(&last_ptr->refill_lock);
3654         return 1;
3655 }
3656
3657 /*
3658  * Return >0 to inform caller that we find nothing
3659  * Return 0 when we found an free extent and set ffe_ctrl->found_offset
3660  * Return -EAGAIN to inform caller that we need to re-search this block group
3661  */
3662 static int find_free_extent_unclustered(struct btrfs_block_group *bg,
3663                                         struct find_free_extent_ctl *ffe_ctl)
3664 {
3665         struct btrfs_free_cluster *last_ptr = ffe_ctl->last_ptr;
3666         u64 offset;
3667
3668         /*
3669          * We are doing an unclustered allocation, set the fragmented flag so
3670          * we don't bother trying to setup a cluster again until we get more
3671          * space.
3672          */
3673         if (unlikely(last_ptr)) {
3674                 spin_lock(&last_ptr->lock);
3675                 last_ptr->fragmented = 1;
3676                 spin_unlock(&last_ptr->lock);
3677         }
3678         if (ffe_ctl->cached) {
3679                 struct btrfs_free_space_ctl *free_space_ctl;
3680
3681                 free_space_ctl = bg->free_space_ctl;
3682                 spin_lock(&free_space_ctl->tree_lock);
3683                 if (free_space_ctl->free_space <
3684                     ffe_ctl->num_bytes + ffe_ctl->empty_cluster +
3685                     ffe_ctl->empty_size) {
3686                         ffe_ctl->total_free_space = max_t(u64,
3687                                         ffe_ctl->total_free_space,
3688                                         free_space_ctl->free_space);
3689                         spin_unlock(&free_space_ctl->tree_lock);
3690                         return 1;
3691                 }
3692                 spin_unlock(&free_space_ctl->tree_lock);
3693         }
3694
3695         offset = btrfs_find_space_for_alloc(bg, ffe_ctl->search_start,
3696                         ffe_ctl->num_bytes, ffe_ctl->empty_size,
3697                         &ffe_ctl->max_extent_size);
3698
3699         /*
3700          * If we didn't find a chunk, and we haven't failed on this block group
3701          * before, and this block group is in the middle of caching and we are
3702          * ok with waiting, then go ahead and wait for progress to be made, and
3703          * set @retry_unclustered to true.
3704          *
3705          * If @retry_unclustered is true then we've already waited on this
3706          * block group once and should move on to the next block group.
3707          */
3708         if (!offset && !ffe_ctl->retry_unclustered && !ffe_ctl->cached &&
3709             ffe_ctl->loop > LOOP_CACHING_NOWAIT) {
3710                 btrfs_wait_block_group_cache_progress(bg, ffe_ctl->num_bytes +
3711                                                       ffe_ctl->empty_size);
3712                 ffe_ctl->retry_unclustered = true;
3713                 return -EAGAIN;
3714         } else if (!offset) {
3715                 return 1;
3716         }
3717         ffe_ctl->found_offset = offset;
3718         return 0;
3719 }
3720
3721 static int do_allocation_clustered(struct btrfs_block_group *block_group,
3722                                    struct find_free_extent_ctl *ffe_ctl,
3723                                    struct btrfs_block_group **bg_ret)
3724 {
3725         int ret;
3726
3727         /* We want to try and use the cluster allocator, so lets look there */
3728         if (ffe_ctl->last_ptr && ffe_ctl->use_cluster) {
3729                 ret = find_free_extent_clustered(block_group, ffe_ctl, bg_ret);
3730                 if (ret >= 0 || ret == -EAGAIN)
3731                         return ret;
3732                 /* ret == -ENOENT case falls through */
3733         }
3734
3735         return find_free_extent_unclustered(block_group, ffe_ctl);
3736 }
3737
3738 /*
3739  * Tree-log block group locking
3740  * ============================
3741  *
3742  * fs_info::treelog_bg_lock protects the fs_info::treelog_bg which
3743  * indicates the starting address of a block group, which is reserved only
3744  * for tree-log metadata.
3745  *
3746  * Lock nesting
3747  * ============
3748  *
3749  * space_info::lock
3750  *   block_group::lock
3751  *     fs_info::treelog_bg_lock
3752  */
3753
3754 /*
3755  * Simple allocator for sequential-only block group. It only allows sequential
3756  * allocation. No need to play with trees. This function also reserves the
3757  * bytes as in btrfs_add_reserved_bytes.
3758  */
3759 static int do_allocation_zoned(struct btrfs_block_group *block_group,
3760                                struct find_free_extent_ctl *ffe_ctl,
3761                                struct btrfs_block_group **bg_ret)
3762 {
3763         struct btrfs_fs_info *fs_info = block_group->fs_info;
3764         struct btrfs_space_info *space_info = block_group->space_info;
3765         struct btrfs_free_space_ctl *ctl = block_group->free_space_ctl;
3766         u64 start = block_group->start;
3767         u64 num_bytes = ffe_ctl->num_bytes;
3768         u64 avail;
3769         u64 bytenr = block_group->start;
3770         u64 log_bytenr;
3771         u64 data_reloc_bytenr;
3772         int ret = 0;
3773         bool skip = false;
3774
3775         ASSERT(btrfs_is_zoned(block_group->fs_info));
3776
3777         /*
3778          * Do not allow non-tree-log blocks in the dedicated tree-log block
3779          * group, and vice versa.
3780          */
3781         spin_lock(&fs_info->treelog_bg_lock);
3782         log_bytenr = fs_info->treelog_bg;
3783         if (log_bytenr && ((ffe_ctl->for_treelog && bytenr != log_bytenr) ||
3784                            (!ffe_ctl->for_treelog && bytenr == log_bytenr)))
3785                 skip = true;
3786         spin_unlock(&fs_info->treelog_bg_lock);
3787         if (skip)
3788                 return 1;
3789
3790         /*
3791          * Do not allow non-relocation blocks in the dedicated relocation block
3792          * group, and vice versa.
3793          */
3794         spin_lock(&fs_info->relocation_bg_lock);
3795         data_reloc_bytenr = fs_info->data_reloc_bg;
3796         if (data_reloc_bytenr &&
3797             ((ffe_ctl->for_data_reloc && bytenr != data_reloc_bytenr) ||
3798              (!ffe_ctl->for_data_reloc && bytenr == data_reloc_bytenr)))
3799                 skip = true;
3800         spin_unlock(&fs_info->relocation_bg_lock);
3801         if (skip)
3802                 return 1;
3803
3804         /* Check RO and no space case before trying to activate it */
3805         spin_lock(&block_group->lock);
3806         if (block_group->ro ||
3807             block_group->alloc_offset == block_group->zone_capacity) {
3808                 ret = 1;
3809                 /*
3810                  * May need to clear fs_info->{treelog,data_reloc}_bg.
3811                  * Return the error after taking the locks.
3812                  */
3813         }
3814         spin_unlock(&block_group->lock);
3815
3816         if (!ret && !btrfs_zone_activate(block_group)) {
3817                 ret = 1;
3818                 /*
3819                  * May need to clear fs_info->{treelog,data_reloc}_bg.
3820                  * Return the error after taking the locks.
3821                  */
3822         }
3823
3824         spin_lock(&space_info->lock);
3825         spin_lock(&block_group->lock);
3826         spin_lock(&fs_info->treelog_bg_lock);
3827         spin_lock(&fs_info->relocation_bg_lock);
3828
3829         if (ret)
3830                 goto out;
3831
3832         ASSERT(!ffe_ctl->for_treelog ||
3833                block_group->start == fs_info->treelog_bg ||
3834                fs_info->treelog_bg == 0);
3835         ASSERT(!ffe_ctl->for_data_reloc ||
3836                block_group->start == fs_info->data_reloc_bg ||
3837                fs_info->data_reloc_bg == 0);
3838
3839         if (block_group->ro) {
3840                 ret = 1;
3841                 goto out;
3842         }
3843
3844         /*
3845          * Do not allow currently using block group to be tree-log dedicated
3846          * block group.
3847          */
3848         if (ffe_ctl->for_treelog && !fs_info->treelog_bg &&
3849             (block_group->used || block_group->reserved)) {
3850                 ret = 1;
3851                 goto out;
3852         }
3853
3854         /*
3855          * Do not allow currently used block group to be the data relocation
3856          * dedicated block group.
3857          */
3858         if (ffe_ctl->for_data_reloc && !fs_info->data_reloc_bg &&
3859             (block_group->used || block_group->reserved)) {
3860                 ret = 1;
3861                 goto out;
3862         }
3863
3864         WARN_ON_ONCE(block_group->alloc_offset > block_group->zone_capacity);
3865         avail = block_group->zone_capacity - block_group->alloc_offset;
3866         if (avail < num_bytes) {
3867                 if (ffe_ctl->max_extent_size < avail) {
3868                         /*
3869                          * With sequential allocator, free space is always
3870                          * contiguous
3871                          */
3872                         ffe_ctl->max_extent_size = avail;
3873                         ffe_ctl->total_free_space = avail;
3874                 }
3875                 ret = 1;
3876                 goto out;
3877         }
3878
3879         if (ffe_ctl->for_treelog && !fs_info->treelog_bg)
3880                 fs_info->treelog_bg = block_group->start;
3881
3882         if (ffe_ctl->for_data_reloc && !fs_info->data_reloc_bg)
3883                 fs_info->data_reloc_bg = block_group->start;
3884
3885         ffe_ctl->found_offset = start + block_group->alloc_offset;
3886         block_group->alloc_offset += num_bytes;
3887         spin_lock(&ctl->tree_lock);
3888         ctl->free_space -= num_bytes;
3889         spin_unlock(&ctl->tree_lock);
3890
3891         /*
3892          * We do not check if found_offset is aligned to stripesize. The
3893          * address is anyway rewritten when using zone append writing.
3894          */
3895
3896         ffe_ctl->search_start = ffe_ctl->found_offset;
3897
3898 out:
3899         if (ret && ffe_ctl->for_treelog)
3900                 fs_info->treelog_bg = 0;
3901         if (ret && ffe_ctl->for_data_reloc)
3902                 fs_info->data_reloc_bg = 0;
3903         spin_unlock(&fs_info->relocation_bg_lock);
3904         spin_unlock(&fs_info->treelog_bg_lock);
3905         spin_unlock(&block_group->lock);
3906         spin_unlock(&space_info->lock);
3907         return ret;
3908 }
3909
3910 static int do_allocation(struct btrfs_block_group *block_group,
3911                          struct find_free_extent_ctl *ffe_ctl,
3912                          struct btrfs_block_group **bg_ret)
3913 {
3914         switch (ffe_ctl->policy) {
3915         case BTRFS_EXTENT_ALLOC_CLUSTERED:
3916                 return do_allocation_clustered(block_group, ffe_ctl, bg_ret);
3917         case BTRFS_EXTENT_ALLOC_ZONED:
3918                 return do_allocation_zoned(block_group, ffe_ctl, bg_ret);
3919         default:
3920                 BUG();
3921         }
3922 }
3923
3924 static void release_block_group(struct btrfs_block_group *block_group,
3925                                 struct find_free_extent_ctl *ffe_ctl,
3926                                 int delalloc)
3927 {
3928         switch (ffe_ctl->policy) {
3929         case BTRFS_EXTENT_ALLOC_CLUSTERED:
3930                 ffe_ctl->retry_clustered = false;
3931                 ffe_ctl->retry_unclustered = false;
3932                 break;
3933         case BTRFS_EXTENT_ALLOC_ZONED:
3934                 /* Nothing to do */
3935                 break;
3936         default:
3937                 BUG();
3938         }
3939
3940         BUG_ON(btrfs_bg_flags_to_raid_index(block_group->flags) !=
3941                ffe_ctl->index);
3942         btrfs_release_block_group(block_group, delalloc);
3943 }
3944
3945 static void found_extent_clustered(struct find_free_extent_ctl *ffe_ctl,
3946                                    struct btrfs_key *ins)
3947 {
3948         struct btrfs_free_cluster *last_ptr = ffe_ctl->last_ptr;
3949
3950         if (!ffe_ctl->use_cluster && last_ptr) {
3951                 spin_lock(&last_ptr->lock);
3952                 last_ptr->window_start = ins->objectid;
3953                 spin_unlock(&last_ptr->lock);
3954         }
3955 }
3956
3957 static void found_extent(struct find_free_extent_ctl *ffe_ctl,
3958                          struct btrfs_key *ins)
3959 {
3960         switch (ffe_ctl->policy) {
3961         case BTRFS_EXTENT_ALLOC_CLUSTERED:
3962                 found_extent_clustered(ffe_ctl, ins);
3963                 break;
3964         case BTRFS_EXTENT_ALLOC_ZONED:
3965                 /* Nothing to do */
3966                 break;
3967         default:
3968                 BUG();
3969         }
3970 }
3971
3972 static bool can_allocate_chunk(struct btrfs_fs_info *fs_info,
3973                                struct find_free_extent_ctl *ffe_ctl)
3974 {
3975         switch (ffe_ctl->policy) {
3976         case BTRFS_EXTENT_ALLOC_CLUSTERED:
3977                 return true;
3978         case BTRFS_EXTENT_ALLOC_ZONED:
3979                 /*
3980                  * If we have enough free space left in an already
3981                  * active block group and we can't activate any other
3982                  * zone now, do not allow allocating a new chunk and
3983                  * let find_free_extent() retry with a smaller size.
3984                  */
3985                 if (ffe_ctl->max_extent_size >= ffe_ctl->min_alloc_size &&
3986                     !btrfs_can_activate_zone(fs_info->fs_devices, ffe_ctl->flags))
3987                         return false;
3988                 return true;
3989         default:
3990                 BUG();
3991         }
3992 }
3993
3994 static int chunk_allocation_failed(struct find_free_extent_ctl *ffe_ctl)
3995 {
3996         switch (ffe_ctl->policy) {
3997         case BTRFS_EXTENT_ALLOC_CLUSTERED:
3998                 /*
3999                  * If we can't allocate a new chunk we've already looped through
4000                  * at least once, move on to the NO_EMPTY_SIZE case.
4001                  */
4002                 ffe_ctl->loop = LOOP_NO_EMPTY_SIZE;
4003                 return 0;
4004         case BTRFS_EXTENT_ALLOC_ZONED:
4005                 /* Give up here */
4006                 return -ENOSPC;
4007         default:
4008                 BUG();
4009         }
4010 }
4011
4012 /*
4013  * Return >0 means caller needs to re-search for free extent
4014  * Return 0 means we have the needed free extent.
4015  * Return <0 means we failed to locate any free extent.
4016  */
4017 static int find_free_extent_update_loop(struct btrfs_fs_info *fs_info,
4018                                         struct btrfs_key *ins,
4019                                         struct find_free_extent_ctl *ffe_ctl,
4020                                         bool full_search)
4021 {
4022         struct btrfs_root *root = fs_info->chunk_root;
4023         int ret;
4024
4025         if ((ffe_ctl->loop == LOOP_CACHING_NOWAIT) &&
4026             ffe_ctl->have_caching_bg && !ffe_ctl->orig_have_caching_bg)
4027                 ffe_ctl->orig_have_caching_bg = true;
4028
4029         if (ins->objectid) {
4030                 found_extent(ffe_ctl, ins);
4031                 return 0;
4032         }
4033
4034         if (ffe_ctl->loop >= LOOP_CACHING_WAIT && ffe_ctl->have_caching_bg)
4035                 return 1;
4036
4037         ffe_ctl->index++;
4038         if (ffe_ctl->index < BTRFS_NR_RAID_TYPES)
4039                 return 1;
4040
4041         /*
4042          * LOOP_CACHING_NOWAIT, search partially cached block groups, kicking
4043          *                      caching kthreads as we move along
4044          * LOOP_CACHING_WAIT, search everything, and wait if our bg is caching
4045          * LOOP_ALLOC_CHUNK, force a chunk allocation and try again
4046          * LOOP_NO_EMPTY_SIZE, set empty_size and empty_cluster to 0 and try
4047          *                     again
4048          */
4049         if (ffe_ctl->loop < LOOP_NO_EMPTY_SIZE) {
4050                 ffe_ctl->index = 0;
4051                 if (ffe_ctl->loop == LOOP_CACHING_NOWAIT) {
4052                         /*
4053                          * We want to skip the LOOP_CACHING_WAIT step if we
4054                          * don't have any uncached bgs and we've already done a
4055                          * full search through.
4056                          */
4057                         if (ffe_ctl->orig_have_caching_bg || !full_search)
4058                                 ffe_ctl->loop = LOOP_CACHING_WAIT;
4059                         else
4060                                 ffe_ctl->loop = LOOP_ALLOC_CHUNK;
4061                 } else {
4062                         ffe_ctl->loop++;
4063                 }
4064
4065                 if (ffe_ctl->loop == LOOP_ALLOC_CHUNK) {
4066                         struct btrfs_trans_handle *trans;
4067                         int exist = 0;
4068
4069                         /*Check if allocation policy allows to create a new chunk */
4070                         if (!can_allocate_chunk(fs_info, ffe_ctl))
4071                                 return -ENOSPC;
4072
4073                         trans = current->journal_info;
4074                         if (trans)
4075                                 exist = 1;
4076                         else
4077                                 trans = btrfs_join_transaction(root);
4078
4079                         if (IS_ERR(trans)) {
4080                                 ret = PTR_ERR(trans);
4081                                 return ret;
4082                         }
4083
4084                         ret = btrfs_chunk_alloc(trans, ffe_ctl->flags,
4085                                                 CHUNK_ALLOC_FORCE);
4086
4087                         /* Do not bail out on ENOSPC since we can do more. */
4088                         if (ret == -ENOSPC)
4089                                 ret = chunk_allocation_failed(ffe_ctl);
4090                         else if (ret < 0)
4091                                 btrfs_abort_transaction(trans, ret);
4092                         else
4093                                 ret = 0;
4094                         if (!exist)
4095                                 btrfs_end_transaction(trans);
4096                         if (ret)
4097                                 return ret;
4098                 }
4099
4100                 if (ffe_ctl->loop == LOOP_NO_EMPTY_SIZE) {
4101                         if (ffe_ctl->policy != BTRFS_EXTENT_ALLOC_CLUSTERED)
4102                                 return -ENOSPC;
4103
4104                         /*
4105                          * Don't loop again if we already have no empty_size and
4106                          * no empty_cluster.
4107                          */
4108                         if (ffe_ctl->empty_size == 0 &&
4109                             ffe_ctl->empty_cluster == 0)
4110                                 return -ENOSPC;
4111                         ffe_ctl->empty_size = 0;
4112                         ffe_ctl->empty_cluster = 0;
4113                 }
4114                 return 1;
4115         }
4116         return -ENOSPC;
4117 }
4118
4119 static int prepare_allocation_clustered(struct btrfs_fs_info *fs_info,
4120                                         struct find_free_extent_ctl *ffe_ctl,
4121                                         struct btrfs_space_info *space_info,
4122                                         struct btrfs_key *ins)
4123 {
4124         /*
4125          * If our free space is heavily fragmented we may not be able to make
4126          * big contiguous allocations, so instead of doing the expensive search
4127          * for free space, simply return ENOSPC with our max_extent_size so we
4128          * can go ahead and search for a more manageable chunk.
4129          *
4130          * If our max_extent_size is large enough for our allocation simply
4131          * disable clustering since we will likely not be able to find enough
4132          * space to create a cluster and induce latency trying.
4133          */
4134         if (space_info->max_extent_size) {
4135                 spin_lock(&space_info->lock);
4136                 if (space_info->max_extent_size &&
4137                     ffe_ctl->num_bytes > space_info->max_extent_size) {
4138                         ins->offset = space_info->max_extent_size;
4139                         spin_unlock(&space_info->lock);
4140                         return -ENOSPC;
4141                 } else if (space_info->max_extent_size) {
4142                         ffe_ctl->use_cluster = false;
4143                 }
4144                 spin_unlock(&space_info->lock);
4145         }
4146
4147         ffe_ctl->last_ptr = fetch_cluster_info(fs_info, space_info,
4148                                                &ffe_ctl->empty_cluster);
4149         if (ffe_ctl->last_ptr) {
4150                 struct btrfs_free_cluster *last_ptr = ffe_ctl->last_ptr;
4151
4152                 spin_lock(&last_ptr->lock);
4153                 if (last_ptr->block_group)
4154                         ffe_ctl->hint_byte = last_ptr->window_start;
4155                 if (last_ptr->fragmented) {
4156                         /*
4157                          * We still set window_start so we can keep track of the
4158                          * last place we found an allocation to try and save
4159                          * some time.
4160                          */
4161                         ffe_ctl->hint_byte = last_ptr->window_start;
4162                         ffe_ctl->use_cluster = false;
4163                 }
4164                 spin_unlock(&last_ptr->lock);
4165         }
4166
4167         return 0;
4168 }
4169
4170 static int prepare_allocation(struct btrfs_fs_info *fs_info,
4171                               struct find_free_extent_ctl *ffe_ctl,
4172                               struct btrfs_space_info *space_info,
4173                               struct btrfs_key *ins)
4174 {
4175         switch (ffe_ctl->policy) {
4176         case BTRFS_EXTENT_ALLOC_CLUSTERED:
4177                 return prepare_allocation_clustered(fs_info, ffe_ctl,
4178                                                     space_info, ins);
4179         case BTRFS_EXTENT_ALLOC_ZONED:
4180                 if (ffe_ctl->for_treelog) {
4181                         spin_lock(&fs_info->treelog_bg_lock);
4182                         if (fs_info->treelog_bg)
4183                                 ffe_ctl->hint_byte = fs_info->treelog_bg;
4184                         spin_unlock(&fs_info->treelog_bg_lock);
4185                 }
4186                 if (ffe_ctl->for_data_reloc) {
4187                         spin_lock(&fs_info->relocation_bg_lock);
4188                         if (fs_info->data_reloc_bg)
4189                                 ffe_ctl->hint_byte = fs_info->data_reloc_bg;
4190                         spin_unlock(&fs_info->relocation_bg_lock);
4191                 }
4192                 return 0;
4193         default:
4194                 BUG();
4195         }
4196 }
4197
4198 /*
4199  * walks the btree of allocated extents and find a hole of a given size.
4200  * The key ins is changed to record the hole:
4201  * ins->objectid == start position
4202  * ins->flags = BTRFS_EXTENT_ITEM_KEY
4203  * ins->offset == the size of the hole.
4204  * Any available blocks before search_start are skipped.
4205  *
4206  * If there is no suitable free space, we will record the max size of
4207  * the free space extent currently.
4208  *
4209  * The overall logic and call chain:
4210  *
4211  * find_free_extent()
4212  * |- Iterate through all block groups
4213  * |  |- Get a valid block group
4214  * |  |- Try to do clustered allocation in that block group
4215  * |  |- Try to do unclustered allocation in that block group
4216  * |  |- Check if the result is valid
4217  * |  |  |- If valid, then exit
4218  * |  |- Jump to next block group
4219  * |
4220  * |- Push harder to find free extents
4221  *    |- If not found, re-iterate all block groups
4222  */
4223 static noinline int find_free_extent(struct btrfs_root *root,
4224                                      struct btrfs_key *ins,
4225                                      struct find_free_extent_ctl *ffe_ctl)
4226 {
4227         struct btrfs_fs_info *fs_info = root->fs_info;
4228         int ret = 0;
4229         int cache_block_group_error = 0;
4230         struct btrfs_block_group *block_group = NULL;
4231         struct btrfs_space_info *space_info;
4232         bool full_search = false;
4233
4234         WARN_ON(ffe_ctl->num_bytes < fs_info->sectorsize);
4235
4236         ffe_ctl->search_start = 0;
4237         /* For clustered allocation */
4238         ffe_ctl->empty_cluster = 0;
4239         ffe_ctl->last_ptr = NULL;
4240         ffe_ctl->use_cluster = true;
4241         ffe_ctl->have_caching_bg = false;
4242         ffe_ctl->orig_have_caching_bg = false;
4243         ffe_ctl->index = btrfs_bg_flags_to_raid_index(ffe_ctl->flags);
4244         ffe_ctl->loop = 0;
4245         /* For clustered allocation */
4246         ffe_ctl->retry_clustered = false;
4247         ffe_ctl->retry_unclustered = false;
4248         ffe_ctl->cached = 0;
4249         ffe_ctl->max_extent_size = 0;
4250         ffe_ctl->total_free_space = 0;
4251         ffe_ctl->found_offset = 0;
4252         ffe_ctl->policy = BTRFS_EXTENT_ALLOC_CLUSTERED;
4253
4254         if (btrfs_is_zoned(fs_info))
4255                 ffe_ctl->policy = BTRFS_EXTENT_ALLOC_ZONED;
4256
4257         ins->type = BTRFS_EXTENT_ITEM_KEY;
4258         ins->objectid = 0;
4259         ins->offset = 0;
4260
4261         trace_find_free_extent(root, ffe_ctl->num_bytes, ffe_ctl->empty_size,
4262                                ffe_ctl->flags);
4263
4264         space_info = btrfs_find_space_info(fs_info, ffe_ctl->flags);
4265         if (!space_info) {
4266                 btrfs_err(fs_info, "No space info for %llu", ffe_ctl->flags);
4267                 return -ENOSPC;
4268         }
4269
4270         ret = prepare_allocation(fs_info, ffe_ctl, space_info, ins);
4271         if (ret < 0)
4272                 return ret;
4273
4274         ffe_ctl->search_start = max(ffe_ctl->search_start,
4275                                     first_logical_byte(fs_info, 0));
4276         ffe_ctl->search_start = max(ffe_ctl->search_start, ffe_ctl->hint_byte);
4277         if (ffe_ctl->search_start == ffe_ctl->hint_byte) {
4278                 block_group = btrfs_lookup_block_group(fs_info,
4279                                                        ffe_ctl->search_start);
4280                 /*
4281                  * we don't want to use the block group if it doesn't match our
4282                  * allocation bits, or if its not cached.
4283                  *
4284                  * However if we are re-searching with an ideal block group
4285                  * picked out then we don't care that the block group is cached.
4286                  */
4287                 if (block_group && block_group_bits(block_group, ffe_ctl->flags) &&
4288                     block_group->cached != BTRFS_CACHE_NO) {
4289                         down_read(&space_info->groups_sem);
4290                         if (list_empty(&block_group->list) ||
4291                             block_group->ro) {
4292                                 /*
4293                                  * someone is removing this block group,
4294                                  * we can't jump into the have_block_group
4295                                  * target because our list pointers are not
4296                                  * valid
4297                                  */
4298                                 btrfs_put_block_group(block_group);
4299                                 up_read(&space_info->groups_sem);
4300                         } else {
4301                                 ffe_ctl->index = btrfs_bg_flags_to_raid_index(
4302                                                         block_group->flags);
4303                                 btrfs_lock_block_group(block_group,
4304                                                        ffe_ctl->delalloc);
4305                                 goto have_block_group;
4306                         }
4307                 } else if (block_group) {
4308                         btrfs_put_block_group(block_group);
4309                 }
4310         }
4311 search:
4312         ffe_ctl->have_caching_bg = false;
4313         if (ffe_ctl->index == btrfs_bg_flags_to_raid_index(ffe_ctl->flags) ||
4314             ffe_ctl->index == 0)
4315                 full_search = true;
4316         down_read(&space_info->groups_sem);
4317         list_for_each_entry(block_group,
4318                             &space_info->block_groups[ffe_ctl->index], list) {
4319                 struct btrfs_block_group *bg_ret;
4320
4321                 /* If the block group is read-only, we can skip it entirely. */
4322                 if (unlikely(block_group->ro)) {
4323                         if (ffe_ctl->for_treelog)
4324                                 btrfs_clear_treelog_bg(block_group);
4325                         if (ffe_ctl->for_data_reloc)
4326                                 btrfs_clear_data_reloc_bg(block_group);
4327                         continue;
4328                 }
4329
4330                 btrfs_grab_block_group(block_group, ffe_ctl->delalloc);
4331                 ffe_ctl->search_start = block_group->start;
4332
4333                 /*
4334                  * this can happen if we end up cycling through all the
4335                  * raid types, but we want to make sure we only allocate
4336                  * for the proper type.
4337                  */
4338                 if (!block_group_bits(block_group, ffe_ctl->flags)) {
4339                         u64 extra = BTRFS_BLOCK_GROUP_DUP |
4340                                 BTRFS_BLOCK_GROUP_RAID1_MASK |
4341                                 BTRFS_BLOCK_GROUP_RAID56_MASK |
4342                                 BTRFS_BLOCK_GROUP_RAID10;
4343
4344                         /*
4345                          * if they asked for extra copies and this block group
4346                          * doesn't provide them, bail.  This does allow us to
4347                          * fill raid0 from raid1.
4348                          */
4349                         if ((ffe_ctl->flags & extra) && !(block_group->flags & extra))
4350                                 goto loop;
4351
4352                         /*
4353                          * This block group has different flags than we want.
4354                          * It's possible that we have MIXED_GROUP flag but no
4355                          * block group is mixed.  Just skip such block group.
4356                          */
4357                         btrfs_release_block_group(block_group, ffe_ctl->delalloc);
4358                         continue;
4359                 }
4360
4361 have_block_group:
4362                 ffe_ctl->cached = btrfs_block_group_done(block_group);
4363                 if (unlikely(!ffe_ctl->cached)) {
4364                         ffe_ctl->have_caching_bg = true;
4365                         ret = btrfs_cache_block_group(block_group, 0);
4366
4367                         /*
4368                          * If we get ENOMEM here or something else we want to
4369                          * try other block groups, because it may not be fatal.
4370                          * However if we can't find anything else we need to
4371                          * save our return here so that we return the actual
4372                          * error that caused problems, not ENOSPC.
4373                          */
4374                         if (ret < 0) {
4375                                 if (!cache_block_group_error)
4376                                         cache_block_group_error = ret;
4377                                 ret = 0;
4378                                 goto loop;
4379                         }
4380                         ret = 0;
4381                 }
4382
4383                 if (unlikely(block_group->cached == BTRFS_CACHE_ERROR))
4384                         goto loop;
4385
4386                 bg_ret = NULL;
4387                 ret = do_allocation(block_group, ffe_ctl, &bg_ret);
4388                 if (ret == 0) {
4389                         if (bg_ret && bg_ret != block_group) {
4390                                 btrfs_release_block_group(block_group,
4391                                                           ffe_ctl->delalloc);
4392                                 block_group = bg_ret;
4393                         }
4394                 } else if (ret == -EAGAIN) {
4395                         goto have_block_group;
4396                 } else if (ret > 0) {
4397                         goto loop;
4398                 }
4399
4400                 /* Checks */
4401                 ffe_ctl->search_start = round_up(ffe_ctl->found_offset,
4402                                                  fs_info->stripesize);
4403
4404                 /* move on to the next group */
4405                 if (ffe_ctl->search_start + ffe_ctl->num_bytes >
4406                     block_group->start + block_group->length) {
4407                         btrfs_add_free_space_unused(block_group,
4408                                             ffe_ctl->found_offset,
4409                                             ffe_ctl->num_bytes);
4410                         goto loop;
4411                 }
4412
4413                 if (ffe_ctl->found_offset < ffe_ctl->search_start)
4414                         btrfs_add_free_space_unused(block_group,
4415                                         ffe_ctl->found_offset,
4416                                         ffe_ctl->search_start - ffe_ctl->found_offset);
4417
4418                 ret = btrfs_add_reserved_bytes(block_group, ffe_ctl->ram_bytes,
4419                                                ffe_ctl->num_bytes,
4420                                                ffe_ctl->delalloc);
4421                 if (ret == -EAGAIN) {
4422                         btrfs_add_free_space_unused(block_group,
4423                                         ffe_ctl->found_offset,
4424                                         ffe_ctl->num_bytes);
4425                         goto loop;
4426                 }
4427                 btrfs_inc_block_group_reservations(block_group);
4428
4429                 /* we are all good, lets return */
4430                 ins->objectid = ffe_ctl->search_start;
4431                 ins->offset = ffe_ctl->num_bytes;
4432
4433                 trace_btrfs_reserve_extent(block_group, ffe_ctl->search_start,
4434                                            ffe_ctl->num_bytes);
4435                 btrfs_release_block_group(block_group, ffe_ctl->delalloc);
4436                 break;
4437 loop:
4438                 release_block_group(block_group, ffe_ctl, ffe_ctl->delalloc);
4439                 cond_resched();
4440         }
4441         up_read(&space_info->groups_sem);
4442
4443         ret = find_free_extent_update_loop(fs_info, ins, ffe_ctl, full_search);
4444         if (ret > 0)
4445                 goto search;
4446
4447         if (ret == -ENOSPC && !cache_block_group_error) {
4448                 /*
4449                  * Use ffe_ctl->total_free_space as fallback if we can't find
4450                  * any contiguous hole.
4451                  */
4452                 if (!ffe_ctl->max_extent_size)
4453                         ffe_ctl->max_extent_size = ffe_ctl->total_free_space;
4454                 spin_lock(&space_info->lock);
4455                 space_info->max_extent_size = ffe_ctl->max_extent_size;
4456                 spin_unlock(&space_info->lock);
4457                 ins->offset = ffe_ctl->max_extent_size;
4458         } else if (ret == -ENOSPC) {
4459                 ret = cache_block_group_error;
4460         }
4461         return ret;
4462 }
4463
4464 /*
4465  * btrfs_reserve_extent - entry point to the extent allocator. Tries to find a
4466  *                        hole that is at least as big as @num_bytes.
4467  *
4468  * @root           -    The root that will contain this extent
4469  *
4470  * @ram_bytes      -    The amount of space in ram that @num_bytes take. This
4471  *                      is used for accounting purposes. This value differs
4472  *                      from @num_bytes only in the case of compressed extents.
4473  *
4474  * @num_bytes      -    Number of bytes to allocate on-disk.
4475  *
4476  * @min_alloc_size -    Indicates the minimum amount of space that the
4477  *                      allocator should try to satisfy. In some cases
4478  *                      @num_bytes may be larger than what is required and if
4479  *                      the filesystem is fragmented then allocation fails.
4480  *                      However, the presence of @min_alloc_size gives a
4481  *                      chance to try and satisfy the smaller allocation.
4482  *
4483  * @empty_size     -    A hint that you plan on doing more COW. This is the
4484  *                      size in bytes the allocator should try to find free
4485  *                      next to the block it returns.  This is just a hint and
4486  *                      may be ignored by the allocator.
4487  *
4488  * @hint_byte      -    Hint to the allocator to start searching above the byte
4489  *                      address passed. It might be ignored.
4490  *
4491  * @ins            -    This key is modified to record the found hole. It will
4492  *                      have the following values:
4493  *                      ins->objectid == start position
4494  *                      ins->flags = BTRFS_EXTENT_ITEM_KEY
4495  *                      ins->offset == the size of the hole.
4496  *
4497  * @is_data        -    Boolean flag indicating whether an extent is
4498  *                      allocated for data (true) or metadata (false)
4499  *
4500  * @delalloc       -    Boolean flag indicating whether this allocation is for
4501  *                      delalloc or not. If 'true' data_rwsem of block groups
4502  *                      is going to be acquired.
4503  *
4504  *
4505  * Returns 0 when an allocation succeeded or < 0 when an error occurred. In
4506  * case -ENOSPC is returned then @ins->offset will contain the size of the
4507  * largest available hole the allocator managed to find.
4508  */
4509 int btrfs_reserve_extent(struct btrfs_root *root, u64 ram_bytes,
4510                          u64 num_bytes, u64 min_alloc_size,
4511                          u64 empty_size, u64 hint_byte,
4512                          struct btrfs_key *ins, int is_data, int delalloc)
4513 {
4514         struct btrfs_fs_info *fs_info = root->fs_info;
4515         struct find_free_extent_ctl ffe_ctl = {};
4516         bool final_tried = num_bytes == min_alloc_size;
4517         u64 flags;
4518         int ret;
4519         bool for_treelog = (root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID);
4520         bool for_data_reloc = (btrfs_is_data_reloc_root(root) && is_data);
4521
4522         flags = get_alloc_profile_by_root(root, is_data);
4523 again:
4524         WARN_ON(num_bytes < fs_info->sectorsize);
4525
4526         ffe_ctl.ram_bytes = ram_bytes;
4527         ffe_ctl.num_bytes = num_bytes;
4528         ffe_ctl.min_alloc_size = min_alloc_size;
4529         ffe_ctl.empty_size = empty_size;
4530         ffe_ctl.flags = flags;
4531         ffe_ctl.delalloc = delalloc;
4532         ffe_ctl.hint_byte = hint_byte;
4533         ffe_ctl.for_treelog = for_treelog;
4534         ffe_ctl.for_data_reloc = for_data_reloc;
4535
4536         ret = find_free_extent(root, ins, &ffe_ctl);
4537         if (!ret && !is_data) {
4538                 btrfs_dec_block_group_reservations(fs_info, ins->objectid);
4539         } else if (ret == -ENOSPC) {
4540                 if (!final_tried && ins->offset) {
4541                         num_bytes = min(num_bytes >> 1, ins->offset);
4542                         num_bytes = round_down(num_bytes,
4543                                                fs_info->sectorsize);
4544                         num_bytes = max(num_bytes, min_alloc_size);
4545                         ram_bytes = num_bytes;
4546                         if (num_bytes == min_alloc_size)
4547                                 final_tried = true;
4548                         goto again;
4549                 } else if (btrfs_test_opt(fs_info, ENOSPC_DEBUG)) {
4550                         struct btrfs_space_info *sinfo;
4551
4552                         sinfo = btrfs_find_space_info(fs_info, flags);
4553                         btrfs_err(fs_info,
4554         "allocation failed flags %llu, wanted %llu tree-log %d, relocation: %d",
4555                                   flags, num_bytes, for_treelog, for_data_reloc);
4556                         if (sinfo)
4557                                 btrfs_dump_space_info(fs_info, sinfo,
4558                                                       num_bytes, 1);
4559                 }
4560         }
4561
4562         return ret;
4563 }
4564
4565 int btrfs_free_reserved_extent(struct btrfs_fs_info *fs_info,
4566                                u64 start, u64 len, int delalloc)
4567 {
4568         struct btrfs_block_group *cache;
4569
4570         cache = btrfs_lookup_block_group(fs_info, start);
4571         if (!cache) {
4572                 btrfs_err(fs_info, "Unable to find block group for %llu",
4573                           start);
4574                 return -ENOSPC;
4575         }
4576
4577         btrfs_add_free_space(cache, start, len);
4578         btrfs_free_reserved_bytes(cache, len, delalloc);
4579         trace_btrfs_reserved_extent_free(fs_info, start, len);
4580
4581         btrfs_put_block_group(cache);
4582         return 0;
4583 }
4584
4585 int btrfs_pin_reserved_extent(struct btrfs_trans_handle *trans, u64 start,
4586                               u64 len)
4587 {
4588         struct btrfs_block_group *cache;
4589         int ret = 0;
4590
4591         cache = btrfs_lookup_block_group(trans->fs_info, start);
4592         if (!cache) {
4593                 btrfs_err(trans->fs_info, "unable to find block group for %llu",
4594                           start);
4595                 return -ENOSPC;
4596         }
4597
4598         ret = pin_down_extent(trans, cache, start, len, 1);
4599         btrfs_put_block_group(cache);
4600         return ret;
4601 }
4602
4603 static int alloc_reserved_extent(struct btrfs_trans_handle *trans, u64 bytenr,
4604                                  u64 num_bytes)
4605 {
4606         struct btrfs_fs_info *fs_info = trans->fs_info;
4607         int ret;
4608
4609         ret = remove_from_free_space_tree(trans, bytenr, num_bytes);
4610         if (ret)
4611                 return ret;
4612
4613         ret = btrfs_update_block_group(trans, bytenr, num_bytes, true);
4614         if (ret) {
4615                 ASSERT(!ret);
4616                 btrfs_err(fs_info, "update block group failed for %llu %llu",
4617                           bytenr, num_bytes);
4618                 return ret;
4619         }
4620
4621         trace_btrfs_reserved_extent_alloc(fs_info, bytenr, num_bytes);
4622         return 0;
4623 }
4624
4625 static int alloc_reserved_file_extent(struct btrfs_trans_handle *trans,
4626                                       u64 parent, u64 root_objectid,
4627                                       u64 flags, u64 owner, u64 offset,
4628                                       struct btrfs_key *ins, int ref_mod)
4629 {
4630         struct btrfs_fs_info *fs_info = trans->fs_info;
4631         struct btrfs_root *extent_root;
4632         int ret;
4633         struct btrfs_extent_item *extent_item;
4634         struct btrfs_extent_inline_ref *iref;
4635         struct btrfs_path *path;
4636         struct extent_buffer *leaf;
4637         int type;
4638         u32 size;
4639
4640         if (parent > 0)
4641                 type = BTRFS_SHARED_DATA_REF_KEY;
4642         else
4643                 type = BTRFS_EXTENT_DATA_REF_KEY;
4644
4645         size = sizeof(*extent_item) + btrfs_extent_inline_ref_size(type);
4646
4647         path = btrfs_alloc_path();
4648         if (!path)
4649                 return -ENOMEM;
4650
4651         extent_root = btrfs_extent_root(fs_info, ins->objectid);
4652         ret = btrfs_insert_empty_item(trans, extent_root, path, ins, size);
4653         if (ret) {
4654                 btrfs_free_path(path);
4655                 return ret;
4656         }
4657
4658         leaf = path->nodes[0];
4659         extent_item = btrfs_item_ptr(leaf, path->slots[0],
4660                                      struct btrfs_extent_item);
4661         btrfs_set_extent_refs(leaf, extent_item, ref_mod);
4662         btrfs_set_extent_generation(leaf, extent_item, trans->transid);
4663         btrfs_set_extent_flags(leaf, extent_item,
4664                                flags | BTRFS_EXTENT_FLAG_DATA);
4665
4666         iref = (struct btrfs_extent_inline_ref *)(extent_item + 1);
4667         btrfs_set_extent_inline_ref_type(leaf, iref, type);
4668         if (parent > 0) {
4669                 struct btrfs_shared_data_ref *ref;
4670                 ref = (struct btrfs_shared_data_ref *)(iref + 1);
4671                 btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
4672                 btrfs_set_shared_data_ref_count(leaf, ref, ref_mod);
4673         } else {
4674                 struct btrfs_extent_data_ref *ref;
4675                 ref = (struct btrfs_extent_data_ref *)(&iref->offset);
4676                 btrfs_set_extent_data_ref_root(leaf, ref, root_objectid);
4677                 btrfs_set_extent_data_ref_objectid(leaf, ref, owner);
4678                 btrfs_set_extent_data_ref_offset(leaf, ref, offset);
4679                 btrfs_set_extent_data_ref_count(leaf, ref, ref_mod);
4680         }
4681
4682         btrfs_mark_buffer_dirty(path->nodes[0]);
4683         btrfs_free_path(path);
4684
4685         return alloc_reserved_extent(trans, ins->objectid, ins->offset);
4686 }
4687
4688 static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
4689                                      struct btrfs_delayed_ref_node *node,
4690                                      struct btrfs_delayed_extent_op *extent_op)
4691 {
4692         struct btrfs_fs_info *fs_info = trans->fs_info;
4693         struct btrfs_root *extent_root;
4694         int ret;
4695         struct btrfs_extent_item *extent_item;
4696         struct btrfs_key extent_key;
4697         struct btrfs_tree_block_info *block_info;
4698         struct btrfs_extent_inline_ref *iref;
4699         struct btrfs_path *path;
4700         struct extent_buffer *leaf;
4701         struct btrfs_delayed_tree_ref *ref;
4702         u32 size = sizeof(*extent_item) + sizeof(*iref);
4703         u64 flags = extent_op->flags_to_set;
4704         bool skinny_metadata = btrfs_fs_incompat(fs_info, SKINNY_METADATA);
4705
4706         ref = btrfs_delayed_node_to_tree_ref(node);
4707
4708         extent_key.objectid = node->bytenr;
4709         if (skinny_metadata) {
4710                 extent_key.offset = ref->level;
4711                 extent_key.type = BTRFS_METADATA_ITEM_KEY;
4712         } else {
4713                 extent_key.offset = node->num_bytes;
4714                 extent_key.type = BTRFS_EXTENT_ITEM_KEY;
4715                 size += sizeof(*block_info);
4716         }
4717
4718         path = btrfs_alloc_path();
4719         if (!path)
4720                 return -ENOMEM;
4721
4722         extent_root = btrfs_extent_root(fs_info, extent_key.objectid);
4723         ret = btrfs_insert_empty_item(trans, extent_root, path, &extent_key,
4724                                       size);
4725         if (ret) {
4726                 btrfs_free_path(path);
4727                 return ret;
4728         }
4729
4730         leaf = path->nodes[0];
4731         extent_item = btrfs_item_ptr(leaf, path->slots[0],
4732                                      struct btrfs_extent_item);
4733         btrfs_set_extent_refs(leaf, extent_item, 1);
4734         btrfs_set_extent_generation(leaf, extent_item, trans->transid);
4735         btrfs_set_extent_flags(leaf, extent_item,
4736                                flags | BTRFS_EXTENT_FLAG_TREE_BLOCK);
4737
4738         if (skinny_metadata) {
4739                 iref = (struct btrfs_extent_inline_ref *)(extent_item + 1);
4740         } else {
4741                 block_info = (struct btrfs_tree_block_info *)(extent_item + 1);
4742                 btrfs_set_tree_block_key(leaf, block_info, &extent_op->key);
4743                 btrfs_set_tree_block_level(leaf, block_info, ref->level);
4744                 iref = (struct btrfs_extent_inline_ref *)(block_info + 1);
4745         }
4746
4747         if (node->type == BTRFS_SHARED_BLOCK_REF_KEY) {
4748                 btrfs_set_extent_inline_ref_type(leaf, iref,
4749                                                  BTRFS_SHARED_BLOCK_REF_KEY);
4750                 btrfs_set_extent_inline_ref_offset(leaf, iref, ref->parent);
4751         } else {
4752                 btrfs_set_extent_inline_ref_type(leaf, iref,
4753                                                  BTRFS_TREE_BLOCK_REF_KEY);
4754                 btrfs_set_extent_inline_ref_offset(leaf, iref, ref->root);
4755         }
4756
4757         btrfs_mark_buffer_dirty(leaf);
4758         btrfs_free_path(path);
4759
4760         return alloc_reserved_extent(trans, node->bytenr, fs_info->nodesize);
4761 }
4762
4763 int btrfs_alloc_reserved_file_extent(struct btrfs_trans_handle *trans,
4764                                      struct btrfs_root *root, u64 owner,
4765                                      u64 offset, u64 ram_bytes,
4766                                      struct btrfs_key *ins)
4767 {
4768         struct btrfs_ref generic_ref = { 0 };
4769
4770         BUG_ON(root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID);
4771
4772         btrfs_init_generic_ref(&generic_ref, BTRFS_ADD_DELAYED_EXTENT,
4773                                ins->objectid, ins->offset, 0);
4774         btrfs_init_data_ref(&generic_ref, root->root_key.objectid, owner,
4775                             offset, 0, false);
4776         btrfs_ref_tree_mod(root->fs_info, &generic_ref);
4777
4778         return btrfs_add_delayed_data_ref(trans, &generic_ref, ram_bytes);
4779 }
4780
4781 /*
4782  * this is used by the tree logging recovery code.  It records that
4783  * an extent has been allocated and makes sure to clear the free
4784  * space cache bits as well
4785  */
4786 int btrfs_alloc_logged_file_extent(struct btrfs_trans_handle *trans,
4787                                    u64 root_objectid, u64 owner, u64 offset,
4788                                    struct btrfs_key *ins)
4789 {
4790         struct btrfs_fs_info *fs_info = trans->fs_info;
4791         int ret;
4792         struct btrfs_block_group *block_group;
4793         struct btrfs_space_info *space_info;
4794
4795         /*
4796          * Mixed block groups will exclude before processing the log so we only
4797          * need to do the exclude dance if this fs isn't mixed.
4798          */
4799         if (!btrfs_fs_incompat(fs_info, MIXED_GROUPS)) {
4800                 ret = __exclude_logged_extent(fs_info, ins->objectid,
4801                                               ins->offset);
4802                 if (ret)
4803                         return ret;
4804         }
4805
4806         block_group = btrfs_lookup_block_group(fs_info, ins->objectid);
4807         if (!block_group)
4808                 return -EINVAL;
4809
4810         space_info = block_group->space_info;
4811         spin_lock(&space_info->lock);
4812         spin_lock(&block_group->lock);
4813         space_info->bytes_reserved += ins->offset;
4814         block_group->reserved += ins->offset;
4815         spin_unlock(&block_group->lock);
4816         spin_unlock(&space_info->lock);
4817
4818         ret = alloc_reserved_file_extent(trans, 0, root_objectid, 0, owner,
4819                                          offset, ins, 1);
4820         if (ret)
4821                 btrfs_pin_extent(trans, ins->objectid, ins->offset, 1);
4822         btrfs_put_block_group(block_group);
4823         return ret;
4824 }
4825
4826 static struct extent_buffer *
4827 btrfs_init_new_buffer(struct btrfs_trans_handle *trans, struct btrfs_root *root,
4828                       u64 bytenr, int level, u64 owner,
4829                       enum btrfs_lock_nesting nest)
4830 {
4831         struct btrfs_fs_info *fs_info = root->fs_info;
4832         struct extent_buffer *buf;
4833
4834         buf = btrfs_find_create_tree_block(fs_info, bytenr, owner, level);
4835         if (IS_ERR(buf))
4836                 return buf;
4837
4838         /*
4839          * Extra safety check in case the extent tree is corrupted and extent
4840          * allocator chooses to use a tree block which is already used and
4841          * locked.
4842          */
4843         if (buf->lock_owner == current->pid) {
4844                 btrfs_err_rl(fs_info,
4845 "tree block %llu owner %llu already locked by pid=%d, extent tree corruption detected",
4846                         buf->start, btrfs_header_owner(buf), current->pid);
4847                 free_extent_buffer(buf);
4848                 return ERR_PTR(-EUCLEAN);
4849         }
4850
4851         /*
4852          * This needs to stay, because we could allocate a freed block from an
4853          * old tree into a new tree, so we need to make sure this new block is
4854          * set to the appropriate level and owner.
4855          */
4856         btrfs_set_buffer_lockdep_class(owner, buf, level);
4857         __btrfs_tree_lock(buf, nest);
4858         btrfs_clean_tree_block(buf);
4859         clear_bit(EXTENT_BUFFER_STALE, &buf->bflags);
4860         clear_bit(EXTENT_BUFFER_NO_CHECK, &buf->bflags);
4861
4862         set_extent_buffer_uptodate(buf);
4863
4864         memzero_extent_buffer(buf, 0, sizeof(struct btrfs_header));
4865         btrfs_set_header_level(buf, level);
4866         btrfs_set_header_bytenr(buf, buf->start);
4867         btrfs_set_header_generation(buf, trans->transid);
4868         btrfs_set_header_backref_rev(buf, BTRFS_MIXED_BACKREF_REV);
4869         btrfs_set_header_owner(buf, owner);
4870         write_extent_buffer_fsid(buf, fs_info->fs_devices->metadata_uuid);
4871         write_extent_buffer_chunk_tree_uuid(buf, fs_info->chunk_tree_uuid);
4872         if (root->root_key.objectid == BTRFS_TREE_LOG_OBJECTID) {
4873                 buf->log_index = root->log_transid % 2;
4874                 /*
4875                  * we allow two log transactions at a time, use different
4876                  * EXTENT bit to differentiate dirty pages.
4877                  */
4878                 if (buf->log_index == 0)
4879                         set_extent_dirty(&root->dirty_log_pages, buf->start,
4880                                         buf->start + buf->len - 1, GFP_NOFS);
4881                 else
4882                         set_extent_new(&root->dirty_log_pages, buf->start,
4883                                         buf->start + buf->len - 1);
4884         } else {
4885                 buf->log_index = -1;
4886                 set_extent_dirty(&trans->transaction->dirty_pages, buf->start,
4887                          buf->start + buf->len - 1, GFP_NOFS);
4888         }
4889         /* this returns a buffer locked for blocking */
4890         return buf;
4891 }
4892
4893 /*
4894  * finds a free extent and does all the dirty work required for allocation
4895  * returns the tree buffer or an ERR_PTR on error.
4896  */
4897 struct extent_buffer *btrfs_alloc_tree_block(struct btrfs_trans_handle *trans,
4898                                              struct btrfs_root *root,
4899                                              u64 parent, u64 root_objectid,
4900                                              const struct btrfs_disk_key *key,
4901                                              int level, u64 hint,
4902                                              u64 empty_size,
4903                                              enum btrfs_lock_nesting nest)
4904 {
4905         struct btrfs_fs_info *fs_info = root->fs_info;
4906         struct btrfs_key ins;
4907         struct btrfs_block_rsv *block_rsv;
4908         struct extent_buffer *buf;
4909         struct btrfs_delayed_extent_op *extent_op;
4910         struct btrfs_ref generic_ref = { 0 };
4911         u64 flags = 0;
4912         int ret;
4913         u32 blocksize = fs_info->nodesize;
4914         bool skinny_metadata = btrfs_fs_incompat(fs_info, SKINNY_METADATA);
4915
4916 #ifdef CONFIG_BTRFS_FS_RUN_SANITY_TESTS
4917         if (btrfs_is_testing(fs_info)) {
4918                 buf = btrfs_init_new_buffer(trans, root, root->alloc_bytenr,
4919                                             level, root_objectid, nest);
4920                 if (!IS_ERR(buf))
4921                         root->alloc_bytenr += blocksize;
4922                 return buf;
4923         }
4924 #endif
4925
4926         block_rsv = btrfs_use_block_rsv(trans, root, blocksize);
4927         if (IS_ERR(block_rsv))
4928                 return ERR_CAST(block_rsv);
4929
4930         ret = btrfs_reserve_extent(root, blocksize, blocksize, blocksize,
4931                                    empty_size, hint, &ins, 0, 0);
4932         if (ret)
4933                 goto out_unuse;
4934
4935         buf = btrfs_init_new_buffer(trans, root, ins.objectid, level,
4936                                     root_objectid, nest);
4937         if (IS_ERR(buf)) {
4938                 ret = PTR_ERR(buf);
4939                 goto out_free_reserved;
4940         }
4941
4942         if (root_objectid == BTRFS_TREE_RELOC_OBJECTID) {
4943                 if (parent == 0)
4944                         parent = ins.objectid;
4945                 flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
4946         } else
4947                 BUG_ON(parent > 0);
4948
4949         if (root_objectid != BTRFS_TREE_LOG_OBJECTID) {
4950                 extent_op = btrfs_alloc_delayed_extent_op();
4951                 if (!extent_op) {
4952                         ret = -ENOMEM;
4953                         goto out_free_buf;
4954                 }
4955                 if (key)
4956                         memcpy(&extent_op->key, key, sizeof(extent_op->key));
4957                 else
4958                         memset(&extent_op->key, 0, sizeof(extent_op->key));
4959                 extent_op->flags_to_set = flags;
4960                 extent_op->update_key = skinny_metadata ? false : true;
4961                 extent_op->update_flags = true;
4962                 extent_op->is_data = false;
4963                 extent_op->level = level;
4964
4965                 btrfs_init_generic_ref(&generic_ref, BTRFS_ADD_DELAYED_EXTENT,
4966                                        ins.objectid, ins.offset, parent);
4967                 btrfs_init_tree_ref(&generic_ref, level, root_objectid,
4968                                     root->root_key.objectid, false);
4969                 btrfs_ref_tree_mod(fs_info, &generic_ref);
4970                 ret = btrfs_add_delayed_tree_ref(trans, &generic_ref, extent_op);
4971                 if (ret)
4972                         goto out_free_delayed;
4973         }
4974         return buf;
4975
4976 out_free_delayed:
4977         btrfs_free_delayed_extent_op(extent_op);
4978 out_free_buf:
4979         btrfs_tree_unlock(buf);
4980         free_extent_buffer(buf);
4981 out_free_reserved:
4982         btrfs_free_reserved_extent(fs_info, ins.objectid, ins.offset, 0);
4983 out_unuse:
4984         btrfs_unuse_block_rsv(fs_info, block_rsv, blocksize);
4985         return ERR_PTR(ret);
4986 }
4987
4988 struct walk_control {
4989         u64 refs[BTRFS_MAX_LEVEL];
4990         u64 flags[BTRFS_MAX_LEVEL];
4991         struct btrfs_key update_progress;
4992         struct btrfs_key drop_progress;
4993         int drop_level;
4994         int stage;
4995         int level;
4996         int shared_level;
4997         int update_ref;
4998         int keep_locks;
4999         int reada_slot;
5000         int reada_count;
5001         int restarted;
5002 };
5003
5004 #define DROP_REFERENCE  1
5005 #define UPDATE_BACKREF  2
5006
5007 static noinline void reada_walk_down(struct btrfs_trans_handle *trans,
5008                                      struct btrfs_root *root,
5009                                      struct walk_control *wc,
5010                                      struct btrfs_path *path)
5011 {
5012         struct btrfs_fs_info *fs_info = root->fs_info;
5013         u64 bytenr;
5014         u64 generation;
5015         u64 refs;
5016         u64 flags;
5017         u32 nritems;
5018         struct btrfs_key key;
5019         struct extent_buffer *eb;
5020         int ret;
5021         int slot;
5022         int nread = 0;
5023
5024         if (path->slots[wc->level] < wc->reada_slot) {
5025                 wc->reada_count = wc->reada_count * 2 / 3;
5026                 wc->reada_count = max(wc->reada_count, 2);
5027         } else {
5028                 wc->reada_count = wc->reada_count * 3 / 2;
5029                 wc->reada_count = min_t(int, wc->reada_count,
5030                                         BTRFS_NODEPTRS_PER_BLOCK(fs_info));
5031         }
5032
5033         eb = path->nodes[wc->level];
5034         nritems = btrfs_header_nritems(eb);
5035
5036         for (slot = path->slots[wc->level]; slot < nritems; slot++) {
5037                 if (nread >= wc->reada_count)
5038                         break;
5039
5040                 cond_resched();
5041                 bytenr = btrfs_node_blockptr(eb, slot);
5042                 generation = btrfs_node_ptr_generation(eb, slot);
5043
5044                 if (slot == path->slots[wc->level])
5045                         goto reada;
5046
5047                 if (wc->stage == UPDATE_BACKREF &&
5048                     generation <= root->root_key.offset)
5049                         continue;
5050
5051                 /* We don't lock the tree block, it's OK to be racy here */
5052                 ret = btrfs_lookup_extent_info(trans, fs_info, bytenr,
5053                                                wc->level - 1, 1, &refs,
5054                                                &flags);
5055                 /* We don't care about errors in readahead. */
5056                 if (ret < 0)
5057                         continue;
5058                 BUG_ON(refs == 0);
5059
5060                 if (wc->stage == DROP_REFERENCE) {
5061                         if (refs == 1)
5062                                 goto reada;
5063
5064                         if (wc->level == 1 &&
5065                             (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF))
5066                                 continue;
5067                         if (!wc->update_ref ||
5068                             generation <= root->root_key.offset)
5069                                 continue;
5070                         btrfs_node_key_to_cpu(eb, &key, slot);
5071                         ret = btrfs_comp_cpu_keys(&key,
5072                                                   &wc->update_progress);
5073                         if (ret < 0)
5074                                 continue;
5075                 } else {
5076                         if (wc->level == 1 &&
5077                             (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF))
5078                                 continue;
5079                 }
5080 reada:
5081                 btrfs_readahead_node_child(eb, slot);
5082                 nread++;
5083         }
5084         wc->reada_slot = slot;
5085 }
5086
5087 /*
5088  * helper to process tree block while walking down the tree.
5089  *
5090  * when wc->stage == UPDATE_BACKREF, this function updates
5091  * back refs for pointers in the block.
5092  *
5093  * NOTE: return value 1 means we should stop walking down.
5094  */
5095 static noinline int walk_down_proc(struct btrfs_trans_handle *trans,
5096                                    struct btrfs_root *root,
5097                                    struct btrfs_path *path,
5098                                    struct walk_control *wc, int lookup_info)
5099 {
5100         struct btrfs_fs_info *fs_info = root->fs_info;
5101         int level = wc->level;
5102         struct extent_buffer *eb = path->nodes[level];
5103         u64 flag = BTRFS_BLOCK_FLAG_FULL_BACKREF;
5104         int ret;
5105
5106         if (wc->stage == UPDATE_BACKREF &&
5107             btrfs_header_owner(eb) != root->root_key.objectid)
5108                 return 1;
5109
5110         /*
5111          * when reference count of tree block is 1, it won't increase
5112          * again. once full backref flag is set, we never clear it.
5113          */
5114         if (lookup_info &&
5115             ((wc->stage == DROP_REFERENCE && wc->refs[level] != 1) ||
5116              (wc->stage == UPDATE_BACKREF && !(wc->flags[level] & flag)))) {
5117                 BUG_ON(!path->locks[level]);
5118                 ret = btrfs_lookup_extent_info(trans, fs_info,
5119                                                eb->start, level, 1,
5120                                                &wc->refs[level],
5121                                                &wc->flags[level]);
5122                 BUG_ON(ret == -ENOMEM);
5123                 if (ret)
5124                         return ret;
5125                 BUG_ON(wc->refs[level] == 0);
5126         }
5127
5128         if (wc->stage == DROP_REFERENCE) {
5129                 if (wc->refs[level] > 1)
5130                         return 1;
5131
5132                 if (path->locks[level] && !wc->keep_locks) {
5133                         btrfs_tree_unlock_rw(eb, path->locks[level]);
5134                         path->locks[level] = 0;
5135                 }
5136                 return 0;
5137         }
5138
5139         /* wc->stage == UPDATE_BACKREF */
5140         if (!(wc->flags[level] & flag)) {
5141                 BUG_ON(!path->locks[level]);
5142                 ret = btrfs_inc_ref(trans, root, eb, 1);
5143                 BUG_ON(ret); /* -ENOMEM */
5144                 ret = btrfs_dec_ref(trans, root, eb, 0);
5145                 BUG_ON(ret); /* -ENOMEM */
5146                 ret = btrfs_set_disk_extent_flags(trans, eb, flag,
5147                                                   btrfs_header_level(eb), 0);
5148                 BUG_ON(ret); /* -ENOMEM */
5149                 wc->flags[level] |= flag;
5150         }
5151
5152         /*
5153          * the block is shared by multiple trees, so it's not good to
5154          * keep the tree lock
5155          */
5156         if (path->locks[level] && level > 0) {
5157                 btrfs_tree_unlock_rw(eb, path->locks[level]);
5158                 path->locks[level] = 0;
5159         }
5160         return 0;
5161 }
5162
5163 /*
5164  * This is used to verify a ref exists for this root to deal with a bug where we
5165  * would have a drop_progress key that hadn't been updated properly.
5166  */
5167 static int check_ref_exists(struct btrfs_trans_handle *trans,
5168                             struct btrfs_root *root, u64 bytenr, u64 parent,
5169                             int level)
5170 {
5171         struct btrfs_path *path;
5172         struct btrfs_extent_inline_ref *iref;
5173         int ret;
5174
5175         path = btrfs_alloc_path();
5176         if (!path)
5177                 return -ENOMEM;
5178
5179         ret = lookup_extent_backref(trans, path, &iref, bytenr,
5180                                     root->fs_info->nodesize, parent,
5181                                     root->root_key.objectid, level, 0);
5182         btrfs_free_path(path);
5183         if (ret == -ENOENT)
5184                 return 0;
5185         if (ret < 0)
5186                 return ret;
5187         return 1;
5188 }
5189
5190 /*
5191  * helper to process tree block pointer.
5192  *
5193  * when wc->stage == DROP_REFERENCE, this function checks
5194  * reference count of the block pointed to. if the block
5195  * is shared and we need update back refs for the subtree
5196  * rooted at the block, this function changes wc->stage to
5197  * UPDATE_BACKREF. if the block is shared and there is no
5198  * need to update back, this function drops the reference
5199  * to the block.
5200  *
5201  * NOTE: return value 1 means we should stop walking down.
5202  */
5203 static noinline int do_walk_down(struct btrfs_trans_handle *trans,
5204                                  struct btrfs_root *root,
5205                                  struct btrfs_path *path,
5206                                  struct walk_control *wc, int *lookup_info)
5207 {
5208         struct btrfs_fs_info *fs_info = root->fs_info;
5209         u64 bytenr;
5210         u64 generation;
5211         u64 parent;
5212         struct btrfs_key key;
5213         struct btrfs_key first_key;
5214         struct btrfs_ref ref = { 0 };
5215         struct extent_buffer *next;
5216         int level = wc->level;
5217         int reada = 0;
5218         int ret = 0;
5219         bool need_account = false;
5220
5221         generation = btrfs_node_ptr_generation(path->nodes[level],
5222                                                path->slots[level]);
5223         /*
5224          * if the lower level block was created before the snapshot
5225          * was created, we know there is no need to update back refs
5226          * for the subtree
5227          */
5228         if (wc->stage == UPDATE_BACKREF &&
5229             generation <= root->root_key.offset) {
5230                 *lookup_info = 1;
5231                 return 1;
5232         }
5233
5234         bytenr = btrfs_node_blockptr(path->nodes[level], path->slots[level]);
5235         btrfs_node_key_to_cpu(path->nodes[level], &first_key,
5236                               path->slots[level]);
5237
5238         next = find_extent_buffer(fs_info, bytenr);
5239         if (!next) {
5240                 next = btrfs_find_create_tree_block(fs_info, bytenr,
5241                                 root->root_key.objectid, level - 1);
5242                 if (IS_ERR(next))
5243                         return PTR_ERR(next);
5244                 reada = 1;
5245         }
5246         btrfs_tree_lock(next);
5247
5248         ret = btrfs_lookup_extent_info(trans, fs_info, bytenr, level - 1, 1,
5249                                        &wc->refs[level - 1],
5250                                        &wc->flags[level - 1]);
5251         if (ret < 0)
5252                 goto out_unlock;
5253
5254         if (unlikely(wc->refs[level - 1] == 0)) {
5255                 btrfs_err(fs_info, "Missing references.");
5256                 ret = -EIO;
5257                 goto out_unlock;
5258         }
5259         *lookup_info = 0;
5260
5261         if (wc->stage == DROP_REFERENCE) {
5262                 if (wc->refs[level - 1] > 1) {
5263                         need_account = true;
5264                         if (level == 1 &&
5265                             (wc->flags[0] & BTRFS_BLOCK_FLAG_FULL_BACKREF))
5266                                 goto skip;
5267
5268                         if (!wc->update_ref ||
5269                             generation <= root->root_key.offset)
5270                                 goto skip;
5271
5272                         btrfs_node_key_to_cpu(path->nodes[level], &key,
5273                                               path->slots[level]);
5274                         ret = btrfs_comp_cpu_keys(&key, &wc->update_progress);
5275                         if (ret < 0)
5276                                 goto skip;
5277
5278                         wc->stage = UPDATE_BACKREF;
5279                         wc->shared_level = level - 1;
5280                 }
5281         } else {
5282                 if (level == 1 &&
5283                     (wc->flags[0] & BTRFS_BLOCK_FLAG_FULL_BACKREF))
5284                         goto skip;
5285         }
5286
5287         if (!btrfs_buffer_uptodate(next, generation, 0)) {
5288                 btrfs_tree_unlock(next);
5289                 free_extent_buffer(next);
5290                 next = NULL;
5291                 *lookup_info = 1;
5292         }
5293
5294         if (!next) {
5295                 if (reada && level == 1)
5296                         reada_walk_down(trans, root, wc, path);
5297                 next = read_tree_block(fs_info, bytenr, root->root_key.objectid,
5298                                        generation, level - 1, &first_key);
5299                 if (IS_ERR(next)) {
5300                         return PTR_ERR(next);
5301                 } else if (!extent_buffer_uptodate(next)) {
5302                         free_extent_buffer(next);
5303                         return -EIO;
5304                 }
5305                 btrfs_tree_lock(next);
5306         }
5307
5308         level--;
5309         ASSERT(level == btrfs_header_level(next));
5310         if (level != btrfs_header_level(next)) {
5311                 btrfs_err(root->fs_info, "mismatched level");
5312                 ret = -EIO;
5313                 goto out_unlock;
5314         }
5315         path->nodes[level] = next;
5316         path->slots[level] = 0;
5317         path->locks[level] = BTRFS_WRITE_LOCK;
5318         wc->level = level;
5319         if (wc->level == 1)
5320                 wc->reada_slot = 0;
5321         return 0;
5322 skip:
5323         wc->refs[level - 1] = 0;
5324         wc->flags[level - 1] = 0;
5325         if (wc->stage == DROP_REFERENCE) {
5326                 if (wc->flags[level] & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
5327                         parent = path->nodes[level]->start;
5328                 } else {
5329                         ASSERT(root->root_key.objectid ==
5330                                btrfs_header_owner(path->nodes[level]));
5331                         if (root->root_key.objectid !=
5332                             btrfs_header_owner(path->nodes[level])) {
5333                                 btrfs_err(root->fs_info,
5334                                                 "mismatched block owner");
5335                                 ret = -EIO;
5336                                 goto out_unlock;
5337                         }
5338                         parent = 0;
5339                 }
5340
5341                 /*
5342                  * If we had a drop_progress we need to verify the refs are set
5343                  * as expected.  If we find our ref then we know that from here
5344                  * on out everything should be correct, and we can clear the
5345                  * ->restarted flag.
5346                  */
5347                 if (wc->restarted) {
5348                         ret = check_ref_exists(trans, root, bytenr, parent,
5349                                                level - 1);
5350                         if (ret < 0)
5351                                 goto out_unlock;
5352                         if (ret == 0)
5353                                 goto no_delete;
5354                         ret = 0;
5355                         wc->restarted = 0;
5356                 }
5357
5358                 /*
5359                  * Reloc tree doesn't contribute to qgroup numbers, and we have
5360                  * already accounted them at merge time (replace_path),
5361                  * thus we could skip expensive subtree trace here.
5362                  */
5363                 if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID &&
5364                     need_account) {
5365                         ret = btrfs_qgroup_trace_subtree(trans, next,
5366                                                          generation, level - 1);
5367                         if (ret) {
5368                                 btrfs_err_rl(fs_info,
5369                                              "Error %d accounting shared subtree. Quota is out of sync, rescan required.",
5370                                              ret);
5371                         }
5372                 }
5373
5374                 /*
5375                  * We need to update the next key in our walk control so we can
5376                  * update the drop_progress key accordingly.  We don't care if
5377                  * find_next_key doesn't find a key because that means we're at
5378                  * the end and are going to clean up now.
5379                  */
5380                 wc->drop_level = level;
5381                 find_next_key(path, level, &wc->drop_progress);
5382
5383                 btrfs_init_generic_ref(&ref, BTRFS_DROP_DELAYED_REF, bytenr,
5384                                        fs_info->nodesize, parent);
5385                 btrfs_init_tree_ref(&ref, level - 1, root->root_key.objectid,
5386                                     0, false);
5387                 ret = btrfs_free_extent(trans, &ref);
5388                 if (ret)
5389                         goto out_unlock;
5390         }
5391 no_delete:
5392         *lookup_info = 1;
5393         ret = 1;
5394
5395 out_unlock:
5396         btrfs_tree_unlock(next);
5397         free_extent_buffer(next);
5398
5399         return ret;
5400 }
5401
5402 /*
5403  * helper to process tree block while walking up the tree.
5404  *
5405  * when wc->stage == DROP_REFERENCE, this function drops
5406  * reference count on the block.
5407  *
5408  * when wc->stage == UPDATE_BACKREF, this function changes
5409  * wc->stage back to DROP_REFERENCE if we changed wc->stage
5410  * to UPDATE_BACKREF previously while processing the block.
5411  *
5412  * NOTE: return value 1 means we should stop walking up.
5413  */
5414 static noinline int walk_up_proc(struct btrfs_trans_handle *trans,
5415                                  struct btrfs_root *root,
5416                                  struct btrfs_path *path,
5417                                  struct walk_control *wc)
5418 {
5419         struct btrfs_fs_info *fs_info = root->fs_info;
5420         int ret;
5421         int level = wc->level;
5422         struct extent_buffer *eb = path->nodes[level];
5423         u64 parent = 0;
5424
5425         if (wc->stage == UPDATE_BACKREF) {
5426                 BUG_ON(wc->shared_level < level);
5427                 if (level < wc->shared_level)
5428                         goto out;
5429
5430                 ret = find_next_key(path, level + 1, &wc->update_progress);
5431                 if (ret > 0)
5432                         wc->update_ref = 0;
5433
5434                 wc->stage = DROP_REFERENCE;
5435                 wc->shared_level = -1;
5436                 path->slots[level] = 0;
5437
5438                 /*
5439                  * check reference count again if the block isn't locked.
5440                  * we should start walking down the tree again if reference
5441                  * count is one.
5442                  */
5443                 if (!path->locks[level]) {
5444                         BUG_ON(level == 0);
5445                         btrfs_tree_lock(eb);
5446                         path->locks[level] = BTRFS_WRITE_LOCK;
5447
5448                         ret = btrfs_lookup_extent_info(trans, fs_info,
5449                                                        eb->start, level, 1,
5450                                                        &wc->refs[level],
5451                                                        &wc->flags[level]);
5452                         if (ret < 0) {
5453                                 btrfs_tree_unlock_rw(eb, path->locks[level]);
5454                                 path->locks[level] = 0;
5455                                 return ret;
5456                         }
5457                         BUG_ON(wc->refs[level] == 0);
5458                         if (wc->refs[level] == 1) {
5459                                 btrfs_tree_unlock_rw(eb, path->locks[level]);
5460                                 path->locks[level] = 0;
5461                                 return 1;
5462                         }
5463                 }
5464         }
5465
5466         /* wc->stage == DROP_REFERENCE */
5467         BUG_ON(wc->refs[level] > 1 && !path->locks[level]);
5468
5469         if (wc->refs[level] == 1) {
5470                 if (level == 0) {
5471                         if (wc->flags[level] & BTRFS_BLOCK_FLAG_FULL_BACKREF)
5472                                 ret = btrfs_dec_ref(trans, root, eb, 1);
5473                         else
5474                                 ret = btrfs_dec_ref(trans, root, eb, 0);
5475                         BUG_ON(ret); /* -ENOMEM */
5476                         if (is_fstree(root->root_key.objectid)) {
5477                                 ret = btrfs_qgroup_trace_leaf_items(trans, eb);
5478                                 if (ret) {
5479                                         btrfs_err_rl(fs_info,
5480         "error %d accounting leaf items, quota is out of sync, rescan required",
5481                                              ret);
5482                                 }
5483                         }
5484                 }
5485                 /* make block locked assertion in btrfs_clean_tree_block happy */
5486                 if (!path->locks[level] &&
5487                     btrfs_header_generation(eb) == trans->transid) {
5488                         btrfs_tree_lock(eb);
5489                         path->locks[level] = BTRFS_WRITE_LOCK;
5490                 }
5491                 btrfs_clean_tree_block(eb);
5492         }
5493
5494         if (eb == root->node) {
5495                 if (wc->flags[level] & BTRFS_BLOCK_FLAG_FULL_BACKREF)
5496                         parent = eb->start;
5497                 else if (root->root_key.objectid != btrfs_header_owner(eb))
5498                         goto owner_mismatch;
5499         } else {
5500                 if (wc->flags[level + 1] & BTRFS_BLOCK_FLAG_FULL_BACKREF)
5501                         parent = path->nodes[level + 1]->start;
5502                 else if (root->root_key.objectid !=
5503                          btrfs_header_owner(path->nodes[level + 1]))
5504                         goto owner_mismatch;
5505         }
5506
5507         btrfs_free_tree_block(trans, btrfs_root_id(root), eb, parent,
5508                               wc->refs[level] == 1);
5509 out:
5510         wc->refs[level] = 0;
5511         wc->flags[level] = 0;
5512         return 0;
5513
5514 owner_mismatch:
5515         btrfs_err_rl(fs_info, "unexpected tree owner, have %llu expect %llu",
5516                      btrfs_header_owner(eb), root->root_key.objectid);
5517         return -EUCLEAN;
5518 }
5519
5520 static noinline int walk_down_tree(struct btrfs_trans_handle *trans,
5521                                    struct btrfs_root *root,
5522                                    struct btrfs_path *path,
5523                                    struct walk_control *wc)
5524 {
5525         int level = wc->level;
5526         int lookup_info = 1;
5527         int ret;
5528
5529         while (level >= 0) {
5530                 ret = walk_down_proc(trans, root, path, wc, lookup_info);
5531                 if (ret > 0)
5532                         break;
5533
5534                 if (level == 0)
5535                         break;
5536
5537                 if (path->slots[level] >=
5538                     btrfs_header_nritems(path->nodes[level]))
5539                         break;
5540
5541                 ret = do_walk_down(trans, root, path, wc, &lookup_info);
5542                 if (ret > 0) {
5543                         path->slots[level]++;
5544                         continue;
5545                 } else if (ret < 0)
5546                         return ret;
5547                 level = wc->level;
5548         }
5549         return 0;
5550 }
5551
5552 static noinline int walk_up_tree(struct btrfs_trans_handle *trans,
5553                                  struct btrfs_root *root,
5554                                  struct btrfs_path *path,
5555                                  struct walk_control *wc, int max_level)
5556 {
5557         int level = wc->level;
5558         int ret;
5559
5560         path->slots[level] = btrfs_header_nritems(path->nodes[level]);
5561         while (level < max_level && path->nodes[level]) {
5562                 wc->level = level;
5563                 if (path->slots[level] + 1 <
5564                     btrfs_header_nritems(path->nodes[level])) {
5565                         path->slots[level]++;
5566                         return 0;
5567                 } else {
5568                         ret = walk_up_proc(trans, root, path, wc);
5569                         if (ret > 0)
5570                                 return 0;
5571                         if (ret < 0)
5572                                 return ret;
5573
5574                         if (path->locks[level]) {
5575                                 btrfs_tree_unlock_rw(path->nodes[level],
5576                                                      path->locks[level]);
5577                                 path->locks[level] = 0;
5578                         }
5579                         free_extent_buffer(path->nodes[level]);
5580                         path->nodes[level] = NULL;
5581                         level++;
5582                 }
5583         }
5584         return 1;
5585 }
5586
5587 /*
5588  * drop a subvolume tree.
5589  *
5590  * this function traverses the tree freeing any blocks that only
5591  * referenced by the tree.
5592  *
5593  * when a shared tree block is found. this function decreases its
5594  * reference count by one. if update_ref is true, this function
5595  * also make sure backrefs for the shared block and all lower level
5596  * blocks are properly updated.
5597  *
5598  * If called with for_reloc == 0, may exit early with -EAGAIN
5599  */
5600 int btrfs_drop_snapshot(struct btrfs_root *root, int update_ref, int for_reloc)
5601 {
5602         struct btrfs_fs_info *fs_info = root->fs_info;
5603         struct btrfs_path *path;
5604         struct btrfs_trans_handle *trans;
5605         struct btrfs_root *tree_root = fs_info->tree_root;
5606         struct btrfs_root_item *root_item = &root->root_item;
5607         struct walk_control *wc;
5608         struct btrfs_key key;
5609         int err = 0;
5610         int ret;
5611         int level;
5612         bool root_dropped = false;
5613         bool unfinished_drop = false;
5614
5615         btrfs_debug(fs_info, "Drop subvolume %llu", root->root_key.objectid);
5616
5617         path = btrfs_alloc_path();
5618         if (!path) {
5619                 err = -ENOMEM;
5620                 goto out;
5621         }
5622
5623         wc = kzalloc(sizeof(*wc), GFP_NOFS);
5624         if (!wc) {
5625                 btrfs_free_path(path);
5626                 err = -ENOMEM;
5627                 goto out;
5628         }
5629
5630         /*
5631          * Use join to avoid potential EINTR from transaction start. See
5632          * wait_reserve_ticket and the whole reservation callchain.
5633          */
5634         if (for_reloc)
5635                 trans = btrfs_join_transaction(tree_root);
5636         else
5637                 trans = btrfs_start_transaction(tree_root, 0);
5638         if (IS_ERR(trans)) {
5639                 err = PTR_ERR(trans);
5640                 goto out_free;
5641         }
5642
5643         err = btrfs_run_delayed_items(trans);
5644         if (err)
5645                 goto out_end_trans;
5646
5647         /*
5648          * This will help us catch people modifying the fs tree while we're
5649          * dropping it.  It is unsafe to mess with the fs tree while it's being
5650          * dropped as we unlock the root node and parent nodes as we walk down
5651          * the tree, assuming nothing will change.  If something does change
5652          * then we'll have stale information and drop references to blocks we've
5653          * already dropped.
5654          */
5655         set_bit(BTRFS_ROOT_DELETING, &root->state);
5656         unfinished_drop = test_bit(BTRFS_ROOT_UNFINISHED_DROP, &root->state);
5657
5658         if (btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
5659                 level = btrfs_header_level(root->node);
5660                 path->nodes[level] = btrfs_lock_root_node(root);
5661                 path->slots[level] = 0;
5662                 path->locks[level] = BTRFS_WRITE_LOCK;
5663                 memset(&wc->update_progress, 0,
5664                        sizeof(wc->update_progress));
5665         } else {
5666                 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
5667                 memcpy(&wc->update_progress, &key,
5668                        sizeof(wc->update_progress));
5669
5670                 level = btrfs_root_drop_level(root_item);
5671                 BUG_ON(level == 0);
5672                 path->lowest_level = level;
5673                 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
5674                 path->lowest_level = 0;
5675                 if (ret < 0) {
5676                         err = ret;
5677                         goto out_end_trans;
5678                 }
5679                 WARN_ON(ret > 0);
5680
5681                 /*
5682                  * unlock our path, this is safe because only this
5683                  * function is allowed to delete this snapshot
5684                  */
5685                 btrfs_unlock_up_safe(path, 0);
5686
5687                 level = btrfs_header_level(root->node);
5688                 while (1) {
5689                         btrfs_tree_lock(path->nodes[level]);
5690                         path->locks[level] = BTRFS_WRITE_LOCK;
5691
5692                         ret = btrfs_lookup_extent_info(trans, fs_info,
5693                                                 path->nodes[level]->start,
5694                                                 level, 1, &wc->refs[level],
5695                                                 &wc->flags[level]);
5696                         if (ret < 0) {
5697                                 err = ret;
5698                                 goto out_end_trans;
5699                         }
5700                         BUG_ON(wc->refs[level] == 0);
5701
5702                         if (level == btrfs_root_drop_level(root_item))
5703                                 break;
5704
5705                         btrfs_tree_unlock(path->nodes[level]);
5706                         path->locks[level] = 0;
5707                         WARN_ON(wc->refs[level] != 1);
5708                         level--;
5709                 }
5710         }
5711
5712         wc->restarted = test_bit(BTRFS_ROOT_DEAD_TREE, &root->state);
5713         wc->level = level;
5714         wc->shared_level = -1;
5715         wc->stage = DROP_REFERENCE;
5716         wc->update_ref = update_ref;
5717         wc->keep_locks = 0;
5718         wc->reada_count = BTRFS_NODEPTRS_PER_BLOCK(fs_info);
5719
5720         while (1) {
5721
5722                 ret = walk_down_tree(trans, root, path, wc);
5723                 if (ret < 0) {
5724                         err = ret;
5725                         break;
5726                 }
5727
5728                 ret = walk_up_tree(trans, root, path, wc, BTRFS_MAX_LEVEL);
5729                 if (ret < 0) {
5730                         err = ret;
5731                         break;
5732                 }
5733
5734                 if (ret > 0) {
5735                         BUG_ON(wc->stage != DROP_REFERENCE);
5736                         break;
5737                 }
5738
5739                 if (wc->stage == DROP_REFERENCE) {
5740                         wc->drop_level = wc->level;
5741                         btrfs_node_key_to_cpu(path->nodes[wc->drop_level],
5742                                               &wc->drop_progress,
5743                                               path->slots[wc->drop_level]);
5744                 }
5745                 btrfs_cpu_key_to_disk(&root_item->drop_progress,
5746                                       &wc->drop_progress);
5747                 btrfs_set_root_drop_level(root_item, wc->drop_level);
5748
5749                 BUG_ON(wc->level == 0);
5750                 if (btrfs_should_end_transaction(trans) ||
5751                     (!for_reloc && btrfs_need_cleaner_sleep(fs_info))) {
5752                         ret = btrfs_update_root(trans, tree_root,
5753                                                 &root->root_key,
5754                                                 root_item);
5755                         if (ret) {
5756                                 btrfs_abort_transaction(trans, ret);
5757                                 err = ret;
5758                                 goto out_end_trans;
5759                         }
5760
5761                         btrfs_end_transaction_throttle(trans);
5762                         if (!for_reloc && btrfs_need_cleaner_sleep(fs_info)) {
5763                                 btrfs_debug(fs_info,
5764                                             "drop snapshot early exit");
5765                                 err = -EAGAIN;
5766                                 goto out_free;
5767                         }
5768
5769                        /*
5770                         * Use join to avoid potential EINTR from transaction
5771                         * start. See wait_reserve_ticket and the whole
5772                         * reservation callchain.
5773                         */
5774                         if (for_reloc)
5775                                 trans = btrfs_join_transaction(tree_root);
5776                         else
5777                                 trans = btrfs_start_transaction(tree_root, 0);
5778                         if (IS_ERR(trans)) {
5779                                 err = PTR_ERR(trans);
5780                                 goto out_free;
5781                         }
5782                 }
5783         }
5784         btrfs_release_path(path);
5785         if (err)
5786                 goto out_end_trans;
5787
5788         ret = btrfs_del_root(trans, &root->root_key);
5789         if (ret) {
5790                 btrfs_abort_transaction(trans, ret);
5791                 err = ret;
5792                 goto out_end_trans;
5793         }
5794
5795         if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
5796                 ret = btrfs_find_root(tree_root, &root->root_key, path,
5797                                       NULL, NULL);
5798                 if (ret < 0) {
5799                         btrfs_abort_transaction(trans, ret);
5800                         err = ret;
5801                         goto out_end_trans;
5802                 } else if (ret > 0) {
5803                         /* if we fail to delete the orphan item this time
5804                          * around, it'll get picked up the next time.
5805                          *
5806                          * The most common failure here is just -ENOENT.
5807                          */
5808                         btrfs_del_orphan_item(trans, tree_root,
5809                                               root->root_key.objectid);
5810                 }
5811         }
5812
5813         /*
5814          * This subvolume is going to be completely dropped, and won't be
5815          * recorded as dirty roots, thus pertrans meta rsv will not be freed at
5816          * commit transaction time.  So free it here manually.
5817          */
5818         btrfs_qgroup_convert_reserved_meta(root, INT_MAX);
5819         btrfs_qgroup_free_meta_all_pertrans(root);
5820
5821         if (test_bit(BTRFS_ROOT_IN_RADIX, &root->state))
5822                 btrfs_add_dropped_root(trans, root);
5823         else
5824                 btrfs_put_root(root);
5825         root_dropped = true;
5826 out_end_trans:
5827         btrfs_end_transaction_throttle(trans);
5828 out_free:
5829         kfree(wc);
5830         btrfs_free_path(path);
5831 out:
5832         /*
5833          * We were an unfinished drop root, check to see if there are any
5834          * pending, and if not clear and wake up any waiters.
5835          */
5836         if (!err && unfinished_drop)
5837                 btrfs_maybe_wake_unfinished_drop(fs_info);
5838
5839         /*
5840          * So if we need to stop dropping the snapshot for whatever reason we
5841          * need to make sure to add it back to the dead root list so that we
5842          * keep trying to do the work later.  This also cleans up roots if we
5843          * don't have it in the radix (like when we recover after a power fail
5844          * or unmount) so we don't leak memory.
5845          */
5846         if (!for_reloc && !root_dropped)
5847                 btrfs_add_dead_root(root);
5848         return err;
5849 }
5850
5851 /*
5852  * drop subtree rooted at tree block 'node'.
5853  *
5854  * NOTE: this function will unlock and release tree block 'node'
5855  * only used by relocation code
5856  */
5857 int btrfs_drop_subtree(struct btrfs_trans_handle *trans,
5858                         struct btrfs_root *root,
5859                         struct extent_buffer *node,
5860                         struct extent_buffer *parent)
5861 {
5862         struct btrfs_fs_info *fs_info = root->fs_info;
5863         struct btrfs_path *path;
5864         struct walk_control *wc;
5865         int level;
5866         int parent_level;
5867         int ret = 0;
5868         int wret;
5869
5870         BUG_ON(root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID);
5871
5872         path = btrfs_alloc_path();
5873         if (!path)
5874                 return -ENOMEM;
5875
5876         wc = kzalloc(sizeof(*wc), GFP_NOFS);
5877         if (!wc) {
5878                 btrfs_free_path(path);
5879                 return -ENOMEM;
5880         }
5881
5882         btrfs_assert_tree_write_locked(parent);
5883         parent_level = btrfs_header_level(parent);
5884         atomic_inc(&parent->refs);
5885         path->nodes[parent_level] = parent;
5886         path->slots[parent_level] = btrfs_header_nritems(parent);
5887
5888         btrfs_assert_tree_write_locked(node);
5889         level = btrfs_header_level(node);
5890         path->nodes[level] = node;
5891         path->slots[level] = 0;
5892         path->locks[level] = BTRFS_WRITE_LOCK;
5893
5894         wc->refs[parent_level] = 1;
5895         wc->flags[parent_level] = BTRFS_BLOCK_FLAG_FULL_BACKREF;
5896         wc->level = level;
5897         wc->shared_level = -1;
5898         wc->stage = DROP_REFERENCE;
5899         wc->update_ref = 0;
5900         wc->keep_locks = 1;
5901         wc->reada_count = BTRFS_NODEPTRS_PER_BLOCK(fs_info);
5902
5903         while (1) {
5904                 wret = walk_down_tree(trans, root, path, wc);
5905                 if (wret < 0) {
5906                         ret = wret;
5907                         break;
5908                 }
5909
5910                 wret = walk_up_tree(trans, root, path, wc, parent_level);
5911                 if (wret < 0)
5912                         ret = wret;
5913                 if (wret != 0)
5914                         break;
5915         }
5916
5917         kfree(wc);
5918         btrfs_free_path(path);
5919         return ret;
5920 }
5921
5922 /*
5923  * helper to account the unused space of all the readonly block group in the
5924  * space_info. takes mirrors into account.
5925  */
5926 u64 btrfs_account_ro_block_groups_free_space(struct btrfs_space_info *sinfo)
5927 {
5928         struct btrfs_block_group *block_group;
5929         u64 free_bytes = 0;
5930         int factor;
5931
5932         /* It's df, we don't care if it's racy */
5933         if (list_empty(&sinfo->ro_bgs))
5934                 return 0;
5935
5936         spin_lock(&sinfo->lock);
5937         list_for_each_entry(block_group, &sinfo->ro_bgs, ro_list) {
5938                 spin_lock(&block_group->lock);
5939
5940                 if (!block_group->ro) {
5941                         spin_unlock(&block_group->lock);
5942                         continue;
5943                 }
5944
5945                 factor = btrfs_bg_type_to_factor(block_group->flags);
5946                 free_bytes += (block_group->length -
5947                                block_group->used) * factor;
5948
5949                 spin_unlock(&block_group->lock);
5950         }
5951         spin_unlock(&sinfo->lock);
5952
5953         return free_bytes;
5954 }
5955
5956 int btrfs_error_unpin_extent_range(struct btrfs_fs_info *fs_info,
5957                                    u64 start, u64 end)
5958 {
5959         return unpin_extent_range(fs_info, start, end, false);
5960 }
5961
5962 /*
5963  * It used to be that old block groups would be left around forever.
5964  * Iterating over them would be enough to trim unused space.  Since we
5965  * now automatically remove them, we also need to iterate over unallocated
5966  * space.
5967  *
5968  * We don't want a transaction for this since the discard may take a
5969  * substantial amount of time.  We don't require that a transaction be
5970  * running, but we do need to take a running transaction into account
5971  * to ensure that we're not discarding chunks that were released or
5972  * allocated in the current transaction.
5973  *
5974  * Holding the chunks lock will prevent other threads from allocating
5975  * or releasing chunks, but it won't prevent a running transaction
5976  * from committing and releasing the memory that the pending chunks
5977  * list head uses.  For that, we need to take a reference to the
5978  * transaction and hold the commit root sem.  We only need to hold
5979  * it while performing the free space search since we have already
5980  * held back allocations.
5981  */
5982 static int btrfs_trim_free_extents(struct btrfs_device *device, u64 *trimmed)
5983 {
5984         u64 start = SZ_1M, len = 0, end = 0;
5985         int ret;
5986
5987         *trimmed = 0;
5988
5989         /* Discard not supported = nothing to do. */
5990         if (!blk_queue_discard(bdev_get_queue(device->bdev)))
5991                 return 0;
5992
5993         /* Not writable = nothing to do. */
5994         if (!test_bit(BTRFS_DEV_STATE_WRITEABLE, &device->dev_state))
5995                 return 0;
5996
5997         /* No free space = nothing to do. */
5998         if (device->total_bytes <= device->bytes_used)
5999                 return 0;
6000
6001         ret = 0;
6002
6003         while (1) {
6004                 struct btrfs_fs_info *fs_info = device->fs_info;
6005                 u64 bytes;
6006
6007                 ret = mutex_lock_interruptible(&fs_info->chunk_mutex);
6008                 if (ret)
6009                         break;
6010
6011                 find_first_clear_extent_bit(&device->alloc_state, start,
6012                                             &start, &end,
6013                                             CHUNK_TRIMMED | CHUNK_ALLOCATED);
6014
6015                 /* Check if there are any CHUNK_* bits left */
6016                 if (start > device->total_bytes) {
6017                         WARN_ON(IS_ENABLED(CONFIG_BTRFS_DEBUG));
6018                         btrfs_warn_in_rcu(fs_info,
6019 "ignoring attempt to trim beyond device size: offset %llu length %llu device %s device size %llu",
6020                                           start, end - start + 1,
6021                                           rcu_str_deref(device->name),
6022                                           device->total_bytes);
6023                         mutex_unlock(&fs_info->chunk_mutex);
6024                         ret = 0;
6025                         break;
6026                 }
6027
6028                 /* Ensure we skip the reserved area in the first 1M */
6029                 start = max_t(u64, start, SZ_1M);
6030
6031                 /*
6032                  * If find_first_clear_extent_bit find a range that spans the
6033                  * end of the device it will set end to -1, in this case it's up
6034                  * to the caller to trim the value to the size of the device.
6035                  */
6036                 end = min(end, device->total_bytes - 1);
6037
6038                 len = end - start + 1;
6039
6040                 /* We didn't find any extents */
6041                 if (!len) {
6042                         mutex_unlock(&fs_info->chunk_mutex);
6043                         ret = 0;
6044                         break;
6045                 }
6046
6047                 ret = btrfs_issue_discard(device->bdev, start, len,
6048                                           &bytes);
6049                 if (!ret)
6050                         set_extent_bits(&device->alloc_state, start,
6051                                         start + bytes - 1,
6052                                         CHUNK_TRIMMED);
6053                 mutex_unlock(&fs_info->chunk_mutex);
6054
6055                 if (ret)
6056                         break;
6057
6058                 start += len;
6059                 *trimmed += bytes;
6060
6061                 if (fatal_signal_pending(current)) {
6062                         ret = -ERESTARTSYS;
6063                         break;
6064                 }
6065
6066                 cond_resched();
6067         }
6068
6069         return ret;
6070 }
6071
6072 /*
6073  * Trim the whole filesystem by:
6074  * 1) trimming the free space in each block group
6075  * 2) trimming the unallocated space on each device
6076  *
6077  * This will also continue trimming even if a block group or device encounters
6078  * an error.  The return value will be the last error, or 0 if nothing bad
6079  * happens.
6080  */
6081 int btrfs_trim_fs(struct btrfs_fs_info *fs_info, struct fstrim_range *range)
6082 {
6083         struct btrfs_fs_devices *fs_devices = fs_info->fs_devices;
6084         struct btrfs_block_group *cache = NULL;
6085         struct btrfs_device *device;
6086         u64 group_trimmed;
6087         u64 range_end = U64_MAX;
6088         u64 start;
6089         u64 end;
6090         u64 trimmed = 0;
6091         u64 bg_failed = 0;
6092         u64 dev_failed = 0;
6093         int bg_ret = 0;
6094         int dev_ret = 0;
6095         int ret = 0;
6096
6097         if (range->start == U64_MAX)
6098                 return -EINVAL;
6099
6100         /*
6101          * Check range overflow if range->len is set.
6102          * The default range->len is U64_MAX.
6103          */
6104         if (range->len != U64_MAX &&
6105             check_add_overflow(range->start, range->len, &range_end))
6106                 return -EINVAL;
6107
6108         cache = btrfs_lookup_first_block_group(fs_info, range->start);
6109         for (; cache; cache = btrfs_next_block_group(cache)) {
6110                 if (cache->start >= range_end) {
6111                         btrfs_put_block_group(cache);
6112                         break;
6113                 }
6114
6115                 start = max(range->start, cache->start);
6116                 end = min(range_end, cache->start + cache->length);
6117
6118                 if (end - start >= range->minlen) {
6119                         if (!btrfs_block_group_done(cache)) {
6120                                 ret = btrfs_cache_block_group(cache, 0);
6121                                 if (ret) {
6122                                         bg_failed++;
6123                                         bg_ret = ret;
6124                                         continue;
6125                                 }
6126                                 ret = btrfs_wait_block_group_cache_done(cache);
6127                                 if (ret) {
6128                                         bg_failed++;
6129                                         bg_ret = ret;
6130                                         continue;
6131                                 }
6132                         }
6133                         ret = btrfs_trim_block_group(cache,
6134                                                      &group_trimmed,
6135                                                      start,
6136                                                      end,
6137                                                      range->minlen);
6138
6139                         trimmed += group_trimmed;
6140                         if (ret) {
6141                                 bg_failed++;
6142                                 bg_ret = ret;
6143                                 continue;
6144                         }
6145                 }
6146         }
6147
6148         if (bg_failed)
6149                 btrfs_warn(fs_info,
6150                         "failed to trim %llu block group(s), last error %d",
6151                         bg_failed, bg_ret);
6152
6153         mutex_lock(&fs_devices->device_list_mutex);
6154         list_for_each_entry(device, &fs_devices->devices, dev_list) {
6155                 if (test_bit(BTRFS_DEV_STATE_MISSING, &device->dev_state))
6156                         continue;
6157
6158                 ret = btrfs_trim_free_extents(device, &group_trimmed);
6159                 if (ret) {
6160                         dev_failed++;
6161                         dev_ret = ret;
6162                         break;
6163                 }
6164
6165                 trimmed += group_trimmed;
6166         }
6167         mutex_unlock(&fs_devices->device_list_mutex);
6168
6169         if (dev_failed)
6170                 btrfs_warn(fs_info,
6171                         "failed to trim %llu device(s), last error %d",
6172                         dev_failed, dev_ret);
6173         range->len = trimmed;
6174         if (bg_ret)
6175                 return bg_ret;
6176         return dev_ret;
6177 }