2 * Copyright (C) 2013 FUJITSU LIMITED. 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.
19 #include "kerncompat.h"
20 #include "androidcompat.h"
23 #include <stdio_ext.h>
25 #include <sys/types.h>
29 #include <uuid/uuid.h>
33 #include "radix-tree.h"
35 #include "extent-cache.h"
38 #include "transaction.h"
44 struct recover_control {
52 u64 chunk_root_generation;
54 struct btrfs_fs_devices *fs_devices;
56 struct cache_tree chunk;
57 struct block_group_tree bg;
58 struct device_extent_tree devext;
59 struct cache_tree eb_cache;
61 struct list_head good_chunks;
62 struct list_head bad_chunks;
63 struct list_head rebuild_chunks;
64 struct list_head unrepaired_chunks;
65 pthread_mutex_t rc_lock;
68 struct extent_record {
69 struct cache_extent cache;
71 u8 csum[BTRFS_CSUM_SIZE];
72 struct btrfs_device *devices[BTRFS_MAX_MIRRORS];
73 u64 offsets[BTRFS_MAX_MIRRORS];
78 struct recover_control *rc;
79 struct btrfs_device *dev;
84 static struct extent_record *btrfs_new_extent_record(struct extent_buffer *eb)
86 struct extent_record *rec;
88 rec = malloc(sizeof(*rec));
90 fprintf(stderr, "Fail to allocate memory for extent record.\n");
94 memset(rec, 0, sizeof(*rec));
95 rec->cache.start = btrfs_header_bytenr(eb);
96 rec->cache.size = eb->len;
97 rec->generation = btrfs_header_generation(eb);
98 read_extent_buffer(eb, rec->csum, (unsigned long)btrfs_header_csum(eb),
103 static int process_extent_buffer(struct cache_tree *eb_cache,
104 struct extent_buffer *eb,
105 struct btrfs_device *device, u64 offset)
107 struct extent_record *rec;
108 struct extent_record *exist;
109 struct cache_extent *cache;
112 rec = btrfs_new_extent_record(eb);
113 if (!rec->cache.size)
116 cache = lookup_cache_extent(eb_cache,
120 exist = container_of(cache, struct extent_record, cache);
122 if (exist->generation > rec->generation)
124 if (exist->generation == rec->generation) {
125 if (exist->cache.start != rec->cache.start ||
126 exist->cache.size != rec->cache.size ||
127 memcmp(exist->csum, rec->csum, BTRFS_CSUM_SIZE)) {
130 BUG_ON(exist->nmirrors >= BTRFS_MAX_MIRRORS);
131 exist->devices[exist->nmirrors] = device;
132 exist->offsets[exist->nmirrors] = offset;
137 remove_cache_extent(eb_cache, cache);
142 rec->devices[0] = device;
143 rec->offsets[0] = offset;
145 ret = insert_cache_extent(eb_cache, &rec->cache);
154 static void free_extent_record(struct cache_extent *cache)
156 struct extent_record *er;
158 er = container_of(cache, struct extent_record, cache);
162 FREE_EXTENT_CACHE_BASED_TREE(extent_record, free_extent_record);
164 static struct btrfs_chunk *create_chunk_item(struct chunk_record *record)
166 struct btrfs_chunk *ret;
167 struct btrfs_stripe *chunk_stripe;
170 if (!record || record->num_stripes == 0)
172 ret = malloc(btrfs_chunk_item_size(record->num_stripes));
175 btrfs_set_stack_chunk_length(ret, record->length);
176 btrfs_set_stack_chunk_owner(ret, record->owner);
177 btrfs_set_stack_chunk_stripe_len(ret, record->stripe_len);
178 btrfs_set_stack_chunk_type(ret, record->type_flags);
179 btrfs_set_stack_chunk_io_align(ret, record->io_align);
180 btrfs_set_stack_chunk_io_width(ret, record->io_width);
181 btrfs_set_stack_chunk_sector_size(ret, record->sector_size);
182 btrfs_set_stack_chunk_num_stripes(ret, record->num_stripes);
183 btrfs_set_stack_chunk_sub_stripes(ret, record->sub_stripes);
184 for (i = 0, chunk_stripe = &ret->stripe; i < record->num_stripes;
185 i++, chunk_stripe++) {
186 btrfs_set_stack_stripe_devid(chunk_stripe,
187 record->stripes[i].devid);
188 btrfs_set_stack_stripe_offset(chunk_stripe,
189 record->stripes[i].offset);
190 memcpy(chunk_stripe->dev_uuid, record->stripes[i].dev_uuid,
196 static void init_recover_control(struct recover_control *rc, int verbose,
199 memset(rc, 0, sizeof(struct recover_control));
200 cache_tree_init(&rc->chunk);
201 cache_tree_init(&rc->eb_cache);
202 block_group_tree_init(&rc->bg);
203 device_extent_tree_init(&rc->devext);
205 INIT_LIST_HEAD(&rc->good_chunks);
206 INIT_LIST_HEAD(&rc->bad_chunks);
207 INIT_LIST_HEAD(&rc->rebuild_chunks);
208 INIT_LIST_HEAD(&rc->unrepaired_chunks);
210 rc->verbose = verbose;
212 pthread_mutex_init(&rc->rc_lock, NULL);
215 static void free_recover_control(struct recover_control *rc)
217 free_block_group_tree(&rc->bg);
218 free_chunk_cache_tree(&rc->chunk);
219 free_device_extent_tree(&rc->devext);
220 free_extent_record_tree(&rc->eb_cache);
221 pthread_mutex_destroy(&rc->rc_lock);
224 static int process_block_group_item(struct block_group_tree *bg_cache,
225 struct extent_buffer *leaf,
226 struct btrfs_key *key, int slot)
228 struct block_group_record *rec;
229 struct block_group_record *exist;
230 struct cache_extent *cache;
233 rec = btrfs_new_block_group_record(leaf, key, slot);
234 if (!rec->cache.size)
237 cache = lookup_cache_extent(&bg_cache->tree,
241 exist = container_of(cache, struct block_group_record, cache);
243 /*check the generation and replace if needed*/
244 if (exist->generation > rec->generation)
246 if (exist->generation == rec->generation) {
247 int offset = offsetof(struct block_group_record,
250 * According to the current kernel code, the following
251 * case is impossble, or there is something wrong in
254 if (memcmp(((void *)exist) + offset,
255 ((void *)rec) + offset,
256 sizeof(*rec) - offset))
260 remove_cache_extent(&bg_cache->tree, cache);
261 list_del_init(&exist->list);
264 * We must do seach again to avoid the following cache.
265 * /--old bg 1--//--old bg 2--/
271 ret = insert_block_group_record(bg_cache, rec);
280 static int process_chunk_item(struct cache_tree *chunk_cache,
281 struct extent_buffer *leaf, struct btrfs_key *key,
284 struct chunk_record *rec;
285 struct chunk_record *exist;
286 struct cache_extent *cache;
289 rec = btrfs_new_chunk_record(leaf, key, slot);
290 if (!rec->cache.size)
293 cache = lookup_cache_extent(chunk_cache, rec->offset, rec->length);
295 exist = container_of(cache, struct chunk_record, cache);
297 if (exist->generation > rec->generation)
299 if (exist->generation == rec->generation) {
300 int num_stripes = rec->num_stripes;
301 int rec_size = btrfs_chunk_record_size(num_stripes);
302 int offset = offsetof(struct chunk_record, generation);
304 if (exist->num_stripes != rec->num_stripes ||
305 memcmp(((void *)exist) + offset,
306 ((void *)rec) + offset,
311 remove_cache_extent(chunk_cache, cache);
315 ret = insert_cache_extent(chunk_cache, &rec->cache);
324 static int process_device_extent_item(struct device_extent_tree *devext_cache,
325 struct extent_buffer *leaf,
326 struct btrfs_key *key, int slot)
328 struct device_extent_record *rec;
329 struct device_extent_record *exist;
330 struct cache_extent *cache;
333 rec = btrfs_new_device_extent_record(leaf, key, slot);
334 if (!rec->cache.size)
337 cache = lookup_cache_extent2(&devext_cache->tree,
342 exist = container_of(cache, struct device_extent_record, cache);
343 if (exist->generation > rec->generation)
345 if (exist->generation == rec->generation) {
346 int offset = offsetof(struct device_extent_record,
348 if (memcmp(((void *)exist) + offset,
349 ((void *)rec) + offset,
350 sizeof(*rec) - offset))
354 remove_cache_extent(&devext_cache->tree, cache);
355 list_del_init(&exist->chunk_list);
356 list_del_init(&exist->device_list);
361 ret = insert_device_extent_record(devext_cache, rec);
370 static void print_block_group_info(struct block_group_record *rec, char *prefix)
373 printf("%s", prefix);
374 printf("Block Group: start = %llu, len = %llu, flag = %llx\n",
375 rec->objectid, rec->offset, rec->flags);
378 static void print_block_group_tree(struct block_group_tree *tree)
380 struct cache_extent *cache;
381 struct block_group_record *rec;
383 printf("All Block Groups:\n");
384 for (cache = first_cache_extent(&tree->tree); cache;
385 cache = next_cache_extent(cache)) {
386 rec = container_of(cache, struct block_group_record, cache);
387 print_block_group_info(rec, "\t");
392 static void print_stripe_info(struct stripe *data, char *prefix1, char *prefix2,
396 printf("%s", prefix1);
398 printf("%s", prefix2);
399 printf("[%2d] Stripe: devid = %llu, offset = %llu\n",
400 index, data->devid, data->offset);
403 static void print_chunk_self_info(struct chunk_record *rec, char *prefix)
408 printf("%s", prefix);
409 printf("Chunk: start = %llu, len = %llu, type = %llx, num_stripes = %u\n",
410 rec->offset, rec->length, rec->type_flags, rec->num_stripes);
412 printf("%s", prefix);
413 printf(" Stripes list:\n");
414 for (i = 0; i < rec->num_stripes; i++)
415 print_stripe_info(&rec->stripes[i], prefix, " ", i);
418 static void print_chunk_tree(struct cache_tree *tree)
420 struct cache_extent *n;
421 struct chunk_record *entry;
423 printf("All Chunks:\n");
424 for (n = first_cache_extent(tree); n;
425 n = next_cache_extent(n)) {
426 entry = container_of(n, struct chunk_record, cache);
427 print_chunk_self_info(entry, "\t");
432 static void print_device_extent_info(struct device_extent_record *rec,
436 printf("%s", prefix);
437 printf("Device extent: devid = %llu, start = %llu, len = %llu, chunk offset = %llu\n",
438 rec->objectid, rec->offset, rec->length, rec->chunk_offset);
441 static void print_device_extent_tree(struct device_extent_tree *tree)
443 struct cache_extent *n;
444 struct device_extent_record *entry;
446 printf("All Device Extents:\n");
447 for (n = first_cache_extent(&tree->tree); n;
448 n = next_cache_extent(n)) {
449 entry = container_of(n, struct device_extent_record, cache);
450 print_device_extent_info(entry, "\t");
455 static void print_device_info(struct btrfs_device *device, char *prefix)
458 printf("%s", prefix);
459 printf("Device: id = %llu, name = %s\n",
460 device->devid, device->name);
463 static void print_all_devices(struct list_head *devices)
465 struct btrfs_device *dev;
467 printf("All Devices:\n");
468 list_for_each_entry(dev, devices, dev_list)
469 print_device_info(dev, "\t");
473 static void print_scan_result(struct recover_control *rc)
478 printf("DEVICE SCAN RESULT:\n");
479 printf("Filesystem Information:\n");
480 printf("\tsectorsize: %d\n", rc->sectorsize);
481 printf("\tleafsize: %d\n", rc->leafsize);
482 printf("\ttree root generation: %llu\n", rc->generation);
483 printf("\tchunk root generation: %llu\n", rc->chunk_root_generation);
486 print_all_devices(&rc->fs_devices->devices);
487 print_block_group_tree(&rc->bg);
488 print_chunk_tree(&rc->chunk);
489 print_device_extent_tree(&rc->devext);
492 static void print_chunk_info(struct chunk_record *chunk, char *prefix)
494 struct device_extent_record *devext;
497 print_chunk_self_info(chunk, prefix);
499 printf("%s", prefix);
501 print_block_group_info(chunk->bg_rec, " ");
503 printf(" No block group.\n");
505 printf("%s", prefix);
506 if (list_empty(&chunk->dextents)) {
507 printf(" No device extent.\n");
509 printf(" Device extent list:\n");
511 list_for_each_entry(devext, &chunk->dextents, chunk_list) {
513 printf("%s", prefix);
514 printf("%s[%2d]", " ", i);
515 print_device_extent_info(devext, NULL);
521 static void print_check_result(struct recover_control *rc)
523 struct chunk_record *chunk;
524 struct block_group_record *bg;
525 struct device_extent_record *devext;
533 printf("CHECK RESULT:\n");
534 printf("Recoverable Chunks:\n");
535 list_for_each_entry(chunk, &rc->good_chunks, list) {
536 print_chunk_info(chunk, " ");
540 list_for_each_entry(chunk, &rc->rebuild_chunks, list) {
541 print_chunk_info(chunk, " ");
545 list_for_each_entry(chunk, &rc->unrepaired_chunks, list) {
546 print_chunk_info(chunk, " ");
550 printf("Unrecoverable Chunks:\n");
551 list_for_each_entry(chunk, &rc->bad_chunks, list) {
552 print_chunk_info(chunk, " ");
557 printf("Total Chunks:\t\t%d\n", total);
558 printf(" Recoverable:\t\t%d\n", good);
559 printf(" Unrecoverable:\t%d\n", bad);
562 printf("Orphan Block Groups:\n");
563 list_for_each_entry(bg, &rc->bg.block_groups, list)
564 print_block_group_info(bg, " ");
567 printf("Orphan Device Extents:\n");
568 list_for_each_entry(devext, &rc->devext.no_chunk_orphans, chunk_list)
569 print_device_extent_info(devext, " ");
573 static int check_chunk_by_metadata(struct recover_control *rc,
574 struct btrfs_root *root,
575 struct chunk_record *chunk, int bg_only)
580 struct btrfs_path path;
581 struct btrfs_key key;
582 struct btrfs_root *dev_root;
583 struct stripe *stripe;
584 struct btrfs_dev_extent *dev_extent;
585 struct btrfs_block_group_item *bg_ptr;
586 struct extent_buffer *l;
588 btrfs_init_path(&path);
593 dev_root = root->fs_info->dev_root;
594 for (i = 0; i < chunk->num_stripes; i++) {
595 stripe = &chunk->stripes[i];
597 key.objectid = stripe->devid;
598 key.offset = stripe->offset;
599 key.type = BTRFS_DEV_EXTENT_KEY;
601 ret = btrfs_search_slot(NULL, dev_root, &key, &path, 0, 0);
603 fprintf(stderr, "Search device extent failed(%d)\n",
605 btrfs_release_path(&path);
607 } else if (ret > 0) {
610 "No device extent[%llu, %llu]\n",
611 stripe->devid, stripe->offset);
612 btrfs_release_path(&path);
616 slot = path.slots[0];
617 dev_extent = btrfs_item_ptr(l, slot, struct btrfs_dev_extent);
619 btrfs_dev_extent_chunk_offset(l, dev_extent)) {
622 "Device tree unmatch with chunks dev_extent[%llu, %llu], chunk[%llu, %llu]\n",
623 btrfs_dev_extent_chunk_offset(l,
625 btrfs_dev_extent_length(l, dev_extent),
626 chunk->offset, chunk->length);
627 btrfs_release_path(&path);
630 btrfs_release_path(&path);
634 key.objectid = chunk->offset;
635 key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
636 key.offset = chunk->length;
638 ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, &path,
641 fprintf(stderr, "Search block group failed(%d)\n", ret);
642 btrfs_release_path(&path);
644 } else if (ret > 0) {
646 fprintf(stderr, "No block group[%llu, %llu]\n",
647 key.objectid, key.offset);
648 btrfs_release_path(&path);
653 slot = path.slots[0];
654 bg_ptr = btrfs_item_ptr(l, slot, struct btrfs_block_group_item);
655 if (chunk->type_flags != btrfs_disk_block_group_flags(l, bg_ptr)) {
658 "Chunk[%llu, %llu]'s type(%llu) is differemt with Block Group's type(%llu)\n",
659 chunk->offset, chunk->length, chunk->type_flags,
660 btrfs_disk_block_group_flags(l, bg_ptr));
661 btrfs_release_path(&path);
664 btrfs_release_path(&path);
668 static int check_all_chunks_by_metadata(struct recover_control *rc,
669 struct btrfs_root *root)
671 struct chunk_record *chunk;
672 struct chunk_record *next;
673 LIST_HEAD(orphan_chunks);
677 list_for_each_entry_safe(chunk, next, &rc->good_chunks, list) {
678 err = check_chunk_by_metadata(rc, root, chunk, 0);
681 list_move_tail(&chunk->list, &orphan_chunks);
682 else if (err && !ret)
687 list_for_each_entry_safe(chunk, next, &rc->unrepaired_chunks, list) {
688 err = check_chunk_by_metadata(rc, root, chunk, 1);
690 list_move_tail(&chunk->list, &orphan_chunks);
691 else if (err && !ret)
695 list_for_each_entry(chunk, &rc->bad_chunks, list) {
696 err = check_chunk_by_metadata(rc, root, chunk, 1);
697 if (err != -ENOENT && !ret)
698 ret = err ? err : -EINVAL;
700 list_splice(&orphan_chunks, &rc->bad_chunks);
704 static int extract_metadata_record(struct recover_control *rc,
705 struct extent_buffer *leaf)
707 struct btrfs_key key;
712 nritems = btrfs_header_nritems(leaf);
713 for (i = 0; i < nritems; i++) {
714 btrfs_item_key_to_cpu(leaf, &key, i);
716 case BTRFS_BLOCK_GROUP_ITEM_KEY:
717 pthread_mutex_lock(&rc->rc_lock);
718 ret = process_block_group_item(&rc->bg, leaf, &key, i);
719 pthread_mutex_unlock(&rc->rc_lock);
721 case BTRFS_CHUNK_ITEM_KEY:
722 pthread_mutex_lock(&rc->rc_lock);
723 ret = process_chunk_item(&rc->chunk, leaf, &key, i);
724 pthread_mutex_unlock(&rc->rc_lock);
726 case BTRFS_DEV_EXTENT_KEY:
727 pthread_mutex_lock(&rc->rc_lock);
728 ret = process_device_extent_item(&rc->devext, leaf,
730 pthread_mutex_unlock(&rc->rc_lock);
739 static inline int is_super_block_address(u64 offset)
743 for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
744 if (offset == btrfs_sb_offset(i))
750 static int scan_one_device(void *dev_scan_struct)
752 struct extent_buffer *buf;
755 struct device_scan *dev_scan = (struct device_scan *)dev_scan_struct;
756 struct recover_control *rc = dev_scan->rc;
757 struct btrfs_device *device = dev_scan->dev;
758 int fd = dev_scan->fd;
761 ret = pthread_setcanceltype(PTHREAD_CANCEL_ASYNCHRONOUS, &oldtype);
765 buf = malloc(sizeof(*buf) + rc->leafsize);
768 buf->len = rc->leafsize;
772 dev_scan->bytenr = bytenr;
774 if (is_super_block_address(bytenr))
775 bytenr += rc->sectorsize;
777 if (pread64(fd, buf->data, rc->leafsize, bytenr) <
781 if (memcmp_extent_buffer(buf, rc->fs_devices->fsid,
784 bytenr += rc->sectorsize;
788 if (verify_tree_block_csum_silent(buf, rc->csum_size)) {
789 bytenr += rc->sectorsize;
793 pthread_mutex_lock(&rc->rc_lock);
794 ret = process_extent_buffer(&rc->eb_cache, buf, device, bytenr);
795 pthread_mutex_unlock(&rc->rc_lock);
799 if (btrfs_header_level(buf) != 0)
802 switch (btrfs_header_owner(buf)) {
803 case BTRFS_EXTENT_TREE_OBJECTID:
804 case BTRFS_DEV_TREE_OBJECTID:
805 /* different tree use different generation */
806 if (btrfs_header_generation(buf) > rc->generation)
808 ret = extract_metadata_record(rc, buf);
812 case BTRFS_CHUNK_TREE_OBJECTID:
813 if (btrfs_header_generation(buf) >
814 rc->chunk_root_generation)
816 ret = extract_metadata_record(rc, buf);
822 bytenr += rc->leafsize;
830 static int scan_devices(struct recover_control *rc)
834 struct btrfs_device *dev;
835 struct device_scan *dev_scans;
843 list_for_each_entry(dev, &rc->fs_devices->devices, dev_list)
845 dev_scans = (struct device_scan *)malloc(sizeof(struct device_scan)
849 t_scans = (pthread_t *)malloc(sizeof(pthread_t) * devnr);
852 t_rets = (long *)malloc(sizeof(long) * devnr);
856 list_for_each_entry(dev, &rc->fs_devices->devices, dev_list) {
857 fd = open(dev->name, O_RDONLY);
859 fprintf(stderr, "Failed to open device %s\n",
864 dev_scans[devidx].rc = rc;
865 dev_scans[devidx].dev = dev;
866 dev_scans[devidx].fd = fd;
867 dev_scans[devidx].bytenr = -1;
871 for (i = 0; i < devidx; i++) {
872 ret = pthread_create(&t_scans[i], NULL,
873 (void *)scan_one_device,
874 (void *)&dev_scans[i]);
878 dev_scans[i].bytenr = 0;
883 for (i = 0; i < devidx; i++) {
884 if (dev_scans[i].bytenr == -1)
886 ret = pthread_tryjoin_np(t_scans[i],
887 (void **)&t_rets[i]);
892 if (ret || t_rets[i]) {
896 dev_scans[i].bytenr = -1;
899 printf("\rScanning: ");
900 for (i = 0; i < devidx; i++) {
901 if (dev_scans[i].bytenr == -1)
902 printf("%sDONE in dev%d",
905 printf("%s%llu in dev%d",
906 i ? ", " : "", dev_scans[i].bytenr, i);
908 /* clear chars if exist in tail */
910 printf("\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b");
921 for (i = 0; i < devidx; i++) {
922 if (dev_scans[i].bytenr == -1)
924 pthread_cancel(t_scans[i]);
933 static int build_device_map_by_chunk_record(struct btrfs_root *root,
934 struct chunk_record *chunk)
939 u8 uuid[BTRFS_UUID_SIZE];
941 struct btrfs_mapping_tree *map_tree;
942 struct map_lookup *map;
943 struct stripe *stripe;
945 map_tree = &root->fs_info->mapping_tree;
946 num_stripes = chunk->num_stripes;
947 map = malloc(btrfs_map_lookup_size(num_stripes));
950 map->ce.start = chunk->offset;
951 map->ce.size = chunk->length;
952 map->num_stripes = num_stripes;
953 map->io_width = chunk->io_width;
954 map->io_align = chunk->io_align;
955 map->sector_size = chunk->sector_size;
956 map->stripe_len = chunk->stripe_len;
957 map->type = chunk->type_flags;
958 map->sub_stripes = chunk->sub_stripes;
960 for (i = 0, stripe = chunk->stripes; i < num_stripes; i++, stripe++) {
961 devid = stripe->devid;
962 memcpy(uuid, stripe->dev_uuid, BTRFS_UUID_SIZE);
963 map->stripes[i].physical = stripe->offset;
964 map->stripes[i].dev = btrfs_find_device(root, devid,
966 if (!map->stripes[i].dev) {
972 ret = insert_cache_extent(&map_tree->cache_tree, &map->ce);
976 static int build_device_maps_by_chunk_records(struct recover_control *rc,
977 struct btrfs_root *root)
980 struct chunk_record *chunk;
982 list_for_each_entry(chunk, &rc->good_chunks, list) {
983 ret = build_device_map_by_chunk_record(root, chunk);
987 list_for_each_entry(chunk, &rc->rebuild_chunks, list) {
988 ret = build_device_map_by_chunk_record(root, chunk);
995 static int block_group_remove_all_extent_items(struct btrfs_trans_handle *trans,
996 struct btrfs_root *root,
997 struct block_group_record *bg)
999 struct btrfs_fs_info *fs_info = root->fs_info;
1000 struct btrfs_key key;
1001 struct btrfs_path path;
1002 struct extent_buffer *leaf;
1003 u64 start = bg->objectid;
1004 u64 end = bg->objectid + bg->offset;
1011 btrfs_init_path(&path);
1012 root = root->fs_info->extent_root;
1014 key.objectid = start;
1016 key.type = BTRFS_EXTENT_ITEM_KEY;
1018 ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
1024 leaf = path.nodes[0];
1025 nitems = btrfs_header_nritems(leaf);
1027 /* The tree is empty. */
1032 if (path.slots[0] >= nitems) {
1033 ret = btrfs_next_leaf(root, &path);
1040 leaf = path.nodes[0];
1041 btrfs_item_key_to_cpu(leaf, &key, 0);
1042 if (key.objectid >= end)
1044 btrfs_release_path(&path);
1050 for (i = path.slots[0]; i < nitems; i++) {
1051 btrfs_item_key_to_cpu(leaf, &key, i);
1052 if (key.objectid >= end)
1055 if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
1065 if (key.type == BTRFS_EXTENT_ITEM_KEY ||
1066 key.type == BTRFS_METADATA_ITEM_KEY) {
1067 old_val = btrfs_super_bytes_used(fs_info->super_copy);
1068 if (key.type == BTRFS_METADATA_ITEM_KEY)
1069 old_val += root->leafsize;
1071 old_val += key.offset;
1072 btrfs_set_super_bytes_used(fs_info->super_copy,
1078 ret = btrfs_del_items(trans, root, &path, del_s, del_nr);
1083 if (key.objectid < end) {
1084 if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
1085 key.objectid += root->sectorsize;
1086 key.type = BTRFS_EXTENT_ITEM_KEY;
1089 btrfs_release_path(&path);
1093 btrfs_release_path(&path);
1097 static int block_group_free_all_extent(struct btrfs_trans_handle *trans,
1098 struct btrfs_root *root,
1099 struct block_group_record *bg)
1101 struct btrfs_block_group_cache *cache;
1102 struct btrfs_fs_info *info;
1106 info = root->fs_info;
1107 cache = btrfs_lookup_block_group(info, bg->objectid);
1111 start = cache->key.objectid;
1112 end = start + cache->key.offset - 1;
1114 set_extent_bits(&info->block_group_cache, start, end,
1115 BLOCK_GROUP_DIRTY, GFP_NOFS);
1116 set_extent_dirty(&info->free_space_cache, start, end, GFP_NOFS);
1118 btrfs_set_block_group_used(&cache->item, 0);
1123 static int remove_chunk_extent_item(struct btrfs_trans_handle *trans,
1124 struct recover_control *rc,
1125 struct btrfs_root *root)
1127 struct chunk_record *chunk;
1130 list_for_each_entry(chunk, &rc->good_chunks, list) {
1131 if (!(chunk->type_flags & BTRFS_BLOCK_GROUP_SYSTEM))
1133 ret = block_group_remove_all_extent_items(trans, root,
1138 ret = block_group_free_all_extent(trans, root, chunk->bg_rec);
1145 static int __rebuild_chunk_root(struct btrfs_trans_handle *trans,
1146 struct recover_control *rc,
1147 struct btrfs_root *root)
1150 struct btrfs_device *dev;
1151 struct extent_buffer *cow;
1152 struct btrfs_disk_key disk_key;
1155 list_for_each_entry(dev, &rc->fs_devices->devices, dev_list) {
1156 if (min_devid > dev->devid)
1157 min_devid = dev->devid;
1159 disk_key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
1160 disk_key.type = BTRFS_DEV_ITEM_KEY;
1161 disk_key.offset = min_devid;
1163 cow = btrfs_alloc_free_block(trans, root, root->nodesize,
1164 BTRFS_CHUNK_TREE_OBJECTID,
1165 &disk_key, 0, 0, 0);
1166 btrfs_set_header_bytenr(cow, cow->start);
1167 btrfs_set_header_generation(cow, trans->transid);
1168 btrfs_set_header_nritems(cow, 0);
1169 btrfs_set_header_level(cow, 0);
1170 btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
1171 btrfs_set_header_owner(cow, BTRFS_CHUNK_TREE_OBJECTID);
1172 write_extent_buffer(cow, root->fs_info->fsid,
1173 btrfs_header_fsid(), BTRFS_FSID_SIZE);
1175 write_extent_buffer(cow, root->fs_info->chunk_tree_uuid,
1176 btrfs_header_chunk_tree_uuid(cow),
1180 btrfs_mark_buffer_dirty(cow);
1185 static int __rebuild_device_items(struct btrfs_trans_handle *trans,
1186 struct recover_control *rc,
1187 struct btrfs_root *root)
1189 struct btrfs_device *dev;
1190 struct btrfs_key key;
1191 struct btrfs_dev_item *dev_item;
1194 dev_item = malloc(sizeof(struct btrfs_dev_item));
1198 list_for_each_entry(dev, &rc->fs_devices->devices, dev_list) {
1199 key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
1200 key.type = BTRFS_DEV_ITEM_KEY;
1201 key.offset = dev->devid;
1203 btrfs_set_stack_device_generation(dev_item, 0);
1204 btrfs_set_stack_device_type(dev_item, dev->type);
1205 btrfs_set_stack_device_id(dev_item, dev->devid);
1206 btrfs_set_stack_device_total_bytes(dev_item, dev->total_bytes);
1207 btrfs_set_stack_device_bytes_used(dev_item, dev->bytes_used);
1208 btrfs_set_stack_device_io_align(dev_item, dev->io_align);
1209 btrfs_set_stack_device_io_width(dev_item, dev->io_width);
1210 btrfs_set_stack_device_sector_size(dev_item, dev->sector_size);
1211 memcpy(dev_item->uuid, dev->uuid, BTRFS_UUID_SIZE);
1212 memcpy(dev_item->fsid, dev->fs_devices->fsid, BTRFS_UUID_SIZE);
1214 ret = btrfs_insert_item(trans, root, &key,
1215 dev_item, sizeof(*dev_item));
1222 static int __insert_chunk_item(struct btrfs_trans_handle *trans,
1223 struct chunk_record *chunk_rec,
1224 struct btrfs_root *chunk_root)
1226 struct btrfs_key key;
1227 struct btrfs_chunk *chunk = NULL;
1230 chunk = create_chunk_item(chunk_rec);
1233 key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
1234 key.type = BTRFS_CHUNK_ITEM_KEY;
1235 key.offset = chunk_rec->offset;
1237 ret = btrfs_insert_item(trans, chunk_root, &key, chunk,
1238 btrfs_chunk_item_size(chunk->num_stripes));
1243 static int __rebuild_chunk_items(struct btrfs_trans_handle *trans,
1244 struct recover_control *rc,
1245 struct btrfs_root *root)
1247 struct btrfs_root *chunk_root;
1248 struct chunk_record *chunk_rec;
1251 chunk_root = root->fs_info->chunk_root;
1253 list_for_each_entry(chunk_rec, &rc->good_chunks, list) {
1254 ret = __insert_chunk_item(trans, chunk_rec, chunk_root);
1258 list_for_each_entry(chunk_rec, &rc->rebuild_chunks, list) {
1259 ret = __insert_chunk_item(trans, chunk_rec, chunk_root);
1266 static int rebuild_chunk_tree(struct btrfs_trans_handle *trans,
1267 struct recover_control *rc,
1268 struct btrfs_root *root)
1272 root = root->fs_info->chunk_root;
1274 ret = __rebuild_chunk_root(trans, rc, root);
1278 ret = __rebuild_device_items(trans, rc, root);
1282 ret = __rebuild_chunk_items(trans, rc, root);
1287 static int rebuild_sys_array(struct recover_control *rc,
1288 struct btrfs_root *root)
1290 struct btrfs_chunk *chunk;
1291 struct btrfs_key key;
1292 struct chunk_record *chunk_rec;
1296 btrfs_set_super_sys_array_size(root->fs_info->super_copy, 0);
1298 list_for_each_entry(chunk_rec, &rc->good_chunks, list) {
1299 if (!(chunk_rec->type_flags & BTRFS_BLOCK_GROUP_SYSTEM))
1302 num_stripes = chunk_rec->num_stripes;
1303 chunk = create_chunk_item(chunk_rec);
1309 key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
1310 key.type = BTRFS_CHUNK_ITEM_KEY;
1311 key.offset = chunk_rec->offset;
1313 ret = btrfs_add_system_chunk(NULL, root, &key, chunk,
1314 btrfs_chunk_item_size(num_stripes));
1323 static int calculate_bg_used(struct btrfs_root *extent_root,
1324 struct chunk_record *chunk_rec,
1325 struct btrfs_path *path,
1328 struct extent_buffer *node;
1329 struct btrfs_key found_key;
1335 node = path->nodes[0];
1336 slot = path->slots[0];
1337 btrfs_item_key_to_cpu(node, &found_key, slot);
1338 if (found_key.objectid >= chunk_rec->offset + chunk_rec->length)
1340 if (found_key.type != BTRFS_METADATA_ITEM_KEY &&
1341 found_key.type != BTRFS_EXTENT_DATA_KEY)
1343 if (found_key.type == BTRFS_METADATA_ITEM_KEY)
1344 used_ret += extent_root->nodesize;
1346 used_ret += found_key.offset;
1348 if (slot + 1 < btrfs_header_nritems(node)) {
1351 ret = btrfs_next_leaf(extent_root, path);
1365 static int __insert_block_group(struct btrfs_trans_handle *trans,
1366 struct chunk_record *chunk_rec,
1367 struct btrfs_root *extent_root,
1370 struct btrfs_block_group_item bg_item;
1371 struct btrfs_key key;
1374 btrfs_set_block_group_used(&bg_item, used);
1375 btrfs_set_block_group_chunk_objectid(&bg_item, used);
1376 btrfs_set_block_group_flags(&bg_item, chunk_rec->type_flags);
1377 key.objectid = chunk_rec->offset;
1378 key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
1379 key.offset = chunk_rec->length;
1381 ret = btrfs_insert_item(trans, extent_root, &key, &bg_item,
1387 * Search through the extent tree to rebuild the 'used' member of the block
1389 * However, since block group and extent item shares the extent tree,
1390 * the extent item may also missing.
1391 * In that case, we fill the 'used' with the length of the block group to
1392 * ensure no write into the block group.
1393 * Btrfsck will hate it but we will inform user to call '--init-extent-tree'
1394 * if possible, or just salvage as much data as possible from the fs.
1396 static int rebuild_block_group(struct btrfs_trans_handle *trans,
1397 struct recover_control *rc,
1398 struct btrfs_root *root)
1400 struct chunk_record *chunk_rec;
1401 struct btrfs_key search_key;
1402 struct btrfs_path *path;
1406 if (list_empty(&rc->rebuild_chunks))
1409 path = btrfs_alloc_path();
1412 list_for_each_entry(chunk_rec, &rc->rebuild_chunks, list) {
1413 search_key.objectid = chunk_rec->offset;
1414 search_key.type = BTRFS_EXTENT_ITEM_KEY;
1415 search_key.offset = 0;
1416 ret = btrfs_search_slot(NULL, root->fs_info->extent_root,
1417 &search_key, path, 0, 0);
1420 ret = calculate_bg_used(root->fs_info->extent_root,
1421 chunk_rec, path, &used);
1423 * Extent tree is damaged, better to rebuild the whole extent
1424 * tree. Currently, change the used to chunk's len to prevent
1425 * write/block reserve happening in that block group.
1429 "Fail to search extent tree for block group: [%llu,%llu]\n",
1431 chunk_rec->offset + chunk_rec->length);
1433 "Mark the block group full to prevent block rsv problems\n");
1434 used = chunk_rec->length;
1436 btrfs_release_path(path);
1437 ret = __insert_block_group(trans, chunk_rec,
1438 root->fs_info->extent_root,
1444 btrfs_free_path(path);
1448 static struct btrfs_root *
1449 open_ctree_with_broken_chunk(struct recover_control *rc)
1451 struct btrfs_fs_info *fs_info;
1452 struct btrfs_super_block *disk_super;
1453 struct extent_buffer *eb;
1460 fs_info = btrfs_new_fs_info(1, BTRFS_SUPER_INFO_OFFSET);
1462 fprintf(stderr, "Failed to allocate memory for fs_info\n");
1463 return ERR_PTR(-ENOMEM);
1465 fs_info->is_chunk_recover = 1;
1467 fs_info->fs_devices = rc->fs_devices;
1468 ret = btrfs_open_devices(fs_info->fs_devices, O_RDWR);
1472 disk_super = fs_info->super_copy;
1473 ret = btrfs_read_dev_super(fs_info->fs_devices->latest_bdev,
1474 disk_super, fs_info->super_bytenr, 1);
1476 fprintf(stderr, "No valid btrfs found\n");
1480 memcpy(fs_info->fsid, &disk_super->fsid, BTRFS_FSID_SIZE);
1482 ret = btrfs_check_fs_compatibility(disk_super, 1);
1486 nodesize = btrfs_super_nodesize(disk_super);
1487 leafsize = btrfs_super_leafsize(disk_super);
1488 sectorsize = btrfs_super_sectorsize(disk_super);
1489 stripesize = btrfs_super_stripesize(disk_super);
1491 __setup_root(nodesize, leafsize, sectorsize, stripesize,
1492 fs_info->chunk_root, fs_info, BTRFS_CHUNK_TREE_OBJECTID);
1494 ret = build_device_maps_by_chunk_records(rc, fs_info->chunk_root);
1498 ret = btrfs_setup_all_roots(fs_info, 0, 0);
1502 eb = fs_info->tree_root->node;
1503 read_extent_buffer(eb, fs_info->chunk_tree_uuid,
1504 btrfs_header_chunk_tree_uuid(eb),
1507 return fs_info->fs_root;
1509 btrfs_release_all_roots(fs_info);
1511 btrfs_cleanup_all_caches(fs_info);
1513 btrfs_close_devices(fs_info->fs_devices);
1515 btrfs_free_fs_info(fs_info);
1516 return ERR_PTR(ret);
1519 static int recover_prepare(struct recover_control *rc, char *path)
1523 struct btrfs_super_block *sb;
1524 struct btrfs_fs_devices *fs_devices;
1527 fd = open(path, O_RDONLY);
1529 fprintf(stderr, "open %s\n error.\n", path);
1533 sb = malloc(BTRFS_SUPER_INFO_SIZE);
1535 fprintf(stderr, "allocating memory for sb failed.\n");
1540 ret = btrfs_read_dev_super(fd, sb, BTRFS_SUPER_INFO_OFFSET, 1);
1542 fprintf(stderr, "read super block error\n");
1546 rc->sectorsize = btrfs_super_sectorsize(sb);
1547 rc->leafsize = btrfs_super_leafsize(sb);
1548 rc->generation = btrfs_super_generation(sb);
1549 rc->chunk_root_generation = btrfs_super_chunk_root_generation(sb);
1550 rc->csum_size = btrfs_super_csum_size(sb);
1552 /* if seed, the result of scanning below will be partial */
1553 if (btrfs_super_flags(sb) & BTRFS_SUPER_FLAG_SEEDING) {
1554 fprintf(stderr, "this device is seed device\n");
1559 ret = btrfs_scan_fs_devices(fd, path, &fs_devices, 0, 1, 0);
1563 rc->fs_devices = fs_devices;
1566 print_all_devices(&rc->fs_devices->devices);
1575 static int btrfs_get_device_extents(u64 chunk_object,
1576 struct list_head *orphan_devexts,
1577 struct list_head *ret_list)
1579 struct device_extent_record *devext;
1580 struct device_extent_record *next;
1583 list_for_each_entry_safe(devext, next, orphan_devexts, chunk_list) {
1584 if (devext->chunk_offset == chunk_object) {
1585 list_move_tail(&devext->chunk_list, ret_list);
1592 static int calc_num_stripes(u64 type)
1594 if (type & (BTRFS_BLOCK_GROUP_RAID0 |
1595 BTRFS_BLOCK_GROUP_RAID10 |
1596 BTRFS_BLOCK_GROUP_RAID5 |
1597 BTRFS_BLOCK_GROUP_RAID6))
1599 else if (type & (BTRFS_BLOCK_GROUP_RAID1 |
1600 BTRFS_BLOCK_GROUP_DUP))
1606 static inline int calc_sub_nstripes(u64 type)
1608 if (type & BTRFS_BLOCK_GROUP_RAID10)
1614 static int btrfs_verify_device_extents(struct block_group_record *bg,
1615 struct list_head *devexts, int ndevexts)
1617 struct device_extent_record *devext;
1619 int expected_num_stripes;
1621 expected_num_stripes = calc_num_stripes(bg->flags);
1622 if (expected_num_stripes && expected_num_stripes != ndevexts)
1625 strpie_length = calc_stripe_length(bg->flags, bg->offset, ndevexts);
1626 list_for_each_entry(devext, devexts, chunk_list) {
1627 if (devext->length != strpie_length)
1633 static int btrfs_rebuild_unordered_chunk_stripes(struct recover_control *rc,
1634 struct chunk_record *chunk)
1636 struct device_extent_record *devext;
1637 struct btrfs_device *device;
1640 devext = list_first_entry(&chunk->dextents, struct device_extent_record,
1642 for (i = 0; i < chunk->num_stripes; i++) {
1643 chunk->stripes[i].devid = devext->objectid;
1644 chunk->stripes[i].offset = devext->offset;
1645 device = btrfs_find_device_by_devid(rc->fs_devices,
1650 BUG_ON(btrfs_find_device_by_devid(rc->fs_devices,
1653 memcpy(chunk->stripes[i].dev_uuid, device->uuid,
1655 devext = list_next_entry(devext, chunk_list);
1660 static int btrfs_calc_stripe_index(struct chunk_record *chunk, u64 logical)
1662 u64 offset = logical - chunk->offset;
1664 int nr_data_stripes;
1667 stripe_nr = offset / chunk->stripe_len;
1668 if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID0) {
1669 index = stripe_nr % chunk->num_stripes;
1670 } else if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID10) {
1671 index = stripe_nr % (chunk->num_stripes / chunk->sub_stripes);
1672 index *= chunk->sub_stripes;
1673 } else if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID5) {
1674 nr_data_stripes = chunk->num_stripes - 1;
1675 index = stripe_nr % nr_data_stripes;
1676 stripe_nr /= nr_data_stripes;
1677 index = (index + stripe_nr) % chunk->num_stripes;
1678 } else if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID6) {
1679 nr_data_stripes = chunk->num_stripes - 2;
1680 index = stripe_nr % nr_data_stripes;
1681 stripe_nr /= nr_data_stripes;
1682 index = (index + stripe_nr) % chunk->num_stripes;
1689 /* calc the logical offset which is the start of the next stripe. */
1690 static inline u64 btrfs_next_stripe_logical_offset(struct chunk_record *chunk,
1693 u64 offset = logical - chunk->offset;
1695 offset /= chunk->stripe_len;
1696 offset *= chunk->stripe_len;
1697 offset += chunk->stripe_len;
1699 return offset + chunk->offset;
1702 static int is_extent_record_in_device_extent(struct extent_record *er,
1703 struct device_extent_record *dext,
1708 for (i = 0; i < er->nmirrors; i++) {
1709 if (er->devices[i]->devid == dext->objectid &&
1710 er->offsets[i] >= dext->offset &&
1711 er->offsets[i] < dext->offset + dext->length) {
1720 btrfs_rebuild_ordered_meta_chunk_stripes(struct recover_control *rc,
1721 struct chunk_record *chunk)
1723 u64 start = chunk->offset;
1724 u64 end = chunk->offset + chunk->length;
1725 struct cache_extent *cache;
1726 struct extent_record *er;
1727 struct device_extent_record *devext;
1728 struct device_extent_record *next;
1729 struct btrfs_device *device;
1735 cache = lookup_cache_extent(&rc->eb_cache,
1736 start, chunk->length);
1738 /* No used space, we can reorder the stripes freely. */
1739 ret = btrfs_rebuild_unordered_chunk_stripes(rc, chunk);
1743 list_splice_init(&chunk->dextents, &devexts);
1745 er = container_of(cache, struct extent_record, cache);
1746 index = btrfs_calc_stripe_index(chunk, er->cache.start);
1747 BUG_ON(index == -1);
1748 if (chunk->stripes[index].devid)
1750 list_for_each_entry_safe(devext, next, &devexts, chunk_list) {
1751 if (is_extent_record_in_device_extent(er, devext, &mirror)) {
1752 chunk->stripes[index].devid = devext->objectid;
1753 chunk->stripes[index].offset = devext->offset;
1754 memcpy(chunk->stripes[index].dev_uuid,
1755 er->devices[mirror]->uuid,
1758 list_move(&devext->chunk_list, &chunk->dextents);
1762 start = btrfs_next_stripe_logical_offset(chunk, er->cache.start);
1764 goto no_extent_record;
1766 cache = lookup_cache_extent(&rc->eb_cache, start, end - start);
1770 if (list_empty(&devexts))
1773 if (chunk->type_flags & (BTRFS_BLOCK_GROUP_RAID5 |
1774 BTRFS_BLOCK_GROUP_RAID6)) {
1775 /* Fixme: try to recover the order by the parity block. */
1776 list_splice_tail(&devexts, &chunk->dextents);
1780 /* There is no data on the lost stripes, we can reorder them freely. */
1781 for (index = 0; index < chunk->num_stripes; index++) {
1782 if (chunk->stripes[index].devid)
1785 devext = list_first_entry(&devexts,
1786 struct device_extent_record,
1788 list_move(&devext->chunk_list, &chunk->dextents);
1790 chunk->stripes[index].devid = devext->objectid;
1791 chunk->stripes[index].offset = devext->offset;
1792 device = btrfs_find_device_by_devid(rc->fs_devices,
1796 list_splice_tail(&devexts, &chunk->dextents);
1799 BUG_ON(btrfs_find_device_by_devid(rc->fs_devices,
1802 memcpy(chunk->stripes[index].dev_uuid, device->uuid,
1808 #define BTRFS_ORDERED_RAID (BTRFS_BLOCK_GROUP_RAID0 | \
1809 BTRFS_BLOCK_GROUP_RAID10 | \
1810 BTRFS_BLOCK_GROUP_RAID5 | \
1811 BTRFS_BLOCK_GROUP_RAID6)
1813 static int btrfs_rebuild_chunk_stripes(struct recover_control *rc,
1814 struct chunk_record *chunk)
1819 * All the data in the system metadata chunk will be dropped,
1820 * so we need not guarantee that the data is right or not, that
1821 * is we can reorder the stripes in the system metadata chunk.
1823 if ((chunk->type_flags & BTRFS_BLOCK_GROUP_METADATA) &&
1824 (chunk->type_flags & BTRFS_ORDERED_RAID))
1825 ret =btrfs_rebuild_ordered_meta_chunk_stripes(rc, chunk);
1826 else if ((chunk->type_flags & BTRFS_BLOCK_GROUP_DATA) &&
1827 (chunk->type_flags & BTRFS_ORDERED_RAID))
1828 ret = 1; /* Be handled after the fs is opened. */
1830 ret = btrfs_rebuild_unordered_chunk_stripes(rc, chunk);
1835 static int next_csum(struct btrfs_root *root,
1836 struct extent_buffer **leaf,
1837 struct btrfs_path *path,
1842 struct btrfs_key *key)
1845 struct btrfs_root *csum_root = root->fs_info->csum_root;
1846 struct btrfs_csum_item *csum_item;
1847 u32 blocksize = root->sectorsize;
1848 u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
1849 int csums_in_item = btrfs_item_size_nr(*leaf, *slot) / csum_size;
1851 if (*csum_offset >= csums_in_item) {
1854 if (*slot >= btrfs_header_nritems(*leaf)) {
1855 ret = btrfs_next_leaf(csum_root, path);
1860 *leaf = path->nodes[0];
1861 *slot = path->slots[0];
1863 btrfs_item_key_to_cpu(*leaf, key, *slot);
1866 if (key->offset + (*csum_offset) * blocksize >= end)
1868 csum_item = btrfs_item_ptr(*leaf, *slot, struct btrfs_csum_item);
1869 csum_item = (struct btrfs_csum_item *)((unsigned char *)csum_item
1870 + (*csum_offset) * csum_size);
1871 read_extent_buffer(*leaf, tree_csum,
1872 (unsigned long)csum_item, csum_size);
1876 static u64 calc_data_offset(struct btrfs_key *key,
1877 struct chunk_record *chunk,
1883 int logical_stripe_nr;
1885 int nr_data_stripes;
1887 data_offset = key->offset + csum_offset * blocksize - chunk->offset;
1888 nr_data_stripes = chunk->num_stripes;
1890 if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID5)
1891 nr_data_stripes -= 1;
1892 else if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID6)
1893 nr_data_stripes -= 2;
1895 logical_stripe_nr = data_offset / chunk->stripe_len;
1896 dev_stripe_nr = logical_stripe_nr / nr_data_stripes;
1898 data_offset -= logical_stripe_nr * chunk->stripe_len;
1899 data_offset += dev_stripe_nr * chunk->stripe_len;
1901 return dev_offset + data_offset;
1904 static int check_one_csum(int fd, u64 start, u32 len, u32 tree_csum)
1908 u32 csum_result = ~(u32)0;
1913 ret = pread64(fd, data, len, start);
1914 if (ret < 0 || ret != len) {
1919 csum_result = btrfs_csum_data(NULL, data, csum_result, len);
1920 btrfs_csum_final(csum_result, (char *)&csum_result);
1921 if (csum_result != tree_csum)
1928 static u64 item_end_offset(struct btrfs_root *root, struct btrfs_key *key,
1929 struct extent_buffer *leaf, int slot) {
1930 u32 blocksize = root->sectorsize;
1931 u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
1933 u64 offset = btrfs_item_size_nr(leaf, slot);
1934 offset /= csum_size;
1935 offset *= blocksize;
1936 offset += key->offset;
1941 static int insert_stripe(struct list_head *devexts,
1942 struct recover_control *rc,
1943 struct chunk_record *chunk,
1945 struct device_extent_record *devext;
1946 struct btrfs_device *dev;
1948 devext = list_entry(devexts->next, struct device_extent_record,
1950 dev = btrfs_find_device_by_devid(rc->fs_devices, devext->objectid,
1954 BUG_ON(btrfs_find_device_by_devid(rc->fs_devices, devext->objectid,
1957 chunk->stripes[index].devid = devext->objectid;
1958 chunk->stripes[index].offset = devext->offset;
1959 memcpy(chunk->stripes[index].dev_uuid, dev->uuid, BTRFS_UUID_SIZE);
1961 list_move(&devext->chunk_list, &chunk->dextents);
1966 static inline int count_devext_records(struct list_head *record_list)
1968 int num_of_records = 0;
1969 struct device_extent_record *devext;
1971 list_for_each_entry(devext, record_list, chunk_list)
1974 return num_of_records;
1977 static int fill_chunk_up(struct chunk_record *chunk, struct list_head *devexts,
1978 struct recover_control *rc)
1983 for (i = 0; i < chunk->num_stripes; i++) {
1984 if (!chunk->stripes[i].devid) {
1985 ret = insert_stripe(devexts, rc, chunk, i);
1994 #define EQUAL_STRIPE (1 << 0)
1996 static int rebuild_raid_data_chunk_stripes(struct recover_control *rc,
1997 struct btrfs_root *root,
1998 struct chunk_record *chunk,
2004 struct btrfs_path path;
2005 struct btrfs_key prev_key;
2006 struct btrfs_key key;
2007 struct btrfs_root *csum_root;
2008 struct extent_buffer *leaf;
2009 struct device_extent_record *devext;
2010 struct device_extent_record *next;
2011 struct btrfs_device *dev;
2012 u64 start = chunk->offset;
2013 u64 end = start + chunk->stripe_len;
2014 u64 chunk_end = chunk->offset + chunk->length;
2015 u64 csum_offset = 0;
2017 u32 blocksize = root->sectorsize;
2020 int num_unordered = 0;
2021 LIST_HEAD(unordered);
2022 LIST_HEAD(candidates);
2024 csum_root = root->fs_info->csum_root;
2025 btrfs_init_path(&path);
2026 list_splice_init(&chunk->dextents, &candidates);
2028 if (list_is_last(candidates.next, &candidates))
2031 key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
2032 key.type = BTRFS_EXTENT_CSUM_KEY;
2035 ret = btrfs_search_slot(NULL, csum_root, &key, &path, 0, 0);
2037 fprintf(stderr, "Search csum failed(%d)\n", ret);
2040 leaf = path.nodes[0];
2041 slot = path.slots[0];
2043 if (slot >= btrfs_header_nritems(leaf)) {
2044 ret = btrfs_next_leaf(csum_root, &path);
2047 "Walk tree failed(%d)\n", ret);
2049 } else if (ret > 0) {
2050 slot = btrfs_header_nritems(leaf) - 1;
2051 btrfs_item_key_to_cpu(leaf, &key, slot);
2052 if (item_end_offset(root, &key, leaf, slot)
2054 csum_offset = start - key.offset;
2055 csum_offset /= blocksize;
2060 leaf = path.nodes[0];
2061 slot = path.slots[0];
2063 btrfs_item_key_to_cpu(leaf, &key, slot);
2064 ret = btrfs_previous_item(csum_root, &path, 0,
2065 BTRFS_EXTENT_CSUM_KEY);
2069 if (key.offset >= end)
2074 leaf = path.nodes[0];
2075 slot = path.slots[0];
2077 btrfs_item_key_to_cpu(leaf, &prev_key, slot);
2078 if (item_end_offset(root, &prev_key, leaf, slot) > start) {
2079 csum_offset = start - prev_key.offset;
2080 csum_offset /= blocksize;
2081 btrfs_item_key_to_cpu(leaf, &key, slot);
2083 if (key.offset >= end)
2087 if (key.offset + csum_offset * blocksize > chunk_end)
2091 ret = next_csum(root, &leaf, &path, &slot, &csum_offset, &tree_csum,
2094 fprintf(stderr, "Fetch csum failed\n");
2096 } else if (ret == 1) {
2097 if (!(*flags & EQUAL_STRIPE))
2098 *flags |= EQUAL_STRIPE;
2100 } else if (ret == 2)
2103 list_for_each_entry_safe(devext, next, &candidates, chunk_list) {
2104 data_offset = calc_data_offset(&key, chunk, devext->offset,
2105 csum_offset, blocksize);
2106 dev = btrfs_find_device_by_devid(rc->fs_devices,
2107 devext->objectid, 0);
2112 BUG_ON(btrfs_find_device_by_devid(rc->fs_devices,
2113 devext->objectid, 1));
2115 ret = check_one_csum(dev->fd, data_offset, blocksize,
2120 list_move(&devext->chunk_list, &unordered);
2123 if (list_empty(&candidates)) {
2124 num_unordered = count_devext_records(&unordered);
2125 if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID6
2126 && num_unordered == 2) {
2127 btrfs_release_path(&path);
2128 ret = fill_chunk_up(chunk, &unordered, rc);
2135 if (list_is_last(candidates.next, &candidates)) {
2136 index = btrfs_calc_stripe_index(chunk,
2137 key.offset + csum_offset * blocksize);
2138 BUG_ON(index == -1);
2139 if (chunk->stripes[index].devid)
2141 ret = insert_stripe(&candidates, rc, chunk, index);
2149 start = btrfs_next_stripe_logical_offset(chunk, start);
2150 end = min(start + chunk->stripe_len, chunk_end);
2151 list_splice_init(&unordered, &candidates);
2152 btrfs_release_path(&path);
2154 if (end < chunk_end)
2158 list_splice_init(&candidates, &unordered);
2159 num_unordered = count_devext_records(&unordered);
2160 if (num_unordered == 1) {
2161 for (i = 0; i < chunk->num_stripes; i++) {
2162 if (!chunk->stripes[i].devid) {
2167 ret = insert_stripe(&unordered, rc, chunk, index);
2171 if ((num_unordered == 2 && chunk->type_flags
2172 & BTRFS_BLOCK_GROUP_RAID5)
2173 || (num_unordered == 3 && chunk->type_flags
2174 & BTRFS_BLOCK_GROUP_RAID6)) {
2175 ret = fill_chunk_up(chunk, &unordered, rc);
2179 ret = !!ret || (list_empty(&unordered) ? 0 : 1);
2180 list_splice_init(&candidates, &chunk->dextents);
2181 list_splice_init(&unordered, &chunk->dextents);
2182 btrfs_release_path(&path);
2187 static int btrfs_rebuild_ordered_data_chunk_stripes(struct recover_control *rc,
2188 struct btrfs_root *root)
2190 struct chunk_record *chunk;
2191 struct chunk_record *next;
2196 list_for_each_entry_safe(chunk, next, &rc->unrepaired_chunks, list) {
2197 if ((chunk->type_flags & BTRFS_BLOCK_GROUP_DATA)
2198 && (chunk->type_flags & BTRFS_ORDERED_RAID)) {
2200 err = rebuild_raid_data_chunk_stripes(rc, root, chunk,
2203 list_move(&chunk->list, &rc->bad_chunks);
2204 if (flags & EQUAL_STRIPE)
2206 "Failure: too many equal stripes in chunk[%llu %llu]\n",
2207 chunk->offset, chunk->length);
2211 list_move(&chunk->list, &rc->good_chunks);
2217 static int btrfs_recover_chunks(struct recover_control *rc)
2219 struct chunk_record *chunk;
2220 struct block_group_record *bg;
2221 struct block_group_record *next;
2222 LIST_HEAD(new_chunks);
2227 /* create the chunk by block group */
2228 list_for_each_entry_safe(bg, next, &rc->bg.block_groups, list) {
2229 nstripes = btrfs_get_device_extents(bg->objectid,
2230 &rc->devext.no_chunk_orphans,
2232 chunk = malloc(btrfs_chunk_record_size(nstripes));
2235 memset(chunk, 0, btrfs_chunk_record_size(nstripes));
2236 INIT_LIST_HEAD(&chunk->dextents);
2238 chunk->cache.start = bg->objectid;
2239 chunk->cache.size = bg->offset;
2240 chunk->objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
2241 chunk->type = BTRFS_CHUNK_ITEM_KEY;
2242 chunk->offset = bg->objectid;
2243 chunk->generation = bg->generation;
2244 chunk->length = bg->offset;
2245 chunk->owner = BTRFS_CHUNK_TREE_OBJECTID;
2246 chunk->stripe_len = BTRFS_STRIPE_LEN;
2247 chunk->type_flags = bg->flags;
2248 chunk->io_width = BTRFS_STRIPE_LEN;
2249 chunk->io_align = BTRFS_STRIPE_LEN;
2250 chunk->sector_size = rc->sectorsize;
2251 chunk->sub_stripes = calc_sub_nstripes(bg->flags);
2253 ret = insert_cache_extent(&rc->chunk, &chunk->cache);
2256 list_del_init(&bg->list);
2258 list_add_tail(&chunk->list, &rc->bad_chunks);
2262 list_splice_init(&devexts, &chunk->dextents);
2264 ret = btrfs_verify_device_extents(bg, &devexts, nstripes);
2266 list_add_tail(&chunk->list, &rc->bad_chunks);
2270 chunk->num_stripes = nstripes;
2271 ret = btrfs_rebuild_chunk_stripes(rc, chunk);
2273 list_add_tail(&chunk->list, &rc->unrepaired_chunks);
2275 list_add_tail(&chunk->list, &rc->bad_chunks);
2277 list_add_tail(&chunk->list, &rc->good_chunks);
2280 * Don't worry about the lost orphan device extents, they don't
2281 * have its chunk and block group, they must be the old ones that
2287 static inline int is_chunk_overlap(struct chunk_record *chunk1,
2288 struct chunk_record *chunk2)
2290 if (chunk1->offset >= chunk2->offset + chunk2->length ||
2291 chunk1->offset + chunk1->length <= chunk2->offset)
2296 /* Move invalid(overlap with good chunks) rebuild chunks to bad chunk list */
2297 static void validate_rebuild_chunks(struct recover_control *rc)
2299 struct chunk_record *good;
2300 struct chunk_record *rebuild;
2301 struct chunk_record *tmp;
2303 list_for_each_entry_safe(rebuild, tmp, &rc->rebuild_chunks, list) {
2304 list_for_each_entry(good, &rc->good_chunks, list) {
2305 if (is_chunk_overlap(rebuild, good)) {
2306 list_move_tail(&rebuild->list,
2315 * Return 0 when succesful, < 0 on error and > 0 if aborted by user
2317 int btrfs_recover_chunk_tree(char *path, int verbose, int yes)
2320 struct btrfs_root *root = NULL;
2321 struct btrfs_trans_handle *trans;
2322 struct recover_control rc;
2324 init_recover_control(&rc, verbose, yes);
2326 ret = recover_prepare(&rc, path);
2328 fprintf(stderr, "recover prepare error\n");
2332 ret = scan_devices(&rc);
2334 fprintf(stderr, "scan chunk headers error\n");
2338 if (cache_tree_empty(&rc.chunk) &&
2339 cache_tree_empty(&rc.bg.tree) &&
2340 cache_tree_empty(&rc.devext.tree)) {
2341 fprintf(stderr, "no recoverable chunk\n");
2345 print_scan_result(&rc);
2347 ret = check_chunks(&rc.chunk, &rc.bg, &rc.devext, &rc.good_chunks,
2348 &rc.bad_chunks, &rc.rebuild_chunks, 1);
2350 if (!list_empty(&rc.bg.block_groups) ||
2351 !list_empty(&rc.devext.no_chunk_orphans)) {
2352 ret = btrfs_recover_chunks(&rc);
2357 print_check_result(&rc);
2358 printf("Check chunks successfully with no orphans\n");
2361 validate_rebuild_chunks(&rc);
2362 print_check_result(&rc);
2364 root = open_ctree_with_broken_chunk(&rc);
2366 fprintf(stderr, "open with broken chunk error\n");
2367 ret = PTR_ERR(root);
2371 ret = check_all_chunks_by_metadata(&rc, root);
2373 fprintf(stderr, "The chunks in memory can not match the metadata of the fs. Repair failed.\n");
2374 goto fail_close_ctree;
2377 ret = btrfs_rebuild_ordered_data_chunk_stripes(&rc, root);
2379 fprintf(stderr, "Failed to rebuild ordered chunk stripes.\n");
2380 goto fail_close_ctree;
2384 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?");
2387 goto fail_close_ctree;
2391 trans = btrfs_start_transaction(root, 1);
2392 ret = remove_chunk_extent_item(trans, &rc, root);
2395 ret = rebuild_chunk_tree(trans, &rc, root);
2398 ret = rebuild_sys_array(&rc, root);
2401 ret = rebuild_block_group(trans, &rc, root);
2403 printf("Fail to rebuild block groups.\n");
2404 printf("Recommend to run 'btrfs check --init-extent-tree <dev>' after recovery\n");
2407 btrfs_commit_transaction(trans, root);
2411 free_recover_control(&rc);