btrfsck.c

   1 #define _XOPEN_SOURCE 500
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #define __USE_GNU
   5 #include <fcntl.h>
   6 #include "kerncompat.h"
   7 #include "radix-tree.h"
   8 #include "ctree.h"
   9 #include "disk-io.h"
  10 #include "print-tree.h"
  11 #include "transaction.h"
  12 #include "bit-radix.h"
  13
  14 static u64 blocks_used = 0;
  15 static u64 total_csum_bytes = 0;
  16 static u64 total_btree_blocks = 0;
  17 static u64 btree_space_waste = 0;
  18
  19 struct extent_record {
  20         struct btrfs_disk_key parent_key;
  21         u64 start;
  22         u64 nr;
  23         u64 owner;
  24         u32 refs;
  25         u32 extent_item_refs;
  26         int checked;
  27 };
  28
  29 static int check_node(struct btrfs_root *root,
  30                       struct btrfs_disk_key *parent_key,
  31                       struct btrfs_node *node)
  32 {
  33         int i;
  34         u32 nritems = btrfs_header_nritems(&node->header);
  35
  36         if (nritems == 0 || nritems > BTRFS_NODEPTRS_PER_BLOCK(root))
  37                 return 1;
  38         if (parent_key->flags) {
  39                 if (memcmp(parent_key, &node->ptrs[0].key,
  40                               sizeof(struct btrfs_disk_key)))
  41                         return 1;
  42         }
  43         for (i = 0; nritems > 1 && i < nritems - 2; i++) {
  44                 struct btrfs_key cpukey;
  45                 btrfs_disk_key_to_cpu(&cpukey, &node->ptrs[i + 1].key);
  46                 if (btrfs_comp_keys(&node->ptrs[i].key, &cpukey) >= 0)
  47                         return 1;
  48         }
  49         return 0;
  50 }
  51
  52 static int check_leaf(struct btrfs_root *root,
  53                       struct btrfs_disk_key *parent_key,
  54                       struct btrfs_leaf *leaf)
  55 {
  56         int i;
  57         u32 nritems = btrfs_header_nritems(&leaf->header);
  58
  59         if (btrfs_header_level(&leaf->header) != 0) {
  60                 fprintf(stderr, "leaf is not a leaf %Lu\n",
  61                         btrfs_header_blocknr(&leaf->header));
  62                 return 1;
  63         }
  64         if (btrfs_leaf_free_space(root, leaf) < 0) {
  65                 fprintf(stderr, "leaf free space incorrect %Lu %d\n",
  66                         btrfs_header_blocknr(&leaf->header),
  67                         btrfs_leaf_free_space(root, leaf));
  68                 return 1;
  69         }
  70
  71         if (nritems == 0)
  72                 return 0;
  73
  74         if (parent_key->flags) {
  75                 if (memcmp(parent_key, &leaf->items[0].key,
  76                        sizeof(struct btrfs_disk_key))) {
  77                         fprintf(stderr, "leaf parent key incorrect %Lu\n",
  78                                 btrfs_header_blocknr(&leaf->header));
  79                         return 1;
  80                 }
  81         }
  82         for (i = 0; nritems > 1 && i < nritems - 2; i++) {
  83                 struct btrfs_key cpukey;
  84                 btrfs_disk_key_to_cpu(&cpukey, &leaf->items[i + 1].key);
  85                 if (btrfs_comp_keys(&leaf->items[i].key,
  86                                  &cpukey) >= 0)
  87                         return 1;
  88                 if (btrfs_item_offset(leaf->items + i) !=
  89                         btrfs_item_end(leaf->items + i + 1))
  90                         return 1;
  91                 if (i == 0) {
  92                         if (btrfs_item_offset(leaf->items + i) +
  93                                btrfs_item_size(leaf->items + i) !=
  94                                BTRFS_LEAF_DATA_SIZE(root))
  95                                 return 1;
  96                 }
  97         }
  98         return 0;
  99 }
 100
 101 static int maybe_free_extent_rec(struct radix_tree_root *extent_radix,
 102                                  struct extent_record *rec)
 103 {
 104         if (rec->checked && rec->extent_item_refs == rec->refs &&
 105             rec->refs > 0) {
 106                 radix_tree_delete(extent_radix, rec->start);
 107                 free(rec);
 108         }
 109         return 0;
 110 }
 111
 112 static int check_block(struct btrfs_root *root,
 113                        struct radix_tree_root *extent_radix,
 114                        struct btrfs_buffer *buf)
 115 {
 116         struct extent_record *rec;
 117         int ret = 1;
 118
 119         rec = radix_tree_lookup(extent_radix, buf->blocknr);
 120         if (!rec)
 121                 return 1;
 122         if (btrfs_is_leaf(&buf->node)) {
 123                 ret = check_leaf(root, &rec->parent_key, &buf->leaf);
 124         } else {
 125                 ret = check_node(root, &rec->parent_key, &buf->node);
 126         }
 127         rec->checked = 1;
 128         if (!ret)
 129                 maybe_free_extent_rec(extent_radix, rec);
 130         return ret;
 131 }
 132
 133 static int add_extent_rec(struct radix_tree_root *extent_radix,
 134                           struct btrfs_disk_key *parent_key,
 135                           u64 ref, u64 start, u64 nr, u64 owner,
 136                           u32 extent_item_refs, int inc_ref, int set_checked)
 137 {
 138         struct extent_record *rec;
 139         int ret = 0;
 140         rec = radix_tree_lookup(extent_radix, start);
 141         if (rec) {
 142                 if (inc_ref)
 143                         rec->refs++;
 144                 if (start != rec->start) {
 145                         fprintf(stderr, "warning, start mismatch %Lu %Lu\n",
 146                                 rec->start, start);
 147                         ret = 1;
 148                 }
 149                 if (extent_item_refs) {
 150                         if (rec->extent_item_refs) {
 151                                 fprintf(stderr, "block %Lu rec extent_item_refs %u, passed %u\n", start, rec->extent_item_refs, extent_item_refs);
 152                         }
 153                         rec->extent_item_refs = extent_item_refs;
 154                 }
 155                 if (set_checked)
 156                         rec->checked = 1;
 157                 maybe_free_extent_rec(extent_radix, rec);
 158                 return ret;
 159         }
 160         rec = malloc(sizeof(*rec));
 161         if (start == 0)
 162                 extent_item_refs = 0;
 163         rec->start = start;
 164         rec->nr = nr;
 165         rec->owner = owner;
 166         rec->checked = 0;
 167
 168         if (inc_ref)
 169                 rec->refs = 1;
 170         else
 171                 rec->refs = 0;
 172
 173         if (extent_item_refs)
 174                 rec->extent_item_refs = extent_item_refs;
 175         else
 176                 rec->extent_item_refs = 0;
 177
 178         if (parent_key)
 179                 memcpy(&rec->parent_key, parent_key, sizeof(*parent_key));
 180         else
 181                 memset(&rec->parent_key, 0, sizeof(*parent_key));
 182
 183         ret = radix_tree_insert(extent_radix, start, rec);
 184         BUG_ON(ret);
 185         blocks_used += nr;
 186         if (set_checked)
 187                 rec->checked = 1;
 188         return ret;
 189 }
 190
 191 static int add_pending(struct radix_tree_root *pending,
 192                        struct radix_tree_root *seen, u64 blocknr)
 193 {
 194         if (test_radix_bit(seen, blocknr))
 195                 return -EEXIST;
 196         set_radix_bit(pending, blocknr);
 197         set_radix_bit(seen, blocknr);
 198         return 0;
 199 }
 200 static int pick_next_pending(struct radix_tree_root *pending,
 201                         struct radix_tree_root *reada,
 202                         struct radix_tree_root *nodes,
 203                         u64 last, unsigned long *bits, int bits_nr,
 204                         int *reada_bits)
 205 {
 206         unsigned long node_start = last;
 207         int ret;
 208         ret = find_first_radix_bit(reada, bits, 0, 1);
 209         if (ret) {
 210                 *reada_bits = 1;
 211                 return ret;
 212         }
 213         *reada_bits = 0;
 214         if (node_start > 8)
 215                 node_start -= 8;
 216         ret = find_first_radix_bit(nodes, bits, node_start, bits_nr);
 217         if (!ret)
 218                 ret = find_first_radix_bit(nodes, bits, 0, bits_nr);
 219         if (ret) {
 220                 if (bits_nr - ret > 8) {
 221                         int ret2;
 222                         u64 sequential;
 223                         ret2 = find_first_radix_bit(pending, bits + ret,
 224                                                     bits[0], bits_nr - ret);
 225                         sequential = bits[0];
 226                         while(ret2 > 0) {
 227                                 if (bits[ret] - sequential > 8)
 228                                         break;
 229                                 sequential = bits[ret];
 230                                 ret++;
 231                                 ret2--;
 232                         }
 233                 }
 234                 return ret;
 235         }
 236         return find_first_radix_bit(pending, bits, 0, bits_nr);
 237 }
 238 static struct btrfs_buffer reada_buf;
 239
 240 static int run_next_block(struct btrfs_root *root,
 241                           unsigned long *bits,
 242                           int bits_nr,
 243                           u64 *last,
 244                           struct radix_tree_root *pending,
 245                           struct radix_tree_root *seen,
 246                           struct radix_tree_root *reada,
 247                           struct radix_tree_root *nodes,
 248                           struct radix_tree_root *extent_radix)
 249 {
 250         struct btrfs_buffer *buf;
 251         u64 blocknr;
 252         int ret;
 253         int i;
 254         int nritems;
 255         struct btrfs_leaf *leaf;
 256         struct btrfs_node *node;
 257         struct btrfs_disk_key *disk_key;
 258         int reada_bits;
 259
 260         u64 last_block = 0;
 261         ret = pick_next_pending(pending, reada, nodes, *last, bits,
 262                                 bits_nr, &reada_bits);
 263         if (ret == 0) {
 264                 return 1;
 265         }
 266         if (!reada_bits) {
 267                 for(i = 0; i < ret; i++) {
 268                         u64 offset;
 269                         set_radix_bit(reada, bits[i]);
 270                         btrfs_map_bh_to_logical(root, &reada_buf, bits[i]);
 271                         offset = reada_buf.dev_blocknr * root->blocksize;
 272                         last_block = bits[i];
 273                         readahead(reada_buf.fd, offset, root->blocksize);
 274                 }
 275         }
 276         *last = bits[0];
 277         blocknr = bits[0];
 278         clear_radix_bit(pending, blocknr);
 279         clear_radix_bit(reada, blocknr);
 280         clear_radix_bit(nodes, blocknr);
 281         buf = read_tree_block(root, blocknr);
 282         nritems = btrfs_header_nritems(&buf->node.header);
 283         ret = check_block(root, extent_radix, buf);
 284         if (ret) {
 285                 fprintf(stderr, "bad block %Lu\n", blocknr);
 286         }
 287         if (btrfs_is_leaf(&buf->node)) {
 288                 leaf = &buf->leaf;
 289                 btree_space_waste += btrfs_leaf_free_space(root, leaf);
 290                 for (i = 0; i < nritems; i++) {
 291                         struct btrfs_file_extent_item *fi;
 292                         disk_key = &leaf->items[i].key;
 293                         if (btrfs_disk_key_type(disk_key) ==
 294                             BTRFS_EXTENT_ITEM_KEY) {
 295                                 struct btrfs_key found;
 296                                 struct btrfs_extent_item *ei;
 297                                 btrfs_disk_key_to_cpu(&found,
 298                                                       &leaf->items[i].key);
 299                                 ei = btrfs_item_ptr(leaf, i,
 300                                                     struct btrfs_extent_item);
 301                                 add_extent_rec(extent_radix, NULL, 0,
 302                                                found.objectid,
 303                                                found.offset,
 304                                                btrfs_extent_owner(ei),
 305                                                btrfs_extent_refs(ei), 0, 0);
 306                                 continue;
 307                         }
 308                         if (btrfs_disk_key_type(disk_key) ==
 309                             BTRFS_CSUM_ITEM_KEY) {
 310                                 total_csum_bytes +=
 311                                         btrfs_item_size(leaf->items + i);
 312                                 continue;
 313                         }
 314                         if (btrfs_disk_key_type(disk_key) ==
 315                             BTRFS_BLOCK_GROUP_ITEM_KEY) {
 316                                 struct btrfs_block_group_item *bi;
 317                                 bi = btrfs_item_ptr(leaf, i,
 318                                             struct btrfs_block_group_item);
 319 #if 0
 320                                 fprintf(stderr,"block group %Lu %Lu used %Lu ",
 321                                         btrfs_disk_key_objectid(disk_key),
 322                                         btrfs_disk_key_offset(disk_key),
 323                                         btrfs_block_group_used(bi));
 324                                 fprintf(stderr, "flags %x\n", bi->flags);
 325 #endif
 326                                 continue;
 327                         }
 328                         if (btrfs_disk_key_type(&leaf->items[i].key) !=
 329                             BTRFS_EXTENT_DATA_KEY)
 330                                 continue;
 331                         fi = btrfs_item_ptr(leaf, i,
 332                                             struct btrfs_file_extent_item);
 333                         if (btrfs_file_extent_type(fi) !=
 334                             BTRFS_FILE_EXTENT_REG)
 335                                 continue;
 336                         if (btrfs_file_extent_disk_blocknr(fi) == 0)
 337                                 continue;
 338                         ret = add_extent_rec(extent_radix, NULL, blocknr,
 339                                    btrfs_file_extent_disk_blocknr(fi),
 340                                    btrfs_file_extent_disk_num_blocks(fi),
 341                                    btrfs_disk_key_objectid(&leaf->items[i].key),
 342                                    0, 1, 1);
 343                         BUG_ON(ret);
 344                 }
 345         } else {
 346                 int level;
 347                 node = &buf->node;
 348                 level = btrfs_header_level(&node->header);
 349                 for (i = 0; i < nritems; i++) {
 350                         u64 ptr = btrfs_node_blockptr(node, i);
 351                         ret = add_extent_rec(extent_radix,
 352                                              &node->ptrs[i].key,
 353                                              blocknr, ptr, 1,
 354                                              btrfs_header_owner(&node->header),
 355                                              0, 1, 0);
 356                         BUG_ON(ret);
 357                         if (level > 1) {
 358                                 add_pending(nodes, seen, ptr);
 359                         } else {
 360                                 add_pending(pending, seen, ptr);
 361                         }
 362                 }
 363                 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) -
 364                                       nritems) * sizeof(struct btrfs_key_ptr);
 365         }
 366         btrfs_block_release(root, buf);
 367         total_btree_blocks++;
 368         return 0;
 369 }
 370
 371 static int add_root_to_pending(struct btrfs_buffer *buf,
 372                                unsigned long *bits,
 373                                int bits_nr,
 374                                struct radix_tree_root *extent_radix,
 375                                struct radix_tree_root *pending,
 376                                struct radix_tree_root *seen,
 377                                struct radix_tree_root *reada,
 378                                struct radix_tree_root *nodes)
 379 {
 380         if (btrfs_header_level(&buf->node.header) > 0)
 381                 add_pending(nodes, seen, buf->blocknr);
 382         else
 383                 add_pending(pending, seen, buf->blocknr);
 384         add_extent_rec(extent_radix, NULL, 0, buf->blocknr, 1,
 385                        btrfs_header_owner(&buf->node.header), 0, 1, 0);
 386         return 0;
 387 }
 388
 389 int check_extent_refs(struct btrfs_root *root,
 390                       struct radix_tree_root *extent_radix)
 391 {
 392         struct extent_record *rec[64];
 393         int i;
 394         int ret;
 395         int err = 0;
 396
 397         while(1) {
 398                 ret = radix_tree_gang_lookup(extent_radix, (void **)rec, 0,
 399                                              ARRAY_SIZE(rec));
 400                 if (!ret)
 401                         break;
 402                 for (i = 0; i < ret; i++) {
 403                         if (rec[i]->refs != rec[i]->extent_item_refs) {
 404                                 fprintf(stderr, "ref mismatch on [%Lu %Lu] ",
 405                                         rec[i]->start, rec[i]->nr);
 406                                 fprintf(stderr, "extent item %u, found %u\n",
 407                                         rec[i]->extent_item_refs,
 408                                         rec[i]->refs);
 409                                 err = 1;
 410                         }
 411                         radix_tree_delete(extent_radix, rec[i]->start);
 412                         free(rec[i]);
 413                 }
 414         }
 415         return err;
 416 }
 417
 418 int main(int ac, char **av) {
 419         struct btrfs_super_block super;
 420         struct btrfs_root *root;
 421         struct radix_tree_root extent_radix;
 422         struct radix_tree_root seen;
 423         struct radix_tree_root pending;
 424         struct radix_tree_root reada;
 425         struct radix_tree_root nodes;
 426         struct btrfs_path path;
 427         struct btrfs_key key;
 428         struct btrfs_key found_key;
 429         int ret;
 430         u64 last = 0;
 431         unsigned long *bits;
 432         int bits_nr;
 433         struct btrfs_leaf *leaf;
 434         int slot;
 435         struct btrfs_root_item *ri;
 436
 437         radix_tree_init();
 438
 439
 440         INIT_RADIX_TREE(&extent_radix, GFP_NOFS);
 441         init_bit_radix(&seen);
 442         init_bit_radix(&pending);
 443         init_bit_radix(&reada);
 444         init_bit_radix(&nodes);
 445
 446         root = open_ctree(av[1], &super);
 447
 448         bits_nr = 1024 * 1024 / root->blocksize;
 449         bits = malloc(bits_nr * sizeof(unsigned long));
 450         if (!bits) {
 451                 perror("malloc");
 452                 exit(1);
 453         }
 454
 455         add_root_to_pending(root->fs_info->tree_root->node, bits, bits_nr,
 456                             &extent_radix, &pending, &seen, &reada, &nodes);
 457
 458         btrfs_init_path(&path);
 459         key.offset = 0;
 460         key.objectid = 0;
 461         key.flags = 0;
 462         btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
 463         ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
 464                                         &key, &path, 0, 0);
 465         BUG_ON(ret < 0);
 466         while(1) {
 467                 leaf = &path.nodes[0]->leaf;
 468                 slot = path.slots[0];
 469                 if (slot >= btrfs_header_nritems(&leaf->header)) {
 470                         ret = btrfs_next_leaf(root, &path);
 471                         if (ret != 0)
 472                                 break;
 473                         leaf = &path.nodes[0]->leaf;
 474                         slot = path.slots[0];
 475                 }
 476                 btrfs_disk_key_to_cpu(&found_key,
 477                                       &leaf->items[path.slots[0]].key);
 478                 if (btrfs_key_type(&found_key) == BTRFS_ROOT_ITEM_KEY) {
 479                         struct btrfs_buffer *buf;
 480                         ri = btrfs_item_ptr(leaf, path.slots[0],
 481                                             struct btrfs_root_item);
 482                         buf = read_tree_block(root->fs_info->tree_root,
 483                                               btrfs_root_blocknr(ri));
 484                         add_root_to_pending(buf, bits, bits_nr, &extent_radix,
 485                                             &pending, &seen, &reada, &nodes);
 486                         btrfs_block_release(root->fs_info->tree_root, buf);
 487                 }
 488                 path.slots[0]++;
 489         }
 490         btrfs_release_path(root, &path);
 491         while(1) {
 492                 ret = run_next_block(root, bits, bits_nr, &last, &pending,
 493                                      &seen, &reada, &nodes, &extent_radix);
 494                 if (ret != 0)
 495                         break;
 496         }
 497         ret = check_extent_refs(root, &extent_radix);
 498         close_ctree(root, &super);
 499         printf("found %Lu blocks used err is %d\n", blocks_used, ret);
 500         printf("total csum bytes: %Lu\n", total_csum_bytes);
 501         printf("total tree blocks: %Lu\n", total_btree_blocks);
 502         printf("btree space waste bytes: %Lu\n", btree_space_waste);
 503         return ret;
 504 }