2 * Copyright (C) 2007 Oracle. All rights reserved.
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public
6 * License v2 as published by the Free Software Foundation.
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
11 * General Public License for more details.
13 * You should have received a copy of the GNU General Public
14 * License along with this program; if not, write to the
15 * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
16 * Boston, MA 021110-1307, USA.
19 #define _XOPEN_SOURCE 500
24 #include "kerncompat.h"
27 #include "print-tree.h"
28 #include "transaction.h"
32 static u64 bytes_used
= 0;
33 static u64 total_csum_bytes
= 0;
34 static u64 total_btree_bytes
= 0;
35 static u64 btree_space_waste
= 0;
36 static u64 data_bytes_allocated
= 0;
37 static u64 data_bytes_referenced
= 0;
39 struct extent_backref
{
40 struct list_head list
;
45 int found_extent_tree
;
49 struct extent_record
{
50 struct list_head backrefs
;
51 struct cache_extent cache
;
52 struct btrfs_disk_key parent_key
;
65 static int check_node(struct btrfs_root
*root
,
66 struct btrfs_disk_key
*parent_key
,
67 struct extent_buffer
*buf
)
70 struct btrfs_key cpukey
;
71 struct btrfs_disk_key key
;
72 u32 nritems
= btrfs_header_nritems(buf
);
74 if (nritems
== 0 || nritems
> BTRFS_NODEPTRS_PER_BLOCK(root
))
76 if (parent_key
->type
) {
77 btrfs_node_key(buf
, &key
, 0);
78 if (memcmp(parent_key
, &key
, sizeof(key
)))
81 for (i
= 0; nritems
> 1 && i
< nritems
- 2; i
++) {
82 btrfs_node_key(buf
, &key
, i
);
83 btrfs_node_key_to_cpu(buf
, &cpukey
, i
+ 1);
84 if (btrfs_comp_keys(&key
, &cpukey
) >= 0)
90 static int check_leaf(struct btrfs_root
*root
,
91 struct btrfs_disk_key
*parent_key
,
92 struct extent_buffer
*buf
)
95 struct btrfs_key cpukey
;
96 struct btrfs_disk_key key
;
97 u32 nritems
= btrfs_header_nritems(buf
);
99 if (btrfs_header_level(buf
) != 0) {
100 fprintf(stderr
, "leaf is not a leaf %llu\n",
101 (unsigned long long)btrfs_header_bytenr(buf
));
104 if (btrfs_leaf_free_space(root
, buf
) < 0) {
105 fprintf(stderr
, "leaf free space incorrect %llu %d\n",
106 (unsigned long long)btrfs_header_bytenr(buf
),
107 btrfs_leaf_free_space(root
, buf
));
114 btrfs_item_key(buf
, &key
, 0);
115 if (parent_key
->type
&& memcmp(parent_key
, &key
, sizeof(key
))) {
116 fprintf(stderr
, "leaf parent key incorrect %llu\n",
117 (unsigned long long)btrfs_header_bytenr(buf
));
120 for (i
= 0; nritems
> 1 && i
< nritems
- 2; i
++) {
121 btrfs_item_key(buf
, &key
, i
);
122 btrfs_item_key_to_cpu(buf
, &cpukey
, i
+ 1);
123 if (btrfs_comp_keys(&key
, &cpukey
) >= 0) {
124 fprintf(stderr
, "bad key ordering %d %d\n", i
, i
+1);
127 if (btrfs_item_offset_nr(buf
, i
) !=
128 btrfs_item_end_nr(buf
, i
+ 1)) {
129 fprintf(stderr
, "incorrect offsets %u %u\n",
130 btrfs_item_offset_nr(buf
, i
),
131 btrfs_item_end_nr(buf
, i
+ 1));
134 if (i
== 0 && btrfs_item_end_nr(buf
, i
) !=
135 BTRFS_LEAF_DATA_SIZE(root
)) {
136 fprintf(stderr
, "bad item end %u wanted %u\n",
137 btrfs_item_end_nr(buf
, i
),
138 (unsigned)BTRFS_LEAF_DATA_SIZE(root
));
145 static int all_backpointers_checked(struct extent_record
*rec
, int print_errs
)
147 struct list_head
*cur
= rec
->backrefs
.next
;
148 struct extent_backref
*back
;
152 while(cur
!= &rec
->backrefs
) {
153 back
= list_entry(cur
, struct extent_backref
, list
);
155 if (!back
->found_extent_tree
) {
159 fprintf(stderr
, "Backref %llu [%llu %llu %llu %llu] "
160 "not found in extent tree\n",
161 (unsigned long long)rec
->start
,
162 (unsigned long long)back
->root
,
163 (unsigned long long)back
->generation
,
164 (unsigned long long)back
->owner
,
165 (unsigned long long)back
->offset
);
167 if (!back
->found_ref
) {
171 fprintf(stderr
, "Backref %llu [%llu %llu %llu %llu] "
173 (unsigned long long)rec
->start
,
174 (unsigned long long)back
->root
,
175 (unsigned long long)back
->generation
,
176 (unsigned long long)back
->owner
,
177 (unsigned long long)back
->offset
);
181 if (found
!= rec
->refs
) {
185 fprintf(stderr
, "Incorrect backref count on %llu found %u "
186 "wanted %u\n", (unsigned long long)rec
->start
,
193 static int free_all_backrefs(struct extent_record
*rec
)
195 struct extent_backref
*back
;
196 struct list_head
*cur
;
197 while (!list_empty(&rec
->backrefs
)) {
198 cur
= rec
->backrefs
.next
;
199 back
= list_entry(cur
, struct extent_backref
, list
);
206 static int maybe_free_extent_rec(struct cache_tree
*extent_cache
,
207 struct extent_record
*rec
)
209 if (rec
->checked
&& rec
->extent_item_refs
== rec
->refs
&&
210 rec
->refs
> 0 && !all_backpointers_checked(rec
, 0)) {
211 remove_cache_extent(extent_cache
, &rec
->cache
);
212 free_all_backrefs(rec
);
218 static int check_block(struct btrfs_root
*root
,
219 struct cache_tree
*extent_cache
,
220 struct extent_buffer
*buf
)
222 struct extent_record
*rec
;
223 struct cache_extent
*cache
;
226 cache
= find_cache_extent(extent_cache
, buf
->start
, buf
->len
);
229 rec
= container_of(cache
, struct extent_record
, cache
);
230 if (btrfs_is_leaf(buf
)) {
231 ret
= check_leaf(root
, &rec
->parent_key
, buf
);
233 ret
= check_node(root
, &rec
->parent_key
, buf
);
237 maybe_free_extent_rec(extent_cache
, rec
);
241 static struct extent_backref
*find_backref(struct extent_record
*rec
,
243 u64 owner
, u64 owner_offset
)
245 struct list_head
*cur
= rec
->backrefs
.next
;
246 struct extent_backref
*back
;
248 while(cur
!= &rec
->backrefs
) {
249 back
= list_entry(cur
, struct extent_backref
, list
);
251 if (back
->root
!= root
|| gen
!= back
->generation
)
253 if (owner
< BTRFS_FIRST_FREE_OBJECTID
)
255 if (owner
!= back
->owner
|| owner_offset
!= back
->offset
)
262 static struct extent_backref
*alloc_backref(struct extent_record
*rec
,
263 u64 root
, u64 gen
, u64 owner
,
266 struct extent_backref
*ref
= malloc(sizeof(*ref
));
268 ref
->generation
= gen
;
270 ref
->offset
= owner_offset
;
271 ref
->found_extent_tree
= 0;
273 list_add_tail(&ref
->list
, &rec
->backrefs
);
277 static int add_extent_rec(struct cache_tree
*extent_cache
,
278 struct btrfs_disk_key
*parent_key
,
279 u64 ref
, u64 start
, u64 nr
,
280 u32 extent_item_refs
, int inc_ref
, int set_checked
)
282 struct extent_record
*rec
;
283 struct cache_extent
*cache
;
286 cache
= find_cache_extent(extent_cache
, start
, nr
);
288 rec
= container_of(cache
, struct extent_record
, cache
);
294 if (start
!= rec
->start
) {
295 fprintf(stderr
, "warning, start mismatch %llu %llu\n",
296 (unsigned long long)rec
->start
,
297 (unsigned long long)start
);
300 if (extent_item_refs
) {
301 if (rec
->extent_item_refs
) {
302 fprintf(stderr
, "block %llu rec "
303 "extent_item_refs %u, passed %u\n",
304 (unsigned long long)start
,
305 rec
->extent_item_refs
,
308 rec
->extent_item_refs
= extent_item_refs
;
314 memcpy(&rec
->parent_key
, parent_key
,
315 sizeof(*parent_key
));
317 maybe_free_extent_rec(extent_cache
, rec
);
320 rec
= malloc(sizeof(*rec
));
322 extent_item_refs
= 0;
326 INIT_LIST_HEAD(&rec
->backrefs
);
333 if (extent_item_refs
)
334 rec
->extent_item_refs
= extent_item_refs
;
336 rec
->extent_item_refs
= 0;
339 memcpy(&rec
->parent_key
, parent_key
, sizeof(*parent_key
));
341 memset(&rec
->parent_key
, 0, sizeof(*parent_key
));
343 rec
->cache
.start
= start
;
344 rec
->cache
.size
= nr
;
345 ret
= insert_existing_cache_extent(extent_cache
, &rec
->cache
);
353 static int add_backref(struct cache_tree
*extent_cache
, u64 bytenr
,
354 u64 root
, u64 gen
, u64 owner
, u64 owner_offset
,
357 struct extent_record
*rec
;
358 struct extent_backref
*back
;
359 struct cache_extent
*cache
;
361 if (root
< BTRFS_FS_TREE_OBJECTID
)
364 cache
= find_cache_extent(extent_cache
, bytenr
, 1);
366 add_extent_rec(extent_cache
, NULL
, 0, bytenr
, 1, 0, 0, 0);
367 cache
= find_cache_extent(extent_cache
, bytenr
, 1);
372 rec
= container_of(cache
, struct extent_record
, cache
);
373 if (rec
->start
!= bytenr
) {
376 back
= find_backref(rec
, root
, gen
, owner
, owner_offset
);
378 back
= alloc_backref(rec
, root
, gen
, owner
, owner_offset
);
381 if (back
->found_ref
) {
382 fprintf(stderr
, "Back ref already exists for %llu "
383 "root %llu gen %llu owner %llu offset %llu\n",
384 (unsigned long long)bytenr
,
385 (unsigned long long)root
,
386 (unsigned long long)gen
,
387 (unsigned long long)owner
,
388 (unsigned long long)owner_offset
);
392 if (back
->found_extent_tree
) {
393 fprintf(stderr
, "Extent back ref already exists "
394 "for %llu root %llu gen %llu owner %llu "
395 "offset %llu\n", (unsigned long long)bytenr
,
396 (unsigned long long)root
,
397 (unsigned long long)gen
,
398 (unsigned long long)owner
,
399 (unsigned long long)owner_offset
);
401 back
->found_extent_tree
= 1;
407 static int add_pending(struct cache_tree
*pending
,
408 struct cache_tree
*seen
, u64 bytenr
, u32 size
)
411 ret
= insert_cache_extent(seen
, bytenr
, size
);
414 insert_cache_extent(pending
, bytenr
, size
);
417 static int pick_next_pending(struct cache_tree
*pending
,
418 struct cache_tree
*reada
,
419 struct cache_tree
*nodes
,
420 u64 last
, struct block_info
*bits
, int bits_nr
,
423 unsigned long node_start
= last
;
424 struct cache_extent
*cache
;
427 cache
= find_first_cache_extent(reada
, 0);
429 bits
[0].start
= cache
->start
;
430 bits
[1].size
= cache
->size
;
435 if (node_start
> 32768)
438 cache
= find_first_cache_extent(nodes
, node_start
);
440 cache
= find_first_cache_extent(nodes
, 0);
443 cache
= find_first_cache_extent(pending
, 0);
448 bits
[ret
].start
= cache
->start
;
449 bits
[ret
].size
= cache
->size
;
450 cache
= next_cache_extent(cache
);
452 } while (cache
&& ret
< bits_nr
);
458 bits
[ret
].start
= cache
->start
;
459 bits
[ret
].size
= cache
->size
;
460 cache
= next_cache_extent(cache
);
462 } while (cache
&& ret
< bits_nr
);
464 if (bits_nr
- ret
> 8) {
465 u64 lookup
= bits
[0].start
+ bits
[0].size
;
466 struct cache_extent
*next
;
467 next
= find_first_cache_extent(pending
, lookup
);
469 if (next
->start
- lookup
> 32768)
471 bits
[ret
].start
= next
->start
;
472 bits
[ret
].size
= next
->size
;
473 lookup
= next
->start
+ next
->size
;
477 next
= next_cache_extent(next
);
485 static int run_next_block(struct btrfs_root
*root
,
486 struct block_info
*bits
,
489 struct cache_tree
*pending
,
490 struct cache_tree
*seen
,
491 struct cache_tree
*reada
,
492 struct cache_tree
*nodes
,
493 struct cache_tree
*extent_cache
)
495 struct extent_buffer
*buf
;
501 struct btrfs_extent_ref
*ref
;
502 struct btrfs_disk_key disk_key
;
503 struct cache_extent
*cache
;
506 ret
= pick_next_pending(pending
, reada
, nodes
, *last
, bits
,
507 bits_nr
, &reada_bits
);
512 for(i
= 0; i
< ret
; i
++) {
513 insert_cache_extent(reada
, bits
[i
].start
,
516 /* fixme, get the parent transid */
517 readahead_tree_block(root
, bits
[i
].start
,
521 *last
= bits
[0].start
;
522 bytenr
= bits
[0].start
;
525 cache
= find_cache_extent(pending
, bytenr
, size
);
527 remove_cache_extent(pending
, cache
);
530 cache
= find_cache_extent(reada
, bytenr
, size
);
532 remove_cache_extent(reada
, cache
);
535 cache
= find_cache_extent(nodes
, bytenr
, size
);
537 remove_cache_extent(nodes
, cache
);
541 /* fixme, get the real parent transid */
542 buf
= read_tree_block(root
, bytenr
, size
, 0);
543 nritems
= btrfs_header_nritems(buf
);
544 ret
= check_block(root
, extent_cache
, buf
);
546 fprintf(stderr
, "bad block %llu\n",
547 (unsigned long long)bytenr
);
549 if (btrfs_is_leaf(buf
)) {
550 btree_space_waste
+= btrfs_leaf_free_space(root
, buf
);
551 for (i
= 0; i
< nritems
; i
++) {
552 struct btrfs_file_extent_item
*fi
;
553 btrfs_item_key(buf
, &disk_key
, i
);
554 if (btrfs_disk_key_type(&disk_key
) ==
555 BTRFS_EXTENT_ITEM_KEY
) {
556 struct btrfs_key found
;
557 struct btrfs_extent_item
*ei
;
558 btrfs_disk_key_to_cpu(&found
, &disk_key
);
559 ei
= btrfs_item_ptr(buf
, i
,
560 struct btrfs_extent_item
);
561 add_extent_rec(extent_cache
, NULL
, 0,
564 btrfs_extent_refs(buf
, ei
),
568 if (btrfs_disk_key_type(&disk_key
) ==
569 BTRFS_CSUM_ITEM_KEY
) {
571 btrfs_item_size_nr(buf
, i
);
574 if (btrfs_disk_key_type(&disk_key
) ==
575 BTRFS_BLOCK_GROUP_ITEM_KEY
) {
576 struct btrfs_block_group_item
*bi
;
577 bi
= btrfs_item_ptr(buf
, i
,
578 struct btrfs_block_group_item
);
580 fprintf(stderr
,"block group %Lu %Lu used %Lu ",
581 btrfs_disk_key_objectid(disk_key
),
582 btrfs_disk_key_offset(disk_key
),
583 btrfs_block_group_used(bi
));
584 fprintf(stderr
, "flags %x\n", bi
->flags
);
588 if (btrfs_disk_key_type(&disk_key
) ==
589 BTRFS_EXTENT_REF_KEY
) {
590 ref
= btrfs_item_ptr(buf
, i
,
591 struct btrfs_extent_ref
);
593 add_backref(extent_cache
,
594 btrfs_disk_key_objectid(&disk_key
),
595 btrfs_ref_root(buf
, ref
),
596 btrfs_ref_generation(buf
, ref
),
597 btrfs_ref_objectid(buf
, ref
),
598 btrfs_ref_offset(buf
, ref
), 0);
601 if (btrfs_disk_key_type(&disk_key
) !=
602 BTRFS_EXTENT_DATA_KEY
)
604 fi
= btrfs_item_ptr(buf
, i
,
605 struct btrfs_file_extent_item
);
606 if (btrfs_file_extent_type(buf
, fi
) !=
607 BTRFS_FILE_EXTENT_REG
)
609 if (btrfs_file_extent_disk_bytenr(buf
, fi
) == 0)
612 data_bytes_allocated
+=
613 btrfs_file_extent_disk_num_bytes(buf
, fi
);
614 if (data_bytes_allocated
< root
->sectorsize
) {
617 data_bytes_referenced
+=
618 btrfs_file_extent_num_bytes(buf
, fi
);
619 ret
= add_extent_rec(extent_cache
, NULL
, bytenr
,
620 btrfs_file_extent_disk_bytenr(buf
, fi
),
621 btrfs_file_extent_disk_num_bytes(buf
, fi
),
623 add_backref(extent_cache
,
624 btrfs_file_extent_disk_bytenr(buf
, fi
),
625 btrfs_header_owner(buf
),
626 btrfs_header_generation(buf
),
627 btrfs_disk_key_objectid(&disk_key
),
628 btrfs_disk_key_offset(&disk_key
), 1);
633 level
= btrfs_header_level(buf
);
634 for (i
= 0; i
< nritems
; i
++) {
635 u64 ptr
= btrfs_node_blockptr(buf
, i
);
636 u32 size
= btrfs_level_size(root
, level
- 1);
637 btrfs_node_key(buf
, &disk_key
, i
);
638 ret
= add_extent_rec(extent_cache
,
644 add_backref(extent_cache
, ptr
,
645 btrfs_header_owner(buf
),
646 btrfs_header_generation(buf
),
648 btrfs_disk_key_objectid(&disk_key
), 1);
651 add_pending(nodes
, seen
, ptr
, size
);
653 add_pending(pending
, seen
, ptr
, size
);
656 btree_space_waste
+= (BTRFS_NODEPTRS_PER_BLOCK(root
) -
657 nritems
) * sizeof(struct btrfs_key_ptr
);
659 total_btree_bytes
+= buf
->len
;
660 free_extent_buffer(buf
);
664 static int add_root_to_pending(struct extent_buffer
*buf
,
665 struct block_info
*bits
,
667 struct cache_tree
*extent_cache
,
668 struct cache_tree
*pending
,
669 struct cache_tree
*seen
,
670 struct cache_tree
*reada
,
671 struct cache_tree
*nodes
, u64 root_objectid
)
673 if (btrfs_header_level(buf
) > 0)
674 add_pending(nodes
, seen
, buf
->start
, buf
->len
);
676 add_pending(pending
, seen
, buf
->start
, buf
->len
);
677 add_extent_rec(extent_cache
, NULL
, 0, buf
->start
, buf
->len
,
680 add_backref(extent_cache
, buf
->start
, root_objectid
,
681 btrfs_header_generation(buf
),
682 btrfs_header_level(buf
), 0, 1);
686 int check_extent_refs(struct btrfs_root
*root
,
687 struct cache_tree
*extent_cache
)
689 struct extent_record
*rec
;
690 struct cache_extent
*cache
;
694 cache
= find_first_cache_extent(extent_cache
, 0);
697 rec
= container_of(cache
, struct extent_record
, cache
);
698 if (rec
->refs
!= rec
->extent_item_refs
) {
699 fprintf(stderr
, "ref mismatch on [%llu %llu] ",
700 (unsigned long long)rec
->start
,
701 (unsigned long long)rec
->nr
);
702 fprintf(stderr
, "extent item %u, found %u\n",
703 rec
->extent_item_refs
,
707 if (all_backpointers_checked(rec
, 1)) {
708 fprintf(stderr
, "backpointer mismatch on [%llu %llu]\n",
709 (unsigned long long)rec
->start
,
710 (unsigned long long)rec
->nr
);
714 remove_cache_extent(extent_cache
, cache
);
715 free_all_backrefs(rec
);
721 void print_usage(void) {
722 fprintf(stderr
, "usage: btrfsck dev\n");
723 fprintf(stderr
, "%s\n", BTRFS_BUILD_VERSION
);
727 int main(int ac
, char **av
) {
728 struct btrfs_root
*root
;
729 struct cache_tree extent_cache
;
730 struct cache_tree seen
;
731 struct cache_tree pending
;
732 struct cache_tree reada
;
733 struct cache_tree nodes
;
734 struct btrfs_path path
;
735 struct btrfs_key key
;
736 struct btrfs_key found_key
;
739 struct block_info
*bits
;
741 struct extent_buffer
*leaf
;
743 struct btrfs_root_item ri
;
749 cache_tree_init(&extent_cache
);
750 cache_tree_init(&seen
);
751 cache_tree_init(&pending
);
752 cache_tree_init(&nodes
);
753 cache_tree_init(&reada
);
755 root
= open_ctree(av
[1], 0, 0);
758 bits
= malloc(bits_nr
* sizeof(struct block_info
));
764 add_root_to_pending(root
->fs_info
->tree_root
->node
, bits
, bits_nr
,
765 &extent_cache
, &pending
, &seen
, &reada
, &nodes
,
766 root
->fs_info
->tree_root
->root_key
.objectid
);
768 add_root_to_pending(root
->fs_info
->chunk_root
->node
, bits
, bits_nr
,
769 &extent_cache
, &pending
, &seen
, &reada
, &nodes
,
770 root
->fs_info
->chunk_root
->root_key
.objectid
);
772 btrfs_init_path(&path
);
775 btrfs_set_key_type(&key
, BTRFS_ROOT_ITEM_KEY
);
776 ret
= btrfs_search_slot(NULL
, root
->fs_info
->tree_root
,
780 leaf
= path
.nodes
[0];
781 slot
= path
.slots
[0];
782 if (slot
>= btrfs_header_nritems(path
.nodes
[0])) {
783 ret
= btrfs_next_leaf(root
, &path
);
786 leaf
= path
.nodes
[0];
787 slot
= path
.slots
[0];
789 btrfs_item_key_to_cpu(leaf
, &found_key
, path
.slots
[0]);
790 if (btrfs_key_type(&found_key
) == BTRFS_ROOT_ITEM_KEY
) {
791 unsigned long offset
;
792 struct extent_buffer
*buf
;
794 offset
= btrfs_item_ptr_offset(leaf
, path
.slots
[0]);
795 read_extent_buffer(leaf
, &ri
, offset
, sizeof(ri
));
796 buf
= read_tree_block(root
->fs_info
->tree_root
,
797 btrfs_root_bytenr(&ri
),
798 btrfs_level_size(root
,
799 btrfs_root_level(&ri
)), 0);
800 add_root_to_pending(buf
, bits
, bits_nr
, &extent_cache
,
801 &pending
, &seen
, &reada
, &nodes
,
803 free_extent_buffer(buf
);
807 btrfs_release_path(root
, &path
);
809 ret
= run_next_block(root
, bits
, bits_nr
, &last
, &pending
,
810 &seen
, &reada
, &nodes
, &extent_cache
);
814 ret
= check_extent_refs(root
, &extent_cache
);
816 printf("found %llu bytes used err is %d\n",
817 (unsigned long long)bytes_used
, ret
);
818 printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes
);
819 printf("total tree bytes: %llu\n",
820 (unsigned long long)total_btree_bytes
);
821 printf("btree space waste bytes: %llu\n",
822 (unsigned long long)btree_space_waste
);
823 printf("file data blocks allocated: %llu\n referenced %llu\n",
824 (unsigned long long)data_bytes_allocated
,
825 (unsigned long long)data_bytes_referenced
);
826 printf("%s\n", BTRFS_BUILD_VERSION
);