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

login
register
mail settings
Submitter Andrey Sidorov
Date March 19, 2013, 4:06 p.m.
Message ID <1363709164-3210-3-git-send-email-qrxd43@motorola.com>
Download mbox | patch
Permalink /patch/229105/
State Superseded
Headers show

Comments

Andrey Sidorov - March 19, 2013, 4:06 p.m.
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(-)

Patch

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;