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"
38 static int verbose = 0;
39 static int no_pretty = 0;
58 u64 total_cluster_size;
63 struct rb_root seek_root;
69 struct btrfs_key *snaps;
72 static int add_seek(struct rb_root *root, u64 dist)
74 struct rb_node **p = &root->rb_node;
75 struct rb_node *parent = NULL;
76 struct seek *seek = NULL;
80 seek = rb_entry(parent, struct seek, n);
82 if (dist < seek->distance) {
84 } else if (dist > seek->distance) {
92 seek = malloc(sizeof(struct seek));
95 seek->distance = dist;
97 rb_link_node(&seek->n, parent, p);
98 rb_insert_color(&seek->n, root);
102 static int walk_leaf(struct btrfs_root *root, struct btrfs_path *path,
103 struct root_stats *stat, int find_inline)
105 struct extent_buffer *b = path->nodes[0];
106 struct btrfs_file_extent_item *fi;
107 struct btrfs_key found_key;
110 stat->total_bytes += root->leafsize;
111 stat->total_leaves++;
116 for (i = 0; i < btrfs_header_nritems(b); i++) {
117 btrfs_item_key_to_cpu(b, &found_key, i);
118 if (found_key.type != BTRFS_EXTENT_DATA_KEY)
121 fi = btrfs_item_ptr(b, i, struct btrfs_file_extent_item);
122 if (btrfs_file_extent_type(b, fi) == BTRFS_FILE_EXTENT_INLINE)
123 stat->total_inline +=
124 btrfs_file_extent_inline_item_len(b,
131 static u64 calc_distance(u64 block1, u64 block2)
134 return block2 - block1;
135 return block1 - block2;
138 static int walk_nodes(struct btrfs_root *root, struct btrfs_path *path,
139 struct root_stats *stat, int level, int find_inline)
141 struct extent_buffer *b = path->nodes[level];
143 u64 cluster_size = root->leafsize;
147 stat->total_bytes += root->nodesize;
150 last_block = btrfs_header_bytenr(b);
151 for (i = 0; i < btrfs_header_nritems(b); i++) {
152 struct extent_buffer *tmp = NULL;
153 u64 cur_blocknr = btrfs_node_blockptr(b, i);
155 path->slots[level] = i;
156 if ((level - 1) > 0 || find_inline) {
157 tmp = read_tree_block(root, cur_blocknr,
158 btrfs_level_size(root, level - 1),
159 btrfs_node_ptr_generation(b, i));
161 fprintf(stderr, "Failed to read blocknr %Lu\n",
162 btrfs_node_blockptr(b, i));
165 path->nodes[level - 1] = tmp;
168 ret = walk_nodes(root, path, stat, level - 1,
171 ret = walk_leaf(root, path, stat, find_inline);
172 if (last_block + root->leafsize != cur_blocknr) {
173 u64 distance = calc_distance(last_block +
177 stat->total_seek_len += distance;
178 if (stat->max_seek_len < distance)
179 stat->max_seek_len = distance;
180 if (add_seek(&stat->seek_root, distance)) {
181 fprintf(stderr, "Error adding new seek\n");
186 if (last_block < cur_blocknr)
187 stat->forward_seeks++;
189 stat->backward_seeks++;
190 if (cluster_size != root->leafsize) {
191 stat->total_cluster_size += cluster_size;
192 stat->total_clusters++;
193 if (cluster_size < stat->min_cluster_size)
194 stat->min_cluster_size = cluster_size;
195 if (cluster_size > stat->max_cluster_size)
196 stat->max_cluster_size = cluster_size;
198 cluster_size = root->leafsize;
200 cluster_size += root->leafsize;
202 last_block = cur_blocknr;
203 if (cur_blocknr < stat->lowest_bytenr)
204 stat->lowest_bytenr = cur_blocknr;
205 if (cur_blocknr > stat->highest_bytenr)
206 stat->highest_bytenr = cur_blocknr;
207 free_extent_buffer(tmp);
209 fprintf(stderr, "Error walking down path\n");
217 static void print_seek_histogram(struct root_stats *stat)
219 struct rb_node *n = rb_first(&stat->seek_root);
226 u64 max_seek = stat->max_seek_len;
229 if (stat->total_seeks < 20)
232 while ((max_seek /= 10))
235 /* Make a tick count as 5% of the total seeks */
236 tick_interval = stat->total_seeks / 20;
237 printf("\tSeek histogram\n");
238 for (; n; n = rb_next(n)) {
239 u64 ticks, gticks = 0;
241 seek = rb_entry(n, struct seek, n);
242 ticks = seek->count / tick_interval;
244 gticks = group_count / tick_interval;
246 if (ticks <= 2 && gticks <= 2) {
247 if (group_count == 0)
248 group_start = seek->distance;
249 group_end = seek->distance;
250 group_count += seek->count;
256 gticks = group_count / tick_interval;
257 printf("\t\t%*Lu - %*Lu: %*Lu ", digits, group_start,
258 digits, group_end, digits, group_count);
260 for (i = 0; i < gticks; i++)
272 printf("\t\t%*Lu - %*Lu: %*Lu ", digits, seek->distance,
273 digits, seek->distance, digits, seek->count);
274 for (i = 0; i < ticks; i++)
281 gticks = group_count / tick_interval;
282 printf("\t\t%*Lu - %*Lu: %*Lu ", digits, group_start,
283 digits, group_end, digits, group_count);
285 for (i = 0; i < gticks; i++)
295 static void timeval_subtract(struct timeval *result,struct timeval *x,
298 if (x->tv_usec < y->tv_usec) {
299 int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1;
300 y->tv_usec -= 1000000 * nsec;
304 if (x->tv_usec - y->tv_usec > 1000000) {
305 int nsec = (x->tv_usec - y->tv_usec) / 1000000;
306 y->tv_usec += 1000000 * nsec;
310 result->tv_sec = x->tv_sec - y->tv_sec;
311 result->tv_usec = x->tv_usec - y->tv_usec;
314 static int calc_root_size(struct btrfs_root *tree_root, struct btrfs_key *key,
317 struct btrfs_root *root;
318 struct btrfs_path *path;
320 struct timeval start, end, diff = {0};
321 struct root_stats stat;
326 root = btrfs_read_fs_root(tree_root->fs_info, key);
328 fprintf(stderr, "Failed to read root %Lu\n", key->objectid);
332 path = btrfs_alloc_path();
334 fprintf(stderr, "Could not allocate path\n");
338 memset(&stat, 0, sizeof(stat));
339 level = btrfs_header_level(root->node);
340 stat.lowest_bytenr = btrfs_header_bytenr(root->node);
341 stat.highest_bytenr = stat.lowest_bytenr;
342 stat.min_cluster_size = (u64)-1;
343 stat.max_cluster_size = root->leafsize;
344 path->nodes[level] = root->node;
345 if (gettimeofday(&start, NULL)) {
346 fprintf(stderr, "Error getting time: %d\n", errno);
350 ret = walk_leaf(root, path, &stat, find_inline);
356 ret = walk_nodes(root, path, &stat, level, find_inline);
359 if (gettimeofday(&end, NULL)) {
360 fprintf(stderr, "Error getting time: %d\n", errno);
363 timeval_subtract(&diff, &end, &start);
365 if (stat.min_cluster_size == (u64)-1) {
366 stat.min_cluster_size = 0;
367 stat.total_clusters = 1;
370 if (no_pretty || size_fail) {
371 printf("\tTotal size: %Lu\n", stat.total_bytes);
372 printf("\t\tInline data: %Lu\n", stat.total_inline);
373 printf("\tTotal seeks: %Lu\n", stat.total_seeks);
374 printf("\t\tForward seeks: %Lu\n", stat.forward_seeks);
375 printf("\t\tBackward seeks: %Lu\n", stat.backward_seeks);
376 printf("\t\tAvg seek len: %Lu\n", stat.total_seek_len /
378 print_seek_histogram(&stat);
379 printf("\tTotal clusters: %Lu\n", stat.total_clusters);
380 printf("\t\tAvg cluster size: %Lu\n", stat.total_cluster_size /
381 stat.total_clusters);
382 printf("\t\tMin cluster size: %Lu\n", stat.min_cluster_size);
383 printf("\t\tMax cluster size: %Lu\n", stat.max_cluster_size);
384 printf("\tTotal disk spread: %Lu\n", stat.highest_bytenr -
386 printf("\tTotal read time: %d s %d us\n", (int)diff.tv_sec,
388 printf("\tLevels: %d\n", level + 1);
390 printf("\tTotal size: %s\n", pretty_size(stat.total_bytes));
391 printf("\t\tInline data: %s\n", pretty_size(stat.total_inline));
392 printf("\tTotal seeks: %Lu\n", stat.total_seeks);
393 printf("\t\tForward seeks: %Lu\n", stat.forward_seeks);
394 printf("\t\tBackward seeks: %Lu\n", stat.backward_seeks);
395 printf("\t\tAvg seek len: %s\n", stat.total_seeks ?
396 pretty_size(stat.total_seek_len / stat.total_seeks) :
398 print_seek_histogram(&stat);
399 printf("\tTotal clusters: %Lu\n", stat.total_clusters);
400 printf("\t\tAvg cluster size: %s\n",
401 pretty_size((stat.total_cluster_size /
402 stat.total_clusters)));
403 printf("\t\tMin cluster size: %s\n",
404 pretty_size(stat.min_cluster_size));
405 printf("\t\tMax cluster size: %s\n",
406 pretty_size(stat.max_cluster_size));
407 printf("\tTotal disk spread: %s\n",
408 pretty_size(stat.highest_bytenr -
409 stat.lowest_bytenr));
410 printf("\tTotal read time: %d s %d us\n", (int)diff.tv_sec,
412 printf("\tLevels: %d\n", level + 1);
415 while ((n = rb_first(&stat.seek_root)) != NULL) {
416 struct seek *seek = rb_entry(n, struct seek, n);
417 rb_erase(n, &stat.seek_root);
421 btrfs_free_path(path);
427 fprintf(stderr, "Usage: calc-size [-v] [-b] <device>\n");
430 int main(int argc, char **argv)
432 struct btrfs_key key;
433 struct fs_root *roots;
434 struct btrfs_root *root;
435 size_t fs_roots_size = sizeof(struct fs_root);
439 while ((opt = getopt(argc, argv, "vb")) != -1) {
454 argc = argc - optind;
455 if (check_argc_min(argc, 1)) {
461 if ((ret = check_mounted(argv[optind])) < 0) {
462 fprintf(stderr, "Could not check mount status: %d\n", ret);
464 fprintf(stderr, "Maybe you need to run as root?\n");
467 fprintf(stderr, "%s is currently mounted. Aborting.\n",
473 root = open_ctree(argv[optind], 0, 0);
475 fprintf(stderr, "Couldn't open ctree\n");
479 roots = malloc(fs_roots_size);
481 fprintf(stderr, "No memory\n");
485 printf("Calculating size of root tree\n");
486 key.objectid = BTRFS_ROOT_TREE_OBJECTID;
487 ret = calc_root_size(root, &key, 0);
491 printf("Calculating size of extent tree\n");
492 key.objectid = BTRFS_EXTENT_TREE_OBJECTID;
493 ret = calc_root_size(root, &key, 0);
497 printf("Calculating size of csum tree\n");
498 key.objectid = BTRFS_CSUM_TREE_OBJECTID;
499 ret = calc_root_size(root, &key, 0);
503 roots[0].key.objectid = BTRFS_FS_TREE_OBJECTID;
504 roots[0].key.offset = (u64)-1;
505 printf("Calculatin' size of fs tree\n");
506 ret = calc_root_size(root, &roots[0].key, 1);