[PATCH 1/2] btrfs-progs: copy btrfs-calc-size to inspect-internal tree-stats

[PATCH 1/2] btrfs-progs: copy btrfs-calc-size to inspect-internal tree-stats

[Alexander Fougner]

Signed-off-by: Alexander Fougner <fougner89@gmail.com>
---
 Makefile.in               |   3 +-
 btrfs-calc-size.c         | 482 +------------------------------------------
 cmds-inspect-tree-stats.c | 506 ++++++++++++++++++++++++++++++++++++++++++++++
 cmds-inspect-tree-stats.h |  26 +++
 cmds-inspect.c            |   5 +-
 5 files changed, 545 insertions(+), 477 deletions(-)
 create mode 100644 cmds-inspect-tree-stats.c
 create mode 100644 cmds-inspect-tree-stats.h

diff --git a/Makefile.in b/Makefile.in
index dd30686..a179a36 100644
--- a/Makefile.in
+++ b/Makefile.in
@@ -76,7 +76,7 @@ cmds_objects = cmds-subvolume.o cmds-filesystem.o cmds-device.o cmds-scrub.o \
 	       cmds-quota.o cmds-qgroup.o cmds-replace.o cmds-check.o \
 	       cmds-restore.o cmds-rescue.o chunk-recover.o super-recover.o \
 	       cmds-property.o cmds-fi-usage.o cmds-inspect-dump-tree.o \
-	       cmds-inspect-dump-super.o cmds-fi-du.o
+	       cmds-inspect-dump-super.o cmds-inspect-tree-stats.o cmds-fi-du.o
 libbtrfs_objects = send-stream.o send-utils.o rbtree.o btrfs-list.o crc32c.o \
 		   uuid-tree.o utils-lib.o rbtree-utils.o
 libbtrfs_headers = send-stream.h send-utils.h send.h rbtree.h btrfs-list.h \
@@ -128,6 +128,7 @@ btrfs_convert_libs = @EXT2FS_LIBS@ @COM_ERR_LIBS@
 btrfs_fragments_libs = -lgd -lpng -ljpeg -lfreetype
 btrfs_debug_tree_objects = cmds-inspect-dump-tree.o
 btrfs_show_super_objects = cmds-inspect-dump-super.o
+btrfs_calc_size_objects = cmds-inspect-tree-stats.o
 
 SUBDIRS =
 BUILDDIRS = $(patsubst %,build-%,$(SUBDIRS))
diff --git a/btrfs-calc-size.c b/btrfs-calc-size.c
index 45fb510..2d29901 100644
--- a/btrfs-calc-size.c
+++ b/btrfs-calc-size.c
@@ -16,490 +16,22 @@
  * Boston, MA 021110-1307, USA.
  */
 
-#include <ctype.h>
-#include <stdio.h>
-#include <stdlib.h>
-#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"
-#include "disk-io.h"
-#include "print-tree.h"
-#include "transaction.h"
-#include "list.h"
 #include "volumes.h"
 #include "utils.h"
+#include "commands.h"
+#include "cmds-inspect-tree-stats.h"
 
