Quelle  extent-tree.c   Sprache: C

// SPDX-License-Identifier: GPL-2.0
/*
 * Copyright (C) 2007 Oracle.  All rights reserved.
 */

#include <linux/sched.h>
#include <linux/sched/signal.h>
#include <linux/pagemap.h>
#include <linux/writeback.h>
#include <linux/blkdev.h>
#include <linux/sort.h>
#include <linux/rcupdate.h>
#include <linux/kthread.h>
#include <linux/slab.h>
#include <linux/ratelimit.h>
#include <linux/percpu_counter.h>
#include <linux/lockdep.h>
#include <linux/crc32c.h>
#include "ctree.h"
#include "extent-tree.h"
#include "transaction.h"
#include "disk-io.h"
#include "print-tree.h"
#include "volumes.h"
#include "raid56.h"
#include "locking.h"
#include "free-space-cache.h"
#include "free-space-tree.h"
#include "qgroup.h"
#include "ref-verify.h"
#include "space-info.h"
#include "block-rsv.h"
#include "discard.h"
#include "zoned.h"
#include "dev-replace.h"
#include "fs.h"
#include "accessors.h"
#include "root-tree.h"
#include "file-item.h"
#include "orphan.h"
#include "tree-checker.h"
#include "raid-stripe-tree.h"

#undef SCRAMBLE_DELAYED_REFS


static int __btrfs_free_extent(struct btrfs_trans_handle *trans,
          struct btrfs_delayed_ref_head *href,
          const struct btrfs_delayed_ref_node *node,
          struct btrfs_delayed_extent_op *extra_op);
static void __run_delayed_extent_op(struct btrfs_delayed_extent_op *extent_op,
        struct extent_buffer *leaf,
        struct btrfs_extent_item *ei);
static int alloc_reserved_file_extent(struct btrfs_trans_handle *trans,
          u64 parent, u64 root_objectid,
          u64 flags, u64 owner, u64 offset,
          struct btrfs_key *ins, int ref_mod, u64 oref_root);
static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
         const struct btrfs_delayed_ref_node *node,
         struct btrfs_delayed_extent_op *extent_op);
static int find_next_key(const struct btrfs_path *path, int level,
    struct btrfs_key *key);

static int block_group_bits(const struct btrfs_block_group *cache, u64 bits)
{
 return (cache->flags & bits) == bits;
}

/* simple helper to search for an existing data extent at a given offset */
int btrfs_lookup_data_extent(struct btrfs_fs_info *fs_info, u64 start, u64 len)
{
 struct btrfs_root *root = btrfs_extent_root(fs_info, start);
 struct btrfs_key key;
 BTRFS_PATH_AUTO_FREE(path);

 path = btrfs_alloc_path();
 if (!path)
  return -ENOMEM;

 key.objectid = start;
 key.type = BTRFS_EXTENT_ITEM_KEY;
 key.offset = len;
 return btrfs_search_slot(NULL, root, &key, path, 0, 0);
}

/*
 * helper function to lookup reference count and flags of a tree block.
 *
 * the head node for delayed ref is used to store the sum of all the
 * reference count modifications queued up in the rbtree. the head
 * node may also store the extent flags to set. This way you can check
 * to see what the reference count and extent flags would be if all of
 * the delayed refs are not processed.
 */
int btrfs_lookup_extent_info(struct btrfs_trans_handle *trans,
        struct btrfs_fs_info *fs_info, u64 bytenr,
        u64 offset, int metadata, u64 *refs, u64 *flags,
        u64 *owning_root)
{
 struct btrfs_root *extent_root;
 struct btrfs_delayed_ref_head *head;
 struct btrfs_delayed_ref_root *delayed_refs;
 BTRFS_PATH_AUTO_FREE(path);
 struct btrfs_key key;
 u64 num_refs;
 u64 extent_flags;
 u64 owner = 0;
 int ret;

 /*
 * If we don't have skinny metadata, don't bother doing anything
 * different
 */
 if (metadata && !btrfs_fs_incompat(fs_info, SKINNY_METADATA)) {
  offset = fs_info->nodesize;
  metadata = 0;
 }

 path = btrfs_alloc_path();
 if (!path)
  return -ENOMEM;

search_again:
 key.objectid = bytenr;
 if (metadata)
  key.type = BTRFS_METADATA_ITEM_KEY;
 else
  key.type = BTRFS_EXTENT_ITEM_KEY;
 key.offset = offset;

 extent_root = btrfs_extent_root(fs_info, bytenr);
 ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
 if (ret < 0)
  return ret;

 if (ret > 0 && key.type == BTRFS_METADATA_ITEM_KEY) {
  if (path->slots[0]) {
   path->slots[0]--;
   btrfs_item_key_to_cpu(path->nodes[0], &key,
           path->slots[0]);
   if (key.objectid == bytenr &&
       key.type == BTRFS_EXTENT_ITEM_KEY &&
       key.offset == fs_info->nodesize)
    ret = 0;
  }
 }

 if (ret == 0) {
  struct extent_buffer *leaf = path->nodes[0];
  struct btrfs_extent_item *ei;
  const u32 item_size = btrfs_item_size(leaf, path->slots[0]);

  if (unlikely(item_size < sizeof(*ei))) {
   ret = -EUCLEAN;
   btrfs_err(fs_info,
   "unexpected extent item size, has %u expect >= %zu",
      item_size, sizeof(*ei));
   btrfs_abort_transaction(trans, ret);
   return ret;
  }

  ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
  num_refs = btrfs_extent_refs(leaf, ei);
  if (unlikely(num_refs == 0)) {
   ret = -EUCLEAN;
   btrfs_err(fs_info,
  "unexpected zero reference count for extent item (%llu %u %llu)",
      key.objectid, key.type, key.offset);
   btrfs_abort_transaction(trans, ret);
   return ret;
  }
  extent_flags = btrfs_extent_flags(leaf, ei);
  owner = btrfs_get_extent_owner_root(fs_info, leaf, path->slots[0]);
 } else {
  num_refs = 0;
  extent_flags = 0;
  ret = 0;
 }

 delayed_refs = &trans->transaction->delayed_refs;
 spin_lock(&delayed_refs->lock);
 head = btrfs_find_delayed_ref_head(fs_info, delayed_refs, bytenr);
 if (head) {
  if (!mutex_trylock(&head->mutex)) {
   refcount_inc(&head->refs);
   spin_unlock(&delayed_refs->lock);

   btrfs_release_path(path);

   /*
 * Mutex was contended, block until it's released and try
 * again
 */
   mutex_lock(&head->mutex);
   mutex_unlock(&head->mutex);
   btrfs_put_delayed_ref_head(head);
   goto search_again;
  }
  spin_lock(&head->lock);
  if (head->extent_op && head->extent_op->update_flags)
   extent_flags |= head->extent_op->flags_to_set;

  num_refs += head->ref_mod;
  spin_unlock(&head->lock);
  mutex_unlock(&head->mutex);
 }
 spin_unlock(&delayed_refs->lock);

 WARN_ON(num_refs == 0);
 if (refs)
  *refs = num_refs;
 if (flags)
  *flags = extent_flags;
 if (owning_root)
  *owning_root = owner;

 return ret;
}

/*
 * Back reference rules.  Back refs have three main goals:
 *
 * 1) differentiate between all holders of references to an extent so that
 *    when a reference is dropped we can make sure it was a valid reference
 *    before freeing the extent.
 *
 * 2) Provide enough information to quickly find the holders of an extent
 *    if we notice a given block is corrupted or bad.
 *
 * 3) Make it easy to migrate blocks for FS shrinking or storage pool
 *    maintenance.  This is actually the same as #2, but with a slightly
 *    different use case.
 *
 * There are two kinds of back refs. The implicit back refs is optimized
 * for pointers in non-shared tree blocks. For a given pointer in a block,
 * back refs of this kind provide information about the block's owner tree
 * and the pointer's key. These information allow us to find the block by
 * b-tree searching. The full back refs is for pointers in tree blocks not
 * referenced by their owner trees. The location of tree block is recorded
 * in the back refs. Actually the full back refs is generic, and can be
 * used in all cases the implicit back refs is used. The major shortcoming
 * of the full back refs is its overhead. Every time a tree block gets
 * COWed, we have to update back refs entry for all pointers in it.
 *
 * For a newly allocated tree block, we use implicit back refs for
 * pointers in it. This means most tree related operations only involve
 * implicit back refs. For a tree block created in old transaction, the
 * only way to drop a reference to it is COW it. So we can detect the
 * event that tree block loses its owner tree's reference and do the
 * back refs conversion.
 *
 * When a tree block is COWed through a tree, there are four cases:
 *
 * The reference count of the block is one and the tree is the block's
 * owner tree. Nothing to do in this case.
 *
 * The reference count of the block is one and the tree is not the
 * block's owner tree. In this case, full back refs is used for pointers
 * in the block. Remove these full back refs, add implicit back refs for
 * every pointers in the new block.
 *
 * The reference count of the block is greater than one and the tree is
 * the block's owner tree. In this case, implicit back refs is used for
 * pointers in the block. Add full back refs for every pointers in the
 * block, increase lower level extents' reference counts. The original
 * implicit back refs are entailed to the new block.
 *
 * The reference count of the block is greater than one and the tree is
 * not the block's owner tree. Add implicit back refs for every pointer in
 * the new block, increase lower level extents' reference count.
 *
 * Back Reference Key composing:
 *
 * The key objectid corresponds to the first byte in the extent,
 * The key type is used to differentiate between types of back refs.
 * There are different meanings of the key offset for different types
 * of back refs.
 *
 * File extents can be referenced by:
 *
 * - multiple snapshots, subvolumes, or different generations in one subvol
 * - different files inside a single subvolume
 * - different offsets inside a file (bookend extents in file.c)
 *
 * The extent ref structure for the implicit back refs has fields for:
 *
 * - Objectid of the subvolume root
 * - objectid of the file holding the reference
 * - original offset in the file
 * - how many bookend extents
 *
 * The key offset for the implicit back refs is hash of the first
 * three fields.
 *
 * The extent ref structure for the full back refs has field for:
 *
 * - number of pointers in the tree leaf
 *
 * The key offset for the implicit back refs is the first byte of
 * the tree leaf
 *
 * When a file extent is allocated, The implicit back refs is used.
 * the fields are filled in:
 *
 *     (root_key.objectid, inode objectid, offset in file, 1)
 *
 * When a file extent is removed file truncation, we find the
 * corresponding implicit back refs and check the following fields:
 *
 *     (btrfs_header_owner(leaf), inode objectid, offset in file)
 *
 * Btree extents can be referenced by:
 *
 * - Different subvolumes
 *
 * Both the implicit back refs and the full back refs for tree blocks
 * only consist of key. The key offset for the implicit back refs is
 * objectid of block's owner tree. The key offset for the full back refs
 * is the first byte of parent block.
 *
 * When implicit back refs is used, information about the lowest key and
 * level of the tree block are required. These information are stored in
 * tree block info structure.
 */

