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 %lu\n",
 136                                 btrfs_item_end_nr(buf, i),
 137                                 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 static struct extent_buffer reada_buf;
 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         u64 last_block = 0;
 507         ret = pick_next_pending(pending, reada, nodes, *last, bits,
 508                                 bits_nr, &reada_bits);
 509         if (ret == 0) {
 510                 return 1;
 511         }
 512         if (!reada_bits) {
 513                 for(i = 0; i < ret; i++) {
 514                         u64 offset;
 515                         insert_cache_extent(reada, bits[i].start,
 516                                             bits[i].size);
 517                         btrfs_map_bh_to_logical(root, &reada_buf,
 518                                                 bits[i].start);
 519                         offset = reada_buf.dev_bytenr;
 520                         last_block = bits[i].start;
 521                         readahead(reada_buf.fd, offset, bits[i].size);
 522                 }
 523         }
 524         *last = bits[0].start;
 525         bytenr = bits[0].start;
 526         size = bits[0].size;
 527
 528         cache = find_cache_extent(pending, bytenr, size);
 529         if (cache) {
 530                 remove_cache_extent(pending, cache);
 531                 free(cache);
 532         }
 533         cache = find_cache_extent(reada, bytenr, size);
 534         if (cache) {
 535                 remove_cache_extent(reada, cache);
 536                 free(cache);
 537         }
 538         cache = find_cache_extent(nodes, bytenr, size);
 539         if (cache) {
 540                 remove_cache_extent(nodes, cache);
 541                 free(cache);
 542         }
 543
 544         buf = read_tree_block(root, bytenr, size);
 545         nritems = btrfs_header_nritems(buf);
 546         ret = check_block(root, extent_cache, buf);
 547         if (ret) {
 548                 fprintf(stderr, "bad block %llu\n",
 549                         (unsigned long long)bytenr);
 550         }
 551         if (btrfs_is_leaf(buf)) {
 552                 btree_space_waste += btrfs_leaf_free_space(root, buf);
 553                 for (i = 0; i < nritems; i++) {
 554                         struct btrfs_file_extent_item *fi;
 555                         btrfs_item_key(buf, &disk_key, i);
 556                         if (btrfs_disk_key_type(&disk_key) ==
 557                             BTRFS_EXTENT_ITEM_KEY) {
 558                                 struct btrfs_key found;
 559                                 struct btrfs_extent_item *ei;
 560                                 btrfs_disk_key_to_cpu(&found, &disk_key);
 561                                 ei = btrfs_item_ptr(buf, i,
 562                                                     struct btrfs_extent_item);
 563                                 add_extent_rec(extent_cache, NULL, 0,
 564                                                found.objectid,
 565                                                found.offset,
 566                                                btrfs_extent_refs(buf, ei),
 567                                                0, 0);
 568                                 continue;
 569                         }
 570                         if (btrfs_disk_key_type(&disk_key) ==
 571                             BTRFS_CSUM_ITEM_KEY) {
 572                                 total_csum_bytes +=
 573                                         btrfs_item_size_nr(buf, i);
 574                                 continue;
 575                         }
 576                         if (btrfs_disk_key_type(&disk_key) ==
 577                             BTRFS_BLOCK_GROUP_ITEM_KEY) {
 578                                 struct btrfs_block_group_item *bi;
 579                                 bi = btrfs_item_ptr(buf, i,
 580                                             struct btrfs_block_group_item);
 581 #if 0
 582                                 fprintf(stderr,"block group %Lu %Lu used %Lu ",
 583                                         btrfs_disk_key_objectid(disk_key),
 584                                         btrfs_disk_key_offset(disk_key),
 585                                         btrfs_block_group_used(bi));
 586                                 fprintf(stderr, "flags %x\n", bi->flags);
 587 #endif
 588                                 continue;
 589                         }
 590                         if (btrfs_disk_key_type(&disk_key) ==
 591                             BTRFS_EXTENT_REF_KEY) {
 592                                 ref = btrfs_item_ptr(buf, i,
 593                                                      struct btrfs_extent_ref);
 594
 595                                 add_backref(extent_cache,
 596                                             btrfs_disk_key_objectid(&disk_key),
 597                                             btrfs_ref_root(buf, ref),
 598                                             btrfs_ref_generation(buf, ref),
 599                                             btrfs_ref_objectid(buf, ref),
 600                                             btrfs_ref_offset(buf, ref), 0);
 601                                 continue;
 602                         }
 603                         if (btrfs_disk_key_type(&disk_key) !=
 604                             BTRFS_EXTENT_DATA_KEY)
 605                                 continue;
 606                         fi = btrfs_item_ptr(buf, i,
 607                                             struct btrfs_file_extent_item);
 608                         if (btrfs_file_extent_type(buf, fi) !=
 609                             BTRFS_FILE_EXTENT_REG)
 610                                 continue;
 611                         if (btrfs_file_extent_disk_bytenr(buf, fi) == 0)
 612                                 continue;
 613
 614                         data_bytes_allocated +=
 615                                 btrfs_file_extent_disk_num_bytes(buf, fi);
 616                         data_bytes_referenced +=
 617                                 btrfs_file_extent_num_bytes(buf, fi);
 618                         ret = add_extent_rec(extent_cache, NULL, bytenr,
 619                                    btrfs_file_extent_disk_bytenr(buf, fi),
 620                                    btrfs_file_extent_disk_num_bytes(buf, fi),
 621                                    0, 1, 1);
 622                         add_backref(extent_cache,
 623                                     btrfs_file_extent_disk_bytenr(buf, fi),
 624                                     btrfs_header_owner(buf),
 625                                     btrfs_header_generation(buf),
 626                                     btrfs_disk_key_objectid(&disk_key),
 627                                     btrfs_disk_key_offset(&disk_key), 1);
 628                         BUG_ON(ret);
 629                 }
 630         } else {
 631                 int level;
 632                 level = btrfs_header_level(buf);
 633                 for (i = 0; i < nritems; i++) {
 634                         u64 ptr = btrfs_node_blockptr(buf, i);
 635                         u32 size = btrfs_level_size(root, level - 1);
 636                         btrfs_node_key(buf, &disk_key, i);
 637                         ret = add_extent_rec(extent_cache,
 638                                              &disk_key,
 639                                              bytenr, ptr, size,
 640                                              0, 1, 0);
 641                         BUG_ON(ret);
 642
 643                         add_backref(extent_cache, ptr,
 644                                 btrfs_header_owner(buf),
 645                                 btrfs_header_generation(buf),
 646                                 level - 1,
 647                                 btrfs_disk_key_objectid(&disk_key), 1);
 648
 649                         if (level > 1) {
 650                                 add_pending(nodes, seen, ptr, size);
 651                         } else {
 652                                 add_pending(pending, seen, ptr, size);
 653                         }
 654                 }
 655                 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) -
 656                                       nritems) * sizeof(struct btrfs_key_ptr);
 657         }
 658         total_btree_bytes += buf->len;
 659         free_extent_buffer(buf);
 660         return 0;
 661 }
 662
 663 static int add_root_to_pending(struct extent_buffer *buf,
 664                                struct block_info *bits,
 665                                int bits_nr,
 666                                struct cache_tree *extent_cache,
 667                                struct cache_tree *pending,
 668                                struct cache_tree *seen,
 669                                struct cache_tree *reada,
 670                                struct cache_tree *nodes, u64 root_objectid)
 671 {
 672         if (btrfs_header_level(buf) > 0)
 673                 add_pending(nodes, seen, buf->start, buf->len);
 674         else
 675                 add_pending(pending, seen, buf->start, buf->len);
 676         add_extent_rec(extent_cache, NULL, 0, buf->start, buf->len,
 677                        0, 1, 0);
 678
 679         add_backref(extent_cache, buf->start, root_objectid,
 680                     btrfs_header_generation(buf),
 681                     btrfs_header_level(buf), 0, 1);
 682         return 0;
 683 }
 684
 685 int check_extent_refs(struct btrfs_root *root,
 686                       struct cache_tree *extent_cache)
 687 {
 688         struct extent_record *rec;
 689         struct cache_extent *cache;
 690         int err = 0;
 691
 692         while(1) {
 693                 cache = find_first_cache_extent(extent_cache, 0);
 694                 if (!cache)
 695                         break;
 696                 rec = container_of(cache, struct extent_record, cache);
 697                 if (rec->refs != rec->extent_item_refs) {
 698                         fprintf(stderr, "ref mismatch on [%llu %llu] ",
 699                                 (unsigned long long)rec->start,
 700                                 (unsigned long long)rec->nr);
 701                         fprintf(stderr, "extent item %u, found %u\n",
 702                                 rec->extent_item_refs,
 703                                 rec->refs);
 704                         err = 1;
 705                 }
 706                 if (all_backpointers_checked(rec, 1)) {
 707                         fprintf(stderr, "backpointer mismatch on [%llu %llu]\n",
 708                                 (unsigned long long)rec->start,
 709                                 (unsigned long long)rec->nr);
 710
 711                         err = 1;
 712                 }
 713                 remove_cache_extent(extent_cache, cache);
 714                 free_all_backrefs(rec);
 715                 free(rec);
 716         }
 717         return err;
 718 }
 719
 720 void print_usage(void) {
 721         fprintf(stderr, "usage: btrfsck dev\n");
 722         exit(1);
 723 }
 724
 725 int main(int ac, char **av) {
 726         struct btrfs_root *root;
 727         struct cache_tree extent_cache;
 728         struct cache_tree seen;
 729         struct cache_tree pending;
 730         struct cache_tree reada;
 731         struct cache_tree nodes;
 732         struct btrfs_path path;
 733         struct btrfs_key key;
 734         struct btrfs_key found_key;
 735         int ret;
 736         u64 last = 0;
 737         struct block_info *bits;
 738         int bits_nr;
 739         struct extent_buffer *leaf;
 740         int slot;
 741         struct btrfs_root_item ri;
 742
 743         if (ac < 2)
 744                 print_usage();
 745
 746         radix_tree_init();
 747         cache_tree_init(&extent_cache);
 748         cache_tree_init(&seen);
 749         cache_tree_init(&pending);
 750         cache_tree_init(&nodes);
 751         cache_tree_init(&reada);
 752
 753         root = open_ctree(av[1], 0);
 754
 755         bits_nr = 1024;
 756         bits = malloc(bits_nr * sizeof(struct block_info));
 757         if (!bits) {
 758                 perror("malloc");
 759                 exit(1);
 760         }
 761
 762         add_root_to_pending(root->fs_info->tree_root->node, bits, bits_nr,
 763                             &extent_cache, &pending, &seen, &reada, &nodes,
 764                             root->fs_info->tree_root->root_key.objectid);
 765
 766         add_root_to_pending(root->fs_info->chunk_root->node, bits, bits_nr,
 767                             &extent_cache, &pending, &seen, &reada, &nodes,
 768                             root->fs_info->chunk_root->root_key.objectid);
 769
 770         btrfs_init_path(&path);
 771         key.offset = 0;
 772         key.objectid = 0;
 773         btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
 774         ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
 775                                         &key, &path, 0, 0);
 776         BUG_ON(ret < 0);
 777         while(1) {
 778                 leaf = path.nodes[0];
 779                 slot = path.slots[0];
 780                 if (slot >= btrfs_header_nritems(path.nodes[0])) {
 781                         ret = btrfs_next_leaf(root, &path);
 782                         if (ret != 0)
 783                                 break;
 784                         leaf = path.nodes[0];
 785                         slot = path.slots[0];
 786                 }
 787                 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
 788                 if (btrfs_key_type(&found_key) == BTRFS_ROOT_ITEM_KEY) {
 789                         unsigned long offset;
 790                         struct extent_buffer *buf;
 791
 792                         offset = btrfs_item_ptr_offset(leaf, path.slots[0]);
 793                         read_extent_buffer(leaf, &ri, offset, sizeof(ri));
 794                         buf = read_tree_block(root->fs_info->tree_root,
 795                                               btrfs_root_bytenr(&ri),
 796                                               btrfs_level_size(root,
 797                                                        btrfs_root_level(&ri)));
 798                         add_root_to_pending(buf, bits, bits_nr, &extent_cache,
 799                                             &pending, &seen, &reada, &nodes,
 800                                             found_key.objectid);
 801                         free_extent_buffer(buf);
 802                 }
 803                 path.slots[0]++;
 804         }
 805         btrfs_release_path(root, &path);
 806         while(1) {
 807                 ret = run_next_block(root, bits, bits_nr, &last, &pending,
 808                                      &seen, &reada, &nodes, &extent_cache);
 809                 if (ret != 0)
 810                         break;
 811         }
 812         ret = check_extent_refs(root, &extent_cache);
 813         close_ctree(root);
 814         printf("found %llu bytes used err is %d\n",
 815                (unsigned long long)bytes_used, ret);
 816         printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes);
 817         printf("total tree bytes: %llu\n",
 818                (unsigned long long)total_btree_bytes);
 819         printf("btree space waste bytes: %llu\n",
 820                (unsigned long long)btree_space_waste);
 821         printf("file data blocks allocated: %llu\n referenced %llu\n",
 822                 (unsigned long long)data_bytes_allocated,
 823                 (unsigned long long)data_bytes_referenced);
 824         return ret;
 825 }