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"
25 #include "radix-tree.h"
28 #include "print-tree.h"
29 #include "transaction.h"
30 #include "bit-radix.h"
32 static u64 blocks_used = 0;
33 static u64 total_csum_bytes = 0;
34 static u64 total_btree_blocks = 0;
35 static u64 btree_space_waste = 0;
37 struct extent_record {
38 struct btrfs_disk_key parent_key;
47 static int check_node(struct btrfs_root *root,
48 struct btrfs_disk_key *parent_key,
49 struct btrfs_node *node)
52 u32 nritems = btrfs_header_nritems(&node->header);
54 if (nritems == 0 || nritems > BTRFS_NODEPTRS_PER_BLOCK(root))
56 if (parent_key->flags) {
57 if (memcmp(parent_key, &node->ptrs[0].key,
58 sizeof(struct btrfs_disk_key)))
61 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
62 struct btrfs_key cpukey;
63 btrfs_disk_key_to_cpu(&cpukey, &node->ptrs[i + 1].key);
64 if (btrfs_comp_keys(&node->ptrs[i].key, &cpukey) >= 0)
70 static int check_leaf(struct btrfs_root *root,
71 struct btrfs_disk_key *parent_key,
72 struct btrfs_leaf *leaf)
75 u32 nritems = btrfs_header_nritems(&leaf->header);
77 if (btrfs_header_level(&leaf->header) != 0) {
78 fprintf(stderr, "leaf is not a leaf %llu\n",
79 (unsigned long long)btrfs_header_blocknr(&leaf->header));
82 if (btrfs_leaf_free_space(root, leaf) < 0) {
83 fprintf(stderr, "leaf free space incorrect %llu %d\n",
84 (unsigned long long)btrfs_header_blocknr(&leaf->header),
85 btrfs_leaf_free_space(root, leaf));
92 if (parent_key->flags && memcmp(parent_key, &leaf->items[0].key,
93 sizeof(struct btrfs_disk_key))) {
94 fprintf(stderr, "leaf parent key incorrect %llu\n",
95 (unsigned long long)btrfs_header_blocknr(&leaf->header));
98 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
99 struct btrfs_key cpukey;
100 btrfs_disk_key_to_cpu(&cpukey, &leaf->items[i + 1].key);
101 if (btrfs_comp_keys(&leaf->items[i].key,
104 if (btrfs_item_offset(leaf->items + i) !=
105 btrfs_item_end(leaf->items + i + 1))
108 if (btrfs_item_offset(leaf->items + i) +
109 btrfs_item_size(leaf->items + i) !=
110 BTRFS_LEAF_DATA_SIZE(root))
117 static int maybe_free_extent_rec(struct radix_tree_root *extent_radix,
118 struct extent_record *rec)
120 if (rec->checked && rec->extent_item_refs == rec->refs &&
122 radix_tree_delete(extent_radix, rec->start);
128 static int check_block(struct btrfs_root *root,
129 struct radix_tree_root *extent_radix,
130 struct btrfs_buffer *buf)
132 struct extent_record *rec;
135 rec = radix_tree_lookup(extent_radix, buf->blocknr);
138 if (btrfs_is_leaf(&buf->node)) {
139 ret = check_leaf(root, &rec->parent_key, &buf->leaf);
141 ret = check_node(root, &rec->parent_key, &buf->node);
145 maybe_free_extent_rec(extent_radix, rec);
149 static int add_extent_rec(struct radix_tree_root *extent_radix,
150 struct btrfs_disk_key *parent_key,
151 u64 ref, u64 start, u64 nr, u64 owner,
152 u32 extent_item_refs, int inc_ref, int set_checked)
154 struct extent_record *rec;
156 rec = radix_tree_lookup(extent_radix, start);
160 if (start != rec->start) {
161 fprintf(stderr, "warning, start mismatch %llu %llu\n",
162 (unsigned long long)rec->start,
163 (unsigned long long)start);
166 if (extent_item_refs) {
167 if (rec->extent_item_refs) {
168 fprintf(stderr, "block %llu rec extent_item_refs %u, passed %u\n", (unsigned long long)start, rec->extent_item_refs, extent_item_refs);
170 rec->extent_item_refs = extent_item_refs;
174 maybe_free_extent_rec(extent_radix, rec);
177 rec = malloc(sizeof(*rec));
179 extent_item_refs = 0;
190 if (extent_item_refs)
191 rec->extent_item_refs = extent_item_refs;
193 rec->extent_item_refs = 0;
196 memcpy(&rec->parent_key, parent_key, sizeof(*parent_key));
198 memset(&rec->parent_key, 0, sizeof(*parent_key));
200 ret = radix_tree_insert(extent_radix, start, rec);
208 static int add_pending(struct radix_tree_root *pending,
209 struct radix_tree_root *seen, u64 blocknr)
211 if (test_radix_bit(seen, blocknr))
213 set_radix_bit(pending, blocknr);
214 set_radix_bit(seen, blocknr);
217 static int pick_next_pending(struct radix_tree_root *pending,
218 struct radix_tree_root *reada,
219 struct radix_tree_root *nodes,
220 u64 last, unsigned long *bits, int bits_nr,
223 unsigned long node_start = last;
225 ret = find_first_radix_bit(reada, bits, 0, 1);
233 ret = find_first_radix_bit(nodes, bits, node_start, bits_nr);
235 ret = find_first_radix_bit(nodes, bits, 0, bits_nr);
237 if (bits_nr - ret > 8) {
240 ret2 = find_first_radix_bit(pending, bits + ret,
241 bits[0], bits_nr - ret);
242 sequential = bits[0];
244 if (bits[ret] - sequential > 8)
246 sequential = bits[ret];
253 return find_first_radix_bit(pending, bits, 0, bits_nr);
255 static struct btrfs_buffer reada_buf;
257 static int run_next_block(struct btrfs_root *root,
261 struct radix_tree_root *pending,
262 struct radix_tree_root *seen,
263 struct radix_tree_root *reada,
264 struct radix_tree_root *nodes,
265 struct radix_tree_root *extent_radix)
267 struct btrfs_buffer *buf;
272 struct btrfs_leaf *leaf;
273 struct btrfs_node *node;
274 struct btrfs_disk_key *disk_key;
278 ret = pick_next_pending(pending, reada, nodes, *last, bits,
279 bits_nr, &reada_bits);
284 for(i = 0; i < ret; i++) {
286 set_radix_bit(reada, bits[i]);
287 btrfs_map_bh_to_logical(root, &reada_buf, bits[i]);
288 offset = reada_buf.dev_blocknr * root->blocksize;
289 last_block = bits[i];
290 readahead(reada_buf.fd, offset, root->blocksize);
295 clear_radix_bit(pending, blocknr);
296 clear_radix_bit(reada, blocknr);
297 clear_radix_bit(nodes, blocknr);
298 buf = read_tree_block(root, blocknr);
299 nritems = btrfs_header_nritems(&buf->node.header);
300 ret = check_block(root, extent_radix, buf);
302 fprintf(stderr, "bad block %llu\n",
303 (unsigned long long)blocknr);
305 if (btrfs_is_leaf(&buf->node)) {
307 btree_space_waste += btrfs_leaf_free_space(root, leaf);
308 for (i = 0; i < nritems; i++) {
309 struct btrfs_file_extent_item *fi;
310 disk_key = &leaf->items[i].key;
311 if (btrfs_disk_key_type(disk_key) ==
312 BTRFS_EXTENT_ITEM_KEY) {
313 struct btrfs_key found;
314 struct btrfs_extent_item *ei;
315 btrfs_disk_key_to_cpu(&found,
316 &leaf->items[i].key);
317 ei = btrfs_item_ptr(leaf, i,
318 struct btrfs_extent_item);
319 add_extent_rec(extent_radix, NULL, 0,
322 btrfs_extent_owner(ei),
323 btrfs_extent_refs(ei), 0, 0);
326 if (btrfs_disk_key_type(disk_key) ==
327 BTRFS_CSUM_ITEM_KEY) {
329 btrfs_item_size(leaf->items + i);
332 if (btrfs_disk_key_type(disk_key) ==
333 BTRFS_BLOCK_GROUP_ITEM_KEY) {
334 struct btrfs_block_group_item *bi;
335 bi = btrfs_item_ptr(leaf, i,
336 struct btrfs_block_group_item);
338 fprintf(stderr,"block group %Lu %Lu used %Lu ",
339 btrfs_disk_key_objectid(disk_key),
340 btrfs_disk_key_offset(disk_key),
341 btrfs_block_group_used(bi));
342 fprintf(stderr, "flags %x\n", bi->flags);
346 if (btrfs_disk_key_type(&leaf->items[i].key) !=
347 BTRFS_EXTENT_DATA_KEY)
349 fi = btrfs_item_ptr(leaf, i,
350 struct btrfs_file_extent_item);
351 if (btrfs_file_extent_type(fi) !=
352 BTRFS_FILE_EXTENT_REG)
354 if (btrfs_file_extent_disk_blocknr(fi) == 0)
356 ret = add_extent_rec(extent_radix, NULL, blocknr,
357 btrfs_file_extent_disk_blocknr(fi),
358 btrfs_file_extent_disk_num_blocks(fi),
359 btrfs_disk_key_objectid(&leaf->items[i].key),
366 level = btrfs_header_level(&node->header);
367 for (i = 0; i < nritems; i++) {
368 u64 ptr = btrfs_node_blockptr(node, i);
369 ret = add_extent_rec(extent_radix,
372 btrfs_header_owner(&node->header),
376 add_pending(nodes, seen, ptr);
378 add_pending(pending, seen, ptr);
381 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) -
382 nritems) * sizeof(struct btrfs_key_ptr);
384 btrfs_block_release(root, buf);
385 total_btree_blocks++;
389 static int add_root_to_pending(struct btrfs_buffer *buf,
392 struct radix_tree_root *extent_radix,
393 struct radix_tree_root *pending,
394 struct radix_tree_root *seen,
395 struct radix_tree_root *reada,
396 struct radix_tree_root *nodes)
398 if (btrfs_header_level(&buf->node.header) > 0)
399 add_pending(nodes, seen, buf->blocknr);
401 add_pending(pending, seen, buf->blocknr);
402 add_extent_rec(extent_radix, NULL, 0, buf->blocknr, 1,
403 btrfs_header_owner(&buf->node.header), 0, 1, 0);
407 int check_extent_refs(struct btrfs_root *root,
408 struct radix_tree_root *extent_radix)
410 struct extent_record *rec[64];
416 ret = radix_tree_gang_lookup(extent_radix, (void **)rec, 0,
420 for (i = 0; i < ret; i++) {
421 if (rec[i]->refs != rec[i]->extent_item_refs) {
422 fprintf(stderr, "ref mismatch on [%llu %llu] ",
423 (unsigned long long)rec[i]->start,
424 (unsigned long long)rec[i]->nr);
425 fprintf(stderr, "extent item %u, found %u\n",
426 rec[i]->extent_item_refs,
430 radix_tree_delete(extent_radix, rec[i]->start);
437 int main(int ac, char **av) {
438 struct btrfs_super_block super;
439 struct btrfs_root *root;
440 struct radix_tree_root extent_radix;
441 struct radix_tree_root seen;
442 struct radix_tree_root pending;
443 struct radix_tree_root reada;
444 struct radix_tree_root nodes;
445 struct btrfs_path path;
446 struct btrfs_key key;
447 struct btrfs_key found_key;
452 struct btrfs_leaf *leaf;
454 struct btrfs_root_item *ri;
459 INIT_RADIX_TREE(&extent_radix, GFP_NOFS);
460 init_bit_radix(&seen);
461 init_bit_radix(&pending);
462 init_bit_radix(&reada);
463 init_bit_radix(&nodes);
465 root = open_ctree(av[1], &super);
467 bits_nr = 1024 * 1024 / root->blocksize;
468 bits = malloc(bits_nr * sizeof(unsigned long));
474 add_root_to_pending(root->fs_info->tree_root->node, bits, bits_nr,
475 &extent_radix, &pending, &seen, &reada, &nodes);
477 btrfs_init_path(&path);
481 btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
482 ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
486 leaf = &path.nodes[0]->leaf;
487 slot = path.slots[0];
488 if (slot >= btrfs_header_nritems(&leaf->header)) {
489 ret = btrfs_next_leaf(root, &path);
492 leaf = &path.nodes[0]->leaf;
493 slot = path.slots[0];
495 btrfs_disk_key_to_cpu(&found_key,
496 &leaf->items[path.slots[0]].key);
497 if (btrfs_key_type(&found_key) == BTRFS_ROOT_ITEM_KEY) {
498 struct btrfs_buffer *buf;
499 ri = btrfs_item_ptr(leaf, path.slots[0],
500 struct btrfs_root_item);
501 buf = read_tree_block(root->fs_info->tree_root,
502 btrfs_root_blocknr(ri));
503 add_root_to_pending(buf, bits, bits_nr, &extent_radix,
504 &pending, &seen, &reada, &nodes);
505 btrfs_block_release(root->fs_info->tree_root, buf);
509 btrfs_release_path(root, &path);
511 ret = run_next_block(root, bits, bits_nr, &last, &pending,
512 &seen, &reada, &nodes, &extent_radix);
516 ret = check_extent_refs(root, &extent_radix);
517 close_ctree(root, &super);
518 printf("found %llu blocks used err is %d\n",
519 (unsigned long long)blocks_used, ret);
520 printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes);
521 printf("total tree blocks: %llu\n",
522 (unsigned long long)total_btree_blocks);
523 printf("btree space waste bytes: %llu\n",
524 (unsigned long long)btree_space_waste);