btrfs-progs: deprecate and stop using btrfs_level_size
[platform/upstream/btrfs-progs.git] / cmds-inspect-tree-stats.c
1 /*
2  * Copyright (C) 2011 Red Hat.  All rights reserved.
3  *
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.
7  *
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.
12  *
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.
17  */
18
19 #include <ctype.h>
20 #include <stdio.h>
21 #include <stdlib.h>
22 #include <unistd.h>
23 #include <fcntl.h>
24 #include <sys/stat.h>
25 #include <sys/time.h>
26 #include <sys/types.h>
27 #include <zlib.h>
28
29 #include "kerncompat.h"
30 #include "ctree.h"
31 #include "disk-io.h"
32 #include "print-tree.h"
33 #include "transaction.h"
34 #include "list.h"
35 #include "volumes.h"
36 #include "utils.h"
37 #include "commands.h"
38 #include "cmds-inspect-tree-stats.h"
39
40 static int verbose = 0;
41 static int no_pretty = 0;
42
43 struct seek {
44         u64 distance;
45         u64 count;
46         struct rb_node n;
47 };
48
49 struct root_stats {
50         u64 total_nodes;
51         u64 total_leaves;
52         u64 total_bytes;
53         u64 total_inline;
54         u64 total_seeks;
55         u64 forward_seeks;
56         u64 backward_seeks;
57         u64 total_seek_len;
58         u64 max_seek_len;
59         u64 total_clusters;
60         u64 total_cluster_size;
61         u64 min_cluster_size;
62         u64 max_cluster_size;
63         u64 lowest_bytenr;
64         u64 highest_bytenr;
65         struct rb_root seek_root;
66         int total_levels;
67 };
68
69 static int add_seek(struct rb_root *root, u64 dist)
70 {
71         struct rb_node **p = &root->rb_node;
72         struct rb_node *parent = NULL;
73         struct seek *seek = NULL;
74
75         while (*p) {
76                 parent = *p;
77                 seek = rb_entry(parent, struct seek, n);
78
79                 if (dist < seek->distance) {
80                         p = &(*p)->rb_left;
81                 } else if (dist > seek->distance) {
82                         p = &(*p)->rb_right;
83                 } else {
84                         seek->count++;
85                         return 0;
86                 }
87         }
88
89         seek = malloc(sizeof(struct seek));
90         if (!seek)
91                 return -ENOMEM;
92         seek->distance = dist;
93         seek->count = 1;
94         rb_link_node(&seek->n, parent, p);
95         rb_insert_color(&seek->n, root);
96         return 0;
97 }
98
99 static int walk_leaf(struct btrfs_root *root, struct btrfs_path *path,
100                      struct root_stats *stat, int find_inline)
101 {
102         struct extent_buffer *b = path->nodes[0];
103         struct btrfs_file_extent_item *fi;
104         struct btrfs_key found_key;
105         int i;
106
107         stat->total_bytes += root->nodesize;
108         stat->total_leaves++;
109
110         if (!find_inline)
111                 return 0;
112
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)
116                         continue;
117
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,
122                                                         btrfs_item_nr(i));
123         }
124
125         return 0;
126 }
127
128 static u64 calc_distance(u64 block1, u64 block2)
129 {
130         if (block1 < block2)
131                 return block2 - block1;
132         return block1 - block2;
133 }
134
135 static int walk_nodes(struct btrfs_root *root, struct btrfs_path *path,
136                       struct root_stats *stat, int level, int find_inline)
137 {
138         struct extent_buffer *b = path->nodes[level];
139         u64 last_block;
140         u64 cluster_size = root->nodesize;
141         int i;
142         int ret = 0;
143
144         stat->total_bytes += root->nodesize;
145         stat->total_nodes++;
146
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);
151
152                 path->slots[level] = i;
153                 if ((level - 1) > 0 || find_inline) {
154                         tmp = read_tree_block(root, cur_blocknr,
155                                               root->nodesize,
156                                               btrfs_node_ptr_generation(b, i));
157                         if (!extent_buffer_uptodate(tmp)) {
158                                 fprintf(stderr, "Failed to read blocknr %llu\n",
159                                         btrfs_node_blockptr(b, i));
160                                 continue;
161                         }
162                         path->nodes[level - 1] = tmp;
163                 }
164                 if (level - 1)
165                         ret = walk_nodes(root, path, stat, level - 1,
166                                          find_inline);
167                 else
168                         ret = walk_leaf(root, path, stat, find_inline);
169                 if (last_block + root->nodesize != cur_blocknr) {
170                         u64 distance = calc_distance(last_block +
171                                                      root->nodesize,
172                                                      cur_blocknr);
173                         stat->total_seeks++;
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                                 fprintf(stderr, "Error adding new seek\n");
179                                 ret = -ENOMEM;
180                                 break;
181                         }
182
183                         if (last_block < cur_blocknr)
184                                 stat->forward_seeks++;
185                         else
186                                 stat->backward_seeks++;
187                         if (cluster_size != root->nodesize) {
188                                 stat->total_cluster_size += cluster_size;
189                                 stat->total_clusters++;
190                                 if (cluster_size < stat->min_cluster_size)
191                                         stat->min_cluster_size = cluster_size;
192                                 if (cluster_size > stat->max_cluster_size)
193                                         stat->max_cluster_size = cluster_size;
194                         }
195                         cluster_size = root->nodesize;
196                 } else {
197                         cluster_size += root->nodesize;
198                 }
199                 last_block = cur_blocknr;
200                 if (cur_blocknr < stat->lowest_bytenr)
201                         stat->lowest_bytenr = cur_blocknr;
202                 if (cur_blocknr > stat->highest_bytenr)
203                         stat->highest_bytenr = cur_blocknr;
204                 free_extent_buffer(tmp);
205                 if (ret) {
206                         fprintf(stderr, "Error walking down path\n");
207                         break;
208                 }
209         }
210
211         return ret;
212 }
213
214 static void print_seek_histogram(struct root_stats *stat)
215 {
216         struct rb_node *n = rb_first(&stat->seek_root);
217         struct seek *seek;
218         u64 tick_interval;
219         u64 group_start = 0;
220         u64 group_count = 0;
221         u64 group_end = 0;
222         u64 i;
223         u64 max_seek = stat->max_seek_len;
224         int digits = 1;
225
226         if (stat->total_seeks < 20)
227                 return;
228
229         while ((max_seek /= 10))
230                 digits++;
231
232         /* Make a tick count as 5% of the total seeks */
233         tick_interval = stat->total_seeks / 20;
234         printf("\tSeek histogram\n");
235         for (; n; n = rb_next(n)) {
236                 u64 ticks, gticks = 0;
237
238                 seek = rb_entry(n, struct seek, n);
239                 ticks = seek->count / tick_interval;
240                 if (group_count)
241                         gticks = group_count / tick_interval;
242
243                 if (ticks <= 2 && gticks <= 2) {
244                         if (group_count == 0)
245                                 group_start = seek->distance;
246                         group_end = seek->distance;
247                         group_count += seek->count;
248                         continue;
249                 }
250
251                 if (group_count) {
252
253                         gticks = group_count / tick_interval;
254                         printf("\t\t%*Lu - %*Lu: %*Lu ", digits, group_start,
255                                digits, group_end, digits, group_count);
256                         if (gticks) {
257                                 for (i = 0; i < gticks; i++)
258                                         printf("#");
259                                 printf("\n");
260                         } else {
261                                 printf("|\n");
262                         }
263                         group_count = 0;
264                 }
265
266                 if (ticks <= 2)
267                         continue;
268
269                 printf("\t\t%*Lu - %*Lu: %*Lu ", digits, seek->distance,
270                        digits, seek->distance, digits, seek->count);
271                 for (i = 0; i < ticks; i++)
272                         printf("#");
273                 printf("\n");
274         }
275         if (group_count) {
276                 u64 gticks;
277
278                 gticks = group_count / tick_interval;
279                 printf("\t\t%*Lu - %*Lu: %*Lu ", digits, group_start,
280                        digits, group_end, digits, group_count);
281                 if (gticks) {
282                         for (i = 0; i < gticks; i++)
283                                 printf("#");
284                         printf("\n");
285                 } else {
286                         printf("|\n");
287                 }
288                 group_count = 0;
289         }
290 }
291
292 static void timeval_subtract(struct timeval *result, struct timeval *x,
293                              struct timeval *y)
294 {
295         if (x->tv_usec < y->tv_usec) {
296                 int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1;
297                 y->tv_usec -= 1000000 * nsec;
298                 y->tv_sec += nsec;
299         }
300
301         if (x->tv_usec - y->tv_usec > 1000000) {
302                 int nsec = (x->tv_usec - y->tv_usec) / 1000000;
303                 y->tv_usec += 1000000 * nsec;
304                 y->tv_sec -= nsec;
305         }
306
307         result->tv_sec = x->tv_sec - y->tv_sec;
308         result->tv_usec = x->tv_usec - y->tv_usec;
309 }
310
311 static int calc_root_size(struct btrfs_root *tree_root, struct btrfs_key *key,
312                           int find_inline)
313 {
314         struct btrfs_root *root;
315         struct btrfs_path *path;
316         struct rb_node *n;
317         struct timeval start, end, diff = {0};
318         struct root_stats stat;
319         int level;
320         int ret = 0;
321         int size_fail = 0;
322
323         root = btrfs_read_fs_root(tree_root->fs_info, key);
324         if (IS_ERR(root)) {
325                 fprintf(stderr, "Failed to read root %llu\n", key->objectid);
326                 return 1;
327         }
328
329         path = btrfs_alloc_path();
330         if (!path) {
331                 fprintf(stderr, "Could not allocate path\n");
332                 return 1;
333         }
334
335         memset(&stat, 0, sizeof(stat));
336         level = btrfs_header_level(root->node);
337         stat.lowest_bytenr = btrfs_header_bytenr(root->node);
338         stat.highest_bytenr = stat.lowest_bytenr;
339         stat.min_cluster_size = (u64)-1;
340         stat.max_cluster_size = root->nodesize;
341         path->nodes[level] = root->node;
342         if (gettimeofday(&start, NULL)) {
343                 fprintf(stderr, "Error getting time: %d\n", errno);
344                 goto out;
345         }
346         if (!level) {
347                 ret = walk_leaf(root, path, &stat, find_inline);
348                 if (ret)
349                         goto out;
350                 goto out_print;
351         }
352
353         ret = walk_nodes(root, path, &stat, level, find_inline);
354         if (ret)
355                 goto out;
356         if (gettimeofday(&end, NULL)) {
357                 fprintf(stderr, "Error getting time: %d\n", errno);
358                 goto out;
359         }
360         timeval_subtract(&diff, &end, &start);
361 out_print:
362         if (stat.min_cluster_size == (u64)-1) {
363                 stat.min_cluster_size = 0;
364                 stat.total_clusters = 1;
365         }
366
367         if (no_pretty || size_fail) {
368                 printf("\tTotal size: %llu\n", stat.total_bytes);
369                 printf("\t\tInline data: %llu\n", stat.total_inline);
370                 printf("\tTotal seeks: %llu\n", stat.total_seeks);
371                 printf("\t\tForward seeks: %llu\n", stat.forward_seeks);
372                 printf("\t\tBackward seeks: %llu\n", stat.backward_seeks);
373                 printf("\t\tAvg seek len: %llu\n", stat.total_seeks ?
374                         stat.total_seek_len / stat.total_seeks : 0);
375                 print_seek_histogram(&stat);
376                 printf("\tTotal clusters: %llu\n", stat.total_clusters);
377                 printf("\t\tAvg cluster size: %llu\n", stat.total_cluster_size /
378                        stat.total_clusters);
379                 printf("\t\tMin cluster size: %llu\n", stat.min_cluster_size);
380                 printf("\t\tMax cluster size: %llu\n", stat.max_cluster_size);
381                 printf("\tTotal disk spread: %llu\n", stat.highest_bytenr -
382                        stat.lowest_bytenr);
383                 printf("\tTotal read time: %d s %d us\n", (int)diff.tv_sec,
384                        (int)diff.tv_usec);
385                 printf("\tLevels: %d\n", level + 1);
386         } else {
387                 printf("\tTotal size: %s\n", pretty_size(stat.total_bytes));
388                 printf("\t\tInline data: %s\n", pretty_size(stat.total_inline));
389                 printf("\tTotal seeks: %llu\n", stat.total_seeks);
390                 printf("\t\tForward seeks: %llu\n", stat.forward_seeks);
391                 printf("\t\tBackward seeks: %llu\n", stat.backward_seeks);
392                 printf("\t\tAvg seek len: %s\n", stat.total_seeks ?
393                         pretty_size(stat.total_seek_len / stat.total_seeks) :
394                         pretty_size(0));
395                 print_seek_histogram(&stat);
396                 printf("\tTotal clusters: %llu\n", stat.total_clusters);
397                 printf("\t\tAvg cluster size: %s\n",
398                                 pretty_size((stat.total_cluster_size /
399                                                 stat.total_clusters)));
400                 printf("\t\tMin cluster size: %s\n",
401                                 pretty_size(stat.min_cluster_size));
402                 printf("\t\tMax cluster size: %s\n",
403                                 pretty_size(stat.max_cluster_size));
404                 printf("\tTotal disk spread: %s\n",
405                                 pretty_size(stat.highest_bytenr -
406                                         stat.lowest_bytenr));
407                 printf("\tTotal read time: %d s %d us\n", (int)diff.tv_sec,
408                        (int)diff.tv_usec);
409                 printf("\tLevels: %d\n", level + 1);
410         }
411 out:
412         while ((n = rb_first(&stat.seek_root)) != NULL) {
413                 struct seek *seek = rb_entry(n, struct seek, n);
414                 rb_erase(n, &stat.seek_root);
415                 free(seek);
416         }
417
418         /*
419          * We only use path to save node data in iterating,
420          * without holding eb's ref_cnt in path.
421          * Don't use btrfs_free_path() here, it will free these
422          * eb again, and cause many problems, as negative ref_cnt
423          * or invalid memory access.
424          */
425         free(path);
426         return ret;
427 }
428
429 const char * const cmd_inspect_tree_stats_usage[] = {
430         "btrfs inspect-internal tree-stats [options] <device>",
431         "Print various stats for trees",
432         "-b             raw numbers in bytes",
433         NULL
434 };
435
436 int cmd_inspect_tree_stats(int argc, char **argv)
437 {
438         struct btrfs_key key;
439         struct btrfs_root *root;
440         int opt;
441         int ret = 0;
442
443         while ((opt = getopt(argc, argv, "vb")) != -1) {
444                 switch (opt) {
445                 case 'v':
446                         verbose++;
447                         break;
448                 case 'b':
449                         no_pretty = 1;
450                         break;
451                 default:
452                         usage(cmd_inspect_tree_stats_usage);
453                 }
454         }
455
456         if (check_argc_exact(argc - optind, 1)) {
457                 usage(cmd_inspect_tree_stats_usage);
458         }
459
460         /*
461         if ((ret = check_mounted(argv[optind])) < 0) {
462                 fprintf(stderr, "Could not check mount status: %d\n", ret);
463                 if (ret == -EACCES)
464                         fprintf(stderr, "Maybe you need to run as root?\n");
465                 return ret;
466         } else if (ret) {
467                 fprintf(stderr, "%s is currently mounted.  Aborting.\n",
468                         argv[optind]);
469                 return -EBUSY;
470         }
471         */
472
473         root = open_ctree(argv[optind], 0, 0);
474         if (!root) {
475                 fprintf(stderr, "Couldn't open ctree\n");
476                 exit(1);
477         }
478
479         printf("Calculating size of root tree\n");
480         key.objectid = BTRFS_ROOT_TREE_OBJECTID;
481         ret = calc_root_size(root, &key, 0);
482         if (ret)
483                 goto out;
484
485         printf("Calculating size of extent tree\n");
486         key.objectid = BTRFS_EXTENT_TREE_OBJECTID;
487         ret = calc_root_size(root, &key, 0);
488         if (ret)
489                 goto out;
490
491         printf("Calculating size of csum tree\n");
492         key.objectid = BTRFS_CSUM_TREE_OBJECTID;
493         ret = calc_root_size(root, &key, 0);
494         if (ret)
495                 goto out;
496
497         key.objectid = BTRFS_FS_TREE_OBJECTID;
498         key.offset = (u64)-1;
499         printf("Calculatin' size of fs tree\n");
500         ret = calc_root_size(root, &key, 1);
501         if (ret)
502                 goto out;
503 out:
504         close_ctree(root);
505         return ret;
506 }