[PATCH 0/5] Make filesystem shrinking faster and less CPU-intensive

[PATCH 0/5] Make filesystem shrinking faster and less CPU-intensive

[Sami Liedes]

[-- Attachment #1: Type: text/plain, Size: 1202 bytes --]

This patch set speeds up at least resize2fs shrinking by causing its
CPU usage to drop by 99.5% by optimizing inode bitfield scanning.

Test case: A 100G ext4 filesystem filled to 50% with copies of
/usr/share/doc, shrinking to 75G on a slow disk (~5400 rpm) and fast
processor (Core i7):

Before:

# time resize2fs -p $FILESYSTEM 75G
[...]
real    96m26.852s
user    56m39.768s
sys     0m27.922s

After:

# time resize2fs -p $FILESYSTEM 75G
real    39m49.287s
user    0m16.601s
sys     0m26.606s

Sami Liedes (5):
      libext2fs: Move a modulo operation out of a hot loop.
      resize2fs: Use EXT2_FLAG_64BITS.
      libext2fs: Document EXT2_FLAG_64BITS in ext2fs_open2().
      libext2fs: Implement ext2fs_find_first_zero_generic_bmap().
      libext2fs: Implement fast find_first_zero() for bitarray bitmaps.

 lib/ext2fs/alloc.c        |   27 +++------------
 lib/ext2fs/bitops.h       |   16 ---------
 lib/ext2fs/blkmap64_ba.c  |   81 ---------------------------------------------
 lib/ext2fs/bmap64.h       |    5 ---
 lib/ext2fs/gen_bitmap64.c |   28 ---------------
 lib/ext2fs/openfs.c       |    1 -
 resize/main.c             |    3 --
 7 files changed, 5 insertions(+), 156 deletions(-)

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [PATCH 1/5] libext2fs: Move a modulo operation out of a hot loop.

[Sami Liedes]

[-- Attachment #1: Type: text/plain, Size: 1649 bytes --]

From 8d712d4e49cdc8a0b82f27b5b62a7691fafcacbf Mon Sep 17 00:00:00 2001
From: Sami Liedes <sami.liedes@iki.fi>
Date: Sat, 10 Mar 2012 22:13:12 +0200
Subject: [PATCH] libext2fs: Move a modulo operation out of a hot loop.

Filesystem shrinking in particular is a heavy user of this loop in
ext2fs_new_inode(). This change makes resize2fs use 24% less CPU time
for shrinking a 100G filesystem.

Signed-off-by: Sami Liedes <sami.liedes@iki.fi>

diff --git a/lib/ext2fs/alloc.c b/lib/ext2fs/alloc.c
index 948a0ec..eb4e0f5 100644
--- a/lib/ext2fs/alloc.c
+++ b/lib/ext2fs/alloc.c
@@ -109,6 +109,7 @@ errcode_t ext2fs_new_inode(ext2_filsys fs, ext2_ino_t dir,
 	ext2_ino_t	dir_group = 0;
 	ext2_ino_t	i;
 	ext2_ino_t	start_inode;
+	ext2_ino_t	modulo;
 
 	EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
 
@@ -126,17 +127,21 @@ errcode_t ext2fs_new_inode(ext2_filsys fs, ext2_ino_t dir,
 	if (start_inode > fs->super->s_inodes_count)
 		return EXT2_ET_INODE_ALLOC_FAIL;
 	i = start_inode;
+	modulo = (i - 1) % EXT2_INODES_PER_GROUP(fs->super);
 
 	do {
-		if (((i - 1) % EXT2_INODES_PER_GROUP(fs->super)) == 0)
+		if (modulo == 0)
 			check_inode_uninit(fs, map, (i - 1) /
 					   EXT2_INODES_PER_GROUP(fs->super));
 
 		if (!ext2fs_fast_test_inode_bitmap2(map, i))
 			break;
-		i++;
-		if (i > fs->super->s_inodes_count)
+		if (++modulo == EXT2_INODES_PER_GROUP(fs->super))
+			modulo = 0;
+		if (++i > fs->super->s_inodes_count) {
 			i = EXT2_FIRST_INODE(fs->super);
+			modulo = (i - 1) % EXT2_INODES_PER_GROUP(fs->super);
+		}
 	} while (i != start_inode);
 
 	if (ext2fs_test_inode_bitmap2(map, i))

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [PATCH 2/5] resize2fs: Use EXT2_FLAG_64BITS.

[Sami Liedes]

[-- Attachment #1: Type: text/plain, Size: 1087 bytes --]

From 975ea6001ab14b02b1197588bbe40ea133e17568 Mon Sep 17 00:00:00 2001
From: Sami Liedes <sami.liedes@iki.fi>
Date: Sun, 26 Feb 2012 21:54:23 +0200
Subject: [PATCH] resize2fs: Use EXT2_FLAG_64BITS.

By passing EXT2_FLAG_64BITS to ext2fs_open2() we can avoid some
unnecessary redirection in critical paths. While resize2fs does not
currently otherwise support so big filesystems that this would matter,
passing this flag is entirely harmless and only tells libext2fs that
the caller has been recompiled against current headers.

With this change the CPU time needed to shrink a 100G filesystem drops
by 20%.

Signed-off-by: Sami Liedes <sami.liedes@iki.fi>

diff --git a/resize/main.c b/resize/main.c
index ffefe01..e6604f2 100644
--- a/resize/main.c
+++ b/resize/main.c
@@ -294,6 +294,9 @@ int main (int argc, char ** argv)
 
 	if (!(mount_flags & EXT2_MF_MOUNTED))
 		io_flags = EXT2_FLAG_RW | EXT2_FLAG_EXCLUSIVE;
+
+	io_flags |= EXT2_FLAG_64BITS;
+
 	retval = ext2fs_open2(device_name, io_options, io_flags,
 			      0, 0, io_ptr, &fs);
 	if (retval) {

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

[PATCH 3/5] libext2fs: Document EXT2_FLAG_64BITS in ext2fs_open2().

[Sami Liedes]

[-- Attachment #1: Type: text/plain, Size: 859 bytes --]

From 5c7302de65d689ad84427649aab4d361b21270df Mon Sep 17 00:00:00 2001
From: Sami Liedes <sami.liedes@iki.fi>
Date: Sat, 10 Mar 2012 22:25:55 +0200
Subject: [PATCH] libext2fs: Document EXT2_FLAG_64BITS in ext2fs_open2().

Signed-off-by: Sami Liedes <sami.liedes@iki.fi>

diff --git a/lib/ext2fs/openfs.c b/lib/ext2fs/openfs.c
index 32e068c..55082c4 100644
--- a/lib/ext2fs/openfs.c
+++ b/lib/ext2fs/openfs.c
@@ -87,6 +87,7 @@ errcode_t ext2fs_open(const char *name, int flags, int superblock,
  *				features aren't supported.
  *	EXT2_FLAG_JOURNAL_DEV_OK - Open an ext3 journal device
  *	EXT2_FLAG_SKIP_MMP - Open without multi-mount protection check.
+ *	EXT2_FLAG_64BITS - Allow 64-bit bitfields (needed for large filesystems).
  */
 errcode_t ext2fs_open2(const char *name, const char *io_options,
 		       int flags, int superblock,

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

[PATCH 4/5] libext2fs: Implement ext2fs_find_first_zero_generic_bmap().

[Sami Liedes]

[-- Attachment #1: Type: text/plain, Size: 5082 bytes --]

From a58c07c019e4a7e6181f021ae022ebcdc5cce4e2 Mon Sep 17 00:00:00 2001
From: Sami Liedes <sami.liedes@iki.fi>
Date: Sat, 10 Mar 2012 22:36:12 +0200
Subject: [PATCH] libext2fs: Implement ext2fs_find_first_zero_generic_bmap().

This function searches a bitmap for the first zero bit within a range.
It checks if there is a bitmap backend specific implementation
available (if the relevant field in bitmap_ops is non-NULL). If not,
it uses a generic and slow method by repeatedly calling test_bmap() in
a loop. Also change ext2fs_new_inode() to use this new function.

This change in itself does not result in a large speedup, rather it
refactors the code in preparation for the introduction of a faster
find_first_zero() for bitarray based bitmaps.

Signed-off-by: Sami Liedes <sami.liedes@iki.fi>

diff --git a/lib/ext2fs/alloc.c b/lib/ext2fs/alloc.c
index eb4e0f5..1da9532 100644
--- a/lib/ext2fs/alloc.c
+++ b/lib/ext2fs/alloc.c
@@ -109,7 +109,8 @@ errcode_t ext2fs_new_inode(ext2_filsys fs, ext2_ino_t dir,
 	ext2_ino_t	dir_group = 0;
 	ext2_ino_t	i;
 	ext2_ino_t	start_inode;
-	ext2_ino_t	modulo;
+	ext2_ino_t	modulo, upto, first_zero;
+	errcode_t	err;
 
 	EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
 
@@ -128,16 +129,27 @@ errcode_t ext2fs_new_inode(ext2_filsys fs, ext2_ino_t dir,
 		return EXT2_ET_INODE_ALLOC_FAIL;
 	i = start_inode;
 	modulo = (i - 1) % EXT2_INODES_PER_GROUP(fs->super);
-
 	do {
 		if (modulo == 0)
 			check_inode_uninit(fs, map, (i - 1) /
 					   EXT2_INODES_PER_GROUP(fs->super));
 
-		if (!ext2fs_fast_test_inode_bitmap2(map, i))
+		upto = i + (EXT2_INODES_PER_GROUP(fs->super) - modulo);
+		if (i < start_inode && upto >= start_inode)
+			upto = start_inode - 1;
+		if (upto > fs->super->s_inodes_count)
+			upto = fs->super->s_inodes_count;
+
+		err = ext2fs_find_first_zero_inode_bitmap2(map, i, upto, &first_zero);
+		if (!err) {
+			i = first_zero;
 			break;
-		if (++modulo == EXT2_INODES_PER_GROUP(fs->super))
-			modulo = 0;
+		} else {
+			if (err != ENOENT)
+				return EXT2_ET_INODE_ALLOC_FAIL;
+			i = upto;
+		}
+
 		if (++i > fs->super->s_inodes_count) {
 			i = EXT2_FIRST_INODE(fs->super);
 			modulo = (i - 1) % EXT2_INODES_PER_GROUP(fs->super);
diff --git a/lib/ext2fs/bitops.h b/lib/ext2fs/bitops.h
index 83a01e4..70caa86 100644
--- a/lib/ext2fs/bitops.h
+++ b/lib/ext2fs/bitops.h
@@ -188,6 +188,9 @@ extern void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap bitmap,
 					    blk64_t block, unsigned int num);
 extern void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap bitmap,
 					      blk64_t block, unsigned int num);
+extern errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
+						     __u64 start, __u64 end,
+						     __u64 *out);
 
 /*
  * The inline routines themselves...
@@ -593,6 +596,19 @@ _INLINE_ int ext2fs_fast_test_inode_bitmap2(ext2fs_inode_bitmap bitmap,
 					inode);
 }
 
+_INLINE_ errcode_t ext2fs_find_first_zero_inode_bitmap2(ext2fs_inode_bitmap bitmap,
+							ext2_ino_t start,
+							ext2_ino_t end,
+							ext2_ino_t *out)
+{
+	__u64 o;
+	errcode_t rv = ext2fs_find_first_zero_generic_bmap((ext2fs_generic_bitmap) bitmap,
+							   start, end, &o);
+	if (!rv)
+		*out = o;
+	return rv;
+}
+
 _INLINE_ blk64_t ext2fs_get_block_bitmap_start2(ext2fs_block_bitmap bitmap)
 {
 	return ext2fs_get_generic_bmap_start((ext2fs_generic_bitmap) bitmap);
diff --git a/lib/ext2fs/bmap64.h b/lib/ext2fs/bmap64.h
index 288e1b6..f44d379 100644
--- a/lib/ext2fs/bmap64.h
+++ b/lib/ext2fs/bmap64.h
@@ -89,6 +89,11 @@ struct ext2_bitmap_ops {
 				    __u64 start, size_t num, void *out);
 	void (*clear_bmap)(ext2fs_generic_bitmap bitmap);
 	void (*print_stats)(ext2fs_generic_bitmap);
+
+	/* Find the first zero bit between start and end, inclusive.
+	 * May be NULL, in which case a generic function is used. */
+	errcode_t (*find_first_zero)(ext2fs_generic_bitmap bitmap,
+				     __u64 start, __u64 end, __u64 *out);
 };
 
 extern struct ext2_bitmap_ops ext2fs_blkmap64_bitarray;
diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c
index fa8d7b7..b57df54 100644
--- a/lib/ext2fs/gen_bitmap64.c
+++ b/lib/ext2fs/gen_bitmap64.c
@@ -762,3 +762,31 @@ errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs,
 	*bitmap = cmap;
 	return 0;
 }
+
+errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
+					      __u64 start, __u64 end, __u64 *out)
+{
+	int b;
+
+	if (bitmap->bitmap_ops->find_first_zero)
+		return bitmap->bitmap_ops->find_first_zero(bitmap, start, end, out);
+
+	if (!bitmap || !EXT2FS_IS_64_BITMAP(bitmap) || bitmap->cluster_bits)
+		return EINVAL;
+
+	if (start < bitmap->start || end > bitmap->end || start > end) {
+		warn_bitmap(bitmap, EXT2FS_TEST_ERROR, start);
+		return EINVAL;
+	}
+
+	while (start <= end) {
+		b = bitmap->bitmap_ops->test_bmap(bitmap, start);
+		if (!b) {
+			*out = start;
+			return 0;
+		}
+		start++;
+	}
+
+	return ENOENT;
+}

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

[PATCH 5/5] libext2fs: Implement fast find_first_zero() for bitarray bitmaps.

[Sami Liedes]

[-- Attachment #1: Type: text/plain, Size: 3001 bytes --]

From 020d7721d9de525e511b4778795d375675160844 Mon Sep 17 00:00:00 2001
From: Sami Liedes <sami.liedes@iki.fi>
Date: Sat, 10 Mar 2012 22:50:51 +0200
Subject: [PATCH] libext2fs: Implement fast find_first_zero() for bitarray
 bitmaps.

With this change the CPU time needed to shrink a 100G filesystem drops
to 0.8% of the original (17 CPU seconds instead of 2057).

Signed-off-by: Sami Liedes <sami.liedes@iki.fi>

diff --git a/lib/ext2fs/blkmap64_ba.c b/lib/ext2fs/blkmap64_ba.c
index 3f0c643..8eddde9 100644
--- a/lib/ext2fs/blkmap64_ba.c
+++ b/lib/ext2fs/blkmap64_ba.c
@@ -317,6 +317,86 @@ static void ba_print_stats(ext2fs_generic_bitmap bitmap)
 		sizeof(struct ext2fs_ba_private_struct));
 }
 
+/* Find the first zero bit between start and end, inclusive. */
+static errcode_t ba_find_first_zero(ext2fs_generic_bitmap bitmap,
+				    __u64 start, __u64 end, __u64 *out)
+{
+	ext2fs_ba_private bp = (ext2fs_ba_private)bitmap->private;
+	unsigned long bitpos = start - bitmap->start;
+	unsigned long count = end - start + 1;
+	int byte_found = 0; /* whether a != 0xff byte has been found */
+	const unsigned char *pos;
+	unsigned long max_loop_count, i;
+
+	if (start < bitmap->start || end > bitmap->end || start > end)
+		return EINVAL;
+
+	if (bitmap->cluster_bits)
+		return EINVAL;
+
+	/* scan bits until we hit a byte boundary */
+	while ((bitpos & 0x7) != 0 && count > 0) {
+		if (!ext2fs_test_bit64(bitpos, bp->bitarray)) {
+			*out = bitpos + bitmap->start;
+			return 0;
+		}
+		bitpos++;
+		count--;
+	}
+
+	if (!count)
+		return ENOENT;
+
+	pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3);
+	/* scan bytes until 8-byte (64-bit) aligned */
+	while (count >= 8 && (((unsigned long)pos) & 0x07)) {
+		if (*pos != 0xff) {
+			byte_found = 1;
+			break;
+		}
+		pos++;
+		count -= 8;
+		bitpos += 8;
+	}
+
+	if (!byte_found) {
+		max_loop_count = count >> 6; /* 8-byte blocks */
+		i = max_loop_count;
+		while (i) {
+			if (*((const __u64 *)pos) != ((__u64)-1))
+				break;
+			pos += 8;
+			i--;
+		}
+		count -= 64 * (max_loop_count - i);
+		bitpos += 64 * (max_loop_count - i);
+
+		max_loop_count = count >> 3;
+		i = max_loop_count;
+		while (i) {
+			if (*pos != 0xff) {
+				byte_found = 1;
+				break;
+			}
+			pos++;
+			i--;
+		}
+		count -= 8 * (max_loop_count - i);
+		bitpos += 8 * (max_loop_count - i);
+	}
+
+	/* Here either count < 8 or byte_found == 1. */
+	while (count-- > 0) {
+		if (!ext2fs_test_bit64(bitpos, bp->bitarray)) {
+			*out = bitpos + bitmap->start;
+			return 0;
+		}
+		bitpos++;
+	}
+
+	return ENOENT;
+}
+
 struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = {
 	.type = EXT2FS_BMAP64_BITARRAY,
 	.new_bmap = ba_new_bmap,
@@ -333,4 +413,5 @@ struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = {
 	.get_bmap_range = ba_get_bmap_range,
 	.clear_bmap = ba_clear_bmap,
 	.print_stats = ba_print_stats,
+	.find_first_zero = ba_find_first_zero
 };

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [PATCH 1/5] libext2fs: Move a modulo operation out of a hot loop.

[Andreas Dilger]

On 2012-03-10, at 2:34 PM, Sami Liedes wrote:
> From 8d712d4e49cdc8a0b82f27b5b62a7691fafcacbf Mon Sep 17 00:00:00 2001
> From: Sami Liedes <sami.liedes@iki.fi>
> Date: Sat, 10 Mar 2012 22:13:12 +0200
> Subject: [PATCH] libext2fs: Move a modulo operation out of a hot loop.
> 
> Filesystem shrinking in particular is a heavy user of this loop in
> ext2fs_new_inode(). This change makes resize2fs use 24% less CPU time
> for shrinking a 100G filesystem.
> 
> Signed-off-by: Sami Liedes <sami.liedes@iki.fi>
> 
> diff --git a/lib/ext2fs/alloc.c b/lib/ext2fs/alloc.c
> index 948a0ec..eb4e0f5 100644
> --- a/lib/ext2fs/alloc.c
> +++ b/lib/ext2fs/alloc.c
> @@ -109,6 +109,7 @@ errcode_t ext2fs_new_inode(ext2_filsys fs, ext2_ino_t dir,
> 	ext2_ino_t	dir_group = 0;
> 	ext2_ino_t	i;
> 	ext2_ino_t	start_inode;
> +	ext2_ino_t	modulo;

Good to see someone working on optimizing this code.  One comment on this patch -
"modulo" isn't a very good name for this variable.  Sure it is a modulus, but it
doesn't really say _what_ it is.  Better would be something like "inode_in_group".

> 	EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
> 
> @@ -126,17 +127,21 @@ errcode_t ext2fs_new_inode(ext2_filsys fs, ext2_ino_t dir,
> 	if (start_inode > fs->super->s_inodes_count)
> 		return EXT2_ET_INODE_ALLOC_FAIL;
> 	i = start_inode;
> +	modulo = (i - 1) % EXT2_INODES_PER_GROUP(fs->super);
> 
> 	do {
> -		if (((i - 1) % EXT2_INODES_PER_GROUP(fs->super)) == 0)
> +		if (modulo == 0)
> 			check_inode_uninit(fs, map, (i - 1) /
> 					   EXT2_INODES_PER_GROUP(fs->super));
> 
> 		if (!ext2fs_fast_test_inode_bitmap2(map, i))
> 			break;
> -		i++;
> -		if (i > fs->super->s_inodes_count)
> +		if (++modulo == EXT2_INODES_PER_GROUP(fs->super))
> +			modulo = 0;
> +		if (++i > fs->super->s_inodes_count) {
> 			i = EXT2_FIRST_INODE(fs->super);
> +			modulo = (i - 1) % EXT2_INODES_PER_GROUP(fs->super);
> +		}
> 	} while (i != start_inode);
> 
> 	if (ext2fs_test_inode_bitmap2(map, i))


Cheers, Andreas

Re: [PATCH 4/5] libext2fs: Implement ext2fs_find_first_zero_generic_bmap().

[Andreas Dilger]

On 2012-03-10, at 2:37 PM, Sami Liedes wrote:
> From a58c07c019e4a7e6181f021ae022ebcdc5cce4e2 Mon Sep 17 00:00:00 2001
> From: Sami Liedes <sami.liedes@iki.fi>
> Date: Sat, 10 Mar 2012 22:36:12 +0200
> Subject: [PATCH] libext2fs: Implement ext2fs_find_first_zero_generic_bmap().
> 
> This function searches a bitmap for the first zero bit within a range.
> It checks if there is a bitmap backend specific implementation
> available (if the relevant field in bitmap_ops is non-NULL). If not,
> it uses a generic and slow method by repeatedly calling test_bmap() in
> a loop. Also change ext2fs_new_inode() to use this new function.
> 
> This change in itself does not result in a large speedup, rather it
> refactors the code in preparation for the introduction of a faster
> find_first_zero() for bitarray based bitmaps.

Rather than making the bitmap searching loop more efficient, I've always thought
it would be better to have an interface that iterates over the bitmap and returns
the next set bit.  It is similar to what you implemented with ->find_first_zero(),
but it would be better to have (IMHO) ->find_next_zero() and ->find_next_set().

This allows the internal bitmap implementation to do efficient walking of the
bitmap/tree/list and in cases where the bitmap is very sparse it can avoid a
lot of scanning.

> Signed-off-by: Sami Liedes <sami.liedes@iki.fi>
> 
> diff --git a/lib/ext2fs/alloc.c b/lib/ext2fs/alloc.c
> index eb4e0f5..1da9532 100644
> --- a/lib/ext2fs/alloc.c
> +++ b/lib/ext2fs/alloc.c
> @@ -109,7 +109,8 @@ errcode_t ext2fs_new_inode(ext2_filsys fs, ext2_ino_t dir,
> 	ext2_ino_t	dir_group = 0;
> 	ext2_ino_t	i;
> 	ext2_ino_t	start_inode;
> -	ext2_ino_t	modulo;
> +	ext2_ino_t	modulo, upto, first_zero;
> +	errcode_t	err;
> 
> 	EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
> 
> @@ -128,16 +129,27 @@ errcode_t ext2fs_new_inode(ext2_filsys fs, ext2_ino_t dir,
> 		return EXT2_ET_INODE_ALLOC_FAIL;
> 	i = start_inode;
> 	modulo = (i - 1) % EXT2_INODES_PER_GROUP(fs->super);
> -
> 	do {
> 		if (modulo == 0)
> 			check_inode_uninit(fs, map, (i - 1) /
> 					   EXT2_INODES_PER_GROUP(fs->super));
> 
> -		if (!ext2fs_fast_test_inode_bitmap2(map, i))
> +		upto = i + (EXT2_INODES_PER_GROUP(fs->super) - modulo);
> +		if (i < start_inode && upto >= start_inode)
> +			upto = start_inode - 1;
> +		if (upto > fs->super->s_inodes_count)
> +			upto = fs->super->s_inodes_count;
> +
> +		err = ext2fs_find_first_zero_inode_bitmap2(map, i, upto, &first_zero);
> +		if (!err) {
> +			i = first_zero;
> 			break;
> -		if (++modulo == EXT2_INODES_PER_GROUP(fs->super))
> -			modulo = 0;
> +		} else {
> +			if (err != ENOENT)
> +				return EXT2_ET_INODE_ALLOC_FAIL;
> +			i = upto;
> +		}
> +
> 		if (++i > fs->super->s_inodes_count) {
> 			i = EXT2_FIRST_INODE(fs->super);
> 			modulo = (i - 1) % EXT2_INODES_PER_GROUP(fs->super);
> diff --git a/lib/ext2fs/bitops.h b/lib/ext2fs/bitops.h
> index 83a01e4..70caa86 100644
> --- a/lib/ext2fs/bitops.h
> +++ b/lib/ext2fs/bitops.h
> @@ -188,6 +188,9 @@ extern void ext2fs_mark_block_bitmap_range2(ext2fs_block_bitmap bitmap,
> 					    blk64_t block, unsigned int num);
> extern void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap bitmap,
> 					      blk64_t block, unsigned int num);
> +extern errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
> +						     __u64 start, __u64 end,
> +						     __u64 *out);
> 
> /*
>  * The inline routines themselves...
> @@ -593,6 +596,19 @@ _INLINE_ int ext2fs_fast_test_inode_bitmap2(ext2fs_inode_bitmap bitmap,
> 					inode);
> }
> 
> +_INLINE_ errcode_t ext2fs_find_first_zero_inode_bitmap2(ext2fs_inode_bitmap bitmap,
> +							ext2_ino_t start,
> +							ext2_ino_t end,
> +							ext2_ino_t *out)
> +{
> +	__u64 o;
> +	errcode_t rv = ext2fs_find_first_zero_generic_bmap((ext2fs_generic_bitmap) bitmap,
> +							   start, end, &o);
> +	if (!rv)
> +		*out = o;
> +	return rv;
> +}
> +
> _INLINE_ blk64_t ext2fs_get_block_bitmap_start2(ext2fs_block_bitmap bitmap)
> {
> 	return ext2fs_get_generic_bmap_start((ext2fs_generic_bitmap) bitmap);
> diff --git a/lib/ext2fs/bmap64.h b/lib/ext2fs/bmap64.h
> index 288e1b6..f44d379 100644
> --- a/lib/ext2fs/bmap64.h
> +++ b/lib/ext2fs/bmap64.h
> @@ -89,6 +89,11 @@ struct ext2_bitmap_ops {
> 				    __u64 start, size_t num, void *out);
> 	void (*clear_bmap)(ext2fs_generic_bitmap bitmap);
> 	void (*print_stats)(ext2fs_generic_bitmap);
> +
> +	/* Find the first zero bit between start and end, inclusive.
> +	 * May be NULL, in which case a generic function is used. */
> +	errcode_t (*find_first_zero)(ext2fs_generic_bitmap bitmap,
> +				     __u64 start, __u64 end, __u64 *out);
> };
> 
> extern struct ext2_bitmap_ops ext2fs_blkmap64_bitarray;
> diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c
> index fa8d7b7..b57df54 100644
> --- a/lib/ext2fs/gen_bitmap64.c
> +++ b/lib/ext2fs/gen_bitmap64.c
> @@ -762,3 +762,31 @@ errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs,
> 	*bitmap = cmap;
> 	return 0;
> }
> +
> +errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
> +					      __u64 start, __u64 end, __u64 *out)
> +{
> +	int b;
> +
> +	if (bitmap->bitmap_ops->find_first_zero)
> +		return bitmap->bitmap_ops->find_first_zero(bitmap, start, end, out);
> +
> +	if (!bitmap || !EXT2FS_IS_64_BITMAP(bitmap) || bitmap->cluster_bits)
> +		return EINVAL;
> +
> +	if (start < bitmap->start || end > bitmap->end || start > end) {
> +		warn_bitmap(bitmap, EXT2FS_TEST_ERROR, start);
> +		return EINVAL;
> +	}
> +
> +	while (start <= end) {
> +		b = bitmap->bitmap_ops->test_bmap(bitmap, start);
> +		if (!b) {
> +			*out = start;
> +			return 0;
> +		}
> +		start++;
> +	}
> +
> +	return ENOENT;
> +}


Cheers, Andreas

Re: [PATCH 4/5] libext2fs: Implement ext2fs_find_first_zero_generic_bmap().

[Sami Liedes]

[-- Attachment #1: Type: text/plain, Size: 2065 bytes --]

On Sun, Mar 11, 2012 at 03:51:05AM -0600, Andreas Dilger wrote:
> Rather than making the bitmap searching loop more efficient, I've always thought
> it would be better to have an interface that iterates over the bitmap and returns
> the next set bit.  It is similar to what you implemented with ->find_first_zero(),
> but it would be better to have (IMHO) ->find_next_zero() and ->find_next_set().

I've been thinking about this. Such an interface might be a good idea,
and I could implement it and a corresponding backend implementation
for the bit array backend, but I don't think ext2fs_new_inode() could
properly exercise it and I'm hesitant to submit code that isn't tested
by being actually properly used somewhere. I will still do it if
there's a general consensus that it's a good idea.

It could be something along the lines of

* type ext2fs_bitmap_iterator, opaque to calling code, mainly a magic
  number and backend-specific private data. In the bitarray case it
  could just be the number of the bit pointed to and the end of the
  range to iterate.

* bool bitmap_ops->deref_iterator(ext2fs_generic_bitmap, ext2fs_bitmap_iterator)

* ext2fs_bitmap_iterator ops->create_iterator()
                            ->create_ranged_iterator(__u64 start, __u64 end)
                            ->free_iterator(ext2fs_bitmap_iterator) 

* __u64 bitmap_ops->iterator_position(...)

* errcode_t ops->find_next_zero(..., __u64 *pos),
               ->find_next_set(..., __u64 *pos)
  * These would both increment the iterator and, if pos != NULL, set
    *pos to the new bit position

* Modifying a bitmap invalidates all its iterators in such a way that
  the only legal operation for them afterwards is ->free_iterator()

In the case of ext2fs_new_inode(), the function does not actually
iterate through all zero bits; it really only wants to find the first
zero in a certain range, after which it returns. So for simplicity of
use (and efficiency) I think it still makes sense to have
->find_first_zero() too.

	Sami

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 836 bytes --]

Re: [PATCH 4/5] libext2fs: Implement ext2fs_find_first_zero_generic_bmap().

[Andreas Dilger]

[-- Attachment #1: Type: text/plain, Size: 3046 bytes --]

On 2012-03-12, at 1:15 PM, Sami Liedes wrote:
> On Sun, Mar 11, 2012 at 03:51:05AM -0600, Andreas Dilger wrote:
>> Rather than making the bitmap searching loop more efficient, I've always thought
>> it would be better to have an interface that iterates over the bitmap and returns
>> the next set bit.  It is similar to what you implemented with ->find_first_zero(),
>> but it would be better to have (IMHO) ->find_next_zero() and ->find_next_set().
> 
> I've been thinking about this. Such an interface might be a good idea,
> and I could implement it and a corresponding backend implementation
> for the bit array backend, but I don't think ext2fs_new_inode() could
> properly exercise it and I'm hesitant to submit code that isn't tested
> by being actually properly used somewhere.

It is actually common practise in e2fsprogs to embed test programs in the
code being modified.  See tst_bitmaps.c, for example.  That can give you
better test coverage for rarely executed code, and the tests should be run
by anyone modifying the e2fsprogs code and for every RPM build.

The ext2fs_new_block2() function could be improved in a similar manner, and
in fact benefits even more than the inode allocator, because far more blocks
are allocated under normal usage.

> I will still do it if there's a general consensus that it's a good idea.

Let's hear back from Ted first.  He will probably have some good feedback on
the API design that he would like.

> It could be something along the lines of
> 
> * type ext2fs_bitmap_iterator, opaque to calling code, mainly a magic
>  number and backend-specific private data. In the bitarray case it
>  could just be the number of the bit pointed to and the end of the
>  range to iterate.
> 
> * bool bitmap_ops->deref_iterator(ext2fs_generic_bitmap, ext2fs_bitmap_iterator)
> 
> * ext2fs_bitmap_iterator ops->create_iterator()
>                            ->create_ranged_iterator(__u64 start, __u64 end)
>                            ->free_iterator(ext2fs_bitmap_iterator) 
> 
> * __u64 bitmap_ops->iterator_position(...)
> 
> * errcode_t ops->find_next_zero(..., __u64 *pos),
>               ->find_next_set(..., __u64 *pos)
>  * These would both increment the iterator and, if pos != NULL, set
>    *pos to the new bit position
> 
> * Modifying a bitmap invalidates all its iterators in such a way that
>  the only legal operation for them afterwards is ->free_iterator()

Note that there is already the rbtree bitmap implementation, which is needed
for huge filesystems in order to be able to run e2fsck without needing huge
amounts of RAM, so it should also have a backend iterator implementation.

> In the case of ext2fs_new_inode(), the function does not actually
> iterate through all zero bits; it really only wants to find the first
> zero in a certain range, after which it returns. So for simplicity of
> use (and efficiency) I think it still makes sense to have
> ->find_first_zero() too.
> 
> 	Sami


Cheers, Andreas






[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 235 bytes --]

Re: [PATCH 4/5] libext2fs: Implement ext2fs_find_first_zero_generic_bmap().

[Ted Ts'o]

On Mon, Mar 12, 2012 at 09:15:14PM +0200, Sami Liedes wrote:
> In the case of ext2fs_new_inode(), the function does not actually
> iterate through all zero bits; it really only wants to find the first
> zero in a certain range, after which it returns. So for simplicity of
> use (and efficiency) I think it still makes sense to have
> ->find_first_zero() too.

I agree, a find_first_zero() and a find_first_set(), both of which
taking a starting bit position for the search, and the best low-level
primitives that would be implemented on for each backend bitmap
implementation.

It would then be very easy to build iterators on *top* of
find_first_zero() and find_first_set(), and in fact this could be used
to replace some of the places where we are using a sorted list (i.e.,
the badblocks list).  So that sounds like a good idea, and I can
definitely think of some places where we could use that code today.

So I plan to pull in your patch series and then we can further enhance
this with iterator support afterwards.  Sami, if you'd be interested
in implementing iterators, that would be great!

Thanks,

   			   	      	 - Ted

Re: [PATCH 5/5] libext2fs: Implement fast find_first_zero() for bitarray bitmaps.

[Ted Ts'o]

On Sat, Mar 10, 2012 at 11:38:40PM +0200, Sami Liedes wrote:
> +/* Find the first zero bit between start and end, inclusive. */
> +static errcode_t ba_find_first_zero(ext2fs_generic_bitmap bitmap,
> +				    __u64 start, __u64 end, __u64 *out)
> +{
> +	ext2fs_ba_private bp = (ext2fs_ba_private)bitmap->private;
> +	unsigned long bitpos = start - bitmap->start;
> +	unsigned long count = end - start + 1;
> +	int byte_found = 0; /* whether a != 0xff byte has been found */
> +	const unsigned char *pos;
> +	unsigned long max_loop_count, i;
> +
> +	if (start < bitmap->start || end > bitmap->end || start > end)
> +		return EINVAL;
> +
> +	if (bitmap->cluster_bits)
> +		return EINVAL;
> +
> +	/* scan bits until we hit a byte boundary */
> +	while ((bitpos & 0x7) != 0 && count > 0) {
> +		if (!ext2fs_test_bit64(bitpos, bp->bitarray)) {
> +			*out = bitpos + bitmap->start;
> +			return 0;
> +		}
> +		bitpos++;
> +		count--;
> +	}
> +
> +	if (!count)
> +		return ENOENT;

Um, this can't possibly be right.  Once we hit a byte boundary, we
will bomb out with ENOENT, and not proceed to the rest of the
function.  How much testing did you do before you submitted this patch
series?

I think we just need to delete the two lines, but we also need a good
regression test to make sure the implementation is really correct....

					- Ted

> +
> +	pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3);
> +	/* scan bytes until 8-byte (64-bit) aligned */
> +	while (count >= 8 && (((unsigned long)pos) & 0x07)) {
> +		if (*pos != 0xff) {
> +			byte_found = 1;
> +			break;
> +		}
> +		pos++;
> +		count -= 8;
> +		bitpos += 8;
> +	}
> +
> +	if (!byte_found) {
> +		max_loop_count = count >> 6; /* 8-byte blocks */
> +		i = max_loop_count;
> +		while (i) {
> +			if (*((const __u64 *)pos) != ((__u64)-1))
> +				break;
> +			pos += 8;
> +			i--;
> +		}
> +		count -= 64 * (max_loop_count - i);
> +		bitpos += 64 * (max_loop_count - i);
> +
> +		max_loop_count = count >> 3;
> +		i = max_loop_count;
> +		while (i) {
> +			if (*pos != 0xff) {
> +				byte_found = 1;
> +				break;
> +			}
> +			pos++;
> +			i--;
> +		}
> +		count -= 8 * (max_loop_count - i);
> +		bitpos += 8 * (max_loop_count - i);
> +	}
> +
> +	/* Here either count < 8 or byte_found == 1. */
> +	while (count-- > 0) {
> +		if (!ext2fs_test_bit64(bitpos, bp->bitarray)) {
> +			*out = bitpos + bitmap->start;
> +			return 0;
> +		}
> +		bitpos++;
> +	}
> +
> +	return ENOENT;
> +}
> +
>  struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = {
>  	.type = EXT2FS_BMAP64_BITARRAY,
>  	.new_bmap = ba_new_bmap,
> @@ -333,4 +413,5 @@ struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = {
>  	.get_bmap_range = ba_get_bmap_range,
>  	.clear_bmap = ba_clear_bmap,
>  	.print_stats = ba_print_stats,
> +	.find_first_zero = ba_find_first_zero
>  };

Re: [PATCH 4/5] libext2fs: Implement ext2fs_find_first_zero_generic_bmap().

[Ted Ts'o]

On Sat, Mar 10, 2012 at 11:37:40PM +0200, Sami Liedes wrote:
> @@ -128,16 +129,27 @@ errcode_t ext2fs_new_inode(ext2_filsys fs, ext2_ino_t dir,
>  		return EXT2_ET_INODE_ALLOC_FAIL;
>  	i = start_inode;
>  	modulo = (i - 1) % EXT2_INODES_PER_GROUP(fs->super);
> -
>  	do {
>  		if (modulo == 0)
>  			check_inode_uninit(fs, map, (i - 1) /
>  					   EXT2_INODES_PER_GROUP(fs->super));
>  
> -		if (!ext2fs_fast_test_inode_bitmap2(map, i))
> +		upto = i + (EXT2_INODES_PER_GROUP(fs->super) - modulo);
> +		if (i < start_inode && upto >= start_inode)
> +			upto = start_inode - 1;
> +		if (upto > fs->super->s_inodes_count)
> +			upto = fs->super->s_inodes_count;
> +
> +		err = ext2fs_find_first_zero_inode_bitmap2(map, i, upto, &first_zero);
> +		if (!err) {
> +			i = first_zero;
>  			break;
> -		if (++modulo == EXT2_INODES_PER_GROUP(fs->super))
> -			modulo = 0;
> +		} else {
> +			if (err != ENOENT)
> +				return EXT2_ET_INODE_ALLOC_FAIL;
> +			i = upto;
> +		}
> +
>  		if (++i > fs->super->s_inodes_count) {
>  			i = EXT2_FIRST_INODE(fs->super);
>  			modulo = (i - 1) % EXT2_INODES_PER_GROUP(fs->super);

There a bug in this code.  modulo (which I've renamed to ino_in_group
per Andreas's suggestion) isn't getting updated, and after the first
pass through the loop modulo needs to be zero.  Otherwise the code
will end up spanning group boundaries and check_inode_uninit won't get
called at the right times.

I've fixed this up and applied it, with some changes to make sure
ext2fs_new_inode() is easier to understand, and hence audit for
correctness.  It now looks like this:

errcode_t ext2fs_new_inode(ext2_filsys fs, ext2_ino_t dir,
			   int mode EXT2FS_ATTR((unused)),
			   ext2fs_inode_bitmap map, ext2_ino_t *ret)
{
	ext2_ino_t	start_inode = 0;
	ext2_ino_t	i, ino_in_group, upto, first_zero;
	errcode_t	retval;
	dgrp_t		group;

	EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);

	if (!map)
		map = fs->inode_map;
	if (!map)
		return EXT2_ET_NO_INODE_BITMAP;

	if (dir > 0) {
		group = (dir - 1) / EXT2_INODES_PER_GROUP(fs->super);
		start_inode = (group * EXT2_INODES_PER_GROUP(fs->super)) + 1;
	}
	if (start_inode < EXT2_FIRST_INODE(fs->super))
		start_inode = EXT2_FIRST_INODE(fs->super);
	if (start_inode > fs->super->s_inodes_count)
		return EXT2_ET_INODE_ALLOC_FAIL;
	i = start_inode;
	do {
		ino_in_group = (i - 1) % EXT2_INODES_PER_GROUP(fs->super);
		group = (i - 1) / EXT2_INODES_PER_GROUP(fs->super);

		check_inode_uninit(fs, map, group);
		upto = i + (EXT2_INODES_PER_GROUP(fs->super) - ino_in_group);
		if (i < start_inode && upto >= start_inode)
			upto = start_inode - 1;
		if (upto > fs->super->s_inodes_count)
			upto = fs->super->s_inodes_count;

		retval = ext2fs_find_first_zero_inode_bitmap2(map, i, upto,
							      &first_zero);
		if (retval == 0) {
			i = first_zero;
			break;
		}
		if (retval != ENOENT)
			return EXT2_ET_INODE_ALLOC_FAIL;
		i = upto + 1;
		if (i > fs->super->s_inodes_count)
			i = EXT2_FIRST_INODE(fs->super);
	} while (i != start_inode);

	if (ext2fs_test_inode_bitmap2(map, i))
		return EXT2_ET_INODE_ALLOC_FAIL;
	*ret = i;
	return 0;
}

					- Ted

Re: [PATCH 5/5] libext2fs: Implement fast find_first_zero() for bitarray bitmaps.

[Sami Liedes]

On Sun, Mar 25, 2012 at 10:34:00PM -0400, Ted Ts'o wrote:
> On Sat, Mar 10, 2012 at 11:38:40PM +0200, Sami Liedes wrote:
> > +/* Find the first zero bit between start and end, inclusive. */
> > +static errcode_t ba_find_first_zero(ext2fs_generic_bitmap bitmap,
> > +				    __u64 start, __u64 end, __u64 *out)
> > +{
> > +	ext2fs_ba_private bp = (ext2fs_ba_private)bitmap->private;
> > +	unsigned long bitpos = start - bitmap->start;
> > +	unsigned long count = end - start + 1;
> > +	int byte_found = 0; /* whether a != 0xff byte has been found */
> > +	const unsigned char *pos;
> > +	unsigned long max_loop_count, i;
> > +
> > +	if (start < bitmap->start || end > bitmap->end || start > end)
> > +		return EINVAL;
> > +
> > +	if (bitmap->cluster_bits)
> > +		return EINVAL;
> > +
> > +	/* scan bits until we hit a byte boundary */
> > +	while ((bitpos & 0x7) != 0 && count > 0) {
> > +		if (!ext2fs_test_bit64(bitpos, bp->bitarray)) {
> > +			*out = bitpos + bitmap->start;
> > +			return 0;
> > +		}
> > +		bitpos++;
> > +		count--;
> > +	}
> > +
> > +	if (!count)
> > +		return ENOENT;
> 
> Um, this can't possibly be right.  Once we hit a byte boundary, we
> will bomb out with ENOENT, and not proceed to the rest of the
> function.  How much testing did you do before you submitted this patch
> series?
> 
> I think we just need to delete the two lines, but we also need a good
> regression test to make sure the implementation is really correct....

Hmm, no, I don't think so? count==0 here iff we have tested as many
bits as the caller requested. So this code will bail out if the number
of bits to test is not large enough to even hit a byte boundary, or if
the last bit to test and the byte boundary coincide. Perhaps count
should be renamed to something like bits_left_to_test if it's
confusing now?

Looking at the code, in retrospect I think it's indeed safe to delete
these two lines, but then the path to the "return ENOENT" in the end
of the function is a bit contrived and laden with calculations that
really expect that bitpos points to a byte boundary. Personally I
think it's better anyway to bail out earlier here if count reaches 0,
if only because it is (or so I thought...) immediately obvious this
way that this special case is handled too.

As to the question of testing of this patch set:

1) I did some throwaway tests on this function; I didn't notice there
   were tests in the sources until Andreas pointed that out, so I
   didn't put any of that in tst_bitmaps.c...

2) I ran resize2fs on an actual filesystem and verified that the
   outputs of dumpe2fs were identical, except for the last written
   time, for the resulting filesystems with and without this patch
   set.

I realize it would have been better to test that the resulting
filesystem images are identical except for the bytes where the
timestamp is stored. I don't actually know how much relevant
information dumpe2fs outputs. In fact I first tried to test for
identical output, but then noticed the timestamp, became lazy and
reasoned that dumpe2fs would probably show any relevant differences
since we're talking about inode allocation here.

I agree that a regression test is needed. I'll look into writing that.

	Sami

> > +
> > +	pos = ((unsigned char *)bp->bitarray) + (bitpos >> 3);
> > +	/* scan bytes until 8-byte (64-bit) aligned */
> > +	while (count >= 8 && (((unsigned long)pos) & 0x07)) {
> > +		if (*pos != 0xff) {
> > +			byte_found = 1;
> > +			break;
> > +		}
> > +		pos++;
> > +		count -= 8;
> > +		bitpos += 8;
> > +	}
> > +
> > +	if (!byte_found) {
> > +		max_loop_count = count >> 6; /* 8-byte blocks */
> > +		i = max_loop_count;
> > +		while (i) {
> > +			if (*((const __u64 *)pos) != ((__u64)-1))
> > +				break;
> > +			pos += 8;
> > +			i--;
> > +		}
> > +		count -= 64 * (max_loop_count - i);
> > +		bitpos += 64 * (max_loop_count - i);
> > +
> > +		max_loop_count = count >> 3;
> > +		i = max_loop_count;
> > +		while (i) {
> > +			if (*pos != 0xff) {
> > +				byte_found = 1;
> > +				break;
> > +			}
> > +			pos++;
> > +			i--;
> > +		}
> > +		count -= 8 * (max_loop_count - i);
> > +		bitpos += 8 * (max_loop_count - i);
> > +	}
> > +
> > +	/* Here either count < 8 or byte_found == 1. */
> > +	while (count-- > 0) {
> > +		if (!ext2fs_test_bit64(bitpos, bp->bitarray)) {
> > +			*out = bitpos + bitmap->start;
> > +			return 0;
> > +		}
> > +		bitpos++;
> > +	}
> > +
> > +	return ENOENT;
> > +}
> > +
> >  struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = {
> >  	.type = EXT2FS_BMAP64_BITARRAY,
> >  	.new_bmap = ba_new_bmap,
> > @@ -333,4 +413,5 @@ struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = {
> >  	.get_bmap_range = ba_get_bmap_range,
> >  	.clear_bmap = ba_clear_bmap,
> >  	.print_stats = ba_print_stats,
> > +	.find_first_zero = ba_find_first_zero
> >  };
> 
> 

Re: [PATCH 4/5] libext2fs: Implement ext2fs_find_first_zero_generic_bmap().

[Sami Liedes]

On Fri, Mar 23, 2012 at 06:33:31PM -0400, Ted Ts'o wrote:
> It would then be very easy to build iterators on *top* of
> find_first_zero() and find_first_set(), and in fact this could be used
> to replace some of the places where we are using a sorted list (i.e.,
> the badblocks list).  So that sounds like a good idea, and I can
> definitely think of some places where we could use that code today.
> 
> So I plan to pull in your patch series and then we can further enhance
> this with iterator support afterwards.  Sami, if you'd be interested
> in implementing iterators, that would be great!

Just to be on the same page, what is the motivation for iterators? Is
it performance, making the code cleaner or facilitating further
functionality?

If it's driven by performance concerns, it would be good to first have
a case where they cause performance problems. Otherwise it would be
good to first figure out a program in the e2fsprogs suite that
exercises (or could exercise) the code in question, just for testing.

My work on inode allocation was actually entirely driven by a friend's
observation that resize2fs took 16 CPU hours to shrink a filesystem.
Profile-guided optimization is something I generally do a lot, but I'm
not averse to doing other kinds of useful coding tasks for useful open
source projects.

	Sami

Re: [PATCH 5/5] libext2fs: Implement fast find_first_zero() for bitarray bitmaps.

[Ted Ts'o]

On Mon, Mar 26, 2012 at 04:22:58PM +0300, Sami Liedes wrote:
> Hmm, no, I don't think so? count==0 here iff we have tested as many
> bits as the caller requested. So this code will bail out if the number
> of bits to test is not large enough to even hit a byte boundary, or if
> the last bit to test and the byte boundary coincide. Perhaps count
> should be renamed to something like bits_left_to_test if it's
> confusing now?

Ah, you're right, my bad.  I managed to confuse myself with !count.
In cases where we're not dealing with a boolean value, it's actually
better to write (count == 0), for this reason.

> I agree that a regression test is needed. I'll look into writing that.

If you could work on improving tst_bitmaps, that would be great.  Thanks!!

       	     	     	       		    - Ted

Re: [PATCH 4/5] libext2fs: Implement ext2fs_find_first_zero_generic_bmap().

[Ted Ts'o]

On Mon, Mar 26, 2012 at 04:53:56PM +0300, Sami Liedes wrote:
> > So I plan to pull in your patch series and then we can further enhance
> > this with iterator support afterwards.  Sami, if you'd be interested
> > in implementing iterators, that would be great!
> 
> Just to be on the same page, what is the motivation for iterators? Is
> it performance, making the code cleaner or facilitating further
> functionality?

It's a little of all three.  For example, in e2fsck's pass #5, we
currently test each bit, one at a time.  The code paths are quite
complex, but given that we're already using an rbtree for block and
inode bitmaps in e2fsck, using a find_first_set() function could
significantly improve performance.  (We can't really use an iterator
since we need to stop at each block group boundary to check the bg
summary values, but that's where using a find_first_set() with an
"upto" field would do what we want.)

I'll note by the way that it's possible for resize2fs, if we implement
find_first_set() and find_first_zero() for rbtree bitmaps, using
rbtree bitmaps could be even faster, since even with your
optimizations, if there are large blocks of unset bitmaps, we have to
check every single memory location in a bitarray, where as a rbtree
bitmap is much more space compact and would also be faster from a
"find_first_set" standpoint.

There are a few other places where it would make the code cleaner, and
where I might switch to using an rbtree-backed bitmap instead of a
sorted array implementation, but that's a secondary concern.

Cheers,

					- Ted