/*
 * is_data == BTRFS_REF_TYPE_BLOCK, tree block type is required,
 * is_data == BTRFS_REF_TYPE_DATA, data type is requiried,
 * is_data == BTRFS_REF_TYPE_ANY, either type is OK.
 */
int btrfs_get_extent_inline_ref_type(const struct extent_buffer *eb,
         const struct btrfs_extent_inline_ref *iref,
         enum btrfs_inline_ref_type is_data)
{
 struct btrfs_fs_info *fs_info = eb->fs_info;
 int type = btrfs_extent_inline_ref_type(eb, iref);
 u64 offset = btrfs_extent_inline_ref_offset(eb, iref);

 if (type == BTRFS_EXTENT_OWNER_REF_KEY) {
  ASSERT(btrfs_fs_incompat(fs_info, SIMPLE_QUOTA));
  return type;
 }

 if (type == BTRFS_TREE_BLOCK_REF_KEY ||
     type == BTRFS_SHARED_BLOCK_REF_KEY ||
     type == BTRFS_SHARED_DATA_REF_KEY ||
     type == BTRFS_EXTENT_DATA_REF_KEY) {
  if (is_data == BTRFS_REF_TYPE_BLOCK) {
   if (type == BTRFS_TREE_BLOCK_REF_KEY)
    return type;
   if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
    ASSERT(fs_info);
    /*
 * Every shared one has parent tree block,
 * which must be aligned to sector size.
 */
    if (offset && IS_ALIGNED(offset, fs_info->sectorsize))
     return type;
   }
  } else if (is_data == BTRFS_REF_TYPE_DATA) {
   if (type == BTRFS_EXTENT_DATA_REF_KEY)
    return type;
   if (type == BTRFS_SHARED_DATA_REF_KEY) {
    ASSERT(fs_info);
    /*
 * Every shared one has parent tree block,
 * which must be aligned to sector size.
 */
    if (offset &&
        IS_ALIGNED(offset, fs_info->sectorsize))
     return type;
   }
  } else {
   ASSERT(is_data == BTRFS_REF_TYPE_ANY);
   return type;
  }
 }

 WARN_ON(1);
 btrfs_print_leaf(eb);
 btrfs_err(fs_info,
    "eb %llu iref 0x%lx invalid extent inline ref type %d",
    eb->start, (unsigned long)iref, type);

 return BTRFS_REF_TYPE_INVALID;
}

u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset)
{
 u32 high_crc = ~(u32)0;
 u32 low_crc = ~(u32)0;
 __le64 lenum;

 lenum = cpu_to_le64(root_objectid);
 high_crc = crc32c(high_crc, &lenum, sizeof(lenum));
 lenum = cpu_to_le64(owner);
 low_crc = crc32c(low_crc, &lenum, sizeof(lenum));
 lenum = cpu_to_le64(offset);
 low_crc = crc32c(low_crc, &lenum, sizeof(lenum));

 return ((u64)high_crc << 31) ^ (u64)low_crc;
}

static u64 hash_extent_data_ref_item(const struct extent_buffer *leaf,
         const struct btrfs_extent_data_ref *ref)
{
 return hash_extent_data_ref(btrfs_extent_data_ref_root(leaf, ref),
        btrfs_extent_data_ref_objectid(leaf, ref),
        btrfs_extent_data_ref_offset(leaf, ref));
}

static bool match_extent_data_ref(const struct extent_buffer *leaf,
      const struct btrfs_extent_data_ref *ref,
      u64 root_objectid, u64 owner, u64 offset)
{
 if (btrfs_extent_data_ref_root(leaf, ref) != root_objectid ||
     btrfs_extent_data_ref_objectid(leaf, ref) != owner ||
     btrfs_extent_data_ref_offset(leaf, ref) != offset)
  return false;
 return true;
}

static noinline int lookup_extent_data_ref(struct btrfs_trans_handle *trans,
        struct btrfs_path *path,
        u64 bytenr, u64 parent,
        u64 root_objectid,
        u64 owner, u64 offset)
{
 struct btrfs_root *root = btrfs_extent_root(trans->fs_info, bytenr);
 struct btrfs_key key;
 struct btrfs_extent_data_ref *ref;
 struct extent_buffer *leaf;
 u32 nritems;
 int recow;
 int ret;

 key.objectid = bytenr;
 if (parent) {
  key.type = BTRFS_SHARED_DATA_REF_KEY;
  key.offset = parent;
 } else {
  key.type = BTRFS_EXTENT_DATA_REF_KEY;
  key.offset = hash_extent_data_ref(root_objectid,
        owner, offset);
 }
again:
 recow = 0;
 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 if (ret < 0)
  return ret;

 if (parent) {
  if (ret)
   return -ENOENT;
  return 0;
 }

 ret = -ENOENT;
 leaf = path->nodes[0];
 nritems = btrfs_header_nritems(leaf);
 while (1) {
  if (path->slots[0] >= nritems) {
   ret = btrfs_next_leaf(root, path);
   if (ret) {
    if (ret > 0)
     return -ENOENT;
    return ret;
   }

   leaf = path->nodes[0];
   nritems = btrfs_header_nritems(leaf);
   recow = 1;
  }

  btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
  if (key.objectid != bytenr ||
      key.type != BTRFS_EXTENT_DATA_REF_KEY)
   goto fail;

  ref = btrfs_item_ptr(leaf, path->slots[0],
         struct btrfs_extent_data_ref);

  if (match_extent_data_ref(leaf, ref, root_objectid,
       owner, offset)) {
   if (recow) {
    btrfs_release_path(path);
    goto again;
   }
   ret = 0;
   break;
  }
  path->slots[0]++;
 }
fail:
 return ret;
}

static noinline int insert_extent_data_ref(struct btrfs_trans_handle *trans,
        struct btrfs_path *path,
        const struct btrfs_delayed_ref_node *node,
        u64 bytenr)
{
 struct btrfs_root *root = btrfs_extent_root(trans->fs_info, bytenr);
 struct btrfs_key key;
 struct extent_buffer *leaf;
 u64 owner = btrfs_delayed_ref_owner(node);
 u64 offset = btrfs_delayed_ref_offset(node);
 u32 size;
 u32 num_refs;
 int ret;

 key.objectid = bytenr;
 if (node->parent) {
  key.type = BTRFS_SHARED_DATA_REF_KEY;
  key.offset = node->parent;
  size = sizeof(struct btrfs_shared_data_ref);
 } else {
  key.type = BTRFS_EXTENT_DATA_REF_KEY;
  key.offset = hash_extent_data_ref(node->ref_root, owner, offset);
  size = sizeof(struct btrfs_extent_data_ref);
 }

 ret = btrfs_insert_empty_item(trans, root, path, &key, size);
 if (ret && ret != -EEXIST)
  goto fail;

 leaf = path->nodes[0];
 if (node->parent) {
  struct btrfs_shared_data_ref *ref;
  ref = btrfs_item_ptr(leaf, path->slots[0],
         struct btrfs_shared_data_ref);
  if (ret == 0) {
   btrfs_set_shared_data_ref_count(leaf, ref, node->ref_mod);
  } else {
   num_refs = btrfs_shared_data_ref_count(leaf, ref);
   num_refs += node->ref_mod;
   btrfs_set_shared_data_ref_count(leaf, ref, num_refs);
  }
 } else {
  struct btrfs_extent_data_ref *ref;
  while (ret == -EEXIST) {
   ref = btrfs_item_ptr(leaf, path->slots[0],
          struct btrfs_extent_data_ref);
   if (match_extent_data_ref(leaf, ref, node->ref_root,
        owner, offset))
    break;
   btrfs_release_path(path);
   key.offset++;
   ret = btrfs_insert_empty_item(trans, root, path, &key,
            size);
   if (ret && ret != -EEXIST)
    goto fail;

   leaf = path->nodes[0];
  }
  ref = btrfs_item_ptr(leaf, path->slots[0],
         struct btrfs_extent_data_ref);
  if (ret == 0) {
   btrfs_set_extent_data_ref_root(leaf, ref, node->ref_root);
   btrfs_set_extent_data_ref_objectid(leaf, ref, owner);
   btrfs_set_extent_data_ref_offset(leaf, ref, offset);
   btrfs_set_extent_data_ref_count(leaf, ref, node->ref_mod);
  } else {
   num_refs = btrfs_extent_data_ref_count(leaf, ref);
   num_refs += node->ref_mod;
   btrfs_set_extent_data_ref_count(leaf, ref, num_refs);
  }
 }
 ret = 0;
fail:
 btrfs_release_path(path);
 return ret;
}

