[PATCH 00/10] extent-based bitmaps for e2fsprogs

[PATCH 00/10] extent-based bitmaps for e2fsprogs

[Theodore Ts'o]

I spent some time playing with Lukas Czerner's rbtree patches.  Here is
a patch set which is based on the latest e2fsprogs sources, and which
doesn't break any library ABI's or API's.  I also threw in regression
tester for bitmaps, and fixed a bug in rb_unmark_bmap() that was found
by the regression tests.

My tests on a number of file systems that I had easy access to seems to
indicate that on pretty much all file systems, using the rbtree based
implementation is a huge win over the bitarray.  (With memory required
after patches being as low as 25% of the memory needed beforehand,
although I believe 40-50% of the memory required in previous releases is
more realistic.)  The one exception is if there are a huge number of
directories, which is the reason for the AUTODIR pseudo backend.

Comments, please!

						- Ted

Lukas Czerner (3):
  libext2fs: add rbtree library
  libext2fs: add a bitmap implementation using rbtree's
  libext2fs: add bitmap statistics

Theodore Ts'o (7):
  libext2fs: add default_bitmap_type to the ext2_filsys structure
  libext2fs: add tests for the bitmap functions
  libext2fs: add pseudo bitmap backend type EXT2FS_BMAP64_AUTODIR
  e2fsck: fix pass5 bug when using two different bitmap backends
  libext2fs: use the rbtree bitmap by default when initializing a file
    system
  e2fsck: use different bitmap types as appropriate
  libext2fs: adjust the description when copying a bitmap

 e2fsck/e2fsck.h               |   20 +
 e2fsck/pass1.c                |   62 ++--
 e2fsck/pass1b.c               |    6 +-
 e2fsck/pass2.c                |    7 +-
 e2fsck/pass3.c                |    7 +-
 e2fsck/pass5.c                |    4 +-
 e2fsck/unix.c                 |    4 +
 e2fsck/util.c                 |   61 +++
 lib/ext2fs/Makefile.in        |   38 ++-
 lib/ext2fs/bitmaps.c          |   14 +-
 lib/ext2fs/blkmap64_ba.c      |    8 +
 lib/ext2fs/blkmap64_rb.c      |  824 +++++++++++++++++++++++++++++++++++++++++
 lib/ext2fs/bmap64.h           |   33 ++
 lib/ext2fs/ext2fs.h           |   15 +-
 lib/ext2fs/ext2fsP.h          |    2 -
 lib/ext2fs/gen_bitmap64.c     |  158 ++++++++-
 lib/ext2fs/icount.c           |    4 +-
 lib/ext2fs/initialize.c       |    1 +
 lib/ext2fs/rbtree.c           |  451 ++++++++++++++++++++++
 lib/ext2fs/rbtree.h           |  180 +++++++++
 lib/ext2fs/tst_bitmaps.c      |  577 ++++++++++++++++++++++++++++
 lib/ext2fs/tst_bitmaps_cmd.ct |   39 ++
 lib/ext2fs/tst_bitmaps_cmds   |   46 +++
 lib/ext2fs/tst_bitmaps_exp    |   92 +++++
 24 files changed, 2600 insertions(+), 53 deletions(-)
 create mode 100644 lib/ext2fs/blkmap64_rb.c
 create mode 100644 lib/ext2fs/rbtree.c
 create mode 100644 lib/ext2fs/rbtree.h
 create mode 100644 lib/ext2fs/tst_bitmaps.c
 create mode 100644 lib/ext2fs/tst_bitmaps_cmd.ct
 create mode 100644 lib/ext2fs/tst_bitmaps_cmds
 create mode 100644 lib/ext2fs/tst_bitmaps_exp

-- 
1.7.8.11.gefc1f.dirty

[PATCH 01/10] libext2fs: add default_bitmap_type to the ext2_filsys structure

[Theodore Ts'o]

This allows a program to control the bitmap backend implementation
that will get used without needing to change the current library API.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 lib/ext2fs/bitmaps.c      |   14 +++++++-------
 lib/ext2fs/ext2fs.h       |   10 +++++++++-
 lib/ext2fs/ext2fsP.h      |    2 --
 lib/ext2fs/gen_bitmap64.c |    3 +++
 4 files changed, 19 insertions(+), 10 deletions(-)

diff --git a/lib/ext2fs/bitmaps.c b/lib/ext2fs/bitmaps.c
index e518295..8402191 100644
--- a/lib/ext2fs/bitmaps.c
+++ b/lib/ext2fs/bitmaps.c
@@ -67,9 +67,9 @@ errcode_t ext2fs_allocate_inode_bitmap(ext2_filsys fs,
 	/* Are we permitted to use new-style bitmaps? */
 	if (fs->flags & EXT2_FLAG_64BITS)
 		return (ext2fs_alloc_generic_bmap(fs,
-				  EXT2_ET_MAGIC_INODE_BITMAP64,
-				  EXT2FS_BMAP64_BITARRAY,
-				  start, end, real_end, descr, ret));
+				EXT2_ET_MAGIC_INODE_BITMAP64,
+				fs->default_bitmap_type,
+				start, end, real_end, descr, ret));
 
 	/* Otherwise, check to see if the file system is small enough
 	 * to use old-style 32-bit bitmaps */
@@ -99,9 +99,9 @@ errcode_t ext2fs_allocate_block_bitmap(ext2_filsys fs,
 
 	if (fs->flags & EXT2_FLAG_64BITS)
 		return (ext2fs_alloc_generic_bmap(fs,
-				  EXT2_ET_MAGIC_BLOCK_BITMAP64,
-				  EXT2FS_BMAP64_BITARRAY,
-				  start, end, real_end, descr, ret));
+				EXT2_ET_MAGIC_BLOCK_BITMAP64,
+				fs->default_bitmap_type,
+				start, end, real_end, descr, ret));
 
 	if ((end > ~0U) || (real_end > ~0U))
 		return EXT2_ET_CANT_USE_LEGACY_BITMAPS;
@@ -143,7 +143,7 @@ errcode_t ext2fs_allocate_subcluster_bitmap(ext2_filsys fs,
 		    * (__u64) fs->group_desc_count)-1 + start;
 
 	retval = ext2fs_alloc_generic_bmap(fs, EXT2_ET_MAGIC_BLOCK_BITMAP64,
-					   EXT2FS_BMAP64_BITARRAY, start,
+					   fs->default_bitmap_type, start,
 					   end, real_end, descr, &bmap);
 	if (retval)
 		return retval;
diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h
index 227ee58..d90a8b1 100644
--- a/lib/ext2fs/ext2fs.h
+++ b/lib/ext2fs/ext2fs.h
@@ -244,10 +244,12 @@ struct struct_ext2_filsys {
 	__u32				umask;
 	time_t				now;
 	int				cluster_ratio_bits;
+	__u16				default_bitmap_type;
+	__u16				pad;
 	/*
 	 * Reserved for future expansion
 	 */
-	__u32				reserved[6];
+	__u32				reserved[5];
 
 	/*
 	 * Reserved for the use of the calling application.
@@ -287,6 +289,12 @@ struct struct_ext2_filsys {
 #endif
 
 /*
+ * 64-bit bitmap backend types
+ */
+
+#define EXT2FS_BMAP64_BITARRAY	1
+
+/*
  * Return flags for the block iterator functions
  */
 #define BLOCK_CHANGED	1
diff --git a/lib/ext2fs/ext2fsP.h b/lib/ext2fs/ext2fsP.h
index 82e1ba0..729d5c5 100644
--- a/lib/ext2fs/ext2fsP.h
+++ b/lib/ext2fs/ext2fsP.h
@@ -109,8 +109,6 @@ extern void ext2fs_numeric_progress_close(ext2_filsys fs,
  * 64-bit bitmap support
  */
 
-#define EXT2FS_BMAP64_BITARRAY	1

[PATCH 02/10] libext2fs: add tests for the bitmap functions

[Theodore Ts'o]

These tests allow us to be sure that the new bitmap backends are
correctly implemented.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 lib/ext2fs/Makefile.in        |   17 ++-
 lib/ext2fs/tst_bitmaps.c      |  577 +++++++++++++++++++++++++++++++++++++++++
 lib/ext2fs/tst_bitmaps_cmd.ct |   39 +++
 lib/ext2fs/tst_bitmaps_cmds   |   46 ++++
 lib/ext2fs/tst_bitmaps_exp    |   92 +++++++
 5 files changed, 770 insertions(+), 1 deletions(-)
 create mode 100644 lib/ext2fs/tst_bitmaps.c
 create mode 100644 lib/ext2fs/tst_bitmaps_cmd.ct
 create mode 100644 lib/ext2fs/tst_bitmaps_cmds
 create mode 100644 lib/ext2fs/tst_bitmaps_exp

diff --git a/lib/ext2fs/Makefile.in b/lib/ext2fs/Makefile.in
index 3d08095..37f5ee5 100644
--- a/lib/ext2fs/Makefile.in
+++ b/lib/ext2fs/Makefile.in
@@ -347,6 +347,16 @@ filefrag.o: $(top_srcdir)/debugfs/filefrag.c
 	$(E) "	CC $<"
 	$(Q) $(CC) $(ALL_CFLAGS) -c $< -o $@
 
+tst_bitmaps_cmd.c: tst_bitmaps_cmd.ct
+	$(E) "	MK_CMDS $@"
+	$(Q) DIR=$(srcdir) $(MK_CMDS) $(srcdir)/tst_bitmaps_cmd.ct
+
+tst_bitmaps: tst_bitmaps.o tst_bitmaps_cmd.o $(STATIC_LIBEXT2FS) $(DEPLIBSS) \
+		$(DEPLIBCOM_ERR)
+	$(E) "	LD $@"
+	$(Q) $(CC) -o $@ tst_bitmaps.o tst_bitmaps_cmd.o $(ALL_CFLAGS) \
+		$(STATIC_LIBEXT2FS) $(LIBSS) $(LIBCOM_ERR)
+
 tst_extents: $(srcdir)/extent.c extent_dbg.c $(DEBUG_OBJS) $(DEPLIBSS) \
 	$(LIBE2P) $(DEPLIBUUID) $(DEPLIBBLKID) $(DEPLIBCOM_ERR)
 	$(E) "	LD $@"
@@ -369,7 +379,8 @@ mkjournal: mkjournal.c $(STATIC_LIBEXT2FS) $(DEPLIBCOM_ERR)
 	$(E) "	LD $@"
 	$(Q) $(CC) -o mkjournal $(srcdir)/mkjournal.c -DDEBUG $(STATIC_LIBEXT2FS) $(LIBCOM_ERR) $(ALL_CFLAGS)
 
-check:: tst_bitops tst_badblocks tst_iscan tst_types tst_icount tst_super_size tst_types tst_inode_size tst_csum tst_crc32c
+check:: tst_bitops tst_badblocks tst_iscan tst_types tst_icount \
+    tst_super_size tst_types tst_inode_size tst_csum tst_crc32c tst_bitmaps
 	LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) ./tst_bitops
 	LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) ./tst_badblocks
 	LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) ./tst_iscan
@@ -379,6 +390,9 @@ check:: tst_bitops tst_badblocks tst_iscan tst_types tst_icount tst_super_size t
 	LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) ./tst_inode_size
 	LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) ./tst_csum
 	LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) ./tst_crc32c
+	LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) \
+		./tst_bitmaps -f $(srcdir)/tst_bitmaps_cmds > tst_bitmaps_out
+	diff $(srcdir)/tst_bitmaps_exp tst_bitmaps_out
 
 installdirs::
 	$(E) "	MKINSTALLDIRS $(libdir) $(includedir)/ext2fs"
@@ -411,6 +425,7 @@ clean::
 		tst_badblocks tst_iscan ext2_err.et ext2_err.c ext2_err.h \
 		tst_byteswap tst_ismounted tst_getsize tst_sectgetsize \
 		tst_bitops tst_types tst_icount tst_super_size tst_csum \
+		tst_bitmaps tst_bitmaps_out tst_bitmaps_cmd.c \
 		ext2_tdbtool mkjournal debug_cmds.c \
 		../libext2fs.a ../libext2fs_p.a ../libext2fs_chk.a \
 		crc32c_table.h gen_crc32ctable tst_crc32c
