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>
Fri, 17 Jan 2025 02:23:16 +0000 (13:23 +1100)
commitca2a6dcaab75cfdfdf3291fbdb31df6a9149e41f
tree3e402fb58c049b06f8123f3bf172bd32324f7d4d
parent7a6bd1ac1ecceb08067143b174bde5f480ccf9e9
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