Generic implementation of find_first_set for bitmaps.
Make ffs/ffz work for cluster bitmaps.
Signed-off-by: Andrey Sidorov <qrxd43@xxxxxxxxxxxx>
---
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
--
To unsubscribe from this list: send the line "unsubscribe linux-ext4" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
