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:
> > From: Dave Chinner <dchinner@xxxxxxxxxx>
> >
> > 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@xxxxxxxxxx>
> > Signed-off-by: Dave Chinner <dchinner@xxxxxxxxxx>
> > Signed-off-by: Gao Xiang <hsiangkao@xxxxxxxxxx>
> > ---
> > 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@xxxxxxxxxxxxx
>
