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 fix_item_offset(struct btrfs_trans_handle *trans,
2838                            struct btrfs_root *root,
2839                            struct extent_buffer *buf)
2840 {
2841         struct btrfs_path *path;
2842         struct btrfs_key k1;
2843         int i;
2844         int level;
2845         int ret;
2846
2847         k1.objectid = btrfs_header_owner(buf);
2848         k1.type = BTRFS_ROOT_ITEM_KEY;
2849         k1.offset = (u64)-1;
2850
2851         root = btrfs_read_fs_root(root->fs_info, &k1);
2852         if (IS_ERR(root))
2853                 return -EIO;
2854
2855         record_root_in_trans(trans, root);
2856
2857         path = btrfs_alloc_path();
2858         if (!path)
2859                 return -EIO;
2860
2861         level = btrfs_header_level(buf);
2862         path->lowest_level = level;
2863         path->skip_check_block = 1;
2864         if (level)
2865                 btrfs_node_key_to_cpu(buf, &k1, 0);
2866         else
2867                 btrfs_item_key_to_cpu(buf, &k1, 0);
2868
2869         ret = btrfs_search_slot(trans, root, &k1, path, 0, 1);
2870         if (ret) {
2871                 btrfs_free_path(path);
2872                 return -EIO;
2873         }
2874
2875         buf = path->nodes[level];
2876         for (i = 0; i < btrfs_header_nritems(buf); i++) {
2877                 unsigned int shift = 0, offset;
2878
2879                 if (i == 0 && btrfs_item_end_nr(buf, i) !=
2880                     BTRFS_LEAF_DATA_SIZE(root)) {
2881                         if (btrfs_item_end_nr(buf, i) >
2882                             BTRFS_LEAF_DATA_SIZE(root)) {
2883                                 fprintf(stderr, "item is off the end of the "
2884                                         "leaf, can't fix\n");
2885                                 ret = -EIO;
2886                                 break;
2887                         }
2888                         shift = BTRFS_LEAF_DATA_SIZE(root) -
2889                                 btrfs_item_end_nr(buf, i);
2890                 } else if (i > 0 && btrfs_item_end_nr(buf, i) !=
2891                            btrfs_item_offset_nr(buf, i - 1)) {
2892                         if (btrfs_item_end_nr(buf, i) >
2893                             btrfs_item_offset_nr(buf, i - 1)) {
2894                                 fprintf(stderr, "items overlap, can't fix\n");
2895                                 ret = -EIO;
2896                                 break;
2897                         }
2898                         shift = btrfs_item_offset_nr(buf, i - 1) -
2899                                 btrfs_item_end_nr(buf, i);
2900                 }
2901                 if (!shift)
2902                         continue;
2903
2904                 printf("Shifting item nr %d by %u bytes in block %llu\n",
2905                        i, shift, (unsigned long long)buf->start);
2906                 offset = btrfs_item_offset_nr(buf, i);
2907                 memmove_extent_buffer(buf,
2908                                       btrfs_leaf_data(buf) + offset + shift,
2909                                       btrfs_leaf_data(buf) + offset,
2910                                       btrfs_item_size_nr(buf, i));
2911                 btrfs_set_item_offset(buf, btrfs_item_nr(i),
2912                                       offset + shift);
2913                 btrfs_mark_buffer_dirty(buf);
2914         }
2915
2916         /*
2917          * We may have moved things, in which case we want to exit so we don't
2918          * write those changes out.  Once we have proper abort functionality in
2919          * progs this can be changed to something nicer.
2920          */
2921         BUG_ON(ret);
2922         btrfs_free_path(path);
2923         return ret;
2924 }
2925
2926 /*
2927  * Attempt to fix basic block failures.  If we can't fix it for whatever reason
2928  * then just return -EIO.
2929  */
2930 static int try_to_fix_bad_block(struct btrfs_trans_handle *trans,
2931                                 struct btrfs_root *root,
2932                                 struct extent_buffer *buf,
2933                                 enum btrfs_tree_block_status status)
2934 {
2935         if (status == BTRFS_TREE_BLOCK_BAD_KEY_ORDER)
2936                 return fix_key_order(trans, root, buf);
2937         if (status == BTRFS_TREE_BLOCK_INVALID_OFFSETS)
2938                 return fix_item_offset(trans, root, buf);
2939         return -EIO;
2940 }
2941
2942 static int check_block(struct btrfs_trans_handle *trans,
2943                        struct btrfs_root *root,
2944                        struct cache_tree *extent_cache,
2945                        struct extent_buffer *buf, u64 flags)
2946 {
2947         struct extent_record *rec;
2948         struct cache_extent *cache;
2949         struct btrfs_key key;
2950         enum btrfs_tree_block_status status;
2951         int ret = 0;
2952         int level;
2953
2954         cache = lookup_cache_extent(extent_cache, buf->start, buf->len);
2955         if (!cache)
2956                 return 1;
2957         rec = container_of(cache, struct extent_record, cache);
2958         rec->generation = btrfs_header_generation(buf);
2959
2960         level = btrfs_header_level(buf);
2961         if (btrfs_header_nritems(buf) > 0) {
2962
2963                 if (level == 0)
2964                         btrfs_item_key_to_cpu(buf, &key, 0);
2965                 else
2966                         btrfs_node_key_to_cpu(buf, &key, 0);
2967
2968                 rec->info_objectid = key.objectid;
2969         }
2970         rec->info_level = level;
2971
2972         if (btrfs_is_leaf(buf))
2973                 status = btrfs_check_leaf(root, &rec->parent_key, buf);
2974         else
2975                 status = btrfs_check_node(root, &rec->parent_key, buf);
2976
2977         if (status != BTRFS_TREE_BLOCK_CLEAN) {
2978                 if (repair)
2979                         status = try_to_fix_bad_block(trans, root, buf,
2980                                                       status);
2981                 if (status != BTRFS_TREE_BLOCK_CLEAN) {
2982                         ret = -EIO;
2983                         fprintf(stderr, "bad block %llu\n",
2984                                 (unsigned long long)buf->start);
2985                 } else {
2986                         /*
2987                          * Signal to callers we need to start the scan over
2988                          * again since we'll have cow'ed blocks.
2989                          */
2990                         ret = -EAGAIN;
2991                 }
2992         } else {
2993                 rec->content_checked = 1;
2994                 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)
2995                         rec->owner_ref_checked = 1;
2996                 else {
2997                         ret = check_owner_ref(root, rec, buf);
2998                         if (!ret)
2999                                 rec->owner_ref_checked = 1;
3000                 }
3001         }
3002         if (!ret)
3003                 maybe_free_extent_rec(extent_cache, rec);
3004         return ret;
3005 }
3006
3007 static struct tree_backref *find_tree_backref(struct extent_record *rec,
3008                                                 u64 parent, u64 root)
3009 {
3010         struct list_head *cur = rec->backrefs.next;
3011         struct extent_backref *node;
3012         struct tree_backref *back;
3013
3014         while(cur != &rec->backrefs) {
3015                 node = list_entry(cur, struct extent_backref, list);
3016                 cur = cur->next;
3017                 if (node->is_data)
3018                         continue;
3019                 back = (struct tree_backref *)node;
3020                 if (parent > 0) {
3021                         if (!node->full_backref)
3022                                 continue;
3023                         if (parent == back->parent)
3024                                 return back;
3025                 } else {
3026                         if (node->full_backref)
3027                                 continue;
3028                         if (back->root == root)
3029                                 return back;
3030                 }
3031         }
3032         return NULL;
3033 }
3034
3035 static struct tree_backref *alloc_tree_backref(struct extent_record *rec,
3036                                                 u64 parent, u64 root)
3037 {
3038         struct tree_backref *ref = malloc(sizeof(*ref));
3039         memset(&ref->node, 0, sizeof(ref->node));
3040         if (parent > 0) {
3041                 ref->parent = parent;
3042                 ref->node.full_backref = 1;
3043         } else {
3044                 ref->root = root;
3045                 ref->node.full_backref = 0;
3046         }
3047         list_add_tail(&ref->node.list, &rec->backrefs);
3048
3049         return ref;
3050 }
3051
3052 static struct data_backref *find_data_backref(struct extent_record *rec,
3053                                                 u64 parent, u64 root,
3054                                                 u64 owner, u64 offset,
3055                                                 int found_ref,
3056                                                 u64 disk_bytenr, u64 bytes)
3057 {
3058         struct list_head *cur = rec->backrefs.next;
3059         struct extent_backref *node;
3060         struct data_backref *back;
3061
3062         while(cur != &rec->backrefs) {
3063                 node = list_entry(cur, struct extent_backref, list);
3064                 cur = cur->next;
3065                 if (!node->is_data)
3066                         continue;
3067                 back = (struct data_backref *)node;
3068                 if (parent > 0) {
3069                         if (!node->full_backref)
3070                                 continue;
3071                         if (parent == back->parent)
3072                                 return back;
3073                 } else {
3074                         if (node->full_backref)
3075                                 continue;
3076                         if (back->root == root && back->owner == owner &&
3077                             back->offset == offset) {
3078                                 if (found_ref && node->found_ref &&
3079                                     (back->bytes != bytes ||
3080                                     back->disk_bytenr != disk_bytenr))
3081                                         continue;
3082                                 return back;
3083                         }
3084                 }
3085         }
3086         return NULL;
3087 }
3088
3089 static struct data_backref *alloc_data_backref(struct extent_record *rec,
3090                                                 u64 parent, u64 root,
3091                                                 u64 owner, u64 offset,
3092                                                 u64 max_size)
3093 {
3094         struct data_backref *ref = malloc(sizeof(*ref));
3095         memset(&ref->node, 0, sizeof(ref->node));
3096         ref->node.is_data = 1;
3097
3098         if (parent > 0) {
3099                 ref->parent = parent;
3100                 ref->owner = 0;
3101                 ref->offset = 0;
3102                 ref->node.full_backref = 1;
3103         } else {
3104                 ref->root = root;
3105                 ref->owner = owner;
3106                 ref->offset = offset;
3107                 ref->node.full_backref = 0;
3108         }
3109         ref->bytes = max_size;
3110         ref->found_ref = 0;
3111         ref->num_refs = 0;
3112         list_add_tail(&ref->node.list, &rec->backrefs);
3113         if (max_size > rec->max_size)
3114                 rec->max_size = max_size;
3115         return ref;
3116 }
3117
3118 static int add_extent_rec(struct cache_tree *extent_cache,
3119                           struct btrfs_key *parent_key, u64 parent_gen,
3120                           u64 start, u64 nr, u64 extent_item_refs,
3121                           int is_root, int inc_ref, int set_checked,
3122                           int metadata, int extent_rec, u64 max_size)
3123 {
3124         struct extent_record *rec;
3125         struct cache_extent *cache;
3126         int ret = 0;
3127         int dup = 0;
3128
3129         cache = lookup_cache_extent(extent_cache, start, nr);
3130         if (cache) {
3131                 rec = container_of(cache, struct extent_record, cache);
3132                 if (inc_ref)
3133                         rec->refs++;
3134                 if (rec->nr == 1)
3135                         rec->nr = max(nr, max_size);
3136
3137                 /*
3138                  * We need to make sure to reset nr to whatever the extent
3139                  * record says was the real size, this way we can compare it to
3140                  * the backrefs.
3141                  */
3142                 if (extent_rec) {
3143                         if (start != rec->start || rec->found_rec) {
3144                                 struct extent_record *tmp;
3145
3146                                 dup = 1;
3147                                 if (list_empty(&rec->list))
3148                                         list_add_tail(&rec->list,
3149                                                       &duplicate_extents);
3150
3151                                 /*
3152                                  * We have to do this song and dance in case we
3153                                  * find an extent record that falls inside of
3154                                  * our current extent record but does not have
3155                                  * the same objectid.
3156                                  */
3157                                 tmp = malloc(sizeof(*tmp));
3158                                 if (!tmp)
3159                                         return -ENOMEM;
3160                                 tmp->start = start;
3161                                 tmp->max_size = max_size;
3162                                 tmp->nr = nr;
3163                                 tmp->found_rec = 1;
3164                                 tmp->metadata = metadata;
3165                                 tmp->extent_item_refs = extent_item_refs;
3166                                 INIT_LIST_HEAD(&tmp->list);
3167                                 list_add_tail(&tmp->list, &rec->dups);
3168                                 rec->num_duplicates++;
3169                         } else {
3170                                 rec->nr = nr;
3171                                 rec->found_rec = 1;
3172                         }
3173                 }
3174
3175                 if (extent_item_refs && !dup) {
3176                         if (rec->extent_item_refs) {
3177                                 fprintf(stderr, "block %llu rec "
3178                                         "extent_item_refs %llu, passed %llu\n",
3179                                         (unsigned long long)start,
3180                                         (unsigned long long)
3181                                                         rec->extent_item_refs,
3182                                         (unsigned long long)extent_item_refs);
3183                         }
3184                         rec->extent_item_refs = extent_item_refs;
3185                 }
3186                 if (is_root)
3187                         rec->is_root = 1;
3188                 if (set_checked) {
3189                         rec->content_checked = 1;
3190                         rec->owner_ref_checked = 1;
3191                 }
3192
3193                 if (parent_key)
3194                         btrfs_cpu_key_to_disk(&rec->parent_key, parent_key);
3195                 if (parent_gen)
3196                         rec->parent_generation = parent_gen;
3197
3198                 if (rec->max_size < max_size)
3199                         rec->max_size = max_size;
3200
3201                 maybe_free_extent_rec(extent_cache, rec);
3202                 return ret;
3203         }
3204         rec = malloc(sizeof(*rec));
3205         rec->start = start;
3206         rec->max_size = max_size;
3207         rec->nr = max(nr, max_size);
3208         rec->found_rec = !!extent_rec;
3209         rec->content_checked = 0;
3210         rec->owner_ref_checked = 0;
3211         rec->num_duplicates = 0;
3212         rec->metadata = metadata;
3213         INIT_LIST_HEAD(&rec->backrefs);
3214         INIT_LIST_HEAD(&rec->dups);
3215         INIT_LIST_HEAD(&rec->list);
3216
3217         if (is_root)
3218                 rec->is_root = 1;
3219         else
3220                 rec->is_root = 0;
3221
3222         if (inc_ref)
3223                 rec->refs = 1;
3224         else
3225                 rec->refs = 0;
3226
3227         if (extent_item_refs)
3228                 rec->extent_item_refs = extent_item_refs;
3229         else
3230                 rec->extent_item_refs = 0;
3231
3232         if (parent_key)
3233                 btrfs_cpu_key_to_disk(&rec->parent_key, parent_key);
3234         else
3235                 memset(&rec->parent_key, 0, sizeof(*parent_key));
3236
3237         if (parent_gen)
3238                 rec->parent_generation = parent_gen;
3239         else
3240                 rec->parent_generation = 0;
3241
3242         rec->cache.start = start;
3243         rec->cache.size = nr;
3244         ret = insert_cache_extent(extent_cache, &rec->cache);
3245         BUG_ON(ret);
3246         bytes_used += nr;
3247         if (set_checked) {
3248                 rec->content_checked = 1;
3249                 rec->owner_ref_checked = 1;
3250         }
3251         return ret;
3252 }
3253
3254 static int add_tree_backref(struct cache_tree *extent_cache, u64 bytenr,
3255                             u64 parent, u64 root, int found_ref)
3256 {
3257         struct extent_record *rec;
3258         struct tree_backref *back;
3259         struct cache_extent *cache;
3260
3261         cache = lookup_cache_extent(extent_cache, bytenr, 1);
3262         if (!cache) {
3263                 add_extent_rec(extent_cache, NULL, 0, bytenr,
3264                                1, 0, 0, 0, 0, 1, 0, 0);
3265                 cache = lookup_cache_extent(extent_cache, bytenr, 1);
3266                 if (!cache)
3267                         abort();
3268         }
3269
3270         rec = container_of(cache, struct extent_record, cache);
3271         if (rec->start != bytenr) {
3272                 abort();
3273         }
3274
3275         back = find_tree_backref(rec, parent, root);
3276         if (!back)
3277                 back = alloc_tree_backref(rec, parent, root);
3278
3279         if (found_ref) {
3280                 if (back->node.found_ref) {
3281                         fprintf(stderr, "Extent back ref already exists "
3282                                 "for %llu parent %llu root %llu \n",
3283                                 (unsigned long long)bytenr,
3284                                 (unsigned long long)parent,
3285                                 (unsigned long long)root);
3286                 }
3287                 back->node.found_ref = 1;
3288         } else {
3289                 if (back->node.found_extent_tree) {
3290                         fprintf(stderr, "Extent back ref already exists "
3291                                 "for %llu parent %llu root %llu \n",
3292                                 (unsigned long long)bytenr,
3293                                 (unsigned long long)parent,
3294                                 (unsigned long long)root);
3295                 }
3296                 back->node.found_extent_tree = 1;
3297         }
3298         maybe_free_extent_rec(extent_cache, rec);
3299         return 0;
3300 }
3301
3302 static int add_data_backref(struct cache_tree *extent_cache, u64 bytenr,
3303                             u64 parent, u64 root, u64 owner, u64 offset,
3304                             u32 num_refs, int found_ref, u64 max_size)
3305 {
3306         struct extent_record *rec;
3307         struct data_backref *back;
3308         struct cache_extent *cache;
3309
3310         cache = lookup_cache_extent(extent_cache, bytenr, 1);
3311         if (!cache) {
3312                 add_extent_rec(extent_cache, NULL, 0, bytenr, 1, 0, 0, 0, 0,
3313                                0, 0, max_size);
3314                 cache = lookup_cache_extent(extent_cache, bytenr, 1);
3315                 if (!cache)
3316                         abort();
3317         }
3318
3319         rec = container_of(cache, struct extent_record, cache);
3320         if (rec->max_size < max_size)
3321                 rec->max_size = max_size;
3322
3323         /*
3324          * If found_ref is set then max_size is the real size and must match the
3325          * existing refs.  So if we have already found a ref then we need to
3326          * make sure that this ref matches the existing one, otherwise we need
3327          * to add a new backref so we can notice that the backrefs don't match
3328          * and we need to figure out who is telling the truth.  This is to
3329          * account for that awful fsync bug I introduced where we'd end up with
3330          * a btrfs_file_extent_item that would have its length include multiple
3331          * prealloc extents or point inside of a prealloc extent.
3332          */
3333         back = find_data_backref(rec, parent, root, owner, offset, found_ref,
3334                                  bytenr, max_size);
3335         if (!back)
3336                 back = alloc_data_backref(rec, parent, root, owner, offset,
3337                                           max_size);
3338
3339         if (found_ref) {
3340                 BUG_ON(num_refs != 1);
3341                 if (back->node.found_ref)
3342                         BUG_ON(back->bytes != max_size);
3343                 back->node.found_ref = 1;
3344                 back->found_ref += 1;
3345                 back->bytes = max_size;
3346                 back->disk_bytenr = bytenr;
3347                 rec->refs += 1;
3348                 rec->content_checked = 1;
3349                 rec->owner_ref_checked = 1;
3350         } else {
3351                 if (back->node.found_extent_tree) {
3352                         fprintf(stderr, "Extent back ref already exists "
3353                                 "for %llu parent %llu root %llu "
3354                                 "owner %llu offset %llu num_refs %lu\n",
3355                                 (unsigned long long)bytenr,
3356                                 (unsigned long long)parent,
3357                                 (unsigned long long)root,
3358                                 (unsigned long long)owner,
3359                                 (unsigned long long)offset,
3360                                 (unsigned long)num_refs);
3361                 }
3362                 back->num_refs = num_refs;
3363                 back->node.found_extent_tree = 1;
3364         }
3365         maybe_free_extent_rec(extent_cache, rec);
3366         return 0;
3367 }
3368
3369 static int add_pending(struct cache_tree *pending,
3370                        struct cache_tree *seen, u64 bytenr, u32 size)
3371 {
3372         int ret;
3373         ret = add_cache_extent(seen, bytenr, size);
3374         if (ret)
3375                 return ret;
3376         add_cache_extent(pending, bytenr, size);
3377         return 0;
3378 }
3379
3380 static int pick_next_pending(struct cache_tree *pending,
3381                         struct cache_tree *reada,
3382                         struct cache_tree *nodes,
3383                         u64 last, struct block_info *bits, int bits_nr,
3384                         int *reada_bits)
3385 {
3386         unsigned long node_start = last;
3387         struct cache_extent *cache;
3388         int ret;
3389
3390         cache = search_cache_extent(reada, 0);
3391         if (cache) {
3392                 bits[0].start = cache->start;
3393                 bits[0].size = cache->size;
3394                 *reada_bits = 1;
3395                 return 1;
3396         }
3397         *reada_bits = 0;
3398         if (node_start > 32768)
3399                 node_start -= 32768;
3400
3401         cache = search_cache_extent(nodes, node_start);
3402         if (!cache)
3403                 cache = search_cache_extent(nodes, 0);
3404
3405         if (!cache) {
3406                  cache = search_cache_extent(pending, 0);
3407                  if (!cache)
3408                          return 0;
3409                  ret = 0;
3410                  do {
3411                          bits[ret].start = cache->start;
3412                          bits[ret].size = cache->size;
3413                          cache = next_cache_extent(cache);
3414                          ret++;
3415                  } while (cache && ret < bits_nr);
3416                  return ret;
3417         }
3418
3419         ret = 0;
3420         do {
3421                 bits[ret].start = cache->start;
3422                 bits[ret].size = cache->size;
3423                 cache = next_cache_extent(cache);
3424                 ret++;
3425         } while (cache && ret < bits_nr);
3426
3427         if (bits_nr - ret > 8) {
3428                 u64 lookup = bits[0].start + bits[0].size;
3429                 struct cache_extent *next;
3430                 next = search_cache_extent(pending, lookup);
3431                 while(next) {
3432                         if (next->start - lookup > 32768)
3433                                 break;
3434                         bits[ret].start = next->start;
3435                         bits[ret].size = next->size;
3436                         lookup = next->start + next->size;
3437                         ret++;
3438                         if (ret == bits_nr)
3439                                 break;
3440                         next = next_cache_extent(next);
3441                         if (!next)
3442                                 break;
3443                 }
3444         }
3445         return ret;
3446 }
3447
3448 static void free_chunk_record(struct cache_extent *cache)
3449 {
3450         struct chunk_record *rec;
3451
3452         rec = container_of(cache, struct chunk_record, cache);
3453         list_del_init(&rec->list);
3454         list_del_init(&rec->dextents);
3455         free(rec);
3456 }
3457
3458 void free_chunk_cache_tree(struct cache_tree *chunk_cache)
3459 {
3460         cache_tree_free_extents(chunk_cache, free_chunk_record);
3461 }
3462
3463 static void free_device_record(struct rb_node *node)
3464 {
3465         struct device_record *rec;
3466
3467         rec = container_of(node, struct device_record, node);
3468         free(rec);
3469 }
3470
3471 FREE_RB_BASED_TREE(device_cache, free_device_record);
3472
3473 int insert_block_group_record(struct block_group_tree *tree,
3474                               struct block_group_record *bg_rec)
3475 {
3476         int ret;
3477
3478         ret = insert_cache_extent(&tree->tree, &bg_rec->cache);
3479         if (ret)
3480                 return ret;
3481
3482         list_add_tail(&bg_rec->list, &tree->block_groups);
3483         return 0;
3484 }
3485
3486 static void free_block_group_record(struct cache_extent *cache)
3487 {
3488         struct block_group_record *rec;
3489
3490         rec = container_of(cache, struct block_group_record, cache);
3491         list_del_init(&rec->list);
3492         free(rec);
3493 }
3494
3495 void free_block_group_tree(struct block_group_tree *tree)
3496 {
3497         cache_tree_free_extents(&tree->tree, free_block_group_record);
3498 }
3499
3500 int insert_device_extent_record(struct device_extent_tree *tree,
3501                                 struct device_extent_record *de_rec)
3502 {
3503         int ret;
3504
3505         /*
3506          * Device extent is a bit different from the other extents, because
3507          * the extents which belong to the different devices may have the
3508          * same start and size, so we need use the special extent cache
3509          * search/insert functions.
3510          */
3511         ret = insert_cache_extent2(&tree->tree, &de_rec->cache);
3512         if (ret)
3513                 return ret;
3514
3515         list_add_tail(&de_rec->chunk_list, &tree->no_chunk_orphans);
3516         list_add_tail(&de_rec->device_list, &tree->no_device_orphans);
3517         return 0;
3518 }
3519
3520 static void free_device_extent_record(struct cache_extent *cache)
3521 {
3522         struct device_extent_record *rec;
3523
3524         rec = container_of(cache, struct device_extent_record, cache);
3525         if (!list_empty(&rec->chunk_list))
3526                 list_del_init(&rec->chunk_list);
3527         if (!list_empty(&rec->device_list))
3528                 list_del_init(&rec->device_list);
3529         free(rec);
3530 }
3531
3532 void free_device_extent_tree(struct device_extent_tree *tree)
3533 {
3534         cache_tree_free_extents(&tree->tree, free_device_extent_record);
3535 }
3536
3537 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
3538 static int process_extent_ref_v0(struct cache_tree *extent_cache,
3539                                  struct extent_buffer *leaf, int slot)
3540 {
3541         struct btrfs_extent_ref_v0 *ref0;
3542         struct btrfs_key key;
3543
3544         btrfs_item_key_to_cpu(leaf, &key, slot);
3545         ref0 = btrfs_item_ptr(leaf, slot, struct btrfs_extent_ref_v0);
3546         if (btrfs_ref_objectid_v0(leaf, ref0) < BTRFS_FIRST_FREE_OBJECTID) {
3547                 add_tree_backref(extent_cache, key.objectid, key.offset, 0, 0);
3548         } else {
3549                 add_data_backref(extent_cache, key.objectid, key.offset, 0,
3550                                  0, 0, btrfs_ref_count_v0(leaf, ref0), 0, 0);
3551         }
3552         return 0;
3553 }
3554 #endif
3555
3556 struct chunk_record *btrfs_new_chunk_record(struct extent_buffer *leaf,
3557                                             struct btrfs_key *key,
3558                                             int slot)
3559 {
3560         struct btrfs_chunk *ptr;
3561         struct chunk_record *rec;
3562         int num_stripes, i;
3563
3564         ptr = btrfs_item_ptr(leaf, slot, struct btrfs_chunk);
3565         num_stripes = btrfs_chunk_num_stripes(leaf, ptr);
3566
3567         rec = malloc(btrfs_chunk_record_size(num_stripes));
3568         if (!rec) {
3569                 fprintf(stderr, "memory allocation failed\n");
3570                 exit(-1);
3571         }
3572
3573         memset(rec, 0, btrfs_chunk_record_size(num_stripes));
3574
3575         INIT_LIST_HEAD(&rec->list);
3576         INIT_LIST_HEAD(&rec->dextents);
3577         rec->bg_rec = NULL;
3578
3579         rec->cache.start = key->offset;
3580         rec->cache.size = btrfs_chunk_length(leaf, ptr);
3581
3582         rec->generation = btrfs_header_generation(leaf);
3583
3584         rec->objectid = key->objectid;
3585         rec->type = key->type;
3586         rec->offset = key->offset;
3587
3588         rec->length = rec->cache.size;
3589         rec->owner = btrfs_chunk_owner(leaf, ptr);
3590         rec->stripe_len = btrfs_chunk_stripe_len(leaf, ptr);
3591         rec->type_flags = btrfs_chunk_type(leaf, ptr);
3592         rec->io_width = btrfs_chunk_io_width(leaf, ptr);
3593         rec->io_align = btrfs_chunk_io_align(leaf, ptr);
3594         rec->sector_size = btrfs_chunk_sector_size(leaf, ptr);
3595         rec->num_stripes = num_stripes;
3596         rec->sub_stripes = btrfs_chunk_sub_stripes(leaf, ptr);
3597
3598         for (i = 0; i < rec->num_stripes; ++i) {
3599                 rec->stripes[i].devid =
3600                         btrfs_stripe_devid_nr(leaf, ptr, i);
3601                 rec->stripes[i].offset =
3602                         btrfs_stripe_offset_nr(leaf, ptr, i);
3603                 read_extent_buffer(leaf, rec->stripes[i].dev_uuid,
3604                                 (unsigned long)btrfs_stripe_dev_uuid_nr(ptr, i),
3605                                 BTRFS_UUID_SIZE);
3606         }
3607
3608         return rec;
3609 }
3610
3611 static int process_chunk_item(struct cache_tree *chunk_cache,
3612                               struct btrfs_key *key, struct extent_buffer *eb,
3613                               int slot)
3614 {
3615         struct chunk_record *rec;
3616         int ret = 0;
3617
3618         rec = btrfs_new_chunk_record(eb, key, slot);
3619         ret = insert_cache_extent(chunk_cache, &rec->cache);
3620         if (ret) {
3621                 fprintf(stderr, "Chunk[%llu, %llu] existed.\n",
3622                         rec->offset, rec->length);
3623                 free(rec);
3624         }
3625
3626         return ret;
3627 }
3628
3629 static int process_device_item(struct rb_root *dev_cache,
3630                 struct btrfs_key *key, struct extent_buffer *eb, int slot)
3631 {
3632         struct btrfs_dev_item *ptr;
3633         struct device_record *rec;
3634         int ret = 0;
3635
3636         ptr = btrfs_item_ptr(eb,
3637                 slot, struct btrfs_dev_item);
3638
3639         rec = malloc(sizeof(*rec));
3640         if (!rec) {
3641                 fprintf(stderr, "memory allocation failed\n");
3642                 return -ENOMEM;
3643         }
3644
3645         rec->devid = key->offset;
3646         rec->generation = btrfs_header_generation(eb);
3647
3648         rec->objectid = key->objectid;
3649         rec->type = key->type;
3650         rec->offset = key->offset;
3651
3652         rec->devid = btrfs_device_id(eb, ptr);
3653         rec->total_byte = btrfs_device_total_bytes(eb, ptr);
3654         rec->byte_used = btrfs_device_bytes_used(eb, ptr);
3655
3656         ret = rb_insert(dev_cache, &rec->node, device_record_compare);
3657         if (ret) {
3658                 fprintf(stderr, "Device[%llu] existed.\n", rec->devid);
3659                 free(rec);
3660         }
3661
3662         return ret;
3663 }
3664
3665 struct block_group_record *
3666 btrfs_new_block_group_record(struct extent_buffer *leaf, struct btrfs_key *key,
3667                              int slot)
3668 {
3669         struct btrfs_block_group_item *ptr;
3670         struct block_group_record *rec;
3671
3672         rec = malloc(sizeof(*rec));
3673         if (!rec) {
3674                 fprintf(stderr, "memory allocation failed\n");
3675                 exit(-1);
3676         }
3677         memset(rec, 0, sizeof(*rec));
3678
3679         rec->cache.start = key->objectid;
3680         rec->cache.size = key->offset;
3681
3682         rec->generation = btrfs_header_generation(leaf);
3683
3684         rec->objectid = key->objectid;
3685         rec->type = key->type;
3686         rec->offset = key->offset;
3687
3688         ptr = btrfs_item_ptr(leaf, slot, struct btrfs_block_group_item);
3689         rec->flags = btrfs_disk_block_group_flags(leaf, ptr);
3690
3691         INIT_LIST_HEAD(&rec->list);
3692
3693         return rec;
3694 }
3695
3696 static int process_block_group_item(struct block_group_tree *block_group_cache,
3697                                     struct btrfs_key *key,
3698                                     struct extent_buffer *eb, int slot)
3699 {
3700         struct block_group_record *rec;
3701         int ret = 0;
3702
3703         rec = btrfs_new_block_group_record(eb, key, slot);
3704         ret = insert_block_group_record(block_group_cache, rec);
3705         if (ret) {
3706                 fprintf(stderr, "Block Group[%llu, %llu] existed.\n",
3707                         rec->objectid, rec->offset);
3708                 free(rec);
3709         }
3710
3711         return ret;
3712 }
3713
3714 struct device_extent_record *
3715 btrfs_new_device_extent_record(struct extent_buffer *leaf,
3716                                struct btrfs_key *key, int slot)
3717 {
3718         struct device_extent_record *rec;
3719         struct btrfs_dev_extent *ptr;
3720
3721         rec = malloc(sizeof(*rec));
3722         if (!rec) {
3723                 fprintf(stderr, "memory allocation failed\n");
3724                 exit(-1);
3725         }
3726         memset(rec, 0, sizeof(*rec));
3727
3728         rec->cache.objectid = key->objectid;
3729         rec->cache.start = key->offset;
3730
3731         rec->generation = btrfs_header_generation(leaf);
3732
3733         rec->objectid = key->objectid;
3734         rec->type = key->type;
3735         rec->offset = key->offset;
3736
3737         ptr = btrfs_item_ptr(leaf, slot, struct btrfs_dev_extent);
3738         rec->chunk_objecteid =
3739                 btrfs_dev_extent_chunk_objectid(leaf, ptr);
3740         rec->chunk_offset =
3741                 btrfs_dev_extent_chunk_offset(leaf, ptr);
3742         rec->length = btrfs_dev_extent_length(leaf, ptr);
3743         rec->cache.size = rec->length;
3744
3745         INIT_LIST_HEAD(&rec->chunk_list);
3746         INIT_LIST_HEAD(&rec->device_list);
3747
3748         return rec;
3749 }
3750
3751 static int
3752 process_device_extent_item(struct device_extent_tree *dev_extent_cache,
3753                            struct btrfs_key *key, struct extent_buffer *eb,
3754                            int slot)
3755 {
3756         struct device_extent_record *rec;
3757         int ret;
3758
3759         rec = btrfs_new_device_extent_record(eb, key, slot);
3760         ret = insert_device_extent_record(dev_extent_cache, rec);
3761         if (ret) {
3762                 fprintf(stderr,
3763                         "Device extent[%llu, %llu, %llu] existed.\n",
3764                         rec->objectid, rec->offset, rec->length);
3765                 free(rec);
3766         }
3767
3768         return ret;
3769 }
3770
3771 static int process_extent_item(struct btrfs_root *root,
3772                                struct cache_tree *extent_cache,
3773                                struct extent_buffer *eb, int slot)
3774 {
3775         struct btrfs_extent_item *ei;
3776         struct btrfs_extent_inline_ref *iref;
3777         struct btrfs_extent_data_ref *dref;
3778         struct btrfs_shared_data_ref *sref;
3779         struct btrfs_key key;
3780         unsigned long end;
3781         unsigned long ptr;
3782         int type;
3783         u32 item_size = btrfs_item_size_nr(eb, slot);
3784         u64 refs = 0;
3785         u64 offset;
3786         u64 num_bytes;
3787         int metadata = 0;
3788
3789         btrfs_item_key_to_cpu(eb, &key, slot);
3790
3791         if (key.type == BTRFS_METADATA_ITEM_KEY) {
3792                 metadata = 1;
3793                 num_bytes = root->leafsize;
3794         } else {
3795                 num_bytes = key.offset;
3796         }
3797
3798         if (item_size < sizeof(*ei)) {
3799 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
3800                 struct btrfs_extent_item_v0 *ei0;
3801                 BUG_ON(item_size != sizeof(*ei0));
3802                 ei0 = btrfs_item_ptr(eb, slot, struct btrfs_extent_item_v0);
3803                 refs = btrfs_extent_refs_v0(eb, ei0);
3804 #else
3805                 BUG();
3806 #endif
3807                 return add_extent_rec(extent_cache, NULL, 0, key.objectid,
3808                                       num_bytes, refs, 0, 0, 0, metadata, 1,
3809                                       num_bytes);
3810         }
3811
3812         ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
3813         refs = btrfs_extent_refs(eb, ei);
3814
3815         add_extent_rec(extent_cache, NULL, 0, key.objectid, num_bytes,
3816                        refs, 0, 0, 0, metadata, 1, num_bytes);
3817
3818         ptr = (unsigned long)(ei + 1);
3819         if (btrfs_extent_flags(eb, ei) & BTRFS_EXTENT_FLAG_TREE_BLOCK &&
3820             key.type == BTRFS_EXTENT_ITEM_KEY)
3821                 ptr += sizeof(struct btrfs_tree_block_info);
3822
3823         end = (unsigned long)ei + item_size;
3824         while (ptr < end) {
3825                 iref = (struct btrfs_extent_inline_ref *)ptr;
3826                 type = btrfs_extent_inline_ref_type(eb, iref);
3827                 offset = btrfs_extent_inline_ref_offset(eb, iref);
3828                 switch (type) {
3829                 case BTRFS_TREE_BLOCK_REF_KEY:
3830                         add_tree_backref(extent_cache, key.objectid,
3831                                          0, offset, 0);
3832                         break;
3833                 case BTRFS_SHARED_BLOCK_REF_KEY:
3834                         add_tree_backref(extent_cache, key.objectid,
3835                                          offset, 0, 0);
3836                         break;
3837                 case BTRFS_EXTENT_DATA_REF_KEY:
3838                         dref = (struct btrfs_extent_data_ref *)(&iref->offset);
3839                         add_data_backref(extent_cache, key.objectid, 0,
3840                                         btrfs_extent_data_ref_root(eb, dref),
3841                                         btrfs_extent_data_ref_objectid(eb,
3842                                                                        dref),
3843                                         btrfs_extent_data_ref_offset(eb, dref),
3844                                         btrfs_extent_data_ref_count(eb, dref),
3845                                         0, num_bytes);
3846                         break;
3847                 case BTRFS_SHARED_DATA_REF_KEY:
3848                         sref = (struct btrfs_shared_data_ref *)(iref + 1);
3849                         add_data_backref(extent_cache, key.objectid, offset,
3850                                         0, 0, 0,
3851                                         btrfs_shared_data_ref_count(eb, sref),
3852                                         0, num_bytes);
3853                         break;
3854                 default:
3855                         fprintf(stderr, "corrupt extent record: key %Lu %u %Lu\n",
3856                                 key.objectid, key.type, num_bytes);
3857                         goto out;
3858                 }
3859                 ptr += btrfs_extent_inline_ref_size(type);
3860         }
3861         WARN_ON(ptr > end);
3862 out:
3863         return 0;
3864 }
3865
3866 static int check_cache_range(struct btrfs_root *root,
3867                              struct btrfs_block_group_cache *cache,
3868                              u64 offset, u64 bytes)
3869 {
3870         struct btrfs_free_space *entry;
3871         u64 *logical;
3872         u64 bytenr;
3873         int stripe_len;
3874         int i, nr, ret;
3875
3876         for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
3877                 bytenr = btrfs_sb_offset(i);
3878                 ret = btrfs_rmap_block(&root->fs_info->mapping_tree,
3879                                        cache->key.objectid, bytenr, 0,
3880                                        &logical, &nr, &stripe_len);
3881                 if (ret)
3882                         return ret;
3883
3884                 while (nr--) {
3885                         if (logical[nr] + stripe_len <= offset)
3886                                 continue;
3887                         if (offset + bytes <= logical[nr])
3888                                 continue;
3889                         if (logical[nr] == offset) {
3890                                 if (stripe_len >= bytes) {
3891                                         kfree(logical);
3892                                         return 0;
3893                                 }
3894                                 bytes -= stripe_len;
3895                                 offset += stripe_len;
3896                         } else if (logical[nr] < offset) {
3897                                 if (logical[nr] + stripe_len >=
3898                                     offset + bytes) {
3899                                         kfree(logical);
3900                                         return 0;
3901                                 }
3902                                 bytes = (offset + bytes) -
3903                                         (logical[nr] + stripe_len);
3904                                 offset = logical[nr] + stripe_len;
3905                         } else {
3906                                 /*
3907                                  * Could be tricky, the super may land in the
3908                                  * middle of the area we're checking.  First
3909                                  * check the easiest case, it's at the end.
3910                                  */
3911                                 if (logical[nr] + stripe_len >=
3912                                     bytes + offset) {
3913                                         bytes = logical[nr] - offset;
3914                                         continue;
3915                                 }
3916
3917                                 /* Check the left side */
3918                                 ret = check_cache_range(root, cache,
3919                                                         offset,
3920                                                         logical[nr] - offset);
3921                                 if (ret) {
3922                                         kfree(logical);
3923                                         return ret;
3924                                 }
3925
3926                                 /* Now we continue with the right side */
3927                                 bytes = (offset + bytes) -
3928                                         (logical[nr] + stripe_len);
3929                                 offset = logical[nr] + stripe_len;
3930                         }
3931                 }
3932
3933                 kfree(logical);
3934         }
3935
3936         entry = btrfs_find_free_space(cache->free_space_ctl, offset, bytes);
3937         if (!entry) {
3938                 fprintf(stderr, "There is no free space entry for %Lu-%Lu\n",
3939                         offset, offset+bytes);
3940                 return -EINVAL;
3941         }
3942
3943         if (entry->offset != offset) {
3944                 fprintf(stderr, "Wanted offset %Lu, found %Lu\n", offset,
3945                         entry->offset);
3946                 return -EINVAL;
3947         }
3948
3949         if (entry->bytes != bytes) {
3950                 fprintf(stderr, "Wanted bytes %Lu, found %Lu for off %Lu\n",
3951                         bytes, entry->bytes, offset);
3952                 return -EINVAL;
3953         }
3954
3955         unlink_free_space(cache->free_space_ctl, entry);
3956         free(entry);
3957         return 0;
3958 }
3959
3960 static int verify_space_cache(struct btrfs_root *root,
3961                               struct btrfs_block_group_cache *cache)
3962 {
3963         struct btrfs_path *path;
3964         struct extent_buffer *leaf;
3965         struct btrfs_key key;
3966         u64 last;
3967         int ret = 0;
3968
3969         path = btrfs_alloc_path();
3970         if (!path)
3971                 return -ENOMEM;
3972
3973         root = root->fs_info->extent_root;
3974
3975         last = max_t(u64, cache->key.objectid, BTRFS_SUPER_INFO_OFFSET);
3976
3977         key.objectid = last;
3978         key.offset = 0;
3979         key.type = BTRFS_EXTENT_ITEM_KEY;
3980
3981         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
3982         if (ret < 0)
3983                 goto out;
3984         ret = 0;
3985         while (1) {
3986                 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
3987                         ret = btrfs_next_leaf(root, path);
3988                         if (ret < 0)
3989                                 goto out;
3990                         if (ret > 0) {
3991                                 ret = 0;
3992                                 break;
3993                         }
3994                 }
3995                 leaf = path->nodes[0];
3996                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
3997                 if (key.objectid >= cache->key.offset + cache->key.objectid)
3998                         break;
3999                 if (key.type != BTRFS_EXTENT_ITEM_KEY &&
4000                     key.type != BTRFS_METADATA_ITEM_KEY) {
4001                         path->slots[0]++;
4002                         continue;
4003                 }
4004
4005                 if (last == key.objectid) {
4006                         if (key.type == BTRFS_EXTENT_ITEM_KEY)
4007                                 last = key.objectid + key.offset;
4008                         else
4009                                 last = key.objectid + root->leafsize;
4010                         path->slots[0]++;
4011                         continue;
4012                 }
4013
4014                 ret = check_cache_range(root, cache, last,
4015                                         key.objectid - last);
4016                 if (ret)
4017                         break;
4018                 if (key.type == BTRFS_EXTENT_ITEM_KEY)
4019                         last = key.objectid + key.offset;
4020                 else
4021                         last = key.objectid + root->leafsize;
4022                 path->slots[0]++;
4023         }
4024
4025         if (last < cache->key.objectid + cache->key.offset)
4026                 ret = check_cache_range(root, cache, last,
4027                                         cache->key.objectid +
4028                                         cache->key.offset - last);
4029
4030 out:
4031         btrfs_free_path(path);
4032
4033         if (!ret &&
4034             !RB_EMPTY_ROOT(&cache->free_space_ctl->free_space_offset)) {
4035                 fprintf(stderr, "There are still entries left in the space "
4036                         "cache\n");
4037                 ret = -EINVAL;
4038         }
4039
4040         return ret;
4041 }
4042
4043 static int check_space_cache(struct btrfs_root *root)
4044 {
4045         struct btrfs_block_group_cache *cache;
4046         u64 start = BTRFS_SUPER_INFO_OFFSET + BTRFS_SUPER_INFO_SIZE;
4047         int ret;
4048         int error = 0;
4049
4050         if (btrfs_super_cache_generation(root->fs_info->super_copy) != -1ULL &&
4051             btrfs_super_generation(root->fs_info->super_copy) !=
4052             btrfs_super_cache_generation(root->fs_info->super_copy)) {
4053                 printf("cache and super generation don't match, space cache "
4054                        "will be invalidated\n");
4055                 return 0;
4056         }
4057
4058         while (1) {
4059                 cache = btrfs_lookup_first_block_group(root->fs_info, start);
4060                 if (!cache)
4061                         break;
4062
4063                 start = cache->key.objectid + cache->key.offset;
4064                 if (!cache->free_space_ctl) {
4065                         if (btrfs_init_free_space_ctl(cache,
4066                                                       root->sectorsize)) {
4067                                 ret = -ENOMEM;
4068                                 break;
4069                         }
4070                 } else {
4071                         btrfs_remove_free_space_cache(cache);
4072                 }
4073
4074                 ret = load_free_space_cache(root->fs_info, cache);
4075                 if (!ret)
4076                         continue;
4077
4078                 ret = verify_space_cache(root, cache);
4079                 if (ret) {
4080                         fprintf(stderr, "cache appears valid but isnt %Lu\n",
4081                                 cache->key.objectid);
4082                         error++;
4083                 }
4084         }
4085
4086         return error ? -EINVAL : 0;
4087 }
4088
4089 static int read_extent_data(struct btrfs_root *root, char *data,
4090                         u64 logical, u64 *len, int mirror)
4091 {
4092         u64 offset = 0;
4093         struct btrfs_multi_bio *multi = NULL;
4094         struct btrfs_fs_info *info = root->fs_info;
4095         struct btrfs_device *device;
4096         int ret = 0;
4097         u64 max_len = *len;
4098
4099         ret = btrfs_map_block(&info->mapping_tree, READ, logical, len,
4100                               &multi, mirror, NULL);
4101         if (ret) {
4102                 fprintf(stderr, "Couldn't map the block %llu\n",
4103                                 logical + offset);
4104                 goto err;
4105         }
4106         device = multi->stripes[0].dev;
4107
4108         if (device->fd == 0)
4109                 goto err;
4110         if (*len > max_len)
4111                 *len = max_len;
4112
4113         ret = pread64(device->fd, data, *len, multi->stripes[0].physical);
4114         if (ret != *len)
4115                 ret = -EIO;
4116         else
4117                 ret = 0;
4118 err:
4119         kfree(multi);
4120         return ret;
4121 }
4122
4123 static int check_extent_csums(struct btrfs_root *root, u64 bytenr,
4124                         u64 num_bytes, unsigned long leaf_offset,
4125                         struct extent_buffer *eb) {
4126
4127         u64 offset = 0;
4128         u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
4129         char *data;
4130         unsigned long csum_offset;
4131         u32 csum;
4132         u32 csum_expected;
4133         u64 read_len;
4134         u64 data_checked = 0;
4135         u64 tmp;
4136         int ret = 0;
4137         int mirror;
4138         int num_copies;
4139
4140         if (num_bytes % root->sectorsize)
4141                 return -EINVAL;
4142
4143         data = malloc(num_bytes);
4144         if (!data)
4145                 return -ENOMEM;
4146
4147         while (offset < num_bytes) {
4148                 mirror = 0;
4149 again:
4150                 read_len = num_bytes - offset;
4151                 /* read as much space once a time */
4152                 ret = read_extent_data(root, data + offset,
4153                                 bytenr + offset, &read_len, mirror);
4154                 if (ret)
4155                         goto out;
4156                 data_checked = 0;
4157                 /* verify every 4k data's checksum */
4158                 while (data_checked < read_len) {
4159                         csum = ~(u32)0;
4160                         tmp = offset + data_checked;
4161
4162                         csum = btrfs_csum_data(NULL, (char *)data + tmp,
4163                                                csum, root->sectorsize);
4164                         btrfs_csum_final(csum, (char *)&csum);
4165
4166                         csum_offset = leaf_offset +
4167                                  tmp / root->sectorsize * csum_size;
4168                         read_extent_buffer(eb, (char *)&csum_expected,
4169                                            csum_offset, csum_size);
4170                         /* try another mirror */
4171                         if (csum != csum_expected) {
4172                                 fprintf(stderr, "mirror %d bytenr %llu csum %u expected csum %u\n",
4173                                                 mirror, bytenr + tmp,
4174                                                 csum, csum_expected);
4175                                 num_copies = btrfs_num_copies(
4176                                                 &root->fs_info->mapping_tree,
4177                                                 bytenr, num_bytes);
4178                                 if (mirror < num_copies - 1) {
4179                                         mirror += 1;
4180                                         goto again;
4181                                 }
4182                         }
4183                         data_checked += root->sectorsize;
4184                 }
4185                 offset += read_len;
4186         }
4187 out:
4188         free(data);
4189         return ret;
4190 }
4191
4192 static int check_extent_exists(struct btrfs_root *root, u64 bytenr,
4193                                u64 num_bytes)
4194 {
4195         struct btrfs_path *path;
4196         struct extent_buffer *leaf;
4197         struct btrfs_key key;
4198         int ret;
4199
4200         path = btrfs_alloc_path();
4201         if (!path) {
4202                 fprintf(stderr, "Error allocing path\n");
4203                 return -ENOMEM;
4204         }
4205
4206         key.objectid = bytenr;
4207         key.type = BTRFS_EXTENT_ITEM_KEY;
4208         key.offset = (u64)-1;
4209
4210 again:
4211         ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, path,
4212                                 0, 0);
4213         if (ret < 0) {
4214                 fprintf(stderr, "Error looking up extent record %d\n", ret);
4215                 btrfs_free_path(path);
4216                 return ret;
4217         } else if (ret) {
4218                 if (path->slots[0] > 0) {
4219                         path->slots[0]--;
4220                 } else {
4221                         ret = btrfs_prev_leaf(root, path);
4222                         if (ret < 0) {
4223                                 goto out;
4224                         } else if (ret > 0) {
4225                                 ret = 0;
4226                                 goto out;
4227                         }
4228                 }
4229         }
4230
4231         btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
4232
4233         /*
4234          * Block group items come before extent items if they have the same
4235          * bytenr, so walk back one more just in case.  Dear future traveler,
4236          * first congrats on mastering time travel.  Now if it's not too much
4237          * trouble could you go back to 2006 and tell Chris to make the
4238          * BLOCK_GROUP_ITEM_KEY (and BTRFS_*_REF_KEY) lower than the
4239          * EXTENT_ITEM_KEY please?
4240          */
4241         while (key.type > BTRFS_EXTENT_ITEM_KEY) {
4242                 if (path->slots[0] > 0) {
4243                         path->slots[0]--;
4244                 } else {
4245                         ret = btrfs_prev_leaf(root, path);
4246                         if (ret < 0) {
4247                                 goto out;
4248                         } else if (ret > 0) {
4249                                 ret = 0;
4250                                 goto out;
4251                         }
4252                 }
4253                 btrfs_item_key_to_cpu(path->nodes[0], &key, path->slots[0]);
4254         }
4255
4256         while (num_bytes) {
4257                 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
4258                         ret = btrfs_next_leaf(root, path);
4259                         if (ret < 0) {
4260                                 fprintf(stderr, "Error going to next leaf "
4261                                         "%d\n", ret);
4262                                 btrfs_free_path(path);
4263                                 return ret;
4264                         } else if (ret) {
4265                                 break;
4266                         }
4267                 }
4268                 leaf = path->nodes[0];
4269                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
4270                 if (key.type != BTRFS_EXTENT_ITEM_KEY) {
4271                         path->slots[0]++;
4272                         continue;
4273                 }
4274                 if (key.objectid + key.offset < bytenr) {
4275                         path->slots[0]++;
4276                         continue;
4277                 }
4278                 if (key.objectid > bytenr + num_bytes)
4279                         break;
4280
4281                 if (key.objectid == bytenr) {
4282                         if (key.offset >= num_bytes) {
4283                                 num_bytes = 0;
4284                                 break;
4285                         }
4286                         num_bytes -= key.offset;
4287                         bytenr += key.offset;
4288                 } else if (key.objectid < bytenr) {
4289                         if (key.objectid + key.offset >= bytenr + num_bytes) {
4290                                 num_bytes = 0;
4291                                 break;
4292                         }
4293                         num_bytes = (bytenr + num_bytes) -
4294                                 (key.objectid + key.offset);
4295                         bytenr = key.objectid + key.offset;
4296                 } else {
4297                         if (key.objectid + key.offset < bytenr + num_bytes) {
4298                                 u64 new_start = key.objectid + key.offset;
4299                                 u64 new_bytes = bytenr + num_bytes - new_start;
4300
4301                                 /*
4302                                  * Weird case, the extent is in the middle of
4303                                  * our range, we'll have to search one side
4304                                  * and then the other.  Not sure if this happens
4305                                  * in real life, but no harm in coding it up
4306                                  * anyway just in case.
4307                                  */
4308                                 btrfs_release_path(path);
4309                                 ret = check_extent_exists(root, new_start,
4310                                                           new_bytes);
4311                                 if (ret) {
4312                                         fprintf(stderr, "Right section didn't "
4313                                                 "have a record\n");
4314                                         break;
4315                                 }
4316                                 num_bytes = key.objectid - bytenr;
4317                                 goto again;
4318                         }
4319                         num_bytes = key.objectid - bytenr;
4320                 }
4321                 path->slots[0]++;
4322         }
4323         ret = 0;
4324
4325 out:
4326         if (num_bytes && !ret) {
4327                 fprintf(stderr, "There are no extents for csum range "
4328                         "%Lu-%Lu\n", bytenr, bytenr+num_bytes);
4329                 ret = 1;
4330         }
4331
4332         btrfs_free_path(path);
4333         return ret;
4334 }
4335
4336 static int check_csums(struct btrfs_root *root)
4337 {
4338         struct btrfs_path *path;
4339         struct extent_buffer *leaf;
4340         struct btrfs_key key;
4341         u64 offset = 0, num_bytes = 0;
4342         u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
4343         int errors = 0;
4344         int ret;
4345         u64 data_len;
4346         unsigned long leaf_offset;
4347
4348         root = root->fs_info->csum_root;
4349         if (!extent_buffer_uptodate(root->node)) {
4350                 fprintf(stderr, "No valid csum tree found\n");
4351                 return -ENOENT;
4352         }
4353
4354         key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
4355         key.type = BTRFS_EXTENT_CSUM_KEY;
4356         key.offset = 0;
4357
4358         path = btrfs_alloc_path();
4359         if (!path)
4360                 return -ENOMEM;
4361
4362         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
4363         if (ret < 0) {
4364                 fprintf(stderr, "Error searching csum tree %d\n", ret);
4365                 btrfs_free_path(path);
4366                 return ret;
4367         }
4368
4369         if (ret > 0 && path->slots[0])
4370                 path->slots[0]--;
4371         ret = 0;
4372
4373         while (1) {
4374                 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
4375                         ret = btrfs_next_leaf(root, path);
4376                         if (ret < 0) {
4377                                 fprintf(stderr, "Error going to next leaf "
4378                                         "%d\n", ret);
4379                                 break;
4380                         }
4381                         if (ret)
4382                                 break;
4383                 }
4384                 leaf = path->nodes[0];
4385
4386                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
4387                 if (key.type != BTRFS_EXTENT_CSUM_KEY) {
4388                         path->slots[0]++;
4389                         continue;
4390                 }
4391
4392                 data_len = (btrfs_item_size_nr(leaf, path->slots[0]) /
4393                               csum_size) * root->sectorsize;
4394                 if (!check_data_csum)
4395                         goto skip_csum_check;
4396                 leaf_offset = btrfs_item_ptr_offset(leaf, path->slots[0]);
4397                 ret = check_extent_csums(root, key.offset, data_len,
4398                                          leaf_offset, leaf);
4399                 if (ret)
4400                         break;
4401 skip_csum_check:
4402                 if (!num_bytes) {
4403                         offset = key.offset;
4404                 } else if (key.offset != offset + num_bytes) {
4405                         ret = check_extent_exists(root, offset, num_bytes);
4406                         if (ret) {
4407                                 fprintf(stderr, "Csum exists for %Lu-%Lu but "
4408                                         "there is no extent record\n",
4409                                         offset, offset+num_bytes);
4410                                 errors++;
4411                         }
4412                         offset = key.offset;
4413                         num_bytes = 0;
4414                 }
4415                 num_bytes += data_len;
4416                 path->slots[0]++;
4417         }
4418
4419         btrfs_free_path(path);
4420         return errors;
4421 }
4422
4423 static int is_dropped_key(struct btrfs_key *key,
4424                           struct btrfs_key *drop_key) {
4425         if (key->objectid < drop_key->objectid)
4426                 return 1;
4427         else if (key->objectid == drop_key->objectid) {
4428                 if (key->type < drop_key->type)
4429                         return 1;
4430                 else if (key->type == drop_key->type) {
4431                         if (key->offset < drop_key->offset)
4432                                 return 1;
4433                 }
4434         }
4435         return 0;
4436 }
4437
4438 static int run_next_block(struct btrfs_trans_handle *trans,
4439                           struct btrfs_root *root,
4440                           struct block_info *bits,
4441                           int bits_nr,
4442                           u64 *last,
4443                           struct cache_tree *pending,
4444                           struct cache_tree *seen,
4445                           struct cache_tree *reada,
4446                           struct cache_tree *nodes,
4447                           struct cache_tree *extent_cache,
4448                           struct cache_tree *chunk_cache,
4449                           struct rb_root *dev_cache,
4450                           struct block_group_tree *block_group_cache,
4451                           struct device_extent_tree *dev_extent_cache,
4452                           struct btrfs_root_item *ri)
4453 {
4454         struct extent_buffer *buf;
4455         u64 bytenr;
4456         u32 size;
4457         u64 parent;
4458         u64 owner;
4459         u64 flags;
4460         u64 ptr;
4461         u64 gen = 0;
4462         int ret = 0;
4463         int i;
4464         int nritems;
4465         struct btrfs_key key;
4466         struct cache_extent *cache;
4467         int reada_bits;
4468
4469         nritems = pick_next_pending(pending, reada, nodes, *last, bits,
4470                                     bits_nr, &reada_bits);
4471         if (nritems == 0)
4472                 return 1;
4473
4474         if (!reada_bits) {
4475                 for(i = 0; i < nritems; i++) {
4476                         ret = add_cache_extent(reada, bits[i].start,
4477                                                bits[i].size);
4478                         if (ret == -EEXIST)
4479                                 continue;
4480
4481                         /* fixme, get the parent transid */
4482                         readahead_tree_block(root, bits[i].start,
4483                                              bits[i].size, 0);
4484                 }
4485         }
4486         *last = bits[0].start;
4487         bytenr = bits[0].start;
4488         size = bits[0].size;
4489
4490         cache = lookup_cache_extent(pending, bytenr, size);
4491         if (cache) {
4492                 remove_cache_extent(pending, cache);
4493                 free(cache);
4494         }
4495         cache = lookup_cache_extent(reada, bytenr, size);
4496         if (cache) {
4497                 remove_cache_extent(reada, cache);
4498                 free(cache);
4499         }
4500         cache = lookup_cache_extent(nodes, bytenr, size);
4501         if (cache) {
4502                 remove_cache_extent(nodes, cache);
4503                 free(cache);
4504         }
4505         cache = lookup_cache_extent(extent_cache, bytenr, size);
4506         if (cache) {
4507                 struct extent_record *rec;
4508
4509                 rec = container_of(cache, struct extent_record, cache);
4510                 gen = rec->parent_generation;
4511         }
4512
4513         /* fixme, get the real parent transid */
4514         buf = read_tree_block(root, bytenr, size, gen);
4515         if (!extent_buffer_uptodate(buf)) {
4516                 record_bad_block_io(root->fs_info,
4517                                     extent_cache, bytenr, size);
4518                 goto out;
4519         }
4520
4521         nritems = btrfs_header_nritems(buf);
4522
4523         /*
4524          * FIXME, this only works only if we don't have any full
4525          * backref mode.
4526          */
4527         if (!init_extent_tree) {
4528                 ret = btrfs_lookup_extent_info(NULL, root, bytenr,
4529                                        btrfs_header_level(buf), 1, NULL,
4530                                        &flags);
4531                 if (ret < 0)
4532                         flags = 0;
4533         } else {
4534                 flags = 0;
4535         }
4536
4537         if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
4538                 parent = bytenr;
4539                 owner = 0;
4540         } else {
4541                 parent = 0;
4542                 owner = btrfs_header_owner(buf);
4543         }
4544
4545         ret = check_block(trans, root, extent_cache, buf, flags);
4546         if (ret)
4547                 goto out;
4548
4549         if (btrfs_is_leaf(buf)) {
4550                 btree_space_waste += btrfs_leaf_free_space(root, buf);
4551                 for (i = 0; i < nritems; i++) {
4552                         struct btrfs_file_extent_item *fi;
4553                         btrfs_item_key_to_cpu(buf, &key, i);
4554                         if (key.type == BTRFS_EXTENT_ITEM_KEY) {
4555                                 process_extent_item(root, extent_cache, buf,
4556                                                     i);
4557                                 continue;
4558                         }
4559                         if (key.type == BTRFS_METADATA_ITEM_KEY) {
4560                                 process_extent_item(root, extent_cache, buf,
4561                                                     i);
4562                                 continue;
4563                         }
4564                         if (key.type == BTRFS_EXTENT_CSUM_KEY) {
4565                                 total_csum_bytes +=
4566                                         btrfs_item_size_nr(buf, i);
4567                                 continue;
4568                         }
4569                         if (key.type == BTRFS_CHUNK_ITEM_KEY) {
4570                                 process_chunk_item(chunk_cache, &key, buf, i);
4571                                 continue;
4572                         }
4573                         if (key.type == BTRFS_DEV_ITEM_KEY) {
4574                                 process_device_item(dev_cache, &key, buf, i);
4575                                 continue;
4576                         }
4577                         if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
4578                                 process_block_group_item(block_group_cache,
4579                                         &key, buf, i);
4580                                 continue;
4581                         }
4582                         if (key.type == BTRFS_DEV_EXTENT_KEY) {
4583                                 process_device_extent_item(dev_extent_cache,
4584                                         &key, buf, i);
4585                                 continue;
4586
4587                         }
4588                         if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
4589 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
4590                                 process_extent_ref_v0(extent_cache, buf, i);
4591 #else
4592                                 BUG();
4593 #endif
4594                                 continue;
4595                         }
4596
4597                         if (key.type == BTRFS_TREE_BLOCK_REF_KEY) {
4598                                 add_tree_backref(extent_cache, key.objectid, 0,
4599                                                  key.offset, 0);
4600                                 continue;
4601                         }
4602                         if (key.type == BTRFS_SHARED_BLOCK_REF_KEY) {
4603                                 add_tree_backref(extent_cache, key.objectid,
4604                                                  key.offset, 0, 0);
4605                                 continue;
4606                         }
4607                         if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
4608                                 struct btrfs_extent_data_ref *ref;
4609                                 ref = btrfs_item_ptr(buf, i,
4610                                                 struct btrfs_extent_data_ref);
4611                                 add_data_backref(extent_cache,
4612                                         key.objectid, 0,
4613                                         btrfs_extent_data_ref_root(buf, ref),
4614                                         btrfs_extent_data_ref_objectid(buf,
4615                                                                        ref),
4616                                         btrfs_extent_data_ref_offset(buf, ref),
4617                                         btrfs_extent_data_ref_count(buf, ref),
4618                                         0, root->sectorsize);
4619                                 continue;
4620                         }
4621                         if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
4622                                 struct btrfs_shared_data_ref *ref;
4623                                 ref = btrfs_item_ptr(buf, i,
4624                                                 struct btrfs_shared_data_ref);
4625                                 add_data_backref(extent_cache,
4626                                         key.objectid, key.offset, 0, 0, 0,
4627                                         btrfs_shared_data_ref_count(buf, ref),
4628                                         0, root->sectorsize);
4629                                 continue;
4630                         }
4631                         if (key.type == BTRFS_ORPHAN_ITEM_KEY) {
4632                                 struct bad_item *bad;
4633
4634                                 if (key.objectid == BTRFS_ORPHAN_OBJECTID)
4635                                         continue;
4636                                 if (!owner)
4637                                         continue;
4638                                 bad = malloc(sizeof(struct bad_item));
4639                                 if (!bad)
4640                                         continue;
4641                                 INIT_LIST_HEAD(&bad->list);
4642                                 memcpy(&bad->key, &key,
4643                                        sizeof(struct btrfs_key));
4644                                 bad->root_id = owner;
4645                                 list_add_tail(&bad->list, &delete_items);
4646                                 continue;
4647                         }
4648                         if (key.type != BTRFS_EXTENT_DATA_KEY)
4649                                 continue;
4650                         fi = btrfs_item_ptr(buf, i,
4651                                             struct btrfs_file_extent_item);
4652                         if (btrfs_file_extent_type(buf, fi) ==
4653                             BTRFS_FILE_EXTENT_INLINE)
4654                                 continue;
4655                         if (btrfs_file_extent_disk_bytenr(buf, fi) == 0)
4656                                 continue;
4657
4658                         data_bytes_allocated +=
4659                                 btrfs_file_extent_disk_num_bytes(buf, fi);
4660                         if (data_bytes_allocated < root->sectorsize) {
4661                                 abort();
4662                         }
4663                         data_bytes_referenced +=
4664                                 btrfs_file_extent_num_bytes(buf, fi);
4665                         add_data_backref(extent_cache,
4666                                 btrfs_file_extent_disk_bytenr(buf, fi),
4667                                 parent, owner, key.objectid, key.offset -
4668                                 btrfs_file_extent_offset(buf, fi), 1, 1,
4669                                 btrfs_file_extent_disk_num_bytes(buf, fi));
4670                 }
4671         } else {
4672                 int level;
4673                 struct btrfs_key first_key;
4674
4675                 first_key.objectid = 0;
4676
4677                 if (nritems > 0)
4678                         btrfs_item_key_to_cpu(buf, &first_key, 0);
4679                 level = btrfs_header_level(buf);
4680                 for (i = 0; i < nritems; i++) {
4681                         ptr = btrfs_node_blockptr(buf, i);
4682                         size = btrfs_level_size(root, level - 1);
4683                         btrfs_node_key_to_cpu(buf, &key, i);
4684                         if (ri != NULL) {
4685                                 struct btrfs_key drop_key;
4686                                 btrfs_disk_key_to_cpu(&drop_key,
4687                                                       &ri->drop_progress);
4688                                 if ((level == ri->drop_level)
4689                                     && is_dropped_key(&key, &drop_key)) {
4690                                         continue;
4691                                 }
4692                         }
4693                         ret = add_extent_rec(extent_cache, &key,
4694                                              btrfs_node_ptr_generation(buf, i),
4695                                              ptr, size, 0, 0, 1, 0, 1, 0,
4696                                              size);
4697                         BUG_ON(ret);
4698
4699                         add_tree_backref(extent_cache, ptr, parent, owner, 1);
4700
4701                         if (level > 1) {
4702                                 add_pending(nodes, seen, ptr, size);
4703                         } else {
4704                                 add_pending(pending, seen, ptr, size);
4705                         }
4706                 }
4707                 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) -
4708                                       nritems) * sizeof(struct btrfs_key_ptr);
4709         }
4710         total_btree_bytes += buf->len;
4711         if (fs_root_objectid(btrfs_header_owner(buf)))
4712                 total_fs_tree_bytes += buf->len;
4713         if (btrfs_header_owner(buf) == BTRFS_EXTENT_TREE_OBJECTID)
4714                 total_extent_tree_bytes += buf->len;
4715         if (!found_old_backref &&
4716             btrfs_header_owner(buf) == BTRFS_TREE_RELOC_OBJECTID &&
4717             btrfs_header_backref_rev(buf) == BTRFS_MIXED_BACKREF_REV &&
4718             !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))
4719                 found_old_backref = 1;
4720 out:
4721         free_extent_buffer(buf);
4722         return ret;
4723 }
4724
4725 static int add_root_to_pending(struct extent_buffer *buf,
4726                                struct cache_tree *extent_cache,
4727                                struct cache_tree *pending,
4728                                struct cache_tree *seen,
4729                                struct cache_tree *nodes,
4730                                struct btrfs_key *root_key)
4731 {
4732         if (btrfs_header_level(buf) > 0)
4733                 add_pending(nodes, seen, buf->start, buf->len);
4734         else
4735                 add_pending(pending, seen, buf->start, buf->len);
4736         add_extent_rec(extent_cache, NULL, 0, buf->start, buf->len,
4737                        0, 1, 1, 0, 1, 0, buf->len);
4738
4739         if (root_key->objectid == BTRFS_TREE_RELOC_OBJECTID ||
4740             btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
4741                 add_tree_backref(extent_cache, buf->start, buf->start,
4742                                  0, 1);
4743         else
4744                 add_tree_backref(extent_cache, buf->start, 0,
4745                                  root_key->objectid, 1);
4746         return 0;
4747 }
4748
4749 /* as we fix the tree, we might be deleting blocks that
4750  * we're tracking for repair.  This hook makes sure we
4751  * remove any backrefs for blocks as we are fixing them.
4752  */
4753 static int free_extent_hook(struct btrfs_trans_handle *trans,
4754                             struct btrfs_root *root,
4755                             u64 bytenr, u64 num_bytes, u64 parent,
4756                             u64 root_objectid, u64 owner, u64 offset,
4757                             int refs_to_drop)
4758 {
4759         struct extent_record *rec;
4760         struct cache_extent *cache;
4761         int is_data;
4762         struct cache_tree *extent_cache = root->fs_info->fsck_extent_cache;
4763
4764         is_data = owner >= BTRFS_FIRST_FREE_OBJECTID;
4765         cache = lookup_cache_extent(extent_cache, bytenr, num_bytes);
4766         if (!cache)
4767                 return 0;
4768
4769         rec = container_of(cache, struct extent_record, cache);
4770         if (is_data) {
4771                 struct data_backref *back;
4772                 back = find_data_backref(rec, parent, root_objectid, owner,
4773                                          offset, 1, bytenr, num_bytes);
4774                 if (!back)
4775                         goto out;
4776                 if (back->node.found_ref) {
4777                         back->found_ref -= refs_to_drop;
4778                         if (rec->refs)
4779                                 rec->refs -= refs_to_drop;
4780                 }
4781                 if (back->node.found_extent_tree) {
4782                         back->num_refs -= refs_to_drop;
4783                         if (rec->extent_item_refs)
4784                                 rec->extent_item_refs -= refs_to_drop;
4785                 }
4786                 if (back->found_ref == 0)
4787                         back->node.found_ref = 0;
4788                 if (back->num_refs == 0)
4789                         back->node.found_extent_tree = 0;
4790
4791                 if (!back->node.found_extent_tree && back->node.found_ref) {
4792                         list_del(&back->node.list);
4793                         free(back);
4794                 }
4795         } else {
4796                 struct tree_backref *back;
4797                 back = find_tree_backref(rec, parent, root_objectid);
4798                 if (!back)
4799                         goto out;
4800                 if (back->node.found_ref) {
4801                         if (rec->refs)
4802                                 rec->refs--;
4803                         back->node.found_ref = 0;
4804                 }
4805                 if (back->node.found_extent_tree) {
4806                         if (rec->extent_item_refs)
4807                                 rec->extent_item_refs--;
4808                         back->node.found_extent_tree = 0;
4809                 }
4810                 if (!back->node.found_extent_tree && back->node.found_ref) {
4811                         list_del(&back->node.list);
4812                         free(back);
4813                 }
4814         }
4815         maybe_free_extent_rec(extent_cache, rec);
4816 out:
4817         return 0;
4818 }
4819
4820 static int delete_extent_records(struct btrfs_trans_handle *trans,
4821                                  struct btrfs_root *root,
4822                                  struct btrfs_path *path,
4823                                  u64 bytenr, u64 new_len)
4824 {
4825         struct btrfs_key key;
4826         struct btrfs_key found_key;
4827         struct extent_buffer *leaf;
4828         int ret;
4829         int slot;
4830
4831
4832         key.objectid = bytenr;
4833         key.type = (u8)-1;
4834         key.offset = (u64)-1;
4835
4836         while(1) {
4837                 ret = btrfs_search_slot(trans, root->fs_info->extent_root,
4838                                         &key, path, 0, 1);
4839                 if (ret < 0)
4840                         break;
4841
4842                 if (ret > 0) {
4843                         ret = 0;
4844                         if (path->slots[0] == 0)
4845                                 break;
4846                         path->slots[0]--;
4847                 }
4848                 ret = 0;
4849
4850                 leaf = path->nodes[0];
4851                 slot = path->slots[0];
4852
4853                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
4854                 if (found_key.objectid != bytenr)
4855                         break;
4856
4857                 if (found_key.type != BTRFS_EXTENT_ITEM_KEY &&
4858                     found_key.type != BTRFS_METADATA_ITEM_KEY &&
4859                     found_key.type != BTRFS_TREE_BLOCK_REF_KEY &&
4860                     found_key.type != BTRFS_EXTENT_DATA_REF_KEY &&
4861                     found_key.type != BTRFS_EXTENT_REF_V0_KEY &&
4862                     found_key.type != BTRFS_SHARED_BLOCK_REF_KEY &&
4863                     found_key.type != BTRFS_SHARED_DATA_REF_KEY) {
4864                         btrfs_release_path(path);
4865                         if (found_key.type == 0) {
4866                                 if (found_key.offset == 0)
4867                                         break;
4868                                 key.offset = found_key.offset - 1;
4869                                 key.type = found_key.type;
4870                         }
4871                         key.type = found_key.type - 1;
4872                         key.offset = (u64)-1;
4873                         continue;
4874                 }
4875
4876                 fprintf(stderr, "repair deleting extent record: key %Lu %u %Lu\n",
4877                         found_key.objectid, found_key.type, found_key.offset);
4878
4879                 ret = btrfs_del_item(trans, root->fs_info->extent_root, path);
4880                 if (ret)
4881                         break;
4882                 btrfs_release_path(path);
4883
4884                 if (found_key.type == BTRFS_EXTENT_ITEM_KEY ||
4885                     found_key.type == BTRFS_METADATA_ITEM_KEY) {
4886                         u64 bytes = (found_key.type == BTRFS_EXTENT_ITEM_KEY) ?
4887                                 found_key.offset : root->leafsize;
4888
4889                         ret = btrfs_update_block_group(trans, root, bytenr,
4890                                                        bytes, 0, 0);
4891                         if (ret)
4892                                 break;
4893                 }
4894         }
4895
4896         btrfs_release_path(path);
4897         return ret;
4898 }
4899
4900 /*
4901  * for a single backref, this will allocate a new extent
4902  * and add the backref to it.
4903  */
4904 static int record_extent(struct btrfs_trans_handle *trans,
4905                          struct btrfs_fs_info *info,
4906                          struct btrfs_path *path,
4907                          struct extent_record *rec,
4908                          struct extent_backref *back,
4909                          int allocated, u64 flags)
4910 {
4911         int ret;
4912         struct btrfs_root *extent_root = info->extent_root;
4913         struct extent_buffer *leaf;
4914         struct btrfs_key ins_key;
4915         struct btrfs_extent_item *ei;
4916         struct tree_backref *tback;
4917         struct data_backref *dback;
4918         struct btrfs_tree_block_info *bi;
4919
4920         if (!back->is_data)
4921                 rec->max_size = max_t(u64, rec->max_size,
4922                                     info->extent_root->leafsize);
4923
4924         if (!allocated) {
4925                 u32 item_size = sizeof(*ei);
4926
4927                 if (!back->is_data)
4928                         item_size += sizeof(*bi);
4929
4930                 ins_key.objectid = rec->start;
4931                 ins_key.offset = rec->max_size;
4932                 ins_key.type = BTRFS_EXTENT_ITEM_KEY;
4933
4934                 ret = btrfs_insert_empty_item(trans, extent_root, path,
4935                                         &ins_key, item_size);
4936                 if (ret)
4937                         goto fail;
4938
4939                 leaf = path->nodes[0];
4940                 ei = btrfs_item_ptr(leaf, path->slots[0],
4941                                     struct btrfs_extent_item);
4942
4943                 btrfs_set_extent_refs(leaf, ei, 0);
4944                 btrfs_set_extent_generation(leaf, ei, rec->generation);
4945
4946                 if (back->is_data) {
4947                         btrfs_set_extent_flags(leaf, ei,
4948                                                BTRFS_EXTENT_FLAG_DATA);
4949                 } else {
4950                         struct btrfs_disk_key copy_key;;
4951
4952                         tback = (struct tree_backref *)back;
4953                         bi = (struct btrfs_tree_block_info *)(ei + 1);
4954                         memset_extent_buffer(leaf, 0, (unsigned long)bi,
4955                                              sizeof(*bi));
4956
4957                         btrfs_set_disk_key_objectid(&copy_key,
4958                                                     rec->info_objectid);
4959                         btrfs_set_disk_key_type(&copy_key, 0);
4960                         btrfs_set_disk_key_offset(&copy_key, 0);
4961
4962                         btrfs_set_tree_block_level(leaf, bi, rec->info_level);
4963                         btrfs_set_tree_block_key(leaf, bi, &copy_key);
4964
4965                         btrfs_set_extent_flags(leaf, ei,
4966                                                BTRFS_EXTENT_FLAG_TREE_BLOCK | flags);
4967                 }
4968
4969                 btrfs_mark_buffer_dirty(leaf);
4970                 ret = btrfs_update_block_group(trans, extent_root, rec->start,
4971                                                rec->max_size, 1, 0);
4972                 if (ret)
4973                         goto fail;
4974                 btrfs_release_path(path);
4975         }
4976
4977         if (back->is_data) {
4978                 u64 parent;
4979                 int i;
4980
4981                 dback = (struct data_backref *)back;
4982                 if (back->full_backref)
4983                         parent = dback->parent;
4984                 else
4985                         parent = 0;
4986
4987                 for (i = 0; i < dback->found_ref; i++) {
4988                         /* if parent != 0, we're doing a full backref
4989                          * passing BTRFS_FIRST_FREE_OBJECTID as the owner
4990                          * just makes the backref allocator create a data
4991                          * backref
4992                          */
4993                         ret = btrfs_inc_extent_ref(trans, info->extent_root,
4994                                                    rec->start, rec->max_size,
4995                                                    parent,
4996                                                    dback->root,
4997                                                    parent ?
4998                                                    BTRFS_FIRST_FREE_OBJECTID :
4999                                                    dback->owner,
5000                                                    dback->offset);
5001                         if (ret)
5002                                 break;
5003                 }
5004                 fprintf(stderr, "adding new data backref"
5005                                 " on %llu %s %llu owner %llu"
5006                                 " offset %llu found %d\n",
5007                                 (unsigned long long)rec->start,
5008                                 back->full_backref ?
5009                                 "parent" : "root",
5010                                 back->full_backref ?
5011                                 (unsigned long long)parent :
5012                                 (unsigned long long)dback->root,
5013                                 (unsigned long long)dback->owner,
5014                                 (unsigned long long)dback->offset,
5015                                 dback->found_ref);
5016         } else {
5017                 u64 parent;
5018
5019                 tback = (struct tree_backref *)back;
5020                 if (back->full_backref)
5021                         parent = tback->parent;
5022                 else
5023                         parent = 0;
5024
5025                 ret = btrfs_inc_extent_ref(trans, info->extent_root,
5026                                            rec->start, rec->max_size,
5027                                            parent, tback->root, 0, 0);
5028                 fprintf(stderr, "adding new tree backref on "
5029                         "start %llu len %llu parent %llu root %llu\n",
5030                         rec->start, rec->max_size, tback->parent, tback->root);
5031         }
5032         if (ret)
5033                 goto fail;
5034 fail:
5035         btrfs_release_path(path);
5036         return ret;
5037 }
5038
5039 struct extent_entry {
5040         u64 bytenr;
5041         u64 bytes;
5042         int count;
5043         int broken;
5044         struct list_head list;
5045 };
5046
5047 static struct extent_entry *find_entry(struct list_head *entries,
5048                                        u64 bytenr, u64 bytes)
5049 {
5050         struct extent_entry *entry = NULL;
5051
5052         list_for_each_entry(entry, entries, list) {
5053                 if (entry->bytenr == bytenr && entry->bytes == bytes)
5054                         return entry;
5055         }
5056
5057         return NULL;
5058 }
5059
5060 static struct extent_entry *find_most_right_entry(struct list_head *entries)
5061 {
5062         struct extent_entry *entry, *best = NULL, *prev = NULL;
5063
5064         list_for_each_entry(entry, entries, list) {
5065                 if (!prev) {
5066                         prev = entry;
5067                         continue;
5068                 }
5069
5070                 /*
5071                  * If there are as many broken entries as entries then we know
5072                  * not to trust this particular entry.
5073                  */
5074                 if (entry->broken == entry->count)
5075                         continue;
5076
5077                 /*
5078                  * If our current entry == best then we can't be sure our best
5079                  * is really the best, so we need to keep searching.
5080                  */
5081                 if (best && best->count == entry->count) {
5082                         prev = entry;
5083                         best = NULL;
5084                         continue;
5085                 }
5086
5087                 /* Prev == entry, not good enough, have to keep searching */
5088                 if (!prev->broken && prev->count == entry->count)
5089                         continue;
5090
5091                 if (!best)
5092                         best = (prev->count > entry->count) ? prev : entry;
5093                 else if (best->count < entry->count)
5094                         best = entry;
5095                 prev = entry;
5096         }
5097
5098         return best;
5099 }
5100
5101 static int repair_ref(struct btrfs_trans_handle *trans,
5102                       struct btrfs_fs_info *info, struct btrfs_path *path,
5103                       struct data_backref *dback, struct extent_entry *entry)
5104 {
5105         struct btrfs_root *root;
5106         struct btrfs_file_extent_item *fi;
5107         struct extent_buffer *leaf;
5108         struct btrfs_key key;
5109         u64 bytenr, bytes;
5110         int ret;
5111
5112         key.objectid = dback->root;
5113         key.type = BTRFS_ROOT_ITEM_KEY;
5114         key.offset = (u64)-1;
5115         root = btrfs_read_fs_root(info, &key);
5116         if (IS_ERR(root)) {
5117                 fprintf(stderr, "Couldn't find root for our ref\n");
5118                 return -EINVAL;
5119         }
5120
5121         /*
5122          * The backref points to the original offset of the extent if it was
5123          * split, so we need to search down to the offset we have and then walk
5124          * forward until we find the backref we're looking for.
5125          */
5126         key.objectid = dback->owner;
5127         key.type = BTRFS_EXTENT_DATA_KEY;
5128         key.offset = dback->offset;
5129         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
5130         if (ret < 0) {
5131                 fprintf(stderr, "Error looking up ref %d\n", ret);
5132                 return ret;
5133         }
5134
5135         while (1) {
5136                 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
5137                         ret = btrfs_next_leaf(root, path);
5138                         if (ret) {
5139                                 fprintf(stderr, "Couldn't find our ref, next\n");
5140                                 return -EINVAL;
5141                         }
5142                 }
5143                 leaf = path->nodes[0];
5144                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
5145                 if (key.objectid != dback->owner ||
5146                     key.type != BTRFS_EXTENT_DATA_KEY) {
5147                         fprintf(stderr, "Couldn't find our ref, search\n");
5148                         return -EINVAL;
5149                 }
5150                 fi = btrfs_item_ptr(leaf, path->slots[0],
5151                                     struct btrfs_file_extent_item);
5152                 bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
5153                 bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
5154
5155                 if (bytenr == dback->disk_bytenr && bytes == dback->bytes)
5156                         break;
5157                 path->slots[0]++;
5158         }
5159
5160         btrfs_release_path(path);
5161
5162         /*
5163          * Have to make sure that this root gets updated when we commit the
5164          * transaction
5165          */
5166         record_root_in_trans(trans, root);
5167
5168         /*
5169          * Ok we have the key of the file extent we want to fix, now we can cow
5170          * down to the thing and fix it.
5171          */
5172         ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
5173         if (ret < 0) {
5174                 fprintf(stderr, "Error cowing down to ref [%Lu, %u, %Lu]: %d\n",
5175                         key.objectid, key.type, key.offset, ret);
5176                 return ret;
5177         }
5178         if (ret > 0) {
5179                 fprintf(stderr, "Well that's odd, we just found this key "
5180                         "[%Lu, %u, %Lu]\n", key.objectid, key.type,
5181                         key.offset);
5182                 return -EINVAL;
5183         }
5184         leaf = path->nodes[0];
5185         fi = btrfs_item_ptr(leaf, path->slots[0],
5186                             struct btrfs_file_extent_item);
5187
5188         if (btrfs_file_extent_compression(leaf, fi) &&
5189             dback->disk_bytenr != entry->bytenr) {
5190                 fprintf(stderr, "Ref doesn't match the record start and is "
5191                         "compressed, please take a btrfs-image of this file "
5192                         "system and send it to a btrfs developer so they can "
5193                         "complete this functionality for bytenr %Lu\n",
5194                         dback->disk_bytenr);
5195                 return -EINVAL;
5196         }
5197
5198         if (dback->node.broken && dback->disk_bytenr != entry->bytenr) {
5199                 btrfs_set_file_extent_disk_bytenr(leaf, fi, entry->bytenr);
5200         } else if (dback->disk_bytenr > entry->bytenr) {
5201                 u64 off_diff, offset;
5202
5203                 off_diff = dback->disk_bytenr - entry->bytenr;
5204                 offset = btrfs_file_extent_offset(leaf, fi);
5205                 if (dback->disk_bytenr + offset +
5206                     btrfs_file_extent_num_bytes(leaf, fi) >
5207                     entry->bytenr + entry->bytes) {
5208                         fprintf(stderr, "Ref is past the entry end, please "
5209                                 "take a btrfs-image of this file system and "
5210                                 "send it to a btrfs developer, ref %Lu\n",
5211                                 dback->disk_bytenr);
5212                         return -EINVAL;
5213                 }
5214                 offset += off_diff;
5215                 btrfs_set_file_extent_disk_bytenr(leaf, fi, entry->bytenr);
5216                 btrfs_set_file_extent_offset(leaf, fi, offset);
5217         } else if (dback->disk_bytenr < entry->bytenr) {
5218                 u64 offset;
5219
5220                 offset = btrfs_file_extent_offset(leaf, fi);
5221                 if (dback->disk_bytenr + offset < entry->bytenr) {
5222                         fprintf(stderr, "Ref is before the entry start, please"
5223                                 " take a btrfs-image of this file system and "
5224                                 "send it to a btrfs developer, ref %Lu\n",
5225                                 dback->disk_bytenr);
5226                         return -EINVAL;
5227                 }
5228
5229                 offset += dback->disk_bytenr;
5230                 offset -= entry->bytenr;
5231                 btrfs_set_file_extent_disk_bytenr(leaf, fi, entry->bytenr);
5232                 btrfs_set_file_extent_offset(leaf, fi, offset);
5233         }
5234
5235         btrfs_set_file_extent_disk_num_bytes(leaf, fi, entry->bytes);
5236
5237         /*
5238          * Chances are if disk_num_bytes were wrong then so is ram_bytes, but
5239          * only do this if we aren't using compression, otherwise it's a
5240          * trickier case.
5241          */
5242         if (!btrfs_file_extent_compression(leaf, fi))
5243                 btrfs_set_file_extent_ram_bytes(leaf, fi, entry->bytes);
5244         else
5245                 printf("ram bytes may be wrong?\n");
5246         btrfs_mark_buffer_dirty(leaf);
5247         btrfs_release_path(path);
5248         return 0;
5249 }
5250
5251 static int verify_backrefs(struct btrfs_trans_handle *trans,
5252                            struct btrfs_fs_info *info, struct btrfs_path *path,
5253                            struct extent_record *rec)
5254 {
5255         struct extent_backref *back;
5256         struct data_backref *dback;
5257         struct extent_entry *entry, *best = NULL;
5258         LIST_HEAD(entries);
5259         int nr_entries = 0;
5260         int broken_entries = 0;
5261         int ret = 0;
5262         short mismatch = 0;
5263
5264         /*
5265          * Metadata is easy and the backrefs should always agree on bytenr and
5266          * size, if not we've got bigger issues.
5267          */
5268         if (rec->metadata)
5269                 return 0;
5270
5271         list_for_each_entry(back, &rec->backrefs, list) {
5272                 if (back->full_backref || !back->is_data)
5273                         continue;
5274
5275                 dback = (struct data_backref *)back;
5276
5277                 /*
5278                  * We only pay attention to backrefs that we found a real
5279                  * backref for.
5280                  */
5281                 if (dback->found_ref == 0)
5282                         continue;
5283
5284                 /*
5285                  * For now we only catch when the bytes don't match, not the
5286                  * bytenr.  We can easily do this at the same time, but I want
5287                  * to have a fs image to test on before we just add repair
5288                  * functionality willy-nilly so we know we won't screw up the
5289                  * repair.
5290                  */
5291
5292                 entry = find_entry(&entries, dback->disk_bytenr,
5293                                    dback->bytes);
5294                 if (!entry) {
5295                         entry = malloc(sizeof(struct extent_entry));
5296                         if (!entry) {
5297                                 ret = -ENOMEM;
5298                                 goto out;
5299                         }
5300                         memset(entry, 0, sizeof(*entry));
5301                         entry->bytenr = dback->disk_bytenr;
5302                         entry->bytes = dback->bytes;
5303                         list_add_tail(&entry->list, &entries);
5304                         nr_entries++;
5305                 }
5306
5307                 /*
5308                  * If we only have on entry we may think the entries agree when
5309                  * in reality they don't so we have to do some extra checking.
5310                  */
5311                 if (dback->disk_bytenr != rec->start ||
5312                     dback->bytes != rec->nr || back->broken)
5313                         mismatch = 1;
5314
5315                 if (back->broken) {
5316                         entry->broken++;
5317                         broken_entries++;
5318                 }
5319
5320                 entry->count++;
5321         }
5322
5323         /* Yay all the backrefs agree, carry on good sir */
5324         if (nr_entries <= 1 && !mismatch)
5325                 goto out;
5326
5327         fprintf(stderr, "attempting to repair backref discrepency for bytenr "
5328                 "%Lu\n", rec->start);
5329
5330         /*
5331          * First we want to see if the backrefs can agree amongst themselves who
5332          * is right, so figure out which one of the entries has the highest
5333          * count.
5334          */
5335         best = find_most_right_entry(&entries);
5336
5337         /*
5338          * Ok so we may have an even split between what the backrefs think, so
5339          * this is where we use the extent ref to see what it thinks.
5340          */
5341         if (!best) {
5342                 entry = find_entry(&entries, rec->start, rec->nr);
5343                 if (!entry && (!broken_entries || !rec->found_rec)) {
5344                         fprintf(stderr, "Backrefs don't agree with each other "
5345                                 "and extent record doesn't agree with anybody,"
5346                                 " so we can't fix bytenr %Lu bytes %Lu\n",
5347                                 rec->start, rec->nr);
5348                         ret = -EINVAL;
5349                         goto out;
5350                 } else if (!entry) {
5351                         /*
5352                          * Ok our backrefs were broken, we'll assume this is the
5353                          * correct value and add an entry for this range.
5354                          */
5355                         entry = malloc(sizeof(struct extent_entry));
5356                         if (!entry) {
5357                                 ret = -ENOMEM;
5358                                 goto out;
5359                         }
5360                         memset(entry, 0, sizeof(*entry));
5361                         entry->bytenr = rec->start;
5362                         entry->bytes = rec->nr;
5363                         list_add_tail(&entry->list, &entries);
5364                         nr_entries++;
5365                 }
5366                 entry->count++;
5367                 best = find_most_right_entry(&entries);
5368                 if (!best) {
5369                         fprintf(stderr, "Backrefs and extent record evenly "
5370                                 "split on who is right, this is going to "
5371                                 "require user input to fix bytenr %Lu bytes "
5372                                 "%Lu\n", rec->start, rec->nr);
5373                         ret = -EINVAL;
5374                         goto out;
5375                 }
5376         }
5377
5378         /*
5379          * I don't think this can happen currently as we'll abort() if we catch
5380          * this case higher up, but in case somebody removes that we still can't
5381          * deal with it properly here yet, so just bail out of that's the case.
5382          */
5383         if (best->bytenr != rec->start) {
5384                 fprintf(stderr, "Extent start and backref starts don't match, "
5385                         "please use btrfs-image on this file system and send "
5386                         "it to a btrfs developer so they can make fsck fix "
5387                         "this particular case.  bytenr is %Lu, bytes is %Lu\n",
5388                         rec->start, rec->nr);
5389                 ret = -EINVAL;
5390                 goto out;
5391         }
5392
5393         /*
5394          * Ok great we all agreed on an extent record, let's go find the real
5395          * references and fix up the ones that don't match.
5396          */
5397         list_for_each_entry(back, &rec->backrefs, list) {
5398                 if (back->full_backref || !back->is_data)
5399                         continue;
5400
5401                 dback = (struct data_backref *)back;
5402
5403                 /*
5404                  * Still ignoring backrefs that don't have a real ref attached
5405                  * to them.
5406                  */
5407                 if (dback->found_ref == 0)
5408                         continue;
5409
5410                 if (dback->bytes == best->bytes &&
5411                     dback->disk_bytenr == best->bytenr)
5412                         continue;
5413
5414                 ret = repair_ref(trans, info, path, dback, best);
5415                 if (ret)
5416                         goto out;
5417         }
5418
5419         /*
5420          * Ok we messed with the actual refs, which means we need to drop our
5421          * entire cache and go back and rescan.  I know this is a huge pain and
5422          * adds a lot of extra work, but it's the only way to be safe.  Once all
5423          * the backrefs agree we may not need to do anything to the extent
5424          * record itself.
5425          */
5426         ret = -EAGAIN;
5427 out:
5428         while (!list_empty(&entries)) {
5429                 entry = list_entry(entries.next, struct extent_entry, list);
5430                 list_del_init(&entry->list);
5431                 free(entry);
5432         }
5433         return ret;
5434 }
5435
5436 static int process_duplicates(struct btrfs_root *root,
5437                               struct cache_tree *extent_cache,
5438                               struct extent_record *rec)
5439 {
5440         struct extent_record *good, *tmp;
5441         struct cache_extent *cache;
5442         int ret;
5443
5444         /*
5445          * If we found a extent record for this extent then return, or if we
5446          * have more than one duplicate we are likely going to need to delete
5447          * something.
5448          */
5449         if (rec->found_rec || rec->num_duplicates > 1)
5450                 return 0;
5451
5452         /* Shouldn't happen but just in case */
5453         BUG_ON(!rec->num_duplicates);
5454
5455         /*
5456          * So this happens if we end up with a backref that doesn't match the
5457          * actual extent entry.  So either the backref is bad or the extent
5458          * entry is bad.  Either way we want to have the extent_record actually
5459          * reflect what we found in the extent_tree, so we need to take the
5460          * duplicate out and use that as the extent_record since the only way we
5461          * get a duplicate is if we find a real life BTRFS_EXTENT_ITEM_KEY.
5462          */
5463         remove_cache_extent(extent_cache, &rec->cache);
5464
5465         good = list_entry(rec->dups.next, struct extent_record, list);
5466         list_del_init(&good->list);
5467         INIT_LIST_HEAD(&good->backrefs);
5468         INIT_LIST_HEAD(&good->dups);
5469         good->cache.start = good->start;
5470         good->cache.size = good->nr;
5471         good->content_checked = 0;
5472         good->owner_ref_checked = 0;
5473         good->num_duplicates = 0;
5474         good->refs = rec->refs;
5475         list_splice_init(&rec->backrefs, &good->backrefs);
5476         while (1) {
5477                 cache = lookup_cache_extent(extent_cache, good->start,
5478                                             good->nr);
5479                 if (!cache)
5480                         break;
5481                 tmp = container_of(cache, struct extent_record, cache);
5482
5483                 /*
5484                  * If we find another overlapping extent and it's found_rec is
5485                  * set then it's a duplicate and we need to try and delete
5486                  * something.
5487                  */
5488                 if (tmp->found_rec || tmp->num_duplicates > 0) {
5489                         if (list_empty(&good->list))
5490                                 list_add_tail(&good->list,
5491                                               &duplicate_extents);
5492                         good->num_duplicates += tmp->num_duplicates + 1;
5493                         list_splice_init(&tmp->dups, &good->dups);
5494                         list_del_init(&tmp->list);
5495                         list_add_tail(&tmp->list, &good->dups);
5496                         remove_cache_extent(extent_cache, &tmp->cache);
5497                         continue;
5498                 }
5499
5500                 /*
5501                  * Ok we have another non extent item backed extent rec, so lets
5502                  * just add it to this extent and carry on like we did above.
5503                  */
5504                 good->refs += tmp->refs;
5505                 list_splice_init(&tmp->backrefs, &good->backrefs);
5506                 remove_cache_extent(extent_cache, &tmp->cache);
5507                 free(tmp);
5508         }
5509         ret = insert_cache_extent(extent_cache, &good->cache);
5510         BUG_ON(ret);
5511         free(rec);
5512         return good->num_duplicates ? 0 : 1;
5513 }
5514
5515 static int delete_duplicate_records(struct btrfs_trans_handle *trans,
5516                                     struct btrfs_root *root,
5517                                     struct extent_record *rec)
5518 {
5519         LIST_HEAD(delete_list);
5520         struct btrfs_path *path;
5521         struct extent_record *tmp, *good, *n;
5522         int nr_del = 0;
5523         int ret = 0;
5524         struct btrfs_key key;
5525
5526         path = btrfs_alloc_path();
5527         if (!path) {
5528                 ret = -ENOMEM;
5529                 goto out;
5530         }
5531
5532         good = rec;
5533         /* Find the record that covers all of the duplicates. */
5534         list_for_each_entry(tmp, &rec->dups, list) {
5535                 if (good->start < tmp->start)
5536                         continue;
5537                 if (good->nr > tmp->nr)
5538                         continue;
5539
5540                 if (tmp->start + tmp->nr < good->start + good->nr) {
5541                         fprintf(stderr, "Ok we have overlapping extents that "
5542                                 "aren't completely covered by eachother, this "
5543                                 "is going to require more careful thought.  "
5544                                 "The extents are [%Lu-%Lu] and [%Lu-%Lu]\n",
5545                                 tmp->start, tmp->nr, good->start, good->nr);
5546                         abort();
5547                 }
5548                 good = tmp;
5549         }
5550
5551         if (good != rec)
5552                 list_add_tail(&rec->list, &delete_list);
5553
5554         list_for_each_entry_safe(tmp, n, &rec->dups, list) {
5555                 if (tmp == good)
5556                         continue;
5557                 list_move_tail(&tmp->list, &delete_list);
5558         }
5559
5560         root = root->fs_info->extent_root;
5561         list_for_each_entry(tmp, &delete_list, list) {
5562                 if (tmp->found_rec == 0)
5563                         continue;
5564                 key.objectid = tmp->start;
5565                 key.type = BTRFS_EXTENT_ITEM_KEY;
5566                 key.offset = tmp->nr;
5567
5568                 /* Shouldn't happen but just in case */
5569                 if (tmp->metadata) {
5570                         fprintf(stderr, "Well this shouldn't happen, extent "
5571                                 "record overlaps but is metadata? "
5572                                 "[%Lu, %Lu]\n", tmp->start, tmp->nr);
5573                         abort();
5574                 }
5575
5576                 ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
5577                 if (ret) {
5578                         if (ret > 0)
5579                                 ret = -EINVAL;
5580                         goto out;
5581                 }
5582                 ret = btrfs_del_item(trans, root, path);
5583                 if (ret)
5584                         goto out;
5585                 btrfs_release_path(path);
5586                 nr_del++;
5587         }
5588
5589 out:
5590         while (!list_empty(&delete_list)) {
5591                 tmp = list_entry(delete_list.next, struct extent_record, list);
5592                 list_del_init(&tmp->list);
5593                 if (tmp == rec)
5594                         continue;
5595                 free(tmp);
5596         }
5597
5598         while (!list_empty(&rec->dups)) {
5599                 tmp = list_entry(rec->dups.next, struct extent_record, list);
5600                 list_del_init(&tmp->list);
5601                 free(tmp);
5602         }
5603
5604         btrfs_free_path(path);
5605
5606         if (!ret && !nr_del)
5607                 rec->num_duplicates = 0;
5608
5609         return ret ? ret : nr_del;
5610 }
5611
5612 static int find_possible_backrefs(struct btrfs_trans_handle *trans,
5613                                   struct btrfs_fs_info *info,
5614                                   struct btrfs_path *path,
5615                                   struct cache_tree *extent_cache,
5616                                   struct extent_record *rec)
5617 {
5618         struct btrfs_root *root;
5619         struct extent_backref *back;
5620         struct data_backref *dback;
5621         struct cache_extent *cache;
5622         struct btrfs_file_extent_item *fi;
5623         struct btrfs_key key;
5624         u64 bytenr, bytes;
5625         int ret;
5626
5627         list_for_each_entry(back, &rec->backrefs, list) {
5628                 /* Don't care about full backrefs (poor unloved backrefs) */
5629                 if (back->full_backref || !back->is_data)
5630                         continue;
5631
5632                 dback = (struct data_backref *)back;
5633
5634                 /* We found this one, we don't need to do a lookup */
5635                 if (dback->found_ref)
5636                         continue;
5637
5638                 key.objectid = dback->root;
5639                 key.type = BTRFS_ROOT_ITEM_KEY;
5640                 key.offset = (u64)-1;
5641
5642                 root = btrfs_read_fs_root(info, &key);
5643
5644                 /* No root, definitely a bad ref, skip */
5645                 if (IS_ERR(root) && PTR_ERR(root) == -ENOENT)
5646                         continue;
5647                 /* Other err, exit */
5648                 if (IS_ERR(root))
5649                         return PTR_ERR(root);
5650
5651                 key.objectid = dback->owner;
5652                 key.type = BTRFS_EXTENT_DATA_KEY;
5653                 key.offset = dback->offset;
5654                 ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
5655                 if (ret) {
5656                         btrfs_release_path(path);
5657                         if (ret < 0)
5658                                 return ret;
5659                         /* Didn't find it, we can carry on */
5660                         ret = 0;
5661                         continue;
5662                 }
5663
5664                 fi = btrfs_item_ptr(path->nodes[0], path->slots[0],
5665                                     struct btrfs_file_extent_item);
5666                 bytenr = btrfs_file_extent_disk_bytenr(path->nodes[0], fi);
5667                 bytes = btrfs_file_extent_disk_num_bytes(path->nodes[0], fi);
5668                 btrfs_release_path(path);
5669                 cache = lookup_cache_extent(extent_cache, bytenr, 1);
5670                 if (cache) {
5671                         struct extent_record *tmp;
5672                         tmp = container_of(cache, struct extent_record, cache);
5673
5674                         /*
5675                          * If we found an extent record for the bytenr for this
5676                          * particular backref then we can't add it to our
5677                          * current extent record.  We only want to add backrefs
5678                          * that don't have a corresponding extent item in the
5679                          * extent tree since they likely belong to this record
5680                          * and we need to fix it if it doesn't match bytenrs.
5681                          */
5682                         if  (tmp->found_rec)
5683                                 continue;
5684                 }
5685
5686                 dback->found_ref += 1;
5687                 dback->disk_bytenr = bytenr;
5688                 dback->bytes = bytes;
5689
5690                 /*
5691                  * Set this so the verify backref code knows not to trust the
5692                  * values in this backref.
5693                  */
5694                 back->broken = 1;
5695         }
5696
5697         return 0;
5698 }
5699
5700 /*
5701  * when an incorrect extent item is found, this will delete
5702  * all of the existing entries for it and recreate them
5703  * based on what the tree scan found.
5704  */
5705 static int fixup_extent_refs(struct btrfs_trans_handle *trans,
5706                              struct btrfs_fs_info *info,
5707                              struct cache_tree *extent_cache,
5708                              struct extent_record *rec)
5709 {
5710         int ret;
5711         struct btrfs_path *path;
5712         struct list_head *cur = rec->backrefs.next;
5713         struct cache_extent *cache;
5714         struct extent_backref *back;
5715         int allocated = 0;
5716         u64 flags = 0;
5717
5718         /*
5719          * remember our flags for recreating the extent.
5720          * FIXME, if we have cleared extent tree, we can not
5721          * lookup extent info in extent tree.
5722          */
5723         if (!init_extent_tree) {
5724                 ret = btrfs_lookup_extent_info(NULL, info->extent_root,
5725                                         rec->start, rec->max_size,
5726                                         rec->metadata, NULL, &flags);
5727                 if (ret < 0)
5728                         flags = 0;
5729         } else {
5730                 flags = 0;
5731         }
5732
5733         path = btrfs_alloc_path();
5734         if (!path)
5735                 return -ENOMEM;
5736
5737         if (rec->refs != rec->extent_item_refs && !rec->metadata) {
5738                 /*
5739                  * Sometimes the backrefs themselves are so broken they don't
5740                  * get attached to any meaningful rec, so first go back and
5741                  * check any of our backrefs that we couldn't find and throw
5742                  * them into the list if we find the backref so that
5743                  * verify_backrefs can figure out what to do.
5744                  */
5745                 ret = find_possible_backrefs(trans, info, path, extent_cache,
5746                                              rec);
5747                 if (ret < 0)
5748                         goto out;
5749         }
5750
5751         /* step one, make sure all of the backrefs agree */
5752         ret = verify_backrefs(trans, info, path, rec);
5753         if (ret < 0)
5754                 goto out;
5755
5756         /* step two, delete all the existing records */
5757         ret = delete_extent_records(trans, info->extent_root, path,
5758                                     rec->start, rec->max_size);
5759
5760         if (ret < 0)
5761                 goto out;
5762
5763         /* was this block corrupt?  If so, don't add references to it */
5764         cache = lookup_cache_extent(info->corrupt_blocks,
5765                                     rec->start, rec->max_size);
5766         if (cache) {
5767                 ret = 0;
5768                 goto out;
5769         }
5770
5771         /* step three, recreate all the refs we did find */
5772         while(cur != &rec->backrefs) {
5773                 back = list_entry(cur, struct extent_backref, list);
5774                 cur = cur->next;
5775
5776                 /*
5777                  * if we didn't find any references, don't create a
5778                  * new extent record
5779                  */
5780                 if (!back->found_ref)
5781                         continue;
5782
5783                 ret = record_extent(trans, info, path, rec, back, allocated, flags);
5784                 allocated = 1;
5785
5786                 if (ret)
5787                         goto out;
5788         }
5789 out:
5790         btrfs_free_path(path);
5791         return ret;
5792 }
5793
5794 /* right now we only prune from the extent allocation tree */
5795 static int prune_one_block(struct btrfs_trans_handle *trans,
5796                            struct btrfs_fs_info *info,
5797                            struct btrfs_corrupt_block *corrupt)
5798 {
5799         int ret;
5800         struct btrfs_path path;
5801         struct extent_buffer *eb;
5802         u64 found;
5803         int slot;
5804         int nritems;
5805         int level = corrupt->level + 1;
5806
5807         btrfs_init_path(&path);
5808 again:
5809         /* we want to stop at the parent to our busted block */
5810         path.lowest_level = level;
5811
5812         ret = btrfs_search_slot(trans, info->extent_root,
5813                                 &corrupt->key, &path, -1, 1);
5814
5815         if (ret < 0)
5816                 goto out;
5817
5818         eb = path.nodes[level];
5819         if (!eb) {
5820                 ret = -ENOENT;
5821                 goto out;
5822         }
5823
5824         /*
5825          * hopefully the search gave us the block we want to prune,
5826          * lets try that first
5827          */
5828         slot = path.slots[level];
5829         found =  btrfs_node_blockptr(eb, slot);
5830         if (found == corrupt->cache.start)
5831                 goto del_ptr;
5832
5833         nritems = btrfs_header_nritems(eb);
5834
5835         /* the search failed, lets scan this node and hope we find it */
5836         for (slot = 0; slot < nritems; slot++) {
5837                 found =  btrfs_node_blockptr(eb, slot);
5838                 if (found == corrupt->cache.start)
5839                         goto del_ptr;
5840         }
5841         /*
5842          * we couldn't find the bad block.  TODO, search all the nodes for pointers
5843          * to this block
5844          */
5845         if (eb == info->extent_root->node) {
5846                 ret = -ENOENT;
5847                 goto out;
5848         } else {
5849                 level++;
5850                 btrfs_release_path(&path);
5851                 goto again;
5852         }
5853
5854 del_ptr:
5855         printk("deleting pointer to block %Lu\n", corrupt->cache.start);
5856         ret = btrfs_del_ptr(trans, info->extent_root, &path, level, slot);
5857
5858 out:
5859         btrfs_release_path(&path);
5860         return ret;
5861 }
5862
5863 static int prune_corrupt_blocks(struct btrfs_trans_handle *trans,
5864                                 struct btrfs_fs_info *info)
5865 {
5866         struct cache_extent *cache;
5867         struct btrfs_corrupt_block *corrupt;
5868
5869         cache = search_cache_extent(info->corrupt_blocks, 0);
5870         while (1) {
5871                 if (!cache)
5872                         break;
5873                 corrupt = container_of(cache, struct btrfs_corrupt_block, cache);
5874                 prune_one_block(trans, info, corrupt);
5875                 cache = next_cache_extent(cache);
5876         }
5877         return 0;
5878 }
5879
5880 static void free_corrupt_block(struct cache_extent *cache)
5881 {
5882         struct btrfs_corrupt_block *corrupt;
5883
5884         corrupt = container_of(cache, struct btrfs_corrupt_block, cache);
5885         free(corrupt);
5886 }
5887
5888 FREE_EXTENT_CACHE_BASED_TREE(corrupt_blocks, free_corrupt_block);
5889
5890 static void reset_cached_block_groups(struct btrfs_fs_info *fs_info)
5891 {
5892         struct btrfs_block_group_cache *cache;
5893         u64 start, end;
5894         int ret;
5895
5896         while (1) {
5897                 ret = find_first_extent_bit(&fs_info->free_space_cache, 0,
5898                                             &start, &end, EXTENT_DIRTY);
5899                 if (ret)
5900                         break;
5901                 clear_extent_dirty(&fs_info->free_space_cache, start, end,
5902                                    GFP_NOFS);
5903         }
5904
5905         start = 0;
5906         while (1) {
5907                 cache = btrfs_lookup_first_block_group(fs_info, start);
5908                 if (!cache)
5909                         break;
5910                 if (cache->cached)
5911                         cache->cached = 0;
5912                 start = cache->key.objectid + cache->key.offset;
5913         }
5914 }
5915
5916 static int check_extent_refs(struct btrfs_trans_handle *trans,
5917                              struct btrfs_root *root,
5918                              struct cache_tree *extent_cache)
5919 {
5920         struct extent_record *rec;
5921         struct cache_extent *cache;
5922         int err = 0;
5923         int ret = 0;
5924         int fixed = 0;
5925         int had_dups = 0;
5926
5927         if (repair) {
5928                 /*
5929                  * if we're doing a repair, we have to make sure
5930                  * we don't allocate from the problem extents.
5931                  * In the worst case, this will be all the
5932                  * extents in the FS
5933                  */
5934                 cache = search_cache_extent(extent_cache, 0);
5935                 while(cache) {
5936                         rec = container_of(cache, struct extent_record, cache);
5937                         btrfs_pin_extent(root->fs_info,
5938                                          rec->start, rec->max_size);
5939                         cache = next_cache_extent(cache);
5940                 }
5941
5942                 /* pin down all the corrupted blocks too */
5943                 cache = search_cache_extent(root->fs_info->corrupt_blocks, 0);
5944                 while(cache) {
5945                         btrfs_pin_extent(root->fs_info,
5946                                          cache->start, cache->size);
5947                         cache = next_cache_extent(cache);
5948                 }
5949                 prune_corrupt_blocks(trans, root->fs_info);
5950                 reset_cached_block_groups(root->fs_info);
5951         }
5952
5953         /*
5954          * We need to delete any duplicate entries we find first otherwise we
5955          * could mess up the extent tree when we have backrefs that actually
5956          * belong to a different extent item and not the weird duplicate one.
5957          */
5958         while (repair && !list_empty(&duplicate_extents)) {
5959                 rec = list_entry(duplicate_extents.next, struct extent_record,
5960                                  list);
5961                 list_del_init(&rec->list);
5962
5963                 /* Sometimes we can find a backref before we find an actual
5964                  * extent, so we need to process it a little bit to see if there
5965                  * truly are multiple EXTENT_ITEM_KEY's for the same range, or
5966                  * if this is a backref screwup.  If we need to delete stuff
5967                  * process_duplicates() will return 0, otherwise it will return
5968                  * 1 and we
5969                  */
5970                 if (process_duplicates(root, extent_cache, rec))
5971                         continue;
5972                 ret = delete_duplicate_records(trans, root, rec);
5973                 if (ret < 0)
5974                         return ret;
5975                 /*
5976                  * delete_duplicate_records will return the number of entries
5977                  * deleted, so if it's greater than 0 then we know we actually
5978                  * did something and we need to remove.
5979                  */
5980                 if (ret)
5981                         had_dups = 1;
5982         }
5983
5984         if (had_dups)
5985                 return -EAGAIN;
5986
5987         while(1) {
5988                 fixed = 0;
5989                 cache = search_cache_extent(extent_cache, 0);
5990                 if (!cache)
5991                         break;
5992                 rec = container_of(cache, struct extent_record, cache);
5993                 if (rec->num_duplicates) {
5994                         fprintf(stderr, "extent item %llu has multiple extent "
5995                                 "items\n", (unsigned long long)rec->start);
5996                         err = 1;
5997                 }
5998
5999                 if (rec->refs != rec->extent_item_refs) {
6000                         fprintf(stderr, "ref mismatch on [%llu %llu] ",
6001                                 (unsigned long long)rec->start,
6002                                 (unsigned long long)rec->nr);
6003                         fprintf(stderr, "extent item %llu, found %llu\n",
6004                                 (unsigned long long)rec->extent_item_refs,
6005                                 (unsigned long long)rec->refs);
6006                         if (!fixed && repair) {
6007                                 ret = fixup_extent_refs(trans, root->fs_info,
6008                                                         extent_cache, rec);
6009                                 if (ret)
6010                                         goto repair_abort;
6011                                 fixed = 1;
6012                         }
6013                         err = 1;
6014
6015                 }
6016                 if (all_backpointers_checked(rec, 1)) {
6017                         fprintf(stderr, "backpointer mismatch on [%llu %llu]\n",
6018                                 (unsigned long long)rec->start,
6019                                 (unsigned long long)rec->nr);
6020
6021                         if (!fixed && repair) {
6022                                 ret = fixup_extent_refs(trans, root->fs_info,
6023                                                         extent_cache, rec);
6024                                 if (ret)
6025                                         goto repair_abort;
6026                                 fixed = 1;
6027                         }
6028
6029                         err = 1;
6030                 }
6031                 if (!rec->owner_ref_checked) {
6032                         fprintf(stderr, "owner ref check failed [%llu %llu]\n",
6033                                 (unsigned long long)rec->start,
6034                                 (unsigned long long)rec->nr);
6035                         if (!fixed && repair) {
6036                                 ret = fixup_extent_refs(trans, root->fs_info,
6037                                                         extent_cache, rec);
6038                                 if (ret)
6039                                         goto repair_abort;
6040                                 fixed = 1;
6041                         }
6042                         err = 1;
6043                 }
6044
6045                 remove_cache_extent(extent_cache, cache);
6046                 free_all_extent_backrefs(rec);
6047                 free(rec);
6048         }
6049 repair_abort:
6050         if (repair) {
6051                 if (ret && ret != -EAGAIN) {
6052                         fprintf(stderr, "failed to repair damaged filesystem, aborting\n");
6053                         exit(1);
6054                 } else if (!ret) {
6055                         btrfs_fix_block_accounting(trans, root);
6056                 }
6057                 if (err)
6058                         fprintf(stderr, "repaired damaged extent references\n");
6059                 return ret;
6060         }
6061         return err;
6062 }
6063
6064 u64 calc_stripe_length(u64 type, u64 length, int num_stripes)
6065 {
6066         u64 stripe_size;
6067
6068         if (type & BTRFS_BLOCK_GROUP_RAID0) {
6069                 stripe_size = length;
6070                 stripe_size /= num_stripes;
6071         } else if (type & BTRFS_BLOCK_GROUP_RAID10) {
6072                 stripe_size = length * 2;
6073                 stripe_size /= num_stripes;
6074         } else if (type & BTRFS_BLOCK_GROUP_RAID5) {
6075                 stripe_size = length;
6076                 stripe_size /= (num_stripes - 1);
6077         } else if (type & BTRFS_BLOCK_GROUP_RAID6) {
6078                 stripe_size = length;
6079                 stripe_size /= (num_stripes - 2);
6080         } else {
6081                 stripe_size = length;
6082         }
6083         return stripe_size;
6084 }
6085
6086 static int check_chunk_refs(struct chunk_record *chunk_rec,
6087                             struct block_group_tree *block_group_cache,
6088                             struct device_extent_tree *dev_extent_cache,
6089                             int silent)
6090 {
6091         struct cache_extent *block_group_item;
6092         struct block_group_record *block_group_rec;
6093         struct cache_extent *dev_extent_item;
6094         struct device_extent_record *dev_extent_rec;
6095         u64 devid;
6096         u64 offset;
6097         u64 length;
6098         int i;
6099         int ret = 0;
6100
6101         block_group_item = lookup_cache_extent(&block_group_cache->tree,
6102                                                chunk_rec->offset,
6103                                                chunk_rec->length);
6104         if (block_group_item) {
6105                 block_group_rec = container_of(block_group_item,
6106                                                struct block_group_record,
6107                                                cache);
6108                 if (chunk_rec->length != block_group_rec->offset ||
6109                     chunk_rec->offset != block_group_rec->objectid ||
6110                     chunk_rec->type_flags != block_group_rec->flags) {
6111                         if (!silent)
6112                                 fprintf(stderr,
6113                                         "Chunk[%llu, %u, %llu]: length(%llu), offset(%llu), type(%llu) mismatch with block group[%llu, %u, %llu]: offset(%llu), objectid(%llu), flags(%llu)\n",
6114                                         chunk_rec->objectid,
6115                                         chunk_rec->type,
6116                                         chunk_rec->offset,
6117                                         chunk_rec->length,
6118                                         chunk_rec->offset,
6119                                         chunk_rec->type_flags,
6120                                         block_group_rec->objectid,
6121                                         block_group_rec->type,
6122                                         block_group_rec->offset,
6123                                         block_group_rec->offset,
6124                                         block_group_rec->objectid,
6125                                         block_group_rec->flags);
6126                         ret = -1;
6127                 } else {
6128                         list_del_init(&block_group_rec->list);
6129                         chunk_rec->bg_rec = block_group_rec;
6130                 }
6131         } else {
6132                 if (!silent)
6133                         fprintf(stderr,
6134                                 "Chunk[%llu, %u, %llu]: length(%llu), offset(%llu), type(%llu) is not found in block group\n",
6135                                 chunk_rec->objectid,
6136                                 chunk_rec->type,
6137                                 chunk_rec->offset,
6138                                 chunk_rec->length,
6139                                 chunk_rec->offset,
6140                                 chunk_rec->type_flags);
6141                 ret = -1;
6142         }
6143
6144         length = calc_stripe_length(chunk_rec->type_flags, chunk_rec->length,
6145                                     chunk_rec->num_stripes);
6146         for (i = 0; i < chunk_rec->num_stripes; ++i) {
6147                 devid = chunk_rec->stripes[i].devid;
6148                 offset = chunk_rec->stripes[i].offset;
6149                 dev_extent_item = lookup_cache_extent2(&dev_extent_cache->tree,
6150                                                        devid, offset, length);
6151                 if (dev_extent_item) {
6152                         dev_extent_rec = container_of(dev_extent_item,
6153                                                 struct device_extent_record,
6154                                                 cache);
6155                         if (dev_extent_rec->objectid != devid ||
6156                             dev_extent_rec->offset != offset ||
6157                             dev_extent_rec->chunk_offset != chunk_rec->offset ||
6158                             dev_extent_rec->length != length) {
6159                                 if (!silent)
6160                                         fprintf(stderr,
6161                                                 "Chunk[%llu, %u, %llu] stripe[%llu, %llu] dismatch dev extent[%llu, %llu, %llu]\n",
6162                                                 chunk_rec->objectid,
6163                                                 chunk_rec->type,
6164                                                 chunk_rec->offset,
6165                                                 chunk_rec->stripes[i].devid,
6166                                                 chunk_rec->stripes[i].offset,
6167                                                 dev_extent_rec->objectid,
6168                                                 dev_extent_rec->offset,
6169                                                 dev_extent_rec->length);
6170                                 ret = -1;
6171                         } else {
6172                                 list_move(&dev_extent_rec->chunk_list,
6173                                           &chunk_rec->dextents);
6174                         }
6175                 } else {
6176                         if (!silent)
6177                                 fprintf(stderr,
6178                                         "Chunk[%llu, %u, %llu] stripe[%llu, %llu] is not found in dev extent\n",
6179                                         chunk_rec->objectid,
6180                                         chunk_rec->type,
6181                                         chunk_rec->offset,
6182                                         chunk_rec->stripes[i].devid,
6183                                         chunk_rec->stripes[i].offset);
6184                         ret = -1;
6185                 }
6186         }
6187         return ret;
6188 }
6189
6190 /* check btrfs_chunk -> btrfs_dev_extent / btrfs_block_group_item */
6191 int check_chunks(struct cache_tree *chunk_cache,
6192                  struct block_group_tree *block_group_cache,
6193                  struct device_extent_tree *dev_extent_cache,
6194                  struct list_head *good, struct list_head *bad, int silent)
6195 {
6196         struct cache_extent *chunk_item;
6197         struct chunk_record *chunk_rec;
6198         struct block_group_record *bg_rec;
6199         struct device_extent_record *dext_rec;
6200         int err;
6201         int ret = 0;
6202
6203         chunk_item = first_cache_extent(chunk_cache);
6204         while (chunk_item) {
6205                 chunk_rec = container_of(chunk_item, struct chunk_record,
6206                                          cache);
6207                 err = check_chunk_refs(chunk_rec, block_group_cache,
6208                                        dev_extent_cache, silent);
6209                 if (err) {
6210                         ret = err;
6211                         if (bad)
6212                                 list_add_tail(&chunk_rec->list, bad);
6213                 } else {
6214                         if (good)
6215                                 list_add_tail(&chunk_rec->list, good);
6216                 }
6217
6218                 chunk_item = next_cache_extent(chunk_item);
6219         }
6220
6221         list_for_each_entry(bg_rec, &block_group_cache->block_groups, list) {
6222                 if (!silent)
6223                         fprintf(stderr,
6224                                 "Block group[%llu, %llu] (flags = %llu) didn't find the relative chunk.\n",
6225                                 bg_rec->objectid,
6226                                 bg_rec->offset,
6227                                 bg_rec->flags);
6228                 if (!ret)
6229                         ret = 1;
6230         }
6231
6232         list_for_each_entry(dext_rec, &dev_extent_cache->no_chunk_orphans,
6233                             chunk_list) {
6234                 if (!silent)
6235                         fprintf(stderr,
6236                                 "Device extent[%llu, %llu, %llu] didn't find the relative chunk.\n",
6237                                 dext_rec->objectid,
6238                                 dext_rec->offset,
6239                                 dext_rec->length);
6240                 if (!ret)
6241                         ret = 1;
6242         }
6243         return ret;
6244 }
6245
6246
6247 static int check_device_used(struct device_record *dev_rec,
6248                              struct device_extent_tree *dext_cache)
6249 {
6250         struct cache_extent *cache;
6251         struct device_extent_record *dev_extent_rec;
6252         u64 total_byte = 0;
6253
6254         cache = search_cache_extent2(&dext_cache->tree, dev_rec->devid, 0);
6255         while (cache) {
6256                 dev_extent_rec = container_of(cache,
6257                                               struct device_extent_record,
6258                                               cache);
6259                 if (dev_extent_rec->objectid != dev_rec->devid)
6260                         break;
6261
6262                 list_del_init(&dev_extent_rec->device_list);
6263                 total_byte += dev_extent_rec->length;
6264                 cache = next_cache_extent(cache);
6265         }
6266
6267         if (total_byte != dev_rec->byte_used) {
6268                 fprintf(stderr,
6269                         "Dev extent's total-byte(%llu) is not equal to byte-used(%llu) in dev[%llu, %u, %llu]\n",
6270                         total_byte, dev_rec->byte_used, dev_rec->objectid,
6271                         dev_rec->type, dev_rec->offset);
6272                 return -1;
6273         } else {
6274                 return 0;
6275         }
6276 }
6277
6278 /* check btrfs_dev_item -> btrfs_dev_extent */
6279 static int check_devices(struct rb_root *dev_cache,
6280                          struct device_extent_tree *dev_extent_cache)
6281 {
6282         struct rb_node *dev_node;
6283         struct device_record *dev_rec;
6284         struct device_extent_record *dext_rec;
6285         int err;
6286         int ret = 0;
6287
6288         dev_node = rb_first(dev_cache);
6289         while (dev_node) {
6290                 dev_rec = container_of(dev_node, struct device_record, node);
6291                 err = check_device_used(dev_rec, dev_extent_cache);
6292                 if (err)
6293                         ret = err;
6294
6295                 dev_node = rb_next(dev_node);
6296         }
6297         list_for_each_entry(dext_rec, &dev_extent_cache->no_device_orphans,
6298                             device_list) {
6299                 fprintf(stderr,
6300                         "Device extent[%llu, %llu, %llu] didn't find its device.\n",
6301                         dext_rec->objectid, dext_rec->offset, dext_rec->length);
6302                 if (!ret)
6303                         ret = 1;
6304         }
6305         return ret;
6306 }
6307
6308 static int check_chunks_and_extents(struct btrfs_root *root)
6309 {
6310         struct rb_root dev_cache;
6311         struct cache_tree chunk_cache;
6312         struct block_group_tree block_group_cache;
6313         struct device_extent_tree dev_extent_cache;
6314         struct cache_tree extent_cache;
6315         struct cache_tree seen;
6316         struct cache_tree pending;
6317         struct cache_tree reada;
6318         struct cache_tree nodes;
6319         struct cache_tree corrupt_blocks;
6320         struct btrfs_path path;
6321         struct btrfs_key key;
6322         struct btrfs_key found_key;
6323         int ret, err = 0;
6324         u64 last = 0;
6325         struct block_info *bits;
6326         int bits_nr;
6327         struct extent_buffer *leaf;
6328         struct btrfs_trans_handle *trans = NULL;
6329         int slot;
6330         struct btrfs_root_item ri;
6331         struct list_head dropping_trees;
6332
6333         dev_cache = RB_ROOT;
6334         cache_tree_init(&chunk_cache);
6335         block_group_tree_init(&block_group_cache);
6336         device_extent_tree_init(&dev_extent_cache);
6337
6338         cache_tree_init(&extent_cache);
6339         cache_tree_init(&seen);
6340         cache_tree_init(&pending);
6341         cache_tree_init(&nodes);
6342         cache_tree_init(&reada);
6343         cache_tree_init(&corrupt_blocks);
6344         INIT_LIST_HEAD(&dropping_trees);
6345
6346         if (repair) {
6347                 trans = btrfs_start_transaction(root, 1);
6348                 if (IS_ERR(trans)) {
6349                         fprintf(stderr, "Error starting transaction\n");
6350                         return PTR_ERR(trans);
6351                 }
6352                 root->fs_info->fsck_extent_cache = &extent_cache;
6353                 root->fs_info->free_extent_hook = free_extent_hook;
6354                 root->fs_info->corrupt_blocks = &corrupt_blocks;
6355         }
6356
6357         bits_nr = 1024;
6358         bits = malloc(bits_nr * sizeof(struct block_info));
6359         if (!bits) {
6360                 perror("malloc");
6361                 exit(1);
6362         }
6363
6364 again:
6365         add_root_to_pending(root->fs_info->tree_root->node,
6366                             &extent_cache, &pending, &seen, &nodes,
6367                             &root->fs_info->tree_root->root_key);
6368
6369         add_root_to_pending(root->fs_info->chunk_root->node,
6370                             &extent_cache, &pending, &seen, &nodes,
6371                             &root->fs_info->chunk_root->root_key);
6372
6373         btrfs_init_path(&path);
6374         key.offset = 0;
6375         key.objectid = 0;
6376         btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
6377         ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
6378                                         &key, &path, 0, 0);
6379         if (ret < 0)
6380                 goto out;
6381         while(1) {
6382                 leaf = path.nodes[0];
6383                 slot = path.slots[0];
6384                 if (slot >= btrfs_header_nritems(path.nodes[0])) {
6385                         ret = btrfs_next_leaf(root, &path);
6386                         if (ret != 0)
6387                                 break;
6388                         leaf = path.nodes[0];
6389                         slot = path.slots[0];
6390                 }
6391                 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
6392                 if (btrfs_key_type(&found_key) == BTRFS_ROOT_ITEM_KEY) {
6393                         unsigned long offset;
6394                         struct extent_buffer *buf;
6395
6396                         offset = btrfs_item_ptr_offset(leaf, path.slots[0]);
6397                         read_extent_buffer(leaf, &ri, offset, sizeof(ri));
6398                         if (btrfs_disk_key_objectid(&ri.drop_progress) == 0) {
6399                                 buf = read_tree_block(root->fs_info->tree_root,
6400                                                       btrfs_root_bytenr(&ri),
6401                                                       btrfs_level_size(root,
6402                                                       btrfs_root_level(&ri)),
6403                                                       0);
6404                                 if (!buf) {
6405                                         ret = -EIO;
6406                                         goto out;
6407                                 }
6408                                 add_root_to_pending(buf, &extent_cache,
6409                                                     &pending, &seen, &nodes,
6410                                                     &found_key);
6411                                 free_extent_buffer(buf);
6412                         } else {
6413                                 struct dropping_root_item_record *dri_rec;
6414                                 dri_rec = malloc(sizeof(*dri_rec));
6415                                 if (!dri_rec) {
6416                                         perror("malloc");
6417                                         exit(1);
6418                                 }
6419                                 memcpy(&dri_rec->ri, &ri, sizeof(ri));
6420                                 memcpy(&dri_rec->found_key, &found_key,
6421                                        sizeof(found_key));
6422                                 list_add_tail(&dri_rec->list, &dropping_trees);
6423                         }
6424                 }
6425                 path.slots[0]++;
6426         }
6427         btrfs_release_path(&path);
6428         while (1) {
6429                 ret = run_next_block(trans, root, bits, bits_nr, &last,
6430                                      &pending, &seen, &reada, &nodes,
6431                                      &extent_cache, &chunk_cache, &dev_cache,
6432                                      &block_group_cache, &dev_extent_cache,
6433                                      NULL);
6434                 if (ret != 0)
6435                         break;
6436         }
6437
6438         while (!list_empty(&dropping_trees)) {
6439                 struct dropping_root_item_record *rec;
6440                 struct extent_buffer *buf;
6441                 rec = list_entry(dropping_trees.next,
6442                                  struct dropping_root_item_record, list);
6443                 last = 0;
6444                 if (!bits) {
6445                         perror("realloc");
6446                         exit(1);
6447                 }
6448                 buf = read_tree_block(root->fs_info->tree_root,
6449                                       btrfs_root_bytenr(&rec->ri),
6450                                       btrfs_level_size(root,
6451                                       btrfs_root_level(&rec->ri)), 0);
6452                 if (!buf) {
6453                         ret = -EIO;
6454                         goto out;
6455                 }
6456                 add_root_to_pending(buf, &extent_cache, &pending,
6457                                     &seen, &nodes, &rec->found_key);
6458                 while (1) {
6459                         ret = run_next_block(trans, root, bits, bits_nr, &last,
6460                                              &pending, &seen, &reada,
6461                                              &nodes, &extent_cache,
6462                                              &chunk_cache, &dev_cache,
6463                                              &block_group_cache,
6464                                              &dev_extent_cache,
6465                                              &rec->ri);
6466                         if (ret != 0)
6467                                 break;
6468                 }
6469                 free_extent_buffer(buf);
6470                 list_del(&rec->list);
6471                 free(rec);
6472         }
6473
6474         if (ret >= 0)
6475                 ret = check_extent_refs(trans, root, &extent_cache);
6476         if (ret == -EAGAIN) {
6477                 ret = btrfs_commit_transaction(trans, root);
6478                 if (ret)
6479                         goto out;
6480
6481                 trans = btrfs_start_transaction(root, 1);
6482                 if (IS_ERR(trans)) {
6483                         ret = PTR_ERR(trans);
6484                         goto out;
6485                 }
6486
6487                 free_corrupt_blocks_tree(root->fs_info->corrupt_blocks);
6488                 free_extent_cache_tree(&seen);
6489                 free_extent_cache_tree(&pending);
6490                 free_extent_cache_tree(&reada);
6491                 free_extent_cache_tree(&nodes);
6492                 free_chunk_cache_tree(&chunk_cache);
6493                 free_block_group_tree(&block_group_cache);
6494                 free_device_cache_tree(&dev_cache);
6495                 free_device_extent_tree(&dev_extent_cache);
6496                 free_extent_record_cache(root->fs_info, &extent_cache);
6497                 goto again;
6498         }
6499
6500         err = check_chunks(&chunk_cache, &block_group_cache,
6501                            &dev_extent_cache, NULL, NULL, 0);
6502         if (err && !ret)
6503                 ret = err;
6504
6505         err = check_devices(&dev_cache, &dev_extent_cache);
6506         if (err && !ret)
6507                 ret = err;
6508
6509 out:
6510         if (trans) {
6511                 err = btrfs_commit_transaction(trans, root);
6512                 if (!ret)
6513                         ret = err;
6514         }
6515         if (repair) {
6516                 free_corrupt_blocks_tree(root->fs_info->corrupt_blocks);
6517                 root->fs_info->fsck_extent_cache = NULL;
6518                 root->fs_info->free_extent_hook = NULL;
6519                 root->fs_info->corrupt_blocks = NULL;
6520         }
6521         free(bits);
6522         free_chunk_cache_tree(&chunk_cache);
6523         free_device_cache_tree(&dev_cache);
6524         free_block_group_tree(&block_group_cache);
6525         free_device_extent_tree(&dev_extent_cache);
6526         free_extent_cache_tree(&seen);
6527         free_extent_cache_tree(&pending);
6528         free_extent_cache_tree(&reada);
6529         free_extent_cache_tree(&nodes);
6530         return ret;
6531 }
6532
6533 static int btrfs_fsck_reinit_root(struct btrfs_trans_handle *trans,
6534                            struct btrfs_root *root, int overwrite)
6535 {
6536         struct extent_buffer *c;
6537         struct extent_buffer *old = root->node;
6538         int level;
6539         int ret;
6540         struct btrfs_disk_key disk_key = {0,0,0};
6541
6542         level = 0;
6543
6544         if (overwrite) {
6545                 c = old;
6546                 extent_buffer_get(c);
6547                 goto init;
6548         }
6549         c = btrfs_alloc_free_block(trans, root,
6550                                    btrfs_level_size(root, 0),
6551                                    root->root_key.objectid,
6552                                    &disk_key, level, 0, 0);
6553         if (IS_ERR(c)) {
6554                 c = old;
6555                 extent_buffer_get(c);
6556                 overwrite = 1;
6557         }
6558 init:
6559         memset_extent_buffer(c, 0, 0, sizeof(struct btrfs_header));
6560         btrfs_set_header_level(c, level);
6561         btrfs_set_header_bytenr(c, c->start);
6562         btrfs_set_header_generation(c, trans->transid);
6563         btrfs_set_header_backref_rev(c, BTRFS_MIXED_BACKREF_REV);
6564         btrfs_set_header_owner(c, root->root_key.objectid);
6565
6566         write_extent_buffer(c, root->fs_info->fsid,
6567                             btrfs_header_fsid(), BTRFS_FSID_SIZE);
6568
6569         write_extent_buffer(c, root->fs_info->chunk_tree_uuid,
6570                             btrfs_header_chunk_tree_uuid(c),
6571                             BTRFS_UUID_SIZE);
6572
6573         btrfs_mark_buffer_dirty(c);
6574         /*
6575          * this case can happen in the following case:
6576          *
6577          * 1.overwrite previous root.
6578          *
6579          * 2.reinit reloc data root, this is because we skip pin
6580          * down reloc data tree before which means we can allocate
6581          * same block bytenr here.
6582          */
6583         if (old->start == c->start) {
6584                 btrfs_set_root_generation(&root->root_item,
6585                                           trans->transid);
6586                 root->root_item.level = btrfs_header_level(root->node);
6587                 ret = btrfs_update_root(trans, root->fs_info->tree_root,
6588                                         &root->root_key, &root->root_item);
6589                 if (ret) {
6590                         free_extent_buffer(c);
6591                         return ret;
6592                 }
6593         }
6594         free_extent_buffer(old);
6595         root->node = c;
6596         add_root_to_dirty_list(root);
6597         return 0;
6598 }
6599
6600 static int pin_down_tree_blocks(struct btrfs_fs_info *fs_info,
6601                                 struct extent_buffer *eb, int tree_root)
6602 {
6603         struct extent_buffer *tmp;
6604         struct btrfs_root_item *ri;
6605         struct btrfs_key key;
6606         u64 bytenr;
6607         u32 leafsize;
6608         int level = btrfs_header_level(eb);
6609         int nritems;
6610         int ret;
6611         int i;
6612
6613         /*
6614          * If we have pinned this block before, don't pin it again.
6615          * This can not only avoid forever loop with broken filesystem
6616          * but also give us some speedups.
6617          */
6618         if (test_range_bit(&fs_info->pinned_extents, eb->start,
6619                            eb->start + eb->len - 1, EXTENT_DIRTY, 0))
6620                 return 0;
6621
6622         btrfs_pin_extent(fs_info, eb->start, eb->len);
6623
6624         leafsize = btrfs_super_leafsize(fs_info->super_copy);
6625         nritems = btrfs_header_nritems(eb);
6626         for (i = 0; i < nritems; i++) {
6627                 if (level == 0) {
6628                         btrfs_item_key_to_cpu(eb, &key, i);
6629                         if (key.type != BTRFS_ROOT_ITEM_KEY)
6630                                 continue;
6631                         /* Skip the extent root and reloc roots */
6632                         if (key.objectid == BTRFS_EXTENT_TREE_OBJECTID ||
6633                             key.objectid == BTRFS_TREE_RELOC_OBJECTID ||
6634                             key.objectid == BTRFS_DATA_RELOC_TREE_OBJECTID)
6635                                 continue;
6636                         ri = btrfs_item_ptr(eb, i, struct btrfs_root_item);
6637                         bytenr = btrfs_disk_root_bytenr(eb, ri);
6638
6639                         /*
6640                          * If at any point we start needing the real root we
6641                          * will have to build a stump root for the root we are
6642                          * in, but for now this doesn't actually use the root so
6643                          * just pass in extent_root.
6644                          */
6645                         tmp = read_tree_block(fs_info->extent_root, bytenr,
6646                                               leafsize, 0);
6647                         if (!tmp) {
6648                                 fprintf(stderr, "Error reading root block\n");
6649                                 return -EIO;
6650                         }
6651                         ret = pin_down_tree_blocks(fs_info, tmp, 0);
6652                         free_extent_buffer(tmp);
6653                         if (ret)
6654                                 return ret;
6655                 } else {
6656                         bytenr = btrfs_node_blockptr(eb, i);
6657
6658                         /* If we aren't the tree root don't read the block */
6659                         if (level == 1 && !tree_root) {
6660                                 btrfs_pin_extent(fs_info, bytenr, leafsize);
6661                                 continue;
6662                         }
6663
6664                         tmp = read_tree_block(fs_info->extent_root, bytenr,
6665                                               leafsize, 0);
6666                         if (!tmp) {
6667                                 fprintf(stderr, "Error reading tree block\n");
6668                                 return -EIO;
6669                         }
6670                         ret = pin_down_tree_blocks(fs_info, tmp, tree_root);
6671                         free_extent_buffer(tmp);
6672                         if (ret)
6673                                 return ret;
6674                 }
6675         }
6676
6677         return 0;
6678 }
6679
6680 static int pin_metadata_blocks(struct btrfs_fs_info *fs_info)
6681 {
6682         int ret;
6683
6684         ret = pin_down_tree_blocks(fs_info, fs_info->chunk_root->node, 0);
6685         if (ret)
6686                 return ret;
6687
6688         return pin_down_tree_blocks(fs_info, fs_info->tree_root->node, 1);
6689 }
6690
6691 static int reset_block_groups(struct btrfs_fs_info *fs_info)
6692 {
6693         struct btrfs_block_group_cache *cache;
6694         struct btrfs_path *path;
6695         struct extent_buffer *leaf;
6696         struct btrfs_chunk *chunk;
6697         struct btrfs_key key;
6698         int ret;
6699         u64 start;
6700
6701         path = btrfs_alloc_path();
6702         if (!path)
6703                 return -ENOMEM;
6704
6705         key.objectid = 0;
6706         key.type = BTRFS_CHUNK_ITEM_KEY;
6707         key.offset = 0;
6708
6709         ret = btrfs_search_slot(NULL, fs_info->chunk_root, &key, path, 0, 0);
6710         if (ret < 0) {
6711                 btrfs_free_path(path);
6712                 return ret;
6713         }
6714
6715         /*
6716          * We do this in case the block groups were screwed up and had alloc
6717          * bits that aren't actually set on the chunks.  This happens with
6718          * restored images every time and could happen in real life I guess.
6719          */
6720         fs_info->avail_data_alloc_bits = 0;
6721         fs_info->avail_metadata_alloc_bits = 0;
6722         fs_info->avail_system_alloc_bits = 0;
6723
6724         /* First we need to create the in-memory block groups */
6725         while (1) {
6726                 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
6727                         ret = btrfs_next_leaf(fs_info->chunk_root, path);
6728                         if (ret < 0) {
6729                                 btrfs_free_path(path);
6730                                 return ret;
6731                         }
6732                         if (ret) {
6733                                 ret = 0;
6734                                 break;
6735                         }
6736                 }
6737                 leaf = path->nodes[0];
6738                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
6739                 if (key.type != BTRFS_CHUNK_ITEM_KEY) {
6740                         path->slots[0]++;
6741                         continue;
6742                 }
6743
6744                 chunk = btrfs_item_ptr(leaf, path->slots[0],
6745                                        struct btrfs_chunk);
6746                 btrfs_add_block_group(fs_info, 0,
6747                                       btrfs_chunk_type(leaf, chunk),
6748                                       key.objectid, key.offset,
6749                                       btrfs_chunk_length(leaf, chunk));
6750                 set_extent_dirty(&fs_info->free_space_cache, key.offset,
6751                                  key.offset + btrfs_chunk_length(leaf, chunk),
6752                                  GFP_NOFS);
6753                 path->slots[0]++;
6754         }
6755         start = 0;
6756         while (1) {
6757                 cache = btrfs_lookup_first_block_group(fs_info, start);
6758                 if (!cache)
6759                         break;
6760                 cache->cached = 1;
6761                 start = cache->key.objectid + cache->key.offset;
6762         }
6763
6764         btrfs_free_path(path);
6765         return 0;
6766 }
6767
6768 static int reset_balance(struct btrfs_trans_handle *trans,
6769                          struct btrfs_fs_info *fs_info)
6770 {
6771         struct btrfs_root *root = fs_info->tree_root;
6772         struct btrfs_path *path;
6773         struct extent_buffer *leaf;
6774         struct btrfs_key key;
6775         int del_slot, del_nr = 0;
6776         int ret;
6777         int found = 0;
6778
6779         path = btrfs_alloc_path();
6780         if (!path)
6781                 return -ENOMEM;
6782
6783         key.objectid = BTRFS_BALANCE_OBJECTID;
6784         key.type = BTRFS_BALANCE_ITEM_KEY;
6785         key.offset = 0;
6786
6787         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
6788         if (ret) {
6789                 if (ret > 0)
6790                         ret = 0;
6791                 if (!ret)
6792                         goto reinit_data_reloc;
6793                 else
6794                         goto out;
6795         }
6796
6797         ret = btrfs_del_item(trans, root, path);
6798         if (ret)
6799                 goto out;
6800         btrfs_release_path(path);
6801
6802         key.objectid = BTRFS_TREE_RELOC_OBJECTID;
6803         key.type = BTRFS_ROOT_ITEM_KEY;
6804         key.offset = 0;
6805
6806         ret = btrfs_search_slot(trans, root, &key, path, -1, 1);
6807         if (ret < 0)
6808                 goto out;
6809         while (1) {
6810                 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
6811                         if (!found)
6812                                 break;
6813
6814                         if (del_nr) {
6815                                 ret = btrfs_del_items(trans, root, path,
6816                                                       del_slot, del_nr);
6817                                 del_nr = 0;
6818                                 if (ret)
6819                                         goto out;
6820                         }
6821                         key.offset++;
6822                         btrfs_release_path(path);
6823
6824                         found = 0;
6825                         ret = btrfs_search_slot(trans, root, &key, path,
6826                                                 -1, 1);
6827                         if (ret < 0)
6828                                 goto out;
6829                         continue;
6830                 }
6831                 found = 1;
6832                 leaf = path->nodes[0];
6833                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
6834                 if (key.objectid > BTRFS_TREE_RELOC_OBJECTID)
6835                         break;
6836                 if (key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
6837                         path->slots[0]++;
6838                         continue;
6839                 }
6840                 if (!del_nr) {
6841                         del_slot = path->slots[0];
6842                         del_nr = 1;
6843                 } else {
6844                         del_nr++;
6845                 }
6846                 path->slots[0]++;
6847         }
6848
6849         if (del_nr) {
6850                 ret = btrfs_del_items(trans, root, path, del_slot, del_nr);
6851                 if (ret)
6852                         goto out;
6853         }
6854         btrfs_release_path(path);
6855
6856 reinit_data_reloc:
6857         key.objectid = BTRFS_DATA_RELOC_TREE_OBJECTID;
6858         key.type = BTRFS_ROOT_ITEM_KEY;
6859         key.offset = (u64)-1;
6860         root = btrfs_read_fs_root(fs_info, &key);
6861         if (IS_ERR(root)) {
6862                 fprintf(stderr, "Error reading data reloc tree\n");
6863                 return PTR_ERR(root);
6864         }
6865         record_root_in_trans(trans, root);
6866         ret = btrfs_fsck_reinit_root(trans, root, 0);
6867         if (ret)
6868                 goto out;
6869         ret = btrfs_make_root_dir(trans, root, BTRFS_FIRST_FREE_OBJECTID);
6870 out:
6871         btrfs_free_path(path);
6872         return ret;
6873 }
6874
6875 static int reinit_extent_tree(struct btrfs_trans_handle *trans,
6876                               struct btrfs_fs_info *fs_info)
6877 {
6878         u64 start = 0;
6879         int ret;
6880
6881         /*
6882          * The only reason we don't do this is because right now we're just
6883          * walking the trees we find and pinning down their bytes, we don't look
6884          * at any of the leaves.  In order to do mixed groups we'd have to check
6885          * the leaves of any fs roots and pin down the bytes for any file
6886          * extents we find.  Not hard but why do it if we don't have to?
6887          */
6888         if (btrfs_fs_incompat(fs_info, BTRFS_FEATURE_INCOMPAT_MIXED_GROUPS)) {
6889                 fprintf(stderr, "We don't support re-initing the extent tree "
6890                         "for mixed block groups yet, please notify a btrfs "
6891                         "developer you want to do this so they can add this "
6892                         "functionality.\n");
6893                 return -EINVAL;
6894         }
6895
6896         /*
6897          * first we need to walk all of the trees except the extent tree and pin
6898          * down the bytes that are in use so we don't overwrite any existing
6899          * metadata.
6900          */
6901         ret = pin_metadata_blocks(fs_info);
6902         if (ret) {
6903                 fprintf(stderr, "error pinning down used bytes\n");
6904                 return ret;
6905         }
6906
6907         /*
6908          * Need to drop all the block groups since we're going to recreate all
6909          * of them again.
6910          */
6911         btrfs_free_block_groups(fs_info);
6912         ret = reset_block_groups(fs_info);
6913         if (ret) {
6914                 fprintf(stderr, "error resetting the block groups\n");
6915                 return ret;
6916         }
6917
6918         /* Ok we can allocate now, reinit the extent root */
6919         ret = btrfs_fsck_reinit_root(trans, fs_info->extent_root, 0);
6920         if (ret) {
6921                 fprintf(stderr, "extent root initialization failed\n");
6922                 /*
6923                  * When the transaction code is updated we should end the
6924                  * transaction, but for now progs only knows about commit so
6925                  * just return an error.
6926                  */
6927                 return ret;
6928         }
6929
6930         /*
6931          * Now we have all the in-memory block groups setup so we can make
6932          * allocations properly, and the metadata we care about is safe since we
6933          * pinned all of it above.
6934          */
6935         while (1) {
6936                 struct btrfs_block_group_cache *cache;
6937
6938                 cache = btrfs_lookup_first_block_group(fs_info, start);
6939                 if (!cache)
6940                         break;
6941                 start = cache->key.objectid + cache->key.offset;
6942                 ret = btrfs_insert_item(trans, fs_info->extent_root,
6943                                         &cache->key, &cache->item,
6944                                         sizeof(cache->item));
6945                 if (ret) {
6946                         fprintf(stderr, "Error adding block group\n");
6947                         return ret;
6948                 }
6949                 btrfs_extent_post_op(trans, fs_info->extent_root);
6950         }
6951
6952         ret = reset_balance(trans, fs_info);
6953         if (ret)
6954                 fprintf(stderr, "error reseting the pending balance\n");
6955
6956         return ret;
6957 }
6958
6959 static int recow_extent_buffer(struct btrfs_root *root, struct extent_buffer *eb)
6960 {
6961         struct btrfs_path *path;
6962         struct btrfs_trans_handle *trans;
6963         struct btrfs_key key;
6964         int ret;
6965
6966         printf("Recowing metadata block %llu\n", eb->start);
6967         key.objectid = btrfs_header_owner(eb);
6968         key.type = BTRFS_ROOT_ITEM_KEY;
6969         key.offset = (u64)-1;
6970
6971         root = btrfs_read_fs_root(root->fs_info, &key);
6972         if (IS_ERR(root)) {
6973                 fprintf(stderr, "Couldn't find owner root %llu\n",
6974                         key.objectid);
6975                 return PTR_ERR(root);
6976         }
6977
6978         path = btrfs_alloc_path();
6979         if (!path)
6980                 return -ENOMEM;
6981
6982         trans = btrfs_start_transaction(root, 1);
6983         if (IS_ERR(trans)) {
6984                 btrfs_free_path(path);
6985                 return PTR_ERR(trans);
6986         }
6987
6988         path->lowest_level = btrfs_header_level(eb);
6989         if (path->lowest_level)
6990                 btrfs_node_key_to_cpu(eb, &key, 0);
6991         else
6992                 btrfs_item_key_to_cpu(eb, &key, 0);
6993
6994         ret = btrfs_search_slot(trans, root, &key, path, 0, 1);
6995         btrfs_commit_transaction(trans, root);
6996         btrfs_free_path(path);
6997         return ret;
6998 }
6999
7000 static int delete_bad_item(struct btrfs_root *root, struct bad_item *bad)
7001 {
7002         struct btrfs_path *path;
7003         struct btrfs_trans_handle *trans;
7004         struct btrfs_key key;
7005         int ret;
7006
7007         printf("Deleting bad item [%llu,%u,%llu]\n", bad->key.objectid,
7008                bad->key.type, bad->key.offset);
7009         key.objectid = bad->root_id;
7010         key.type = BTRFS_ROOT_ITEM_KEY;
7011         key.offset = (u64)-1;
7012
7013         root = btrfs_read_fs_root(root->fs_info, &key);
7014         if (IS_ERR(root)) {
7015                 fprintf(stderr, "Couldn't find owner root %llu\n",
7016                         key.objectid);
7017                 return PTR_ERR(root);
7018         }
7019
7020         path = btrfs_alloc_path();
7021         if (!path)
7022                 return -ENOMEM;
7023
7024         trans = btrfs_start_transaction(root, 1);
7025         if (IS_ERR(trans)) {
7026                 btrfs_free_path(path);
7027                 return PTR_ERR(trans);
7028         }
7029
7030         ret = btrfs_search_slot(trans, root, &bad->key, path, -1, 1);
7031         if (ret) {
7032                 if (ret > 0)
7033                         ret = 0;
7034                 goto out;
7035         }
7036         ret = btrfs_del_item(trans, root, path);
7037 out:
7038         btrfs_commit_transaction(trans, root);
7039         btrfs_free_path(path);
7040         return ret;
7041 }
7042
7043 static int zero_log_tree(struct btrfs_root *root)
7044 {
7045         struct btrfs_trans_handle *trans;
7046         int ret;
7047
7048         trans = btrfs_start_transaction(root, 1);
7049         if (IS_ERR(trans)) {
7050                 ret = PTR_ERR(trans);
7051                 return ret;
7052         }
7053         btrfs_set_super_log_root(root->fs_info->super_copy, 0);
7054         btrfs_set_super_log_root_level(root->fs_info->super_copy, 0);
7055         ret = btrfs_commit_transaction(trans, root);
7056         return ret;
7057 }
7058
7059 static int populate_csum(struct btrfs_trans_handle *trans,
7060                          struct btrfs_root *csum_root, char *buf, u64 start,
7061                          u64 len)
7062 {
7063         u64 offset = 0;
7064         u64 sectorsize;
7065         int ret = 0;
7066
7067         while (offset < len) {
7068                 sectorsize = csum_root->sectorsize;
7069                 ret = read_extent_data(csum_root, buf, start + offset,
7070                                        &sectorsize, 0);
7071                 if (ret)
7072                         break;
7073                 ret = btrfs_csum_file_block(trans, csum_root, start + len,
7074                                             start + offset, buf, sectorsize);
7075                 if (ret)
7076                         break;
7077                 offset += sectorsize;
7078         }
7079         return ret;
7080 }
7081
7082 static int fill_csum_tree(struct btrfs_trans_handle *trans,
7083                           struct btrfs_root *csum_root)
7084 {
7085         struct btrfs_root *extent_root = csum_root->fs_info->extent_root;
7086         struct btrfs_path *path;
7087         struct btrfs_extent_item *ei;
7088         struct extent_buffer *leaf;
7089         char *buf;
7090         struct btrfs_key key;
7091         int ret;
7092
7093         path = btrfs_alloc_path();
7094         if (!path)
7095                 return -ENOMEM;
7096
7097         key.objectid = 0;
7098         key.type = BTRFS_EXTENT_ITEM_KEY;
7099         key.offset = 0;
7100
7101         ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
7102         if (ret < 0) {
7103                 btrfs_free_path(path);
7104                 return ret;
7105         }
7106
7107         buf = malloc(csum_root->sectorsize);
7108         if (!buf) {
7109                 btrfs_free_path(path);
7110                 return -ENOMEM;
7111         }
7112
7113         while (1) {
7114                 if (path->slots[0] >= btrfs_header_nritems(path->nodes[0])) {
7115                         ret = btrfs_next_leaf(extent_root, path);
7116                         if (ret < 0)
7117                                 break;
7118                         if (ret) {
7119                                 ret = 0;
7120                                 break;
7121                         }
7122                 }
7123                 leaf = path->nodes[0];
7124
7125                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
7126                 if (key.type != BTRFS_EXTENT_ITEM_KEY) {
7127                         path->slots[0]++;
7128                         continue;
7129                 }
7130
7131                 ei = btrfs_item_ptr(leaf, path->slots[0],
7132                                     struct btrfs_extent_item);
7133                 if (!(btrfs_extent_flags(leaf, ei) &
7134                       BTRFS_EXTENT_FLAG_DATA)) {
7135                         path->slots[0]++;
7136                         continue;
7137                 }
7138
7139                 ret = populate_csum(trans, csum_root, buf, key.objectid,
7140                                     key.offset);
7141                 if (ret)
7142                         break;
7143                 path->slots[0]++;
7144         }
7145
7146         btrfs_free_path(path);
7147         free(buf);
7148         return ret;
7149 }
7150
7151 static struct option long_options[] = {
7152         { "super", 1, NULL, 's' },
7153         { "repair", 0, NULL, 0 },
7154         { "init-csum-tree", 0, NULL, 0 },
7155         { "init-extent-tree", 0, NULL, 0 },
7156         { "check-data-csum", 0, NULL, 0 },
7157         { "backup", 0, NULL, 0 },
7158         { "subvol-extents", no_argument, NULL, 'E' },
7159         { "qgroup-report", 0, NULL, 'Q' },
7160         { NULL, 0, NULL, 0}
7161 };
7162
7163 const char * const cmd_check_usage[] = {
7164         "btrfs check [options] <device>",
7165         "Check an unmounted btrfs filesystem.",
7166         "",
7167         "-s|--super <superblock>     use this superblock copy",
7168         "-b|--backup                 use the backup root copy",
7169         "--repair                    try to repair the filesystem",
7170         "--init-csum-tree            create a new CRC tree",
7171         "--init-extent-tree          create a new extent tree",
7172         "--check-data-csum           verify checkums of data blocks",
7173         "--qgroup-report             print a report on qgroup consistency",
7174         "--subvol-extents            print subvolume extents and sharing state",
7175         NULL
7176 };
7177
7178 int cmd_check(int argc, char **argv)
7179 {
7180         struct cache_tree root_cache;
7181         struct btrfs_root *root;
7182         struct btrfs_fs_info *info;
7183         u64 bytenr = 0;
7184         u64 subvolid = 0;
7185         char uuidbuf[BTRFS_UUID_UNPARSED_SIZE];
7186         int ret;
7187         u64 num;
7188         int option_index = 0;
7189         int init_csum_tree = 0;
7190         int qgroup_report = 0;
7191         enum btrfs_open_ctree_flags ctree_flags = OPEN_CTREE_EXCLUSIVE;
7192
7193         while(1) {
7194                 int c;
7195                 c = getopt_long(argc, argv, "as:b", long_options,
7196                                 &option_index);
7197                 if (c < 0)
7198                         break;
7199                 switch(c) {
7200                         case 'a': /* ignored */ break;
7201                         case 'b':
7202                                 ctree_flags |= OPEN_CTREE_BACKUP_ROOT;
7203                                 break;
7204                         case 's':
7205                                 num = arg_strtou64(optarg);
7206                                 if (num >= BTRFS_SUPER_MIRROR_MAX) {
7207                                         fprintf(stderr,
7208                                                 "ERROR: super mirror should be less than: %d\n",
7209                                                 BTRFS_SUPER_MIRROR_MAX);
7210                                         exit(1);
7211                                 }
7212                                 bytenr = btrfs_sb_offset(((int)num));
7213                                 printf("using SB copy %llu, bytenr %llu\n", num,
7214                                        (unsigned long long)bytenr);
7215                                 break;
7216                         case 'Q':
7217                                 qgroup_report = 1;
7218                                 break;
7219                         case 'E':
7220                                 subvolid = arg_strtou64(optarg);
7221                                 break;
7222                         case '?':
7223                         case 'h':
7224                                 usage(cmd_check_usage);
7225                 }
7226                 if (option_index == 1) {
7227                         printf("enabling repair mode\n");
7228                         repair = 1;
7229                         ctree_flags |= OPEN_CTREE_WRITES;
7230                 } else if (option_index == 2) {
7231                         printf("Creating a new CRC tree\n");
7232                         init_csum_tree = 1;
7233                         repair = 1;
7234                         ctree_flags |= OPEN_CTREE_WRITES;
7235                 } else if (option_index == 3) {
7236                         init_extent_tree = 1;
7237                         ctree_flags |= (OPEN_CTREE_WRITES |
7238                                         OPEN_CTREE_NO_BLOCK_GROUPS);
7239                         repair = 1;
7240                 } else if (option_index == 4) {
7241                         check_data_csum = 1;
7242                 }
7243         }
7244         argc = argc - optind;
7245
7246         if (check_argc_exact(argc, 1))
7247                 usage(cmd_check_usage);
7248
7249         radix_tree_init();
7250         cache_tree_init(&root_cache);
7251
7252         if((ret = check_mounted(argv[optind])) < 0) {
7253                 fprintf(stderr, "Could not check mount status: %s\n", strerror(-ret));
7254                 goto err_out;
7255         } else if(ret) {
7256                 fprintf(stderr, "%s is currently mounted. Aborting.\n", argv[optind]);
7257                 ret = -EBUSY;
7258                 goto err_out;
7259         }
7260
7261         /* only allow partial opening under repair mode */
7262         if (repair)
7263                 ctree_flags |= OPEN_CTREE_PARTIAL;
7264
7265         info = open_ctree_fs_info(argv[optind], bytenr, 0, ctree_flags);
7266         if (!info) {
7267                 fprintf(stderr, "Couldn't open file system\n");
7268                 ret = -EIO;
7269                 goto err_out;
7270         }
7271
7272         root = info->fs_root;
7273         /*
7274          * repair mode will force us to commit transaction which
7275          * will make us fail to load log tree when mounting.
7276          */
7277         if (repair && btrfs_super_log_root(info->super_copy)) {
7278                 ret = ask_user("repair mode will force to clear out log tree, Are you sure?");
7279                 if (!ret) {
7280                         ret = 1;
7281                         goto close_out;
7282                 }
7283                 ret = zero_log_tree(root);
7284                 if (ret) {
7285                         fprintf(stderr, "fail to zero log tree\n");
7286                         goto close_out;
7287                 }
7288         }
7289
7290         uuid_unparse(info->super_copy->fsid, uuidbuf);
7291         if (qgroup_report) {
7292                 printf("Print quota groups for %s\nUUID: %s\n", argv[optind],
7293                        uuidbuf);
7294                 ret = qgroup_verify_all(info);
7295                 if (ret == 0)
7296                         print_qgroup_report(1);
7297                 goto close_out;
7298         }
7299         if (subvolid) {
7300                 printf("Print extent state for subvolume %llu on %s\nUUID: %s\n",
7301                        subvolid, argv[optind], uuidbuf);
7302                 ret = print_extent_state(info, subvolid);
7303                 goto close_out;
7304         }
7305         printf("Checking filesystem on %s\nUUID: %s\n", argv[optind], uuidbuf);
7306
7307         if (!extent_buffer_uptodate(info->tree_root->node) ||
7308             !extent_buffer_uptodate(info->dev_root->node) ||
7309             !extent_buffer_uptodate(info->chunk_root->node)) {
7310                 fprintf(stderr, "Critical roots corrupted, unable to fsck the FS\n");
7311                 ret = -EIO;
7312                 goto close_out;
7313         }
7314
7315         if (init_extent_tree || init_csum_tree) {
7316                 struct btrfs_trans_handle *trans;
7317
7318                 trans = btrfs_start_transaction(info->extent_root, 0);
7319                 if (IS_ERR(trans)) {
7320                         fprintf(stderr, "Error starting transaction\n");
7321                         ret = PTR_ERR(trans);
7322                         goto close_out;
7323                 }
7324
7325                 if (init_extent_tree) {
7326                         printf("Creating a new extent tree\n");
7327                         ret = reinit_extent_tree(trans, info);
7328                         if (ret)
7329                                 goto close_out;
7330                 }
7331
7332                 if (init_csum_tree) {
7333                         fprintf(stderr, "Reinit crc root\n");
7334                         ret = btrfs_fsck_reinit_root(trans, info->csum_root, 0);
7335                         if (ret) {
7336                                 fprintf(stderr, "crc root initialization failed\n");
7337                                 ret = -EIO;
7338                                 goto close_out;
7339                         }
7340
7341                         ret = fill_csum_tree(trans, info->csum_root);
7342                         if (ret) {
7343                                 fprintf(stderr, "crc refilling failed\n");
7344                                 return -EIO;
7345                         }
7346                 }
7347                 /*
7348                  * Ok now we commit and run the normal fsck, which will add
7349                  * extent entries for all of the items it finds.
7350                  */
7351                 ret = btrfs_commit_transaction(trans, info->extent_root);
7352                 if (ret)
7353                         goto close_out;
7354         }
7355         if (!extent_buffer_uptodate(info->extent_root->node)) {
7356                 fprintf(stderr, "Critical roots corrupted, unable to fsck the FS\n");
7357                 ret = -EIO;
7358                 goto close_out;
7359         }
7360         if (!extent_buffer_uptodate(info->csum_root->node)) {
7361                 fprintf(stderr, "Checksum root corrupted, rerun with --init-csum-tree option\n");
7362                 ret = -EIO;
7363                 goto close_out;
7364         }
7365
7366         fprintf(stderr, "checking extents\n");
7367         ret = check_chunks_and_extents(root);
7368         if (ret)
7369                 fprintf(stderr, "Errors found in extent allocation tree or chunk allocation\n");
7370
7371         fprintf(stderr, "checking free space cache\n");
7372         ret = check_space_cache(root);
7373         if (ret)
7374                 goto out;
7375
7376         /*
7377          * We used to have to have these hole extents in between our real
7378          * extents so if we don't have this flag set we need to make sure there
7379          * are no gaps in the file extents for inodes, otherwise we can just
7380          * ignore it when this happens.
7381          */
7382         no_holes = btrfs_fs_incompat(root->fs_info,
7383                                      BTRFS_FEATURE_INCOMPAT_NO_HOLES);
7384         fprintf(stderr, "checking fs roots\n");
7385         ret = check_fs_roots(root, &root_cache);
7386         if (ret)
7387                 goto out;
7388
7389         fprintf(stderr, "checking csums\n");
7390         ret = check_csums(root);
7391         if (ret)
7392                 goto out;
7393
7394         fprintf(stderr, "checking root refs\n");
7395         ret = check_root_refs(root, &root_cache);
7396         if (ret)
7397                 goto out;
7398
7399         while (repair && !list_empty(&root->fs_info->recow_ebs)) {
7400                 struct extent_buffer *eb;
7401
7402                 eb = list_first_entry(&root->fs_info->recow_ebs,
7403                                       struct extent_buffer, recow);
7404                 list_del_init(&eb->recow);
7405                 ret = recow_extent_buffer(root, eb);
7406                 if (ret)
7407                         break;
7408         }
7409
7410         while (!list_empty(&delete_items)) {
7411                 struct bad_item *bad;
7412
7413                 bad = list_first_entry(&delete_items, struct bad_item, list);
7414                 list_del_init(&bad->list);
7415                 if (repair)
7416                         ret = delete_bad_item(root, bad);
7417                 free(bad);
7418         }
7419
7420         if (info->quota_enabled) {
7421                 int err;
7422                 fprintf(stderr, "checking quota groups\n");
7423                 err = qgroup_verify_all(info);
7424                 if (err)
7425                         goto out;
7426         }
7427
7428         if (!list_empty(&root->fs_info->recow_ebs)) {
7429                 fprintf(stderr, "Transid errors in file system\n");
7430                 ret = 1;
7431         }
7432 out:
7433         print_qgroup_report(0);
7434         if (found_old_backref) { /*
7435                  * there was a disk format change when mixed
7436                  * backref was in testing tree. The old format
7437                  * existed about one week.
7438                  */
7439                 printf("\n * Found old mixed backref format. "
7440                        "The old format is not supported! *"
7441                        "\n * Please mount the FS in readonly mode, "
7442                        "backup data and re-format the FS. *\n\n");
7443                 ret = 1;
7444         }
7445         printf("found %llu bytes used err is %d\n",
7446                (unsigned long long)bytes_used, ret);
7447         printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes);
7448         printf("total tree bytes: %llu\n",
7449                (unsigned long long)total_btree_bytes);
7450         printf("total fs tree bytes: %llu\n",
7451                (unsigned long long)total_fs_tree_bytes);
7452         printf("total extent tree bytes: %llu\n",
7453                (unsigned long long)total_extent_tree_bytes);
7454         printf("btree space waste bytes: %llu\n",
7455                (unsigned long long)btree_space_waste);
7456         printf("file data blocks allocated: %llu\n referenced %llu\n",
7457                 (unsigned long long)data_bytes_allocated,
7458                 (unsigned long long)data_bytes_referenced);
7459         printf("%s\n", BTRFS_BUILD_VERSION);
7460
7461         free_root_recs_tree(&root_cache);
7462 close_out:
7463         close_ctree(root);
7464 err_out:
7465         return ret;
7466 }