On Mon, Jul 17, 2023 at 02:06:36PM -0700, Omar Sandoval wrote:
> 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.
<nod>
> > "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.)
Hmm. It's hard to remember what I was thinking 15 minutes ago let alone
2 weeks ago, but I /think/ this is what I was driving at. I agree with
your statement that this would find any free extent starting before
bbno, instead of a free extent *ending* as close as possible to bbno.
I now understand what this patch is trying to accomplish, and it looks
good to me, modulo whatever comment changes you want to make. :)
> 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.)
<nod>
> > > * 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.
Ok, thanks. That makes sense to me now.
--D
