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