"Fossies" - the Fresh Open Source Software Archive

Member "btrfs-progs-v5.4.1/check/main.c" (9 Jan 2020, 274219 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 "main.c" see the Fossies "Dox" file reference documentation and the latest Fossies "Diffs" side-by-side code changes report: v5.4_vs_v5.4.1.

    1 /*
    2  * Copyright (C) 2007 Oracle.  All rights reserved.
    3  *
    4  * This program is free software; you can redistribute it and/or
    5  * modify it under the terms of the GNU General Public
    6  * License v2 as published by the Free Software Foundation.
    7  *
    8  * This program is distributed in the hope that it will be useful,
    9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
   10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   11  * General Public License for more details.
   12  *
   13  * You should have received a copy of the GNU General Public
   14  * License along with this program; if not, write to the
   15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   16  * Boston, MA 021110-1307, USA.
   17  */
   18 
   19 #include <stdio.h>
   20 #include <stdlib.h>
   21 #include <unistd.h>
   22 #include <fcntl.h>
   23 #include <sys/types.h>
   24 #include <sys/stat.h>
   25 #include <unistd.h>
   26 #include <getopt.h>
   27 #include <uuid/uuid.h>
   28 #include <time.h>
   29 #include "ctree.h"
   30 #include "volumes.h"
   31 #include "repair.h"
   32 #include "disk-io.h"
   33 #include "print-tree.h"
   34 #include "common/task-utils.h"
   35 #include "transaction.h"
   36 #include "common/utils.h"
   37 #include "cmds/commands.h"
   38 #include "free-space-cache.h"
   39 #include "free-space-tree.h"
   40 #include "common/rbtree-utils.h"
   41 #include "backref.h"
   42 #include "kernel-shared/ulist.h"
   43 #include "hash.h"
   44 #include "common/help.h"
   45 #include "check/common.h"
   46 #include "check/mode-common.h"
   47 #include "check/mode-original.h"
   48 #include "check/mode-lowmem.h"
   49 #include "check/qgroup-verify.h"
   50 
   51 u64 bytes_used = 0;
   52 u64 total_csum_bytes = 0;
   53 u64 total_btree_bytes = 0;
   54 u64 total_fs_tree_bytes = 0;
   55 u64 total_extent_tree_bytes = 0;
   56 u64 btree_space_waste = 0;
   57 u64 data_bytes_allocated = 0;
   58 u64 data_bytes_referenced = 0;
   59 LIST_HEAD(duplicate_extents);
   60 LIST_HEAD(delete_items);
   61 int no_holes = 0;
   62 static int is_free_space_tree = 0;
   63 int init_extent_tree = 0;
   64 int check_data_csum = 0;
   65 struct btrfs_fs_info *global_info;
   66 struct task_ctx ctx = { 0 };
   67 struct cache_tree *roots_info_cache = NULL;
   68 
   69 enum btrfs_check_mode {
   70     CHECK_MODE_ORIGINAL,
   71     CHECK_MODE_LOWMEM,
   72     CHECK_MODE_UNKNOWN,
   73     CHECK_MODE_DEFAULT = CHECK_MODE_ORIGINAL
   74 };
   75 
   76 static enum btrfs_check_mode check_mode = CHECK_MODE_DEFAULT;
   77 
   78 struct device_record {
   79     struct rb_node node;
   80     u64 devid;
   81 
   82     u64 generation;
   83 
   84     u64 objectid;
   85     u8  type;
   86     u64 offset;
   87 
   88     u64 total_byte;
   89     u64 byte_used;
   90 
   91     u64 real_used;
   92 };
   93 
   94 static int compare_data_backref(struct rb_node *node1, struct rb_node *node2)
   95 {
   96     struct extent_backref *ext1 = rb_node_to_extent_backref(node1);
   97     struct extent_backref *ext2 = rb_node_to_extent_backref(node2);
   98     struct data_backref *back1 = to_data_backref(ext1);
   99     struct data_backref *back2 = to_data_backref(ext2);
  100 
  101     WARN_ON(!ext1->is_data);
  102     WARN_ON(!ext2->is_data);
  103 
  104     /* parent and root are a union, so this covers both */
  105     if (back1->parent > back2->parent)
  106         return 1;
  107     if (back1->parent < back2->parent)
  108         return -1;
  109 
  110     /* This is a full backref and the parents match. */
  111     if (back1->node.full_backref)
  112         return 0;
  113 
  114     if (back1->owner > back2->owner)
  115         return 1;
  116     if (back1->owner < back2->owner)
  117         return -1;
  118 
  119     if (back1->offset > back2->offset)
  120         return 1;
  121     if (back1->offset < back2->offset)
  122         return -1;
  123 
  124     if (back1->found_ref && back2->found_ref) {
  125         if (back1->disk_bytenr > back2->disk_bytenr)
  126             return 1;
  127         if (back1->disk_bytenr < back2->disk_bytenr)
  128             return -1;
  129 
  130         if (back1->bytes > back2->bytes)
  131             return 1;
  132         if (back1->bytes < back2->bytes)
  133             return -1;
  134     }
  135 
  136     return 0;
  137 }
  138 
  139 static int compare_tree_backref(struct rb_node *node1, struct rb_node *node2)
  140 {
  141     struct extent_backref *ext1 = rb_node_to_extent_backref(node1);
  142     struct extent_backref *ext2 = rb_node_to_extent_backref(node2);
  143     struct tree_backref *back1 = to_tree_backref(ext1);
  144     struct tree_backref *back2 = to_tree_backref(ext2);
  145 
  146     WARN_ON(ext1->is_data);
  147     WARN_ON(ext2->is_data);
  148 
  149     /* parent and root are a union, so this covers both */
  150     if (back1->parent > back2->parent)
  151         return 1;
  152     if (back1->parent < back2->parent)
  153         return -1;
  154 
  155     return 0;
  156 }
  157 
  158 static int compare_extent_backref(struct rb_node *node1, struct rb_node *node2)
  159 {
  160     struct extent_backref *ext1 = rb_node_to_extent_backref(node1);
  161     struct extent_backref *ext2 = rb_node_to_extent_backref(node2);
  162 
  163     if (ext1->is_data > ext2->is_data)
  164         return 1;
  165 
  166     if (ext1->is_data < ext2->is_data)
  167         return -1;
  168 
  169     if (ext1->full_backref > ext2->full_backref)
  170         return 1;
  171     if (ext1->full_backref < ext2->full_backref)
  172         return -1;
  173 
  174     if (ext1->is_data)
  175         return compare_data_backref(node1, node2);
  176     else
  177         return compare_tree_backref(node1, node2);
  178 }
  179 
  180 static void print_status_check_line(void *p)
  181 {
  182     struct task_ctx *priv = p;
  183     const char *task_position_string[] = {
  184         "[1/7] checking root items                     ",
  185         "[2/7] checking extents                        ",
  186         is_free_space_tree ?
  187         "[3/7] checking free space tree                " :
  188         "[3/7] checking free space cache               ",
  189         "[4/7] checking fs roots                       ",
  190         check_data_csum ?
  191         "[5/7] checking csums against data             " :
  192         "[5/7] checking csums (without verifying data) ",
  193         "[6/7] checking root refs                      ",
  194         "[7/7] checking quota groups                   ",
  195     };
  196     time_t elapsed;
  197     int hours;
  198     int minutes;
  199     int seconds;
  200 
  201     elapsed = time(NULL) - priv->start_time;
  202     hours   = elapsed  / 3600;
  203     elapsed -= hours   * 3600;
  204     minutes = elapsed  / 60;
  205     elapsed -= minutes * 60;
  206     seconds = elapsed;
  207 
  208     printf("%s (%d:%02d:%02d elapsed", task_position_string[priv->tp],
  209             hours, minutes, seconds);
  210     if (priv->item_count > 0)
  211         printf(", %llu items checked)\r", priv->item_count);
  212     else
  213         printf(")\r");
  214     fflush(stdout);
  215 }
  216 
  217 static void *print_status_check(void *p)
  218 {
  219     struct task_ctx *priv = p;
  220 
  221     /* 1 second */
  222     task_period_start(priv->info, 1000);
  223 
  224     if (priv->tp == TASK_NOTHING)
  225         return NULL;
  226 
  227     while (1) {
  228         print_status_check_line(p);
  229         task_period_wait(priv->info);
  230     }
  231     return NULL;
  232 }
  233 
  234 static int print_status_return(void *p)
  235 {
  236     print_status_check_line(p);
  237     printf("\n");
  238     fflush(stdout);
  239 
  240     return 0;
  241 }
  242 
  243 static enum btrfs_check_mode parse_check_mode(const char *str)
  244 {
  245     if (strcmp(str, "lowmem") == 0)
  246         return CHECK_MODE_LOWMEM;
  247     if (strcmp(str, "orig") == 0)
  248         return CHECK_MODE_ORIGINAL;
  249     if (strcmp(str, "original") == 0)
  250         return CHECK_MODE_ORIGINAL;
  251 
  252     return CHECK_MODE_UNKNOWN;
  253 }
  254 
  255 /* Compatible function to allow reuse of old codes */
  256 static u64 first_extent_gap(struct rb_root *holes)
  257 {
  258     struct file_extent_hole *hole;
  259 
  260     if (RB_EMPTY_ROOT(holes))
  261         return (u64)-1;
  262 
  263     hole = rb_entry(rb_first(holes), struct file_extent_hole, node);
  264     return hole->start;
  265 }
  266 
  267 static int compare_hole(struct rb_node *node1, struct rb_node *node2)
  268 {
  269     struct file_extent_hole *hole1;
  270     struct file_extent_hole *hole2;
  271 
  272     hole1 = rb_entry(node1, struct file_extent_hole, node);
  273     hole2 = rb_entry(node2, struct file_extent_hole, node);
  274 
  275     if (hole1->start > hole2->start)
  276         return -1;
  277     if (hole1->start < hole2->start)
  278         return 1;
  279     /* Now hole1->start == hole2->start */
  280     if (hole1->len >= hole2->len)
  281         /*
  282          * Hole 1 will be merge center
  283          * Same hole will be merged later
  284          */
  285         return -1;
  286     /* Hole 2 will be merge center */
  287     return 1;
  288 }
  289 
  290 /*
  291  * Add a hole to the record
  292  *
  293  * This will do hole merge for copy_file_extent_holes(),
  294  * which will ensure there won't be continuous holes.
  295  */
  296 static int add_file_extent_hole(struct rb_root *holes,
  297                 u64 start, u64 len)
  298 {
  299     struct file_extent_hole *hole;
  300     struct file_extent_hole *prev = NULL;
  301     struct file_extent_hole *next = NULL;
  302 
  303     hole = malloc(sizeof(*hole));
  304     if (!hole)
  305         return -ENOMEM;
  306     hole->start = start;
  307     hole->len = len;
  308     /* Since compare will not return 0, no -EEXIST will happen */
  309     rb_insert(holes, &hole->node, compare_hole);
  310 
  311     /* simple merge with previous hole */
  312     if (rb_prev(&hole->node))
  313         prev = rb_entry(rb_prev(&hole->node), struct file_extent_hole,
  314                 node);
  315     if (prev && prev->start + prev->len >= hole->start) {
  316         hole->len = hole->start + hole->len - prev->start;
  317         hole->start = prev->start;
  318         rb_erase(&prev->node, holes);
  319         free(prev);
  320         prev = NULL;
  321     }
  322 
  323     /* iterate merge with next holes */
  324     while (1) {
  325         if (!rb_next(&hole->node))
  326             break;
  327         next = rb_entry(rb_next(&hole->node), struct file_extent_hole,
  328                     node);
  329         if (hole->start + hole->len >= next->start) {
  330             if (hole->start + hole->len <= next->start + next->len)
  331                 hole->len = next->start + next->len -
  332                         hole->start;
  333             rb_erase(&next->node, holes);
  334             free(next);
  335             next = NULL;
  336         } else
  337             break;
  338     }
  339     return 0;
  340 }
  341 
  342 static int compare_hole_range(struct rb_node *node, void *data)
  343 {
  344     struct file_extent_hole *hole;
  345     u64 start;
  346 
  347     hole = (struct file_extent_hole *)data;
  348     start = hole->start;
  349 
  350     hole = rb_entry(node, struct file_extent_hole, node);
  351     if (start < hole->start)
  352         return -1;
  353     if (start >= hole->start && start < hole->start + hole->len)
  354         return 0;
  355     return 1;
  356 }
  357 
  358 /*
  359  * Delete a hole in the record
  360  *
  361  * This will do the hole split and is much restrict than add.
  362  */
  363 static int del_file_extent_hole(struct rb_root *holes,
  364                 u64 start, u64 len)
  365 {
  366     struct file_extent_hole *hole;
  367     struct file_extent_hole tmp;
  368     u64 prev_start = 0;
  369     u64 prev_len = 0;
  370     u64 next_start = 0;
  371     u64 next_len = 0;
  372     struct rb_node *node;
  373     int have_prev = 0;
  374     int have_next = 0;
  375     int ret = 0;
  376 
  377     tmp.start = start;
  378     tmp.len = len;
  379     node = rb_search(holes, &tmp, compare_hole_range, NULL);
  380     if (!node)
  381         return -EEXIST;
  382     hole = rb_entry(node, struct file_extent_hole, node);
  383     if (start + len > hole->start + hole->len)
  384         return -EEXIST;
  385 
  386     /*
  387      * Now there will be no overlap, delete the hole and re-add the
  388      * split(s) if they exists.
  389      */
  390     if (start > hole->start) {
  391         prev_start = hole->start;
  392         prev_len = start - hole->start;
  393         have_prev = 1;
  394     }
  395     if (hole->start + hole->len > start + len) {
  396         next_start = start + len;
  397         next_len = hole->start + hole->len - start - len;
  398         have_next = 1;
  399     }
  400     rb_erase(node, holes);
  401     free(hole);
  402     if (have_prev) {
  403         ret = add_file_extent_hole(holes, prev_start, prev_len);
  404         if (ret < 0)
  405             return ret;
  406     }
  407     if (have_next) {
  408         ret = add_file_extent_hole(holes, next_start, next_len);
  409         if (ret < 0)
  410             return ret;
  411     }
  412     return 0;
  413 }
  414 
  415 static int copy_file_extent_holes(struct rb_root *dst,
  416                   struct rb_root *src)
  417 {
  418     struct file_extent_hole *hole;
  419     struct rb_node *node;
  420     int ret = 0;
  421 
  422     node = rb_first(src);
  423     while (node) {
  424         hole = rb_entry(node, struct file_extent_hole, node);
  425         ret = add_file_extent_hole(dst, hole->start, hole->len);
  426         if (ret)
  427             break;
  428         node = rb_next(node);
  429     }
  430     return ret;
  431 }
  432 
  433 static void free_file_extent_holes(struct rb_root *holes)
  434 {
  435     struct rb_node *node;
  436     struct file_extent_hole *hole;
  437 
  438     node = rb_first(holes);
  439     while (node) {
  440         hole = rb_entry(node, struct file_extent_hole, node);
  441         rb_erase(node, holes);
  442         free(hole);
  443         node = rb_first(holes);
  444     }
  445 }
  446 
  447 static void record_root_in_trans(struct btrfs_trans_handle *trans,
  448                  struct btrfs_root *root)
  449 {
  450     if (root->last_trans != trans->transid) {
  451         root->track_dirty = 1;
  452         root->last_trans = trans->transid;
  453         root->commit_root = root->node;
  454         extent_buffer_get(root->node);
  455     }
  456 }
  457 
  458 static int device_record_compare(struct rb_node *node1, struct rb_node *node2)
  459 {
  460     struct device_record *rec1;
  461     struct device_record *rec2;
  462 
  463     rec1 = rb_entry(node1, struct device_record, node);
  464     rec2 = rb_entry(node2, struct device_record, node);
  465     if (rec1->devid > rec2->devid)
  466         return -1;
  467     else if (rec1->devid < rec2->devid)
  468         return 1;
  469     else
  470         return 0;
  471 }
  472 
  473 static struct inode_record *clone_inode_rec(struct inode_record *orig_rec)
  474 {
  475     struct inode_record *rec;
  476     struct inode_backref *backref;
  477     struct inode_backref *orig;
  478     struct inode_backref *tmp;
  479     struct mismatch_dir_hash_record *hash_record;
  480     struct mismatch_dir_hash_record *new_record;
  481     struct unaligned_extent_rec_t *src;
  482     struct unaligned_extent_rec_t *dst;
  483     struct rb_node *rb;
  484     size_t size;
  485     int ret;
  486 
  487     rec = malloc(sizeof(*rec));
  488     if (!rec)
  489         return ERR_PTR(-ENOMEM);
  490     memcpy(rec, orig_rec, sizeof(*rec));
  491     rec->refs = 1;
  492     INIT_LIST_HEAD(&rec->backrefs);
  493     INIT_LIST_HEAD(&rec->mismatch_dir_hash);
  494     INIT_LIST_HEAD(&rec->unaligned_extent_recs);
  495     rec->holes = RB_ROOT;
  496 
  497     list_for_each_entry(orig, &orig_rec->backrefs, list) {
  498         size = sizeof(*orig) + orig->namelen + 1;
  499         backref = malloc(size);
  500         if (!backref) {
  501             ret = -ENOMEM;
  502             goto cleanup;
  503         }
  504         memcpy(backref, orig, size);
  505         list_add_tail(&backref->list, &rec->backrefs);
  506     }
  507     list_for_each_entry(hash_record, &orig_rec->mismatch_dir_hash, list) {
  508         size = sizeof(*hash_record) + hash_record->namelen;
  509         new_record = malloc(size);
  510         if (!new_record) {
  511             ret = -ENOMEM;
  512             goto cleanup;
  513         }
  514         memcpy(&new_record, hash_record, size);
  515         list_add_tail(&new_record->list, &rec->mismatch_dir_hash);
  516     }
  517     list_for_each_entry(src, &orig_rec->unaligned_extent_recs, list) {
  518         size = sizeof(*src);
  519         dst = malloc(size);
  520         if (!dst) {
  521             ret = -ENOMEM;
  522             goto cleanup;
  523         }
  524         memcpy(dst, src, size);
  525         list_add_tail(&dst->list, &rec->unaligned_extent_recs);
  526     }
  527 
  528     ret = copy_file_extent_holes(&rec->holes, &orig_rec->holes);
  529     if (ret < 0)
  530         goto cleanup_rb;
  531 
  532     return rec;
  533 
  534 cleanup_rb:
  535     rb = rb_first(&rec->holes);
  536     while (rb) {
  537         struct file_extent_hole *hole;
  538 
  539         hole = rb_entry(rb, struct file_extent_hole, node);
  540         rb = rb_next(rb);
  541         free(hole);
  542     }
  543 
  544 cleanup:
  545     if (!list_empty(&rec->backrefs))
  546         list_for_each_entry_safe(orig, tmp, &rec->backrefs, list) {
  547             list_del(&orig->list);
  548             free(orig);
  549         }
  550 
  551     if (!list_empty(&rec->mismatch_dir_hash)) {
  552         list_for_each_entry_safe(hash_record, new_record,
  553                 &rec->mismatch_dir_hash, list) {
  554             list_del(&hash_record->list);
  555             free(hash_record);
  556         }
  557     }
  558     if (!list_empty(&rec->unaligned_extent_recs))
  559         list_for_each_entry_safe(src, dst, &rec->unaligned_extent_recs,
  560                 list) {
  561             list_del(&src->list);
  562             free(src);
  563         }
  564 
  565     free(rec);
  566 
  567     return ERR_PTR(ret);
  568 }
  569 
  570 static void print_inode_error(struct btrfs_root *root, struct inode_record *rec)
  571 {
  572     u64 root_objectid = root->root_key.objectid;
  573     int errors = rec->errors;
  574 
  575     if (!errors)
  576         return;
  577     /* reloc root errors, we print its corresponding fs root objectid*/
  578     if (root_objectid == BTRFS_TREE_RELOC_OBJECTID) {
  579         root_objectid = root->root_key.offset;
  580         fprintf(stderr, "reloc");
  581     }
  582     fprintf(stderr, "root %llu inode %llu errors %x",
  583         (unsigned long long) root_objectid,
  584         (unsigned long long) rec->ino, rec->errors);
  585 
  586     if (errors & I_ERR_NO_INODE_ITEM)
  587         fprintf(stderr, ", no inode item");
  588     if (errors & I_ERR_NO_ORPHAN_ITEM)
  589         fprintf(stderr, ", no orphan item");
  590     if (errors & I_ERR_DUP_INODE_ITEM)
  591         fprintf(stderr, ", dup inode item");
  592     if (errors & I_ERR_DUP_DIR_INDEX)
  593         fprintf(stderr, ", dup dir index");
  594     if (errors & I_ERR_ODD_DIR_ITEM)
  595         fprintf(stderr, ", odd dir item");
  596     if (errors & I_ERR_ODD_FILE_EXTENT)
  597         fprintf(stderr, ", odd file extent");
  598     if (errors & I_ERR_BAD_FILE_EXTENT)
  599         fprintf(stderr, ", bad file extent");
  600     if (errors & I_ERR_FILE_EXTENT_OVERLAP)
  601         fprintf(stderr, ", file extent overlap");
  602     if (errors & I_ERR_FILE_EXTENT_TOO_LARGE)
  603         fprintf(stderr, ", inline file extent too large");
  604     if (errors & I_ERR_FILE_EXTENT_DISCOUNT)
  605         fprintf(stderr, ", file extent discount");
  606     if (errors & I_ERR_DIR_ISIZE_WRONG)
  607         fprintf(stderr, ", dir isize wrong");
  608     if (errors & I_ERR_FILE_NBYTES_WRONG)
  609         fprintf(stderr, ", nbytes wrong");
  610     if (errors & I_ERR_ODD_CSUM_ITEM)
  611         fprintf(stderr, ", odd csum item");
  612     if (errors & I_ERR_SOME_CSUM_MISSING)
  613         fprintf(stderr, ", some csum missing");
  614     if (errors & I_ERR_LINK_COUNT_WRONG)
  615         fprintf(stderr, ", link count wrong");
  616     if (errors & I_ERR_ODD_INODE_FLAGS)
  617         fprintf(stderr, ", odd inode flags");
  618     if (errors & I_ERR_INLINE_RAM_BYTES_WRONG)
  619         fprintf(stderr, ", invalid inline ram bytes");
  620     if (errors & I_ERR_INVALID_IMODE)
  621         fprintf(stderr, ", invalid inode mode bit 0%o",
  622             rec->imode & ~07777);
  623     if (errors & I_ERR_INVALID_GEN)
  624         fprintf(stderr, ", invalid inode generation");
  625     fprintf(stderr, "\n");
  626 
  627     /* Print the holes if needed */
  628     if (errors & I_ERR_FILE_EXTENT_DISCOUNT) {
  629         struct file_extent_hole *hole;
  630         struct rb_node *node;
  631         int found = 0;
  632 
  633         node = rb_first(&rec->holes);
  634         fprintf(stderr, "Found file extent holes:\n");
  635         while (node) {
  636             found = 1;
  637             hole = rb_entry(node, struct file_extent_hole, node);
  638             fprintf(stderr, "\tstart: %llu, len: %llu\n",
  639                 hole->start, hole->len);
  640             node = rb_next(node);
  641         }
  642         if (!found)
  643             fprintf(stderr, "\tstart: 0, len: %llu\n",
  644                 round_up(rec->isize,
  645                      root->fs_info->sectorsize));
  646     }
  647 
  648     /* Print dir item with mismatch hash */
  649     if (errors & I_ERR_MISMATCH_DIR_HASH) {
  650         struct mismatch_dir_hash_record *hash_record;
  651 
  652         fprintf(stderr, "Dir items with mismatch hash:\n");
  653         list_for_each_entry(hash_record, &rec->mismatch_dir_hash,
  654                 list) {
  655             char *namebuf = (char *)(hash_record + 1);
  656             u32 crc;
  657 
  658             crc = btrfs_name_hash(namebuf, hash_record->namelen);
  659             fprintf(stderr,
  660             "\tname: %.*s namelen: %u wanted 0x%08x has 0x%08llx\n",
  661                 hash_record->namelen, namebuf,
  662                 hash_record->namelen, crc,
  663                 hash_record->key.offset);
  664         }
  665     }
  666 }
  667 
  668 static void print_ref_error(int errors)
  669 {
  670     if (errors & REF_ERR_NO_DIR_ITEM)
  671         fprintf(stderr, ", no dir item");
  672     if (errors & REF_ERR_NO_DIR_INDEX)
  673         fprintf(stderr, ", no dir index");
  674     if (errors & REF_ERR_NO_INODE_REF)
  675         fprintf(stderr, ", no inode ref");
  676     if (errors & REF_ERR_DUP_DIR_ITEM)
  677         fprintf(stderr, ", dup dir item");
  678     if (errors & REF_ERR_DUP_DIR_INDEX)
  679         fprintf(stderr, ", dup dir index");
  680     if (errors & REF_ERR_DUP_INODE_REF)
  681         fprintf(stderr, ", dup inode ref");
  682     if (errors & REF_ERR_INDEX_UNMATCH)
  683         fprintf(stderr, ", index mismatch");
  684     if (errors & REF_ERR_FILETYPE_UNMATCH)
  685         fprintf(stderr, ", filetype mismatch");
  686     if (errors & REF_ERR_NAME_TOO_LONG)
  687         fprintf(stderr, ", name too long");
  688     if (errors & REF_ERR_NO_ROOT_REF)
  689         fprintf(stderr, ", no root ref");
  690     if (errors & REF_ERR_NO_ROOT_BACKREF)
  691         fprintf(stderr, ", no root backref");
  692     if (errors & REF_ERR_DUP_ROOT_REF)
  693         fprintf(stderr, ", dup root ref");
  694     if (errors & REF_ERR_DUP_ROOT_BACKREF)
  695         fprintf(stderr, ", dup root backref");
  696     fprintf(stderr, "\n");
  697 }
  698 
  699 static struct inode_record *get_inode_rec(struct cache_tree *inode_cache,
  700                       u64 ino, int mod)
  701 {
  702     struct ptr_node *node;
  703     struct cache_extent *cache;
  704     struct inode_record *rec = NULL;
  705     int ret;
  706 
  707     cache = lookup_cache_extent(inode_cache, ino, 1);
  708     if (cache) {
  709         node = container_of(cache, struct ptr_node, cache);
  710         rec = node->data;
  711         if (mod && rec->refs > 1) {
  712             node->data = clone_inode_rec(rec);
  713             if (IS_ERR(node->data))
  714                 return node->data;
  715             rec->refs--;
  716             rec = node->data;
  717         }
  718     } else if (mod) {
  719         rec = calloc(1, sizeof(*rec));
  720         if (!rec)
  721             return ERR_PTR(-ENOMEM);
  722         rec->ino = ino;
  723         rec->extent_start = (u64)-1;
  724         rec->refs = 1;
  725         INIT_LIST_HEAD(&rec->backrefs);
  726         INIT_LIST_HEAD(&rec->mismatch_dir_hash);
  727         INIT_LIST_HEAD(&rec->unaligned_extent_recs);
  728         rec->holes = RB_ROOT;
  729 
  730         node = malloc(sizeof(*node));
  731         if (!node) {
  732             free(rec);
  733             return ERR_PTR(-ENOMEM);
  734         }
  735         node->cache.start = ino;
  736         node->cache.size = 1;
  737         node->data = rec;
  738 
  739         if (ino == BTRFS_FREE_INO_OBJECTID)
  740             rec->found_link = 1;
  741 
  742         ret = insert_cache_extent(inode_cache, &node->cache);
  743         if (ret)
  744             return ERR_PTR(-EEXIST);
  745     }
  746     return rec;
  747 }
  748 
  749 static void free_unaligned_extent_recs(struct list_head *unaligned_extent_recs)
  750 {
  751     struct unaligned_extent_rec_t *urec;
  752 
  753     while (!list_empty(unaligned_extent_recs)) {
  754         urec = list_entry(unaligned_extent_recs->next,
  755                 struct unaligned_extent_rec_t, list);
  756         list_del(&urec->list);
  757         free(urec);
  758     }
  759 }
  760 
  761 static void free_inode_rec(struct inode_record *rec)
  762 {
  763     struct inode_backref *backref;
  764     struct mismatch_dir_hash_record *hash;
  765     struct mismatch_dir_hash_record *next;
  766 
  767     if (--rec->refs > 0)
  768         return;
  769 
  770     while (!list_empty(&rec->backrefs)) {
  771         backref = to_inode_backref(rec->backrefs.next);
  772         list_del(&backref->list);
  773         free(backref);
  774     }
  775     list_for_each_entry_safe(hash, next, &rec->mismatch_dir_hash, list)
  776         free(hash);
  777     free_unaligned_extent_recs(&rec->unaligned_extent_recs);
  778     free_file_extent_holes(&rec->holes);
  779     free(rec);
  780 }
  781 
  782 static int can_free_inode_rec(struct inode_record *rec)
  783 {
  784     if (!rec->errors && rec->checked && rec->found_inode_item &&
  785         rec->nlink == rec->found_link && list_empty(&rec->backrefs))
  786         return 1;
  787     return 0;
  788 }
  789 
  790 static void maybe_free_inode_rec(struct cache_tree *inode_cache,
  791                  struct inode_record *rec)
  792 {
  793     struct cache_extent *cache;
  794     struct inode_backref *tmp, *backref;
  795     struct ptr_node *node;
  796     u8 filetype;
  797 
  798     if (!rec->found_inode_item)
  799         return;
  800 
  801     filetype = imode_to_type(rec->imode);
  802     list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
  803         if (backref->found_dir_item && backref->found_dir_index) {
  804             if (backref->filetype != filetype)
  805                 backref->errors |= REF_ERR_FILETYPE_UNMATCH;
  806             if (!backref->errors && backref->found_inode_ref &&
  807                 rec->nlink == rec->found_link) {
  808                 list_del(&backref->list);
  809                 free(backref);
  810             }
  811         }
  812     }
  813 
  814     if (!rec->checked || rec->merging)
  815         return;
  816 
  817     if (!is_valid_imode(rec->imode))
  818         rec->errors |= I_ERR_INVALID_IMODE;
  819     if (S_ISDIR(rec->imode)) {
  820         if (rec->found_size != rec->isize)
  821             rec->errors |= I_ERR_DIR_ISIZE_WRONG;
  822         if (rec->found_file_extent)
  823             rec->errors |= I_ERR_ODD_FILE_EXTENT;
  824     } else if (S_ISREG(rec->imode) || S_ISLNK(rec->imode)) {
  825         if (rec->found_dir_item)
  826             rec->errors |= I_ERR_ODD_DIR_ITEM;
  827         /* Orphan inodes don't have correct nbytes */
  828         if (rec->nlink > 0 && rec->found_size != rec->nbytes)
  829             rec->errors |= I_ERR_FILE_NBYTES_WRONG;
  830         if (rec->nlink > 0 && !no_holes &&
  831             (rec->extent_end < rec->isize ||
  832              first_extent_gap(&rec->holes) < rec->isize))
  833             rec->errors |= I_ERR_FILE_EXTENT_DISCOUNT;
  834     }
  835 
  836     if (S_ISREG(rec->imode) || S_ISLNK(rec->imode)) {
  837         if (rec->found_csum_item && rec->nodatasum)
  838             rec->errors |= I_ERR_ODD_CSUM_ITEM;
  839         if (rec->some_csum_missing && !rec->nodatasum)
  840             rec->errors |= I_ERR_SOME_CSUM_MISSING;
  841     }
  842 
  843     BUG_ON(rec->refs != 1);
  844     if (can_free_inode_rec(rec)) {
  845         cache = lookup_cache_extent(inode_cache, rec->ino, 1);
  846         node = container_of(cache, struct ptr_node, cache);
  847         BUG_ON(node->data != rec);
  848         remove_cache_extent(inode_cache, &node->cache);
  849         free(node);
  850         free_inode_rec(rec);
  851     }
  852 }
  853 
  854 static int check_orphan_item(struct btrfs_root *root, u64 ino)
  855 {
  856     struct btrfs_path path;
  857     struct btrfs_key key;
  858     int ret;
  859 
  860     key.objectid = BTRFS_ORPHAN_OBJECTID;
  861     key.type = BTRFS_ORPHAN_ITEM_KEY;
  862     key.offset = ino;
  863 
  864     btrfs_init_path(&path);
  865     ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
  866     btrfs_release_path(&path);
  867     if (ret > 0)
  868         ret = -ENOENT;
  869     return ret;
  870 }
  871 
  872 static int process_inode_item(struct extent_buffer *eb,
  873                   int slot, struct btrfs_key *key,
  874                   struct shared_node *active_node)
  875 {
  876     struct inode_record *rec;
  877     struct btrfs_inode_item *item;
  878     u64 gen_uplimit;
  879     u64 flags;
  880 
  881     rec = active_node->current;
  882     BUG_ON(rec->ino != key->objectid || rec->refs > 1);
  883     if (rec->found_inode_item) {
  884         rec->errors |= I_ERR_DUP_INODE_ITEM;
  885         return 1;
  886     }
  887     item = btrfs_item_ptr(eb, slot, struct btrfs_inode_item);
  888     rec->nlink = btrfs_inode_nlink(eb, item);
  889     rec->isize = btrfs_inode_size(eb, item);
  890     rec->nbytes = btrfs_inode_nbytes(eb, item);
  891     rec->imode = btrfs_inode_mode(eb, item);
  892     if (btrfs_inode_flags(eb, item) & BTRFS_INODE_NODATASUM)
  893         rec->nodatasum = 1;
  894     rec->found_inode_item = 1;
  895     if (rec->nlink == 0)
  896         rec->errors |= I_ERR_NO_ORPHAN_ITEM;
  897     flags = btrfs_inode_flags(eb, item);
  898     if (S_ISLNK(rec->imode) &&
  899         flags & (BTRFS_INODE_IMMUTABLE | BTRFS_INODE_APPEND))
  900         rec->errors |= I_ERR_ODD_INODE_FLAGS;
  901     /*
  902      * We don't have accurate root info to determine the correct
  903      * inode generation uplimit, use super_generation + 1 anyway
  904      */
  905     gen_uplimit = btrfs_super_generation(global_info->super_copy) + 1;
  906     if (btrfs_inode_generation(eb, item) > gen_uplimit)
  907         rec->errors |= I_ERR_INVALID_GEN;
  908     maybe_free_inode_rec(&active_node->inode_cache, rec);
  909     return 0;
  910 }
  911 
  912 static struct inode_backref *get_inode_backref(struct inode_record *rec,
  913                         const char *name,
  914                         int namelen, u64 dir)
  915 {
  916     struct inode_backref *backref;
  917 
  918     list_for_each_entry(backref, &rec->backrefs, list) {
  919         if (rec->ino == BTRFS_MULTIPLE_OBJECTIDS)
  920             break;
  921         if (backref->dir != dir || backref->namelen != namelen)
  922             continue;
  923         if (memcmp(name, backref->name, namelen))
  924             continue;
  925         return backref;
  926     }
  927 
  928     backref = malloc(sizeof(*backref) + namelen + 1);
  929     if (!backref)
  930         return NULL;
  931     memset(backref, 0, sizeof(*backref));
  932     backref->dir = dir;
  933     backref->namelen = namelen;
  934     memcpy(backref->name, name, namelen);
  935     backref->name[namelen] = '\0';
  936     list_add_tail(&backref->list, &rec->backrefs);
  937     return backref;
  938 }
  939 
  940 static int add_inode_backref(struct cache_tree *inode_cache,
  941                  u64 ino, u64 dir, u64 index,
  942                  const char *name, int namelen,
  943                  u8 filetype, u8 itemtype, int errors)
  944 {
  945     struct inode_record *rec;
  946     struct inode_backref *backref;
  947 
  948     rec = get_inode_rec(inode_cache, ino, 1);
  949     BUG_ON(IS_ERR(rec));
  950     backref = get_inode_backref(rec, name, namelen, dir);
  951     BUG_ON(!backref);
  952     if (errors)
  953         backref->errors |= errors;
  954     if (itemtype == BTRFS_DIR_INDEX_KEY) {
  955         if (backref->found_dir_index)
  956             backref->errors |= REF_ERR_DUP_DIR_INDEX;
  957         if (backref->found_inode_ref && backref->index != index)
  958             backref->errors |= REF_ERR_INDEX_UNMATCH;
  959         if (backref->found_dir_item && backref->filetype != filetype)
  960             backref->errors |= REF_ERR_FILETYPE_UNMATCH;
  961 
  962         backref->index = index;
  963         backref->filetype = filetype;
  964         backref->found_dir_index = 1;
  965     } else if (itemtype == BTRFS_DIR_ITEM_KEY) {
  966         rec->found_link++;
  967         if (backref->found_dir_item)
  968             backref->errors |= REF_ERR_DUP_DIR_ITEM;
  969         if (backref->found_dir_index && backref->filetype != filetype)
  970             backref->errors |= REF_ERR_FILETYPE_UNMATCH;
  971 
  972         backref->filetype = filetype;
  973         backref->found_dir_item = 1;
  974     } else if ((itemtype == BTRFS_INODE_REF_KEY) ||
  975            (itemtype == BTRFS_INODE_EXTREF_KEY)) {
  976         if (backref->found_inode_ref)
  977             backref->errors |= REF_ERR_DUP_INODE_REF;
  978         if (backref->found_dir_index && backref->index != index)
  979             backref->errors |= REF_ERR_INDEX_UNMATCH;
  980         else
  981             backref->index = index;
  982 
  983         backref->ref_type = itemtype;
  984         backref->found_inode_ref = 1;
  985     } else {
  986         BUG_ON(1);
  987     }
  988 
  989     maybe_free_inode_rec(inode_cache, rec);
  990     return 0;
  991 }
  992 
  993 static int merge_inode_recs(struct inode_record *src, struct inode_record *dst,
  994                 struct cache_tree *dst_cache)
  995 {
  996     struct inode_backref *backref;
  997     u32 dir_count = 0;
  998     int ret = 0;
  999 
 1000     dst->merging = 1;
 1001     list_for_each_entry(backref, &src->backrefs, list) {
 1002         if (backref->found_dir_index) {
 1003             add_inode_backref(dst_cache, dst->ino, backref->dir,
 1004                     backref->index, backref->name,
 1005                     backref->namelen, backref->filetype,
 1006                     BTRFS_DIR_INDEX_KEY, backref->errors);
 1007         }
 1008         if (backref->found_dir_item) {
 1009             dir_count++;
 1010             add_inode_backref(dst_cache, dst->ino,
 1011                     backref->dir, 0, backref->name,
 1012                     backref->namelen, backref->filetype,
 1013                     BTRFS_DIR_ITEM_KEY, backref->errors);
 1014         }
 1015         if (backref->found_inode_ref) {
 1016             add_inode_backref(dst_cache, dst->ino,
 1017                     backref->dir, backref->index,
 1018                     backref->name, backref->namelen, 0,
 1019                     backref->ref_type, backref->errors);
 1020         }
 1021     }
 1022 
 1023     if (src->found_dir_item)
 1024         dst->found_dir_item = 1;
 1025     if (src->found_file_extent)
 1026         dst->found_file_extent = 1;
 1027     if (src->found_csum_item)
 1028         dst->found_csum_item = 1;
 1029     if (src->some_csum_missing)
 1030         dst->some_csum_missing = 1;
 1031     if (first_extent_gap(&dst->holes) > first_extent_gap(&src->holes)) {
 1032         ret = copy_file_extent_holes(&dst->holes, &src->holes);
 1033         if (ret < 0)
 1034             return ret;
 1035     }
 1036 
 1037     BUG_ON(src->found_link < dir_count);
 1038     dst->found_link += src->found_link - dir_count;
 1039     dst->found_size += src->found_size;
 1040     if (src->extent_start != (u64)-1) {
 1041         if (dst->extent_start == (u64)-1) {
 1042             dst->extent_start = src->extent_start;
 1043             dst->extent_end = src->extent_end;
 1044         } else {
 1045             if (dst->extent_end > src->extent_start)
 1046                 dst->errors |= I_ERR_FILE_EXTENT_OVERLAP;
 1047             else if (dst->extent_end < src->extent_start) {
 1048                 ret = add_file_extent_hole(&dst->holes,
 1049                     dst->extent_end,
 1050                     src->extent_start - dst->extent_end);
 1051             }
 1052             if (dst->extent_end < src->extent_end)
 1053                 dst->extent_end = src->extent_end;
 1054         }
 1055     }
 1056 
 1057     dst->errors |= src->errors;
 1058     if (src->found_inode_item) {
 1059         if (!dst->found_inode_item) {
 1060             dst->nlink = src->nlink;
 1061             dst->isize = src->isize;
 1062             dst->nbytes = src->nbytes;
 1063             dst->imode = src->imode;
 1064             dst->nodatasum = src->nodatasum;
 1065             dst->found_inode_item = 1;
 1066         } else {
 1067             dst->errors |= I_ERR_DUP_INODE_ITEM;
 1068         }
 1069     }
 1070     dst->merging = 0;
 1071 
 1072     return 0;
 1073 }
 1074 
 1075 static int splice_shared_node(struct shared_node *src_node,
 1076                   struct shared_node *dst_node)
 1077 {
 1078     struct cache_extent *cache;
 1079     struct ptr_node *node, *ins;
 1080     struct cache_tree *src, *dst;
 1081     struct inode_record *rec, *conflict;
 1082     u64 current_ino = 0;
 1083     int splice = 0;
 1084     int ret;
 1085 
 1086     if (--src_node->refs == 0)
 1087         splice = 1;
 1088     if (src_node->current)
 1089         current_ino = src_node->current->ino;
 1090 
 1091     src = &src_node->root_cache;
 1092     dst = &dst_node->root_cache;
 1093 again:
 1094     cache = search_cache_extent(src, 0);
 1095     while (cache) {
 1096         node = container_of(cache, struct ptr_node, cache);
 1097         rec = node->data;
 1098         cache = next_cache_extent(cache);
 1099 
 1100         if (splice) {
 1101             remove_cache_extent(src, &node->cache);
 1102             ins = node;
 1103         } else {
 1104             ins = malloc(sizeof(*ins));
 1105             BUG_ON(!ins);
 1106             ins->cache.start = node->cache.start;
 1107             ins->cache.size = node->cache.size;
 1108             ins->data = rec;
 1109             rec->refs++;
 1110         }
 1111         ret = insert_cache_extent(dst, &ins->cache);
 1112         if (ret == -EEXIST) {
 1113             conflict = get_inode_rec(dst, rec->ino, 1);
 1114             BUG_ON(IS_ERR(conflict));
 1115             merge_inode_recs(rec, conflict, dst);
 1116             if (rec->checked) {
 1117                 conflict->checked = 1;
 1118                 if (dst_node->current == conflict)
 1119                     dst_node->current = NULL;
 1120             }
 1121             maybe_free_inode_rec(dst, conflict);
 1122             free_inode_rec(rec);
 1123             free(ins);
 1124         } else {
 1125             BUG_ON(ret);
 1126         }
 1127     }
 1128 
 1129     if (src == &src_node->root_cache) {
 1130         src = &src_node->inode_cache;
 1131         dst = &dst_node->inode_cache;
 1132         goto again;
 1133     }
 1134 
 1135     if (current_ino > 0 && (!dst_node->current ||
 1136         current_ino > dst_node->current->ino)) {
 1137         if (dst_node->current) {
 1138             dst_node->current->checked = 1;
 1139             maybe_free_inode_rec(dst, dst_node->current);
 1140         }
 1141         dst_node->current = get_inode_rec(dst, current_ino, 1);
 1142         BUG_ON(IS_ERR(dst_node->current));
 1143     }
 1144     return 0;
 1145 }
 1146 
 1147 static void free_inode_ptr(struct cache_extent *cache)
 1148 {
 1149     struct ptr_node *node;
 1150     struct inode_record *rec;
 1151 
 1152     node = container_of(cache, struct ptr_node, cache);
 1153     rec = node->data;
 1154     free_inode_rec(rec);
 1155     free(node);
 1156 }
 1157 
 1158 FREE_EXTENT_CACHE_BASED_TREE(inode_recs, free_inode_ptr);
 1159 
 1160 static struct shared_node *find_shared_node(struct cache_tree *shared,
 1161                         u64 bytenr)
 1162 {
 1163     struct cache_extent *cache;
 1164     struct shared_node *node;
 1165 
 1166     cache = lookup_cache_extent(shared, bytenr, 1);
 1167     if (cache) {
 1168         node = container_of(cache, struct shared_node, cache);
 1169         return node;
 1170     }
 1171     return NULL;
 1172 }
 1173 
 1174 static int add_shared_node(struct cache_tree *shared, u64 bytenr, u32 refs)
 1175 {
 1176     int ret;
 1177     struct shared_node *node;
 1178 
 1179     node = calloc(1, sizeof(*node));
 1180     if (!node)
 1181         return -ENOMEM;
 1182     node->cache.start = bytenr;
 1183     node->cache.size = 1;
 1184     cache_tree_init(&node->root_cache);
 1185     cache_tree_init(&node->inode_cache);
 1186     node->refs = refs;
 1187 
 1188     ret = insert_cache_extent(shared, &node->cache);
 1189 
 1190     return ret;
 1191 }
 1192 
 1193 static int enter_shared_node(struct btrfs_root *root, u64 bytenr, u32 refs,
 1194                  struct walk_control *wc, int level)
 1195 {
 1196     struct shared_node *node;
 1197     struct shared_node *dest;
 1198     int ret;
 1199 
 1200     if (level == wc->active_node)
 1201         return 0;
 1202 
 1203     BUG_ON(wc->active_node <= level);
 1204     node = find_shared_node(&wc->shared, bytenr);
 1205     if (!node) {
 1206         ret = add_shared_node(&wc->shared, bytenr, refs);
 1207         BUG_ON(ret);
 1208         node = find_shared_node(&wc->shared, bytenr);
 1209         wc->nodes[level] = node;
 1210         wc->active_node = level;
 1211         return 0;
 1212     }
 1213 
 1214     if (wc->root_level == wc->active_node &&
 1215         btrfs_root_refs(&root->root_item) == 0) {
 1216         if (--node->refs == 0) {
 1217             free_inode_recs_tree(&node->root_cache);
 1218             free_inode_recs_tree(&node->inode_cache);
 1219             remove_cache_extent(&wc->shared, &node->cache);
 1220             free(node);
 1221         }
 1222         return 1;
 1223     }
 1224 
 1225     dest = wc->nodes[wc->active_node];
 1226     splice_shared_node(node, dest);
 1227     if (node->refs == 0) {
 1228         remove_cache_extent(&wc->shared, &node->cache);
 1229         free(node);
 1230     }
 1231     return 1;
 1232 }
 1233 
 1234 static int leave_shared_node(struct btrfs_root *root,
 1235                  struct walk_control *wc, int level)
 1236 {
 1237     struct shared_node *node;
 1238     struct shared_node *dest;
 1239     int i;
 1240 
 1241     if (level == wc->root_level)
 1242         return 0;
 1243 
 1244     for (i = level + 1; i < BTRFS_MAX_LEVEL; i++) {
 1245         if (wc->nodes[i])
 1246             break;
 1247     }
 1248     BUG_ON(i >= BTRFS_MAX_LEVEL);
 1249 
 1250     node = wc->nodes[wc->active_node];
 1251     wc->nodes[wc->active_node] = NULL;
 1252     wc->active_node = i;
 1253 
 1254     dest = wc->nodes[wc->active_node];
 1255     if (wc->active_node < wc->root_level ||
 1256         btrfs_root_refs(&root->root_item) > 0) {
 1257         BUG_ON(node->refs <= 1);
 1258         splice_shared_node(node, dest);
 1259     } else {
 1260         BUG_ON(node->refs < 2);
 1261         node->refs--;
 1262     }
 1263     return 0;
 1264 }
 1265 
 1266 /*
 1267  * Returns:
 1268  * < 0 - on error
 1269  * 1   - if the root with id child_root_id is a child of root parent_root_id
 1270  * 0   - if the root child_root_id isn't a child of the root parent_root_id but
 1271  *       has other root(s) as parent(s)
 1272  * 2   - if the root child_root_id doesn't have any parent roots
 1273  */
 1274 static int is_child_root(struct btrfs_root *root, u64 parent_root_id,
 1275              u64 child_root_id)
 1276 {
 1277     struct btrfs_path path;
 1278     struct btrfs_key key;
 1279     struct extent_buffer *leaf;
 1280     int has_parent = 0;
 1281     int ret;
 1282 
 1283     btrfs_init_path(&path);
 1284 
 1285     key.objectid = parent_root_id;
 1286     key.type = BTRFS_ROOT_REF_KEY;
 1287     key.offset = child_root_id;
 1288     ret = btrfs_search_slot(NULL, root->fs_info->tree_root, &key, &path,
 1289                 0, 0);
 1290     if (ret < 0)
 1291         return ret;
 1292     btrfs_release_path(&path);
 1293     if (!ret)
 1294         return 1;
 1295 
 1296     key.objectid = child_root_id;
 1297     key.type = BTRFS_ROOT_BACKREF_KEY;
 1298     key.offset = 0;
 1299     ret = btrfs_search_slot(NULL, root->fs_info->tree_root, &key, &path,
 1300                 0, 0);
 1301     if (ret < 0)
 1302         goto out;
 1303 
 1304     while (1) {
 1305         leaf = path.nodes[0];
 1306         if (path.slots[0] >= btrfs_header_nritems(leaf)) {
 1307             ret = btrfs_next_leaf(root->fs_info->tree_root, &path);
 1308             if (ret)
 1309                 break;
 1310             leaf = path.nodes[0];
 1311         }
 1312 
 1313         btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
 1314         if (key.objectid != child_root_id ||
 1315             key.type != BTRFS_ROOT_BACKREF_KEY)
 1316             break;
 1317 
 1318         has_parent = 1;
 1319 
 1320         if (key.offset == parent_root_id) {
 1321             btrfs_release_path(&path);
 1322             return 1;
 1323         }
 1324 
 1325         path.slots[0]++;
 1326     }
 1327 out:
 1328     btrfs_release_path(&path);
 1329     if (ret < 0)
 1330         return ret;
 1331     return has_parent ? 0 : 2;
 1332 }
 1333 
 1334 static int add_mismatch_dir_hash(struct inode_record *dir_rec,
 1335                  struct btrfs_key *key, const char *namebuf,
 1336                  int namelen)
 1337 {
 1338     struct mismatch_dir_hash_record *hash_record;
 1339 
 1340     hash_record = malloc(sizeof(*hash_record) + namelen);
 1341     if (!hash_record) {
 1342         error("failed to allocate memory for mismatch dir hash rec");
 1343         return -ENOMEM;
 1344     }
 1345     memcpy(&hash_record->key, key, sizeof(*key));
 1346     memcpy(hash_record + 1, namebuf, namelen);
 1347     hash_record->namelen = namelen;
 1348 
 1349     list_add(&hash_record->list, &dir_rec->mismatch_dir_hash);
 1350     return 0;
 1351 }
 1352 
 1353 static int process_dir_item(struct extent_buffer *eb,
 1354                 int slot, struct btrfs_key *key,
 1355                 struct shared_node *active_node)
 1356 {
 1357     u32 total;
 1358     u32 cur = 0;
 1359     u32 len;
 1360     u32 name_len;
 1361     u32 data_len;
 1362     int error;
 1363     int nritems = 0;
 1364     u8 filetype;
 1365     struct btrfs_dir_item *di;
 1366     struct inode_record *rec;
 1367     struct cache_tree *root_cache;
 1368     struct cache_tree *inode_cache;
 1369     struct btrfs_key location;
 1370     char namebuf[BTRFS_NAME_LEN];
 1371 
 1372     root_cache = &active_node->root_cache;
 1373     inode_cache = &active_node->inode_cache;
 1374     rec = active_node->current;
 1375     rec->found_dir_item = 1;
 1376 
 1377     di = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);
 1378     total = btrfs_item_size_nr(eb, slot);
 1379     while (cur < total) {
 1380         int ret;
 1381 
 1382         nritems++;
 1383         btrfs_dir_item_key_to_cpu(eb, di, &location);
 1384         name_len = btrfs_dir_name_len(eb, di);
 1385         data_len = btrfs_dir_data_len(eb, di);
 1386         filetype = btrfs_dir_type(eb, di);
 1387 
 1388         rec->found_size += name_len;
 1389         if (cur + sizeof(*di) + name_len > total ||
 1390             name_len > BTRFS_NAME_LEN) {
 1391             error = REF_ERR_NAME_TOO_LONG;
 1392 
 1393             if (cur + sizeof(*di) > total)
 1394                 break;
 1395             len = min_t(u32, total - cur - sizeof(*di),
 1396                     BTRFS_NAME_LEN);
 1397         } else {
 1398             len = name_len;
 1399             error = 0;
 1400         }
 1401 
 1402         read_extent_buffer(eb, namebuf, (unsigned long)(di + 1), len);
 1403 
 1404         if (key->type == BTRFS_DIR_ITEM_KEY &&
 1405             key->offset != btrfs_name_hash(namebuf, len)) {
 1406             rec->errors |= I_ERR_MISMATCH_DIR_HASH;
 1407             ret = add_mismatch_dir_hash(rec, key, namebuf, len);
 1408             /* Fatal error, ENOMEM */
 1409             if (ret < 0)
 1410                 return ret;
 1411             goto next;
 1412         }
 1413 
 1414         if (location.type == BTRFS_INODE_ITEM_KEY) {
 1415             add_inode_backref(inode_cache, location.objectid,
 1416                       key->objectid, key->offset, namebuf,
 1417                       len, filetype, key->type, error);
 1418         } else if (location.type == BTRFS_ROOT_ITEM_KEY) {
 1419             add_inode_backref(root_cache, location.objectid,
 1420                       key->objectid, key->offset,
 1421                       namebuf, len, filetype,
 1422                       key->type, error);
 1423         } else {
 1424             fprintf(stderr,
 1425                 "unknown location type %d in DIR_ITEM[%llu %llu]\n",
 1426                 location.type, key->objectid, key->offset);
 1427             add_inode_backref(inode_cache, BTRFS_MULTIPLE_OBJECTIDS,
 1428                       key->objectid, key->offset, namebuf,
 1429                       len, filetype, key->type, error);
 1430         }
 1431 
 1432 next:
 1433         len = sizeof(*di) + name_len + data_len;
 1434         di = (struct btrfs_dir_item *)((char *)di + len);
 1435         cur += len;
 1436     }
 1437     if (key->type == BTRFS_DIR_INDEX_KEY && nritems > 1)
 1438         rec->errors |= I_ERR_DUP_DIR_INDEX;
 1439 
 1440     return 0;
 1441 }
 1442 
 1443 static int process_inode_ref(struct extent_buffer *eb,
 1444                  int slot, struct btrfs_key *key,
 1445                  struct shared_node *active_node)
 1446 {
 1447     u32 total;
 1448     u32 cur = 0;
 1449     u32 len;
 1450     u32 name_len;
 1451     u64 index;
 1452     int error;
 1453     struct cache_tree *inode_cache;
 1454     struct btrfs_inode_ref *ref;
 1455     char namebuf[BTRFS_NAME_LEN];
 1456 
 1457     inode_cache = &active_node->inode_cache;
 1458 
 1459     ref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
 1460     total = btrfs_item_size_nr(eb, slot);
 1461     while (cur < total) {
 1462         name_len = btrfs_inode_ref_name_len(eb, ref);
 1463         index = btrfs_inode_ref_index(eb, ref);
 1464 
 1465         /* inode_ref + namelen should not cross item boundary */
 1466         if (cur + sizeof(*ref) + name_len > total ||
 1467             name_len > BTRFS_NAME_LEN) {
 1468             if (total < cur + sizeof(*ref))
 1469                 break;
 1470 
 1471             /* Still try to read out the remaining part */
 1472             len = min_t(u32, total - cur - sizeof(*ref),
 1473                     BTRFS_NAME_LEN);
 1474             error = REF_ERR_NAME_TOO_LONG;
 1475         } else {
 1476             len = name_len;
 1477             error = 0;
 1478         }
 1479 
 1480         read_extent_buffer(eb, namebuf, (unsigned long)(ref + 1), len);
 1481         add_inode_backref(inode_cache, key->objectid, key->offset,
 1482                   index, namebuf, len, 0, key->type, error);
 1483 
 1484         len = sizeof(*ref) + name_len;
 1485         ref = (struct btrfs_inode_ref *)((char *)ref + len);
 1486         cur += len;
 1487     }
 1488     return 0;
 1489 }
 1490 
 1491 static int process_inode_extref(struct extent_buffer *eb,
 1492                 int slot, struct btrfs_key *key,
 1493                 struct shared_node *active_node)
 1494 {
 1495     u32 total;
 1496     u32 cur = 0;
 1497     u32 len;
 1498     u32 name_len;
 1499     u64 index;
 1500     u64 parent;
 1501     int error;
 1502     struct cache_tree *inode_cache;
 1503     struct btrfs_inode_extref *extref;
 1504     char namebuf[BTRFS_NAME_LEN];
 1505 
 1506     inode_cache = &active_node->inode_cache;
 1507 
 1508     extref = btrfs_item_ptr(eb, slot, struct btrfs_inode_extref);
 1509     total = btrfs_item_size_nr(eb, slot);
 1510     while (cur < total) {
 1511         name_len = btrfs_inode_extref_name_len(eb, extref);
 1512         index = btrfs_inode_extref_index(eb, extref);
 1513         parent = btrfs_inode_extref_parent(eb, extref);
 1514         if (name_len <= BTRFS_NAME_LEN) {
 1515             len = name_len;
 1516             error = 0;
 1517         } else {
 1518             len = BTRFS_NAME_LEN;
 1519             error = REF_ERR_NAME_TOO_LONG;
 1520         }
 1521         read_extent_buffer(eb, namebuf,
 1522                    (unsigned long)(extref + 1), len);
 1523         add_inode_backref(inode_cache, key->objectid, parent,
 1524                   index, namebuf, len, 0, key->type, error);
 1525 
 1526         len = sizeof(*extref) + name_len;
 1527         extref = (struct btrfs_inode_extref *)((char *)extref + len);
 1528         cur += len;
 1529     }
 1530     return 0;
 1531 
 1532 }
 1533 
 1534 static int process_file_extent(struct btrfs_root *root,
 1535                 struct extent_buffer *eb,
 1536                 int slot, struct btrfs_key *key,
 1537                 struct shared_node *active_node)
 1538 {
 1539     struct inode_record *rec;
 1540     struct btrfs_file_extent_item *fi;
 1541     u64 num_bytes = 0;
 1542     u64 disk_bytenr = 0;
 1543     u64 extent_offset = 0;
 1544     u64 mask = root->fs_info->sectorsize - 1;
 1545     u32 max_inline_size = min_t(u32, mask,
 1546                 BTRFS_MAX_INLINE_DATA_SIZE(root->fs_info));
 1547     u8 compression;
 1548     int extent_type;
 1549     int ret;
 1550 
 1551     rec = active_node->current;
 1552     BUG_ON(rec->ino != key->objectid || rec->refs > 1);
 1553     rec->found_file_extent = 1;
 1554 
 1555     if (rec->extent_start == (u64)-1) {
 1556         rec->extent_start = key->offset;
 1557         rec->extent_end = key->offset;
 1558     }
 1559 
 1560     if (rec->extent_end > key->offset)
 1561         rec->errors |= I_ERR_FILE_EXTENT_OVERLAP;
 1562     else if (rec->extent_end < key->offset) {
 1563         ret = add_file_extent_hole(&rec->holes, rec->extent_end,
 1564                        key->offset - rec->extent_end);
 1565         if (ret < 0)
 1566             return ret;
 1567     }
 1568 
 1569     fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
 1570     extent_type = btrfs_file_extent_type(eb, fi);
 1571     compression = btrfs_file_extent_compression(eb, fi);
 1572 
 1573     if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
 1574         struct btrfs_item *item = btrfs_item_nr(slot);
 1575 
 1576         num_bytes = btrfs_file_extent_ram_bytes(eb, fi);
 1577         if (num_bytes == 0)
 1578             rec->errors |= I_ERR_BAD_FILE_EXTENT;
 1579         if (compression) {
 1580             if (btrfs_file_extent_inline_item_len(eb, item) >
 1581                 max_inline_size ||
 1582                 num_bytes > root->fs_info->sectorsize)
 1583                 rec->errors |= I_ERR_FILE_EXTENT_TOO_LARGE;
 1584         } else {
 1585             if (num_bytes > max_inline_size)
 1586                 rec->errors |= I_ERR_FILE_EXTENT_TOO_LARGE;
 1587             if (btrfs_file_extent_inline_item_len(eb, item) !=
 1588                 num_bytes)
 1589                 rec->errors |= I_ERR_INLINE_RAM_BYTES_WRONG;
 1590         }
 1591         rec->found_size += num_bytes;
 1592         num_bytes = (num_bytes + mask) & ~mask;
 1593     } else if (extent_type == BTRFS_FILE_EXTENT_REG ||
 1594            extent_type == BTRFS_FILE_EXTENT_PREALLOC) {
 1595         num_bytes = btrfs_file_extent_num_bytes(eb, fi);
 1596         disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
 1597         extent_offset = btrfs_file_extent_offset(eb, fi);
 1598         if (num_bytes == 0 || (num_bytes & mask))
 1599             rec->errors |= I_ERR_BAD_FILE_EXTENT;
 1600         if (num_bytes + extent_offset >
 1601             btrfs_file_extent_ram_bytes(eb, fi))
 1602             rec->errors |= I_ERR_BAD_FILE_EXTENT;
 1603         if (extent_type == BTRFS_FILE_EXTENT_PREALLOC &&
 1604             (btrfs_file_extent_compression(eb, fi) ||
 1605              btrfs_file_extent_encryption(eb, fi) ||
 1606              btrfs_file_extent_other_encoding(eb, fi)))
 1607             rec->errors |= I_ERR_BAD_FILE_EXTENT;
 1608         if (compression && rec->nodatasum)
 1609             rec->errors |= I_ERR_BAD_FILE_EXTENT;
 1610         if (disk_bytenr > 0)
 1611             rec->found_size += num_bytes;
 1612     } else {
 1613         rec->errors |= I_ERR_BAD_FILE_EXTENT;
 1614     }
 1615     rec->extent_end = key->offset + num_bytes;
 1616 
 1617     /*
 1618      * The data reloc tree will copy full extents into its inode and then
 1619      * copy the corresponding csums.  Because the extent it copied could be
 1620      * a preallocated extent that hasn't been written to yet there may be no
 1621      * csums to copy, ergo we won't have csums for our file extent.  This is
 1622      * ok so just don't bother checking csums if the inode belongs to the
 1623      * data reloc tree.
 1624      */
 1625     if (disk_bytenr > 0 &&
 1626         btrfs_header_owner(eb) != BTRFS_DATA_RELOC_TREE_OBJECTID) {
 1627         u64 found;
 1628 
 1629         if (compression)
 1630             num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
 1631         else
 1632             disk_bytenr += extent_offset;
 1633 
 1634         ret = count_csum_range(root->fs_info, disk_bytenr, num_bytes,
 1635                        &found);
 1636         if (ret < 0)
 1637             return ret;
 1638         if (extent_type == BTRFS_FILE_EXTENT_REG) {
 1639             if (found > 0)
 1640                 rec->found_csum_item = 1;
 1641             if (found < num_bytes)
 1642                 rec->some_csum_missing = 1;
 1643             if (compression && found < num_bytes)
 1644                 rec->errors |= I_ERR_SOME_CSUM_MISSING;
 1645         } else if (extent_type == BTRFS_FILE_EXTENT_PREALLOC) {
 1646             if (found > 0) {
 1647                 ret = check_prealloc_extent_written(root->fs_info,
 1648                                     disk_bytenr,
 1649                                     num_bytes);
 1650                 if (ret < 0)
 1651                     return ret;
 1652                 if (ret == 0)
 1653                     rec->errors |= I_ERR_ODD_CSUM_ITEM;
 1654             }
 1655         }
 1656     }
 1657     return 0;
 1658 }
 1659 
 1660 static int process_one_leaf(struct btrfs_root *root, struct extent_buffer *eb,
 1661                 struct walk_control *wc)
 1662 {
 1663     struct btrfs_key key;
 1664     u32 nritems;
 1665     int i;
 1666     int ret = 0;
 1667     struct cache_tree *inode_cache;
 1668     struct shared_node *active_node;
 1669 
 1670     if (wc->root_level == wc->active_node &&
 1671         btrfs_root_refs(&root->root_item) == 0)
 1672         return 0;
 1673 
 1674     active_node = wc->nodes[wc->active_node];
 1675     inode_cache = &active_node->inode_cache;
 1676     nritems = btrfs_header_nritems(eb);
 1677     for (i = 0; i < nritems; i++) {
 1678         btrfs_item_key_to_cpu(eb, &key, i);
 1679 
 1680         if (key.objectid == BTRFS_FREE_SPACE_OBJECTID)
 1681             continue;
 1682         if (key.type == BTRFS_ORPHAN_ITEM_KEY)
 1683             continue;
 1684 
 1685         if (active_node->current == NULL ||
 1686             active_node->current->ino < key.objectid) {
 1687             if (active_node->current) {
 1688                 active_node->current->checked = 1;
 1689                 maybe_free_inode_rec(inode_cache,
 1690                              active_node->current);
 1691             }
 1692             active_node->current = get_inode_rec(inode_cache,
 1693                                  key.objectid, 1);
 1694             BUG_ON(IS_ERR(active_node->current));
 1695         }
 1696         switch (key.type) {
 1697         case BTRFS_DIR_ITEM_KEY:
 1698         case BTRFS_DIR_INDEX_KEY:
 1699             ret = process_dir_item(eb, i, &key, active_node);
 1700             break;
 1701         case BTRFS_INODE_REF_KEY:
 1702             ret = process_inode_ref(eb, i, &key, active_node);
 1703             break;
 1704         case BTRFS_INODE_EXTREF_KEY:
 1705             ret = process_inode_extref(eb, i, &key, active_node);
 1706             break;
 1707         case BTRFS_INODE_ITEM_KEY:
 1708             ret = process_inode_item(eb, i, &key, active_node);
 1709             break;
 1710         case BTRFS_EXTENT_DATA_KEY:
 1711             ret = process_file_extent(root, eb, i, &key,
 1712                           active_node);
 1713             break;
 1714         default:
 1715             break;
 1716         };
 1717     }
 1718     return ret;
 1719 }
 1720 
 1721 static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
 1722               struct walk_control *wc, int *level,
 1723               struct node_refs *nrefs)
 1724 {
 1725     enum btrfs_tree_block_status status;
 1726     u64 bytenr;
 1727     u64 ptr_gen;
 1728     struct btrfs_fs_info *fs_info = root->fs_info;
 1729     struct extent_buffer *next;
 1730     struct extent_buffer *cur;
 1731     int ret, err = 0;
 1732     u64 refs;
 1733 
 1734     WARN_ON(*level < 0);
 1735     WARN_ON(*level >= BTRFS_MAX_LEVEL);
 1736 
 1737     if (path->nodes[*level]->start == nrefs->bytenr[*level]) {
 1738         refs = nrefs->refs[*level];
 1739         ret = 0;
 1740     } else {
 1741         ret = btrfs_lookup_extent_info(NULL, fs_info,
 1742                            path->nodes[*level]->start,
 1743                            *level, 1, &refs, NULL);
 1744         if (ret < 0) {
 1745             err = ret;
 1746             goto out;
 1747         }
 1748         nrefs->bytenr[*level] = path->nodes[*level]->start;
 1749         nrefs->refs[*level] = refs;
 1750     }
 1751 
 1752     if (refs > 1) {
 1753         ret = enter_shared_node(root, path->nodes[*level]->start,
 1754                     refs, wc, *level);
 1755         if (ret > 0) {
 1756             err = ret;
 1757             goto out;
 1758         }
 1759     }
 1760 
 1761     while (*level >= 0) {
 1762         WARN_ON(*level < 0);
 1763         WARN_ON(*level >= BTRFS_MAX_LEVEL);
 1764         cur = path->nodes[*level];
 1765 
 1766         if (btrfs_header_level(cur) != *level)
 1767             WARN_ON(1);
 1768 
 1769         if (path->slots[*level] >= btrfs_header_nritems(cur))
 1770             break;
 1771         if (*level == 0) {
 1772             ret = process_one_leaf(root, cur, wc);
 1773             if (ret < 0)
 1774                 err = ret;
 1775             break;
 1776         }
 1777         bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
 1778         ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
 1779 
 1780         if (bytenr == nrefs->bytenr[*level - 1]) {
 1781             refs = nrefs->refs[*level - 1];
 1782         } else {
 1783             ret = btrfs_lookup_extent_info(NULL, fs_info, bytenr,
 1784                     *level - 1, 1, &refs, NULL);
 1785             if (ret < 0) {
 1786                 refs = 0;
 1787             } else {
 1788                 nrefs->bytenr[*level - 1] = bytenr;
 1789                 nrefs->refs[*level - 1] = refs;
 1790             }
 1791         }
 1792 
 1793         if (refs > 1) {
 1794             ret = enter_shared_node(root, bytenr, refs,
 1795                         wc, *level - 1);
 1796             if (ret > 0) {
 1797                 path->slots[*level]++;
 1798                 continue;
 1799             }
 1800         }
 1801 
 1802         next = btrfs_find_tree_block(fs_info, bytenr, fs_info->nodesize);
 1803         if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
 1804             free_extent_buffer(next);
 1805             reada_walk_down(root, cur, path->slots[*level]);
 1806             next = read_tree_block(root->fs_info, bytenr, ptr_gen);
 1807             if (!extent_buffer_uptodate(next)) {
 1808                 struct btrfs_key node_key;
 1809 
 1810                 btrfs_node_key_to_cpu(path->nodes[*level],
 1811                               &node_key,
 1812                               path->slots[*level]);
 1813                 btrfs_add_corrupt_extent_record(root->fs_info,
 1814                         &node_key,
 1815                         path->nodes[*level]->start,
 1816                         root->fs_info->nodesize,
 1817                         *level);
 1818                 err = -EIO;
 1819                 goto out;
 1820             }
 1821         }
 1822 
 1823         ret = check_child_node(cur, path->slots[*level], next);
 1824         if (ret) {
 1825             free_extent_buffer(next);
 1826             err = ret;
 1827             goto out;
 1828         }
 1829 
 1830         if (btrfs_is_leaf(next))
 1831             status = btrfs_check_leaf(fs_info, NULL, next);
 1832         else
 1833             status = btrfs_check_node(fs_info, NULL, next);
 1834         if (status != BTRFS_TREE_BLOCK_CLEAN) {
 1835             free_extent_buffer(next);
 1836             err = -EIO;
 1837             goto out;
 1838         }
 1839 
 1840         *level = *level - 1;
 1841         free_extent_buffer(path->nodes[*level]);
 1842         path->nodes[*level] = next;
 1843         path->slots[*level] = 0;
 1844     }
 1845 out:
 1846     path->slots[*level] = btrfs_header_nritems(path->nodes[*level]);
 1847     return err;
 1848 }
 1849 
 1850 static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
 1851             struct walk_control *wc, int *level)
 1852 {
 1853     int i;
 1854     struct extent_buffer *leaf;
 1855 
 1856     for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
 1857         leaf = path->nodes[i];
 1858         if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) {
 1859             path->slots[i]++;
 1860             *level = i;
 1861             return 0;
 1862         }
 1863         free_extent_buffer(path->nodes[*level]);
 1864         path->nodes[*level] = NULL;
 1865         BUG_ON(*level > wc->active_node);
 1866         if (*level == wc->active_node)
 1867             leave_shared_node(root, wc, *level);
 1868         *level = i + 1;
 1869     }
 1870     return 1;
 1871 }
 1872 
 1873 static int check_root_dir(struct inode_record *rec)
 1874 {
 1875     struct inode_backref *backref;
 1876     int ret = -1;
 1877 
 1878     if (!rec->found_inode_item || rec->errors)
 1879         goto out;
 1880     if (rec->nlink != 1 || rec->found_link != 0)
 1881         goto out;
 1882     if (list_empty(&rec->backrefs))
 1883         goto out;
 1884     backref = to_inode_backref(rec->backrefs.next);
 1885     if (!backref->found_inode_ref)
 1886         goto out;
 1887     if (backref->index != 0 || backref->namelen != 2 ||
 1888         memcmp(backref->name, "..", 2))
 1889         goto out;
 1890     if (backref->found_dir_index || backref->found_dir_item)
 1891         goto out;
 1892     ret = 0;
 1893 out:
 1894     return ret;
 1895 }
 1896 
 1897 static int repair_inode_isize(struct btrfs_trans_handle *trans,
 1898                   struct btrfs_root *root, struct btrfs_path *path,
 1899                   struct inode_record *rec)
 1900 {
 1901     struct btrfs_inode_item *ei;
 1902     struct btrfs_key key;
 1903     int ret;
 1904 
 1905     key.objectid = rec->ino;
 1906     key.type = BTRFS_INODE_ITEM_KEY;
 1907     key.offset = (u64)-1;
 1908 
 1909     ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
 1910     if (ret < 0)
 1911         goto out;
 1912     if (ret) {
 1913         if (!path->slots[0]) {
 1914             ret = -ENOENT;
 1915             goto out;
 1916         }
 1917         path->slots[0]--;
 1918         ret = 0;
 1919     }
 1920     btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
 1921     if (key.objectid != rec->ino) {
 1922         ret = -ENOENT;
 1923         goto out;
 1924     }
 1925 
 1926     ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
 1927                 struct btrfs_inode_item);
 1928     btrfs_set_inode_size(path->nodes[0], ei, rec->found_size);
 1929     btrfs_mark_buffer_dirty(path->nodes[0]);
 1930     rec->errors &= ~I_ERR_DIR_ISIZE_WRONG;
 1931     printf("reset isize for dir %llu root %llu\n", rec->ino,
 1932            root->root_key.objectid);
 1933 out:
 1934     btrfs_release_path(path);
 1935     return ret;
 1936 }
 1937 
 1938 static int repair_inode_orphan_item(struct btrfs_trans_handle *trans,
 1939                     struct btrfs_root *root,
 1940                     struct btrfs_path *path,
 1941                     struct inode_record *rec)
 1942 {
 1943     int ret;
 1944 
 1945     ret = btrfs_add_orphan_item(trans, root, path, rec->ino);
 1946     btrfs_release_path(path);
 1947     if (!ret)
 1948         rec->errors &= ~I_ERR_NO_ORPHAN_ITEM;
 1949     return ret;
 1950 }
 1951 
 1952 static int repair_inode_nbytes(struct btrfs_trans_handle *trans,
 1953                    struct btrfs_root *root,
 1954                    struct btrfs_path *path,
 1955                    struct inode_record *rec)
 1956 {
 1957     struct btrfs_inode_item *ei;
 1958     struct btrfs_key key;
 1959     int ret = 0;
 1960 
 1961     key.objectid = rec->ino;
 1962     key.type = BTRFS_INODE_ITEM_KEY;
 1963     key.offset = 0;
 1964 
 1965     ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
 1966     if (ret) {
 1967         if (ret > 0)
 1968             ret = -ENOENT;
 1969         goto out;
 1970     }
 1971 
 1972     /* Since ret == 0, no need to check anything */
 1973     ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
 1974                 struct btrfs_inode_item);
 1975     btrfs_set_inode_nbytes(path->nodes[0], ei, rec->found_size);
 1976     btrfs_mark_buffer_dirty(path->nodes[0]);
 1977     rec->errors &= ~I_ERR_FILE_NBYTES_WRONG;
 1978     printf("reset nbytes for ino %llu root %llu\n",
 1979            rec->ino, root->root_key.objectid);
 1980 out:
 1981     btrfs_release_path(path);
 1982     return ret;
 1983 }
 1984 
 1985 static int add_missing_dir_index(struct btrfs_root *root,
 1986                  struct cache_tree *inode_cache,
 1987                  struct inode_record *rec,
 1988                  struct inode_backref *backref)
 1989 {
 1990     struct btrfs_path path;
 1991     struct btrfs_trans_handle *trans;
 1992     struct btrfs_dir_item *dir_item;
 1993     struct extent_buffer *leaf;
 1994     struct btrfs_key key;
 1995     struct btrfs_disk_key disk_key;
 1996     struct inode_record *dir_rec;
 1997     unsigned long name_ptr;
 1998     u32 data_size = sizeof(*dir_item) + backref->namelen;
 1999     int ret;
 2000 
 2001     trans = btrfs_start_transaction(root, 1);
 2002     if (IS_ERR(trans))
 2003         return PTR_ERR(trans);
 2004 
 2005     fprintf(stderr, "repairing missing dir index item for inode %llu\n",
 2006         (unsigned long long)rec->ino);
 2007 
 2008     btrfs_init_path(&path);
 2009     key.objectid = backref->dir;
 2010     key.type = BTRFS_DIR_INDEX_KEY;
 2011     key.offset = backref->index;
 2012     ret = btrfs_insert_empty_item(trans, root, &path, &key, data_size);
 2013     BUG_ON(ret);
 2014 
 2015     leaf = path.nodes[0];
 2016     dir_item = btrfs_item_ptr(leaf, path.slots[0], struct btrfs_dir_item);
 2017 
 2018     disk_key.objectid = cpu_to_le64(rec->ino);
 2019     disk_key.type = BTRFS_INODE_ITEM_KEY;
 2020     disk_key.offset = 0;
 2021 
 2022     btrfs_set_dir_item_key(leaf, dir_item, &disk_key);
 2023     btrfs_set_dir_type(leaf, dir_item, imode_to_type(rec->imode));
 2024     btrfs_set_dir_data_len(leaf, dir_item, 0);
 2025     btrfs_set_dir_name_len(leaf, dir_item, backref->namelen);
 2026     name_ptr = (unsigned long)(dir_item + 1);
 2027     write_extent_buffer(leaf, backref->name, name_ptr, backref->namelen);
 2028     btrfs_mark_buffer_dirty(leaf);
 2029     btrfs_release_path(&path);
 2030     btrfs_commit_transaction(trans, root);
 2031 
 2032     backref->found_dir_index = 1;
 2033     dir_rec = get_inode_rec(inode_cache, backref->dir, 0);
 2034     BUG_ON(IS_ERR(dir_rec));
 2035     if (!dir_rec)
 2036         return 0;
 2037     dir_rec->found_size += backref->namelen;
 2038     if (dir_rec->found_size == dir_rec->isize &&
 2039         (dir_rec->errors & I_ERR_DIR_ISIZE_WRONG))
 2040         dir_rec->errors &= ~I_ERR_DIR_ISIZE_WRONG;
 2041     if (dir_rec->found_size != dir_rec->isize)
 2042         dir_rec->errors |= I_ERR_DIR_ISIZE_WRONG;
 2043 
 2044     return 0;
 2045 }
 2046 
 2047 static int delete_dir_index(struct btrfs_root *root,
 2048                 struct inode_backref *backref)
 2049 {
 2050     struct btrfs_trans_handle *trans;
 2051     struct btrfs_dir_item *di;
 2052     struct btrfs_path path;
 2053     int ret = 0;
 2054 
 2055     trans = btrfs_start_transaction(root, 1);
 2056     if (IS_ERR(trans))
 2057         return PTR_ERR(trans);
 2058 
 2059     fprintf(stderr, "Deleting bad dir index [%llu,%u,%llu] root %llu\n",
 2060         (unsigned long long)backref->dir,
 2061         BTRFS_DIR_INDEX_KEY, (unsigned long long)backref->index,
 2062         (unsigned long long)root->objectid);
 2063 
 2064     btrfs_init_path(&path);
 2065     di = btrfs_lookup_dir_index(trans, root, &path, backref->dir,
 2066                     backref->name, backref->namelen,
 2067                     backref->index, -1);
 2068     if (IS_ERR(di)) {
 2069         ret = PTR_ERR(di);
 2070         btrfs_release_path(&path);
 2071         btrfs_commit_transaction(trans, root);
 2072         if (ret == -ENOENT)
 2073             return 0;
 2074         return ret;
 2075     }
 2076 
 2077     if (!di)
 2078         ret = btrfs_del_item(trans, root, &path);
 2079     else
 2080         ret = btrfs_delete_one_dir_name(trans, root, &path, di);
 2081     BUG_ON(ret);
 2082     btrfs_release_path(&path);
 2083     btrfs_commit_transaction(trans, root);
 2084     return ret;
 2085 }
 2086 
 2087 static int create_inode_item(struct btrfs_root *root,
 2088                  struct inode_record *rec, int root_dir)
 2089 {
 2090     struct btrfs_trans_handle *trans;
 2091     u64 nlink = 0;
 2092     u32 mode = 0;
 2093     u64 size = 0;
 2094     int ret;
 2095 
 2096     trans = btrfs_start_transaction(root, 1);
 2097     if (IS_ERR(trans)) {
 2098         ret = PTR_ERR(trans);
 2099         return ret;
 2100     }
 2101 
 2102     nlink = root_dir ? 1 : rec->found_link;
 2103     if (rec->found_dir_item) {
 2104         if (rec->found_file_extent)
 2105             fprintf(stderr, "root %llu inode %llu has both a dir "
 2106                 "item and extents, unsure if it is a dir or a "
 2107                 "regular file so setting it as a directory\n",
 2108                 (unsigned long long)root->objectid,
 2109                 (unsigned long long)rec->ino);
 2110         mode = S_IFDIR | 0755;
 2111         size = rec->found_size;
 2112     } else if (!rec->found_dir_item) {
 2113         size = rec->extent_end;
 2114         mode =  S_IFREG | 0755;
 2115     }
 2116 
 2117     ret = insert_inode_item(trans, root, rec->ino, size, rec->nbytes,
 2118                   nlink, mode);
 2119     btrfs_commit_transaction(trans, root);
 2120     return 0;
 2121 }
 2122 
 2123 static int repair_inode_backrefs(struct btrfs_root *root,
 2124                  struct inode_record *rec,
 2125                  struct cache_tree *inode_cache,
 2126                  int delete)
 2127 {
 2128     struct inode_backref *tmp, *backref;
 2129     u64 root_dirid = btrfs_root_dirid(&root->root_item);
 2130     int ret = 0;
 2131     int repaired = 0;
 2132 
 2133     list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
 2134         if (!delete && rec->ino == root_dirid) {
 2135             if (!rec->found_inode_item) {
 2136                 ret = create_inode_item(root, rec, 1);
 2137                 if (ret)
 2138                     break;
 2139                 repaired++;
 2140             }
 2141         }
 2142 
 2143         /* Index 0 for root dir's are special, don't mess with it */
 2144         if (rec->ino == root_dirid && backref->index == 0)
 2145             continue;
 2146 
 2147         if (delete &&
 2148             ((backref->found_dir_index && !backref->found_inode_ref) ||
 2149              (backref->found_dir_index && backref->found_inode_ref &&
 2150               (backref->errors & REF_ERR_INDEX_UNMATCH)))) {
 2151             ret = delete_dir_index(root, backref);
 2152             if (ret)
 2153                 break;
 2154             repaired++;
 2155             list_del(&backref->list);
 2156             free(backref);
 2157             continue;
 2158         }
 2159 
 2160         if (!delete && !backref->found_dir_index &&
 2161             backref->found_dir_item && backref->found_inode_ref) {
 2162             ret = add_missing_dir_index(root, inode_cache, rec,
 2163                             backref);
 2164             if (ret)
 2165                 break;
 2166             repaired++;
 2167             if (backref->found_dir_item &&
 2168                 backref->found_dir_index) {
 2169                 if (!backref->errors &&
 2170                     backref->found_inode_ref) {
 2171                     list_del(&backref->list);
 2172                     free(backref);
 2173                     continue;
 2174                 }
 2175             }
 2176         }
 2177 
 2178         if (!delete && (!backref->found_dir_index &&
 2179                 !backref->found_dir_item &&
 2180                 backref->found_inode_ref)) {
 2181             struct btrfs_trans_handle *trans;
 2182             struct btrfs_key location;
 2183 
 2184             ret = check_dir_conflict(root, backref->name,
 2185                          backref->namelen,
 2186                          backref->dir,
 2187                          backref->index);
 2188             if (ret) {
 2189                 /*
 2190                  * let nlink fixing routine to handle it,
 2191                  * which can do it better.
 2192                  */
 2193                 ret = 0;
 2194                 break;
 2195             }
 2196             location.objectid = rec->ino;
 2197             location.type = BTRFS_INODE_ITEM_KEY;
 2198             location.offset = 0;
 2199 
 2200             trans = btrfs_start_transaction(root, 1);
 2201             if (IS_ERR(trans)) {
 2202                 ret = PTR_ERR(trans);
 2203                 break;
 2204             }
 2205             fprintf(stderr, "adding missing dir index/item pair "
 2206                 "for inode %llu\n",
 2207                 (unsigned long long)rec->ino);
 2208             ret = btrfs_insert_dir_item(trans, root, backref->name,
 2209                             backref->namelen,
 2210                             backref->dir, &location,
 2211                             imode_to_type(rec->imode),
 2212                             backref->index);
 2213             BUG_ON(ret);
 2214             btrfs_commit_transaction(trans, root);
 2215             repaired++;
 2216         }
 2217 
 2218         if (!delete && (backref->found_inode_ref &&
 2219                 backref->found_dir_index &&
 2220                 backref->found_dir_item &&
 2221                 !(backref->errors & REF_ERR_INDEX_UNMATCH) &&
 2222                 !rec->found_inode_item)) {
 2223             ret = create_inode_item(root, rec, 0);
 2224             if (ret)
 2225                 break;
 2226             repaired++;
 2227         }
 2228 
 2229     }
 2230     return ret ? ret : repaired;
 2231 }
 2232 
 2233 /*
 2234  * To determine the file type for nlink/inode_item repair
 2235  *
 2236  * Return 0 if file type is found and BTRFS_FT_* is stored into type.
 2237  * Return -ENOENT if file type is not found.
 2238  */
 2239 static int find_file_type(struct inode_record *rec, u8 *type)
 2240 {
 2241     struct inode_backref *backref;
 2242 
 2243     /* For inode item recovered case */
 2244     if (rec->found_inode_item) {
 2245         *type = imode_to_type(rec->imode);
 2246         return 0;
 2247     }
 2248 
 2249     list_for_each_entry(backref, &rec->backrefs, list) {
 2250         if (backref->found_dir_index || backref->found_dir_item) {
 2251             *type = backref->filetype;
 2252             return 0;
 2253         }
 2254     }
 2255     return -ENOENT;
 2256 }
 2257 
 2258 /*
 2259  * To determine the file name for nlink repair
 2260  *
 2261  * Return 0 if file name is found, set name and namelen.
 2262  * Return -ENOENT if file name is not found.
 2263  */
 2264 static int find_file_name(struct inode_record *rec,
 2265               char *name, int *namelen)
 2266 {
 2267     struct inode_backref *backref;
 2268 
 2269     list_for_each_entry(backref, &rec->backrefs, list) {
 2270         if (backref->found_dir_index || backref->found_dir_item ||
 2271             backref->found_inode_ref) {
 2272             memcpy(name, backref->name, backref->namelen);
 2273             *namelen = backref->namelen;
 2274             return 0;
 2275         }
 2276     }
 2277     return -ENOENT;
 2278 }
 2279 
 2280 /* Reset the nlink of the inode to the correct one */
 2281 static int reset_nlink(struct btrfs_trans_handle *trans,
 2282                struct btrfs_root *root,
 2283                struct btrfs_path *path,
 2284                struct inode_record *rec)
 2285 {
 2286     struct inode_backref *backref;
 2287     struct inode_backref *tmp;
 2288     struct btrfs_key key;
 2289     struct btrfs_inode_item *inode_item;
 2290     int ret = 0;
 2291 
 2292     /* We don't believe this either, reset it and iterate backref */
 2293     rec->found_link = 0;
 2294 
 2295     /* Remove all backref including the valid ones */
 2296     list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
 2297         ret = btrfs_unlink(trans, root, rec->ino, backref->dir,
 2298                    backref->index, backref->name,
 2299                    backref->namelen, 0);
 2300         if (ret < 0)
 2301             goto out;
 2302 
 2303         /* remove invalid backref, so it won't be added back */
 2304         if (!(backref->found_dir_index &&
 2305               backref->found_dir_item &&
 2306               backref->found_inode_ref)) {
 2307             list_del(&backref->list);
 2308             free(backref);
 2309         } else {
 2310             rec->found_link++;
 2311         }
 2312     }
 2313 
 2314     /* Set nlink to 0 */
 2315     key.objectid = rec->ino;
 2316     key.type = BTRFS_INODE_ITEM_KEY;
 2317     key.offset = 0;
 2318     ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
 2319     if (ret < 0)
 2320         goto out;
 2321     if (ret > 0) {
 2322         ret = -ENOENT;
 2323         goto out;
 2324     }
 2325     inode_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
 2326                     struct btrfs_inode_item);
 2327     btrfs_set_inode_nlink(path->nodes[0], inode_item, 0);
 2328     btrfs_mark_buffer_dirty(path->nodes[0]);
 2329     btrfs_release_path(path);
 2330 
 2331     /*
 2332      * Add back valid inode_ref/dir_item/dir_index,
 2333      * add_link() will handle the nlink inc, so new nlink must be correct
 2334      */
 2335     list_for_each_entry(backref, &rec->backrefs, list) {
 2336         ret = btrfs_add_link(trans, root, rec->ino, backref->dir,
 2337                      backref->name, backref->namelen,
 2338                      backref->filetype, &backref->index, 1, 0);
 2339         if (ret < 0)
 2340             goto out;
 2341     }
 2342 out:
 2343     btrfs_release_path(path);
 2344     return ret;
 2345 }
 2346 
 2347 static int repair_inode_nlinks(struct btrfs_trans_handle *trans,
 2348                    struct btrfs_root *root,
 2349                    struct btrfs_path *path,
 2350                    struct inode_record *rec)
 2351 {
 2352     char namebuf[BTRFS_NAME_LEN] = {0};
 2353     u8 type = 0;
 2354     int namelen = 0;
 2355     int name_recovered = 0;
 2356     int type_recovered = 0;
 2357     int ret = 0;
 2358 
 2359     /*
 2360      * Get file name and type first before these invalid inode ref
 2361      * are deleted by remove_all_invalid_backref()
 2362      */
 2363     name_recovered = !find_file_name(rec, namebuf, &namelen);
 2364     type_recovered = !find_file_type(rec, &type);
 2365 
 2366     if (!name_recovered) {
 2367         printf("Can't get file name for inode %llu, using '%llu' as fallback\n",
 2368                rec->ino, rec->ino);
 2369         namelen = count_digits(rec->ino);
 2370         sprintf(namebuf, "%llu", rec->ino);
 2371         name_recovered = 1;
 2372     }
 2373     if (!type_recovered) {
 2374         printf("Can't get file type for inode %llu, using FILE as fallback\n",
 2375                rec->ino);
 2376         type = BTRFS_FT_REG_FILE;
 2377         type_recovered = 1;
 2378     }
 2379 
 2380     ret = reset_nlink(trans, root, path, rec);
 2381     if (ret < 0) {
 2382         errno = -ret;
 2383         fprintf(stderr,
 2384             "Failed to reset nlink for inode %llu: %m\n", rec->ino);
 2385         goto out;
 2386     }
 2387 
 2388     if (rec->found_link == 0) {
 2389         ret = link_inode_to_lostfound(trans, root, path, rec->ino,
 2390                           namebuf, namelen, type,
 2391                           (u64 *)&rec->found_link);
 2392         if (ret)
 2393             goto out;
 2394     }
 2395     printf("Fixed the nlink of inode %llu\n", rec->ino);
 2396 out:
 2397     /*
 2398      * Clear the flag anyway, or we will loop forever for the same inode
 2399      * as it will not be removed from the bad inode list and the dead loop
 2400      * happens.
 2401      */
 2402     rec->errors &= ~I_ERR_LINK_COUNT_WRONG;
 2403     btrfs_release_path(path);
 2404     return ret;
 2405 }
 2406 
 2407 /*
 2408  * Check if there is any normal(reg or prealloc) file extent for given
 2409  * ino.
 2410  * This is used to determine the file type when neither its dir_index/item or
 2411  * inode_item exists.
 2412  *
 2413  * This will *NOT* report error, if any error happens, just consider it does
 2414  * not have any normal file extent.
 2415  */
 2416 static int find_normal_file_extent(struct btrfs_root *root, u64 ino)
 2417 {
 2418     struct btrfs_path path;
 2419     struct btrfs_key key;
 2420     struct btrfs_key found_key;
 2421     struct btrfs_file_extent_item *fi;
 2422     u8 type;
 2423     int ret = 0;
 2424 
 2425     btrfs_init_path(&path);
 2426     key.objectid = ino;
 2427     key.type = BTRFS_EXTENT_DATA_KEY;
 2428     key.offset = 0;
 2429 
 2430     ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
 2431     if (ret < 0) {
 2432         ret = 0;
 2433         goto out;
 2434     }
 2435     if (ret && path.slots[0] >= btrfs_header_nritems(path.nodes[0])) {
 2436         ret = btrfs_next_leaf(root, &path);
 2437         if (ret) {
 2438             ret = 0;
 2439             goto out;
 2440         }
 2441     }
 2442     while (1) {
 2443         btrfs_item_key_to_cpu(path.nodes[0], &found_key,
 2444                       path.slots[0]);
 2445         if (found_key.objectid != ino ||
 2446             found_key.type != BTRFS_EXTENT_DATA_KEY)
 2447             break;
 2448         fi = btrfs_item_ptr(path.nodes[0], path.slots[0],
 2449                     struct btrfs_file_extent_item);
 2450         type = btrfs_file_extent_type(path.nodes[0], fi);
 2451         if (type != BTRFS_FILE_EXTENT_INLINE) {
 2452             ret = 1;
 2453             goto out;
 2454         }
 2455     }
 2456 out:
 2457     btrfs_release_path(&path);
 2458     return ret;
 2459 }
 2460 
 2461 static int repair_inode_no_item(struct btrfs_trans_handle *trans,
 2462                 struct btrfs_root *root,
 2463                 struct btrfs_path *path,
 2464                 struct inode_record *rec)
 2465 {
 2466     u8 filetype;
 2467     u32 mode = 0700;
 2468     int type_recovered = 0;
 2469     int ret = 0;
 2470 
 2471     printf("Trying to rebuild inode:%llu\n", rec->ino);
 2472 
 2473     type_recovered = !find_file_type(rec, &filetype);
 2474 
 2475     /*
 2476      * Try to determine inode type if type not found.
 2477      *
 2478      * For found regular file extent, it must be FILE.
 2479      * For found dir_item/index, it must be DIR.
 2480      *
 2481      * For undetermined one, use FILE as fallback.
 2482      *
 2483      * TODO:
 2484      * 1. If found backref(inode_index/item is already handled) to it,
 2485      *    it must be DIR.
 2486      *    Need new inode-inode ref structure to allow search for that.
 2487      */
 2488     if (!type_recovered) {
 2489         if (rec->found_file_extent &&
 2490             find_normal_file_extent(root, rec->ino)) {
 2491             type_recovered = 1;
 2492             filetype = BTRFS_FT_REG_FILE;
 2493         } else if (rec->found_dir_item) {
 2494             type_recovered = 1;
 2495             filetype = BTRFS_FT_DIR;
 2496         } else{
 2497             printf("Can't determine the filetype for inode %llu, assume it is a normal file\n",
 2498                    rec->ino);
 2499             type_recovered = 1;
 2500             filetype = BTRFS_FT_REG_FILE;
 2501         }
 2502     }
 2503 
 2504     ret = btrfs_new_inode(trans, root, rec->ino,
 2505                   mode | btrfs_type_to_imode(filetype));
 2506     if (ret < 0)
 2507         goto out;
 2508 
 2509     /*
 2510      * Here inode rebuild is done, we only rebuild the inode item,
 2511      * don't repair the nlink(like move to lost+found).
 2512      * That is the job of nlink repair.
 2513      *
 2514      * We just fill the record and return
 2515      */
 2516     rec->found_dir_item = 1;
 2517     rec->imode = mode | btrfs_type_to_imode(filetype);
 2518     rec->nlink = 0;
 2519     rec->errors &= ~I_ERR_NO_INODE_ITEM;
 2520     /* Ensure the inode_nlinks repair function will be called */
 2521     rec->errors |= I_ERR_LINK_COUNT_WRONG;
 2522 out:
 2523     return ret;
 2524 }
 2525 
 2526 static int repair_inode_discount_extent(struct btrfs_trans_handle *trans,
 2527                     struct btrfs_root *root,
 2528                     struct btrfs_path *path,
 2529                     struct inode_record *rec)
 2530 {
 2531     struct rb_node *node;
 2532     struct file_extent_hole *hole;
 2533     int found = 0;
 2534     int ret = 0;
 2535 
 2536     node = rb_first(&rec->holes);
 2537 
 2538     while (node) {
 2539         found = 1;
 2540         hole = rb_entry(node, struct file_extent_hole, node);
 2541         ret = btrfs_punch_hole(trans, root, rec->ino,
 2542                        hole->start, hole->len);
 2543         if (ret < 0)
 2544             goto out;
 2545         ret = del_file_extent_hole(&rec->holes, hole->start,
 2546                        hole->len);
 2547         if (ret < 0)
 2548             goto out;
 2549         if (RB_EMPTY_ROOT(&rec->holes))
 2550             rec->errors &= ~I_ERR_FILE_EXTENT_DISCOUNT;
 2551         node = rb_first(&rec->holes);
 2552     }
 2553     /* special case for a file losing all its file extent */
 2554     if (!found) {
 2555         ret = btrfs_punch_hole(trans, root, rec->ino, 0,
 2556                        round_up(rec->isize,
 2557                             root->fs_info->sectorsize));
 2558         if (ret < 0)
 2559             goto out;
 2560     }
 2561     printf("Fixed discount file extents for inode: %llu in root: %llu\n",
 2562            rec->ino, root->objectid);
 2563 out:
 2564     return ret;
 2565 }
 2566 
 2567 static int repair_inline_ram_bytes(struct btrfs_trans_handle *trans,
 2568                    struct btrfs_root *root,
 2569                    struct btrfs_path *path,
 2570                    struct inode_record *rec)
 2571 {
 2572     struct btrfs_key key;
 2573     struct btrfs_file_extent_item *fi;
 2574     struct btrfs_item *i;
 2575     u64 on_disk_item_len;
 2576     int ret;
 2577 
 2578     key.objectid = rec->ino;
 2579     key.offset = 0;
 2580     key.type = BTRFS_EXTENT_DATA_KEY;
 2581 
 2582     ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
 2583     if (ret > 0)
 2584         ret = -ENOENT;
 2585     if (ret < 0)
 2586         goto out;
 2587 
 2588     i = btrfs_item_nr(path->slots[0]);
 2589     on_disk_item_len = btrfs_file_extent_inline_item_len(path->nodes[0], i);
 2590     fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
 2591                 struct btrfs_file_extent_item);
 2592     btrfs_set_file_extent_ram_bytes(path->nodes[0], fi, on_disk_item_len);
 2593     btrfs_mark_buffer_dirty(path->nodes[0]);
 2594     printf("Repaired inline ram_bytes for root %llu ino %llu\n",
 2595         root->objectid, rec->ino);
 2596     rec->errors &= ~I_ERR_INLINE_RAM_BYTES_WRONG;
 2597 out:
 2598     btrfs_release_path(path);
 2599     return ret;
 2600 }
 2601 
 2602 static int repair_mismatch_dir_hash(struct btrfs_trans_handle *trans,
 2603                     struct btrfs_root *root,
 2604                     struct inode_record *rec)
 2605 {
 2606     struct mismatch_dir_hash_record *hash;
 2607     int ret = -EUCLEAN;
 2608 
 2609     printf(
 2610     "Deleting bad dir items with invalid hash for root %llu ino %llu\n",
 2611         root->root_key.objectid, rec->ino);
 2612     while (!list_empty(&rec->mismatch_dir_hash)) {
 2613         char *namebuf;
 2614 
 2615         hash = list_entry(rec->mismatch_dir_hash.next,
 2616                 struct mismatch_dir_hash_record, list);
 2617         namebuf = (char *)(hash + 1);
 2618 
 2619         ret = delete_corrupted_dir_item(trans, root, &hash->key,
 2620                         namebuf, hash->namelen);
 2621         if (ret < 0)
 2622             break;
 2623 
 2624         /* Also reduce dir isize */
 2625         rec->found_size -= hash->namelen;
 2626         list_del(&hash->list);
 2627         free(hash);
 2628     }
 2629     if (!ret) {
 2630         rec->errors &= ~I_ERR_MISMATCH_DIR_HASH;
 2631         /* We rely on later dir isize repair to reset dir isize */
 2632         rec->errors |= I_ERR_DIR_ISIZE_WRONG;
 2633     }
 2634     return ret;
 2635 }
 2636 
 2637 static int btrfs_delete_item(struct btrfs_trans_handle *trans,
 2638         struct btrfs_root *root, struct btrfs_key *key)
 2639 {
 2640     struct btrfs_path path;
 2641     int ret = 0;
 2642 
 2643     btrfs_init_path(&path);
 2644 
 2645     ret = btrfs_search_slot(trans, root, key, &path, -1, 1);
 2646     if (ret) {
 2647         if (ret > 0)
 2648             ret = -ENOENT;
 2649 
 2650         btrfs_release_path(&path);
 2651         return ret;
 2652     }
 2653 
 2654     ret = btrfs_del_item(trans, root, &path);
 2655 
 2656     btrfs_release_path(&path);
 2657     return ret;
 2658 }
 2659 
 2660 static int find_file_extent_offset_by_bytenr(struct btrfs_root *root,
 2661         u64 owner, u64 bytenr, u64 *offset_ret)
 2662 {
 2663     int ret = 0;
 2664     struct btrfs_path path;
 2665     struct btrfs_key key;
 2666     struct btrfs_key found_key;
 2667     struct btrfs_file_extent_item *fi;
 2668     struct extent_buffer *leaf;
 2669     u64 disk_bytenr;
 2670     int slot;
 2671 
 2672     btrfs_init_path(&path);
 2673 
 2674     key.objectid = owner;
 2675     key.type = BTRFS_INODE_ITEM_KEY;
 2676     key.offset = 0;
 2677 
 2678     ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
 2679     if (ret) {
 2680         if (ret > 0)
 2681             ret = -ENOENT;
 2682         btrfs_release_path(&path);
 2683         return ret;
 2684     }
 2685 
 2686     btrfs_release_path(&path);
 2687 
 2688     key.objectid = owner;
 2689     key.type = BTRFS_EXTENT_DATA_KEY;
 2690     key.offset = 0;
 2691 
 2692     ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
 2693     if (ret < 0) {
 2694         btrfs_release_path(&path);
 2695         return ret;
 2696     }
 2697 
 2698     while (1) {
 2699         leaf = path.nodes[0];
 2700         slot = path.slots[0];
 2701 
 2702         if (slot >= btrfs_header_nritems(leaf)) {
 2703             ret = btrfs_next_leaf(root, &path);
 2704             if (ret) {
 2705                 if (ret > 0)
 2706                     ret = 0;
 2707                 break;
 2708             }
 2709 
 2710             leaf = path.nodes[0];
 2711             slot = path.slots[0];
 2712         }
 2713 
 2714         btrfs_item_key_to_cpu(leaf, &found_key, slot);
 2715         if ((found_key.objectid != owner) ||
 2716             (found_key.type != BTRFS_EXTENT_DATA_KEY))
 2717             break;
 2718 
 2719         fi = btrfs_item_ptr(leaf, slot,
 2720                 struct btrfs_file_extent_item);
 2721 
 2722         disk_bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
 2723         if (disk_bytenr == bytenr) {
 2724             *offset_ret = found_key.offset;
 2725             ret = 0;
 2726             break;
 2727         }
 2728         path.slots[0]++;
 2729     }
 2730 
 2731     btrfs_release_path(&path);
 2732     return ret;
 2733 }
 2734 
 2735 static int repair_unaligned_extent_recs(struct btrfs_trans_handle *trans,
 2736                 struct btrfs_root *root,
 2737                 struct btrfs_path *path,
 2738                 struct inode_record *rec)
 2739 {
 2740     int ret = 0;
 2741     struct btrfs_key key;
 2742     struct unaligned_extent_rec_t *urec;
 2743     struct unaligned_extent_rec_t *tmp;
 2744 
 2745     list_for_each_entry_safe(urec, tmp, &rec->unaligned_extent_recs, list) {
 2746 
 2747         key.objectid = urec->owner;
 2748         key.type = BTRFS_EXTENT_DATA_KEY;
 2749         key.offset = urec->offset;
 2750         fprintf(stderr, "delete file extent item [%llu,%llu]\n",
 2751                     urec->owner, urec->offset);
 2752         ret = btrfs_delete_item(trans, root, &key);
 2753         if (ret)
 2754             return ret;
 2755 
 2756         list_del(&urec->list);
 2757         free(urec);
 2758     }
 2759     rec->errors &= ~I_ERR_UNALIGNED_EXTENT_REC;
 2760 
 2761     return ret;
 2762 }
 2763 
 2764 static int repair_imode_original(struct btrfs_trans_handle *trans,
 2765                  struct btrfs_root *root,
 2766                  struct btrfs_path *path,
 2767                  struct inode_record *rec)
 2768 {
 2769     struct btrfs_key key;
 2770     int ret;
 2771     u32 imode;
 2772 
 2773     key.objectid = rec->ino;
 2774     key.type = BTRFS_INODE_ITEM_KEY;
 2775     key.offset = 0;
 2776 
 2777     ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
 2778     if (ret > 0)
 2779         ret = -ENOENT;
 2780     if (ret < 0)
 2781         return ret;
 2782 
 2783     if (root->objectid == BTRFS_ROOT_TREE_OBJECTID) {
 2784         /* In root tree we only have two possible imode */
 2785         if (rec->ino == BTRFS_ROOT_TREE_OBJECTID)
 2786             imode = S_IFDIR | 0755;
 2787         else
 2788             imode = S_IFREG | 0600;
 2789     } else {
 2790         ret = detect_imode(root, path, &imode);
 2791         if (ret < 0) {
 2792             btrfs_release_path(path);
 2793             return ret;
 2794         }
 2795     }
 2796     btrfs_release_path(path);
 2797     ret = reset_imode(trans, root, path, rec->ino, imode);
 2798     btrfs_release_path(path);
 2799     if (ret < 0)
 2800         return ret;
 2801     rec->errors &= ~I_ERR_INVALID_IMODE;
 2802     rec->imode = imode;
 2803     return ret;
 2804 }
 2805 
 2806 static int repair_inode_gen_original(struct btrfs_trans_handle *trans,
 2807                      struct btrfs_root *root,
 2808                      struct btrfs_path *path,
 2809                      struct inode_record *rec)
 2810 {
 2811     struct btrfs_inode_item *ii;
 2812     struct btrfs_key key;
 2813     int ret;
 2814 
 2815     key.objectid = rec->ino;
 2816     key.offset = 0;
 2817     key.type = BTRFS_INODE_ITEM_KEY;
 2818 
 2819     ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
 2820     if (ret > 0) {
 2821         ret = -ENOENT;
 2822         error("no inode item found for ino %llu", rec->ino);
 2823         return ret;
 2824     }
 2825     if (ret < 0) {
 2826         errno = -ret;
 2827         error("failed to search inode item for ino %llu: %m", rec->ino);
 2828         return ret;
 2829     }
 2830     ii = btrfs_item_ptr(path->nodes[0], path->slots[0],
 2831                 struct btrfs_inode_item);
 2832     btrfs_set_inode_generation(path->nodes[0], ii, trans->transid);
 2833     btrfs_mark_buffer_dirty(path->nodes[0]);
 2834     btrfs_release_path(path);
 2835     printf("resetting inode generation to %llu for ino %llu\n",
 2836         trans->transid, rec->ino);
 2837     rec->errors &= ~I_ERR_INVALID_GEN;
 2838     return 0;
 2839 }
 2840 
 2841 static int try_repair_inode(struct btrfs_root *root, struct inode_record *rec)
 2842 {
 2843     struct btrfs_trans_handle *trans;
 2844     struct btrfs_path path;
 2845     int ret = 0;
 2846 
 2847     /* unaligned extent recs always lead to csum missing error, clean it */
 2848     if ((rec->errors & I_ERR_SOME_CSUM_MISSING) &&
 2849             (rec->errors & I_ERR_UNALIGNED_EXTENT_REC))
 2850         rec->errors &= ~I_ERR_SOME_CSUM_MISSING;
 2851 
 2852 
 2853     if (!(rec->errors & (I_ERR_DIR_ISIZE_WRONG |
 2854                  I_ERR_NO_ORPHAN_ITEM |
 2855                  I_ERR_LINK_COUNT_WRONG |
 2856                  I_ERR_NO_INODE_ITEM |
 2857                  I_ERR_FILE_EXTENT_DISCOUNT |
 2858                  I_ERR_FILE_NBYTES_WRONG |
 2859                  I_ERR_INLINE_RAM_BYTES_WRONG |
 2860                  I_ERR_MISMATCH_DIR_HASH |
 2861                  I_ERR_UNALIGNED_EXTENT_REC |
 2862                  I_ERR_INVALID_IMODE |
 2863                  I_ERR_INVALID_GEN)))
 2864         return rec->errors;
 2865 
 2866     /*
 2867      * For nlink repair, it may create a dir and add link, so
 2868      * 2 for parent(256)'s dir_index and dir_item
 2869      * 2 for lost+found dir's inode_item and inode_ref
 2870      * 1 for the new inode_ref of the file
 2871      * 2 for lost+found dir's dir_index and dir_item for the file
 2872      */
 2873     trans = btrfs_start_transaction(root, 7);
 2874     if (IS_ERR(trans))
 2875         return PTR_ERR(trans);
 2876 
 2877     btrfs_init_path(&path);
 2878     if (!ret && rec->errors & I_ERR_MISMATCH_DIR_HASH)
 2879         ret = repair_mismatch_dir_hash(trans, root, rec);
 2880     if (!ret && rec->errors & I_ERR_INVALID_IMODE)
 2881         ret = repair_imode_original(trans, root, &path, rec);
 2882     if (rec->errors & I_ERR_NO_INODE_ITEM)
 2883         ret = repair_inode_no_item(trans, root, &path, rec);
 2884     if (!ret && rec->errors & I_ERR_FILE_EXTENT_DISCOUNT)
 2885         ret = repair_inode_discount_extent(trans, root, &path, rec);
 2886     if (!ret && rec->errors & I_ERR_DIR_ISIZE_WRONG)
 2887         ret = repair_inode_isize(trans, root, &path, rec);
 2888     if (!ret && rec->errors & I_ERR_NO_ORPHAN_ITEM)
 2889         ret = repair_inode_orphan_item(trans, root, &path, rec);
 2890     if (!ret && rec->errors & I_ERR_LINK_COUNT_WRONG)
 2891         ret = repair_inode_nlinks(trans, root, &path, rec);
 2892     if (!ret && rec->errors & I_ERR_FILE_NBYTES_WRONG)
 2893         ret = repair_inode_nbytes(trans, root, &path, rec);
 2894     if (!ret && rec->errors & I_ERR_INLINE_RAM_BYTES_WRONG)
 2895         ret = repair_inline_ram_bytes(trans, root, &path, rec);
 2896     if (!ret && rec->errors & I_ERR_UNALIGNED_EXTENT_REC)
 2897         ret = repair_unaligned_extent_recs(trans, root, &path, rec);
 2898     if (!ret && rec->errors & I_ERR_INVALID_GEN)
 2899         ret = repair_inode_gen_original(trans, root, &path, rec);
 2900     btrfs_commit_transaction(trans, root);
 2901     btrfs_release_path(&path);
 2902     return ret;
 2903 }
 2904 
 2905 static int check_inode_recs(struct btrfs_root *root,
 2906                 struct cache_tree *inode_cache)
 2907 {
 2908     struct cache_extent *cache;
 2909     struct ptr_node *node;
 2910     struct inode_record *rec;
 2911     struct inode_backref *backref;
 2912     int stage = 0;
 2913     int ret = 0;
 2914     int err = 0;
 2915     u64 error = 0;
 2916     u64 root_dirid = btrfs_root_dirid(&root->root_item);
 2917 
 2918     if (btrfs_root_refs(&root->root_item) == 0) {
 2919         if (!cache_tree_empty(inode_cache))
 2920             fprintf(stderr, "warning line %d\n", __LINE__);
 2921         return 0;
 2922     }
 2923 
 2924     /*
 2925      * We need to repair backrefs first because we could change some of the
 2926      * errors in the inode recs.
 2927      *
 2928      * We also need to go through and delete invalid backrefs first and then
 2929      * add the correct ones second.  We do this because we may get EEXIST
 2930      * when adding back the correct index because we hadn't yet deleted the
 2931      * invalid index.
 2932      *
 2933      * For example, if we were missing a dir index then the directories
 2934      * isize would be wrong, so if we fixed the isize to what we thought it
 2935      * would be and then fixed the backref we'd still have a invalid fs, so
 2936      * we need to add back the dir index and then check to see if the isize
 2937      * is still wrong.
 2938      */
 2939     while (stage < 3) {
 2940         stage++;
 2941         if (stage == 3 && !err)
 2942             break;
 2943 
 2944         cache = search_cache_extent(inode_cache, 0);
 2945         while (repair && cache) {
 2946             node = container_of(cache, struct ptr_node, cache);
 2947             rec = node->data;
 2948             cache = next_cache_extent(cache);
 2949 
 2950             /* Need to free everything up and rescan */
 2951             if (stage == 3) {
 2952                 remove_cache_extent(inode_cache, &node->cache);
 2953                 free(node);
 2954                 free_inode_rec(rec);
 2955                 continue;
 2956             }
 2957 
 2958             if (list_empty(&rec->backrefs))
 2959                 continue;
 2960 
 2961             ret = repair_inode_backrefs(root, rec, inode_cache,
 2962                             stage == 1);
 2963             if (ret < 0) {
 2964                 err = ret;
 2965                 stage = 2;
 2966                 break;
 2967             } if (ret > 0) {
 2968                 err = -EAGAIN;
 2969             }
 2970         }
 2971     }
 2972     if (err)
 2973         return err;
 2974 
 2975     rec = get_inode_rec(inode_cache, root_dirid, 0);
 2976     BUG_ON(IS_ERR(rec));
 2977     if (rec) {
 2978         if (repair) {
 2979             ret = try_repair_inode(root, rec);
 2980             if (ret < 0)
 2981                 error++;
 2982         }
 2983         ret = check_root_dir(rec);
 2984         if (ret) {
 2985             fprintf(stderr, "root %llu root dir %llu error\n",
 2986                 (unsigned long long)root->root_key.objectid,
 2987                 (unsigned long long)root_dirid);
 2988             print_inode_error(root, rec);
 2989             error++;
 2990         }
 2991     } else {
 2992         if (repair) {
 2993             struct btrfs_trans_handle *trans;
 2994 
 2995             trans = btrfs_start_transaction(root, 1);
 2996             if (IS_ERR(trans)) {
 2997                 err = PTR_ERR(trans);
 2998                 return err;
 2999             }
 3000 
 3001             fprintf(stderr,
 3002                 "root %llu missing its root dir, recreating\n",
 3003                 (unsigned long long)root->objectid);
 3004 
 3005             ret = btrfs_make_root_dir(trans, root, root_dirid);
 3006             if (ret < 0) {
 3007                 btrfs_abort_transaction(trans, ret);
 3008                 return ret;
 3009             }
 3010 
 3011             btrfs_commit_transaction(trans, root);
 3012             return -EAGAIN;
 3013         }
 3014 
 3015         fprintf(stderr, "root %llu root dir %llu not found\n",
 3016             (unsigned long long)root->root_key.objectid,
 3017             (unsigned long long)root_dirid);
 3018     }
 3019 
 3020     while (1) {
 3021         cache = search_cache_extent(inode_cache, 0);
 3022         if (!cache)
 3023             break;
 3024         node = container_of(cache, struct ptr_node, cache);
 3025         rec = node->data;
 3026         remove_cache_extent(inode_cache, &node->cache);
 3027         free(node);
 3028         if (rec->ino == root_dirid ||
 3029             rec->ino == BTRFS_ORPHAN_OBJECTID) {
 3030             free_inode_rec(rec);
 3031             continue;
 3032         }
 3033 
 3034         if (rec->errors & I_ERR_NO_ORPHAN_ITEM) {
 3035             ret = check_orphan_item(root, rec->ino);
 3036             if (ret == 0)
 3037                 rec->errors &= ~I_ERR_NO_ORPHAN_ITEM;
 3038             if (can_free_inode_rec(rec)) {
 3039                 free_inode_rec(rec);
 3040                 continue;
 3041             }
 3042         }
 3043 
 3044         if (!rec->found_inode_item)
 3045             rec->errors |= I_ERR_NO_INODE_ITEM;
 3046         if (rec->found_link != rec->nlink)
 3047             rec->errors |= I_ERR_LINK_COUNT_WRONG;
 3048         if (repair) {
 3049             ret = try_repair_inode(root, rec);
 3050             if (ret == 0 && can_free_inode_rec(rec)) {
 3051                 free_inode_rec(rec);
 3052                 continue;
 3053             }
 3054         }
 3055 
 3056         if (!(repair && ret == 0))
 3057             error++;
 3058         print_inode_error(root, rec);
 3059         list_for_each_entry(backref, &rec->backrefs, list) {
 3060             if (!backref->found_dir_item)
 3061                 backref->errors |= REF_ERR_NO_DIR_ITEM;
 3062             if (!backref->found_dir_index)
 3063                 backref->errors |= REF_ERR_NO_DIR_INDEX;
 3064             if (!backref->found_inode_ref)
 3065                 backref->errors |= REF_ERR_NO_INODE_REF;
 3066             fprintf(stderr, "\tunresolved ref dir %llu index %llu"
 3067                 " namelen %u name %s filetype %d errors %x",
 3068                 (unsigned long long)backref->dir,
 3069                 (unsigned long long)backref->index,
 3070                 backref->namelen, backref->name,
 3071                 backref->filetype, backref->errors);
 3072             print_ref_error(backref->errors);
 3073         }
 3074         free_inode_rec(rec);
 3075     }
 3076     return (error > 0) ? -1 : 0;
 3077 }
 3078 
 3079 static struct root_record *get_root_rec(struct cache_tree *root_cache,
 3080                     u64 objectid)
 3081 {
 3082     struct cache_extent *cache;
 3083     struct root_record *rec = NULL;
 3084     int ret;
 3085 
 3086     cache = lookup_cache_extent(root_cache, objectid, 1);
 3087     if (cache) {
 3088         rec = container_of(cache, struct root_record, cache);
 3089     } else {
 3090         rec = calloc(1, sizeof(*rec));
 3091         if (!rec)
 3092             return ERR_PTR(-ENOMEM);
 3093         rec->objectid = objectid;
 3094         INIT_LIST_HEAD(&rec->backrefs);
 3095         rec->cache.start = objectid;
 3096         rec->cache.size = 1;
 3097 
 3098         ret = insert_cache_extent(root_cache, &rec->cache);
 3099         if (ret)
 3100             return ERR_PTR(-EEXIST);
 3101     }
 3102     return rec;
 3103 }
 3104 
 3105 static struct root_backref *get_root_backref(struct root_record *rec,
 3106                          u64 ref_root, u64 dir, u64 index,
 3107                          const char *name, int namelen)
 3108 {
 3109     struct root_backref *backref;
 3110 
 3111     list_for_each_entry(backref, &rec->backrefs, list) {
 3112         if (backref->ref_root != ref_root || backref->dir != dir ||
 3113             backref->namelen != namelen)
 3114             continue;
 3115         if (memcmp(name, backref->name, namelen))
 3116             continue;
 3117         return backref;
 3118     }
 3119 
 3120     backref = calloc(1, sizeof(*backref) + namelen + 1);
 3121     if (!backref)
 3122         return NULL;
 3123     backref->ref_root = ref_root;
 3124     backref->dir = dir;
 3125     backref->index = index;
 3126     backref->namelen = namelen;
 3127     memcpy(backref->name, name, namelen);
 3128     backref->name[namelen] = '\0';
 3129     list_add_tail(&backref->list, &rec->backrefs);
 3130     return backref;
 3131 }
 3132 
 3133 static void free_root_record(struct cache_extent *cache)
 3134 {
 3135     struct root_record *rec;
 3136     struct root_backref *backref;
 3137 
 3138     rec = container_of(cache, struct root_record, cache);
 3139     while (!list_empty(&rec->backrefs)) {
 3140         backref = to_root_backref(rec->backrefs.next);
 3141         list_del(&backref->list);
 3142         free(backref);
 3143     }
 3144 
 3145     free(rec);
 3146 }
 3147 
 3148 FREE_EXTENT_CACHE_BASED_TREE(root_recs, free_root_record);
 3149 
 3150 static int add_root_backref(struct cache_tree *root_cache,
 3151                 u64 root_id, u64 ref_root, u64 dir, u64 index,
 3152                 const char *name, int namelen,
 3153                 int item_type, int errors)
 3154 {
 3155     struct root_record *rec;
 3156     struct root_backref *backref;
 3157 
 3158     rec = get_root_rec(root_cache, root_id);
 3159     BUG_ON(IS_ERR(rec));
 3160     backref = get_root_backref(rec, ref_root, dir, index, name, namelen);
 3161     BUG_ON(!backref);
 3162 
 3163     backref->errors |= errors;
 3164 
 3165     if (item_type != BTRFS_DIR_ITEM_KEY) {
 3166         if (backref->found_dir_index || backref->found_back_ref ||
 3167             backref->found_forward_ref) {
 3168             if (backref->index != index)
 3169                 backref->errors |= REF_ERR_INDEX_UNMATCH;
 3170         } else {
 3171             backref->index = index;
 3172         }
 3173     }
 3174 
 3175     if (item_type == BTRFS_DIR_ITEM_KEY) {
 3176         if (backref->found_forward_ref)
 3177             rec->found_ref++;
 3178         backref->found_dir_item = 1;
 3179     } else if (item_type == BTRFS_DIR_INDEX_KEY) {
 3180         backref->found_dir_index = 1;
 3181     } else if (item_type == BTRFS_ROOT_REF_KEY) {
 3182         if (backref->found_forward_ref)
 3183             backref->errors |= REF_ERR_DUP_ROOT_REF;
 3184         else if (backref->found_dir_item)
 3185             rec->found_ref++;
 3186         backref->found_forward_ref = 1;
 3187     } else if (item_type == BTRFS_ROOT_BACKREF_KEY) {
 3188         if (backref->found_back_ref)
 3189             backref->errors |= REF_ERR_DUP_ROOT_BACKREF;
 3190         backref->found_back_ref = 1;
 3191     } else {
 3192         BUG_ON(1);
 3193     }
 3194 
 3195     if (backref->found_forward_ref && backref->found_dir_item)
 3196         backref->reachable = 1;
 3197     return 0;
 3198 }
 3199 
 3200 static int merge_root_recs(struct btrfs_root *root,
 3201                struct cache_tree *src_cache,
 3202                struct cache_tree *dst_cache)
 3203 {
 3204     struct cache_extent *cache;
 3205     struct ptr_node *node;
 3206     struct inode_record *rec;
 3207     struct inode_backref *backref;
 3208     int ret = 0;
 3209 
 3210     if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
 3211         free_inode_recs_tree(src_cache);
 3212         return 0;
 3213     }
 3214 
 3215     while (1) {
 3216         cache = search_cache_extent(src_cache, 0);
 3217         if (!cache)
 3218             break;
 3219         node = container_of(cache, struct ptr_node, cache);
 3220         rec = node->data;
 3221         remove_cache_extent(src_cache, &node->cache);
 3222         free(node);
 3223 
 3224         ret = is_child_root(root, root->objectid, rec->ino);
 3225         if (ret < 0)
 3226             break;
 3227         else if (ret == 0)
 3228             goto skip;
 3229 
 3230         list_for_each_entry(backref, &rec->backrefs, list) {
 3231             BUG_ON(backref->found_inode_ref);
 3232             if (backref->found_dir_item)
 3233                 add_root_backref(dst_cache, rec->ino,
 3234                     root->root_key.objectid, backref->dir,
 3235                     backref->index, backref->name,
 3236                     backref->namelen, BTRFS_DIR_ITEM_KEY,
 3237                     backref->errors);
 3238             if (backref->found_dir_index)
 3239                 add_root_backref(dst_cache, rec->ino,
 3240                     root->root_key.objectid, backref->dir,
 3241                     backref->index, backref->name,
 3242                     backref->namelen, BTRFS_DIR_INDEX_KEY,
 3243                     backref->errors);
 3244         }
 3245 skip:
 3246         free_inode_rec(rec);
 3247     }
 3248     if (ret < 0)
 3249         return ret;
 3250     return 0;
 3251 }
 3252 
 3253 static int check_root_refs(struct btrfs_root *root,
 3254                struct cache_tree *root_cache)
 3255 {
 3256     struct root_record *rec;
 3257     struct root_record *ref_root;
 3258     struct root_backref *backref;
 3259     struct cache_extent *cache;
 3260     int loop = 1;
 3261     int ret;
 3262     int error;
 3263     int errors = 0;
 3264 
 3265     rec = get_root_rec(root_cache, BTRFS_FS_TREE_OBJECTID);
 3266     BUG_ON(IS_ERR(rec));
 3267     rec->found_ref = 1;
 3268 
 3269     /* fixme: this can not detect circular references */
 3270     while (loop) {
 3271         loop = 0;
 3272         cache = search_cache_extent(root_cache, 0);
 3273         while (1) {
 3274             ctx.item_count++;
 3275             if (!cache)
 3276                 break;
 3277             rec = container_of(cache, struct root_record, cache);
 3278             cache = next_cache_extent(cache);
 3279 
 3280             if (rec->found_ref == 0)
 3281                 continue;
 3282 
 3283             list_for_each_entry(backref, &rec->backrefs, list) {
 3284                 if (!backref->reachable)
 3285                     continue;
 3286 
 3287                 ref_root = get_root_rec(root_cache,
 3288                             backref->ref_root);
 3289                 BUG_ON(IS_ERR(ref_root));
 3290                 if (ref_root->found_ref > 0)
 3291                     continue;
 3292 
 3293                 backref->reachable = 0;
 3294                 rec->found_ref--;
 3295                 if (rec->found_ref == 0)
 3296                     loop = 1;
 3297             }
 3298         }
 3299     }
 3300 
 3301     cache = search_cache_extent(root_cache, 0);
 3302     while (1) {
 3303         if (!cache)
 3304             break;
 3305         rec = container_of(cache, struct root_record, cache);
 3306         cache = next_cache_extent(cache);
 3307 
 3308         if (rec->found_ref == 0 &&
 3309             rec->objectid >= BTRFS_FIRST_FREE_OBJECTID &&
 3310             rec->objectid <= BTRFS_LAST_FREE_OBJECTID) {
 3311             ret = check_orphan_item(root->fs_info->tree_root,
 3312                         rec->objectid);
 3313             if (ret == 0)
 3314                 continue;
 3315 
 3316             /*
 3317              * If we don't have a root item then we likely just have
 3318              * a dir item in a snapshot for this root but no actual
 3319              * ref key or anything so it's meaningless.
 3320              */
 3321             if (!rec->found_root_item)
 3322                 continue;
 3323             errors++;
 3324             fprintf(stderr, "fs tree %llu not referenced\n",
 3325                 (unsigned long long)rec->objectid);
 3326         }
 3327 
 3328         error = 0;
 3329         if (rec->found_ref > 0 && !rec->found_root_item)
 3330             error = 1;
 3331         list_for_each_entry(backref, &rec->backrefs, list) {
 3332             if (!backref->found_dir_item)
 3333                 backref->errors |= REF_ERR_NO_DIR_ITEM;
 3334             if (!backref->found_dir_index)
 3335                 backref->errors |= REF_ERR_NO_DIR_INDEX;
 3336             if (!backref->found_back_ref)
 3337                 backref->errors |= REF_ERR_NO_ROOT_BACKREF;
 3338             if (!backref->found_forward_ref)
 3339                 backref->errors |= REF_ERR_NO_ROOT_REF;
 3340             if (backref->reachable && backref->errors)
 3341                 error = 1;
 3342         }
 3343         if (!error)
 3344             continue;
 3345 
 3346         errors++;
 3347         fprintf(stderr, "fs tree %llu refs %u %s\n",
 3348             (unsigned long long)rec->objectid, rec->found_ref,
 3349              rec->found_root_item ? "" : "not found");
 3350 
 3351         list_for_each_entry(backref, &rec->backrefs, list) {
 3352             if (!backref->reachable)
 3353                 continue;
 3354             if (!backref->errors && rec->found_root_item)
 3355                 continue;
 3356             fprintf(stderr, "\tunresolved ref root %llu dir %llu"
 3357                 " index %llu namelen %u name %s errors %x\n",
 3358                 (unsigned long long)backref->ref_root,
 3359                 (unsigned long long)backref->dir,
 3360                 (unsigned long long)backref->index,
 3361                 backref->namelen, backref->name,
 3362                 backref->errors);
 3363             print_ref_error(backref->errors);
 3364         }
 3365     }
 3366     return errors > 0 ? 1 : 0;
 3367 }
 3368 
 3369 static int process_root_ref(struct extent_buffer *eb, int slot,
 3370                 struct btrfs_key *key,
 3371                 struct cache_tree *root_cache)
 3372 {
 3373     u64 dirid;
 3374     u64 index;
 3375     u32 len;
 3376     u32 name_len;
 3377     struct btrfs_root_ref *ref;
 3378     char namebuf[BTRFS_NAME_LEN];
 3379     int error;
 3380 
 3381     ref = btrfs_item_ptr(eb, slot, struct btrfs_root_ref);
 3382 
 3383     dirid = btrfs_root_ref_dirid(eb, ref);
 3384     index = btrfs_root_ref_sequence(eb, ref);
 3385     name_len = btrfs_root_ref_name_len(eb, ref);
 3386 
 3387     if (name_len <= BTRFS_NAME_LEN) {
 3388         len = name_len;
 3389         error = 0;
 3390     } else {
 3391         len = BTRFS_NAME_LEN;
 3392         error = REF_ERR_NAME_TOO_LONG;
 3393     }
 3394     read_extent_buffer(eb, namebuf, (unsigned long)(ref + 1), len);
 3395 
 3396     if (key->type == BTRFS_ROOT_REF_KEY) {
 3397         add_root_backref(root_cache, key->offset, key->objectid, dirid,
 3398                  index, namebuf, len, key->type, error);
 3399     } else {
 3400         add_root_backref(root_cache, key->objectid, key->offset, dirid,
 3401                  index, namebuf, len, key->type, error);
 3402     }
 3403     return 0;
 3404 }
 3405 
 3406 static void free_corrupt_block(struct cache_extent *cache)
 3407 {
 3408     struct btrfs_corrupt_block *corrupt;
 3409 
 3410     corrupt = container_of(cache, struct btrfs_corrupt_block, cache);
 3411     free(corrupt);
 3412 }
 3413 
 3414 FREE_EXTENT_CACHE_BASED_TREE(corrupt_blocks, free_corrupt_block);
 3415 
 3416 /*
 3417  * Repair the btree of the given root.
 3418  *
 3419  * The fix is to remove the node key in corrupt_blocks cache_tree.
 3420  * and rebalance the tree.
 3421  * After the fix, the btree should be writeable.
 3422  */
 3423 static int repair_btree(struct btrfs_root *root,
 3424             struct cache_tree *corrupt_blocks)
 3425 {
 3426     struct btrfs_trans_handle *trans;
 3427     struct btrfs_path path;
 3428     struct btrfs_corrupt_block *corrupt;
 3429     struct cache_extent *cache;
 3430     struct btrfs_key key;
 3431     u64 offset;
 3432     int level;
 3433     int ret = 0;
 3434 
 3435     if (cache_tree_empty(corrupt_blocks))
 3436         return 0;
 3437 
 3438     trans = btrfs_start_transaction(root, 1);
 3439     if (IS_ERR(trans)) {
 3440         ret = PTR_ERR(trans);
 3441         errno = -ret;
 3442         fprintf(stderr, "Error starting transaction: %m\n");
 3443         return ret;
 3444     }
 3445     btrfs_init_path(&path);
 3446     cache = first_cache_extent(corrupt_blocks);
 3447     while (cache) {
 3448         corrupt = container_of(cache, struct btrfs_corrupt_block,
 3449                        cache);
 3450         level = corrupt->level;
 3451         path.lowest_level = level;
 3452         key.objectid = corrupt->key.objectid;
 3453         key.type = corrupt->key.type;
 3454         key.offset = corrupt->key.offset;
 3455 
 3456         /*
 3457          * Here we don't want to do any tree balance, since it may
 3458          * cause a balance with corrupted brother leaf/node,
 3459          * so ins_len set to 0 here.
 3460          * Balance will be done after all corrupt node/leaf is deleted.
 3461          */
 3462         ret = btrfs_search_slot(trans, root, &key, &path, 0, 1);
 3463         if (ret < 0)
 3464             goto out;
 3465         offset = btrfs_node_blockptr(path.nodes[level],
 3466                          path.slots[level]);
 3467 
 3468         /* Remove the ptr */
 3469         ret = btrfs_del_ptr(root, &path, level, path.slots[level]);
 3470         if (ret < 0)
 3471             goto out;
 3472         /*
 3473          * Remove the corresponding extent
 3474          * return value is not concerned.
 3475          */
 3476         btrfs_release_path(&path);
 3477         ret = btrfs_free_extent(trans, root, offset,
 3478                 root->fs_info->nodesize, 0,
 3479                 root->root_key.objectid, level - 1, 0);
 3480         cache = next_cache_extent(cache);
 3481     }
 3482 
 3483     /* Balance the btree using btrfs_search_slot() */
 3484     cache = first_cache_extent(corrupt_blocks);
 3485     while (cache) {
 3486         corrupt = container_of(cache, struct btrfs_corrupt_block,
 3487                        cache);
 3488         memcpy(&key, &corrupt->key, sizeof(key));
 3489         ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
 3490         if (ret < 0)
 3491             goto out;
 3492         /* return will always >0 since it won't find the item */
 3493         ret = 0;
 3494         btrfs_release_path(&path);
 3495         cache = next_cache_extent(cache);
 3496     }
 3497 out:
 3498     btrfs_commit_transaction(trans, root);
 3499     btrfs_release_path(&path);
 3500     return ret;
 3501 }
 3502 
 3503 static int check_fs_root(struct btrfs_root *root,
 3504              struct cache_tree *root_cache,
 3505              struct walk_control *wc)
 3506 {
 3507     int ret = 0;
 3508     int err = 0;
 3509     bool generation_err = false;
 3510     int wret;
 3511     int level;
 3512     u64 super_generation;
 3513     struct btrfs_path path;
 3514     struct shared_node root_node;
 3515     struct root_record *rec;
 3516     struct btrfs_root_item *root_item = &root->root_item;
 3517     struct cache_tree corrupt_blocks;
 3518     enum btrfs_tree_block_status status;
 3519     struct node_refs nrefs;
 3520     struct unaligned_extent_rec_t *urec;
 3521     struct unaligned_extent_rec_t *tmp;
 3522 
 3523     super_generation = btrfs_super_generation(root->fs_info->super_copy);
 3524     if (btrfs_root_generation(root_item) > super_generation + 1) {
 3525         error(
 3526     "invalid generation for root %llu, have %llu expect (0, %llu]",
 3527               root->root_key.objectid, btrfs_root_generation(root_item),
 3528               super_generation + 1);
 3529         generation_err = true;
 3530         if (repair) {
 3531             root->node->flags |= EXTENT_BAD_TRANSID;
 3532             ret = recow_extent_buffer(root, root->node);
 3533             if (!ret) {
 3534                 printf("Reset generation for root %llu\n",
 3535                     root->root_key.objectid);
 3536                 generation_err = false;
 3537             }
 3538         }
 3539     }
 3540     /*
 3541      * Reuse the corrupt_block cache tree to record corrupted tree block
 3542      *
 3543      * Unlike the usage in extent tree check, here we do it in a per
 3544      * fs/subvol tree base.
 3545      */
 3546     cache_tree_init(&corrupt_blocks);
 3547     root->fs_info->corrupt_blocks = &corrupt_blocks;
 3548 
 3549     if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
 3550         rec = get_root_rec(root_cache, root->root_key.objectid);
 3551         BUG_ON(IS_ERR(rec));
 3552         if (btrfs_root_refs(root_item) > 0)
 3553             rec->found_root_item = 1;
 3554     }
 3555 
 3556     btrfs_init_path(&path);
 3557     memset(&root_node, 0, sizeof(root_node));
 3558     cache_tree_init(&root_node.root_cache);
 3559     cache_tree_init(&root_node.inode_cache);
 3560     memset(&nrefs, 0, sizeof(nrefs));
 3561 
 3562     /* Mode unaligned extent recs to corresponding inode record */
 3563     list_for_each_entry_safe(urec, tmp,
 3564             &root->unaligned_extent_recs, list) {
 3565         struct inode_record *inode;
 3566 
 3567         inode = get_inode_rec(&root_node.inode_cache, urec->owner, 1);
 3568 
 3569         if (IS_ERR_OR_NULL(inode)) {
 3570             fprintf(stderr,
 3571                 "fail to get inode rec on [%llu,%llu]\n",
 3572                 urec->objectid, urec->owner);
 3573 
 3574             list_del(&urec->list);
 3575             free(urec);
 3576 
 3577             continue;
 3578         }
 3579 
 3580         inode->errors |= I_ERR_UNALIGNED_EXTENT_REC;
 3581         list_move(&urec->list, &inode->unaligned_extent_recs);
 3582     }
 3583 
 3584     level = btrfs_header_level(root->node);
 3585     memset(wc->nodes, 0, sizeof(wc->nodes));
 3586     wc->nodes[level] = &root_node;
 3587     wc->active_node = level;
 3588     wc->root_level = level;
 3589 
 3590     /* We may not have checked the root block, lets do that now */
 3591     if (btrfs_is_leaf(root->node))
 3592         status = btrfs_check_leaf(root->fs_info, NULL, root->node);
 3593     else
 3594         status = btrfs_check_node(root->fs_info, NULL, root->node);
 3595     if (status != BTRFS_TREE_BLOCK_CLEAN)
 3596         return -EIO;
 3597 
 3598     if (btrfs_root_refs(root_item) > 0 ||
 3599         btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
 3600         path.nodes[level] = root->node;
 3601         extent_buffer_get(root->node);
 3602         path.slots[level] = 0;
 3603     } else {
 3604         struct btrfs_key key;
 3605         struct btrfs_disk_key found_key;
 3606 
 3607         btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
 3608         level = root_item->drop_level;
 3609         path.lowest_level = level;
 3610         if (level > btrfs_header_level(root->node) ||
 3611             level >= BTRFS_MAX_LEVEL) {
 3612             error("ignoring invalid drop level: %u", level);
 3613             goto skip_walking;
 3614         }
 3615         wret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
 3616         if (wret < 0)
 3617             goto skip_walking;
 3618         btrfs_node_key(path.nodes[level], &found_key,
 3619                 path.slots[level]);
 3620         WARN_ON(memcmp(&found_key, &root_item->drop_progress,
 3621                     sizeof(found_key)));
 3622     }
 3623 
 3624     while (1) {
 3625         ctx.item_count++;
 3626         wret = walk_down_tree(root, &path, wc, &level, &nrefs);
 3627         if (wret < 0)
 3628             ret = wret;
 3629         if (wret != 0)
 3630             break;
 3631 
 3632         wret = walk_up_tree(root, &path, wc, &level);
 3633         if (wret < 0)
 3634             ret = wret;
 3635         if (wret != 0)
 3636             break;
 3637     }
 3638 skip_walking:
 3639     btrfs_release_path(&path);
 3640 
 3641     if (!cache_tree_empty(&corrupt_blocks)) {
 3642         struct cache_extent *cache;
 3643         struct btrfs_corrupt_block *corrupt;
 3644 
 3645         printf("The following tree block(s) is corrupted in tree %llu:\n",
 3646                root->root_key.objectid);
 3647         cache = first_cache_extent(&corrupt_blocks);
 3648         while (cache) {
 3649             corrupt = container_of(cache,
 3650                            struct btrfs_corrupt_block,
 3651                            cache);
 3652             printf("\ttree block bytenr: %llu, level: %d, node key: (%llu, %u, %llu)\n",
 3653                    cache->start, corrupt->level,
 3654                    corrupt->key.objectid, corrupt->key.type,
 3655                    corrupt->key.offset);
 3656             cache = next_cache_extent(cache);
 3657         }
 3658         if (repair) {
 3659             printf("Try to repair the btree for root %llu\n",
 3660                    root->root_key.objectid);
 3661             ret = repair_btree(root, &corrupt_blocks);
 3662             if (ret < 0) {
 3663                 errno = -ret;
 3664                 fprintf(stderr, "Failed to repair btree: %m\n");
 3665             }
 3666             if (!ret)
 3667                 printf("Btree for root %llu is fixed\n",
 3668                        root->root_key.objectid);
 3669         }
 3670     }
 3671 
 3672     err = merge_root_recs(root, &root_node.root_cache, root_cache);
 3673     if (err < 0)
 3674         ret = err;
 3675 
 3676     if (root_node.current) {
 3677         root_node.current->checked = 1;
 3678         maybe_free_inode_rec(&root_node.inode_cache,
 3679                 root_node.current);
 3680     }
 3681 
 3682     err = check_inode_recs(root, &root_node.inode_cache);
 3683     if (!ret)
 3684         ret = err;
 3685 
 3686     free_corrupt_blocks_tree(&corrupt_blocks);
 3687     root->fs_info->corrupt_blocks = NULL;
 3688     if (!ret && generation_err)
 3689         ret = -1;
 3690     return ret;
 3691 }
 3692 
 3693 static int check_fs_roots(struct btrfs_fs_info *fs_info,
 3694               struct cache_tree *root_cache)
 3695 {
 3696     struct btrfs_path path;
 3697     struct btrfs_key key;
 3698     struct walk_control wc;
 3699     struct extent_buffer *leaf, *tree_node;
 3700     struct btrfs_root *tmp_root;
 3701     struct btrfs_root *tree_root = fs_info->tree_root;
 3702     u64 skip_root = 0;
 3703     int ret;
 3704     int err = 0;
 3705 
 3706     /*
 3707      * Just in case we made any changes to the extent tree that weren't
 3708      * reflected into the free space cache yet.
 3709      */
 3710     if (repair)
 3711         reset_cached_block_groups(fs_info);
 3712     memset(&wc, 0, sizeof(wc));
 3713     cache_tree_init(&wc.shared);
 3714     btrfs_init_path(&path);
 3715 
 3716 again:
 3717     key.offset = 0;
 3718     if (skip_root)
 3719         key.objectid = skip_root + 1;
 3720     else
 3721         key.objectid = 0;
 3722     key.type = BTRFS_ROOT_ITEM_KEY;
 3723     ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0);
 3724     if (ret < 0) {
 3725         err = 1;
 3726         goto out;
 3727     }
 3728     tree_node = tree_root->node;
 3729     while (1) {
 3730 
 3731         if (tree_node != tree_root->node) {
 3732             free_root_recs_tree(root_cache);
 3733             btrfs_release_path(&path);
 3734             goto again;
 3735         }
 3736         leaf = path.nodes[0];
 3737         if (path.slots[0] >= btrfs_header_nritems(leaf)) {
 3738             ret = btrfs_next_leaf(tree_root, &path);
 3739             if (ret) {
 3740                 if (ret < 0)
 3741                     err = 1;
 3742                 break;
 3743             }
 3744             leaf = path.nodes[0];
 3745         }
 3746         btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
 3747         if (key.type == BTRFS_ROOT_ITEM_KEY &&
 3748             fs_root_objectid(key.objectid)) {
 3749             if (key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
 3750                 tmp_root = btrfs_read_fs_root_no_cache(
 3751                         fs_info, &key);
 3752             } else {
 3753                 key.offset = (u64)-1;
 3754                 tmp_root = btrfs_read_fs_root(
 3755                         fs_info, &key);
 3756             }
 3757             if (IS_ERR(tmp_root)) {
 3758                 err = 1;
 3759                 goto next;
 3760             }
 3761             ret = check_fs_root(tmp_root, root_cache, &wc);
 3762             if (ret == -EAGAIN) {
 3763                 free_root_recs_tree(root_cache);
 3764                 btrfs_release_path(&path);
 3765                 goto again;
 3766             }
 3767             if (ret) {
 3768                 err = 1;
 3769 
 3770                 /*
 3771                  * We failed to repair this root but modified
 3772                  * tree root, after again: label we will still
 3773                  * hit this root and fail to repair, so we must
 3774                  * skip it to avoid infinite loop.
 3775                  */
 3776                 if (repair)
 3777                     skip_root = key.objectid;
 3778             }
 3779             if (key.objectid == BTRFS_TREE_RELOC_OBJECTID)
 3780                 btrfs_free_fs_root(tmp_root);
 3781         } else if (key.type == BTRFS_ROOT_REF_KEY ||
 3782                key.type == BTRFS_ROOT_BACKREF_KEY) {
 3783             process_root_ref(leaf, path.slots[0], &key,
 3784                      root_cache);
 3785         } else if (key.type == BTRFS_INODE_ITEM_KEY &&
 3786                is_fstree(key.objectid)) {
 3787             ret = check_repair_free_space_inode(fs_info, &path);
 3788             if (ret < 0 && !path.nodes[0]) {
 3789                 err = 1;
 3790                 goto out;
 3791             }
 3792             if (ret < 0 && path.nodes[0]) {
 3793                 err = 1;
 3794                 goto next;
 3795             }
 3796         }
 3797 next:
 3798         path.slots[0]++;
 3799     }
 3800 out:
 3801     btrfs_release_path(&path);
 3802     if (err)
 3803         free_extent_cache_tree(&wc.shared);
 3804     if (!cache_tree_empty(&wc.shared))
 3805         fprintf(stderr, "warning line %d\n", __LINE__);
 3806 
 3807     return err;
 3808 }
 3809 
 3810 static struct tree_backref *find_tree_backref(struct extent_record *rec,
 3811                         u64 parent, u64 root)
 3812 {
 3813     struct rb_node *node;
 3814     struct tree_backref *back = NULL;
 3815     struct tree_backref match = {
 3816         .node = {
 3817             .is_data = 0,
 3818         },
 3819     };
 3820 
 3821     if (parent) {
 3822         match.parent = parent;
 3823         match.node.full_backref = 1;
 3824     } else {
 3825         match.root = root;
 3826     }
 3827 
 3828     node = rb_search(&rec->backref_tree, &match.node.node,
 3829              (rb_compare_keys)compare_extent_backref, NULL);
 3830     if (node)
 3831         back = to_tree_backref(rb_node_to_extent_backref(node));
 3832 
 3833     return back;
 3834 }
 3835 
 3836 static struct data_backref *find_data_backref(struct extent_record *rec,
 3837                         u64 parent, u64 root,
 3838                         u64 owner, u64 offset,
 3839                         int found_ref,
 3840                         u64 disk_bytenr, u64 bytes)
 3841 {
 3842     struct rb_node *node;
 3843     struct data_backref *back = NULL;
 3844     struct data_backref match = {
 3845         .node = {
 3846             .is_data = 1,
 3847         },
 3848         .owner = owner,
 3849         .offset = offset,
 3850         .bytes = bytes,
 3851         .found_ref = found_ref,
 3852         .disk_bytenr = disk_bytenr,
 3853     };
 3854 
 3855     if (parent) {
 3856         match.parent = parent;
 3857         match.node.full_backref = 1;
 3858     } else {
 3859         match.root = root;
 3860     }
 3861 
 3862     node = rb_search(&rec->backref_tree, &match.node.node,
 3863              (rb_compare_keys)compare_extent_backref, NULL);
 3864     if (node)
 3865         back = to_data_backref(rb_node_to_extent_backref(node));
 3866 
 3867     return back;
 3868 }
 3869 
 3870 static int do_check_fs_roots(struct btrfs_fs_info *fs_info,
 3871               struct cache_tree *root_cache)
 3872 {
 3873     int ret;
 3874 
 3875     if (check_mode == CHECK_MODE_LOWMEM)
 3876         ret = check_fs_roots_lowmem(fs_info);
 3877     else
 3878         ret = check_fs_roots(fs_info, root_cache);
 3879 
 3880     return ret;
 3881 }
 3882 
 3883 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
 3884 {
 3885     struct extent_backref *back, *tmp;
 3886     struct tree_backref *tback;
 3887     struct data_backref *dback;
 3888     u64 found = 0;
 3889     int err = 0;
 3890 
 3891     rbtree_postorder_for_each_entry_safe(back, tmp,
 3892                          &rec->backref_tree, node) {
 3893         if (!back->found_extent_tree) {
 3894             err = 1;
 3895             if (!print_errs)
 3896                 goto out;
 3897             if (back->is_data) {
 3898                 dback = to_data_backref(back);
 3899                 fprintf(stderr,
 3900 "data backref %llu %s %llu owner %llu offset %llu num_refs %lu not found in extent tree\n",
 3901                     (unsigned long long)rec->start,
 3902                     back->full_backref ?
 3903                     "parent" : "root",
 3904                     back->full_backref ?
 3905                     (unsigned long long)dback->parent :
 3906                     (unsigned long long)dback->root,
 3907                     (unsigned long long)dback->owner,
 3908                     (unsigned long long)dback->offset,
 3909                     (unsigned long)dback->num_refs);
 3910             } else {
 3911                 tback = to_tree_backref(back);
 3912                 fprintf(stderr,
 3913 "tree backref %llu parent %llu root %llu not found in extent tree\n",
 3914                     (unsigned long long)rec->start,
 3915                     (unsigned long long)tback->parent,
 3916                     (unsigned long long)tback->root);
 3917             }
 3918         }
 3919         if (!back->is_data && !back->found_ref) {
 3920             err = 1;
 3921             if (!print_errs)
 3922                 goto out;
 3923             tback = to_tree_backref(back);
 3924             fprintf(stderr,
 3925                 "backref %llu %s %llu not referenced back %p\n",
 3926                 (unsigned long long)rec->start,
 3927                 back->full_backref ? "parent" : "root",
 3928                 back->full_backref ?
 3929                 (unsigned long long)tback->parent :
 3930                 (unsigned long long)tback->root, back);
 3931         }
 3932         if (back->is_data) {
 3933             dback = to_data_backref(back);
 3934             if (dback->found_ref != dback->num_refs) {
 3935                 err = 1;
 3936                 if (!print_errs)
 3937                     goto out;
 3938                 fprintf(stderr,
 3939 "incorrect local backref count on %llu %s %llu owner %llu offset %llu found %u wanted %u back %p\n",
 3940                     (unsigned long long)rec->start,
 3941                     back->full_backref ?
 3942                     "parent" : "root",
 3943                     back->full_backref ?
 3944                     (unsigned long long)dback->parent :
 3945                     (unsigned long long)dback->root,
 3946                     (unsigned long long)dback->owner,
 3947                     (unsigned long long)dback->offset,
 3948                     dback->found_ref, dback->num_refs,
 3949                     back);
 3950             }
 3951             if (dback->disk_bytenr != rec->start) {
 3952                 err = 1;
 3953                 if (!print_errs)
 3954                     goto out;
 3955                 fprintf(stderr,
 3956 "backref disk bytenr does not match extent record, bytenr=%llu, ref bytenr=%llu\n",
 3957                     (unsigned long long)rec->start,
 3958                     (unsigned long long)dback->disk_bytenr);
 3959             }
 3960 
 3961             if (dback->bytes != rec->nr) {
 3962                 err = 1;
 3963                 if (!print_errs)
 3964                     goto out;
 3965                 fprintf(stderr,
 3966 "backref bytes do not match extent backref, bytenr=%llu, ref bytes=%llu, backref bytes=%llu\n",
 3967                     (unsigned long long)rec->start,
 3968                     (unsigned long long)rec->nr,
 3969                     (unsigned long long)dback->bytes);
 3970             }
 3971         }
 3972         if (!back->is_data) {
 3973             found += 1;
 3974         } else {
 3975             dback = to_data_backref(back);
 3976             found += dback->found_ref;
 3977         }
 3978     }
 3979     if (found != rec->refs) {
 3980         err = 1;
 3981         if (!print_errs)
 3982             goto out;
 3983         fprintf(stderr,
 3984     "incorrect global backref count on %llu found %llu wanted %llu\n",
 3985             (unsigned long long)rec->start,
 3986             (unsigned long long)found,
 3987             (unsigned long long)rec->refs);
 3988     }
 3989 out:
 3990     return err;
 3991 }
 3992 
 3993 static void __free_one_backref(struct rb_node *node)
 3994 {
 3995     struct extent_backref *back = rb_node_to_extent_backref(node);
 3996 
 3997     free(back);
 3998 }
 3999 
 4000 static void free_all_extent_backrefs(struct extent_record *rec)
 4001 {
 4002     rb_free_nodes(&rec->backref_tree, __free_one_backref);
 4003 }
 4004 
 4005 static void free_extent_record_cache(struct cache_tree *extent_cache)
 4006 {
 4007     struct cache_extent *cache;
 4008     struct extent_record *rec;
 4009 
 4010     while (1) {
 4011         cache = first_cache_extent(extent_cache);
 4012         if (!cache)
 4013             break;
 4014         rec = container_of(cache, struct extent_record, cache);
 4015         remove_cache_extent(extent_cache, cache);
 4016         free_all_extent_backrefs(rec);
 4017         free(rec);
 4018     }
 4019 }
 4020 
 4021 static int maybe_free_extent_rec(struct cache_tree *extent_cache,
 4022                  struct extent_record *rec)
 4023 {
 4024     u64 super_gen = btrfs_super_generation(global_info->super_copy);
 4025 
 4026     if (rec->content_checked && rec->owner_ref_checked &&
 4027         rec->extent_item_refs == rec->refs && rec->refs > 0 &&
 4028         rec->num_duplicates == 0 && !all_backpointers_checked(rec, 0) &&
 4029         !rec->bad_full_backref && !rec->crossing_stripes &&
 4030         rec->generation <= super_gen + 1 &&
 4031         !rec->wrong_chunk_type) {
 4032         remove_cache_extent(extent_cache, &rec->cache);
 4033         free_all_extent_backrefs(rec);
 4034         list_del_init(&rec->list);
 4035         free(rec);
 4036     }
 4037     return 0;
 4038 }
 4039 
 4040 static int check_owner_ref(struct btrfs_root *root,
 4041                 struct extent_record *rec,
 4042                 struct extent_buffer *buf)
 4043 {
 4044     struct extent_backref *node, *tmp;
 4045     struct tree_backref *back;
 4046     struct btrfs_root *ref_root;
 4047     struct btrfs_key key;
 4048     struct btrfs_path path;
 4049     struct extent_buffer *parent;
 4050     int level;
 4051     int found = 0;
 4052     int ret;
 4053 
 4054     rbtree_postorder_for_each_entry_safe(node, tmp,
 4055                          &rec->backref_tree, node) {
 4056         if (node->is_data)
 4057             continue;
 4058         if (!node->found_ref)
 4059             continue;
 4060         if (node->full_backref)
 4061             continue;
 4062         back = to_tree_backref(node);
 4063         if (btrfs_header_owner(buf) == back->root)
 4064             return 0;
 4065     }
 4066     /*
 4067      * Some unexpected root item referring to this one, return 1 to
 4068      * indicate owner not found
 4069      */
 4070     if (rec->is_root)
 4071         return 1;
 4072 
 4073     /* try to find the block by search corresponding fs tree */
 4074     key.objectid = btrfs_header_owner(buf);
 4075     key.type = BTRFS_ROOT_ITEM_KEY;
 4076     key.offset = (u64)-1;
 4077 
 4078     ref_root = btrfs_read_fs_root(root->fs_info, &key);
 4079     if (IS_ERR(ref_root))
 4080         return 1;
 4081 
 4082     level = btrfs_header_level(buf);
 4083     if (level == 0)
 4084         btrfs_item_key_to_cpu(buf, &key, 0);
 4085     else
 4086         btrfs_node_key_to_cpu(buf, &key, 0);
 4087 
 4088     btrfs_init_path(&path);
 4089     path.lowest_level = level + 1;
 4090     ret = btrfs_search_slot(NULL, ref_root, &key, &path, 0, 0);
 4091     if (ret < 0)
 4092         return 0;
 4093 
 4094     parent = path.nodes[level + 1];
 4095     if (parent && buf->start == btrfs_node_blockptr(parent,
 4096                             path.slots[level + 1]))
 4097         found = 1;
 4098 
 4099     btrfs_release_path(&path);
 4100     return found ? 0 : 1;
 4101 }
 4102 
 4103 static int is_extent_tree_record(struct extent_record *rec)
 4104 {
 4105     struct extent_backref *node, *tmp;
 4106     struct tree_backref *back;
 4107     int is_extent = 0;
 4108 
 4109     rbtree_postorder_for_each_entry_safe(node, tmp,
 4110                          &rec->backref_tree, node) {
 4111         if (node->is_data)
 4112             return 0;
 4113         back = to_tree_backref(node);
 4114         if (node->full_backref)
 4115             return 0;
 4116         if (back->root == BTRFS_EXTENT_TREE_OBJECTID)
 4117             is_extent = 1;
 4118     }
 4119     return is_extent;
 4120 }
 4121 
 4122 
 4123 static int record_bad_block_io(struct btrfs_fs_info *info,
 4124                    struct cache_tree *extent_cache,
 4125                    u64 start, u64 len)
 4126 {
 4127     struct extent_record *rec;
 4128     struct cache_extent *cache;
 4129     struct btrfs_key key;
 4130 
 4131     cache = lookup_cache_extent(extent_cache, start, len);
 4132     if (!cache)
 4133         return 0;
 4134 
 4135     rec = container_of(cache, struct extent_record, cache);
 4136     if (!is_extent_tree_record(rec))
 4137         return 0;
 4138 
 4139     btrfs_disk_key_to_cpu(&key, &rec->parent_key);
 4140     return btrfs_add_corrupt_extent_record(info, &key, start, len, 0);
 4141 }
 4142 
 4143 static int swap_values(struct btrfs_root *root, struct btrfs_path *path,
 4144                struct extent_buffer *buf, int slot)
 4145 {
 4146     if (btrfs_header_level(buf)) {
 4147         struct btrfs_key_ptr ptr1, ptr2;
 4148 
 4149         read_extent_buffer(buf, &ptr1, btrfs_node_key_ptr_offset(slot),
 4150                    sizeof(struct btrfs_key_ptr));
 4151         read_extent_buffer(buf, &ptr2,
 4152                    btrfs_node_key_ptr_offset(slot + 1),
 4153                    sizeof(struct btrfs_key_ptr));
 4154         write_extent_buffer(buf, &ptr1,
 4155                     btrfs_node_key_ptr_offset(slot + 1),
 4156                     sizeof(struct btrfs_key_ptr));
 4157         write_extent_buffer(buf, &ptr2,
 4158                     btrfs_node_key_ptr_offset(slot),
 4159                     sizeof(struct btrfs_key_ptr));
 4160         if (slot == 0) {
 4161             struct btrfs_disk_key key;
 4162 
 4163             btrfs_node_key(buf, &key, 0);
 4164             btrfs_fixup_low_keys(root, path, &key,
 4165                          btrfs_header_level(buf) + 1);
 4166         }
 4167     } else {
 4168         struct btrfs_item *item1, *item2;
 4169         struct btrfs_key k1, k2;
 4170         char *item1_data, *item2_data;
 4171         u32 item1_offset, item2_offset, item1_size, item2_size;
 4172 
 4173         item1 = btrfs_item_nr(slot);
 4174         item2 = btrfs_item_nr(slot + 1);
 4175         btrfs_item_key_to_cpu(buf, &k1, slot);
 4176         btrfs_item_key_to_cpu(buf, &k2, slot + 1);
 4177         item1_offset = btrfs_item_offset(buf, item1);
 4178         item2_offset = btrfs_item_offset(buf, item2);
 4179         item1_size = btrfs_item_size(buf, item1);
 4180         item2_size = btrfs_item_size(buf, item2);
 4181 
 4182         item1_data = malloc(item1_size);
 4183         if (!item1_data)
 4184             return -ENOMEM;
 4185         item2_data = malloc(item2_size);
 4186         if (!item2_data) {
 4187             free(item1_data);
 4188             return -ENOMEM;
 4189         }
 4190 
 4191         read_extent_buffer(buf, item1_data, item1_offset, item1_size);
 4192         read_extent_buffer(buf, item2_data, item2_offset, item2_size);
 4193 
 4194         write_extent_buffer(buf, item1_data, item2_offset, item2_size);
 4195         write_extent_buffer(buf, item2_data, item1_offset, item1_size);
 4196         free(item1_data);
 4197         free(item2_data);
 4198 
 4199         btrfs_set_item_offset(buf, item1, item2_offset);
 4200         btrfs_set_item_offset(buf, item2, item1_offset);
 4201         btrfs_set_item_size(buf, item1, item2_size);
 4202         btrfs_set_item_size(buf, item2, item1_size);
 4203 
 4204         path->slots[0] = slot;
 4205         btrfs_set_item_key_unsafe(root, path, &k2);
 4206         path->slots[0] = slot + 1;
 4207         btrfs_set_item_key_unsafe(root, path, &k1);
 4208     }
 4209     return 0;
 4210 }
 4211 
 4212 static int fix_key_order(struct btrfs_root *root, struct btrfs_path *path)
 4213 {
 4214     struct extent_buffer *buf;
 4215     struct btrfs_key k1, k2;
 4216     int i;
 4217     int level = path->lowest_level;
 4218     int ret = -EIO;
 4219 
 4220     buf = path->nodes[level];
 4221     for (i = 0; i < btrfs_header_nritems(buf) - 1; i++) {
 4222         if (level) {
 4223             btrfs_node_key_to_cpu(buf, &k1, i);
 4224             btrfs_node_key_to_cpu(buf, &k2, i + 1);
 4225         } else {
 4226             btrfs_item_key_to_cpu(buf, &k1, i);
 4227             btrfs_item_key_to_cpu(buf, &k2, i + 1);
 4228         }
 4229         if (btrfs_comp_cpu_keys(&k1, &k2) < 0)
 4230             continue;
 4231         ret = swap_values(root, path, buf, i);
 4232         if (ret)
 4233             break;
 4234         btrfs_mark_buffer_dirty(buf);
 4235         i = 0;
 4236     }
 4237     return ret;
 4238 }
 4239 
 4240 static int delete_bogus_item(struct btrfs_root *root,
 4241                  struct btrfs_path *path,
 4242                  struct extent_buffer *buf, int slot)
 4243 {
 4244     struct btrfs_key key;
 4245     int nritems = btrfs_header_nritems(buf);
 4246 
 4247     btrfs_item_key_to_cpu(buf, &key, slot);
 4248 
 4249     /* These are all the keys we can deal with missing. */
 4250     if (key.type != BTRFS_DIR_INDEX_KEY &&
 4251         key.type != BTRFS_EXTENT_ITEM_KEY &&
 4252         key.type != BTRFS_METADATA_ITEM_KEY &&
 4253         key.type != BTRFS_TREE_BLOCK_REF_KEY &&
 4254         key.type != BTRFS_EXTENT_DATA_REF_KEY)
 4255         return -1;
 4256 
 4257     printf("Deleting bogus item [%llu,%u,%llu] at slot %d on block %llu\n",
 4258            (unsigned long long)key.objectid, key.type,
 4259            (unsigned long long)key.offset, slot, buf->start);
 4260     memmove_extent_buffer(buf, btrfs_item_nr_offset(slot),
 4261                   btrfs_item_nr_offset(slot + 1),
 4262                   sizeof(struct btrfs_item) *
 4263                   (nritems - slot - 1));
 4264     btrfs_set_header_nritems(buf, nritems - 1);
 4265     if (slot == 0) {
 4266         struct btrfs_disk_key disk_key;
 4267 
 4268         btrfs_item_key(buf, &disk_key, 0);
 4269         btrfs_fixup_low_keys(root, path, &disk_key, 1);
 4270     }
 4271     btrfs_mark_buffer_dirty(buf);
 4272     return 0;
 4273 }
 4274 
 4275 static int fix_item_offset(struct btrfs_root *root, struct btrfs_path *path)
 4276 {
 4277     struct extent_buffer *buf;
 4278     int i;
 4279     int ret = 0;
 4280 
 4281     /* We should only get this for leaves */
 4282     BUG_ON(path->lowest_level);
 4283     buf = path->nodes[0];
 4284 again:
 4285     for (i = 0; i < btrfs_header_nritems(buf); i++) {
 4286         unsigned int shift = 0, offset;
 4287 
 4288         if (i == 0 && btrfs_item_end_nr(buf, i) !=
 4289             BTRFS_LEAF_DATA_SIZE(root->fs_info)) {
 4290             if (btrfs_item_end_nr(buf, i) >
 4291                 BTRFS_LEAF_DATA_SIZE(root->fs_info)) {
 4292                 ret = delete_bogus_item(root, path, buf, i);
 4293                 if (!ret)
 4294                     goto again;
 4295                 fprintf(stderr,
 4296                 "item is off the end of the leaf, can't fix\n");
 4297                 ret = -EIO;
 4298                 break;
 4299             }
 4300             shift = BTRFS_LEAF_DATA_SIZE(root->fs_info) -
 4301                 btrfs_item_end_nr(buf, i);
 4302         } else if (i > 0 && btrfs_item_end_nr(buf, i) !=
 4303                btrfs_item_offset_nr(buf, i - 1)) {
 4304             if (btrfs_item_end_nr(buf, i) >
 4305                 btrfs_item_offset_nr(buf, i - 1)) {
 4306                 ret = delete_bogus_item(root, path, buf, i);
 4307                 if (!ret)
 4308                     goto again;
 4309                 fprintf(stderr, "items overlap, can't fix\n");
 4310                 ret = -EIO;
 4311                 break;
 4312             }
 4313             shift = btrfs_item_offset_nr(buf, i - 1) -
 4314                 btrfs_item_end_nr(buf, i);
 4315         }
 4316         if (!shift)
 4317             continue;
 4318 
 4319         printf("Shifting item nr %d by %u bytes in block %llu\n",
 4320                i, shift, (unsigned long long)buf->start);
 4321         offset = btrfs_item_offset_nr(buf, i);
 4322         memmove_extent_buffer(buf,
 4323                       btrfs_leaf_data(buf) + offset + shift,
 4324                       btrfs_leaf_data(buf) + offset,
 4325                       btrfs_item_size_nr(buf, i));
 4326         btrfs_set_item_offset(buf, btrfs_item_nr(i),
 4327                       offset + shift);
 4328         btrfs_mark_buffer_dirty(buf);
 4329     }
 4330 
 4331     /*
 4332      * We may have moved things, in which case we want to exit so we don't
 4333      * write those changes out.  Once we have proper abort functionality in
 4334      * progs this can be changed to something nicer.
 4335      */
 4336     BUG_ON(ret);
 4337     return ret;
 4338 }
 4339 
 4340 /*
 4341  * Attempt to fix basic block failures.  If we can't fix it for whatever reason
 4342  * then just return -EIO.
 4343  */
 4344 static int try_to_fix_bad_block(struct btrfs_root *root,
 4345                 struct extent_buffer *buf,
 4346                 enum btrfs_tree_block_status status)
 4347 {
 4348     struct btrfs_trans_handle *trans;
 4349     struct ulist *roots;
 4350     struct ulist_node *node;
 4351     struct btrfs_root *search_root;
 4352     struct btrfs_path path;
 4353     struct ulist_iterator iter;
 4354     struct btrfs_key root_key, key;
 4355     int ret;
 4356 
 4357     if (status != BTRFS_TREE_BLOCK_BAD_KEY_ORDER &&
 4358         status != BTRFS_TREE_BLOCK_INVALID_OFFSETS)
 4359         return -EIO;
 4360 
 4361     ret = btrfs_find_all_roots(NULL, root->fs_info, buf->start, 0, &roots);
 4362     if (ret)
 4363         return -EIO;
 4364 
 4365     btrfs_init_path(&path);
 4366     ULIST_ITER_INIT(&iter);
 4367     /*
 4368      * If we found no roots referencing to this tree block, there is no
 4369      * chance to fix. So our default ret is -EIO.
 4370      */
 4371     ret = -EIO;
 4372     while ((node = ulist_next(roots, &iter))) {
 4373         root_key.objectid = node->val;
 4374         root_key.type = BTRFS_ROOT_ITEM_KEY;
 4375         root_key.offset = (u64)-1;
 4376 
 4377         search_root = btrfs_read_fs_root(root->fs_info, &root_key);
 4378         if (IS_ERR(root)) {
 4379             ret = -EIO;
 4380             break;
 4381         }
 4382 
 4383 
 4384         trans = btrfs_start_transaction(search_root, 0);
 4385         if (IS_ERR(trans)) {
 4386             ret = PTR_ERR(trans);
 4387             break;
 4388         }
 4389 
 4390         path.lowest_level = btrfs_header_level(buf);
 4391         path.skip_check_block = 1;
 4392         if (path.lowest_level)
 4393             btrfs_node_key_to_cpu(buf, &key, 0);
 4394         else
 4395             btrfs_item_key_to_cpu(buf, &key, 0);
 4396         ret = btrfs_search_slot(trans, search_root, &key, &path, 0, 1);
 4397         if (ret) {
 4398             ret = -EIO;
 4399             btrfs_commit_transaction(trans, search_root);
 4400             break;
 4401         }
 4402         if (status == BTRFS_TREE_BLOCK_BAD_KEY_ORDER)
 4403             ret = fix_key_order(search_root, &path);
 4404         else if (status == BTRFS_TREE_BLOCK_INVALID_OFFSETS)
 4405             ret = fix_item_offset(search_root, &path);
 4406         if (ret) {
 4407             btrfs_commit_transaction(trans, search_root);
 4408             break;
 4409         }
 4410         btrfs_release_path(&path);
 4411         btrfs_commit_transaction(trans, search_root);
 4412     }
 4413     ulist_free(roots);
 4414     btrfs_release_path(&path);
 4415     return ret;
 4416 }
 4417 
 4418 static int check_block(struct btrfs_root *root,
 4419                struct cache_tree *extent_cache,
 4420                struct extent_buffer *buf, u64 flags)
 4421 {
 4422     struct extent_record *rec;
 4423     struct cache_extent *cache;
 4424     struct btrfs_key key;
 4425     enum btrfs_tree_block_status status;
 4426     int ret = 0;
 4427     int level;
 4428 
 4429     cache = lookup_cache_extent(extent_cache, buf->start, buf->len);
 4430     if (!cache)
 4431         return 1;
 4432     rec = container_of(cache, struct extent_record, cache);
 4433     rec->generation = btrfs_header_generation(buf);
 4434 
 4435     level = btrfs_header_level(buf);
 4436     if (btrfs_header_nritems(buf) > 0) {
 4437 
 4438         if (level == 0)
 4439             btrfs_item_key_to_cpu(buf, &key, 0);
 4440         else
 4441             btrfs_node_key_to_cpu(buf, &key, 0);
 4442 
 4443         rec->info_objectid = key.objectid;
 4444     }
 4445     rec->info_level = level;
 4446 
 4447     if (btrfs_is_leaf(buf))
 4448         status = btrfs_check_leaf(root->fs_info, &rec->parent_key, buf);
 4449     else
 4450         status = btrfs_check_node(root->fs_info, &rec->parent_key, buf);
 4451 
 4452     if (status != BTRFS_TREE_BLOCK_CLEAN) {
 4453         if (repair)
 4454             status = try_to_fix_bad_block(root, buf, status);
 4455         if (status != BTRFS_TREE_BLOCK_CLEAN) {
 4456             ret = -EIO;
 4457             fprintf(stderr, "bad block %llu\n",
 4458                 (unsigned long long)buf->start);
 4459         } else {
 4460             /*
 4461              * Signal to callers we need to start the scan over
 4462              * again since we'll have cowed blocks.
 4463              */
 4464             ret = -EAGAIN;
 4465         }
 4466     } else {
 4467         rec->content_checked = 1;
 4468         if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)
 4469             rec->owner_ref_checked = 1;
 4470         else {
 4471             ret = check_owner_ref(root, rec, buf);
 4472             if (!ret)
 4473                 rec->owner_ref_checked = 1;
 4474         }
 4475     }
 4476     if (!ret)
 4477         maybe_free_extent_rec(extent_cache, rec);
 4478     return ret;
 4479 }
 4480 
 4481 static struct tree_backref *alloc_tree_backref(struct extent_record *rec,
 4482                         u64 parent, u64 root)
 4483 {
 4484     struct tree_backref *ref = malloc(sizeof(*ref));
 4485 
 4486     if (!ref)
 4487         return NULL;
 4488     memset(&ref->node, 0, sizeof(ref->node));
 4489     if (parent > 0) {
 4490         ref->parent = parent;
 4491         ref->node.full_backref = 1;
 4492     } else {
 4493         ref->root = root;
 4494         ref->node.full_backref = 0;
 4495     }
 4496 
 4497     return ref;
 4498 }
 4499 
 4500 static struct data_backref *alloc_data_backref(struct extent_record *rec,
 4501                         u64 parent, u64 root,
 4502                         u64 owner, u64 offset,
 4503                         u64 max_size)
 4504 {
 4505     struct data_backref *ref = malloc(sizeof(*ref));
 4506 
 4507     if (!ref)
 4508         return NULL;
 4509     memset(&ref->node, 0, sizeof(ref->node));
 4510     ref->node.is_data = 1;
 4511 
 4512     if (parent > 0) {
 4513         ref->parent = parent;
 4514         ref->owner = 0;
 4515         ref->offset = 0;
 4516         ref->node.full_backref = 1;
 4517     } else {
 4518         ref->root = root;
 4519         ref->owner = owner;
 4520         ref->offset = offset;
 4521         ref->node.full_backref = 0;
 4522     }
 4523     ref->bytes = max_size;
 4524     ref->found_ref = 0;
 4525     ref->num_refs = 0;
 4526     if (max_size > rec->max_size)
 4527         rec->max_size = max_size;
 4528     return ref;
 4529 }
 4530 
 4531 /* Check if the type of extent matches with its chunk */
 4532 static void check_extent_type(struct extent_record *rec)
 4533 {
 4534     struct btrfs_block_group_cache *bg_cache;
 4535 
 4536     bg_cache = btrfs_lookup_first_block_group(global_info, rec->start);
 4537     if (!bg_cache)
 4538         return;
 4539 
 4540     /* data extent, check chunk directly*/
 4541     if (!rec->metadata) {
 4542         if (!(bg_cache->flags & BTRFS_BLOCK_GROUP_DATA))
 4543             rec->wrong_chunk_type = 1;
 4544         return;
 4545     }
 4546 
 4547     /* metadata extent, check the obvious case first */
 4548     if (!(bg_cache->flags & (BTRFS_BLOCK_GROUP_SYSTEM |
 4549                  BTRFS_BLOCK_GROUP_METADATA))) {
 4550         rec->wrong_chunk_type = 1;
 4551         return;
 4552     }
 4553 
 4554     /*
 4555      * Check SYSTEM extent, as it's also marked as metadata, we can only
 4556      * make sure it's a SYSTEM extent by its backref
 4557      */
 4558     if (!RB_EMPTY_ROOT(&rec->backref_tree)) {
 4559         struct extent_backref *node;
 4560         struct tree_backref *tback;
 4561         u64 bg_type;
 4562 
 4563         node = rb_node_to_extent_backref(rb_first(&rec->backref_tree));
 4564         if (node->is_data) {
 4565             /* tree block shouldn't have data backref */
 4566             rec->wrong_chunk_type = 1;
 4567             return;
 4568         }
 4569         tback = container_of(node, struct tree_backref, node);
 4570 
 4571         if (tback->root == BTRFS_CHUNK_TREE_OBJECTID)
 4572             bg_type = BTRFS_BLOCK_GROUP_SYSTEM;
 4573         else
 4574             bg_type = BTRFS_BLOCK_GROUP_METADATA;
 4575         if (!(bg_cache->flags & bg_type))
 4576             rec->wrong_chunk_type = 1;
 4577     }
 4578 }
 4579 
 4580 /*
 4581  * Allocate a new extent record, fill default values from @tmpl and insert int
 4582  * @extent_cache. Caller is supposed to make sure the [start,nr) is not in
 4583  * the cache, otherwise it fails.
 4584  */
 4585 static int add_extent_rec_nolookup(struct cache_tree *extent_cache,
 4586         struct extent_record *tmpl)
 4587 {
 4588     struct extent_record *rec;
 4589     int ret = 0;
 4590 
 4591     BUG_ON(tmpl->max_size == 0);
 4592     rec = malloc(sizeof(*rec));
 4593     if (!rec)
 4594         return -ENOMEM;
 4595     rec->start = tmpl->start;
 4596     rec->max_size = tmpl->max_size;
 4597     rec->nr = max(tmpl->nr, tmpl->max_size);
 4598     rec->found_rec = tmpl->found_rec;
 4599     rec->content_checked = tmpl->content_checked;
 4600     rec->owner_ref_checked = tmpl->owner_ref_checked;
 4601     rec->num_duplicates = 0;
 4602     rec->metadata = tmpl->metadata;
 4603     rec->flag_block_full_backref = FLAG_UNSET;
 4604     rec->bad_full_backref = 0;
 4605     rec->crossing_stripes = 0;
 4606     rec->wrong_chunk_type = 0;
 4607     rec->is_root = tmpl->is_root;
 4608     rec->refs = tmpl->refs;
 4609     rec->extent_item_refs = tmpl->extent_item_refs;
 4610     rec->parent_generation = tmpl->parent_generation;
 4611     rec->generation = tmpl->generation;
 4612     INIT_LIST_HEAD(&rec->backrefs);
 4613     INIT_LIST_HEAD(&rec->dups);
 4614     INIT_LIST_HEAD(&rec->list);
 4615     rec->backref_tree = RB_ROOT;
 4616     memcpy(&rec->parent_key, &tmpl->parent_key, sizeof(tmpl->parent_key));
 4617     rec->cache.start = tmpl->start;
 4618     rec->cache.size = tmpl->nr;
 4619     ret = insert_cache_extent(extent_cache, &rec->cache);
 4620     if (ret) {
 4621         free(rec);
 4622         return ret;
 4623     }
 4624     bytes_used += rec->nr;
 4625 
 4626     if (tmpl->metadata)
 4627         rec->crossing_stripes = check_crossing_stripes(global_info,
 4628                 rec->start, global_info->nodesize);
 4629     check_extent_type(rec);
 4630     return ret;
 4631 }
 4632 
 4633 /*
 4634  * Lookup and modify an extent, some values of @tmpl are interpreted verbatim,
 4635  * some are hints:
 4636  * - refs              - if found, increase refs
 4637  * - is_root           - if found, set
 4638  * - content_checked   - if found, set
 4639  * - owner_ref_checked - if found, set
 4640  *
 4641  * If not found, create a new one, initialize and insert.
 4642  */
 4643 static int add_extent_rec(struct cache_tree *extent_cache,
 4644         struct extent_record *tmpl)
 4645 {
 4646     struct extent_record *rec;
 4647     struct cache_extent *cache;
 4648     int ret = 0;
 4649     int dup = 0;
 4650 
 4651     cache = lookup_cache_extent(extent_cache, tmpl->start, tmpl->nr);
 4652     if (cache) {
 4653         rec = container_of(cache, struct extent_record, cache);
 4654         if (tmpl->refs)
 4655             rec->refs++;
 4656         if (rec->nr == 1)
 4657             rec->nr = max(tmpl->nr, tmpl->max_size);
 4658 
 4659         /*
 4660          * We need to make sure to reset nr to whatever the extent
 4661          * record says was the real size, this way we can compare it to
 4662          * the backrefs.
 4663          */
 4664         if (tmpl->found_rec) {
 4665             if (tmpl->start != rec->start || rec->found_rec) {
 4666                 struct extent_record *tmp;
 4667 
 4668                 dup = 1;
 4669                 if (list_empty(&rec->list))
 4670                     list_add_tail(&rec->list,
 4671                               &duplicate_extents);
 4672 
 4673                 /*
 4674                  * We have to do this song and dance in case we
 4675                  * find an extent record that falls inside of
 4676                  * our current extent record but does not have
 4677                  * the same objectid.
 4678                  */
 4679                 tmp = malloc(sizeof(*tmp));
 4680                 if (!tmp)
 4681                     return -ENOMEM;
 4682                 tmp->start = tmpl->start;
 4683                 tmp->max_size = tmpl->max_size;
 4684                 tmp->nr = tmpl->nr;
 4685                 tmp->found_rec = 1;
 4686                 tmp->metadata = tmpl->metadata;
 4687                 tmp->extent_item_refs = tmpl->extent_item_refs;
 4688                 INIT_LIST_HEAD(&tmp->list);
 4689                 list_add_tail(&tmp->list, &rec->dups);
 4690                 rec->num_duplicates++;
 4691             } else {
 4692                 rec->nr = tmpl->nr;
 4693                 rec->found_rec = 1;
 4694             }
 4695         }
 4696 
 4697         if (tmpl->extent_item_refs && !dup) {
 4698             if (rec->extent_item_refs) {
 4699                 fprintf(stderr,
 4700             "block %llu rec extent_item_refs %llu, passed %llu\n",
 4701                     (unsigned long long)tmpl->start,
 4702                     (unsigned long long)
 4703                             rec->extent_item_refs,
 4704                     (unsigned long long)
 4705                             tmpl->extent_item_refs);
 4706             }
 4707             rec->extent_item_refs = tmpl->extent_item_refs;
 4708         }
 4709         if (tmpl->is_root)
 4710             rec->is_root = 1;
 4711         if (tmpl->content_checked)
 4712             rec->content_checked = 1;
 4713         if (tmpl->owner_ref_checked)
 4714             rec->owner_ref_checked = 1;
 4715         memcpy(&rec->parent_key, &tmpl->parent_key,
 4716                 sizeof(tmpl->parent_key));
 4717         if (tmpl->parent_generation)
 4718             rec->parent_generation = tmpl->parent_generation;
 4719         if (rec->max_size < tmpl->max_size)
 4720             rec->max_size = tmpl->max_size;
 4721 
 4722         /*
 4723          * A metadata extent can't cross stripe_len boundary, otherwise
 4724          * kernel scrub won't be able to handle it.
 4725          * As now stripe_len is fixed to BTRFS_STRIPE_LEN, just check
 4726          * it.
 4727          */
 4728         if (tmpl->metadata)
 4729             rec->crossing_stripes = check_crossing_stripes(
 4730                     global_info, rec->start,
 4731                     global_info->nodesize);
 4732         check_extent_type(rec);
 4733         maybe_free_extent_rec(extent_cache, rec);
 4734         return ret;
 4735     }
 4736 
 4737     ret = add_extent_rec_nolookup(extent_cache, tmpl);
 4738 
 4739     return ret;
 4740 }
 4741 
 4742 static int add_tree_backref(struct cache_tree *extent_cache, u64 bytenr,
 4743                 u64 parent, u64 root, int found_ref)
 4744 {
 4745     struct extent_record *rec;
 4746     struct tree_backref *back;
 4747     struct cache_extent *cache;
 4748     int ret;
 4749     bool insert = false;
 4750 
 4751     cache = lookup_cache_extent(extent_cache, bytenr, 1);
 4752     if (!cache) {
 4753         struct extent_record tmpl;
 4754 
 4755         memset(&tmpl, 0, sizeof(tmpl));
 4756         tmpl.start = bytenr;
 4757         tmpl.nr = 1;
 4758         tmpl.metadata = 1;
 4759         tmpl.max_size = 1;
 4760 
 4761         ret = add_extent_rec_nolookup(extent_cache, &tmpl);
 4762         if (ret)
 4763             return ret;
 4764 
 4765         /* really a bug in cache_extent implement now */
 4766         cache = lookup_cache_extent(extent_cache, bytenr, 1);
 4767         if (!cache)
 4768             return -ENOENT;
 4769     }
 4770 
 4771     rec = container_of(cache, struct extent_record, cache);
 4772     if (rec->start != bytenr) {
 4773         /*
 4774          * Several cause, from unaligned bytenr to over lapping extents
 4775          */
 4776         return -EEXIST;
 4777     }
 4778 
 4779     back = find_tree_backref(rec, parent, root);
 4780     if (!back) {
 4781         back = alloc_tree_backref(rec, parent, root);
 4782         if (!back)
 4783             return -ENOMEM;
 4784         insert = true;
 4785     }
 4786 
 4787     if (found_ref) {
 4788         if (back->node.found_ref) {
 4789             fprintf(stderr,
 4790     "Extent back ref already exists for %llu parent %llu root %llu\n",
 4791                 (unsigned long long)bytenr,
 4792                 (unsigned long long)parent,
 4793                 (unsigned long long)root);
 4794         }
 4795         back->node.found_ref = 1;
 4796     } else {
 4797         if (back->node.found_extent_tree) {
 4798             fprintf(stderr,
 4799     "extent back ref already exists for %llu parent %llu root %llu\n",
 4800                 (unsigned long long)bytenr,
 4801                 (unsigned long long)parent,
 4802                 (unsigned long long)root);
 4803         }
 4804         back->node.found_extent_tree = 1;
 4805     }
 4806     if (insert)
 4807         WARN_ON(rb_insert(&rec->backref_tree, &back->node.node,
 4808             compare_extent_backref));
 4809     check_extent_type(rec);
 4810     maybe_free_extent_rec(extent_cache, rec);
 4811     return 0;
 4812 }
 4813 
 4814 static int add_data_backref(struct cache_tree *extent_cache, u64 bytenr,
 4815                 u64 parent, u64 root, u64 owner, u64 offset,
 4816                 u32 num_refs, u64 gen, int found_ref, u64 max_size)
 4817 {
 4818     struct extent_record *rec;
 4819     struct data_backref *back;
 4820     struct cache_extent *cache;
 4821     int ret;
 4822     bool insert = false;
 4823 
 4824     cache = lookup_cache_extent(extent_cache, bytenr, 1);
 4825     if (!cache) {
 4826         struct extent_record tmpl;
 4827 
 4828         memset(&tmpl, 0, sizeof(tmpl));
 4829         tmpl.start = bytenr;
 4830         tmpl.nr = 1;
 4831         tmpl.max_size = max_size;
 4832         tmpl.generation = gen;
 4833 
 4834         ret = add_extent_rec_nolookup(extent_cache, &tmpl);
 4835         if (ret)
 4836             return ret;
 4837 
 4838         cache = lookup_cache_extent(extent_cache, bytenr, 1);
 4839         if (!cache)
 4840             abort();
 4841     }
 4842 
 4843     rec = container_of(cache, struct extent_record, cache);
 4844     if (rec->max_size < max_size)
 4845         rec->max_size = max_size;
 4846 
 4847     if (rec->generation < gen)
 4848         rec->generation = gen;
 4849     /*
 4850      * If found_ref is set then max_size is the real size and must match the
 4851      * existing refs.  So if we have already found a ref then we need to
 4852      * make sure that this ref matches the existing one, otherwise we need
 4853      * to add a new backref so we can notice that the backrefs don't match
 4854      * and we need to figure out who is telling the truth.  This is to
 4855      * account for that awful fsync bug I introduced where we'd end up with
 4856      * a btrfs_file_extent_item that would have its length include multiple
 4857      * prealloc extents or point inside of a prealloc extent.
 4858      */
 4859     back = find_data_backref(rec, parent, root, owner, offset, found_ref,
 4860                  bytenr, max_size);
 4861     if (!back) {
 4862         back = alloc_data_backref(rec, parent, root, owner, offset,
 4863                       max_size);
 4864         BUG_ON(!back);
 4865         insert = true;
 4866     }
 4867 
 4868     if (found_ref) {
 4869         BUG_ON(num_refs != 1);
 4870         if (back->node.found_ref)
 4871             BUG_ON(back->bytes != max_size);
 4872         back->node.found_ref = 1;
 4873         back->found_ref += 1;
 4874         if (back->bytes != max_size || back->disk_bytenr != bytenr) {
 4875             back->bytes = max_size;
 4876             back->disk_bytenr = bytenr;
 4877 
 4878             /* Need to reinsert if not already in the tree */
 4879             if (!insert) {
 4880                 rb_erase(&back->node.node, &rec->backref_tree);
 4881                 insert = true;
 4882             }
 4883         }
 4884         rec->refs += 1;
 4885         rec->content_checked = 1;
 4886         rec->owner_ref_checked = 1;
 4887     } else {
 4888         if (back->node.found_extent_tree) {
 4889             fprintf(stderr,
 4890 "Extent back ref already exists for %llu parent %llu root %llu owner %llu offset %llu num_refs %lu\n",
 4891                 (unsigned long long)bytenr,
 4892                 (unsigned long long)parent,
 4893                 (unsigned long long)root,
 4894                 (unsigned long long)owner,
 4895                 (unsigned long long)offset,
 4896                 (unsigned long)num_refs);
 4897         }
 4898         back->num_refs = num_refs;
 4899         back->node.found_extent_tree = 1;
 4900     }
 4901     if (insert)
 4902         WARN_ON(rb_insert(&rec->backref_tree, &back->node.node,
 4903             compare_extent_backref));
 4904 
 4905     maybe_free_extent_rec(extent_cache, rec);
 4906     return 0;
 4907 }
 4908 
 4909 static int add_pending(struct cache_tree *pending,
 4910                struct cache_tree *seen, u64 bytenr, u32 size)
 4911 {
 4912     int ret;
 4913 
 4914     ret = add_cache_extent(seen, bytenr, size);
 4915     if (ret)
 4916         return ret;
 4917     add_cache_extent(pending, bytenr, size);
 4918     return 0;
 4919 }
 4920 
 4921 static int pick_next_pending(struct cache_tree *pending,
 4922             struct cache_tree *reada,
 4923             struct cache_tree *nodes,
 4924             u64 last, struct block_info *bits, int bits_nr,
 4925             int *reada_bits)
 4926 {
 4927     unsigned long node_start = last;
 4928     struct cache_extent *cache;
 4929     int ret;
 4930 
 4931     cache = search_cache_extent(reada, 0);
 4932     if (cache) {
 4933         bits[0].start = cache->start;
 4934         bits[0].size = cache->size;
 4935         *reada_bits = 1;
 4936         return 1;
 4937     }
 4938     *reada_bits = 0;
 4939     if (node_start > 32768)
 4940         node_start -= 32768;
 4941 
 4942     cache = search_cache_extent(nodes, node_start);
 4943     if (!cache)
 4944         cache = search_cache_extent(nodes, 0);
 4945 
 4946     if (!cache) {
 4947         cache = search_cache_extent(pending, 0);
 4948         if (!cache)
 4949             return 0;
 4950         ret = 0;
 4951         do {
 4952             bits[ret].start = cache->start;
 4953             bits[ret].size = cache->size;
 4954             cache = next_cache_extent(cache);
 4955             ret++;
 4956         } while (cache && ret < bits_nr);
 4957         return ret;
 4958     }
 4959 
 4960     ret = 0;
 4961     do {
 4962         bits[ret].start = cache->start;
 4963         bits[ret].size = cache->size;
 4964         cache = next_cache_extent(cache);
 4965         ret++;
 4966     } while (cache && ret < bits_nr);
 4967 
 4968     if (bits_nr - ret > 8) {
 4969         u64 lookup = bits[0].start + bits[0].size;
 4970         struct cache_extent *next;
 4971 
 4972         next = search_cache_extent(pending, lookup);
 4973         while (next) {
 4974             if (next->start - lookup > 32768)
 4975                 break;
 4976             bits[ret].start = next->start;
 4977             bits[ret].size = next->size;
 4978             lookup = next->start + next->size;
 4979             ret++;
 4980             if (ret == bits_nr)
 4981                 break;
 4982             next = next_cache_extent(next);
 4983             if (!next)
 4984                 break;
 4985         }
 4986     }
 4987     return ret;
 4988 }
 4989 
 4990 static void free_chunk_record(struct cache_extent *cache)
 4991 {
 4992     struct chunk_record *rec;
 4993 
 4994     rec = container_of(cache, struct chunk_record, cache);
 4995     list_del_init(&rec->list);
 4996     list_del_init(&rec->dextents);
 4997     free(rec);
 4998 }
 4999 
 5000 void free_chunk_cache_tree(struct cache_tree *chunk_cache)
 5001 {
 5002     cache_tree_free_extents(chunk_cache, free_chunk_record);
 5003 }
 5004 
 5005 static void free_device_record(struct rb_node *node)
 5006 {
 5007     struct device_record *rec;
 5008 
 5009     rec = container_of(node, struct device_record, node);
 5010     free(rec);
 5011 }
 5012 
 5013 FREE_RB_BASED_TREE(device_cache, free_device_record);
 5014 
 5015 int insert_block_group_record(struct block_group_tree *tree,
 5016                   struct block_group_record *bg_rec)
 5017 {
 5018     int ret;
 5019 
 5020     ret = insert_cache_extent(&tree->tree, &bg_rec->cache);
 5021     if (ret)
 5022         return ret;
 5023 
 5024     list_add_tail(&bg_rec->list, &tree->block_groups);
 5025     return 0;
 5026 }
 5027 
 5028 static void free_block_group_record(struct cache_extent *cache)
 5029 {
 5030     struct block_group_record *rec;
 5031 
 5032     rec = container_of(cache, struct block_group_record, cache);
 5033     list_del_init(&rec->list);
 5034     free(rec);
 5035 }
 5036 
 5037 void free_block_group_tree(struct block_group_tree *tree)
 5038 {
 5039     cache_tree_free_extents(&tree->tree, free_block_group_record);
 5040 }
 5041 
 5042 int insert_device_extent_record(struct device_extent_tree *tree,
 5043                 struct device_extent_record *de_rec)
 5044 {
 5045     int ret;
 5046 
 5047     /*
 5048      * Device extent is a bit different from the other extents, because
 5049      * the extents which belong to the different devices may have the
 5050      * same start and size, so we need use the special extent cache
 5051      * search/insert functions.
 5052      */
 5053     ret = insert_cache_extent2(&tree->tree, &de_rec->cache);
 5054     if (ret)
 5055         return ret;
 5056 
 5057     list_add_tail(&de_rec->chunk_list, &tree->no_chunk_orphans);
 5058     list_add_tail(&de_rec->device_list, &tree->no_device_orphans);
 5059     return 0;
 5060 }
 5061 
 5062 static void free_device_extent_record(struct cache_extent *cache)
 5063 {
 5064     struct device_extent_record *rec;
 5065 
 5066     rec = container_of(cache, struct device_extent_record, cache);
 5067     if (!list_empty(&rec->chunk_list))
 5068         list_del_init(&rec->chunk_list);
 5069     if (!list_empty(&rec->device_list))
 5070         list_del_init(&rec->device_list);
 5071     free(rec);
 5072 }
 5073 
 5074 void free_device_extent_tree(struct device_extent_tree *tree)
 5075 {
 5076     cache_tree_free_extents(&tree->tree, free_device_extent_record);
 5077 }
 5078 
 5079 struct chunk_record *btrfs_new_chunk_record(struct extent_buffer *leaf,
 5080                         struct btrfs_key *key,
 5081                         int slot)
 5082 {
 5083     struct btrfs_chunk *ptr;
 5084     struct chunk_record *rec;
 5085     int num_stripes, i;
 5086 
 5087     ptr = btrfs_item_ptr(leaf, slot, struct btrfs_chunk);
 5088     num_stripes = btrfs_chunk_num_stripes(leaf, ptr);
 5089 
 5090     rec = calloc(1, btrfs_chunk_record_size(num_stripes));
 5091     if (!rec) {
 5092         fprintf(stderr, "memory allocation failed\n");
 5093         exit(-1);
 5094     }
 5095 
 5096     INIT_LIST_HEAD(&rec->list);
 5097     INIT_LIST_HEAD(&rec->dextents);
 5098     rec->bg_rec = NULL;
 5099 
 5100     rec->cache.start = key->offset;
 5101     rec->cache.size = btrfs_chunk_length(leaf, ptr);
 5102 
 5103     rec->generation = btrfs_header_generation(leaf);
 5104 
 5105     rec->objectid = key->objectid;
 5106     rec->type = key->type;
 5107     rec->offset = key->offset;
 5108 
 5109     rec->length = rec->cache.size;
 5110     rec->owner = btrfs_chunk_owner(leaf, ptr);
 5111     rec->stripe_len = btrfs_chunk_stripe_len(leaf, ptr);
 5112     rec->type_flags = btrfs_chunk_type(leaf, ptr);
 5113     rec->io_width = btrfs_chunk_io_width(leaf, ptr);
 5114     rec->io_align = btrfs_chunk_io_align(leaf, ptr);
 5115     rec->sector_size = btrfs_chunk_sector_size(leaf, ptr);
 5116     rec->num_stripes = num_stripes;
 5117     rec->sub_stripes = btrfs_chunk_sub_stripes(leaf, ptr);
 5118 
 5119     for (i = 0; i < rec->num_stripes; ++i) {
 5120         rec->stripes[i].devid =
 5121             btrfs_stripe_devid_nr(leaf, ptr, i);
 5122         rec->stripes[i].offset =
 5123             btrfs_stripe_offset_nr(leaf, ptr, i);
 5124         read_extent_buffer(leaf, rec->stripes[i].dev_uuid,
 5125                 (unsigned long)btrfs_stripe_dev_uuid_nr(ptr, i),
 5126                 BTRFS_UUID_SIZE);
 5127     }
 5128 
 5129     return rec;
 5130 }
 5131 
 5132 static int process_chunk_item(struct cache_tree *chunk_cache,
 5133                   struct btrfs_key *key, struct extent_buffer *eb,
 5134                   int slot)
 5135 {
 5136     struct chunk_record *rec;
 5137     struct btrfs_chunk *chunk;
 5138     int ret = 0;
 5139 
 5140     chunk = btrfs_item_ptr(eb, slot, struct btrfs_chunk);
 5141     /*
 5142      * Do extra check for this chunk item,
 5143      *
 5144      * It's still possible one can craft a leaf with CHUNK_ITEM, with
 5145      * wrong onwer(3) out of chunk tree, to pass both chunk tree check
 5146      * and owner<->key_type check.
 5147      */
 5148     ret = btrfs_check_chunk_valid(global_info, eb, chunk, slot,
 5149                       key->offset);
 5150     if (ret < 0) {
 5151         error("chunk(%llu, %llu) is not valid, ignore it",
 5152               key->offset, btrfs_chunk_length(eb, chunk));
 5153         return 0;
 5154     }
 5155     rec = btrfs_new_chunk_record(eb, key, slot);
 5156     ret = insert_cache_extent(chunk_cache, &rec->cache);
 5157     if (ret) {
 5158         fprintf(stderr, "Chunk[%llu, %llu] existed.\n",
 5159             rec->offset, rec->length);
 5160         free(rec);
 5161     }
 5162 
 5163     return ret;
 5164 }
 5165 
 5166 static int process_device_item(struct rb_root *dev_cache,
 5167         struct btrfs_key *key, struct extent_buffer *eb, int slot)
 5168 {
 5169     struct btrfs_dev_item *ptr;
 5170     struct device_record *rec;
 5171     int ret = 0;
 5172 
 5173     ptr = btrfs_item_ptr(eb,
 5174         slot, struct btrfs_dev_item);
 5175 
 5176     rec = malloc(sizeof(*rec));
 5177     if (!rec) {
 5178         fprintf(stderr, "memory allocation failed\n");
 5179         return -ENOMEM;
 5180     }
 5181 
 5182     rec->devid = key->offset;
 5183     rec->generation = btrfs_header_generation(eb);
 5184 
 5185     rec->objectid = key->objectid;
 5186     rec->type = key->type;
 5187     rec->offset = key->offset;
 5188 
 5189     rec->devid = btrfs_device_id(eb, ptr);
 5190     rec->total_byte = btrfs_device_total_bytes(eb, ptr);
 5191     rec->byte_used = btrfs_device_bytes_used(eb, ptr);
 5192 
 5193     ret = rb_insert(dev_cache, &rec->node, device_record_compare);
 5194     if (ret) {
 5195         fprintf(stderr, "Device[%llu] existed.\n", rec->devid);
 5196         free(rec);
 5197     }
 5198 
 5199     return ret;
 5200 }
 5201 
 5202 struct block_group_record *
 5203 btrfs_new_block_group_record(struct extent_buffer *leaf, struct btrfs_key *key,