diff --git a/lib/ext2fs/tst_bitmaps.c b/lib/ext2fs/tst_bitmaps.c
new file mode 100644
index 0000000..27722e5
--- /dev/null
+++ b/lib/ext2fs/tst_bitmaps.c
@@ -0,0 +1,577 @@
+/*
+ * tst_bitmaps.c
+ *
+ * Copyright (C) 2011 Theodore Ts'o.
+ *
+ * %Begin-Header%
+ * This file may be redistributed under the terms of the GNU Library
+ * General Public License, version 2.
+ * %End-Header%
+ */
+
+#include "config.h"
+#include <unistd.h>
+#include <stdlib.h>
+#include <stdio.h>
+#ifdef HAVE_GETOPT_H
+#include <getopt.h>
+#endif
+#include <string.h>
+#include <fcntl.h>
+#include <time.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#include "ss/ss.h"
+
+#include "ext2_fs.h"
+#include "ext2fs.h"
+#include "ext2fsP.h"
+
+extern ss_request_table tst_bitmaps_cmds;
+
+static char subsystem_name[] = "tst_bitmaps";
+static char version[] = "1.0";
+
+ext2_filsys	test_fs;
+int		exit_status = 0;
+
+static int source_file(const char *cmd_file, int sci_idx)
+{
+	FILE		*f;
+	char		buf[256];
+	char		*cp;
+	int		retval;
+	int 		noecho;
+
+	if (strcmp(cmd_file, "-") == 0)
+		f = stdin;
+	else {
+		f = fopen(cmd_file, "r");
+		if (!f) {
+			perror(cmd_file);
+			exit(1);
+		}
+	}
+	fflush(stdout);
+	fflush(stderr);
+	setbuf(stdout, NULL);
+	setbuf(stderr, NULL);
+	while (!feof(f)) {
+		if (fgets(buf, sizeof(buf), f) == NULL)
+			break;
+		if (buf[0] == '#')
+			continue;
+		noecho = 0;
+		if (buf[0] == '-') {
+			noecho = 1;
+			buf[0] = ' ';
+		}
+		cp = strchr(buf, '\n');
+		if (cp)
+			*cp = 0;
+		cp = strchr(buf, '\r');
+		if (cp)
+			*cp = 0;
+		if (!noecho)
+			printf("%s: %s\n", subsystem_name, buf);
+		retval = ss_execute_line(sci_idx, buf);
+		if (retval) {
+			ss_perror(sci_idx, retval, buf);
+			exit_status++;
+		}
+	}
+	return exit_status;
+}
+
+
+/*
+ * This function resets the libc getopt() function, which keeps
+ * internal state.  Bad design!  Stupid libc API designers!  No
+ * biscuit!
+ *
+ * BSD-derived getopt() functions require that optind be reset to 1 in
+ * order to reset getopt() state.  This used to be generally accepted
+ * way of resetting getopt().  However, glibc's getopt()
+ * has additional getopt() state beyond optind, and requires that
+ * optind be set zero to reset its state.  So the unfortunate state of
+ * affairs is that BSD-derived versions of getopt() misbehave if
+ * optind is set to 0 in order to reset getopt(), and glibc's getopt()
+ * will core dump if optind is set 1 in order to reset getopt().
+ *
+ * More modern versions of BSD require that optreset be set to 1 in
+ * order to reset getopt().   Sigh.  Standards, anyone?
+ *
+ * We hide the hair here.
+ */
+void reset_getopt(void)
+{
+#if defined(__GLIBC__) || defined(__linux__)
+	optind = 0;
+#else
+	optind = 1;
+#endif
+#ifdef HAVE_OPTRESET
+	optreset = 1;		/* Makes BSD getopt happy */
+#endif
+}
+
+/*
+ * This function will convert a string to an unsigned long, printing
+ * an error message if it fails, and returning success or failure in err.
+ */
+unsigned long parse_ulong(const char *str, const char *cmd,
+			  const char *descr, int *err)
+{
+	char		*tmp;
+	unsigned long	ret;
+
+	ret = strtoul(str, &tmp, 0);
+	if (*tmp == 0) {
+		if (err)
+			*err = 0;
+		return ret;
+	}
+	com_err(cmd, 0, "Bad %s - %s", descr, str);
+	if (err)
+		*err = 1;
+	else
+		exit(1);
+	return 0;
+}
+
+
+int check_fs_open(char *name)
+{
+	if (!test_fs) {
+		com_err(name, 0, "Filesystem not open");
+		return 1;
+	}
+	return 0;
+}
+
+static void setup_filesystem(const char *name,
+			     unsigned int blocks, unsigned int inodes,
+			     unsigned int type)
+{
+	struct ext2_super_block param;
+	errcode_t retval;
+
+	memset(&param, 0, sizeof(param));
+	ext2fs_blocks_count_set(&param, blocks);
+	param.s_inodes_count = inodes;
+
+	retval = ext2fs_initialize("test fs", EXT2_FLAG_64BITS, &param,
+				   test_io_manager, &test_fs);
+
+	if (retval) {
+		com_err(name, retval, "while initializing filesystem");
+		return;
+	}
+	test_fs->default_bitmap_type = type;
+	ext2fs_free_block_bitmap(test_fs->block_map);
+	test_fs->block_map = 0;
+	ext2fs_free_inode_bitmap(test_fs->inode_map);
+	test_fs->inode_map = 0;
+	retval = ext2fs_allocate_block_bitmap(test_fs, "block bitmap",
+					      &test_fs->block_map);
+	if (retval) {
+		com_err(name, retval, "while allocating block bitmap");
+		goto errout;
+	}
+	retval = ext2fs_allocate_inode_bitmap(test_fs, "inode bitmap",
+					      &test_fs->inode_map);
+	if (retval) {
+		com_err(name, retval, "while allocating inode bitmap");
+		goto errout;
+	}
+	return;
+
+errout:
+	ext2fs_close(test_fs);
+	test_fs = 0;
+}
+
+void setup_cmd(int argc, char **argv)
+{
+	errcode_t	retval;
+	int		i, c, err;
+	unsigned int	blocks = 128;
+	unsigned int	inodes = 0;
+	unsigned int	type = EXT2FS_BMAP64_BITARRAY;
+
+	if (test_fs) {
+		ext2fs_close(test_fs);
+		test_fs = 0;
+	}
+
+	reset_getopt();
+	while ((c = getopt(argc, argv, "b:i:t:")) != EOF) {
+		switch (c) {
+		case 'b':
+			blocks = parse_ulong(optarg, argv[0],
+					     "number of blocks", &err);
+			if (err)
+				return;
+			break;
+		case 'i':
+			inodes = parse_ulong(optarg, argv[0],
+					     "number of blocks", &err);
+			if (err)
+				return;
+			break;
+		case 't':
+			type = parse_ulong(optarg, argv[0],
+					   "bitmap backend type", &err);
+			if (err)
+				return;
+			break;
+		default:
+			fprintf(stderr, "%s: usage: setup [-b blocks] "
+				"[-i inodes] [-t type]\n", argv[0]);
+			return;
+		}
+	}
+	setup_filesystem(argv[0], blocks, inodes, type);
+}
+
+void close_cmd(int argc, char **argv)
+{
+	if (check_fs_open(argv[0]))
+		return;
+
+	ext2fs_close(test_fs);
+	test_fs = 0;
+}
+
+
+void dump_bitmap(ext2fs_generic_bitmap bmap, unsigned int start, unsigned num)
+{
+	unsigned char	*buf;
+	errcode_t	retval;
+	int		i, len = (num - start + 7) / 8;
+
+	buf = malloc(len);
+	if (!buf) {
+		com_err("dump_bitmap", 0, "couldn't allocate buffer");
+		return;
+	}
+	memset(buf, 0, len);
+	retval = ext2fs_get_generic_bmap_range(bmap, (__u64) start, num, buf);
+	if (retval) {
+		com_err("dump_bitmap", retval, 
+			"while calling ext2fs_generic_bmap_range");
+		free(buf);
+		return;
+	}
+	for (i=0; i < len; i++)
+		printf("%02x", buf[i]);
+	printf("\n");
+	free(buf);
+}
+
+void dump_inode_bitmap_cmd(int argc, char **argv)
+{
+	if (check_fs_open(argv[0]))
+		return;
+
+	printf("inode bitmap: ");
+	dump_bitmap(test_fs->inode_map, 1, test_fs->super->s_inodes_count);
+}
+	
+void dump_block_bitmap_cmd(int argc, char **argv)
+{
+	if (check_fs_open(argv[0]))
+		return;
+
+	printf("block bitmap: ");
+	dump_bitmap(test_fs->block_map, test_fs->super->s_first_data_block,
+		    test_fs->super->s_blocks_count);
+}
+	
+void do_setb(int argc, char *argv[])
+{
+	unsigned int block, num;
+	int err;
+	int test_result, op_result;
+
+	if (check_fs_open(argv[0]))
+		return;
+
+	if (argc != 2 && argc != 3) {
+		com_err(argv[0], 0, "Usage: setb <block> [num]");
+		return;
+	}
+
+	block = parse_ulong(argv[1], argv[0], "block", &err);
+	if (err)
+		return;
+
+	if (argc == 3) {
+		num = parse_ulong(argv[2], argv[0], "num", &err);
+		if (err)
+			return;
+
+		ext2fs_mark_block_bitmap_range2(test_fs->block_map,
+						block, num);
+		printf("Marking blocks %u to %u\n", block, block + num - 1);
+		return;
+	}
+
+	test_result = ext2fs_test_block_bitmap2(test_fs->block_map, block);
+	op_result = ext2fs_mark_block_bitmap2(test_fs->block_map, block);
+	printf("Setting block %u, was %s before\n", block, op_result ?
+	       "set" : "clear");
+	if (!test_result != !op_result)
+		com_err(argv[0], 0, "*ERROR* test_result different! (%d, %d)",
+			test_result, op_result);
+}
+
+void do_clearb(int argc, char *argv[])
+{
+	unsigned int block, num;
+	int err;
+	int test_result, op_result;
+
+	if (check_fs_open(argv[0]))
+		return;
+
+	if (argc != 2 && argc != 3) {
+		com_err(argv[0], 0, "Usage: clearb <block> [num]");
+		return;
+	}
+
+	block = parse_ulong(argv[1], argv[0], "block", &err);
+	if (err)
+		return;
+
+	if (argc == 3) {
+		num = parse_ulong(argv[2], argv[0], "num", &err);
+		if (err)
+			return;
+
+		ext2fs_unmark_block_bitmap_range2(test_fs->block_map,
+						block, num);
+		printf("Clearing blocks %u to %u\n", block, block + num - 1);
+		return;
+	}
+
+	test_result = ext2fs_test_block_bitmap2(test_fs->block_map, block);
+	op_result = ext2fs_unmark_block_bitmap2(test_fs->block_map, block);
+	printf("Clearing block %u, was %s before\n", block, op_result ?
+	       "set" : "clear");
+	if (!test_result != !op_result)
+		com_err(argv[0], 0, "*ERROR* test_result different! (%d, %d)",
+			test_result, op_result);
+}
+
+void do_testb(int argc, char *argv[])
+{
+	unsigned int block, num;
+	int err;
+	int test_result, op_result;
+
+	if (check_fs_open(argv[0]))
+		return;
+
+	if (argc != 2 && argc != 3) {
+		com_err(argv[0], 0, "Usage: testb <block> [num]");
+		return;
+	}
+
+	block = parse_ulong(argv[1], argv[0], "block", &err);
+	if (err)
+		return;
+
+	if (argc == 3) {
+		num = parse_ulong(argv[2], argv[0], "num", &err);
+		if (err)
+			return;
+
+		test_result =
+			ext2fs_test_block_bitmap_range2(test_fs->block_map,
+							block, num);
+		printf("Blocks %u to %u are %sall clear.\n",
+		       block, block + num - 1, test_result ? "" : "NOT ");
+		return;
+	}
+
+	test_result = ext2fs_test_block_bitmap2(test_fs->block_map, block);
+	printf("Block %u is %s\n", block, test_result ? "set" : "clear");
+}
+
+void do_zerob(int argc, char *argv[])
+{
+	if (check_fs_open(argv[0]))
+		return;
+
+	printf("Clearing block bitmap.\n");
+	ext2fs_clear_block_bitmap(test_fs->block_map);
+}
+
+void do_seti(int argc, char *argv[])
+{
+	unsigned int inode;
+	int err;
+	int test_result, op_result;
+
+	if (check_fs_open(argv[0]))
+		return;
+
+	if (argc != 2) {
+		com_err(argv[0], 0, "Usage: seti <inode>");
+		return;
+	}
+
+	inode = parse_ulong(argv[1], argv[0], "inode", &err);
+	if (err)
+		return;
+
+	test_result = ext2fs_test_inode_bitmap2(test_fs->inode_map, inode);
+	op_result = ext2fs_mark_inode_bitmap2(test_fs->inode_map, inode);
+	printf("Setting inode %u, was %s before\n", inode, op_result ?
+	       "set" : "clear");
+	if (!test_result != !op_result) {
+		com_err(argv[0], 0, "*ERROR* test_result different! (%d, %d)",
+			test_result, op_result);
+		exit_status++;
+	}
+}
+
+void do_cleari(int argc, char *argv[])
+{
+	unsigned int inode;
+	int err;
+	int test_result, op_result;
+
+	if (check_fs_open(argv[0]))
+		return;
+
+	if (argc != 2) {
+		com_err(argv[0], 0, "Usage: clearb <inode>");
+		return;
+	}
+
+	inode = parse_ulong(argv[1], argv[0], "inode", &err);
+	if (err)
+		return;
+
+	test_result = ext2fs_test_inode_bitmap2(test_fs->inode_map, inode);
+	op_result = ext2fs_unmark_inode_bitmap2(test_fs->inode_map, inode);
+	printf("Clearing inode %u, was %s before\n", inode, op_result ?
+	       "set" : "clear");
+	if (!test_result != !op_result) {
+		com_err(argv[0], 0, "*ERROR* test_result different! (%d, %d)",
+			test_result, op_result);
+		exit_status++;
+	}
+}
+
+void do_testi(int argc, char *argv[])
+{
+	unsigned int inode;
+	int err;
+	int test_result, op_result;
+
+	if (check_fs_open(argv[0]))
+		return;
+
+	if (argc != 2) {
+		com_err(argv[0], 0, "Usage: testb <inode>");
+		return;
+	}
+
+	inode = parse_ulong(argv[1], argv[0], "inode", &err);
+	if (err)
+		return;
+
+	test_result = ext2fs_test_inode_bitmap2(test_fs->inode_map, inode);
+	printf("Inode %u is %s\n", inode, test_result ? "set" : "clear");
+}
+
+void do_zeroi(int argc, char *argv[])
+{
+	if (check_fs_open(argv[0]))
+		return;
+
+	printf("Clearing inode bitmap.\n");
+	ext2fs_clear_inode_bitmap(test_fs->inode_map);
+}
+
+int main(int argc, char **argv)
+{
+	unsigned int	blocks = 128;
+	unsigned int	inodes = 0;
+	unsigned int	type = EXT2FS_BMAP64_BITARRAY;
+	int		c, err, code;
+	char		*request = (char *)NULL;
+	char		*cmd_file = 0;
+	int		sci_idx;
+
+	add_error_table(&et_ss_error_table);
+	add_error_table(&et_ext2_error_table);
+	while ((c = getopt (argc, argv, "b:i:t:R:f:")) != EOF) {
+		switch (c) {
+		case 'b':
+			blocks = parse_ulong(optarg, argv[0],
+					     "number of blocks", &err);
+			if (err)
+				return;
+			break;
+		case 'i':
+			inodes = parse_ulong(optarg, argv[0],
+					     "number of blocks", &err);
+			if (err)
+				return;
+			break;
+		case 't':
+			type = parse_ulong(optarg, argv[0],
+					   "bitmap backend type", &err);
+			if (err)
+				return;
+			break;
+		case 'R':
+			request = optarg;
+			break;
+		case 'f':
+			cmd_file = optarg;
+			break;
+		default:
+			com_err(argv[0], 0, "Usage: %s [-R request] "
+				"[-f cmd_file]", subsystem_name);
+			exit(1);
+		}
+	}
+
+	sci_idx = ss_create_invocation(subsystem_name, version,
+				       (char *)NULL, &tst_bitmaps_cmds, &code);
+	if (code) {
+		ss_perror(sci_idx, code, "creating invocation");
+		exit(1);
+	}
+
+	(void) ss_add_request_table (sci_idx, &ss_std_requests, 1, &code);
+	if (code) {
+		ss_perror(sci_idx, code, "adding standard requests");
+		exit (1);
+	}
+
+	printf("%s %s.  Type '?' for a list of commands.\n\n",
+	       subsystem_name, version);
+
+	setup_filesystem(argv[0], blocks, inodes, type);
+
+	if (request) {
+		code = ss_execute_line(sci_idx, request);
+		if (code) {
+			ss_perror(sci_idx, code, request);
+			exit_status++;
+		}
+	} else if (cmd_file) {
+		exit_status = source_file(cmd_file, sci_idx);
+	} else {
+		ss_listen(sci_idx);
+	}
+
+	exit(exit_status);
+}
+
diff --git a/lib/ext2fs/tst_bitmaps_cmd.ct b/lib/ext2fs/tst_bitmaps_cmd.ct
new file mode 100644
index 0000000..5a51d23
--- /dev/null
+++ b/lib/ext2fs/tst_bitmaps_cmd.ct
@@ -0,0 +1,39 @@
+command_table tst_bitmaps_cmds;
+
+request setup_cmd, "Setup file system",
+	setup;
+
+request close_cmd, "Close file system",
+	close;
+
+request dump_inode_bitmap_cmd, "Dump the inode bitmap",
+	dump_inode_bitmap, dump_ib;
+
+request dump_block_bitmap_cmd, "Dump the block bitmap",
+	dump_block_bitmap, dump_bb;
+
+request do_setb, "Set block",
+	set_block, setb;
+
+request do_clearb, "Clear block",
+	clear_block, clearb;
+
+request do_testb, "Test block",
+	test_block, testb;
+
+request do_zerob, "Clear block bitmap",
+	clear_block_bitmap, zerob;
+
+request do_seti, "Set inode",
+	set_inode, seti;
+
+request do_cleari, "Clear inode",
+	clear_inode, cleari;
+
+request do_testi, "Test inode",
+	test_inode, testi;
+
+request do_zeroi, "Clear inode bitmap",
+	clear_inode_bitmap, zeroi;
+
+end;
diff --git a/lib/ext2fs/tst_bitmaps_cmds b/lib/ext2fs/tst_bitmaps_cmds
new file mode 100644
index 0000000..13f4ea8
--- /dev/null
+++ b/lib/ext2fs/tst_bitmaps_cmds
@@ -0,0 +1,46 @@
+setb 12
+setb 12
+clearb 12
+clearb 12
+setb 12
+setb 14
+setb 16
+testb 13
+testb 15
+testb 12
+testb 14
+setb 13
+setb 15
+testb 12
+testb 11
+testb 15
+testb 16
+dump_bb
+clearb 12 7
+testb 12 7
+setb 15
+testb 12 7
+clearb 15
+testb 12 7
+setb 12 7
+dump_bb
+seti 2
+seti 5
+seti 4
+seti 3
+seti 4
+seti 5
+testi 6
+testi 1
+dump_ib
+zeroi
+testi 5
+seti 5
+seti 5
+cleari 5
+cleari 5
+testi 17
+testi 6
+testi 4
+quit
+
diff --git a/lib/ext2fs/tst_bitmaps_exp b/lib/ext2fs/tst_bitmaps_exp
new file mode 100644
index 0000000..aa64ae7
--- /dev/null
+++ b/lib/ext2fs/tst_bitmaps_exp
@@ -0,0 +1,92 @@
+tst_bitmaps 1.0.  Type '?' for a list of commands.
+
+tst_bitmaps: setb 12
+Setting block 12, was clear before
+tst_bitmaps: setb 12
+Setting block 12, was set before
+tst_bitmaps: clearb 12
+Clearing block 12, was set before
+tst_bitmaps: clearb 12
+Clearing block 12, was clear before
+tst_bitmaps: setb 12
+Setting block 12, was clear before
+tst_bitmaps: setb 14
+Setting block 14, was clear before
+tst_bitmaps: setb 16
+Setting block 16, was clear before
+tst_bitmaps: testb 13
+Block 13 is clear
+tst_bitmaps: testb 15
+Block 15 is clear
+tst_bitmaps: testb 12
+Block 12 is set
+tst_bitmaps: testb 14
+Block 14 is set
+tst_bitmaps: setb 13
+Setting block 13, was clear before
+tst_bitmaps: setb 15
+Setting block 15, was clear before
+tst_bitmaps: testb 12
+Block 12 is set
+tst_bitmaps: testb 11
+Block 11 is clear
+tst_bitmaps: testb 15
+Block 15 is set
+tst_bitmaps: testb 16
+Block 16 is set
+tst_bitmaps: dump_bb
+block bitmap: 00f80000000000000000000000000000
+tst_bitmaps: clearb 12 7
+Clearing blocks 12 to 18
+tst_bitmaps: testb 12 7
+Blocks 12 to 18 are all clear.
+tst_bitmaps: setb 15
+Setting block 15, was clear before
+tst_bitmaps: testb 12 7
+Blocks 12 to 18 are NOT all clear.
+tst_bitmaps: clearb 15
+Clearing block 15, was set before
+tst_bitmaps: testb 12 7
+Blocks 12 to 18 are all clear.
+tst_bitmaps: setb 12 7
+Marking blocks 12 to 18
+tst_bitmaps: dump_bb
+block bitmap: 00f80300000000000000000000000000
+tst_bitmaps: seti 2
+Setting inode 2, was clear before
+tst_bitmaps: seti 5
+Setting inode 5, was clear before
+tst_bitmaps: seti 4
+Setting inode 4, was clear before
+tst_bitmaps: seti 3
+Setting inode 3, was clear before
+tst_bitmaps: seti 4
+Setting inode 4, was set before
+tst_bitmaps: seti 5
+Setting inode 5, was set before
+tst_bitmaps: testi 6
+Inode 6 is clear
+tst_bitmaps: testi 1
+Inode 1 is clear
+tst_bitmaps: dump_ib
+inode bitmap: 1e000000
+tst_bitmaps: zeroi
+Clearing inode bitmap.
+tst_bitmaps: testi 5
+Inode 5 is clear
+tst_bitmaps: seti 5
+Setting inode 5, was clear before
+tst_bitmaps: seti 5
+Setting inode 5, was set before
+tst_bitmaps: cleari 5
+Clearing inode 5, was set before
+tst_bitmaps: cleari 5
+Clearing inode 5, was clear before
+tst_bitmaps: testi 17
+Inode 17 is clear
+tst_bitmaps: testi 6
+Inode 6 is clear
+tst_bitmaps: testi 4
+Inode 4 is clear
+tst_bitmaps: quit
+tst_bitmaps: 
-- 
1.7.8.11.gefc1f.dirty

[PATCH 03/10] libext2fs: add rbtree library

