Date:	Thu, 17 Mar 2011 19:50:21 +0100
From:	Lukas Czerner <lczerner@...hat.com>
To:	linux-ext4@...r.kernel.org
Cc:	tytso@....edu, sandeen@...hat.com,
	Lukas Czerner <lczerner@...hat.com>
Subject: [PATCH 4/4] Add macro to enable collecting bitmap statistics

This commit adds a new preprocessor macro BMAP_STATS, which can be
defined in ext2fs.h. Setting this macro, the code for statistic
collection of bitmap handling is enabled and once the bitmap shall be
freed collected information is printed to the stderr.

This feature is especially useful for better understanding how e2fsprogs
tools (mainly e2fsck) treats bitmaps and what bitmap backend can be most
suitable for particular bitmap. Backend itself (if implemented) can
provide statistics of its own as well.

I was thinking about enabling this feature simply by setting program
parameter, however collecting of the statistic, even conditional, means
unnecessary overhead. And since information provided is usually relevant
only for e2fsprogs developers, I decided to use preprocessor macro
instead.

Obviously this feature is off by default.

Signed-off-by: Lukas Czerner <lczerner@...hat.com>
---
 lib/ext2fs/blkmap64_ba.c  |    8 +++
 lib/ext2fs/blkmap64_rb.c  |   82 ++++++++++++++++++++++++++++-
 lib/ext2fs/bmap64.h       |   31 +++++++++++
 lib/ext2fs/ext2fs.h       |    4 ++
 lib/ext2fs/gen_bitmap64.c |  126 ++++++++++++++++++++++++++++++++++++++++++++-
 5 files changed, 248 insertions(+), 3 deletions(-)

diff --git a/lib/ext2fs/blkmap64_ba.c b/lib/ext2fs/blkmap64_ba.c
index 395aba9..72d775e 100644
--- a/lib/ext2fs/blkmap64_ba.c
+++ b/lib/ext2fs/blkmap64_ba.c
@@ -309,6 +309,13 @@ static void ba_clear_bmap(ext2fs_generic_bitmap bitmap)
 	       (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1));
 }
 
