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>
29 #include "kerncompat.h"
32 #include "print-tree.h"
33 #include "transaction.h"
38 #include "cmds-inspect-tree-stats.h"
40 static int verbose = 0;
41 static int no_pretty = 0;
60 u64 total_cluster_size;
65 struct rb_root seek_root;
69 static int add_seek(struct rb_root *root, u64 dist)
71 struct rb_node **p = &root->rb_node;
72 struct rb_node *parent = NULL;
73 struct seek *seek = NULL;
77 seek = rb_entry(parent, struct seek, n);
79 if (dist < seek->distance) {
81 } else if (dist > seek->distance) {
89 seek = malloc(sizeof(struct seek));
92 seek->distance = dist;
94 rb_link_node(&seek->n, parent, p);
95 rb_insert_color(&seek->n, root);
99 static int walk_leaf(struct btrfs_root *root, struct btrfs_path *path,
100 struct root_stats *stat, int find_inline)
102 struct extent_buffer *b = path->nodes[0];
103 struct btrfs_file_extent_item *fi;
104 struct btrfs_key found_key;
107 stat->total_bytes += root->nodesize;
108 stat->total_leaves++;
113 for (i = 0; i < btrfs_header_nritems(b); i++) {
114 btrfs_item_key_to_cpu(b, &found_key, i);
115 if (found_key.type != BTRFS_EXTENT_DATA_KEY)
118 fi = btrfs_item_ptr(b, i, struct btrfs_file_extent_item);
119 if (btrfs_file_extent_type(b, fi) == BTRFS_FILE_EXTENT_INLINE)
120 stat->total_inline +=
121 btrfs_file_extent_inline_item_len(b,
128 static u64 calc_distance(u64 block1, u64 block2)
131 return block2 - block1;
132 return block1 - block2;
135 static int walk_nodes(struct btrfs_root *root, struct btrfs_path *path,
136 struct root_stats *stat, int level, int find_inline)
138 struct extent_buffer *b = path->nodes[level];
140 u64 cluster_size = root->nodesize;
144 stat->total_bytes += root->nodesize;
147 last_block = btrfs_header_bytenr(b);
148 for (i = 0; i < btrfs_header_nritems(b); i++) {
149 struct extent_buffer *tmp = NULL;
150 u64 cur_blocknr = btrfs_node_blockptr(b, i);
152 path->slots[level] = i;
153 if ((level - 1) > 0 || find_inline) {
154 tmp = read_tree_block(root, cur_blocknr,
156 btrfs_node_ptr_generation(b, i));
157 if (!extent_buffer_uptodate(tmp)) {
158 error("failed to read blocknr %llu",
159 btrfs_node_blockptr(b, i));
162 path->nodes[level - 1] = tmp;
165 ret = walk_nodes(root, path, stat, level - 1,
168 ret = walk_leaf(root, path, stat, find_inline);
169 if (last_block + root->nodesize != cur_blocknr) {
170 u64 distance = calc_distance(last_block +
174 stat->total_seek_len += distance;
175 if (stat->max_seek_len < distance)
176 stat->max_seek_len = distance;
177 if (add_seek(&stat->seek_root, distance)) {
178 error("cannot add new seek at distance %llu",
179 (unsigned long long)distance);
184 if (last_block < cur_blocknr)
185 stat->forward_seeks++;
187 stat->backward_seeks++;
188 if (cluster_size != root->nodesize) {
189 stat->total_cluster_size += cluster_size;
190 stat->total_clusters++;
191 if (cluster_size < stat->min_cluster_size)
192 stat->min_cluster_size = cluster_size;
193 if (cluster_size > stat->max_cluster_size)
194 stat->max_cluster_size = cluster_size;
196 cluster_size = root->nodesize;
198 cluster_size += root->nodesize;
200 last_block = cur_blocknr;
201 if (cur_blocknr < stat->lowest_bytenr)
202 stat->lowest_bytenr = cur_blocknr;
203 if (cur_blocknr > stat->highest_bytenr)
204 stat->highest_bytenr = cur_blocknr;
205 free_extent_buffer(tmp);
207 error("walking down path failed: %d", ret);
215 static void print_seek_histogram(struct root_stats *stat)
217 struct rb_node *n = rb_first(&stat->seek_root);
224 u64 max_seek = stat->max_seek_len;
227 if (stat->total_seeks < 20)
230 while ((max_seek /= 10))
233 /* Make a tick count as 5% of the total seeks */
234 tick_interval = stat->total_seeks / 20;
235 printf("\tSeek histogram\n");
236 for (; n; n = rb_next(n)) {
237 u64 ticks, gticks = 0;
239 seek = rb_entry(n, struct seek, n);
240 ticks = seek->count / tick_interval;
242 gticks = group_count / tick_interval;
244 if (ticks <= 2 && gticks <= 2) {
245 if (group_count == 0)
246 group_start = seek->distance;
247 group_end = seek->distance;
248 group_count += seek->count;
254 gticks = group_count / tick_interval;
255 printf("\t\t%*Lu - %*Lu: %*Lu ", digits, group_start,
256 digits, group_end, digits, group_count);
258 for (i = 0; i < gticks; i++)
270 printf("\t\t%*Lu - %*Lu: %*Lu ", digits, seek->distance,
271 digits, seek->distance, digits, seek->count);
272 for (i = 0; i < ticks; i++)
279 gticks = group_count / tick_interval;
280 printf("\t\t%*Lu - %*Lu: %*Lu ", digits, group_start,
281 digits, group_end, digits, group_count);
283 for (i = 0; i < gticks; i++)
293 static void timeval_subtract(struct timeval *result, struct timeval *x,
296 if (x->tv_usec < y->tv_usec) {
297 int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1;
298 y->tv_usec -= 1000000 * nsec;
302 if (x->tv_usec - y->tv_usec > 1000000) {
303 int nsec = (x->tv_usec - y->tv_usec) / 1000000;
304 y->tv_usec += 1000000 * nsec;
308 result->tv_sec = x->tv_sec - y->tv_sec;
309 result->tv_usec = x->tv_usec - y->tv_usec;
312 static int calc_root_size(struct btrfs_root *tree_root, struct btrfs_key *key,
315 struct btrfs_root *root;
316 struct btrfs_path *path;
318 struct timeval start, end, diff = {0};
319 struct root_stats stat;
324 root = btrfs_read_fs_root(tree_root->fs_info, key);
326 error("failed to read root %llu", key->objectid);
330 path = btrfs_alloc_path();
332 error("could not allocate path");
336 memset(&stat, 0, sizeof(stat));
337 level = btrfs_header_level(root->node);
338 stat.lowest_bytenr = btrfs_header_bytenr(root->node);
339 stat.highest_bytenr = stat.lowest_bytenr;
340 stat.min_cluster_size = (u64)-1;
341 stat.max_cluster_size = root->nodesize;
342 path->nodes[level] = root->node;
343 if (gettimeofday(&start, NULL)) {
344 error("cannot get time: %s", strerror(errno));
348 ret = walk_leaf(root, path, &stat, find_inline);
354 ret = walk_nodes(root, path, &stat, level, find_inline);
357 if (gettimeofday(&end, NULL)) {
358 error("cannot get time: %s", strerror(errno));
361 timeval_subtract(&diff, &end, &start);
363 if (stat.min_cluster_size == (u64)-1) {
364 stat.min_cluster_size = 0;
365 stat.total_clusters = 1;
368 if (no_pretty || size_fail) {
369 printf("\tTotal size: %llu\n", stat.total_bytes);
370 printf("\t\tInline data: %llu\n", stat.total_inline);
371 printf("\tTotal seeks: %llu\n", stat.total_seeks);
372 printf("\t\tForward seeks: %llu\n", stat.forward_seeks);
373 printf("\t\tBackward seeks: %llu\n", stat.backward_seeks);
374 printf("\t\tAvg seek len: %llu\n", stat.total_seeks ?
375 stat.total_seek_len / stat.total_seeks : 0);
376 print_seek_histogram(&stat);
377 printf("\tTotal clusters: %llu\n", stat.total_clusters);
378 printf("\t\tAvg cluster size: %llu\n", stat.total_cluster_size /
379 stat.total_clusters);
380 printf("\t\tMin cluster size: %llu\n", stat.min_cluster_size);
381 printf("\t\tMax cluster size: %llu\n", stat.max_cluster_size);
382 printf("\tTotal disk spread: %llu\n", stat.highest_bytenr -
384 printf("\tTotal read time: %d s %d us\n", (int)diff.tv_sec,
386 printf("\tLevels: %d\n", level + 1);
388 printf("\tTotal size: %s\n", pretty_size(stat.total_bytes));
389 printf("\t\tInline data: %s\n", pretty_size(stat.total_inline));
390 printf("\tTotal seeks: %llu\n", stat.total_seeks);
391 printf("\t\tForward seeks: %llu\n", stat.forward_seeks);
392 printf("\t\tBackward seeks: %llu\n", stat.backward_seeks);
393 printf("\t\tAvg seek len: %s\n", stat.total_seeks ?
394 pretty_size(stat.total_seek_len / stat.total_seeks) :
396 print_seek_histogram(&stat);
397 printf("\tTotal clusters: %llu\n", stat.total_clusters);
398 printf("\t\tAvg cluster size: %s\n",
399 pretty_size((stat.total_cluster_size /
400 stat.total_clusters)));
401 printf("\t\tMin cluster size: %s\n",
402 pretty_size(stat.min_cluster_size));
403 printf("\t\tMax cluster size: %s\n",
404 pretty_size(stat.max_cluster_size));
405 printf("\tTotal disk spread: %s\n",
406 pretty_size(stat.highest_bytenr -
407 stat.lowest_bytenr));
408 printf("\tTotal read time: %d s %d us\n", (int)diff.tv_sec,
410 printf("\tLevels: %d\n", level + 1);
413 while ((n = rb_first(&stat.seek_root)) != NULL) {
414 struct seek *seek = rb_entry(n, struct seek, n);
415 rb_erase(n, &stat.seek_root);
420 * We only use path to save node data in iterating,
421 * without holding eb's ref_cnt in path.
422 * Don't use btrfs_free_path() here, it will free these
423 * eb again, and cause many problems, as negative ref_cnt
424 * or invalid memory access.
430 const char * const cmd_inspect_tree_stats_usage[] = {
431 "btrfs inspect-internal tree-stats [options] <device>",
432 "Print various stats for trees",
433 "-b raw numbers in bytes",
437 int cmd_inspect_tree_stats(int argc, char **argv)
439 struct btrfs_key key;
440 struct btrfs_root *root;
444 while ((opt = getopt(argc, argv, "vb")) != -1) {
453 usage(cmd_inspect_tree_stats_usage);
457 if (check_argc_exact(argc - optind, 1)) {
458 usage(cmd_inspect_tree_stats_usage);
461 ret = check_mounted(argv[optind]);
463 warning("unable to check mount status of: %s",
466 warning("%s already mounted, results may be inaccurate",
470 root = open_ctree(argv[optind], 0, 0);
472 error("cannot open ctree");
476 printf("Calculating size of root tree\n");
477 key.objectid = BTRFS_ROOT_TREE_OBJECTID;
478 ret = calc_root_size(root, &key, 0);
482 printf("Calculating size of extent tree\n");
483 key.objectid = BTRFS_EXTENT_TREE_OBJECTID;
484 ret = calc_root_size(root, &key, 0);
488 printf("Calculating size of csum tree\n");
489 key.objectid = BTRFS_CSUM_TREE_OBJECTID;
490 ret = calc_root_size(root, &key, 0);
494 key.objectid = BTRFS_FS_TREE_OBJECTID;
495 key.offset = (u64)-1;
496 printf("Calculating size of fs tree\n");
497 ret = calc_root_size(root, &key, 1);