Received-SPF: pass (google.com: domain of linux-ext4-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
From:   Ritesh Harjani <ritesh.list@gmail.com>
To:     Theodore Ts'o <tytso@mit.edu>
Cc:     Harshad Shirwadkar <harshadshirwadkar@gmail.com>,
        Andreas Dilger <adilger@dilger.ca>,
        linux-ext4 <linux-ext4@vger.kernel.org>,
        Ritesh Harjani <ritesh.list@gmail.com>
Subject: [RFC 06/13] blkmap64_ba: Implement initial implementation of merge bitmaps
Date:   Mon,  4 Jul 2022 12:36:55 +0530
Message-Id: <2cd087afb18522029158f537edad49cb3f435e88.1656912918.git.ritesh.list@gmail.com>
In-Reply-To: <cover.1656912918.git.ritesh.list@gmail.com>
References: <cover.1656912918.git.ritesh.list@gmail.com>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Precedence: bulk

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