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