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         struct btrfs_disk_key node_key;
  22         u64 start;
  23         u64 nr;
  24         u64 owner;
  25         u32 refs;
  26         u32 extent_item_refs;
  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 check_block(struct btrfs_root *root,
 102                        struct radix_tree_root *extent_radix,
 103                        struct btrfs_buffer *buf)
 104 {
 105         struct extent_record *rec;
 106
 107         rec = radix_tree_lookup(extent_radix, buf->blocknr);
 108         if (!rec)
 109                 return 1;
 110         if (btrfs_is_leaf(&buf->node)) {
 111                 return check_leaf(root, &rec->parent_key, &buf->leaf);
 112         } else {
 113                 return check_node(root, &rec->parent_key, &buf->node);
 114         }
 115         return 1;
 116 }
 117
 118 static int add_extent_rec(struct radix_tree_root *extent_radix,
 119                           struct btrfs_disk_key *parent_key,
 120                           u64 ref, u64 start, u64 nr, u64 owner,
 121                           u32 extent_item_refs, int inc_ref)
 122 {
 123         struct extent_record *rec;
 124         int ret = 0;
 125         rec = radix_tree_lookup(extent_radix, start);
 126         if (rec) {
 127                 if (inc_ref)
 128                         rec->refs++;
 129                 if (start != rec->start) {
 130                         fprintf(stderr, "warning, start mismatch %Lu %Lu\n",
 131                                 rec->start, start);
 132                         ret = 1;
 133                 }
 134                 if (extent_item_refs)
 135                         rec->extent_item_refs = extent_item_refs;
 136                 return ret;
 137         }
 138         rec = malloc(sizeof(*rec));
 139         if (start == 0)
 140                 extent_item_refs = 0;
 141         rec->start = start;
 142         rec->nr = nr;
 143         rec->owner = owner;
 144
 145         if (inc_ref)
 146                 rec->refs = 1;
 147         else
 148                 rec->refs = 0;
 149
 150         if (extent_item_refs)
 151                 rec->extent_item_refs = extent_item_refs;
 152         else
 153                 rec->extent_item_refs = 0;
 154
 155         if (parent_key)
 156                 memcpy(&rec->parent_key, parent_key, sizeof(*parent_key));
 157         else
 158                 memset(&rec->parent_key, 0, sizeof(*parent_key));
 159
 160         ret = radix_tree_insert(extent_radix, start, rec);
 161         BUG_ON(ret);
 162         blocks_used += nr;
 163         return ret;
 164 }
 165
 166 static int add_pending(struct radix_tree_root *pending,
 167                        struct radix_tree_root *seen, u64 blocknr)
 168 {
 169         if (test_radix_bit(seen, blocknr))
 170                 return -EEXIST;
 171         set_radix_bit(pending, blocknr);
 172         set_radix_bit(seen, blocknr);
 173         return 0;
 174 }
 175 static int pick_next_pending(struct radix_tree_root *pending,
 176                         struct radix_tree_root *reada,
 177                         struct radix_tree_root *nodes,
 178                         u64 last, unsigned long *bits, int bits_nr)
 179 {
 180         unsigned long node_start = last;
 181         int ret;
 182         ret = find_first_radix_bit(reada, bits, 0, 1);
 183         if (ret && ret > 16)
 184                 return ret;
 185         if (node_start > 8)
 186                 node_start -= 8;
 187         ret = find_first_radix_bit(nodes, bits, node_start, bits_nr);
 188         if (!ret)
 189                 ret = find_first_radix_bit(nodes, bits, 0, bits_nr);
 190         if (ret)
 191                 return ret;
 192         return find_first_radix_bit(pending, bits, 0, bits_nr);
 193 }
 194 static struct btrfs_buffer reada_buf;
 195
 196 static int run_next_block(struct btrfs_root *root,
 197                           unsigned long *bits,
 198                           int bits_nr,
 199                           u64 *last,
 200                           struct radix_tree_root *pending,
 201                           struct radix_tree_root *seen,
 202                           struct radix_tree_root *reada,
 203                           struct radix_tree_root *nodes,
 204                           struct radix_tree_root *extent_radix)
 205 {
 206         struct btrfs_buffer *buf;
 207         u64 blocknr;
 208         int ret;
 209         int i;
 210         int nritems;
 211         struct btrfs_leaf *leaf;
 212         struct btrfs_node *node;
 213         u64 last_block = 0;
 214         ret = pick_next_pending(pending, reada, nodes, *last, bits, bits_nr);
 215         if (ret == 0) {
 216                 return 1;
 217         }
 218         for(i = 0; i < ret; i++) {
 219                 u64 offset;
 220                 if (test_radix_bit(reada, bits[i]))
 221                         continue;
 222                 set_radix_bit(reada, bits[i]);
 223                 btrfs_map_bh_to_logical(root, &reada_buf, bits[i]);
 224                 offset = reada_buf.dev_blocknr * root->blocksize;
 225                 last_block = bits[i];
 226                 readahead(reada_buf.fd, offset, root->blocksize);
 227         }
 228         *last = bits[0];
 229         blocknr = bits[0];
 230         clear_radix_bit(pending, blocknr);
 231         clear_radix_bit(reada, blocknr);
 232         clear_radix_bit(nodes, blocknr);
 233         buf = read_tree_block(root, blocknr);
 234         nritems = btrfs_header_nritems(&buf->node.header);
 235         ret = check_block(root, extent_radix, buf);
 236         if (ret) {
 237                 fprintf(stderr, "bad block %Lu\n", blocknr);
 238         }
 239         if (btrfs_is_leaf(&buf->node)) {
 240                 leaf = &buf->leaf;
 241                 btree_space_waste += btrfs_leaf_free_space(root, leaf);
 242                 for (i = 0; i < nritems; i++) {
 243                         struct btrfs_file_extent_item *fi;
 244                         if (btrfs_disk_key_type(&leaf->items[i].key) ==
 245                             BTRFS_EXTENT_ITEM_KEY) {
 246                                 struct btrfs_key found;
 247                                 struct btrfs_extent_item *ei;
 248                                 btrfs_disk_key_to_cpu(&found,
 249                                                       &leaf->items[i].key);
 250                                 ei = btrfs_item_ptr(leaf, i,
 251                                                     struct btrfs_extent_item);
 252                                 add_extent_rec(extent_radix, NULL, 0,
 253                                                found.objectid,
 254                                                found.offset,
 255                                                btrfs_extent_owner(ei),
 256                                                btrfs_extent_refs(ei), 0);
 257                                 continue;
 258                         }
 259                         if (btrfs_disk_key_type(&leaf->items[i].key) ==
 260                             BTRFS_CSUM_ITEM_KEY) {
 261                                 total_csum_bytes +=
 262                                         btrfs_item_size(leaf->items + i);
 263                                 continue;
 264                         }
 265                         if (btrfs_disk_key_type(&leaf->items[i].key) !=
 266                             BTRFS_EXTENT_DATA_KEY)
 267                                 continue;
 268                         fi = btrfs_item_ptr(leaf, i,
 269                                             struct btrfs_file_extent_item);
 270                         if (btrfs_file_extent_type(fi) !=
 271                             BTRFS_FILE_EXTENT_REG)
 272                                 continue;
 273                         ret = add_extent_rec(extent_radix, NULL, blocknr,
 274                                    btrfs_file_extent_disk_blocknr(fi),
 275                                    btrfs_file_extent_disk_num_blocks(fi),
 276                                    btrfs_disk_key_objectid(&leaf->items[i].key),
 277                                    0, 1);
 278                         BUG_ON(ret);
 279                 }
 280         } else {
 281                 int level;
 282                 node = &buf->node;
 283                 level = btrfs_header_level(&node->header);
 284                 for (i = 0; i < nritems; i++) {
 285                         u64 ptr = btrfs_node_blockptr(node, i);
 286                         ret = add_extent_rec(extent_radix,
 287                                              &node->ptrs[i].key,
 288                                              blocknr, ptr, 1,
 289                                              btrfs_header_owner(&node->header),
 290                                              0, 1);
 291                         BUG_ON(ret);
 292                         if (level > 1) {
 293                                 add_pending(nodes, seen, ptr);
 294                         } else {
 295                                 add_pending(pending, seen, ptr);
 296                         }
 297                 }
 298                 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) -
 299                                       nritems) * sizeof(struct btrfs_key_ptr);
 300         }
 301         btrfs_block_release(root, buf);
 302         total_btree_blocks++;
 303         return 0;
 304 }
 305
 306 static int add_root_to_pending(struct btrfs_buffer *buf,
 307                                unsigned long *bits,
 308                                int bits_nr,
 309                                struct radix_tree_root *extent_radix,
 310                                struct radix_tree_root *pending,
 311                                struct radix_tree_root *seen,
 312                                struct radix_tree_root *reada,
 313                                struct radix_tree_root *nodes)
 314 {
 315         if (btrfs_header_level(&buf->node.header) > 0)
 316                 add_pending(nodes, seen, buf->blocknr);
 317         else
 318                 add_pending(pending, seen, buf->blocknr);
 319         add_extent_rec(extent_radix, NULL, 0, buf->blocknr, 1,
 320                        btrfs_header_owner(&buf->node.header), 0, 1);
 321         return 0;
 322 }
 323
 324 int check_extent_refs(struct btrfs_root *root,
 325                       struct radix_tree_root *extent_radix)
 326 {
 327         struct extent_record *rec[64];
 328         int i;
 329         int ret;
 330         int err = 0;
 331
 332         while(1) {
 333                 ret = radix_tree_gang_lookup(extent_radix, (void **)rec, 0,
 334                                              ARRAY_SIZE(rec));
 335                 if (!ret)
 336                         break;
 337                 for (i = 0; i < ret; i++) {
 338                         if (rec[i]->refs != rec[i]->extent_item_refs) {
 339                                 fprintf(stderr, "ref mismatch on [%Lu %Lu] ",
 340                                         rec[i]->start, rec[i]->nr);
 341                                 fprintf(stderr, "extent item %u, found %u\n",
 342                                         rec[i]->extent_item_refs,
 343                                         rec[i]->refs);
 344                                 err = 1;
 345                         }
 346                         radix_tree_delete(extent_radix, rec[i]->start);
 347                         free(rec[i]);
 348                 }
 349         }
 350         return err;
 351 }
 352
 353 int main(int ac, char **av) {
 354         struct btrfs_super_block super;
 355         struct btrfs_root *root;
 356         struct radix_tree_root extent_radix;
 357         struct radix_tree_root seen;
 358         struct radix_tree_root pending;
 359         struct radix_tree_root reada;
 360         struct radix_tree_root nodes;
 361         struct btrfs_path path;
 362         struct btrfs_key key;
 363         struct btrfs_key found_key;
 364         int ret;
 365         u64 last = 0;
 366         unsigned long *bits;
 367         int bits_nr;
 368         struct btrfs_leaf *leaf;
 369         int slot;
 370         struct btrfs_root_item *ri;
 371
 372         radix_tree_init();
 373
 374
 375         INIT_RADIX_TREE(&extent_radix, GFP_NOFS);
 376         init_bit_radix(&seen);
 377         init_bit_radix(&pending);
 378         init_bit_radix(&reada);
 379         init_bit_radix(&nodes);
 380
 381         root = open_ctree(av[1], &super);
 382
 383         bits_nr = 1024 * 1024 / root->blocksize;
 384         bits = malloc(bits_nr * sizeof(unsigned long));
 385         if (!bits) {
 386                 perror("malloc");
 387                 exit(1);
 388         }
 389
 390         add_root_to_pending(root->fs_info->tree_root->node, bits, bits_nr,
 391                             &extent_radix, &pending, &seen, &reada, &nodes);
 392         add_root_to_pending(root->fs_info->dev_root->node, bits, bits_nr,
 393                             &extent_radix, &pending, &seen, &reada, &nodes);
 394
 395         btrfs_init_path(&path);
 396         key.offset = 0;
 397         key.objectid = 0;
 398         key.flags = 0;
 399         btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
 400         ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
 401                                         &key, &path, 0, 0);
 402         BUG_ON(ret < 0);
 403         while(1) {
 404                 leaf = &path.nodes[0]->leaf;
 405                 slot = path.slots[0];
 406                 if (slot >= btrfs_header_nritems(&leaf->header)) {
 407                         ret = btrfs_next_leaf(root, &path);
 408                         if (ret != 0)
 409                                 break;
 410                         leaf = &path.nodes[0]->leaf;
 411                         slot = path.slots[0];
 412                 }
 413                 btrfs_disk_key_to_cpu(&found_key,
 414                                       &leaf->items[path.slots[0]].key);
 415                 if (btrfs_key_type(&found_key) == BTRFS_ROOT_ITEM_KEY) {
 416                         struct btrfs_buffer *buf;
 417                         ri = btrfs_item_ptr(leaf, path.slots[0],
 418                                             struct btrfs_root_item);
 419                         buf = read_tree_block(root->fs_info->tree_root,
 420                                               btrfs_root_blocknr(ri));
 421                         add_root_to_pending(buf, bits, bits_nr, &extent_radix,
 422                                             &pending, &seen, &reada, &nodes);
 423                         btrfs_block_release(root->fs_info->tree_root, buf);
 424                 }
 425                 path.slots[0]++;
 426         }
 427         btrfs_release_path(root, &path);
 428         while(1) {
 429                 ret = run_next_block(root, bits, bits_nr, &last, &pending,
 430                                      &seen, &reada, &nodes, &extent_radix);
 431                 if (ret != 0)
 432                         break;
 433         }
 434         ret = check_extent_refs(root, &extent_radix);
 435         close_ctree(root, &super);
 436         printf("found %Lu blocks used err is %d\n", blocks_used, ret);
 437         printf("total csum bytes: %Lu\n", total_csum_bytes);
 438         printf("total tree blocks: %Lu\n", total_btree_blocks);
 439         printf("btree space waste bytes: %Lu\n", btree_space_waste);
 440         return ret;
 441 }