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"
41 static int verbose = 0;
42 static int no_pretty = 0;
61 u64 total_cluster_size;
66 struct rb_root seek_root;
70 static int add_seek(struct rb_root *root, u64 dist)
72 struct rb_node **p = &root->rb_node;
73 struct rb_node *parent = NULL;
74 struct seek *seek = NULL;
78 seek = rb_entry(parent, struct seek, n);
80 if (dist < seek->distance) {
82 } else if (dist > seek->distance) {
90 seek = malloc(sizeof(struct seek));
93 seek->distance = dist;
95 rb_link_node(&seek->n, parent, p);
96 rb_insert_color(&seek->n, root);
100 static int walk_leaf(struct btrfs_root *root, struct btrfs_path *path,
101 struct root_stats *stat, int find_inline)
103 struct extent_buffer *b = path->nodes[0];
104 struct btrfs_file_extent_item *fi;
105 struct btrfs_key found_key;
108 stat->total_bytes += root->fs_info->nodesize;
109 stat->total_leaves++;
114 for (i = 0; i < btrfs_header_nritems(b); i++) {
115 btrfs_item_key_to_cpu(b, &found_key, i);
116 if (found_key.type != BTRFS_EXTENT_DATA_KEY)
119 fi = btrfs_item_ptr(b, i, struct btrfs_file_extent_item);
120 if (btrfs_file_extent_type(b, fi) == BTRFS_FILE_EXTENT_INLINE)
121 stat->total_inline +=
122 btrfs_file_extent_inline_item_len(b,
129 static u64 calc_distance(u64 block1, u64 block2)
132 return block2 - block1;
133 return block1 - block2;
136 static int walk_nodes(struct btrfs_root *root, struct btrfs_path *path,
137 struct root_stats *stat, int level, int find_inline)
139 struct extent_buffer *b = path->nodes[level];
140 u32 nodesize = root->fs_info->nodesize;
142 u64 cluster_size = nodesize;
146 stat->total_bytes += 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,
158 btrfs_node_ptr_generation(b, i));
159 if (!extent_buffer_uptodate(tmp)) {
160 error("failed to read blocknr %llu",
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 + nodesize != 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 error("cannot add new seek at distance %llu",
181 (unsigned long long)distance);
186 if (last_block < cur_blocknr)
187 stat->forward_seeks++;
189 stat->backward_seeks++;
190 if (cluster_size != nodesize) {
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 = nodesize;
200 cluster_size += nodesize;
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 error("walking down path failed: %d", ret);
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 error("failed to read root %llu", key->objectid);
332 btrfs_init_path(&path);
333 memset(&stat, 0, sizeof(stat));
334 level = btrfs_header_level(root->node);
335 stat.lowest_bytenr = btrfs_header_bytenr(root->node);
336 stat.highest_bytenr = stat.lowest_bytenr;
337 stat.min_cluster_size = (u64)-1;
338 stat.max_cluster_size = root->fs_info->nodesize;
339 path.nodes[level] = root->node;
340 if (gettimeofday(&start, NULL)) {
341 error("cannot get time: %s", strerror(errno));
345 ret = walk_leaf(root, &path, &stat, find_inline);
351 ret = walk_nodes(root, &path, &stat, level, find_inline);
354 if (gettimeofday(&end, NULL)) {
355 error("cannot get time: %s", strerror(errno));
358 timeval_subtract(&diff, &end, &start);
360 if (stat.min_cluster_size == (u64)-1) {
361 stat.min_cluster_size = 0;
362 stat.total_clusters = 1;
365 if (no_pretty || size_fail) {
366 printf("\tTotal size: %llu\n", stat.total_bytes);
367 printf("\t\tInline data: %llu\n", stat.total_inline);
368 printf("\tTotal seeks: %llu\n", stat.total_seeks);
369 printf("\t\tForward seeks: %llu\n", stat.forward_seeks);
370 printf("\t\tBackward seeks: %llu\n", stat.backward_seeks);
371 printf("\t\tAvg seek len: %llu\n", stat.total_seeks ?
372 stat.total_seek_len / stat.total_seeks : 0);
373 print_seek_histogram(&stat);
374 printf("\tTotal clusters: %llu\n", stat.total_clusters);
375 printf("\t\tAvg cluster size: %llu\n", stat.total_cluster_size /
376 stat.total_clusters);
377 printf("\t\tMin cluster size: %llu\n", stat.min_cluster_size);
378 printf("\t\tMax cluster size: %llu\n", stat.max_cluster_size);
379 printf("\tTotal disk spread: %llu\n", stat.highest_bytenr -
381 printf("\tTotal read time: %d s %d us\n", (int)diff.tv_sec,
383 printf("\tLevels: %d\n", level + 1);
385 printf("\tTotal size: %s\n", pretty_size(stat.total_bytes));
386 printf("\t\tInline data: %s\n", pretty_size(stat.total_inline));
387 printf("\tTotal seeks: %llu\n", stat.total_seeks);
388 printf("\t\tForward seeks: %llu\n", stat.forward_seeks);
389 printf("\t\tBackward seeks: %llu\n", stat.backward_seeks);
390 printf("\t\tAvg seek len: %s\n", stat.total_seeks ?
391 pretty_size(stat.total_seek_len / stat.total_seeks) :
393 print_seek_histogram(&stat);
394 printf("\tTotal clusters: %llu\n", stat.total_clusters);
395 printf("\t\tAvg cluster size: %s\n",
396 pretty_size((stat.total_cluster_size /
397 stat.total_clusters)));
398 printf("\t\tMin cluster size: %s\n",
399 pretty_size(stat.min_cluster_size));
400 printf("\t\tMax cluster size: %s\n",
401 pretty_size(stat.max_cluster_size));
402 printf("\tTotal disk spread: %s\n",
403 pretty_size(stat.highest_bytenr -
404 stat.lowest_bytenr));
405 printf("\tTotal read time: %d s %d us\n", (int)diff.tv_sec,
407 printf("\tLevels: %d\n", level + 1);
410 while ((n = rb_first(&stat.seek_root)) != NULL) {
411 struct seek *seek = rb_entry(n, struct seek, n);
412 rb_erase(n, &stat.seek_root);
417 * We only use path to save node data in iterating, without holding
418 * eb's ref_cnt in path. Don't use btrfs_release_path() here, it will
419 * free these eb again, and cause many problems, as negative ref_cnt or
420 * invalid memory access.
425 const char * const cmd_inspect_tree_stats_usage[] = {
426 "btrfs inspect-internal tree-stats [options] <device>",
427 "Print various stats for trees",
428 "-b raw numbers in bytes",
432 int cmd_inspect_tree_stats(int argc, char **argv)
434 struct btrfs_key key;
435 struct btrfs_root *root;
439 while ((opt = getopt(argc, argv, "vb")) != -1) {
448 usage(cmd_inspect_tree_stats_usage);
452 if (check_argc_exact(argc - optind, 1)) {
453 usage(cmd_inspect_tree_stats_usage);
456 ret = check_mounted(argv[optind]);
458 warning("unable to check mount status of: %s",
461 warning("%s already mounted, results may be inaccurate",
465 root = open_ctree(argv[optind], 0, 0);
467 error("cannot open ctree");
471 printf("Calculating size of root tree\n");
472 key.objectid = BTRFS_ROOT_TREE_OBJECTID;
473 ret = calc_root_size(root, &key, 0);
477 printf("Calculating size of extent tree\n");
478 key.objectid = BTRFS_EXTENT_TREE_OBJECTID;
479 ret = calc_root_size(root, &key, 0);
483 printf("Calculating size of csum tree\n");
484 key.objectid = BTRFS_CSUM_TREE_OBJECTID;
485 ret = calc_root_size(root, &key, 0);
489 key.objectid = BTRFS_FS_TREE_OBJECTID;
490 key.offset = (u64)-1;
491 printf("Calculating size of fs tree\n");
492 ret = calc_root_size(root, &key, 1);