[RFC 00/13] libext2fs: Add merge/clone abstraction changes

[RFC 00/13] libext2fs: Add merge/clone abstraction changes

[Ritesh Harjani]

Hello,

Though this series is not yet ready to be merged (due to few more todos), but I atleast
wanted to get this base patch series out with some action items listed of what I
am planning to do next and whether it is inline with the expectation as I last
discussed here [1].
So looking at older review comments, it looks like we wanted a base patch series
with libext2fs clone/merge apis so that anyone wanting to do parallel I/O could utilize
libext2fs abstraction changes API for clone and merge of it's ext2_filsys structure.

Earlier the I/O manager abstraction changes for doing parallel I/O were already merged.
This patch series mainly adds the libext2fs abstraction changes for cloning and merging
libext2fs data structures.

So next few todos that I am planning are (some of which are sitting in my tree but still needs more work)
1. Add dblist unit test - there is nothing that exist today for dblist unit
   tests.
2. Fix the todos listed in libext2fs merge/clone patch since some of those are not required
   while cloning ext2_filsys structure and it's members.
3. Start bringing in the pfsck base changes (work done by others) to this series along with writing
   unit tests for those.
4. Work on making older pfsck patches, work with latest features that have gone in like fastcommit,
   casefolding etc.
5. Make sure that the later bug fixes (and some which I have identified), should be included in the
   original feature patches (rather than as a separate bug fix patches).
6. Make sure to add more tests for pfsck with fuzzed images with e2fuzz.
7. Later we could work on other passes and/or other tools like debugfs etc, to make it parallel.

Please let me know if this is going in the right direction. Also if you could take a look
at this series and kindly let me know whether patches looks ok to you.

I guess this might have taken longer than I earlier estimated. But I will definitely try to
correct that with future revisions.

[1]: https://lore.kernel.org/linux-ext4/20220321164009.dwqmdo7axyyixn2t@riteshh-domain/

-ritesh

NOTE (Background)
===================
As I understand, earlier to make fsck parallel, the patches added io_manager
relationship directly within e2fsck_t struct. Which is a layering violation
which will expose internal library functions and structures to it's clients.
Also if any other client (e.g. debugfs etc.) who would like to add threading
support will also have to do the same work in their structures.