static noinline int remove_extent_data_ref(struct btrfs_trans_handle *trans,
        struct btrfs_root *root,
        struct btrfs_path *path,
        int refs_to_drop)
{
 struct btrfs_key key;
 struct btrfs_extent_data_ref *ref1 = NULL;
 struct btrfs_shared_data_ref *ref2 = NULL;
 struct extent_buffer *leaf;
 u32 num_refs = 0;
 int ret = 0;

 leaf = path->nodes[0];
 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);

 if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
  ref1 = btrfs_item_ptr(leaf, path->slots[0],
          struct btrfs_extent_data_ref);
  num_refs = btrfs_extent_data_ref_count(leaf, ref1);
 } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
  ref2 = btrfs_item_ptr(leaf, path->slots[0],
          struct btrfs_shared_data_ref);
  num_refs = btrfs_shared_data_ref_count(leaf, ref2);
 } else {
  btrfs_err(trans->fs_info,
     "unrecognized backref key (%llu %u %llu)",
     key.objectid, key.type, key.offset);
  btrfs_abort_transaction(trans, -EUCLEAN);
  return -EUCLEAN;
 }

 BUG_ON(num_refs < refs_to_drop);
 num_refs -= refs_to_drop;

 if (num_refs == 0) {
  ret = btrfs_del_item(trans, root, path);
 } else {
  if (key.type == BTRFS_EXTENT_DATA_REF_KEY)
   btrfs_set_extent_data_ref_count(leaf, ref1, num_refs);
  else if (key.type == BTRFS_SHARED_DATA_REF_KEY)
   btrfs_set_shared_data_ref_count(leaf, ref2, num_refs);
 }
 return ret;
}

static noinline u32 extent_data_ref_count(const struct btrfs_path *path,
       const struct btrfs_extent_inline_ref *iref)
{
 struct btrfs_key key;
 struct extent_buffer *leaf;
 const struct btrfs_extent_data_ref *ref1;
 const struct btrfs_shared_data_ref *ref2;
 u32 num_refs = 0;
 int type;

 leaf = path->nodes[0];
 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);

 if (iref) {
  /*
 * If type is invalid, we should have bailed out earlier than
 * this call.
 */
  type = btrfs_get_extent_inline_ref_type(leaf, iref, BTRFS_REF_TYPE_DATA);
  ASSERT(type != BTRFS_REF_TYPE_INVALID);
  if (type == BTRFS_EXTENT_DATA_REF_KEY) {
   ref1 = (const struct btrfs_extent_data_ref *)(&iref->offset);
   num_refs = btrfs_extent_data_ref_count(leaf, ref1);
  } else {
   ref2 = (const struct btrfs_shared_data_ref *)(iref + 1);
   num_refs = btrfs_shared_data_ref_count(leaf, ref2);
  }
 } else if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
  ref1 = btrfs_item_ptr(leaf, path->slots[0],
          struct btrfs_extent_data_ref);
  num_refs = btrfs_extent_data_ref_count(leaf, ref1);
 } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
  ref2 = btrfs_item_ptr(leaf, path->slots[0],
          struct btrfs_shared_data_ref);
  num_refs = btrfs_shared_data_ref_count(leaf, ref2);
 } else {
  WARN_ON(1);
 }
 return num_refs;
}

static noinline int lookup_tree_block_ref(struct btrfs_trans_handle *trans,
       struct btrfs_path *path,
       u64 bytenr, u64 parent,
       u64 root_objectid)
{
 struct btrfs_root *root = btrfs_extent_root(trans->fs_info, bytenr);
 struct btrfs_key key;
 int ret;

 key.objectid = bytenr;
 if (parent) {
  key.type = BTRFS_SHARED_BLOCK_REF_KEY;
  key.offset = parent;
 } else {
  key.type = BTRFS_TREE_BLOCK_REF_KEY;
  key.offset = root_objectid;
 }

 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 if (ret > 0)
  ret = -ENOENT;
 return ret;
}

static noinline int insert_tree_block_ref(struct btrfs_trans_handle *trans,
       struct btrfs_path *path,
       const struct btrfs_delayed_ref_node *node,
       u64 bytenr)
{
 struct btrfs_root *root = btrfs_extent_root(trans->fs_info, bytenr);
 struct btrfs_key key;
 int ret;

 key.objectid = bytenr;
 if (node->parent) {
  key.type = BTRFS_SHARED_BLOCK_REF_KEY;
  key.offset = node->parent;
 } else {
  key.type = BTRFS_TREE_BLOCK_REF_KEY;
  key.offset = node->ref_root;
 }

 ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
 btrfs_release_path(path);
 return ret;
}

static inline int extent_ref_type(u64 parent, u64 owner)
{
 int type;
 if (owner < BTRFS_FIRST_FREE_OBJECTID) {
  if (parent > 0)
   type = BTRFS_SHARED_BLOCK_REF_KEY;
  else
   type = BTRFS_TREE_BLOCK_REF_KEY;
 } else {
  if (parent > 0)
   type = BTRFS_SHARED_DATA_REF_KEY;
  else
   type = BTRFS_EXTENT_DATA_REF_KEY;
 }
 return type;
}

static int find_next_key(const struct btrfs_path *path, int level,
    struct btrfs_key *key)

{
 for (; level < BTRFS_MAX_LEVEL; level++) {
  if (!path->nodes[level])
   break;
  if (path->slots[level] + 1 >=
      btrfs_header_nritems(path->nodes[level]))
   continue;
  if (level == 0)
   btrfs_item_key_to_cpu(path->nodes[level], key,
           path->slots[level] + 1);
  else
   btrfs_node_key_to_cpu(path->nodes[level], key,
           path->slots[level] + 1);
  return 0;
 }
 return 1;
}

/*
 * look for inline back ref. if back ref is found, *ref_ret is set
 * to the address of inline back ref, and 0 is returned.
 *
 * if back ref isn't found, *ref_ret is set to the address where it
 * should be inserted, and -ENOENT is returned.
 *
 * if insert is true and there are too many inline back refs, the path
 * points to the extent item, and -EAGAIN is returned.
 *
 * NOTE: inline back refs are ordered in the same way that back ref
 *  items in the tree are ordered.
 */
