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.
18 #define _XOPEN_SOURCE 500
22 #include <stdio_ext.h>
24 #include <sys/types.h>
28 #include <uuid/uuid.h>
31 #include "kerncompat.h"
33 #include "radix-tree.h"
35 #include "extent-cache.h"
38 #include "transaction.h"
45 #define BTRFS_NUM_MIRRORS 2
47 struct recover_control
{
55 u64 chunk_root_generation
;
57 struct btrfs_fs_devices
*fs_devices
;
59 struct cache_tree chunk
;
60 struct block_group_tree bg
;
61 struct device_extent_tree devext
;
62 struct cache_tree eb_cache
;
64 struct list_head good_chunks
;
65 struct list_head bad_chunks
;
66 struct list_head unrepaired_chunks
;
67 pthread_mutex_t rc_lock
;
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
];
80 struct recover_control
*rc
;
81 struct btrfs_device
*dev
;
85 static struct extent_record
*btrfs_new_extent_record(struct extent_buffer
*eb
)
87 struct extent_record
*rec
;
89 rec
= malloc(sizeof(*rec
));
91 fprintf(stderr
, "Fail to allocate memory for extent record.\n");
95 memset(rec
, 0, sizeof(*rec
));
96 rec
->cache
.start
= btrfs_header_bytenr(eb
);
97 rec
->cache
.size
= eb
->len
;
98 rec
->generation
= btrfs_header_generation(eb
);
99 read_extent_buffer(eb
, rec
->csum
, (unsigned long)btrfs_header_csum(eb
),
104 static int process_extent_buffer(struct cache_tree
*eb_cache
,
105 struct extent_buffer
*eb
,
106 struct btrfs_device
*device
, u64 offset
)
108 struct extent_record
*rec
;
109 struct extent_record
*exist
;
110 struct cache_extent
*cache
;
113 rec
= btrfs_new_extent_record(eb
);
114 if (!rec
->cache
.size
)
117 cache
= lookup_cache_extent(eb_cache
,
121 exist
= container_of(cache
, struct extent_record
, cache
);
123 if (exist
->generation
> rec
->generation
)
125 if (exist
->generation
== rec
->generation
) {
126 if (exist
->cache
.start
!= rec
->cache
.start
||
127 exist
->cache
.size
!= rec
->cache
.size
||
128 memcmp(exist
->csum
, rec
->csum
, BTRFS_CSUM_SIZE
)) {
131 BUG_ON(exist
->nmirrors
>= BTRFS_NUM_MIRRORS
);
132 exist
->devices
[exist
->nmirrors
] = device
;
133 exist
->offsets
[exist
->nmirrors
] = offset
;
138 remove_cache_extent(eb_cache
, cache
);
143 rec
->devices
[0] = device
;
144 rec
->offsets
[0] = offset
;
146 ret
= insert_cache_extent(eb_cache
, &rec
->cache
);
155 static void free_extent_record(struct cache_extent
*cache
)
157 struct extent_record
*er
;
159 er
= container_of(cache
, struct extent_record
, cache
);
163 FREE_EXTENT_CACHE_BASED_TREE(extent_record
, free_extent_record
);
165 static struct btrfs_chunk
*create_chunk_item(struct chunk_record
*record
)
167 struct btrfs_chunk
*ret
;
168 struct btrfs_stripe
*chunk_stripe
;
171 if (!record
|| record
->num_stripes
== 0)
173 ret
= malloc(btrfs_chunk_item_size(record
->num_stripes
));
176 btrfs_set_stack_chunk_length(ret
, record
->length
);
177 btrfs_set_stack_chunk_owner(ret
, record
->owner
);
178 btrfs_set_stack_chunk_stripe_len(ret
, record
->stripe_len
);
179 btrfs_set_stack_chunk_type(ret
, record
->type_flags
);
180 btrfs_set_stack_chunk_io_align(ret
, record
->io_align
);
181 btrfs_set_stack_chunk_io_width(ret
, record
->io_width
);
182 btrfs_set_stack_chunk_sector_size(ret
, record
->sector_size
);
183 btrfs_set_stack_chunk_num_stripes(ret
, record
->num_stripes
);
184 btrfs_set_stack_chunk_sub_stripes(ret
, record
->sub_stripes
);
185 for (i
= 0, chunk_stripe
= &ret
->stripe
; i
< record
->num_stripes
;
186 i
++, chunk_stripe
++) {
187 btrfs_set_stack_stripe_devid(chunk_stripe
,
188 record
->stripes
[i
].devid
);
189 btrfs_set_stack_stripe_offset(chunk_stripe
,
190 record
->stripes
[i
].offset
);
191 memcpy(chunk_stripe
->dev_uuid
, record
->stripes
[i
].dev_uuid
,
197 static void init_recover_control(struct recover_control
*rc
, int verbose
,
200 memset(rc
, 0, sizeof(struct recover_control
));
201 cache_tree_init(&rc
->chunk
);
202 cache_tree_init(&rc
->eb_cache
);
203 block_group_tree_init(&rc
->bg
);
204 device_extent_tree_init(&rc
->devext
);
206 INIT_LIST_HEAD(&rc
->good_chunks
);
207 INIT_LIST_HEAD(&rc
->bad_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("Healthy Chunks:\n");
535 list_for_each_entry(chunk
, &rc
->good_chunks
, list
) {
536 print_chunk_info(chunk
, " ");
540 printf("Bad Chunks:\n");
541 list_for_each_entry(chunk
, &rc
->bad_chunks
, list
) {
542 print_chunk_info(chunk
, " ");
547 printf("Total Chunks:\t%d\n", total
);
548 printf(" Heathy:\t%d\n", good
);
549 printf(" Bad:\t%d\n", bad
);
552 printf("Orphan Block Groups:\n");
553 list_for_each_entry(bg
, &rc
->bg
.block_groups
, list
)
554 print_block_group_info(bg
, " ");
557 printf("Orphan Device Extents:\n");
558 list_for_each_entry(devext
, &rc
->devext
.no_chunk_orphans
, chunk_list
)
559 print_device_extent_info(devext
, " ");
562 static int check_chunk_by_metadata(struct recover_control
*rc
,
563 struct btrfs_root
*root
,
564 struct chunk_record
*chunk
, int bg_only
)
569 struct btrfs_path path
;
570 struct btrfs_key key
;
571 struct btrfs_root
*dev_root
;
572 struct stripe
*stripe
;
573 struct btrfs_dev_extent
*dev_extent
;
574 struct btrfs_block_group_item
*bg_ptr
;
575 struct extent_buffer
*l
;
577 btrfs_init_path(&path
);
582 dev_root
= root
->fs_info
->dev_root
;
583 for (i
= 0; i
< chunk
->num_stripes
; i
++) {
584 stripe
= &chunk
->stripes
[i
];
586 key
.objectid
= stripe
->devid
;
587 key
.offset
= stripe
->offset
;
588 key
.type
= BTRFS_DEV_EXTENT_KEY
;
590 ret
= btrfs_search_slot(NULL
, dev_root
, &key
, &path
, 0, 0);
592 fprintf(stderr
, "Search device extent failed(%d)\n",
594 btrfs_release_path(&path
);
596 } else if (ret
> 0) {
599 "No device extent[%llu, %llu]\n",
600 stripe
->devid
, stripe
->offset
);
601 btrfs_release_path(&path
);
605 slot
= path
.slots
[0];
606 dev_extent
= btrfs_item_ptr(l
, slot
, struct btrfs_dev_extent
);
608 btrfs_dev_extent_chunk_offset(l
, dev_extent
)) {
611 "Device tree unmatch with chunks dev_extent[%llu, %llu], chunk[%llu, %llu]\n",
612 btrfs_dev_extent_chunk_offset(l
,
614 btrfs_dev_extent_length(l
, dev_extent
),
615 chunk
->offset
, chunk
->length
);
616 btrfs_release_path(&path
);
619 btrfs_release_path(&path
);
623 key
.objectid
= chunk
->offset
;
624 key
.type
= BTRFS_BLOCK_GROUP_ITEM_KEY
;
625 key
.offset
= chunk
->length
;
627 ret
= btrfs_search_slot(NULL
, root
->fs_info
->extent_root
, &key
, &path
,
630 fprintf(stderr
, "Search block group failed(%d)\n", ret
);
631 btrfs_release_path(&path
);
633 } else if (ret
> 0) {
635 fprintf(stderr
, "No block group[%llu, %llu]\n",
636 key
.objectid
, key
.offset
);
637 btrfs_release_path(&path
);
642 slot
= path
.slots
[0];
643 bg_ptr
= btrfs_item_ptr(l
, slot
, struct btrfs_block_group_item
);
644 if (chunk
->type_flags
!= btrfs_disk_block_group_flags(l
, bg_ptr
)) {
647 "Chunk[%llu, %llu]'s type(%llu) is differemt with Block Group's type(%llu)\n",
648 chunk
->offset
, chunk
->length
, chunk
->type_flags
,
649 btrfs_disk_block_group_flags(l
, bg_ptr
));
650 btrfs_release_path(&path
);
653 btrfs_release_path(&path
);
657 static int check_all_chunks_by_metadata(struct recover_control
*rc
,
658 struct btrfs_root
*root
)
660 struct chunk_record
*chunk
;
661 struct chunk_record
*next
;
662 LIST_HEAD(orphan_chunks
);
666 list_for_each_entry_safe(chunk
, next
, &rc
->good_chunks
, list
) {
667 err
= check_chunk_by_metadata(rc
, root
, chunk
, 0);
670 list_move_tail(&chunk
->list
, &orphan_chunks
);
671 else if (err
&& !ret
)
676 list_for_each_entry_safe(chunk
, next
, &rc
->unrepaired_chunks
, list
) {
677 err
= check_chunk_by_metadata(rc
, root
, chunk
, 1);
679 list_move_tail(&chunk
->list
, &orphan_chunks
);
680 else if (err
&& !ret
)
684 list_for_each_entry(chunk
, &rc
->bad_chunks
, list
) {
685 err
= check_chunk_by_metadata(rc
, root
, chunk
, 1);
686 if (err
!= -ENOENT
&& !ret
)
687 ret
= err
? err
: -EINVAL
;
689 list_splice(&orphan_chunks
, &rc
->bad_chunks
);
693 static int extract_metadata_record(struct recover_control
*rc
,
694 struct extent_buffer
*leaf
)
696 struct btrfs_key key
;
701 nritems
= btrfs_header_nritems(leaf
);
702 for (i
= 0; i
< nritems
; i
++) {
703 btrfs_item_key_to_cpu(leaf
, &key
, i
);
705 case BTRFS_BLOCK_GROUP_ITEM_KEY
:
706 pthread_mutex_lock(&rc
->rc_lock
);
707 ret
= process_block_group_item(&rc
->bg
, leaf
, &key
, i
);
708 pthread_mutex_unlock(&rc
->rc_lock
);
710 case BTRFS_CHUNK_ITEM_KEY
:
711 pthread_mutex_lock(&rc
->rc_lock
);
712 ret
= process_chunk_item(&rc
->chunk
, leaf
, &key
, i
);
713 pthread_mutex_unlock(&rc
->rc_lock
);
715 case BTRFS_DEV_EXTENT_KEY
:
716 pthread_mutex_lock(&rc
->rc_lock
);
717 ret
= process_device_extent_item(&rc
->devext
, leaf
,
719 pthread_mutex_unlock(&rc
->rc_lock
);
728 static inline int is_super_block_address(u64 offset
)
732 for (i
= 0; i
< BTRFS_SUPER_MIRROR_MAX
; i
++) {
733 if (offset
== btrfs_sb_offset(i
))
739 static int scan_one_device(void *dev_scan_struct
)
741 struct extent_buffer
*buf
;
744 struct device_scan
*dev_scan
= (struct device_scan
*)dev_scan_struct
;
745 struct recover_control
*rc
= dev_scan
->rc
;
746 struct btrfs_device
*device
= dev_scan
->dev
;
747 int fd
= dev_scan
->fd
;
750 ret
= pthread_setcanceltype(PTHREAD_CANCEL_ASYNCHRONOUS
, &oldtype
);
754 buf
= malloc(sizeof(*buf
) + rc
->leafsize
);
757 buf
->len
= rc
->leafsize
;
761 if (is_super_block_address(bytenr
))
762 bytenr
+= rc
->sectorsize
;
764 if (pread64(fd
, buf
->data
, rc
->leafsize
, bytenr
) <
768 if (memcmp_extent_buffer(buf
, rc
->fs_devices
->fsid
,
771 bytenr
+= rc
->sectorsize
;
775 if (verify_tree_block_csum_silent(buf
, rc
->csum_size
)) {
776 bytenr
+= rc
->sectorsize
;
780 pthread_mutex_lock(&rc
->rc_lock
);
781 ret
= process_extent_buffer(&rc
->eb_cache
, buf
, device
, bytenr
);
782 pthread_mutex_unlock(&rc
->rc_lock
);
786 if (btrfs_header_level(buf
) != 0)
789 switch (btrfs_header_owner(buf
)) {
790 case BTRFS_EXTENT_TREE_OBJECTID
:
791 case BTRFS_DEV_TREE_OBJECTID
:
792 /* different tree use different generation */
793 if (btrfs_header_generation(buf
) > rc
->generation
)
795 ret
= extract_metadata_record(rc
, buf
);
799 case BTRFS_CHUNK_TREE_OBJECTID
:
800 if (btrfs_header_generation(buf
) >
801 rc
->chunk_root_generation
)
803 ret
= extract_metadata_record(rc
, buf
);
809 bytenr
+= rc
->leafsize
;
817 static int scan_devices(struct recover_control
*rc
)
821 struct btrfs_device
*dev
;
822 struct device_scan
*dev_scans
;
831 list_for_each_entry(dev
, &rc
->fs_devices
->devices
, dev_list
)
833 dev_scans
= (struct device_scan
*)malloc(sizeof(struct device_scan
)
837 t_scans
= (pthread_t
*)malloc(sizeof(pthread_t
) * devnr
);
840 t_rets
= (int *)malloc(sizeof(int) * devnr
);
844 list_for_each_entry(dev
, &rc
->fs_devices
->devices
, dev_list
) {
845 fd
= open(dev
->name
, O_RDONLY
);
847 fprintf(stderr
, "Failed to open device %s\n",
852 dev_scans
[devidx
].rc
= rc
;
853 dev_scans
[devidx
].dev
= dev
;
854 dev_scans
[devidx
].fd
= fd
;
855 ret
= pthread_create(&t_scans
[devidx
], NULL
,
856 (void *)scan_one_device
,
857 (void *)&dev_scans
[devidx
]);
860 cancel_to
= devidx
- 1;
868 ret
= pthread_join(t_scans
[i
], (void **)&t_rets
[i
]);
869 if (ret
|| t_rets
[i
]) {
872 cancel_to
= devnr
- 1;
878 while (ret
&& (cancel_from
<= cancel_to
)) {
879 pthread_cancel(t_scans
[cancel_from
]);
889 static int build_device_map_by_chunk_record(struct btrfs_root
*root
,
890 struct chunk_record
*chunk
)
895 u8 uuid
[BTRFS_UUID_SIZE
];
897 struct btrfs_mapping_tree
*map_tree
;
898 struct map_lookup
*map
;
899 struct stripe
*stripe
;
901 map_tree
= &root
->fs_info
->mapping_tree
;
902 num_stripes
= chunk
->num_stripes
;
903 map
= malloc(btrfs_map_lookup_size(num_stripes
));
906 map
->ce
.start
= chunk
->offset
;
907 map
->ce
.size
= chunk
->length
;
908 map
->num_stripes
= num_stripes
;
909 map
->io_width
= chunk
->io_width
;
910 map
->io_align
= chunk
->io_align
;
911 map
->sector_size
= chunk
->sector_size
;
912 map
->stripe_len
= chunk
->stripe_len
;
913 map
->type
= chunk
->type_flags
;
914 map
->sub_stripes
= chunk
->sub_stripes
;
916 for (i
= 0, stripe
= chunk
->stripes
; i
< num_stripes
; i
++, stripe
++) {
917 devid
= stripe
->devid
;
918 memcpy(uuid
, stripe
->dev_uuid
, BTRFS_UUID_SIZE
);
919 map
->stripes
[i
].physical
= stripe
->offset
;
920 map
->stripes
[i
].dev
= btrfs_find_device(root
, devid
,
922 if (!map
->stripes
[i
].dev
) {
928 ret
= insert_cache_extent(&map_tree
->cache_tree
, &map
->ce
);
932 static int build_device_maps_by_chunk_records(struct recover_control
*rc
,
933 struct btrfs_root
*root
)
936 struct chunk_record
*chunk
;
938 list_for_each_entry(chunk
, &rc
->good_chunks
, list
) {
939 ret
= build_device_map_by_chunk_record(root
, chunk
);
946 static int block_group_remove_all_extent_items(struct btrfs_trans_handle
*trans
,
947 struct btrfs_root
*root
,
948 struct block_group_record
*bg
)
950 struct btrfs_fs_info
*fs_info
= root
->fs_info
;
951 struct btrfs_key key
;
952 struct btrfs_path path
;
953 struct extent_buffer
*leaf
;
954 u64 start
= bg
->objectid
;
955 u64 end
= bg
->objectid
+ bg
->offset
;
962 btrfs_init_path(&path
);
963 root
= root
->fs_info
->extent_root
;
965 key
.objectid
= start
;
967 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
969 ret
= btrfs_search_slot(trans
, root
, &key
, &path
, -1, 1);
975 leaf
= path
.nodes
[0];
976 nitems
= btrfs_header_nritems(leaf
);
978 /* The tree is empty. */
983 if (path
.slots
[0] >= nitems
) {
984 ret
= btrfs_next_leaf(root
, &path
);
991 leaf
= path
.nodes
[0];
992 btrfs_item_key_to_cpu(leaf
, &key
, 0);
993 if (key
.objectid
>= end
)
995 btrfs_release_path(&path
);
1001 for (i
= path
.slots
[0]; i
< nitems
; i
++) {
1002 btrfs_item_key_to_cpu(leaf
, &key
, i
);
1003 if (key
.objectid
>= end
)
1006 if (key
.type
== BTRFS_BLOCK_GROUP_ITEM_KEY
) {
1016 if (key
.type
== BTRFS_EXTENT_ITEM_KEY
||
1017 key
.type
== BTRFS_METADATA_ITEM_KEY
) {
1018 old_val
= btrfs_super_bytes_used(fs_info
->super_copy
);
1019 if (key
.type
== BTRFS_METADATA_ITEM_KEY
)
1020 old_val
+= root
->leafsize
;
1022 old_val
+= key
.offset
;
1023 btrfs_set_super_bytes_used(fs_info
->super_copy
,
1029 ret
= btrfs_del_items(trans
, root
, &path
, del_s
, del_nr
);
1034 if (key
.objectid
< end
) {
1035 if (key
.type
== BTRFS_BLOCK_GROUP_ITEM_KEY
) {
1036 key
.objectid
+= root
->sectorsize
;
1037 key
.type
= BTRFS_EXTENT_ITEM_KEY
;
1040 btrfs_release_path(&path
);
1044 btrfs_release_path(&path
);
1048 static int block_group_free_all_extent(struct btrfs_trans_handle
*trans
,
1049 struct btrfs_root
*root
,
1050 struct block_group_record
*bg
)
1052 struct btrfs_block_group_cache
*cache
;
1053 struct btrfs_fs_info
*info
;
1057 info
= root
->fs_info
;
1058 cache
= btrfs_lookup_block_group(info
, bg
->objectid
);
1062 start
= cache
->key
.objectid
;
1063 end
= start
+ cache
->key
.offset
- 1;
1065 set_extent_bits(&info
->block_group_cache
, start
, end
,
1066 BLOCK_GROUP_DIRTY
, GFP_NOFS
);
1067 set_extent_dirty(&info
->free_space_cache
, start
, end
, GFP_NOFS
);
1069 btrfs_set_block_group_used(&cache
->item
, 0);
1074 static int remove_chunk_extent_item(struct btrfs_trans_handle
*trans
,
1075 struct recover_control
*rc
,
1076 struct btrfs_root
*root
)
1078 struct chunk_record
*chunk
;
1081 list_for_each_entry(chunk
, &rc
->good_chunks
, list
) {
1082 if (!(chunk
->type_flags
& BTRFS_BLOCK_GROUP_SYSTEM
))
1084 ret
= block_group_remove_all_extent_items(trans
, root
,
1089 ret
= block_group_free_all_extent(trans
, root
, chunk
->bg_rec
);
1096 static int __rebuild_chunk_root(struct btrfs_trans_handle
*trans
,
1097 struct recover_control
*rc
,
1098 struct btrfs_root
*root
)
1101 struct btrfs_device
*dev
;
1102 struct extent_buffer
*cow
;
1103 struct btrfs_disk_key disk_key
;
1106 list_for_each_entry(dev
, &rc
->fs_devices
->devices
, dev_list
) {
1107 if (min_devid
> dev
->devid
)
1108 min_devid
= dev
->devid
;
1110 disk_key
.objectid
= BTRFS_DEV_ITEMS_OBJECTID
;
1111 disk_key
.type
= BTRFS_DEV_ITEM_KEY
;
1112 disk_key
.offset
= min_devid
;
1114 cow
= btrfs_alloc_free_block(trans
, root
, root
->nodesize
,
1115 BTRFS_CHUNK_TREE_OBJECTID
,
1116 &disk_key
, 0, 0, 0);
1117 btrfs_set_header_bytenr(cow
, cow
->start
);
1118 btrfs_set_header_generation(cow
, trans
->transid
);
1119 btrfs_set_header_nritems(cow
, 0);
1120 btrfs_set_header_level(cow
, 0);
1121 btrfs_set_header_backref_rev(cow
, BTRFS_MIXED_BACKREF_REV
);
1122 btrfs_set_header_owner(cow
, BTRFS_CHUNK_TREE_OBJECTID
);
1123 write_extent_buffer(cow
, root
->fs_info
->fsid
,
1124 btrfs_header_fsid(), BTRFS_FSID_SIZE
);
1126 write_extent_buffer(cow
, root
->fs_info
->chunk_tree_uuid
,
1127 btrfs_header_chunk_tree_uuid(cow
),
1131 btrfs_mark_buffer_dirty(cow
);
1136 static int __rebuild_device_items(struct btrfs_trans_handle
*trans
,
1137 struct recover_control
*rc
,
1138 struct btrfs_root
*root
)
1140 struct btrfs_device
*dev
;
1141 struct btrfs_key key
;
1142 struct btrfs_dev_item
*dev_item
;
1145 dev_item
= malloc(sizeof(struct btrfs_dev_item
));
1149 list_for_each_entry(dev
, &rc
->fs_devices
->devices
, dev_list
) {
1150 key
.objectid
= BTRFS_DEV_ITEMS_OBJECTID
;
1151 key
.type
= BTRFS_DEV_ITEM_KEY
;
1152 key
.offset
= dev
->devid
;
1154 btrfs_set_stack_device_generation(dev_item
, 0);
1155 btrfs_set_stack_device_type(dev_item
, dev
->type
);
1156 btrfs_set_stack_device_id(dev_item
, dev
->devid
);
1157 btrfs_set_stack_device_total_bytes(dev_item
, dev
->total_bytes
);
1158 btrfs_set_stack_device_bytes_used(dev_item
, dev
->bytes_used
);
1159 btrfs_set_stack_device_io_align(dev_item
, dev
->io_align
);
1160 btrfs_set_stack_device_io_width(dev_item
, dev
->io_width
);
1161 btrfs_set_stack_device_sector_size(dev_item
, dev
->sector_size
);
1162 memcpy(dev_item
->uuid
, dev
->uuid
, BTRFS_UUID_SIZE
);
1163 memcpy(dev_item
->fsid
, dev
->fs_devices
->fsid
, BTRFS_UUID_SIZE
);
1165 ret
= btrfs_insert_item(trans
, root
, &key
,
1166 dev_item
, sizeof(*dev_item
));
1173 static int __rebuild_chunk_items(struct btrfs_trans_handle
*trans
,
1174 struct recover_control
*rc
,
1175 struct btrfs_root
*root
)
1177 struct btrfs_key key
;
1178 struct btrfs_chunk
*chunk
= NULL
;
1179 struct btrfs_root
*chunk_root
;
1180 struct chunk_record
*chunk_rec
;
1183 chunk_root
= root
->fs_info
->chunk_root
;
1185 list_for_each_entry(chunk_rec
, &rc
->good_chunks
, list
) {
1186 chunk
= create_chunk_item(chunk_rec
);
1190 key
.objectid
= BTRFS_FIRST_CHUNK_TREE_OBJECTID
;
1191 key
.type
= BTRFS_CHUNK_ITEM_KEY
;
1192 key
.offset
= chunk_rec
->offset
;
1194 ret
= btrfs_insert_item(trans
, chunk_root
, &key
, chunk
,
1195 btrfs_chunk_item_size(chunk
->num_stripes
));
1203 static int rebuild_chunk_tree(struct btrfs_trans_handle
*trans
,
1204 struct recover_control
*rc
,
1205 struct btrfs_root
*root
)
1209 root
= root
->fs_info
->chunk_root
;
1211 ret
= __rebuild_chunk_root(trans
, rc
, root
);
1215 ret
= __rebuild_device_items(trans
, rc
, root
);
1219 ret
= __rebuild_chunk_items(trans
, rc
, root
);
1224 static int rebuild_sys_array(struct recover_control
*rc
,
1225 struct btrfs_root
*root
)
1227 struct btrfs_chunk
*chunk
;
1228 struct btrfs_key key
;
1229 struct chunk_record
*chunk_rec
;
1233 btrfs_set_super_sys_array_size(root
->fs_info
->super_copy
, 0);
1235 list_for_each_entry(chunk_rec
, &rc
->good_chunks
, list
) {
1236 if (!(chunk_rec
->type_flags
& BTRFS_BLOCK_GROUP_SYSTEM
))
1239 num_stripes
= chunk_rec
->num_stripes
;
1240 chunk
= create_chunk_item(chunk_rec
);
1246 key
.objectid
= BTRFS_FIRST_CHUNK_TREE_OBJECTID
;
1247 key
.type
= BTRFS_CHUNK_ITEM_KEY
;
1248 key
.offset
= chunk_rec
->offset
;
1250 ret
= btrfs_add_system_chunk(NULL
, root
, &key
, chunk
,
1251 btrfs_chunk_item_size(num_stripes
));
1260 static struct btrfs_root
*
1261 open_ctree_with_broken_chunk(struct recover_control
*rc
)
1263 struct btrfs_fs_info
*fs_info
;
1264 struct btrfs_super_block
*disk_super
;
1265 struct extent_buffer
*eb
;
1272 fs_info
= btrfs_new_fs_info(1, BTRFS_SUPER_INFO_OFFSET
);
1274 fprintf(stderr
, "Failed to allocate memory for fs_info\n");
1275 return ERR_PTR(-ENOMEM
);
1277 fs_info
->is_chunk_recover
= 1;
1279 fs_info
->fs_devices
= rc
->fs_devices
;
1280 ret
= btrfs_open_devices(fs_info
->fs_devices
, O_RDWR
);
1284 disk_super
= fs_info
->super_copy
;
1285 ret
= btrfs_read_dev_super(fs_info
->fs_devices
->latest_bdev
,
1286 disk_super
, fs_info
->super_bytenr
);
1288 fprintf(stderr
, "No valid btrfs found\n");
1292 memcpy(fs_info
->fsid
, &disk_super
->fsid
, BTRFS_FSID_SIZE
);
1294 ret
= btrfs_check_fs_compatibility(disk_super
, 1);
1298 nodesize
= btrfs_super_nodesize(disk_super
);
1299 leafsize
= btrfs_super_leafsize(disk_super
);
1300 sectorsize
= btrfs_super_sectorsize(disk_super
);
1301 stripesize
= btrfs_super_stripesize(disk_super
);
1303 __setup_root(nodesize
, leafsize
, sectorsize
, stripesize
,
1304 fs_info
->chunk_root
, fs_info
, BTRFS_CHUNK_TREE_OBJECTID
);
1306 ret
= build_device_maps_by_chunk_records(rc
, fs_info
->chunk_root
);
1310 ret
= btrfs_setup_all_roots(fs_info
, 0, 0);
1314 eb
= fs_info
->tree_root
->node
;
1315 read_extent_buffer(eb
, fs_info
->chunk_tree_uuid
,
1316 btrfs_header_chunk_tree_uuid(eb
),
1319 return fs_info
->fs_root
;
1321 btrfs_release_all_roots(fs_info
);
1323 btrfs_cleanup_all_caches(fs_info
);
1325 btrfs_close_devices(fs_info
->fs_devices
);
1327 btrfs_free_fs_info(fs_info
);
1328 return ERR_PTR(ret
);
1331 static int recover_prepare(struct recover_control
*rc
, char *path
)
1335 struct btrfs_super_block
*sb
;
1336 struct btrfs_fs_devices
*fs_devices
;
1339 fd
= open(path
, O_RDONLY
);
1341 fprintf(stderr
, "open %s\n error.\n", path
);
1345 sb
= malloc(sizeof(struct btrfs_super_block
));
1347 fprintf(stderr
, "allocating memory for sb failed.\n");
1352 ret
= btrfs_read_dev_super(fd
, sb
, BTRFS_SUPER_INFO_OFFSET
);
1354 fprintf(stderr
, "read super block error\n");
1358 rc
->sectorsize
= btrfs_super_sectorsize(sb
);
1359 rc
->leafsize
= btrfs_super_leafsize(sb
);
1360 rc
->generation
= btrfs_super_generation(sb
);
1361 rc
->chunk_root_generation
= btrfs_super_chunk_root_generation(sb
);
1362 rc
->csum_size
= btrfs_super_csum_size(sb
);
1364 /* if seed, the result of scanning below will be partial */
1365 if (btrfs_super_flags(sb
) & BTRFS_SUPER_FLAG_SEEDING
) {
1366 fprintf(stderr
, "this device is seed device\n");
1371 ret
= btrfs_scan_fs_devices(fd
, path
, &fs_devices
, 0, 1);
1375 rc
->fs_devices
= fs_devices
;
1378 print_all_devices(&rc
->fs_devices
->devices
);
1387 static int btrfs_get_device_extents(u64 chunk_object
,
1388 struct list_head
*orphan_devexts
,
1389 struct list_head
*ret_list
)
1391 struct device_extent_record
*devext
;
1392 struct device_extent_record
*next
;
1395 list_for_each_entry_safe(devext
, next
, orphan_devexts
, chunk_list
) {
1396 if (devext
->chunk_offset
== chunk_object
) {
1397 list_move_tail(&devext
->chunk_list
, ret_list
);
1404 static int calc_num_stripes(u64 type
)
1406 if (type
& (BTRFS_BLOCK_GROUP_RAID0
|
1407 BTRFS_BLOCK_GROUP_RAID10
|
1408 BTRFS_BLOCK_GROUP_RAID5
|
1409 BTRFS_BLOCK_GROUP_RAID6
))
1411 else if (type
& (BTRFS_BLOCK_GROUP_RAID1
|
1412 BTRFS_BLOCK_GROUP_DUP
))
1418 static inline int calc_sub_nstripes(u64 type
)
1420 if (type
& BTRFS_BLOCK_GROUP_RAID10
)
1426 static int btrfs_verify_device_extents(struct block_group_record
*bg
,
1427 struct list_head
*devexts
, int ndevexts
)
1429 struct device_extent_record
*devext
;
1431 int expected_num_stripes
;
1433 expected_num_stripes
= calc_num_stripes(bg
->flags
);
1434 if (expected_num_stripes
&& expected_num_stripes
!= ndevexts
)
1437 strpie_length
= calc_stripe_length(bg
->flags
, bg
->offset
, ndevexts
);
1438 list_for_each_entry(devext
, devexts
, chunk_list
) {
1439 if (devext
->length
!= strpie_length
)
1445 static int btrfs_rebuild_unordered_chunk_stripes(struct recover_control
*rc
,
1446 struct chunk_record
*chunk
)
1448 struct device_extent_record
*devext
;
1449 struct btrfs_device
*device
;
1452 devext
= list_first_entry(&chunk
->dextents
, struct device_extent_record
,
1454 for (i
= 0; i
< chunk
->num_stripes
; i
++) {
1455 chunk
->stripes
[i
].devid
= devext
->objectid
;
1456 chunk
->stripes
[i
].offset
= devext
->offset
;
1457 device
= btrfs_find_device_by_devid(rc
->fs_devices
,
1462 BUG_ON(btrfs_find_device_by_devid(rc
->fs_devices
,
1465 memcpy(chunk
->stripes
[i
].dev_uuid
, device
->uuid
,
1467 devext
= list_next_entry(devext
, chunk_list
);
1472 static int btrfs_calc_stripe_index(struct chunk_record
*chunk
, u64 logical
)
1474 u64 offset
= logical
- chunk
->offset
;
1476 int nr_data_stripes
;
1479 stripe_nr
= offset
/ chunk
->stripe_len
;
1480 if (chunk
->type_flags
& BTRFS_BLOCK_GROUP_RAID0
) {
1481 index
= stripe_nr
% chunk
->num_stripes
;
1482 } else if (chunk
->type_flags
& BTRFS_BLOCK_GROUP_RAID10
) {
1483 index
= stripe_nr
% (chunk
->num_stripes
/ chunk
->sub_stripes
);
1484 index
*= chunk
->sub_stripes
;
1485 } else if (chunk
->type_flags
& BTRFS_BLOCK_GROUP_RAID5
) {
1486 nr_data_stripes
= chunk
->num_stripes
- 1;
1487 index
= stripe_nr
% nr_data_stripes
;
1488 stripe_nr
/= nr_data_stripes
;
1489 index
= (index
+ stripe_nr
) % chunk
->num_stripes
;
1490 } else if (chunk
->type_flags
& BTRFS_BLOCK_GROUP_RAID6
) {
1491 nr_data_stripes
= chunk
->num_stripes
- 2;
1492 index
= stripe_nr
% nr_data_stripes
;
1493 stripe_nr
/= nr_data_stripes
;
1494 index
= (index
+ stripe_nr
) % chunk
->num_stripes
;
1501 /* calc the logical offset which is the start of the next stripe. */
1502 static inline u64
btrfs_next_stripe_logical_offset(struct chunk_record
*chunk
,
1505 u64 offset
= logical
- chunk
->offset
;
1507 offset
/= chunk
->stripe_len
;
1508 offset
*= chunk
->stripe_len
;
1509 offset
+= chunk
->stripe_len
;
1511 return offset
+ chunk
->offset
;
1514 static int is_extent_record_in_device_extent(struct extent_record
*er
,
1515 struct device_extent_record
*dext
,
1520 for (i
= 0; i
< er
->nmirrors
; i
++) {
1521 if (er
->devices
[i
]->devid
== dext
->objectid
&&
1522 er
->offsets
[i
] >= dext
->offset
&&
1523 er
->offsets
[i
] < dext
->offset
+ dext
->length
) {
1532 btrfs_rebuild_ordered_meta_chunk_stripes(struct recover_control
*rc
,
1533 struct chunk_record
*chunk
)
1535 u64 start
= chunk
->offset
;
1536 u64 end
= chunk
->offset
+ chunk
->length
;
1537 struct cache_extent
*cache
;
1538 struct extent_record
*er
;
1539 struct device_extent_record
*devext
;
1540 struct device_extent_record
*next
;
1541 struct btrfs_device
*device
;
1547 cache
= lookup_cache_extent(&rc
->eb_cache
,
1548 start
, chunk
->length
);
1550 /* No used space, we can reorder the stripes freely. */
1551 ret
= btrfs_rebuild_unordered_chunk_stripes(rc
, chunk
);
1555 list_splice_init(&chunk
->dextents
, &devexts
);
1557 er
= container_of(cache
, struct extent_record
, cache
);
1558 index
= btrfs_calc_stripe_index(chunk
, er
->cache
.start
);
1559 if (chunk
->stripes
[index
].devid
)
1561 list_for_each_entry_safe(devext
, next
, &devexts
, chunk_list
) {
1562 if (is_extent_record_in_device_extent(er
, devext
, &mirror
)) {
1563 chunk
->stripes
[index
].devid
= devext
->objectid
;
1564 chunk
->stripes
[index
].offset
= devext
->offset
;
1565 memcpy(chunk
->stripes
[index
].dev_uuid
,
1566 er
->devices
[mirror
]->uuid
,
1569 list_move(&devext
->chunk_list
, &chunk
->dextents
);
1573 start
= btrfs_next_stripe_logical_offset(chunk
, er
->cache
.start
);
1575 goto no_extent_record
;
1577 cache
= lookup_cache_extent(&rc
->eb_cache
, start
, end
- start
);
1581 if (list_empty(&devexts
))
1584 if (chunk
->type_flags
& (BTRFS_BLOCK_GROUP_RAID5
|
1585 BTRFS_BLOCK_GROUP_RAID6
)) {
1586 /* Fixme: try to recover the order by the parity block. */
1587 list_splice_tail(&devexts
, &chunk
->dextents
);
1591 /* There is no data on the lost stripes, we can reorder them freely. */
1592 for (index
= 0; index
< chunk
->num_stripes
; index
++) {
1593 if (chunk
->stripes
[index
].devid
)
1596 devext
= list_first_entry(&devexts
,
1597 struct device_extent_record
,
1599 list_move(&devext
->chunk_list
, &chunk
->dextents
);
1601 chunk
->stripes
[index
].devid
= devext
->objectid
;
1602 chunk
->stripes
[index
].offset
= devext
->offset
;
1603 device
= btrfs_find_device_by_devid(rc
->fs_devices
,
1607 list_splice_tail(&devexts
, &chunk
->dextents
);
1610 BUG_ON(btrfs_find_device_by_devid(rc
->fs_devices
,
1613 memcpy(chunk
->stripes
[index
].dev_uuid
, device
->uuid
,
1619 #define BTRFS_ORDERED_RAID (BTRFS_BLOCK_GROUP_RAID0 | \
1620 BTRFS_BLOCK_GROUP_RAID10 | \
1621 BTRFS_BLOCK_GROUP_RAID5 | \
1622 BTRFS_BLOCK_GROUP_RAID6)
1624 static int btrfs_rebuild_chunk_stripes(struct recover_control
*rc
,
1625 struct chunk_record
*chunk
)
1630 * All the data in the system metadata chunk will be dropped,
1631 * so we need not guarantee that the data is right or not, that
1632 * is we can reorder the stripes in the system metadata chunk.
1634 if ((chunk
->type_flags
& BTRFS_BLOCK_GROUP_METADATA
) &&
1635 (chunk
->type_flags
& BTRFS_ORDERED_RAID
))
1636 ret
=btrfs_rebuild_ordered_meta_chunk_stripes(rc
, chunk
);
1637 else if ((chunk
->type_flags
& BTRFS_BLOCK_GROUP_DATA
) &&
1638 (chunk
->type_flags
& BTRFS_ORDERED_RAID
))
1639 ret
= 1; /* Be handled after the fs is opened. */
1641 ret
= btrfs_rebuild_unordered_chunk_stripes(rc
, chunk
);
1646 static int next_csum(struct btrfs_root
*root
,
1647 struct extent_buffer
**leaf
,
1648 struct btrfs_path
*path
,
1653 struct btrfs_key
*key
)
1656 struct btrfs_root
*csum_root
= root
->fs_info
->csum_root
;
1657 struct btrfs_csum_item
*csum_item
;
1658 u32 blocksize
= root
->sectorsize
;
1659 u16 csum_size
= btrfs_super_csum_size(root
->fs_info
->super_copy
);
1660 int csums_in_item
= btrfs_item_size_nr(*leaf
, *slot
) / csum_size
;
1662 if (*csum_offset
>= csums_in_item
) {
1665 if (*slot
>= btrfs_header_nritems(*leaf
)) {
1666 ret
= btrfs_next_leaf(csum_root
, path
);
1671 *leaf
= path
->nodes
[0];
1672 *slot
= path
->slots
[0];
1674 btrfs_item_key_to_cpu(*leaf
, key
, *slot
);
1677 if (key
->offset
+ (*csum_offset
) * blocksize
>= end
)
1679 csum_item
= btrfs_item_ptr(*leaf
, *slot
, struct btrfs_csum_item
);
1680 csum_item
= (struct btrfs_csum_item
*)((unsigned char *)csum_item
1681 + (*csum_offset
) * csum_size
);
1682 read_extent_buffer(*leaf
, tree_csum
,
1683 (unsigned long)csum_item
, csum_size
);
1687 static u64
calc_data_offset(struct btrfs_key
*key
,
1688 struct chunk_record
*chunk
,
1694 int logical_stripe_nr
;
1696 int nr_data_stripes
;
1698 data_offset
= key
->offset
+ csum_offset
* blocksize
- chunk
->offset
;
1699 nr_data_stripes
= chunk
->num_stripes
;
1701 if (chunk
->type_flags
& BTRFS_BLOCK_GROUP_RAID5
)
1702 nr_data_stripes
-= 1;
1703 else if (chunk
->type_flags
& BTRFS_BLOCK_GROUP_RAID6
)
1704 nr_data_stripes
-= 2;
1706 logical_stripe_nr
= data_offset
/ chunk
->stripe_len
;
1707 dev_stripe_nr
= logical_stripe_nr
/ nr_data_stripes
;
1709 data_offset
-= logical_stripe_nr
* chunk
->stripe_len
;
1710 data_offset
+= dev_stripe_nr
* chunk
->stripe_len
;
1712 return dev_offset
+ data_offset
;
1715 static int check_one_csum(int fd
, u64 start
, u32 len
, u32 tree_csum
)
1719 u32 csum_result
= ~(u32
)0;
1724 ret
= pread64(fd
, data
, len
, start
);
1725 if (ret
< 0 || ret
!= len
) {
1730 csum_result
= btrfs_csum_data(NULL
, data
, csum_result
, len
);
1731 btrfs_csum_final(csum_result
, (char *)&csum_result
);
1732 if (csum_result
!= tree_csum
)
1739 static u64
item_end_offset(struct btrfs_root
*root
, struct btrfs_key
*key
,
1740 struct extent_buffer
*leaf
, int slot
) {
1741 u32 blocksize
= root
->sectorsize
;
1742 u16 csum_size
= btrfs_super_csum_size(root
->fs_info
->super_copy
);
1744 u64 offset
= btrfs_item_size_nr(leaf
, slot
);
1745 offset
/= csum_size
;
1746 offset
*= blocksize
;
1747 offset
+= key
->offset
;
1752 static int insert_stripe(struct list_head
*devexts
,
1753 struct recover_control
*rc
,
1754 struct chunk_record
*chunk
,
1756 struct device_extent_record
*devext
;
1757 struct btrfs_device
*dev
;
1759 devext
= list_entry(devexts
->next
, struct device_extent_record
,
1761 dev
= btrfs_find_device_by_devid(rc
->fs_devices
, devext
->objectid
,
1765 BUG_ON(btrfs_find_device_by_devid(rc
->fs_devices
, devext
->objectid
,
1768 chunk
->stripes
[index
].devid
= devext
->objectid
;
1769 chunk
->stripes
[index
].offset
= devext
->offset
;
1770 memcpy(chunk
->stripes
[index
].dev_uuid
, dev
->uuid
, BTRFS_UUID_SIZE
);
1772 list_move(&devext
->chunk_list
, &chunk
->dextents
);
1777 #define EQUAL_STRIPE (1 << 0)
1779 static int rebuild_raid_data_chunk_stripes(struct recover_control
*rc
,
1780 struct btrfs_root
*root
,
1781 struct chunk_record
*chunk
,
1787 struct btrfs_path path
;
1788 struct btrfs_key prev_key
;
1789 struct btrfs_key key
;
1790 struct btrfs_root
*csum_root
;
1791 struct extent_buffer
*leaf
;
1792 struct device_extent_record
*devext
;
1793 struct device_extent_record
*next
;
1794 struct btrfs_device
*dev
;
1795 u64 start
= chunk
->offset
;
1796 u64 end
= start
+ chunk
->stripe_len
;
1797 u64 chunk_end
= chunk
->offset
+ chunk
->length
;
1798 u64 csum_offset
= 0;
1800 u32 blocksize
= root
->sectorsize
;
1803 int num_unordered
= 0;
1804 LIST_HEAD(unordered
);
1805 LIST_HEAD(candidates
);
1807 csum_root
= root
->fs_info
->csum_root
;
1808 btrfs_init_path(&path
);
1809 list_splice_init(&chunk
->dextents
, &candidates
);
1811 if (list_is_last(candidates
.next
, &candidates
))
1814 key
.objectid
= BTRFS_EXTENT_CSUM_OBJECTID
;
1815 key
.type
= BTRFS_EXTENT_CSUM_KEY
;
1818 ret
= btrfs_search_slot(NULL
, csum_root
, &key
, &path
, 0, 0);
1820 fprintf(stderr
, "Search csum failed(%d)\n", ret
);
1823 leaf
= path
.nodes
[0];
1824 slot
= path
.slots
[0];
1826 if (slot
>= btrfs_header_nritems(leaf
)) {
1827 ret
= btrfs_next_leaf(csum_root
, &path
);
1830 "Walk tree failed(%d)\n", ret
);
1832 } else if (ret
> 0) {
1833 slot
= btrfs_header_nritems(leaf
) - 1;
1834 btrfs_item_key_to_cpu(leaf
, &key
, slot
);
1835 if (item_end_offset(root
, &key
, leaf
, slot
)
1837 csum_offset
= start
- key
.offset
;
1838 csum_offset
/= blocksize
;
1843 leaf
= path
.nodes
[0];
1844 slot
= path
.slots
[0];
1846 btrfs_item_key_to_cpu(leaf
, &key
, slot
);
1847 ret
= btrfs_previous_item(csum_root
, &path
, 0,
1848 BTRFS_EXTENT_CSUM_KEY
);
1852 if (key
.offset
>= end
)
1857 leaf
= path
.nodes
[0];
1858 slot
= path
.slots
[0];
1860 btrfs_item_key_to_cpu(leaf
, &prev_key
, slot
);
1861 if (item_end_offset(root
, &prev_key
, leaf
, slot
) > start
) {
1862 csum_offset
= start
- prev_key
.offset
;
1863 csum_offset
/= blocksize
;
1864 btrfs_item_key_to_cpu(leaf
, &key
, slot
);
1866 if (key
.offset
>= end
)
1870 if (key
.offset
+ csum_offset
* blocksize
> chunk_end
)
1874 ret
= next_csum(root
, &leaf
, &path
, &slot
, &csum_offset
, &tree_csum
,
1877 fprintf(stderr
, "Fetch csum failed\n");
1879 } else if (ret
== 1) {
1880 list_for_each_entry(devext
, &unordered
, chunk_list
)
1882 if (!(*flags
& EQUAL_STRIPE
))
1883 *flags
|= EQUAL_STRIPE
;
1885 } else if (ret
== 2)
1888 list_for_each_entry_safe(devext
, next
, &candidates
, chunk_list
) {
1889 data_offset
= calc_data_offset(&key
, chunk
, devext
->offset
,
1890 csum_offset
, blocksize
);
1891 dev
= btrfs_find_device_by_devid(rc
->fs_devices
,
1892 devext
->objectid
, 0);
1897 BUG_ON(btrfs_find_device_by_devid(rc
->fs_devices
,
1898 devext
->objectid
, 1));
1900 ret
= check_one_csum(dev
->fd
, data_offset
, blocksize
,
1905 list_move(&devext
->chunk_list
, &unordered
);
1908 if (list_empty(&candidates
)) {
1909 list_for_each_entry(devext
, &unordered
, chunk_list
)
1911 if (chunk
->type_flags
& BTRFS_BLOCK_GROUP_RAID6
1912 && num_unordered
== 2) {
1913 list_splice_init(&unordered
, &chunk
->dextents
);
1914 btrfs_release_path(&path
);
1922 if (list_is_last(candidates
.next
, &candidates
)) {
1923 index
= btrfs_calc_stripe_index(chunk
,
1924 key
.offset
+ csum_offset
* blocksize
);
1925 if (chunk
->stripes
[index
].devid
)
1927 ret
= insert_stripe(&candidates
, rc
, chunk
, index
);
1935 start
= btrfs_next_stripe_logical_offset(chunk
, start
);
1936 end
= min(start
+ chunk
->stripe_len
, chunk_end
);
1937 list_splice_init(&unordered
, &candidates
);
1938 btrfs_release_path(&path
);
1940 if (end
< chunk_end
)
1944 list_splice_init(&candidates
, &unordered
);
1945 list_for_each_entry(devext
, &unordered
, chunk_list
)
1947 if (num_unordered
== 1) {
1948 for (i
= 0; i
< chunk
->num_stripes
; i
++) {
1949 if (!chunk
->stripes
[i
].devid
) {
1954 ret
= insert_stripe(&unordered
, rc
, chunk
, index
);
1958 if ((num_unordered
== 2 && chunk
->type_flags
1959 & BTRFS_BLOCK_GROUP_RAID5
)
1960 || (num_unordered
== 3 && chunk
->type_flags
1961 & BTRFS_BLOCK_GROUP_RAID6
)) {
1962 for (i
= 0; i
< chunk
->num_stripes
; i
++) {
1963 if (!chunk
->stripes
[i
].devid
) {
1964 ret
= insert_stripe(&unordered
, rc
,
1973 ret
= !!ret
|| (list_empty(&unordered
) ? 0 : 1);
1974 list_splice_init(&candidates
, &chunk
->dextents
);
1975 list_splice_init(&unordered
, &chunk
->dextents
);
1976 btrfs_release_path(&path
);
1981 static int btrfs_rebuild_ordered_data_chunk_stripes(struct recover_control
*rc
,
1982 struct btrfs_root
*root
)
1984 struct chunk_record
*chunk
;
1985 struct chunk_record
*next
;
1990 list_for_each_entry_safe(chunk
, next
, &rc
->unrepaired_chunks
, list
) {
1991 if ((chunk
->type_flags
& BTRFS_BLOCK_GROUP_DATA
)
1992 && (chunk
->type_flags
& BTRFS_ORDERED_RAID
)) {
1994 err
= rebuild_raid_data_chunk_stripes(rc
, root
, chunk
,
1997 list_move(&chunk
->list
, &rc
->bad_chunks
);
1998 if (flags
& EQUAL_STRIPE
)
2000 "Failure: too many equal stripes in chunk[%llu %llu]\n",
2001 chunk
->offset
, chunk
->length
);
2005 list_move(&chunk
->list
, &rc
->good_chunks
);
2011 static int btrfs_recover_chunks(struct recover_control
*rc
)
2013 struct chunk_record
*chunk
;
2014 struct block_group_record
*bg
;
2015 struct block_group_record
*next
;
2016 LIST_HEAD(new_chunks
);
2021 /* create the chunk by block group */
2022 list_for_each_entry_safe(bg
, next
, &rc
->bg
.block_groups
, list
) {
2023 nstripes
= btrfs_get_device_extents(bg
->objectid
,
2024 &rc
->devext
.no_chunk_orphans
,
2026 chunk
= malloc(btrfs_chunk_record_size(nstripes
));
2029 memset(chunk
, 0, btrfs_chunk_record_size(nstripes
));
2030 INIT_LIST_HEAD(&chunk
->dextents
);
2032 chunk
->cache
.start
= bg
->objectid
;
2033 chunk
->cache
.size
= bg
->offset
;
2034 chunk
->objectid
= BTRFS_FIRST_CHUNK_TREE_OBJECTID
;
2035 chunk
->type
= BTRFS_CHUNK_ITEM_KEY
;
2036 chunk
->offset
= bg
->objectid
;
2037 chunk
->generation
= bg
->generation
;
2038 chunk
->length
= bg
->offset
;
2039 chunk
->owner
= BTRFS_CHUNK_TREE_OBJECTID
;
2040 chunk
->stripe_len
= BTRFS_STRIPE_LEN
;
2041 chunk
->type_flags
= bg
->flags
;
2042 chunk
->io_width
= BTRFS_STRIPE_LEN
;
2043 chunk
->io_align
= BTRFS_STRIPE_LEN
;
2044 chunk
->sector_size
= rc
->sectorsize
;
2045 chunk
->sub_stripes
= calc_sub_nstripes(bg
->flags
);
2047 ret
= insert_cache_extent(&rc
->chunk
, &chunk
->cache
);
2051 list_add_tail(&chunk
->list
, &rc
->bad_chunks
);
2055 list_splice_init(&devexts
, &chunk
->dextents
);
2057 ret
= btrfs_verify_device_extents(bg
, &devexts
, nstripes
);
2059 list_add_tail(&chunk
->list
, &rc
->bad_chunks
);
2063 chunk
->num_stripes
= nstripes
;
2064 ret
= btrfs_rebuild_chunk_stripes(rc
, chunk
);
2066 list_add_tail(&chunk
->list
, &rc
->unrepaired_chunks
);
2068 list_add_tail(&chunk
->list
, &rc
->bad_chunks
);
2070 list_add_tail(&chunk
->list
, &rc
->good_chunks
);
2073 * Don't worry about the lost orphan device extents, they don't
2074 * have its chunk and block group, they must be the old ones that
2081 * Return 0 when succesful, < 0 on error and > 0 if aborted by user
2083 int btrfs_recover_chunk_tree(char *path
, int verbose
, int yes
)
2086 struct btrfs_root
*root
= NULL
;
2087 struct btrfs_trans_handle
*trans
;
2088 struct recover_control rc
;
2090 init_recover_control(&rc
, verbose
, yes
);
2092 ret
= recover_prepare(&rc
, path
);
2094 fprintf(stderr
, "recover prepare error\n");
2098 ret
= scan_devices(&rc
);
2100 fprintf(stderr
, "scan chunk headers error\n");
2104 if (cache_tree_empty(&rc
.chunk
) &&
2105 cache_tree_empty(&rc
.bg
.tree
) &&
2106 cache_tree_empty(&rc
.devext
.tree
)) {
2107 fprintf(stderr
, "no recoverable chunk\n");
2111 print_scan_result(&rc
);
2113 ret
= check_chunks(&rc
.chunk
, &rc
.bg
, &rc
.devext
, &rc
.good_chunks
,
2115 print_check_result(&rc
);
2117 if (!list_empty(&rc
.bg
.block_groups
) ||
2118 !list_empty(&rc
.devext
.no_chunk_orphans
)) {
2119 ret
= btrfs_recover_chunks(&rc
);
2124 * If the chunk is healthy, its block group item and device
2125 * extent item should be written on the disks. So, it is very
2126 * likely that the bad chunk is a old one that has been
2127 * droppped from the fs. Don't deal with them now, we will
2128 * check it after the fs is opened.
2131 fprintf(stderr
, "Check chunks successfully with no orphans\n");
2135 root
= open_ctree_with_broken_chunk(&rc
);
2137 fprintf(stderr
, "open with broken chunk error\n");
2138 ret
= PTR_ERR(root
);
2142 ret
= check_all_chunks_by_metadata(&rc
, root
);
2144 fprintf(stderr
, "The chunks in memory can not match the metadata of the fs. Repair failed.\n");
2145 goto fail_close_ctree
;
2148 ret
= btrfs_rebuild_ordered_data_chunk_stripes(&rc
, root
);
2150 fprintf(stderr
, "Failed to rebuild ordered chunk stripes.\n");
2151 goto fail_close_ctree
;
2155 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?");
2158 goto fail_close_ctree
;
2162 trans
= btrfs_start_transaction(root
, 1);
2163 ret
= remove_chunk_extent_item(trans
, &rc
, root
);
2166 ret
= rebuild_chunk_tree(trans
, &rc
, root
);
2169 ret
= rebuild_sys_array(&rc
, root
);
2172 btrfs_commit_transaction(trans
, root
);
2176 free_recover_control(&rc
);