[PATCH 0/5] mke2fs/e2fsck optimizations

[PATCH 0/5] mke2fs/e2fsck optimizations

[Andrey Sidorov]

Various optimizations for mke2fs / e2fsck.
First patch makes no big change for x86, but saves a
couple of seconds on embedded systems. Mostly effective
for large non-bigalloc volumes.
The rest of the series is to improve mke2fs time on
bigalloc volumes.

Times for mke2fs of 1TB volume
x86, plain: 7.5s -> 7.0s
x86, bigalloc256: 6.5s -> 1.9s
mips, plain: 9.9s -> 5.7s
mips, bigalloc256: 29.0s -> 1.9s

Testing done:
patched mke2fs, unpatched e2fsck, patched e2fsck,
mount, basic write operations, unmount,
unpatched e2fsck, patched e2fsck.
ffs/ffz were tested with tst_bitmaps commands which
cover all exit paths for rb_tree implementation.
Output of tst_bitmaps is same for ba and rb bitmaps.

Andrey Sidorov (5):
  libext2fs: Optimize ext2fs_allocate_group_table()
  libext2fs: find_first_set() for bitmaps.
  libext2fs: find_first_set() for bitarray bitmap
  libext2fs: ffz/ffs for rb_tree bitmap
  libext2fs: Optimize ext2fs_convert_subcluster_bitmap()

 lib/ext2fs/alloc_tables.c     |   31 +++++---
 lib/ext2fs/bitops.h           |   41 +++++++++++
 lib/ext2fs/blkmap64_ba.c      |   83 +++++++++++++++++++--
 lib/ext2fs/blkmap64_rb.c      |  164 +++++++++++++++++++++++++++++++++++++++--
 lib/ext2fs/bmap64.h           |    4 +-
 lib/ext2fs/ext2fs.h           |    3 +
 lib/ext2fs/gen_bitmap.c       |   23 ++++++
 lib/ext2fs/gen_bitmap64.c     |  118 +++++++++++++++++++++++------
 lib/ext2fs/tst_bitmaps.c      |   66 +++++++++++++++++
 lib/ext2fs/tst_bitmaps_cmd.ct |    6 ++
 10 files changed, 492 insertions(+), 47 deletions(-)

-- 
1.7.10.4

[PATCH 1/5] libext2fs: Optimize ext2fs_allocate_group_table()

[Andrey Sidorov]

Iterate over groups instead of blocks.

Signed-off-by: Andrey Sidorov <qrxd43@motorola.com>
---
 lib/ext2fs/alloc_tables.c |   31 +++++++++++++++++++++----------
 1 file changed, 21 insertions(+), 10 deletions(-)

diff --git a/lib/ext2fs/alloc_tables.c b/lib/ext2fs/alloc_tables.c
index 5e6e556..e51dcee 100644
--- a/lib/ext2fs/alloc_tables.c
+++ b/lib/ext2fs/alloc_tables.c
@@ -205,16 +205,27 @@ errcode_t ext2fs_allocate_group_table(ext2_filsys fs, dgrp_t group,
 						bmap, &new_blk);
 		if (retval)
 			return retval;
