| Message ID | 20210330142531.19809-4-hsiangkao@aol.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | repair: Phase 6 performance improvements | expand |
On Tue, Mar 30, 2021 at 10:25:26PM +0800, Gao Xiang wrote: > From: Dave Chinner <dchinner@redhat.com> > > 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 <dchinner@redhat.com> > Signed-off-by: Gao Xiang <hsiangkao@redhat.com> > --- > 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. 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... Cheers, Dave.
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@redhat.com> > > > > 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 <dchinner@redhat.com> > > Signed-off-by: Gao Xiang <hsiangkao@redhat.com> > > --- > > 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 >
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); } bool dir2_is_badino( xfs_ino_t ino) { - unsigned int i; + unsigned int i; + bool ret = false; - for (i = 0; i < dir2_bad.nr; ++i) - if (dir2_bad.itab[i] == ino) - return true; - return false; + pthread_mutex_lock(&dir2_bad_lock); + for (i = 0; i < dir2_bad.nr; ++i) { + if (dir2_bad.itab[i] == ino) { + ret = true; + break; + } + } + pthread_mutex_unlock(&dir2_bad_lock); + return ret; } /*