static noinline_for_stack
int lookup_inline_extent_backref(struct btrfs_trans_handle *trans,
     struct btrfs_path *path,
     struct btrfs_extent_inline_ref **ref_ret,
     u64 bytenr, u64 num_bytes,
     u64 parent, u64 root_objectid,
     u64 owner, u64 offset, int insert)
{
 struct btrfs_fs_info *fs_info = trans->fs_info;
 struct btrfs_root *root = btrfs_extent_root(fs_info, bytenr);
 struct btrfs_key key;
 struct extent_buffer *leaf;
 struct btrfs_extent_item *ei;
 struct btrfs_extent_inline_ref *iref;
 u64 flags;
 u64 item_size;
 unsigned long ptr;
 unsigned long end;
 int extra_size;
 int type;
 int want;
 int ret;
 bool skinny_metadata = btrfs_fs_incompat(fs_info, SKINNY_METADATA);
 int needed;

 key.objectid = bytenr;
 key.type = BTRFS_EXTENT_ITEM_KEY;
 key.offset = num_bytes;

 want = extent_ref_type(parent, owner);
 if (insert) {
  extra_size = btrfs_extent_inline_ref_size(want);
  path->search_for_extension = 1;
 } else
  extra_size = -1;

 /*
 * Owner is our level, so we can just add one to get the level for the
 * block we are interested in.
 */
 if (skinny_metadata && owner < BTRFS_FIRST_FREE_OBJECTID) {
  key.type = BTRFS_METADATA_ITEM_KEY;
  key.offset = owner;
 }

again:
 ret = btrfs_search_slot(trans, root, &key, path, extra_size, 1);
 if (ret < 0)
  goto out;

 /*
 * We may be a newly converted file system which still has the old fat
 * extent entries for metadata, so try and see if we have one of those.
 */
 if (ret > 0 && skinny_metadata) {
  skinny_metadata = false;
  if (path->slots[0]) {
   path->slots[0]--;
   btrfs_item_key_to_cpu(path->nodes[0], &key,
           path->slots[0]);
   if (key.objectid == bytenr &&
       key.type == BTRFS_EXTENT_ITEM_KEY &&
       key.offset == num_bytes)
    ret = 0;
  }
  if (ret) {
   key.objectid = bytenr;
   key.type = BTRFS_EXTENT_ITEM_KEY;
   key.offset = num_bytes;
   btrfs_release_path(path);
   goto again;
  }
 }

 if (ret && !insert) {
  ret = -ENOENT;
  goto out;
 } else if (WARN_ON(ret)) {
  btrfs_print_leaf(path->nodes[0]);
  btrfs_err(fs_info,
"extent item not found for insert, bytenr %llu num_bytes %llu parent %llu root_objectid %llu owner %llu offset %llu",
     bytenr, num_bytes, parent, root_objectid, owner,
     offset);
  ret = -EUCLEAN;
  goto out;
 }

 leaf = path->nodes[0];
 item_size = btrfs_item_size(leaf, path->slots[0]);
 if (unlikely(item_size < sizeof(*ei))) {
  ret = -EUCLEAN;
  btrfs_err(fs_info,
     "unexpected extent item size, has %llu expect >= %zu",
     item_size, sizeof(*ei));
  btrfs_abort_transaction(trans, ret);
  goto out;
 }

 ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
 flags = btrfs_extent_flags(leaf, ei);

 ptr = (unsigned long)(ei + 1);
 end = (unsigned long)ei + item_size;

 if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK && !skinny_metadata) {
  ptr += sizeof(struct btrfs_tree_block_info);
  BUG_ON(ptr > end);
 }

 if (owner >= BTRFS_FIRST_FREE_OBJECTID)
  needed = BTRFS_REF_TYPE_DATA;
 else
  needed = BTRFS_REF_TYPE_BLOCK;

 ret = -ENOENT;
 while (ptr < end) {
  iref = (struct btrfs_extent_inline_ref *)ptr;
  type = btrfs_get_extent_inline_ref_type(leaf, iref, needed);
  if (type == BTRFS_EXTENT_OWNER_REF_KEY) {
   ASSERT(btrfs_fs_incompat(fs_info, SIMPLE_QUOTA));
   ptr += btrfs_extent_inline_ref_size(type);
   continue;
  }
  if (type == BTRFS_REF_TYPE_INVALID) {
   ret = -EUCLEAN;
   goto out;
  }

  if (want < type)
   break;
  if (want > type) {
   ptr += btrfs_extent_inline_ref_size(type);
   continue;
  }

  if (type == BTRFS_EXTENT_DATA_REF_KEY) {
   struct btrfs_extent_data_ref *dref;
   dref = (struct btrfs_extent_data_ref *)(&iref->offset);
   if (match_extent_data_ref(leaf, dref, root_objectid,
        owner, offset)) {
    ret = 0;
    break;
   }
   if (hash_extent_data_ref_item(leaf, dref) <
       hash_extent_data_ref(root_objectid, owner, offset))
    break;
  } else {
   u64 ref_offset;
   ref_offset = btrfs_extent_inline_ref_offset(leaf, iref);
   if (parent > 0) {
    if (parent == ref_offset) {
     ret = 0;
     break;
    }
    if (ref_offset < parent)
     break;
   } else {
    if (root_objectid == ref_offset) {
     ret = 0;
     break;
    }
    if (ref_offset < root_objectid)
     break;
   }
  }
  ptr += btrfs_extent_inline_ref_size(type);
 }

 if (unlikely(ptr > end)) {
  ret = -EUCLEAN;
  btrfs_print_leaf(path->nodes[0]);
  btrfs_crit(fs_info,
"overrun extent record at slot %d while looking for inline extent for root %llu owner %llu offset %llu parent %llu",
      path->slots[0], root_objectid, owner, offset, parent);
  goto out;
 }

 if (ret == -ENOENT && insert) {
  if (item_size + extra_size >=
      BTRFS_MAX_EXTENT_ITEM_SIZE(root)) {
   ret = -EAGAIN;
   goto out;
  }

  if (path->slots[0] + 1 < btrfs_header_nritems(path->nodes[0])) {
   struct btrfs_key tmp_key;

   btrfs_item_key_to_cpu(path->nodes[0], &tmp_key, path->slots[0] + 1);
   if (tmp_key.objectid == bytenr &&
       tmp_key.type < BTRFS_BLOCK_GROUP_ITEM_KEY) {
    ret = -EAGAIN;
    goto out;
   }
   goto out_no_entry;
  }

  if (!path->keep_locks) {
   btrfs_release_path(path);
   path->keep_locks = 1;
   goto again;
  }

  /*
 * To add new inline back ref, we have to make sure
 * there is no corresponding back ref item.
 * For simplicity, we just do not add new inline back
 * ref if there is any kind of item for this block
 */
  if (find_next_key(path, 0, &key) == 0 &&
      key.objectid == bytenr &&
      key.type < BTRFS_BLOCK_GROUP_ITEM_KEY) {
   ret = -EAGAIN;
   goto out;
  }
 }
out_no_entry:
 *ref_ret = (struct btrfs_extent_inline_ref *)ptr;
out:
 if (path->keep_locks) {
  path->keep_locks = 0;
  btrfs_unlock_up_safe(path, 1);
 }
 if (insert)
  path->search_for_extension = 0;
 return ret;
}

/*
 * helper to add new inline back ref
 */
static noinline_for_stack
void setup_inline_extent_backref(struct btrfs_trans_handle *trans,
     struct btrfs_path *path,
     struct btrfs_extent_inline_ref *iref,
     u64 parent, u64 root_objectid,
     u64 owner, u64 offset, int refs_to_add,
     struct btrfs_delayed_extent_op *extent_op)
{
 struct extent_buffer *leaf;
 struct btrfs_extent_item *ei;
 unsigned long ptr;
 unsigned long end;
 unsigned long item_offset;
 u64 refs;
 int size;
 int type;

 leaf = path->nodes[0];
 ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
 item_offset = (unsigned long)iref - (unsigned long)ei;

 type = extent_ref_type(parent, owner);
 size = btrfs_extent_inline_ref_size(type);

 btrfs_extend_item(trans, path, size);

 ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
 refs = btrfs_extent_refs(leaf, ei);
 refs += refs_to_add;
 btrfs_set_extent_refs(leaf, ei, refs);
 if (extent_op)
  __run_delayed_extent_op(extent_op, leaf, ei);

 ptr = (unsigned long)ei + item_offset;
 end = (unsigned long)ei + btrfs_item_size(leaf, path->slots[0]);
 if (ptr < end - size)
  memmove_extent_buffer(leaf, ptr + size, ptr,
          end - size - ptr);

 iref = (struct btrfs_extent_inline_ref *)ptr;
 btrfs_set_extent_inline_ref_type(leaf, iref, type);
 if (type == BTRFS_EXTENT_DATA_REF_KEY) {
  struct btrfs_extent_data_ref *dref;
  dref = (struct btrfs_extent_data_ref *)(&iref->offset);
  btrfs_set_extent_data_ref_root(leaf, dref, root_objectid);
  btrfs_set_extent_data_ref_objectid(leaf, dref, owner);
  btrfs_set_extent_data_ref_offset(leaf, dref, offset);
  btrfs_set_extent_data_ref_count(leaf, dref, refs_to_add);
 } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
  struct btrfs_shared_data_ref *sref;
  sref = (struct btrfs_shared_data_ref *)(iref + 1);
  btrfs_set_shared_data_ref_count(leaf, sref, refs_to_add);
  btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
 } else if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
  btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
 } else {
  btrfs_set_extent_inline_ref_offset(leaf, iref, root_objectid);
 }
}

static int lookup_extent_backref(struct btrfs_trans_handle *trans,
     struct btrfs_path *path,
     struct btrfs_extent_inline_ref **ref_ret,
     u64 bytenr, u64 num_bytes, u64 parent,
     u64 root_objectid, u64 owner, u64 offset)
{
 int ret;

 ret = lookup_inline_extent_backref(trans, path, ref_ret, bytenr,
        num_bytes, parent, root_objectid,
        owner, offset, 0);
 if (ret != -ENOENT)
  return ret;

 btrfs_release_path(path);
 *ref_ret = NULL;

 if (owner < BTRFS_FIRST_FREE_OBJECTID) {
  ret = lookup_tree_block_ref(trans, path, bytenr, parent,
         root_objectid);
 } else {
  ret = lookup_extent_data_ref(trans, path, bytenr, parent,
          root_objectid, owner, offset);
 }
 return ret;
}

/*
 * helper to update/remove inline back ref
 */
static noinline_for_stack int update_inline_extent_backref(
      struct btrfs_trans_handle *trans,
      struct btrfs_path *path,
      struct btrfs_extent_inline_ref *iref,
      int refs_to_mod,
      struct btrfs_delayed_extent_op *extent_op)
{
 struct extent_buffer *leaf = path->nodes[0];
 struct btrfs_fs_info *fs_info = leaf->fs_info;
 struct btrfs_extent_item *ei;
 struct btrfs_extent_data_ref *dref = NULL;
 struct btrfs_shared_data_ref *sref = NULL;
 unsigned long ptr;
 unsigned long end;
 u32 item_size;
 int size;
 int type;
 u64 refs;

 ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
 refs = btrfs_extent_refs(leaf, ei);
 if (unlikely(refs_to_mod < 0 && refs + refs_to_mod <= 0)) {
  struct btrfs_key key;
  u32 extent_size;

  btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
  if (key.type == BTRFS_METADATA_ITEM_KEY)
   extent_size = fs_info->nodesize;
  else
   extent_size = key.offset;
  btrfs_print_leaf(leaf);
  btrfs_err(fs_info,
 "invalid refs_to_mod for extent %llu num_bytes %u, has %d expect >= -%llu",
     key.objectid, extent_size, refs_to_mod, refs);
  return -EUCLEAN;
 }
 refs += refs_to_mod;
 btrfs_set_extent_refs(leaf, ei, refs);
 if (extent_op)
  __run_delayed_extent_op(extent_op, leaf, ei);

 type = btrfs_get_extent_inline_ref_type(leaf, iref, BTRFS_REF_TYPE_ANY);
 /*
 * Function btrfs_get_extent_inline_ref_type() has already printed
 * error messages.
 */
 if (unlikely(type == BTRFS_REF_TYPE_INVALID))
  return -EUCLEAN;

