On Thu, Sep 19, 2019 at 11:04:24AM -0400, Brian Foster wrote:
> On Wed, Sep 18, 2019 at 01:43:11PM -0700, Darrick J. Wong wrote:
> > On Mon, Sep 16, 2019 at 08:16:30AM -0400, Brian Foster wrote:
> > > The near mode bnobt scan searches left and right in the bnobt
> > > looking for the closest free extent to the allocation hint that
> > > satisfies minlen. Once such an extent is found, the left/right
> > > search terminates, we search one more time in the opposite direction
> > > and finish the allocation with the best overall extent.
> > >
> > > The left/right and find best searches are currently controlled via a
> > > combination of cursor state and local variables. Clean up this code
> > > and prepare for further improvements to the near mode fallback
> > > algorithm by reusing the allocation cursor best extent tracking
> > > mechanism. Update the tracking logic to deactivate bnobt cursors
> > > when out of allocation range and replace open-coded extent checks to
> > > calls to the common helper. In doing so, rename some misnamed local
> > > variables in the top-level near mode allocation function.
> > >
> > > Signed-off-by: Brian Foster <bfoster@xxxxxxxxxx>
> > > ---
> > > fs/xfs/libxfs/xfs_alloc.c | 270 +++++++++++---------------------------
> > > fs/xfs/xfs_trace.h | 4 +-
> > > 2 files changed, 76 insertions(+), 198 deletions(-)
> > >
> > > diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c
> > > index 2fa7bb6a00a8..edcec975c306 100644
> > > --- a/fs/xfs/libxfs/xfs_alloc.c
> > > +++ b/fs/xfs/libxfs/xfs_alloc.c
> ...
> > > @@ -1163,96 +1172,44 @@ xfs_alloc_ag_vextent_exact(
> > > }
> > >
> > > /*
> > > - * Search the btree in a given direction via the search cursor and compare
> > > - * the records found against the good extent we've already found.
> > > + * Search the btree in a given direction and check the records against the good
> > > + * extent we've already found.
> > > */
> > > STATIC int
> > > xfs_alloc_find_best_extent(
> > > - struct xfs_alloc_arg *args, /* allocation argument structure */
> > > - struct xfs_btree_cur *gcur, /* good cursor */
> > > - struct xfs_btree_cur *scur, /* searching cursor */
> > > - xfs_agblock_t gdiff, /* difference for search comparison */
> > > - xfs_agblock_t *sbno, /* extent found by search */
> > > - xfs_extlen_t *slen, /* extent length */
> > > - xfs_agblock_t *sbnoa, /* aligned extent found by search */
> > > - xfs_extlen_t *slena, /* aligned extent length */
> > > - int dir) /* 0 = search right, 1 = search left */
> > > + struct xfs_alloc_arg *args,
> > > + struct xfs_alloc_cur *acur,
> > > + struct xfs_btree_cur *cur,
> > > + bool increment)
> > > {
> > > - xfs_agblock_t new;
> > > - xfs_agblock_t sdiff;
> > > int error;
> > > int i;
> > > - unsigned busy_gen;
> > > -
> > > - /* The good extent is perfect, no need to search. */
> > > - if (!gdiff)
> > > - goto out_use_good;
> > >
> > > /*
> > > - * Look until we find a better one, run out of space or run off the end.
> > > + * Search so long as the cursor is active or we find a better extent.
> > > + * The cursor is deactivated if it extends beyond the range of the
> > > + * current allocation candidate.
> > > */
> > > - do {
> > > - error = xfs_alloc_get_rec(scur, sbno, slen, &i);
> > > + while (xfs_alloc_cur_active(cur)) {
> > > + error = xfs_alloc_cur_check(args, acur, cur, &i);
> >
> > Does @i > 0 now mean "we found a better candidate for allocation so
> > we're done" ?
> >
>
> In the context of xfs_alloc_cur_check(), i == 1 just means the checked
> extent became the new allocation candidate. Whether "we're done" or not
> is a higher level policy decision. In the xfs_alloc_find_best_extent()
> case, we're doing a last effort search in the opposite direction after
> finding an extent to allocate in the higher level left/right bnobt
> search. So yes, we are done in that scenario, but that's not necessarily
> the case for all calls to xfs_alloc_cur_check() that return i == 1.
>
> Ideally this could be documented better, but this function is reworked
> into xfs_alloc_walk_iter() in the next couple patches and the behavior
> changes slightly.
>
> > > if (error)
> > > - goto error0;
> > > - XFS_WANT_CORRUPTED_GOTO(args->mp, i == 1, error0);
> > > - xfs_alloc_compute_aligned(args, *sbno, *slen,
> > > - sbnoa, slena, &busy_gen);
> > > -
> > > - /*
> > > - * The good extent is closer than this one.
> > > - */
> > > - if (!dir) {
> > > - if (*sbnoa > args->max_agbno)
> > > - goto out_use_good;
> > > - if (*sbnoa >= args->agbno + gdiff)
> > > - goto out_use_good;
> > > - } else {
> > > - if (*sbnoa < args->min_agbno)
> > > - goto out_use_good;
> > > - if (*sbnoa <= args->agbno - gdiff)
> > > - goto out_use_good;
> > > - }
> > > -
> > > - /*
> > > - * Same distance, compare length and pick the best.
> > > - */
> > > - if (*slena >= args->minlen) {
> > > - args->len = XFS_EXTLEN_MIN(*slena, args->maxlen);
> > > - xfs_alloc_fix_len(args);
> > > -
> > > - sdiff = xfs_alloc_compute_diff(args->agbno, args->len,
> > > - args->alignment,
> > > - args->datatype, *sbnoa,
> > > - *slena, &new);
> > > -
> > > - /*
> > > - * Choose closer size and invalidate other cursor.
> > > - */
> > > - if (sdiff < gdiff)
> > > - goto out_use_search;
> > > - goto out_use_good;
> > > - }
> > > + return error;
> > > + if (i == 1)
> > > + break;
> > > + if (!xfs_alloc_cur_active(cur))
> > > + break;
> > >
> > > - if (!dir)
> > > - error = xfs_btree_increment(scur, 0, &i);
> > > + if (increment)
> > > + error = xfs_btree_increment(cur, 0, &i);
> > > else
> > > - error = xfs_btree_decrement(scur, 0, &i);
> > > + error = xfs_btree_decrement(cur, 0, &i);
> > > if (error)
> > > - goto error0;
> > > - } while (i);
> > > -
> > > -out_use_good:
> > > - scur->bc_private.a.priv.abt.active = false;
> > > - return 0;
> > > + return error;
> > > + if (i == 0)
> > > + cur->bc_private.a.priv.abt.active = false;
> >
> > ...and I guess @i == 0 here means "@cur hit the end of the records so
> > deactivate it"?
> >
>
> Yeah, this is a bit of a quirk in that xfs_btree_[inc|dec]rement() are
> generic btree functions and so there was no place to bury the 'active'
> updates in the first patch of the series. I suppose you could argue that
> updating active is a reason to create a couple
> xfs_alloc_[inc|dec]rement() wrappers, but I don't have a strong
> preference. Thoughts?
Heh, oops, forgot to reply to this. I would say that if we're
open-coding a lot of:
error = xfs_btree_increment(some_alloc_cur, &i);
if (error)
return error;
if (i == 0)
some_alloc_cur->bc_private.a.priv.abt.active = false;
then yes, let's have a helper. However, I'd only do that if there are
places other than this function that do this, and only as a cleanup to
add to the end of the series.
--D
>
> > > + }
> > >
> > > -out_use_search:
> > > - gcur->bc_private.a.priv.abt.active = false;
> > > return 0;
> > > -
> > > -error0:
> > > - /* caller invalidates cursors */
> > > - return error;
> > > }
> > >
> > > /*
> > > @@ -1266,23 +1223,13 @@ xfs_alloc_ag_vextent_near(
> > > struct xfs_alloc_arg *args)
> > > {
> > > struct xfs_alloc_cur acur = {0,};
> > > - struct xfs_btree_cur *bno_cur;
> > > - xfs_agblock_t gtbno; /* start bno of right side entry */
> > > - xfs_agblock_t gtbnoa; /* aligned ... */
> > > - xfs_extlen_t gtdiff; /* difference to right side entry */
> > > - xfs_extlen_t gtlen; /* length of right side entry */
> > > - xfs_extlen_t gtlena; /* aligned ... */
> > > - xfs_agblock_t gtnew; /* useful start bno of right side */
> > > + struct xfs_btree_cur *fbcur = NULL;
> > > int error; /* error code */
> > > int i; /* result code, temporary */
> > > int j; /* result code, temporary */
> > > - xfs_agblock_t ltbno; /* start bno of left side entry */
> > > - xfs_agblock_t ltbnoa; /* aligned ... */
> > > - xfs_extlen_t ltdiff; /* difference to left side entry */
> > > - xfs_extlen_t ltlen; /* length of left side entry */
> > > - xfs_extlen_t ltlena; /* aligned ... */
> > > - xfs_agblock_t ltnew; /* useful start bno of left side */
> > > - xfs_extlen_t rlen; /* length of returned extent */
> > > + xfs_agblock_t bno;
> >
> > Is the indenting here inconsistent with the *fbcur declaration above?
> >
>
> No, will fix.
>
> > > + xfs_extlen_t len;
> > > + bool fbinc = false;
> > > #ifdef DEBUG
> > > /*
> > > * Randomly don't execute the first algorithm.
> ...
> > > @@ -1524,47 +1434,15 @@ xfs_alloc_ag_vextent_near(
> > > goto out;
> > > }
> > >
> > > - /*
> > > - * At this point we have selected a freespace entry, either to the
> > > - * left or to the right. If it's on the right, copy all the
> > > - * useful variables to the "left" set so we only have one
> > > - * copy of this code.
> > > - */
> > > - if (xfs_alloc_cur_active(acur.bnogt)) {
> > > - bno_cur = acur.bnogt;
> > > - ltbno = gtbno;
> > > - ltbnoa = gtbnoa;
> > > - ltlen = gtlen;
> > > - ltlena = gtlena;
> > > - j = 1;
> > > - } else {
> > > - bno_cur = acur.bnolt;
> > > - j = 0;
> > > - }
> > > -
> > > - /*
> > > - * Fix up the length and compute the useful address.
> > > - */
> > > - args->len = XFS_EXTLEN_MIN(ltlena, args->maxlen);
> > > - xfs_alloc_fix_len(args);
> > > - rlen = args->len;
> > > - (void)xfs_alloc_compute_diff(args->agbno, rlen, args->alignment,
> > > - args->datatype, ltbnoa, ltlena, <new);
> >
> > Hmm. So I /think/ the reason this can go away is that
> > xfs_alloc_cur_check already did all this trimming and whatnot and
> > stuffed the values into the xfs_alloc_cur structure, so we can just copy
> > the allocated extent to the caller's @args, update the bnobt/cntbt to
> > reflect the allocation, and exit?
> >
>
> Right, the code just above should be a subset of what
> xfs_alloc_cur_check() is already doing before it selects a new
> candidate. This was necessary in the current code because this was all
> tracked by cursor state (i.e. xfs_alloc_find_best_extent() decides
> whether to use the left or right cursor). This is all replaced with
> explicit "best extent" tracking, independent from logic around things
> like which direction to do the "find best" search in, etc.
>
> > I think this looks ok, but woof a lot to digest. :/
> >
>
> This was the hairiest patch of the set IMO. :P
>
> Brian
>
> > --D
> >
> > > - ASSERT(ltnew >= ltbno);
> > > - ASSERT(ltnew + rlen <= ltbnoa + ltlena);
> > > - ASSERT(ltnew + rlen <= be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
> > > - ASSERT(ltnew >= args->min_agbno && ltnew <= args->max_agbno);
> > > - args->agbno = ltnew;
> > > -
> > > - error = xfs_alloc_fixup_trees(acur.cnt, bno_cur, ltbno, ltlen, ltnew,
> > > - rlen, XFSA_FIXUP_BNO_OK);
> > > - if (error)
> > > - goto out;
> > > + args->agbno = acur.bno;
> > > + args->len = acur.len;
> > > + ASSERT(acur.bno >= acur.rec_bno);
> > > + ASSERT(acur.bno + acur.len <= acur.rec_bno + acur.rec_len);
> > > + ASSERT(acur.rec_bno + acur.rec_len <=
> > > + be32_to_cpu(XFS_BUF_TO_AGF(args->agbp)->agf_length));
> > >
> > > - if (j)
> > > - trace_xfs_alloc_near_greater(args);
> > > - else
> > > - trace_xfs_alloc_near_lesser(args);
> > > + error = xfs_alloc_fixup_trees(acur.cnt, acur.bnolt, acur.rec_bno,
> > > + acur.rec_len, acur.bno, acur.len, 0);
> > >
> > > out:
> > > xfs_alloc_cur_close(&acur, error);
> > > diff --git a/fs/xfs/xfs_trace.h b/fs/xfs/xfs_trace.h
> > > index b12fad3e45cb..2e57dc3d4230 100644
> > > --- a/fs/xfs/xfs_trace.h
> > > +++ b/fs/xfs/xfs_trace.h
> > > @@ -1642,8 +1642,8 @@ DEFINE_ALLOC_EVENT(xfs_alloc_exact_notfound);
> > > DEFINE_ALLOC_EVENT(xfs_alloc_exact_error);
> > > DEFINE_ALLOC_EVENT(xfs_alloc_near_nominleft);
> > > DEFINE_ALLOC_EVENT(xfs_alloc_near_first);
> > > -DEFINE_ALLOC_EVENT(xfs_alloc_near_greater);
> > > -DEFINE_ALLOC_EVENT(xfs_alloc_near_lesser);
> > > +DEFINE_ALLOC_EVENT(xfs_alloc_cur_right);
> > > +DEFINE_ALLOC_EVENT(xfs_alloc_cur_left);
> > > DEFINE_ALLOC_EVENT(xfs_alloc_near_error);
> > > DEFINE_ALLOC_EVENT(xfs_alloc_near_noentry);
> > > DEFINE_ALLOC_EVENT(xfs_alloc_near_busy);
> > > --
> > > 2.20.1
> > >
