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