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 (IBM)" <ritesh.list@gmail.com>
To:     Theodore Ts'o <tytso@mit.edu>
Cc:     linux-ext4@vger.kernel.org,
        Harshad Shirwadkar <harshadshirwadkar@gmail.com>,
        Wang Shilong <wshilong@ddn.com>,
        Andreas Dilger <adilger.kernel@dilger.ca>,
        Li Xi <lixi@ddn.com>, Ritesh Harjani <ritesh.list@gmail.com>
Subject: [RFCv1 05/72] badblocks: Add badblocks merge logic
Date:   Mon,  7 Nov 2022 17:50:53 +0530
Message-Id: <01e72f626dcebdb8f0a78b53e4cd093357d82787.1667822611.git.ritesh.list@gmail.com>
In-Reply-To: <cover.1667822611.git.ritesh.list@gmail.com>
References: <cover.1667822611.git.ritesh.list@gmail.com>
MIME-Version: 1.0
Content-Transfer-Encoding: 8bit
Precedence: bulk

From: Wang Shilong <wshilong@ddn.com>

Add badblocks merge logic

Signed-off-by: Wang Shilong <wshilong@ddn.com>
Signed-off-by: Ritesh Harjani (IBM) <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 345168e0..36794e69 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 9cc994b1..18dddc2c 100644
--- a/lib/ext2fs/ext2fs.h
+++ b/lib/ext2fs/ext2fs.h
@@ -845,6 +845,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.37.3