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)
124 if (btrfs_item_offset_nr(buf, i) !=
125 btrfs_item_end_nr(buf, i + 1))
128 if (btrfs_item_end_nr(buf, i) !=
129 BTRFS_LEAF_DATA_SIZE(root))
136 static int all_backpointers_checked(struct extent_record *rec, int print_errs)
138 struct list_head *cur = rec->backrefs.next;
139 struct extent_backref *back;
143 while(cur != &rec->backrefs) {
144 back = list_entry(cur, struct extent_backref, list);
146 if (!back->found_extent_tree) {
150 fprintf(stderr, "Backref %llu [%llu %llu %llu %llu] "
151 "not found in extent tree\n",
152 (unsigned long long)rec->start,
153 (unsigned long long)back->root,
154 (unsigned long long)back->generation,
155 (unsigned long long)back->owner,
156 (unsigned long long)back->offset);
158 if (!back->found_ref) {
162 fprintf(stderr, "Backref %llu [%llu %llu %llu %llu] "
164 (unsigned long long)rec->start,
165 (unsigned long long)back->root,
166 (unsigned long long)back->generation,
167 (unsigned long long)back->owner,
168 (unsigned long long)back->offset);
172 if (found != rec->refs) {
176 fprintf(stderr, "Incorrect backref count on %llu found %u "
177 "wanted %u\n", (unsigned long long)rec->start,
184 static int free_all_backrefs(struct extent_record *rec)
186 struct extent_backref *back;
187 struct list_head *cur;
188 while (!list_empty(&rec->backrefs)) {
189 cur = rec->backrefs.next;
190 back = list_entry(cur, struct extent_backref, list);
197 static int maybe_free_extent_rec(struct cache_tree *extent_cache,
198 struct extent_record *rec)
200 if (rec->checked && rec->extent_item_refs == rec->refs &&
201 rec->refs > 0 && !all_backpointers_checked(rec, 0)) {
202 remove_cache_extent(extent_cache, &rec->cache);
203 free_all_backrefs(rec);
209 static int check_block(struct btrfs_root *root,
210 struct cache_tree *extent_cache,
211 struct extent_buffer *buf)
213 struct extent_record *rec;
214 struct cache_extent *cache;
217 cache = find_cache_extent(extent_cache, buf->start, buf->len);
220 rec = container_of(cache, struct extent_record, cache);
221 if (btrfs_is_leaf(buf)) {
222 ret = check_leaf(root, &rec->parent_key, buf);
224 ret = check_node(root, &rec->parent_key, buf);
228 maybe_free_extent_rec(extent_cache, rec);
232 static struct extent_backref *find_backref(struct extent_record *rec,
234 u64 owner, u64 owner_offset)
236 struct list_head *cur = rec->backrefs.next;
237 struct extent_backref *back;
239 while(cur != &rec->backrefs) {
240 back = list_entry(cur, struct extent_backref, list);
242 if (back->root != root || gen != back->generation)
244 if (owner < BTRFS_FIRST_FREE_OBJECTID)
246 if (owner != back->owner || owner_offset != back->offset)
253 static struct extent_backref *alloc_backref(struct extent_record *rec,
254 u64 root, u64 gen, u64 owner,
257 struct extent_backref *ref = malloc(sizeof(*ref));
259 ref->generation = gen;
261 ref->offset = owner_offset;
262 ref->found_extent_tree = 0;
264 list_add_tail(&ref->list, &rec->backrefs);
268 static int add_extent_rec(struct cache_tree *extent_cache,
269 struct btrfs_disk_key *parent_key,
270 u64 ref, u64 start, u64 nr,
271 u32 extent_item_refs, int inc_ref, int set_checked)
273 struct extent_record *rec;
274 struct cache_extent *cache;
277 cache = find_cache_extent(extent_cache, start, nr);
279 rec = container_of(cache, struct extent_record, cache);
285 if (start != rec->start) {
286 fprintf(stderr, "warning, start mismatch %llu %llu\n",
287 (unsigned long long)rec->start,
288 (unsigned long long)start);
291 if (extent_item_refs) {
292 if (rec->extent_item_refs) {
293 fprintf(stderr, "block %llu rec "
294 "extent_item_refs %u, passed %u\n",
295 (unsigned long long)start,
296 rec->extent_item_refs,
299 rec->extent_item_refs = extent_item_refs;
305 memcpy(&rec->parent_key, parent_key,
306 sizeof(*parent_key));
308 maybe_free_extent_rec(extent_cache, rec);
311 rec = malloc(sizeof(*rec));
313 extent_item_refs = 0;
317 INIT_LIST_HEAD(&rec->backrefs);
324 if (extent_item_refs)
325 rec->extent_item_refs = extent_item_refs;
327 rec->extent_item_refs = 0;
330 memcpy(&rec->parent_key, parent_key, sizeof(*parent_key));
332 memset(&rec->parent_key, 0, sizeof(*parent_key));
334 rec->cache.start = start;
335 rec->cache.size = nr;
336 ret = insert_existing_cache_extent(extent_cache, &rec->cache);
344 static int add_backref(struct cache_tree *extent_cache, u64 bytenr,
345 u64 root, u64 gen, u64 owner, u64 owner_offset,
348 struct extent_record *rec;
349 struct extent_backref *back;
350 struct cache_extent *cache;
352 if (root < BTRFS_FS_TREE_OBJECTID)
355 cache = find_cache_extent(extent_cache, bytenr, 1);
357 add_extent_rec(extent_cache, NULL, 0, bytenr, 1, 0, 0, 0);
358 cache = find_cache_extent(extent_cache, bytenr, 1);
363 rec = container_of(cache, struct extent_record, cache);
364 if (rec->start != bytenr) {
367 back = find_backref(rec, root, gen, owner, owner_offset);
369 back = alloc_backref(rec, root, gen, owner, owner_offset);
372 if (back->found_ref) {
373 fprintf(stderr, "Back ref already exists for %llu "
374 "root %llu gen %llu owner %llu offset %llu\n",
375 (unsigned long long)bytenr,
376 (unsigned long long)root,
377 (unsigned long long)gen,
378 (unsigned long long)owner,
379 (unsigned long long)owner_offset);
383 if (back->found_extent_tree) {
384 fprintf(stderr, "Extent back ref already exists "
385 "for %llu root %llu gen %llu owner %llu "
386 "offset %llu\n", (unsigned long long)bytenr,
387 (unsigned long long)root,
388 (unsigned long long)gen,
389 (unsigned long long)owner,
390 (unsigned long long)owner_offset);
392 back->found_extent_tree = 1;
398 static int add_pending(struct cache_tree *pending,
399 struct cache_tree *seen, u64 bytenr, u32 size)
402 ret = insert_cache_extent(seen, bytenr, size);
405 insert_cache_extent(pending, bytenr, size);
408 static int pick_next_pending(struct cache_tree *pending,
409 struct cache_tree *reada,
410 struct cache_tree *nodes,
411 u64 last, struct block_info *bits, int bits_nr,
414 unsigned long node_start = last;
415 struct cache_extent *cache;
418 cache = find_first_cache_extent(reada, 0);
420 bits[0].start = cache->start;
421 bits[1].size = cache->size;
426 if (node_start > 32768)
429 cache = find_first_cache_extent(nodes, node_start);
431 cache = find_first_cache_extent(nodes, 0);
434 cache = find_first_cache_extent(pending, 0);
439 bits[ret].start = cache->start;
440 bits[ret].size = cache->size;
441 cache = next_cache_extent(cache);
443 } while (cache && ret < bits_nr);
449 bits[ret].start = cache->start;
450 bits[ret].size = cache->size;
451 cache = next_cache_extent(cache);
453 } while (cache && ret < bits_nr);
455 if (bits_nr - ret > 8) {
456 u64 lookup = bits[0].start + bits[0].size;
457 struct cache_extent *next;
458 next = find_first_cache_extent(pending, lookup);
460 if (next->start - lookup > 32768)
462 bits[ret].start = next->start;
463 bits[ret].size = next->size;
464 lookup = next->start + next->size;
468 next = next_cache_extent(next);
475 static struct extent_buffer reada_buf;
477 static int run_next_block(struct btrfs_root *root,
478 struct block_info *bits,
481 struct cache_tree *pending,
482 struct cache_tree *seen,
483 struct cache_tree *reada,
484 struct cache_tree *nodes,
485 struct cache_tree *extent_cache)
487 struct extent_buffer *buf;
493 struct btrfs_extent_ref *ref;
494 struct btrfs_disk_key disk_key;
495 struct cache_extent *cache;
499 ret = pick_next_pending(pending, reada, nodes, *last, bits,
500 bits_nr, &reada_bits);
505 for(i = 0; i < ret; i++) {
507 insert_cache_extent(reada, bits[i].start,
509 btrfs_map_bh_to_logical(root, &reada_buf,
511 offset = reada_buf.dev_bytenr;
512 last_block = bits[i].start;
513 readahead(reada_buf.fd, offset, bits[i].size);
516 *last = bits[0].start;
517 bytenr = bits[0].start;
520 cache = find_cache_extent(pending, bytenr, size);
522 remove_cache_extent(pending, cache);
525 cache = find_cache_extent(reada, bytenr, size);
527 remove_cache_extent(reada, cache);
530 cache = find_cache_extent(nodes, bytenr, size);
532 remove_cache_extent(nodes, cache);
536 buf = read_tree_block(root, bytenr, size);
537 nritems = btrfs_header_nritems(buf);
538 ret = check_block(root, extent_cache, buf);
540 fprintf(stderr, "bad block %llu\n",
541 (unsigned long long)bytenr);
543 if (btrfs_is_leaf(buf)) {
544 btree_space_waste += btrfs_leaf_free_space(root, buf);
545 for (i = 0; i < nritems; i++) {
546 struct btrfs_file_extent_item *fi;
547 btrfs_item_key(buf, &disk_key, i);
548 if (btrfs_disk_key_type(&disk_key) ==
549 BTRFS_EXTENT_ITEM_KEY) {
550 struct btrfs_key found;
551 struct btrfs_extent_item *ei;
552 btrfs_disk_key_to_cpu(&found, &disk_key);
553 ei = btrfs_item_ptr(buf, i,
554 struct btrfs_extent_item);
555 add_extent_rec(extent_cache, NULL, 0,
558 btrfs_extent_refs(buf, ei),
562 if (btrfs_disk_key_type(&disk_key) ==
563 BTRFS_CSUM_ITEM_KEY) {
565 btrfs_item_size_nr(buf, i);
568 if (btrfs_disk_key_type(&disk_key) ==
569 BTRFS_BLOCK_GROUP_ITEM_KEY) {
570 struct btrfs_block_group_item *bi;
571 bi = btrfs_item_ptr(buf, i,
572 struct btrfs_block_group_item);
574 fprintf(stderr,"block group %Lu %Lu used %Lu ",
575 btrfs_disk_key_objectid(disk_key),
576 btrfs_disk_key_offset(disk_key),
577 btrfs_block_group_used(bi));
578 fprintf(stderr, "flags %x\n", bi->flags);
582 if (btrfs_disk_key_type(&disk_key) ==
583 BTRFS_EXTENT_REF_KEY) {
584 ref = btrfs_item_ptr(buf, i,
585 struct btrfs_extent_ref);
587 add_backref(extent_cache,
588 btrfs_disk_key_objectid(&disk_key),
589 btrfs_ref_root(buf, ref),
590 btrfs_ref_generation(buf, ref),
591 btrfs_ref_objectid(buf, ref),
592 btrfs_ref_offset(buf, ref), 0);
595 if (btrfs_disk_key_type(&disk_key) !=
596 BTRFS_EXTENT_DATA_KEY)
598 fi = btrfs_item_ptr(buf, i,
599 struct btrfs_file_extent_item);
600 if (btrfs_file_extent_type(buf, fi) !=
601 BTRFS_FILE_EXTENT_REG)
603 if (btrfs_file_extent_disk_bytenr(buf, fi) == 0)
606 data_bytes_allocated +=
607 btrfs_file_extent_disk_num_bytes(buf, fi);
608 data_bytes_referenced +=
609 btrfs_file_extent_num_bytes(buf, fi);
610 ret = add_extent_rec(extent_cache, NULL, bytenr,
611 btrfs_file_extent_disk_bytenr(buf, fi),
612 btrfs_file_extent_disk_num_bytes(buf, fi),
614 add_backref(extent_cache,
615 btrfs_file_extent_disk_bytenr(buf, fi),
616 btrfs_header_owner(buf),
617 btrfs_header_generation(buf),
618 btrfs_disk_key_objectid(&disk_key),
619 btrfs_disk_key_offset(&disk_key), 1);
624 level = btrfs_header_level(buf);
625 for (i = 0; i < nritems; i++) {
626 u64 ptr = btrfs_node_blockptr(buf, i);
627 u32 size = btrfs_level_size(root, level - 1);
628 btrfs_node_key(buf, &disk_key, i);
629 ret = add_extent_rec(extent_cache,
635 add_backref(extent_cache, ptr,
636 btrfs_header_owner(buf),
637 btrfs_header_generation(buf),
639 btrfs_disk_key_objectid(&disk_key), 1);
642 add_pending(nodes, seen, ptr, size);
644 add_pending(pending, seen, ptr, size);
647 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) -
648 nritems) * sizeof(struct btrfs_key_ptr);
650 total_btree_bytes += buf->len;
651 free_extent_buffer(buf);
655 static int add_root_to_pending(struct extent_buffer *buf,
656 struct block_info *bits,
658 struct cache_tree *extent_cache,
659 struct cache_tree *pending,
660 struct cache_tree *seen,
661 struct cache_tree *reada,
662 struct cache_tree *nodes, u64 root_objectid)
664 if (btrfs_header_level(buf) > 0)
665 add_pending(nodes, seen, buf->start, buf->len);
667 add_pending(pending, seen, buf->start, buf->len);
668 add_extent_rec(extent_cache, NULL, 0, buf->start, buf->len,
671 add_backref(extent_cache, buf->start, root_objectid,
672 btrfs_header_generation(buf),
673 btrfs_header_level(buf), 0, 1);
677 int check_extent_refs(struct btrfs_root *root,
678 struct cache_tree *extent_cache)
680 struct extent_record *rec;
681 struct cache_extent *cache;
685 cache = find_first_cache_extent(extent_cache, 0);
688 rec = container_of(cache, struct extent_record, cache);
689 if (rec->refs != rec->extent_item_refs) {
690 fprintf(stderr, "ref mismatch on [%llu %llu] ",
691 (unsigned long long)rec->start,
692 (unsigned long long)rec->nr);
693 fprintf(stderr, "extent item %u, found %u\n",
694 rec->extent_item_refs,
698 if (all_backpointers_checked(rec, 1)) {
699 fprintf(stderr, "backpointer mismatch on [%llu %llu]\n",
700 (unsigned long long)rec->start,
701 (unsigned long long)rec->nr);
705 remove_cache_extent(extent_cache, cache);
706 free_all_backrefs(rec);
712 int main(int ac, char **av) {
713 struct btrfs_root *root;
714 struct cache_tree extent_cache;
715 struct cache_tree seen;
716 struct cache_tree pending;
717 struct cache_tree reada;
718 struct cache_tree nodes;
719 struct btrfs_path path;
720 struct btrfs_key key;
721 struct btrfs_key found_key;
724 struct block_info *bits;
726 struct extent_buffer *leaf;
728 struct btrfs_root_item ri;
731 cache_tree_init(&extent_cache);
732 cache_tree_init(&seen);
733 cache_tree_init(&pending);
734 cache_tree_init(&nodes);
735 cache_tree_init(&reada);
737 root = open_ctree(av[1], 0);
740 bits = malloc(bits_nr * sizeof(struct block_info));
746 add_root_to_pending(root->fs_info->tree_root->node, bits, bits_nr,
747 &extent_cache, &pending, &seen, &reada, &nodes,
748 root->fs_info->tree_root->root_key.objectid);
750 btrfs_init_path(&path);
753 btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
754 ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
758 leaf = path.nodes[0];
759 slot = path.slots[0];
760 if (slot >= btrfs_header_nritems(path.nodes[0])) {
761 ret = btrfs_next_leaf(root, &path);
764 leaf = path.nodes[0];
765 slot = path.slots[0];
767 btrfs_item_key_to_cpu(leaf, &found_key, path.slots[0]);
768 if (btrfs_key_type(&found_key) == BTRFS_ROOT_ITEM_KEY) {
769 unsigned long offset;
770 struct extent_buffer *buf;
772 offset = btrfs_item_ptr_offset(leaf, path.slots[0]);
773 read_extent_buffer(leaf, &ri, offset, sizeof(ri));
774 buf = read_tree_block(root->fs_info->tree_root,
775 btrfs_root_bytenr(&ri),
776 btrfs_level_size(root,
777 btrfs_root_level(&ri)));
778 add_root_to_pending(buf, bits, bits_nr, &extent_cache,
779 &pending, &seen, &reada, &nodes,
781 free_extent_buffer(buf);
785 btrfs_release_path(root, &path);
787 ret = run_next_block(root, bits, bits_nr, &last, &pending,
788 &seen, &reada, &nodes, &extent_cache);
792 ret = check_extent_refs(root, &extent_cache);
794 printf("found %llu bytes used err is %d\n",
795 (unsigned long long)bytes_used, ret);
796 printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes);
797 printf("total tree bytes: %llu\n",
798 (unsigned long long)total_btree_bytes);
799 printf("btree space waste bytes: %llu\n",
800 (unsigned long long)btree_space_waste);
801 printf("file data blocks allocated: %llu\n referenced %llu\n",
802 (unsigned long long)data_bytes_allocated,
803 (unsigned long long)data_bytes_referenced);