-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;
-};
-
-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)
-{
-	struct extent_buffer *b = path->nodes[0];
-	struct btrfs_file_extent_item *fi;
-	struct btrfs_key found_key;
-	int i;
-
-	stat->total_bytes += root->leafsize;
-	stat->total_leaves++;
-
-	if (!find_inline)
-		return 0;
-
-	for (i = 0; i < btrfs_header_nritems(b); i++) {
-		btrfs_item_key_to_cpu(b, &found_key, i);
-		if (found_key.type != BTRFS_EXTENT_DATA_KEY)
-			continue;
-
-		fi = btrfs_item_ptr(b, i, struct btrfs_file_extent_item);
-		if (btrfs_file_extent_type(b, fi) == BTRFS_FILE_EXTENT_INLINE)
-			stat->total_inline +=
-				btrfs_file_extent_inline_item_len(b,
-							btrfs_item_nr(i));
-	}
-
-	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, cur_blocknr,
-					      btrfs_level_size(root, level - 1),
-					      btrfs_node_ptr_generation(b, i));
-			if (!extent_buffer_uptodate(tmp)) {
-				fprintf(stderr, "Failed to read blocknr %Lu\n",
-					btrfs_node_blockptr(b, i));
-				continue;
-			}
-			path->nodes[level - 1] = tmp;
-		}
-		if (level - 1)
-			ret = walk_nodes(root, path, stat, level - 1,
-					 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");
-			break;
-		}
-	}
-
-	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 = 0;
-	u64 group_count = 0;
-	u64 group_end = 0;
-	u64 i;
-	u64 max_seek = stat->max_seek_len;
-	int digits = 1;
-
-	if (stat->total_seeks < 20)
-		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;
-	int size_fail = 0;
-
-	root = btrfs_read_fs_root(tree_root->fs_info, key);
-	if (IS_ERR(root)) {
-		fprintf(stderr, "Failed to read root %Lu\n", key->objectid);
-		return 1;
-	}
-
-	path = btrfs_alloc_path();
-	if (!path) {
-		fprintf(stderr, "Could not allocate path\n");
-		return 1;
-	}
-
-	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)
-			goto out;
-		goto out_print;
-	}
-
-	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("\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: %llu\n", stat.total_seeks ?
-			stat.total_seek_len / stat.total_seeks : 0);
-		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("\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);
-	}
-
-	/*
-	 * We only use path to save node data in iterating,
-	 * without holding eb's ref_cnt in path.
-	 * Don't use btrfs_free_path() here, it will free these
-	 * eb again, and cause many problems, as negative ref_cnt
-	 * or invalid memory access.
-	 */
-	free(path);
-	return ret;
-}
-
-static void usage(void)
-{
-	fprintf(stderr, "Usage: calc-size [-v] [-b] <device>\n");
-}
 
 int main(int argc, char **argv)
 {
-	struct btrfs_key key;
-	struct btrfs_root *root;
-	int opt;
-	int ret = 0;
-
-	while ((opt = getopt(argc, argv, "vb")) != -1) {
-		switch (opt) {
-			case 'v':
-				verbose++;
-				break;
-			case 'b':
-				no_pretty = 1;
-				break;
-			default:
-				usage();
-				exit(1);
-		}
-	}
-
-	set_argv0(argv);
-	if (check_argc_min(argc - optind, 1)) {
-		usage();
-		exit(1);
-	}
+	int ret;
 
-	/*
-	if ((ret = check_mounted(argv[optind])) < 0) {
-		fprintf(stderr, "Could not check mount status: %d\n", ret);
-		if (ret == -EACCES)
-			fprintf(stderr, "Maybe you need to run as root?\n");
-		return ret;
-	} else if (ret) {
-		fprintf(stderr, "%s is currently mounted.  Aborting.\n",
-			argv[optind]);
-		return -EBUSY;
-	}
-	*/
+	if (argc > 1 && !strcmp(argv[1], "--help"))
+		usage(cmd_inspect_tree_stats_usage);
 
-	root = open_ctree(argv[optind], 0, 0);
-	if (!root) {
-		fprintf(stderr, "Couldn't open ctree\n");
-		exit(1);
-	}
+	ret = cmd_inspect_tree_stats(argc, argv);
 
-	printf("Calculating size of root tree\n");
-	key.objectid = BTRFS_ROOT_TREE_OBJECTID;
-	ret = calc_root_size(root, &key, 0);
-	if (ret)
-		goto out;
-
-	printf("Calculating size of extent tree\n");
-	key.objectid = BTRFS_EXTENT_TREE_OBJECTID;
-	ret = calc_root_size(root, &key, 0);
-	if (ret)
-		goto out;
-
-	printf("Calculating size of csum tree\n");
-	key.objectid = BTRFS_CSUM_TREE_OBJECTID;
-	ret = calc_root_size(root, &key, 0);
-	if (ret)
-		goto out;
-
-	key.objectid = BTRFS_FS_TREE_OBJECTID;
-	key.offset = (u64)-1;
-	printf("Calculatin' size of fs tree\n");
-	ret = calc_root_size(root, &key, 1);
-	if (ret)
-		goto out;
-out:
-	close_ctree(root);
 	btrfs_close_all_devices();
+
 	return ret;
 }
