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