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
Iterate over groups instead of blocks.
Signed-off-by: Andrey Sidorov <[email protected]>
---
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
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 <[email protected]>
---
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
Generic implementation of find_first_set for bitmaps.
Make ffs/ffz work for cluster bitmaps.
Signed-off-by: Andrey Sidorov <[email protected]>
---
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
Scan original bitmap with successive ffs/ffz and
insert complete extents into target bitmap.
Signed-off-by Andrey Sidorov <[email protected]>
---
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
find_first_set() implementation for bitarray bitmap,
just an inverted copy of find_first_zero().
Signed-off-by: Andrey Sidorov <[email protected]>
---
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