btrfs-progs: add a recovery utility to pull files from damanged filesystems
[platform/upstream/btrfs-progs.git] / 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 }