btrfsck.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 "kerncompat.h"
  31 #include "ctree.h"
  32 #include "volumes.h"
  33 #include "repair.h"
  34 #include "disk-io.h"
  35 #include "print-tree.h"
  36 #include "transaction.h"
  37 #include "list.h"
  38 #include "version.h"
  39 #include "utils.h"
  40
  41 static u64 bytes_used = 0;
  42 static u64 total_csum_bytes = 0;
  43 static u64 total_btree_bytes = 0;
  44 static u64 total_fs_tree_bytes = 0;
  45 static u64 btree_space_waste = 0;
  46 static u64 data_bytes_allocated = 0;
  47 static u64 data_bytes_referenced = 0;
  48 static int found_old_backref = 0;
  49
  50 struct extent_backref {
  51         struct list_head list;
  52         unsigned int is_data:1;
  53         unsigned int found_extent_tree:1;
  54         unsigned int full_backref:1;
  55         unsigned int found_ref:1;
  56 };
  57
  58 struct data_backref {
  59         struct extent_backref node;
  60         union {
  61                 u64 parent;
  62                 u64 root;
  63         };
  64         u64 owner;
  65         u64 offset;
  66         u32 num_refs;
  67         u32 found_ref;
  68 };
  69
  70 struct tree_backref {
  71         struct extent_backref node;
  72         union {
  73                 u64 parent;
  74                 u64 root;
  75         };
  76 };
  77
  78 struct extent_record {
  79         struct list_head backrefs;
  80         struct cache_extent cache;
  81         struct btrfs_disk_key parent_key;
  82         u64 start;
  83         u64 max_size;
  84         u64 nr;
  85         u64 refs;
  86         u64 extent_item_refs;
  87         u64 generation;
  88         u64 info_objectid;
  89         u8 info_level;
  90         unsigned int content_checked:1;
  91         unsigned int owner_ref_checked:1;
  92         unsigned int is_root:1;
  93 };
  94
  95 struct inode_backref {
  96         struct list_head list;
  97         unsigned int found_dir_item:1;
  98         unsigned int found_dir_index:1;
  99         unsigned int found_inode_ref:1;
 100         unsigned int filetype:8;
 101         int errors;
 102         unsigned int ref_type;
 103         u64 dir;
 104         u64 index;
 105         u16 namelen;
 106         char name[0];
 107 };
 108
 109 #define REF_ERR_NO_DIR_ITEM             (1 << 0)
 110 #define REF_ERR_NO_DIR_INDEX            (1 << 1)
 111 #define REF_ERR_NO_INODE_REF            (1 << 2)
 112 #define REF_ERR_DUP_DIR_ITEM            (1 << 3)
 113 #define REF_ERR_DUP_DIR_INDEX           (1 << 4)
 114 #define REF_ERR_DUP_INODE_REF           (1 << 5)
 115 #define REF_ERR_INDEX_UNMATCH           (1 << 6)
 116 #define REF_ERR_FILETYPE_UNMATCH        (1 << 7)
 117 #define REF_ERR_NAME_TOO_LONG           (1 << 8) // 100
 118 #define REF_ERR_NO_ROOT_REF             (1 << 9)
 119 #define REF_ERR_NO_ROOT_BACKREF         (1 << 10)
 120 #define REF_ERR_DUP_ROOT_REF            (1 << 11)
 121 #define REF_ERR_DUP_ROOT_BACKREF        (1 << 12)
 122
 123 struct inode_record {
 124         struct list_head backrefs;
 125         unsigned int checked:1;
 126         unsigned int merging:1;
 127         unsigned int found_inode_item:1;
 128         unsigned int found_dir_item:1;
 129         unsigned int found_file_extent:1;
 130         unsigned int found_csum_item:1;
 131         unsigned int some_csum_missing:1;
 132         unsigned int nodatasum:1;
 133         int errors;
 134
 135         u64 ino;
 136         u32 nlink;
 137         u32 imode;
 138         u64 isize;
 139         u64 nbytes;
 140
 141         u32 found_link;
 142         u64 found_size;
 143         u64 extent_start;
 144         u64 extent_end;
 145         u64 first_extent_gap;
 146
 147         u32 refs;
 148 };
 149
 150 #define I_ERR_NO_INODE_ITEM             (1 << 0)
 151 #define I_ERR_NO_ORPHAN_ITEM            (1 << 1)
 152 #define I_ERR_DUP_INODE_ITEM            (1 << 2)
 153 #define I_ERR_DUP_DIR_INDEX             (1 << 3)
 154 #define I_ERR_ODD_DIR_ITEM              (1 << 4)
 155 #define I_ERR_ODD_FILE_EXTENT           (1 << 5)
 156 #define I_ERR_BAD_FILE_EXTENT           (1 << 6)
 157 #define I_ERR_FILE_EXTENT_OVERLAP       (1 << 7)
 158 #define I_ERR_FILE_EXTENT_DISCOUNT      (1 << 8) // 100
 159 #define I_ERR_DIR_ISIZE_WRONG           (1 << 9)
 160 #define I_ERR_FILE_NBYTES_WRONG         (1 << 10) // 400
 161 #define I_ERR_ODD_CSUM_ITEM             (1 << 11)
 162 #define I_ERR_SOME_CSUM_MISSING         (1 << 12)
 163 #define I_ERR_LINK_COUNT_WRONG          (1 << 13)
 164
 165 struct root_backref {
 166         struct list_head list;
 167         unsigned int found_dir_item:1;
 168         unsigned int found_dir_index:1;
 169         unsigned int found_back_ref:1;
 170         unsigned int found_forward_ref:1;
 171         unsigned int reachable:1;
 172         int errors;
 173         u64 ref_root;
 174         u64 dir;
 175         u64 index;
 176         u16 namelen;
 177         char name[0];
 178 };
 179
 180 struct root_record {
 181         struct list_head backrefs;
 182         struct cache_extent cache;
 183         unsigned int found_root_item:1;
 184         u64 objectid;
 185         u32 found_ref;
 186 };
 187
 188 struct ptr_node {
 189         struct cache_extent cache;
 190         void *data;
 191 };
 192
 193 struct shared_node {
 194         struct cache_extent cache;
 195         struct cache_tree root_cache;
 196         struct cache_tree inode_cache;
 197         struct inode_record *current;
 198         u32 refs;
 199 };
 200
 201 struct block_info {
 202         u64 start;
 203         u32 size;
 204 };
 205
 206 struct walk_control {
 207         struct cache_tree shared;
 208         struct shared_node *nodes[BTRFS_MAX_LEVEL];
 209         int active_node;
 210         int root_level;
 211 };
 212
 213 static u8 imode_to_type(u32 imode)
 214 {
 215 #define S_SHIFT 12
 216         static unsigned char btrfs_type_by_mode[S_IFMT >> S_SHIFT] = {
 217                 [S_IFREG >> S_SHIFT]    = BTRFS_FT_REG_FILE,
 218                 [S_IFDIR >> S_SHIFT]    = BTRFS_FT_DIR,
 219                 [S_IFCHR >> S_SHIFT]    = BTRFS_FT_CHRDEV,
 220                 [S_IFBLK >> S_SHIFT]    = BTRFS_FT_BLKDEV,
 221                 [S_IFIFO >> S_SHIFT]    = BTRFS_FT_FIFO,
 222                 [S_IFSOCK >> S_SHIFT]   = BTRFS_FT_SOCK,
 223                 [S_IFLNK >> S_SHIFT]    = BTRFS_FT_SYMLINK,
 224         };
 225
 226         return btrfs_type_by_mode[(imode & S_IFMT) >> S_SHIFT];
 227 #undef S_SHIFT
 228 }
 229
 230 static struct inode_record *clone_inode_rec(struct inode_record *orig_rec)
 231 {
 232         struct inode_record *rec;
 233         struct inode_backref *backref;
 234         struct inode_backref *orig;
 235         size_t size;
 236
 237         rec = malloc(sizeof(*rec));
 238         memcpy(rec, orig_rec, sizeof(*rec));
 239         rec->refs = 1;
 240         INIT_LIST_HEAD(&rec->backrefs);
 241
 242         list_for_each_entry(orig, &orig_rec->backrefs, list) {
 243                 size = sizeof(*orig) + orig->namelen + 1;
 244                 backref = malloc(size);
 245                 memcpy(backref, orig, size);
 246                 list_add_tail(&backref->list, &rec->backrefs);
 247         }
 248         return rec;
 249 }
 250
 251 static struct inode_record *get_inode_rec(struct cache_tree *inode_cache,
 252                                           u64 ino, int mod)
 253 {
 254         struct ptr_node *node;
 255         struct cache_extent *cache;
 256         struct inode_record *rec = NULL;
 257         int ret;
 258
 259         cache = find_cache_extent(inode_cache, ino, 1);
 260         if (cache) {
 261                 node = container_of(cache, struct ptr_node, cache);
 262                 rec = node->data;
 263                 if (mod && rec->refs > 1) {
 264                         node->data = clone_inode_rec(rec);
 265                         rec->refs--;
 266                         rec = node->data;
 267                 }
 268         } else if (mod) {
 269                 rec = calloc(1, sizeof(*rec));
 270                 rec->ino = ino;
 271                 rec->extent_start = (u64)-1;
 272                 rec->first_extent_gap = (u64)-1;
 273                 rec->refs = 1;
 274                 INIT_LIST_HEAD(&rec->backrefs);
 275
 276                 node = malloc(sizeof(*node));
 277                 node->cache.start = ino;
 278                 node->cache.size = 1;
 279                 node->data = rec;
 280
 281                 if (ino == BTRFS_FREE_INO_OBJECTID)
 282                         rec->found_link = 1;
 283
 284                 ret = insert_existing_cache_extent(inode_cache, &node->cache);
 285                 BUG_ON(ret);
 286         }
 287         return rec;
 288 }
 289
 290 static void free_inode_rec(struct inode_record *rec)
 291 {
 292         struct inode_backref *backref;
 293
 294         if (--rec->refs > 0)
 295                 return;
 296
 297         while (!list_empty(&rec->backrefs)) {
 298                 backref = list_entry(rec->backrefs.next,
 299                                      struct inode_backref, list);
 300                 list_del(&backref->list);
 301                 free(backref);
 302         }
 303         free(rec);
 304 }
 305
 306 static int can_free_inode_rec(struct inode_record *rec)
 307 {
 308         if (!rec->errors && rec->checked && rec->found_inode_item &&
 309             rec->nlink == rec->found_link && list_empty(&rec->backrefs))
 310                 return 1;
 311         return 0;
 312 }
 313
 314 static void maybe_free_inode_rec(struct cache_tree *inode_cache,
 315                                  struct inode_record *rec)
 316 {
 317         struct cache_extent *cache;
 318         struct inode_backref *tmp, *backref;
 319         struct ptr_node *node;
 320         unsigned char filetype;
 321
 322         if (!rec->found_inode_item)
 323                 return;
 324
 325         filetype = imode_to_type(rec->imode);
 326         list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
 327                 if (backref->found_dir_item && backref->found_dir_index) {
 328                         if (backref->filetype != filetype)
 329                                 backref->errors |= REF_ERR_FILETYPE_UNMATCH;
 330                         if (!backref->errors && backref->found_inode_ref) {
 331                                 list_del(&backref->list);
 332                                 free(backref);
 333                         }
 334                 }
 335         }
 336
 337         if (!rec->checked || rec->merging)
 338                 return;
 339
 340         if (S_ISDIR(rec->imode)) {
 341                 if (rec->found_size != rec->isize)
 342                         rec->errors |= I_ERR_DIR_ISIZE_WRONG;
 343                 if (rec->found_file_extent)
 344                         rec->errors |= I_ERR_ODD_FILE_EXTENT;
 345         } else if (S_ISREG(rec->imode) || S_ISLNK(rec->imode)) {
 346                 if (rec->found_dir_item)
 347                         rec->errors |= I_ERR_ODD_DIR_ITEM;
 348                 if (rec->found_size != rec->nbytes)
 349                         rec->errors |= I_ERR_FILE_NBYTES_WRONG;
 350                 if (rec->extent_start == (u64)-1 || rec->extent_start > 0)
 351                         rec->first_extent_gap = 0;
 352                 if (rec->nlink > 0 && (rec->extent_end < rec->isize ||
 353                     rec->first_extent_gap < rec->isize))
 354                         rec->errors |= I_ERR_FILE_EXTENT_DISCOUNT;
 355         }
 356
 357         if (S_ISREG(rec->imode) || S_ISLNK(rec->imode)) {
 358                 if (rec->found_csum_item && rec->nodatasum)
 359                         rec->errors |= I_ERR_ODD_CSUM_ITEM;
 360                 if (rec->some_csum_missing && !rec->nodatasum)
 361                         rec->errors |= I_ERR_SOME_CSUM_MISSING;
 362         }
 363
 364         BUG_ON(rec->refs != 1);
 365         if (can_free_inode_rec(rec)) {
 366                 cache = find_cache_extent(inode_cache, rec->ino, 1);
 367                 node = container_of(cache, struct ptr_node, cache);
 368                 BUG_ON(node->data != rec);
 369                 remove_cache_extent(inode_cache, &node->cache);
 370                 free(node);
 371                 free_inode_rec(rec);
 372         }
 373 }
 374
 375 static int check_orphan_item(struct btrfs_root *root, u64 ino)
 376 {
 377         struct btrfs_path path;
 378         struct btrfs_key key;
 379         int ret;
 380
 381         key.objectid = BTRFS_ORPHAN_OBJECTID;
 382         key.type = BTRFS_ORPHAN_ITEM_KEY;
 383         key.offset = ino;
 384
 385         btrfs_init_path(&path);
 386         ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
 387         btrfs_release_path(root, &path);
 388         if (ret > 0)
 389                 ret = -ENOENT;
 390         return ret;
 391 }
 392
 393 static int process_inode_item(struct extent_buffer *eb,
 394                               int slot, struct btrfs_key *key,
 395                               struct shared_node *active_node)
 396 {
 397         struct inode_record *rec;
 398         struct btrfs_inode_item *item;
 399
 400         rec = active_node->current;
 401         BUG_ON(rec->ino != key->objectid || rec->refs > 1);
 402         if (rec->found_inode_item) {
 403                 rec->errors |= I_ERR_DUP_INODE_ITEM;
 404                 return 1;
 405         }
 406         item = btrfs_item_ptr(eb, slot, struct btrfs_inode_item);
 407         rec->nlink = btrfs_inode_nlink(eb, item);
 408         rec->isize = btrfs_inode_size(eb, item);
 409         rec->nbytes = btrfs_inode_nbytes(eb, item);
 410         rec->imode = btrfs_inode_mode(eb, item);
 411         if (btrfs_inode_flags(eb, item) & BTRFS_INODE_NODATASUM)
 412                 rec->nodatasum = 1;
 413         rec->found_inode_item = 1;
 414         if (rec->nlink == 0)
 415                 rec->errors |= I_ERR_NO_ORPHAN_ITEM;
 416         maybe_free_inode_rec(&active_node->inode_cache, rec);
 417         return 0;
 418 }
 419
 420 static struct inode_backref *get_inode_backref(struct inode_record *rec,
 421                                                 const char *name,
 422                                                 int namelen, u64 dir)
 423 {
 424         struct inode_backref *backref;
 425
 426         list_for_each_entry(backref, &rec->backrefs, list) {
 427                 if (backref->dir != dir || backref->namelen != namelen)
 428                         continue;
 429                 if (memcmp(name, backref->name, namelen))
 430                         continue;
 431                 return backref;
 432         }
 433
 434         backref = malloc(sizeof(*backref) + namelen + 1);
 435         memset(backref, 0, sizeof(*backref));
 436         backref->dir = dir;
 437         backref->namelen = namelen;
 438         memcpy(backref->name, name, namelen);
 439         backref->name[namelen] = '\0';
 440         list_add_tail(&backref->list, &rec->backrefs);
 441         return backref;
 442 }
 443
 444 static int add_inode_backref(struct cache_tree *inode_cache,
 445                              u64 ino, u64 dir, u64 index,
 446                              const char *name, int namelen,
 447                              int filetype, int itemtype, int errors)
 448 {
 449         struct inode_record *rec;
 450         struct inode_backref *backref;
 451
 452         rec = get_inode_rec(inode_cache, ino, 1);
 453         backref = get_inode_backref(rec, name, namelen, dir);
 454         if (errors)
 455                 backref->errors |= errors;
 456         if (itemtype == BTRFS_DIR_INDEX_KEY) {
 457                 if (backref->found_dir_index)
 458                         backref->errors |= REF_ERR_DUP_DIR_INDEX;
 459                 if (backref->found_inode_ref && backref->index != index)
 460                         backref->errors |= REF_ERR_INDEX_UNMATCH;
 461                 if (backref->found_dir_item && backref->filetype != filetype)
 462                         backref->errors |= REF_ERR_FILETYPE_UNMATCH;
 463
 464                 backref->index = index;
 465                 backref->filetype = filetype;
 466                 backref->found_dir_index = 1;
 467         } else if (itemtype == BTRFS_DIR_ITEM_KEY) {
 468                 rec->found_link++;
 469                 if (backref->found_dir_item)
 470                         backref->errors |= REF_ERR_DUP_DIR_ITEM;
 471                 if (backref->found_dir_index && backref->filetype != filetype)
 472                         backref->errors |= REF_ERR_FILETYPE_UNMATCH;
 473
 474                 backref->filetype = filetype;
 475                 backref->found_dir_item = 1;
 476         } else if ((itemtype == BTRFS_INODE_REF_KEY) ||
 477                    (itemtype == BTRFS_INODE_EXTREF_KEY)) {
 478                 if (backref->found_inode_ref)
 479                         backref->errors |= REF_ERR_DUP_INODE_REF;
 480                 if (backref->found_dir_index && backref->index != index)
 481                         backref->errors |= REF_ERR_INDEX_UNMATCH;
 482
 483                 backref->ref_type = itemtype;
 484                 backref->index = index;
 485                 backref->found_inode_ref = 1;
 486         } else {
 487                 BUG_ON(1);
 488         }
 489
 490         maybe_free_inode_rec(inode_cache, rec);
 491         return 0;
 492 }
 493
 494 static int merge_inode_recs(struct inode_record *src, struct inode_record *dst,
 495                             struct cache_tree *dst_cache)
 496 {
 497         struct inode_backref *backref;
 498         u32 dir_count = 0;
 499
 500         dst->merging = 1;
 501         list_for_each_entry(backref, &src->backrefs, list) {
 502                 if (backref->found_dir_index) {
 503                         add_inode_backref(dst_cache, dst->ino, backref->dir,
 504                                         backref->index, backref->name,
 505                                         backref->namelen, backref->filetype,
 506                                         BTRFS_DIR_INDEX_KEY, backref->errors);
 507                 }
 508                 if (backref->found_dir_item) {
 509                         dir_count++;
 510                         add_inode_backref(dst_cache, dst->ino,
 511                                         backref->dir, 0, backref->name,
 512                                         backref->namelen, backref->filetype,
 513                                         BTRFS_DIR_ITEM_KEY, backref->errors);
 514                 }
 515                 if (backref->found_inode_ref) {
 516                         add_inode_backref(dst_cache, dst->ino,
 517                                         backref->dir, backref->index,
 518                                         backref->name, backref->namelen, 0,
 519                                         backref->ref_type, backref->errors);
 520                 }
 521         }
 522
 523         if (src->found_dir_item)
 524                 dst->found_dir_item = 1;
 525         if (src->found_file_extent)
 526                 dst->found_file_extent = 1;
 527         if (src->found_csum_item)
 528                 dst->found_csum_item = 1;
 529         if (src->some_csum_missing)
 530                 dst->some_csum_missing = 1;
 531         if (dst->first_extent_gap > src->first_extent_gap)
 532                 dst->first_extent_gap = src->first_extent_gap;
 533
 534         BUG_ON(src->found_link < dir_count);
 535         dst->found_link += src->found_link - dir_count;
 536         dst->found_size += src->found_size;
 537         if (src->extent_start != (u64)-1) {
 538                 if (dst->extent_start == (u64)-1) {
 539                         dst->extent_start = src->extent_start;
 540                         dst->extent_end = src->extent_end;
 541                 } else {
 542                         if (dst->extent_end > src->extent_start)
 543                                 dst->errors |= I_ERR_FILE_EXTENT_OVERLAP;
 544                         else if (dst->extent_end < src->extent_start &&
 545                                  dst->extent_end < dst->first_extent_gap)
 546                                 dst->first_extent_gap = dst->extent_end;
 547                         if (dst->extent_end < src->extent_end)
 548                                 dst->extent_end = src->extent_end;
 549                 }
 550         }
 551
 552         dst->errors |= src->errors;
 553         if (src->found_inode_item) {
 554                 if (!dst->found_inode_item) {
 555                         dst->nlink = src->nlink;
 556                         dst->isize = src->isize;
 557                         dst->nbytes = src->nbytes;
 558                         dst->imode = src->imode;
 559                         dst->nodatasum = src->nodatasum;
 560                         dst->found_inode_item = 1;
 561                 } else {
 562                         dst->errors |= I_ERR_DUP_INODE_ITEM;
 563                 }
 564         }
 565         dst->merging = 0;
 566
 567         return 0;
 568 }
 569
 570 static int splice_shared_node(struct shared_node *src_node,
 571                               struct shared_node *dst_node)
 572 {
 573         struct cache_extent *cache;
 574         struct ptr_node *node, *ins;
 575         struct cache_tree *src, *dst;
 576         struct inode_record *rec, *conflict;
 577         u64 current_ino = 0;
 578         int splice = 0;
 579         int ret;
 580
 581         if (--src_node->refs == 0)
 582                 splice = 1;
 583         if (src_node->current)
 584                 current_ino = src_node->current->ino;
 585
 586         src = &src_node->root_cache;
 587         dst = &dst_node->root_cache;
 588 again:
 589         cache = find_first_cache_extent(src, 0);
 590         while (cache) {
 591                 node = container_of(cache, struct ptr_node, cache);
 592                 rec = node->data;
 593                 cache = next_cache_extent(cache);
 594
 595                 if (splice) {
 596                         remove_cache_extent(src, &node->cache);
 597                         ins = node;
 598                 } else {
 599                         ins = malloc(sizeof(*ins));
 600                         ins->cache.start = node->cache.start;
 601                         ins->cache.size = node->cache.size;
 602                         ins->data = rec;
 603                         rec->refs++;
 604                 }
 605                 ret = insert_existing_cache_extent(dst, &ins->cache);
 606                 if (ret == -EEXIST) {
 607                         conflict = get_inode_rec(dst, rec->ino, 1);
 608                         merge_inode_recs(rec, conflict, dst);
 609                         if (rec->checked) {
 610                                 conflict->checked = 1;
 611                                 if (dst_node->current == conflict)
 612                                         dst_node->current = NULL;
 613                         }
 614                         maybe_free_inode_rec(dst, conflict);
 615                         free_inode_rec(rec);
 616                         free(ins);
 617                 } else {
 618                         BUG_ON(ret);
 619                 }
 620         }
 621
 622         if (src == &src_node->root_cache) {
 623                 src = &src_node->inode_cache;
 624                 dst = &dst_node->inode_cache;
 625                 goto again;
 626         }
 627
 628         if (current_ino > 0 && (!dst_node->current ||
 629             current_ino > dst_node->current->ino)) {
 630                 if (dst_node->current) {
 631                         dst_node->current->checked = 1;
 632                         maybe_free_inode_rec(dst, dst_node->current);
 633                 }
 634                 dst_node->current = get_inode_rec(dst, current_ino, 1);
 635         }
 636         return 0;
 637 }
 638
 639 static void free_inode_recs(struct cache_tree *inode_cache)
 640 {
 641         struct cache_extent *cache;
 642         struct ptr_node *node;
 643         struct inode_record *rec;
 644
 645         while (1) {
 646                 cache = find_first_cache_extent(inode_cache, 0);
 647                 if (!cache)
 648                         break;
 649                 node = container_of(cache, struct ptr_node, cache);
 650                 rec = node->data;
 651                 remove_cache_extent(inode_cache, &node->cache);
 652                 free(node);
 653                 free_inode_rec(rec);
 654         }
 655 }
 656
 657 static struct shared_node *find_shared_node(struct cache_tree *shared,
 658                                             u64 bytenr)
 659 {
 660         struct cache_extent *cache;
 661         struct shared_node *node;
 662
 663         cache = find_cache_extent(shared, bytenr, 1);
 664         if (cache) {
 665                 node = container_of(cache, struct shared_node, cache);
 666                 return node;
 667         }
 668         return NULL;
 669 }
 670
 671 static int add_shared_node(struct cache_tree *shared, u64 bytenr, u32 refs)
 672 {
 673         int ret;
 674         struct shared_node *node;
 675
 676         node = calloc(1, sizeof(*node));
 677         node->cache.start = bytenr;
 678         node->cache.size = 1;
 679         cache_tree_init(&node->root_cache);
 680         cache_tree_init(&node->inode_cache);
 681         node->refs = refs;
 682
 683         ret = insert_existing_cache_extent(shared, &node->cache);
 684         BUG_ON(ret);
 685         return 0;
 686 }
 687
 688 static int enter_shared_node(struct btrfs_root *root, u64 bytenr, u32 refs,
 689                              struct walk_control *wc, int level)
 690 {
 691         struct shared_node *node;
 692         struct shared_node *dest;
 693
 694         if (level == wc->active_node)
 695                 return 0;
 696
 697         BUG_ON(wc->active_node <= level);
 698         node = find_shared_node(&wc->shared, bytenr);
 699         if (!node) {
 700                 add_shared_node(&wc->shared, bytenr, refs);
 701                 node = find_shared_node(&wc->shared, bytenr);
 702                 wc->nodes[level] = node;
 703                 wc->active_node = level;
 704                 return 0;
 705         }
 706
 707         if (wc->root_level == wc->active_node &&
 708             btrfs_root_refs(&root->root_item) == 0) {
 709                 if (--node->refs == 0) {
 710                         free_inode_recs(&node->root_cache);
 711                         free_inode_recs(&node->inode_cache);
 712                         remove_cache_extent(&wc->shared, &node->cache);
 713                         free(node);
 714                 }
 715                 return 1;
 716         }
 717
 718         dest = wc->nodes[wc->active_node];
 719         splice_shared_node(node, dest);
 720         if (node->refs == 0) {
 721                 remove_cache_extent(&wc->shared, &node->cache);
 722                 free(node);
 723         }
 724         return 1;
 725 }
 726
 727 static int leave_shared_node(struct btrfs_root *root,
 728                              struct walk_control *wc, int level)
 729 {
 730         struct shared_node *node;
 731         struct shared_node *dest;
 732         int i;
 733
 734         if (level == wc->root_level)
 735                 return 0;
 736
 737         for (i = level + 1; i < BTRFS_MAX_LEVEL; i++) {
 738                 if (wc->nodes[i])
 739                         break;
 740         }
 741         BUG_ON(i >= BTRFS_MAX_LEVEL);
 742
 743         node = wc->nodes[wc->active_node];
 744         wc->nodes[wc->active_node] = NULL;
 745         wc->active_node = i;
 746
 747         dest = wc->nodes[wc->active_node];
 748         if (wc->active_node < wc->root_level ||
 749             btrfs_root_refs(&root->root_item) > 0) {
 750                 BUG_ON(node->refs <= 1);
 751                 splice_shared_node(node, dest);
 752         } else {
 753                 BUG_ON(node->refs < 2);
 754                 node->refs--;
 755         }
 756         return 0;
 757 }
 758
 759 static int is_child_root(struct btrfs_root *root, u64 parent_root_id,
 760                          u64 child_root_id)
 761 {
 762         struct btrfs_path path;
 763         struct btrfs_key key;
 764         struct extent_buffer *leaf;
 765         int has_parent = 0;
 766         int ret;
 767
 768         btrfs_init_path(&path);
 769
 770         key.objectid = parent_root_id;
 771         key.type = BTRFS_ROOT_REF_KEY;
 772         key.offset = child_root_id;
 773         ret = btrfs_search_slot(NULL, root->fs_info->tree_root, &key, &path,
 774                                 0, 0);
 775         BUG_ON(ret < 0);
 776         btrfs_release_path(root, &path);
 777         if (!ret)
 778                 return 1;
 779
 780         key.objectid = child_root_id;
 781         key.type = BTRFS_ROOT_BACKREF_KEY;
 782         key.offset = 0;
 783         ret = btrfs_search_slot(NULL, root->fs_info->tree_root, &key, &path,
 784                                 0, 0);
 785         BUG_ON(ret <= 0);
 786
 787         while (1) {
 788                 leaf = path.nodes[0];
 789                 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
 790                         ret = btrfs_next_leaf(root->fs_info->tree_root, &path);
 791                         BUG_ON(ret < 0);
 792
 793                         if (ret > 0)
 794                                 break;
 795                         leaf = path.nodes[0];
 796                 }
 797
 798                 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
 799                 if (key.objectid != child_root_id ||
 800                     key.type != BTRFS_ROOT_BACKREF_KEY)
 801                         break;
 802
 803                 has_parent = 1;
 804
 805                 if (key.offset == parent_root_id) {
 806                         btrfs_release_path(root, &path);
 807                         return 1;
 808                 }
 809
 810                 path.slots[0]++;
 811         }
 812
 813         btrfs_release_path(root, &path);
 814         return has_parent? 0 : -1;
 815 }
 816
 817 static int process_dir_item(struct btrfs_root *root,
 818                             struct extent_buffer *eb,
 819                             int slot, struct btrfs_key *key,
 820                             struct shared_node *active_node)
 821 {
 822         u32 total;
 823         u32 cur = 0;
 824         u32 len;
 825         u32 name_len;
 826         u32 data_len;
 827         int error;
 828         int nritems = 0;
 829         int filetype;
 830         struct btrfs_dir_item *di;
 831         struct inode_record *rec;
 832         struct cache_tree *root_cache;
 833         struct cache_tree *inode_cache;
 834         struct btrfs_key location;
 835         char namebuf[BTRFS_NAME_LEN];
 836
 837         root_cache = &active_node->root_cache;
 838         inode_cache = &active_node->inode_cache;
 839         rec = active_node->current;
 840         rec->found_dir_item = 1;
 841
 842         di = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);
 843         total = btrfs_item_size_nr(eb, slot);
 844         while (cur < total) {
 845                 nritems++;
 846                 btrfs_dir_item_key_to_cpu(eb, di, &location);
 847                 name_len = btrfs_dir_name_len(eb, di);
 848                 data_len = btrfs_dir_data_len(eb, di);
 849                 filetype = btrfs_dir_type(eb, di);
 850
 851                 rec->found_size += name_len;
 852                 if (name_len <= BTRFS_NAME_LEN) {
 853                         len = name_len;
 854                         error = 0;
 855                 } else {
 856                         len = BTRFS_NAME_LEN;
 857                         error = REF_ERR_NAME_TOO_LONG;
 858                 }
 859                 read_extent_buffer(eb, namebuf, (unsigned long)(di + 1), len);
 860
 861                 if (location.type == BTRFS_INODE_ITEM_KEY) {
 862                         add_inode_backref(inode_cache, location.objectid,
 863                                           key->objectid, key->offset, namebuf,
 864                                           len, filetype, key->type, error);
 865                 } else if (location.type == BTRFS_ROOT_ITEM_KEY) {
 866                         add_inode_backref(root_cache, location.objectid,
 867                                           key->objectid, key->offset,
 868                                           namebuf, len, filetype,
 869                                           key->type, error);
 870                 } else {
 871                         fprintf(stderr, "warning line %d\n", __LINE__);
 872                 }
 873
 874                 len = sizeof(*di) + name_len + data_len;
 875                 di = (struct btrfs_dir_item *)((char *)di + len);
 876                 cur += len;
 877         }
 878         if (key->type == BTRFS_DIR_INDEX_KEY && nritems > 1)
 879                 rec->errors |= I_ERR_DUP_DIR_INDEX;
 880
 881         return 0;
 882 }
 883
 884 static int process_inode_ref(struct extent_buffer *eb,
 885                              int slot, struct btrfs_key *key,
 886                              struct shared_node *active_node)
 887 {
 888         u32 total;
 889         u32 cur = 0;
 890         u32 len;
 891         u32 name_len;
 892         u64 index;
 893         int error;
 894         struct cache_tree *inode_cache;
 895         struct btrfs_inode_ref *ref;
 896         char namebuf[BTRFS_NAME_LEN];
 897
 898         inode_cache = &active_node->inode_cache;
 899
 900         ref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
 901         total = btrfs_item_size_nr(eb, slot);
 902         while (cur < total) {
 903                 name_len = btrfs_inode_ref_name_len(eb, ref);
 904                 index = btrfs_inode_ref_index(eb, ref);
 905                 if (name_len <= BTRFS_NAME_LEN) {
 906                         len = name_len;
 907                         error = 0;
 908                 } else {
 909                         len = BTRFS_NAME_LEN;
 910                         error = REF_ERR_NAME_TOO_LONG;
 911                 }
 912                 read_extent_buffer(eb, namebuf, (unsigned long)(ref + 1), len);
 913                 add_inode_backref(inode_cache, key->objectid, key->offset,
 914                                   index, namebuf, len, 0, key->type, error);
 915
 916                 len = sizeof(*ref) + name_len;
 917                 ref = (struct btrfs_inode_ref *)((char *)ref + len);
 918                 cur += len;
 919         }
 920         return 0;
 921 }
 922
 923 static int process_inode_extref(struct extent_buffer *eb,
 924                                 int slot, struct btrfs_key *key,
 925                                 struct shared_node *active_node)
 926 {
 927         u32 total;
 928         u32 cur = 0;
 929         u32 len;
 930         u32 name_len;
 931         u64 index;
 932         u64 parent;
 933         int error;
 934         struct cache_tree *inode_cache;
 935         struct btrfs_inode_extref *extref;
 936         char namebuf[BTRFS_NAME_LEN];
 937
 938         inode_cache = &active_node->inode_cache;
 939
 940         extref = btrfs_item_ptr(eb, slot, struct btrfs_inode_extref);
 941         total = btrfs_item_size_nr(eb, slot);
 942         while (cur < total) {
 943                 name_len = btrfs_inode_extref_name_len(eb, extref);
 944                 index = btrfs_inode_extref_index(eb, extref);
 945                 parent = btrfs_inode_extref_parent(eb, extref);
 946                 if (name_len <= BTRFS_NAME_LEN) {
 947                         len = name_len;
 948                         error = 0;
 949                 } else {
 950                         len = BTRFS_NAME_LEN;
 951                         error = REF_ERR_NAME_TOO_LONG;
 952                 }
 953                 read_extent_buffer(eb, namebuf,
 954                                    (unsigned long)(extref + 1), len);
 955                 add_inode_backref(inode_cache, key->objectid, parent,
 956                                   index, namebuf, len, 0, key->type, error);
 957
 958                 len = sizeof(*extref) + name_len;
 959                 extref = (struct btrfs_inode_extref *)((char *)extref + len);
 960                 cur += len;
 961         }
 962         return 0;
 963
 964 }
 965
 966 static u64 count_csum_range(struct btrfs_root *root, u64 start, u64 len)
 967 {
 968         struct btrfs_key key;
 969         struct btrfs_path path;
 970         struct extent_buffer *leaf;
 971         int ret ;
 972         size_t size;
 973         u64 found = 0;
 974         u64 csum_end;
 975         u16 csum_size = btrfs_super_csum_size(&root->fs_info->super_copy);
 976
 977         btrfs_init_path(&path);
 978
 979         key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
 980         key.offset = start;
 981         key.type = BTRFS_EXTENT_CSUM_KEY;
 982
 983         ret = btrfs_search_slot(NULL, root->fs_info->csum_root,
 984                                 &key, &path, 0, 0);
 985         BUG_ON(ret < 0);
 986         if (ret > 0 && path.slots[0] > 0) {
 987                 leaf = path.nodes[0];
 988                 btrfs_item_key_to_cpu(leaf, &key, path.slots[0] - 1);
 989                 if (key.objectid == BTRFS_EXTENT_CSUM_OBJECTID &&
 990                     key.type == BTRFS_EXTENT_CSUM_KEY)
 991                         path.slots[0]--;
 992         }
 993
 994         while (len > 0) {
 995                 leaf = path.nodes[0];
 996                 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
 997                         ret = btrfs_next_leaf(root->fs_info->csum_root, &path);
 998                         BUG_ON(ret < 0);
 999                         if (ret > 0)
1000                                 break;
1001                         leaf = path.nodes[0];
1002                 }
1003
1004                 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
1005                 if (key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
1006                     key.type != BTRFS_EXTENT_CSUM_KEY)
1007                         break;
1008
1009                 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
1010                 if (key.offset >= start + len)
1011                         break;
1012
1013                 if (key.offset > start)
1014                         start = key.offset;
1015
1016                 size = btrfs_item_size_nr(leaf, path.slots[0]);
1017                 csum_end = key.offset + (size / csum_size) * root->sectorsize;
1018                 if (csum_end > start) {
1019                         size = min(csum_end - start, len);
1020                         len -= size;
1021                         start += size;
1022                         found += size;
1023                 }
1024
1025                 path.slots[0]++;
1026         }
1027         btrfs_release_path(root->fs_info->csum_root, &path);
1028         return found;
1029 }
1030
1031 static int process_file_extent(struct btrfs_root *root,
1032                                 struct extent_buffer *eb,
1033                                 int slot, struct btrfs_key *key,
1034                                 struct shared_node *active_node)
1035 {
1036         struct inode_record *rec;
1037         struct btrfs_file_extent_item *fi;
1038         u64 num_bytes = 0;
1039         u64 disk_bytenr = 0;
1040         u64 extent_offset = 0;
1041         u64 mask = root->sectorsize - 1;
1042         int extent_type;
1043
1044         rec = active_node->current;
1045         BUG_ON(rec->ino != key->objectid || rec->refs > 1);
1046         rec->found_file_extent = 1;
1047
1048         if (rec->extent_start == (u64)-1) {
1049                 rec->extent_start = key->offset;
1050                 rec->extent_end = key->offset;
1051         }
1052
1053         if (rec->extent_end > key->offset)
1054                 rec->errors |= I_ERR_FILE_EXTENT_OVERLAP;
1055         else if (rec->extent_end < key->offset &&
1056                  rec->extent_end < rec->first_extent_gap)
1057                 rec->first_extent_gap = rec->extent_end;
1058
1059         fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
1060         extent_type = btrfs_file_extent_type(eb, fi);
1061
1062         if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
1063                 num_bytes = btrfs_file_extent_inline_len(eb, fi);
1064                 if (num_bytes == 0)
1065                         rec->errors |= I_ERR_BAD_FILE_EXTENT;
1066                 rec->found_size += num_bytes;
1067                 num_bytes = (num_bytes + mask) & ~mask;
1068         } else if (extent_type == BTRFS_FILE_EXTENT_REG ||
1069                    extent_type == BTRFS_FILE_EXTENT_PREALLOC) {
1070                 num_bytes = btrfs_file_extent_num_bytes(eb, fi);
1071                 disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
1072                 extent_offset = btrfs_file_extent_offset(eb, fi);
1073                 if (num_bytes == 0 || (num_bytes & mask))
1074                         rec->errors |= I_ERR_BAD_FILE_EXTENT;
1075                 if (num_bytes + extent_offset >
1076                     btrfs_file_extent_ram_bytes(eb, fi))
1077                         rec->errors |= I_ERR_BAD_FILE_EXTENT;
1078                 if (extent_type == BTRFS_FILE_EXTENT_PREALLOC &&
1079                     (btrfs_file_extent_compression(eb, fi) ||
1080                      btrfs_file_extent_encryption(eb, fi) ||
1081                      btrfs_file_extent_other_encoding(eb, fi)))
1082                         rec->errors |= I_ERR_BAD_FILE_EXTENT;
1083                 if (disk_bytenr > 0)
1084                         rec->found_size += num_bytes;
1085         } else {
1086                 rec->errors |= I_ERR_BAD_FILE_EXTENT;
1087         }
1088         rec->extent_end = key->offset + num_bytes;
1089
1090         if (disk_bytenr > 0) {
1091                 u64 found;
1092                 if (btrfs_file_extent_compression(eb, fi))
1093                         num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
1094                 else
1095                         disk_bytenr += extent_offset;
1096
1097                 found = count_csum_range(root, disk_bytenr, num_bytes);
1098                 if (extent_type == BTRFS_FILE_EXTENT_REG) {
1099                         if (found > 0)
1100                                 rec->found_csum_item = 1;
1101                         if (found < num_bytes)
1102                                 rec->some_csum_missing = 1;
1103                 } else if (extent_type == BTRFS_FILE_EXTENT_PREALLOC) {
1104                         if (found > 0)
1105                                 rec->errors |= I_ERR_ODD_CSUM_ITEM;
1106                 }
1107         }
1108         return 0;
1109 }
1110
1111 static int process_one_leaf(struct btrfs_root *root, struct extent_buffer *eb,
1112                             struct walk_control *wc)
1113 {
1114         struct btrfs_key key;
1115         u32 nritems;
1116         int i;
1117         int ret = 0;
1118         struct cache_tree *inode_cache;
1119         struct shared_node *active_node;
1120
1121         if (wc->root_level == wc->active_node &&
1122             btrfs_root_refs(&root->root_item) == 0)
1123                 return 0;
1124
1125         active_node = wc->nodes[wc->active_node];
1126         inode_cache = &active_node->inode_cache;
1127         nritems = btrfs_header_nritems(eb);
1128         for (i = 0; i < nritems; i++) {
1129                 btrfs_item_key_to_cpu(eb, &key, i);
1130
1131                 if (key.objectid == BTRFS_FREE_SPACE_OBJECTID)
1132                         continue;
1133
1134                 if (active_node->current == NULL ||
1135                     active_node->current->ino < key.objectid) {
1136                         if (active_node->current) {
1137                                 active_node->current->checked = 1;
1138                                 maybe_free_inode_rec(inode_cache,
1139                                                      active_node->current);
1140                         }
1141                         active_node->current = get_inode_rec(inode_cache,
1142                                                              key.objectid, 1);
1143                 }
1144                 switch (key.type) {
1145                 case BTRFS_DIR_ITEM_KEY:
1146                 case BTRFS_DIR_INDEX_KEY:
1147                         ret = process_dir_item(root, eb, i, &key, active_node);
1148                         break;
1149                 case BTRFS_INODE_REF_KEY:
1150                         ret = process_inode_ref(eb, i, &key, active_node);
1151                         break;
1152                 case BTRFS_INODE_EXTREF_KEY:
1153                         ret = process_inode_extref(eb, i, &key, active_node);
1154                         break;
1155                 case BTRFS_INODE_ITEM_KEY:
1156                         ret = process_inode_item(eb, i, &key, active_node);
1157                         break;
1158                 case BTRFS_EXTENT_DATA_KEY:
1159                         ret = process_file_extent(root, eb, i, &key,
1160                                                   active_node);
1161                         break;
1162                 default:
1163                         break;
1164                 };
1165         }
1166         return ret;
1167 }
1168
1169 static void reada_walk_down(struct btrfs_root *root,
1170                             struct extent_buffer *node, int slot)
1171 {
1172         u64 bytenr;
1173         u64 ptr_gen;
1174         u32 nritems;
1175         u32 blocksize;
1176         int i;
1177         int ret;
1178         int level;
1179
1180         level = btrfs_header_level(node);
1181         if (level != 1)
1182                 return;
1183
1184         nritems = btrfs_header_nritems(node);
1185         blocksize = btrfs_level_size(root, level - 1);
1186         for (i = slot; i < nritems; i++) {
1187                 bytenr = btrfs_node_blockptr(node, i);
1188                 ptr_gen = btrfs_node_ptr_generation(node, i);
1189                 ret = readahead_tree_block(root, bytenr, blocksize, ptr_gen);
1190                 if (ret)
1191                         break;
1192         }
1193 }
1194
1195 static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
1196                           struct walk_control *wc, int *level)
1197 {
1198         u64 bytenr;
1199         u64 ptr_gen;
1200         struct extent_buffer *next;
1201         struct extent_buffer *cur;
1202         u32 blocksize;
1203         int ret;
1204         u64 refs;
1205
1206         WARN_ON(*level < 0);
1207         WARN_ON(*level >= BTRFS_MAX_LEVEL);
1208         ret = btrfs_lookup_extent_info(NULL, root,
1209                                        path->nodes[*level]->start,
1210                                        path->nodes[*level]->len, &refs, NULL);
1211         if (ret < 0)
1212                 goto out;
1213
1214         if (refs > 1) {
1215                 ret = enter_shared_node(root, path->nodes[*level]->start,
1216                                         refs, wc, *level);
1217                 if (ret > 0)
1218                         goto out;
1219         }
1220
1221         while (*level >= 0) {
1222                 WARN_ON(*level < 0);
1223                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1224                 cur = path->nodes[*level];
1225
1226                 if (btrfs_header_level(cur) != *level)
1227                         WARN_ON(1);
1228
1229                 if (path->slots[*level] >= btrfs_header_nritems(cur))
1230                         break;
1231                 if (*level == 0) {
1232                         ret = process_one_leaf(root, cur, wc);
1233                         break;
1234                 }
1235                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
1236                 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
1237                 blocksize = btrfs_level_size(root, *level - 1);
1238                 ret = btrfs_lookup_extent_info(NULL, root, bytenr, blocksize,
1239                                                &refs, NULL);
1240                 if (ret < 0)
1241                         refs = 0;
1242
1243                 if (refs > 1) {
1244                         ret = enter_shared_node(root, bytenr, refs,
1245                                                 wc, *level - 1);
1246                         if (ret > 0) {
1247                                 path->slots[*level]++;
1248                                 continue;
1249                         }
1250                 }
1251
1252                 next = btrfs_find_tree_block(root, bytenr, blocksize);
1253                 if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
1254                         free_extent_buffer(next);
1255                         reada_walk_down(root, cur, path->slots[*level]);
1256                         next = read_tree_block(root, bytenr, blocksize,
1257                                                ptr_gen);
1258                 }
1259
1260                 *level = *level - 1;
1261                 free_extent_buffer(path->nodes[*level]);
1262                 path->nodes[*level] = next;
1263                 path->slots[*level] = 0;
1264         }
1265 out:
1266         path->slots[*level] = btrfs_header_nritems(path->nodes[*level]);
1267         return 0;
1268 }
1269
1270 static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
1271                         struct walk_control *wc, int *level)
1272 {
1273         int i;
1274         struct extent_buffer *leaf;
1275
1276         for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
1277                 leaf = path->nodes[i];
1278                 if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) {
1279                         path->slots[i]++;
1280                         *level = i;
1281                         return 0;
1282                 } else {
1283                         free_extent_buffer(path->nodes[*level]);
1284                         path->nodes[*level] = NULL;
1285                         BUG_ON(*level > wc->active_node);
1286                         if (*level == wc->active_node)
1287                                 leave_shared_node(root, wc, *level);
1288                         *level = i + 1;
1289                 }
1290         }
1291         return 1;
1292 }
1293
1294 static int check_root_dir(struct inode_record *rec)
1295 {
1296         struct inode_backref *backref;
1297         int ret = -1;
1298
1299         if (!rec->found_inode_item || rec->errors)
1300                 goto out;
1301         if (rec->nlink != 1 || rec->found_link != 0)
1302                 goto out;
1303         if (list_empty(&rec->backrefs))
1304                 goto out;
1305         backref = list_entry(rec->backrefs.next, struct inode_backref, list);
1306         if (!backref->found_inode_ref)
1307                 goto out;
1308         if (backref->index != 0 || backref->namelen != 2 ||
1309             memcmp(backref->name, "..", 2))
1310                 goto out;
1311         if (backref->found_dir_index || backref->found_dir_item)
1312                 goto out;
1313         ret = 0;
1314 out:
1315         return ret;
1316 }
1317
1318 static int check_inode_recs(struct btrfs_root *root,
1319                             struct cache_tree *inode_cache)
1320 {
1321         struct cache_extent *cache;
1322         struct ptr_node *node;
1323         struct inode_record *rec;
1324         struct inode_backref *backref;
1325         int ret;
1326         u64 error = 0;
1327         u64 root_dirid = btrfs_root_dirid(&root->root_item);
1328
1329         if (btrfs_root_refs(&root->root_item) == 0) {
1330                 if (!cache_tree_empty(inode_cache))
1331                         fprintf(stderr, "warning line %d\n", __LINE__);
1332                 return 0;
1333         }
1334
1335         rec = get_inode_rec(inode_cache, root_dirid, 0);
1336         if (rec) {
1337                 ret = check_root_dir(rec);
1338                 if (ret) {
1339                         fprintf(stderr, "root %llu root dir %llu error\n",
1340                                 (unsigned long long)root->root_key.objectid,
1341                                 (unsigned long long)root_dirid);
1342                         error++;
1343                 }
1344         } else {
1345                 fprintf(stderr, "root %llu root dir %llu not found\n",
1346                         (unsigned long long)root->root_key.objectid,
1347                         (unsigned long long)root_dirid);
1348         }
1349
1350         while (1) {
1351                 cache = find_first_cache_extent(inode_cache, 0);
1352                 if (!cache)
1353                         break;
1354                 node = container_of(cache, struct ptr_node, cache);
1355                 rec = node->data;
1356                 remove_cache_extent(inode_cache, &node->cache);
1357                 free(node);
1358                 if (rec->ino == root_dirid ||
1359                     rec->ino == BTRFS_ORPHAN_OBJECTID) {
1360                         free_inode_rec(rec);
1361                         continue;
1362                 }
1363
1364                 if (rec->errors & I_ERR_NO_ORPHAN_ITEM) {
1365                         ret = check_orphan_item(root, rec->ino);
1366                         if (ret == 0)
1367                                 rec->errors &= ~I_ERR_NO_ORPHAN_ITEM;
1368                         if (can_free_inode_rec(rec)) {
1369                                 free_inode_rec(rec);
1370                                 continue;
1371                         }
1372                 }
1373
1374                 error++;
1375                 if (!rec->found_inode_item)
1376                         rec->errors |= I_ERR_NO_INODE_ITEM;
1377                 if (rec->found_link != rec->nlink)
1378                         rec->errors |= I_ERR_LINK_COUNT_WRONG;
1379                 fprintf(stderr, "root %llu inode %llu errors %x\n",
1380                         (unsigned long long) root->root_key.objectid,
1381                         (unsigned long long) rec->ino, rec->errors);
1382                 list_for_each_entry(backref, &rec->backrefs, list) {
1383                         if (!backref->found_dir_item)
1384                                 backref->errors |= REF_ERR_NO_DIR_ITEM;
1385                         if (!backref->found_dir_index)
1386                                 backref->errors |= REF_ERR_NO_DIR_INDEX;
1387                         if (!backref->found_inode_ref)
1388                                 backref->errors |= REF_ERR_NO_INODE_REF;
1389                         fprintf(stderr, "\tunresolved ref dir %llu index %llu"
1390                                 " namelen %u name %s filetype %d error %x\n",
1391                                 (unsigned long long)backref->dir,
1392                                 (unsigned long long)backref->index,
1393                                 backref->namelen, backref->name,
1394                                 backref->filetype, backref->errors);
1395                 }
1396                 free_inode_rec(rec);
1397         }
1398         return (error > 0) ? -1 : 0;
1399 }
1400
1401 static struct root_record *get_root_rec(struct cache_tree *root_cache,
1402                                         u64 objectid)
1403 {
1404         struct cache_extent *cache;
1405         struct root_record *rec = NULL;
1406         int ret;
1407
1408         cache = find_cache_extent(root_cache, objectid, 1);
1409         if (cache) {
1410                 rec = container_of(cache, struct root_record, cache);
1411         } else {
1412                 rec = calloc(1, sizeof(*rec));
1413                 rec->objectid = objectid;
1414                 INIT_LIST_HEAD(&rec->backrefs);
1415                 rec->cache.start = objectid;
1416                 rec->cache.size = 1;
1417
1418                 ret = insert_existing_cache_extent(root_cache, &rec->cache);
1419                 BUG_ON(ret);
1420         }
1421         return rec;
1422 }
1423
1424 static struct root_backref *get_root_backref(struct root_record *rec,
1425                                              u64 ref_root, u64 dir, u64 index,
1426                                              const char *name, int namelen)
1427 {
1428         struct root_backref *backref;
1429
1430         list_for_each_entry(backref, &rec->backrefs, list) {
1431                 if (backref->ref_root != ref_root || backref->dir != dir ||
1432                     backref->namelen != namelen)
1433                         continue;
1434                 if (memcmp(name, backref->name, namelen))
1435                         continue;
1436                 return backref;
1437         }
1438
1439         backref = malloc(sizeof(*backref) + namelen + 1);
1440         memset(backref, 0, sizeof(*backref));
1441         backref->ref_root = ref_root;
1442         backref->dir = dir;
1443         backref->index = index;
1444         backref->namelen = namelen;
1445         memcpy(backref->name, name, namelen);
1446         backref->name[namelen] = '\0';
1447         list_add_tail(&backref->list, &rec->backrefs);
1448         return backref;
1449 }
1450
1451 static void free_root_recs(struct cache_tree *root_cache)
1452 {
1453         struct cache_extent *cache;
1454         struct root_record *rec;
1455         struct root_backref *backref;
1456
1457         while (1) {
1458                 cache = find_first_cache_extent(root_cache, 0);
1459                 if (!cache)
1460                         break;
1461                 rec = container_of(cache, struct root_record, cache);
1462                 remove_cache_extent(root_cache, &rec->cache);
1463
1464                 while (!list_empty(&rec->backrefs)) {
1465                         backref = list_entry(rec->backrefs.next,
1466                                              struct root_backref, list);
1467                         list_del(&backref->list);
1468                         free(backref);
1469                 }
1470                 kfree(rec);
1471         }
1472 }
1473
1474 static int add_root_backref(struct cache_tree *root_cache,
1475                             u64 root_id, u64 ref_root, u64 dir, u64 index,
1476                             const char *name, int namelen,
1477                             int item_type, int errors)
1478 {
1479         struct root_record *rec;
1480         struct root_backref *backref;
1481
1482         rec = get_root_rec(root_cache, root_id);
1483         backref = get_root_backref(rec, ref_root, dir, index, name, namelen);
1484
1485         backref->errors |= errors;
1486
1487         if (item_type != BTRFS_DIR_ITEM_KEY) {
1488                 if (backref->found_dir_index || backref->found_back_ref ||
1489                     backref->found_forward_ref) {
1490                         if (backref->index != index)
1491                                 backref->errors |= REF_ERR_INDEX_UNMATCH;
1492                 } else {
1493                         backref->index = index;
1494                 }
1495         }
1496
1497         if (item_type == BTRFS_DIR_ITEM_KEY) {
1498                 backref->found_dir_item = 1;
1499                 backref->reachable = 1;
1500                 rec->found_ref++;
1501         } else if (item_type == BTRFS_DIR_INDEX_KEY) {
1502                 backref->found_dir_index = 1;
1503         } else if (item_type == BTRFS_ROOT_REF_KEY) {
1504                 if (backref->found_forward_ref)
1505                         backref->errors |= REF_ERR_DUP_ROOT_REF;
1506                 backref->found_forward_ref = 1;
1507         } else if (item_type == BTRFS_ROOT_BACKREF_KEY) {
1508                 if (backref->found_back_ref)
1509                         backref->errors |= REF_ERR_DUP_ROOT_BACKREF;
1510                 backref->found_back_ref = 1;
1511         } else {
1512                 BUG_ON(1);
1513         }
1514
1515         return 0;
1516 }
1517
1518 static int merge_root_recs(struct btrfs_root *root,
1519                            struct cache_tree *src_cache,
1520                            struct cache_tree *dst_cache)
1521 {
1522         struct cache_extent *cache;
1523         struct ptr_node *node;
1524         struct inode_record *rec;
1525         struct inode_backref *backref;
1526
1527         if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
1528                 free_inode_recs(src_cache);
1529                 return 0;
1530         }
1531
1532         while (1) {
1533                 cache = find_first_cache_extent(src_cache, 0);
1534                 if (!cache)
1535                         break;
1536                 node = container_of(cache, struct ptr_node, cache);
1537                 rec = node->data;
1538                 remove_cache_extent(src_cache, &node->cache);
1539                 free(node);
1540
1541                 if (!is_child_root(root, root->objectid, rec->ino))
1542                         goto skip;
1543
1544                 list_for_each_entry(backref, &rec->backrefs, list) {
1545                         BUG_ON(backref->found_inode_ref);
1546                         if (backref->found_dir_item)
1547                                 add_root_backref(dst_cache, rec->ino,
1548                                         root->root_key.objectid, backref->dir,
1549                                         backref->index, backref->name,
1550                                         backref->namelen, BTRFS_DIR_ITEM_KEY,
1551                                         backref->errors);
1552                         if (backref->found_dir_index)
1553                                 add_root_backref(dst_cache, rec->ino,
1554                                         root->root_key.objectid, backref->dir,
1555                                         backref->index, backref->name,
1556                                         backref->namelen, BTRFS_DIR_INDEX_KEY,
1557                                         backref->errors);
1558                 }
1559 skip:
1560                 free_inode_rec(rec);
1561         }
1562         return 0;
1563 }
1564
1565 static int check_root_refs(struct btrfs_root *root,
1566                            struct cache_tree *root_cache)
1567 {
1568         struct root_record *rec;
1569         struct root_record *ref_root;
1570         struct root_backref *backref;
1571         struct cache_extent *cache;
1572         int loop = 1;
1573         int ret;
1574         int error;
1575         int errors = 0;
1576
1577         rec = get_root_rec(root_cache, BTRFS_FS_TREE_OBJECTID);
1578         rec->found_ref = 1;
1579
1580         /* fixme: this can not detect circular references */
1581         while (loop) {
1582                 loop = 0;
1583                 cache = find_first_cache_extent(root_cache, 0);
1584                 while (1) {
1585                         if (!cache)
1586                                 break;
1587                         rec = container_of(cache, struct root_record, cache);
1588                         cache = next_cache_extent(cache);
1589
1590                         if (rec->found_ref == 0)
1591                                 continue;
1592
1593                         list_for_each_entry(backref, &rec->backrefs, list) {
1594                                 if (!backref->reachable)
1595                                         continue;
1596
1597                                 ref_root = get_root_rec(root_cache,
1598                                                         backref->ref_root);
1599                                 if (ref_root->found_ref > 0)
1600                                         continue;
1601
1602                                 backref->reachable = 0;
1603                                 rec->found_ref--;
1604                                 if (rec->found_ref == 0)
1605                                         loop = 1;
1606                         }
1607                 }
1608         }
1609
1610         cache = find_first_cache_extent(root_cache, 0);
1611         while (1) {
1612                 if (!cache)
1613                         break;
1614                 rec = container_of(cache, struct root_record, cache);
1615                 cache = next_cache_extent(cache);
1616
1617                 if (rec->found_ref == 0 &&
1618                     rec->objectid >= BTRFS_FIRST_FREE_OBJECTID &&
1619                     rec->objectid <= BTRFS_LAST_FREE_OBJECTID) {
1620                         ret = check_orphan_item(root->fs_info->tree_root,
1621                                                 rec->objectid);
1622                         if (ret == 0)
1623                                 continue;
1624                         errors++;
1625                         fprintf(stderr, "fs tree %llu not referenced\n",
1626                                 (unsigned long long)rec->objectid);
1627                 }
1628
1629                 error = 0;
1630                 if (rec->found_ref > 0 && !rec->found_root_item)
1631                         error = 1;
1632                 list_for_each_entry(backref, &rec->backrefs, list) {
1633                         if (!backref->found_dir_item)
1634                                 backref->errors |= REF_ERR_NO_DIR_ITEM;
1635                         if (!backref->found_dir_index)
1636                                 backref->errors |= REF_ERR_NO_DIR_INDEX;
1637                         if (!backref->found_back_ref)
1638                                 backref->errors |= REF_ERR_NO_ROOT_BACKREF;
1639                         if (!backref->found_forward_ref)
1640                                 backref->errors |= REF_ERR_NO_ROOT_REF;
1641                         if (backref->reachable && backref->errors)
1642                                 error = 1;
1643                 }
1644                 if (!error)
1645                         continue;
1646
1647                 errors++;
1648                 fprintf(stderr, "fs tree %llu refs %u %s\n",
1649                         (unsigned long long)rec->objectid, rec->found_ref,
1650                          rec->found_root_item ? "" : "not found");
1651
1652                 list_for_each_entry(backref, &rec->backrefs, list) {
1653                         if (!backref->reachable)
1654                                 continue;
1655                         if (!backref->errors && rec->found_root_item)
1656                                 continue;
1657                         fprintf(stderr, "\tunresolved ref root %llu dir %llu"
1658                                 " index %llu namelen %u name %s error %x\n",
1659                                 (unsigned long long)backref->ref_root,
1660                                 (unsigned long long)backref->dir,
1661                                 (unsigned long long)backref->index,
1662                                 backref->namelen, backref->name,
1663                                 backref->errors);
1664                 }
1665         }
1666         return errors > 0 ? 1 : 0;
1667 }
1668
1669 static int process_root_ref(struct extent_buffer *eb, int slot,
1670                             struct btrfs_key *key,
1671                             struct cache_tree *root_cache)
1672 {
1673         u64 dirid;
1674         u64 index;
1675         u32 len;
1676         u32 name_len;
1677         struct btrfs_root_ref *ref;
1678         char namebuf[BTRFS_NAME_LEN];
1679         int error;
1680
1681         ref = btrfs_item_ptr(eb, slot, struct btrfs_root_ref);
1682
1683         dirid = btrfs_root_ref_dirid(eb, ref);
1684         index = btrfs_root_ref_sequence(eb, ref);
1685         name_len = btrfs_root_ref_name_len(eb, ref);
1686
1687         if (name_len <= BTRFS_NAME_LEN) {
1688                 len = name_len;
1689                 error = 0;
1690         } else {
1691                 len = BTRFS_NAME_LEN;
1692                 error = REF_ERR_NAME_TOO_LONG;
1693         }
1694         read_extent_buffer(eb, namebuf, (unsigned long)(ref + 1), len);
1695
1696         if (key->type == BTRFS_ROOT_REF_KEY) {
1697                 add_root_backref(root_cache, key->offset, key->objectid, dirid,
1698                                  index, namebuf, len, key->type, error);
1699         } else {
1700                 add_root_backref(root_cache, key->objectid, key->offset, dirid,
1701                                  index, namebuf, len, key->type, error);
1702         }
1703         return 0;
1704 }
1705
1706 static int check_fs_root(struct btrfs_root *root,
1707                          struct cache_tree *root_cache,
1708                          struct walk_control *wc)
1709 {
1710         int ret = 0;
1711         int wret;
1712         int level;
1713         struct btrfs_path path;
1714         struct shared_node root_node;
1715         struct root_record *rec;
1716         struct btrfs_root_item *root_item = &root->root_item;
1717
1718         if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
1719                 rec = get_root_rec(root_cache, root->root_key.objectid);
1720                 if (btrfs_root_refs(root_item) > 0)
1721                         rec->found_root_item = 1;
1722         }
1723
1724         btrfs_init_path(&path);
1725         memset(&root_node, 0, sizeof(root_node));
1726         cache_tree_init(&root_node.root_cache);
1727         cache_tree_init(&root_node.inode_cache);
1728
1729         level = btrfs_header_level(root->node);
1730         memset(wc->nodes, 0, sizeof(wc->nodes));
1731         wc->nodes[level] = &root_node;
1732         wc->active_node = level;
1733         wc->root_level = level;
1734
1735         if (btrfs_root_refs(root_item) > 0 ||
1736             btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
1737                 path.nodes[level] = root->node;
1738                 extent_buffer_get(root->node);
1739                 path.slots[level] = 0;
1740         } else {
1741                 struct btrfs_key key;
1742                 struct btrfs_disk_key found_key;
1743
1744                 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
1745                 level = root_item->drop_level;
1746                 path.lowest_level = level;
1747                 wret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
1748                 BUG_ON(wret < 0);
1749                 btrfs_node_key(path.nodes[level], &found_key,
1750                                 path.slots[level]);
1751                 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
1752                                         sizeof(found_key)));
1753         }
1754
1755         while (1) {
1756                 wret = walk_down_tree(root, &path, wc, &level);
1757                 if (wret < 0)
1758                         ret = wret;
1759                 if (wret != 0)
1760                         break;
1761
1762                 wret = walk_up_tree(root, &path, wc, &level);
1763                 if (wret < 0)
1764                         ret = wret;
1765                 if (wret != 0)
1766                         break;
1767         }
1768         btrfs_release_path(root, &path);
1769
1770         merge_root_recs(root, &root_node.root_cache, root_cache);
1771
1772         if (root_node.current) {
1773                 root_node.current->checked = 1;
1774                 maybe_free_inode_rec(&root_node.inode_cache,
1775                                 root_node.current);
1776         }
1777
1778         ret = check_inode_recs(root, &root_node.inode_cache);
1779         return ret;
1780 }
1781
1782 static int fs_root_objectid(u64 objectid)
1783 {
1784         if (objectid == BTRFS_FS_TREE_OBJECTID ||
1785             objectid == BTRFS_TREE_RELOC_OBJECTID ||
1786             objectid == BTRFS_DATA_RELOC_TREE_OBJECTID ||
1787             (objectid >= BTRFS_FIRST_FREE_OBJECTID &&
1788              objectid <= BTRFS_LAST_FREE_OBJECTID))
1789                 return 1;
1790         return 0;
1791 }
1792
1793 static int check_fs_roots(struct btrfs_root *root,
1794                           struct cache_tree *root_cache)
1795 {
1796         struct btrfs_path path;
1797         struct btrfs_key key;
1798         struct walk_control wc;
1799         struct extent_buffer *leaf;
1800         struct btrfs_root *tmp_root;
1801         struct btrfs_root *tree_root = root->fs_info->tree_root;
1802         int ret;
1803         int err = 0;
1804
1805         memset(&wc, 0, sizeof(wc));
1806         cache_tree_init(&wc.shared);
1807         btrfs_init_path(&path);
1808
1809         key.offset = 0;
1810         key.objectid = 0;
1811         key.type = BTRFS_ROOT_ITEM_KEY;
1812         ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0);
1813         BUG_ON(ret < 0);
1814         while (1) {
1815                 leaf = path.nodes[0];
1816                 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
1817                         ret = btrfs_next_leaf(tree_root, &path);
1818                         if (ret != 0)
1819                                 break;
1820                         leaf = path.nodes[0];
1821                 }
1822                 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
1823                 if (key.type == BTRFS_ROOT_ITEM_KEY &&
1824                     fs_root_objectid(key.objectid)) {
1825                         tmp_root = btrfs_read_fs_root_no_cache(root->fs_info,
1826                                                                &key);
1827                         ret = check_fs_root(tmp_root, root_cache, &wc);
1828                         if (ret)
1829                                 err = 1;
1830                         btrfs_free_fs_root(root->fs_info, tmp_root);
1831                 } else if (key.type == BTRFS_ROOT_REF_KEY ||
1832                            key.type == BTRFS_ROOT_BACKREF_KEY) {
1833                         process_root_ref(leaf, path.slots[0], &key,
1834                                          root_cache);
1835                 }
1836                 path.slots[0]++;
1837         }
1838         btrfs_release_path(tree_root, &path);
1839
1840         if (!cache_tree_empty(&wc.shared))
1841                 fprintf(stderr, "warning line %d\n", __LINE__);
1842
1843         return err;
1844 }
1845
1846 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
1847 {
1848         struct list_head *cur = rec->backrefs.next;
1849         struct extent_backref *back;
1850         struct tree_backref *tback;
1851         struct data_backref *dback;
1852         u64 found = 0;
1853         int err = 0;
1854
1855         while(cur != &rec->backrefs) {
1856                 back = list_entry(cur, struct extent_backref, list);
1857                 cur = cur->next;
1858                 if (!back->found_extent_tree) {
1859                         err = 1;
1860                         if (!print_errs)
1861                                 goto out;
1862                         if (back->is_data) {
1863                                 dback = (struct data_backref *)back;
1864                                 fprintf(stderr, "Backref %llu %s %llu"
1865                                         " owner %llu offset %llu num_refs %lu"
1866                                         " not found in extent tree\n",
1867                                         (unsigned long long)rec->start,
1868                                         back->full_backref ?
1869                                         "parent" : "root",
1870                                         back->full_backref ?
1871                                         (unsigned long long)dback->parent:
1872                                         (unsigned long long)dback->root,
1873                                         (unsigned long long)dback->owner,
1874                                         (unsigned long long)dback->offset,
1875                                         (unsigned long)dback->num_refs);
1876                         } else {
1877                                 tback = (struct tree_backref *)back;
1878                                 fprintf(stderr, "Backref %llu parent %llu"
1879                                         " root %llu not found in extent tree\n",
1880                                         (unsigned long long)rec->start,
1881                                         (unsigned long long)tback->parent,
1882                                         (unsigned long long)tback->root);
1883                         }
1884                 }
1885                 if (!back->is_data && !back->found_ref) {
1886                         err = 1;
1887                         if (!print_errs)
1888                                 goto out;
1889                         tback = (struct tree_backref *)back;
1890                         fprintf(stderr, "Backref %llu %s %llu not referenced back %p\n",
1891                                 (unsigned long long)rec->start,
1892                                 back->full_backref ? "parent" : "root",
1893                                 back->full_backref ?
1894                                 (unsigned long long)tback->parent :
1895                                 (unsigned long long)tback->root, back);
1896                 }
1897                 if (back->is_data) {
1898                         dback = (struct data_backref *)back;
1899                         if (dback->found_ref != dback->num_refs) {
1900                                 err = 1;
1901                                 if (!print_errs)
1902                                         goto out;
1903                                 fprintf(stderr, "Incorrect local backref count"
1904                                         " on %llu %s %llu owner %llu"
1905                                         " offset %llu found %u wanted %u back %p\n",
1906                                         (unsigned long long)rec->start,
1907                                         back->full_backref ?
1908                                         "parent" : "root",
1909                                         back->full_backref ?
1910                                         (unsigned long long)dback->parent:
1911                                         (unsigned long long)dback->root,
1912                                         (unsigned long long)dback->owner,
1913                                         (unsigned long long)dback->offset,
1914                                         dback->found_ref, dback->num_refs, back);
1915                         }
1916                 }
1917                 if (!back->is_data) {
1918                         found += 1;
1919                 } else {
1920                         dback = (struct data_backref *)back;
1921                         found += dback->found_ref;
1922                 }
1923         }
1924         if (found != rec->refs) {
1925                 err = 1;
1926                 if (!print_errs)
1927                         goto out;
1928                 fprintf(stderr, "Incorrect global backref count "
1929                         "on %llu found %llu wanted %llu\n",
1930                         (unsigned long long)rec->start,
1931                         (unsigned long long)found,
1932                         (unsigned long long)rec->refs);
1933         }
1934 out:
1935         return err;
1936 }
1937
1938 static int free_all_extent_backrefs(struct extent_record *rec)
1939 {
1940         struct extent_backref *back;
1941         struct list_head *cur;
1942         while (!list_empty(&rec->backrefs)) {
1943                 cur = rec->backrefs.next;
1944                 back = list_entry(cur, struct extent_backref, list);
1945                 list_del(cur);
1946                 free(back);
1947         }
1948         return 0;
1949 }
1950
1951 static int maybe_free_extent_rec(struct cache_tree *extent_cache,
1952                                  struct extent_record *rec)
1953 {
1954         if (rec->content_checked && rec->owner_ref_checked &&
1955             rec->extent_item_refs == rec->refs && rec->refs > 0 &&
1956             !all_backpointers_checked(rec, 0)) {
1957                 remove_cache_extent(extent_cache, &rec->cache);
1958                 free_all_extent_backrefs(rec);
1959                 free(rec);
1960         }
1961         return 0;
1962 }
1963
1964 static int check_owner_ref(struct btrfs_root *root,
1965                             struct extent_record *rec,
1966                             struct extent_buffer *buf)
1967 {
1968         struct extent_backref *node;
1969         struct tree_backref *back;
1970         struct btrfs_root *ref_root;
1971         struct btrfs_key key;
1972         struct btrfs_path path;
1973         int level;
1974         int found = 0;
1975
1976         list_for_each_entry(node, &rec->backrefs, list) {
1977                 if (node->is_data)
1978                         continue;
1979                 if (!node->found_ref)
1980                         continue;
1981                 if (node->full_backref)
1982                         continue;
1983                 back = (struct tree_backref *)node;
1984                 if (btrfs_header_owner(buf) == back->root)
1985                         return 0;
1986         }
1987         BUG_ON(rec->is_root);
1988
1989         /* try to find the block by search corresponding fs tree */
1990         key.objectid = btrfs_header_owner(buf);
1991         key.type = BTRFS_ROOT_ITEM_KEY;
1992         key.offset = (u64)-1;
1993
1994         ref_root = btrfs_read_fs_root(root->fs_info, &key);
1995         BUG_ON(IS_ERR(ref_root));
1996
1997         level = btrfs_header_level(buf);
1998         if (level == 0)
1999                 btrfs_item_key_to_cpu(buf, &key, 0);
2000         else
2001                 btrfs_node_key_to_cpu(buf, &key, 0);
2002
2003         btrfs_init_path(&path);
2004         path.lowest_level = level + 1;
2005         btrfs_search_slot(NULL, ref_root, &key, &path, 0, 0);
2006
2007         if (buf->start == btrfs_node_blockptr(path.nodes[level + 1],
2008                                               path.slots[level + 1]))
2009                 found = 1;
2010
2011         btrfs_release_path(ref_root, &path);
2012         return found ? 0 : 1;
2013 }
2014
2015 static int is_extent_tree_record(struct extent_record *rec)
2016 {
2017         struct list_head *cur = rec->backrefs.next;
2018         struct extent_backref *node;
2019         struct tree_backref *back;
2020         int is_extent = 0;
2021
2022         while(cur != &rec->backrefs) {
2023                 node = list_entry(cur, struct extent_backref, list);
2024                 cur = cur->next;
2025                 if (node->is_data)
2026                         return 0;
2027                 back = (struct tree_backref *)node;
2028                 if (node->full_backref)
2029                         return 0;
2030                 if (back->root == BTRFS_EXTENT_TREE_OBJECTID)
2031                         is_extent = 1;
2032         }
2033         return is_extent;
2034 }
2035
2036
2037 static int record_bad_block_io(struct btrfs_fs_info *info,
2038                                struct cache_tree *extent_cache,
2039                                u64 start, u64 len)
2040 {
2041         struct extent_record *rec;
2042         struct cache_extent *cache;
2043         struct btrfs_key key;
2044
2045         cache = find_cache_extent(extent_cache, start, len);
2046         if (!cache)
2047                 return 0;
2048
2049         rec = container_of(cache, struct extent_record, cache);
2050         if (!is_extent_tree_record(rec))
2051                 return 0;
2052
2053         btrfs_disk_key_to_cpu(&key, &rec->parent_key);
2054         return btrfs_add_corrupt_extent_record(info, &key, start, len, 0);
2055 }
2056
2057 static int check_block(struct btrfs_root *root,
2058                        struct cache_tree *extent_cache,
2059                        struct extent_buffer *buf, u64 flags)
2060 {
2061         struct extent_record *rec;
2062         struct cache_extent *cache;
2063         struct btrfs_key key;
2064         int ret = 1;
2065         int level;
2066
2067         cache = find_cache_extent(extent_cache, buf->start, buf->len);
2068         if (!cache)
2069                 return 1;
2070         rec = container_of(cache, struct extent_record, cache);
2071         rec->generation = btrfs_header_generation(buf);
2072
2073         level = btrfs_header_level(buf);
2074         if (btrfs_header_nritems(buf) > 0) {
2075
2076                 if (level == 0)
2077                         btrfs_item_key_to_cpu(buf, &key, 0);
2078                 else
2079                         btrfs_node_key_to_cpu(buf, &key, 0);
2080
2081                 rec->info_objectid = key.objectid;
2082         }
2083         rec->info_level = level;
2084
2085         if (btrfs_is_leaf(buf))
2086                 ret = btrfs_check_leaf(root, &rec->parent_key, buf);
2087         else
2088                 ret = btrfs_check_node(root, &rec->parent_key, buf);
2089
2090         if (ret) {
2091                 fprintf(stderr, "bad block %llu\n",
2092                         (unsigned long long)buf->start);
2093         } else {
2094                 rec->content_checked = 1;
2095                 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)
2096                         rec->owner_ref_checked = 1;
2097                 else {
2098                         ret = check_owner_ref(root, rec, buf);
2099                         if (!ret)
2100                                 rec->owner_ref_checked = 1;
2101                 }
2102         }
2103         if (!ret)
2104                 maybe_free_extent_rec(extent_cache, rec);
2105         return ret;
2106 }
2107
2108 static struct tree_backref *find_tree_backref(struct extent_record *rec,
2109                                                 u64 parent, u64 root)
2110 {
2111         struct list_head *cur = rec->backrefs.next;
2112         struct extent_backref *node;
2113         struct tree_backref *back;
2114
2115         while(cur != &rec->backrefs) {
2116                 node = list_entry(cur, struct extent_backref, list);
2117                 cur = cur->next;
2118                 if (node->is_data)
2119                         continue;
2120                 back = (struct tree_backref *)node;
2121                 if (parent > 0) {
2122                         if (!node->full_backref)
2123                                 continue;
2124                         if (parent == back->parent)
2125                                 return back;
2126                 } else {
2127                         if (node->full_backref)
2128                                 continue;
2129                         if (back->root == root)
2130                                 return back;
2131                 }
2132         }
2133         return NULL;
2134 }
2135
2136 static struct tree_backref *alloc_tree_backref(struct extent_record *rec,
2137                                                 u64 parent, u64 root)
2138 {
2139         struct tree_backref *ref = malloc(sizeof(*ref));
2140         memset(&ref->node, 0, sizeof(ref->node));
2141         if (parent > 0) {
2142                 ref->parent = parent;
2143                 ref->node.full_backref = 1;
2144         } else {
2145                 ref->root = root;
2146                 ref->node.full_backref = 0;
2147         }
2148         list_add_tail(&ref->node.list, &rec->backrefs);
2149
2150         return ref;
2151 }
2152
2153 static struct data_backref *find_data_backref(struct extent_record *rec,
2154                                                 u64 parent, u64 root,
2155                                                 u64 owner, u64 offset)
2156 {
2157         struct list_head *cur = rec->backrefs.next;
2158         struct extent_backref *node;
2159         struct data_backref *back;
2160
2161         while(cur != &rec->backrefs) {
2162                 node = list_entry(cur, struct extent_backref, list);
2163                 cur = cur->next;
2164                 if (!node->is_data)
2165                         continue;
2166                 back = (struct data_backref *)node;
2167                 if (parent > 0) {
2168                         if (!node->full_backref)
2169                                 continue;
2170                         if (parent == back->parent)
2171                                 return back;
2172                 } else {
2173                         if (node->full_backref)
2174                                 continue;
2175                         if (back->root == root && back->owner == owner &&
2176                             back->offset == offset)
2177                                 return back;
2178                 }
2179         }
2180         return NULL;
2181 }
2182
2183 static struct data_backref *alloc_data_backref(struct extent_record *rec,
2184                                                 u64 parent, u64 root,
2185                                                 u64 owner, u64 offset,
2186                                                 u64 max_size)
2187 {
2188         struct data_backref *ref = malloc(sizeof(*ref));
2189         memset(&ref->node, 0, sizeof(ref->node));
2190         ref->node.is_data = 1;
2191
2192         if (parent > 0) {
2193                 ref->parent = parent;
2194                 ref->owner = 0;
2195                 ref->offset = 0;
2196                 ref->node.full_backref = 1;
2197         } else {
2198                 ref->root = root;
2199                 ref->owner = owner;
2200                 ref->offset = offset;
2201                 ref->node.full_backref = 0;
2202         }
2203         ref->found_ref = 0;
2204         ref->num_refs = 0;
2205         list_add_tail(&ref->node.list, &rec->backrefs);
2206         if (max_size > rec->max_size)
2207                 rec->max_size = max_size;
2208         return ref;
2209 }
2210
2211 static int add_extent_rec(struct cache_tree *extent_cache,
2212                           struct btrfs_key *parent_key,
2213                           u64 start, u64 nr, u64 extent_item_refs,
2214                           int is_root, int inc_ref, int set_checked,
2215                           u64 max_size)
2216 {
2217         struct extent_record *rec;
2218         struct cache_extent *cache;
2219         int ret = 0;
2220
2221         cache = find_cache_extent(extent_cache, start, nr);
2222         if (cache) {
2223                 rec = container_of(cache, struct extent_record, cache);
2224                 if (inc_ref)
2225                         rec->refs++;
2226                 if (rec->nr == 1)
2227                         rec->nr = max(nr, max_size);
2228
2229                 if (start != rec->start) {
2230                         fprintf(stderr, "warning, start mismatch %llu %llu\n",
2231                                 (unsigned long long)rec->start,
2232                                 (unsigned long long)start);
2233                         ret = 1;
2234                 }
2235                 if (extent_item_refs) {
2236                         if (rec->extent_item_refs) {
2237                                 fprintf(stderr, "block %llu rec "
2238                                         "extent_item_refs %llu, passed %llu\n",
2239                                         (unsigned long long)start,
2240                                         (unsigned long long)
2241                                                         rec->extent_item_refs,
2242                                         (unsigned long long)extent_item_refs);
2243                         }
2244                         rec->extent_item_refs = extent_item_refs;
2245                 }
2246                 if (is_root)
2247                         rec->is_root = 1;
2248                 if (set_checked) {
2249                         rec->content_checked = 1;
2250                         rec->owner_ref_checked = 1;
2251                 }
2252
2253                 if (parent_key)
2254                         btrfs_cpu_key_to_disk(&rec->parent_key, parent_key);
2255
2256                 if (rec->max_size < max_size)
2257                         rec->max_size = max_size;
2258
2259                 maybe_free_extent_rec(extent_cache, rec);
2260                 return ret;
2261         }
2262         rec = malloc(sizeof(*rec));
2263         rec->start = start;
2264         rec->max_size = max_size;
2265         rec->nr = max(nr, max_size);
2266         rec->content_checked = 0;
2267         rec->owner_ref_checked = 0;
2268         INIT_LIST_HEAD(&rec->backrefs);
2269
2270         if (is_root)
2271                 rec->is_root = 1;
2272         else
2273                 rec->is_root = 0;
2274
2275         if (inc_ref)
2276                 rec->refs = 1;
2277         else
2278                 rec->refs = 0;
2279
2280         if (extent_item_refs)
2281                 rec->extent_item_refs = extent_item_refs;
2282         else
2283                 rec->extent_item_refs = 0;
2284
2285         if (parent_key)
2286                 btrfs_cpu_key_to_disk(&rec->parent_key, parent_key);
2287         else
2288                 memset(&rec->parent_key, 0, sizeof(*parent_key));
2289
2290         rec->cache.start = start;
2291         rec->cache.size = nr;
2292         ret = insert_existing_cache_extent(extent_cache, &rec->cache);
2293         BUG_ON(ret);
2294         bytes_used += nr;
2295         if (set_checked) {
2296                 rec->content_checked = 1;
2297                 rec->owner_ref_checked = 1;
2298         }
2299         return ret;
2300 }
2301
2302 static int add_tree_backref(struct cache_tree *extent_cache, u64 bytenr,
2303                             u64 parent, u64 root, int found_ref)
2304 {
2305         struct extent_record *rec;
2306         struct tree_backref *back;
2307         struct cache_extent *cache;
2308
2309         cache = find_cache_extent(extent_cache, bytenr, 1);
2310         if (!cache) {
2311                 add_extent_rec(extent_cache, NULL, bytenr, 1, 0, 0, 0, 0, 0);
2312                 cache = find_cache_extent(extent_cache, bytenr, 1);
2313                 if (!cache)
2314                         abort();
2315         }
2316
2317         rec = container_of(cache, struct extent_record, cache);
2318         if (rec->start != bytenr) {
2319                 abort();
2320         }
2321
2322         back = find_tree_backref(rec, parent, root);
2323         if (!back)
2324                 back = alloc_tree_backref(rec, parent, root);
2325
2326         if (found_ref) {
2327                 if (back->node.found_ref) {
2328                         fprintf(stderr, "Extent back ref already exists "
2329                                 "for %llu parent %llu root %llu \n",
2330                                 (unsigned long long)bytenr,
2331                                 (unsigned long long)parent,
2332                                 (unsigned long long)root);
2333                 }
2334                 back->node.found_ref = 1;
2335         } else {
2336                 if (back->node.found_extent_tree) {
2337                         fprintf(stderr, "Extent back ref already exists "
2338                                 "for %llu parent %llu root %llu \n",
2339                                 (unsigned long long)bytenr,
2340                                 (unsigned long long)parent,
2341                                 (unsigned long long)root);
2342                 }
2343                 back->node.found_extent_tree = 1;
2344         }
2345         return 0;
2346 }
2347
2348 static int add_data_backref(struct cache_tree *extent_cache, u64 bytenr,
2349                             u64 parent, u64 root, u64 owner, u64 offset,
2350                             u32 num_refs, int found_ref, u64 max_size)
2351 {
2352         struct extent_record *rec;
2353         struct data_backref *back;
2354         struct cache_extent *cache;
2355
2356         cache = find_cache_extent(extent_cache, bytenr, 1);
2357         if (!cache) {
2358                 add_extent_rec(extent_cache, NULL, bytenr, 1, 0, 0, 0, 0,
2359                                max_size);
2360                 cache = find_cache_extent(extent_cache, bytenr, 1);
2361                 if (!cache)
2362                         abort();
2363         }
2364
2365         rec = container_of(cache, struct extent_record, cache);
2366         if (rec->start != bytenr) {
2367                 abort();
2368         }
2369         if (rec->max_size < max_size)
2370                 rec->max_size = max_size;
2371
2372         back = find_data_backref(rec, parent, root, owner, offset);
2373         if (!back)
2374                 back = alloc_data_backref(rec, parent, root, owner, offset,
2375                                           max_size);
2376
2377         if (found_ref) {
2378                 BUG_ON(num_refs != 1);
2379                 back->node.found_ref = 1;
2380                 back->found_ref += 1;
2381         } else {
2382                 if (back->node.found_extent_tree) {
2383                         fprintf(stderr, "Extent back ref already exists "
2384                                 "for %llu parent %llu root %llu"
2385                                 "owner %llu offset %llu num_refs %lu\n",
2386                                 (unsigned long long)bytenr,
2387                                 (unsigned long long)parent,
2388                                 (unsigned long long)root,
2389                                 (unsigned long long)owner,
2390                                 (unsigned long long)offset,
2391                                 (unsigned long)num_refs);
2392                 }
2393                 back->num_refs = num_refs;
2394                 back->node.found_extent_tree = 1;
2395         }
2396         return 0;
2397 }
2398
2399 static int add_pending(struct cache_tree *pending,
2400                        struct cache_tree *seen, u64 bytenr, u32 size)
2401 {
2402         int ret;
2403         ret = insert_cache_extent(seen, bytenr, size);
2404         if (ret)
2405                 return ret;
2406         insert_cache_extent(pending, bytenr, size);
2407         return 0;
2408 }
2409
2410 static int pick_next_pending(struct cache_tree *pending,
2411                         struct cache_tree *reada,
2412                         struct cache_tree *nodes,
2413                         u64 last, struct block_info *bits, int bits_nr,
2414                         int *reada_bits)
2415 {
2416         unsigned long node_start = last;
2417         struct cache_extent *cache;
2418         int ret;
2419
2420         cache = find_first_cache_extent(reada, 0);
2421         if (cache) {
2422                 bits[0].start = cache->start;
2423                 bits[1].size = cache->size;
2424                 *reada_bits = 1;
2425                 return 1;
2426         }
2427         *reada_bits = 0;
2428         if (node_start > 32768)
2429                 node_start -= 32768;
2430
2431         cache = find_first_cache_extent(nodes, node_start);
2432         if (!cache)
2433                 cache = find_first_cache_extent(nodes, 0);
2434
2435         if (!cache) {
2436                  cache = find_first_cache_extent(pending, 0);
2437                  if (!cache)
2438                          return 0;
2439                  ret = 0;
2440                  do {
2441                          bits[ret].start = cache->start;
2442                          bits[ret].size = cache->size;
2443                          cache = next_cache_extent(cache);
2444                          ret++;
2445                  } while (cache && ret < bits_nr);
2446                  return ret;
2447         }
2448
2449         ret = 0;
2450         do {
2451                 bits[ret].start = cache->start;
2452                 bits[ret].size = cache->size;
2453                 cache = next_cache_extent(cache);
2454                 ret++;
2455         } while (cache && ret < bits_nr);
2456
2457         if (bits_nr - ret > 8) {
2458                 u64 lookup = bits[0].start + bits[0].size;
2459                 struct cache_extent *next;
2460                 next = find_first_cache_extent(pending, lookup);
2461                 while(next) {
2462                         if (next->start - lookup > 32768)
2463                                 break;
2464                         bits[ret].start = next->start;
2465                         bits[ret].size = next->size;
2466                         lookup = next->start + next->size;
2467                         ret++;
2468                         if (ret == bits_nr)
2469                                 break;
2470                         next = next_cache_extent(next);
2471                         if (!next)
2472                                 break;
2473                 }
2474         }
2475         return ret;
2476 }
2477
2478 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2479 static int process_extent_ref_v0(struct cache_tree *extent_cache,
2480                                  struct extent_buffer *leaf, int slot)
2481 {
2482         struct btrfs_extent_ref_v0 *ref0;
2483         struct btrfs_key key;
2484
2485         btrfs_item_key_to_cpu(leaf, &key, slot);
2486         ref0 = btrfs_item_ptr(leaf, slot, struct btrfs_extent_ref_v0);
2487         if (btrfs_ref_objectid_v0(leaf, ref0) < BTRFS_FIRST_FREE_OBJECTID) {
2488                 add_tree_backref(extent_cache, key.objectid, key.offset, 0, 0);
2489         } else {
2490                 add_data_backref(extent_cache, key.objectid, key.offset, 0,
2491                                  0, 0, btrfs_ref_count_v0(leaf, ref0), 0, 0);
2492         }
2493         return 0;
2494 }
2495 #endif
2496
2497 static int process_extent_item(struct cache_tree *extent_cache,
2498                                struct extent_buffer *eb, int slot)
2499 {
2500         struct btrfs_extent_item *ei;
2501         struct btrfs_extent_inline_ref *iref;
2502         struct btrfs_extent_data_ref *dref;
2503         struct btrfs_shared_data_ref *sref;
2504         struct btrfs_key key;
2505         unsigned long end;
2506         unsigned long ptr;
2507         int type;
2508         u32 item_size = btrfs_item_size_nr(eb, slot);
2509         u64 refs = 0;
2510         u64 offset;
2511
2512         btrfs_item_key_to_cpu(eb, &key, slot);
2513
2514         if (item_size < sizeof(*ei)) {
2515 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2516                 struct btrfs_extent_item_v0 *ei0;
2517                 BUG_ON(item_size != sizeof(*ei0));
2518                 ei0 = btrfs_item_ptr(eb, slot, struct btrfs_extent_item_v0);
2519                 refs = btrfs_extent_refs_v0(eb, ei0);
2520 #else
2521                 BUG();
2522 #endif
2523                 return add_extent_rec(extent_cache, NULL, key.objectid,
2524                                       key.offset, refs, 0, 0, 0, key.offset);
2525         }
2526
2527         ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
2528         refs = btrfs_extent_refs(eb, ei);
2529
2530         add_extent_rec(extent_cache, NULL, key.objectid, key.offset,
2531                        refs, 0, 0, 0, key.offset);
2532
2533         ptr = (unsigned long)(ei + 1);
2534         if (btrfs_extent_flags(eb, ei) & BTRFS_EXTENT_FLAG_TREE_BLOCK)
2535                 ptr += sizeof(struct btrfs_tree_block_info);
2536
2537         end = (unsigned long)ei + item_size;
2538         while (ptr < end) {
2539                 iref = (struct btrfs_extent_inline_ref *)ptr;
2540                 type = btrfs_extent_inline_ref_type(eb, iref);
2541                 offset = btrfs_extent_inline_ref_offset(eb, iref);
2542                 switch (type) {
2543                 case BTRFS_TREE_BLOCK_REF_KEY:
2544                         add_tree_backref(extent_cache, key.objectid,
2545                                          0, offset, 0);
2546                         break;
2547                 case BTRFS_SHARED_BLOCK_REF_KEY:
2548                         add_tree_backref(extent_cache, key.objectid,
2549                                          offset, 0, 0);
2550                         break;
2551                 case BTRFS_EXTENT_DATA_REF_KEY:
2552                         dref = (struct btrfs_extent_data_ref *)(&iref->offset);
2553                         add_data_backref(extent_cache, key.objectid, 0,
2554                                         btrfs_extent_data_ref_root(eb, dref),
2555                                         btrfs_extent_data_ref_objectid(eb,
2556                                                                        dref),
2557                                         btrfs_extent_data_ref_offset(eb, dref),
2558                                         btrfs_extent_data_ref_count(eb, dref),
2559                                         0, key.offset);
2560                         break;
2561                 case BTRFS_SHARED_DATA_REF_KEY:
2562                         sref = (struct btrfs_shared_data_ref *)(iref + 1);
2563                         add_data_backref(extent_cache, key.objectid, offset,
2564                                         0, 0, 0,
2565                                         btrfs_shared_data_ref_count(eb, sref),
2566                                         0, key.offset);
2567                         break;
2568                 default:
2569                         fprintf(stderr, "corrupt extent record: key %Lu %u %Lu\n",
2570                                 key.objectid, key.type, key.offset);
2571                         goto out;
2572                 }
2573                 ptr += btrfs_extent_inline_ref_size(type);
2574         }
2575         WARN_ON(ptr > end);
2576 out:
2577         return 0;
2578 }
2579
2580 static int run_next_block(struct btrfs_root *root,
2581                           struct block_info *bits,
2582                           int bits_nr,
2583                           u64 *last,
2584                           struct cache_tree *pending,
2585                           struct cache_tree *seen,
2586                           struct cache_tree *reada,
2587                           struct cache_tree *nodes,
2588                           struct cache_tree *extent_cache)
2589 {
2590         struct extent_buffer *buf;
2591         u64 bytenr;
2592         u32 size;
2593         u64 parent;
2594         u64 owner;
2595         u64 flags;
2596         int ret;
2597         int i;
2598         int nritems;
2599         struct btrfs_key key;
2600         struct cache_extent *cache;
2601         int reada_bits;
2602
2603         ret = pick_next_pending(pending, reada, nodes, *last, bits,
2604                                 bits_nr, &reada_bits);
2605         if (ret == 0) {
2606                 return 1;
2607         }
2608         if (!reada_bits) {
2609                 for(i = 0; i < ret; i++) {
2610                         insert_cache_extent(reada, bits[i].start,
2611                                             bits[i].size);
2612
2613                         /* fixme, get the parent transid */
2614                         readahead_tree_block(root, bits[i].start,
2615                                              bits[i].size, 0);
2616                 }
2617         }
2618         *last = bits[0].start;
2619         bytenr = bits[0].start;
2620         size = bits[0].size;
2621
2622         cache = find_cache_extent(pending, bytenr, size);
2623         if (cache) {
2624                 remove_cache_extent(pending, cache);
2625                 free(cache);
2626         }
2627         cache = find_cache_extent(reada, bytenr, size);
2628         if (cache) {
2629                 remove_cache_extent(reada, cache);
2630                 free(cache);
2631         }
2632         cache = find_cache_extent(nodes, bytenr, size);
2633         if (cache) {
2634                 remove_cache_extent(nodes, cache);
2635                 free(cache);
2636         }
2637
2638         /* fixme, get the real parent transid */
2639         buf = read_tree_block(root, bytenr, size, 0);
2640         if (!extent_buffer_uptodate(buf)) {
2641                 record_bad_block_io(root->fs_info,
2642                                     extent_cache, bytenr, size);
2643                 free_extent_buffer(buf);
2644                 goto out;
2645         }
2646
2647         nritems = btrfs_header_nritems(buf);
2648
2649         ret = btrfs_lookup_extent_info(NULL, root, bytenr, size, NULL, &flags);
2650         if (ret < 0)
2651                 flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
2652
2653         if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
2654                 parent = bytenr;
2655                 owner = 0;
2656         } else {
2657                 parent = 0;
2658                 owner = btrfs_header_owner(buf);
2659         }
2660
2661         ret = check_block(root, extent_cache, buf, flags);
2662         if (ret)
2663                 goto out;
2664
2665         if (btrfs_is_leaf(buf)) {
2666                 btree_space_waste += btrfs_leaf_free_space(root, buf);
2667                 for (i = 0; i < nritems; i++) {
2668                         struct btrfs_file_extent_item *fi;
2669                         btrfs_item_key_to_cpu(buf, &key, i);
2670                         if (key.type == BTRFS_EXTENT_ITEM_KEY) {
2671                                 process_extent_item(extent_cache, buf, i);
2672                                 continue;
2673                         }
2674                         if (key.type == BTRFS_EXTENT_CSUM_KEY) {
2675                                 total_csum_bytes +=
2676                                         btrfs_item_size_nr(buf, i);
2677                                 continue;
2678                         }
2679                         if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
2680                                 continue;
2681                         }
2682                         if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
2683 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2684                                 process_extent_ref_v0(extent_cache, buf, i);
2685 #else
2686                                 BUG();
2687 #endif
2688                                 continue;
2689                         }
2690
2691                         if (key.type == BTRFS_TREE_BLOCK_REF_KEY) {
2692                                 add_tree_backref(extent_cache, key.objectid, 0,
2693                                                  key.offset, 0);
2694                                 continue;
2695                         }
2696                         if (key.type == BTRFS_SHARED_BLOCK_REF_KEY) {
2697                                 add_tree_backref(extent_cache, key.objectid,
2698                                                  key.offset, 0, 0);
2699                                 continue;
2700                         }
2701                         if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
2702                                 struct btrfs_extent_data_ref *ref;
2703                                 ref = btrfs_item_ptr(buf, i,
2704                                                 struct btrfs_extent_data_ref);
2705                                 add_data_backref(extent_cache,
2706                                         key.objectid, 0,
2707                                         btrfs_extent_data_ref_root(buf, ref),
2708                                         btrfs_extent_data_ref_objectid(buf,
2709                                                                        ref),
2710                                         btrfs_extent_data_ref_offset(buf, ref),
2711                                         btrfs_extent_data_ref_count(buf, ref),
2712                                         0, root->sectorsize);
2713                                 continue;
2714                         }
2715                         if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
2716                                 struct btrfs_shared_data_ref *ref;
2717                                 ref = btrfs_item_ptr(buf, i,
2718                                                 struct btrfs_shared_data_ref);
2719                                 add_data_backref(extent_cache,
2720                                         key.objectid, key.offset, 0, 0, 0,
2721                                         btrfs_shared_data_ref_count(buf, ref),
2722                                         0, root->sectorsize);
2723                                 continue;
2724                         }
2725                         if (key.type != BTRFS_EXTENT_DATA_KEY)
2726                                 continue;
2727                         fi = btrfs_item_ptr(buf, i,
2728                                             struct btrfs_file_extent_item);
2729                         if (btrfs_file_extent_type(buf, fi) ==
2730                             BTRFS_FILE_EXTENT_INLINE)
2731                                 continue;
2732                         if (btrfs_file_extent_disk_bytenr(buf, fi) == 0)
2733                                 continue;
2734
2735                         data_bytes_allocated +=
2736                                 btrfs_file_extent_disk_num_bytes(buf, fi);
2737                         if (data_bytes_allocated < root->sectorsize) {
2738                                 abort();
2739                         }
2740                         data_bytes_referenced +=
2741                                 btrfs_file_extent_num_bytes(buf, fi);
2742                         ret = add_extent_rec(extent_cache, NULL,
2743                                    btrfs_file_extent_disk_bytenr(buf, fi),
2744                                    btrfs_file_extent_disk_num_bytes(buf, fi),
2745                                    0, 0, 1, 1,
2746                                    btrfs_file_extent_disk_num_bytes(buf, fi));
2747                         add_data_backref(extent_cache,
2748                                 btrfs_file_extent_disk_bytenr(buf, fi),
2749                                 parent, owner, key.objectid, key.offset -
2750                                 btrfs_file_extent_offset(buf, fi), 1, 1,
2751                                 btrfs_file_extent_disk_num_bytes(buf, fi));
2752                         BUG_ON(ret);
2753                 }
2754         } else {
2755                 int level;
2756                 struct btrfs_key first_key;
2757
2758                 first_key.objectid = 0;
2759
2760                 if (nritems > 0)
2761                         btrfs_item_key_to_cpu(buf, &first_key, 0);
2762                 level = btrfs_header_level(buf);
2763                 for (i = 0; i < nritems; i++) {
2764                         u64 ptr = btrfs_node_blockptr(buf, i);
2765                         u32 size = btrfs_level_size(root, level - 1);
2766                         btrfs_node_key_to_cpu(buf, &key, i);
2767                         ret = add_extent_rec(extent_cache, &key,
2768                                              ptr, size, 0, 0, 1, 0, size);
2769                         BUG_ON(ret);
2770
2771                         add_tree_backref(extent_cache, ptr, parent, owner, 1);
2772
2773                         if (level > 1) {
2774                                 add_pending(nodes, seen, ptr, size);
2775                         } else {
2776                                 add_pending(pending, seen, ptr, size);
2777                         }
2778                 }
2779                 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) -
2780                                       nritems) * sizeof(struct btrfs_key_ptr);
2781         }
2782         total_btree_bytes += buf->len;
2783         if (fs_root_objectid(btrfs_header_owner(buf)))
2784                 total_fs_tree_bytes += buf->len;
2785         if (!found_old_backref &&
2786             btrfs_header_owner(buf) == BTRFS_TREE_RELOC_OBJECTID &&
2787             btrfs_header_backref_rev(buf) == BTRFS_MIXED_BACKREF_REV &&
2788             !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))
2789                 found_old_backref = 1;
2790 out:
2791         free_extent_buffer(buf);
2792         return 0;
2793 }
2794
2795 static int add_root_to_pending(struct extent_buffer *buf,
2796                                struct block_info *bits,
2797                                int bits_nr,
2798                                struct cache_tree *extent_cache,
2799                                struct cache_tree *pending,
2800                                struct cache_tree *seen,
2801                                struct cache_tree *reada,
2802                                struct cache_tree *nodes,
2803                                struct btrfs_key *root_key)
2804 {
2805         if (btrfs_header_level(buf) > 0)
2806                 add_pending(nodes, seen, buf->start, buf->len);
2807         else
2808                 add_pending(pending, seen, buf->start, buf->len);
2809         add_extent_rec(extent_cache, NULL, buf->start, buf->len,
2810                        0, 1, 1, 0, buf->len);
2811
2812         if (root_key->objectid == BTRFS_TREE_RELOC_OBJECTID ||
2813             btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
2814                 add_tree_backref(extent_cache, buf->start, buf->start,
2815                                  0, 1);
2816         else
2817                 add_tree_backref(extent_cache, buf->start, 0,
2818                                  root_key->objectid, 1);
2819         return 0;
2820 }
2821
2822 /* as we fix the tree, we might be deleting blocks that
2823  * we're tracking for repair.  This hook makes sure we
2824  * remove any backrefs for blocks as we are fixing them.
2825  */
2826 static int free_extent_hook(struct btrfs_trans_handle *trans,
2827                             struct btrfs_root *root,
2828                             u64 bytenr, u64 num_bytes, u64 parent,
2829                             u64 root_objectid, u64 owner, u64 offset,
2830                             int refs_to_drop)
2831 {
2832         struct extent_record *rec;
2833         struct cache_extent *cache;
2834         int is_data;
2835         struct cache_tree *extent_cache = root->fs_info->fsck_extent_cache;
2836
2837         is_data = owner >= BTRFS_FIRST_FREE_OBJECTID;
2838         cache = find_cache_extent(extent_cache, bytenr, num_bytes);
2839         if (!cache)
2840                 return 0;
2841
2842         rec = container_of(cache, struct extent_record, cache);
2843         if (is_data) {
2844                 struct data_backref *back;
2845                 back = find_data_backref(rec, parent, root_objectid, owner,
2846                                          offset);
2847                 if (!back)
2848                         goto out;
2849                 if (back->node.found_ref) {
2850                         back->found_ref -= refs_to_drop;
2851                         if (rec->refs)
2852                                 rec->refs -= refs_to_drop;
2853                 }
2854                 if (back->node.found_extent_tree) {
2855                         back->num_refs -= refs_to_drop;
2856                         if (rec->extent_item_refs)
2857                                 rec->extent_item_refs -= refs_to_drop;
2858                 }
2859                 if (back->found_ref == 0)
2860                         back->node.found_ref = 0;
2861                 if (back->num_refs == 0)
2862                         back->node.found_extent_tree = 0;
2863
2864                 if (!back->node.found_extent_tree && back->node.found_ref) {
2865                         list_del(&back->node.list);
2866                         free(back);
2867                 }
2868         } else {
2869                 struct tree_backref *back;
2870                 back = find_tree_backref(rec, parent, root_objectid);
2871                 if (!back)
2872                         goto out;
2873                 if (back->node.found_ref) {
2874                         if (rec->refs)
2875                                 rec->refs--;
2876                         back->node.found_ref = 0;
2877                 }
2878                 if (back->node.found_extent_tree) {
2879                         if (rec->extent_item_refs)
2880                                 rec->extent_item_refs--;
2881                         back->node.found_extent_tree = 0;
2882                 }
2883                 if (!back->node.found_extent_tree && back->node.found_ref) {
2884                         list_del(&back->node.list);
2885                         free(back);
2886                 }
2887         }
2888         maybe_free_extent_rec(extent_cache, rec);
2889 out:
2890         return 0;
2891 }
2892
2893 static int delete_extent_records(struct btrfs_trans_handle *trans,
2894                                  struct btrfs_root *root,
2895                                  struct btrfs_path *path,
2896                                  u64 bytenr, u64 new_len)
2897 {
2898         struct btrfs_key key;
2899         struct btrfs_key found_key;
2900         struct extent_buffer *leaf;
2901         int ret;
2902         int slot;
2903
2904
2905         key.objectid = bytenr;
2906         key.type = (u8)-1;
2907         key.offset = (u64)-1;
2908
2909         while(1) {
2910                 ret = btrfs_search_slot(trans, root->fs_info->extent_root,
2911                                         &key, path, 0, 1);
2912                 if (ret < 0)
2913                         break;
2914
2915                 if (ret > 0) {
2916                         ret = 0;
2917                         if (path->slots[0] == 0)
2918                                 break;
2919                         path->slots[0]--;
2920                 }
2921                 ret = 0;
2922
2923                 leaf = path->nodes[0];
2924                 slot = path->slots[0];
2925
2926                 btrfs_item_key_to_cpu(leaf, &found_key, slot);
2927                 if (found_key.objectid != bytenr)
2928                         break;
2929
2930                 if (found_key.type != BTRFS_EXTENT_ITEM_KEY &&
2931                     found_key.type != BTRFS_TREE_BLOCK_REF_KEY &&
2932                     found_key.type != BTRFS_EXTENT_DATA_REF_KEY &&
2933                     found_key.type != BTRFS_EXTENT_REF_V0_KEY &&
2934                     found_key.type != BTRFS_SHARED_BLOCK_REF_KEY &&
2935                     found_key.type != BTRFS_SHARED_DATA_REF_KEY) {
2936                         btrfs_release_path(NULL, path);
2937                         if (found_key.type == 0) {
2938                                 if (found_key.offset == 0)
2939                                         break;
2940                                 key.offset = found_key.offset - 1;
2941                                 key.type = found_key.type;
2942                         }
2943                         key.type = found_key.type - 1;
2944                         key.offset = (u64)-1;
2945                         continue;
2946                 }
2947
2948                 fprintf(stderr, "repair deleting extent record: key %Lu %u %Lu\n",
2949                         found_key.objectid, found_key.type, found_key.offset);
2950
2951                 ret = btrfs_del_item(trans, root->fs_info->extent_root, path);
2952                 if (ret)
2953                         break;
2954                 btrfs_release_path(NULL, path);
2955
2956                 if (found_key.type == BTRFS_EXTENT_ITEM_KEY) {
2957                         ret = btrfs_update_block_group(trans, root, bytenr,
2958                                                        found_key.offset, 0, 0);
2959                         if (ret)
2960                                 break;
2961                 }
2962         }
2963
2964         btrfs_release_path(NULL, path);
2965         return ret;
2966 }
2967
2968 /*
2969  * for a single backref, this will allocate a new extent
2970  * and add the backref to it.
2971  */
2972 static int record_extent(struct btrfs_trans_handle *trans,
2973                          struct btrfs_fs_info *info,
2974                          struct btrfs_path *path,
2975                          struct extent_record *rec,
2976                          struct extent_backref *back,
2977                          int allocated, u64 flags)
2978 {
2979         int ret;
2980         struct btrfs_root *extent_root = info->extent_root;
2981         struct extent_buffer *leaf;
2982         struct btrfs_key ins_key;
2983         struct btrfs_extent_item *ei;
2984         struct tree_backref *tback;
2985         struct data_backref *dback;
2986         struct btrfs_tree_block_info *bi;
2987
2988         if (!back->is_data)
2989                 rec->max_size = max_t(u64, rec->max_size,
2990                                     info->extent_root->leafsize);
2991
2992         if (!allocated) {
2993                 u32 item_size = sizeof(*ei);
2994
2995                 if (!back->is_data)
2996                         item_size += sizeof(*bi);
2997
2998                 ins_key.objectid = rec->start;
2999                 ins_key.offset = rec->max_size;
3000                 ins_key.type = BTRFS_EXTENT_ITEM_KEY;
3001
3002                 ret = btrfs_insert_empty_item(trans, extent_root, path,
3003                                         &ins_key, item_size);
3004                 if (ret)
3005                         goto fail;
3006
3007                 leaf = path->nodes[0];
3008                 ei = btrfs_item_ptr(leaf, path->slots[0],
3009                                     struct btrfs_extent_item);
3010
3011                 btrfs_set_extent_refs(leaf, ei, 0);
3012                 btrfs_set_extent_generation(leaf, ei, rec->generation);
3013
3014                 if (back->is_data) {
3015                         btrfs_set_extent_flags(leaf, ei,
3016                                                BTRFS_EXTENT_FLAG_DATA);
3017                 } else {
3018                         struct btrfs_disk_key copy_key;;
3019
3020                         tback = (struct tree_backref *)back;
3021                         bi = (struct btrfs_tree_block_info *)(ei + 1);
3022                         memset_extent_buffer(leaf, 0, (unsigned long)bi,
3023                                              sizeof(*bi));
3024                         memset(&copy_key, 0, sizeof(copy_key));
3025
3026                         copy_key.objectid = le64_to_cpu(rec->info_objectid);
3027                         btrfs_set_tree_block_level(leaf, bi, rec->info_level);
3028                         btrfs_set_tree_block_key(leaf, bi, &copy_key);
3029
3030                         btrfs_set_extent_flags(leaf, ei,
3031                                                BTRFS_EXTENT_FLAG_TREE_BLOCK | flags);
3032                 }
3033
3034                 btrfs_mark_buffer_dirty(leaf);
3035                 ret = btrfs_update_block_group(trans, extent_root, rec->start,
3036                                                rec->max_size, 1, 0);
3037                 if (ret)
3038                         goto fail;
3039                 btrfs_release_path(NULL, path);
3040         }
3041
3042         if (back->is_data) {
3043                 u64 parent;
3044                 int i;
3045
3046                 dback = (struct data_backref *)back;
3047                 if (back->full_backref)
3048                         parent = dback->parent;
3049                 else
3050                         parent = 0;
3051
3052                 for (i = 0; i < dback->found_ref; i++) {
3053                         /* if parent != 0, we're doing a full backref
3054                          * passing BTRFS_FIRST_FREE_OBJECTID as the owner
3055                          * just makes the backref allocator create a data
3056                          * backref
3057                          */
3058                         ret = btrfs_inc_extent_ref(trans, info->extent_root,
3059                                                    rec->start, rec->max_size,
3060                                                    parent,
3061                                                    dback->root,
3062                                                    parent ?
3063                                                    BTRFS_FIRST_FREE_OBJECTID :
3064                                                    dback->owner,
3065                                                    dback->offset);
3066                         if (ret)
3067                                 break;
3068                 }
3069                 fprintf(stderr, "adding new data backref"
3070                                 " on %llu %s %llu owner %llu"
3071                                 " offset %llu found %d\n",
3072                                 (unsigned long long)rec->start,
3073                                 back->full_backref ?
3074                                 "parent" : "root",
3075                                 back->full_backref ?
3076                                 (unsigned long long)parent :
3077                                 (unsigned long long)dback->root,
3078                                 (unsigned long long)dback->owner,
3079                                 (unsigned long long)dback->offset,
3080                                 dback->found_ref);
3081         } else {
3082                 u64 parent;
3083
3084                 tback = (struct tree_backref *)back;
3085                 if (back->full_backref)
3086                         parent = tback->parent;
3087                 else
3088                         parent = 0;
3089
3090                 ret = btrfs_inc_extent_ref(trans, info->extent_root,
3091                                            rec->start, rec->max_size,
3092                                            parent, tback->root, 0, 0);
3093                 fprintf(stderr, "adding new tree backref on "
3094                         "start %llu len %llu parent %llu root %llu\n",
3095                         rec->start, rec->max_size, tback->parent, tback->root);
3096         }
3097         if (ret)
3098                 goto fail;
3099 fail:
3100         btrfs_release_path(NULL, path);
3101         return ret;
3102 }
3103
3104 /*
3105  * when an incorrect extent item is found, this will delete
3106  * all of the existing entries for it and recreate them
3107  * based on what the tree scan found.
3108  */
3109 static int fixup_extent_refs(struct btrfs_trans_handle *trans,
3110                              struct btrfs_fs_info *info,
3111                              struct extent_record *rec)
3112 {
3113         int ret;
3114         struct btrfs_path *path;
3115         struct list_head *cur = rec->backrefs.next;
3116         struct cache_extent *cache;
3117         struct extent_backref *back;
3118         int allocated = 0;
3119         u64 flags = 0;
3120
3121         /* remember our flags for recreating the extent */
3122         ret = btrfs_lookup_extent_info(NULL, info->extent_root, rec->start,
3123                                        rec->max_size, NULL, &flags);
3124         if (ret < 0)
3125                 flags = BTRFS_BLOCK_FLAG_FULL_BACKREF;
3126
3127         path = btrfs_alloc_path();
3128
3129         /* step one, delete all the existing records */
3130         ret = delete_extent_records(trans, info->extent_root, path,
3131                                     rec->start, rec->max_size);
3132
3133         if (ret < 0)
3134                 goto out;
3135
3136         /* was this block corrupt?  If so, don't add references to it */
3137         cache = find_cache_extent(info->corrupt_blocks, rec->start, rec->max_size);
3138         if (cache) {
3139                 ret = 0;
3140                 goto out;
3141         }
3142
3143         /* step two, recreate all the refs we did find */
3144         while(cur != &rec->backrefs) {
3145                 back = list_entry(cur, struct extent_backref, list);
3146                 cur = cur->next;
3147
3148                 /*
3149                  * if we didn't find any references, don't create a
3150                  * new extent record
3151                  */
3152                 if (!back->found_ref)
3153                         continue;
3154
3155                 ret = record_extent(trans, info, path, rec, back, allocated, flags);
3156                 allocated = 1;
3157
3158                 if (ret)
3159                         goto out;
3160         }
3161 out:
3162         btrfs_free_path(path);
3163         return ret;
3164 }
3165
3166 /* right now we only prune from the extent allocation tree */
3167 static int prune_one_block(struct btrfs_trans_handle *trans,
3168                            struct btrfs_fs_info *info,
3169                            struct btrfs_corrupt_block *corrupt)
3170 {
3171         int ret;
3172         struct btrfs_path path;
3173         struct extent_buffer *eb;
3174         u64 found;
3175         int slot;
3176         int nritems;
3177         int level = corrupt->level + 1;
3178
3179         btrfs_init_path(&path);
3180 again:
3181         /* we want to stop at the parent to our busted block */
3182         path.lowest_level = level;
3183
3184         ret = btrfs_search_slot(trans, info->extent_root,
3185                                 &corrupt->key, &path, -1, 1);
3186
3187         if (ret < 0)
3188                 goto out;
3189
3190         eb = path.nodes[level];
3191         if (!eb) {
3192                 ret = -ENOENT;
3193                 goto out;
3194         }
3195
3196         /*
3197          * hopefully the search gave us the block we want to prune,
3198          * lets try that first
3199          */
3200         slot = path.slots[level];
3201         found =  btrfs_node_blockptr(eb, slot);
3202         if (found == corrupt->cache.start)
3203                 goto del_ptr;
3204
3205         nritems = btrfs_header_nritems(eb);
3206
3207         /* the search failed, lets scan this node and hope we find it */
3208         for (slot = 0; slot < nritems; slot++) {
3209                 found =  btrfs_node_blockptr(eb, slot);
3210                 if (found == corrupt->cache.start)
3211                         goto del_ptr;
3212         }
3213         /*
3214          * we couldn't find the bad block.  TODO, search all the nodes for pointers
3215          * to this block
3216          */
3217         if (eb == info->extent_root->node) {
3218                 ret = -ENOENT;
3219                 goto out;
3220         } else {
3221                 level++;
3222                 btrfs_release_path(NULL, &path);
3223                 goto again;
3224         }
3225
3226 del_ptr:
3227         printk("deleting pointer to block %Lu\n", corrupt->cache.start);
3228         ret = btrfs_del_ptr(trans, info->extent_root, &path, level, slot);
3229
3230 out:
3231         btrfs_release_path(NULL, &path);
3232         return ret;
3233 }
3234
3235 static int prune_corrupt_blocks(struct btrfs_trans_handle *trans,
3236                                 struct btrfs_fs_info *info)
3237 {
3238         struct cache_extent *cache;
3239         struct btrfs_corrupt_block *corrupt;
3240
3241         cache = find_first_cache_extent(info->corrupt_blocks, 0);
3242         while (1) {
3243                 if (!cache)
3244                         break;
3245                 corrupt = container_of(cache, struct btrfs_corrupt_block, cache);
3246                 prune_one_block(trans, info, corrupt);
3247                 cache = next_cache_extent(cache);
3248         }
3249         return 0;
3250 }
3251
3252 static void free_corrupt_blocks(struct btrfs_fs_info *info)
3253 {
3254         struct cache_extent *cache;
3255         struct btrfs_corrupt_block *corrupt;
3256
3257         while (1) {
3258                 cache = find_first_cache_extent(info->corrupt_blocks, 0);
3259                 if (!cache)
3260                         break;
3261                 corrupt = container_of(cache, struct btrfs_corrupt_block, cache);
3262                 remove_cache_extent(info->corrupt_blocks, cache);
3263                 free(corrupt);
3264         }
3265 }
3266
3267 static int check_block_group(struct btrfs_trans_handle *trans,
3268                               struct btrfs_fs_info *info,
3269                               struct map_lookup *map,
3270                               int *reinit)
3271 {
3272         struct btrfs_key key;
3273         struct btrfs_path path;
3274         int ret;
3275
3276         key.objectid = map->ce.start;
3277         key.offset = map->ce.size;
3278         key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
3279
3280         btrfs_init_path(&path);
3281         ret = btrfs_search_slot(NULL, info->extent_root,
3282                                 &key, &path, 0, 0);
3283         btrfs_release_path(NULL, &path);
3284         if (ret <= 0)
3285                 goto out;
3286
3287         ret = btrfs_make_block_group(trans, info->extent_root, 0, map->type,
3288                                BTRFS_FIRST_CHUNK_TREE_OBJECTID,
3289                                key.objectid, key.offset);
3290         *reinit = 1;
3291 out:
3292         return ret;
3293 }
3294
3295 static int check_block_groups(struct btrfs_trans_handle *trans,
3296                               struct btrfs_fs_info *info, int *reinit)
3297 {
3298         struct cache_extent *ce;
3299         struct map_lookup *map;
3300         struct btrfs_mapping_tree *map_tree = &info->mapping_tree;
3301
3302         /* this isn't quite working */
3303         return 0;
3304
3305         ce = find_first_cache_extent(&map_tree->cache_tree, 0);
3306         while (1) {
3307                 if (!ce)
3308                         break;
3309                 map = container_of(ce, struct map_lookup, ce);
3310                 check_block_group(trans, info, map, reinit);
3311                 ce = next_cache_extent(ce);
3312         }
3313         return 0;
3314 }
3315
3316 static int check_extent_refs(struct btrfs_trans_handle *trans,
3317                              struct btrfs_root *root,
3318                              struct cache_tree *extent_cache, int repair)
3319 {
3320         struct extent_record *rec;
3321         struct cache_extent *cache;
3322         int err = 0;
3323         int ret = 0;
3324         int fixed = 0;
3325         int reinit = 0;
3326
3327         if (repair) {
3328                 /*
3329                  * if we're doing a repair, we have to make sure
3330                  * we don't allocate from the problem extents.
3331                  * In the worst case, this will be all the
3332                  * extents in the FS
3333                  */
3334                 cache = find_first_cache_extent(extent_cache, 0);
3335                 while(cache) {
3336                         rec = container_of(cache, struct extent_record, cache);
3337                         btrfs_pin_extent(root->fs_info,
3338                                          rec->start, rec->max_size);
3339                         cache = next_cache_extent(cache);
3340                 }
3341
3342                 /* pin down all the corrupted blocks too */
3343                 cache = find_first_cache_extent(root->fs_info->corrupt_blocks, 0);
3344                 while(cache) {
3345                         rec = container_of(cache, struct extent_record, cache);
3346                         btrfs_pin_extent(root->fs_info,
3347                                          rec->start, rec->max_size);
3348                         cache = next_cache_extent(cache);
3349                 }
3350                 prune_corrupt_blocks(trans, root->fs_info);
3351                 check_block_groups(trans, root->fs_info, &reinit);
3352                 if (reinit)
3353                         btrfs_read_block_groups(root->fs_info->extent_root);
3354         }
3355         while(1) {
3356                 fixed = 0;
3357                 cache = find_first_cache_extent(extent_cache, 0);
3358                 if (!cache)
3359                         break;
3360                 rec = container_of(cache, struct extent_record, cache);
3361                 if (rec->refs != rec->extent_item_refs) {
3362                         fprintf(stderr, "ref mismatch on [%llu %llu] ",
3363                                 (unsigned long long)rec->start,
3364                                 (unsigned long long)rec->nr);
3365                         fprintf(stderr, "extent item %llu, found %llu\n",
3366                                 (unsigned long long)rec->extent_item_refs,
3367                                 (unsigned long long)rec->refs);
3368                         if (!fixed && repair) {
3369                                 ret = fixup_extent_refs(trans, root->fs_info, rec);
3370                                 if (ret)
3371                                         goto repair_abort;
3372                                 fixed = 1;
3373                         }
3374                         err = 1;
3375
3376                 }
3377                 if (all_backpointers_checked(rec, 1)) {
3378                         fprintf(stderr, "backpointer mismatch on [%llu %llu]\n",
3379                                 (unsigned long long)rec->start,
3380                                 (unsigned long long)rec->nr);
3381
3382                         if (!fixed && repair) {
3383                                 ret = fixup_extent_refs(trans, root->fs_info, rec);
3384                                 if (ret)
3385                                         goto repair_abort;
3386                                 fixed = 1;
3387                         }
3388
3389                         err = 1;
3390                 }
3391                 if (!rec->owner_ref_checked) {
3392                         fprintf(stderr, "owner ref check failed [%llu %llu]\n",
3393                                 (unsigned long long)rec->start,
3394                                 (unsigned long long)rec->nr);
3395                         if (!fixed && repair) {
3396                                 ret = fixup_extent_refs(trans, root->fs_info, rec);
3397                                 if (ret)
3398                                         goto repair_abort;
3399                                 fixed = 1;
3400                         }
3401                         err = 1;
3402                 }
3403
3404                 remove_cache_extent(extent_cache, cache);
3405                 free_all_extent_backrefs(rec);
3406                 free(rec);
3407         }
3408 repair_abort:
3409         if (repair) {
3410                 if (ret) {
3411                         fprintf(stderr, "failed to repair damaged filesystem, aborting\n");
3412                         exit(1);
3413                 } else {
3414                         btrfs_fix_block_accounting(trans, root);
3415                 }
3416                 if (err)
3417                         fprintf(stderr, "repaired damaged extent references\n");
3418                 return ret;
3419         }
3420         return err;
3421 }
3422
3423 static int check_extents(struct btrfs_trans_handle *trans,
3424                          struct btrfs_root *root, int repair)
3425 {
3426         struct cache_tree extent_cache;
3427         struct cache_tree seen;
3428         struct cache_tree pending;
3429         struct cache_tree reada;
3430         struct cache_tree nodes;
3431         struct cache_tree corrupt_blocks;
3432         struct btrfs_path path;
3433         struct btrfs_key key;
3434         struct btrfs_key found_key;
3435         int ret;
3436         u64 last = 0;
3437         struct block_info *bits;
3438         int bits_nr;
3439         struct extent_buffer *leaf;
3440         int slot;
3441         struct btrfs_root_item ri;
3442
3443         cache_tree_init(&extent_cache);
3444         cache_tree_init(&seen);
3445         cache_tree_init(&pending);
3446         cache_tree_init(&nodes);
3447         cache_tree_init(&reada);
3448         cache_tree_init(&corrupt_blocks);
3449
3450         if (repair) {
3451                 root->fs_info->fsck_extent_cache = &extent_cache;
3452                 root->fs_info->free_extent_hook = free_extent_hook;
3453                 root->fs_info->corrupt_blocks = &corrupt_blocks;
3454         }
3455
3456         bits_nr = 1024;
3457         bits = malloc(bits_nr * sizeof(struct block_info));
3458         if (!bits) {
3459                 perror("malloc");
3460                 exit(1);
3461         }
3462
3463         add_root_to_pending(root->fs_info->tree_root->node, bits, bits_nr,
3464                             &extent_cache, &pending, &seen, &reada, &nodes,
3465                             &root->fs_info->tree_root->root_key);
3466
3467         add_root_to_pending(root->fs_info->chunk_root->node, bits, bits_nr,
3468                             &extent_cache, &pending, &seen, &reada, &nodes,
3469                             &root->fs_info->chunk_root->root_key);
3470
3471         btrfs_init_path(&path);
3472         key.offset = 0;
3473         key.objectid = 0;
3474         btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
3475         ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
3476                                         &key, &path, 0, 0);
3477         BUG_ON(ret < 0);
3478         while(1) {
3479                 leaf = path.nodes[0];
3480                 slot = path.slots[0];
3481                 if (slot >= btrfs_header_nritems(path.nodes[0])) {
3482                         ret = btrfs_next_leaf(root, &path);
3483                         if (ret != 0)
3484                                 break;
3485                         leaf = path.nodes[0];
3486                         slot = path.slots[0];
3487                 }
3488                 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
3489                 if (btrfs_key_type(&found_key) == BTRFS_ROOT_ITEM_KEY) {
3490                         unsigned long offset;
3491                         struct extent_buffer *buf;
3492
3493                         offset = btrfs_item_ptr_offset(leaf, path.slots[0]);
3494                         read_extent_buffer(leaf, &ri, offset, sizeof(ri));
3495                         buf = read_tree_block(root->fs_info->tree_root,
3496                                               btrfs_root_bytenr(&ri),
3497                                               btrfs_level_size(root,
3498                                                btrfs_root_level(&ri)), 0);
3499                         add_root_to_pending(buf, bits, bits_nr, &extent_cache,
3500                                             &pending, &seen, &reada, &nodes,
3501                                             &found_key);
3502                         free_extent_buffer(buf);
3503                 }
3504                 path.slots[0]++;
3505         }
3506         btrfs_release_path(root, &path);
3507         while(1) {
3508                 ret = run_next_block(root, bits, bits_nr, &last, &pending,
3509                                      &seen, &reada, &nodes, &extent_cache);
3510                 if (ret != 0)
3511                         break;
3512         }
3513         ret = check_extent_refs(trans, root, &extent_cache, repair);
3514
3515         if (repair) {
3516                 free_corrupt_blocks(root->fs_info);
3517                 root->fs_info->fsck_extent_cache = NULL;
3518                 root->fs_info->free_extent_hook = NULL;
3519                 root->fs_info->corrupt_blocks = NULL;
3520         }
3521
3522         return ret;
3523 }
3524
3525 static void print_usage(void)
3526 {
3527         fprintf(stderr, "usage: btrfsck dev\n");
3528         fprintf(stderr, "%s\n", BTRFS_BUILD_VERSION);
3529         exit(1);
3530 }
3531
3532 static struct option long_options[] = {
3533         { "super", 1, NULL, 's' },
3534         { "repair", 0, NULL, 0 },
3535         { "init-csum-tree", 0, NULL, 0 },
3536         { "init-extent-tree", 0, NULL, 0 },
3537         { 0, 0, 0, 0}
3538 };
3539
3540 int main(int ac, char **av)
3541 {
3542         struct cache_tree root_cache;
3543         struct btrfs_root *root;
3544         struct btrfs_fs_info *info;
3545         struct btrfs_trans_handle *trans = NULL;
3546         u64 bytenr = 0;
3547         char uuidbuf[37];
3548         int ret;
3549         int num;
3550         int repair = 0;
3551         int option_index = 0;
3552         int init_csum_tree = 0;
3553         int rw = 0;
3554
3555         while(1) {
3556                 int c;
3557                 c = getopt_long(ac, av, "as:", long_options,
3558                                 &option_index);
3559                 if (c < 0)
3560                         break;
3561                 switch(c) {
3562                         case 'a': /* ignored */ break;
3563                         case 's':
3564                                 num = atol(optarg);
3565                                 bytenr = btrfs_sb_offset(num);
3566                                 printf("using SB copy %d, bytenr %llu\n", num,
3567                                        (unsigned long long)bytenr);
3568                                 break;
3569                         case '?':
3570                                 print_usage();
3571                 }
3572                 if (option_index == 1) {
3573                         printf("enabling repair mode\n");
3574                         repair = 1;
3575                         rw = 1;
3576                 } else if (option_index == 2) {
3577                         printf("Creating a new CRC tree\n");
3578                         init_csum_tree = 1;
3579                         rw = 1;
3580                 }
3581
3582         }
3583         ac = ac - optind;
3584
3585         if (ac != 1)
3586                 print_usage();
3587
3588         radix_tree_init();
3589         cache_tree_init(&root_cache);
3590
3591         if((ret = check_mounted(av[optind])) < 0) {
3592                 fprintf(stderr, "Could not check mount status: %s\n", strerror(-ret));
3593                 return ret;
3594         } else if(ret) {
3595                 fprintf(stderr, "%s is currently mounted. Aborting.\n", av[optind]);
3596                 return -EBUSY;
3597         }
3598
3599         info = open_ctree_fs_info(av[optind], bytenr, rw, 1);
3600         uuid_unparse(info->super_copy.fsid, uuidbuf);
3601         printf("Checking filesystem on %s\nUUID: %s\n", av[optind], uuidbuf);
3602
3603         if (info == NULL)
3604                 return 1;
3605
3606         if (!extent_buffer_uptodate(info->tree_root->node) ||
3607             !extent_buffer_uptodate(info->dev_root->node) ||
3608             !extent_buffer_uptodate(info->extent_root->node) ||
3609             !extent_buffer_uptodate(info->chunk_root->node)) {
3610                 fprintf(stderr, "Critical roots corrupted, unable to fsck the FS\n");
3611                 return -EIO;
3612         }
3613
3614         root = info->fs_root;
3615
3616         fprintf(stderr, "checking extents\n");
3617         if (rw)
3618                 trans = btrfs_start_transaction(root, 1);
3619
3620         if (init_csum_tree) {
3621                 fprintf(stderr, "Reinit crc root\n");
3622                 ret = btrfs_fsck_reinit_root(trans, info->csum_root);
3623                 if (ret) {
3624                         fprintf(stderr, "crc root initialization failed\n");
3625                         return -EIO;
3626                 }
3627                 goto out;
3628         }
3629         ret = check_extents(trans, root, repair);
3630         if (ret)
3631                 fprintf(stderr, "Errors found in extent allocation tree\n");
3632
3633         fprintf(stderr, "checking fs roots\n");
3634         ret = check_fs_roots(root, &root_cache);
3635         if (ret)
3636                 goto out;
3637
3638         fprintf(stderr, "checking root refs\n");
3639         ret = check_root_refs(root, &root_cache);
3640 out:
3641         free_root_recs(&root_cache);
3642         if (rw) {
3643                 ret = btrfs_commit_transaction(trans, root);
3644                 if (ret)
3645                         exit(1);
3646         }
3647         close_ctree(root);
3648
3649         if (found_old_backref) { /*
3650                  * there was a disk format change when mixed
3651                  * backref was in testing tree. The old format
3652                  * existed about one week.
3653                  */
3654                 printf("\n * Found old mixed backref format. "
3655                        "The old format is not supported! *"
3656                        "\n * Please mount the FS in readonly mode, "
3657                        "backup data and re-format the FS. *\n\n");
3658                 ret = 1;
3659         }
3660         printf("found %llu bytes used err is %d\n",
3661                (unsigned long long)bytes_used, ret);
3662         printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes);
3663         printf("total tree bytes: %llu\n",
3664                (unsigned long long)total_btree_bytes);
3665         printf("total fs tree bytes: %llu\n",
3666                (unsigned long long)total_fs_tree_bytes);
3667         printf("btree space waste bytes: %llu\n",
3668                (unsigned long long)btree_space_waste);
3669         printf("file data blocks allocated: %llu\n referenced %llu\n",
3670                 (unsigned long long)data_bytes_allocated,
3671                 (unsigned long long)data_bytes_referenced);
3672         printf("%s\n", BTRFS_BUILD_VERSION);
3673         return ret;
3674 }