Skip to content

repair: Phase 6 performance improvements

Dave Chinner linux-xfs 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 Latest7 patches 20 repliesIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/7workqueue: bound maximum queue depthlibfrog/workqueue.c libfrog/workqueue.h+43 -36 replies
2/7repair: Protect bad inode list with mutexrepair/dir2.c+21 -112 replies
3/7repair: protect inode chunk tree records with a mutexrepair/incore.h repair/incore_ino.c+38 -03 replies
4/7repair: parallelise phase 6repair/phase6.c+35 -83 replies
5/7repair: don't duplicate names in phase 6repair/phase6.c+29 -724 replies
6/7repair: convert the dir byaddr hash to a radix treelibfrog/radix-tree.c repair/phase6.c+148 -1201 reply
7/7repair: scale duplicate name checking in phase 6.repair/phase6.c+24 -61 reply

Reviews trailers per patch

4 of 7 patches have a Reviewed-by or Acked-by.

PatchDarrick J. Wong
1/7
2/7R-b
3/7R-b
4/7
5/7R-b
6/7R-b
7/7

Trailers given in replies are filled; those carried in the patches from earlier versions are outlined with dashes.

Read the v1 thread

Cover letter [PATCH 0/7] repair: Phase 6 performance improvements

Hi folks

Phase 6 is single threaded, processing a single AG at a time and a single directory inode at a time. Phase 6 if often IO latency bound despite the prefetching it does, resulting in low disk utilisation and high runtimes. The solution for this is the same as phase 3 and 4 - scan multiple AGs at once for directory inodes to process. This patch set enables phase 6 to scan multiple AGS at once, and hence requires concurrent updates of inode records as tehy can be accessed and modified by multiple scanning threads now. We also need to protect the bad inodes list from concurrent access and then we can enable concurrent processing of directories.

However, directory entry checking and reconstruction can also be CPU bound - large directories overwhelm the directory name hash structures because the algorithms have poor scalability - one is O(n
+ n^2), another is O(n^2) when the number of dirents greatly outsizes the hash table sizes. Hence we need to more than just parallelise across AGs - we need to parallelise processing within AGs so that a single large directory doesn't completely serialise processing within an AG. This is done by using bound-depth workqueues to allow inode records to be processed asynchronously as the inode records are fetched from disk.

Further, we need to fix the bad alogrithmic scalability of the in memory directory tracking structures. This is done through a combination of better structures and more appropriate dynamic size choices.

The results on a filesystem with a single 10 million entry directory containing 400MB of directory entry data is as follows:

v5.6.0 (Baseline)

       XFS_REPAIR Summary    Thu Oct 22 12:10:52 2020
Phase           Start           End             Duration
Phase 1:        10/22 12:06:41  10/22 12:06:41
Phase 2:        10/22 12:06:41  10/22 12:06:41
Phase 3:        10/22 12:06:41  10/22 12:07:00  19 seconds
Phase 4:        10/22 12:07:00  10/22 12:07:12  12 seconds
Phase 5:        10/22 12:07:12  10/22 12:07:13  1 second
Phase 6:        10/22 12:07:13  10/22 12:10:51  3 minutes, 38 seconds
Phase 7:        10/22 12:10:51  10/22 12:10:51

Total run time: 4 minutes, 10 seconds

real 4m11.151s
user 4m20.083s
sys 0m14.744s

5.9.0-rc1 + patchset:

        XFS_REPAIR Summary    Thu Oct 22 13:19:02 2020
Phase           Start           End             Duration
Phase 1:        10/22 13:18:09  10/22 13:18:09
Phase 2:        10/22 13:18:09  10/22 13:18:09
Phase 3:        10/22 13:18:09  10/22 13:18:31  22 seconds
Phase 4:        10/22 13:18:31  10/22 13:18:45  14 seconds
Phase 5:        10/22 13:18:45  10/22 13:18:45
Phase 6:        10/22 13:18:45  10/22 13:19:00  15 seconds
Phase 7:        10/22 13:19:00  10/22 13:19:00

Total run time: 51 seconds

real 0m52.375s
user 1m3.739s
sys 0m20.346s

Performance improvements on filesystems with small directories and really fast storage are, at best, modest. The big improvements are seen with either really large directories and/or relatively slow devices that are IO latency bound and can benefit from having more IO in flight at once.

Cheers,

Dave.

Dave Chinner (7):
workqueue: bound maximum queue depth
repair: Protect bad inode list with mutex
repair: protect inode chunk tree records with a mutex
repair: parallelise phase 6
repair: don't duplicate names in phase 6
repair: convert the dir byaddr hash to a radix tree
repair: scale duplicate name checking in phase 6.

 libfrog/radix-tree.c |  46 +++++
 libfrog/workqueue.c  |  42 ++++-
 libfrog/workqueue.h  |   4 +
 repair/dir2.c        |  32 ++--
 repair/incore.h      |  23 +++
 repair/incore_ino.c  |  15 ++
 repair/phase6.c      | 396 +++++++++++++++++++++----------------------
 7 files changed, 338 insertions(+), 220 deletions(-)
Signature · 1 line
2.28.0