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/stat.h>
  26 #include "kerncompat.h"
  27 #include "ctree.h"
  28 #include "disk-io.h"
  29 #include "print-tree.h"
  30 #include "transaction.h"
  31 #include "list.h"
  32 #include "version.h"
  33 #include "utils.h"
  34
  35 static u64 bytes_used = 0;
  36 static u64 total_csum_bytes = 0;
  37 static u64 total_btree_bytes = 0;
  38 static u64 total_fs_tree_bytes = 0;
  39 static u64 btree_space_waste = 0;
  40 static u64 data_bytes_allocated = 0;
  41 static u64 data_bytes_referenced = 0;
  42 static int found_old_backref = 0;
  43
  44 struct extent_backref {
  45         struct list_head list;
  46         unsigned int is_data:1;
  47         unsigned int found_extent_tree:1;
  48         unsigned int full_backref:1;
  49         unsigned int found_ref:1;
  50 };
  51
  52 struct data_backref {
  53         struct extent_backref node;
  54         union {
  55                 u64 parent;
  56                 u64 root;
  57         };
  58         u64 owner;
  59         u64 offset;
  60         u32 num_refs;
  61         u32 found_ref;
  62 };
  63
  64 struct tree_backref {
  65         struct extent_backref node;
  66         union {
  67                 u64 parent;
  68                 u64 root;
  69         };
  70 };
  71
  72 struct extent_record {
  73         struct list_head backrefs;
  74         struct cache_extent cache;
  75         struct btrfs_disk_key parent_key;
  76         u64 start;
  77         u64 nr;
  78         u64 refs;
  79         u64 extent_item_refs;
  80         unsigned int content_checked:1;
  81         unsigned int owner_ref_checked:1;
  82         unsigned int is_root:1;
  83 };
  84
  85 struct inode_backref {
  86         struct list_head list;
  87         unsigned int found_dir_item:1;
  88         unsigned int found_dir_index:1;
  89         unsigned int found_inode_ref:1;
  90         unsigned int filetype:8;
  91         int errors;
  92         u64 dir;
  93         u64 index;
  94         u16 namelen;
  95         char name[0];
  96 };
  97
  98 #define REF_ERR_NO_DIR_ITEM             (1 << 0)
  99 #define REF_ERR_NO_DIR_INDEX            (1 << 1)
 100 #define REF_ERR_NO_INODE_REF            (1 << 2)
 101 #define REF_ERR_DUP_DIR_ITEM            (1 << 3)
 102 #define REF_ERR_DUP_DIR_INDEX           (1 << 4)
 103 #define REF_ERR_DUP_INODE_REF           (1 << 5)
 104 #define REF_ERR_INDEX_UNMATCH           (1 << 6)
 105 #define REF_ERR_FILETYPE_UNMATCH        (1 << 7)
 106 #define REF_ERR_NAME_TOO_LONG           (1 << 8) // 100
 107 #define REF_ERR_NO_ROOT_REF             (1 << 9)
 108 #define REF_ERR_NO_ROOT_BACKREF         (1 << 10)
 109 #define REF_ERR_DUP_ROOT_REF            (1 << 11)
 110 #define REF_ERR_DUP_ROOT_BACKREF        (1 << 12)
 111
 112 struct inode_record {
 113         struct list_head backrefs;
 114         unsigned int checked:1;
 115         unsigned int merging:1;
 116         unsigned int found_inode_item:1;
 117         unsigned int found_dir_item:1;
 118         unsigned int found_file_extent:1;
 119         unsigned int found_csum_item:1;
 120         unsigned int some_csum_missing:1;
 121         unsigned int nodatasum:1;
 122         int errors;
 123
 124         u64 ino;
 125         u32 nlink;
 126         u32 imode;
 127         u64 isize;
 128         u64 nbytes;
 129
 130         u32 found_link;
 131         u64 found_size;
 132         u64 extent_start;
 133         u64 extent_end;
 134         u64 first_extent_gap;
 135
 136         u32 refs;
 137 };
 138
 139 #define I_ERR_NO_INODE_ITEM             (1 << 0)
 140 #define I_ERR_NO_ORPHAN_ITEM            (1 << 1)
 141 #define I_ERR_DUP_INODE_ITEM            (1 << 2)
 142 #define I_ERR_DUP_DIR_INDEX             (1 << 3)
 143 #define I_ERR_ODD_DIR_ITEM              (1 << 4)
 144 #define I_ERR_ODD_FILE_EXTENT           (1 << 5)
 145 #define I_ERR_BAD_FILE_EXTENT           (1 << 6)
 146 #define I_ERR_FILE_EXTENT_OVERLAP       (1 << 7)
 147 #define I_ERR_FILE_EXTENT_DISCOUNT      (1 << 8) // 100
 148 #define I_ERR_DIR_ISIZE_WRONG           (1 << 9)
 149 #define I_ERR_FILE_NBYTES_WRONG         (1 << 10) // 400
 150 #define I_ERR_ODD_CSUM_ITEM             (1 << 11)
 151 #define I_ERR_SOME_CSUM_MISSING         (1 << 12)
 152 #define I_ERR_LINK_COUNT_WRONG          (1 << 13)
 153
 154 struct root_backref {
 155         struct list_head list;
 156         unsigned int found_dir_item:1;
 157         unsigned int found_dir_index:1;
 158         unsigned int found_back_ref:1;
 159         unsigned int found_forward_ref:1;
 160         unsigned int reachable:1;
 161         int errors;
 162         u64 ref_root;
 163         u64 dir;
 164         u64 index;
 165         u16 namelen;
 166         char name[0];
 167 };
 168
 169 struct root_record {
 170         struct list_head backrefs;
 171         struct cache_extent cache;
 172         unsigned int found_root_item:1;
 173         u64 objectid;
 174         u32 found_ref;
 175 };
 176
 177 struct ptr_node {
 178         struct cache_extent cache;
 179         void *data;
 180 };
 181
 182 struct shared_node {
 183         struct cache_extent cache;
 184         struct cache_tree root_cache;
 185         struct cache_tree inode_cache;
 186         struct inode_record *current;
 187         u32 refs;
 188 };
 189
 190 struct block_info {
 191         u64 start;
 192         u32 size;
 193 };
 194
 195 struct walk_control {
 196         struct cache_tree shared;
 197         struct shared_node *nodes[BTRFS_MAX_LEVEL];
 198         int active_node;
 199         int root_level;
 200 };
 201
 202 static u8 imode_to_type(u32 imode)
 203 {
 204 #define S_SHIFT 12
 205         static unsigned char btrfs_type_by_mode[S_IFMT >> S_SHIFT] = {
 206                 [S_IFREG >> S_SHIFT]    = BTRFS_FT_REG_FILE,
 207                 [S_IFDIR >> S_SHIFT]    = BTRFS_FT_DIR,
 208                 [S_IFCHR >> S_SHIFT]    = BTRFS_FT_CHRDEV,
 209                 [S_IFBLK >> S_SHIFT]    = BTRFS_FT_BLKDEV,
 210                 [S_IFIFO >> S_SHIFT]    = BTRFS_FT_FIFO,
 211                 [S_IFSOCK >> S_SHIFT]   = BTRFS_FT_SOCK,
 212                 [S_IFLNK >> S_SHIFT]    = BTRFS_FT_SYMLINK,
 213         };
 214
 215         return btrfs_type_by_mode[(imode & S_IFMT) >> S_SHIFT];
 216 #undef S_SHIFT
 217 }
 218
 219 static struct inode_record *clone_inode_rec(struct inode_record *orig_rec)
 220 {
 221         struct inode_record *rec;
 222         struct inode_backref *backref;
 223         struct inode_backref *orig;
 224         size_t size;
 225
 226         rec = malloc(sizeof(*rec));
 227         memcpy(rec, orig_rec, sizeof(*rec));
 228         rec->refs = 1;
 229         INIT_LIST_HEAD(&rec->backrefs);
 230
 231         list_for_each_entry(orig, &orig_rec->backrefs, list) {
 232                 size = sizeof(*orig) + orig->namelen + 1;
 233                 backref = malloc(size);
 234                 memcpy(backref, orig, size);
 235                 list_add_tail(&backref->list, &rec->backrefs);
 236         }
 237         return rec;
 238 }
 239
 240 static struct inode_record *get_inode_rec(struct cache_tree *inode_cache,
 241                                           u64 ino, int mod)
 242 {
 243         struct ptr_node *node;
 244         struct cache_extent *cache;
 245         struct inode_record *rec = NULL;
 246         int ret;
 247
 248         cache = find_cache_extent(inode_cache, ino, 1);
 249         if (cache) {
 250                 node = container_of(cache, struct ptr_node, cache);
 251                 rec = node->data;
 252                 if (mod && rec->refs > 1) {
 253                         node->data = clone_inode_rec(rec);
 254                         rec->refs--;
 255                         rec = node->data;
 256                 }
 257         } else if (mod) {
 258                 rec = calloc(1, sizeof(*rec));
 259                 rec->ino = ino;
 260                 rec->extent_start = (u64)-1;
 261                 rec->first_extent_gap = (u64)-1;
 262                 rec->refs = 1;
 263                 INIT_LIST_HEAD(&rec->backrefs);
 264
 265                 node = malloc(sizeof(*node));
 266                 node->cache.start = ino;
 267                 node->cache.size = 1;
 268                 node->data = rec;
 269
 270                 ret = insert_existing_cache_extent(inode_cache, &node->cache);
 271                 BUG_ON(ret);
 272         }
 273         return rec;
 274 }
 275
 276 static void free_inode_rec(struct inode_record *rec)
 277 {
 278         struct inode_backref *backref;
 279
 280         if (--rec->refs > 0)
 281                 return;
 282
 283         while (!list_empty(&rec->backrefs)) {
 284                 backref = list_entry(rec->backrefs.next,
 285                                      struct inode_backref, list);
 286                 list_del(&backref->list);
 287                 free(backref);
 288         }
 289         free(rec);
 290 }
 291
 292 static int can_free_inode_rec(struct inode_record *rec)
 293 {
 294         if (!rec->errors && rec->checked && rec->found_inode_item &&
 295             rec->nlink == rec->found_link && list_empty(&rec->backrefs))
 296                 return 1;
 297         return 0;
 298 }
 299
 300 static void maybe_free_inode_rec(struct cache_tree *inode_cache,
 301                                  struct inode_record *rec)
 302 {
 303         struct cache_extent *cache;
 304         struct inode_backref *tmp, *backref;
 305         struct ptr_node *node;
 306         unsigned char filetype;
 307
 308         if (!rec->found_inode_item)
 309                 return;
 310
 311         filetype = imode_to_type(rec->imode);
 312         list_for_each_entry_safe(backref, tmp, &rec->backrefs, list) {
 313                 if (backref->found_dir_item && backref->found_dir_index) {
 314                         if (backref->filetype != filetype)
 315                                 backref->errors |= REF_ERR_FILETYPE_UNMATCH;
 316                         if (!backref->errors && backref->found_inode_ref) {
 317                                 list_del(&backref->list);
 318                                 free(backref);
 319                         }
 320                 }
 321         }
 322
 323         if (!rec->checked || rec->merging)
 324                 return;
 325
 326         if (S_ISDIR(rec->imode)) {
 327                 if (rec->found_size != rec->isize)
 328                         rec->errors |= I_ERR_DIR_ISIZE_WRONG;
 329                 if (rec->found_file_extent)
 330                         rec->errors |= I_ERR_ODD_FILE_EXTENT;
 331         } else if (S_ISREG(rec->imode) || S_ISLNK(rec->imode)) {
 332                 if (rec->found_dir_item)
 333                         rec->errors |= I_ERR_ODD_DIR_ITEM;
 334                 if (rec->found_size != rec->nbytes)
 335                         rec->errors |= I_ERR_FILE_NBYTES_WRONG;
 336                 if (rec->extent_start == (u64)-1 || rec->extent_start > 0)
 337                         rec->first_extent_gap = 0;
 338                 if (rec->nlink > 0 && (rec->extent_end < rec->isize ||
 339                     rec->first_extent_gap < rec->isize))
 340                         rec->errors |= I_ERR_FILE_EXTENT_DISCOUNT;
 341         }
 342
 343         if (S_ISREG(rec->imode) || S_ISLNK(rec->imode)) {
 344                 if (rec->found_csum_item && rec->nodatasum)
 345                         rec->errors |= I_ERR_ODD_CSUM_ITEM;
 346                 if (rec->some_csum_missing && !rec->nodatasum)
 347                         rec->errors |= I_ERR_SOME_CSUM_MISSING;
 348         }
 349
 350         BUG_ON(rec->refs != 1);
 351         if (can_free_inode_rec(rec)) {
 352                 cache = find_cache_extent(inode_cache, rec->ino, 1);
 353                 node = container_of(cache, struct ptr_node, cache);
 354                 BUG_ON(node->data != rec);
 355                 remove_cache_extent(inode_cache, &node->cache);
 356                 free(node);
 357                 free_inode_rec(rec);
 358         }
 359 }
 360
 361 static int check_orphan_item(struct btrfs_root *root, u64 ino)
 362 {
 363         struct btrfs_path path;
 364         struct btrfs_key key;
 365         int ret;
 366
 367         key.objectid = BTRFS_ORPHAN_OBJECTID;
 368         key.type = BTRFS_ORPHAN_ITEM_KEY;
 369         key.offset = ino;
 370
 371         btrfs_init_path(&path);
 372         ret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
 373         btrfs_release_path(root, &path);
 374         if (ret > 0)
 375                 ret = -ENOENT;
 376         return ret;
 377 }
 378
 379 static int process_inode_item(struct extent_buffer *eb,
 380                               int slot, struct btrfs_key *key,
 381                               struct shared_node *active_node)
 382 {
 383         struct inode_record *rec;
 384         struct btrfs_inode_item *item;
 385
 386         rec = active_node->current;
 387         BUG_ON(rec->ino != key->objectid || rec->refs > 1);
 388         if (rec->found_inode_item) {
 389                 rec->errors |= I_ERR_DUP_INODE_ITEM;
 390                 return 1;
 391         }
 392         item = btrfs_item_ptr(eb, slot, struct btrfs_inode_item);
 393         rec->nlink = btrfs_inode_nlink(eb, item);
 394         rec->isize = btrfs_inode_size(eb, item);
 395         rec->nbytes = btrfs_inode_nbytes(eb, item);
 396         rec->imode = btrfs_inode_mode(eb, item);
 397         if (btrfs_inode_flags(eb, item) & BTRFS_INODE_NODATASUM)
 398                 rec->nodatasum = 1;
 399         rec->found_inode_item = 1;
 400         if (rec->nlink == 0)
 401                 rec->errors |= I_ERR_NO_ORPHAN_ITEM;
 402         maybe_free_inode_rec(&active_node->inode_cache, rec);
 403         return 0;
 404 }
 405
 406 static struct inode_backref *get_inode_backref(struct inode_record *rec,
 407                                                 const char *name,
 408                                                 int namelen, u64 dir)
 409 {
 410         struct inode_backref *backref;
 411
 412         list_for_each_entry(backref, &rec->backrefs, list) {
 413                 if (backref->dir != dir || backref->namelen != namelen)
 414                         continue;
 415                 if (memcmp(name, backref->name, namelen))
 416                         continue;
 417                 return backref;
 418         }
 419
 420         backref = malloc(sizeof(*backref) + namelen + 1);
 421         memset(backref, 0, sizeof(*backref));
 422         backref->dir = dir;
 423         backref->namelen = namelen;
 424         memcpy(backref->name, name, namelen);
 425         backref->name[namelen] = '\0';
 426         list_add_tail(&backref->list, &rec->backrefs);
 427         return backref;
 428 }
 429
 430 static int add_inode_backref(struct cache_tree *inode_cache,
 431                              u64 ino, u64 dir, u64 index,
 432                              const char *name, int namelen,
 433                              int filetype, int itemtype, int errors)
 434 {
 435         struct inode_record *rec;
 436         struct inode_backref *backref;
 437
 438         rec = get_inode_rec(inode_cache, ino, 1);
 439         backref = get_inode_backref(rec, name, namelen, dir);
 440         if (errors)
 441                 backref->errors |= errors;
 442         if (itemtype == BTRFS_DIR_INDEX_KEY) {
 443                 if (backref->found_dir_index)
 444                         backref->errors |= REF_ERR_DUP_DIR_INDEX;
 445                 if (backref->found_inode_ref && backref->index != index)
 446                         backref->errors |= REF_ERR_INDEX_UNMATCH;
 447                 if (backref->found_dir_item && backref->filetype != filetype)
 448                         backref->errors |= REF_ERR_FILETYPE_UNMATCH;
 449
 450                 backref->index = index;
 451                 backref->filetype = filetype;
 452                 backref->found_dir_index = 1;
 453         } else if (itemtype == BTRFS_DIR_ITEM_KEY) {
 454                 rec->found_link++;
 455                 if (backref->found_dir_item)
 456                         backref->errors |= REF_ERR_DUP_DIR_ITEM;
 457                 if (backref->found_dir_index && backref->filetype != filetype)
 458                         backref->errors |= REF_ERR_FILETYPE_UNMATCH;
 459
 460                 backref->filetype = filetype;
 461                 backref->found_dir_item = 1;
 462         } else if (itemtype == BTRFS_INODE_REF_KEY) {
 463                 if (backref->found_inode_ref)
 464                         backref->errors |= REF_ERR_DUP_INODE_REF;
 465                 if (backref->found_dir_index && backref->index != index)
 466                         backref->errors |= REF_ERR_INDEX_UNMATCH;
 467
 468                 backref->index = index;
 469                 backref->found_inode_ref = 1;
 470         } else {
 471                 BUG_ON(1);
 472         }
 473
 474         maybe_free_inode_rec(inode_cache, rec);
 475         return 0;
 476 }
 477
 478 static int merge_inode_recs(struct inode_record *src, struct inode_record *dst,
 479                             struct cache_tree *dst_cache)
 480 {
 481         struct inode_backref *backref;
 482         u32 dir_count = 0;
 483
 484         dst->merging = 1;
 485         list_for_each_entry(backref, &src->backrefs, list) {
 486                 if (backref->found_dir_index) {
 487                         add_inode_backref(dst_cache, dst->ino, backref->dir,
 488                                         backref->index, backref->name,
 489                                         backref->namelen, backref->filetype,
 490                                         BTRFS_DIR_INDEX_KEY, backref->errors);
 491                 }
 492                 if (backref->found_dir_item) {
 493                         dir_count++;
 494                         add_inode_backref(dst_cache, dst->ino,
 495                                         backref->dir, 0, backref->name,
 496                                         backref->namelen, backref->filetype,
 497                                         BTRFS_DIR_ITEM_KEY, backref->errors);
 498                 }
 499                 if (backref->found_inode_ref) {
 500                         add_inode_backref(dst_cache, dst->ino,
 501                                         backref->dir, backref->index,
 502                                         backref->name, backref->namelen, 0,
 503                                         BTRFS_INODE_REF_KEY, backref->errors);
 504                 }
 505         }
 506
 507         if (src->found_dir_item)
 508                 dst->found_dir_item = 1;
 509         if (src->found_file_extent)
 510                 dst->found_file_extent = 1;
 511         if (src->found_csum_item)
 512                 dst->found_csum_item = 1;
 513         if (src->some_csum_missing)
 514                 dst->some_csum_missing = 1;
 515         if (dst->first_extent_gap > src->first_extent_gap)
 516                 dst->first_extent_gap = src->first_extent_gap;
 517
 518         BUG_ON(src->found_link < dir_count);
 519         dst->found_link += src->found_link - dir_count;
 520         dst->found_size += src->found_size;
 521         if (src->extent_start != (u64)-1) {
 522                 if (dst->extent_start == (u64)-1) {
 523                         dst->extent_start = src->extent_start;
 524                         dst->extent_end = src->extent_end;
 525                 } else {
 526                         if (dst->extent_end > src->extent_start)
 527                                 dst->errors |= I_ERR_FILE_EXTENT_OVERLAP;
 528                         else if (dst->extent_end < src->extent_start &&
 529                                  dst->extent_end < dst->first_extent_gap)
 530                                 dst->first_extent_gap = dst->extent_end;
 531                         if (dst->extent_end < src->extent_end)
 532                                 dst->extent_end = src->extent_end;
 533                 }
 534         }
 535
 536         dst->errors |= src->errors;
 537         if (src->found_inode_item) {
 538                 if (!dst->found_inode_item) {
 539                         dst->nlink = src->nlink;
 540                         dst->isize = src->isize;
 541                         dst->nbytes = src->nbytes;
 542                         dst->imode = src->imode;
 543                         dst->nodatasum = src->nodatasum;
 544                         dst->found_inode_item = 1;
 545                 } else {
 546                         dst->errors |= I_ERR_DUP_INODE_ITEM;
 547                 }
 548         }
 549         dst->merging = 0;
 550
 551         return 0;
 552 }
 553
 554 static int splice_shared_node(struct shared_node *src_node,
 555                               struct shared_node *dst_node)
 556 {
 557         struct cache_extent *cache;
 558         struct ptr_node *node, *ins;
 559         struct cache_tree *src, *dst;
 560         struct inode_record *rec, *conflict;
 561         u64 current_ino = 0;
 562         int splice = 0;
 563         int ret;
 564
 565         if (--src_node->refs == 0)
 566                 splice = 1;
 567         if (src_node->current)
 568                 current_ino = src_node->current->ino;
 569
 570         src = &src_node->root_cache;
 571         dst = &dst_node->root_cache;
 572 again:
 573         cache = find_first_cache_extent(src, 0);
 574         while (cache) {
 575                 node = container_of(cache, struct ptr_node, cache);
 576                 rec = node->data;
 577                 cache = next_cache_extent(cache);
 578
 579                 if (splice) {
 580                         remove_cache_extent(src, &node->cache);
 581                         ins = node;
 582                 } else {
 583                         ins = malloc(sizeof(*ins));
 584                         ins->cache.start = node->cache.start;
 585                         ins->cache.size = node->cache.size;
 586                         ins->data = rec;
 587                         rec->refs++;
 588                 }
 589                 ret = insert_existing_cache_extent(dst, &ins->cache);
 590                 if (ret == -EEXIST) {
 591                         conflict = get_inode_rec(dst, rec->ino, 1);
 592                         merge_inode_recs(rec, conflict, dst);
 593                         if (rec->checked) {
 594                                 conflict->checked = 1;
 595                                 if (dst_node->current == conflict)
 596                                         dst_node->current = NULL;
 597                         }
 598                         maybe_free_inode_rec(dst, conflict);
 599                         free_inode_rec(rec);
 600                         free(ins);
 601                 } else {
 602                         BUG_ON(ret);
 603                 }
 604         }
 605
 606         if (src == &src_node->root_cache) {
 607                 src = &src_node->inode_cache;
 608                 dst = &dst_node->inode_cache;
 609                 goto again;
 610         }
 611
 612         if (current_ino > 0 && (!dst_node->current ||
 613             current_ino > dst_node->current->ino)) {
 614                 if (dst_node->current) {
 615                         dst_node->current->checked = 1;
 616                         maybe_free_inode_rec(dst, dst_node->current);
 617                 }
 618                 dst_node->current = get_inode_rec(dst, current_ino, 1);
 619         }
 620         return 0;
 621 }
 622
 623 static void free_inode_recs(struct cache_tree *inode_cache)
 624 {
 625         struct cache_extent *cache;
 626         struct ptr_node *node;
 627         struct inode_record *rec;
 628
 629         while (1) {
 630                 cache = find_first_cache_extent(inode_cache, 0);
 631                 if (!cache)
 632                         break;
 633                 node = container_of(cache, struct ptr_node, cache);
 634                 rec = node->data;
 635                 remove_cache_extent(inode_cache, &node->cache);
 636                 free(node);
 637                 free_inode_rec(rec);
 638         }
 639 }
 640
 641 static struct shared_node *find_shared_node(struct cache_tree *shared,
 642                                             u64 bytenr)
 643 {
 644         struct cache_extent *cache;
 645         struct shared_node *node;
 646
 647         cache = find_cache_extent(shared, bytenr, 1);
 648         if (cache) {
 649                 node = container_of(cache, struct shared_node, cache);
 650                 return node;
 651         }
 652         return NULL;
 653 }
 654
 655 static int add_shared_node(struct cache_tree *shared, u64 bytenr, u32 refs)
 656 {
 657         int ret;
 658         struct shared_node *node;
 659
 660         node = calloc(1, sizeof(*node));
 661         node->cache.start = bytenr;
 662         node->cache.size = 1;
 663         cache_tree_init(&node->root_cache);
 664         cache_tree_init(&node->inode_cache);
 665         node->refs = refs;
 666
 667         ret = insert_existing_cache_extent(shared, &node->cache);
 668         BUG_ON(ret);
 669         return 0;
 670 }
 671
 672 static int enter_shared_node(struct btrfs_root *root, u64 bytenr, u32 refs,
 673                              struct walk_control *wc, int level)
 674 {
 675         struct shared_node *node;
 676         struct shared_node *dest;
 677
 678         if (level == wc->active_node)
 679                 return 0;
 680
 681         BUG_ON(wc->active_node <= level);
 682         node = find_shared_node(&wc->shared, bytenr);
 683         if (!node) {
 684                 add_shared_node(&wc->shared, bytenr, refs);
 685                 node = find_shared_node(&wc->shared, bytenr);
 686                 wc->nodes[level] = node;
 687                 wc->active_node = level;
 688                 return 0;
 689         }
 690
 691         if (wc->root_level == wc->active_node &&
 692             btrfs_root_refs(&root->root_item) == 0) {
 693                 if (--node->refs == 0) {
 694                         free_inode_recs(&node->root_cache);
 695                         free_inode_recs(&node->inode_cache);
 696                         remove_cache_extent(&wc->shared, &node->cache);
 697                         free(node);
 698                 }
 699                 return 1;
 700         }
 701
 702         dest = wc->nodes[wc->active_node];
 703         splice_shared_node(node, dest);
 704         if (node->refs == 0) {
 705                 remove_cache_extent(&wc->shared, &node->cache);
 706                 free(node);
 707         }
 708         return 1;
 709 }
 710
 711 static int leave_shared_node(struct btrfs_root *root,
 712                              struct walk_control *wc, int level)
 713 {
 714         struct shared_node *node;
 715         struct shared_node *dest;
 716         int i;
 717
 718         if (level == wc->root_level)
 719                 return 0;
 720
 721         for (i = level + 1; i < BTRFS_MAX_LEVEL; i++) {
 722                 if (wc->nodes[i])
 723                         break;
 724         }
 725         BUG_ON(i >= BTRFS_MAX_LEVEL);
 726
 727         node = wc->nodes[wc->active_node];
 728         wc->nodes[wc->active_node] = NULL;
 729         wc->active_node = i;
 730
 731         dest = wc->nodes[wc->active_node];
 732         if (wc->active_node < wc->root_level ||
 733             btrfs_root_refs(&root->root_item) > 0) {
 734                 BUG_ON(node->refs <= 1);
 735                 splice_shared_node(node, dest);
 736         } else {
 737                 BUG_ON(node->refs < 2);
 738                 node->refs--;
 739         }
 740         return 0;
 741 }
 742
 743 static int process_dir_item(struct extent_buffer *eb,
 744                             int slot, struct btrfs_key *key,
 745                             struct shared_node *active_node)
 746 {
 747         u32 total;
 748         u32 cur = 0;
 749         u32 len;
 750         u32 name_len;
 751         u32 data_len;
 752         int error;
 753         int nritems = 0;
 754         int filetype;
 755         struct btrfs_dir_item *di;
 756         struct inode_record *rec;
 757         struct cache_tree *root_cache;
 758         struct cache_tree *inode_cache;
 759         struct btrfs_key location;
 760         char namebuf[BTRFS_NAME_LEN];
 761
 762         root_cache = &active_node->root_cache;
 763         inode_cache = &active_node->inode_cache;
 764         rec = active_node->current;
 765         rec->found_dir_item = 1;
 766
 767         di = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);
 768         total = btrfs_item_size_nr(eb, slot);
 769         while (cur < total) {
 770                 nritems++;
 771                 btrfs_dir_item_key_to_cpu(eb, di, &location);
 772                 name_len = btrfs_dir_name_len(eb, di);
 773                 data_len = btrfs_dir_data_len(eb, di);
 774                 filetype = btrfs_dir_type(eb, di);
 775
 776                 rec->found_size += name_len;
 777                 if (name_len <= BTRFS_NAME_LEN) {
 778                         len = name_len;
 779                         error = 0;
 780                 } else {
 781                         len = BTRFS_NAME_LEN;
 782                         error = REF_ERR_NAME_TOO_LONG;
 783                 }
 784                 read_extent_buffer(eb, namebuf, (unsigned long)(di + 1), len);
 785
 786                 if (location.type == BTRFS_INODE_ITEM_KEY) {
 787                         add_inode_backref(inode_cache, location.objectid,
 788                                           key->objectid, key->offset, namebuf,
 789                                           len, filetype, key->type, error);
 790                 } else if (location.type == BTRFS_ROOT_ITEM_KEY) {
 791                         add_inode_backref(root_cache, location.objectid,
 792                                           key->objectid, key->offset, namebuf,
 793                                           len, filetype, key->type, error);
 794                 } else {
 795                         fprintf(stderr, "warning line %d\n", __LINE__);
 796                 }
 797
 798                 len = sizeof(*di) + name_len + data_len;
 799                 di = (struct btrfs_dir_item *)((char *)di + len);
 800                 cur += len;
 801         }
 802         if (key->type == BTRFS_DIR_INDEX_KEY && nritems > 1)
 803                 rec->errors |= I_ERR_DUP_DIR_INDEX;
 804
 805         return 0;
 806 }
 807
 808 static int process_inode_ref(struct extent_buffer *eb,
 809                              int slot, struct btrfs_key *key,
 810                              struct shared_node *active_node)
 811 {
 812         u32 total;
 813         u32 cur = 0;
 814         u32 len;
 815         u32 name_len;
 816         u64 index;
 817         int error;
 818         struct cache_tree *inode_cache;
 819         struct btrfs_inode_ref *ref;
 820         char namebuf[BTRFS_NAME_LEN];
 821
 822         inode_cache = &active_node->inode_cache;
 823
 824         ref = btrfs_item_ptr(eb, slot, struct btrfs_inode_ref);
 825         total = btrfs_item_size_nr(eb, slot);
 826         while (cur < total) {
 827                 name_len = btrfs_inode_ref_name_len(eb, ref);
 828                 index = btrfs_inode_ref_index(eb, ref);
 829                 if (name_len <= BTRFS_NAME_LEN) {
 830                         len = name_len;
 831                         error = 0;
 832                 } else {
 833                         len = BTRFS_NAME_LEN;
 834                         error = REF_ERR_NAME_TOO_LONG;
 835                 }
 836                 read_extent_buffer(eb, namebuf, (unsigned long)(ref + 1), len);
 837                 add_inode_backref(inode_cache, key->objectid, key->offset,
 838                                   index, namebuf, len, 0, key->type, error);
 839
 840                 len = sizeof(*ref) + name_len;
 841                 ref = (struct btrfs_inode_ref *)((char *)ref + len);
 842                 cur += len;
 843         }
 844         return 0;
 845 }
 846
 847 static u64 count_csum_range(struct btrfs_root *root, u64 start, u64 len)
 848 {
 849         struct btrfs_key key;
 850         struct btrfs_path path;
 851         struct extent_buffer *leaf;
 852         int ret ;
 853         size_t size;
 854         u64 found = 0;
 855         u64 csum_end;
 856         u16 csum_size = btrfs_super_csum_size(&root->fs_info->super_copy);
 857
 858         btrfs_init_path(&path);
 859
 860         key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
 861         key.offset = start;
 862         key.type = BTRFS_EXTENT_CSUM_KEY;
 863
 864         ret = btrfs_search_slot(NULL, root->fs_info->csum_root,
 865                                 &key, &path, 0, 0);
 866         BUG_ON(ret < 0);
 867         if (ret > 0 && path.slots[0] > 0) {
 868                 leaf = path.nodes[0];
 869                 btrfs_item_key_to_cpu(leaf, &key, path.slots[0] - 1);
 870                 if (key.objectid == BTRFS_EXTENT_CSUM_OBJECTID &&
 871                     key.type == BTRFS_EXTENT_CSUM_KEY)
 872                         path.slots[0]--;
 873         }
 874
 875         while (len > 0) {
 876                 leaf = path.nodes[0];
 877                 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
 878                         ret = btrfs_next_leaf(root->fs_info->csum_root, &path);
 879                         BUG_ON(ret < 0);
 880                         if (ret > 0)
 881                                 break;
 882                         leaf = path.nodes[0];
 883                 }
 884
 885                 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
 886                 if (key.objectid != BTRFS_EXTENT_CSUM_OBJECTID ||
 887                     key.type != BTRFS_EXTENT_CSUM_KEY)
 888                         break;
 889
 890                 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
 891                 if (key.offset >= start + len)
 892                         break;
 893
 894                 if (key.offset > start)
 895                         start = key.offset;
 896
 897                 size = btrfs_item_size_nr(leaf, path.slots[0]);
 898                 csum_end = key.offset + (size / csum_size) * root->sectorsize;
 899                 if (csum_end > start) {
 900                         size = min(csum_end - start, len);
 901                         len -= size;
 902                         start += size;
 903                         found += size;
 904                 }
 905
 906                 path.slots[0]++;
 907         }
 908         btrfs_release_path(root->fs_info->csum_root, &path);
 909         return found;
 910 }
 911
 912 static int process_file_extent(struct btrfs_root *root,
 913                                 struct extent_buffer *eb,
 914                                 int slot, struct btrfs_key *key,
 915                                 struct shared_node *active_node)
 916 {
 917         struct inode_record *rec;
 918         struct btrfs_file_extent_item *fi;
 919         u64 num_bytes = 0;
 920         u64 disk_bytenr = 0;
 921         u64 extent_offset = 0;
 922         u64 mask = root->sectorsize - 1;
 923         int extent_type;
 924
 925         rec = active_node->current;
 926         BUG_ON(rec->ino != key->objectid || rec->refs > 1);
 927         rec->found_file_extent = 1;
 928
 929         if (rec->extent_start == (u64)-1) {
 930                 rec->extent_start = key->offset;
 931                 rec->extent_end = key->offset;
 932         }
 933
 934         if (rec->extent_end > key->offset)
 935                 rec->errors |= I_ERR_FILE_EXTENT_OVERLAP;
 936         else if (rec->extent_end < key->offset &&
 937                  rec->extent_end < rec->first_extent_gap)
 938                 rec->first_extent_gap = rec->extent_end;
 939
 940         fi = btrfs_item_ptr(eb, slot, struct btrfs_file_extent_item);
 941         extent_type = btrfs_file_extent_type(eb, fi);
 942
 943         if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
 944                 num_bytes = btrfs_file_extent_inline_len(eb, fi);
 945                 if (num_bytes == 0)
 946                         rec->errors |= I_ERR_BAD_FILE_EXTENT;
 947                 rec->found_size += num_bytes;
 948                 num_bytes = (num_bytes + mask) & ~mask;
 949         } else if (extent_type == BTRFS_FILE_EXTENT_REG ||
 950                    extent_type == BTRFS_FILE_EXTENT_PREALLOC) {
 951                 num_bytes = btrfs_file_extent_num_bytes(eb, fi);
 952                 disk_bytenr = btrfs_file_extent_disk_bytenr(eb, fi);
 953                 extent_offset = btrfs_file_extent_offset(eb, fi);
 954                 if (num_bytes == 0 || (num_bytes & mask))
 955                         rec->errors |= I_ERR_BAD_FILE_EXTENT;
 956                 if (num_bytes + extent_offset >
 957                     btrfs_file_extent_ram_bytes(eb, fi))
 958                         rec->errors |= I_ERR_BAD_FILE_EXTENT;
 959                 if (extent_type == BTRFS_FILE_EXTENT_PREALLOC &&
 960                     (btrfs_file_extent_compression(eb, fi) ||
 961                      btrfs_file_extent_encryption(eb, fi) ||
 962                      btrfs_file_extent_other_encoding(eb, fi)))
 963                         rec->errors |= I_ERR_BAD_FILE_EXTENT;
 964                 if (disk_bytenr > 0)
 965                         rec->found_size += num_bytes;
 966         } else {
 967                 rec->errors |= I_ERR_BAD_FILE_EXTENT;
 968         }
 969         rec->extent_end = key->offset + num_bytes;
 970
 971         if (disk_bytenr > 0) {
 972                 u64 found;
 973                 if (btrfs_file_extent_compression(eb, fi))
 974                         num_bytes = btrfs_file_extent_disk_num_bytes(eb, fi);
 975                 else
 976                         disk_bytenr += extent_offset;
 977
 978                 found = count_csum_range(root, disk_bytenr, num_bytes);
 979                 if (extent_type == BTRFS_FILE_EXTENT_REG) {
 980                         if (found > 0)
 981                                 rec->found_csum_item = 1;
 982                         if (found < num_bytes)
 983                                 rec->some_csum_missing = 1;
 984                 } else if (extent_type == BTRFS_FILE_EXTENT_PREALLOC) {
 985                         if (found > 0)
 986                                 rec->errors |= I_ERR_ODD_CSUM_ITEM;
 987                 }
 988         }
 989         return 0;
 990 }
 991
 992 static int process_one_leaf(struct btrfs_root *root, struct extent_buffer *eb,
 993                             struct walk_control *wc)
 994 {
 995         struct btrfs_key key;
 996         u32 nritems;
 997         int i;
 998         int ret;
 999         struct cache_tree *inode_cache;
1000         struct shared_node *active_node;
1001
1002         if (wc->root_level == wc->active_node &&
1003             btrfs_root_refs(&root->root_item) == 0)
1004                 return 0;
1005
1006         active_node = wc->nodes[wc->active_node];
1007         inode_cache = &active_node->inode_cache;
1008         nritems = btrfs_header_nritems(eb);
1009         for (i = 0; i < nritems; i++) {
1010                 btrfs_item_key_to_cpu(eb, &key, i);
1011                 if (active_node->current == NULL ||
1012                     active_node->current->ino < key.objectid) {
1013                         if (active_node->current) {
1014                                 active_node->current->checked = 1;
1015                                 maybe_free_inode_rec(inode_cache,
1016                                                      active_node->current);
1017                         }
1018                         active_node->current = get_inode_rec(inode_cache,
1019                                                              key.objectid, 1);
1020                 }
1021                 switch (key.type) {
1022                 case BTRFS_DIR_ITEM_KEY:
1023                 case BTRFS_DIR_INDEX_KEY:
1024                         ret = process_dir_item(eb, i, &key, active_node);
1025                         break;
1026                 case BTRFS_INODE_REF_KEY:
1027                         ret = process_inode_ref(eb, i, &key, active_node);
1028                         break;
1029                 case BTRFS_INODE_ITEM_KEY:
1030                         ret = process_inode_item(eb, i, &key, active_node);
1031                         break;
1032                 case BTRFS_EXTENT_DATA_KEY:
1033                         ret = process_file_extent(root, eb, i, &key,
1034                                                   active_node);
1035                         break;
1036                 default:
1037                         break;
1038                 };
1039         }
1040         return ret;
1041 }
1042
1043 static void reada_walk_down(struct btrfs_root *root,
1044                             struct extent_buffer *node, int slot)
1045 {
1046         u64 bytenr;
1047         u64 ptr_gen;
1048         u32 nritems;
1049         u32 blocksize;
1050         int i;
1051         int ret;
1052         int level;
1053
1054         level = btrfs_header_level(node);
1055         if (level != 1)
1056                 return;
1057
1058         nritems = btrfs_header_nritems(node);
1059         blocksize = btrfs_level_size(root, level - 1);
1060         for (i = slot; i < nritems; i++) {
1061                 bytenr = btrfs_node_blockptr(node, i);
1062                 ptr_gen = btrfs_node_ptr_generation(node, i);
1063                 ret = readahead_tree_block(root, bytenr, blocksize, ptr_gen);
1064                 if (ret)
1065                         break;
1066         }
1067 }
1068
1069 static int walk_down_tree(struct btrfs_root *root, struct btrfs_path *path,
1070                           struct walk_control *wc, int *level)
1071 {
1072         u64 bytenr;
1073         u64 ptr_gen;
1074         struct extent_buffer *next;
1075         struct extent_buffer *cur;
1076         u32 blocksize;
1077         int ret;
1078         u64 refs;
1079
1080         WARN_ON(*level < 0);
1081         WARN_ON(*level >= BTRFS_MAX_LEVEL);
1082         ret = btrfs_lookup_extent_info(NULL, root,
1083                                        path->nodes[*level]->start,
1084                                        path->nodes[*level]->len, &refs, NULL);
1085         BUG_ON(ret);
1086         if (refs > 1) {
1087                 ret = enter_shared_node(root, path->nodes[*level]->start,
1088                                         refs, wc, *level);
1089                 if (ret > 0)
1090                         goto out;
1091         }
1092
1093         while (*level >= 0) {
1094                 WARN_ON(*level < 0);
1095                 WARN_ON(*level >= BTRFS_MAX_LEVEL);
1096                 cur = path->nodes[*level];
1097
1098                 if (btrfs_header_level(cur) != *level)
1099                         WARN_ON(1);
1100
1101                 if (path->slots[*level] >= btrfs_header_nritems(cur))
1102                         break;
1103                 if (*level == 0) {
1104                         ret = process_one_leaf(root, cur, wc);
1105                         break;
1106                 }
1107                 bytenr = btrfs_node_blockptr(cur, path->slots[*level]);
1108                 ptr_gen = btrfs_node_ptr_generation(cur, path->slots[*level]);
1109                 blocksize = btrfs_level_size(root, *level - 1);
1110                 ret = btrfs_lookup_extent_info(NULL, root, bytenr, blocksize,
1111                                                &refs, NULL);
1112                 BUG_ON(ret);
1113
1114                 if (refs > 1) {
1115                         ret = enter_shared_node(root, bytenr, refs,
1116                                                 wc, *level - 1);
1117                         if (ret > 0) {
1118                                 path->slots[*level]++;
1119                                 continue;
1120                         }
1121                 }
1122
1123                 next = btrfs_find_tree_block(root, bytenr, blocksize);
1124                 if (!next || !btrfs_buffer_uptodate(next, ptr_gen)) {
1125                         free_extent_buffer(next);
1126                         reada_walk_down(root, cur, path->slots[*level]);
1127                         next = read_tree_block(root, bytenr, blocksize,
1128                                                ptr_gen);
1129                 }
1130
1131                 *level = *level - 1;
1132                 free_extent_buffer(path->nodes[*level]);
1133                 path->nodes[*level] = next;
1134                 path->slots[*level] = 0;
1135         }
1136 out:
1137         path->slots[*level] = btrfs_header_nritems(path->nodes[*level]);
1138         return 0;
1139 }
1140
1141 static int walk_up_tree(struct btrfs_root *root, struct btrfs_path *path,
1142                         struct walk_control *wc, int *level)
1143 {
1144         int i;
1145         struct extent_buffer *leaf;
1146
1147         for (i = *level; i < BTRFS_MAX_LEVEL - 1 && path->nodes[i]; i++) {
1148                 leaf = path->nodes[i];
1149                 if (path->slots[i] + 1 < btrfs_header_nritems(leaf)) {
1150                         path->slots[i]++;
1151                         *level = i;
1152                         return 0;
1153                 } else {
1154                         free_extent_buffer(path->nodes[*level]);
1155                         path->nodes[*level] = NULL;
1156                         BUG_ON(*level > wc->active_node);
1157                         if (*level == wc->active_node)
1158                                 leave_shared_node(root, wc, *level);
1159                         *level = i + 1;
1160                 }
1161         }
1162         return 1;
1163 }
1164
1165 static int check_root_dir(struct inode_record *rec)
1166 {
1167         struct inode_backref *backref;
1168         int ret = -1;
1169
1170         if (!rec->found_inode_item || rec->errors)
1171                 goto out;
1172         if (rec->nlink != 1 || rec->found_link != 0)
1173                 goto out;
1174         if (list_empty(&rec->backrefs))
1175                 goto out;
1176         backref = list_entry(rec->backrefs.next, struct inode_backref, list);
1177         if (!backref->found_inode_ref)
1178                 goto out;
1179         if (backref->index != 0 || backref->namelen != 2 ||
1180             memcmp(backref->name, "..", 2))
1181                 goto out;
1182         if (backref->found_dir_index || backref->found_dir_item)
1183                 goto out;
1184         ret = 0;
1185 out:
1186         return ret;
1187 }
1188
1189 static int check_inode_recs(struct btrfs_root *root,
1190                             struct cache_tree *inode_cache)
1191 {
1192         struct cache_extent *cache;
1193         struct ptr_node *node;
1194         struct inode_record *rec;
1195         struct inode_backref *backref;
1196         int ret;
1197         u64 error = 0;
1198         u64 root_dirid = btrfs_root_dirid(&root->root_item);
1199
1200         if (btrfs_root_refs(&root->root_item) == 0) {
1201                 if (!cache_tree_empty(inode_cache))
1202                         fprintf(stderr, "warning line %d\n", __LINE__);
1203                 return 0;
1204         }
1205
1206         rec = get_inode_rec(inode_cache, root_dirid, 0);
1207         if (rec) {
1208                 ret = check_root_dir(rec);
1209                 if (ret) {
1210                         fprintf(stderr, "root %llu root dir %llu error\n",
1211                                 (unsigned long long)root->root_key.objectid,
1212                                 (unsigned long long)root_dirid);
1213                         error++;
1214                 }
1215         } else {
1216                 fprintf(stderr, "root %llu root dir %llu not found\n",
1217                         (unsigned long long)root->root_key.objectid,
1218                         (unsigned long long)root_dirid);
1219         }
1220
1221         while (1) {
1222                 cache = find_first_cache_extent(inode_cache, 0);
1223                 if (!cache)
1224                         break;
1225                 node = container_of(cache, struct ptr_node, cache);
1226                 rec = node->data;
1227                 remove_cache_extent(inode_cache, &node->cache);
1228                 free(node);
1229                 if (rec->ino == root_dirid ||
1230                     rec->ino == BTRFS_ORPHAN_OBJECTID) {
1231                         free_inode_rec(rec);
1232                         continue;
1233                 }
1234
1235                 if (rec->errors & I_ERR_NO_ORPHAN_ITEM) {
1236                         ret = check_orphan_item(root, rec->ino);
1237                         if (ret == 0)
1238                                 rec->errors &= ~I_ERR_NO_ORPHAN_ITEM;
1239                         if (can_free_inode_rec(rec)) {
1240                                 free_inode_rec(rec);
1241                                 continue;
1242                         }
1243                 }
1244
1245                 error++;
1246                 if (!rec->found_inode_item)
1247                         rec->errors |= I_ERR_NO_INODE_ITEM;
1248                 if (rec->found_link != rec->nlink)
1249                         rec->errors |= I_ERR_LINK_COUNT_WRONG;
1250                 fprintf(stderr, "root %llu inode %llu errors %x\n",
1251                         (unsigned long long) root->root_key.objectid,
1252                         (unsigned long long) rec->ino, rec->errors);
1253                 list_for_each_entry(backref, &rec->backrefs, list) {
1254                         if (!backref->found_dir_item)
1255                                 backref->errors |= REF_ERR_NO_DIR_ITEM;
1256                         if (!backref->found_dir_index)
1257                                 backref->errors |= REF_ERR_NO_DIR_INDEX;
1258                         if (!backref->found_inode_ref)
1259                                 backref->errors |= REF_ERR_NO_INODE_REF;
1260                         fprintf(stderr, "\tunresolved ref dir %llu index %llu"
1261                                 " namelen %u name %s filetype %d error %x\n",
1262                                 (unsigned long long)backref->dir,
1263                                 (unsigned long long)backref->index,
1264                                 backref->namelen, backref->name,
1265                                 backref->filetype, backref->errors);
1266                 }
1267                 free_inode_rec(rec);
1268         }
1269         return (error > 0) ? -1 : 0;
1270 }
1271
1272 static struct root_record *get_root_rec(struct cache_tree *root_cache,
1273                                         u64 objectid)
1274 {
1275         struct cache_extent *cache;
1276         struct root_record *rec = NULL;
1277         int ret;
1278
1279         cache = find_cache_extent(root_cache, objectid, 1);
1280         if (cache) {
1281                 rec = container_of(cache, struct root_record, cache);
1282         } else {
1283                 rec = calloc(1, sizeof(*rec));
1284                 rec->objectid = objectid;
1285                 INIT_LIST_HEAD(&rec->backrefs);
1286                 rec->cache.start = objectid;
1287                 rec->cache.size = 1;
1288
1289                 ret = insert_existing_cache_extent(root_cache, &rec->cache);
1290                 BUG_ON(ret);
1291         }
1292         return rec;
1293 }
1294
1295 static struct root_backref *get_root_backref(struct root_record *rec,
1296                                              u64 ref_root, u64 dir, u64 index,
1297                                              const char *name, int namelen)
1298 {
1299         struct root_backref *backref;
1300
1301         list_for_each_entry(backref, &rec->backrefs, list) {
1302                 if (backref->ref_root != ref_root || backref->dir != dir ||
1303                     backref->namelen != namelen)
1304                         continue;
1305                 if (memcmp(name, backref->name, namelen))
1306                         continue;
1307                 return backref;
1308         }
1309
1310         backref = malloc(sizeof(*backref) + namelen + 1);
1311         memset(backref, 0, sizeof(*backref));
1312         backref->ref_root = ref_root;
1313         backref->dir = dir;
1314         backref->index = index;
1315         backref->namelen = namelen;
1316         memcpy(backref->name, name, namelen);
1317         backref->name[namelen] = '\0';
1318         list_add_tail(&backref->list, &rec->backrefs);
1319         return backref;
1320 }
1321
1322 static void free_root_recs(struct cache_tree *root_cache)
1323 {
1324         struct cache_extent *cache;
1325         struct root_record *rec;
1326         struct root_backref *backref;
1327
1328         while (1) {
1329                 cache = find_first_cache_extent(root_cache, 0);
1330                 if (!cache)
1331                         break;
1332                 rec = container_of(cache, struct root_record, cache);
1333                 remove_cache_extent(root_cache, &rec->cache);
1334
1335                 while (!list_empty(&rec->backrefs)) {
1336                         backref = list_entry(rec->backrefs.next,
1337                                              struct root_backref, list);
1338                         list_del(&backref->list);
1339                         free(backref);
1340                 }
1341                 kfree(rec);
1342         }
1343 }
1344
1345 static int add_root_backref(struct cache_tree *root_cache,
1346                             u64 root_id, u64 ref_root, u64 dir, u64 index,
1347                             const char *name, int namelen,
1348                             int item_type, int errors)
1349 {
1350         struct root_record *rec;
1351         struct root_backref *backref;
1352
1353         rec = get_root_rec(root_cache, root_id);
1354         backref = get_root_backref(rec, ref_root, dir, index, name, namelen);
1355
1356         backref->errors |= errors;
1357
1358         if (item_type != BTRFS_DIR_ITEM_KEY) {
1359                 if (backref->found_dir_index || backref->found_back_ref ||
1360                     backref->found_forward_ref) {
1361                         if (backref->index != index)
1362                                 backref->errors |= REF_ERR_INDEX_UNMATCH;
1363                 } else {
1364                         backref->index = index;
1365                 }
1366         }
1367
1368         if (item_type == BTRFS_DIR_ITEM_KEY) {
1369                 backref->found_dir_item = 1;
1370                 backref->reachable = 1;
1371                 rec->found_ref++;
1372         } else if (item_type == BTRFS_DIR_INDEX_KEY) {
1373                 backref->found_dir_index = 1;
1374         } else if (item_type == BTRFS_ROOT_REF_KEY) {
1375                 if (backref->found_forward_ref)
1376                         backref->errors |= REF_ERR_DUP_ROOT_REF;
1377                 backref->found_forward_ref = 1;
1378         } else if (item_type == BTRFS_ROOT_BACKREF_KEY) {
1379                 if (backref->found_back_ref)
1380                         backref->errors |= REF_ERR_DUP_ROOT_BACKREF;
1381                 backref->found_back_ref = 1;
1382         } else {
1383                 BUG_ON(1);
1384         }
1385
1386         return 0;
1387 }
1388
1389 static int merge_root_recs(struct btrfs_root *root,
1390                            struct cache_tree *src_cache,
1391                            struct cache_tree *dst_cache)
1392 {
1393         struct cache_extent *cache;
1394         struct ptr_node *node;
1395         struct inode_record *rec;
1396         struct inode_backref *backref;
1397
1398         if (root->root_key.objectid == BTRFS_TREE_RELOC_OBJECTID) {
1399                 free_inode_recs(src_cache);
1400                 return 0;
1401         }
1402
1403         while (1) {
1404                 cache = find_first_cache_extent(src_cache, 0);
1405                 if (!cache)
1406                         break;
1407                 node = container_of(cache, struct ptr_node, cache);
1408                 rec = node->data;
1409                 remove_cache_extent(src_cache, &node->cache);
1410                 free(node);
1411
1412                 list_for_each_entry(backref, &rec->backrefs, list) {
1413                         BUG_ON(backref->found_inode_ref);
1414                         if (backref->found_dir_item)
1415                                 add_root_backref(dst_cache, rec->ino,
1416                                         root->root_key.objectid, backref->dir,
1417                                         backref->index, backref->name,
1418                                         backref->namelen, BTRFS_DIR_ITEM_KEY,
1419                                         backref->errors);
1420                         if (backref->found_dir_index)
1421                                 add_root_backref(dst_cache, rec->ino,
1422                                         root->root_key.objectid, backref->dir,
1423                                         backref->index, backref->name,
1424                                         backref->namelen, BTRFS_DIR_INDEX_KEY,
1425                                         backref->errors);
1426                 }
1427                 free_inode_rec(rec);
1428         }
1429         return 0;
1430 }
1431
1432 static int check_root_refs(struct btrfs_root *root,
1433                            struct cache_tree *root_cache)
1434 {
1435         struct root_record *rec;
1436         struct root_record *ref_root;
1437         struct root_backref *backref;
1438         struct cache_extent *cache;
1439         int loop = 1;
1440         int ret;
1441         int error;
1442         int errors = 0;
1443
1444         rec = get_root_rec(root_cache, BTRFS_FS_TREE_OBJECTID);
1445         rec->found_ref = 1;
1446
1447         /* fixme: this can not detect circular references */
1448         while (loop) {
1449                 loop = 0;
1450                 cache = find_first_cache_extent(root_cache, 0);
1451                 while (1) {
1452                         if (!cache)
1453                                 break;
1454                         rec = container_of(cache, struct root_record, cache);
1455                         cache = next_cache_extent(cache);
1456
1457                         if (rec->found_ref == 0)
1458                                 continue;
1459
1460                         list_for_each_entry(backref, &rec->backrefs, list) {
1461                                 if (!backref->reachable)
1462                                         continue;
1463
1464                                 ref_root = get_root_rec(root_cache,
1465                                                         backref->ref_root);
1466                                 if (ref_root->found_ref > 0)
1467                                         continue;
1468
1469                                 backref->reachable = 0;
1470                                 rec->found_ref--;
1471                                 if (rec->found_ref == 0)
1472                                         loop = 1;
1473                         }
1474                 }
1475         }
1476
1477         cache = find_first_cache_extent(root_cache, 0);
1478         while (1) {
1479                 if (!cache)
1480                         break;
1481                 rec = container_of(cache, struct root_record, cache);
1482                 cache = next_cache_extent(cache);
1483
1484                 if (rec->found_ref == 0 &&
1485                     rec->objectid >= BTRFS_FIRST_FREE_OBJECTID &&
1486                     rec->objectid <= BTRFS_LAST_FREE_OBJECTID) {
1487                         ret = check_orphan_item(root->fs_info->tree_root,
1488                                                 rec->objectid);
1489                         if (ret == 0)
1490                                 continue;
1491                         errors++;
1492                         fprintf(stderr, "fs tree %llu not referenced\n",
1493                                 (unsigned long long)rec->objectid);
1494                 }
1495
1496                 error = 0;
1497                 if (rec->found_ref > 0 && !rec->found_root_item)
1498                         error = 1;
1499                 list_for_each_entry(backref, &rec->backrefs, list) {
1500                         if (!backref->found_dir_item)
1501                                 backref->errors |= REF_ERR_NO_DIR_ITEM;
1502                         if (!backref->found_dir_index)
1503                                 backref->errors |= REF_ERR_NO_DIR_INDEX;
1504                         if (!backref->found_back_ref)
1505                                 backref->errors |= REF_ERR_NO_ROOT_BACKREF;
1506                         if (!backref->found_forward_ref)
1507                                 backref->errors |= REF_ERR_NO_ROOT_REF;
1508                         if (backref->reachable && backref->errors)
1509                                 error = 1;
1510                 }
1511                 if (!error)
1512                         continue;
1513
1514                 errors++;
1515                 fprintf(stderr, "fs tree %llu refs %u %s\n",
1516                         (unsigned long long)rec->objectid, rec->found_ref,
1517                          rec->found_root_item ? "" : "not found");
1518
1519                 list_for_each_entry(backref, &rec->backrefs, list) {
1520                         if (!backref->reachable)
1521                                 continue;
1522                         if (!backref->errors && rec->found_root_item)
1523                                 continue;
1524                         fprintf(stderr, "\tunresolved ref root %llu dir %llu"
1525                                 " index %llu namelen %u name %s error %x\n",
1526                                 (unsigned long long)backref->ref_root,
1527                                 (unsigned long long)backref->dir,
1528                                 (unsigned long long)backref->index,
1529                                 backref->namelen, backref->name,
1530                                 backref->errors);
1531                 }
1532         }
1533         return errors > 0 ? 1 : 0;
1534 }
1535
1536 static int process_root_ref(struct extent_buffer *eb, int slot,
1537                             struct btrfs_key *key,
1538                             struct cache_tree *root_cache)
1539 {
1540         u64 dirid;
1541         u64 index;
1542         u32 len;
1543         u32 name_len;
1544         struct btrfs_root_ref *ref;
1545         char namebuf[BTRFS_NAME_LEN];
1546         int error;
1547
1548         ref = btrfs_item_ptr(eb, slot, struct btrfs_root_ref);
1549
1550         dirid = btrfs_root_ref_dirid(eb, ref);
1551         index = btrfs_root_ref_sequence(eb, ref);
1552         name_len = btrfs_root_ref_name_len(eb, ref);
1553
1554         if (name_len <= BTRFS_NAME_LEN) {
1555                 len = name_len;
1556                 error = 0;
1557         } else {
1558                 len = BTRFS_NAME_LEN;
1559                 error = REF_ERR_NAME_TOO_LONG;
1560         }
1561         read_extent_buffer(eb, namebuf, (unsigned long)(ref + 1), len);
1562
1563         if (key->type == BTRFS_ROOT_REF_KEY) {
1564                 add_root_backref(root_cache, key->offset, key->objectid, dirid,
1565                                  index, namebuf, len, key->type, error);
1566         } else {
1567                 add_root_backref(root_cache, key->objectid, key->offset, dirid,
1568                                  index, namebuf, len, key->type, error);
1569         }
1570         return 0;
1571 }
1572
1573 static int check_fs_root(struct btrfs_root *root,
1574                          struct cache_tree *root_cache,
1575                          struct walk_control *wc)
1576 {
1577         int ret = 0;
1578         int wret;
1579         int level;
1580         struct btrfs_path path;
1581         struct shared_node root_node;
1582         struct root_record *rec;
1583         struct btrfs_root_item *root_item = &root->root_item;
1584
1585         if (root->root_key.objectid != BTRFS_TREE_RELOC_OBJECTID) {
1586                 rec = get_root_rec(root_cache, root->root_key.objectid);
1587                 if (btrfs_root_refs(root_item) > 0)
1588                         rec->found_root_item = 1;
1589         }
1590
1591         btrfs_init_path(&path);
1592         memset(&root_node, 0, sizeof(root_node));
1593         cache_tree_init(&root_node.root_cache);
1594         cache_tree_init(&root_node.inode_cache);
1595
1596         level = btrfs_header_level(root->node);
1597         memset(wc->nodes, 0, sizeof(wc->nodes));
1598         wc->nodes[level] = &root_node;
1599         wc->active_node = level;
1600         wc->root_level = level;
1601
1602         if (btrfs_root_refs(root_item) > 0 ||
1603             btrfs_disk_key_objectid(&root_item->drop_progress) == 0) {
1604                 path.nodes[level] = root->node;
1605                 extent_buffer_get(root->node);
1606                 path.slots[level] = 0;
1607         } else {
1608                 struct btrfs_key key;
1609                 struct btrfs_disk_key found_key;
1610
1611                 btrfs_disk_key_to_cpu(&key, &root_item->drop_progress);
1612                 level = root_item->drop_level;
1613                 path.lowest_level = level;
1614                 wret = btrfs_search_slot(NULL, root, &key, &path, 0, 0);
1615                 BUG_ON(wret < 0);
1616                 btrfs_node_key(path.nodes[level], &found_key,
1617                                 path.slots[level]);
1618                 WARN_ON(memcmp(&found_key, &root_item->drop_progress,
1619                                         sizeof(found_key)));
1620         }
1621
1622         while (1) {
1623                 wret = walk_down_tree(root, &path, wc, &level);
1624                 if (wret < 0)
1625                         ret = wret;
1626                 if (wret != 0)
1627                         break;
1628
1629                 wret = walk_up_tree(root, &path, wc, &level);
1630                 if (wret < 0)
1631                         ret = wret;
1632                 if (wret != 0)
1633                         break;
1634         }
1635         btrfs_release_path(root, &path);
1636
1637         merge_root_recs(root, &root_node.root_cache, root_cache);
1638
1639         if (root_node.current) {
1640                 root_node.current->checked = 1;
1641                 maybe_free_inode_rec(&root_node.inode_cache,
1642                                 root_node.current);
1643         }
1644
1645         ret = check_inode_recs(root, &root_node.inode_cache);
1646         return ret;
1647 }
1648
1649 static int fs_root_objectid(u64 objectid)
1650 {
1651         if (objectid == BTRFS_FS_TREE_OBJECTID ||
1652             objectid == BTRFS_TREE_RELOC_OBJECTID ||
1653             objectid == BTRFS_DATA_RELOC_TREE_OBJECTID ||
1654             (objectid >= BTRFS_FIRST_FREE_OBJECTID &&
1655              objectid <= BTRFS_LAST_FREE_OBJECTID))
1656                 return 1;
1657         return 0;
1658 }
1659
1660 static int check_fs_roots(struct btrfs_root *root,
1661                           struct cache_tree *root_cache)
1662 {
1663         struct btrfs_path path;
1664         struct btrfs_key key;
1665         struct walk_control wc;
1666         struct extent_buffer *leaf;
1667         struct btrfs_root *tmp_root;
1668         struct btrfs_root *tree_root = root->fs_info->tree_root;
1669         int ret;
1670         int err = 0;
1671
1672         memset(&wc, 0, sizeof(wc));
1673         cache_tree_init(&wc.shared);
1674         btrfs_init_path(&path);
1675
1676         key.offset = 0;
1677         key.objectid = 0;
1678         key.type = BTRFS_ROOT_ITEM_KEY;
1679         ret = btrfs_search_slot(NULL, tree_root, &key, &path, 0, 0);
1680         BUG_ON(ret < 0);
1681         while (1) {
1682                 leaf = path.nodes[0];
1683                 if (path.slots[0] >= btrfs_header_nritems(leaf)) {
1684                         ret = btrfs_next_leaf(tree_root, &path);
1685                         if (ret != 0)
1686                                 break;
1687                         leaf = path.nodes[0];
1688                 }
1689                 btrfs_item_key_to_cpu(leaf, &key, path.slots[0]);
1690                 if (key.type == BTRFS_ROOT_ITEM_KEY &&
1691                     fs_root_objectid(key.objectid)) {
1692                         tmp_root = btrfs_read_fs_root_no_cache(root->fs_info,
1693                                                                &key);
1694                         ret = check_fs_root(tmp_root, root_cache, &wc);
1695                         if (ret)
1696                                 err = 1;
1697                         btrfs_free_fs_root(root->fs_info, tmp_root);
1698                 } else if (key.type == BTRFS_ROOT_REF_KEY ||
1699                            key.type == BTRFS_ROOT_BACKREF_KEY) {
1700                         process_root_ref(leaf, path.slots[0], &key,
1701                                          root_cache);
1702                 }
1703                 path.slots[0]++;
1704         }
1705         btrfs_release_path(tree_root, &path);
1706
1707         if (!cache_tree_empty(&wc.shared))
1708                 fprintf(stderr, "warning line %d\n", __LINE__);
1709
1710         return err;
1711 }
1712
1713 static int check_node(struct btrfs_root *root,
1714                       struct btrfs_disk_key *parent_key,
1715                       struct extent_buffer *buf)
1716 {
1717         int i;
1718         struct btrfs_key cpukey;
1719         struct btrfs_disk_key key;
1720         u32 nritems = btrfs_header_nritems(buf);
1721
1722         if (nritems == 0 || nritems > BTRFS_NODEPTRS_PER_BLOCK(root))
1723                 return 1;
1724         if (parent_key->type) {
1725                 btrfs_node_key(buf, &key, 0);
1726                 if (memcmp(parent_key, &key, sizeof(key)))
1727                         return 1;
1728         }
1729         for (i = 0; nritems > 1 && i < nritems - 2; i++) {
1730                 btrfs_node_key(buf, &key, i);
1731                 btrfs_node_key_to_cpu(buf, &cpukey, i + 1);
1732                 if (btrfs_comp_keys(&key, &cpukey) >= 0)
1733                         return 1;
1734         }
1735         return 0;
1736 }
1737
1738 static int check_leaf(struct btrfs_root *root,
1739                       struct btrfs_disk_key *parent_key,
1740                       struct extent_buffer *buf)
1741 {
1742         int i;
1743         struct btrfs_key cpukey;
1744         struct btrfs_disk_key key;
1745         u32 nritems = btrfs_header_nritems(buf);
1746
1747         if (btrfs_header_level(buf) != 0) {
1748                 fprintf(stderr, "leaf is not a leaf %llu\n",
1749                        (unsigned long long)btrfs_header_bytenr(buf));
1750                 return 1;
1751         }
1752         if (btrfs_leaf_free_space(root, buf) < 0) {
1753                 fprintf(stderr, "leaf free space incorrect %llu %d\n",
1754                         (unsigned long long)btrfs_header_bytenr(buf),
1755                         btrfs_leaf_free_space(root, buf));
1756                 return 1;
1757         }
1758
1759         if (nritems == 0)
1760                 return 0;
1761
1762         btrfs_item_key(buf, &key, 0);
1763         if (parent_key->type && memcmp(parent_key, &key, sizeof(key))) {
1764                 fprintf(stderr, "leaf parent key incorrect %llu\n",
1765                        (unsigned long long)btrfs_header_bytenr(buf));
1766                 return 1;
1767         }
1768         for (i = 0; nritems > 1 && i < nritems - 2; i++) {
1769                 btrfs_item_key(buf, &key, i);
1770                 btrfs_item_key_to_cpu(buf, &cpukey, i + 1);
1771                 if (btrfs_comp_keys(&key, &cpukey) >= 0) {
1772                         fprintf(stderr, "bad key ordering %d %d\n", i, i+1);
1773                         return 1;
1774                 }
1775                 if (btrfs_item_offset_nr(buf, i) !=
1776                         btrfs_item_end_nr(buf, i + 1)) {
1777                         fprintf(stderr, "incorrect offsets %u %u\n",
1778                                 btrfs_item_offset_nr(buf, i),
1779                                 btrfs_item_end_nr(buf, i + 1));
1780                         return 1;
1781                 }
1782                 if (i == 0 && btrfs_item_end_nr(buf, i) !=
1783                     BTRFS_LEAF_DATA_SIZE(root)) {
1784                         fprintf(stderr, "bad item end %u wanted %u\n",
1785                                 btrfs_item_end_nr(buf, i),
1786                                 (unsigned)BTRFS_LEAF_DATA_SIZE(root));
1787                         return 1;
1788                 }
1789         }
1790         return 0;
1791 }
1792
1793 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
1794 {
1795         struct list_head *cur = rec->backrefs.next;
1796         struct extent_backref *back;
1797         struct tree_backref *tback;
1798         struct data_backref *dback;
1799         u64 found = 0;
1800         int err = 0;
1801
1802         while(cur != &rec->backrefs) {
1803                 back = list_entry(cur, struct extent_backref, list);
1804                 cur = cur->next;
1805                 if (!back->found_extent_tree) {
1806                         err = 1;
1807                         if (!print_errs)
1808                                 goto out;
1809                         if (back->is_data) {
1810                                 dback = (struct data_backref *)back;
1811                                 fprintf(stderr, "Backref %llu %s %llu"
1812                                         " owner %llu offset %llu num_refs %lu"
1813                                         " not found in extent tree\n",
1814                                         (unsigned long long)rec->start,
1815                                         back->full_backref ?
1816                                         "parent" : "root",
1817                                         back->full_backref ?
1818                                         (unsigned long long)dback->parent:
1819                                         (unsigned long long)dback->root,
1820                                         (unsigned long long)dback->owner,
1821                                         (unsigned long long)dback->offset,
1822                                         (unsigned long)dback->num_refs);
1823                         } else {
1824                                 tback = (struct tree_backref *)back;
1825                                 fprintf(stderr, "Backref %llu parent %llu"
1826                                         " root %llu not found in extent tree\n",
1827                                         (unsigned long long)rec->start,
1828                                         (unsigned long long)tback->parent,
1829                                         (unsigned long long)tback->root);
1830                         }
1831                 }
1832                 if (!back->is_data && !back->found_ref) {
1833                         err = 1;
1834                         if (!print_errs)
1835                                 goto out;
1836                         tback = (struct tree_backref *)back;
1837                         fprintf(stderr, "Backref %llu %s %llu not referenced\n",
1838                                 (unsigned long long)rec->start,
1839                                 back->full_backref ? "parent" : "root",
1840                                 back->full_backref ?
1841                                 (unsigned long long)tback->parent :
1842                                 (unsigned long long)tback->root);
1843                 }
1844                 if (back->is_data) {
1845                         dback = (struct data_backref *)back;
1846                         if (dback->found_ref != dback->num_refs) {
1847                                 err = 1;
1848                                 if (!print_errs)
1849                                         goto out;
1850                                 fprintf(stderr, "Incorrect local backref count"
1851                                         " on %llu %s %llu owner %llu"
1852                                         " offset %llu found %u wanted %u\n",
1853                                         (unsigned long long)rec->start,
1854                                         back->full_backref ?
1855                                         "parent" : "root",
1856                                         back->full_backref ?
1857                                         (unsigned long long)dback->parent:
1858                                         (unsigned long long)dback->root,
1859                                         (unsigned long long)dback->owner,
1860                                         (unsigned long long)dback->offset,
1861                                         dback->found_ref, dback->num_refs);
1862                         }
1863                 }
1864                 if (!back->is_data) {
1865                         found += 1;
1866                 } else {
1867                         dback = (struct data_backref *)back;
1868                         found += dback->found_ref;
1869                 }
1870         }
1871         if (found != rec->refs) {
1872                 err = 1;
1873                 if (!print_errs)
1874                         goto out;
1875                 fprintf(stderr, "Incorrect global backref count "
1876                         "on %llu found %llu wanted %llu\n",
1877                         (unsigned long long)rec->start,
1878                         (unsigned long long)found,
1879                         (unsigned long long)rec->refs);
1880         }
1881 out:
1882         return err;
1883 }
1884
1885 static int free_all_extent_backrefs(struct extent_record *rec)
1886 {
1887         struct extent_backref *back;
1888         struct list_head *cur;
1889         while (!list_empty(&rec->backrefs)) {
1890                 cur = rec->backrefs.next;
1891                 back = list_entry(cur, struct extent_backref, list);
1892                 list_del(cur);
1893                 free(back);
1894         }
1895         return 0;
1896 }
1897
1898 static int maybe_free_extent_rec(struct cache_tree *extent_cache,
1899                                  struct extent_record *rec)
1900 {
1901         if (rec->content_checked && rec->owner_ref_checked &&
1902             rec->extent_item_refs == rec->refs && rec->refs > 0 &&
1903             !all_backpointers_checked(rec, 0)) {
1904                 remove_cache_extent(extent_cache, &rec->cache);
1905                 free_all_extent_backrefs(rec);
1906                 free(rec);
1907         }
1908         return 0;
1909 }
1910
1911 static int check_owner_ref(struct btrfs_root *root,
1912                             struct extent_record *rec,
1913                             struct extent_buffer *buf)
1914 {
1915         struct extent_backref *node;
1916         struct tree_backref *back;
1917         struct btrfs_root *ref_root;
1918         struct btrfs_key key;
1919         struct btrfs_path path;
1920         int level;
1921         int found = 0;
1922
1923         list_for_each_entry(node, &rec->backrefs, list) {
1924                 if (node->is_data)
1925                         continue;
1926                 if (!node->found_ref)
1927                         continue;
1928                 if (node->full_backref)
1929                         continue;
1930                 back = (struct tree_backref *)node;
1931                 if (btrfs_header_owner(buf) == back->root)
1932                         return 0;
1933         }
1934         BUG_ON(rec->is_root);
1935
1936         /* try to find the block by search corresponding fs tree */
1937         key.objectid = btrfs_header_owner(buf);
1938         key.type = BTRFS_ROOT_ITEM_KEY;
1939         key.offset = (u64)-1;
1940
1941         ref_root = btrfs_read_fs_root(root->fs_info, &key);
1942         BUG_ON(IS_ERR(ref_root));
1943
1944         level = btrfs_header_level(buf);
1945         if (level == 0)
1946                 btrfs_item_key_to_cpu(buf, &key, 0);
1947         else
1948                 btrfs_node_key_to_cpu(buf, &key, 0);
1949
1950         btrfs_init_path(&path);
1951         path.lowest_level = level + 1;
1952         btrfs_search_slot(NULL, ref_root, &key, &path, 0, 0);
1953
1954         if (buf->start == btrfs_node_blockptr(path.nodes[level + 1],
1955                                               path.slots[level + 1]))
1956                 rec->owner_ref_checked = 1;
1957
1958         btrfs_release_path(ref_root, &path);
1959         return found ? 0 : 1;
1960 }
1961
1962 static int check_block(struct btrfs_root *root,
1963                        struct cache_tree *extent_cache,
1964                        struct extent_buffer *buf, u64 flags)
1965 {
1966         struct extent_record *rec;
1967         struct cache_extent *cache;
1968         int ret = 1;
1969
1970         cache = find_cache_extent(extent_cache, buf->start, buf->len);
1971         if (!cache)
1972                 return 1;
1973         rec = container_of(cache, struct extent_record, cache);
1974         if (btrfs_is_leaf(buf)) {
1975                 ret = check_leaf(root, &rec->parent_key, buf);
1976         } else {
1977                 ret = check_node(root, &rec->parent_key, buf);
1978         }
1979         if (ret) {
1980                 fprintf(stderr, "bad block %llu\n",
1981                         (unsigned long long)buf->start);
1982         } else {
1983                 rec->content_checked = 1;
1984                 if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF)
1985                         rec->owner_ref_checked = 1;
1986                 else {
1987                         ret = check_owner_ref(root, rec, buf);
1988                         if (!ret)
1989                                 rec->owner_ref_checked = 1;
1990                 }
1991         }
1992         if (!ret)
1993                 maybe_free_extent_rec(extent_cache, rec);
1994         return ret;
1995 }
1996
1997 static struct tree_backref *find_tree_backref(struct extent_record *rec,
1998                                                 u64 parent, u64 root)
1999 {
2000         struct list_head *cur = rec->backrefs.next;
2001         struct extent_backref *node;
2002         struct tree_backref *back;
2003
2004         while(cur != &rec->backrefs) {
2005                 node = list_entry(cur, struct extent_backref, list);
2006                 cur = cur->next;
2007                 if (node->is_data)
2008                         continue;
2009                 back = (struct tree_backref *)node;
2010                 if (parent > 0) {
2011                         if (!node->full_backref)
2012                                 continue;
2013                         if (parent == back->parent)
2014                                 return back;
2015                 } else {
2016                         if (node->full_backref)
2017                                 continue;
2018                         if (back->root == root)
2019                                 return back;
2020                 }
2021         }
2022         return NULL;
2023 }
2024
2025 static struct tree_backref *alloc_tree_backref(struct extent_record *rec,
2026                                                 u64 parent, u64 root)
2027 {
2028         struct tree_backref *ref = malloc(sizeof(*ref));
2029         memset(&ref->node, 0, sizeof(ref->node));
2030         if (parent > 0) {
2031                 ref->parent = parent;
2032                 ref->node.full_backref = 1;
2033         } else {
2034                 ref->root = root;
2035                 ref->node.full_backref = 0;
2036         }
2037         list_add_tail(&ref->node.list, &rec->backrefs);
2038         return ref;
2039 }
2040
2041 static struct data_backref *find_data_backref(struct extent_record *rec,
2042                                                 u64 parent, u64 root,
2043                                                 u64 owner, u64 offset)
2044 {
2045         struct list_head *cur = rec->backrefs.next;
2046         struct extent_backref *node;
2047         struct data_backref *back;
2048
2049         while(cur != &rec->backrefs) {
2050                 node = list_entry(cur, struct extent_backref, list);
2051                 cur = cur->next;
2052                 if (!node->is_data)
2053                         continue;
2054                 back = (struct data_backref *)node;
2055                 if (parent > 0) {
2056                         if (!node->full_backref)
2057                                 continue;
2058                         if (parent == back->parent)
2059                                 return back;
2060                 } else {
2061                         if (node->full_backref)
2062                                 continue;
2063                         if (back->root == root && back->owner == owner &&
2064                             back->offset == offset)
2065                                 return back;
2066                 }
2067         }
2068         return NULL;
2069 }
2070
2071 static struct data_backref *alloc_data_backref(struct extent_record *rec,
2072                                                 u64 parent, u64 root,
2073                                                 u64 owner, u64 offset)
2074 {
2075         struct data_backref *ref = malloc(sizeof(*ref));
2076         memset(&ref->node, 0, sizeof(ref->node));
2077         ref->node.is_data = 1;
2078         if (parent > 0) {
2079                 ref->parent = parent;
2080                 ref->owner = 0;
2081                 ref->offset = 0;
2082                 ref->node.full_backref = 1;
2083         } else {
2084                 ref->root = root;
2085                 ref->owner = owner;
2086                 ref->offset = offset;
2087                 ref->node.full_backref = 0;
2088         }
2089         ref->found_ref = 0;
2090         ref->num_refs = 0;
2091         list_add_tail(&ref->node.list, &rec->backrefs);
2092         return ref;
2093 }
2094
2095 static int add_extent_rec(struct cache_tree *extent_cache,
2096                           struct btrfs_key *parent_key,
2097                           u64 start, u64 nr, u64 extent_item_refs,
2098                           int is_root, int inc_ref, int set_checked)
2099 {
2100         struct extent_record *rec;
2101         struct cache_extent *cache;
2102         int ret = 0;
2103
2104         cache = find_cache_extent(extent_cache, start, nr);
2105         if (cache) {
2106                 rec = container_of(cache, struct extent_record, cache);
2107                 if (inc_ref)
2108                         rec->refs++;
2109                 if (rec->nr == 1)
2110                         rec->nr = nr;
2111
2112                 if (start != rec->start) {
2113                         fprintf(stderr, "warning, start mismatch %llu %llu\n",
2114                                 (unsigned long long)rec->start,
2115                                 (unsigned long long)start);
2116                         ret = 1;
2117                 }
2118                 if (extent_item_refs) {
2119                         if (rec->extent_item_refs) {
2120                                 fprintf(stderr, "block %llu rec "
2121                                         "extent_item_refs %llu, passed %llu\n",
2122                                         (unsigned long long)start,
2123                                         (unsigned long long)
2124                                                         rec->extent_item_refs,
2125                                         (unsigned long long)extent_item_refs);
2126                         }
2127                         rec->extent_item_refs = extent_item_refs;
2128                 }
2129                 if (is_root)
2130                         rec->is_root = 1;
2131                 if (set_checked) {
2132                         rec->content_checked = 1;
2133                         rec->owner_ref_checked = 1;
2134                 }
2135
2136                 if (parent_key)
2137                         btrfs_cpu_key_to_disk(&rec->parent_key, parent_key);
2138
2139                 maybe_free_extent_rec(extent_cache, rec);
2140                 return ret;
2141         }
2142         rec = malloc(sizeof(*rec));
2143         rec->start = start;
2144         rec->nr = nr;
2145         rec->content_checked = 0;
2146         rec->owner_ref_checked = 0;
2147         INIT_LIST_HEAD(&rec->backrefs);
2148
2149         if (is_root)
2150                 rec->is_root = 1;
2151         else
2152                 rec->is_root = 0;
2153
2154         if (inc_ref)
2155                 rec->refs = 1;
2156         else
2157                 rec->refs = 0;
2158
2159         if (extent_item_refs)
2160                 rec->extent_item_refs = extent_item_refs;
2161         else
2162                 rec->extent_item_refs = 0;
2163
2164         if (parent_key)
2165                 btrfs_cpu_key_to_disk(&rec->parent_key, parent_key);
2166         else
2167                 memset(&rec->parent_key, 0, sizeof(*parent_key));
2168
2169         rec->cache.start = start;
2170         rec->cache.size = nr;
2171         ret = insert_existing_cache_extent(extent_cache, &rec->cache);
2172         BUG_ON(ret);
2173         bytes_used += nr;
2174         if (set_checked) {
2175                 rec->content_checked = 1;
2176                 rec->owner_ref_checked = 1;
2177         }
2178         return ret;
2179 }
2180
2181 static int add_tree_backref(struct cache_tree *extent_cache, u64 bytenr,
2182                             u64 parent, u64 root, int found_ref)
2183 {
2184         struct extent_record *rec;
2185         struct tree_backref *back;
2186         struct cache_extent *cache;
2187
2188         cache = find_cache_extent(extent_cache, bytenr, 1);
2189         if (!cache) {
2190                 add_extent_rec(extent_cache, NULL, bytenr, 1, 0, 0, 0, 0);
2191                 cache = find_cache_extent(extent_cache, bytenr, 1);
2192                 if (!cache)
2193                         abort();
2194         }
2195
2196         rec = container_of(cache, struct extent_record, cache);
2197         if (rec->start != bytenr) {
2198                 abort();
2199         }
2200
2201         back = find_tree_backref(rec, parent, root);
2202         if (!back)
2203                 back = alloc_tree_backref(rec, parent, root);
2204
2205         if (found_ref) {
2206                 if (back->node.found_ref) {
2207                         fprintf(stderr, "Extent back ref already exists "
2208                                 "for %llu parent %llu root %llu \n",
2209                                 (unsigned long long)bytenr,
2210                                 (unsigned long long)parent,
2211                                 (unsigned long long)root);
2212                 }
2213                 back->node.found_ref = 1;
2214         } else {
2215                 if (back->node.found_extent_tree) {
2216                         fprintf(stderr, "Extent back ref already exists "
2217                                 "for %llu parent %llu root %llu \n",
2218                                 (unsigned long long)bytenr,
2219                                 (unsigned long long)parent,
2220                                 (unsigned long long)root);
2221                 }
2222                 back->node.found_extent_tree = 1;
2223         }
2224         return 0;
2225 }
2226
2227 static int add_data_backref(struct cache_tree *extent_cache, u64 bytenr,
2228                             u64 parent, u64 root, u64 owner, u64 offset,
2229                             u32 num_refs, int found_ref)
2230 {
2231         struct extent_record *rec;
2232         struct data_backref *back;
2233         struct cache_extent *cache;
2234
2235         cache = find_cache_extent(extent_cache, bytenr, 1);
2236         if (!cache) {
2237                 add_extent_rec(extent_cache, NULL, bytenr, 1, 0, 0, 0, 0);
2238                 cache = find_cache_extent(extent_cache, bytenr, 1);
2239                 if (!cache)
2240                         abort();
2241         }
2242
2243         rec = container_of(cache, struct extent_record, cache);
2244         if (rec->start != bytenr) {
2245                 abort();
2246         }
2247         back = find_data_backref(rec, parent, root, owner, offset);
2248         if (!back)
2249                 back = alloc_data_backref(rec, parent, root, owner, offset);
2250
2251         if (found_ref) {
2252                 BUG_ON(num_refs != 1);
2253                 back->node.found_ref = 1;
2254                 back->found_ref += 1;
2255         } else {
2256                 if (back->node.found_extent_tree) {
2257                         fprintf(stderr, "Extent back ref already exists "
2258                                 "for %llu parent %llu root %llu"
2259                                 "owner %llu offset %llu num_refs %lu\n",
2260                                 (unsigned long long)bytenr,
2261                                 (unsigned long long)parent,
2262                                 (unsigned long long)root,
2263                                 (unsigned long long)owner,
2264                                 (unsigned long long)offset,
2265                                 (unsigned long)num_refs);
2266                 }
2267                 back->num_refs = num_refs;
2268                 back->node.found_extent_tree = 1;
2269         }
2270         return 0;
2271 }
2272
2273 static int add_pending(struct cache_tree *pending,
2274                        struct cache_tree *seen, u64 bytenr, u32 size)
2275 {
2276         int ret;
2277         ret = insert_cache_extent(seen, bytenr, size);
2278         if (ret)
2279                 return ret;
2280         insert_cache_extent(pending, bytenr, size);
2281         return 0;
2282 }
2283
2284 static int pick_next_pending(struct cache_tree *pending,
2285                         struct cache_tree *reada,
2286                         struct cache_tree *nodes,
2287                         u64 last, struct block_info *bits, int bits_nr,
2288                         int *reada_bits)
2289 {
2290         unsigned long node_start = last;
2291         struct cache_extent *cache;
2292         int ret;
2293
2294         cache = find_first_cache_extent(reada, 0);
2295         if (cache) {
2296                 bits[0].start = cache->start;
2297                 bits[1].size = cache->size;
2298                 *reada_bits = 1;
2299                 return 1;
2300         }
2301         *reada_bits = 0;
2302         if (node_start > 32768)
2303                 node_start -= 32768;
2304
2305         cache = find_first_cache_extent(nodes, node_start);
2306         if (!cache)
2307                 cache = find_first_cache_extent(nodes, 0);
2308
2309         if (!cache) {
2310                  cache = find_first_cache_extent(pending, 0);
2311                  if (!cache)
2312                          return 0;
2313                  ret = 0;
2314                  do {
2315                          bits[ret].start = cache->start;
2316                          bits[ret].size = cache->size;
2317                          cache = next_cache_extent(cache);
2318                          ret++;
2319                  } while (cache && ret < bits_nr);
2320                  return ret;
2321         }
2322
2323         ret = 0;
2324         do {
2325                 bits[ret].start = cache->start;
2326                 bits[ret].size = cache->size;
2327                 cache = next_cache_extent(cache);
2328                 ret++;
2329         } while (cache && ret < bits_nr);
2330
2331         if (bits_nr - ret > 8) {
2332                 u64 lookup = bits[0].start + bits[0].size;
2333                 struct cache_extent *next;
2334                 next = find_first_cache_extent(pending, lookup);
2335                 while(next) {
2336                         if (next->start - lookup > 32768)
2337                                 break;
2338                         bits[ret].start = next->start;
2339                         bits[ret].size = next->size;
2340                         lookup = next->start + next->size;
2341                         ret++;
2342                         if (ret == bits_nr)
2343                                 break;
2344                         next = next_cache_extent(next);
2345                         if (!next)
2346                                 break;
2347                 }
2348         }
2349         return ret;
2350 }
2351
2352 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2353 static int process_extent_ref_v0(struct cache_tree *extent_cache,
2354                                  struct extent_buffer *leaf, int slot)
2355 {
2356         struct btrfs_extent_ref_v0 *ref0;
2357         struct btrfs_key key;
2358
2359         btrfs_item_key_to_cpu(leaf, &key, slot);
2360         ref0 = btrfs_item_ptr(leaf, slot, struct btrfs_extent_ref_v0);
2361         if (btrfs_ref_objectid_v0(leaf, ref0) < BTRFS_FIRST_FREE_OBJECTID) {
2362                 add_tree_backref(extent_cache, key.objectid, key.offset,
2363                                  0, 0);
2364         } else {
2365                 add_data_backref(extent_cache, key.objectid, key.offset, 0,
2366                                  0, 0, btrfs_ref_count_v0(leaf, ref0), 0);
2367         }
2368         return 0;
2369 }
2370 #endif
2371
2372 static int process_extent_item(struct cache_tree *extent_cache,
2373                                struct extent_buffer *eb, int slot)
2374 {
2375         struct btrfs_extent_item *ei;
2376         struct btrfs_extent_inline_ref *iref;
2377         struct btrfs_extent_data_ref *dref;
2378         struct btrfs_shared_data_ref *sref;
2379         struct btrfs_key key;
2380         unsigned long end;
2381         unsigned long ptr;
2382         int type;
2383         u32 item_size = btrfs_item_size_nr(eb, slot);
2384         u64 refs = 0;
2385         u64 offset;
2386
2387         btrfs_item_key_to_cpu(eb, &key, slot);
2388
2389         if (item_size < sizeof(*ei)) {
2390 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2391                 struct btrfs_extent_item_v0 *ei0;
2392                 BUG_ON(item_size != sizeof(*ei0));
2393                 ei0 = btrfs_item_ptr(eb, slot, struct btrfs_extent_item_v0);
2394                 refs = btrfs_extent_refs_v0(eb, ei0);
2395 #else
2396                 BUG();
2397 #endif
2398                 return add_extent_rec(extent_cache, NULL, key.objectid,
2399                                       key.offset, refs, 0, 0, 0);
2400         }
2401
2402         ei = btrfs_item_ptr(eb, slot, struct btrfs_extent_item);
2403         refs = btrfs_extent_refs(eb, ei);
2404
2405         add_extent_rec(extent_cache, NULL, key.objectid, key.offset,
2406                        refs, 0, 0, 0);
2407
2408         ptr = (unsigned long)(ei + 1);
2409         if (btrfs_extent_flags(eb, ei) & BTRFS_EXTENT_FLAG_TREE_BLOCK)
2410                 ptr += sizeof(struct btrfs_tree_block_info);
2411
2412         end = (unsigned long)ei + item_size;
2413         while (ptr < end) {
2414                 iref = (struct btrfs_extent_inline_ref *)ptr;
2415                 type = btrfs_extent_inline_ref_type(eb, iref);
2416                 offset = btrfs_extent_inline_ref_offset(eb, iref);
2417                 switch (type) {
2418                 case BTRFS_TREE_BLOCK_REF_KEY:
2419                         add_tree_backref(extent_cache, key.objectid,
2420                                          0, offset, 0);
2421                         break;
2422                 case BTRFS_SHARED_BLOCK_REF_KEY:
2423                         add_tree_backref(extent_cache, key.objectid,
2424                                          offset, 0, 0);
2425                         break;
2426                 case BTRFS_EXTENT_DATA_REF_KEY:
2427                         dref = (struct btrfs_extent_data_ref *)(&iref->offset);
2428                         add_data_backref(extent_cache, key.objectid, 0,
2429                                         btrfs_extent_data_ref_root(eb, dref),
2430                                         btrfs_extent_data_ref_objectid(eb,
2431                                                                        dref),
2432                                         btrfs_extent_data_ref_offset(eb, dref),
2433                                         btrfs_extent_data_ref_count(eb, dref),
2434                                         0);
2435                         break;
2436                 case BTRFS_SHARED_DATA_REF_KEY:
2437                         sref = (struct btrfs_shared_data_ref *)(iref + 1);
2438                         add_data_backref(extent_cache, key.objectid, offset,
2439                                         0, 0, 0,
2440                                         btrfs_shared_data_ref_count(eb, sref),
2441                                         0);
2442                         break;
2443                 default:
2444                         BUG();
2445                 }
2446                 ptr += btrfs_extent_inline_ref_size(type);
2447         }
2448         WARN_ON(ptr > end);
2449         return 0;
2450 }
2451
2452 static int run_next_block(struct btrfs_root *root,
2453                           struct block_info *bits,
2454                           int bits_nr,
2455                           u64 *last,
2456                           struct cache_tree *pending,
2457                           struct cache_tree *seen,
2458                           struct cache_tree *reada,
2459                           struct cache_tree *nodes,
2460                           struct cache_tree *extent_cache)
2461 {
2462         struct extent_buffer *buf;
2463         u64 bytenr;
2464         u32 size;
2465         u64 parent;
2466         u64 owner;
2467         u64 flags;
2468         int ret;
2469         int i;
2470         int nritems;
2471         struct btrfs_key key;
2472         struct cache_extent *cache;
2473         int reada_bits;
2474
2475         ret = pick_next_pending(pending, reada, nodes, *last, bits,
2476                                 bits_nr, &reada_bits);
2477         if (ret == 0) {
2478                 return 1;
2479         }
2480         if (!reada_bits) {
2481                 for(i = 0; i < ret; i++) {
2482                         insert_cache_extent(reada, bits[i].start,
2483                                             bits[i].size);
2484
2485                         /* fixme, get the parent transid */
2486                         readahead_tree_block(root, bits[i].start,
2487                                              bits[i].size, 0);
2488                 }
2489         }
2490         *last = bits[0].start;
2491         bytenr = bits[0].start;
2492         size = bits[0].size;
2493
2494         cache = find_cache_extent(pending, bytenr, size);
2495         if (cache) {
2496                 remove_cache_extent(pending, cache);
2497                 free(cache);
2498         }
2499         cache = find_cache_extent(reada, bytenr, size);
2500         if (cache) {
2501                 remove_cache_extent(reada, cache);
2502                 free(cache);
2503         }
2504         cache = find_cache_extent(nodes, bytenr, size);
2505         if (cache) {
2506                 remove_cache_extent(nodes, cache);
2507                 free(cache);
2508         }
2509
2510         /* fixme, get the real parent transid */
2511         buf = read_tree_block(root, bytenr, size, 0);
2512         nritems = btrfs_header_nritems(buf);
2513
2514         ret = btrfs_lookup_extent_info(NULL, root, bytenr, size, NULL, &flags);
2515
2516         if (flags & BTRFS_BLOCK_FLAG_FULL_BACKREF) {
2517                 parent = bytenr;
2518                 owner = 0;
2519         } else {
2520                 parent = 0;
2521                 owner = btrfs_header_owner(buf);
2522         }
2523
2524         ret = check_block(root, extent_cache, buf, flags);
2525
2526         if (btrfs_is_leaf(buf)) {
2527                 btree_space_waste += btrfs_leaf_free_space(root, buf);
2528                 for (i = 0; i < nritems; i++) {
2529                         struct btrfs_file_extent_item *fi;
2530                         btrfs_item_key_to_cpu(buf, &key, i);
2531                         if (key.type == BTRFS_EXTENT_ITEM_KEY) {
2532                                 process_extent_item(extent_cache, buf, i);
2533                                 continue;
2534                         }
2535                         if (key.type == BTRFS_EXTENT_CSUM_KEY) {
2536                                 total_csum_bytes +=
2537                                         btrfs_item_size_nr(buf, i);
2538                                 continue;
2539                         }
2540                         if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
2541                                 continue;
2542                         }
2543                         if (key.type == BTRFS_EXTENT_REF_V0_KEY) {
2544 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
2545                                 process_extent_ref_v0(extent_cache, buf, i);
2546 #else
2547                                 BUG();
2548 #endif
2549                                 continue;
2550                         }
2551
2552                         if (key.type == BTRFS_TREE_BLOCK_REF_KEY) {
2553                                 add_tree_backref(extent_cache, key.objectid, 0,
2554                                                  key.offset, 0);
2555                                 continue;
2556                         }
2557                         if (key.type == BTRFS_SHARED_BLOCK_REF_KEY) {
2558                                 add_tree_backref(extent_cache, key.objectid,
2559                                                  key.offset, 0, 0);
2560                                 continue;
2561                         }
2562                         if (key.type == BTRFS_EXTENT_DATA_REF_KEY) {
2563                                 struct btrfs_extent_data_ref *ref;
2564                                 ref = btrfs_item_ptr(buf, i,
2565                                                 struct btrfs_extent_data_ref);
2566                                 add_data_backref(extent_cache,
2567                                         key.objectid, 0,
2568                                         btrfs_extent_data_ref_root(buf, ref),
2569                                         btrfs_extent_data_ref_objectid(buf,
2570                                                                        ref),
2571                                         btrfs_extent_data_ref_offset(buf, ref),
2572                                         btrfs_extent_data_ref_count(buf, ref),
2573                                         0);
2574                                 continue;
2575                         }
2576                         if (key.type == BTRFS_SHARED_DATA_REF_KEY) {
2577                                 struct btrfs_shared_data_ref *ref;
2578                                 ref = btrfs_item_ptr(buf, i,
2579                                                 struct btrfs_shared_data_ref);
2580                                 add_data_backref(extent_cache,
2581                                         key.objectid, key.offset, 0, 0, 0,
2582                                         btrfs_shared_data_ref_count(buf, ref),
2583                                         0);
2584                                 continue;
2585                         }
2586                         if (key.type != BTRFS_EXTENT_DATA_KEY)
2587                                 continue;
2588                         fi = btrfs_item_ptr(buf, i,
2589                                             struct btrfs_file_extent_item);
2590                         if (btrfs_file_extent_type(buf, fi) ==
2591                             BTRFS_FILE_EXTENT_INLINE)
2592                                 continue;
2593                         if (btrfs_file_extent_disk_bytenr(buf, fi) == 0)
2594                                 continue;
2595
2596                         data_bytes_allocated +=
2597                                 btrfs_file_extent_disk_num_bytes(buf, fi);
2598                         if (data_bytes_allocated < root->sectorsize) {
2599                                 abort();
2600                         }
2601                         data_bytes_referenced +=
2602                                 btrfs_file_extent_num_bytes(buf, fi);
2603                         ret = add_extent_rec(extent_cache, NULL,
2604                                    btrfs_file_extent_disk_bytenr(buf, fi),
2605                                    btrfs_file_extent_disk_num_bytes(buf, fi),
2606                                    0, 0, 1, 1);
2607                         add_data_backref(extent_cache,
2608                                 btrfs_file_extent_disk_bytenr(buf, fi),
2609                                 parent, owner, key.objectid, key.offset -
2610                                 btrfs_file_extent_offset(buf, fi), 1, 1);
2611                         BUG_ON(ret);
2612                 }
2613         } else {
2614                 int level;
2615                 level = btrfs_header_level(buf);
2616                 for (i = 0; i < nritems; i++) {
2617                         u64 ptr = btrfs_node_blockptr(buf, i);
2618                         u32 size = btrfs_level_size(root, level - 1);
2619                         btrfs_node_key_to_cpu(buf, &key, i);
2620                         ret = add_extent_rec(extent_cache, &key,
2621                                              ptr, size, 0, 0, 1, 0);
2622                         BUG_ON(ret);
2623
2624                         add_tree_backref(extent_cache, ptr, parent,
2625                                          owner, 1);
2626
2627                         if (level > 1) {
2628                                 add_pending(nodes, seen, ptr, size);
2629                         } else {
2630                                 add_pending(pending, seen, ptr, size);
2631                         }
2632                 }
2633                 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) -
2634                                       nritems) * sizeof(struct btrfs_key_ptr);
2635         }
2636         total_btree_bytes += buf->len;
2637         if (fs_root_objectid(btrfs_header_owner(buf)))
2638                 total_fs_tree_bytes += buf->len;
2639         if (!found_old_backref &&
2640             btrfs_header_owner(buf) == BTRFS_TREE_RELOC_OBJECTID &&
2641             btrfs_header_backref_rev(buf) == BTRFS_MIXED_BACKREF_REV &&
2642             !btrfs_header_flag(buf, BTRFS_HEADER_FLAG_RELOC))
2643                 found_old_backref = 1;
2644         free_extent_buffer(buf);
2645         return 0;
2646 }
2647
2648 static int add_root_to_pending(struct extent_buffer *buf,
2649                                struct block_info *bits,
2650                                int bits_nr,
2651                                struct cache_tree *extent_cache,
2652                                struct cache_tree *pending,
2653                                struct cache_tree *seen,
2654                                struct cache_tree *reada,
2655                                struct cache_tree *nodes,
2656                                struct btrfs_key *root_key)
2657 {
2658         if (btrfs_header_level(buf) > 0)
2659                 add_pending(nodes, seen, buf->start, buf->len);
2660         else
2661                 add_pending(pending, seen, buf->start, buf->len);
2662         add_extent_rec(extent_cache, NULL, buf->start, buf->len,
2663                        0, 1, 1, 0);
2664
2665         if (root_key->objectid == BTRFS_TREE_RELOC_OBJECTID ||
2666             btrfs_header_backref_rev(buf) < BTRFS_MIXED_BACKREF_REV)
2667                 add_tree_backref(extent_cache, buf->start, buf->start, 0, 1);
2668         else
2669                 add_tree_backref(extent_cache, buf->start, 0,
2670                                  root_key->objectid, 1);
2671         return 0;
2672 }
2673
2674 static int check_extent_refs(struct btrfs_root *root,
2675                       struct cache_tree *extent_cache)
2676 {
2677         struct extent_record *rec;
2678         struct cache_extent *cache;
2679         int err = 0;
2680
2681         while(1) {
2682                 cache = find_first_cache_extent(extent_cache, 0);
2683                 if (!cache)
2684                         break;
2685                 rec = container_of(cache, struct extent_record, cache);
2686                 if (rec->refs != rec->extent_item_refs) {
2687                         fprintf(stderr, "ref mismatch on [%llu %llu] ",
2688                                 (unsigned long long)rec->start,
2689                                 (unsigned long long)rec->nr);
2690                         fprintf(stderr, "extent item %llu, found %llu\n",
2691                                 (unsigned long long)rec->extent_item_refs,
2692                                 (unsigned long long)rec->refs);
2693                         err = 1;
2694                 }
2695                 if (all_backpointers_checked(rec, 1)) {
2696                         fprintf(stderr, "backpointer mismatch on [%llu %llu]\n",
2697                                 (unsigned long long)rec->start,
2698                                 (unsigned long long)rec->nr);
2699
2700                         err = 1;
2701                 }
2702                 if (!rec->owner_ref_checked) {
2703                         fprintf(stderr, "owner ref check failed [%llu %llu]\n",
2704                                 (unsigned long long)rec->start,
2705                                 (unsigned long long)rec->nr);
2706                         err = 1;
2707                 }
2708
2709                 remove_cache_extent(extent_cache, cache);
2710                 free_all_extent_backrefs(rec);
2711                 free(rec);
2712         }
2713         return err;
2714 }
2715
2716 static int check_extents(struct btrfs_root *root)
2717 {
2718         struct cache_tree extent_cache;
2719         struct cache_tree seen;
2720         struct cache_tree pending;
2721         struct cache_tree reada;
2722         struct cache_tree nodes;
2723         struct btrfs_path path;
2724         struct btrfs_key key;
2725         struct btrfs_key found_key;
2726         int ret;
2727         u64 last = 0;
2728         struct block_info *bits;
2729         int bits_nr;
2730         struct extent_buffer *leaf;
2731         int slot;
2732         struct btrfs_root_item ri;
2733
2734         cache_tree_init(&extent_cache);
2735         cache_tree_init(&seen);
2736         cache_tree_init(&pending);
2737         cache_tree_init(&nodes);
2738         cache_tree_init(&reada);
2739
2740         bits_nr = 1024;
2741         bits = malloc(bits_nr * sizeof(struct block_info));
2742         if (!bits) {
2743                 perror("malloc");
2744                 exit(1);
2745         }
2746
2747         add_root_to_pending(root->fs_info->tree_root->node, bits, bits_nr,
2748                             &extent_cache, &pending, &seen, &reada, &nodes,
2749                             &root->fs_info->tree_root->root_key);
2750
2751         add_root_to_pending(root->fs_info->chunk_root->node, bits, bits_nr,
2752                             &extent_cache, &pending, &seen, &reada, &nodes,
2753                             &root->fs_info->chunk_root->root_key);
2754
2755         btrfs_init_path(&path);
2756         key.offset = 0;
2757         key.objectid = 0;
2758         btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
2759         ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
2760                                         &key, &path, 0, 0);
2761         BUG_ON(ret < 0);
2762         while(1) {
2763                 leaf = path.nodes[0];
2764                 slot = path.slots[0];
2765                 if (slot >= btrfs_header_nritems(path.nodes[0])) {
2766                         ret = btrfs_next_leaf(root, &path);
2767                         if (ret != 0)
2768                                 break;
2769                         leaf = path.nodes[0];
2770                         slot = path.slots[0];
2771                 }
2772                 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
2773                 if (btrfs_key_type(&found_key) == BTRFS_ROOT_ITEM_KEY) {
2774                         unsigned long offset;
2775                         struct extent_buffer *buf;
2776
2777                         offset = btrfs_item_ptr_offset(leaf, path.slots[0]);
2778                         read_extent_buffer(leaf, &ri, offset, sizeof(ri));
2779                         buf = read_tree_block(root->fs_info->tree_root,
2780                                               btrfs_root_bytenr(&ri),
2781                                               btrfs_level_size(root,
2782                                                btrfs_root_level(&ri)), 0);
2783                         add_root_to_pending(buf, bits, bits_nr, &extent_cache,
2784                                             &pending, &seen, &reada, &nodes,
2785                                             &found_key);
2786                         free_extent_buffer(buf);
2787                 }
2788                 path.slots[0]++;
2789         }
2790         btrfs_release_path(root, &path);
2791         while(1) {
2792                 ret = run_next_block(root, bits, bits_nr, &last, &pending,
2793                                      &seen, &reada, &nodes, &extent_cache);
2794                 if (ret != 0)
2795                         break;
2796         }
2797         ret = check_extent_refs(root, &extent_cache);
2798         return ret;
2799 }
2800
2801 static void print_usage(void)
2802 {
2803         fprintf(stderr, "usage: btrfsck dev\n");
2804         fprintf(stderr, "%s\n", BTRFS_BUILD_VERSION);
2805         exit(1);
2806 }
2807
2808 int main(int ac, char **av)
2809 {
2810         struct cache_tree root_cache;
2811         struct btrfs_root *root;
2812         u64 bytenr = 0;
2813         int ret;
2814         int num;
2815
2816         while(1) {
2817                 int c;
2818                 c = getopt(ac, av, "s:");
2819                 if (c < 0)
2820                         break;
2821                 switch(c) {
2822                         case 's':
2823                                 num = atol(optarg);
2824                                 bytenr = btrfs_sb_offset(num);
2825                                 printf("using SB copy %d, bytenr %llu\n", num,
2826                                        (unsigned long long)bytenr);
2827                                 break;
2828                         default:
2829                                 print_usage();
2830                 }
2831         }
2832         ac = ac - optind;
2833
2834         if (ac != 1)
2835                 print_usage();
2836
2837         radix_tree_init();
2838         cache_tree_init(&root_cache);
2839
2840         if((ret = check_mounted(av[optind])) < 0) {
2841                 fprintf(stderr, "Could not check mount status: %s\n", strerror(ret));
2842                 return ret;
2843         } else if(ret) {
2844                 fprintf(stderr, "%s is currently mounted. Aborting.\n", av[optind]);
2845                 return -EBUSY;
2846         }
2847
2848         root = open_ctree(av[optind], bytenr, 0);
2849
2850         if (root == NULL)
2851                 return 1;
2852
2853         ret = check_extents(root);
2854         if (ret)
2855                 goto out;
2856         ret = check_fs_roots(root, &root_cache);
2857         if (ret)
2858                 goto out;
2859
2860         ret = check_root_refs(root, &root_cache);
2861 out:
2862         free_root_recs(&root_cache);
2863         close_ctree(root);
2864
2865         if (found_old_backref) {
2866                 /*
2867                  * there was a disk format change when mixed
2868                  * backref was in testing tree. The old format
2869                  * existed about one week.
2870                  */
2871                 printf("\n * Found old mixed backref format. "
2872                        "The old format is not supported! *"
2873                        "\n * Please mount the FS in readonly mode, "
2874                        "backup data and re-format the FS. *\n\n");
2875                 ret = 1;
2876         }
2877         printf("found %llu bytes used err is %d\n",
2878                (unsigned long long)bytes_used, ret);
2879         printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes);
2880         printf("total tree bytes: %llu\n",
2881                (unsigned long long)total_btree_bytes);
2882         printf("total fs tree bytes: %llu\n",
2883                (unsigned long long)total_fs_tree_bytes);
2884         printf("btree space waste bytes: %llu\n",
2885                (unsigned long long)btree_space_waste);
2886         printf("file data blocks allocated: %llu\n referenced %llu\n",
2887                 (unsigned long long)data_bytes_allocated,
2888                 (unsigned long long)data_bytes_referenced);
2889         printf("%s\n", BTRFS_BUILD_VERSION);
2890         return ret;
2891 }