[Theodore Ts'o]

From: Lukas Czerner <lczerner@redhat.com>

This commit adds rbtree library into e2fsprogs so it can be used for
various internal data structures. The rbtree implementation is ripped of
kernel rbtree implementation with small changes needed for it to work
outside kernel.

[ I prefixed the exported symbols and interface with ext2fs_ to keep
  avoid pulluting the namespace exported by the libext2fs shared
  library.  -- tytso ]

Signed-off-by: Lukas Czerner <lczerner@redhat.com>
Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 lib/ext2fs/Makefile.in |   11 +-
 lib/ext2fs/rbtree.c    |  451 ++++++++++++++++++++++++++++++++++++++++++++++++
 lib/ext2fs/rbtree.h    |  180 +++++++++++++++++++
 3 files changed, 640 insertions(+), 2 deletions(-)
 create mode 100644 lib/ext2fs/rbtree.c
 create mode 100644 lib/ext2fs/rbtree.h

diff --git a/lib/ext2fs/Makefile.in b/lib/ext2fs/Makefile.in
index 37f5ee5..cdf53b8 100644
--- a/lib/ext2fs/Makefile.in
+++ b/lib/ext2fs/Makefile.in
@@ -83,7 +83,8 @@ OBJS= $(DEBUGFS_LIB_OBJS) $(RESIZE_LIB_OBJS) $(E2IMAGE_LIB_OBJS) \
 	unix_io.o \
 	unlink.o \
 	valid_blk.o \
-	version.o
+	version.o \
+	rbtree.o
 
 SRCS= ext2_err.c \
 	$(srcdir)/alloc.c \
@@ -162,7 +163,8 @@ SRCS= ext2_err.c \
 	$(srcdir)/unlink.c \
 	$(srcdir)/valid_blk.c \
 	$(srcdir)/version.c \
-	$(srcdir)/write_bb_file.c
+	$(srcdir)/write_bb_file.c \
+	$(srcdir)/rbtree.c \
 
 HFILES= bitops.h ext2fs.h ext2_io.h ext2_fs.h ext2_ext_attr.h ext3_extents.h \
 	tdb.h qcow2.h
@@ -919,3 +921,8 @@ write_bb_file.o: $(srcdir)/write_bb_file.c $(top_builddir)/lib/config.h \
  $(srcdir)/ext2_fs.h $(srcdir)/ext3_extents.h $(top_srcdir)/lib/et/com_err.h \
  $(srcdir)/ext2_io.h $(top_builddir)/lib/ext2fs/ext2_err.h \
  $(srcdir)/ext2_ext_attr.h $(srcdir)/bitops.h
+rbtree.o: $(srcdir)/rbtree.c $(srcdir)/ext2_fs.h \
+ $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/ext2fs.h \
+ $(srcdir)/ext2_fs.h $(srcdir)/ext3_extents.h $(top_srcdir)/lib/et/com_err.h \
+ $(srcdir)/ext2_io.h $(top_builddir)/lib/ext2fs/ext2_err.h \
+ $(srcdir)/ext2_ext_attr.h $(srcdir)/bitops.h
diff --git a/lib/ext2fs/rbtree.c b/lib/ext2fs/rbtree.c
new file mode 100644
index 0000000..7467e10
--- /dev/null
+++ b/lib/ext2fs/rbtree.c
@@ -0,0 +1,451 @@
+/*
+  Red Black Trees
+  (C) 1999  Andrea Arcangeli <andrea@suse.de>
+  (C) 2002  David Woodhouse <dwmw2@infradead.org>
+
+  This program is free software; you can redistribute it and/or modify
+  it under the terms of the GNU General Public License as published by
+  the Free Software Foundation; either version 2 of the License, or
+  (at your option) any later version.
+
+  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  02111-1307  USA
+
+  linux/lib/rbtree.c
+*/
+
+#include "rbtree.h"
+
+static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
+{
+	struct rb_node *right = node->rb_right;
+	struct rb_node *parent = ext2fs_rb_parent(node);
+
+	if ((node->rb_right = right->rb_left))
+		ext2fs_rb_set_parent(right->rb_left, node);
+	right->rb_left = node;
+
+	ext2fs_rb_set_parent(right, parent);
+
+	if (parent)
+	{
+		if (node == parent->rb_left)
+			parent->rb_left = right;
+		else
+			parent->rb_right = right;
+	}
+	else
+		root->rb_node = right;
+	ext2fs_rb_set_parent(node, right);
+}
+
+static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
+{
+	struct rb_node *left = node->rb_left;
+	struct rb_node *parent = ext2fs_rb_parent(node);
+
+	if ((node->rb_left = left->rb_right))
+		ext2fs_rb_set_parent(left->rb_right, node);
+	left->rb_right = node;
+
+	ext2fs_rb_set_parent(left, parent);
+
+	if (parent)
+	{
+		if (node == parent->rb_right)
+			parent->rb_right = left;
+		else
+			parent->rb_left = left;
+	}
+	else
+		root->rb_node = left;
+	ext2fs_rb_set_parent(node, left);
+}
+
+void ext2fs_rb_insert_color(struct rb_node *node, struct rb_root *root)
+{
+	struct rb_node *parent, *gparent;
+
+	while ((parent = ext2fs_rb_parent(node)) && ext2fs_rb_is_red(parent))
+	{
+		gparent = ext2fs_rb_parent(parent);
+
+		if (parent == gparent->rb_left)
+		{
+			{
+				register struct rb_node *uncle = gparent->rb_right;
+				if (uncle && ext2fs_rb_is_red(uncle))
+				{
+					ext2fs_rb_set_black(uncle);
+					ext2fs_rb_set_black(parent);
+					ext2fs_rb_set_red(gparent);
+					node = gparent;
+					continue;
+				}
+			}
+
+			if (parent->rb_right == node)
+			{
+				register struct rb_node *tmp;
+				__rb_rotate_left(parent, root);
+				tmp = parent;
+				parent = node;
+				node = tmp;
+			}
+
+			ext2fs_rb_set_black(parent);
+			ext2fs_rb_set_red(gparent);
+			__rb_rotate_right(gparent, root);
+		} else {
+			{
+				register struct rb_node *uncle = gparent->rb_left;
+				if (uncle && ext2fs_rb_is_red(uncle))
+				{
+					ext2fs_rb_set_black(uncle);
+					ext2fs_rb_set_black(parent);
+					ext2fs_rb_set_red(gparent);
+					node = gparent;
+					continue;
+				}
+			}
+
+			if (parent->rb_left == node)
+			{
+				register struct rb_node *tmp;
+				__rb_rotate_right(parent, root);
+				tmp = parent;
+				parent = node;
+				node = tmp;
+			}
+
+			ext2fs_rb_set_black(parent);
+			ext2fs_rb_set_red(gparent);
+			__rb_rotate_left(gparent, root);
+		}
+	}
+
+	ext2fs_rb_set_black(root->rb_node);
+}
+
+static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
+			     struct rb_root *root)
+{
+	struct rb_node *other;
+
+	while ((!node || ext2fs_rb_is_black(node)) && node != root->rb_node)
+	{
+		if (parent->rb_left == node)
+		{
+			other = parent->rb_right;
+			if (ext2fs_rb_is_red(other))
+			{
+				ext2fs_rb_set_black(other);
+				ext2fs_rb_set_red(parent);
+				__rb_rotate_left(parent, root);
+				other = parent->rb_right;
+			}
+			if ((!other->rb_left || ext2fs_rb_is_black(other->rb_left)) &&
+			    (!other->rb_right || ext2fs_rb_is_black(other->rb_right)))
+			{
+				ext2fs_rb_set_red(other);
+				node = parent;
+				parent = ext2fs_rb_parent(node);
+			}
+			else
+			{
+				if (!other->rb_right || ext2fs_rb_is_black(other->rb_right))
+				{
+					ext2fs_rb_set_black(other->rb_left);
+					ext2fs_rb_set_red(other);
+					__rb_rotate_right(other, root);
+					other = parent->rb_right;
+				}
+				ext2fs_rb_set_color(other, ext2fs_rb_color(parent));
+				ext2fs_rb_set_black(parent);
+				ext2fs_rb_set_black(other->rb_right);
+				__rb_rotate_left(parent, root);
+				node = root->rb_node;
+				break;
+			}
+		}
+		else
+		{
+			other = parent->rb_left;
+			if (ext2fs_rb_is_red(other))
+			{
+				ext2fs_rb_set_black(other);
+				ext2fs_rb_set_red(parent);
+				__rb_rotate_right(parent, root);
+				other = parent->rb_left;
+			}
+			if ((!other->rb_left || ext2fs_rb_is_black(other->rb_left)) &&
+			    (!other->rb_right || ext2fs_rb_is_black(other->rb_right)))
+			{
+				ext2fs_rb_set_red(other);
+				node = parent;
+				parent = ext2fs_rb_parent(node);
+			}
+			else
+			{
+				if (!other->rb_left || ext2fs_rb_is_black(other->rb_left))
+				{
+					ext2fs_rb_set_black(other->rb_right);
+					ext2fs_rb_set_red(other);
+					__rb_rotate_left(other, root);
+					other = parent->rb_left;
+				}
+				ext2fs_rb_set_color(other, ext2fs_rb_color(parent));
+				ext2fs_rb_set_black(parent);
+				ext2fs_rb_set_black(other->rb_left);
+				__rb_rotate_right(parent, root);
+				node = root->rb_node;
+				break;
+			}
+		}
+	}
+	if (node)
+		ext2fs_rb_set_black(node);
+}
+
+void ext2fs_rb_erase(struct rb_node *node, struct rb_root *root)
+{
+	struct rb_node *child, *parent;
+	int color;
+
+	if (!node->rb_left)
+		child = node->rb_right;
+	else if (!node->rb_right)
+		child = node->rb_left;
+	else
+	{
+		struct rb_node *old = node, *left;
+
+		node = node->rb_right;
+		while ((left = node->rb_left) != NULL)
+			node = left;
+
+		if (ext2fs_rb_parent(old)) {
+			if (ext2fs_rb_parent(old)->rb_left == old)
+				ext2fs_rb_parent(old)->rb_left = node;
+			else
+				ext2fs_rb_parent(old)->rb_right = node;
+		} else
+			root->rb_node = node;
+
+		child = node->rb_right;
+		parent = ext2fs_rb_parent(node);
+		color = ext2fs_rb_color(node);
+
+		if (parent == old) {
+			parent = node;
+		} else {
+			if (child)
+				ext2fs_rb_set_parent(child, parent);
+			parent->rb_left = child;
+
+			node->rb_right = old->rb_right;
+			ext2fs_rb_set_parent(old->rb_right, node);
+		}
+
+		node->rb_parent_color = old->rb_parent_color;
+		node->rb_left = old->rb_left;
+		ext2fs_rb_set_parent(old->rb_left, node);
+
+		goto color;
+	}
+
+	parent = ext2fs_rb_parent(node);
+	color = ext2fs_rb_color(node);
+
+	if (child)
+		ext2fs_rb_set_parent(child, parent);
+	if (parent)
+	{
+		if (parent->rb_left == node)
+			parent->rb_left = child;
+		else
+			parent->rb_right = child;
+	}
+	else
+		root->rb_node = child;
+
+ color:
+	if (color == RB_BLACK)
+		__rb_erase_color(child, parent, root);
+}
+
+static void ext2fs_rb_augment_path(struct rb_node *node, rb_augment_f func, void *data)
+{
+	struct rb_node *parent;
+
+up:
+	func(node, data);
+	parent = ext2fs_rb_parent(node);
+	if (!parent)
+		return;
+
+	if (node == parent->rb_left && parent->rb_right)
+		func(parent->rb_right, data);
+	else if (parent->rb_left)
+		func(parent->rb_left, data);
+
+	node = parent;
+	goto up;
+}
+
+/*
+ * after inserting @node into the tree, update the tree to account for
+ * both the new entry and any damage done by rebalance
+ */
+void ext2fs_rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)
+{
+	if (node->rb_left)
+		node = node->rb_left;
+	else if (node->rb_right)
+		node = node->rb_right;
+
+	ext2fs_rb_augment_path(node, func, data);
+}
+
+/*
+ * before removing the node, find the deepest node on the rebalance path
+ * that will still be there after @node gets removed
+ */
+struct rb_node *ext2fs_rb_augment_erase_begin(struct rb_node *node)
+{
+	struct rb_node *deepest;
+
+	if (!node->rb_right && !node->rb_left)
+		deepest = ext2fs_rb_parent(node);
+	else if (!node->rb_right)
+		deepest = node->rb_left;
+	else if (!node->rb_left)
+		deepest = node->rb_right;
+	else {
+		deepest = ext2fs_rb_next(node);
+		if (deepest->rb_right)
+			deepest = deepest->rb_right;
+		else if (ext2fs_rb_parent(deepest) != node)
+			deepest = ext2fs_rb_parent(deepest);
+	}
+
+	return deepest;
+}
+
+/*
+ * after removal, update the tree to account for the removed entry
+ * and any rebalance damage.
+ */
+void ext2fs_rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)
+{
+	if (node)
+		ext2fs_rb_augment_path(node, func, data);
+}
+
+/*
+ * This function returns the first node (in sort order) of the tree.
+ */
+struct rb_node *ext2fs_rb_first(const struct rb_root *root)
+{
+	struct rb_node	*n;
+
+	n = root->rb_node;
+	if (!n)
+		return NULL;
+	while (n->rb_left)
+		n = n->rb_left;
+	return n;
+}
+
+struct rb_node *ext2fs_rb_last(const struct rb_root *root)
+{
+	struct rb_node	*n;
+
+	n = root->rb_node;
+	if (!n)
+		return NULL;
+	while (n->rb_right)
+		n = n->rb_right;
+	return n;
+}
+
+struct rb_node *ext2fs_rb_next(const struct rb_node *node)
+{
+	struct rb_node *parent;
+
+	if (ext2fs_rb_parent(node) == node)
+		return NULL;
+
+	/* If we have a right-hand child, go down and then left as far
+	   as we can. */
+	if (node->rb_right) {
+		node = node->rb_right;
+		while (node->rb_left)
+			node=node->rb_left;
+		return (struct rb_node *)node;
+	}
+
+	/* No right-hand children.  Everything down and left is
+	   smaller than us, so any 'next' node must be in the general
+	   direction of our parent. Go up the tree; any time the
+	   ancestor is a right-hand child of its parent, keep going
+	   up. First time it's a left-hand child of its parent, said
+	   parent is our 'next' node. */
+	while ((parent = ext2fs_rb_parent(node)) && node == parent->rb_right)
+		node = parent;
+
+	return parent;
+}
+
+struct rb_node *ext2fs_rb_prev(const struct rb_node *node)
+{
+	struct rb_node *parent;
+
+	if (ext2fs_rb_parent(node) == node)
+		return NULL;
+
+	/* If we have a left-hand child, go down and then right as far
+	   as we can. */
+	if (node->rb_left) {
+		node = node->rb_left;
+		while (node->rb_right)
+			node=node->rb_right;
+		return (struct rb_node *)node;
+	}
+
+	/* No left-hand children. Go up till we find an ancestor which
+	   is a right-hand child of its parent */
+	while ((parent = ext2fs_rb_parent(node)) && node == parent->rb_left)
+		node = parent;
+
+	return parent;
+}
+
+void ext2fs_rb_replace_node(struct rb_node *victim, struct rb_node *new,
+			  struct rb_root *root)
+{
+	struct rb_node *parent = ext2fs_rb_parent(victim);
+
+	/* Set the surrounding nodes to point to the replacement */
+	if (parent) {
+		if (victim == parent->rb_left)
+			parent->rb_left = new;
+		else
+			parent->rb_right = new;
+	} else {
+		root->rb_node = new;
+	}
+	if (victim->rb_left)
+		ext2fs_rb_set_parent(victim->rb_left, new);
+	if (victim->rb_right)
+		ext2fs_rb_set_parent(victim->rb_right, new);
+
+	/* Copy the pointers/colour from the victim to the replacement */
+	*new = *victim;
+}
diff --git a/lib/ext2fs/rbtree.h b/lib/ext2fs/rbtree.h
new file mode 100644
index 0000000..972297b
--- /dev/null
+++ b/lib/ext2fs/rbtree.h
@@ -0,0 +1,180 @@
+/*
+  Red Black Trees
+  (C) 1999  Andrea Arcangeli <andrea@suse.de>
+
+  This program is free software; you can redistribute it and/or modify
+  it under the terms of the GNU General Public License as published by
+  the Free Software Foundation; either version 2 of the License, or
+  (at your option) any later version.
+
+  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  02111-1307  USA
+
+  linux/include/linux/rbtree.h
+
+  To use rbtrees you'll have to implement your own insert and search cores.
+  This will avoid us to use callbacks and to drop drammatically performances.
+  I know it's not the cleaner way,  but in C (not in C++) to get
+  performances and genericity...
+
+  Some example of insert and search follows here. The search is a plain
+  normal search over an ordered tree. The insert instead must be implemented
+  in two steps: First, the code must insert the element in order as a red leaf
+  in the tree, and then the support library function rb_insert_color() must
+  be called. Such function will do the not trivial work to rebalance the
+  rbtree, if necessary.
+
+-----------------------------------------------------------------------
+static inline struct page * rb_search_page_cache(struct inode * inode,
+						 unsigned long offset)
+{
+	struct rb_node * n = inode->i_rb_page_cache.rb_node;
+	struct page * page;
+
+	while (n)
+	{
+		page = rb_entry(n, struct page, rb_page_cache);
+
+		if (offset < page->offset)
+			n = n->rb_left;
+		else if (offset > page->offset)
+			n = n->rb_right;
+		else
+			return page;
+	}
+	return NULL;
+}
+
+static inline struct page * __rb_insert_page_cache(struct inode * inode,
+						   unsigned long offset,
+						   struct rb_node * node)
+{
+	struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
+	struct rb_node * parent = NULL;
+	struct page * page;
+
+	while (*p)
+	{
+		parent = *p;
+		page = rb_entry(parent, struct page, rb_page_cache);
+
+		if (offset < page->offset)
+			p = &(*p)->rb_left;
+		else if (offset > page->offset)
+			p = &(*p)->rb_right;
+		else
+			return page;
+	}
+
+	rb_link_node(node, parent, p);
+
+	return NULL;
+}
+
+static inline struct page * rb_insert_page_cache(struct inode * inode,
+						 unsigned long offset,
+						 struct rb_node * node)
+{
+	struct page * ret;
+	if ((ret = __rb_insert_page_cache(inode, offset, node)))
+		goto out;
+	rb_insert_color(node, &inode->i_rb_page_cache);
+ out:
+	return ret;
+}
+-----------------------------------------------------------------------
+*/
+
+#ifndef	_LINUX_RBTREE_H
+#define	_LINUX_RBTREE_H
+
+#include <stdlib.h>
+
+#undef offsetof
+#ifdef __compiler_offsetof
+#define offsetof(TYPE,MEMBER) __compiler_offsetof(TYPE,MEMBER)
+#else
+#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
+#endif
+
+#define container_of(ptr, type, member) ({			\
+	const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
+	(type *)( (char *)__mptr - offsetof(type,member) );})
+
+struct rb_node
+{
+	unsigned long  rb_parent_color;
+#define	RB_RED		0
+#define	RB_BLACK	1
+	struct rb_node *rb_right;
+	struct rb_node *rb_left;
+} __attribute__((aligned(sizeof(long))));
+    /* The alignment might seem pointless, but allegedly CRIS needs it */
+
+struct rb_root
+{
+	struct rb_node *rb_node;
+};
+
+
+#define ext2fs_rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
+#define ext2fs_rb_color(r)   ((r)->rb_parent_color & 1)
+#define ext2fs_rb_is_red(r)   (!ext2fs_rb_color(r))
+#define ext2fs_rb_is_black(r) ext2fs_rb_color(r)
+#define ext2fs_rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
+#define ext2fs_rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)
+
+static inline void ext2fs_rb_set_parent(struct rb_node *rb, struct rb_node *p)
+{
+	rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
+}
+static inline void ext2fs_rb_set_color(struct rb_node *rb, int color)
+{
+	rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
+}
+
+#define RB_ROOT	(struct rb_root) { NULL, }
+#define	ext2fs_rb_entry(ptr, type, member) container_of(ptr, type, member)
+
+#define EXT2FS_RB_EMPTY_ROOT(root)	((root)->rb_node == NULL)
+#define EXT2FS_RB_EMPTY_NODE(node)	(ext2fs_rb_parent(node) == node)
+#define EXT2FS_RB_CLEAR_NODE(node)	(ext2fs_rb_set_parent(node, node))
+
+extern void ext2fs_rb_insert_color(struct rb_node *, struct rb_root *);
+extern void ext2fs_rb_erase(struct rb_node *, struct rb_root *);
+
+typedef void (*rb_augment_f)(struct rb_node *node, void *data);
+
+extern void ext2fs_rb_augment_insert(struct rb_node *node,
+			      rb_augment_f func, void *data);
+extern struct rb_node *ext2fs_rb_augment_erase_begin(struct rb_node *node);
+extern void ext2fs_rb_augment_erase_end(struct rb_node *node,
+				 rb_augment_f func, void *data);
+
+/* Find logical next and previous nodes in a tree */
+extern struct rb_node *ext2fs_rb_next(const struct rb_node *);
+extern struct rb_node *ext2fs_rb_prev(const struct rb_node *);
+extern struct rb_node *ext2fs_rb_first(const struct rb_root *);
+extern struct rb_node *ext2fs_rb_last(const struct rb_root *);
+
+/* Fast replacement of a single node without remove/rebalance/add/rebalance */
+extern void ext2fs_rb_replace_node(struct rb_node *victim, struct rb_node *new,
+				 struct rb_root *root);
+
+static inline void ext2fs_rb_link_node(struct rb_node * node,
+				     struct rb_node * parent,
+				     struct rb_node ** rb_link)
+{
+	node->rb_parent_color = (unsigned long )parent;
+	node->rb_left = node->rb_right = NULL;
+
+	*rb_link = node;
+}
+
+#endif	/* _LINUX_RBTREE_H */
-- 
1.7.8.11.gefc1f.dirty

[PATCH 04/10] libext2fs: add a bitmap implementation using rbtree's

[Theodore Ts'o]

From: Lukas Czerner <lczerner@redhat.com>

For a long time we had a bitarray backend for storing filesystem
metadata bitmaps, however today this approach might hit its limits with
todays huge data storage devices, because of its memory utilization.

Bitarrays stores bitmaps as ..well, as bitmaps. But this is in most
cases highly unefficient because we need to allocate memory even for the
big parts of bitmaps we will never use, resulting in high memory
utilization especially for huge filesystem, when bitmaps might occupy
gigabytes of space.

This commit adds another backend to store bitmaps. It is based on
rbtrees and it stores just used extents of bitmaps. It means that it can
be more memory efficient in most cases.

I have done some limited benchmarking and it shows that rbtree backend
consumes approx 65% less memory that bitarray on 312GB filesystem aged
with Impression (default config). This number may grow significantly
with the filesystem size, but also it may be a lot lower (even negative)
if the inodes are very fragmented (need more benchmarking).

This commit itself does not enable the use of rbtree backend.

[ Simplified the code by avoiding unneeded memory allocation and
  deallocation of del_ext.  In addition, fixed a bug discovered by the
  tst_bitmaps tests: rb_unamrk_bmap() must return true if the bit was
  previously set in bitmap, and zero otherwise -- tytso ]

Signed-off-by: Lukas Czerner <lczerner@redhat.com>
Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 lib/ext2fs/Makefile.in    |   17 +-
 lib/ext2fs/blkmap64_rb.c  |  743 +++++++++++++++++++++++++++++++++++++++++++++
 lib/ext2fs/bmap64.h       |    1 +
 lib/ext2fs/ext2fs.h       |    1 +
 lib/ext2fs/gen_bitmap64.c |    3 +
 5 files changed, 760 insertions(+), 5 deletions(-)
 create mode 100644 lib/ext2fs/blkmap64_rb.c

diff --git a/lib/ext2fs/Makefile.in b/lib/ext2fs/Makefile.in
index cdf53b8..4c5ebed 100644
--- a/lib/ext2fs/Makefile.in
+++ b/lib/ext2fs/Makefile.in
@@ -27,6 +27,7 @@ OBJS= $(DEBUGFS_LIB_OBJS) $(RESIZE_LIB_OBJS) $(E2IMAGE_LIB_OBJS) \
 	bitmaps.o \
 	bitops.o \
 	blkmap64_ba.o \
+	blkmap64_rb.o \
 	blknum.o \
 	block.o \
 	bmap.o \
@@ -97,6 +98,7 @@ SRCS= ext2_err.c \
 	$(srcdir)/bitmaps.c \
 	$(srcdir)/bitops.c \
 	$(srcdir)/blkmap64_ba.c \
+	$(srcdir)/blkmap64_rb.c \
 	$(srcdir)/block.c \
 	$(srcdir)/bmap.c \
 	$(srcdir)/check_desc.c \
@@ -395,6 +397,9 @@ check:: tst_bitops tst_badblocks tst_iscan tst_types tst_icount \
 	LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) \
 		./tst_bitmaps -f $(srcdir)/tst_bitmaps_cmds > tst_bitmaps_out
 	diff $(srcdir)/tst_bitmaps_exp tst_bitmaps_out
+	LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) \
+		./tst_bitmaps -t 2 -f $(srcdir)/tst_bitmaps_cmds > tst_bitmaps_out
+	diff $(srcdir)/tst_bitmaps_exp tst_bitmaps_out
 
 installdirs::
 	$(E) "	MKINSTALLDIRS $(libdir) $(includedir)/ext2fs"
@@ -522,6 +527,12 @@ blkmap64_ba.o: $(srcdir)/blkmap64_ba.c $(top_builddir)/lib/config.h \
  $(top_srcdir)/lib/et/com_err.h $(srcdir)/ext2_io.h \
  $(top_builddir)/lib/ext2fs/ext2_err.h $(srcdir)/ext2_ext_attr.h \
  $(srcdir)/bitops.h $(srcdir)/bmap64.h
+blkmap64_rb.o: $(srcdir)/blkmap64_rb.c $(srcdir)/ext2_fs.h \
+ $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/ext2fsP.h \
+ $(srcdir)/ext2fs.h $(srcdir)/ext2_fs.h $(srcdir)/ext3_extents.h \
+ $(top_srcdir)/lib/et/com_err.h $(srcdir)/ext2_io.h \
+ $(top_builddir)/lib/ext2fs/ext2_err.h $(srcdir)/ext2_ext_attr.h \
+ $(srcdir)/bitops.h $(srcdir)/bmap64.h $(srcdir)/rbtree.h
 block.o: $(srcdir)/block.c $(top_builddir)/lib/config.h \
  $(top_builddir)/lib/dirpaths.h $(srcdir)/ext2_fs.h \
  $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/ext2fs.h \
@@ -921,8 +932,4 @@ write_bb_file.o: $(srcdir)/write_bb_file.c $(top_builddir)/lib/config.h \
  $(srcdir)/ext2_fs.h $(srcdir)/ext3_extents.h $(top_srcdir)/lib/et/com_err.h \
  $(srcdir)/ext2_io.h $(top_builddir)/lib/ext2fs/ext2_err.h \
  $(srcdir)/ext2_ext_attr.h $(srcdir)/bitops.h