-		for (j=0, blk = new_blk;
-		     j < fs->inode_blocks_per_group;
-		     j++, blk++) {
-			ext2fs_mark_block_bitmap2(bmap, blk);
-			if (flexbg_size) {
-				dgrp_t gr = ext2fs_group_of_blk2(fs, blk);
-				ext2fs_bg_free_blocks_count_set(fs, gr, ext2fs_bg_free_blocks_count(fs, gr) - 1);
-				ext2fs_free_blocks_count_add(fs->super, -1);
-				ext2fs_bg_flags_clear(fs, gr,
-						     EXT2_BG_BLOCK_UNINIT);
+
+		ext2fs_mark_block_bitmap_range2(bmap, new_blk, fs->inode_blocks_per_group);
+		if (flexbg_size) {
+			blk64_t last_blk = new_blk + fs->inode_blocks_per_group - 1;
+			dgrp_t gr = ext2fs_group_of_blk2(fs, new_blk);
+			dgrp_t last_gr = ext2fs_group_of_blk2(fs, last_blk);
+
+			ext2fs_free_blocks_count_add(fs->super, -(blk64_t)(fs->inode_blocks_per_group));
+			for (; gr <= last_gr; ++gr) {
+				blk64_t gr_first_blk = ext2fs_group_first_block2(fs, gr);
+				blk64_t gr_last_blk = ext2fs_group_last_block2(fs, gr);
+				__u32 free_blocks = ext2fs_bg_free_blocks_count(fs, gr);
+				if (gr_first_blk < new_blk)
+					gr_first_blk = new_blk;
+				if (gr_last_blk > last_blk)
+					gr_last_blk = last_blk;
+
+				free_blocks -= (__u32)(gr_last_blk - gr_first_blk + 1);
+
+				ext2fs_bg_free_blocks_count_set(fs, gr, free_blocks);
+				ext2fs_bg_flags_clear(fs, gr, EXT2_BG_BLOCK_UNINIT);
 				ext2fs_group_desc_csum_set(fs, gr);
 			}
 		}
-- 
1.7.10.4

[PATCH 2/5] libext2fs: find_first_set() for bitmaps.

[Andrey Sidorov]

Generic implementation of find_first_set for bitmaps.
Make ffs/ffz work for cluster bitmaps.

Signed-off-by: Andrey Sidorov <qrxd43@motorola.com>
---
 lib/ext2fs/bitops.h           |   41 +++++++++++++++++++
 lib/ext2fs/bmap64.h           |    4 +-
 lib/ext2fs/ext2fs.h           |    3 ++
 lib/ext2fs/gen_bitmap.c       |   23 +++++++++++
 lib/ext2fs/gen_bitmap64.c     |   89 +++++++++++++++++++++++++++++++++++++----
 lib/ext2fs/tst_bitmaps.c      |   66 ++++++++++++++++++++++++++++++
 lib/ext2fs/tst_bitmaps_cmd.ct |    6 +++
 7 files changed, 224 insertions(+), 8 deletions(-)

diff --git a/lib/ext2fs/bitops.h b/lib/ext2fs/bitops.h
index 1559539..523d07d 100644
--- a/lib/ext2fs/bitops.h
+++ b/lib/ext2fs/bitops.h
@@ -149,6 +149,14 @@ extern errcode_t ext2fs_find_first_zero_inode_bitmap2(ext2fs_inode_bitmap bitmap
 						      ext2_ino_t start,
 						      ext2_ino_t end,
 						      ext2_ino_t *out);
+extern errcode_t ext2fs_find_first_set_block_bitmap2(ext2fs_block_bitmap bitmap,
+						     blk64_t start,
+						     blk64_t end,
+						     blk64_t *out);
+extern errcode_t ext2fs_find_first_set_inode_bitmap2(ext2fs_inode_bitmap bitmap,
+						     ext2_ino_t start,
+						     ext2_ino_t end,
+						     ext2_ino_t *out);
 extern blk64_t ext2fs_get_block_bitmap_start2(ext2fs_block_bitmap bitmap);
 extern ext2_ino_t ext2fs_get_inode_bitmap_start2(ext2fs_inode_bitmap bitmap);
 extern blk64_t ext2fs_get_block_bitmap_end2(ext2fs_block_bitmap bitmap);
@@ -190,6 +198,9 @@ extern void ext2fs_unmark_block_bitmap_range2(ext2fs_block_bitmap bitmap,
 extern errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
 						     __u64 start, __u64 end,
 						     __u64 *out);
+extern errcode_t ext2fs_find_first_set_generic_bmap(ext2fs_generic_bitmap bitmap,
+						    __u64 start, __u64 end,
+						    __u64 *out);
 
 /*
  * The inline routines themselves...
@@ -596,6 +607,36 @@ _INLINE_ errcode_t ext2fs_find_first_zero_inode_bitmap2(ext2fs_inode_bitmap bitm
 	return rv;
 }
 
+_INLINE_ errcode_t ext2fs_find_first_set_block_bitmap2(ext2fs_block_bitmap bitmap,
+						       blk64_t start,
+						       blk64_t end,
+						       blk64_t *out)
+{
+	__u64 o;
+	errcode_t rv;
+
+	rv = ext2fs_find_first_set_generic_bmap((ext2fs_generic_bitmap) bitmap,
+						start, end, &o);
+	if (!rv)
+		*out = o;
+	return rv;
+}
+
+_INLINE_ errcode_t ext2fs_find_first_set_inode_bitmap2(ext2fs_inode_bitmap bitmap,
+						       ext2_ino_t start,
+						       ext2_ino_t end,
+						       ext2_ino_t *out)
+{
+	__u64 o;
+	errcode_t rv;
+
+	rv = ext2fs_find_first_set_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 c5384c9..40fec22 100644
--- a/lib/ext2fs/bmap64.h
+++ b/lib/ext2fs/bmap64.h
@@ -90,10 +90,12 @@ struct ext2_bitmap_ops {
 	void (*clear_bmap)(ext2fs_generic_bitmap bitmap);
 	void (*print_stats)(ext2fs_generic_bitmap);
 
-	/* Find the first zero bit between start and end, inclusive.
+	/* Find the first zero/set 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);
+	errcode_t (*find_first_set)(ext2fs_generic_bitmap bitmap,
+				    __u64 start, __u64 end, __u64 *out);
 };
 
 extern struct ext2_bitmap_ops ext2fs_blkmap64_bitarray;
diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h
index 7139b4d..cbefdb9 100644
--- a/lib/ext2fs/ext2fs.h
+++ b/lib/ext2fs/ext2fs.h
@@ -1237,6 +1237,9 @@ extern errcode_t ext2fs_set_generic_bitmap_range(ext2fs_generic_bitmap bmap,
 extern errcode_t ext2fs_find_first_zero_generic_bitmap(ext2fs_generic_bitmap bitmap,
 						       __u32 start, __u32 end,
 						       __u32 *out);
+extern errcode_t ext2fs_find_first_set_generic_bitmap(ext2fs_generic_bitmap bitmap,
+						      __u32 start, __u32 end,
+						      __u32 *out);
 
 /* gen_bitmap64.c */
 void ext2fs_free_generic_bmap(ext2fs_generic_bitmap bmap);
diff --git a/lib/ext2fs/gen_bitmap.c b/lib/ext2fs/gen_bitmap.c
index 0bff854..07215cd 100644
--- a/lib/ext2fs/gen_bitmap.c
+++ b/lib/ext2fs/gen_bitmap.c
@@ -527,6 +527,29 @@ errcode_t ext2fs_find_first_zero_generic_bitmap(ext2fs_generic_bitmap bitmap,
 	return ENOENT;
 }
 
+errcode_t ext2fs_find_first_set_generic_bitmap(ext2fs_generic_bitmap bitmap,
+					       __u32 start, __u32 end,
+					       __u32 *out)
+{
+	blk_t b;
+
+	if (start < bitmap->start || end > bitmap->end || start > end) {
+		ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
+		return EINVAL;
+	}
+
+	while (start <= end) {
+		b = ext2fs_test_bit(start - bitmap->start, bitmap->bitmap);
+		if (b) {
+			*out = start;
+			return 0;
+		}
+		start++;
+	}
+
+	return ENOENT;
+}
+
 
 int ext2fs_test_block_bitmap_range(ext2fs_block_bitmap bitmap,
 				   blk_t block, int num)
diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c
index 42a97d4..80502b5 100644
--- a/lib/ext2fs/gen_bitmap64.c
+++ b/lib/ext2fs/gen_bitmap64.c
@@ -800,17 +800,14 @@ errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
 					      __u64 start, __u64 end, __u64 *out)
 {
 	int b;
+	errcode_t retval = ENOENT;
+	__u64 original_start = start;
 
 	if (!bitmap)
 		return EINVAL;
 
-	if (EXT2FS_IS_64_BITMAP(bitmap) && bitmap->bitmap_ops->find_first_zero)
-		return bitmap->bitmap_ops->find_first_zero(bitmap, start,
-							   end, out);
-
 	if (EXT2FS_IS_32_BITMAP(bitmap)) {
 		blk_t blk = 0;
-		errcode_t retval;
 
 		if (((start) & ~0xffffffffULL) ||
 		    ((end) & ~0xffffffffULL)) {
@@ -836,14 +833,92 @@ errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
 		return EINVAL;
 	}
 
+	if (bitmap->bitmap_ops->find_first_zero) {
+		retval = bitmap->bitmap_ops->find_first_zero(bitmap, start,
+							     end, out);
+
+		if (!retval)
+			*out <<= bitmap->cluster_bits;
+		goto out;
+	}
+
+
 	while (start <= end) {
 		b = bitmap->bitmap_ops->test_bmap(bitmap, start);
 		if (!b) {
 			*out = start << bitmap->cluster_bits;
-			return 0;
+			retval = 0;
+			break;
 		}
 		start++;
 	}
 
-	return ENOENT;
+out:
+	if (!retval && *out < original_start)
+		*out = original_start;
+
+	return retval;
+}
+
+errcode_t ext2fs_find_first_set_generic_bmap(ext2fs_generic_bitmap bitmap,
+					     __u64 start, __u64 end, __u64 *out)
+{
+	int b;
+	errcode_t retval = ENOENT;
+	__u64 original_start = start;
+
+	if (!bitmap)
+		return EINVAL;
+
+	if (EXT2FS_IS_32_BITMAP(bitmap)) {
+		blk_t blk = 0;
+
+		if (((start) & ~0xffffffffULL) ||
+		    ((end) & ~0xffffffffULL)) {
+			ext2fs_warn_bitmap2(bitmap, EXT2FS_TEST_ERROR, start);
+			return EINVAL;
+		}
+
+		retval = ext2fs_find_first_set_generic_bitmap(bitmap, start,
+							      end, &blk);
+		if (retval == 0)
+			*out = blk;
+		return retval;
+	}
+
+	if (!EXT2FS_IS_64_BITMAP(bitmap))
+		return EINVAL;
+
+	start >>= bitmap->cluster_bits;
+	end >>= bitmap->cluster_bits;
+
+	if (start < bitmap->start || end > bitmap->end || start > end) {
+		warn_bitmap(bitmap, EXT2FS_TEST_ERROR, start);
+		return EINVAL;
+	}
+
+	if (bitmap->bitmap_ops->find_first_set) {
+		retval = bitmap->bitmap_ops->find_first_set(bitmap, start,
+							    end, out);
+		if (!retval)
+			*out <<= bitmap->cluster_bits;
+		goto out;
+	}
+
+
+	while (start <= end) {
+		b = bitmap->bitmap_ops->test_bmap(bitmap, start);
+		if (b) {
+			*out = start << bitmap->cluster_bits;
+			retval = 0;
+			break;
+		}
+		start++;
+	}
+
+out:
+	if (!retval && *out < original_start)
+		*out = original_start;
+
+	return retval;
 }
diff --git a/lib/ext2fs/tst_bitmaps.c b/lib/ext2fs/tst_bitmaps.c
index 57bfd6c..dffceab 100644
--- a/lib/ext2fs/tst_bitmaps.c
+++ b/lib/ext2fs/tst_bitmaps.c
@@ -436,6 +436,39 @@ void do_ffzb(int argc, char *argv[])
 	printf("First unmarked block is %llu\n", out);
 }
 
+void do_ffsb(int argc, char *argv[])
+{
+	unsigned int start, end;
+	int err;
+	errcode_t retval;
+	blk64_t out;
+
+	if (check_fs_open(argv[0]))
+		return;
+
+	if (argc != 3 && argc != 3) {
+		com_err(argv[0], 0, "Usage: ffsb <start> <end>");
+		return;
+	}
+
+	start = parse_ulong(argv[1], argv[0], "start", &err);
+	if (err)
+		return;
+
+	end = parse_ulong(argv[2], argv[0], "end", &err);
+	if (err)
+		return;
+
+	retval = ext2fs_find_first_set_block_bitmap2(test_fs->block_map,
+						      start, end, &out);
+	if (retval) {
+		printf("ext2fs_find_first_set_block_bitmap2() returned %s\n",
+		       error_message(retval));
+		return;
+	}
+	printf("First marked block is %llu\n", out);
+}
+
 
 void do_zerob(int argc, char *argv[])
 {
@@ -559,6 +592,39 @@ void do_ffzi(int argc, char *argv[])
 	printf("First unmarked inode is %u\n", out);
 }
 
+void do_ffsi(int argc, char *argv[])
+{
+	unsigned int start, end;
+	int err;
+	errcode_t retval;
+	ext2_ino_t out;
+
+	if (check_fs_open(argv[0]))
+		return;
+
+	if (argc != 3 && argc != 3) {
+		com_err(argv[0], 0, "Usage: ffsi <start> <end>");
+		return;
+	}
+
+	start = parse_ulong(argv[1], argv[0], "start", &err);
+	if (err)
+		return;
+
+	end = parse_ulong(argv[2], argv[0], "end", &err);
+	if (err)
+		return;
+
+	retval = ext2fs_find_first_set_inode_bitmap2(test_fs->inode_map,
+						     start, end, &out);
+	if (retval) {
+		printf("ext2fs_find_first_set_inode_bitmap2() returned %s\n",
+		       error_message(retval));
+		return;
+	}
+	printf("First marked inode is %u\n", out);
+}
+
 
 void do_zeroi(int argc, char *argv[])
 {
diff --git a/lib/ext2fs/tst_bitmaps_cmd.ct b/lib/ext2fs/tst_bitmaps_cmd.ct
index 1e1e5d3..13b7fa7 100644
--- a/lib/ext2fs/tst_bitmaps_cmd.ct
+++ b/lib/ext2fs/tst_bitmaps_cmd.ct
@@ -24,6 +24,9 @@ request do_testb, "Test block",
 request do_ffzb, "Find first zero block",
 	find_first_zero_block, ffzb;
 
+request do_ffsb, "Find first set block",
+	find_first_set_block, ffsb;
+
 request do_zerob, "Clear block bitmap",
 	clear_block_bitmap, zerob;
 
@@ -39,6 +42,9 @@ request do_testi, "Test inode",
 request do_ffzi, "Find first zero inode",
 	find_first_zero_inode, ffzi;
 
+request do_ffsi, "Find first set inode",
+	find_first_set_inode, ffsi;
+
 request do_zeroi, "Clear inode bitmap",
 	clear_inode_bitmap, zeroi;
 
-- 
1.7.10.4

[PATCH 3/5] libext2fs: find_first_set() for bitarray bitmap

[Andrey Sidorov]

find_first_set() implementation for bitarray bitmap,
just an inverted copy of find_first_zero().

Signed-off-by: Andrey Sidorov <qrxd43@motorola.com>
---
 lib/ext2fs/blkmap64_ba.c |   83 ++++++++++++++++++++++++++++++++++++++++++----
 1 file changed, 76 insertions(+), 7 deletions(-)

diff --git a/lib/ext2fs/blkmap64_ba.c b/lib/ext2fs/blkmap64_ba.c
index 73180b0..d3bd769 100644
--- a/lib/ext2fs/blkmap64_ba.c
+++ b/lib/ext2fs/blkmap64_ba.c
@@ -332,12 +332,6 @@ static errcode_t ba_find_first_zero(ext2fs_generic_bitmap bitmap,
 	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)) {
@@ -401,6 +395,80 @@ static errcode_t ba_find_first_zero(ext2fs_generic_bitmap bitmap,
 	return ENOENT;
 }
 
+/* Find the first zero bit between start and end, inclusive. */
+static errcode_t ba_find_first_set(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 != 0x00 byte has been found */
+	const unsigned char *pos;
+	unsigned long max_loop_count, i;
+
+	/* 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 != 0) {
+			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)0))
+				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 != 0) {
+				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,
@@ -417,5 +485,6 @@ 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
+	.find_first_zero = ba_find_first_zero,
+	.find_first_set = ba_find_first_set
 };
-- 
1.7.10.4

[PATCH 4/5] libext2fs: ffz/ffs for rb_tree bitmap

[Andrey Sidorov]

find_first_zero / find_first_set Implementation for
rb_tree bitmap. Use of rcursor / rcursor_next makes
successive ffs/ffz/ffs/... calls to be equivalent of
iterating tree via ext2fs_rb_next.

Signed-off-by: Andrey Sidorov <qrxd43@motorola.com>
---
 lib/ext2fs/blkmap64_rb.c |  164 +++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 156 insertions(+), 8 deletions(-)

diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c
index 702187f..76c525e 100644
--- a/lib/ext2fs/blkmap64_rb.c
+++ b/lib/ext2fs/blkmap64_rb.c
@@ -51,6 +51,21 @@ 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);
 
+static inline struct bmap_rb_extent *
+rb_load_next_cursor(struct ext2fs_rb_private *bp)
+{
+	if (!bp->rcursor_next && bp->rcursor) {
+		struct rb_node *node;
+		node = ext2fs_rb_next(&bp->rcursor->node);
+		if (!node)
+			return NULL;
+		bp->rcursor_next = ext2fs_rb_entry(node,
+						   struct bmap_rb_extent,
+						   node);
+	}
+	return bp->rcursor_next;
+}
+
 /* #define DEBUG_RB */
 
 #ifdef DEBUG_RB
@@ -324,14 +339,7 @@ rb_test_bit(struct ext2fs_rb_private *bp, __u64 bit)
 		return 1;
 	}
 
-	next_ext = bp->rcursor_next;
-	if (!next_ext) {
-		next = ext2fs_rb_next(&rcursor->node);
-		if (next)
-			next_ext = ext2fs_rb_entry(next, struct bmap_rb_extent,
-						   node);
-		bp->rcursor_next = next_ext;
-	}
+	next_ext = rb_load_next_cursor(bp);
 	if (next_ext) {
 		if ((bit >= rcursor->start + rcursor->count) &&
 		    (bit < next_ext->start)) {
@@ -855,6 +863,144 @@ static void rb_print_stats(ext2fs_generic_bitmap bitmap)
 static void rb_print_stats(ext2fs_generic_bitmap bitmap){}
 #endif
 
+/* Find the first zero bit between start and end, inclusive. */
+static errcode_t rb_find_first_zero(ext2fs_generic_bitmap bitmap,
+				    __u64 start, __u64 end, __u64 *out)
+{
+	struct ext2fs_rb_private *bp = bitmap->private;
+	struct rb_node *parent = NULL;
+	struct rb_node **n = &bp->root.rb_node;
+	struct bmap_rb_extent *ext = bp->rcursor;
+
+	start -= bitmap->start;
+	end -= bitmap->start;
+
+	if (!ext)
+		goto search_tree;
+
+	if (start >= ext->start) {
+		if (start <= ext->start + ext->count) {
+			goto match;
+		}
+		ext = rb_load_next_cursor(bp);
+		if (ext && start <= ext->start + ext->count) {
+			if (start >= ext->start) {
+				bp->rcursor = ext;
+				bp->rcursor_next = NULL;
+			}
+			goto match;
+		}
+	}
+
+search_tree:
+	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;
+		}
+	}
+	bp->rcursor = ext;
+	bp->rcursor_next = NULL;
+
+match:
+	if (ext) {
+		if (start >= ext->start && start <= ext->start + ext->count) {
+			if (ext->start + ext->count <= end) {
+				*out = bitmap->start + ext->start + ext->count;
+				return 0;
+			}
+			else {
+				return ENOENT;
+			}
+		}
+		else {
+			*out = bitmap->start + start;
+			return 0;
+		}
+	}
+
+	*out = bitmap->start;
+	return 0;
+}
+
+/* Find the first set bit between start and end, inclusive. */
+static errcode_t rb_find_first_set(ext2fs_generic_bitmap bitmap,
+				   __u64 start, __u64 end, __u64 *out)
+{
+	struct ext2fs_rb_private *bp = bitmap->private;
+	struct rb_node *parent = NULL;
+	struct rb_node **n = &bp->root.rb_node;
+	struct bmap_rb_extent *ext = bp->rcursor;
+
+	start -= bitmap->start;
+	end -= bitmap->start;
+
+	if (!ext)
+		goto search_tree;
+
+	if (start >= ext->start) {
+		if (start < ext->start + ext->count) {
+			*out = bitmap->start + start;
+			return 0;
+		}
+
+		ext = rb_load_next_cursor(bp);
+		if (!ext)
+			return ENOENT;
+		if (start < ext->start + ext->count) {
+			bp->rcursor = ext;
+			bp->rcursor_next = NULL;
+			goto match;
+		}
+	}
+
+search_tree:
+	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;
+		}
+	}
+
+	if (ext && start >= ext->start + ext->count) {
+		struct rb_node *next = ext2fs_rb_next(parent);
+		if (next)
+			ext = ext2fs_rb_entry(next, struct bmap_rb_extent,
+					      node);
+	}
+
+	bp->rcursor = ext;
+	bp->rcursor_next = NULL;
+
+match:
+	if (ext) {
+		if (start < ext->start) {
+			if (ext->start <= end) {
+				*out = bitmap->start + ext->start;
+				return 0;
+			}
+		}
+		else if (start < ext->start + ext->count) {
+			*out = bitmap->start + start;
+			return 0;
+		}
+	}
+
+	return ENOENT;
+}
+
 struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = {
 	.type = EXT2FS_BMAP64_RBTREE,
 	.new_bmap = rb_new_bmap,
@@ -871,4 +1017,6 @@ struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = {
 	.get_bmap_range = rb_get_bmap_range,
 	.clear_bmap = rb_clear_bmap,
 	.print_stats = rb_print_stats,
+	.find_first_zero = rb_find_first_zero,
+	.find_first_set = rb_find_first_set,
 };
-- 
1.7.10.4

[PATCH 5/5] libext2fs: Optimize ext2fs_convert_subcluster_bitmap()

[Andrey Sidorov]

Scan original bitmap with successive ffs/ffz and
insert complete extents into target bitmap.

Signed-off-by Andrey Sidorov <qrxd43@motorola.com>
---
 lib/ext2fs/gen_bitmap64.c |   29 +++++++++++++++--------------
 1 file changed, 15 insertions(+), 14 deletions(-)

diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c
index 80502b5..3639f60 100644
--- a/lib/ext2fs/gen_bitmap64.c
+++ b/lib/ext2fs/gen_bitmap64.c
@@ -758,8 +758,7 @@ errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs,
 {
 	ext2fs_block_bitmap	cmap, bmap;
 	errcode_t		retval;
-	blk64_t			i, b_end, c_end;
-	int			n, ratio;
+	blk64_t			b_end, c_end, f_zero, f_set;
 
 	bmap = *bitmap;
 
@@ -771,23 +770,25 @@ errcode_t ext2fs_convert_subcluster_bitmap(ext2_filsys fs,
 	if (retval)
 		return retval;
 
-	i = bmap->start;
+	f_zero = bmap->start;
 	b_end = bmap->end;
 	bmap->end = bmap->real_end;
 	c_end = cmap->end;
 	cmap->end = cmap->real_end;
-	n = 0;
-	ratio = 1 << fs->cluster_ratio_bits;
-	while (i < bmap->real_end) {
-		if (ext2fs_test_block_bitmap2(bmap, i)) {
-			ext2fs_mark_block_bitmap2(cmap, i);
-			i += ratio - n;
-			n = 0;
-			continue;
+
+	while (f_zero < bmap->real_end) {
+		retval = ext2fs_find_first_set_block_bitmap2(bmap, f_zero,
+							     bmap->real_end,
+							     &f_set);
+		if (retval)
+			break;
+		retval = ext2fs_find_first_zero_block_bitmap2(bmap, f_set,
+							      bmap->real_end,
+							      &f_zero);
+		if (retval) {
+			f_zero = bmap->real_end + 1;
 		}
-		i++; n++;
-		if (n >= ratio)
-			n = 0;
+		ext2fs_mark_block_bitmap_range2(cmap, f_set, f_zero - f_set);
 	}
 	bmap->end = b_end;
 	cmap->end = c_end;
-- 
1.7.10.4