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