diff options
| -rw-r--r-- | btrfs-calc-size.c | 271 |
1 files changed, 261 insertions, 10 deletions
diff --git a/btrfs-calc-size.c b/btrfs-calc-size.c index f19155d4..7ae728e2 100644 --- a/btrfs-calc-size.c +++ b/btrfs-calc-size.c @@ -24,6 +24,8 @@ #include <unistd.h> #include <fcntl.h> #include <sys/stat.h> +#include <sys/time.h> +#include <sys/types.h> #include <zlib.h> #include "kerncompat.h" #include "ctree.h" @@ -38,11 +40,29 @@ static int verbose = 0; static int no_pretty = 0; +struct seek { + u64 distance; + u64 count; + struct rb_node n; +}; + struct root_stats { u64 total_nodes; u64 total_leaves; u64 total_bytes; u64 total_inline; + u64 total_seeks; + u64 forward_seeks; + u64 backward_seeks; + u64 total_seek_len; + u64 max_seek_len; + u64 total_clusters; + u64 total_cluster_size; + u64 min_cluster_size; + u64 max_cluster_size; + u64 lowest_bytenr; + u64 highest_bytenr; + struct rb_root seek_root; int total_levels; }; @@ -51,6 +71,36 @@ struct fs_root { struct btrfs_key *snaps; }; +static int add_seek(struct rb_root *root, u64 dist) +{ + struct rb_node **p = &root->rb_node; + struct rb_node *parent = NULL; + struct seek *seek = NULL; + + while (*p) { + parent = *p; + seek = rb_entry(parent, struct seek, n); + + if (dist < seek->distance) { + p = &(*p)->rb_left; + } else if (dist > seek->distance) { + p = &(*p)->rb_right; + } else { + seek->count++; + return 0; + } + } + + seek = malloc(sizeof(struct seek)); + if (!seek) + return -ENOMEM; + seek->distance = dist; + seek->count = 1; + rb_link_node(&seek->n, parent, p); + rb_insert_color(&seek->n, root); + return 0; +} + static int walk_leaf(struct btrfs_root *root, struct btrfs_path *path, struct root_stats *stat, int find_inline) { @@ -80,22 +130,33 @@ static int walk_leaf(struct btrfs_root *root, struct btrfs_path *path, return 0; } +static u64 calc_distance(u64 block1, u64 block2) +{ + if (block1 < block2) + return block2 - block1; + return block1 - block2; +} + static int walk_nodes(struct btrfs_root *root, struct btrfs_path *path, struct root_stats *stat, int level, int find_inline) { struct extent_buffer *b = path->nodes[level]; + u64 last_block; + u64 cluster_size = root->leafsize; int i; int ret = 0; stat->total_bytes += root->nodesize; stat->total_nodes++; + last_block = btrfs_header_bytenr(b); for (i = 0; i < btrfs_header_nritems(b); i++) { struct extent_buffer *tmp = NULL; + u64 cur_blocknr = btrfs_node_blockptr(b, i); path->slots[level] = i; if ((level - 1) > 0 || find_inline) { - tmp = read_tree_block(root, btrfs_node_blockptr(b, i), + tmp = read_tree_block(root, cur_blocknr, btrfs_level_size(root, level - 1), btrfs_node_ptr_generation(b, i)); if (!tmp) { @@ -110,6 +171,41 @@ static int walk_nodes(struct btrfs_root *root, struct btrfs_path *path, find_inline); else ret = walk_leaf(root, path, stat, find_inline); + if (last_block + root->leafsize != cur_blocknr) { + u64 distance = calc_distance(last_block + + root->leafsize, + cur_blocknr); + stat->total_seeks++; + stat->total_seek_len += distance; + if (stat->max_seek_len < distance) + stat->max_seek_len = distance; + if (add_seek(&stat->seek_root, distance)) { + fprintf(stderr, "Error adding new seek\n"); + ret = -ENOMEM; + break; + } + + if (last_block < cur_blocknr) + stat->forward_seeks++; + else + stat->backward_seeks++; + if (cluster_size != root->leafsize) { + stat->total_cluster_size += cluster_size; + stat->total_clusters++; + if (cluster_size < stat->min_cluster_size) + stat->min_cluster_size = cluster_size; + if (cluster_size > stat->max_cluster_size) + stat->max_cluster_size = cluster_size; + } + cluster_size = root->leafsize; + } else { + cluster_size += root->leafsize; + } + last_block = cur_blocknr; + if (cur_blocknr < stat->lowest_bytenr) + stat->lowest_bytenr = cur_blocknr; + if (cur_blocknr > stat->highest_bytenr) + stat->highest_bytenr = cur_blocknr; free_extent_buffer(tmp); if (ret) { fprintf(stderr, "Error walking down path\n"); @@ -120,11 +216,110 @@ static int walk_nodes(struct btrfs_root *root, struct btrfs_path *path, return ret; } +static void print_seek_histogram(struct root_stats *stat) +{ + struct rb_node *n = rb_first(&stat->seek_root); + struct seek *seek; + u64 tick_interval; + u64 group_start; + u64 group_count = 0; + u64 group_end; + u64 i; + u64 max_seek = stat->max_seek_len; + int digits = 1; + + if (stat->total_seeks < 5) + return; + + while ((max_seek /= 10)) + digits++; + + /* Make a tick count as 5% of the total seeks */ + tick_interval = stat->total_seeks / 20; + printf("\tSeek histogram\n"); + for (; n; n = rb_next(n)) { + u64 ticks, gticks = 0; + + seek = rb_entry(n, struct seek, n); + ticks = seek->count / tick_interval; + if (group_count) + gticks = group_count / tick_interval; + + if (ticks <= 2 && gticks <= 2) { + if (group_count == 0) + group_start = seek->distance; + group_end = seek->distance; + group_count += seek->count; + continue; + } + + if (group_count) { + + gticks = group_count / tick_interval; + printf("\t\t%*Lu - %*Lu: %*Lu ", digits, group_start, + digits, group_end, digits, group_count); + if (gticks) { + for (i = 0; i < gticks; i++) + printf("#"); + printf("\n"); + } else { + printf("|\n"); + } + group_count = 0; + } + + if (ticks <= 2) + continue; + + printf("\t\t%*Lu - %*Lu: %*Lu ", digits, seek->distance, + digits, seek->distance, digits, seek->count); + for (i = 0; i < ticks; i++) + printf("#"); + printf("\n"); + } + if (group_count) { + u64 gticks; + + gticks = group_count / tick_interval; + printf("\t\t%*Lu - %*Lu: %*Lu ", digits, group_start, + digits, group_end, digits, group_count); + if (gticks) { + for (i = 0; i < gticks; i++) + printf("#"); + printf("\n"); + } else { + printf("|\n"); + } + group_count = 0; + } +} + +static void timeval_subtract(struct timeval *result,struct timeval *x, + struct timeval *y) +{ + if (x->tv_usec < y->tv_usec) { + int nsec = (y->tv_usec - x->tv_usec) / 1000000 + 1; + y->tv_usec -= 1000000 * nsec; + y->tv_sec += nsec; + } + + if (x->tv_usec - y->tv_usec > 1000000) { + int nsec = (x->tv_usec - y->tv_usec) / 1000000; + y->tv_usec += 1000000 * nsec; + y->tv_sec -= nsec; + } + + result->tv_sec = x->tv_sec - y->tv_sec; + result->tv_usec = x->tv_usec - y->tv_usec; +} + static int calc_root_size(struct btrfs_root *tree_root, struct btrfs_key *key, int find_inline) { struct btrfs_root *root; struct btrfs_path *path; + struct rb_node *n; + struct timeval start, end, diff = {0}; struct root_stats stat; int level; int ret = 0; @@ -144,7 +339,15 @@ static int calc_root_size(struct btrfs_root *tree_root, struct btrfs_key *key, memset(&stat, 0, sizeof(stat)); level = btrfs_header_level(root->node); + stat.lowest_bytenr = btrfs_header_bytenr(root->node); + stat.highest_bytenr = stat.lowest_bytenr; + stat.min_cluster_size = (u64)-1; + stat.max_cluster_size = root->leafsize; path->nodes[level] = root->node; + if (gettimeofday(&start, NULL)) { + fprintf(stderr, "Error getting time: %d\n", errno); + goto out; + } if (!level) { ret = walk_leaf(root, path, &stat, find_inline); if (ret) @@ -155,20 +358,68 @@ static int calc_root_size(struct btrfs_root *tree_root, struct btrfs_key *key, ret = walk_nodes(root, path, &stat, level, find_inline); if (ret) goto out; + if (gettimeofday(&end, NULL)) { + fprintf(stderr, "Error getting time: %d\n", errno); + goto out; + } + timeval_subtract(&diff, &end, &start); out_print: + if (stat.min_cluster_size == (u64)-1) { + stat.min_cluster_size = 0; + stat.total_clusters = 1; + } + if (no_pretty || size_fail) { - printf("\t%Lu total bytes, %Lu inline data bytes, %Lu nodes, " - "%Lu leaves, %d levels\n", stat.total_bytes, - stat.total_inline, stat.total_nodes, stat.total_leaves, - level + 1); + printf("\tTotal size: %Lu\n", stat.total_bytes); + printf("\t\tInline data: %Lu\n", stat.total_inline); + printf("\tTotal seeks: %Lu\n", stat.total_seeks); + printf("\t\tForward seeks: %Lu\n", stat.forward_seeks); + printf("\t\tBackward seeks: %Lu\n", stat.backward_seeks); + printf("\t\tAvg seek len: %Lu\n", stat.total_seek_len / + stat.total_seeks); + print_seek_histogram(&stat); + printf("\tTotal clusters: %Lu\n", stat.total_clusters); + printf("\t\tAvg cluster size: %Lu\n", stat.total_cluster_size / + stat.total_clusters); + printf("\t\tMin cluster size: %Lu\n", stat.min_cluster_size); + printf("\t\tMax cluster size: %Lu\n", stat.max_cluster_size); + printf("\tTotal disk spread: %Lu\n", stat.highest_bytenr - + stat.lowest_bytenr); + printf("\tTotal read time: %d s %d us\n", (int)diff.tv_sec, + (int)diff.tv_usec); + printf("\tLevels: %d\n", level + 1); } else { - printf("\t%s total size, %s inline data, %Lu nodes, " - "%Lu leaves, %d levels\n", - pretty_size(stat.total_bytes), - pretty_size(stat.total_inline), - stat.total_nodes, stat.total_leaves, level + 1); + printf("\tTotal size: %s\n", pretty_size(stat.total_bytes)); + printf("\t\tInline data: %s\n", pretty_size(stat.total_inline)); + printf("\tTotal seeks: %Lu\n", stat.total_seeks); + printf("\t\tForward seeks: %Lu\n", stat.forward_seeks); + printf("\t\tBackward seeks: %Lu\n", stat.backward_seeks); + printf("\t\tAvg seek len: %s\n", stat.total_seeks ? + pretty_size(stat.total_seek_len / stat.total_seeks) : + pretty_size(0)); + print_seek_histogram(&stat); + printf("\tTotal clusters: %Lu\n", stat.total_clusters); + printf("\t\tAvg cluster size: %s\n", + pretty_size((stat.total_cluster_size / + stat.total_clusters))); + printf("\t\tMin cluster size: %s\n", + pretty_size(stat.min_cluster_size)); + printf("\t\tMax cluster size: %s\n", + pretty_size(stat.max_cluster_size)); + printf("\tTotal disk spread: %s\n", + pretty_size(stat.highest_bytenr - + stat.lowest_bytenr)); + printf("\tTotal read time: %d s %d us\n", (int)diff.tv_sec, + (int)diff.tv_usec); + printf("\tLevels: %d\n", level + 1); } out: + while ((n = rb_first(&stat.seek_root)) != NULL) { + struct seek *seek = rb_entry(n, struct seek, n); + rb_erase(n, &stat.seek_root); + free(seek); + } + btrfs_free_path(path); return ret; } |