diff mbox series

[RFCv1,05/72] badblocks: Add badblocks merge logic

Message ID 01e72f626dcebdb8f0a78b53e4cd093357d82787.1667822611.git.ritesh.list@gmail.com
State Under Review
Delegated to: Theodore Ts'o
Headers show
Series e2fsprogs: Parallel fsck support | expand

Commit Message

Ritesh Harjani (IBM) Nov. 7, 2022, 12:20 p.m. UTC 
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(+)

Comments

Andreas Dilger Nov. 18, 2022, 1:31 p.m. UTC | #1 
On Nov 7, 2022, at 06:22, Ritesh Harjani (IBM) <ritesh.list@gmail.com> wrote:
> 
> 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>

Reviewed-by: Andreas Dilger <adilger@dilger.ca>

> ---
> 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
>
diff mbox series

Patch

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);