Patchwork [4/4] Add macro to enable collecting bitmap statistics

login
register
mail settings
Submitter Lukas Czerner
Date March 17, 2011, 6:50 p.m.
Message ID <1300387821-21705-5-git-send-email-lczerner@redhat.com>
Download mbox | patch
Permalink /patch/87417/
State Superseded
Headers show

Comments

Lukas Czerner - March 17, 2011, 6:50 p.m.
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@redhat.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(-)
Andreas Dilger - March 17, 2011, 9:19 p.m.
On 2011-03-17, at 12:50 PM, Lukas Czerner wrote:
> 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.

Being able to turn this on/off at runtime without needing to recompile is pretty important.  It is fine to allow it to be #ifdef out entirely, but if it is enabled it is good to be able to turn it on/off via the command-line.

> @@ -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);

This looks like a bug in the upstream code that should be submitted separately.  However, I don't see this bug in my tree (it is correctly ordered already), and I don't see it being introduced by your patches...  It again makes me wonder which branch these patches are against.

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

This should include the amount of memory used by the bitmap, which is one of the most important stats for this code.

> +#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@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html


Cheers, Andreas





--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Lukas Czerner - March 18, 2011, 10:23 a.m.
On Thu, 17 Mar 2011, Andreas Dilger wrote:

> On 2011-03-17, at 12:50 PM, Lukas Czerner wrote:
> > 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.
> 
> Being able to turn this on/off at runtime without needing to recompile is pretty important.  It is fine to allow it to be #ifdef out entirely, but if it is enabled it is good to be able to turn it on/off via the command-line.

The downside of this is that bitmaps are used by many tools, so it would
require change in all of those tools to use command-line option.

> 
> > @@ -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);
> 
> This looks like a bug in the upstream code that should be submitted separately.  However, I don't see this bug in my tree (it is correctly ordered already), and I don't see it being introduced by your patches...  It again makes me wonder which branch these patches are against.

I can see this bug in master branch
git://git.kernel.org/pub/scm/fs/ext2/e2fsprogs.git

so I'll send it separately.

> 
> > +	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);
> > +}
> 
> This should include the amount of memory used by the bitmap, which is one of the most important stats for this code.

Yes, it is the most important, however at this level we can not know
this kind of bitmap backend specific information. That's why there is
new bitmap operation print_stats() which is called right after
ext2fs_print_bmap_statistics() and should provide additional bitmap
backed specific information. Rbtree and bitarray does that with this
commit.

> 
> > +#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@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 
> 
> Cheers, Andreas
> 

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

Patch

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