linux-kernel - Re: [PATCH] xfs: Reduce unnecessary searches when searching for the best extents

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <ZxtEJN/dTw9JipJe@dread.disaster.area>
Date: Fri, 25 Oct 2024 18:09:24 +1100
From: Dave Chinner <david@...morbit.com>
To: Chi Zhiling <chizhiling@....com>
Cc: cem@...nel.org, djwong@...nel.org, linux-xfs@...r.kernel.org,
	linux-kernel@...r.kernel.org, Chi Zhiling <chizhiling@...inos.cn>
Subject: Re: [PATCH] xfs: Reduce unnecessary searches when searching for the
 best extents

On Fri, Oct 25, 2024 at 10:33:20AM +0800, Chi Zhiling wrote:
> From: Chi Zhiling <chizhiling@...inos.cn>
> 
> Recently, we found that the CPU spent a lot of time in
> xfs_alloc_ag_vextent_size when the filesystem has millions of fragmented
> spaces.
> 
> The reason is that we conducted much extra searching for extents that
> could not yield a better result, and these searches would cost a lot of
> time when there were millions of extents to search through. Even if we
> get the same result length, we don't switch our choice to the new one,
> so we can definitely terminate the search early.
> 
> Since the result length cannot exceed the found length, when the found
> length equals the best result length we already have, we can conclude
> the search.
> 
> We did a test in that filesystem:
> [root@...alhost ~]# xfs_db -c freesp /dev/vdb
>    from      to extents  blocks    pct
>       1       1     215     215   0.01
>       2       3  994476 1988952  99.99

Ok, so you have *badly* fragmented free space. That going to cause
lots more problems than only "allocation searches take a long
time". e.g. you can't allocate inodes in a AG that is fragmented
this badly - not even sparse inode clusters....

> Before this patch:
>  0)               |  xfs_alloc_ag_vextent_size [xfs]() {
>  0) * 15597.94 us |  }
> 
> After this patch:
>  0)               |  xfs_alloc_ag_vextent_size [xfs]() {
>  0)   19.176 us    |  }

Yup, that's a good improvement.


> Signed-off-by: Chi Zhiling <chizhiling@...inos.cn>
> ---
>  fs/xfs/libxfs/xfs_alloc.c | 2 +-
>  1 file changed, 1 insertion(+), 1 deletion(-)
> 
> diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c
> index 04f64cf9777e..22bdbb3e9980 100644
> --- a/fs/xfs/libxfs/xfs_alloc.c
> +++ b/fs/xfs/libxfs/xfs_alloc.c
> @@ -1923,7 +1923,7 @@ xfs_alloc_ag_vextent_size(
>  				error = -EFSCORRUPTED;
>  				goto error0;
>  			}
> -			if (flen < bestrlen)
> +			if (flen <= bestrlen)
>  				break;
>  			busy = xfs_alloc_compute_aligned(args, fbno, flen,
>  					&rbno, &rlen, &busy_gen);

Yup, I think that works fine. We aren't caring about using locality
as a secondary search key so as soon as we have a candidate extent
of a length that that the remaining extents in the free space btree
can't improve on, we are done.

Nice work!

Reviewed-by: Dave Chinner <dchinner@...hat.com>

-- 
Dave Chinner
david@...morbit.com