"Fossies" - the Fresh Open Source Software Archive

Member "btrfs-progs-v5.4.1/check/mode-lowmem.c" (9 Jan 2020, 142906 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 "mode-lowmem.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  * This program is free software; you can redistribute it and/or
    3  * modify it under the terms of the GNU General Public
    4  * License v2 as published by the Free Software Foundation.
    5  *
    6  * This program is distributed in the hope that it will be useful,
    7  * but WITHOUT ANY WARRANTY; without even the implied warranty of
    8  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    9  * General Public License for more details.
   10  *
   11  * You should have received a copy of the GNU General Public
   12  * License along with this program; if not, write to the
   13  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   14  * Boston, MA 021110-1307, USA.
   15  */
   16 
   17 #include <time.h>
   18 #include "ctree.h"
   19 #include "repair.h"
   20 #include "transaction.h"
   21 #include "common/messages.h"
   22 #include "disk-io.h"
   23 #include "backref.h"
   24 #include "hash.h"
   25 #include "common/internal.h"
   26 #include "common/utils.h"
   27 #include "volumes.h"
   28 #include "check/mode-common.h"
   29 #include "check/mode-lowmem.h"
   30 
   31 static u64 last_allocated_chunk;
   32 
   33 static int calc_extent_flag(struct btrfs_root *root, struct extent_buffer *eb,
   34                 u64 *flags_ret)
   35 {
   36     struct btrfs_root *extent_root = root->fs_info->extent_root;
   37     struct btrfs_root_item *ri = &root->root_item;
   38     struct btrfs_extent_inline_ref *iref;
   39     struct btrfs_extent_item *ei;
   40     struct btrfs_key key;
   41     struct btrfs_path *path = NULL;
   42     unsigned long ptr;
   43     unsigned long end;
   44     u64 flags;
   45     u64 owner = 0;
   46     u64 offset;
   47     int slot;
   48     int type;
   49     int ret = 0;
   50 
   51     /*
   52      * Except file/reloc tree, we can not have FULL BACKREF MODE
   53      */
   54     if (root->objectid < BTRFS_FIRST_FREE_OBJECTID)
   55         goto normal;
   56 
   57     /* root node */
   58     if (eb->start == btrfs_root_bytenr(ri))
   59         goto normal;
   60 
   61     if (btrfs_header_flag(eb, BTRFS_HEADER_FLAG_RELOC))
   62         goto full_backref;
   63 
   64     owner = btrfs_header_owner(eb);
   65     if (owner == root->objectid)
   66         goto normal;
   67 
   68     path = btrfs_alloc_path();
   69     if (!path)
   70         return -ENOMEM;
   71 
   72     key.objectid = btrfs_header_bytenr(eb);
   73     key.type = (u8)-1;
   74     key.offset = (u64)-1;
   75 
   76     ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
   77     if (ret <= 0) {
   78         ret = -EIO;
   79         goto out;
   80     }
   81 
   82     if (ret > 0) {
   83         ret = btrfs_previous_extent_item(extent_root, path,
   84                          key.objectid);
   85         if (ret)
   86             goto full_backref;
   87 
   88     }
   89     btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
   90 
   91     eb = path->nodes[0];
   92     slot = path->slots[0];
   93     ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
   94 
   95     flags = btrfs_extent_flags(eb, ei);
   96     if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)
   97         goto full_backref;
   98 
   99     ptr = (unsigned long)(ei + 1);
  100     end = (unsigned long)ei + btrfs_item_size_nr(eb, slot);
  101 
  102     if (key.type == BTRFS_EXTENT_ITEM_KEY)
  103         ptr += sizeof(struct btrfs_tree_block_info);
  104 
  105 next:
  106     /* Reached extent item ends normally */
  107     if (ptr == end)
  108         goto full_backref;
  109 
  110     /* Beyond extent item end, wrong item size */
  111     if (ptr > end) {
  112         error("extent item at bytenr %llu slot %d has wrong size",
  113             eb->start, slot);
  114         goto full_backref;
  115     }
  116 
  117     iref = (struct btrfs_extent_inline_ref *)ptr;
  118     offset = btrfs_extent_inline_ref_offset(eb, iref);
  119     type = btrfs_extent_inline_ref_type(eb, iref);
  120 
  121     if (type == BTRFS_TREE_BLOCK_REF_KEY && offset == owner)
  122         goto normal;
  123     ptr += btrfs_extent_inline_ref_size(type);
  124     goto next;
  125 
  126 normal:
  127     *flags_ret &= ~BTRFS_BLOCK_FLAG_FULL_BACKREF;
  128     goto out;
  129 
  130 full_backref:
  131     *flags_ret |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
  132 out:
  133     btrfs_free_path(path);
  134     return ret;
  135 }
  136 
  137 /*
  138  * for a tree node or leaf, if it's shared, indeed we don't need to iterate it
  139  * in every fs or file tree check. Here we find its all root ids, and only check
  140  * it in the fs or file tree which has the smallest root id.
  141  */
  142 static int need_check(struct btrfs_root *root, struct ulist *roots)
  143 {
  144     struct rb_node *node;
  145     struct ulist_node *u;
  146 
  147     /*
  148      * @roots can be empty if it belongs to tree reloc tree
  149      * In that case, we should always check the leaf, as we can't use
  150      * the tree owner to ensure some other root will check it.
  151      */
  152     if (roots->nnodes == 1 || roots->nnodes == 0)
  153         return 1;
  154 
  155     node = rb_first(&roots->root);
  156     u = rb_entry(node, struct ulist_node, rb_node);
  157     /*
  158      * current root id is not smallest, we skip it and let it be checked
  159      * in the fs or file tree who hash the smallest root id.
  160      */
  161     if (root->objectid != u->val)
  162         return 0;
  163 
  164     return 1;
  165 }
  166 
  167 /*
  168  * for a tree node or leaf, we record its reference count, so later if we still
  169  * process this node or leaf, don't need to compute its reference count again.
  170  *
  171  * @bytenr  if @bytenr == (u64)-1, only update nrefs->full_backref[level]
  172  */
  173 static int update_nodes_refs(struct btrfs_root *root, u64 bytenr,
  174                  struct extent_buffer *eb, struct node_refs *nrefs,
  175                  u64 level, int check_all)
  176 {
  177     struct ulist *roots;
  178     u64 refs = 0;
  179     u64 flags = 0;
  180     int root_level = btrfs_header_level(root->node);
  181     int check;
  182     int ret;
  183 
  184     if (nrefs->bytenr[level] == bytenr)
  185         return 0;
  186 
  187     if (bytenr != (u64)-1) {
  188         /* the return value of this function seems a mistake */
  189         ret = btrfs_lookup_extent_info(NULL, root->fs_info, bytenr,
  190                            level, 1, &refs, &flags);
  191         /* temporary fix */
  192         if (ret < 0 && !check_all)
  193             return ret;
  194 
  195         nrefs->bytenr[level] = bytenr;
  196         nrefs->refs[level] = refs;
  197         nrefs->full_backref[level] = 0;
  198         nrefs->checked[level] = 0;
  199 
  200         if (refs > 1) {
  201             ret = btrfs_find_all_roots(NULL, root->fs_info, bytenr,
  202                            0, &roots);
  203             if (ret)
  204                 return -EIO;
  205 
  206             check = need_check(root, roots);
  207             ulist_free(roots);
  208             nrefs->need_check[level] = check;
  209         } else {
  210             if (!check_all) {
  211                 nrefs->need_check[level] = 1;
  212             } else {
  213                 if (level == root_level) {
  214                     nrefs->need_check[level] = 1;
  215                 } else {
  216                     /*
  217                      * The node refs may have not been
  218                      * updated if upper needs checking (the
  219                      * lowest root_objectid) the node can
  220                      * be checked.
  221                      */
  222                     nrefs->need_check[level] =
  223                         nrefs->need_check[level + 1];
  224                 }
  225             }
  226         }
  227     }
  228 
  229     if (check_all && eb) {
  230         calc_extent_flag(root, eb, &flags);
  231         if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)
  232             nrefs->full_backref[level] = 1;
  233     }
  234 
  235     return 0;
  236 }
  237 
  238 /*
  239  * Mark all extents unfree in the block group. And set @block_group->cached
  240  * according to @cache.
  241  */
  242 static int modify_block_group_cache(struct btrfs_fs_info *fs_info,
  243             struct btrfs_block_group_cache *block_group, int cache)
  244 {
  245     struct extent_io_tree *free_space_cache = &fs_info->free_space_cache;
  246     u64 start = block_group->key.objectid;
  247     u64 end = start + block_group->key.offset;
  248 
  249     if (cache && !block_group->cached) {
  250         block_group->cached = 1;
  251         clear_extent_dirty(free_space_cache, start, end - 1);
  252     }
  253 
  254     if (!cache && block_group->cached) {
  255         block_group->cached = 0;
  256         clear_extent_dirty(free_space_cache, start, end - 1);
  257     }
  258     return 0;
  259 }
  260 
  261 /*
  262  * Modify block groups which have @flags unfree in free space cache.
  263  *
  264  * @cache: if 0, clear block groups cache state;
  265  *         not 0, mark blocks groups cached.
  266  */
  267 static int modify_block_groups_cache(struct btrfs_fs_info *fs_info, u64 flags,
  268                      int cache)
  269 {
  270     struct btrfs_root *root = fs_info->extent_root;
  271     struct btrfs_key key;
  272     struct btrfs_path path;
  273     struct btrfs_block_group_cache *bg_cache;
  274     struct btrfs_block_group_item *bi;
  275     struct btrfs_block_group_item bg_item;
  276     struct extent_buffer *eb;
  277     int slot;
  278     int ret;
  279 
  280     key.objectid = 0;
  281     key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
  282     key.offset = 0;
  283 
  284     btrfs_init_path(&path);
  285     ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
  286     if (ret < 0) {
  287         errno = -ret;
  288         error("fail to search block groups due to %m");
  289         goto out;
  290     }
  291 
  292     while (1) {
  293         eb = path.nodes[0];
  294         slot = path.slots[0];
  295         btrfs_item_key_to_cpu(eb, &key, slot);
  296         bg_cache = btrfs_lookup_block_group(fs_info, key.objectid);
  297         if (!bg_cache) {
  298             ret = -ENOENT;
  299             goto out;
  300         }
  301 
  302         bi = btrfs_item_ptr(eb, slot, struct btrfs_block_group_item);
  303         read_extent_buffer(eb, &bg_item, (unsigned long)bi,
  304                    sizeof(bg_item));
  305         if (btrfs_block_group_flags(&bg_item) & flags)
  306             modify_block_group_cache(fs_info, bg_cache, cache);
  307 
  308         ret = btrfs_next_item(root, &path);
  309         if (ret > 0) {
  310             ret = 0;
  311             goto out;
  312         }
  313         if (ret < 0)
  314             goto out;
  315     }
  316 
  317 out:
  318     btrfs_release_path(&path);
  319     return ret;
  320 }
  321 
  322 static int mark_block_groups_full(struct btrfs_fs_info *fs_info, u64 flags)
  323 {
  324     return modify_block_groups_cache(fs_info, flags, 1);
  325 }
  326 
  327 static int clear_block_groups_full(struct btrfs_fs_info *fs_info, u64 flags)
  328 {
  329     return modify_block_groups_cache(fs_info, flags, 0);
  330 }
  331 
  332 static int create_chunk_and_block_group(struct btrfs_fs_info *fs_info,
  333                     u64 flags, u64 *start, u64 *nbytes)
  334 {
  335     struct btrfs_trans_handle *trans;
  336     struct btrfs_root *root = fs_info->extent_root;
  337     int ret;
  338 
  339     if ((flags & BTRFS_BLOCK_GROUP_TYPE_MASK) == 0)
  340         return -EINVAL;
  341 
  342     trans = btrfs_start_transaction(root, 1);
  343     if (IS_ERR(trans)) {
  344         ret = PTR_ERR(trans);
  345         errno = -ret;
  346         error("error starting transaction %m");
  347         return ret;
  348     }
  349     ret = btrfs_alloc_chunk(trans, fs_info, start, nbytes, flags);
  350     if (ret) {
  351         errno = -ret;
  352         error("fail to allocate new chunk %m");
  353         goto out;
  354     }
  355     ret = btrfs_make_block_group(trans, fs_info, 0, flags, *start,
  356                      *nbytes);
  357     if (ret) {
  358         errno = -ret;
  359         error("fail to make block group for chunk %llu %llu %m",
  360               *start, *nbytes);
  361         goto out;
  362     }
  363 out:
  364     btrfs_commit_transaction(trans, root);
  365     return ret;
  366 }
  367 
  368 static int force_cow_in_new_chunk(struct btrfs_fs_info *fs_info,
  369                   u64 *start_ret)
  370 {
  371     struct btrfs_block_group_cache *bg;
  372     u64 start;
  373     u64 nbytes;
  374     u64 alloc_profile;
  375     u64 flags;
  376     int ret;
  377 
  378     alloc_profile = (fs_info->avail_metadata_alloc_bits &
  379              fs_info->metadata_alloc_profile);
  380     flags = BTRFS_BLOCK_GROUP_METADATA | alloc_profile;
  381     if (btrfs_fs_incompat(fs_info, MIXED_GROUPS))
  382         flags |= BTRFS_BLOCK_GROUP_DATA;
  383 
  384     ret = create_chunk_and_block_group(fs_info, flags, &start, &nbytes);
  385     if (ret)
  386         goto err;
  387     printf("Created new chunk [%llu %llu]\n", start, nbytes);
  388 
  389     flags = BTRFS_BLOCK_GROUP_METADATA;
  390     /* Mark all metadata block groups cached and full in free space*/
  391     ret = mark_block_groups_full(fs_info, flags);
  392     if (ret)
  393         goto clear_bgs_full;
  394 
  395     bg = btrfs_lookup_block_group(fs_info, start);
  396     if (!bg) {
  397         ret = -ENOENT;
  398         error("fail to look up block group %llu %llu", start, nbytes);
  399         goto clear_bgs_full;
  400     }
  401 
  402     /* Clear block group cache just allocated */
  403     ret = modify_block_group_cache(fs_info, bg, 0);
  404     if (ret)
  405         goto clear_bgs_full;
  406     if (start_ret)
  407         *start_ret = start;
  408     return 0;
  409 
  410 clear_bgs_full:
  411     clear_block_groups_full(fs_info, flags);
  412 err:
  413     return ret;
  414 }
  415 
  416 /*
  417  * Returns 0 means not almost full.
  418  * Returns >0 means almost full.
  419  * Returns <0 means fatal error.
  420  */
  421 static int is_chunk_almost_full(struct btrfs_fs_info *fs_info, u64 start)
  422 {
  423     struct btrfs_path path;
  424     struct btrfs_key key;
  425     struct btrfs_root *root = fs_info->extent_root;
  426     struct btrfs_block_group_item *bi;
  427     struct btrfs_block_group_item bg_item;
  428     struct extent_buffer *eb;
  429     u64 used;
  430     u64 total;
  431     u64 min_free;
  432     int ret;
  433     int slot;
  434 
  435     key.objectid = start;
  436     key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
  437     key.offset = (u64)-1;
  438 
  439     btrfs_init_path(&path);
  440     ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
  441     if (!ret)
  442         ret = -EIO;
  443     if (ret < 0)
  444         goto out;
  445     ret = btrfs_previous_item(root, &path, start,
  446                   BTRFS_BLOCK_GROUP_ITEM_KEY);
  447     if (ret) {
  448         error("failed to find block group %llu", start);
  449         ret = -ENOENT;
  450         goto out;
  451     }
  452 
  453     eb = path.nodes[0];
  454     slot = path.slots[0];
  455     btrfs_item_key_to_cpu(eb, &key, slot);
  456     if (key.objectid != start) {
  457         ret = -ENOENT;
  458         goto out;
  459     }
  460 
  461     total = key.offset;
  462     bi = btrfs_item_ptr(eb, slot, struct btrfs_block_group_item);
  463     read_extent_buffer(eb, &bg_item, (unsigned long)bi, sizeof(bg_item));
  464     used = btrfs_block_group_used(&bg_item);
  465 
  466     /*
  467      * if the free space in the chunk is less than %10 of total,
  468      * or not not enough for CoW once, we think the chunk is almost full.
  469      */
  470     min_free = max_t(u64, (BTRFS_MAX_LEVEL + 1) * fs_info->nodesize,
  471              div_factor(total, 1));
  472 
  473     if ((total - used) > min_free)
  474         ret = 0;
  475     else
  476         ret = 1;
  477 out:
  478     btrfs_release_path(&path);
  479     return ret;
  480 }
  481 
  482 /*
  483  * Returns <0 for error.
  484  * Returns 0 for success.
  485  */
  486 static int try_to_force_cow_in_new_chunk(struct btrfs_fs_info *fs_info,
  487                     u64 old_start, u64 *new_start)
  488 {
  489     int ret;
  490 
  491     if (old_start) {
  492         ret = is_chunk_almost_full(fs_info, old_start);
  493         if (ret <= 0)
  494             return ret;
  495     }
  496     ret = force_cow_in_new_chunk(fs_info, new_start);
  497     return ret;
  498 }
  499 
  500 static int avoid_extents_overwrite(struct btrfs_fs_info *fs_info)
  501 {
  502     int ret;
  503     int mixed = btrfs_fs_incompat(fs_info, MIXED_GROUPS);
  504 
  505     if (fs_info->excluded_extents)
  506         return 0;
  507 
  508     if (last_allocated_chunk != (u64)-1) {
  509         ret = try_to_force_cow_in_new_chunk(fs_info,
  510             last_allocated_chunk, &last_allocated_chunk);
  511         if (!ret)
  512             goto out;
  513         /*
  514          * If failed, do not try to allocate chunk again in
  515          * next call.
  516          * If there is no space left to allocate, try to exclude all
  517          * metadata blocks. Mixed filesystem is unsupported.
  518          */
  519         last_allocated_chunk = (u64)-1;
  520         if (ret != -ENOSPC || mixed)
  521             goto out;
  522     }
  523 
  524     printf(
  525     "Try to exclude all metadata blcoks and extents, it may be slow\n");
  526     ret = exclude_metadata_blocks(fs_info);
  527 out:
  528     if (ret) {
  529         errno = -ret;
  530         error("failed to avoid extents overwrite %m");
  531     }
  532     return ret;
  533 }
  534 
  535 static int end_avoid_extents_overwrite(struct btrfs_fs_info *fs_info)
  536 {
  537     int ret = 0;
  538 
  539     cleanup_excluded_extents(fs_info);
  540     if (last_allocated_chunk)
  541         ret = clear_block_groups_full(fs_info,
  542                     BTRFS_BLOCK_GROUP_METADATA);
  543     return ret;
  544 }
  545 
  546 /*
  547  * Delete the item @path point to. A wrapper of btrfs_del_item().
  548  *
  549  * If deleted successfully, @path will point to the previous item of the
  550  * deleted item.
  551  */
  552 static int delete_item(struct btrfs_root *root, struct btrfs_path *path)
  553 {
  554     struct btrfs_key key;
  555     struct btrfs_trans_handle *trans;
  556     int ret = 0;
  557 
  558     ret = avoid_extents_overwrite(root->fs_info);
  559     if (ret)
  560         return ret;
  561     trans = btrfs_start_transaction(root, 1);
  562     if (IS_ERR(trans)) {
  563         ret = PTR_ERR(trans);
  564         error("fail to start transaction %s", strerror(-ret));
  565         goto out;
  566     }
  567     btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
  568     btrfs_release_path(path);
  569     ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
  570     if (ret) {
  571         ret = -ENOENT;
  572         goto out;
  573     }
  574 
  575     ret = btrfs_del_item(trans, root, path);
  576     if (ret)
  577         goto out;
  578 
  579     if (path->slots[0] == 0)
  580         btrfs_prev_leaf(root, path);
  581     else
  582         path->slots[0]--;
  583 out:
  584     btrfs_commit_transaction(trans, root);
  585     if (ret)
  586         error("failed to delete root %llu item[%llu, %u, %llu]",
  587               root->objectid, key.objectid, key.type, key.offset);
  588     else
  589         printf("Deleted root %llu item[%llu, %u, %llu]\n",
  590                root->objectid, key.objectid, key.type, key.offset);
  591     return ret;
  592 }
  593 
  594 /*
  595  * Wrapper function for btrfs_fix_block_accounting().
  596  *
  597  * Returns 0     on success.
  598  * Returns != 0  on error.
  599  */
  600 static int repair_block_accounting(struct btrfs_fs_info *fs_info)
  601 {
  602     struct btrfs_trans_handle *trans = NULL;
  603     struct btrfs_root *root = fs_info->extent_root;
  604     int ret;
  605 
  606     trans = btrfs_start_transaction(root, 1);
  607     if (IS_ERR(trans)) {
  608         ret = PTR_ERR(trans);
  609         errno = -ret;
  610         error("fail to start transaction: %m");
  611         return ret;
  612     }
  613 
  614     ret = btrfs_fix_block_accounting(trans);
  615     btrfs_commit_transaction(trans, root);
  616     return ret;
  617 }
  618 
  619 /*
  620  * This function only handles BACKREF_MISSING,
  621  * If corresponding extent item exists, increase the ref, else insert an extent
  622  * item and backref.
  623  *
  624  * Returns error bits after repair.
  625  */
  626 static int repair_tree_block_ref(struct btrfs_root *root,
  627                  struct extent_buffer *node,
  628                  struct node_refs *nrefs, int level, int err)
  629 {
  630     struct btrfs_trans_handle *trans = NULL;
  631     struct btrfs_fs_info *fs_info = root->fs_info;
  632     struct btrfs_root *extent_root = fs_info->extent_root;
  633     struct btrfs_path path;
  634     struct btrfs_extent_item *ei;
  635     struct btrfs_tree_block_info *bi;
  636     struct btrfs_key key;
  637     struct extent_buffer *eb;
  638     u32 size = sizeof(*ei);
  639     u32 node_size = root->fs_info->nodesize;
  640     int insert_extent = 0;
  641     int skinny_metadata = btrfs_fs_incompat(fs_info, SKINNY_METADATA);
  642     int root_level = btrfs_header_level(root->node);
  643     int generation;
  644     int ret;
  645     u64 owner;
  646     u64 bytenr;
  647     u64 flags = BTRFS_EXTENT_FLAG_TREE_BLOCK;
  648     u64 parent = 0;
  649 
  650     if ((err & BACKREF_MISSING) == 0)
  651         return err;
  652 
  653     WARN_ON(level > BTRFS_MAX_LEVEL);
  654     WARN_ON(level < 0);
  655 
  656     btrfs_init_path(&path);
  657     bytenr = btrfs_header_bytenr(node);
  658     owner = btrfs_header_owner(node);
  659     generation = btrfs_header_generation(node);
  660 
  661     key.objectid = bytenr;
  662     key.type = (u8)-1;
  663     key.offset = (u64)-1;
  664 
  665     /* Search for the extent item */
  666     ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
  667     if (ret <= 0) {
  668         ret = -EIO;
  669         goto out;
  670     }
  671 
  672     ret = btrfs_previous_extent_item(extent_root, &path, bytenr);
  673     if (ret)
  674         insert_extent = 1;
  675 
  676     /* calculate if the extent item flag is full backref or not */
  677     if (nrefs->full_backref[level] != 0)
  678         flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
  679 
  680     ret = avoid_extents_overwrite(root->fs_info);
  681     if (ret)
  682         goto out;
  683     trans = btrfs_start_transaction(extent_root, 1);
  684     if (IS_ERR(trans)) {
  685         ret = PTR_ERR(trans);
  686         trans = NULL;
  687         errno = -ret;
  688         error("fail to start transaction: %m");
  689         goto out;
  690     }
  691     /* insert an extent item */
  692     if (insert_extent) {
  693         struct btrfs_disk_key copy_key;
  694 
  695         generation = btrfs_header_generation(node);
  696 
  697         if (level < root_level && nrefs->full_backref[level + 1] &&
  698             owner != root->objectid) {
  699             flags |= BTRFS_BLOCK_FLAG_FULL_BACKREF;
  700         }
  701 
  702         key.objectid = bytenr;
  703         if (!skinny_metadata) {
  704             key.type = BTRFS_EXTENT_ITEM_KEY;
  705             key.offset = node_size;
  706             size += sizeof(*bi);
  707         } else {
  708             key.type = BTRFS_METADATA_ITEM_KEY;
  709             key.offset = level;
  710         }
  711 
  712         btrfs_release_path(&path);
  713         ret = btrfs_insert_empty_item(trans, extent_root, &path, &key,
  714                           size);
  715         if (ret)
  716             goto out;
  717 
  718         eb = path.nodes[0];
  719         ei = btrfs_item_ptr(eb, path.slots[0], struct btrfs_extent_item);
  720 
  721         btrfs_set_extent_refs(eb, ei, 0);
  722         btrfs_set_extent_generation(eb, ei, generation);
  723         btrfs_set_extent_flags(eb, ei, flags);
  724 
  725         if (!skinny_metadata) {
  726             bi = (struct btrfs_tree_block_info *)(ei + 1);
  727             memset_extent_buffer(eb, 0, (unsigned long)bi,
  728                          sizeof(*bi));
  729             btrfs_set_disk_key_objectid(&copy_key, root->objectid);
  730             btrfs_set_disk_key_type(&copy_key, 0);
  731             btrfs_set_disk_key_offset(&copy_key, 0);
  732 
  733             btrfs_set_tree_block_level(eb, bi, level);
  734             btrfs_set_tree_block_key(eb, bi, &copy_key);
  735         }
  736         btrfs_mark_buffer_dirty(eb);
  737         printf("Added an extent item [%llu %u]\n", bytenr, node_size);
  738         btrfs_update_block_group(extent_root, bytenr, node_size, 1, 0);
  739 
  740         nrefs->refs[level] = 0;
  741         nrefs->full_backref[level] =
  742             flags & BTRFS_BLOCK_FLAG_FULL_BACKREF;
  743         btrfs_release_path(&path);
  744     }
  745 
  746     if (level < root_level && nrefs->full_backref[level + 1] &&
  747         owner != root->objectid)
  748         parent = nrefs->bytenr[level + 1];
  749 
  750     /* increase the ref */
  751     ret = btrfs_inc_extent_ref(trans, extent_root, bytenr, node_size,
  752             parent, root->objectid, level, 0);
  753 
  754     nrefs->refs[level]++;
  755 out:
  756     if (trans)
  757         btrfs_commit_transaction(trans, extent_root);
  758     btrfs_release_path(&path);
  759     if (ret) {
  760         errno = -ret;
  761         error(
  762     "failed to repair tree block ref start %llu root %llu due to %m",
  763               bytenr, root->objectid);
  764     } else {
  765         printf("Added one tree block ref start %llu %s %llu\n",
  766                bytenr, parent ? "parent" : "root",
  767                parent ? parent : root->objectid);
  768         err &= ~BACKREF_MISSING;
  769     }
  770 
  771     return err;
  772 }
  773 
  774 /*
  775  * Update global fs information.
  776  */
  777 static void account_bytes(struct btrfs_root *root, struct btrfs_path *path,
  778              int level)
  779 {
  780     u32 free_nrs;
  781     struct extent_buffer *eb = path->nodes[level];
  782 
  783     total_btree_bytes += eb->len;
  784     if (fs_root_objectid(root->objectid))
  785         total_fs_tree_bytes += eb->len;
  786     if (btrfs_header_owner(eb) == BTRFS_EXTENT_TREE_OBJECTID)
  787         total_extent_tree_bytes += eb->len;
  788 
  789     if (level == 0) {
  790         btree_space_waste += btrfs_leaf_free_space(eb);
  791     } else {
  792         free_nrs = (BTRFS_NODEPTRS_PER_BLOCK(root->fs_info) -
  793                 btrfs_header_nritems(eb));
  794         btree_space_waste += free_nrs * sizeof(struct btrfs_key_ptr);
  795     }
  796 }
  797 
  798 /*
  799  * Find the @index according by @ino and name.
  800  * Notice:time efficiency is O(N)
  801  *
  802  * @root:   the root of the fs/file tree
  803  * @index_ret:  the index as return value
  804  * @namebuf:    the name to match
  805  * @name_len:   the length of name to match
  806  * @file_type:  the file_type of INODE_ITEM to match
  807  *
  808  * Returns 0 if found and *@index_ret will be modified with right value
  809  * Returns< 0 not found and *@index_ret will be (u64)-1
  810  */
  811 static int find_dir_index(struct btrfs_root *root, u64 dirid, u64 location_id,
  812               u64 *index_ret, char *namebuf, u32 name_len,
  813               u8 file_type)
  814 {
  815     struct btrfs_path path;
  816     struct extent_buffer *node;
  817     struct btrfs_dir_item *di;
  818     struct btrfs_key key;
  819     struct btrfs_key location;
  820     char name[BTRFS_NAME_LEN] = {0};
  821 
  822     u32 total;
  823     u32 cur = 0;
  824     u32 len;
  825     u32 data_len;
  826     u8 filetype;
  827     int slot;
  828     int ret;
  829 
  830     ASSERT(index_ret);
  831 
  832     /* search from the last index */
  833     key.objectid = dirid;
  834     key.offset = (u64)-1;
  835     key.type = BTRFS_DIR_INDEX_KEY;
  836 
  837     btrfs_init_path(&path);
  838     ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
  839     if (ret < 0)
  840         return ret;
  841 
  842 loop:
  843     ret = btrfs_previous_item(root, &path, dirid, BTRFS_DIR_INDEX_KEY);
  844     if (ret) {
  845         ret = -ENOENT;
  846         *index_ret = (64)-1;
  847         goto out;
  848     }
  849     /* Check whether inode_id/filetype/name match */
  850     node = path.nodes[0];
  851     slot = path.slots[0];
  852     di = btrfs_item_ptr(node, slot, struct btrfs_dir_item);
  853     total = btrfs_item_size_nr(node, slot);
  854     while (cur < total) {
  855         ret = -ENOENT;
  856         len = btrfs_dir_name_len(node, di);
  857         data_len = btrfs_dir_data_len(node, di);
  858 
  859         btrfs_dir_item_key_to_cpu(node, di, &location);
  860         if (location.objectid != location_id ||
  861             location.type != BTRFS_INODE_ITEM_KEY ||
  862             location.offset != 0)
  863             goto next;
  864 
  865         filetype = btrfs_dir_type(node, di);
  866         if (file_type != filetype)
  867             goto next;
  868 
  869         if (len > BTRFS_NAME_LEN)
  870             len = BTRFS_NAME_LEN;
  871 
  872         read_extent_buffer(node, name, (unsigned long)(di + 1), len);
  873         if (len != name_len || strncmp(namebuf, name, len))
  874             goto next;
  875 
  876         btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
  877         *index_ret = key.offset;
  878         ret = 0;
  879         goto out;
  880 next:
  881         len += sizeof(*di) + data_len;
  882         di = (struct btrfs_dir_item *)((char *)di + len);
  883         cur += len;
  884     }
  885     goto loop;
  886 
  887 out:
  888     btrfs_release_path(&path);
  889     return ret;
  890 }
  891 
  892 /*
  893  * Find DIR_ITEM/DIR_INDEX for the given key and check it with the specified
  894  * INODE_REF/INODE_EXTREF match.
  895  *
  896  * @root:   the root of the fs/file tree
  897  * @key:    the key of the DIR_ITEM/DIR_INDEX, key->offset will be right
  898  *              value while find index
  899  * @location_key: location key of the struct btrfs_dir_item to match
  900  * @name:   the name to match
  901  * @namelen:    the length of name
  902  * @file_type:  the type of file to math
  903  *
  904  * Return 0 if no error occurred.
  905  * Return DIR_ITEM_MISSING/DIR_INDEX_MISSING if couldn't find
  906  * DIR_ITEM/DIR_INDEX
  907  * Return DIR_ITEM_MISMATCH/DIR_INDEX_MISMATCH if INODE_REF/INODE_EXTREF
  908  * and DIR_ITEM/DIR_INDEX mismatch
  909  */
  910 static int find_dir_item(struct btrfs_root *root, struct btrfs_key *key,
  911              struct btrfs_key *location_key, char *name,
  912              u32 namelen, u8 file_type)
  913 {
  914     struct btrfs_path path;
  915     struct extent_buffer *node;
  916     struct btrfs_dir_item *di;
  917     struct btrfs_key location;
  918     char namebuf[BTRFS_NAME_LEN] = {0};
  919     u32 total;
  920     u32 cur = 0;
  921     u32 len;
  922     u32 data_len;
  923     u8 filetype;
  924     int slot;
  925     int ret;
  926 
  927     /* get the index by traversing all index */
  928     if (key->type == BTRFS_DIR_INDEX_KEY && key->offset == (u64)-1) {
  929         ret = find_dir_index(root, key->objectid,
  930                      location_key->objectid, &key->offset,
  931                      name, namelen, file_type);
  932         if (ret)
  933             ret = DIR_INDEX_MISSING;
  934         return ret;
  935     }
  936 
  937     btrfs_init_path(&path);
  938     ret = btrfs_search_slot(NULL, root, key, &path, 0, 0);
  939     if (ret) {
  940         ret = key->type == BTRFS_DIR_ITEM_KEY ? DIR_ITEM_MISSING :
  941             DIR_INDEX_MISSING;
  942         goto out;
  943     }
  944 
  945     /* Check whether inode_id/filetype/name match */
  946     node = path.nodes[0];
  947     slot = path.slots[0];
  948     di = btrfs_item_ptr(node, slot, struct btrfs_dir_item);
  949     total = btrfs_item_size_nr(node, slot);
  950     while (cur < total) {
  951         ret = key->type == BTRFS_DIR_ITEM_KEY ?
  952             DIR_ITEM_MISMATCH : DIR_INDEX_MISMATCH;
  953 
  954         len = btrfs_dir_name_len(node, di);
  955         data_len = btrfs_dir_data_len(node, di);
  956 
  957         btrfs_dir_item_key_to_cpu(node, di, &location);
  958         if (location.objectid != location_key->objectid ||
  959             location.type != location_key->type ||
  960             location.offset != location_key->offset)
  961             goto next;
  962 
  963         filetype = btrfs_dir_type(node, di);
  964         if (file_type != filetype)
  965             goto next;
  966 
  967         if (len > BTRFS_NAME_LEN) {
  968             len = BTRFS_NAME_LEN;
  969             warning("root %llu %s[%llu %llu] name too long %u, trimmed",
  970             root->objectid,
  971             key->type == BTRFS_DIR_ITEM_KEY ?
  972             "DIR_ITEM" : "DIR_INDEX",
  973             key->objectid, key->offset, len);
  974         }
  975         read_extent_buffer(node, namebuf, (unsigned long)(di + 1),
  976                    len);
  977         if (len != namelen || strncmp(namebuf, name, len))
  978             goto next;
  979 
  980         ret = 0;
  981         goto out;
  982 next:
  983         len += sizeof(*di) + data_len;
  984         di = (struct btrfs_dir_item *)((char *)di + len);
  985         cur += len;
  986     }
  987 
  988 out:
  989     btrfs_release_path(&path);
  990     return ret;
  991 }
  992 
  993 /*
  994  * The ternary means dir item, dir index and relative inode ref.
  995  * The function handles errs: INODE_MISSING, DIR_INDEX_MISSING
  996  * DIR_INDEX_MISMATCH, DIR_ITEM_MISSING, DIR_ITEM_MISMATCH by the follow
  997  * strategy:
  998  * If two of three is missing or mismatched, delete the existing one.
  999  * If one of three is missing or mismatched, add the missing one.
 1000  *
 1001  * returns 0 means success.
 1002  * returns not 0 means on error;
 1003  */
 1004 static int repair_ternary_lowmem(struct btrfs_root *root, u64 dir_ino, u64 ino,
 1005               u64 index, char *name, int name_len, u8 filetype,
 1006               int err)
 1007 {
 1008     struct btrfs_trans_handle *trans;
 1009     int stage = 0;
 1010     int ret = 0;
 1011 
 1012     /*
 1013      * stage shall be one of following valild values:
 1014      *  0: Fine, nothing to do.
 1015      *  1: One of three is wrong, so add missing one.
 1016      *  2: Two of three is wrong, so delete existed one.
 1017      */
 1018     if (err & (DIR_INDEX_MISMATCH | DIR_INDEX_MISSING))
 1019         stage++;
 1020     if (err & (DIR_ITEM_MISMATCH | DIR_ITEM_MISSING))
 1021         stage++;
 1022     if (err & (INODE_REF_MISSING))
 1023         stage++;
 1024 
 1025     /* stage must be smllarer than 3 */
 1026     ASSERT(stage < 3);
 1027 
 1028     trans = btrfs_start_transaction(root, 1);
 1029     if (stage == 2) {
 1030         ret = btrfs_unlink(trans, root, ino, dir_ino, index, name,
 1031                    name_len, 0);
 1032         goto out;
 1033     }
 1034     if (stage == 1) {
 1035         ret = btrfs_unlink(trans, root, ino, dir_ino, index, name,
 1036                 name_len, 0);
 1037         if (ret)
 1038             goto out;
 1039         ret = btrfs_add_link(trans, root, ino, dir_ino, name, name_len,
 1040                    filetype, &index, 1, 1);
 1041         goto out;
 1042     }
 1043 out:
 1044     btrfs_commit_transaction(trans, root);
 1045 
 1046     if (ret)
 1047         error("fail to repair inode %llu name %s filetype %u",
 1048               ino, name, filetype);
 1049     else
 1050         printf("%s ref/dir_item of inode %llu name %s filetype %u\n",
 1051                stage == 2 ? "Delete" : "Add",
 1052                ino, name, filetype);
 1053 
 1054     return ret;
 1055 }
 1056 
 1057 /*
 1058  * Prints inode ref error message
 1059  */
 1060 static void print_inode_ref_err(struct btrfs_root *root, struct btrfs_key *key,
 1061                 u64 index, const char *namebuf, int name_len,
 1062                 u8 filetype, int err)
 1063 {
 1064     if (!err)
 1065         return;
 1066 
 1067     /* root dir error */
 1068     if (key->objectid == BTRFS_FIRST_FREE_OBJECTID) {
 1069         error(
 1070     "root %llu root dir shouldn't have INODE REF[%llu %llu] name %s",
 1071               root->objectid, key->objectid, key->offset, namebuf);
 1072         return;
 1073     }
 1074 
 1075     /* normal error */
 1076     if (err & (DIR_ITEM_MISMATCH | DIR_ITEM_MISSING))
 1077         error("root %llu DIR ITEM[%llu %llu] %s name %s filetype %u",
 1078               root->objectid, key->offset,
 1079               btrfs_name_hash(namebuf, name_len),
 1080               err & DIR_ITEM_MISMATCH ? "mismatch" : "missing",
 1081               namebuf, filetype);
 1082     if (err & (DIR_INDEX_MISMATCH | DIR_INDEX_MISSING))
 1083         error("root %llu DIR INDEX[%llu %llu] %s name %s filetype %u",
 1084               root->objectid, key->offset, index,
 1085               err & DIR_ITEM_MISMATCH ? "mismatch" : "missing",
 1086               namebuf, filetype);
 1087 }
 1088 
 1089 /*
 1090  * Traverse the given INODE_REF and call find_dir_item() to find related
 1091  * DIR_ITEM/DIR_INDEX.
 1092  *
 1093  * @root:   the root of the fs/file tree
 1094  * @ref_key:    the key of the INODE_REF
 1095  * @path        the path provides node and slot
 1096  * @refs:   the count of INODE_REF
 1097  * @mode:   the st_mode of INODE_ITEM
 1098  * @name_ret:   returns with the first ref's name
 1099  * @name_len_ret:    len of the name_ret
 1100  *
 1101  * Return 0 if no error occurred.
 1102  */
 1103 static int check_inode_ref(struct btrfs_root *root, struct btrfs_key *ref_key,
 1104                struct btrfs_path *path, char *name_ret,
 1105                u32 *namelen_ret, u64 *refs_ret, int mode)
 1106 {
 1107     struct btrfs_key key;
 1108     struct btrfs_key location;
 1109     struct btrfs_inode_ref *ref;
 1110     struct extent_buffer *node;
 1111     char namebuf[BTRFS_NAME_LEN] = {0};
 1112     u32 total;
 1113     u32 cur = 0;
 1114     u32 len;
 1115     u32 name_len;
 1116     u64 index;
 1117     int ret;
 1118     int err = 0;
 1119     int tmp_err;
 1120     int slot;
 1121     int need_research = 0;
 1122     u64 refs;
 1123 
 1124 begin:
 1125     err = 0;
 1126     cur = 0;
 1127     refs = *refs_ret;
 1128 
 1129     /* since after repair, path and the dir item may be changed */
 1130     if (need_research) {
 1131         need_research = 0;
 1132         btrfs_release_path(path);
 1133         ret = btrfs_search_slot(NULL, root, ref_key, path, 0, 0);
 1134         /*
 1135          * The item was deleted, let the path point to the last checked
 1136          * item.
 1137          */
 1138         if (ret > 0) {
 1139             if (path->slots[0] == 0)
 1140                 btrfs_prev_leaf(root, path);
 1141             else
 1142                 path->slots[0]--;
 1143         }
 1144         if (ret)
 1145             goto out;
 1146     }
 1147 
 1148     location.objectid = ref_key->objectid;
 1149     location.type = BTRFS_INODE_ITEM_KEY;
 1150     location.offset = 0;
 1151     node = path->nodes[0];
 1152     slot = path->slots[0];
 1153 
 1154     memset(namebuf, 0, sizeof(namebuf) / sizeof(*namebuf));
 1155     ref = btrfs_item_ptr(node, slot, struct btrfs_inode_ref);
 1156     total = btrfs_item_size_nr(node, slot);
 1157 
 1158 next:
 1159     /* Update inode ref count */
 1160     refs++;
 1161     tmp_err = 0;
 1162     index = btrfs_inode_ref_index(node, ref);
 1163     name_len = btrfs_inode_ref_name_len(node, ref);
 1164 
 1165     if (name_len <= BTRFS_NAME_LEN) {
 1166         len = name_len;
 1167     } else {
 1168         len = BTRFS_NAME_LEN;
 1169         warning("root %llu INODE_REF[%llu %llu] name too long",
 1170             root->objectid, ref_key->objectid, ref_key->offset);
 1171     }
 1172 
 1173     read_extent_buffer(node, namebuf, (unsigned long)(ref + 1), len);
 1174 
 1175     /* copy the first name found to name_ret */
 1176     if (refs == 1 && name_ret) {
 1177         memcpy(name_ret, namebuf, len);
 1178         *namelen_ret = len;
 1179     }
 1180 
 1181     /* Check root dir ref */
 1182     if (ref_key->objectid == BTRFS_FIRST_FREE_OBJECTID) {
 1183         if (index != 0 || len != strlen("..") ||
 1184             strncmp("..", namebuf, len) ||
 1185             ref_key->offset != BTRFS_FIRST_FREE_OBJECTID) {
 1186             /* set err bits then repair will delete the ref */
 1187             err |= DIR_INDEX_MISSING;
 1188             err |= DIR_ITEM_MISSING;
 1189         }
 1190         goto end;
 1191     }
 1192 
 1193     /* Find related DIR_INDEX */
 1194     key.objectid = ref_key->offset;
 1195     key.type = BTRFS_DIR_INDEX_KEY;
 1196     key.offset = index;
 1197     tmp_err |= find_dir_item(root, &key, &location, namebuf, len,
 1198                 imode_to_type(mode));
 1199 
 1200     /* Find related dir_item */
 1201     key.objectid = ref_key->offset;
 1202     key.type = BTRFS_DIR_ITEM_KEY;
 1203     key.offset = btrfs_name_hash(namebuf, len);
 1204     tmp_err |= find_dir_item(root, &key, &location, namebuf, len,
 1205                 imode_to_type(mode));
 1206 end:
 1207     if (tmp_err && repair) {
 1208         ret = repair_ternary_lowmem(root, ref_key->offset,
 1209                         ref_key->objectid, index, namebuf,
 1210                         name_len, imode_to_type(mode),
 1211                         tmp_err);
 1212         if (!ret) {
 1213             need_research = 1;
 1214             goto begin;
 1215         }
 1216     }
 1217     print_inode_ref_err(root, ref_key, index, namebuf, name_len,
 1218                 imode_to_type(mode), tmp_err);
 1219     err |= tmp_err;
 1220     len = sizeof(*ref) + name_len;
 1221     ref = (struct btrfs_inode_ref *)((char *)ref + len);
 1222     cur += len;
 1223     if (cur < total)
 1224         goto next;
 1225 
 1226 out:
 1227     *refs_ret = refs;
 1228     return err;
 1229 }
 1230 
 1231 /*
 1232  * Traverse the given INODE_EXTREF and call find_dir_item() to find related
 1233  * DIR_ITEM/DIR_INDEX.
 1234  *
 1235  * @root:   the root of the fs/file tree
 1236  * @ref_key:    the key of the INODE_EXTREF
 1237  * @refs:   the count of INODE_EXTREF
 1238  * @mode:   the st_mode of INODE_ITEM
 1239  *
 1240  * Return 0 if no error occurred.
 1241  */
 1242 static int check_inode_extref(struct btrfs_root *root,
 1243                   struct btrfs_key *ref_key,
 1244                   struct extent_buffer *node, int slot, u64 *refs,
 1245                   int mode)
 1246 {
 1247     struct btrfs_key key;
 1248     struct btrfs_key location;
 1249     struct btrfs_inode_extref *extref;
 1250     char namebuf[BTRFS_NAME_LEN] = {0};
 1251     u32 total;
 1252     u32 cur = 0;
 1253     u32 len;
 1254     u32 name_len;
 1255     u64 index;
 1256     u64 parent;
 1257     int ret;
 1258     int err = 0;
 1259 
 1260     location.objectid = ref_key->objectid;
 1261     location.type = BTRFS_INODE_ITEM_KEY;
 1262     location.offset = 0;
 1263 
 1264     extref = btrfs_item_ptr(node, slot, struct btrfs_inode_extref);
 1265     total = btrfs_item_size_nr(node, slot);
 1266 
 1267 next:
 1268     /* update inode ref count */
 1269     (*refs)++;
 1270     name_len = btrfs_inode_extref_name_len(node, extref);
 1271     index = btrfs_inode_extref_index(node, extref);
 1272     parent = btrfs_inode_extref_parent(node, extref);
 1273     if (name_len <= BTRFS_NAME_LEN) {
 1274         len = name_len;
 1275     } else {
 1276         len = BTRFS_NAME_LEN;
 1277         warning("root %llu INODE_EXTREF[%llu %llu] name too long",
 1278             root->objectid, ref_key->objectid, ref_key->offset);
 1279     }
 1280     read_extent_buffer(node, namebuf, (unsigned long)(extref + 1), len);
 1281 
 1282     /* Check root dir ref name */
 1283     if (index == 0 && strncmp(namebuf, "..", name_len)) {
 1284         error("root %llu INODE_EXTREF[%llu %llu] ROOT_DIR name shouldn't be %s",
 1285               root->objectid, ref_key->objectid, ref_key->offset,
 1286               namebuf);
 1287         err |= ROOT_DIR_ERROR;
 1288     }
 1289 
 1290     /* find related dir_index */
 1291     key.objectid = parent;
 1292     key.type = BTRFS_DIR_INDEX_KEY;
 1293     key.offset = index;
 1294     ret = find_dir_item(root, &key, &location, namebuf, len, mode);
 1295     err |= ret;
 1296 
 1297     /* find related dir_item */
 1298     key.objectid = parent;
 1299     key.type = BTRFS_DIR_ITEM_KEY;
 1300     key.offset = btrfs_name_hash(namebuf, len);
 1301     ret = find_dir_item(root, &key, &location, namebuf, len, mode);
 1302     err |= ret;
 1303 
 1304     len = sizeof(*extref) + name_len;
 1305     extref = (struct btrfs_inode_extref *)((char *)extref + len);
 1306     cur += len;
 1307 
 1308     if (cur < total)
 1309         goto next;
 1310 
 1311     return err;
 1312 }
 1313 
 1314 /*
 1315  * Find INODE_REF/INODE_EXTREF for the given key and check it with the specified
 1316  * DIR_ITEM/DIR_INDEX match.
 1317  * Return with @index_ret.
 1318  *
 1319  * @root:   the root of the fs/file tree
 1320  * @key:    the key of the INODE_REF/INODE_EXTREF
 1321  * @name:   the name in the INODE_REF/INODE_EXTREF
 1322  * @namelen:    the length of name in the INODE_REF/INODE_EXTREF
 1323  * @index_ret:  the index in the INODE_REF/INODE_EXTREF,
 1324  *              value (64)-1 means do not check index
 1325  *
 1326  * Return 0 if no error occurred.
 1327  * Return >0 for error bitmap
 1328  */
 1329 static int find_inode_ref(struct btrfs_root *root, struct btrfs_key *key,
 1330               char *name, int namelen, u64 *index_ret)
 1331 
 1332 {
 1333     struct btrfs_path path;
 1334     struct btrfs_inode_ref *ref;
 1335     struct btrfs_inode_extref *extref;
 1336     struct extent_buffer *node;
 1337     char ref_namebuf[BTRFS_NAME_LEN] = {0};
 1338     u32 total;
 1339     u32 cur = 0;
 1340     u32 len;
 1341     u32 ref_namelen;
 1342     u64 ref_index;
 1343     u64 parent;
 1344     u64 dir_id;
 1345     int slot;
 1346     int ret;
 1347 
 1348     ASSERT(index_ret);
 1349 
 1350     btrfs_init_path(&path);
 1351     ret = btrfs_search_slot(NULL, root, key, &path, 0, 0);
 1352     if (ret) {
 1353         ret = INODE_REF_MISSING;
 1354         goto extref;
 1355     }
 1356 
 1357     node = path.nodes[0];
 1358     slot = path.slots[0];
 1359 
 1360     ref = btrfs_item_ptr(node, slot, struct btrfs_inode_ref);
 1361     total = btrfs_item_size_nr(node, slot);
 1362 
 1363     /* Iterate all entry of INODE_REF */
 1364     while (cur < total) {
 1365         ret = INODE_REF_MISSING;
 1366 
 1367         ref_namelen = btrfs_inode_ref_name_len(node, ref);
 1368         ref_index = btrfs_inode_ref_index(node, ref);
 1369         if (*index_ret != (u64)-1 && *index_ret != ref_index)
 1370             goto next_ref;
 1371 
 1372         if (cur + sizeof(*ref) + ref_namelen > total ||
 1373             ref_namelen > BTRFS_NAME_LEN) {
 1374             warning("root %llu INODE %s[%llu %llu] name too long",
 1375                 root->objectid,
 1376                 key->type == BTRFS_INODE_REF_KEY ?
 1377                     "REF" : "EXTREF",
 1378                 key->objectid, key->offset);
 1379 
 1380             if (cur + sizeof(*ref) > total)
 1381                 break;
 1382             len = min_t(u32, total - cur - sizeof(*ref),
 1383                     BTRFS_NAME_LEN);
 1384         } else {
 1385             len = ref_namelen;
 1386         }
 1387 
 1388         read_extent_buffer(node, ref_namebuf, (unsigned long)(ref + 1),
 1389                    len);
 1390 
 1391         if (len != namelen || strncmp(ref_namebuf, name, len))
 1392             goto next_ref;
 1393 
 1394         *index_ret = ref_index;
 1395         ret = 0;
 1396         goto out;
 1397 next_ref:
 1398         len = sizeof(*ref) + ref_namelen;
 1399         ref = (struct btrfs_inode_ref *)((char *)ref + len);
 1400         cur += len;
 1401     }
 1402 
 1403 extref:
 1404 
 1405     /* Skip if not support EXTENDED_IREF feature */
 1406     if (!btrfs_fs_incompat(root->fs_info, EXTENDED_IREF))
 1407         goto out;
 1408 
 1409     btrfs_release_path(&path);
 1410     btrfs_init_path(&path);
 1411 
 1412     dir_id = key->offset;
 1413     key->type = BTRFS_INODE_EXTREF_KEY;
 1414     key->offset = btrfs_extref_hash(dir_id, name, namelen);
 1415 
 1416     ret = btrfs_search_slot(NULL, root, key, &path, 0, 0);
 1417     if (ret) {
 1418         ret = INODE_REF_MISSING;
 1419         goto out;
 1420     }
 1421 
 1422     node = path.nodes[0];
 1423     slot = path.slots[0];
 1424 
 1425     extref = btrfs_item_ptr(node, slot, struct btrfs_inode_extref);
 1426     cur = 0;
 1427     total = btrfs_item_size_nr(node, slot);
 1428 
 1429     /* Iterate all entry of INODE_EXTREF */
 1430     while (cur < total) {
 1431         ret = INODE_REF_MISSING;
 1432 
 1433         ref_namelen = btrfs_inode_extref_name_len(node, extref);
 1434         ref_index = btrfs_inode_extref_index(node, extref);
 1435         parent = btrfs_inode_extref_parent(node, extref);
 1436         if (*index_ret != (u64)-1 && *index_ret != ref_index)
 1437             goto next_extref;
 1438 
 1439         if (parent != dir_id)
 1440             goto next_extref;
 1441 
 1442         if (ref_namelen <= BTRFS_NAME_LEN) {
 1443             len = ref_namelen;
 1444         } else {
 1445             len = BTRFS_NAME_LEN;
 1446             warning("root %llu INODE %s[%llu %llu] name too long",
 1447                 root->objectid,
 1448                 key->type == BTRFS_INODE_REF_KEY ?
 1449                     "REF" : "EXTREF",
 1450                 key->objectid, key->offset);
 1451         }
 1452         read_extent_buffer(node, ref_namebuf,
 1453                    (unsigned long)(extref + 1), len);
 1454 
 1455         if (len != namelen || strncmp(ref_namebuf, name, len))
 1456             goto next_extref;
 1457 
 1458         *index_ret = ref_index;
 1459         ret = 0;
 1460         goto out;
 1461 
 1462 next_extref:
 1463         len = sizeof(*extref) + ref_namelen;
 1464         extref = (struct btrfs_inode_extref *)((char *)extref + len);
 1465         cur += len;
 1466 
 1467     }
 1468 out:
 1469     btrfs_release_path(&path);
 1470     return ret;
 1471 }
 1472 
 1473 static int create_inode_item_lowmem(struct btrfs_trans_handle *trans,
 1474                     struct btrfs_root *root, u64 ino,
 1475                     u8 filetype)
 1476 {
 1477     u32 mode = (filetype == BTRFS_FT_DIR ? S_IFDIR : S_IFREG) | 0755;
 1478 
 1479     return insert_inode_item(trans, root, ino, 0, 0, 0, mode);
 1480 }
 1481 
 1482 /*
 1483  * Insert the missing inode item.
 1484  *
 1485  * Returns 0 means success.
 1486  * Returns <0 means error.
 1487  */
 1488 static int repair_inode_item_missing(struct btrfs_root *root, u64 ino,
 1489                      u8 filetype)
 1490 {
 1491     struct btrfs_key key;
 1492     struct btrfs_trans_handle *trans;
 1493     struct btrfs_path path;
 1494     int ret;
 1495 
 1496     key.objectid = ino;
 1497     key.type = BTRFS_INODE_ITEM_KEY;
 1498     key.offset = 0;
 1499 
 1500     btrfs_init_path(&path);
 1501     trans = btrfs_start_transaction(root, 1);
 1502     if (IS_ERR(trans)) {
 1503         ret = -EIO;
 1504         goto out;
 1505     }
 1506 
 1507     ret = btrfs_search_slot(trans, root, &key, &path, 1, 1);
 1508     if (ret < 0 || !ret)
 1509         goto fail;
 1510 
 1511     /* insert inode item */
 1512     create_inode_item_lowmem(trans, root, ino, filetype);
 1513     ret = 0;
 1514 fail:
 1515     btrfs_commit_transaction(trans, root);
 1516 out:
 1517     if (ret)
 1518         error("failed to repair root %llu INODE ITEM[%llu] missing",
 1519               root->objectid, ino);
 1520     btrfs_release_path(&path);
 1521     return ret;
 1522 }
 1523 
 1524 /*
 1525  * A wrapper for delete_corrupted_dir_item(), with support part like
 1526  * start/commit transaction.
 1527  */
 1528 static int lowmem_delete_corrupted_dir_item(struct btrfs_root *root,
 1529                         struct btrfs_key *di_key,
 1530                         char *namebuf, u32 name_len)
 1531 {
 1532     struct btrfs_trans_handle *trans;
 1533     int ret;
 1534 
 1535     trans = btrfs_start_transaction(root, 1);
 1536     if (IS_ERR(trans)) {
 1537         ret = PTR_ERR(trans);
 1538         error("failed to start transaction: %d", ret);
 1539         return ret;
 1540     }
 1541 
 1542     ret = delete_corrupted_dir_item(trans, root, di_key, namebuf, name_len);
 1543     if (ret < 0) {
 1544         btrfs_abort_transaction(trans, ret);
 1545     } else {
 1546         ret = btrfs_commit_transaction(trans, root);
 1547         if (ret < 0)
 1548             error("failed to commit transaction: %d", ret);
 1549     }
 1550     return ret;
 1551 }
 1552 
 1553 static int try_repair_imode(struct btrfs_root *root, u64 ino)
 1554 {
 1555     struct btrfs_inode_item *iitem;
 1556     struct btrfs_path path;
 1557     struct btrfs_key key;
 1558     int ret;
 1559 
 1560     key.objectid = ino;
 1561     key.type = BTRFS_INODE_ITEM_KEY;
 1562     key.offset = 0;
 1563     btrfs_init_path(&path);
 1564 
 1565     ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
 1566     if (ret > 0)
 1567         ret = -ENOENT;
 1568     if (ret < 0)
 1569         goto out;
 1570     iitem = btrfs_item_ptr(path.nodes[0], path.slots[0],
 1571                    struct btrfs_inode_item);
 1572     if (!is_valid_imode(btrfs_inode_mode(path.nodes[0], iitem))) {
 1573         ret = repair_imode_common(root, &path);
 1574     } else {
 1575         ret = -ENOTTY;
 1576     }
 1577 out:
 1578     btrfs_release_path(&path);
 1579     return ret;
 1580 }
 1581 
 1582 /*
 1583  * Call repair_inode_item_missing and repair_ternary_lowmem to repair
 1584  *
 1585  * Returns error after repair
 1586  */
 1587 static int repair_dir_item(struct btrfs_root *root, struct btrfs_key *di_key,
 1588                u64 ino, u64 index, u8 filetype, char *namebuf,
 1589                u32 name_len, int err)
 1590 {
 1591     u64 dirid = di_key->objectid;
 1592     int ret;
 1593 
 1594     if (err & (DIR_ITEM_HASH_MISMATCH)) {
 1595         ret = lowmem_delete_corrupted_dir_item(root, di_key, namebuf,
 1596                                name_len);
 1597         if (!ret)
 1598             err &= ~(DIR_ITEM_HASH_MISMATCH);
 1599     }
 1600     if (err & INODE_ITEM_MISSING) {
 1601         ret = repair_inode_item_missing(root, ino, filetype);
 1602         if (!ret)
 1603             err &= ~(INODE_ITEM_MISMATCH | INODE_ITEM_MISSING);
 1604     }
 1605 
 1606     if (err & INODE_ITEM_MISMATCH) {
 1607         /*
 1608          * INODE_ITEM mismatch can be caused by bad imode, so check if
 1609          * it's a bad imode, then repair if possible.
 1610          */
 1611         ret = try_repair_imode(root, ino);
 1612         if (!ret)
 1613             err &= ~INODE_ITEM_MISMATCH;
 1614     }
 1615 
 1616     if (err & ~(INODE_ITEM_MISMATCH | INODE_ITEM_MISSING)) {
 1617         ret = repair_ternary_lowmem(root, dirid, ino, index, namebuf,
 1618                         name_len, filetype, err);
 1619         if (!ret) {
 1620             err &= ~(DIR_INDEX_MISMATCH | DIR_INDEX_MISSING);
 1621             err &= ~(DIR_ITEM_MISMATCH | DIR_ITEM_MISSING);
 1622             err &= ~(INODE_REF_MISSING);
 1623         }
 1624     }
 1625     return err;
 1626 }
 1627 
 1628 static void print_dir_item_err(struct btrfs_root *root, struct btrfs_key *key,
 1629                    u64 ino, u64 index, const char *namebuf,
 1630                    int name_len, u8 filetype, int err)
 1631 {
 1632     if (err & (DIR_ITEM_MISMATCH | DIR_ITEM_MISSING)) {
 1633         error("root %llu DIR ITEM[%llu %llu] name %s filetype %d %s",
 1634               root->objectid, key->objectid, key->offset, namebuf,
 1635               filetype,
 1636               err & DIR_ITEM_MISMATCH ? "mismath" : "missing");
 1637     }
 1638 
 1639     if (err & (DIR_INDEX_MISMATCH | DIR_INDEX_MISSING)) {
 1640         error("root %llu DIR INDEX[%llu %llu] name %s filetype %d %s",
 1641               root->objectid, key->objectid, index, namebuf, filetype,
 1642               err & DIR_ITEM_MISMATCH ? "mismath" : "missing");
 1643     }
 1644 
 1645     if (err & (INODE_ITEM_MISSING | INODE_ITEM_MISMATCH)) {
 1646         error(
 1647         "root %llu INODE_ITEM[%llu] index %llu name %s filetype %d %s",
 1648               root->objectid, ino, index, namebuf, filetype,
 1649               err & INODE_ITEM_MISMATCH ? "mismath" : "missing");
 1650     }
 1651 
 1652     if (err & INODE_REF_MISSING)
 1653         error(
 1654         "root %llu INODE REF[%llu, %llu] name %s filetype %u missing",
 1655               root->objectid, ino, key->objectid, namebuf, filetype);
 1656 
 1657 }
 1658 
 1659 /*
 1660  * Traverse the given DIR_ITEM/DIR_INDEX and check related INODE_ITEM and
 1661  * call find_inode_ref() to check related INODE_REF/INODE_EXTREF.
 1662  *
 1663  * @root:   the root of the fs/file tree
 1664  * @key:    the key of the INODE_REF/INODE_EXTREF
 1665  * @path:       the path
 1666  * @size:   the st_size of the INODE_ITEM
 1667  *
 1668  * Return 0 if no error occurred.
 1669  * Return DIR_COUNT_AGAIN if the isize of the inode should be recalculated.
 1670  */
 1671 static int check_dir_item(struct btrfs_root *root, struct btrfs_key *di_key,
 1672               struct btrfs_path *path, u64 *size)
 1673 {
 1674     struct btrfs_dir_item *di;
 1675     struct btrfs_inode_item *ii;
 1676     struct btrfs_key key;
 1677     struct btrfs_key location;
 1678     struct extent_buffer *node;
 1679     int slot;
 1680     char namebuf[BTRFS_NAME_LEN] = {0};
 1681     u32 total;
 1682     u32 cur = 0;
 1683     u32 len;
 1684     u32 name_len;
 1685     u32 data_len;
 1686     u8 filetype;
 1687     u32 mode = 0;
 1688     u64 index;
 1689     int ret;
 1690     int err;
 1691     int tmp_err;
 1692     int need_research = 0;
 1693 
 1694 begin:
 1695     err = 0;
 1696     cur = 0;
 1697 
 1698     /* since after repair, path and the dir item may be changed */
 1699     if (need_research) {
 1700         need_research = 0;
 1701         err |= DIR_COUNT_AGAIN;
 1702         btrfs_release_path(path);
 1703         ret = btrfs_search_slot(NULL, root, di_key, path, 0, 0);
 1704         /* the item was deleted, let path point the last checked item */
 1705         if (ret > 0) {
 1706             if (path->slots[0] == 0)
 1707                 btrfs_prev_leaf(root, path);
 1708             else
 1709                 path->slots[0]--;
 1710         }
 1711         if (ret)
 1712             goto out;
 1713     }
 1714 
 1715     node = path->nodes[0];
 1716     slot = path->slots[0];
 1717 
 1718     di = btrfs_item_ptr(node, slot, struct btrfs_dir_item);
 1719     total = btrfs_item_size_nr(node, slot);
 1720     memset(namebuf, 0, sizeof(namebuf) / sizeof(*namebuf));
 1721 
 1722     while (cur < total) {
 1723         /*
 1724          * For DIR_ITEM set index to (u64)-1, so that find_inode_ref
 1725          * ignore index check.
 1726          */
 1727         if (di_key->type == BTRFS_DIR_INDEX_KEY)
 1728             index = di_key->offset;
 1729         else
 1730             index = (u64)-1;
 1731 
 1732         data_len = btrfs_dir_data_len(node, di);
 1733         tmp_err = 0;
 1734         if (data_len)
 1735             error("root %llu %s[%llu %llu] data_len shouldn't be %u",
 1736                   root->objectid,
 1737           di_key->type == BTRFS_DIR_ITEM_KEY ? "DIR_ITEM" : "DIR_INDEX",
 1738                   di_key->objectid, di_key->offset, data_len);
 1739 
 1740         name_len = btrfs_dir_name_len(node, di);
 1741         if (name_len <= BTRFS_NAME_LEN) {
 1742             len = name_len;
 1743         } else {
 1744             len = BTRFS_NAME_LEN;
 1745             warning("root %llu %s[%llu %llu] name too long",
 1746                 root->objectid,
 1747         di_key->type == BTRFS_DIR_ITEM_KEY ? "DIR_ITEM" : "DIR_INDEX",
 1748                 di_key->objectid, di_key->offset);
 1749         }
 1750         (*size) += name_len;
 1751         read_extent_buffer(node, namebuf, (unsigned long)(di + 1),
 1752                    len);
 1753         filetype = btrfs_dir_type(node, di);
 1754 
 1755         if (di_key->type == BTRFS_DIR_ITEM_KEY &&
 1756             di_key->offset != btrfs_name_hash(namebuf, len)) {
 1757             error("root %llu DIR_ITEM[%llu %llu] name %s namelen %u filetype %u mismatch with its hash, wanted %llu have %llu",
 1758             root->objectid, di_key->objectid, di_key->offset,
 1759             namebuf, len, filetype, di_key->offset,
 1760             btrfs_name_hash(namebuf, len));
 1761             tmp_err |= DIR_ITEM_HASH_MISMATCH;
 1762             goto next;
 1763         }
 1764 
 1765         btrfs_dir_item_key_to_cpu(node, di, &location);
 1766         /* Ignore related ROOT_ITEM check */
 1767         if (location.type == BTRFS_ROOT_ITEM_KEY)
 1768             goto next;
 1769 
 1770         btrfs_release_path(path);
 1771         /* Check relative INODE_ITEM(existence/filetype) */
 1772         ret = btrfs_search_slot(NULL, root, &location, path, 0, 0);
 1773         if (ret) {
 1774             tmp_err |= INODE_ITEM_MISSING;
 1775             goto next;
 1776         }
 1777 
 1778         ii = btrfs_item_ptr(path->nodes[0], path->slots[0],
 1779                     struct btrfs_inode_item);
 1780         mode = btrfs_inode_mode(path->nodes[0], ii);
 1781         if (imode_to_type(mode) != filetype) {
 1782             tmp_err |= INODE_ITEM_MISMATCH;
 1783             goto next;
 1784         }
 1785 
 1786         /* Check relative INODE_REF/INODE_EXTREF */
 1787         key.objectid = location.objectid;
 1788         key.type = BTRFS_INODE_REF_KEY;
 1789         key.offset = di_key->objectid;
 1790         tmp_err |= find_inode_ref(root, &key, namebuf, len, &index);
 1791 
 1792         /* check relative INDEX/ITEM */
 1793         key.objectid = di_key->objectid;
 1794         if (key.type == BTRFS_DIR_ITEM_KEY) {
 1795             key.type = BTRFS_DIR_INDEX_KEY;
 1796             key.offset = index;
 1797         } else {
 1798             key.type = BTRFS_DIR_ITEM_KEY;
 1799             key.offset = btrfs_name_hash(namebuf, name_len);
 1800         }
 1801 
 1802         tmp_err |= find_dir_item(root, &key, &location, namebuf,
 1803                      name_len, filetype);
 1804         /* find_dir_item may find index */
 1805         if (key.type == BTRFS_DIR_INDEX_KEY)
 1806             index = key.offset;
 1807 next:
 1808 
 1809         if (tmp_err && repair) {
 1810             ret = repair_dir_item(root, di_key,
 1811                           location.objectid, index,
 1812                           imode_to_type(mode), namebuf,
 1813                           name_len, tmp_err);
 1814             if (ret != tmp_err) {
 1815                 need_research = 1;
 1816                 goto begin;
 1817             }
 1818         }
 1819         btrfs_release_path(path);
 1820         print_dir_item_err(root, di_key, location.objectid, index,
 1821                    namebuf, name_len, filetype, tmp_err);
 1822         err |= tmp_err;
 1823         len = sizeof(*di) + name_len + data_len;
 1824         di = (struct btrfs_dir_item *)((char *)di + len);
 1825         cur += len;
 1826 
 1827         if (di_key->type == BTRFS_DIR_INDEX_KEY && cur < total) {
 1828             error("root %llu DIR_INDEX[%llu %llu] should contain only one entry",
 1829                   root->objectid, di_key->objectid,
 1830                   di_key->offset);
 1831             break;
 1832         }
 1833     }
 1834 out:
 1835     /* research path */
 1836     btrfs_release_path(path);
 1837     ret = btrfs_search_slot(NULL, root, di_key, path, 0, 0);
 1838     if (ret)
 1839         err |= ret > 0 ? -ENOENT : ret;
 1840     return err;
 1841 }
 1842 
 1843 /*
 1844  * Wrapper function of btrfs_punch_hole.
 1845  *
 1846  * @path:   The path holder, will point to the same key after hole punching.
 1847  *
 1848  * Returns 0 means success.
 1849  * Returns not 0 means error.
 1850  */
 1851 static int punch_extent_hole(struct btrfs_root *root, struct btrfs_path *path,
 1852                  u64 ino, u64 start, u64 len)
 1853 {
 1854     struct btrfs_trans_handle *trans;
 1855     struct btrfs_key key;
 1856     int ret;
 1857 
 1858     btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
 1859     trans = btrfs_start_transaction(root, 1);
 1860     if (IS_ERR(trans))
 1861         return PTR_ERR(trans);
 1862 
 1863     ret = btrfs_punch_hole(trans, root, ino, start, len);
 1864     if (ret) {
 1865         error("failed to add hole [%llu, %llu] in inode [%llu]",
 1866               start, len, ino);
 1867         btrfs_abort_transaction(trans, ret);
 1868         return ret;
 1869     }
 1870     printf("Add a hole [%llu, %llu] in inode [%llu]\n", start, len, ino);
 1871     btrfs_commit_transaction(trans, root);
 1872 
 1873     btrfs_release_path(path);
 1874     ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 1875     if (ret > 0)
 1876         ret = -ENOENT;
 1877     return ret;
 1878 }
 1879 
 1880 static int repair_inline_ram_bytes(struct btrfs_root *root,
 1881                    struct btrfs_path *path, u64 *ram_bytes_ret)
 1882 {
 1883     struct btrfs_trans_handle *trans;
 1884     struct btrfs_key key;
 1885     struct btrfs_file_extent_item *fi;
 1886     struct btrfs_item *item;
 1887     u32 on_disk_data_len;
 1888     int ret;
 1889     int recover_ret;
 1890 
 1891     trans = btrfs_start_transaction(root, 1);
 1892     if (IS_ERR(trans)) {
 1893         ret = PTR_ERR(trans);
 1894         return ret;
 1895     }
 1896     btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
 1897     btrfs_release_path(path);
 1898     ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
 1899     /* Not really possible */
 1900     if (ret > 0) {
 1901         ret = -ENOENT;
 1902         btrfs_release_path(path);
 1903         goto recover;
 1904     }
 1905     if (ret < 0)
 1906         goto recover;
 1907 
 1908     item = btrfs_item_nr(path->slots[0]);
 1909     on_disk_data_len = btrfs_file_extent_inline_item_len(path->nodes[0],
 1910             item);
 1911 
 1912     fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
 1913                 struct btrfs_file_extent_item);
 1914     if (btrfs_file_extent_type(path->nodes[0], fi) !=
 1915             BTRFS_FILE_EXTENT_INLINE ||
 1916         btrfs_file_extent_compression(path->nodes[0], fi) !=
 1917             BTRFS_COMPRESS_NONE)
 1918         return -EINVAL;
 1919     btrfs_set_file_extent_ram_bytes(path->nodes[0], fi, on_disk_data_len);
 1920     btrfs_mark_buffer_dirty(path->nodes[0]);
 1921 
 1922     ret = btrfs_commit_transaction(trans, root);
 1923     if (!ret) {
 1924         printf(
 1925     "Successfully repaired inline ram_bytes for root %llu ino %llu\n",
 1926             root->objectid, key.objectid);
 1927         *ram_bytes_ret = on_disk_data_len;
 1928     }
 1929     return ret;
 1930 
 1931 recover:
 1932     /*
 1933      * COW search failed, mostly due to the extra COW work (extent
 1934      * allocation, etc).  Since we have a good path from before, readonly
 1935      * search should still work, or later checks will fail due to empty
 1936      * path.
 1937      */
 1938     recover_ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 1939 
 1940     /* This really shouldn't happen, or we have a big problem */
 1941     ASSERT(recover_ret == 0);
 1942     return ret;
 1943 }
 1944 
 1945 static int check_file_extent_inline(struct btrfs_root *root,
 1946                     struct btrfs_path *path, u64 *size,
 1947                     u64 *end)
 1948 {
 1949     u32 max_inline_extent_size = min_t(u32, root->fs_info->sectorsize - 1,
 1950                 BTRFS_MAX_INLINE_DATA_SIZE(root->fs_info));
 1951     struct extent_buffer *node = path->nodes[0];
 1952     struct btrfs_item *e = btrfs_item_nr(path->slots[0]);
 1953     struct btrfs_file_extent_item *fi;
 1954     struct btrfs_key fkey;
 1955     u64 extent_num_bytes;
 1956     u32 item_inline_len;
 1957     int ret;
 1958     int compressed = 0;
 1959     int err = 0;
 1960 
 1961     fi = btrfs_item_ptr(node, path->slots[0], struct btrfs_file_extent_item);
 1962     item_inline_len = btrfs_file_extent_inline_item_len(node, e);
 1963     extent_num_bytes = btrfs_file_extent_ram_bytes(node, fi);
 1964     compressed = btrfs_file_extent_compression(node, fi);
 1965     btrfs_item_key_to_cpu(node, &fkey, path->slots[0]);
 1966 
 1967     if (extent_num_bytes == 0) {
 1968         error(
 1969 "root %llu EXTENT_DATA[%llu %llu] has empty inline extent",
 1970                 root->objectid, fkey.objectid, fkey.offset);
 1971         err |= FILE_EXTENT_ERROR;
 1972     }
 1973 
 1974     if (compressed) {
 1975         if (extent_num_bytes > root->fs_info->sectorsize) {
 1976             error(
 1977 "root %llu EXTENT_DATA[%llu %llu] too large inline extent ram size, have %llu, max: %u",
 1978                 root->objectid, fkey.objectid, fkey.offset,
 1979                 extent_num_bytes, root->fs_info->sectorsize - 1);
 1980             err |= FILE_EXTENT_ERROR;
 1981         }
 1982 
 1983         if (item_inline_len > max_inline_extent_size) {
 1984             error(
 1985 "root %llu EXTENT_DATA[%llu %llu] too large inline extent on-disk size, have %u, max: %u",
 1986                 root->objectid, fkey.objectid, fkey.offset,
 1987                 item_inline_len, max_inline_extent_size);
 1988             err |= FILE_EXTENT_ERROR;
 1989         }
 1990     } else {
 1991         if (extent_num_bytes > max_inline_extent_size) {
 1992             error(
 1993 "root %llu EXTENT_DATA[%llu %llu] too large inline extent size, have %llu, max: %u",
 1994                 root->objectid, fkey.objectid, fkey.offset,
 1995                 extent_num_bytes, max_inline_extent_size);
 1996             err |= FILE_EXTENT_ERROR;
 1997         }
 1998 
 1999         if (extent_num_bytes != item_inline_len) {
 2000             error(
 2001 "root %llu EXTENT_DATA[%llu %llu] wrong inline size, have: %llu, expected: %u",
 2002                 root->objectid, fkey.objectid, fkey.offset,
 2003                 extent_num_bytes, item_inline_len);
 2004             if (repair) {
 2005                 ret = repair_inline_ram_bytes(root, path,
 2006                                   &extent_num_bytes);
 2007                 if (ret)
 2008                     err |= FILE_EXTENT_ERROR;
 2009             } else {
 2010                 err |= FILE_EXTENT_ERROR;
 2011             }
 2012         }
 2013     }
 2014     *end += extent_num_bytes;
 2015     *size += extent_num_bytes;
 2016 
 2017     return err;
 2018 }
 2019 
 2020 /*
 2021  * Check file extent datasum/hole, update the size of the file extents,
 2022  * check and update the last offset of the file extent.
 2023  *
 2024  * @root:   the root of fs/file tree.
 2025  * @nodatasum:  INODE_NODATASUM feature.
 2026  * @size:   the sum of all EXTENT_DATA items size for this inode.
 2027  * @end:    the offset of the last extent.
 2028  *
 2029  * Return 0 if no error occurred.
 2030  */
 2031 static int check_file_extent(struct btrfs_root *root, struct btrfs_path *path,
 2032                  unsigned int nodatasum, u64 *size, u64 *end)
 2033 {
 2034     struct btrfs_file_extent_item *fi;
 2035     struct btrfs_key fkey;
 2036     struct extent_buffer *node = path->nodes[0];
 2037     u64 disk_bytenr;
 2038     u64 disk_num_bytes;
 2039     u64 extent_num_bytes;
 2040     u64 extent_offset;
 2041     u64 csum_found;     /* In byte size, sectorsize aligned */
 2042     u64 search_start;   /* Logical range start we search for csum */
 2043     u64 search_len;     /* Logical range len we search for csum */
 2044     u64 gen;
 2045     u64 super_gen;
 2046     unsigned int extent_type;
 2047     unsigned int is_hole;
 2048     int slot = path->slots[0];
 2049     int compressed = 0;
 2050     int ret;
 2051     int err = 0;
 2052 
 2053     btrfs_item_key_to_cpu(node, &fkey, slot);
 2054     fi = btrfs_item_ptr(node, slot, struct btrfs_file_extent_item);
 2055     extent_type = btrfs_file_extent_type(node, fi);
 2056 
 2057     /* Check extent type */
 2058     if (extent_type != BTRFS_FILE_EXTENT_REG &&
 2059         extent_type != BTRFS_FILE_EXTENT_PREALLOC &&
 2060         extent_type != BTRFS_FILE_EXTENT_INLINE) {
 2061         err |= FILE_EXTENT_ERROR;
 2062         error("root %llu EXTENT_DATA[%llu %llu] type bad",
 2063               root->objectid, fkey.objectid, fkey.offset);
 2064         return err;
 2065     }
 2066 
 2067     /* Check inline extent */
 2068     if (extent_type == BTRFS_FILE_EXTENT_INLINE)
 2069         return check_file_extent_inline(root, path, size, end);
 2070 
 2071     /* Check REG_EXTENT/PREALLOC_EXTENT */
 2072     gen = btrfs_file_extent_generation(node, fi);
 2073     disk_bytenr = btrfs_file_extent_disk_bytenr(node, fi);
 2074     disk_num_bytes = btrfs_file_extent_disk_num_bytes(node, fi);
 2075     extent_num_bytes = btrfs_file_extent_num_bytes(node, fi);
 2076     extent_offset = btrfs_file_extent_offset(node, fi);
 2077     compressed = btrfs_file_extent_compression(node, fi);
 2078     is_hole = (disk_bytenr == 0) && (disk_num_bytes == 0);
 2079     super_gen = btrfs_super_generation(root->fs_info->super_copy);
 2080 
 2081     if (gen > super_gen + 1) {
 2082         error(
 2083         "invalid file extent generation, have %llu expect (0, %llu]",
 2084             gen, super_gen + 1);
 2085         err |= INVALID_GENERATION;
 2086     }
 2087 
 2088     /*
 2089      * Check EXTENT_DATA csum
 2090      *
 2091      * For plain (uncompressed) extent, we should only check the range
 2092      * we're referring to, as it's possible that part of prealloc extent
 2093      * has been written, and has csum:
 2094      *
 2095      * |<--- Original large preallocated extent A ---->|
 2096      * |<- Prealloc File Extent ->|<- Regular Extent ->|
 2097      *  No csum             Has csum
 2098      *
 2099      * For compressed extent, we should check the whole range.
 2100      */
 2101     if (!compressed) {
 2102         search_start = disk_bytenr + extent_offset;
 2103         search_len = extent_num_bytes;
 2104     } else {
 2105         search_start = disk_bytenr;
 2106         search_len = disk_num_bytes;
 2107     }
 2108     ret = count_csum_range(root->fs_info, search_start, search_len,
 2109                    &csum_found);
 2110     if (csum_found > 0 && nodatasum) {
 2111         err |= ODD_CSUM_ITEM;
 2112         error("root %llu EXTENT_DATA[%llu %llu] nodatasum shouldn't have datasum",
 2113               root->objectid, fkey.objectid, fkey.offset);
 2114     } else if (extent_type == BTRFS_FILE_EXTENT_REG && !nodatasum &&
 2115            !is_hole && (ret < 0 || csum_found < search_len)) {
 2116         err |= CSUM_ITEM_MISSING;
 2117         error("root %llu EXTENT_DATA[%llu %llu] csum missing, have: %llu, expected: %llu",
 2118               root->objectid, fkey.objectid, fkey.offset,
 2119               csum_found, search_len);
 2120     } else if (extent_type == BTRFS_FILE_EXTENT_PREALLOC &&
 2121            csum_found > 0) {
 2122         ret = check_prealloc_extent_written(root->fs_info,
 2123                             disk_bytenr, disk_num_bytes);
 2124         if (ret < 0)
 2125             return ret;
 2126         if (ret == 0) {
 2127             err |= ODD_CSUM_ITEM;
 2128             error(
 2129 "root %llu EXTENT_DATA[%llu %llu] prealloc shouldn't have csum, but has: %llu",
 2130                   root->objectid, fkey.objectid, fkey.offset,
 2131                   csum_found);
 2132         }
 2133     }
 2134 
 2135     /*
 2136      * Extra check for compressed extents:
 2137      * Btrfs doesn't allow NODATASUM and compressed extent co-exist, thus
 2138      * all compressed extents should have a checksum.
 2139      */
 2140     if (compressed && csum_found < search_len) {
 2141         error(
 2142 "root %llu EXTENT_DATA[%llu %llu] compressed extent must have csum, but only %llu bytes have, expect %llu",
 2143               root->objectid, fkey.objectid, fkey.offset, csum_found,
 2144               search_len);
 2145         err |= CSUM_ITEM_MISSING;
 2146     }
 2147     if (compressed && nodatasum) {
 2148         error(
 2149 "root %llu EXTENT_DATA[%llu %llu] is compressed, but inode flag doesn't allow it",
 2150               root->objectid, fkey.objectid, fkey.offset);
 2151         err |= FILE_EXTENT_ERROR;
 2152     }
 2153 
 2154     /* Check EXTENT_DATA hole */
 2155     if (!no_holes && *end != fkey.offset) {
 2156         if (repair)
 2157             ret = punch_extent_hole(root, path, fkey.objectid,
 2158                         *end, fkey.offset - *end);
 2159         if (!repair || ret) {
 2160             err |= FILE_EXTENT_ERROR;
 2161             error(
 2162 "root %llu EXTENT_DATA[%llu %llu] gap exists, expected: EXTENT_DATA[%llu %llu]",
 2163                 root->objectid, fkey.objectid, fkey.offset,
 2164                 fkey.objectid, *end);
 2165         }
 2166     }
 2167 
 2168     *end = fkey.offset + extent_num_bytes;
 2169     if (!is_hole)
 2170         *size += extent_num_bytes;
 2171 
 2172     return err;
 2173 }
 2174 
 2175 static int __count_dir_isize(struct btrfs_root *root, u64 ino, int type,
 2176         u64 *size_ret)
 2177 {
 2178     struct btrfs_key key;
 2179     struct btrfs_path path;
 2180     u32 len;
 2181     struct btrfs_dir_item *di;
 2182     int ret;
 2183     int cur = 0;
 2184     int total = 0;
 2185 
 2186     ASSERT(size_ret);
 2187     *size_ret = 0;
 2188 
 2189     key.objectid = ino;
 2190     key.type = type;
 2191     key.offset = (u64)-1;
 2192 
 2193     btrfs_init_path(&path);
 2194     ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
 2195     if (ret < 0) {
 2196         ret = -EIO;
 2197         goto out;
 2198     }
 2199     /* if found, go to spacial case */
 2200     if (ret == 0)
 2201         goto special_case;
 2202 
 2203 loop:
 2204     ret = btrfs_previous_item(root, &path, ino, type);
 2205 
 2206     if (ret) {
 2207         ret = 0;
 2208         goto out;
 2209     }
 2210 
 2211 special_case:
 2212     di = btrfs_item_ptr(path.nodes[0], path.slots[0], struct btrfs_dir_item);
 2213     cur = 0;
 2214     total = btrfs_item_size_nr(path.nodes[0], path.slots[0]);
 2215 
 2216     while (cur < total) {
 2217         len = btrfs_dir_name_len(path.nodes[0], di);
 2218         if (len > BTRFS_NAME_LEN)
 2219             len = BTRFS_NAME_LEN;
 2220         *size_ret += len;
 2221 
 2222         len += btrfs_dir_data_len(path.nodes[0], di);
 2223         len += sizeof(*di);
 2224         di = (struct btrfs_dir_item *)((char *)di + len);
 2225         cur += len;
 2226     }
 2227     goto loop;
 2228 
 2229 out:
 2230     btrfs_release_path(&path);
 2231     return ret;
 2232 }
 2233 
 2234 static int count_dir_isize(struct btrfs_root *root, u64 ino, u64 *size)
 2235 {
 2236     u64 item_size;
 2237     u64 index_size;
 2238     int ret;
 2239 
 2240     ASSERT(size);
 2241     ret = __count_dir_isize(root, ino, BTRFS_DIR_ITEM_KEY, &item_size);
 2242     if (ret)
 2243         goto out;
 2244 
 2245     ret = __count_dir_isize(root, ino, BTRFS_DIR_INDEX_KEY, &index_size);
 2246     if (ret)
 2247         goto out;
 2248 
 2249     *size = item_size + index_size;
 2250 
 2251 out:
 2252     if (ret)
 2253         error("failed to count root %llu INODE[%llu] root size",
 2254               root->objectid, ino);
 2255     return ret;
 2256 }
 2257 
 2258 /*
 2259  * Set inode item nbytes to @nbytes
 2260  *
 2261  * Returns  0     on success
 2262  * Returns  != 0  on error
 2263  */
 2264 static int repair_inode_nbytes_lowmem(struct btrfs_root *root,
 2265                       struct btrfs_path *path,
 2266                       u64 ino, u64 nbytes)
 2267 {
 2268     struct btrfs_trans_handle *trans;
 2269     struct btrfs_inode_item *ii;
 2270     struct btrfs_key key;
 2271     struct btrfs_key research_key;
 2272     int err = 0;
 2273     int ret;
 2274 
 2275     btrfs_item_key_to_cpu(path->nodes[0], &research_key, path->slots[0]);
 2276 
 2277     key.objectid = ino;
 2278     key.type = BTRFS_INODE_ITEM_KEY;
 2279     key.offset = 0;
 2280 
 2281     trans = btrfs_start_transaction(root, 1);
 2282     if (IS_ERR(trans)) {
 2283         ret = PTR_ERR(trans);
 2284         err |= ret;
 2285         goto out;
 2286     }
 2287 
 2288     btrfs_release_path(path);
 2289     ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
 2290     if (ret > 0)
 2291         ret = -ENOENT;
 2292     if (ret) {
 2293         err |= ret;
 2294         goto fail;
 2295     }
 2296 
 2297     ii = btrfs_item_ptr(path->nodes[0], path->slots[0],
 2298                 struct btrfs_inode_item);
 2299     btrfs_set_inode_nbytes(path->nodes[0], ii, nbytes);
 2300     btrfs_mark_buffer_dirty(path->nodes[0]);
 2301 fail:
 2302     btrfs_commit_transaction(trans, root);
 2303 out:
 2304     if (ret)
 2305         error("failed to set nbytes in inode %llu root %llu",
 2306               ino, root->root_key.objectid);
 2307     else
 2308         printf("Set nbytes in inode item %llu root %llu to %llu\n", ino,
 2309                root->root_key.objectid, nbytes);
 2310 
 2311     /* research path */
 2312     btrfs_release_path(path);
 2313     ret = btrfs_search_slot(NULL, root, &research_key, path, 0, 0);
 2314     err |= ret;
 2315 
 2316     return err;
 2317 }
 2318 
 2319 /*
 2320  * Set directory inode isize to @isize.
 2321  *
 2322  * Returns 0     on success.
 2323  * Returns != 0  on error.
 2324  */
 2325 static int repair_dir_isize_lowmem(struct btrfs_root *root,
 2326                    struct btrfs_path *path,
 2327                    u64 ino, u64 isize)
 2328 {
 2329     struct btrfs_trans_handle *trans;
 2330     struct btrfs_inode_item *ii;
 2331     struct btrfs_key key;
 2332     struct btrfs_key research_key;
 2333     int ret;
 2334     int err = 0;
 2335 
 2336     btrfs_item_key_to_cpu(path->nodes[0], &research_key, path->slots[0]);
 2337 
 2338     key.objectid = ino;
 2339     key.type = BTRFS_INODE_ITEM_KEY;
 2340     key.offset = 0;
 2341 
 2342     trans = btrfs_start_transaction(root, 1);
 2343     if (IS_ERR(trans)) {
 2344         ret = PTR_ERR(trans);
 2345         err |= ret;
 2346         goto out;
 2347     }
 2348 
 2349     btrfs_release_path(path);
 2350     ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
 2351     if (ret > 0)
 2352         ret = -ENOENT;
 2353     if (ret) {
 2354         err |= ret;
 2355         goto fail;
 2356     }
 2357 
 2358     ii = btrfs_item_ptr(path->nodes[0], path->slots[0],
 2359                 struct btrfs_inode_item);
 2360     btrfs_set_inode_size(path->nodes[0], ii, isize);
 2361     btrfs_mark_buffer_dirty(path->nodes[0]);
 2362 fail:
 2363     btrfs_commit_transaction(trans, root);
 2364 out:
 2365     if (ret)
 2366         error("failed to set isize in inode %llu root %llu",
 2367               ino, root->root_key.objectid);
 2368     else
 2369         printf("Set isize in inode %llu root %llu to %llu\n",
 2370                ino, root->root_key.objectid, isize);
 2371 
 2372     btrfs_release_path(path);
 2373     ret = btrfs_search_slot(NULL, root, &research_key, path, 0, 0);
 2374     err |= ret;
 2375 
 2376     return err;
 2377 }
 2378 
 2379 /*
 2380  * Wrapper function for btrfs_add_orphan_item().
 2381  *
 2382  * Returns 0     on success.
 2383  * Returns != 0  on error.
 2384  */
 2385 static int repair_inode_orphan_item_lowmem(struct btrfs_root *root,
 2386                        struct btrfs_path *path, u64 ino)
 2387 {
 2388     struct btrfs_trans_handle *trans;
 2389     struct btrfs_key research_key;
 2390     int ret;
 2391     int err = 0;
 2392 
 2393     btrfs_item_key_to_cpu(path->nodes[0], &research_key, path->slots[0]);
 2394 
 2395     trans = btrfs_start_transaction(root, 1);
 2396     if (IS_ERR(trans)) {
 2397         ret = PTR_ERR(trans);
 2398         err |= ret;
 2399         goto out;
 2400     }
 2401 
 2402     btrfs_release_path(path);
 2403     ret = btrfs_add_orphan_item(trans, root, path, ino);
 2404     err |= ret;
 2405     btrfs_commit_transaction(trans, root);
 2406 out:
 2407     if (ret)
 2408         error("failed to add inode %llu as orphan item root %llu",
 2409               ino, root->root_key.objectid);
 2410     else
 2411         printf("Added inode %llu as orphan item root %llu\n",
 2412                ino, root->root_key.objectid);
 2413 
 2414     btrfs_release_path(path);
 2415     ret = btrfs_search_slot(NULL, root, &research_key, path, 0, 0);
 2416     err |= ret;
 2417 
 2418     return err;
 2419 }
 2420 
 2421 /* Set inode_item nlink to @ref_count.
 2422  * If @ref_count == 0, move it to "lost+found" and increase @ref_count.
 2423  *
 2424  * Returns 0 on success
 2425  */
 2426 static int repair_inode_nlinks_lowmem(struct btrfs_root *root,
 2427                       struct btrfs_path *path, u64 ino,
 2428                       const char *name, u32 namelen,
 2429                       u64 ref_count, u8 filetype, u64 *nlink)
 2430 {
 2431     struct btrfs_trans_handle *trans;
 2432     struct btrfs_inode_item *ii;
 2433     struct btrfs_key key;
 2434     struct btrfs_key old_key;
 2435     char namebuf[BTRFS_NAME_LEN] = {0};
 2436     int name_len;
 2437     int ret;
 2438     int ret2;
 2439 
 2440     /* save the key */
 2441     btrfs_item_key_to_cpu(path->nodes[0], &old_key, path->slots[0]);
 2442 
 2443     if (name && namelen) {
 2444         ASSERT(namelen <= BTRFS_NAME_LEN);
 2445         memcpy(namebuf, name, namelen);
 2446         name_len = namelen;
 2447     } else {
 2448         sprintf(namebuf, "%llu", ino);
 2449         name_len = count_digits(ino);
 2450         printf("Can't find file name for inode %llu, use %s instead\n",
 2451                ino, namebuf);
 2452     }
 2453 
 2454     trans = btrfs_start_transaction(root, 1);
 2455     if (IS_ERR(trans)) {
 2456         ret = PTR_ERR(trans);
 2457         goto out;
 2458     }
 2459 
 2460     btrfs_release_path(path);
 2461     /* if refs is 0, put it into lostfound */
 2462     if (ref_count == 0) {
 2463         ret = link_inode_to_lostfound(trans, root, path, ino, namebuf,
 2464                           name_len, filetype, &ref_count);
 2465         if (ret)
 2466             goto fail;
 2467     }
 2468 
 2469     /* reset inode_item's nlink to ref_count */
 2470     key.objectid = ino;
 2471     key.type = BTRFS_INODE_ITEM_KEY;
 2472     key.offset = 0;
 2473 
 2474     btrfs_release_path(path);
 2475     ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
 2476     if (ret > 0)
 2477         ret = -ENOENT;
 2478     if (ret)
 2479         goto fail;
 2480 
 2481     ii = btrfs_item_ptr(path->nodes[0], path->slots[0],
 2482                 struct btrfs_inode_item);
 2483     btrfs_set_inode_nlink(path->nodes[0], ii, ref_count);
 2484     btrfs_mark_buffer_dirty(path->nodes[0]);
 2485 
 2486     if (nlink)
 2487         *nlink = ref_count;
 2488 fail:
 2489     btrfs_commit_transaction(trans, root);
 2490 out:
 2491     if (ret)
 2492         error(
 2493     "fail to repair nlink of inode %llu root %llu name %s filetype %u",
 2494                root->objectid, ino, namebuf, filetype);
 2495     else
 2496         printf("Fixed nlink of inode %llu root %llu name %s filetype %u\n",
 2497                root->objectid, ino, namebuf, filetype);
 2498 
 2499     /* research */
 2500     btrfs_release_path(path);
 2501     ret2 = btrfs_search_slot(NULL, root, &old_key, path, 0, 0);
 2502     if (ret2 < 0)
 2503         return ret |= ret2;
 2504     return ret;
 2505 }
 2506 
 2507 static bool has_orphan_item(struct btrfs_root *root, u64 ino)
 2508 {
 2509     struct btrfs_path path;
 2510     struct btrfs_key key;
 2511     int ret;
 2512 
 2513     btrfs_init_path(&path);
 2514     key.objectid = BTRFS_ORPHAN_OBJECTID;
 2515     key.type = BTRFS_ORPHAN_ITEM_KEY;
 2516     key.offset = ino;
 2517 
 2518     ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
 2519     btrfs_release_path(&path);
 2520     if (ret == 0)
 2521         return true;
 2522     return false;
 2523 }
 2524 
 2525 static int repair_inode_gen_lowmem(struct btrfs_root *root,
 2526                    struct btrfs_path *path)
 2527 {
 2528     struct btrfs_trans_handle *trans;
 2529     struct btrfs_inode_item *ii;
 2530     struct btrfs_key key;
 2531     u64 transid;
 2532     int ret;
 2533 
 2534     trans = btrfs_start_transaction(root, 1);
 2535     if (IS_ERR(trans)) {
 2536         ret = PTR_ERR(trans);
 2537         errno = -ret;
 2538         error("failed to start transaction for inode gen repair: %m");
 2539         return ret;
 2540     }
 2541     transid = trans->transid;
 2542     btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
 2543     ASSERT(key.type == BTRFS_INODE_ITEM_KEY);
 2544 
 2545     btrfs_release_path(path);
 2546 
 2547     ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
 2548     if (ret > 0) {
 2549         ret = -ENOENT;
 2550         error("no inode item found for ino %llu", key.objectid);
 2551         goto error;
 2552     }
 2553     if (ret < 0) {
 2554         errno = -ret;
 2555         error("failed to find inode item for ino %llu: %m", key.objectid);
 2556         goto error;
 2557     }
 2558     ii = btrfs_item_ptr(path->nodes[0], path->slots[0],
 2559                 struct btrfs_inode_item);
 2560     btrfs_set_inode_generation(path->nodes[0], ii, trans->transid);
 2561     btrfs_mark_buffer_dirty(path->nodes[0]);
 2562     ret = btrfs_commit_transaction(trans, root);
 2563     if (ret < 0) {
 2564         errno = -ret;
 2565         error("failed to commit transaction: %m");
 2566         goto error;
 2567     }
 2568     printf("reseting inode generation to %llu for ino %llu\n",
 2569         transid, key.objectid);
 2570     return ret;
 2571 
 2572 error:
 2573     btrfs_abort_transaction(trans, ret);
 2574     return ret;
 2575 }
 2576 
 2577 /*
 2578  * Check INODE_ITEM and related ITEMs (the same inode number)
 2579  * 1. check link count
 2580  * 2. check inode ref/extref
 2581  * 3. check dir item/index
 2582  *
 2583  * Return 0 if no error occurred.
 2584  * Return >0 for error or hit the traversal is done(by error bitmap)
 2585  */
 2586 static int check_inode_item(struct btrfs_root *root, struct btrfs_path *path)
 2587 {
 2588     struct extent_buffer *node;
 2589     struct btrfs_inode_item *ii;
 2590     struct btrfs_key key;
 2591     struct btrfs_key last_key;
 2592     struct btrfs_super_block *super = root->fs_info->super_copy;
 2593     u64 inode_id;
 2594     u32 mode;
 2595     u64 flags;
 2596     u64 nlink;
 2597     u64 nbytes;
 2598     u64 isize;
 2599     u64 size = 0;
 2600     u64 refs = 0;
 2601     u64 extent_end = 0;
 2602     u64 extent_size = 0;
 2603     u64 generation;
 2604     u64 gen_uplimit;
 2605     unsigned int dir;
 2606     unsigned int nodatasum;
 2607     bool is_orphan = false;
 2608     int slot;
 2609     int ret;
 2610     int err = 0;
 2611     char namebuf[BTRFS_NAME_LEN] = {0};
 2612     u32 name_len = 0;
 2613 
 2614     node = path->nodes[0];
 2615     slot = path->slots[0];
 2616 
 2617     btrfs_item_key_to_cpu(node, &key, slot);
 2618     inode_id = key.objectid;
 2619 
 2620     if (inode_id == BTRFS_ORPHAN_OBJECTID) {
 2621         ret = btrfs_next_item(root, path);
 2622         if (ret > 0)
 2623             err |= LAST_ITEM;
 2624         return err;
 2625     }
 2626 
 2627     is_orphan = has_orphan_item(root, inode_id);
 2628     ii = btrfs_item_ptr(node, slot, struct btrfs_inode_item);
 2629     isize = btrfs_inode_size(node, ii);
 2630     nbytes = btrfs_inode_nbytes(node, ii);
 2631     mode = btrfs_inode_mode(node, ii);
 2632     flags = btrfs_inode_flags(node, ii);
 2633     dir = imode_to_type(mode) == BTRFS_FT_DIR;
 2634     nlink = btrfs_inode_nlink(node, ii);
 2635     generation = btrfs_inode_generation(node, ii);
 2636     nodatasum = btrfs_inode_flags(node, ii) & BTRFS_INODE_NODATASUM;
 2637 
 2638     if (!is_valid_imode(mode)) {
 2639         error("invalid imode mode bits: 0%o", mode);
 2640         if (repair) {
 2641             ret = repair_imode_common(root, path);
 2642             if (ret < 0)
 2643                 err |= INODE_MODE_ERROR;
 2644         } else {
 2645             err |= INODE_MODE_ERROR;
 2646         }
 2647     }
 2648 
 2649     if (btrfs_super_log_root(super) != 0 &&
 2650         root->objectid == BTRFS_TREE_LOG_OBJECTID)
 2651         gen_uplimit = btrfs_super_generation(super) + 1;
 2652     else
 2653         gen_uplimit = btrfs_super_generation(super);
 2654 
 2655     if (generation > gen_uplimit) {
 2656         error(
 2657     "invalid inode generation for ino %llu, have %llu expect [0, %llu)",
 2658               inode_id, generation, gen_uplimit);
 2659         if (repair) {
 2660             ret = repair_inode_gen_lowmem(root, path);
 2661             if (ret < 0)
 2662                 err |= INVALID_GENERATION;
 2663         } else {
 2664             err |= INVALID_GENERATION;
 2665         }
 2666 
 2667     }
 2668     if (S_ISLNK(mode) &&
 2669         flags & (BTRFS_INODE_IMMUTABLE | BTRFS_INODE_APPEND)) {
 2670         err |= INODE_FLAGS_ERROR;
 2671         error(
 2672 "symlinks must never have immutable/append flags set, root %llu inode item %llu flags %llu may be corrupted",
 2673               root->objectid, inode_id, flags);
 2674     }
 2675 
 2676     while (1) {
 2677         btrfs_item_key_to_cpu(path->nodes[0], &last_key, path->slots[0]);
 2678         ret = btrfs_next_item(root, path);
 2679         if (ret < 0) {
 2680             /* out will fill 'err' rusing current statistics */
 2681             goto out;
 2682         } else if (ret > 0) {
 2683             err |= LAST_ITEM;
 2684             goto out;
 2685         }
 2686 
 2687         node = path->nodes[0];
 2688         slot = path->slots[0];
 2689         btrfs_item_key_to_cpu(node, &key, slot);
 2690         if (key.objectid != inode_id)
 2691             goto out;
 2692 
 2693         switch (key.type) {
 2694         case BTRFS_INODE_REF_KEY:
 2695             ret = check_inode_ref(root, &key, path, namebuf,
 2696                           &name_len, &refs, mode);
 2697             err |= ret;
 2698             break;
 2699         case BTRFS_INODE_EXTREF_KEY:
 2700         {
 2701             bool ext_ref = btrfs_fs_incompat(root->fs_info,
 2702                              EXTENDED_IREF);
 2703             if (key.type == BTRFS_INODE_EXTREF_KEY && !ext_ref)
 2704                 warning("root %llu EXTREF[%llu %llu] isn't supported",
 2705                     root->objectid, key.objectid,
 2706                     key.offset);
 2707             ret = check_inode_extref(root, &key, node, slot, &refs,
 2708                          mode);
 2709             err |= ret;
 2710             break;
 2711         }
 2712         case BTRFS_DIR_ITEM_KEY:
 2713         case BTRFS_DIR_INDEX_KEY:
 2714             if (!dir) {
 2715                 warning("root %llu INODE[%llu] mode %u shouldn't have DIR_INDEX[%llu %llu]",
 2716                     root->objectid, inode_id,
 2717                     imode_to_type(mode), key.objectid,
 2718                     key.offset);
 2719             }
 2720             ret = check_dir_item(root, &key, path, &size);
 2721             err |= ret;
 2722             break;
 2723         case BTRFS_EXTENT_DATA_KEY:
 2724             if (dir) {
 2725                 warning("root %llu DIR INODE[%llu] shouldn't EXTENT_DATA[%llu %llu]",
 2726                     root->objectid, inode_id, key.objectid,
 2727                     key.offset);
 2728             }
 2729             ret = check_file_extent(root, path, nodatasum,
 2730                         &extent_size, &extent_end);
 2731             err |= ret;
 2732             break;
 2733         case BTRFS_XATTR_ITEM_KEY:
 2734             break;
 2735         default:
 2736             error("ITEM[%llu %u %llu] UNKNOWN TYPE",
 2737                   key.objectid, key.type, key.offset);
 2738         }
 2739     }
 2740 
 2741 out:
 2742     if (err & LAST_ITEM) {
 2743         btrfs_release_path(path);
 2744         ret = btrfs_search_slot(NULL, root, &last_key, path, 0, 0);
 2745         if (ret)
 2746             return err;
 2747     }
 2748 
 2749     /* verify INODE_ITEM nlink/isize/nbytes */
 2750     if (dir) {
 2751         if (repair && (err & DIR_COUNT_AGAIN)) {
 2752             err &= ~DIR_COUNT_AGAIN;
 2753             count_dir_isize(root, inode_id, &size);
 2754         }
 2755 
 2756         if ((nlink != 1 || refs != 1) && repair) {
 2757             ret = repair_inode_nlinks_lowmem(root, path, inode_id,
 2758                 namebuf, name_len, refs, imode_to_type(mode),
 2759                 &nlink);
 2760         }
 2761 
 2762         if (nlink != 1) {
 2763             err |= LINK_COUNT_ERROR;
 2764             error("root %llu DIR INODE[%llu] shouldn't have more than one link(%llu)",
 2765                   root->objectid, inode_id, nlink);
 2766         }
 2767 
 2768         /*
 2769          * Just a warning, as dir inode nbytes is just an
 2770          * instructive value.
 2771          */
 2772         if (!IS_ALIGNED(nbytes, root->fs_info->nodesize)) {
 2773             warning("root %llu DIR INODE[%llu] nbytes should be aligned to %u",
 2774                 root->objectid, inode_id,
 2775                 root->fs_info->nodesize);
 2776         }
 2777 
 2778         if (isize != size) {
 2779             if (repair)
 2780                 ret = repair_dir_isize_lowmem(root, path,
 2781                                   inode_id, size);
 2782             if (!repair || ret) {
 2783                 err |= ISIZE_ERROR;
 2784                 error(
 2785         "root %llu DIR INODE [%llu] size %llu not equal to %llu",
 2786                       root->objectid, inode_id, isize, size);
 2787             }
 2788         }
 2789     } else {
 2790         if (nlink != refs) {
 2791             if (repair)
 2792                 ret = repair_inode_nlinks_lowmem(root, path,
 2793                      inode_id, namebuf, name_len, refs,
 2794                      imode_to_type(mode), &nlink);
 2795             if (!repair || ret) {
 2796                 err |= LINK_COUNT_ERROR;
 2797                 error(
 2798         "root %llu INODE[%llu] nlink(%llu) not equal to inode_refs(%llu)",
 2799                       root->objectid, inode_id, nlink, refs);
 2800             }
 2801         } else if (!nlink && !is_orphan) {
 2802             if (repair)
 2803                 ret = repair_inode_orphan_item_lowmem(root,
 2804                                   path, inode_id);
 2805             if (!repair || ret) {
 2806                 err |= ORPHAN_ITEM;
 2807                 error("root %llu INODE[%llu] is orphan item",
 2808                       root->objectid, inode_id);
 2809             }
 2810         }
 2811 
 2812         /*
 2813          * For orhpan inode, updating nbytes/size is just a waste of
 2814          * time, so skip such repair and don't report them as error.
 2815          */
 2816         if (nbytes != extent_size && !is_orphan) {
 2817             if (repair) {
 2818                 ret = repair_inode_nbytes_lowmem(root, path,
 2819                              inode_id, extent_size);
 2820                 if (!ret)
 2821                     nbytes = extent_size;
 2822             }
 2823             if (!repair || ret) {
 2824                 err |= NBYTES_ERROR;
 2825                 error(
 2826     "root %llu INODE[%llu] nbytes %llu not equal to extent_size %llu",
 2827                       root->objectid, inode_id, nbytes,
 2828                       extent_size);
 2829             }
 2830         }
 2831 
 2832         if (!nbytes && !no_holes && extent_end < isize) {
 2833             if (repair)
 2834                 ret = punch_extent_hole(root, path, inode_id,
 2835                         extent_end, isize - extent_end);
 2836             if (!repair || ret) {
 2837                 err |= NBYTES_ERROR;
 2838                 error(
 2839     "root %llu INODE[%llu] size %llu should have a file extent hole",
 2840                       root->objectid, inode_id, isize);
 2841             }
 2842         }
 2843     }
 2844 
 2845     if (err & LAST_ITEM)
 2846         btrfs_next_item(root, path);
 2847     return err;
 2848 }
 2849 
 2850 /*
 2851  * Returns >0  Found error, not fatal, should continue
 2852  * Returns <0  Fatal error, must exit the whole check
 2853  * Returns 0   No errors found
 2854  */
 2855 static int process_one_leaf(struct btrfs_root *root, struct btrfs_path *path,
 2856                 struct node_refs *nrefs, int *level)
 2857 {
 2858     struct extent_buffer *cur = path->nodes[0];
 2859     struct btrfs_key key;
 2860     u64 cur_bytenr;
 2861     u32 nritems;
 2862     u64 first_ino = 0;
 2863     int root_level = btrfs_header_level(root->node);
 2864     int i;
 2865     int ret = 0; /* Final return value */
 2866     int err = 0; /* Positive error bitmap */
 2867 
 2868     cur_bytenr = cur->start;
 2869 
 2870     /* skip to first inode item or the first inode number change */
 2871     nritems = btrfs_header_nritems(cur);
 2872     for (i = 0; i < nritems; i++) {
 2873         btrfs_item_key_to_cpu(cur, &key, i);
 2874         if (i == 0)
 2875             first_ino = key.objectid;
 2876         if (key.type == BTRFS_INODE_ITEM_KEY ||
 2877             (first_ino && first_ino != key.objectid))
 2878             break;
 2879     }
 2880     if (i == nritems) {
 2881         path->slots[0] = nritems;
 2882         return 0;
 2883     }
 2884     path->slots[0] = i;
 2885 
 2886 again:
 2887     err |= check_inode_item(root, path);
 2888 
 2889     /* modify cur since check_inode_item may change path */
 2890     cur = path->nodes[0];
 2891 
 2892     if (err & LAST_ITEM)
 2893         goto out;
 2894 
 2895     /* still have inode items in this leaf */
 2896     if (cur->start == cur_bytenr)
 2897         goto again;
 2898 
 2899     /*
 2900      * we have switched to another leaf, above nodes may
 2901      * have changed, here walk down the path, if a node
 2902      * or leaf is shared, check whether we can skip this
 2903      * node or leaf.
 2904      */
 2905     for (i = root_level; i >= 0; i--) {
 2906         if (path->nodes[i]->start == nrefs->bytenr[i])
 2907             continue;
 2908 
 2909         ret = update_nodes_refs(root, path->nodes[i]->start,
 2910                 path->nodes[i], nrefs, i, 0);
 2911         if (ret)
 2912             goto out;
 2913 
 2914         if (!nrefs->need_check[i]) {
 2915             *level += 1;
 2916             break;
 2917         }
 2918     }
 2919 
 2920     for (i = 0; i < *level; i++) {
 2921         free_extent_buffer(path->nodes[i]);
 2922         path->nodes[i] = NULL;
 2923     }
 2924 out:
 2925     err &= ~LAST_ITEM;
 2926     if (err && !ret)
 2927         ret = err;
 2928     return ret;
 2929 }
 2930 
 2931 /*
 2932  * @level           if @level == -1 means extent data item
 2933  *                  else normal treeblock.
 2934  */
 2935 static int should_check_extent_strictly(struct btrfs_root *root,
 2936                     struct node_refs *nrefs, int level)
 2937 {
 2938     int root_level = btrfs_header_level(root->node);
 2939 
 2940     if (level > root_level || level < -1)
 2941         return 1;
 2942     if (level == root_level)
 2943         return 1;
 2944     /*
 2945      * if the upper node is marked full backref, it should contain shared
 2946      * backref of the parent (except owner == root->objectid).
 2947      */
 2948     while (++level <= root_level)
 2949         if (nrefs->refs[level] > 1)
 2950             return 0;
 2951 
 2952     return 1;
 2953 }
 2954 
 2955 static int check_extent_inline_ref(struct extent_buffer *eb,
 2956            struct btrfs_key *key, struct btrfs_extent_inline_ref *iref)
 2957 {
 2958     int ret;
 2959     u8 type = btrfs_extent_inline_ref_type(eb, iref);
 2960 
 2961     switch (type) {
 2962     case BTRFS_TREE_BLOCK_REF_KEY:
 2963     case BTRFS_EXTENT_DATA_REF_KEY:
 2964     case BTRFS_SHARED_BLOCK_REF_KEY:
 2965     case BTRFS_SHARED_DATA_REF_KEY:
 2966         ret = 0;
 2967         break;
 2968     default:
 2969         error("extent[%llu %u %llu] has unknown ref type: %d",
 2970               key->objectid, key->type, key->offset, type);
 2971         ret = UNKNOWN_TYPE;
 2972         break;
 2973     }
 2974 
 2975     return ret;
 2976 }
 2977 
 2978 /*
 2979  * Check backrefs of a tree block given by @bytenr or @eb.
 2980  *
 2981  * @root:   the root containing the @bytenr or @eb
 2982  * @eb:     tree block extent buffer, can be NULL
 2983  * @bytenr: bytenr of the tree block to search
 2984  * @level:  tree level of the tree block
 2985  * @owner:  owner of the tree block
 2986  *
 2987  * Return >0 for any error found and output error message
 2988  * Return 0 for no error found
 2989  */
 2990 static int check_tree_block_ref(struct btrfs_root *root,
 2991                 struct extent_buffer *eb, u64 bytenr,
 2992                 int level, u64 owner, struct node_refs *nrefs)
 2993 {
 2994     struct btrfs_key key;
 2995     struct btrfs_root *extent_root = root->fs_info->extent_root;
 2996     struct btrfs_path path;
 2997     struct btrfs_extent_item *ei;
 2998     struct btrfs_extent_inline_ref *iref;
 2999     struct extent_buffer *leaf;
 3000     unsigned long end;
 3001     unsigned long ptr;
 3002     int slot;
 3003     int skinny_level;
 3004     int root_level = btrfs_header_level(root->node);
 3005     int type;
 3006     u32 nodesize = root->fs_info->nodesize;
 3007     u32 item_size;
 3008     u64 offset;
 3009     int found_ref = 0;
 3010     int err = 0;
 3011     int ret;
 3012     int strict = 1;
 3013     int parent = 0;
 3014 
 3015     btrfs_init_path(&path);
 3016     key.objectid = bytenr;
 3017     if (btrfs_fs_incompat(root->fs_info, SKINNY_METADATA))
 3018         key.type = BTRFS_METADATA_ITEM_KEY;
 3019     else
 3020         key.type = BTRFS_EXTENT_ITEM_KEY;
 3021     key.offset = (u64)-1;
 3022 
 3023     /* Search for the backref in extent tree */
 3024     ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
 3025     if (ret < 0) {
 3026         err |= BACKREF_MISSING;
 3027         goto out;
 3028     }
 3029     ret = btrfs_previous_extent_item(extent_root, &path, bytenr);
 3030     if (ret) {
 3031         err |= BACKREF_MISSING;
 3032         goto out;
 3033     }
 3034 
 3035     leaf = path.nodes[0];
 3036     slot = path.slots[0];
 3037     btrfs_item_key_to_cpu(leaf, &key, slot);
 3038 
 3039     ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
 3040 
 3041     if (key.type == BTRFS_METADATA_ITEM_KEY) {
 3042         skinny_level = (int)key.offset;
 3043         iref = (struct btrfs_extent_inline_ref *)(ei + 1);
 3044     } else {
 3045         struct btrfs_tree_block_info *info;
 3046 
 3047         info = (struct btrfs_tree_block_info *)(ei + 1);
 3048         skinny_level = btrfs_tree_block_level(leaf, info);
 3049         iref = (struct btrfs_extent_inline_ref *)(info + 1);
 3050     }
 3051 
 3052 
 3053     if (eb) {
 3054         u64 header_gen;
 3055         u64 extent_gen;
 3056 
 3057         /*
 3058          * Due to the feature of shared tree blocks, if the upper node
 3059          * is a fs root or shared node, the extent of checked node may
 3060          * not be updated until the next CoW.
 3061          */
 3062         if (nrefs)
 3063             strict = should_check_extent_strictly(root, nrefs,
 3064                     level);
 3065         if (!(btrfs_extent_flags(leaf, ei) &
 3066               BTRFS_EXTENT_FLAG_TREE_BLOCK)) {
 3067             error(
 3068         "extent[%llu %u] backref type mismatch, missing bit: %llx",
 3069                 key.objectid, nodesize,
 3070                 BTRFS_EXTENT_FLAG_TREE_BLOCK);
 3071             err = BACKREF_MISMATCH;
 3072         }
 3073         header_gen = btrfs_header_generation(eb);
 3074         extent_gen = btrfs_extent_generation(leaf, ei);
 3075         if (header_gen != extent_gen) {
 3076             error(
 3077     "extent[%llu %u] backref generation mismatch, wanted: %llu, have: %llu",
 3078                 key.objectid, nodesize, header_gen,
 3079                 extent_gen);
 3080             err = BACKREF_MISMATCH;
 3081         }
 3082         if (level != skinny_level) {
 3083             error(
 3084             "extent[%llu %u] level mismatch, wanted: %u, have: %u",
 3085                 key.objectid, nodesize, level, skinny_level);
 3086             err = BACKREF_MISMATCH;
 3087         }
 3088         if (!is_fstree(owner) && btrfs_extent_refs(leaf, ei) != 1) {
 3089             error(
 3090             "extent[%llu %u] is referred by other roots than %llu",
 3091                 key.objectid, nodesize, root->objectid);
 3092             err = BACKREF_MISMATCH;
 3093         }
 3094     }
 3095 
 3096     /*
 3097      * Iterate the extent/metadata item to find the exact backref
 3098      */
 3099     item_size = btrfs_item_size_nr(leaf, slot);
 3100     ptr = (unsigned long)iref;
 3101     end = (unsigned long)ei + item_size;
 3102 
 3103     while (ptr < end) {
 3104         iref = (struct btrfs_extent_inline_ref *)ptr;
 3105         type = btrfs_extent_inline_ref_type(leaf, iref);
 3106         offset = btrfs_extent_inline_ref_offset(leaf, iref);
 3107 
 3108         ret = check_extent_inline_ref(leaf, &key, iref);
 3109         if (ret) {
 3110             err |= ret;
 3111             break;
 3112         }
 3113         if (type == BTRFS_TREE_BLOCK_REF_KEY) {
 3114             if (offset == root->objectid)
 3115                 found_ref = 1;
 3116             if (!strict && owner == offset)
 3117                 found_ref = 1;
 3118         } else if (type == BTRFS_SHARED_BLOCK_REF_KEY) {
 3119             /*
 3120              * Backref of tree reloc root points to itself, no need
 3121              * to check backref any more.
 3122              *
 3123              * This may be an error of loop backref, but extent tree
 3124              * checker should have already handled it.
 3125              * Here we only need to avoid infinite iteration.
 3126              */
 3127             if (offset == bytenr) {
 3128                 found_ref = 1;
 3129             } else {
 3130                 /*
 3131                  * Check if the backref points to valid
 3132                  * referencer
 3133                  */
 3134                 found_ref = !check_tree_block_ref(root, NULL,
 3135                         offset, level + 1, owner, NULL);
 3136             }
 3137         }
 3138 
 3139         if (found_ref)
 3140             break;
 3141         ptr += btrfs_extent_inline_ref_size(type);
 3142     }
 3143 
 3144     /*
 3145      * Inlined extent item doesn't have what we need, check
 3146      * TREE_BLOCK_REF_KEY
 3147      */
 3148     if (!found_ref) {
 3149         btrfs_release_path(&path);
 3150         key.objectid = bytenr;
 3151         key.type = BTRFS_TREE_BLOCK_REF_KEY;
 3152         key.offset = root->objectid;
 3153 
 3154         ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
 3155         if (!ret)
 3156             found_ref = 1;
 3157     }
 3158     /*
 3159      * Finally check SHARED BLOCK REF, any found will be good
 3160      * Here we're not doing comprehensive extent backref checking,
 3161      * only need to ensure there is some extent referring to this
 3162      * tree block.
 3163      */
 3164     if (!found_ref) {
 3165         btrfs_release_path(&path);
 3166         key.objectid = bytenr;
 3167         key.type = BTRFS_SHARED_BLOCK_REF_KEY;
 3168         key.offset = (u64)-1;
 3169 
 3170         ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
 3171         if (ret < 0) {
 3172             err |= BACKREF_MISSING;
 3173             goto out;
 3174         }
 3175         ret = btrfs_previous_extent_item(extent_root, &path, bytenr);
 3176         if (ret) {
 3177             err |= BACKREF_MISSING;
 3178             goto out;
 3179         }
 3180         found_ref = 1;
 3181     }
 3182     if (!found_ref)
 3183         err |= BACKREF_MISSING;
 3184 out:
 3185     btrfs_release_path(&path);
 3186     if (nrefs && strict &&
 3187         level < root_level && nrefs->full_backref[level + 1])
 3188         parent = nrefs->bytenr[level + 1];
 3189     if (eb && (err & BACKREF_MISSING))
 3190         error(
 3191     "extent[%llu %u] backref lost (owner: %llu, level: %u) %s %llu",
 3192               bytenr, nodesize, owner, level,
 3193               parent ? "parent" : "root",
 3194               parent ? parent : root->objectid);
 3195     return err;
 3196 }
 3197 
 3198 /*
 3199  * If @err contains BYTES_UNALIGNED then delete the extent data item.
 3200  * If @err contains BACKREF_MISSING then add extent of the
 3201  * file_extent_data_item.
 3202  *
 3203  * Returns error bits after reapir.
 3204  */
 3205 static int repair_extent_data_item(struct btrfs_root *root,
 3206                    struct btrfs_path *pathp,
 3207                    struct node_refs *nrefs,
 3208                    int err)
 3209 {
 3210     struct btrfs_trans_handle *trans = NULL;
 3211     struct btrfs_file_extent_item *fi;
 3212     struct btrfs_key fi_key;
 3213     struct btrfs_key key;
 3214     struct btrfs_extent_item *ei;
 3215     struct btrfs_path path;
 3216     struct btrfs_root *extent_root = root->fs_info->extent_root;
 3217     struct extent_buffer *eb;
 3218     u64 size;
 3219     u64 disk_bytenr;
 3220     u64 num_bytes;
 3221     u64 parent;
 3222     u64 offset;
 3223     u64 extent_offset;
 3224     u64 file_offset;
 3225     int generation;
 3226     int slot;
 3227     int need_insert = 0;
 3228     int ret = 0;
 3229 
 3230     eb = pathp->nodes[0];
 3231     slot = pathp->slots[0];
 3232     btrfs_item_key_to_cpu(eb, &fi_key, slot);
 3233     fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
 3234 
 3235     if (btrfs_file_extent_type(eb, fi) == BTRFS_FILE_EXTENT_INLINE ||
 3236         btrfs_file_extent_disk_bytenr(eb, fi) == 0)
 3237         return err;
 3238 
 3239     file_offset = fi_key.offset;
 3240     generation = btrfs_file_extent_generation(eb, fi);
 3241     disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
 3242     num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
 3243     extent_offset = btrfs_file_extent_offset(eb, fi);
 3244     offset = file_offset - extent_offset;
 3245 
 3246     if (nrefs->full_backref[0])
 3247         parent = btrfs_header_bytenr(eb);
 3248     else
 3249         parent = 0;
 3250 
 3251     if (err & BYTES_UNALIGNED) {
 3252         ret = delete_item(root, pathp);
 3253         if (!ret)
 3254             err = 0;
 3255         goto out;
 3256     }
 3257 
 3258     /* now repair only adds backref */
 3259     if ((err & BACKREF_MISSING) == 0)
 3260         return err;
 3261 
 3262     /* search extent item */
 3263     key.objectid = disk_bytenr;
 3264     key.type = BTRFS_EXTENT_ITEM_KEY;
 3265     key.offset = num_bytes;
 3266 
 3267     btrfs_init_path(&path);
 3268     ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
 3269     if (ret < 0) {
 3270         ret = -EIO;
 3271         goto out;
 3272     }
 3273     need_insert = ret;
 3274 
 3275     ret = avoid_extents_overwrite(root->fs_info);
 3276     if (ret)
 3277         goto out;
 3278     trans = btrfs_start_transaction(root, 1);
 3279     if (IS_ERR(trans)) {
 3280         ret = PTR_ERR(trans);
 3281         trans = NULL;
 3282         errno = -ret;
 3283         error("fail to start transaction: %m");
 3284         goto out;
 3285     }
 3286     /* insert an extent item */
 3287     if (need_insert) {
 3288         key.objectid = disk_bytenr;
 3289         key.type = BTRFS_EXTENT_ITEM_KEY;
 3290         key.offset = num_bytes;
 3291         size = sizeof(*ei);
 3292 
 3293         btrfs_release_path(&path);
 3294         ret = btrfs_insert_empty_item(trans, extent_root, &path, &key,
 3295                           size);
 3296         if (ret)
 3297             goto out;
 3298         eb = path.nodes[0];
 3299         ei = btrfs_item_ptr(eb, path.slots[0], struct btrfs_extent_item);
 3300 
 3301         btrfs_set_extent_refs(eb, ei, 0);
 3302         btrfs_set_extent_generation(eb, ei, generation);
 3303         btrfs_set_extent_flags(eb, ei, BTRFS_EXTENT_FLAG_DATA);
 3304 
 3305         btrfs_mark_buffer_dirty(eb);
 3306         ret = btrfs_update_block_group(extent_root, disk_bytenr,
 3307                            num_bytes, 1, 0);
 3308         btrfs_release_path(&path);
 3309     }
 3310 
 3311     ret = btrfs_inc_extent_ref(trans, root, disk_bytenr, num_bytes, parent,
 3312                    root->objectid,
 3313            parent ? BTRFS_FIRST_FREE_OBJECTID : fi_key.objectid,
 3314                    offset);
 3315     if (ret) {
 3316         error(
 3317         "failed to increase extent data backref[%llu %llu] root %llu",
 3318               disk_bytenr, num_bytes, root->objectid);
 3319         goto out;
 3320     } else {
 3321         printf("Add one extent data backref [%llu %llu]\n",
 3322                disk_bytenr, num_bytes);
 3323     }
 3324 
 3325     err &= ~BACKREF_MISSING;
 3326 out:
 3327     if (trans)
 3328         btrfs_commit_transaction(trans, root);
 3329     btrfs_release_path(&path);
 3330     if (ret)
 3331         error("can't repair root %llu extent data item[%llu %llu]",
 3332               root->objectid, disk_bytenr, num_bytes);
 3333     return err;
 3334 }
 3335 
 3336 /*
 3337  * Check EXTENT_DATA item, mainly for its dbackref in extent tree
 3338  *
 3339  * Return >0 any error found and output error message
 3340  * Return 0 for no error found
 3341  */
 3342 static int check_extent_data_item(struct btrfs_root *root,
 3343                   struct btrfs_path *pathp,
 3344                   struct node_refs *nrefs,  int account_bytes)
 3345 {
 3346     struct btrfs_file_extent_item *fi;
 3347     struct extent_buffer *eb = pathp->nodes[0];
 3348     struct btrfs_path path;
 3349     struct btrfs_root *extent_root = root->fs_info->extent_root;
 3350     struct btrfs_key fi_key;
 3351     struct btrfs_key dbref_key;
 3352     struct extent_buffer *leaf;
 3353     struct btrfs_extent_item *ei;
 3354     struct btrfs_extent_inline_ref *iref;
 3355     struct btrfs_extent_data_ref *dref;
 3356     u64 owner;
 3357     u64 disk_bytenr;
 3358     u64 disk_num_bytes;
 3359     u64 extent_num_bytes;
 3360     u64 extent_flags;
 3361     u64 offset;
 3362     u32 item_size;
 3363     unsigned long end;
 3364     unsigned long ptr;
 3365     int type;
 3366     int found_dbackref = 0;
 3367     int slot = pathp->slots[0];
 3368     int err = 0;
 3369     int ret;
 3370     int strict;
 3371 
 3372     btrfs_item_key_to_cpu(eb, &fi_key, slot);
 3373     fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
 3374 
 3375     /* Nothing to check for hole and inline data extents */
 3376     if (btrfs_file_extent_type(eb, fi) == BTRFS_FILE_EXTENT_INLINE ||
 3377         btrfs_file_extent_disk_bytenr(eb, fi) == 0)
 3378         return 0;
 3379 
 3380     disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
 3381     disk_num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
 3382     extent_num_bytes = btrfs_file_extent_num_bytes(eb, fi);
 3383     offset = btrfs_file_extent_offset(eb, fi);
 3384 
 3385     /* Check unaligned disk_bytenr, disk_num_bytes and num_bytes */
 3386     if (!IS_ALIGNED(disk_bytenr, root->fs_info->sectorsize)) {
 3387         error(
 3388 "file extent [%llu, %llu] has unaligned disk bytenr: %llu, should be aligned to %u",
 3389             fi_key.objectid, fi_key.offset, disk_bytenr,
 3390             root->fs_info->sectorsize);
 3391         err |= BYTES_UNALIGNED;
 3392     }
 3393     if (!IS_ALIGNED(disk_num_bytes, root->fs_info->sectorsize)) {
 3394         error(
 3395 "file extent [%llu, %llu] has unaligned disk num bytes: %llu, should be aligned to %u",
 3396             fi_key.objectid, fi_key.offset, disk_num_bytes,
 3397             root->fs_info->sectorsize);
 3398         err |= BYTES_UNALIGNED;
 3399     } else if (account_bytes) {
 3400         data_bytes_allocated += disk_num_bytes;
 3401     }
 3402     if (!IS_ALIGNED(extent_num_bytes, root->fs_info->sectorsize)) {
 3403         error(
 3404 "file extent [%llu, %llu] has unaligned num bytes: %llu, should be aligned to %u",
 3405             fi_key.objectid, fi_key.offset, extent_num_bytes,
 3406             root->fs_info->sectorsize);
 3407         err |= BYTES_UNALIGNED;
 3408     } else if (account_bytes) {
 3409         data_bytes_referenced += extent_num_bytes;
 3410     }
 3411     owner = btrfs_header_owner(eb);
 3412 
 3413     /* Check the extent item of the file extent in extent tree */
 3414     btrfs_init_path(&path);
 3415     dbref_key.objectid = btrfs_file_extent_disk_bytenr(eb, fi);
 3416     dbref_key.type = BTRFS_EXTENT_ITEM_KEY;
 3417     dbref_key.offset = btrfs_file_extent_disk_num_bytes(eb, fi);
 3418 
 3419     ret = btrfs_search_slot(NULL, extent_root, &dbref_key, &path, 0, 0);
 3420     if (ret)
 3421         goto out;
 3422 
 3423     leaf = path.nodes[0];
 3424     slot = path.slots[0];
 3425     ei = btrfs_item_ptr(leaf, slot, struct btrfs_extent_item);
 3426 
 3427     extent_flags = btrfs_extent_flags(leaf, ei);
 3428 
 3429     if (!(extent_flags & BTRFS_EXTENT_FLAG_DATA)) {
 3430         error(
 3431 "file extent[%llu %llu] root %llu owner %llu backref type mismatch, wanted bit: %llx",
 3432             fi_key.objectid, fi_key.offset, root->objectid, owner,
 3433             BTRFS_EXTENT_FLAG_DATA);
 3434         err |= BACKREF_MISMATCH;
 3435     }
 3436 
 3437     /* Check data backref inside that extent item */
 3438     item_size = btrfs_item_size_nr(leaf, path.slots[0]);
 3439     iref = (struct btrfs_extent_inline_ref *)(ei + 1);
 3440     ptr = (unsigned long)iref;
 3441     end = (unsigned long)ei + item_size;
 3442     strict = should_check_extent_strictly(root, nrefs, -1);
 3443 
 3444     while (ptr < end) {
 3445         u64 ref_root;
 3446         u64 ref_objectid;
 3447         u64 ref_offset;
 3448         bool match = false;
 3449 
 3450         iref = (struct btrfs_extent_inline_ref *)ptr;
 3451         type = btrfs_extent_inline_ref_type(leaf, iref);
 3452         dref = (struct btrfs_extent_data_ref *)(&iref->offset);
 3453 
 3454         ret = check_extent_inline_ref(leaf, &dbref_key, iref);
 3455         if (ret) {
 3456             err |= ret;
 3457             break;
 3458         }
 3459         if (type == BTRFS_EXTENT_DATA_REF_KEY) {
 3460             ref_root = btrfs_extent_data_ref_root(leaf, dref);
 3461             ref_objectid = btrfs_extent_data_ref_objectid(leaf,
 3462                                       dref);
 3463             ref_offset = btrfs_extent_data_ref_offset(leaf, dref);
 3464 
 3465             if (ref_objectid == fi_key.objectid &&
 3466                 ref_offset == fi_key.offset - offset)
 3467                 match = true;
 3468             if (ref_root == root->objectid && match)
 3469                 found_dbackref = 1;
 3470             else if (!strict && owner == ref_root && match)
 3471                 found_dbackref = 1;
 3472         } else if (type == BTRFS_SHARED_DATA_REF_KEY) {
 3473             found_dbackref = !check_tree_block_ref(root, NULL,
 3474                 btrfs_extent_inline_ref_offset(leaf, iref),
 3475                 0, owner, NULL);
 3476         }
 3477 
 3478         if (found_dbackref)
 3479             break;
 3480         ptr += btrfs_extent_inline_ref_size(type);
 3481     }
 3482 
 3483     if (!found_dbackref) {
 3484         btrfs_release_path(&path);
 3485 
 3486         /* Didn't find inlined data backref, try EXTENT_DATA_REF_KEY */
 3487         dbref_key.objectid = btrfs_file_extent_disk_bytenr(eb, fi);
 3488         dbref_key.type = BTRFS_EXTENT_DATA_REF_KEY;
 3489         dbref_key.offset = hash_extent_data_ref(owner, fi_key.objectid,
 3490                             fi_key.offset - offset);
 3491 
 3492         ret = btrfs_search_slot(NULL, root->fs_info->extent_root,
 3493                     &dbref_key, &path, 0, 0);
 3494         if (!ret) {
 3495             found_dbackref = 1;
 3496             goto out;
 3497         }
 3498 
 3499         btrfs_release_path(&path);
 3500 
 3501         /*
 3502          * Neither inlined nor EXTENT_DATA_REF found, try
 3503          * SHARED_DATA_REF as last chance.
 3504          */
 3505         dbref_key.objectid = disk_bytenr;
 3506         dbref_key.type = BTRFS_SHARED_DATA_REF_KEY;
 3507         dbref_key.offset = eb->start;
 3508 
 3509         ret = btrfs_search_slot(NULL, root->fs_info->extent_root,
 3510                     &dbref_key, &path, 0, 0);
 3511         if (!ret) {
 3512             found_dbackref = 1;
 3513             goto out;
 3514         }
 3515     }
 3516 
 3517 out:
 3518     if (!found_dbackref)
 3519         err |= BACKREF_MISSING;
 3520     btrfs_release_path(&path);
 3521     if (err & BACKREF_MISSING) {
 3522         error(
 3523         "file extent[%llu %llu] root %llu owner %llu backref lost",
 3524             fi_key.objectid, fi_key.offset, root->objectid, owner);
 3525     }
 3526     return err;
 3527 }
 3528 
 3529 /*
 3530  * Check a block group item with its referener (chunk) and its used space
 3531  * with extent/metadata item
 3532  */
 3533 static int check_block_group_item(struct btrfs_fs_info *fs_info,
 3534                   struct extent_buffer *eb, int slot)
 3535 {
 3536     struct btrfs_root *extent_root = fs_info->extent_root;
 3537     struct btrfs_root *chunk_root = fs_info->chunk_root;
 3538     struct btrfs_block_group_item *bi;
 3539     struct btrfs_block_group_item bg_item;
 3540     struct btrfs_path path;
 3541     struct btrfs_key bg_key;
 3542     struct btrfs_key chunk_key;
 3543     struct btrfs_key extent_key;
 3544     struct btrfs_chunk *chunk;
 3545     struct extent_buffer *leaf;
 3546     struct btrfs_extent_item *ei;
 3547     u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
 3548     u64 flags;
 3549     u64 bg_flags;
 3550     u64 used;
 3551     u64 total = 0;
 3552     int ret;
 3553     int err = 0;
 3554 
 3555     btrfs_item_key_to_cpu(eb, &bg_key, slot);
 3556     bi = btrfs_item_ptr(eb, slot, struct btrfs_block_group_item);
 3557     read_extent_buffer(eb, &bg_item, (unsigned long)bi, sizeof(bg_item));
 3558     used = btrfs_block_group_used(&bg_item);
 3559     bg_flags = btrfs_block_group_flags(&bg_item);
 3560 
 3561     chunk_key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
 3562     chunk_key.type = BTRFS_CHUNK_ITEM_KEY;
 3563     chunk_key.offset = bg_key.objectid;
 3564 
 3565     btrfs_init_path(&path);
 3566     /* Search for the referencer chunk */
 3567     ret = btrfs_search_slot(NULL, chunk_root, &chunk_key, &path, 0, 0);
 3568     if (ret) {
 3569         error(
 3570         "block group[%llu %llu] did not find the related chunk item",
 3571             bg_key.objectid, bg_key.offset);
 3572         err |= REFERENCER_MISSING;
 3573     } else {
 3574         chunk = btrfs_item_ptr(path.nodes[0], path.slots[0],
 3575                     struct btrfs_chunk);
 3576         if (btrfs_chunk_length(path.nodes[0], chunk) !=
 3577                         bg_key.offset) {
 3578             error(
 3579     "block group[%llu %llu] related chunk item length does not match",
 3580                 bg_key.objectid, bg_key.offset);
 3581             err |= REFERENCER_MISMATCH;
 3582         }
 3583     }
 3584     btrfs_release_path(&path);
 3585 
 3586     /* Search from the block group bytenr */
 3587     extent_key.objectid = bg_key.objectid;
 3588     extent_key.type = 0;
 3589     extent_key.offset = 0;
 3590 
 3591     btrfs_init_path(&path);
 3592     ret = btrfs_search_slot(NULL, extent_root, &extent_key, &path, 0, 0);
 3593     if (ret < 0)
 3594         goto out;
 3595 
 3596     /* Iterate extent tree to account used space */
 3597     while (1) {
 3598         leaf = path.nodes[0];
 3599 
 3600         /* Search slot can point to the last item beyond leaf nritems */
 3601         if (path.slots[0] >= btrfs_header_nritems(leaf))
 3602             goto next;
 3603 
 3604         btrfs_item_key_to_cpu(leaf, &extent_key, path.slots[0]);
 3605         if (extent_key.objectid >= bg_key.objectid + bg_key.offset)
 3606             break;
 3607 
 3608         if (extent_key.type != BTRFS_METADATA_ITEM_KEY &&
 3609             extent_key.type != BTRFS_EXTENT_ITEM_KEY)
 3610             goto next;
 3611         if (extent_key.objectid < bg_key.objectid)
 3612             goto next;
 3613 
 3614         if (extent_key.type == BTRFS_METADATA_ITEM_KEY)
 3615             total += nodesize;
 3616         else
 3617             total += extent_key.offset;
 3618 
 3619         ei = btrfs_item_ptr(leaf, path.slots[0],
 3620                     struct btrfs_extent_item);
 3621         flags = btrfs_extent_flags(leaf, ei);
 3622         if (flags & BTRFS_EXTENT_FLAG_DATA) {
 3623             if (!(bg_flags & BTRFS_BLOCK_GROUP_DATA)) {
 3624                 error(
 3625             "bad extent[%llu, %llu) type mismatch with chunk",
 3626                       extent_key.objectid,
 3627                       extent_key.objectid + extent_key.offset);
 3628                 err |= CHUNK_TYPE_MISMATCH;
 3629             }
 3630         } else if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK) {
 3631             if (!(bg_flags & (BTRFS_BLOCK_GROUP_SYSTEM |
 3632                     BTRFS_BLOCK_GROUP_METADATA))) {
 3633                 error(
 3634             "bad extent[%llu, %llu) type mismatch with chunk",
 3635                     extent_key.objectid,
 3636                     extent_key.objectid + nodesize);
 3637                 err |= CHUNK_TYPE_MISMATCH;
 3638             }
 3639         }
 3640 next:
 3641         ret = btrfs_next_item(extent_root, &path);
 3642         if (ret)
 3643             break;
 3644     }
 3645 
 3646 out:
 3647     btrfs_release_path(&path);
 3648 
 3649     if (total != used) {
 3650         error(
 3651         "block group[%llu %llu] used %llu but extent items used %llu",
 3652             bg_key.objectid, bg_key.offset, used, total);
 3653         err |= BG_ACCOUNTING_ERROR;
 3654     }
 3655     return err;
 3656 }
 3657 
 3658 /*
 3659  * Get real tree block level for the case like shared block
 3660  * Return >= 0 as tree level
 3661  * Return <0 for error
 3662  */
 3663 static int query_tree_block_level(struct btrfs_fs_info *fs_info, u64 bytenr)
 3664 {
 3665     struct extent_buffer *eb;
 3666     struct btrfs_path path;
 3667     struct btrfs_key key;
 3668     struct btrfs_extent_item *ei;
 3669     u64 flags;
 3670     u64 transid;
 3671     u8 backref_level;
 3672     u8 header_level;
 3673     int ret;
 3674 
 3675     /* Search extent tree for extent generation and level */
 3676     key.objectid = bytenr;
 3677     key.type = BTRFS_METADATA_ITEM_KEY;
 3678     key.offset = (u64)-1;
 3679 
 3680     btrfs_init_path(&path);
 3681     ret = btrfs_search_slot(NULL, fs_info->extent_root, &key, &path, 0, 0);
 3682     if (ret < 0)
 3683         goto release_out;
 3684     ret = btrfs_previous_extent_item(fs_info->extent_root, &path, bytenr);
 3685     if (ret < 0)
 3686         goto release_out;
 3687     if (ret > 0) {
 3688         ret = -ENOENT;
 3689         goto release_out;
 3690     }
 3691 
 3692     btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
 3693     ei = btrfs_item_ptr(path.nodes[0], path.slots[0],
 3694                 struct btrfs_extent_item);
 3695     flags = btrfs_extent_flags(path.nodes[0], ei);
 3696     if (!(flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)) {
 3697         ret = -ENOENT;
 3698         goto release_out;
 3699     }
 3700 
 3701     /* Get transid for later read_tree_block() check */
 3702     transid = btrfs_extent_generation(path.nodes[0], ei);
 3703 
 3704     /* Get backref level as one source */
 3705     if (key.type == BTRFS_METADATA_ITEM_KEY) {
 3706         backref_level = key.offset;
 3707     } else {
 3708         struct btrfs_tree_block_info *info;
 3709 
 3710         info = (struct btrfs_tree_block_info *)(ei + 1);
 3711         backref_level = btrfs_tree_block_level(path.nodes[0], info);
 3712     }
 3713     btrfs_release_path(&path);
 3714 
 3715     /* Get level from tree block as an alternative source */
 3716     eb = read_tree_block(fs_info, bytenr, transid);
 3717     if (!extent_buffer_uptodate(eb)) {
 3718         free_extent_buffer(eb);
 3719         return -EIO;
 3720     }
 3721     header_level = btrfs_header_level(eb);
 3722     free_extent_buffer(eb);
 3723 
 3724     if (header_level != backref_level)
 3725         return -EIO;
 3726     return header_level;
 3727 
 3728 release_out:
 3729     btrfs_release_path(&path);
 3730     return ret;
 3731 }
 3732 
 3733 /*
 3734  * Check if a tree block backref is valid (points to a valid tree block)
 3735  * if level == -1, level will be resolved
 3736  * Return >0 for any error found and print error message
 3737  */
 3738 static int check_tree_block_backref(struct btrfs_fs_info *fs_info, u64 root_id,
 3739                     u64 bytenr, int level)
 3740 {
 3741     struct btrfs_root *root;
 3742     struct btrfs_key key;
 3743     struct btrfs_path path;
 3744     struct extent_buffer *eb;
 3745     struct extent_buffer *node;
 3746     u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
 3747     int err = 0;
 3748     int ret;
 3749 
 3750     /* Query level for level == -1 special case */
 3751     if (level == -1)
 3752         level = query_tree_block_level(fs_info, bytenr);
 3753     if (level < 0) {
 3754         err |= REFERENCER_MISSING;
 3755         goto out;
 3756     }
 3757 
 3758     key.objectid = root_id;
 3759     key.type = BTRFS_ROOT_ITEM_KEY;
 3760     key.offset = (u64)-1;
 3761 
 3762     root = btrfs_read_fs_root(fs_info, &key);
 3763     if (IS_ERR(root)) {
 3764         err |= REFERENCER_MISSING;
 3765         goto out;
 3766     }
 3767 
 3768     /* Read out the tree block to get item/node key */
 3769     eb = read_tree_block(fs_info, bytenr, 0);
 3770     if (!extent_buffer_uptodate(eb)) {
 3771         err |= REFERENCER_MISSING;
 3772         free_extent_buffer(eb);
 3773         goto out;
 3774     }
 3775 
 3776     /* Empty tree, no need to check key */
 3777     if (!btrfs_header_nritems(eb) && !level) {
 3778         free_extent_buffer(eb);
 3779         goto out;
 3780     }
 3781 
 3782     if (level)
 3783         btrfs_node_key_to_cpu(eb, &key, 0);
 3784     else
 3785         btrfs_item_key_to_cpu(eb, &key, 0);
 3786 
 3787     free_extent_buffer(eb);
 3788 
 3789     btrfs_init_path(&path);
 3790     path.lowest_level = level;
 3791     /* Search with the first key, to ensure we can reach it */
 3792     ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
 3793     if (ret < 0) {
 3794         err |= REFERENCER_MISSING;
 3795         goto release_out;
 3796     }
 3797 
 3798     node = path.nodes[level];
 3799     if (btrfs_header_bytenr(node) != bytenr) {
 3800         error(
 3801     "extent [%llu %d] referencer bytenr mismatch, wanted: %llu, have: %llu",
 3802             bytenr, nodesize, bytenr,
 3803             btrfs_header_bytenr(node));
 3804         err |= REFERENCER_MISMATCH;
 3805     }
 3806     if (btrfs_header_level(node) != level) {
 3807         error(
 3808     "extent [%llu %d] referencer level mismatch, wanted: %d, have: %d",
 3809             bytenr, nodesize, level,
 3810             btrfs_header_level(node));
 3811         err |= REFERENCER_MISMATCH;
 3812     }
 3813 
 3814 release_out:
 3815     btrfs_release_path(&path);
 3816 out:
 3817     if (err & REFERENCER_MISSING) {
 3818         if (level < 0)
 3819             error("extent [%llu %d] lost referencer (owner: %llu)",
 3820                 bytenr, nodesize, root_id);
 3821         else
 3822             error(
 3823         "extent [%llu %d] lost referencer (owner: %llu, level: %u)",
 3824                 bytenr, nodesize, root_id, level);
 3825     }
 3826 
 3827     return err;
 3828 }
 3829 
 3830 /*
 3831  * Check if tree block @eb is tree reloc root.
 3832  * Return 0 if it's not or any problem happens
 3833  * Return 1 if it's a tree reloc root
 3834  */
 3835 static int is_tree_reloc_root(struct btrfs_fs_info *fs_info,
 3836                  struct extent_buffer *eb)
 3837 {
 3838     struct btrfs_root *tree_reloc_root;
 3839     struct btrfs_key key;
 3840     u64 bytenr = btrfs_header_bytenr(eb);
 3841     u64 owner = btrfs_header_owner(eb);
 3842     int ret = 0;
 3843 
 3844     key.objectid = BTRFS_TREE_RELOC_OBJECTID;
 3845     key.offset = owner;
 3846     key.type = BTRFS_ROOT_ITEM_KEY;
 3847 
 3848     tree_reloc_root = btrfs_read_fs_root_no_cache(fs_info, &key);
 3849     if (IS_ERR(tree_reloc_root))
 3850         return 0;
 3851 
 3852     if (bytenr == btrfs_header_bytenr(tree_reloc_root->node))
 3853         ret = 1;
 3854     btrfs_free_fs_root(tree_reloc_root);
 3855     return ret;
 3856 }
 3857 
 3858 /*
 3859  * Check referencer for shared block backref
 3860  * If level == -1, this function will resolve the level.
 3861  */
 3862 static int check_shared_block_backref(struct btrfs_fs_info *fs_info,
 3863                      u64 parent, u64 bytenr, int level)
 3864 {
 3865     struct extent_buffer *eb;
 3866     u32 nr;
 3867     int found_parent = 0;
 3868     int i;
 3869 
 3870     eb = read_tree_block(fs_info, parent, 0);
 3871     if (!extent_buffer_uptodate(eb))
 3872         goto out;
 3873 
 3874     if (level == -1)
 3875         level = query_tree_block_level(fs_info, bytenr);
 3876     if (level < 0)
 3877         goto out;
 3878 
 3879     /* It's possible it's a tree reloc root */
 3880     if (parent == bytenr) {
 3881         if (is_tree_reloc_root(fs_info, eb))
 3882             found_parent = 1;
 3883         goto out;
 3884     }
 3885 
 3886     if (level + 1 != btrfs_header_level(eb))
 3887         goto out;
 3888 
 3889     nr = btrfs_header_nritems(eb);
 3890     for (i = 0; i < nr; i++) {
 3891         if (bytenr == btrfs_node_blockptr(eb, i)) {
 3892             found_parent = 1;
 3893             break;
 3894         }
 3895     }
 3896 out:
 3897     free_extent_buffer(eb);
 3898     if (!found_parent) {
 3899         error(
 3900     "shared extent[%llu %u] lost its parent (parent: %llu, level: %u)",
 3901             bytenr, fs_info->nodesize, parent, level);
 3902         return REFERENCER_MISSING;
 3903     }
 3904     return 0;
 3905 }
 3906 
 3907 /*
 3908  * Check referencer for normal (inlined) data ref
 3909  * If len == 0, it will be resolved by searching in extent tree
 3910  */
 3911 static int check_extent_data_backref(struct btrfs_fs_info *fs_info,
 3912                      u64 root_id, u64 objectid, u64 offset,
 3913                      u64 bytenr, u64 len, u32 count)
 3914 {
 3915     struct btrfs_root *root;
 3916     struct btrfs_root *extent_root = fs_info->extent_root;
 3917     struct btrfs_key key;
 3918     struct btrfs_path path;
 3919     struct extent_buffer *leaf;
 3920     struct btrfs_file_extent_item *fi;
 3921     u32 found_count = 0;
 3922     int slot;
 3923     int ret = 0;
 3924 
 3925     if (!len) {
 3926         key.objectid = bytenr;
 3927         key.type = BTRFS_EXTENT_ITEM_KEY;
 3928         key.offset = (u64)-1;
 3929 
 3930         btrfs_init_path(&path);
 3931         ret = btrfs_search_slot(NULL, extent_root, &key, &path, 0, 0);
 3932         if (ret < 0)
 3933             goto out;
 3934         ret = btrfs_previous_extent_item(extent_root, &path, bytenr);
 3935         if (ret)
 3936             goto out;
 3937         btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
 3938         if (key.objectid != bytenr ||
 3939             key.type != BTRFS_EXTENT_ITEM_KEY)
 3940             goto out;
 3941         len = key.offset;
 3942         btrfs_release_path(&path);
 3943     }
 3944     key.objectid = root_id;
 3945     key.type = BTRFS_ROOT_ITEM_KEY;
 3946     key.offset = (u64)-1;
 3947     btrfs_init_path(&path);
 3948 
 3949     root = btrfs_read_fs_root(fs_info, &key);
 3950     if (IS_ERR(root))
 3951         goto out;
 3952 
 3953     key.objectid = objectid;
 3954     key.type = BTRFS_EXTENT_DATA_KEY;
 3955     /*
 3956      * It can be nasty as data backref offset is
 3957      * file offset - file extent offset, which is smaller or
 3958      * equal to original backref offset.  The only special case is
 3959      * overflow.  So we need to special check and do further search.
 3960      */
 3961     key.offset = offset & (1ULL << 63) ? 0 : offset;
 3962 
 3963     ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
 3964     if (ret < 0)
 3965         goto out;
 3966 
 3967     /*
 3968      * Search afterwards to get correct one
 3969      * NOTE: As we must do a comprehensive check on the data backref to
 3970      * make sure the dref count also matches, we must iterate all file
 3971      * extents for that inode.
 3972      */
 3973     while (1) {
 3974         leaf = path.nodes[0];
 3975         slot = path.slots[0];
 3976 
 3977         if (slot >= btrfs_header_nritems(leaf) ||
 3978             btrfs_header_owner(leaf) != root_id)
 3979             goto next;
 3980         /*
 3981          * For tree blocks have been relocated, data backref are
 3982          * shared instead of keyed. Do not account it.
 3983          */
 3984         if (btrfs_header_flag(leaf, BTRFS_HEADER_FLAG_RELOC)) {
 3985             /*
 3986              * skip the leaf to speed up.
 3987              */
 3988             slot = btrfs_header_nritems(leaf);
 3989             goto next;
 3990         }
 3991 
 3992         btrfs_item_key_to_cpu(leaf, &key, slot);
 3993         if (key.objectid != objectid ||
 3994             key.type != BTRFS_EXTENT_DATA_KEY)
 3995             break;
 3996         fi = btrfs_item_ptr(leaf, slot, struct btrfs_file_extent_item);
 3997         /*
 3998          * Except normal disk bytenr and disk num bytes, we still
 3999          * need to do extra check on dbackref offset as
 4000          * dbackref offset = file_offset - file_extent_offset
 4001          *
 4002          * Also, we must check the leaf owner.
 4003          * In case of shared tree blocks (snapshots) we can inherit
 4004          * leaves from source snapshot.
 4005          * In that case, reference from source snapshot should not
 4006          * count.
 4007          */
 4008         if (btrfs_file_extent_disk_bytenr(leaf, fi) == bytenr &&
 4009             btrfs_file_extent_disk_num_bytes(leaf, fi) == len &&
 4010             (u64)(key.offset - btrfs_file_extent_offset(leaf, fi)) ==
 4011             offset && btrfs_header_owner(leaf) == root_id)
 4012             found_count++;
 4013 
 4014 next:
 4015         ret = btrfs_next_item(root, &path);
 4016         if (ret)
 4017             break;
 4018     }
 4019 out:
 4020     btrfs_release_path(&path);
 4021     if (found_count != count) {
 4022         error(
 4023 "extent[%llu, %llu] referencer count mismatch (root: %llu, owner: %llu, offset: %llu) wanted: %u, have: %u",
 4024             bytenr, len, root_id, objectid, offset, count,
 4025             found_count);
 4026         return REFERENCER_MISSING;
 4027     }
 4028     return 0;
 4029 }
 4030 
 4031 /*
 4032  * Check if the referencer of a shared data backref exists
 4033  */
 4034 static int check_shared_data_backref(struct btrfs_fs_info *fs_info,
 4035                      u64 parent, u64 bytenr)
 4036 {
 4037     struct extent_buffer *eb;
 4038     struct btrfs_key key;
 4039     struct btrfs_file_extent_item *fi;
 4040     u32 nr;
 4041     int found_parent = 0;
 4042     int i;
 4043 
 4044     eb = read_tree_block(fs_info, parent, 0);
 4045     if (!extent_buffer_uptodate(eb))
 4046         goto out;
 4047 
 4048     nr = btrfs_header_nritems(eb);
 4049     for (i = 0; i < nr; i++) {
 4050         btrfs_item_key_to_cpu(eb, &key, i);
 4051         if (key.type != BTRFS_EXTENT_DATA_KEY)
 4052             continue;
 4053 
 4054         fi = btrfs_item_ptr(eb, i, struct btrfs_file_extent_item);
 4055         if (btrfs_file_extent_type(eb, fi) == BTRFS_FILE_EXTENT_INLINE)
 4056             continue;
 4057 
 4058         if (btrfs_file_extent_disk_bytenr(eb, fi) == bytenr) {
 4059             found_parent = 1;
 4060             break;
 4061         }
 4062     }
 4063 
 4064 out:
 4065     free_extent_buffer(eb);
 4066     if (!found_parent) {
 4067         error("shared extent %llu referencer lost (parent: %llu)",
 4068             bytenr, parent);
 4069         return REFERENCER_MISSING;
 4070     }
 4071     return 0;
 4072 }
 4073 
 4074 /*
 4075  * Only delete backref if REFERENCER_MISSING or REFERENCER_MISMATCH.
 4076  *
 4077  * Returns <0   error
 4078  * Returns >0   the backref was deleted but extent still exists
 4079  * Returns =0   the whole extent item was deleted
 4080  */
 4081 static int repair_extent_item(struct btrfs_root *root, struct btrfs_path *path,
 4082               u64 bytenr, u64 num_bytes, u64 parent, u64 root_objectid,
 4083               u64 owner, u64 offset)
 4084 {
 4085     struct btrfs_trans_handle *trans;
 4086     struct btrfs_root *extent_root = root->fs_info->extent_root;
 4087     struct btrfs_key old_key;
 4088     int ret;
 4089 
 4090     btrfs_item_key_to_cpu(path->nodes[0], &old_key, path->slots[0]);
 4091 
 4092     ret = avoid_extents_overwrite(root->fs_info);
 4093     if (ret)
 4094         return ret;
 4095 
 4096     trans = btrfs_start_transaction(extent_root, 1);
 4097     if (IS_ERR(trans)) {
 4098         ret = PTR_ERR(trans);
 4099         errno = -ret;
 4100         error("fail to start transaction: %m");
 4101         goto out;
 4102     }
 4103     /* delete the backref */
 4104     ret = btrfs_free_extent(trans, root->fs_info->fs_root, bytenr,
 4105             num_bytes, parent, root_objectid, owner, offset);
 4106     if (!ret)
 4107         printf("Delete backref in extent [%llu %llu]\n",
 4108                bytenr, num_bytes);
 4109     else {
 4110         error("fail to delete backref in extent [%llu %llu]",
 4111               bytenr, num_bytes);
 4112         btrfs_abort_transaction(trans, ret);
 4113         goto out;
 4114     }
 4115     btrfs_commit_transaction(trans, extent_root);
 4116 
 4117     btrfs_release_path(path);
 4118     ret = btrfs_search_slot(NULL, root, &old_key, path, 0, 0);
 4119     if (ret > 0) {
 4120         /* odd, there must be one block group before at least */
 4121         if (path->slots[0] == 0) {
 4122             ret = -EUCLEAN;
 4123             goto out;
 4124         }
 4125         /*
 4126          * btrfs_free_extent() has deleted the extent item,
 4127          * let path point to last checked item.
 4128          */
 4129         if (path->slots[0] >= btrfs_header_nritems(path->nodes[0]))
 4130             path->slots[0] = btrfs_header_nritems(path->nodes[0]) - 1;
 4131         else
 4132             path->slots[0]--;
 4133 
 4134         ret = 0;
 4135     } else if (ret == 0) {
 4136         ret = 1;
 4137     }
 4138 
 4139 out:
 4140     return ret;
 4141 }
 4142 
 4143 /*
 4144  * This function will check a given extent item, including its backref and
 4145  * itself (like crossing stripe boundary and type)
 4146  *
 4147  * Since we don't use extent_record anymore, introduce new error bit
 4148  */
 4149 static int check_extent_item(struct btrfs_fs_info *fs_info,
 4150                  struct btrfs_path *path)
 4151 {
 4152     struct btrfs_extent_item *ei;
 4153     struct btrfs_extent_inline_ref *iref;
 4154     struct btrfs_extent_data_ref *dref;
 4155     struct extent_buffer *eb = path->nodes[0];
 4156     unsigned long ptr;
 4157     int slot = path->slots[0];
 4158     int type;
 4159     u32 nodesize = btrfs_super_nodesize(fs_info->super_copy);
 4160     u32 item_size = btrfs_item_size_nr(eb, slot);
 4161     u64 flags;
 4162     u64 offset;
 4163     u64 parent;
 4164     u64 num_bytes;
 4165     u64 root_objectid;
 4166     u64 gen;
 4167     u64 owner;
 4168     u64 owner_offset;
 4169     u64 super_gen;
 4170     int metadata = 0;
 4171     int level;
 4172     struct btrfs_key key;
 4173     int ret;
 4174     int err = 0;
 4175     int tmp_err;
 4176     u32 ptr_offset;
 4177 
 4178     btrfs_item_key_to_cpu(eb, &key, slot);
 4179     if (key.type == BTRFS_EXTENT_ITEM_KEY) {
 4180         bytes_used += key.offset;
 4181         num_bytes = key.offset;
 4182     } else {
 4183         bytes_used += nodesize;
 4184         num_bytes = nodesize;
 4185     }
 4186 
 4187     if (item_size < sizeof(*ei)) {
 4188         /*
 4189          * COMPAT_EXTENT_TREE_V0 case, but it's already a super
 4190          * old thing when on disk format is still un-determined.
 4191          * No need to care about it anymore
 4192          */
 4193         error("unsupported COMPAT_EXTENT_TREE_V0 detected");
 4194         return -ENOTTY;
 4195     }
 4196 
 4197     ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
 4198     flags = btrfs_extent_flags(eb, ei);
 4199     gen = btrfs_extent_generation(eb, ei);
 4200     super_gen = btrfs_super_generation(fs_info->super_copy);
 4201     if (gen > super_gen + 1) {
 4202         error(
 4203         "invalid generation for extent %llu, have %llu expect (0, %llu]",
 4204             key.objectid, gen, super_gen + 1);
 4205         err |= INVALID_GENERATION;
 4206     }
 4207 
 4208     if (flags & BTRFS_EXTENT_FLAG_TREE_BLOCK)
 4209         metadata = 1;
 4210     if (metadata && check_crossing_stripes(global_info, key.objectid,
 4211                            eb->len)) {
 4212         error("bad metadata [%llu, %llu) crossing stripe boundary",
 4213               key.objectid, key.objectid + nodesize);
 4214         err |= CROSSING_STRIPE_BOUNDARY;
 4215     }
 4216 
 4217     ptr = (unsigned long)(ei + 1);
 4218 
 4219     if (metadata && key.type == BTRFS_EXTENT_ITEM_KEY) {
 4220         /* Old EXTENT_ITEM metadata */
 4221         struct btrfs_tree_block_info *info;
 4222 
 4223         info = (struct btrfs_tree_block_info *)ptr;
 4224         level = btrfs_tree_block_level(eb, info);
 4225         ptr += sizeof(struct btrfs_tree_block_info);
 4226     } else {
 4227         /* New METADATA_ITEM */
 4228         level = key.offset;
 4229     }
 4230     ptr_offset = ptr - (unsigned long)ei;
 4231 
 4232 next:
 4233     /* Reached extent item end normally */
 4234     if (ptr_offset == item_size)
 4235         goto out;
 4236 
 4237     /* Beyond extent item end, wrong item size */
 4238     if (ptr_offset > item_size) {
 4239         err |= ITEM_SIZE_MISMATCH;
 4240         error("extent item at bytenr %llu slot %d has wrong size",
 4241             eb->start, slot);
 4242         goto out;
 4243     }
 4244 
 4245     ptr = (unsigned long)ei + ptr_offset;
 4246     parent = 0;
 4247     root_objectid = 0;
 4248     owner = 0;
 4249     owner_offset = 0;
 4250     /* Now check every backref in this extent item */
 4251     iref = (struct btrfs_extent_inline_ref *)ptr;
 4252     type = btrfs_extent_inline_ref_type(eb, iref);
 4253     offset = btrfs_extent_inline_ref_offset(eb, iref);
 4254     switch (type) {
 4255     case BTRFS_TREE_BLOCK_REF_KEY:
 4256         root_objectid = offset;
 4257         owner = level;
 4258         tmp_err = check_tree_block_backref(fs_info, offset,
 4259                            key.objectid, level);
 4260         break;
 4261     case BTRFS_SHARED_BLOCK_REF_KEY:
 4262         parent = offset;
 4263         tmp_err = check_shared_block_backref(fs_info, offset,
 4264                              key.objectid, level);
 4265         break;
 4266     case BTRFS_EXTENT_DATA_REF_KEY:
 4267         dref = (struct btrfs_extent_data_ref *)(&iref->offset);
 4268         root_objectid = btrfs_extent_data_ref_root(eb, dref);
 4269         owner = btrfs_extent_data_ref_objectid(eb, dref);
 4270         owner_offset = btrfs_extent_data_ref_offset(eb, dref);
 4271         tmp_err = check_extent_data_backref(fs_info, root_objectid,
 4272                 owner, owner_offset, key.objectid, key.offset,
 4273                 btrfs_extent_data_ref_count(eb, dref));
 4274         break;
 4275     case BTRFS_SHARED_DATA_REF_KEY:
 4276         parent = offset;
 4277         tmp_err = check_shared_data_backref(fs_info, offset,
 4278                             key.objectid);
 4279         break;
 4280     default:
 4281         error("extent[%llu %d %llu] has unknown ref type: %d",
 4282             key.objectid, key.type, key.offset, type);
 4283         err |= UNKNOWN_TYPE;
 4284 
 4285         goto out;
 4286     }
 4287 
 4288     if ((tmp_err & (REFERENCER_MISSING | REFERENCER_MISMATCH))
 4289         && repair) {
 4290         ret = repair_extent_item(fs_info->extent_root, path,
 4291              key.objectid, num_bytes, parent, root_objectid,
 4292              owner, owner_offset);
 4293         if (ret < 0) {
 4294             err |= tmp_err;
 4295             err |= FATAL_ERROR;
 4296             goto out;
 4297         } else if (ret == 0) {
 4298             err = 0;
 4299             goto out;
 4300         } else if (ret > 0) {
 4301             /*
 4302              * The error has been repaired which means the
 4303              * extent item is still existed with other backrefs,
 4304              * go to check next.
 4305              */
 4306             tmp_err &= ~REFERENCER_MISSING;
 4307             tmp_err &= ~REFERENCER_MISMATCH;
 4308             err |= tmp_err;
 4309             eb = path->nodes[0];
 4310             slot = path->slots[0];
 4311             ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
 4312             item_size = btrfs_item_size_nr(eb, slot);
 4313             goto next;
 4314         }
 4315     } else {
 4316         err |= tmp_err;
 4317     }
 4318 
 4319     ptr_offset += btrfs_extent_inline_ref_size(type);
 4320     goto next;
 4321 
 4322 out:
 4323     return err;
 4324 }
 4325 
 4326 /*
 4327  * Check if a dev extent item is referred correctly by its chunk
 4328  */
 4329 static int check_dev_extent_item(struct btrfs_fs_info *fs_info,
 4330                  struct extent_buffer *eb, int slot)
 4331 {
 4332     struct btrfs_root *chunk_root = fs_info->chunk_root;
 4333     struct btrfs_dev_extent *ptr;
 4334     struct btrfs_path path;
 4335     struct btrfs_key chunk_key;
 4336     struct btrfs_key devext_key;
 4337     struct btrfs_chunk *chunk;
 4338     struct extent_buffer *l;
 4339     int num_stripes;
 4340     u64 length;
 4341     int i;
 4342     int found_chunk = 0;
 4343     int ret;
 4344 
 4345     btrfs_item_key_to_cpu(eb, &devext_key, slot);
 4346     ptr = btrfs_item_ptr(eb, slot, struct btrfs_dev_extent);
 4347     length = btrfs_dev_extent_length(eb, ptr);
 4348 
 4349     chunk_key.objectid = btrfs_dev_extent_chunk_objectid(eb, ptr);
 4350     chunk_key.type = BTRFS_CHUNK_ITEM_KEY;
 4351     chunk_key.offset = btrfs_dev_extent_chunk_offset(eb, ptr);
 4352 
 4353     btrfs_init_path(&path);
 4354     ret = btrfs_search_slot(NULL, chunk_root, &chunk_key, &path, 0, 0);
 4355     if (ret)
 4356         goto out;
 4357 
 4358     l = path.nodes[0];
 4359     chunk = btrfs_item_ptr(l, path.slots[0], struct btrfs_chunk);
 4360     ret = btrfs_check_chunk_valid(fs_info, l, chunk, path.slots[0],
 4361                       chunk_key.offset);
 4362     if (ret < 0)
 4363         goto out;
 4364 
 4365     if (btrfs_stripe_length(fs_info, l, chunk) != length)
 4366         goto out;
 4367 
 4368     num_stripes = btrfs_chunk_num_stripes(l, chunk);
 4369     for (i = 0; i < num_stripes; i++) {
 4370         u64 devid = btrfs_stripe_devid_nr(l, chunk, i);
 4371         u64 offset = btrfs_stripe_offset_nr(l, chunk, i);
 4372 
 4373         if (devid == devext_key.objectid &&
 4374             offset == devext_key.offset) {
 4375             found_chunk = 1;
 4376             break;
 4377         }
 4378     }
 4379 out:
 4380     btrfs_release_path(&path);
 4381     if (!found_chunk) {
 4382         error(
 4383         "device extent[%llu, %llu, %llu] did not find the related chunk",
 4384             devext_key.objectid, devext_key.offset, length);
 4385         return REFERENCER_MISSING;
 4386     }
 4387     return 0;
 4388 }
 4389 
 4390 /*
 4391  * Check if the used space is correct with the dev item
 4392  */
 4393 static int check_dev_item(struct btrfs_fs_info *fs_info,
 4394               struct extent_buffer *eb, int slot)
 4395 {
 4396     struct btrfs_root *dev_root = fs_info->dev_root;
 4397     struct btrfs_dev_item *dev_item;
 4398     struct btrfs_path path;
 4399     struct btrfs_key key;
 4400     struct btrfs_dev_extent *ptr;
 4401     u64 total_bytes;
 4402     u64 dev_id;
 4403     u64 used;
 4404     u64 total = 0;
 4405     u64 prev_devid = 0;
 4406     u64 prev_dev_ext_end = 0;
 4407     int ret;
 4408 
 4409     dev_item = btrfs_item_ptr(eb, slot, struct btrfs_dev_item);
 4410     dev_id = btrfs_device_id(eb, dev_item);
 4411     used = btrfs_device_bytes_used(eb, dev_item);
 4412     total_bytes = btrfs_device_total_bytes(eb, dev_item);
 4413 
 4414     if (used > total_bytes) {
 4415         error(
 4416         "device %llu has incorrect used bytes %llu > total bytes %llu",
 4417             dev_id, used, total_bytes);
 4418         return ACCOUNTING_MISMATCH;
 4419     }
 4420     key.objectid = dev_id;
 4421     key.type = BTRFS_DEV_EXTENT_KEY;
 4422     key.offset = 0;
 4423 
 4424     btrfs_init_path(&path);
 4425     ret = btrfs_search_slot(NULL, dev_root, &key, &path, 0, 0);
 4426     if (ret < 0) {
 4427         btrfs_item_key_to_cpu(eb, &key, slot);
 4428         error("cannot find any related dev extent for dev[%llu, %u, %llu]",
 4429             key.objectid, key.type, key.offset);
 4430         btrfs_release_path(&path);
 4431         return REFERENCER_MISSING;
 4432     }
 4433 
 4434     /*
 4435      * Iterate dev_extents to calculate the used space of a device
 4436      *
 4437      * Also make sure no dev extents overlap and end beyond device boundary
 4438      */
 4439     while (1) {
 4440         u64 devid;
 4441         u64 physical_offset;
 4442         u64 physical_len;
 4443 
 4444         if (path.slots[0] >= btrfs_header_nritems(path.nodes[0]))
 4445             goto next;
 4446 
 4447         btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
 4448         if (key.objectid > dev_id)
 4449             break;
 4450         if (key.type != BTRFS_DEV_EXTENT_KEY || key.objectid != dev_id)
 4451             goto next;
 4452 
 4453         ptr = btrfs_item_ptr(path.nodes[0], path.slots[0],
 4454                      struct btrfs_dev_extent);
 4455         devid = key.objectid;
 4456         physical_offset = key.offset;
 4457         physical_len = btrfs_dev_extent_length(path.nodes[0], ptr);
 4458 
 4459         if (prev_devid == devid && physical_offset < prev_dev_ext_end) {
 4460             error(
 4461 "dev extent devid %llu offset %llu len %llu overlap with previous dev extent end %llu",
 4462                   devid, physical_offset, physical_len,
 4463                   prev_dev_ext_end);
 4464             return ACCOUNTING_MISMATCH;
 4465         }
 4466         if (physical_offset + physical_len > total_bytes) {
 4467             error(
 4468 "dev extent devid %llu offset %llu len %llu is beyond device boundary %llu",
 4469                   devid, physical_offset, physical_len,
 4470                   total_bytes);
 4471             return ACCOUNTING_MISMATCH;
 4472         }
 4473         prev_devid = devid;
 4474         prev_dev_ext_end = physical_offset + physical_len;
 4475         total += physical_len;
 4476 next:
 4477         ret = btrfs_next_item(dev_root, &path);
 4478         if (ret)
 4479             break;
 4480     }
 4481     btrfs_release_path(&path);
 4482 
 4483     if (used != total) {
 4484         btrfs_item_key_to_cpu(eb, &key, slot);
 4485         error(
 4486 "Dev extent's total-byte %llu is not equal to bytes-used %llu in dev[%llu, %u, %llu]",
 4487             total, used, BTRFS_ROOT_TREE_OBJECTID,
 4488             BTRFS_DEV_EXTENT_KEY, dev_id);
 4489         return ACCOUNTING_MISMATCH;
 4490     }
 4491     check_dev_size_alignment(dev_id, total_bytes, fs_info->sectorsize);
 4492 
 4493     return 0;
 4494 }
 4495 
 4496 /*
 4497  * Check a chunk item.
 4498  * Including checking all referred dev_extents and block group
 4499  */
 4500 static int check_chunk_item(struct btrfs_fs_info *fs_info,
 4501                 struct extent_buffer *eb, int slot)
 4502 {
 4503     struct btrfs_root *extent_root = fs_info->extent_root;
 4504     struct btrfs_root *dev_root = fs_info->dev_root;
 4505     struct btrfs_path path;
 4506     struct btrfs_key chunk_key;
 4507     struct btrfs_key bg_key;
 4508     struct btrfs_key devext_key;
 4509     struct btrfs_chunk *chunk;
 4510     struct extent_buffer *leaf;
 4511     struct btrfs_block_group_item *bi;
 4512     struct btrfs_block_group_item bg_item;
 4513     struct btrfs_dev_extent *ptr;
 4514     u64 length;
 4515     u64 chunk_end;
 4516     u64 stripe_len;
 4517     u64 type;
 4518     int num_stripes;
 4519     u64 offset;
 4520     u64 objectid;
 4521     int i;
 4522     int ret;
 4523     int err = 0;
 4524 
 4525     btrfs_item_key_to_cpu(eb, &chunk_key, slot);
 4526     chunk = btrfs_item_ptr(eb, slot, struct btrfs_chunk);
 4527     length = btrfs_chunk_length(eb, chunk);
 4528     chunk_end = chunk_key.offset + length;
 4529     ret = btrfs_check_chunk_valid(fs_info, eb, chunk, slot,
 4530                       chunk_key.offset);
 4531     if (ret < 0) {
 4532         error("chunk[%llu %llu) is invalid", chunk_key.offset,
 4533             chunk_end);
 4534         err |= BYTES_UNALIGNED | UNKNOWN_TYPE;
 4535         goto out;
 4536     }
 4537     type = btrfs_chunk_type(eb, chunk);
 4538 
 4539     bg_key.objectid = chunk_key.offset;
 4540     bg_key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
 4541     bg_key.offset = length;
 4542 
 4543     btrfs_init_path(&path);
 4544     ret = btrfs_search_slot(NULL, extent_root, &bg_key, &path, 0, 0);
 4545     if (ret) {
 4546         error(
 4547         "chunk[%llu %llu) did not find the related block group item",
 4548             chunk_key.offset, chunk_end);
 4549         err |= REFERENCER_MISSING;
 4550     } else{
 4551         leaf = path.nodes[0];
 4552         bi = btrfs_item_ptr(leaf, path.slots[0],
 4553                     struct btrfs_block_group_item);
 4554         read_extent_buffer(leaf, &bg_item, (unsigned long)bi,
 4555                    sizeof(bg_item));
 4556         if (btrfs_block_group_flags(&bg_item) != type) {
 4557             error(
 4558 "chunk[%llu %llu) related block group item flags mismatch, wanted: %llu, have: %llu",
 4559                 chunk_key.offset, chunk_end, type,
 4560                 btrfs_block_group_flags(&bg_item));
 4561             err |= REFERENCER_MISSING;
 4562         }
 4563     }
 4564 
 4565     num_stripes = btrfs_chunk_num_stripes(eb, chunk);
 4566     stripe_len = btrfs_stripe_length(fs_info, eb, chunk);
 4567     for (i = 0; i < num_stripes; i++) {
 4568         btrfs_release_path(&path);
 4569         btrfs_init_path(&path);
 4570         devext_key.objectid = btrfs_stripe_devid_nr(eb, chunk, i);
 4571         devext_key.type = BTRFS_DEV_EXTENT_KEY;
 4572         devext_key.offset = btrfs_stripe_offset_nr(eb, chunk, i);
 4573 
 4574         ret = btrfs_search_slot(NULL, dev_root, &devext_key, &path,
 4575                     0, 0);
 4576         if (ret)
 4577             goto not_match_dev;
 4578 
 4579         leaf = path.nodes[0];
 4580         ptr = btrfs_item_ptr(leaf, path.slots[0],
 4581                      struct btrfs_dev_extent);
 4582         objectid = btrfs_dev_extent_chunk_objectid(leaf, ptr);
 4583         offset = btrfs_dev_extent_chunk_offset(leaf, ptr);
 4584         if (objectid != chunk_key.objectid ||
 4585             offset != chunk_key.offset ||
 4586             btrfs_dev_extent_length(leaf, ptr) != stripe_len)
 4587             goto not_match_dev;
 4588         continue;
 4589 not_match_dev:
 4590         err |= BACKREF_MISSING;
 4591         error(
 4592         "chunk[%llu %llu) stripe %d did not find the related dev extent",
 4593             chunk_key.objectid, chunk_end, i);
 4594         continue;
 4595     }
 4596     btrfs_release_path(&path);
 4597 out:
 4598     return err;
 4599 }
 4600 
 4601 /*
 4602  * Add block group item to the extent tree if @err contains REFERENCER_MISSING.
 4603  * FIXME: We still need to repair error of dev_item.
 4604  *
 4605  * Returns error after repair.
 4606  */
 4607 static int repair_chunk_item(struct btrfs_root *chunk_root,
 4608                  struct btrfs_path *path, int err)
 4609 {
 4610     struct btrfs_chunk *chunk;
 4611     struct btrfs_key chunk_key;
 4612     struct extent_buffer *eb = path->nodes[0];
 4613     struct btrfs_root *extent_root = chunk_root->fs_info->extent_root;
 4614     struct btrfs_trans_handle *trans;
 4615     u64 length;
 4616     int slot = path->slots[0];
 4617     u64 type;
 4618     int ret = 0;
 4619 
 4620     btrfs_item_key_to_cpu(eb, &chunk_key, slot);
 4621     if (chunk_key.type != BTRFS_CHUNK_ITEM_KEY)
 4622         return err;
 4623     chunk = btrfs_item_ptr(eb, slot, struct btrfs_chunk);
 4624     type = btrfs_chunk_type(path->nodes[0], chunk);
 4625     length = btrfs_chunk_length(eb, chunk);
 4626 
 4627     /* now repair only adds block group */
 4628     if ((err & REFERENCER_MISSING) == 0)
 4629         return err;
 4630 
 4631     ret = avoid_extents_overwrite(chunk_root->fs_info);
 4632     if (ret)
 4633         return ret;
 4634 
 4635     trans = btrfs_start_transaction(extent_root, 1);
 4636     if (IS_ERR(trans)) {
 4637         ret = PTR_ERR(trans);
 4638         errno = -ret;
 4639         error("fail to start transaction: %m");
 4640         return ret;
 4641     }
 4642 
 4643     ret = btrfs_make_block_group(trans, chunk_root->fs_info, 0, type,
 4644                      chunk_key.offset, length);
 4645     if (ret) {
 4646         error("fail to add block group item [%llu %llu]",
 4647               chunk_key.offset, length);
 4648     } else {
 4649         err &= ~REFERENCER_MISSING;
 4650         printf("Added block group item[%llu %llu]\n", chunk_key.offset,
 4651                length);
 4652     }
 4653 
 4654     btrfs_commit_transaction(trans, extent_root);
 4655     if (ret)
 4656         error("fail to repair item(s) related to chunk item [%llu %llu]",
 4657               chunk_key.objectid, chunk_key.offset);
 4658     return err;
 4659 }
 4660 
 4661 /*
 4662  * Main entry function to check known items and update related accounting info
 4663  */
 4664 static int check_leaf_items(struct btrfs_root *root, struct btrfs_path *path,
 4665                 struct node_refs *nrefs, int account_bytes)
 4666 {
 4667     struct btrfs_fs_info *fs_info = root->fs_info;
 4668     struct btrfs_key key;
 4669     struct extent_buffer *eb;
 4670     int slot;
 4671     int type;
 4672     struct btrfs_extent_data_ref *dref;
 4673     int ret = 0;
 4674     int err = 0;
 4675 
 4676 again:
 4677     eb = path->nodes[0];
 4678     slot = path->slots[0];
 4679     if (slot >= btrfs_header_nritems(eb)) {
 4680         if (slot == 0) {
 4681             error("empty leaf [%llu %u] root %llu", eb->start,
 4682                 root->fs_info->nodesize, root->objectid);
 4683             err |= EIO;
 4684         }
 4685         goto out;
 4686     }
 4687 
 4688     btrfs_item_key_to_cpu(eb, &key, slot);
 4689     type = key.type;
 4690 
 4691     switch (type) {
 4692     case BTRFS_EXTENT_DATA_KEY:
 4693         ret = check_extent_data_item(root, path, nrefs, account_bytes);
 4694         if (repair && ret)
 4695             ret = repair_extent_data_item(root, path, nrefs, ret);
 4696         err |= ret;
 4697         break;
 4698     case BTRFS_BLOCK_GROUP_ITEM_KEY:
 4699         ret = check_block_group_item(fs_info, eb, slot);
 4700         if (repair &&
 4701             ret & REFERENCER_MISSING)
 4702             ret = delete_item(root, path);
 4703         err |= ret;
 4704         break;
 4705     case BTRFS_DEV_ITEM_KEY:
 4706         ret = check_dev_item(fs_info, eb, slot);
 4707         err |= ret;
 4708         break;
 4709     case BTRFS_CHUNK_ITEM_KEY:
 4710         ret = check_chunk_item(fs_info, eb, slot);
 4711         if (repair && ret)
 4712             ret = repair_chunk_item(root, path, ret);
 4713         err |= ret;
 4714         break;
 4715     case BTRFS_DEV_EXTENT_KEY:
 4716         ret = check_dev_extent_item(fs_info, eb, slot);
 4717         err |= ret;
 4718         break;
 4719     case BTRFS_EXTENT_ITEM_KEY:
 4720     case BTRFS_METADATA_ITEM_KEY:
 4721         ret = check_extent_item(fs_info, path);
 4722         err |= ret;
 4723         break;
 4724     case BTRFS_EXTENT_CSUM_KEY:
 4725         total_csum_bytes += btrfs_item_size_nr(eb, slot);
 4726         err |= ret;
 4727         break;
 4728     case BTRFS_TREE_BLOCK_REF_KEY:
 4729         ret = check_tree_block_backref(fs_info, key.offset,
 4730                            key.objectid, -1);
 4731         if (repair &&
 4732             ret & (REFERENCER_MISMATCH | REFERENCER_MISSING))
 4733             ret = delete_item(root, path);
 4734         err |= ret;
 4735         break;
 4736     case BTRFS_EXTENT_DATA_REF_KEY:
 4737         dref = btrfs_item_ptr(eb, slot, struct btrfs_extent_data_ref);
 4738         ret = check_extent_data_backref(fs_info,
 4739                 btrfs_extent_data_ref_root(eb, dref),
 4740                 btrfs_extent_data_ref_objectid(eb, dref),
 4741                 btrfs_extent_data_ref_offset(eb, dref),
 4742                 key.objectid, 0,
 4743                 btrfs_extent_data_ref_count(eb, dref));
 4744         if (repair &&
 4745             ret & (REFERENCER_MISMATCH | REFERENCER_MISSING))
 4746             ret = delete_item(root, path);
 4747         err |= ret;
 4748         break;
 4749     case BTRFS_SHARED_BLOCK_REF_KEY:
 4750         ret = check_shared_block_backref(fs_info, key.offset,
 4751                          key.objectid, -1);
 4752         if (repair &&
 4753             ret & (REFERENCER_MISMATCH | REFERENCER_MISSING))
 4754             ret = delete_item(root, path);
 4755         err |= ret;
 4756         break;
 4757     case BTRFS_SHARED_DATA_REF_KEY:
 4758         ret = check_shared_data_backref(fs_info, key.offset,
 4759                         key.objectid);
 4760         if (repair &&
 4761             ret & (REFERENCER_MISMATCH | REFERENCER_MISSING))
 4762             ret = delete_item(root, path);
 4763         err |= ret;
 4764         break;
 4765     default:
 4766         break;
 4767     }
 4768 
 4769     ++path->slots[0];
 4770     goto again;
 4771 out:
 4772     return err;
 4773 }
 4774 
 4775 /*
 4776  * @trans      just for lowmem repair mode
 4777  * @check all  if not 0 then check all tree block backrefs and items
 4778  *             0 then just check relationship of items in fs tree(s)
 4779  *
 4780  * Returns >0  Found error, should continue
 4781  * Returns <0  Fatal error, must exit the whole check
 4782  * Returns 0   No errors found
 4783  */
 4784 static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
 4785               int *level, struct node_refs *nrefs, int check_all)
 4786 {
 4787     enum btrfs_tree_block_status status;
 4788     u64 bytenr;
 4789     u64 ptr_gen;
 4790     struct btrfs_fs_info *fs_info = root->fs_info;
 4791     struct extent_buffer *next;
 4792     struct extent_buffer *cur;
 4793     int ret;
 4794     int err = 0;
 4795     int check;
 4796     int account_file_data = 0;
 4797 
 4798     WARN_ON(*level < 0);
 4799     WARN_ON(*level >= BTRFS_MAX_LEVEL);
 4800 
 4801     ret = update_nodes_refs(root, btrfs_header_bytenr(path->nodes[*level]),
 4802                 path->nodes[*level], nrefs, *level, check_all);
 4803     if (ret < 0)
 4804         return ret;
 4805 
 4806     while (*level >= 0) {
 4807         WARN_ON(*level < 0);
 4808         WARN_ON(*level >= BTRFS_MAX_LEVEL);
 4809         cur = path->nodes[*level];
 4810         bytenr = btrfs_header_bytenr(cur);
 4811         check = nrefs->need_check[*level];
 4812 
 4813         if (btrfs_header_level(cur) != *level)
 4814             WARN_ON(1);
 4815            /*
 4816         * Update bytes accounting and check tree block ref
 4817         * NOTE: Doing accounting and check before checking nritems
 4818         * is necessary because of empty node/leaf.
 4819         */
 4820         if ((check_all && !nrefs->checked[*level]) ||
 4821             (!check_all && nrefs->need_check[*level])) {
 4822             ret = check_tree_block_ref(root, cur,
 4823                btrfs_header_bytenr(cur), btrfs_header_level(cur),
 4824                btrfs_header_owner(cur), nrefs);
 4825 
 4826             if (repair && ret)
 4827                 ret = repair_tree_block_ref(root,
 4828                     path->nodes[*level], nrefs, *level, ret);
 4829             err |= ret;
 4830 
 4831             if (check_all && nrefs->need_check[*level] &&
 4832                 nrefs->refs[*level]) {
 4833                 account_bytes(root, path, *level);
 4834                 account_file_data = 1;
 4835             }
 4836             nrefs->checked[*level] = 1;
 4837         }
 4838 
 4839         if (path->slots[*level] >= btrfs_header_nritems(cur))
 4840             break;
 4841 
 4842         /* Don't forgot to check leaf/node validation */
 4843         if (*level == 0) {
 4844             /* skip duplicate check */
 4845             if (check || !check_all) {
 4846                 ret = btrfs_check_leaf(fs_info, NULL, cur);
 4847                 if (ret != BTRFS_TREE_BLOCK_CLEAN) {
 4848                     err |= -EIO;
 4849                     break;
 4850                 }
 4851             }
 4852 
 4853             ret = 0;
 4854             if (!check_all)
 4855                 ret = process_one_leaf(root, path, nrefs, level);
 4856             else
 4857                 ret = check_leaf_items(root, path,
 4858                            nrefs, account_file_data);
 4859             err |= ret;
 4860             break;
 4861         }
 4862         if (check || !check_all) {
 4863             ret = btrfs_check_node(fs_info, NULL, cur);
 4864             if (ret != BTRFS_TREE_BLOCK_CLEAN) {
 4865                 err |= -EIO;
 4866                 break;
 4867             }
 4868         }
 4869 
 4870         bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
 4871         ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
 4872 
 4873         ret = update_nodes_refs(root, bytenr, NULL, nrefs, *level - 1,
 4874                     check_all);
 4875         if (ret < 0)
 4876             break;
 4877         /*
 4878          * check all trees in check_chunks_and_extent
 4879          * check shared node once in check_fs_roots
 4880          */
 4881         if (!check_all && !nrefs->need_check[*level - 1]) {
 4882             path->slots[*level]++;
 4883             continue;
 4884         }
 4885 
 4886         next = btrfs_find_tree_block(fs_info, bytenr, fs_info->nodesize);
 4887         if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
 4888             free_extent_buffer(next);
 4889             reada_walk_down(root, cur, path->slots[*level]);
 4890             next = read_tree_block(fs_info, bytenr, ptr_gen);
 4891             if (!extent_buffer_uptodate(next)) {
 4892                 struct btrfs_key node_key;
 4893 
 4894                 btrfs_node_key_to_cpu(path->nodes[*level],
 4895                               &node_key,
 4896                               path->slots[*level]);
 4897                 btrfs_add_corrupt_extent_record(fs_info,
 4898                     &node_key, path->nodes[*level]->start,
 4899                     fs_info->nodesize, *level);
 4900                 err |= -EIO;
 4901                 break;
 4902             }
 4903         }
 4904 
 4905         ret = check_child_node(cur, path->slots[*level], next);
 4906         err |= ret;
 4907         if (ret < 0)
 4908             break;
 4909 
 4910         if (btrfs_is_leaf(next))
 4911             status = btrfs_check_leaf(fs_info, NULL, next);
 4912         else
 4913             status = btrfs_check_node(fs_info, NULL, next);
 4914         if (status != BTRFS_TREE_BLOCK_CLEAN) {
 4915             free_extent_buffer(next);
 4916             err |= -EIO;
 4917             break;
 4918         }
 4919 
 4920         *level = *level - 1;
 4921         free_extent_buffer(path->nodes[*level]);
 4922         path->nodes[*level] = next;
 4923         path->slots[*level] = 0;
 4924         account_file_data = 0;
 4925 
 4926         update_nodes_refs(root, (u64)-1, next, nrefs, *level, check_all);
 4927     }
 4928     return err;
 4929 }
 4930 
 4931 static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
 4932             int *level)
 4933 {
 4934     int i;
 4935     struct extent_buffer *leaf;
 4936 
 4937     for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
 4938         leaf = path->nodes[i];
 4939         if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) {
 4940             path->slots[i]++;
 4941             *level = i;
 4942             return 0;
 4943         }
 4944         free_extent_buffer(path->nodes[*level]);
 4945         path->nodes[*level] = NULL;
 4946         *level = i + 1;
 4947     }
 4948     return 1;
 4949 }
 4950 
 4951 /*
 4952  * Insert the missing inode item and inode ref.
 4953  *
 4954  * Normal INODE_ITEM_MISSING and INODE_REF_MISSING are handled in backref * dir.
 4955  * Root dir should be handled specially because root dir is the root of fs.
 4956  *
 4957  * returns err (>0 or 0) after repair
 4958  */
 4959 static int repair_fs_first_inode(struct btrfs_root *root, int err)
 4960 {
 4961     struct btrfs_trans_handle *trans;
 4962     struct btrfs_key key;
 4963     struct btrfs_path path;
 4964     int filetype = BTRFS_FT_DIR;
 4965     int ret = 0;
 4966 
 4967     btrfs_init_path(&path);
 4968 
 4969     if (err & INODE_REF_MISSING) {
 4970         key.objectid = BTRFS_FIRST_FREE_OBJECTID;
 4971         key.type = BTRFS_INODE_REF_KEY;
 4972         key.offset = BTRFS_FIRST_FREE_OBJECTID;
 4973 
 4974         trans = btrfs_start_transaction(root, 1);
 4975         if (IS_ERR(trans)) {
 4976             ret = PTR_ERR(trans);
 4977             goto out;
 4978         }
 4979 
 4980         btrfs_release_path(&path);
 4981         ret = btrfs_search_slot(trans, root, &key, &path, 1, 1);
 4982         if (ret)
 4983             goto trans_fail;
 4984 
 4985         ret = btrfs_insert_inode_ref(trans, root, "..", 2,
 4986                          BTRFS_FIRST_FREE_OBJECTID,
 4987                          BTRFS_FIRST_FREE_OBJECTID, 0);
 4988         if (ret)
 4989             goto trans_fail;
 4990 
 4991         printf("Add INODE_REF[%llu %llu] name %s\n",
 4992                BTRFS_FIRST_FREE_OBJECTID, BTRFS_FIRST_FREE_OBJECTID,
 4993                "..");
 4994         err &= ~INODE_REF_MISSING;
 4995 trans_fail:
 4996         if (ret)
 4997             error("fail to insert first inode's ref");
 4998         btrfs_commit_transaction(trans, root);
 4999     }
 5000 
 5001     if (err & INODE_ITEM_MISSING) {
 5002         ret = repair_inode_item_missing(root,
 5003                     BTRFS_FIRST_FREE_OBJECTID, filetype);
 5004         if (ret)
 5005             goto out;
 5006         err &= ~INODE_ITEM_MISSING;
 5007     }
 5008 out:
 5009     if (ret)
 5010         error("fail to repair first inode");
 5011     btrfs_release_path(&path);
 5012     return err;
 5013 }
 5014 
 5015 /*
 5016  * check first root dir's inode_item and inode_ref
 5017  *
 5018  * returns 0 means no error
 5019  * returns >0 means error
 5020  * returns <0 means fatal error
 5021  */
 5022 static int check_fs_first_inode(struct btrfs_root *root)
 5023 {
 5024     struct btrfs_path path;
 5025     struct btrfs_key key;
 5026     struct btrfs_inode_item *ii;
 5027     u64 index;
 5028     u32 mode;
 5029     int err = 0;
 5030     int ret;
 5031 
 5032     key.objectid = BTRFS_FIRST_FREE_OBJECTID;
 5033     key.type = BTRFS_INODE_ITEM_KEY;
 5034     key.offset = 0;
 5035 
 5036     /* For root being dropped, we don't need to check first inode */
 5037     if (btrfs_root_refs(&root->root_item) == 0 &&
 5038         btrfs_disk_key_objectid(&root->root_item.drop_progress) >=
 5039         BTRFS_FIRST_FREE_OBJECTID)
 5040         return 0;
 5041 
 5042     btrfs_init_path(&path);
 5043     ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
 5044     if (ret < 0)
 5045         goto out;
 5046     if (ret > 0) {
 5047         ret = 0;
 5048         err |= INODE_ITEM_MISSING;
 5049     } else {
 5050         ii = btrfs_item_ptr(path.nodes[0], path.slots[0],
 5051                     struct btrfs_inode_item);
 5052         mode = btrfs_inode_mode(path.nodes[0], ii);
 5053         if (imode_to_type(mode) != BTRFS_FT_DIR)
 5054             err |= INODE_ITEM_MISMATCH;
 5055     }
 5056 
 5057     /* lookup first inode ref */
 5058     key.offset = BTRFS_FIRST_FREE_OBJECTID;
 5059     key.type = BTRFS_INODE_REF_KEY;
 5060     /* special index value */
 5061     index = 0;
 5062 
 5063     ret = find_inode_ref(root, &key, "..", strlen(".."), &index);
 5064     if (ret < 0)
 5065         goto out;
 5066     err |= ret;
 5067 
 5068 out:
 5069     btrfs_release_path(&path);
 5070 
 5071     if (err && repair)
 5072         err = repair_fs_first_inode(root, err);
 5073 
 5074     if (err & (INODE_ITEM_MISSING | INODE_ITEM_MISMATCH))
 5075         error("root dir INODE_ITEM is %s",
 5076               err & INODE_ITEM_MISMATCH ? "mismatch" : "missing");
 5077     if (err & INODE_REF_MISSING)
 5078         error("root dir INODE_REF is missing");
 5079 
 5080     return ret < 0 ? ret : err;
 5081 }
 5082 
 5083 /*
 5084  * This function calls walk_down_tree and walk_up_tree to check tree
 5085  * blocks and integrity of fs tree items.
 5086  *
 5087  * @root:         the root of the tree to be checked.
 5088  * @account       if NOT 0 means check the tree (including tree)'s treeblocks.
 5089  *                otherwise means check fs tree(s) items relationship and
 5090  *        @root MUST be a fs tree root.
 5091  * Returns 0      represents OK.
 5092  * Returns >0     represents error bits.
 5093  */
 5094 static int check_btrfs_root(struct btrfs_root *root, int check_all)
 5095 {
 5096     struct btrfs_path path;
 5097     struct node_refs nrefs;
 5098     struct btrfs_root_item *root_item = &root->root_item;
 5099     u64 super_generation = btrfs_super_generation(root->fs_info->super_copy);
 5100     int ret;
 5101     int level;
 5102     int err = 0;
 5103 
 5104     memset(&nrefs, 0, sizeof(nrefs));
 5105     if (!check_all) {
 5106         /*
 5107          * We need to manually check the first inode item (256)
 5108          * As the following traversal function will only start from
 5109          * the first inode item in the leaf, if inode item (256) is
 5110          * missing we will skip it forever.
 5111          */
 5112         ret = check_fs_first_inode(root);
 5113         if (ret < 0)
 5114             return FATAL_ERROR;
 5115     }
 5116 
 5117 
 5118     level = btrfs_header_level(root->node);
 5119     btrfs_init_path(&path);
 5120 
 5121     if (btrfs_root_generation(root_item) > super_generation + 1) {
 5122         error(
 5123     "invalid root generation for root %llu, have %llu expect (0, %llu)",
 5124               root->root_key.objectid, btrfs_root_generation(root_item),
 5125               super_generation + 1);
 5126         err |= INVALID_GENERATION;
 5127         if (repair) {
 5128             root->node->flags |= EXTENT_BAD_TRANSID;
 5129             ret = recow_extent_buffer(root, root->node);
 5130             if (!ret) {
 5131                 printf("Reset generation for root %llu\n",
 5132                     root->root_key.objectid);
 5133                 err &= ~INVALID_GENERATION;
 5134             }
 5135         }
 5136     }
 5137     if (btrfs_root_refs(root_item) > 0 ||
 5138         btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
 5139         path.nodes[level] = root->node;
 5140         path.slots[level] = 0;
 5141         extent_buffer_get(root->node);
 5142     } else {
 5143         struct btrfs_key key;
 5144 
 5145         btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
 5146         level = root_item->drop_level;
 5147         path.lowest_level = level;
 5148         ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
 5149         if (ret < 0)
 5150             goto out;
 5151         ret = 0;
 5152     }
 5153 
 5154     while (1) {
 5155         ctx.item_count++;
 5156         ret = walk_down_tree(root, &path, &level, &nrefs, check_all);
 5157 
 5158         if (ret > 0)
 5159             err |= ret;
 5160         /* if ret is negative, walk shall stop */
 5161         if (ret < 0) {
 5162             ret = err | FATAL_ERROR;
 5163             break;
 5164         }
 5165 
 5166         ret = walk_up_tree(root, &path, &level);
 5167         if (ret != 0) {
 5168             /* Normal exit, reset ret to err */
 5169             ret = err;
 5170             break;
 5171         }
 5172     }
 5173 
 5174 out:
 5175     btrfs_release_path(&path);
 5176     return ret;
 5177 }
 5178 
 5179 /*
 5180  * Iterate all items in the tree and call check_inode_item() to check.
 5181  *
 5182  * @root:   the root of the tree to be checked.
 5183  *
 5184  * Return 0 if no error found.
 5185  * Return <0 for error.
 5186  */
 5187 static int check_fs_root(struct btrfs_root *root)
 5188 {
 5189     reset_cached_block_groups(root->fs_info);
 5190     return check_btrfs_root(root, 0);
 5191 }
 5192 
 5193 /*
 5194  * Find the relative ref for root_ref and root_backref.
 5195  *
 5196  * @root:   the root of the root tree.
 5197  * @ref_key:    the key of the root ref.
 5198  *
 5199  * Return 0 if no error occurred.
 5200  */
 5201 static int check_root_ref(struct btrfs_root *root, struct btrfs_key *ref_key,
 5202               struct extent_buffer *node, int slot)
 5203 {
 5204     struct btrfs_path path;
 5205     struct btrfs_key key;
 5206     struct btrfs_root_ref *ref;
 5207     struct btrfs_root_ref *backref;
 5208     char ref_name[BTRFS_NAME_LEN] = {0};
 5209     char backref_name[BTRFS_NAME_LEN] = {0};
 5210     u64 ref_dirid;
 5211     u64 ref_seq;
 5212     u32 ref_namelen;
 5213     u64 backref_dirid;
 5214     u64 backref_seq;
 5215     u32 backref_namelen;
 5216     u32 len;
 5217     int ret;
 5218     int err = 0;
 5219 
 5220     ref = btrfs_item_ptr(node, slot, struct btrfs_root_ref);
 5221     ref_dirid = btrfs_root_ref_dirid(node, ref);
 5222     ref_seq = btrfs_root_ref_sequence(node, ref);
 5223     ref_namelen = btrfs_root_ref_name_len(node, ref);
 5224 
 5225     if (ref_namelen <= BTRFS_NAME_LEN) {
 5226         len = ref_namelen;
 5227     } else {
 5228         len = BTRFS_NAME_LEN;
 5229         warning("%s[%llu %llu] ref_name too long",
 5230             ref_key->type == BTRFS_ROOT_REF_KEY ?
 5231             "ROOT_REF" : "ROOT_BACKREF", ref_key->objectid,
 5232             ref_key->offset);
 5233     }
 5234     read_extent_buffer(node, ref_name, (unsigned long)(ref + 1), len);
 5235 
 5236     /* Find relative root_ref */
 5237     key.objectid = ref_key->offset;
 5238     key.type = BTRFS_ROOT_BACKREF_KEY + BTRFS_ROOT_REF_KEY - ref_key->type;
 5239     key.offset = ref_key->objectid;
 5240 
 5241     btrfs_init_path(&path);
 5242     ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
 5243     if (ret) {
 5244         err |= ROOT_REF_MISSING;
 5245         error("%s[%llu %llu] couldn't find relative ref",
 5246               ref_key->type == BTRFS_ROOT_REF_KEY ?
 5247               "ROOT_REF" : "ROOT_BACKREF",
 5248               ref_key->objectid, ref_key->offset);
 5249         goto out;
 5250     }
 5251 
 5252     backref = btrfs_item_ptr(path.nodes[0], path.slots[0],
 5253                  struct btrfs_root_ref);
 5254     backref_dirid = btrfs_root_ref_dirid(path.nodes[0], backref);
 5255     backref_seq = btrfs_root_ref_sequence(path.nodes[0], backref);
 5256     backref_namelen = btrfs_root_ref_name_len(path.nodes[0], backref);
 5257 
 5258     if (backref_namelen <= BTRFS_NAME_LEN) {
 5259         len = backref_namelen;
 5260     } else {
 5261         len = BTRFS_NAME_LEN;
 5262         warning("%s[%llu %llu] ref_name too long",
 5263             key.type == BTRFS_ROOT_REF_KEY ?
 5264             "ROOT_REF" : "ROOT_BACKREF",
 5265             key.objectid, key.offset);
 5266     }
 5267     read_extent_buffer(path.nodes[0], backref_name,
 5268                (unsigned long)(backref + 1), len);
 5269 
 5270     if (ref_dirid != backref_dirid || ref_seq != backref_seq ||
 5271         ref_namelen != backref_namelen ||
 5272         strncmp(ref_name, backref_name, len)) {
 5273         err |= ROOT_REF_MISMATCH;
 5274         error("%s[%llu %llu] mismatch relative ref",
 5275               ref_key->type == BTRFS_ROOT_REF_KEY ?
 5276               "ROOT_REF" : "ROOT_BACKREF",
 5277               ref_key->objectid, ref_key->offset);
 5278     }
 5279 out:
 5280     btrfs_release_path(&path);
 5281     return err;
 5282 }
 5283 
 5284 /*
 5285  * Check all fs/file tree in low_memory mode.
 5286  *
 5287  * 1. for fs tree root item, call check_fs_root()
 5288  * 2. for fs tree root ref/backref, call check_root_ref()
 5289  *
 5290  * Return 0 if no error occurred.
 5291  */
 5292 int check_fs_roots_lowmem(struct btrfs_fs_info *fs_info)
 5293 {
 5294     struct btrfs_root *tree_root = fs_info->tree_root;
 5295     struct btrfs_root *cur_root = NULL;
 5296     struct btrfs_path path;
 5297     struct btrfs_key key;
 5298     struct extent_buffer *node;
 5299     int slot;
 5300     int ret;
 5301     int err = 0;
 5302 
 5303     btrfs_init_path(&path);
 5304     key.objectid = BTRFS_FS_TREE_OBJECTID;
 5305     key.offset = 0;
 5306     key.type = BTRFS_ROOT_ITEM_KEY;
 5307 
 5308     ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0);
 5309     if (ret < 0) {
 5310         err = ret;
 5311         goto out;
 5312     } else if (ret > 0) {
 5313         err = -ENOENT;
 5314         goto out;
 5315     }
 5316 
 5317     while (1) {
 5318         node = path.nodes[0];
 5319         slot = path.slots[0];
 5320         btrfs_item_key_to_cpu(node, &key, slot);
 5321         if (key.objectid > BTRFS_LAST_FREE_OBJECTID)
 5322             goto out;
 5323         if (key.type == BTRFS_INODE_ITEM_KEY &&
 5324             is_fstree(key.objectid)) {
 5325             ret = check_repair_free_space_inode(fs_info, &path);
 5326             /* Check if we still have a valid path to continue */
 5327             if (ret < 0 && path.nodes[0]) {
 5328                 err |= ret;
 5329                 goto next;
 5330             }
 5331             if (ret < 0 && !path.nodes[0])
 5332                 goto out;
 5333         }
 5334         if (key.type == BTRFS_ROOT_ITEM_KEY &&
 5335             fs_root_objectid(key.objectid)) {
 5336             if (key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
 5337                 cur_root = btrfs_read_fs_root_no_cache(fs_info,
 5338                                        &key);
 5339             } else {
 5340                 key.offset = (u64)-1;
 5341                 cur_root = btrfs_read_fs_root(fs_info, &key);
 5342             }
 5343 
 5344             if (IS_ERR(cur_root)) {
 5345                 error("Fail to read fs/subvol tree: %lld",
 5346                       key.objectid);
 5347                 err = -EIO;
 5348                 goto next;
 5349             }
 5350 
 5351             ret = check_fs_root(cur_root);
 5352             err |= ret;
 5353 
 5354             if (key.objectid == BTRFS_TREE_RELOC_OBJECTID)
 5355                 btrfs_free_fs_root(cur_root);
 5356         } else if (key.type == BTRFS_ROOT_REF_KEY ||
 5357                 key.type == BTRFS_ROOT_BACKREF_KEY) {
 5358             ret = check_root_ref(tree_root, &key, node, slot);
 5359             err |= ret;
 5360         }
 5361 next:
 5362         /*
 5363          * In repair mode, our path is no longer reliable as CoW can
 5364          * happen.  We need to reset our path.
 5365          */
 5366         if (repair) {
 5367             btrfs_release_path(&path);
 5368             ret = btrfs_search_slot(NULL, tree_root, &key, &path,
 5369                         0, 0);
 5370             if (ret < 0) {
 5371                 if (!err)
 5372                     err = ret;
 5373                 goto out;
 5374             }
 5375             if (ret > 0) {
 5376                 /* Key not found, but already at next item */
 5377                 if (path.slots[0] <
 5378                     btrfs_header_nritems(path.nodes[0]))
 5379                     continue;
 5380                 /* falls through to next leaf */
 5381             }
 5382         }
 5383         ret = btrfs_next_item(tree_root, &path);
 5384         if (ret > 0)
 5385             goto out;
 5386         if (ret < 0) {
 5387             err = ret;
 5388             goto out;
 5389         }
 5390     }
 5391 
 5392 out:
 5393     btrfs_release_path(&path);
 5394     return err;
 5395 }
 5396 
 5397 /*
 5398  * Low memory usage version check_chunks_and_extents.
 5399  */
 5400 int check_chunks_and_extents_lowmem(struct btrfs_fs_info *fs_info)
 5401 {
 5402     struct btrfs_path path;
 5403     struct btrfs_key old_key;
 5404     struct btrfs_key key;
 5405     struct btrfs_root *root1;
 5406     struct btrfs_root *root;
 5407     struct btrfs_root *cur_root;
 5408     int err = 0;
 5409     int ret;
 5410 
 5411     root = fs_info->fs_root;
 5412 
 5413     root1 = root->fs_info->chunk_root;
 5414     ret = check_btrfs_root(root1, 1);
 5415     err |= ret;
 5416 
 5417     root1 = root->fs_info->tree_root;
 5418     ret = check_btrfs_root(root1, 1);
 5419     err |= ret;
 5420 
 5421     btrfs_init_path(&path);
 5422     key.objectid = BTRFS_EXTENT_TREE_OBJECTID;
 5423     key.offset = 0;
 5424     key.type = BTRFS_ROOT_ITEM_KEY;
 5425 
 5426     ret = btrfs_search_slot(NULL, root1, &key, &path, 0, 0);
 5427     if (ret) {
 5428         error("cannot find extent tree in tree_root");
 5429         goto out;
 5430     }
 5431 
 5432     while (1) {
 5433         btrfs_item_key_to_cpu(path.nodes[0], &key, path.slots[0]);
 5434         if (key.type != BTRFS_ROOT_ITEM_KEY)
 5435             goto next;
 5436         old_key = key;
 5437         key.offset = (u64)-1;
 5438 
 5439         if (key.objectid == BTRFS_TREE_RELOC_OBJECTID)
 5440             cur_root = btrfs_read_fs_root_no_cache(root->fs_info,
 5441                     &key);
 5442         else
 5443             cur_root = btrfs_read_fs_root(root->fs_info, &key);
 5444         if (IS_ERR(cur_root) || !cur_root) {
 5445             error("failed to read tree: %lld", key.objectid);
 5446             goto next;
 5447         }
 5448 
 5449         ret = check_btrfs_root(cur_root, 1);
 5450         err |= ret;
 5451 
 5452         if (key.objectid == BTRFS_TREE_RELOC_OBJECTID)
 5453             btrfs_free_fs_root(cur_root);
 5454 
 5455         btrfs_release_path(&path);
 5456         ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
 5457                     &old_key, &path, 0, 0);
 5458         if (ret)
 5459             goto out;
 5460 next:
 5461         ret = btrfs_next_item(root1, &path);
 5462         if (ret)
 5463             goto out;
 5464     }
 5465 out:
 5466 
 5467     if (repair) {
 5468         ret = end_avoid_extents_overwrite(fs_info);
 5469         if (ret < 0)
 5470             ret = FATAL_ERROR;
 5471         err |= ret;
 5472 
 5473         reset_cached_block_groups(fs_info);
 5474         /* update block accounting */
 5475         ret = repair_block_accounting(fs_info);
 5476         if (ret)
 5477             err |= ret;
 5478         else
 5479             err &= ~BG_ACCOUNTING_ERROR;
 5480     }
 5481 
 5482     btrfs_release_path(&path);
 5483     return err;
 5484 }