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