btrfs-calc-size.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 #include "kerncompat.h"
  29 #include "ctree.h"
  30 #include "disk-io.h"
  31 #include "print-tree.h"
  32 #include "transaction.h"
  33 #include "list.h"
  34 #include "volumes.h"
  35 #include "utils.h"
  36
  37 static int verbose = 0;
  38 static int no_pretty = 0;
  39
  40 struct seek {
  41         u64 distance;
  42         u64 count;
  43         struct rb_node n;
  44 };
  45
  46 struct root_stats {
  47         u64 total_nodes;
  48         u64 total_leaves;
  49         u64 total_bytes;
  50         u64 total_inline;
  51         u64 total_seeks;
  52         u64 forward_seeks;
  53         u64 backward_seeks;
  54         u64 total_seek_len;
  55         u64 max_seek_len;
  56         u64 total_clusters;
  57         u64 total_cluster_size;
  58         u64 min_cluster_size;
  59         u64 max_cluster_size;
  60         u64 lowest_bytenr;
  61         u64 highest_bytenr;
  62         struct rb_root seek_root;
  63         int total_levels;
  64 };
  65
  66 static int add_seek(struct rb_root *root, u64 dist)
  67 {
  68         struct rb_node **p = &root->rb_node;
  69         struct rb_node *parent = NULL;
  70         struct seek *seek = NULL;
  71
  72         while (*p) {
  73                 parent = *p;
  74                 seek = rb_entry(parent, struct seek, n);
  75
  76                 if (dist < seek->distance) {
  77                         p = &(*p)->rb_left;
  78                 } else if (dist > seek->distance) {
  79                         p = &(*p)->rb_right;
  80                 } else {
  81                         seek->count++;
  82                         return 0;
  83                 }
  84         }
  85
  86         seek = malloc(sizeof(struct seek));
  87         if (!seek)
  88                 return -ENOMEM;
  89         seek->distance = dist;
  90         seek->count = 1;
  91         rb_link_node(&seek->n, parent, p);
  92         rb_insert_color(&seek->n, root);
  93         return 0;
  94 }
  95
  96 static int walk_leaf(struct btrfs_root *root, struct btrfs_path *path,
  97                      struct root_stats *stat, int find_inline)
  98 {
  99         struct extent_buffer *b = path->nodes[0];
 100         struct btrfs_file_extent_item *fi;
 101         struct btrfs_key found_key;
 102         int i;
 103
 104         stat->total_bytes += root->leafsize;
 105         stat->total_leaves++;
 106
 107         if (!find_inline)
 108                 return 0;
 109
 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)
 113                         continue;
 114
 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,
 119                                                         btrfs_item_nr(i));
 120         }
 121
 122         return 0;
 123 }
 124
 125 static u64 calc_distance(u64 block1, u64 block2)
 126 {
 127         if (block1 < block2)
 128                 return block2 - block1;
 129         return block1 - block2;
 130 }
 131
 132 static int walk_nodes(struct btrfs_root *root, struct btrfs_path *path,
 133                       struct root_stats *stat, int level, int find_inline)
 134 {
 135         struct extent_buffer *b = path->nodes[level];
 136         u64 last_block;
 137         u64 cluster_size = root->leafsize;
 138         int i;
 139         int ret = 0;
 140
 141         stat->total_bytes += root->nodesize;
 142         stat->total_nodes++;
 143
 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);
 148
 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));
 157                                 continue;
 158                         }
 159                         path->nodes[level - 1] = tmp;
 160                 }
 161                 if (level - 1)
 162                         ret = walk_nodes(root, path, stat, level - 1,
 163                                          find_inline);
 164                 else
 165                         ret = walk_leaf(root, path, stat, find_inline);
 166                 if (last_block + root->leafsize != cur_blocknr) {
 167                         u64 distance = calc_distance(last_block +
 168                                                      root->leafsize,
 169                                                      cur_blocknr);
 170                         stat->total_seeks++;
 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");
 176                                 ret = -ENOMEM;
 177                                 break;
 178                         }
 179
 180                         if (last_block < cur_blocknr)
 181                                 stat->forward_seeks++;
 182                         else
 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;
 191                         }
 192                         cluster_size = root->leafsize;
 193                 } else {
 194                         cluster_size += root->leafsize;
 195                 }
 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);
 202                 if (ret) {
 203                         fprintf(stderr, "Error walking down path\n");
 204                         break;
 205                 }
 206         }
 207
 208         return ret;
 209 }
 210
 211 static void print_seek_histogram(struct root_stats *stat)
 212 {
 213         struct rb_node *n = rb_first(&stat->seek_root);
 214         struct seek *seek;
 215         u64 tick_interval;
 216         u64 group_start = 0;
 217         u64 group_count = 0;
 218         u64 group_end = 0;
 219         u64 i;
 220         u64 max_seek = stat->max_seek_len;
 221         int digits = 1;
 222
 223         if (stat->total_seeks < 20)
 224                 return;
 225
 226         while ((max_seek /= 10))
 227                 digits++;
 228
 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;
 234
 235                 seek = rb_entry(n, struct seek, n);
 236                 ticks = seek->count / tick_interval;
 237                 if (group_count)
 238                         gticks = group_count / tick_interval;
 239
 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;
 245                         continue;
 246                 }
 247
 248                 if (group_count) {
 249
 250                         gticks = group_count / tick_interval;
 251                         printf("\t\t%*Lu - %*Lu: %*Lu ", digits, group_start,
 252                                digits, group_end, digits, group_count);
 253                         if (gticks) {
 254                                 for (i = 0; i < gticks; i++)
 255                                         printf("#");
 256                                 printf("\n");
 257                         } else {
 258                                 printf("|\n");
 259                         }
 260                         group_count = 0;
 261                 }
 262
 263                 if (ticks <= 2)
 264                         continue;
 265
 266                 printf("\t\t%*Lu - %*Lu: %*Lu ", digits, seek->distance,
 267                        digits, seek->distance, digits, seek->count);
 268                 for (i = 0; i < ticks; i++)
 269                         printf("#");
 270                 printf("\n");
 271         }
 272         if (group_count) {
 273                 u64 gticks;
 274
 275                 gticks = group_count / tick_interval;
 276                 printf("\t\t%*Lu - %*Lu: %*Lu ", digits, group_start,
 277                        digits, group_end, digits, group_count);
 278                 if (gticks) {
 279                         for (i = 0; i < gticks; i++)
 280                                 printf("#");
 281                         printf("\n");
 282                 } else {
 283                         printf("|\n");
 284                 }
 285                 group_count = 0;
 286         }
 287 }
 288
 289 static void timeval_subtract(struct timeval *result,struct timeval *x,
 290                              struct timeval *y)
 291 {
 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;
 295                 y->tv_sec += nsec;
 296         }
 297
 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;
 301                 y->tv_sec -= nsec;
 302         }
 303
 304         result->tv_sec = x->tv_sec - y->tv_sec;
 305         result->tv_usec = x->tv_usec - y->tv_usec;
 306 }
 307
 308 static int calc_root_size(struct btrfs_root *tree_root, struct btrfs_key *key,
 309                           int find_inline)
 310 {
 311         struct btrfs_root *root;
 312         struct btrfs_path *path;
 313         struct rb_node *n;
 314         struct timeval start, end, diff = {0};
 315         struct root_stats stat;
 316         int level;
 317         int ret = 0;
 318         int size_fail = 0;
 319
 320         root = btrfs_read_fs_root(tree_root->fs_info, key);
 321         if (IS_ERR(root)) {
 322                 fprintf(stderr, "Failed to read root %Lu\n", key->objectid);
 323                 return 1;
 324         }
 325
 326         path = btrfs_alloc_path();
 327         if (!path) {
 328                 fprintf(stderr, "Could not allocate path\n");
 329                 return 1;
 330         }
 331
 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);
 341                 goto out;
 342         }
 343         if (!level) {
 344                 ret = walk_leaf(root, path, &stat, find_inline);
 345                 if (ret)
 346                         goto out;
 347                 goto out_print;
 348         }
 349
 350         ret = walk_nodes(root, path, &stat, level, find_inline);
 351         if (ret)
 352                 goto out;
 353         if (gettimeofday(&end, NULL)) {
 354                 fprintf(stderr, "Error getting time: %d\n", errno);
 355                 goto out;
 356         }
 357         timeval_subtract(&diff, &end, &start);
 358 out_print:
 359         if (stat.min_cluster_size == (u64)-1) {
 360                 stat.min_cluster_size = 0;
 361                 stat.total_clusters = 1;
 362         }
 363
 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 -
 379                        stat.lowest_bytenr);
 380                 printf("\tTotal read time: %d s %d us\n", (int)diff.tv_sec,
 381                        (int)diff.tv_usec);
 382                 printf("\tLevels: %d\n", level + 1);
 383         } else {
 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) :
 391                         pretty_size(0));
 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,
 405                        (int)diff.tv_usec);
 406                 printf("\tLevels: %d\n", level + 1);
 407         }
 408 out:
 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);
 412                 free(seek);
 413         }
 414
 415         /*
 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.
 421          */
 422         free(path);
 423         return ret;
 424 }
 425
 426 static void usage(void)
 427 {
 428         fprintf(stderr, "Usage: calc-size [-v] [-b] <device>\n");
 429 }
 430
 431 int main(int argc, char **argv)
 432 {
 433         struct btrfs_key key;
 434         struct btrfs_root *root;
 435         int opt;
 436         int ret = 0;
 437
 438         while ((opt = getopt(argc, argv, "vb")) != -1) {
 439                 switch (opt) {
 440                         case 'v':
 441                                 verbose++;
 442                                 break;
 443                         case 'b':
 444                                 no_pretty = 1;
 445                                 break;
 446                         default:
 447                                 usage();
 448                                 exit(1);
 449                 }
 450         }
 451
 452         set_argv0(argv);
 453         argc = argc - optind;
 454         if (check_argc_min(argc, 1)) {
 455                 usage();
 456                 exit(1);
 457         }
 458
 459         /*
 460         if ((ret = check_mounted(argv[optind])) < 0) {
 461                 fprintf(stderr, "Could not check mount status: %d\n", ret);
 462                 if (ret == -EACCES)
 463                         fprintf(stderr, "Maybe you need to run as root?\n");
 464                 return ret;
 465         } else if (ret) {
 466                 fprintf(stderr, "%s is currently mounted.  Aborting.\n",
 467                         argv[optind]);
 468                 return -EBUSY;
 469         }
 470         */
 471
 472         root = open_ctree(argv[optind], 0, 0);
 473         if (!root) {
 474                 fprintf(stderr, "Couldn't open ctree\n");
 475                 exit(1);
 476         }
 477
 478         printf("Calculating size of root tree\n");
 479         key.objectid = BTRFS_ROOT_TREE_OBJECTID;
 480         ret = calc_root_size(root, &key, 0);
 481         if (ret)
 482                 goto out;
 483
 484         printf("Calculating size of extent tree\n");
 485         key.objectid = BTRFS_EXTENT_TREE_OBJECTID;
 486         ret = calc_root_size(root, &key, 0);
 487         if (ret)
 488                 goto out;
 489
 490         printf("Calculating size of csum tree\n");
 491         key.objectid = BTRFS_CSUM_TREE_OBJECTID;
 492         ret = calc_root_size(root, &key, 0);
 493         if (ret)
 494                 goto out;
 495
 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);
 500         if (ret)
 501                 goto out;
 502 out:
 503         close_ctree(root);
 504         btrfs_close_all_devices();
 505         return ret;
 506 }