diff --git a/cmds-inspect-tree-stats.c b/cmds-inspect-tree-stats.c
new file mode 100644
index 0000000..792ccaa
--- /dev/null
+++ b/cmds-inspect-tree-stats.c
@@ -0,0 +1,506 @@
+/*
+ * Copyright (C) 2011 Red Hat.  All rights reserved.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public
+ * License v2 as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public
+ * License along with this program; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 021110-1307, USA.
+ */
+
+#include <ctype.h>
+#include <stdio.h>
+#include <stdlib.h>
+#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"
+#include "disk-io.h"
+#include "print-tree.h"
+#include "transaction.h"
+#include "list.h"
+#include "volumes.h"
+#include "utils.h"
+#include "commands.h"
+#include "cmds-inspect-tree-stats.h"
+
+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;
+};
+
+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)
+{
+	struct extent_buffer *b = path->nodes[0];
+	struct btrfs_file_extent_item *fi;
+	struct btrfs_key found_key;
+	int i;
+
+	stat->total_bytes += root->leafsize;
+	stat->total_leaves++;
+
+	if (!find_inline)
+		return 0;
+
+	for (i = 0; i < btrfs_header_nritems(b); i++) {
+		btrfs_item_key_to_cpu(b, &found_key, i);
+		if (found_key.type != BTRFS_EXTENT_DATA_KEY)
+			continue;
+
+		fi = btrfs_item_ptr(b, i, struct btrfs_file_extent_item);
+		if (btrfs_file_extent_type(b, fi) == BTRFS_FILE_EXTENT_INLINE)
+			stat->total_inline +=
+				btrfs_file_extent_inline_item_len(b,
+							btrfs_item_nr(i));
+	}
+
+	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, cur_blocknr,
+					      btrfs_level_size(root, level - 1),
+					      btrfs_node_ptr_generation(b, i));
+			if (!extent_buffer_uptodate(tmp)) {
+				fprintf(stderr, "Failed to read blocknr %llu\n",
+					btrfs_node_blockptr(b, i));
+				continue;
+			}
+			path->nodes[level - 1] = tmp;
+		}
+		if (level - 1)
+			ret = walk_nodes(root, path, stat, level - 1,
+					 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");
+			break;
+		}
+	}
+
+	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 = 0;
+	u64 group_count = 0;
+	u64 group_end = 0;
+	u64 i;
+	u64 max_seek = stat->max_seek_len;
+	int digits = 1;
+
+	if (stat->total_seeks < 20)
+		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;
+	int size_fail = 0;
+
+	root = btrfs_read_fs_root(tree_root->fs_info, key);
+	if (IS_ERR(root)) {
+		fprintf(stderr, "Failed to read root %llu\n", key->objectid);
+		return 1;
+	}
+
+	path = btrfs_alloc_path();
+	if (!path) {
+		fprintf(stderr, "Could not allocate path\n");
+		return 1;
+	}
+
+	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)
+			goto out;
+		goto out_print;
+	}
+
+	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("\tTotal size: %llu\n", stat.total_bytes);
+		printf("\t\tInline data: %llu\n", stat.total_inline);
+		printf("\tTotal seeks: %llu\n", stat.total_seeks);
+		printf("\t\tForward seeks: %llu\n", stat.forward_seeks);
+		printf("\t\tBackward seeks: %llu\n", stat.backward_seeks);
+		printf("\t\tAvg seek len: %llu\n", stat.total_seeks ?
+			stat.total_seek_len / stat.total_seeks : 0);
+		print_seek_histogram(&stat);
+		printf("\tTotal clusters: %llu\n", stat.total_clusters);
+		printf("\t\tAvg cluster size: %llu\n", stat.total_cluster_size /
+		       stat.total_clusters);
+		printf("\t\tMin cluster size: %llu\n", stat.min_cluster_size);
+		printf("\t\tMax cluster size: %llu\n", stat.max_cluster_size);
+		printf("\tTotal disk spread: %llu\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("\tTotal size: %s\n", pretty_size(stat.total_bytes));
+		printf("\t\tInline data: %s\n", pretty_size(stat.total_inline));
+		printf("\tTotal seeks: %llu\n", stat.total_seeks);
+		printf("\t\tForward seeks: %llu\n", stat.forward_seeks);
+		printf("\t\tBackward seeks: %llu\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: %llu\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);
+	}
+
+	/*
+	 * We only use path to save node data in iterating,
+	 * without holding eb's ref_cnt in path.
+	 * Don't use btrfs_free_path() here, it will free these
+	 * eb again, and cause many problems, as negative ref_cnt
+	 * or invalid memory access.
+	 */
+	free(path);
+	return ret;
+}
+
+const char * const cmd_inspect_tree_stats_usage[] = {
+	"btrfs inspect-internal tree-stats [options] <device>",
+	"Print various stats for trees",
+	"-b		raw numbers in bytes",
+	NULL
+};
+
+int cmd_inspect_tree_stats(int argc, char **argv)
+{
+	struct btrfs_key key;
+	struct btrfs_root *root;
+	int opt;
+	int ret = 0;
+
+	while ((opt = getopt(argc, argv, "vb")) != -1) {
+		switch (opt) {
+		case 'v':
+			verbose++;
+			break;
+		case 'b':
+			no_pretty = 1;
+			break;
+		default:
+			usage(cmd_inspect_tree_stats_usage);
+		}
+	}
+
+	if (check_argc_exact(argc - optind, 1)) {
+		usage(cmd_inspect_tree_stats_usage);
+	}
+
+	/*
+	if ((ret = check_mounted(argv[optind])) < 0) {
+		fprintf(stderr, "Could not check mount status: %d\n", ret);
+		if (ret == -EACCES)
+			fprintf(stderr, "Maybe you need to run as root?\n");
+		return ret;
+	} else if (ret) {
+		fprintf(stderr, "%s is currently mounted.  Aborting.\n",
+			argv[optind]);
+		return -EBUSY;
+	}
+	*/
+
+	root = open_ctree(argv[optind], 0, 0);
+	if (!root) {
+		fprintf(stderr, "Couldn't open ctree\n");
+		exit(1);
+	}
+
+	printf("Calculating size of root tree\n");
+	key.objectid = BTRFS_ROOT_TREE_OBJECTID;
+	ret = calc_root_size(root, &key, 0);
+	if (ret)
+		goto out;
+
+	printf("Calculating size of extent tree\n");
+	key.objectid = BTRFS_EXTENT_TREE_OBJECTID;
+	ret = calc_root_size(root, &key, 0);
+	if (ret)
+		goto out;
+
+	printf("Calculating size of csum tree\n");
+	key.objectid = BTRFS_CSUM_TREE_OBJECTID;
+	ret = calc_root_size(root, &key, 0);
+	if (ret)
+		goto out;
+
+	key.objectid = BTRFS_FS_TREE_OBJECTID;
+	key.offset = (u64)-1;
+	printf("Calculatin' size of fs tree\n");
+	ret = calc_root_size(root, &key, 1);
+	if (ret)
+		goto out;
+out:
+	close_ctree(root);
+	return ret;
+}
diff --git a/cmds-inspect-tree-stats.h b/cmds-inspect-tree-stats.h
new file mode 100644
index 0000000..eb401da
--- /dev/null
+++ b/cmds-inspect-tree-stats.h
@@ -0,0 +1,26 @@
+/*
+ * Copyright (C) 2011 Red Hat.  All rights reserved.
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public
+ * License v2 as published by the Free Software Foundation.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public
+ * License along with this program; if not, write to the
+ * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
+ * Boston, MA 021110-1307, USA.
+ */
+
+#ifndef __CMDS_INSPECT_TREE_STATS_H__
+#define __CMDS_INSPECT_TREE_STATS_H__
+
+int cmd_inspect_tree_stats(int argc, char **argv);
+
+extern const char * const cmd_inspect_tree_stats_usage[];
+
+#endif
diff --git a/cmds-inspect.c b/cmds-inspect.c
index 04e1ae8..d96b5c2 100644
--- a/cmds-inspect.c
+++ b/cmds-inspect.c
@@ -33,6 +33,7 @@
 #include "btrfs-list.h"
 #include "cmds-inspect-dump-tree.h"
 #include "cmds-inspect-dump-super.h"
