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         u8 type;
  23 };
  24
  25 static int check_node(struct btrfs_root *root,
  26                       struct btrfs_disk_key *parent_key,
  27                       struct btrfs_node *node)
  28 {
  29         int i;
  30         u32 nritems = btrfs_header_nritems(&node->header);
  31
  32         if (nritems == 0 || nritems > BTRFS_NODEPTRS_PER_BLOCK(root))
  33                 return 1;
  34         if (parent_key->flags) {
  35                 if (memcmp(parent_key, &node->ptrs[0].key,
  36                               sizeof(struct btrfs_disk_key)))
  37                         return 1;
  38         }
  39         for (i = 0; nritems > 1 && i < nritems - 2; i++) {
  40                 struct btrfs_key cpukey;
  41                 btrfs_disk_key_to_cpu(&cpukey, &node->ptrs[i + 1].key);
  42                 if (btrfs_comp_keys(&node->ptrs[i].key, &cpukey) >= 0)
  43                         return 1;
  44         }
  45         return 0;
  46 }
  47
  48 static int check_leaf(struct btrfs_root *root,
  49                       struct btrfs_disk_key *parent_key,
  50                       struct btrfs_leaf *leaf)
  51 {
  52         int i;
  53         u32 nritems = btrfs_header_nritems(&leaf->header);
  54
  55         if (btrfs_header_level(&leaf->header) != 0) {
  56                 fprintf(stderr, "leaf is not a leaf %Lu\n",
  57                         btrfs_header_blocknr(&leaf->header));
  58                 return 1;
  59         }
  60         if (btrfs_leaf_free_space(root, leaf) < 0) {
  61                 fprintf(stderr, "leaf free space incorrect %Lu %d\n",
  62                         btrfs_header_blocknr(&leaf->header),
  63                         btrfs_leaf_free_space(root, leaf));
  64                 return 1;
  65         }
  66
  67         if (nritems == 0)
  68                 return 0;
  69
  70         if (parent_key->flags) {
  71                 if (memcmp(parent_key, &leaf->items[0].key,
  72                        sizeof(struct btrfs_disk_key))) {
  73                         fprintf(stderr, "leaf parent key incorrect %Lu\n",
  74                                 btrfs_header_blocknr(&leaf->header));
  75                         return 1;
  76                 }
  77         }
  78         for (i = 0; nritems > 1 && i < nritems - 2; i++) {
  79                 struct btrfs_key cpukey;
  80                 btrfs_disk_key_to_cpu(&cpukey, &leaf->items[i + 1].key);
  81                 if (btrfs_comp_keys(&leaf->items[i].key,
  82                                  &cpukey) >= 0)
  83                         return 1;
  84                 if (btrfs_item_offset(leaf->items + i) !=
  85                         btrfs_item_end(leaf->items + i + 1))
  86                         return 1;
  87                 if (i == 0) {
  88                         if (btrfs_item_offset(leaf->items + i) +
  89                                btrfs_item_size(leaf->items + i) !=
  90                                BTRFS_LEAF_DATA_SIZE(root))
  91                                 return 1;
  92                 }
  93         }
  94         return 0;
  95 }
  96
  97 static int check_block(struct btrfs_root *root,
  98                        struct radix_tree_root *extent_radix,
  99                        struct btrfs_buffer *buf)
 100 {
 101         struct extent_record *rec;
 102
 103         rec = radix_tree_lookup(extent_radix, buf->blocknr);
 104         if (!rec)
 105                 return 1;
 106         if (btrfs_is_leaf(&buf->node)) {
 107                 return check_leaf(root, &rec->parent_key, &buf->leaf);
 108         } else {
 109                 return check_node(root, &rec->parent_key, &buf->node);
 110         }
 111         return 1;
 112 }
 113
 114 static int add_extent_rec(struct radix_tree_root *extent_radix,
 115                           struct btrfs_disk_key *parent_key,
 116                           u64 ref, u64 start, u64 nr, u64 owner, u8 type,
 117                           u32 extent_item_refs, int inc_ref)
 118 {
 119         struct extent_record *rec;
 120         int ret = 0;
 121         rec = radix_tree_lookup(extent_radix, start);
 122         if (rec) {
 123                 if (inc_ref)
 124                         rec->refs++;
 125                 if (owner != rec->owner) {
 126                         fprintf(stderr, "warning, owner mismatch %Lu %Lu %Lu\n",
 127                                 start, owner, rec->owner);
 128                         ret = 1;
 129                 }
 130                 if (start != rec->start) {
 131                         fprintf(stderr, "warning, start mismatch %Lu %Lu\n",
 132                                 rec->start, start);
 133                         ret = 1;
 134                 }
 135                 if (type != rec->type) {
 136                         fprintf(stderr, "type mismatch block %Lu %d %d\n",
 137                                 start, type, rec->type);
 138                         ret = 1;
 139                 }
 140                 if (extent_item_refs)
 141                         rec->extent_item_refs = extent_item_refs;
 142                 return ret;
 143         }
 144         rec = malloc(sizeof(*rec));
 145         if (start == 0)
 146                 extent_item_refs = 0;
 147         rec->start = start;
 148         rec->nr = nr;
 149         rec->owner = owner;
 150         rec->type = type;
 151
 152         if (inc_ref)
 153                 rec->refs = 1;
 154         else
 155                 rec->refs = 0;
 156
 157         if (extent_item_refs)
 158                 rec->extent_item_refs = extent_item_refs;
 159         else
 160                 rec->extent_item_refs = 0;
 161
 162         if (parent_key)
 163                 memcpy(&rec->parent_key, parent_key, sizeof(*parent_key));
 164         else
 165                 memset(&rec->parent_key, 0, sizeof(*parent_key));
 166
 167         ret = radix_tree_insert(extent_radix, start, rec);
 168         BUG_ON(ret);
 169         blocks_used += nr;
 170         return ret;
 171 }
 172
 173 static int add_pending(struct radix_tree_root *pending,
 174                        struct radix_tree_root *seen, u64 blocknr)
 175 {
 176         if (test_radix_bit(seen, blocknr))
 177                 return -EEXIST;
 178         set_radix_bit(pending, blocknr);
 179         set_radix_bit(seen, blocknr);
 180         return 0;
 181 }
 182
 183 static int pick_next_pending(struct radix_tree_root *pending,
 184                         struct radix_tree_root *reada,
 185                         struct radix_tree_root *nodes,
 186                         u64 last, unsigned long *bits, int bits_nr)
 187 {
 188         unsigned long node_start = last;
 189         int ret;
 190         ret = find_first_radix_bit(reada, bits, 0, 1);
 191         if (ret)
 192                 return ret;
 193         if (node_start > 8)
 194                 node_start -= 8;
 195         ret = find_first_radix_bit(nodes, bits, node_start, bits_nr);
 196         if (!ret)
 197                 ret = find_first_radix_bit(nodes, bits, 0, bits_nr);
 198         if (ret)
 199                 return ret;
 200         return find_first_radix_bit(pending, bits, 0, bits_nr);
 201 }
 202
 203 static struct btrfs_buffer reada_buf;
 204
 205 static int run_next_block(struct btrfs_root *root,
 206                           unsigned long *bits,
 207                           int bits_nr,
 208                           u64 *last,
 209                           struct radix_tree_root *pending,
 210                           struct radix_tree_root *seen,
 211                           struct radix_tree_root *reada,
 212                           struct radix_tree_root *nodes,
 213                           struct radix_tree_root *extent_radix)
 214 {
 215         struct btrfs_buffer *buf;
 216         u64 blocknr;
 217         int ret;
 218         int i;
 219         int nritems;
 220         struct btrfs_leaf *leaf;
 221         struct btrfs_node *node;
 222         u64 last_block = 0;
 223
 224         ret = pick_next_pending(pending, reada, nodes, *last, bits, bits_nr);
 225         if (ret == 0) {
 226                 return 1;
 227         }
 228         for(i = 0; i < ret; i++) {
 229                 u64 offset;
 230                 if (test_radix_bit(reada, bits[i]))
 231                         continue;
 232                 set_radix_bit(reada, bits[i]);
 233                 btrfs_map_bh_to_logical(root, &reada_buf, bits[i]);
 234                 offset = reada_buf.dev_blocknr * root->blocksize;
 235                 last_block = bits[i];
 236                 readahead(reada_buf.fd, offset, root->blocksize);
 237         }
 238
 239         *last = bits[0];
 240         blocknr = bits[0];
 241         clear_radix_bit(pending, blocknr);
 242         clear_radix_bit(reada, blocknr);
 243         clear_radix_bit(nodes, blocknr);
 244         buf = read_tree_block(root, blocknr);
 245         nritems = btrfs_header_nritems(&buf->node.header);
 246         ret = check_block(root, extent_radix, buf);
 247         if (ret) {
 248                 fprintf(stderr, "bad block %Lu\n", blocknr);
 249         }
 250         if (btrfs_is_leaf(&buf->node)) {
 251                 leaf = &buf->leaf;
 252                 for (i = 0; i < nritems; i++) {
 253                         struct btrfs_file_extent_item *fi;
 254                         if (btrfs_disk_key_type(&leaf->items[i].key) ==
 255                             BTRFS_EXTENT_ITEM_KEY) {
 256                                 struct btrfs_key found;
 257                                 struct btrfs_extent_item *ei;
 258                                 btrfs_disk_key_to_cpu(&found,
 259                                                       &leaf->items[i].key);
 260                                 ei = btrfs_item_ptr(leaf, i,
 261                                                     struct btrfs_extent_item);
 262                                 add_extent_rec(extent_radix, NULL, 0,
 263                                                found.objectid,
 264                                                found.offset,
 265                                                btrfs_extent_owner(ei),
 266                                                btrfs_extent_type(ei),
 267                                                btrfs_extent_refs(ei), 0);
 268                                 continue;
 269                         }
 270                         if (btrfs_disk_key_type(&leaf->items[i].key) !=
 271                             BTRFS_EXTENT_DATA_KEY)
 272                                 continue;
 273                         fi = btrfs_item_ptr(leaf, i,
 274                                             struct btrfs_file_extent_item);
 275                         if (btrfs_file_extent_type(fi) !=
 276                             BTRFS_FILE_EXTENT_REG)
 277                                 continue;
 278                         ret = add_extent_rec(extent_radix, NULL, blocknr,
 279                                    btrfs_file_extent_disk_blocknr(fi),
 280                                    btrfs_file_extent_disk_num_blocks(fi),
 281                                    btrfs_disk_key_objectid(&leaf->items[i].key),
 282                                    BTRFS_EXTENT_FILE, 0, 1);
 283                         BUG_ON(ret);
 284                 }
 285         } else {
 286                 int level;
 287                 node = &buf->node;
 288                 level = btrfs_header_level(&node->header);
 289                 for (i = 0; i < nritems; i++) {
 290                         u64 ptr = btrfs_node_blockptr(node, i);
 291                         ret = add_extent_rec(extent_radix,
 292                                              &node->ptrs[i].key,
 293                                              blocknr, ptr, 1,
 294                                              btrfs_header_owner(&node->header),
 295                                              BTRFS_EXTENT_TREE, 0, 1);
 296                         BUG_ON(ret);
 297                         if (level > 1) {
 298                                 add_pending(nodes, seen, ptr);
 299                         } else {
 300                                 add_pending(pending, seen, ptr);
 301                         }
 302                 }
 303         }
 304         btrfs_block_release(root, buf);
 305         return 0;
 306 }
 307
 308 static int add_root_to_pending(struct btrfs_root *root,
 309                                unsigned long *bits,
 310                                int bits_nr,
 311                                struct radix_tree_root *extent_radix,
 312                                struct radix_tree_root *pending,
 313                                struct radix_tree_root *seen,
 314                                struct radix_tree_root *reada,
 315                                struct radix_tree_root *nodes)
 316 {
 317         add_pending(pending, seen, root->node->blocknr);
 318         add_extent_rec(extent_radix, NULL, 0, root->node->blocknr, 1,
 319                        btrfs_header_owner(&root->node->node.header),
 320                        BTRFS_EXTENT_TREE, 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         int ret;
 362         u64 last = 0;
 363         unsigned long *bits;
 364         int bits_nr;
 365
 366         radix_tree_init();
 367
 368
 369         INIT_RADIX_TREE(&extent_radix, GFP_NOFS);
 370         init_bit_radix(&seen);
 371         init_bit_radix(&pending);
 372         init_bit_radix(&reada);
 373         init_bit_radix(&nodes);
 374
 375         root = open_ctree(av[1], &super);
 376
 377         bits_nr = 1024 * 1024 / root->blocksize;
 378         bits = malloc(bits_nr * sizeof(unsigned long));
 379         if (!bits) {
 380                 perror("malloc");
 381                 exit(1);
 382         }
 383
 384         add_root_to_pending(root, bits, bits_nr, &extent_radix,
 385                             &pending, &seen, &reada, &nodes);
 386         add_root_to_pending(root->fs_info->tree_root, bits, bits_nr,
 387                             &extent_radix, &pending, &seen, &reada, &nodes);
 388         add_root_to_pending(root->fs_info->dev_root, bits, bits_nr,
 389                             &extent_radix, &pending, &seen, &reada, &nodes);
 390         add_root_to_pending(root->fs_info->extent_root, bits, bits_nr,
 391                             &extent_radix, &pending, &seen, &reada, &nodes);
 392         while(1) {
 393                 ret = run_next_block(root, bits, bits_nr, &last, &pending,
 394                                      &seen, &reada, &nodes, &extent_radix);
 395                 if (ret != 0)
 396                         break;
 397         }
 398         ret = check_extent_refs(root, &extent_radix);
 399         close_ctree(root, &super);
 400         printf("found %Lu blocks used err is %d\n", blocks_used, ret);
 401         return ret;
 402 }