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>
30 #include "kerncompat.h"
32 #include "radix-tree.h"
34 #include "extent-cache.h"
37 #include "transaction.h"
44 #define BTRFS_CHUNK_TREE_REBUILD_ABORTED -7500
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;
70 struct extent_record {
71 struct cache_extent cache;
73 u8 csum[BTRFS_CSUM_SIZE];
74 struct btrfs_device *devices[BTRFS_NUM_MIRRORS];
75 u64 offsets[BTRFS_NUM_MIRRORS];
79 static struct extent_record *btrfs_new_extent_record(struct extent_buffer *eb)
81 struct extent_record *rec;
83 rec = malloc(sizeof(*rec));
85 fprintf(stderr, "Fail to allocate memory for extent record.\n");
89 memset(rec, 0, sizeof(*rec));
90 rec->cache.start = btrfs_header_bytenr(eb);
91 rec->cache.size = eb->len;
92 rec->generation = btrfs_header_generation(eb);
93 read_extent_buffer(eb, rec->csum, (unsigned long)btrfs_header_csum(eb),
98 static int process_extent_buffer(struct cache_tree *eb_cache,
99 struct extent_buffer *eb,
100 struct btrfs_device *device, u64 offset)
102 struct extent_record *rec;
103 struct extent_record *exist;
104 struct cache_extent *cache;
107 rec = btrfs_new_extent_record(eb);
108 if (!rec->cache.size)
111 cache = lookup_cache_extent(eb_cache,
115 exist = container_of(cache, struct extent_record, cache);
117 if (exist->generation > rec->generation)
119 if (exist->generation == rec->generation) {
120 if (exist->cache.start != rec->cache.start ||
121 exist->cache.size != rec->cache.size ||
122 memcmp(exist->csum, rec->csum, BTRFS_CSUM_SIZE)) {
125 BUG_ON(exist->nmirrors >= BTRFS_NUM_MIRRORS);
126 exist->devices[exist->nmirrors] = device;
127 exist->offsets[exist->nmirrors] = offset;
132 remove_cache_extent(eb_cache, cache);
137 rec->devices[0] = device;
138 rec->offsets[0] = offset;
140 ret = insert_cache_extent(eb_cache, &rec->cache);
149 static void free_extent_record(struct cache_extent *cache)
151 struct extent_record *er;
153 er = container_of(cache, struct extent_record, cache);
157 FREE_EXTENT_CACHE_BASED_TREE(extent_record, free_extent_record);
159 static struct btrfs_chunk *create_chunk_item(struct chunk_record *record)
161 struct btrfs_chunk *ret;
162 struct btrfs_stripe *chunk_stripe;
165 if (!record || record->num_stripes == 0)
167 ret = malloc(btrfs_chunk_item_size(record->num_stripes));
170 btrfs_set_stack_chunk_length(ret, record->length);
171 btrfs_set_stack_chunk_owner(ret, record->owner);
172 btrfs_set_stack_chunk_stripe_len(ret, record->stripe_len);
173 btrfs_set_stack_chunk_type(ret, record->type_flags);
174 btrfs_set_stack_chunk_io_align(ret, record->io_align);
175 btrfs_set_stack_chunk_io_width(ret, record->io_width);
176 btrfs_set_stack_chunk_sector_size(ret, record->sector_size);
177 btrfs_set_stack_chunk_num_stripes(ret, record->num_stripes);
178 btrfs_set_stack_chunk_sub_stripes(ret, record->sub_stripes);
179 for (i = 0, chunk_stripe = &ret->stripe; i < record->num_stripes;
180 i++, chunk_stripe++) {
181 btrfs_set_stack_stripe_devid(chunk_stripe,
182 record->stripes[i].devid);
183 btrfs_set_stack_stripe_offset(chunk_stripe,
184 record->stripes[i].offset);
185 memcpy(chunk_stripe->dev_uuid, record->stripes[i].dev_uuid,
191 static void init_recover_control(struct recover_control *rc, int verbose,
194 memset(rc, 0, sizeof(struct recover_control));
195 cache_tree_init(&rc->chunk);
196 cache_tree_init(&rc->eb_cache);
197 block_group_tree_init(&rc->bg);
198 device_extent_tree_init(&rc->devext);
200 INIT_LIST_HEAD(&rc->good_chunks);
201 INIT_LIST_HEAD(&rc->bad_chunks);
202 INIT_LIST_HEAD(&rc->unrepaired_chunks);
204 rc->verbose = verbose;
208 static void free_recover_control(struct recover_control *rc)
210 free_block_group_tree(&rc->bg);
211 free_chunk_cache_tree(&rc->chunk);
212 free_device_extent_tree(&rc->devext);
213 free_extent_record_tree(&rc->eb_cache);
216 static int process_block_group_item(struct block_group_tree *bg_cache,
217 struct extent_buffer *leaf,
218 struct btrfs_key *key, int slot)
220 struct block_group_record *rec;
221 struct block_group_record *exist;
222 struct cache_extent *cache;
225 rec = btrfs_new_block_group_record(leaf, key, slot);
226 if (!rec->cache.size)
229 cache = lookup_cache_extent(&bg_cache->tree,
233 exist = container_of(cache, struct block_group_record, cache);
235 /*check the generation and replace if needed*/
236 if (exist->generation > rec->generation)
238 if (exist->generation == rec->generation) {
239 int offset = offsetof(struct block_group_record,
242 * According to the current kernel code, the following
243 * case is impossble, or there is something wrong in
246 if (memcmp(((void *)exist) + offset,
247 ((void *)rec) + offset,
248 sizeof(*rec) - offset))
252 remove_cache_extent(&bg_cache->tree, cache);
253 list_del_init(&exist->list);
256 * We must do seach again to avoid the following cache.
257 * /--old bg 1--//--old bg 2--/
263 ret = insert_block_group_record(bg_cache, rec);
272 static int process_chunk_item(struct cache_tree *chunk_cache,
273 struct extent_buffer *leaf, struct btrfs_key *key,
276 struct chunk_record *rec;
277 struct chunk_record *exist;
278 struct cache_extent *cache;
281 rec = btrfs_new_chunk_record(leaf, key, slot);
282 if (!rec->cache.size)
285 cache = lookup_cache_extent(chunk_cache, rec->offset, rec->length);
287 exist = container_of(cache, struct chunk_record, cache);
289 if (exist->generation > rec->generation)
291 if (exist->generation == rec->generation) {
292 int num_stripes = rec->num_stripes;
293 int rec_size = btrfs_chunk_record_size(num_stripes);
294 int offset = offsetof(struct chunk_record, generation);
296 if (exist->num_stripes != rec->num_stripes ||
297 memcmp(((void *)exist) + offset,
298 ((void *)rec) + offset,
303 remove_cache_extent(chunk_cache, cache);
307 ret = insert_cache_extent(chunk_cache, &rec->cache);
316 static int process_device_extent_item(struct device_extent_tree *devext_cache,
317 struct extent_buffer *leaf,
318 struct btrfs_key *key, int slot)
320 struct device_extent_record *rec;
321 struct device_extent_record *exist;
322 struct cache_extent *cache;
325 rec = btrfs_new_device_extent_record(leaf, key, slot);
326 if (!rec->cache.size)
329 cache = lookup_cache_extent2(&devext_cache->tree,
334 exist = container_of(cache, struct device_extent_record, cache);
335 if (exist->generation > rec->generation)
337 if (exist->generation == rec->generation) {
338 int offset = offsetof(struct device_extent_record,
340 if (memcmp(((void *)exist) + offset,
341 ((void *)rec) + offset,
342 sizeof(*rec) - offset))
346 remove_cache_extent(&devext_cache->tree, cache);
347 list_del_init(&exist->chunk_list);
348 list_del_init(&exist->device_list);
353 ret = insert_device_extent_record(devext_cache, rec);
362 static void print_block_group_info(struct block_group_record *rec, char *prefix)
365 printf("%s", prefix);
366 printf("Block Group: start = %llu, len = %llu, flag = %llx\n",
367 rec->objectid, rec->offset, rec->flags);
370 static void print_block_group_tree(struct block_group_tree *tree)
372 struct cache_extent *cache;
373 struct block_group_record *rec;
375 printf("All Block Groups:\n");
376 for (cache = first_cache_extent(&tree->tree); cache;
377 cache = next_cache_extent(cache)) {
378 rec = container_of(cache, struct block_group_record, cache);
379 print_block_group_info(rec, "\t");
384 static void print_stripe_info(struct stripe *data, char *prefix1, char *prefix2,
388 printf("%s", prefix1);
390 printf("%s", prefix2);
391 printf("[%2d] Stripe: devid = %llu, offset = %llu\n",
392 index, data->devid, data->offset);
395 static void print_chunk_self_info(struct chunk_record *rec, char *prefix)
400 printf("%s", prefix);
401 printf("Chunk: start = %llu, len = %llu, type = %llx, num_stripes = %u\n",
402 rec->offset, rec->length, rec->type_flags, rec->num_stripes);
404 printf("%s", prefix);
405 printf(" Stripes list:\n");
406 for (i = 0; i < rec->num_stripes; i++)
407 print_stripe_info(&rec->stripes[i], prefix, " ", i);
410 static void print_chunk_tree(struct cache_tree *tree)
412 struct cache_extent *n;
413 struct chunk_record *entry;
415 printf("All Chunks:\n");
416 for (n = first_cache_extent(tree); n;
417 n = next_cache_extent(n)) {
418 entry = container_of(n, struct chunk_record, cache);
419 print_chunk_self_info(entry, "\t");
424 static void print_device_extent_info(struct device_extent_record *rec,
428 printf("%s", prefix);
429 printf("Device extent: devid = %llu, start = %llu, len = %llu, chunk offset = %llu\n",
430 rec->objectid, rec->offset, rec->length, rec->chunk_offset);
433 static void print_device_extent_tree(struct device_extent_tree *tree)
435 struct cache_extent *n;
436 struct device_extent_record *entry;
438 printf("All Device Extents:\n");
439 for (n = first_cache_extent(&tree->tree); n;
440 n = next_cache_extent(n)) {
441 entry = container_of(n, struct device_extent_record, cache);
442 print_device_extent_info(entry, "\t");
447 static void print_device_info(struct btrfs_device *device, char *prefix)
450 printf("%s", prefix);
451 printf("Device: id = %llu, name = %s\n",
452 device->devid, device->name);
455 static void print_all_devices(struct list_head *devices)
457 struct btrfs_device *dev;
459 printf("All Devices:\n");
460 list_for_each_entry(dev, devices, dev_list)
461 print_device_info(dev, "\t");
465 static void print_scan_result(struct recover_control *rc)
470 printf("DEVICE SCAN RESULT:\n");
471 printf("Filesystem Information:\n");
472 printf("\tsectorsize: %d\n", rc->sectorsize);
473 printf("\tleafsize: %d\n", rc->leafsize);
474 printf("\ttree root generation: %llu\n", rc->generation);
475 printf("\tchunk root generation: %llu\n", rc->chunk_root_generation);
478 print_all_devices(&rc->fs_devices->devices);
479 print_block_group_tree(&rc->bg);
480 print_chunk_tree(&rc->chunk);
481 print_device_extent_tree(&rc->devext);
484 static void print_chunk_info(struct chunk_record *chunk, char *prefix)
486 struct device_extent_record *devext;
489 print_chunk_self_info(chunk, prefix);
491 printf("%s", prefix);
493 print_block_group_info(chunk->bg_rec, " ");
495 printf(" No block group.\n");
497 printf("%s", prefix);
498 if (list_empty(&chunk->dextents)) {
499 printf(" No device extent.\n");
501 printf(" Device extent list:\n");
503 list_for_each_entry(devext, &chunk->dextents, chunk_list) {
505 printf("%s", prefix);
506 printf("%s[%2d]", " ", i);
507 print_device_extent_info(devext, NULL);
513 static void print_check_result(struct recover_control *rc)
515 struct chunk_record *chunk;
516 struct block_group_record *bg;
517 struct device_extent_record *devext;
525 printf("CHECK RESULT:\n");
526 printf("Healthy Chunks:\n");
527 list_for_each_entry(chunk, &rc->good_chunks, list) {
528 print_chunk_info(chunk, " ");
532 printf("Bad Chunks:\n");
533 list_for_each_entry(chunk, &rc->bad_chunks, list) {
534 print_chunk_info(chunk, " ");
539 printf("Total Chunks:\t%d\n", total);
540 printf(" Heathy:\t%d\n", good);
541 printf(" Bad:\t%d\n", bad);
544 printf("Orphan Block Groups:\n");
545 list_for_each_entry(bg, &rc->bg.block_groups, list)
546 print_block_group_info(bg, " ");
549 printf("Orphan Device Extents:\n");
550 list_for_each_entry(devext, &rc->devext.no_chunk_orphans, chunk_list)
551 print_device_extent_info(devext, " ");
554 static int check_chunk_by_metadata(struct recover_control *rc,
555 struct btrfs_root *root,
556 struct chunk_record *chunk, int bg_only)
561 struct btrfs_path path;
562 struct btrfs_key key;
563 struct btrfs_root *dev_root;
564 struct stripe *stripe;
565 struct btrfs_dev_extent *dev_extent;
566 struct btrfs_block_group_item *bg_ptr;
567 struct extent_buffer *l;
569 btrfs_init_path(&path);
574 dev_root = root->fs_info->dev_root;
575 for (i = 0; i < chunk->num_stripes; i++) {
576 stripe = &chunk->stripes[i];
578 key.objectid = stripe->devid;
579 key.offset = stripe->offset;
580 key.type = BTRFS_DEV_EXTENT_KEY;
582 ret = btrfs_search_slot(NULL, dev_root, &key, &path, 0, 0);
584 fprintf(stderr, "Search device extent failed(%d)\n",
586 btrfs_release_path(&path);
588 } else if (ret > 0) {
591 "No device extent[%llu, %llu]\n",
592 stripe->devid, stripe->offset);
593 btrfs_release_path(&path);
597 slot = path.slots[0];
598 dev_extent = btrfs_item_ptr(l, slot, struct btrfs_dev_extent);
600 btrfs_dev_extent_chunk_offset(l, dev_extent)) {
603 "Device tree unmatch with chunks dev_extent[%llu, %llu], chunk[%llu, %llu]\n",
604 btrfs_dev_extent_chunk_offset(l,
606 btrfs_dev_extent_length(l, dev_extent),
607 chunk->offset, chunk->length);
608 btrfs_release_path(&path);
611 btrfs_release_path(&path);
615 key.objectid = chunk->offset;
616 key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
617 key.offset = chunk->length;
619 ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, &path,
622 fprintf(stderr, "Search block group failed(%d)\n", ret);
623 btrfs_release_path(&path);
625 } else if (ret > 0) {
627 fprintf(stderr, "No block group[%llu, %llu]\n",
628 key.objectid, key.offset);
629 btrfs_release_path(&path);
634 slot = path.slots[0];
635 bg_ptr = btrfs_item_ptr(l, slot, struct btrfs_block_group_item);
636 if (chunk->type_flags != btrfs_disk_block_group_flags(l, bg_ptr)) {
639 "Chunk[%llu, %llu]'s type(%llu) is differemt with Block Group's type(%llu)\n",
640 chunk->offset, chunk->length, chunk->type_flags,
641 btrfs_disk_block_group_flags(l, bg_ptr));
642 btrfs_release_path(&path);
645 btrfs_release_path(&path);
649 static int check_all_chunks_by_metadata(struct recover_control *rc,
650 struct btrfs_root *root)
652 struct chunk_record *chunk;
653 struct chunk_record *next;
654 LIST_HEAD(orphan_chunks);
658 list_for_each_entry_safe(chunk, next, &rc->good_chunks, list) {
659 err = check_chunk_by_metadata(rc, root, chunk, 0);
662 list_move_tail(&chunk->list, &orphan_chunks);
663 else if (err && !ret)
668 list_for_each_entry_safe(chunk, next, &rc->unrepaired_chunks, list) {
669 err = check_chunk_by_metadata(rc, root, chunk, 1);
671 list_move_tail(&chunk->list, &orphan_chunks);
672 else if (err && !ret)
676 list_for_each_entry(chunk, &rc->bad_chunks, list) {
677 err = check_chunk_by_metadata(rc, root, chunk, 1);
678 if (err != -ENOENT && !ret)
679 ret = err ? err : -EINVAL;
681 list_splice(&orphan_chunks, &rc->bad_chunks);
685 static int extract_metadata_record(struct recover_control *rc,
686 struct extent_buffer *leaf)
688 struct btrfs_key key;
693 nritems = btrfs_header_nritems(leaf);
694 for (i = 0; i < nritems; i++) {
695 btrfs_item_key_to_cpu(leaf, &key, i);
697 case BTRFS_BLOCK_GROUP_ITEM_KEY:
698 ret = process_block_group_item(&rc->bg, leaf, &key, i);
700 case BTRFS_CHUNK_ITEM_KEY:
701 ret = process_chunk_item(&rc->chunk, leaf, &key, i);
703 case BTRFS_DEV_EXTENT_KEY:
704 ret = process_device_extent_item(&rc->devext, leaf,
714 static inline int is_super_block_address(u64 offset)
718 for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
719 if (offset == btrfs_sb_offset(i))
725 static int scan_one_device(struct recover_control *rc, int fd,
726 struct btrfs_device *device)
728 struct extent_buffer *buf;
732 buf = malloc(sizeof(*buf) + rc->leafsize);
735 buf->len = rc->leafsize;
739 if (is_super_block_address(bytenr))
740 bytenr += rc->sectorsize;
742 if (pread64(fd, buf->data, rc->leafsize, bytenr) <
746 if (memcmp_extent_buffer(buf, rc->fs_devices->fsid,
747 (unsigned long)btrfs_header_fsid(buf),
749 bytenr += rc->sectorsize;
753 if (verify_tree_block_csum_silent(buf, rc->csum_size)) {
754 bytenr += rc->sectorsize;
758 ret = process_extent_buffer(&rc->eb_cache, buf, device, bytenr);
762 if (btrfs_header_level(buf) != 0)
765 switch (btrfs_header_owner(buf)) {
766 case BTRFS_EXTENT_TREE_OBJECTID:
767 case BTRFS_DEV_TREE_OBJECTID:
768 /* different tree use different generation */
769 if (btrfs_header_generation(buf) > rc->generation)
771 ret = extract_metadata_record(rc, buf);
775 case BTRFS_CHUNK_TREE_OBJECTID:
776 if (btrfs_header_generation(buf) >
777 rc->chunk_root_generation)
779 ret = extract_metadata_record(rc, buf);
785 bytenr += rc->leafsize;
792 static int scan_devices(struct recover_control *rc)
796 struct btrfs_device *dev;
798 list_for_each_entry(dev, &rc->fs_devices->devices, dev_list) {
799 fd = open(dev->name, O_RDONLY);
801 fprintf(stderr, "Failed to open device %s\n",
805 ret = scan_one_device(rc, fd, dev);
813 static int build_device_map_by_chunk_record(struct btrfs_root *root,
814 struct chunk_record *chunk)
819 u8 uuid[BTRFS_UUID_SIZE];
821 struct btrfs_mapping_tree *map_tree;
822 struct map_lookup *map;
823 struct stripe *stripe;
825 map_tree = &root->fs_info->mapping_tree;
826 num_stripes = chunk->num_stripes;
827 map = malloc(btrfs_map_lookup_size(num_stripes));
830 map->ce.start = chunk->offset;
831 map->ce.size = chunk->length;
832 map->num_stripes = num_stripes;
833 map->io_width = chunk->io_width;
834 map->io_align = chunk->io_align;
835 map->sector_size = chunk->sector_size;
836 map->stripe_len = chunk->stripe_len;
837 map->type = chunk->type_flags;
838 map->sub_stripes = chunk->sub_stripes;
840 for (i = 0, stripe = chunk->stripes; i < num_stripes; i++, stripe++) {
841 devid = stripe->devid;
842 memcpy(uuid, stripe->dev_uuid, BTRFS_UUID_SIZE);
843 map->stripes[i].physical = stripe->offset;
844 map->stripes[i].dev = btrfs_find_device(root, devid,
846 if (!map->stripes[i].dev) {
852 ret = insert_cache_extent(&map_tree->cache_tree, &map->ce);
856 static int build_device_maps_by_chunk_records(struct recover_control *rc,
857 struct btrfs_root *root)
860 struct chunk_record *chunk;
862 list_for_each_entry(chunk, &rc->good_chunks, list) {
863 ret = build_device_map_by_chunk_record(root, chunk);
870 static int block_group_remove_all_extent_items(struct btrfs_trans_handle *trans,
871 struct btrfs_root *root,
872 struct block_group_record *bg)
874 struct btrfs_fs_info *fs_info = root->fs_info;
875 struct btrfs_key key;
876 struct btrfs_path path;
877 struct extent_buffer *leaf;
878 u64 start = bg->objectid;
879 u64 end = bg->objectid + bg->offset;
886 btrfs_init_path(&path);
887 root = root->fs_info->extent_root;
889 key.objectid = start;
891 key.type = BTRFS_EXTENT_ITEM_KEY;
893 ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
899 leaf = path.nodes[0];
900 nitems = btrfs_header_nritems(leaf);
902 /* The tree is empty. */
907 if (path.slots[0] >= nitems) {
908 ret = btrfs_next_leaf(root, &path);
915 leaf = path.nodes[0];
916 btrfs_item_key_to_cpu(leaf, &key, 0);
917 if (key.objectid >= end)
919 btrfs_release_path(&path);
925 for (i = path.slots[0]; i < nitems; i++) {
926 btrfs_item_key_to_cpu(leaf, &key, i);
927 if (key.objectid >= end)
930 if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
940 if (key.type == BTRFS_EXTENT_ITEM_KEY ||
941 key.type == BTRFS_METADATA_ITEM_KEY) {
942 old_val = btrfs_super_bytes_used(fs_info->super_copy);
943 if (key.type == BTRFS_METADATA_ITEM_KEY)
944 old_val += root->leafsize;
946 old_val += key.offset;
947 btrfs_set_super_bytes_used(fs_info->super_copy,
953 ret = btrfs_del_items(trans, root, &path, del_s, del_nr);
958 if (key.objectid < end) {
959 if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
960 key.objectid += root->sectorsize;
961 key.type = BTRFS_EXTENT_ITEM_KEY;
964 btrfs_release_path(&path);
968 btrfs_release_path(&path);
972 static int block_group_free_all_extent(struct btrfs_trans_handle *trans,
973 struct btrfs_root *root,
974 struct block_group_record *bg)
976 struct btrfs_block_group_cache *cache;
977 struct btrfs_fs_info *info;
981 info = root->fs_info;
982 cache = btrfs_lookup_block_group(info, bg->objectid);
986 start = cache->key.objectid;
987 end = start + cache->key.offset - 1;
989 set_extent_bits(&info->block_group_cache, start, end,
990 BLOCK_GROUP_DIRTY, GFP_NOFS);
991 set_extent_dirty(&info->free_space_cache, start, end, GFP_NOFS);
993 btrfs_set_block_group_used(&cache->item, 0);
998 static int remove_chunk_extent_item(struct btrfs_trans_handle *trans,
999 struct recover_control *rc,
1000 struct btrfs_root *root)
1002 struct chunk_record *chunk;
1005 list_for_each_entry(chunk, &rc->good_chunks, list) {
1006 if (!(chunk->type_flags & BTRFS_BLOCK_GROUP_SYSTEM))
1008 ret = block_group_remove_all_extent_items(trans, root,
1013 ret = block_group_free_all_extent(trans, root, chunk->bg_rec);
1020 static int __rebuild_chunk_root(struct btrfs_trans_handle *trans,
1021 struct recover_control *rc,
1022 struct btrfs_root *root)
1025 struct btrfs_device *dev;
1026 struct extent_buffer *cow;
1027 struct btrfs_disk_key disk_key;
1030 list_for_each_entry(dev, &rc->fs_devices->devices, dev_list) {
1031 if (min_devid > dev->devid)
1032 min_devid = dev->devid;
1034 btrfs_set_disk_key_objectid(&disk_key, BTRFS_DEV_ITEMS_OBJECTID);
1035 btrfs_set_disk_key_type(&disk_key, BTRFS_DEV_ITEM_KEY);
1036 btrfs_set_disk_key_offset(&disk_key, min_devid);
1038 cow = btrfs_alloc_free_block(trans, root, root->sectorsize,
1039 BTRFS_CHUNK_TREE_OBJECTID,
1040 &disk_key, 0, 0, 0);
1041 btrfs_set_header_bytenr(cow, cow->start);
1042 btrfs_set_header_generation(cow, trans->transid);
1043 btrfs_set_header_nritems(cow, 0);
1044 btrfs_set_header_level(cow, 0);
1045 btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
1046 btrfs_set_header_owner(cow, BTRFS_CHUNK_TREE_OBJECTID);
1047 write_extent_buffer(cow, root->fs_info->fsid,
1048 (unsigned long)btrfs_header_fsid(cow),
1051 write_extent_buffer(cow, root->fs_info->chunk_tree_uuid,
1052 (unsigned long)btrfs_header_chunk_tree_uuid(cow),
1056 btrfs_mark_buffer_dirty(cow);
1061 static int __rebuild_device_items(struct btrfs_trans_handle *trans,
1062 struct recover_control *rc,
1063 struct btrfs_root *root)
1065 struct btrfs_device *dev;
1066 struct btrfs_key key;
1067 struct btrfs_dev_item *dev_item;
1070 dev_item = malloc(sizeof(struct btrfs_dev_item));
1074 list_for_each_entry(dev, &rc->fs_devices->devices, dev_list) {
1075 key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
1076 key.type = BTRFS_DEV_ITEM_KEY;
1077 key.offset = dev->devid;
1079 btrfs_set_stack_device_generation(dev_item, 0);
1080 btrfs_set_stack_device_type(dev_item, dev->type);
1081 btrfs_set_stack_device_id(dev_item, dev->devid);
1082 btrfs_set_stack_device_total_bytes(dev_item, dev->total_bytes);
1083 btrfs_set_stack_device_bytes_used(dev_item, dev->bytes_used);
1084 btrfs_set_stack_device_io_align(dev_item, dev->io_align);
1085 btrfs_set_stack_device_io_width(dev_item, dev->io_width);
1086 btrfs_set_stack_device_sector_size(dev_item, dev->sector_size);
1087 memcpy(dev_item->uuid, dev->uuid, BTRFS_UUID_SIZE);
1088 memcpy(dev_item->fsid, dev->fs_devices->fsid, BTRFS_UUID_SIZE);
1090 ret = btrfs_insert_item(trans, root, &key,
1091 dev_item, sizeof(*dev_item));
1098 static int __rebuild_chunk_items(struct btrfs_trans_handle *trans,
1099 struct recover_control *rc,
1100 struct btrfs_root *root)
1102 struct btrfs_key key;
1103 struct btrfs_chunk *chunk = NULL;
1104 struct btrfs_root *chunk_root;
1105 struct chunk_record *chunk_rec;
1108 chunk_root = root->fs_info->chunk_root;
1110 list_for_each_entry(chunk_rec, &rc->good_chunks, list) {
1111 chunk = create_chunk_item(chunk_rec);
1115 key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
1116 key.type = BTRFS_CHUNK_ITEM_KEY;
1117 key.offset = chunk_rec->offset;
1119 ret = btrfs_insert_item(trans, chunk_root, &key, chunk,
1120 btrfs_chunk_item_size(chunk_rec->num_stripes));
1128 static int rebuild_chunk_tree(struct btrfs_trans_handle *trans,
1129 struct recover_control *rc,
1130 struct btrfs_root *root)
1134 root = root->fs_info->chunk_root;
1136 ret = __rebuild_chunk_root(trans, rc, root);
1140 ret = __rebuild_device_items(trans, rc, root);
1144 ret = __rebuild_chunk_items(trans, rc, root);
1149 static int rebuild_sys_array(struct recover_control *rc,
1150 struct btrfs_root *root)
1152 struct btrfs_chunk *chunk;
1153 struct btrfs_key key;
1154 struct chunk_record *chunk_rec;
1158 btrfs_set_super_sys_array_size(root->fs_info->super_copy, 0);
1160 list_for_each_entry(chunk_rec, &rc->good_chunks, list) {
1161 if (!(chunk_rec->type_flags & BTRFS_BLOCK_GROUP_SYSTEM))
1164 num_stripes = chunk_rec->num_stripes;
1165 chunk = create_chunk_item(chunk_rec);
1171 key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
1172 key.type = BTRFS_CHUNK_ITEM_KEY;
1173 key.offset = chunk_rec->offset;
1175 ret = btrfs_add_system_chunk(NULL, root, &key, chunk,
1176 btrfs_chunk_item_size(num_stripes));
1185 static struct btrfs_root *
1186 open_ctree_with_broken_chunk(struct recover_control *rc)
1188 struct btrfs_fs_info *fs_info;
1189 struct btrfs_super_block *disk_super;
1190 struct extent_buffer *eb;
1197 fs_info = btrfs_new_fs_info(1, BTRFS_SUPER_INFO_OFFSET);
1199 fprintf(stderr, "Failed to allocate memory for fs_info\n");
1200 return ERR_PTR(-ENOMEM);
1203 fs_info->fs_devices = rc->fs_devices;
1204 ret = btrfs_open_devices(fs_info->fs_devices, O_RDWR);
1208 disk_super = fs_info->super_copy;
1209 ret = btrfs_read_dev_super(fs_info->fs_devices->latest_bdev,
1210 disk_super, fs_info->super_bytenr);
1212 fprintf(stderr, "No valid btrfs found\n");
1216 memcpy(fs_info->fsid, &disk_super->fsid, BTRFS_FSID_SIZE);
1218 ret = btrfs_check_fs_compatibility(disk_super, 1);
1222 nodesize = btrfs_super_nodesize(disk_super);
1223 leafsize = btrfs_super_leafsize(disk_super);
1224 sectorsize = btrfs_super_sectorsize(disk_super);
1225 stripesize = btrfs_super_stripesize(disk_super);
1227 __setup_root(nodesize, leafsize, sectorsize, stripesize,
1228 fs_info->chunk_root, fs_info, BTRFS_CHUNK_TREE_OBJECTID);
1230 ret = build_device_maps_by_chunk_records(rc, fs_info->chunk_root);
1234 ret = btrfs_setup_all_roots(fs_info, 0, 0);
1238 eb = fs_info->tree_root->node;
1239 read_extent_buffer(eb, fs_info->chunk_tree_uuid,
1240 (unsigned long)btrfs_header_chunk_tree_uuid(eb),
1243 return fs_info->fs_root;
1245 btrfs_release_all_roots(fs_info);
1247 btrfs_cleanup_all_caches(fs_info);
1249 btrfs_close_devices(fs_info->fs_devices);
1251 btrfs_free_fs_info(fs_info);
1252 return ERR_PTR(ret);
1255 static int recover_prepare(struct recover_control *rc, char *path)
1259 struct btrfs_super_block *sb;
1260 struct btrfs_fs_devices *fs_devices;
1263 fd = open(path, O_RDONLY);
1265 fprintf(stderr, "open %s\n error.\n", path);
1269 sb = malloc(sizeof(struct btrfs_super_block));
1271 fprintf(stderr, "allocating memory for sb failed.\n");
1276 ret = btrfs_read_dev_super(fd, sb, BTRFS_SUPER_INFO_OFFSET);
1278 fprintf(stderr, "read super block error\n");
1282 rc->sectorsize = btrfs_super_sectorsize(sb);
1283 rc->leafsize = btrfs_super_leafsize(sb);
1284 rc->generation = btrfs_super_generation(sb);
1285 rc->chunk_root_generation = btrfs_super_chunk_root_generation(sb);
1286 rc->csum_size = btrfs_super_csum_size(sb);
1288 /* if seed, the result of scanning below will be partial */
1289 if (btrfs_super_flags(sb) & BTRFS_SUPER_FLAG_SEEDING) {
1290 fprintf(stderr, "this device is seed device\n");
1295 ret = btrfs_scan_fs_devices(fd, path, &fs_devices, 0);
1299 rc->fs_devices = fs_devices;
1302 print_all_devices(&rc->fs_devices->devices);
1312 * This reads a line from the stdin and only returns non-zero if the
1313 * first whitespace delimited token is a case insensitive match with yes
1316 static int ask_user(char *question)
1318 char buf[30] = {0,};
1319 char *saveptr = NULL;
1322 printf("%s [y/N]: ", question);
1324 return fgets(buf, sizeof(buf) - 1, stdin) &&
1325 (answer = strtok_r(buf, " \t\n\r", &saveptr)) &&
1326 (!strcasecmp(answer, "yes") || !strcasecmp(answer, "y"));
1329 static int btrfs_get_device_extents(u64 chunk_object,
1330 struct list_head *orphan_devexts,
1331 struct list_head *ret_list)
1333 struct device_extent_record *devext;
1334 struct device_extent_record *next;
1337 list_for_each_entry_safe(devext, next, orphan_devexts, chunk_list) {
1338 if (devext->chunk_offset == chunk_object) {
1339 list_move_tail(&devext->chunk_list, ret_list);
1346 static int calc_num_stripes(u64 type)
1348 if (type & (BTRFS_BLOCK_GROUP_RAID0 |
1349 BTRFS_BLOCK_GROUP_RAID10 |
1350 BTRFS_BLOCK_GROUP_RAID5 |
1351 BTRFS_BLOCK_GROUP_RAID6))
1353 else if (type & (BTRFS_BLOCK_GROUP_RAID1 |
1354 BTRFS_BLOCK_GROUP_DUP))
1360 static inline int calc_sub_nstripes(u64 type)
1362 if (type & BTRFS_BLOCK_GROUP_RAID10)
1368 static int btrfs_verify_device_extents(struct block_group_record *bg,
1369 struct list_head *devexts, int ndevexts)
1371 struct device_extent_record *devext;
1373 int expected_num_stripes;
1375 expected_num_stripes = calc_num_stripes(bg->flags);
1376 if (expected_num_stripes && expected_num_stripes != ndevexts)
1379 strpie_length = calc_stripe_length(bg->flags, bg->offset, ndevexts);
1380 list_for_each_entry(devext, devexts, chunk_list) {
1381 if (devext->length != strpie_length)
1387 static int btrfs_rebuild_unordered_chunk_stripes(struct recover_control *rc,
1388 struct chunk_record *chunk)
1390 struct device_extent_record *devext;
1391 struct btrfs_device *device;
1394 devext = list_first_entry(&chunk->dextents, struct device_extent_record,
1396 for (i = 0; i < chunk->num_stripes; i++) {
1397 chunk->stripes[i].devid = devext->objectid;
1398 chunk->stripes[i].offset = devext->offset;
1399 device = btrfs_find_device_by_devid(rc->fs_devices,
1404 BUG_ON(btrfs_find_device_by_devid(rc->fs_devices,
1407 memcpy(chunk->stripes[i].dev_uuid, device->uuid,
1409 devext = list_next_entry(devext, chunk_list);
1414 static int btrfs_calc_stripe_index(struct chunk_record *chunk, u64 logical)
1416 u64 offset = logical - chunk->offset;
1418 int nr_data_stripes;
1421 stripe_nr = offset / chunk->stripe_len;
1422 if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID0) {
1423 index = stripe_nr % chunk->num_stripes;
1424 } else if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID10) {
1425 index = stripe_nr % (chunk->num_stripes / chunk->sub_stripes);
1426 index *= chunk->sub_stripes;
1427 } else if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID5) {
1428 nr_data_stripes = chunk->num_stripes - 1;
1429 index = stripe_nr % nr_data_stripes;
1430 stripe_nr /= nr_data_stripes;
1431 index = (index + stripe_nr) % chunk->num_stripes;
1432 } else if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID6) {
1433 nr_data_stripes = chunk->num_stripes - 2;
1434 index = stripe_nr % nr_data_stripes;
1435 stripe_nr /= nr_data_stripes;
1436 index = (index + stripe_nr) % chunk->num_stripes;
1443 /* calc the logical offset which is the start of the next stripe. */
1444 static inline u64 btrfs_next_stripe_logical_offset(struct chunk_record *chunk,
1447 u64 offset = logical - chunk->offset;
1449 offset /= chunk->stripe_len;
1450 offset *= chunk->stripe_len;
1451 offset += chunk->stripe_len;
1453 return offset + chunk->offset;
1456 static int is_extent_record_in_device_extent(struct extent_record *er,
1457 struct device_extent_record *dext,
1462 for (i = 0; i < er->nmirrors; i++) {
1463 if (er->devices[i]->devid == dext->objectid &&
1464 er->offsets[i] >= dext->offset &&
1465 er->offsets[i] < dext->offset + dext->length) {
1474 btrfs_rebuild_ordered_meta_chunk_stripes(struct recover_control *rc,
1475 struct chunk_record *chunk)
1477 u64 start = chunk->offset;
1478 u64 end = chunk->offset + chunk->length;
1479 struct cache_extent *cache;
1480 struct extent_record *er;
1481 struct device_extent_record *devext;
1482 struct device_extent_record *next;
1483 struct btrfs_device *device;
1489 cache = lookup_cache_extent(&rc->eb_cache,
1490 start, chunk->length);
1492 /* No used space, we can reorder the stripes freely. */
1493 ret = btrfs_rebuild_unordered_chunk_stripes(rc, chunk);
1497 list_splice_init(&chunk->dextents, &devexts);
1499 er = container_of(cache, struct extent_record, cache);
1500 index = btrfs_calc_stripe_index(chunk, er->cache.start);
1501 if (chunk->stripes[index].devid)
1503 list_for_each_entry_safe(devext, next, &devexts, chunk_list) {
1504 if (is_extent_record_in_device_extent(er, devext, &mirror)) {
1505 chunk->stripes[index].devid = devext->objectid;
1506 chunk->stripes[index].offset = devext->offset;
1507 memcpy(chunk->stripes[index].dev_uuid,
1508 er->devices[mirror]->uuid,
1511 list_move(&devext->chunk_list, &chunk->dextents);
1515 start = btrfs_next_stripe_logical_offset(chunk, er->cache.start);
1517 goto no_extent_record;
1519 cache = lookup_cache_extent(&rc->eb_cache, start, end - start);
1523 if (list_empty(&devexts))
1526 if (chunk->type_flags & (BTRFS_BLOCK_GROUP_RAID5 |
1527 BTRFS_BLOCK_GROUP_RAID6)) {
1528 /* Fixme: try to recover the order by the parity block. */
1529 list_splice_tail(&devexts, &chunk->dextents);
1533 /* There is no data on the lost stripes, we can reorder them freely. */
1534 for (index = 0; index < chunk->num_stripes; index++) {
1535 if (chunk->stripes[index].devid)
1538 devext = list_first_entry(&devexts,
1539 struct device_extent_record,
1541 list_move(&devext->chunk_list, &chunk->dextents);
1543 chunk->stripes[index].devid = devext->objectid;
1544 chunk->stripes[index].offset = devext->offset;
1545 device = btrfs_find_device_by_devid(rc->fs_devices,
1549 list_splice_tail(&devexts, &chunk->dextents);
1552 BUG_ON(btrfs_find_device_by_devid(rc->fs_devices,
1555 memcpy(chunk->stripes[index].dev_uuid, device->uuid,
1561 #define BTRFS_ORDERED_RAID (BTRFS_BLOCK_GROUP_RAID0 | \
1562 BTRFS_BLOCK_GROUP_RAID10 | \
1563 BTRFS_BLOCK_GROUP_RAID5 | \
1564 BTRFS_BLOCK_GROUP_RAID6)
1566 static int btrfs_rebuild_chunk_stripes(struct recover_control *rc,
1567 struct chunk_record *chunk)
1572 * All the data in the system metadata chunk will be dropped,
1573 * so we need not guarantee that the data is right or not, that
1574 * is we can reorder the stripes in the system metadata chunk.
1576 if ((chunk->type_flags & BTRFS_BLOCK_GROUP_METADATA) &&
1577 (chunk->type_flags & BTRFS_ORDERED_RAID))
1578 ret =btrfs_rebuild_ordered_meta_chunk_stripes(rc, chunk);
1579 else if ((chunk->type_flags & BTRFS_BLOCK_GROUP_DATA) &&
1580 (chunk->type_flags & BTRFS_ORDERED_RAID))
1581 ret = 1; /* Be handled after the fs is opened. */
1583 ret = btrfs_rebuild_unordered_chunk_stripes(rc, chunk);
1588 static int btrfs_recover_chunks(struct recover_control *rc)
1590 struct chunk_record *chunk;
1591 struct block_group_record *bg;
1592 struct block_group_record *next;
1593 LIST_HEAD(new_chunks);
1598 /* create the chunk by block group */
1599 list_for_each_entry_safe(bg, next, &rc->bg.block_groups, list) {
1600 nstripes = btrfs_get_device_extents(bg->objectid,
1601 &rc->devext.no_chunk_orphans,
1603 chunk = malloc(btrfs_chunk_record_size(nstripes));
1606 memset(chunk, 0, btrfs_chunk_record_size(nstripes));
1607 INIT_LIST_HEAD(&chunk->dextents);
1609 chunk->cache.start = bg->objectid;
1610 chunk->cache.size = bg->offset;
1611 chunk->objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
1612 chunk->type = BTRFS_CHUNK_ITEM_KEY;
1613 chunk->offset = bg->objectid;
1614 chunk->generation = bg->generation;
1615 chunk->length = bg->offset;
1616 chunk->owner = BTRFS_CHUNK_TREE_OBJECTID;
1617 chunk->stripe_len = BTRFS_STRIPE_LEN;
1618 chunk->type_flags = bg->flags;
1619 chunk->io_width = BTRFS_STRIPE_LEN;
1620 chunk->io_align = BTRFS_STRIPE_LEN;
1621 chunk->sector_size = rc->sectorsize;
1622 chunk->sub_stripes = calc_sub_nstripes(bg->flags);
1624 ret = insert_cache_extent(&rc->chunk, &chunk->cache);
1628 list_add_tail(&chunk->list, &rc->bad_chunks);
1632 list_splice_init(&devexts, &chunk->dextents);
1634 ret = btrfs_verify_device_extents(bg, &devexts, nstripes);
1636 list_add_tail(&chunk->list, &rc->bad_chunks);
1640 chunk->num_stripes = nstripes;
1641 ret = btrfs_rebuild_chunk_stripes(rc, chunk);
1643 list_add_tail(&chunk->list, &rc->unrepaired_chunks);
1645 list_add_tail(&chunk->list, &rc->bad_chunks);
1647 list_add_tail(&chunk->list, &rc->good_chunks);
1650 * Don't worry about the lost orphan device extents, they don't
1651 * have its chunk and block group, they must be the old ones that
1657 static int btrfs_recover_chunk_tree(char *path, int verbose, int yes)
1660 struct btrfs_root *root = NULL;
1661 struct btrfs_trans_handle *trans;
1662 struct recover_control rc;
1664 init_recover_control(&rc, verbose, yes);
1666 ret = recover_prepare(&rc, path);
1668 fprintf(stderr, "recover prepare error\n");
1672 ret = scan_devices(&rc);
1674 fprintf(stderr, "scan chunk headers error\n");
1678 if (cache_tree_empty(&rc.chunk) &&
1679 cache_tree_empty(&rc.bg.tree) &&
1680 cache_tree_empty(&rc.devext.tree)) {
1681 fprintf(stderr, "no recoverable chunk\n");
1685 print_scan_result(&rc);
1687 ret = check_chunks(&rc.chunk, &rc.bg, &rc.devext, &rc.good_chunks,
1689 print_check_result(&rc);
1691 if (!list_empty(&rc.bg.block_groups) ||
1692 !list_empty(&rc.devext.no_chunk_orphans)) {
1693 ret = btrfs_recover_chunks(&rc);
1698 * If the chunk is healthy, its block group item and device
1699 * extent item should be written on the disks. So, it is very
1700 * likely that the bad chunk is a old one that has been
1701 * droppped from the fs. Don't deal with them now, we will
1702 * check it after the fs is opened.
1706 root = open_ctree_with_broken_chunk(&rc);
1708 fprintf(stderr, "open with broken chunk error\n");
1709 ret = PTR_ERR(root);
1713 ret = check_all_chunks_by_metadata(&rc, root);
1715 fprintf(stderr, "The chunks in memory can not match the metadata of the fs. Repair failed.\n");
1716 goto fail_close_ctree;
1720 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?");
1722 ret = BTRFS_CHUNK_TREE_REBUILD_ABORTED;
1723 goto fail_close_ctree;
1727 trans = btrfs_start_transaction(root, 1);
1728 ret = remove_chunk_extent_item(trans, &rc, root);
1731 ret = rebuild_chunk_tree(trans, &rc, root);
1734 ret = rebuild_sys_array(&rc, root);
1737 btrfs_commit_transaction(trans, root);
1741 free_recover_control(&rc);
1745 const char * const cmd_chunk_recover_usage[] = {
1746 "btrfs chunk-recover [options] <device>",
1747 "Recover the chunk tree by scanning the devices one by one.",
1749 "-y Assume an answer of `yes' to all questions",
1755 int cmd_chunk_recover(int argc, char *argv[])
1763 int c = getopt(argc, argv, "yvh");
1775 usage(cmd_chunk_recover_usage);
1779 argc = argc - optind;
1781 usage(cmd_chunk_recover_usage);
1783 file = argv[optind];
1785 ret = check_mounted(file);
1787 fprintf(stderr, "the device is busy\n");
1791 ret = btrfs_recover_chunk_tree(file, verbose, yes);
1793 fprintf(stdout, "Recover the chunk tree successfully.\n");
1794 } else if (ret == BTRFS_CHUNK_TREE_REBUILD_ABORTED) {
1796 fprintf(stdout, "Abort to rebuild the on-disk chunk tree.\n");
1798 fprintf(stdout, "Fail to recover the chunk tree.\n");