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 <fcntl.h>
  24 #include "kerncompat.h"
  25 #include "ctree.h"
  26 #include "disk-io.h"
  27 #include "print-tree.h"
  28 #include "transaction.h"
  29 #include "list.h"
  30
  31 static u64 bytes_used = 0;
  32 static u64 total_csum_bytes = 0;
  33 static u64 total_btree_bytes = 0;
  34 static u64 btree_space_waste = 0;
  35 static u64 data_bytes_allocated = 0;
  36 static u64 data_bytes_referenced = 0;
  37
  38 struct extent_backref {
  39         struct list_head list;
  40         u64 root;
  41         u64 generation;
  42         u64 owner;
  43         u64 offset;
  44         int found_extent_tree;
  45         int found_ref;
  46 };
  47
  48 struct extent_record {
  49         struct list_head backrefs;
  50         struct cache_extent cache;
  51         struct btrfs_disk_key parent_key;
  52         u64 start;
  53         u64 nr;
  54         u32 refs;
  55         u32 extent_item_refs;
  56         int checked;
  57 };
  58
  59 struct block_info {
  60         u64 start;
  61         u32 size;
  62 };
  63
  64 static int check_node(struct btrfs_root *root,
  65                       struct btrfs_disk_key *parent_key,
  66                       struct extent_buffer *buf)
  67 {
  68         int i;
  69         struct btrfs_key cpukey;
  70         struct btrfs_disk_key key;
  71         u32 nritems = btrfs_header_nritems(buf);
  72
  73         if (nritems == 0 || nritems > BTRFS_NODEPTRS_PER_BLOCK(root))
  74                 return 1;
  75         if (parent_key->type) {
  76                 btrfs_node_key(buf, &key, 0);
  77                 if (memcmp(parent_key, &key, sizeof(key)))
  78                         return 1;
  79         }
  80         for (i = 0; nritems > 1 && i < nritems - 2; i++) {
  81                 btrfs_node_key(buf, &key, i);
  82                 btrfs_node_key_to_cpu(buf, &cpukey, i + 1);
  83                 if (btrfs_comp_keys(&key, &cpukey) >= 0)
  84                         return 1;
  85         }
  86         return 0;
  87 }
  88
  89 static int check_leaf(struct btrfs_root *root,
  90                       struct btrfs_disk_key *parent_key,
  91                       struct extent_buffer *buf)
  92 {
  93         int i;
  94         struct btrfs_key cpukey;
  95         struct btrfs_disk_key key;
  96         u32 nritems = btrfs_header_nritems(buf);
  97
  98         if (btrfs_header_level(buf) != 0) {
  99                 fprintf(stderr, "leaf is not a leaf %llu\n",
 100                        (unsigned long long)btrfs_header_bytenr(buf));
 101                 return 1;
 102         }
 103         if (btrfs_leaf_free_space(root, buf) < 0) {
 104                 fprintf(stderr, "leaf free space incorrect %llu %d\n",
 105                         (unsigned long long)btrfs_header_bytenr(buf),
 106                         btrfs_leaf_free_space(root, buf));
 107                 return 1;
 108         }
 109
 110         if (nritems == 0)
 111                 return 0;
 112
 113         btrfs_item_key(buf, &key, 0);
 114         if (parent_key->type && memcmp(parent_key, &key, sizeof(key))) {
 115                 fprintf(stderr, "leaf parent key incorrect %llu\n",
 116                        (unsigned long long)btrfs_header_bytenr(buf));
 117                 return 1;
 118         }
 119         for (i = 0; nritems > 1 && i < nritems - 2; i++) {
 120                 btrfs_item_key(buf, &key, i);
 121                 btrfs_item_key_to_cpu(buf, &cpukey, i + 1);
 122                 if (btrfs_comp_keys(&key, &cpukey) >= 0) {
 123                         fprintf(stderr, "bad key ordering %d %d\n", i, i+1);
 124                         return 1;
 125                 }
 126                 if (btrfs_item_offset_nr(buf, i) !=
 127                         btrfs_item_end_nr(buf, i + 1)) {
 128                         fprintf(stderr, "incorrect offsets %u %u\n",
 129                                 btrfs_item_offset_nr(buf, i),
 130                                 btrfs_item_end_nr(buf, i + 1));
 131                         return 1;
 132                 }
 133                 if (i == 0 && btrfs_item_end_nr(buf, i) !=
 134                     BTRFS_LEAF_DATA_SIZE(root)) {
 135                         fprintf(stderr, "bad item end %u wanted %u\n",
 136                                 btrfs_item_end_nr(buf, i),
 137                                 (unsigned)BTRFS_LEAF_DATA_SIZE(root));
 138                         return 1;
 139                 }
 140         }
 141         return 0;
 142 }
 143
 144 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
 145 {
 146         struct list_head *cur = rec->backrefs.next;
 147         struct extent_backref *back;
 148         u32 found = 0;
 149         int err = 0;
 150
 151         while(cur != &rec->backrefs) {
 152                 back = list_entry(cur, struct extent_backref, list);
 153                 cur = cur->next;
 154                 if (!back->found_extent_tree) {
 155                         err = 1;
 156                         if (!print_errs)
 157                                 goto out;
 158                         fprintf(stderr, "Backref %llu [%llu %llu %llu %llu] "
 159                                 "not found in extent tree\n",
 160                                 (unsigned long long)rec->start,
 161                                 (unsigned long long)back->root,
 162                                 (unsigned long long)back->generation,
 163                                 (unsigned long long)back->owner,
 164                                 (unsigned long long)back->offset);
 165                 }
 166                 if (!back->found_ref) {
 167                         err = 1;
 168                         if (!print_errs)
 169                                 goto out;
 170                         fprintf(stderr, "Backref %llu [%llu %llu %llu %llu] "
 171                                 "not referenced\n",
 172                                 (unsigned long long)rec->start,
 173                                 (unsigned long long)back->root,
 174                                 (unsigned long long)back->generation,
 175                                 (unsigned long long)back->owner,
 176                                 (unsigned long long)back->offset);
 177                 }
 178                 found++;
 179         }
 180         if (found != rec->refs) {
 181                 err = 1;
 182                 if (!print_errs)
 183                         goto out;
 184                 fprintf(stderr, "Incorrect backref count on %llu found %u "
 185                         "wanted %u\n", (unsigned long long)rec->start,
 186                         found, rec->refs);
 187         }
 188 out:
 189         return err;
 190 }
 191
 192 static int free_all_backrefs(struct extent_record *rec)
 193 {
 194         struct extent_backref *back;
 195         struct list_head *cur;
 196         while (!list_empty(&rec->backrefs)) {
 197                 cur = rec->backrefs.next;
 198                 back = list_entry(cur, struct extent_backref, list);
 199                 list_del(cur);
 200                 free(back);
 201         }
 202         return 0;
 203 }
 204
 205 static int maybe_free_extent_rec(struct cache_tree *extent_cache,
 206                                  struct extent_record *rec)
 207 {
 208         if (rec->checked && rec->extent_item_refs == rec->refs &&
 209             rec->refs > 0 && !all_backpointers_checked(rec, 0)) {
 210                 remove_cache_extent(extent_cache, &rec->cache);
 211                 free_all_backrefs(rec);
 212                 free(rec);
 213         }
 214         return 0;
 215 }
 216
 217 static int check_block(struct btrfs_root *root,
 218                        struct cache_tree *extent_cache,
 219                        struct extent_buffer *buf)
 220 {
 221         struct extent_record *rec;
 222         struct cache_extent *cache;
 223         int ret = 1;
 224
 225         cache = find_cache_extent(extent_cache, buf->start, buf->len);
 226         if (!cache)
 227                 return 1;
 228         rec = container_of(cache, struct extent_record, cache);
 229         if (btrfs_is_leaf(buf)) {
 230                 ret = check_leaf(root, &rec->parent_key, buf);
 231         } else {
 232                 ret = check_node(root, &rec->parent_key, buf);
 233         }
 234         rec->checked = 1;
 235         if (!ret)
 236                 maybe_free_extent_rec(extent_cache, rec);
 237         return ret;
 238 }
 239
 240 static struct extent_backref *find_backref(struct extent_record *rec,
 241                                            u64 root, u64 gen,
 242                                            u64 owner, u64 owner_offset)
 243 {
 244         struct list_head *cur = rec->backrefs.next;
 245         struct extent_backref *back;
 246
 247         while(cur != &rec->backrefs) {
 248                 back = list_entry(cur, struct extent_backref, list);
 249                 cur = cur->next;
 250                 if (back->root != root || gen != back->generation)
 251                         continue;
 252                 if (owner < BTRFS_FIRST_FREE_OBJECTID)
 253                         return back;
 254                 if (owner != back->owner || owner_offset != back->offset)
 255                         continue;
 256                 return back;
 257         }
 258         return NULL;
 259 }
 260
 261 static struct extent_backref *alloc_backref(struct extent_record *rec,
 262                                             u64 root, u64 gen, u64 owner,
 263                                             u64 owner_offset)
 264 {
 265         struct extent_backref *ref = malloc(sizeof(*ref));
 266         ref->root = root;
 267         ref->generation = gen;
 268         ref->owner = owner;
 269         ref->offset = owner_offset;
 270         ref->found_extent_tree = 0;
 271         ref->found_ref = 0;
 272         list_add_tail(&ref->list, &rec->backrefs);
 273         return ref;
 274 }
 275
 276 static int add_extent_rec(struct cache_tree *extent_cache,
 277                           struct btrfs_disk_key *parent_key,
 278                           u64 ref, u64 start, u64 nr,
 279                           u32 extent_item_refs, int inc_ref, int set_checked)
 280 {
 281         struct extent_record *rec;
 282         struct cache_extent *cache;
 283         int ret = 0;
 284
 285         cache = find_cache_extent(extent_cache, start, nr);
 286         if (cache) {
 287                 rec = container_of(cache, struct extent_record, cache);
 288                 if (inc_ref)
 289                         rec->refs++;
 290                 if (rec->nr == 1)
 291                         rec->nr = nr;
 292
 293                 if (start != rec->start) {
 294                         fprintf(stderr, "warning, start mismatch %llu %llu\n",
 295                                 (unsigned long long)rec->start,
 296                                 (unsigned long long)start);
 297                         ret = 1;
 298                 }
 299                 if (extent_item_refs) {
 300                         if (rec->extent_item_refs) {
 301                                 fprintf(stderr, "block %llu rec "
 302                                         "extent_item_refs %u, passed %u\n",
 303                                         (unsigned long long)start,
 304                                         rec->extent_item_refs,
 305                                         extent_item_refs);
 306                         }
 307                         rec->extent_item_refs = extent_item_refs;
 308                 }
 309                 if (set_checked)
 310                         rec->checked = 1;
 311
 312                 if (parent_key)
 313                         memcpy(&rec->parent_key, parent_key,
 314                                sizeof(*parent_key));
 315
 316                 maybe_free_extent_rec(extent_cache, rec);
 317                 return ret;
 318         }
 319         rec = malloc(sizeof(*rec));
 320         if (start == 0)
 321                 extent_item_refs = 0;
 322         rec->start = start;
 323         rec->nr = nr;
 324         rec->checked = 0;
 325         INIT_LIST_HEAD(&rec->backrefs);
 326
 327         if (inc_ref)
 328                 rec->refs = 1;
 329         else
 330                 rec->refs = 0;
 331
 332         if (extent_item_refs)
 333                 rec->extent_item_refs = extent_item_refs;
 334         else
 335                 rec->extent_item_refs = 0;
 336
 337         if (parent_key)
 338                 memcpy(&rec->parent_key, parent_key, sizeof(*parent_key));
 339         else
 340                 memset(&rec->parent_key, 0, sizeof(*parent_key));
 341
 342         rec->cache.start = start;
 343         rec->cache.size = nr;
 344         ret = insert_existing_cache_extent(extent_cache, &rec->cache);
 345         BUG_ON(ret);
 346         bytes_used += nr;
 347         if (set_checked)
 348                 rec->checked = 1;
 349         return ret;
 350 }
 351
 352 static int add_backref(struct cache_tree *extent_cache, u64 bytenr,
 353                        u64 root, u64 gen, u64 owner, u64 owner_offset,
 354                        int found_ref)
 355 {
 356         struct extent_record *rec;
 357         struct extent_backref *back;
 358         struct cache_extent *cache;
 359
 360         if (root < BTRFS_FS_TREE_OBJECTID)
 361                 gen = 0;
 362
 363         cache = find_cache_extent(extent_cache, bytenr, 1);
 364         if (!cache) {
 365                 add_extent_rec(extent_cache, NULL, 0, bytenr, 1, 0, 0, 0);
 366                 cache = find_cache_extent(extent_cache, bytenr, 1);
 367                 if (!cache)
 368                         abort();
 369         }
 370
 371         rec = container_of(cache, struct extent_record, cache);
 372         if (rec->start != bytenr) {
 373                 abort();
 374         }
 375         back = find_backref(rec, root, gen, owner, owner_offset);
 376         if (!back)
 377                 back = alloc_backref(rec, root, gen, owner, owner_offset);
 378
 379         if (found_ref) {
 380                 if (back->found_ref) {
 381                         fprintf(stderr, "Back ref already exists for %llu "
 382                                 "root %llu gen %llu owner %llu offset %llu\n",
 383                                 (unsigned long long)bytenr,
 384                                 (unsigned long long)root,
 385                                 (unsigned long long)gen,
 386                                 (unsigned long long)owner,
 387                                 (unsigned long long)owner_offset);
 388                 }
 389                 back->found_ref = 1;
 390         } else {
 391                 if (back->found_extent_tree) {
 392                         fprintf(stderr, "Extent back ref already exists "
 393                                 "for %llu root %llu gen %llu owner %llu "
 394                                 "offset %llu\n", (unsigned long long)bytenr,
 395                                 (unsigned long long)root,
 396                                 (unsigned long long)gen,
 397                                 (unsigned long long)owner,
 398                                 (unsigned long long)owner_offset);
 399                 }
 400                 back->found_extent_tree = 1;
 401         }
 402         return 0;
 403 }
 404
 405
 406 static int add_pending(struct cache_tree *pending,
 407                        struct cache_tree *seen, u64 bytenr, u32 size)
 408 {
 409         int ret;
 410         ret = insert_cache_extent(seen, bytenr, size);
 411         if (ret)
 412                 return ret;
 413         insert_cache_extent(pending, bytenr, size);
 414         return 0;
 415 }
 416 static int pick_next_pending(struct cache_tree *pending,
 417                         struct cache_tree *reada,
 418                         struct cache_tree *nodes,
 419                         u64 last, struct block_info *bits, int bits_nr,
 420                         int *reada_bits)
 421 {
 422         unsigned long node_start = last;
 423         struct cache_extent *cache;
 424         int ret;
 425
 426         cache = find_first_cache_extent(reada, 0);
 427         if (cache) {
 428                 bits[0].start = cache->start;
 429                 bits[1].size = cache->size;
 430                 *reada_bits = 1;
 431                 return 1;
 432         }
 433         *reada_bits = 0;
 434         if (node_start > 32768)
 435                 node_start -= 32768;
 436
 437         cache = find_first_cache_extent(nodes, node_start);
 438         if (!cache)
 439                 cache = find_first_cache_extent(nodes, 0);
 440
 441         if (!cache) {
 442                  cache = find_first_cache_extent(pending, 0);
 443                  if (!cache)
 444                          return 0;
 445                  ret = 0;
 446                  do {
 447                          bits[ret].start = cache->start;
 448                          bits[ret].size = cache->size;
 449                          cache = next_cache_extent(cache);
 450                          ret++;
 451                  } while (cache && ret < bits_nr);
 452                  return ret;
 453         }
 454
 455         ret = 0;
 456         do {
 457                 bits[ret].start = cache->start;
 458                 bits[ret].size = cache->size;
 459                 cache = next_cache_extent(cache);
 460                 ret++;
 461         } while (cache && ret < bits_nr);
 462
 463         if (bits_nr - ret > 8) {
 464                 u64 lookup = bits[0].start + bits[0].size;
 465                 struct cache_extent *next;
 466                 next = find_first_cache_extent(pending, lookup);
 467                 while(next) {
 468                         if (next->start - lookup > 32768)
 469                                 break;
 470                         bits[ret].start = next->start;
 471                         bits[ret].size = next->size;
 472                         lookup = next->start + next->size;
 473                         ret++;
 474                         if (ret == bits_nr)
 475                                 break;
 476                         next = next_cache_extent(next);
 477                         if (!next)
 478                                 break;
 479                 }
 480         }
 481         return ret;
 482 }
 483
 484 static int run_next_block(struct btrfs_root *root,
 485                           struct block_info *bits,
 486                           int bits_nr,
 487                           u64 *last,
 488                           struct cache_tree *pending,
 489                           struct cache_tree *seen,
 490                           struct cache_tree *reada,
 491                           struct cache_tree *nodes,
 492                           struct cache_tree *extent_cache)
 493 {
 494         struct extent_buffer *buf;
 495         u64 bytenr;
 496         u32 size;
 497         int ret;
 498         int i;
 499         int nritems;
 500         struct btrfs_extent_ref *ref;
 501         struct btrfs_disk_key disk_key;
 502         struct cache_extent *cache;
 503         int reada_bits;
 504
 505         ret = pick_next_pending(pending, reada, nodes, *last, bits,
 506                                 bits_nr, &reada_bits);
 507         if (ret == 0) {
 508                 return 1;
 509         }
 510         if (!reada_bits) {
 511                 for(i = 0; i < ret; i++) {
 512                         insert_cache_extent(reada, bits[i].start,
 513                                             bits[i].size);
 514                         readahead_tree_block(root, bits[i].start, bits[i].size);
 515                 }
 516         }
 517         *last = bits[0].start;
 518         bytenr = bits[0].start;
 519         size = bits[0].size;
 520
 521         cache = find_cache_extent(pending, bytenr, size);
 522         if (cache) {
 523                 remove_cache_extent(pending, cache);
 524                 free(cache);
 525         }
 526         cache = find_cache_extent(reada, bytenr, size);
 527         if (cache) {
 528                 remove_cache_extent(reada, cache);
 529                 free(cache);
 530         }
 531         cache = find_cache_extent(nodes, bytenr, size);
 532         if (cache) {
 533                 remove_cache_extent(nodes, cache);
 534                 free(cache);
 535         }
 536
 537         buf = read_tree_block(root, bytenr, size);
 538         nritems = btrfs_header_nritems(buf);
 539         ret = check_block(root, extent_cache, buf);
 540         if (ret) {
 541                 fprintf(stderr, "bad block %llu\n",
 542                         (unsigned long long)bytenr);
 543         }
 544         if (btrfs_is_leaf(buf)) {
 545                 btree_space_waste += btrfs_leaf_free_space(root, buf);
 546                 for (i = 0; i < nritems; i++) {
 547                         struct btrfs_file_extent_item *fi;
 548                         btrfs_item_key(buf, &disk_key, i);
 549                         if (btrfs_disk_key_type(&disk_key) ==
 550                             BTRFS_EXTENT_ITEM_KEY) {
 551                                 struct btrfs_key found;
 552                                 struct btrfs_extent_item *ei;
 553                                 btrfs_disk_key_to_cpu(&found, &disk_key);
 554                                 ei = btrfs_item_ptr(buf, i,
 555                                                     struct btrfs_extent_item);
 556                                 add_extent_rec(extent_cache, NULL, 0,
 557                                                found.objectid,
 558                                                found.offset,
 559                                                btrfs_extent_refs(buf, ei),
 560                                                0, 0);
 561                                 continue;
 562                         }
 563                         if (btrfs_disk_key_type(&disk_key) ==
 564                             BTRFS_CSUM_ITEM_KEY) {
 565                                 total_csum_bytes +=
 566                                         btrfs_item_size_nr(buf, i);
 567                                 continue;
 568                         }
 569                         if (btrfs_disk_key_type(&disk_key) ==
 570                             BTRFS_BLOCK_GROUP_ITEM_KEY) {
 571                                 struct btrfs_block_group_item *bi;
 572                                 bi = btrfs_item_ptr(buf, i,
 573                                             struct btrfs_block_group_item);
 574 #if 0
 575                                 fprintf(stderr,"block group %Lu %Lu used %Lu ",
 576                                         btrfs_disk_key_objectid(disk_key),
 577                                         btrfs_disk_key_offset(disk_key),
 578                                         btrfs_block_group_used(bi));
 579                                 fprintf(stderr, "flags %x\n", bi->flags);
 580 #endif
 581                                 continue;
 582                         }
 583                         if (btrfs_disk_key_type(&disk_key) ==
 584                             BTRFS_EXTENT_REF_KEY) {
 585                                 ref = btrfs_item_ptr(buf, i,
 586                                                      struct btrfs_extent_ref);
 587
 588                                 add_backref(extent_cache,
 589                                             btrfs_disk_key_objectid(&disk_key),
 590                                             btrfs_ref_root(buf, ref),
 591                                             btrfs_ref_generation(buf, ref),
 592                                             btrfs_ref_objectid(buf, ref),
 593                                             btrfs_ref_offset(buf, ref), 0);
 594                                 continue;
 595                         }
 596                         if (btrfs_disk_key_type(&disk_key) !=
 597                             BTRFS_EXTENT_DATA_KEY)
 598                                 continue;
 599                         fi = btrfs_item_ptr(buf, i,
 600                                             struct btrfs_file_extent_item);
 601                         if (btrfs_file_extent_type(buf, fi) !=
 602                             BTRFS_FILE_EXTENT_REG)
 603                                 continue;
 604                         if (btrfs_file_extent_disk_bytenr(buf, fi) == 0)
 605                                 continue;
 606
 607                         data_bytes_allocated +=
 608                                 btrfs_file_extent_disk_num_bytes(buf, fi);
 609                         if (data_bytes_allocated < root->sectorsize) {
 610                                 abort();
 611                         }
 612                         data_bytes_referenced +=
 613                                 btrfs_file_extent_num_bytes(buf, fi);
 614                         ret = add_extent_rec(extent_cache, NULL, bytenr,
 615                                    btrfs_file_extent_disk_bytenr(buf, fi),
 616                                    btrfs_file_extent_disk_num_bytes(buf, fi),
 617                                    0, 1, 1);
 618                         add_backref(extent_cache,
 619                                     btrfs_file_extent_disk_bytenr(buf, fi),
 620                                     btrfs_header_owner(buf),
 621                                     btrfs_header_generation(buf),
 622                                     btrfs_disk_key_objectid(&disk_key),
 623                                     btrfs_disk_key_offset(&disk_key), 1);
 624                         BUG_ON(ret);
 625                 }
 626         } else {
 627                 int level;
 628                 level = btrfs_header_level(buf);
 629                 for (i = 0; i < nritems; i++) {
 630                         u64 ptr = btrfs_node_blockptr(buf, i);
 631                         u32 size = btrfs_level_size(root, level - 1);
 632                         btrfs_node_key(buf, &disk_key, i);
 633                         ret = add_extent_rec(extent_cache,
 634                                              &disk_key,
 635                                              bytenr, ptr, size,
 636                                              0, 1, 0);
 637                         BUG_ON(ret);
 638
 639                         add_backref(extent_cache, ptr,
 640                                 btrfs_header_owner(buf),
 641                                 btrfs_header_generation(buf),
 642                                 level - 1,
 643                                 btrfs_disk_key_objectid(&disk_key), 1);
 644
 645                         if (level > 1) {
 646                                 add_pending(nodes, seen, ptr, size);
 647                         } else {
 648                                 add_pending(pending, seen, ptr, size);
 649                         }
 650                 }
 651                 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) -
 652                                       nritems) * sizeof(struct btrfs_key_ptr);
 653         }
 654         total_btree_bytes += buf->len;
 655         free_extent_buffer(buf);
 656         return 0;
 657 }
 658
 659 static int add_root_to_pending(struct extent_buffer *buf,
 660                                struct block_info *bits,
 661                                int bits_nr,
 662                                struct cache_tree *extent_cache,
 663                                struct cache_tree *pending,
 664                                struct cache_tree *seen,
 665                                struct cache_tree *reada,
 666                                struct cache_tree *nodes, u64 root_objectid)
 667 {
 668         if (btrfs_header_level(buf) > 0)
 669                 add_pending(nodes, seen, buf->start, buf->len);
 670         else
 671                 add_pending(pending, seen, buf->start, buf->len);
 672         add_extent_rec(extent_cache, NULL, 0, buf->start, buf->len,
 673                        0, 1, 0);
 674
 675         add_backref(extent_cache, buf->start, root_objectid,
 676                     btrfs_header_generation(buf),
 677                     btrfs_header_level(buf), 0, 1);
 678         return 0;
 679 }
 680
 681 int check_extent_refs(struct btrfs_root *root,
 682                       struct cache_tree *extent_cache)
 683 {
 684         struct extent_record *rec;
 685         struct cache_extent *cache;
 686         int err = 0;
 687
 688         while(1) {
 689                 cache = find_first_cache_extent(extent_cache, 0);
 690                 if (!cache)
 691                         break;
 692                 rec = container_of(cache, struct extent_record, cache);
 693                 if (rec->refs != rec->extent_item_refs) {
 694                         fprintf(stderr, "ref mismatch on [%llu %llu] ",
 695                                 (unsigned long long)rec->start,
 696                                 (unsigned long long)rec->nr);
 697                         fprintf(stderr, "extent item %u, found %u\n",
 698                                 rec->extent_item_refs,
 699                                 rec->refs);
 700                         err = 1;
 701                 }
 702                 if (all_backpointers_checked(rec, 1)) {
 703                         fprintf(stderr, "backpointer mismatch on [%llu %llu]\n",
 704                                 (unsigned long long)rec->start,
 705                                 (unsigned long long)rec->nr);
 706
 707                         err = 1;
 708                 }
 709                 remove_cache_extent(extent_cache, cache);
 710                 free_all_backrefs(rec);
 711                 free(rec);
 712         }
 713         return err;
 714 }
 715
 716 void print_usage(void) {
 717         fprintf(stderr, "usage: btrfsck dev\n");
 718         exit(1);
 719 }
 720
 721 int main(int ac, char **av) {
 722         struct btrfs_root *root;
 723         struct cache_tree extent_cache;
 724         struct cache_tree seen;
 725         struct cache_tree pending;
 726         struct cache_tree reada;
 727         struct cache_tree nodes;
 728         struct btrfs_path path;
 729         struct btrfs_key key;
 730         struct btrfs_key found_key;
 731         int ret;
 732         u64 last = 0;
 733         struct block_info *bits;
 734         int bits_nr;
 735         struct extent_buffer *leaf;
 736         int slot;
 737         struct btrfs_root_item ri;
 738
 739         if (ac < 2)
 740                 print_usage();
 741
 742         radix_tree_init();
 743         cache_tree_init(&extent_cache);
 744         cache_tree_init(&seen);
 745         cache_tree_init(&pending);
 746         cache_tree_init(&nodes);
 747         cache_tree_init(&reada);
 748
 749         root = open_ctree(av[1], 0, 0);
 750
 751         bits_nr = 1024;
 752         bits = malloc(bits_nr * sizeof(struct block_info));
 753         if (!bits) {
 754                 perror("malloc");
 755                 exit(1);
 756         }
 757
 758         add_root_to_pending(root->fs_info->tree_root->node, bits, bits_nr,
 759                             &extent_cache, &pending, &seen, &reada, &nodes,
 760                             root->fs_info->tree_root->root_key.objectid);
 761
 762         add_root_to_pending(root->fs_info->chunk_root->node, bits, bits_nr,
 763                             &extent_cache, &pending, &seen, &reada, &nodes,
 764                             root->fs_info->chunk_root->root_key.objectid);
 765
 766         btrfs_init_path(&path);
 767         key.offset = 0;
 768         key.objectid = 0;
 769         btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
 770         ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
 771                                         &key, &path, 0, 0);
 772         BUG_ON(ret < 0);
 773         while(1) {
 774                 leaf = path.nodes[0];
 775                 slot = path.slots[0];
 776                 if (slot >= btrfs_header_nritems(path.nodes[0])) {
 777                         ret = btrfs_next_leaf(root, &path);
 778                         if (ret != 0)
 779                                 break;
 780                         leaf = path.nodes[0];
 781                         slot = path.slots[0];
 782                 }
 783                 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
 784                 if (btrfs_key_type(&found_key) == BTRFS_ROOT_ITEM_KEY) {
 785                         unsigned long offset;
 786                         struct extent_buffer *buf;
 787
 788                         offset = btrfs_item_ptr_offset(leaf, path.slots[0]);
 789                         read_extent_buffer(leaf, &ri, offset, sizeof(ri));
 790                         buf = read_tree_block(root->fs_info->tree_root,
 791                                               btrfs_root_bytenr(&ri),
 792                                               btrfs_level_size(root,
 793                                                        btrfs_root_level(&ri)));
 794                         add_root_to_pending(buf, bits, bits_nr, &extent_cache,
 795                                             &pending, &seen, &reada, &nodes,
 796                                             found_key.objectid);
 797                         free_extent_buffer(buf);
 798                 }
 799                 path.slots[0]++;
 800         }
 801         btrfs_release_path(root, &path);
 802         while(1) {
 803                 ret = run_next_block(root, bits, bits_nr, &last, &pending,
 804                                      &seen, &reada, &nodes, &extent_cache);
 805                 if (ret != 0)
 806                         break;
 807         }
 808         ret = check_extent_refs(root, &extent_cache);
 809         close_ctree(root);
 810         printf("found %llu bytes used err is %d\n",
 811                (unsigned long long)bytes_used, ret);
 812         printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes);
 813         printf("total tree bytes: %llu\n",
 814                (unsigned long long)total_btree_bytes);
 815         printf("btree space waste bytes: %llu\n",
 816                (unsigned long long)btree_space_waste);
 817         printf("file data blocks allocated: %llu\n referenced %llu\n",
 818                 (unsigned long long)data_bytes_allocated,
 819                 (unsigned long long)data_bytes_referenced);
 820         return ret;
 821 }