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