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