[PATCH 1/5] libext2fs: add ext2fs_find_first_set_{block,inode}_bitmap2()

[PATCH 1/5] libext2fs: add ext2fs_find_first_set_{block,inode}_bitmap2()

[Theodore Ts'o]

Add functions which try to find the first set block or inode in a
bitmap.  This is useful when trying to allocate a range of blocks
efficiently.

Like the find_first_zero family of functions, provide a generic O(N)
search function which will be used if there is no optimized version
provided by the red-black tree or bitarray functions.

Also, expand the test cases for ext2fs_find_first_zero_*() functions.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 lib/ext2fs/bitops.h           | 41 ++++++++++++++++++
 lib/ext2fs/bmap64.h           |  4 ++
 lib/ext2fs/ext2fs.h           |  3 ++
 lib/ext2fs/gen_bitmap.c       | 22 ++++++++++
 lib/ext2fs/gen_bitmap64.c     | 52 +++++++++++++++++++++++
 lib/ext2fs/tst_bitmaps.c      | 65 ++++++++++++++++++++++++++++
 lib/ext2fs/tst_bitmaps_cmd.ct |  6 +++
 lib/ext2fs/tst_bitmaps_cmds   | 49 ++++++++++++++++++++++
 lib/ext2fs/tst_bitmaps_exp    | 98 +++++++++++++++++++++++++++++++++++++++++++
 9 files changed, 340 insertions(+)

diff --git a/lib/ext2fs/bitops.h b/lib/ext2fs/bitops.h
index 3e8132d..4fb7dc6 100644
--- a/lib/ext2fs/bitops.h
+++ b/lib/ext2fs/bitops.h
@@ -157,6 +157,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);
@@ -198,6 +206,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...
@@ -604,6 +615,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 = (ext2_ino_t) 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 f44d379..9deba46 100644
--- a/lib/ext2fs/bmap64.h
+++ b/lib/ext2fs/bmap64.h
@@ -94,6 +94,10 @@ struct ext2_bitmap_ops {
 	 * 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);
+	/* Find the first set bit between start and end, inclusive.
+	 * May be NULL, in which case a generic function is used. */
+	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 8ff5a7e..e4d6c1a 100644
--- a/lib/ext2fs/ext2fs.h
+++ b/lib/ext2fs/ext2fs.h
@@ -1178,6 +1178,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 */
 
diff --git a/lib/ext2fs/gen_bitmap.c b/lib/ext2fs/gen_bitmap.c
index 0bff854..6cd6fe6 100644
--- a/lib/ext2fs/gen_bitmap.c
+++ b/lib/ext2fs/gen_bitmap.c
@@ -527,6 +527,28 @@ 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 9ba7701..fcf63ad 100644
--- a/lib/ext2fs/gen_bitmap64.c
+++ b/lib/ext2fs/gen_bitmap64.c
@@ -848,3 +848,55 @@ errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
 
 	return ENOENT;
 }
+
+errcode_t ext2fs_find_first_set_generic_bmap(ext2fs_generic_bitmap bitmap,
+					     __u64 start, __u64 end, __u64 *out)
+{
+	int b;
+
+	if (!bitmap)
+		return EINVAL;
+
+	if (EXT2FS_IS_64_BITMAP(bitmap) && bitmap->bitmap_ops->find_first_set)
+		return bitmap->bitmap_ops->find_first_set(bitmap, start,
+							  end, out);
+
+	if (EXT2FS_IS_32_BITMAP(bitmap)) {
+		blk_t blk = 0;
+		errcode_t retval;
+
+		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;
+	}
+
+	while (start <= end) {
+		b = bitmap->bitmap_ops->test_bmap(bitmap, start);
+		if (b) {
+			*out = start << bitmap->cluster_bits;
+			return 0;
+		}
+		start++;
+	}
+
+	return ENOENT;
+}
diff --git a/lib/ext2fs/tst_bitmaps.c b/lib/ext2fs/tst_bitmaps.c
index 57bfd6c..4e02ade 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,38 @@ 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;
 