-rbtree.o: $(srcdir)/rbtree.c $(srcdir)/ext2_fs.h \
- $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/ext2fs.h \
- $(srcdir)/ext2_fs.h $(srcdir)/ext3_extents.h $(top_srcdir)/lib/et/com_err.h \
- $(srcdir)/ext2_io.h $(top_builddir)/lib/ext2fs/ext2_err.h \
- $(srcdir)/ext2_ext_attr.h $(srcdir)/bitops.h
+rbtree.o: $(srcdir)/rbtree.c $(srcdir)/rbtree.h
diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c
new file mode 100644
index 0000000..31fc393
--- /dev/null
+++ b/lib/ext2fs/blkmap64_rb.c
@@ -0,0 +1,743 @@
+/*
+ * blkmap64_rb.c --- Simple rb-tree implementation for bitmaps
+ *
+ * (C)2010 Red Hat, Inc., Lukas Czerner <lczerner@redhat.com>
+ *
+ * %Begin-Header%
+ * This file may be redistributed under the terms of the GNU Public
+ * License.
+ * %End-Header%
+ */
+
+#include <stdio.h>
+#include <string.h>
+#if HAVE_UNISTD_H
+#include <unistd.h>
+#endif
+#include <fcntl.h>
+#include <time.h>
+#if HAVE_SYS_STAT_H
+#include <sys/stat.h>
+#endif
+#if HAVE_SYS_TYPES_H
+#include <sys/types.h>
+#endif
+
+#include "ext2_fs.h"
+#include "ext2fsP.h"
+#include "bmap64.h"
+#include "rbtree.h"
+
+#include <limits.h>
+
+struct bmap_rb_extent {
+	struct rb_node node;
+	__u64 start;
+	__u32 count;
+};
+
+struct ext2fs_rb_private {
+	struct rb_root root;
+	struct bmap_rb_extent **wcursor;
+	struct bmap_rb_extent **rcursor;
+};
+
+static int rb_insert_extent(__u64 start, __u64 count,
+			    struct ext2fs_rb_private *);
+static void rb_get_new_extent(struct bmap_rb_extent **, __u64, __u64);
+
+/* #define DEBUG_RB */
+
+#ifdef DEBUG_RB
+static void print_tree(struct rb_root *root)
+{
+	struct rb_node *node = NULL;
+	struct bmap_rb_extent *ext;
+
+	printf("\t\t\t=================================\n");
+	node = ext2fs_rb_first(root);
+	for (node = ext2fs_rb_first(root); node != NULL; 
+	     node = ext2fs_rb_next(node)) {
+		ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
+		printf("\t\t\t--> (%llu -> %llu)\n",
+			ext->start, ext->start + ext->count);
+	}
+	printf("\t\t\t=================================\n");
+}
+
+static int check_tree(struct rb_root *root, const char *msg)
+{
+	struct rb_node *new_node, *node, *next;
+	struct bmap_rb_extent *ext, *old = NULL;
+
+	for (node = ext2fs_rb_first(root); node;
+	     node = ext2fs_rb_next(node)) {
+		ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
+		if (ext->count <= 0) {
+			printf("Tree Error: count is crazy\n");
+			printf("extent: %llu -> %llu (%u)\n", ext->start,
+				ext->start + ext->count, ext->count);
+			goto err_out;
+		}
+		if (ext->start < 0) {
+			printf("Tree Error: start is crazy\n");
+			printf("extent: %llu -> %llu (%u)\n", ext->start,
+				ext->start + ext->count, ext->count);
+			goto err_out;
+		}
+
+		if (old) {
+			if (old->start > ext->start) {
+				printf("Tree Error: start is crazy\n");
+				printf("extent: %llu -> %llu (%u)\n",
+					old->start, old->start + old->count,
+					old->count);
+				printf("extent next: %llu -> %llu (%u)\n",
+					ext->start, ext->start + ext->count,
+					ext->count);
+				goto err_out;
+			}
+			if ((old->start + old->count) >= ext->start) {
+				printf("Tree Error: extent is crazy\n");
+				printf("extent: %llu -> %llu (%u)\n",
+					old->start, old->start + old->count,
+					old->count);
+				printf("extent next: %llu -> %llu (%u)\n",
+					ext->start, ext->start + ext->count,
+					ext->count);
+				goto err_out;
+			}
+		}
+		old = ext;
+	}
+	return 0;
+
+err_out:
+	printf("%s\n", msg);
+	print_tree(root);
+	exit(1);
+}
+#else
+#define check_tree(root, msg) 0
+#define print_tree(root, msg) 0
+#endif
+
+static void rb_get_new_extent(struct bmap_rb_extent **ext, __u64 start,
+			     __u64 count)
+{
+	struct bmap_rb_extent *new_ext;
+	int retval;
+
+	retval = ext2fs_get_mem(sizeof (struct bmap_rb_extent),
+				&new_ext);
+	if (retval) {
+		perror("ext2fs_get_mem");
+		exit(1);
+	}
+
+	new_ext->start = start;
+	new_ext->count = count;
+	*ext = new_ext;
+}
+
+inline
+static void rb_free_extent(struct ext2fs_rb_private *bp,
+			   struct bmap_rb_extent *ext)
+{
+	if (*bp->wcursor == ext)
+		*bp->wcursor = NULL;
+	if (*bp->rcursor == ext)
+		*bp->rcursor = NULL;
+	ext2fs_free_mem(&ext);
+}
+
+static errcode_t rb_alloc_private_data (ext2fs_generic_bitmap bitmap)
+{
+	struct ext2fs_rb_private *bp;
+	errcode_t	retval;
+
+	retval = ext2fs_get_mem(sizeof (struct ext2fs_rb_private), &bp);
+	if (retval)
+		return retval;
+
+	bp->root = RB_ROOT;
+	retval = ext2fs_get_mem(sizeof(struct bmap_rb_extent *), &bp->rcursor);
+	if (retval)
+		return retval;
+	retval = ext2fs_get_mem(sizeof(struct bmap_rb_extent *), &bp->wcursor);
+	if (retval)
+		return retval;
+	*bp->rcursor = NULL;
+	*bp->wcursor = NULL;
+
+	bitmap->private = (void *) bp;
+	return 0;
+}
+
+static errcode_t rb_new_bmap(ext2_filsys fs EXT2FS_ATTR((unused)),
+			     ext2fs_generic_bitmap bitmap)
+{
+	errcode_t	retval;
+
+	retval = rb_alloc_private_data (bitmap);
+	if (retval)
+		return retval;
+
+	return 0;
+}
+
+static void rb_free_tree(struct rb_root *root)
+{
+	struct bmap_rb_extent *ext;
+	struct rb_node *node, *next;
+
+	for (node = ext2fs_rb_first(root); node; node = next) {
+		next = ext2fs_rb_next(node);
+		ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
+		ext2fs_rb_erase(node, root);
+		ext2fs_free_mem(&ext);
+	}
+}
+
+static void rb_free_bmap(ext2fs_generic_bitmap bitmap)
+{
+	struct ext2fs_rb_private *bp;
+
+	bp = (struct ext2fs_rb_private *) bitmap->private;
+
+	rb_free_tree(&bp->root);
+	ext2fs_free_mem(&bp->rcursor);
+	ext2fs_free_mem(&bp->wcursor);
+	ext2fs_free_mem(&bp);
+	bp = 0;
+}
+
+static errcode_t rb_copy_bmap(ext2fs_generic_bitmap src,
+			      ext2fs_generic_bitmap dest)
+{
+	struct ext2fs_rb_private *src_bp, *dest_bp;
+	struct bmap_rb_extent *src_ext, *dest_ext;
+	struct rb_node *dest_node, *src_node, *dest_last, **n;
+	errcode_t retval = 0;
+
+	retval = rb_alloc_private_data (dest);
+	if (retval)
+		return retval;
+
+	src_bp = (struct ext2fs_rb_private *) src->private;
+	dest_bp = (struct ext2fs_rb_private *) dest->private;
+	*src_bp->rcursor = NULL;
+	*dest_bp->rcursor = NULL;
+
+	src_node = ext2fs_rb_first(&src_bp->root);
+	while (src_node) {
+		src_ext = ext2fs_rb_entry(src_node, struct bmap_rb_extent, node);
+		retval = ext2fs_get_mem(sizeof (struct bmap_rb_extent),
+					&dest_ext);
+		if (retval)
+			break;
+
+		memcpy(dest_ext, src_ext, sizeof(struct bmap_rb_extent));
+
+		dest_node = &dest_ext->node;
+		n = &dest_bp->root.rb_node;
+
+		dest_last = NULL;
+		if (*n) {
+			dest_last = ext2fs_rb_last(&dest_bp->root);
+			n = &(dest_last)->rb_right;
+		}
+
+		ext2fs_rb_link_node(dest_node, dest_last, n);
+		ext2fs_rb_insert_color(dest_node, &dest_bp->root);
+
+		src_node = ext2fs_rb_next(src_node);
+	}
+
+	return retval;
+}
+
+static void rb_truncate(__u64 new_max, struct rb_root *root)
+{
+	struct bmap_rb_extent *ext;
+	struct rb_node *node;
+
+	node = ext2fs_rb_last(root);
+	while (node) {
+		ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
+
+		if ((ext->start + ext->count - 1) <= new_max)
+			break;
+		else if (ext->start > new_max) {
+			ext2fs_rb_erase(node, root);
+			ext2fs_free_mem(&ext);
+			node = ext2fs_rb_last(root);
+			continue;
+		} else
+			ext->count = new_max - ext->start + 1;
+	}
+}
+
+static errcode_t rb_resize_bmap(ext2fs_generic_bitmap bmap,
+				__u64 new_end, __u64 new_real_end)
+{
+	struct ext2fs_rb_private *bp;
+
+	if (new_real_end >= bmap->real_end) {
+		bmap->end = new_end;
+		bmap->real_end = new_real_end;
+		return 0;
+	}
+
+	bp = (struct ext2fs_rb_private *) bmap->private;
+	*bp->rcursor = NULL;
+	*bp->wcursor = NULL;
+
+	/* truncate tree to new_real_end size */
+	rb_truncate(new_real_end, &bp->root);
+
+	bmap->end = new_end;
+	bmap->real_end = new_real_end;
+	return 0;
+
+}
+
+inline static int
+rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
+{
+	struct bmap_rb_extent *rcursor;
+	struct rb_node *parent = NULL;
+	struct rb_node **n = &bp->root.rb_node;
+	struct bmap_rb_extent *ext;
+	int i=0;
+
+	rcursor = *bp->rcursor;
+	if (!rcursor)
+		goto search_tree;
+
+	if (bit >= rcursor->start && bit < rcursor->start + rcursor->count)
+		return 1;
+
+	rcursor = *bp->wcursor;
+	if (!rcursor)
+		goto search_tree;
+
+	if (bit >= rcursor->start && bit < rcursor->start + rcursor->count)
+		return 1;
+
+search_tree:
+
+	while (*n) {
+		parent = *n;
+		ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node);
+		if (bit < ext->start)
+			n = &(*n)->rb_left;
+		else if (bit >= (ext->start + ext->count))
+			n = &(*n)->rb_right;
+		else {
+			*bp->rcursor = ext;
+			return 1;
+		}
+	}
+	return 0;
+}
+
+static int rb_insert_extent(__u64 start, __u64 count,
+			    struct ext2fs_rb_private *bp)
+{
+	struct rb_root *root = &bp->root;
+	struct rb_node *parent = NULL, **n = &root->rb_node;
+	struct rb_node *new_node, *node, *next;
+	struct bmap_rb_extent *new_ext;
+	struct bmap_rb_extent *ext;
+	int retval = 0;
+
+	ext = *bp->wcursor;
+	if (ext) {
+		if (start >= ext->start &&
+		    start <= (ext->start + ext->count))
+			goto got_extent;
+	}
+
+	while (*n) {
+		parent = *n;
+		ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node);
+
+		if (start < ext->start) {
+			n = &(*n)->rb_left;
+		} else if (start > (ext->start + ext->count)) {
+			n = &(*n)->rb_right;
+		} else {
+got_extent:
+			if ((start + count) <= (ext->start + ext->count))
+				return 1;
+
+			if ((ext->start + ext->count) == start)
+				retval = 0;
+			else
+				retval = 1;
+
+			count += (start - ext->start);
+			start = ext->start;
+			new_ext = ext;
+			new_node = &ext->node;
+
+			goto skip_insert;
+		}
+	}
+
+	rb_get_new_extent(&new_ext, start, count);
+
+	new_node = &new_ext->node;
+	ext2fs_rb_link_node(new_node, parent, n);
+	ext2fs_rb_insert_color(new_node, root);
+	*bp->wcursor = new_ext;
+
+	node = ext2fs_rb_prev(new_node);
+	if (node) {
+		ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
+		if ((ext->start + ext->count) == start) {
+			start = ext->start;
+			count += ext->count;
+			ext2fs_rb_erase(node, root);
+			rb_free_extent(bp, ext);
+		}
+	}
+
+skip_insert:
+	/* See if we can merge extent to the right */
+	for (node = ext2fs_rb_next(new_node); node != NULL; node = next) {
+		next = ext2fs_rb_next(node);
+		ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
+
+		if ((ext->start + ext->count) <= start)
+			continue;
+
+		/* No more merging */
+		if ((start + count) < ext->start)
+			break;
+
+		/* ext is embedded in new_ext interval */
+		if ((start + count) >= (ext->start + ext->count)) {
+			ext2fs_rb_erase(node, root);
+			rb_free_extent(bp, ext);
+			continue;
+		} else {
+		/* merge ext with new_ext */
+			count += ((ext->start + ext->count) -
+				  (start + count));
+			ext2fs_rb_erase(node, root);
+			rb_free_extent(bp, ext);
+			break;
+		}
+	}
+
+	new_ext->start = start;
+	new_ext->count = count;
+
+	return retval;
+}
+
+static int rb_remove_extent(__u64 start, __u64 count,
+			    struct ext2fs_rb_private *bp)
+{
+	struct rb_root *root = &bp->root;
+	struct rb_node *parent = NULL, **n = &root->rb_node;
+	struct rb_node *node;
+	struct bmap_rb_extent *ext;
+	__u64 new_start, new_count;
+	int retval = 0;
+
+	if (EXT2FS_RB_EMPTY_ROOT(root))
+		return 0;
+
+	while (*n) {
+		parent = *n;
+		ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node);
+		if (start < ext->start) {
+			n = &(*n)->rb_left;
+			continue;
+		} else if (start >= (ext->start + ext->count)) {
+			n = &(*n)->rb_right;
+			continue;
+		}
+
+		if ((start > ext->start) &&
+		    (start + count) < (ext->start + ext->count)) {
+			/* We have to split extent into two */
+			new_start = start + count;
+			new_count = (ext->start + ext->count) - new_start;
+
+			ext->count = start - ext->start;
+
+			rb_insert_extent(new_start, new_count, bp);
+			return 1;
+		}
+
+		if ((start + count) >= (ext->start + ext->count)) {
+			ext->count = start - ext->start;
+			retval = 1;
+		}
+
+		if (0 == ext->count) {
+			parent = ext2fs_rb_next(&ext->node);
+			ext2fs_rb_erase(&ext->node, root);
+			rb_free_extent(bp, ext);
+			break;
+		}
+
+		if (start == ext->start) {
+			ext->start += count;
+			ext->count -= count;
+			return 1;
+		}
+	}
+
+	/* See if we should delete or truncate extent on the right */
+	for (; parent != NULL; parent = node) {
+		node = ext2fs_rb_next(parent);
+		ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node);
+		if ((ext->start + ext->count) <= start)
+			continue;
+
+		/* No more extents to be removed/truncated */
+		if ((start + count) < ext->start)
+			break;
+
+		/* The entire extent is within the region to be removed */
+		if ((start + count) >= (ext->start + ext->count)) {
+			ext2fs_rb_erase(parent, root);
+			rb_free_extent(bp, ext);
+			retval = 1;
+			continue;
+		} else {
+			/* modify the last extent in reigon to be removed */
+			ext->count -= ((start + count) - ext->start);
+			ext->start = start + count;
+			retval = 1;
+			break;
+		}
+	}
+
+	return retval;
+}
+
+static int rb_mark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
+{
+	struct ext2fs_rb_private *bp;
+	int i;
+
+
+	bp = (struct ext2fs_rb_private *) bitmap->private;
+	arg -= bitmap->start;
+
+	return rb_insert_extent(arg, 1, bp);
+}
+
+static int rb_unmark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
+{
+	struct ext2fs_rb_private *bp;
+	int retval;
+
+	bp = (struct ext2fs_rb_private *) bitmap->private;
+	arg -= bitmap->start;
+
+	retval = rb_remove_extent(arg, 1, bp);
+	check_tree(&bp->root, __func__);
+
+	return retval;
+}
+
+inline
+static int rb_test_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
+{
+	struct ext2fs_rb_private *bp;
+
+	bp = (struct ext2fs_rb_private *) bitmap->private;
+	arg -= bitmap->start;
+
+	return rb_test_bit(bp, arg);
+}
+
+static void rb_mark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
+				unsigned int num)
+{
+	struct ext2fs_rb_private *bp;
+	struct bmap_rb_extent *new_ext;
+
+	bp = (struct ext2fs_rb_private *) bitmap->private;
+	arg -= bitmap->start;
+
+	rb_insert_extent(arg, num, bp);
+}
+
+static void rb_unmark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
+				  unsigned int num)
+{
+	struct ext2fs_rb_private *bp;
+	int ret;
+
+	bp = (struct ext2fs_rb_private *) bitmap->private;
+	arg -= bitmap->start;
+
+	rb_remove_extent(arg, num, bp);
+	check_tree(&bp->root, __func__);
+}
+
+static int rb_test_clear_bmap_extent(ext2fs_generic_bitmap bitmap,
+				     __u64 start, unsigned int len)
+{
+	struct rb_node *parent = NULL, **n;
+	struct rb_node *node, *next;
+	struct ext2fs_rb_private *bp;
+	struct bmap_rb_extent *ext;
+	int retval = 1;
+
+	bp = (struct ext2fs_rb_private *) bitmap->private;
+	n = &bp->root.rb_node;
+	start -= bitmap->start;
+
+	if ((len == 0) || EXT2FS_RB_EMPTY_ROOT(&bp->root))
+		return 1;
+
+	/*
+	 * If we find nothing, we should examine whole extent, but
+	 * when we find match, the extent is not clean, thus be return
+	 * false.
+	 */
+	while (*n) {
+		parent = *n;
+		ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node);
+		if (start < ext->start) {
+			n = &(*n)->rb_left;
+		} else if (start >= (ext->start + ext->count)) {
+			n = &(*n)->rb_right;
+		} else {
+			/*
+			 * We found extent int the tree -> extent is not
+			 * clean
+			 */
+			return 0;
+		}
+	}
+
+	node = parent;
+	while (node) {
+		next = ext2fs_rb_next(node);
+		ext = ext2fs_rb_entry(node, struct bmap_rb_extent, node);
+		node = next;
+
+		if ((ext->start + ext->count) <= start)
+			continue;
+
+		/* No more merging */
+		if ((start + len) <= ext->start)
+			break;
+
+		retval = 0;
+		break;
+	}
+	return retval;
+}
+
+static errcode_t rb_set_bmap_range(ext2fs_generic_bitmap bitmap,
+				     __u64 start, size_t num, void *in)
+{
+	struct ext2fs_rb_private *bp;
+	size_t i;
+	int ret;
+
+	bp = (struct ext2fs_rb_private *) bitmap->private;
+
+	for (i = 0; i < num; i++) {
+		ret = ext2fs_test_bit(i, in);
+		if (ret)
+			rb_insert_extent(start + i - bitmap->start, 1, bp);
+	}
+
+	return 0;
+}
+
+static errcode_t rb_get_bmap_range(ext2fs_generic_bitmap bitmap,
+				     __u64 start, size_t num, void *out)
+{
+
+	struct rb_node *parent = NULL, *next, **n;
+	struct ext2fs_rb_private *bp;
+	struct bmap_rb_extent *ext;
+	__u64 pos;
+
+	bp = (struct ext2fs_rb_private *) bitmap->private;
+	n = &bp->root.rb_node;
+	start -= bitmap->start;
+
+	if (EXT2FS_RB_EMPTY_ROOT(&bp->root))
+		return 0;
+
+	while (*n) {
+		parent = *n;
+		ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node);
+		if (start < ext->start) {
+			n = &(*n)->rb_left;
+		} else if (start >= (ext->start + ext->count)) {
+			n = &(*n)->rb_right;
+		} else
+			break;
+	}
+
+	pos = start;
+	for (; parent != NULL; parent = next) {
+		next = ext2fs_rb_next(parent);
+		ext = ext2fs_rb_entry(parent, struct bmap_rb_extent, node);
+
+		while (((pos - start) < num) &&
+			(pos < ext->start)) {
+			ext2fs_fast_clear_bit64((pos - start), out);
+			pos++;
+		}
+
+		if ((pos - start) >= num)
+			return 0;
+
+		while (((pos - start) < num) &&
+			(pos < (ext->start + ext->count))) {
+			ext2fs_fast_set_bit64((pos - start), out);
+			pos++;
+		}
+	}
+
+	while ((pos - start) < num) {
+		ext2fs_fast_clear_bit64((pos - start), out);
+		pos++;
+	}
+
+	return 0;
+}
+
+static void rb_clear_bmap(ext2fs_generic_bitmap bitmap)
+{
+	struct ext2fs_rb_private *bp;
+
+	bp = (struct ext2fs_rb_private *) bitmap->private;
+
+	rb_free_tree(&bp->root);
+	*bp->rcursor = NULL;
+	*bp->wcursor = NULL;
+}
+
+struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = {
+	.type = EXT2FS_BMAP64_RBTREE,
+	.new_bmap = rb_new_bmap,
+	.free_bmap = rb_free_bmap,
+	.copy_bmap = rb_copy_bmap,
+	.resize_bmap = rb_resize_bmap,
+	.mark_bmap = rb_mark_bmap,
+	.unmark_bmap = rb_unmark_bmap,
+	.test_bmap = rb_test_bmap,
+	.test_clear_bmap_extent = rb_test_clear_bmap_extent,
+	.mark_bmap_extent = rb_mark_bmap_extent,
+	.unmark_bmap_extent = rb_unmark_bmap_extent,
+	.set_bmap_range = rb_set_bmap_range,
+	.get_bmap_range = rb_get_bmap_range,
+	.clear_bmap = rb_clear_bmap,
+};
diff --git a/lib/ext2fs/bmap64.h b/lib/ext2fs/bmap64.h
index 3056544..21d24ad 100644
--- a/lib/ext2fs/bmap64.h
+++ b/lib/ext2fs/bmap64.h
@@ -60,3 +60,4 @@ struct ext2_bitmap_ops {
 };
 
 extern struct ext2_bitmap_ops ext2fs_blkmap64_bitarray;