+#include "cmds-inspect-tree-stats.h"
 
 static const char * const inspect_cmd_group_usage[] = {
 	"btrfs inspect-internal <command> <args>",
@@ -293,7 +294,7 @@ static int cmd_inspect_subvolid_resolve(int argc, char **argv)
 
 out:
 	close_file_or_dir(fd, dirstream);
-	return ret ? 1 : 0;
+	return !!ret;
 }
 
 static const char* const cmd_inspect_rootid_usage[] = {
@@ -640,6 +641,8 @@ const struct cmd_group inspect_cmd_group = {
 				cmd_inspect_dump_tree_usage, NULL, 0 },
 		{ "dump-super", cmd_inspect_dump_super,
 				cmd_inspect_dump_super_usage, NULL, 0 },
+		{ "tree-stats", cmd_inspect_tree_stats,
+				cmd_inspect_tree_stats_usage, NULL, 0 },
 		NULL_CMD_STRUCT
 	}
 };
-- 
2.7.2

[PATCH 2/2] btrfs-progs: update docs and completion for tree-stats

[Alexander Fougner]

Signed-off-by: Alexander Fougner <fougner89@gmail.com>
---
 Documentation/btrfs-inspect-internal.asciidoc | 10 ++++++++++
 btrfs-completion                              |  2 +-
 2 files changed, 11 insertions(+), 1 deletion(-)

