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