+extern struct ext2_bitmap_ops ext2fs_blkmap64_rbtree;
diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h
index d90a8b1..5ffb036 100644
--- a/lib/ext2fs/ext2fs.h
+++ b/lib/ext2fs/ext2fs.h
@@ -293,6 +293,7 @@ struct struct_ext2_filsys {
  */
 
 #define EXT2FS_BMAP64_BITARRAY	1
+#define EXT2FS_BMAP64_RBTREE	2
 
 /*
  * Return flags for the block iterator functions
diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c
index e1b4f42..c9b4051 100644
--- a/lib/ext2fs/gen_bitmap64.c
+++ b/lib/ext2fs/gen_bitmap64.c
@@ -95,6 +95,9 @@ errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
 	case EXT2FS_BMAP64_BITARRAY:
 		ops = &ext2fs_blkmap64_bitarray;
 		break;
+	case EXT2FS_BMAP64_RBTREE:
+		ops = &ext2fs_blkmap64_rbtree;
+		break;
 	default:
 		return EINVAL;
 	}
-- 
1.7.8.11.gefc1f.dirty

[PATCH 05/10] libext2fs: add pseudo bitmap backend type EXT2FS_BMAP64_AUTODIR

[Theodore Ts'o]

This backend type will automatically switch between the bitarray and
the rbtree backend based on the number of directories in the file
system.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 lib/ext2fs/Makefile.in    |    3 +++
 lib/ext2fs/ext2fs.h       |    1 +
 lib/ext2fs/gen_bitmap64.c |    8 ++++++++
 3 files changed, 12 insertions(+), 0 deletions(-)

diff --git a/lib/ext2fs/Makefile.in b/lib/ext2fs/Makefile.in
index 4c5ebed..ef55494 100644
--- a/lib/ext2fs/Makefile.in
+++ b/lib/ext2fs/Makefile.in
@@ -400,6 +400,9 @@ check:: tst_bitops tst_badblocks tst_iscan tst_types tst_icount \
 	LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) \
 		./tst_bitmaps -t 2 -f $(srcdir)/tst_bitmaps_cmds > tst_bitmaps_out
 	diff $(srcdir)/tst_bitmaps_exp tst_bitmaps_out
+	LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) \
+		./tst_bitmaps -t 3 -f $(srcdir)/tst_bitmaps_cmds > tst_bitmaps_out
+	diff $(srcdir)/tst_bitmaps_exp tst_bitmaps_out
 
 installdirs::
 	$(E) "	MKINSTALLDIRS $(libdir) $(includedir)/ext2fs"
diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h
index 5ffb036..f2df66e 100644
--- a/lib/ext2fs/ext2fs.h
+++ b/lib/ext2fs/ext2fs.h
@@ -294,6 +294,7 @@ struct struct_ext2_filsys {
 
 #define EXT2FS_BMAP64_BITARRAY	1
 #define EXT2FS_BMAP64_RBTREE	2
+#define EXT2FS_BMAP64_AUTODIR	3
 
 /*
  * Return flags for the block iterator functions
diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c
index c9b4051..7b066a2 100644
--- a/lib/ext2fs/gen_bitmap64.c
+++ b/lib/ext2fs/gen_bitmap64.c
@@ -86,6 +86,7 @@ errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
 {
 	ext2fs_generic_bitmap	bitmap;
 	struct ext2_bitmap_ops	*ops;
+	ext2_ino_t num_dirs;
 	errcode_t retval;
 
 	if (!type)
@@ -98,6 +99,13 @@ errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
 	case EXT2FS_BMAP64_RBTREE:
 		ops = &ext2fs_blkmap64_rbtree;
 		break;
+	case EXT2FS_BMAP64_AUTODIR:
+		retval = ext2fs_get_num_dirs(fs, &num_dirs);
+		if (retval || num_dirs > (fs->super->s_inodes_count / 320))
+			ops = &ext2fs_blkmap64_bitarray;
+		else
+			ops = &ext2fs_blkmap64_rbtree;
+		break;
 	default:
 		return EINVAL;
 	}
-- 
1.7.8.11.gefc1f.dirty

[PATCH 06/10] e2fsck: fix pass5 bug when using two different bitmap backends

[Theodore Ts'o]

The pass5 checks would fail if the expected and current {inode,block}
bitmaps used different back ends that returned different non-zero
values from the test_*_bitmap() functions.  Fix this by changing
"(actual == bitmap)" to "(!actual == !bitmap)".

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 e2fsck/pass5.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/e2fsck/pass5.c b/e2fsck/pass5.c
index a60e84a..1e836e3 100644
--- a/e2fsck/pass5.c
+++ b/e2fsck/pass5.c
@@ -279,7 +279,7 @@ redo_counts:
 		else
 			bitmap = ext2fs_fast_test_block_bitmap2(fs->block_map, i);
 
-		if (actual == bitmap)
+		if (!actual == !bitmap)
 			goto do_counts;
 
 		if (!actual && bitmap) {
@@ -511,7 +511,7 @@ redo_counts:
 			bitmap = actual;
 		else if (!skip_group)
 			bitmap = ext2fs_fast_test_inode_bitmap2(fs->inode_map, i);
-		if (actual == bitmap)
+		if (!actual == !bitmap)
 			goto do_counts;
 
 		if (!actual && bitmap) {
-- 
1.7.8.11.gefc1f.dirty

[PATCH 07/10] libext2fs: use the rbtree bitmap by default when initializing a file system

[Theodore Ts'o]

This change causes the max resident memory of mke2fs, as reported by
/usr/bin/time, to drop from 9296k to 5328k when formatting a 25
gig volume.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 lib/ext2fs/initialize.c |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

diff --git a/lib/ext2fs/initialize.c b/lib/ext2fs/initialize.c
index b050a0a..a63ea18 100644
--- a/lib/ext2fs/initialize.c
+++ b/lib/ext2fs/initialize.c
@@ -112,6 +112,7 @@ errcode_t ext2fs_initialize(const char *name, int flags,
 	fs->magic = EXT2_ET_MAGIC_EXT2FS_FILSYS;
 	fs->flags = flags | EXT2_FLAG_RW;
 	fs->umask = 022;
+	fs->default_bitmap_type = EXT2FS_BMAP64_RBTREE;
 #ifdef WORDS_BIGENDIAN
 	fs->flags |= EXT2_FLAG_SWAP_BYTES;
 #endif
-- 
1.7.8.11.gefc1f.dirty

[PATCH 08/10] e2fsck: use different bitmap types as appropriate

[Theodore Ts'o]

Now that we have multiple backend implementations of the bitmap code,
this commit teaches e2fsck to use either the most appropriate backend
for each use case.

Since we don't know for sure if we will get it all right, the default
choices can be overridden via e2fsck.conf.  The various definitions
are shown here, with the current defaults (which may change as we add
more bitmap implementations and as learn what works better).

; EXT2FS_BAMP64_BITARRAY is 1
; EXT2FS_BMAP64_RBTREE is 2
; EXT2FS_BMAP64_AUTODIR is 3
[bitmaps]
	inode_used_map = 2	; pass1
	inode_dir_map = 3	; pass1
	inode_reg_map = 2	; pass1
	block_found_map = 2	; pass1
	inode_bad_map = 2	; pass1
	inode_imagic_map = 2	; pass1
	block_dup_map = 2	; pass1
	block_ea_map = 2	; pass1
	inode_link_info = 2	; pass1
	inode_dup_map = 2	; pass1b
	inode_done_map = 3	; pass3
	inode_loop_detect = 3	; pass3
	fs_bitmaps = 2

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 e2fsck/e2fsck.h     |   20 ++++++++++++++++
 e2fsck/pass1.c      |   62 +++++++++++++++++++++++++++++++-------------------
 e2fsck/pass1b.c     |    6 +++-
 e2fsck/pass2.c      |    7 +++++-
 e2fsck/pass3.c      |    7 +++--
 e2fsck/unix.c       |    4 +++
 e2fsck/util.c       |   61 ++++++++++++++++++++++++++++++++++++++++++++++++++
 lib/ext2fs/ext2fs.h |    1 -
 8 files changed, 137 insertions(+), 31 deletions(-)

diff --git a/e2fsck/e2fsck.h b/e2fsck/e2fsck.h
index d225d89..ed8b0c7 100644
--- a/e2fsck/e2fsck.h
+++ b/e2fsck/e2fsck.h
@@ -540,6 +540,26 @@ extern int write_all(int fd, char *buf, size_t count);
 void dump_mmp_msg(struct mmp_struct *mmp, const char *msg);
 errcode_t e2fsck_mmp_update(ext2_filsys fs);
 
+extern void e2fsck_set_bitmap_type(ext2_filsys fs,
+				   unsigned int default_type,
+				   const char *profile_name,
+				   unsigned int *old_type);
+extern errcode_t e2fsck_allocate_inode_bitmap(ext2_filsys fs,
+					      const char *descr,
+					      int default_type,
+					      const char *profile_name,
+					      ext2fs_inode_bitmap *ret);
+extern errcode_t e2fsck_allocate_block_bitmap(ext2_filsys fs,
+					      const char *descr,
+					      int default_type,
+					      const char *profile_name,
+					      ext2fs_block_bitmap *ret);
+extern errcode_t e2fsck_allocate_subcluster_bitmap(ext2_filsys fs,
+						   const char *descr,
+						   int default_type,
+						   const char *profile_name,
+						   ext2fs_block_bitmap *ret);
+
 /* unix.c */
 extern void e2fsck_clear_progbar(e2fsck_t ctx);
 extern int e2fsck_simple_progress(e2fsck_t ctx, const char *label,
diff --git a/e2fsck/pass1.c b/e2fsck/pass1.c
index d225026..5faa093 100644
--- a/e2fsck/pass1.c
+++ b/e2fsck/pass1.c
@@ -557,6 +557,7 @@ void e2fsck_pass1(e2fsck_t ctx)
 	struct		scan_callback_struct scan_struct;
 	struct ext2_super_block *sb = ctx->fs->super;
 	const char	*old_op;
+	unsigned int	save_type;
 	int		imagic_fs, extent_fs;
 	int		busted_fs_time = 0;
 	int		inode_size;
@@ -594,33 +595,38 @@ void e2fsck_pass1(e2fsck_t ctx)
 	/*
 	 * Allocate bitmaps structures
 	 */
-	pctx.errcode = ext2fs_allocate_inode_bitmap(fs, _("in-use inode map"),
-					      &ctx->inode_used_map);
+	pctx.errcode = e2fsck_allocate_inode_bitmap(fs, _("in-use inode map"),
+						    EXT2FS_BMAP64_RBTREE,
+						    "inode_used_map",
+						    &ctx->inode_used_map);
 	if (pctx.errcode) {
 		pctx.num = 1;
 		fix_problem(ctx, PR_1_ALLOCATE_IBITMAP_ERROR, &pctx);
 		ctx->flags |= E2F_FLAG_ABORT;
 		return;
 	}
-	pctx.errcode = ext2fs_allocate_inode_bitmap(fs,
-				_("directory inode map"), &ctx->inode_dir_map);
+	pctx.errcode = e2fsck_allocate_inode_bitmap(fs,
+			_("directory inode map"),
+			EXT2FS_BMAP64_AUTODIR,
+			"inode_dir_map", &ctx->inode_dir_map);
 	if (pctx.errcode) {
 		pctx.num = 2;
 		fix_problem(ctx, PR_1_ALLOCATE_IBITMAP_ERROR, &pctx);
 		ctx->flags |= E2F_FLAG_ABORT;
 		return;
 	}
-	pctx.errcode = ext2fs_allocate_inode_bitmap(fs,
-			_("regular file inode map"), &ctx->inode_reg_map);
+	pctx.errcode = e2fsck_allocate_inode_bitmap(fs,
+			_("regular file inode map"), EXT2FS_BMAP64_RBTREE,
+			"inode_reg_map", &ctx->inode_reg_map);
 	if (pctx.errcode) {
 		pctx.num = 6;
 		fix_problem(ctx, PR_1_ALLOCATE_IBITMAP_ERROR, &pctx);
 		ctx->flags |= E2F_FLAG_ABORT;
 		return;
 	}
-	pctx.errcode = ext2fs_allocate_subcluster_bitmap(fs,
-						_("in-use block map"),
-						&ctx->block_found_map);
+	pctx.errcode = e2fsck_allocate_subcluster_bitmap(fs,
+			_("in-use block map"), EXT2FS_BMAP64_RBTREE,
+			"block_found_map", &ctx->block_found_map);
 	if (pctx.errcode) {
 		pctx.num = 1;
 		fix_problem(ctx, PR_1_ALLOCATE_BBITMAP_ERROR, &pctx);
@@ -628,9 +634,14 @@ void e2fsck_pass1(e2fsck_t ctx)
 		return;
 	}
 	e2fsck_setup_tdb_icount(ctx, 0, &ctx->inode_link_info);
-	if (!ctx->inode_link_info)
+	if (!ctx->inode_link_info) {
+		e2fsck_set_bitmap_type(fs, EXT2FS_BMAP64_RBTREE,
+				       "inode_link_info", &save_type);
 		pctx.errcode = ext2fs_create_icount2(fs, 0, 0, 0,
 						     &ctx->inode_link_info);
+		fs->default_bitmap_type = save_type;
+	}
+
 	if (pctx.errcode) {
 		fix_problem(ctx, PR_1_ALLOCATE_ICOUNT, &pctx);
 		ctx->flags |= E2F_FLAG_ABORT;
@@ -1331,8 +1342,9 @@ static void mark_inode_bad(e2fsck_t ctx, ino_t ino)
 	if (!ctx->inode_bad_map) {
 		clear_problem_context(&pctx);
 
-		pctx.errcode = ext2fs_allocate_inode_bitmap(ctx->fs,
-			    _("bad inode map"), &ctx->inode_bad_map);
+		pctx.errcode = e2fsck_allocate_inode_bitmap(ctx->fs,
+				_("bad inode map"), EXT2FS_BMAP64_RBTREE,
+				"inode_bad_map", &ctx->inode_bad_map);
 		if (pctx.errcode) {
 			pctx.num = 3;
 			fix_problem(ctx, PR_1_ALLOCATE_IBITMAP_ERROR, &pctx);
@@ -1353,9 +1365,9 @@ static void alloc_bb_map(e2fsck_t ctx)
 	struct		problem_context pctx;
 
 	clear_problem_context(&pctx);
-	pctx.errcode = ext2fs_allocate_inode_bitmap(ctx->fs,
-					      _("inode in bad block map"),
-					      &ctx->inode_bb_map);
+	pctx.errcode = e2fsck_allocate_inode_bitmap(ctx->fs,
+			_("inode in bad block map"), EXT2FS_BMAP64_RBTREE,
+			"inode_bb_map", &ctx->inode_bb_map);
 	if (pctx.errcode) {
 		pctx.num = 4;
 		fix_problem(ctx, PR_1_ALLOCATE_IBITMAP_ERROR, &pctx);
@@ -1373,9 +1385,9 @@ static void alloc_imagic_map(e2fsck_t ctx)
 	struct		problem_context pctx;
 
 	clear_problem_context(&pctx);
-	pctx.errcode = ext2fs_allocate_inode_bitmap(ctx->fs,
-					      _("imagic inode map"),
-					      &ctx->inode_imagic_map);
+	pctx.errcode = e2fsck_allocate_inode_bitmap(ctx->fs,
+			_("imagic inode map"), EXT2FS_BMAP64_RBTREE,
+			"inode_imagic_map", &ctx->inode_imagic_map);
 	if (pctx.errcode) {
 		pctx.num = 5;
 		fix_problem(ctx, PR_1_ALLOCATE_IBITMAP_ERROR, &pctx);
@@ -1400,9 +1412,10 @@ static _INLINE_ void mark_block_used(e2fsck_t ctx, blk64_t block)
 
 	if (ext2fs_fast_test_block_bitmap2(ctx->block_found_map, block)) {
 		if (!ctx->block_dup_map) {
-			pctx.errcode = ext2fs_allocate_block_bitmap(ctx->fs,
-			      _("multiply claimed block map"),
-			      &ctx->block_dup_map);
+			pctx.errcode = e2fsck_allocate_block_bitmap(ctx->fs,
+					_("multiply claimed block map"),
+					EXT2FS_BMAP64_RBTREE, "block_dup_map",
+					&ctx->block_dup_map);
 			if (pctx.errcode) {
 				pctx.num = 3;
 				fix_problem(ctx, PR_1_ALLOCATE_BBITMAP_ERROR,
@@ -1500,9 +1513,10 @@ static int check_ext_attr(e2fsck_t ctx, struct problem_context *pctx,
 
 	/* If ea bitmap hasn't been allocated, create it */
 	if (!ctx->block_ea_map) {
-		pctx->errcode = ext2fs_allocate_block_bitmap(fs,
-						      _("ext attr block map"),
-						      &ctx->block_ea_map);
+		pctx->errcode = e2fsck_allocate_block_bitmap(fs,
+					_("ext attr block map"),
+					EXT2FS_BMAP64_RBTREE, "block_ea_map",
+					&ctx->block_ea_map);
 		if (pctx->errcode) {
 			pctx->num = 2;
 			fix_problem(ctx, PR_1_ALLOCATE_BBITMAP_ERROR, pctx);
diff --git a/e2fsck/pass1b.c b/e2fsck/pass1b.c
index a9eecd2..93fb630 100644
--- a/e2fsck/pass1b.c
+++ b/e2fsck/pass1b.c
@@ -218,8 +218,10 @@ void e2fsck_pass1_dupblocks(e2fsck_t ctx, char *block_buf)
 
 	clear_problem_context(&pctx);
 
-	pctx.errcode = ext2fs_allocate_inode_bitmap(fs,
-		      _("multiply claimed inode map"), &inode_dup_map);
+	pctx.errcode = e2fsck_allocate_inode_bitmap(fs,
+			_("multiply claimed inode map"),
+			EXT2FS_BMAP64_RBTREE, "inode_dup_map",
+			&inode_dup_map);
 	if (pctx.errcode) {
 		fix_problem(ctx, PR_1B_ALLOCATE_IBITMAP_ERROR, &pctx);
 		ctx->flags |= E2F_FLAG_ABORT;
diff --git a/e2fsck/pass2.c b/e2fsck/pass2.c
index 103b155..882950d 100644
--- a/e2fsck/pass2.c
+++ b/e2fsck/pass2.c
@@ -91,6 +91,7 @@ void e2fsck_pass2(e2fsck_t ctx)
 	struct check_dir_struct cd;
 	struct dx_dir_info	*dx_dir;
 	struct dx_dirblock_info	*dx_db, *dx_parent;
+	unsigned int		save_type;
 	int			b;
 	int			i, depth;
 	problem_t		code;
@@ -110,11 +111,15 @@ void e2fsck_pass2(e2fsck_t ctx)
 				&ctx->inode_count);
 	if (ctx->inode_count)
 		cd.pctx.errcode = 0;
-	else
+	else {
+		e2fsck_set_bitmap_type(fs, EXT2FS_BMAP64_RBTREE,
+				       "inode_count", &save_type);
 		cd.pctx.errcode = ext2fs_create_icount2(fs,
 						EXT2_ICOUNT_OPT_INCREMENT,
 						0, ctx->inode_link_info,
 						&ctx->inode_count);
+		fs->default_bitmap_type = save_type;
+	}
 	if (cd.pctx.errcode) {
 		fix_problem(ctx, PR_2_ALLOCATE_ICOUNT, &cd.pctx);
 		ctx->flags |= E2F_FLAG_ABORT;
diff --git a/e2fsck/pass3.c b/e2fsck/pass3.c
index 7164aa9..565b8e3 100644
--- a/e2fsck/pass3.c
+++ b/e2fsck/pass3.c
@@ -74,8 +74,9 @@ void e2fsck_pass3(e2fsck_t ctx)
 	/*
 	 * Allocate some bitmaps to do loop detection.
 	 */
-	pctx.errcode = ext2fs_allocate_inode_bitmap(fs, _("inode done bitmap"),
-						    &inode_done_map);
+	pctx.errcode = e2fsck_allocate_inode_bitmap(fs, _("inode done bitmap"),
+					EXT2FS_BMAP64_AUTODIR,
+					"inode_done_map", &inode_done_map);
 	if (pctx.errcode) {
 		pctx.num = 2;
 		fix_problem(ctx, PR_3_ALLOCATE_IBITMAP_ERROR, &pctx);
@@ -318,7 +319,7 @@ static int check_directory(e2fsck_t ctx, ext2_ino_t dir,
 			if (inode_loop_detect)
 				ext2fs_clear_inode_bitmap(inode_loop_detect);
 			else {
-				pctx->errcode = ext2fs_allocate_inode_bitmap(fs, _("inode loop detection bitmap"), &inode_loop_detect);
+				pctx->errcode = e2fsck_allocate_inode_bitmap(fs, _("inode loop detection bitmap"), EXT2FS_BMAP64_AUTODIR, "inode_loop_detect", &inode_loop_detect);
 				if (pctx->errcode) {
 					pctx->num = 1;
 					fix_problem(ctx,
diff --git a/e2fsck/unix.c b/e2fsck/unix.c
index d2a8c80..c38b67a 100644
--- a/e2fsck/unix.c
+++ b/e2fsck/unix.c
@@ -1002,6 +1002,10 @@ static errcode_t try_open_fs(e2fsck_t ctx, int flags, io_manager io_ptr,
 	} else
 		retval = ext2fs_open2(ctx->filesystem_name, ctx->io_options,
 				      flags, 0, 0, io_ptr, ret_fs);
+
+	if (ret_fs)
+		e2fsck_set_bitmap_type(*ret_fs, EXT2FS_BMAP64_RBTREE,
+				       "default", NULL);
 	return retval;
 }
 
diff --git a/e2fsck/util.c b/e2fsck/util.c
index f00734e..6e3a1dc 100644
--- a/e2fsck/util.c
+++ b/e2fsck/util.c
@@ -237,6 +237,7 @@ void e2fsck_read_bitmaps(e2fsck_t ctx)
 	ext2_filsys fs = ctx->fs;
 	errcode_t	retval;
 	const char	*old_op;
+	unsigned int	save_type;
 
 	if (ctx->invalid_bitmaps) {
 		com_err(ctx->program_name, 0,
@@ -246,7 +247,10 @@ void e2fsck_read_bitmaps(e2fsck_t ctx)
 	}
 
 	old_op = ehandler_operation(_("reading inode and block bitmaps"));
+	e2fsck_set_bitmap_type(fs, EXT2FS_BMAP64_RBTREE, "fs_bitmaps",
+			       &save_type);
 	retval = ext2fs_read_bitmaps(fs);
+	fs->default_bitmap_type = save_type;
 	ehandler_operation(old_op);
 	if (retval) {
 		com_err(ctx->program_name, retval,
@@ -757,3 +761,60 @@ errcode_t e2fsck_mmp_update(ext2_filsys fs)
 
 	return retval;
 }
+
+void e2fsck_set_bitmap_type(ext2_filsys fs, unsigned int default_type,
+			    const char *profile_name, unsigned int *old_type)
+{
+	unsigned type;
+	errcode_t	retval;
+
+	if (old_type)
+		*old_type = fs->default_bitmap_type;
+	profile_get_uint(e2fsck_global_ctx->profile, "bitmaps",
+			 profile_name, 0, default_type, &type);
+	profile_get_uint(e2fsck_global_ctx->profile, "bitmaps",
+			 "all", 0, type, &type);
+	fs->default_bitmap_type = type ? type : default_type;
+}
+
+errcode_t e2fsck_allocate_inode_bitmap(ext2_filsys fs, const char *descr,
+				       int deftype,
+				       const char *name,
+				       ext2fs_inode_bitmap *ret)
+{
+	errcode_t	retval;
+	unsigned int	save_type;
+
+	e2fsck_set_bitmap_type(fs, deftype, name, &save_type);
+	retval = ext2fs_allocate_inode_bitmap(fs, descr, ret);
+	fs->default_bitmap_type = save_type;
+	return retval;
+}
+
+errcode_t e2fsck_allocate_block_bitmap(ext2_filsys fs, const char *descr,
+				       int deftype,
+				       const char *name,
+				       ext2fs_block_bitmap *ret)
+{
+	errcode_t	retval;
+	unsigned int	save_type;
+
+	e2fsck_set_bitmap_type(fs, deftype, name, &save_type);
+	retval = ext2fs_allocate_block_bitmap(fs, descr, ret);
+	fs->default_bitmap_type = save_type;
+	return retval;
+}
+
+errcode_t e2fsck_allocate_subcluster_bitmap(ext2_filsys fs, const char *descr,
+					    int deftype,
+					    const char *name,
+					    ext2fs_block_bitmap *ret)
+{
+	errcode_t	retval;
+	unsigned int	save_type;
+
+	e2fsck_set_bitmap_type(fs, deftype, name, &save_type);
+	retval = ext2fs_allocate_subcluster_bitmap(fs, descr, ret);
+	fs->default_bitmap_type = save_type;
+	return retval;
+}
diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h
index f2df66e..3f8333f 100644
--- a/lib/ext2fs/ext2fs.h
+++ b/lib/ext2fs/ext2fs.h
@@ -291,7 +291,6 @@ struct struct_ext2_filsys {
 /*
  * 64-bit bitmap backend types
  */

[PATCH 09/10] libext2fs: adjust the description when copying a bitmap

[Theodore Ts'o]

Label the copy of a bitmap as "copy of ..." so that the bitmap's
description is more descriptive.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 lib/ext2fs/gen_bitmap64.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c
index 7b066a2..9dcca03 100644
--- a/lib/ext2fs/gen_bitmap64.c
+++ b/lib/ext2fs/gen_bitmap64.c
@@ -212,12 +212,12 @@ errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap src,
 
 	descr = src->description;
 	if (descr) {
-		retval = ext2fs_get_mem(strlen(descr)+1, &new_descr);
+		retval = ext2fs_get_mem(strlen(descr)+10, &new_descr);
 		if (retval) {
 			ext2fs_free_mem(&new_bmap);
 			return retval;
 		}
-		strcpy(new_descr, descr);
+		sprintf(new_descr, "copy of %s", descr);
 		new_bmap->description = new_descr;
 	}
 
-- 
1.7.8.11.gefc1f.dirty

[PATCH 10/10] libext2fs: add bitmap statistics

[Theodore Ts'o]

From: Lukas Czerner <lczerner@redhat.com>

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.

[ Changed to provide basic statistics when enabled with the
  E2FSPROGS_BITMAPS_STATS environment variable -- tytso]

Signed-off-by: Lukas Czerner <lczerner@redhat.com>
Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 lib/ext2fs/blkmap64_ba.c  |    8 +++
 lib/ext2fs/blkmap64_rb.c  |   85 ++++++++++++++++++++++++++-
 lib/ext2fs/bmap64.h       |   32 ++++++++++
 lib/ext2fs/ext2fs.h       |    4 +
 lib/ext2fs/gen_bitmap64.c |  140 +++++++++++++++++++++++++++++++++++++++++++-
 lib/ext2fs/icount.c       |    4 +-
 6 files changed, 265 insertions(+), 8 deletions(-)

diff --git a/lib/ext2fs/blkmap64_ba.c b/lib/ext2fs/blkmap64_ba.c
index 9253af2..3f0c643 100644
--- a/lib/ext2fs/blkmap64_ba.c
+++ b/lib/ext2fs/blkmap64_ba.c
@@ -310,6 +310,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, "%16llu 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,
@@ -325,4 +332,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 31fc393..aba7cfd 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_OPS
+	__u64 mark_hit;
+	__u64 test_hit;
+#endif
 };
 
 static int rb_insert_extent(__u64 start, __u64 count,
@@ -170,6 +174,11 @@ static errcode_t rb_alloc_private_data (ext2fs_generic_bitmap bitmap)
 	*bp->rcursor = NULL;
 	*bp->wcursor = NULL;
 
+#ifdef BMAP_STATS_OPS
+	bp->test_hit = 0;
+	bp->mark_hit = 0;
+#endif
+
 	bitmap->private = (void *) bp;
 	return 0;
 }
@@ -315,8 +324,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_OPS
+		bp->test_hit++;
+#endif
 		return 1;
+	}
 
 	rcursor = *bp->wcursor;
 	if (!rcursor)
@@ -355,8 +368,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_OPS
+			bp->mark_hit++;
+#endif
 			goto got_extent;
+		}
 	}
 
 	while (*n) {
@@ -725,6 +742,69 @@ 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 = ext2fs_rb_first(&bp->root);
+	for (node = ext2fs_rb_first(&bp->root); node != NULL;
+	     node = ext2fs_rb_next(node)) {
+		ext = ext2fs_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);
+#ifdef BMAP_STATS_OPS
+	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);
+#endif
+	fprintf(stderr, "%16llu extents (%llu bytes)\n",
+		count, ((count * sizeof(struct bmap_rb_extent)) +
+			sizeof(struct ext2fs_rb_private)));
+ 	fprintf(stderr, "%16llu bits minimum size\n",
+		min_size);
+	fprintf(stderr, "%16llu bits maximum size\n"
+		"%16llu bits average size\n",
+		max_size, avg_size);
+	fprintf(stderr, "%16llu bits set in bitmap (out of %llu)\n", size,
+		bitmap->real_end - bitmap->start);
+	fprintf(stderr,
+		"%16.4lf memory / bitmap bit memory ratio (bitarray = 1)\n",
+		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,
@@ -740,4 +820,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 21d24ad..288e1b6 100644
--- a/lib/ext2fs/bmap64.h
+++ b/lib/ext2fs/bmap64.h
@@ -9,6 +9,34 @@
  * %End-Header%
  */
 
+struct ext2_bmap_statistics {
+	int		type;
+	struct timeval	created;
+
+#ifdef BMAP_STATS_OPS
+	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;
+#endif /* BMAP_STATS_OPS */
+};
+
+
 struct ext2fs_struct_generic_bitmap {
 	errcode_t		magic;
 	ext2_filsys 		fs;
@@ -20,6 +48,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) \
@@ -57,6 +88,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 3f8333f..7343090 100644
--- a/lib/ext2fs/ext2fs.h
+++ b/lib/ext2fs/ext2fs.h
@@ -1168,6 +1168,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 9dcca03..bf1a76b 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_OPS
+#define INC_STAT(map, name) map->stats.name
+#else
+#define INC_STAT(map, name) ;;
+#endif
+
 
 errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
 				    int type, __u64 start, __u64 end,
@@ -110,11 +116,20 @@ errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
 		return EINVAL;
 	}
 
-	retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap),
-				&bitmap);
+	retval = ext2fs_get_memzero(sizeof(struct ext2fs_struct_generic_bitmap),
+				    &bitmap);
 	if (retval)
 		return retval;
 
+#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;
@@ -155,6 +170,71 @@ 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;
+	struct timeval now;
+
+#ifdef BMAP_STATS_OPS
+	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;
+	}
+#endif
+
+	if (gettimeofday(&now, (struct timezone *) NULL) == -1) {
+		perror("gettimeofday");
+		return;
+	}
+
+	inuse = (double) now.tv_sec + \
+		(((double) now.tv_usec) * 0.000001);
+	inuse -= (double) stats->created.tv_sec + \
+		(((double) stats->created.tv_usec) * 0.000001);
+
+	fprintf(stderr, "\n[+] %s bitmap (type %d)\n", bitmap->description,
+		stats->type);
+	fprintf(stderr, "=================================================\n");
+#ifdef BMAP_STATS_OPS
+	fprintf(stderr, "%16llu 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"
+		"%16llu bits tested backwards (%.2f%%)\n",
+		stats->mark_seq, mark_seq_perc,
+		stats->test_back, test_back_perc);
+	fprintf(stderr, "%16llu bits marked backwards (%.2f%%)\n"
+		"%16.2f seconds in use\n",
+		stats->mark_back, mark_back_perc, inuse);
+#endif /* BMAP_STATS_OPS */
+}
+#endif
+
 void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap)
 {
 	if (!bmap)
@@ -168,6 +248,13 @@ void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap)
 	if (!EXT2FS_IS_64_BITMAP(bmap))
 		return;
 
+#ifdef BMAP_STATS
+	if (getenv("E2FSPROGS_BITMAP_STATS")) {
+		ext2fs_print_bmap_statistics(bmap);
+		bmap->bitmap_ops->print_stats(bmap);
+	}
+#endif
+
 	bmap->bitmap_ops->free_bmap(bmap);
 
 	if (bmap->description) {
@@ -195,11 +282,24 @@ errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap src,
 		return EINVAL;
 
 	/* Allocate a new bitmap struct */
-	retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap),
-				&new_bmap);
+	retval = ext2fs_get_memzero(sizeof(struct ext2fs_struct_generic_bitmap),
+				    &new_bmap);
 	if (retval)
 		return retval;
 
+
+#ifdef BMAP_STATS_OPS
+	src->stats.copy_count++;
+#endif
+#ifdef BMAP_STATS
+	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;
@@ -247,6 +347,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);
 }
 
@@ -335,6 +437,15 @@ int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap bitmap,
 
 	arg >>= bitmap->cluster_bits;
 
+#ifdef BMAP_STATS_OPS
+	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;
@@ -363,6 +474,8 @@ int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap bitmap,
 
 	arg >>= bitmap->cluster_bits;
 
+	INC_STAT(bitmap, unmark_count);
+
 	if ((arg < bitmap->start) || (arg > bitmap->end)) {
 		warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg);
 		return 0;
@@ -391,6 +504,15 @@ int ext2fs_test_generic_bmap(ext2fs_generic_bitmap bitmap,
 
 	arg >>= bitmap->cluster_bits;
 
+#ifdef BMAP_STATS_OPS
+	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;
@@ -419,6 +541,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);
 }
 
@@ -442,6 +566,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);
 }
 
@@ -513,6 +639,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);
 }
 
@@ -535,6 +663,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);
@@ -563,6 +693,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);
diff --git a/lib/ext2fs/icount.c b/lib/ext2fs/icount.c
index 5d64ac4..8b46eda 100644
--- a/lib/ext2fs/icount.c
+++ b/lib/ext2fs/icount.c
@@ -104,12 +104,12 @@ static errcode_t alloc_icount(ext2_filsys fs, int flags, ext2_icount_t *ret)
 		return retval;
 	memset(icount, 0, sizeof(struct ext2_icount));
 
-	retval = ext2fs_allocate_inode_bitmap(fs, 0, &icount->single);
+	retval = ext2fs_allocate_inode_bitmap(fs, "icount", &icount->single);
 	if (retval)
 		goto errout;
 
 	if (flags & EXT2_ICOUNT_OPT_INCREMENT) {
-		retval = ext2fs_allocate_inode_bitmap(fs, 0,
+		retval = ext2fs_allocate_inode_bitmap(fs, "icount_inc",
 						      &icount->multiple);
 		if (retval)
 			goto errout;
-- 
1.7.8.11.gefc1f.dirty

Re: [PATCH 00/10] extent-based bitmaps for e2fsprogs

[Lukas Czerner]

On Sun, 18 Dec 2011, Theodore Ts'o wrote:

> I spent some time playing with Lukas Czerner's rbtree patches.  Here is
> a patch set which is based on the latest e2fsprogs sources, and which
> doesn't break any library ABI's or API's.  I also threw in regression
> tester for bitmaps, and fixed a bug in rb_unmark_bmap() that was found
> by the regression tests.
> 
> My tests on a number of file systems that I had easy access to seems to
> indicate that on pretty much all file systems, using the rbtree based
> implementation is a huge win over the bitarray.  (With memory required
> after patches being as low as 25% of the memory needed beforehand,
> although I believe 40-50% of the memory required in previous releases is
> more realistic.)  The one exception is if there are a huge number of
> directories, which is the reason for the AUTODIR pseudo backend.
> 
> Comments, please!

Hi Ted, it looks great, I am really happy you've resurrected my old
patches, I'll give it a try and take a look at patches.

Thanks!
-Lukas

> 
> 						- Ted
> 
> Lukas Czerner (3):
>   libext2fs: add rbtree library
>   libext2fs: add a bitmap implementation using rbtree's
>   libext2fs: add bitmap statistics
> 
> Theodore Ts'o (7):
>   libext2fs: add default_bitmap_type to the ext2_filsys structure
>   libext2fs: add tests for the bitmap functions
>   libext2fs: add pseudo bitmap backend type EXT2FS_BMAP64_AUTODIR
>   e2fsck: fix pass5 bug when using two different bitmap backends
>   libext2fs: use the rbtree bitmap by default when initializing a file
>     system
>   e2fsck: use different bitmap types as appropriate
>   libext2fs: adjust the description when copying a bitmap
> 
>  e2fsck/e2fsck.h               |   20 +
>  e2fsck/pass1.c                |   62 ++--
>  e2fsck/pass1b.c               |    6 +-
>  e2fsck/pass2.c                |    7 +-
>  e2fsck/pass3.c                |    7 +-
>  e2fsck/pass5.c                |    4 +-
>  e2fsck/unix.c                 |    4 +
>  e2fsck/util.c                 |   61 +++
>  lib/ext2fs/Makefile.in        |   38 ++-
>  lib/ext2fs/bitmaps.c          |   14 +-
>  lib/ext2fs/blkmap64_ba.c      |    8 +
>  lib/ext2fs/blkmap64_rb.c      |  824 +++++++++++++++++++++++++++++++++++++++++
>  lib/ext2fs/bmap64.h           |   33 ++
>  lib/ext2fs/ext2fs.h           |   15 +-
>  lib/ext2fs/ext2fsP.h          |    2 -
>  lib/ext2fs/gen_bitmap64.c     |  158 ++++++++-
>  lib/ext2fs/icount.c           |    4 +-
>  lib/ext2fs/initialize.c       |    1 +
>  lib/ext2fs/rbtree.c           |  451 ++++++++++++++++++++++
>  lib/ext2fs/rbtree.h           |  180 +++++++++
>  lib/ext2fs/tst_bitmaps.c      |  577 ++++++++++++++++++++++++++++
>  lib/ext2fs/tst_bitmaps_cmd.ct |   39 ++
>  lib/ext2fs/tst_bitmaps_cmds   |   46 +++
>  lib/ext2fs/tst_bitmaps_exp    |   92 +++++
>  24 files changed, 2600 insertions(+), 53 deletions(-)
>  create mode 100644 lib/ext2fs/blkmap64_rb.c
>  create mode 100644 lib/ext2fs/rbtree.c
>  create mode 100644 lib/ext2fs/rbtree.h
>  create mode 100644 lib/ext2fs/tst_bitmaps.c
>  create mode 100644 lib/ext2fs/tst_bitmaps_cmd.ct
>  create mode 100644 lib/ext2fs/tst_bitmaps_cmds
>  create mode 100644 lib/ext2fs/tst_bitmaps_exp
> 
> 

-- 

Re: [PATCH 02/10] libext2fs: add tests for the bitmap functions

[Lukas Czerner]

On Sun, 18 Dec 2011, Theodore Ts'o wrote:

> These tests allow us to be sure that the new bitmap backends are
> correctly implemented.

This looks good, just two tiny comments.

Thanks!
-Lukas

> 
> Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
> ---
>  lib/ext2fs/Makefile.in        |   17 ++-
>  lib/ext2fs/tst_bitmaps.c      |  577 +++++++++++++++++++++++++++++++++++++++++
>  lib/ext2fs/tst_bitmaps_cmd.ct |   39 +++
>  lib/ext2fs/tst_bitmaps_cmds   |   46 ++++
>  lib/ext2fs/tst_bitmaps_exp    |   92 +++++++
>  5 files changed, 770 insertions(+), 1 deletions(-)
>  create mode 100644 lib/ext2fs/tst_bitmaps.c
>  create mode 100644 lib/ext2fs/tst_bitmaps_cmd.ct
>  create mode 100644 lib/ext2fs/tst_bitmaps_cmds
>  create mode 100644 lib/ext2fs/tst_bitmaps_exp
> 
> diff --git a/lib/ext2fs/Makefile.in b/lib/ext2fs/Makefile.in
> index 3d08095..37f5ee5 100644
> --- a/lib/ext2fs/Makefile.in
> +++ b/lib/ext2fs/Makefile.in
> @@ -347,6 +347,16 @@ filefrag.o: $(top_srcdir)/debugfs/filefrag.c
>  	$(E) "	CC $<"
>  	$(Q) $(CC) $(ALL_CFLAGS) -c $< -o $@
>  
> +tst_bitmaps_cmd.c: tst_bitmaps_cmd.ct
> +	$(E) "	MK_CMDS $@"
> +	$(Q) DIR=$(srcdir) $(MK_CMDS) $(srcdir)/tst_bitmaps_cmd.ct
> +
> +tst_bitmaps: tst_bitmaps.o tst_bitmaps_cmd.o $(STATIC_LIBEXT2FS) $(DEPLIBSS) \
> +		$(DEPLIBCOM_ERR)
> +	$(E) "	LD $@"
> +	$(Q) $(CC) -o $@ tst_bitmaps.o tst_bitmaps_cmd.o $(ALL_CFLAGS) \
> +		$(STATIC_LIBEXT2FS) $(LIBSS) $(LIBCOM_ERR)
> +
>  tst_extents: $(srcdir)/extent.c extent_dbg.c $(DEBUG_OBJS) $(DEPLIBSS) \
>  	$(LIBE2P) $(DEPLIBUUID) $(DEPLIBBLKID) $(DEPLIBCOM_ERR)
>  	$(E) "	LD $@"
> @@ -369,7 +379,8 @@ mkjournal: mkjournal.c $(STATIC_LIBEXT2FS) $(DEPLIBCOM_ERR)
>  	$(E) "	LD $@"
>  	$(Q) $(CC) -o mkjournal $(srcdir)/mkjournal.c -DDEBUG $(STATIC_LIBEXT2FS) $(LIBCOM_ERR) $(ALL_CFLAGS)
>  
> -check:: tst_bitops tst_badblocks tst_iscan tst_types tst_icount tst_super_size tst_types tst_inode_size tst_csum tst_crc32c
> +check:: tst_bitops tst_badblocks tst_iscan tst_types tst_icount \
> +    tst_super_size tst_types tst_inode_size tst_csum tst_crc32c tst_bitmaps
>  	LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) ./tst_bitops
>  	LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) ./tst_badblocks
>  	LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) ./tst_iscan
> @@ -379,6 +390,9 @@ check:: tst_bitops tst_badblocks tst_iscan tst_types tst_icount tst_super_size t
>  	LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) ./tst_inode_size
>  	LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) ./tst_csum
>  	LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) ./tst_crc32c
> +	LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) \
> +		./tst_bitmaps -f $(srcdir)/tst_bitmaps_cmds > tst_bitmaps_out
> +	diff $(srcdir)/tst_bitmaps_exp tst_bitmaps_out
>  
>  installdirs::
>  	$(E) "	MKINSTALLDIRS $(libdir) $(includedir)/ext2fs"
> @@ -411,6 +425,7 @@ clean::
>  		tst_badblocks tst_iscan ext2_err.et ext2_err.c ext2_err.h \
>  		tst_byteswap tst_ismounted tst_getsize tst_sectgetsize \
>  		tst_bitops tst_types tst_icount tst_super_size tst_csum \
> +		tst_bitmaps tst_bitmaps_out tst_bitmaps_cmd.c \
>  		ext2_tdbtool mkjournal debug_cmds.c \
>  		../libext2fs.a ../libext2fs_p.a ../libext2fs_chk.a \
>  		crc32c_table.h gen_crc32ctable tst_crc32c
> diff --git a/lib/ext2fs/tst_bitmaps.c b/lib/ext2fs/tst_bitmaps.c
> new file mode 100644
> index 0000000..27722e5
> --- /dev/null
> +++ b/lib/ext2fs/tst_bitmaps.c
> @@ -0,0 +1,577 @@
> +/*
> + * tst_bitmaps.c
> + *
> + * Copyright (C) 2011 Theodore Ts'o.
> + *
> + * %Begin-Header%
> + * This file may be redistributed under the terms of the GNU Library
> + * General Public License, version 2.
> + * %End-Header%
> + */
> +
> +#include "config.h"
> +#include <unistd.h>
> +#include <stdlib.h>
> +#include <stdio.h>
> +#ifdef HAVE_GETOPT_H
> +#include <getopt.h>
> +#endif
> +#include <string.h>
> +#include <fcntl.h>
> +#include <time.h>
> +#include <sys/stat.h>
> +#include <sys/types.h>
> +#include "ss/ss.h"
> +
> +#include "ext2_fs.h"
> +#include "ext2fs.h"
> +#include "ext2fsP.h"
> +
> +extern ss_request_table tst_bitmaps_cmds;
> +
> +static char subsystem_name[] = "tst_bitmaps";
> +static char version[] = "1.0";
> +
> +ext2_filsys	test_fs;
> +int		exit_status = 0;
> +
> +static int source_file(const char *cmd_file, int sci_idx)
> +{
> +	FILE		*f;
> +	char		buf[256];
> +	char		*cp;
> +	int		retval;
> +	int 		noecho;
> +
> +	if (strcmp(cmd_file, "-") == 0)
> +		f = stdin;
> +	else {
> +		f = fopen(cmd_file, "r");
> +		if (!f) {
> +			perror(cmd_file);
> +			exit(1);
> +		}
> +	}
> +	fflush(stdout);
> +	fflush(stderr);
> +	setbuf(stdout, NULL);
> +	setbuf(stderr, NULL);
> +	while (!feof(f)) {
> +		if (fgets(buf, sizeof(buf), f) == NULL)
> +			break;
> +		if (buf[0] == '#')
> +			continue;
> +		noecho = 0;
> +		if (buf[0] == '-') {
> +			noecho = 1;
> +			buf[0] = ' ';
> +		}
> +		cp = strchr(buf, '\n');
> +		if (cp)
> +			*cp = 0;
> +		cp = strchr(buf, '\r');
> +		if (cp)
> +			*cp = 0;

Since we are dealing with strings here I would rather use '\0' so it
make more obvious.

> +		if (!noecho)
> +			printf("%s: %s\n", subsystem_name, buf);
> +		retval = ss_execute_line(sci_idx, buf);
> +		if (retval) {
> +			ss_perror(sci_idx, retval, buf);
> +			exit_status++;
> +		}
> +	}
> +	return exit_status;
> +}
> +
> +
> +/*
> + * This function resets the libc getopt() function, which keeps
> + * internal state.  Bad design!  Stupid libc API designers!  No
> + * biscuit!
> + *
> + * BSD-derived getopt() functions require that optind be reset to 1 in
> + * order to reset getopt() state.  This used to be generally accepted
> + * way of resetting getopt().  However, glibc's getopt()
> + * has additional getopt() state beyond optind, and requires that
> + * optind be set zero to reset its state.  So the unfortunate state of
> + * affairs is that BSD-derived versions of getopt() misbehave if
> + * optind is set to 0 in order to reset getopt(), and glibc's getopt()
> + * will core dump if optind is set 1 in order to reset getopt().
> + *
> + * More modern versions of BSD require that optreset be set to 1 in
> + * order to reset getopt().   Sigh.  Standards, anyone?
> + *
> + * We hide the hair here.
> + */
> +void reset_getopt(void)
> +{
> +#if defined(__GLIBC__) || defined(__linux__)
> +	optind = 0;
> +#else
> +	optind = 1;
> +#endif
> +#ifdef HAVE_OPTRESET
> +	optreset = 1;		/* Makes BSD getopt happy */
> +#endif
> +}
> +
> +/*
> + * This function will convert a string to an unsigned long, printing
> + * an error message if it fails, and returning success or failure in err.
> + */
> +unsigned long parse_ulong(const char *str, const char *cmd,
> +			  const char *descr, int *err)
> +{
> +	char		*tmp;
> +	unsigned long	ret;
> +
> +	ret = strtoul(str, &tmp, 0);
> +	if (*tmp == 0) {
> +		if (err)
> +			*err = 0;
> +		return ret;
> +	}
> +	com_err(cmd, 0, "Bad %s - %s", descr, str);
> +	if (err)
> +		*err = 1;
> +	else
> +		exit(1);
> +	return 0;
> +}
> +
> +
> +int check_fs_open(char *name)
> +{
> +	if (!test_fs) {
> +		com_err(name, 0, "Filesystem not open");
> +		return 1;
> +	}
> +	return 0;
> +}
> +
> +static void setup_filesystem(const char *name,
> +			     unsigned int blocks, unsigned int inodes,
> +			     unsigned int type)
> +{
> +	struct ext2_super_block param;
> +	errcode_t retval;
> +
> +	memset(&param, 0, sizeof(param));
> +	ext2fs_blocks_count_set(&param, blocks);
> +	param.s_inodes_count = inodes;
> +
> +	retval = ext2fs_initialize("test fs", EXT2_FLAG_64BITS, &param,
> +				   test_io_manager, &test_fs);
> +
> +	if (retval) {
> +		com_err(name, retval, "while initializing filesystem");
> +		return;
> +	}
> +	test_fs->default_bitmap_type = type;
> +	ext2fs_free_block_bitmap(test_fs->block_map);
> +	test_fs->block_map = 0;
> +	ext2fs_free_inode_bitmap(test_fs->inode_map);
> +	test_fs->inode_map = 0;
> +	retval = ext2fs_allocate_block_bitmap(test_fs, "block bitmap",
> +					      &test_fs->block_map);
> +	if (retval) {
> +		com_err(name, retval, "while allocating block bitmap");
> +		goto errout;
> +	}
> +	retval = ext2fs_allocate_inode_bitmap(test_fs, "inode bitmap",
> +					      &test_fs->inode_map);
> +	if (retval) {
> +		com_err(name, retval, "while allocating inode bitmap");
> +		goto errout;
> +	}
> +	return;
> +
> +errout:
> +	ext2fs_close(test_fs);
> +	test_fs = 0;
> +}
> +
> +void setup_cmd(int argc, char **argv)
> +{
> +	errcode_t	retval;
> +	int		i, c, err;
> +	unsigned int	blocks = 128;
> +	unsigned int	inodes = 0;
> +	unsigned int	type = EXT2FS_BMAP64_BITARRAY;
> +
> +	if (test_fs) {
> +		ext2fs_close(test_fs);
> +		test_fs = 0;
> +	}
> +
> +	reset_getopt();
> +	while ((c = getopt(argc, argv, "b:i:t:")) != EOF) {
> +		switch (c) {
> +		case 'b':
> +			blocks = parse_ulong(optarg, argv[0],
> +					     "number of blocks", &err);
> +			if (err)
> +				return;
> +			break;
> +		case 'i':
> +			inodes = parse_ulong(optarg, argv[0],
> +					     "number of blocks", &err);
> +			if (err)
> +				return;
> +			break;
> +		case 't':
> +			type = parse_ulong(optarg, argv[0],
> +					   "bitmap backend type", &err);
> +			if (err)
> +				return;
> +			break;
> +		default:
> +			fprintf(stderr, "%s: usage: setup [-b blocks] "
> +				"[-i inodes] [-t type]\n", argv[0]);
> +			return;
> +		}
> +	}
> +	setup_filesystem(argv[0], blocks, inodes, type);
> +}
> +
> +void close_cmd(int argc, char **argv)
> +{
> +	if (check_fs_open(argv[0]))
> +		return;
> +
> +	ext2fs_close(test_fs);
> +	test_fs = 0;
> +}
> +
> +
> +void dump_bitmap(ext2fs_generic_bitmap bmap, unsigned int start, unsigned num)
> +{
> +	unsigned char	*buf;
> +	errcode_t	retval;
> +	int		i, len = (num - start + 7) / 8;
> +
> +	buf = malloc(len);
> +	if (!buf) {
> +		com_err("dump_bitmap", 0, "couldn't allocate buffer");
> +		return;
> +	}
> +	memset(buf, 0, len);
> +	retval = ext2fs_get_generic_bmap_range(bmap, (__u64) start, num, buf);
> +	if (retval) {
> +		com_err("dump_bitmap", retval, 
> +			"while calling ext2fs_generic_bmap_range");
> +		free(buf);
> +		return;
> +	}
> +	for (i=0; i < len; i++)
> +		printf("%02x", buf[i]);
> +	printf("\n");
> +	free(buf);
> +}
> +
> +void dump_inode_bitmap_cmd(int argc, char **argv)
> +{
> +	if (check_fs_open(argv[0]))
> +		return;
> +
> +	printf("inode bitmap: ");
> +	dump_bitmap(test_fs->inode_map, 1, test_fs->super->s_inodes_count);
> +}
> +	
> +void dump_block_bitmap_cmd(int argc, char **argv)
> +{
> +	if (check_fs_open(argv[0]))
> +		return;
> +
> +	printf("block bitmap: ");
> +	dump_bitmap(test_fs->block_map, test_fs->super->s_first_data_block,
> +		    test_fs->super->s_blocks_count);
> +}
> +	
> +void do_setb(int argc, char *argv[])
> +{
> +	unsigned int block, num;
> +	int err;
> +	int test_result, op_result;
> +
> +	if (check_fs_open(argv[0]))
> +		return;
> +
> +	if (argc != 2 && argc != 3) {
> +		com_err(argv[0], 0, "Usage: setb <block> [num]");
> +		return;
> +	}
> +
> +	block = parse_ulong(argv[1], argv[0], "block", &err);
> +	if (err)
> +		return;
> +
> +	if (argc == 3) {
> +		num = parse_ulong(argv[2], argv[0], "num", &err);
> +		if (err)
> +			return;
> +
> +		ext2fs_mark_block_bitmap_range2(test_fs->block_map,
> +						block, num);
> +		printf("Marking blocks %u to %u\n", block, block + num - 1);
> +		return;
> +	}
> +
> +	test_result = ext2fs_test_block_bitmap2(test_fs->block_map, block);
> +	op_result = ext2fs_mark_block_bitmap2(test_fs->block_map, block);
> +	printf("Setting block %u, was %s before\n", block, op_result ?
> +	       "set" : "clear");
> +	if (!test_result != !op_result)
> +		com_err(argv[0], 0, "*ERROR* test_result different! (%d, %d)",
> +			test_result, op_result);
> +}
> +
> +void do_clearb(int argc, char *argv[])
> +{
> +	unsigned int block, num;
> +	int err;
> +	int test_result, op_result;
> +
> +	if (check_fs_open(argv[0]))
> +		return;
> +
> +	if (argc != 2 && argc != 3) {
> +		com_err(argv[0], 0, "Usage: clearb <block> [num]");
> +		return;
> +	}
> +
> +	block = parse_ulong(argv[1], argv[0], "block", &err);
> +	if (err)
> +		return;
> +
> +	if (argc == 3) {
> +		num = parse_ulong(argv[2], argv[0], "num", &err);
> +		if (err)
> +			return;
> +
> +		ext2fs_unmark_block_bitmap_range2(test_fs->block_map,
> +						block, num);
> +		printf("Clearing blocks %u to %u\n", block, block + num - 1);
> +		return;
> +	}
> +
> +	test_result = ext2fs_test_block_bitmap2(test_fs->block_map, block);
> +	op_result = ext2fs_unmark_block_bitmap2(test_fs->block_map, block);
> +	printf("Clearing block %u, was %s before\n", block, op_result ?
> +	       "set" : "clear");
> +	if (!test_result != !op_result)
> +		com_err(argv[0], 0, "*ERROR* test_result different! (%d, %d)",
> +			test_result, op_result);
> +}
> +
> +void do_testb(int argc, char *argv[])
> +{
> +	unsigned int block, num;
> +	int err;
> +	int test_result, op_result;
> +
> +	if (check_fs_open(argv[0]))
> +		return;
> +
> +	if (argc != 2 && argc != 3) {
> +		com_err(argv[0], 0, "Usage: testb <block> [num]");
> +		return;
> +	}
> +
> +	block = parse_ulong(argv[1], argv[0], "block", &err);
> +	if (err)
> +		return;
> +
> +	if (argc == 3) {
> +		num = parse_ulong(argv[2], argv[0], "num", &err);
> +		if (err)
> +			return;
> +
> +		test_result =
> +			ext2fs_test_block_bitmap_range2(test_fs->block_map,
> +							block, num);
> +		printf("Blocks %u to %u are %sall clear.\n",
> +		       block, block + num - 1, test_result ? "" : "NOT ");
> +		return;
> +	}
> +
> +	test_result = ext2fs_test_block_bitmap2(test_fs->block_map, block);
> +	printf("Block %u is %s\n", block, test_result ? "set" : "clear");
> +}
> +
> +void do_zerob(int argc, char *argv[])
> +{
> +	if (check_fs_open(argv[0]))
> +		return;
> +
> +	printf("Clearing block bitmap.\n");
> +	ext2fs_clear_block_bitmap(test_fs->block_map);
> +}
> +
> +void do_seti(int argc, char *argv[])
> +{
> +	unsigned int inode;
> +	int err;
> +	int test_result, op_result;
> +
> +	if (check_fs_open(argv[0]))
> +		return;
> +
> +	if (argc != 2) {
> +		com_err(argv[0], 0, "Usage: seti <inode>");
> +		return;
> +	}
> +
> +	inode = parse_ulong(argv[1], argv[0], "inode", &err);
> +	if (err)
> +		return;
> +
> +	test_result = ext2fs_test_inode_bitmap2(test_fs->inode_map, inode);
> +	op_result = ext2fs_mark_inode_bitmap2(test_fs->inode_map, inode);
> +	printf("Setting inode %u, was %s before\n", inode, op_result ?
> +	       "set" : "clear");
> +	if (!test_result != !op_result) {
> +		com_err(argv[0], 0, "*ERROR* test_result different! (%d, %d)",
> +			test_result, op_result);
> +		exit_status++;
> +	}
> +}
> +
> +void do_cleari(int argc, char *argv[])
> +{
> +	unsigned int inode;
> +	int err;
> +	int test_result, op_result;
> +
> +	if (check_fs_open(argv[0]))
> +		return;
> +
> +	if (argc != 2) {
> +		com_err(argv[0], 0, "Usage: clearb <inode>");
> +		return;
> +	}
> +
> +	inode = parse_ulong(argv[1], argv[0], "inode", &err);
> +	if (err)
> +		return;
> +
> +	test_result = ext2fs_test_inode_bitmap2(test_fs->inode_map, inode);
> +	op_result = ext2fs_unmark_inode_bitmap2(test_fs->inode_map, inode);
> +	printf("Clearing inode %u, was %s before\n", inode, op_result ?
> +	       "set" : "clear");
> +	if (!test_result != !op_result) {
> +		com_err(argv[0], 0, "*ERROR* test_result different! (%d, %d)",
> +			test_result, op_result);
> +		exit_status++;
> +	}
> +}
> +
> +void do_testi(int argc, char *argv[])
> +{
> +	unsigned int inode;
> +	int err;
> +	int test_result, op_result;
> +
> +	if (check_fs_open(argv[0]))
> +		return;
> +
> +	if (argc != 2) {
> +		com_err(argv[0], 0, "Usage: testb <inode>");
> +		return;
> +	}
> +
> +	inode = parse_ulong(argv[1], argv[0], "inode", &err);
> +	if (err)
> +		return;
> +
> +	test_result = ext2fs_test_inode_bitmap2(test_fs->inode_map, inode);
> +	printf("Inode %u is %s\n", inode, test_result ? "set" : "clear");
> +}
> +
> +void do_zeroi(int argc, char *argv[])
> +{
> +	if (check_fs_open(argv[0]))
> +		return;
> +
> +	printf("Clearing inode bitmap.\n");
> +	ext2fs_clear_inode_bitmap(test_fs->inode_map);
> +}
> +
> +int main(int argc, char **argv)
> +{
> +	unsigned int	blocks = 128;
> +	unsigned int	inodes = 0;
> +	unsigned int	type = EXT2FS_BMAP64_BITARRAY;
> +	int		c, err, code;
> +	char		*request = (char *)NULL;
> +	char		*cmd_file = 0;
> +	int		sci_idx;
> +
> +	add_error_table(&et_ss_error_table);
> +	add_error_table(&et_ext2_error_table);
> +	while ((c = getopt (argc, argv, "b:i:t:R:f:")) != EOF) {
> +		switch (c) {
> +		case 'b':
> +			blocks = parse_ulong(optarg, argv[0],
> +					     "number of blocks", &err);
> +			if (err)
> +				return;
> +			break;
> +		case 'i':
> +			inodes = parse_ulong(optarg, argv[0],
> +					     "number of blocks", &err);
> +			if (err)
> +				return;
> +			break;
> +		case 't':
> +			type = parse_ulong(optarg, argv[0],
> +					   "bitmap backend type", &err);
> +			if (err)
> +				return;
> +			break;
> +		case 'R':
> +			request = optarg;
> +			break;
> +		case 'f':
> +			cmd_file = optarg;
> +			break;
> +		default:
> +			com_err(argv[0], 0, "Usage: %s [-R request] "
> +				"[-f cmd_file]", subsystem_name);

-b, -i and -t are missing in the Usage.

> +			exit(1);
> +		}
> +	}
> +
> +	sci_idx = ss_create_invocation(subsystem_name, version,
> +				       (char *)NULL, &tst_bitmaps_cmds, &code);
> +	if (code) {
> +		ss_perror(sci_idx, code, "creating invocation");
> +		exit(1);
> +	}
> +
> +	(void) ss_add_request_table (sci_idx, &ss_std_requests, 1, &code);
> +	if (code) {
> +		ss_perror(sci_idx, code, "adding standard requests");
> +		exit (1);
> +	}
> +
> +	printf("%s %s.  Type '?' for a list of commands.\n\n",
> +	       subsystem_name, version);
> +
> +	setup_filesystem(argv[0], blocks, inodes, type);
> +
> +	if (request) {
> +		code = ss_execute_line(sci_idx, request);
> +		if (code) {
> +			ss_perror(sci_idx, code, request);
> +			exit_status++;
> +		}
> +	} else if (cmd_file) {
> +		exit_status = source_file(cmd_file, sci_idx);
> +	} else {
> +		ss_listen(sci_idx);
> +	}
> +
> +	exit(exit_status);
> +}
> +
> diff --git a/lib/ext2fs/tst_bitmaps_cmd.ct b/lib/ext2fs/tst_bitmaps_cmd.ct
> new file mode 100644
> index 0000000..5a51d23
> --- /dev/null
> +++ b/lib/ext2fs/tst_bitmaps_cmd.ct
> @@ -0,0 +1,39 @@
> +command_table tst_bitmaps_cmds;
> +
> +request setup_cmd, "Setup file system",
> +	setup;
> +
> +request close_cmd, "Close file system",
> +	close;
> +
> +request dump_inode_bitmap_cmd, "Dump the inode bitmap",
> +	dump_inode_bitmap, dump_ib;
> +
> +request dump_block_bitmap_cmd, "Dump the block bitmap",
> +	dump_block_bitmap, dump_bb;
> +
> +request do_setb, "Set block",
> +	set_block, setb;
> +
> +request do_clearb, "Clear block",
> +	clear_block, clearb;
> +
> +request do_testb, "Test block",
> +	test_block, testb;
> +
> +request do_zerob, "Clear block bitmap",
> +	clear_block_bitmap, zerob;
> +
> +request do_seti, "Set inode",
> +	set_inode, seti;
> +
> +request do_cleari, "Clear inode",
> +	clear_inode, cleari;
> +
> +request do_testi, "Test inode",
> +	test_inode, testi;
> +
> +request do_zeroi, "Clear inode bitmap",
> +	clear_inode_bitmap, zeroi;
> +
> +end;
> diff --git a/lib/ext2fs/tst_bitmaps_cmds b/lib/ext2fs/tst_bitmaps_cmds
> new file mode 100644
> index 0000000..13f4ea8
> --- /dev/null
> +++ b/lib/ext2fs/tst_bitmaps_cmds
> @@ -0,0 +1,46 @@
> +setb 12
> +setb 12
> +clearb 12
> +clearb 12
> +setb 12
> +setb 14
> +setb 16
> +testb 13
> +testb 15
> +testb 12
> +testb 14
> +setb 13
> +setb 15
> +testb 12
> +testb 11
> +testb 15
> +testb 16
> +dump_bb
> +clearb 12 7
> +testb 12 7
> +setb 15
> +testb 12 7
> +clearb 15
> +testb 12 7
> +setb 12 7
> +dump_bb
> +seti 2
> +seti 5
> +seti 4
> +seti 3
> +seti 4
> +seti 5
> +testi 6
> +testi 1
> +dump_ib
> +zeroi
> +testi 5
> +seti 5
> +seti 5
> +cleari 5
> +cleari 5
> +testi 17
> +testi 6
> +testi 4
> +quit
> +
> diff --git a/lib/ext2fs/tst_bitmaps_exp b/lib/ext2fs/tst_bitmaps_exp
> new file mode 100644
> index 0000000..aa64ae7
> --- /dev/null
> +++ b/lib/ext2fs/tst_bitmaps_exp
> @@ -0,0 +1,92 @@
> +tst_bitmaps 1.0.  Type '?' for a list of commands.
> +
> +tst_bitmaps: setb 12
> +Setting block 12, was clear before
> +tst_bitmaps: setb 12
> +Setting block 12, was set before
> +tst_bitmaps: clearb 12
> +Clearing block 12, was set before
> +tst_bitmaps: clearb 12
> +Clearing block 12, was clear before
> +tst_bitmaps: setb 12
> +Setting block 12, was clear before
> +tst_bitmaps: setb 14
> +Setting block 14, was clear before
> +tst_bitmaps: setb 16
> +Setting block 16, was clear before
> +tst_bitmaps: testb 13
> +Block 13 is clear
> +tst_bitmaps: testb 15
> +Block 15 is clear
> +tst_bitmaps: testb 12
> +Block 12 is set
> +tst_bitmaps: testb 14
> +Block 14 is set
> +tst_bitmaps: setb 13
> +Setting block 13, was clear before
> +tst_bitmaps: setb 15
> +Setting block 15, was clear before
> +tst_bitmaps: testb 12
> +Block 12 is set
> +tst_bitmaps: testb 11
> +Block 11 is clear
> +tst_bitmaps: testb 15
> +Block 15 is set
> +tst_bitmaps: testb 16
> +Block 16 is set
> +tst_bitmaps: dump_bb
> +block bitmap: 00f80000000000000000000000000000
> +tst_bitmaps: clearb 12 7
> +Clearing blocks 12 to 18
> +tst_bitmaps: testb 12 7
> +Blocks 12 to 18 are all clear.
> +tst_bitmaps: setb 15
> +Setting block 15, was clear before
> +tst_bitmaps: testb 12 7
> +Blocks 12 to 18 are NOT all clear.
> +tst_bitmaps: clearb 15
> +Clearing block 15, was set before
> +tst_bitmaps: testb 12 7
> +Blocks 12 to 18 are all clear.
> +tst_bitmaps: setb 12 7
> +Marking blocks 12 to 18
> +tst_bitmaps: dump_bb
> +block bitmap: 00f80300000000000000000000000000
> +tst_bitmaps: seti 2
> +Setting inode 2, was clear before
> +tst_bitmaps: seti 5
> +Setting inode 5, was clear before
> +tst_bitmaps: seti 4
> +Setting inode 4, was clear before
> +tst_bitmaps: seti 3
> +Setting inode 3, was clear before
> +tst_bitmaps: seti 4
> +Setting inode 4, was set before
> +tst_bitmaps: seti 5
> +Setting inode 5, was set before
> +tst_bitmaps: testi 6
> +Inode 6 is clear
> +tst_bitmaps: testi 1
> +Inode 1 is clear
> +tst_bitmaps: dump_ib
> +inode bitmap: 1e000000
> +tst_bitmaps: zeroi
> +Clearing inode bitmap.
> +tst_bitmaps: testi 5
> +Inode 5 is clear
> +tst_bitmaps: seti 5
> +Setting inode 5, was clear before
> +tst_bitmaps: seti 5
> +Setting inode 5, was set before
> +tst_bitmaps: cleari 5
> +Clearing inode 5, was set before
> +tst_bitmaps: cleari 5
> +Clearing inode 5, was clear before
> +tst_bitmaps: testi 17
> +Inode 17 is clear
> +tst_bitmaps: testi 6
> +Inode 6 is clear
> +tst_bitmaps: testi 4
> +Inode 4 is clear
> +tst_bitmaps: quit
> +tst_bitmaps: 
> 