+static void ba_print_stats(ext2fs_generic_bitmap bitmap)
+{
+	fprintf(stderr, "%16lu Bytes used by bitarray\n",
+		((bitmap->real_end - bitmap->start) >> 3) + 1 +
+		sizeof(struct ext2fs_ba_private_struct));
+}
+
 struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = {
 	.type = EXT2FS_BMAP64_BITARRAY,
 	.new_bmap = ba_new_bmap,
@@ -324,4 +331,5 @@ struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = {
 	.set_bmap_range = ba_set_bmap_range,
 	.get_bmap_range = ba_get_bmap_range,
 	.clear_bmap = ba_clear_bmap,
+	.print_stats = ba_print_stats,
 };
diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c
index 8f121b3..c9f77a6 100644
--- a/lib/ext2fs/blkmap64_rb.c
+++ b/lib/ext2fs/blkmap64_rb.c
@@ -40,6 +40,10 @@ struct ext2fs_rb_private {
 	struct rb_root root;
 	struct bmap_rb_extent **wcursor;
 	struct bmap_rb_extent **rcursor;
+#ifdef BMAP_STATS
+	__u64 mark_hit;
+	__u64 test_hit;
+#endif
 };
 
 static int rb_insert_extent(__u64 start, __u64 count,
@@ -168,6 +172,11 @@ static errcode_t rb_alloc_private_data (ext2fs_generic_bitmap bitmap)
 	*bp->rcursor = NULL;
 	*bp->wcursor = NULL;
 
+#ifdef BMAP_STATS
+	bp->test_hit = 0;
+	bp->mark_hit = 0;
+#endif
+
 	bitmap->private = (void *) bp;
 	return 0;
 }
@@ -313,8 +322,12 @@ rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
 	if (!rcursor)
 		goto search_tree;
 
-	if (bit >= rcursor->start && bit < rcursor->start + rcursor->count)
+	if (bit >= rcursor->start && bit < rcursor->start + rcursor->count) {
+#ifdef BMAP_STATS
+		bp->test_hit++;
+#endif
 		return 1;
+	}
 
 	rcursor = *bp->wcursor;
 	if (!rcursor)
@@ -353,8 +366,12 @@ static int rb_insert_extent(__u64 start, __u64 count,
 	ext = *bp->wcursor;
 	if (ext) {
 		if (start >= ext->start &&
-		    start <= (ext->start + ext->count))
+		    start <= (ext->start + ext->count)) {
+#ifdef BMAP_STATS
+			bp->mark_hit++;
+#endif
 			goto got_extent;
+		}
 	}
 
 	while (*n) {
@@ -733,6 +750,66 @@ static void rb_clear_bmap(ext2fs_generic_bitmap bitmap)
 	*bp->wcursor = NULL;
 }
 
+#ifdef BMAP_STATS
+static void rb_print_stats(ext2fs_generic_bitmap bitmap)
+{
+	struct ext2fs_rb_private *bp;
+	struct rb_node *node = NULL;
+	struct bmap_rb_extent *ext;
+	__u64 count = 0;
+	__u64 max_size = 0;
+	__u64 min_size = ULONG_MAX;
+	__u64 size = 0, avg_size = 0;
+	__u64 mark_all, test_all;
+	double eff, m_hit = 0.0, t_hit = 0.0;
+
+	bp = (struct ext2fs_rb_private *) bitmap->private;
+
+	node = rb_first(&bp->root);
+	for (node = rb_first(&bp->root); node != NULL; node=rb_next(node)) {
+		ext = rb_entry(node, struct bmap_rb_extent, node);
+		count++;
+		if (ext->count > max_size)
+			max_size = ext->count;
+		if (ext->count < min_size)
+			min_size = ext->count;
+		size += ext->count;
+	}
+
+	if (count)
+		avg_size = size / count;
+	if (min_size == ULONG_MAX)
+		min_size = 0;
+	eff = (double)((count * sizeof(struct bmap_rb_extent)) << 3) /
+	      (bitmap->real_end - bitmap->start);
+	mark_all = bitmap->stats.mark_count + bitmap->stats.mark_ext_count;
+	test_all = bitmap->stats.test_count + bitmap->stats.test_ext_count;
+	if (mark_all)
+		m_hit = ((double)bp->mark_hit / mark_all) * 100;
+	if (test_all)
+		t_hit = ((double)bp->test_hit / test_all) * 100;
+
+	fprintf(stderr, "%16llu cache hits on test (%.2f%)\n"
+		"%16llu cache hits on mark (%.2f%)\n",
+		bp->test_hit, t_hit, bp->mark_hit, m_hit);
+	fprintf(stderr, "%16llu extents\n%16llu Bytes per extent\n",
+		count, sizeof(struct bmap_rb_extent));
+	fprintf(stderr, "%16llu Bytes used by rbtree\n"
+		"%16llu bits minimum size\n",
+		count * sizeof(struct bmap_rb_extent) +
+		sizeof(struct ext2fs_rb_private), min_size);
+	fprintf(stderr, "%16llu bits maximum size\n"
+		"%16llu bits average size\n",
+		max_size, avg_size);
+	fprintf(stderr, "%16llu bits mapped by extents\n", size);
+	fprintf(stderr, "%16llu bitmap size\n"
+		"%16.4lf memory / bitmap bit memory ratio (bitarray = 1)\n",
+		bitmap->real_end - bitmap->start, eff);
+}
+#else
+static void rb_print_stats(ext2fs_generic_bitmap bitmap){}
+#endif
+
 struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = {
 	.type = EXT2FS_BMAP64_RBTREE,
 	.new_bmap = rb_new_bmap,
@@ -748,4 +825,5 @@ struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = {
 	.set_bmap_range = rb_set_bmap_range,
 	.get_bmap_range = rb_get_bmap_range,
 	.clear_bmap = rb_clear_bmap,
+	.print_stats = rb_print_stats,
 };
diff --git a/lib/ext2fs/bmap64.h b/lib/ext2fs/bmap64.h
index 31021b9..fdb5ace 100644
--- a/lib/ext2fs/bmap64.h
+++ b/lib/ext2fs/bmap64.h
@@ -9,6 +9,33 @@
  * %End-Header%
  */
 
+struct ext2_bmap_statistics {
+	int		type;
+	struct timeval	created;
+	struct timeval	destroyed;;
+
+	unsigned long	copy_count;
+	unsigned long	resize_count;
+	unsigned long	mark_count;
+	unsigned long	unmark_count;
+	unsigned long	test_count;
+	unsigned long	mark_ext_count;
+	unsigned long	unmark_ext_count;
+	unsigned long	test_ext_count;
+	unsigned long	set_range_count;
+	unsigned long	get_range_count;
+	unsigned long	clear_count;
+
+	blk64_t		last_marked;
+	blk64_t		last_tested;
+	blk64_t		mark_back;
+	blk64_t		test_back;
+
+	unsigned long	mark_seq;
+	unsigned long	test_seq;
+};
+
+
 struct ext2fs_struct_generic_bitmap {
 	errcode_t		magic;
 	ext2_filsys 		fs;
@@ -19,6 +46,9 @@ struct ext2fs_struct_generic_bitmap {
 	char			*description;
 	void			*private;
 	errcode_t		base_error_code;
+#ifdef BMAP_STATS
+	struct ext2_bmap_statistics	stats;
+#endif
 };
 
 #define EXT2FS_IS_32_BITMAP(bmap) \
@@ -56,6 +86,7 @@ struct ext2_bitmap_ops {
 	errcode_t (*get_bmap_range)(ext2fs_generic_bitmap bitmap,
 				    __u64 start, size_t num, void *out);
 	void (*clear_bmap)(ext2fs_generic_bitmap bitmap);
+	void (*print_stats)(ext2fs_generic_bitmap);
 };
 
 extern struct ext2_bitmap_ops ext2fs_blkmap64_bitarray;
diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h
index 8621bf6..eb35ad8 100644
--- a/lib/ext2fs/ext2fs.h
+++ b/lib/ext2fs/ext2fs.h
@@ -1113,6 +1113,10 @@ extern errcode_t ext2fs_set_generic_bitmap_range(ext2fs_generic_bitmap bmap,
 						 void *in);
 
 /* gen_bitmap64.c */
+
+/* Generate and print bitmap usage statistics */
+/* #define BMAP_STATS */
+
 void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap);
 errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
 				    int type, __u64 start, __u64 end,
diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c
index 4c69244..e2d3a09 100644
--- a/lib/ext2fs/gen_bitmap64.c
+++ b/lib/ext2fs/gen_bitmap64.c
@@ -77,6 +77,12 @@ static void warn_bitmap(ext2fs_generic_bitmap bitmap,
 #endif
 }
 
+#ifdef BMAP_STATS
+#define INC_STAT(map, name) map->stats.name
+#else
+#define INC_STAT(map, name) ;;
+#endif
+
 
 #define EXT2_DEFAULT_BITMAP_BACKEND EXT2FS_BMAP64_BITARRAY
 
@@ -216,6 +222,15 @@ errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
 		return retval;
 	memset(bitmap, 0, sizeof(struct ext2fs_struct_generic_bitmap));
 
+#ifdef BMAP_STATS
+	if (gettimeofday(&bitmap->stats.created,
+			 (struct timezone *) NULL) == -1) {
+		perror("gettimeofday");
+		return 1;
+	}
+	bitmap->stats.type = type;
+#endif
+
 	/* XXX factor out, repeated in copy_bmap */
 	bitmap->magic = magic;
 	bitmap->fs = fs;
@@ -245,8 +260,8 @@ errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
 
 	retval = bitmap->bitmap_ops->new_bmap(fs, bitmap);
 	if (retval) {
-		ext2fs_free_mem(&bitmap);
 		ext2fs_free_mem(&bitmap->description);
+		ext2fs_free_mem(&bitmap);
 		return retval;
 	}
 
@@ -254,6 +269,62 @@ errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
 	return 0;
 }
 
+#ifdef BMAP_STATS
+void ext2fs_print_bmap_statistics(ext2fs_generic_bitmap bitmap)
+{
+	struct ext2_bmap_statistics *stats = &bitmap->stats;
+	float mark_seq_perc = 0.0, test_seq_perc = 0.0;
+	float mark_back_perc = 0.0, test_back_perc = 0.0;
+	double inuse;
+
+	if (stats->test_count) {
+		test_seq_perc = ((float)stats->test_seq /
+				 stats->test_count) * 100;
+		test_back_perc = ((float)stats->test_back /
+				  stats->test_count) * 100;
+	}
+
+	if (stats->mark_count) {
+		mark_seq_perc = ((float)stats->mark_seq /
+				 stats->mark_count) * 100;
+		mark_back_perc = ((float)stats->mark_back /
+				  stats->mark_count) * 100;
+	}
+
+	inuse = (double) stats->destroyed.tv_sec + \
+		(((double) stats->destroyed.tv_usec) * 0.000001);
+	inuse -= (double) stats->created.tv_sec + \
+		(((double) stats->created.tv_usec) * 0.000001);
+
+	fprintf(stderr, "\n[+] %s bitmap\n", bmap_defs[stats->type].descr);
+	fprintf(stderr, "=================================================\n");
+	fprintf(stderr, "%16d type\n%16d backend\n",
+		stats->type, bmap_defs[stats->type].backend);
+	fprintf(stderr, "%16d bits long\n",
+		bitmap->real_end - bitmap->start);
+	fprintf(stderr, "%16lu copy_bmap\n%16lu resize_bmap\n",
+		stats->copy_count, stats->resize_count);
+	fprintf(stderr, "%16lu mark bmap\n%16lu unmark_bmap\n",
+		stats->mark_count, stats->unmark_count);
+	fprintf(stderr, "%16lu test_bmap\n%16lu mark_bmap_extent\n",
+		stats->test_count, stats->mark_ext_count);
+	fprintf(stderr, "%16lu unmark_bmap_extent\n"
+		"%16lu test_clear_bmap_extent\n",
+		stats->unmark_ext_count, stats->test_ext_count);
+	fprintf(stderr, "%16lu set_bmap_range\n%16lu set_bmap_range\n",
+		stats->set_range_count, stats->get_range_count);
+	fprintf(stderr, "%16lu clear_bmap\n%16lu contiguous bit test (%.2f%)\n",
+		stats->clear_count, stats->test_seq, test_seq_perc);
+	fprintf(stderr, "%16lu contiguous bit mark (%.2f%)\n"
+		"%16lu bits tested backwards (%.2f%)\n",
+		stats->mark_seq, mark_seq_perc,
+		stats->test_back, test_back_perc);
+	fprintf(stderr, "%16lu bits marked backwards (%.2f%)\n"
+		"%16.2f seconds in use\n",
+		stats->mark_back, mark_back_perc, inuse);
+}
+#endif
+
 void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap)
 {
 	if (!bmap)
@@ -267,6 +338,16 @@ void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap)
 	if (!EXT2FS_IS_64_BITMAP(bmap))
 		return;
 
