btrfs-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 #include <stdio.h>
  20 #include <stdlib.h>
  21 #include <unistd.h>
  22 #include <fcntl.h>
  23 #include <sys/stat.h>
  24 #include <zlib.h>
  25 #include "kerncompat.h"
  26 #include "ctree.h"
  27 #include "disk-io.h"
  28 #include "print-tree.h"
  29 #include "transaction.h"
  30 #include "list.h"
  31 #include "volumes.h"
  32 #include "utils.h"
  33 #include "crc32c.h"
  34 #include "extent-cache.h"
  35 #include "find-root.h"
  36
  37 static u16 csum_size = 0;
  38 static u64 search_objectid = BTRFS_ROOT_TREE_OBJECTID;
  39 static u64 search_generation = 0;
  40 static unsigned long search_level = 0;
  41
  42 static void usage(void)
  43 {
  44         fprintf(stderr, "Usage: find-roots [-o search_objectid] "
  45                 "[ -g search_generation ] [ -l search_level ] <device>\n");
  46 }
  47
  48 static int csum_block(void *buf, u32 len)
  49 {
  50         char *result;
  51         u32 crc = ~(u32)0;
  52         int ret = 0;
  53
  54         result = malloc(csum_size * sizeof(char));
  55         if (!result) {
  56                 fprintf(stderr, "No memory\n");
  57                 return 1;
  58         }
  59
  60         len -= BTRFS_CSUM_SIZE;
  61         crc = crc32c(crc, buf + BTRFS_CSUM_SIZE, len);
  62         btrfs_csum_final(crc, result);
  63
  64         if (memcmp(buf, result, csum_size))
  65                 ret = 1;
  66         free(result);
  67         return ret;
  68 }
  69
  70 static struct btrfs_root *open_ctree_broken(int fd, const char *device)
  71 {
  72         struct btrfs_fs_info *fs_info;
  73         struct btrfs_super_block *disk_super;
  74         struct btrfs_fs_devices *fs_devices = NULL;
  75         struct extent_buffer *eb;
  76         int ret;
  77
  78         fs_info = btrfs_new_fs_info(0, BTRFS_SUPER_INFO_OFFSET);
  79         if (!fs_info) {
  80                 fprintf(stderr, "Failed to allocate memory for fs_info\n");
  81                 return NULL;
  82         }
  83
  84         ret = btrfs_scan_fs_devices(fd, device, &fs_devices, 0, 1, 0);
  85         if (ret)
  86                 goto out;
  87
  88         fs_info->fs_devices = fs_devices;
  89
  90         ret = btrfs_open_devices(fs_devices, O_RDONLY);
  91         if (ret)
  92                 goto out_devices;
  93
  94         disk_super = fs_info->super_copy;
  95         ret = btrfs_read_dev_super(fs_devices->latest_bdev,
  96                                    disk_super, fs_info->super_bytenr, 1);
  97         if (ret) {
  98                 printk("No valid btrfs found\n");
  99                 goto out_devices;
 100         }
 101
 102         memcpy(fs_info->fsid, &disk_super->fsid, BTRFS_FSID_SIZE);
 103
 104         ret = btrfs_check_fs_compatibility(disk_super, 0);
 105         if (ret)
 106                 goto out_devices;
 107
 108         ret = btrfs_setup_chunk_tree_and_device_map(fs_info);
 109         if (ret)
 110                 goto out_chunk;
 111
 112         eb = fs_info->chunk_root->node;
 113         read_extent_buffer(eb, fs_info->chunk_tree_uuid,
 114                            btrfs_header_chunk_tree_uuid(eb), BTRFS_UUID_SIZE);
 115
 116         return fs_info->chunk_root;
 117 out_chunk:
 118         free_extent_buffer(fs_info->chunk_root->node);
 119         btrfs_cleanup_all_caches(fs_info);
 120 out_devices:
 121         btrfs_close_devices(fs_info->fs_devices);
 122 out:
 123         btrfs_free_fs_info(fs_info);
 124         return NULL;
 125 }
 126
 127 static int search_iobuf(struct btrfs_root *root, void *iobuf,
 128                         size_t iobuf_size, off_t offset)
 129 {
 130         u64 gen = search_generation;
 131         u64 objectid = search_objectid;
 132         u32 size = btrfs_super_nodesize(root->fs_info->super_copy);
 133         u8 level = search_level;
 134         size_t block_off = 0;
 135
 136         while (block_off < iobuf_size) {
 137                 void *block = iobuf + block_off;
 138                 struct btrfs_header *header = block;
 139                 u64 h_byte, h_level, h_gen, h_owner;
 140
 141 //              printf("searching %Lu\n", offset + block_off);
 142                 h_byte = btrfs_stack_header_bytenr(header);
 143                 h_owner = btrfs_stack_header_owner(header);
 144                 h_level = header->level;
 145                 h_gen = btrfs_stack_header_generation(header);
 146
 147                 if (h_owner != objectid)
 148                         goto next;
 149                 if (h_byte != (offset + block_off))
 150                         goto next;
 151                 if (h_level < level)
 152                         goto next;
 153                 level = h_level;
 154                 if (csum_block(block, size)) {
 155                         fprintf(stderr, "Well block %Lu seems good, "
 156                                 "but the csum doesn't match\n",
 157                                 h_byte);
 158                         goto next;
 159                 }
 160                 if (h_gen != gen) {
 161                         fprintf(stderr, "Well block %Lu seems great, "
 162                                 "but generation doesn't match, "
 163                                 "have=%Lu, want=%Lu level %Lu\n", h_byte,
 164                                 h_gen, gen, h_level);
 165                         goto next;
 166                 }
 167                 printf("Found tree root at %Lu gen %Lu level %Lu\n", h_byte,
 168                        h_gen, h_level);
 169                 return 0;
 170 next:
 171                 block_off += size;
 172         }
 173
 174         return 1;
 175 }
 176
 177 static int read_physical(struct btrfs_root *root, int fd, u64 offset,
 178                          u64 bytenr, u64 len)
 179 {
 180         char *iobuf = malloc(len);
 181         ssize_t done;
 182         size_t total_read = 0;
 183         int ret = 1;
 184
 185         if (!iobuf) {
 186                 fprintf(stderr, "No memory\n");
 187                 return -1;
 188         }
 189
 190         while (total_read < len) {
 191                 done = pread64(fd, iobuf + total_read, len - total_read,
 192                                bytenr + total_read);
 193                 if (done < 0) {
 194                         fprintf(stderr, "Failed to read: %s\n",
 195                                 strerror(errno));
 196                         ret = -1;
 197                         goto out;
 198                 }
 199                 total_read += done;
 200         }
 201
 202         ret = search_iobuf(root, iobuf, total_read, offset);
 203 out:
 204         free(iobuf);
 205         return ret;
 206 }
 207
 208 static int find_root(struct btrfs_root *root)
 209 {
 210         struct btrfs_multi_bio *multi = NULL;
 211         struct btrfs_device *device;
 212         u64 metadata_offset = 0, metadata_size = 0;
 213         off_t offset = 0;
 214         off_t bytenr;
 215         int fd;
 216         int err;
 217         int ret = 1;
 218
 219         printf("Super think's the tree root is at %Lu, chunk root %Lu\n",
 220                btrfs_super_root(root->fs_info->super_copy),
 221                btrfs_super_chunk_root(root->fs_info->super_copy));
 222
 223         err = btrfs_next_metadata(&root->fs_info->mapping_tree,
 224                                   &metadata_offset, &metadata_size);
 225         if (err)
 226                 return ret;
 227
 228         offset = metadata_offset;
 229         while (1) {
 230                 u64 map_length = 4096;
 231                 u64 type;
 232
 233                 if (offset >
 234                     btrfs_super_total_bytes(root->fs_info->super_copy)) {
 235                         printf("Went past the fs size, exiting");
 236                         break;
 237                 }
 238                 if (offset >= (metadata_offset + metadata_size)) {
 239                         err = btrfs_next_metadata(&root->fs_info->mapping_tree,
 240                                                   &metadata_offset,
 241                                                   &metadata_size);
 242                         if (err) {
 243                                 printf("No more metdata to scan, exiting\n");
 244                                 break;
 245                         }
 246                         offset = metadata_offset;
 247                 }
 248                 err = __btrfs_map_block(&root->fs_info->mapping_tree, READ,
 249                                       offset, &map_length, &type,
 250                                       &multi, 0, NULL);
 251                 if (err) {
 252                         offset += map_length;
 253                         continue;
 254                 }
 255
 256                 if (!(type & BTRFS_BLOCK_GROUP_METADATA)) {
 257                         offset += map_length;
 258                         kfree(multi);
 259                         continue;
 260                 }
 261
 262                 device = multi->stripes[0].dev;
 263                 fd = device->fd;
 264                 bytenr = multi->stripes[0].physical;
 265                 kfree(multi);
 266
 267                 err = read_physical(root, fd, offset, bytenr, map_length);
 268                 if (!err) {
 269                         ret = 0;
 270                         break;
 271                 } else if (err < 0) {
 272                         ret = err;
 273                         break;
 274                 }
 275                 offset += map_length;
 276         }
 277         return ret;
 278 }
 279
 280 /*
 281  * Get reliable generation and level for given root.
 282  *
 283  * We have two sources of gen/level: superblock and tree root.
 284  * superblock include the following level:
 285  *   Root, chunk, log
 286  * and the following generations:
 287  *   Root, chunk, uuid
 288  * Other gen/leven can only be read from its btrfs_tree_root if possible.
 289  *
 290  * Currently we only believe things from superblock.
 291  */
 292 static void get_root_gen_and_level(u64 objectid, struct btrfs_fs_info *fs_info,
 293                                    u64 *ret_gen, u8 *ret_level)
 294 {
 295         struct btrfs_super_block *super = fs_info->super_copy;
 296         u64 gen = (u64)-1;
 297         u8 level = (u8)-1;
 298
 299         switch (objectid) {
 300         case BTRFS_ROOT_TREE_OBJECTID:
 301                 level = btrfs_super_root_level(super);
 302                 gen = btrfs_super_generation(super);
 303                 break;
 304         case BTRFS_CHUNK_TREE_OBJECTID:
 305                 level = btrfs_super_chunk_root_level(super);
 306                 gen = btrfs_super_chunk_root_generation(super);
 307                 printf("Search for chunk root is not supported yet\n");
 308                 break;
 309         case BTRFS_TREE_LOG_OBJECTID:
 310                 level = btrfs_super_log_root_level(super);
 311                 gen = btrfs_super_log_root_transid(super);
 312                 break;
 313         case BTRFS_UUID_TREE_OBJECTID:
 314                 gen = btrfs_super_uuid_tree_generation(super);
 315                 break;
 316         }
 317         if (gen != (u64)-1) {
 318                 printf("Superblock thinks the generation is %llu\n", gen);
 319                 if (ret_gen)
 320                         *ret_gen = gen;
 321         } else {
 322                 printf("Superblock doesn't contain generation info for root %llu\n",
 323                        objectid);
 324         }
 325         if (level != (u8)-1) {
 326                 printf("Superblock thinks the level is %u\n", level);
 327                 if (ret_level)
 328                         *ret_level = level;
 329         } else {
 330                 printf("Superblock doesn't contain the level info for root %llu\n",
 331                        objectid);
 332         }
 333 }
 334
 335 static void print_one_result(struct cache_extent *tree_block,
 336                              u8 level, u64 generation,
 337                              struct btrfs_find_root_filter *filter)
 338 {
 339         int unsure = 0;
 340
 341         if (filter->match_gen == (u64)-1 || filter->match_level == (u8)-1)
 342                 unsure = 1;
 343         printf("Well block %llu(gen: %llu level: %u) seems good, ",
 344                tree_block->start, generation, level);
 345         if (unsure)
 346                 printf("but we are unsure about the correct generation/level\n");
 347         else
 348                 printf("but generation/level doesn't match, want gen: %llu level: %u\n",
 349                        filter->match_gen, filter->match_level);
 350 }
 351
 352 static void print_find_root_result(struct cache_tree *result,
 353                                    struct btrfs_find_root_filter *filter)
 354 {
 355         struct btrfs_find_root_gen_cache *gen_cache;
 356         struct cache_extent *cache;
 357         struct cache_extent *tree_block;
 358         u64 generation = 0;
 359         u8 level = 0;
 360
 361         for (cache = last_cache_extent(result);
 362              cache; cache = prev_cache_extent(cache)) {
 363                 gen_cache = container_of(cache,
 364                                 struct btrfs_find_root_gen_cache, cache);
 365                 level = gen_cache->highest_level;
 366                 generation = cache->start;
 367                 if (level == filter->match_level &&
 368                     generation == filter->match_gen)
 369                         continue;
 370                 for (tree_block = last_cache_extent(&gen_cache->eb_tree);
 371                      tree_block; tree_block = prev_cache_extent(tree_block))
 372                         print_one_result(tree_block, level, generation, filter);
 373         }
 374 }
 375
 376 int main(int argc, char **argv)
 377 {
 378         struct btrfs_root *root;
 379         struct btrfs_find_root_filter filter = {0};
 380         struct cache_tree result;
 381         struct cache_extent *found;
 382         int opt;
 383         int ret;
 384
 385         /* Default to search root tree */
 386         filter.objectid = BTRFS_ROOT_TREE_OBJECTID;
 387         filter.match_gen = (u64)-1;
 388         filter.match_level = (u8)-1;
 389         while ((opt = getopt(argc, argv, "l:o:g:")) != -1) {
 390                 switch(opt) {
 391                         case 'o':
 392                                 filter.objectid = arg_strtou64(optarg);
 393                                 break;
 394                         case 'g':
 395                                 filter.generation = arg_strtou64(optarg);
 396                                 break;
 397                         case 'l':
 398                                 filter.level = arg_strtou64(optarg);
 399                                 break;
 400                         default:
 401                                 usage();
 402                                 exit(1);
 403                 }
 404         }
 405
 406         set_argv0(argv);
 407         argc = argc - optind;
 408         if (check_argc_min(argc, 1)) {
 409                 usage();
 410                 exit(1);
 411         }
 412
 413         root = open_ctree(argv[optind], 0, OPEN_CTREE_CHUNK_ROOT_ONLY);
 414         if (!root) {
 415                 fprintf(stderr, "Open ctree failed\n");
 416                 exit(1);
 417         }
 418         cache_tree_init(&result);
 419
 420         get_root_gen_and_level(filter.objectid, root->fs_info,
 421                                &filter.match_gen, &filter.match_level);
 422         ret = btrfs_find_root_search(root, &filter, &result, &found);
 423         if (ret < 0) {
 424                 fprintf(stderr, "Fail to search the tree root: %s\n",
 425                         strerror(-ret));
 426                 goto out;
 427         }
 428         if (ret > 0) {
 429                 printf("Found tree root at %llu gen %llu level %u\n",
 430                        found->start, filter.match_gen, filter.match_level);
 431                 ret = 0;
 432         }
 433         print_find_root_result(&result, &filter);
 434 out:
 435         btrfs_find_root_free(&result);
 436         close_ctree(root);
 437         return ret;
 438 }