1 #define _XOPEN_SOURCE 500
6 #include "kerncompat.h"
7 #include "radix-tree.h"
10 #include "print-tree.h"
11 #include "transaction.h"
12 #include "bit-radix.h"
14 static u64 blocks_used = 0;
15 static u64 total_csum_bytes = 0;
16 static u64 total_btree_blocks = 0;
17 static u64 btree_space_waste = 0;
19 struct extent_record {
20 struct btrfs_disk_key parent_key;
29 static int check_node(struct btrfs_root *root,
30 struct btrfs_disk_key *parent_key,
31 struct btrfs_node *node)
34 u32 nritems = btrfs_header_nritems(&node->header);
36 if (nritems == 0 || nritems > BTRFS_NODEPTRS_PER_BLOCK(root))
38 if (parent_key->flags) {
39 if (memcmp(parent_key, &node->ptrs[0].key,
40 sizeof(struct btrfs_disk_key)))
43 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
44 struct btrfs_key cpukey;
45 btrfs_disk_key_to_cpu(&cpukey, &node->ptrs[i + 1].key);
46 if (btrfs_comp_keys(&node->ptrs[i].key, &cpukey) >= 0)
52 static int check_leaf(struct btrfs_root *root,
53 struct btrfs_disk_key *parent_key,
54 struct btrfs_leaf *leaf)
57 u32 nritems = btrfs_header_nritems(&leaf->header);
59 if (btrfs_header_level(&leaf->header) != 0) {
60 fprintf(stderr, "leaf is not a leaf %llu\n",
61 (unsigned long long)btrfs_header_blocknr(&leaf->header));
64 if (btrfs_leaf_free_space(root, leaf) < 0) {
65 fprintf(stderr, "leaf free space incorrect %llu %d\n",
66 (unsigned long long)btrfs_header_blocknr(&leaf->header),
67 btrfs_leaf_free_space(root, leaf));
74 if (parent_key->flags && memcmp(parent_key, &leaf->items[0].key,
75 sizeof(struct btrfs_disk_key))) {
76 fprintf(stderr, "leaf parent key incorrect %llu\n",
77 (unsigned long long)btrfs_header_blocknr(&leaf->header));
80 for (i = 0; nritems > 1 && i < nritems - 2; i++) {
81 struct btrfs_key cpukey;
82 btrfs_disk_key_to_cpu(&cpukey, &leaf->items[i + 1].key);
83 if (btrfs_comp_keys(&leaf->items[i].key,
86 if (btrfs_item_offset(leaf->items + i) !=
87 btrfs_item_end(leaf->items + i + 1))
90 if (btrfs_item_offset(leaf->items + i) +
91 btrfs_item_size(leaf->items + i) !=
92 BTRFS_LEAF_DATA_SIZE(root))
99 static int maybe_free_extent_rec(struct radix_tree_root *extent_radix,
100 struct extent_record *rec)
102 if (rec->checked && rec->extent_item_refs == rec->refs &&
104 radix_tree_delete(extent_radix, rec->start);
110 static int check_block(struct btrfs_root *root,
111 struct radix_tree_root *extent_radix,
112 struct btrfs_buffer *buf)
114 struct extent_record *rec;
117 rec = radix_tree_lookup(extent_radix, buf->blocknr);
120 if (btrfs_is_leaf(&buf->node)) {
121 ret = check_leaf(root, &rec->parent_key, &buf->leaf);
123 ret = check_node(root, &rec->parent_key, &buf->node);
127 maybe_free_extent_rec(extent_radix, rec);
131 static int add_extent_rec(struct radix_tree_root *extent_radix,
132 struct btrfs_disk_key *parent_key,
133 u64 ref, u64 start, u64 nr, u64 owner,
134 u32 extent_item_refs, int inc_ref, int set_checked)
136 struct extent_record *rec;
138 rec = radix_tree_lookup(extent_radix, start);
142 if (start != rec->start) {
143 fprintf(stderr, "warning, start mismatch %llu %llu\n",
144 (unsigned long long)rec->start,
145 (unsigned long long)start);
148 if (extent_item_refs) {
149 if (rec->extent_item_refs) {
150 fprintf(stderr, "block %llu rec extent_item_refs %u, passed %u\n", (unsigned long long)start, rec->extent_item_refs, extent_item_refs);
152 rec->extent_item_refs = extent_item_refs;
156 maybe_free_extent_rec(extent_radix, rec);
159 rec = malloc(sizeof(*rec));
161 extent_item_refs = 0;
172 if (extent_item_refs)
173 rec->extent_item_refs = extent_item_refs;
175 rec->extent_item_refs = 0;
178 memcpy(&rec->parent_key, parent_key, sizeof(*parent_key));
180 memset(&rec->parent_key, 0, sizeof(*parent_key));
182 ret = radix_tree_insert(extent_radix, start, rec);
190 static int add_pending(struct radix_tree_root *pending,
191 struct radix_tree_root *seen, u64 blocknr)
193 if (test_radix_bit(seen, blocknr))
195 set_radix_bit(pending, blocknr);
196 set_radix_bit(seen, blocknr);
199 static int pick_next_pending(struct radix_tree_root *pending,
200 struct radix_tree_root *reada,
201 struct radix_tree_root *nodes,
202 u64 last, unsigned long *bits, int bits_nr,
205 unsigned long node_start = last;
207 ret = find_first_radix_bit(reada, bits, 0, 1);
215 ret = find_first_radix_bit(nodes, bits, node_start, bits_nr);
217 ret = find_first_radix_bit(nodes, bits, 0, bits_nr);
219 if (bits_nr - ret > 8) {
222 ret2 = find_first_radix_bit(pending, bits + ret,
223 bits[0], bits_nr - ret);
224 sequential = bits[0];
226 if (bits[ret] - sequential > 8)
228 sequential = bits[ret];
235 return find_first_radix_bit(pending, bits, 0, bits_nr);
237 static struct btrfs_buffer reada_buf;
239 static int run_next_block(struct btrfs_root *root,
243 struct radix_tree_root *pending,
244 struct radix_tree_root *seen,
245 struct radix_tree_root *reada,
246 struct radix_tree_root *nodes,
247 struct radix_tree_root *extent_radix)
249 struct btrfs_buffer *buf;
254 struct btrfs_leaf *leaf;
255 struct btrfs_node *node;
256 struct btrfs_disk_key *disk_key;
260 ret = pick_next_pending(pending, reada, nodes, *last, bits,
261 bits_nr, &reada_bits);
266 for(i = 0; i < ret; i++) {
268 set_radix_bit(reada, bits[i]);
269 btrfs_map_bh_to_logical(root, &reada_buf, bits[i]);
270 offset = reada_buf.dev_blocknr * root->blocksize;
271 last_block = bits[i];
272 readahead(reada_buf.fd, offset, root->blocksize);
277 clear_radix_bit(pending, blocknr);
278 clear_radix_bit(reada, blocknr);
279 clear_radix_bit(nodes, blocknr);
280 buf = read_tree_block(root, blocknr);
281 nritems = btrfs_header_nritems(&buf->node.header);
282 ret = check_block(root, extent_radix, buf);
284 fprintf(stderr, "bad block %llu\n",
285 (unsigned long long)blocknr);
287 if (btrfs_is_leaf(&buf->node)) {
289 btree_space_waste += btrfs_leaf_free_space(root, leaf);
290 for (i = 0; i < nritems; i++) {
291 struct btrfs_file_extent_item *fi;
292 disk_key = &leaf->items[i].key;
293 if (btrfs_disk_key_type(disk_key) ==
294 BTRFS_EXTENT_ITEM_KEY) {
295 struct btrfs_key found;
296 struct btrfs_extent_item *ei;
297 btrfs_disk_key_to_cpu(&found,
298 &leaf->items[i].key);
299 ei = btrfs_item_ptr(leaf, i,
300 struct btrfs_extent_item);
301 add_extent_rec(extent_radix, NULL, 0,
304 btrfs_extent_owner(ei),
305 btrfs_extent_refs(ei), 0, 0);
308 if (btrfs_disk_key_type(disk_key) ==
309 BTRFS_CSUM_ITEM_KEY) {
311 btrfs_item_size(leaf->items + i);
314 if (btrfs_disk_key_type(disk_key) ==
315 BTRFS_BLOCK_GROUP_ITEM_KEY) {
316 struct btrfs_block_group_item *bi;
317 bi = btrfs_item_ptr(leaf, i,
318 struct btrfs_block_group_item);
320 fprintf(stderr,"block group %Lu %Lu used %Lu ",
321 btrfs_disk_key_objectid(disk_key),
322 btrfs_disk_key_offset(disk_key),
323 btrfs_block_group_used(bi));
324 fprintf(stderr, "flags %x\n", bi->flags);
328 if (btrfs_disk_key_type(&leaf->items[i].key) !=
329 BTRFS_EXTENT_DATA_KEY)
331 fi = btrfs_item_ptr(leaf, i,
332 struct btrfs_file_extent_item);
333 if (btrfs_file_extent_type(fi) !=
334 BTRFS_FILE_EXTENT_REG)
336 if (btrfs_file_extent_disk_blocknr(fi) == 0)
338 ret = add_extent_rec(extent_radix, NULL, blocknr,
339 btrfs_file_extent_disk_blocknr(fi),
340 btrfs_file_extent_disk_num_blocks(fi),
341 btrfs_disk_key_objectid(&leaf->items[i].key),
348 level = btrfs_header_level(&node->header);
349 for (i = 0; i < nritems; i++) {
350 u64 ptr = btrfs_node_blockptr(node, i);
351 ret = add_extent_rec(extent_radix,
354 btrfs_header_owner(&node->header),
358 add_pending(nodes, seen, ptr);
360 add_pending(pending, seen, ptr);
363 btree_space_waste += (BTRFS_NODEPTRS_PER_BLOCK(root) -
364 nritems) * sizeof(struct btrfs_key_ptr);
366 btrfs_block_release(root, buf);
367 total_btree_blocks++;
371 static int add_root_to_pending(struct btrfs_buffer *buf,
374 struct radix_tree_root *extent_radix,
375 struct radix_tree_root *pending,
376 struct radix_tree_root *seen,
377 struct radix_tree_root *reada,
378 struct radix_tree_root *nodes)
380 if (btrfs_header_level(&buf->node.header) > 0)
381 add_pending(nodes, seen, buf->blocknr);
383 add_pending(pending, seen, buf->blocknr);
384 add_extent_rec(extent_radix, NULL, 0, buf->blocknr, 1,
385 btrfs_header_owner(&buf->node.header), 0, 1, 0);
389 int check_extent_refs(struct btrfs_root *root,
390 struct radix_tree_root *extent_radix)
392 struct extent_record *rec[64];
398 ret = radix_tree_gang_lookup(extent_radix, (void **)rec, 0,
402 for (i = 0; i < ret; i++) {
403 if (rec[i]->refs != rec[i]->extent_item_refs) {
404 fprintf(stderr, "ref mismatch on [%llu %llu] ",
405 (unsigned long long)rec[i]->start,
406 (unsigned long long)rec[i]->nr);
407 fprintf(stderr, "extent item %u, found %u\n",
408 rec[i]->extent_item_refs,
412 radix_tree_delete(extent_radix, rec[i]->start);
419 int main(int ac, char **av) {
420 struct btrfs_super_block super;
421 struct btrfs_root *root;
422 struct radix_tree_root extent_radix;
423 struct radix_tree_root seen;
424 struct radix_tree_root pending;
425 struct radix_tree_root reada;
426 struct radix_tree_root nodes;
427 struct btrfs_path path;
428 struct btrfs_key key;
429 struct btrfs_key found_key;
434 struct btrfs_leaf *leaf;
436 struct btrfs_root_item *ri;
441 INIT_RADIX_TREE(&extent_radix, GFP_NOFS);
442 init_bit_radix(&seen);
443 init_bit_radix(&pending);
444 init_bit_radix(&reada);
445 init_bit_radix(&nodes);
447 root = open_ctree(av[1], &super);
449 bits_nr = 1024 * 1024 / root->blocksize;
450 bits = malloc(bits_nr * sizeof(unsigned long));
456 add_root_to_pending(root->fs_info->tree_root->node, bits, bits_nr,
457 &extent_radix, &pending, &seen, &reada, &nodes);
459 btrfs_init_path(&path);
463 btrfs_set_key_type(&key, BTRFS_ROOT_ITEM_KEY);
464 ret = btrfs_search_slot(NULL, root->fs_info->tree_root,
468 leaf = &path.nodes[0]->leaf;
469 slot = path.slots[0];
470 if (slot >= btrfs_header_nritems(&leaf->header)) {
471 ret = btrfs_next_leaf(root, &path);
474 leaf = &path.nodes[0]->leaf;
475 slot = path.slots[0];
477 btrfs_disk_key_to_cpu(&found_key,
478 &leaf->items[path.slots[0]].key);
479 if (btrfs_key_type(&found_key) == BTRFS_ROOT_ITEM_KEY) {
480 struct btrfs_buffer *buf;
481 ri = btrfs_item_ptr(leaf, path.slots[0],
482 struct btrfs_root_item);
483 buf = read_tree_block(root->fs_info->tree_root,
484 btrfs_root_blocknr(ri));
485 add_root_to_pending(buf, bits, bits_nr, &extent_radix,
486 &pending, &seen, &reada, &nodes);
487 btrfs_block_release(root->fs_info->tree_root, buf);
491 btrfs_release_path(root, &path);
493 ret = run_next_block(root, bits, bits_nr, &last, &pending,
494 &seen, &reada, &nodes, &extent_radix);
498 ret = check_extent_refs(root, &extent_radix);
499 close_ctree(root, &super);
500 printf("found %llu blocks used err is %d\n",
501 (unsigned long long)blocks_used, ret);
502 printf("total csum bytes: %llu\n",(unsigned long long)total_csum_bytes);
503 printf("total tree blocks: %llu\n",
504 (unsigned long long)total_btree_blocks);
505 printf("btree space waste bytes: %llu\n",
506 (unsigned long long)btree_space_waste);