btrfsck.c

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