find-root.c

   1 /*
   2  * Copyright (C) 2011 Red Hat.  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 <unistd.h>
  24 #include <fcntl.h>
  25 #include <sys/stat.h>
  26 #include <zlib.h>
  27 #include "kerncompat.h"
  28 #include "ctree.h"
  29 #include "disk-io.h"
  30 #include "print-tree.h"
  31 #include "transaction.h"
  32 #include "list.h"
  33 #include "version.h"
  34 #include "volumes.h"
  35 #include "utils.h"
  36 #include "crc32c.h"
  37
  38 static int verbose = 0;
  39 static u16 csum_size = 0;
  40 static u64 search_objectid = BTRFS_ROOT_TREE_OBJECTID;
  41
  42 static void usage()
  43 {
  44         fprintf(stderr, "Usage: find-roots [-v] <device>\n");
  45 }
  46
  47 int csum_block(void *buf, u32 len)
  48 {
  49         char *result;
  50         u32 crc = ~(u32)0;
  51         int ret = 0;
  52
  53         result = malloc(csum_size * sizeof(char));
  54         if (!result) {
  55                 fprintf(stderr, "No memory\n");
  56                 return 1;
  57         }
  58
  59         len -= BTRFS_CSUM_SIZE;
  60         crc = crc32c(crc, buf + BTRFS_CSUM_SIZE, len);
  61         btrfs_csum_final(crc, result);
  62
  63         if (memcmp(buf, result, csum_size))
  64                 ret = 1;
  65         free(result);
  66         return ret;
  67 }
  68
  69 static int __setup_root(u32 nodesize, u32 leafsize, u32 sectorsize,
  70                         u32 stripesize, struct btrfs_root *root,
  71                         struct btrfs_fs_info *fs_info, u64 objectid)
  72 {
  73         root->node = NULL;
  74         root->commit_root = NULL;
  75         root->sectorsize = sectorsize;
  76         root->nodesize = nodesize;
  77         root->leafsize = leafsize;
  78         root->stripesize = stripesize;
  79         root->ref_cows = 0;
  80         root->track_dirty = 0;
  81
  82         root->fs_info = fs_info;
  83         root->objectid = objectid;
  84         root->last_trans = 0;
  85         root->highest_inode = 0;
  86         root->last_inode_alloc = 0;
  87
  88         INIT_LIST_HEAD(&root->dirty_list);
  89         memset(&root->root_key, 0, sizeof(root->root_key));
  90         memset(&root->root_item, 0, sizeof(root->root_item));
  91         root->root_key.objectid = objectid;
  92         return 0;
  93 }
  94
  95 static int close_all_devices(struct btrfs_fs_info *fs_info)
  96 {
  97         struct list_head *list;
  98         struct list_head *next;
  99         struct btrfs_device *device;
 100
 101         return 0;
 102
 103         list = &fs_info->fs_devices->devices;
 104         list_for_each(next, list) {
 105                 device = list_entry(next, struct btrfs_device, dev_list);
 106                 close(device->fd);
 107         }
 108         return 0;
 109 }
 110
 111 static struct btrfs_root *open_ctree_broken(int fd, const char *device)
 112 {
 113         u32 sectorsize;
 114         u32 nodesize;
 115         u32 leafsize;
 116         u32 blocksize;
 117         u32 stripesize;
 118         u64 generation;
 119         struct btrfs_root *tree_root = malloc(sizeof(struct btrfs_root));
 120         struct btrfs_root *extent_root = malloc(sizeof(struct btrfs_root));
 121         struct btrfs_root *chunk_root = malloc(sizeof(struct btrfs_root));
 122         struct btrfs_root *dev_root = malloc(sizeof(struct btrfs_root));
 123         struct btrfs_root *csum_root = malloc(sizeof(struct btrfs_root));
 124         struct btrfs_fs_info *fs_info = malloc(sizeof(*fs_info));
 125         int ret;
 126         struct btrfs_super_block *disk_super;
 127         struct btrfs_fs_devices *fs_devices = NULL;
 128         u64 total_devs;
 129         u64 features;
 130
 131         ret = btrfs_scan_one_device(fd, device, &fs_devices,
 132                                     &total_devs, BTRFS_SUPER_INFO_OFFSET);
 133
 134         if (ret) {
 135                 fprintf(stderr, "No valid Btrfs found on %s\n", device);
 136                 goto out;
 137         }
 138
 139         if (total_devs != 1) {
 140                 ret = btrfs_scan_for_fsid(fs_devices, total_devs, 1);
 141                 if (ret)
 142                         goto out;
 143         }
 144
 145         memset(fs_info, 0, sizeof(*fs_info));
 146         fs_info->tree_root = tree_root;
 147         fs_info->extent_root = extent_root;
 148         fs_info->chunk_root = chunk_root;
 149         fs_info->dev_root = dev_root;
 150         fs_info->csum_root = csum_root;
 151
 152         fs_info->readonly = 1;
 153
 154         extent_io_tree_init(&fs_info->extent_cache);
 155         extent_io_tree_init(&fs_info->free_space_cache);
 156         extent_io_tree_init(&fs_info->block_group_cache);
 157         extent_io_tree_init(&fs_info->pinned_extents);
 158         extent_io_tree_init(&fs_info->pending_del);
 159         extent_io_tree_init(&fs_info->extent_ins);
 160         cache_tree_init(&fs_info->fs_root_cache);
 161
 162         cache_tree_init(&fs_info->mapping_tree.cache_tree);
 163
 164         mutex_init(&fs_info->fs_mutex);
 165         fs_info->fs_devices = fs_devices;
 166         INIT_LIST_HEAD(&fs_info->dirty_cowonly_roots);
 167         INIT_LIST_HEAD(&fs_info->space_info);
 168
 169         __setup_root(4096, 4096, 4096, 4096, tree_root,
 170                      fs_info, BTRFS_ROOT_TREE_OBJECTID);
 171
 172         ret = btrfs_open_devices(fs_devices, O_RDONLY);
 173         if (ret)
 174                 goto out_cleanup;
 175
 176         fs_info->super_bytenr = BTRFS_SUPER_INFO_OFFSET;
 177         disk_super = &fs_info->super_copy;
 178         ret = btrfs_read_dev_super(fs_devices->latest_bdev,
 179                                    disk_super, BTRFS_SUPER_INFO_OFFSET);
 180         if (ret) {
 181                 printk("No valid btrfs found\n");
 182                 goto out_devices;
 183         }
 184
 185         memcpy(fs_info->fsid, &disk_super->fsid, BTRFS_FSID_SIZE);
 186
 187
 188         features = btrfs_super_incompat_flags(disk_super) &
 189                    ~BTRFS_FEATURE_INCOMPAT_SUPP;
 190         if (features) {
 191                 printk("couldn't open because of unsupported "
 192                        "option features (%Lx).\n", features);
 193                 goto out_devices;
 194         }
 195
 196         features = btrfs_super_incompat_flags(disk_super);
 197         if (!(features & BTRFS_FEATURE_INCOMPAT_MIXED_BACKREF)) {
 198                 features |= BTRFS_FEATURE_INCOMPAT_MIXED_BACKREF;
 199                 btrfs_set_super_incompat_flags(disk_super, features);
 200         }
 201
 202         nodesize = btrfs_super_nodesize(disk_super);
 203         leafsize = btrfs_super_leafsize(disk_super);
 204         sectorsize = btrfs_super_sectorsize(disk_super);
 205         stripesize = btrfs_super_stripesize(disk_super);
 206         tree_root->nodesize = nodesize;
 207         tree_root->leafsize = leafsize;
 208         tree_root->sectorsize = sectorsize;
 209         tree_root->stripesize = stripesize;
 210
 211         ret = btrfs_read_sys_array(tree_root);
 212         if (ret)
 213                 goto out_devices;
 214         blocksize = btrfs_level_size(tree_root,
 215                                      btrfs_super_chunk_root_level(disk_super));
 216         generation = btrfs_super_chunk_root_generation(disk_super);
 217
 218         __setup_root(nodesize, leafsize, sectorsize, stripesize,
 219                      chunk_root, fs_info, BTRFS_CHUNK_TREE_OBJECTID);
 220
 221         chunk_root->node = read_tree_block(chunk_root,
 222                                            btrfs_super_chunk_root(disk_super),
 223                                            blocksize, generation);
 224         if (!chunk_root->node) {
 225                 printk("Couldn't read chunk root\n");
 226                 goto out_devices;
 227         }
 228
 229         read_extent_buffer(chunk_root->node, fs_info->chunk_tree_uuid,
 230                  (unsigned long)btrfs_header_chunk_tree_uuid(chunk_root->node),
 231                  BTRFS_UUID_SIZE);
 232
 233         if (!(btrfs_super_flags(disk_super) & BTRFS_SUPER_FLAG_METADUMP)) {
 234                 ret = btrfs_read_chunk_tree(chunk_root);
 235                 if (ret)
 236                         goto out_chunk;
 237         }
 238
 239         return fs_info->chunk_root;
 240 out_chunk:
 241         free_extent_buffer(fs_info->chunk_root->node);
 242 out_devices:
 243         close_all_devices(fs_info);
 244 out_cleanup:
 245         extent_io_tree_cleanup(&fs_info->extent_cache);
 246         extent_io_tree_cleanup(&fs_info->free_space_cache);
 247         extent_io_tree_cleanup(&fs_info->block_group_cache);
 248         extent_io_tree_cleanup(&fs_info->pinned_extents);
 249         extent_io_tree_cleanup(&fs_info->pending_del);
 250         extent_io_tree_cleanup(&fs_info->extent_ins);
 251 out:
 252         free(tree_root);
 253         free(extent_root);
 254         free(chunk_root);
 255         free(dev_root);
 256         free(csum_root);
 257         free(fs_info);
 258         return NULL;
 259 }
 260
 261 static int search_iobuf(struct btrfs_root *root, void *iobuf,
 262                         size_t iobuf_size, off_t offset)
 263 {
 264         u64 gen = btrfs_super_generation(&root->fs_info->super_copy);
 265         u64 objectid = search_objectid;
 266         u32 size = btrfs_super_nodesize(&root->fs_info->super_copy);
 267         u8 level = root->fs_info->super_copy.root_level;
 268         size_t block_off = 0;
 269
 270         while (block_off < iobuf_size) {
 271                 void *block = iobuf + block_off;
 272                 struct btrfs_header *header = block;
 273                 u64 h_byte, h_level, h_gen, h_owner;
 274
 275 //              printf("searching %Lu\n", offset + block_off);
 276                 h_byte = le64_to_cpu(header->bytenr);
 277                 h_owner = le64_to_cpu(header->owner);
 278                 h_level = header->level;
 279                 h_gen = le64_to_cpu(header->generation);
 280
 281                 if (h_owner != objectid)
 282                         goto next;
 283                 if (h_byte != (offset + block_off))
 284                         goto next;
 285                 if (h_level != level)
 286                         goto next;
 287                 if (csum_block(block, size)) {
 288                         fprintf(stderr, "Well block %Lu seems good, "
 289                                 "but the csum doesn't match\n",
 290                                 h_byte);
 291                         goto next;
 292                 }
 293                 if (h_gen != gen) {
 294                         fprintf(stderr, "Well block %Lu seems great, "
 295                                 "but generation doesn't match, "
 296                                 "have=%Lu, want=%Lu\n", h_byte, h_gen,
 297                                 gen);
 298                         goto next;
 299                 }
 300                 printf("Found tree root at %Lu\n", h_byte);
 301                 return 0;
 302 next:
 303                 block_off += size;
 304         }
 305
 306         return 1;
 307 }
 308
 309 static int read_physical(struct btrfs_root *root, int fd, u64 offset,
 310                          u64 bytenr, u64 len)
 311 {
 312         char *iobuf = malloc(len);
 313         ssize_t done;
 314         size_t total_read = 0;
 315         int ret = 1;
 316
 317         if (!iobuf) {
 318                 fprintf(stderr, "No memory\n");
 319                 return -1;
 320         }
 321
 322         while (total_read < len) {
 323                 done = pread64(fd, iobuf + total_read, len - total_read,
 324                                bytenr + total_read);
 325                 if (done < 0) {
 326                         fprintf(stderr, "Failed to read: %s\n",
 327                                 strerror(errno));
 328                         ret = -1;
 329                         goto out;
 330                 }
 331                 total_read += done;
 332         }
 333
 334         ret = search_iobuf(root, iobuf, total_read, offset);
 335 out:
 336         free(iobuf);
 337         return ret;
 338 }
 339
 340 static int find_root(struct btrfs_root *root)
 341 {
 342         struct btrfs_multi_bio *multi = NULL;
 343         struct btrfs_device *device;
 344         u64 metadata_offset = 0, metadata_size = 0;
 345         off_t offset = 0;
 346         off_t bytenr;
 347         int fd;
 348         int err;
 349         int ret = 1;
 350
 351         printf("Super think's the tree root is at %Lu, chunk root %Lu\n",
 352                btrfs_super_root(&root->fs_info->super_copy),
 353                btrfs_super_chunk_root(&root->fs_info->super_copy));
 354
 355         err = btrfs_next_metadata(&root->fs_info->mapping_tree,
 356                                   &metadata_offset, &metadata_size);
 357         if (err)
 358                 return ret;
 359
 360         offset = metadata_offset;
 361         while (1) {
 362                 u64 map_length = 4096;
 363                 u64 type;
 364
 365                 if (offset >
 366                     btrfs_super_total_bytes(&root->fs_info->super_copy)) {
 367                         printf("Went past the fs size, exiting");
 368                         break;
 369                 }
 370                 if (offset >= (metadata_offset + metadata_size)) {
 371                         err = btrfs_next_metadata(&root->fs_info->mapping_tree,
 372                                                   &metadata_offset,
 373                                                   &metadata_size);
 374                         if (err) {
 375                                 printf("No more metdata to scan, exiting\n");
 376                                 break;
 377                         }
 378                         offset = metadata_offset;
 379                 }
 380                 err = __btrfs_map_block(&root->fs_info->mapping_tree, READ,
 381                                       offset, &map_length, &type, &multi, 0);
 382                 if (err) {
 383                         offset += map_length;
 384                         continue;
 385                 }
 386
 387                 if (!(type & BTRFS_BLOCK_GROUP_METADATA)) {
 388                         offset += map_length;
 389                         continue;
 390                 }
 391
 392                 device = multi->stripes[0].dev;
 393                 fd = device->fd;
 394                 bytenr = multi->stripes[0].physical;
 395                 kfree(multi);
 396
 397                 err = read_physical(root, fd, offset, bytenr, map_length);
 398                 if (!err) {
 399                         ret = 0;
 400                         break;
 401                 } else if (err < 0) {
 402                         ret = err;
 403                         break;
 404                 }
 405                 offset += map_length;
 406         }
 407         return ret;
 408 }
 409
 410 int main(int argc, char **argv)
 411 {
 412         struct btrfs_root *root;
 413         int dev_fd;
 414         int opt;
 415         int ret;
 416
 417         while ((opt = getopt(argc, argv, "vo:")) != -1) {
 418                 switch(opt) {
 419                         case 'v':
 420                                 verbose++;
 421                                 break;
 422                         case 'o':
 423                                 errno = 0;
 424                                 search_objectid = (u64)strtoll(optarg, NULL,
 425                                                                10);
 426                                 if (errno) {
 427                                         fprintf(stderr, "Error parsing "
 428                                                 "objectid\n");
 429                                         exit(1);
 430                                 }
 431                                 break;
 432                         default:
 433                                 usage();
 434                                 exit(1);
 435                 }
 436         }
 437
 438         if (optind >= argc) {
 439                 usage();
 440                 exit(1);
 441         }
 442
 443         dev_fd = open(argv[optind], O_RDONLY);
 444         if (dev_fd < 0) {
 445                 fprintf(stderr, "Failed to open device %s\n", argv[optind]);
 446                 exit(1);
 447         }
 448
 449         root = open_ctree_broken(dev_fd, argv[optind]);
 450         close(dev_fd);
 451         if (!root)
 452                 exit(1);
 453
 454         csum_size = btrfs_super_csum_size(&root->fs_info->super_copy);
 455         ret = find_root(root);
 456         close_ctree(root);
 457         return ret;
 458 }