"Fossies" - the Fresh Open Source Software Archive

Member "btrfs-progs-v5.4.1/extent-tree.c" (9 Jan 2020, 103947 Bytes) of package /linux/misc/btrfs-progs-v5.4.1.tar.xz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. For more information about "extent-tree.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: v5.4_vs_v5.4.1.

    1 /*
    2  * Copyright (C) 2007 Oracle.  All rights reserved.
    3  *
    4  * This program is free software; you can redistribute it and/or
    5  * modify it under the terms of the GNU General Public
    6  * License v2 as published by the Free Software Foundation.
    7  *
    8  * This program is distributed in the hope that it will be useful,
    9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
   10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   11  * General Public License for more details.
   12  *
   13  * You should have received a copy of the GNU General Public
   14  * License along with this program; if not, write to the
   15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   16  * Boston, MA 021110-1307, USA.
   17  */
   18 
   19 #include <stdio.h>
   20 #include <stdlib.h>
   21 #include <stdint.h>
   22 #include <math.h>
   23 #include "kerncompat.h"
   24 #include "kernel-lib/radix-tree.h"
   25 #include "ctree.h"
   26 #include "disk-io.h"
   27 #include "print-tree.h"
   28 #include "transaction.h"
   29 #include "crypto/crc32c.h"
   30 #include "volumes.h"
   31 #include "free-space-cache.h"
   32 #include "free-space-tree.h"
   33 #include "common/utils.h"
   34 
   35 #define PENDING_EXTENT_INSERT 0
   36 #define PENDING_EXTENT_DELETE 1
   37 #define PENDING_BACKREF_UPDATE 2
   38 
   39 struct pending_extent_op {
   40     int type;
   41     u64 bytenr;
   42     u64 num_bytes;
   43     u64 flags;
   44     struct btrfs_disk_key key;
   45     int level;
   46 };
   47 
   48 static int __free_extent(struct btrfs_trans_handle *trans,
   49              u64 bytenr, u64 num_bytes, u64 parent,
   50              u64 root_objectid, u64 owner_objectid,
   51              u64 owner_offset, int refs_to_drop);
   52 static struct btrfs_block_group_cache *
   53 btrfs_find_block_group(struct btrfs_root *root, struct btrfs_block_group_cache
   54                *hint, u64 search_start, int data, int owner);
   55 
   56 static int remove_sb_from_cache(struct btrfs_root *root,
   57                 struct btrfs_block_group_cache *cache)
   58 {
   59     u64 bytenr;
   60     u64 *logical;
   61     int stripe_len;
   62     int i, nr, ret;
   63     struct btrfs_fs_info *fs_info = root->fs_info;
   64     struct extent_io_tree *free_space_cache;
   65 
   66     free_space_cache = &fs_info->free_space_cache;
   67     for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
   68         bytenr = btrfs_sb_offset(i);
   69         ret = btrfs_rmap_block(fs_info, cache->key.objectid, bytenr,
   70                        &logical, &nr, &stripe_len);
   71         BUG_ON(ret);
   72         while (nr--) {
   73             clear_extent_dirty(free_space_cache, logical[nr],
   74                 logical[nr] + stripe_len - 1);
   75         }
   76         kfree(logical);
   77     }
   78     return 0;
   79 }
   80 
   81 static int cache_block_group(struct btrfs_root *root,
   82                  struct btrfs_block_group_cache *block_group)
   83 {
   84     struct btrfs_path *path;
   85     int ret;
   86     struct btrfs_key key;
   87     struct extent_buffer *leaf;
   88     struct extent_io_tree *free_space_cache;
   89     int slot;
   90     u64 last;
   91     u64 hole_size;
   92 
   93     if (!block_group)
   94         return 0;
   95 
   96     root = root->fs_info->extent_root;
   97     free_space_cache = &root->fs_info->free_space_cache;
   98 
   99     if (block_group->cached)
  100         return 0;
  101 
  102     path = btrfs_alloc_path();
  103     if (!path)
  104         return -ENOMEM;
  105 
  106     path->reada = READA_FORWARD;
  107     last = max_t(u64, block_group->key.objectid, BTRFS_SUPER_INFO_OFFSET);
  108     key.objectid = last;
  109     key.offset = 0;
  110     key.type = 0;
  111 
  112     ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
  113     if (ret < 0)
  114         goto err;
  115 
  116     while(1) {
  117         leaf = path->nodes[0];
  118         slot = path->slots[0];
  119         if (slot >= btrfs_header_nritems(leaf)) {
  120             ret = btrfs_next_leaf(root, path);
  121             if (ret < 0)
  122                 goto err;
  123             if (ret == 0) {
  124                 continue;
  125             } else {
  126                 break;
  127             }
  128         }
  129         btrfs_item_key_to_cpu(leaf, &key, slot);
  130         if (key.objectid < block_group->key.objectid) {
  131             goto next;
  132         }
  133         if (key.objectid >= block_group->key.objectid +
  134             block_group->key.offset) {
  135             break;
  136         }
  137 
  138         if (key.type == BTRFS_EXTENT_ITEM_KEY ||
  139             key.type == BTRFS_METADATA_ITEM_KEY) {
  140             if (key.objectid > last) {
  141                 hole_size = key.objectid - last;
  142                 set_extent_dirty(free_space_cache, last,
  143                          last + hole_size - 1);
  144             }
  145             if (key.type == BTRFS_METADATA_ITEM_KEY)
  146                 last = key.objectid + root->fs_info->nodesize;
  147             else
  148                 last = key.objectid + key.offset;
  149         }
  150 next:
  151         path->slots[0]++;
  152     }
  153 
  154     if (block_group->key.objectid +
  155         block_group->key.offset > last) {
  156         hole_size = block_group->key.objectid +
  157             block_group->key.offset - last;
  158         set_extent_dirty(free_space_cache, last, last + hole_size - 1);
  159     }
  160     remove_sb_from_cache(root, block_group);
  161     block_group->cached = 1;
  162 err:
  163     btrfs_free_path(path);
  164     return 0;
  165 }
  166 
  167 /*
  168  * Return the block group that contains @bytenr, otherwise return the next one
  169  * that starts after @bytenr
  170  */
  171 struct btrfs_block_group_cache *btrfs_lookup_first_block_group(struct
  172                                btrfs_fs_info *info,
  173                                u64 bytenr)
  174 {
  175     struct extent_io_tree *block_group_cache;
  176     struct btrfs_block_group_cache *block_group = NULL;
  177     u64 ptr;
  178     u64 start;
  179     u64 end;
  180     int ret;
  181 
  182     bytenr = max_t(u64, bytenr,
  183                BTRFS_SUPER_INFO_OFFSET + BTRFS_SUPER_INFO_SIZE);
  184     block_group_cache = &info->block_group_cache;
  185     ret = find_first_extent_bit(block_group_cache,
  186                     bytenr, &start, &end,
  187                     BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA |
  188                     BLOCK_GROUP_SYSTEM);
  189     if (ret) {
  190         return NULL;
  191     }
  192     ret = get_state_private(block_group_cache, start, &ptr);
  193     if (ret)
  194         return NULL;
  195 
  196     block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
  197     return block_group;
  198 }
  199 
  200 /*
  201  * Return the block group that contains the given @bytenr
  202  */
  203 struct btrfs_block_group_cache *btrfs_lookup_block_group(struct
  204                              btrfs_fs_info *info,
  205                              u64 bytenr)
  206 {
  207     struct extent_io_tree *block_group_cache;
  208     struct btrfs_block_group_cache *block_group = NULL;
  209     u64 ptr;
  210     u64 start;
  211     u64 end;
  212     int ret;
  213 
  214     block_group_cache = &info->block_group_cache;
  215     ret = find_first_extent_bit(block_group_cache,
  216                     bytenr, &start, &end,
  217                     BLOCK_GROUP_DATA | BLOCK_GROUP_METADATA |
  218                     BLOCK_GROUP_SYSTEM);
  219     if (ret) {
  220         return NULL;
  221     }
  222     ret = get_state_private(block_group_cache, start, &ptr);
  223     if (ret)
  224         return NULL;
  225 
  226     block_group = (struct btrfs_block_group_cache *)(unsigned long)ptr;
  227     if (block_group->key.objectid <= bytenr && bytenr <
  228         block_group->key.objectid + block_group->key.offset)
  229         return block_group;
  230     return NULL;
  231 }
  232 
  233 static int block_group_bits(struct btrfs_block_group_cache *cache, u64 bits)
  234 {
  235     return (cache->flags & bits) == bits;
  236 }
  237 
  238 static int noinline find_search_start(struct btrfs_root *root,
  239                   struct btrfs_block_group_cache **cache_ret,
  240                   u64 *start_ret, int num, int data)
  241 {
  242     int ret;
  243     struct btrfs_block_group_cache *cache = *cache_ret;
  244     u64 last = *start_ret;
  245     u64 start = 0;
  246     u64 end = 0;
  247     u64 search_start = *start_ret;
  248     int wrapped = 0;
  249 
  250     if (!cache)
  251         goto out;
  252 again:
  253     ret = cache_block_group(root, cache);
  254     if (ret)
  255         goto out;
  256 
  257     last = max(search_start, cache->key.objectid);
  258     if (cache->ro || !block_group_bits(cache, data))
  259         goto new_group;
  260 
  261     while(1) {
  262         ret = find_first_extent_bit(&root->fs_info->free_space_cache,
  263                         last, &start, &end, EXTENT_DIRTY);
  264         if (ret) {
  265             goto new_group;
  266         }
  267 
  268         start = max(last, start);
  269         last = end + 1;
  270         if (last - start < num) {
  271             continue;
  272         }
  273         if (start + num > cache->key.objectid + cache->key.offset) {
  274             goto new_group;
  275         }
  276         *start_ret = start;
  277         return 0;
  278     }
  279 out:
  280     *start_ret = last;
  281     cache = btrfs_lookup_block_group(root->fs_info, search_start);
  282     if (!cache) {
  283         printk("Unable to find block group for %llu\n",
  284             (unsigned long long)search_start);
  285         return -ENOENT;
  286     }
  287     return -ENOSPC;
  288 
  289 new_group:
  290     last = cache->key.objectid + cache->key.offset;
  291 wrapped:
  292     cache = btrfs_lookup_first_block_group(root->fs_info, last);
  293     if (!cache) {
  294         if (!wrapped) {
  295             wrapped = 1;
  296             last = search_start;
  297             goto wrapped;
  298         }
  299         goto out;
  300     }
  301     *cache_ret = cache;
  302     goto again;
  303 }
  304 
  305 static int block_group_state_bits(u64 flags)
  306 {
  307     int bits = 0;
  308     if (flags & BTRFS_BLOCK_GROUP_DATA)
  309         bits |= BLOCK_GROUP_DATA;
  310     if (flags & BTRFS_BLOCK_GROUP_METADATA)
  311         bits |= BLOCK_GROUP_METADATA;
  312     if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
  313         bits |= BLOCK_GROUP_SYSTEM;
  314     return bits;
  315 }
  316 
  317 static struct btrfs_block_group_cache *
  318 btrfs_find_block_group(struct btrfs_root *root, struct btrfs_block_group_cache
  319                *hint, u64 search_start, int data, int owner)
  320 {
  321     struct btrfs_block_group_cache *cache;
  322     struct extent_io_tree *block_group_cache;
  323     struct btrfs_block_group_cache *found_group = NULL;
  324     struct btrfs_fs_info *info = root->fs_info;
  325     u64 used;
  326     u64 last = 0;
  327     u64 hint_last;
  328     u64 start;
  329     u64 end;
  330     u64 free_check;
  331     u64 ptr;
  332     int bit;
  333     int ret;
  334     int full_search = 0;
  335     int factor = 10;
  336 
  337     block_group_cache = &info->block_group_cache;
  338 
  339     if (!owner)
  340         factor = 10;
  341 
  342     bit = block_group_state_bits(data);
  343 
  344     if (search_start) {
  345         struct btrfs_block_group_cache *shint;
  346         shint = btrfs_lookup_block_group(info, search_start);
  347         if (shint && !shint->ro && block_group_bits(shint, data)) {
  348             used = shint->used;
  349             if (used + shint->pinned <
  350                 div_factor(shint->key.offset, factor)) {
  351                 return shint;
  352             }
  353         }
  354     }
  355     if (hint && !hint->ro && block_group_bits(hint, data)) {
  356         used = hint->used;
  357         if (used + hint->pinned <
  358             div_factor(hint->key.offset, factor)) {
  359             return hint;
  360         }
  361         last = hint->key.objectid + hint->key.offset;
  362         hint_last = last;
  363     } else {
  364         if (hint)
  365             hint_last = max(hint->key.objectid, search_start);
  366         else
  367             hint_last = search_start;
  368 
  369         last = hint_last;
  370     }
  371 again:
  372     while(1) {
  373         ret = find_first_extent_bit(block_group_cache, last,
  374                         &start, &end, bit);
  375         if (ret)
  376             break;
  377 
  378         ret = get_state_private(block_group_cache, start, &ptr);
  379         if (ret)
  380             break;
  381 
  382         cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
  383         last = cache->key.objectid + cache->key.offset;
  384         used = cache->used;
  385 
  386         if (!cache->ro && block_group_bits(cache, data)) {
  387             if (full_search)
  388                 free_check = cache->key.offset;
  389             else
  390                 free_check = div_factor(cache->key.offset,
  391                             factor);
  392 
  393             if (used + cache->pinned < free_check) {
  394                 found_group = cache;
  395                 goto found;
  396             }
  397         }
  398         cond_resched();
  399     }
  400     if (!full_search) {
  401         last = search_start;
  402         full_search = 1;
  403         goto again;
  404     }
  405 found:
  406     return found_group;
  407 }
  408 
  409 /*
  410  * Back reference rules.  Back refs have three main goals:
  411  *
  412  * 1) differentiate between all holders of references to an extent so that
  413  *    when a reference is dropped we can make sure it was a valid reference
  414  *    before freeing the extent.
  415  *
  416  * 2) Provide enough information to quickly find the holders of an extent
  417  *    if we notice a given block is corrupted or bad.
  418  *
  419  * 3) Make it easy to migrate blocks for FS shrinking or storage pool
  420  *    maintenance.  This is actually the same as #2, but with a slightly
  421  *    different use case.
  422  *
  423  * There are two kinds of back refs. The implicit back refs is optimized
  424  * for pointers in non-shared tree blocks. For a given pointer in a block,
  425  * back refs of this kind provide information about the block's owner tree
  426  * and the pointer's key. These information allow us to find the block by
  427  * b-tree searching. The full back refs is for pointers in tree blocks not
  428  * referenced by their owner trees. The location of tree block is recorded
  429  * in the back refs. Actually the full back refs is generic, and can be
  430  * used in all cases the implicit back refs is used. The major shortcoming
  431  * of the full back refs is its overhead. Every time a tree block gets
  432  * COWed, we have to update back refs entry for all pointers in it.
  433  *
  434  * For a newly allocated tree block, we use implicit back refs for
  435  * pointers in it. This means most tree related operations only involve
  436  * implicit back refs. For a tree block created in old transaction, the
  437  * only way to drop a reference to it is COW it. So we can detect the
  438  * event that tree block loses its owner tree's reference and do the
  439  * back refs conversion.
  440  *
  441  * When a tree block is COW'd through a tree, there are four cases:
  442  *
  443  * The reference count of the block is one and the tree is the block's
  444  * owner tree. Nothing to do in this case.
  445  *
  446  * The reference count of the block is one and the tree is not the
  447  * block's owner tree. In this case, full back refs is used for pointers
  448  * in the block. Remove these full back refs, add implicit back refs for
  449  * every pointers in the new block.
  450  *
  451  * The reference count of the block is greater than one and the tree is
  452  * the block's owner tree. In this case, implicit back refs is used for
  453  * pointers in the block. Add full back refs for every pointers in the
  454  * block, increase lower level extents' reference counts. The original
  455  * implicit back refs are entailed to the new block.
  456  *
  457  * The reference count of the block is greater than one and the tree is
  458  * not the block's owner tree. Add implicit back refs for every pointer in
  459  * the new block, increase lower level extents' reference count.
  460  *
  461  * Back Reference Key composing:
  462  *
  463  * The key objectid corresponds to the first byte in the extent,
  464  * The key type is used to differentiate between types of back refs.
  465  * There are different meanings of the key offset for different types
  466  * of back refs.
  467  *
  468  * File extents can be referenced by:
  469  *
  470  * - multiple snapshots, subvolumes, or different generations in one subvol
  471  * - different files inside a single subvolume
  472  * - different offsets inside a file (bookend extents in file.c)
  473  *
  474  * The extent ref structure for the implicit back refs has fields for:
  475  *
  476  * - Objectid of the subvolume root
  477  * - objectid of the file holding the reference
  478  * - original offset in the file
  479  * - how many bookend extents
  480  *
  481  * The key offset for the implicit back refs is hash of the first
  482  * three fields.
  483  *
  484  * The extent ref structure for the full back refs has field for:
  485  *
  486  * - number of pointers in the tree leaf
  487  *
  488  * The key offset for the implicit back refs is the first byte of
  489  * the tree leaf
  490  *
  491  * When a file extent is allocated, The implicit back refs is used.
  492  * the fields are filled in:
  493  *
  494  *     (root_key.objectid, inode objectid, offset in file, 1)
  495  *
  496  * When a file extent is removed file truncation, we find the
  497  * corresponding implicit back refs and check the following fields:
  498  *
  499  *     (btrfs_header_owner(leaf), inode objectid, offset in file)
  500  *
  501  * Btree extents can be referenced by:
  502  *
  503  * - Different subvolumes
  504  *
  505  * Both the implicit back refs and the full back refs for tree blocks
  506  * only consist of key. The key offset for the implicit back refs is
  507  * objectid of block's owner tree. The key offset for the full back refs
  508  * is the first byte of parent block.
  509  *
  510  * When implicit back refs is used, information about the lowest key and
  511  * level of the tree block are required. These information are stored in
  512  * tree block info structure.
  513  */
  514 
  515 u64 hash_extent_data_ref(u64 root_objectid, u64 owner, u64 offset)
  516 {
  517     u32 high_crc = ~(u32)0;
  518     u32 low_crc = ~(u32)0;
  519     __le64 lenum;
  520 
  521     lenum = cpu_to_le64(root_objectid);
  522     high_crc = btrfs_crc32c(high_crc, &lenum, sizeof(lenum));
  523     lenum = cpu_to_le64(owner);
  524     low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
  525     lenum = cpu_to_le64(offset);
  526     low_crc = btrfs_crc32c(low_crc, &lenum, sizeof(lenum));
  527 
  528     return ((u64)high_crc << 31) ^ (u64)low_crc;
  529 }
  530 
  531 static u64 hash_extent_data_ref_item(struct extent_buffer *leaf,
  532                      struct btrfs_extent_data_ref *ref)
  533 {
  534     return hash_extent_data_ref(btrfs_extent_data_ref_root(leaf, ref),
  535                     btrfs_extent_data_ref_objectid(leaf, ref),
  536                     btrfs_extent_data_ref_offset(leaf, ref));
  537 }
  538 
  539 static int match_extent_data_ref(struct extent_buffer *leaf,
  540                  struct btrfs_extent_data_ref *ref,
  541                  u64 root_objectid, u64 owner, u64 offset)
  542 {
  543     if (btrfs_extent_data_ref_root(leaf, ref) != root_objectid ||
  544         btrfs_extent_data_ref_objectid(leaf, ref) != owner ||
  545         btrfs_extent_data_ref_offset(leaf, ref) != offset)
  546         return 0;
  547     return 1;
  548 }
  549 
  550 static noinline int lookup_extent_data_ref(struct btrfs_trans_handle *trans,
  551                        struct btrfs_root *root,
  552                        struct btrfs_path *path,
  553                        u64 bytenr, u64 parent,
  554                        u64 root_objectid,
  555                        u64 owner, u64 offset)
  556 {
  557     struct btrfs_key key;
  558     struct btrfs_extent_data_ref *ref;
  559     struct extent_buffer *leaf;
  560     u32 nritems;
  561     int ret;
  562     int recow;
  563     int err = -ENOENT;
  564 
  565     key.objectid = bytenr;
  566     if (parent) {
  567         key.type = BTRFS_SHARED_DATA_REF_KEY;
  568         key.offset = parent;
  569     } else {
  570         key.type = BTRFS_EXTENT_DATA_REF_KEY;
  571         key.offset = hash_extent_data_ref(root_objectid,
  572                           owner, offset);
  573     }
  574 again:
  575     recow = 0;
  576     ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
  577     if (ret < 0) {
  578         err = ret;
  579         goto fail;
  580     }
  581 
  582     if (parent) {
  583         if (!ret)
  584             return 0;
  585         goto fail;
  586     }
  587 
  588     leaf = path->nodes[0];
  589     nritems = btrfs_header_nritems(leaf);
  590     while (1) {
  591         if (path->slots[0] >= nritems) {
  592             ret = btrfs_next_leaf(root, path);
  593             if (ret < 0)
  594                 err = ret;
  595             if (ret)
  596                 goto fail;
  597 
  598             leaf = path->nodes[0];
  599             nritems = btrfs_header_nritems(leaf);
  600             recow = 1;
  601         }
  602 
  603         btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
  604         if (key.objectid != bytenr ||
  605             key.type != BTRFS_EXTENT_DATA_REF_KEY)
  606             goto fail;
  607 
  608         ref = btrfs_item_ptr(leaf, path->slots[0],
  609                      struct btrfs_extent_data_ref);
  610 
  611         if (match_extent_data_ref(leaf, ref, root_objectid,
  612                       owner, offset)) {
  613             if (recow) {
  614                 btrfs_release_path(path);
  615                 goto again;
  616             }
  617             err = 0;
  618             break;
  619         }
  620         path->slots[0]++;
  621     }
  622 fail:
  623     return err;
  624 }
  625 
  626 static noinline int insert_extent_data_ref(struct btrfs_trans_handle *trans,
  627                        struct btrfs_root *root,
  628                        struct btrfs_path *path,
  629                        u64 bytenr, u64 parent,
  630                        u64 root_objectid, u64 owner,
  631                        u64 offset, int refs_to_add)
  632 {
  633     struct btrfs_key key;
  634     struct extent_buffer *leaf;
  635     u32 size;
  636     u32 num_refs;
  637     int ret;
  638 
  639     key.objectid = bytenr;
  640     if (parent) {
  641         key.type = BTRFS_SHARED_DATA_REF_KEY;
  642         key.offset = parent;
  643         size = sizeof(struct btrfs_shared_data_ref);
  644     } else {
  645         key.type = BTRFS_EXTENT_DATA_REF_KEY;
  646         key.offset = hash_extent_data_ref(root_objectid,
  647                           owner, offset);
  648         size = sizeof(struct btrfs_extent_data_ref);
  649     }
  650 
  651     ret = btrfs_insert_empty_item(trans, root, path, &key, size);
  652     if (ret && ret != -EEXIST)
  653         goto fail;
  654 
  655     leaf = path->nodes[0];
  656     if (parent) {
  657         struct btrfs_shared_data_ref *ref;
  658         ref = btrfs_item_ptr(leaf, path->slots[0],
  659                      struct btrfs_shared_data_ref);
  660         if (ret == 0) {
  661             btrfs_set_shared_data_ref_count(leaf, ref, refs_to_add);
  662         } else {
  663             num_refs = btrfs_shared_data_ref_count(leaf, ref);
  664             num_refs += refs_to_add;
  665             btrfs_set_shared_data_ref_count(leaf, ref, num_refs);
  666         }
  667     } else {
  668         struct btrfs_extent_data_ref *ref;
  669         while (ret == -EEXIST) {
  670             ref = btrfs_item_ptr(leaf, path->slots[0],
  671                          struct btrfs_extent_data_ref);
  672             if (match_extent_data_ref(leaf, ref, root_objectid,
  673                           owner, offset))
  674                 break;
  675             btrfs_release_path(path);
  676 
  677             key.offset++;
  678             ret = btrfs_insert_empty_item(trans, root, path, &key,
  679                               size);
  680             if (ret && ret != -EEXIST)
  681                 goto fail;
  682 
  683             leaf = path->nodes[0];
  684         }
  685         ref = btrfs_item_ptr(leaf, path->slots[0],
  686                      struct btrfs_extent_data_ref);
  687         if (ret == 0) {
  688             btrfs_set_extent_data_ref_root(leaf, ref,
  689                                root_objectid);
  690             btrfs_set_extent_data_ref_objectid(leaf, ref, owner);
  691             btrfs_set_extent_data_ref_offset(leaf, ref, offset);
  692             btrfs_set_extent_data_ref_count(leaf, ref, refs_to_add);
  693         } else {
  694             num_refs = btrfs_extent_data_ref_count(leaf, ref);
  695             num_refs += refs_to_add;
  696             btrfs_set_extent_data_ref_count(leaf, ref, num_refs);
  697         }
  698     }
  699     btrfs_mark_buffer_dirty(leaf);
  700     ret = 0;
  701 fail:
  702     btrfs_release_path(path);
  703     return ret;
  704 }
  705 
  706 static noinline int remove_extent_data_ref(struct btrfs_trans_handle *trans,
  707                        struct btrfs_root *root,
  708                        struct btrfs_path *path,
  709                        int refs_to_drop)
  710 {
  711     struct btrfs_key key;
  712     struct btrfs_extent_data_ref *ref1 = NULL;
  713     struct btrfs_shared_data_ref *ref2 = NULL;
  714     struct extent_buffer *leaf;
  715     u32 num_refs = 0;
  716     int ret = 0;
  717 
  718     leaf = path->nodes[0];
  719     btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
  720 
  721     if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
  722         ref1 = btrfs_item_ptr(leaf, path->slots[0],
  723                       struct btrfs_extent_data_ref);
  724         num_refs = btrfs_extent_data_ref_count(leaf, ref1);
  725     } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
  726         ref2 = btrfs_item_ptr(leaf, path->slots[0],
  727                       struct btrfs_shared_data_ref);
  728         num_refs = btrfs_shared_data_ref_count(leaf, ref2);
  729     } else {
  730         BUG();
  731     }
  732 
  733     BUG_ON(num_refs < refs_to_drop);
  734     num_refs -= refs_to_drop;
  735 
  736     if (num_refs == 0) {
  737         ret = btrfs_del_item(trans, root, path);
  738     } else {
  739         if (key.type == BTRFS_EXTENT_DATA_REF_KEY)
  740             btrfs_set_extent_data_ref_count(leaf, ref1, num_refs);
  741         else if (key.type == BTRFS_SHARED_DATA_REF_KEY)
  742             btrfs_set_shared_data_ref_count(leaf, ref2, num_refs);
  743         btrfs_mark_buffer_dirty(leaf);
  744     }
  745     return ret;
  746 }
  747 
  748 static noinline u32 extent_data_ref_count(struct btrfs_path *path,
  749                       struct btrfs_extent_inline_ref *iref)
  750 {
  751     struct btrfs_key key;
  752     struct extent_buffer *leaf;
  753     struct btrfs_extent_data_ref *ref1;
  754     struct btrfs_shared_data_ref *ref2;
  755     u32 num_refs = 0;
  756 
  757     leaf = path->nodes[0];
  758     btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
  759     if (iref) {
  760         if (btrfs_extent_inline_ref_type(leaf, iref) ==
  761             BTRFS_EXTENT_DATA_REF_KEY) {
  762             ref1 = (struct btrfs_extent_data_ref *)(&iref->offset);
  763             num_refs = btrfs_extent_data_ref_count(leaf, ref1);
  764         } else {
  765             ref2 = (struct btrfs_shared_data_ref *)(iref + 1);
  766             num_refs = btrfs_shared_data_ref_count(leaf, ref2);
  767         }
  768     } else if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
  769         ref1 = btrfs_item_ptr(leaf, path->slots[0],
  770                       struct btrfs_extent_data_ref);
  771         num_refs = btrfs_extent_data_ref_count(leaf, ref1);
  772     } else if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
  773         ref2 = btrfs_item_ptr(leaf, path->slots[0],
  774                       struct btrfs_shared_data_ref);
  775         num_refs = btrfs_shared_data_ref_count(leaf, ref2);
  776     } else {
  777         BUG();
  778     }
  779     return num_refs;
  780 }
  781 
  782 static noinline int lookup_tree_block_ref(struct btrfs_trans_handle *trans,
  783                       struct btrfs_root *root,
  784                       struct btrfs_path *path,
  785                       u64 bytenr, u64 parent,
  786                       u64 root_objectid)
  787 {
  788     struct btrfs_key key;
  789     int ret;
  790 
  791     key.objectid = bytenr;
  792     if (parent) {
  793         key.type = BTRFS_SHARED_BLOCK_REF_KEY;
  794         key.offset = parent;
  795     } else {
  796         key.type = BTRFS_TREE_BLOCK_REF_KEY;
  797         key.offset = root_objectid;
  798     }
  799 
  800     ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
  801     if (ret > 0)
  802         ret = -ENOENT;
  803     return ret;
  804 }
  805 
  806 static noinline int insert_tree_block_ref(struct btrfs_trans_handle *trans,
  807                       struct btrfs_root *root,
  808                       struct btrfs_path *path,
  809                       u64 bytenr, u64 parent,
  810                       u64 root_objectid)
  811 {
  812     struct btrfs_key key;
  813     int ret;
  814 
  815     key.objectid = bytenr;
  816     if (parent) {
  817         key.type = BTRFS_SHARED_BLOCK_REF_KEY;
  818         key.offset = parent;
  819     } else {
  820         key.type = BTRFS_TREE_BLOCK_REF_KEY;
  821         key.offset = root_objectid;
  822     }
  823 
  824     ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
  825 
  826     btrfs_release_path(path);
  827     return ret;
  828 }
  829 
  830 static inline int extent_ref_type(u64 parent, u64 owner)
  831 {
  832     int type;
  833     if (owner < BTRFS_FIRST_FREE_OBJECTID) {
  834         if (parent > 0)
  835             type = BTRFS_SHARED_BLOCK_REF_KEY;
  836         else
  837             type = BTRFS_TREE_BLOCK_REF_KEY;
  838     } else {
  839         if (parent > 0)
  840             type = BTRFS_SHARED_DATA_REF_KEY;
  841         else
  842             type = BTRFS_EXTENT_DATA_REF_KEY;
  843     }
  844     return type;
  845 }
  846 
  847 static int lookup_inline_extent_backref(struct btrfs_trans_handle *trans,
  848                  struct btrfs_root *root,
  849                  struct btrfs_path *path,
  850                  struct btrfs_extent_inline_ref **ref_ret,
  851                  u64 bytenr, u64 num_bytes,
  852                  u64 parent, u64 root_objectid,
  853                  u64 owner, u64 offset, int insert)
  854 {
  855     struct btrfs_key key;
  856     struct extent_buffer *leaf;
  857     struct btrfs_extent_item *ei;
  858     struct btrfs_extent_inline_ref *iref;
  859     u64 flags;
  860     u32 item_size;
  861     unsigned long ptr;
  862     unsigned long end;
  863     int extra_size;
  864     int type;
  865     int want;
  866     int ret;
  867     int err = 0;
  868     int skinny_metadata =
  869         btrfs_fs_incompat(root->fs_info, SKINNY_METADATA);
  870 
  871     key.objectid = bytenr;
  872     key.type = BTRFS_EXTENT_ITEM_KEY;
  873     key.offset = num_bytes;
  874 
  875     want = extent_ref_type(parent, owner);
  876     if (insert)
  877         extra_size = btrfs_extent_inline_ref_size(want);
  878     else
  879         extra_size = -1;
  880 
  881     if (owner < BTRFS_FIRST_FREE_OBJECTID && skinny_metadata) {
  882         key.type = BTRFS_METADATA_ITEM_KEY;
  883         key.offset = owner;
  884     } else if (skinny_metadata) {
  885         skinny_metadata = 0;
  886     }
  887 
  888 again:
  889     ret = btrfs_search_slot(trans, root, &key, path, extra_size, 1);
  890     if (ret < 0) {
  891         err = ret;
  892         goto out;
  893     }
  894 
  895     /*
  896      * We may be a newly converted file system which still has the old fat
  897      * extent entries for metadata, so try and see if we have one of those.
  898      */
  899     if (ret > 0 && skinny_metadata) {
  900         skinny_metadata = 0;
  901         if (path->slots[0]) {
  902             path->slots[0]--;
  903             btrfs_item_key_to_cpu(path->nodes[0], &key,
  904                           path->slots[0]);
  905             if (key.objectid == bytenr &&
  906                 key.type == BTRFS_EXTENT_ITEM_KEY &&
  907                 key.offset == num_bytes)
  908                 ret = 0;
  909         }
  910         if (ret) {
  911             key.type = BTRFS_EXTENT_ITEM_KEY;
  912             key.offset = num_bytes;
  913             btrfs_release_path(path);
  914             goto again;
  915         }
  916     }
  917 
  918     if (ret) {
  919         printf("Failed to find [%llu, %u, %llu]\n", key.objectid, key.type, key.offset);
  920         return -ENOENT;
  921     }
  922 
  923     BUG_ON(ret);
  924 
  925     leaf = path->nodes[0];
  926     item_size = btrfs_item_size_nr(leaf, path->slots[0]);
  927     if (item_size < sizeof(*ei)) {
  928         printf("Size is %u, needs to be %u, slot %d\n",
  929                (unsigned)item_size,
  930                (unsigned)sizeof(*ei), path->slots[0]);
  931         btrfs_print_leaf(leaf);
  932         return -EINVAL;
  933     }
  934 
  935     ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
  936     flags = btrfs_extent_flags(leaf, ei);
  937 
  938     ptr = (unsigned long)(ei + 1);
  939     end = (unsigned long)ei + item_size;
  940 
  941     if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK && !skinny_metadata) {
  942         ptr += sizeof(struct btrfs_tree_block_info);
  943         BUG_ON(ptr > end);
  944     } else if (!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)) {
  945         if (!(flags & BTRFS_EXTENT_FLAG_DATA)) {
  946             return -EIO;
  947         }
  948     }
  949 
  950     err = -ENOENT;
  951     while (1) {
  952         if (ptr >= end) {
  953             WARN_ON(ptr > end);
  954             break;
  955         }
  956         iref = (struct btrfs_extent_inline_ref *)ptr;
  957         type = btrfs_extent_inline_ref_type(leaf, iref);
  958         if (want < type)
  959             break;
  960         if (want > type) {
  961             ptr += btrfs_extent_inline_ref_size(type);
  962             continue;
  963         }
  964 
  965         if (type == BTRFS_EXTENT_DATA_REF_KEY) {
  966             struct btrfs_extent_data_ref *dref;
  967             dref = (struct btrfs_extent_data_ref *)(&iref->offset);
  968             if (match_extent_data_ref(leaf, dref, root_objectid,
  969                           owner, offset)) {
  970                 err = 0;
  971                 break;
  972             }
  973             if (hash_extent_data_ref_item(leaf, dref) <
  974                 hash_extent_data_ref(root_objectid, owner, offset))
  975                 break;
  976         } else {
  977             u64 ref_offset;
  978             ref_offset = btrfs_extent_inline_ref_offset(leaf, iref);
  979             if (parent > 0) {
  980                 if (parent == ref_offset) {
  981                     err = 0;
  982                     break;
  983                 }
  984                 if (ref_offset < parent)
  985                     break;
  986             } else {
  987                 if (root_objectid == ref_offset) {
  988                     err = 0;
  989                     break;
  990                 }
  991                 if (ref_offset < root_objectid)
  992                     break;
  993             }
  994         }
  995         ptr += btrfs_extent_inline_ref_size(type);
  996     }
  997     if (err == -ENOENT && insert) {
  998         if (item_size + extra_size >=
  999             BTRFS_MAX_EXTENT_ITEM_SIZE(root)) {
 1000             err = -EAGAIN;
 1001             goto out;
 1002         }
 1003         /*
 1004          * To add new inline back ref, we have to make sure
 1005          * there is no corresponding back ref item.
 1006          * For simplicity, we just do not add new inline back
 1007          * ref if there is any back ref item.
 1008          */
 1009         if (find_next_key(path, &key) == 0 && key.objectid == bytenr &&
 1010             key.type < BTRFS_BLOCK_GROUP_ITEM_KEY) {
 1011             err = -EAGAIN;
 1012             goto out;
 1013         }
 1014     }
 1015     *ref_ret = (struct btrfs_extent_inline_ref *)ptr;
 1016 out:
 1017     return err;
 1018 }
 1019 
 1020 static int setup_inline_extent_backref(struct btrfs_root *root,
 1021                 struct btrfs_path *path,
 1022                 struct btrfs_extent_inline_ref *iref,
 1023                 u64 parent, u64 root_objectid,
 1024                 u64 owner, u64 offset, int refs_to_add)
 1025 {
 1026     struct extent_buffer *leaf;
 1027     struct btrfs_extent_item *ei;
 1028     unsigned long ptr;
 1029     unsigned long end;
 1030     unsigned long item_offset;
 1031     u64 refs;
 1032     int size;
 1033     int type;
 1034     int ret;
 1035 
 1036     leaf = path->nodes[0];
 1037     ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
 1038     item_offset = (unsigned long)iref - (unsigned long)ei;
 1039 
 1040     type = extent_ref_type(parent, owner);
 1041     size = btrfs_extent_inline_ref_size(type);
 1042 
 1043     ret = btrfs_extend_item(root, path, size);
 1044     BUG_ON(ret);
 1045 
 1046     ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
 1047     refs = btrfs_extent_refs(leaf, ei);
 1048     refs += refs_to_add;
 1049     btrfs_set_extent_refs(leaf, ei, refs);
 1050 
 1051     ptr = (unsigned long)ei + item_offset;
 1052     end = (unsigned long)ei + btrfs_item_size_nr(leaf, path->slots[0]);
 1053     if (ptr < end - size)
 1054         memmove_extent_buffer(leaf, ptr + size, ptr,
 1055                       end - size - ptr);
 1056 
 1057     iref = (struct btrfs_extent_inline_ref *)ptr;
 1058     btrfs_set_extent_inline_ref_type(leaf, iref, type);
 1059     if (type == BTRFS_EXTENT_DATA_REF_KEY) {
 1060         struct btrfs_extent_data_ref *dref;
 1061         dref = (struct btrfs_extent_data_ref *)(&iref->offset);
 1062         btrfs_set_extent_data_ref_root(leaf, dref, root_objectid);
 1063         btrfs_set_extent_data_ref_objectid(leaf, dref, owner);
 1064         btrfs_set_extent_data_ref_offset(leaf, dref, offset);
 1065         btrfs_set_extent_data_ref_count(leaf, dref, refs_to_add);
 1066     } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
 1067         struct btrfs_shared_data_ref *sref;
 1068         sref = (struct btrfs_shared_data_ref *)(iref + 1);
 1069         btrfs_set_shared_data_ref_count(leaf, sref, refs_to_add);
 1070         btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
 1071     } else if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
 1072         btrfs_set_extent_inline_ref_offset(leaf, iref, parent);
 1073     } else {
 1074         btrfs_set_extent_inline_ref_offset(leaf, iref, root_objectid);
 1075     }
 1076     btrfs_mark_buffer_dirty(leaf);
 1077     return 0;
 1078 }
 1079 
 1080 static int lookup_extent_backref(struct btrfs_trans_handle *trans,
 1081                  struct btrfs_root *root,
 1082                  struct btrfs_path *path,
 1083                  struct btrfs_extent_inline_ref **ref_ret,
 1084                  u64 bytenr, u64 num_bytes, u64 parent,
 1085                  u64 root_objectid, u64 owner, u64 offset)
 1086 {
 1087     int ret;
 1088 
 1089     ret = lookup_inline_extent_backref(trans, root, path, ref_ret,
 1090                        bytenr, num_bytes, parent,
 1091                        root_objectid, owner, offset, 0);
 1092     if (ret != -ENOENT)
 1093         return ret;
 1094 
 1095     btrfs_release_path(path);
 1096     *ref_ret = NULL;
 1097 
 1098     if (owner < BTRFS_FIRST_FREE_OBJECTID) {
 1099         ret = lookup_tree_block_ref(trans, root, path, bytenr, parent,
 1100                         root_objectid);
 1101     } else {
 1102         ret = lookup_extent_data_ref(trans, root, path, bytenr, parent,
 1103                          root_objectid, owner, offset);
 1104     }
 1105     return ret;
 1106 }
 1107 
 1108 static int update_inline_extent_backref(struct btrfs_trans_handle *trans,
 1109                  struct btrfs_root *root,
 1110                  struct btrfs_path *path,
 1111                  struct btrfs_extent_inline_ref *iref,
 1112                  int refs_to_mod)
 1113 {
 1114     struct extent_buffer *leaf;
 1115     struct btrfs_extent_item *ei;
 1116     struct btrfs_extent_data_ref *dref = NULL;
 1117     struct btrfs_shared_data_ref *sref = NULL;
 1118     unsigned long ptr;
 1119     unsigned long end;
 1120     u32 item_size;
 1121     int size;
 1122     int type;
 1123     int ret;
 1124     u64 refs;
 1125 
 1126     leaf = path->nodes[0];
 1127     ei = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
 1128     refs = btrfs_extent_refs(leaf, ei);
 1129     WARN_ON(refs_to_mod < 0 && refs + refs_to_mod <= 0);
 1130     refs += refs_to_mod;
 1131     btrfs_set_extent_refs(leaf, ei, refs);
 1132 
 1133     type = btrfs_extent_inline_ref_type(leaf, iref);
 1134 
 1135     if (type == BTRFS_EXTENT_DATA_REF_KEY) {
 1136         dref = (struct btrfs_extent_data_ref *)(&iref->offset);
 1137         refs = btrfs_extent_data_ref_count(leaf, dref);
 1138     } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
 1139         sref = (struct btrfs_shared_data_ref *)(iref + 1);
 1140         refs = btrfs_shared_data_ref_count(leaf, sref);
 1141     } else {
 1142         refs = 1;
 1143         BUG_ON(refs_to_mod != -1);
 1144     }
 1145 
 1146     BUG_ON(refs_to_mod < 0 && refs < -refs_to_mod);
 1147     refs += refs_to_mod;
 1148 
 1149     if (refs > 0) {
 1150         if (type == BTRFS_EXTENT_DATA_REF_KEY)
 1151             btrfs_set_extent_data_ref_count(leaf, dref, refs);
 1152         else
 1153             btrfs_set_shared_data_ref_count(leaf, sref, refs);
 1154     } else {
 1155         size =  btrfs_extent_inline_ref_size(type);
 1156         item_size = btrfs_item_size_nr(leaf, path->slots[0]);
 1157         ptr = (unsigned long)iref;
 1158         end = (unsigned long)ei + item_size;
 1159         if (ptr + size < end)
 1160             memmove_extent_buffer(leaf, ptr, ptr + size,
 1161                           end - ptr - size);
 1162         item_size -= size;
 1163         ret = btrfs_truncate_item(root, path, item_size, 1);
 1164         BUG_ON(ret);
 1165     }
 1166     btrfs_mark_buffer_dirty(leaf);
 1167     return 0;
 1168 }
 1169 
 1170 static int insert_inline_extent_backref(struct btrfs_trans_handle *trans,
 1171                  struct btrfs_root *root,
 1172                  struct btrfs_path *path,
 1173                  u64 bytenr, u64 num_bytes, u64 parent,
 1174                  u64 root_objectid, u64 owner,
 1175                  u64 offset, int refs_to_add)
 1176 {
 1177     struct btrfs_extent_inline_ref *iref;
 1178     int ret;
 1179 
 1180     ret = lookup_inline_extent_backref(trans, root, path, &iref,
 1181                        bytenr, num_bytes, parent,
 1182                        root_objectid, owner, offset, 1);
 1183     if (ret == 0) {
 1184         BUG_ON(owner < BTRFS_FIRST_FREE_OBJECTID);
 1185         ret = update_inline_extent_backref(trans, root, path, iref,
 1186                            refs_to_add);
 1187     } else if (ret == -ENOENT) {
 1188         ret = setup_inline_extent_backref(root, path, iref,
 1189                           parent, root_objectid,
 1190                           owner, offset, refs_to_add);
 1191     }
 1192     return ret;
 1193 }
 1194 
 1195 static int insert_extent_backref(struct btrfs_trans_handle *trans,
 1196                  struct btrfs_root *root,
 1197                  struct btrfs_path *path,
 1198                  u64 bytenr, u64 parent, u64 root_objectid,
 1199                  u64 owner, u64 offset, int refs_to_add)
 1200 {
 1201     int ret;
 1202 
 1203     if (owner >= BTRFS_FIRST_FREE_OBJECTID) {
 1204         ret = insert_extent_data_ref(trans, root, path, bytenr,
 1205                          parent, root_objectid,
 1206                          owner, offset, refs_to_add);
 1207     } else {
 1208         BUG_ON(refs_to_add != 1);
 1209         ret = insert_tree_block_ref(trans, root, path, bytenr,
 1210                         parent, root_objectid);
 1211     }
 1212     return ret;
 1213 }
 1214 
 1215 static int remove_extent_backref(struct btrfs_trans_handle *trans,
 1216                  struct btrfs_root *root,
 1217                  struct btrfs_path *path,
 1218                  struct btrfs_extent_inline_ref *iref,
 1219                  int refs_to_drop, int is_data)
 1220 {
 1221     int ret;
 1222 
 1223     BUG_ON(!is_data && refs_to_drop != 1);
 1224     if (iref) {
 1225         ret = update_inline_extent_backref(trans, root, path, iref,
 1226                            -refs_to_drop);
 1227     } else if (is_data) {
 1228         ret = remove_extent_data_ref(trans, root, path, refs_to_drop);
 1229     } else {
 1230         ret = btrfs_del_item(trans, root, path);
 1231     }
 1232     return ret;
 1233 }
 1234 
 1235 int btrfs_inc_extent_ref(struct btrfs_trans_handle *trans,
 1236              struct btrfs_root *root,
 1237              u64 bytenr, u64 num_bytes, u64 parent,
 1238              u64 root_objectid, u64 owner, u64 offset)
 1239 {
 1240     struct btrfs_path *path;
 1241     struct extent_buffer *leaf;
 1242     struct btrfs_extent_item *item;
 1243     u64 refs;
 1244     int ret;
 1245     int err = 0;
 1246 
 1247     path = btrfs_alloc_path();
 1248     if (!path)
 1249         return -ENOMEM;
 1250 
 1251     path->reada = READA_BACK;
 1252 
 1253     ret = insert_inline_extent_backref(trans, root->fs_info->extent_root,
 1254                        path, bytenr, num_bytes, parent,
 1255                        root_objectid, owner, offset, 1);
 1256     if (ret == 0)
 1257         goto out;
 1258 
 1259     if (ret != -EAGAIN) {
 1260         err = ret;
 1261         goto out;
 1262     }
 1263 
 1264     leaf = path->nodes[0];
 1265     item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_extent_item);
 1266     refs = btrfs_extent_refs(leaf, item);
 1267     btrfs_set_extent_refs(leaf, item, refs + 1);
 1268 
 1269     btrfs_mark_buffer_dirty(leaf);
 1270     btrfs_release_path(path);
 1271 
 1272     path->reada = READA_BACK;
 1273 
 1274     /* now insert the actual backref */
 1275     ret = insert_extent_backref(trans, root->fs_info->extent_root,
 1276                     path, bytenr, parent, root_objectid,
 1277                     owner, offset, 1);
 1278     if (ret)
 1279         err = ret;
 1280 out:
 1281     btrfs_free_path(path);
 1282     BUG_ON(err);
 1283     return err;
 1284 }
 1285 
 1286 int btrfs_lookup_extent_info(struct btrfs_trans_handle *trans,
 1287                  struct btrfs_fs_info *fs_info, u64 bytenr,
 1288                  u64 offset, int metadata, u64 *refs, u64 *flags)
 1289 {
 1290     struct btrfs_path *path;
 1291     int ret;
 1292     struct btrfs_key key;
 1293     struct extent_buffer *l;
 1294     struct btrfs_extent_item *item;
 1295     u32 item_size;
 1296     u64 num_refs;
 1297     u64 extent_flags;
 1298 
 1299     if (metadata && !btrfs_fs_incompat(fs_info, SKINNY_METADATA)) {
 1300         offset = fs_info->nodesize;
 1301         metadata = 0;
 1302     }
 1303 
 1304     path = btrfs_alloc_path();
 1305     if (!path)
 1306         return -ENOMEM;
 1307     path->reada = READA_BACK;
 1308 
 1309     key.objectid = bytenr;
 1310     key.offset = offset;
 1311     if (metadata)
 1312         key.type = BTRFS_METADATA_ITEM_KEY;
 1313     else
 1314         key.type = BTRFS_EXTENT_ITEM_KEY;
 1315 
 1316 again:
 1317     ret = btrfs_search_slot(trans, fs_info->extent_root, &key, path, 0, 0);
 1318     if (ret < 0)
 1319         goto out;
 1320 
 1321     /*
 1322      * Deal with the fact that we may have mixed SKINNY and normal refs.  If
 1323      * we didn't find what we wanted check and see if we have a normal ref
 1324      * right next to us, or re-search if we are on the edge of the leaf just
 1325      * to make sure.
 1326      */
 1327     if (ret > 0 && metadata) {
 1328         if (path->slots[0]) {
 1329             path->slots[0]--;
 1330             btrfs_item_key_to_cpu(path->nodes[0], &key,
 1331                           path->slots[0]);
 1332             if (key.objectid == bytenr &&
 1333                 key.type == BTRFS_EXTENT_ITEM_KEY &&
 1334                 key.offset == fs_info->nodesize)
 1335                 ret = 0;
 1336         }
 1337 
 1338         if (ret) {
 1339             btrfs_release_path(path);
 1340             key.type = BTRFS_EXTENT_ITEM_KEY;
 1341             key.offset = fs_info->nodesize;
 1342             metadata = 0;
 1343             goto again;
 1344         }
 1345     }
 1346 
 1347     if (ret != 0) {
 1348         ret = -EIO;
 1349         goto out;
 1350     }
 1351 
 1352     l = path->nodes[0];
 1353     item_size = btrfs_item_size_nr(l, path->slots[0]);
 1354     if (item_size >= sizeof(*item)) {
 1355         item = btrfs_item_ptr(l, path->slots[0],
 1356                       struct btrfs_extent_item);
 1357         num_refs = btrfs_extent_refs(l, item);
 1358         extent_flags = btrfs_extent_flags(l, item);
 1359     } else {
 1360             BUG();
 1361     }
 1362     item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
 1363     if (refs)
 1364         *refs = num_refs;
 1365     if (flags)
 1366         *flags = extent_flags;
 1367 out:
 1368     btrfs_free_path(path);
 1369     return ret;
 1370 }
 1371 
 1372 int btrfs_set_block_flags(struct btrfs_trans_handle *trans, u64 bytenr,
 1373               int level, u64 flags)
 1374 {
 1375     struct btrfs_fs_info *fs_info = trans->fs_info;
 1376     struct btrfs_path *path;
 1377     int ret;
 1378     struct btrfs_key key;
 1379     struct extent_buffer *l;
 1380     struct btrfs_extent_item *item;
 1381     u32 item_size;
 1382     int skinny_metadata = btrfs_fs_incompat(fs_info, SKINNY_METADATA);
 1383 
 1384     path = btrfs_alloc_path();
 1385     if (!path)
 1386         return -ENOMEM;
 1387     path->reada = READA_BACK;
 1388 
 1389     key.objectid = bytenr;
 1390     if (skinny_metadata) {
 1391         key.offset = level;
 1392         key.type = BTRFS_METADATA_ITEM_KEY;
 1393     } else {
 1394         key.offset = fs_info->nodesize;
 1395         key.type = BTRFS_EXTENT_ITEM_KEY;
 1396     }
 1397 
 1398 again:
 1399     ret = btrfs_search_slot(trans, fs_info->extent_root, &key, path, 0, 0);
 1400     if (ret < 0)
 1401         goto out;
 1402 
 1403     if (ret > 0 && skinny_metadata) {
 1404         skinny_metadata = 0;
 1405         if (path->slots[0]) {
 1406             path->slots[0]--;
 1407             btrfs_item_key_to_cpu(path->nodes[0], &key,
 1408                           path->slots[0]);
 1409             if (key.objectid == bytenr &&
 1410                 key.offset == fs_info->nodesize &&
 1411                 key.type == BTRFS_EXTENT_ITEM_KEY)
 1412                 ret = 0;
 1413         }
 1414         if (ret) {
 1415             btrfs_release_path(path);
 1416             key.offset = fs_info->nodesize;
 1417             key.type = BTRFS_EXTENT_ITEM_KEY;
 1418             goto again;
 1419         }
 1420     }
 1421 
 1422     if (ret != 0) {
 1423         btrfs_print_leaf(path->nodes[0]);
 1424         printk("failed to find block number %Lu\n",
 1425             (unsigned long long)bytenr);
 1426         BUG();
 1427     }
 1428     l = path->nodes[0];
 1429     item_size = btrfs_item_size_nr(l, path->slots[0]);
 1430     if (item_size < sizeof(*item)) {
 1431         error(
 1432 "unsupported or corrupted extent item, item size=%u expect minimal size=%zu",
 1433             item_size, sizeof(*item));
 1434         ret = -EUCLEAN;
 1435         goto out;
 1436     }
 1437     item = btrfs_item_ptr(l, path->slots[0], struct btrfs_extent_item);
 1438     flags |= btrfs_extent_flags(l, item);
 1439     btrfs_set_extent_flags(l, item, flags);
 1440 out:
 1441     btrfs_free_path(path);
 1442     return ret;
 1443 }
 1444 
 1445 static int __btrfs_mod_ref(struct btrfs_trans_handle *trans,
 1446                struct btrfs_root *root,
 1447                struct extent_buffer *buf,
 1448                int record_parent, int inc)
 1449 {
 1450     u64 bytenr;
 1451     u64 num_bytes;
 1452     u64 parent;
 1453     u64 ref_root;
 1454     u32 nritems;
 1455     struct btrfs_key key;
 1456     struct btrfs_file_extent_item *fi;
 1457     int i;
 1458     int level;
 1459     int ret = 0;
 1460     int (*process_func)(struct btrfs_trans_handle *trans,
 1461                 struct btrfs_root *root,
 1462                 u64, u64, u64, u64, u64, u64);
 1463 
 1464     ref_root = btrfs_header_owner(buf);
 1465     nritems = btrfs_header_nritems(buf);
 1466     level = btrfs_header_level(buf);
 1467 
 1468     if (!root->ref_cows && level == 0)
 1469         return 0;
 1470 
 1471     if (inc)
 1472         process_func = btrfs_inc_extent_ref;
 1473     else
 1474         process_func = btrfs_free_extent;
 1475 
 1476     if (record_parent)
 1477         parent = buf->start;
 1478     else
 1479         parent = 0;
 1480 
 1481     for (i = 0; i < nritems; i++) {
 1482         cond_resched();
 1483         if (level == 0) {
 1484             btrfs_item_key_to_cpu(buf, &key, i);
 1485             if (key.type != BTRFS_EXTENT_DATA_KEY)
 1486                 continue;
 1487             fi = btrfs_item_ptr(buf, i,
 1488                         struct btrfs_file_extent_item);
 1489             if (btrfs_file_extent_type(buf, fi) ==
 1490                 BTRFS_FILE_EXTENT_INLINE)
 1491                 continue;
 1492             bytenr = btrfs_file_extent_disk_bytenr(buf, fi);
 1493             if (bytenr == 0)
 1494                 continue;
 1495 
 1496             num_bytes = btrfs_file_extent_disk_num_bytes(buf, fi);
 1497             key.offset -= btrfs_file_extent_offset(buf, fi);
 1498             ret = process_func(trans, root, bytenr, num_bytes,
 1499                        parent, ref_root, key.objectid,
 1500                        key.offset);
 1501             if (ret) {
 1502                 WARN_ON(1);
 1503                 goto fail;
 1504             }
 1505         } else {
 1506             bytenr = btrfs_node_blockptr(buf, i);
 1507             num_bytes = root->fs_info->nodesize;
 1508             ret = process_func(trans, root, bytenr, num_bytes,
 1509                        parent, ref_root, level - 1, 0);
 1510             if (ret) {
 1511                 WARN_ON(1);
 1512                 goto fail;
 1513             }
 1514         }
 1515     }
 1516     return 0;
 1517 fail:
 1518     WARN_ON(1);
 1519     return ret;
 1520 }
 1521 
 1522 int btrfs_inc_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 1523           struct extent_buffer *buf, int record_parent)
 1524 {
 1525     return __btrfs_mod_ref(trans, root, buf, record_parent, 1);
 1526 }
 1527 
 1528 int btrfs_dec_ref(struct btrfs_trans_handle *trans, struct btrfs_root *root,
 1529           struct extent_buffer *buf, int record_parent)
 1530 {
 1531     return __btrfs_mod_ref(trans, root, buf, record_parent, 0);
 1532 }
 1533 
 1534 static int write_one_cache_group(struct btrfs_trans_handle *trans,
 1535                  struct btrfs_path *path,
 1536                  struct btrfs_block_group_cache *cache)
 1537 {
 1538     int ret;
 1539     struct btrfs_root *extent_root = trans->fs_info->extent_root;
 1540     unsigned long bi;
 1541     struct btrfs_block_group_item bgi;
 1542     struct extent_buffer *leaf;
 1543 
 1544     ret = btrfs_search_slot(trans, extent_root, &cache->key, path, 0, 1);
 1545     if (ret < 0)
 1546         goto fail;
 1547     BUG_ON(ret);
 1548 
 1549     leaf = path->nodes[0];
 1550     bi = btrfs_item_ptr_offset(leaf, path->slots[0]);
 1551     btrfs_set_block_group_used(&bgi, cache->used);
 1552     btrfs_set_block_group_flags(&bgi, cache->flags);
 1553     btrfs_set_block_group_chunk_objectid(&bgi, BTRFS_FIRST_CHUNK_TREE_OBJECTID);
 1554     write_extent_buffer(leaf, &bgi, bi, sizeof(bgi));
 1555     btrfs_mark_buffer_dirty(leaf);
 1556     btrfs_release_path(path);
 1557 fail:
 1558     if (ret)
 1559         return ret;
 1560     return 0;
 1561 
 1562 }
 1563 
 1564 int btrfs_write_dirty_block_groups(struct btrfs_trans_handle *trans)
 1565 {
 1566     struct extent_io_tree *block_group_cache;
 1567     struct btrfs_block_group_cache *cache;
 1568     int ret;
 1569     struct btrfs_path *path;
 1570     u64 last = 0;
 1571     u64 start;
 1572     u64 end;
 1573     u64 ptr;
 1574 
 1575     block_group_cache = &trans->fs_info->block_group_cache;
 1576     path = btrfs_alloc_path();
 1577     if (!path)
 1578         return -ENOMEM;
 1579 
 1580     while(1) {
 1581         ret = find_first_extent_bit(block_group_cache, last,
 1582                         &start, &end, BLOCK_GROUP_DIRTY);
 1583         if (ret) {
 1584             if (last == 0)
 1585                 break;
 1586             last = 0;
 1587             continue;
 1588         }
 1589 
 1590         last = end + 1;
 1591         ret = get_state_private(block_group_cache, start, &ptr);
 1592         BUG_ON(ret);
 1593 
 1594         clear_extent_bits(block_group_cache, start, end,
 1595                   BLOCK_GROUP_DIRTY);
 1596 
 1597         cache = (struct btrfs_block_group_cache *)(unsigned long)ptr;
 1598         ret = write_one_cache_group(trans, path, cache);
 1599     }
 1600     btrfs_free_path(path);
 1601     return 0;
 1602 }
 1603 
 1604 static struct btrfs_space_info *__find_space_info(struct btrfs_fs_info *info,
 1605                           u64 flags)
 1606 {
 1607     struct btrfs_space_info *found;
 1608 
 1609     flags &= BTRFS_BLOCK_GROUP_TYPE_MASK;
 1610 
 1611     list_for_each_entry(found, &info->space_info, list) {
 1612         if (found->flags & flags)
 1613             return found;
 1614     }
 1615     return NULL;
 1616 
 1617 }
 1618 
 1619 static int free_space_info(struct btrfs_fs_info *fs_info, u64 flags,
 1620                           u64 total_bytes, u64 bytes_used,
 1621                           struct btrfs_space_info **space_info)
 1622 {
 1623     struct btrfs_space_info *found;
 1624 
 1625     /* only support free block group which is empty */
 1626     if (bytes_used)
 1627         return -ENOTEMPTY;
 1628 
 1629     found = __find_space_info(fs_info, flags);
 1630     if (!found)
 1631         return -ENOENT;
 1632     if (found->total_bytes < total_bytes) {
 1633         fprintf(stderr,
 1634             "WARNING: bad space info to free %llu only have %llu\n",
 1635             total_bytes, found->total_bytes);
 1636         return -EINVAL;
 1637     }
 1638     found->total_bytes -= total_bytes;
 1639     if (space_info)
 1640         *space_info = found;
 1641     return 0;
 1642 }
 1643 
 1644 int update_space_info(struct btrfs_fs_info *info, u64 flags,
 1645               u64 total_bytes, u64 bytes_used,
 1646               struct btrfs_space_info **space_info)
 1647 {
 1648     struct btrfs_space_info *found;
 1649 
 1650     found = __find_space_info(info, flags);
 1651     if (found) {
 1652         found->total_bytes += total_bytes;
 1653         found->bytes_used += bytes_used;
 1654         if (found->total_bytes < found->bytes_used) {
 1655             fprintf(stderr, "warning, bad space info total_bytes "
 1656                 "%llu used %llu\n",
 1657                    (unsigned long long)found->total_bytes,
 1658                    (unsigned long long)found->bytes_used);
 1659         }
 1660         *space_info = found;
 1661         return 0;
 1662     }
 1663     found = kmalloc(sizeof(*found), GFP_NOFS);
 1664     if (!found)
 1665         return -ENOMEM;
 1666 
 1667     list_add(&found->list, &info->space_info);
 1668     found->flags = flags & BTRFS_BLOCK_GROUP_TYPE_MASK;
 1669     found->total_bytes = total_bytes;
 1670     found->bytes_used = bytes_used;
 1671     found->bytes_pinned = 0;
 1672     found->bytes_reserved = 0;
 1673     found->full = 0;
 1674     *space_info = found;
 1675     return 0;
 1676 }
 1677 
 1678 
 1679 static void set_avail_alloc_bits(struct btrfs_fs_info *fs_info, u64 flags)
 1680 {
 1681     u64 extra_flags = flags & (BTRFS_BLOCK_GROUP_RAID0 |
 1682                    BTRFS_BLOCK_GROUP_RAID1 |
 1683                    BTRFS_BLOCK_GROUP_RAID1C3 |
 1684                    BTRFS_BLOCK_GROUP_RAID1C4 |
 1685                    BTRFS_BLOCK_GROUP_RAID10 |
 1686                    BTRFS_BLOCK_GROUP_RAID5 |
 1687                    BTRFS_BLOCK_GROUP_RAID6 |
 1688                    BTRFS_BLOCK_GROUP_DUP);
 1689     if (extra_flags) {
 1690         if (flags & BTRFS_BLOCK_GROUP_DATA)
 1691             fs_info->avail_data_alloc_bits |= extra_flags;
 1692         if (flags & BTRFS_BLOCK_GROUP_METADATA)
 1693             fs_info->avail_metadata_alloc_bits |= extra_flags;
 1694         if (flags & BTRFS_BLOCK_GROUP_SYSTEM)
 1695             fs_info->avail_system_alloc_bits |= extra_flags;
 1696     }
 1697 }
 1698 
 1699 static int do_chunk_alloc(struct btrfs_trans_handle *trans,
 1700               struct btrfs_fs_info *fs_info, u64 alloc_bytes,
 1701               u64 flags)
 1702 {
 1703     struct btrfs_space_info *space_info;
 1704     u64 thresh;
 1705     u64 start;
 1706     u64 num_bytes;
 1707     int ret;
 1708 
 1709     space_info = __find_space_info(fs_info, flags);
 1710     if (!space_info) {
 1711         ret = update_space_info(fs_info, flags, 0, 0, &space_info);
 1712         BUG_ON(ret);
 1713     }
 1714     BUG_ON(!space_info);
 1715 
 1716     if (space_info->full)
 1717         return 0;
 1718 
 1719     thresh = div_factor(space_info->total_bytes, 7);
 1720     if ((space_info->bytes_used + space_info->bytes_pinned +
 1721          space_info->bytes_reserved + alloc_bytes) < thresh)
 1722         return 0;
 1723 
 1724     /*
 1725      * Avoid allocating given chunk type
 1726      */
 1727     if (fs_info->avoid_meta_chunk_alloc &&
 1728         (flags & BTRFS_BLOCK_GROUP_METADATA))
 1729         return 0;
 1730     if (fs_info->avoid_sys_chunk_alloc &&
 1731         (flags & BTRFS_BLOCK_GROUP_SYSTEM))
 1732         return 0;
 1733 
 1734     /*
 1735      * We're going to allocate new chunk, during the process, we will
 1736      * allocate new tree blocks, which can trigger new chunk allocation
 1737      * again. Avoid the recursion.
 1738      */
 1739     if (trans->allocating_chunk)
 1740         return 0;
 1741     trans->allocating_chunk = 1;
 1742 
 1743     ret = btrfs_alloc_chunk(trans, fs_info, &start, &num_bytes,
 1744                             space_info->flags);
 1745     if (ret == -ENOSPC) {
 1746         space_info->full = 1;
 1747         trans->allocating_chunk = 0;
 1748         return 0;
 1749     }
 1750 
 1751     BUG_ON(ret);
 1752 
 1753     ret = btrfs_make_block_group(trans, fs_info, 0, space_info->flags,
 1754                      start, num_bytes);
 1755     BUG_ON(ret);
 1756     trans->allocating_chunk = 0;
 1757     return 0;
 1758 }
 1759 
 1760 static int update_block_group(struct btrfs_fs_info *info, u64 bytenr,
 1761                   u64 num_bytes, int alloc, int mark_free)
 1762 {
 1763     struct btrfs_block_group_cache *cache;
 1764     u64 total = num_bytes;
 1765     u64 old_val;
 1766     u64 byte_in_group;
 1767     u64 start;
 1768     u64 end;
 1769 
 1770     /* block accounting for super block */
 1771     old_val = btrfs_super_bytes_used(info->super_copy);
 1772     if (alloc)
 1773         old_val += num_bytes;
 1774     else
 1775         old_val -= num_bytes;
 1776     btrfs_set_super_bytes_used(info->super_copy, old_val);
 1777 
 1778     while(total) {
 1779         cache = btrfs_lookup_block_group(info, bytenr);
 1780         if (!cache) {
 1781             return -1;
 1782         }
 1783         byte_in_group = bytenr - cache->key.objectid;
 1784         WARN_ON(byte_in_group > cache->key.offset);
 1785         start = cache->key.objectid;
 1786         end = start + cache->key.offset - 1;
 1787         set_extent_bits(&info->block_group_cache, start, end,
 1788                 BLOCK_GROUP_DIRTY);
 1789 
 1790         old_val = cache->used;
 1791         num_bytes = min(total, cache->key.offset - byte_in_group);
 1792 
 1793         if (alloc) {
 1794             old_val += num_bytes;
 1795             cache->space_info->bytes_used += num_bytes;
 1796         } else {
 1797             old_val -= num_bytes;
 1798             cache->space_info->bytes_used -= num_bytes;
 1799             if (mark_free) {
 1800                 set_extent_dirty(&info->free_space_cache,
 1801                         bytenr, bytenr + num_bytes - 1);
 1802             }
 1803         }
 1804         cache->used = old_val;
 1805         total -= num_bytes;
 1806         bytenr += num_bytes;
 1807     }
 1808     return 0;
 1809 }
 1810 
 1811 static int update_pinned_extents(struct btrfs_fs_info *fs_info,
 1812                 u64 bytenr, u64 num, int pin)
 1813 {
 1814     u64 len;
 1815     struct btrfs_block_group_cache *cache;
 1816 
 1817     if (pin) {
 1818         set_extent_dirty(&fs_info->pinned_extents,
 1819                 bytenr, bytenr + num - 1);
 1820     } else {
 1821         clear_extent_dirty(&fs_info->pinned_extents,
 1822                 bytenr, bytenr + num - 1);
 1823     }
 1824     while (num > 0) {
 1825         cache = btrfs_lookup_block_group(fs_info, bytenr);
 1826         if (!cache) {
 1827             len = min((u64)fs_info->sectorsize, num);
 1828             goto next;
 1829         }
 1830         WARN_ON(!cache);
 1831         len = min(num, cache->key.offset -
 1832               (bytenr - cache->key.objectid));
 1833         if (pin) {
 1834             cache->pinned += len;
 1835             cache->space_info->bytes_pinned += len;
 1836             fs_info->total_pinned += len;
 1837         } else {
 1838             cache->pinned -= len;
 1839             cache->space_info->bytes_pinned -= len;
 1840             fs_info->total_pinned -= len;
 1841         }
 1842 next:
 1843         bytenr += len;
 1844         num -= len;
 1845     }
 1846     return 0;
 1847 }
 1848 
 1849 void btrfs_finish_extent_commit(struct btrfs_trans_handle *trans)
 1850 {
 1851     u64 start;
 1852     u64 end;
 1853     int ret;
 1854     struct btrfs_fs_info *fs_info = trans->fs_info;
 1855     struct extent_io_tree *free_space_cache = &fs_info->free_space_cache;
 1856     struct extent_io_tree *pinned_extents = &fs_info->pinned_extents;
 1857 
 1858     while(1) {
 1859         ret = find_first_extent_bit(pinned_extents, 0, &start, &end,
 1860                         EXTENT_DIRTY);
 1861         if (ret)
 1862             break;
 1863         update_pinned_extents(trans->fs_info, start, end + 1 - start,
 1864                       0);
 1865         clear_extent_dirty(pinned_extents, start, end);
 1866         set_extent_dirty(free_space_cache, start, end);
 1867     }
 1868 }
 1869 
 1870 static int pin_down_bytes(struct btrfs_trans_handle *trans, u64 bytenr,
 1871               u64 num_bytes, int is_data)
 1872 {
 1873     int err = 0;
 1874     struct extent_buffer *buf;
 1875 
 1876     if (is_data)
 1877         goto pinit;
 1878 
 1879     buf = btrfs_find_tree_block(trans->fs_info, bytenr, num_bytes);
 1880     if (!buf)
 1881         goto pinit;
 1882 
 1883     /* we can reuse a block if it hasn't been written
 1884      * and it is from this transaction.  We can't
 1885      * reuse anything from the tree log root because
 1886      * it has tiny sub-transactions.
 1887      */
 1888     if (btrfs_buffer_uptodate(buf, 0)) {
 1889         u64 header_owner = btrfs_header_owner(buf);
 1890         u64 header_transid = btrfs_header_generation(buf);
 1891         if (header_owner != BTRFS_TREE_LOG_OBJECTID &&
 1892             header_transid == trans->transid &&
 1893             !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_WRITTEN)) {
 1894             clean_tree_block(buf);
 1895             free_extent_buffer(buf);
 1896             return 1;
 1897         }
 1898     }
 1899     free_extent_buffer(buf);
 1900 pinit:
 1901     update_pinned_extents(trans->fs_info, bytenr, num_bytes, 1);
 1902 
 1903     BUG_ON(err < 0);
 1904     return 0;
 1905 }
 1906 
 1907 void btrfs_pin_extent(struct btrfs_fs_info *fs_info,
 1908                u64 bytenr, u64 num_bytes)
 1909 {
 1910     update_pinned_extents(fs_info, bytenr, num_bytes, 1);
 1911 }
 1912 
 1913 void btrfs_unpin_extent(struct btrfs_fs_info *fs_info,
 1914             u64 bytenr, u64 num_bytes)
 1915 {
 1916     update_pinned_extents(fs_info, bytenr, num_bytes, 0);
 1917 }
 1918 
 1919 /*
 1920  * remove an extent from the root, returns 0 on success
 1921  */
 1922 static int __free_extent(struct btrfs_trans_handle *trans,
 1923              u64 bytenr, u64 num_bytes, u64 parent,
 1924              u64 root_objectid, u64 owner_objectid,
 1925              u64 owner_offset, int refs_to_drop)
 1926 {
 1927 
 1928     struct btrfs_key key;
 1929     struct btrfs_path *path;
 1930     struct btrfs_root *extent_root = trans->fs_info->extent_root;
 1931     struct extent_buffer *leaf;
 1932     struct btrfs_extent_item *ei;
 1933     struct btrfs_extent_inline_ref *iref;
 1934     int ret;
 1935     int is_data;
 1936     int extent_slot = 0;
 1937     int found_extent = 0;
 1938     int num_to_del = 1;
 1939     u32 item_size;
 1940     u64 refs;
 1941     int skinny_metadata =
 1942         btrfs_fs_incompat(extent_root->fs_info, SKINNY_METADATA);
 1943 
 1944     if (trans->fs_info->free_extent_hook) {
 1945         trans->fs_info->free_extent_hook(trans->fs_info, bytenr, num_bytes,
 1946                         parent, root_objectid, owner_objectid,
 1947                         owner_offset, refs_to_drop);
 1948 
 1949     }
 1950     path = btrfs_alloc_path();
 1951     if (!path)
 1952         return -ENOMEM;
 1953 
 1954     path->reada = READA_BACK;
 1955 
 1956     is_data = owner_objectid >= BTRFS_FIRST_FREE_OBJECTID;
 1957     if (is_data)
 1958         skinny_metadata = 0;
 1959     BUG_ON(!is_data && refs_to_drop != 1);
 1960 
 1961     ret = lookup_extent_backref(trans, extent_root, path, &iref,
 1962                     bytenr, num_bytes, parent,
 1963                     root_objectid, owner_objectid,
 1964                     owner_offset);
 1965     if (ret == 0) {
 1966         extent_slot = path->slots[0];
 1967         while (extent_slot >= 0) {
 1968             btrfs_item_key_to_cpu(path->nodes[0], &key,
 1969                           extent_slot);
 1970             if (key.objectid != bytenr)
 1971                 break;
 1972             if (key.type == BTRFS_EXTENT_ITEM_KEY &&
 1973                 key.offset == num_bytes) {
 1974                 found_extent = 1;
 1975                 break;
 1976             }
 1977             if (key.type == BTRFS_METADATA_ITEM_KEY &&
 1978                 key.offset == owner_objectid) {
 1979                 found_extent = 1;
 1980                 break;
 1981             }
 1982             if (path->slots[0] - extent_slot > 5)
 1983                 break;
 1984             extent_slot--;
 1985         }
 1986         if (!found_extent) {
 1987             BUG_ON(iref);
 1988             ret = remove_extent_backref(trans, extent_root, path,
 1989                             NULL, refs_to_drop,
 1990                             is_data);
 1991             BUG_ON(ret);
 1992             btrfs_release_path(path);
 1993 
 1994             key.objectid = bytenr;
 1995 
 1996             if (skinny_metadata) {
 1997                 key.type = BTRFS_METADATA_ITEM_KEY;
 1998                 key.offset = owner_objectid;
 1999             } else {
 2000                 key.type = BTRFS_EXTENT_ITEM_KEY;
 2001                 key.offset = num_bytes;
 2002             }
 2003 
 2004             ret = btrfs_search_slot(trans, extent_root,
 2005                         &key, path, -1, 1);
 2006             if (ret > 0 && skinny_metadata && path->slots[0]) {
 2007                 path->slots[0]--;
 2008                 btrfs_item_key_to_cpu(path->nodes[0],
 2009                               &key,
 2010                               path->slots[0]);
 2011                 if (key.objectid == bytenr &&
 2012                     key.type == BTRFS_EXTENT_ITEM_KEY &&
 2013                     key.offset == num_bytes)
 2014                     ret = 0;
 2015             }
 2016 
 2017             if (ret > 0 && skinny_metadata) {
 2018                 skinny_metadata = 0;
 2019                 btrfs_release_path(path);
 2020                 key.type = BTRFS_EXTENT_ITEM_KEY;
 2021                 key.offset = num_bytes;
 2022                 ret = btrfs_search_slot(trans, extent_root,
 2023                             &key, path, -1, 1);
 2024             }
 2025 
 2026             if (ret) {
 2027                 printk(KERN_ERR "umm, got %d back from search"
 2028                        ", was looking for %llu\n", ret,
 2029                        (unsigned long long)bytenr);
 2030                 btrfs_print_leaf(path->nodes[0]);
 2031             }
 2032             BUG_ON(ret);
 2033             extent_slot = path->slots[0];
 2034         }
 2035     } else {
 2036         printk(KERN_ERR "btrfs unable to find ref byte nr %llu "
 2037                "parent %llu root %llu  owner %llu offset %llu\n",
 2038                (unsigned long long)bytenr,
 2039                (unsigned long long)parent,
 2040                (unsigned long long)root_objectid,
 2041                (unsigned long long)owner_objectid,
 2042                (unsigned long long)owner_offset);
 2043         printf("path->slots[0]: %d path->nodes[0]:\n", path->slots[0]);
 2044         btrfs_print_leaf(path->nodes[0]);
 2045         ret = -EIO;
 2046         goto fail;
 2047     }
 2048 
 2049     leaf = path->nodes[0];
 2050     item_size = btrfs_item_size_nr(leaf, extent_slot);
 2051     if (item_size < sizeof(*ei)) {
 2052         error(
 2053 "unsupported or corrupted extent item, item size=%u expect minimal size=%zu",
 2054             item_size, sizeof(*ei));
 2055         ret = -EUCLEAN;
 2056         goto fail;
 2057     }
 2058     ei = btrfs_item_ptr(leaf, extent_slot,
 2059                 struct btrfs_extent_item);
 2060     if (owner_objectid < BTRFS_FIRST_FREE_OBJECTID &&
 2061         key.type == BTRFS_EXTENT_ITEM_KEY) {
 2062         struct btrfs_tree_block_info *bi;
 2063         BUG_ON(item_size < sizeof(*ei) + sizeof(*bi));
 2064         bi = (struct btrfs_tree_block_info *)(ei + 1);
 2065         WARN_ON(owner_objectid != btrfs_tree_block_level(leaf, bi));
 2066     }
 2067 
 2068     refs = btrfs_extent_refs(leaf, ei);
 2069     BUG_ON(refs < refs_to_drop);
 2070     refs -= refs_to_drop;
 2071 
 2072     if (refs > 0) {
 2073         /*
 2074          * In the case of inline back ref, reference count will
 2075          * be updated by remove_extent_backref
 2076          */
 2077         if (iref) {
 2078             BUG_ON(!found_extent);
 2079         } else {
 2080             btrfs_set_extent_refs(leaf, ei, refs);
 2081             btrfs_mark_buffer_dirty(leaf);
 2082         }
 2083         if (found_extent) {
 2084             ret = remove_extent_backref(trans, extent_root, path,
 2085                             iref, refs_to_drop,
 2086                             is_data);
 2087             BUG_ON(ret);
 2088         }
 2089     } else {
 2090         int mark_free = 0;
 2091 
 2092         if (found_extent) {
 2093             BUG_ON(is_data && refs_to_drop !=
 2094                    extent_data_ref_count(path, iref));
 2095             if (iref) {
 2096                 BUG_ON(path->slots[0] != extent_slot);
 2097             } else {
 2098                 BUG_ON(path->slots[0] != extent_slot + 1);
 2099                 path->slots[0] = extent_slot;
 2100                 num_to_del = 2;
 2101             }
 2102         }
 2103 
 2104         ret = pin_down_bytes(trans, bytenr, num_bytes,
 2105                      is_data);
 2106         if (ret > 0)
 2107             mark_free = 1;
 2108         BUG_ON(ret < 0);
 2109 
 2110         ret = btrfs_del_items(trans, extent_root, path, path->slots[0],
 2111                       num_to_del);
 2112         BUG_ON(ret);
 2113         btrfs_release_path(path);
 2114 
 2115         if (is_data) {
 2116             ret = btrfs_del_csums(trans, bytenr, num_bytes);
 2117             BUG_ON(ret);
 2118         }
 2119 
 2120         ret = add_to_free_space_tree(trans, bytenr, num_bytes);
 2121         if (ret) {
 2122             goto fail;
 2123         }
 2124 
 2125         update_block_group(trans->fs_info, bytenr, num_bytes, 0,
 2126                    mark_free);
 2127     }
 2128 fail:
 2129     btrfs_free_path(path);
 2130     return ret;
 2131 }
 2132 
 2133 int btrfs_free_tree_block(struct btrfs_trans_handle *trans,
 2134               struct btrfs_root *root,
 2135               struct extent_buffer *buf,
 2136               u64 parent, int last_ref)
 2137 {
 2138     return btrfs_free_extent(trans, root, buf->start, buf->len, parent,
 2139                  root->root_key.objectid,
 2140                  btrfs_header_level(buf), 0);
 2141 }
 2142 
 2143 /*
 2144  * remove an extent from the root, returns 0 on success
 2145  */
 2146 
 2147 int btrfs_free_extent(struct btrfs_trans_handle *trans,
 2148               struct btrfs_root *root,
 2149               u64 bytenr, u64 num_bytes, u64 parent,
 2150               u64 root_objectid, u64 owner, u64 offset)
 2151 {
 2152     int ret;
 2153 
 2154     WARN_ON(num_bytes < root->fs_info->sectorsize);
 2155     /*
 2156      * tree log blocks never actually go into the extent allocation
 2157      * tree, just update pinning info and exit early.
 2158      */
 2159     if (root_objectid == BTRFS_TREE_LOG_OBJECTID) {
 2160         printf("PINNING EXTENTS IN LOG TREE\n");
 2161         WARN_ON(owner >= BTRFS_FIRST_FREE_OBJECTID);
 2162         btrfs_pin_extent(trans->fs_info, bytenr, num_bytes);
 2163         ret = 0;
 2164     } else if (owner < BTRFS_FIRST_FREE_OBJECTID) {
 2165         BUG_ON(offset);
 2166         ret = btrfs_add_delayed_tree_ref(trans->fs_info, trans,
 2167                          bytenr, num_bytes, parent,
 2168                          root_objectid, (int)owner,
 2169                          BTRFS_DROP_DELAYED_REF,
 2170                          NULL, NULL, NULL);
 2171     } else {
 2172         ret = __free_extent(trans, bytenr, num_bytes, parent,
 2173                     root_objectid, owner, offset, 1);
 2174     }
 2175     return ret;
 2176 }
 2177 
 2178 static u64 stripe_align(struct btrfs_root *root, u64 val)
 2179 {
 2180     return round_up(val, (u64)root->fs_info->stripesize);
 2181 }
 2182 
 2183 /*
 2184  * walks the btree of allocated extents and find a hole of a given size.
 2185  * The key ins is changed to record the hole:
 2186  * ins->objectid == block start
 2187  * ins->flags = BTRFS_EXTENT_ITEM_KEY
 2188  * ins->offset == number of blocks
 2189  * Any available blocks before search_start are skipped.
 2190  */
 2191 static int noinline find_free_extent(struct btrfs_trans_handle *trans,
 2192                      struct btrfs_root *orig_root,
 2193                      u64 num_bytes, u64 empty_size,
 2194                      u64 search_start, u64 search_end,
 2195                      u64 hint_byte, struct btrfs_key *ins,
 2196                      u64 exclude_start, u64 exclude_nr,
 2197                      int data)
 2198 {
 2199     int ret;
 2200     u64 orig_search_start = search_start;
 2201     struct btrfs_root * root = orig_root->fs_info->extent_root;
 2202     struct btrfs_fs_info *info = root->fs_info;
 2203     u64 total_needed = num_bytes;
 2204     struct btrfs_block_group_cache *block_group;
 2205     int full_scan = 0;
 2206     int wrapped = 0;
 2207 
 2208     WARN_ON(num_bytes < info->sectorsize);
 2209     ins->type = BTRFS_EXTENT_ITEM_KEY;
 2210 
 2211     search_start = stripe_align(root, search_start);
 2212 
 2213     if (hint_byte) {
 2214         block_group = btrfs_lookup_first_block_group(info, hint_byte);
 2215         if (!block_group)
 2216             hint_byte = search_start;
 2217         block_group = btrfs_find_block_group(root, block_group,
 2218                              hint_byte, data, 1);
 2219     } else {
 2220         block_group = btrfs_find_block_group(root,
 2221                              trans->block_group,
 2222                              search_start, data, 1);
 2223     }
 2224 
 2225     total_needed += empty_size;
 2226 
 2227 check_failed:
 2228     search_start = stripe_align(root, search_start);
 2229     if (!block_group) {
 2230         block_group = btrfs_lookup_first_block_group(info,
 2231                                  search_start);
 2232         if (!block_group)
 2233             block_group = btrfs_lookup_first_block_group(info,
 2234                                orig_search_start);
 2235     }
 2236     ret = find_search_start(root, &block_group, &search_start,
 2237                 total_needed, data);
 2238     if (ret)
 2239         goto new_group;
 2240 
 2241     ins->objectid = search_start;
 2242     ins->offset = num_bytes;
 2243 
 2244     if (ins->objectid + num_bytes >
 2245         block_group->key.objectid + block_group->key.offset) {
 2246         search_start = block_group->key.objectid +
 2247             block_group->key.offset;
 2248         goto new_group;
 2249     }
 2250 
 2251     if (test_range_bit(&info->extent_ins, ins->objectid,
 2252                ins->objectid + num_bytes -1, EXTENT_LOCKED, 0)) {
 2253         search_start = ins->objectid + num_bytes;
 2254         goto new_group;
 2255     }
 2256 
 2257     if (test_range_bit(&info->pinned_extents, ins->objectid,
 2258                ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
 2259         search_start = ins->objectid + num_bytes;
 2260         goto new_group;
 2261     }
 2262 
 2263     if (info->excluded_extents &&
 2264         test_range_bit(info->excluded_extents, ins->objectid,
 2265                ins->objectid + num_bytes -1, EXTENT_DIRTY, 0)) {
 2266         search_start = ins->objectid + num_bytes;
 2267         goto new_group;
 2268     }
 2269 
 2270     if (exclude_nr > 0 && (ins->objectid + num_bytes > exclude_start &&
 2271         ins->objectid < exclude_start + exclude_nr)) {
 2272         search_start = exclude_start + exclude_nr;
 2273         goto new_group;
 2274     }
 2275 
 2276     if (!(data & BTRFS_BLOCK_GROUP_DATA)) {
 2277         if (check_crossing_stripes(info, ins->objectid, num_bytes)) {
 2278             struct btrfs_block_group_cache *bg_cache;
 2279             u64 bg_offset;
 2280 
 2281             bg_cache = btrfs_lookup_block_group(info, ins->objectid);
 2282             if (!bg_cache)
 2283                 goto no_bg_cache;
 2284             bg_offset = ins->objectid - bg_cache->key.objectid;
 2285 
 2286             search_start = round_up(
 2287                 bg_offset + num_bytes, BTRFS_STRIPE_LEN) +
 2288                 bg_cache->key.objectid;
 2289             goto new_group;
 2290         }
 2291 no_bg_cache:
 2292         block_group = btrfs_lookup_block_group(info, ins->objectid);
 2293         if (block_group)
 2294             trans->block_group = block_group;
 2295     }
 2296     ins->offset = num_bytes;
 2297     return 0;
 2298 
 2299 new_group:
 2300     block_group = btrfs_lookup_first_block_group(info, search_start);
 2301     if (!block_group) {
 2302         search_start = orig_search_start;
 2303         if (full_scan) {
 2304             ret = -ENOSPC;
 2305             goto error;
 2306         }
 2307         if (wrapped) {
 2308             if (!full_scan)
 2309                 total_needed -= empty_size;
 2310             full_scan = 1;
 2311         } else
 2312             wrapped = 1;
 2313     }
 2314     cond_resched();
 2315     block_group = btrfs_find_block_group(root, block_group,
 2316                          search_start, data, 0);
 2317     goto check_failed;
 2318 
 2319 error:
 2320     return ret;
 2321 }
 2322 
 2323 int btrfs_reserve_extent(struct btrfs_trans_handle *trans,
 2324              struct btrfs_root *root,
 2325              u64 num_bytes, u64 empty_size,
 2326              u64 hint_byte, u64 search_end,
 2327              struct btrfs_key *ins, bool is_data)
 2328 {
 2329     int ret;
 2330     u64 search_start = 0;
 2331     u64 alloc_profile;
 2332     u64 profile;
 2333     struct btrfs_fs_info *info = root->fs_info;
 2334 
 2335     if (is_data) {
 2336         alloc_profile = info->avail_data_alloc_bits &
 2337                     info->data_alloc_profile;
 2338         profile = BTRFS_BLOCK_GROUP_DATA | alloc_profile;
 2339     } else if (info->system_allocs == 1 || root == info->chunk_root) {
 2340         alloc_profile = info->avail_system_alloc_bits &
 2341                     info->system_alloc_profile;
 2342         profile = BTRFS_BLOCK_GROUP_SYSTEM | alloc_profile;
 2343     } else {
 2344         alloc_profile = info->avail_metadata_alloc_bits &
 2345                     info->metadata_alloc_profile;
 2346         profile = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
 2347     }
 2348 
 2349     /*
 2350      * Also preallocate metadata for csum tree and fs trees (root->ref_cows
 2351      * already set), as they can consume a lot of metadata space.
 2352      * Pre-allocate to avoid unexpected ENOSPC.
 2353      */
 2354     if (root->ref_cows ||
 2355         root->root_key.objectid == BTRFS_CSUM_TREE_OBJECTID) {
 2356         if (!(profile & BTRFS_BLOCK_GROUP_METADATA)) {
 2357             ret = do_chunk_alloc(trans, info,
 2358                          num_bytes,
 2359                          BTRFS_BLOCK_GROUP_METADATA);
 2360             BUG_ON(ret);
 2361         }
 2362         ret = do_chunk_alloc(trans, info,
 2363                      num_bytes + SZ_2M, profile);
 2364         BUG_ON(ret);
 2365     }
 2366 
 2367     WARN_ON(num_bytes < info->sectorsize);
 2368     ret = find_free_extent(trans, root, num_bytes, empty_size,
 2369                    search_start, search_end, hint_byte, ins,
 2370                    trans->alloc_exclude_start,
 2371                    trans->alloc_exclude_nr, profile);
 2372     if (ret < 0)
 2373         return ret;
 2374     clear_extent_dirty(&info->free_space_cache,
 2375                ins->objectid, ins->objectid + ins->offset - 1);
 2376     return ret;
 2377 }
 2378 
 2379 static int alloc_reserved_tree_block(struct btrfs_trans_handle *trans,
 2380                       struct btrfs_delayed_ref_node *node,
 2381                       struct btrfs_delayed_extent_op *extent_op)
 2382 {
 2383 
 2384     struct btrfs_delayed_tree_ref *ref = btrfs_delayed_node_to_tree_ref(node);
 2385     bool skinny_metadata = btrfs_fs_incompat(trans->fs_info, SKINNY_METADATA);
 2386     struct btrfs_fs_info *fs_info = trans->fs_info;
 2387     struct btrfs_extent_item *extent_item;
 2388     struct btrfs_extent_inline_ref *iref;
 2389     struct btrfs_space_info *sinfo;
 2390     struct extent_buffer *leaf;
 2391     struct btrfs_path *path;
 2392     struct btrfs_key ins;
 2393     u32 size = sizeof(*extent_item) + sizeof(*iref);
 2394     u64 start, end;
 2395     int ret;
 2396 
 2397     sinfo = __find_space_info(fs_info, BTRFS_BLOCK_GROUP_METADATA);
 2398     ASSERT(sinfo);
 2399 
 2400     ins.objectid = node->bytenr;
 2401     if (skinny_metadata) {
 2402         ins.offset = ref->level;
 2403         ins.type = BTRFS_METADATA_ITEM_KEY;
 2404     } else {
 2405         ins.offset = node->num_bytes;
 2406         ins.type = BTRFS_EXTENT_ITEM_KEY;
 2407 
 2408         size += sizeof(struct btrfs_tree_block_info);
 2409     }
 2410 
 2411     if (ref->root == BTRFS_EXTENT_TREE_OBJECTID) {
 2412         ret = find_first_extent_bit(&trans->fs_info->extent_ins,
 2413                         node->bytenr, &start, &end,
 2414                         EXTENT_LOCKED);
 2415         ASSERT(!ret);
 2416         ASSERT(start == node->bytenr);
 2417         ASSERT(end == node->bytenr + node->num_bytes - 1);
 2418     }
 2419 
 2420     path = btrfs_alloc_path();
 2421     if (!path)
 2422         return -ENOMEM;
 2423 
 2424     ret = btrfs_insert_empty_item(trans, fs_info->extent_root, path,
 2425                       &ins, size);
 2426     if (ret)
 2427         return ret;
 2428 
 2429     leaf = path->nodes[0];
 2430     extent_item = btrfs_item_ptr(leaf, path->slots[0],
 2431                      struct btrfs_extent_item);
 2432     btrfs_set_extent_refs(leaf, extent_item, 1);
 2433     btrfs_set_extent_generation(leaf, extent_item, trans->transid);
 2434     btrfs_set_extent_flags(leaf, extent_item,
 2435                    extent_op->flags_to_set |
 2436                    BTRFS_EXTENT_FLAG_TREE_BLOCK);
 2437 
 2438     if (skinny_metadata) {
 2439         iref = (struct btrfs_extent_inline_ref *)(extent_item + 1);
 2440     } else {
 2441         struct btrfs_tree_block_info *block_info;
 2442         block_info = (struct btrfs_tree_block_info *)(extent_item + 1);
 2443         btrfs_set_tree_block_key(leaf, block_info, &extent_op->key);
 2444         btrfs_set_tree_block_level(leaf, block_info, ref->level);
 2445         iref = (struct btrfs_extent_inline_ref *)(block_info + 1);
 2446     }
 2447 
 2448     btrfs_set_extent_inline_ref_type(leaf, iref, BTRFS_TREE_BLOCK_REF_KEY);
 2449     btrfs_set_extent_inline_ref_offset(leaf, iref, ref->root);
 2450 
 2451     btrfs_mark_buffer_dirty(leaf);
 2452     btrfs_free_path(path);
 2453 
 2454     ret = remove_from_free_space_tree(trans, ins.objectid, fs_info->nodesize);
 2455     if (ret)
 2456         return ret;
 2457 
 2458     ret = update_block_group(fs_info, ins.objectid, fs_info->nodesize, 1,
 2459                  0);
 2460     if (sinfo) {
 2461         if (fs_info->nodesize > sinfo->bytes_reserved) {
 2462             WARN_ON(1);
 2463             sinfo->bytes_reserved = 0;
 2464         } else {
 2465             sinfo->bytes_reserved -= fs_info->nodesize;
 2466         }
 2467     }
 2468 
 2469     if (ref->root == BTRFS_EXTENT_TREE_OBJECTID) {
 2470         clear_extent_bits(&trans->fs_info->extent_ins, start, end,
 2471                   EXTENT_LOCKED);
 2472     }
 2473 
 2474     return ret;
 2475 }
 2476 
 2477 static int alloc_tree_block(struct btrfs_trans_handle *trans,
 2478                 struct btrfs_root *root, u64 num_bytes,
 2479                 u64 root_objectid, u64 generation,
 2480                 u64 flags, struct btrfs_disk_key *key,
 2481                 int level, u64 empty_size, u64 hint_byte,
 2482                 u64 search_end, struct btrfs_key *ins)
 2483 {
 2484     int ret;
 2485     u64 extent_size;
 2486     struct btrfs_delayed_extent_op *extent_op;
 2487     struct btrfs_space_info *sinfo;
 2488     struct btrfs_fs_info *fs_info = root->fs_info;
 2489     bool skinny_metadata = btrfs_fs_incompat(root->fs_info,
 2490                          SKINNY_METADATA);
 2491 
 2492     extent_op = btrfs_alloc_delayed_extent_op();
 2493     if (!extent_op)
 2494         return -ENOMEM;
 2495 
 2496     sinfo = __find_space_info(fs_info, BTRFS_BLOCK_GROUP_METADATA);
 2497     if (!sinfo) {
 2498         error("Corrupted fs, no valid METADATA block group found");
 2499         return -EUCLEAN;
 2500     }
 2501     ret = btrfs_reserve_extent(trans, root, num_bytes, empty_size,
 2502                    hint_byte, search_end, ins, 0);
 2503     if (ret < 0)
 2504         return ret;
 2505 
 2506     if (key)
 2507         memcpy(&extent_op->key, key, sizeof(extent_op->key));
 2508     else
 2509         memset(&extent_op->key, 0, sizeof(extent_op->key));
 2510     extent_op->flags_to_set = flags;
 2511     extent_op->update_key = skinny_metadata ? false : true;
 2512     extent_op->update_flags = true;
 2513     extent_op->is_data = false;
 2514     extent_op->level = level;
 2515 
 2516     extent_size = ins->offset;
 2517 
 2518     if (btrfs_fs_incompat(root->fs_info, SKINNY_METADATA)) {
 2519         ins->offset = level;
 2520         ins->type = BTRFS_METADATA_ITEM_KEY;
 2521     }
 2522 
 2523     /* Ensure this reserved extent is not found by the allocator */
 2524     if (root_objectid == BTRFS_EXTENT_TREE_OBJECTID) {
 2525         ret = set_extent_bits(&trans->fs_info->extent_ins,
 2526                       ins->objectid,
 2527                       ins->objectid + extent_size - 1,
 2528                       EXTENT_LOCKED);
 2529 
 2530         BUG_ON(ret);
 2531     }
 2532 
 2533     sinfo->bytes_reserved += extent_size;
 2534     ret = btrfs_add_delayed_tree_ref(root->fs_info, trans, ins->objectid,
 2535                      extent_size, 0, root_objectid,
 2536                      level, BTRFS_ADD_DELAYED_EXTENT,
 2537                      extent_op, NULL, NULL);
 2538     return ret;
 2539 }
 2540 
 2541 /*
 2542  * helper function to allocate a block for a given tree
 2543  * returns the tree buffer or NULL.
 2544  */
 2545 struct extent_buffer *btrfs_alloc_free_block(struct btrfs_trans_handle *trans,
 2546                     struct btrfs_root *root,
 2547                     u32 blocksize, u64 root_objectid,
 2548                     struct btrfs_disk_key *key, int level,
 2549                     u64 hint, u64 empty_size)
 2550 {
 2551     struct btrfs_key ins;
 2552     int ret;
 2553     struct extent_buffer *buf;
 2554 
 2555     ret = alloc_tree_block(trans, root, blocksize, root_objectid,
 2556                    trans->transid, 0, key, level,
 2557                    empty_size, hint, (u64)-1, &ins);
 2558     if (ret) {
 2559         BUG_ON(ret > 0);
 2560         return ERR_PTR(ret);
 2561     }
 2562 
 2563     buf = btrfs_find_create_tree_block(root->fs_info, ins.objectid);
 2564     if (!buf) {
 2565         btrfs_free_extent(trans, root, ins.objectid, ins.offset,
 2566                   0, root->root_key.objectid, level, 0);
 2567         BUG_ON(1);
 2568         return ERR_PTR(-ENOMEM);
 2569     }
 2570     btrfs_set_buffer_uptodate(buf);
 2571     trans->blocks_used++;
 2572 
 2573     return buf;
 2574 }
 2575 
 2576 int btrfs_free_block_groups(struct btrfs_fs_info *info)
 2577 {
 2578     struct btrfs_space_info *sinfo;
 2579     struct btrfs_block_group_cache *cache;
 2580     u64 start;
 2581     u64 end;
 2582     u64 ptr;
 2583     int ret;
 2584 
 2585     while(1) {
 2586         ret = find_first_extent_bit(&info->block_group_cache, 0,
 2587                         &start, &end, (unsigned int)-1);
 2588         if (ret)
 2589             break;
 2590         ret = get_state_private(&info->block_group_cache, start, &ptr);
 2591         if (!ret) {
 2592             cache = u64_to_ptr(ptr);
 2593             if (cache->free_space_ctl) {
 2594                 btrfs_remove_free_space_cache(cache);
 2595                 kfree(cache->free_space_ctl);
 2596             }
 2597             kfree(cache);
 2598         }
 2599         clear_extent_bits(&info->block_group_cache, start,
 2600                   end, (unsigned int)-1);
 2601     }
 2602     while(1) {
 2603         ret = find_first_extent_bit(&info->free_space_cache, 0,
 2604                         &start, &end, EXTENT_DIRTY);
 2605         if (ret)
 2606             break;
 2607         clear_extent_dirty(&info->free_space_cache, start, end);
 2608     }
 2609 
 2610     while (!list_empty(&info->space_info)) {
 2611         sinfo = list_entry(info->space_info.next,
 2612                    struct btrfs_space_info, list);
 2613         list_del_init(&sinfo->list);
 2614         if (sinfo->bytes_reserved)
 2615             warning(
 2616         "reserved space leaked, flag=0x%llx bytes_reserved=%llu",
 2617                 sinfo->flags, sinfo->bytes_reserved);
 2618         kfree(sinfo);
 2619     }
 2620     return 0;
 2621 }
 2622 
 2623 /*
 2624  * Find a block group which starts >= @key->objectid in extent tree.
 2625  *
 2626  * Return 0 for found
 2627  * Retrun >0 for not found
 2628  * Return <0 for error
 2629  */
 2630 static int find_first_block_group(struct btrfs_root *root,
 2631         struct btrfs_path *path, struct btrfs_key *key)
 2632 {
 2633     int ret;
 2634     struct btrfs_key found_key;
 2635     struct extent_buffer *leaf;
 2636     int slot;
 2637 
 2638     ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
 2639     if (ret < 0)
 2640         return ret;
 2641     while(1) {
 2642         slot = path->slots[0];
 2643         leaf = path->nodes[0];
 2644         if (slot >= btrfs_header_nritems(leaf)) {
 2645             ret = btrfs_next_leaf(root, path);
 2646             if (ret == 0)
 2647                 continue;
 2648             if (ret < 0)
 2649                 goto error;
 2650             break;
 2651         }
 2652         btrfs_item_key_to_cpu(leaf, &found_key, slot);
 2653 
 2654         if (found_key.objectid >= key->objectid &&
 2655             found_key.type == BTRFS_BLOCK_GROUP_ITEM_KEY)
 2656             return 0;
 2657         path->slots[0]++;
 2658     }
 2659     ret = 1;
 2660 error:
 2661     return ret;
 2662 }
 2663 
 2664 /*
 2665  * Read out one BLOCK_GROUP_ITEM and insert it into block group cache.
 2666  *
 2667  * Return 0 if nothing wrong (either insert the bg cache or skip 0 sized bg)
 2668  * Return <0 for error.
 2669  */
 2670 static int read_one_block_group(struct btrfs_fs_info *fs_info,
 2671                  struct btrfs_path *path)
 2672 {
 2673     struct extent_io_tree *block_group_cache = &fs_info->block_group_cache;
 2674     struct extent_buffer *leaf = path->nodes[0];
 2675     struct btrfs_space_info *space_info;
 2676     struct btrfs_block_group_cache *cache;
 2677     struct btrfs_block_group_item bgi;
 2678     struct btrfs_key key;
 2679     int slot = path->slots[0];
 2680     int bit = 0;
 2681     int ret;
 2682 
 2683     btrfs_item_key_to_cpu(leaf, &key, slot);
 2684     ASSERT(key.type == BTRFS_BLOCK_GROUP_ITEM_KEY);
 2685 
 2686     /*
 2687      * Skip 0 sized block group, don't insert them into block group cache
 2688      * tree, as its length is 0, it won't get freed at close_ctree() time.
 2689      */
 2690     if (key.offset == 0)
 2691         return 0;
 2692 
 2693     cache = kzalloc(sizeof(*cache), GFP_NOFS);
 2694     if (!cache)
 2695         return -ENOMEM;
 2696     read_extent_buffer(leaf, &bgi, btrfs_item_ptr_offset(leaf, slot),
 2697                sizeof(bgi));
 2698     memcpy(&cache->key, &key, sizeof(key));
 2699     cache->cached = 0;
 2700     cache->pinned = 0;
 2701     cache->flags = btrfs_block_group_flags(&bgi);
 2702     cache->used = btrfs_block_group_used(&bgi);
 2703     if (cache->flags & BTRFS_BLOCK_GROUP_DATA) {
 2704         bit = BLOCK_GROUP_DATA;
 2705     } else if (cache->flags & BTRFS_BLOCK_GROUP_SYSTEM) {
 2706         bit = BLOCK_GROUP_SYSTEM;
 2707     } else if (cache->flags & BTRFS_BLOCK_GROUP_METADATA) {
 2708         bit = BLOCK_GROUP_METADATA;
 2709     }
 2710     set_avail_alloc_bits(fs_info, cache->flags);
 2711     ret = btrfs_chunk_readonly(fs_info, cache->key.objectid);
 2712     if (ret < 0) {
 2713         free(cache);
 2714         return ret;
 2715     }
 2716     if (ret)
 2717         cache->ro = 1;
 2718     exclude_super_stripes(fs_info, cache);
 2719 
 2720     ret = update_space_info(fs_info, cache->flags, cache->key.offset,
 2721                 cache->used, &space_info);
 2722     if (ret < 0) {
 2723         free(cache);
 2724         return ret;
 2725     }
 2726     cache->space_info = space_info;
 2727 
 2728     set_extent_bits(block_group_cache, cache->key.objectid,
 2729             cache->key.objectid + cache->key.offset - 1,
 2730             bit | EXTENT_LOCKED);
 2731     set_state_private(block_group_cache, cache->key.objectid,
 2732               (unsigned long)cache);
 2733     return 0;
 2734 }
 2735 
 2736 int btrfs_read_block_groups(struct btrfs_fs_info *fs_info)
 2737 {
 2738     struct btrfs_path path;
 2739     struct btrfs_root *root;
 2740     int ret;
 2741     struct btrfs_key key;
 2742 
 2743     root = fs_info->extent_root;
 2744     key.objectid = 0;
 2745     key.offset = 0;
 2746     key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
 2747     btrfs_init_path(&path);
 2748 
 2749     while(1) {
 2750         ret = find_first_block_group(root, &path, &key);
 2751         if (ret > 0) {
 2752             ret = 0;
 2753             goto error;
 2754         }
 2755         if (ret != 0) {
 2756             goto error;
 2757         }
 2758         btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
 2759 
 2760         ret = read_one_block_group(fs_info, &path);
 2761         if (ret < 0 && ret != -ENOENT)
 2762             goto error;
 2763 
 2764         if (key.offset == 0)
 2765             key.objectid++;
 2766         else
 2767             key.objectid = key.objectid + key.offset;
 2768         key.offset = 0;
 2769         btrfs_release_path(&path);
 2770     }
 2771     ret = 0;
 2772 error:
 2773     btrfs_release_path(&path);
 2774     return ret;
 2775 }
 2776 
 2777 struct btrfs_block_group_cache *
 2778 btrfs_add_block_group(struct btrfs_fs_info *fs_info, u64 bytes_used, u64 type,
 2779               u64 chunk_offset, u64 size)
 2780 {
 2781     int ret;
 2782     int bit = 0;
 2783     struct btrfs_block_group_cache *cache;
 2784     struct extent_io_tree *block_group_cache;
 2785 
 2786     block_group_cache = &fs_info->block_group_cache;
 2787 
 2788     cache = kzalloc(sizeof(*cache), GFP_NOFS);
 2789     BUG_ON(!cache);
 2790     cache->key.objectid = chunk_offset;
 2791     cache->key.offset = size;
 2792 
 2793     cache->key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
 2794     cache->used = bytes_used;
 2795     cache->flags = type;
 2796 
 2797     exclude_super_stripes(fs_info, cache);
 2798     ret = update_space_info(fs_info, cache->flags, size, bytes_used,
 2799                 &cache->space_info);
 2800     BUG_ON(ret);
 2801 
 2802     bit = block_group_state_bits(type);
 2803     ret = set_extent_bits(block_group_cache, chunk_offset,
 2804                   chunk_offset + size - 1,
 2805                   bit | EXTENT_LOCKED);
 2806     BUG_ON(ret);
 2807 
 2808     ret = set_state_private(block_group_cache, chunk_offset,
 2809                 (unsigned long)cache);
 2810     BUG_ON(ret);
 2811     set_avail_alloc_bits(fs_info, type);
 2812 
 2813     return cache;
 2814 }
 2815 
 2816 int btrfs_make_block_group(struct btrfs_trans_handle *trans,
 2817                struct btrfs_fs_info *fs_info, u64 bytes_used,
 2818                u64 type, u64 chunk_offset, u64 size)
 2819 {
 2820     int ret;
 2821     struct btrfs_root *extent_root = fs_info->extent_root;
 2822     struct btrfs_block_group_cache *cache;
 2823     struct btrfs_block_group_item bgi;
 2824 
 2825     cache = btrfs_add_block_group(fs_info, bytes_used, type, chunk_offset,
 2826                       size);
 2827     btrfs_set_block_group_used(&bgi, cache->used);
 2828     btrfs_set_block_group_flags(&bgi, cache->flags);
 2829     btrfs_set_block_group_chunk_objectid(&bgi,
 2830             BTRFS_FIRST_CHUNK_TREE_OBJECTID);
 2831     ret = btrfs_insert_item(trans, extent_root, &cache->key, &bgi,
 2832                 sizeof(bgi));
 2833     BUG_ON(ret);
 2834 
 2835     return 0;
 2836 }
 2837 
 2838 /*
 2839  * This is for converter use only.
 2840  *
 2841  * In that case, we don't know where are free blocks located.
 2842  * Therefore all block group cache entries must be setup properly
 2843  * before doing any block allocation.
 2844  */
 2845 int btrfs_make_block_groups(struct btrfs_trans_handle *trans,
 2846                 struct btrfs_fs_info *fs_info)
 2847 {
 2848     u64 total_bytes;
 2849     u64 cur_start;
 2850     u64 group_type;
 2851     u64 group_size;
 2852     u64 group_align;
 2853     u64 total_data = 0;
 2854     u64 total_metadata = 0;
 2855     int ret;
 2856     int bit;
 2857     struct btrfs_root *extent_root = fs_info->extent_root;
 2858     struct btrfs_block_group_cache *cache;
 2859     struct extent_io_tree *block_group_cache;
 2860 
 2861     block_group_cache = &fs_info->block_group_cache;
 2862     total_bytes = btrfs_super_total_bytes(fs_info->super_copy);
 2863     group_align = 64 * fs_info->sectorsize;
 2864 
 2865     cur_start = 0;
 2866     while (cur_start < total_bytes) {
 2867         group_size = total_bytes / 12;
 2868         group_size = min_t(u64, group_size, total_bytes - cur_start);
 2869         if (cur_start == 0) {
 2870             bit = BLOCK_GROUP_SYSTEM;
 2871             group_type = BTRFS_BLOCK_GROUP_SYSTEM;
 2872             group_size /= 4;
 2873             group_size &= ~(group_align - 1);
 2874             group_size = max_t(u64, group_size, SZ_8M);
 2875             group_size = min_t(u64, group_size, SZ_32M);
 2876         } else {
 2877             group_size &= ~(group_align - 1);
 2878             if (total_data >= total_metadata * 2) {
 2879                 group_type = BTRFS_BLOCK_GROUP_METADATA;
 2880                 group_size = min_t(u64, group_size, SZ_1G);
 2881                 total_metadata += group_size;
 2882             } else {
 2883                 group_type = BTRFS_BLOCK_GROUP_DATA;
 2884                 group_size = min_t(u64, group_size,
 2885                            5ULL * SZ_1G);
 2886                 total_data += group_size;
 2887             }
 2888             if ((total_bytes - cur_start) * 4 < group_size * 5)
 2889                 group_size = total_bytes - cur_start;
 2890         }
 2891 
 2892         cache = kzalloc(sizeof(*cache), GFP_NOFS);
 2893         BUG_ON(!cache);
 2894 
 2895         cache->key.objectid = cur_start;
 2896         cache->key.offset = group_size;
 2897         cache->key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
 2898         cache->used = 0;
 2899         cache->flags = group_type;
 2900 
 2901         ret = update_space_info(fs_info, group_type, group_size,
 2902                     0, &cache->space_info);
 2903         BUG_ON(ret);
 2904         set_avail_alloc_bits(fs_info, group_type);
 2905 
 2906         set_extent_bits(block_group_cache, cur_start,
 2907                 cur_start + group_size - 1,
 2908                 bit | EXTENT_LOCKED);
 2909         set_state_private(block_group_cache, cur_start,
 2910                   (unsigned long)cache);
 2911         cur_start += group_size;
 2912     }
 2913     /* then insert all the items */
 2914     cur_start = 0;
 2915     while(cur_start < total_bytes) {
 2916         struct btrfs_block_group_item bgi;
 2917 
 2918         cache = btrfs_lookup_block_group(fs_info, cur_start);
 2919         BUG_ON(!cache);
 2920 
 2921         btrfs_set_block_group_used(&bgi, cache->used);
 2922         btrfs_set_block_group_flags(&bgi, cache->flags);
 2923         btrfs_set_block_group_chunk_objectid(&bgi,
 2924                 BTRFS_FIRST_CHUNK_TREE_OBJECTID);
 2925         ret = btrfs_insert_item(trans, extent_root, &cache->key, &bgi,
 2926                     sizeof(bgi));
 2927         BUG_ON(ret);
 2928 
 2929         cur_start = cache->key.objectid + cache->key.offset;
 2930     }
 2931     return 0;
 2932 }
 2933 
 2934 int btrfs_update_block_group(struct btrfs_root *root,
 2935                  u64 bytenr, u64 num_bytes, int alloc,
 2936                  int mark_free)
 2937 {
 2938     return update_block_group(root->fs_info, bytenr, num_bytes,
 2939                   alloc, mark_free);
 2940 }
 2941 
 2942 /*
 2943  * Just remove a block group item in extent tree
 2944  * Caller should ensure the block group is empty and all space is pinned.
 2945  * Or new tree block/data may be allocated into it.
 2946  */
 2947 static int free_block_group_item(struct btrfs_trans_handle *trans,
 2948                  struct btrfs_fs_info *fs_info,
 2949                  u64 bytenr, u64 len)
 2950 {
 2951     struct btrfs_path *path;
 2952     struct btrfs_key key;
 2953     struct btrfs_root *root = fs_info->extent_root;
 2954     int ret = 0;
 2955 
 2956     key.objectid = bytenr;
 2957     key.offset = len;
 2958     key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
 2959 
 2960     path = btrfs_alloc_path();
 2961     if (!path)
 2962         return -ENOMEM;
 2963 
 2964     ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 2965     if (ret > 0) {
 2966         ret = -ENOENT;
 2967         goto out;
 2968     }
 2969     if (ret < 0)
 2970         goto out;
 2971 
 2972     ret = btrfs_del_item(trans, root, path);
 2973 out:
 2974     btrfs_free_path(path);
 2975     return ret;
 2976 }
 2977 
 2978 static int free_dev_extent_item(struct btrfs_trans_handle *trans,
 2979                 struct btrfs_fs_info *fs_info,
 2980                 u64 devid, u64 dev_offset)
 2981 {
 2982     struct btrfs_root *root = fs_info->dev_root;
 2983     struct btrfs_path *path;
 2984     struct btrfs_key key;
 2985     int ret;
 2986 
 2987     path = btrfs_alloc_path();
 2988     if (!path)
 2989         return -ENOMEM;
 2990 
 2991     key.objectid = devid;
 2992     key.type = BTRFS_DEV_EXTENT_KEY;
 2993     key.offset = dev_offset;
 2994 
 2995     ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 2996     if (ret < 0)
 2997         goto out;
 2998     if (ret > 0) {
 2999         ret = -ENOENT;
 3000         goto out;
 3001     }
 3002 
 3003     ret = btrfs_del_item(trans, root, path);
 3004 out:
 3005     btrfs_free_path(path);
 3006     return ret;
 3007 }
 3008 
 3009 static int free_chunk_dev_extent_items(struct btrfs_trans_handle *trans,
 3010                        struct btrfs_fs_info *fs_info,
 3011                        u64 chunk_offset)
 3012 {
 3013     struct btrfs_chunk *chunk = NULL;
 3014     struct btrfs_root *root= fs_info->chunk_root;
 3015     struct btrfs_path *path;
 3016     struct btrfs_key key;
 3017     u16 num_stripes;
 3018     int i;
 3019     int ret;
 3020 
 3021     path = btrfs_alloc_path();
 3022     if (!path)
 3023         return -ENOMEM;
 3024 
 3025     key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
 3026     key.type = BTRFS_CHUNK_ITEM_KEY;
 3027     key.offset = chunk_offset;
 3028 
 3029     ret = btrfs_search_slot(trans, root, &key, path, 0, 0);
 3030     if (ret < 0)
 3031         goto out;
 3032     if (ret > 0) {
 3033         ret = -ENOENT;
 3034         goto out;
 3035     }
 3036     chunk = btrfs_item_ptr(path->nodes[0], path->slots[0],
 3037                    struct btrfs_chunk);
 3038     num_stripes = btrfs_chunk_num_stripes(path->nodes[0], chunk);
 3039     for (i = 0; i < num_stripes; i++) {
 3040         ret = free_dev_extent_item(trans, fs_info,
 3041             btrfs_stripe_devid_nr(path->nodes[0], chunk, i),
 3042             btrfs_stripe_offset_nr(path->nodes[0], chunk, i));
 3043         if (ret < 0)
 3044             goto out;
 3045     }
 3046 out:
 3047     btrfs_free_path(path);
 3048     return ret;
 3049 }
 3050 
 3051 static int free_system_chunk_item(struct btrfs_super_block *super,
 3052                   struct btrfs_key *key)
 3053 {
 3054     struct btrfs_disk_key *disk_key;
 3055     struct btrfs_key cpu_key;
 3056     u32 array_size = btrfs_super_sys_array_size(super);
 3057     char *ptr = (char *)super->sys_chunk_array;
 3058     int cur = 0;
 3059     int ret = -ENOENT;
 3060 
 3061     while (cur < btrfs_super_sys_array_size(super)) {
 3062         struct btrfs_chunk *chunk;
 3063         u32 num_stripes;
 3064         u32 chunk_len;
 3065 
 3066         disk_key = (struct btrfs_disk_key *)(ptr + cur);
 3067         btrfs_disk_key_to_cpu(&cpu_key, disk_key);
 3068         if (cpu_key.type != BTRFS_CHUNK_ITEM_KEY) {
 3069             /* just in case */
 3070             ret = -EIO;
 3071             goto out;
 3072         }
 3073 
 3074         chunk = (struct btrfs_chunk *)(ptr + cur + sizeof(*disk_key));
 3075         num_stripes = btrfs_stack_chunk_num_stripes(chunk);
 3076         chunk_len = btrfs_chunk_item_size(num_stripes) +
 3077                 sizeof(*disk_key);
 3078 
 3079         if (key->objectid == cpu_key.objectid &&
 3080             key->offset == cpu_key.offset &&
 3081             key->type == cpu_key.type) {
 3082             memmove(ptr + cur, ptr + cur + chunk_len,
 3083                 array_size - cur - chunk_len);
 3084             array_size -= chunk_len;
 3085             btrfs_set_super_sys_array_size(super, array_size);
 3086             ret = 0;
 3087             goto out;
 3088         }
 3089 
 3090         cur += chunk_len;
 3091     }
 3092 out:
 3093     return ret;
 3094 }
 3095 
 3096 static int free_chunk_item(struct btrfs_trans_handle *trans,
 3097                struct btrfs_fs_info *fs_info,
 3098                u64 bytenr)
 3099 {
 3100     struct btrfs_path *path;
 3101     struct btrfs_key key;
 3102     struct btrfs_root *root = fs_info->chunk_root;
 3103     struct btrfs_chunk *chunk;
 3104     u64 chunk_type;
 3105     int ret;
 3106 
 3107     key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
 3108     key.offset = bytenr;
 3109     key.type = BTRFS_CHUNK_ITEM_KEY;
 3110 
 3111     path = btrfs_alloc_path();
 3112     if (!path)
 3113         return -ENOMEM;
 3114 
 3115     ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
 3116     if (ret > 0) {
 3117         ret = -ENOENT;
 3118         goto out;
 3119     }
 3120     if (ret < 0)
 3121         goto out;
 3122     chunk = btrfs_item_ptr(path->nodes[0], path->slots[0],
 3123                    struct btrfs_chunk);
 3124     chunk_type = btrfs_chunk_type(path->nodes[0], chunk);
 3125 
 3126     ret = btrfs_del_item(trans, root, path);
 3127     if (ret < 0)
 3128         goto out;
 3129 
 3130     if (chunk_type & BTRFS_BLOCK_GROUP_SYSTEM)
 3131         ret = free_system_chunk_item(fs_info->super_copy, &key);
 3132 out:
 3133     btrfs_free_path(path);
 3134     return ret;
 3135 }
 3136 
 3137 static u64 get_dev_extent_len(struct map_lookup *map)
 3138 {
 3139     int div;
 3140 
 3141     switch (map->type & BTRFS_BLOCK_GROUP_PROFILE_MASK) {
 3142     case 0: /* Single */
 3143     case BTRFS_BLOCK_GROUP_DUP:
 3144     case BTRFS_BLOCK_GROUP_RAID1:
 3145     case BTRFS_BLOCK_GROUP_RAID1C3:
 3146     case BTRFS_BLOCK_GROUP_RAID1C4:
 3147         div = 1;
 3148         break;
 3149     case BTRFS_BLOCK_GROUP_RAID5:
 3150         div = (map->num_stripes - 1);
 3151         break;
 3152     case BTRFS_BLOCK_GROUP_RAID6:
 3153         div = (map->num_stripes - 2);
 3154         break;
 3155     case BTRFS_BLOCK_GROUP_RAID10:
 3156         div = (map->num_stripes / map->sub_stripes);
 3157         break;
 3158     default:
 3159         /* normally, read chunk security hook should handled it */
 3160         BUG_ON(1);
 3161     }
 3162     return map->ce.size / div;
 3163 }
 3164 
 3165 /* free block group/chunk related caches */
 3166 static int free_block_group_cache(struct btrfs_trans_handle *trans,
 3167                   struct btrfs_fs_info *fs_info,
 3168                   u64 bytenr, u64 len)
 3169 {
 3170     struct btrfs_block_group_cache *cache;
 3171     struct cache_extent *ce;
 3172     struct map_lookup *map;
 3173     int ret;
 3174     int i;
 3175     u64 flags;
 3176 
 3177     /* Free block group cache first */
 3178     cache = btrfs_lookup_block_group(fs_info, bytenr);
 3179     if (!cache)
 3180         return -ENOENT;
 3181     flags = cache->flags;
 3182     if (cache->free_space_ctl) {
 3183         btrfs_remove_free_space_cache(cache);
 3184         kfree(cache->free_space_ctl);
 3185     }
 3186     clear_extent_bits(&fs_info->block_group_cache, bytenr, bytenr + len - 1,
 3187               (unsigned int)-1);
 3188     ret = free_space_info(fs_info, flags, len, 0, NULL);
 3189     if (ret < 0)
 3190         goto out;
 3191     kfree(cache);
 3192 
 3193     /* Then free mapping info and dev usage info */
 3194     ce = search_cache_extent(&fs_info->mapping_tree.cache_tree, bytenr);
 3195     if (!ce || ce->start != bytenr) {
 3196         ret = -ENOENT;
 3197         goto out;
 3198     }
 3199     map = container_of(ce, struct map_lookup, ce);
 3200     for (i = 0; i < map->num_stripes; i++) {
 3201         struct btrfs_device *device;
 3202 
 3203         device = map->stripes[i].dev;
 3204         device->bytes_used -= get_dev_extent_len(map);
 3205         ret = btrfs_update_device(trans, device);
 3206         if (ret < 0)
 3207             goto out;
 3208     }
 3209     remove_cache_extent(&fs_info->mapping_tree.cache_tree, ce);
 3210     free(map);
 3211 out:
 3212     return ret;
 3213 }
 3214 
 3215 int btrfs_free_block_group(struct btrfs_trans_handle *trans,
 3216                struct btrfs_fs_info *fs_info, u64 bytenr, u64 len)
 3217 {
 3218     struct btrfs_root *extent_root = fs_info->extent_root;
 3219     struct btrfs_path *path;
 3220     struct btrfs_block_group_item *bgi;
 3221     struct btrfs_key key;
 3222     int ret = 0;
 3223 
 3224     path = btrfs_alloc_path();
 3225     if (!path)
 3226         return -ENOMEM;
 3227 
 3228     key.objectid = bytenr;
 3229     key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
 3230     key.offset = len;
 3231 
 3232     /* Double check the block group to ensure it's empty */
 3233     ret = btrfs_search_slot(trans, extent_root, &key, path, 0, 0);
 3234     if (ret > 0) {
 3235         ret = -ENONET;
 3236         goto out;
 3237     }
 3238     if (ret < 0)
 3239         goto out;
 3240 
 3241     bgi = btrfs_item_ptr(path->nodes[0], path->slots[0],
 3242                  struct btrfs_block_group_item);
 3243     if (btrfs_disk_block_group_used(path->nodes[0], bgi)) {
 3244         fprintf(stderr,
 3245             "WARNING: block group [%llu,%llu) is not empty\n",
 3246             bytenr, bytenr + len);
 3247         ret = -EINVAL;
 3248         goto out;
 3249     }
 3250     btrfs_release_path(path);
 3251 
 3252     /*
 3253      * Now pin all space in the block group, to prevent further transaction
 3254      * allocate space from it.
 3255      * Every operation needs a transaction must be in the range.
 3256      */
 3257     btrfs_pin_extent(fs_info, bytenr, len);
 3258 
 3259     /* delete block group item and chunk item */
 3260     ret = free_block_group_item(trans, fs_info, bytenr, len);
 3261     if (ret < 0) {
 3262         fprintf(stderr,
 3263             "failed to free block group item for [%llu,%llu)\n",
 3264             bytenr, bytenr + len);
 3265         btrfs_unpin_extent(fs_info, bytenr, len);
 3266         goto out;
 3267     }
 3268 
 3269     ret = free_chunk_dev_extent_items(trans, fs_info, bytenr);
 3270     if (ret < 0) {
 3271         fprintf(stderr,
 3272             "failed to dev extents belongs to [%llu,%llu)\n",
 3273             bytenr, bytenr + len);
 3274         btrfs_unpin_extent(fs_info, bytenr, len);
 3275         goto out;
 3276     }
 3277     ret = free_chunk_item(trans, fs_info, bytenr);
 3278     if (ret < 0) {
 3279         fprintf(stderr,
 3280             "failed to free chunk for [%llu,%llu)\n",
 3281             bytenr, bytenr + len);
 3282         btrfs_unpin_extent(fs_info, bytenr, len);
 3283         goto out;
 3284     }
 3285 
 3286     /* Now release the block_group_cache */
 3287     ret = free_block_group_cache(trans, fs_info, bytenr, len);
 3288     btrfs_unpin_extent(fs_info, bytenr, len);
 3289 
 3290 out:
 3291     btrfs_free_path(path);
 3292     return ret;
 3293 }
 3294 
 3295 /*
 3296  * Fixup block accounting. The initial block accounting created by
 3297  * make_block_groups isn't accuracy in this case.
 3298  */
 3299 int btrfs_fix_block_accounting(struct btrfs_trans_handle *trans)
 3300 {
 3301     int ret = 0;
 3302     int slot;
 3303     u64 start = 0;
 3304     u64 bytes_used = 0;
 3305     struct btrfs_path path;
 3306     struct btrfs_key key;
 3307     struct extent_buffer *leaf;
 3308     struct btrfs_block_group_cache *cache;
 3309     struct btrfs_fs_info *fs_info = trans->fs_info;
 3310     struct btrfs_root *root = fs_info->extent_root;
 3311 
 3312     ret = btrfs_run_delayed_refs(trans, -1);
 3313     if (ret)
 3314         return ret;
 3315 
 3316     while(1) {
 3317         cache = btrfs_lookup_first_block_group(fs_info, start);
 3318         if (!cache)
 3319             break;
 3320         start = cache->key.objectid + cache->key.offset;
 3321         cache->used = 0;
 3322         cache->space_info->bytes_used = 0;
 3323         set_extent_bits(&root->fs_info->block_group_cache,
 3324                 cache->key.objectid,
 3325                 cache->key.objectid + cache->key.offset -1,
 3326                 BLOCK_GROUP_DIRTY);
 3327     }
 3328 
 3329     btrfs_init_path(&path);
 3330     key.offset = 0;
 3331     key.objectid = 0;
 3332     key.type = BTRFS_EXTENT_ITEM_KEY;
 3333     ret = btrfs_search_slot(trans, root->fs_info->extent_root,
 3334                 &key, &path, 0, 0);
 3335     if (ret < 0)
 3336         return ret;
 3337     while(1) {
 3338         leaf = path.nodes[0];
 3339         slot = path.slots[0];
 3340         if (slot >= btrfs_header_nritems(leaf)) {
 3341             ret = btrfs_next_leaf(root, &path);
 3342             if (ret < 0)
 3343                 return ret;
 3344             if (ret > 0)
 3345                 break;
 3346             leaf = path.nodes[0];
 3347             slot = path.slots[0];
 3348         }
 3349         btrfs_item_key_to_cpu(leaf, &key, slot);
 3350         if (key.type == BTRFS_EXTENT_ITEM_KEY) {
 3351             bytes_used += key.offset;
 3352             ret = btrfs_update_block_group(root,
 3353                   key.objectid, key.offset, 1, 0);
 3354             BUG_ON(ret);
 3355         } else if (key.type == BTRFS_METADATA_ITEM_KEY) {
 3356             bytes_used += fs_info->nodesize;
 3357             ret = btrfs_update_block_group(root,
 3358                   key.objectid, fs_info->nodesize, 1, 0);
 3359             if (ret)
 3360                 goto out;
 3361         }
 3362         path.slots[0]++;
 3363     }
 3364     btrfs_set_super_bytes_used(root->fs_info->super_copy, bytes_used);
 3365     ret = 0;
 3366 out:
 3367     btrfs_release_path(&path);
 3368     return ret;
 3369 }
 3370 
 3371 static void __get_extent_size(struct btrfs_root *root, struct btrfs_path *path,
 3372                   u64 *start, u64 *len)
 3373 {
 3374     struct btrfs_key key;
 3375 
 3376     btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
 3377     BUG_ON(!(key.type == BTRFS_EXTENT_ITEM_KEY ||
 3378          key.type == BTRFS_METADATA_ITEM_KEY));
 3379     *start = key.objectid;
 3380     if (key.type == BTRFS_EXTENT_ITEM_KEY)
 3381         *len = key.offset;
 3382     else
 3383         *len = root->fs_info->nodesize;
 3384 }
 3385 
 3386 /*
 3387  * Find first overlap extent for range [bytenr, bytenr + len)
 3388  * Return 0 for found and point path to it.
 3389  * Return >0 for not found.
 3390  * Return <0 for err
 3391  */
 3392 static int btrfs_search_overlap_extent(struct btrfs_root *root,
 3393                 struct btrfs_path *path, u64 bytenr, u64 len)
 3394 {
 3395     struct btrfs_key key;
 3396     u64 cur_start;
 3397     u64 cur_len;
 3398     int ret;
 3399 
 3400     key.objectid = bytenr;
 3401     key.type = BTRFS_EXTENT_DATA_KEY;
 3402     key.offset = (u64)-1;
 3403 
 3404     ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 3405     if (ret < 0)
 3406         return ret;
 3407     BUG_ON(ret == 0);
 3408 
 3409     ret = btrfs_previous_extent_item(root, path, 0);
 3410     if (ret < 0)
 3411         return ret;
 3412     /* no previous, check next extent */
 3413     if (ret > 0)
 3414         goto next;
 3415     __get_extent_size(root, path, &cur_start, &cur_len);
 3416     /* Tail overlap */
 3417     if (cur_start + cur_len > bytenr)
 3418         return 1;
 3419 
 3420 next:
 3421     ret = btrfs_next_extent_item(root, path, bytenr + len);
 3422     if (ret < 0)
 3423         return ret;
 3424     /* No next, prev already checked, no overlap */
 3425     if (ret > 0)
 3426         return 0;
 3427     __get_extent_size(root, path, &cur_start, &cur_len);
 3428     /* head overlap*/
 3429     if (cur_start < bytenr + len)
 3430         return 1;
 3431     return 0;
 3432 }
 3433 
 3434 static int __btrfs_record_file_extent(struct btrfs_trans_handle *trans,
 3435                       struct btrfs_root *root, u64 objectid,
 3436                       struct btrfs_inode_item *inode,
 3437                       u64 file_pos, u64 disk_bytenr,
 3438                       u64 *ret_num_bytes)
 3439 {
 3440     int ret;
 3441     struct btrfs_fs_info *info = root->fs_info;
 3442     struct btrfs_root *extent_root = info->extent_root;
 3443     struct extent_buffer *leaf;
 3444     struct btrfs_file_extent_item *fi;
 3445     struct btrfs_key ins_key;
 3446     struct btrfs_path *path;
 3447     struct btrfs_extent_item *ei;
 3448     u64 nbytes;
 3449     u64 extent_num_bytes;
 3450     u64 extent_bytenr;
 3451     u64 extent_offset;
 3452     u64 num_bytes = *ret_num_bytes;
 3453 
 3454     /*
 3455      * All supported file system should not use its 0 extent.
 3456      * As it's for hole
 3457      *
 3458      * And hole extent has no size limit, no need to loop.
 3459      */
 3460     if (disk_bytenr == 0) {
 3461         ret = btrfs_insert_file_extent(trans, root, objectid,
 3462                         file_pos, disk_bytenr,
 3463                         num_bytes, num_bytes);
 3464         return ret;
 3465     }
 3466     num_bytes = min_t(u64, num_bytes, BTRFS_MAX_EXTENT_SIZE);
 3467 
 3468     path = btrfs_alloc_path();
 3469     if (!path)
 3470         return -ENOMEM;
 3471 
 3472     /* First to check extent overlap */
 3473     ret = btrfs_search_overlap_extent(extent_root, path, disk_bytenr,
 3474                       num_bytes);
 3475     if (ret < 0)
 3476         goto fail;
 3477     if (ret > 0) {
 3478         /* Found overlap */
 3479         u64 cur_start;
 3480         u64 cur_len;
 3481 
 3482         __get_extent_size(extent_root, path, &cur_start, &cur_len);
 3483         /*
 3484          * For convert case, this extent should be a subset of
 3485          * existing one.
 3486          */
 3487         BUG_ON(disk_bytenr < cur_start);
 3488 
 3489         extent_bytenr = cur_start;
 3490         extent_num_bytes = cur_len;
 3491         extent_offset = disk_bytenr - extent_bytenr;
 3492     } else {
 3493         /* No overlap, create new extent */
 3494         btrfs_release_path(path);
 3495         ins_key.objectid = disk_bytenr;
 3496         ins_key.offset = num_bytes;
 3497         ins_key.type = BTRFS_EXTENT_ITEM_KEY;
 3498 
 3499         ret = btrfs_insert_empty_item(trans, extent_root, path,
 3500                           &ins_key, sizeof(*ei));
 3501         if (ret == 0) {
 3502             leaf = path->nodes[0];
 3503             ei = btrfs_item_ptr(leaf, path->slots[0],
 3504                         struct btrfs_extent_item);
 3505 
 3506             btrfs_set_extent_refs(leaf, ei, 0);
 3507             btrfs_set_extent_generation(leaf, ei, 0);
 3508             btrfs_set_extent_flags(leaf, ei,
 3509                            BTRFS_EXTENT_FLAG_DATA);
 3510             btrfs_mark_buffer_dirty(leaf);
 3511 
 3512             ret = btrfs_update_block_group(root, disk_bytenr,
 3513                                num_bytes, 1, 0);
 3514             if (ret)
 3515                 goto fail;
 3516         } else if (ret != -EEXIST) {
 3517             goto fail;
 3518         }
 3519         btrfs_run_delayed_refs(trans, -1);
 3520         extent_bytenr = disk_bytenr;
 3521         extent_num_bytes = num_bytes;
 3522         extent_offset = 0;
 3523     }
 3524     btrfs_release_path(path);
 3525     ins_key.objectid = objectid;
 3526     ins_key.offset = file_pos;
 3527     ins_key.type = BTRFS_EXTENT_DATA_KEY;
 3528     ret = btrfs_insert_empty_item(trans, root, path, &ins_key,
 3529                       sizeof(*fi));
 3530     if (ret)
 3531         goto fail;
 3532     leaf = path->nodes[0];
 3533     fi = btrfs_item_ptr(leaf, path->slots[0],
 3534                 struct btrfs_file_extent_item);
 3535     btrfs_set_file_extent_generation(leaf, fi, trans->transid);
 3536     btrfs_set_file_extent_type(leaf, fi, BTRFS_FILE_EXTENT_REG);
 3537     btrfs_set_file_extent_disk_bytenr(leaf, fi, extent_bytenr);
 3538     btrfs_set_file_extent_disk_num_bytes(leaf, fi, extent_num_bytes);
 3539     btrfs_set_file_extent_offset(leaf, fi, extent_offset);
 3540     btrfs_set_file_extent_num_bytes(leaf, fi, num_bytes);
 3541     btrfs_set_file_extent_ram_bytes(leaf, fi, extent_num_bytes);
 3542     btrfs_set_file_extent_compression(leaf, fi, 0);
 3543     btrfs_set_file_extent_encryption(leaf, fi, 0);
 3544     btrfs_set_file_extent_other_encoding(leaf, fi, 0);
 3545     btrfs_mark_buffer_dirty(leaf);
 3546 
 3547     nbytes = btrfs_stack_inode_nbytes(inode) + num_bytes;
 3548     btrfs_set_stack_inode_nbytes(inode, nbytes);
 3549     btrfs_release_path(path);
 3550 
 3551     ret = btrfs_inc_extent_ref(trans, root, extent_bytenr, extent_num_bytes,
 3552                    0, root->root_key.objectid, objectid,
 3553                    file_pos - extent_offset);
 3554     if (ret)
 3555         goto fail;
 3556     ret = 0;
 3557     *ret_num_bytes = min(extent_num_bytes - extent_offset, num_bytes);
 3558 fail:
 3559     btrfs_free_path(path);
 3560     return ret;
 3561 }
 3562 
 3563 /*
 3564  * Record a file extent. Do all the required works, such as inserting
 3565  * file extent item, inserting extent item and backref item into extent
 3566  * tree and updating block accounting.
 3567  */
 3568 int btrfs_record_file_extent(struct btrfs_trans_handle *trans,
 3569                   struct btrfs_root *root, u64 objectid,
 3570                   struct btrfs_inode_item *inode,
 3571                   u64 file_pos, u64 disk_bytenr,
 3572                   u64 num_bytes)
 3573 {
 3574     u64 cur_disk_bytenr = disk_bytenr;
 3575     u64 cur_file_pos = file_pos;
 3576     u64 cur_num_bytes = num_bytes;
 3577     int ret = 0;
 3578 
 3579     while (num_bytes > 0) {
 3580         ret = __btrfs_record_file_extent(trans, root, objectid,
 3581                          inode, cur_file_pos,
 3582                          cur_disk_bytenr,
 3583                          &cur_num_bytes);
 3584         if (ret < 0)
 3585             break;
 3586         cur_disk_bytenr += cur_num_bytes;
 3587         cur_file_pos += cur_num_bytes;
 3588         num_bytes -= cur_num_bytes;
 3589     }
 3590     return ret;
 3591 }
 3592 
 3593 
 3594 static int add_excluded_extent(struct btrfs_fs_info *fs_info,
 3595                    u64 start, u64 num_bytes)
 3596 {
 3597     u64 end = start + num_bytes - 1;
 3598     set_extent_bits(&fs_info->pinned_extents,
 3599             start, end, EXTENT_UPTODATE);
 3600     return 0;
 3601 }
 3602 
 3603 void free_excluded_extents(struct btrfs_fs_info *fs_info,
 3604                struct btrfs_block_group_cache *cache)
 3605 {
 3606     u64 start, end;
 3607 
 3608     start = cache->key.objectid;
 3609     end = start + cache->key.offset - 1;
 3610 
 3611     clear_extent_bits(&fs_info->pinned_extents,
 3612               start, end, EXTENT_UPTODATE);
 3613 }
 3614 
 3615 int exclude_super_stripes(struct btrfs_fs_info *fs_info,
 3616               struct btrfs_block_group_cache *cache)
 3617 {
 3618     u64 bytenr;
 3619     u64 *logical;
 3620     int stripe_len;
 3621     int i, nr, ret;
 3622 
 3623     if (cache->key.objectid < BTRFS_SUPER_INFO_OFFSET) {
 3624         stripe_len = BTRFS_SUPER_INFO_OFFSET - cache->key.objectid;
 3625         cache->bytes_super += stripe_len;
 3626         ret = add_excluded_extent(fs_info, cache->key.objectid,
 3627                       stripe_len);
 3628         if (ret)
 3629             return ret;
 3630     }
 3631 
 3632     for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
 3633         bytenr = btrfs_sb_offset(i);
 3634         ret = btrfs_rmap_block(fs_info,
 3635                        cache->key.objectid, bytenr,
 3636                        &logical, &nr, &stripe_len);
 3637         if (ret)
 3638             return ret;
 3639 
 3640         while (nr--) {
 3641             u64 start, len;
 3642 
 3643             if (logical[nr] >= cache->key.objectid +
 3644                 cache->key.offset)
 3645                 continue;
 3646 
 3647             if (logical[nr] + stripe_len <= cache->key.objectid)
 3648                 continue;
 3649 
 3650             start = logical[nr];
 3651             if (start < cache->key.objectid) {
 3652                 start = cache->key.objectid;
 3653                 len = (logical[nr] + stripe_len) - start;
 3654             } else {
 3655                 len = min_t(u64, stripe_len,
 3656                         cache->key.objectid +
 3657                         cache->key.offset - start);
 3658             }
 3659 
 3660             cache->bytes_super += len;
 3661             ret = add_excluded_extent(fs_info, start, len);
 3662             if (ret) {
 3663                 kfree(logical);
 3664                 return ret;
 3665             }
 3666         }
 3667 
 3668         kfree(logical);
 3669     }
 3670     return 0;
 3671 }
 3672 
 3673 u64 add_new_free_space(struct btrfs_block_group_cache *block_group,
 3674                struct btrfs_fs_info *info, u64 start, u64 end)
 3675 {
 3676     u64 extent_start, extent_end, size, total_added = 0;
 3677     int ret;
 3678 
 3679     while (start < end) {
 3680         ret = find_first_extent_bit(&info->pinned_extents, start,
 3681                         &extent_start, &extent_end,
 3682                         EXTENT_DIRTY | EXTENT_UPTODATE);
 3683         if (ret)
 3684             break;
 3685 
 3686         if (extent_start <= start) {
 3687             start = extent_end + 1;
 3688         } else if (extent_start > start && extent_start < end) {
 3689             size = extent_start - start;
 3690             total_added += size;
 3691             ret = btrfs_add_free_space(block_group->free_space_ctl,
 3692                            start, size);
 3693             BUG_ON(ret); /* -ENOMEM or logic error */
 3694             start = extent_end + 1;
 3695         } else {
 3696             break;
 3697         }
 3698     }
 3699 
 3700     if (start < end) {
 3701         size = end - start;
 3702         total_added += size;
 3703         ret = btrfs_add_free_space(block_group->free_space_ctl, start,
 3704                        size);
 3705         BUG_ON(ret); /* -ENOMEM or logic error */
 3706     }
 3707 
 3708     return total_added;
 3709 }
 3710 
 3711 static void cleanup_extent_op(struct btrfs_trans_handle *trans,
 3712                  struct btrfs_fs_info *fs_info,
 3713                  struct btrfs_delayed_ref_head *head)
 3714 {
 3715     struct btrfs_delayed_extent_op *extent_op = head->extent_op;
 3716 
 3717     if (!extent_op)
 3718         return;
 3719     head->extent_op = NULL;
 3720     btrfs_free_delayed_extent_op(extent_op);
 3721 }
 3722 
 3723 static void unselect_delayed_ref_head(struct btrfs_delayed_ref_root *delayed_refs,
 3724                       struct btrfs_delayed_ref_head *head)
 3725 {
 3726     head->processing = 0;
 3727     delayed_refs->num_heads_ready++;
 3728 }
 3729 
 3730 int cleanup_ref_head(struct btrfs_trans_handle *trans,
 3731              struct btrfs_fs_info *fs_info,
 3732              struct btrfs_delayed_ref_head *head)
 3733 {
 3734     struct btrfs_delayed_ref_root *delayed_refs;
 3735 
 3736     delayed_refs = &trans->delayed_refs;
 3737 
 3738     cleanup_extent_op(trans, fs_info, head);
 3739 
 3740     /*
 3741      * Need to drop our head ref lock and re-acquire the delayed ref lock
 3742      * and then re-check to make sure nobody got added.
 3743      */
 3744     if (!RB_EMPTY_ROOT(&head->ref_tree) || head->extent_op)
 3745         return 1;
 3746 
 3747     delayed_refs->num_heads--;
 3748     rb_erase(&head->href_node, &delayed_refs->href_root);
 3749     RB_CLEAR_NODE(&head->href_node);
 3750 
 3751     if (head->must_insert_reserved) {
 3752         btrfs_pin_extent(fs_info, head->bytenr, head->num_bytes);
 3753         if (!head->is_data) {
 3754             struct btrfs_space_info *sinfo;
 3755 
 3756             sinfo = __find_space_info(trans->fs_info,
 3757                     BTRFS_BLOCK_GROUP_METADATA);
 3758             ASSERT(sinfo);
 3759             sinfo->bytes_reserved -= head->num_bytes;
 3760         }
 3761     }
 3762 
 3763     btrfs_put_delayed_ref_head(head);
 3764     return 0;
 3765 }
 3766 
 3767 static inline struct btrfs_delayed_ref_node *
 3768 select_delayed_ref(struct btrfs_delayed_ref_head *head)
 3769 {
 3770     struct btrfs_delayed_ref_node *ref;
 3771 
 3772     if (RB_EMPTY_ROOT(&head->ref_tree))
 3773         return NULL;
 3774     /*
 3775      * Select a delayed ref of type BTRFS_ADD_DELAYED_REF first.
 3776      * This is to prevent a ref count from going down to zero, which deletes
 3777      * the extent item from the extent tree, when there still are references
 3778      * to add, which would fail because they would not find the extent item.
 3779      */
 3780     if (!list_empty(&head->ref_add_list))
 3781         return list_first_entry(&head->ref_add_list,
 3782                     struct btrfs_delayed_ref_node,
 3783                     add_list);
 3784     ref = rb_entry(rb_first(&head->ref_tree),
 3785                struct btrfs_delayed_ref_node, ref_node);
 3786     ASSERT(list_empty(&ref->add_list));
 3787     return ref;
 3788 }
 3789 
 3790 
 3791 static int run_delayed_tree_ref(struct btrfs_trans_handle *trans,
 3792                 struct btrfs_fs_info *fs_info,
 3793                 struct btrfs_delayed_ref_node *node,
 3794                 struct btrfs_delayed_extent_op *extent_op,
 3795                 int insert_reserved)
 3796 {
 3797     int ret = 0;
 3798     struct btrfs_delayed_tree_ref *ref;
 3799     u64 parent = 0;
 3800     u64 ref_root = 0;
 3801 
 3802     ref = btrfs_delayed_node_to_tree_ref(node);
 3803 
 3804     if (node->type == BTRFS_SHARED_BLOCK_REF_KEY)
 3805             parent = ref->parent;
 3806     ref_root = ref->root;
 3807 
 3808     if (node->ref_mod != 1) {
 3809         printf("btree block(%llu) has %d references rather than 1: action %u ref_root %llu parent %llu",
 3810             node->bytenr, node->ref_mod, node->action, ref_root,
 3811             parent);
 3812         return -EIO;
 3813     }
 3814     if (node->action == BTRFS_ADD_DELAYED_REF && insert_reserved) {
 3815         BUG_ON(!extent_op || !extent_op->update_flags);
 3816         ret = alloc_reserved_tree_block(trans, node, extent_op);
 3817     } else if (node->action == BTRFS_DROP_DELAYED_REF) {
 3818         struct btrfs_delayed_tree_ref *ref = btrfs_delayed_node_to_tree_ref(node);
 3819         ret =  __free_extent(trans, node->bytenr, node->num_bytes,
 3820                  ref->parent, ref->root, ref->level, 0, 1);
 3821     } else {
 3822         BUG();
 3823     }
 3824 
 3825     return ret;
 3826 }
 3827 
 3828 /* helper function to actually process a single delayed ref entry */
 3829 static int run_one_delayed_ref(struct btrfs_trans_handle *trans,
 3830                    struct btrfs_fs_info *fs_info,
 3831                    struct btrfs_delayed_ref_node *node,
 3832                    struct btrfs_delayed_extent_op *extent_op,
 3833                    int insert_reserved)
 3834 {
 3835     int ret = 0;
 3836 
 3837     if (node->type == BTRFS_TREE_BLOCK_REF_KEY ||
 3838         node->type == BTRFS_SHARED_BLOCK_REF_KEY) {
 3839         ret = run_delayed_tree_ref(trans, fs_info, node, extent_op,
 3840                        insert_reserved);
 3841     } else
 3842         BUG();
 3843     return ret;
 3844 }
 3845 
 3846 int btrfs_run_delayed_refs(struct btrfs_trans_handle *trans, unsigned long nr)
 3847 {
 3848     struct btrfs_fs_info *fs_info = trans->fs_info;
 3849     struct btrfs_delayed_ref_root *delayed_refs;
 3850     struct btrfs_delayed_ref_node *ref;
 3851     struct btrfs_delayed_ref_head *locked_ref = NULL;
 3852     struct btrfs_delayed_extent_op *extent_op;
 3853     int ret;
 3854     int must_insert_reserved = 0;
 3855 
 3856     delayed_refs = &trans->delayed_refs;
 3857     while (1) {
 3858         if (!locked_ref) {
 3859             locked_ref = btrfs_select_ref_head(trans);
 3860             if (!locked_ref)
 3861                 break;
 3862         }
 3863         /*
 3864          * We need to try and merge add/drops of the same ref since we
 3865          * can run into issues with relocate dropping the implicit ref
 3866          * and then it being added back again before the drop can
 3867          * finish.  If we merged anything we need to re-loop so we can
 3868          * get a good ref.
 3869          * Or we can get node references of the same type that weren't
 3870          * merged when created due to bumps in the tree mod seq, and
 3871          * we need to merge them to prevent adding an inline extent
 3872          * backref before dropping it (triggering a BUG_ON at
 3873          * insert_inline_extent_backref()).
 3874          */
 3875         btrfs_merge_delayed_refs(trans, delayed_refs, locked_ref);
 3876         ref = select_delayed_ref(locked_ref);
 3877         /*
 3878          * We're done processing refs in this ref_head, clean everything
 3879          * up and move on to the next ref_head.
 3880          */
 3881         if (!ref) {
 3882             ret = cleanup_ref_head(trans, fs_info, locked_ref);
 3883             if (ret > 0 ) {
 3884                 /* We dropped our lock, we need to loop. */
 3885                 ret = 0;
 3886                 continue;
 3887             }
 3888             locked_ref = NULL;
 3889             continue;
 3890         }
 3891 
 3892         ref->in_tree = 0;
 3893         rb_erase(&ref->ref_node, &locked_ref->ref_tree);
 3894         RB_CLEAR_NODE(&ref->ref_node);
 3895         if (!list_empty(&ref->add_list))
 3896                 list_del(&ref->add_list);
 3897         /*
 3898          * When we play the delayed ref, also correct the ref_mod on
 3899          * head
 3900          */
 3901         switch (ref->action) {
 3902         case BTRFS_ADD_DELAYED_REF:
 3903         case BTRFS_ADD_DELAYED_EXTENT:
 3904             locked_ref->ref_mod -= ref->ref_mod;
 3905             break;
 3906         case BTRFS_DROP_DELAYED_REF:
 3907             locked_ref->ref_mod += ref->ref_mod;
 3908             break;
 3909         default:
 3910             WARN_ON(1);
 3911         }
 3912 
 3913         /*
 3914          * Record the must-insert_reserved flag before we drop the spin
 3915          * lock.
 3916          */
 3917         must_insert_reserved = locked_ref->must_insert_reserved;
 3918         locked_ref->must_insert_reserved = 0;
 3919 
 3920         extent_op = locked_ref->extent_op;
 3921         locked_ref->extent_op = NULL;
 3922 
 3923         ret = run_one_delayed_ref(trans, fs_info, ref, extent_op,
 3924                       must_insert_reserved);
 3925 
 3926         btrfs_free_delayed_extent_op(extent_op);
 3927         /*
 3928          * If we are re-initing extent tree in this transaction
 3929          * failure in freeing old roots are expected (because we don't
 3930          * have the old extent tree, hence backref resolution will
 3931          * return -EIO).
 3932          */
 3933         if (ret && (!trans->reinit_extent_tree ||
 3934              ref->action != BTRFS_DROP_DELAYED_REF)) {
 3935             unselect_delayed_ref_head(delayed_refs, locked_ref);
 3936             btrfs_put_delayed_ref(ref);
 3937             return ret;
 3938         }
 3939 
 3940         btrfs_put_delayed_ref(ref);
 3941     }
 3942 
 3943     return 0;
 3944 }