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 "help.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->fs_info->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         u32 nodesize = root->fs_info->nodesize;
 140         u64 last_block;
 141         u64 cluster_size = nodesize;
 142         int i;
 143         int ret = 0;
 144
 145         stat->total_bytes += nodesize;
 146         stat->total_nodes++;
 147
 148         last_block = btrfs_header_bytenr(b);
 149         for (i = 0; i < btrfs_header_nritems(b); i++) {
 150                 struct extent_buffer *tmp = NULL;
 151                 u64 cur_blocknr = btrfs_node_blockptr(b, i);
 152
 153                 path->slots[level] = i;
 154                 if ((level - 1) > 0 || find_inline) {
 155                         tmp = read_tree_block(root->fs_info, 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));
 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 + nodesize != cur_blocknr) {
 170                         u64 distance = calc_distance(last_block +
 171                                                      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                                 error("cannot add new seek at distance %llu",
 179                                                 (unsigned long long)distance);
 180                                 ret = -ENOMEM;
 181                                 break;
 182                         }
 183
 184                         if (last_block < cur_blocknr)
 185                                 stat->forward_seeks++;
 186                         else
 187                                 stat->backward_seeks++;
 188                         if (cluster_size != 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;
 195                         }
 196                         cluster_size = nodesize;
 197                 } else {
 198                         cluster_size += nodesize;
 199                 }
 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);
 206                 if (ret) {
 207                         error("walking down path failed: %d",  ret);
 208                         break;
 209                 }
 210         }
 211
 212         return ret;
 213 }
 214
 215 static void print_seek_histogram(struct root_stats *stat)
 216 {
 217         struct rb_node *n = rb_first(&stat->seek_root);
 218         struct seek *seek;
 219         u64 tick_interval;
 220         u64 group_start = 0;
 221         u64 group_count = 0;
 222         u64 group_end = 0;
 223         u64 i;
 224         u64 max_seek = stat->max_seek_len;
 225         int digits = 1;
 226
 227         if (stat->total_seeks < 20)
 228                 return;
 229
 230         while ((max_seek /= 10))
 231                 digits++;
 232
 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;
 238
 239                 seek = rb_entry(n, struct seek, n);
 240                 ticks = seek->count / tick_interval;
 241                 if (group_count)
 242                         gticks = group_count / tick_interval;
 243
 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;
 249                         continue;
 250                 }
 251
 252                 if (group_count) {
 253
 254                         gticks = group_count / tick_interval;
 255                         printf("\t\t%*Lu - %*Lu: %*Lu ", digits, group_start,
 256                                digits, group_end, digits, group_count);
 257                         if (gticks) {
 258                                 for (i = 0; i < gticks; i++)
 259                                         printf("#");
 260                                 printf("\n");
 261                         } else {
 262                                 printf("|\n");
 263                         }
 264                         group_count = 0;
 265                 }
 266
 267                 if (ticks <= 2)
 268                         continue;
 269
 270                 printf("\t\t%*Lu - %*Lu: %*Lu ", digits, seek->distance,
 271                        digits, seek->distance, digits, seek->count);
 272                 for (i = 0; i < ticks; i++)
 273                         printf("#");
 274                 printf("\n");
 275         }
 276         if (group_count) {
 277                 u64 gticks;
 278
 279                 gticks = group_count / tick_interval;
 280                 printf("\t\t%*Lu - %*Lu: %*Lu ", digits, group_start,
 281                        digits, group_end, digits, group_count);
 282                 if (gticks) {
 283                         for (i = 0; i < gticks; i++)
 284                                 printf("#");
 285                         printf("\n");
 286                 } else {
 287                         printf("|\n");
 288                 }
 289                 group_count = 0;
 290         }
 291 }
 292
 293 static void timeval_subtract(struct timeval *result, struct timeval *x,
 294                              struct timeval *y)
 295 {
 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;
 299                 y->tv_sec += nsec;
 300         }
 301
 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;
 305                 y->tv_sec -= nsec;
 306         }
 307
 308         result->tv_sec = x->tv_sec - y->tv_sec;
 309         result->tv_usec = x->tv_usec - y->tv_usec;
 310 }
 311
 312 static int calc_root_size(struct btrfs_root *tree_root, struct btrfs_key *key,
 313                           int find_inline)
 314 {
 315         struct btrfs_root *root;
 316         struct btrfs_path path;
 317         struct rb_node *n;
 318         struct timeval start, end, diff = {0};
 319         struct root_stats stat;
 320         int level;
 321         int ret = 0;
 322         int size_fail = 0;
 323
 324         root = btrfs_read_fs_root(tree_root->fs_info, key);
 325         if (IS_ERR(root)) {
 326                 error("failed to read root %llu", key->objectid);
 327                 return 1;
 328         }
 329
 330         btrfs_init_path(&path);
 331         memset(&stat, 0, sizeof(stat));
 332         level = btrfs_header_level(root->node);
 333         stat.lowest_bytenr = btrfs_header_bytenr(root->node);
 334         stat.highest_bytenr = stat.lowest_bytenr;
 335         stat.min_cluster_size = (u64)-1;
 336         stat.max_cluster_size = root->fs_info->nodesize;
 337         path.nodes[level] = root->node;
 338         if (gettimeofday(&start, NULL)) {
 339                 error("cannot get time: %m");
 340                 goto out;
 341         }
 342         if (!level) {
 343                 ret = walk_leaf(root, &path, &stat, find_inline);
 344                 if (ret)
 345                         goto out;
 346                 goto out_print;
 347         }
 348
 349         ret = walk_nodes(root, &path, &stat, level, find_inline);
 350         if (ret)
 351                 goto out;
 352         if (gettimeofday(&end, NULL)) {
 353                 error("cannot get time: %m");
 354                 goto out;
 355         }
 356         timeval_subtract(&diff, &end, &start);
 357 out_print:
 358         if (stat.min_cluster_size == (u64)-1) {
 359                 stat.min_cluster_size = 0;
 360                 stat.total_clusters = 1;
 361         }
 362
 363         if (no_pretty || size_fail) {
 364                 printf("\tTotal size: %llu\n", stat.total_bytes);
 365                 printf("\t\tInline data: %llu\n", stat.total_inline);
 366                 printf("\tTotal seeks: %llu\n", stat.total_seeks);
 367                 printf("\t\tForward seeks: %llu\n", stat.forward_seeks);
 368                 printf("\t\tBackward seeks: %llu\n", stat.backward_seeks);
 369                 printf("\t\tAvg seek len: %llu\n", stat.total_seeks ?
 370                         stat.total_seek_len / stat.total_seeks : 0);
 371                 print_seek_histogram(&stat);
 372                 printf("\tTotal clusters: %llu\n", stat.total_clusters);
 373                 printf("\t\tAvg cluster size: %llu\n", stat.total_cluster_size /
 374                        stat.total_clusters);
 375                 printf("\t\tMin cluster size: %llu\n", stat.min_cluster_size);
 376                 printf("\t\tMax cluster size: %llu\n", stat.max_cluster_size);
 377                 printf("\tTotal disk spread: %llu\n", stat.highest_bytenr -
 378                        stat.lowest_bytenr);
 379                 printf("\tTotal read time: %d s %d us\n", (int)diff.tv_sec,
 380                        (int)diff.tv_usec);
 381                 printf("\tLevels: %d\n", level + 1);
 382         } else {
 383                 printf("\tTotal size: %s\n", pretty_size(stat.total_bytes));
 384                 printf("\t\tInline data: %s\n", pretty_size(stat.total_inline));
 385                 printf("\tTotal seeks: %llu\n", stat.total_seeks);
 386                 printf("\t\tForward seeks: %llu\n", stat.forward_seeks);
 387                 printf("\t\tBackward seeks: %llu\n", stat.backward_seeks);
 388                 printf("\t\tAvg seek len: %s\n", stat.total_seeks ?
 389                         pretty_size(stat.total_seek_len / stat.total_seeks) :
 390                         pretty_size(0));
 391                 print_seek_histogram(&stat);
 392                 printf("\tTotal clusters: %llu\n", stat.total_clusters);
 393                 printf("\t\tAvg cluster size: %s\n",
 394                                 pretty_size((stat.total_cluster_size /
 395                                                 stat.total_clusters)));
 396                 printf("\t\tMin cluster size: %s\n",
 397                                 pretty_size(stat.min_cluster_size));
 398                 printf("\t\tMax cluster size: %s\n",
 399                                 pretty_size(stat.max_cluster_size));
 400                 printf("\tTotal disk spread: %s\n",
 401                                 pretty_size(stat.highest_bytenr -
 402                                         stat.lowest_bytenr));
 403                 printf("\tTotal read time: %d s %d us\n", (int)diff.tv_sec,
 404                        (int)diff.tv_usec);
 405                 printf("\tLevels: %d\n", level + 1);
 406         }
 407 out:
 408         while ((n = rb_first(&stat.seek_root)) != NULL) {
 409                 struct seek *seek = rb_entry(n, struct seek, n);
 410                 rb_erase(n, &stat.seek_root);
 411                 free(seek);
 412         }
 413
 414         /*
 415          * We only use path to save node data in iterating, without holding
 416          * eb's ref_cnt in path.  Don't use btrfs_release_path() here, it will
 417          * free these eb again, and cause many problems, as negative ref_cnt or
 418          * invalid memory access.
 419          */
 420         return ret;
 421 }
 422
 423 const char * const cmd_inspect_tree_stats_usage[] = {
 424         "btrfs inspect-internal tree-stats [options] <device>",
 425         "Print various stats for trees",
 426         "-b             raw numbers in bytes",
 427         NULL
 428 };
 429
 430 int cmd_inspect_tree_stats(int argc, char **argv)
 431 {
 432         struct btrfs_key key;
 433         struct btrfs_root *root;
 434         int opt;
 435         int ret = 0;
 436
 437         while ((opt = getopt(argc, argv, "vb")) != -1) {
 438                 switch (opt) {
 439                 case 'v':
 440                         verbose++;
 441                         break;
 442                 case 'b':
 443                         no_pretty = 1;
 444                         break;
 445                 default:
 446                         usage(cmd_inspect_tree_stats_usage);
 447                 }
 448         }
 449
 450         if (check_argc_exact(argc - optind, 1)) {
 451                 usage(cmd_inspect_tree_stats_usage);
 452         }
 453
 454         ret = check_mounted(argv[optind]);
 455         if (ret < 0) {
 456                 warning("unable to check mount status of: %s",
 457                                 strerror(-ret));
 458         } else if (ret) {
 459                 warning("%s already mounted, results may be inaccurate",
 460                                 argv[optind]);
 461         }
 462
 463         root = open_ctree(argv[optind], 0, 0);
 464         if (!root) {
 465                 error("cannot open ctree");
 466                 exit(1);
 467         }
 468
 469         printf("Calculating size of root tree\n");
 470         key.objectid = BTRFS_ROOT_TREE_OBJECTID;
 471         ret = calc_root_size(root, &key, 0);
 472         if (ret)
 473                 goto out;
 474
 475         printf("Calculating size of extent tree\n");
 476         key.objectid = BTRFS_EXTENT_TREE_OBJECTID;
 477         ret = calc_root_size(root, &key, 0);
 478         if (ret)
 479                 goto out;
 480
 481         printf("Calculating size of csum tree\n");
 482         key.objectid = BTRFS_CSUM_TREE_OBJECTID;
 483         ret = calc_root_size(root, &key, 0);
 484         if (ret)
 485                 goto out;
 486
 487         key.objectid = BTRFS_FS_TREE_OBJECTID;
 488         key.offset = (u64)-1;
 489         printf("Calculating size of fs tree\n");
 490         ret = calc_root_size(root, &key, 1);
 491         if (ret)
 492                 goto out;
 493 out:
 494         close_ctree(root);
 495         return ret;
 496 }