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 [thread overview]
Message-ID: <01e72f626dcebdb8f0a78b53e4cd093357d82787.1667822611.git.ritesh.list@gmail.com> (raw)
In-Reply-To: <cover.1667822611.git.ritesh.list@gmail.com>
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
next prev parent reply other threads:[~2022-11-07 12:22 UTC|newest]
Thread overview: 104+ messages / expand[flat|nested] mbox.gz Atom feed top
2022-11-07 12:20 [RFCv1 00/72] e2fsprogs: Parallel fsck support Ritesh Harjani (IBM)
2022-11-07 12:20 ` [RFCv1 01/72] e2fsck: Fix unbalanced mutex unlock for BOUNCE_MTX Ritesh Harjani (IBM)
2022-11-17 16:02 ` Theodore Ts'o
2022-11-17 18:45 ` Ritesh Harjani (IBM)
2022-11-18 10:34 ` Andreas Dilger
2022-11-18 11:37 ` Ritesh Harjani (IBM)
2022-11-18 13:20 ` Andreas Dilger
2022-11-19 3:46 ` Ritesh Harjani (IBM)
2023-01-24 16:40 ` Theodore Ts'o
2022-11-07 12:20 ` [RFCv1 02/72] gen_bitmaps: Fix ext2fs_compare_generic_bmap/bitmap logic Ritesh Harjani (IBM)
2022-11-23 5:04 ` Andreas Dilger
2023-01-24 16:59 ` Theodore Ts'o
2022-11-07 12:20 ` [RFCv1 03/72] blkmap64_ba: Add common helper for bits size calculation Ritesh Harjani (IBM)
2022-11-18 10:40 ` Andreas Dilger
2022-11-07 12:20 ` [RFCv1 04/72] badblocks: Remove unused badblocks_flags Ritesh Harjani (IBM)
2022-11-18 13:26 ` Andreas Dilger
2022-11-07 12:20 ` Ritesh Harjani (IBM) [this message]
2022-11-18 13:31 ` [RFCv1 05/72] badblocks: Add badblocks merge logic Andreas Dilger
2022-11-07 12:20 ` [RFCv1 06/72] dblist: add dblist " Ritesh Harjani (IBM)
2022-11-18 13:34 ` Andreas Dilger
2022-11-07 12:20 ` [RFCv1 07/72] libext2fs: Add rbtree bitmap " Ritesh Harjani (IBM)
2022-11-07 12:20 ` [RFCv1 08/72] libext2fs: Add bitmaps merge ops Ritesh Harjani (IBM)
2022-11-18 13:36 ` Andreas Dilger
2022-11-07 12:20 ` [RFCv1 09/72] libext2fs: Add flush cleanup API Ritesh Harjani (IBM)
2022-11-18 13:39 ` Andreas Dilger
2022-11-07 12:20 ` [RFCv1 10/72] libext2fs: merge icounts after thread finishes Ritesh Harjani (IBM)
2022-11-18 13:40 ` Andreas Dilger
2022-11-07 12:20 ` [RFCv1 11/72] libext2fs: merge quota context after threads finish Ritesh Harjani (IBM)
2022-11-18 13:42 ` Andreas Dilger
2022-11-07 12:21 ` [RFCv1 12/72] libext2fs: dupfs: Add fs clone & merge api Ritesh Harjani (IBM)
2022-11-18 19:46 ` Andreas Dilger
2022-11-19 5:02 ` Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 13/72] tst_badblocks: Add unit test to verify badblocks list " Ritesh Harjani (IBM)
2022-12-12 20:35 ` Andreas Dilger
2022-11-07 12:21 ` [RFCv1 14/72] tst_bitmaps_standalone: Add copy and merge bitmaps test Ritesh Harjani (IBM)
2022-12-12 20:40 ` Andreas Dilger
2022-12-14 5:12 ` Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 15/72] tst_bitmaps_pthread: Add merge bitmaps test using pthreads Ritesh Harjani (IBM)
2022-12-14 21:15 ` Andreas Dilger
2022-11-07 12:21 ` [RFCv1 16/72] tst_libext2fs_pthread: Add libext2fs merge/clone unit tests Ritesh Harjani (IBM)
2022-12-14 21:17 ` Andreas Dilger
2022-11-07 12:21 ` [RFCv1 17/72] libext2fs: Add support for ext2fs_test_block_bitmap_range2_valid() Ritesh Harjani (IBM)
2022-12-14 21:21 ` Andreas Dilger
2022-11-07 12:21 ` [RFCv1 18/72] libext2fs: Add support to get average group count Ritesh Harjani (IBM)
2022-12-14 21:24 ` Andreas Dilger
2022-11-07 12:21 ` [RFCv1 19/72] libext2fs: Misc fixes for struct_ext2_filsys Ritesh Harjani (IBM)
2022-12-14 21:22 ` Andreas Dilger
2022-11-07 12:21 ` [RFCv1 20/72] libext2fs: avoid too much memory allocation in case fs_num_threads Ritesh Harjani (IBM)
2022-11-18 13:37 ` Andreas Dilger
2022-11-07 12:21 ` [RFCv1 21/72] e2fsck: add -m option for multithread Ritesh Harjani (IBM)
2022-12-14 21:32 ` Andreas Dilger
2022-11-07 12:21 ` [RFCv1 22/72] e2fsck: copy context when using multi-thread fsck Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 23/72] e2fsck: create logs for multi-threads Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 24/72] e2fsck: configure one pfsck thread Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 25/72] e2fsck: Add e2fsck_pass1_thread_join return value Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 26/72] e2fsck: Use merge/clone apis of libext2fs Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 27/72] e2fsck: Add e2fsck_pass1_merge_bitmap() api Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 28/72] e2fsck: Add asserts in open_channel_fs Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 29/72] e2fsck: add start/end group for thread Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 30/72] e2fsck: split groups to different threads Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 31/72] e2fsck: print thread log properly Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 32/72] e2fsck: do not change global variables Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 33/72] e2fsck: optimize the inserting of dir_info_db Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 34/72] e2fsck: merge dir_info after thread finishes Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 35/72] e2fsck: rbtree bitmap for dir Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 36/72] e2fsck: merge icounts after thread finishes Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 37/72] e2fsck: add debug codes for multiple threads Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 38/72] e2fsck: merge counts after threads finish Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 39/72] e2fsck: merge dx_dir_info " Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 40/72] e2fsck: merge dirs_to_hash when " Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 41/72] e2fsck: merge context flags properly Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 42/72] e2fsck: merge quota context after threads finish Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 43/72] e2fsck: serialize fix operations Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 44/72] e2fsck: move some fixes out of parallel pthreads Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 45/72] e2fsck: split and merge invalid bitmaps Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 46/72] e2fsck: merge EA blocks properly Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 47/72] e2fsck: kickoff mutex lock for block found map Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 48/72] e2fsck: allow admin specify number of threads Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 49/72] e2fsck: adjust " Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 50/72] e2fsck: fix readahead for pfsck of pass1 Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 51/72] e2fsck: merge options after threads finish Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 52/72] e2fsck: reset lost_and_found " Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 53/72] e2fsck: merge extent depth count " Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 54/72] e2fsck: simplify e2fsck context merging codes Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 55/72] e2fsck: set E2F_FLAG_ALLOC_OK after threads Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 56/72] e2fsck: wait fix thread finish before checking Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 57/72] e2fsck: cleanup e2fsck_pass1_thread_join() Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 58/72] e2fsck: make default smallest RA size to 1M Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 59/72] e2fsck: update mmp block in one thread Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 60/72] e2fsck: reset @inodes_to_rebuild if restart Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 61/72] tests: add pfsck test Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 62/72] e2fsck: fix memory leaks with pfsck enabled Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 63/72] e2fsck: misc cleanups for pfsck Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 64/72] e2fsck: propagate number of threads Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 65/72] e2fsck: Annotating fields in e2fsck_struct Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 66/72] e2fsck: merge casefolded dir lists after thread finish Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 67/72] sec: support encrypted files handling in pfsck mode Ritesh Harjani (IBM)
2022-11-07 19:22 ` Eric Biggers
2022-11-07 12:21 ` [RFCv1 68/72] e2fsck: Fix io->align assert check Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 69/72] e2fsck: Fix double free of inodes_to_process Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 70/72] e2fsck: Fix and simplify update_mmp in case of pfsck Ritesh Harjani (IBM)
2022-11-07 12:21 ` [RFCv1 71/72] e2fsck: Make threads call log_out after pthread_join Ritesh Harjani (IBM)
2022-11-07 12:22 ` [RFCv1 72/72] tests/f_multithread: Fix f_multithread related tests Ritesh Harjani (IBM)
[not found] ` <B4ED1C86-D3EC-4A0A-97B3-CFCB46617E1A@dilger.ca>
2022-11-19 5:39 ` [RFCv1 00/72] e2fsprogs: Parallel fsck support Ritesh Harjani
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=01e72f626dcebdb8f0a78b53e4cd093357d82787.1667822611.git.ritesh.list@gmail.com \
--to=ritesh.list@gmail.com \
--cc=adilger.kernel@dilger.ca \
--cc=harshadshirwadkar@gmail.com \
--cc=linux-ext4@vger.kernel.org \
--cc=lixi@ddn.com \
--cc=tytso@mit.edu \
--cc=wshilong@ddn.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).