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