 if (type == BTRFS_EXTENT_DATA_REF_KEY) {
  dref = (struct btrfs_extent_data_ref *)(&iref->offset);
  refs = btrfs_extent_data_ref_count(leaf, dref);
 } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
  sref = (struct btrfs_shared_data_ref *)(iref + 1);
  refs = btrfs_shared_data_ref_count(leaf, sref);
 } else {
  refs = 1;
  /*
 * For tree blocks we can only drop one ref for it, and tree
 * blocks should not have refs > 1.
 *
 * Furthermore if we're inserting a new inline backref, we
 * won't reach this path either. That would be
 * setup_inline_extent_backref().
 */
  if (unlikely(refs_to_mod != -1)) {
   struct btrfs_key key;

   btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);

   btrfs_print_leaf(leaf);
   btrfs_err(fs_info,
   "invalid refs_to_mod for tree block %llu, has %d expect -1",
      key.objectid, refs_to_mod);
   return -EUCLEAN;
  }
 }

 if (unlikely(refs_to_mod < 0 && refs < -refs_to_mod)) {
  struct btrfs_key key;
  u32 extent_size;

  btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
  if (key.type == BTRFS_METADATA_ITEM_KEY)
   extent_size = fs_info->nodesize;
  else
   extent_size = key.offset;
  btrfs_print_leaf(leaf);
  btrfs_err(fs_info,
"invalid refs_to_mod for backref entry, iref %lu extent %llu num_bytes %u, has %d expect >= -%llu",
     (unsigned long)iref, key.objectid, extent_size,
     refs_to_mod, refs);
  return -EUCLEAN;
 }
 refs += refs_to_mod;

 if (refs > 0) {
  if (type == BTRFS_EXTENT_DATA_REF_KEY)
   btrfs_set_extent_data_ref_count(leaf, dref, refs);
  else
   btrfs_set_shared_data_ref_count(leaf, sref, refs);
 } else {
  size =  btrfs_extent_inline_ref_size(type);
  item_size = btrfs_item_size(leaf, path->slots[0]);
  ptr = (unsigned long)iref;
  end = (unsigned long)ei + item_size;
  if (ptr + size < end)
   memmove_extent_buffer(leaf, ptr, ptr + size,
           end - ptr - size);
  item_size -= size;
  btrfs_truncate_item(trans, path, item_size, 1);
 }
 return 0;
}

static noinline_for_stack
int insert_inline_extent_backref(struct btrfs_trans_handle *trans,
     struct btrfs_path *path,
     u64 bytenr, u64 num_bytes, u64 parent,
     u64 root_objectid, u64 owner,
     u64 offset, int refs_to_add,
     struct btrfs_delayed_extent_op *extent_op)
{
 struct btrfs_extent_inline_ref *iref;
 int ret;

 ret = lookup_inline_extent_backref(trans, path, &iref, bytenr,
        num_bytes, parent, root_objectid,
        owner, offset, 1);
 if (ret == 0) {
  /*
 * We're adding refs to a tree block we already own, this
 * should not happen at all.
 */
  if (owner < BTRFS_FIRST_FREE_OBJECTID) {
   btrfs_print_leaf(path->nodes[0]);
   btrfs_crit(trans->fs_info,
"adding refs to an existing tree ref, bytenr %llu num_bytes %llu root_objectid %llu slot %u",
       bytenr, num_bytes, root_objectid, path->slots[0]);
   return -EUCLEAN;
  }
  ret = update_inline_extent_backref(trans, path, iref,
         refs_to_add, extent_op);
 } else if (ret == -ENOENT) {
  setup_inline_extent_backref(trans, path, iref, parent,
         root_objectid, owner, offset,
         refs_to_add, extent_op);
  ret = 0;
 }
 return ret;
}

static int remove_extent_backref(struct btrfs_trans_handle *trans,
     struct btrfs_root *root,
     struct btrfs_path *path,
     struct btrfs_extent_inline_ref *iref,
     int refs_to_drop, int is_data)
{
 int ret = 0;

 BUG_ON(!is_data && refs_to_drop != 1);
 if (iref)
  ret = update_inline_extent_backref(trans, path, iref,
         -refs_to_drop, NULL);
 else if (is_data)
  ret = remove_extent_data_ref(trans, root, path, refs_to_drop);
 else
  ret = btrfs_del_item(trans, root, path);
 return ret;
}

static int btrfs_issue_discard(struct block_device *bdev, u64 start, u64 len,
          u64 *discarded_bytes)
{
 int j, ret = 0;
 u64 bytes_left, end;
 u64 aligned_start = ALIGN(start, SECTOR_SIZE);

 /* Adjust the range to be aligned to 512B sectors if necessary. */
 if (start != aligned_start) {
  len -= aligned_start - start;
  len = round_down(len, SECTOR_SIZE);
  start = aligned_start;
 }

 *discarded_bytes = 0;

 if (!len)
  return 0;

 end = start + len;
 bytes_left = len;

 /* Skip any superblocks on this device. */
 for (j = 0; j < BTRFS_SUPER_MIRROR_MAX; j++) {
  u64 sb_start = btrfs_sb_offset(j);
  u64 sb_end = sb_start + BTRFS_SUPER_INFO_SIZE;
  u64 size = sb_start - start;

  if (!in_range(sb_start, start, bytes_left) &&
      !in_range(sb_end, start, bytes_left) &&
      !in_range(start, sb_start, BTRFS_SUPER_INFO_SIZE))
   continue;

  /*
 * Superblock spans beginning of range.  Adjust start and
 * try again.
 */
  if (sb_start <= start) {
   start += sb_end - start;
   if (start > end) {
    bytes_left = 0;
    break;
   }
   bytes_left = end - start;
   continue;
  }

  if (size) {
   ret = blkdev_issue_discard(bdev, start >> SECTOR_SHIFT,
         size >> SECTOR_SHIFT,
         GFP_NOFS);
   if (!ret)
    *discarded_bytes += size;
   else if (ret != -EOPNOTSUPP)
    return ret;
  }

  start = sb_end;
  if (start > end) {
   bytes_left = 0;
   break;
  }
  bytes_left = end - start;
 }

 while (bytes_left) {
  u64 bytes_to_discard = min(BTRFS_MAX_DISCARD_CHUNK_SIZE, bytes_left);

  ret = blkdev_issue_discard(bdev, start >> SECTOR_SHIFT,
        bytes_to_discard >> SECTOR_SHIFT,
        GFP_NOFS);

  if (ret) {
   if (ret != -EOPNOTSUPP)
    break;
   continue;
  }

  start += bytes_to_discard;
  bytes_left -= bytes_to_discard;
  *discarded_bytes += bytes_to_discard;

  if (btrfs_trim_interrupted()) {
   ret = -ERESTARTSYS;
   break;
  }
 }

 return ret;
}

static int do_discard_extent(struct btrfs_discard_stripe *stripe, u64 *bytes)
{
 struct btrfs_device *dev = stripe->dev;
 struct btrfs_fs_info *fs_info = dev->fs_info;
 struct btrfs_dev_replace *dev_replace = &fs_info->dev_replace;
 u64 phys = stripe->physical;
 u64 len = stripe->length;
 u64 discarded = 0;
 int ret = 0;

 /* Zone reset on a zoned filesystem */
 if (btrfs_can_zone_reset(dev, phys, len)) {
  u64 src_disc;

  ret = btrfs_reset_device_zone(dev, phys, len, &discarded);
  if (ret)
   goto out;

  if (!btrfs_dev_replace_is_ongoing(dev_replace) ||
      dev != dev_replace->srcdev)
   goto out;

  src_disc = discarded;

  /* Send to replace target as well */
  ret = btrfs_reset_device_zone(dev_replace->tgtdev, phys, len,
           &discarded);
  discarded += src_disc;
 } else if (bdev_max_discard_sectors(stripe->dev->bdev)) {
  ret = btrfs_issue_discard(dev->bdev, phys, len, &discarded);
 } else {
  ret = 0;
  *bytes = 0;
 }

out:
 *bytes = discarded;
 return ret;
}

int btrfs_discard_extent(struct btrfs_fs_info *fs_info, u64 bytenr,
    u64 num_bytes, u64 *actual_bytes)
{
 int ret = 0;
 u64 discarded_bytes = 0;
 u64 end = bytenr + num_bytes;
 u64 cur = bytenr;

 /*
 * Avoid races with device replace and make sure the devices in the
 * stripes don't go away while we are discarding.
 */
 btrfs_bio_counter_inc_blocked(fs_info);
 while (cur < end) {
  struct btrfs_discard_stripe *stripes;
  unsigned int num_stripes;
  int i;

  num_bytes = end - cur;
  stripes = btrfs_map_discard(fs_info, cur, &num_bytes, &num_stripes);
  if (IS_ERR(stripes)) {
   ret = PTR_ERR(stripes);
   if (ret == -EOPNOTSUPP)
    ret = 0;
   break;
  }

  for (i = 0; i < num_stripes; i++) {
   struct btrfs_discard_stripe *stripe = stripes + i;
   u64 bytes;

   if (!stripe->dev->bdev) {
    ASSERT(btrfs_test_opt(fs_info, DEGRADED));
    continue;
   }

   if (!test_bit(BTRFS_DEV_STATE_WRITEABLE,
     &stripe->dev->dev_state))
    continue;

   ret = do_discard_extent(stripe, &bytes);
   if (ret) {
    /*
 * Keep going if discard is not supported by the
 * device.
 */
    if (ret != -EOPNOTSUPP)
     break;
    ret = 0;
   } else {
    discarded_bytes += bytes;
   }
  }
  kfree(stripes);
  if (ret)
   break;
  cur += num_bytes;
 }
 btrfs_bio_counter_dec(fs_info);
 if (actual_bytes)
  *actual_bytes = discarded_bytes;
 return ret;
}

/* Can return -ENOMEM */
int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
    struct btrfs_ref *generic_ref)
{
 struct btrfs_fs_info *fs_info = trans->fs_info;
 int ret;

 ASSERT(generic_ref->type != BTRFS_REF_NOT_SET &&
        generic_ref->action);
 BUG_ON(generic_ref->type == BTRFS_REF_METADATA &&
        generic_ref->ref_root == BTRFS_TREE_LOG_OBJECTID);

