btrfs-image.c

   1 /*
   2  * Copyright (C) 2008 Oracle.  All rights reserved.
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public
   6  * License v2 as published by the Free Software Foundation.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  11  * General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU General Public
  14  * License along with this program; if not, write to the
  15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  16  * Boston, MA 021110-1307, USA.
  17  */
  18
  19 #include <pthread.h>
  20 #include <stdio.h>
  21 #include <stdlib.h>
  22 #include <sys/types.h>
  23 #include <sys/stat.h>
  24 #include <fcntl.h>
  25 #include <unistd.h>
  26 #include <dirent.h>
  27 #include <zlib.h>
  28 #include "kerncompat.h"
  29 #include "crc32c.h"
  30 #include "ctree.h"
  31 #include "disk-io.h"
  32 #include "transaction.h"
  33 #include "utils.h"
  34 #include "volumes.h"
  35 #include "extent_io.h"
  36
  37 #define HEADER_MAGIC            0xbd5c25e27295668bULL
  38 #define MAX_PENDING_SIZE        (256 * 1024)
  39 #define BLOCK_SIZE              1024
  40 #define BLOCK_MASK              (BLOCK_SIZE - 1)
  41
  42 #define COMPRESS_NONE           0
  43 #define COMPRESS_ZLIB           1
  44
  45 struct meta_cluster_item {
  46         __le64 bytenr;
  47         __le32 size;
  48 } __attribute__ ((__packed__));
  49
  50 struct meta_cluster_header {
  51         __le64 magic;
  52         __le64 bytenr;
  53         __le32 nritems;
  54         u8 compress;
  55 } __attribute__ ((__packed__));
  56
  57 /* cluster header + index items + buffers */
  58 struct meta_cluster {
  59         struct meta_cluster_header header;
  60         struct meta_cluster_item items[];
  61 } __attribute__ ((__packed__));
  62
  63 #define ITEMS_PER_CLUSTER ((BLOCK_SIZE - sizeof(struct meta_cluster)) / \
  64                            sizeof(struct meta_cluster_item))
  65
  66 struct fs_chunk {
  67         u64 logical;
  68         u64 physical;
  69         u64 bytes;
  70         struct rb_node n;
  71 };
  72
  73 struct async_work {
  74         struct list_head list;
  75         struct list_head ordered;
  76         u64 start;
  77         u64 size;
  78         u8 *buffer;
  79         size_t bufsize;
  80         int error;
  81 };
  82
  83 struct metadump_struct {
  84         struct btrfs_root *root;
  85         FILE *out;
  86
  87         struct meta_cluster *cluster;
  88
  89         pthread_t *threads;
  90         size_t num_threads;
  91         pthread_mutex_t mutex;
  92         pthread_cond_t cond;
  93         struct rb_root name_tree;
  94
  95         struct list_head list;
  96         struct list_head ordered;
  97         size_t num_items;
  98         size_t num_ready;
  99
 100         u64 pending_start;
 101         u64 pending_size;
 102
 103         int compress_level;
 104         int done;
 105         int data;
 106         int sanitize_names;
 107
 108         int error;
 109 };
 110
 111 struct name {
 112         struct rb_node n;
 113         char *val;
 114         char *sub;
 115         u32 len;
 116 };
 117
 118 struct mdrestore_struct {
 119         FILE *in;
 120         FILE *out;
 121
 122         pthread_t *threads;
 123         size_t num_threads;
 124         pthread_mutex_t mutex;
 125         pthread_cond_t cond;
 126
 127         struct rb_root chunk_tree;
 128         struct list_head list;
 129         size_t num_items;
 130         u32 leafsize;
 131         u64 devid;
 132         u8 uuid[BTRFS_UUID_SIZE];
 133         u8 fsid[BTRFS_FSID_SIZE];
 134
 135         int compress_method;
 136         int done;
 137         int error;
 138         int old_restore;
 139         int fixup_offset;
 140         int multi_devices;
 141         struct btrfs_fs_info *info;
 142 };
 143
 144 static void print_usage(void) __attribute__((noreturn));
 145 static int search_for_chunk_blocks(struct mdrestore_struct *mdres,
 146                                    u64 search, u64 cluster_bytenr);
 147 static struct extent_buffer *alloc_dummy_eb(u64 bytenr, u32 size);
 148
 149 static void csum_block(u8 *buf, size_t len)
 150 {
 151         char result[BTRFS_CRC32_SIZE];
 152         u32 crc = ~(u32)0;
 153         crc = crc32c(crc, buf + BTRFS_CSUM_SIZE, len - BTRFS_CSUM_SIZE);
 154         btrfs_csum_final(crc, result);
 155         memcpy(buf, result, BTRFS_CRC32_SIZE);
 156 }
 157
 158 static int has_name(struct btrfs_key *key)
 159 {
 160         switch (key->type) {
 161         case BTRFS_DIR_ITEM_KEY:
 162         case BTRFS_DIR_INDEX_KEY:
 163         case BTRFS_INODE_REF_KEY:
 164         case BTRFS_INODE_EXTREF_KEY:
 165         case BTRFS_XATTR_ITEM_KEY:
 166                 return 1;
 167         default:
 168                 break;
 169         }
 170
 171         return 0;
 172 }
 173
 174 static char *generate_garbage(u32 name_len)
 175 {
 176         char *buf = malloc(name_len);
 177         int i;
 178
 179         if (!buf)
 180                 return NULL;
 181
 182         for (i = 0; i < name_len; i++) {
 183                 char c = rand() % 94 + 33;
 184
 185                 if (c == '/')
 186                         c++;
 187                 buf[i] = c;
 188         }
 189
 190         return buf;
 191 }
 192
 193 static int name_cmp(struct rb_node *a, struct rb_node *b, int fuzz)
 194 {
 195         struct name *entry = rb_entry(a, struct name, n);
 196         struct name *ins = rb_entry(b, struct name, n);
 197         u32 len;
 198
 199         len = min(ins->len, entry->len);
 200         return memcmp(ins->val, entry->val, len);
 201 }
 202
 203 static int chunk_cmp(struct rb_node *a, struct rb_node *b, int fuzz)
 204 {
 205         struct fs_chunk *entry = rb_entry(a, struct fs_chunk, n);
 206         struct fs_chunk *ins = rb_entry(b, struct fs_chunk, n);
 207
 208         if (fuzz && ins->logical >= entry->logical &&
 209             ins->logical < entry->logical + entry->bytes)
 210                 return 0;
 211
 212         if (ins->logical < entry->logical)
 213                 return -1;
 214         else if (ins->logical > entry->logical)
 215                 return 1;
 216         return 0;
 217 }
 218
 219 static void tree_insert(struct rb_root *root, struct rb_node *ins,
 220                         int (*cmp)(struct rb_node *a, struct rb_node *b,
 221                                    int fuzz))
 222 {
 223         struct rb_node ** p = &root->rb_node;
 224         struct rb_node * parent = NULL;
 225         int dir;
 226
 227         while(*p) {
 228                 parent = *p;
 229
 230                 dir = cmp(*p, ins, 0);
 231                 if (dir < 0)
 232                         p = &(*p)->rb_left;
 233                 else if (dir > 0)
 234                         p = &(*p)->rb_right;
 235                 else
 236                         BUG();
 237         }
 238
 239         rb_link_node(ins, parent, p);
 240         rb_insert_color(ins, root);
 241 }
 242
 243 static struct rb_node *tree_search(struct rb_root *root,
 244                                    struct rb_node *search,
 245                                    int (*cmp)(struct rb_node *a,
 246                                               struct rb_node *b, int fuzz),
 247                                    int fuzz)
 248 {
 249         struct rb_node *n = root->rb_node;
 250         int dir;
 251
 252         while (n) {
 253                 dir = cmp(n, search, fuzz);
 254                 if (dir < 0)
 255                         n = n->rb_left;
 256                 else if (dir > 0)
 257                         n = n->rb_right;
 258                 else
 259                         return n;
 260         }
 261
 262         return NULL;
 263 }
 264
 265 static char *find_collision(struct metadump_struct *md, char *name,
 266                             u32 name_len)
 267 {
 268         struct name *val;
 269         struct rb_node *entry;
 270         struct name tmp;
 271         unsigned long checksum;
 272         int found = 0;
 273         int i;
 274
 275         tmp.val = name;
 276         tmp.len = name_len;
 277         entry = tree_search(&md->name_tree, &tmp.n, name_cmp, 0);
 278         if (entry) {
 279                 val = rb_entry(entry, struct name, n);
 280                 free(name);
 281                 return val->sub;
 282         }
 283
 284         val = malloc(sizeof(struct name));
 285         if (!val) {
 286                 fprintf(stderr, "Couldn't sanitize name, enomem\n");
 287                 free(name);
 288                 return NULL;
 289         }
 290
 291         memset(val, 0, sizeof(*val));
 292
 293         val->val = name;
 294         val->len = name_len;
 295         val->sub = malloc(name_len);
 296         if (!val->sub) {
 297                 fprintf(stderr, "Couldn't sanitize name, enomem\n");
 298                 free(val);
 299                 free(name);
 300                 return NULL;
 301         }
 302
 303         checksum = crc32c(~1, val->val, name_len);
 304         memset(val->sub, ' ', name_len);
 305         i = 0;
 306         while (1) {
 307                 if (crc32c(~1, val->sub, name_len) == checksum &&
 308                     memcmp(val->sub, val->val, val->len)) {
 309                         found = 1;
 310                         break;
 311                 }
 312
 313                 if (val->sub[i] == 127) {
 314                         do {
 315                                 i++;
 316                                 if (i >= name_len)
 317                                         break;
 318                         } while (val->sub[i] == 127);
 319
 320                         if (i >= name_len)
 321                                 break;
 322                         val->sub[i]++;
 323                         if (val->sub[i] == '/')
 324                                 val->sub[i]++;
 325                         memset(val->sub, ' ', i);
 326                         i = 0;
 327                         continue;
 328                 } else {
 329                         val->sub[i]++;
 330                         if (val->sub[i] == '/')
 331                                 val->sub[i]++;
 332                 }
 333         }
 334
 335         if (!found) {
 336                 fprintf(stderr, "Couldn't find a collision for '%.*s', "
 337                         "generating normal garbage, it won't match indexes\n",
 338                         val->len, val->val);
 339                 for (i = 0; i < name_len; i++) {
 340                         char c = rand() % 94 + 33;
 341
 342                         if (c == '/')
 343                                 c++;
 344                         val->sub[i] = c;
 345                 }
 346         }
 347
 348         tree_insert(&md->name_tree, &val->n, name_cmp);
 349         return val->sub;
 350 }
 351
 352 static void sanitize_dir_item(struct metadump_struct *md, struct extent_buffer *eb,
 353                               int slot)
 354 {
 355         struct btrfs_dir_item *dir_item;
 356         char *buf;
 357         char *garbage;
 358         unsigned long name_ptr;
 359         u32 total_len;
 360         u32 cur = 0;
 361         u32 this_len;
 362         u32 name_len;
 363         int free_garbage = (md->sanitize_names == 1);
 364
 365         dir_item = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);
 366         total_len = btrfs_item_size_nr(eb, slot);
 367         while (cur < total_len) {
 368                 this_len = sizeof(*dir_item) +
 369                         btrfs_dir_name_len(eb, dir_item) +
 370                         btrfs_dir_data_len(eb, dir_item);
 371                 name_ptr = (unsigned long)(dir_item + 1);
 372                 name_len = btrfs_dir_name_len(eb, dir_item);
 373
 374                 if (md->sanitize_names > 1) {
 375                         buf = malloc(name_len);
 376                         if (!buf) {
 377                                 fprintf(stderr, "Couldn't sanitize name, "
 378                                         "enomem\n");
 379                                 return;
 380                         }
 381                         read_extent_buffer(eb, buf, name_ptr, name_len);
 382                         garbage = find_collision(md, buf, name_len);
 383                 } else {
 384                         garbage = generate_garbage(name_len);
 385                 }
 386                 if (!garbage) {
 387                         fprintf(stderr, "Couldn't sanitize name, enomem\n");
 388                         return;
 389                 }
 390                 write_extent_buffer(eb, garbage, name_ptr, name_len);
 391                 cur += this_len;
 392                 dir_item = (struct btrfs_dir_item *)((char *)dir_item +
 393                                                      this_len);
 394                 if (free_garbage)
 395                         free(garbage);
 396         }
 397 }
 398
 399 static void sanitize_inode_ref(struct metadump_struct *md,
 400                                struct extent_buffer *eb, int slot, int ext)
 401 {
 402         struct btrfs_inode_extref *extref;
 403         struct btrfs_inode_ref *ref;
 404         char *garbage, *buf;
 405         unsigned long ptr;
 406         unsigned long name_ptr;
 407         u32 item_size;
 408         u32 cur_offset = 0;
 409         int len;
 410         int free_garbage = (md->sanitize_names == 1);
 411
 412         item_size = btrfs_item_size_nr(eb, slot);
 413         ptr = btrfs_item_ptr_offset(eb, slot);
 414         while (cur_offset < item_size) {
 415                 if (ext) {
 416                         extref = (struct btrfs_inode_extref *)(ptr +
 417                                                                cur_offset);
 418                         name_ptr = (unsigned long)(&extref->name);
 419                         len = btrfs_inode_extref_name_len(eb, extref);
 420                         cur_offset += sizeof(*extref);
 421                 } else {
 422                         ref = (struct btrfs_inode_ref *)(ptr + cur_offset);
 423                         len = btrfs_inode_ref_name_len(eb, ref);
 424                         name_ptr = (unsigned long)(ref + 1);
 425                         cur_offset += sizeof(*ref);
 426                 }
 427                 cur_offset += len;
 428
 429                 if (md->sanitize_names > 1) {
 430                         buf = malloc(len);
 431                         if (!buf) {
 432                                 fprintf(stderr, "Couldn't sanitize name, "
 433                                         "enomem\n");
 434                                 return;
 435                         }
 436                         read_extent_buffer(eb, buf, name_ptr, len);
 437                         garbage = find_collision(md, buf, len);
 438                 } else {
 439                         garbage = generate_garbage(len);
 440                 }
 441
 442                 if (!garbage) {
 443                         fprintf(stderr, "Couldn't sanitize name, enomem\n");
 444                         return;
 445                 }
 446                 write_extent_buffer(eb, garbage, name_ptr, len);
 447                 if (free_garbage)
 448                         free(garbage);
 449         }
 450 }
 451
 452 static void sanitize_xattr(struct metadump_struct *md,
 453                            struct extent_buffer *eb, int slot)
 454 {
 455         struct btrfs_dir_item *dir_item;
 456         unsigned long data_ptr;
 457         u32 data_len;
 458
 459         dir_item = btrfs_item_ptr(eb, slot, struct btrfs_dir_item);
 460         data_len = btrfs_dir_data_len(eb, dir_item);
 461
 462         data_ptr = (unsigned long)((char *)(dir_item + 1) +
 463                                    btrfs_dir_name_len(eb, dir_item));
 464         memset_extent_buffer(eb, 0, data_ptr, data_len);
 465 }
 466
 467 static void sanitize_name(struct metadump_struct *md, u8 *dst,
 468                           struct extent_buffer *src, struct btrfs_key *key,
 469                           int slot)
 470 {
 471         struct extent_buffer *eb;
 472
 473         eb = alloc_dummy_eb(src->start, src->len);
 474         if (!eb) {
 475                 fprintf(stderr, "Couldn't sanitize name, no memory\n");
 476                 return;
 477         }
 478
 479         memcpy(eb->data, dst, eb->len);
 480
 481         switch (key->type) {
 482         case BTRFS_DIR_ITEM_KEY:
 483         case BTRFS_DIR_INDEX_KEY:
 484                 sanitize_dir_item(md, eb, slot);
 485                 break;
 486         case BTRFS_INODE_REF_KEY:
 487                 sanitize_inode_ref(md, eb, slot, 0);
 488                 break;
 489         case BTRFS_INODE_EXTREF_KEY:
 490                 sanitize_inode_ref(md, eb, slot, 1);
 491                 break;
 492         case BTRFS_XATTR_ITEM_KEY:
 493                 sanitize_xattr(md, eb, slot);
 494                 break;
 495         default:
 496                 break;
 497         }
 498
 499         memcpy(dst, eb->data, eb->len);
 500         free(eb);
 501 }
 502
 503 /*
 504  * zero inline extents and csum items
 505  */
 506 static void zero_items(struct metadump_struct *md, u8 *dst,
 507                        struct extent_buffer *src)
 508 {
 509         struct btrfs_file_extent_item *fi;
 510         struct btrfs_item *item;
 511         struct btrfs_key key;
 512         u32 nritems = btrfs_header_nritems(src);
 513         size_t size;
 514         unsigned long ptr;
 515         int i, extent_type;
 516
 517         for (i = 0; i < nritems; i++) {
 518                 item = btrfs_item_nr(i);
 519                 btrfs_item_key_to_cpu(src, &key, i);
 520                 if (key.type == BTRFS_CSUM_ITEM_KEY) {
 521                         size = btrfs_item_size_nr(src, i);
 522                         memset(dst + btrfs_leaf_data(src) +
 523                                btrfs_item_offset_nr(src, i), 0, size);
 524                         continue;
 525                 }
 526
 527                 if (md->sanitize_names && has_name(&key)) {
 528                         sanitize_name(md, dst, src, &key, i);
 529                         continue;
 530                 }
 531
 532                 if (key.type != BTRFS_EXTENT_DATA_KEY)
 533                         continue;
 534
 535                 fi = btrfs_item_ptr(src, i, struct btrfs_file_extent_item);
 536                 extent_type = btrfs_file_extent_type(src, fi);
 537                 if (extent_type != BTRFS_FILE_EXTENT_INLINE)
 538                         continue;
 539
 540                 ptr = btrfs_file_extent_inline_start(fi);
 541                 size = btrfs_file_extent_inline_item_len(src, item);
 542                 memset(dst + ptr, 0, size);
 543         }
 544 }
 545
 546 /*
 547  * copy buffer and zero useless data in the buffer
 548  */
 549 static void copy_buffer(struct metadump_struct *md, u8 *dst,
 550                         struct extent_buffer *src)
 551 {
 552         int level;
 553         size_t size;
 554         u32 nritems;
 555
 556         memcpy(dst, src->data, src->len);
 557         if (src->start == BTRFS_SUPER_INFO_OFFSET)
 558                 return;
 559
 560         level = btrfs_header_level(src);
 561         nritems = btrfs_header_nritems(src);
 562
 563         if (nritems == 0) {
 564                 size = sizeof(struct btrfs_header);
 565                 memset(dst + size, 0, src->len - size);
 566         } else if (level == 0) {
 567                 size = btrfs_leaf_data(src) +
 568                         btrfs_item_offset_nr(src, nritems - 1) -
 569                         btrfs_item_nr_offset(nritems);
 570                 memset(dst + btrfs_item_nr_offset(nritems), 0, size);
 571                 zero_items(md, dst, src);
 572         } else {
 573                 size = offsetof(struct btrfs_node, ptrs) +
 574                         sizeof(struct btrfs_key_ptr) * nritems;
 575                 memset(dst + size, 0, src->len - size);
 576         }
 577         csum_block(dst, src->len);
 578 }
 579
 580 static void *dump_worker(void *data)
 581 {
 582         struct metadump_struct *md = (struct metadump_struct *)data;
 583         struct async_work *async;
 584         int ret;
 585
 586         while (1) {
 587                 pthread_mutex_lock(&md->mutex);
 588                 while (list_empty(&md->list)) {
 589                         if (md->done) {
 590                                 pthread_mutex_unlock(&md->mutex);
 591                                 goto out;
 592                         }
 593                         pthread_cond_wait(&md->cond, &md->mutex);
 594                 }
 595                 async = list_entry(md->list.next, struct async_work, list);
 596                 list_del_init(&async->list);
 597                 pthread_mutex_unlock(&md->mutex);
 598
 599                 if (md->compress_level > 0) {
 600                         u8 *orig = async->buffer;
 601
 602                         async->bufsize = compressBound(async->size);
 603                         async->buffer = malloc(async->bufsize);
 604                         if (!async->buffer) {
 605                                 fprintf(stderr, "Error allocing buffer\n");
 606                                 pthread_mutex_lock(&md->mutex);
 607                                 if (!md->error)
 608                                         md->error = -ENOMEM;
 609                                 pthread_mutex_unlock(&md->mutex);
 610                                 pthread_exit(NULL);
 611                         }
 612
 613                         ret = compress2(async->buffer,
 614                                          (unsigned long *)&async->bufsize,
 615                                          orig, async->size, md->compress_level);
 616
 617                         if (ret != Z_OK)
 618                                 async->error = 1;
 619
 620                         free(orig);
 621                 }
 622
 623                 pthread_mutex_lock(&md->mutex);
 624                 md->num_ready++;
 625                 pthread_mutex_unlock(&md->mutex);
 626         }
 627 out:
 628         pthread_exit(NULL);
 629 }
 630
 631 static void meta_cluster_init(struct metadump_struct *md, u64 start)
 632 {
 633         struct meta_cluster_header *header;
 634
 635         md->num_items = 0;
 636         md->num_ready = 0;
 637         header = &md->cluster->header;
 638         header->magic = cpu_to_le64(HEADER_MAGIC);
 639         header->bytenr = cpu_to_le64(start);
 640         header->nritems = cpu_to_le32(0);
 641         header->compress = md->compress_level > 0 ?
 642                            COMPRESS_ZLIB : COMPRESS_NONE;
 643 }
 644
 645 static void metadump_destroy(struct metadump_struct *md, int num_threads)
 646 {
 647         int i;
 648         struct rb_node *n;
 649
 650         pthread_mutex_lock(&md->mutex);
 651         md->done = 1;
 652         pthread_cond_broadcast(&md->cond);
 653         pthread_mutex_unlock(&md->mutex);
 654
 655         for (i = 0; i < num_threads; i++)
 656                 pthread_join(md->threads[i], NULL);
 657
 658         pthread_cond_destroy(&md->cond);
 659         pthread_mutex_destroy(&md->mutex);
 660
 661         while ((n = rb_first(&md->name_tree))) {
 662                 struct name *name;
 663
 664                 name = rb_entry(n, struct name, n);
 665                 rb_erase(n, &md->name_tree);
 666                 free(name->val);
 667                 free(name->sub);
 668                 free(name);
 669         }
 670         free(md->threads);
 671         free(md->cluster);
 672 }
 673
 674 static int metadump_init(struct metadump_struct *md, struct btrfs_root *root,
 675                          FILE *out, int num_threads, int compress_level,
 676                          int sanitize_names)
 677 {
 678         int i, ret = 0;
 679
 680         memset(md, 0, sizeof(*md));
 681         pthread_cond_init(&md->cond, NULL);
 682         pthread_mutex_init(&md->mutex, NULL);
 683         INIT_LIST_HEAD(&md->list);
 684         INIT_LIST_HEAD(&md->ordered);
 685         md->root = root;
 686         md->out = out;
 687         md->pending_start = (u64)-1;
 688         md->compress_level = compress_level;
 689         md->cluster = calloc(1, BLOCK_SIZE);
 690         md->sanitize_names = sanitize_names;
 691         if (sanitize_names > 1)
 692                 crc32c_optimization_init();
 693
 694         if (!md->cluster) {
 695                 pthread_cond_destroy(&md->cond);
 696                 pthread_mutex_destroy(&md->mutex);
 697                 return -ENOMEM;
 698         }
 699
 700         meta_cluster_init(md, 0);
 701         if (!num_threads)
 702                 return 0;
 703
 704         md->name_tree.rb_node = NULL;
 705         md->num_threads = num_threads;
 706         md->threads = calloc(num_threads, sizeof(pthread_t));
 707         if (!md->threads) {
 708                 free(md->cluster);
 709                 pthread_cond_destroy(&md->cond);
 710                 pthread_mutex_destroy(&md->mutex);
 711                 return -ENOMEM;
 712         }
 713
 714         for (i = 0; i < num_threads; i++) {
 715                 ret = pthread_create(md->threads + i, NULL, dump_worker, md);
 716                 if (ret)
 717                         break;
 718         }
 719
 720         if (ret)
 721                 metadump_destroy(md, i + 1);
 722
 723         return ret;
 724 }
 725
 726 static int write_zero(FILE *out, size_t size)
 727 {
 728         static char zero[BLOCK_SIZE];
 729         return fwrite(zero, size, 1, out);
 730 }
 731
 732 static int write_buffers(struct metadump_struct *md, u64 *next)
 733 {
 734         struct meta_cluster_header *header = &md->cluster->header;
 735         struct meta_cluster_item *item;
 736         struct async_work *async;
 737         u64 bytenr = 0;
 738         u32 nritems = 0;
 739         int ret;
 740         int err = 0;
 741
 742         if (list_empty(&md->ordered))
 743                 goto out;
 744
 745         /* wait until all buffers are compressed */
 746         while (!err && md->num_items > md->num_ready) {
 747                 struct timespec ts = {
 748                         .tv_sec = 0,
 749                         .tv_nsec = 10000000,
 750                 };
 751                 pthread_mutex_unlock(&md->mutex);
 752                 nanosleep(&ts, NULL);
 753                 pthread_mutex_lock(&md->mutex);
 754                 err = md->error;
 755         }
 756
 757         if (err) {
 758                 fprintf(stderr, "One of the threads errored out %s\n",
 759                                 strerror(err));
 760                 goto out;
 761         }
 762
 763         /* setup and write index block */
 764         list_for_each_entry(async, &md->ordered, ordered) {
 765                 item = md->cluster->items + nritems;
 766                 item->bytenr = cpu_to_le64(async->start);
 767                 item->size = cpu_to_le32(async->bufsize);
 768                 nritems++;
 769         }
 770         header->nritems = cpu_to_le32(nritems);
 771
 772         ret = fwrite(md->cluster, BLOCK_SIZE, 1, md->out);
 773         if (ret != 1) {
 774                 fprintf(stderr, "Error writing out cluster: %d\n", errno);
 775                 return -EIO;
 776         }
 777
 778         /* write buffers */
 779         bytenr += le64_to_cpu(header->bytenr) + BLOCK_SIZE;
 780         while (!list_empty(&md->ordered)) {
 781                 async = list_entry(md->ordered.next, struct async_work,
 782                                    ordered);
 783                 list_del_init(&async->ordered);
 784
 785                 bytenr += async->bufsize;
 786                 if (!err)
 787                         ret = fwrite(async->buffer, async->bufsize, 1,
 788                                      md->out);
 789                 if (ret != 1) {
 790                         err = -EIO;
 791                         ret = 0;
 792                         fprintf(stderr, "Error writing out cluster: %d\n",
 793                                 errno);
 794                 }
 795
 796                 free(async->buffer);
 797                 free(async);
 798         }
 799
 800         /* zero unused space in the last block */
 801         if (!err && bytenr & BLOCK_MASK) {
 802                 size_t size = BLOCK_SIZE - (bytenr & BLOCK_MASK);
 803
 804                 bytenr += size;
 805                 ret = write_zero(md->out, size);
 806                 if (ret != 1) {
 807                         fprintf(stderr, "Error zeroing out buffer: %d\n",
 808                                 errno);
 809                         err = -EIO;
 810                 }
 811         }
 812 out:
 813         *next = bytenr;
 814         return err;
 815 }
 816
 817 static int read_data_extent(struct metadump_struct *md,
 818                             struct async_work *async)
 819 {
 820         struct btrfs_multi_bio *multi = NULL;
 821         struct btrfs_device *device;
 822         u64 bytes_left = async->size;
 823         u64 logical = async->start;
 824         u64 offset = 0;
 825         u64 bytenr;
 826         u64 read_len;
 827         ssize_t done;
 828         int fd;
 829         int ret;
 830
 831         while (bytes_left) {
 832                 read_len = bytes_left;
 833                 ret = btrfs_map_block(&md->root->fs_info->mapping_tree, READ,
 834                                       logical, &read_len, &multi, 0, NULL);
 835                 if (ret) {
 836                         fprintf(stderr, "Couldn't map data block %d\n", ret);
 837                         return ret;
 838                 }
 839
 840                 device = multi->stripes[0].dev;
 841
 842                 if (device->fd == 0) {
 843                         fprintf(stderr,
 844                                 "Device we need to read from is not open\n");
 845                         free(multi);
 846                         return -EIO;
 847                 }
 848                 fd = device->fd;
 849                 bytenr = multi->stripes[0].physical;
 850                 free(multi);
 851
 852                 read_len = min(read_len, bytes_left);
 853                 done = pread64(fd, async->buffer+offset, read_len, bytenr);
 854                 if (done < read_len) {
 855                         if (done < 0)
 856                                 fprintf(stderr, "Error reading extent %d\n",
 857                                         errno);
 858                         else
 859                                 fprintf(stderr, "Short read\n");
 860                         return -EIO;
 861                 }
 862
 863                 bytes_left -= done;
 864                 offset += done;
 865                 logical += done;
 866         }
 867
 868         return 0;
 869 }
 870
 871 static int get_dev_fd(struct btrfs_root *root)
 872 {
 873         struct btrfs_device *dev;
 874
 875         dev = list_first_entry(&root->fs_info->fs_devices->devices,
 876                                struct btrfs_device, dev_list);
 877         return dev->fd;
 878 }
 879
 880 static int flush_pending(struct metadump_struct *md, int done)
 881 {
 882         struct async_work *async = NULL;
 883         struct extent_buffer *eb;
 884         u64 blocksize = md->root->nodesize;
 885         u64 start;
 886         u64 size;
 887         size_t offset;
 888         int ret = 0;
 889
 890         if (md->pending_size) {
 891                 async = calloc(1, sizeof(*async));
 892                 if (!async)
 893                         return -ENOMEM;
 894
 895                 async->start = md->pending_start;
 896                 async->size = md->pending_size;
 897                 async->bufsize = async->size;
 898                 async->buffer = malloc(async->bufsize);
 899                 if (!async->buffer) {
 900                         free(async);
 901                         return -ENOMEM;
 902                 }
 903                 offset = 0;
 904                 start = async->start;
 905                 size = async->size;
 906
 907                 if (md->data) {
 908                         ret = read_data_extent(md, async);
 909                         if (ret) {
 910                                 free(async->buffer);
 911                                 free(async);
 912                                 return ret;
 913                         }
 914                 }
 915
 916                 /*
 917                  * Balance can make the mapping not cover the super block, so
 918                  * just copy directly from one of the devices.
 919                  */
 920                 if (start == BTRFS_SUPER_INFO_OFFSET) {
 921                         int fd = get_dev_fd(md->root);
 922
 923                         ret = pread64(fd, async->buffer, size, start);
 924                         if (ret < size) {
 925                                 free(async->buffer);
 926                                 free(async);
 927                                 fprintf(stderr, "Error reading superblock\n");
 928                                 return -EIO;
 929                         }
 930                         size = 0;
 931                         ret = 0;
 932                 }
 933
 934                 while (!md->data && size > 0) {
 935                         u64 this_read = min(blocksize, size);
 936                         eb = read_tree_block(md->root, start, this_read, 0);
 937                         if (!extent_buffer_uptodate(eb)) {
 938                                 free(async->buffer);
 939                                 free(async);
 940                                 fprintf(stderr,
 941                                         "Error reading metadata block\n");
 942                                 return -EIO;
 943                         }
 944                         copy_buffer(md, async->buffer + offset, eb);
 945                         free_extent_buffer(eb);
 946                         start += this_read;
 947                         offset += this_read;
 948                         size -= this_read;
 949                 }
 950
 951                 md->pending_start = (u64)-1;
 952                 md->pending_size = 0;
 953         } else if (!done) {
 954                 return 0;
 955         }
 956
 957         pthread_mutex_lock(&md->mutex);
 958         if (async) {
 959                 list_add_tail(&async->ordered, &md->ordered);
 960                 md->num_items++;
 961                 if (md->compress_level > 0) {
 962                         list_add_tail(&async->list, &md->list);
 963                         pthread_cond_signal(&md->cond);
 964                 } else {
 965                         md->num_ready++;
 966                 }
 967         }
 968         if (md->num_items >= ITEMS_PER_CLUSTER || done) {
 969                 ret = write_buffers(md, &start);
 970                 if (ret)
 971                         fprintf(stderr, "Error writing buffers %d\n",
 972                                 errno);
 973                 else
 974                         meta_cluster_init(md, start);
 975         }
 976         pthread_mutex_unlock(&md->mutex);
 977         return ret;
 978 }
 979
 980 static int add_extent(u64 start, u64 size, struct metadump_struct *md,
 981                       int data)
 982 {
 983         int ret;
 984         if (md->data != data ||
 985             md->pending_size + size > MAX_PENDING_SIZE ||
 986             md->pending_start + md->pending_size != start) {
 987                 ret = flush_pending(md, 0);
 988                 if (ret)
 989                         return ret;
 990                 md->pending_start = start;
 991         }
 992         readahead_tree_block(md->root, start, size, 0);
 993         md->pending_size += size;
 994         md->data = data;
 995         return 0;
 996 }
 997
 998 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
 999 static int is_tree_block(struct btrfs_root *extent_root,
1000                          struct btrfs_path *path, u64 bytenr)
1001 {
1002         struct extent_buffer *leaf;
1003         struct btrfs_key key;
1004         u64 ref_objectid;
1005         int ret;
1006
1007         leaf = path->nodes[0];
1008         while (1) {
1009                 struct btrfs_extent_ref_v0 *ref_item;
1010                 path->slots[0]++;
1011                 if (path->slots[0] >= btrfs_header_nritems(leaf)) {
1012                         ret = btrfs_next_leaf(extent_root, path);
1013                         if (ret < 0)
1014                                 return ret;
1015                         if (ret > 0)
1016                                 break;
1017                         leaf = path->nodes[0];
1018                 }
1019                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
1020                 if (key.objectid != bytenr)
1021                         break;
1022                 if (key.type != BTRFS_EXTENT_REF_V0_KEY)
1023                         continue;
1024                 ref_item = btrfs_item_ptr(leaf, path->slots[0],
1025                                           struct btrfs_extent_ref_v0);
1026                 ref_objectid = btrfs_ref_objectid_v0(leaf, ref_item);
1027                 if (ref_objectid < BTRFS_FIRST_FREE_OBJECTID)
1028                         return 1;
1029                 break;
1030         }
1031         return 0;
1032 }
1033 #endif
1034
1035 static int copy_tree_blocks(struct btrfs_root *root, struct extent_buffer *eb,
1036                             struct metadump_struct *metadump, int root_tree)
1037 {
1038         struct extent_buffer *tmp;
1039         struct btrfs_root_item *ri;
1040         struct btrfs_key key;
1041         u64 bytenr;
1042         int level;
1043         int nritems = 0;
1044         int i = 0;
1045         int ret;
1046
1047         ret = add_extent(btrfs_header_bytenr(eb), root->leafsize, metadump, 0);
1048         if (ret) {
1049                 fprintf(stderr, "Error adding metadata block\n");
1050                 return ret;
1051         }
1052
1053         if (btrfs_header_level(eb) == 0 && !root_tree)
1054                 return 0;
1055
1056         level = btrfs_header_level(eb);
1057         nritems = btrfs_header_nritems(eb);
1058         for (i = 0; i < nritems; i++) {
1059                 if (level == 0) {
1060                         btrfs_item_key_to_cpu(eb, &key, i);
1061                         if (key.type != BTRFS_ROOT_ITEM_KEY)
1062                                 continue;
1063                         ri = btrfs_item_ptr(eb, i, struct btrfs_root_item);
1064                         bytenr = btrfs_disk_root_bytenr(eb, ri);
1065                         tmp = read_tree_block(root, bytenr, root->leafsize, 0);
1066                         if (!extent_buffer_uptodate(tmp)) {
1067                                 fprintf(stderr,
1068                                         "Error reading log root block\n");
1069                                 return -EIO;
1070                         }
1071                         ret = copy_tree_blocks(root, tmp, metadump, 0);
1072                         free_extent_buffer(tmp);
1073                         if (ret)
1074                                 return ret;
1075                 } else {
1076                         bytenr = btrfs_node_blockptr(eb, i);
1077                         tmp = read_tree_block(root, bytenr, root->leafsize, 0);
1078                         if (!extent_buffer_uptodate(tmp)) {
1079                                 fprintf(stderr, "Error reading log block\n");
1080                                 return -EIO;
1081                         }
1082                         ret = copy_tree_blocks(root, tmp, metadump, root_tree);
1083                         free_extent_buffer(tmp);
1084                         if (ret)
1085                                 return ret;
1086                 }
1087         }
1088
1089         return 0;
1090 }
1091
1092 static int copy_log_trees(struct btrfs_root *root,
1093                           struct metadump_struct *metadump,
1094                           struct btrfs_path *path)
1095 {
1096         u64 blocknr = btrfs_super_log_root(root->fs_info->super_copy);
1097
1098         if (blocknr == 0)
1099                 return 0;
1100
1101         if (!root->fs_info->log_root_tree ||
1102             !root->fs_info->log_root_tree->node) {
1103                 fprintf(stderr, "Error copying tree log, it wasn't setup\n");
1104                 return -EIO;
1105         }
1106
1107         return copy_tree_blocks(root, root->fs_info->log_root_tree->node,
1108                                 metadump, 1);
1109 }
1110
1111 static int copy_space_cache(struct btrfs_root *root,
1112                             struct metadump_struct *metadump,
1113                             struct btrfs_path *path)
1114 {
1115         struct extent_buffer *leaf;
1116         struct btrfs_file_extent_item *fi;
1117         struct btrfs_key key;
1118         u64 bytenr, num_bytes;
1119         int ret;
1120
1121         root = root->fs_info->tree_root;
1122
1123         key.objectid = 0;
1124         key.type = BTRFS_EXTENT_DATA_KEY;
1125         key.offset = 0;
1126
1127         ret = btrfs_search_slot(NULL, root, &key, path, 0, 0);
1128         if (ret < 0) {
1129                 fprintf(stderr, "Error searching for free space inode %d\n",
1130                         ret);
1131                 return ret;
1132         }
1133
1134         leaf = path->nodes[0];
1135
1136         while (1) {
1137                 if (path->slots[0] >= btrfs_header_nritems(leaf)) {
1138                         ret = btrfs_next_leaf(root, path);
1139                         if (ret < 0) {
1140                                 fprintf(stderr, "Error going to next leaf "
1141                                         "%d\n", ret);
1142                                 return ret;
1143                         }
1144                         if (ret > 0)
1145                                 break;
1146                         leaf = path->nodes[0];
1147                 }
1148
1149                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
1150                 if (key.type != BTRFS_EXTENT_DATA_KEY) {
1151                         path->slots[0]++;
1152                         continue;
1153                 }
1154
1155                 fi = btrfs_item_ptr(leaf, path->slots[0],
1156                                     struct btrfs_file_extent_item);
1157                 if (btrfs_file_extent_type(leaf, fi) !=
1158                     BTRFS_FILE_EXTENT_REG) {
1159                         path->slots[0]++;
1160                         continue;
1161                 }
1162
1163                 bytenr = btrfs_file_extent_disk_bytenr(leaf, fi);
1164                 num_bytes = btrfs_file_extent_disk_num_bytes(leaf, fi);
1165                 ret = add_extent(bytenr, num_bytes, metadump, 1);
1166                 if (ret) {
1167                         fprintf(stderr, "Error adding space cache blocks %d\n",
1168                                 ret);
1169                         btrfs_release_path(path);
1170                         return ret;
1171                 }
1172                 path->slots[0]++;
1173         }
1174
1175         return 0;
1176 }
1177
1178 static int copy_from_extent_tree(struct metadump_struct *metadump,
1179                                  struct btrfs_path *path)
1180 {
1181         struct btrfs_root *extent_root;
1182         struct extent_buffer *leaf;
1183         struct btrfs_extent_item *ei;
1184         struct btrfs_key key;
1185         u64 bytenr;
1186         u64 num_bytes;
1187         int ret;
1188
1189         extent_root = metadump->root->fs_info->extent_root;
1190         bytenr = BTRFS_SUPER_INFO_OFFSET + BTRFS_SUPER_INFO_SIZE;
1191         key.objectid = bytenr;
1192         key.type = BTRFS_EXTENT_ITEM_KEY;
1193         key.offset = 0;
1194
1195         ret = btrfs_search_slot(NULL, extent_root, &key, path, 0, 0);
1196         if (ret < 0) {
1197                 fprintf(stderr, "Error searching extent root %d\n", ret);
1198                 return ret;
1199         }
1200         ret = 0;
1201
1202         leaf = path->nodes[0];
1203
1204         while (1) {
1205                 if (path->slots[0] >= btrfs_header_nritems(leaf)) {
1206                         ret = btrfs_next_leaf(extent_root, path);
1207                         if (ret < 0) {
1208                                 fprintf(stderr, "Error going to next leaf %d"
1209                                         "\n", ret);
1210                                 break;
1211                         }
1212                         if (ret > 0) {
1213                                 ret = 0;
1214                                 break;
1215                         }
1216                         leaf = path->nodes[0];
1217                 }
1218
1219                 btrfs_item_key_to_cpu(leaf, &key, path->slots[0]);
1220                 if (key.objectid < bytenr ||
1221                     (key.type != BTRFS_EXTENT_ITEM_KEY &&
1222                      key.type != BTRFS_METADATA_ITEM_KEY)) {
1223                         path->slots[0]++;
1224                         continue;
1225                 }
1226
1227                 bytenr = key.objectid;
1228                 if (key.type == BTRFS_METADATA_ITEM_KEY)
1229                         num_bytes = extent_root->leafsize;
1230                 else
1231                         num_bytes = key.offset;
1232
1233                 if (btrfs_item_size_nr(leaf, path->slots[0]) > sizeof(*ei)) {
1234                         ei = btrfs_item_ptr(leaf, path->slots[0],
1235                                             struct btrfs_extent_item);
1236                         if (btrfs_extent_flags(leaf, ei) &
1237                             BTRFS_EXTENT_FLAG_TREE_BLOCK) {
1238                                 ret = add_extent(bytenr, num_bytes, metadump,
1239                                                  0);
1240                                 if (ret) {
1241                                         fprintf(stderr, "Error adding block "
1242                                                 "%d\n", ret);
1243                                         break;
1244                                 }
1245                         }
1246                 } else {
1247 #ifdef BTRFS_COMPAT_EXTENT_TREE_V0
1248                         ret = is_tree_block(extent_root, path, bytenr);
1249                         if (ret < 0) {
1250                                 fprintf(stderr, "Error checking tree block "
1251                                         "%d\n", ret);
1252                                 break;
1253                         }
1254
1255                         if (ret) {
1256                                 ret = add_extent(bytenr, num_bytes, metadump,
1257                                                  0);
1258                                 if (ret) {
1259                                         fprintf(stderr, "Error adding block "
1260                                                 "%d\n", ret);
1261                                         break;
1262                                 }
1263                         }
1264                         ret = 0;
1265 #else
1266                         fprintf(stderr, "Either extent tree corruption or "
1267                                 "you haven't built with V0 support\n");
1268                         ret = -EIO;
1269                         break;
1270 #endif
1271                 }
1272                 bytenr += num_bytes;
1273         }
1274
1275         btrfs_release_path(path);
1276
1277         return ret;
1278 }
1279
1280 static int create_metadump(const char *input, FILE *out, int num_threads,
1281                            int compress_level, int sanitize, int walk_trees)
1282 {
1283         struct btrfs_root *root;
1284         struct btrfs_path *path = NULL;
1285         struct metadump_struct metadump;
1286         int ret;
1287         int err = 0;
1288
1289         root = open_ctree(input, 0, 0);
1290         if (!root) {
1291                 fprintf(stderr, "Open ctree failed\n");
1292                 return -EIO;
1293         }
1294
1295         BUG_ON(root->nodesize != root->leafsize);
1296
1297         ret = metadump_init(&metadump, root, out, num_threads,
1298                             compress_level, sanitize);
1299         if (ret) {
1300                 fprintf(stderr, "Error initing metadump %d\n", ret);
1301                 close_ctree(root);
1302                 return ret;
1303         }
1304
1305         ret = add_extent(BTRFS_SUPER_INFO_OFFSET, BTRFS_SUPER_INFO_SIZE,
1306                         &metadump, 0);
1307         if (ret) {
1308                 fprintf(stderr, "Error adding metadata %d\n", ret);
1309                 err = ret;
1310                 goto out;
1311         }
1312
1313         path = btrfs_alloc_path();
1314         if (!path) {
1315                 fprintf(stderr, "Out of memory allocing path\n");
1316                 err = -ENOMEM;
1317                 goto out;
1318         }
1319
1320         if (walk_trees) {
1321                 ret = copy_tree_blocks(root, root->fs_info->chunk_root->node,
1322                                        &metadump, 1);
1323                 if (ret) {
1324                         err = ret;
1325                         goto out;
1326                 }
1327
1328                 ret = copy_tree_blocks(root, root->fs_info->tree_root->node,
1329                                        &metadump, 1);
1330                 if (ret) {
1331                         err = ret;
1332                         goto out;
1333                 }
1334         } else {
1335                 ret = copy_from_extent_tree(&metadump, path);
1336                 if (ret) {
1337                         err = ret;
1338                         goto out;
1339                 }
1340         }
1341
1342         ret = copy_log_trees(root, &metadump, path);
1343         if (ret) {
1344                 err = ret;
1345                 goto out;
1346         }
1347
1348         ret = copy_space_cache(root, &metadump, path);
1349 out:
1350         ret = flush_pending(&metadump, 1);
1351         if (ret) {
1352                 if (!err)
1353                         err = ret;
1354                 fprintf(stderr, "Error flushing pending %d\n", ret);
1355         }
1356
1357         metadump_destroy(&metadump, num_threads);
1358
1359         btrfs_free_path(path);
1360         ret = close_ctree(root);
1361         return err ? err : ret;
1362 }
1363
1364 static void update_super_old(u8 *buffer)
1365 {
1366         struct btrfs_super_block *super = (struct btrfs_super_block *)buffer;
1367         struct btrfs_chunk *chunk;
1368         struct btrfs_disk_key *key;
1369         u32 sectorsize = btrfs_super_sectorsize(super);
1370         u64 flags = btrfs_super_flags(super);
1371
1372         flags |= BTRFS_SUPER_FLAG_METADUMP;
1373         btrfs_set_super_flags(super, flags);
1374
1375         key = (struct btrfs_disk_key *)(super->sys_chunk_array);
1376         chunk = (struct btrfs_chunk *)(super->sys_chunk_array +
1377                                        sizeof(struct btrfs_disk_key));
1378
1379         btrfs_set_disk_key_objectid(key, BTRFS_FIRST_CHUNK_TREE_OBJECTID);
1380         btrfs_set_disk_key_type(key, BTRFS_CHUNK_ITEM_KEY);
1381         btrfs_set_disk_key_offset(key, 0);
1382
1383         btrfs_set_stack_chunk_length(chunk, (u64)-1);
1384         btrfs_set_stack_chunk_owner(chunk, BTRFS_EXTENT_TREE_OBJECTID);
1385         btrfs_set_stack_chunk_stripe_len(chunk, BTRFS_STRIPE_LEN);
1386         btrfs_set_stack_chunk_type(chunk, BTRFS_BLOCK_GROUP_SYSTEM);
1387         btrfs_set_stack_chunk_io_align(chunk, sectorsize);
1388         btrfs_set_stack_chunk_io_width(chunk, sectorsize);
1389         btrfs_set_stack_chunk_sector_size(chunk, sectorsize);
1390         btrfs_set_stack_chunk_num_stripes(chunk, 1);
1391         btrfs_set_stack_chunk_sub_stripes(chunk, 0);
1392         chunk->stripe.devid = super->dev_item.devid;
1393         btrfs_set_stack_stripe_offset(&chunk->stripe, 0);
1394         memcpy(chunk->stripe.dev_uuid, super->dev_item.uuid, BTRFS_UUID_SIZE);
1395         btrfs_set_super_sys_array_size(super, sizeof(*key) + sizeof(*chunk));
1396         csum_block(buffer, BTRFS_SUPER_INFO_SIZE);
1397 }
1398
1399 static int update_super(u8 *buffer)
1400 {
1401         struct btrfs_super_block *super = (struct btrfs_super_block *)buffer;
1402         struct btrfs_chunk *chunk;
1403         struct btrfs_disk_key *disk_key;
1404         struct btrfs_key key;
1405         u32 new_array_size = 0;
1406         u32 array_size;
1407         u32 cur = 0;
1408         u8 *ptr, *write_ptr;
1409         int old_num_stripes;
1410
1411         write_ptr = ptr = super->sys_chunk_array;
1412         array_size = btrfs_super_sys_array_size(super);
1413
1414         while (cur < array_size) {
1415                 disk_key = (struct btrfs_disk_key *)ptr;
1416                 btrfs_disk_key_to_cpu(&key, disk_key);
1417
1418                 new_array_size += sizeof(*disk_key);
1419                 memmove(write_ptr, ptr, sizeof(*disk_key));
1420
1421                 write_ptr += sizeof(*disk_key);
1422                 ptr += sizeof(*disk_key);
1423                 cur += sizeof(*disk_key);
1424
1425                 if (key.type == BTRFS_CHUNK_ITEM_KEY) {
1426                         chunk = (struct btrfs_chunk *)ptr;
1427                         old_num_stripes = btrfs_stack_chunk_num_stripes(chunk);
1428                         chunk = (struct btrfs_chunk *)write_ptr;
1429
1430                         memmove(write_ptr, ptr, sizeof(*chunk));
1431                         btrfs_set_stack_chunk_num_stripes(chunk, 1);
1432                         btrfs_set_stack_chunk_sub_stripes(chunk, 0);
1433                         btrfs_set_stack_chunk_type(chunk,
1434                                                    BTRFS_BLOCK_GROUP_SYSTEM);
1435                         chunk->stripe.devid = super->dev_item.devid;
1436                         memcpy(chunk->stripe.dev_uuid, super->dev_item.uuid,
1437                                BTRFS_UUID_SIZE);
1438                         new_array_size += sizeof(*chunk);
1439                 } else {
1440                         fprintf(stderr, "Bogus key in the sys chunk array "
1441                                 "%d\n", key.type);
1442                         return -EIO;
1443                 }
1444                 write_ptr += sizeof(*chunk);
1445                 ptr += btrfs_chunk_item_size(old_num_stripes);
1446                 cur += btrfs_chunk_item_size(old_num_stripes);
1447         }
1448
1449         btrfs_set_super_sys_array_size(super, new_array_size);
1450         csum_block(buffer, BTRFS_SUPER_INFO_SIZE);
1451
1452         return 0;
1453 }
1454
1455 static struct extent_buffer *alloc_dummy_eb(u64 bytenr, u32 size)
1456 {
1457         struct extent_buffer *eb;
1458
1459         eb = malloc(sizeof(struct extent_buffer) + size);
1460         if (!eb)
1461                 return NULL;
1462         memset(eb, 0, sizeof(struct extent_buffer) + size);
1463
1464         eb->start = bytenr;
1465         eb->len = size;
1466         return eb;
1467 }
1468
1469 static void truncate_item(struct extent_buffer *eb, int slot, u32 new_size)
1470 {
1471         struct btrfs_item *item;
1472         u32 nritems;
1473         u32 old_size;
1474         u32 old_data_start;
1475         u32 size_diff;
1476         u32 data_end;
1477         int i;
1478
1479         old_size = btrfs_item_size_nr(eb, slot);
1480         if (old_size == new_size)
1481                 return;
1482
1483         nritems = btrfs_header_nritems(eb);
1484         data_end = btrfs_item_offset_nr(eb, nritems - 1);
1485
1486         old_data_start = btrfs_item_offset_nr(eb, slot);
1487         size_diff = old_size - new_size;
1488
1489         for (i = slot; i < nritems; i++) {
1490                 u32 ioff;
1491                 item = btrfs_item_nr(i);
1492                 ioff = btrfs_item_offset(eb, item);
1493                 btrfs_set_item_offset(eb, item, ioff + size_diff);
1494         }
1495
1496         memmove_extent_buffer(eb, btrfs_leaf_data(eb) + data_end + size_diff,
1497                               btrfs_leaf_data(eb) + data_end,
1498                               old_data_start + new_size - data_end);
1499         item = btrfs_item_nr(slot);
1500         btrfs_set_item_size(eb, item, new_size);
1501 }
1502
1503 static int fixup_chunk_tree_block(struct mdrestore_struct *mdres,
1504                                   struct async_work *async, u8 *buffer,
1505                                   size_t size)
1506 {
1507         struct extent_buffer *eb;
1508         size_t size_left = size;
1509         u64 bytenr = async->start;
1510         int i;
1511
1512         if (size_left % mdres->leafsize)
1513                 return 0;
1514
1515         eb = alloc_dummy_eb(bytenr, mdres->leafsize);
1516         if (!eb)
1517                 return -ENOMEM;
1518
1519         while (size_left) {
1520                 eb->start = bytenr;
1521                 memcpy(eb->data, buffer, mdres->leafsize);
1522
1523                 if (btrfs_header_bytenr(eb) != bytenr)
1524                         break;
1525                 if (memcmp(mdres->fsid,
1526                            eb->data + offsetof(struct btrfs_header, fsid),
1527                            BTRFS_FSID_SIZE))
1528                         break;
1529
1530                 if (btrfs_header_owner(eb) != BTRFS_CHUNK_TREE_OBJECTID)
1531                         goto next;
1532
1533                 if (btrfs_header_level(eb) != 0)
1534                         goto next;
1535
1536                 for (i = 0; i < btrfs_header_nritems(eb); i++) {
1537                         struct btrfs_chunk chunk;
1538                         struct btrfs_key key;
1539                         u64 type;
1540
1541                         btrfs_item_key_to_cpu(eb, &key, i);
1542                         if (key.type != BTRFS_CHUNK_ITEM_KEY)
1543                                 continue;
1544                         truncate_item(eb, i, sizeof(chunk));
1545                         read_extent_buffer(eb, &chunk,
1546                                            btrfs_item_ptr_offset(eb, i),
1547                                            sizeof(chunk));
1548
1549                         /* Zero out the RAID profile */
1550                         type = btrfs_stack_chunk_type(&chunk);
1551                         type &= (BTRFS_BLOCK_GROUP_DATA |
1552                                  BTRFS_BLOCK_GROUP_SYSTEM |
1553                                  BTRFS_BLOCK_GROUP_METADATA |
1554                                  BTRFS_BLOCK_GROUP_DUP);
1555                         btrfs_set_stack_chunk_type(&chunk, type);
1556
1557                         btrfs_set_stack_chunk_num_stripes(&chunk, 1);
1558                         btrfs_set_stack_chunk_sub_stripes(&chunk, 0);
1559                         btrfs_set_stack_stripe_devid(&chunk.stripe, mdres->devid);
1560                         memcpy(chunk.stripe.dev_uuid, mdres->uuid,
1561                                BTRFS_UUID_SIZE);
1562                         write_extent_buffer(eb, &chunk,
1563                                             btrfs_item_ptr_offset(eb, i),
1564                                             sizeof(chunk));
1565                 }
1566                 memcpy(buffer, eb->data, eb->len);
1567                 csum_block(buffer, eb->len);
1568 next:
1569                 size_left -= mdres->leafsize;
1570                 buffer += mdres->leafsize;
1571                 bytenr += mdres->leafsize;
1572         }
1573
1574         free(eb);
1575         return 0;
1576 }
1577
1578 static void write_backup_supers(int fd, u8 *buf)
1579 {
1580         struct btrfs_super_block *super = (struct btrfs_super_block *)buf;
1581         struct stat st;
1582         u64 size;
1583         u64 bytenr;
1584         int i;
1585         int ret;
1586
1587         if (fstat(fd, &st)) {
1588                 fprintf(stderr, "Couldn't stat restore point, won't be able "
1589                         "to write backup supers: %d\n", errno);
1590                 return;
1591         }
1592
1593         size = btrfs_device_size(fd, &st);
1594
1595         for (i = 1; i < BTRFS_SUPER_MIRROR_MAX; i++) {
1596                 bytenr = btrfs_sb_offset(i);
1597                 if (bytenr + BTRFS_SUPER_INFO_SIZE > size)
1598                         break;
1599                 btrfs_set_super_bytenr(super, bytenr);
1600                 csum_block(buf, BTRFS_SUPER_INFO_SIZE);
1601                 ret = pwrite64(fd, buf, BTRFS_SUPER_INFO_SIZE, bytenr);
1602                 if (ret < BTRFS_SUPER_INFO_SIZE) {
1603                         if (ret < 0)
1604                                 fprintf(stderr, "Problem writing out backup "
1605                                         "super block %d, err %d\n", i, errno);
1606                         else
1607                                 fprintf(stderr, "Short write writing out "
1608                                         "backup super block\n");
1609                         break;
1610                 }
1611         }
1612 }
1613
1614 static u64 logical_to_physical(struct mdrestore_struct *mdres, u64 logical, u64 *size)
1615 {
1616         struct fs_chunk *fs_chunk;
1617         struct rb_node *entry;
1618         struct fs_chunk search;
1619         u64 offset;
1620
1621         if (logical == BTRFS_SUPER_INFO_OFFSET)
1622                 return logical;
1623
1624         search.logical = logical;
1625         entry = tree_search(&mdres->chunk_tree, &search.n, chunk_cmp, 1);
1626         if (!entry) {
1627                 if (mdres->in != stdin)
1628                         printf("Couldn't find a chunk, using logical\n");
1629                 return logical;
1630         }
1631         fs_chunk = rb_entry(entry, struct fs_chunk, n);
1632         if (fs_chunk->logical > logical || fs_chunk->logical + fs_chunk->bytes < logical)
1633                 BUG();
1634         offset = search.logical - fs_chunk->logical;
1635
1636         *size = min(*size, fs_chunk->bytes + fs_chunk->logical - logical);
1637         return fs_chunk->physical + offset;
1638 }
1639
1640 static void *restore_worker(void *data)
1641 {
1642         struct mdrestore_struct *mdres = (struct mdrestore_struct *)data;
1643         struct async_work *async;
1644         size_t size;
1645         u8 *buffer;
1646         u8 *outbuf;
1647         int outfd;
1648         int ret;
1649         int compress_size = MAX_PENDING_SIZE * 4;
1650
1651         outfd = fileno(mdres->out);
1652         buffer = malloc(compress_size);
1653         if (!buffer) {
1654                 fprintf(stderr, "Error allocing buffer\n");
1655                 pthread_mutex_lock(&mdres->mutex);
1656                 if (!mdres->error)
1657                         mdres->error = -ENOMEM;
1658                 pthread_mutex_unlock(&mdres->mutex);
1659                 pthread_exit(NULL);
1660         }
1661
1662         while (1) {
1663                 u64 bytenr;
1664                 off_t offset = 0;
1665                 int err = 0;
1666
1667                 pthread_mutex_lock(&mdres->mutex);
1668                 while (!mdres->leafsize || list_empty(&mdres->list)) {
1669                         if (mdres->done) {
1670                                 pthread_mutex_unlock(&mdres->mutex);
1671                                 goto out;
1672                         }
1673                         pthread_cond_wait(&mdres->cond, &mdres->mutex);
1674                 }
1675                 async = list_entry(mdres->list.next, struct async_work, list);
1676                 list_del_init(&async->list);
1677                 pthread_mutex_unlock(&mdres->mutex);
1678
1679                 if (mdres->compress_method == COMPRESS_ZLIB) {
1680                         size = compress_size;
1681                         ret = uncompress(buffer, (unsigned long *)&size,
1682                                          async->buffer, async->bufsize);
1683                         if (ret != Z_OK) {
1684                                 fprintf(stderr, "Error decompressing %d\n",
1685                                         ret);
1686                                 err = -EIO;
1687                         }
1688                         outbuf = buffer;
1689                 } else {
1690                         outbuf = async->buffer;
1691                         size = async->bufsize;
1692                 }
1693
1694                 if (!mdres->multi_devices) {
1695                         if (async->start == BTRFS_SUPER_INFO_OFFSET) {
1696                                 if (mdres->old_restore) {
1697                                         update_super_old(outbuf);
1698                                 } else {
1699                                         ret = update_super(outbuf);
1700                                         if (ret)
1701                                                 err = ret;
1702                                 }
1703                         } else if (!mdres->old_restore) {
1704                                 ret = fixup_chunk_tree_block(mdres, async, outbuf, size);
1705                                 if (ret)
1706                                         err = ret;
1707                         }
1708                 }
1709
1710                 if (!mdres->fixup_offset) {
1711                         while (size) {
1712                                 u64 chunk_size = size;
1713                                 if (!mdres->multi_devices && !mdres->old_restore)
1714                                         bytenr = logical_to_physical(mdres,
1715                                                                      async->start + offset,
1716                                                                      &chunk_size);
1717                                 else
1718                                         bytenr = async->start + offset;
1719
1720                                 ret = pwrite64(outfd, outbuf+offset, chunk_size,
1721                                                bytenr);
1722                                 if (ret != chunk_size) {
1723                                         if (ret < 0) {
1724                                                 fprintf(stderr, "Error writing to "
1725                                                         "device %d\n", errno);
1726                                                 err = errno;
1727                                                 break;
1728                                         } else {
1729                                                 fprintf(stderr, "Short write\n");
1730                                                 err = -EIO;
1731                                                 break;
1732                                         }
1733                                 }
1734                                 size -= chunk_size;
1735                                 offset += chunk_size;
1736                         }
1737                 } else if (async->start != BTRFS_SUPER_INFO_OFFSET) {
1738                         ret = write_data_to_disk(mdres->info, outbuf, async->start, size, 0);
1739                         if (ret) {
1740                                 printk("Error write data\n");
1741                                 exit(1);
1742                         }
1743                 }
1744
1745
1746                 /* backup super blocks are already there at fixup_offset stage */
1747                 if (!mdres->multi_devices && async->start == BTRFS_SUPER_INFO_OFFSET)
1748                         write_backup_supers(outfd, outbuf);
1749
1750                 pthread_mutex_lock(&mdres->mutex);
1751                 if (err && !mdres->error)
1752                         mdres->error = err;
1753                 mdres->num_items--;
1754                 pthread_mutex_unlock(&mdres->mutex);
1755
1756                 free(async->buffer);
1757                 free(async);
1758         }
1759 out:
1760         free(buffer);
1761         pthread_exit(NULL);
1762 }
1763
1764 static void mdrestore_destroy(struct mdrestore_struct *mdres, int num_threads)
1765 {
1766         struct rb_node *n;
1767         int i;
1768
1769         while ((n = rb_first(&mdres->chunk_tree))) {
1770                 struct fs_chunk *entry;
1771
1772                 entry = rb_entry(n, struct fs_chunk, n);
1773                 rb_erase(n, &mdres->chunk_tree);
1774                 free(entry);
1775         }
1776         pthread_mutex_lock(&mdres->mutex);
1777         mdres->done = 1;
1778         pthread_cond_broadcast(&mdres->cond);
1779         pthread_mutex_unlock(&mdres->mutex);
1780
1781         for (i = 0; i < num_threads; i++)
1782                 pthread_join(mdres->threads[i], NULL);
1783
1784         pthread_cond_destroy(&mdres->cond);
1785         pthread_mutex_destroy(&mdres->mutex);
1786         free(mdres->threads);
1787 }
1788
1789 static int mdrestore_init(struct mdrestore_struct *mdres,
1790                           FILE *in, FILE *out, int old_restore,
1791                           int num_threads, int fixup_offset,
1792                           struct btrfs_fs_info *info, int multi_devices)
1793 {
1794         int i, ret = 0;
1795
1796         memset(mdres, 0, sizeof(*mdres));
1797         pthread_cond_init(&mdres->cond, NULL);
1798         pthread_mutex_init(&mdres->mutex, NULL);
1799         INIT_LIST_HEAD(&mdres->list);
1800         mdres->in = in;
1801         mdres->out = out;
1802         mdres->old_restore = old_restore;
1803         mdres->chunk_tree.rb_node = NULL;
1804         mdres->fixup_offset = fixup_offset;
1805         mdres->info = info;
1806         mdres->multi_devices = multi_devices;
1807
1808         if (!num_threads)
1809                 return 0;
1810
1811         mdres->num_threads = num_threads;
1812         mdres->threads = calloc(num_threads, sizeof(pthread_t));
1813         if (!mdres->threads)
1814                 return -ENOMEM;
1815         for (i = 0; i < num_threads; i++) {
1816                 ret = pthread_create(mdres->threads + i, NULL, restore_worker,
1817                                      mdres);
1818                 if (ret)
1819                         break;
1820         }
1821         if (ret)
1822                 mdrestore_destroy(mdres, i + 1);
1823         return ret;
1824 }
1825
1826 static int fill_mdres_info(struct mdrestore_struct *mdres,
1827                            struct async_work *async)
1828 {
1829         struct btrfs_super_block *super;
1830         u8 *buffer = NULL;
1831         u8 *outbuf;
1832         int ret;
1833
1834         /* We've already been initialized */
1835         if (mdres->leafsize)
1836                 return 0;
1837
1838         if (mdres->compress_method == COMPRESS_ZLIB) {
1839                 size_t size = MAX_PENDING_SIZE * 2;
1840
1841                 buffer = malloc(MAX_PENDING_SIZE * 2);
1842                 if (!buffer)
1843                         return -ENOMEM;
1844                 ret = uncompress(buffer, (unsigned long *)&size,
1845                                  async->buffer, async->bufsize);
1846                 if (ret != Z_OK) {
1847                         fprintf(stderr, "Error decompressing %d\n", ret);
1848                         free(buffer);
1849                         return -EIO;
1850                 }
1851                 outbuf = buffer;
1852         } else {
1853                 outbuf = async->buffer;
1854         }
1855
1856         super = (struct btrfs_super_block *)outbuf;
1857         mdres->leafsize = btrfs_super_leafsize(super);
1858         memcpy(mdres->fsid, super->fsid, BTRFS_FSID_SIZE);
1859         memcpy(mdres->uuid, super->dev_item.uuid,
1860                        BTRFS_UUID_SIZE);
1861         mdres->devid = le64_to_cpu(super->dev_item.devid);
1862         free(buffer);
1863         return 0;
1864 }
1865
1866 static int add_cluster(struct meta_cluster *cluster,
1867                        struct mdrestore_struct *mdres, u64 *next)
1868 {
1869         struct meta_cluster_item *item;
1870         struct meta_cluster_header *header = &cluster->header;
1871         struct async_work *async;
1872         u64 bytenr;
1873         u32 i, nritems;
1874         int ret;
1875
1876         BUG_ON(mdres->num_items);
1877         mdres->compress_method = header->compress;
1878
1879         bytenr = le64_to_cpu(header->bytenr) + BLOCK_SIZE;
1880         nritems = le32_to_cpu(header->nritems);
1881         for (i = 0; i < nritems; i++) {
1882                 item = &cluster->items[i];
1883                 async = calloc(1, sizeof(*async));
1884                 if (!async) {
1885                         fprintf(stderr, "Error allocating async\n");
1886                         return -ENOMEM;
1887                 }
1888                 async->start = le64_to_cpu(item->bytenr);
1889                 async->bufsize = le32_to_cpu(item->size);
1890                 async->buffer = malloc(async->bufsize);
1891                 if (!async->buffer) {
1892                         fprintf(stderr, "Error allocing async buffer\n");
1893                         free(async);
1894                         return -ENOMEM;
1895                 }
1896                 ret = fread(async->buffer, async->bufsize, 1, mdres->in);
1897                 if (ret != 1) {
1898                         fprintf(stderr, "Error reading buffer %d\n", errno);
1899                         free(async->buffer);
1900                         free(async);
1901                         return -EIO;
1902                 }
1903                 bytenr += async->bufsize;
1904
1905                 pthread_mutex_lock(&mdres->mutex);
1906                 if (async->start == BTRFS_SUPER_INFO_OFFSET) {
1907                         ret = fill_mdres_info(mdres, async);
1908                         if (ret) {
1909                                 fprintf(stderr, "Error setting up restore\n");
1910                                 pthread_mutex_unlock(&mdres->mutex);
1911                                 free(async->buffer);
1912                                 free(async);
1913                                 return ret;
1914                         }
1915                 }
1916                 list_add_tail(&async->list, &mdres->list);
1917                 mdres->num_items++;
1918                 pthread_cond_signal(&mdres->cond);
1919                 pthread_mutex_unlock(&mdres->mutex);
1920         }
1921         if (bytenr & BLOCK_MASK) {
1922                 char buffer[BLOCK_MASK];
1923                 size_t size = BLOCK_SIZE - (bytenr & BLOCK_MASK);
1924
1925                 bytenr += size;
1926                 ret = fread(buffer, size, 1, mdres->in);
1927                 if (ret != 1) {
1928                         fprintf(stderr, "Error reading in buffer %d\n", errno);
1929                         return -EIO;
1930                 }
1931         }
1932         *next = bytenr;
1933         return 0;
1934 }
1935
1936 static int wait_for_worker(struct mdrestore_struct *mdres)
1937 {
1938         int ret = 0;
1939
1940         pthread_mutex_lock(&mdres->mutex);
1941         ret = mdres->error;
1942         while (!ret && mdres->num_items > 0) {
1943                 struct timespec ts = {
1944                         .tv_sec = 0,
1945                         .tv_nsec = 10000000,
1946                 };
1947                 pthread_mutex_unlock(&mdres->mutex);
1948                 nanosleep(&ts, NULL);
1949                 pthread_mutex_lock(&mdres->mutex);
1950                 ret = mdres->error;
1951         }
1952         pthread_mutex_unlock(&mdres->mutex);
1953         return ret;
1954 }
1955
1956 static int read_chunk_block(struct mdrestore_struct *mdres, u8 *buffer,
1957                             u64 bytenr, u64 item_bytenr, u32 bufsize,
1958                             u64 cluster_bytenr)
1959 {
1960         struct extent_buffer *eb;
1961         int ret = 0;
1962         int i;
1963
1964         eb = alloc_dummy_eb(bytenr, mdres->leafsize);
1965         if (!eb) {
1966                 ret = -ENOMEM;
1967                 goto out;
1968         }
1969
1970         while (item_bytenr != bytenr) {
1971                 buffer += mdres->leafsize;
1972                 item_bytenr += mdres->leafsize;
1973         }
1974
1975         memcpy(eb->data, buffer, mdres->leafsize);
1976         if (btrfs_header_bytenr(eb) != bytenr) {
1977                 fprintf(stderr, "Eb bytenr doesn't match found bytenr\n");
1978                 ret = -EIO;
1979                 goto out;
1980         }
1981
1982         if (memcmp(mdres->fsid, eb->data + offsetof(struct btrfs_header, fsid),
1983                    BTRFS_FSID_SIZE)) {
1984                 fprintf(stderr, "Fsid doesn't match\n");
1985                 ret = -EIO;
1986                 goto out;
1987         }
1988
1989         if (btrfs_header_owner(eb) != BTRFS_CHUNK_TREE_OBJECTID) {
1990                 fprintf(stderr, "Does not belong to the chunk tree\n");
1991                 ret = -EIO;
1992                 goto out;
1993         }
1994
1995         for (i = 0; i < btrfs_header_nritems(eb); i++) {
1996                 struct btrfs_chunk chunk;
1997                 struct fs_chunk *fs_chunk;
1998                 struct btrfs_key key;
1999
2000                 if (btrfs_header_level(eb)) {
2001                         u64 blockptr = btrfs_node_blockptr(eb, i);
2002
2003                         ret = search_for_chunk_blocks(mdres, blockptr,
2004                                                       cluster_bytenr);
2005                         if (ret)
2006                                 break;
2007                         continue;
2008                 }
2009
2010                 /* Yay a leaf!  We loves leafs! */
2011                 btrfs_item_key_to_cpu(eb, &key, i);
2012                 if (key.type != BTRFS_CHUNK_ITEM_KEY)
2013                         continue;
2014
2015                 fs_chunk = malloc(sizeof(struct fs_chunk));
2016                 if (!fs_chunk) {
2017                         fprintf(stderr, "Erorr allocating chunk\n");
2018                         ret = -ENOMEM;
2019                         break;
2020                 }
2021                 memset(fs_chunk, 0, sizeof(*fs_chunk));
2022                 read_extent_buffer(eb, &chunk, btrfs_item_ptr_offset(eb, i),
2023                                    sizeof(chunk));
2024
2025                 fs_chunk->logical = key.offset;
2026                 fs_chunk->physical = btrfs_stack_stripe_offset(&chunk.stripe);
2027                 fs_chunk->bytes = btrfs_stack_chunk_length(&chunk);
2028                 tree_insert(&mdres->chunk_tree, &fs_chunk->n, chunk_cmp);
2029         }
2030 out:
2031         free(eb);
2032         return ret;
2033 }
2034
2035 /* If you have to ask you aren't worthy */
2036 static int search_for_chunk_blocks(struct mdrestore_struct *mdres,
2037                                    u64 search, u64 cluster_bytenr)
2038 {
2039         struct meta_cluster *cluster;
2040         struct meta_cluster_header *header;
2041         struct meta_cluster_item *item;
2042         u64 current_cluster = cluster_bytenr, bytenr;
2043         u64 item_bytenr;
2044         u32 bufsize, nritems, i;
2045         u32 max_size = MAX_PENDING_SIZE * 2;
2046         u8 *buffer, *tmp = NULL;
2047         int ret = 0;
2048
2049         cluster = malloc(BLOCK_SIZE);
2050         if (!cluster) {
2051                 fprintf(stderr, "Error allocating cluster\n");
2052                 return -ENOMEM;
2053         }
2054
2055         buffer = malloc(max_size);
2056         if (!buffer) {
2057                 fprintf(stderr, "Error allocing buffer\n");
2058                 free(cluster);
2059                 return -ENOMEM;
2060         }
2061
2062         if (mdres->compress_method == COMPRESS_ZLIB) {
2063                 tmp = malloc(max_size);
2064                 if (!tmp) {
2065                         fprintf(stderr, "Error allocing tmp buffer\n");
2066                         free(cluster);
2067                         free(buffer);
2068                         return -ENOMEM;
2069                 }
2070         }
2071
2072         bytenr = current_cluster;
2073         while (1) {
2074                 if (fseek(mdres->in, current_cluster, SEEK_SET)) {
2075                         fprintf(stderr, "Error seeking: %d\n", errno);
2076                         ret = -EIO;
2077                         break;
2078                 }
2079
2080                 ret = fread(cluster, BLOCK_SIZE, 1, mdres->in);
2081                 if (ret == 0) {
2082                         if (cluster_bytenr != 0) {
2083                                 cluster_bytenr = 0;
2084                                 current_cluster = 0;
2085                                 bytenr = 0;
2086                                 continue;
2087                         }
2088                         printf("ok this is where we screwed up?\n");
2089                         ret = -EIO;
2090                         break;
2091                 } else if (ret < 0) {
2092                         fprintf(stderr, "Error reading image\n");
2093                         break;
2094                 }
2095                 ret = 0;
2096
2097                 header = &cluster->header;
2098                 if (le64_to_cpu(header->magic) != HEADER_MAGIC ||
2099                     le64_to_cpu(header->bytenr) != current_cluster) {
2100                         fprintf(stderr, "bad header in metadump image\n");
2101                         ret = -EIO;
2102                         break;
2103                 }
2104
2105                 bytenr += BLOCK_SIZE;
2106                 nritems = le32_to_cpu(header->nritems);
2107                 for (i = 0; i < nritems; i++) {
2108                         size_t size;
2109
2110                         item = &cluster->items[i];
2111                         bufsize = le32_to_cpu(item->size);
2112                         item_bytenr = le64_to_cpu(item->bytenr);
2113
2114                         if (bufsize > max_size) {
2115                                 fprintf(stderr, "item %u size %u too big\n",
2116                                         i, bufsize);
2117                                 ret = -EIO;
2118                                 break;
2119                         }
2120
2121                         if (mdres->compress_method == COMPRESS_ZLIB) {
2122                                 ret = fread(tmp, bufsize, 1, mdres->in);
2123                                 if (ret != 1) {
2124                                         fprintf(stderr, "Error reading: %d\n",
2125                                                 errno);
2126                                         ret = -EIO;
2127                                         break;
2128                                 }
2129
2130                                 size = max_size;
2131                                 ret = uncompress(buffer,
2132                                                  (unsigned long *)&size, tmp,
2133                                                  bufsize);
2134                                 if (ret != Z_OK) {
2135                                         fprintf(stderr, "Error decompressing "
2136                                                 "%d\n", ret);
2137                                         ret = -EIO;
2138                                         break;
2139                                 }
2140                         } else {
2141                                 ret = fread(buffer, bufsize, 1, mdres->in);
2142                                 if (ret != 1) {
2143                                         fprintf(stderr, "Error reading: %d\n",
2144                                                 errno);
2145                                         ret = -EIO;
2146                                         break;
2147                                 }
2148                                 size = bufsize;
2149                         }
2150                         ret = 0;
2151
2152                         if (item_bytenr <= search &&
2153                             item_bytenr + size > search) {
2154                                 ret = read_chunk_block(mdres, buffer, search,
2155                                                        item_bytenr, size,
2156                                                        current_cluster);
2157                                 if (!ret)
2158                                         ret = 1;
2159                                 break;
2160                         }
2161                         bytenr += bufsize;
2162                 }
2163                 if (ret) {
2164                         if (ret > 0)
2165                                 ret = 0;
2166                         break;
2167                 }
2168                 if (bytenr & BLOCK_MASK)
2169                         bytenr += BLOCK_SIZE - (bytenr & BLOCK_MASK);
2170                 current_cluster = bytenr;
2171         }
2172
2173         free(tmp);
2174         free(buffer);
2175         free(cluster);
2176         return ret;
2177 }
2178
2179 static int build_chunk_tree(struct mdrestore_struct *mdres,
2180                             struct meta_cluster *cluster)
2181 {
2182         struct btrfs_super_block *super;
2183         struct meta_cluster_header *header;
2184         struct meta_cluster_item *item = NULL;
2185         u64 chunk_root_bytenr = 0;
2186         u32 i, nritems;
2187         u64 bytenr = 0;
2188         u8 *buffer;
2189         int ret;
2190
2191         /* We can't seek with stdin so don't bother doing this */
2192         if (mdres->in == stdin)
2193                 return 0;
2194
2195         ret = fread(cluster, BLOCK_SIZE, 1, mdres->in);
2196         if (ret <= 0) {
2197                 fprintf(stderr, "Error reading in cluster: %d\n", errno);
2198                 return -EIO;
2199         }
2200         ret = 0;
2201
2202         header = &cluster->header;
2203         if (le64_to_cpu(header->magic) != HEADER_MAGIC ||
2204             le64_to_cpu(header->bytenr) != 0) {
2205                 fprintf(stderr, "bad header in metadump image\n");
2206                 return -EIO;
2207         }
2208
2209         bytenr += BLOCK_SIZE;
2210         mdres->compress_method = header->compress;
2211         nritems = le32_to_cpu(header->nritems);
2212         for (i = 0; i < nritems; i++) {
2213                 item = &cluster->items[i];
2214
2215                 if (le64_to_cpu(item->bytenr) == BTRFS_SUPER_INFO_OFFSET)
2216                         break;
2217                 bytenr += le32_to_cpu(item->size);
2218                 if (fseek(mdres->in, le32_to_cpu(item->size), SEEK_CUR)) {
2219                         fprintf(stderr, "Error seeking: %d\n", errno);
2220                         return -EIO;
2221                 }
2222         }
2223
2224         if (!item || le64_to_cpu(item->bytenr) != BTRFS_SUPER_INFO_OFFSET) {
2225                 fprintf(stderr, "Huh, didn't find the super?\n");
2226                 return -EINVAL;
2227         }
2228
2229         buffer = malloc(le32_to_cpu(item->size));
2230         if (!buffer) {
2231                 fprintf(stderr, "Error allocing buffer\n");
2232                 return -ENOMEM;
2233         }
2234
2235         ret = fread(buffer, le32_to_cpu(item->size), 1, mdres->in);
2236         if (ret != 1) {
2237                 fprintf(stderr, "Error reading buffer: %d\n", errno);
2238                 free(buffer);
2239                 return -EIO;
2240         }
2241
2242         if (mdres->compress_method == COMPRESS_ZLIB) {
2243                 size_t size = MAX_PENDING_SIZE * 2;
2244                 u8 *tmp;
2245
2246                 tmp = malloc(MAX_PENDING_SIZE * 2);
2247                 if (!tmp) {
2248                         free(buffer);
2249                         return -ENOMEM;
2250                 }
2251                 ret = uncompress(tmp, (unsigned long *)&size,
2252                                  buffer, le32_to_cpu(item->size));
2253                 if (ret != Z_OK) {
2254                         fprintf(stderr, "Error decompressing %d\n", ret);
2255                         free(buffer);
2256                         free(tmp);
2257                         return -EIO;
2258                 }
2259                 free(buffer);
2260                 buffer = tmp;
2261         }
2262
2263         pthread_mutex_lock(&mdres->mutex);
2264         super = (struct btrfs_super_block *)buffer;
2265         chunk_root_bytenr = btrfs_super_chunk_root(super);
2266         mdres->leafsize = btrfs_super_leafsize(super);
2267         memcpy(mdres->fsid, super->fsid, BTRFS_FSID_SIZE);
2268         memcpy(mdres->uuid, super->dev_item.uuid,
2269                        BTRFS_UUID_SIZE);
2270         mdres->devid = le64_to_cpu(super->dev_item.devid);
2271         free(buffer);
2272         pthread_mutex_unlock(&mdres->mutex);
2273
2274         return search_for_chunk_blocks(mdres, chunk_root_bytenr, 0);
2275 }
2276
2277 static int __restore_metadump(const char *input, FILE *out, int old_restore,
2278                               int num_threads, int fixup_offset,
2279                               const char *target, int multi_devices)
2280 {
2281         struct meta_cluster *cluster = NULL;
2282         struct meta_cluster_header *header;
2283         struct mdrestore_struct mdrestore;
2284         struct btrfs_fs_info *info = NULL;
2285         u64 bytenr = 0;
2286         FILE *in = NULL;
2287         int ret = 0;
2288
2289         if (!strcmp(input, "-")) {
2290                 in = stdin;
2291         } else {
2292                 in = fopen(input, "r");
2293                 if (!in) {
2294                         perror("unable to open metadump image");
2295                         return 1;
2296                 }
2297         }
2298
2299         /* NOTE: open with write mode */
2300         if (fixup_offset) {
2301                 BUG_ON(!target);
2302                 info = open_ctree_fs_info(target, 0, 0,
2303                                           OPEN_CTREE_WRITES |
2304                                           OPEN_CTREE_RESTORE |
2305                                           OPEN_CTREE_PARTIAL);
2306                 if (!info) {
2307                         fprintf(stderr, "%s: open ctree failed\n", __func__);
2308                         ret = -EIO;
2309                         goto failed_open;
2310                 }
2311         }
2312
2313         cluster = malloc(BLOCK_SIZE);
2314         if (!cluster) {
2315                 fprintf(stderr, "Error allocating cluster\n");
2316                 ret = -ENOMEM;
2317                 goto failed_info;
2318         }
2319
2320         ret = mdrestore_init(&mdrestore, in, out, old_restore, num_threads,
2321                              fixup_offset, info, multi_devices);
2322         if (ret) {
2323                 fprintf(stderr, "Error initing mdrestore %d\n", ret);
2324                 goto failed_cluster;
2325         }
2326
2327         if (!multi_devices && !old_restore) {
2328                 ret = build_chunk_tree(&mdrestore, cluster);
2329                 if (ret)
2330                         goto out;
2331         }
2332
2333         if (in != stdin && fseek(in, 0, SEEK_SET)) {
2334                 fprintf(stderr, "Error seeking %d\n", errno);
2335                 goto out;
2336         }
2337
2338         while (1) {
2339                 ret = fread(cluster, BLOCK_SIZE, 1, in);
2340                 if (!ret)
2341                         break;
2342
2343                 header = &cluster->header;
2344                 if (le64_to_cpu(header->magic) != HEADER_MAGIC ||
2345                     le64_to_cpu(header->bytenr) != bytenr) {
2346                         fprintf(stderr, "bad header in metadump image\n");
2347                         ret = -EIO;
2348                         break;
2349                 }
2350                 ret = add_cluster(cluster, &mdrestore, &bytenr);
2351                 if (ret) {
2352                         fprintf(stderr, "Error adding cluster\n");
2353                         break;
2354                 }
2355
2356                 ret = wait_for_worker(&mdrestore);
2357                 if (ret) {
2358                         fprintf(stderr, "One of the threads errored out %d\n",
2359                                 ret);
2360                         break;
2361                 }
2362         }
2363 out:
2364         mdrestore_destroy(&mdrestore, num_threads);
2365 failed_cluster:
2366         free(cluster);
2367 failed_info:
2368         if (fixup_offset && info)
2369                 close_ctree(info->chunk_root);
2370 failed_open:
2371         if (in != stdin)
2372                 fclose(in);
2373         return ret;
2374 }
2375
2376 static int restore_metadump(const char *input, FILE *out, int old_restore,
2377                             int num_threads, int multi_devices)
2378 {
2379         return __restore_metadump(input, out, old_restore, num_threads, 0, NULL,
2380                                   multi_devices);
2381 }
2382
2383 static int fixup_metadump(const char *input, FILE *out, int num_threads,
2384                           const char *target)
2385 {
2386         return __restore_metadump(input, out, 0, num_threads, 1, target, 1);
2387 }
2388
2389 static int update_disk_super_on_device(struct btrfs_fs_info *info,
2390                                        const char *other_dev, u64 cur_devid)
2391 {
2392         struct btrfs_key key;
2393         struct extent_buffer *leaf;
2394         struct btrfs_path path;
2395         struct btrfs_dev_item *dev_item;
2396         struct btrfs_super_block *disk_super;
2397         char dev_uuid[BTRFS_UUID_SIZE];
2398         char fs_uuid[BTRFS_UUID_SIZE];
2399         u64 devid, type, io_align, io_width;
2400         u64 sector_size, total_bytes, bytes_used;
2401         char *buf;
2402         int fp;
2403         int ret;
2404
2405         key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
2406         key.type = BTRFS_DEV_ITEM_KEY;
2407         key.offset = cur_devid;
2408
2409         btrfs_init_path(&path);
2410         ret = btrfs_search_slot(NULL, info->chunk_root, &key, &path, 0, 0);
2411         if (ret) {
2412                 fprintf(stderr, "search key fails\n");
2413                 exit(1);
2414         }
2415
2416         leaf = path.nodes[0];
2417         dev_item = btrfs_item_ptr(leaf, path.slots[0],
2418                                   struct btrfs_dev_item);
2419
2420         devid = btrfs_device_id(leaf, dev_item);
2421         if (devid != cur_devid) {
2422                 printk("devid %llu mismatch with %llu\n", devid, cur_devid);
2423                 exit(1);
2424         }
2425
2426         type = btrfs_device_type(leaf, dev_item);
2427         io_align = btrfs_device_io_align(leaf, dev_item);
2428         io_width = btrfs_device_io_width(leaf, dev_item);
2429         sector_size = btrfs_device_sector_size(leaf, dev_item);
2430         total_bytes = btrfs_device_total_bytes(leaf, dev_item);
2431         bytes_used = btrfs_device_bytes_used(leaf, dev_item);
2432         read_extent_buffer(leaf, dev_uuid, (unsigned long)btrfs_device_uuid(dev_item), BTRFS_UUID_SIZE);
2433         read_extent_buffer(leaf, fs_uuid, (unsigned long)btrfs_device_fsid(dev_item), BTRFS_UUID_SIZE);
2434
2435         btrfs_release_path(&path);
2436
2437         printk("update disk super on %s devid=%llu\n", other_dev, devid);
2438
2439         /* update other devices' super block */
2440         fp = open(other_dev, O_CREAT | O_RDWR, 0600);
2441         if (fp < 0) {
2442                 fprintf(stderr, "could not open %s\n", other_dev);
2443                 exit(1);
2444         }
2445
2446         buf = malloc(BTRFS_SUPER_INFO_SIZE);
2447         if (!buf) {
2448                 ret = -ENOMEM;
2449                 close(fp);
2450                 return ret;
2451         }
2452
2453         memcpy(buf, info->super_copy, BTRFS_SUPER_INFO_SIZE);
2454
2455         disk_super = (struct btrfs_super_block *)buf;
2456         dev_item = &disk_super->dev_item;
2457
2458         btrfs_set_stack_device_type(dev_item, type);
2459         btrfs_set_stack_device_id(dev_item, devid);
2460         btrfs_set_stack_device_total_bytes(dev_item, total_bytes);
2461         btrfs_set_stack_device_bytes_used(dev_item, bytes_used);
2462         btrfs_set_stack_device_io_align(dev_item, io_align);
2463         btrfs_set_stack_device_io_width(dev_item, io_width);
2464         btrfs_set_stack_device_sector_size(dev_item, sector_size);
2465         memcpy(dev_item->uuid, dev_uuid, BTRFS_UUID_SIZE);
2466         memcpy(dev_item->fsid, fs_uuid, BTRFS_UUID_SIZE);
2467         csum_block((u8 *)buf, BTRFS_SUPER_INFO_SIZE);
2468
2469         ret = pwrite64(fp, buf, BTRFS_SUPER_INFO_SIZE, BTRFS_SUPER_INFO_OFFSET);
2470         if (ret != BTRFS_SUPER_INFO_SIZE) {
2471                 ret = -EIO;
2472                 goto out;
2473         }
2474
2475         write_backup_supers(fp, (u8 *)buf);
2476
2477 out:
2478         free(buf);
2479         close(fp);
2480         return 0;
2481 }
2482
2483 static void print_usage(void)
2484 {
2485         fprintf(stderr, "usage: btrfs-image [options] source target\n");
2486         fprintf(stderr, "\t-r      \trestore metadump image\n");
2487         fprintf(stderr, "\t-c value\tcompression level (0 ~ 9)\n");
2488         fprintf(stderr, "\t-t value\tnumber of threads (1 ~ 32)\n");
2489         fprintf(stderr, "\t-o      \tdon't mess with the chunk tree when restoring\n");
2490         fprintf(stderr, "\t-s      \tsanitize file names, use once to just use garbage, use twice if you want crc collisions\n");
2491         fprintf(stderr, "\t-w      \twalk all trees instead of using extent tree, do this if your extent tree is broken\n");
2492         fprintf(stderr, "\t-m      \trestore for multiple devices\n");
2493         fprintf(stderr, "\n");
2494         fprintf(stderr, "\tIn the dump mode, source is the btrfs device and target is the output file (use '-' for stdout).\n");
2495         fprintf(stderr, "\tIn the restore mode, source is the dumped image and target is the btrfs device/file.\n");
2496         exit(1);
2497 }
2498
2499 int main(int argc, char *argv[])
2500 {
2501         char *source;
2502         char *target;
2503         u64 num_threads = 0;
2504         u64 compress_level = 0;
2505         int create = 1;
2506         int old_restore = 0;
2507         int walk_trees = 0;
2508         int multi_devices = 0;
2509         int ret;
2510         int sanitize = 0;
2511         int dev_cnt = 0;
2512         int usage_error = 0;
2513         FILE *out;
2514
2515         while (1) {
2516                 int c = getopt(argc, argv, "rc:t:oswm");
2517                 if (c < 0)
2518                         break;
2519                 switch (c) {
2520                 case 'r':
2521                         create = 0;
2522                         break;
2523                 case 't':
2524                         num_threads = arg_strtou64(optarg);
2525                         if (num_threads > 32)
2526                                 print_usage();
2527                         break;
2528                 case 'c':
2529                         compress_level = arg_strtou64(optarg);
2530                         if (compress_level > 9)
2531                                 print_usage();
2532                         break;
2533                 case 'o':
2534                         old_restore = 1;
2535                         break;
2536                 case 's':
2537                         sanitize++;
2538                         break;
2539                 case 'w':
2540                         walk_trees = 1;
2541                         break;
2542                 case 'm':
2543                         create = 0;
2544                         multi_devices = 1;
2545                         break;
2546                 default:
2547                         print_usage();
2548                 }
2549         }
2550
2551         argc = argc - optind;
2552         set_argv0(argv);
2553         if (check_argc_min(argc, 2))
2554                 print_usage();
2555
2556         dev_cnt = argc - 1;
2557
2558         if (create) {
2559                 if (old_restore) {
2560                         fprintf(stderr, "Usage error: create and restore cannot be used at the same time\n");
2561                         usage_error++;
2562                 }
2563         } else {
2564                 if (walk_trees || sanitize || compress_level) {
2565                         fprintf(stderr, "Usage error: use -w, -s, -c options for restore makes no sense\n");
2566                         usage_error++;
2567                 }
2568                 if (multi_devices && dev_cnt < 2) {
2569                         fprintf(stderr, "Usage error: not enough devices specified for -m option\n");
2570                         usage_error++;
2571                 }
2572                 if (!multi_devices && dev_cnt != 1) {
2573                         fprintf(stderr, "Usage error: accepts only 1 device without -m option\n");
2574                         usage_error++;
2575                 }
2576         }
2577
2578         if (usage_error)
2579                 print_usage();
2580
2581         source = argv[optind];
2582         target = argv[optind + 1];
2583
2584         if (create && !strcmp(target, "-")) {
2585                 out = stdout;
2586         } else {
2587                 out = fopen(target, "w+");
2588                 if (!out) {
2589                         perror("unable to create target file");
2590                         exit(1);
2591                 }
2592         }
2593
2594         if (num_threads == 0 && compress_level > 0) {
2595                 num_threads = sysconf(_SC_NPROCESSORS_ONLN);
2596                 if (num_threads <= 0)
2597                         num_threads = 1;
2598         }
2599
2600         if (create) {
2601                 ret = check_mounted(source);
2602                 if (ret < 0) {
2603                         fprintf(stderr, "Could not check mount status: %s\n",
2604                                 strerror(-ret));
2605                         exit(1);
2606                 } else if (ret)
2607                         fprintf(stderr,
2608                 "WARNING: The device is mounted. Make sure the filesystem is quiescent.\n");
2609
2610                 ret = create_metadump(source, out, num_threads,
2611                                       compress_level, sanitize, walk_trees);
2612         } else {
2613                 ret = restore_metadump(source, out, old_restore, 1,
2614                                        multi_devices);
2615         }
2616         if (ret) {
2617                 printk("%s failed (%s)\n", (create) ? "create" : "restore",
2618                        strerror(errno));
2619                 goto out;
2620         }
2621
2622          /* extended support for multiple devices */
2623         if (!create && multi_devices) {
2624                 struct btrfs_fs_info *info;
2625                 u64 total_devs;
2626                 int i;
2627
2628                 info = open_ctree_fs_info(target, 0, 0,
2629                                           OPEN_CTREE_PARTIAL |
2630                                           OPEN_CTREE_RESTORE);
2631                 if (!info) {
2632                         int e = errno;
2633                         fprintf(stderr, "unable to open %s error = %s\n",
2634                                 target, strerror(e));
2635                         return 1;
2636                 }
2637
2638                 total_devs = btrfs_super_num_devices(info->super_copy);
2639                 if (total_devs != dev_cnt) {
2640                         printk("it needs %llu devices but has only %d\n",
2641                                 total_devs, dev_cnt);
2642                         close_ctree(info->chunk_root);
2643                         goto out;
2644                 }
2645
2646                 /* update super block on other disks */
2647                 for (i = 2; i <= dev_cnt; i++) {
2648                         ret = update_disk_super_on_device(info,
2649                                         argv[optind + i], (u64)i);
2650                         if (ret) {
2651                                 printk("update disk super failed devid=%d (error=%d)\n",
2652                                         i, ret);
2653                                 close_ctree(info->chunk_root);
2654                                 exit(1);
2655                         }
2656                 }
2657
2658                 close_ctree(info->chunk_root);
2659
2660                 /* fix metadata block to map correct chunk */
2661                 ret = fixup_metadump(source, out, 1, target);
2662                 if (ret) {
2663                         fprintf(stderr, "fix metadump failed (error=%d)\n",
2664                                 ret);
2665                         exit(1);
2666                 }
2667         }
2668
2669 out:
2670         if (out == stdout) {
2671                 fflush(out);
2672         } else {
2673                 fclose(out);
2674                 if (ret && create) {
2675                         int unlink_ret;
2676
2677                         unlink_ret = unlink(target);
2678                         if (unlink_ret)
2679                                 fprintf(stderr,
2680                                         "unlink output file failed : %s\n",
2681                                         strerror(errno));
2682                 }
2683         }
2684
2685         return !!ret;
2686 }