From: "Darrick J. Wong" <darrick.wong@oracle.com>
To: darrick.wong@oracle.com
Cc: linux-xfs@vger.kernel.org
Subject: [PATCH 08/27] xfs: scrub the shape of a metadata btree
Date: Wed, 20 Sep 2017 17:18:26 -0700 [thread overview]
Message-ID: <150595310675.18473.3213689888370264086.stgit@magnolia> (raw)
In-Reply-To: <150595305131.18473.16572195821331601191.stgit@magnolia>
From: Darrick J. Wong <darrick.wong@oracle.com>
Create a function that can check the shape of a btree -- each block
passes basic inspection and all the pointers look ok. In the next patch
we'll add the ability to check the actual keys and records stored within
the btree. Add some helper functions so that we report detailed scrub
errors in a uniform manner in dmesg. These are helper functions for
subsequent patches.
Signed-off-by: Darrick J. Wong <darrick.wong@oracle.com>
---
fs/xfs/libxfs/xfs_btree.c | 16 +++
fs/xfs/libxfs/xfs_btree.h | 7 +
fs/xfs/scrub/btree.c | 236 +++++++++++++++++++++++++++++++++++++++++++++
fs/xfs/scrub/common.h | 13 ++
4 files changed, 268 insertions(+), 4 deletions(-)
diff --git a/fs/xfs/libxfs/xfs_btree.c b/fs/xfs/libxfs/xfs_btree.c
index 5bfb882..c4d8b47 100644
--- a/fs/xfs/libxfs/xfs_btree.c
+++ b/fs/xfs/libxfs/xfs_btree.c
@@ -1027,7 +1027,7 @@ xfs_btree_setbuf(
}
}
-STATIC int
+bool
xfs_btree_ptr_is_null(
struct xfs_btree_cur *cur,
union xfs_btree_ptr *ptr)
@@ -1052,7 +1052,7 @@ xfs_btree_set_ptr_null(
/*
* Get/set/init sibling pointers
*/
-STATIC void
+void
xfs_btree_get_sibling(
struct xfs_btree_cur *cur,
struct xfs_btree_block *block,
@@ -4914,3 +4914,15 @@ xfs_btree_count_blocks(
return xfs_btree_visit_blocks(cur, xfs_btree_count_blocks_helper,
blocks);
}
+
+/* Compare two btree pointers. */
+int64_t
+xfs_btree_diff_two_ptrs(
+ struct xfs_btree_cur *cur,
+ const union xfs_btree_ptr *a,
+ const union xfs_btree_ptr *b)
+{
+ if (cur->bc_flags & XFS_BTREE_LONG_PTRS)
+ return (int64_t)be64_to_cpu(a->l) - be64_to_cpu(b->l);
+ return (int64_t)be32_to_cpu(a->s) - be32_to_cpu(b->s);
+}
diff --git a/fs/xfs/libxfs/xfs_btree.h b/fs/xfs/libxfs/xfs_btree.h
index f2a88c3..0daf524 100644
--- a/fs/xfs/libxfs/xfs_btree.h
+++ b/fs/xfs/libxfs/xfs_btree.h
@@ -517,5 +517,12 @@ int xfs_btree_lookup_get_block(struct xfs_btree_cur *cur, int level,
union xfs_btree_ptr *pp, struct xfs_btree_block **blkp);
struct xfs_btree_block *xfs_btree_get_block(struct xfs_btree_cur *cur,
int level, struct xfs_buf **bpp);
+bool xfs_btree_ptr_is_null(struct xfs_btree_cur *cur, union xfs_btree_ptr *ptr);
+int64_t xfs_btree_diff_two_ptrs(struct xfs_btree_cur *cur,
+ const union xfs_btree_ptr *a,
+ const union xfs_btree_ptr *b);
+void xfs_btree_get_sibling(struct xfs_btree_cur *cur,
+ struct xfs_btree_block *block,
+ union xfs_btree_ptr *ptr, int lr);
#endif /* __XFS_BTREE_H__ */
diff --git a/fs/xfs/scrub/btree.c b/fs/xfs/scrub/btree.c
index adf5d09..a9c2bf3 100644
--- a/fs/xfs/scrub/btree.c
+++ b/fs/xfs/scrub/btree.c
@@ -94,6 +94,152 @@ xfs_scrub_btree_check_ok(
return fs_ok;
}
+/* Check a btree pointer. */
+static int
+xfs_scrub_btree_ptr(
+ struct xfs_scrub_btree *bs,
+ int level,
+ union xfs_btree_ptr *ptr)
+{
+ struct xfs_btree_cur *cur = bs->cur;
+ xfs_daddr_t daddr;
+ xfs_daddr_t eofs;
+
+ if (!xfs_scrub_btree_check_ok(bs->sc, cur, level,
+ !xfs_btree_ptr_is_null(cur, ptr)))
+ goto corrupt;
+ if (cur->bc_flags & XFS_BTREE_LONG_PTRS) {
+ daddr = XFS_FSB_TO_DADDR(cur->bc_mp, be64_to_cpu(ptr->l));
+ } else {
+ if (!xfs_scrub_btree_check_ok(bs->sc, cur, level,
+ cur->bc_private.a.agno != NULLAGNUMBER))
+ goto corrupt;
+
+ daddr = XFS_AGB_TO_DADDR(cur->bc_mp, cur->bc_private.a.agno,
+ be32_to_cpu(ptr->s));
+ }
+ eofs = XFS_FSB_TO_BB(cur->bc_mp, cur->bc_mp->m_sb.sb_dblocks);
+ if (!xfs_scrub_btree_check_ok(bs->sc, cur, level,
+ daddr != 0 && daddr < eofs))
+ goto corrupt;
+
+ return 0;
+
+corrupt:
+ return -EFSCORRUPTED;
+}
+
+/* Check that a btree block's sibling matches what we expect it. */
+STATIC int
+xfs_scrub_btree_block_check_sibling(
+ struct xfs_scrub_btree *bs,
+ int level,
+ int direction,
+ union xfs_btree_ptr *sibling)
+{
+ struct xfs_btree_cur *cur = bs->cur;
+ struct xfs_btree_block *pblock;
+ struct xfs_buf *pbp;
+ struct xfs_btree_cur *ncur;
+ union xfs_btree_ptr *pp;
+ int success;
+ int error;
+
+ if (xfs_btree_ptr_is_null(cur, sibling))
+ return 0;
+
+ error = xfs_btree_dup_cursor(cur, &ncur);
+ if (error)
+ return error;
+
+ if (direction > 0)
+ error = xfs_btree_increment(ncur, level + 1, &success);
+ else
+ error = xfs_btree_decrement(ncur, level + 1, &success);
+ if (!xfs_scrub_btree_op_ok(bs->sc, cur, level + 1, &error) ||
+ !xfs_scrub_btree_check_ok(bs->sc, cur, level + 1, success))
+ goto out;
+
+ pblock = xfs_btree_get_block(ncur, level + 1, &pbp);
+ pp = xfs_btree_ptr_addr(ncur, ncur->bc_ptrs[level + 1], pblock);
+ error = xfs_scrub_btree_ptr(bs, level + 1, pp);
+ if (error) {
+ /*
+ * _scrub_btree_ptr already recorded a garbage sibling.
+ * Don't let the EFSCORRUPTED bubble up and prevent more
+ * scanning of the data structure.
+ */
+ error = 0;
+ goto out;
+ }
+
+ xfs_scrub_btree_check_ok(bs->sc, cur, level,
+ !xfs_btree_diff_two_ptrs(cur, pp, sibling));
+out:
+ xfs_btree_del_cursor(ncur, XFS_BTREE_ERROR);
+ return error;
+}
+
+/* Check the siblings of a btree block. */
+STATIC int
+xfs_scrub_btree_block_check_siblings(
+ struct xfs_scrub_btree *bs,
+ struct xfs_btree_block *block)
+{
+ struct xfs_btree_cur *cur = bs->cur;
+ union xfs_btree_ptr leftsib;
+ union xfs_btree_ptr rightsib;
+ int level;
+ int error = 0;
+
+ xfs_btree_get_sibling(cur, block, &leftsib, XFS_BB_LEFTSIB);
+ xfs_btree_get_sibling(cur, block, &rightsib, XFS_BB_RIGHTSIB);
+ level = xfs_btree_get_level(block);
+
+ /* Root block should never have siblings. */
+ if (level == cur->bc_nlevels - 1) {
+ xfs_scrub_btree_check_ok(bs->sc, cur, level,
+ xfs_btree_ptr_is_null(cur, &leftsib) &&
+ xfs_btree_ptr_is_null(cur, &rightsib));
+ goto out;
+ }
+
+ /* Does the left sibling match the parent level left block? */
+ error = xfs_scrub_btree_block_check_sibling(bs, level, -1, &leftsib);
+ if (error)
+ return error;
+
+ /* Does the right sibling match the parent level right block? */
+ error = xfs_scrub_btree_block_check_sibling(bs, level, 1, &rightsib);
+ if (error)
+ return error;
+out:
+ return error;
+}
+
+/* Grab and scrub a btree block. */
+STATIC int
+xfs_scrub_btree_block(
+ struct xfs_scrub_btree *bs,
+ int level,
+ union xfs_btree_ptr *pp,
+ struct xfs_btree_block **pblock,
+ struct xfs_buf **pbp)
+{
+ int error;
+
+ error = xfs_btree_lookup_get_block(bs->cur, level, pp, pblock);
+ if (error)
+ return error;
+
+ xfs_btree_get_block(bs->cur, level, pbp);
+ error = xfs_btree_check_block(bs->cur, *pblock, level, *pbp);
+ if (error)
+ return error;
+
+ return xfs_scrub_btree_block_check_siblings(bs, *pblock);
+}
+
/*
* Visit all nodes and leaves of a btree. Check that all pointers and
* records are in order, that the keys reflect the records, and use a callback
@@ -109,6 +255,92 @@ xfs_scrub_btree(
struct xfs_owner_info *oinfo,
void *private)
{
- xfs_scrub_btree_op_ok(sc, cur, 0, false);
- return -EOPNOTSUPP;
+ struct xfs_scrub_btree bs = {0};
+ union xfs_btree_ptr ptr;
+ union xfs_btree_ptr *pp;
+ struct xfs_btree_block *block;
+ int level;
+ struct xfs_buf *bp;
+ int i;
+ int error = 0;
+
+ /* Initialize scrub state */
+ bs.cur = cur;
+ bs.scrub_rec = scrub_fn;
+ bs.oinfo = oinfo;
+ bs.firstrec = true;
+ bs.private = private;
+ bs.sc = sc;
+ for (i = 0; i < XFS_BTREE_MAXLEVELS; i++)
+ bs.firstkey[i] = true;
+ INIT_LIST_HEAD(&bs.to_check);
+
+ /* Don't try to check a tree with a height we can't handle. */
+ if (!xfs_scrub_btree_check_ok(sc, cur, 0, cur->bc_nlevels > 0 &&
+ cur->bc_nlevels <= XFS_BTREE_MAXLEVELS))
+ goto out;
+
+ /* Make sure the root isn't in the superblock. */
+ if (!(cur->bc_flags & XFS_BTREE_ROOT_IN_INODE)) {
+ cur->bc_ops->init_ptr_from_cur(cur, &ptr);
+ error = xfs_scrub_btree_ptr(&bs, cur->bc_nlevels, &ptr);
+ if (!xfs_scrub_btree_op_ok(sc, cur, cur->bc_nlevels - 1, &error))
+ goto out;
+ }
+
+ /* Load the root of the btree. */
+ level = cur->bc_nlevels - 1;
+ cur->bc_ops->init_ptr_from_cur(cur, &ptr);
+ error = xfs_scrub_btree_block(&bs, level, &ptr, &block, &bp);
+ if (!xfs_scrub_btree_op_ok(sc, cur, cur->bc_nlevels - 1, &error))
+ goto out;
+
+ cur->bc_ptrs[level] = 1;
+
+ while (level < cur->bc_nlevels) {
+ block = xfs_btree_get_block(cur, level, &bp);
+
+ if (level == 0) {
+ /* End of leaf, pop back towards the root. */
+ if (cur->bc_ptrs[level] >
+ be16_to_cpu(block->bb_numrecs)) {
+ if (level < cur->bc_nlevels - 1)
+ cur->bc_ptrs[level + 1]++;
+ level++;
+ continue;
+ }
+
+ if (xfs_scrub_should_terminate(&error))
+ break;
+
+ cur->bc_ptrs[level]++;
+ continue;
+ }
+
+ /* End of node, pop back towards the root. */
+ if (cur->bc_ptrs[level] > be16_to_cpu(block->bb_numrecs)) {
+ if (level < cur->bc_nlevels - 1)
+ cur->bc_ptrs[level + 1]++;
+ level++;
+ continue;
+ }
+
+ /* Drill another level deeper. */
+ pp = xfs_btree_ptr_addr(cur, cur->bc_ptrs[level], block);
+ error = xfs_scrub_btree_ptr(&bs, level, pp);
+ if (error) {
+ error = 0;
+ cur->bc_ptrs[level]++;
+ continue;
+ }
+ level--;
+ error = xfs_scrub_btree_block(&bs, level, pp, &block, &bp);
+ if (!xfs_scrub_btree_op_ok(sc, cur, level, &error))
+ goto out;
+
+ cur->bc_ptrs[level] = 1;
+ }
+
+out:
+ return error;
}
diff --git a/fs/xfs/scrub/common.h b/fs/xfs/scrub/common.h
index e1bb14b..9920488 100644
--- a/fs/xfs/scrub/common.h
+++ b/fs/xfs/scrub/common.h
@@ -20,6 +20,19 @@
#ifndef __XFS_SCRUB_COMMON_H__
#define __XFS_SCRUB_COMMON_H__
+/* Should we end the scrub early? */
+static inline bool
+xfs_scrub_should_terminate(
+ int *error)
+{
+ if (fatal_signal_pending(current)) {
+ if (*error == 0)
+ *error = -EAGAIN;
+ return true;
+ }
+ return false;
+}
+
/*
* Grab a transaction. If we're going to repair something, we need to
* ensure there's enough reservation to make all the changes. If not,
next prev parent reply other threads:[~2017-09-21 0:18 UTC|newest]
Thread overview: 51+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-09-21 0:17 [PATCH v10 00/27] xfs: online scrub support Darrick J. Wong
2017-09-21 0:17 ` [PATCH 01/27] xfs: return a distinct error code value for IGET_INCORE cache misses Darrick J. Wong
2017-09-21 14:36 ` Brian Foster
2017-09-21 0:17 ` [PATCH 02/27] xfs: query the per-AG reservation counters Darrick J. Wong
2017-09-21 14:36 ` Brian Foster
2017-09-21 17:30 ` Darrick J. Wong
2017-09-21 0:17 ` [PATCH 03/27] xfs: create an ioctl to scrub AG metadata Darrick J. Wong
2017-09-21 14:36 ` Brian Foster
2017-09-21 17:35 ` Darrick J. Wong
2017-09-21 17:52 ` Brian Foster
2017-09-22 3:26 ` Darrick J. Wong
2017-09-21 0:18 ` [PATCH 04/27] xfs: dispatch metadata scrub subcommands Darrick J. Wong
2017-09-21 14:37 ` Brian Foster
2017-09-21 18:08 ` Darrick J. Wong
2017-09-21 0:18 ` [PATCH 05/27] xfs: test the scrub ioctl Darrick J. Wong
2017-09-21 6:04 ` Dave Chinner
2017-09-21 18:14 ` Darrick J. Wong
2017-09-21 0:18 ` [PATCH 06/27] xfs: create helpers to record and deal with scrub problems Darrick J. Wong
2017-09-22 7:16 ` Dave Chinner
2017-09-22 16:44 ` Darrick J. Wong
2017-09-23 7:22 ` Dave Chinner
2017-09-23 7:24 ` Darrick J. Wong
2017-09-21 0:18 ` [PATCH 07/27] xfs: create helpers to scrub a metadata btree Darrick J. Wong
2017-09-22 7:23 ` Dave Chinner
2017-09-22 16:59 ` Darrick J. Wong
2017-09-21 0:18 ` Darrick J. Wong [this message]
2017-09-22 15:22 ` [PATCH 08/27] xfs: scrub the shape of " Brian Foster
2017-09-22 17:22 ` Darrick J. Wong
2017-09-22 19:13 ` Brian Foster
2017-09-22 20:14 ` Darrick J. Wong
2017-09-22 21:15 ` Brian Foster
2017-09-21 0:18 ` [PATCH 09/27] xfs: scrub btree keys and records Darrick J. Wong
2017-09-21 0:18 ` [PATCH 10/27] xfs: create helpers to scan an allocation group Darrick J. Wong
2017-09-21 0:18 ` [PATCH 11/27] xfs: scrub the backup superblocks Darrick J. Wong
2017-09-21 0:18 ` [PATCH 12/27] xfs: scrub AGF and AGFL Darrick J. Wong
2017-09-21 0:18 ` [PATCH 13/27] xfs: scrub the AGI Darrick J. Wong
2017-09-21 0:19 ` [PATCH 14/27] xfs: scrub free space btrees Darrick J. Wong
2017-09-21 0:19 ` [PATCH 15/27] xfs: scrub inode btrees Darrick J. Wong
2017-09-21 0:19 ` [PATCH 16/27] xfs: scrub rmap btrees Darrick J. Wong
2017-09-21 0:19 ` [PATCH 17/27] xfs: scrub refcount btrees Darrick J. Wong
2017-09-21 0:19 ` [PATCH 18/27] xfs: scrub inodes Darrick J. Wong
2017-09-21 0:19 ` [PATCH 19/27] xfs: scrub inode block mappings Darrick J. Wong
2017-09-21 0:19 ` [PATCH 20/27] xfs: scrub directory/attribute btrees Darrick J. Wong
2017-09-21 0:19 ` [PATCH 21/27] xfs: scrub directory metadata Darrick J. Wong
2017-09-21 0:19 ` [PATCH 22/27] xfs: scrub directory freespace Darrick J. Wong
2017-09-21 0:20 ` [PATCH 23/27] xfs: scrub extended attributes Darrick J. Wong
2017-09-21 0:20 ` [PATCH 24/27] xfs: scrub symbolic links Darrick J. Wong
2017-09-21 0:20 ` [PATCH 25/27] xfs: scrub parent pointers Darrick J. Wong
2017-09-21 0:20 ` [PATCH 26/27] xfs: scrub realtime bitmap/summary Darrick J. Wong
2017-09-21 0:20 ` [PATCH 27/27] xfs: scrub quota information Darrick J. Wong
2017-09-22 3:27 ` [PATCH] man: describe the metadata scrubbing ioctl 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=150595310675.18473.3213689888370264086.stgit@magnolia \
--to=darrick.wong@oracle.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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.