chunk-recover.c

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