diff --git a/Documentation/btrfs-inspect-internal.asciidoc b/Documentation/btrfs-inspect-internal.asciidoc
index bbbbc59..eb83708 100644
--- a/Documentation/btrfs-inspect-internal.asciidoc
+++ b/Documentation/btrfs-inspect-internal.asciidoc
@@ -128,6 +128,16 @@ for debugging (disables the '-f' option)
 +
 resolve the absolute path of a the subvolume id 'subvolid'
 
+*tree-stats* [options] <device>::
+(needs root privileges)
++
+Print sizes and statistics of trees.
++
+`Options`
++
+-b::::
+Print raw numbers in bytes.
+
 EXIT STATUS
 -----------
 *btrfs inspect-internal* returns a zero exit status if it succeeds. Non zero is
diff --git a/btrfs-completion b/btrfs-completion
index db0dd97..3ede77b 100644
--- a/btrfs-completion
+++ b/btrfs-completion
@@ -36,7 +36,7 @@ _btrfs()
     commands_device='scan add delete remove ready stats usage'
     commands_scrub='start cancel resume status'
     commands_rescue='chunk-recover super-recover'
-    commands_inspect_internal='inode-resolve logical-resolve subvolid-resolve rootid min-dev-size dump-tree dump-super'
+    commands_inspect_internal='inode-resolve logical-resolve subvolid-resolve rootid min-dev-size dump-tree dump-super tree-stats'
     commands_property='get set list'
     commands_quota='enable disable rescan'
     commands_qgroup='assign remove create destroy show limit'
-- 
2.7.2

Re: [PATCH 1/2] btrfs-progs: copy btrfs-calc-size to inspect-internal tree-stats

[David Sterba]

On Fri, Mar 11, 2016 at 12:49:45PM +0100, Alexander Fougner wrote:
> Signed-off-by: Alexander Fougner <fougner89@gmail.com>

Both applied, thanks.