Btrfs-progs: pass properly formated key to read_fs_root
[platform/upstream/btrfs-progs.git] / cmds-restore.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
22 #include "kerncompat.h"
23
24 #include <ctype.h>
25 #include <stdio.h>
26 #include <stdlib.h>
27 #include <unistd.h>
28 #include <fcntl.h>
29 #include <sys/stat.h>
30 #include <lzo/lzoconf.h>
31 #include <lzo/lzo1x.h>
32 #include <zlib.h>
33
34 #include "ctree.h"
35 #include "disk-io.h"
36 #include "print-tree.h"
37 #include "transaction.h"
38 #include "list.h"
39 #include "version.h"
40 #include "volumes.h"
41 #include "utils.h"
42 #include "commands.h"
43
44 static char fs_name[4096];
45 static char path_name[4096];
46 static int get_snaps = 0;
47 static int verbose = 0;
48 static int ignore_errors = 0;
49 static int overwrite = 0;
50
51 #define LZO_LEN 4
52 #define PAGE_CACHE_SIZE 4096
53 #define lzo1x_worst_compress(x) ((x) + ((x) / 16) + 64 + 3)
54
55 static int decompress_zlib(char *inbuf, char *outbuf, u64 compress_len,
56                            u64 decompress_len)
57 {
58         z_stream strm;
59         int ret;
60
61         memset(&strm, 0, sizeof(strm));
62         ret = inflateInit(&strm);
63         if (ret != Z_OK) {
64                 fprintf(stderr, "inflate init returnd %d\n", ret);
65                 return -1;
66         }
67
68         strm.avail_in = compress_len;
69         strm.next_in = (unsigned char *)inbuf;
70         strm.avail_out = decompress_len;
71         strm.next_out = (unsigned char *)outbuf;
72         ret = inflate(&strm, Z_NO_FLUSH);
73         if (ret != Z_STREAM_END) {
74                 (void)inflateEnd(&strm);
75                 fprintf(stderr, "failed to inflate: %d\n", ret);
76                 return -1;
77         }
78
79         (void)inflateEnd(&strm);
80         return 0;
81 }
82 static inline size_t read_compress_length(unsigned char *buf)
83 {
84         __le32 dlen;
85         memcpy(&dlen, buf, LZO_LEN);
86         return le32_to_cpu(dlen);
87 }
88
89 static int decompress_lzo(unsigned char *inbuf, char *outbuf, u64 compress_len,
90                           u64 *decompress_len)
91 {
92         size_t new_len;
93         size_t in_len;
94         size_t out_len = 0;
95         size_t tot_len;
96         size_t tot_in;
97         int ret;
98
99         ret = lzo_init();
100         if (ret != LZO_E_OK) {
101                 fprintf(stderr, "lzo init returned %d\n", ret);
102                 return -1;
103         }
104
105         tot_len = read_compress_length(inbuf);
106         inbuf += LZO_LEN;
107         tot_in = LZO_LEN;
108
109         while (tot_in < tot_len) {
110                 in_len = read_compress_length(inbuf);
111                 inbuf += LZO_LEN;
112                 tot_in += LZO_LEN;
113
114                 new_len = lzo1x_worst_compress(PAGE_CACHE_SIZE);
115                 ret = lzo1x_decompress_safe((const unsigned char *)inbuf, in_len,
116                                             (unsigned char *)outbuf,
117                                             (void *)&new_len, NULL);
118                 if (ret != LZO_E_OK) {
119                         fprintf(stderr, "failed to inflate: %d\n", ret);
120                         return -1;
121                 }
122                 out_len += new_len;
123                 outbuf += new_len;
124                 inbuf += in_len;
125                 tot_in += in_len;
126         }
127
128         *decompress_len = out_len;
129
130         return 0;
131 }
132
133 static int decompress(char *inbuf, char *outbuf, u64 compress_len,
134                       u64 *decompress_len, int compress)
135 {
136         switch (compress) {
137         case BTRFS_COMPRESS_ZLIB:
138                 return decompress_zlib(inbuf, outbuf, compress_len,
139                                        *decompress_len);
140         case BTRFS_COMPRESS_LZO:
141                 return decompress_lzo((unsigned char *)inbuf, outbuf, compress_len,
142                                       decompress_len);
143         default:
144                 break;
145         }
146
147         fprintf(stderr, "invalid compression type: %d\n", compress);
148         return -1;
149 }
150
151 int next_leaf(struct btrfs_root *root, struct btrfs_path *path)
152 {
153         int slot;
154         int level = 1;
155         struct extent_buffer *c;
156         struct extent_buffer *next = NULL;
157
158         for (; level < BTRFS_MAX_LEVEL; level++) {
159                 if (path->nodes[level])
160                         break;
161         }
162
163         if (level == BTRFS_MAX_LEVEL)
164                 return 1;
165
166         slot = path->slots[level] + 1;
167
168         while(level < BTRFS_MAX_LEVEL) {
169                 if (!path->nodes[level])
170                         return 1;
171
172                 slot = path->slots[level] + 1;
173                 c = path->nodes[level];
174                 if (slot >= btrfs_header_nritems(c)) {
175                         level++;
176                         if (level == BTRFS_MAX_LEVEL)
177                                 return 1;
178                         continue;
179                 }
180
181                 if (path->reada)
182                         reada_for_search(root, path, level, slot, 0);
183
184                 next = read_node_slot(root, c, slot);
185                 break;
186         }
187         path->slots[level] = slot;
188         while(1) {
189                 level--;
190                 c = path->nodes[level];
191                 free_extent_buffer(c);
192                 path->nodes[level] = next;
193                 path->slots[level] = 0;
194                 if (!level)
195                         break;
196                 if (path->reada)
197                         reada_for_search(root, path, level, 0, 0);
198                 next = read_node_slot(root, next, 0);
199         }
200         return 0;
201 }
202
203 static int copy_one_inline(int fd, struct btrfs_path *path, u64 pos)
204 {
205         struct extent_buffer *leaf = path->nodes[0];
206         struct btrfs_file_extent_item *fi;
207         char buf[4096];
208         char *outbuf;
209         u64 ram_size;
210         ssize_t done;
211         unsigned long ptr;
212         int ret;
213         int len;
214         int compress;
215
216         fi = btrfs_item_ptr(leaf, path->slots[0],
217                             struct btrfs_file_extent_item);
218         ptr = btrfs_file_extent_inline_start(fi);
219         len = btrfs_file_extent_inline_item_len(leaf,
220                                         btrfs_item_nr(leaf, path->slots[0]));
221         read_extent_buffer(leaf, buf, ptr, len);
222
223         compress = btrfs_file_extent_compression(leaf, fi);
224         if (compress == BTRFS_COMPRESS_NONE) {
225                 done = pwrite(fd, buf, len, pos);
226                 if (done < len) {
227                         fprintf(stderr, "Short inline write, wanted %d, did "
228                                 "%zd: %d\n", len, done, errno);
229                         return -1;
230                 }
231                 return 0;
232         }
233
234         ram_size = btrfs_file_extent_ram_bytes(leaf, fi);
235         outbuf = malloc(ram_size);
236         if (!outbuf) {
237                 fprintf(stderr, "No memory\n");
238                 return -1;
239         }
240
241         ret = decompress(buf, outbuf, len, &ram_size, compress);
242         if (ret) {
243                 free(outbuf);
244                 return ret;
245         }
246
247         done = pwrite(fd, outbuf, ram_size, pos);
248         free(outbuf);
249         if (done < ram_size) {
250                 fprintf(stderr, "Short compressed inline write, wanted %Lu, "
251                         "did %zd: %d\n", ram_size, done, errno);
252                 return -1;
253         }
254
255         return 0;
256 }
257
258 static int copy_one_extent(struct btrfs_root *root, int fd,
259                            struct extent_buffer *leaf,
260                            struct btrfs_file_extent_item *fi, u64 pos)
261 {
262         struct btrfs_multi_bio *multi = NULL;
263         struct btrfs_device *device;
264         char *inbuf, *outbuf = NULL;
265         ssize_t done, total = 0;
266         u64 bytenr;
267         u64 ram_size;
268         u64 disk_size;
269         u64 length;
270         u64 size_left;
271         u64 dev_bytenr;
272         u64 offset;
273         u64 count = 0;
274         int compress;
275         int ret;
276         int dev_fd;
277         int mirror_num = 1;
278         int num_copies;
279
280         compress = btrfs_file_extent_compression(leaf, fi);
281         bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
282         disk_size = btrfs_file_extent_disk_num_bytes(leaf, fi);
283         ram_size = btrfs_file_extent_ram_bytes(leaf, fi);
284         offset = btrfs_file_extent_offset(leaf, fi);
285         size_left = disk_size;
286
287         if (offset)
288                 printf("offset is %Lu\n", offset);
289         /* we found a hole */
290         if (disk_size == 0)
291                 return 0;
292
293         inbuf = malloc(disk_size);
294         if (!inbuf) {
295                 fprintf(stderr, "No memory\n");
296                 return -1;
297         }
298
299         if (compress != BTRFS_COMPRESS_NONE) {
300                 outbuf = malloc(ram_size);
301                 if (!outbuf) {
302                         fprintf(stderr, "No memory\n");
303                         free(inbuf);
304                         return -1;
305                 }
306         }
307 again:
308         length = size_left;
309         ret = btrfs_map_block(&root->fs_info->mapping_tree, READ,
310                               bytenr, &length, &multi, mirror_num, NULL);
311         if (ret) {
312                 fprintf(stderr, "Error mapping block %d\n", ret);
313                 goto out;
314         }
315         device = multi->stripes[0].dev;
316         dev_fd = device->fd;
317         device->total_ios++;
318         dev_bytenr = multi->stripes[0].physical;
319         kfree(multi);
320
321         if (size_left < length)
322                 length = size_left;
323
324         done = pread(dev_fd, inbuf+count, length, dev_bytenr);
325         /* Need both checks, or we miss negative values due to u64 conversion */
326         if (done < 0 || done < length) {
327                 num_copies = btrfs_num_copies(&root->fs_info->mapping_tree,
328                                               bytenr, length);
329                 mirror_num++;
330                 /* mirror_num is 1-indexed, so num_copies is a valid mirror. */
331                 if (mirror_num > num_copies) {
332                         ret = -1;
333                         fprintf(stderr, "Exhausted mirrors trying to read\n");
334                         goto out;
335                 }
336                 fprintf(stderr, "Trying another mirror\n");
337                 goto again;
338         }
339
340         mirror_num = 1;
341         size_left -= length;
342         count += length;
343         bytenr += length;
344         if (size_left)
345                 goto again;
346
347         if (compress == BTRFS_COMPRESS_NONE) {
348                 while (total < ram_size) {
349                         done = pwrite(fd, inbuf+total, ram_size-total,
350                                       pos+total);
351                         if (done < 0) {
352                                 ret = -1;
353                                 fprintf(stderr, "Error writing: %d %s\n", errno, strerror(errno));
354                                 goto out;
355                         }
356                         total += done;
357                 }
358                 ret = 0;
359                 goto out;
360         }
361
362         ret = decompress(inbuf, outbuf, disk_size, &ram_size, compress);
363         if (ret) {
364                 num_copies = btrfs_num_copies(&root->fs_info->mapping_tree,
365                                               bytenr, length);
366                 mirror_num++;
367                 if (mirror_num >= num_copies) {
368                         ret = -1;
369                         goto out;
370                 }
371                 fprintf(stderr, "Trying another mirror\n");
372                 goto again;
373         }
374
375         while (total < ram_size) {
376                 done = pwrite(fd, outbuf+total, ram_size-total, pos+total);
377                 if (done < 0) {
378                         ret = -1;
379                         goto out;
380                 }
381                 total += done;
382         }
383 out:
384         free(inbuf);
385         free(outbuf);
386         return ret;
387 }
388
389 static int ask_to_continue(const char *file)
390 {
391         char buf[2];
392         char *ret;
393
394         printf("We seem to be looping a lot on %s, do you want to keep going "
395                "on ? (y/N): ", file);
396 again:
397         ret = fgets(buf, 2, stdin);
398         if (*ret == '\n' || tolower(*ret) == 'n')
399                 return 1;
400         if (tolower(*ret) != 'y') {
401                 printf("Please enter either 'y' or 'n': ");
402                 goto again;
403         }
404
405         return 0;
406 }
407
408
409 static int copy_file(struct btrfs_root *root, int fd, struct btrfs_key *key,
410                      const char *file)
411 {
412         struct extent_buffer *leaf;
413         struct btrfs_path *path;
414         struct btrfs_file_extent_item *fi;
415         struct btrfs_inode_item *inode_item;
416         struct btrfs_key found_key;
417         int ret;
418         int extent_type;
419         int compression;
420         int loops = 0;
421         u64 found_size = 0;
422
423         path = btrfs_alloc_path();
424         if (!path) {
425                 fprintf(stderr, "Ran out of memory\n");
426                 return -1;
427         }
428         path->skip_locking = 1;
429
430         ret = btrfs_lookup_inode(NULL, root, path, key, 0);
431         if (ret == 0) {
432                 inode_item = btrfs_item_ptr(path->nodes[0], path->slots[0],
433                                     struct btrfs_inode_item);
434                 found_size = btrfs_inode_size(path->nodes[0], inode_item);
435         }
436         btrfs_release_path(root, path);
437
438         key->offset = 0;
439         key->type = BTRFS_EXTENT_DATA_KEY;
440
441         ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
442         if (ret < 0) {
443                 fprintf(stderr, "Error searching %d\n", ret);
444                 btrfs_free_path(path);
445                 return ret;
446         }
447
448         leaf = path->nodes[0];
449         while (!leaf) {
450                 ret = next_leaf(root, path);
451                 if (ret < 0) {
452                         fprintf(stderr, "Error getting next leaf %d\n",
453                                 ret);
454                         btrfs_free_path(path);
455                         return ret;
456                 } else if (ret > 0) {
457                         /* No more leaves to search */
458                         btrfs_free_path(path);
459                         return 0;
460                 }
461                 leaf = path->nodes[0];
462         }
463
464         while (1) {
465                 if (loops++ >= 1024) {
466                         ret = ask_to_continue(file);
467                         if (ret)
468                                 break;
469                         loops = 0;
470                 }
471                 if (path->slots[0] >= btrfs_header_nritems(leaf)) {
472                         do {
473                                 ret = next_leaf(root, path);
474                                 if (ret < 0) {
475                                         fprintf(stderr, "Error searching %d\n", ret);
476                                         btrfs_free_path(path);
477                                         return ret;
478                                 } else if (ret) {
479                                         /* No more leaves to search */
480                                         btrfs_free_path(path);
481                                         goto set_size;
482                                 }
483                                 leaf = path->nodes[0];
484                         } while (!leaf);
485                         continue;
486                 }
487                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
488                 if (found_key.objectid != key->objectid)
489                         break;
490                 if (found_key.type != key->type)
491                         break;
492                 fi = btrfs_item_ptr(leaf, path->slots[0],
493                                     struct btrfs_file_extent_item);
494                 extent_type = btrfs_file_extent_type(leaf, fi);
495                 compression = btrfs_file_extent_compression(leaf, fi);
496                 if (compression >= BTRFS_COMPRESS_LAST) {
497                         fprintf(stderr, "Don't support compression yet %d\n",
498                                 compression);
499                         btrfs_free_path(path);
500                         return -1;
501                 }
502
503                 if (extent_type == BTRFS_FILE_EXTENT_PREALLOC)
504                         goto next;
505                 if (extent_type == BTRFS_FILE_EXTENT_INLINE) {
506                         ret = copy_one_inline(fd, path, found_key.offset);
507                         if (ret) {
508                                 btrfs_free_path(path);
509                                 return -1;
510                         }
511                 } else if (extent_type == BTRFS_FILE_EXTENT_REG) {
512                         ret = copy_one_extent(root, fd, leaf, fi,
513                                               found_key.offset);
514                         if (ret) {
515                                 btrfs_free_path(path);
516                                 return ret;
517                         }
518                 } else {
519                         printf("Weird extent type %d\n", extent_type);
520                 }
521 next:
522                 path->slots[0]++;
523         }
524
525         btrfs_free_path(path);
526 set_size:
527         if (found_size) {
528                 ret = ftruncate(fd, (loff_t)found_size);
529                 if (ret)
530                         return ret;
531         }
532         return 0;
533 }
534
535 static int search_dir(struct btrfs_root *root, struct btrfs_key *key,
536                       const char *output_rootdir, const char *dir)
537 {
538         struct btrfs_path *path;
539         struct extent_buffer *leaf;
540         struct btrfs_dir_item *dir_item;
541         struct btrfs_key found_key, location;
542         char filename[BTRFS_NAME_LEN + 1];
543         unsigned long name_ptr;
544         int name_len;
545         int ret;
546         int fd;
547         int loops = 0;
548         u8 type;
549
550         path = btrfs_alloc_path();
551         if (!path) {
552                 fprintf(stderr, "Ran out of memory\n");
553                 return -1;
554         }
555         path->skip_locking = 1;
556
557         key->offset = 0;
558         key->type = BTRFS_DIR_INDEX_KEY;
559
560         ret = btrfs_search_slot(NULL, root, key, path, 0, 0);
561         if (ret < 0) {
562                 fprintf(stderr, "Error searching %d\n", ret);
563                 btrfs_free_path(path);
564                 return ret;
565         }
566
567         leaf = path->nodes[0];
568         while (!leaf) {
569                 if (verbose > 1)
570                         printf("No leaf after search, looking for the next "
571                                "leaf\n");
572                 ret = next_leaf(root, path);
573                 if (ret < 0) {
574                         fprintf(stderr, "Error getting next leaf %d\n",
575                                 ret);
576                         btrfs_free_path(path);
577                         return ret;
578                 } else if (ret > 0) {
579                         /* No more leaves to search */
580                         if (verbose)
581                                 printf("Reached the end of the tree looking "
582                                        "for the directory\n");
583                         btrfs_free_path(path);
584                         return 0;
585                 }
586                 leaf = path->nodes[0];
587         }
588
589         while (leaf) {
590                 if (loops++ >= 1024) {
591                         printf("We have looped trying to restore files in %s "
592                                "too many times to be making progress, "
593                                "stopping\n", dir);
594                         break;
595                 }
596
597                 if (path->slots[0] >= btrfs_header_nritems(leaf)) {
598                         do {
599                                 ret = next_leaf(root, path);
600                                 if (ret < 0) {
601                                         fprintf(stderr, "Error searching %d\n",
602                                                 ret);
603                                         btrfs_free_path(path);
604                                         return ret;
605                                 } else if (ret > 0) {
606                                         /* No more leaves to search */
607                                         if (verbose)
608                                                 printf("Reached the end of "
609                                                        "the tree searching the"
610                                                        " directory\n");
611                                         btrfs_free_path(path);
612                                         return 0;
613                                 }
614                                 leaf = path->nodes[0];
615                         } while (!leaf);
616                         continue;
617                 }
618                 btrfs_item_key_to_cpu(leaf, &found_key, path->slots[0]);
619                 if (found_key.objectid != key->objectid) {
620                         if (verbose > 1)
621                                 printf("Found objectid=%Lu, key=%Lu\n",
622                                        found_key.objectid, key->objectid);
623                         break;
624                 }
625                 if (found_key.type != key->type) {
626                         if (verbose > 1)
627                                 printf("Found type=%u, want=%u\n",
628                                        found_key.type, key->type);
629                         break;
630                 }
631                 dir_item = btrfs_item_ptr(leaf, path->slots[0],
632                                           struct btrfs_dir_item);
633                 name_ptr = (unsigned long)(dir_item + 1);
634                 name_len = btrfs_dir_name_len(leaf, dir_item);
635                 read_extent_buffer(leaf, filename, name_ptr, name_len);
636                 filename[name_len] = '\0';
637                 type = btrfs_dir_type(leaf, dir_item);
638                 btrfs_dir_item_key_to_cpu(leaf, dir_item, &location);
639
640                 /* full path from root of btrfs being restored */
641                 snprintf(fs_name, 4096, "%s/%s", dir, filename);
642
643                 /* full path from system root */
644                 snprintf(path_name, 4096, "%s%s", output_rootdir, fs_name);
645
646                 /*
647                  * At this point we're only going to restore directories and
648                  * files, no symlinks or anything else.
649                  */
650                 if (type == BTRFS_FT_REG_FILE) {
651                         if (!overwrite) {
652                                 static int warn = 0;
653                                 struct stat st;
654
655                                 ret = stat(path_name, &st);
656                                 if (!ret) {
657                                         loops = 0;
658                                         if (verbose || !warn)
659                                                 printf("Skipping existing file"
660                                                        " %s\n", path_name);
661                                         if (warn)
662                                                 goto next;
663                                         printf("If you wish to overwrite use "
664                                                "the -o option to overwrite\n");
665                                         warn = 1;
666                                         goto next;
667                                 }
668                                 ret = 0;
669                         }
670                         if (verbose)
671                                 printf("Restoring %s\n", path_name);
672                         fd = open(path_name, O_CREAT|O_WRONLY, 0644);
673                         if (fd < 0) {
674                                 fprintf(stderr, "Error creating %s: %d\n",
675                                         path_name, errno);
676                                 if (ignore_errors)
677                                         goto next;
678                                 btrfs_free_path(path);
679                                 return -1;
680                         }
681                         loops = 0;
682                         ret = copy_file(root, fd, &location, path_name);
683                         close(fd);
684                         if (ret) {
685                                 if (ignore_errors)
686                                         goto next;
687                                 btrfs_free_path(path);
688                                 return ret;
689                         }
690                 } else if (type == BTRFS_FT_DIR) {
691                         struct btrfs_root *search_root = root;
692                         char *dir = strdup(fs_name);
693
694                         if (!dir) {
695                                 fprintf(stderr, "Ran out of memory\n");
696                                 btrfs_free_path(path);
697                                 return -1;
698                         }
699
700                         if (location.type == BTRFS_ROOT_ITEM_KEY) {
701                                 /*
702                                  * If we are a snapshot and this is the index
703                                  * object to ourselves just skip it.
704                                  */
705                                 if (location.objectid ==
706                                     root->root_key.objectid) {
707                                         free(dir);
708                                         goto next;
709                                 }
710
711                                 location.offset = (u64)-1;
712                                 search_root = btrfs_read_fs_root(root->fs_info,
713                                                                  &location);
714                                 if (IS_ERR(search_root)) {
715                                         free(dir);
716                                         fprintf(stderr, "Error reading "
717                                                 "subvolume %s: %lu\n",
718                                                 path_name,
719                                                 PTR_ERR(search_root));
720                                         if (ignore_errors)
721                                                 goto next;
722                                         btrfs_free_path(path);
723                                         return PTR_ERR(search_root);
724                                 }
725
726                                 /*
727                                  * A subvolume will have a key.offset of 0, a
728                                  * snapshot will have key.offset of a transid.
729                                  */
730                                 if (search_root->root_key.offset != 0 &&
731                                     get_snaps == 0) {
732                                         free(dir);
733                                         printf("Skipping snapshot %s\n",
734                                                filename);
735                                         goto next;
736                                 }
737                                 location.objectid = BTRFS_FIRST_FREE_OBJECTID;
738                         }
739
740                         if (verbose)
741                                 printf("Restoring %s\n", path_name);
742
743                         errno = 0;
744                         ret = mkdir(path_name, 0755);
745                         if (ret && errno != EEXIST) {
746                                 free(dir);
747                                 fprintf(stderr, "Error mkdiring %s: %d\n",
748                                         path_name, errno);
749                                 if (ignore_errors)
750                                         goto next;
751                                 btrfs_free_path(path);
752                                 return -1;
753                         }
754                         loops = 0;
755                         ret = search_dir(search_root, &location,
756                                          output_rootdir, dir);
757                         free(dir);
758                         if (ret) {
759                                 if (ignore_errors)
760                                         goto next;
761                                 btrfs_free_path(path);
762                                 return ret;
763                         }
764                 }
765 next:
766                 path->slots[0]++;
767         }
768
769         if (verbose)
770                 printf("Done searching %s\n", dir);
771         btrfs_free_path(path);
772         return 0;
773 }
774
775 static int do_list_roots(struct btrfs_root *root)
776 {
777         struct btrfs_key key;
778         struct btrfs_key found_key;
779         struct btrfs_disk_key disk_key;
780         struct btrfs_path *path;
781         struct extent_buffer *leaf;
782         struct btrfs_root_item ri;
783         unsigned long offset;
784         int slot;
785         int ret;
786
787         root = root->fs_info->tree_root;
788         path = btrfs_alloc_path();
789         if (!path) {
790                 fprintf(stderr, "Failed to alloc path\n");
791                 return -1;
792         }
793
794         key.offset = 0;
795         key.objectid = 0;
796         key.type = BTRFS_ROOT_ITEM_KEY;
797
798         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
799         if (ret < 0) {
800                 fprintf(stderr, "Failed to do search %d\n", ret);
801                 btrfs_free_path(path);
802                 return -1;
803         }
804
805         while (1) {
806                 leaf = path->nodes[0];
807                 slot = path->slots[0];
808                 if (slot >= btrfs_header_nritems(leaf)) {
809                         ret = btrfs_next_leaf(root, path);
810                         if (ret)
811                                 break;
812                         leaf = path->nodes[0];
813                         slot = path->slots[0];
814                 }
815                 btrfs_item_key(leaf, &disk_key, slot);
816                 btrfs_disk_key_to_cpu(&found_key, &disk_key);
817                 if (btrfs_key_type(&found_key) != BTRFS_ROOT_ITEM_KEY) {
818                         path->slots[0]++;
819                         continue;
820                 }
821
822                 offset = btrfs_item_ptr_offset(leaf, slot);
823                 read_extent_buffer(leaf, &ri, offset, sizeof(ri));
824                 printf(" tree ");
825                 btrfs_print_key(&disk_key);
826                 printf(" %Lu level %d\n", btrfs_root_bytenr(&ri),
827                        btrfs_root_level(&ri));
828                 path->slots[0]++;
829         }
830         btrfs_free_path(path);
831
832         return 0;
833 }
834
835 static struct btrfs_root *open_fs(const char *dev, u64 root_location,
836                                   int super_mirror, int list_roots)
837 {
838         struct btrfs_fs_info *fs_info = NULL;
839         struct btrfs_root *root = NULL;
840         u64 bytenr;
841         int i;
842
843         for (i = super_mirror; i < BTRFS_SUPER_MIRROR_MAX; i++) {
844                 bytenr = btrfs_sb_offset(i);
845                 fs_info = open_ctree_fs_info(dev, bytenr, root_location, 0, 1);
846                 if (fs_info)
847                         break;
848                 fprintf(stderr, "Could not open root, trying backup super\n");
849         }
850
851         if (!fs_info)
852                 return NULL;
853
854         /*
855          * All we really need to succeed is reading the chunk tree, everything
856          * else we can do by hand, since we only need to read the tree root and
857          * the fs_root.
858          */
859         if (!extent_buffer_uptodate(fs_info->tree_root->node)) {
860                 u64 generation;
861
862                 root = fs_info->tree_root;
863                 if (!root_location)
864                         root_location = btrfs_super_root(fs_info->super_copy);
865                 generation = btrfs_super_generation(fs_info->super_copy);
866                 root->node = read_tree_block(root, root_location,
867                                              root->leafsize, generation);
868                 if (!extent_buffer_uptodate(root->node)) {
869                         fprintf(stderr, "Error opening tree root\n");
870                         close_ctree(root);
871                         return NULL;
872                 }
873         }
874
875         if (!list_roots && !fs_info->fs_root) {
876                 struct btrfs_key key;
877
878                 key.objectid = BTRFS_FS_TREE_OBJECTID;
879                 key.type = BTRFS_ROOT_ITEM_KEY;
880                 key.offset = (u64)-1;
881                 fs_info->fs_root = btrfs_read_fs_root_no_cache(fs_info, &key);
882                 if (IS_ERR(fs_info->fs_root)) {
883                         fprintf(stderr, "Couldn't read fs root: %ld\n",
884                                 PTR_ERR(fs_info->fs_root));
885                         close_ctree(fs_info->tree_root);
886                         return NULL;
887                 }
888         }
889
890         if (list_roots && do_list_roots(fs_info->tree_root)) {
891                 close_ctree(fs_info->tree_root);
892                 return NULL;
893         }
894
895         return fs_info->fs_root;
896 }
897
898 static int find_first_dir(struct btrfs_root *root, u64 *objectid)
899 {
900         struct btrfs_path *path;
901         struct btrfs_key found_key;
902         struct btrfs_key key;
903         int ret = -1;
904         int i;
905
906         key.objectid = 0;
907         key.type = BTRFS_DIR_INDEX_KEY;
908         key.offset = 0;
909
910         path = btrfs_alloc_path();
911         if (!path) {
912                 fprintf(stderr, "Ran out of memory\n");
913                 return ret;
914         }
915
916         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
917         if (ret < 0) {
918                 fprintf(stderr, "Error searching %d\n", ret);
919                 goto out;
920         }
921
922         if (!path->nodes[0]) {
923                 fprintf(stderr, "No leaf!\n");
924                 goto out;
925         }
926 again:
927         for (i = path->slots[0];
928              i < btrfs_header_nritems(path->nodes[0]); i++) {
929                 btrfs_item_key_to_cpu(path->nodes[0], &found_key, i);
930                 if (found_key.type != key.type)
931                         continue;
932
933                 printf("Using objectid %Lu for first dir\n",
934                        found_key.objectid);
935                 *objectid = found_key.objectid;
936                 ret = 0;
937                 goto out;
938         }
939         do {
940                 ret = next_leaf(root, path);
941                 if (ret < 0) {
942                         fprintf(stderr, "Error getting next leaf %d\n",
943                                 ret);
944                         goto out;
945                 } else if (ret > 0) {
946                         fprintf(stderr, "No more leaves\n");
947                         goto out;
948                 }
949         } while (!path->nodes[0]);
950         if (path->nodes[0])
951                 goto again;
952         printf("Couldn't find a dir index item\n");
953 out:
954         btrfs_free_path(path);
955         return ret;
956 }
957
958 const char * const cmd_restore_usage[] = {
959         "btrfs restore [options] <device>",
960         "Try to restore files from a damaged filesystem (unmounted)",
961         "",
962         "-s              get snapshots",
963         "-v              verbose",
964         "-i              ignore errors",
965         "-o              overwrite",
966         "-t              tree location",
967         "-f <offset>     filesystem location",
968         "-u <block>      super mirror",
969         "-d              find dir",
970         NULL
971 };
972
973 int cmd_restore(int argc, char **argv)
974 {
975         struct btrfs_root *root;
976         struct btrfs_key key;
977         char dir_name[128];
978         u64 tree_location = 0;
979         u64 fs_location = 0;
980         u64 root_objectid = 0;
981         int len;
982         int ret;
983         int opt;
984         int super_mirror = 0;
985         int find_dir = 0;
986         int list_roots = 0;
987
988         while ((opt = getopt(argc, argv, "sviot:u:df:r:l")) != -1) {
989                 switch (opt) {
990                         case 's':
991                                 get_snaps = 1;
992                                 break;
993                         case 'v':
994                                 verbose++;
995                                 break;
996                         case 'i':
997                                 ignore_errors = 1;
998                                 break;
999                         case 'o':
1000                                 overwrite = 1;
1001                                 break;
1002                         case 't':
1003                                 errno = 0;
1004                                 tree_location = (u64)strtoll(optarg, NULL, 10);
1005                                 if (errno != 0) {
1006                                         fprintf(stderr, "Tree location not valid\n");
1007                                         exit(1);
1008                                 }
1009                                 break;
1010                         case 'f':
1011                                 errno = 0;
1012                                 fs_location = (u64)strtoll(optarg, NULL, 10);
1013                                 if (errno != 0) {
1014                                         fprintf(stderr, "Fs location not valid\n");
1015                                         exit(1);
1016                                 }
1017                                 break;
1018                         case 'u':
1019                                 errno = 0;
1020                                 super_mirror = (int)strtol(optarg, NULL, 10);
1021                                 if (errno != 0 ||
1022                                     super_mirror >= BTRFS_SUPER_MIRROR_MAX) {
1023                                         fprintf(stderr, "Super mirror not "
1024                                                 "valid\n");
1025                                         exit(1);
1026                                 }
1027                                 break;
1028                         case 'd':
1029                                 find_dir = 1;
1030                                 break;
1031                         case 'r':
1032                                 errno = 0;
1033                                 root_objectid = (u64)strtoll(optarg, NULL, 10);
1034                                 if (errno != 0) {
1035                                         fprintf(stderr, "Root objectid not valid\n");
1036                                         exit(1);
1037                                 }
1038                                 break;
1039                         case 'l':
1040                                 list_roots = 1;
1041                                 break;
1042                         default:
1043                                 usage(cmd_restore_usage);
1044                 }
1045         }
1046
1047         if (!list_roots && optind + 1 >= argc)
1048                 usage(cmd_restore_usage);
1049         else if (list_roots && optind >= argc)
1050                 usage(cmd_restore_usage);
1051
1052         if ((ret = check_mounted(argv[optind])) < 0) {
1053                 fprintf(stderr, "Could not check mount status: %s\n",
1054                         strerror(-ret));
1055                 return ret;
1056         } else if (ret) {
1057                 fprintf(stderr, "%s is currently mounted.  Aborting.\n", argv[optind]);
1058                 return 1;
1059         }
1060
1061         root = open_fs(argv[optind], tree_location, super_mirror, list_roots);
1062         if (root == NULL)
1063                 return 1;
1064
1065         if (list_roots)
1066                 goto out;
1067
1068         if (fs_location != 0) {
1069                 free_extent_buffer(root->node);
1070                 root->node = read_tree_block(root, fs_location, 4096, 0);
1071                 if (!root->node) {
1072                         fprintf(stderr, "Failed to read fs location\n");
1073                         goto out;
1074                 }
1075         }
1076
1077         memset(path_name, 0, 4096);
1078
1079         strncpy(dir_name, argv[optind + 1], sizeof dir_name);
1080         dir_name[sizeof dir_name - 1] = 0;
1081
1082         /* Strip the trailing / on the dir name */
1083         len = strlen(dir_name);
1084         while (len && dir_name[--len] == '/') {
1085                 dir_name[len] = '\0';
1086         }
1087
1088         if (root_objectid != 0) {
1089                 struct btrfs_root *orig_root = root;
1090
1091                 key.objectid = root_objectid;
1092                 key.type = BTRFS_ROOT_ITEM_KEY;
1093                 key.offset = (u64)-1;
1094                 root = btrfs_read_fs_root(orig_root->fs_info, &key);
1095                 if (IS_ERR(root)) {
1096                         fprintf(stderr, "Error reading root\n");
1097                         root = orig_root;
1098                         ret = 1;
1099                         goto out;
1100                 }
1101                 key.type = 0;
1102                 key.offset = 0;
1103         }
1104
1105         if (find_dir) {
1106                 ret = find_first_dir(root, &key.objectid);
1107                 if (ret)
1108                         goto out;
1109         } else {
1110                 key.objectid = BTRFS_FIRST_FREE_OBJECTID;
1111         }
1112
1113         ret = search_dir(root, &key, dir_name, "");
1114
1115 out:
1116         close_ctree(root);
1117         return ret;
1118 }