check/mode-lowmem.c

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