+#ifdef BMAP_STATS
+	if (gettimeofday(&bmap->stats.destroyed,
+			 (struct timezone *) NULL) == -1) {
+		perror("gettimeofday");
+		return;
+	}
+	ext2fs_print_bmap_statistics(bmap);
+	bmap->bitmap_ops->print_stats(bmap);
+#endif
+
 	bmap->bitmap_ops->free_bmap(bmap);
 
 	if (bmap->description) {
@@ -300,6 +381,17 @@ errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap src,
 		return retval;
 	memset(new_bmap, 0, sizeof(struct ext2fs_struct_generic_bitmap));
 
+
+#ifdef BMAP_STATS
+	src->stats.copy_count++;
+	if (gettimeofday(&new_bmap->stats.created,
+			 (struct timezone *) NULL) == -1) {
+		perror("gettimeofday");
+		return 1;
+	}
+	new_bmap->stats.type = src->stats.type;
+#endif
+
 	/* Copy all the high-level parts over */
 	new_bmap->magic = src->magic;
 	new_bmap->fs = src->fs;
@@ -346,6 +438,8 @@ errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap bmap,
 	if (!EXT2FS_IS_64_BITMAP(bmap))
 		return EINVAL;
 
+	INC_STAT(bmap, resize_count);
+
 	return bmap->bitmap_ops->resize_bmap(bmap, new_end, new_real_end);
 }
 