 if (generic_ref->type == BTRFS_REF_METADATA)
  ret = btrfs_add_delayed_tree_ref(trans, generic_ref, NULL);
 else
  ret = btrfs_add_delayed_data_ref(trans, generic_ref, 0);

 btrfs_ref_tree_mod(fs_info, generic_ref);

 return ret;
}

/*
 * Insert backreference for a given extent.
 *
 * The counterpart is in __btrfs_free_extent(), with examples and more details
 * how it works.
 *
 * @trans:     Handle of transaction
 *
 * @node:     The delayed ref node used to get the bytenr/length for
 *     extent whose references are incremented.
 *
 * @extent_op       Pointer to a structure, holding information necessary when
 *                  updating a tree block's flags
 *
 */
static int __btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
      const struct btrfs_delayed_ref_node *node,
      struct btrfs_delayed_extent_op *extent_op)
{
 BTRFS_PATH_AUTO_FREE(path);
 struct extent_buffer *leaf;
 struct btrfs_extent_item *item;
 struct btrfs_key key;
 u64 bytenr = node->bytenr;
 u64 num_bytes = node->num_bytes;
 u64 owner = btrfs_delayed_ref_owner(node);
 u64 offset = btrfs_delayed_ref_offset(node);
 u64 refs;
 int refs_to_add = node->ref_mod;
 int ret;

 path = btrfs_alloc_path();
 if (!path)
  return -ENOMEM;

 /* this will setup the path even if it fails to insert the back ref */
 ret = insert_inline_extent_backref(trans, path, bytenr, num_bytes,
        node->parent, node->ref_root, owner,
        offset, refs_to_add, extent_op);
 if ((ret < 0 && ret != -EAGAIN) || !ret)
  return ret;

 /*
 * Ok we had -EAGAIN which means we didn't have space to insert and
 * inline extent ref, so just update the reference count and add a
 * normal backref.
 */
 leaf = path->nodes[0];
 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
 item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
 refs = btrfs_extent_refs(leaf, item);
 btrfs_set_extent_refs(leaf, item, refs + refs_to_add);
 if (extent_op)
  __run_delayed_extent_op(extent_op, leaf, item);

 btrfs_release_path(path);

 /* now insert the actual backref */
 if (owner < BTRFS_FIRST_FREE_OBJECTID) {
  ret = insert_tree_block_ref(trans, path, node, bytenr);
  if (ret)
   btrfs_abort_transaction(trans, ret);
 } else {
  ret = insert_extent_data_ref(trans, path, node, bytenr);
  if (ret)
   btrfs_abort_transaction(trans, ret);
 }

 return ret;
}

static void free_head_ref_squota_rsv(struct btrfs_fs_info *fs_info,
         const struct btrfs_delayed_ref_head *href)
{
 u64 root = href->owning_root;

 /*
 * Don't check must_insert_reserved, as this is called from contexts
 * where it has already been unset.
 */
 if (btrfs_qgroup_mode(fs_info) != BTRFS_QGROUP_MODE_SIMPLE ||
     !href->is_data || !btrfs_is_fstree(root))
  return;

 btrfs_qgroup_free_refroot(fs_info, root, href->reserved_bytes,
      BTRFS_QGROUP_RSV_DATA);
}

static int run_delayed_data_ref(struct btrfs_trans_handle *trans,
    struct btrfs_delayed_ref_head *href,
    const struct btrfs_delayed_ref_node *node,
    struct btrfs_delayed_extent_op *extent_op,
    bool insert_reserved)
{
 int ret = 0;
 u64 parent = 0;
 u64 flags = 0;

 trace_run_delayed_data_ref(trans->fs_info, node);

 if (node->type == BTRFS_SHARED_DATA_REF_KEY)
  parent = node->parent;

 if (node->action == BTRFS_ADD_DELAYED_REF && insert_reserved) {
  struct btrfs_key key;
  struct btrfs_squota_delta delta = {
   .root = href->owning_root,
   .num_bytes = node->num_bytes,
   .is_data = true,
   .is_inc = true,
   .generation = trans->transid,
  };
  u64 owner = btrfs_delayed_ref_owner(node);
  u64 offset = btrfs_delayed_ref_offset(node);

  if (extent_op)
   flags |= extent_op->flags_to_set;

  key.objectid = node->bytenr;
  key.type = BTRFS_EXTENT_ITEM_KEY;
  key.offset = node->num_bytes;

  ret = alloc_reserved_file_extent(trans, parent, node->ref_root,
       flags, owner, offset, &key,
       node->ref_mod,
       href->owning_root);
  free_head_ref_squota_rsv(trans->fs_info, href);
  if (!ret)
   ret = btrfs_record_squota_delta(trans->fs_info, &delta);
 } else if (node->action == BTRFS_ADD_DELAYED_REF) {
  ret = __btrfs_inc_extent_ref(trans, node, extent_op);
 } else if (node->action == BTRFS_DROP_DELAYED_REF) {
  ret = __btrfs_free_extent(trans, href, node, extent_op);
 } else {
  BUG();
 }
 return ret;
}

static void __run_delayed_extent_op(struct btrfs_delayed_extent_op *extent_op,
        struct extent_buffer *leaf,
        struct btrfs_extent_item *ei)
{
 u64 flags = btrfs_extent_flags(leaf, ei);
 if (extent_op->update_flags) {
  flags |= extent_op->flags_to_set;
  btrfs_set_extent_flags(leaf, ei, flags);
 }

 if (extent_op->update_key) {
  struct btrfs_tree_block_info *bi;
  BUG_ON(!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK));
  bi = (struct btrfs_tree_block_info *)(ei + 1);
  btrfs_set_tree_block_key(leaf, bi, &extent_op->key);
 }
}

static int run_delayed_extent_op(struct btrfs_trans_handle *trans,
     const struct btrfs_delayed_ref_head *head,
     struct btrfs_delayed_extent_op *extent_op)
{
 struct btrfs_fs_info *fs_info = trans->fs_info;
 struct btrfs_root *root;
 struct btrfs_key key;
 BTRFS_PATH_AUTO_FREE(path);
 struct btrfs_extent_item *ei;
 struct extent_buffer *leaf;
 u32 item_size;
 int ret;
 int metadata = 1;

 if (TRANS_ABORTED(trans))
  return 0;

 if (!btrfs_fs_incompat(fs_info, SKINNY_METADATA))
  metadata = 0;

 path = btrfs_alloc_path();
 if (!path)
  return -ENOMEM;

 key.objectid = head->bytenr;

 if (metadata) {
  key.type = BTRFS_METADATA_ITEM_KEY;
  key.offset = head->level;
 } else {
  key.type = BTRFS_EXTENT_ITEM_KEY;
  key.offset = head->num_bytes;
 }

 root = btrfs_extent_root(fs_info, key.objectid);
again:
 ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
 if (ret < 0) {
  return ret;
 } else if (ret > 0) {
  if (metadata) {
   if (path->slots[0] > 0) {
    path->slots[0]--;
    btrfs_item_key_to_cpu(path->nodes[0], &key,
            path->slots[0]);
    if (key.objectid == head->bytenr &&
        key.type == BTRFS_EXTENT_ITEM_KEY &&
        key.offset == head->num_bytes)
     ret = 0;
   }
   if (ret > 0) {
    btrfs_release_path(path);
    metadata = 0;

    key.objectid = head->bytenr;
    key.type = BTRFS_EXTENT_ITEM_KEY;
    key.offset = head->num_bytes;
    goto again;
   }
  } else {
   ret = -EUCLEAN;
   btrfs_err(fs_info,
    "missing extent item for extent %llu num_bytes %llu level %d",
      head->bytenr, head->num_bytes, head->level);
   return ret;
  }
 }

 leaf = path->nodes[0];
 item_size = btrfs_item_size(leaf, path->slots[0]);

 if (unlikely(item_size < sizeof(*ei))) {
  ret = -EUCLEAN;
  btrfs_err(fs_info,
     "unexpected extent item size, has %u expect >= %zu",
     item_size, sizeof(*ei));
  btrfs_abort_transaction(trans, ret);
  return ret;
 }

 ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
 __run_delayed_extent_op(extent_op, leaf, ei);

 return ret;
}

static int run_delayed_tree_ref(struct btrfs_trans_handle *trans,
    struct btrfs_delayed_ref_head *href,
    const struct btrfs_delayed_ref_node *node,
    struct btrfs_delayed_extent_op *extent_op,
    bool insert_reserved)
{
 int ret = 0;
 struct btrfs_fs_info *fs_info = trans->fs_info;
 u64 parent = 0;
 u64 ref_root = 0;

 trace_run_delayed_tree_ref(trans->fs_info, node);

 if (node->type == BTRFS_SHARED_BLOCK_REF_KEY)
  parent = node->parent;
 ref_root = node->ref_root;

 if (unlikely(node->ref_mod != 1)) {
  btrfs_err(trans->fs_info,
 "btree block %llu has %d references rather than 1: action %d ref_root %llu parent %llu",
     node->bytenr, node->ref_mod, node->action, ref_root,
     parent);
  return -EUCLEAN;
 }
 if (node->action == BTRFS_ADD_DELAYED_REF && insert_reserved) {
  struct btrfs_squota_delta delta = {
   .root = href->owning_root,
   .num_bytes = fs_info->nodesize,
   .is_data = false,
   .is_inc = true,
   .generation = trans->transid,
  };

  ret = alloc_reserved_tree_block(trans, node, extent_op);
  if (!ret)
   btrfs_record_squota_delta(fs_info, &delta);
 } else if (node->action == BTRFS_ADD_DELAYED_REF) {
  ret = __btrfs_inc_extent_ref(trans, node, extent_op);
 } else if (node->action == BTRFS_DROP_DELAYED_REF) {
  ret = __btrfs_free_extent(trans, href, node, extent_op);
 } else {
  BUG();
 }
 return ret;
}

