chunk-recover.c

   1 /*
   2  * Copyright (C) 2013 FUJITSU LIMITED.  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 #define _XOPEN_SOURCE 500
  19 #define _GNU_SOURCE
  20
  21 #include <stdio.h>
  22 #include <stdio_ext.h>
  23 #include <stdlib.h>
  24 #include <sys/types.h>
  25 #include <sys/stat.h>
  26 #include <fcntl.h>
  27 #include <unistd.h>
  28 #include <uuid/uuid.h>
  29 #include <pthread.h>
  30
  31 #include "kerncompat.h"
  32 #include "list.h"
  33 #include "radix-tree.h"
  34 #include "ctree.h"
  35 #include "extent-cache.h"
  36 #include "disk-io.h"
  37 #include "volumes.h"
  38 #include "transaction.h"
  39 #include "crc32c.h"
  40 #include "utils.h"
  41 #include "version.h"
  42 #include "btrfsck.h"
  43 #include "commands.h"
  44
  45 #define BTRFS_NUM_MIRRORS                       2
  46
  47 struct recover_control {
  48         int verbose;
  49         int yes;
  50
  51         u16 csum_size;
  52         u32 sectorsize;
  53         u32 leafsize;
  54         u64 generation;
  55         u64 chunk_root_generation;
  56
  57         struct btrfs_fs_devices *fs_devices;
  58
  59         struct cache_tree chunk;
  60         struct block_group_tree bg;
  61         struct device_extent_tree devext;
  62         struct cache_tree eb_cache;
  63
  64         struct list_head good_chunks;
  65         struct list_head bad_chunks;
  66         struct list_head unrepaired_chunks;
  67         pthread_mutex_t rc_lock;
  68 };
  69
  70 struct extent_record {
  71         struct cache_extent cache;
  72         u64 generation;
  73         u8 csum[BTRFS_CSUM_SIZE];
  74         struct btrfs_device *devices[BTRFS_NUM_MIRRORS];
  75         u64 offsets[BTRFS_NUM_MIRRORS];
  76         int nmirrors;
  77 };
  78
  79 struct device_scan {
  80         struct recover_control *rc;
  81         struct btrfs_device *dev;
  82         int fd;
  83 };
  84
  85 static struct extent_record *btrfs_new_extent_record(struct extent_buffer *eb)
  86 {
  87         struct extent_record *rec;
  88
  89         rec = malloc(sizeof(*rec));
  90         if (!rec) {
  91                 fprintf(stderr, "Fail to allocate memory for extent record.\n");
  92                 exit(1);
  93         }
  94
  95         memset(rec, 0, sizeof(*rec));
  96         rec->cache.start = btrfs_header_bytenr(eb);
  97         rec->cache.size = eb->len;
  98         rec->generation = btrfs_header_generation(eb);
  99         read_extent_buffer(eb, rec->csum, (unsigned long)btrfs_header_csum(eb),
 100                            BTRFS_CSUM_SIZE);
 101         return rec;
 102 }
 103
 104 static int process_extent_buffer(struct cache_tree *eb_cache,
 105                                  struct extent_buffer *eb,
 106                                  struct btrfs_device *device, u64 offset)
 107 {
 108         struct extent_record *rec;
 109         struct extent_record *exist;
 110         struct cache_extent *cache;
 111         int ret = 0;
 112
 113         rec = btrfs_new_extent_record(eb);
 114         if (!rec->cache.size)
 115                 goto free_out;
 116 again:
 117         cache = lookup_cache_extent(eb_cache,
 118                                     rec->cache.start,
 119                                     rec->cache.size);
 120         if (cache) {
 121                 exist = container_of(cache, struct extent_record, cache);
 122
 123                 if (exist->generation > rec->generation)
 124                         goto free_out;
 125                 if (exist->generation == rec->generation) {
 126                         if (exist->cache.start != rec->cache.start ||
 127                             exist->cache.size != rec->cache.size ||
 128                             memcmp(exist->csum, rec->csum, BTRFS_CSUM_SIZE)) {
 129                                 ret = -EEXIST;
 130                         } else {
 131                                 BUG_ON(exist->nmirrors >= BTRFS_NUM_MIRRORS);
 132                                 exist->devices[exist->nmirrors] = device;
 133                                 exist->offsets[exist->nmirrors] = offset;
 134                                 exist->nmirrors++;
 135                         }
 136                         goto free_out;
 137                 }
 138                 remove_cache_extent(eb_cache, cache);
 139                 free(exist);
 140                 goto again;
 141         }
 142
 143         rec->devices[0] = device;
 144         rec->offsets[0] = offset;
 145         rec->nmirrors++;
 146         ret = insert_cache_extent(eb_cache, &rec->cache);
 147         BUG_ON(ret);
 148 out:
 149         return ret;
 150 free_out:
 151         free(rec);
 152         goto out;
 153 }
 154
 155 static void free_extent_record(struct cache_extent *cache)
 156 {
 157         struct extent_record *er;
 158
 159         er = container_of(cache, struct extent_record, cache);
 160         free(er);
 161 }
 162
 163 FREE_EXTENT_CACHE_BASED_TREE(extent_record, free_extent_record);
 164
 165 static struct btrfs_chunk *create_chunk_item(struct chunk_record *record)
 166 {
 167         struct btrfs_chunk *ret;
 168         struct btrfs_stripe *chunk_stripe;
 169         int i;
 170
 171         if (!record || record->num_stripes == 0)
 172                 return NULL;
 173         ret = malloc(btrfs_chunk_item_size(record->num_stripes));
 174         if (!ret)
 175                 return NULL;
 176         btrfs_set_stack_chunk_length(ret, record->length);
 177         btrfs_set_stack_chunk_owner(ret, record->owner);
 178         btrfs_set_stack_chunk_stripe_len(ret, record->stripe_len);
 179         btrfs_set_stack_chunk_type(ret, record->type_flags);
 180         btrfs_set_stack_chunk_io_align(ret, record->io_align);
 181         btrfs_set_stack_chunk_io_width(ret, record->io_width);
 182         btrfs_set_stack_chunk_sector_size(ret, record->sector_size);
 183         btrfs_set_stack_chunk_num_stripes(ret, record->num_stripes);
 184         btrfs_set_stack_chunk_sub_stripes(ret, record->sub_stripes);
 185         for (i = 0, chunk_stripe = &ret->stripe; i < record->num_stripes;
 186              i++, chunk_stripe++) {
 187                 btrfs_set_stack_stripe_devid(chunk_stripe,
 188                                 record->stripes[i].devid);
 189                 btrfs_set_stack_stripe_offset(chunk_stripe,
 190                                 record->stripes[i].offset);
 191                 memcpy(chunk_stripe->dev_uuid, record->stripes[i].dev_uuid,
 192                        BTRFS_UUID_SIZE);
 193         }
 194         return ret;
 195 }
 196
 197 static void init_recover_control(struct recover_control *rc, int verbose,
 198                 int yes)
 199 {
 200         memset(rc, 0, sizeof(struct recover_control));
 201         cache_tree_init(&rc->chunk);
 202         cache_tree_init(&rc->eb_cache);
 203         block_group_tree_init(&rc->bg);
 204         device_extent_tree_init(&rc->devext);
 205
 206         INIT_LIST_HEAD(&rc->good_chunks);
 207         INIT_LIST_HEAD(&rc->bad_chunks);
 208         INIT_LIST_HEAD(&rc->unrepaired_chunks);
 209
 210         rc->verbose = verbose;
 211         rc->yes = yes;
 212         pthread_mutex_init(&rc->rc_lock, NULL);
 213 }
 214
 215 static void free_recover_control(struct recover_control *rc)
 216 {
 217         free_block_group_tree(&rc->bg);
 218         free_chunk_cache_tree(&rc->chunk);
 219         free_device_extent_tree(&rc->devext);
 220         free_extent_record_tree(&rc->eb_cache);
 221         pthread_mutex_destroy(&rc->rc_lock);
 222 }
 223
 224 static int process_block_group_item(struct block_group_tree *bg_cache,
 225                                     struct extent_buffer *leaf,
 226                                     struct btrfs_key *key, int slot)
 227 {
 228         struct block_group_record *rec;
 229         struct block_group_record *exist;
 230         struct cache_extent *cache;
 231         int ret = 0;
 232
 233         rec = btrfs_new_block_group_record(leaf, key, slot);
 234         if (!rec->cache.size)
 235                 goto free_out;
 236 again:
 237         cache = lookup_cache_extent(&bg_cache->tree,
 238                                     rec->cache.start,
 239                                     rec->cache.size);
 240         if (cache) {
 241                 exist = container_of(cache, struct block_group_record, cache);
 242
 243                 /*check the generation and replace if needed*/
 244                 if (exist->generation > rec->generation)
 245                         goto free_out;
 246                 if (exist->generation == rec->generation) {
 247                         int offset = offsetof(struct block_group_record,
 248                                               generation);
 249                         /*
 250                          * According to the current kernel code, the following
 251                          * case is impossble, or there is something wrong in
 252                          * the kernel code.
 253                          */
 254                         if (memcmp(((void *)exist) + offset,
 255                                    ((void *)rec) + offset,
 256                                    sizeof(*rec) - offset))
 257                                 ret = -EEXIST;
 258                         goto free_out;
 259                 }
 260                 remove_cache_extent(&bg_cache->tree, cache);
 261                 list_del_init(&exist->list);
 262                 free(exist);
 263                 /*
 264                  * We must do seach again to avoid the following cache.
 265                  * /--old bg 1--//--old bg 2--/
 266                  *        /--new bg--/
 267                  */
 268                 goto again;
 269         }
 270
 271         ret = insert_block_group_record(bg_cache, rec);
 272         BUG_ON(ret);
 273 out:
 274         return ret;
 275 free_out:
 276         free(rec);
 277         goto out;
 278 }
 279
 280 static int process_chunk_item(struct cache_tree *chunk_cache,
 281                               struct extent_buffer *leaf, struct btrfs_key *key,
 282                               int slot)
 283 {
 284         struct chunk_record *rec;
 285         struct chunk_record *exist;
 286         struct cache_extent *cache;
 287         int ret = 0;
 288
 289         rec = btrfs_new_chunk_record(leaf, key, slot);
 290         if (!rec->cache.size)
 291                 goto free_out;
 292 again:
 293         cache = lookup_cache_extent(chunk_cache, rec->offset, rec->length);
 294         if (cache) {
 295                 exist = container_of(cache, struct chunk_record, cache);
 296
 297                 if (exist->generation > rec->generation)
 298                         goto free_out;
 299                 if (exist->generation == rec->generation) {
 300                         int num_stripes = rec->num_stripes;
 301                         int rec_size = btrfs_chunk_record_size(num_stripes);
 302                         int offset = offsetof(struct chunk_record, generation);
 303
 304                         if (exist->num_stripes != rec->num_stripes ||
 305                             memcmp(((void *)exist) + offset,
 306                                    ((void *)rec) + offset,
 307                                    rec_size - offset))
 308                                 ret = -EEXIST;
 309                         goto free_out;
 310                 }
 311                 remove_cache_extent(chunk_cache, cache);
 312                 free(exist);
 313                 goto again;
 314         }
 315         ret = insert_cache_extent(chunk_cache, &rec->cache);
 316         BUG_ON(ret);
 317 out:
 318         return ret;
 319 free_out:
 320         free(rec);
 321         goto out;
 322 }
 323
 324 static int process_device_extent_item(struct device_extent_tree *devext_cache,
 325                                       struct extent_buffer *leaf,
 326                                       struct btrfs_key *key, int slot)
 327 {
 328         struct device_extent_record *rec;
 329         struct device_extent_record *exist;
 330         struct cache_extent *cache;
 331         int ret = 0;
 332
 333         rec = btrfs_new_device_extent_record(leaf, key, slot);
 334         if (!rec->cache.size)
 335                 goto free_out;
 336 again:
 337         cache = lookup_cache_extent2(&devext_cache->tree,
 338                                      rec->cache.objectid,
 339                                      rec->cache.start,
 340                                      rec->cache.size);
 341         if (cache) {
 342                 exist = container_of(cache, struct device_extent_record, cache);
 343                 if (exist->generation > rec->generation)
 344                         goto free_out;
 345                 if (exist->generation == rec->generation) {
 346                         int offset = offsetof(struct device_extent_record,
 347                                               generation);
 348                         if (memcmp(((void *)exist) + offset,
 349                                    ((void *)rec) + offset,
 350                                    sizeof(*rec) - offset))
 351                                 ret = -EEXIST;
 352                         goto free_out;
 353                 }
 354                 remove_cache_extent(&devext_cache->tree, cache);
 355                 list_del_init(&exist->chunk_list);
 356                 list_del_init(&exist->device_list);
 357                 free(exist);
 358                 goto again;
 359         }
 360
 361         ret = insert_device_extent_record(devext_cache, rec);
 362         BUG_ON(ret);
 363 out:
 364         return ret;
 365 free_out:
 366         free(rec);
 367         goto out;
 368 }
 369
 370 static void print_block_group_info(struct block_group_record *rec, char *prefix)
 371 {
 372         if (prefix)
 373                 printf("%s", prefix);
 374         printf("Block Group: start = %llu, len = %llu, flag = %llx\n",
 375                rec->objectid, rec->offset, rec->flags);
 376 }
 377
 378 static void print_block_group_tree(struct block_group_tree *tree)
 379 {
 380         struct cache_extent *cache;
 381         struct block_group_record *rec;
 382
 383         printf("All Block Groups:\n");
 384         for (cache = first_cache_extent(&tree->tree); cache;
 385              cache = next_cache_extent(cache)) {
 386                 rec = container_of(cache, struct block_group_record, cache);
 387                 print_block_group_info(rec, "\t");
 388         }
 389         printf("\n");
 390 }
 391
 392 static void print_stripe_info(struct stripe *data, char *prefix1, char *prefix2,
 393                               int index)
 394 {
 395         if (prefix1)
 396                 printf("%s", prefix1);
 397         if (prefix2)
 398                 printf("%s", prefix2);
 399         printf("[%2d] Stripe: devid = %llu, offset = %llu\n",
 400                index, data->devid, data->offset);
 401 }
 402
 403 static void print_chunk_self_info(struct chunk_record *rec, char *prefix)
 404 {
 405         int i;
 406
 407         if (prefix)
 408                 printf("%s", prefix);
 409         printf("Chunk: start = %llu, len = %llu, type = %llx, num_stripes = %u\n",
 410                rec->offset, rec->length, rec->type_flags, rec->num_stripes);
 411         if (prefix)
 412                 printf("%s", prefix);
 413         printf("    Stripes list:\n");
 414         for (i = 0; i < rec->num_stripes; i++)
 415                 print_stripe_info(&rec->stripes[i], prefix, "    ", i);
 416 }
 417
 418 static void print_chunk_tree(struct cache_tree *tree)
 419 {
 420         struct cache_extent *n;
 421         struct chunk_record *entry;
 422
 423         printf("All Chunks:\n");
 424         for (n = first_cache_extent(tree); n;
 425              n = next_cache_extent(n)) {
 426                 entry = container_of(n, struct chunk_record, cache);
 427                 print_chunk_self_info(entry, "\t");
 428         }
 429         printf("\n");
 430 }
 431
 432 static void print_device_extent_info(struct device_extent_record *rec,
 433                                      char *prefix)
 434 {
 435         if (prefix)
 436                 printf("%s", prefix);
 437         printf("Device extent: devid = %llu, start = %llu, len = %llu, chunk offset = %llu\n",
 438                rec->objectid, rec->offset, rec->length, rec->chunk_offset);
 439 }
 440
 441 static void print_device_extent_tree(struct device_extent_tree *tree)
 442 {
 443         struct cache_extent *n;
 444         struct device_extent_record *entry;
 445
 446         printf("All Device Extents:\n");
 447         for (n = first_cache_extent(&tree->tree); n;
 448              n = next_cache_extent(n)) {
 449                 entry = container_of(n, struct device_extent_record, cache);
 450                 print_device_extent_info(entry, "\t");
 451         }
 452         printf("\n");
 453 }
 454
 455 static void print_device_info(struct btrfs_device *device, char *prefix)
 456 {
 457         if (prefix)
 458                 printf("%s", prefix);
 459         printf("Device: id = %llu, name = %s\n",
 460                device->devid, device->name);
 461 }
 462
 463 static void print_all_devices(struct list_head *devices)
 464 {
 465         struct btrfs_device *dev;
 466
 467         printf("All Devices:\n");
 468         list_for_each_entry(dev, devices, dev_list)
 469                 print_device_info(dev, "\t");
 470         printf("\n");
 471 }
 472
 473 static void print_scan_result(struct recover_control *rc)
 474 {
 475         if (!rc->verbose)
 476                 return;
 477
 478         printf("DEVICE SCAN RESULT:\n");
 479         printf("Filesystem Information:\n");
 480         printf("\tsectorsize: %d\n", rc->sectorsize);
 481         printf("\tleafsize: %d\n", rc->leafsize);
 482         printf("\ttree root generation: %llu\n", rc->generation);
 483         printf("\tchunk root generation: %llu\n", rc->chunk_root_generation);
 484         printf("\n");
 485
 486         print_all_devices(&rc->fs_devices->devices);
 487         print_block_group_tree(&rc->bg);
 488         print_chunk_tree(&rc->chunk);
 489         print_device_extent_tree(&rc->devext);
 490 }
 491
 492 static void print_chunk_info(struct chunk_record *chunk, char *prefix)
 493 {
 494         struct device_extent_record *devext;
 495         int i;
 496
 497         print_chunk_self_info(chunk, prefix);
 498         if (prefix)
 499                 printf("%s", prefix);
 500         if (chunk->bg_rec)
 501                 print_block_group_info(chunk->bg_rec, "    ");
 502         else
 503                 printf("    No block group.\n");
 504         if (prefix)
 505                 printf("%s", prefix);
 506         if (list_empty(&chunk->dextents)) {
 507                 printf("    No device extent.\n");
 508         } else {
 509                 printf("    Device extent list:\n");
 510                 i = 0;
 511                 list_for_each_entry(devext, &chunk->dextents, chunk_list) {
 512                         if (prefix)
 513                                 printf("%s", prefix);
 514                         printf("%s[%2d]", "        ", i);
 515                         print_device_extent_info(devext, NULL);
 516                         i++;
 517                 }
 518         }
 519 }
 520
 521 static void print_check_result(struct recover_control *rc)
 522 {
 523         struct chunk_record *chunk;
 524         struct block_group_record *bg;
 525         struct device_extent_record *devext;
 526         int total = 0;
 527         int good = 0;
 528         int bad = 0;
 529
 530         if (!rc->verbose)
 531                 return;
 532
 533         printf("CHECK RESULT:\n");
 534         printf("Healthy Chunks:\n");
 535         list_for_each_entry(chunk, &rc->good_chunks, list) {
 536                 print_chunk_info(chunk, "  ");
 537                 good++;
 538                 total++;
 539         }
 540         printf("Bad Chunks:\n");
 541         list_for_each_entry(chunk, &rc->bad_chunks, list) {
 542                 print_chunk_info(chunk, "  ");
 543                 bad++;
 544                 total++;
 545         }
 546         printf("\n");
 547         printf("Total Chunks:\t%d\n", total);
 548         printf("  Heathy:\t%d\n", good);
 549         printf("  Bad:\t%d\n", bad);
 550
 551         printf("\n");
 552         printf("Orphan Block Groups:\n");
 553         list_for_each_entry(bg, &rc->bg.block_groups, list)
 554                 print_block_group_info(bg, "  ");
 555
 556         printf("\n");
 557         printf("Orphan Device Extents:\n");
 558         list_for_each_entry(devext, &rc->devext.no_chunk_orphans, chunk_list)
 559                 print_device_extent_info(devext, "  ");
 560 }
 561
 562 static int check_chunk_by_metadata(struct recover_control *rc,
 563                                    struct btrfs_root *root,
 564                                    struct chunk_record *chunk, int bg_only)
 565 {
 566         int ret;
 567         int i;
 568         int slot;
 569         struct btrfs_path path;
 570         struct btrfs_key key;
 571         struct btrfs_root *dev_root;
 572         struct stripe *stripe;
 573         struct btrfs_dev_extent *dev_extent;
 574         struct btrfs_block_group_item *bg_ptr;
 575         struct extent_buffer *l;
 576
 577         btrfs_init_path(&path);
 578
 579         if (bg_only)
 580                 goto bg_check;
 581
 582         dev_root = root->fs_info->dev_root;
 583         for (i = 0; i < chunk->num_stripes; i++) {
 584                 stripe = &chunk->stripes[i];
 585
 586                 key.objectid = stripe->devid;
 587                 key.offset = stripe->offset;
 588                 key.type = BTRFS_DEV_EXTENT_KEY;
 589
 590                 ret = btrfs_search_slot(NULL, dev_root, &key, &path, 0, 0);
 591                 if (ret < 0) {
 592                         fprintf(stderr, "Search device extent failed(%d)\n",
 593                                 ret);
 594                         btrfs_release_path(&path);
 595                         return ret;
 596                 } else if (ret > 0) {
 597                         if (rc->verbose)
 598                                 fprintf(stderr,
 599                                         "No device extent[%llu, %llu]\n",
 600                                         stripe->devid, stripe->offset);
 601                         btrfs_release_path(&path);
 602                         return -ENOENT;
 603                 }
 604                 l = path.nodes[0];
 605                 slot = path.slots[0];
 606                 dev_extent = btrfs_item_ptr(l, slot, struct btrfs_dev_extent);
 607                 if (chunk->offset !=
 608                     btrfs_dev_extent_chunk_offset(l, dev_extent)) {
 609                         if (rc->verbose)
 610                                 fprintf(stderr,
 611                                         "Device tree unmatch with chunks dev_extent[%llu, %llu], chunk[%llu, %llu]\n",
 612                                         btrfs_dev_extent_chunk_offset(l,
 613                                                                 dev_extent),
 614                                         btrfs_dev_extent_length(l, dev_extent),
 615                                         chunk->offset, chunk->length);
 616                         btrfs_release_path(&path);
 617                         return -ENOENT;
 618                 }
 619                 btrfs_release_path(&path);
 620         }
 621
 622 bg_check:
 623         key.objectid = chunk->offset;
 624         key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
 625         key.offset = chunk->length;
 626
 627         ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, &path,
 628                                 0, 0);
 629         if (ret < 0) {
 630                 fprintf(stderr, "Search block group failed(%d)\n", ret);
 631                 btrfs_release_path(&path);
 632                 return ret;
 633         } else if (ret > 0) {
 634                 if (rc->verbose)
 635                         fprintf(stderr, "No block group[%llu, %llu]\n",
 636                                 key.objectid, key.offset);
 637                 btrfs_release_path(&path);
 638                 return -ENOENT;
 639         }
 640
 641         l = path.nodes[0];
 642         slot = path.slots[0];
 643         bg_ptr = btrfs_item_ptr(l, slot, struct btrfs_block_group_item);
 644         if (chunk->type_flags != btrfs_disk_block_group_flags(l, bg_ptr)) {
 645                 if (rc->verbose)
 646                         fprintf(stderr,
 647                                 "Chunk[%llu, %llu]'s type(%llu) is differemt with Block Group's type(%llu)\n",
 648                                 chunk->offset, chunk->length, chunk->type_flags,
 649                                 btrfs_disk_block_group_flags(l, bg_ptr));
 650                 btrfs_release_path(&path);
 651                 return -ENOENT;
 652         }
 653         btrfs_release_path(&path);
 654         return 0;
 655 }
 656
 657 static int check_all_chunks_by_metadata(struct recover_control *rc,
 658                                         struct btrfs_root *root)
 659 {
 660         struct chunk_record *chunk;
 661         struct chunk_record *next;
 662         LIST_HEAD(orphan_chunks);
 663         int ret = 0;
 664         int err;
 665
 666         list_for_each_entry_safe(chunk, next, &rc->good_chunks, list) {
 667                 err = check_chunk_by_metadata(rc, root, chunk, 0);
 668                 if (err) {
 669                         if (err == -ENOENT)
 670                                 list_move_tail(&chunk->list, &orphan_chunks);
 671                         else if (err && !ret)
 672                                 ret = err;
 673                 }
 674         }
 675
 676         list_for_each_entry_safe(chunk, next, &rc->unrepaired_chunks, list) {
 677                 err = check_chunk_by_metadata(rc, root, chunk, 1);
 678                 if (err == -ENOENT)
 679                         list_move_tail(&chunk->list, &orphan_chunks);
 680                 else if (err && !ret)
 681                         ret = err;
 682         }
 683
 684         list_for_each_entry(chunk, &rc->bad_chunks, list) {
 685                 err = check_chunk_by_metadata(rc, root, chunk, 1);
 686                 if (err != -ENOENT && !ret)
 687                         ret = err ? err : -EINVAL;
 688         }
 689         list_splice(&orphan_chunks, &rc->bad_chunks);
 690         return ret;
 691 }
 692
 693 static int extract_metadata_record(struct recover_control *rc,
 694                                    struct extent_buffer *leaf)
 695 {
 696         struct btrfs_key key;
 697         int ret = 0;
 698         int i;
 699         u32 nritems;
 700
 701         nritems = btrfs_header_nritems(leaf);
 702         for (i = 0; i < nritems; i++) {
 703                 btrfs_item_key_to_cpu(leaf, &key, i);
 704                 switch (key.type) {
 705                 case BTRFS_BLOCK_GROUP_ITEM_KEY:
 706                         pthread_mutex_lock(&rc->rc_lock);
 707                         ret = process_block_group_item(&rc->bg, leaf, &key, i);
 708                         pthread_mutex_unlock(&rc->rc_lock);
 709                         break;
 710                 case BTRFS_CHUNK_ITEM_KEY:
 711                         pthread_mutex_lock(&rc->rc_lock);
 712                         ret = process_chunk_item(&rc->chunk, leaf, &key, i);
 713                         pthread_mutex_unlock(&rc->rc_lock);
 714                         break;
 715                 case BTRFS_DEV_EXTENT_KEY:
 716                         pthread_mutex_lock(&rc->rc_lock);
 717                         ret = process_device_extent_item(&rc->devext, leaf,
 718                                                          &key, i);
 719                         pthread_mutex_unlock(&rc->rc_lock);
 720                         break;
 721                 }
 722                 if (ret)
 723                         break;
 724         }
 725         return ret;
 726 }
 727
 728 static inline int is_super_block_address(u64 offset)
 729 {
 730         int i;
 731
 732         for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
 733                 if (offset == btrfs_sb_offset(i))
 734                         return 1;
 735         }
 736         return 0;
 737 }
 738
 739 static int scan_one_device(void *dev_scan_struct)
 740 {
 741         struct extent_buffer *buf;
 742         u64 bytenr;
 743         int ret = 0;
 744         struct device_scan *dev_scan = (struct device_scan *)dev_scan_struct;
 745         struct recover_control *rc = dev_scan->rc;
 746         struct btrfs_device *device = dev_scan->dev;
 747         int fd = dev_scan->fd;
 748         int oldtype;
 749
 750         ret = pthread_setcanceltype(PTHREAD_CANCEL_ASYNCHRONOUS, &oldtype);
 751         if (ret)
 752                 return 1;
 753
 754         buf = malloc(sizeof(*buf) + rc->leafsize);
 755         if (!buf)
 756                 return -ENOMEM;
 757         buf->len = rc->leafsize;
 758
 759         bytenr = 0;
 760         while (1) {
 761                 if (is_super_block_address(bytenr))
 762                         bytenr += rc->sectorsize;
 763
 764                 if (pread64(fd, buf->data, rc->leafsize, bytenr) <
 765                     rc->leafsize)
 766                         break;
 767
 768                 if (memcmp_extent_buffer(buf, rc->fs_devices->fsid,
 769                                          btrfs_header_fsid(),
 770                                          BTRFS_FSID_SIZE)) {
 771                         bytenr += rc->sectorsize;
 772                         continue;
 773                 }
 774
 775                 if (verify_tree_block_csum_silent(buf, rc->csum_size)) {
 776                         bytenr += rc->sectorsize;
 777                         continue;
 778                 }
 779
 780                 pthread_mutex_lock(&rc->rc_lock);
 781                 ret = process_extent_buffer(&rc->eb_cache, buf, device, bytenr);
 782                 pthread_mutex_unlock(&rc->rc_lock);
 783                 if (ret)
 784                         goto out;
 785
 786                 if (btrfs_header_level(buf) != 0)
 787                         goto next_node;
 788
 789                 switch (btrfs_header_owner(buf)) {
 790                 case BTRFS_EXTENT_TREE_OBJECTID:
 791                 case BTRFS_DEV_TREE_OBJECTID:
 792                         /* different tree use different generation */
 793                         if (btrfs_header_generation(buf) > rc->generation)
 794                                 break;
 795                         ret = extract_metadata_record(rc, buf);
 796                         if (ret)
 797                                 goto out;
 798                         break;
 799                 case BTRFS_CHUNK_TREE_OBJECTID:
 800                         if (btrfs_header_generation(buf) >
 801                             rc->chunk_root_generation)
 802                                 break;
 803                         ret = extract_metadata_record(rc, buf);
 804                         if (ret)
 805                                 goto out;
 806                         break;
 807                 }
 808 next_node:
 809                 bytenr += rc->leafsize;
 810         }
 811 out:
 812         close(fd);
 813         free(buf);
 814         return ret;
 815 }
 816
 817 static int scan_devices(struct recover_control *rc)
 818 {
 819         int ret = 0;
 820         int fd;
 821         struct btrfs_device *dev;
 822         struct device_scan *dev_scans;
 823         pthread_t *t_scans;
 824         int *t_rets;
 825         int devnr = 0;
 826         int devidx = 0;
 827         int cancel_from = 0;
 828         int cancel_to = 0;
 829         int i;
 830
 831         list_for_each_entry(dev, &rc->fs_devices->devices, dev_list)
 832                 devnr++;
 833         dev_scans = (struct device_scan *)malloc(sizeof(struct device_scan)
 834                                                  * devnr);
 835         if (!dev_scans)
 836                 return -ENOMEM;
 837         t_scans = (pthread_t *)malloc(sizeof(pthread_t) * devnr);
 838         if (!t_scans)
 839                 return -ENOMEM;
 840         t_rets = (int *)malloc(sizeof(int) * devnr);
 841         if (!t_rets)
 842                 return -ENOMEM;
 843
 844         list_for_each_entry(dev, &rc->fs_devices->devices, dev_list) {
 845                 fd = open(dev->name, O_RDONLY);
 846                 if (fd < 0) {
 847                         fprintf(stderr, "Failed to open device %s\n",
 848                                 dev->name);
 849                         ret = 1;
 850                         goto out2;
 851                 }
 852                 dev_scans[devidx].rc = rc;
 853                 dev_scans[devidx].dev = dev;
 854                 dev_scans[devidx].fd = fd;
 855                 ret = pthread_create(&t_scans[devidx], NULL,
 856                                      (void *)scan_one_device,
 857                                      (void *)&dev_scans[devidx]);
 858                 if (ret) {
 859                         cancel_from = 0;
 860                         cancel_to = devidx - 1;
 861                         goto out1;
 862                 }
 863                 devidx++;
 864         }
 865
 866         i = 0;
 867         while (i < devidx) {
 868                 ret = pthread_join(t_scans[i], (void **)&t_rets[i]);
 869                 if (ret || t_rets[i]) {
 870                         ret = 1;
 871                         cancel_from = i + 1;
 872                         cancel_to = devnr - 1;
 873                         goto out1;
 874                 }
 875                 i++;
 876         }
 877 out1:
 878         while (ret && (cancel_from <= cancel_to)) {
 879                 pthread_cancel(t_scans[cancel_from]);
 880                 cancel_from++;
 881         }
 882 out2:
 883         free(dev_scans);
 884         free(t_scans);
 885         free(t_rets);
 886         return !!ret;
 887 }
 888
 889 static int build_device_map_by_chunk_record(struct btrfs_root *root,
 890                                             struct chunk_record *chunk)
 891 {
 892         int ret = 0;
 893         int i;
 894         u64 devid;
 895         u8 uuid[BTRFS_UUID_SIZE];
 896         u16 num_stripes;
 897         struct btrfs_mapping_tree *map_tree;
 898         struct map_lookup *map;
 899         struct stripe *stripe;
 900
 901         map_tree = &root->fs_info->mapping_tree;
 902         num_stripes = chunk->num_stripes;
 903         map = malloc(btrfs_map_lookup_size(num_stripes));
 904         if (!map)
 905                 return -ENOMEM;
 906         map->ce.start = chunk->offset;
 907         map->ce.size = chunk->length;
 908         map->num_stripes = num_stripes;
 909         map->io_width = chunk->io_width;
 910         map->io_align = chunk->io_align;
 911         map->sector_size = chunk->sector_size;
 912         map->stripe_len = chunk->stripe_len;
 913         map->type = chunk->type_flags;
 914         map->sub_stripes = chunk->sub_stripes;
 915
 916         for (i = 0, stripe = chunk->stripes; i < num_stripes; i++, stripe++) {
 917                 devid = stripe->devid;
 918                 memcpy(uuid, stripe->dev_uuid, BTRFS_UUID_SIZE);
 919                 map->stripes[i].physical = stripe->offset;
 920                 map->stripes[i].dev = btrfs_find_device(root, devid,
 921                                                         uuid, NULL);
 922                 if (!map->stripes[i].dev) {
 923                         kfree(map);
 924                         return -EIO;
 925                 }
 926         }
 927
 928         ret = insert_cache_extent(&map_tree->cache_tree, &map->ce);
 929         return ret;
 930 }
 931
 932 static int build_device_maps_by_chunk_records(struct recover_control *rc,
 933                                               struct btrfs_root *root)
 934 {
 935         int ret = 0;
 936         struct chunk_record *chunk;
 937
 938         list_for_each_entry(chunk, &rc->good_chunks, list) {
 939                 ret = build_device_map_by_chunk_record(root, chunk);
 940                 if (ret)
 941                         return ret;
 942         }
 943         return ret;
 944 }
 945
 946 static int block_group_remove_all_extent_items(struct btrfs_trans_handle *trans,
 947                                                struct btrfs_root *root,
 948                                                struct block_group_record *bg)
 949 {
 950         struct btrfs_fs_info *fs_info = root->fs_info;
 951         struct btrfs_key key;
 952         struct btrfs_path path;
 953         struct extent_buffer *leaf;
 954         u64 start = bg->objectid;
 955         u64 end = bg->objectid + bg->offset;
 956         u64 old_val;
 957         int nitems;
 958         int ret;
 959         int i;
 960         int del_s, del_nr;
 961
 962         btrfs_init_path(&path);
 963         root = root->fs_info->extent_root;
 964
 965         key.objectid = start;
 966         key.offset = 0;
 967         key.type = BTRFS_EXTENT_ITEM_KEY;
 968 again:
 969         ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
 970         if (ret < 0)
 971                 goto err;
 972         else if (ret > 0)
 973                 ret = 0;
 974
 975         leaf = path.nodes[0];
 976         nitems = btrfs_header_nritems(leaf);
 977         if (!nitems) {
 978                 /* The tree is empty. */
 979                 ret = 0;
 980                 goto err;
 981         }
 982
 983         if (path.slots[0] >= nitems) {
 984                 ret = btrfs_next_leaf(root, &path);
 985                 if (ret < 0)
 986                         goto err;
 987                 if (ret > 0) {
 988                         ret = 0;
 989                         goto err;
 990                 }
 991                 leaf = path.nodes[0];
 992                 btrfs_item_key_to_cpu(leaf, &key, 0);
 993                 if (key.objectid >= end)
 994                         goto err;
 995                 btrfs_release_path(&path);
 996                 goto again;
 997         }
 998
 999         del_nr = 0;
1000         del_s = -1;
1001         for (i = path.slots[0]; i < nitems; i++) {
1002                 btrfs_item_key_to_cpu(leaf, &key, i);
1003                 if (key.objectid >= end)
1004                         break;
1005
1006                 if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
1007                         if (del_nr == 0)
1008                                 continue;
1009                         else
1010                                 break;
1011                 }
1012
1013                 if (del_s == -1)
1014                         del_s = i;
1015                 del_nr++;
1016                 if (key.type == BTRFS_EXTENT_ITEM_KEY ||
1017                     key.type == BTRFS_METADATA_ITEM_KEY) {
1018                         old_val = btrfs_super_bytes_used(fs_info->super_copy);
1019                         if (key.type == BTRFS_METADATA_ITEM_KEY)
1020                                 old_val += root->leafsize;
1021                         else
1022                                 old_val += key.offset;
1023                         btrfs_set_super_bytes_used(fs_info->super_copy,
1024                                                    old_val);
1025                 }
1026         }
1027
1028         if (del_nr) {
1029                 ret = btrfs_del_items(trans, root, &path, del_s, del_nr);
1030                 if (ret)
1031                         goto err;
1032         }
1033
1034         if (key.objectid < end) {
1035                 if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
1036                         key.objectid += root->sectorsize;
1037                         key.type = BTRFS_EXTENT_ITEM_KEY;
1038                         key.offset = 0;
1039                 }
1040                 btrfs_release_path(&path);
1041                 goto again;
1042         }
1043 err:
1044         btrfs_release_path(&path);
1045         return ret;
1046 }
1047
1048 static int block_group_free_all_extent(struct btrfs_trans_handle *trans,
1049                                        struct btrfs_root *root,
1050                                        struct block_group_record *bg)
1051 {
1052         struct btrfs_block_group_cache *cache;
1053         struct btrfs_fs_info *info;
1054         u64 start;
1055         u64 end;
1056
1057         info = root->fs_info;
1058         cache = btrfs_lookup_block_group(info, bg->objectid);
1059         if (!cache)
1060                 return -ENOENT;
1061
1062         start = cache->key.objectid;
1063         end = start + cache->key.offset - 1;
1064
1065         set_extent_bits(&info->block_group_cache, start, end,
1066                         BLOCK_GROUP_DIRTY, GFP_NOFS);
1067         set_extent_dirty(&info->free_space_cache, start, end, GFP_NOFS);
1068
1069         btrfs_set_block_group_used(&cache->item, 0);
1070
1071         return 0;
1072 }
1073
1074 static int remove_chunk_extent_item(struct btrfs_trans_handle *trans,
1075                                     struct recover_control *rc,
1076                                     struct btrfs_root *root)
1077 {
1078         struct chunk_record *chunk;
1079         int ret = 0;
1080
1081         list_for_each_entry(chunk, &rc->good_chunks, list) {
1082                 if (!(chunk->type_flags & BTRFS_BLOCK_GROUP_SYSTEM))
1083                         continue;
1084                 ret = block_group_remove_all_extent_items(trans, root,
1085                                                           chunk->bg_rec);
1086                 if (ret)
1087                         return ret;
1088
1089                 ret = block_group_free_all_extent(trans, root, chunk->bg_rec);
1090                 if (ret)
1091                         return ret;
1092         }
1093         return ret;
1094 }
1095
1096 static int __rebuild_chunk_root(struct btrfs_trans_handle *trans,
1097                                 struct recover_control *rc,
1098                                 struct btrfs_root *root)
1099 {
1100         u64 min_devid = -1;
1101         struct btrfs_device *dev;
1102         struct extent_buffer *cow;
1103         struct btrfs_disk_key disk_key;
1104         int ret = 0;
1105
1106         list_for_each_entry(dev, &rc->fs_devices->devices, dev_list) {
1107                 if (min_devid > dev->devid)
1108                         min_devid = dev->devid;
1109         }
1110         disk_key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
1111         disk_key.type = BTRFS_DEV_ITEM_KEY;
1112         disk_key.offset = min_devid;
1113
1114         cow = btrfs_alloc_free_block(trans, root, root->nodesize,
1115                                      BTRFS_CHUNK_TREE_OBJECTID,
1116                                      &disk_key, 0, 0, 0);
1117         btrfs_set_header_bytenr(cow, cow->start);
1118         btrfs_set_header_generation(cow, trans->transid);
1119         btrfs_set_header_nritems(cow, 0);
1120         btrfs_set_header_level(cow, 0);
1121         btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
1122         btrfs_set_header_owner(cow, BTRFS_CHUNK_TREE_OBJECTID);
1123         write_extent_buffer(cow, root->fs_info->fsid,
1124                         btrfs_header_fsid(), BTRFS_FSID_SIZE);
1125
1126         write_extent_buffer(cow, root->fs_info->chunk_tree_uuid,
1127                         btrfs_header_chunk_tree_uuid(cow),
1128                         BTRFS_UUID_SIZE);
1129
1130         root->node = cow;
1131         btrfs_mark_buffer_dirty(cow);
1132
1133         return ret;
1134 }
1135
1136 static int __rebuild_device_items(struct btrfs_trans_handle *trans,
1137                                   struct recover_control *rc,
1138                                   struct btrfs_root *root)
1139 {
1140         struct btrfs_device *dev;
1141         struct btrfs_key key;
1142         struct btrfs_dev_item *dev_item;
1143         int ret = 0;
1144
1145         dev_item = malloc(sizeof(struct btrfs_dev_item));
1146         if (!dev_item)
1147                 return -ENOMEM;
1148
1149         list_for_each_entry(dev, &rc->fs_devices->devices, dev_list) {
1150                 key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
1151                 key.type = BTRFS_DEV_ITEM_KEY;
1152                 key.offset = dev->devid;
1153
1154                 btrfs_set_stack_device_generation(dev_item, 0);
1155                 btrfs_set_stack_device_type(dev_item, dev->type);
1156                 btrfs_set_stack_device_id(dev_item, dev->devid);
1157                 btrfs_set_stack_device_total_bytes(dev_item, dev->total_bytes);
1158                 btrfs_set_stack_device_bytes_used(dev_item, dev->bytes_used);
1159                 btrfs_set_stack_device_io_align(dev_item, dev->io_align);
1160                 btrfs_set_stack_device_io_width(dev_item, dev->io_width);
1161                 btrfs_set_stack_device_sector_size(dev_item, dev->sector_size);
1162                 memcpy(dev_item->uuid, dev->uuid, BTRFS_UUID_SIZE);
1163                 memcpy(dev_item->fsid, dev->fs_devices->fsid, BTRFS_UUID_SIZE);
1164
1165                 ret = btrfs_insert_item(trans, root, &key,
1166                                         dev_item, sizeof(*dev_item));
1167         }
1168
1169         free(dev_item);
1170         return ret;
1171 }
1172
1173 static int __rebuild_chunk_items(struct btrfs_trans_handle *trans,
1174                                  struct recover_control *rc,
1175                                  struct btrfs_root *root)
1176 {
1177         struct btrfs_key key;
1178         struct btrfs_chunk *chunk = NULL;
1179         struct btrfs_root *chunk_root;
1180         struct chunk_record *chunk_rec;
1181         int ret;
1182
1183         chunk_root = root->fs_info->chunk_root;
1184
1185         list_for_each_entry(chunk_rec, &rc->good_chunks, list) {
1186                 chunk = create_chunk_item(chunk_rec);
1187                 if (!chunk)
1188                         return -ENOMEM;
1189
1190                 key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
1191                 key.type = BTRFS_CHUNK_ITEM_KEY;
1192                 key.offset = chunk_rec->offset;
1193
1194                 ret = btrfs_insert_item(trans, chunk_root, &key, chunk,
1195                                 btrfs_chunk_item_size(chunk->num_stripes));
1196                 free(chunk);
1197                 if (ret)
1198                         return ret;
1199         }
1200         return 0;
1201 }
1202
1203 static int rebuild_chunk_tree(struct btrfs_trans_handle *trans,
1204                               struct recover_control *rc,
1205                               struct btrfs_root *root)
1206 {
1207         int ret = 0;
1208
1209         root = root->fs_info->chunk_root;
1210
1211         ret = __rebuild_chunk_root(trans, rc, root);
1212         if (ret)
1213                 return ret;
1214
1215         ret = __rebuild_device_items(trans, rc, root);
1216         if (ret)
1217                 return ret;
1218
1219         ret = __rebuild_chunk_items(trans, rc, root);
1220
1221         return ret;
1222 }
1223
1224 static int rebuild_sys_array(struct recover_control *rc,
1225                              struct btrfs_root *root)
1226 {
1227         struct btrfs_chunk *chunk;
1228         struct btrfs_key key;
1229         struct chunk_record *chunk_rec;
1230         int ret = 0;
1231         u16 num_stripes;
1232
1233         btrfs_set_super_sys_array_size(root->fs_info->super_copy, 0);
1234
1235         list_for_each_entry(chunk_rec, &rc->good_chunks, list) {
1236                 if (!(chunk_rec->type_flags & BTRFS_BLOCK_GROUP_SYSTEM))
1237                         continue;
1238
1239                 num_stripes = chunk_rec->num_stripes;
1240                 chunk = create_chunk_item(chunk_rec);
1241                 if (!chunk) {
1242                         ret = -ENOMEM;
1243                         break;
1244                 }
1245
1246                 key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
1247                 key.type = BTRFS_CHUNK_ITEM_KEY;
1248                 key.offset = chunk_rec->offset;
1249
1250                 ret = btrfs_add_system_chunk(NULL, root, &key, chunk,
1251                                 btrfs_chunk_item_size(num_stripes));
1252                 free(chunk);
1253                 if (ret)
1254                         break;
1255         }
1256         return ret;
1257
1258 }
1259
1260 static struct btrfs_root *
1261 open_ctree_with_broken_chunk(struct recover_control *rc)
1262 {
1263         struct btrfs_fs_info *fs_info;
1264         struct btrfs_super_block *disk_super;
1265         struct extent_buffer *eb;
1266         u32 sectorsize;
1267         u32 nodesize;
1268         u32 leafsize;
1269         u32 stripesize;
1270         int ret;
1271
1272         fs_info = btrfs_new_fs_info(1, BTRFS_SUPER_INFO_OFFSET);
1273         if (!fs_info) {
1274                 fprintf(stderr, "Failed to allocate memory for fs_info\n");
1275                 return ERR_PTR(-ENOMEM);
1276         }
1277         fs_info->is_chunk_recover = 1;
1278
1279         fs_info->fs_devices = rc->fs_devices;
1280         ret = btrfs_open_devices(fs_info->fs_devices, O_RDWR);
1281         if (ret)
1282                 goto out;
1283
1284         disk_super = fs_info->super_copy;
1285         ret = btrfs_read_dev_super(fs_info->fs_devices->latest_bdev,
1286                                    disk_super, fs_info->super_bytenr);
1287         if (ret) {
1288                 fprintf(stderr, "No valid btrfs found\n");
1289                 goto out_devices;
1290         }
1291
1292         memcpy(fs_info->fsid, &disk_super->fsid, BTRFS_FSID_SIZE);
1293
1294         ret = btrfs_check_fs_compatibility(disk_super, 1);
1295         if (ret)
1296                 goto out_devices;
1297
1298         nodesize = btrfs_super_nodesize(disk_super);
1299         leafsize = btrfs_super_leafsize(disk_super);
1300         sectorsize = btrfs_super_sectorsize(disk_super);
1301         stripesize = btrfs_super_stripesize(disk_super);
1302
1303         __setup_root(nodesize, leafsize, sectorsize, stripesize,
1304                      fs_info->chunk_root, fs_info, BTRFS_CHUNK_TREE_OBJECTID);
1305
1306         ret = build_device_maps_by_chunk_records(rc, fs_info->chunk_root);
1307         if (ret)
1308                 goto out_cleanup;
1309
1310         ret = btrfs_setup_all_roots(fs_info, 0, 0);
1311         if (ret)
1312                 goto out_failed;
1313
1314         eb = fs_info->tree_root->node;
1315         read_extent_buffer(eb, fs_info->chunk_tree_uuid,
1316                            btrfs_header_chunk_tree_uuid(eb),
1317                            BTRFS_UUID_SIZE);
1318
1319         return fs_info->fs_root;
1320 out_failed:
1321         btrfs_release_all_roots(fs_info);
1322 out_cleanup:
1323         btrfs_cleanup_all_caches(fs_info);
1324 out_devices:
1325         btrfs_close_devices(fs_info->fs_devices);
1326 out:
1327         btrfs_free_fs_info(fs_info);
1328         return ERR_PTR(ret);
1329 }
1330
1331 static int recover_prepare(struct recover_control *rc, char *path)
1332 {
1333         int ret;
1334         int fd;
1335         struct btrfs_super_block *sb;
1336         struct btrfs_fs_devices *fs_devices;
1337
1338         ret = 0;
1339         fd = open(path, O_RDONLY);
1340         if (fd < 0) {
1341                 fprintf(stderr, "open %s\n error.\n", path);
1342                 return -1;
1343         }
1344
1345         sb = malloc(sizeof(struct btrfs_super_block));
1346         if (!sb) {
1347                 fprintf(stderr, "allocating memory for sb failed.\n");
1348                 ret = -ENOMEM;
1349                 goto fail_close_fd;
1350         }
1351
1352         ret = btrfs_read_dev_super(fd, sb, BTRFS_SUPER_INFO_OFFSET);
1353         if (ret) {
1354                 fprintf(stderr, "read super block error\n");
1355                 goto fail_free_sb;
1356         }
1357
1358         rc->sectorsize = btrfs_super_sectorsize(sb);
1359         rc->leafsize = btrfs_super_leafsize(sb);
1360         rc->generation = btrfs_super_generation(sb);
1361         rc->chunk_root_generation = btrfs_super_chunk_root_generation(sb);
1362         rc->csum_size = btrfs_super_csum_size(sb);
1363
1364         /* if seed, the result of scanning below will be partial */
1365         if (btrfs_super_flags(sb) & BTRFS_SUPER_FLAG_SEEDING) {
1366                 fprintf(stderr, "this device is seed device\n");
1367                 ret = -1;
1368                 goto fail_free_sb;
1369         }
1370
1371         ret = btrfs_scan_fs_devices(fd, path, &fs_devices, 0, 1);
1372         if (ret)
1373                 goto fail_free_sb;
1374
1375         rc->fs_devices = fs_devices;
1376
1377         if (rc->verbose)
1378                 print_all_devices(&rc->fs_devices->devices);
1379
1380 fail_free_sb:
1381         free(sb);
1382 fail_close_fd:
1383         close(fd);
1384         return ret;
1385 }
1386
1387 static int btrfs_get_device_extents(u64 chunk_object,
1388                                     struct list_head *orphan_devexts,
1389                                     struct list_head *ret_list)
1390 {
1391         struct device_extent_record *devext;
1392         struct device_extent_record *next;
1393         int count = 0;
1394
1395         list_for_each_entry_safe(devext, next, orphan_devexts, chunk_list) {
1396                 if (devext->chunk_offset == chunk_object) {
1397                         list_move_tail(&devext->chunk_list, ret_list);
1398                         count++;
1399                 }
1400         }
1401         return count;
1402 }
1403
1404 static int calc_num_stripes(u64 type)
1405 {
1406         if (type & (BTRFS_BLOCK_GROUP_RAID0 |
1407                     BTRFS_BLOCK_GROUP_RAID10 |
1408                     BTRFS_BLOCK_GROUP_RAID5 |
1409                     BTRFS_BLOCK_GROUP_RAID6))
1410                 return 0;
1411         else if (type & (BTRFS_BLOCK_GROUP_RAID1 |
1412                          BTRFS_BLOCK_GROUP_DUP))
1413                 return 2;
1414         else
1415                 return 1;
1416 }
1417
1418 static inline int calc_sub_nstripes(u64 type)
1419 {
1420         if (type & BTRFS_BLOCK_GROUP_RAID10)
1421                 return 2;
1422         else
1423                 return 1;
1424 }
1425
1426 static int btrfs_verify_device_extents(struct block_group_record *bg,
1427                                        struct list_head *devexts, int ndevexts)
1428 {
1429         struct device_extent_record *devext;
1430         u64 strpie_length;
1431         int expected_num_stripes;
1432
1433         expected_num_stripes = calc_num_stripes(bg->flags);
1434         if (expected_num_stripes && expected_num_stripes != ndevexts)
1435                 return 1;
1436
1437         strpie_length = calc_stripe_length(bg->flags, bg->offset, ndevexts);
1438         list_for_each_entry(devext, devexts, chunk_list) {
1439                 if (devext->length != strpie_length)
1440                         return 1;
1441         }
1442         return 0;
1443 }
1444
1445 static int btrfs_rebuild_unordered_chunk_stripes(struct recover_control *rc,
1446                                                  struct chunk_record *chunk)
1447 {
1448         struct device_extent_record *devext;
1449         struct btrfs_device *device;
1450         int i;
1451
1452         devext = list_first_entry(&chunk->dextents, struct device_extent_record,
1453                                   chunk_list);
1454         for (i = 0; i < chunk->num_stripes; i++) {
1455                 chunk->stripes[i].devid = devext->objectid;
1456                 chunk->stripes[i].offset = devext->offset;
1457                 device = btrfs_find_device_by_devid(rc->fs_devices,
1458                                                     devext->objectid,
1459                                                     0);
1460                 if (!device)
1461                         return -ENOENT;
1462                 BUG_ON(btrfs_find_device_by_devid(rc->fs_devices,
1463                                                   devext->objectid,
1464                                                   1));
1465                 memcpy(chunk->stripes[i].dev_uuid, device->uuid,
1466                        BTRFS_UUID_SIZE);
1467                 devext = list_next_entry(devext, chunk_list);
1468         }
1469         return 0;
1470 }
1471
1472 static int btrfs_calc_stripe_index(struct chunk_record *chunk, u64 logical)
1473 {
1474         u64 offset = logical - chunk->offset;
1475         int stripe_nr;
1476         int nr_data_stripes;
1477         int index;
1478
1479         stripe_nr = offset / chunk->stripe_len;
1480         if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID0) {
1481                 index = stripe_nr % chunk->num_stripes;
1482         } else if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID10) {
1483                 index = stripe_nr % (chunk->num_stripes / chunk->sub_stripes);
1484                 index *= chunk->sub_stripes;
1485         } else if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID5) {
1486                 nr_data_stripes = chunk->num_stripes - 1;
1487                 index = stripe_nr % nr_data_stripes;
1488                 stripe_nr /= nr_data_stripes;
1489                 index = (index + stripe_nr) % chunk->num_stripes;
1490         } else if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID6) {
1491                 nr_data_stripes = chunk->num_stripes - 2;
1492                 index = stripe_nr % nr_data_stripes;
1493                 stripe_nr /= nr_data_stripes;
1494                 index = (index + stripe_nr) % chunk->num_stripes;
1495         } else {
1496                 BUG_ON(1);
1497         }
1498         return index;
1499 }
1500
1501 /* calc the logical offset which is the start of the next stripe. */
1502 static inline u64 btrfs_next_stripe_logical_offset(struct chunk_record *chunk,
1503                                                    u64 logical)
1504 {
1505         u64 offset = logical - chunk->offset;
1506
1507         offset /= chunk->stripe_len;
1508         offset *= chunk->stripe_len;
1509         offset += chunk->stripe_len;
1510
1511         return offset + chunk->offset;
1512 }
1513
1514 static int is_extent_record_in_device_extent(struct extent_record *er,
1515                                              struct device_extent_record *dext,
1516                                              int *mirror)
1517 {
1518         int i;
1519
1520         for (i = 0; i < er->nmirrors; i++) {
1521                 if (er->devices[i]->devid == dext->objectid &&
1522                     er->offsets[i] >= dext->offset &&
1523                     er->offsets[i] < dext->offset + dext->length) {
1524                         *mirror = i;
1525                         return 1;
1526                 }
1527         }
1528         return 0;
1529 }
1530
1531 static int
1532 btrfs_rebuild_ordered_meta_chunk_stripes(struct recover_control *rc,
1533                                          struct chunk_record *chunk)
1534 {
1535         u64 start = chunk->offset;
1536         u64 end = chunk->offset + chunk->length;
1537         struct cache_extent *cache;
1538         struct extent_record *er;
1539         struct device_extent_record *devext;
1540         struct device_extent_record *next;
1541         struct btrfs_device *device;
1542         LIST_HEAD(devexts);
1543         int index;
1544         int mirror;
1545         int ret;
1546
1547         cache = lookup_cache_extent(&rc->eb_cache,
1548                                     start, chunk->length);
1549         if (!cache) {
1550                 /* No used space, we can reorder the stripes freely. */
1551                 ret = btrfs_rebuild_unordered_chunk_stripes(rc, chunk);
1552                 return ret;
1553         }
1554
1555         list_splice_init(&chunk->dextents, &devexts);
1556 again:
1557         er = container_of(cache, struct extent_record, cache);
1558         index = btrfs_calc_stripe_index(chunk, er->cache.start);
1559         if (chunk->stripes[index].devid)
1560                 goto next;
1561         list_for_each_entry_safe(devext, next, &devexts, chunk_list) {
1562                 if (is_extent_record_in_device_extent(er, devext, &mirror)) {
1563                         chunk->stripes[index].devid = devext->objectid;
1564                         chunk->stripes[index].offset = devext->offset;
1565                         memcpy(chunk->stripes[index].dev_uuid,
1566                                er->devices[mirror]->uuid,
1567                                BTRFS_UUID_SIZE);
1568                         index++;
1569                         list_move(&devext->chunk_list, &chunk->dextents);
1570                 }
1571         }
1572 next:
1573         start = btrfs_next_stripe_logical_offset(chunk, er->cache.start);
1574         if (start >= end)
1575                 goto no_extent_record;
1576
1577         cache = lookup_cache_extent(&rc->eb_cache, start, end - start);
1578         if (cache)
1579                 goto again;
1580 no_extent_record:
1581         if (list_empty(&devexts))
1582                 return 0;
1583
1584         if (chunk->type_flags & (BTRFS_BLOCK_GROUP_RAID5 |
1585                                  BTRFS_BLOCK_GROUP_RAID6)) {
1586                 /* Fixme: try to recover the order by the parity block. */
1587                 list_splice_tail(&devexts, &chunk->dextents);
1588                 return -EINVAL;
1589         }
1590
1591         /* There is no data on the lost stripes, we can reorder them freely. */
1592         for (index = 0; index < chunk->num_stripes; index++) {
1593                 if (chunk->stripes[index].devid)
1594                         continue;
1595
1596                 devext = list_first_entry(&devexts,
1597                                           struct device_extent_record,
1598                                            chunk_list);
1599                 list_move(&devext->chunk_list, &chunk->dextents);
1600
1601                 chunk->stripes[index].devid = devext->objectid;
1602                 chunk->stripes[index].offset = devext->offset;
1603                 device = btrfs_find_device_by_devid(rc->fs_devices,
1604                                                     devext->objectid,
1605                                                     0);
1606                 if (!device) {
1607                         list_splice_tail(&devexts, &chunk->dextents);
1608                         return -EINVAL;
1609                 }
1610                 BUG_ON(btrfs_find_device_by_devid(rc->fs_devices,
1611                                                   devext->objectid,
1612                                                   1));
1613                 memcpy(chunk->stripes[index].dev_uuid, device->uuid,
1614                        BTRFS_UUID_SIZE);
1615         }
1616         return 0;
1617 }
1618
1619 #define BTRFS_ORDERED_RAID      (BTRFS_BLOCK_GROUP_RAID0 |      \
1620                                  BTRFS_BLOCK_GROUP_RAID10 |     \
1621                                  BTRFS_BLOCK_GROUP_RAID5 |      \
1622                                  BTRFS_BLOCK_GROUP_RAID6)
1623
1624 static int btrfs_rebuild_chunk_stripes(struct recover_control *rc,
1625                                        struct chunk_record *chunk)
1626 {
1627         int ret;
1628
1629         /*
1630          * All the data in the system metadata chunk will be dropped,
1631          * so we need not guarantee that the data is right or not, that
1632          * is we can reorder the stripes in the system metadata chunk.
1633          */
1634         if ((chunk->type_flags & BTRFS_BLOCK_GROUP_METADATA) &&
1635             (chunk->type_flags & BTRFS_ORDERED_RAID))
1636                 ret =btrfs_rebuild_ordered_meta_chunk_stripes(rc, chunk);
1637         else if ((chunk->type_flags & BTRFS_BLOCK_GROUP_DATA) &&
1638                  (chunk->type_flags & BTRFS_ORDERED_RAID))
1639                 ret = 1;        /* Be handled after the fs is opened. */
1640         else
1641                 ret = btrfs_rebuild_unordered_chunk_stripes(rc, chunk);
1642
1643         return ret;
1644 }
1645
1646 static int next_csum(struct btrfs_root *root,
1647                      struct extent_buffer **leaf,
1648                      struct btrfs_path *path,
1649                      int *slot,
1650                      u64 *csum_offset,
1651                      u32 *tree_csum,
1652                      u64 end,
1653                      struct btrfs_key *key)
1654 {
1655         int ret = 0;
1656         struct btrfs_root *csum_root = root->fs_info->csum_root;
1657         struct btrfs_csum_item *csum_item;
1658         u32 blocksize = root->sectorsize;
1659         u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
1660         int csums_in_item = btrfs_item_size_nr(*leaf, *slot) / csum_size;
1661
1662         if (*csum_offset >= csums_in_item) {
1663                 ++(*slot);
1664                 *csum_offset = 0;
1665                 if (*slot >= btrfs_header_nritems(*leaf)) {
1666                         ret = btrfs_next_leaf(csum_root, path);
1667                         if (ret < 0)
1668                                 return -1;
1669                         else if (ret > 0)
1670                                 return 1;
1671                         *leaf = path->nodes[0];
1672                         *slot = path->slots[0];
1673                 }
1674                 btrfs_item_key_to_cpu(*leaf, key, *slot);
1675         }
1676
1677         if (key->offset + (*csum_offset) * blocksize >= end)
1678                 return 2;
1679         csum_item = btrfs_item_ptr(*leaf, *slot, struct btrfs_csum_item);
1680         csum_item = (struct btrfs_csum_item *)((unsigned char *)csum_item
1681                                              + (*csum_offset) * csum_size);
1682         read_extent_buffer(*leaf, tree_csum,
1683                           (unsigned long)csum_item, csum_size);
1684         return ret;
1685 }
1686
1687 static u64 calc_data_offset(struct btrfs_key *key,
1688                             struct chunk_record *chunk,
1689                             u64 dev_offset,
1690                             u64 csum_offset,
1691                             u32 blocksize)
1692 {
1693         u64 data_offset;
1694         int logical_stripe_nr;
1695         int dev_stripe_nr;
1696         int nr_data_stripes;
1697
1698         data_offset = key->offset + csum_offset * blocksize - chunk->offset;
1699         nr_data_stripes = chunk->num_stripes;
1700
1701         if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID5)
1702                 nr_data_stripes -= 1;
1703         else if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID6)
1704                 nr_data_stripes -= 2;
1705
1706         logical_stripe_nr = data_offset / chunk->stripe_len;
1707         dev_stripe_nr = logical_stripe_nr / nr_data_stripes;
1708
1709         data_offset -= logical_stripe_nr * chunk->stripe_len;
1710         data_offset += dev_stripe_nr * chunk->stripe_len;
1711
1712         return dev_offset + data_offset;
1713 }
1714
1715 static int check_one_csum(int fd, u64 start, u32 len, u32 tree_csum)
1716 {
1717         char *data;
1718         int ret = 0;
1719         u32 csum_result = ~(u32)0;
1720
1721         data = malloc(len);
1722         if (!data)
1723                 return -1;
1724         ret = pread64(fd, data, len, start);
1725         if (ret < 0 || ret != len) {
1726                 ret = -1;
1727                 goto out;
1728         }
1729         ret = 0;
1730         csum_result = btrfs_csum_data(NULL, data, csum_result, len);
1731         btrfs_csum_final(csum_result, (char *)&csum_result);
1732         if (csum_result != tree_csum)
1733                 ret = 1;
1734 out:
1735         free(data);
1736         return ret;
1737 }
1738
1739 static u64 item_end_offset(struct btrfs_root *root, struct btrfs_key *key,
1740                            struct extent_buffer *leaf, int slot) {
1741         u32 blocksize = root->sectorsize;
1742         u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
1743
1744         u64 offset = btrfs_item_size_nr(leaf, slot);
1745         offset /= csum_size;
1746         offset *= blocksize;
1747         offset += key->offset;
1748
1749         return offset;
1750 }
1751
1752 static int insert_stripe(struct list_head *devexts,
1753                          struct recover_control *rc,
1754                          struct chunk_record *chunk,
1755                          int index) {
1756         struct device_extent_record *devext;
1757         struct btrfs_device *dev;
1758
1759         devext = list_entry(devexts->next, struct device_extent_record,
1760                             chunk_list);
1761         dev = btrfs_find_device_by_devid(rc->fs_devices, devext->objectid,
1762                                         0);
1763         if (!dev)
1764                 return 1;
1765         BUG_ON(btrfs_find_device_by_devid(rc->fs_devices, devext->objectid,
1766                                         1));
1767
1768         chunk->stripes[index].devid = devext->objectid;
1769         chunk->stripes[index].offset = devext->offset;
1770         memcpy(chunk->stripes[index].dev_uuid, dev->uuid, BTRFS_UUID_SIZE);
1771
1772         list_move(&devext->chunk_list, &chunk->dextents);
1773
1774         return 0;
1775 }
1776
1777 static inline int count_devext_records(struct list_head *record_list)
1778 {
1779         int num_of_records = 0;
1780         struct device_extent_record *devext;
1781
1782         list_for_each_entry(devext, record_list, chunk_list)
1783                 num_of_records++;
1784
1785         return num_of_records;
1786 }
1787
1788 static int fill_chunk_up(struct chunk_record *chunk, struct list_head *devexts,
1789                          struct recover_control *rc)
1790 {
1791         int ret = 0;
1792         int i;
1793
1794         for (i = 0; i < chunk->num_stripes; i++) {
1795                 if (!chunk->stripes[i].devid) {
1796                         ret = insert_stripe(devexts, rc, chunk, i);
1797                         if (ret)
1798                                 break;
1799                 }
1800         }
1801
1802         return ret;
1803 }
1804
1805 #define EQUAL_STRIPE (1 << 0)
1806
1807 static int rebuild_raid_data_chunk_stripes(struct recover_control *rc,
1808                                            struct btrfs_root *root,
1809                                            struct chunk_record *chunk,
1810                                            u8 *flags)
1811 {
1812         int i;
1813         int ret = 0;
1814         int slot;
1815         struct btrfs_path path;
1816         struct btrfs_key prev_key;
1817         struct btrfs_key key;
1818         struct btrfs_root *csum_root;
1819         struct extent_buffer *leaf;
1820         struct device_extent_record *devext;
1821         struct device_extent_record *next;
1822         struct btrfs_device *dev;
1823         u64 start = chunk->offset;
1824         u64 end = start + chunk->stripe_len;
1825         u64 chunk_end = chunk->offset + chunk->length;
1826         u64 csum_offset = 0;
1827         u64 data_offset;
1828         u32 blocksize = root->sectorsize;
1829         u32 tree_csum;
1830         int index = 0;
1831         int num_unordered = 0;
1832         LIST_HEAD(unordered);
1833         LIST_HEAD(candidates);
1834
1835         csum_root = root->fs_info->csum_root;
1836         btrfs_init_path(&path);
1837         list_splice_init(&chunk->dextents, &candidates);
1838 again:
1839         if (list_is_last(candidates.next, &candidates))
1840                 goto out;
1841
1842         key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
1843         key.type = BTRFS_EXTENT_CSUM_KEY;
1844         key.offset = start;
1845
1846         ret = btrfs_search_slot(NULL, csum_root, &key, &path, 0, 0);
1847         if (ret < 0) {
1848                 fprintf(stderr, "Search csum failed(%d)\n", ret);
1849                 goto fail_out;
1850         }
1851         leaf = path.nodes[0];
1852         slot = path.slots[0];
1853         if (ret > 0) {
1854                 if (slot >= btrfs_header_nritems(leaf)) {
1855                         ret = btrfs_next_leaf(csum_root, &path);
1856                         if (ret < 0) {
1857                                 fprintf(stderr,
1858                                         "Walk tree failed(%d)\n", ret);
1859                                 goto fail_out;
1860                         } else if (ret > 0) {
1861                                 slot = btrfs_header_nritems(leaf) - 1;
1862                                 btrfs_item_key_to_cpu(leaf, &key, slot);
1863                                 if (item_end_offset(root, &key, leaf, slot)
1864                                                                 > start) {
1865                                         csum_offset = start - key.offset;
1866                                         csum_offset /= blocksize;
1867                                         goto next_csum;
1868                                 }
1869                                 goto next_stripe;
1870                         }
1871                         leaf = path.nodes[0];
1872                         slot = path.slots[0];
1873                 }
1874                 btrfs_item_key_to_cpu(leaf, &key, slot);
1875                 ret = btrfs_previous_item(csum_root, &path, 0,
1876                                           BTRFS_EXTENT_CSUM_KEY);
1877                 if (ret < 0)
1878                         goto fail_out;
1879                 else if (ret > 0) {
1880                         if (key.offset >= end)
1881                                 goto next_stripe;
1882                         else
1883                                 goto next_csum;
1884                 }
1885                 leaf = path.nodes[0];
1886                 slot = path.slots[0];
1887
1888                 btrfs_item_key_to_cpu(leaf, &prev_key, slot);
1889                 if (item_end_offset(root, &prev_key, leaf, slot) > start) {
1890                         csum_offset = start - prev_key.offset;
1891                         csum_offset /= blocksize;
1892                         btrfs_item_key_to_cpu(leaf, &key, slot);
1893                 } else {
1894                         if (key.offset >= end)
1895                                 goto next_stripe;
1896                 }
1897
1898                 if (key.offset + csum_offset * blocksize > chunk_end)
1899                         goto out;
1900         }
1901 next_csum:
1902         ret = next_csum(root, &leaf, &path, &slot, &csum_offset, &tree_csum,
1903                         end, &key);
1904         if (ret < 0) {
1905                 fprintf(stderr, "Fetch csum failed\n");
1906                 goto fail_out;
1907         } else if (ret == 1) {
1908                 if (!(*flags & EQUAL_STRIPE))
1909                         *flags |= EQUAL_STRIPE;
1910                 goto out;
1911         } else if (ret == 2)
1912                 goto next_stripe;
1913
1914         list_for_each_entry_safe(devext, next, &candidates, chunk_list) {
1915                 data_offset = calc_data_offset(&key, chunk, devext->offset,
1916                                                csum_offset, blocksize);
1917                 dev = btrfs_find_device_by_devid(rc->fs_devices,
1918                                                  devext->objectid, 0);
1919                 if (!dev) {
1920                         ret = 1;
1921                         goto fail_out;
1922                 }
1923                 BUG_ON(btrfs_find_device_by_devid(rc->fs_devices,
1924                                                   devext->objectid, 1));
1925
1926                 ret = check_one_csum(dev->fd, data_offset, blocksize,
1927                                      tree_csum);
1928                 if (ret < 0)
1929                         goto fail_out;
1930                 else if (ret > 0)
1931                         list_move(&devext->chunk_list, &unordered);
1932         }
1933
1934         if (list_empty(&candidates)) {
1935                 num_unordered = count_devext_records(&unordered);
1936                 if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID6
1937                                         && num_unordered == 2) {
1938                         btrfs_release_path(&path);
1939                         ret = fill_chunk_up(chunk, &unordered, rc);
1940                         return ret;
1941                 }
1942
1943                 goto next_stripe;
1944         }
1945
1946         if (list_is_last(candidates.next, &candidates)) {
1947                 index = btrfs_calc_stripe_index(chunk,
1948                         key.offset + csum_offset * blocksize);
1949                 if (chunk->stripes[index].devid)
1950                         goto next_stripe;
1951                 ret = insert_stripe(&candidates, rc, chunk, index);
1952                 if (ret)
1953                         goto fail_out;
1954         } else {
1955                 csum_offset++;
1956                 goto next_csum;
1957         }
1958 next_stripe:
1959         start = btrfs_next_stripe_logical_offset(chunk, start);
1960         end = min(start + chunk->stripe_len, chunk_end);
1961         list_splice_init(&unordered, &candidates);
1962         btrfs_release_path(&path);
1963         csum_offset = 0;
1964         if (end < chunk_end)
1965                 goto again;
1966 out:
1967         ret = 0;
1968         list_splice_init(&candidates, &unordered);
1969         num_unordered = count_devext_records(&unordered);
1970         if (num_unordered == 1) {
1971                 for (i = 0; i < chunk->num_stripes; i++) {
1972                         if (!chunk->stripes[i].devid) {
1973                                 index = i;
1974                                 break;
1975                         }
1976                 }
1977                 ret = insert_stripe(&unordered, rc, chunk, index);
1978                 if (ret)
1979                         goto fail_out;
1980         } else {
1981                 if ((num_unordered == 2 && chunk->type_flags
1982                         & BTRFS_BLOCK_GROUP_RAID5)
1983                  || (num_unordered == 3 && chunk->type_flags
1984                         & BTRFS_BLOCK_GROUP_RAID6)) {
1985                         ret = fill_chunk_up(chunk, &unordered, rc);
1986                 }
1987         }
1988 fail_out:
1989         ret = !!ret || (list_empty(&unordered) ? 0 : 1);
1990         list_splice_init(&candidates, &chunk->dextents);
1991         list_splice_init(&unordered, &chunk->dextents);
1992         btrfs_release_path(&path);
1993
1994         return ret;
1995 }
1996
1997 static int btrfs_rebuild_ordered_data_chunk_stripes(struct recover_control *rc,
1998                                            struct btrfs_root *root)
1999 {
2000         struct chunk_record *chunk;
2001         struct chunk_record *next;
2002         int ret = 0;
2003         int err;
2004         u8 flags;
2005
2006         list_for_each_entry_safe(chunk, next, &rc->unrepaired_chunks, list) {
2007                 if ((chunk->type_flags & BTRFS_BLOCK_GROUP_DATA)
2008                  && (chunk->type_flags & BTRFS_ORDERED_RAID)) {
2009                         flags = 0;
2010                         err = rebuild_raid_data_chunk_stripes(rc, root, chunk,
2011                                                               &flags);
2012                         if (err) {
2013                                 list_move(&chunk->list, &rc->bad_chunks);
2014                                 if (flags & EQUAL_STRIPE)
2015                                         fprintf(stderr,
2016                         "Failure: too many equal stripes in chunk[%llu %llu]\n",
2017                                                 chunk->offset, chunk->length);
2018                                 if (!ret)
2019                                         ret = err;
2020                         } else
2021                                 list_move(&chunk->list, &rc->good_chunks);
2022                 }
2023         }
2024         return ret;
2025 }
2026
2027 static int btrfs_recover_chunks(struct recover_control *rc)
2028 {
2029         struct chunk_record *chunk;
2030         struct block_group_record *bg;
2031         struct block_group_record *next;
2032         LIST_HEAD(new_chunks);
2033         LIST_HEAD(devexts);
2034         int nstripes;
2035         int ret;
2036
2037         /* create the chunk by block group */
2038         list_for_each_entry_safe(bg, next, &rc->bg.block_groups, list) {
2039                 nstripes = btrfs_get_device_extents(bg->objectid,
2040                                                     &rc->devext.no_chunk_orphans,
2041                                                     &devexts);
2042                 chunk = malloc(btrfs_chunk_record_size(nstripes));
2043                 if (!chunk)
2044                         return -ENOMEM;
2045                 memset(chunk, 0, btrfs_chunk_record_size(nstripes));
2046                 INIT_LIST_HEAD(&chunk->dextents);
2047                 chunk->bg_rec = bg;
2048                 chunk->cache.start = bg->objectid;
2049                 chunk->cache.size = bg->offset;
2050                 chunk->objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
2051                 chunk->type = BTRFS_CHUNK_ITEM_KEY;
2052                 chunk->offset = bg->objectid;
2053                 chunk->generation = bg->generation;
2054                 chunk->length = bg->offset;
2055                 chunk->owner = BTRFS_CHUNK_TREE_OBJECTID;
2056                 chunk->stripe_len = BTRFS_STRIPE_LEN;
2057                 chunk->type_flags = bg->flags;
2058                 chunk->io_width = BTRFS_STRIPE_LEN;
2059                 chunk->io_align = BTRFS_STRIPE_LEN;
2060                 chunk->sector_size = rc->sectorsize;
2061                 chunk->sub_stripes = calc_sub_nstripes(bg->flags);
2062
2063                 ret = insert_cache_extent(&rc->chunk, &chunk->cache);
2064                 BUG_ON(ret);
2065
2066                 if (!nstripes) {
2067                         list_add_tail(&chunk->list, &rc->bad_chunks);
2068                         continue;
2069                 }
2070
2071                 list_splice_init(&devexts, &chunk->dextents);
2072
2073                 ret = btrfs_verify_device_extents(bg, &devexts, nstripes);
2074                 if (ret) {
2075                         list_add_tail(&chunk->list, &rc->bad_chunks);
2076                         continue;
2077                 }
2078
2079                 chunk->num_stripes = nstripes;
2080                 ret = btrfs_rebuild_chunk_stripes(rc, chunk);
2081                 if (ret > 0)
2082                         list_add_tail(&chunk->list, &rc->unrepaired_chunks);
2083                 else if (ret < 0)
2084                         list_add_tail(&chunk->list, &rc->bad_chunks);
2085                 else
2086                         list_add_tail(&chunk->list, &rc->good_chunks);
2087         }
2088         /*
2089          * Don't worry about the lost orphan device extents, they don't
2090          * have its chunk and block group, they must be the old ones that
2091          * we have dropped.
2092          */
2093         return 0;
2094 }
2095
2096 /*
2097  * Return 0 when succesful, < 0 on error and > 0 if aborted by user
2098  */
2099 int btrfs_recover_chunk_tree(char *path, int verbose, int yes)
2100 {
2101         int ret = 0;
2102         struct btrfs_root *root = NULL;
2103         struct btrfs_trans_handle *trans;
2104         struct recover_control rc;
2105
2106         init_recover_control(&rc, verbose, yes);
2107
2108         ret = recover_prepare(&rc, path);
2109         if (ret) {
2110                 fprintf(stderr, "recover prepare error\n");
2111                 return ret;
2112         }
2113
2114         ret = scan_devices(&rc);
2115         if (ret) {
2116                 fprintf(stderr, "scan chunk headers error\n");
2117                 goto fail_rc;
2118         }
2119
2120         if (cache_tree_empty(&rc.chunk) &&
2121             cache_tree_empty(&rc.bg.tree) &&
2122             cache_tree_empty(&rc.devext.tree)) {
2123                 fprintf(stderr, "no recoverable chunk\n");
2124                 goto fail_rc;
2125         }
2126
2127         print_scan_result(&rc);
2128
2129         ret = check_chunks(&rc.chunk, &rc.bg, &rc.devext, &rc.good_chunks,
2130                            &rc.bad_chunks, 1);
2131         print_check_result(&rc);
2132         if (ret) {
2133                 if (!list_empty(&rc.bg.block_groups) ||
2134                     !list_empty(&rc.devext.no_chunk_orphans)) {
2135                         ret = btrfs_recover_chunks(&rc);
2136                         if (ret)
2137                                 goto fail_rc;
2138                 }
2139                 /*
2140                  * If the chunk is healthy, its block group item and device
2141                  * extent item should be written on the disks. So, it is very
2142                  * likely that the bad chunk is a old one that has been
2143                  * droppped from the fs. Don't deal with them now, we will
2144                  * check it after the fs is opened.
2145                  */
2146         } else {
2147                 fprintf(stderr, "Check chunks successfully with no orphans\n");
2148                 goto fail_rc;
2149         }
2150
2151         root = open_ctree_with_broken_chunk(&rc);
2152         if (IS_ERR(root)) {
2153                 fprintf(stderr, "open with broken chunk error\n");
2154                 ret = PTR_ERR(root);
2155                 goto fail_rc;
2156         }
2157
2158         ret = check_all_chunks_by_metadata(&rc, root);
2159         if (ret) {
2160                 fprintf(stderr, "The chunks in memory can not match the metadata of the fs. Repair failed.\n");
2161                 goto fail_close_ctree;
2162         }
2163
2164         ret = btrfs_rebuild_ordered_data_chunk_stripes(&rc, root);
2165         if (ret) {
2166                 fprintf(stderr, "Failed to rebuild ordered chunk stripes.\n");
2167                 goto fail_close_ctree;
2168         }
2169
2170         if (!rc.yes) {
2171                 ret = ask_user("We are going to rebuild the chunk tree on disk, it might destroy the old metadata on the disk, Are you sure?");
2172                 if (!ret) {
2173                         ret = 1;
2174                         goto fail_close_ctree;
2175                 }
2176         }
2177
2178         trans = btrfs_start_transaction(root, 1);
2179         ret = remove_chunk_extent_item(trans, &rc, root);
2180         BUG_ON(ret);
2181
2182         ret = rebuild_chunk_tree(trans, &rc, root);
2183         BUG_ON(ret);
2184
2185         ret = rebuild_sys_array(&rc, root);
2186         BUG_ON(ret);
2187
2188         btrfs_commit_transaction(trans, root);
2189 fail_close_ctree:
2190         close_ctree(root);
2191 fail_rc:
2192         free_recover_control(&rc);
2193         return ret;
2194 }