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;
66 static int add_seek(struct rb_root *root, u64 dist)
68 struct rb_node **p = &root->rb_node;
69 struct rb_node *parent = NULL;
70 struct seek *seek = NULL;
74 seek = rb_entry(parent, struct seek, n);
76 if (dist < seek->distance) {
78 } else if (dist > seek->distance) {
86 seek = malloc(sizeof(struct seek));
89 seek->distance = dist;
91 rb_link_node(&seek->n, parent, p);
92 rb_insert_color(&seek->n, root);
96 static int walk_leaf(struct btrfs_root *root, struct btrfs_path *path,
97 struct root_stats *stat, int find_inline)
99 struct extent_buffer *b = path->nodes[0];
100 struct btrfs_file_extent_item *fi;
101 struct btrfs_key found_key;
104 stat->total_bytes += root->leafsize;
105 stat->total_leaves++;
110 for (i = 0; i < btrfs_header_nritems(b); i++) {
111 btrfs_item_key_to_cpu(b, &found_key, i);
112 if (found_key.type != BTRFS_EXTENT_DATA_KEY)
115 fi = btrfs_item_ptr(b, i, struct btrfs_file_extent_item);
116 if (btrfs_file_extent_type(b, fi) == BTRFS_FILE_EXTENT_INLINE)
117 stat->total_inline +=
118 btrfs_file_extent_inline_item_len(b,
125 static u64 calc_distance(u64 block1, u64 block2)
128 return block2 - block1;
129 return block1 - block2;
132 static int walk_nodes(struct btrfs_root *root, struct btrfs_path *path,
133 struct root_stats *stat, int level, int find_inline)
135 struct extent_buffer *b = path->nodes[level];
137 u64 cluster_size = root->leafsize;
141 stat->total_bytes += root->nodesize;
144 last_block = btrfs_header_bytenr(b);
145 for (i = 0; i < btrfs_header_nritems(b); i++) {
146 struct extent_buffer *tmp = NULL;
147 u64 cur_blocknr = btrfs_node_blockptr(b, i);
149 path->slots[level] = i;
150 if ((level - 1) > 0 || find_inline) {
151 tmp = read_tree_block(root, cur_blocknr,
152 btrfs_level_size(root, level - 1),
153 btrfs_node_ptr_generation(b, i));
154 if (!extent_buffer_uptodate(tmp)) {
155 fprintf(stderr, "Failed to read blocknr %Lu\n",
156 btrfs_node_blockptr(b, i));
159 path->nodes[level - 1] = tmp;
162 ret = walk_nodes(root, path, stat, level - 1,
165 ret = walk_leaf(root, path, stat, find_inline);
166 if (last_block + root->leafsize != cur_blocknr) {
167 u64 distance = calc_distance(last_block +
171 stat->total_seek_len += distance;
172 if (stat->max_seek_len < distance)
173 stat->max_seek_len = distance;
174 if (add_seek(&stat->seek_root, distance)) {
175 fprintf(stderr, "Error adding new seek\n");
180 if (last_block < cur_blocknr)
181 stat->forward_seeks++;
183 stat->backward_seeks++;
184 if (cluster_size != root->leafsize) {
185 stat->total_cluster_size += cluster_size;
186 stat->total_clusters++;
187 if (cluster_size < stat->min_cluster_size)
188 stat->min_cluster_size = cluster_size;
189 if (cluster_size > stat->max_cluster_size)
190 stat->max_cluster_size = cluster_size;
192 cluster_size = root->leafsize;
194 cluster_size += root->leafsize;
196 last_block = cur_blocknr;
197 if (cur_blocknr < stat->lowest_bytenr)
198 stat->lowest_bytenr = cur_blocknr;
199 if (cur_blocknr > stat->highest_bytenr)
200 stat->highest_bytenr = cur_blocknr;
201 free_extent_buffer(tmp);
203 fprintf(stderr, "Error walking down path\n");
211 static void print_seek_histogram(struct root_stats *stat)
213 struct rb_node *n = rb_first(&stat->seek_root);
220 u64 max_seek = stat->max_seek_len;
223 if (stat->total_seeks < 20)
226 while ((max_seek /= 10))
229 /* Make a tick count as 5% of the total seeks */
230 tick_interval = stat->total_seeks / 20;
231 printf("\tSeek histogram\n");
232 for (; n; n = rb_next(n)) {
233 u64 ticks, gticks = 0;
235 seek = rb_entry(n, struct seek, n);
236 ticks = seek->count / tick_interval;
238 gticks = group_count / tick_interval;
240 if (ticks <= 2 && gticks <= 2) {
241 if (group_count == 0)
242 group_start = seek->distance;
243 group_end = seek->distance;
244 group_count += seek->count;
250 gticks = group_count / tick_interval;
251 printf("\t\t%*Lu - %*Lu: %*Lu ", digits, group_start,
252 digits, group_end, digits, group_count);
254 for (i = 0; i < gticks; i++)
266 printf("\t\t%*Lu - %*Lu: %*Lu ", digits, seek->distance,
267 digits, seek->distance, digits, seek->count);
268 for (i = 0; i < ticks; i++)
275 gticks = group_count / tick_interval;
276 printf("\t\t%*Lu - %*Lu: %*Lu ", digits, group_start,
277 digits, group_end, digits, group_count);
279 for (i = 0; i < gticks; i++)
289 static void timeval_subtract(struct timeval *result,struct timeval *x,
292 if (x->tv_usec < y->tv_usec) {
293 int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1;
294 y->tv_usec -= 1000000 * nsec;
298 if (x->tv_usec - y->tv_usec > 1000000) {
299 int nsec = (x->tv_usec - y->tv_usec) / 1000000;
300 y->tv_usec += 1000000 * nsec;
304 result->tv_sec = x->tv_sec - y->tv_sec;
305 result->tv_usec = x->tv_usec - y->tv_usec;
308 static int calc_root_size(struct btrfs_root *tree_root, struct btrfs_key *key,
311 struct btrfs_root *root;
312 struct btrfs_path *path;
314 struct timeval start, end, diff = {0};
315 struct root_stats stat;
320 root = btrfs_read_fs_root(tree_root->fs_info, key);
322 fprintf(stderr, "Failed to read root %Lu\n", key->objectid);
326 path = btrfs_alloc_path();
328 fprintf(stderr, "Could not allocate path\n");
332 memset(&stat, 0, sizeof(stat));
333 level = btrfs_header_level(root->node);
334 stat.lowest_bytenr = btrfs_header_bytenr(root->node);
335 stat.highest_bytenr = stat.lowest_bytenr;
336 stat.min_cluster_size = (u64)-1;
337 stat.max_cluster_size = root->leafsize;
338 path->nodes[level] = root->node;
339 if (gettimeofday(&start, NULL)) {
340 fprintf(stderr, "Error getting time: %d\n", errno);
344 ret = walk_leaf(root, path, &stat, find_inline);
350 ret = walk_nodes(root, path, &stat, level, find_inline);
353 if (gettimeofday(&end, NULL)) {
354 fprintf(stderr, "Error getting time: %d\n", errno);
357 timeval_subtract(&diff, &end, &start);
359 if (stat.min_cluster_size == (u64)-1) {
360 stat.min_cluster_size = 0;
361 stat.total_clusters = 1;
364 if (no_pretty || size_fail) {
365 printf("\tTotal size: %Lu\n", stat.total_bytes);
366 printf("\t\tInline data: %Lu\n", stat.total_inline);
367 printf("\tTotal seeks: %Lu\n", stat.total_seeks);
368 printf("\t\tForward seeks: %Lu\n", stat.forward_seeks);
369 printf("\t\tBackward seeks: %Lu\n", stat.backward_seeks);
370 printf("\t\tAvg seek len: %llu\n", stat.total_seeks ?
371 stat.total_seek_len / stat.total_seeks : 0);
372 print_seek_histogram(&stat);
373 printf("\tTotal clusters: %Lu\n", stat.total_clusters);
374 printf("\t\tAvg cluster size: %Lu\n", stat.total_cluster_size /
375 stat.total_clusters);
376 printf("\t\tMin cluster size: %Lu\n", stat.min_cluster_size);
377 printf("\t\tMax cluster size: %Lu\n", stat.max_cluster_size);
378 printf("\tTotal disk spread: %Lu\n", stat.highest_bytenr -
380 printf("\tTotal read time: %d s %d us\n", (int)diff.tv_sec,
382 printf("\tLevels: %d\n", level + 1);
384 printf("\tTotal size: %s\n", pretty_size(stat.total_bytes));
385 printf("\t\tInline data: %s\n", pretty_size(stat.total_inline));
386 printf("\tTotal seeks: %Lu\n", stat.total_seeks);
387 printf("\t\tForward seeks: %Lu\n", stat.forward_seeks);
388 printf("\t\tBackward seeks: %Lu\n", stat.backward_seeks);
389 printf("\t\tAvg seek len: %s\n", stat.total_seeks ?
390 pretty_size(stat.total_seek_len / stat.total_seeks) :
392 print_seek_histogram(&stat);
393 printf("\tTotal clusters: %Lu\n", stat.total_clusters);
394 printf("\t\tAvg cluster size: %s\n",
395 pretty_size((stat.total_cluster_size /
396 stat.total_clusters)));
397 printf("\t\tMin cluster size: %s\n",
398 pretty_size(stat.min_cluster_size));
399 printf("\t\tMax cluster size: %s\n",
400 pretty_size(stat.max_cluster_size));
401 printf("\tTotal disk spread: %s\n",
402 pretty_size(stat.highest_bytenr -
403 stat.lowest_bytenr));
404 printf("\tTotal read time: %d s %d us\n", (int)diff.tv_sec,
406 printf("\tLevels: %d\n", level + 1);
409 while ((n = rb_first(&stat.seek_root)) != NULL) {
410 struct seek *seek = rb_entry(n, struct seek, n);
411 rb_erase(n, &stat.seek_root);
416 * We only use path to save node data in iterating,
417 * without holding eb's ref_cnt in path.
418 * Don't use btrfs_free_path() here, it will free these
419 * eb again, and cause many problems, as negative ref_cnt
420 * or invalid memory access.
426 static void usage(void)
428 fprintf(stderr, "Usage: calc-size [-v] [-b] <device>\n");
431 int main(int argc, char **argv)
433 struct btrfs_key key;
434 struct btrfs_root *root;
438 while ((opt = getopt(argc, argv, "vb")) != -1) {
453 argc = argc - optind;
454 if (check_argc_min(argc, 1)) {
460 if ((ret = check_mounted(argv[optind])) < 0) {
461 fprintf(stderr, "Could not check mount status: %d\n", ret);
463 fprintf(stderr, "Maybe you need to run as root?\n");
466 fprintf(stderr, "%s is currently mounted. Aborting.\n",
472 root = open_ctree(argv[optind], 0, 0);
474 fprintf(stderr, "Couldn't open ctree\n");
478 printf("Calculating size of root tree\n");
479 key.objectid = BTRFS_ROOT_TREE_OBJECTID;
480 ret = calc_root_size(root, &key, 0);
484 printf("Calculating size of extent tree\n");
485 key.objectid = BTRFS_EXTENT_TREE_OBJECTID;
486 ret = calc_root_size(root, &key, 0);
490 printf("Calculating size of csum tree\n");
491 key.objectid = BTRFS_CSUM_TREE_OBJECTID;
492 ret = calc_root_size(root, &key, 0);
496 key.objectid = BTRFS_FS_TREE_OBJECTID;
497 key.offset = (u64)-1;
498 printf("Calculatin' size of fs tree\n");
499 ret = calc_root_size(root, &key, 1);
504 btrfs_close_all_devices();