So instead we now have added a parent structure of same type within ext2_filsys
struct for multi-threading support. And libext2fs is responsible for providing
the meaningful apis to it's client for clone/merge of it's data structures/bitmaps
for parallel threading support based on the flags passed by it's clients.

                                +------------------+
                                | DS relationships |
                    %===============================================%
                    % typedef struct struct_io_manager *io_manager; %
                    % typedef struct struct_io_channel *io_channel; %
                    % typedef struct struct_io_stats *io_stats;     %
                    %===============================================%

                                +-----------------+
                                | e2fsck/e2fsck.h |
                                +-------------------------------+
                                | (ctx) struct e2fsck_t  {      |
                         +------|------ ext2_filsys fs          |
                         |      |       io_manager io_manager --|-------------------+  --> layering violation
                         |      |       io_channel	journal_io  |                   |
                         |      | }                             |                   |
                         |      +-------------------------------+                   |
                         +---+                                                      |
        <<<< Libext2fs >>>>  |                                                      |
                    +----------------------+                                        |
                    | lib/ext2fs/ext2fs.h  |                                        |
                    +-----------------------------+                                 |
                    | (fs) struct ext2_filsys {   |                                 |
                    | (struct struct_ext2_filsys) |                                 |
                    |         io_channel io       |                                 |
                    |              |              |                                 |
                    +--------------v--------------+                                 |
                                   |                                                |
         <<<< IO LAYER >>>>>>>     |                                                |
                +----------------------+                                            |
                | lib/ext2fs/ext2_io.h |                                            |
                +-----------------------------------------------+----+              |
                | (io) typedef struct struct_io_channel *io_channel{ |              |
          +---- |                  io_manager manager                |              |
          |     |                  void *private_data                |              |
          |     +----------------------------------------------------+              |
          |                          |                                              |
          |                          | (io_channel-> io_manager)                    v
          |  +--------------------------------------------------------------------------------------------------+
          |  | lib/ext2fs/windows_io.c <global> 1041 io_manager windows_io_manager  = &struct_windows_manager;  |
          |  | lib/ext2fs/sparse_io.c <global> 554 io_manager sparsefd_io_manager   = &struct_sparsefd_manager; |
          |  | lib/ext2fs/sparse_io.c <global> 553 io_manager sparse_io_manager     = &struct_sparse_manager;   |
          |  | lib/ext2fs/unix_io.c <global> 1437 io_manager unixfd_io_manager      = &struct_unixfd_manager;   |
          |  | lib/ext2fs/inode_io.c <global> 79 io_manager inode_io_manager        = &struct_inode_manager;    |
          |  | lib/ext2fs/unix_io.c <global> 1415 io_manager unix_io_manager        = &struct_unix_manager;     |
          |  | lib/ext2fs/undo_io.c <global> 1125 io_manager undo_io_manager        = &struct_undo_manager;     |
          |  | lib/ext2fs/test_io.c <global> 555 io_manager test_io_manager         = &struct_test_manager;     |
          |  | lib/ext2fs/dosio.c <global> 75 io_manager dos_io_manager             = &struct_dos_manager;      |
          |  +--------------------------------------------------------------------------------------------------+
          |
          | (io_channel->private_data)
          |    +-------------------------------------------------------------+
          |    | lib/ext2fs/nt_io.c:206:20:typedef struct _NT_PRIVATE_DATA { |
          |    | lib/ext2fs/windows_io.c:95:16:struct windows_private_data { |
          |    | lib/ext2fs/inode_io.c:34:14:struct inode_private_data {     |        +--------------------------------------+
           --->| lib/ext2fs/unix_io.c:103:13:struct unix_private_data {      |<-------| struct unix_private_data {           |
               | lib/ext2fs/undo_io.c:126:13:struct undo_private_data {      |        |     struct struct_io_stats io_stats; |
               | lib/ext2fs/test_io.c:45:13:struct test_private_data {       |        +--------------------------------------+
               +------------------------^------------------------------------+
                                        |
                    +-------------------|--------------------+
                    | struct undo_private_data {             |
                    |         /* the undo file io channel */ |
                    |         io_channel undo_file;          |
                    |         /* The backing io channel */   |
                    |         io_channel real;               |
                    |         char *tdb_file;                |
                    | }                                      |
                    +----------------------------------------+

	Fig: Depicting that with this patch series, there is no need to add "io_manager" into ext2_filsys which was done by original pfsck implementation.


Li Xi (1):
  dblist: add dblist merge logic

Ritesh Harjani (8):
  gen_bitmaps: Fix ext2fs_compare_generic_bmap/bitmap logic
  badblocks: Remove unused badblocks_flags
  blkmap64_ba: Add common helper for bits size calculation
  blkmap64_ba: Implement initial implementation of merge bitmaps
  tst_bitmaps_standalone: Add copy and merge bitmaps test
  tst_bitmaps_pthread: Add merge bitmaps test using pthreads
  tst_badblocks: Add unit test to verify badblocks list merge api
  tst_libext2fs_pthread: Add libext2fs merge/clone unit tests

Saranya Muruganandam (1):
  libext2fs: dupfs: Add fs clone & merge api

Wang Shilong (3):
  ext2fs/bitmaps: Add merge bitmaps library abstraction changes
  libext2fs: blkmap64_rb: Add rbtree bmap merge logic changes
  badblocks: Add badblocks merge logic

 lib/ext2fs/Makefile.in              |  53 ++++-
 lib/ext2fs/badblocks.c              |  81 ++++++-
 lib/ext2fs/bitmaps.c                |   9 +
 lib/ext2fs/blkmap64_ba.c            |  73 ++++++-
 lib/ext2fs/blkmap64_rb.c            |  65 ++++++
 lib/ext2fs/bmap64.h                 |   5 +
 lib/ext2fs/dblist.c                 |  36 ++++
 lib/ext2fs/dupfs.c                  | 149 +++++++++++++
 lib/ext2fs/ext2fs.h                 |  35 +++
 lib/ext2fs/ext2fsP.h                |   1 -
 lib/ext2fs/gen_bitmap.c             |   9 +-
 lib/ext2fs/gen_bitmap64.c           |  39 +++-
 lib/ext2fs/tst_badblocks.c          |  61 +++++-
 lib/ext2fs/tst_bitmaps_pthread.c    | 247 +++++++++++++++++++++
 lib/ext2fs/tst_bitmaps_standalone.c | 173 +++++++++++++++
 lib/ext2fs/tst_libext2fs_pthread.c  | 322 ++++++++++++++++++++++++++++
 16 files changed, 1330 insertions(+), 28 deletions(-)
 create mode 100644 lib/ext2fs/tst_bitmaps_pthread.c
 create mode 100644 lib/ext2fs/tst_bitmaps_standalone.c
 create mode 100644 lib/ext2fs/tst_libext2fs_pthread.c

--
2.35.3

[RFC 01/13] gen_bitmaps: Fix ext2fs_compare_generic_bmap/bitmap logic

[Ritesh Harjani]

Currently this function was not correctly comparing against the right
length of the bitmap. Also when we compare bitarray v/s rbtree bitmap
the value returned by ext2fs_test_generic_bmap() could be different in
these two implementations. Hence only check against boolean value.

Signed-off-by: Ritesh Harjani <ritesh.list@gmail.com>
---
 lib/ext2fs/gen_bitmap.c   |  9 ++++++---
 lib/ext2fs/gen_bitmap64.c | 10 +++++++---
 2 files changed, 13 insertions(+), 6 deletions(-)

diff --git a/lib/ext2fs/gen_bitmap.c b/lib/ext2fs/gen_bitmap.c
index 1536d4b3..f7764fca 100644
--- a/lib/ext2fs/gen_bitmap.c
+++ b/lib/ext2fs/gen_bitmap.c
@@ -385,10 +385,13 @@ errcode_t ext2fs_compare_generic_bitmap(errcode_t magic, errcode_t neq,
 		    (size_t) (bm1->end - bm1->start)/8)))
 		return neq;
 
-	for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++)
-		if (ext2fs_fast_test_block_bitmap(gen_bm1, i) !=
-		    ext2fs_fast_test_block_bitmap(gen_bm2, i))
+	for (i = bm1->start; i <= bm1->end; i++) {
+		int ret1, ret2;
+		ret1 = !!ext2fs_fast_test_block_bitmap(gen_bm1, i);
+		ret2 = !!ext2fs_fast_test_block_bitmap(gen_bm2, i);
+		if (ret1 != ret2)
 			return neq;
+	}
 
 	return 0;
 }
diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c
index d9809084..90c700ca 100644
--- a/lib/ext2fs/gen_bitmap64.c
+++ b/lib/ext2fs/gen_bitmap64.c
@@ -629,10 +629,14 @@ errcode_t ext2fs_compare_generic_bmap(errcode_t neq,
 	    (bm1->end != bm2->end))
 		return neq;
 
-	for (i = bm1->end - ((bm1->end - bm1->start) % 8); i <= bm1->end; i++)
-		if (ext2fs_test_generic_bmap(gen_bm1, i) !=
-		    ext2fs_test_generic_bmap(gen_bm2, i))
+	for (i = bm1->start; i < bm1->end; i++) {
+		int ret1, ret2;
+		ret1 = !!ext2fs_test_generic_bmap(gen_bm1, i);
+		ret2 = !!ext2fs_test_generic_bmap(gen_bm2, i);
+		if (ret1 != ret2) {
 			return neq;
+		}
+	}
 
 	return 0;
 }
-- 
2.35.3

[RFC 02/13] badblocks: Remove unused badblocks_flags

[Ritesh Harjani]

badblocks_flags is not used anywhere. So just remove it.

Signed-off-by: Ritesh Harjani <ritesh.list@gmail.com>
---
 lib/ext2fs/badblocks.c | 6 +-----
 lib/ext2fs/ext2fsP.h   | 1 -
 2 files changed, 1 insertion(+), 6 deletions(-)

diff --git a/lib/ext2fs/badblocks.c b/lib/ext2fs/badblocks.c
index 0f23983b..0570b131 100644
--- a/lib/ext2fs/badblocks.c
+++ b/lib/ext2fs/badblocks.c
@@ -81,11 +81,7 @@ errcode_t ext2fs_u32_copy(ext2_u32_list src, ext2_u32_list *dest)
 {
 	errcode_t	retval;
 
-	retval = make_u32_list(src->size, src->num, src->list, dest);
-	if (retval)
-		return retval;
-	(*dest)->badblocks_flags = src->badblocks_flags;
-	return 0;
+	return make_u32_list(src->size, src->num, src->list, dest);
 }
 
 errcode_t ext2fs_badblocks_copy(ext2_badblocks_list src,
diff --git a/lib/ext2fs/ext2fsP.h b/lib/ext2fs/ext2fsP.h
index a20a0502..d2045af8 100644
--- a/lib/ext2fs/ext2fsP.h
+++ b/lib/ext2fs/ext2fsP.h
@@ -34,7 +34,6 @@ struct ext2_struct_u32_list {
 	int	num;
 	int	size;
 	__u32	*list;
-	int	badblocks_flags;
 };
 
 struct ext2_struct_u32_iterate {
-- 
2.35.3

[RFC 03/13] blkmap64_ba: Add common helper for bits size calculation

[Ritesh Harjani]

Just a quick common helper for bits size calculation.

Signed-off-by: Ritesh Harjani <ritesh.list@gmail.com>
---
 lib/ext2fs/blkmap64_ba.c | 20 +++++++++++++-------
 1 file changed, 13 insertions(+), 7 deletions(-)

diff --git a/lib/ext2fs/blkmap64_ba.c b/lib/ext2fs/blkmap64_ba.c
index 5d8f1548..4e7007f0 100644
--- a/lib/ext2fs/blkmap64_ba.c
+++ b/lib/ext2fs/blkmap64_ba.c
@@ -40,6 +40,13 @@ struct ext2fs_ba_private_struct {
 
 typedef struct ext2fs_ba_private_struct *ext2fs_ba_private;
 
+#define ba_bits_size(start, end) ((((end) - (start)) / 8 + 1))
+
+static size_t ba_bitmap_size(ext2fs_generic_bitmap_64 bitmap)
+{
+	return (size_t) ba_bits_size(bitmap->start, bitmap->real_end);
+}
+
 static errcode_t ba_alloc_private_data (ext2fs_generic_bitmap_64 bitmap)
 {
 	ext2fs_ba_private bp;
@@ -56,7 +63,7 @@ static errcode_t ba_alloc_private_data (ext2fs_generic_bitmap_64 bitmap)
 	if (retval)
 		return retval;
 
-	size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1);
+	size = ba_bitmap_size(bitmap);
 
 	retval = ext2fs_get_mem(size, &bp->bitarray);
 	if (retval) {
@@ -80,7 +87,7 @@ static errcode_t ba_new_bmap(ext2_filsys fs EXT2FS_ATTR((unused)),
 		return retval;
 
 	bp = (ext2fs_ba_private) bitmap->private;
-	size = (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1);
+	size = ba_bitmap_size(bitmap);
 	memset(bp->bitarray, 0, size);
 
 	return 0;
@@ -115,7 +122,7 @@ static errcode_t ba_copy_bmap(ext2fs_generic_bitmap_64 src,
 
 	dest_bp = (ext2fs_ba_private) dest->private;
 
-	size = (size_t) (((src->real_end - src->start) / 8) + 1);
+	size = ba_bitmap_size(src);
 	memcpy (dest_bp->bitarray, src_bp->bitarray, size);
 
 	return 0;
@@ -145,8 +152,8 @@ static errcode_t ba_resize_bmap(ext2fs_generic_bitmap_64 bmap,
 		return 0;
 	}
 
-	size = ((bmap->real_end - bmap->start) / 8) + 1;
-	new_size = ((new_real_end - bmap->start) / 8) + 1;
+	size = ba_bitmap_size(bmap);
+	new_size = ba_bits_size(new_real_end, bmap->start);
 
 	if (size != new_size) {
 		retval = ext2fs_resize_mem(size, new_size, &bp->bitarray);
@@ -306,8 +313,7 @@ static void ba_clear_bmap(ext2fs_generic_bitmap_64 bitmap)
 {
 	ext2fs_ba_private bp = (ext2fs_ba_private) bitmap->private;
 
-	memset(bp->bitarray, 0,
-	       (size_t) (((bitmap->real_end - bitmap->start) / 8) + 1));
+	memset(bp->bitarray, 0, ba_bitmap_size(bitmap));
 }
 
 #ifdef ENABLE_BMAP_STATS
-- 
2.35.3

[RFC 04/13] ext2fs/bitmaps: Add merge bitmaps library abstraction changes

[Ritesh Harjani]

From: Wang Shilong <wshilong@ddn.com>

Add merge bitmaps library abstraction changes.

Signed-off-by: Wang Shilong <wshilong@ddn.com>
Signed-off-by: Ritesh Harjani <ritesh.list@gmail.com>
---
 lib/ext2fs/bitmaps.c      |  9 +++++++++
 lib/ext2fs/bmap64.h       |  5 +++++
 lib/ext2fs/ext2fs.h       |  8 ++++++++
 lib/ext2fs/gen_bitmap64.c | 29 +++++++++++++++++++++++++++++
 4 files changed, 51 insertions(+)

diff --git a/lib/ext2fs/bitmaps.c b/lib/ext2fs/bitmaps.c
index 834a3962..23072a11 100644
--- a/lib/ext2fs/bitmaps.c
+++ b/lib/ext2fs/bitmaps.c
@@ -45,6 +45,15 @@ errcode_t ext2fs_copy_bitmap(ext2fs_generic_bitmap src,
 {
 	return (ext2fs_copy_generic_bmap(src, dest));
 }
+
+errcode_t ext2fs_merge_bitmap(ext2fs_generic_bitmap src,
+							  ext2fs_generic_bitmap dst,
+							  ext2fs_generic_bitmap dup,
+							  ext2fs_generic_bitmap dup_allowed)
+{
+	return ext2fs_merge_generic_bmap(src, dst, dup, dup_allowed);
+}
+
 void ext2fs_set_bitmap_padding(ext2fs_generic_bitmap map)
 {
 	ext2fs_set_generic_bmap_padding(map);
diff --git a/lib/ext2fs/bmap64.h b/lib/ext2fs/bmap64.h
index de334548..4c254892 100644
--- a/lib/ext2fs/bmap64.h
+++ b/lib/ext2fs/bmap64.h
@@ -100,6 +100,11 @@ struct ext2_bitmap_ops {
 	 * May be NULL, in which case a generic function is used. */
 	errcode_t (*find_first_set)(ext2fs_generic_bitmap_64 bitmap,
 				    __u64 start, __u64 end, __u64 *out);
+
+	errcode_t (*merge_bmap)(ext2fs_generic_bitmap_64 src,
+							ext2fs_generic_bitmap_64 dest,
+							ext2fs_generic_bitmap_64 dup,
+							ext2fs_generic_bitmap_64 dup_allowed);
 };
 
 extern struct ext2_bitmap_ops ext2fs_blkmap64_bitarray;
diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h
index 68f9c1fe..c18849d7 100644
--- a/lib/ext2fs/ext2fs.h
+++ b/lib/ext2fs/ext2fs.h
@@ -867,6 +867,10 @@ extern void ext2fs_free_block_bitmap(ext2fs_block_bitmap bitmap);
 extern void ext2fs_free_inode_bitmap(ext2fs_inode_bitmap bitmap);
 extern errcode_t ext2fs_copy_bitmap(ext2fs_generic_bitmap src,
 				    ext2fs_generic_bitmap *dest);
+extern errcode_t ext2fs_merge_bitmap(ext2fs_generic_bitmap src,
+							  ext2fs_generic_bitmap dst,
+							  ext2fs_generic_bitmap dup,
+							  ext2fs_generic_bitmap dup_allowed);
 extern errcode_t ext2fs_allocate_block_bitmap(ext2_filsys fs,
 					      const char *descr,
 					      ext2fs_block_bitmap *ret);
@@ -1455,6 +1459,10 @@ errcode_t ext2fs_alloc_generic_bmap(ext2_filsys fs, errcode_t magic,
 				    ext2fs_generic_bitmap *ret);
 errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap src,
 				   ext2fs_generic_bitmap *dest);
+extern errcode_t ext2fs_merge_generic_bmap(ext2fs_generic_bitmap gen_src,
+							  ext2fs_generic_bitmap gen_dst,
+							  ext2fs_generic_bitmap gen_dup,
+							  ext2fs_generic_bitmap gen_dup_allowed);
 void ext2fs_clear_generic_bmap(ext2fs_generic_bitmap bitmap);
 errcode_t ext2fs_fudge_generic_bmap_end(ext2fs_generic_bitmap bitmap,
 					errcode_t neq,
diff --git a/lib/ext2fs/gen_bitmap64.c b/lib/ext2fs/gen_bitmap64.c
index 90c700ca..eea100b0 100644
--- a/lib/ext2fs/gen_bitmap64.c
+++ b/lib/ext2fs/gen_bitmap64.c
@@ -346,6 +346,35 @@ errcode_t ext2fs_copy_generic_bmap(ext2fs_generic_bitmap gen_src,
 	return 0;
 }
 
+errcode_t ext2fs_merge_generic_bmap(ext2fs_generic_bitmap gen_src,
+							  ext2fs_generic_bitmap gen_dst,
+							  ext2fs_generic_bitmap gen_dup,
+							  ext2fs_generic_bitmap gen_dup_allowed)
+{
+	ext2fs_generic_bitmap_64 src = (ext2fs_generic_bitmap_64) gen_src;
+	ext2fs_generic_bitmap_64 dst = (ext2fs_generic_bitmap_64) gen_dst;
+	ext2fs_generic_bitmap_64 dup = (ext2fs_generic_bitmap_64) gen_dup;
+	ext2fs_generic_bitmap_64 dup_allowed = (ext2fs_generic_bitmap_64) gen_dup_allowed;
+
+	if (!src || !dst)
+		return EINVAL;
+
+	if (!EXT2FS_IS_64_BITMAP(src) || !EXT2FS_IS_64_BITMAP(dst) ||
+	   (dup && !EXT2FS_IS_64_BITMAP(dup)) ||
+	   (dup_allowed && !EXT2FS_IS_64_BITMAP(dup_allowed)))
+		return EINVAL;
+
+	if (src->bitmap_ops != dst->bitmap_ops ||
+		(dup && dup->bitmap_ops != src->bitmap_ops) ||
+		(dup_allowed && dup_allowed->bitmap_ops != src->bitmap_ops))
+		return EINVAL;
+
+	if (!src->bitmap_ops->merge_bmap)
+		return EOPNOTSUPP;
+
+	return src->bitmap_ops->merge_bmap(src, dst, dup, dup_allowed);
+}
+
 errcode_t ext2fs_resize_generic_bmap(ext2fs_generic_bitmap gen_bmap,
 				     __u64 new_end,
 				     __u64 new_real_end)
-- 
2.35.3

[RFC 05/13] libext2fs: blkmap64_rb: Add rbtree bmap merge logic changes

[Ritesh Harjani]

From: Wang Shilong <wshilong@ddn.com>

Add rbtree bmap merge logic changes.

Signed-off-by: Ritesh Harjani <ritesh.list@gmail.com>
Signed-off-by: Wang Shilong <wshilong@ddn.com>
---
 lib/ext2fs/blkmap64_rb.c | 65 ++++++++++++++++++++++++++++++++++++++++
 1 file changed, 65 insertions(+)

diff --git a/lib/ext2fs/blkmap64_rb.c b/lib/ext2fs/blkmap64_rb.c
index 0df58dc7..d7c88aef 100644
--- a/lib/ext2fs/blkmap64_rb.c
+++ b/lib/ext2fs/blkmap64_rb.c
@@ -977,11 +977,76 @@ static void rb_print_stats(ext2fs_generic_bitmap_64 bitmap EXT2FS_ATTR((unused))
 }
 #endif
 
+static errcode_t rb_merge_bmap(ext2fs_generic_bitmap_64 src,
+			       ext2fs_generic_bitmap_64 dest,
+			       ext2fs_generic_bitmap_64 dup,
+			       ext2fs_generic_bitmap_64 dup_allowed)
+{
+	struct ext2fs_rb_private *src_bp, *dest_bp, *dup_bp = NULL;
+	struct bmap_rb_extent *src_ext;
+	struct rb_node *src_node;
+	errcode_t retval = 0;
+	int dup_found = 0;
+	__u64 i;
+
+	src_bp = (struct ext2fs_rb_private *) src->private;
+	dest_bp = (struct ext2fs_rb_private *) dest->private;
+	if (dup)
+		dup_bp = (struct ext2fs_rb_private *)dup->private;
+	src_bp->rcursor = NULL;
+	dest_bp->rcursor = NULL;
+
+	src_node = ext2fs_rb_first(&src_bp->root);
+	while (src_node) {
+		src_ext = node_to_extent(src_node);
+		retval = rb_test_clear_bmap_extent(dest,
+					src_ext->start + src->start,
+					src_ext->count);
+		if (retval) {
+			rb_insert_extent(src_ext->start, src_ext->count,
+					 dest_bp);
+			goto next;
+		}
+
+		/* unlikely case, do it one by one block */
+		for (i = src_ext->start;
+		     i < src_ext->start + src_ext->count; i++) {
+			retval = rb_test_clear_bmap_extent(dest, i + src->start, 1);
+			if (retval) {
+				rb_insert_extent(i, 1, dest_bp);
+				continue;
+			}
+			if (dup_allowed) {
+				retval = rb_test_clear_bmap_extent(dup_allowed,
+							i + src->start, 1);
+				/* not existed in dup_allowed */
+				if (retval) {
+					dup_found = 1;
+					if (dup_bp)
+						rb_insert_extent(i, 1, dup_bp);
+				} /* else we conside it not duplicated */
+			} else {
+				if (dup_bp)
+					rb_insert_extent(i, 1, dup_bp);
+				dup_found = 1;
+			}
+		}
+next:
+		src_node = ext2fs_rb_next(src_node);
+	}
+
+	if (dup_found && dup)
+		return EEXIST;
+
+	return 0;
+}
+
 struct ext2_bitmap_ops ext2fs_blkmap64_rbtree = {
 	.type = EXT2FS_BMAP64_RBTREE,
 	.new_bmap = rb_new_bmap,
 	.free_bmap = rb_free_bmap,
 	.copy_bmap = rb_copy_bmap,
+	.merge_bmap = rb_merge_bmap,
 	.resize_bmap = rb_resize_bmap,
 	.mark_bmap = rb_mark_bmap,
 	.unmark_bmap = rb_unmark_bmap,
-- 
2.35.3

[RFC 06/13] blkmap64_ba: Implement initial implementation of merge bitmaps

[Ritesh Harjani]

DO NOT MERGE

Adding a basic merge implementation of bitarray for later
adding/supporting test cases w.r.t. libext2fs merge/clone API.

Signed-off-by: Ritesh Harjani <ritesh.list@gmail.com>
---
 lib/ext2fs/blkmap64_ba.c | 53 +++++++++++++++++++++++++++++++++++++++-
 1 file changed, 52 insertions(+), 1 deletion(-)

diff --git a/lib/ext2fs/blkmap64_ba.c b/lib/ext2fs/blkmap64_ba.c
index 4e7007f0..9a9f6563 100644
--- a/lib/ext2fs/blkmap64_ba.c
+++ b/lib/ext2fs/blkmap64_ba.c
@@ -12,6 +12,7 @@
 #include "config.h"
 #include <stdio.h>
 #include <string.h>
+#include <assert.h>
 #if HAVE_UNISTD_H
 #include <unistd.h>
 #endif
@@ -476,6 +477,55 @@ static errcode_t ba_find_first_set(ext2fs_generic_bitmap_64 bitmap,
 
 	return ENOENT;
 }
+errcode_t ba_merge_bmap(ext2fs_generic_bitmap_64 src,
+						ext2fs_generic_bitmap_64 dst,
+						ext2fs_generic_bitmap_64 dup,
+						ext2fs_generic_bitmap_64 dup_allowed)
+{
+	ext2fs_ba_private src_bp = (ext2fs_ba_private) src->private;
+	ext2fs_ba_private dst_bp = (ext2fs_ba_private) dst->private;
+
+	const unsigned char *src_pos = src_bp->bitarray;
+	const unsigned char *dst_pos = dst_bp->bitarray;
+	unsigned long count = src->real_end - src->start + 1;
+	unsigned long bitpos = src->start;
+
+	assert(src->start == dst->start);
+	assert(src->end == dst->end);
+	assert(src->real_end == dst->real_end);
+
+	// TODO add full support
+	// For now assuming the pos is aligned addr
+	assert(!(((uintptr_t)src_pos) & 0x07));
+
+	// 8-byte blocks compare
+	while (count >= 64) {
+		const __u64 src_val = *(const __u64 *)src_pos;
+		const __u64 dst_val = *(const __u64 *)dst_pos;
+		const __u64 sd_val = src_val & dst_val;
+
+		// TODO: Not implemented case to handle duplicates/dup_allowed case of EA
+		if (dup || dup_allowed)
+			assert(sd_val == 0);
+
+		*(__u64 *)dst_pos |= src_val;
+
+		src_pos += 8;
+		dst_pos += 8;
+		count -= 64;
+		bitpos += 64;
+	}
+
+	while (count-- > 0) {
+		// TODO: dup case not implemented yet.
+		if (ext2fs_test_bit64(bitpos, src_bp->bitarray))
+			assert(ext2fs_set_bit64(bitpos, dst_bp->bitarray) == 0);
+		bitpos++;
+	}
+
+	return 0;
+}
+
 
 struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = {
 	.type = EXT2FS_BMAP64_BITARRAY,
@@ -494,5 +544,6 @@ struct ext2_bitmap_ops ext2fs_blkmap64_bitarray = {
 	.clear_bmap = ba_clear_bmap,
 	.print_stats = ba_print_stats,
 	.find_first_zero = ba_find_first_zero,
-	.find_first_set = ba_find_first_set
+	.find_first_set = ba_find_first_set,
+	.merge_bmap = ba_merge_bmap,
 };
-- 
2.35.3

[RFC 07/13] tst_bitmaps_standalone: Add copy and merge bitmaps test

[Ritesh Harjani]

This adds a basic copy and merge api test for both bitmap types
(i.e. rbtree and bitarray)

Signed-off-by: Ritesh Harjani <ritesh.list@gmail.com>
---
 lib/ext2fs/Makefile.in              |  25 +++-
 lib/ext2fs/tst_bitmaps_standalone.c | 173 ++++++++++++++++++++++++++++
 2 files changed, 192 insertions(+), 6 deletions(-)
 create mode 100644 lib/ext2fs/tst_bitmaps_standalone.c

diff --git a/lib/ext2fs/Makefile.in b/lib/ext2fs/Makefile.in
index f6a050a2..1692500e 100644
--- a/lib/ext2fs/Makefile.in
+++ b/lib/ext2fs/Makefile.in
@@ -227,6 +227,7 @@ SRCS= ext2_err.c \
 	$(srcdir)/write_bb_file.c \
 	$(srcdir)/rbtree.c \
 	$(srcdir)/tst_libext2fs.c \
+	$(srcdir)/tst_bitmaps_standalone.c \
 	$(DEBUG_SRCS)
 
 HFILES= bitops.h ext2fs.h ext2_io.h ext2_fs.h ext2_ext_attr.h ext3_extents.h \
@@ -328,9 +329,9 @@ tst_getsectsize: tst_getsectsize.o getsectsize.o $(STATIC_LIBEXT2FS) \
 		$(ALL_LDFLAGS) $(STATIC_LIBEXT2FS) $(STATIC_LIBCOM_ERR) \
 		$(SYSLIBS)
 
-tst_types.o: $(srcdir)/tst_types.c ext2_types.h 
+tst_types.o: $(srcdir)/tst_types.c ext2_types.h
 
-tst_types: tst_types.o ext2_types.h 
+tst_types: tst_types.o ext2_types.h
 	$(E) "	LD $@"
 	$(Q) $(CC) -o tst_types tst_types.o $(ALL_LDFLAGS) $(SYSLIBS)
 
@@ -362,6 +363,11 @@ tst_sha512: $(srcdir)/sha512.c $(srcdir)/ext2_fs.h
 	$(Q) $(CC) $(ALL_LDFLAGS) $(ALL_CFLAGS) -o tst_sha512 \
 		$(srcdir)/sha512.c -DUNITTEST $(SYSLIBS)
 
+tst_bitmaps_standalone: tst_bitmaps_standalone.o $(STATIC_LIBEXT2FS) $(DEPSTATIC_LIBCOM_ERR)
+	$(E) "	LD $@"
+	$(Q) $(CC) -o tst_bitmaps_standalone tst_bitmaps_standalone.o $(ALL_LDFLAGS) \
+		$(STATIC_LIBEXT2FS) $(STATIC_LIBCOM_ERR) $(SYSLIBS)
+
 ext2_tdbtool: tdbtool.o
 	$(E) "	LD $@"
 	$(Q) $(CC) -o ext2_tdbtool tdbtool.o tdb.o $(ALL_LDFLAGS) $(SYSLIBS)
@@ -533,7 +539,7 @@ mkjournal: mkjournal.c $(STATIC_LIBEXT2FS) $(DEPLIBCOM_ERR)
 fullcheck check:: tst_bitops tst_badblocks tst_iscan tst_types tst_icount \
     tst_super_size tst_types tst_inode_size tst_csum tst_crc32c tst_bitmaps \
     tst_inline tst_inline_data tst_libext2fs tst_sha256 tst_sha512 \
-    tst_digest_encode tst_getsize tst_getsectsize
+    tst_digest_encode tst_getsize tst_getsectsize tst_bitmaps_standalone
 	$(TESTENV) ./tst_bitops
 	$(TESTENV) ./tst_badblocks
 	$(TESTENV) ./tst_iscan
@@ -556,6 +562,7 @@ fullcheck check:: tst_bitops tst_badblocks tst_iscan tst_types tst_icount \
 	$(TESTENV) ./tst_bitmaps -l -f $(srcdir)/tst_bitmaps_cmds > tst_bitmaps_out
 	diff $(srcdir)/tst_bitmaps_exp tst_bitmaps_out
 	$(TESTENV) ./tst_digest_encode
+	$(TESTENV) ./tst_bitmaps_standalone
 
 installdirs::
 	$(E) "	MKDIR_P $(libdir) $(includedir)/ext2fs"
@@ -581,7 +588,7 @@ install:: all $(HFILES) $(HFILES_IN) installdirs ext2fs.pc
 uninstall::
 	$(RM) -f $(DESTDIR)$(libdir)/libext2fs.a \
 		$(DESTDIR)$(pkgconfigdir)/ext2fs.pc
-	$(RM) -rf $(DESTDIR)$(includedir)/ext2fs 
+	$(RM) -rf $(DESTDIR)$(includedir)/ext2fs
 
 clean::
 	$(RM) -f \#* *.s *.o *.a *~ *.bak core profiled/* \
@@ -590,7 +597,7 @@ clean::
 		tst_bitops tst_types tst_icount tst_super_size tst_csum \
 		tst_bitmaps tst_bitmaps_out tst_extents tst_inline \
 		tst_inline_data tst_inode_size tst_bitmaps_cmd.c \
-		tst_digest_encode tst_sha256 tst_sha512 \
+		tst_digest_encode tst_sha256 tst_sha512  tst_bitmaps_standalone \
 		ext2_tdbtool mkjournal debug_cmds.c tst_cmds.c extent_cmds.c \
 		../libext2fs.a ../libext2fs_p.a ../libext2fs_chk.a \
 		crc32c_table.h gen_crc32ctable tst_crc32c tst_libext2fs \
@@ -646,7 +653,7 @@ windows_io.o: $(srcdir)/windows_io.c $(top_builddir)/lib/config.h \
  $(srcdir)/ext2_ext_attr.h $(srcdir)/bitops.h $(srcdir)/ext2fsP.h
 
 # +++ Dependency line eater +++
-# 
+#
 # Makefile dependencies follow.  This must be the last section in
 # the Makefile.in file
 #
@@ -1156,6 +1163,12 @@ tst_iscan.o: $(srcdir)/tst_iscan.c $(top_builddir)/lib/config.h \
  $(srcdir)/ext2_fs.h $(srcdir)/ext3_extents.h $(top_srcdir)/lib/et/com_err.h \
  $(srcdir)/ext2_io.h $(top_builddir)/lib/ext2fs/ext2_err.h \
  $(srcdir)/ext2_ext_attr.h $(srcdir)/hashmap.h $(srcdir)/bitops.h
+tst_bitmaps_standalone.o: $(srcdir)/tst_bitmaps_standalone.c $(top_builddir)/lib/config.h \
+ $(top_builddir)/lib/dirpaths.h $(srcdir)/ext2_fs.h \
+ $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/ext2fs.h \
+ $(srcdir)/ext2_fs.h $(srcdir)/ext3_extents.h $(top_srcdir)/lib/et/com_err.h \
+ $(srcdir)/ext2_io.h $(top_builddir)/lib/ext2fs/ext2_err.h \
+ $(srcdir)/ext2_ext_attr.h $(srcdir)/hashmap.h $(srcdir)/bitops.h
 undo_io.o: $(srcdir)/undo_io.c $(top_builddir)/lib/config.h \
  $(top_builddir)/lib/dirpaths.h $(srcdir)/ext2_fs.h \
  $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/ext2fs.h \
diff --git a/lib/ext2fs/tst_bitmaps_standalone.c b/lib/ext2fs/tst_bitmaps_standalone.c
new file mode 100644
index 00000000..325398f8
--- /dev/null
+++ b/lib/ext2fs/tst_bitmaps_standalone.c
@@ -0,0 +1,173 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+#include <assert.h>
+#if HAVE_UNISTD_H
+#include <unistd.h>
+#endif
+#include <fcntl.h>
+#include <time.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#if HAVE_ERRNO_H
+#include <errno.h>
+#endif
+
+#include "ext2_fs.h"
+#include "ext2fs.h"
+#include "bmap64.h"
+
+ext2_filsys test_fs;
+ext2fs_block_bitmap block_map_1;
+ext2fs_block_bitmap block_map_2;
+ext2fs_block_bitmap block_map;
+
+static int test_fail = 0;
+
+void dump_bitmap(ext2fs_generic_bitmap bmap, unsigned int start, unsigned num)
+{
+	unsigned char	*buf;
+	errcode_t	retval;
+	int	i, len = (num - start + 7) / 8;
+
+	buf = malloc(len);
+	if (!buf) {
+		com_err("dump_bitmap", 0, "couldn't allocate buffer");
+		return;
+	}
+	memset(buf, 0, len);
+	retval = ext2fs_get_generic_bmap_range(bmap, (__u64) start, num, buf);
+	if (retval) {
+		com_err("dump_bitmap", retval,
+			"while calling ext2fs_generic_bmap_range");
+		free(buf);
+		return;
+	}
+	for (i=len-1; i >= 0; i--)
+		printf("%02x ", buf[i]);
+	printf("\n");
+	printf("bits set: %u\n", ext2fs_bitcount(buf, len));
+	free(buf);
+}
+
+static void test_copy_run()
+{
+	int blocks[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 21, 23, 26, 29, 33, 37, 38};
+	errcode_t ret;
+	char *buf_map = NULL;
+	char *buf_copy_map = NULL;
+
+	assert(ext2fs_allocate_block_bitmap(test_fs, "block bitmap", &block_map_1) == 0);
+
+	for (int i = 0; i < sizeof(blocks)/sizeof(blocks[0]); i++) {
+		ext2fs_mark_block_bitmap2(block_map_1, blocks[i]);
+	}
+
+	assert(ext2fs_copy_bitmap(block_map_1, &block_map) == 0);
+
+	if (ext2fs_compare_block_bitmap(block_map_1, block_map) != 0) {
+		printf("block bitmap copy test failed\n");
+		test_fail++;
+
+		dump_bitmap(block_map_1, test_fs->super->s_first_data_block,
+				test_fs->super->s_blocks_count);
+
+		dump_bitmap(block_map, test_fs->super->s_first_data_block,
+				test_fs->super->s_blocks_count);
+	}
+
+	ext2fs_free_block_bitmap(block_map_1);
+	ext2fs_free_block_bitmap(block_map);
+}
+
+void test_merge_run()
+{
+	int blocks_odd[] = {1, 3, 5, 7, 9, 21, 23, 29, 33, 37};
+	int blocks_even[] = {2, 4, 6, 8, 10, 26, 38};
+	ext2fs_generic_bitmap_64 tmp_map;
+
+	assert(ext2fs_allocate_block_bitmap(test_fs, "block bitmap 1", &block_map_1) == 0);
+	assert(ext2fs_allocate_block_bitmap(test_fs, "block bitmap 2", &block_map_2) == 0);
+	assert(ext2fs_allocate_block_bitmap(test_fs, "block bitmap 2", &block_map) == 0);
+
+	for (int i = 0; i < sizeof(blocks_odd) / sizeof(blocks_odd[0]); i++) {
+		ext2fs_mark_block_bitmap2(block_map_1, blocks_odd[i]);
+		ext2fs_mark_block_bitmap2(block_map, blocks_odd[i]);
+	}
+
+	for (int i = 0; i < sizeof(blocks_even) / sizeof(blocks_even[0]); i++) {
+		ext2fs_mark_block_bitmap2(block_map_2, blocks_even[i]);
+		ext2fs_mark_block_bitmap2(block_map, blocks_even[i]);
+	}
+
+	assert(ext2fs_merge_bitmap(block_map_2, block_map_1, NULL, NULL) == 0);
+	if (ext2fs_compare_block_bitmap(block_map_1, block_map) != 0) {
+		printf("block bitmap merge test failed\n");
+		test_fail++;
+
+		dump_bitmap(block_map_1, test_fs->super->s_first_data_block,
+				test_fs->super->s_blocks_count);
+
+		dump_bitmap(block_map, test_fs->super->s_first_data_block,
+				test_fs->super->s_blocks_count);
+	}
+
+	ext2fs_free_block_bitmap(block_map_1);
+	ext2fs_free_block_bitmap(block_map_2);
+	ext2fs_free_block_bitmap(block_map);
+}
+
+static void setup_filesystem(const char *name, unsigned int blocks,
+							 unsigned int inodes, unsigned int type,
+							 unsigned int flags)
+{
+	struct ext2_super_block param;
+	errcode_t ret;
+
+	memset(&param, 0, sizeof(param));
+	ext2fs_blocks_count_set(&param, blocks);
+	param.s_inodes_count = inodes;
+
+	ret = ext2fs_initialize(name, flags, &param, test_io_manager,
+							&test_fs);
+	if (ret) {
+		com_err(name, ret, "while initializing filesystem");
+		return;
+	}
+
+	test_fs->default_bitmap_type = type;
+
+	ext2fs_free_block_bitmap(test_fs->block_map);
+	ext2fs_free_block_bitmap(test_fs->inode_map);
+
+	return;
+errout:
+	ext2fs_close_free(&test_fs);
+}
+
+int main(int argc, char **argv)
+{
+	unsigned int blocks = 127;
+	unsigned int inodes = 0;
+	unsigned int type = EXT2FS_BMAP64_RBTREE;
+	unsigned int flags = EXT2_FLAG_64BITS;
+	char *buf = NULL;
+
+	setup_filesystem(argv[0], blocks, inodes, type, flags);
+
+	/* test for EXT2FS_BMAP64_RBTREE */
+	test_copy_run();
+	test_merge_run();
+
+	/* test for EXT2FS_BMAP64_BITARRAY */
+	test_fs->default_bitmap_type = EXT2FS_BMAP64_BITARRAY;
+	test_copy_run();
+	test_merge_run();
+
+	if (test_fail)
+		printf("%s: Test copy & merge bitmaps -- NOT OK\n", argv[0]);
+	else
+		printf("%s: Test copy & merge bitmaps -- OK\n", argv[0]);
+
+	return test_fail;
+}
-- 
2.35.3

[RFC 08/13] tst_bitmaps_pthread: Add merge bitmaps test using pthreads

[Ritesh Harjani]

This patch adds a test to verify the core bitmaps merge APIs
for both bitarray and rbtree type.

Signed-off-by: Ritesh Harjani <ritesh.list@gmail.com>
---
 lib/ext2fs/Makefile.in           |  17 ++-
 lib/ext2fs/tst_bitmaps_pthread.c | 247 +++++++++++++++++++++++++++++++
 2 files changed, 263 insertions(+), 1 deletion(-)
 create mode 100644 lib/ext2fs/tst_bitmaps_pthread.c

diff --git a/lib/ext2fs/Makefile.in b/lib/ext2fs/Makefile.in
index 1692500e..c0694175 100644
--- a/lib/ext2fs/Makefile.in
+++ b/lib/ext2fs/Makefile.in
@@ -228,6 +228,7 @@ SRCS= ext2_err.c \
 	$(srcdir)/rbtree.c \
 	$(srcdir)/tst_libext2fs.c \
 	$(srcdir)/tst_bitmaps_standalone.c \
+	$(srcdir)/tst_bitmaps_pthread.c \
 	$(DEBUG_SRCS)
 
 HFILES= bitops.h ext2fs.h ext2_io.h ext2_fs.h ext2_ext_attr.h ext3_extents.h \
@@ -368,6 +369,11 @@ tst_bitmaps_standalone: tst_bitmaps_standalone.o $(STATIC_LIBEXT2FS) $(DEPSTATIC
 	$(Q) $(CC) -o tst_bitmaps_standalone tst_bitmaps_standalone.o $(ALL_LDFLAGS) \
 		$(STATIC_LIBEXT2FS) $(STATIC_LIBCOM_ERR) $(SYSLIBS)
 
+tst_bitmaps_pthread: tst_bitmaps_pthread.o $(STATIC_LIBEXT2FS) $(DEPSTATIC_LIBCOM_ERR)
+	$(E) "	LD $@"
+	$(Q) $(CC) -o tst_bitmaps_pthread tst_bitmaps_pthread.o $(ALL_LDFLAGS) \
+		$(STATIC_LIBEXT2FS) $(STATIC_LIBCOM_ERR) $(SYSLIBS)
+
 ext2_tdbtool: tdbtool.o
 	$(E) "	LD $@"
 	$(Q) $(CC) -o ext2_tdbtool tdbtool.o tdb.o $(ALL_LDFLAGS) $(SYSLIBS)
@@ -539,7 +545,8 @@ mkjournal: mkjournal.c $(STATIC_LIBEXT2FS) $(DEPLIBCOM_ERR)
 fullcheck check:: tst_bitops tst_badblocks tst_iscan tst_types tst_icount \
     tst_super_size tst_types tst_inode_size tst_csum tst_crc32c tst_bitmaps \
     tst_inline tst_inline_data tst_libext2fs tst_sha256 tst_sha512 \
-    tst_digest_encode tst_getsize tst_getsectsize tst_bitmaps_standalone
+    tst_digest_encode tst_getsize tst_getsectsize tst_bitmaps_standalone \
+	tst_bitmaps_pthread
 	$(TESTENV) ./tst_bitops
 	$(TESTENV) ./tst_badblocks
 	$(TESTENV) ./tst_iscan
@@ -563,6 +570,7 @@ fullcheck check:: tst_bitops tst_badblocks tst_iscan tst_types tst_icount \
 	diff $(srcdir)/tst_bitmaps_exp tst_bitmaps_out
 	$(TESTENV) ./tst_digest_encode
 	$(TESTENV) ./tst_bitmaps_standalone
+	$(TESTENV) ./tst_bitmaps_pthread
 
 installdirs::
 	$(E) "	MKDIR_P $(libdir) $(includedir)/ext2fs"
@@ -598,6 +606,7 @@ clean::
 		tst_bitmaps tst_bitmaps_out tst_extents tst_inline \
 		tst_inline_data tst_inode_size tst_bitmaps_cmd.c \
 		tst_digest_encode tst_sha256 tst_sha512  tst_bitmaps_standalone \
+		tst_bitmaps_pthread \
 		ext2_tdbtool mkjournal debug_cmds.c tst_cmds.c extent_cmds.c \
 		../libext2fs.a ../libext2fs_p.a ../libext2fs_chk.a \
 		crc32c_table.h gen_crc32ctable tst_crc32c tst_libext2fs \
@@ -1169,6 +1178,12 @@ tst_bitmaps_standalone.o: $(srcdir)/tst_bitmaps_standalone.c $(top_builddir)/lib
  $(srcdir)/ext2_fs.h $(srcdir)/ext3_extents.h $(top_srcdir)/lib/et/com_err.h \
  $(srcdir)/ext2_io.h $(top_builddir)/lib/ext2fs/ext2_err.h \
  $(srcdir)/ext2_ext_attr.h $(srcdir)/hashmap.h $(srcdir)/bitops.h
+tst_bitmaps_pthread.o: $(srcdir)/tst_bitmaps_pthread.c $(top_builddir)/lib/config.h \
+ $(top_builddir)/lib/dirpaths.h $(srcdir)/ext2_fs.h \
+ $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/ext2fs.h \
+ $(srcdir)/ext2_fs.h $(srcdir)/ext3_extents.h $(top_srcdir)/lib/et/com_err.h \
+ $(srcdir)/ext2_io.h $(top_builddir)/lib/ext2fs/ext2_err.h \
+ $(srcdir)/ext2_ext_attr.h $(srcdir)/hashmap.h $(srcdir)/bitops.h
 undo_io.o: $(srcdir)/undo_io.c $(top_builddir)/lib/config.h \
  $(top_builddir)/lib/dirpaths.h $(srcdir)/ext2_fs.h \
  $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/ext2fs.h \
diff --git a/lib/ext2fs/tst_bitmaps_pthread.c b/lib/ext2fs/tst_bitmaps_pthread.c
new file mode 100644
index 00000000..2ce389b0
--- /dev/null
+++ b/lib/ext2fs/tst_bitmaps_pthread.c
@@ -0,0 +1,247 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+#include <assert.h>
+#if HAVE_UNISTD_H
+#include <unistd.h>
+#endif
+#include <fcntl.h>
+#include <time.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#if HAVE_ERRNO_H
+#include <errno.h>
+#endif
+#if HAVE_PTHREAD
+#include <pthread.h>
+#endif
+
+#include "ext2_fs.h"
+#include "ext2fs.h"
+
+/*
+ * In this test we first setup used_bitmap by setting some random bits.
+ * This used_bitmap is then scanned in parallel by two threads, each scanning
+ * upto nr_bits/2 and setting their respective child_bitmap.
+ * Then once both threads finishes, we merge the child_bitmap_1/2 into
+ * parent_bitmap which then is used to compare against used_bitmap.
+ * In the end used_bitmap bits should match with parent_bitmap.
+ *
+ * Note we use EXT2FS_BMAP64_BITARRAY always for used_bitmap, this is because
+ * EXT2FS_BMAP64_RBTREE does not support parallel scan due to rcursor
+ * optimization.
+ */
+
+int test_fail = 0;
+ext2fs_generic_bitmap child_bitmap1, child_bitmap2, parent_bitmap;
+ext2fs_generic_bitmap used_bitmap;
+pthread_t pthread_infos[2];
+
+#define nr_bits 8192
+int nr_threads = 2;
+int bitmap_type[2] = {EXT2FS_BMAP64_BITARRAY, EXT2FS_BMAP64_RBTREE};
+
+void dump_bitmap(ext2fs_generic_bitmap bmap, unsigned int start, unsigned num)
+{
+	unsigned char	*buf;
+	errcode_t	retval;
+	int	i, len = (num - start + 7) / 8;
+
+	buf = malloc(len);
+	if (!buf) {
+		com_err("dump_bitmap", 0, "couldn't allocate buffer");
+		return;
+	}
+	memset(buf, 0, len);
+	retval = ext2fs_get_generic_bmap_range(bmap, (__u64) start, num, buf);
+	if (retval) {
+		com_err("dump_bitmap", retval,
+			"while calling ext2fs_generic_bmap_range");
+		free(buf);
+		return;
+	}
+	for (i=len-1; i >= 0; i--)
+		printf("%02x ", buf[i]);
+	printf("\n");
+	printf("bits set: %u\n", ext2fs_bitcount(buf, len));
+	free(buf);
+}
+
+int should_mark_bit()
+{
+	return rand() % 2 == 0;
+}
+
+void alloc_bitmaps(int type)
+{
+	errcode_t retval;
+
+	retval = ext2fs_alloc_generic_bmap(NULL, EXT2_ET_MAGIC_GENERIC_BITMAP64,
+							  type, 0, nr_bits, nr_bits,
+							  "child bitmap1", &child_bitmap1);
+	if (retval)
+		goto out;
+
+	retval = ext2fs_alloc_generic_bmap(NULL, EXT2_ET_MAGIC_GENERIC_BITMAP64,
+							  type, 0, nr_bits, nr_bits,
+							  "child bitmap2", &child_bitmap2);
+	if (retval)
+		goto out;
+
+	retval = ext2fs_alloc_generic_bmap(NULL, EXT2_ET_MAGIC_GENERIC_BITMAP64,
+							  type, 0, nr_bits, nr_bits,
+							  "parent bitmap", &parent_bitmap);
+	if (retval)
+		goto out;
+
+	/*
+	 * Note that EXT2FS_BMAP64_RBTREE doesn't support parallel read.
+	 * this is due to a optimization of maintaining a read cursor within
+	 * rbtree bitmap implementation.
+	 */
+	retval = ext2fs_alloc_generic_bmap(NULL, EXT2_ET_MAGIC_GENERIC_BITMAP64,
+							  EXT2FS_BMAP64_BITARRAY, 0, nr_bits, nr_bits,
+							  "used bitmap", &used_bitmap);
+	if (retval)
+		goto out;
+
+	return;
+out:
+	com_err("alloc_bitmaps", retval, "while allocating bitmaps\n");
+	exit(1);
+}
+
+void setup_bitmaps()
+{
+	int i = 0;
+	errcode_t retval;
+
+	/*
+	 * Note we cannot setup used_bitmap in parallel w/o locking.
+	 * Hence setting up the used_bitmap (random bits) here before
+	 * starting pthreads.
+	 */
+	for (i = 0; i < nr_bits; i++) {
+		if (should_mark_bit())
+			ext2fs_mark_generic_bmap(used_bitmap, i);
+	}
+}
+
+static void *run_pthread(void *arg)
+{
+	int i = 0, j = 0, start, end;
+	ext2fs_generic_bitmap test_bitmap;
+	errcode_t retval = 0;
+	pthread_t id = pthread_self();
+
+	if (pthread_equal(pthread_infos[0], id)) {
+		start = 0;
+		end = nr_bits/2;
+		test_bitmap = child_bitmap1;
+	} else {
+		start = nr_bits / 2 + 1;;
+		end = nr_bits - 1;
+		test_bitmap = child_bitmap2;
+	}
+
+	for (i = start; i <= end; i++) {
+		if (ext2fs_test_generic_bmap(used_bitmap, i)) {
+			retval = ext2fs_mark_generic_bmap(test_bitmap, i);
+			if (retval) {
+				com_err("run_pthread", retval, "while marking child bitmaps %d\n", i);
+				test_fail++;
+				pthread_exit(&retval);
+			}
+		}
+	}
+	return NULL;
+}
+
+void run_pthreads()
+{
+	errcode_t retval;
+	void *retp[2];
+	int i;
+
+	for (i = 0; i < nr_threads; i++) {
+		printf("Starting thread (%d)\n", i);
+		retval = pthread_create(&pthread_infos[i], NULL, &run_pthread, NULL);
+		if (retval) {
+			com_err("run_pthreads", retval, "while pthread_create");
+			exit(1);
+		}
+	}
+
+	for (i = 0; i < nr_threads; i++) {
+		void *status;
+		int ret;
+		retval = pthread_join(pthread_infos[i], &status);
+		if (retval) {
+			com_err("run_pthreads", retval, "while joining pthreads");
+			exit(1);
+
+		}
+		ret = status == NULL ? 0 : *(int*)status;
+		if (ret) {
+			com_err("run_pthreads", ret, "pthread returned error");
+			test_fail++;
+		}
+
+		printf("Closing thread (%d), ret(%d)\n", i, ret);
+	}
+
+	assert(ext2fs_merge_bitmap(child_bitmap1, parent_bitmap, NULL, NULL) == 0);
+	assert(ext2fs_merge_bitmap(child_bitmap2, parent_bitmap, NULL, NULL) == 0);
+}
+
+void test_bitmaps(int type)
+{
+	errcode_t retval;
+	retval = ext2fs_compare_generic_bmap(EXT2_ET_NEQ_BLOCK_BITMAP, parent_bitmap,
+				used_bitmap);
+	if (retval) {
+		test_fail++;
+		printf("Bitmaps compare failed for bitmap type %d err %ld\n", type, retval);
+		dump_bitmap(parent_bitmap, 0, nr_bits);
+		dump_bitmap(used_bitmap, 0, nr_bits);
+	}
+}
+
+void free_bitmaps()
+{
+	ext2fs_free_generic_bmap(child_bitmap1);
+	ext2fs_free_generic_bmap(child_bitmap2);
+	ext2fs_free_generic_bmap(parent_bitmap);
+	ext2fs_free_generic_bmap(used_bitmap);
+}
+
+int main(int argc, char *argv[])
+{
+	int i;
+	int ret = 0;
+
+#ifndef HAVE_PTHREAD
+	printf("No PTHREAD support, exiting...\n");
+	return ret;
+#endif
+
+	srand(time(0));
+
+	/* loop to test for both bitmap types */
+	for (i = 0; i < 2; i++) {
+		test_fail = 0;
+		alloc_bitmaps(i);
+		setup_bitmaps();
+		run_pthreads();
+		test_bitmaps(i);
+		free_bitmaps();
+
+		if (test_fail)
+			printf("%s: Test with bitmap (%d) NOT OK!!\n", argv[0], bitmap_type[i]);
+		else
+			printf("%s: Test with bitmap (%d) OK!!\n", argv[0], bitmap_type[i]);
+		ret |= test_fail;
+	}
+
+	return ret;
+}
-- 
2.35.3

[RFC 09/13] badblocks: Add badblocks merge logic

[Ritesh Harjani]

From: Wang Shilong <wshilong@ddn.com>

Add badblocks merge logic

Signed-off-by: Wang Shilong <wshilong@ddn.com>
Signed-off-by: Ritesh Harjani <ritesh.list@gmail.com>
---
 lib/ext2fs/badblocks.c | 75 ++++++++++++++++++++++++++++++++++++++++++
 lib/ext2fs/ext2fs.h    |  2 ++
 2 files changed, 77 insertions(+)

diff --git a/lib/ext2fs/badblocks.c b/lib/ext2fs/badblocks.c
index 0570b131..48968adc 100644
--- a/lib/ext2fs/badblocks.c
+++ b/lib/ext2fs/badblocks.c
@@ -56,6 +56,74 @@ static errcode_t make_u32_list(int size, int num, __u32 *list,
 	return 0;
 }
 
+static inline int insert_ok(blk_t *array, int cnt, blk_t new)
+{
+   return (cnt == 0 || array[cnt - 1] != new);
+}
+
+/*
+ * Merge list from src to dest
+ */
+static errcode_t merge_u32_list(ext2_u32_list src, ext2_u32_list dest)
+{
+   errcode_t    retval;
+   int      src_count = src->num;
+   int      dest_count = dest->num;
+   int      size = src_count + dest_count;
+   int      size_entry = sizeof(blk_t);
+   blk_t       *array;
+   blk_t       *src_array = src->list;
+   blk_t       *dest_array = dest->list;
+   int      src_index = 0;
+   int      dest_index = 0;
+   int      uniq_cnt = 0;
+
+   if (src->num == 0)
+       return 0;
+
+   retval = ext2fs_get_array(size, size_entry, &array);
+   if (retval)
+       return retval;
+
+   /*
+    * It is possible that src list and dest list could be
+    * duplicated when merging badblocks.
+    */
+   while (src_index < src_count || dest_index < dest_count) {
+       if (src_index >= src_count) {
+           for (; dest_index < dest_count; dest_index++)
+               if (insert_ok(array, uniq_cnt, dest_array[dest_index]))
+                   array[uniq_cnt++] = dest_array[dest_index];
+           break;
+       }
+       if (dest_index >= dest_count) {
+           for (; src_index < src_count; src_index++)
+               if (insert_ok(array, uniq_cnt, src_array[src_index]))
+                   array[uniq_cnt++] = src_array[src_index];
+           break;
+       }
+       if (src_array[src_index] < dest_array[dest_index]) {
+           if (insert_ok(array, uniq_cnt, src_array[src_index]))
+               array[uniq_cnt++] = src_array[src_index];
+           src_index++;
+       } else if (src_array[src_index] > dest_array[dest_index]) {
+           if (insert_ok(array, uniq_cnt, dest_array[dest_index]))
+               array[uniq_cnt++] = dest_array[dest_index];
+           dest_index++;
+       } else {
+           if (insert_ok(array, uniq_cnt, dest_array[dest_index]))
+               array[uniq_cnt++] = dest_array[dest_index];
+           src_index++;
+           dest_index++;
+       }
+   }
+
+   ext2fs_free_mem(&dest->list);
+   dest->list = array;
+   dest->num = uniq_cnt;
+   dest->size = size;
+   return 0;
+}
 
 /*
  * This procedure creates an empty u32 list.
@@ -91,6 +159,13 @@ errcode_t ext2fs_badblocks_copy(ext2_badblocks_list src,
 			       (ext2_u32_list *) dest);
 }
 
+errcode_t ext2fs_badblocks_merge(ext2_badblocks_list src,
+                ext2_badblocks_list dest)
+{
+   return merge_u32_list((ext2_u32_list) src,
+                 (ext2_u32_list) dest);
+}
+
 /*
  * This procedure frees a badblocks list.
  *
diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h
index c18849d7..13404f3d 100644
--- a/lib/ext2fs/ext2fs.h
+++ b/lib/ext2fs/ext2fs.h
@@ -844,6 +844,8 @@ extern int ext2fs_badblocks_list_iterate(ext2_badblocks_iterate iter,
 extern void ext2fs_badblocks_list_iterate_end(ext2_badblocks_iterate iter);
 extern errcode_t ext2fs_badblocks_copy(ext2_badblocks_list src,
 				       ext2_badblocks_list *dest);
+extern errcode_t ext2fs_badblocks_merge(ext2_badblocks_list src,
+                   ext2_badblocks_list dest);
 extern int ext2fs_badblocks_equal(ext2_badblocks_list bb1,
 				  ext2_badblocks_list bb2);
 extern int ext2fs_u32_list_count(ext2_u32_list bb);
-- 
2.35.3

[RFC 10/13] tst_badblocks: Add unit test to verify badblocks list merge api

[Ritesh Harjani]

Add unit test to verify badblocks list merge api i.e.
ext2fs_badblocks_merge()

Signed-off-by: Ritesh Harjani <ritesh.list@gmail.com>
---
 lib/ext2fs/tst_badblocks.c | 61 ++++++++++++++++++++++++++++++++++++--
 1 file changed, 59 insertions(+), 2 deletions(-)

diff --git a/lib/ext2fs/tst_badblocks.c b/lib/ext2fs/tst_badblocks.c
index b6e766ab..946de0ae 100644
--- a/lib/ext2fs/tst_badblocks.c
+++ b/lib/ext2fs/tst_badblocks.c
@@ -119,6 +119,40 @@ static void print_list(badblocks_list bb, int verify)
 	}
 }
 
+static void do_list_merge_verify(badblocks_list bb, badblocks_list bbm, int verify)
+{
+	errcode_t retval;
+	badblocks_iterate iter;
+	blk_t blk;
+	int i, ok;
+
+	retval = ext2fs_badblocks_merge(bb, bbm);
+	if (retval) {
+		com_err("do_list_merge_verify", retval, "while doing list merge");
+		return;
+	}
+
+	if (!verify)
+		return;
+
+	retval = ext2fs_badblocks_list_iterate_begin(bb, &iter);
+	if (retval) {
+		com_err("do_list_merge_verify", retval, "while setting up iterator");
+		return;
+	}
+
+	while (ext2fs_badblocks_list_iterate(iter, &blk)) {
+		retval = ext2fs_badblocks_list_test(bbm, blk);
+		if (retval == 0) {
+			printf(" --- NOT OK\n");
+			test_fail++;
+			return;
+		}
+	}
+	ext2fs_badblocks_list_iterate_end(iter);
+	printf(" --- OK\n");
+}
+
 static void validate_test_seq(badblocks_list bb, blk_t *vec)
 {
 	int	i, match, ok;
@@ -275,13 +309,13 @@ out:
 
 int main(int argc, char **argv)
 {
-	badblocks_list bb1, bb2, bb3, bb4, bb5;
+	badblocks_list bb1, bb2, bb3, bb4, bb5, bbm;
 	int	equal;
 	errcode_t	retval;
 
 	add_error_table(&et_ext2_error_table);
 
-	bb1 = bb2 = bb3 = bb4 = bb5 = 0;
+	bb1 = bb2 = bb3 = bb4 = bb5 = bbm = 0;
 
 	printf("test1: ");
 	retval = create_test_list(test1, &bb1);
@@ -346,6 +380,27 @@ int main(int argc, char **argv)
 		printf("\n");
 	}
 
+	printf("Create merge bb list\n");
+	retval = ext2fs_badblocks_list_create(&bbm, 5);
+	if (retval) {
+		com_err("ext2fs_badblocks_list_create", retval, "while creating list");
+		test_fail++;
+	}
+
+	printf("Merge & Verify all bb{1..5} into bbm\n");
+	if (bb1 && bb2 && bb3 && bb4 && bb5 && bbm) {
+		printf("Merge bb1 into bbm");
+		do_list_merge_verify(bb1, bbm, 1);
+		printf("Merge bb2 into bbm");
+		do_list_merge_verify(bb2, bbm, 1);
+		printf("Merge bb3 into bbm");
+		do_list_merge_verify(bb3, bbm, 1);
+		printf("Merge bb4 into bbm");
+		do_list_merge_verify(bb4, bbm, 1);
+		printf("Merge bb5 into bbm");
+		do_list_merge_verify(bb5, bbm, 1);
+	}
+
 	file_test(bb4);
 
 	file_test_invalid(bb4);
@@ -363,6 +418,8 @@ int main(int argc, char **argv)
 		ext2fs_badblocks_list_free(bb4);
 	if (bb5)
 		ext2fs_badblocks_list_free(bb5);
+	if (bbm)
+		ext2fs_badblocks_list_free(bbm);
 
 	return test_fail;
 
-- 
2.35.3

[RFC 11/13] dblist: add dblist merge logic

[Ritesh Harjani]

From: Li Xi <lixi@ddn.com>

This adds dblist merge logic.

TODO: Add a unit test for core operations of dblist. Currently there is
no such test for this.

Signed-off-by: Li Xi <lixi@ddn.com>
Signed-off-by: Ritesh Harjani <ritesh.list@gmail.com>
---
 lib/ext2fs/dblist.c | 36 ++++++++++++++++++++++++++++++++++++
 lib/ext2fs/ext2fs.h |  1 +
 2 files changed, 37 insertions(+)

diff --git a/lib/ext2fs/dblist.c b/lib/ext2fs/dblist.c
index bbdb221d..5568b8ec 100644
--- a/lib/ext2fs/dblist.c
+++ b/lib/ext2fs/dblist.c
@@ -119,6 +119,42 @@ errcode_t ext2fs_copy_dblist(ext2_dblist src, ext2_dblist *dest)
 	return 0;
 }
 
+/*
+ * Merge a directory block list @src to @dest
+ */
+errcode_t ext2fs_merge_dblist(ext2_dblist src, ext2_dblist dest)
+{
+   unsigned long long src_count = src->count;
+   unsigned long long dest_count = dest->count;
+   unsigned long long size = src_count + dest_count;
+   size_t size_entry = sizeof(struct ext2_db_entry2);
+   struct ext2_db_entry2 *array, *array2;
+   errcode_t retval;
+
+   if (src_count == 0)
+       return 0;
+
+   if (src->sorted || (dest->sorted && dest_count != 0))
+       return EINVAL;
+
+   retval = ext2fs_get_array(size, size_entry, &array);
+   if (retval)
+       return retval;
+
+   array2 = array;
+   memcpy(array, src->list, src_count * size_entry);
+   array += src_count;
+   memcpy(array, dest->list, dest_count * size_entry);
+   ext2fs_free_mem(&dest->list);
+
+   dest->list = array2;
+   dest->count = src_count + dest_count;
+   dest->size = size;
+   dest->sorted = 0;
+
+   return 0;
+}
+
 /*
  * Close a directory block list
  *
diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h
index 13404f3d..29e7be9f 100644
--- a/lib/ext2fs/ext2fs.h
+++ b/lib/ext2fs/ext2fs.h
@@ -1146,6 +1146,7 @@ extern errcode_t ext2fs_add_dir_block(ext2_dblist dblist, ext2_ino_t ino,
 				      blk_t blk, int blockcnt);
 extern errcode_t ext2fs_add_dir_block2(ext2_dblist dblist, ext2_ino_t ino,
 				       blk64_t blk, e2_blkcnt_t blockcnt);
+extern errcode_t ext2fs_merge_dblist(ext2_dblist src, ext2_dblist dest);
 extern void ext2fs_dblist_sort(ext2_dblist dblist,
 			       EXT2_QSORT_TYPE (*sortfunc)(const void *,
 							   const void *));
-- 
2.35.3

[RFC 12/13] libext2fs: dupfs: Add fs clone & merge api

[Ritesh Harjani]

From: Saranya Muruganandam <saranyamohan@google.com>

This patch mainly adds "parent" & "clone_flags" member in ext2_filsys struct
for enabling multi-threading. Based on what CLONE flags will be passed from
the client of libext2fs down to ext2fs_clone_fs(), those structures/bitmaps will
be cloned (thread-aware child copy) and rest will be shared with the parent fs.

The same flags will also help to merge those cloned bitmap structures back into
the parent bitmaps when ext2fs_merge_fs() will be called with childfs struct.

Review couple of todos within the patch.
1. I think we don't need refcount here.
2. For io_channel_close(), I think that might be required here (even though
   earlier I thought it should be done by the caller), before freeing childfs.

Signed-off-by: Saranya Muruganandam <saranyamohan@google.com>
[added todos, modified naming, used #ifdef HAVE_PTHREAD, small bug fix in
calling io_channel_close(), later added a test case against this patch]
Signed-off-by: Ritesh Harjani <ritesh.list@gmail.com>
---
 lib/ext2fs/dupfs.c  | 149 ++++++++++++++++++++++++++++++++++++++++++++
 lib/ext2fs/ext2fs.h |  24 +++++++
 2 files changed, 173 insertions(+)

diff --git a/lib/ext2fs/dupfs.c b/lib/ext2fs/dupfs.c
index 02721e1a..8500a82c 100644
--- a/lib/ext2fs/dupfs.c
+++ b/lib/ext2fs/dupfs.c
@@ -14,8 +14,12 @@
 #if HAVE_UNISTD_H
 #include <unistd.h>
 #endif
+#if HAVE_PTHREAD_H
+#include <pthread.h>
+#endif
 #include <time.h>
 #include <string.h>
+#include <assert.h>

 #include "ext2_fs.h"
 #include "ext2fsP.h"
@@ -120,3 +124,148 @@ errout:

 }

+#ifdef HAVE_PTHREAD
+errcode_t ext2fs_clone_fs(ext2_filsys fs, ext2_filsys *dest, unsigned int flags)
+{
+	errcode_t retval;
+	ext2_filsys childfs;
+
+	EXT2_CHECK_MAGIC(fs, EXT2_ET_MAGIC_EXT2FS_FILSYS);
+
+	retval = ext2fs_get_mem(sizeof(struct struct_ext2_filsys), &childfs);
+	if (retval)
+		return retval;
+
+	/* make an exact copy implying lists and memory structures are shared */
+	memcpy(childfs, fs, sizeof(struct struct_ext2_filsys));
+	childfs->inode_map = NULL;
+	childfs->block_map = NULL;
+	childfs->badblocks = NULL;
+	childfs->dblist = NULL;
+
+	pthread_mutex_lock(&fs->refcount_mutex);
+	fs->refcount++;
+	pthread_mutex_unlock(&fs->refcount_mutex);
+
+	if ((flags & EXT2FS_CLONE_INODE) && fs->inode_map) {
+		retval = ext2fs_copy_bitmap(fs->inode_map, &childfs->inode_map);
+		if (retval)
+			return retval;
+		childfs->inode_map->fs = childfs;
+	}
+
+	if ((flags & EXT2FS_CLONE_BLOCK) && fs->block_map) {
+		retval = ext2fs_copy_bitmap(fs->block_map, &childfs->block_map);
+		if (retval)
+			return retval;
+		childfs->block_map->fs = childfs;
+	}
+
+	if ((flags & EXT2FS_CLONE_BADBLOCKS) && fs->badblocks) {
+		retval = ext2fs_badblocks_copy(fs->badblocks, &childfs->badblocks);
+		if (retval)
+			return retval;
+	}
+
+	if ((flags & EXT2FS_CLONE_DBLIST) && fs->dblist) {
+		retval = ext2fs_copy_dblist(fs->dblist, &childfs->dblist);
+		if (retval)
+			return retval;
+		childfs->dblist->fs = childfs;
+	}
+
+	/* icache when NULL will be rebuilt if needed */
+	childfs->icache = NULL;
+
+	childfs->clone_flags = flags;
+	childfs->parent = fs;
+	*dest = childfs;
+
+	return 0;
+}
+
+errcode_t ext2fs_merge_fs(ext2_filsys fs)
+{
+	errcode_t retval = 0;
+	ext2_filsys dest = fs->parent;
+	ext2_filsys src = fs;
+	unsigned int flags = fs->clone_flags;
+
+	pthread_mutex_lock(&fs->refcount_mutex);
+	fs->refcount--;
+	assert(fs->refcount >= 0);
+	pthread_mutex_unlock(&fs->refcount_mutex);
+
+	if ((flags & EXT2FS_CLONE_INODE) && src->inode_map) {
+		if (dest->inode_map == NULL) {
+			dest->inode_map = src->inode_map;
+			src->inode_map = NULL;
+		} else {
+			retval = ext2fs_merge_bitmap(src->inode_map, dest->inode_map, NULL, NULL);
+			if (retval)
+				goto out;
+		}
+		dest->inode_map->fs = dest;
+	}
+
+	if ((flags & EXT2FS_CLONE_BLOCK) && src->block_map) {
+		if (dest->block_map == NULL) {
+			dest->block_map = src->block_map;
+			src->block_map = NULL;
+		} else {
+			retval = ext2fs_merge_bitmap(src->block_map, dest->block_map, NULL, NULL);
+			if (retval)
+				goto out;
+		}
+		dest->block_map->fs = dest;
+	}
+
+	if ((flags & EXT2FS_CLONE_BADBLOCKS) && src->badblocks) {
+		if (dest->badblocks == NULL)
+			retval = ext2fs_badblocks_copy(src->badblocks, &dest->badblocks);
+		else
+			retval = ext2fs_badblocks_merge(src->badblocks, dest->badblocks);
+		if (retval)
+			goto out;
+	}
+
+	if ((flags & EXT2FS_CLONE_DBLIST) && src->dblist) {
+		if (dest->dblist == NULL) {
+			dest->dblist = src->dblist;
+			src->dblist = NULL;
+		} else {
+			retval = ext2fs_merge_dblist(src->dblist, dest->dblist);
+			if (retval)
+				goto out;
+		}
+		dest->dblist->fs = dest;
+	}
+
+	dest->flags |= src->flags;
+	if (!(dest->flags & EXT2_FLAG_VALID))
+		ext2fs_unmark_valid(dest);
+
+	if (src->icache) {
+		ext2fs_free_inode_cache(src->icache);
+		src->icache = NULL;
+	}
+
+out:
+	/* TODO check if io_channel_close is called correctly here? */
+	if (src->io)
+		io_channel_close(src->io);
+
+	if ((flags & EXT2FS_CLONE_INODE) && src->inode_map)
+		ext2fs_free_generic_bmap(src->inode_map);
+	if ((flags & EXT2FS_CLONE_BLOCK) && src->block_map)
+		ext2fs_free_generic_bmap(src->block_map);
+	if ((flags & EXT2FS_CLONE_BADBLOCKS) && src->badblocks)
+		ext2fs_badblocks_list_free(src->badblocks);
+	if ((flags & EXT2FS_CLONE_DBLIST) && src->dblist)
+		ext2fs_free_dblist(src->dblist);
+
+	ext2fs_free_mem(&src);
+
+	return retval;
+}
+#endif
diff --git a/lib/ext2fs/ext2fs.h b/lib/ext2fs/ext2fs.h
index 29e7be9f..6daa7832 100644
--- a/lib/ext2fs/ext2fs.h
+++ b/lib/ext2fs/ext2fs.h
@@ -12,6 +12,10 @@
 #ifndef _EXT2FS_EXT2FS_H
 #define _EXT2FS_EXT2FS_H

+#ifdef HAVE_PTHREAD_H
+#include <pthread.h>
+#endif
+
 #ifdef __GNUC__
 #define EXT2FS_ATTR(x) __attribute__(x)
 #else
@@ -330,6 +334,14 @@ struct struct_ext2_filsys {
 	struct ext2fs_hashmap* block_sha_map;

 	const struct ext2fs_nls_table *encoding;
+
+#ifdef HAVE_PTHREAD
+	struct struct_ext2_filsys *parent;
+	/* TODO do we need refcount? */
+	size_t refcount;
+	pthread_mutex_t refcount_mutex;
+	unsigned int clone_flags;
+#endif
 };

 #if EXT2_FLAT_INCLUDES
@@ -1056,6 +1068,18 @@ extern errcode_t ext2fs_move_blocks(ext2_filsys fs,
 /* check_desc.c */
 extern errcode_t ext2fs_check_desc(ext2_filsys fs);

+#ifdef HAVE_PTHREAD
+/* flags for ext2fs_clone_fs */
+#define EXT2FS_CLONE_BLOCK 			0x0001
+#define EXT2FS_CLONE_INODE 			0x0002
+#define EXT2FS_CLONE_BADBLOCKS 		0x0004
+#define EXT2FS_CLONE_DBLIST			0x0008
+
+extern errcode_t ext2fs_clone_fs(ext2_filsys fs, ext2_filsys *dest,
+								 unsigned int flags);
+extern errcode_t ext2fs_merge_fs(ext2_filsys fs);
+#endif
+
 /* closefs.c */
 extern errcode_t ext2fs_close(ext2_filsys fs);
 extern errcode_t ext2fs_close2(ext2_filsys fs, int flags);
--
2.35.3

[RFC 13/13] tst_libext2fs_pthread: Add libext2fs merge/clone unit tests

[Ritesh Harjani]

This adds a unit tests for libext2fs merge/clone apis and uses pthreads
to test the functionality correctly.

TODO:
We can also add EXT2FS_CLONE_BADBLOCKS and EXT2FS_CLONE_DBLIST test as well
into it.

Signed-off-by: Ritesh Harjani <ritesh.list@gmail.com>
---
 lib/ext2fs/Makefile.in             |  17 +-
 lib/ext2fs/tst_libext2fs_pthread.c | 322 +++++++++++++++++++++++++++++
 2 files changed, 337 insertions(+), 2 deletions(-)
 create mode 100644 lib/ext2fs/tst_libext2fs_pthread.c

diff --git a/lib/ext2fs/Makefile.in b/lib/ext2fs/Makefile.in
index c0694175..5fde9900 100644
--- a/lib/ext2fs/Makefile.in
+++ b/lib/ext2fs/Makefile.in
@@ -229,6 +229,7 @@ SRCS= ext2_err.c \
 	$(srcdir)/tst_libext2fs.c \
 	$(srcdir)/tst_bitmaps_standalone.c \
 	$(srcdir)/tst_bitmaps_pthread.c \
+	$(srcdir)/tst_libext2fs_pthread.c \
 	$(DEBUG_SRCS)
 
 HFILES= bitops.h ext2fs.h ext2_io.h ext2_fs.h ext2_ext_attr.h ext3_extents.h \
@@ -374,6 +375,11 @@ tst_bitmaps_pthread: tst_bitmaps_pthread.o $(STATIC_LIBEXT2FS) $(DEPSTATIC_LIBCO
 	$(Q) $(CC) -o tst_bitmaps_pthread tst_bitmaps_pthread.o $(ALL_LDFLAGS) \
 		$(STATIC_LIBEXT2FS) $(STATIC_LIBCOM_ERR) $(SYSLIBS)
 
+tst_libext2fs_pthread: tst_libext2fs_pthread.o $(STATIC_LIBEXT2FS) $(DEPSTATIC_LIBCOM_ERR)
+	$(E) "	LD $@"
+	$(Q) $(CC) -o tst_libext2fs_pthread tst_libext2fs_pthread.o $(ALL_LDFLAGS) \
+		$(STATIC_LIBEXT2FS) $(STATIC_LIBCOM_ERR) $(SYSLIBS)
+
 ext2_tdbtool: tdbtool.o
 	$(E) "	LD $@"
 	$(Q) $(CC) -o ext2_tdbtool tdbtool.o tdb.o $(ALL_LDFLAGS) $(SYSLIBS)
@@ -546,7 +552,7 @@ fullcheck check:: tst_bitops tst_badblocks tst_iscan tst_types tst_icount \
     tst_super_size tst_types tst_inode_size tst_csum tst_crc32c tst_bitmaps \
     tst_inline tst_inline_data tst_libext2fs tst_sha256 tst_sha512 \
     tst_digest_encode tst_getsize tst_getsectsize tst_bitmaps_standalone \
-	tst_bitmaps_pthread
+	tst_bitmaps_pthread tst_libext2fs_pthread
 	$(TESTENV) ./tst_bitops
 	$(TESTENV) ./tst_badblocks
 	$(TESTENV) ./tst_iscan
@@ -571,6 +577,7 @@ fullcheck check:: tst_bitops tst_badblocks tst_iscan tst_types tst_icount \
 	$(TESTENV) ./tst_digest_encode
 	$(TESTENV) ./tst_bitmaps_standalone
 	$(TESTENV) ./tst_bitmaps_pthread
+	$(TESTENV) ./tst_libext2fs_pthread
 
 installdirs::
 	$(E) "	MKDIR_P $(libdir) $(includedir)/ext2fs"
@@ -606,7 +613,7 @@ clean::
 		tst_bitmaps tst_bitmaps_out tst_extents tst_inline \
 		tst_inline_data tst_inode_size tst_bitmaps_cmd.c \
 		tst_digest_encode tst_sha256 tst_sha512  tst_bitmaps_standalone \
-		tst_bitmaps_pthread \
+		tst_bitmaps_pthread tst_libext2fs_pthread \
 		ext2_tdbtool mkjournal debug_cmds.c tst_cmds.c extent_cmds.c \
 		../libext2fs.a ../libext2fs_p.a ../libext2fs_chk.a \
 		crc32c_table.h gen_crc32ctable tst_crc32c tst_libext2fs \
@@ -1184,6 +1191,12 @@ tst_bitmaps_pthread.o: $(srcdir)/tst_bitmaps_pthread.c $(top_builddir)/lib/confi
  $(srcdir)/ext2_fs.h $(srcdir)/ext3_extents.h $(top_srcdir)/lib/et/com_err.h \
  $(srcdir)/ext2_io.h $(top_builddir)/lib/ext2fs/ext2_err.h \
  $(srcdir)/ext2_ext_attr.h $(srcdir)/hashmap.h $(srcdir)/bitops.h
+tst_libext2fs_pthread.o: $(srcdir)/tst_libext2fs_pthread.c $(top_builddir)/lib/config.h \
+ $(top_builddir)/lib/dirpaths.h $(srcdir)/ext2_fs.h \
+ $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/ext2fs.h \
+ $(srcdir)/ext2_fs.h $(srcdir)/ext3_extents.h $(top_srcdir)/lib/et/com_err.h \
+ $(srcdir)/ext2_io.h $(top_builddir)/lib/ext2fs/ext2_err.h \
+ $(srcdir)/ext2_ext_attr.h $(srcdir)/hashmap.h $(srcdir)/bitops.h
 undo_io.o: $(srcdir)/undo_io.c $(top_builddir)/lib/config.h \
  $(top_builddir)/lib/dirpaths.h $(srcdir)/ext2_fs.h \
  $(top_builddir)/lib/ext2fs/ext2_types.h $(srcdir)/ext2fs.h \
diff --git a/lib/ext2fs/tst_libext2fs_pthread.c b/lib/ext2fs/tst_libext2fs_pthread.c
new file mode 100644
index 00000000..f13bf611
--- /dev/null
+++ b/lib/ext2fs/tst_libext2fs_pthread.c
@@ -0,0 +1,322 @@
+#include "config.h"
+#include <stdio.h>
+#include <string.h>
+#include <assert.h>
+#if HAVE_UNISTD_H
+#include <unistd.h>
+#endif
+#include <fcntl.h>
+#include <time.h>
+#include <sys/stat.h>
+#include <sys/types.h>
+#if HAVE_ERRNO_H
+#include <errno.h>
+#endif
+#if HAVE_PTHREAD
+#include <pthread.h>
+#endif
+
+#include "ext2_fs.h"
+#include "ext2fs.h"
+
+int test_fail = 0;
+ext2_filsys testfs;
+ext2fs_inode_bitmap	inode_used_map;
+ext2fs_block_bitmap block_used_map;
+ext2_filsys childfs[2];
+pthread_t pthread_infos[2];
+
+#define nr_bits 16384
+int nr_threads = 2;
+
+int should_mark_bit()
+{
+	return rand() % 2 == 0;
+}
+
+void setupfs()
+{
+	errcode_t retval;
+	struct ext2_super_block param;
+
+	initialize_ext2_error_table();
+
+	memset(&param, 0, sizeof(param));
+	ext2fs_blocks_count_set(&param, nr_bits);
+	retval = ext2fs_initialize("test fs", EXT2_FLAG_64BITS, &param,
+							   test_io_manager, &testfs);
+	if (retval) {
+		com_err("setup", retval, "while initializing filesystem");
+		exit(1);
+	}
+
+	retval = ext2fs_allocate_tables(testfs);
+	if (retval) {
+		com_err("setup", retval, "while allocating tables for testfs");
+		exit(1);
+	}
+}
+
+void setup_used_bitmaps()
+{
+	int saved_type = testfs->default_bitmap_type;
+	ext2_inode_scan scan;
+	struct ext2_inode inode;
+	ext2_ino_t ino;
+	errcode_t retval;
+	int i;
+
+	testfs->default_bitmap_type = EXT2FS_BMAP64_BITARRAY;
+
+	/* allocate block and inode used bitmaps */
+	retval = ext2fs_allocate_block_bitmap(testfs, "block used map", &block_used_map);
+	if (retval)
+		goto out;
+
+	retval = ext2fs_allocate_inode_bitmap(testfs, "inode used map", &inode_used_map);
+	if (retval)
+		goto out;
+
+	/* setup block and inode used bitmaps */
+	for (i = 1; i < nr_bits; i++) {
+		/*
+		 * we check for testfs->block_map as well since there could be some
+		 * blocks already set as part of the FS metadata.
+		 */
+		if (should_mark_bit() || ext2fs_test_block_bitmap2(testfs->block_map, i)) {
+			ext2fs_mark_block_bitmap2(block_used_map, i);
+		}
+	}
+
+	retval = ext2fs_open_inode_scan(testfs, 8, &scan);
+	if (retval) {
+		com_err("setup_inode_map", retval, "while open inode scan");
+		exit(1);
+	}
+
+	retval = ext2fs_get_next_inode(scan, &ino, &inode);
+	if (retval) {
+		com_err("setup_inode_map", retval, "while getting next inode");
+		exit(1);
+	}
+
+	while (ino) {
+		if (should_mark_bit())
+			ext2fs_mark_inode_bitmap2(inode_used_map, ino);
+
+		retval = ext2fs_get_next_inode(scan, &ino, &inode);
+		if (retval) {
+			com_err("setup_inode_map", retval, "while getting next inode");
+			exit(1);
+		}
+	}
+	ext2fs_close_inode_scan(scan);
+
+	testfs->default_bitmap_type = saved_type;
+	return;
+out:
+	com_err("setup_used_bitmaps", retval, "while setting up bitmaps\n");
+	exit(1);
+}
+
+void setup_childfs()
+{
+	errcode_t retval;
+	int i;
+
+	for (i = 0; i < nr_threads; i++) {
+		retval = ext2fs_clone_fs(testfs, &childfs[i], EXT2FS_CLONE_INODE | EXT2FS_CLONE_BLOCK);
+		if (retval) {
+			com_err("setup_childfs", retval, "while clone testfs for childfs");
+			exit(1);
+		}
+
+		retval = childfs[i]->io->manager->open(childfs[i]->device_name,
+											IO_FLAG_THREADS | IO_FLAG_NOCACHE, &childfs[i]->io);
+		if (retval) {
+			com_err("setup_pthread", retval, "while opening childfs");
+			exit(1);
+		}
+		assert(childfs[i]->parent == testfs);
+	}
+}
+
+void free_childfs()
+{
+	int i;
+
+	for (i = 0; i < nr_threads; i++){
+		ext2fs_free(childfs[i]);
+	}
+}
+
+
+static errcode_t scan_callback(ext2_filsys fs,
+			       ext2_inode_scan scan EXT2FS_ATTR((unused)),
+			       dgrp_t group, void *priv_data)
+{
+	pthread_t id = *((pthread_t *)priv_data);
+
+	printf("%s: Called for group %d via thread %d\n", __func__, group,
+			pthread_equal(pthread_infos[1], id));
+	if (pthread_equal(pthread_infos[0], id)) {
+		if (group >= fs->group_desc_count / 2 - 1)
+			return 1;
+	}
+	return 0;
+}
+
+static void *run_pthread(void *arg)
+{
+	errcode_t retval = 0;
+	int i = 0, start, end;
+	ext2fs_block_bitmap test_block_bitmap;
+	ext2fs_inode_bitmap test_inode_bitmap;
+	ext2_inode_scan scan;
+	struct ext2_inode inode;
+	ext2_ino_t ino;
+	pthread_t id = pthread_self();
+
+	if (pthread_equal(pthread_infos[0], id)) {
+		start = 1;
+		end = nr_bits/2;
+		test_block_bitmap = childfs[0]->block_map;
+		test_inode_bitmap = childfs[0]->inode_map;
+
+		retval = ext2fs_open_inode_scan(childfs[0], 8, &scan);
+		if (retval) {
+			com_err("setup_inode_map", retval, "while open inode scan");
+			exit(1);
+		}
+
+	} else {
+		start = nr_bits / 2 + 1;;
+		end = nr_bits - 1;
+		test_block_bitmap = childfs[1]->block_map;
+		test_inode_bitmap = childfs[1]->inode_map;
+
+		retval = ext2fs_open_inode_scan(childfs[1], 8, &scan);
+		if (retval) {
+			com_err("setup_inode_map", retval, "while open inode scan");
+			exit(1);
+		}
+		ext2fs_inode_scan_goto_blockgroup(scan, testfs->group_desc_count/2);
+	}
+
+	ext2fs_set_inode_callback(scan, scan_callback, &id);
+
+	/* blocks scan */
+	for (i = start; i <= end; i++) {
+		if (ext2fs_test_block_bitmap2(block_used_map, i)) {
+			ext2fs_mark_block_bitmap2(test_block_bitmap, i);
+		}
+	}
+
+	/* inodes scan */
+	retval = ext2fs_get_next_inode(scan, &ino, &inode);
+	if (retval) {
+		com_err("setup_inode_map", retval, "while getting next inode");
+		exit(1);
+	}
+
+	while (ino) {
+		if (ext2fs_test_inode_bitmap2(inode_used_map, ino)) {
+			ext2fs_mark_inode_bitmap2(test_inode_bitmap, ino);
+		}
+
+		retval = ext2fs_get_next_inode(scan, &ino, &inode);
+		if (retval)
+			break;
+	}
+	ext2fs_close_inode_scan(scan);
+	return NULL;
+}
+
+void run_pthreads()
+{
+	errcode_t retval;
+	int i;
+
+	for (i = 0; i < nr_threads; i++) {
+		printf("Starting thread (%d)\n", i);
+		retval = pthread_create(&pthread_infos[i], NULL, &run_pthread, NULL);
+		if (retval) {
+			com_err("run_pthreads", retval, "while pthread_create");
+			exit(1);
+		}
+	}
+
+	for (i = 0; i < nr_threads; i++) {
+		void *status;
+		int ret;
+		retval = pthread_join(pthread_infos[i], &status);
+		if (retval) {
+			com_err("run_pthreads", retval, "while joining pthreads");
+			exit(1);
+
+		}
+		ret = status == NULL ? 0 : *(int*)status;
+		if (ret) {
+			com_err("run_pthreads", ret, "pthread returned error");
+			test_fail++;
+		}
+
+		printf("Closing thread (%d), ret(%d)\n", i, ret);
+	}
+
+	assert(ext2fs_merge_fs(childfs[0]) == 0);
+	assert(ext2fs_merge_fs(childfs[1]) == 0);
+}
+
+void test_bitmaps()
+{
+	errcode_t retval;
+	retval = ext2fs_compare_block_bitmap(testfs->block_map, block_used_map);
+	if (retval) {
+		printf("Block bitmap compare -- NOT OK!! (%ld)\n", retval);
+		test_fail++;
+	}
+
+	printf("Block compare bitmap  -- OK!!\n");
+	retval = ext2fs_compare_inode_bitmap(testfs->inode_map, inode_used_map);
+	if (retval) {
+		printf("Inode bitmap compare -- NOT OK!! (%ld)\n", retval);
+		test_fail++;
+	}
+	printf("Inode compare bitmap  -- OK!!\n");
+}
+
+void free_used_bitmaps()
+{
+	ext2fs_free_block_bitmap(block_used_map);
+	ext2fs_free_inode_bitmap(inode_used_map);
+}
+
+int main(int argc, char *argv[])
+{
+	int i;
+
+#ifndef HAVE_PTHREAD
+	printf("No PTHREAD support, exiting...\n");
+	return 0;
+#endif
+
+	srand(time(0));
+
+	setupfs();
+	setup_used_bitmaps();
+
+	setup_childfs();
+	run_pthreads();
+	test_bitmaps(i);
+
+	if (test_fail)
+		printf("%s: Test libext2fs clone/merge with pthreads NOT OK!!\n", argv[0]);
+	else
+		printf("%s: Test libext2fs clone/merge with pthreads OK!!\n", argv[0]);
+	free_used_bitmaps();
+	free_childfs();
+	ext2fs_free(testfs);
+
+	return test_fail;
+}
-- 
2.35.3