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