chunk-recover.c

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