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