From: Brian Foster <bfoster@redhat.com>
To: linux-xfs@vger.kernel.org
Subject: [PATCH v5 08/11] xfs: refactor and reuse best extent scanning logic
Date: Fri, 27 Sep 2019 13:17:59 -0400 [thread overview]
Message-ID: <20190927171802.45582-9-bfoster@redhat.com> (raw)
In-Reply-To: <20190927171802.45582-1-bfoster@redhat.com>
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.
Signed-off-by: Brian Foster <bfoster@redhat.com>
---
fs/xfs/libxfs/xfs_alloc.c | 110 +++++++++++++++++++-------------------
1 file changed, 55 insertions(+), 55 deletions(-)
diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c
index 32b378c8e16c..85e82e184ec9 100644
--- a/fs/xfs/libxfs/xfs_alloc.c
+++ b/fs/xfs/libxfs/xfs_alloc.c
@@ -875,6 +875,13 @@ xfs_alloc_cur_check(
acur->diff = diff;
*new = 1;
+ /*
+ * We're done if we found a perfect allocation. This only deactivates
+ * the current cursor, but this is just an optimization to terminate a
+ * cntbt search that otherwise runs to the edge of the tree.
+ */
+ if (acur->diff == 0 && acur->len == args->maxlen)
+ deactivate = true;
out:
if (deactivate)
cur->bc_private.a.priv.abt.active = false;
@@ -1172,30 +1179,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 +1222,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 +1244,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 +1330,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 +1367,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
next prev parent reply other threads:[~2019-09-27 17:18 UTC|newest]
Thread overview: 22+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-09-27 17:17 [PATCH v5 00/11] xfs: rework near mode extent allocation Brian Foster
2019-09-27 17:17 ` [PATCH v5 01/11] xfs: track active state of allocation btree cursors Brian Foster
2019-09-30 8:11 ` Christoph Hellwig
2019-09-30 12:17 ` Brian Foster
2019-10-01 6:36 ` Christoph Hellwig
2019-10-01 10:30 ` Brian Foster
2019-10-01 5:35 ` Darrick J. Wong
2019-09-27 17:17 ` [PATCH v5 02/11] xfs: introduce allocation cursor data structure Brian Foster
2019-09-27 17:17 ` [PATCH v5 03/11] xfs: track allocation busy state in allocation cursor Brian Foster
2019-09-27 17:17 ` [PATCH v5 04/11] xfs: track best extent from cntbt lastblock scan in alloc cursor Brian Foster
2019-10-04 22:35 ` Darrick J. Wong
2019-09-27 17:17 ` [PATCH v5 05/11] xfs: refactor cntbt lastblock scan best extent logic into helper Brian Foster
2019-10-04 22:40 ` Darrick J. Wong
2019-09-27 17:17 ` [PATCH v5 06/11] xfs: reuse best extent tracking logic for bnobt scan Brian Foster
2019-10-04 22:45 ` Darrick J. Wong
2019-09-27 17:17 ` [PATCH v5 07/11] xfs: refactor allocation tree fixup code Brian Foster
2019-09-27 17:17 ` Brian Foster [this message]
2019-10-04 22:59 ` [PATCH v5 08/11] xfs: refactor and reuse best extent scanning logic Darrick J. Wong
2019-09-27 17:18 ` [PATCH v5 09/11] xfs: refactor near mode alloc bnobt scan into separate function Brian Foster
2019-09-27 17:18 ` [PATCH v5 10/11] xfs: factor out tree fixup logic into helper Brian Foster
2019-09-27 17:18 ` [PATCH v5 11/11] xfs: optimize near mode bnobt scans with concurrent cntbt lookups Brian Foster
2019-10-04 23:20 ` Darrick J. Wong
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20190927171802.45582-9-bfoster@redhat.com \
--to=bfoster@redhat.com \
--cc=linux-xfs@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).