cmds-check.c

   1 /*
   2  * Copyright (C) 2007 Oracle.  All rights reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public
   6  * License v2 as published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public
  14  * License along with this program; if not, write to the
  15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16  * Boston, MA 021110-1307, USA.
  17  */
  18
  19 #define _XOPEN_SOURCE 500
  20 #define _GNU_SOURCE 1
  21 #include <stdio.h>
  22 #include <stdlib.h>
  23 #include <unistd.h>
  24 #include <fcntl.h>
  25 #include <sys/types.h>
  26 #include <sys/stat.h>
  27 #include <unistd.h>
  28 #include <getopt.h>
  29 #include <uuid/uuid.h>
  30 #include "ctree.h"
  31 #include "volumes.h"
  32 #include "repair.h"
  33 #include "disk-io.h"
  34 #include "print-tree.h"
  35 #include "transaction.h"
  36 #include "version.h"
  37 #include "utils.h"
  38 #include "commands.h"
  39 #include "free-space-cache.h"
  40 #include "btrfsck.h"
  41 #include "qgroup-verify.h"
  42 #include "rbtree-utils.h"
  43
  44 static u64 bytes_used = 0;
  45 static u64 total_csum_bytes = 0;
  46 static u64 total_btree_bytes = 0;
  47 static u64 total_fs_tree_bytes = 0;
  48 static u64 total_extent_tree_bytes = 0;
  49 static u64 btree_space_waste = 0;
  50 static u64 data_bytes_allocated = 0;
  51 static u64 data_bytes_referenced = 0;
  52 static int found_old_backref = 0;
  53 static LIST_HEAD(duplicate_extents);
  54 static LIST_HEAD(delete_items);
  55 static int repair = 0;
  56 static int no_holes = 0;
  57 static int init_extent_tree = 0;
  58 static int check_data_csum = 0;
  59
  60 struct extent_backref {
  61         struct list_head list;
  62         unsigned int is_data:1;
  63         unsigned int found_extent_tree:1;
  64         unsigned int full_backref:1;
  65         unsigned int found_ref:1;
  66         unsigned int broken:1;
  67 };
  68
  69 struct data_backref {
  70         struct extent_backref node;
  71         union {
  72                 u64 parent;
  73                 u64 root;
  74         };
  75         u64 owner;
  76         u64 offset;
  77         u64 disk_bytenr;
  78         u64 bytes;
  79         u64 ram_bytes;
  80         u32 num_refs;
  81         u32 found_ref;
  82 };
  83
  84 struct tree_backref {
  85         struct extent_backref node;
  86         union {
  87                 u64 parent;
  88                 u64 root;
  89         };
  90 };
  91
  92 struct extent_record {
  93         struct list_head backrefs;
  94         struct list_head dups;
  95         struct list_head list;
  96         struct cache_extent cache;
  97         struct btrfs_disk_key parent_key;
  98         u64 start;
  99         u64 max_size;
 100         u64 nr;
 101         u64 refs;
 102         u64 extent_item_refs;
 103         u64 generation;
 104         u64 parent_generation;
 105         u64 info_objectid;
 106         u32 num_duplicates;
 107         u8 info_level;
 108         unsigned int found_rec:1;
 109         unsigned int content_checked:1;
 110         unsigned int owner_ref_checked:1;
 111         unsigned int is_root:1;
 112         unsigned int metadata:1;
 113 };
 114
 115 struct inode_backref {
 116         struct list_head list;
 117         unsigned int found_dir_item:1;
 118         unsigned int found_dir_index:1;
 119         unsigned int found_inode_ref:1;
 120         unsigned int filetype:8;
 121         int errors;
 122         unsigned int ref_type;
 123         u64 dir;
 124         u64 index;
 125         u16 namelen;
 126         char name[0];
 127 };
 128
 129 struct dropping_root_item_record {
 130         struct list_head list;
 131         struct btrfs_root_item ri;
 132         struct btrfs_key found_key;
 133 };
 134
 135 #define REF_ERR_NO_DIR_ITEM             (1 << 0)
 136 #define REF_ERR_NO_DIR_INDEX            (1 << 1)
 137 #define REF_ERR_NO_INODE_REF            (1 << 2)
 138 #define REF_ERR_DUP_DIR_ITEM            (1 << 3)
 139 #define REF_ERR_DUP_DIR_INDEX           (1 << 4)
 140 #define REF_ERR_DUP_INODE_REF           (1 << 5)
 141 #define REF_ERR_INDEX_UNMATCH           (1 << 6)
 142 #define REF_ERR_FILETYPE_UNMATCH        (1 << 7)
 143 #define REF_ERR_NAME_TOO_LONG           (1 << 8) // 100
 144 #define REF_ERR_NO_ROOT_REF             (1 << 9)
 145 #define REF_ERR_NO_ROOT_BACKREF         (1 << 10)
 146 #define REF_ERR_DUP_ROOT_REF            (1 << 11)
 147 #define REF_ERR_DUP_ROOT_BACKREF        (1 << 12)
 148
 149 struct inode_record {
 150         struct list_head backrefs;
 151         unsigned int checked:1;
 152         unsigned int merging:1;
 153         unsigned int found_inode_item:1;
 154         unsigned int found_dir_item:1;
 155         unsigned int found_file_extent:1;
 156         unsigned int found_csum_item:1;
 157         unsigned int some_csum_missing:1;
 158         unsigned int nodatasum:1;
 159         int errors;
 160
 161         u64 ino;
 162         u32 nlink;
 163         u32 imode;
 164         u64 isize;
 165         u64 nbytes;
 166
 167         u32 found_link;
 168         u64 found_size;
 169         u64 extent_start;
 170         u64 extent_end;
 171         u64 first_extent_gap;
 172
 173         u32 refs;
 174 };
 175
 176 #define I_ERR_NO_INODE_ITEM             (1 << 0)
 177 #define I_ERR_NO_ORPHAN_ITEM            (1 << 1)
 178 #define I_ERR_DUP_INODE_ITEM            (1 << 2)
 179 #define I_ERR_DUP_DIR_INDEX             (1 << 3)
 180 #define I_ERR_ODD_DIR_ITEM              (1 << 4)
 181 #define I_ERR_ODD_FILE_EXTENT           (1 << 5)
 182 #define I_ERR_BAD_FILE_EXTENT           (1 << 6)
 183 #define I_ERR_FILE_EXTENT_OVERLAP       (1 << 7)
 184 #define I_ERR_FILE_EXTENT_DISCOUNT      (1 << 8) // 100
 185 #define I_ERR_DIR_ISIZE_WRONG           (1 << 9)
 186 #define I_ERR_FILE_NBYTES_WRONG         (1 << 10) // 400
 187 #define I_ERR_ODD_CSUM_ITEM             (1 << 11)
 188 #define I_ERR_SOME_CSUM_MISSING         (1 << 12)
 189 #define I_ERR_LINK_COUNT_WRONG          (1 << 13)
 190
 191 struct root_backref {
 192         struct list_head list;
 193         unsigned int found_dir_item:1;
 194         unsigned int found_dir_index:1;
 195         unsigned int found_back_ref:1;
 196         unsigned int found_forward_ref:1;
 197         unsigned int reachable:1;
 198         int errors;
 199         u64 ref_root;
 200         u64 dir;
 201         u64 index;
 202         u16 namelen;
 203         char name[0];
 204 };
 205
 206 struct root_record {
 207         struct list_head backrefs;
 208         struct cache_extent cache;
 209         unsigned int found_root_item:1;
 210         u64 objectid;
 211         u32 found_ref;
 212 };
 213
 214 struct ptr_node {
 215         struct cache_extent cache;
 216         void *data;
 217 };
 218
 219 struct shared_node {
 220         struct cache_extent cache;
 221         struct cache_tree root_cache;
 222         struct cache_tree inode_cache;
 223         struct inode_record *current;
 224         u32 refs;
 225 };
 226
 227 struct block_info {
 228         u64 start;
 229         u32 size;
 230 };
 231
 232 struct walk_control {
 233         struct cache_tree shared;
 234         struct shared_node *nodes[BTRFS_MAX_LEVEL];
 235         int active_node;
 236         int root_level;
 237 };
 238
 239 struct bad_item {
 240         struct btrfs_key key;
 241         u64 root_id;
 242         struct list_head list;
 243 };
 244
 245 static void reset_cached_block_groups(struct btrfs_fs_info *fs_info);
 246
 247 static void record_root_in_trans(struct btrfs_trans_handle *trans,
 248                                  struct btrfs_root *root)
 249 {
 250         if (root->last_trans != trans->transid) {
 251                 root->track_dirty = 1;
 252                 root->last_trans = trans->transid;
 253                 root->commit_root = root->node;
 254                 extent_buffer_get(root->node);
 255         }
 256 }
 257
 258 static u8 imode_to_type(u32 imode)
 259 {
 260 #define S_SHIFT 12
 261         static unsigned char btrfs_type_by_mode[S_IFMT >> S_SHIFT] = {
 262                 [S_IFREG >> S_SHIFT]    = BTRFS_FT_REG_FILE,
 263                 [S_IFDIR >> S_SHIFT]    = BTRFS_FT_DIR,
 264                 [S_IFCHR >> S_SHIFT]    = BTRFS_FT_CHRDEV,
 265                 [S_IFBLK >> S_SHIFT]    = BTRFS_FT_BLKDEV,
 266                 [S_IFIFO >> S_SHIFT]    = BTRFS_FT_FIFO,
 267                 [S_IFSOCK >> S_SHIFT]   = BTRFS_FT_SOCK,
 268                 [S_IFLNK >> S_SHIFT]    = BTRFS_FT_SYMLINK,
 269         };
 270
 271         return btrfs_type_by_mode[(imode & S_IFMT) >> S_SHIFT];
 272 #undef S_SHIFT
 273 }
 274
 275 static int device_record_compare(struct rb_node *node1, struct rb_node *node2)
 276 {
 277         struct device_record *rec1;
 278         struct device_record *rec2;
 279
 280         rec1 = rb_entry(node1, struct device_record, node);
 281         rec2 = rb_entry(node2, struct device_record, node);
 282         if (rec1->devid > rec2->devid)
 283                 return -1;
 284         else if (rec1->devid < rec2->devid)
 285                 return 1;
 286         else
 287                 return 0;
 288 }
 289
 290 static struct inode_record *clone_inode_rec(struct inode_record *orig_rec)
 291 {
 292         struct inode_record *rec;
 293         struct inode_backref *backref;
 294         struct inode_backref *orig;
 295         size_t size;
 296
 297         rec = malloc(sizeof(*rec));
 298         memcpy(rec, orig_rec, sizeof(*rec));
 299         rec->refs = 1;
 300         INIT_LIST_HEAD(&rec->backrefs);
 301
 302         list_for_each_entry(orig, &orig_rec->backrefs, list) {
 303                 size = sizeof(*orig) + orig->namelen + 1;
 304                 backref = malloc(size);
 305                 memcpy(backref, orig, size);
 306                 list_add_tail(&backref->list, &rec->backrefs);
 307         }
 308         return rec;
 309 }
 310
 311 static void print_inode_error(struct btrfs_root *root, struct inode_record *rec)
 312 {
 313         u64 root_objectid = root->root_key.objectid;
 314         int errors = rec->errors;
 315
 316         if (!errors)
 317                 return;
 318         /* reloc root errors, we print its corresponding fs root objectid*/
 319         if (root_objectid == BTRFS_TREE_RELOC_OBJECTID) {
 320                 root_objectid = root->root_key.offset;
 321                 fprintf(stderr, "reloc");
 322         }
 323         fprintf(stderr, "root %llu inode %llu errors %x",
 324                 (unsigned long long) root_objectid,
 325                 (unsigned long long) rec->ino, rec->errors);
 326
 327         if (errors & I_ERR_NO_INODE_ITEM)
 328                 fprintf(stderr, ", no inode item");
 329         if (errors & I_ERR_NO_ORPHAN_ITEM)
 330                 fprintf(stderr, ", no orphan item");
 331         if (errors & I_ERR_DUP_INODE_ITEM)
 332                 fprintf(stderr, ", dup inode item");
 333         if (errors & I_ERR_DUP_DIR_INDEX)
 334                 fprintf(stderr, ", dup dir index");
 335         if (errors & I_ERR_ODD_DIR_ITEM)
 336                 fprintf(stderr, ", odd dir item");
 337         if (errors & I_ERR_ODD_FILE_EXTENT)
 338                 fprintf(stderr, ", odd file extent");
 339         if (errors & I_ERR_BAD_FILE_EXTENT)
 340                 fprintf(stderr, ", bad file extent");
 341         if (errors & I_ERR_FILE_EXTENT_OVERLAP)
 342                 fprintf(stderr, ", file extent overlap");
 343         if (errors & I_ERR_FILE_EXTENT_DISCOUNT)
 344                 fprintf(stderr, ", file extent discount");
 345         if (errors & I_ERR_DIR_ISIZE_WRONG)
 346                 fprintf(stderr, ", dir isize wrong");
 347         if (errors & I_ERR_FILE_NBYTES_WRONG)
 348                 fprintf(stderr, ", nbytes wrong");
 349         if (errors & I_ERR_ODD_CSUM_ITEM)
 350                 fprintf(stderr, ", odd csum item");
 351         if (errors & I_ERR_SOME_CSUM_MISSING)
 352                 fprintf(stderr, ", some csum missing");
 353         if (errors & I_ERR_LINK_COUNT_WRONG)
 354                 fprintf(stderr, ", link count wrong");
 355         fprintf(stderr, "\n");
 356 }
 357
 358 static void print_ref_error(int errors)
 359 {
 360         if (errors & REF_ERR_NO_DIR_ITEM)
 361                 fprintf(stderr, ", no dir item");
 362         if (errors & REF_ERR_NO_DIR_INDEX)
 363                 fprintf(stderr, ", no dir index");
 364         if (errors & REF_ERR_NO_INODE_REF)
 365                 fprintf(stderr, ", no inode ref");
 366         if (errors & REF_ERR_DUP_DIR_ITEM)
 367                 fprintf(stderr, ", dup dir item");
 368         if (errors & REF_ERR_DUP_DIR_INDEX)
 369                 fprintf(stderr, ", dup dir index");
 370         if (errors & REF_ERR_DUP_INODE_REF)
 371                 fprintf(stderr, ", dup inode ref");
 372         if (errors & REF_ERR_INDEX_UNMATCH)
 373                 fprintf(stderr, ", index unmatch");
 374         if (errors & REF_ERR_FILETYPE_UNMATCH)
 375                 fprintf(stderr, ", filetype unmatch");
 376         if (errors & REF_ERR_NAME_TOO_LONG)
 377                 fprintf(stderr, ", name too long");
 378         if (errors & REF_ERR_NO_ROOT_REF)
 379                 fprintf(stderr, ", no root ref");
 380         if (errors & REF_ERR_NO_ROOT_BACKREF)
 381                 fprintf(stderr, ", no root backref");
 382         if (errors & REF_ERR_DUP_ROOT_REF)
 383                 fprintf(stderr, ", dup root ref");
 384         if (errors & REF_ERR_DUP_ROOT_BACKREF)
 385                 fprintf(stderr, ", dup root backref");
 386         fprintf(stderr, "\n");
 387 }
 388
 389 static struct inode_record *get_inode_rec(struct cache_tree *inode_cache,
 390                                           u64 ino, int mod)
 391 {
 392         struct ptr_node *node;
 393         struct cache_extent *cache;
 394         struct inode_record *rec = NULL;
 395         int ret;
 396
 397         cache = lookup_cache_extent(inode_cache, ino, 1);
 398         if (cache) {
 399                 node = container_of(cache, struct ptr_node, cache);
 400                 rec = node->data;
 401                 if (mod && rec->refs > 1) {
 402                         node->data = clone_inode_rec(rec);
 403                         rec->refs--;
 404                         rec = node->data;
 405                 }
 406         } else if (mod) {
 407                 rec = calloc(1, sizeof(*rec));
 408                 rec->ino = ino;
 409                 rec->extent_start = (u64)-1;
 410                 rec->first_extent_gap = (u64)-1;
 411                 rec->refs = 1;
 412                 INIT_LIST_HEAD(&rec->backrefs);
 413
 414                 node = malloc(sizeof(*node));
 415                 node->cache.start = ino;
 416                 node->cache.size = 1;
 417                 node->data = rec;
 418
 419                 if (ino == BTRFS_FREE_INO_OBJECTID)
 420                         rec->found_link = 1;
 421
 422                 ret = insert_cache_extent(inode_cache, &node->cache);
 423                 BUG_ON(ret);
 424         }
 425         return rec;
 426 }
 427
 428 static void free_inode_rec(struct inode_record *rec)
 429 {
 430         struct inode_backref *backref;
 431
 432         if (--rec->refs > 0)
 433                 return;
 434
 435         while (!list_empty(&rec->backrefs)) {
 436                 backref = list_entry(rec->backrefs.next,
 437                                      struct inode_backref, list);
 438                 list_del(&backref->list);
 439                 free(backref);
 440         }
 441         free(rec);
 442 }
 443
 444 static int can_free_inode_rec(struct inode_record *rec)
 445 {
 446         if (!rec->errors && rec->checked && rec->found_inode_item &&
 447             rec->nlink == rec->found_link && list_empty(&rec->backrefs))
 448                 return 1;
 449         return 0;
 450 }
 451
 452 static void maybe_free_inode_rec(struct cache_tree *inode_cache,
 453                                  struct inode_record *rec)
 454 {
 455         struct cache_extent *cache;
 456         struct inode_backref *tmp, *backref;
 457         struct ptr_node *node;
 458         unsigned char filetype;
 459
 460         if (!rec->found_inode_item)
 461                 return;
 462
 463         filetype = imode_to_type(rec->imode);
 464         list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
 465                 if (backref->found_dir_item && backref->found_dir_index) {
 466                         if (backref->filetype != filetype)
 467                                 backref->errors |= REF_ERR_FILETYPE_UNMATCH;
 468                         if (!backref->errors && backref->found_inode_ref) {
 469                                 list_del(&backref->list);
 470                                 free(backref);
 471                         }
 472                 }
 473         }
 474
 475         if (!rec->checked || rec->merging)
 476                 return;
 477
 478         if (S_ISDIR(rec->imode)) {
 479                 if (rec->found_size != rec->isize)
 480                         rec->errors |= I_ERR_DIR_ISIZE_WRONG;
 481                 if (rec->found_file_extent)
 482                         rec->errors |= I_ERR_ODD_FILE_EXTENT;
 483         } else if (S_ISREG(rec->imode) || S_ISLNK(rec->imode)) {
 484                 if (rec->found_dir_item)
 485                         rec->errors |= I_ERR_ODD_DIR_ITEM;
 486                 if (rec->found_size != rec->nbytes)
 487                         rec->errors |= I_ERR_FILE_NBYTES_WRONG;
 488                 if (rec->extent_start == (u64)-1 || rec->extent_start > 0)
 489                         rec->first_extent_gap = 0;
 490                 if (rec->nlink > 0 && !no_holes &&
 491                     (rec->extent_end < rec->isize ||
 492                      rec->first_extent_gap < rec->isize))
 493                         rec->errors |= I_ERR_FILE_EXTENT_DISCOUNT;
 494         }
 495
 496         if (S_ISREG(rec->imode) || S_ISLNK(rec->imode)) {
 497                 if (rec->found_csum_item && rec->nodatasum)
 498                         rec->errors |= I_ERR_ODD_CSUM_ITEM;
 499                 if (rec->some_csum_missing && !rec->nodatasum)
 500                         rec->errors |= I_ERR_SOME_CSUM_MISSING;
 501         }
 502
 503         BUG_ON(rec->refs != 1);
 504         if (can_free_inode_rec(rec)) {
 505                 cache = lookup_cache_extent(inode_cache, rec->ino, 1);
 506                 node = container_of(cache, struct ptr_node, cache);
 507                 BUG_ON(node->data != rec);
 508                 remove_cache_extent(inode_cache, &node->cache);
 509                 free(node);
 510                 free_inode_rec(rec);
 511         }
 512 }
 513
 514 static int check_orphan_item(struct btrfs_root *root, u64 ino)
 515 {
 516         struct btrfs_path path;
 517         struct btrfs_key key;
 518         int ret;
 519
 520         key.objectid = BTRFS_ORPHAN_OBJECTID;
 521         key.type = BTRFS_ORPHAN_ITEM_KEY;
 522         key.offset = ino;
 523
 524         btrfs_init_path(&path);
 525         ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
 526         btrfs_release_path(&path);
 527         if (ret > 0)
 528                 ret = -ENOENT;
 529         return ret;
 530 }
 531
 532 static int process_inode_item(struct extent_buffer *eb,
 533                               int slot, struct btrfs_key *key,
 534                               struct shared_node *active_node)
 535 {
 536         struct inode_record *rec;
 537         struct btrfs_inode_item *item;
 538
 539         rec = active_node->current;
 540         BUG_ON(rec->ino != key->objectid || rec->refs > 1);
 541         if (rec->found_inode_item) {
 542                 rec->errors |= I_ERR_DUP_INODE_ITEM;
 543                 return 1;
 544         }
 545         item = btrfs_item_ptr(eb, slot, struct btrfs_inode_item);
 546         rec->nlink = btrfs_inode_nlink(eb, item);
 547         rec->isize = btrfs_inode_size(eb, item);
 548         rec->nbytes = btrfs_inode_nbytes(eb, item);
 549         rec->imode = btrfs_inode_mode(eb, item);
 550         if (btrfs_inode_flags(eb, item) & BTRFS_INODE_NODATASUM)
 551                 rec->nodatasum = 1;
 552         rec->found_inode_item = 1;
 553         if (rec->nlink == 0)
 554                 rec->errors |= I_ERR_NO_ORPHAN_ITEM;
 555         maybe_free_inode_rec(&active_node->inode_cache, rec);
 556         return 0;
 557 }
 558
 559 static struct inode_backref *get_inode_backref(struct inode_record *rec,
 560                                                 const char *name,
 561                                                 int namelen, u64 dir)
 562 {
 563         struct inode_backref *backref;
 564
 565         list_for_each_entry(backref, &rec->backrefs, list) {
 566                 if (rec->ino == BTRFS_MULTIPLE_OBJECTIDS)
 567                         break;
 568                 if (backref->dir != dir || backref->namelen != namelen)
 569                         continue;
 570                 if (memcmp(name, backref->name, namelen))
 571                         continue;
 572                 return backref;
 573         }
 574
 575         backref = malloc(sizeof(*backref) + namelen + 1);
 576         memset(backref, 0, sizeof(*backref));
 577         backref->dir = dir;
 578         backref->namelen = namelen;
 579         memcpy(backref->name, name, namelen);
 580         backref->name[namelen] = '\0';
 581         list_add_tail(&backref->list, &rec->backrefs);
 582         return backref;
 583 }
 584
 585 static int add_inode_backref(struct cache_tree *inode_cache,
 586                              u64 ino, u64 dir, u64 index,
 587                              const char *name, int namelen,
 588                              int filetype, int itemtype, int errors)
 589 {
 590         struct inode_record *rec;
 591         struct inode_backref *backref;
 592
 593         rec = get_inode_rec(inode_cache, ino, 1);
 594         backref = get_inode_backref(rec, name, namelen, dir);
 595         if (errors)
 596                 backref->errors |= errors;
 597         if (itemtype == BTRFS_DIR_INDEX_KEY) {
 598                 if (backref->found_dir_index)
 599                         backref->errors |= REF_ERR_DUP_DIR_INDEX;
 600                 if (backref->found_inode_ref && backref->index != index)
 601                         backref->errors |= REF_ERR_INDEX_UNMATCH;
 602                 if (backref->found_dir_item && backref->filetype != filetype)
 603                         backref->errors |= REF_ERR_FILETYPE_UNMATCH;
 604
 605                 backref->index = index;
 606                 backref->filetype = filetype;
 607                 backref->found_dir_index = 1;
 608         } else if (itemtype == BTRFS_DIR_ITEM_KEY) {
 609                 rec->found_link++;
 610                 if (backref->found_dir_item)
 611                         backref->errors |= REF_ERR_DUP_DIR_ITEM;
 612                 if (backref->found_dir_index && backref->filetype != filetype)
 613                         backref->errors |= REF_ERR_FILETYPE_UNMATCH;
 614
 615                 backref->filetype = filetype;
 616                 backref->found_dir_item = 1;
 617         } else if ((itemtype == BTRFS_INODE_REF_KEY) ||
 618                    (itemtype == BTRFS_INODE_EXTREF_KEY)) {
 619                 if (backref->found_inode_ref)
 620                         backref->errors |= REF_ERR_DUP_INODE_REF;
 621                 if (backref->found_dir_index && backref->index != index)
 622                         backref->errors |= REF_ERR_INDEX_UNMATCH;
 623
 624                 backref->ref_type = itemtype;
 625                 backref->index = index;
 626                 backref->found_inode_ref = 1;
 627         } else {
 628                 BUG_ON(1);
 629         }
 630
 631         maybe_free_inode_rec(inode_cache, rec);
 632         return 0;
 633 }
 634
 635 static int merge_inode_recs(struct inode_record *src, struct inode_record *dst,
 636                             struct cache_tree *dst_cache)
 637 {
 638         struct inode_backref *backref;
 639         u32 dir_count = 0;
 640
 641         dst->merging = 1;
 642         list_for_each_entry(backref, &src->backrefs, list) {
 643                 if (backref->found_dir_index) {
 644                         add_inode_backref(dst_cache, dst->ino, backref->dir,
 645                                         backref->index, backref->name,
 646                                         backref->namelen, backref->filetype,
 647                                         BTRFS_DIR_INDEX_KEY, backref->errors);
 648                 }
 649                 if (backref->found_dir_item) {
 650                         dir_count++;
 651                         add_inode_backref(dst_cache, dst->ino,
 652                                         backref->dir, 0, backref->name,
 653                                         backref->namelen, backref->filetype,
 654                                         BTRFS_DIR_ITEM_KEY, backref->errors);
 655                 }
 656                 if (backref->found_inode_ref) {
 657                         add_inode_backref(dst_cache, dst->ino,
 658                                         backref->dir, backref->index,
 659                                         backref->name, backref->namelen, 0,
 660                                         backref->ref_type, backref->errors);
 661                 }
 662         }
 663
 664         if (src->found_dir_item)
 665                 dst->found_dir_item = 1;
 666         if (src->found_file_extent)
 667                 dst->found_file_extent = 1;
 668         if (src->found_csum_item)
 669                 dst->found_csum_item = 1;
 670         if (src->some_csum_missing)
 671                 dst->some_csum_missing = 1;
 672         if (dst->first_extent_gap > src->first_extent_gap)
 673                 dst->first_extent_gap = src->first_extent_gap;
 674
 675         BUG_ON(src->found_link < dir_count);
 676         dst->found_link += src->found_link - dir_count;
 677         dst->found_size += src->found_size;
 678         if (src->extent_start != (u64)-1) {
 679                 if (dst->extent_start == (u64)-1) {
 680                         dst->extent_start = src->extent_start;
 681                         dst->extent_end = src->extent_end;
 682                 } else {
 683                         if (dst->extent_end > src->extent_start)
 684                                 dst->errors |= I_ERR_FILE_EXTENT_OVERLAP;
 685                         else if (dst->extent_end < src->extent_start &&
 686                                  dst->extent_end < dst->first_extent_gap)
 687                                 dst->first_extent_gap = dst->extent_end;
 688                         if (dst->extent_end < src->extent_end)
 689                                 dst->extent_end = src->extent_end;
 690                 }
 691         }
 692
 693         dst->errors |= src->errors;
 694         if (src->found_inode_item) {
 695                 if (!dst->found_inode_item) {
 696                         dst->nlink = src->nlink;
 697                         dst->isize = src->isize;
 698                         dst->nbytes = src->nbytes;
 699                         dst->imode = src->imode;
 700                         dst->nodatasum = src->nodatasum;
 701                         dst->found_inode_item = 1;
 702                 } else {
 703                         dst->errors |= I_ERR_DUP_INODE_ITEM;
 704                 }
 705         }
 706         dst->merging = 0;
 707
 708         return 0;
 709 }
 710
 711 static int splice_shared_node(struct shared_node *src_node,
 712                               struct shared_node *dst_node)
 713 {
 714         struct cache_extent *cache;
 715         struct ptr_node *node, *ins;
 716         struct cache_tree *src, *dst;
 717         struct inode_record *rec, *conflict;
 718         u64 current_ino = 0;
 719         int splice = 0;
 720         int ret;
 721
 722         if (--src_node->refs == 0)
 723                 splice = 1;
 724         if (src_node->current)
 725                 current_ino = src_node->current->ino;
 726
 727         src = &src_node->root_cache;
 728         dst = &dst_node->root_cache;
 729 again:
 730         cache = search_cache_extent(src, 0);
 731         while (cache) {
 732                 node = container_of(cache, struct ptr_node, cache);
 733                 rec = node->data;
 734                 cache = next_cache_extent(cache);
 735
 736                 if (splice) {
 737                         remove_cache_extent(src, &node->cache);
 738                         ins = node;
 739                 } else {
 740                         ins = malloc(sizeof(*ins));
 741                         ins->cache.start = node->cache.start;
 742                         ins->cache.size = node->cache.size;
 743                         ins->data = rec;
 744                         rec->refs++;
 745                 }
 746                 ret = insert_cache_extent(dst, &ins->cache);
 747                 if (ret == -EEXIST) {
 748                         conflict = get_inode_rec(dst, rec->ino, 1);
 749                         merge_inode_recs(rec, conflict, dst);
 750                         if (rec->checked) {
 751                                 conflict->checked = 1;
 752                                 if (dst_node->current == conflict)
 753                                         dst_node->current = NULL;
 754                         }
 755                         maybe_free_inode_rec(dst, conflict);
 756                         free_inode_rec(rec);
 757                         free(ins);
 758                 } else {
 759                         BUG_ON(ret);
 760                 }
 761         }
 762
 763         if (src == &src_node->root_cache) {
 764                 src = &src_node->inode_cache;
 765                 dst = &dst_node->inode_cache;
 766                 goto again;
 767         }
 768
 769         if (current_ino > 0 && (!dst_node->current ||
 770             current_ino > dst_node->current->ino)) {
 771                 if (dst_node->current) {
 772                         dst_node->current->checked = 1;
 773                         maybe_free_inode_rec(dst, dst_node->current);
 774                 }
 775                 dst_node->current = get_inode_rec(dst, current_ino, 1);
 776         }
 777         return 0;
 778 }
 779
 780 static void free_inode_ptr(struct cache_extent *cache)
 781 {
 782         struct ptr_node *node;
 783         struct inode_record *rec;
 784
 785         node = container_of(cache, struct ptr_node, cache);
 786         rec = node->data;
 787         free_inode_rec(rec);
 788         free(node);
 789 }
 790
 791 FREE_EXTENT_CACHE_BASED_TREE(inode_recs, free_inode_ptr);
 792
 793 static struct shared_node *find_shared_node(struct cache_tree *shared,
 794                                             u64 bytenr)
 795 {
 796         struct cache_extent *cache;
 797         struct shared_node *node;
 798
 799         cache = lookup_cache_extent(shared, bytenr, 1);
 800         if (cache) {
 801                 node = container_of(cache, struct shared_node, cache);
 802                 return node;
 803         }
 804         return NULL;
 805 }
 806
 807 static int add_shared_node(struct cache_tree *shared, u64 bytenr, u32 refs)
 808 {
 809         int ret;
 810         struct shared_node *node;
 811
 812         node = calloc(1, sizeof(*node));
 813         node->cache.start = bytenr;
 814         node->cache.size = 1;
 815         cache_tree_init(&node->root_cache);
 816         cache_tree_init(&node->inode_cache);
 817         node->refs = refs;
 818
 819         ret = insert_cache_extent(shared, &node->cache);
 820         BUG_ON(ret);
 821         return 0;
 822 }
 823
 824 static int enter_shared_node(struct btrfs_root *root, u64 bytenr, u32 refs,
 825                              struct walk_control *wc, int level)
 826 {
 827         struct shared_node *node;
 828         struct shared_node *dest;
 829
 830         if (level == wc->active_node)
 831                 return 0;
 832
 833         BUG_ON(wc->active_node <= level);
 834         node = find_shared_node(&wc->shared, bytenr);
 835         if (!node) {
 836                 add_shared_node(&wc->shared, bytenr, refs);
 837                 node = find_shared_node(&wc->shared, bytenr);
 838                 wc->nodes[level] = node;
 839                 wc->active_node = level;
 840                 return 0;
 841         }
 842
 843         if (wc->root_level == wc->active_node &&
 844             btrfs_root_refs(&root->root_item) == 0) {
 845                 if (--node->refs == 0) {
 846                         free_inode_recs_tree(&node->root_cache);
 847                         free_inode_recs_tree(&node->inode_cache);
 848                         remove_cache_extent(&wc->shared, &node->cache);
 849                         free(node);
 850                 }
 851                 return 1;
 852         }
 853
 854         dest = wc->nodes[wc->active_node];
 855         splice_shared_node(node, dest);
 856         if (node->refs == 0) {
 857                 remove_cache_extent(&wc->shared, &node->cache);
 858                 free(node);
 859         }
 860         return 1;
 861 }
 862
 863 static int leave_shared_node(struct btrfs_root *root,
 864                              struct walk_control *wc, int level)
 865 {
 866         struct shared_node *node;
 867         struct shared_node *dest;
 868         int i;
 869
 870         if (level == wc->root_level)
 871                 return 0;
 872
 873         for (i = level + 1; i < BTRFS_MAX_LEVEL; i++) {
 874                 if (wc->nodes[i])
 875                         break;
 876         }
 877         BUG_ON(i >= BTRFS_MAX_LEVEL);
 878
 879         node = wc->nodes[wc->active_node];
 880         wc->nodes[wc->active_node] = NULL;
 881         wc->active_node = i;
 882
 883         dest = wc->nodes[wc->active_node];
 884         if (wc->active_node < wc->root_level ||
 885             btrfs_root_refs(&root->root_item) > 0) {
 886                 BUG_ON(node->refs <= 1);
 887                 splice_shared_node(node, dest);
 888         } else {
 889                 BUG_ON(node->refs < 2);
 890                 node->refs--;
 891         }
 892         return 0;
 893 }
 894
 895 static int is_child_root(struct btrfs_root *root, u64 parent_root_id,
 896                          u64 child_root_id)
 897 {
 898         struct btrfs_path path;
 899         struct btrfs_key key;
 900         struct extent_buffer *leaf;
 901         int has_parent = 0;
 902         int ret;
 903
 904         btrfs_init_path(&path);
 905
 906         key.objectid = parent_root_id;
 907         key.type = BTRFS_ROOT_REF_KEY;
 908         key.offset = child_root_id;
 909         ret = btrfs_search_slot(NULL, root->fs_info->tree_root, &key, &path,
 910                                 0, 0);
 911         if (ret < 0)
 912                 return ret;
 913         btrfs_release_path(&path);
 914         if (!ret)
 915                 return 1;
 916
 917         key.objectid = child_root_id;
 918         key.type = BTRFS_ROOT_BACKREF_KEY;
 919         key.offset = 0;
 920         ret = btrfs_search_slot(NULL, root->fs_info->tree_root, &key, &path,
 921                                 0, 0);
 922         if (ret < 0)
 923                 goto out;
 924
 925         while (1) {
 926                 leaf = path.nodes[0];
 927                 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
 928                         ret = btrfs_next_leaf(root->fs_info->tree_root, &path);
 929                         if (ret)
 930                                 break;
 931                         leaf = path.nodes[0];
 932                 }
 933
 934                 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
 935                 if (key.objectid != child_root_id ||
 936                     key.type != BTRFS_ROOT_BACKREF_KEY)
 937                         break;
 938
 939                 has_parent = 1;
 940
 941                 if (key.offset == parent_root_id) {
 942                         btrfs_release_path(&path);
 943                         return 1;
 944                 }
 945
 946                 path.slots[0]++;
 947         }
 948 out:
 949         btrfs_release_path(&path);
 950         if (ret < 0)
 951                 return ret;
 952         return has_parent? 0 : -1;
 953 }
 954
 955 static int process_dir_item(struct btrfs_root *root,
 956                             struct extent_buffer *eb,
 957                             int slot, struct btrfs_key *key,
 958                             struct shared_node *active_node)
 959 {
 960         u32 total;
 961         u32 cur = 0;
 962         u32 len;
 963         u32 name_len;
 964         u32 data_len;
 965         int error;
 966         int nritems = 0;
 967         int filetype;
 968         struct btrfs_dir_item *di;
 969         struct inode_record *rec;
 970         struct cache_tree *root_cache;
 971         struct cache_tree *inode_cache;
 972         struct btrfs_key location;
 973         char namebuf[BTRFS_NAME_LEN];
 974
 975         root_cache = &active_node->root_cache;
 976         inode_cache = &active_node->inode_cache;
 977         rec = active_node->current;
 978         rec->found_dir_item = 1;
 979
 980         di = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);
 981         total = btrfs_item_size_nr(eb, slot);
 982         while (cur < total) {
 983                 nritems++;
 984                 btrfs_dir_item_key_to_cpu(eb, di, &location);
 985                 name_len = btrfs_dir_name_len(eb, di);
 986                 data_len = btrfs_dir_data_len(eb, di);
 987                 filetype = btrfs_dir_type(eb, di);
 988
 989                 rec->found_size += name_len;
 990                 if (name_len <= BTRFS_NAME_LEN) {
 991                         len = name_len;
 992                         error = 0;
 993                 } else {
 994                         len = BTRFS_NAME_LEN;
 995                         error = REF_ERR_NAME_TOO_LONG;
 996                 }
 997                 read_extent_buffer(eb, namebuf, (unsigned long)(di + 1), len);
 998
 999                 if (location.type == BTRFS_INODE_ITEM_KEY) {
1000                         add_inode_backref(inode_cache, location.objectid,
1001                                           key->objectid, key->offset, namebuf,
1002                                           len, filetype, key->type, error);
1003                 } else if (location.type == BTRFS_ROOT_ITEM_KEY) {
1004                         add_inode_backref(root_cache, location.objectid,
1005                                           key->objectid, key->offset,
1006                                           namebuf, len, filetype,
1007                                           key->type, error);
1008                 } else {
1009                         fprintf(stderr, "invalid location in dir item %u\n",
1010                                 location.type);
1011                         add_inode_backref(inode_cache, BTRFS_MULTIPLE_OBJECTIDS,
1012                                           key->objectid, key->offset, namebuf,
1013                                           len, filetype, key->type, error);
1014                 }
1015
1016                 len = sizeof(*di) + name_len + data_len;
1017                 di = (struct btrfs_dir_item *)((char *)di + len);
1018                 cur += len;
1019         }
1020         if (key->type == BTRFS_DIR_INDEX_KEY && nritems > 1)
1021                 rec->errors |= I_ERR_DUP_DIR_INDEX;
1022
1023         return 0;
1024 }
1025
1026 static int process_inode_ref(struct extent_buffer *eb,
1027                              int slot, struct btrfs_key *key,
1028                              struct shared_node *active_node)
1029 {
1030         u32 total;
1031         u32 cur = 0;
1032         u32 len;
1033         u32 name_len;
1034         u64 index;
1035         int error;
1036         struct cache_tree *inode_cache;
1037         struct btrfs_inode_ref *ref;
1038         char namebuf[BTRFS_NAME_LEN];
1039
1040         inode_cache = &active_node->inode_cache;
1041
1042         ref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
1043         total = btrfs_item_size_nr(eb, slot);
1044         while (cur < total) {
1045                 name_len = btrfs_inode_ref_name_len(eb, ref);
1046                 index = btrfs_inode_ref_index(eb, ref);
1047                 if (name_len <= BTRFS_NAME_LEN) {
1048                         len = name_len;
1049                         error = 0;
1050                 } else {
1051                         len = BTRFS_NAME_LEN;
1052                         error = REF_ERR_NAME_TOO_LONG;
1053                 }
1054                 read_extent_buffer(eb, namebuf, (unsigned long)(ref + 1), len);
1055                 add_inode_backref(inode_cache, key->objectid, key->offset,
1056                                   index, namebuf, len, 0, key->type, error);
1057
1058                 len = sizeof(*ref) + name_len;
1059                 ref = (struct btrfs_inode_ref *)((char *)ref + len);
1060                 cur += len;
1061         }
1062         return 0;
1063 }
1064
1065 static int process_inode_extref(struct extent_buffer *eb,
1066                                 int slot, struct btrfs_key *key,
1067                                 struct shared_node *active_node)
1068 {
1069         u32 total;
1070         u32 cur = 0;
1071         u32 len;
1072         u32 name_len;
1073         u64 index;
1074         u64 parent;
1075         int error;
1076         struct cache_tree *inode_cache;
1077         struct btrfs_inode_extref *extref;
1078         char namebuf[BTRFS_NAME_LEN];
1079
1080         inode_cache = &active_node->inode_cache;
1081
1082         extref = btrfs_item_ptr(eb, slot, struct btrfs_inode_extref);
1083         total = btrfs_item_size_nr(eb, slot);
1084         while (cur < total) {
1085                 name_len = btrfs_inode_extref_name_len(eb, extref);
1086                 index = btrfs_inode_extref_index(eb, extref);
1087                 parent = btrfs_inode_extref_parent(eb, extref);
1088                 if (name_len <= BTRFS_NAME_LEN) {
1089                         len = name_len;
1090                         error = 0;
1091                 } else {
1092                         len = BTRFS_NAME_LEN;
1093                         error = REF_ERR_NAME_TOO_LONG;
1094                 }
1095                 read_extent_buffer(eb, namebuf,
1096                                    (unsigned long)(extref + 1), len);
1097                 add_inode_backref(inode_cache, key->objectid, parent,
1098                                   index, namebuf, len, 0, key->type, error);
1099
1100                 len = sizeof(*extref) + name_len;
1101                 extref = (struct btrfs_inode_extref *)((char *)extref + len);
1102                 cur += len;
1103         }
1104         return 0;
1105
1106 }
1107
1108 static int count_csum_range(struct btrfs_root *root, u64 start,
1109                             u64 len, u64 *found)
1110 {
1111         struct btrfs_key key;
1112         struct btrfs_path path;
1113         struct extent_buffer *leaf;
1114         int ret;
1115         size_t size;
1116         *found = 0;
1117         u64 csum_end;
1118         u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
1119
1120         btrfs_init_path(&path);
1121
1122         key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
1123         key.offset = start;
1124         key.type = BTRFS_EXTENT_CSUM_KEY;
1125
1126         ret = btrfs_search_slot(NULL, root->fs_info->csum_root,
1127                                 &key, &path, 0, 0);
1128         if (ret < 0)
1129                 goto out;
1130         if (ret > 0 && path.slots[0] > 0) {
1131                 leaf = path.nodes[0];
1132                 btrfs_item_key_to_cpu(leaf, &key, path.slots[0] - 1);
1133                 if (key.objectid == BTRFS_EXTENT_CSUM_OBJECTID &&
1134                     key.type == BTRFS_EXTENT_CSUM_KEY)
1135                         path.slots[0]--;
1136         }
1137
1138         while (len > 0) {
1139                 leaf = path.nodes[0];
1140                 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
1141                         ret = btrfs_next_leaf(root->fs_info->csum_root, &path);
1142                         if (ret > 0)
1143                                 break;
1144                         else if (ret < 0)
1145                                 goto out;
1146                         leaf = path.nodes[0];
1147                 }
1148
1149                 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
1150                 if (key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
1151                     key.type != BTRFS_EXTENT_CSUM_KEY)
1152                         break;
1153
1154                 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
1155                 if (key.offset >= start + len)
1156                         break;
1157
1158                 if (key.offset > start)
1159                         start = key.offset;
1160
1161                 size = btrfs_item_size_nr(leaf, path.slots[0]);
1162                 csum_end = key.offset + (size / csum_size) * root->sectorsize;
1163                 if (csum_end > start) {
1164                         size = min(csum_end - start, len);
1165                         len -= size;
1166                         start += size;
1167                         *found += size;
1168                 }
1169
1170                 path.slots[0]++;
1171         }
1172 out:
1173         if (ret < 0)
1174                 return ret;
1175         btrfs_release_path(&path);
1176         return 0;
1177 }
1178
1179 static int process_file_extent(struct btrfs_root *root,
1180                                 struct extent_buffer *eb,
1181                                 int slot, struct btrfs_key *key,
1182                                 struct shared_node *active_node)
1183 {
1184         struct inode_record *rec;
1185         struct btrfs_file_extent_item *fi;
1186         u64 num_bytes = 0;
1187         u64 disk_bytenr = 0;
1188         u64 extent_offset = 0;
1189         u64 mask = root->sectorsize - 1;
1190         int extent_type;
1191         int ret;
1192
1193         rec = active_node->current;
1194         BUG_ON(rec->ino != key->objectid || rec->refs > 1);
1195         rec->found_file_extent = 1;
1196
1197         if (rec->extent_start == (u64)-1) {
1198                 rec->extent_start = key->offset;
1199                 rec->extent_end = key->offset;
1200         }
1201
1202         if (rec->extent_end > key->offset)
1203                 rec->errors |= I_ERR_FILE_EXTENT_OVERLAP;
1204         else if (rec->extent_end < key->offset &&
1205                  rec->extent_end < rec->first_extent_gap)
1206                 rec->first_extent_gap = rec->extent_end;
1207
1208         fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
1209         extent_type = btrfs_file_extent_type(eb, fi);
1210
1211         if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
1212                 num_bytes = btrfs_file_extent_inline_len(eb, slot, fi);
1213                 if (num_bytes == 0)
1214                         rec->errors |= I_ERR_BAD_FILE_EXTENT;
1215                 rec->found_size += num_bytes;
1216                 num_bytes = (num_bytes + mask) & ~mask;
1217         } else if (extent_type == BTRFS_FILE_EXTENT_REG ||
1218                    extent_type == BTRFS_FILE_EXTENT_PREALLOC) {
1219                 num_bytes = btrfs_file_extent_num_bytes(eb, fi);
1220                 disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
1221                 extent_offset = btrfs_file_extent_offset(eb, fi);
1222                 if (num_bytes == 0 || (num_bytes & mask))
1223                         rec->errors |= I_ERR_BAD_FILE_EXTENT;
1224                 if (num_bytes + extent_offset >
1225                     btrfs_file_extent_ram_bytes(eb, fi))
1226                         rec->errors |= I_ERR_BAD_FILE_EXTENT;
1227                 if (extent_type == BTRFS_FILE_EXTENT_PREALLOC &&
1228                     (btrfs_file_extent_compression(eb, fi) ||
1229                      btrfs_file_extent_encryption(eb, fi) ||
1230                      btrfs_file_extent_other_encoding(eb, fi)))
1231                         rec->errors |= I_ERR_BAD_FILE_EXTENT;
1232                 if (disk_bytenr > 0)
1233                         rec->found_size += num_bytes;
1234         } else {
1235                 rec->errors |= I_ERR_BAD_FILE_EXTENT;
1236         }
1237         rec->extent_end = key->offset + num_bytes;
1238
1239         if (disk_bytenr > 0) {
1240                 u64 found;
1241                 if (btrfs_file_extent_compression(eb, fi))
1242                         num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
1243                 else
1244                         disk_bytenr += extent_offset;
1245
1246                 ret = count_csum_range(root, disk_bytenr, num_bytes, &found);
1247                 if (ret < 0)
1248                         return ret;
1249                 if (extent_type == BTRFS_FILE_EXTENT_REG) {
1250                         if (found > 0)
1251                                 rec->found_csum_item = 1;
1252                         if (found < num_bytes)
1253                                 rec->some_csum_missing = 1;
1254                 } else if (extent_type == BTRFS_FILE_EXTENT_PREALLOC) {
1255                         if (found > 0)
1256                                 rec->errors |= I_ERR_ODD_CSUM_ITEM;
1257                 }
1258         }
1259         return 0;
1260 }
1261
1262 static int process_one_leaf(struct btrfs_root *root, struct extent_buffer *eb,
1263                             struct walk_control *wc)
1264 {
1265         struct btrfs_key key;
1266         u32 nritems;
1267         int i;
1268         int ret = 0;
1269         struct cache_tree *inode_cache;
1270         struct shared_node *active_node;
1271
1272         if (wc->root_level == wc->active_node &&
1273             btrfs_root_refs(&root->root_item) == 0)
1274                 return 0;
1275
1276         active_node = wc->nodes[wc->active_node];
1277         inode_cache = &active_node->inode_cache;
1278         nritems = btrfs_header_nritems(eb);
1279         for (i = 0; i < nritems; i++) {
1280                 btrfs_item_key_to_cpu(eb, &key, i);
1281
1282                 if (key.objectid == BTRFS_FREE_SPACE_OBJECTID)
1283                         continue;
1284                 if (key.type == BTRFS_ORPHAN_ITEM_KEY)
1285                         continue;
1286
1287                 if (active_node->current == NULL ||
1288                     active_node->current->ino < key.objectid) {
1289                         if (active_node->current) {
1290                                 active_node->current->checked = 1;
1291                                 maybe_free_inode_rec(inode_cache,
1292                                                      active_node->current);
1293                         }
1294                         active_node->current = get_inode_rec(inode_cache,
1295                                                              key.objectid, 1);
1296                 }
1297                 switch (key.type) {
1298                 case BTRFS_DIR_ITEM_KEY:
1299                 case BTRFS_DIR_INDEX_KEY:
1300                         ret = process_dir_item(root, eb, i, &key, active_node);
1301                         break;
1302                 case BTRFS_INODE_REF_KEY:
1303                         ret = process_inode_ref(eb, i, &key, active_node);
1304                         break;
1305                 case BTRFS_INODE_EXTREF_KEY:
1306                         ret = process_inode_extref(eb, i, &key, active_node);
1307                         break;
1308                 case BTRFS_INODE_ITEM_KEY:
1309                         ret = process_inode_item(eb, i, &key, active_node);
1310                         break;
1311                 case BTRFS_EXTENT_DATA_KEY:
1312                         ret = process_file_extent(root, eb, i, &key,
1313                                                   active_node);
1314                         break;
1315                 default:
1316                         break;
1317                 };
1318         }
1319         return ret;
1320 }
1321
1322 static void reada_walk_down(struct btrfs_root *root,
1323                             struct extent_buffer *node, int slot)
1324 {
1325         u64 bytenr;
1326         u64 ptr_gen;
1327         u32 nritems;
1328         u32 blocksize;
1329         int i;
1330         int level;
1331
1332         level = btrfs_header_level(node);
1333         if (level != 1)
1334                 return;
1335
1336         nritems = btrfs_header_nritems(node);
1337         blocksize = btrfs_level_size(root, level - 1);
1338         for (i = slot; i < nritems; i++) {
1339                 bytenr = btrfs_node_blockptr(node, i);
1340                 ptr_gen = btrfs_node_ptr_generation(node, i);
1341                 readahead_tree_block(root, bytenr, blocksize, ptr_gen);
1342         }
1343 }
1344
1345 /*
1346  * Check the child node/leaf by the following condition:
1347  * 1. the first item key of the node/leaf should be the same with the one
1348  *    in parent.
1349  * 2. block in parent node should match the child node/leaf.
1350  * 3. generation of parent node and child's header should be consistent.
1351  *
1352  * Or the child node/leaf pointed by the key in parent is not valid.
1353  *
1354  * We hope to check leaf owner too, but since subvol may share leaves,
1355  * which makes leaf owner check not so strong, key check should be
1356  * sufficient enough for that case.
1357  */
1358 static int check_child_node(struct btrfs_root *root,
1359                             struct extent_buffer *parent, int slot,
1360                             struct extent_buffer *child)
1361 {
1362         struct btrfs_key parent_key;
1363         struct btrfs_key child_key;
1364         int ret = 0;
1365
1366         btrfs_node_key_to_cpu(parent, &parent_key, slot);
1367         if (btrfs_header_level(child) == 0)
1368                 btrfs_item_key_to_cpu(child, &child_key, 0);
1369         else
1370                 btrfs_node_key_to_cpu(child, &child_key, 0);
1371
1372         if (memcmp(&parent_key, &child_key, sizeof(parent_key))) {
1373                 ret = -EINVAL;
1374                 fprintf(stderr,
1375                         "Wrong key of child node/leaf, wanted: (%llu, %u, %llu), have: (%llu, %u, %llu)\n",
1376                         parent_key.objectid, parent_key.type, parent_key.offset,
1377                         child_key.objectid, child_key.type, child_key.offset);
1378         }
1379         if (btrfs_header_bytenr(child) != btrfs_node_blockptr(parent, slot)) {
1380                 ret = -EINVAL;
1381                 fprintf(stderr, "Wrong block of child node/leaf, wanted: %llu, have: %llu\n",
1382                         btrfs_node_blockptr(parent, slot),
1383                         btrfs_header_bytenr(child));
1384         }
1385         if (btrfs_node_ptr_generation(parent, slot) !=
1386             btrfs_header_generation(child)) {
1387                 ret = -EINVAL;
1388                 fprintf(stderr, "Wrong generation of child node/leaf, wanted: %llu, have: %llu\n",
1389                         btrfs_header_generation(child),
1390                         btrfs_node_ptr_generation(parent, slot));
1391         }
1392         return ret;
1393 }
1394
1395 static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
1396                           struct walk_control *wc, int *level)
1397 {
1398         u64 bytenr;
1399         u64 ptr_gen;
1400         struct extent_buffer *next;
1401         struct extent_buffer *cur;
1402         u32 blocksize;
1403         int ret, err = 0;
1404         u64 refs;
1405
1406         WARN_ON(*level < 0);
1407         WARN_ON(*level >= BTRFS_MAX_LEVEL);
1408         ret = btrfs_lookup_extent_info(NULL, root,
1409                                        path->nodes[*level]->start,
1410                                        *level, 1, &refs, NULL);
1411         if (ret < 0) {
1412                 err = ret;
1413                 goto out;
1414         }
1415
1416         if (refs > 1) {
1417                 ret = enter_shared_node(root, path->nodes[*level]->start,
1418                                         refs, wc, *level);
1419                 if (ret > 0) {
1420                         err = ret;
1421                         goto out;
1422                 }
1423         }
1424
1425         while (*level >= 0) {
1426                 WARN_ON(*level < 0);
1427                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1428                 cur = path->nodes[*level];
1429
1430                 if (btrfs_header_level(cur) != *level)
1431                         WARN_ON(1);
1432
1433                 if (path->slots[*level] >= btrfs_header_nritems(cur))
1434                         break;
1435                 if (*level == 0) {
1436                         ret = process_one_leaf(root, cur, wc);
1437                         if (ret < 0)
1438                                 err = ret;
1439                         break;
1440                 }
1441                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
1442                 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
1443                 blocksize = btrfs_level_size(root, *level - 1);
1444                 ret = btrfs_lookup_extent_info(NULL, root, bytenr, *level - 1,
1445                                                1, &refs, NULL);
1446                 if (ret < 0)
1447                         refs = 0;
1448
1449                 if (refs > 1) {
1450                         ret = enter_shared_node(root, bytenr, refs,
1451                                                 wc, *level - 1);
1452                         if (ret > 0) {
1453                                 path->slots[*level]++;
1454                                 continue;
1455                         }
1456                 }
1457
1458                 next = btrfs_find_tree_block(root, bytenr, blocksize);
1459                 if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
1460                         free_extent_buffer(next);
1461                         reada_walk_down(root, cur, path->slots[*level]);
1462                         next = read_tree_block(root, bytenr, blocksize,
1463                                                ptr_gen);
1464                         if (!next) {
1465                                 err = -EIO;
1466                                 goto out;
1467                         }
1468                 }
1469
1470                 ret = check_child_node(root, cur, path->slots[*level], next);
1471                 if (ret) {
1472                         err = ret;
1473                         goto out;
1474                 }
1475                 *level = *level - 1;
1476                 free_extent_buffer(path->nodes[*level]);
1477                 path->nodes[*level] = next;
1478                 path->slots[*level] = 0;
1479         }
1480 out:
1481         path->slots[*level] = btrfs_header_nritems(path->nodes[*level]);
1482         return err;
1483 }
1484
1485 static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
1486                         struct walk_control *wc, int *level)
1487 {
1488         int i;
1489         struct extent_buffer *leaf;
1490
1491         for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
1492                 leaf = path->nodes[i];
1493                 if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) {
1494                         path->slots[i]++;
1495                         *level = i;
1496                         return 0;
1497                 } else {
1498                         free_extent_buffer(path->nodes[*level]);
1499                         path->nodes[*level] = NULL;
1500                         BUG_ON(*level > wc->active_node);
1501                         if (*level == wc->active_node)
1502                                 leave_shared_node(root, wc, *level);
1503                         *level = i + 1;
1504                 }
1505         }
1506         return 1;
1507 }
1508
1509 static int check_root_dir(struct inode_record *rec)
1510 {
1511         struct inode_backref *backref;
1512         int ret = -1;
1513
1514         if (!rec->found_inode_item || rec->errors)
1515                 goto out;
1516         if (rec->nlink != 1 || rec->found_link != 0)
1517                 goto out;
1518         if (list_empty(&rec->backrefs))
1519                 goto out;
1520         backref = list_entry(rec->backrefs.next, struct inode_backref, list);
1521         if (!backref->found_inode_ref)
1522                 goto out;
1523         if (backref->index != 0 || backref->namelen != 2 ||
1524             memcmp(backref->name, "..", 2))
1525                 goto out;
1526         if (backref->found_dir_index || backref->found_dir_item)
1527                 goto out;
1528         ret = 0;
1529 out:
1530         return ret;
1531 }
1532
1533 static int repair_inode_isize(struct btrfs_trans_handle *trans,
1534                               struct btrfs_root *root, struct btrfs_path *path,
1535                               struct inode_record *rec)
1536 {
1537         struct btrfs_inode_item *ei;
1538         struct btrfs_key key;
1539         int ret;
1540
1541         key.objectid = rec->ino;
1542         key.type = BTRFS_INODE_ITEM_KEY;
1543         key.offset = (u64)-1;
1544
1545         ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
1546         if (ret < 0)
1547                 goto out;
1548         if (ret) {
1549                 if (!path->slots[0]) {
1550                         ret = -ENOENT;
1551                         goto out;
1552                 }
1553                 path->slots[0]--;
1554                 ret = 0;
1555         }
1556         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
1557         if (key.objectid != rec->ino) {
1558                 ret = -ENOENT;
1559                 goto out;
1560         }
1561
1562         ei = btrfs_item_ptr(path->nodes[0], path->slots[0],
1563                             struct btrfs_inode_item);
1564         btrfs_set_inode_size(path->nodes[0], ei, rec->found_size);
1565         btrfs_mark_buffer_dirty(path->nodes[0]);
1566         rec->errors &= ~I_ERR_DIR_ISIZE_WRONG;
1567         printf("reset isize for dir %Lu root %Lu\n", rec->ino,
1568                root->root_key.objectid);
1569 out:
1570         btrfs_release_path(path);
1571         return ret;
1572 }
1573
1574 static int repair_inode_orphan_item(struct btrfs_trans_handle *trans,
1575                                     struct btrfs_root *root,
1576                                     struct btrfs_path *path,
1577                                     struct inode_record *rec)
1578 {
1579         struct btrfs_key key;
1580         int ret;
1581
1582         key.objectid = BTRFS_ORPHAN_OBJECTID;
1583         key.type = BTRFS_ORPHAN_ITEM_KEY;
1584         key.offset = rec->ino;
1585
1586         ret = btrfs_insert_empty_item(trans, root, path, &key, 0);
1587         btrfs_release_path(path);
1588         if (!ret)
1589                 rec->errors &= ~I_ERR_NO_ORPHAN_ITEM;
1590         return ret;
1591 }
1592
1593 static int add_missing_dir_index(struct btrfs_root *root,
1594                                  struct cache_tree *inode_cache,
1595                                  struct inode_record *rec,
1596                                  struct inode_backref *backref)
1597 {
1598         struct btrfs_path *path;
1599         struct btrfs_trans_handle *trans;
1600         struct btrfs_dir_item *dir_item;
1601         struct extent_buffer *leaf;
1602         struct btrfs_key key;
1603         struct btrfs_disk_key disk_key;
1604         struct inode_record *dir_rec;
1605         unsigned long name_ptr;
1606         u32 data_size = sizeof(*dir_item) + backref->namelen;
1607         int ret;
1608
1609         path = btrfs_alloc_path();
1610         if (!path)
1611                 return -ENOMEM;
1612
1613         trans = btrfs_start_transaction(root, 1);
1614         if (IS_ERR(trans)) {
1615                 btrfs_free_path(path);
1616                 return PTR_ERR(trans);
1617         }
1618
1619         fprintf(stderr, "repairing missing dir index item for inode %llu\n",
1620                 (unsigned long long)rec->ino);
1621         key.objectid = backref->dir;
1622         key.type = BTRFS_DIR_INDEX_KEY;
1623         key.offset = backref->index;
1624
1625         ret = btrfs_insert_empty_item(trans, root, path, &key, data_size);
1626         BUG_ON(ret);
1627
1628         leaf = path->nodes[0];
1629         dir_item = btrfs_item_ptr(leaf, path->slots[0], struct btrfs_dir_item);
1630
1631         disk_key.objectid = cpu_to_le64(rec->ino);
1632         disk_key.type = BTRFS_INODE_ITEM_KEY;
1633         disk_key.offset = 0;
1634
1635         btrfs_set_dir_item_key(leaf, dir_item, &disk_key);
1636         btrfs_set_dir_type(leaf, dir_item, imode_to_type(rec->imode));
1637         btrfs_set_dir_data_len(leaf, dir_item, 0);
1638         btrfs_set_dir_name_len(leaf, dir_item, backref->namelen);
1639         name_ptr = (unsigned long)(dir_item + 1);
1640         write_extent_buffer(leaf, backref->name, name_ptr, backref->namelen);
1641         btrfs_mark_buffer_dirty(leaf);
1642         btrfs_free_path(path);
1643         btrfs_commit_transaction(trans, root);
1644
1645         backref->found_dir_index = 1;
1646         dir_rec = get_inode_rec(inode_cache, backref->dir, 0);
1647         if (!dir_rec)
1648                 return 0;
1649         dir_rec->found_size += backref->namelen;
1650         if (dir_rec->found_size == dir_rec->isize &&
1651             (dir_rec->errors & I_ERR_DIR_ISIZE_WRONG))
1652                 dir_rec->errors &= ~I_ERR_DIR_ISIZE_WRONG;
1653         if (dir_rec->found_size != dir_rec->isize)
1654                 dir_rec->errors |= I_ERR_DIR_ISIZE_WRONG;
1655
1656         return 0;
1657 }
1658
1659 static int delete_dir_index(struct btrfs_root *root,
1660                             struct cache_tree *inode_cache,
1661                             struct inode_record *rec,
1662                             struct inode_backref *backref)
1663 {
1664         struct btrfs_trans_handle *trans;
1665         struct btrfs_dir_item *di;
1666         struct btrfs_path *path;
1667         int ret = 0;
1668
1669         path = btrfs_alloc_path();
1670         if (!path)
1671                 return -ENOMEM;
1672
1673         trans = btrfs_start_transaction(root, 1);
1674         if (IS_ERR(trans)) {
1675                 btrfs_free_path(path);
1676                 return PTR_ERR(trans);
1677         }
1678
1679
1680         fprintf(stderr, "Deleting bad dir index [%llu,%u,%llu] root %llu\n",
1681                 (unsigned long long)backref->dir,
1682                 BTRFS_DIR_INDEX_KEY, (unsigned long long)backref->index,
1683                 (unsigned long long)root->objectid);
1684
1685         di = btrfs_lookup_dir_index(trans, root, path, backref->dir,
1686                                     backref->name, backref->namelen,
1687                                     backref->index, -1);
1688         if (IS_ERR(di)) {
1689                 ret = PTR_ERR(di);
1690                 btrfs_free_path(path);
1691                 btrfs_commit_transaction(trans, root);
1692                 if (ret == -ENOENT)
1693                         return 0;
1694                 return ret;
1695         }
1696
1697         if (!di)
1698                 ret = btrfs_del_item(trans, root, path);
1699         else
1700                 ret = btrfs_delete_one_dir_name(trans, root, path, di);
1701         BUG_ON(ret);
1702         btrfs_free_path(path);
1703         btrfs_commit_transaction(trans, root);
1704         return ret;
1705 }
1706
1707 static int repair_inode_backrefs(struct btrfs_root *root,
1708                                  struct inode_record *rec,
1709                                  struct cache_tree *inode_cache,
1710                                  int delete)
1711 {
1712         struct inode_backref *tmp, *backref;
1713         u64 root_dirid = btrfs_root_dirid(&root->root_item);
1714         int ret = 0;
1715         int repaired = 0;
1716
1717         list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
1718                 /* Index 0 for root dir's are special, don't mess with it */
1719                 if (rec->ino == root_dirid && backref->index == 0)
1720                         continue;
1721
1722                 if (delete && backref->found_dir_index &&
1723                     !backref->found_inode_ref) {
1724                         ret = delete_dir_index(root, inode_cache, rec, backref);
1725                         if (ret)
1726                                 break;
1727                         repaired++;
1728                         list_del(&backref->list);
1729                         free(backref);
1730                 }
1731
1732                 if (!delete && !backref->found_dir_index &&
1733                     backref->found_dir_item && backref->found_inode_ref) {
1734                         ret = add_missing_dir_index(root, inode_cache, rec,
1735                                                     backref);
1736                         if (ret)
1737                                 break;
1738                         repaired++;
1739                         if (backref->found_dir_item &&
1740                             backref->found_dir_index &&
1741                             backref->found_dir_index) {
1742                                 if (!backref->errors &&
1743                                     backref->found_inode_ref) {
1744                                         list_del(&backref->list);
1745                                         free(backref);
1746                                 }
1747                         }
1748                 }
1749
1750         }
1751         return ret ? ret : repaired;
1752 }
1753
1754 static int try_repair_inode(struct btrfs_root *root, struct inode_record *rec)
1755 {
1756         struct btrfs_trans_handle *trans;
1757         struct btrfs_path *path;
1758         int ret = 0;
1759
1760         if (!(rec->errors & (I_ERR_DIR_ISIZE_WRONG | I_ERR_NO_ORPHAN_ITEM)))
1761                 return rec->errors;
1762
1763         path = btrfs_alloc_path();
1764         if (!path)
1765                 return -ENOMEM;
1766
1767         trans = btrfs_start_transaction(root, 1);
1768         if (IS_ERR(trans)) {
1769                 btrfs_free_path(path);
1770                 return PTR_ERR(trans);
1771         }
1772
1773         if (rec->errors & I_ERR_DIR_ISIZE_WRONG)
1774                 ret = repair_inode_isize(trans, root, path, rec);
1775         if (!ret && rec->errors & I_ERR_NO_ORPHAN_ITEM)
1776                 ret = repair_inode_orphan_item(trans, root, path, rec);
1777         btrfs_commit_transaction(trans, root);
1778         btrfs_free_path(path);
1779         return ret;
1780 }
1781
1782 static int check_inode_recs(struct btrfs_root *root,
1783                             struct cache_tree *inode_cache)
1784 {
1785         struct cache_extent *cache;
1786         struct ptr_node *node;
1787         struct inode_record *rec;
1788         struct inode_backref *backref;
1789         int stage = 0;
1790         int ret;
1791         int err = 0;
1792         u64 error = 0;
1793         u64 root_dirid = btrfs_root_dirid(&root->root_item);
1794
1795         if (btrfs_root_refs(&root->root_item) == 0) {
1796                 if (!cache_tree_empty(inode_cache))
1797                         fprintf(stderr, "warning line %d\n", __LINE__);
1798                 return 0;
1799         }
1800
1801         /*
1802          * We need to repair backrefs first because we could change some of the
1803          * errors in the inode recs.
1804          *
1805          * We also need to go through and delete invalid backrefs first and then
1806          * add the correct ones second.  We do this because we may get EEXIST
1807          * when adding back the correct index because we hadn't yet deleted the
1808          * invalid index.
1809          *
1810          * For example, if we were missing a dir index then the directories
1811          * isize would be wrong, so if we fixed the isize to what we thought it
1812          * would be and then fixed the backref we'd still have a invalid fs, so
1813          * we need to add back the dir index and then check to see if the isize
1814          * is still wrong.
1815          */
1816         while (stage < 3) {
1817                 stage++;
1818                 if (stage == 3 && !err)
1819                         break;
1820
1821                 cache = search_cache_extent(inode_cache, 0);
1822                 while (repair && cache) {
1823                         node = container_of(cache, struct ptr_node, cache);
1824                         rec = node->data;
1825                         cache = next_cache_extent(cache);
1826
1827                         /* Need to free everything up and rescan */
1828                         if (stage == 3) {
1829                                 remove_cache_extent(inode_cache, &node->cache);
1830                                 free(node);
1831                                 free_inode_rec(rec);
1832                                 continue;
1833                         }
1834
1835                         if (list_empty(&rec->backrefs))
1836                                 continue;
1837
1838                         ret = repair_inode_backrefs(root, rec, inode_cache,
1839                                                     stage == 1);
1840                         if (ret < 0) {
1841                                 err = ret;
1842                                 stage = 2;
1843                                 break;
1844                         } if (ret > 0) {
1845                                 err = -EAGAIN;
1846                         }
1847                 }
1848         }
1849         if (err)
1850                 return err;
1851
1852         rec = get_inode_rec(inode_cache, root_dirid, 0);
1853         if (rec) {
1854                 ret = check_root_dir(rec);
1855                 if (ret) {
1856                         fprintf(stderr, "root %llu root dir %llu error\n",
1857                                 (unsigned long long)root->root_key.objectid,
1858                                 (unsigned long long)root_dirid);
1859                         error++;
1860                 }
1861         } else {
1862                 fprintf(stderr, "root %llu root dir %llu not found\n",
1863                         (unsigned long long)root->root_key.objectid,
1864                         (unsigned long long)root_dirid);
1865         }
1866
1867         while (1) {
1868                 cache = search_cache_extent(inode_cache, 0);
1869                 if (!cache)
1870                         break;
1871                 node = container_of(cache, struct ptr_node, cache);
1872                 rec = node->data;
1873                 remove_cache_extent(inode_cache, &node->cache);
1874                 free(node);
1875                 if (rec->ino == root_dirid ||
1876                     rec->ino == BTRFS_ORPHAN_OBJECTID) {
1877                         free_inode_rec(rec);
1878                         continue;
1879                 }
1880
1881                 if (rec->errors & I_ERR_NO_ORPHAN_ITEM) {
1882                         ret = check_orphan_item(root, rec->ino);
1883                         if (ret == 0)
1884                                 rec->errors &= ~I_ERR_NO_ORPHAN_ITEM;
1885                         if (can_free_inode_rec(rec)) {
1886                                 free_inode_rec(rec);
1887                                 continue;
1888                         }
1889                 }
1890
1891                 if (repair) {
1892                         ret = try_repair_inode(root, rec);
1893                         if (ret == 0 && can_free_inode_rec(rec)) {
1894                                 free_inode_rec(rec);
1895                                 continue;
1896                         }
1897                         ret = 0;
1898                 }
1899
1900                 error++;
1901                 if (!rec->found_inode_item)
1902                         rec->errors |= I_ERR_NO_INODE_ITEM;
1903                 if (rec->found_link != rec->nlink)
1904                         rec->errors |= I_ERR_LINK_COUNT_WRONG;
1905                 print_inode_error(root, rec);
1906                 list_for_each_entry(backref, &rec->backrefs, list) {
1907                         if (!backref->found_dir_item)
1908                                 backref->errors |= REF_ERR_NO_DIR_ITEM;
1909                         if (!backref->found_dir_index)
1910                                 backref->errors |= REF_ERR_NO_DIR_INDEX;
1911                         if (!backref->found_inode_ref)
1912                                 backref->errors |= REF_ERR_NO_INODE_REF;
1913                         fprintf(stderr, "\tunresolved ref dir %llu index %llu"
1914                                 " namelen %u name %s filetype %d errors %x",
1915                                 (unsigned long long)backref->dir,
1916                                 (unsigned long long)backref->index,
1917                                 backref->namelen, backref->name,
1918                                 backref->filetype, backref->errors);
1919                         print_ref_error(backref->errors);
1920                 }
1921                 free_inode_rec(rec);
1922         }
1923         return (error > 0) ? -1 : 0;
1924 }
1925
1926 static struct root_record *get_root_rec(struct cache_tree *root_cache,
1927                                         u64 objectid)
1928 {
1929         struct cache_extent *cache;
1930         struct root_record *rec = NULL;
1931         int ret;
1932
1933         cache = lookup_cache_extent(root_cache, objectid, 1);
1934         if (cache) {
1935                 rec = container_of(cache, struct root_record, cache);
1936         } else {
1937                 rec = calloc(1, sizeof(*rec));
1938                 rec->objectid = objectid;
1939                 INIT_LIST_HEAD(&rec->backrefs);
1940                 rec->cache.start = objectid;
1941                 rec->cache.size = 1;
1942
1943                 ret = insert_cache_extent(root_cache, &rec->cache);
1944                 BUG_ON(ret);
1945         }
1946         return rec;
1947 }
1948
1949 static struct root_backref *get_root_backref(struct root_record *rec,
1950                                              u64 ref_root, u64 dir, u64 index,
1951                                              const char *name, int namelen)
1952 {
1953         struct root_backref *backref;
1954
1955         list_for_each_entry(backref, &rec->backrefs, list) {
1956                 if (backref->ref_root != ref_root || backref->dir != dir ||
1957                     backref->namelen != namelen)
1958                         continue;
1959                 if (memcmp(name, backref->name, namelen))
1960                         continue;
1961                 return backref;
1962         }
1963
1964         backref = malloc(sizeof(*backref) + namelen + 1);
1965         memset(backref, 0, sizeof(*backref));
1966         backref->ref_root = ref_root;
1967         backref->dir = dir;
1968         backref->index = index;
1969         backref->namelen = namelen;
1970         memcpy(backref->name, name, namelen);
1971         backref->name[namelen] = '\0';
1972         list_add_tail(&backref->list, &rec->backrefs);
1973         return backref;
1974 }
1975
1976 static void free_root_record(struct cache_extent *cache)
1977 {
1978         struct root_record *rec;
1979         struct root_backref *backref;
1980
1981         rec = container_of(cache, struct root_record, cache);
1982         while (!list_empty(&rec->backrefs)) {
1983                 backref = list_entry(rec->backrefs.next,
1984                                      struct root_backref, list);
1985                 list_del(&backref->list);
1986                 free(backref);
1987         }
1988
1989         kfree(rec);
1990 }
1991
1992 FREE_EXTENT_CACHE_BASED_TREE(root_recs, free_root_record);
1993
1994 static int add_root_backref(struct cache_tree *root_cache,
1995                             u64 root_id, u64 ref_root, u64 dir, u64 index,
1996                             const char *name, int namelen,
1997                             int item_type, int errors)
1998 {
1999         struct root_record *rec;
2000         struct root_backref *backref;
2001
2002         rec = get_root_rec(root_cache, root_id);
2003         backref = get_root_backref(rec, ref_root, dir, index, name, namelen);
2004
2005         backref->errors |= errors;
2006
2007         if (item_type != BTRFS_DIR_ITEM_KEY) {
2008                 if (backref->found_dir_index || backref->found_back_ref ||
2009                     backref->found_forward_ref) {
2010                         if (backref->index != index)
2011                                 backref->errors |= REF_ERR_INDEX_UNMATCH;
2012                 } else {
2013                         backref->index = index;
2014                 }
2015         }
2016
2017         if (item_type == BTRFS_DIR_ITEM_KEY) {
2018                 if (backref->found_forward_ref)
2019                         rec->found_ref++;
2020                 backref->found_dir_item = 1;
2021         } else if (item_type == BTRFS_DIR_INDEX_KEY) {
2022                 backref->found_dir_index = 1;
2023         } else if (item_type == BTRFS_ROOT_REF_KEY) {
2024                 if (backref->found_forward_ref)
2025                         backref->errors |= REF_ERR_DUP_ROOT_REF;
2026                 else if (backref->found_dir_item)
2027                         rec->found_ref++;
2028                 backref->found_forward_ref = 1;
2029         } else if (item_type == BTRFS_ROOT_BACKREF_KEY) {
2030                 if (backref->found_back_ref)
2031                         backref->errors |= REF_ERR_DUP_ROOT_BACKREF;
2032                 backref->found_back_ref = 1;
2033         } else {
2034                 BUG_ON(1);
2035         }
2036
2037         if (backref->found_forward_ref && backref->found_dir_item)
2038                 backref->reachable = 1;
2039         return 0;
2040 }
2041
2042 static int merge_root_recs(struct btrfs_root *root,
2043                            struct cache_tree *src_cache,
2044                            struct cache_tree *dst_cache)
2045 {
2046         struct cache_extent *cache;
2047         struct ptr_node *node;
2048         struct inode_record *rec;
2049         struct inode_backref *backref;
2050         int ret = 0;
2051
2052         if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
2053                 free_inode_recs_tree(src_cache);
2054                 return 0;
2055         }
2056
2057         while (1) {
2058                 cache = search_cache_extent(src_cache, 0);
2059                 if (!cache)
2060                         break;
2061                 node = container_of(cache, struct ptr_node, cache);
2062                 rec = node->data;
2063                 remove_cache_extent(src_cache, &node->cache);
2064                 free(node);
2065
2066                 ret = is_child_root(root, root->objectid, rec->ino);
2067                 if (ret < 0)
2068                         break;
2069                 else if (ret == 0)
2070                         goto skip;
2071
2072                 list_for_each_entry(backref, &rec->backrefs, list) {
2073                         BUG_ON(backref->found_inode_ref);
2074                         if (backref->found_dir_item)
2075                                 add_root_backref(dst_cache, rec->ino,
2076                                         root->root_key.objectid, backref->dir,
2077                                         backref->index, backref->name,
2078                                         backref->namelen, BTRFS_DIR_ITEM_KEY,
2079                                         backref->errors);
2080                         if (backref->found_dir_index)
2081                                 add_root_backref(dst_cache, rec->ino,
2082                                         root->root_key.objectid, backref->dir,
2083                                         backref->index, backref->name,
2084                                         backref->namelen, BTRFS_DIR_INDEX_KEY,
2085                                         backref->errors);
2086                 }
2087 skip:
2088                 free_inode_rec(rec);
2089         }
2090         if (ret < 0)
2091                 return ret;
2092         return 0;
2093 }
2094
2095 static int check_root_refs(struct btrfs_root *root,
2096                            struct cache_tree *root_cache)
2097 {
2098         struct root_record *rec;
2099         struct root_record *ref_root;
2100         struct root_backref *backref;
2101         struct cache_extent *cache;
2102         int loop = 1;
2103         int ret;
2104         int error;
2105         int errors = 0;
2106
2107         rec = get_root_rec(root_cache, BTRFS_FS_TREE_OBJECTID);
2108         rec->found_ref = 1;
2109
2110         /* fixme: this can not detect circular references */
2111         while (loop) {
2112                 loop = 0;
2113                 cache = search_cache_extent(root_cache, 0);
2114                 while (1) {
2115                         if (!cache)
2116                                 break;
2117                         rec = container_of(cache, struct root_record, cache);
2118                         cache = next_cache_extent(cache);
2119
2120                         if (rec->found_ref == 0)
2121                                 continue;
2122
2123                         list_for_each_entry(backref, &rec->backrefs, list) {
2124                                 if (!backref->reachable)
2125                                         continue;
2126
2127                                 ref_root = get_root_rec(root_cache,
2128                                                         backref->ref_root);
2129                                 if (ref_root->found_ref > 0)
2130                                         continue;
2131
2132                                 backref->reachable = 0;
2133                                 rec->found_ref--;
2134                                 if (rec->found_ref == 0)
2135                                         loop = 1;
2136                         }
2137                 }
2138         }
2139
2140         cache = search_cache_extent(root_cache, 0);
2141         while (1) {
2142                 if (!cache)
2143                         break;
2144                 rec = container_of(cache, struct root_record, cache);
2145                 cache = next_cache_extent(cache);
2146
2147                 if (rec->found_ref == 0 &&
2148                     rec->objectid >= BTRFS_FIRST_FREE_OBJECTID &&
2149                     rec->objectid <= BTRFS_LAST_FREE_OBJECTID) {
2150                         ret = check_orphan_item(root->fs_info->tree_root,
2151                                                 rec->objectid);
2152                         if (ret == 0)
2153                                 continue;
2154
2155                         /*
2156                          * If we don't have a root item then we likely just have
2157                          * a dir item in a snapshot for this root but no actual
2158                          * ref key or anything so it's meaningless.
2159                          */
2160                         if (!rec->found_root_item)
2161                                 continue;
2162                         errors++;
2163                         fprintf(stderr, "fs tree %llu not referenced\n",
2164                                 (unsigned long long)rec->objectid);
2165                 }
2166
2167                 error = 0;
2168                 if (rec->found_ref > 0 && !rec->found_root_item)
2169                         error = 1;
2170                 list_for_each_entry(backref, &rec->backrefs, list) {
2171                         if (!backref->found_dir_item)
2172                                 backref->errors |= REF_ERR_NO_DIR_ITEM;
2173                         if (!backref->found_dir_index)
2174                                 backref->errors |= REF_ERR_NO_DIR_INDEX;
2175                         if (!backref->found_back_ref)
2176                                 backref->errors |= REF_ERR_NO_ROOT_BACKREF;
2177                         if (!backref->found_forward_ref)
2178                                 backref->errors |= REF_ERR_NO_ROOT_REF;
2179                         if (backref->reachable && backref->errors)
2180                                 error = 1;
2181                 }
2182                 if (!error)
2183                         continue;
2184
2185                 errors++;
2186                 fprintf(stderr, "fs tree %llu refs %u %s\n",
2187                         (unsigned long long)rec->objectid, rec->found_ref,
2188                          rec->found_root_item ? "" : "not found");
2189
2190                 list_for_each_entry(backref, &rec->backrefs, list) {
2191                         if (!backref->reachable)
2192                                 continue;
2193                         if (!backref->errors && rec->found_root_item)
2194                                 continue;
2195                         fprintf(stderr, "\tunresolved ref root %llu dir %llu"
2196                                 " index %llu namelen %u name %s errors %x\n",
2197                                 (unsigned long long)backref->ref_root,
2198                                 (unsigned long long)backref->dir,
2199                                 (unsigned long long)backref->index,
2200                                 backref->namelen, backref->name,
2201                                 backref->errors);
2202                         print_ref_error(backref->errors);
2203                 }
2204         }
2205         return errors > 0 ? 1 : 0;
2206 }
2207
2208 static int process_root_ref(struct extent_buffer *eb, int slot,
2209                             struct btrfs_key *key,
2210                             struct cache_tree *root_cache)
2211 {
2212         u64 dirid;
2213         u64 index;
2214         u32 len;
2215         u32 name_len;
2216         struct btrfs_root_ref *ref;
2217         char namebuf[BTRFS_NAME_LEN];
2218         int error;
2219
2220         ref = btrfs_item_ptr(eb, slot, struct btrfs_root_ref);
2221
2222         dirid = btrfs_root_ref_dirid(eb, ref);
2223         index = btrfs_root_ref_sequence(eb, ref);
2224         name_len = btrfs_root_ref_name_len(eb, ref);
2225
2226         if (name_len <= BTRFS_NAME_LEN) {
2227                 len = name_len;
2228                 error = 0;
2229         } else {
2230                 len = BTRFS_NAME_LEN;
2231                 error = REF_ERR_NAME_TOO_LONG;
2232         }
2233         read_extent_buffer(eb, namebuf, (unsigned long)(ref + 1), len);
2234
2235         if (key->type == BTRFS_ROOT_REF_KEY) {
2236                 add_root_backref(root_cache, key->offset, key->objectid, dirid,
2237                                  index, namebuf, len, key->type, error);
2238         } else {
2239                 add_root_backref(root_cache, key->objectid, key->offset, dirid,
2240                                  index, namebuf, len, key->type, error);
2241         }
2242         return 0;
2243 }
2244
2245 static int check_fs_root(struct btrfs_root *root,
2246                          struct cache_tree *root_cache,
2247                          struct walk_control *wc)
2248 {
2249         int ret = 0;
2250         int err = 0;
2251         int wret;
2252         int level;
2253         struct btrfs_path path;
2254         struct shared_node root_node;
2255         struct root_record *rec;
2256         struct btrfs_root_item *root_item = &root->root_item;
2257
2258         if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
2259                 rec = get_root_rec(root_cache, root->root_key.objectid);
2260                 if (btrfs_root_refs(root_item) > 0)
2261                         rec->found_root_item = 1;
2262         }
2263
2264         btrfs_init_path(&path);
2265         memset(&root_node, 0, sizeof(root_node));
2266         cache_tree_init(&root_node.root_cache);
2267         cache_tree_init(&root_node.inode_cache);
2268
2269         level = btrfs_header_level(root->node);
2270         memset(wc->nodes, 0, sizeof(wc->nodes));
2271         wc->nodes[level] = &root_node;
2272         wc->active_node = level;
2273         wc->root_level = level;
2274
2275         if (btrfs_root_refs(root_item) > 0 ||
2276             btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
2277                 path.nodes[level] = root->node;
2278                 extent_buffer_get(root->node);
2279                 path.slots[level] = 0;
2280         } else {
2281                 struct btrfs_key key;
2282                 struct btrfs_disk_key found_key;
2283
2284                 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
2285                 level = root_item->drop_level;
2286                 path.lowest_level = level;
2287                 wret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
2288                 if (wret < 0)
2289                         goto skip_walking;
2290                 btrfs_node_key(path.nodes[level], &found_key,
2291                                 path.slots[level]);
2292                 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
2293                                         sizeof(found_key)));
2294         }
2295
2296         while (1) {
2297                 wret = walk_down_tree(root, &path, wc, &level);
2298                 if (wret < 0)
2299                         ret = wret;
2300                 if (wret != 0)
2301                         break;
2302
2303                 wret = walk_up_tree(root, &path, wc, &level);
2304                 if (wret < 0)
2305                         ret = wret;
2306                 if (wret != 0)
2307                         break;
2308         }
2309 skip_walking:
2310         btrfs_release_path(&path);
2311
2312         err = merge_root_recs(root, &root_node.root_cache, root_cache);
2313         if (err < 0)
2314                 ret = err;
2315
2316         if (root_node.current) {
2317                 root_node.current->checked = 1;
2318                 maybe_free_inode_rec(&root_node.inode_cache,
2319                                 root_node.current);
2320         }
2321
2322         err = check_inode_recs(root, &root_node.inode_cache);
2323         if (!ret)
2324                 ret = err;
2325         return ret;
2326 }
2327
2328 static int fs_root_objectid(u64 objectid)
2329 {
2330         if (objectid == BTRFS_TREE_RELOC_OBJECTID ||
2331             objectid == BTRFS_DATA_RELOC_TREE_OBJECTID)
2332                 return 1;
2333         return is_fstree(objectid);
2334 }
2335
2336 static int check_fs_roots(struct btrfs_root *root,
2337                           struct cache_tree *root_cache)
2338 {
2339         struct btrfs_path path;
2340         struct btrfs_key key;
2341         struct walk_control wc;
2342         struct extent_buffer *leaf, *tree_node;
2343         struct btrfs_root *tmp_root;
2344         struct btrfs_root *tree_root = root->fs_info->tree_root;
2345         int ret;
2346         int err = 0;
2347
2348         /*
2349          * Just in case we made any changes to the extent tree that weren't
2350          * reflected into the free space cache yet.
2351          */
2352         if (repair)
2353                 reset_cached_block_groups(root->fs_info);
2354         memset(&wc, 0, sizeof(wc));
2355         cache_tree_init(&wc.shared);
2356         btrfs_init_path(&path);
2357
2358 again:
2359         key.offset = 0;
2360         key.objectid = 0;
2361         key.type = BTRFS_ROOT_ITEM_KEY;
2362         ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0);
2363         if (ret < 0) {
2364                 err = 1;
2365                 goto out;
2366         }
2367         tree_node = tree_root->node;
2368         while (1) {
2369                 if (tree_node != tree_root->node) {
2370                         free_root_recs_tree(root_cache);
2371                         btrfs_release_path(&path);
2372                         goto again;
2373                 }
2374                 leaf = path.nodes[0];
2375                 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
2376                         ret = btrfs_next_leaf(tree_root, &path);
2377                         if (ret) {
2378                                 if (ret < 0)
2379                                         err = 1;
2380                                 break;
2381                         }
2382                         leaf = path.nodes[0];
2383                 }
2384                 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
2385                 if (key.type == BTRFS_ROOT_ITEM_KEY &&
2386                     fs_root_objectid(key.objectid)) {
2387                         if (key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
2388                                 tmp_root = btrfs_read_fs_root_no_cache(
2389                                                 root->fs_info, &key);
2390                         } else {
2391                                 key.offset = (u64)-1;
2392                                 tmp_root = btrfs_read_fs_root(
2393                                                 root->fs_info, &key);
2394                         }
2395                         if (IS_ERR(tmp_root)) {
2396                                 err = 1;
2397                                 goto next;
2398                         }
2399                         ret = check_fs_root(tmp_root, root_cache, &wc);
2400                         if (ret == -EAGAIN) {
2401                                 free_root_recs_tree(root_cache);
2402                                 btrfs_release_path(&path);
2403                                 goto again;
2404                         }
2405                         if (ret)
2406                                 err = 1;
2407                         if (key.objectid == BTRFS_TREE_RELOC_OBJECTID)
2408                                 btrfs_free_fs_root(tmp_root);
2409                 } else if (key.type == BTRFS_ROOT_REF_KEY ||
2410                            key.type == BTRFS_ROOT_BACKREF_KEY) {
2411                         process_root_ref(leaf, path.slots[0], &key,
2412                                          root_cache);
2413                 }
2414 next:
2415                 path.slots[0]++;
2416         }
2417 out:
2418         btrfs_release_path(&path);
2419         if (err)
2420                 free_extent_cache_tree(&wc.shared);
2421         if (!cache_tree_empty(&wc.shared))
2422                 fprintf(stderr, "warning line %d\n", __LINE__);
2423
2424         return err;
2425 }
2426
2427 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
2428 {
2429         struct list_head *cur = rec->backrefs.next;
2430         struct extent_backref *back;
2431         struct tree_backref *tback;
2432         struct data_backref *dback;
2433         u64 found = 0;
2434         int err = 0;
2435
2436         while(cur != &rec->backrefs) {
2437                 back = list_entry(cur, struct extent_backref, list);
2438                 cur = cur->next;
2439                 if (!back->found_extent_tree) {
2440                         err = 1;
2441                         if (!print_errs)
2442                                 goto out;
2443                         if (back->is_data) {
2444                                 dback = (struct data_backref *)back;
2445                                 fprintf(stderr, "Backref %llu %s %llu"
2446                                         " owner %llu offset %llu num_refs %lu"
2447                                         " not found in extent tree\n",
2448                                         (unsigned long long)rec->start,
2449                                         back->full_backref ?
2450                                         "parent" : "root",
2451                                         back->full_backref ?
2452                                         (unsigned long long)dback->parent:
2453                                         (unsigned long long)dback->root,
2454                                         (unsigned long long)dback->owner,
2455                                         (unsigned long long)dback->offset,
2456                                         (unsigned long)dback->num_refs);
2457                         } else {
2458                                 tback = (struct tree_backref *)back;
2459                                 fprintf(stderr, "Backref %llu parent %llu"
2460                                         " root %llu not found in extent tree\n",
2461                                         (unsigned long long)rec->start,
2462                                         (unsigned long long)tback->parent,
2463                                         (unsigned long long)tback->root);
2464                         }
2465                 }
2466                 if (!back->is_data && !back->found_ref) {
2467                         err = 1;
2468                         if (!print_errs)
2469                                 goto out;
2470                         tback = (struct tree_backref *)back;
2471                         fprintf(stderr, "Backref %llu %s %llu not referenced back %p\n",
2472                                 (unsigned long long)rec->start,
2473                                 back->full_backref ? "parent" : "root",
2474                                 back->full_backref ?
2475                                 (unsigned long long)tback->parent :
2476                                 (unsigned long long)tback->root, back);
2477                 }
2478                 if (back->is_data) {
2479                         dback = (struct data_backref *)back;
2480                         if (dback->found_ref != dback->num_refs) {
2481                                 err = 1;
2482                                 if (!print_errs)
2483                                         goto out;
2484                                 fprintf(stderr, "Incorrect local backref count"
2485                                         " on %llu %s %llu owner %llu"
2486                                         " offset %llu found %u wanted %u back %p\n",
2487                                         (unsigned long long)rec->start,
2488                                         back->full_backref ?
2489                                         "parent" : "root",
2490                                         back->full_backref ?
2491                                         (unsigned long long)dback->parent:
2492                                         (unsigned long long)dback->root,
2493                                         (unsigned long long)dback->owner,
2494                                         (unsigned long long)dback->offset,
2495                                         dback->found_ref, dback->num_refs, back);
2496                         }
2497                         if (dback->disk_bytenr != rec->start) {
2498                                 err = 1;
2499                                 if (!print_errs)
2500                                         goto out;
2501                                 fprintf(stderr, "Backref disk bytenr does not"
2502                                         " match extent record, bytenr=%llu, "
2503                                         "ref bytenr=%llu\n",
2504                                         (unsigned long long)rec->start,
2505                                         (unsigned long long)dback->disk_bytenr);
2506                         }
2507
2508                         if (dback->bytes != rec->nr) {
2509                                 err = 1;
2510                                 if (!print_errs)
2511                                         goto out;
2512                                 fprintf(stderr, "Backref bytes do not match "
2513                                         "extent backref, bytenr=%llu, ref "
2514                                         "bytes=%llu, backref bytes=%llu\n",
2515                                         (unsigned long long)rec->start,
2516                                         (unsigned long long)rec->nr,
2517                                         (unsigned long long)dback->bytes);
2518                         }
2519                 }
2520                 if (!back->is_data) {
2521                         found += 1;
2522                 } else {
2523                         dback = (struct data_backref *)back;
2524                         found += dback->found_ref;
2525                 }
2526         }
2527         if (found != rec->refs) {
2528                 err = 1;
2529                 if (!print_errs)
2530                         goto out;
2531                 fprintf(stderr, "Incorrect global backref count "
2532                         "on %llu found %llu wanted %llu\n",
2533                         (unsigned long long)rec->start,
2534                         (unsigned long long)found,
2535                         (unsigned long long)rec->refs);
2536         }
2537 out:
2538         return err;
2539 }
2540
2541 static int free_all_extent_backrefs(struct extent_record *rec)
2542 {
2543         struct extent_backref *back;
2544         struct list_head *cur;
2545         while (!list_empty(&rec->backrefs)) {
2546                 cur = rec->backrefs.next;
2547                 back = list_entry(cur, struct extent_backref, list);
2548                 list_del(cur);
2549                 free(back);
2550         }
2551         return 0;
2552 }
2553
2554 static void free_extent_record_cache(struct btrfs_fs_info *fs_info,
2555                                      struct cache_tree *extent_cache)
2556 {
2557         struct cache_extent *cache;
2558         struct extent_record *rec;
2559
2560         while (1) {
2561                 cache = first_cache_extent(extent_cache);
2562                 if (!cache)
2563                         break;
2564                 rec = container_of(cache, struct extent_record, cache);
2565                 btrfs_unpin_extent(fs_info, rec->start, rec->max_size);
2566                 remove_cache_extent(extent_cache, cache);
2567                 free_all_extent_backrefs(rec);
2568                 free(rec);
2569         }
2570 }
2571
2572 static int maybe_free_extent_rec(struct cache_tree *extent_cache,
2573                                  struct extent_record *rec)
2574 {
2575         if (rec->content_checked && rec->owner_ref_checked &&
2576             rec->extent_item_refs == rec->refs && rec->refs > 0 &&
2577             rec->num_duplicates == 0 && !all_backpointers_checked(rec, 0)) {
2578                 remove_cache_extent(extent_cache, &rec->cache);
2579                 free_all_extent_backrefs(rec);
2580                 list_del_init(&rec->list);
2581                 free(rec);
2582         }
2583         return 0;
2584 }
2585
2586 static int check_owner_ref(struct btrfs_root *root,
2587                             struct extent_record *rec,
2588                             struct extent_buffer *buf)
2589 {
2590         struct extent_backref *node;
2591         struct tree_backref *back;
2592         struct btrfs_root *ref_root;
2593         struct btrfs_key key;
2594         struct btrfs_path path;
2595         struct extent_buffer *parent;
2596         int level;
2597         int found = 0;
2598         int ret;
2599
2600         list_for_each_entry(node, &rec->backrefs, list) {
2601                 if (node->is_data)
2602                         continue;
2603                 if (!node->found_ref)
2604                         continue;
2605                 if (node->full_backref)
2606                         continue;
2607                 back = (struct tree_backref *)node;
2608                 if (btrfs_header_owner(buf) == back->root)
2609                         return 0;
2610         }
2611         BUG_ON(rec->is_root);
2612
2613         /* try to find the block by search corresponding fs tree */
2614         key.objectid = btrfs_header_owner(buf);
2615         key.type = BTRFS_ROOT_ITEM_KEY;
2616         key.offset = (u64)-1;
2617
2618         ref_root = btrfs_read_fs_root(root->fs_info, &key);
2619         if (IS_ERR(ref_root))
2620                 return 1;
2621
2622         level = btrfs_header_level(buf);
2623         if (level == 0)
2624                 btrfs_item_key_to_cpu(buf, &key, 0);
2625         else
2626                 btrfs_node_key_to_cpu(buf, &key, 0);
2627
2628         btrfs_init_path(&path);
2629         path.lowest_level = level + 1;
2630         ret = btrfs_search_slot(NULL, ref_root, &key, &path, 0, 0);
2631         if (ret < 0)
2632                 return 0;
2633
2634         parent = path.nodes[level + 1];
2635         if (parent && buf->start == btrfs_node_blockptr(parent,
2636                                                         path.slots[level + 1]))
2637                 found = 1;
2638
2639         btrfs_release_path(&path);
2640         return found ? 0 : 1;
2641 }
2642
2643 static int is_extent_tree_record(struct extent_record *rec)
2644 {
2645         struct list_head *cur = rec->backrefs.next;
2646         struct extent_backref *node;
2647         struct tree_backref *back;
2648         int is_extent = 0;
2649
2650         while(cur != &rec->backrefs) {
2651                 node = list_entry(cur, struct extent_backref, list);
2652                 cur = cur->next;
2653                 if (node->is_data)
2654                         return 0;
2655                 back = (struct tree_backref *)node;
2656                 if (node->full_backref)
2657                         return 0;
2658                 if (back->root == BTRFS_EXTENT_TREE_OBJECTID)
2659                         is_extent = 1;
2660         }
2661         return is_extent;
2662 }
2663
2664
2665 static int record_bad_block_io(struct btrfs_fs_info *info,
2666                                struct cache_tree *extent_cache,
2667                                u64 start, u64 len)
2668 {
2669         struct extent_record *rec;
2670         struct cache_extent *cache;
2671         struct btrfs_key key;
2672
2673         cache = lookup_cache_extent(extent_cache, start, len);
2674         if (!cache)
2675                 return 0;
2676
2677         rec = container_of(cache, struct extent_record, cache);
2678         if (!is_extent_tree_record(rec))
2679                 return 0;
2680
2681         btrfs_disk_key_to_cpu(&key, &rec->parent_key);
2682         return btrfs_add_corrupt_extent_record(info, &key, start, len, 0);
2683 }
2684
2685 static int swap_values(struct btrfs_root *root, struct btrfs_path *path,
2686                        struct extent_buffer *buf, int slot)
2687 {
2688         if (btrfs_header_level(buf)) {
2689                 struct btrfs_key_ptr ptr1, ptr2;
2690
2691                 read_extent_buffer(buf, &ptr1, btrfs_node_key_ptr_offset(slot),
2692                                    sizeof(struct btrfs_key_ptr));
2693                 read_extent_buffer(buf, &ptr2,
2694                                    btrfs_node_key_ptr_offset(slot + 1),
2695                                    sizeof(struct btrfs_key_ptr));
2696                 write_extent_buffer(buf, &ptr1,
2697                                     btrfs_node_key_ptr_offset(slot + 1),
2698                                     sizeof(struct btrfs_key_ptr));
2699                 write_extent_buffer(buf, &ptr2,
2700                                     btrfs_node_key_ptr_offset(slot),
2701                                     sizeof(struct btrfs_key_ptr));
2702                 if (slot == 0) {
2703                         struct btrfs_disk_key key;
2704                         btrfs_node_key(buf, &key, 0);
2705                         btrfs_fixup_low_keys(root, path, &key,
2706                                              btrfs_header_level(buf) + 1);
2707                 }
2708         } else {
2709                 struct btrfs_item *item1, *item2;
2710                 struct btrfs_key k1, k2;
2711                 char *item1_data, *item2_data;
2712                 u32 item1_offset, item2_offset, item1_size, item2_size;
2713
2714                 item1 = btrfs_item_nr(slot);
2715                 item2 = btrfs_item_nr(slot + 1);
2716                 btrfs_item_key_to_cpu(buf, &k1, slot);
2717                 btrfs_item_key_to_cpu(buf, &k2, slot + 1);
2718                 item1_offset = btrfs_item_offset(buf, item1);
2719                 item2_offset = btrfs_item_offset(buf, item2);
2720                 item1_size = btrfs_item_size(buf, item1);
2721                 item2_size = btrfs_item_size(buf, item2);
2722
2723                 item1_data = malloc(item1_size);
2724                 if (!item1_data)
2725                         return -ENOMEM;
2726                 item2_data = malloc(item2_size);
2727                 if (!item2_data) {
2728                         free(item1_data);
2729                         return -ENOMEM;
2730                 }
2731
2732                 read_extent_buffer(buf, item1_data, item1_offset, item1_size);
2733                 read_extent_buffer(buf, item2_data, item2_offset, item2_size);
2734
2735                 write_extent_buffer(buf, item1_data, item2_offset, item2_size);
2736                 write_extent_buffer(buf, item2_data, item1_offset, item1_size);
2737                 free(item1_data);
2738                 free(item2_data);
2739
2740                 btrfs_set_item_offset(buf, item1, item2_offset);
2741                 btrfs_set_item_offset(buf, item2, item1_offset);
2742                 btrfs_set_item_size(buf, item1, item2_size);
2743                 btrfs_set_item_size(buf, item2, item1_size);
2744
2745                 path->slots[0] = slot;
2746                 btrfs_set_item_key_unsafe(root, path, &k2);
2747                 path->slots[0] = slot + 1;
2748                 btrfs_set_item_key_unsafe(root, path, &k1);
2749         }
2750         return 0;
2751 }
2752
2753 /*
2754  * Attempt to fix basic block failures.  Currently we only handle bad key
2755  * orders, we will cycle through the keys and swap them if necessary.
2756  */
2757 static int try_to_fix_bad_block(struct btrfs_trans_handle *trans,
2758                                 struct btrfs_root *root,
2759                                 struct extent_buffer *buf,
2760                                 struct btrfs_disk_key *parent_key,
2761                                 enum btrfs_tree_block_status status)
2762 {
2763         struct btrfs_path *path;
2764         struct btrfs_key k1, k2;
2765         int i;
2766         int level;
2767         int ret;
2768
2769         if (status != BTRFS_TREE_BLOCK_BAD_KEY_ORDER)
2770                 return -EIO;
2771
2772         k1.objectid = btrfs_header_owner(buf);
2773         k1.type = BTRFS_ROOT_ITEM_KEY;
2774         k1.offset = (u64)-1;
2775
2776         root = btrfs_read_fs_root(root->fs_info, &k1);
2777         if (IS_ERR(root))
2778                 return -EIO;
2779
2780         record_root_in_trans(trans, root);
2781
2782         path = btrfs_alloc_path();
2783         if (!path)
2784                 return -EIO;
2785
2786         level = btrfs_header_level(buf);
2787         path->lowest_level = level;
2788         path->skip_check_block = 1;
2789         if (level)
2790                 btrfs_node_key_to_cpu(buf, &k1, 0);
2791         else
2792                 btrfs_item_key_to_cpu(buf, &k1, 0);
2793
2794         ret = btrfs_search_slot(trans, root, &k1, path, 0, 1);
2795         if (ret) {
2796                 btrfs_free_path(path);
2797                 return -EIO;
2798         }
2799
2800         buf = path->nodes[level];
2801         for (i = 0; i < btrfs_header_nritems(buf) - 1; i++) {
2802                 if (level) {
2803                         btrfs_node_key_to_cpu(buf, &k1, i);
2804                         btrfs_node_key_to_cpu(buf, &k2, i + 1);
2805                 } else {
2806                         btrfs_item_key_to_cpu(buf, &k1, i);
2807                         btrfs_item_key_to_cpu(buf, &k2, i + 1);
2808                 }
2809                 if (btrfs_comp_cpu_keys(&k1, &k2) < 0)
2810                         continue;
2811                 ret = swap_values(root, path, buf, i);
2812                 if (ret)
2813                         break;
2814                 btrfs_mark_buffer_dirty(buf);
2815                 i = 0;
2816         }
2817
2818         btrfs_free_path(path);
2819         return ret;
2820 }
2821
2822 static int check_block(struct btrfs_trans_handle *trans,
2823                        struct btrfs_root *root,
2824                        struct cache_tree *extent_cache,
2825                        struct extent_buffer *buf, u64 flags)
2826 {
2827         struct extent_record *rec;
2828         struct cache_extent *cache;
2829         struct btrfs_key key;
2830         enum btrfs_tree_block_status status;
2831         int ret = 0;
2832         int level;
2833
2834         cache = lookup_cache_extent(extent_cache, buf->start, buf->len);
2835         if (!cache)
2836                 return 1;
2837         rec = container_of(cache, struct extent_record, cache);
2838         rec->generation = btrfs_header_generation(buf);
2839
2840         level = btrfs_header_level(buf);
2841         if (btrfs_header_nritems(buf) > 0) {
2842
2843                 if (level == 0)
2844                         btrfs_item_key_to_cpu(buf, &key, 0);
2845                 else
2846                         btrfs_node_key_to_cpu(buf, &key, 0);
2847
2848                 rec->info_objectid = key.objectid;
2849         }
2850         rec->info_level = level;
2851
2852         if (btrfs_is_leaf(buf))
2853                 status = btrfs_check_leaf(root, &rec->parent_key, buf);
2854         else
2855                 status = btrfs_check_node(root, &rec->parent_key, buf);
2856
2857         if (status != BTRFS_TREE_BLOCK_CLEAN) {
2858                 if (repair)
2859                         status = try_to_fix_bad_block(trans, root, buf,
2860                                                       &rec->parent_key,
2861                                                       status);
2862                 if (status != BTRFS_TREE_BLOCK_CLEAN) {
2863                         ret = -EIO;
2864                         fprintf(stderr, "bad block %llu\n",
2865                                 (unsigned long long)buf->start);
2866                 } else {
2867                         /*
2868                          * Signal to callers we need to start the scan over
2869                          * again since we'll have cow'ed blocks.
2870                          */
2871                         ret = -EAGAIN;
2872                 }
2873         } else {
2874                 rec->content_checked = 1;
2875                 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)
2876                         rec->owner_ref_checked = 1;
2877                 else {
2878                         ret = check_owner_ref(root, rec, buf);
2879                         if (!ret)
2880                                 rec->owner_ref_checked = 1;
2881                 }
2882         }
2883         if (!ret)
2884                 maybe_free_extent_rec(extent_cache, rec);
2885         return ret;
2886 }
2887
2888 static struct tree_backref *find_tree_backref(struct extent_record *rec,
2889                                                 u64 parent, u64 root)
2890 {
2891         struct list_head *cur = rec->backrefs.next;
2892         struct extent_backref *node;
2893         struct tree_backref *back;
2894
2895         while(cur != &rec->backrefs) {
2896                 node = list_entry(cur, struct extent_backref, list);
2897                 cur = cur->next;
2898                 if (node->is_data)
2899                         continue;
2900                 back = (struct tree_backref *)node;
2901                 if (parent > 0) {
2902                         if (!node->full_backref)
2903                                 continue;
2904                         if (parent == back->parent)
2905                                 return back;
2906                 } else {
2907                         if (node->full_backref)
2908                                 continue;
2909                         if (back->root == root)
2910                                 return back;
2911                 }
2912         }
2913         return NULL;
2914 }
2915
2916 static struct tree_backref *alloc_tree_backref(struct extent_record *rec,
2917                                                 u64 parent, u64 root)
2918 {
2919         struct tree_backref *ref = malloc(sizeof(*ref));
2920         memset(&ref->node, 0, sizeof(ref->node));
2921         if (parent > 0) {
2922                 ref->parent = parent;
2923                 ref->node.full_backref = 1;
2924         } else {
2925                 ref->root = root;
2926                 ref->node.full_backref = 0;
2927         }
2928         list_add_tail(&ref->node.list, &rec->backrefs);
2929
2930         return ref;
2931 }
2932
2933 static struct data_backref *find_data_backref(struct extent_record *rec,
2934                                                 u64 parent, u64 root,
2935                                                 u64 owner, u64 offset,
2936                                                 int found_ref,
2937                                                 u64 disk_bytenr, u64 bytes)
2938 {
2939         struct list_head *cur = rec->backrefs.next;
2940         struct extent_backref *node;
2941         struct data_backref *back;
2942
2943         while(cur != &rec->backrefs) {
2944                 node = list_entry(cur, struct extent_backref, list);
2945                 cur = cur->next;
2946                 if (!node->is_data)
2947                         continue;
2948                 back = (struct data_backref *)node;
2949                 if (parent > 0) {
2950                         if (!node->full_backref)
2951                                 continue;
2952                         if (parent == back->parent)
2953                                 return back;
2954                 } else {
2955                         if (node->full_backref)
2956                                 continue;
2957                         if (back->root == root && back->owner == owner &&
2958                             back->offset == offset) {
2959                                 if (found_ref && node->found_ref &&
2960                                     (back->bytes != bytes ||
2961                                     back->disk_bytenr != disk_bytenr))
2962                                         continue;
2963                                 return back;
2964                         }
2965                 }
2966         }
2967         return NULL;
2968 }
2969
2970 static struct data_backref *alloc_data_backref(struct extent_record *rec,
2971                                                 u64 parent, u64 root,
2972                                                 u64 owner, u64 offset,
2973                                                 u64 max_size)
2974 {
2975         struct data_backref *ref = malloc(sizeof(*ref));
2976         memset(&ref->node, 0, sizeof(ref->node));
2977         ref->node.is_data = 1;
2978
2979         if (parent > 0) {
2980                 ref->parent = parent;
2981                 ref->owner = 0;
2982                 ref->offset = 0;
2983                 ref->node.full_backref = 1;
2984         } else {
2985                 ref->root = root;
2986                 ref->owner = owner;
2987                 ref->offset = offset;
2988                 ref->node.full_backref = 0;
2989         }
2990         ref->bytes = max_size;
2991         ref->found_ref = 0;
2992         ref->num_refs = 0;
2993         list_add_tail(&ref->node.list, &rec->backrefs);
2994         if (max_size > rec->max_size)
2995                 rec->max_size = max_size;
2996         return ref;
2997 }
2998
2999 static int add_extent_rec(struct cache_tree *extent_cache,
3000                           struct btrfs_key *parent_key, u64 parent_gen,
3001                           u64 start, u64 nr, u64 extent_item_refs,
3002                           int is_root, int inc_ref, int set_checked,
3003                           int metadata, int extent_rec, u64 max_size)
3004 {
3005         struct extent_record *rec;
3006         struct cache_extent *cache;
3007         int ret = 0;
3008         int dup = 0;
3009
3010         cache = lookup_cache_extent(extent_cache, start, nr);
3011         if (cache) {
3012                 rec = container_of(cache, struct extent_record, cache);
3013                 if (inc_ref)
3014                         rec->refs++;
3015                 if (rec->nr == 1)
3016                         rec->nr = max(nr, max_size);
3017
3018                 /*
3019                  * We need to make sure to reset nr to whatever the extent
3020                  * record says was the real size, this way we can compare it to
3021                  * the backrefs.
3022                  */
3023                 if (extent_rec) {
3024                         if (start != rec->start || rec->found_rec) {
3025                                 struct extent_record *tmp;
3026
3027                                 dup = 1;
3028                                 if (list_empty(&rec->list))
3029                                         list_add_tail(&rec->list,
3030                                                       &duplicate_extents);
3031
3032                                 /*
3033                                  * We have to do this song and dance in case we
3034                                  * find an extent record that falls inside of
3035                                  * our current extent record but does not have
3036                                  * the same objectid.
3037                                  */
3038                                 tmp = malloc(sizeof(*tmp));
3039                                 if (!tmp)
3040                                         return -ENOMEM;
3041                                 tmp->start = start;
3042                                 tmp->max_size = max_size;
3043                                 tmp->nr = nr;
3044                                 tmp->found_rec = 1;
3045                                 tmp->metadata = metadata;
3046                                 tmp->extent_item_refs = extent_item_refs;
3047                                 INIT_LIST_HEAD(&tmp->list);
3048                                 list_add_tail(&tmp->list, &rec->dups);
3049                                 rec->num_duplicates++;
3050                         } else {
3051                                 rec->nr = nr;
3052                                 rec->found_rec = 1;
3053                         }
3054                 }
3055
3056                 if (extent_item_refs && !dup) {
3057                         if (rec->extent_item_refs) {
3058                                 fprintf(stderr, "block %llu rec "
3059                                         "extent_item_refs %llu, passed %llu\n",
3060                                         (unsigned long long)start,
3061                                         (unsigned long long)
3062                                                         rec->extent_item_refs,
3063                                         (unsigned long long)extent_item_refs);
3064                         }
3065                         rec->extent_item_refs = extent_item_refs;
3066                 }
3067                 if (is_root)
3068                         rec->is_root = 1;
3069                 if (set_checked) {
3070                         rec->content_checked = 1;
3071                         rec->owner_ref_checked = 1;
3072                 }
3073
3074                 if (parent_key)
3075                         btrfs_cpu_key_to_disk(&rec->parent_key, parent_key);
3076                 if (parent_gen)
3077                         rec->parent_generation = parent_gen;
3078
3079                 if (rec->max_size < max_size)
3080                         rec->max_size = max_size;
3081
3082                 maybe_free_extent_rec(extent_cache, rec);
3083                 return ret;
3084         }
3085         rec = malloc(sizeof(*rec));
3086         rec->start = start;
3087         rec->max_size = max_size;
3088         rec->nr = max(nr, max_size);
3089         rec->found_rec = !!extent_rec;
3090         rec->content_checked = 0;
3091         rec->owner_ref_checked = 0;
3092         rec->num_duplicates = 0;
3093         rec->metadata = metadata;
3094         INIT_LIST_HEAD(&rec->backrefs);
3095         INIT_LIST_HEAD(&rec->dups);
3096         INIT_LIST_HEAD(&rec->list);
3097
3098         if (is_root)
3099                 rec->is_root = 1;
3100         else
3101                 rec->is_root = 0;
3102
3103         if (inc_ref)
3104                 rec->refs = 1;
3105         else
3106                 rec->refs = 0;
3107
3108         if (extent_item_refs)
3109                 rec->extent_item_refs = extent_item_refs;
3110         else
3111                 rec->extent_item_refs = 0;
3112
3113         if (parent_key)
3114                 btrfs_cpu_key_to_disk(&rec->parent_key, parent_key);
3115         else
3116                 memset(&rec->parent_key, 0, sizeof(*parent_key));
3117
3118         if (parent_gen)
3119                 rec->parent_generation = parent_gen;
3120         else
3121                 rec->parent_generation = 0;
3122
3123         rec->cache.start = start;
3124         rec->cache.size = nr;
3125         ret = insert_cache_extent(extent_cache, &rec->cache);
3126         BUG_ON(ret);
3127         bytes_used += nr;
3128         if (set_checked) {
3129                 rec->content_checked = 1;
3130                 rec->owner_ref_checked = 1;
3131         }
3132         return ret;
3133 }
3134
3135 static int add_tree_backref(struct cache_tree *extent_cache, u64 bytenr,
3136                             u64 parent, u64 root, int found_ref)
3137 {
3138         struct extent_record *rec;
3139         struct tree_backref *back;
3140         struct cache_extent *cache;
3141
3142         cache = lookup_cache_extent(extent_cache, bytenr, 1);
3143         if (!cache) {
3144                 add_extent_rec(extent_cache, NULL, 0, bytenr,
3145                                1, 0, 0, 0, 0, 1, 0, 0);
3146                 cache = lookup_cache_extent(extent_cache, bytenr, 1);
3147                 if (!cache)
3148                         abort();
3149         }
3150
3151         rec = container_of(cache, struct extent_record, cache);
3152         if (rec->start != bytenr) {
3153                 abort();
3154         }
3155
3156         back = find_tree_backref(rec, parent, root);
3157         if (!back)
3158                 back = alloc_tree_backref(rec, parent, root);
3159
3160         if (found_ref) {
3161                 if (back->node.found_ref) {
3162                         fprintf(stderr, "Extent back ref already exists "
3163                                 "for %llu parent %llu root %llu \n",
3164                                 (unsigned long long)bytenr,
3165                                 (unsigned long long)parent,
3166                                 (unsigned long long)root);
3167                 }
3168                 back->node.found_ref = 1;
3169         } else {
3170                 if (back->node.found_extent_tree) {
3171                         fprintf(stderr, "Extent back ref already exists "
3172                                 "for %llu parent %llu root %llu \n",
3173                                 (unsigned long long)bytenr,
3174                                 (unsigned long long)parent,
3175                                 (unsigned long long)root);
3176                 }
3177                 back->node.found_extent_tree = 1;
3178         }
3179         maybe_free_extent_rec(extent_cache, rec);
3180         return 0;
3181 }
3182
3183 static int add_data_backref(struct cache_tree *extent_cache, u64 bytenr,
3184                             u64 parent, u64 root, u64 owner, u64 offset,
3185                             u32 num_refs, int found_ref, u64 max_size)
3186 {
3187         struct extent_record *rec;
3188         struct data_backref *back;
3189         struct cache_extent *cache;
3190
3191         cache = lookup_cache_extent(extent_cache, bytenr, 1);
3192         if (!cache) {
3193                 add_extent_rec(extent_cache, NULL, 0, bytenr, 1, 0, 0, 0, 0,
3194                                0, 0, max_size);
3195                 cache = lookup_cache_extent(extent_cache, bytenr, 1);
3196                 if (!cache)
3197                         abort();
3198         }
3199
3200         rec = container_of(cache, struct extent_record, cache);
3201         if (rec->max_size < max_size)
3202                 rec->max_size = max_size;
3203
3204         /*
3205          * If found_ref is set then max_size is the real size and must match the
3206          * existing refs.  So if we have already found a ref then we need to
3207          * make sure that this ref matches the existing one, otherwise we need
3208          * to add a new backref so we can notice that the backrefs don't match
3209          * and we need to figure out who is telling the truth.  This is to
3210          * account for that awful fsync bug I introduced where we'd end up with
3211          * a btrfs_file_extent_item that would have its length include multiple
3212          * prealloc extents or point inside of a prealloc extent.
3213          */
3214         back = find_data_backref(rec, parent, root, owner, offset, found_ref,
3215                                  bytenr, max_size);
3216         if (!back)
3217                 back = alloc_data_backref(rec, parent, root, owner, offset,
3218                                           max_size);
3219
3220         if (found_ref) {
3221                 BUG_ON(num_refs != 1);
3222                 if (back->node.found_ref)
3223                         BUG_ON(back->bytes != max_size);
3224                 back->node.found_ref = 1;
3225                 back->found_ref += 1;
3226                 back->bytes = max_size;
3227                 back->disk_bytenr = bytenr;
3228                 rec->refs += 1;
3229                 rec->content_checked = 1;
3230                 rec->owner_ref_checked = 1;
3231         } else {
3232                 if (back->node.found_extent_tree) {
3233                         fprintf(stderr, "Extent back ref already exists "
3234                                 "for %llu parent %llu root %llu "
3235                                 "owner %llu offset %llu num_refs %lu\n",
3236                                 (unsigned long long)bytenr,
3237                                 (unsigned long long)parent,
3238                                 (unsigned long long)root,
3239                                 (unsigned long long)owner,
3240                                 (unsigned long long)offset,
3241                                 (unsigned long)num_refs);
3242                 }
3243                 back->num_refs = num_refs;
3244                 back->node.found_extent_tree = 1;
3245         }
3246         maybe_free_extent_rec(extent_cache, rec);
3247         return 0;
3248 }
3249
3250 static int add_pending(struct cache_tree *pending,
3251                        struct cache_tree *seen, u64 bytenr, u32 size)
3252 {
3253         int ret;
3254         ret = add_cache_extent(seen, bytenr, size);
3255         if (ret)
3256                 return ret;
3257         add_cache_extent(pending, bytenr, size);
3258         return 0;
3259 }
3260
3261 static int pick_next_pending(struct cache_tree *pending,
3262                         struct cache_tree *reada,
3263                         struct cache_tree *nodes,
3264                         u64 last, struct block_info *bits, int bits_nr,
3265                         int *reada_bits)
3266 {
3267         unsigned long node_start = last;
3268         struct cache_extent *cache;
3269         int ret;
3270
3271         cache = search_cache_extent(reada, 0);
3272         if (cache) {
3273                 bits[0].start = cache->start;
3274                 bits[0].size = cache->size;
3275                 *reada_bits = 1;
3276                 return 1;
3277         }
3278         *reada_bits = 0;
3279         if (node_start > 32768)
3280                 node_start -= 32768;
3281
3282         cache = search_cache_extent(nodes, node_start);
3283         if (!cache)
3284                 cache = search_cache_extent(nodes, 0);
3285
3286         if (!cache) {
3287                  cache = search_cache_extent(pending, 0);
3288                  if (!cache)
3289                          return 0;
3290                  ret = 0;
3291                  do {
3292                          bits[ret].start = cache->start;
3293                          bits[ret].size = cache->size;
3294                          cache = next_cache_extent(cache);
3295                          ret++;
3296                  } while (cache && ret < bits_nr);
3297                  return ret;
3298         }
3299
3300         ret = 0;
3301         do {
3302                 bits[ret].start = cache->start;
3303                 bits[ret].size = cache->size;
3304                 cache = next_cache_extent(cache);
3305                 ret++;
3306         } while (cache && ret < bits_nr);
3307
3308         if (bits_nr - ret > 8) {
3309                 u64 lookup = bits[0].start + bits[0].size;
3310                 struct cache_extent *next;
3311                 next = search_cache_extent(pending, lookup);
3312                 while(next) {
3313                         if (next->start - lookup > 32768)
3314                                 break;
3315                         bits[ret].start = next->start;
3316                         bits[ret].size = next->size;
3317                         lookup = next->start + next->size;
3318                         ret++;
3319                         if (ret == bits_nr)
3320                                 break;
3321                         next = next_cache_extent(next);
3322                         if (!next)
3323                                 break;
3324                 }
3325         }
3326         return ret;
3327 }
3328
3329 static void free_chunk_record(struct cache_extent *cache)
3330 {
3331         struct chunk_record *rec;
3332
3333         rec = container_of(cache, struct chunk_record, cache);
3334         list_del_init(&rec->list);
3335         list_del_init(&rec->dextents);
3336         free(rec);
3337 }
3338
3339 void free_chunk_cache_tree(struct cache_tree *chunk_cache)
3340 {
3341         cache_tree_free_extents(chunk_cache, free_chunk_record);
3342 }
3343
3344 static void free_device_record(struct rb_node *node)
3345 {
3346         struct device_record *rec;
3347
3348         rec = container_of(node, struct device_record, node);
3349         free(rec);
3350 }
3351
3352 FREE_RB_BASED_TREE(device_cache, free_device_record);
3353
3354 int insert_block_group_record(struct block_group_tree *tree,
3355                               struct block_group_record *bg_rec)
3356 {
3357         int ret;
3358
3359         ret = insert_cache_extent(&tree->tree, &bg_rec->cache);
3360         if (ret)
3361                 return ret;
3362
3363         list_add_tail(&bg_rec->list, &tree->block_groups);
3364         return 0;
3365 }
3366
3367 static void free_block_group_record(struct cache_extent *cache)
3368 {
3369         struct block_group_record *rec;
3370
3371         rec = container_of(cache, struct block_group_record, cache);
3372         list_del_init(&rec->list);
3373         free(rec);
3374 }
3375
3376 void free_block_group_tree(struct block_group_tree *tree)
3377 {
3378         cache_tree_free_extents(&tree->tree, free_block_group_record);
3379 }
3380
3381 int insert_device_extent_record(struct device_extent_tree *tree,
3382                                 struct device_extent_record *de_rec)
3383 {
3384         int ret;
3385
3386         /*
3387          * Device extent is a bit different from the other extents, because
3388          * the extents which belong to the different devices may have the
3389          * same start and size, so we need use the special extent cache
3390          * search/insert functions.
3391          */
3392         ret = insert_cache_extent2(&tree->tree, &de_rec->cache);
3393         if (ret)
3394                 return ret;
3395
3396         list_add_tail(&de_rec->chunk_list, &tree->no_chunk_orphans);
3397         list_add_tail(&de_rec->device_list, &tree->no_device_orphans);
3398         return 0;
3399 }
3400
3401 static void free_device_extent_record(struct cache_extent *cache)
3402 {
3403         struct device_extent_record *rec;
3404
3405         rec = container_of(cache, struct device_extent_record, cache);
3406         if (!list_empty(&rec->chunk_list))
3407                 list_del_init(&rec->chunk_list);
3408         if (!list_empty(&rec->device_list))
3409                 list_del_init(&rec->device_list);
3410         free(rec);
3411 }
3412
3413 void free_device_extent_tree(struct device_extent_tree *tree)
3414 {
3415         cache_tree_free_extents(&tree->tree, free_device_extent_record);
3416 }
3417
3418 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
3419 static int process_extent_ref_v0(struct cache_tree *extent_cache,
3420                                  struct extent_buffer *leaf, int slot)
3421 {
3422         struct btrfs_extent_ref_v0 *ref0;
3423         struct btrfs_key key;
3424
3425         btrfs_item_key_to_cpu(leaf, &key, slot);
3426         ref0 = btrfs_item_ptr(leaf, slot, struct btrfs_extent_ref_v0);
3427         if (btrfs_ref_objectid_v0(leaf, ref0) < BTRFS_FIRST_FREE_OBJECTID) {
3428                 add_tree_backref(extent_cache, key.objectid, key.offset, 0, 0);
3429         } else {
3430                 add_data_backref(extent_cache, key.objectid, key.offset, 0,
3431                                  0, 0, btrfs_ref_count_v0(leaf, ref0), 0, 0);
3432         }
3433         return 0;
3434 }
3435 #endif
3436
3437 struct chunk_record *btrfs_new_chunk_record(struct extent_buffer *leaf,
3438                                             struct btrfs_key *key,
3439                                             int slot)
3440 {
3441         struct btrfs_chunk *ptr;
3442         struct chunk_record *rec;
3443         int num_stripes, i;
3444
3445         ptr = btrfs_item_ptr(leaf, slot, struct btrfs_chunk);
3446         num_stripes = btrfs_chunk_num_stripes(leaf, ptr);
3447
3448         rec = malloc(btrfs_chunk_record_size(num_stripes));
3449         if (!rec) {
3450                 fprintf(stderr, "memory allocation failed\n");
3451                 exit(-1);
3452         }
3453
3454         memset(rec, 0, btrfs_chunk_record_size(num_stripes));
3455
3456         INIT_LIST_HEAD(&rec->list);
3457         INIT_LIST_HEAD(&rec->dextents);
3458         rec->bg_rec = NULL;
3459
3460         rec->cache.start = key->offset;
3461         rec->cache.size = btrfs_chunk_length(leaf, ptr);
3462
3463         rec->generation = btrfs_header_generation(leaf);
3464
3465         rec->objectid = key->objectid;
3466         rec->type = key->type;
3467         rec->offset = key->offset;
3468
3469         rec->length = rec->cache.size;
3470         rec->owner = btrfs_chunk_owner(leaf, ptr);
3471         rec->stripe_len = btrfs_chunk_stripe_len(leaf, ptr);
3472         rec->type_flags = btrfs_chunk_type(leaf, ptr);
3473         rec->io_width = btrfs_chunk_io_width(leaf, ptr);
3474         rec->io_align = btrfs_chunk_io_align(leaf, ptr);
3475         rec->sector_size = btrfs_chunk_sector_size(leaf, ptr);
3476         rec->num_stripes = num_stripes;
3477         rec->sub_stripes = btrfs_chunk_sub_stripes(leaf, ptr);
3478
3479         for (i = 0; i < rec->num_stripes; ++i) {
3480                 rec->stripes[i].devid =
3481                         btrfs_stripe_devid_nr(leaf, ptr, i);
3482                 rec->stripes[i].offset =
3483                         btrfs_stripe_offset_nr(leaf, ptr, i);
3484                 read_extent_buffer(leaf, rec->stripes[i].dev_uuid,
3485                                 (unsigned long)btrfs_stripe_dev_uuid_nr(ptr, i),
3486                                 BTRFS_UUID_SIZE);
3487         }
3488
3489         return rec;
3490 }
3491
3492 static int process_chunk_item(struct cache_tree *chunk_cache,
3493                               struct btrfs_key *key, struct extent_buffer *eb,
3494                               int slot)
3495 {
3496         struct chunk_record *rec;
3497         int ret = 0;
3498
3499         rec = btrfs_new_chunk_record(eb, key, slot);
3500         ret = insert_cache_extent(chunk_cache, &rec->cache);
3501         if (ret) {
3502                 fprintf(stderr, "Chunk[%llu, %llu] existed.\n",
3503                         rec->offset, rec->length);
3504                 free(rec);
3505         }
3506
3507         return ret;
3508 }
3509
3510 static int process_device_item(struct rb_root *dev_cache,
3511                 struct btrfs_key *key, struct extent_buffer *eb, int slot)
3512 {
3513         struct btrfs_dev_item *ptr;
3514         struct device_record *rec;
3515         int ret = 0;
3516
3517         ptr = btrfs_item_ptr(eb,
3518                 slot, struct btrfs_dev_item);
3519
3520         rec = malloc(sizeof(*rec));
3521         if (!rec) {
3522                 fprintf(stderr, "memory allocation failed\n");
3523                 return -ENOMEM;
3524         }
3525
3526         rec->devid = key->offset;
3527         rec->generation = btrfs_header_generation(eb);
3528
3529         rec->objectid = key->objectid;
3530         rec->type = key->type;
3531         rec->offset = key->offset;
3532
3533         rec->devid = btrfs_device_id(eb, ptr);
3534         rec->total_byte = btrfs_device_total_bytes(eb, ptr);
3535         rec->byte_used = btrfs_device_bytes_used(eb, ptr);
3536
3537         ret = rb_insert(dev_cache, &rec->node, device_record_compare);
3538         if (ret) {
3539                 fprintf(stderr, "Device[%llu] existed.\n", rec->devid);
3540                 free(rec);
3541         }
3542
3543         return ret;
3544 }
3545
3546 struct block_group_record *
3547 btrfs_new_block_group_record(struct extent_buffer *leaf, struct btrfs_key *key,
3548                              int slot)
3549 {
3550         struct btrfs_block_group_item *ptr;
3551         struct block_group_record *rec;
3552
3553         rec = malloc(sizeof(*rec));
3554         if (!rec) {
3555                 fprintf(stderr, "memory allocation failed\n");
3556                 exit(-1);
3557         }
3558         memset(rec, 0, sizeof(*rec));
3559
3560         rec->cache.start = key->objectid;
3561         rec->cache.size = key->offset;
3562
3563         rec->generation = btrfs_header_generation(leaf);
3564
3565         rec->objectid = key->objectid;
3566         rec->type = key->type;
3567         rec->offset = key->offset;
3568
3569         ptr = btrfs_item_ptr(leaf, slot, struct btrfs_block_group_item);
3570         rec->flags = btrfs_disk_block_group_flags(leaf, ptr);
3571
3572         INIT_LIST_HEAD(&rec->list);
3573
3574         return rec;
3575 }
3576
3577 static int process_block_group_item(struct block_group_tree *block_group_cache,
3578                                     struct btrfs_key *key,
3579                                     struct extent_buffer *eb, int slot)
3580 {
3581         struct block_group_record *rec;
3582         int ret = 0;
3583
3584         rec = btrfs_new_block_group_record(eb, key, slot);
3585         ret = insert_block_group_record(block_group_cache, rec);
3586         if (ret) {
3587                 fprintf(stderr, "Block Group[%llu, %llu] existed.\n",
3588                         rec->objectid, rec->offset);
3589                 free(rec);
3590         }
3591
3592         return ret;
3593 }
3594
3595 struct device_extent_record *
3596 btrfs_new_device_extent_record(struct extent_buffer *leaf,
3597                                struct btrfs_key *key, int slot)
3598 {
3599         struct device_extent_record *rec;
3600         struct btrfs_dev_extent *ptr;
3601
3602         rec = malloc(sizeof(*rec));
3603         if (!rec) {
3604                 fprintf(stderr, "memory allocation failed\n");
3605                 exit(-1);
3606         }
3607         memset(rec, 0, sizeof(*rec));
3608
3609         rec->cache.objectid = key->objectid;
3610         rec->cache.start = key->offset;
3611
3612         rec->generation = btrfs_header_generation(leaf);
3613
3614         rec->objectid = key->objectid;
3615         rec->type = key->type;
3616         rec->offset = key->offset;
3617
3618         ptr = btrfs_item_ptr(leaf, slot, struct btrfs_dev_extent);
3619         rec->chunk_objecteid =
3620                 btrfs_dev_extent_chunk_objectid(leaf, ptr);
3621         rec->chunk_offset =
3622                 btrfs_dev_extent_chunk_offset(leaf, ptr);
3623         rec->length = btrfs_dev_extent_length(leaf, ptr);
3624         rec->cache.size = rec->length;
3625
3626         INIT_LIST_HEAD(&rec->chunk_list);
3627         INIT_LIST_HEAD(&rec->device_list);
3628
3629         return rec;
3630 }
3631
3632 static int
3633 process_device_extent_item(struct device_extent_tree *dev_extent_cache,
3634                            struct btrfs_key *key, struct extent_buffer *eb,
3635                            int slot)
3636 {
3637         struct device_extent_record *rec;
3638         int ret;
3639
3640         rec = btrfs_new_device_extent_record(eb, key, slot);
3641         ret = insert_device_extent_record(dev_extent_cache, rec);
3642         if (ret) {
3643                 fprintf(stderr,
3644                         "Device extent[%llu, %llu, %llu] existed.\n",
3645                         rec->objectid, rec->offset, rec->length);
3646                 free(rec);
3647         }
3648
3649         return ret;
3650 }
3651
3652 static int process_extent_item(struct btrfs_root *root,
3653                                struct cache_tree *extent_cache,
3654                                struct extent_buffer *eb, int slot)
3655 {
3656         struct btrfs_extent_item *ei;
3657         struct btrfs_extent_inline_ref *iref;
3658         struct btrfs_extent_data_ref *dref;
3659         struct btrfs_shared_data_ref *sref;
3660         struct btrfs_key key;
3661         unsigned long end;
3662         unsigned long ptr;
3663         int type;
3664         u32 item_size = btrfs_item_size_nr(eb, slot);
3665         u64 refs = 0;
3666         u64 offset;
3667         u64 num_bytes;
3668         int metadata = 0;
3669
3670         btrfs_item_key_to_cpu(eb, &key, slot);
3671
3672         if (key.type == BTRFS_METADATA_ITEM_KEY) {
3673                 metadata = 1;
3674                 num_bytes = root->leafsize;
3675         } else {
3676                 num_bytes = key.offset;
3677         }
3678
3679         if (item_size < sizeof(*ei)) {
3680 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
3681                 struct btrfs_extent_item_v0 *ei0;
3682                 BUG_ON(item_size != sizeof(*ei0));
3683                 ei0 = btrfs_item_ptr(eb, slot, struct btrfs_extent_item_v0);
3684                 refs = btrfs_extent_refs_v0(eb, ei0);
3685 #else
3686                 BUG();
3687 #endif
3688                 return add_extent_rec(extent_cache, NULL, 0, key.objectid,
3689                                       num_bytes, refs, 0, 0, 0, metadata, 1,
3690                                       num_bytes);
3691         }
3692
3693         ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
3694         refs = btrfs_extent_refs(eb, ei);
3695
3696         add_extent_rec(extent_cache, NULL, 0, key.objectid, num_bytes,
3697                        refs, 0, 0, 0, metadata, 1, num_bytes);
3698
3699         ptr = (unsigned long)(ei + 1);
3700         if (btrfs_extent_flags(eb, ei) & BTRFS_EXTENT_FLAG_TREE_BLOCK &&
3701             key.type == BTRFS_EXTENT_ITEM_KEY)
3702                 ptr += sizeof(struct btrfs_tree_block_info);
3703
3704         end = (unsigned long)ei + item_size;
3705         while (ptr < end) {
3706                 iref = (struct btrfs_extent_inline_ref *)ptr;
3707                 type = btrfs_extent_inline_ref_type(eb, iref);
3708                 offset = btrfs_extent_inline_ref_offset(eb, iref);
3709                 switch (type) {
3710                 case BTRFS_TREE_BLOCK_REF_KEY:
3711                         add_tree_backref(extent_cache, key.objectid,
3712                                          0, offset, 0);
3713                         break;
3714                 case BTRFS_SHARED_BLOCK_REF_KEY:
3715                         add_tree_backref(extent_cache, key.objectid,
3716                                          offset, 0, 0);
3717                         break;
3718                 case BTRFS_EXTENT_DATA_REF_KEY:
3719                         dref = (struct btrfs_extent_data_ref *)(&iref->offset);
3720                         add_data_backref(extent_cache, key.objectid, 0,
3721                                         btrfs_extent_data_ref_root(eb, dref),
3722                                         btrfs_extent_data_ref_objectid(eb,
3723                                                                        dref),
3724                                         btrfs_extent_data_ref_offset(eb, dref),
3725                                         btrfs_extent_data_ref_count(eb, dref),
3726                                         0, num_bytes);
3727                         break;
3728                 case BTRFS_SHARED_DATA_REF_KEY:
3729                         sref = (struct btrfs_shared_data_ref *)(iref + 1);
3730                         add_data_backref(extent_cache, key.objectid, offset,
3731                                         0, 0, 0,
3732                                         btrfs_shared_data_ref_count(eb, sref),
3733                                         0, num_bytes);
3734                         break;
3735                 default:
3736                         fprintf(stderr, "corrupt extent record: key %Lu %u %Lu\n",
3737                                 key.objectid, key.type, num_bytes);
3738                         goto out;
3739                 }
3740                 ptr += btrfs_extent_inline_ref_size(type);
3741         }
3742         WARN_ON(ptr > end);
3743 out:
3744         return 0;
3745 }
3746
3747 static int check_cache_range(struct btrfs_root *root,
3748                              struct btrfs_block_group_cache *cache,
3749                              u64 offset, u64 bytes)
3750 {
3751         struct btrfs_free_space *entry;
3752         u64 *logical;
3753         u64 bytenr;
3754         int stripe_len;
3755         int i, nr, ret;
3756
3757         for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
3758                 bytenr = btrfs_sb_offset(i);
3759                 ret = btrfs_rmap_block(&root->fs_info->mapping_tree,
3760                                        cache->key.objectid, bytenr, 0,
3761                                        &logical, &nr, &stripe_len);
3762                 if (ret)
3763                         return ret;
3764
3765                 while (nr--) {
3766                         if (logical[nr] + stripe_len <= offset)
3767                                 continue;
3768                         if (offset + bytes <= logical[nr])
3769                                 continue;
3770                         if (logical[nr] == offset) {
3771                                 if (stripe_len >= bytes) {
3772                                         kfree(logical);
3773                                         return 0;
3774                                 }
3775                                 bytes -= stripe_len;
3776                                 offset += stripe_len;
3777                         } else if (logical[nr] < offset) {
3778                                 if (logical[nr] + stripe_len >=
3779                                     offset + bytes) {
3780                                         kfree(logical);
3781                                         return 0;
3782                                 }
3783                                 bytes = (offset + bytes) -
3784                                         (logical[nr] + stripe_len);
3785                                 offset = logical[nr] + stripe_len;
3786                         } else {
3787                                 /*
3788                                  * Could be tricky, the super may land in the
3789                                  * middle of the area we're checking.  First
3790                                  * check the easiest case, it's at the end.
3791                                  */
3792                                 if (logical[nr] + stripe_len >=
3793                                     bytes + offset) {
3794                                         bytes = logical[nr] - offset;
3795                                         continue;
3796                                 }
3797
3798                                 /* Check the left side */
3799                                 ret = check_cache_range(root, cache,
3800                                                         offset,
3801                                                         logical[nr] - offset);
3802                                 if (ret) {
3803                                         kfree(logical);
3804                                         return ret;
3805                                 }
3806
3807                                 /* Now we continue with the right side */
3808                                 bytes = (offset + bytes) -
3809                                         (logical[nr] + stripe_len);
3810                                 offset = logical[nr] + stripe_len;
3811                         }
3812                 }
3813
3814                 kfree(logical);
3815         }
3816
3817         entry = btrfs_find_free_space(cache->free_space_ctl, offset, bytes);
3818         if (!entry) {
3819                 fprintf(stderr, "There is no free space entry for %Lu-%Lu\n",
3820                         offset, offset+bytes);
3821                 return -EINVAL;
3822         }
3823
3824         if (entry->offset != offset) {
3825                 fprintf(stderr, "Wanted offset %Lu, found %Lu\n", offset,
3826                         entry->offset);
3827                 return -EINVAL;
3828         }
3829
3830         if (entry->bytes != bytes) {
3831                 fprintf(stderr, "Wanted bytes %Lu, found %Lu for off %Lu\n",
3832                         bytes, entry->bytes, offset);
3833                 return -EINVAL;
3834         }
3835
3836         unlink_free_space(cache->free_space_ctl, entry);
3837         free(entry);
3838         return 0;
3839 }
3840
3841 static int verify_space_cache(struct btrfs_root *root,
3842                               struct btrfs_block_group_cache *cache)
3843 {
3844         struct btrfs_path *path;
3845         struct extent_buffer *leaf;
3846         struct btrfs_key key;
3847         u64 last;
3848         int ret = 0;
3849
3850         path = btrfs_alloc_path();
3851         if (!path)
3852                 return -ENOMEM;
3853
3854         root = root->fs_info->extent_root;
3855
3856         last = max_t(u64, cache->key.objectid, BTRFS_SUPER_INFO_OFFSET);
3857
3858         key.objectid = last;
3859         key.offset = 0;
3860         key.type = BTRFS_EXTENT_ITEM_KEY;
3861
3862         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
3863         if (ret < 0)
3864                 goto out;
3865         ret = 0;
3866         while (1) {
3867                 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
3868                         ret = btrfs_next_leaf(root, path);
3869                         if (ret < 0)
3870                                 goto out;
3871                         if (ret > 0) {
3872                                 ret = 0;
3873                                 break;
3874                         }
3875                 }
3876                 leaf = path->nodes[0];
3877                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
3878                 if (key.objectid >= cache->key.offset + cache->key.objectid)
3879                         break;
3880                 if (key.type != BTRFS_EXTENT_ITEM_KEY &&
3881                     key.type != BTRFS_METADATA_ITEM_KEY) {
3882                         path->slots[0]++;
3883                         continue;
3884                 }
3885
3886                 if (last == key.objectid) {
3887                         if (key.type == BTRFS_EXTENT_ITEM_KEY)
3888                                 last = key.objectid + key.offset;
3889                         else
3890                                 last = key.objectid + root->leafsize;
3891                         path->slots[0]++;
3892                         continue;
3893                 }
3894
3895                 ret = check_cache_range(root, cache, last,
3896                                         key.objectid - last);
3897                 if (ret)
3898                         break;
3899                 if (key.type == BTRFS_EXTENT_ITEM_KEY)
3900                         last = key.objectid + key.offset;
3901                 else
3902                         last = key.objectid + root->leafsize;
3903                 path->slots[0]++;
3904         }
3905
3906         if (last < cache->key.objectid + cache->key.offset)
3907                 ret = check_cache_range(root, cache, last,
3908                                         cache->key.objectid +
3909                                         cache->key.offset - last);
3910
3911 out:
3912         btrfs_free_path(path);
3913
3914         if (!ret &&
3915             !RB_EMPTY_ROOT(&cache->free_space_ctl->free_space_offset)) {
3916                 fprintf(stderr, "There are still entries left in the space "
3917                         "cache\n");
3918                 ret = -EINVAL;
3919         }
3920
3921         return ret;
3922 }
3923
3924 static int check_space_cache(struct btrfs_root *root)
3925 {
3926         struct btrfs_block_group_cache *cache;
3927         u64 start = BTRFS_SUPER_INFO_OFFSET + BTRFS_SUPER_INFO_SIZE;
3928         int ret;
3929         int error = 0;
3930
3931         if (btrfs_super_cache_generation(root->fs_info->super_copy) != -1ULL &&
3932             btrfs_super_generation(root->fs_info->super_copy) !=
3933             btrfs_super_cache_generation(root->fs_info->super_copy)) {
3934                 printf("cache and super generation don't match, space cache "
3935                        "will be invalidated\n");
3936                 return 0;
3937         }
3938
3939         while (1) {
3940                 cache = btrfs_lookup_first_block_group(root->fs_info, start);
3941                 if (!cache)
3942                         break;
3943
3944                 start = cache->key.objectid + cache->key.offset;
3945                 if (!cache->free_space_ctl) {
3946                         if (btrfs_init_free_space_ctl(cache,
3947                                                       root->sectorsize)) {
3948                                 ret = -ENOMEM;
3949                                 break;
3950                         }
3951                 } else {
3952                         btrfs_remove_free_space_cache(cache);
3953                 }
3954
3955                 ret = load_free_space_cache(root->fs_info, cache);
3956                 if (!ret)
3957                         continue;
3958
3959                 ret = verify_space_cache(root, cache);
3960                 if (ret) {
3961                         fprintf(stderr, "cache appears valid but isnt %Lu\n",
3962                                 cache->key.objectid);
3963                         error++;
3964                 }
3965         }
3966
3967         return error ? -EINVAL : 0;
3968 }
3969
3970 static int read_extent_data(struct btrfs_root *root, char *data,
3971                         u64 logical, u64 *len, int mirror)
3972 {
3973         u64 offset = 0;
3974         struct btrfs_multi_bio *multi = NULL;
3975         struct btrfs_fs_info *info = root->fs_info;
3976         struct btrfs_device *device;
3977         int ret = 0;
3978         u64 max_len = *len;
3979
3980         ret = btrfs_map_block(&info->mapping_tree, READ, logical, len,
3981                               &multi, mirror, NULL);
3982         if (ret) {
3983                 fprintf(stderr, "Couldn't map the block %llu\n",
3984                                 logical + offset);
3985                 goto err;
3986         }
3987         device = multi->stripes[0].dev;
3988
3989         if (device->fd == 0)
3990                 goto err;
3991         if (*len > max_len)
3992                 *len = max_len;
3993
3994         ret = pread64(device->fd, data, *len, multi->stripes[0].physical);
3995         if (ret != *len)
3996                 ret = -EIO;
3997         else
3998                 ret = 0;
3999 err:
4000         kfree(multi);
4001         return ret;
4002 }
4003
4004 static int check_extent_csums(struct btrfs_root *root, u64 bytenr,
4005                         u64 num_bytes, unsigned long leaf_offset,
4006                         struct extent_buffer *eb) {
4007
4008         u64 offset = 0;
4009         u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
4010         char *data;
4011         unsigned long csum_offset;
4012         u32 csum;
4013         u32 csum_expected;
4014         u64 read_len;
4015         u64 data_checked = 0;
4016         u64 tmp;
4017         int ret = 0;
4018         int mirror;
4019         int num_copies;
4020
4021         if (num_bytes % root->sectorsize)
4022                 return -EINVAL;
4023
4024         data = malloc(num_bytes);
4025         if (!data)
4026                 return -ENOMEM;
4027
4028         while (offset < num_bytes) {
4029                 mirror = 0;
4030 again:
4031                 read_len = num_bytes - offset;
4032                 /* read as much space once a time */
4033                 ret = read_extent_data(root, data + offset,
4034                                 bytenr + offset, &read_len, mirror);
4035                 if (ret)
4036                         goto out;
4037                 data_checked = 0;
4038                 /* verify every 4k data's checksum */
4039                 while (data_checked < read_len) {
4040                         csum = ~(u32)0;
4041                         tmp = offset + data_checked;
4042
4043                         csum = btrfs_csum_data(NULL, (char *)data + tmp,
4044                                                csum, root->sectorsize);
4045                         btrfs_csum_final(csum, (char *)&csum);
4046
4047                         csum_offset = leaf_offset +
4048                                  tmp / root->sectorsize * csum_size;
4049                         read_extent_buffer(eb, (char *)&csum_expected,
4050                                            csum_offset, csum_size);
4051                         /* try another mirror */
4052                         if (csum != csum_expected) {
4053                                 fprintf(stderr, "mirror %d bytenr %llu csum %u expected csum %u\n",
4054                                                 mirror, bytenr + tmp,
4055                                                 csum, csum_expected);
4056                                 num_copies = btrfs_num_copies(
4057                                                 &root->fs_info->mapping_tree,
4058                                                 bytenr, num_bytes);
4059                                 if (mirror < num_copies - 1) {
4060                                         mirror += 1;
4061                                         goto again;
4062                                 }
4063                         }
4064                         data_checked += root->sectorsize;
4065                 }
4066                 offset += read_len;
4067         }
4068 out:
4069         free(data);
4070         return ret;
4071 }
4072
4073 static int check_extent_exists(struct btrfs_root *root, u64 bytenr,
4074                                u64 num_bytes)
4075 {
4076         struct btrfs_path *path;
4077         struct extent_buffer *leaf;
4078         struct btrfs_key key;
4079         int ret;
4080
4081         path = btrfs_alloc_path();
4082         if (!path) {
4083                 fprintf(stderr, "Error allocing path\n");
4084                 return -ENOMEM;
4085         }
4086
4087         key.objectid = bytenr;
4088         key.type = BTRFS_EXTENT_ITEM_KEY;
4089         key.offset = (u64)-1;
4090
4091 again:
4092         ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, path,
4093                                 0, 0);
4094         if (ret < 0) {
4095                 fprintf(stderr, "Error looking up extent record %d\n", ret);
4096                 btrfs_free_path(path);
4097                 return ret;
4098         } else if (ret) {
4099                 if (path->slots[0] > 0) {
4100                         path->slots[0]--;
4101                 } else {
4102                         ret = btrfs_prev_leaf(root, path);
4103                         if (ret < 0) {
4104                                 goto out;
4105                         } else if (ret > 0) {
4106                                 ret = 0;
4107                                 goto out;
4108                         }
4109                 }
4110         }
4111
4112         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
4113
4114         /*
4115          * Block group items come before extent items if they have the same
4116          * bytenr, so walk back one more just in case.  Dear future traveler,
4117          * first congrats on mastering time travel.  Now if it's not too much
4118          * trouble could you go back to 2006 and tell Chris to make the
4119          * BLOCK_GROUP_ITEM_KEY (and BTRFS_*_REF_KEY) lower than the
4120          * EXTENT_ITEM_KEY please?
4121          */
4122         while (key.type > BTRFS_EXTENT_ITEM_KEY) {
4123                 if (path->slots[0] > 0) {
4124                         path->slots[0]--;
4125                 } else {
4126                         ret = btrfs_prev_leaf(root, path);
4127                         if (ret < 0) {
4128                                 goto out;
4129                         } else if (ret > 0) {
4130                                 ret = 0;
4131                                 goto out;
4132                         }
4133                 }
4134                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
4135         }
4136
4137         while (num_bytes) {
4138                 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
4139                         ret = btrfs_next_leaf(root, path);
4140                         if (ret < 0) {
4141                                 fprintf(stderr, "Error going to next leaf "
4142                                         "%d\n", ret);
4143                                 btrfs_free_path(path);
4144                                 return ret;
4145                         } else if (ret) {
4146                                 break;
4147                         }
4148                 }
4149                 leaf = path->nodes[0];
4150                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
4151                 if (key.type != BTRFS_EXTENT_ITEM_KEY) {
4152                         path->slots[0]++;
4153                         continue;
4154                 }
4155                 if (key.objectid + key.offset < bytenr) {
4156                         path->slots[0]++;
4157                         continue;
4158                 }
4159                 if (key.objectid > bytenr + num_bytes)
4160                         break;
4161
4162                 if (key.objectid == bytenr) {
4163                         if (key.offset >= num_bytes) {
4164                                 num_bytes = 0;
4165                                 break;
4166                         }
4167                         num_bytes -= key.offset;
4168                         bytenr += key.offset;
4169                 } else if (key.objectid < bytenr) {
4170                         if (key.objectid + key.offset >= bytenr + num_bytes) {
4171                                 num_bytes = 0;
4172                                 break;
4173                         }
4174                         num_bytes = (bytenr + num_bytes) -
4175                                 (key.objectid + key.offset);
4176                         bytenr = key.objectid + key.offset;
4177                 } else {
4178                         if (key.objectid + key.offset < bytenr + num_bytes) {
4179                                 u64 new_start = key.objectid + key.offset;
4180                                 u64 new_bytes = bytenr + num_bytes - new_start;
4181
4182                                 /*
4183                                  * Weird case, the extent is in the middle of
4184                                  * our range, we'll have to search one side
4185                                  * and then the other.  Not sure if this happens
4186                                  * in real life, but no harm in coding it up
4187                                  * anyway just in case.
4188                                  */
4189                                 btrfs_release_path(path);
4190                                 ret = check_extent_exists(root, new_start,
4191                                                           new_bytes);
4192                                 if (ret) {
4193                                         fprintf(stderr, "Right section didn't "
4194                                                 "have a record\n");
4195                                         break;
4196                                 }
4197                                 num_bytes = key.objectid - bytenr;
4198                                 goto again;
4199                         }
4200                         num_bytes = key.objectid - bytenr;
4201                 }
4202                 path->slots[0]++;
4203         }
4204         ret = 0;
4205
4206 out:
4207         if (num_bytes && !ret) {
4208                 fprintf(stderr, "There are no extents for csum range "
4209                         "%Lu-%Lu\n", bytenr, bytenr+num_bytes);
4210                 ret = 1;
4211         }
4212
4213         btrfs_free_path(path);
4214         return ret;
4215 }
4216
4217 static int check_csums(struct btrfs_root *root)
4218 {
4219         struct btrfs_path *path;
4220         struct extent_buffer *leaf;
4221         struct btrfs_key key;
4222         u64 offset = 0, num_bytes = 0;
4223         u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
4224         int errors = 0;
4225         int ret;
4226         u64 data_len;
4227         unsigned long leaf_offset;
4228
4229         root = root->fs_info->csum_root;
4230         if (!extent_buffer_uptodate(root->node)) {
4231                 fprintf(stderr, "No valid csum tree found\n");
4232                 return -ENOENT;
4233         }
4234
4235         key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
4236         key.type = BTRFS_EXTENT_CSUM_KEY;
4237         key.offset = 0;
4238
4239         path = btrfs_alloc_path();
4240         if (!path)
4241                 return -ENOMEM;
4242
4243         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4244         if (ret < 0) {
4245                 fprintf(stderr, "Error searching csum tree %d\n", ret);
4246                 btrfs_free_path(path);
4247                 return ret;
4248         }
4249
4250         if (ret > 0 && path->slots[0])
4251                 path->slots[0]--;
4252         ret = 0;
4253
4254         while (1) {
4255                 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
4256                         ret = btrfs_next_leaf(root, path);
4257                         if (ret < 0) {
4258                                 fprintf(stderr, "Error going to next leaf "
4259                                         "%d\n", ret);
4260                                 break;
4261                         }
4262                         if (ret)
4263                                 break;
4264                 }
4265                 leaf = path->nodes[0];
4266
4267                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
4268                 if (key.type != BTRFS_EXTENT_CSUM_KEY) {
4269                         path->slots[0]++;
4270                         continue;
4271                 }
4272
4273                 data_len = (btrfs_item_size_nr(leaf, path->slots[0]) /
4274                               csum_size) * root->sectorsize;
4275                 if (!check_data_csum)
4276                         goto skip_csum_check;
4277                 leaf_offset = btrfs_item_ptr_offset(leaf, path->slots[0]);
4278                 ret = check_extent_csums(root, key.offset, data_len,
4279                                          leaf_offset, leaf);
4280                 if (ret)
4281                         break;
4282 skip_csum_check:
4283                 if (!num_bytes) {
4284                         offset = key.offset;
4285                 } else if (key.offset != offset + num_bytes) {
4286                         ret = check_extent_exists(root, offset, num_bytes);
4287                         if (ret) {
4288                                 fprintf(stderr, "Csum exists for %Lu-%Lu but "
4289                                         "there is no extent record\n",
4290                                         offset, offset+num_bytes);
4291                                 errors++;
4292                         }
4293                         offset = key.offset;
4294                         num_bytes = 0;
4295                 }
4296                 num_bytes += data_len;
4297                 path->slots[0]++;
4298         }
4299
4300         btrfs_free_path(path);
4301         return errors;
4302 }
4303
4304 static int is_dropped_key(struct btrfs_key *key,
4305                           struct btrfs_key *drop_key) {
4306         if (key->objectid < drop_key->objectid)
4307                 return 1;
4308         else if (key->objectid == drop_key->objectid) {
4309                 if (key->type < drop_key->type)
4310                         return 1;
4311                 else if (key->type == drop_key->type) {
4312                         if (key->offset < drop_key->offset)
4313                                 return 1;
4314                 }
4315         }
4316         return 0;
4317 }
4318
4319 static int run_next_block(struct btrfs_trans_handle *trans,
4320                           struct btrfs_root *root,
4321                           struct block_info *bits,
4322                           int bits_nr,
4323                           u64 *last,
4324                           struct cache_tree *pending,
4325                           struct cache_tree *seen,
4326                           struct cache_tree *reada,
4327                           struct cache_tree *nodes,
4328                           struct cache_tree *extent_cache,
4329                           struct cache_tree *chunk_cache,
4330                           struct rb_root *dev_cache,
4331                           struct block_group_tree *block_group_cache,
4332                           struct device_extent_tree *dev_extent_cache,
4333                           struct btrfs_root_item *ri)
4334 {
4335         struct extent_buffer *buf;
4336         u64 bytenr;
4337         u32 size;
4338         u64 parent;
4339         u64 owner;
4340         u64 flags;
4341         u64 ptr;
4342         u64 gen = 0;
4343         int ret = 0;
4344         int i;
4345         int nritems;
4346         struct btrfs_key key;
4347         struct cache_extent *cache;
4348         int reada_bits;
4349
4350         nritems = pick_next_pending(pending, reada, nodes, *last, bits,
4351                                     bits_nr, &reada_bits);
4352         if (nritems == 0)
4353                 return 1;
4354
4355         if (!reada_bits) {
4356                 for(i = 0; i < nritems; i++) {
4357                         ret = add_cache_extent(reada, bits[i].start,
4358                                                bits[i].size);
4359                         if (ret == -EEXIST)
4360                                 continue;
4361
4362                         /* fixme, get the parent transid */
4363                         readahead_tree_block(root, bits[i].start,
4364                                              bits[i].size, 0);
4365                 }
4366         }
4367         *last = bits[0].start;
4368         bytenr = bits[0].start;
4369         size = bits[0].size;
4370
4371         cache = lookup_cache_extent(pending, bytenr, size);
4372         if (cache) {
4373                 remove_cache_extent(pending, cache);
4374                 free(cache);
4375         }
4376         cache = lookup_cache_extent(reada, bytenr, size);
4377         if (cache) {
4378                 remove_cache_extent(reada, cache);
4379                 free(cache);
4380         }
4381         cache = lookup_cache_extent(nodes, bytenr, size);
4382         if (cache) {
4383                 remove_cache_extent(nodes, cache);
4384                 free(cache);
4385         }
4386         cache = lookup_cache_extent(extent_cache, bytenr, size);
4387         if (cache) {
4388                 struct extent_record *rec;
4389
4390                 rec = container_of(cache, struct extent_record, cache);
4391                 gen = rec->parent_generation;
4392         }
4393
4394         /* fixme, get the real parent transid */
4395         buf = read_tree_block(root, bytenr, size, gen);
4396         if (!extent_buffer_uptodate(buf)) {
4397                 record_bad_block_io(root->fs_info,
4398                                     extent_cache, bytenr, size);
4399                 goto out;
4400         }
4401
4402         nritems = btrfs_header_nritems(buf);
4403
4404         /*
4405          * FIXME, this only works only if we don't have any full
4406          * backref mode.
4407          */
4408         if (!init_extent_tree) {
4409                 ret = btrfs_lookup_extent_info(NULL, root, bytenr,
4410                                        btrfs_header_level(buf), 1, NULL,
4411                                        &flags);
4412                 if (ret < 0)
4413                         flags = 0;
4414         } else {
4415                 flags = 0;
4416         }
4417
4418         if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
4419                 parent = bytenr;
4420                 owner = 0;
4421         } else {
4422                 parent = 0;
4423                 owner = btrfs_header_owner(buf);
4424         }
4425
4426         ret = check_block(trans, root, extent_cache, buf, flags);
4427         if (ret)
4428                 goto out;
4429
4430         if (btrfs_is_leaf(buf)) {
4431                 btree_space_waste += btrfs_leaf_free_space(root, buf);
4432                 for (i = 0; i < nritems; i++) {
4433                         struct btrfs_file_extent_item *fi;
4434                         btrfs_item_key_to_cpu(buf, &key, i);
4435                         if (key.type == BTRFS_EXTENT_ITEM_KEY) {
4436                                 process_extent_item(root, extent_cache, buf,
4437                                                     i);
4438                                 continue;
4439                         }
4440                         if (key.type == BTRFS_METADATA_ITEM_KEY) {
4441                                 process_extent_item(root, extent_cache, buf,
4442                                                     i);
4443                                 continue;
4444                         }
4445                         if (key.type == BTRFS_EXTENT_CSUM_KEY) {
4446                                 total_csum_bytes +=
4447                                         btrfs_item_size_nr(buf, i);
4448                                 continue;
4449                         }
4450                         if (key.type == BTRFS_CHUNK_ITEM_KEY) {
4451                                 process_chunk_item(chunk_cache, &key, buf, i);
4452                                 continue;
4453                         }
4454                         if (key.type == BTRFS_DEV_ITEM_KEY) {
4455                                 process_device_item(dev_cache, &key, buf, i);
4456                                 continue;
4457                         }
4458                         if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
4459                                 process_block_group_item(block_group_cache,
4460                                         &key, buf, i);
4461                                 continue;
4462                         }
4463                         if (key.type == BTRFS_DEV_EXTENT_KEY) {
4464                                 process_device_extent_item(dev_extent_cache,
4465                                         &key, buf, i);
4466                                 continue;
4467
4468                         }
4469                         if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
4470 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
4471                                 process_extent_ref_v0(extent_cache, buf, i);
4472 #else
4473                                 BUG();
4474 #endif
4475                                 continue;
4476                         }
4477
4478                         if (key.type == BTRFS_TREE_BLOCK_REF_KEY) {
4479                                 add_tree_backref(extent_cache, key.objectid, 0,
4480                                                  key.offset, 0);
4481                                 continue;
4482                         }
4483                         if (key.type == BTRFS_SHARED_BLOCK_REF_KEY) {
4484                                 add_tree_backref(extent_cache, key.objectid,
4485                                                  key.offset, 0, 0);
4486                                 continue;
4487                         }
4488                         if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
4489                                 struct btrfs_extent_data_ref *ref;
4490                                 ref = btrfs_item_ptr(buf, i,
4491                                                 struct btrfs_extent_data_ref);
4492                                 add_data_backref(extent_cache,
4493                                         key.objectid, 0,
4494                                         btrfs_extent_data_ref_root(buf, ref),
4495                                         btrfs_extent_data_ref_objectid(buf,
4496                                                                        ref),
4497                                         btrfs_extent_data_ref_offset(buf, ref),
4498                                         btrfs_extent_data_ref_count(buf, ref),
4499                                         0, root->sectorsize);
4500                                 continue;
4501                         }
4502                         if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
4503                                 struct btrfs_shared_data_ref *ref;
4504                                 ref = btrfs_item_ptr(buf, i,
4505                                                 struct btrfs_shared_data_ref);
4506                                 add_data_backref(extent_cache,
4507                                         key.objectid, key.offset, 0, 0, 0,
4508                                         btrfs_shared_data_ref_count(buf, ref),
4509                                         0, root->sectorsize);
4510                                 continue;
4511                         }
4512                         if (key.type == BTRFS_ORPHAN_ITEM_KEY) {
4513                                 struct bad_item *bad;
4514
4515                                 if (key.objectid == BTRFS_ORPHAN_OBJECTID)
4516                                         continue;
4517                                 if (!owner)
4518                                         continue;
4519                                 bad = malloc(sizeof(struct bad_item));
4520                                 if (!bad)
4521                                         continue;
4522                                 INIT_LIST_HEAD(&bad->list);
4523                                 memcpy(&bad->key, &key,
4524                                        sizeof(struct btrfs_key));
4525                                 bad->root_id = owner;
4526                                 list_add_tail(&bad->list, &delete_items);
4527                                 continue;
4528                         }
4529                         if (key.type != BTRFS_EXTENT_DATA_KEY)
4530                                 continue;
4531                         fi = btrfs_item_ptr(buf, i,
4532                                             struct btrfs_file_extent_item);
4533                         if (btrfs_file_extent_type(buf, fi) ==
4534                             BTRFS_FILE_EXTENT_INLINE)
4535                                 continue;
4536                         if (btrfs_file_extent_disk_bytenr(buf, fi) == 0)
4537                                 continue;
4538
4539                         data_bytes_allocated +=
4540                                 btrfs_file_extent_disk_num_bytes(buf, fi);
4541                         if (data_bytes_allocated < root->sectorsize) {
4542                                 abort();
4543                         }
4544                         data_bytes_referenced +=
4545                                 btrfs_file_extent_num_bytes(buf, fi);
4546                         add_data_backref(extent_cache,
4547                                 btrfs_file_extent_disk_bytenr(buf, fi),
4548                                 parent, owner, key.objectid, key.offset -
4549                                 btrfs_file_extent_offset(buf, fi), 1, 1,
4550                                 btrfs_file_extent_disk_num_bytes(buf, fi));
4551                 }
4552         } else {
4553                 int level;
4554                 struct btrfs_key first_key;
4555
4556                 first_key.objectid = 0;
4557
4558                 if (nritems > 0)
4559                         btrfs_item_key_to_cpu(buf, &first_key, 0);
4560                 level = btrfs_header_level(buf);
4561                 for (i = 0; i < nritems; i++) {
4562                         ptr = btrfs_node_blockptr(buf, i);
4563                         size = btrfs_level_size(root, level - 1);
4564                         btrfs_node_key_to_cpu(buf, &key, i);
4565                         if (ri != NULL) {
4566                                 struct btrfs_key drop_key;
4567                                 btrfs_disk_key_to_cpu(&drop_key,
4568                                                       &ri->drop_progress);
4569                                 if ((level == ri->drop_level)
4570                                     && is_dropped_key(&key, &drop_key)) {
4571                                         continue;
4572                                 }
4573                         }
4574                         ret = add_extent_rec(extent_cache, &key,
4575                                              btrfs_node_ptr_generation(buf, i),
4576                                              ptr, size, 0, 0, 1, 0, 1, 0,
4577                                              size);
4578                         BUG_ON(ret);
4579
4580                         add_tree_backref(extent_cache, ptr, parent, owner, 1);
4581
4582                         if (level > 1) {
4583                                 add_pending(nodes, seen, ptr, size);
4584                         } else {
4585                                 add_pending(pending, seen, ptr, size);
4586                         }
4587                 }
4588                 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) -
4589                                       nritems) * sizeof(struct btrfs_key_ptr);
4590         }
4591         total_btree_bytes += buf->len;
4592         if (fs_root_objectid(btrfs_header_owner(buf)))
4593                 total_fs_tree_bytes += buf->len;
4594         if (btrfs_header_owner(buf) == BTRFS_EXTENT_TREE_OBJECTID)
4595                 total_extent_tree_bytes += buf->len;
4596         if (!found_old_backref &&
4597             btrfs_header_owner(buf) == BTRFS_TREE_RELOC_OBJECTID &&
4598             btrfs_header_backref_rev(buf) == BTRFS_MIXED_BACKREF_REV &&
4599             !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))
4600                 found_old_backref = 1;
4601 out:
4602         free_extent_buffer(buf);
4603         return ret;
4604 }
4605
4606 static int add_root_to_pending(struct extent_buffer *buf,
4607                                struct cache_tree *extent_cache,
4608                                struct cache_tree *pending,
4609                                struct cache_tree *seen,
4610                                struct cache_tree *nodes,
4611                                struct btrfs_key *root_key)
4612 {
4613         if (btrfs_header_level(buf) > 0)
4614                 add_pending(nodes, seen, buf->start, buf->len);
4615         else
4616                 add_pending(pending, seen, buf->start, buf->len);
4617         add_extent_rec(extent_cache, NULL, 0, buf->start, buf->len,
4618                        0, 1, 1, 0, 1, 0, buf->len);
4619
4620         if (root_key->objectid == BTRFS_TREE_RELOC_OBJECTID ||
4621             btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
4622                 add_tree_backref(extent_cache, buf->start, buf->start,
4623                                  0, 1);
4624         else
4625                 add_tree_backref(extent_cache, buf->start, 0,
4626                                  root_key->objectid, 1);
4627         return 0;
4628 }
4629
4630 /* as we fix the tree, we might be deleting blocks that
4631  * we're tracking for repair.  This hook makes sure we
4632  * remove any backrefs for blocks as we are fixing them.
4633  */
4634 static int free_extent_hook(struct btrfs_trans_handle *trans,
4635                             struct btrfs_root *root,
4636                             u64 bytenr, u64 num_bytes, u64 parent,
4637                             u64 root_objectid, u64 owner, u64 offset,
4638                             int refs_to_drop)
4639 {
4640         struct extent_record *rec;
4641         struct cache_extent *cache;
4642         int is_data;
4643         struct cache_tree *extent_cache = root->fs_info->fsck_extent_cache;
4644
4645         is_data = owner >= BTRFS_FIRST_FREE_OBJECTID;
4646         cache = lookup_cache_extent(extent_cache, bytenr, num_bytes);
4647         if (!cache)
4648                 return 0;
4649
4650         rec = container_of(cache, struct extent_record, cache);
4651         if (is_data) {
4652                 struct data_backref *back;
4653                 back = find_data_backref(rec, parent, root_objectid, owner,
4654                                          offset, 1, bytenr, num_bytes);
4655                 if (!back)
4656                         goto out;
4657                 if (back->node.found_ref) {
4658                         back->found_ref -= refs_to_drop;
4659                         if (rec->refs)
4660                                 rec->refs -= refs_to_drop;
4661                 }
4662                 if (back->node.found_extent_tree) {
4663                         back->num_refs -= refs_to_drop;
4664                         if (rec->extent_item_refs)
4665                                 rec->extent_item_refs -= refs_to_drop;
4666                 }
4667                 if (back->found_ref == 0)
4668                         back->node.found_ref = 0;
4669                 if (back->num_refs == 0)
4670                         back->node.found_extent_tree = 0;
4671
4672                 if (!back->node.found_extent_tree && back->node.found_ref) {
4673                         list_del(&back->node.list);
4674                         free(back);
4675                 }
4676         } else {
4677                 struct tree_backref *back;
4678                 back = find_tree_backref(rec, parent, root_objectid);
4679                 if (!back)
4680                         goto out;
4681                 if (back->node.found_ref) {
4682                         if (rec->refs)
4683                                 rec->refs--;
4684                         back->node.found_ref = 0;
4685                 }
4686                 if (back->node.found_extent_tree) {
4687                         if (rec->extent_item_refs)
4688                                 rec->extent_item_refs--;
4689                         back->node.found_extent_tree = 0;
4690                 }
4691                 if (!back->node.found_extent_tree && back->node.found_ref) {
4692                         list_del(&back->node.list);
4693                         free(back);
4694                 }
4695         }
4696         maybe_free_extent_rec(extent_cache, rec);
4697 out:
4698         return 0;
4699 }
4700
4701 static int delete_extent_records(struct btrfs_trans_handle *trans,
4702                                  struct btrfs_root *root,
4703                                  struct btrfs_path *path,
4704                                  u64 bytenr, u64 new_len)
4705 {
4706         struct btrfs_key key;
4707         struct btrfs_key found_key;
4708         struct extent_buffer *leaf;
4709         int ret;
4710         int slot;
4711
4712
4713         key.objectid = bytenr;
4714         key.type = (u8)-1;
4715         key.offset = (u64)-1;
4716
4717         while(1) {
4718                 ret = btrfs_search_slot(trans, root->fs_info->extent_root,
4719                                         &key, path, 0, 1);
4720                 if (ret < 0)
4721                         break;
4722
4723                 if (ret > 0) {
4724                         ret = 0;
4725                         if (path->slots[0] == 0)
4726                                 break;
4727                         path->slots[0]--;
4728                 }
4729                 ret = 0;
4730
4731                 leaf = path->nodes[0];
4732                 slot = path->slots[0];
4733
4734                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
4735                 if (found_key.objectid != bytenr)
4736                         break;
4737
4738                 if (found_key.type != BTRFS_EXTENT_ITEM_KEY &&
4739                     found_key.type != BTRFS_METADATA_ITEM_KEY &&
4740                     found_key.type != BTRFS_TREE_BLOCK_REF_KEY &&
4741                     found_key.type != BTRFS_EXTENT_DATA_REF_KEY &&
4742                     found_key.type != BTRFS_EXTENT_REF_V0_KEY &&
4743                     found_key.type != BTRFS_SHARED_BLOCK_REF_KEY &&
4744                     found_key.type != BTRFS_SHARED_DATA_REF_KEY) {
4745                         btrfs_release_path(path);
4746                         if (found_key.type == 0) {
4747                                 if (found_key.offset == 0)
4748                                         break;
4749                                 key.offset = found_key.offset - 1;
4750                                 key.type = found_key.type;
4751                         }
4752                         key.type = found_key.type - 1;
4753                         key.offset = (u64)-1;
4754                         continue;
4755                 }
4756
4757                 fprintf(stderr, "repair deleting extent record: key %Lu %u %Lu\n",
4758                         found_key.objectid, found_key.type, found_key.offset);
4759
4760                 ret = btrfs_del_item(trans, root->fs_info->extent_root, path);
4761                 if (ret)
4762                         break;
4763                 btrfs_release_path(path);
4764
4765                 if (found_key.type == BTRFS_EXTENT_ITEM_KEY ||
4766                     found_key.type == BTRFS_METADATA_ITEM_KEY) {
4767                         u64 bytes = (found_key.type == BTRFS_EXTENT_ITEM_KEY) ?
4768                                 found_key.offset : root->leafsize;
4769
4770                         ret = btrfs_update_block_group(trans, root, bytenr,
4771                                                        bytes, 0, 0);
4772                         if (ret)
4773                                 break;
4774                 }
4775         }
4776
4777         btrfs_release_path(path);
4778         return ret;
4779 }
4780
4781 /*
4782  * for a single backref, this will allocate a new extent
4783  * and add the backref to it.
4784  */
4785 static int record_extent(struct btrfs_trans_handle *trans,
4786                          struct btrfs_fs_info *info,
4787                          struct btrfs_path *path,
4788                          struct extent_record *rec,
4789                          struct extent_backref *back,
4790                          int allocated, u64 flags)
4791 {
4792         int ret;
4793         struct btrfs_root *extent_root = info->extent_root;
4794         struct extent_buffer *leaf;
4795         struct btrfs_key ins_key;
4796         struct btrfs_extent_item *ei;
4797         struct tree_backref *tback;
4798         struct data_backref *dback;
4799         struct btrfs_tree_block_info *bi;
4800
4801         if (!back->is_data)
4802                 rec->max_size = max_t(u64, rec->max_size,
4803                                     info->extent_root->leafsize);
4804
4805         if (!allocated) {
4806                 u32 item_size = sizeof(*ei);
4807
4808                 if (!back->is_data)
4809                         item_size += sizeof(*bi);
4810
4811                 ins_key.objectid = rec->start;
4812                 ins_key.offset = rec->max_size;
4813                 ins_key.type = BTRFS_EXTENT_ITEM_KEY;
4814
4815                 ret = btrfs_insert_empty_item(trans, extent_root, path,
4816                                         &ins_key, item_size);
4817                 if (ret)
4818                         goto fail;
4819
4820                 leaf = path->nodes[0];
4821                 ei = btrfs_item_ptr(leaf, path->slots[0],
4822                                     struct btrfs_extent_item);
4823
4824                 btrfs_set_extent_refs(leaf, ei, 0);
4825                 btrfs_set_extent_generation(leaf, ei, rec->generation);
4826
4827                 if (back->is_data) {
4828                         btrfs_set_extent_flags(leaf, ei,
4829                                                BTRFS_EXTENT_FLAG_DATA);
4830                 } else {
4831                         struct btrfs_disk_key copy_key;;
4832
4833                         tback = (struct tree_backref *)back;
4834                         bi = (struct btrfs_tree_block_info *)(ei + 1);
4835                         memset_extent_buffer(leaf, 0, (unsigned long)bi,
4836                                              sizeof(*bi));
4837
4838                         btrfs_set_disk_key_objectid(&copy_key,
4839                                                     rec->info_objectid);
4840                         btrfs_set_disk_key_type(&copy_key, 0);
4841                         btrfs_set_disk_key_offset(&copy_key, 0);
4842
4843                         btrfs_set_tree_block_level(leaf, bi, rec->info_level);
4844                         btrfs_set_tree_block_key(leaf, bi, &copy_key);
4845
4846                         btrfs_set_extent_flags(leaf, ei,
4847                                                BTRFS_EXTENT_FLAG_TREE_BLOCK | flags);
4848                 }
4849
4850                 btrfs_mark_buffer_dirty(leaf);
4851                 ret = btrfs_update_block_group(trans, extent_root, rec->start,
4852                                                rec->max_size, 1, 0);
4853                 if (ret)
4854                         goto fail;
4855                 btrfs_release_path(path);
4856         }
4857
4858         if (back->is_data) {
4859                 u64 parent;
4860                 int i;
4861
4862                 dback = (struct data_backref *)back;
4863                 if (back->full_backref)
4864                         parent = dback->parent;
4865                 else
4866                         parent = 0;
4867
4868                 for (i = 0; i < dback->found_ref; i++) {
4869                         /* if parent != 0, we're doing a full backref
4870                          * passing BTRFS_FIRST_FREE_OBJECTID as the owner
4871                          * just makes the backref allocator create a data
4872                          * backref
4873                          */
4874                         ret = btrfs_inc_extent_ref(trans, info->extent_root,
4875                                                    rec->start, rec->max_size,
4876                                                    parent,
4877                                                    dback->root,
4878                                                    parent ?
4879                                                    BTRFS_FIRST_FREE_OBJECTID :
4880                                                    dback->owner,
4881                                                    dback->offset);
4882                         if (ret)
4883                                 break;
4884                 }
4885                 fprintf(stderr, "adding new data backref"
4886                                 " on %llu %s %llu owner %llu"
4887                                 " offset %llu found %d\n",
4888                                 (unsigned long long)rec->start,
4889                                 back->full_backref ?
4890                                 "parent" : "root",
4891                                 back->full_backref ?
4892                                 (unsigned long long)parent :
4893                                 (unsigned long long)dback->root,
4894                                 (unsigned long long)dback->owner,
4895                                 (unsigned long long)dback->offset,
4896                                 dback->found_ref);
4897         } else {
4898                 u64 parent;
4899
4900                 tback = (struct tree_backref *)back;
4901                 if (back->full_backref)
4902                         parent = tback->parent;
4903                 else
4904                         parent = 0;
4905
4906                 ret = btrfs_inc_extent_ref(trans, info->extent_root,
4907                                            rec->start, rec->max_size,
4908                                            parent, tback->root, 0, 0);
4909                 fprintf(stderr, "adding new tree backref on "
4910                         "start %llu len %llu parent %llu root %llu\n",
4911                         rec->start, rec->max_size, tback->parent, tback->root);
4912         }
4913         if (ret)
4914                 goto fail;
4915 fail:
4916         btrfs_release_path(path);
4917         return ret;
4918 }
4919
4920 struct extent_entry {
4921         u64 bytenr;
4922         u64 bytes;
4923         int count;
4924         int broken;
4925         struct list_head list;
4926 };
4927
4928 static struct extent_entry *find_entry(struct list_head *entries,
4929                                        u64 bytenr, u64 bytes)
4930 {
4931         struct extent_entry *entry = NULL;
4932
4933         list_for_each_entry(entry, entries, list) {
4934                 if (entry->bytenr == bytenr && entry->bytes == bytes)
4935                         return entry;
4936         }
4937
4938         return NULL;
4939 }
4940
4941 static struct extent_entry *find_most_right_entry(struct list_head *entries)
4942 {
4943         struct extent_entry *entry, *best = NULL, *prev = NULL;
4944
4945         list_for_each_entry(entry, entries, list) {
4946                 if (!prev) {
4947                         prev = entry;
4948                         continue;
4949                 }
4950
4951                 /*
4952                  * If there are as many broken entries as entries then we know
4953                  * not to trust this particular entry.
4954                  */
4955                 if (entry->broken == entry->count)
4956                         continue;
4957
4958                 /*
4959                  * If our current entry == best then we can't be sure our best
4960                  * is really the best, so we need to keep searching.
4961                  */
4962                 if (best && best->count == entry->count) {
4963                         prev = entry;
4964                         best = NULL;
4965                         continue;
4966                 }
4967
4968                 /* Prev == entry, not good enough, have to keep searching */
4969                 if (!prev->broken && prev->count == entry->count)
4970                         continue;
4971
4972                 if (!best)
4973                         best = (prev->count > entry->count) ? prev : entry;
4974                 else if (best->count < entry->count)
4975                         best = entry;
4976                 prev = entry;
4977         }
4978
4979         return best;
4980 }
4981
4982 static int repair_ref(struct btrfs_trans_handle *trans,
4983                       struct btrfs_fs_info *info, struct btrfs_path *path,
4984                       struct data_backref *dback, struct extent_entry *entry)
4985 {
4986         struct btrfs_root *root;
4987         struct btrfs_file_extent_item *fi;
4988         struct extent_buffer *leaf;
4989         struct btrfs_key key;
4990         u64 bytenr, bytes;
4991         int ret;
4992
4993         key.objectid = dback->root;
4994         key.type = BTRFS_ROOT_ITEM_KEY;
4995         key.offset = (u64)-1;
4996         root = btrfs_read_fs_root(info, &key);
4997         if (IS_ERR(root)) {
4998                 fprintf(stderr, "Couldn't find root for our ref\n");
4999                 return -EINVAL;
5000         }
5001
5002         /*
5003          * The backref points to the original offset of the extent if it was
5004          * split, so we need to search down to the offset we have and then walk
5005          * forward until we find the backref we're looking for.
5006          */
5007         key.objectid = dback->owner;
5008         key.type = BTRFS_EXTENT_DATA_KEY;
5009         key.offset = dback->offset;
5010         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
5011         if (ret < 0) {
5012                 fprintf(stderr, "Error looking up ref %d\n", ret);
5013                 return ret;
5014         }
5015
5016         while (1) {
5017                 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
5018                         ret = btrfs_next_leaf(root, path);
5019                         if (ret) {
5020                                 fprintf(stderr, "Couldn't find our ref, next\n");
5021                                 return -EINVAL;
5022                         }
5023                 }
5024                 leaf = path->nodes[0];
5025                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
5026                 if (key.objectid != dback->owner ||
5027                     key.type != BTRFS_EXTENT_DATA_KEY) {
5028                         fprintf(stderr, "Couldn't find our ref, search\n");
5029                         return -EINVAL;
5030                 }
5031                 fi = btrfs_item_ptr(leaf, path->slots[0],
5032                                     struct btrfs_file_extent_item);
5033                 bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
5034                 bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
5035
5036                 if (bytenr == dback->disk_bytenr && bytes == dback->bytes)
5037                         break;
5038                 path->slots[0]++;
5039         }
5040
5041         btrfs_release_path(path);
5042
5043         /*
5044          * Have to make sure that this root gets updated when we commit the
5045          * transaction
5046          */
5047         record_root_in_trans(trans, root);
5048
5049         /*
5050          * Ok we have the key of the file extent we want to fix, now we can cow
5051          * down to the thing and fix it.
5052          */
5053         ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
5054         if (ret < 0) {
5055                 fprintf(stderr, "Error cowing down to ref [%Lu, %u, %Lu]: %d\n",
5056                         key.objectid, key.type, key.offset, ret);
5057                 return ret;
5058         }
5059         if (ret > 0) {
5060                 fprintf(stderr, "Well that's odd, we just found this key "
5061                         "[%Lu, %u, %Lu]\n", key.objectid, key.type,
5062                         key.offset);
5063                 return -EINVAL;
5064         }
5065         leaf = path->nodes[0];
5066         fi = btrfs_item_ptr(leaf, path->slots[0],
5067                             struct btrfs_file_extent_item);
5068
5069         if (btrfs_file_extent_compression(leaf, fi) &&
5070             dback->disk_bytenr != entry->bytenr) {
5071                 fprintf(stderr, "Ref doesn't match the record start and is "
5072                         "compressed, please take a btrfs-image of this file "
5073                         "system and send it to a btrfs developer so they can "
5074                         "complete this functionality for bytenr %Lu\n",
5075                         dback->disk_bytenr);
5076                 return -EINVAL;
5077         }
5078
5079         if (dback->node.broken && dback->disk_bytenr != entry->bytenr) {
5080                 btrfs_set_file_extent_disk_bytenr(leaf, fi, entry->bytenr);
5081         } else if (dback->disk_bytenr > entry->bytenr) {
5082                 u64 off_diff, offset;
5083
5084                 off_diff = dback->disk_bytenr - entry->bytenr;
5085                 offset = btrfs_file_extent_offset(leaf, fi);
5086                 if (dback->disk_bytenr + offset +
5087                     btrfs_file_extent_num_bytes(leaf, fi) >
5088                     entry->bytenr + entry->bytes) {
5089                         fprintf(stderr, "Ref is past the entry end, please "
5090                                 "take a btrfs-image of this file system and "
5091                                 "send it to a btrfs developer, ref %Lu\n",
5092                                 dback->disk_bytenr);
5093                         return -EINVAL;
5094                 }
5095                 offset += off_diff;
5096                 btrfs_set_file_extent_disk_bytenr(leaf, fi, entry->bytenr);
5097                 btrfs_set_file_extent_offset(leaf, fi, offset);
5098         } else if (dback->disk_bytenr < entry->bytenr) {
5099                 u64 offset;
5100
5101                 offset = btrfs_file_extent_offset(leaf, fi);
5102                 if (dback->disk_bytenr + offset < entry->bytenr) {
5103                         fprintf(stderr, "Ref is before the entry start, please"
5104                                 " take a btrfs-image of this file system and "
5105                                 "send it to a btrfs developer, ref %Lu\n",
5106                                 dback->disk_bytenr);
5107                         return -EINVAL;
5108                 }
5109
5110                 offset += dback->disk_bytenr;
5111                 offset -= entry->bytenr;
5112                 btrfs_set_file_extent_disk_bytenr(leaf, fi, entry->bytenr);
5113                 btrfs_set_file_extent_offset(leaf, fi, offset);
5114         }
5115
5116         btrfs_set_file_extent_disk_num_bytes(leaf, fi, entry->bytes);
5117
5118         /*
5119          * Chances are if disk_num_bytes were wrong then so is ram_bytes, but
5120          * only do this if we aren't using compression, otherwise it's a
5121          * trickier case.
5122          */
5123         if (!btrfs_file_extent_compression(leaf, fi))
5124                 btrfs_set_file_extent_ram_bytes(leaf, fi, entry->bytes);
5125         else
5126                 printf("ram bytes may be wrong?\n");
5127         btrfs_mark_buffer_dirty(leaf);
5128         btrfs_release_path(path);
5129         return 0;
5130 }
5131
5132 static int verify_backrefs(struct btrfs_trans_handle *trans,
5133                            struct btrfs_fs_info *info, struct btrfs_path *path,
5134                            struct extent_record *rec)
5135 {
5136         struct extent_backref *back;
5137         struct data_backref *dback;
5138         struct extent_entry *entry, *best = NULL;
5139         LIST_HEAD(entries);
5140         int nr_entries = 0;
5141         int broken_entries = 0;
5142         int ret = 0;
5143         short mismatch = 0;
5144
5145         /*
5146          * Metadata is easy and the backrefs should always agree on bytenr and
5147          * size, if not we've got bigger issues.
5148          */
5149         if (rec->metadata)
5150                 return 0;
5151
5152         list_for_each_entry(back, &rec->backrefs, list) {
5153                 if (back->full_backref || !back->is_data)
5154                         continue;
5155
5156                 dback = (struct data_backref *)back;
5157
5158                 /*
5159                  * We only pay attention to backrefs that we found a real
5160                  * backref for.
5161                  */
5162                 if (dback->found_ref == 0)
5163                         continue;
5164
5165                 /*
5166                  * For now we only catch when the bytes don't match, not the
5167                  * bytenr.  We can easily do this at the same time, but I want
5168                  * to have a fs image to test on before we just add repair
5169                  * functionality willy-nilly so we know we won't screw up the
5170                  * repair.
5171                  */
5172
5173                 entry = find_entry(&entries, dback->disk_bytenr,
5174                                    dback->bytes);
5175                 if (!entry) {
5176                         entry = malloc(sizeof(struct extent_entry));
5177                         if (!entry) {
5178                                 ret = -ENOMEM;
5179                                 goto out;
5180                         }
5181                         memset(entry, 0, sizeof(*entry));
5182                         entry->bytenr = dback->disk_bytenr;
5183                         entry->bytes = dback->bytes;
5184                         list_add_tail(&entry->list, &entries);
5185                         nr_entries++;
5186                 }
5187
5188                 /*
5189                  * If we only have on entry we may think the entries agree when
5190                  * in reality they don't so we have to do some extra checking.
5191                  */
5192                 if (dback->disk_bytenr != rec->start ||
5193                     dback->bytes != rec->nr || back->broken)
5194                         mismatch = 1;
5195
5196                 if (back->broken) {
5197                         entry->broken++;
5198                         broken_entries++;
5199                 }
5200
5201                 entry->count++;
5202         }
5203
5204         /* Yay all the backrefs agree, carry on good sir */
5205         if (nr_entries <= 1 && !mismatch)
5206                 goto out;
5207
5208         fprintf(stderr, "attempting to repair backref discrepency for bytenr "
5209                 "%Lu\n", rec->start);
5210
5211         /*
5212          * First we want to see if the backrefs can agree amongst themselves who
5213          * is right, so figure out which one of the entries has the highest
5214          * count.
5215          */
5216         best = find_most_right_entry(&entries);
5217
5218         /*
5219          * Ok so we may have an even split between what the backrefs think, so
5220          * this is where we use the extent ref to see what it thinks.
5221          */
5222         if (!best) {
5223                 entry = find_entry(&entries, rec->start, rec->nr);
5224                 if (!entry && (!broken_entries || !rec->found_rec)) {
5225                         fprintf(stderr, "Backrefs don't agree with each other "
5226                                 "and extent record doesn't agree with anybody,"
5227                                 " so we can't fix bytenr %Lu bytes %Lu\n",
5228                                 rec->start, rec->nr);
5229                         ret = -EINVAL;
5230                         goto out;
5231                 } else if (!entry) {
5232                         /*
5233                          * Ok our backrefs were broken, we'll assume this is the
5234                          * correct value and add an entry for this range.
5235                          */
5236                         entry = malloc(sizeof(struct extent_entry));
5237                         if (!entry) {
5238                                 ret = -ENOMEM;
5239                                 goto out;
5240                         }
5241                         memset(entry, 0, sizeof(*entry));
5242                         entry->bytenr = rec->start;
5243                         entry->bytes = rec->nr;
5244                         list_add_tail(&entry->list, &entries);
5245                         nr_entries++;
5246                 }
5247                 entry->count++;
5248                 best = find_most_right_entry(&entries);
5249                 if (!best) {
5250                         fprintf(stderr, "Backrefs and extent record evenly "
5251                                 "split on who is right, this is going to "
5252                                 "require user input to fix bytenr %Lu bytes "
5253                                 "%Lu\n", rec->start, rec->nr);
5254                         ret = -EINVAL;
5255                         goto out;
5256                 }
5257         }
5258
5259         /*
5260          * I don't think this can happen currently as we'll abort() if we catch
5261          * this case higher up, but in case somebody removes that we still can't
5262          * deal with it properly here yet, so just bail out of that's the case.
5263          */
5264         if (best->bytenr != rec->start) {
5265                 fprintf(stderr, "Extent start and backref starts don't match, "
5266                         "please use btrfs-image on this file system and send "
5267                         "it to a btrfs developer so they can make fsck fix "
5268                         "this particular case.  bytenr is %Lu, bytes is %Lu\n",
5269                         rec->start, rec->nr);
5270                 ret = -EINVAL;
5271                 goto out;
5272         }
5273
5274         /*
5275          * Ok great we all agreed on an extent record, let's go find the real
5276          * references and fix up the ones that don't match.
5277          */
5278         list_for_each_entry(back, &rec->backrefs, list) {
5279                 if (back->full_backref || !back->is_data)
5280                         continue;
5281
5282                 dback = (struct data_backref *)back;
5283
5284                 /*
5285                  * Still ignoring backrefs that don't have a real ref attached
5286                  * to them.
5287                  */
5288                 if (dback->found_ref == 0)
5289                         continue;
5290
5291                 if (dback->bytes == best->bytes &&
5292                     dback->disk_bytenr == best->bytenr)
5293                         continue;
5294
5295                 ret = repair_ref(trans, info, path, dback, best);
5296                 if (ret)
5297                         goto out;
5298         }
5299
5300         /*
5301          * Ok we messed with the actual refs, which means we need to drop our
5302          * entire cache and go back and rescan.  I know this is a huge pain and
5303          * adds a lot of extra work, but it's the only way to be safe.  Once all
5304          * the backrefs agree we may not need to do anything to the extent
5305          * record itself.
5306          */
5307         ret = -EAGAIN;
5308 out:
5309         while (!list_empty(&entries)) {
5310                 entry = list_entry(entries.next, struct extent_entry, list);
5311                 list_del_init(&entry->list);
5312                 free(entry);
5313         }
5314         return ret;
5315 }
5316
5317 static int process_duplicates(struct btrfs_root *root,
5318                               struct cache_tree *extent_cache,
5319                               struct extent_record *rec)
5320 {
5321         struct extent_record *good, *tmp;
5322         struct cache_extent *cache;
5323         int ret;
5324
5325         /*
5326          * If we found a extent record for this extent then return, or if we
5327          * have more than one duplicate we are likely going to need to delete
5328          * something.
5329          */
5330         if (rec->found_rec || rec->num_duplicates > 1)
5331                 return 0;
5332
5333         /* Shouldn't happen but just in case */
5334         BUG_ON(!rec->num_duplicates);
5335
5336         /*
5337          * So this happens if we end up with a backref that doesn't match the
5338          * actual extent entry.  So either the backref is bad or the extent
5339          * entry is bad.  Either way we want to have the extent_record actually
5340          * reflect what we found in the extent_tree, so we need to take the
5341          * duplicate out and use that as the extent_record since the only way we
5342          * get a duplicate is if we find a real life BTRFS_EXTENT_ITEM_KEY.
5343          */
5344         remove_cache_extent(extent_cache, &rec->cache);
5345
5346         good = list_entry(rec->dups.next, struct extent_record, list);
5347         list_del_init(&good->list);
5348         INIT_LIST_HEAD(&good->backrefs);
5349         INIT_LIST_HEAD(&good->dups);
5350         good->cache.start = good->start;
5351         good->cache.size = good->nr;
5352         good->content_checked = 0;
5353         good->owner_ref_checked = 0;
5354         good->num_duplicates = 0;
5355         good->refs = rec->refs;
5356         list_splice_init(&rec->backrefs, &good->backrefs);
5357         while (1) {
5358                 cache = lookup_cache_extent(extent_cache, good->start,
5359                                             good->nr);
5360                 if (!cache)
5361                         break;
5362                 tmp = container_of(cache, struct extent_record, cache);
5363
5364                 /*
5365                  * If we find another overlapping extent and it's found_rec is
5366                  * set then it's a duplicate and we need to try and delete
5367                  * something.
5368                  */
5369                 if (tmp->found_rec || tmp->num_duplicates > 0) {
5370                         if (list_empty(&good->list))
5371                                 list_add_tail(&good->list,
5372                                               &duplicate_extents);
5373                         good->num_duplicates += tmp->num_duplicates + 1;
5374                         list_splice_init(&tmp->dups, &good->dups);
5375                         list_del_init(&tmp->list);
5376                         list_add_tail(&tmp->list, &good->dups);
5377                         remove_cache_extent(extent_cache, &tmp->cache);
5378                         continue;
5379                 }
5380
5381                 /*
5382                  * Ok we have another non extent item backed extent rec, so lets
5383                  * just add it to this extent and carry on like we did above.
5384                  */
5385                 good->refs += tmp->refs;
5386                 list_splice_init(&tmp->backrefs, &good->backrefs);
5387                 remove_cache_extent(extent_cache, &tmp->cache);
5388                 free(tmp);
5389         }
5390         ret = insert_cache_extent(extent_cache, &good->cache);
5391         BUG_ON(ret);
5392         free(rec);
5393         return good->num_duplicates ? 0 : 1;
5394 }
5395
5396 static int delete_duplicate_records(struct btrfs_trans_handle *trans,
5397                                     struct btrfs_root *root,
5398                                     struct extent_record *rec)
5399 {
5400         LIST_HEAD(delete_list);
5401         struct btrfs_path *path;
5402         struct extent_record *tmp, *good, *n;
5403         int nr_del = 0;
5404         int ret = 0;
5405         struct btrfs_key key;
5406
5407         path = btrfs_alloc_path();
5408         if (!path) {
5409                 ret = -ENOMEM;
5410                 goto out;
5411         }
5412
5413         good = rec;
5414         /* Find the record that covers all of the duplicates. */
5415         list_for_each_entry(tmp, &rec->dups, list) {
5416                 if (good->start < tmp->start)
5417                         continue;
5418                 if (good->nr > tmp->nr)
5419                         continue;
5420
5421                 if (tmp->start + tmp->nr < good->start + good->nr) {
5422                         fprintf(stderr, "Ok we have overlapping extents that "
5423                                 "aren't completely covered by eachother, this "
5424                                 "is going to require more careful thought.  "
5425                                 "The extents are [%Lu-%Lu] and [%Lu-%Lu]\n",
5426                                 tmp->start, tmp->nr, good->start, good->nr);
5427                         abort();
5428                 }
5429                 good = tmp;
5430         }
5431
5432         if (good != rec)
5433                 list_add_tail(&rec->list, &delete_list);
5434
5435         list_for_each_entry_safe(tmp, n, &rec->dups, list) {
5436                 if (tmp == good)
5437                         continue;
5438                 list_move_tail(&tmp->list, &delete_list);
5439         }
5440
5441         root = root->fs_info->extent_root;
5442         list_for_each_entry(tmp, &delete_list, list) {
5443                 if (tmp->found_rec == 0)
5444                         continue;
5445                 key.objectid = tmp->start;
5446                 key.type = BTRFS_EXTENT_ITEM_KEY;
5447                 key.offset = tmp->nr;
5448
5449                 /* Shouldn't happen but just in case */
5450                 if (tmp->metadata) {
5451                         fprintf(stderr, "Well this shouldn't happen, extent "
5452                                 "record overlaps but is metadata? "
5453                                 "[%Lu, %Lu]\n", tmp->start, tmp->nr);
5454                         abort();
5455                 }
5456
5457                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
5458                 if (ret) {
5459                         if (ret > 0)
5460                                 ret = -EINVAL;
5461                         goto out;
5462                 }
5463                 ret = btrfs_del_item(trans, root, path);
5464                 if (ret)
5465                         goto out;
5466                 btrfs_release_path(path);
5467                 nr_del++;
5468         }
5469
5470 out:
5471         while (!list_empty(&delete_list)) {
5472                 tmp = list_entry(delete_list.next, struct extent_record, list);
5473                 list_del_init(&tmp->list);
5474                 if (tmp == rec)
5475                         continue;
5476                 free(tmp);
5477         }
5478
5479         while (!list_empty(&rec->dups)) {
5480                 tmp = list_entry(rec->dups.next, struct extent_record, list);
5481                 list_del_init(&tmp->list);
5482                 free(tmp);
5483         }
5484
5485         btrfs_free_path(path);
5486
5487         if (!ret && !nr_del)
5488                 rec->num_duplicates = 0;
5489
5490         return ret ? ret : nr_del;
5491 }
5492
5493 static int find_possible_backrefs(struct btrfs_trans_handle *trans,
5494                                   struct btrfs_fs_info *info,
5495                                   struct btrfs_path *path,
5496                                   struct cache_tree *extent_cache,
5497                                   struct extent_record *rec)
5498 {
5499         struct btrfs_root *root;
5500         struct extent_backref *back;
5501         struct data_backref *dback;
5502         struct cache_extent *cache;
5503         struct btrfs_file_extent_item *fi;
5504         struct btrfs_key key;
5505         u64 bytenr, bytes;
5506         int ret;
5507
5508         list_for_each_entry(back, &rec->backrefs, list) {
5509                 /* Don't care about full backrefs (poor unloved backrefs) */
5510                 if (back->full_backref || !back->is_data)
5511                         continue;
5512
5513                 dback = (struct data_backref *)back;
5514
5515                 /* We found this one, we don't need to do a lookup */
5516                 if (dback->found_ref)
5517                         continue;
5518
5519                 key.objectid = dback->root;
5520                 key.type = BTRFS_ROOT_ITEM_KEY;
5521                 key.offset = (u64)-1;
5522
5523                 root = btrfs_read_fs_root(info, &key);
5524
5525                 /* No root, definitely a bad ref, skip */
5526                 if (IS_ERR(root) && PTR_ERR(root) == -ENOENT)
5527                         continue;
5528                 /* Other err, exit */
5529                 if (IS_ERR(root))
5530                         return PTR_ERR(root);
5531
5532                 key.objectid = dback->owner;
5533                 key.type = BTRFS_EXTENT_DATA_KEY;
5534                 key.offset = dback->offset;
5535                 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
5536                 if (ret) {
5537                         btrfs_release_path(path);
5538                         if (ret < 0)
5539                                 return ret;
5540                         /* Didn't find it, we can carry on */
5541                         ret = 0;
5542                         continue;
5543                 }
5544
5545                 fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
5546                                     struct btrfs_file_extent_item);
5547                 bytenr = btrfs_file_extent_disk_bytenr(path->nodes[0], fi);
5548                 bytes = btrfs_file_extent_disk_num_bytes(path->nodes[0], fi);
5549                 btrfs_release_path(path);
5550                 cache = lookup_cache_extent(extent_cache, bytenr, 1);
5551                 if (cache) {
5552                         struct extent_record *tmp;
5553                         tmp = container_of(cache, struct extent_record, cache);
5554
5555                         /*
5556                          * If we found an extent record for the bytenr for this
5557                          * particular backref then we can't add it to our
5558                          * current extent record.  We only want to add backrefs
5559                          * that don't have a corresponding extent item in the
5560                          * extent tree since they likely belong to this record
5561                          * and we need to fix it if it doesn't match bytenrs.
5562                          */
5563                         if  (tmp->found_rec)
5564                                 continue;
5565                 }
5566
5567                 dback->found_ref += 1;
5568                 dback->disk_bytenr = bytenr;
5569                 dback->bytes = bytes;
5570
5571                 /*
5572                  * Set this so the verify backref code knows not to trust the
5573                  * values in this backref.
5574                  */
5575                 back->broken = 1;
5576         }
5577
5578         return 0;
5579 }
5580
5581 /*
5582  * when an incorrect extent item is found, this will delete
5583  * all of the existing entries for it and recreate them
5584  * based on what the tree scan found.
5585  */
5586 static int fixup_extent_refs(struct btrfs_trans_handle *trans,
5587                              struct btrfs_fs_info *info,
5588                              struct cache_tree *extent_cache,
5589                              struct extent_record *rec)
5590 {
5591         int ret;
5592         struct btrfs_path *path;
5593         struct list_head *cur = rec->backrefs.next;
5594         struct cache_extent *cache;
5595         struct extent_backref *back;
5596         int allocated = 0;
5597         u64 flags = 0;
5598
5599         /*
5600          * remember our flags for recreating the extent.
5601          * FIXME, if we have cleared extent tree, we can not
5602          * lookup extent info in extent tree.
5603          */
5604         if (!init_extent_tree) {
5605                 ret = btrfs_lookup_extent_info(NULL, info->extent_root,
5606                                         rec->start, rec->max_size,
5607                                         rec->metadata, NULL, &flags);
5608                 if (ret < 0)
5609                         flags = 0;
5610         } else {
5611                 flags = 0;
5612         }
5613
5614         path = btrfs_alloc_path();
5615         if (!path)
5616                 return -ENOMEM;
5617
5618         if (rec->refs != rec->extent_item_refs && !rec->metadata) {
5619                 /*
5620                  * Sometimes the backrefs themselves are so broken they don't
5621                  * get attached to any meaningful rec, so first go back and
5622                  * check any of our backrefs that we couldn't find and throw
5623                  * them into the list if we find the backref so that
5624                  * verify_backrefs can figure out what to do.
5625                  */
5626                 ret = find_possible_backrefs(trans, info, path, extent_cache,
5627                                              rec);
5628                 if (ret < 0)
5629                         goto out;
5630         }
5631
5632         /* step one, make sure all of the backrefs agree */
5633         ret = verify_backrefs(trans, info, path, rec);
5634         if (ret < 0)
5635                 goto out;
5636
5637         /* step two, delete all the existing records */
5638         ret = delete_extent_records(trans, info->extent_root, path,
5639                                     rec->start, rec->max_size);
5640
5641         if (ret < 0)
5642                 goto out;
5643
5644         /* was this block corrupt?  If so, don't add references to it */
5645         cache = lookup_cache_extent(info->corrupt_blocks,
5646                                     rec->start, rec->max_size);
5647         if (cache) {
5648                 ret = 0;
5649                 goto out;
5650         }
5651
5652         /* step three, recreate all the refs we did find */
5653         while(cur != &rec->backrefs) {
5654                 back = list_entry(cur, struct extent_backref, list);
5655                 cur = cur->next;
5656
5657                 /*
5658                  * if we didn't find any references, don't create a
5659                  * new extent record
5660                  */
5661                 if (!back->found_ref)
5662                         continue;
5663
5664                 ret = record_extent(trans, info, path, rec, back, allocated, flags);
5665                 allocated = 1;
5666
5667                 if (ret)
5668                         goto out;
5669         }
5670 out:
5671         btrfs_free_path(path);
5672         return ret;
5673 }
5674
5675 /* right now we only prune from the extent allocation tree */
5676 static int prune_one_block(struct btrfs_trans_handle *trans,
5677                            struct btrfs_fs_info *info,
5678                            struct btrfs_corrupt_block *corrupt)
5679 {
5680         int ret;
5681         struct btrfs_path path;
5682         struct extent_buffer *eb;
5683         u64 found;
5684         int slot;
5685         int nritems;
5686         int level = corrupt->level + 1;
5687
5688         btrfs_init_path(&path);
5689 again:
5690         /* we want to stop at the parent to our busted block */
5691         path.lowest_level = level;
5692
5693         ret = btrfs_search_slot(trans, info->extent_root,
5694                                 &corrupt->key, &path, -1, 1);
5695
5696         if (ret < 0)
5697                 goto out;
5698
5699         eb = path.nodes[level];
5700         if (!eb) {
5701                 ret = -ENOENT;
5702                 goto out;
5703         }
5704
5705         /*
5706          * hopefully the search gave us the block we want to prune,
5707          * lets try that first
5708          */
5709         slot = path.slots[level];
5710         found =  btrfs_node_blockptr(eb, slot);
5711         if (found == corrupt->cache.start)
5712                 goto del_ptr;
5713
5714         nritems = btrfs_header_nritems(eb);
5715
5716         /* the search failed, lets scan this node and hope we find it */
5717         for (slot = 0; slot < nritems; slot++) {
5718                 found =  btrfs_node_blockptr(eb, slot);
5719                 if (found == corrupt->cache.start)
5720                         goto del_ptr;
5721         }
5722         /*
5723          * we couldn't find the bad block.  TODO, search all the nodes for pointers
5724          * to this block
5725          */
5726         if (eb == info->extent_root->node) {
5727                 ret = -ENOENT;
5728                 goto out;
5729         } else {
5730                 level++;
5731                 btrfs_release_path(&path);
5732                 goto again;
5733         }
5734
5735 del_ptr:
5736         printk("deleting pointer to block %Lu\n", corrupt->cache.start);
5737         ret = btrfs_del_ptr(trans, info->extent_root, &path, level, slot);
5738
5739 out:
5740         btrfs_release_path(&path);
5741         return ret;
5742 }
5743
5744 static int prune_corrupt_blocks(struct btrfs_trans_handle *trans,
5745                                 struct btrfs_fs_info *info)
5746 {
5747         struct cache_extent *cache;
5748         struct btrfs_corrupt_block *corrupt;
5749
5750         cache = search_cache_extent(info->corrupt_blocks, 0);
5751         while (1) {
5752                 if (!cache)
5753                         break;
5754                 corrupt = container_of(cache, struct btrfs_corrupt_block, cache);
5755                 prune_one_block(trans, info, corrupt);
5756                 cache = next_cache_extent(cache);
5757         }
5758         return 0;
5759 }
5760
5761 static void free_corrupt_block(struct cache_extent *cache)
5762 {
5763         struct btrfs_corrupt_block *corrupt;
5764
5765         corrupt = container_of(cache, struct btrfs_corrupt_block, cache);
5766         free(corrupt);
5767 }
5768
5769 FREE_EXTENT_CACHE_BASED_TREE(corrupt_blocks, free_corrupt_block);
5770
5771 static void reset_cached_block_groups(struct btrfs_fs_info *fs_info)
5772 {
5773         struct btrfs_block_group_cache *cache;
5774         u64 start, end;
5775         int ret;
5776
5777         while (1) {
5778                 ret = find_first_extent_bit(&fs_info->free_space_cache, 0,
5779                                             &start, &end, EXTENT_DIRTY);
5780                 if (ret)
5781                         break;
5782                 clear_extent_dirty(&fs_info->free_space_cache, start, end,
5783                                    GFP_NOFS);
5784         }
5785
5786         start = 0;
5787         while (1) {
5788                 cache = btrfs_lookup_first_block_group(fs_info, start);
5789                 if (!cache)
5790                         break;
5791                 if (cache->cached)
5792                         cache->cached = 0;
5793                 start = cache->key.objectid + cache->key.offset;
5794         }
5795 }
5796
5797 static int check_extent_refs(struct btrfs_trans_handle *trans,
5798                              struct btrfs_root *root,
5799                              struct cache_tree *extent_cache)
5800 {
5801         struct extent_record *rec;
5802         struct cache_extent *cache;
5803         int err = 0;
5804         int ret = 0;
5805         int fixed = 0;
5806         int had_dups = 0;
5807
5808         if (repair) {
5809                 /*
5810                  * if we're doing a repair, we have to make sure
5811                  * we don't allocate from the problem extents.
5812                  * In the worst case, this will be all the
5813                  * extents in the FS
5814                  */
5815                 cache = search_cache_extent(extent_cache, 0);
5816                 while(cache) {
5817                         rec = container_of(cache, struct extent_record, cache);
5818                         btrfs_pin_extent(root->fs_info,
5819                                          rec->start, rec->max_size);
5820                         cache = next_cache_extent(cache);
5821                 }
5822
5823                 /* pin down all the corrupted blocks too */
5824                 cache = search_cache_extent(root->fs_info->corrupt_blocks, 0);
5825                 while(cache) {
5826                         btrfs_pin_extent(root->fs_info,
5827                                          cache->start, cache->size);
5828                         cache = next_cache_extent(cache);
5829                 }
5830                 prune_corrupt_blocks(trans, root->fs_info);
5831                 reset_cached_block_groups(root->fs_info);
5832         }
5833
5834         /*
5835          * We need to delete any duplicate entries we find first otherwise we
5836          * could mess up the extent tree when we have backrefs that actually
5837          * belong to a different extent item and not the weird duplicate one.
5838          */
5839         while (repair && !list_empty(&duplicate_extents)) {
5840                 rec = list_entry(duplicate_extents.next, struct extent_record,
5841                                  list);
5842                 list_del_init(&rec->list);
5843
5844                 /* Sometimes we can find a backref before we find an actual
5845                  * extent, so we need to process it a little bit to see if there
5846                  * truly are multiple EXTENT_ITEM_KEY's for the same range, or
5847                  * if this is a backref screwup.  If we need to delete stuff
5848                  * process_duplicates() will return 0, otherwise it will return
5849                  * 1 and we
5850                  */
5851                 if (process_duplicates(root, extent_cache, rec))
5852                         continue;
5853                 ret = delete_duplicate_records(trans, root, rec);
5854                 if (ret < 0)
5855                         return ret;
5856                 /*
5857                  * delete_duplicate_records will return the number of entries
5858                  * deleted, so if it's greater than 0 then we know we actually
5859                  * did something and we need to remove.
5860                  */
5861                 if (ret)
5862                         had_dups = 1;
5863         }
5864
5865         if (had_dups)
5866                 return -EAGAIN;
5867
5868         while(1) {
5869                 fixed = 0;
5870                 cache = search_cache_extent(extent_cache, 0);
5871                 if (!cache)
5872                         break;
5873                 rec = container_of(cache, struct extent_record, cache);
5874                 if (rec->num_duplicates) {
5875                         fprintf(stderr, "extent item %llu has multiple extent "
5876                                 "items\n", (unsigned long long)rec->start);
5877                         err = 1;
5878                 }
5879
5880                 if (rec->refs != rec->extent_item_refs) {
5881                         fprintf(stderr, "ref mismatch on [%llu %llu] ",
5882                                 (unsigned long long)rec->start,
5883                                 (unsigned long long)rec->nr);
5884                         fprintf(stderr, "extent item %llu, found %llu\n",
5885                                 (unsigned long long)rec->extent_item_refs,
5886                                 (unsigned long long)rec->refs);
5887                         if (!fixed && repair) {
5888                                 ret = fixup_extent_refs(trans, root->fs_info,
5889                                                         extent_cache, rec);
5890                                 if (ret)
5891                                         goto repair_abort;
5892                                 fixed = 1;
5893                         }
5894                         err = 1;
5895
5896                 }
5897                 if (all_backpointers_checked(rec, 1)) {
5898                         fprintf(stderr, "backpointer mismatch on [%llu %llu]\n",
5899                                 (unsigned long long)rec->start,
5900                                 (unsigned long long)rec->nr);
5901
5902                         if (!fixed && repair) {
5903                                 ret = fixup_extent_refs(trans, root->fs_info,
5904                                                         extent_cache, rec);
5905                                 if (ret)
5906                                         goto repair_abort;
5907                                 fixed = 1;
5908                         }
5909
5910                         err = 1;
5911                 }
5912                 if (!rec->owner_ref_checked) {
5913                         fprintf(stderr, "owner ref check failed [%llu %llu]\n",
5914                                 (unsigned long long)rec->start,
5915                                 (unsigned long long)rec->nr);
5916                         if (!fixed && repair) {
5917                                 ret = fixup_extent_refs(trans, root->fs_info,
5918                                                         extent_cache, rec);
5919                                 if (ret)
5920                                         goto repair_abort;
5921                                 fixed = 1;
5922                         }
5923                         err = 1;
5924                 }
5925
5926                 remove_cache_extent(extent_cache, cache);
5927                 free_all_extent_backrefs(rec);
5928                 free(rec);
5929         }
5930 repair_abort:
5931         if (repair) {
5932                 if (ret && ret != -EAGAIN) {
5933                         fprintf(stderr, "failed to repair damaged filesystem, aborting\n");
5934                         exit(1);
5935                 } else if (!ret) {
5936                         btrfs_fix_block_accounting(trans, root);
5937                 }
5938                 if (err)
5939                         fprintf(stderr, "repaired damaged extent references\n");
5940                 return ret;
5941         }
5942         return err;
5943 }
5944
5945 u64 calc_stripe_length(u64 type, u64 length, int num_stripes)
5946 {
5947         u64 stripe_size;
5948
5949         if (type & BTRFS_BLOCK_GROUP_RAID0) {
5950                 stripe_size = length;
5951                 stripe_size /= num_stripes;
5952         } else if (type & BTRFS_BLOCK_GROUP_RAID10) {
5953                 stripe_size = length * 2;
5954                 stripe_size /= num_stripes;
5955         } else if (type & BTRFS_BLOCK_GROUP_RAID5) {
5956                 stripe_size = length;
5957                 stripe_size /= (num_stripes - 1);
5958         } else if (type & BTRFS_BLOCK_GROUP_RAID6) {
5959                 stripe_size = length;
5960                 stripe_size /= (num_stripes - 2);
5961         } else {
5962                 stripe_size = length;
5963         }
5964         return stripe_size;
5965 }
5966
5967 static int check_chunk_refs(struct chunk_record *chunk_rec,
5968                             struct block_group_tree *block_group_cache,
5969                             struct device_extent_tree *dev_extent_cache,
5970                             int silent)
5971 {
5972         struct cache_extent *block_group_item;
5973         struct block_group_record *block_group_rec;
5974         struct cache_extent *dev_extent_item;
5975         struct device_extent_record *dev_extent_rec;
5976         u64 devid;
5977         u64 offset;
5978         u64 length;
5979         int i;
5980         int ret = 0;
5981
5982         block_group_item = lookup_cache_extent(&block_group_cache->tree,
5983                                                chunk_rec->offset,
5984                                                chunk_rec->length);
5985         if (block_group_item) {
5986                 block_group_rec = container_of(block_group_item,
5987                                                struct block_group_record,
5988                                                cache);
5989                 if (chunk_rec->length != block_group_rec->offset ||
5990                     chunk_rec->offset != block_group_rec->objectid ||
5991                     chunk_rec->type_flags != block_group_rec->flags) {
5992                         if (!silent)
5993                                 fprintf(stderr,
5994                                         "Chunk[%llu, %u, %llu]: length(%llu), offset(%llu), type(%llu) mismatch with block group[%llu, %u, %llu]: offset(%llu), objectid(%llu), flags(%llu)\n",
5995                                         chunk_rec->objectid,
5996                                         chunk_rec->type,
5997                                         chunk_rec->offset,
5998                                         chunk_rec->length,
5999                                         chunk_rec->offset,
6000                                         chunk_rec->type_flags,
6001                                         block_group_rec->objectid,
6002                                         block_group_rec->type,
6003                                         block_group_rec->offset,
6004                                         block_group_rec->offset,
6005                                         block_group_rec->objectid,
6006                                         block_group_rec->flags);
6007                         ret = -1;
6008                 } else {
6009                         list_del_init(&block_group_rec->list);
6010                         chunk_rec->bg_rec = block_group_rec;
6011                 }
6012         } else {
6013                 if (!silent)
6014                         fprintf(stderr,
6015                                 "Chunk[%llu, %u, %llu]: length(%llu), offset(%llu), type(%llu) is not found in block group\n",
6016                                 chunk_rec->objectid,
6017                                 chunk_rec->type,
6018                                 chunk_rec->offset,
6019                                 chunk_rec->length,
6020                                 chunk_rec->offset,
6021                                 chunk_rec->type_flags);
6022                 ret = -1;
6023         }
6024
6025         length = calc_stripe_length(chunk_rec->type_flags, chunk_rec->length,
6026                                     chunk_rec->num_stripes);
6027         for (i = 0; i < chunk_rec->num_stripes; ++i) {
6028                 devid = chunk_rec->stripes[i].devid;
6029                 offset = chunk_rec->stripes[i].offset;
6030                 dev_extent_item = lookup_cache_extent2(&dev_extent_cache->tree,
6031                                                        devid, offset, length);
6032                 if (dev_extent_item) {
6033                         dev_extent_rec = container_of(dev_extent_item,
6034                                                 struct device_extent_record,
6035                                                 cache);
6036                         if (dev_extent_rec->objectid != devid ||
6037                             dev_extent_rec->offset != offset ||
6038                             dev_extent_rec->chunk_offset != chunk_rec->offset ||
6039                             dev_extent_rec->length != length) {
6040                                 if (!silent)
6041                                         fprintf(stderr,
6042                                                 "Chunk[%llu, %u, %llu] stripe[%llu, %llu] dismatch dev extent[%llu, %llu, %llu]\n",
6043                                                 chunk_rec->objectid,
6044                                                 chunk_rec->type,
6045                                                 chunk_rec->offset,
6046                                                 chunk_rec->stripes[i].devid,
6047                                                 chunk_rec->stripes[i].offset,
6048                                                 dev_extent_rec->objectid,
6049                                                 dev_extent_rec->offset,
6050                                                 dev_extent_rec->length);
6051                                 ret = -1;
6052                         } else {
6053                                 list_move(&dev_extent_rec->chunk_list,
6054                                           &chunk_rec->dextents);
6055                         }
6056                 } else {
6057                         if (!silent)
6058                                 fprintf(stderr,
6059                                         "Chunk[%llu, %u, %llu] stripe[%llu, %llu] is not found in dev extent\n",
6060                                         chunk_rec->objectid,
6061                                         chunk_rec->type,
6062                                         chunk_rec->offset,
6063                                         chunk_rec->stripes[i].devid,
6064                                         chunk_rec->stripes[i].offset);
6065                         ret = -1;
6066                 }
6067         }
6068         return ret;
6069 }
6070
6071 /* check btrfs_chunk -> btrfs_dev_extent / btrfs_block_group_item */
6072 int check_chunks(struct cache_tree *chunk_cache,
6073                  struct block_group_tree *block_group_cache,
6074                  struct device_extent_tree *dev_extent_cache,
6075                  struct list_head *good, struct list_head *bad, int silent)
6076 {
6077         struct cache_extent *chunk_item;
6078         struct chunk_record *chunk_rec;
6079         struct block_group_record *bg_rec;
6080         struct device_extent_record *dext_rec;
6081         int err;
6082         int ret = 0;
6083
6084         chunk_item = first_cache_extent(chunk_cache);
6085         while (chunk_item) {
6086                 chunk_rec = container_of(chunk_item, struct chunk_record,
6087                                          cache);
6088                 err = check_chunk_refs(chunk_rec, block_group_cache,
6089                                        dev_extent_cache, silent);
6090                 if (err) {
6091                         ret = err;
6092                         if (bad)
6093                                 list_add_tail(&chunk_rec->list, bad);
6094                 } else {
6095                         if (good)
6096                                 list_add_tail(&chunk_rec->list, good);
6097                 }
6098
6099                 chunk_item = next_cache_extent(chunk_item);
6100         }
6101
6102         list_for_each_entry(bg_rec, &block_group_cache->block_groups, list) {
6103                 if (!silent)
6104                         fprintf(stderr,
6105                                 "Block group[%llu, %llu] (flags = %llu) didn't find the relative chunk.\n",
6106                                 bg_rec->objectid,
6107                                 bg_rec->offset,
6108                                 bg_rec->flags);
6109                 if (!ret)
6110                         ret = 1;
6111         }
6112
6113         list_for_each_entry(dext_rec, &dev_extent_cache->no_chunk_orphans,
6114                             chunk_list) {
6115                 if (!silent)
6116                         fprintf(stderr,
6117                                 "Device extent[%llu, %llu, %llu] didn't find the relative chunk.\n",
6118                                 dext_rec->objectid,
6119                                 dext_rec->offset,
6120                                 dext_rec->length);
6121                 if (!ret)
6122                         ret = 1;
6123         }
6124         return ret;
6125 }
6126
6127
6128 static int check_device_used(struct device_record *dev_rec,
6129                              struct device_extent_tree *dext_cache)
6130 {
6131         struct cache_extent *cache;
6132         struct device_extent_record *dev_extent_rec;
6133         u64 total_byte = 0;
6134
6135         cache = search_cache_extent2(&dext_cache->tree, dev_rec->devid, 0);
6136         while (cache) {
6137                 dev_extent_rec = container_of(cache,
6138                                               struct device_extent_record,
6139                                               cache);
6140                 if (dev_extent_rec->objectid != dev_rec->devid)
6141                         break;
6142
6143                 list_del_init(&dev_extent_rec->device_list);
6144                 total_byte += dev_extent_rec->length;
6145                 cache = next_cache_extent(cache);
6146         }
6147
6148         if (total_byte != dev_rec->byte_used) {
6149                 fprintf(stderr,
6150                         "Dev extent's total-byte(%llu) is not equal to byte-used(%llu) in dev[%llu, %u, %llu]\n",
6151                         total_byte, dev_rec->byte_used, dev_rec->objectid,
6152                         dev_rec->type, dev_rec->offset);
6153                 return -1;
6154         } else {
6155                 return 0;
6156         }
6157 }
6158
6159 /* check btrfs_dev_item -> btrfs_dev_extent */
6160 static int check_devices(struct rb_root *dev_cache,
6161                          struct device_extent_tree *dev_extent_cache)
6162 {
6163         struct rb_node *dev_node;
6164         struct device_record *dev_rec;
6165         struct device_extent_record *dext_rec;
6166         int err;
6167         int ret = 0;
6168
6169         dev_node = rb_first(dev_cache);
6170         while (dev_node) {
6171                 dev_rec = container_of(dev_node, struct device_record, node);
6172                 err = check_device_used(dev_rec, dev_extent_cache);
6173                 if (err)
6174                         ret = err;
6175
6176                 dev_node = rb_next(dev_node);
6177         }
6178         list_for_each_entry(dext_rec, &dev_extent_cache->no_device_orphans,
6179                             device_list) {
6180                 fprintf(stderr,
6181                         "Device extent[%llu, %llu, %llu] didn't find its device.\n",
6182                         dext_rec->objectid, dext_rec->offset, dext_rec->length);
6183                 if (!ret)
6184                         ret = 1;
6185         }
6186         return ret;
6187 }
6188
6189 static int check_chunks_and_extents(struct btrfs_root *root)
6190 {
6191         struct rb_root dev_cache;
6192         struct cache_tree chunk_cache;
6193         struct block_group_tree block_group_cache;
6194         struct device_extent_tree dev_extent_cache;
6195         struct cache_tree extent_cache;
6196         struct cache_tree seen;
6197         struct cache_tree pending;
6198         struct cache_tree reada;
6199         struct cache_tree nodes;
6200         struct cache_tree corrupt_blocks;
6201         struct btrfs_path path;
6202         struct btrfs_key key;
6203         struct btrfs_key found_key;
6204         int ret, err = 0;
6205         u64 last = 0;
6206         struct block_info *bits;
6207         int bits_nr;
6208         struct extent_buffer *leaf;
6209         struct btrfs_trans_handle *trans = NULL;
6210         int slot;
6211         struct btrfs_root_item ri;
6212         struct list_head dropping_trees;
6213
6214         dev_cache = RB_ROOT;
6215         cache_tree_init(&chunk_cache);
6216         block_group_tree_init(&block_group_cache);
6217         device_extent_tree_init(&dev_extent_cache);
6218
6219         cache_tree_init(&extent_cache);
6220         cache_tree_init(&seen);
6221         cache_tree_init(&pending);
6222         cache_tree_init(&nodes);
6223         cache_tree_init(&reada);
6224         cache_tree_init(&corrupt_blocks);
6225         INIT_LIST_HEAD(&dropping_trees);
6226
6227         if (repair) {
6228                 trans = btrfs_start_transaction(root, 1);
6229                 if (IS_ERR(trans)) {
6230                         fprintf(stderr, "Error starting transaction\n");
6231                         return PTR_ERR(trans);
6232                 }
6233                 root->fs_info->fsck_extent_cache = &extent_cache;
6234                 root->fs_info->free_extent_hook = free_extent_hook;
6235                 root->fs_info->corrupt_blocks = &corrupt_blocks;
6236         }
6237
6238         bits_nr = 1024;
6239         bits = malloc(bits_nr * sizeof(struct block_info));
6240         if (!bits) {
6241                 perror("malloc");
6242                 exit(1);
6243         }
6244
6245 again:
6246         add_root_to_pending(root->fs_info->tree_root->node,
6247                             &extent_cache, &pending, &seen, &nodes,
6248                             &root->fs_info->tree_root->root_key);
6249
6250         add_root_to_pending(root->fs_info->chunk_root->node,
6251                             &extent_cache, &pending, &seen, &nodes,
6252                             &root->fs_info->chunk_root->root_key);
6253
6254         btrfs_init_path(&path);
6255         key.offset = 0;
6256         key.objectid = 0;
6257         btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
6258         ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
6259                                         &key, &path, 0, 0);
6260         if (ret < 0)
6261                 goto out;
6262         while(1) {
6263                 leaf = path.nodes[0];
6264                 slot = path.slots[0];
6265                 if (slot >= btrfs_header_nritems(path.nodes[0])) {
6266                         ret = btrfs_next_leaf(root, &path);
6267                         if (ret != 0)
6268                                 break;
6269                         leaf = path.nodes[0];
6270                         slot = path.slots[0];
6271                 }
6272                 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
6273                 if (btrfs_key_type(&found_key) == BTRFS_ROOT_ITEM_KEY) {
6274                         unsigned long offset;
6275                         struct extent_buffer *buf;
6276
6277                         offset = btrfs_item_ptr_offset(leaf, path.slots[0]);
6278                         read_extent_buffer(leaf, &ri, offset, sizeof(ri));
6279                         if (btrfs_disk_key_objectid(&ri.drop_progress) == 0) {
6280                                 buf = read_tree_block(root->fs_info->tree_root,
6281                                                       btrfs_root_bytenr(&ri),
6282                                                       btrfs_level_size(root,
6283                                                       btrfs_root_level(&ri)),
6284                                                       0);
6285                                 if (!buf) {
6286                                         ret = -EIO;
6287                                         goto out;
6288                                 }
6289                                 add_root_to_pending(buf, &extent_cache,
6290                                                     &pending, &seen, &nodes,
6291                                                     &found_key);
6292                                 free_extent_buffer(buf);
6293                         } else {
6294                                 struct dropping_root_item_record *dri_rec;
6295                                 dri_rec = malloc(sizeof(*dri_rec));
6296                                 if (!dri_rec) {
6297                                         perror("malloc");
6298                                         exit(1);
6299                                 }
6300                                 memcpy(&dri_rec->ri, &ri, sizeof(ri));
6301                                 memcpy(&dri_rec->found_key, &found_key,
6302                                        sizeof(found_key));
6303                                 list_add_tail(&dri_rec->list, &dropping_trees);
6304                         }
6305                 }
6306                 path.slots[0]++;
6307         }
6308         btrfs_release_path(&path);
6309         while (1) {
6310                 ret = run_next_block(trans, root, bits, bits_nr, &last,
6311                                      &pending, &seen, &reada, &nodes,
6312                                      &extent_cache, &chunk_cache, &dev_cache,
6313                                      &block_group_cache, &dev_extent_cache,
6314                                      NULL);
6315                 if (ret != 0)
6316                         break;
6317         }
6318
6319         while (!list_empty(&dropping_trees)) {
6320                 struct dropping_root_item_record *rec;
6321                 struct extent_buffer *buf;
6322                 rec = list_entry(dropping_trees.next,
6323                                  struct dropping_root_item_record, list);
6324                 last = 0;
6325                 if (!bits) {
6326                         perror("realloc");
6327                         exit(1);
6328                 }
6329                 buf = read_tree_block(root->fs_info->tree_root,
6330                                       btrfs_root_bytenr(&rec->ri),
6331                                       btrfs_level_size(root,
6332                                       btrfs_root_level(&rec->ri)), 0);
6333                 if (!buf) {
6334                         ret = -EIO;
6335                         goto out;
6336                 }
6337                 add_root_to_pending(buf, &extent_cache, &pending,
6338                                     &seen, &nodes, &rec->found_key);
6339                 while (1) {
6340                         ret = run_next_block(trans, root, bits, bits_nr, &last,
6341                                              &pending, &seen, &reada,
6342                                              &nodes, &extent_cache,
6343                                              &chunk_cache, &dev_cache,
6344                                              &block_group_cache,
6345                                              &dev_extent_cache,
6346                                              &rec->ri);
6347                         if (ret != 0)
6348                                 break;
6349                 }
6350                 free_extent_buffer(buf);
6351                 list_del(&rec->list);
6352                 free(rec);
6353         }
6354
6355         if (ret >= 0)
6356                 ret = check_extent_refs(trans, root, &extent_cache);
6357         if (ret == -EAGAIN) {
6358                 ret = btrfs_commit_transaction(trans, root);
6359                 if (ret)
6360                         goto out;
6361
6362                 trans = btrfs_start_transaction(root, 1);
6363                 if (IS_ERR(trans)) {
6364                         ret = PTR_ERR(trans);
6365                         goto out;
6366                 }
6367
6368                 free_corrupt_blocks_tree(root->fs_info->corrupt_blocks);
6369                 free_extent_cache_tree(&seen);
6370                 free_extent_cache_tree(&pending);
6371                 free_extent_cache_tree(&reada);
6372                 free_extent_cache_tree(&nodes);
6373                 free_chunk_cache_tree(&chunk_cache);
6374                 free_block_group_tree(&block_group_cache);
6375                 free_device_cache_tree(&dev_cache);
6376                 free_device_extent_tree(&dev_extent_cache);
6377                 free_extent_record_cache(root->fs_info, &extent_cache);
6378                 goto again;
6379         }
6380
6381         err = check_chunks(&chunk_cache, &block_group_cache,
6382                            &dev_extent_cache, NULL, NULL, 0);
6383         if (err && !ret)
6384                 ret = err;
6385
6386         err = check_devices(&dev_cache, &dev_extent_cache);
6387         if (err && !ret)
6388                 ret = err;
6389
6390 out:
6391         if (trans) {
6392                 err = btrfs_commit_transaction(trans, root);
6393                 if (!ret)
6394                         ret = err;
6395         }
6396         if (repair) {
6397                 free_corrupt_blocks_tree(root->fs_info->corrupt_blocks);
6398                 root->fs_info->fsck_extent_cache = NULL;
6399                 root->fs_info->free_extent_hook = NULL;
6400                 root->fs_info->corrupt_blocks = NULL;
6401         }
6402         free(bits);
6403         free_chunk_cache_tree(&chunk_cache);
6404         free_device_cache_tree(&dev_cache);
6405         free_block_group_tree(&block_group_cache);
6406         free_device_extent_tree(&dev_extent_cache);
6407         free_extent_cache_tree(&seen);
6408         free_extent_cache_tree(&pending);
6409         free_extent_cache_tree(&reada);
6410         free_extent_cache_tree(&nodes);
6411         return ret;
6412 }
6413
6414 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
6415                            struct btrfs_root *root, int overwrite)
6416 {
6417         struct extent_buffer *c;
6418         struct extent_buffer *old = root->node;
6419         int level;
6420         int ret;
6421         struct btrfs_disk_key disk_key = {0,0,0};
6422
6423         level = 0;
6424
6425         if (overwrite) {
6426                 c = old;
6427                 extent_buffer_get(c);
6428                 goto init;
6429         }
6430         c = btrfs_alloc_free_block(trans, root,
6431                                    btrfs_level_size(root, 0),
6432                                    root->root_key.objectid,
6433                                    &disk_key, level, 0, 0);
6434         if (IS_ERR(c)) {
6435                 c = old;
6436                 extent_buffer_get(c);
6437                 overwrite = 1;
6438         }
6439 init:
6440         memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header));
6441         btrfs_set_header_level(c, level);
6442         btrfs_set_header_bytenr(c, c->start);
6443         btrfs_set_header_generation(c, trans->transid);
6444         btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV);
6445         btrfs_set_header_owner(c, root->root_key.objectid);
6446
6447         write_extent_buffer(c, root->fs_info->fsid,
6448                             btrfs_header_fsid(), BTRFS_FSID_SIZE);
6449
6450         write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
6451                             btrfs_header_chunk_tree_uuid(c),
6452                             BTRFS_UUID_SIZE);
6453
6454         btrfs_mark_buffer_dirty(c);
6455         /*
6456          * this case can happen in the following case:
6457          *
6458          * 1.overwrite previous root.
6459          *
6460          * 2.reinit reloc data root, this is because we skip pin
6461          * down reloc data tree before which means we can allocate
6462          * same block bytenr here.
6463          */
6464         if (old->start == c->start) {
6465                 btrfs_set_root_generation(&root->root_item,
6466                                           trans->transid);
6467                 root->root_item.level = btrfs_header_level(root->node);
6468                 ret = btrfs_update_root(trans, root->fs_info->tree_root,
6469                                         &root->root_key, &root->root_item);
6470                 if (ret) {
6471                         free_extent_buffer(c);
6472                         return ret;
6473                 }
6474         }
6475         free_extent_buffer(old);
6476         root->node = c;
6477         add_root_to_dirty_list(root);
6478         return 0;
6479 }
6480
6481 static int pin_down_tree_blocks(struct btrfs_fs_info *fs_info,
6482                                 struct extent_buffer *eb, int tree_root)
6483 {
6484         struct extent_buffer *tmp;
6485         struct btrfs_root_item *ri;
6486         struct btrfs_key key;
6487         u64 bytenr;
6488         u32 leafsize;
6489         int level = btrfs_header_level(eb);
6490         int nritems;
6491         int ret;
6492         int i;
6493
6494         /*
6495          * If we have pinned this block before, don't pin it again.
6496          * This can not only avoid forever loop with broken filesystem
6497          * but also give us some speedups.
6498          */
6499         if (test_range_bit(&fs_info->pinned_extents, eb->start,
6500                            eb->start + eb->len - 1, EXTENT_DIRTY, 0))
6501                 return 0;
6502
6503         btrfs_pin_extent(fs_info, eb->start, eb->len);
6504
6505         leafsize = btrfs_super_leafsize(fs_info->super_copy);
6506         nritems = btrfs_header_nritems(eb);
6507         for (i = 0; i < nritems; i++) {
6508                 if (level == 0) {
6509                         btrfs_item_key_to_cpu(eb, &key, i);
6510                         if (key.type != BTRFS_ROOT_ITEM_KEY)
6511                                 continue;
6512                         /* Skip the extent root and reloc roots */
6513                         if (key.objectid == BTRFS_EXTENT_TREE_OBJECTID ||
6514                             key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
6515                             key.objectid == BTRFS_DATA_RELOC_TREE_OBJECTID)
6516                                 continue;
6517                         ri = btrfs_item_ptr(eb, i, struct btrfs_root_item);
6518                         bytenr = btrfs_disk_root_bytenr(eb, ri);
6519
6520                         /*
6521                          * If at any point we start needing the real root we
6522                          * will have to build a stump root for the root we are
6523                          * in, but for now this doesn't actually use the root so
6524                          * just pass in extent_root.
6525                          */
6526                         tmp = read_tree_block(fs_info->extent_root, bytenr,
6527                                               leafsize, 0);
6528                         if (!tmp) {
6529                                 fprintf(stderr, "Error reading root block\n");
6530                                 return -EIO;
6531                         }
6532                         ret = pin_down_tree_blocks(fs_info, tmp, 0);
6533                         free_extent_buffer(tmp);
6534                         if (ret)
6535                                 return ret;
6536                 } else {
6537                         bytenr = btrfs_node_blockptr(eb, i);
6538
6539                         /* If we aren't the tree root don't read the block */
6540                         if (level == 1 && !tree_root) {
6541                                 btrfs_pin_extent(fs_info, bytenr, leafsize);
6542                                 continue;
6543                         }
6544
6545                         tmp = read_tree_block(fs_info->extent_root, bytenr,
6546                                               leafsize, 0);
6547                         if (!tmp) {
6548                                 fprintf(stderr, "Error reading tree block\n");
6549                                 return -EIO;
6550                         }
6551                         ret = pin_down_tree_blocks(fs_info, tmp, tree_root);
6552                         free_extent_buffer(tmp);
6553                         if (ret)
6554                                 return ret;
6555                 }
6556         }
6557
6558         return 0;
6559 }
6560
6561 static int pin_metadata_blocks(struct btrfs_fs_info *fs_info)
6562 {
6563         int ret;
6564
6565         ret = pin_down_tree_blocks(fs_info, fs_info->chunk_root->node, 0);
6566         if (ret)
6567                 return ret;
6568
6569         return pin_down_tree_blocks(fs_info, fs_info->tree_root->node, 1);
6570 }
6571
6572 static int reset_block_groups(struct btrfs_fs_info *fs_info)
6573 {
6574         struct btrfs_block_group_cache *cache;
6575         struct btrfs_path *path;
6576         struct extent_buffer *leaf;
6577         struct btrfs_chunk *chunk;
6578         struct btrfs_key key;
6579         int ret;
6580         u64 start;
6581
6582         path = btrfs_alloc_path();
6583         if (!path)
6584                 return -ENOMEM;
6585
6586         key.objectid = 0;
6587         key.type = BTRFS_CHUNK_ITEM_KEY;
6588         key.offset = 0;
6589
6590         ret = btrfs_search_slot(NULL, fs_info->chunk_root, &key, path, 0, 0);
6591         if (ret < 0) {
6592                 btrfs_free_path(path);
6593                 return ret;
6594         }
6595
6596         /*
6597          * We do this in case the block groups were screwed up and had alloc
6598          * bits that aren't actually set on the chunks.  This happens with
6599          * restored images every time and could happen in real life I guess.
6600          */
6601         fs_info->avail_data_alloc_bits = 0;
6602         fs_info->avail_metadata_alloc_bits = 0;
6603         fs_info->avail_system_alloc_bits = 0;
6604
6605         /* First we need to create the in-memory block groups */
6606         while (1) {
6607                 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
6608                         ret = btrfs_next_leaf(fs_info->chunk_root, path);
6609                         if (ret < 0) {
6610                                 btrfs_free_path(path);
6611                                 return ret;
6612                         }
6613                         if (ret) {
6614                                 ret = 0;
6615                                 break;
6616                         }
6617                 }
6618                 leaf = path->nodes[0];
6619                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
6620                 if (key.type != BTRFS_CHUNK_ITEM_KEY) {
6621                         path->slots[0]++;
6622                         continue;
6623                 }
6624
6625                 chunk = btrfs_item_ptr(leaf, path->slots[0],
6626                                        struct btrfs_chunk);
6627                 btrfs_add_block_group(fs_info, 0,
6628                                       btrfs_chunk_type(leaf, chunk),
6629                                       key.objectid, key.offset,
6630                                       btrfs_chunk_length(leaf, chunk));
6631                 set_extent_dirty(&fs_info->free_space_cache, key.offset,
6632                                  key.offset + btrfs_chunk_length(leaf, chunk),
6633                                  GFP_NOFS);
6634                 path->slots[0]++;
6635         }
6636         start = 0;
6637         while (1) {
6638                 cache = btrfs_lookup_first_block_group(fs_info, start);
6639                 if (!cache)
6640                         break;
6641                 cache->cached = 1;
6642                 start = cache->key.objectid + cache->key.offset;
6643         }
6644
6645         btrfs_free_path(path);
6646         return 0;
6647 }
6648
6649 static int reset_balance(struct btrfs_trans_handle *trans,
6650                          struct btrfs_fs_info *fs_info)
6651 {
6652         struct btrfs_root *root = fs_info->tree_root;
6653         struct btrfs_path *path;
6654         struct extent_buffer *leaf;
6655         struct btrfs_key key;
6656         int del_slot, del_nr = 0;
6657         int ret;
6658         int found = 0;
6659
6660         path = btrfs_alloc_path();
6661         if (!path)
6662                 return -ENOMEM;
6663
6664         key.objectid = BTRFS_BALANCE_OBJECTID;
6665         key.type = BTRFS_BALANCE_ITEM_KEY;
6666         key.offset = 0;
6667
6668         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
6669         if (ret) {
6670                 if (ret > 0)
6671                         ret = 0;
6672                 if (!ret)
6673                         goto reinit_data_reloc;
6674                 else
6675                         goto out;
6676         }
6677
6678         ret = btrfs_del_item(trans, root, path);
6679         if (ret)
6680                 goto out;
6681         btrfs_release_path(path);
6682
6683         key.objectid = BTRFS_TREE_RELOC_OBJECTID;
6684         key.type = BTRFS_ROOT_ITEM_KEY;
6685         key.offset = 0;
6686
6687         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
6688         if (ret < 0)
6689                 goto out;
6690         while (1) {
6691                 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
6692                         if (!found)
6693                                 break;
6694
6695                         if (del_nr) {
6696                                 ret = btrfs_del_items(trans, root, path,
6697                                                       del_slot, del_nr);
6698                                 del_nr = 0;
6699                                 if (ret)
6700                                         goto out;
6701                         }
6702                         key.offset++;
6703                         btrfs_release_path(path);
6704
6705                         found = 0;
6706                         ret = btrfs_search_slot(trans, root, &key, path,
6707                                                 -1, 1);
6708                         if (ret < 0)
6709                                 goto out;
6710                         continue;
6711                 }
6712                 found = 1;
6713                 leaf = path->nodes[0];
6714                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
6715                 if (key.objectid > BTRFS_TREE_RELOC_OBJECTID)
6716                         break;
6717                 if (key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
6718                         path->slots[0]++;
6719                         continue;
6720                 }
6721                 if (!del_nr) {
6722                         del_slot = path->slots[0];
6723                         del_nr = 1;
6724                 } else {
6725                         del_nr++;
6726                 }
6727                 path->slots[0]++;
6728         }
6729
6730         if (del_nr) {
6731                 ret = btrfs_del_items(trans, root, path, del_slot, del_nr);
6732                 if (ret)
6733                         goto out;
6734         }
6735         btrfs_release_path(path);
6736
6737 reinit_data_reloc:
6738         key.objectid = BTRFS_DATA_RELOC_TREE_OBJECTID;
6739         key.type = BTRFS_ROOT_ITEM_KEY;
6740         key.offset = (u64)-1;
6741         root = btrfs_read_fs_root(fs_info, &key);
6742         if (IS_ERR(root)) {
6743                 fprintf(stderr, "Error reading data reloc tree\n");
6744                 return PTR_ERR(root);
6745         }
6746         record_root_in_trans(trans, root);
6747         ret = btrfs_fsck_reinit_root(trans, root, 0);
6748         if (ret)
6749                 goto out;
6750         ret = btrfs_make_root_dir(trans, root, BTRFS_FIRST_FREE_OBJECTID);
6751 out:
6752         btrfs_free_path(path);
6753         return ret;
6754 }
6755
6756 static int reinit_extent_tree(struct btrfs_trans_handle *trans,
6757                               struct btrfs_fs_info *fs_info)
6758 {
6759         u64 start = 0;
6760         int ret;
6761
6762         /*
6763          * The only reason we don't do this is because right now we're just
6764          * walking the trees we find and pinning down their bytes, we don't look
6765          * at any of the leaves.  In order to do mixed groups we'd have to check
6766          * the leaves of any fs roots and pin down the bytes for any file
6767          * extents we find.  Not hard but why do it if we don't have to?
6768          */
6769         if (btrfs_fs_incompat(fs_info, BTRFS_FEATURE_INCOMPAT_MIXED_GROUPS)) {
6770                 fprintf(stderr, "We don't support re-initing the extent tree "
6771                         "for mixed block groups yet, please notify a btrfs "
6772                         "developer you want to do this so they can add this "
6773                         "functionality.\n");
6774                 return -EINVAL;
6775         }
6776
6777         /*
6778          * first we need to walk all of the trees except the extent tree and pin
6779          * down the bytes that are in use so we don't overwrite any existing
6780          * metadata.
6781          */
6782         ret = pin_metadata_blocks(fs_info);
6783         if (ret) {
6784                 fprintf(stderr, "error pinning down used bytes\n");
6785                 return ret;
6786         }
6787
6788         /*
6789          * Need to drop all the block groups since we're going to recreate all
6790          * of them again.
6791          */
6792         btrfs_free_block_groups(fs_info);
6793         ret = reset_block_groups(fs_info);
6794         if (ret) {
6795                 fprintf(stderr, "error resetting the block groups\n");
6796                 return ret;
6797         }
6798
6799         /* Ok we can allocate now, reinit the extent root */
6800         ret = btrfs_fsck_reinit_root(trans, fs_info->extent_root, 0);
6801         if (ret) {
6802                 fprintf(stderr, "extent root initialization failed\n");
6803                 /*
6804                  * When the transaction code is updated we should end the
6805                  * transaction, but for now progs only knows about commit so
6806                  * just return an error.
6807                  */
6808                 return ret;
6809         }
6810
6811         /*
6812          * Now we have all the in-memory block groups setup so we can make
6813          * allocations properly, and the metadata we care about is safe since we
6814          * pinned all of it above.
6815          */
6816         while (1) {
6817                 struct btrfs_block_group_cache *cache;
6818
6819                 cache = btrfs_lookup_first_block_group(fs_info, start);
6820                 if (!cache)
6821                         break;
6822                 start = cache->key.objectid + cache->key.offset;
6823                 ret = btrfs_insert_item(trans, fs_info->extent_root,
6824                                         &cache->key, &cache->item,
6825                                         sizeof(cache->item));
6826                 if (ret) {
6827                         fprintf(stderr, "Error adding block group\n");
6828                         return ret;
6829                 }
6830                 btrfs_extent_post_op(trans, fs_info->extent_root);
6831         }
6832
6833         ret = reset_balance(trans, fs_info);
6834         if (ret)
6835                 fprintf(stderr, "error reseting the pending balance\n");
6836
6837         return ret;
6838 }
6839
6840 static int recow_extent_buffer(struct btrfs_root *root, struct extent_buffer *eb)
6841 {
6842         struct btrfs_path *path;
6843         struct btrfs_trans_handle *trans;
6844         struct btrfs_key key;
6845         int ret;
6846
6847         printf("Recowing metadata block %llu\n", eb->start);
6848         key.objectid = btrfs_header_owner(eb);
6849         key.type = BTRFS_ROOT_ITEM_KEY;
6850         key.offset = (u64)-1;
6851
6852         root = btrfs_read_fs_root(root->fs_info, &key);
6853         if (IS_ERR(root)) {
6854                 fprintf(stderr, "Couldn't find owner root %llu\n",
6855                         key.objectid);
6856                 return PTR_ERR(root);
6857         }
6858
6859         path = btrfs_alloc_path();
6860         if (!path)
6861                 return -ENOMEM;
6862
6863         trans = btrfs_start_transaction(root, 1);
6864         if (IS_ERR(trans)) {
6865                 btrfs_free_path(path);
6866                 return PTR_ERR(trans);
6867         }
6868
6869         path->lowest_level = btrfs_header_level(eb);
6870         if (path->lowest_level)
6871                 btrfs_node_key_to_cpu(eb, &key, 0);
6872         else
6873                 btrfs_item_key_to_cpu(eb, &key, 0);
6874
6875         ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
6876         btrfs_commit_transaction(trans, root);
6877         btrfs_free_path(path);
6878         return ret;
6879 }
6880
6881 static int delete_bad_item(struct btrfs_root *root, struct bad_item *bad)
6882 {
6883         struct btrfs_path *path;
6884         struct btrfs_trans_handle *trans;
6885         struct btrfs_key key;
6886         int ret;
6887
6888         printf("Deleting bad item [%llu,%u,%llu]\n", bad->key.objectid,
6889                bad->key.type, bad->key.offset);
6890         key.objectid = bad->root_id;
6891         key.type = BTRFS_ROOT_ITEM_KEY;
6892         key.offset = (u64)-1;
6893
6894         root = btrfs_read_fs_root(root->fs_info, &key);
6895         if (IS_ERR(root)) {
6896                 fprintf(stderr, "Couldn't find owner root %llu\n",
6897                         key.objectid);
6898                 return PTR_ERR(root);
6899         }
6900
6901         path = btrfs_alloc_path();
6902         if (!path)
6903                 return -ENOMEM;
6904
6905         trans = btrfs_start_transaction(root, 1);
6906         if (IS_ERR(trans)) {
6907                 btrfs_free_path(path);
6908                 return PTR_ERR(trans);
6909         }
6910
6911         ret = btrfs_search_slot(trans, root, &bad->key, path, -1, 1);
6912         if (ret) {
6913                 if (ret > 0)
6914                         ret = 0;
6915                 goto out;
6916         }
6917         ret = btrfs_del_item(trans, root, path);
6918 out:
6919         btrfs_commit_transaction(trans, root);
6920         btrfs_free_path(path);
6921         return ret;
6922 }
6923
6924 static int zero_log_tree(struct btrfs_root *root)
6925 {
6926         struct btrfs_trans_handle *trans;
6927         int ret;
6928
6929         trans = btrfs_start_transaction(root, 1);
6930         if (IS_ERR(trans)) {
6931                 ret = PTR_ERR(trans);
6932                 return ret;
6933         }
6934         btrfs_set_super_log_root(root->fs_info->super_copy, 0);
6935         btrfs_set_super_log_root_level(root->fs_info->super_copy, 0);
6936         ret = btrfs_commit_transaction(trans, root);
6937         return ret;
6938 }
6939
6940 static int populate_csum(struct btrfs_trans_handle *trans,
6941                          struct btrfs_root *csum_root, char *buf, u64 start,
6942                          u64 len)
6943 {
6944         u64 offset = 0;
6945         u64 sectorsize;
6946         int ret = 0;
6947
6948         while (offset < len) {
6949                 sectorsize = csum_root->sectorsize;
6950                 ret = read_extent_data(csum_root, buf, start + offset,
6951                                        &sectorsize, 0);
6952                 if (ret)
6953                         break;
6954                 ret = btrfs_csum_file_block(trans, csum_root, start + len,
6955                                             start + offset, buf, sectorsize);
6956                 if (ret)
6957                         break;
6958                 offset += sectorsize;
6959         }
6960         return ret;
6961 }
6962
6963 static int fill_csum_tree(struct btrfs_trans_handle *trans,
6964                           struct btrfs_root *csum_root)
6965 {
6966         struct btrfs_root *extent_root = csum_root->fs_info->extent_root;
6967         struct btrfs_path *path;
6968         struct btrfs_extent_item *ei;
6969         struct extent_buffer *leaf;
6970         char *buf;
6971         struct btrfs_key key;
6972         int ret;
6973
6974         path = btrfs_alloc_path();
6975         if (!path)
6976                 return -ENOMEM;
6977
6978         key.objectid = 0;
6979         key.type = BTRFS_EXTENT_ITEM_KEY;
6980         key.offset = 0;
6981
6982         ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
6983         if (ret < 0) {
6984                 btrfs_free_path(path);
6985                 return ret;
6986         }
6987
6988         buf = malloc(csum_root->sectorsize);
6989         if (!buf) {
6990                 btrfs_free_path(path);
6991                 return -ENOMEM;
6992         }
6993
6994         while (1) {
6995                 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
6996                         ret = btrfs_next_leaf(extent_root, path);
6997                         if (ret < 0)
6998                                 break;
6999                         if (ret) {
7000                                 ret = 0;
7001                                 break;
7002                         }
7003                 }
7004                 leaf = path->nodes[0];
7005
7006                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
7007                 if (key.type != BTRFS_EXTENT_ITEM_KEY) {
7008                         path->slots[0]++;
7009                         continue;
7010                 }
7011
7012                 ei = btrfs_item_ptr(leaf, path->slots[0],
7013                                     struct btrfs_extent_item);
7014                 if (!(btrfs_extent_flags(leaf, ei) &
7015                       BTRFS_EXTENT_FLAG_DATA)) {
7016                         path->slots[0]++;
7017                         continue;
7018                 }
7019
7020                 ret = populate_csum(trans, csum_root, buf, key.objectid,
7021                                     key.offset);
7022                 if (ret)
7023                         break;
7024                 path->slots[0]++;
7025         }
7026
7027         btrfs_free_path(path);
7028         free(buf);
7029         return ret;
7030 }
7031
7032 static struct option long_options[] = {
7033         { "super", 1, NULL, 's' },
7034         { "repair", 0, NULL, 0 },
7035         { "init-csum-tree", 0, NULL, 0 },
7036         { "init-extent-tree", 0, NULL, 0 },
7037         { "check-data-csum", 0, NULL, 0 },
7038         { "backup", 0, NULL, 0 },
7039         { "subvol-extents", no_argument, NULL, 'E' },
7040         { "qgroup-report", 0, NULL, 'Q' },
7041         { NULL, 0, NULL, 0}
7042 };
7043
7044 const char * const cmd_check_usage[] = {
7045         "btrfs check [options] <device>",
7046         "Check an unmounted btrfs filesystem.",
7047         "",
7048         "-s|--super <superblock>     use this superblock copy",
7049         "-b|--backup                 use the backup root copy",
7050         "--repair                    try to repair the filesystem",
7051         "--init-csum-tree            create a new CRC tree",
7052         "--init-extent-tree          create a new extent tree",
7053         "--check-data-csum           verify checkums of data blocks",
7054         "--qgroup-report             print a report on qgroup consistency",
7055         "--subvol-extents            print subvolume extents and sharing state",
7056         NULL
7057 };
7058
7059 int cmd_check(int argc, char **argv)
7060 {
7061         struct cache_tree root_cache;
7062         struct btrfs_root *root;
7063         struct btrfs_fs_info *info;
7064         u64 bytenr = 0;
7065         u64 subvolid = 0;
7066         char uuidbuf[BTRFS_UUID_UNPARSED_SIZE];
7067         int ret;
7068         u64 num;
7069         int option_index = 0;
7070         int init_csum_tree = 0;
7071         int qgroup_report = 0;
7072         enum btrfs_open_ctree_flags ctree_flags = OPEN_CTREE_EXCLUSIVE;
7073
7074         while(1) {
7075                 int c;
7076                 c = getopt_long(argc, argv, "as:b", long_options,
7077                                 &option_index);
7078                 if (c < 0)
7079                         break;
7080                 switch(c) {
7081                         case 'a': /* ignored */ break;
7082                         case 'b':
7083                                 ctree_flags |= OPEN_CTREE_BACKUP_ROOT;
7084                                 break;
7085                         case 's':
7086                                 num = arg_strtou64(optarg);
7087                                 if (num >= BTRFS_SUPER_MIRROR_MAX) {
7088                                         fprintf(stderr,
7089                                                 "ERROR: super mirror should be less than: %d\n",
7090                                                 BTRFS_SUPER_MIRROR_MAX);
7091                                         exit(1);
7092                                 }
7093                                 bytenr = btrfs_sb_offset(((int)num));
7094                                 printf("using SB copy %llu, bytenr %llu\n", num,
7095                                        (unsigned long long)bytenr);
7096                                 break;
7097                         case 'Q':
7098                                 qgroup_report = 1;
7099                                 break;
7100                         case 'E':
7101                                 subvolid = arg_strtou64(optarg);
7102                                 break;
7103                         case '?':
7104                         case 'h':
7105                                 usage(cmd_check_usage);
7106                 }
7107                 if (option_index == 1) {
7108                         printf("enabling repair mode\n");
7109                         repair = 1;
7110                         ctree_flags |= OPEN_CTREE_WRITES;
7111                 } else if (option_index == 2) {
7112                         printf("Creating a new CRC tree\n");
7113                         init_csum_tree = 1;
7114                         repair = 1;
7115                         ctree_flags |= OPEN_CTREE_WRITES;
7116                 } else if (option_index == 3) {
7117                         init_extent_tree = 1;
7118                         ctree_flags |= (OPEN_CTREE_WRITES |
7119                                         OPEN_CTREE_NO_BLOCK_GROUPS);
7120                         repair = 1;
7121                 } else if (option_index == 4) {
7122                         check_data_csum = 1;
7123                 }
7124         }
7125         argc = argc - optind;
7126
7127         if (check_argc_exact(argc, 1))
7128                 usage(cmd_check_usage);
7129
7130         radix_tree_init();
7131         cache_tree_init(&root_cache);
7132
7133         if((ret = check_mounted(argv[optind])) < 0) {
7134                 fprintf(stderr, "Could not check mount status: %s\n", strerror(-ret));
7135                 goto err_out;
7136         } else if(ret) {
7137                 fprintf(stderr, "%s is currently mounted. Aborting.\n", argv[optind]);
7138                 ret = -EBUSY;
7139                 goto err_out;
7140         }
7141
7142         /* only allow partial opening under repair mode */
7143         if (repair)
7144                 ctree_flags |= OPEN_CTREE_PARTIAL;
7145
7146         info = open_ctree_fs_info(argv[optind], bytenr, 0, ctree_flags);
7147         if (!info) {
7148                 fprintf(stderr, "Couldn't open file system\n");
7149                 ret = -EIO;
7150                 goto err_out;
7151         }
7152
7153         root = info->fs_root;
7154         /*
7155          * repair mode will force us to commit transaction which
7156          * will make us fail to load log tree when mounting.
7157          */
7158         if (repair && btrfs_super_log_root(info->super_copy)) {
7159                 ret = ask_user("repair mode will force to clear out log tree, Are you sure?");
7160                 if (!ret) {
7161                         ret = 1;
7162                         goto close_out;
7163                 }
7164                 ret = zero_log_tree(root);
7165                 if (ret) {
7166                         fprintf(stderr, "fail to zero log tree\n");
7167                         goto close_out;
7168                 }
7169         }
7170
7171         uuid_unparse(info->super_copy->fsid, uuidbuf);
7172         if (qgroup_report) {
7173                 printf("Print quota groups for %s\nUUID: %s\n", argv[optind],
7174                        uuidbuf);
7175                 ret = qgroup_verify_all(info);
7176                 if (ret == 0)
7177                         print_qgroup_report(1);
7178                 goto close_out;
7179         }
7180         if (subvolid) {
7181                 printf("Print extent state for subvolume %llu on %s\nUUID: %s\n",
7182                        subvolid, argv[optind], uuidbuf);
7183                 ret = print_extent_state(info, subvolid);
7184                 goto close_out;
7185         }
7186         printf("Checking filesystem on %s\nUUID: %s\n", argv[optind], uuidbuf);
7187
7188         if (!extent_buffer_uptodate(info->tree_root->node) ||
7189             !extent_buffer_uptodate(info->dev_root->node) ||
7190             !extent_buffer_uptodate(info->chunk_root->node)) {
7191                 fprintf(stderr, "Critical roots corrupted, unable to fsck the FS\n");
7192                 ret = -EIO;
7193                 goto close_out;
7194         }
7195
7196         if (init_extent_tree || init_csum_tree) {
7197                 struct btrfs_trans_handle *trans;
7198
7199                 trans = btrfs_start_transaction(info->extent_root, 0);
7200                 if (IS_ERR(trans)) {
7201                         fprintf(stderr, "Error starting transaction\n");
7202                         ret = PTR_ERR(trans);
7203                         goto close_out;
7204                 }
7205
7206                 if (init_extent_tree) {
7207                         printf("Creating a new extent tree\n");
7208                         ret = reinit_extent_tree(trans, info);
7209                         if (ret)
7210                                 goto close_out;
7211                 }
7212
7213                 if (init_csum_tree) {
7214                         fprintf(stderr, "Reinit crc root\n");
7215                         ret = btrfs_fsck_reinit_root(trans, info->csum_root, 0);
7216                         if (ret) {
7217                                 fprintf(stderr, "crc root initialization failed\n");
7218                                 ret = -EIO;
7219                                 goto close_out;
7220                         }
7221
7222                         ret = fill_csum_tree(trans, info->csum_root);
7223                         if (ret) {
7224                                 fprintf(stderr, "crc refilling failed\n");
7225                                 return -EIO;
7226                         }
7227                 }
7228                 /*
7229                  * Ok now we commit and run the normal fsck, which will add
7230                  * extent entries for all of the items it finds.
7231                  */
7232                 ret = btrfs_commit_transaction(trans, info->extent_root);
7233                 if (ret)
7234                         goto close_out;
7235         }
7236         if (!extent_buffer_uptodate(info->extent_root->node)) {
7237                 fprintf(stderr, "Critical roots corrupted, unable to fsck the FS\n");
7238                 ret = -EIO;
7239                 goto close_out;
7240         }
7241         if (!extent_buffer_uptodate(info->csum_root->node)) {
7242                 fprintf(stderr, "Checksum root corrupted, rerun with --init-csum-tree option\n");
7243                 ret = -EIO;
7244                 goto close_out;
7245         }
7246
7247         fprintf(stderr, "checking extents\n");
7248         ret = check_chunks_and_extents(root);
7249         if (ret)
7250                 fprintf(stderr, "Errors found in extent allocation tree or chunk allocation\n");
7251
7252         fprintf(stderr, "checking free space cache\n");
7253         ret = check_space_cache(root);
7254         if (ret)
7255                 goto out;
7256
7257         /*
7258          * We used to have to have these hole extents in between our real
7259          * extents so if we don't have this flag set we need to make sure there
7260          * are no gaps in the file extents for inodes, otherwise we can just
7261          * ignore it when this happens.
7262          */
7263         no_holes = btrfs_fs_incompat(root->fs_info,
7264                                      BTRFS_FEATURE_INCOMPAT_NO_HOLES);
7265         fprintf(stderr, "checking fs roots\n");
7266         ret = check_fs_roots(root, &root_cache);
7267         if (ret)
7268                 goto out;
7269
7270         fprintf(stderr, "checking csums\n");
7271         ret = check_csums(root);
7272         if (ret)
7273                 goto out;
7274
7275         fprintf(stderr, "checking root refs\n");
7276         ret = check_root_refs(root, &root_cache);
7277         if (ret)
7278                 goto out;
7279
7280         while (repair && !list_empty(&root->fs_info->recow_ebs)) {
7281                 struct extent_buffer *eb;
7282
7283                 eb = list_first_entry(&root->fs_info->recow_ebs,
7284                                       struct extent_buffer, recow);
7285                 list_del_init(&eb->recow);
7286                 ret = recow_extent_buffer(root, eb);
7287                 if (ret)
7288                         break;
7289         }
7290
7291         while (!list_empty(&delete_items)) {
7292                 struct bad_item *bad;
7293
7294                 bad = list_first_entry(&delete_items, struct bad_item, list);
7295                 list_del_init(&bad->list);
7296                 if (repair)
7297                         ret = delete_bad_item(root, bad);
7298                 free(bad);
7299         }
7300
7301         if (info->quota_enabled) {
7302                 int err;
7303                 fprintf(stderr, "checking quota groups\n");
7304                 err = qgroup_verify_all(info);
7305                 if (err)
7306                         goto out;
7307         }
7308
7309         if (!list_empty(&root->fs_info->recow_ebs)) {
7310                 fprintf(stderr, "Transid errors in file system\n");
7311                 ret = 1;
7312         }
7313 out:
7314         print_qgroup_report(0);
7315         if (found_old_backref) { /*
7316                  * there was a disk format change when mixed
7317                  * backref was in testing tree. The old format
7318                  * existed about one week.
7319                  */
7320                 printf("\n * Found old mixed backref format. "
7321                        "The old format is not supported! *"
7322                        "\n * Please mount the FS in readonly mode, "
7323                        "backup data and re-format the FS. *\n\n");
7324                 ret = 1;
7325         }
7326         printf("found %llu bytes used err is %d\n",
7327                (unsigned long long)bytes_used, ret);
7328         printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes);
7329         printf("total tree bytes: %llu\n",
7330                (unsigned long long)total_btree_bytes);
7331         printf("total fs tree bytes: %llu\n",
7332                (unsigned long long)total_fs_tree_bytes);
7333         printf("total extent tree bytes: %llu\n",
7334                (unsigned long long)total_extent_tree_bytes);
7335         printf("btree space waste bytes: %llu\n",
7336                (unsigned long long)btree_space_waste);
7337         printf("file data blocks allocated: %llu\n referenced %llu\n",
7338                 (unsigned long long)data_bytes_allocated,
7339                 (unsigned long long)data_bytes_referenced);
7340         printf("%s\n", BTRFS_BUILD_VERSION);
7341
7342         free_root_recs_tree(&root_cache);
7343 close_out:
7344         close_ctree(root);
7345 err_out:
7346         return ret;
7347 }