On Wed, Jul 12, 2023 at 04:34:03PM -0700, Darrick J. Wong wrote:
> 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.
Yes, "where we last checked down to where we are now" might be better
wording.
> "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 are two ways I can think of to remove the j loop, so I'll address
both.
If you mean: make the i >= 0 and i < 0 branches the same and call
xfs_rtallocate_extent_block() if and only if xfs_rtany_summary() returns
a non-zero maxlog, i.e.:
diff --git a/fs/xfs/xfs_rtalloc.c b/fs/xfs/xfs_rtalloc.c
index 4ab03eafd39f..9d7296c40ddd 100644
--- a/fs/xfs/xfs_rtalloc.c
+++ b/fs/xfs/xfs_rtalloc.c
@@ -495,10 +495,6 @@ xfs_rtallocate_extent_near(
xfs_extlen_t maxavail =
min_t(xfs_rtblock_t, maxlen,
(1ULL << (maxlog + 1)) - 1);
- /*
- * On the positive side of the starting location.
- */
- if (i >= 0) {
/*
* Try to allocate an extent starting in
* this block.
@@ -517,33 +513,6 @@ xfs_rtallocate_extent_near(
return 0;
}
}
- /*
- * On the negative side of the starting location.
- */
- else { /* i < 0 */
- /*
- * Loop backwards through the bitmap blocks from
- * where we last checked up to where we are now.
- * There should be an extent which ends in this
- * bitmap block and is long enough.
- */
- for (; j >= i; j--) {
- error = xfs_rtallocate_extent_block(mp,
- tp, bbno + j, minlen, maxavail,
- len, &n, rtbufc, prod, &r);
- if (error) {
- return error;
- }
- /*
- * If it works, return the extent.
- */
- if (r != NULLRTBLOCK) {
- *rtblock = r;
- return 0;
- }
- }
- }
- }
/*
* Loop control. If we were on the positive side, and there's
* still more blocks on the negative side, go there.
Then when i < 0, this will only find the _beginning_ of a free extent
before bbno rather than the apparent goal of trying to allocate as close
as possible to bbno, i.e., the _end_ of the free extent. (This is what I
tried to explain in the commit message.)
If instead you mean: unconditionally call xfs_rtallocate_extent_block()
for bbno + i when i < 0, i.e.:
diff --git a/fs/xfs/xfs_rtalloc.c b/fs/xfs/xfs_rtalloc.c
index 4ab03eafd39f..1cf42910c0e8 100644
--- a/fs/xfs/xfs_rtalloc.c
+++ b/fs/xfs/xfs_rtalloc.c
@@ -491,14 +491,10 @@ xfs_rtallocate_extent_near(
* If there are any useful extents starting here, try
* allocating one.
*/
- if (maxlog >= 0) {
+ if (maxlog >= 0 || i < 0) {
xfs_extlen_t maxavail =
min_t(xfs_rtblock_t, maxlen,
(1ULL << (maxlog + 1)) - 1);
- /*
- * On the positive side of the starting location.
- */
- if (i >= 0) {
/*
* Try to allocate an extent starting in
* this block.
@@ -517,33 +513,6 @@ xfs_rtallocate_extent_near(
return 0;
}
}
- /*
- * On the negative side of the starting location.
- */
- else { /* i < 0 */
- /*
- * Loop backwards through the bitmap blocks from
- * where we last checked up to where we are now.
- * There should be an extent which ends in this
- * bitmap block and is long enough.
- */
- for (; j >= i; j--) {
- error = xfs_rtallocate_extent_block(mp,
- tp, bbno + j, minlen, maxavail,
- len, &n, rtbufc, prod, &r);
- if (error) {
- return error;
- }
- /*
- * If it works, return the extent.
- */
- if (r != NULLRTBLOCK) {
- *rtblock = r;
- return 0;
- }
- }
- }
- }
/*
* Loop control. If we were on the positive side, and there's
* still more blocks on the negative side, go there.
Then this will find the end of the extent, but we will waste a lot of
time searching bitmap blocks that don't have any usable free space. (In
fact, this is something that patch 6 tries to reduce further.)
> > * 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?
Correct. Before, the loop body was different because it contained a call
to xfs_rtany_summary(). But now there's no check, so the extra call can
be included in the loop.
