chunk-recover.c

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