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