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
  30 static u64 bytes_used = 0;
  31 static u64 total_csum_bytes = 0;
  32 static u64 total_btree_bytes = 0;
  33 static u64 btree_space_waste = 0;
  34 static u64 data_bytes_allocated = 0;
  35 static u64 data_bytes_referenced = 0;
  36
  37 struct extent_record {
  38         struct cache_extent cache;
  39         struct btrfs_disk_key parent_key;
  40         u64 start;
  41         u64 nr;
  42         u64 owner;
  43         u32 refs;
  44         u32 extent_item_refs;
  45         int checked;
  46 };
  47
  48 struct block_info {
  49         u64 start;
  50         u32 size;
  51 };
  52
  53 static int check_node(struct btrfs_root *root,
  54                       struct btrfs_disk_key *parent_key,
  55                       struct btrfs_node *node)
  56 {
  57         int i;
  58         u32 nritems = btrfs_header_nritems(&node->header);
  59
  60         if (nritems == 0 || nritems > BTRFS_NODEPTRS_PER_BLOCK(root))
  61                 return 1;
  62         if (parent_key->type) {
  63                 if (memcmp(parent_key, &node->ptrs[0].key,
  64                               sizeof(struct btrfs_disk_key)))
  65                         return 1;
  66         }
  67         for (i = 0; nritems > 1 && i < nritems - 2; i++) {
  68                 struct btrfs_key cpukey;
  69                 btrfs_disk_key_to_cpu(&cpukey, &node->ptrs[i + 1].key);
  70                 if (btrfs_comp_keys(&node->ptrs[i].key, &cpukey) >= 0)
  71                         return 1;
  72         }
  73         return 0;
  74 }
  75
  76 static int check_leaf(struct btrfs_root *root,
  77                       struct btrfs_disk_key *parent_key,
  78                       struct btrfs_leaf *leaf)
  79 {
  80         int i;
  81         u32 nritems = btrfs_header_nritems(&leaf->header);
  82
  83         if (btrfs_header_level(&leaf->header) != 0) {
  84                 fprintf(stderr, "leaf is not a leaf %llu\n",
  85                        (unsigned long long)btrfs_header_bytenr(&leaf->header));
  86                 return 1;
  87         }
  88         if (btrfs_leaf_free_space(root, leaf) < 0) {
  89                 fprintf(stderr, "leaf free space incorrect %llu %d\n",
  90                         (unsigned long long)btrfs_header_bytenr(&leaf->header),
  91                         btrfs_leaf_free_space(root, leaf));
  92                 return 1;
  93         }
  94
  95         if (nritems == 0)
  96                 return 0;
  97
  98         if (parent_key->type && memcmp(parent_key, &leaf->items[0].key,
  99                                         sizeof(struct btrfs_disk_key))) {
 100                 fprintf(stderr, "leaf parent key incorrect %llu\n",
 101                        (unsigned long long)btrfs_header_bytenr(&leaf->header));
 102                 return 1;
 103         }
 104         for (i = 0; nritems > 1 && i < nritems - 2; i++) {
 105                 struct btrfs_key cpukey;
 106                 btrfs_disk_key_to_cpu(&cpukey, &leaf->items[i + 1].key);
 107                 if (btrfs_comp_keys(&leaf->items[i].key,
 108                                  &cpukey) >= 0)
 109                         return 1;
 110                 if (btrfs_item_offset(leaf->items + i) !=
 111                         btrfs_item_end(leaf->items + i + 1))
 112                         return 1;
 113                 if (i == 0) {
 114                         if (btrfs_item_offset(leaf->items + i) +
 115                                btrfs_item_size(leaf->items + i) !=
 116                                BTRFS_LEAF_DATA_SIZE(root))
 117                                 return 1;
 118                 }
 119         }
 120         return 0;
 121 }
 122
 123 static int maybe_free_extent_rec(struct cache_tree *extent_cache,
 124                                  struct extent_record *rec)
 125 {
 126         if (rec->checked && rec->extent_item_refs == rec->refs &&
 127             rec->refs > 0) {
 128                 remove_cache_extent(extent_cache, &rec->cache);
 129                 free(rec);
 130         }
 131         return 0;
 132 }
 133
 134 static int check_block(struct btrfs_root *root,
 135                        struct cache_tree *extent_cache,
 136                        struct btrfs_buffer *buf)
 137 {
 138         struct extent_record *rec;
 139         struct cache_extent *cache;
 140         int ret = 1;
 141
 142         cache = find_cache_extent(extent_cache, buf->bytenr, buf->size);
 143         if (!cache)
 144                 return 1;
 145         rec = container_of(cache, struct extent_record, cache);
 146         if (btrfs_is_leaf(&buf->node)) {
 147                 ret = check_leaf(root, &rec->parent_key, &buf->leaf);
 148         } else {
 149                 ret = check_node(root, &rec->parent_key, &buf->node);
 150         }
 151         rec->checked = 1;
 152         if (!ret)
 153                 maybe_free_extent_rec(extent_cache, rec);
 154         return ret;
 155 }
 156
 157 static int add_extent_rec(struct cache_tree *extent_cache,
 158                           struct btrfs_disk_key *parent_key,
 159                           u64 ref, u64 start,
 160                           u64 nr, u64 owner,
 161                           u32 extent_item_refs, int inc_ref, int set_checked)
 162 {
 163         struct extent_record *rec;
 164         struct cache_extent *cache;
 165         int ret = 0;
 166
 167         cache = find_cache_extent(extent_cache, start, nr);
 168         if (cache) {
 169                 rec = container_of(cache, struct extent_record, cache);
 170                 if (inc_ref)
 171                         rec->refs++;
 172                 if (start != rec->start) {
 173                         fprintf(stderr, "warning, start mismatch %llu %llu\n",
 174                                 (unsigned long long)rec->start,
 175                                 (unsigned long long)start);
 176                         ret = 1;
 177                 }
 178                 if (extent_item_refs) {
 179                         if (rec->extent_item_refs) {
 180                                 fprintf(stderr, "block %llu rec extent_item_refs %u, passed %u\n", (unsigned long long)start, rec->extent_item_refs, extent_item_refs);
 181                         }
 182                         rec->extent_item_refs = extent_item_refs;
 183                 }
 184                 if (set_checked)
 185                         rec->checked = 1;
 186                 maybe_free_extent_rec(extent_cache, rec);
 187                 return ret;
 188         }
 189         rec = malloc(sizeof(*rec));
 190         if (start == 0)
 191                 extent_item_refs = 0;
 192         rec->start = start;
 193         rec->nr = nr;
 194         rec->owner = owner;
 195         rec->checked = 0;
 196
 197         if (inc_ref)
 198                 rec->refs = 1;
 199         else
 200                 rec->refs = 0;
 201
 202         if (extent_item_refs)
 203                 rec->extent_item_refs = extent_item_refs;
 204         else
 205                 rec->extent_item_refs = 0;
 206
 207         if (parent_key)
 208                 memcpy(&rec->parent_key, parent_key, sizeof(*parent_key));
 209         else
 210                 memset(&rec->parent_key, 0, sizeof(*parent_key));
 211
 212         rec->cache.start = start;
 213         rec->cache.size = nr;
 214         ret = insert_existing_cache_extent(extent_cache, &rec->cache);
 215         BUG_ON(ret);
 216         bytes_used += nr;
 217         if (set_checked)
 218                 rec->checked = 1;
 219         return ret;
 220 }
 221
 222 static int add_pending(struct cache_tree *pending,
 223                        struct cache_tree *seen, u64 bytenr, u32 size)
 224 {
 225         int ret;
 226         ret = insert_cache_extent(seen, bytenr, size);
 227         if (ret)
 228                 return ret;
 229         insert_cache_extent(pending, bytenr, size);
 230         return 0;
 231 }
 232 static int pick_next_pending(struct cache_tree *pending,
 233                         struct cache_tree *reada,
 234                         struct cache_tree *nodes,
 235                         u64 last, struct block_info *bits, int bits_nr,
 236                         int *reada_bits)
 237 {
 238         unsigned long node_start = last;
 239         struct cache_extent *cache;
 240         int ret;
 241
 242         cache = find_first_cache_extent(reada, 0);
 243         if (cache) {
 244                 bits[0].start = cache->start;
 245                 bits[1].size = cache->size;
 246                 *reada_bits = 1;
 247                 return 1;
 248         }
 249         *reada_bits = 0;
 250         if (node_start > 32768)
 251                 node_start -= 32768;
 252
 253         cache = find_first_cache_extent(nodes, node_start);
 254         if (!cache)
 255                 cache = find_first_cache_extent(nodes, 0);
 256
 257         if (!cache) {
 258                  cache = find_first_cache_extent(pending, 0);
 259                  if (!cache)
 260                          return 0;
 261                  ret = 0;
 262                  do {
 263                          bits[ret].start = cache->start;
 264                          bits[ret].size = cache->size;
 265                          cache = next_cache_extent(cache);
 266                          ret++;
 267                  } while (cache && ret < bits_nr);
 268                  return ret;
 269         }
 270
 271         ret = 0;
 272         do {
 273                 bits[ret].start = cache->start;
 274                 bits[ret].size = cache->size;
 275                 cache = next_cache_extent(cache);
 276                 ret++;
 277         } while (cache && ret < bits_nr);
 278
 279         if (bits_nr - ret > 8) {
 280                 u64 lookup = bits[0].start + bits[0].size;
 281                 struct cache_extent *next;
 282                 next = find_first_cache_extent(pending, lookup);
 283                 while(next) {
 284                         if (next->start - lookup > 32768)
 285                                 break;
 286                         bits[ret].start = next->start;
 287                         bits[ret].size = next->size;
 288                         lookup = next->start + next->size;
 289                         ret++;
 290                         if (ret == bits_nr)
 291                                 break;
 292                         next = next_cache_extent(next);
 293                         if (!next)
 294                                 break;
 295                 }
 296         }
 297         return ret;
 298 }
 299 static struct btrfs_buffer reada_buf;
 300
 301 static int run_next_block(struct btrfs_root *root,
 302                           struct block_info *bits,
 303                           int bits_nr,
 304                           u64 *last,
 305                           struct cache_tree *pending,
 306                           struct cache_tree *seen,
 307                           struct cache_tree *reada,
 308                           struct cache_tree *nodes,
 309                           struct cache_tree *extent_cache)
 310 {
 311         struct btrfs_buffer *buf;
 312         u64 bytenr;
 313         u32 size;
 314         int ret;
 315         int i;
 316         int nritems;
 317         struct btrfs_leaf *leaf;
 318         struct btrfs_node *node;
 319         struct btrfs_disk_key *disk_key;
 320         struct cache_extent *cache;
 321         int reada_bits;
 322
 323         u64 last_block = 0;
 324         ret = pick_next_pending(pending, reada, nodes, *last, bits,
 325                                 bits_nr, &reada_bits);
 326         if (ret == 0) {
 327                 return 1;
 328         }
 329         if (!reada_bits) {
 330                 for(i = 0; i < ret; i++) {
 331                         u64 offset;
 332                         insert_cache_extent(reada, bits[i].start,
 333                                             bits[i].size);
 334                         btrfs_map_bh_to_logical(root, &reada_buf,
 335                                                 bits[i].start);
 336                         offset = reada_buf.dev_bytenr;
 337                         last_block = bits[i].start;
 338                         readahead(reada_buf.fd, offset, bits[i].size);
 339                 }
 340         }
 341         *last = bits[0].start;
 342         bytenr = bits[0].start;
 343         size = bits[0].size;
 344
 345         cache = find_cache_extent(pending, bytenr, size);
 346         if (cache) {
 347                 remove_cache_extent(pending, cache);
 348                 free(cache);
 349         }
 350         cache = find_cache_extent(reada, bytenr, size);
 351         if (cache) {
 352                 remove_cache_extent(reada, cache);
 353                 free(cache);
 354         }
 355         cache = find_cache_extent(nodes, bytenr, size);
 356         if (cache) {
 357                 remove_cache_extent(nodes, cache);
 358                 free(cache);
 359         }
 360
 361         buf = read_tree_block(root, bytenr, size);
 362         nritems = btrfs_header_nritems(&buf->node.header);
 363         ret = check_block(root, extent_cache, buf);
 364         if (ret) {
 365                 fprintf(stderr, "bad block %llu\n",
 366                         (unsigned long long)bytenr);
 367         }
 368         if (btrfs_is_leaf(&buf->node)) {
 369                 leaf = &buf->leaf;
 370                 btree_space_waste += btrfs_leaf_free_space(root, leaf);
 371                 for (i = 0; i < nritems; i++) {
 372                         struct btrfs_file_extent_item *fi;
 373                         disk_key = &leaf->items[i].key;
 374                         if (btrfs_disk_key_type(disk_key) ==
 375                             BTRFS_EXTENT_ITEM_KEY) {
 376                                 struct btrfs_key found;
 377                                 struct btrfs_extent_item *ei;
 378                                 btrfs_disk_key_to_cpu(&found,
 379                                                       &leaf->items[i].key);
 380                                 ei = btrfs_item_ptr(leaf, i,
 381                                                     struct btrfs_extent_item);
 382                                 add_extent_rec(extent_cache, NULL, 0,
 383                                                found.objectid,
 384                                                found.offset,
 385                                                btrfs_extent_owner(ei),
 386                                                btrfs_extent_refs(ei), 0, 0);
 387                                 continue;
 388                         }
 389                         if (btrfs_disk_key_type(disk_key) ==
 390                             BTRFS_CSUM_ITEM_KEY) {
 391                                 total_csum_bytes +=
 392                                         btrfs_item_size(leaf->items + i);
 393                                 continue;
 394                         }
 395                         if (btrfs_disk_key_type(disk_key) ==
 396                             BTRFS_BLOCK_GROUP_ITEM_KEY) {
 397                                 struct btrfs_block_group_item *bi;
 398                                 bi = btrfs_item_ptr(leaf, i,
 399                                             struct btrfs_block_group_item);
 400 #if 0
 401                                 fprintf(stderr,"block group %Lu %Lu used %Lu ",
 402                                         btrfs_disk_key_objectid(disk_key),
 403                                         btrfs_disk_key_offset(disk_key),
 404                                         btrfs_block_group_used(bi));
 405                                 fprintf(stderr, "flags %x\n", bi->flags);
 406 #endif
 407                                 continue;
 408                         }
 409                         if (btrfs_disk_key_type(&leaf->items[i].key) !=
 410                             BTRFS_EXTENT_DATA_KEY)
 411                                 continue;
 412                         fi = btrfs_item_ptr(leaf, i,
 413                                             struct btrfs_file_extent_item);
 414                         if (btrfs_file_extent_type(fi) !=
 415                             BTRFS_FILE_EXTENT_REG)
 416                                 continue;
 417                         if (btrfs_file_extent_disk_bytenr(fi) == 0)
 418                                 continue;
 419
 420                         data_bytes_allocated +=
 421                                 btrfs_file_extent_disk_num_bytes(fi);
 422                         data_bytes_referenced +=
 423                                 btrfs_file_extent_num_bytes(fi);
 424                         ret = add_extent_rec(extent_cache, NULL, bytenr,
 425                                    btrfs_file_extent_disk_bytenr(fi),
 426                                    btrfs_file_extent_disk_num_bytes(fi),
 427                                    btrfs_disk_key_objectid(&leaf->items[i].key),
 428                                    0, 1, 1);
 429                         BUG_ON(ret);
 430                 }
 431         } else {
 432                 int level;
 433                 node = &buf->node;
 434                 level = btrfs_header_level(&node->header);
 435                 for (i = 0; i < nritems; i++) {
 436                         u64 ptr = btrfs_node_blockptr(node, i);
 437                         u32 size = btrfs_level_size(root, level - 1);
 438                         ret = add_extent_rec(extent_cache,
 439                                              &node->ptrs[i].key,
 440                                              bytenr, ptr, size,
 441                                              btrfs_header_owner(&node->header),
 442                                              0, 1, 0);
 443                         BUG_ON(ret);
 444                         if (level > 1) {
 445                                 add_pending(nodes, seen, ptr, size);
 446                         } else {
 447                                 add_pending(pending, seen, ptr, size);
 448                         }
 449                 }
 450                 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) -
 451                                       nritems) * sizeof(struct btrfs_key_ptr);
 452         }
 453         total_btree_bytes += buf->size;
 454         btrfs_block_release(root, buf);
 455         return 0;
 456 }
 457
 458 static int add_root_to_pending(struct btrfs_buffer *buf,
 459                                struct block_info *bits,
 460                                int bits_nr,
 461                                struct cache_tree *extent_cache,
 462                                struct cache_tree *pending,
 463                                struct cache_tree *seen,
 464                                struct cache_tree *reada,
 465                                struct cache_tree *nodes)
 466 {
 467         if (btrfs_header_level(&buf->node.header) > 0)
 468                 add_pending(nodes, seen, buf->bytenr, buf->size);
 469         else
 470                 add_pending(pending, seen, buf->bytenr, buf->size);
 471         add_extent_rec(extent_cache, NULL, 0, buf->bytenr, buf->size,
 472                        btrfs_header_owner(&buf->node.header), 0, 1, 0);
 473         return 0;
 474 }
 475
 476 int check_extent_refs(struct btrfs_root *root,
 477                       struct cache_tree *extent_cache)
 478 {
 479         struct extent_record *rec;
 480         struct cache_extent *cache;
 481         int err = 0;
 482
 483         while(1) {
 484                 cache = find_first_cache_extent(extent_cache, 0);
 485                 if (!cache)
 486                         break;
 487                 rec = container_of(cache, struct extent_record, cache);
 488                 if (rec->refs != rec->extent_item_refs) {
 489                         fprintf(stderr, "ref mismatch on [%llu %llu] ",
 490                                 (unsigned long long)rec->start,
 491                                 (unsigned long long)rec->nr);
 492                         fprintf(stderr, "extent item %u, found %u\n",
 493                                 rec->extent_item_refs,
 494                                 rec->refs);
 495                         err = 1;
 496                 }
 497                 remove_cache_extent(extent_cache, cache);
 498                 free(rec);
 499         }
 500         return err;
 501 }
 502
 503 int main(int ac, char **av) {
 504         struct btrfs_super_block super;
 505         struct btrfs_root *root;
 506         struct cache_tree extent_cache;
 507         struct cache_tree seen;
 508         struct cache_tree pending;
 509         struct cache_tree reada;
 510         struct cache_tree nodes;
 511         struct btrfs_path path;
 512         struct btrfs_key key;
 513         struct btrfs_key found_key;
 514         int ret;
 515         u64 last = 0;
 516         struct block_info *bits;
 517         int bits_nr;
 518         struct btrfs_leaf *leaf;
 519         int slot;
 520         struct btrfs_root_item *ri;
 521
 522         radix_tree_init();
 523         cache_tree_init(&extent_cache);
 524         cache_tree_init(&seen);
 525         cache_tree_init(&pending);
 526         cache_tree_init(&nodes);
 527         cache_tree_init(&reada);
 528
 529         root = open_ctree(av[1], &super);
 530
 531         bits_nr = 1024;
 532         bits = malloc(bits_nr * sizeof(struct block_info));
 533         if (!bits) {
 534                 perror("malloc");
 535                 exit(1);
 536         }
 537
 538         add_root_to_pending(root->fs_info->tree_root->node, bits, bits_nr,
 539                             &extent_cache, &pending, &seen, &reada, &nodes);
 540
 541         btrfs_init_path(&path);
 542         key.offset = 0;
 543         key.objectid = 0;
 544         btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
 545         ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
 546                                         &key, &path, 0, 0);
 547         BUG_ON(ret < 0);
 548         while(1) {
 549                 leaf = &path.nodes[0]->leaf;
 550                 slot = path.slots[0];
 551                 if (slot >= btrfs_header_nritems(&leaf->header)) {
 552                         ret = btrfs_next_leaf(root, &path);
 553                         if (ret != 0)
 554                                 break;
 555                         leaf = &path.nodes[0]->leaf;
 556                         slot = path.slots[0];
 557                 }
 558                 btrfs_disk_key_to_cpu(&found_key,
 559                                       &leaf->items[path.slots[0]].key);
 560                 if (btrfs_key_type(&found_key) == BTRFS_ROOT_ITEM_KEY) {
 561                         struct btrfs_buffer *buf;
 562                         ri = btrfs_item_ptr(leaf, path.slots[0],
 563                                             struct btrfs_root_item);
 564                         buf = read_tree_block(root->fs_info->tree_root,
 565                                               btrfs_root_bytenr(ri),
 566                                               btrfs_level_size(root,
 567                                                        btrfs_root_level(ri)));
 568                         add_root_to_pending(buf, bits, bits_nr, &extent_cache,
 569                                             &pending, &seen, &reada, &nodes);
 570                         btrfs_block_release(root->fs_info->tree_root, buf);
 571                 }
 572                 path.slots[0]++;
 573         }
 574         btrfs_release_path(root, &path);
 575         while(1) {
 576                 ret = run_next_block(root, bits, bits_nr, &last, &pending,
 577                                      &seen, &reada, &nodes, &extent_cache);
 578                 if (ret != 0)
 579                         break;
 580         }
 581         ret = check_extent_refs(root, &extent_cache);
 582         close_ctree(root, &super);
 583         printf("found %llu bytes used err is %d\n",
 584                (unsigned long long)bytes_used, ret);
 585         printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes);
 586         printf("total tree bytes: %llu\n",
 587                (unsigned long long)total_btree_bytes);
 588         printf("btree space waste bytes: %llu\n",
 589                (unsigned long long)btree_space_waste);
 590         printf("file data blocks allocated: %llu\n referenced %llu\n",
 591                 (unsigned long long)data_bytes_allocated,
 592                 (unsigned long long)data_bytes_referenced);
 593         return ret;
 594 }