Btrfs-progs: add a bunch of new statistics to btrfs-calc-size

I've been wanting to get back to the allocator and make some changes to try and
fix our fragmenation woes with lots of metadata.  But in order to make these
changes I need to have something to tell me if my changes are making a real
measurable difference.  So this patch adds a bunch of new statistics to
btrfs-calc-size.  It will tell me how long it took to read in the trees, how
many seeks it had (both forward and backward).  It will tell me how far spread
out the tree is and spit out a nice histogram of the seeks.  Here is some sample
output

Calculating size of extent tree
        Total size: 60.74MB
                Inline data: 0.00
        Total seeks: 5020
                Forward seeks: 3691
                Backward seeks: 1329
                Avg seek len: 929.53MB
        Seek histogram
                      4096 -       4096:       1043 ####
                      8192 -      73728:        760 ###
                     81920 -   52527104:        753 ###
                  53518336 -  168009728:        753 ###
                 168591360 -  696045568:        753 ###
                 696238080 - 7560364032:        753 ###
                7560437760 - 8409739264:        178 |
        Total clusters: 1874
                Avg cluster size: 25.17KB
                Min cluster size: 8.00KB
                Max cluster size: 472.00KB
        Total disk spread: 7.90GB
        Total read time: 0 s 341670 us
        Levels: 4

This way we can have good numbers to back up any changes we make to the
allocator.  Thanks,

Signed-off-by: Josef Bacik <jbacik@fusionio.com>
Signed-off-by: David Sterba <dsterba@suse.cz>
Signed-off-by: Chris Mason <chris.mason@fusionio.com>

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;
 }