On Thu, Aug 29, 2019 at 08:47:10PM +1000, Dave Chinner wrote:
> From: Dave Chinner <dchinner@xxxxxxxxxx>
>
> When a directory is growing rapidly, new blocks tend to get added at
> the end of the directory. These end up at the end of the freespace
> index, and when the directory gets large finding these new
> freespaces gets expensive. The code does a linear search across the
> frespace index from the first block in the directory to the last,
> hence meaning the newly added space is the last index searched.
>
> Instead, do a reverse order index search, starting from the last
> block and index in the freespace index. This makes most lookups for
> free space on rapidly growing directories O(1) instead of O(N), but
> should not have any impact on random insert workloads because the
> average search length is the same regardless of which end of the
> array we start at.
>
> The result is a major improvement in large directory grow rates:
>
> create time(sec) / rate (files/s)
> File count vanilla Prev commit Patched
> 10k 0.41 / 24.3k 0.42 / 23.8k 0.41 / 24.3k
> 20k 0.74 / 27.0k 0.76 / 26.3k 0.75 / 26.7k
> 100k 3.81 / 26.4k 3.47 / 28.8k 3.27 / 30.6k
> 200k 8.58 / 23.3k 7.19 / 27.8k 6.71 / 29.8k
> 1M 85.69 / 11.7k 48.53 / 20.6k 37.67 / 26.5k
> 2M 280.31 / 7.1k 130.14 / 15.3k 79.55 / 25.2k
> 10M 3913.26 / 2.5k 552.89 / 18.1k
>
> Signed-Off-By: Dave Chinner <dchinner@xxxxxxxxxx>
Heh, neat.
Reviewed-by: Darrick J. Wong <darrick.wong@xxxxxxxxxx>
--D
> ---
> fs/xfs/libxfs/xfs_dir2_node.c | 13 +++++--------
> 1 file changed, 5 insertions(+), 8 deletions(-)
>
> diff --git a/fs/xfs/libxfs/xfs_dir2_node.c b/fs/xfs/libxfs/xfs_dir2_node.c
> index a81f56d9e538..705c4f562758 100644
> --- a/fs/xfs/libxfs/xfs_dir2_node.c
> +++ b/fs/xfs/libxfs/xfs_dir2_node.c
> @@ -1745,10 +1745,11 @@ xfs_dir2_node_find_freeblk(
> struct xfs_inode *dp = args->dp;
> struct xfs_trans *tp = args->trans;
> struct xfs_buf *fbp = NULL;
> + xfs_dir2_db_t firstfbno;
> xfs_dir2_db_t lastfbno;
> xfs_dir2_db_t ifbno = -1;
> xfs_dir2_db_t dbno = -1;
> - xfs_dir2_db_t fbno = -1;
> + xfs_dir2_db_t fbno;
> xfs_fileoff_t fo;
> __be16 *bests = NULL;
> int findex = 0;
> @@ -1780,7 +1781,6 @@ xfs_dir2_node_find_freeblk(
> * We'll start at the beginning of the freespace entries.
> */
> ifbno = fblk->blkno;
> - fbno = ifbno;
> xfs_trans_brelse(tp, fbp);
> fbp = NULL;
> fblk->bp = NULL;
> @@ -1794,12 +1794,9 @@ xfs_dir2_node_find_freeblk(
> if (error)
> return error;
> lastfbno = xfs_dir2_da_to_db(args->geo, (xfs_dablk_t)fo);
> + firstfbno = xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET);
>
> - /* If we haven't get a search start block, set it now */
> - if (fbno == -1)
> - fbno = xfs_dir2_byte_to_db(args->geo, XFS_DIR2_FREE_OFFSET);
> -
> - for ( ; fbno < lastfbno; fbno++) {
> + for (fbno = lastfbno - 1; fbno >= firstfbno; fbno--) {
> /* If it's ifbno we already looked at it. */
> if (fbno == ifbno)
> continue;
> @@ -1822,7 +1819,7 @@ xfs_dir2_node_find_freeblk(
> dp->d_ops->free_hdr_from_disk(&freehdr, free);
>
> /* Scan the free entry array for a large enough free space. */
> - for (findex = 0; findex < freehdr.nvalid; findex++) {
> + for (findex = freehdr.nvalid - 1; findex >= 0; findex--) {
> if (be16_to_cpu(bests[findex]) != NULLDATAOFF &&
> be16_to_cpu(bests[findex]) >= length) {
> dbno = freehdr.firstdb + findex;
> --
> 2.23.0.rc1
>