diff --git a/lib/ext2fs/tst_bitmaps_cmds b/lib/ext2fs/tst_bitmaps_cmds
index 31e2a60..7492592 100644
--- a/lib/ext2fs/tst_bitmaps_cmds
+++ b/lib/ext2fs/tst_bitmaps_cmds
@@ -19,8 +19,17 @@ dump_bb
 ffzb 11 16
 ffzb 12 16
 ffzb 12 20
+ffsb 0 127
+ffsb 1 128
+ffsb 1 127
+ffsb 1 10
+ffsb 1 11
+ffsb 12 12
+ffsb 13 12
+ffsb 12 15
 clearb 13
 ffzb 12 20
+ffsb 13 18
 setb 13
 clearb 12 7
 testb 12 7
@@ -42,8 +51,15 @@ dump_ib
 ffzi 1 6
 ffzi 2 5
 ffzi 2 6
+ffsi 0 31
+ffsi 1 33
+ffsi 1 32
+ffsi 2 32
+ffsi 6 32
 cleari 4
 ffzi 2 6
+ffsi 4 32
+ffsi 5 32
 zeroi
 testi 5
 seti 5
@@ -95,5 +111,38 @@ clearb 2
 clearb 3
 clearb 7
 dump_bb
+ffsb 14 127
+ffsb 15 127
+ffsb 36 127
+ffsb 32 127
+ffsb 52 127
+ffsb 53 127
+ffsb 46 127
+ffsb 45 127
+ffsb 41 127
+ffsb 20 127
+ffsb 1 127
+ffsb 2 127
+ffsb 3 127
+ffsb 4 127
+ffsb 5 127
+ffsb 6 127
+ffsb 7 127
+ffsb 8 127
+ffzb 1 127
+ffzb 2 127
+ffzb 3 127
+ffzb 4 127
+ffzb 5 127
+ffzb 6 127
+ffzb 7 127
+ffzb 8 127
+ffzb 45 127
+ffzb 46 127
+ffzb 47 127
+ffzb 48 127
+ffzb 49 127
+ffzb 50 127
+ffzb 51 127
 quit
 
diff --git a/lib/ext2fs/tst_bitmaps_exp b/lib/ext2fs/tst_bitmaps_exp
index 2d62b66..6b22666 100644
--- a/lib/ext2fs/tst_bitmaps_exp
+++ b/lib/ext2fs/tst_bitmaps_exp
@@ -43,10 +43,28 @@ tst_bitmaps: ffzb 12 16
 ext2fs_find_first_zero_block_bitmap2() returned No such file or directory
 tst_bitmaps: ffzb 12 20
 First unmarked block is 17
+tst_bitmaps: ffsb 0 127
+ext2fs_find_first_set_block_bitmap2() returned Invalid argument
+tst_bitmaps: ffsb 1 128
+ext2fs_find_first_set_block_bitmap2() returned Invalid argument
+tst_bitmaps: ffsb 1 127
+First marked block is 12
+tst_bitmaps: ffsb 1 10
+ext2fs_find_first_set_block_bitmap2() returned No such file or directory
+tst_bitmaps: ffsb 1 11
+ext2fs_find_first_set_block_bitmap2() returned No such file or directory
+tst_bitmaps: ffsb 12 12
+First marked block is 12
+tst_bitmaps: ffsb 13 12
+ext2fs_find_first_set_block_bitmap2() returned Invalid argument
+tst_bitmaps: ffsb 12 15
+First marked block is 12
 tst_bitmaps: clearb 13
 Clearing block 13, was set before
 tst_bitmaps: ffzb 12 20
 First unmarked block is 13
+tst_bitmaps: ffsb 13 18
+First marked block is 14
 tst_bitmaps: setb 13
 Setting block 13, was clear before
 tst_bitmaps: clearb 12 7
@@ -91,10 +109,24 @@ tst_bitmaps: ffzi 2 5
 ext2fs_find_first_zero_inode_bitmap2() returned No such file or directory
 tst_bitmaps: ffzi 2 6
 First unmarked inode is 6
