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"
31 static u64 bytes_used = 0;
32 static u64 total_csum_bytes = 0;
33 static u64 total_btree_bytes = 0;
34 static u64 btree_space_waste = 0;
35 static u64 data_bytes_allocated = 0;
36 static u64 data_bytes_referenced = 0;
38 struct extent_backref {
39 struct list_head list;
44 int found_extent_tree;
48 struct extent_record {
49 struct list_head backrefs;
50 struct cache_extent cache;
51 struct btrfs_disk_key parent_key;
64 static int check_node(struct btrfs_root *root,
65 struct btrfs_disk_key *parent_key,
66 struct extent_buffer *buf)
69 struct btrfs_key cpukey;
70 struct btrfs_disk_key key;
71 u32 nritems = btrfs_header_nritems(buf);
73 if (nritems == 0 || nritems > BTRFS_NODEPTRS_PER_BLOCK(root))
75 if (parent_key->type) {
76 btrfs_node_key(buf, &key, 0);
77 if (memcmp(parent_key, &key, sizeof(key)))
80 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
81 btrfs_node_key(buf, &key, i);
82 btrfs_node_key_to_cpu(buf, &cpukey, i + 1);
83 if (btrfs_comp_keys(&key, &cpukey) >= 0)
89 static int check_leaf(struct btrfs_root *root,
90 struct btrfs_disk_key *parent_key,
91 struct extent_buffer *buf)
94 struct btrfs_key cpukey;
95 struct btrfs_disk_key key;
96 u32 nritems = btrfs_header_nritems(buf);
98 if (btrfs_header_level(buf) != 0) {
99 fprintf(stderr, "leaf is not a leaf %llu\n",
100 (unsigned long long)btrfs_header_bytenr(buf));
103 if (btrfs_leaf_free_space(root, buf) < 0) {
104 fprintf(stderr, "leaf free space incorrect %llu %d\n",
105 (unsigned long long)btrfs_header_bytenr(buf),
106 btrfs_leaf_free_space(root, buf));
113 btrfs_item_key(buf, &key, 0);
114 if (parent_key->type && memcmp(parent_key, &key, sizeof(key))) {
115 fprintf(stderr, "leaf parent key incorrect %llu\n",
116 (unsigned long long)btrfs_header_bytenr(buf));
119 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
120 btrfs_item_key(buf, &key, i);
121 btrfs_item_key_to_cpu(buf, &cpukey, i + 1);
122 if (btrfs_comp_keys(&key, &cpukey) >= 0) {
123 fprintf(stderr, "bad key ordering %d %d\n", i, i+1);
126 if (btrfs_item_offset_nr(buf, i) !=
127 btrfs_item_end_nr(buf, i + 1)) {
128 fprintf(stderr, "incorrect offsets %u %u\n",
129 btrfs_item_offset_nr(buf, i),
130 btrfs_item_end_nr(buf, i + 1));
133 if (i == 0 && btrfs_item_end_nr(buf, i) !=
134 BTRFS_LEAF_DATA_SIZE(root)) {
135 fprintf(stderr, "bad item end %u wanted %lu\n",
136 btrfs_item_end_nr(buf, i),
137 BTRFS_LEAF_DATA_SIZE(root));
144 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
146 struct list_head *cur = rec->backrefs.next;
147 struct extent_backref *back;
151 while(cur != &rec->backrefs) {
152 back = list_entry(cur, struct extent_backref, list);
154 if (!back->found_extent_tree) {
158 fprintf(stderr, "Backref %llu [%llu %llu %llu %llu] "
159 "not found in extent tree\n",
160 (unsigned long long)rec->start,
161 (unsigned long long)back->root,
162 (unsigned long long)back->generation,
163 (unsigned long long)back->owner,
164 (unsigned long long)back->offset);
166 if (!back->found_ref) {
170 fprintf(stderr, "Backref %llu [%llu %llu %llu %llu] "
172 (unsigned long long)rec->start,
173 (unsigned long long)back->root,
174 (unsigned long long)back->generation,
175 (unsigned long long)back->owner,
176 (unsigned long long)back->offset);
180 if (found != rec->refs) {
184 fprintf(stderr, "Incorrect backref count on %llu found %u "
185 "wanted %u\n", (unsigned long long)rec->start,
192 static int free_all_backrefs(struct extent_record *rec)
194 struct extent_backref *back;
195 struct list_head *cur;
196 while (!list_empty(&rec->backrefs)) {
197 cur = rec->backrefs.next;
198 back = list_entry(cur, struct extent_backref, list);
205 static int maybe_free_extent_rec(struct cache_tree *extent_cache,
206 struct extent_record *rec)
208 if (rec->checked && rec->extent_item_refs == rec->refs &&
209 rec->refs > 0 && !all_backpointers_checked(rec, 0)) {
210 remove_cache_extent(extent_cache, &rec->cache);
211 free_all_backrefs(rec);
217 static int check_block(struct btrfs_root *root,
218 struct cache_tree *extent_cache,
219 struct extent_buffer *buf)
221 struct extent_record *rec;
222 struct cache_extent *cache;
225 cache = find_cache_extent(extent_cache, buf->start, buf->len);
228 rec = container_of(cache, struct extent_record, cache);
229 if (btrfs_is_leaf(buf)) {
230 ret = check_leaf(root, &rec->parent_key, buf);
232 ret = check_node(root, &rec->parent_key, buf);
236 maybe_free_extent_rec(extent_cache, rec);
240 static struct extent_backref *find_backref(struct extent_record *rec,
242 u64 owner, u64 owner_offset)
244 struct list_head *cur = rec->backrefs.next;
245 struct extent_backref *back;
247 while(cur != &rec->backrefs) {
248 back = list_entry(cur, struct extent_backref, list);
250 if (back->root != root || gen != back->generation)
252 if (owner < BTRFS_FIRST_FREE_OBJECTID)
254 if (owner != back->owner || owner_offset != back->offset)
261 static struct extent_backref *alloc_backref(struct extent_record *rec,
262 u64 root, u64 gen, u64 owner,
265 struct extent_backref *ref = malloc(sizeof(*ref));
267 ref->generation = gen;
269 ref->offset = owner_offset;
270 ref->found_extent_tree = 0;
272 list_add_tail(&ref->list, &rec->backrefs);
276 static int add_extent_rec(struct cache_tree *extent_cache,
277 struct btrfs_disk_key *parent_key,
278 u64 ref, u64 start, u64 nr,
279 u32 extent_item_refs, int inc_ref, int set_checked)
281 struct extent_record *rec;
282 struct cache_extent *cache;
285 cache = find_cache_extent(extent_cache, start, nr);
287 rec = container_of(cache, struct extent_record, cache);
293 if (start != rec->start) {
294 fprintf(stderr, "warning, start mismatch %llu %llu\n",
295 (unsigned long long)rec->start,
296 (unsigned long long)start);
299 if (extent_item_refs) {
300 if (rec->extent_item_refs) {
301 fprintf(stderr, "block %llu rec "
302 "extent_item_refs %u, passed %u\n",
303 (unsigned long long)start,
304 rec->extent_item_refs,
307 rec->extent_item_refs = extent_item_refs;
313 memcpy(&rec->parent_key, parent_key,
314 sizeof(*parent_key));
316 maybe_free_extent_rec(extent_cache, rec);
319 rec = malloc(sizeof(*rec));
321 extent_item_refs = 0;
325 INIT_LIST_HEAD(&rec->backrefs);
332 if (extent_item_refs)
333 rec->extent_item_refs = extent_item_refs;
335 rec->extent_item_refs = 0;
338 memcpy(&rec->parent_key, parent_key, sizeof(*parent_key));
340 memset(&rec->parent_key, 0, sizeof(*parent_key));
342 rec->cache.start = start;
343 rec->cache.size = nr;
344 ret = insert_existing_cache_extent(extent_cache, &rec->cache);
352 static int add_backref(struct cache_tree *extent_cache, u64 bytenr,
353 u64 root, u64 gen, u64 owner, u64 owner_offset,
356 struct extent_record *rec;
357 struct extent_backref *back;
358 struct cache_extent *cache;
360 if (root < BTRFS_FS_TREE_OBJECTID)
363 cache = find_cache_extent(extent_cache, bytenr, 1);
365 add_extent_rec(extent_cache, NULL, 0, bytenr, 1, 0, 0, 0);
366 cache = find_cache_extent(extent_cache, bytenr, 1);
371 rec = container_of(cache, struct extent_record, cache);
372 if (rec->start != bytenr) {
375 back = find_backref(rec, root, gen, owner, owner_offset);
377 back = alloc_backref(rec, root, gen, owner, owner_offset);
380 if (back->found_ref) {
381 fprintf(stderr, "Back ref already exists for %llu "
382 "root %llu gen %llu owner %llu offset %llu\n",
383 (unsigned long long)bytenr,
384 (unsigned long long)root,
385 (unsigned long long)gen,
386 (unsigned long long)owner,
387 (unsigned long long)owner_offset);
391 if (back->found_extent_tree) {
392 fprintf(stderr, "Extent back ref already exists "
393 "for %llu root %llu gen %llu owner %llu "
394 "offset %llu\n", (unsigned long long)bytenr,
395 (unsigned long long)root,
396 (unsigned long long)gen,
397 (unsigned long long)owner,
398 (unsigned long long)owner_offset);
400 back->found_extent_tree = 1;
406 static int add_pending(struct cache_tree *pending,
407 struct cache_tree *seen, u64 bytenr, u32 size)
410 ret = insert_cache_extent(seen, bytenr, size);
413 insert_cache_extent(pending, bytenr, size);
416 static int pick_next_pending(struct cache_tree *pending,
417 struct cache_tree *reada,
418 struct cache_tree *nodes,
419 u64 last, struct block_info *bits, int bits_nr,
422 unsigned long node_start = last;
423 struct cache_extent *cache;
426 cache = find_first_cache_extent(reada, 0);
428 bits[0].start = cache->start;
429 bits[1].size = cache->size;
434 if (node_start > 32768)
437 cache = find_first_cache_extent(nodes, node_start);
439 cache = find_first_cache_extent(nodes, 0);
442 cache = find_first_cache_extent(pending, 0);
447 bits[ret].start = cache->start;
448 bits[ret].size = cache->size;
449 cache = next_cache_extent(cache);
451 } while (cache && ret < bits_nr);
457 bits[ret].start = cache->start;
458 bits[ret].size = cache->size;
459 cache = next_cache_extent(cache);
461 } while (cache && ret < bits_nr);
463 if (bits_nr - ret > 8) {
464 u64 lookup = bits[0].start + bits[0].size;
465 struct cache_extent *next;
466 next = find_first_cache_extent(pending, lookup);
468 if (next->start - lookup > 32768)
470 bits[ret].start = next->start;
471 bits[ret].size = next->size;
472 lookup = next->start + next->size;
476 next = next_cache_extent(next);
483 static struct extent_buffer reada_buf;
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;
507 ret = pick_next_pending(pending, reada, nodes, *last, bits,
508 bits_nr, &reada_bits);
513 for(i = 0; i < ret; i++) {
515 insert_cache_extent(reada, bits[i].start,
517 btrfs_map_bh_to_logical(root, &reada_buf,
519 offset = reada_buf.dev_bytenr;
520 last_block = bits[i].start;
521 readahead(reada_buf.fd, offset, bits[i].size);
524 *last = bits[0].start;
525 bytenr = bits[0].start;
528 cache = find_cache_extent(pending, bytenr, size);
530 remove_cache_extent(pending, cache);
533 cache = find_cache_extent(reada, bytenr, size);
535 remove_cache_extent(reada, cache);
538 cache = find_cache_extent(nodes, bytenr, size);
540 remove_cache_extent(nodes, cache);
544 buf = read_tree_block(root, bytenr, size);
545 nritems = btrfs_header_nritems(buf);
546 ret = check_block(root, extent_cache, buf);
548 fprintf(stderr, "bad block %llu\n",
549 (unsigned long long)bytenr);
551 if (btrfs_is_leaf(buf)) {
552 btree_space_waste += btrfs_leaf_free_space(root, buf);
553 for (i = 0; i < nritems; i++) {
554 struct btrfs_file_extent_item *fi;
555 btrfs_item_key(buf, &disk_key, i);
556 if (btrfs_disk_key_type(&disk_key) ==
557 BTRFS_EXTENT_ITEM_KEY) {
558 struct btrfs_key found;
559 struct btrfs_extent_item *ei;
560 btrfs_disk_key_to_cpu(&found, &disk_key);
561 ei = btrfs_item_ptr(buf, i,
562 struct btrfs_extent_item);
563 add_extent_rec(extent_cache, NULL, 0,
566 btrfs_extent_refs(buf, ei),
570 if (btrfs_disk_key_type(&disk_key) ==
571 BTRFS_CSUM_ITEM_KEY) {
573 btrfs_item_size_nr(buf, i);
576 if (btrfs_disk_key_type(&disk_key) ==
577 BTRFS_BLOCK_GROUP_ITEM_KEY) {
578 struct btrfs_block_group_item *bi;
579 bi = btrfs_item_ptr(buf, i,
580 struct btrfs_block_group_item);
582 fprintf(stderr,"block group %Lu %Lu used %Lu ",
583 btrfs_disk_key_objectid(disk_key),
584 btrfs_disk_key_offset(disk_key),
585 btrfs_block_group_used(bi));
586 fprintf(stderr, "flags %x\n", bi->flags);
590 if (btrfs_disk_key_type(&disk_key) ==
591 BTRFS_EXTENT_REF_KEY) {
592 ref = btrfs_item_ptr(buf, i,
593 struct btrfs_extent_ref);
595 add_backref(extent_cache,
596 btrfs_disk_key_objectid(&disk_key),
597 btrfs_ref_root(buf, ref),
598 btrfs_ref_generation(buf, ref),
599 btrfs_ref_objectid(buf, ref),
600 btrfs_ref_offset(buf, ref), 0);
603 if (btrfs_disk_key_type(&disk_key) !=
604 BTRFS_EXTENT_DATA_KEY)
606 fi = btrfs_item_ptr(buf, i,
607 struct btrfs_file_extent_item);
608 if (btrfs_file_extent_type(buf, fi) !=
609 BTRFS_FILE_EXTENT_REG)
611 if (btrfs_file_extent_disk_bytenr(buf, fi) == 0)
614 data_bytes_allocated +=
615 btrfs_file_extent_disk_num_bytes(buf, fi);
616 data_bytes_referenced +=
617 btrfs_file_extent_num_bytes(buf, fi);
618 ret = add_extent_rec(extent_cache, NULL, bytenr,
619 btrfs_file_extent_disk_bytenr(buf, fi),
620 btrfs_file_extent_disk_num_bytes(buf, fi),
622 add_backref(extent_cache,
623 btrfs_file_extent_disk_bytenr(buf, fi),
624 btrfs_header_owner(buf),
625 btrfs_header_generation(buf),
626 btrfs_disk_key_objectid(&disk_key),
627 btrfs_disk_key_offset(&disk_key), 1);
632 level = btrfs_header_level(buf);
633 for (i = 0; i < nritems; i++) {
634 u64 ptr = btrfs_node_blockptr(buf, i);
635 u32 size = btrfs_level_size(root, level - 1);
636 btrfs_node_key(buf, &disk_key, i);
637 ret = add_extent_rec(extent_cache,
643 add_backref(extent_cache, ptr,
644 btrfs_header_owner(buf),
645 btrfs_header_generation(buf),
647 btrfs_disk_key_objectid(&disk_key), 1);
650 add_pending(nodes, seen, ptr, size);
652 add_pending(pending, seen, ptr, size);
655 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) -
656 nritems) * sizeof(struct btrfs_key_ptr);
658 total_btree_bytes += buf->len;
659 free_extent_buffer(buf);
663 static int add_root_to_pending(struct extent_buffer *buf,
664 struct block_info *bits,
666 struct cache_tree *extent_cache,
667 struct cache_tree *pending,
668 struct cache_tree *seen,
669 struct cache_tree *reada,
670 struct cache_tree *nodes, u64 root_objectid)
672 if (btrfs_header_level(buf) > 0)
673 add_pending(nodes, seen, buf->start, buf->len);
675 add_pending(pending, seen, buf->start, buf->len);
676 add_extent_rec(extent_cache, NULL, 0, buf->start, buf->len,
679 add_backref(extent_cache, buf->start, root_objectid,
680 btrfs_header_generation(buf),
681 btrfs_header_level(buf), 0, 1);
685 int check_extent_refs(struct btrfs_root *root,
686 struct cache_tree *extent_cache)
688 struct extent_record *rec;
689 struct cache_extent *cache;
693 cache = find_first_cache_extent(extent_cache, 0);
696 rec = container_of(cache, struct extent_record, cache);
697 if (rec->refs != rec->extent_item_refs) {
698 fprintf(stderr, "ref mismatch on [%llu %llu] ",
699 (unsigned long long)rec->start,
700 (unsigned long long)rec->nr);
701 fprintf(stderr, "extent item %u, found %u\n",
702 rec->extent_item_refs,
706 if (all_backpointers_checked(rec, 1)) {
707 fprintf(stderr, "backpointer mismatch on [%llu %llu]\n",
708 (unsigned long long)rec->start,
709 (unsigned long long)rec->nr);
713 remove_cache_extent(extent_cache, cache);
714 free_all_backrefs(rec);
720 void print_usage(void) {
721 fprintf(stderr, "usage: btrfsck dev\n");
725 int main(int ac, char **av) {
726 struct btrfs_root *root;
727 struct cache_tree extent_cache;
728 struct cache_tree seen;
729 struct cache_tree pending;
730 struct cache_tree reada;
731 struct cache_tree nodes;
732 struct btrfs_path path;
733 struct btrfs_key key;
734 struct btrfs_key found_key;
737 struct block_info *bits;
739 struct extent_buffer *leaf;
741 struct btrfs_root_item ri;
747 cache_tree_init(&extent_cache);
748 cache_tree_init(&seen);
749 cache_tree_init(&pending);
750 cache_tree_init(&nodes);
751 cache_tree_init(&reada);
753 root = open_ctree(av[1], 0);
756 bits = malloc(bits_nr * sizeof(struct block_info));
762 add_root_to_pending(root->fs_info->tree_root->node, bits, bits_nr,
763 &extent_cache, &pending, &seen, &reada, &nodes,
764 root->fs_info->tree_root->root_key.objectid);
766 add_root_to_pending(root->fs_info->chunk_root->node, bits, bits_nr,
767 &extent_cache, &pending, &seen, &reada, &nodes,
768 root->fs_info->chunk_root->root_key.objectid);
770 btrfs_init_path(&path);
773 btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
774 ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
778 leaf = path.nodes[0];
779 slot = path.slots[0];
780 if (slot >= btrfs_header_nritems(path.nodes[0])) {
781 ret = btrfs_next_leaf(root, &path);
784 leaf = path.nodes[0];
785 slot = path.slots[0];
787 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
788 if (btrfs_key_type(&found_key) == BTRFS_ROOT_ITEM_KEY) {
789 unsigned long offset;
790 struct extent_buffer *buf;
792 offset = btrfs_item_ptr_offset(leaf, path.slots[0]);
793 read_extent_buffer(leaf, &ri, offset, sizeof(ri));
794 buf = read_tree_block(root->fs_info->tree_root,
795 btrfs_root_bytenr(&ri),
796 btrfs_level_size(root,
797 btrfs_root_level(&ri)));
798 add_root_to_pending(buf, bits, bits_nr, &extent_cache,
799 &pending, &seen, &reada, &nodes,
801 free_extent_buffer(buf);
805 btrfs_release_path(root, &path);
807 ret = run_next_block(root, bits, bits_nr, &last, &pending,
808 &seen, &reada, &nodes, &extent_cache);
812 ret = check_extent_refs(root, &extent_cache);
814 printf("found %llu bytes used err is %d\n",
815 (unsigned long long)bytes_used, ret);
816 printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes);
817 printf("total tree bytes: %llu\n",
818 (unsigned long long)total_btree_bytes);
819 printf("btree space waste bytes: %llu\n",
820 (unsigned long long)btree_space_waste);
821 printf("file data blocks allocated: %llu\n referenced %llu\n",
822 (unsigned long long)data_bytes_allocated,
823 (unsigned long long)data_bytes_referenced);