-- 

Re: [PATCH 05/10] libext2fs: add pseudo bitmap backend type EXT2FS_BMAP64_AUTODIR

[Lukas Czerner]

On Sun, 18 Dec 2011, Theodore Ts'o wrote:

> This backend type will automatically switch between the bitarray and
> the rbtree backend based on the number of directories in the file
> system.
> 
> Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
> ---
>  lib/ext2fs/Makefile.in    |    3 +++
>  lib/ext2fs/ext2fs.h       |    1 +
>  lib/ext2fs/gen_bitmap64.c |    8 ++++++++
>  3 files changed, 12 insertions(+), 0 deletions(-)
> 
> diff --git a/lib/ext2fs/Makefile.in b/lib/ext2fs/Makefile.in
> index 4c5ebed..ef55494 100644
> --- a/lib/ext2fs/Makefile.in
> +++ b/lib/ext2fs/Makefile.in
> @@ -400,6 +400,9 @@ check:: tst_bitops tst_badblocks tst_iscan tst_types tst_icount \
>  	LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) \
>  		./tst_bitmaps -t 2 -f $(srcdir)/tst_bitmaps_cmds > tst_bitmaps_out
>  	diff $(srcdir)/tst_bitmaps_exp tst_bitmaps_out
> +	LD_LIBRARY_PATH=$(LIB) DYLD_LIBRARY_PATH=$(LIB) \
> +		./tst_bitmaps -t 3 -f $(srcdir)/tst_bitmaps_cmds > tst_bitmaps_out
> +	diff $(srcdir)/tst_bitmaps_exp tst_bitmaps_out
>  
>  installdirs::
>  	$(E) "	MKINSTALLDIRS $(libdir) $(includedir)/ext2fs"
> diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h
> index 5ffb036..f2df66e 100644
> --- a/lib/ext2fs/ext2fs.h
> +++ b/lib/ext2fs/ext2fs.h
> @@ -294,6 +294,7 @@ struct struct_ext2_filsys {
>  
>  #define EXT2FS_BMAP64_BITARRAY	1
>  #define EXT2FS_BMAP64_RBTREE	2
> +#define EXT2FS_BMAP64_AUTODIR	3
>  
>  /*
>   * Return flags for the block iterator functions
> diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c
> index c9b4051..7b066a2 100644
> --- a/lib/ext2fs/gen_bitmap64.c
> +++ b/lib/ext2fs/gen_bitmap64.c
> @@ -86,6 +86,7 @@ errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
>  {
>  	ext2fs_generic_bitmap	bitmap;
>  	struct ext2_bitmap_ops	*ops;
> +	ext2_ino_t num_dirs;
>  	errcode_t retval;
>  
>  	if (!type)
> @@ -98,6 +99,13 @@ errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
>  	case EXT2FS_BMAP64_RBTREE:
>  		ops = &ext2fs_blkmap64_rbtree;
>  		break;
> +	case EXT2FS_BMAP64_AUTODIR:
> +		retval = ext2fs_get_num_dirs(fs, &num_dirs);
> +		if (retval || num_dirs > (fs->super->s_inodes_count / 320))
> +			ops = &ext2fs_blkmap64_bitarray;
> +		else
> +			ops = &ext2fs_blkmap64_rbtree;
> +		break;

It is good that even if ext2fs_get_num_dirs() would fail (but it can
not in current implementation - it always return 0), we will set backend
operation struct anyway.

>  	default:
>  		return EINVAL;
>  	}
> 

-- 

Re: [PATCH 10/10] libext2fs: add bitmap statistics

[Lukas Czerner]

On Sun, 18 Dec 2011, Theodore Ts'o wrote:

> From: Lukas Czerner <lczerner@redhat.com>
> 
> 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.
> 
> [ Changed to provide basic statistics when enabled with the
>   E2FSPROGS_BITMAPS_STATS environment variable -- tytso]

Actually it is 'E2FSPROGS_BITMAP_STATS' so BITMAP instead of BITMAPS,
not sure what was intended.

-Lukas

> 
> Signed-off-by: Lukas Czerner <lczerner@redhat.com>
> Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
> ---
>  lib/ext2fs/blkmap64_ba.c  |    8 +++
>  lib/ext2fs/blkmap64_rb.c  |   85 ++++++++++++++++++++++++++-
>  lib/ext2fs/bmap64.h       |   32 ++++++++++
>  lib/ext2fs/ext2fs.h       |    4 +
>  lib/ext2fs/gen_bitmap64.c |  140 +++++++++++++++++++++++++++++++++++++++++++-
>  lib/ext2fs/icount.c       |    4 +-
>  6 files changed, 265 insertions(+), 8 deletions(-)
> 
> diff --git a/lib/ext2fs/blkmap64_ba.c b/lib/ext2fs/blkmap64_ba.c
> index 9253af2..3f0c643 100644
> --- a/lib/ext2fs/blkmap64_ba.c
> +++ b/lib/ext2fs/blkmap64_ba.c
> @@ -310,6 +310,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, "%16llu 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,
> @@ -325,4 +332,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 31fc393..aba7cfd 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_OPS
> +	__u64 mark_hit;
> +	__u64 test_hit;
> +#endif
>  };
>  
>  static int rb_insert_extent(__u64 start, __u64 count,
> @@ -170,6 +174,11 @@ static errcode_t rb_alloc_private_data (ext2fs_generic_bitmap bitmap)
>  	*bp->rcursor = NULL;
>  	*bp->wcursor = NULL;
>  
> +#ifdef BMAP_STATS_OPS
> +	bp->test_hit = 0;
> +	bp->mark_hit = 0;
> +#endif
> +
>  	bitmap->private = (void *) bp;
>  	return 0;
>  }
> @@ -315,8 +324,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_OPS
> +		bp->test_hit++;
> +#endif
>  		return 1;
> +	}
>  
>  	rcursor = *bp->wcursor;
>  	if (!rcursor)
> @@ -355,8 +368,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_OPS
> +			bp->mark_hit++;
> +#endif
>  			goto got_extent;
> +		}
>  	}
>  
>  	while (*n) {
> @@ -725,6 +742,69 @@ 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 = ext2fs_rb_first(&bp->root);
> +	for (node = ext2fs_rb_first(&bp->root); node != NULL;
> +	     node = ext2fs_rb_next(node)) {
> +		ext = ext2fs_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);
> +#ifdef BMAP_STATS_OPS
> +	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);
> +#endif
> +	fprintf(stderr, "%16llu extents (%llu bytes)\n",
> +		count, ((count * sizeof(struct bmap_rb_extent)) +
> +			sizeof(struct ext2fs_rb_private)));
> + 	fprintf(stderr, "%16llu bits minimum size\n",
> +		min_size);
> +	fprintf(stderr, "%16llu bits maximum size\n"
> +		"%16llu bits average size\n",
> +		max_size, avg_size);
> +	fprintf(stderr, "%16llu bits set in bitmap (out of %llu)\n", size,
> +		bitmap->real_end - bitmap->start);
> +	fprintf(stderr,
> +		"%16.4lf memory / bitmap bit memory ratio (bitarray = 1)\n",
> +		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,
> @@ -740,4 +820,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 21d24ad..288e1b6 100644
> --- a/lib/ext2fs/bmap64.h
> +++ b/lib/ext2fs/bmap64.h
> @@ -9,6 +9,34 @@
>   * %End-Header%
>   */
>  
> +struct ext2_bmap_statistics {
> +	int		type;
> +	struct timeval	created;
> +
> +#ifdef BMAP_STATS_OPS
> +	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;
> +#endif /* BMAP_STATS_OPS */
> +};
> +
> +
>  struct ext2fs_struct_generic_bitmap {
>  	errcode_t		magic;
>  	ext2_filsys 		fs;
> @@ -20,6 +48,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) \
> @@ -57,6 +88,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 3f8333f..7343090 100644
> --- a/lib/ext2fs/ext2fs.h
> +++ b/lib/ext2fs/ext2fs.h
> @@ -1168,6 +1168,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 9dcca03..bf1a76b 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_OPS
> +#define INC_STAT(map, name) map->stats.name
> +#else
> +#define INC_STAT(map, name) ;;
> +#endif
> +
>  
>  errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
>  				    int type, __u64 start, __u64 end,
> @@ -110,11 +116,20 @@ errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
>  		return EINVAL;
>  	}
>  
> -	retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap),
> -				&bitmap);
> +	retval = ext2fs_get_memzero(sizeof(struct ext2fs_struct_generic_bitmap),
> +				    &bitmap);
>  	if (retval)
>  		return retval;
>  
> +#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;
> @@ -155,6 +170,71 @@ 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;
> +	struct timeval now;
> +
> +#ifdef BMAP_STATS_OPS
> +	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;
> +	}
> +#endif
> +
> +	if (gettimeofday(&now, (struct timezone *) NULL) == -1) {
> +		perror("gettimeofday");
> +		return;
> +	}
> +
> +	inuse = (double) now.tv_sec + \
> +		(((double) now.tv_usec) * 0.000001);
> +	inuse -= (double) stats->created.tv_sec + \
> +		(((double) stats->created.tv_usec) * 0.000001);
> +
> +	fprintf(stderr, "\n[+] %s bitmap (type %d)\n", bitmap->description,
> +		stats->type);
> +	fprintf(stderr, "=================================================\n");
> +#ifdef BMAP_STATS_OPS
> +	fprintf(stderr, "%16llu 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"
> +		"%16llu bits tested backwards (%.2f%%)\n",
> +		stats->mark_seq, mark_seq_perc,
> +		stats->test_back, test_back_perc);
> +	fprintf(stderr, "%16llu bits marked backwards (%.2f%%)\n"
> +		"%16.2f seconds in use\n",
> +		stats->mark_back, mark_back_perc, inuse);
> +#endif /* BMAP_STATS_OPS */
> +}
> +#endif
> +
>  void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap)
>  {
>  	if (!bmap)
> @@ -168,6 +248,13 @@ void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap)
>  	if (!EXT2FS_IS_64_BITMAP(bmap))
>  		return;
>  
> +#ifdef BMAP_STATS
> +	if (getenv("E2FSPROGS_BITMAP_STATS")) {
> +		ext2fs_print_bmap_statistics(bmap);
> +		bmap->bitmap_ops->print_stats(bmap);
> +	}
> +#endif
> +
>  	bmap->bitmap_ops->free_bmap(bmap);
>  
>  	if (bmap->description) {
> @@ -195,11 +282,24 @@ errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap src,
>  		return EINVAL;
>  
>  	/* Allocate a new bitmap struct */
> -	retval = ext2fs_get_mem(sizeof(struct ext2fs_struct_generic_bitmap),
> -				&new_bmap);
> +	retval = ext2fs_get_memzero(sizeof(struct ext2fs_struct_generic_bitmap),
> +				    &new_bmap);
>  	if (retval)
>  		return retval;
>  
> +
> +#ifdef BMAP_STATS_OPS
> +	src->stats.copy_count++;
> +#endif
> +#ifdef BMAP_STATS
> +	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;
> @@ -247,6 +347,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);
>  }
>  
> @@ -335,6 +437,15 @@ int ext2fs_mark_generic_bmap(ext2fs_generic_bitmap bitmap,
>  
>  	arg >>= bitmap->cluster_bits;
>  
> +#ifdef BMAP_STATS_OPS
> +	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;
> @@ -363,6 +474,8 @@ int ext2fs_unmark_generic_bmap(ext2fs_generic_bitmap bitmap,
>  
>  	arg >>= bitmap->cluster_bits;
>  
> +	INC_STAT(bitmap, unmark_count);
> +
>  	if ((arg < bitmap->start) || (arg > bitmap->end)) {
>  		warn_bitmap(bitmap, EXT2FS_UNMARK_ERROR, arg);
>  		return 0;
> @@ -391,6 +504,15 @@ int ext2fs_test_generic_bmap(ext2fs_generic_bitmap bitmap,
>  
>  	arg >>= bitmap->cluster_bits;
>  
> +#ifdef BMAP_STATS_OPS
> +	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;
> @@ -419,6 +541,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);
>  }
>  
> @@ -442,6 +566,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);
>  }
>  
> @@ -513,6 +639,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);
>  }
>  
> @@ -535,6 +663,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);
> @@ -563,6 +693,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);
> diff --git a/lib/ext2fs/icount.c b/lib/ext2fs/icount.c
> index 5d64ac4..8b46eda 100644
> --- a/lib/ext2fs/icount.c
> +++ b/lib/ext2fs/icount.c
> @@ -104,12 +104,12 @@ static errcode_t alloc_icount(ext2_filsys fs, int flags, ext2_icount_t *ret)
>  		return retval;
>  	memset(icount, 0, sizeof(struct ext2_icount));
>  
> -	retval = ext2fs_allocate_inode_bitmap(fs, 0, &icount->single);
> +	retval = ext2fs_allocate_inode_bitmap(fs, "icount", &icount->single);
>  	if (retval)
>  		goto errout;
>  
>  	if (flags & EXT2_ICOUNT_OPT_INCREMENT) {
> -		retval = ext2fs_allocate_inode_bitmap(fs, 0,
> +		retval = ext2fs_allocate_inode_bitmap(fs, "icount_inc",
>  						      &icount->multiple);
>  		if (retval)
>  			goto errout;
> 

-- 

Re: [PATCH 07/10] libext2fs: use the rbtree bitmap by default when initializing a file system

[Lukas Czerner]

On Sun, 18 Dec 2011, Theodore Ts'o wrote:

> This change causes the max resident memory of mke2fs, as reported by
> /usr/bin/time, to drop from 9296k to 5328k when formatting a 25
> gig volume.

Just for the record, creating bigger file system will show much bigger
difference. For example when creating 100T file system with the old
bitarray backend it will consume 14GB of memory, but with the new rbtree
backend it will only consume 220 MB (reported by /usr/bin/time).

Actually the real allocated memory according to valgrind is 54MB for
rbtree and 3.74GB for bitmap backend. I assume that /usr/bin/time shows
amount of dirtied memory pages ??

A while ago I have done some testing on older version of e2fsprogs with
rbtree patches. The numbers might differ now, but the overall difference
between rbtree and bitmaps should be roughly the same. Here are some
graphs:

http://people.redhat.com/lczerner/e2fsprogs_memory/graphs.pdf

Thanks!
-Lukas

> 
> Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
> ---
>  lib/ext2fs/initialize.c |    1 +
>  1 files changed, 1 insertions(+), 0 deletions(-)
> 
> diff --git a/lib/ext2fs/initialize.c b/lib/ext2fs/initialize.c
> index b050a0a..a63ea18 100644
> --- a/lib/ext2fs/initialize.c
> +++ b/lib/ext2fs/initialize.c
> @@ -112,6 +112,7 @@ errcode_t ext2fs_initialize(const char *name, int flags,
>  	fs->magic = EXT2_ET_MAGIC_EXT2FS_FILSYS;
>  	fs->flags = flags | EXT2_FLAG_RW;
>  	fs->umask = 022;
> +	fs->default_bitmap_type = EXT2FS_BMAP64_RBTREE;
>  #ifdef WORDS_BIGENDIAN
>  	fs->flags |= EXT2_FLAG_SWAP_BYTES;
>  #endif
> 

Re: [PATCH 07/10] libext2fs: use the rbtree bitmap by default when initializing a file system

[Lukas Czerner]

On Mon, 19 Dec 2011, Lukas Czerner wrote:

> On Sun, 18 Dec 2011, Theodore Ts'o wrote:
> 
> > This change causes the max resident memory of mke2fs, as reported by
> > /usr/bin/time, to drop from 9296k to 5328k when formatting a 25
> > gig volume.
> 
> Just for the record, creating bigger file system will show much bigger
> difference. For example when creating 100T file system with the old
> bitarray backend it will consume 14GB of memory, but with the new rbtree
> backend it will only consume 220 MB (reported by /usr/bin/time).
> 
> Actually the real allocated memory according to valgrind is 54MB for
> rbtree and 3.74GB for bitmap backend. I assume that /usr/bin/time shows
> amount of dirtied memory pages ??
> 
> A while ago I have done some testing on older version of e2fsprogs with
> rbtree patches. The numbers might differ now, but the overall difference
> between rbtree and bitmaps should be roughly the same. Here are some
> graphs:
> 
> http://people.redhat.com/lczerner/e2fsprogs_memory/graphs.pdf

Also the testing has been done on e2fsck, rather than mke2fs.

> 
> Thanks!
> -Lukas
> 
> > 
> > Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
> > ---
> >  lib/ext2fs/initialize.c |    1 +
> >  1 files changed, 1 insertions(+), 0 deletions(-)
> > 
> > diff --git a/lib/ext2fs/initialize.c b/lib/ext2fs/initialize.c
> > index b050a0a..a63ea18 100644
> > --- a/lib/ext2fs/initialize.c
> > +++ b/lib/ext2fs/initialize.c
> > @@ -112,6 +112,7 @@ errcode_t ext2fs_initialize(const char *name, int flags,
> >  	fs->magic = EXT2_ET_MAGIC_EXT2FS_FILSYS;
> >  	fs->flags = flags | EXT2_FLAG_RW;
> >  	fs->umask = 022;
> > +	fs->default_bitmap_type = EXT2FS_BMAP64_RBTREE;
> >  #ifdef WORDS_BIGENDIAN
> >  	fs->flags |= EXT2_FLAG_SWAP_BYTES;
> >  #endif
> > 
> --
> 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
> 

--