+tst_bitmaps: ffsi 0 31
+ext2fs_find_first_set_inode_bitmap2() returned Invalid argument
+tst_bitmaps: ffsi 1 33
+ext2fs_find_first_set_inode_bitmap2() returned Invalid argument
+tst_bitmaps: ffsi 1 32
+First marked inode is 2
+tst_bitmaps: ffsi 2 32
+First marked inode is 2
+tst_bitmaps: ffsi 6 32
+ext2fs_find_first_set_inode_bitmap2() returned No such file or directory
 tst_bitmaps: cleari 4
 Clearing inode 4, was set before
 tst_bitmaps: ffzi 2 6
 First unmarked inode is 4
+tst_bitmaps: ffsi 4 32
+First marked inode is 5
+tst_bitmaps: ffsi 5 32
+First marked inode is 5
 tst_bitmaps: zeroi
 Clearing inode bitmap.
 tst_bitmaps: testi 5
@@ -207,5 +239,71 @@ Clearing block 7, was set before
 tst_bitmaps: dump_bb
 block bitmap: b92a85e6c4680d000000000000000000
 bits set: 25
+tst_bitmaps: ffsb 14 127
+First marked block is 14
+tst_bitmaps: ffsb 15 127
+First marked block is 17
+tst_bitmaps: ffsb 36 127
+First marked block is 39
+tst_bitmaps: ffsb 32 127
+First marked block is 32
+tst_bitmaps: ffsb 52 127
+First marked block is 52
+tst_bitmaps: ffsb 53 127
+ext2fs_find_first_set_block_bitmap2() returned No such file or directory
+tst_bitmaps: ffsb 46 127
+First marked block is 46
+tst_bitmaps: ffsb 45 127
+First marked block is 46
+tst_bitmaps: ffsb 41 127
+First marked block is 44
+tst_bitmaps: ffsb 20 127
+First marked block is 24
+tst_bitmaps: ffsb 1 127
+First marked block is 1
+tst_bitmaps: ffsb 2 127
+First marked block is 4
+tst_bitmaps: ffsb 3 127
+First marked block is 4
+tst_bitmaps: ffsb 4 127
+First marked block is 4
+tst_bitmaps: ffsb 5 127
+First marked block is 5
+tst_bitmaps: ffsb 6 127
+First marked block is 6
+tst_bitmaps: ffsb 7 127
+First marked block is 8
+tst_bitmaps: ffsb 8 127
+First marked block is 8
+tst_bitmaps: ffzb 1 127
+First unmarked block is 2
+tst_bitmaps: ffzb 2 127
+First unmarked block is 2
+tst_bitmaps: ffzb 3 127
+First unmarked block is 3
+tst_bitmaps: ffzb 4 127
+First unmarked block is 7
+tst_bitmaps: ffzb 5 127
+First unmarked block is 7
+tst_bitmaps: ffzb 6 127
+First unmarked block is 7
+tst_bitmaps: ffzb 7 127
+First unmarked block is 7
+tst_bitmaps: ffzb 8 127
+First unmarked block is 9
+tst_bitmaps: ffzb 45 127
+First unmarked block is 45
+tst_bitmaps: ffzb 46 127
+First unmarked block is 48
+tst_bitmaps: ffzb 47 127
+First unmarked block is 48
+tst_bitmaps: ffzb 48 127
+First unmarked block is 48
+tst_bitmaps: ffzb 49 127
+First unmarked block is 50
+tst_bitmaps: ffzb 50 127
+First unmarked block is 50
+tst_bitmaps: ffzb 51 127
+First unmarked block is 53
 tst_bitmaps: quit
 tst_bitmaps: 
-- 
1.8.5.rc3.362.gdf10213

[PATCH 2/5] libext2fs: clean up generic handling of ext2fs_find_first_{set,zero}_*()