@@ -432,6 +526,15 @@ int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap bitmap,
 	if (!EXT2FS_IS_64_BITMAP(bitmap))
 		return 0;
 
+#ifdef BMAP_STATS
+	if (arg == bitmap->stats.last_marked + 1)
+		bitmap->stats.mark_seq++;
+	if (arg < bitmap->stats.last_marked)
+		bitmap->stats.mark_back++;
+	bitmap->stats.last_marked = arg;
+	bitmap->stats.mark_count++;
+#endif
+
 	if ((arg < bitmap->start) || (arg > bitmap->end)) {
 		warn_bitmap(bitmap, EXT2FS_MARK_ERROR, arg);
 		return 0;
@@ -458,6 +561,8 @@ int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap bitmap,
 	if (!EXT2FS_IS_64_BITMAP(bitmap))
 		return 0;
 
+	INC_STAT(bitmap, unmark_count);
+
 	if ((arg < bitmap->start) || (arg > bitmap->end)) {
 		warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg);
 		return 0;
@@ -484,6 +589,15 @@ int ext2fs_test_generic_bmap(ext2fs_generic_bitmap bitmap,
 	if (!EXT2FS_IS_64_BITMAP(bitmap))
 		return 0;
 
+#ifdef BMAP_STATS
+	bitmap->stats.test_count++;
+	if (arg == bitmap->stats.last_tested + 1)
+		bitmap->stats.test_seq++;
+	if (arg < bitmap->stats.last_tested)
+		bitmap->stats.test_back++;
+	bitmap->stats.last_tested = arg;
+#endif
+
 	if ((arg < bitmap->start) || (arg > bitmap->end)) {
 		warn_bitmap(bitmap, EXT2FS_TEST_ERROR, arg);
 		return 0;
@@ -512,6 +626,8 @@ errcode_t ext2fs_set_generic_bmap_range(ext2fs_generic_bitmap bmap,
 	if (!EXT2FS_IS_64_BITMAP(bmap))
 		return EINVAL;
 
+	INC_STAT(bmap, set_range_count);
+
 	return bmap->bitmap_ops->set_bmap_range(bmap, start, num, in);
 }
 
@@ -535,6 +651,8 @@ errcode_t ext2fs_get_generic_bmap_range(ext2fs_generic_bitmap bmap,
 	if (!EXT2FS_IS_64_BITMAP(bmap))
 		return EINVAL;
 
+	INC_STAT(bmap, get_range_count);
+
 	return bmap->bitmap_ops->get_bmap_range(bmap, start, num, out);
 }
 
@@ -606,6 +724,8 @@ int ext2fs_test_block_bitmap_range2(ext2fs_block_bitmap bmap,
 	if (!EXT2FS_IS_64_BITMAP(bmap))
 		return EINVAL;
 
+	INC_STAT(bmap, test_ext_count);
+
 	return bmap->bitmap_ops->test_clear_bmap_extent(bmap, block, num);
 }
 
@@ -628,6 +748,8 @@ void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap bmap,
 	if (!EXT2FS_IS_64_BITMAP(bmap))
 		return;
 
+	INC_STAT(bmap, mark_ext_count);
+
 	if ((block < bmap->start) || (block+num-1 > bmap->end)) {
 		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_MARK, block,
 				   bmap->description);
@@ -656,6 +778,8 @@ void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap bmap,
 	if (!EXT2FS_IS_64_BITMAP(bmap))
 		return;
 
+	INC_STAT(bmap, unmark_ext_count);
+
 	if ((block < bmap->start) || (block+num-1 > bmap->end)) {
 		ext2fs_warn_bitmap(EXT2_ET_BAD_BLOCK_UNMARK, block,
 				   bmap->description);
-- 
1.7.4

--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Powered by blists - more mailing lists