?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Btrfs progs v4.17.1
[btrfs-progs-unstable/devel.git] / chunk-recover.c
blob1d30db51d8ed056b1fc9d7600c3488528ef1aad1
1 /*
2 * Copyright (C) 2013 FUJITSU LIMITED. All rights reserved.
3 *
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
12 *
13 * You should have received a copy of the GNU General Public
14 * License along with this program; if not, write to the
15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16 * Boston, MA 021110-1307, USA.
17 */
18
19 #include "kerncompat.h"
20 #include "androidcompat.h"
21
22 #include <stdio.h>
23 #include <stdio_ext.h>
24 #include <stdlib.h>
25 #include <sys/types.h>
26 #include <sys/stat.h>
27 #include <fcntl.h>
28 #include <unistd.h>
29 #include <uuid/uuid.h>
30 #include <pthread.h>
31
32 #include "list.h"
33 #include "radix-tree.h"
34 #include "ctree.h"
35 #include "extent-cache.h"
36 #include "disk-io.h"
37 #include "volumes.h"
38 #include "transaction.h"
39 #include "crc32c.h"
40 #include "utils.h"
41 #include "btrfsck.h"
42 #include "commands.h"
43
44 struct recover_control {
45 int verbose;
46 int yes;
47
48 u16 csum_size;
49 u32 sectorsize;
50 u32 nodesize;
51 u64 generation;
52 u64 chunk_root_generation;
53
54 struct btrfs_fs_devices *fs_devices;
55
56 struct cache_tree chunk;
57 struct block_group_tree bg;
58 struct device_extent_tree devext;
59 struct cache_tree eb_cache;
60
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;
66 };
67
68 struct extent_record {
69 struct cache_extent cache;
70 u64 generation;
71 u8 csum[BTRFS_CSUM_SIZE];
72 struct btrfs_device *devices[BTRFS_MAX_MIRRORS];
73 u64 offsets[BTRFS_MAX_MIRRORS];
74 int nmirrors;
75 };
76
77 struct device_scan {
78 struct recover_control *rc;
79 struct btrfs_device *dev;
80 int fd;
81 u64 bytenr;
82 };
83
84 static struct extent_record *btrfs_new_extent_record(struct extent_buffer *eb)
85 {
86 struct extent_record *rec;
87
88 rec = calloc(1, sizeof(*rec));
89 if (!rec) {
90 fprintf(stderr, "Fail to allocate memory for extent record.\n");
91 exit(1);
92 }
93
94 rec->cache.start = btrfs_header_bytenr(eb);
95 rec->cache.size = eb->len;
96 rec->generation = btrfs_header_generation(eb);
97 read_extent_buffer(eb, rec->csum, (unsigned long)btrfs_header_csum(eb),
98 BTRFS_CSUM_SIZE);
99 return rec;
100 }
101
102 static int process_extent_buffer(struct cache_tree *eb_cache,
103 struct extent_buffer *eb,
104 struct btrfs_device *device, u64 offset)
105 {
106 struct extent_record *rec;
107 struct extent_record *exist;
108 struct cache_extent *cache;
109 int ret = 0;
110
111 rec = btrfs_new_extent_record(eb);
112 if (!rec->cache.size)
113 goto free_out;
114 again:
115 cache = lookup_cache_extent(eb_cache,
116 rec->cache.start,
117 rec->cache.size);
118 if (cache) {
119 exist = container_of(cache, struct extent_record, cache);
120
121 if (exist->generation > rec->generation)
122 goto free_out;
123 if (exist->generation == rec->generation) {
124 if (exist->cache.start != rec->cache.start ||
125 exist->cache.size != rec->cache.size ||
126 memcmp(exist->csum, rec->csum, BTRFS_CSUM_SIZE)) {
127 ret = -EEXIST;
128 } else {
129 BUG_ON(exist->nmirrors >= BTRFS_MAX_MIRRORS);
130 exist->devices[exist->nmirrors] = device;
131 exist->offsets[exist->nmirrors] = offset;
132 exist->nmirrors++;
133 }
134 goto free_out;
135 }
136 remove_cache_extent(eb_cache, cache);
137 free(exist);
138 goto again;
139 }
140
141 rec->devices[0] = device;
142 rec->offsets[0] = offset;
143 rec->nmirrors++;
144 ret = insert_cache_extent(eb_cache, &rec->cache);
145 BUG_ON(ret);
146 out:
147 return ret;
148 free_out:
149 free(rec);
150 goto out;
151 }
152
153 static void free_extent_record(struct cache_extent *cache)
154 {
155 struct extent_record *er;
156
157 er = container_of(cache, struct extent_record, cache);
158 free(er);
159 }
160
161 FREE_EXTENT_CACHE_BASED_TREE(extent_record, free_extent_record);
162
163 static struct btrfs_chunk *create_chunk_item(struct chunk_record *record)
164 {
165 struct btrfs_chunk *ret;
166 struct btrfs_stripe *chunk_stripe;
167 int i;
168
169 if (!record || record->num_stripes == 0)
170 return NULL;
171 ret = malloc(btrfs_chunk_item_size(record->num_stripes));
172 if (!ret)
173 return NULL;
174 btrfs_set_stack_chunk_length(ret, record->length);
175 btrfs_set_stack_chunk_owner(ret, record->owner);
176 btrfs_set_stack_chunk_stripe_len(ret, record->stripe_len);
177 btrfs_set_stack_chunk_type(ret, record->type_flags);
178 btrfs_set_stack_chunk_io_align(ret, record->io_align);
179 btrfs_set_stack_chunk_io_width(ret, record->io_width);
180 btrfs_set_stack_chunk_sector_size(ret, record->sector_size);
181 btrfs_set_stack_chunk_num_stripes(ret, record->num_stripes);
182 btrfs_set_stack_chunk_sub_stripes(ret, record->sub_stripes);
183 for (i = 0, chunk_stripe = &ret->stripe; i < record->num_stripes;
184 i++, chunk_stripe++) {
185 btrfs_set_stack_stripe_devid(chunk_stripe,
186 record->stripes[i].devid);
187 btrfs_set_stack_stripe_offset(chunk_stripe,
188 record->stripes[i].offset);
189 memcpy(chunk_stripe->dev_uuid, record->stripes[i].dev_uuid,
190 BTRFS_UUID_SIZE);
191 }
192 return ret;
193 }
194
195 static void init_recover_control(struct recover_control *rc, int verbose,
196 int yes)
197 {
198 memset(rc, 0, sizeof(struct recover_control));
199 cache_tree_init(&rc->chunk);
200 cache_tree_init(&rc->eb_cache);
201 block_group_tree_init(&rc->bg);
202 device_extent_tree_init(&rc->devext);
203
204 INIT_LIST_HEAD(&rc->good_chunks);
205 INIT_LIST_HEAD(&rc->bad_chunks);
206 INIT_LIST_HEAD(&rc->rebuild_chunks);
207 INIT_LIST_HEAD(&rc->unrepaired_chunks);
208
209 rc->verbose = verbose;
210 rc->yes = yes;
211 pthread_mutex_init(&rc->rc_lock, NULL);
212 }
213
214 static void free_recover_control(struct recover_control *rc)
215 {
216 free_block_group_tree(&rc->bg);
217 free_chunk_cache_tree(&rc->chunk);
218 free_device_extent_tree(&rc->devext);
219 free_extent_record_tree(&rc->eb_cache);
220 pthread_mutex_destroy(&rc->rc_lock);
221 }
222
223 static int process_block_group_item(struct block_group_tree *bg_cache,
224 struct extent_buffer *leaf,
225 struct btrfs_key *key, int slot)
226 {
227 struct block_group_record *rec;
228 struct block_group_record *exist;
229 struct cache_extent *cache;
230 int ret = 0;
231
232 rec = btrfs_new_block_group_record(leaf, key, slot);
233 if (!rec->cache.size)
234 goto free_out;
235 again:
236 cache = lookup_cache_extent(&bg_cache->tree,
237 rec->cache.start,
238 rec->cache.size);
239 if (cache) {
240 exist = container_of(cache, struct block_group_record, cache);
241
242 /*check the generation and replace if needed*/
243 if (exist->generation > rec->generation)
244 goto free_out;
245 if (exist->generation == rec->generation) {
246 int offset = offsetof(struct block_group_record,
247 generation);
248 /*
249 * According to the current kernel code, the following
250 * case is impossible, or there is something wrong in
251 * the kernel code.
252 */
253 if (memcmp(((void *)exist) + offset,
254 ((void *)rec) + offset,
255 sizeof(*rec) - offset))
256 ret = -EEXIST;
257 goto free_out;
258 }
259 remove_cache_extent(&bg_cache->tree, cache);
260 list_del_init(&exist->list);
261 free(exist);
262 /*
263 * We must do search again to avoid the following cache.
264 * /--old bg 1--//--old bg 2--/
265 * /--new bg--/
266 */
267 goto again;
268 }
269
270 ret = insert_block_group_record(bg_cache, rec);
271 BUG_ON(ret);
272 out:
273 return ret;
274 free_out:
275 free(rec);
276 goto out;
277 }
278
279 static int process_chunk_item(struct cache_tree *chunk_cache,
280 struct extent_buffer *leaf, struct btrfs_key *key,
281 int slot)
282 {
283 struct chunk_record *rec;
284 struct chunk_record *exist;
285 struct cache_extent *cache;
286 int ret = 0;
287
288 rec = btrfs_new_chunk_record(leaf, key, slot);
289 if (!rec->cache.size)
290 goto free_out;
291 again:
292 cache = lookup_cache_extent(chunk_cache, rec->offset, rec->length);
293 if (cache) {
294 exist = container_of(cache, struct chunk_record, cache);
295
296 if (exist->generation > rec->generation)
297 goto free_out;
298 if (exist->generation == rec->generation) {
299 int num_stripes = rec->num_stripes;
300 int rec_size = btrfs_chunk_record_size(num_stripes);
301 int offset = offsetof(struct chunk_record, generation);
302
303 if (exist->num_stripes != rec->num_stripes ||
304 memcmp(((void *)exist) + offset,
305 ((void *)rec) + offset,
306 rec_size - offset))
307 ret = -EEXIST;
308 goto free_out;
309 }
310 remove_cache_extent(chunk_cache, cache);
311 free(exist);
312 goto again;
313 }
314 ret = insert_cache_extent(chunk_cache, &rec->cache);
315 BUG_ON(ret);
316 out:
317 return ret;
318 free_out:
319 free(rec);
320 goto out;
321 }
322
323 static int process_device_extent_item(struct device_extent_tree *devext_cache,
324 struct extent_buffer *leaf,
325 struct btrfs_key *key, int slot)
326 {
327 struct device_extent_record *rec;
328 struct device_extent_record *exist;
329 struct cache_extent *cache;
330 int ret = 0;
331
332 rec = btrfs_new_device_extent_record(leaf, key, slot);
333 if (!rec->cache.size)
334 goto free_out;
335 again:
336 cache = lookup_cache_extent2(&devext_cache->tree,
337 rec->cache.objectid,
338 rec->cache.start,
339 rec->cache.size);
340 if (cache) {
341 exist = container_of(cache, struct device_extent_record, cache);
342 if (exist->generation > rec->generation)
343 goto free_out;
344 if (exist->generation == rec->generation) {
345 int offset = offsetof(struct device_extent_record,
346 generation);
347 if (memcmp(((void *)exist) + offset,
348 ((void *)rec) + offset,
349 sizeof(*rec) - offset))
350 ret = -EEXIST;
351 goto free_out;
352 }
353 remove_cache_extent(&devext_cache->tree, cache);
354 list_del_init(&exist->chunk_list);
355 list_del_init(&exist->device_list);
356 free(exist);
357 goto again;
358 }
359
360 ret = insert_device_extent_record(devext_cache, rec);
361 BUG_ON(ret);
362 out:
363 return ret;
364 free_out:
365 free(rec);
366 goto out;
367 }
368
369 static void print_block_group_info(struct block_group_record *rec, char *prefix)
370 {
371 if (prefix)
372 printf("%s", prefix);
373 printf("Block Group: start = %llu, len = %llu, flag = %llx\n",
374 rec->objectid, rec->offset, rec->flags);
375 }
376
377 static void print_block_group_tree(struct block_group_tree *tree)
378 {
379 struct cache_extent *cache;
380 struct block_group_record *rec;
381
382 printf("All Block Groups:\n");
383 for (cache = first_cache_extent(&tree->tree); cache;
384 cache = next_cache_extent(cache)) {
385 rec = container_of(cache, struct block_group_record, cache);
386 print_block_group_info(rec, "\t");
387 }
388 printf("\n");
389 }
390
391 static void print_stripe_info(struct stripe *data, char *prefix1, char *prefix2,
392 int index)
393 {
394 if (prefix1)
395 printf("%s", prefix1);
396 if (prefix2)
397 printf("%s", prefix2);
398 printf("[%2d] Stripe: devid = %llu, offset = %llu\n",
399 index, data->devid, data->offset);
400 }
401
402 static void print_chunk_self_info(struct chunk_record *rec, char *prefix)
403 {
404 int i;
405
406 if (prefix)
407 printf("%s", prefix);
408 printf("Chunk: start = %llu, len = %llu, type = %llx, num_stripes = %u\n",
409 rec->offset, rec->length, rec->type_flags, rec->num_stripes);
410 if (prefix)
411 printf("%s", prefix);
412 printf(" Stripes list:\n");
413 for (i = 0; i < rec->num_stripes; i++)
414 print_stripe_info(&rec->stripes[i], prefix, " ", i);
415 }
416
417 static void print_chunk_tree(struct cache_tree *tree)
418 {
419 struct cache_extent *n;
420 struct chunk_record *entry;
421
422 printf("All Chunks:\n");
423 for (n = first_cache_extent(tree); n;
424 n = next_cache_extent(n)) {
425 entry = container_of(n, struct chunk_record, cache);
426 print_chunk_self_info(entry, "\t");
427 }
428 printf("\n");
429 }
430
431 static void print_device_extent_info(struct device_extent_record *rec,
432 char *prefix)
433 {
434 if (prefix)
435 printf("%s", prefix);
436 printf("Device extent: devid = %llu, start = %llu, len = %llu, chunk offset = %llu\n",
437 rec->objectid, rec->offset, rec->length, rec->chunk_offset);
438 }
439
440 static void print_device_extent_tree(struct device_extent_tree *tree)
441 {
442 struct cache_extent *n;
443 struct device_extent_record *entry;
444
445 printf("All Device Extents:\n");
446 for (n = first_cache_extent(&tree->tree); n;
447 n = next_cache_extent(n)) {
448 entry = container_of(n, struct device_extent_record, cache);
449 print_device_extent_info(entry, "\t");
450 }
451 printf("\n");
452 }
453
454 static void print_scan_result(struct recover_control *rc)
455 {
456 if (!rc->verbose)
457 return;
458
459 printf("DEVICE SCAN RESULT:\n");
460 printf("Filesystem Information:\n");
461 printf("\tsectorsize: %d\n", rc->sectorsize);
462 printf("\tnodesize: %d\n", rc->nodesize);
463 printf("\ttree root generation: %llu\n", rc->generation);
464 printf("\tchunk root generation: %llu\n", rc->chunk_root_generation);
465 printf("\n");
466
467 print_all_devices(&rc->fs_devices->devices);
468 print_block_group_tree(&rc->bg);
469 print_chunk_tree(&rc->chunk);
470 print_device_extent_tree(&rc->devext);
471 }
472
473 static void print_chunk_info(struct chunk_record *chunk, char *prefix)
474 {
475 struct device_extent_record *devext;
476 int i;
477
478 print_chunk_self_info(chunk, prefix);
479 if (prefix)
480 printf("%s", prefix);
481 if (chunk->bg_rec)
482 print_block_group_info(chunk->bg_rec, " ");
483 else
484 printf(" No block group.\n");
485 if (prefix)
486 printf("%s", prefix);
487 if (list_empty(&chunk->dextents)) {
488 printf(" No device extent.\n");
489 } else {
490 printf(" Device extent list:\n");
491 i = 0;
492 list_for_each_entry(devext, &chunk->dextents, chunk_list) {
493 if (prefix)
494 printf("%s", prefix);
495 printf("%s[%2d]", " ", i);
496 print_device_extent_info(devext, NULL);
497 i++;
498 }
499 }
500 }
501
502 static void print_check_result(struct recover_control *rc)
503 {
504 struct chunk_record *chunk;
505 struct block_group_record *bg;
506 struct device_extent_record *devext;
507 int total = 0;
508 int good = 0;
509 int bad = 0;
510
511 if (!rc->verbose)
512 return;
513
514 printf("CHECK RESULT:\n");
515 printf("Recoverable Chunks:\n");
516 list_for_each_entry(chunk, &rc->good_chunks, list) {
517 print_chunk_info(chunk, " ");
518 good++;
519 total++;
520 }
521 list_for_each_entry(chunk, &rc->rebuild_chunks, list) {
522 print_chunk_info(chunk, " ");
523 good++;
524 total++;
525 }
526 list_for_each_entry(chunk, &rc->unrepaired_chunks, list) {
527 print_chunk_info(chunk, " ");
528 good++;
529 total++;
530 }
531 printf("Unrecoverable Chunks:\n");
532 list_for_each_entry(chunk, &rc->bad_chunks, list) {
533 print_chunk_info(chunk, " ");
534 bad++;
535 total++;
536 }
537 printf("\n");
538 printf("Total Chunks:\t\t%d\n", total);
539 printf(" Recoverable:\t\t%d\n", good);
540 printf(" Unrecoverable:\t%d\n", bad);
541
542 printf("\n");
543 printf("Orphan Block Groups:\n");
544 list_for_each_entry(bg, &rc->bg.block_groups, list)
545 print_block_group_info(bg, " ");
546
547 printf("\n");
548 printf("Orphan Device Extents:\n");
549 list_for_each_entry(devext, &rc->devext.no_chunk_orphans, chunk_list)
550 print_device_extent_info(devext, " ");
551 printf("\n");
552 }
553
554 static int check_chunk_by_metadata(struct recover_control *rc,
555 struct btrfs_root *root,
556 struct chunk_record *chunk, int bg_only)
557 {
558 int ret;
559 int i;
560 int slot;
561 struct btrfs_path path;
562 struct btrfs_key key;
563 struct btrfs_root *dev_root;
564 struct stripe *stripe;
565 struct btrfs_dev_extent *dev_extent;
566 struct btrfs_block_group_item *bg_ptr;
567 struct extent_buffer *l;
568
569 btrfs_init_path(&path);
570
571 if (bg_only)
572 goto bg_check;
573
574 dev_root = root->fs_info->dev_root;
575 for (i = 0; i < chunk->num_stripes; i++) {
576 stripe = &chunk->stripes[i];
577
578 key.objectid = stripe->devid;
579 key.offset = stripe->offset;
580 key.type = BTRFS_DEV_EXTENT_KEY;
581
582 ret = btrfs_search_slot(NULL, dev_root, &key, &path, 0, 0);
583 if (ret < 0) {
584 fprintf(stderr, "Search device extent failed(%d)\n",
585 ret);
586 btrfs_release_path(&path);
587 return ret;
588 } else if (ret > 0) {
589 if (rc->verbose)
590 fprintf(stderr,
591 "No device extent[%llu, %llu]\n",
592 stripe->devid, stripe->offset);
593 btrfs_release_path(&path);
594 return -ENOENT;
595 }
596 l = path.nodes[0];
597 slot = path.slots[0];
598 dev_extent = btrfs_item_ptr(l, slot, struct btrfs_dev_extent);
599 if (chunk->offset !=
600 btrfs_dev_extent_chunk_offset(l, dev_extent)) {
601 if (rc->verbose)
602 fprintf(stderr,
603 "Device tree mismatch with chunks dev_extent[%llu, %llu], chunk[%llu, %llu]\n",
604 btrfs_dev_extent_chunk_offset(l,
605 dev_extent),
606 btrfs_dev_extent_length(l, dev_extent),
607 chunk->offset, chunk->length);
608 btrfs_release_path(&path);
609 return -ENOENT;
610 }
611 btrfs_release_path(&path);
612 }
613
614 bg_check:
615 key.objectid = chunk->offset;
616 key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
617 key.offset = chunk->length;
618
619 ret = btrfs_search_slot(NULL, root->fs_info->extent_root, &key, &path,
620 0, 0);
621 if (ret < 0) {
622 fprintf(stderr, "Search block group failed(%d)\n", ret);
623 btrfs_release_path(&path);
624 return ret;
625 } else if (ret > 0) {
626 if (rc->verbose)
627 fprintf(stderr, "No block group[%llu, %llu]\n",
628 key.objectid, key.offset);
629 btrfs_release_path(&path);
630 return -ENOENT;
631 }
632
633 l = path.nodes[0];
634 slot = path.slots[0];
635 bg_ptr = btrfs_item_ptr(l, slot, struct btrfs_block_group_item);
636 if (chunk->type_flags != btrfs_disk_block_group_flags(l, bg_ptr)) {
637 if (rc->verbose)
638 fprintf(stderr,
639 "Chunk[%llu, %llu]'s type(%llu) is different with Block Group's type(%llu)\n",
640 chunk->offset, chunk->length, chunk->type_flags,
641 btrfs_disk_block_group_flags(l, bg_ptr));
642 btrfs_release_path(&path);
643 return -ENOENT;
644 }
645 btrfs_release_path(&path);
646 return 0;
647 }
648
649 static int check_all_chunks_by_metadata(struct recover_control *rc,
650 struct btrfs_root *root)
651 {
652 struct chunk_record *chunk;
653 struct chunk_record *next;
654 LIST_HEAD(orphan_chunks);
655 int ret = 0;
656 int err;
657
658 list_for_each_entry_safe(chunk, next, &rc->good_chunks, list) {
659 err = check_chunk_by_metadata(rc, root, chunk, 0);
660 if (err) {
661 if (err == -ENOENT)
662 list_move_tail(&chunk->list, &orphan_chunks);
663 else if (err && !ret)
664 ret = err;
665 }
666 }
667
668 list_for_each_entry_safe(chunk, next, &rc->unrepaired_chunks, list) {
669 err = check_chunk_by_metadata(rc, root, chunk, 1);
670 if (err == -ENOENT)
671 list_move_tail(&chunk->list, &orphan_chunks);
672 else if (err && !ret)
673 ret = err;
674 }
675
676 list_for_each_entry(chunk, &rc->bad_chunks, list) {
677 err = check_chunk_by_metadata(rc, root, chunk, 1);
678 if (err != -ENOENT && !ret)
679 ret = err ? err : -EINVAL;
680 }
681 list_splice(&orphan_chunks, &rc->bad_chunks);
682 return ret;
683 }
684
685 static int extract_metadata_record(struct recover_control *rc,
686 struct extent_buffer *leaf)
687 {
688 struct btrfs_key key;
689 int ret = 0;
690 int i;
691 u32 nritems;
692
693 nritems = btrfs_header_nritems(leaf);
694 for (i = 0; i < nritems; i++) {
695 btrfs_item_key_to_cpu(leaf, &key, i);
696 switch (key.type) {
697 case BTRFS_BLOCK_GROUP_ITEM_KEY:
698 pthread_mutex_lock(&rc->rc_lock);
699 ret = process_block_group_item(&rc->bg, leaf, &key, i);
700 pthread_mutex_unlock(&rc->rc_lock);
701 break;
702 case BTRFS_CHUNK_ITEM_KEY:
703 pthread_mutex_lock(&rc->rc_lock);
704 ret = process_chunk_item(&rc->chunk, leaf, &key, i);
705 pthread_mutex_unlock(&rc->rc_lock);
706 break;
707 case BTRFS_DEV_EXTENT_KEY:
708 pthread_mutex_lock(&rc->rc_lock);
709 ret = process_device_extent_item(&rc->devext, leaf,
710 &key, i);
711 pthread_mutex_unlock(&rc->rc_lock);
712 break;
713 }
714 if (ret)
715 break;
716 }
717 return ret;
718 }
719
720 static inline int is_super_block_address(u64 offset)
721 {
722 int i;
723
724 for (i = 0; i < BTRFS_SUPER_MIRROR_MAX; i++) {
725 if (offset == btrfs_sb_offset(i))
726 return 1;
727 }
728 return 0;
729 }
730
731 static int scan_one_device(void *dev_scan_struct)
732 {
733 struct extent_buffer *buf;
734 u64 bytenr;
735 int ret = 0;
736 struct device_scan *dev_scan = (struct device_scan *)dev_scan_struct;
737 struct recover_control *rc = dev_scan->rc;
738 struct btrfs_device *device = dev_scan->dev;
739 int fd = dev_scan->fd;
740 int oldtype;
741
742 ret = pthread_setcanceltype(PTHREAD_CANCEL_ASYNCHRONOUS, &oldtype);
743 if (ret)
744 return 1;
745
746 buf = malloc(sizeof(*buf) + rc->nodesize);
747 if (!buf)
748 return -ENOMEM;
749 buf->len = rc->nodesize;
750
751 bytenr = 0;
752 while (1) {
753 dev_scan->bytenr = bytenr;
754
755 if (is_super_block_address(bytenr))
756 bytenr += rc->sectorsize;
757
758 if (pread64(fd, buf->data, rc->nodesize, bytenr) <
759 rc->nodesize)
760 break;
761
762 if (memcmp_extent_buffer(buf, rc->fs_devices->fsid,
763 btrfs_header_fsid(),
764 BTRFS_FSID_SIZE)) {
765 bytenr += rc->sectorsize;
766 continue;
767 }
768
769 if (verify_tree_block_csum_silent(buf, rc->csum_size)) {
770 bytenr += rc->sectorsize;
771 continue;
772 }
773
774 pthread_mutex_lock(&rc->rc_lock);
775 ret = process_extent_buffer(&rc->eb_cache, buf, device, bytenr);
776 pthread_mutex_unlock(&rc->rc_lock);
777 if (ret)
778 goto out;
779
780 if (btrfs_header_level(buf) != 0)
781 goto next_node;
782
783 switch (btrfs_header_owner(buf)) {
784 case BTRFS_EXTENT_TREE_OBJECTID:
785 case BTRFS_DEV_TREE_OBJECTID:
786 /* different tree use different generation */
787 if (btrfs_header_generation(buf) > rc->generation)
788 break;
789 ret = extract_metadata_record(rc, buf);
790 if (ret)
791 goto out;
792 break;
793 case BTRFS_CHUNK_TREE_OBJECTID:
794 if (btrfs_header_generation(buf) >
795 rc->chunk_root_generation)
796 break;
797 ret = extract_metadata_record(rc, buf);
798 if (ret)
799 goto out;
800 break;
801 }
802 next_node:
803 bytenr += rc->nodesize;
804 }
805 out:
806 close(fd);
807 free(buf);
808 return ret;
809 }
810
811 static int scan_devices(struct recover_control *rc)
812 {
813 int ret = 0;
814 int fd;
815 struct btrfs_device *dev;
816 struct device_scan *dev_scans;
817 pthread_t *t_scans;
818 long *t_rets;
819 int devnr = 0;
820 int devidx = 0;
821 int i;
822 int all_done;
823
824 list_for_each_entry(dev, &rc->fs_devices->devices, dev_list)
825 devnr++;
826 dev_scans = (struct device_scan *)malloc(sizeof(struct device_scan)
827 * devnr);
828 if (!dev_scans)
829 return -ENOMEM;
830 t_scans = (pthread_t *)malloc(sizeof(pthread_t) * devnr);
831 if (!t_scans) {
832 free(dev_scans);
833 return -ENOMEM;
834 }
835 t_rets = (long *)malloc(sizeof(long) * devnr);
836 if (!t_rets) {
837 free(dev_scans);
838 free(t_scans);
839 return -ENOMEM;
840 }
841
842 list_for_each_entry(dev, &rc->fs_devices->devices, dev_list) {
843 fd = open(dev->name, O_RDONLY);
844 if (fd < 0) {
845 fprintf(stderr, "Failed to open device %s\n",
846 dev->name);
847 ret = 1;
848 goto out2;
849 }
850 dev_scans[devidx].rc = rc;
851 dev_scans[devidx].dev = dev;
852 dev_scans[devidx].fd = fd;
853 dev_scans[devidx].bytenr = -1;
854 devidx++;
855 }
856
857 for (i = 0; i < devidx; i++) {
858 ret = pthread_create(&t_scans[i], NULL,
859 (void *)scan_one_device,
860 (void *)&dev_scans[i]);
861 if (ret)
862 goto out1;
863
864 dev_scans[i].bytenr = 0;
865 }
866
867 while (1) {
868 all_done = 1;
869 for (i = 0; i < devidx; i++) {
870 if (dev_scans[i].bytenr == -1)
871 continue;
872 ret = pthread_tryjoin_np(t_scans[i],
873 (void **)&t_rets[i]);
874 if (ret == EBUSY) {
875 all_done = 0;
876 continue;
877 }
878 if (ret || t_rets[i]) {
879 ret = 1;
880 goto out1;
881 }
882 dev_scans[i].bytenr = -1;
883 }
884
885 printf("\rScanning: ");
886 for (i = 0; i < devidx; i++) {
887 if (dev_scans[i].bytenr == -1)
888 printf("%sDONE in dev%d",
889 i ? ", " : "", i);
890 else
891 printf("%s%llu in dev%d",
892 i ? ", " : "", dev_scans[i].bytenr, i);
893 }
894 /* clear chars if exist in tail */
895 printf(" ");
896 printf("\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b\b");
897 fflush(stdout);
898
899 if (all_done) {
900 printf("\n");
901 break;
902 }
903
904 sleep(1);
905 }
906 out1:
907 for (i = 0; i < devidx; i++) {
908 if (dev_scans[i].bytenr == -1)
909 continue;
910 pthread_cancel(t_scans[i]);
911 }
912 out2:
913 free(dev_scans);
914 free(t_scans);
915 free(t_rets);
916 return !!ret;
917 }
918
919 static int build_device_map_by_chunk_record(struct btrfs_root *root,
920 struct chunk_record *chunk)
921 {
922 int ret = 0;
923 int i;
924 u64 devid;
925 u8 uuid[BTRFS_UUID_SIZE];
926 u16 num_stripes;
927 struct btrfs_fs_info *fs_info = root->fs_info;
928 struct btrfs_mapping_tree *map_tree;
929 struct map_lookup *map;
930 struct stripe *stripe;
931
932 map_tree = &fs_info->mapping_tree;
933 num_stripes = chunk->num_stripes;
934 map = malloc(btrfs_map_lookup_size(num_stripes));
935 if (!map)
936 return -ENOMEM;
937 map->ce.start = chunk->offset;
938 map->ce.size = chunk->length;
939 map->num_stripes = num_stripes;
940 map->io_width = chunk->io_width;
941 map->io_align = chunk->io_align;
942 map->sector_size = chunk->sector_size;
943 map->stripe_len = chunk->stripe_len;
944 map->type = chunk->type_flags;
945 map->sub_stripes = chunk->sub_stripes;
946
947 for (i = 0, stripe = chunk->stripes; i < num_stripes; i++, stripe++) {
948 devid = stripe->devid;
949 memcpy(uuid, stripe->dev_uuid, BTRFS_UUID_SIZE);
950 map->stripes[i].physical = stripe->offset;
951 map->stripes[i].dev = btrfs_find_device(fs_info, devid,
952 uuid, NULL);
953 if (!map->stripes[i].dev) {
954 free(map);
955 return -EIO;
956 }
957 }
958
959 ret = insert_cache_extent(&map_tree->cache_tree, &map->ce);
960 return ret;
961 }
962
963 static int build_device_maps_by_chunk_records(struct recover_control *rc,
964 struct btrfs_root *root)
965 {
966 int ret = 0;
967 struct chunk_record *chunk;
968
969 list_for_each_entry(chunk, &rc->good_chunks, list) {
970 ret = build_device_map_by_chunk_record(root, chunk);
971 if (ret)
972 return ret;
973 }
974 list_for_each_entry(chunk, &rc->rebuild_chunks, list) {
975 ret = build_device_map_by_chunk_record(root, chunk);
976 if (ret)
977 return ret;
978 }
979 return ret;
980 }
981
982 static int block_group_remove_all_extent_items(struct btrfs_trans_handle *trans,
983 struct btrfs_root *root,
984 struct block_group_record *bg)
985 {
986 struct btrfs_fs_info *fs_info = root->fs_info;
987 struct btrfs_key key;
988 struct btrfs_path path;
989 struct extent_buffer *leaf;
990 u64 start = bg->objectid;
991 u64 end = bg->objectid + bg->offset;
992 u64 old_val;
993 int nitems;
994 int ret;
995 int i;
996 int del_s, del_nr;
997
998 btrfs_init_path(&path);
999 root = root->fs_info->extent_root;
1000
1001 key.objectid = start;
1002 key.offset = 0;
1003 key.type = BTRFS_EXTENT_ITEM_KEY;
1004 again:
1005 ret = btrfs_search_slot(trans, root, &key, &path, -1, 1);
1006 if (ret < 0)
1007 goto err;
1008 else if (ret > 0)
1009 ret = 0;
1010
1011 leaf = path.nodes[0];
1012 nitems = btrfs_header_nritems(leaf);
1013 if (!nitems) {
1014 /* The tree is empty. */
1015 ret = 0;
1016 goto err;
1017 }
1018
1019 if (path.slots[0] >= nitems) {
1020 ret = btrfs_next_leaf(root, &path);
1021 if (ret < 0)
1022 goto err;
1023 if (ret > 0) {
1024 ret = 0;
1025 goto err;
1026 }
1027 leaf = path.nodes[0];
1028 btrfs_item_key_to_cpu(leaf, &key, 0);
1029 if (key.objectid >= end)
1030 goto err;
1031 btrfs_release_path(&path);
1032 goto again;
1033 }
1034
1035 del_nr = 0;
1036 del_s = -1;
1037 for (i = path.slots[0]; i < nitems; i++) {
1038 btrfs_item_key_to_cpu(leaf, &key, i);
1039 if (key.objectid >= end)
1040 break;
1041
1042 if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
1043 if (del_nr == 0)
1044 continue;
1045 else
1046 break;
1047 }
1048
1049 if (del_s == -1)
1050 del_s = i;
1051 del_nr++;
1052 if (key.type == BTRFS_EXTENT_ITEM_KEY ||
1053 key.type == BTRFS_METADATA_ITEM_KEY) {
1054 old_val = btrfs_super_bytes_used(fs_info->super_copy);
1055 if (key.type == BTRFS_METADATA_ITEM_KEY)
1056 old_val += fs_info->nodesize;
1057 else
1058 old_val += key.offset;
1059 btrfs_set_super_bytes_used(fs_info->super_copy,
1060 old_val);
1061 }
1062 }
1063
1064 if (del_nr) {
1065 ret = btrfs_del_items(trans, root, &path, del_s, del_nr);
1066 if (ret)
1067 goto err;
1068 }
1069
1070 if (key.objectid < end) {
1071 if (key.type == BTRFS_BLOCK_GROUP_ITEM_KEY) {
1072 key.objectid += fs_info->sectorsize;
1073 key.type = BTRFS_EXTENT_ITEM_KEY;
1074 key.offset = 0;
1075 }
1076 btrfs_release_path(&path);
1077 goto again;
1078 }
1079 err:
1080 btrfs_release_path(&path);
1081 return ret;
1082 }
1083
1084 static int block_group_free_all_extent(struct btrfs_root *root,
1085 struct block_group_record *bg)
1086 {
1087 struct btrfs_block_group_cache *cache;
1088 struct btrfs_fs_info *info;
1089 u64 start;
1090 u64 end;
1091
1092 info = root->fs_info;
1093 cache = btrfs_lookup_block_group(info, bg->objectid);
1094 if (!cache)
1095 return -ENOENT;
1096
1097 start = cache->key.objectid;
1098 end = start + cache->key.offset - 1;
1099
1100 set_extent_bits(&info->block_group_cache, start, end,
1101 BLOCK_GROUP_DIRTY);
1102 set_extent_dirty(&info->free_space_cache, start, end);
1103
1104 btrfs_set_block_group_used(&cache->item, 0);
1105
1106 return 0;
1107 }
1108
1109 static int remove_chunk_extent_item(struct btrfs_trans_handle *trans,
1110 struct recover_control *rc,
1111 struct btrfs_root *root)
1112 {
1113 struct chunk_record *chunk;
1114 int ret = 0;
1115
1116 list_for_each_entry(chunk, &rc->good_chunks, list) {
1117 if (!(chunk->type_flags & BTRFS_BLOCK_GROUP_SYSTEM))
1118 continue;
1119 ret = block_group_remove_all_extent_items(trans, root,
1120 chunk->bg_rec);
1121 if (ret)
1122 return ret;
1123
1124 ret = block_group_free_all_extent(root, chunk->bg_rec);
1125 if (ret)
1126 return ret;
1127 }
1128 return ret;
1129 }
1130
1131 static int __rebuild_chunk_root(struct btrfs_trans_handle *trans,
1132 struct recover_control *rc,
1133 struct btrfs_root *root)
1134 {
1135 u64 min_devid = -1;
1136 struct btrfs_device *dev;
1137 struct extent_buffer *cow;
1138 struct btrfs_disk_key disk_key;
1139 int ret = 0;
1140
1141 list_for_each_entry(dev, &rc->fs_devices->devices, dev_list) {
1142 if (min_devid > dev->devid)
1143 min_devid = dev->devid;
1144 }
1145 btrfs_set_disk_key_objectid(&disk_key, BTRFS_DEV_ITEMS_OBJECTID);
1146 btrfs_set_disk_key_type(&disk_key, BTRFS_DEV_ITEM_KEY);
1147 btrfs_set_disk_key_offset(&disk_key, min_devid);
1148
1149 cow = btrfs_alloc_free_block(trans, root, root->fs_info->nodesize,
1150 BTRFS_CHUNK_TREE_OBJECTID,
1151 &disk_key, 0, 0, 0);
1152 btrfs_set_header_bytenr(cow, cow->start);
1153 btrfs_set_header_generation(cow, trans->transid);
1154 btrfs_set_header_nritems(cow, 0);
1155 btrfs_set_header_level(cow, 0);
1156 btrfs_set_header_backref_rev(cow, BTRFS_MIXED_BACKREF_REV);
1157 btrfs_set_header_owner(cow, BTRFS_CHUNK_TREE_OBJECTID);
1158 write_extent_buffer(cow, root->fs_info->fsid,
1159 btrfs_header_fsid(), BTRFS_FSID_SIZE);
1160
1161 write_extent_buffer(cow, root->fs_info->chunk_tree_uuid,
1162 btrfs_header_chunk_tree_uuid(cow),
1163 BTRFS_UUID_SIZE);
1164
1165 root->node = cow;
1166 btrfs_mark_buffer_dirty(cow);
1167
1168 return ret;
1169 }
1170
1171 static int __rebuild_device_items(struct btrfs_trans_handle *trans,
1172 struct recover_control *rc,
1173 struct btrfs_root *root)
1174 {
1175 struct btrfs_device *dev;
1176 struct btrfs_key key;
1177 struct btrfs_dev_item dev_item_tmp;
1178 struct btrfs_dev_item *dev_item = &dev_item_tmp;
1179 int ret = 0;
1180
1181 list_for_each_entry(dev, &rc->fs_devices->devices, dev_list) {
1182 key.objectid = BTRFS_DEV_ITEMS_OBJECTID;
1183 key.type = BTRFS_DEV_ITEM_KEY;
1184 key.offset = dev->devid;
1185
1186 btrfs_set_stack_device_generation(dev_item, 0);
1187 btrfs_set_stack_device_type(dev_item, dev->type);
1188 btrfs_set_stack_device_id(dev_item, dev->devid);
1189 btrfs_set_stack_device_total_bytes(dev_item, dev->total_bytes);
1190 btrfs_set_stack_device_bytes_used(dev_item, dev->bytes_used);
1191 btrfs_set_stack_device_io_align(dev_item, dev->io_align);
1192 btrfs_set_stack_device_io_width(dev_item, dev->io_width);
1193 btrfs_set_stack_device_sector_size(dev_item, dev->sector_size);
1194 memcpy(dev_item->uuid, dev->uuid, BTRFS_UUID_SIZE);
1195 memcpy(dev_item->fsid, dev->fs_devices->fsid, BTRFS_UUID_SIZE);
1196
1197 ret = btrfs_insert_item(trans, root, &key,
1198 dev_item, sizeof(*dev_item));
1199 }
1200
1201 return ret;
1202 }
1203
1204 static int __insert_chunk_item(struct btrfs_trans_handle *trans,
1205 struct chunk_record *chunk_rec,
1206 struct btrfs_root *chunk_root)
1207 {
1208 struct btrfs_key key;
1209 struct btrfs_chunk *chunk = NULL;
1210 int ret = 0;
1211
1212 chunk = create_chunk_item(chunk_rec);
1213 if (!chunk)
1214 return -ENOMEM;
1215 key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
1216 key.type = BTRFS_CHUNK_ITEM_KEY;
1217 key.offset = chunk_rec->offset;
1218
1219 ret = btrfs_insert_item(trans, chunk_root, &key, chunk,
1220 btrfs_chunk_item_size(chunk_rec->num_stripes));
1221 free(chunk);
1222 return ret;
1223 }
1224
1225 static int __rebuild_chunk_items(struct btrfs_trans_handle *trans,
1226 struct recover_control *rc,
1227 struct btrfs_root *root)
1228 {
1229 struct btrfs_root *chunk_root;
1230 struct chunk_record *chunk_rec;
1231 int ret;
1232
1233 chunk_root = root->fs_info->chunk_root;
1234
1235 list_for_each_entry(chunk_rec, &rc->good_chunks, list) {
1236 ret = __insert_chunk_item(trans, chunk_rec, chunk_root);
1237 if (ret)
1238 return ret;
1239 }
1240 list_for_each_entry(chunk_rec, &rc->rebuild_chunks, list) {
1241 ret = __insert_chunk_item(trans, chunk_rec, chunk_root);
1242 if (ret)
1243 return ret;
1244 }
1245 return 0;
1246 }
1247
1248 static int rebuild_chunk_tree(struct btrfs_trans_handle *trans,
1249 struct recover_control *rc,
1250 struct btrfs_root *root)
1251 {
1252 int ret = 0;
1253
1254 root = root->fs_info->chunk_root;
1255
1256 ret = __rebuild_chunk_root(trans, rc, root);
1257 if (ret)
1258 return ret;
1259
1260 ret = __rebuild_device_items(trans, rc, root);
1261 if (ret)
1262 return ret;
1263
1264 ret = __rebuild_chunk_items(trans, rc, root);
1265
1266 return ret;
1267 }
1268
1269 static int rebuild_sys_array(struct recover_control *rc,
1270 struct btrfs_root *root)
1271 {
1272 struct btrfs_fs_info *fs_info = root->fs_info;
1273 struct btrfs_chunk *chunk;
1274 struct btrfs_key key;
1275 struct chunk_record *chunk_rec;
1276 int ret = 0;
1277 u16 num_stripes;
1278
1279 btrfs_set_super_sys_array_size(fs_info->super_copy, 0);
1280
1281 list_for_each_entry(chunk_rec, &rc->good_chunks, list) {
1282 if (!(chunk_rec->type_flags & BTRFS_BLOCK_GROUP_SYSTEM))
1283 continue;
1284
1285 num_stripes = chunk_rec->num_stripes;
1286 chunk = create_chunk_item(chunk_rec);
1287 if (!chunk) {
1288 ret = -ENOMEM;
1289 break;
1290 }
1291
1292 key.objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
1293 key.type = BTRFS_CHUNK_ITEM_KEY;
1294 key.offset = chunk_rec->offset;
1295
1296 ret = btrfs_add_system_chunk(fs_info, &key, chunk,
1297 btrfs_chunk_item_size(num_stripes));
1298 free(chunk);
1299 if (ret)
1300 break;
1301 }
1302 return ret;
1303
1304 }
1305
1306 static int calculate_bg_used(struct btrfs_root *extent_root,
1307 struct chunk_record *chunk_rec,
1308 struct btrfs_path *path,
1309 u64 *used)
1310 {
1311 struct extent_buffer *node;
1312 struct btrfs_key found_key;
1313 int slot;
1314 int ret = 0;
1315 u64 used_ret = 0;
1316
1317 while (1) {
1318 node = path->nodes[0];
1319 slot = path->slots[0];
1320 btrfs_item_key_to_cpu(node, &found_key, slot);
1321 if (found_key.objectid >= chunk_rec->offset + chunk_rec->length)
1322 break;
1323 if (found_key.type != BTRFS_METADATA_ITEM_KEY &&
1324 found_key.type != BTRFS_EXTENT_DATA_KEY)
1325 goto next;
1326 if (found_key.type == BTRFS_METADATA_ITEM_KEY)
1327 used_ret += extent_root->fs_info->nodesize;
1328 else
1329 used_ret += found_key.offset;
1330 next:
1331 if (slot + 1 < btrfs_header_nritems(node)) {
1332 slot++;
1333 } else {
1334 ret = btrfs_next_leaf(extent_root, path);
1335 if (ret > 0) {
1336 ret = 0;
1337 break;
1338 }
1339 if (ret < 0)
1340 break;
1341 }
1342 }
1343 if (!ret)
1344 *used = used_ret;
1345 return ret;
1346 }
1347
1348 static int __insert_block_group(struct btrfs_trans_handle *trans,
1349 struct chunk_record *chunk_rec,
1350 struct btrfs_root *extent_root,
1351 u64 used)
1352 {
1353 struct btrfs_block_group_item bg_item;
1354 struct btrfs_key key;
1355 int ret = 0;
1356
1357 btrfs_set_block_group_used(&bg_item, used);
1358 btrfs_set_block_group_chunk_objectid(&bg_item, used);
1359 btrfs_set_block_group_flags(&bg_item, chunk_rec->type_flags);
1360 key.objectid = chunk_rec->offset;
1361 key.type = BTRFS_BLOCK_GROUP_ITEM_KEY;
1362 key.offset = chunk_rec->length;
1363
1364 ret = btrfs_insert_item(trans, extent_root, &key, &bg_item,
1365 sizeof(bg_item));
1366 return ret;
1367 }
1368
1369 /*
1370 * Search through the extent tree to rebuild the 'used' member of the block
1371 * group.
1372 * However, since block group and extent item shares the extent tree,
1373 * the extent item may also missing.
1374 * In that case, we fill the 'used' with the length of the block group to
1375 * ensure no write into the block group.
1376 * Btrfsck will hate it but we will inform user to call '--init-extent-tree'
1377 * if possible, or just salvage as much data as possible from the fs.
1378 */
1379 static int rebuild_block_group(struct btrfs_trans_handle *trans,
1380 struct recover_control *rc,
1381 struct btrfs_root *root)
1382 {
1383 struct chunk_record *chunk_rec;
1384 struct btrfs_key search_key;
1385 struct btrfs_path path;
1386 u64 used = 0;
1387 int ret = 0;
1388
1389 if (list_empty(&rc->rebuild_chunks))
1390 return 0;
1391
1392 btrfs_init_path(&path);
1393 list_for_each_entry(chunk_rec, &rc->rebuild_chunks, list) {
1394 search_key.objectid = chunk_rec->offset;
1395 search_key.type = BTRFS_EXTENT_ITEM_KEY;
1396 search_key.offset = 0;
1397 ret = btrfs_search_slot(NULL, root->fs_info->extent_root,
1398 &search_key, &path, 0, 0);
1399 if (ret < 0)
1400 goto out;
1401 ret = calculate_bg_used(root->fs_info->extent_root,
1402 chunk_rec, &path, &used);
1403 /*
1404 * Extent tree is damaged, better to rebuild the whole extent
1405 * tree. Currently, change the used to chunk's len to prevent
1406 * write/block reserve happening in that block group.
1407 */
1408 if (ret < 0) {
1409 fprintf(stderr,
1410 "Fail to search extent tree for block group: [%llu,%llu]\n",
1411 chunk_rec->offset,
1412 chunk_rec->offset + chunk_rec->length);
1413 fprintf(stderr,
1414 "Mark the block group full to prevent block rsv problems\n");
1415 used = chunk_rec->length;
1416 }
1417 btrfs_release_path(&path);
1418 ret = __insert_block_group(trans, chunk_rec,
1419 root->fs_info->extent_root,
1420 used);
1421 if (ret < 0)
1422 goto out;
1423 }
1424 out:
1425 btrfs_release_path(&path);
1426 return ret;
1427 }
1428
1429 static struct btrfs_root *
1430 open_ctree_with_broken_chunk(struct recover_control *rc)
1431 {
1432 struct btrfs_fs_info *fs_info;
1433 struct btrfs_super_block *disk_super;
1434 struct extent_buffer *eb;
1435 int ret;
1436
1437 fs_info = btrfs_new_fs_info(1, BTRFS_SUPER_INFO_OFFSET);
1438 if (!fs_info) {
1439 fprintf(stderr, "Failed to allocate memory for fs_info\n");
1440 return ERR_PTR(-ENOMEM);
1441 }
1442 fs_info->is_chunk_recover = 1;
1443
1444 fs_info->fs_devices = rc->fs_devices;
1445 ret = btrfs_open_devices(fs_info->fs_devices, O_RDWR);
1446 if (ret)
1447 goto out;
1448
1449 disk_super = fs_info->super_copy;
1450 ret = btrfs_read_dev_super(fs_info->fs_devices->latest_bdev,
1451 disk_super, fs_info->super_bytenr,
1452 SBREAD_RECOVER);
1453 if (ret) {
1454 fprintf(stderr, "No valid btrfs found\n");
1455 goto out_devices;
1456 }
1457
1458 memcpy(fs_info->fsid, &disk_super->fsid, BTRFS_FSID_SIZE);
1459 fs_info->sectorsize = btrfs_super_sectorsize(disk_super);
1460 fs_info->nodesize = btrfs_super_nodesize(disk_super);
1461 fs_info->stripesize = btrfs_super_stripesize(disk_super);
1462
1463 ret = btrfs_check_fs_compatibility(disk_super, OPEN_CTREE_WRITES);
1464 if (ret)
1465 goto out_devices;
1466
1467 btrfs_setup_root(fs_info->chunk_root, fs_info,
1468 BTRFS_CHUNK_TREE_OBJECTID);
1469
1470 ret = build_device_maps_by_chunk_records(rc, fs_info->chunk_root);
1471 if (ret)
1472 goto out_cleanup;
1473
1474 ret = btrfs_setup_all_roots(fs_info, 0, 0);
1475 if (ret)
1476 goto out_failed;
1477
1478 eb = fs_info->tree_root->node;
1479 read_extent_buffer(eb, fs_info->chunk_tree_uuid,
1480 btrfs_header_chunk_tree_uuid(eb),
1481 BTRFS_UUID_SIZE);
1482
1483 return fs_info->fs_root;
1484 out_failed:
1485 btrfs_release_all_roots(fs_info);
1486 out_cleanup:
1487 btrfs_cleanup_all_caches(fs_info);
1488 out_devices:
1489 btrfs_close_devices(fs_info->fs_devices);
1490 out:
1491 btrfs_free_fs_info(fs_info);
1492 return ERR_PTR(ret);
1493 }
1494
1495 static int recover_prepare(struct recover_control *rc, const char *path)
1496 {
1497 int ret;
1498 int fd;
1499 struct btrfs_super_block *sb;
1500 char buf[BTRFS_SUPER_INFO_SIZE];
1501 struct btrfs_fs_devices *fs_devices;
1502
1503 ret = 0;
1504 fd = open(path, O_RDONLY);
1505 if (fd < 0) {
1506 fprintf(stderr, "open %s\n error.\n", path);
1507 return -1;
1508 }
1509
1510 sb = (struct btrfs_super_block*)buf;
1511 ret = btrfs_read_dev_super(fd, sb, BTRFS_SUPER_INFO_OFFSET,
1512 SBREAD_RECOVER);
1513 if (ret) {
1514 fprintf(stderr, "read super block error\n");
1515 goto out_close_fd;
1516 }
1517
1518 rc->sectorsize = btrfs_super_sectorsize(sb);
1519 rc->nodesize = btrfs_super_nodesize(sb);
1520 rc->generation = btrfs_super_generation(sb);
1521 rc->chunk_root_generation = btrfs_super_chunk_root_generation(sb);
1522 rc->csum_size = btrfs_super_csum_size(sb);
1523
1524 /* if seed, the result of scanning below will be partial */
1525 if (btrfs_super_flags(sb) & BTRFS_SUPER_FLAG_SEEDING) {
1526 fprintf(stderr, "this device is seed device\n");
1527 ret = -1;
1528 goto out_close_fd;
1529 }
1530
1531 ret = btrfs_scan_fs_devices(fd, path, &fs_devices, 0, SBREAD_RECOVER, 0);
1532 if (ret)
1533 goto out_close_fd;
1534
1535 rc->fs_devices = fs_devices;
1536
1537 if (rc->verbose)
1538 print_all_devices(&rc->fs_devices->devices);
1539
1540 out_close_fd:
1541 close(fd);
1542 return ret;
1543 }
1544
1545 static int btrfs_get_device_extents(u64 chunk_object,
1546 struct list_head *orphan_devexts,
1547 struct list_head *ret_list)
1548 {
1549 struct device_extent_record *devext;
1550 struct device_extent_record *next;
1551 int count = 0;
1552
1553 list_for_each_entry_safe(devext, next, orphan_devexts, chunk_list) {
1554 if (devext->chunk_offset == chunk_object) {
1555 list_move_tail(&devext->chunk_list, ret_list);
1556 count++;
1557 }
1558 }
1559 return count;
1560 }
1561
1562 static int calc_num_stripes(u64 type)
1563 {
1564 if (type & (BTRFS_BLOCK_GROUP_RAID0 |
1565 BTRFS_BLOCK_GROUP_RAID10 |
1566 BTRFS_BLOCK_GROUP_RAID5 |
1567 BTRFS_BLOCK_GROUP_RAID6))
1568 return 0;
1569 else if (type & (BTRFS_BLOCK_GROUP_RAID1 |
1570 BTRFS_BLOCK_GROUP_DUP))
1571 return 2;
1572 else
1573 return 1;
1574 }
1575
1576 static inline int calc_sub_nstripes(u64 type)
1577 {
1578 if (type & BTRFS_BLOCK_GROUP_RAID10)
1579 return 2;
1580 else
1581 return 1;
1582 }
1583
1584 static int btrfs_verify_device_extents(struct block_group_record *bg,
1585 struct list_head *devexts, int ndevexts)
1586 {
1587 struct device_extent_record *devext;
1588 u64 stripe_length;
1589 int expected_num_stripes;
1590
1591 expected_num_stripes = calc_num_stripes(bg->flags);
1592 if (expected_num_stripes && expected_num_stripes != ndevexts)
1593 return 1;
1594
1595 if (check_num_stripes(bg->flags, ndevexts) < 0)
1596 return 1;
1597
1598 stripe_length = calc_stripe_length(bg->flags, bg->offset, ndevexts);
1599 list_for_each_entry(devext, devexts, chunk_list) {
1600 if (devext->length != stripe_length)
1601 return 1;
1602 }
1603 return 0;
1604 }
1605
1606 static int btrfs_rebuild_unordered_chunk_stripes(struct recover_control *rc,
1607 struct chunk_record *chunk)
1608 {
1609 struct device_extent_record *devext;
1610 struct btrfs_device *device;
1611 int i;
1612
1613 devext = list_first_entry(&chunk->dextents, struct device_extent_record,
1614 chunk_list);
1615 for (i = 0; i < chunk->num_stripes; i++) {
1616 chunk->stripes[i].devid = devext->objectid;
1617 chunk->stripes[i].offset = devext->offset;
1618 device = btrfs_find_device_by_devid(rc->fs_devices,
1619 devext->objectid,
1620 0);
1621 if (!device)
1622 return -ENOENT;
1623 BUG_ON(btrfs_find_device_by_devid(rc->fs_devices,
1624 devext->objectid,
1625 1));
1626 memcpy(chunk->stripes[i].dev_uuid, device->uuid,
1627 BTRFS_UUID_SIZE);
1628 devext = list_next_entry(devext, chunk_list);
1629 }
1630 return 0;
1631 }
1632
1633 static int btrfs_calc_stripe_index(struct chunk_record *chunk, u64 logical)
1634 {
1635 u64 offset = logical - chunk->offset;
1636 int stripe_nr;
1637 int nr_data_stripes;
1638 int index;
1639
1640 stripe_nr = offset / chunk->stripe_len;
1641 if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID0) {
1642 index = stripe_nr % chunk->num_stripes;
1643 } else if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID10) {
1644 index = stripe_nr % (chunk->num_stripes / chunk->sub_stripes);
1645 index *= chunk->sub_stripes;
1646 } else if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID5) {
1647 nr_data_stripes = chunk->num_stripes - 1;
1648 index = stripe_nr % nr_data_stripes;
1649 stripe_nr /= nr_data_stripes;
1650 index = (index + stripe_nr) % chunk->num_stripes;
1651 } else if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID6) {
1652 nr_data_stripes = chunk->num_stripes - 2;
1653 index = stripe_nr % nr_data_stripes;
1654 stripe_nr /= nr_data_stripes;
1655 index = (index + stripe_nr) % chunk->num_stripes;
1656 } else {
1657 return -1;
1658 }
1659 return index;
1660 }
1661
1662 /* calc the logical offset which is the start of the next stripe. */
1663 static inline u64 btrfs_next_stripe_logical_offset(struct chunk_record *chunk,
1664 u64 logical)
1665 {
1666 u64 offset = logical - chunk->offset;
1667
1668 offset /= chunk->stripe_len;
1669 offset *= chunk->stripe_len;
1670 offset += chunk->stripe_len;
1671
1672 return offset + chunk->offset;
1673 }
1674
1675 static int is_extent_record_in_device_extent(struct extent_record *er,
1676 struct device_extent_record *dext,
1677 int *mirror)
1678 {
1679 int i;
1680
1681 for (i = 0; i < er->nmirrors; i++) {
1682 if (er->devices[i]->devid == dext->objectid &&
1683 er->offsets[i] >= dext->offset &&
1684 er->offsets[i] < dext->offset + dext->length) {
1685 *mirror = i;
1686 return 1;
1687 }
1688 }
1689 return 0;
1690 }
1691
1692 static int
1693 btrfs_rebuild_ordered_meta_chunk_stripes(struct recover_control *rc,
1694 struct chunk_record *chunk)
1695 {
1696 u64 start = chunk->offset;
1697 u64 end = chunk->offset + chunk->length;
1698 struct cache_extent *cache;
1699 struct extent_record *er;
1700 struct device_extent_record *devext;
1701 struct device_extent_record *next;
1702 struct btrfs_device *device;
1703 LIST_HEAD(devexts);
1704 int index;
1705 int mirror;
1706 int ret;
1707
1708 cache = lookup_cache_extent(&rc->eb_cache,
1709 start, chunk->length);
1710 if (!cache) {
1711 /* No used space, we can reorder the stripes freely. */
1712 ret = btrfs_rebuild_unordered_chunk_stripes(rc, chunk);
1713 return ret;
1714 }
1715
1716 list_splice_init(&chunk->dextents, &devexts);
1717 again:
1718 er = container_of(cache, struct extent_record, cache);
1719 index = btrfs_calc_stripe_index(chunk, er->cache.start);
1720 BUG_ON(index == -1);
1721 if (chunk->stripes[index].devid)
1722 goto next;
1723 list_for_each_entry_safe(devext, next, &devexts, chunk_list) {
1724 if (is_extent_record_in_device_extent(er, devext, &mirror)) {
1725 chunk->stripes[index].devid = devext->objectid;
1726 chunk->stripes[index].offset = devext->offset;
1727 memcpy(chunk->stripes[index].dev_uuid,
1728 er->devices[mirror]->uuid,
1729 BTRFS_UUID_SIZE);
1730 index++;
1731 list_move(&devext->chunk_list, &chunk->dextents);
1732 }
1733 }
1734 next:
1735 start = btrfs_next_stripe_logical_offset(chunk, er->cache.start);
1736 if (start >= end)
1737 goto no_extent_record;
1738
1739 cache = lookup_cache_extent(&rc->eb_cache, start, end - start);
1740 if (cache)
1741 goto again;
1742 no_extent_record:
1743 if (list_empty(&devexts))
1744 return 0;
1745
1746 if (chunk->type_flags & (BTRFS_BLOCK_GROUP_RAID5 |
1747 BTRFS_BLOCK_GROUP_RAID6)) {
1748 /* Fixme: try to recover the order by the parity block. */
1749 list_splice_tail(&devexts, &chunk->dextents);
1750 return -EINVAL;
1751 }
1752
1753 /* There is no data on the lost stripes, we can reorder them freely. */
1754 for (index = 0; index < chunk->num_stripes; index++) {
1755 if (chunk->stripes[index].devid)
1756 continue;
1757
1758 devext = list_first_entry(&devexts,
1759 struct device_extent_record,
1760 chunk_list);
1761 list_move(&devext->chunk_list, &chunk->dextents);
1762
1763 chunk->stripes[index].devid = devext->objectid;
1764 chunk->stripes[index].offset = devext->offset;
1765 device = btrfs_find_device_by_devid(rc->fs_devices,
1766 devext->objectid,
1767 0);
1768 if (!device) {
1769 list_splice_tail(&devexts, &chunk->dextents);
1770 return -EINVAL;
1771 }
1772 BUG_ON(btrfs_find_device_by_devid(rc->fs_devices,
1773 devext->objectid,
1774 1));
1775 memcpy(chunk->stripes[index].dev_uuid, device->uuid,
1776 BTRFS_UUID_SIZE);
1777 }
1778 return 0;
1779 }
1780
1781 #define BTRFS_ORDERED_RAID (BTRFS_BLOCK_GROUP_RAID0 | \
1782 BTRFS_BLOCK_GROUP_RAID10 | \
1783 BTRFS_BLOCK_GROUP_RAID5 | \
1784 BTRFS_BLOCK_GROUP_RAID6)
1785
1786 static int btrfs_rebuild_chunk_stripes(struct recover_control *rc,
1787 struct chunk_record *chunk)
1788 {
1789 int ret;
1790
1791 /*
1792 * All the data in the system metadata chunk will be dropped,
1793 * so we need not guarantee that the data is right or not, that
1794 * is we can reorder the stripes in the system metadata chunk.
1795 */
1796 if ((chunk->type_flags & BTRFS_BLOCK_GROUP_METADATA) &&
1797 (chunk->type_flags & BTRFS_ORDERED_RAID))
1798 ret =btrfs_rebuild_ordered_meta_chunk_stripes(rc, chunk);
1799 else if ((chunk->type_flags & BTRFS_BLOCK_GROUP_DATA) &&
1800 (chunk->type_flags & BTRFS_ORDERED_RAID))
1801 ret = 1; /* Be handled after the fs is opened. */
1802 else
1803 ret = btrfs_rebuild_unordered_chunk_stripes(rc, chunk);
1804
1805 return ret;
1806 }
1807
1808 static int next_csum(struct btrfs_root *root,
1809 struct extent_buffer **leaf,
1810 struct btrfs_path *path,
1811 int *slot,
1812 u64 *csum_offset,
1813 u32 *tree_csum,
1814 u64 end,
1815 struct btrfs_key *key)
1816 {
1817 int ret = 0;
1818 struct btrfs_root *csum_root = root->fs_info->csum_root;
1819 struct btrfs_csum_item *csum_item;
1820 u32 blocksize = root->fs_info->sectorsize;
1821 u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
1822 int csums_in_item = btrfs_item_size_nr(*leaf, *slot) / csum_size;
1823
1824 if (*csum_offset >= csums_in_item) {
1825 ++(*slot);
1826 *csum_offset = 0;
1827 if (*slot >= btrfs_header_nritems(*leaf)) {
1828 ret = btrfs_next_leaf(csum_root, path);
1829 if (ret < 0)
1830 return -1;
1831 else if (ret > 0)
1832 return 1;
1833 *leaf = path->nodes[0];
1834 *slot = path->slots[0];
1835 }
1836 btrfs_item_key_to_cpu(*leaf, key, *slot);
1837 }
1838
1839 if (key->offset + (*csum_offset) * blocksize >= end)
1840 return 2;
1841 csum_item = btrfs_item_ptr(*leaf, *slot, struct btrfs_csum_item);
1842 csum_item = (struct btrfs_csum_item *)((unsigned char *)csum_item
1843 + (*csum_offset) * csum_size);
1844 read_extent_buffer(*leaf, tree_csum,
1845 (unsigned long)csum_item, csum_size);
1846 return ret;
1847 }
1848
1849 static u64 calc_data_offset(struct btrfs_key *key,
1850 struct chunk_record *chunk,
1851 u64 dev_offset,
1852 u64 csum_offset,
1853 u32 blocksize)
1854 {
1855 u64 data_offset;
1856 int logical_stripe_nr;
1857 int dev_stripe_nr;
1858 int nr_data_stripes;
1859
1860 data_offset = key->offset + csum_offset * blocksize - chunk->offset;
1861 nr_data_stripes = chunk->num_stripes;
1862
1863 if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID5)
1864 nr_data_stripes -= 1;
1865 else if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID6)
1866 nr_data_stripes -= 2;
1867
1868 logical_stripe_nr = data_offset / chunk->stripe_len;
1869 dev_stripe_nr = logical_stripe_nr / nr_data_stripes;
1870
1871 data_offset -= logical_stripe_nr * chunk->stripe_len;
1872 data_offset += dev_stripe_nr * chunk->stripe_len;
1873
1874 return dev_offset + data_offset;
1875 }
1876
1877 static int check_one_csum(int fd, u64 start, u32 len, u32 tree_csum)
1878 {
1879 char *data;
1880 int ret = 0;
1881 u32 csum_result = ~(u32)0;
1882
1883 data = malloc(len);
1884 if (!data)
1885 return -1;
1886 ret = pread64(fd, data, len, start);
1887 if (ret < 0 || ret != len) {
1888 ret = -1;
1889 goto out;
1890 }
1891 ret = 0;
1892 csum_result = btrfs_csum_data(data, csum_result, len);
1893 btrfs_csum_final(csum_result, (u8 *)&csum_result);
1894 if (csum_result != tree_csum)
1895 ret = 1;
1896 out:
1897 free(data);
1898 return ret;
1899 }
1900
1901 static u64 item_end_offset(struct btrfs_root *root, struct btrfs_key *key,
1902 struct extent_buffer *leaf, int slot) {
1903 u32 blocksize = root->fs_info->sectorsize;
1904 u16 csum_size = btrfs_super_csum_size(root->fs_info->super_copy);
1905
1906 u64 offset = btrfs_item_size_nr(leaf, slot);
1907 offset /= csum_size;
1908 offset *= blocksize;
1909 offset += key->offset;
1910
1911 return offset;
1912 }
1913
1914 static int insert_stripe(struct list_head *devexts,
1915 struct recover_control *rc,
1916 struct chunk_record *chunk,
1917 int index) {
1918 struct device_extent_record *devext;
1919 struct btrfs_device *dev;
1920
1921 devext = list_entry(devexts->next, struct device_extent_record,
1922 chunk_list);
1923 dev = btrfs_find_device_by_devid(rc->fs_devices, devext->objectid,
1924 0);
1925 if (!dev)
1926 return -ENOENT;
1927 if (btrfs_find_device_by_devid(rc->fs_devices, devext->objectid, 1)) {
1928 error("unexpected: found another device with id %llu",
1929 (unsigned long long)devext->objectid);
1930 return -EINVAL;
1931 }
1932
1933 chunk->stripes[index].devid = devext->objectid;
1934 chunk->stripes[index].offset = devext->offset;
1935 memcpy(chunk->stripes[index].dev_uuid, dev->uuid, BTRFS_UUID_SIZE);
1936
1937 list_move(&devext->chunk_list, &chunk->dextents);
1938
1939 return 0;
1940 }
1941
1942 static inline int count_devext_records(struct list_head *record_list)
1943 {
1944 int num_of_records = 0;
1945 struct device_extent_record *devext;
1946
1947 list_for_each_entry(devext, record_list, chunk_list)
1948 num_of_records++;
1949
1950 return num_of_records;
1951 }
1952
1953 static int fill_chunk_up(struct chunk_record *chunk, struct list_head *devexts,
1954 struct recover_control *rc)
1955 {
1956 int ret = 0;
1957 int i;
1958
1959 for (i = 0; i < chunk->num_stripes; i++) {
1960 if (!chunk->stripes[i].devid) {
1961 ret = insert_stripe(devexts, rc, chunk, i);
1962 if (ret)
1963 break;
1964 }
1965 }
1966
1967 return ret;
1968 }
1969
1970 #define EQUAL_STRIPE (1 << 0)
1971
1972 static int rebuild_raid_data_chunk_stripes(struct recover_control *rc,
1973 struct btrfs_root *root,
1974 struct chunk_record *chunk,
1975 u8 *flags)
1976 {
1977 int i;
1978 int ret = 0;
1979 int slot;
1980 struct btrfs_path path;
1981 struct btrfs_key prev_key;
1982 struct btrfs_key key;
1983 struct btrfs_root *csum_root;
1984 struct extent_buffer *leaf;
1985 struct device_extent_record *devext;
1986 struct device_extent_record *next;
1987 struct btrfs_device *dev;
1988 u64 start = chunk->offset;
1989 u64 end = start + chunk->stripe_len;
1990 u64 chunk_end = chunk->offset + chunk->length;
1991 u64 csum_offset = 0;
1992 u64 data_offset;
1993 u32 blocksize = root->fs_info->sectorsize;
1994 u32 tree_csum;
1995 int index = 0;
1996 int num_unordered = 0;
1997 LIST_HEAD(unordered);
1998 LIST_HEAD(candidates);
1999
2000 csum_root = root->fs_info->csum_root;
2001 btrfs_init_path(&path);
2002 list_splice_init(&chunk->dextents, &candidates);
2003 again:
2004 if (list_is_last(candidates.next, &candidates))
2005 goto out;
2006
2007 key.objectid = BTRFS_EXTENT_CSUM_OBJECTID;
2008 key.type = BTRFS_EXTENT_CSUM_KEY;
2009 key.offset = start;
2010
2011 ret = btrfs_search_slot(NULL, csum_root, &key, &path, 0, 0);
2012 if (ret < 0) {
2013 fprintf(stderr, "Search csum failed(%d)\n", ret);
2014 goto fail_out;
2015 }
2016 leaf = path.nodes[0];
2017 slot = path.slots[0];
2018 if (ret > 0) {
2019 if (slot >= btrfs_header_nritems(leaf)) {
2020 ret = btrfs_next_leaf(csum_root, &path);
2021 if (ret < 0) {
2022 fprintf(stderr,
2023 "Walk tree failed(%d)\n", ret);
2024 goto fail_out;
2025 } else if (ret > 0) {
2026 slot = btrfs_header_nritems(leaf) - 1;
2027 btrfs_item_key_to_cpu(leaf, &key, slot);
2028 if (item_end_offset(root, &key, leaf, slot)
2029 > start) {
2030 csum_offset = start - key.offset;
2031 csum_offset /= blocksize;
2032 goto next_csum;
2033 }
2034 goto next_stripe;
2035 }
2036 leaf = path.nodes[0];
2037 slot = path.slots[0];
2038 }
2039 btrfs_item_key_to_cpu(leaf, &key, slot);
2040 ret = btrfs_previous_item(csum_root, &path, 0,
2041 BTRFS_EXTENT_CSUM_KEY);
2042 if (ret < 0)
2043 goto fail_out;
2044 else if (ret > 0) {
2045 if (key.offset >= end)
2046 goto next_stripe;
2047 else
2048 goto next_csum;
2049 }
2050 leaf = path.nodes[0];
2051 slot = path.slots[0];
2052
2053 btrfs_item_key_to_cpu(leaf, &prev_key, slot);
2054 if (item_end_offset(root, &prev_key, leaf, slot) > start) {
2055 csum_offset = start - prev_key.offset;
2056 csum_offset /= blocksize;
2057 btrfs_item_key_to_cpu(leaf, &key, slot);
2058 } else {
2059 if (key.offset >= end)
2060 goto next_stripe;
2061 }
2062
2063 if (key.offset + csum_offset * blocksize > chunk_end)
2064 goto out;
2065 }
2066 next_csum:
2067 ret = next_csum(root, &leaf, &path, &slot, &csum_offset, &tree_csum,
2068 end, &key);
2069 if (ret < 0) {
2070 fprintf(stderr, "Fetch csum failed\n");
2071 goto fail_out;
2072 } else if (ret == 1) {
2073 if (!(*flags & EQUAL_STRIPE))
2074 *flags |= EQUAL_STRIPE;
2075 goto out;
2076 } else if (ret == 2)
2077 goto next_stripe;
2078
2079 list_for_each_entry_safe(devext, next, &candidates, chunk_list) {
2080 data_offset = calc_data_offset(&key, chunk, devext->offset,
2081 csum_offset, blocksize);
2082 dev = btrfs_find_device_by_devid(rc->fs_devices,
2083 devext->objectid, 0);
2084 if (!dev) {
2085 ret = 1;
2086 goto fail_out;
2087 }
2088 BUG_ON(btrfs_find_device_by_devid(rc->fs_devices,
2089 devext->objectid, 1));
2090
2091 ret = check_one_csum(dev->fd, data_offset, blocksize,
2092 tree_csum);
2093 if (ret < 0)
2094 goto fail_out;
2095 else if (ret > 0)
2096 list_move(&devext->chunk_list, &unordered);
2097 }
2098
2099 if (list_empty(&candidates)) {
2100 num_unordered = count_devext_records(&unordered);
2101 if (chunk->type_flags & BTRFS_BLOCK_GROUP_RAID6
2102 && num_unordered == 2) {
2103 btrfs_release_path(&path);
2104 ret = fill_chunk_up(chunk, &unordered, rc);
2105 return ret;
2106 }
2107
2108 goto next_stripe;
2109 }
2110
2111 if (list_is_last(candidates.next, &candidates)) {
2112 index = btrfs_calc_stripe_index(chunk,
2113 key.offset + csum_offset * blocksize);
2114 BUG_ON(index == -1);
2115 if (chunk->stripes[index].devid)
2116 goto next_stripe;
2117 ret = insert_stripe(&candidates, rc, chunk, index);
2118 if (ret)
2119 goto fail_out;
2120 } else {
2121 csum_offset++;
2122 goto next_csum;
2123 }
2124 next_stripe:
2125 start = btrfs_next_stripe_logical_offset(chunk, start);
2126 end = min(start + chunk->stripe_len, chunk_end);
2127 list_splice_init(&unordered, &candidates);
2128 btrfs_release_path(&path);
2129 csum_offset = 0;
2130 if (end < chunk_end)
2131 goto again;
2132 out:
2133 ret = 0;
2134 list_splice_init(&candidates, &unordered);
2135 num_unordered = count_devext_records(&unordered);
2136 if (num_unordered == 1) {
2137 for (i = 0; i < chunk->num_stripes; i++) {
2138 if (!chunk->stripes[i].devid) {
2139 index = i;
2140 break;
2141 }
2142 }
2143 ret = insert_stripe(&unordered, rc, chunk, index);
2144 if (ret)
2145 goto fail_out;
2146 } else {
2147 if ((num_unordered == 2 && chunk->type_flags
2148 & BTRFS_BLOCK_GROUP_RAID5)
2149 || (num_unordered == 3 && chunk->type_flags
2150 & BTRFS_BLOCK_GROUP_RAID6)) {
2151 ret = fill_chunk_up(chunk, &unordered, rc);
2152 }
2153 }
2154 fail_out:
2155 ret = !!ret || (list_empty(&unordered) ? 0 : 1);
2156 list_splice_init(&candidates, &chunk->dextents);
2157 list_splice_init(&unordered, &chunk->dextents);
2158 btrfs_release_path(&path);
2159
2160 return ret;
2161 }
2162
2163 static int btrfs_rebuild_ordered_data_chunk_stripes(struct recover_control *rc,
2164 struct btrfs_root *root)
2165 {
2166 struct chunk_record *chunk;
2167 struct chunk_record *next;
2168 int ret = 0;
2169 int err;
2170 u8 flags;
2171
2172 list_for_each_entry_safe(chunk, next, &rc->unrepaired_chunks, list) {
2173 if ((chunk->type_flags & BTRFS_BLOCK_GROUP_DATA)
2174 && (chunk->type_flags & BTRFS_ORDERED_RAID)) {
2175 flags = 0;
2176 err = rebuild_raid_data_chunk_stripes(rc, root, chunk,
2177 &flags);
2178 if (err) {
2179 list_move(&chunk->list, &rc->bad_chunks);
2180 if (flags & EQUAL_STRIPE)
2181 fprintf(stderr,
2182 "Failure: too many equal stripes in chunk[%llu %llu]\n",
2183 chunk->offset, chunk->length);
2184 if (!ret)
2185 ret = err;
2186 } else
2187 list_move(&chunk->list, &rc->good_chunks);
2188 }
2189 }
2190 return ret;
2191 }
2192
2193 static int btrfs_recover_chunks(struct recover_control *rc)
2194 {
2195 struct chunk_record *chunk;
2196 struct block_group_record *bg;
2197 struct block_group_record *next;
2198 LIST_HEAD(new_chunks);
2199 LIST_HEAD(devexts);
2200 int nstripes;
2201 int ret;
2202
2203 /* create the chunk by block group */
2204 list_for_each_entry_safe(bg, next, &rc->bg.block_groups, list) {
2205 nstripes = btrfs_get_device_extents(bg->objectid,
2206 &rc->devext.no_chunk_orphans,
2207 &devexts);
2208 chunk = calloc(1, btrfs_chunk_record_size(nstripes));
2209 if (!chunk)
2210 return -ENOMEM;
2211 INIT_LIST_HEAD(&chunk->dextents);
2212 chunk->bg_rec = bg;
2213 chunk->cache.start = bg->objectid;
2214 chunk->cache.size = bg->offset;
2215 chunk->objectid = BTRFS_FIRST_CHUNK_TREE_OBJECTID;
2216 chunk->type = BTRFS_CHUNK_ITEM_KEY;
2217 chunk->offset = bg->objectid;
2218 chunk->generation = bg->generation;
2219 chunk->length = bg->offset;
2220 chunk->owner = BTRFS_CHUNK_TREE_OBJECTID;
2221 chunk->stripe_len = BTRFS_STRIPE_LEN;
2222 chunk->type_flags = bg->flags;
2223 chunk->io_width = BTRFS_STRIPE_LEN;
2224 chunk->io_align = BTRFS_STRIPE_LEN;
2225 chunk->sector_size = rc->sectorsize;
2226 chunk->sub_stripes = calc_sub_nstripes(bg->flags);
2227
2228 ret = insert_cache_extent(&rc->chunk, &chunk->cache);
2229 if (ret == -EEXIST) {
2230 error("duplicate entry in cache start %llu size %llu",
2231 (unsigned long long)chunk->cache.start,
2232 (unsigned long long)chunk->cache.size);
2233 free(chunk);
2234 return ret;
2235 }
2236 BUG_ON(ret);
2237
2238 list_del_init(&bg->list);
2239 if (!nstripes) {
2240 list_add_tail(&chunk->list, &rc->bad_chunks);
2241 continue;
2242 }
2243
2244 list_splice_init(&devexts, &chunk->dextents);
2245
2246 ret = btrfs_verify_device_extents(bg, &devexts, nstripes);
2247 if (ret) {
2248 list_add_tail(&chunk->list, &rc->bad_chunks);
2249 continue;
2250 }
2251
2252 chunk->num_stripes = nstripes;
2253 ret = btrfs_rebuild_chunk_stripes(rc, chunk);
2254 if (ret > 0)
2255 list_add_tail(&chunk->list, &rc->unrepaired_chunks);
2256 else if (ret < 0)
2257 list_add_tail(&chunk->list, &rc->bad_chunks);
2258 else
2259 list_add_tail(&chunk->list, &rc->good_chunks);
2260 }
2261 /*
2262 * Don't worry about the lost orphan device extents, they don't
2263 * have its chunk and block group, they must be the old ones that
2264 * we have dropped.
2265 */
2266 return 0;
2267 }
2268
2269 static inline int is_chunk_overlap(struct chunk_record *chunk1,
2270 struct chunk_record *chunk2)
2271 {
2272 if (chunk1->offset >= chunk2->offset + chunk2->length ||
2273 chunk1->offset + chunk1->length <= chunk2->offset)
2274 return 0;
2275 return 1;
2276 }
2277
2278 /* Move invalid(overlap with good chunks) rebuild chunks to bad chunk list */
2279 static void validate_rebuild_chunks(struct recover_control *rc)
2280 {
2281 struct chunk_record *good;
2282 struct chunk_record *rebuild;
2283 struct chunk_record *tmp;
2284
2285 list_for_each_entry_safe(rebuild, tmp, &rc->rebuild_chunks, list) {
2286 list_for_each_entry(good, &rc->good_chunks, list) {
2287 if (is_chunk_overlap(rebuild, good)) {
2288 list_move_tail(&rebuild->list,
2289 &rc->bad_chunks);
2290 break;
2291 }
2292 }
2293 }
2294 }
2295
2296 /*
2297 * Return 0 when successful, < 0 on error and > 0 if aborted by user
2298 */
2299 int btrfs_recover_chunk_tree(const char *path, int verbose, int yes)
2300 {
2301 int ret = 0;
2302 struct btrfs_root *root = NULL;
2303 struct btrfs_trans_handle *trans;
2304 struct recover_control rc;
2305
2306 init_recover_control(&rc, verbose, yes);
2307
2308 ret = recover_prepare(&rc, path);
2309 if (ret) {
2310 fprintf(stderr, "recover prepare error\n");
2311 return ret;
2312 }
2313
2314 ret = scan_devices(&rc);
2315 if (ret) {
2316 fprintf(stderr, "scan chunk headers error\n");
2317 goto fail_rc;
2318 }
2319
2320 if (cache_tree_empty(&rc.chunk) &&
2321 cache_tree_empty(&rc.bg.tree) &&
2322 cache_tree_empty(&rc.devext.tree)) {
2323 fprintf(stderr, "no recoverable chunk\n");
2324 goto fail_rc;
2325 }
2326
2327 print_scan_result(&rc);
2328
2329 ret = check_chunks(&rc.chunk, &rc.bg, &rc.devext, &rc.good_chunks,
2330 &rc.bad_chunks, &rc.rebuild_chunks, 1);
2331 if (ret) {
2332 if (!list_empty(&rc.bg.block_groups) ||
2333 !list_empty(&rc.devext.no_chunk_orphans)) {
2334 ret = btrfs_recover_chunks(&rc);
2335 if (ret)
2336 goto fail_rc;
2337 }
2338 } else {
2339 print_check_result(&rc);
2340 printf("Check chunks successfully with no orphans\n");
2341 goto fail_rc;
2342 }
2343 validate_rebuild_chunks(&rc);
2344 print_check_result(&rc);
2345
2346 root = open_ctree_with_broken_chunk(&rc);
2347 if (IS_ERR(root)) {
2348 fprintf(stderr, "open with broken chunk error\n");
2349 ret = PTR_ERR(root);
2350 goto fail_rc;
2351 }
2352
2353 ret = check_all_chunks_by_metadata(&rc, root);
2354 if (ret) {
2355 fprintf(stderr, "The chunks in memory can not match the metadata of the fs. Repair failed.\n");
2356 goto fail_close_ctree;
2357 }
2358
2359 ret = btrfs_rebuild_ordered_data_chunk_stripes(&rc, root);
2360 if (ret) {
2361 fprintf(stderr, "Failed to rebuild ordered chunk stripes.\n");
2362 goto fail_close_ctree;
2363 }
2364
2365 if (!rc.yes) {
2366 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?");
2367 if (!ret) {
2368 ret = 1;
2369 goto fail_close_ctree;
2370 }
2371 }
2372
2373 trans = btrfs_start_transaction(root, 1);
2374 BUG_ON(IS_ERR(trans));
2375 ret = remove_chunk_extent_item(trans, &rc, root);
2376 BUG_ON(ret);
2377
2378 ret = rebuild_chunk_tree(trans, &rc, root);
2379 BUG_ON(ret);
2380
2381 ret = rebuild_sys_array(&rc, root);
2382 BUG_ON(ret);
2383
2384 ret = rebuild_block_group(trans, &rc, root);
2385 if (ret) {
2386 printf("Fail to rebuild block groups.\n");
2387 printf("Recommend to run 'btrfs check --init-extent-tree <dev>' after recovery\n");
2388 }
2389
2390 btrfs_commit_transaction(trans, root);
2391 fail_close_ctree:
2392 close_ctree(root);
2393 fail_rc:
2394 free_recover_control(&rc);
2395 return ret;
2396 }
(deprecated) Btrfs progs developments and patch integration