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