Re: [PATCH 5/6] xfs: don't try redundant allocations in xfs_rtallocate_extent_near()

["Darrick J. Wong" <djwong@kernel.org>]

On Tue, Jun 20, 2023 at 02:32:15PM -0700, Omar Sandoval wrote:
> From: Omar Sandoval <osandov@fb.com>
> 
> xfs_rtallocate_extent_near() tries to find a free extent as close to a
> target bitmap block given by bbno as possible, which may be before or
> after bbno. Searching backwards has a complication: the realtime summary
> accounts for free space _starting_ in a bitmap block, but not straddling
> or ending in a bitmap block. So, when the negative search finds a free
> extent in the realtime summary, in order to end up closer to the target,
> it looks for the end of the free extent. For example, if bbno - 2 has a
> free extent, then it will check bbno - 1, then bbno - 2. But then if
> bbno - 3 has a free extent, it will check bbno - 1 again, then bbno - 2
> again, and then bbno - 3. This results in a quadratic loop, which is
> completely pointless since the repeated checks won't find anything new.
> 
> Fix it by remembering where we last checked up to and continue from
> there. This also obviates the need for a check of the realtime summary.
> 
> Signed-off-by: Omar Sandoval <osandov@fb.com>
> ---
>  fs/xfs/xfs_rtalloc.c | 46 +++-----------------------------------------
>  1 file changed, 3 insertions(+), 43 deletions(-)
> 
> diff --git a/fs/xfs/xfs_rtalloc.c b/fs/xfs/xfs_rtalloc.c
> index d079dfb77c73..4d9d0be2e616 100644
> --- a/fs/xfs/xfs_rtalloc.c
> +++ b/fs/xfs/xfs_rtalloc.c
> @@ -468,6 +468,7 @@ xfs_rtallocate_extent_near(
>  	}
>  	bbno = XFS_BITTOBLOCK(mp, bno);
>  	i = 0;
> +	j = -1;
>  	ASSERT(minlen != 0);
>  	log2len = xfs_highbit32(minlen);
>  	/*
> @@ -518,31 +519,11 @@ xfs_rtallocate_extent_near(
>  			else {		/* i < 0 */
>  				/*
>  				 * Loop backwards through the bitmap blocks from
> -				 * the starting point-1 up to where we are now.
> +				 * where we last checked up to where we are now.

I find this comment a bit unclear -- aren't we looping backwards from
where we last checked *downwards*?  I was reading "where we are now" to
mean @i, which contains a negative value.

"When @i is negative, we try to find a free extent that starts in the
bitmap blocks before bbno.  Starting from the last bitmap block that we
checked in a negative scan (initially bbno - 1) and walking downwards
towards (bbno + i), try to allocate an extent of satisfactory length."

But now having worked my way through that, now I'm wondering what the j
loop is even doing.  Doesn't the sequence of blocks that we call
xfs_rtallocate_extent_block on alternate backwards and forwards?  e.g.

Try to find a satisfactory free extent that starts in:

bbno
bbno + 1
bbno - 1
bbno + 2
bbno - 2
...
etc?

Why not avoid the loop entirely by calling xfs_rtallocate_extent_block
on bbno + i once before switching back to positive @i?  What am I
missing here?

>  				 * There should be an extent which ends in this
>  				 * bitmap block and is long enough.
>  				 */
> -				for (j = -1; j > i; j--) {
> -					/*
> -					 * Grab the summary information for
> -					 * this bitmap block.
> -					 */
> -					error = xfs_rtany_summary(mp, tp,
> -						log2len, mp->m_rsumlevels - 1,
> -						bbno + j, rtbufc, &maxlog);
> -					if (error) {
> -						return error;
> -					}
> -					/*
> -					 * If there's no extent given in the
> -					 * summary that means the extent we
> -					 * found must carry over from an
> -					 * earlier block.  If there is an
> -					 * extent given, we've already tried
> -					 * that allocation, don't do it again.
> -					 */
> -					if (maxlog >= 0)
> -						continue;
> +				for (; j >= i; j--) {

Changing the j > i to j >= i is what obviates the extra call to
xfs_rtallocate_extent_block below, correct?

--D

>  					error = xfs_rtallocate_extent_block(mp,
>  						tp, bbno + j, minlen, maxavail,
>  						len, &n, rtbufc, prod, &r);
> @@ -557,27 +538,6 @@ xfs_rtallocate_extent_near(
>  						return 0;
>  					}
>  				}
> -				/*
> -				 * There weren't intervening bitmap blocks
> -				 * with a long enough extent, or the
> -				 * allocation didn't work for some reason
> -				 * (i.e. it's a little * too short).
> -				 * Try to allocate from the summary block
> -				 * that we found.
> -				 */
> -				error = xfs_rtallocate_extent_block(mp, tp,
> -					bbno + i, minlen, maxavail, len, &n,
> -					rtbufc, prod, &r);
> -				if (error) {
> -					return error;
> -				}
> -				/*
> -				 * If it works, return the extent.
> -				 */
> -				if (r != NULLRTBLOCK) {
> -					*rtblock = r;
> -					return 0;
> -				}
>  			}
>  		}
>  		/*
> -- 
> 2.41.0
>