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

[Omar Sandoval <osandov@osandov.com>]

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@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.

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.