Whamcloud - gitweb
LU-16972 e2fsck: use rb-tree to track EA reference counts
authorLi Dongyang <dongyangli@ddn.com>
Wed, 26 Jul 2023 05:20:54 +0000 (15:20 +1000)
committerLi Dongyang <dongyangli@ddn.com>
Tue, 28 May 2024 05:53:20 +0000 (15:53 +1000)
commit22dd0392953aa669d93c5fab5884410f21ecd813
treec40070c5728137d108e5d5fc659e23de03748643
parentc9275d48974a471e03587474b844e8679dd72b33
LU-16972 e2fsck: use rb-tree to track EA reference counts

Using the sorted array to track the EA blocks and
its refs is not scalable.
When the file system has a huge number of EA blocks,
pass1 scanning could not be finished within a reasonable
time, as 95%+ of CPU time is spent in memmove() when
trying to enlarge the the sorted array.

On a file system with 20 million EA blocks on an NVMe device
pass1 time taken:
without patch:
time: 2014.78/1838.70/19.91
with patch:
time: 45.17/20.17/20.19

Change-Id: I6dc1ee3037dbf7a48deb610514af1f0e35a5a397
Signed-off-by: Li Dongyang <dongyangli@ddn.com>
Reviewed-on: https://review.whamcloud.com/c/tools/e2fsprogs/+/51729
Tested-by: jenkins <devops@whamcloud.com>
Tested-by: Maloo <maloo@whamcloud.com>
Reviewed-by: Andreas Dilger <adilger@whamcloud.com>
e2fsck/e2fsck.h
e2fsck/ea_refcount.c
e2fsck/pass1.c