On Tue, Jun 20, 2023 at 02:32:15PM -0700, Omar Sandoval wrote:
> From: Omar Sandoval <osandov@xxxxxx>
>
> 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@xxxxxx>
> ---
> 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
>
