Btrfs-progs: pass flag to control whether run ioctl in btrfs_scan_for_fsid()
[platform/upstream/btrfs-progs.git] / chunk-recover.c
1 /*
2  * Copyright (C) 2013 Fujitsu.  All rights reserved.
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public
6  * License v2 as published by the Free Software Foundation.
7  *
8  * This program is distributed in the hope that it will be useful,
9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
11  * General Public License for more details.
12  *
13  * You should have received a copy of the GNU General Public
14  * License along with this program; if not, write to the
15  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16  * Boston, MA 021110-1307, USA.
17  */
18 #define _XOPEN_SOURCE 500
19 #define _GNU_SOURCE
20
21 #include <stdio.h>
22 #include <stdio_ext.h>
23 #include <stdlib.h>
24 #include <sys/types.h>
25 #include <sys/stat.h>
26 #include <fcntl.h>
27 #include <unistd.h>
28 #include <uuid/uuid.h>
29
30 #include "kerncompat.h"
31 #include "list.h"
32 #include "radix-tree.h"
33 #include "ctree.h"
34 #include "extent-cache.h"
35 #include "disk-io.h"
36 #include "volumes.h"
37 #include "transaction.h"
38 #include "crc32c.h"
39 #include "utils.h"
40 #include "version.h"
41 #include "btrfsck.h"
42 #include "commands.h"
43
44 #define BTRFS_STRIPE_LEN                        (64 * 1024)
45 #define BTRFS_NUM_MIRRORS                       2
46
47 struct recover_control {
48         int verbose;
49         int yes;
50
51         u16 csum_size;
52         u32 sectorsize;
53         u32 leafsize;
54         u64 generation;
55         u64 chunk_root_generation;
56
57         struct btrfs_fs_devices *fs_devices;
58
59         struct cache_tree chunk;
60         struct block_group_tree bg;
61         struct device_extent_tree devext;
62         struct cache_tree eb_cache;
63
64         struct list_head good_chunks;
65         struct list_head bad_chunks;
66         struct list_head unrepaired_chunks;
67 };
68
69 struct extent_record {
70         struct cache_extent cache;
71         u64 generation;
72         u8 csum[BTRFS_CSUM_SIZE];
73         struct btrfs_device *devices[BTRFS_NUM_MIRRORS];
74         u64 offsets[BTRFS_NUM_MIRRORS];
75         int nmirrors;
76 };
77
78 static struct extent_record *btrfs_new_extent_record(struct extent_buffer *eb)
79 {
80         struct extent_record *rec;
81
82         rec = malloc(sizeof(*rec));
83         if (!rec) {
84                 fprintf(stderr, "Fail to allocate memory for extent record.\n");
85                 exit(1);
86         }
87
88         memset(rec, 0, sizeof(*rec));
89         rec->cache.start = btrfs_header_bytenr(eb);
90         rec->cache.size = eb->len;
91         rec->generation = btrfs_header_generation(eb);
92         read_extent_buffer(eb, rec->csum, (unsigned long)btrfs_header_csum(eb),
93                            BTRFS_CSUM_SIZE);
94         return rec;
95 }
96
97 static int process_extent_buffer(struct cache_tree *eb_cache,
98                                  struct extent_buffer *eb,
99                                  struct btrfs_device *device, u64 offset)
100 {
101         struct extent_record *rec;
102         struct extent_record *exist;
103         struct cache_extent *cache;
104         int ret = 0;
105
106         rec = btrfs_new_extent_record(eb);
107         if (!rec->cache.size)
108                 goto free_out;
109 again:
110         cache = lookup_cache_extent(eb_cache,
111                                     rec->cache.start,
112                                     rec->cache.size);
113         if (cache) {
114                 exist = container_of(cache, struct extent_record, cache);
115
116                 if (exist->generation > rec->generation)
117                         goto free_out;
118                 if (exist->generation == rec->generation) {
119                         if (exist->cache.start != rec->cache.start ||
120                             exist->cache.size != rec->cache.size ||
121                             memcmp(exist->csum, rec->csum, BTRFS_CSUM_SIZE)) {
122                                 ret = -EEXIST;
123                         } else {
124                                 BUG_ON(exist->nmirrors >= BTRFS_NUM_MIRRORS);
125                                 exist->devices[exist->nmirrors] = device;
126                                 exist->offsets[exist->nmirrors] = offset;
127                                 exist->nmirrors++;
128                         }
129                         goto free_out;
130                 }
131                 remove_cache_extent(eb_cache, cache);
132                 free(exist);
133                 goto again;
134         }
135
136         rec->devices[0] = device;
137         rec->offsets[0] = offset;
138         rec->nmirrors++;
139         ret = insert_cache_extent(eb_cache, &rec->cache);
140         BUG_ON(ret);
141 out:
142         return ret;
143 free_out:
144         free(rec);
145         goto out;
146 }
147
148 static void free_extent_record(struct cache_extent *cache)
149 {
150         struct extent_record *er;
151
152         er = container_of(cache, struct extent_record, cache);
153         free(er);
154 }
155
156 FREE_EXTENT_CACHE_BASED_TREE(extent_record, free_extent_record);
157
158 static struct btrfs_chunk *create_chunk_item(struct chunk_record *record)
159 {
160         struct btrfs_chunk *ret;
161         struct btrfs_stripe *chunk_stripe;
162         int i;
163
164         if (!record || record->num_stripes == 0)
165                 return NULL;
166         ret = malloc(btrfs_chunk_item_size(record->num_stripes));
167         if (!ret)
168                 return NULL;
169         btrfs_set_stack_chunk_length(ret, record->length);
170         btrfs_set_stack_chunk_owner(ret, record->owner);
171         btrfs_set_stack_chunk_stripe_len(ret, record->stripe_len);
172         btrfs_set_stack_chunk_type(ret, record->type_flags);
173         btrfs_set_stack_chunk_io_align(ret, record->io_align);
174         btrfs_set_stack_chunk_io_width(ret, record->io_width);
175         btrfs_set_stack_chunk_sector_size(ret, record->sector_size);
176         btrfs_set_stack_chunk_num_stripes(ret, record->num_stripes);
177         btrfs_set_stack_chunk_sub_stripes(ret, record->sub_stripes);
178         for (i = 0, chunk_stripe = &ret->stripe; i < record->num_stripes;
179              i++, chunk_stripe++) {
180                 btrfs_set_stack_stripe_devid(chunk_stripe,
181                                 record->stripes[i].devid);
182                 btrfs_set_stack_stripe_offset(chunk_stripe,
183                                 record->stripes[i].offset);
184                 memcpy(chunk_stripe->dev_uuid, record->stripes[i].dev_uuid,
185                        BTRFS_UUID_SIZE);
186         }
187         return ret;
188 }
189
190 static void init_recover_control(struct recover_control *rc, int verbose,
191                 int yes)
192 {
193         memset(rc, 0, sizeof(struct recover_control));
194         cache_tree_init(&rc->chunk);
195         cache_tree_init(&rc->eb_cache);
196         block_group_tree_init(&rc->bg);
197         device_extent_tree_init(&rc->devext);
198
199         INIT_LIST_HEAD(&rc->good_chunks);
200         INIT_LIST_HEAD(&rc->bad_chunks);
201         INIT_LIST_HEAD(&rc->unrepaired_chunks);
202
203         rc->verbose = verbose;
204         rc->yes = yes;
205 }
206
207 static void free_recover_control(struct recover_control *rc)
208 {
209         free_block_group_tree(&rc->bg);
210         free_chunk_cache_tree(&rc->chunk);
211         free_device_extent_tree(&rc->devext);
212         free_extent_record_tree(&rc->eb_cache);
213 }
214
215 static int process_block_group_item(struct block_group_tree *bg_cache,
216                                     struct extent_buffer *leaf,
217                                     struct btrfs_key *key, int slot)
218 {
219         struct block_group_record *rec;
220         struct block_group_record *exist;
221         struct cache_extent *cache;
222         int ret = 0;
223
224         rec = btrfs_new_block_group_record(leaf, key, slot);
225         if (!rec->cache.size)
226                 goto free_out;
227 again:
228         cache = lookup_cache_extent(&bg_cache->tree,
229                                     rec->cache.start,
230                                     rec->cache.size);
231         if (cache) {
232                 exist = container_of(cache, struct block_group_record, cache);
233
234                 /*check the generation and replace if needed*/
235                 if (exist->generation > rec->generation)
236                         goto free_out;
237                 if (exist->generation == rec->generation) {
238                         int offset = offsetof(struct block_group_record,
239                                               generation);
240                         /*
241                          * According to the current kernel code, the following
242                          * case is impossble, or there is something wrong in
243                          * the kernel code.
244                          */
245                         if (memcmp(((void *)exist) + offset,
246                                    ((void *)rec) + offset,
247                                    sizeof(*rec) - offset))
248                                 ret = -EEXIST;
249                         goto free_out;
250                 }
251                 remove_cache_extent(&bg_cache->tree, cache);
252                 list_del_init(&exist->list);
253                 free(exist);
254                 /*
255                  * We must do seach again to avoid the following cache.
256                  * /--old bg 1--//--old bg 2--/
257                  *        /--new bg--/
258                  */
259                 goto again;
260         }
261
262         ret = insert_block_group_record(bg_cache, rec);
263         BUG_ON(ret);
264 out:
265         return ret;
266 free_out:
267         free(rec);
268         goto out;
269 }
270
271 static int process_chunk_item(struct cache_tree *chunk_cache,
272                               struct extent_buffer *leaf, struct btrfs_key *key,
273                               int slot)
274 {
275         struct chunk_record *rec;
276         struct chunk_record *exist;
277         struct cache_extent *cache;
278         int ret = 0;
279
280         rec = btrfs_new_chunk_record(leaf, key, slot);
281         if (!rec->cache.size)
282                 goto free_out;
283 again:
284         cache = lookup_cache_extent(chunk_cache, rec->offset, rec->length);
285         if (cache) {
286                 exist = container_of(cache, struct chunk_record, cache);
287
288                 if (exist->generation > rec->generation)
289                         goto free_out;
290                 if (exist->generation == rec->generation) {
291                         int num_stripes = rec->num_stripes;
292                         int rec_size = btrfs_chunk_record_size(num_stripes);
293                         int offset = offsetof(struct chunk_record, generation);
294
295                         if (exist->num_stripes != rec->num_stripes ||
296                             memcmp(((void *)exist) + offset,
297                                    ((void *)rec) + offset,
298                                    rec_size - offset))
299                                 ret = -EEXIST;
300                         goto free_out;
301                 }
302                 remove_cache_extent(chunk_cache, cache);
303                 free(exist);
304                 goto again;
305         }
306         ret = insert_cache_extent(chunk_cache, &rec->cache);
307         BUG_ON(ret);
308 out:
309         return ret;
310 free_out:
311         free(rec);
312         goto out;
313 }
314
315 static int process_device_extent_item(struct device_extent_tree *devext_cache,
316                                       struct extent_buffer *leaf,
317                                       struct btrfs_key *key, int slot)
318 {
319         struct device_extent_record *rec;
320         struct device_extent_record *exist;
321         struct cache_extent *cache;
322         int ret = 0;
323
324         rec = btrfs_new_device_extent_record(leaf, key, slot);
325         if (!rec->cache.size)
326                 goto free_out;
327 again:
328         cache = lookup_cache_extent2(&devext_cache->tree,
329                                      rec->cache.objectid,
330                                      rec->cache.start,
331                                      rec->cache.size);
332         if (cache) {
333                 exist = container_of(cache, struct device_extent_record, cache);
334                 if (exist->generation > rec->generation)
335                         goto free_out;
336                 if (exist->generation == rec->generation) {
337                         int offset = offsetof(struct device_extent_record,
338                                               generation);
339                         if (memcmp(((void *)exist) + offset,
340                                    ((void *)rec) + offset,
341                                    sizeof(*rec) - offset))
342                                 ret = -EEXIST;
343                         goto free_out;
344                 }
345                 remove_cache_extent(&devext_cache->tree, cache);
346                 list_del_init(&exist->chunk_list);
347                 list_del_init(&exist->device_list);
348                 free(exist);
349                 goto again;
350         }
351
352         ret = insert_device_extent_record(devext_cache, rec);
353         BUG_ON(ret);
354 out:
355         return ret;
356 free_out:
357         free(rec);
358         goto out;
359 }
360
361 static void print_block_group_info(struct block_group_record *rec, char *prefix)
362 {
363         if (prefix)
364                 printf("%s", prefix);
365         printf("Block Group: start = %llu, len = %llu, flag = %llx\n",
366                rec->objectid, rec->offset, rec->flags);
367 }
368
369 static void print_block_group_tree(struct block_group_tree *tree)
370 {
371         struct cache_extent *cache;
372         struct block_group_record *rec;
373
374         printf("All Block Groups:\n");
375         for (cache = first_cache_extent(&tree->tree); cache;
376              cache = next_cache_extent(cache)) {
377                 rec = container_of(cache, struct block_group_record, cache);
378                 print_block_group_info(rec, "\t");
379         }
380         printf("\n");
381 }
382
383 static void print_stripe_info(struct stripe *data, char *prefix1, char *prefix2,
384                               int index)
385 {
386         if (prefix1)
387                 printf("%s", prefix1);
388         if (prefix2)
389                 printf("%s", prefix2);
390         printf("[%2d] Stripe: devid = %llu, offset = %llu\n",
391                index, data->devid, data->offset);
392 }
393
394 static void print_chunk_self_info(struct chunk_record *rec, char *prefix)
395 {
396         int i;
397
398         if (prefix)
399                 printf("%s", prefix);
400         printf("Chunk: start = %llu, len = %llu, type = %llx, num_stripes = %u\n",
401                rec->offset, rec->length, rec->type_flags, rec->num_stripes);
402         if (prefix)
403                 printf("%s", prefix);
404         printf("    Stripes list:\n");
405         for (i = 0; i < rec->num_stripes; i++)
406                 print_stripe_info(&rec->stripes[i], prefix, "    ", i);
407 }
408
409 static void print_chunk_tree(struct cache_tree *tree)
410 {
411         struct cache_extent *n;
412         struct chunk_record *entry;
413
414         printf("All Chunks:\n");
415         for (n = first_cache_extent(tree); n;
416              n = next_cache_extent(n)) {
417                 entry = container_of(n, struct chunk_record, cache);
418                 print_chunk_self_info(entry, "\t");
419         }
420         printf("\n");
421 }
422
423 static void print_device_extent_info(struct device_extent_record *rec,
424                                      char *prefix)
425 {
426         if (prefix)
427                 printf("%s", prefix);
428         printf("Device extent: devid = %llu, start = %llu, len = %llu, chunk offset = %llu\n",
429                rec->objectid, rec->offset, rec->length, rec->chunk_offset);
430 }
431
432 static void print_device_extent_tree(struct device_extent_tree *tree)
433 {
434         struct cache_extent *n;
435         struct device_extent_record *entry;
436
437         printf("All Device Extents:\n");
438         for (n = first_cache_extent(&tree->tree); n;
439              n = next_cache_extent(n)) {
440                 entry = container_of(n, struct device_extent_record, cache);
441                 print_device_extent_info(entry, "\t");
442         }
443         printf("\n");
444 }
445
446 static void print_device_info(struct btrfs_device *device, char *prefix)
447 {
448         if (prefix)
449                 printf("%s", prefix);
450         printf("Device: id = %llu, name = %s\n",
451                device->devid, device->name);
452 }
453
454 static void print_all_devices(struct list_head *devices)
455 {
456         struct btrfs_device *dev;
457
458         printf("All Devices:\n");
459         list_for_each_entry(dev, devices, dev_list)
460                 print_device_info(dev, "\t");
461         printf("\n");
462 }
463
464 static void print_scan_result(struct recover_control *rc)
465 {
466         if (!rc->verbose)
467                 return;
468
469         printf("DEVICE SCAN RESULT:\n");
470         printf("Filesystem Information:\n");
471         printf("\tsectorsize: %d\n", rc->sectorsize);
472         printf("\tleafsize: %d\n", rc->leafsize);
473         printf("\ttree root generation: %llu\n", rc->generation);
474         printf("\tchunk root generation: %llu\n", rc->chunk_root_generation);
475         printf("\n");
476
477         print_all_devices(&rc->fs_devices->devices);
478         print_block_group_tree(&rc->bg);
479         print_chunk_tree(&rc->chunk);
480         print_device_extent_tree(&rc->devext);
481 }
482
483 static void print_chunk_info(struct chunk_record *chunk, char *prefix)
484 {
485         struct device_extent_record *devext;
486         int i;
487
488         print_chunk_self_info(chunk, prefix);
489         if (prefix)
490                 printf("%s", prefix);
491         if (chunk->bg_rec)
492                 print_block_group_info(chunk->bg_rec, "    ");
493         else
494                 printf("    No block group.\n");
495         if (prefix)
496                 printf("%s", prefix);
497         if (list_empty(&chunk->dextents)) {
498                 printf("    No device extent.\n");
499         } else {
500                 printf("    Device extent list:\n");
501                 i = 0;
502                 list_for_each_entry(devext, &chunk->dextents, chunk_list) {
503                         if (prefix)
504                                 printf("%s", prefix);
505                         printf("%s[%2d]", "        ", i);
506                         print_device_extent_info(devext, NULL);
507                         i++;
508                 }
509         }
510 }
511
512 static void print_check_result(struct recover_control *rc)
513 {
514         struct chunk_record *chunk;
515         struct block_group_record *bg;
516         struct device_extent_record *devext;
517         int total = 0;
518         int good = 0;
519         int bad = 0;
520
521         if (!rc->verbose)
522                 return;
523
524         printf("CHECK RESULT:\n");
525         printf("Healthy Chunks:\n");
526         list_for_each_entry(chunk, &rc->good_chunks, list) {
527                 print_chunk_info(chunk, "  ");
528                 good++;
529                 total++;
530         }
531         printf("Bad Chunks:\n");
532         list_for_each_entry(chunk, &rc->bad_chunks, list) {
533                 print_chunk_info(chunk, "  ");
534                 bad++;
535                 total++;
536         }
537         printf("\n");
538         printf("Total Chunks:\t%d\n", total);
539         printf("  Heathy:\t%d\n", good);
540         printf("  Bad:\t%d\n", bad);
541
542         printf("\n");
543         printf("Orphan Block Groups:\n");
544         list_for_each_entry(bg, &rc->bg.block_groups, list)
545                 print_block_group_info(bg, "  ");
546
547         printf("\n");
548         printf("Orphan Device Extents:\n");
549         list_for_each_entry(devext, &rc->devext.no_chunk_orphans, chunk_list)
550                 print_device_extent_info(devext, "  ");
551 }
552
553 static int check_chunk_by_metadata(struct recover_control *rc,
554                                    struct btrfs_root *root,
555                                    struct chunk_record *chunk, int bg_only)
556 {
557         int ret;
558         int i;
559         int slot;
560         struct btrfs_path path;
561         struct btrfs_key key;
562         struct btrfs_root *dev_root;
563         struct stripe *stripe;
564         struct btrfs_dev_extent *dev_extent;
565         struct btrfs_block_group_item *bg_ptr;
566         struct extent_buffer *l;
567
568         btrfs_init_path(&path);
569
570         if (bg_only)
571                 goto bg_check;
572
573         dev_root = root->fs_info->dev_root;
574         for (i = 0; i < chunk->num_stripes; i++) {
575                 stripe = &chunk->stripes[i];
576
577                 key.objectid = stripe->devid;
578                 key.offset = stripe->offset;
579                 key.type = BTRFS_DEV_EXTENT_KEY;
580
581                 ret = btrfs_search_slot(NULL, dev_root, &key, &path, 0, 0);
582                 if (ret < 0) {
583                         fprintf(stderr, "Search device extent failed(%d)\n",
584                                 ret);
585                         btrfs_release_path(&path);
586                         return ret;
587                 } else if (ret > 0) {
588                         if (rc->verbose)
589                                 fprintf(stderr,
590                                         "No device extent[%llu, %llu]\n",
591                                         stripe->devid, stripe->offset);
592                         btrfs_release_path(&path);
593                         return -ENOENT;
594                 }
595                 l = path.nodes[0];
596                 slot = path.slots[0];
597                 dev_extent = btrfs_item_ptr(l, slot, struct btrfs_dev_extent);
598                 if (chunk->offset !=
599                     btrfs_dev_extent_chunk_offset(l, dev_extent)) {
600                         if (rc->verbose)
601                                 fprintf(stderr,
602                                         "Device tree unmatch with chunks dev_extent[%llu, %llu], chunk[%llu, %llu]\n",
603                                         btrfs_dev_extent_chunk_offset(l,
604                                                                 dev_extent),
605                                         btrfs_dev_extent_length(l, dev_extent),
606                                         chunk->offset, chunk->length);
607                         btrfs_release_path(&path);
608                         return -ENOENT;
609                 }
610                 btrfs_release_path(&path);
611         }
612
613 bg_check:
614         key.objectid = chunk->offset;
615         key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
616         key.offset = chunk->length;
617
618         ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, &path,
619                                 0, 0);
620         if (ret < 0) {
621                 fprintf(stderr, "Search block group failed(%d)\n", ret);
622                 btrfs_release_path(&path);
623                 return ret;
624         } else if (ret > 0) {
625                 if (rc->verbose)
626                         fprintf(stderr, "No block group[%llu, %llu]\n",
627                                 key.objectid, key.offset);
628                 btrfs_release_path(&path);
629                 return -ENOENT;
630         }
631
632         l = path.nodes[0];
633         slot = path.slots[0];
634         bg_ptr = btrfs_item_ptr(l, slot, struct btrfs_block_group_item);
635         if (chunk->type_flags != btrfs_disk_block_group_flags(l, bg_ptr)) {
636                 if (rc->verbose)
637                         fprintf(stderr,
638                                 "Chunk[%llu, %llu]'s type(%llu) is differemt with Block Group's type(%llu)\n",
639                                 chunk->offset, chunk->length, chunk->type_flags,
640                                 btrfs_disk_block_group_flags(l, bg_ptr));
641                 btrfs_release_path(&path);
642                 return -ENOENT;
643         }
644         btrfs_release_path(&path);
645         return 0;
646 }
647
648 static int check_all_chunks_by_metadata(struct recover_control *rc,
649                                         struct btrfs_root *root)
650 {
651         struct chunk_record *chunk;
652         struct chunk_record *next;
653         LIST_HEAD(orphan_chunks);
654         int ret = 0;
655         int err;
656
657         list_for_each_entry_safe(chunk, next, &rc->good_chunks, list) {
658                 err = check_chunk_by_metadata(rc, root, chunk, 0);
659                 if (err) {
660                         if (err == -ENOENT)
661                                 list_move_tail(&chunk->list, &orphan_chunks);
662                         else if (err && !ret)
663                                 ret = err;
664                 }
665         }
666
667         list_for_each_entry_safe(chunk, next, &rc->unrepaired_chunks, list) {
668                 err = check_chunk_by_metadata(rc, root, chunk, 1);
669                 if (err == -ENOENT)
670                         list_move_tail(&chunk->list, &orphan_chunks);
671                 else if (err && !ret)
672                         ret = err;
673         }
674
675         list_for_each_entry(chunk, &rc->bad_chunks, list) {
676                 err = check_chunk_by_metadata(rc, root, chunk, 1);
677                 if (err != -ENOENT && !ret)
678                         ret = err ? err : -EINVAL;
679         }
680         list_splice(&orphan_chunks, &rc->bad_chunks);
681         return ret;
682 }
683
684 static int extract_metadata_record(struct recover_control *rc,
685                                    struct extent_buffer *leaf)
686 {
687         struct btrfs_key key;
688         int ret = 0;
689         int i;
690         u32 nritems;
691
692         nritems = btrfs_header_nritems(leaf);
693         for (i = 0; i < nritems; i++) {
694                 btrfs_item_key_to_cpu(leaf, &key, i);
695                 switch (key.type) {
696                 case BTRFS_BLOCK_GROUP_ITEM_KEY:
697                         ret = process_block_group_item(&rc->bg, leaf, &key, i);
698                         break;
699                 case BTRFS_CHUNK_ITEM_KEY:
700                         ret = process_chunk_item(&rc->chunk, leaf, &key, i);
701                         break;
702                 case BTRFS_DEV_EXTENT_KEY:
703                         ret = process_device_extent_item(&rc->devext, leaf,
704                                                          &key, i);
705                         break;
706                 }
707                 if (ret)
708                         break;
709         }
710         return ret;
711 }
712
713 static inline int is_super_block_address(u64 offset)
714 {
715         int i;
716
717         for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
718                 if (offset == btrfs_sb_offset(i))
719                         return 1;
720         }
721         return 0;
722 }
723
724 static int scan_one_device(struct recover_control *rc, int fd,
725                            struct btrfs_device *device)
726 {
727         struct extent_buffer *buf;
728         u64 bytenr;
729         int ret = 0;
730
731         buf = malloc(sizeof(*buf) + rc->leafsize);
732         if (!buf)
733                 return -ENOMEM;
734         buf->len = rc->leafsize;
735
736         bytenr = 0;
737         while (1) {
738                 if (is_super_block_address(bytenr))
739                         bytenr += rc->sectorsize;
740
741                 if (pread64(fd, buf->data, rc->leafsize, bytenr) <
742                     rc->leafsize)
743                         break;
744
745                 if (memcmp_extent_buffer(buf, rc->fs_devices->fsid,
746                                          (unsigned long)btrfs_header_fsid(buf),
747                                          BTRFS_FSID_SIZE)) {
748                         bytenr += rc->sectorsize;
749                         continue;
750                 }
751
752                 if (verify_tree_block_csum_silent(buf, rc->csum_size)) {
753                         bytenr += rc->sectorsize;
754                         continue;
755                 }
756
757                 ret = process_extent_buffer(&rc->eb_cache, buf, device, bytenr);
758                 if (ret)
759                         goto out;
760
761                 if (btrfs_header_level(buf) != 0)
762                         goto next_node;
763
764                 switch (btrfs_header_owner(buf)) {
765                 case BTRFS_EXTENT_TREE_OBJECTID:
766                 case BTRFS_DEV_TREE_OBJECTID:
767                         /* different tree use different generation */
768                         if (btrfs_header_generation(buf) > rc->generation)
769                                 break;
770                         ret = extract_metadata_record(rc, buf);
771                         if (ret)
772                                 goto out;
773                         break;
774                 case BTRFS_CHUNK_TREE_OBJECTID:
775                         if (btrfs_header_generation(buf) >
776                             rc->chunk_root_generation)
777                                 break;
778                         ret = extract_metadata_record(rc, buf);
779                         if (ret)
780                                 goto out;
781                         break;
782                 }
783 next_node:
784                 bytenr += rc->leafsize;
785         }
786 out:
787         free(buf);
788         return ret;
789 }
790
791 static int scan_devices(struct recover_control *rc)
792 {
793         int ret = 0;
794         int fd;
795         struct btrfs_device *dev;
796
797         list_for_each_entry(dev, &rc->fs_devices->devices, dev_list) {
798                 fd = open(dev->name, O_RDONLY);
799                 if (fd < 0) {
800                         fprintf(stderr, "Failed to open device %s\n",
801                                 dev->name);
802                         return -1;
803                 }
804                 ret = scan_one_device(rc, fd, dev);
805                 close(fd);
806                 if (ret)
807                         return ret;
808         }
809         return ret;
810 }
811
812 static int build_device_map_by_chunk_record(struct btrfs_root *root,
813                                             struct chunk_record *chunk)
814 {
815         int ret = 0;
816         int i;
817         u64 devid;
818         u8 uuid[BTRFS_UUID_SIZE];
819         u16 num_stripes;
820         struct btrfs_mapping_tree *map_tree;
821         struct map_lookup *map;
822         struct stripe *stripe;
823
824         map_tree = &root->fs_info->mapping_tree;
825         num_stripes = chunk->num_stripes;
826         map = malloc(btrfs_map_lookup_size(num_stripes));
827         if (!map)
828                 return -ENOMEM;
829         map->ce.start = chunk->offset;
830         map->ce.size = chunk->length;
831         map->num_stripes = num_stripes;
832         map->io_width = chunk->io_width;
833         map->io_align = chunk->io_align;
834         map->sector_size = chunk->sector_size;
835         map->stripe_len = chunk->stripe_len;
836         map->type = chunk->type_flags;
837         map->sub_stripes = chunk->sub_stripes;
838
839         for (i = 0, stripe = chunk->stripes; i < num_stripes; i++, stripe++) {
840                 devid = stripe->devid;
841                 memcpy(uuid, stripe->dev_uuid, BTRFS_UUID_SIZE);
842                 map->stripes[i].physical = stripe->offset;
843                 map->stripes[i].dev = btrfs_find_device(root, devid,
844                                                         uuid, NULL);
845                 if (!map->stripes[i].dev) {
846                         kfree(map);
847                         return -EIO;
848                 }
849         }
850
851         ret = insert_cache_extent(&map_tree->cache_tree, &map->ce);
852         return ret;
853 }
854
855 static int build_device_maps_by_chunk_records(struct recover_control *rc,
856                                               struct btrfs_root *root)
857 {
858         int ret = 0;
859         struct chunk_record *chunk;
860
861         list_for_each_entry(chunk, &rc->good_chunks, list) {
862                 ret = build_device_map_by_chunk_record(root, chunk);
863                 if (ret)
864                         return ret;
865         }
866         return ret;
867 }
868
869 static int block_group_remove_all_extent_items(struct btrfs_trans_handle *trans,
870                                                struct btrfs_root *root,
871                                                struct block_group_record *bg)
872 {
873         struct btrfs_fs_info *fs_info = root->fs_info;
874         struct btrfs_key key;
875         struct btrfs_path path;
876         struct extent_buffer *leaf;
877         u64 start = bg->objectid;
878         u64 end = bg->objectid + bg->offset;
879         u64 old_val;
880         int nitems;
881         int ret;
882         int i;
883         int del_s, del_nr;
884
885         btrfs_init_path(&path);
886         root = root->fs_info->extent_root;
887
888         key.objectid = start;
889         key.offset = 0;
890         key.type = BTRFS_EXTENT_ITEM_KEY;
891 again:
892         ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
893         if (ret < 0)
894                 goto err;
895         else if (ret > 0)
896                 ret = 0;
897
898         leaf = path.nodes[0];
899         nitems = btrfs_header_nritems(leaf);
900         if (!nitems) {
901                 /* The tree is empty. */
902                 ret = 0;
903                 goto err;
904         }
905
906         if (path.slots[0] >= nitems) {
907                 ret = btrfs_next_leaf(root, &path);
908                 if (ret < 0)
909                         goto err;
910                 if (ret > 0) {
911                         ret = 0;
912                         goto err;
913                 }
914                 leaf = path.nodes[0];
915                 btrfs_item_key_to_cpu(leaf, &key, 0);
916                 if (key.objectid >= end)
917                         goto err;
918                 btrfs_release_path(&path);
919                 goto again;
920         }
921
922         del_nr = 0;
923         del_s = -1;
924         for (i = path.slots[0]; i < nitems; i++) {
925                 btrfs_item_key_to_cpu(leaf, &key, i);
926                 if (key.objectid >= end)
927                         break;
928
929                 if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
930                         if (del_nr == 0)
931                                 continue;
932                         else
933                                 break;
934                 }
935
936                 if (del_s == -1)
937                         del_s = i;
938                 del_nr++;
939                 if (key.type == BTRFS_EXTENT_ITEM_KEY ||
940                     key.type == BTRFS_METADATA_ITEM_KEY) {
941                         old_val = btrfs_super_bytes_used(fs_info->super_copy);
942                         if (key.type == BTRFS_METADATA_ITEM_KEY)
943                                 old_val += root->leafsize;
944                         else
945                                 old_val += key.offset;
946                         btrfs_set_super_bytes_used(fs_info->super_copy,
947                                                    old_val);
948                 }
949         }
950
951         if (del_nr) {
952                 ret = btrfs_del_items(trans, root, &path, del_s, del_nr);
953                 if (ret)
954                         goto err;
955         }
956
957         if (key.objectid < end) {
958                 if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
959                         key.objectid += root->sectorsize;
960                         key.type = BTRFS_EXTENT_ITEM_KEY;
961                         key.offset = 0;
962                 }
963                 btrfs_release_path(&path);
964                 goto again;
965         }
966 err:
967         btrfs_release_path(&path);
968         return ret;
969 }
970
971 static int block_group_free_all_extent(struct btrfs_trans_handle *trans,
972                                        struct btrfs_root *root,
973                                        struct block_group_record *bg)
974 {
975         struct btrfs_block_group_cache *cache;
976         struct btrfs_fs_info *info;
977         u64 start;
978         u64 end;
979
980         info = root->fs_info;
981         cache = btrfs_lookup_block_group(info, bg->objectid);
982         if (!cache)
983                 return -ENOENT;
984
985         start = cache->key.objectid;
986         end = start + cache->key.offset - 1;
987
988         set_extent_bits(&info->block_group_cache, start, end,
989                         BLOCK_GROUP_DIRTY, GFP_NOFS);
990         set_extent_dirty(&info->free_space_cache, start, end, GFP_NOFS);
991
992         btrfs_set_block_group_used(&cache->item, 0);
993
994         return 0;
995 }
996
997 static int remove_chunk_extent_item(struct btrfs_trans_handle *trans,
998                                     struct recover_control *rc,
999                                     struct btrfs_root *root)
1000 {
1001         struct chunk_record *chunk;
1002         int ret = 0;
1003
1004         list_for_each_entry(chunk, &rc->good_chunks, list) {
1005                 if (!(chunk->type_flags & BTRFS_BLOCK_GROUP_SYSTEM))
1006                         continue;
1007                 ret = block_group_remove_all_extent_items(trans, root,
1008                                                           chunk->bg_rec);
1009                 if (ret)
1010                         return ret;
1011
1012                 ret = block_group_free_all_extent(trans, root, chunk->bg_rec);
1013                 if (ret)
1014                         return ret;
1015         }
1016         return ret;
1017 }
1018
1019 static int __rebuild_chunk_root(struct btrfs_trans_handle *trans,
1020                                 struct recover_control *rc,
1021                                 struct btrfs_root *root)
1022 {
1023         u64 min_devid = -1;
1024         struct btrfs_device *dev;
1025         struct extent_buffer *cow;
1026         struct btrfs_disk_key disk_key;
1027         int ret = 0;
1028
1029         list_for_each_entry(dev, &rc->fs_devices->devices, dev_list) {
1030                 if (min_devid > dev->devid)
1031                         min_devid = dev->devid;
1032         }
1033         disk_key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
1034         disk_key.type = BTRFS_DEV_ITEM_KEY;
1035         disk_key.offset = min_devid;
1036
1037         cow = btrfs_alloc_free_block(trans, root, root->sectorsize,
1038                                      BTRFS_CHUNK_TREE_OBJECTID,
1039                                      &disk_key, 0, 0, 0);
1040         btrfs_set_header_bytenr(cow, cow->start);
1041         btrfs_set_header_generation(cow, trans->transid);
1042         btrfs_set_header_nritems(cow, 0);
1043         btrfs_set_header_level(cow, 0);
1044         btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
1045         btrfs_set_header_owner(cow, BTRFS_CHUNK_TREE_OBJECTID);
1046         write_extent_buffer(cow, root->fs_info->fsid,
1047                         (unsigned long)btrfs_header_fsid(cow),
1048                         BTRFS_FSID_SIZE);
1049
1050         write_extent_buffer(cow, root->fs_info->chunk_tree_uuid,
1051                         (unsigned long)btrfs_header_chunk_tree_uuid(cow),
1052                         BTRFS_UUID_SIZE);
1053
1054         root->node = cow;
1055         btrfs_mark_buffer_dirty(cow);
1056
1057         return ret;
1058 }
1059
1060 static int __rebuild_device_items(struct btrfs_trans_handle *trans,
1061                                   struct recover_control *rc,
1062                                   struct btrfs_root *root)
1063 {
1064         struct btrfs_device *dev;
1065         struct btrfs_key key;
1066         struct btrfs_dev_item *dev_item;
1067         int ret = 0;
1068
1069         dev_item = malloc(sizeof(struct btrfs_dev_item));
1070         if (!dev_item)
1071                 return -ENOMEM;
1072
1073         list_for_each_entry(dev, &rc->fs_devices->devices, dev_list) {
1074                 key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
1075                 key.type = BTRFS_DEV_ITEM_KEY;
1076                 key.offset = dev->devid;
1077
1078                 btrfs_set_stack_device_generation(dev_item, 0);
1079                 btrfs_set_stack_device_type(dev_item, dev->type);
1080                 btrfs_set_stack_device_id(dev_item, dev->devid);
1081                 btrfs_set_stack_device_total_bytes(dev_item, dev->total_bytes);
1082                 btrfs_set_stack_device_bytes_used(dev_item, dev->bytes_used);
1083                 btrfs_set_stack_device_io_align(dev_item, dev->io_align);
1084                 btrfs_set_stack_device_io_width(dev_item, dev->io_width);
1085                 btrfs_set_stack_device_sector_size(dev_item, dev->sector_size);
1086                 memcpy(dev_item->uuid, dev->uuid, BTRFS_UUID_SIZE);
1087                 memcpy(dev_item->fsid, dev->fs_devices->fsid, BTRFS_UUID_SIZE);
1088
1089                 ret = btrfs_insert_item(trans, root, &key,
1090                                         dev_item, sizeof(*dev_item));
1091         }
1092
1093         free(dev_item);
1094         return ret;
1095 }
1096
1097 static int __rebuild_chunk_items(struct btrfs_trans_handle *trans,
1098                                  struct recover_control *rc,
1099                                  struct btrfs_root *root)
1100 {
1101         struct btrfs_key key;
1102         struct btrfs_chunk *chunk = NULL;
1103         struct btrfs_root *chunk_root;
1104         struct chunk_record *chunk_rec;
1105         int ret;
1106
1107         chunk_root = root->fs_info->chunk_root;
1108
1109         list_for_each_entry(chunk_rec, &rc->good_chunks, list) {
1110                 chunk = create_chunk_item(chunk_rec);
1111                 if (!chunk)
1112                         return -ENOMEM;
1113
1114                 key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
1115                 key.type = BTRFS_CHUNK_ITEM_KEY;
1116                 key.offset = chunk_rec->offset;
1117
1118                 ret = btrfs_insert_item(trans, chunk_root, &key, chunk,
1119                                 btrfs_chunk_item_size(chunk->num_stripes));
1120                 free(chunk);
1121                 if (ret)
1122                         return ret;
1123         }
1124         return 0;
1125 }
1126
1127 static int rebuild_chunk_tree(struct btrfs_trans_handle *trans,
1128                               struct recover_control *rc,
1129                               struct btrfs_root *root)
1130 {
1131         int ret = 0;
1132
1133         root = root->fs_info->chunk_root;
1134
1135         ret = __rebuild_chunk_root(trans, rc, root);
1136         if (ret)
1137                 return ret;
1138
1139         ret = __rebuild_device_items(trans, rc, root);
1140         if (ret)
1141                 return ret;
1142
1143         ret = __rebuild_chunk_items(trans, rc, root);
1144
1145         return ret;
1146 }
1147
1148 static int rebuild_sys_array(struct recover_control *rc,
1149                              struct btrfs_root *root)
1150 {
1151         struct btrfs_chunk *chunk;
1152         struct btrfs_key key;
1153         struct chunk_record *chunk_rec;
1154         int ret = 0;
1155         u16 num_stripes;
1156
1157         btrfs_set_super_sys_array_size(root->fs_info->super_copy, 0);
1158
1159         list_for_each_entry(chunk_rec, &rc->good_chunks, list) {
1160                 if (!(chunk_rec->type_flags & BTRFS_BLOCK_GROUP_SYSTEM))
1161                         continue;
1162
1163                 num_stripes = chunk_rec->num_stripes;
1164                 chunk = create_chunk_item(chunk_rec);
1165                 if (!chunk) {
1166                         ret = -ENOMEM;
1167                         break;
1168                 }
1169
1170                 key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
1171                 key.type = BTRFS_CHUNK_ITEM_KEY;
1172                 key.offset = chunk_rec->offset;
1173
1174                 ret = btrfs_add_system_chunk(NULL, root, &key, chunk,
1175                                 btrfs_chunk_item_size(num_stripes));
1176                 free(chunk);
1177                 if (ret)
1178                         break;
1179         }
1180         return ret;
1181
1182 }
1183
1184 static struct btrfs_root *
1185 open_ctree_with_broken_chunk(struct recover_control *rc)
1186 {
1187         struct btrfs_fs_info *fs_info;
1188         struct btrfs_super_block *disk_super;
1189         struct extent_buffer *eb;
1190         u32 sectorsize;
1191         u32 nodesize;
1192         u32 leafsize;
1193         u32 stripesize;
1194         int ret;
1195
1196         fs_info = btrfs_new_fs_info(1, BTRFS_SUPER_INFO_OFFSET);
1197         if (!fs_info) {
1198                 fprintf(stderr, "Failed to allocate memory for fs_info\n");
1199                 return ERR_PTR(-ENOMEM);
1200         }
1201
1202         fs_info->fs_devices = rc->fs_devices;
1203         ret = btrfs_open_devices(fs_info->fs_devices, O_RDWR);
1204         if (ret)
1205                 goto out;
1206
1207         disk_super = fs_info->super_copy;
1208         ret = btrfs_read_dev_super(fs_info->fs_devices->latest_bdev,
1209                                    disk_super, fs_info->super_bytenr);
1210         if (ret) {
1211                 fprintf(stderr, "No valid btrfs found\n");
1212                 goto out_devices;
1213         }
1214
1215         memcpy(fs_info->fsid, &disk_super->fsid, BTRFS_FSID_SIZE);
1216
1217         ret = btrfs_check_fs_compatibility(disk_super, 1);
1218         if (ret)
1219                 goto out_devices;
1220
1221         nodesize = btrfs_super_nodesize(disk_super);
1222         leafsize = btrfs_super_leafsize(disk_super);
1223         sectorsize = btrfs_super_sectorsize(disk_super);
1224         stripesize = btrfs_super_stripesize(disk_super);
1225
1226         __setup_root(nodesize, leafsize, sectorsize, stripesize,
1227                      fs_info->chunk_root, fs_info, BTRFS_CHUNK_TREE_OBJECTID);
1228
1229         ret = build_device_maps_by_chunk_records(rc, fs_info->chunk_root);
1230         if (ret)
1231                 goto out_cleanup;
1232
1233         ret = btrfs_setup_all_roots(fs_info, 0, 0);
1234         if (ret)
1235                 goto out_failed;
1236
1237         eb = fs_info->tree_root->node;
1238         read_extent_buffer(eb, fs_info->chunk_tree_uuid,
1239                            (unsigned long)btrfs_header_chunk_tree_uuid(eb),
1240                            BTRFS_UUID_SIZE);
1241
1242         return fs_info->fs_root;
1243 out_failed:
1244         btrfs_release_all_roots(fs_info);
1245 out_cleanup:
1246         btrfs_cleanup_all_caches(fs_info);
1247 out_devices:
1248         btrfs_close_devices(fs_info->fs_devices);
1249 out:
1250         btrfs_free_fs_info(fs_info);
1251         return ERR_PTR(ret);
1252 }
1253
1254 static int recover_prepare(struct recover_control *rc, char *path)
1255 {
1256         int ret;
1257         int fd;
1258         struct btrfs_super_block *sb;
1259         struct btrfs_fs_devices *fs_devices;
1260
1261         ret = 0;
1262         fd = open(path, O_RDONLY);
1263         if (fd < 0) {
1264                 fprintf(stderr, "open %s\n error.\n", path);
1265                 return -1;
1266         }
1267
1268         sb = malloc(sizeof(struct btrfs_super_block));
1269         if (!sb) {
1270                 fprintf(stderr, "allocating memory for sb failed.\n");
1271                 ret = -ENOMEM;
1272                 goto fail_close_fd;
1273         }
1274
1275         ret = btrfs_read_dev_super(fd, sb, BTRFS_SUPER_INFO_OFFSET);
1276         if (ret) {
1277                 fprintf(stderr, "read super block error\n");
1278                 goto fail_free_sb;
1279         }
1280
1281         rc->sectorsize = btrfs_super_sectorsize(sb);
1282         rc->leafsize = btrfs_super_leafsize(sb);
1283         rc->generation = btrfs_super_generation(sb);
1284         rc->chunk_root_generation = btrfs_super_chunk_root_generation(sb);
1285         rc->csum_size = btrfs_super_csum_size(sb);
1286
1287         /* if seed, the result of scanning below will be partial */
1288         if (btrfs_super_flags(sb) & BTRFS_SUPER_FLAG_SEEDING) {
1289                 fprintf(stderr, "this device is seed device\n");
1290                 ret = -1;
1291                 goto fail_free_sb;
1292         }
1293
1294         ret = btrfs_scan_fs_devices(fd, path, &fs_devices, 0, 1);
1295         if (ret)
1296                 goto fail_free_sb;
1297
1298         rc->fs_devices = fs_devices;
1299
1300         if (rc->verbose)
1301                 print_all_devices(&rc->fs_devices->devices);
1302
1303 fail_free_sb:
1304         free(sb);
1305 fail_close_fd:
1306         close(fd);
1307         return ret;
1308 }
1309
1310 /*
1311  * This reads a line from the stdin and only returns non-zero if the
1312  * first whitespace delimited token is a case insensitive match with yes
1313  * or y.
1314  */
1315 static int ask_user(char *question)
1316 {
1317         char buf[30] = {0,};
1318         char *saveptr = NULL;
1319         char *answer;
1320
1321         printf("%s [y/N]: ", question);
1322
1323         return fgets(buf, sizeof(buf) - 1, stdin) &&
1324                (answer = strtok_r(buf, " \t\n\r", &saveptr)) &&
1325                (!strcasecmp(answer, "yes") || !strcasecmp(answer, "y"));
1326 }
1327
1328 static int btrfs_get_device_extents(u64 chunk_object,
1329                                     struct list_head *orphan_devexts,
1330                                     struct list_head *ret_list)
1331 {
1332         struct device_extent_record *devext;
1333         struct device_extent_record *next;
1334         int count = 0;
1335
1336         list_for_each_entry_safe(devext, next, orphan_devexts, chunk_list) {
1337                 if (devext->chunk_offset == chunk_object) {
1338                         list_move_tail(&devext->chunk_list, ret_list);
1339                         count++;
1340                 }
1341         }
1342         return count;
1343 }
1344
1345 static int calc_num_stripes(u64 type)
1346 {
1347         if (type & (BTRFS_BLOCK_GROUP_RAID0 |
1348                     BTRFS_BLOCK_GROUP_RAID10 |
1349                     BTRFS_BLOCK_GROUP_RAID5 |
1350                     BTRFS_BLOCK_GROUP_RAID6))
1351                 return 0;
1352         else if (type & (BTRFS_BLOCK_GROUP_RAID1 |
1353                          BTRFS_BLOCK_GROUP_DUP))
1354                 return 2;
1355         else
1356                 return 1;
1357 }
1358
1359 static inline int calc_sub_nstripes(u64 type)
1360 {
1361         if (type & BTRFS_BLOCK_GROUP_RAID10)
1362                 return 2;
1363         else
1364                 return 1;
1365 }
1366
1367 static int btrfs_verify_device_extents(struct block_group_record *bg,
1368                                        struct list_head *devexts, int ndevexts)
1369 {
1370         struct device_extent_record *devext;
1371         u64 strpie_length;
1372         int expected_num_stripes;
1373
1374         expected_num_stripes = calc_num_stripes(bg->flags);
1375         if (expected_num_stripes && expected_num_stripes != ndevexts)
1376                 return 1;
1377
1378         strpie_length = calc_stripe_length(bg->flags, bg->offset, ndevexts);
1379         list_for_each_entry(devext, devexts, chunk_list) {
1380                 if (devext->length != strpie_length)
1381                         return 1;
1382         }
1383         return 0;
1384 }
1385
1386 static int btrfs_rebuild_unordered_chunk_stripes(struct recover_control *rc,
1387                                                  struct chunk_record *chunk)
1388 {
1389         struct device_extent_record *devext;
1390         struct btrfs_device *device;
1391         int i;
1392
1393         devext = list_first_entry(&chunk->dextents, struct device_extent_record,
1394                                   chunk_list);
1395         for (i = 0; i < chunk->num_stripes; i++) {
1396                 chunk->stripes[i].devid = devext->objectid;
1397                 chunk->stripes[i].offset = devext->offset;
1398                 device = btrfs_find_device_by_devid(rc->fs_devices,
1399                                                     devext->objectid,
1400                                                     0);
1401                 if (!device)
1402                         return -ENOENT;
1403                 BUG_ON(btrfs_find_device_by_devid(rc->fs_devices,
1404                                                   devext->objectid,
1405                                                   1));
1406                 memcpy(chunk->stripes[i].dev_uuid, device->uuid,
1407                        BTRFS_UUID_SIZE);
1408                 devext = list_next_entry(devext, chunk_list);
1409         }
1410         return 0;
1411 }
1412
1413 static int btrfs_calc_stripe_index(struct chunk_record *chunk, u64 logical)
1414 {
1415         u64 offset = logical - chunk->offset;
1416         int stripe_nr;
1417         int nr_data_stripes;
1418         int index;
1419
1420         stripe_nr = offset / chunk->stripe_len;
1421         if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID0) {
1422                 index = stripe_nr % chunk->num_stripes;
1423         } else if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID10) {
1424                 index = stripe_nr % (chunk->num_stripes / chunk->sub_stripes);
1425                 index *= chunk->sub_stripes;
1426         } else if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID5) {
1427                 nr_data_stripes = chunk->num_stripes - 1;
1428                 index = stripe_nr % nr_data_stripes;
1429                 stripe_nr /= nr_data_stripes;
1430                 index = (index + stripe_nr) % chunk->num_stripes;
1431         } else if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID6) {
1432                 nr_data_stripes = chunk->num_stripes - 2;
1433                 index = stripe_nr % nr_data_stripes;
1434                 stripe_nr /= nr_data_stripes;
1435                 index = (index + stripe_nr) % chunk->num_stripes;
1436         } else {
1437                 BUG_ON(1);
1438         }
1439         return index;
1440 }
1441
1442 /* calc the logical offset which is the start of the next stripe. */
1443 static inline u64 btrfs_next_stripe_logical_offset(struct chunk_record *chunk,
1444                                                    u64 logical)
1445 {
1446         u64 offset = logical - chunk->offset;
1447
1448         offset /= chunk->stripe_len;
1449         offset *= chunk->stripe_len;
1450         offset += chunk->stripe_len;
1451
1452         return offset + chunk->offset;
1453 }
1454
1455 static int is_extent_record_in_device_extent(struct extent_record *er,
1456                                              struct device_extent_record *dext,
1457                                              int *mirror)
1458 {
1459         int i;
1460
1461         for (i = 0; i < er->nmirrors; i++) {
1462                 if (er->devices[i]->devid == dext->objectid &&
1463                     er->offsets[i] >= dext->offset &&
1464                     er->offsets[i] < dext->offset + dext->length) {
1465                         *mirror = i;
1466                         return 1;
1467                 }
1468         }
1469         return 0;
1470 }
1471
1472 static int
1473 btrfs_rebuild_ordered_meta_chunk_stripes(struct recover_control *rc,
1474                                          struct chunk_record *chunk)
1475 {
1476         u64 start = chunk->offset;
1477         u64 end = chunk->offset + chunk->length;
1478         struct cache_extent *cache;
1479         struct extent_record *er;
1480         struct device_extent_record *devext;
1481         struct device_extent_record *next;
1482         struct btrfs_device *device;
1483         LIST_HEAD(devexts);
1484         int index;
1485         int mirror;
1486         int ret;
1487
1488         cache = lookup_cache_extent(&rc->eb_cache,
1489                                     start, chunk->length);
1490         if (!cache) {
1491                 /* No used space, we can reorder the stripes freely. */
1492                 ret = btrfs_rebuild_unordered_chunk_stripes(rc, chunk);
1493                 return ret;
1494         }
1495
1496         list_splice_init(&chunk->dextents, &devexts);
1497 again:
1498         er = container_of(cache, struct extent_record, cache);
1499         index = btrfs_calc_stripe_index(chunk, er->cache.start);
1500         if (chunk->stripes[index].devid)
1501                 goto next;
1502         list_for_each_entry_safe(devext, next, &devexts, chunk_list) {
1503                 if (is_extent_record_in_device_extent(er, devext, &mirror)) {
1504                         chunk->stripes[index].devid = devext->objectid;
1505                         chunk->stripes[index].offset = devext->offset;
1506                         memcpy(chunk->stripes[index].dev_uuid,
1507                                er->devices[mirror]->uuid,
1508                                BTRFS_UUID_SIZE);
1509                         index++;
1510                         list_move(&devext->chunk_list, &chunk->dextents);
1511                 }
1512         }
1513 next:
1514         start = btrfs_next_stripe_logical_offset(chunk, er->cache.start);
1515         if (start >= end)
1516                 goto no_extent_record;
1517
1518         cache = lookup_cache_extent(&rc->eb_cache, start, end - start);
1519         if (cache)
1520                 goto again;
1521 no_extent_record:
1522         if (list_empty(&devexts))
1523                 return 0;
1524
1525         if (chunk->type_flags & (BTRFS_BLOCK_GROUP_RAID5 |
1526                                  BTRFS_BLOCK_GROUP_RAID6)) {
1527                 /* Fixme: try to recover the order by the parity block. */
1528                 list_splice_tail(&devexts, &chunk->dextents);
1529                 return -EINVAL;
1530         }
1531
1532         /* There is no data on the lost stripes, we can reorder them freely. */
1533         for (index = 0; index < chunk->num_stripes; index++) {
1534                 if (chunk->stripes[index].devid)
1535                         continue;
1536
1537                 devext = list_first_entry(&devexts,
1538                                           struct device_extent_record,
1539                                            chunk_list);
1540                 list_move(&devext->chunk_list, &chunk->dextents);
1541
1542                 chunk->stripes[index].devid = devext->objectid;
1543                 chunk->stripes[index].offset = devext->offset;
1544                 device = btrfs_find_device_by_devid(rc->fs_devices,
1545                                                     devext->objectid,
1546                                                     0);
1547                 if (!device) {
1548                         list_splice_tail(&devexts, &chunk->dextents);
1549                         return -EINVAL;
1550                 }
1551                 BUG_ON(btrfs_find_device_by_devid(rc->fs_devices,
1552                                                   devext->objectid,
1553                                                   1));
1554                 memcpy(chunk->stripes[index].dev_uuid, device->uuid,
1555                        BTRFS_UUID_SIZE);
1556         }
1557         return 0;
1558 }
1559
1560 #define BTRFS_ORDERED_RAID      (BTRFS_BLOCK_GROUP_RAID0 |      \
1561                                  BTRFS_BLOCK_GROUP_RAID10 |     \
1562                                  BTRFS_BLOCK_GROUP_RAID5 |      \
1563                                  BTRFS_BLOCK_GROUP_RAID6)
1564
1565 static int btrfs_rebuild_chunk_stripes(struct recover_control *rc,
1566                                        struct chunk_record *chunk)
1567 {
1568         int ret;
1569
1570         /*
1571          * All the data in the system metadata chunk will be dropped,
1572          * so we need not guarantee that the data is right or not, that
1573          * is we can reorder the stripes in the system metadata chunk.
1574          */
1575         if ((chunk->type_flags & BTRFS_BLOCK_GROUP_METADATA) &&
1576             (chunk->type_flags & BTRFS_ORDERED_RAID))
1577                 ret =btrfs_rebuild_ordered_meta_chunk_stripes(rc, chunk);
1578         else if ((chunk->type_flags & BTRFS_BLOCK_GROUP_DATA) &&
1579                  (chunk->type_flags & BTRFS_ORDERED_RAID))
1580                 ret = 1;        /* Be handled after the fs is opened. */
1581         else
1582                 ret = btrfs_rebuild_unordered_chunk_stripes(rc, chunk);
1583
1584         return ret;
1585 }
1586
1587 static int btrfs_recover_chunks(struct recover_control *rc)
1588 {
1589         struct chunk_record *chunk;
1590         struct block_group_record *bg;
1591         struct block_group_record *next;
1592         LIST_HEAD(new_chunks);
1593         LIST_HEAD(devexts);
1594         int nstripes;
1595         int ret;
1596
1597         /* create the chunk by block group */
1598         list_for_each_entry_safe(bg, next, &rc->bg.block_groups, list) {
1599                 nstripes = btrfs_get_device_extents(bg->objectid,
1600                                                     &rc->devext.no_chunk_orphans,
1601                                                     &devexts);
1602                 chunk = malloc(btrfs_chunk_record_size(nstripes));
1603                 if (!chunk)
1604                         return -ENOMEM;
1605                 memset(chunk, 0, btrfs_chunk_record_size(nstripes));
1606                 INIT_LIST_HEAD(&chunk->dextents);
1607                 chunk->bg_rec = bg;
1608                 chunk->cache.start = bg->objectid;
1609                 chunk->cache.size = bg->offset;
1610                 chunk->objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
1611                 chunk->type = BTRFS_CHUNK_ITEM_KEY;
1612                 chunk->offset = bg->objectid;
1613                 chunk->generation = bg->generation;
1614                 chunk->length = bg->offset;
1615                 chunk->owner = BTRFS_CHUNK_TREE_OBJECTID;
1616                 chunk->stripe_len = BTRFS_STRIPE_LEN;
1617                 chunk->type_flags = bg->flags;
1618                 chunk->io_width = BTRFS_STRIPE_LEN;
1619                 chunk->io_align = BTRFS_STRIPE_LEN;
1620                 chunk->sector_size = rc->sectorsize;
1621                 chunk->sub_stripes = calc_sub_nstripes(bg->flags);
1622
1623                 ret = insert_cache_extent(&rc->chunk, &chunk->cache);
1624                 BUG_ON(ret);
1625
1626                 if (!nstripes) {
1627                         list_add_tail(&chunk->list, &rc->bad_chunks);
1628                         continue;
1629                 }
1630
1631                 list_splice_init(&devexts, &chunk->dextents);
1632
1633                 ret = btrfs_verify_device_extents(bg, &devexts, nstripes);
1634                 if (ret) {
1635                         list_add_tail(&chunk->list, &rc->bad_chunks);
1636                         continue;
1637                 }
1638
1639                 chunk->num_stripes = nstripes;
1640                 ret = btrfs_rebuild_chunk_stripes(rc, chunk);
1641                 if (ret > 0)
1642                         list_add_tail(&chunk->list, &rc->unrepaired_chunks);
1643                 else if (ret < 0)
1644                         list_add_tail(&chunk->list, &rc->bad_chunks);
1645                 else
1646                         list_add_tail(&chunk->list, &rc->good_chunks);
1647         }
1648         /*
1649          * Don't worry about the lost orphan device extents, they don't
1650          * have its chunk and block group, they must be the old ones that
1651          * we have dropped.
1652          */
1653         return 0;
1654 }
1655
1656 /*
1657  * Return 0 when succesful, < 0 on error and > 0 if aborted by user
1658  */
1659 int btrfs_recover_chunk_tree(char *path, int verbose, int yes)
1660 {
1661         int ret = 0;
1662         struct btrfs_root *root = NULL;
1663         struct btrfs_trans_handle *trans;
1664         struct recover_control rc;
1665
1666         init_recover_control(&rc, verbose, yes);
1667
1668         ret = recover_prepare(&rc, path);
1669         if (ret) {
1670                 fprintf(stderr, "recover prepare error\n");
1671                 return ret;
1672         }
1673
1674         ret = scan_devices(&rc);
1675         if (ret) {
1676                 fprintf(stderr, "scan chunk headers error\n");
1677                 goto fail_rc;
1678         }
1679
1680         if (cache_tree_empty(&rc.chunk) &&
1681             cache_tree_empty(&rc.bg.tree) &&
1682             cache_tree_empty(&rc.devext.tree)) {
1683                 fprintf(stderr, "no recoverable chunk\n");
1684                 goto fail_rc;
1685         }
1686
1687         print_scan_result(&rc);
1688
1689         ret = check_chunks(&rc.chunk, &rc.bg, &rc.devext, &rc.good_chunks,
1690                            &rc.bad_chunks, 1);
1691         print_check_result(&rc);
1692         if (ret) {
1693                 if (!list_empty(&rc.bg.block_groups) ||
1694                     !list_empty(&rc.devext.no_chunk_orphans)) {
1695                         ret = btrfs_recover_chunks(&rc);
1696                         if (ret)
1697                                 goto fail_rc;
1698                 }
1699                 /*
1700                  * If the chunk is healthy, its block group item and device
1701                  * extent item should be written on the disks. So, it is very
1702                  * likely that the bad chunk is a old one that has been
1703                  * droppped from the fs. Don't deal with them now, we will
1704                  * check it after the fs is opened.
1705                  */
1706         }
1707
1708         root = open_ctree_with_broken_chunk(&rc);
1709         if (IS_ERR(root)) {
1710                 fprintf(stderr, "open with broken chunk error\n");
1711                 ret = PTR_ERR(root);
1712                 goto fail_rc;
1713         }
1714
1715         ret = check_all_chunks_by_metadata(&rc, root);
1716         if (ret) {
1717                 fprintf(stderr, "The chunks in memory can not match the metadata of the fs. Repair failed.\n");
1718                 goto fail_close_ctree;
1719         }
1720
1721         if (!rc.yes) {
1722                 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?");
1723                 if (!ret) {
1724                         ret = 1;
1725                         goto fail_close_ctree;
1726                 }
1727         }
1728
1729         trans = btrfs_start_transaction(root, 1);
1730         ret = remove_chunk_extent_item(trans, &rc, root);
1731         BUG_ON(ret);
1732
1733         ret = rebuild_chunk_tree(trans, &rc, root);
1734         BUG_ON(ret);
1735
1736         ret = rebuild_sys_array(&rc, root);
1737         BUG_ON(ret);
1738
1739         btrfs_commit_transaction(trans, root);
1740 fail_close_ctree:
1741         close_ctree(root);
1742 fail_rc:
1743         free_recover_control(&rc);
1744         return ret;
1745 }