/* helper function to actually process a single delayed ref entry */
static int run_one_delayed_ref(struct btrfs_trans_handle *trans,
          struct btrfs_delayed_ref_head *href,
          const struct btrfs_delayed_ref_node *node,
          struct btrfs_delayed_extent_op *extent_op,
          bool insert_reserved)
{
 int ret = 0;

 if (TRANS_ABORTED(trans)) {
  if (insert_reserved) {
   btrfs_pin_extent(trans, node->bytenr, node->num_bytes, 1);
   free_head_ref_squota_rsv(trans->fs_info, href);
  }
  return 0;
 }

 if (node->type == BTRFS_TREE_BLOCK_REF_KEY ||
     node->type == BTRFS_SHARED_BLOCK_REF_KEY)
  ret = run_delayed_tree_ref(trans, href, node, extent_op,
        insert_reserved);
 else if (node->type == BTRFS_EXTENT_DATA_REF_KEY ||
   node->type == BTRFS_SHARED_DATA_REF_KEY)
  ret = run_delayed_data_ref(trans, href, node, extent_op,
        insert_reserved);
 else if (node->type == BTRFS_EXTENT_OWNER_REF_KEY)
  ret = 0;
 else
  BUG();
 if (ret && insert_reserved)
  btrfs_pin_extent(trans, node->bytenr, node->num_bytes, 1);
 if (ret < 0)
  btrfs_err(trans->fs_info,
"failed to run delayed ref for logical %llu num_bytes %llu type %u action %u ref_mod %d: %d",
     node->bytenr, node->num_bytes, node->type,
     node->action, node->ref_mod, ret);
 return ret;
}

static struct btrfs_delayed_extent_op *cleanup_extent_op(
    struct btrfs_delayed_ref_head *head)
{
 struct btrfs_delayed_extent_op *extent_op = head->extent_op;

 if (!extent_op)
  return NULL;

 if (head->must_insert_reserved) {
  head->extent_op = NULL;
  btrfs_free_delayed_extent_op(extent_op);
  return NULL;
 }
 return extent_op;
}

static int run_and_cleanup_extent_op(struct btrfs_trans_handle *trans,
         struct btrfs_delayed_ref_head *head)
{
 struct btrfs_delayed_extent_op *extent_op;
 int ret;

 extent_op = cleanup_extent_op(head);
 if (!extent_op)
  return 0;
 head->extent_op = NULL;
 spin_unlock(&head->lock);
 ret = run_delayed_extent_op(trans, head, extent_op);
 btrfs_free_delayed_extent_op(extent_op);
 return ret ? ret : 1;
}

u64 btrfs_cleanup_ref_head_accounting(struct btrfs_fs_info *fs_info,
      struct btrfs_delayed_ref_root *delayed_refs,
      struct btrfs_delayed_ref_head *head)
{
 u64 ret = 0;

 /*
 * We had csum deletions accounted for in our delayed refs rsv, we need
 * to drop the csum leaves for this update from our delayed_refs_rsv.
 */
 if (head->total_ref_mod < 0 && head->is_data) {
  int nr_csums;

  spin_lock(&delayed_refs->lock);
  delayed_refs->pending_csums -= head->num_bytes;
  spin_unlock(&delayed_refs->lock);
  nr_csums = btrfs_csum_bytes_to_leaves(fs_info, head->num_bytes);

  btrfs_delayed_refs_rsv_release(fs_info, 0, nr_csums);

  ret = btrfs_calc_delayed_ref_csum_bytes(fs_info, nr_csums);
 }
 /* must_insert_reserved can be set only if we didn't run the head ref. */
 if (head->must_insert_reserved)
  free_head_ref_squota_rsv(fs_info, head);

 return ret;
}

static int cleanup_ref_head(struct btrfs_trans_handle *trans,
       struct btrfs_delayed_ref_head *head,
       u64 *bytes_released)
{

 struct btrfs_fs_info *fs_info = trans->fs_info;
 struct btrfs_delayed_ref_root *delayed_refs;
 int ret;

 delayed_refs = &trans->transaction->delayed_refs;

 ret = run_and_cleanup_extent_op(trans, head);
 if (ret < 0) {
  btrfs_unselect_ref_head(delayed_refs, head);
  btrfs_debug(fs_info, "run_delayed_extent_op returned %d", ret);
  return ret;
 } else if (ret) {
  return ret;
 }

 /*
 * Need to drop our head ref lock and re-acquire the delayed ref lock
 * and then re-check to make sure nobody got added.
 */
 spin_unlock(&head->lock);
 spin_lock(&delayed_refs->lock);
 spin_lock(&head->lock);
 if (!RB_EMPTY_ROOT(&head->ref_tree.rb_root) || head->extent_op) {
  spin_unlock(&head->lock);
  spin_unlock(&delayed_refs->lock);
  return 1;
 }
 btrfs_delete_ref_head(fs_info, delayed_refs, head);
 spin_unlock(&head->lock);
 spin_unlock(&delayed_refs->lock);

 if (head->must_insert_reserved) {
  btrfs_pin_extent(trans, head->bytenr, head->num_bytes, 1);
  if (head->is_data) {
   struct btrfs_root *csum_root;

   csum_root = btrfs_csum_root(fs_info, head->bytenr);
   ret = btrfs_del_csums(trans, csum_root, head->bytenr,
           head->num_bytes);
  }
 }

 *bytes_released += btrfs_cleanup_ref_head_accounting(fs_info, delayed_refs, head);

 trace_run_delayed_ref_head(fs_info, head, 0);
 btrfs_delayed_ref_unlock(head);
 btrfs_put_delayed_ref_head(head);
 return ret;
}

static int btrfs_run_delayed_refs_for_head(struct btrfs_trans_handle *trans,
        struct btrfs_delayed_ref_head *locked_ref,
        u64 *bytes_released)
{
 struct btrfs_fs_info *fs_info = trans->fs_info;
 struct btrfs_delayed_ref_root *delayed_refs;
 struct btrfs_delayed_extent_op *extent_op;
 struct btrfs_delayed_ref_node *ref;
 bool must_insert_reserved;
 int ret;

 delayed_refs = &trans->transaction->delayed_refs;

 lockdep_assert_held(&locked_ref->mutex);
 lockdep_assert_held(&locked_ref->lock);

 while ((ref = btrfs_select_delayed_ref(locked_ref))) {
  if (ref->seq &&
      btrfs_check_delayed_seq(fs_info, ref->seq)) {
   spin_unlock(&locked_ref->lock);
   btrfs_unselect_ref_head(delayed_refs, locked_ref);
   return -EAGAIN;
  }

  rb_erase_cached(&ref->ref_node, &locked_ref->ref_tree);
  RB_CLEAR_NODE(&ref->ref_node);
  if (!list_empty(&ref->add_list))
   list_del(&ref->add_list);
  /*
 * When we play the delayed ref, also correct the ref_mod on
 * head
 */
  switch (ref->action) {
  case BTRFS_ADD_DELAYED_REF:
  case BTRFS_ADD_DELAYED_EXTENT:
   locked_ref->ref_mod -= ref->ref_mod;
   break;
  case BTRFS_DROP_DELAYED_REF:
   locked_ref->ref_mod += ref->ref_mod;
   break;
  default:
   WARN_ON(1);
  }

  /*
 * Record the must_insert_reserved flag before we drop the
 * spin lock.
 */
  must_insert_reserved = locked_ref->must_insert_reserved;
  /*
 * Unsetting this on the head ref relinquishes ownership of
 * the rsv_bytes, so it is critical that every possible code
 * path from here forward frees all reserves including qgroup
 * reserve.
 */
  locked_ref->must_insert_reserved = false;

  extent_op = locked_ref->extent_op;
  locked_ref->extent_op = NULL;
  spin_unlock(&locked_ref->lock);

  ret = run_one_delayed_ref(trans, locked_ref, ref, extent_op,
       must_insert_reserved);
  btrfs_delayed_refs_rsv_release(fs_info, 1, 0);
  *bytes_released += btrfs_calc_delayed_ref_bytes(fs_info, 1);

  btrfs_free_delayed_extent_op(extent_op);
  if (ret) {
   btrfs_unselect_ref_head(delayed_refs, locked_ref);
   btrfs_put_delayed_ref(ref);
   return ret;
  }

  btrfs_put_delayed_ref(ref);
  cond_resched();

  spin_lock(&locked_ref->lock);
  btrfs_merge_delayed_refs(fs_info, delayed_refs, locked_ref);
 }

 return 0;
}

/*
 * Returns 0 on success or if called with an already aborted transaction.
 * Returns -ENOMEM or -EIO on failure and will abort the transaction.
 */
