| Message ID | 20190916121635.43148-9-bfoster@redhat.com (mailing list archive) |
|---|---|
| State | Superseded |
| Headers | show |
| Series | xfs: rework near mode extent allocation | expand |
On Mon, Sep 16, 2019 at 08:16:32AM -0400, Brian Foster wrote: > The bnobt "find best" helper implements a simple btree walker > function. This general pattern, or a subset thereof, is reused in > various parts of a near mode allocation operation. For example, the > bnobt left/right scans are each iterative btree walks along with the > cntbt lastblock scan. > > Rework this function into a generic btree walker, add a couple > parameters to control termination behavior from various contexts and > reuse it where applicable. > > XXX: This slightly changes the cntbt lastblock scan logic to scan > the entire block and use the best candidate as opposed to the > current logic of checking until we locate a perfect match. Fix up > cur_check() to terminate on perfect match. Did that fix up happen in a previous patch? > Signed-off-by: Brian Foster <bfoster@redhat.com> > --- > fs/xfs/libxfs/xfs_alloc.c | 103 ++++++++++++++++++-------------------- > 1 file changed, 48 insertions(+), 55 deletions(-) > > diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c > index 3eacc799c4cb..ab494fd50dd7 100644 > --- a/fs/xfs/libxfs/xfs_alloc.c > +++ b/fs/xfs/libxfs/xfs_alloc.c > @@ -1172,30 +1172,38 @@ xfs_alloc_ag_vextent_exact( > } > > /* > - * Search the btree in a given direction and check the records against the good > - * extent we've already found. > + * Search a given number of btree records in a given direction. Check each > + * record against the good extent we've already found. > */ > STATIC int > -xfs_alloc_find_best_extent( > +xfs_alloc_walk_iter( > struct xfs_alloc_arg *args, > struct xfs_alloc_cur *acur, > struct xfs_btree_cur *cur, > - bool increment) > + bool increment, > + bool find_one,/* quit on first candidate */ Space between the comma and the comment? --D > + int count, /* rec count (-1 for infinite) */ > + int *stat) > { > int error; > int i; > > + *stat = 0; > + > /* > * 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. > */ > - while (xfs_alloc_cur_active(cur)) { > + while (xfs_alloc_cur_active(cur) && count) { > error = xfs_alloc_cur_check(args, acur, cur, &i); > if (error) > return error; > - if (i == 1) > - break; > + if (i == 1) { > + *stat = 1; > + if (find_one) > + break; > + } > if (!xfs_alloc_cur_active(cur)) > break; > > @@ -1207,6 +1215,9 @@ xfs_alloc_find_best_extent( > return error; > if (i == 0) > cur->bc_private.a.priv.abt.active = false; > + > + if (count > 0) > + count--; > } > > return 0; > @@ -1226,7 +1237,6 @@ xfs_alloc_ag_vextent_near( > struct xfs_btree_cur *fbcur = NULL; > int error; /* error code */ > int i; /* result code, temporary */ > - int j; /* result code, temporary */ > xfs_agblock_t bno; > xfs_extlen_t len; > bool fbinc = false; > @@ -1313,19 +1323,12 @@ xfs_alloc_ag_vextent_near( > if (!i) > break; > } > - i = acur.cnt->bc_ptrs[0]; > - for (j = 1; > - !error && j && xfs_alloc_cur_active(acur.cnt) && > - (acur.len < args->maxlen || acur.diff > 0); > - error = xfs_btree_increment(acur.cnt, 0, &j)) { > - /* > - * For each entry, decide if it's better than > - * the previous best entry. > - */ > - error = xfs_alloc_cur_check(args, &acur, acur.cnt, &i); > - if (error) > - goto out; > - } > + > + error = xfs_alloc_walk_iter(args, &acur, acur.cnt, true, false, > + -1, &i); > + if (error) > + goto out; > + > /* > * It didn't work. We COULD be in a case where > * there's a good record somewhere, so try again. > @@ -1357,49 +1360,39 @@ xfs_alloc_ag_vextent_near( > goto out; > > /* > - * Loop going left with the leftward cursor, right with the > - * rightward cursor, until either both directions give up or > - * we find an entry at least as big as minlen. > + * Loop going left with the leftward cursor, right with the rightward > + * cursor, until either both directions give up or we find an entry at > + * least as big as minlen. > */ > do { > - if (xfs_alloc_cur_active(acur.bnolt)) { > - error = xfs_alloc_cur_check(args, &acur, acur.bnolt, &i); > - if (error) > - goto out; > - if (i == 1) { > - trace_xfs_alloc_cur_left(args); > - fbcur = acur.bnogt; > - fbinc = true; > - break; > - } > - error = xfs_btree_decrement(acur.bnolt, 0, &i); > - if (error) > - goto out; > - if (!i) > - acur.bnolt->bc_private.a.priv.abt.active = false; > + error = xfs_alloc_walk_iter(args, &acur, acur.bnolt, false, > + true, 1, &i); > + if (error) > + goto out; > + if (i == 1) { > + trace_xfs_alloc_cur_left(args); > + fbcur = acur.bnogt; > + fbinc = true; > + break; > } > - if (xfs_alloc_cur_active(acur.bnogt)) { > - error = xfs_alloc_cur_check(args, &acur, acur.bnogt, &i); > - if (error) > - goto out; > - if (i == 1) { > - trace_xfs_alloc_cur_right(args); > - fbcur = acur.bnolt; > - fbinc = false; > - break; > - } > - error = xfs_btree_increment(acur.bnogt, 0, &i); > - if (error) > - goto out; > - if (!i) > - acur.bnogt->bc_private.a.priv.abt.active = false; > + > + error = xfs_alloc_walk_iter(args, &acur, acur.bnogt, true, true, > + 1, &i); > + if (error) > + goto out; > + if (i == 1) { > + trace_xfs_alloc_cur_right(args); > + fbcur = acur.bnolt; > + fbinc = false; > + break; > } > } while (xfs_alloc_cur_active(acur.bnolt) || > xfs_alloc_cur_active(acur.bnogt)); > > /* search the opposite direction for a better entry */ > if (fbcur) { > - error = xfs_alloc_find_best_extent(args, &acur, fbcur, fbinc); > + error = xfs_alloc_walk_iter(args, &acur, fbcur, fbinc, true, -1, > + &i); > if (error) > goto out; > } > -- > 2.20.1 >
On Wed, Sep 18, 2019 at 02:03:20PM -0700, Darrick J. Wong wrote: > On Mon, Sep 16, 2019 at 08:16:32AM -0400, Brian Foster wrote: > > The bnobt "find best" helper implements a simple btree walker > > function. This general pattern, or a subset thereof, is reused in > > various parts of a near mode allocation operation. For example, the > > bnobt left/right scans are each iterative btree walks along with the > > cntbt lastblock scan. > > > > Rework this function into a generic btree walker, add a couple > > parameters to control termination behavior from various contexts and > > reuse it where applicable. > > > > XXX: This slightly changes the cntbt lastblock scan logic to scan > > the entire block and use the best candidate as opposed to the > > current logic of checking until we locate a perfect match. Fix up > > cur_check() to terminate on perfect match. > > Did that fix up happen in a previous patch? > No, I think at one point I convinced myself to just drop this because it didn't seem likely to find an exact extent via the cntbt and then forgot to update the commit log. That said, I'll revisit this because as rare as it might be, I think it might make sense to just deactivate the cntbt cursor in the (acur->len == args->maxlen && acur->diff == 0) scenario and let that terminate the search reasonably gracefully. > > Signed-off-by: Brian Foster <bfoster@redhat.com> > > --- > > fs/xfs/libxfs/xfs_alloc.c | 103 ++++++++++++++++++-------------------- > > 1 file changed, 48 insertions(+), 55 deletions(-) > > > > diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c > > index 3eacc799c4cb..ab494fd50dd7 100644 > > --- a/fs/xfs/libxfs/xfs_alloc.c > > +++ b/fs/xfs/libxfs/xfs_alloc.c > > @@ -1172,30 +1172,38 @@ xfs_alloc_ag_vextent_exact( > > } > > > > /* > > - * Search the btree in a given direction and check the records against the good > > - * extent we've already found. > > + * Search a given number of btree records in a given direction. Check each > > + * record against the good extent we've already found. > > */ > > STATIC int > > -xfs_alloc_find_best_extent( > > +xfs_alloc_walk_iter( > > struct xfs_alloc_arg *args, > > struct xfs_alloc_cur *acur, > > struct xfs_btree_cur *cur, > > - bool increment) > > + bool increment, > > + bool find_one,/* quit on first candidate */ > > Space between the comma and the comment? > Fixed and aligned both comments with spaces. Brian > --D > > > + int count, /* rec count (-1 for infinite) */ > > + int *stat) > > { > > int error; > > int i; > > > > + *stat = 0; > > + > > /* > > * 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. > > */ > > - while (xfs_alloc_cur_active(cur)) { > > + while (xfs_alloc_cur_active(cur) && count) { > > error = xfs_alloc_cur_check(args, acur, cur, &i); > > if (error) > > return error; > > - if (i == 1) > > - break; > > + if (i == 1) { > > + *stat = 1; > > + if (find_one) > > + break; > > + } > > if (!xfs_alloc_cur_active(cur)) > > break; > > > > @@ -1207,6 +1215,9 @@ xfs_alloc_find_best_extent( > > return error; > > if (i == 0) > > cur->bc_private.a.priv.abt.active = false; > > + > > + if (count > 0) > > + count--; > > } > > > > return 0; > > @@ -1226,7 +1237,6 @@ xfs_alloc_ag_vextent_near( > > struct xfs_btree_cur *fbcur = NULL; > > int error; /* error code */ > > int i; /* result code, temporary */ > > - int j; /* result code, temporary */ > > xfs_agblock_t bno; > > xfs_extlen_t len; > > bool fbinc = false; > > @@ -1313,19 +1323,12 @@ xfs_alloc_ag_vextent_near( > > if (!i) > > break; > > } > > - i = acur.cnt->bc_ptrs[0]; > > - for (j = 1; > > - !error && j && xfs_alloc_cur_active(acur.cnt) && > > - (acur.len < args->maxlen || acur.diff > 0); > > - error = xfs_btree_increment(acur.cnt, 0, &j)) { > > - /* > > - * For each entry, decide if it's better than > > - * the previous best entry. > > - */ > > - error = xfs_alloc_cur_check(args, &acur, acur.cnt, &i); > > - if (error) > > - goto out; > > - } > > + > > + error = xfs_alloc_walk_iter(args, &acur, acur.cnt, true, false, > > + -1, &i); > > + if (error) > > + goto out; > > + > > /* > > * It didn't work. We COULD be in a case where > > * there's a good record somewhere, so try again. > > @@ -1357,49 +1360,39 @@ xfs_alloc_ag_vextent_near( > > goto out; > > > > /* > > - * Loop going left with the leftward cursor, right with the > > - * rightward cursor, until either both directions give up or > > - * we find an entry at least as big as minlen. > > + * Loop going left with the leftward cursor, right with the rightward > > + * cursor, until either both directions give up or we find an entry at > > + * least as big as minlen. > > */ > > do { > > - if (xfs_alloc_cur_active(acur.bnolt)) { > > - error = xfs_alloc_cur_check(args, &acur, acur.bnolt, &i); > > - if (error) > > - goto out; > > - if (i == 1) { > > - trace_xfs_alloc_cur_left(args); > > - fbcur = acur.bnogt; > > - fbinc = true; > > - break; > > - } > > - error = xfs_btree_decrement(acur.bnolt, 0, &i); > > - if (error) > > - goto out; > > - if (!i) > > - acur.bnolt->bc_private.a.priv.abt.active = false; > > + error = xfs_alloc_walk_iter(args, &acur, acur.bnolt, false, > > + true, 1, &i); > > + if (error) > > + goto out; > > + if (i == 1) { > > + trace_xfs_alloc_cur_left(args); > > + fbcur = acur.bnogt; > > + fbinc = true; > > + break; > > } > > - if (xfs_alloc_cur_active(acur.bnogt)) { > > - error = xfs_alloc_cur_check(args, &acur, acur.bnogt, &i); > > - if (error) > > - goto out; > > - if (i == 1) { > > - trace_xfs_alloc_cur_right(args); > > - fbcur = acur.bnolt; > > - fbinc = false; > > - break; > > - } > > - error = xfs_btree_increment(acur.bnogt, 0, &i); > > - if (error) > > - goto out; > > - if (!i) > > - acur.bnogt->bc_private.a.priv.abt.active = false; > > + > > + error = xfs_alloc_walk_iter(args, &acur, acur.bnogt, true, true, > > + 1, &i); > > + if (error) > > + goto out; > > + if (i == 1) { > > + trace_xfs_alloc_cur_right(args); > > + fbcur = acur.bnolt; > > + fbinc = false; > > + break; > > } > > } while (xfs_alloc_cur_active(acur.bnolt) || > > xfs_alloc_cur_active(acur.bnogt)); > > > > /* search the opposite direction for a better entry */ > > if (fbcur) { > > - error = xfs_alloc_find_best_extent(args, &acur, fbcur, fbinc); > > + error = xfs_alloc_walk_iter(args, &acur, fbcur, fbinc, true, -1, > > + &i); > > if (error) > > goto out; > > } > > -- > > 2.20.1 > >
diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c index 3eacc799c4cb..ab494fd50dd7 100644 --- a/fs/xfs/libxfs/xfs_alloc.c +++ b/fs/xfs/libxfs/xfs_alloc.c @@ -1172,30 +1172,38 @@ xfs_alloc_ag_vextent_exact( } /* - * Search the btree in a given direction and check the records against the good - * extent we've already found. + * Search a given number of btree records in a given direction. Check each + * record against the good extent we've already found. */ STATIC int -xfs_alloc_find_best_extent( +xfs_alloc_walk_iter( struct xfs_alloc_arg *args, struct xfs_alloc_cur *acur, struct xfs_btree_cur *cur, - bool increment) + bool increment, + bool find_one,/* quit on first candidate */ + int count, /* rec count (-1 for infinite) */ + int *stat) { int error; int i; + *stat = 0; + /* * 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. */ - while (xfs_alloc_cur_active(cur)) { + while (xfs_alloc_cur_active(cur) && count) { error = xfs_alloc_cur_check(args, acur, cur, &i); if (error) return error; - if (i == 1) - break; + if (i == 1) { + *stat = 1; + if (find_one) + break; + } if (!xfs_alloc_cur_active(cur)) break; @@ -1207,6 +1215,9 @@ xfs_alloc_find_best_extent( return error; if (i == 0) cur->bc_private.a.priv.abt.active = false; + + if (count > 0) + count--; } return 0; @@ -1226,7 +1237,6 @@ xfs_alloc_ag_vextent_near( struct xfs_btree_cur *fbcur = NULL; int error; /* error code */ int i; /* result code, temporary */ - int j; /* result code, temporary */ xfs_agblock_t bno; xfs_extlen_t len; bool fbinc = false; @@ -1313,19 +1323,12 @@ xfs_alloc_ag_vextent_near( if (!i) break; } - i = acur.cnt->bc_ptrs[0]; - for (j = 1; - !error && j && xfs_alloc_cur_active(acur.cnt) && - (acur.len < args->maxlen || acur.diff > 0); - error = xfs_btree_increment(acur.cnt, 0, &j)) { - /* - * For each entry, decide if it's better than - * the previous best entry. - */ - error = xfs_alloc_cur_check(args, &acur, acur.cnt, &i); - if (error) - goto out; - } + + error = xfs_alloc_walk_iter(args, &acur, acur.cnt, true, false, + -1, &i); + if (error) + goto out; + /* * It didn't work. We COULD be in a case where * there's a good record somewhere, so try again. @@ -1357,49 +1360,39 @@ xfs_alloc_ag_vextent_near( goto out; /* - * Loop going left with the leftward cursor, right with the - * rightward cursor, until either both directions give up or - * we find an entry at least as big as minlen. + * Loop going left with the leftward cursor, right with the rightward + * cursor, until either both directions give up or we find an entry at + * least as big as minlen. */ do { - if (xfs_alloc_cur_active(acur.bnolt)) { - error = xfs_alloc_cur_check(args, &acur, acur.bnolt, &i); - if (error) - goto out; - if (i == 1) { - trace_xfs_alloc_cur_left(args); - fbcur = acur.bnogt; - fbinc = true; - break; - } - error = xfs_btree_decrement(acur.bnolt, 0, &i); - if (error) - goto out; - if (!i) - acur.bnolt->bc_private.a.priv.abt.active = false; + error = xfs_alloc_walk_iter(args, &acur, acur.bnolt, false, + true, 1, &i); + if (error) + goto out; + if (i == 1) { + trace_xfs_alloc_cur_left(args); + fbcur = acur.bnogt; + fbinc = true; + break; } - if (xfs_alloc_cur_active(acur.bnogt)) { - error = xfs_alloc_cur_check(args, &acur, acur.bnogt, &i); - if (error) - goto out; - if (i == 1) { - trace_xfs_alloc_cur_right(args); - fbcur = acur.bnolt; - fbinc = false; - break; - } - error = xfs_btree_increment(acur.bnogt, 0, &i); - if (error) - goto out; - if (!i) - acur.bnogt->bc_private.a.priv.abt.active = false; + + error = xfs_alloc_walk_iter(args, &acur, acur.bnogt, true, true, + 1, &i); + if (error) + goto out; + if (i == 1) { + trace_xfs_alloc_cur_right(args); + fbcur = acur.bnolt; + fbinc = false; + break; } } while (xfs_alloc_cur_active(acur.bnolt) || xfs_alloc_cur_active(acur.bnogt)); /* search the opposite direction for a better entry */ if (fbcur) { - error = xfs_alloc_find_best_extent(args, &acur, fbcur, fbinc); + error = xfs_alloc_walk_iter(args, &acur, fbcur, fbinc, true, -1, + &i); if (error) goto out; }
The bnobt "find best" helper implements a simple btree walker function. This general pattern, or a subset thereof, is reused in various parts of a near mode allocation operation. For example, the bnobt left/right scans are each iterative btree walks along with the cntbt lastblock scan. Rework this function into a generic btree walker, add a couple parameters to control termination behavior from various contexts and reuse it where applicable. XXX: This slightly changes the cntbt lastblock scan logic to scan the entire block and use the best candidate as opposed to the current logic of checking until we locate a perfect match. Fix up cur_check() to terminate on perfect match. Signed-off-by: Brian Foster <bfoster@redhat.com> --- fs/xfs/libxfs/xfs_alloc.c | 103 ++++++++++++++++++-------------------- 1 file changed, 48 insertions(+), 55 deletions(-)