2 * Copyright (C) 2013 Fujitsu. All rights reserved.
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.
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.
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.
18 #define _XOPEN_SOURCE 500
22 #include <stdio_ext.h>
24 #include <sys/types.h>
28 #include <uuid/uuid.h>
31 #include "kerncompat.h"
33 #include "radix-tree.h"
35 #include "extent-cache.h"
38 #include "transaction.h"
45 #define BTRFS_STRIPE_LEN (64 * 1024)
46 #define BTRFS_NUM_MIRRORS 2
48 struct recover_control {
56 u64 chunk_root_generation;
58 struct btrfs_fs_devices *fs_devices;
60 struct cache_tree chunk;
61 struct block_group_tree bg;
62 struct device_extent_tree devext;
63 struct cache_tree eb_cache;
65 struct list_head good_chunks;
66 struct list_head bad_chunks;
67 struct list_head unrepaired_chunks;
68 pthread_mutex_t rc_lock;
71 struct extent_record {
72 struct cache_extent cache;
74 u8 csum[BTRFS_CSUM_SIZE];
75 struct btrfs_device *devices[BTRFS_NUM_MIRRORS];
76 u64 offsets[BTRFS_NUM_MIRRORS];
81 struct recover_control *rc;
82 struct btrfs_device *dev;
86 static struct extent_record *btrfs_new_extent_record(struct extent_buffer *eb)
88 struct extent_record *rec;
90 rec = malloc(sizeof(*rec));
92 fprintf(stderr, "Fail to allocate memory for extent record.\n");
96 memset(rec, 0, sizeof(*rec));
97 rec->cache.start = btrfs_header_bytenr(eb);
98 rec->cache.size = eb->len;
99 rec->generation = btrfs_header_generation(eb);
100 read_extent_buffer(eb, rec->csum, (unsigned long)btrfs_header_csum(eb),
105 static int process_extent_buffer(struct cache_tree *eb_cache,
106 struct extent_buffer *eb,
107 struct btrfs_device *device, u64 offset)
109 struct extent_record *rec;
110 struct extent_record *exist;
111 struct cache_extent *cache;
114 rec = btrfs_new_extent_record(eb);
115 if (!rec->cache.size)
118 cache = lookup_cache_extent(eb_cache,
122 exist = container_of(cache, struct extent_record, cache);
124 if (exist->generation > rec->generation)
126 if (exist->generation == rec->generation) {
127 if (exist->cache.start != rec->cache.start ||
128 exist->cache.size != rec->cache.size ||
129 memcmp(exist->csum, rec->csum, BTRFS_CSUM_SIZE)) {
132 BUG_ON(exist->nmirrors >= BTRFS_NUM_MIRRORS);
133 exist->devices[exist->nmirrors] = device;
134 exist->offsets[exist->nmirrors] = offset;
139 remove_cache_extent(eb_cache, cache);
144 rec->devices[0] = device;
145 rec->offsets[0] = offset;
147 ret = insert_cache_extent(eb_cache, &rec->cache);
156 static void free_extent_record(struct cache_extent *cache)
158 struct extent_record *er;
160 er = container_of(cache, struct extent_record, cache);
164 FREE_EXTENT_CACHE_BASED_TREE(extent_record, free_extent_record);
166 static struct btrfs_chunk *create_chunk_item(struct chunk_record *record)
168 struct btrfs_chunk *ret;
169 struct btrfs_stripe *chunk_stripe;
172 if (!record || record->num_stripes == 0)
174 ret = malloc(btrfs_chunk_item_size(record->num_stripes));
177 btrfs_set_stack_chunk_length(ret, record->length);
178 btrfs_set_stack_chunk_owner(ret, record->owner);
179 btrfs_set_stack_chunk_stripe_len(ret, record->stripe_len);
180 btrfs_set_stack_chunk_type(ret, record->type_flags);
181 btrfs_set_stack_chunk_io_align(ret, record->io_align);
182 btrfs_set_stack_chunk_io_width(ret, record->io_width);
183 btrfs_set_stack_chunk_sector_size(ret, record->sector_size);
184 btrfs_set_stack_chunk_num_stripes(ret, record->num_stripes);
185 btrfs_set_stack_chunk_sub_stripes(ret, record->sub_stripes);
186 for (i = 0, chunk_stripe = &ret->stripe; i < record->num_stripes;
187 i++, chunk_stripe++) {
188 btrfs_set_stack_stripe_devid(chunk_stripe,
189 record->stripes[i].devid);
190 btrfs_set_stack_stripe_offset(chunk_stripe,
191 record->stripes[i].offset);
192 memcpy(chunk_stripe->dev_uuid, record->stripes[i].dev_uuid,
198 static void init_recover_control(struct recover_control *rc, int verbose,
201 memset(rc, 0, sizeof(struct recover_control));
202 cache_tree_init(&rc->chunk);
203 cache_tree_init(&rc->eb_cache);
204 block_group_tree_init(&rc->bg);
205 device_extent_tree_init(&rc->devext);
207 INIT_LIST_HEAD(&rc->good_chunks);
208 INIT_LIST_HEAD(&rc->bad_chunks);
209 INIT_LIST_HEAD(&rc->unrepaired_chunks);
211 rc->verbose = verbose;
213 pthread_mutex_init(&rc->rc_lock, NULL);
216 static void free_recover_control(struct recover_control *rc)
218 free_block_group_tree(&rc->bg);
219 free_chunk_cache_tree(&rc->chunk);
220 free_device_extent_tree(&rc->devext);
221 free_extent_record_tree(&rc->eb_cache);
222 pthread_mutex_destroy(&rc->rc_lock);
225 static int process_block_group_item(struct block_group_tree *bg_cache,
226 struct extent_buffer *leaf,
227 struct btrfs_key *key, int slot)
229 struct block_group_record *rec;
230 struct block_group_record *exist;
231 struct cache_extent *cache;
234 rec = btrfs_new_block_group_record(leaf, key, slot);
235 if (!rec->cache.size)
238 cache = lookup_cache_extent(&bg_cache->tree,
242 exist = container_of(cache, struct block_group_record, cache);
244 /*check the generation and replace if needed*/
245 if (exist->generation > rec->generation)
247 if (exist->generation == rec->generation) {
248 int offset = offsetof(struct block_group_record,
251 * According to the current kernel code, the following
252 * case is impossble, or there is something wrong in
255 if (memcmp(((void *)exist) + offset,
256 ((void *)rec) + offset,
257 sizeof(*rec) - offset))
261 remove_cache_extent(&bg_cache->tree, cache);
262 list_del_init(&exist->list);
265 * We must do seach again to avoid the following cache.
266 * /--old bg 1--//--old bg 2--/
272 ret = insert_block_group_record(bg_cache, rec);
281 static int process_chunk_item(struct cache_tree *chunk_cache,
282 struct extent_buffer *leaf, struct btrfs_key *key,
285 struct chunk_record *rec;
286 struct chunk_record *exist;
287 struct cache_extent *cache;
290 rec = btrfs_new_chunk_record(leaf, key, slot);
291 if (!rec->cache.size)
294 cache = lookup_cache_extent(chunk_cache, rec->offset, rec->length);
296 exist = container_of(cache, struct chunk_record, cache);
298 if (exist->generation > rec->generation)
300 if (exist->generation == rec->generation) {
301 int num_stripes = rec->num_stripes;
302 int rec_size = btrfs_chunk_record_size(num_stripes);
303 int offset = offsetof(struct chunk_record, generation);
305 if (exist->num_stripes != rec->num_stripes ||
306 memcmp(((void *)exist) + offset,
307 ((void *)rec) + offset,
312 remove_cache_extent(chunk_cache, cache);
316 ret = insert_cache_extent(chunk_cache, &rec->cache);
325 static int process_device_extent_item(struct device_extent_tree *devext_cache,
326 struct extent_buffer *leaf,
327 struct btrfs_key *key, int slot)
329 struct device_extent_record *rec;
330 struct device_extent_record *exist;
331 struct cache_extent *cache;
334 rec = btrfs_new_device_extent_record(leaf, key, slot);
335 if (!rec->cache.size)
338 cache = lookup_cache_extent2(&devext_cache->tree,
343 exist = container_of(cache, struct device_extent_record, cache);
344 if (exist->generation > rec->generation)
346 if (exist->generation == rec->generation) {
347 int offset = offsetof(struct device_extent_record,
349 if (memcmp(((void *)exist) + offset,
350 ((void *)rec) + offset,
351 sizeof(*rec) - offset))
355 remove_cache_extent(&devext_cache->tree, cache);
356 list_del_init(&exist->chunk_list);
357 list_del_init(&exist->device_list);
362 ret = insert_device_extent_record(devext_cache, rec);
371 static void print_block_group_info(struct block_group_record *rec, char *prefix)
374 printf("%s", prefix);
375 printf("Block Group: start = %llu, len = %llu, flag = %llx\n",
376 rec->objectid, rec->offset, rec->flags);
379 static void print_block_group_tree(struct block_group_tree *tree)
381 struct cache_extent *cache;
382 struct block_group_record *rec;
384 printf("All Block Groups:\n");
385 for (cache = first_cache_extent(&tree->tree); cache;
386 cache = next_cache_extent(cache)) {
387 rec = container_of(cache, struct block_group_record, cache);
388 print_block_group_info(rec, "\t");
393 static void print_stripe_info(struct stripe *data, char *prefix1, char *prefix2,
397 printf("%s", prefix1);
399 printf("%s", prefix2);
400 printf("[%2d] Stripe: devid = %llu, offset = %llu\n",
401 index, data->devid, data->offset);
404 static void print_chunk_self_info(struct chunk_record *rec, char *prefix)
409 printf("%s", prefix);
410 printf("Chunk: start = %llu, len = %llu, type = %llx, num_stripes = %u\n",
411 rec->offset, rec->length, rec->type_flags, rec->num_stripes);
413 printf("%s", prefix);
414 printf(" Stripes list:\n");
415 for (i = 0; i < rec->num_stripes; i++)
416 print_stripe_info(&rec->stripes[i], prefix, " ", i);
419 static void print_chunk_tree(struct cache_tree *tree)
421 struct cache_extent *n;
422 struct chunk_record *entry;
424 printf("All Chunks:\n");
425 for (n = first_cache_extent(tree); n;
426 n = next_cache_extent(n)) {
427 entry = container_of(n, struct chunk_record, cache);
428 print_chunk_self_info(entry, "\t");
433 static void print_device_extent_info(struct device_extent_record *rec,
437 printf("%s", prefix);
438 printf("Device extent: devid = %llu, start = %llu, len = %llu, chunk offset = %llu\n",
439 rec->objectid, rec->offset, rec->length, rec->chunk_offset);
442 static void print_device_extent_tree(struct device_extent_tree *tree)
444 struct cache_extent *n;
445 struct device_extent_record *entry;
447 printf("All Device Extents:\n");
448 for (n = first_cache_extent(&tree->tree); n;
449 n = next_cache_extent(n)) {
450 entry = container_of(n, struct device_extent_record, cache);
451 print_device_extent_info(entry, "\t");
456 static void print_device_info(struct btrfs_device *device, char *prefix)
459 printf("%s", prefix);
460 printf("Device: id = %llu, name = %s\n",
461 device->devid, device->name);
464 static void print_all_devices(struct list_head *devices)
466 struct btrfs_device *dev;
468 printf("All Devices:\n");
469 list_for_each_entry(dev, devices, dev_list)
470 print_device_info(dev, "\t");
474 static void print_scan_result(struct recover_control *rc)
479 printf("DEVICE SCAN RESULT:\n");
480 printf("Filesystem Information:\n");
481 printf("\tsectorsize: %d\n", rc->sectorsize);
482 printf("\tleafsize: %d\n", rc->leafsize);
483 printf("\ttree root generation: %llu\n", rc->generation);
484 printf("\tchunk root generation: %llu\n", rc->chunk_root_generation);
487 print_all_devices(&rc->fs_devices->devices);
488 print_block_group_tree(&rc->bg);
489 print_chunk_tree(&rc->chunk);
490 print_device_extent_tree(&rc->devext);
493 static void print_chunk_info(struct chunk_record *chunk, char *prefix)
495 struct device_extent_record *devext;
498 print_chunk_self_info(chunk, prefix);
500 printf("%s", prefix);
502 print_block_group_info(chunk->bg_rec, " ");
504 printf(" No block group.\n");
506 printf("%s", prefix);
507 if (list_empty(&chunk->dextents)) {
508 printf(" No device extent.\n");
510 printf(" Device extent list:\n");
512 list_for_each_entry(devext, &chunk->dextents, chunk_list) {
514 printf("%s", prefix);
515 printf("%s[%2d]", " ", i);
516 print_device_extent_info(devext, NULL);
522 static void print_check_result(struct recover_control *rc)
524 struct chunk_record *chunk;
525 struct block_group_record *bg;
526 struct device_extent_record *devext;
534 printf("CHECK RESULT:\n");
535 printf("Healthy Chunks:\n");
536 list_for_each_entry(chunk, &rc->good_chunks, list) {
537 print_chunk_info(chunk, " ");
541 printf("Bad Chunks:\n");
542 list_for_each_entry(chunk, &rc->bad_chunks, list) {
543 print_chunk_info(chunk, " ");
548 printf("Total Chunks:\t%d\n", total);
549 printf(" Heathy:\t%d\n", good);
550 printf(" Bad:\t%d\n", bad);
553 printf("Orphan Block Groups:\n");
554 list_for_each_entry(bg, &rc->bg.block_groups, list)
555 print_block_group_info(bg, " ");
558 printf("Orphan Device Extents:\n");
559 list_for_each_entry(devext, &rc->devext.no_chunk_orphans, chunk_list)
560 print_device_extent_info(devext, " ");
563 static int check_chunk_by_metadata(struct recover_control *rc,
564 struct btrfs_root *root,
565 struct chunk_record *chunk, int bg_only)
570 struct btrfs_path path;
571 struct btrfs_key key;
572 struct btrfs_root *dev_root;
573 struct stripe *stripe;
574 struct btrfs_dev_extent *dev_extent;
575 struct btrfs_block_group_item *bg_ptr;
576 struct extent_buffer *l;
578 btrfs_init_path(&path);
583 dev_root = root->fs_info->dev_root;
584 for (i = 0; i < chunk->num_stripes; i++) {
585 stripe = &chunk->stripes[i];
587 key.objectid = stripe->devid;
588 key.offset = stripe->offset;
589 key.type = BTRFS_DEV_EXTENT_KEY;
591 ret = btrfs_search_slot(NULL, dev_root, &key, &path, 0, 0);
593 fprintf(stderr, "Search device extent failed(%d)\n",
595 btrfs_release_path(&path);
597 } else if (ret > 0) {
600 "No device extent[%llu, %llu]\n",
601 stripe->devid, stripe->offset);
602 btrfs_release_path(&path);
606 slot = path.slots[0];
607 dev_extent = btrfs_item_ptr(l, slot, struct btrfs_dev_extent);
609 btrfs_dev_extent_chunk_offset(l, dev_extent)) {
612 "Device tree unmatch with chunks dev_extent[%llu, %llu], chunk[%llu, %llu]\n",
613 btrfs_dev_extent_chunk_offset(l,
615 btrfs_dev_extent_length(l, dev_extent),
616 chunk->offset, chunk->length);
617 btrfs_release_path(&path);
620 btrfs_release_path(&path);
624 key.objectid = chunk->offset;
625 key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
626 key.offset = chunk->length;
628 ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, &path,
631 fprintf(stderr, "Search block group failed(%d)\n", ret);
632 btrfs_release_path(&path);
634 } else if (ret > 0) {
636 fprintf(stderr, "No block group[%llu, %llu]\n",
637 key.objectid, key.offset);
638 btrfs_release_path(&path);
643 slot = path.slots[0];
644 bg_ptr = btrfs_item_ptr(l, slot, struct btrfs_block_group_item);
645 if (chunk->type_flags != btrfs_disk_block_group_flags(l, bg_ptr)) {
648 "Chunk[%llu, %llu]'s type(%llu) is differemt with Block Group's type(%llu)\n",
649 chunk->offset, chunk->length, chunk->type_flags,
650 btrfs_disk_block_group_flags(l, bg_ptr));
651 btrfs_release_path(&path);
654 btrfs_release_path(&path);
658 static int check_all_chunks_by_metadata(struct recover_control *rc,
659 struct btrfs_root *root)
661 struct chunk_record *chunk;
662 struct chunk_record *next;
663 LIST_HEAD(orphan_chunks);
667 list_for_each_entry_safe(chunk, next, &rc->good_chunks, list) {
668 err = check_chunk_by_metadata(rc, root, chunk, 0);
671 list_move_tail(&chunk->list, &orphan_chunks);
672 else if (err && !ret)
677 list_for_each_entry_safe(chunk, next, &rc->unrepaired_chunks, list) {
678 err = check_chunk_by_metadata(rc, root, chunk, 1);
680 list_move_tail(&chunk->list, &orphan_chunks);
681 else if (err && !ret)
685 list_for_each_entry(chunk, &rc->bad_chunks, list) {
686 err = check_chunk_by_metadata(rc, root, chunk, 1);
687 if (err != -ENOENT && !ret)
688 ret = err ? err : -EINVAL;
690 list_splice(&orphan_chunks, &rc->bad_chunks);
694 static int extract_metadata_record(struct recover_control *rc,
695 struct extent_buffer *leaf)
697 struct btrfs_key key;
702 nritems = btrfs_header_nritems(leaf);
703 for (i = 0; i < nritems; i++) {
704 btrfs_item_key_to_cpu(leaf, &key, i);
706 case BTRFS_BLOCK_GROUP_ITEM_KEY:
707 pthread_mutex_lock(&rc->rc_lock);
708 ret = process_block_group_item(&rc->bg, leaf, &key, i);
709 pthread_mutex_unlock(&rc->rc_lock);
711 case BTRFS_CHUNK_ITEM_KEY:
712 pthread_mutex_lock(&rc->rc_lock);
713 ret = process_chunk_item(&rc->chunk, leaf, &key, i);
714 pthread_mutex_unlock(&rc->rc_lock);
716 case BTRFS_DEV_EXTENT_KEY:
717 pthread_mutex_lock(&rc->rc_lock);
718 ret = process_device_extent_item(&rc->devext, leaf,
720 pthread_mutex_unlock(&rc->rc_lock);
729 static inline int is_super_block_address(u64 offset)
733 for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
734 if (offset == btrfs_sb_offset(i))
740 static int scan_one_device(void *dev_scan_struct)
742 struct extent_buffer *buf;
745 struct device_scan *dev_scan = (struct device_scan *)dev_scan_struct;
746 struct recover_control *rc = dev_scan->rc;
747 struct btrfs_device *device = dev_scan->dev;
748 int fd = dev_scan->fd;
750 ret = pthread_setcanceltype(PTHREAD_CANCEL_ASYNCHRONOUS, NULL);
754 buf = malloc(sizeof(*buf) + rc->leafsize);
757 buf->len = rc->leafsize;
761 if (is_super_block_address(bytenr))
762 bytenr += rc->sectorsize;
764 if (pread64(fd, buf->data, rc->leafsize, bytenr) <
768 if (memcmp_extent_buffer(buf, rc->fs_devices->fsid,
771 bytenr += rc->sectorsize;
775 if (verify_tree_block_csum_silent(buf, rc->csum_size)) {
776 bytenr += rc->sectorsize;
780 pthread_mutex_lock(&rc->rc_lock);
781 ret = process_extent_buffer(&rc->eb_cache, buf, device, bytenr);
782 pthread_mutex_unlock(&rc->rc_lock);
786 if (btrfs_header_level(buf) != 0)
789 switch (btrfs_header_owner(buf)) {
790 case BTRFS_EXTENT_TREE_OBJECTID:
791 case BTRFS_DEV_TREE_OBJECTID:
792 /* different tree use different generation */
793 if (btrfs_header_generation(buf) > rc->generation)
795 ret = extract_metadata_record(rc, buf);
799 case BTRFS_CHUNK_TREE_OBJECTID:
800 if (btrfs_header_generation(buf) >
801 rc->chunk_root_generation)
803 ret = extract_metadata_record(rc, buf);
809 bytenr += rc->leafsize;
817 static int scan_devices(struct recover_control *rc)
821 struct btrfs_device *dev;
822 struct device_scan *dev_scans;
831 list_for_each_entry(dev, &rc->fs_devices->devices, dev_list)
833 dev_scans = (struct device_scan *)malloc(sizeof(struct device_scan)
837 t_scans = (pthread_t *)malloc(sizeof(pthread_t) * devnr);
840 t_rets = (int *)malloc(sizeof(int) * devnr);
844 list_for_each_entry(dev, &rc->fs_devices->devices, dev_list) {
845 fd = open(dev->name, O_RDONLY);
847 fprintf(stderr, "Failed to open device %s\n",
851 dev_scans[devidx].rc = rc;
852 dev_scans[devidx].dev = dev;
853 dev_scans[devidx].fd = fd;
854 ret = pthread_create(&t_scans[devidx], NULL,
855 (void *)scan_one_device,
856 (void *)&dev_scans[devidx]);
859 cancel_to = devidx - 1;
867 ret = pthread_join(t_scans[i], (void **)&t_rets[i]);
868 if (ret || t_rets[i]) {
871 cancel_to = devnr - 1;
877 while (cancel_from <= cancel_to) {
878 pthread_cancel(t_scans[cancel_from]);
887 static int build_device_map_by_chunk_record(struct btrfs_root *root,
888 struct chunk_record *chunk)
893 u8 uuid[BTRFS_UUID_SIZE];
895 struct btrfs_mapping_tree *map_tree;
896 struct map_lookup *map;
897 struct stripe *stripe;
899 map_tree = &root->fs_info->mapping_tree;
900 num_stripes = chunk->num_stripes;
901 map = malloc(btrfs_map_lookup_size(num_stripes));
904 map->ce.start = chunk->offset;
905 map->ce.size = chunk->length;
906 map->num_stripes = num_stripes;
907 map->io_width = chunk->io_width;
908 map->io_align = chunk->io_align;
909 map->sector_size = chunk->sector_size;
910 map->stripe_len = chunk->stripe_len;
911 map->type = chunk->type_flags;
912 map->sub_stripes = chunk->sub_stripes;
914 for (i = 0, stripe = chunk->stripes; i < num_stripes; i++, stripe++) {
915 devid = stripe->devid;
916 memcpy(uuid, stripe->dev_uuid, BTRFS_UUID_SIZE);
917 map->stripes[i].physical = stripe->offset;
918 map->stripes[i].dev = btrfs_find_device(root, devid,
920 if (!map->stripes[i].dev) {
926 ret = insert_cache_extent(&map_tree->cache_tree, &map->ce);
930 static int build_device_maps_by_chunk_records(struct recover_control *rc,
931 struct btrfs_root *root)
934 struct chunk_record *chunk;
936 list_for_each_entry(chunk, &rc->good_chunks, list) {
937 ret = build_device_map_by_chunk_record(root, chunk);
944 static int block_group_remove_all_extent_items(struct btrfs_trans_handle *trans,
945 struct btrfs_root *root,
946 struct block_group_record *bg)
948 struct btrfs_fs_info *fs_info = root->fs_info;
949 struct btrfs_key key;
950 struct btrfs_path path;
951 struct extent_buffer *leaf;
952 u64 start = bg->objectid;
953 u64 end = bg->objectid + bg->offset;
960 btrfs_init_path(&path);
961 root = root->fs_info->extent_root;
963 key.objectid = start;
965 key.type = BTRFS_EXTENT_ITEM_KEY;
967 ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
973 leaf = path.nodes[0];
974 nitems = btrfs_header_nritems(leaf);
976 /* The tree is empty. */
981 if (path.slots[0] >= nitems) {
982 ret = btrfs_next_leaf(root, &path);
989 leaf = path.nodes[0];
990 btrfs_item_key_to_cpu(leaf, &key, 0);
991 if (key.objectid >= end)
993 btrfs_release_path(&path);
999 for (i = path.slots[0]; i < nitems; i++) {
1000 btrfs_item_key_to_cpu(leaf, &key, i);
1001 if (key.objectid >= end)
1004 if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
1014 if (key.type == BTRFS_EXTENT_ITEM_KEY ||
1015 key.type == BTRFS_METADATA_ITEM_KEY) {
1016 old_val = btrfs_super_bytes_used(fs_info->super_copy);
1017 if (key.type == BTRFS_METADATA_ITEM_KEY)
1018 old_val += root->leafsize;
1020 old_val += key.offset;
1021 btrfs_set_super_bytes_used(fs_info->super_copy,
1027 ret = btrfs_del_items(trans, root, &path, del_s, del_nr);
1032 if (key.objectid < end) {
1033 if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
1034 key.objectid += root->sectorsize;
1035 key.type = BTRFS_EXTENT_ITEM_KEY;
1038 btrfs_release_path(&path);
1042 btrfs_release_path(&path);
1046 static int block_group_free_all_extent(struct btrfs_trans_handle *trans,
1047 struct btrfs_root *root,
1048 struct block_group_record *bg)
1050 struct btrfs_block_group_cache *cache;
1051 struct btrfs_fs_info *info;
1055 info = root->fs_info;
1056 cache = btrfs_lookup_block_group(info, bg->objectid);
1060 start = cache->key.objectid;
1061 end = start + cache->key.offset - 1;
1063 set_extent_bits(&info->block_group_cache, start, end,
1064 BLOCK_GROUP_DIRTY, GFP_NOFS);
1065 set_extent_dirty(&info->free_space_cache, start, end, GFP_NOFS);
1067 btrfs_set_block_group_used(&cache->item, 0);
1072 static int remove_chunk_extent_item(struct btrfs_trans_handle *trans,
1073 struct recover_control *rc,
1074 struct btrfs_root *root)
1076 struct chunk_record *chunk;
1079 list_for_each_entry(chunk, &rc->good_chunks, list) {
1080 if (!(chunk->type_flags & BTRFS_BLOCK_GROUP_SYSTEM))
1082 ret = block_group_remove_all_extent_items(trans, root,
1087 ret = block_group_free_all_extent(trans, root, chunk->bg_rec);
1094 static int __rebuild_chunk_root(struct btrfs_trans_handle *trans,
1095 struct recover_control *rc,
1096 struct btrfs_root *root)
1099 struct btrfs_device *dev;
1100 struct extent_buffer *cow;
1101 struct btrfs_disk_key disk_key;
1104 list_for_each_entry(dev, &rc->fs_devices->devices, dev_list) {
1105 if (min_devid > dev->devid)
1106 min_devid = dev->devid;
1108 disk_key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
1109 disk_key.type = BTRFS_DEV_ITEM_KEY;
1110 disk_key.offset = min_devid;
1112 cow = btrfs_alloc_free_block(trans, root, root->nodesize,
1113 BTRFS_CHUNK_TREE_OBJECTID,
1114 &disk_key, 0, 0, 0);
1115 btrfs_set_header_bytenr(cow, cow->start);
1116 btrfs_set_header_generation(cow, trans->transid);
1117 btrfs_set_header_nritems(cow, 0);
1118 btrfs_set_header_level(cow, 0);
1119 btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
1120 btrfs_set_header_owner(cow, BTRFS_CHUNK_TREE_OBJECTID);
1121 write_extent_buffer(cow, root->fs_info->fsid,
1122 btrfs_header_fsid(), BTRFS_FSID_SIZE);
1124 write_extent_buffer(cow, root->fs_info->chunk_tree_uuid,
1125 btrfs_header_chunk_tree_uuid(cow),
1129 btrfs_mark_buffer_dirty(cow);
1134 static int __rebuild_device_items(struct btrfs_trans_handle *trans,
1135 struct recover_control *rc,
1136 struct btrfs_root *root)
1138 struct btrfs_device *dev;
1139 struct btrfs_key key;
1140 struct btrfs_dev_item *dev_item;
1143 dev_item = malloc(sizeof(struct btrfs_dev_item));
1147 list_for_each_entry(dev, &rc->fs_devices->devices, dev_list) {
1148 key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
1149 key.type = BTRFS_DEV_ITEM_KEY;
1150 key.offset = dev->devid;
1152 btrfs_set_stack_device_generation(dev_item, 0);
1153 btrfs_set_stack_device_type(dev_item, dev->type);
1154 btrfs_set_stack_device_id(dev_item, dev->devid);
1155 btrfs_set_stack_device_total_bytes(dev_item, dev->total_bytes);
1156 btrfs_set_stack_device_bytes_used(dev_item, dev->bytes_used);
1157 btrfs_set_stack_device_io_align(dev_item, dev->io_align);
1158 btrfs_set_stack_device_io_width(dev_item, dev->io_width);
1159 btrfs_set_stack_device_sector_size(dev_item, dev->sector_size);
1160 memcpy(dev_item->uuid, dev->uuid, BTRFS_UUID_SIZE);
1161 memcpy(dev_item->fsid, dev->fs_devices->fsid, BTRFS_UUID_SIZE);
1163 ret = btrfs_insert_item(trans, root, &key,
1164 dev_item, sizeof(*dev_item));
1171 static int __rebuild_chunk_items(struct btrfs_trans_handle *trans,
1172 struct recover_control *rc,
1173 struct btrfs_root *root)
1175 struct btrfs_key key;
1176 struct btrfs_chunk *chunk = NULL;
1177 struct btrfs_root *chunk_root;
1178 struct chunk_record *chunk_rec;
1181 chunk_root = root->fs_info->chunk_root;
1183 list_for_each_entry(chunk_rec, &rc->good_chunks, list) {
1184 chunk = create_chunk_item(chunk_rec);
1188 key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
1189 key.type = BTRFS_CHUNK_ITEM_KEY;
1190 key.offset = chunk_rec->offset;
1192 ret = btrfs_insert_item(trans, chunk_root, &key, chunk,
1193 btrfs_chunk_item_size(chunk->num_stripes));
1201 static int rebuild_chunk_tree(struct btrfs_trans_handle *trans,
1202 struct recover_control *rc,
1203 struct btrfs_root *root)
1207 root = root->fs_info->chunk_root;
1209 ret = __rebuild_chunk_root(trans, rc, root);
1213 ret = __rebuild_device_items(trans, rc, root);
1217 ret = __rebuild_chunk_items(trans, rc, root);
1222 static int rebuild_sys_array(struct recover_control *rc,
1223 struct btrfs_root *root)
1225 struct btrfs_chunk *chunk;
1226 struct btrfs_key key;
1227 struct chunk_record *chunk_rec;
1231 btrfs_set_super_sys_array_size(root->fs_info->super_copy, 0);
1233 list_for_each_entry(chunk_rec, &rc->good_chunks, list) {
1234 if (!(chunk_rec->type_flags & BTRFS_BLOCK_GROUP_SYSTEM))
1237 num_stripes = chunk_rec->num_stripes;
1238 chunk = create_chunk_item(chunk_rec);
1244 key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
1245 key.type = BTRFS_CHUNK_ITEM_KEY;
1246 key.offset = chunk_rec->offset;
1248 ret = btrfs_add_system_chunk(NULL, root, &key, chunk,
1249 btrfs_chunk_item_size(num_stripes));
1258 static struct btrfs_root *
1259 open_ctree_with_broken_chunk(struct recover_control *rc)
1261 struct btrfs_fs_info *fs_info;
1262 struct btrfs_super_block *disk_super;
1263 struct extent_buffer *eb;
1270 fs_info = btrfs_new_fs_info(1, BTRFS_SUPER_INFO_OFFSET);
1272 fprintf(stderr, "Failed to allocate memory for fs_info\n");
1273 return ERR_PTR(-ENOMEM);
1275 fs_info->is_chunk_recover = 1;
1277 fs_info->fs_devices = rc->fs_devices;
1278 ret = btrfs_open_devices(fs_info->fs_devices, O_RDWR);
1282 disk_super = fs_info->super_copy;
1283 ret = btrfs_read_dev_super(fs_info->fs_devices->latest_bdev,
1284 disk_super, fs_info->super_bytenr);
1286 fprintf(stderr, "No valid btrfs found\n");
1290 memcpy(fs_info->fsid, &disk_super->fsid, BTRFS_FSID_SIZE);
1292 ret = btrfs_check_fs_compatibility(disk_super, 1);
1296 nodesize = btrfs_super_nodesize(disk_super);
1297 leafsize = btrfs_super_leafsize(disk_super);
1298 sectorsize = btrfs_super_sectorsize(disk_super);
1299 stripesize = btrfs_super_stripesize(disk_super);
1301 __setup_root(nodesize, leafsize, sectorsize, stripesize,
1302 fs_info->chunk_root, fs_info, BTRFS_CHUNK_TREE_OBJECTID);
1304 ret = build_device_maps_by_chunk_records(rc, fs_info->chunk_root);
1308 ret = btrfs_setup_all_roots(fs_info, 0, 0);
1312 eb = fs_info->tree_root->node;
1313 read_extent_buffer(eb, fs_info->chunk_tree_uuid,
1314 btrfs_header_chunk_tree_uuid(eb),
1317 return fs_info->fs_root;
1319 btrfs_release_all_roots(fs_info);
1321 btrfs_cleanup_all_caches(fs_info);
1323 btrfs_close_devices(fs_info->fs_devices);
1325 btrfs_free_fs_info(fs_info);
1326 return ERR_PTR(ret);
1329 static int recover_prepare(struct recover_control *rc, char *path)
1333 struct btrfs_super_block *sb;
1334 struct btrfs_fs_devices *fs_devices;
1337 fd = open(path, O_RDONLY);
1339 fprintf(stderr, "open %s\n error.\n", path);
1343 sb = malloc(sizeof(struct btrfs_super_block));
1345 fprintf(stderr, "allocating memory for sb failed.\n");
1350 ret = btrfs_read_dev_super(fd, sb, BTRFS_SUPER_INFO_OFFSET);
1352 fprintf(stderr, "read super block error\n");
1356 rc->sectorsize = btrfs_super_sectorsize(sb);
1357 rc->leafsize = btrfs_super_leafsize(sb);
1358 rc->generation = btrfs_super_generation(sb);
1359 rc->chunk_root_generation = btrfs_super_chunk_root_generation(sb);
1360 rc->csum_size = btrfs_super_csum_size(sb);
1362 /* if seed, the result of scanning below will be partial */
1363 if (btrfs_super_flags(sb) & BTRFS_SUPER_FLAG_SEEDING) {
1364 fprintf(stderr, "this device is seed device\n");
1369 ret = btrfs_scan_fs_devices(fd, path, &fs_devices, 0, 1);
1373 rc->fs_devices = fs_devices;
1376 print_all_devices(&rc->fs_devices->devices);
1385 static int btrfs_get_device_extents(u64 chunk_object,
1386 struct list_head *orphan_devexts,
1387 struct list_head *ret_list)
1389 struct device_extent_record *devext;
1390 struct device_extent_record *next;
1393 list_for_each_entry_safe(devext, next, orphan_devexts, chunk_list) {
1394 if (devext->chunk_offset == chunk_object) {
1395 list_move_tail(&devext->chunk_list, ret_list);
1402 static int calc_num_stripes(u64 type)
1404 if (type & (BTRFS_BLOCK_GROUP_RAID0 |
1405 BTRFS_BLOCK_GROUP_RAID10 |
1406 BTRFS_BLOCK_GROUP_RAID5 |
1407 BTRFS_BLOCK_GROUP_RAID6))
1409 else if (type & (BTRFS_BLOCK_GROUP_RAID1 |
1410 BTRFS_BLOCK_GROUP_DUP))
1416 static inline int calc_sub_nstripes(u64 type)
1418 if (type & BTRFS_BLOCK_GROUP_RAID10)
1424 static int btrfs_verify_device_extents(struct block_group_record *bg,
1425 struct list_head *devexts, int ndevexts)
1427 struct device_extent_record *devext;
1429 int expected_num_stripes;
1431 expected_num_stripes = calc_num_stripes(bg->flags);
1432 if (expected_num_stripes && expected_num_stripes != ndevexts)
1435 strpie_length = calc_stripe_length(bg->flags, bg->offset, ndevexts);
1436 list_for_each_entry(devext, devexts, chunk_list) {
1437 if (devext->length != strpie_length)
1443 static int btrfs_rebuild_unordered_chunk_stripes(struct recover_control *rc,
1444 struct chunk_record *chunk)
1446 struct device_extent_record *devext;
1447 struct btrfs_device *device;
1450 devext = list_first_entry(&chunk->dextents, struct device_extent_record,
1452 for (i = 0; i < chunk->num_stripes; i++) {
1453 chunk->stripes[i].devid = devext->objectid;
1454 chunk->stripes[i].offset = devext->offset;
1455 device = btrfs_find_device_by_devid(rc->fs_devices,
1460 BUG_ON(btrfs_find_device_by_devid(rc->fs_devices,
1463 memcpy(chunk->stripes[i].dev_uuid, device->uuid,
1465 devext = list_next_entry(devext, chunk_list);
1470 static int btrfs_calc_stripe_index(struct chunk_record *chunk, u64 logical)
1472 u64 offset = logical - chunk->offset;
1474 int nr_data_stripes;
1477 stripe_nr = offset / chunk->stripe_len;
1478 if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID0) {
1479 index = stripe_nr % chunk->num_stripes;
1480 } else if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID10) {
1481 index = stripe_nr % (chunk->num_stripes / chunk->sub_stripes);
1482 index *= chunk->sub_stripes;
1483 } else if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID5) {
1484 nr_data_stripes = chunk->num_stripes - 1;
1485 index = stripe_nr % nr_data_stripes;
1486 stripe_nr /= nr_data_stripes;
1487 index = (index + stripe_nr) % chunk->num_stripes;
1488 } else if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID6) {
1489 nr_data_stripes = chunk->num_stripes - 2;
1490 index = stripe_nr % nr_data_stripes;
1491 stripe_nr /= nr_data_stripes;
1492 index = (index + stripe_nr) % chunk->num_stripes;
1499 /* calc the logical offset which is the start of the next stripe. */
1500 static inline u64 btrfs_next_stripe_logical_offset(struct chunk_record *chunk,
1503 u64 offset = logical - chunk->offset;
1505 offset /= chunk->stripe_len;
1506 offset *= chunk->stripe_len;
1507 offset += chunk->stripe_len;
1509 return offset + chunk->offset;
1512 static int is_extent_record_in_device_extent(struct extent_record *er,
1513 struct device_extent_record *dext,
1518 for (i = 0; i < er->nmirrors; i++) {
1519 if (er->devices[i]->devid == dext->objectid &&
1520 er->offsets[i] >= dext->offset &&
1521 er->offsets[i] < dext->offset + dext->length) {
1530 btrfs_rebuild_ordered_meta_chunk_stripes(struct recover_control *rc,
1531 struct chunk_record *chunk)
1533 u64 start = chunk->offset;
1534 u64 end = chunk->offset + chunk->length;
1535 struct cache_extent *cache;
1536 struct extent_record *er;
1537 struct device_extent_record *devext;
1538 struct device_extent_record *next;
1539 struct btrfs_device *device;
1545 cache = lookup_cache_extent(&rc->eb_cache,
1546 start, chunk->length);
1548 /* No used space, we can reorder the stripes freely. */
1549 ret = btrfs_rebuild_unordered_chunk_stripes(rc, chunk);
1553 list_splice_init(&chunk->dextents, &devexts);
1555 er = container_of(cache, struct extent_record, cache);
1556 index = btrfs_calc_stripe_index(chunk, er->cache.start);
1557 if (chunk->stripes[index].devid)
1559 list_for_each_entry_safe(devext, next, &devexts, chunk_list) {
1560 if (is_extent_record_in_device_extent(er, devext, &mirror)) {
1561 chunk->stripes[index].devid = devext->objectid;
1562 chunk->stripes[index].offset = devext->offset;
1563 memcpy(chunk->stripes[index].dev_uuid,
1564 er->devices[mirror]->uuid,
1567 list_move(&devext->chunk_list, &chunk->dextents);
1571 start = btrfs_next_stripe_logical_offset(chunk, er->cache.start);
1573 goto no_extent_record;
1575 cache = lookup_cache_extent(&rc->eb_cache, start, end - start);
1579 if (list_empty(&devexts))
1582 if (chunk->type_flags & (BTRFS_BLOCK_GROUP_RAID5 |
1583 BTRFS_BLOCK_GROUP_RAID6)) {
1584 /* Fixme: try to recover the order by the parity block. */
1585 list_splice_tail(&devexts, &chunk->dextents);
1589 /* There is no data on the lost stripes, we can reorder them freely. */
1590 for (index = 0; index < chunk->num_stripes; index++) {
1591 if (chunk->stripes[index].devid)
1594 devext = list_first_entry(&devexts,
1595 struct device_extent_record,
1597 list_move(&devext->chunk_list, &chunk->dextents);
1599 chunk->stripes[index].devid = devext->objectid;
1600 chunk->stripes[index].offset = devext->offset;
1601 device = btrfs_find_device_by_devid(rc->fs_devices,
1605 list_splice_tail(&devexts, &chunk->dextents);
1608 BUG_ON(btrfs_find_device_by_devid(rc->fs_devices,
1611 memcpy(chunk->stripes[index].dev_uuid, device->uuid,
1617 #define BTRFS_ORDERED_RAID (BTRFS_BLOCK_GROUP_RAID0 | \
1618 BTRFS_BLOCK_GROUP_RAID10 | \
1619 BTRFS_BLOCK_GROUP_RAID5 | \
1620 BTRFS_BLOCK_GROUP_RAID6)
1622 static int btrfs_rebuild_chunk_stripes(struct recover_control *rc,
1623 struct chunk_record *chunk)
1628 * All the data in the system metadata chunk will be dropped,
1629 * so we need not guarantee that the data is right or not, that
1630 * is we can reorder the stripes in the system metadata chunk.
1632 if ((chunk->type_flags & BTRFS_BLOCK_GROUP_METADATA) &&
1633 (chunk->type_flags & BTRFS_ORDERED_RAID))
1634 ret =btrfs_rebuild_ordered_meta_chunk_stripes(rc, chunk);
1635 else if ((chunk->type_flags & BTRFS_BLOCK_GROUP_DATA) &&
1636 (chunk->type_flags & BTRFS_ORDERED_RAID))
1637 ret = 1; /* Be handled after the fs is opened. */
1639 ret = btrfs_rebuild_unordered_chunk_stripes(rc, chunk);
1644 static int next_csum(struct btrfs_root *root,
1645 struct extent_buffer **leaf,
1646 struct btrfs_path *path,
1651 struct btrfs_key *key)
1654 struct btrfs_root *csum_root = root->fs_info->csum_root;
1655 struct btrfs_csum_item *csum_item;
1656 u32 blocksize = root->sectorsize;
1657 u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
1658 int csums_in_item = btrfs_item_size_nr(*leaf, *slot) / csum_size;
1660 if (*csum_offset >= csums_in_item) {
1663 if (*slot >= btrfs_header_nritems(*leaf)) {
1664 ret = btrfs_next_leaf(csum_root, path);
1669 *leaf = path->nodes[0];
1670 *slot = path->slots[0];
1672 btrfs_item_key_to_cpu(*leaf, key, *slot);
1675 if (key->offset + (*csum_offset) * blocksize >= end)
1677 csum_item = btrfs_item_ptr(*leaf, *slot, struct btrfs_csum_item);
1678 csum_item = (struct btrfs_csum_item *)((unsigned char *)csum_item
1679 + (*csum_offset) * csum_size);
1680 read_extent_buffer(*leaf, tree_csum,
1681 (unsigned long)csum_item, csum_size);
1685 static u64 calc_data_offset(struct btrfs_key *key,
1686 struct chunk_record *chunk,
1692 int logical_stripe_nr;
1694 int nr_data_stripes;
1696 data_offset = key->offset + csum_offset * blocksize - chunk->offset;
1697 nr_data_stripes = chunk->num_stripes;
1699 if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID5)
1700 nr_data_stripes -= 1;
1701 else if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID6)
1702 nr_data_stripes -= 2;
1704 logical_stripe_nr = data_offset / chunk->stripe_len;
1705 dev_stripe_nr = logical_stripe_nr / nr_data_stripes;
1707 data_offset -= logical_stripe_nr * chunk->stripe_len;
1708 data_offset += dev_stripe_nr * chunk->stripe_len;
1710 return dev_offset + data_offset;
1713 static int check_one_csum(int fd, u64 start, u32 len, u32 tree_csum)
1717 u32 csum_result = ~(u32)0;
1722 ret = pread64(fd, data, len, start);
1723 if (ret < 0 || ret != len) {
1728 csum_result = btrfs_csum_data(NULL, data, csum_result, len);
1729 btrfs_csum_final(csum_result, (char *)&csum_result);
1730 if (csum_result != tree_csum)
1737 static u64 item_end_offset(struct btrfs_root *root, struct btrfs_key *key,
1738 struct extent_buffer *leaf, int slot) {
1739 u32 blocksize = root->sectorsize;
1740 u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
1742 u64 offset = btrfs_item_size_nr(leaf, slot);
1743 offset /= csum_size;
1744 offset *= blocksize;
1745 offset += key->offset;
1750 static int insert_stripe(struct list_head *devexts,
1751 struct recover_control *rc,
1752 struct chunk_record *chunk,
1754 struct device_extent_record *devext;
1755 struct btrfs_device *dev;
1757 devext = list_entry(devexts->next, struct device_extent_record,
1759 dev = btrfs_find_device_by_devid(rc->fs_devices, devext->objectid,
1763 BUG_ON(btrfs_find_device_by_devid(rc->fs_devices, devext->objectid,
1766 chunk->stripes[index].devid = devext->objectid;
1767 chunk->stripes[index].offset = devext->offset;
1768 memcpy(chunk->stripes[index].dev_uuid, dev->uuid, BTRFS_UUID_SIZE);
1770 list_move(&devext->chunk_list, &chunk->dextents);
1775 #define EQUAL_STRIPE (1 << 0)
1777 static int rebuild_raid_data_chunk_stripes(struct recover_control *rc,
1778 struct btrfs_root *root,
1779 struct chunk_record *chunk,
1785 struct btrfs_path path;
1786 struct btrfs_key prev_key;
1787 struct btrfs_key key;
1788 struct btrfs_root *csum_root;
1789 struct extent_buffer *leaf;
1790 struct device_extent_record *devext;
1791 struct device_extent_record *next;
1792 struct btrfs_device *dev;
1793 u64 start = chunk->offset;
1794 u64 end = start + chunk->stripe_len;
1795 u64 chunk_end = chunk->offset + chunk->length;
1796 u64 csum_offset = 0;
1798 u32 blocksize = root->sectorsize;
1801 int num_unordered = 0;
1802 LIST_HEAD(unordered);
1803 LIST_HEAD(candidates);
1805 csum_root = root->fs_info->csum_root;
1806 btrfs_init_path(&path);
1807 list_splice_init(&chunk->dextents, &candidates);
1809 if (list_is_last(candidates.next, &candidates))
1812 key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
1813 key.type = BTRFS_EXTENT_CSUM_KEY;
1816 ret = btrfs_search_slot(NULL, csum_root, &key, &path, 0, 0);
1818 fprintf(stderr, "Search csum failed(%d)\n", ret);
1821 leaf = path.nodes[0];
1822 slot = path.slots[0];
1824 if (slot >= btrfs_header_nritems(leaf)) {
1825 ret = btrfs_next_leaf(csum_root, &path);
1828 "Walk tree failed(%d)\n", ret);
1830 } else if (ret > 0) {
1831 slot = btrfs_header_nritems(leaf) - 1;
1832 btrfs_item_key_to_cpu(leaf, &key, slot);
1833 if (item_end_offset(root, &key, leaf, slot)
1835 csum_offset = start - key.offset;
1836 csum_offset /= blocksize;
1841 leaf = path.nodes[0];
1842 slot = path.slots[0];
1844 btrfs_item_key_to_cpu(leaf, &key, slot);
1845 ret = btrfs_previous_item(csum_root, &path, 0,
1846 BTRFS_EXTENT_CSUM_KEY);
1850 if (key.offset >= end)
1855 leaf = path.nodes[0];
1856 slot = path.slots[0];
1858 btrfs_item_key_to_cpu(leaf, &prev_key, slot);
1859 if (item_end_offset(root, &prev_key, leaf, slot) > start) {
1860 csum_offset = start - prev_key.offset;
1861 csum_offset /= blocksize;
1862 btrfs_item_key_to_cpu(leaf, &key, slot);
1864 if (key.offset >= end)
1868 if (key.offset + csum_offset * blocksize > chunk_end)
1872 ret = next_csum(root, &leaf, &path, &slot, &csum_offset, &tree_csum,
1875 fprintf(stderr, "Fetch csum failed\n");
1877 } else if (ret == 1) {
1878 list_for_each_entry(devext, &unordered, chunk_list)
1880 if (!(*flags & EQUAL_STRIPE))
1881 *flags |= EQUAL_STRIPE;
1883 } else if (ret == 2)
1886 list_for_each_entry_safe(devext, next, &candidates, chunk_list) {
1887 data_offset = calc_data_offset(&key, chunk, devext->offset,
1888 csum_offset, blocksize);
1889 dev = btrfs_find_device_by_devid(rc->fs_devices,
1890 devext->objectid, 0);
1895 BUG_ON(btrfs_find_device_by_devid(rc->fs_devices,
1896 devext->objectid, 1));
1898 ret = check_one_csum(dev->fd, data_offset, blocksize,
1903 list_move(&devext->chunk_list, &unordered);
1906 if (list_empty(&candidates)) {
1907 list_for_each_entry(devext, &unordered, chunk_list)
1909 if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID6
1910 && num_unordered == 2) {
1911 list_splice_init(&unordered, &chunk->dextents);
1912 btrfs_release_path(&path);
1920 if (list_is_last(candidates.next, &candidates)) {
1921 index = btrfs_calc_stripe_index(chunk,
1922 key.offset + csum_offset * blocksize);
1923 if (chunk->stripes[index].devid)
1925 ret = insert_stripe(&candidates, rc, chunk, index);
1933 start = btrfs_next_stripe_logical_offset(chunk, start);
1934 end = min(start + chunk->stripe_len, chunk_end);
1935 list_splice_init(&unordered, &candidates);
1936 btrfs_release_path(&path);
1938 if (end < chunk_end)
1942 list_splice_init(&candidates, &unordered);
1943 list_for_each_entry(devext, &unordered, chunk_list)
1945 if (num_unordered == 1) {
1946 for (i = 0; i < chunk->num_stripes; i++) {
1947 if (!chunk->stripes[i].devid) {
1952 ret = insert_stripe(&unordered, rc, chunk, index);
1956 if ((num_unordered == 2 && chunk->type_flags
1957 & BTRFS_BLOCK_GROUP_RAID5)
1958 || (num_unordered == 3 && chunk->type_flags
1959 & BTRFS_BLOCK_GROUP_RAID6)) {
1960 for (i = 0; i < chunk->num_stripes; i++) {
1961 if (!chunk->stripes[i].devid) {
1962 ret = insert_stripe(&unordered, rc,
1971 ret = !!ret || (list_empty(&unordered) ? 0 : 1);
1972 list_splice_init(&candidates, &chunk->dextents);
1973 list_splice_init(&unordered, &chunk->dextents);
1974 btrfs_release_path(&path);
1979 static int btrfs_rebuild_ordered_data_chunk_stripes(struct recover_control *rc,
1980 struct btrfs_root *root)
1982 struct chunk_record *chunk;
1983 struct chunk_record *next;
1988 list_for_each_entry_safe(chunk, next, &rc->unrepaired_chunks, list) {
1989 if ((chunk->type_flags & BTRFS_BLOCK_GROUP_DATA)
1990 && (chunk->type_flags & BTRFS_ORDERED_RAID)) {
1992 err = rebuild_raid_data_chunk_stripes(rc, root, chunk,
1995 list_move(&chunk->list, &rc->bad_chunks);
1996 if (flags & EQUAL_STRIPE)
1998 "Failure: too many equal stripes in chunk[%llu %llu]\n",
1999 chunk->offset, chunk->length);
2003 list_move(&chunk->list, &rc->good_chunks);
2009 static int btrfs_recover_chunks(struct recover_control *rc)
2011 struct chunk_record *chunk;
2012 struct block_group_record *bg;
2013 struct block_group_record *next;
2014 LIST_HEAD(new_chunks);
2019 /* create the chunk by block group */
2020 list_for_each_entry_safe(bg, next, &rc->bg.block_groups, list) {
2021 nstripes = btrfs_get_device_extents(bg->objectid,
2022 &rc->devext.no_chunk_orphans,
2024 chunk = malloc(btrfs_chunk_record_size(nstripes));
2027 memset(chunk, 0, btrfs_chunk_record_size(nstripes));
2028 INIT_LIST_HEAD(&chunk->dextents);
2030 chunk->cache.start = bg->objectid;
2031 chunk->cache.size = bg->offset;
2032 chunk->objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
2033 chunk->type = BTRFS_CHUNK_ITEM_KEY;
2034 chunk->offset = bg->objectid;
2035 chunk->generation = bg->generation;
2036 chunk->length = bg->offset;
2037 chunk->owner = BTRFS_CHUNK_TREE_OBJECTID;
2038 chunk->stripe_len = BTRFS_STRIPE_LEN;
2039 chunk->type_flags = bg->flags;
2040 chunk->io_width = BTRFS_STRIPE_LEN;
2041 chunk->io_align = BTRFS_STRIPE_LEN;
2042 chunk->sector_size = rc->sectorsize;
2043 chunk->sub_stripes = calc_sub_nstripes(bg->flags);
2045 ret = insert_cache_extent(&rc->chunk, &chunk->cache);
2049 list_add_tail(&chunk->list, &rc->bad_chunks);
2053 list_splice_init(&devexts, &chunk->dextents);
2055 ret = btrfs_verify_device_extents(bg, &devexts, nstripes);
2057 list_add_tail(&chunk->list, &rc->bad_chunks);
2061 chunk->num_stripes = nstripes;
2062 ret = btrfs_rebuild_chunk_stripes(rc, chunk);
2064 list_add_tail(&chunk->list, &rc->unrepaired_chunks);
2066 list_add_tail(&chunk->list, &rc->bad_chunks);
2068 list_add_tail(&chunk->list, &rc->good_chunks);
2071 * Don't worry about the lost orphan device extents, they don't
2072 * have its chunk and block group, they must be the old ones that
2079 * Return 0 when succesful, < 0 on error and > 0 if aborted by user
2081 int btrfs_recover_chunk_tree(char *path, int verbose, int yes)
2084 struct btrfs_root *root = NULL;
2085 struct btrfs_trans_handle *trans;
2086 struct recover_control rc;
2088 init_recover_control(&rc, verbose, yes);
2090 ret = recover_prepare(&rc, path);
2092 fprintf(stderr, "recover prepare error\n");
2096 ret = scan_devices(&rc);
2098 fprintf(stderr, "scan chunk headers error\n");
2102 if (cache_tree_empty(&rc.chunk) &&
2103 cache_tree_empty(&rc.bg.tree) &&
2104 cache_tree_empty(&rc.devext.tree)) {
2105 fprintf(stderr, "no recoverable chunk\n");
2109 print_scan_result(&rc);
2111 ret = check_chunks(&rc.chunk, &rc.bg, &rc.devext, &rc.good_chunks,
2113 print_check_result(&rc);
2115 if (!list_empty(&rc.bg.block_groups) ||
2116 !list_empty(&rc.devext.no_chunk_orphans)) {
2117 ret = btrfs_recover_chunks(&rc);
2122 * If the chunk is healthy, its block group item and device
2123 * extent item should be written on the disks. So, it is very
2124 * likely that the bad chunk is a old one that has been
2125 * droppped from the fs. Don't deal with them now, we will
2126 * check it after the fs is opened.
2129 fprintf(stderr, "Check chunks successfully with no orphans\n");
2133 root = open_ctree_with_broken_chunk(&rc);
2135 fprintf(stderr, "open with broken chunk error\n");
2136 ret = PTR_ERR(root);
2140 ret = check_all_chunks_by_metadata(&rc, root);
2142 fprintf(stderr, "The chunks in memory can not match the metadata of the fs. Repair failed.\n");
2143 goto fail_close_ctree;
2146 ret = btrfs_rebuild_ordered_data_chunk_stripes(&rc, root);
2148 fprintf(stderr, "Failed to rebuild ordered chunk stripes.\n");
2149 goto fail_close_ctree;
2153 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?");
2156 goto fail_close_ctree;
2160 trans = btrfs_start_transaction(root, 1);
2161 ret = remove_chunk_extent_item(trans, &rc, root);
2164 ret = rebuild_chunk_tree(trans, &rc, root);
2167 ret = rebuild_sys_array(&rc, root);
2170 btrfs_commit_transaction(trans, root);
2174 free_recover_control(&rc);