static noinline int __btrfs_run_delayed_refs(struct btrfs_trans_handle *trans,
          u64 min_bytes)
{
 struct btrfs_fs_info *fs_info = trans->fs_info;
 struct btrfs_delayed_ref_root *delayed_refs;
 struct btrfs_delayed_ref_head *locked_ref = NULL;
 int ret;
 unsigned long count = 0;
 unsigned long max_count = 0;
 u64 bytes_processed = 0;

 delayed_refs = &trans->transaction->delayed_refs;
 if (min_bytes == 0) {
  /*
 * We may be subject to a harmless race if some task is
 * concurrently adding or removing a delayed ref, so silence
 * KCSAN and similar tools.
 */
  max_count = data_race(delayed_refs->num_heads_ready);
  min_bytes = U64_MAX;
 }

 do {
  if (!locked_ref) {
   locked_ref = btrfs_select_ref_head(fs_info, delayed_refs);
   if (IS_ERR_OR_NULL(locked_ref)) {
    if (PTR_ERR(locked_ref) == -EAGAIN) {
     continue;
    } else {
     break;
    }
   }
   count++;
  }
  /*
 * We need to try and merge add/drops of the same ref since we
 * can run into issues with relocate dropping the implicit ref
 * and then it being added back again before the drop can
 * finish.  If we merged anything we need to re-loop so we can
 * get a good ref.
 * Or we can get node references of the same type that weren't
 * merged when created due to bumps in the tree mod seq, and
 * we need to merge them to prevent adding an inline extent
 * backref before dropping it (triggering a BUG_ON at
 * insert_inline_extent_backref()).
 */
  spin_lock(&locked_ref->lock);
  btrfs_merge_delayed_refs(fs_info, delayed_refs, locked_ref);

  ret = btrfs_run_delayed_refs_for_head(trans, locked_ref, &bytes_processed);
  if (ret < 0 && ret != -EAGAIN) {
   /*
 * Error, btrfs_run_delayed_refs_for_head already
 * unlocked everything so just bail out
 */
   return ret;
  } else if (!ret) {
   /*
 * Success, perform the usual cleanup of a processed
 * head
 */
   ret = cleanup_ref_head(trans, locked_ref, &bytes_processed);
   if (ret > 0 ) {
    /* We dropped our lock, we need to loop. */
    ret = 0;
    continue;
   } else if (ret) {
    return ret;
   }
  }

  /*
 * Either success case or btrfs_run_delayed_refs_for_head
 * returned -EAGAIN, meaning we need to select another head
 */

  locked_ref = NULL;
  cond_resched();
 } while ((min_bytes != U64_MAX && bytes_processed < min_bytes) ||
   (max_count > 0 && count < max_count) ||
   locked_ref);

 return 0;
}

#ifdef SCRAMBLE_DELAYED_REFS
/*
 * Normally delayed refs get processed in ascending bytenr order. This
 * correlates in most cases to the order added. To expose dependencies on this
 * order, we start to process the tree in the middle instead of the beginning
 */
static u64 find_middle(struct rb_root *root)
{
 struct rb_node *n = root->rb_node;
 struct btrfs_delayed_ref_node *entry;
 int alt = 1;
 u64 middle;
 u64 first = 0, last = 0;

 n = rb_first(root);
 if (n) {
  entry = rb_entry(n, struct btrfs_delayed_ref_node, rb_node);
  first = entry->bytenr;
 }
 n = rb_last(root);
 if (n) {
  entry = rb_entry(n, struct btrfs_delayed_ref_node, rb_node);
  last = entry->bytenr;
 }
 n = root->rb_node;

 while (n) {
  entry = rb_entry(n, struct btrfs_delayed_ref_node, rb_node);
  WARN_ON(!entry->in_tree);

  middle = entry->bytenr;

  if (alt)
   n = n->rb_left;
  else
   n = n->rb_right;

  alt = 1 - alt;
 }
 return middle;
}
#endif

/*
 * Start processing the delayed reference count updates and extent insertions
 * we have queued up so far.
 *
 * @trans: Transaction handle.
 * @min_bytes: How many bytes of delayed references to process. After this
 * many bytes we stop processing delayed references if there are
 * any more. If 0 it means to run all existing delayed references,
 * but not new ones added after running all existing ones.
 * Use (u64)-1 (U64_MAX) to run all existing delayed references
 * plus any new ones that are added.
 *
 * Returns 0 on success or if called with an aborted transaction
 * Returns <0 on error and aborts the transaction
 */
int btrfs_run_delayed_refs(struct btrfs_trans_handle *trans, u64 min_bytes)
{
 struct btrfs_fs_info *fs_info = trans->fs_info;
 struct btrfs_delayed_ref_root *delayed_refs;
 int ret;

 /* We'll clean this up in btrfs_cleanup_transaction */
 if (TRANS_ABORTED(trans))
  return 0;

 if (test_bit(BTRFS_FS_CREATING_FREE_SPACE_TREE, &fs_info->flags))
  return 0;

 delayed_refs = &trans->transaction->delayed_refs;
again:
#ifdef SCRAMBLE_DELAYED_REFS
 delayed_refs->run_delayed_start = find_middle(&delayed_refs->root);
#endif
 ret = __btrfs_run_delayed_refs(trans, min_bytes);
 if (ret < 0) {
  btrfs_abort_transaction(trans, ret);
  return ret;
 }

 if (min_bytes == U64_MAX) {
  btrfs_create_pending_block_groups(trans);

  spin_lock(&delayed_refs->lock);
  if (xa_empty(&delayed_refs->head_refs)) {
   spin_unlock(&delayed_refs->lock);
   return 0;
  }
  spin_unlock(&delayed_refs->lock);

  cond_resched();
  goto again;
 }

 return 0;
}

int btrfs_set_disk_extent_flags(struct btrfs_trans_handle *trans,
    struct extent_buffer *eb, u64 flags)
{
 struct btrfs_delayed_extent_op *extent_op;
 int ret;

 extent_op = btrfs_alloc_delayed_extent_op();
 if (!extent_op)
  return -ENOMEM;

 extent_op->flags_to_set = flags;
 extent_op->update_flags = true;
 extent_op->update_key = false;

 ret = btrfs_add_delayed_extent_op(trans, eb->start, eb->len,
       btrfs_header_level(eb), extent_op);
 if (ret)
  btrfs_free_delayed_extent_op(extent_op);
 return ret;
}

static noinline int check_delayed_ref(struct btrfs_inode *inode,
          struct btrfs_path *path,
          u64 offset, u64 bytenr)
{
 struct btrfs_root *root = inode->root;
 struct btrfs_delayed_ref_head *head;
 struct btrfs_delayed_ref_node *ref;
 struct btrfs_delayed_ref_root *delayed_refs;
 struct btrfs_transaction *cur_trans;
 struct rb_node *node;
 int ret = 0;

 spin_lock(&root->fs_info->trans_lock);
 cur_trans = root->fs_info->running_transaction;
 if (cur_trans)
  refcount_inc(&cur_trans->use_count);
 spin_unlock(&root->fs_info->trans_lock);
 if (!cur_trans)
  return 0;

 delayed_refs = &cur_trans->delayed_refs;
 spin_lock(&delayed_refs->lock);
 head = btrfs_find_delayed_ref_head(root->fs_info, delayed_refs, bytenr);
 if (!head) {
  spin_unlock(&delayed_refs->lock);
  btrfs_put_transaction(cur_trans);
  return 0;
 }

 if (!mutex_trylock(&head->mutex)) {
  if (path->nowait) {
   spin_unlock(&delayed_refs->lock);
   btrfs_put_transaction(cur_trans);
   return -EAGAIN;
  }

  refcount_inc(&head->refs);
  spin_unlock(&delayed_refs->lock);

  btrfs_release_path(path);

  /*
 * Mutex was contended, block until it's released and let
 * caller try again
 */
  mutex_lock(&head->mutex);
  mutex_unlock(&head->mutex);
  btrfs_put_delayed_ref_head(head);
  btrfs_put_transaction(cur_trans);
  return -EAGAIN;
 }
 spin_unlock(&delayed_refs->lock);

 spin_lock(&head->lock);
 /*
 * XXX: We should replace this with a proper search function in the
 * future.
 */
 for (node = rb_first_cached(&head->ref_tree); node;
      node = rb_next(node)) {
  u64 ref_owner;
  u64 ref_offset;

  ref = rb_entry(node, struct btrfs_delayed_ref_node, ref_node);
  /* If it's a shared ref we know a cross reference exists */
  if (ref->type != BTRFS_EXTENT_DATA_REF_KEY) {
   ret = 1;
   break;
  }

  ref_owner = btrfs_delayed_ref_owner(ref);
  ref_offset = btrfs_delayed_ref_offset(ref);

  /*
 * If our ref doesn't match the one we're currently looking at
 * then we have a cross reference.
 */
  if (ref->ref_root != btrfs_root_id(root) ||
      ref_owner != btrfs_ino(inode) || ref_offset != offset) {
   ret = 1;
   break;
  }
 }
 spin_unlock(&head->lock);
 mutex_unlock(&head->mutex);
 btrfs_put_transaction(cur_trans);
 return ret;
}

/*
 * Check if there are references for a data extent other than the one belonging
 * to the given inode and offset.
 *
 * @inode:     The only inode we expect to find associated with the data extent.
 * @path:      A path to use for searching the extent tree.
 * @offset:    The only offset we expect to find associated with the data extent.
 * @bytenr:    The logical address of the data extent.
 *
 * When the extent does not have any other references other than the one we
 * expect to find, we always return a value of 0 with the path having a locked
 * leaf that contains the extent's extent item - this is necessary to ensure
 * we don't race with a task running delayed references, and our caller must
 * have such a path when calling check_delayed_ref() - it must lock a delayed
 * ref head while holding the leaf locked. In case the extent item is not found
 * in the extent tree, we return -ENOENT with the path having the leaf (locked)
 * where the extent item should be, in order to prevent races with another task
 * running delayed references, so that we don't miss any reference when calling
 * check_delayed_ref().
 *
 * Note: this may return false positives, and this is because we want to be
 *       quick here as we're called in write paths (when flushing delalloc and
 *       in the direct IO write path). For example we can have an extent with
 *       a single reference but that reference is not inlined, or we may have
 *       many references in the extent tree but we also have delayed references
 *       that cancel all the reference except the one for our inode and offset,
 *       but it would be expensive to do such checks and complex due to all
 *       locking to avoid races between the checks and flushing delayed refs,
--> --------------------

--> maximum size reached

--> --------------------