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