Re: [PATCH 3/4] xfs: speed up rmap lookups by using non-overlapped lookups when possible

[Dave Chinner <david@fromorbit.com>]

On Thu, Apr 14, 2022 at 03:54:16PM -0700, Darrick J. Wong wrote:
> From: Darrick J. Wong <djwong@kernel.org>
> 
> Reverse mapping on a reflink-capable filesystem has some pretty high
> overhead when performing file operations.  This is because the rmap
> records for logically and physically adjacent extents might not be
> adjacent in the rmap index due to data block sharing.  As a result, we
> use expensive overlapped-interval btree search, which walks every record
> that overlaps with the supplied key in the hopes of finding the record.
> 
> However, profiling data shows that when the index contains a record that
> is an exact match for a query key, the non-overlapped btree search
> function can find the record much faster than the overlapped version.
> Try the non-overlapped lookup first, which will make scrub run much
> faster.
> 
> Signed-off-by: Darrick J. Wong <djwong@kernel.org>
> ---
>  fs/xfs/libxfs/xfs_rmap.c |   38 ++++++++++++++++++++++++++++++++------
>  1 file changed, 32 insertions(+), 6 deletions(-)
> 
> 
> diff --git a/fs/xfs/libxfs/xfs_rmap.c b/fs/xfs/libxfs/xfs_rmap.c
> index 3eea8056e7bc..5aa94deb3afd 100644
> --- a/fs/xfs/libxfs/xfs_rmap.c
> +++ b/fs/xfs/libxfs/xfs_rmap.c
> @@ -402,12 +402,38 @@ xfs_rmap_lookup_le_range(
>  	info.irec = irec;
>  	info.stat = stat;
>  
> -	trace_xfs_rmap_lookup_le_range(cur->bc_mp,
> -			cur->bc_ag.pag->pag_agno, bno, 0, owner, offset, flags);
> -	error = xfs_rmap_query_range(cur, &info.high, &info.high,
> -			xfs_rmap_lookup_le_range_helper, &info);
> -	if (error == -ECANCELED)
> -		error = 0;
> +	trace_xfs_rmap_lookup_le_range(cur->bc_mp, cur->bc_ag.pag->pag_agno,
> +			bno, 0, owner, offset, flags);
> +
> +	/*
> +	 * Historically, we always used the range query to walk every reverse
> +	 * mapping that could possibly overlap the key that the caller asked
> +	 * for, and filter out the ones that don't.  That is very slow when
> +	 * there are a lot of records.
> +	 *
> +	 * However, there are two scenarios where the classic btree search can
> +	 * produce correct results -- if the index contains a record that is an
> +	 * exact match for the lookup key; and if there are no other records
> +	 * between the record we want and the key we supplied.
> +	 *
> +	 * As an optimization, try a non-overlapped lookup first.  This makes
> +	 * scrub run much faster on most filesystems because bmbt records are
> +	 * usually an exact match for rmap records.  If we don't find what we
> +	 * want, we fall back to the overlapped query.
> +	 */
> +	error = xfs_rmap_lookup_le(cur, bno, owner, offset, flags, irec, stat);
> +	if (error)
> +		return error;
> +	if (*stat) {
> +		*stat = 0;
> +		xfs_rmap_lookup_le_range_helper(cur, irec, &info);
> +	}
> +	if (!(*stat)) {
> +		error = xfs_rmap_query_range(cur, &info.high, &info.high,
> +				xfs_rmap_lookup_le_range_helper, &info);
> +		if (error == -ECANCELED)
> +			error = 0;
> +	}

Ok, I can see what this is doing, but the code is nasty - zeroing
info.stat via *stat = 0, then having
xfs_rmap_lookup_le_range_helper() modify *stat via info.stat and
then relying on that implicit update to skip the very next if
(!(*stat)) clause is not very nice.

xfs_rmap_lookup_le_range_helper() returns -ECANCELED when it's
found a match, so we can use this rather than relying on *stat
to determine what to do:

	error = xfs_rmap_lookup_le(cur, bno, owner, offset, flags, irec, stat);
	if (error)
		return error;

	info.irec = irec;
	info.stat = 0;
	if (*stat)
		error = xfs_rmap_lookup_le_range_helper(cur, irec, &info);
	if (!error)
		error = xfs_rmap_query_range(cur, &info.high, &info.high,
				xfs_rmap_lookup_le_range_helper, &info);
	if (error == -ECANCELED)
		error = 0;

	*stat = info.stat;
....

Cheers,

Dave.

>  	if (*stat)
>  		trace_xfs_rmap_lookup_le_range_result(cur->bc_mp,
>  				cur->bc_ag.pag->pag_agno, irec->rm_startblock,
> 
> 

-- 
Dave Chinner
david@fromorbit.com