cmds-chunk.c

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