[Theodore Ts'o]

Move the error checking into the the generic bitmap code, and add
support for bitmaps with cluster_bits set.

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

diff --git a/lib/ext2fs/blkmap64_ba.c b/lib/ext2fs/blkmap64_ba.c
index 8eddde9..284236d 100644
--- a/lib/ext2fs/blkmap64_ba.c
+++ b/lib/ext2fs/blkmap64_ba.c
@@ -328,12 +328,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)) {
diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c
index fcf63ad..f4cfd40 100644
--- a/lib/ext2fs/gen_bitmap64.c
+++ b/lib/ext2fs/gen_bitmap64.c
@@ -801,14 +801,12 @@ errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
 					      __u64 start, __u64 end, __u64 *out)
 {
 	int b;
+	__u64 cstart, cend, cout;
+	errcode_t retval;
 
 	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;
@@ -829,23 +827,30 @@ errcode_t ext2fs_find_first_zero_generic_bmap(ext2fs_generic_bitmap bitmap,
 	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;
 	}
 
-	while (start <= end) {
-		b = bitmap->bitmap_ops->test_bmap(bitmap, start);
-		if (!b) {
-			*out = start << bitmap->cluster_bits;
-			return 0;
-		}
-		start++;
+	cstart = start >> bitmap->cluster_bits;
+	cend = end + (1 << bitmap->cluster_bits) - 1;
+	cend >>= bitmap->cluster_bits;
+
+	if (bitmap->bitmap_ops->find_first_zero) {
+		retval = bitmap->bitmap_ops->find_first_zero(bitmap, start,
+							     end, &cout);
+		if (retval)
+			return retval;
+	found:
+		cout <<= bitmap->cluster_bits;
+		*out = (cout >= start) ? cout : start;
+		return 0;
 	}
 
+	for (cout = cstart; cout <= cend; cout++)
+		if (!bitmap->bitmap_ops->test_bmap(bitmap, cout))
+			goto found;
+
 	return ENOENT;
 }
 
@@ -853,14 +858,12 @@ errcode_t ext2fs_find_first_set_generic_bmap(ext2fs_generic_bitmap bitmap,
 					     __u64 start, __u64 end, __u64 *out)
 {
 	int b;
+	__u64 cstart, cend, cout;
+	errcode_t retval;
 
 	if (!bitmap)
 		return EINVAL;
 
-	if (EXT2FS_IS_64_BITMAP(bitmap) && bitmap->bitmap_ops->find_first_set)
-		return bitmap->bitmap_ops->find_first_set(bitmap, start,
-							  end, out);
-
 	if (EXT2FS_IS_32_BITMAP(bitmap)) {
 		blk_t blk = 0;
 		errcode_t retval;
@@ -881,22 +884,29 @@ errcode_t ext2fs_find_first_set_generic_bmap(ext2fs_generic_bitmap bitmap,
 	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;
 	}
 
-	while (start <= end) {
-		b = bitmap->bitmap_ops->test_bmap(bitmap, start);
-		if (b) {
-			*out = start << bitmap->cluster_bits;
-			return 0;
-		}
-		start++;
+	cstart = start >> bitmap->cluster_bits;
+	cend = end + (1 << bitmap->cluster_bits) - 1;
+	cend >>= bitmap->cluster_bits;
+
+	if (bitmap->bitmap_ops->find_first_set) {
+		retval = bitmap->bitmap_ops->find_first_set(bitmap, start,
+							    end, &cout);
+		if (retval)
+			return retval;
+	found:
+		cout <<= bitmap->cluster_bits;
+		*out = (cout >= start) ? cout : start;
+		return 0;
 	}
 
+	for (cout = cstart; cout <= cend; cout++)
+		if (bitmap->bitmap_ops->test_bmap(bitmap, cout))
+			goto found;
+
 	return ENOENT;
 }
-- 
1.8.5.rc3.362.gdf10213

[PATCH 3/5] libext2fs: build tst_bitmaps with rep invariants checking enabled

[Theodore Ts'o]

When building tst_bitmaps, enable #define DEBUG_RB, so we are
always testing the sanity of the in-memory representation of the
bitmap when using red-black trees as part of a "make check" run.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 lib/ext2fs/Makefile.in   |  7 ++++---
 lib/ext2fs/blkmap64_rb.c | 14 +++++++++++---
 2 files changed, 15 insertions(+), 6 deletions(-)

diff --git a/lib/ext2fs/Makefile.in b/lib/ext2fs/Makefile.in
index ef55e08..090b89a 100644
--- a/lib/ext2fs/Makefile.in
+++ b/lib/ext2fs/Makefile.in
@@ -372,10 +372,11 @@ 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) \
-		$(DEPSTATIC_LIBSS) $(DEPSTATIC_LIBCOM_ERR)
+tst_bitmaps: tst_bitmaps.o tst_bitmaps_cmd.o $(srcdir)/blkmap64_rb.c \
+		$(STATIC_LIBEXT2FS) $(DEPSTATIC_LIBSS) $(DEPSTATIC_LIBCOM_ERR)
 	$(E) "	LD $@"
-	$(Q) $(CC) -o $@ tst_bitmaps.o tst_bitmaps_cmd.o $(ALL_CFLAGS) \
+	$(Q) $(CC) -o $@ tst_bitmaps.o tst_bitmaps_cmd.o \
+		-DDEBUG_RB $(srcdir)/blkmap64_rb.c $(ALL_CFLAGS) \
 		$(STATIC_LIBEXT2FS) $(STATIC_LIBSS) $(STATIC_LIBCOM_ERR) \
 		$(SYSLIBS)
 
diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c
index a189590..0e0a217 100644
--- a/lib/ext2fs/blkmap64_rb.c
+++ b/lib/ext2fs/blkmap64_rb.c
@@ -135,7 +135,7 @@ err_out:
 }
 #else
 #define check_tree(root, msg) do {} while (0)
-#define print_tree(root, msg) do {} while (0)
+#define print_tree(root) do {} while (0)
 #endif
 
 static void rb_get_new_extent(struct bmap_rb_extent **ext, __u64 start,
@@ -569,11 +569,14 @@ static int rb_remove_extent(__u64 start, __u64 count,
 static int rb_mark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
 {
 	struct ext2fs_rb_private *bp;
+	int retval;
 
 	bp = (struct ext2fs_rb_private *) bitmap->private;
 	arg -= bitmap->start;
 
-	return rb_insert_extent(arg, 1, bp);
+	retval = rb_insert_extent(arg, 1, bp);
+	check_tree(&bp->root, __func__);
+	return retval;
 }
 
 static int rb_unmark_bmap(ext2fs_generic_bitmap bitmap, __u64 arg)
@@ -610,6 +613,7 @@ static void rb_mark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
 	arg -= bitmap->start;
 
 	rb_insert_extent(arg, num, bp);
+	check_tree(&bp->root, __func__);
 }
 
 static void rb_unmark_bmap_extent(ext2fs_generic_bitmap bitmap, __u64 arg,
@@ -714,11 +718,14 @@ static errcode_t rb_set_bmap_range(ext2fs_generic_bitmap bitmap,
 
 		rb_insert_extent(start + first_set - bitmap->start,
 				 i - first_set, bp);
+		check_tree(&bp->root, __func__);
 		first_set = -1;
 	}
-	if (first_set != -1)
+	if (first_set != -1) {
 		rb_insert_extent(start + first_set - bitmap->start,
 				 num - first_set, bp);
+		check_tree(&bp->root, __func__);
+	}
 
 	return 0;
 }
@@ -799,6 +806,7 @@ static void rb_clear_bmap(ext2fs_generic_bitmap bitmap)
 	bp->rcursor = NULL;
 	bp->rcursor_next = NULL;
 	bp->wcursor = NULL;
+	check_tree(&bp->root, __func__);
 }
 
 #ifdef BMAP_STATS
-- 
1.8.5.rc3.362.gdf10213

[PATCH 4/5] libext: optimize find_first_set() for bitarray-based bitmaps

[Theodore Ts'o]

Basically just a trivial adaption of the find_first_zero() function
for bitarray-based bitmaps.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
---
 lib/ext2fs/blkmap64_ba.c | 77 +++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 76 insertions(+), 1 deletion(-)

diff --git a/lib/ext2fs/blkmap64_ba.c b/lib/ext2fs/blkmap64_ba.c
index 284236d..894293a 100644
--- a/lib/ext2fs/blkmap64_ba.c
+++ b/lib/ext2fs/blkmap64_ba.c
@@ -391,6 +391,80 @@ static errcode_t ba_find_first_zero(ext2fs_generic_bitmap bitmap,
 	return ENOENT;
 }
 
+/* Find the first one 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 != 0xff 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) != 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,
@@ -407,5 +481,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.8.5.rc3.362.gdf10213

[PATCH 5/5] libext2fs: optimize find_first_{zero,set}() for red-black tree based bitmaps

[Theodore Ts'o]

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

diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c
index 0e0a217..5be6a4c 100644
--- a/lib/ext2fs/blkmap64_rb.c
+++ b/lib/ext2fs/blkmap64_rb.c
@@ -809,6 +809,118 @@ static void rb_clear_bmap(ext2fs_generic_bitmap bitmap)
 	check_tree(&bp->root, __func__);
 }
 
+static errcode_t rb_find_first_zero(ext2fs_generic_bitmap bitmap,
+				   __u64 start, __u64 end, __u64 *out)
+{
+	struct rb_node *parent = NULL, **n;
+	struct rb_node *node, *next;
+	struct ext2fs_rb_private *bp;
+	struct bmap_rb_extent *ext;
+	int retval = 1;
+	__u64 b;
+
+	bp = (struct ext2fs_rb_private *) bitmap->private;
+	n = &bp->root.rb_node;
+	start -= bitmap->start;
+	end -= bitmap->start;
+
+	if (start > end)
+		return EINVAL;
+
+	if (EXT2FS_RB_EMPTY_ROOT(&bp->root))
+		return ENOENT;
+
+	while (*n) {
+		parent = *n;
+		ext = node_to_extent(parent);
+		if (start < ext->start) {
+			n = &(*n)->rb_left;
+		} else if (start >= (ext->start + ext->count)) {
+			n = &(*n)->rb_right;
+		} else if (ext->start + ext->count <= end) {
+			*out = ext->start + ext->count + bitmap->start;
+			return 0;
+		} else
+			return ENOENT;
+	}
+
+	node = parent;
+	ext = node_to_extent(node);
+	while (ext->start > start) {
+		node = ext2fs_rb_prev(node);
+		if (node == NULL) {
+			*out = start + bitmap->start;
+			return 0;
+		}
+		ext = node_to_extent(node);
+	}
+	while (1) {
+		__u64 ext_end = ext->start + ext->count;
+		if (ext_end >= start && ext_end <= end) {
+			*out = b + bitmap->start;
+			return 0;
+		}
+		if (ext_end > end)
+			return ENOENT;
+		node = ext2fs_rb_next(node);
+		if (node == NULL) {
+			*out = start + bitmap->start;
+			return 0;
+		}
+		ext = node_to_extent(node);
+	}
+	return ENOENT;
+}
+
+static errcode_t rb_find_first_set(ext2fs_generic_bitmap bitmap,
+				   __u64 start, __u64 end, __u64 *out)
+{
+	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;
+	end -= bitmap->start;
+
+	if (start > end)
+		return EINVAL;
+
+	if (EXT2FS_RB_EMPTY_ROOT(&bp->root))
+		return ENOENT;
+
+	while (*n) {
+		parent = *n;
+		ext = node_to_extent(parent);
+		if (start < ext->start) {
+			n = &(*n)->rb_left;
+		} else if (start >= (ext->start + ext->count)) {
+			n = &(*n)->rb_right;
+		} else {
+			/* The start bit is set */
+			*out = start + bitmap->start;
+			return 0;
+		}
+	}
+
+	node = parent;
+	ext = node_to_extent(node);
+	if (ext->start < start) {
+		node = ext2fs_rb_next(node);
+		if (node == NULL)
+			return ENOENT;
+		ext = node_to_extent(node);
+	}
+	if (ext->start <= end) {
+		*out = ext->start + bitmap->start;
+		return 0;
+	}
+	return ENOENT;
+}
+
 #ifdef BMAP_STATS
 static void rb_print_stats(ext2fs_generic_bitmap bitmap)
 {
@@ -890,4 +1002,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.8.5.rc3.362.gdf10213