2 * Copyright (C) 2011 Red Hat. 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.
26 #include <sys/types.h>
28 #include "kerncompat.h"
31 #include "print-tree.h"
32 #include "transaction.h"
37 static int verbose = 0;
38 static int no_pretty = 0;
57 u64 total_cluster_size;
62 struct rb_root seek_root;
68 struct btrfs_key *snaps;
71 static int add_seek(struct rb_root *root, u64 dist)
73 struct rb_node **p = &root->rb_node;
74 struct rb_node *parent = NULL;
75 struct seek *seek = NULL;
79 seek = rb_entry(parent, struct seek, n);
81 if (dist < seek->distance) {
83 } else if (dist > seek->distance) {
91 seek = malloc(sizeof(struct seek));
94 seek->distance = dist;
96 rb_link_node(&seek->n, parent, p);
97 rb_insert_color(&seek->n, root);
101 static int walk_leaf(struct btrfs_root *root, struct btrfs_path *path,
102 struct root_stats *stat, int find_inline)
104 struct extent_buffer *b = path->nodes[0];
105 struct btrfs_file_extent_item *fi;
106 struct btrfs_key found_key;
109 stat->total_bytes += root->leafsize;
110 stat->total_leaves++;
115 for (i = 0; i < btrfs_header_nritems(b); i++) {
116 btrfs_item_key_to_cpu(b, &found_key, i);
117 if (found_key.type != BTRFS_EXTENT_DATA_KEY)
120 fi = btrfs_item_ptr(b, i, struct btrfs_file_extent_item);
121 if (btrfs_file_extent_type(b, fi) == BTRFS_FILE_EXTENT_INLINE)
122 stat->total_inline +=
123 btrfs_file_extent_inline_item_len(b,
130 static u64 calc_distance(u64 block1, u64 block2)
133 return block2 - block1;
134 return block1 - block2;
137 static int walk_nodes(struct btrfs_root *root, struct btrfs_path *path,
138 struct root_stats *stat, int level, int find_inline)
140 struct extent_buffer *b = path->nodes[level];
142 u64 cluster_size = root->leafsize;
146 stat->total_bytes += root->nodesize;
149 last_block = btrfs_header_bytenr(b);
150 for (i = 0; i < btrfs_header_nritems(b); i++) {
151 struct extent_buffer *tmp = NULL;
152 u64 cur_blocknr = btrfs_node_blockptr(b, i);
154 path->slots[level] = i;
155 if ((level - 1) > 0 || find_inline) {
156 tmp = read_tree_block(root, cur_blocknr,
157 btrfs_level_size(root, level - 1),
158 btrfs_node_ptr_generation(b, i));
159 if (!extent_buffer_uptodate(tmp)) {
160 fprintf(stderr, "Failed to read blocknr %Lu\n",
161 btrfs_node_blockptr(b, i));
164 path->nodes[level - 1] = tmp;
167 ret = walk_nodes(root, path, stat, level - 1,
170 ret = walk_leaf(root, path, stat, find_inline);
171 if (last_block + root->leafsize != cur_blocknr) {
172 u64 distance = calc_distance(last_block +
176 stat->total_seek_len += distance;
177 if (stat->max_seek_len < distance)
178 stat->max_seek_len = distance;
179 if (add_seek(&stat->seek_root, distance)) {
180 fprintf(stderr, "Error adding new seek\n");
185 if (last_block < cur_blocknr)
186 stat->forward_seeks++;
188 stat->backward_seeks++;
189 if (cluster_size != root->leafsize) {
190 stat->total_cluster_size += cluster_size;
191 stat->total_clusters++;
192 if (cluster_size < stat->min_cluster_size)
193 stat->min_cluster_size = cluster_size;
194 if (cluster_size > stat->max_cluster_size)
195 stat->max_cluster_size = cluster_size;
197 cluster_size = root->leafsize;
199 cluster_size += root->leafsize;
201 last_block = cur_blocknr;
202 if (cur_blocknr < stat->lowest_bytenr)
203 stat->lowest_bytenr = cur_blocknr;
204 if (cur_blocknr > stat->highest_bytenr)
205 stat->highest_bytenr = cur_blocknr;
206 free_extent_buffer(tmp);
208 fprintf(stderr, "Error walking down path\n");
216 static void print_seek_histogram(struct root_stats *stat)
218 struct rb_node *n = rb_first(&stat->seek_root);
225 u64 max_seek = stat->max_seek_len;
228 if (stat->total_seeks < 20)
231 while ((max_seek /= 10))
234 /* Make a tick count as 5% of the total seeks */
235 tick_interval = stat->total_seeks / 20;
236 printf("\tSeek histogram\n");
237 for (; n; n = rb_next(n)) {
238 u64 ticks, gticks = 0;
240 seek = rb_entry(n, struct seek, n);
241 ticks = seek->count / tick_interval;
243 gticks = group_count / tick_interval;
245 if (ticks <= 2 && gticks <= 2) {
246 if (group_count == 0)
247 group_start = seek->distance;
248 group_end = seek->distance;
249 group_count += seek->count;
255 gticks = group_count / tick_interval;
256 printf("\t\t%*Lu - %*Lu: %*Lu ", digits, group_start,
257 digits, group_end, digits, group_count);
259 for (i = 0; i < gticks; i++)
271 printf("\t\t%*Lu - %*Lu: %*Lu ", digits, seek->distance,
272 digits, seek->distance, digits, seek->count);
273 for (i = 0; i < ticks; i++)
280 gticks = group_count / tick_interval;
281 printf("\t\t%*Lu - %*Lu: %*Lu ", digits, group_start,
282 digits, group_end, digits, group_count);
284 for (i = 0; i < gticks; i++)
294 static void timeval_subtract(struct timeval *result,struct timeval *x,
297 if (x->tv_usec < y->tv_usec) {
298 int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1;
299 y->tv_usec -= 1000000 * nsec;
303 if (x->tv_usec - y->tv_usec > 1000000) {
304 int nsec = (x->tv_usec - y->tv_usec) / 1000000;
305 y->tv_usec += 1000000 * nsec;
309 result->tv_sec = x->tv_sec - y->tv_sec;
310 result->tv_usec = x->tv_usec - y->tv_usec;
313 static int calc_root_size(struct btrfs_root *tree_root, struct btrfs_key *key,
316 struct btrfs_root *root;
317 struct btrfs_path *path;
319 struct timeval start, end, diff = {0};
320 struct root_stats stat;
325 root = btrfs_read_fs_root(tree_root->fs_info, key);
327 fprintf(stderr, "Failed to read root %Lu\n", key->objectid);
331 path = btrfs_alloc_path();
333 fprintf(stderr, "Could not allocate path\n");
337 memset(&stat, 0, sizeof(stat));
338 level = btrfs_header_level(root->node);
339 stat.lowest_bytenr = btrfs_header_bytenr(root->node);
340 stat.highest_bytenr = stat.lowest_bytenr;
341 stat.min_cluster_size = (u64)-1;
342 stat.max_cluster_size = root->leafsize;
343 path->nodes[level] = root->node;
344 if (gettimeofday(&start, NULL)) {
345 fprintf(stderr, "Error getting time: %d\n", errno);
349 ret = walk_leaf(root, path, &stat, find_inline);
355 ret = walk_nodes(root, path, &stat, level, find_inline);
358 if (gettimeofday(&end, NULL)) {
359 fprintf(stderr, "Error getting time: %d\n", errno);
362 timeval_subtract(&diff, &end, &start);
364 if (stat.min_cluster_size == (u64)-1) {
365 stat.min_cluster_size = 0;
366 stat.total_clusters = 1;
369 if (no_pretty || size_fail) {
370 printf("\tTotal size: %Lu\n", stat.total_bytes);
371 printf("\t\tInline data: %Lu\n", stat.total_inline);
372 printf("\tTotal seeks: %Lu\n", stat.total_seeks);
373 printf("\t\tForward seeks: %Lu\n", stat.forward_seeks);
374 printf("\t\tBackward seeks: %Lu\n", stat.backward_seeks);
375 printf("\t\tAvg seek len: %llu\n", stat.total_seeks ?
376 stat.total_seek_len / stat.total_seeks : 0);
377 print_seek_histogram(&stat);
378 printf("\tTotal clusters: %Lu\n", stat.total_clusters);
379 printf("\t\tAvg cluster size: %Lu\n", stat.total_cluster_size /
380 stat.total_clusters);
381 printf("\t\tMin cluster size: %Lu\n", stat.min_cluster_size);
382 printf("\t\tMax cluster size: %Lu\n", stat.max_cluster_size);
383 printf("\tTotal disk spread: %Lu\n", stat.highest_bytenr -
385 printf("\tTotal read time: %d s %d us\n", (int)diff.tv_sec,
387 printf("\tLevels: %d\n", level + 1);
389 printf("\tTotal size: %s\n", pretty_size(stat.total_bytes));
390 printf("\t\tInline data: %s\n", pretty_size(stat.total_inline));
391 printf("\tTotal seeks: %Lu\n", stat.total_seeks);
392 printf("\t\tForward seeks: %Lu\n", stat.forward_seeks);
393 printf("\t\tBackward seeks: %Lu\n", stat.backward_seeks);
394 printf("\t\tAvg seek len: %s\n", stat.total_seeks ?
395 pretty_size(stat.total_seek_len / stat.total_seeks) :
397 print_seek_histogram(&stat);
398 printf("\tTotal clusters: %Lu\n", stat.total_clusters);
399 printf("\t\tAvg cluster size: %s\n",
400 pretty_size((stat.total_cluster_size /
401 stat.total_clusters)));
402 printf("\t\tMin cluster size: %s\n",
403 pretty_size(stat.min_cluster_size));
404 printf("\t\tMax cluster size: %s\n",
405 pretty_size(stat.max_cluster_size));
406 printf("\tTotal disk spread: %s\n",
407 pretty_size(stat.highest_bytenr -
408 stat.lowest_bytenr));
409 printf("\tTotal read time: %d s %d us\n", (int)diff.tv_sec,
411 printf("\tLevels: %d\n", level + 1);
414 while ((n = rb_first(&stat.seek_root)) != NULL) {
415 struct seek *seek = rb_entry(n, struct seek, n);
416 rb_erase(n, &stat.seek_root);
421 * We only use path to save node data in iterating,
422 * without holding eb's ref_cnt in path.
423 * Don't use btrfs_free_path() here, it will free these
424 * eb again, and cause many problems, as negative ref_cnt
425 * or invalid memory access.
431 static void usage(void)
433 fprintf(stderr, "Usage: calc-size [-v] [-b] <device>\n");
436 int main(int argc, char **argv)
438 struct btrfs_key key;
439 struct fs_root *roots;
440 struct btrfs_root *root;
441 size_t fs_roots_size = sizeof(struct fs_root);
445 while ((opt = getopt(argc, argv, "vb")) != -1) {
460 argc = argc - optind;
461 if (check_argc_min(argc, 1)) {
467 if ((ret = check_mounted(argv[optind])) < 0) {
468 fprintf(stderr, "Could not check mount status: %d\n", ret);
470 fprintf(stderr, "Maybe you need to run as root?\n");
473 fprintf(stderr, "%s is currently mounted. Aborting.\n",
479 root = open_ctree(argv[optind], 0, 0);
481 fprintf(stderr, "Couldn't open ctree\n");
485 roots = malloc(fs_roots_size);
487 fprintf(stderr, "No memory\n");
491 printf("Calculating size of root tree\n");
492 key.objectid = BTRFS_ROOT_TREE_OBJECTID;
493 ret = calc_root_size(root, &key, 0);
497 printf("Calculating size of extent tree\n");
498 key.objectid = BTRFS_EXTENT_TREE_OBJECTID;
499 ret = calc_root_size(root, &key, 0);
503 printf("Calculating size of csum tree\n");
504 key.objectid = BTRFS_CSUM_TREE_OBJECTID;
505 ret = calc_root_size(root, &key, 0);
509 roots[0].key.objectid = BTRFS_FS_TREE_OBJECTID;
510 roots[0].key.offset = (u64)-1;
511 printf("Calculatin' size of fs tree\n");
512 ret = calc_root_size(root, &roots[0].key, 1);
518 btrfs_close_all_devices();