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