On Wed, Mar 31, 2021 at 09:26:42AM +1100, Dave Chinner wrote:

On Tue, Mar 30, 2021 at 10:25:26PM +0800, Gao Xiang wrote:

quoted

From: Dave Chinner <redacted>

To enable phase 6 parallelisation, we need to protect the bad inode
list from concurrent modification and/or access. Wrap it with a
mutex and clean up the nasty typedefs.

Reviewed-by: Darrick J. Wong <djwong@kernel.org>
Signed-off-by: Dave Chinner <redacted>
Signed-off-by: Gao Xiang <redacted>
---
 repair/dir2.c | 19 ++++++++++++++-----
 1 file changed, 14 insertions(+), 5 deletions(-)

diff --git a/repair/dir2.c b/repair/dir2.c
index b6a8a5c40ae4..c1d262fb1207 100644
--- a/repair/dir2.c
+++ b/repair/dir2.c

@@ -26,6 +26,7 @@ struct dir2_bad {
 };
 
 static struct dir2_bad	dir2_bad;
+pthread_mutex_t		dir2_bad_lock = PTHREAD_MUTEX_INITIALIZER;
 
 static void
 dir2_add_badlist(

@@ -33,6 +34,7 @@ dir2_add_badlist(
 {
 	xfs_ino_t	*itab;
 
+	pthread_mutex_lock(&dir2_bad_lock);
 	itab = realloc(dir2_bad.itab, (dir2_bad.nr + 1) * sizeof(xfs_ino_t));
 	if (!ino) {
 		do_error(

@@ -42,18 +44,25 @@ _("malloc failed (%zu bytes) dir2_add_badlist:ino %" PRIu64 "\n"),
 	}
 	itab[dir2_bad.nr++] = ino;
 	dir2_bad.itab = itab;
+	pthread_mutex_unlock(&dir2_bad_lock);

Putting a global mutex around a memory allocation like this will
really hurt concurrency. This turns the add operation into a very
complex operation instead of the critical section being just a few
instructions long.

The existing linked list code is far more efficient in this case
because the allocation of the structure tracking the bad inode is
done outside the global lock, and only the list_add() operation is
done within the critical section.

I agree with your conclusion here and actually realized the problem
at that time.

Again, an AVL or radix tree can do the tracking structure allocation
outside the add operation, and with an AVL tree there are no
allocations needed to do the insert operation. A radix tree will
amortise the allocations its needs over many inserts that don't need
allocation. However, I'd be tending towards using an AVL tree here
over a radix tree because bad inodes will be sparse and that's the
worst case for radix tree indexing w.r.t to requiring allocation
during insert...

Yeah, I saw some AVL infrastructure, yet AVL needs amortise insert/lookup
O(logn). Anyway, let me try use ACL instead and do some profile.

Thanks,
Gao Xiang

Cheers,

Dave.
-- 
Dave Chinner
david@fromorbit.com