From patchwork Sun Oct 2 18:20:16 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Darrick J. Wong" X-Patchwork-Id: 12996956 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id B4C73C433FE for ; Sun, 2 Oct 2022 18:32:27 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230071AbiJBSc0 (ORCPT ); Sun, 2 Oct 2022 14:32:26 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34412 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230084AbiJBSc0 (ORCPT ); Sun, 2 Oct 2022 14:32:26 -0400 Received: from ams.source.kernel.org (ams.source.kernel.org [145.40.68.75]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 47B8E3C156 for ; Sun, 2 Oct 2022 11:32:24 -0700 (PDT) Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ams.source.kernel.org (Postfix) with ESMTPS id C739BB80D89 for ; Sun, 2 Oct 2022 18:32:22 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 8995AC433D6; Sun, 2 Oct 2022 18:32:21 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1664735541; bh=7/e1JwB9hs7EQe2EUByn+waJxhbvMLD9gXY+YKQqUu4=; h=Subject:From:To:Cc:Date:In-Reply-To:References:From; b=erPgkrjQUiK3TGI3DtcSl42lOUdDWZ+nOCDdDqOymK+AhmFtvPqD4oVmE+kLZa9r3 02y8qaTs4a55QqdP/yrPzF1V8zkx/DC0p44oW22gSb4q/Jus0S8LXbNxyp6z3jNys5 935H0pJDvv+80u+MgBimhR1Z+Qnr6F2HF5VsDcdYrg8LuLPmp0B+axYrihOIUP7Ada hYEI+qAN+/8phouzdfEyFA23TccToRGZEixXH2PVorAv5ywA4OmRwrb24axH6/r7Wa qo4tRSmiMXOgaYDElZFs0Iw51rFcs0NCKUToV7I9o3M1+SqYSodj/QKnkJ791MeA5o ssS/QYZCz5+DQ== Subject: [PATCH 1/5] xfs: replace xfs_btree_has_record with a general keyspace scanner From: "Darrick J. Wong" To: djwong@kernel.org Cc: linux-xfs@vger.kernel.org Date: Sun, 02 Oct 2022 11:20:16 -0700 Message-ID: <166473481597.1084209.14598185861526380195.stgit@magnolia> In-Reply-To: <166473481572.1084209.5434516873607335909.stgit@magnolia> References: <166473481572.1084209.5434516873607335909.stgit@magnolia> User-Agent: StGit/0.19 MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-xfs@vger.kernel.org From: Darrick J. Wong The current implementation of xfs_btree_has_record returns true if it finds /any/ record within the given range. Unfortunately, that's not sufficient for scrub. We want to be able to tell if a range of keyspace for a btree is devoid of records, is totally mapped to records, or is somewhere in between. By forcing this to be a boolean, we were generally missing the "in between" case and returning incorrect results. Fix the API so that we can tell the caller which of those three is the current state. Signed-off-by: Darrick J. Wong --- fs/xfs/libxfs/xfs_alloc.c | 11 +++- fs/xfs/libxfs/xfs_alloc.h | 4 +- fs/xfs/libxfs/xfs_alloc_btree.c | 13 +++++ fs/xfs/libxfs/xfs_bmap_btree.c | 13 +++++ fs/xfs/libxfs/xfs_btree.c | 92 +++++++++++++++++++++++++++++++----- fs/xfs/libxfs/xfs_btree.h | 15 +++++- fs/xfs/libxfs/xfs_ialloc_btree.c | 14 +++++ fs/xfs/libxfs/xfs_refcount.c | 11 +++- fs/xfs/libxfs/xfs_refcount.h | 5 +- fs/xfs/libxfs/xfs_refcount_btree.c | 13 +++++ fs/xfs/libxfs/xfs_rmap.c | 12 +++-- fs/xfs/libxfs/xfs_rmap.h | 4 +- fs/xfs/libxfs/xfs_rmap_btree.c | 13 +++++ fs/xfs/libxfs/xfs_types.h | 12 +++++ fs/xfs/scrub/alloc.c | 6 +- fs/xfs/scrub/refcount.c | 7 ++- fs/xfs/scrub/rmap.c | 6 +- 17 files changed, 209 insertions(+), 42 deletions(-) diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c index e2bdf089c0a3..f0c92093db0a 100644 --- a/fs/xfs/libxfs/xfs_alloc.c +++ b/fs/xfs/libxfs/xfs_alloc.c @@ -3498,13 +3498,16 @@ xfs_alloc_query_all( return xfs_btree_query_all(cur, xfs_alloc_query_range_helper, &query); } -/* Is there a record covering a given extent? */ +/* + * Scan part of the keyspace of the free space and tell us if the area has no + * records, is fully mapped by records, or is partially filled. + */ int -xfs_alloc_has_record( +xfs_alloc_scan_keyfill( struct xfs_btree_cur *cur, xfs_agblock_t bno, xfs_extlen_t len, - bool *exists) + enum xfs_btree_keyfill *outcome) { union xfs_btree_irec low; union xfs_btree_irec high; @@ -3514,7 +3517,7 @@ xfs_alloc_has_record( memset(&high, 0xFF, sizeof(high)); high.a.ar_startblock = bno + len - 1; - return xfs_btree_has_record(cur, &low, &high, exists); + return xfs_btree_scan_keyfill(cur, &low, &high, outcome); } /* diff --git a/fs/xfs/libxfs/xfs_alloc.h b/fs/xfs/libxfs/xfs_alloc.h index 2c3f762dfb58..ebda867aa6f4 100644 --- a/fs/xfs/libxfs/xfs_alloc.h +++ b/fs/xfs/libxfs/xfs_alloc.h @@ -194,8 +194,8 @@ int xfs_alloc_query_range(struct xfs_btree_cur *cur, int xfs_alloc_query_all(struct xfs_btree_cur *cur, xfs_alloc_query_range_fn fn, void *priv); -int xfs_alloc_has_record(struct xfs_btree_cur *cur, xfs_agblock_t bno, - xfs_extlen_t len, bool *exist); +int xfs_alloc_scan_keyfill(struct xfs_btree_cur *cur, xfs_agblock_t bno, + xfs_extlen_t len, enum xfs_btree_keyfill *outcome); typedef int (*xfs_agfl_walk_fn)(struct xfs_mount *mp, xfs_agblock_t bno, void *priv); diff --git a/fs/xfs/libxfs/xfs_alloc_btree.c b/fs/xfs/libxfs/xfs_alloc_btree.c index 549a3cba0234..916d278204f5 100644 --- a/fs/xfs/libxfs/xfs_alloc_btree.c +++ b/fs/xfs/libxfs/xfs_alloc_btree.c @@ -423,6 +423,18 @@ xfs_cntbt_recs_inorder( be32_to_cpu(r2->alloc.ar_startblock)); } +STATIC bool +xfs_allocbt_has_key_gap( + struct xfs_btree_cur *cur, + const union xfs_btree_key *key1, + const union xfs_btree_key *key2) +{ + xfs_agblock_t next; + + next = be32_to_cpu(key1->alloc.ar_startblock) + 1; + return next != be32_to_cpu(key2->alloc.ar_startblock); +} + static const struct xfs_btree_ops xfs_bnobt_ops = { .rec_len = sizeof(xfs_alloc_rec_t), .key_len = sizeof(xfs_alloc_key_t), @@ -443,6 +455,7 @@ static const struct xfs_btree_ops xfs_bnobt_ops = { .diff_two_keys = xfs_bnobt_diff_two_keys, .keys_inorder = xfs_bnobt_keys_inorder, .recs_inorder = xfs_bnobt_recs_inorder, + .has_key_gap = xfs_allocbt_has_key_gap, }; static const struct xfs_btree_ops xfs_cntbt_ops = { diff --git a/fs/xfs/libxfs/xfs_bmap_btree.c b/fs/xfs/libxfs/xfs_bmap_btree.c index cfa052d40105..d1225b957649 100644 --- a/fs/xfs/libxfs/xfs_bmap_btree.c +++ b/fs/xfs/libxfs/xfs_bmap_btree.c @@ -518,6 +518,18 @@ xfs_bmbt_recs_inorder( xfs_bmbt_disk_get_startoff(&r2->bmbt); } +STATIC bool +xfs_bmbt_has_key_gap( + struct xfs_btree_cur *cur, + const union xfs_btree_key *key1, + const union xfs_btree_key *key2) +{ + xfs_fileoff_t next; + + next = be64_to_cpu(key1->bmbt.br_startoff) + 1; + return next != be64_to_cpu(key2->bmbt.br_startoff); +} + static const struct xfs_btree_ops xfs_bmbt_ops = { .rec_len = sizeof(xfs_bmbt_rec_t), .key_len = sizeof(xfs_bmbt_key_t), @@ -538,6 +550,7 @@ static const struct xfs_btree_ops xfs_bmbt_ops = { .buf_ops = &xfs_bmbt_buf_ops, .keys_inorder = xfs_bmbt_keys_inorder, .recs_inorder = xfs_bmbt_recs_inorder, + .has_key_gap = xfs_bmbt_has_key_gap, }; /* diff --git a/fs/xfs/libxfs/xfs_btree.c b/fs/xfs/libxfs/xfs_btree.c index 4c16c8c31fcb..5710d3ee582a 100644 --- a/fs/xfs/libxfs/xfs_btree.c +++ b/fs/xfs/libxfs/xfs_btree.c @@ -5008,34 +5008,100 @@ xfs_btree_diff_two_ptrs( return (int64_t)be32_to_cpu(a->s) - be32_to_cpu(b->s); } -/* If there's an extent, we're done. */ +struct xfs_btree_scan_keyfill { + /* Keys for the start and end of the range we want to know about. */ + union xfs_btree_key start_key; + union xfs_btree_key end_key; + + /* Highest record key we've seen so far. */ + union xfs_btree_key high_key; + + enum xfs_btree_keyfill outcome; +}; + STATIC int -xfs_btree_has_record_helper( +xfs_btree_scan_keyfill_helper( struct xfs_btree_cur *cur, const union xfs_btree_rec *rec, void *priv) { - return -ECANCELED; + union xfs_btree_key rec_key; + union xfs_btree_key rec_high_key; + struct xfs_btree_scan_keyfill *info = priv; + int64_t res; + + cur->bc_ops->init_key_from_rec(&rec_key, rec); + + if (info->outcome == XFS_BTREE_KEYFILL_EMPTY) { + info->outcome = XFS_BTREE_KEYFILL_SPARSE; + + /* Bail if the first record starts after the start key. */ + res = cur->bc_ops->diff_two_keys(cur, &info->start_key, + &rec_key); + if (res < 0) + return -ECANCELED; + } else { + /* Bail if there's a gap with the previous record. */ + if (cur->bc_ops->has_key_gap(cur, &info->high_key, &rec_key)) + return -ECANCELED; + } + + /* If the current record is higher than what we've seen, remember it. */ + cur->bc_ops->init_high_key_from_rec(&rec_high_key, rec); + res = cur->bc_ops->diff_two_keys(cur, &rec_high_key, &info->high_key); + if (res > 0) + info->high_key = rec_high_key; /* struct copy */ + + return 0; } -/* Is there a record covering a given range of keys? */ +/* + * Scan part of the keyspace of a btree and tell us if the area has no records, + * is fully mapped by records, or is partially filled. + */ int -xfs_btree_has_record( +xfs_btree_scan_keyfill( struct xfs_btree_cur *cur, const union xfs_btree_irec *low, const union xfs_btree_irec *high, - bool *exists) + enum xfs_btree_keyfill *outcome) { + struct xfs_btree_scan_keyfill info = { + .outcome = XFS_BTREE_KEYFILL_EMPTY, + }; + union xfs_btree_rec rec; + int64_t res; int error; + if (!cur->bc_ops->has_key_gap) + return -EOPNOTSUPP; + + cur->bc_rec = *low; + cur->bc_ops->init_rec_from_cur(cur, &rec); + cur->bc_ops->init_key_from_rec(&info.start_key, &rec); + + cur->bc_rec = *high; + cur->bc_ops->init_rec_from_cur(cur, &rec); + cur->bc_ops->init_key_from_rec(&info.end_key, &rec); + error = xfs_btree_query_range(cur, low, high, - &xfs_btree_has_record_helper, NULL); - if (error == -ECANCELED) { - *exists = true; - return 0; - } - *exists = false; - return error; + xfs_btree_scan_keyfill_helper, &info); + if (error == -ECANCELED) + goto out; + if (error) + return error; + + if (info.outcome == XFS_BTREE_KEYFILL_EMPTY) + goto out; + + /* Did the record set go at least as far as the end? */ + res = cur->bc_ops->diff_two_keys(cur, &info.high_key, &info.end_key); + if (res >= 0) + info.outcome = XFS_BTREE_KEYFILL_FULL; + +out: + *outcome = info.outcome; + return 0; } /* Are there more records in this btree? */ diff --git a/fs/xfs/libxfs/xfs_btree.h b/fs/xfs/libxfs/xfs_btree.h index eef27858a013..58a05f0d1f1b 100644 --- a/fs/xfs/libxfs/xfs_btree.h +++ b/fs/xfs/libxfs/xfs_btree.h @@ -157,6 +157,11 @@ struct xfs_btree_ops { int (*recs_inorder)(struct xfs_btree_cur *cur, const union xfs_btree_rec *r1, const union xfs_btree_rec *r2); + + /* decide if there's a gap in the keyspace between two keys */ + bool (*has_key_gap)(struct xfs_btree_cur *cur, + const union xfs_btree_key *key1, + const union xfs_btree_key *key2); }; /* @@ -540,9 +545,15 @@ void xfs_btree_get_keys(struct xfs_btree_cur *cur, struct xfs_btree_block *block, union xfs_btree_key *key); union xfs_btree_key *xfs_btree_high_key_from_key(struct xfs_btree_cur *cur, union xfs_btree_key *key); -int xfs_btree_has_record(struct xfs_btree_cur *cur, +typedef bool (*xfs_btree_key_gap_fn)(struct xfs_btree_cur *cur, + const union xfs_btree_key *key1, + const union xfs_btree_key *key2); + +int xfs_btree_scan_keyfill(struct xfs_btree_cur *cur, const union xfs_btree_irec *low, - const union xfs_btree_irec *high, bool *exists); + const union xfs_btree_irec *high, + enum xfs_btree_keyfill *outcome); + bool xfs_btree_has_more_records(struct xfs_btree_cur *cur); struct xfs_ifork *xfs_btree_ifork_ptr(struct xfs_btree_cur *cur); diff --git a/fs/xfs/libxfs/xfs_ialloc_btree.c b/fs/xfs/libxfs/xfs_ialloc_btree.c index 8c83e265770c..fd48b95b4f4e 100644 --- a/fs/xfs/libxfs/xfs_ialloc_btree.c +++ b/fs/xfs/libxfs/xfs_ialloc_btree.c @@ -380,6 +380,18 @@ xfs_inobt_recs_inorder( be32_to_cpu(r2->inobt.ir_startino); } +STATIC bool +xfs_inobt_has_key_gap( + struct xfs_btree_cur *cur, + const union xfs_btree_key *key1, + const union xfs_btree_key *key2) +{ + xfs_agino_t next; + + next = be32_to_cpu(key1->inobt.ir_startino) + XFS_INODES_PER_CHUNK; + return next != be32_to_cpu(key2->inobt.ir_startino); +} + static const struct xfs_btree_ops xfs_inobt_ops = { .rec_len = sizeof(xfs_inobt_rec_t), .key_len = sizeof(xfs_inobt_key_t), @@ -399,6 +411,7 @@ static const struct xfs_btree_ops xfs_inobt_ops = { .diff_two_keys = xfs_inobt_diff_two_keys, .keys_inorder = xfs_inobt_keys_inorder, .recs_inorder = xfs_inobt_recs_inorder, + .has_key_gap = xfs_inobt_has_key_gap, }; static const struct xfs_btree_ops xfs_finobt_ops = { @@ -420,6 +433,7 @@ static const struct xfs_btree_ops xfs_finobt_ops = { .diff_two_keys = xfs_inobt_diff_two_keys, .keys_inorder = xfs_inobt_keys_inorder, .recs_inorder = xfs_inobt_recs_inorder, + .has_key_gap = xfs_inobt_has_key_gap, }; /* diff --git a/fs/xfs/libxfs/xfs_refcount.c b/fs/xfs/libxfs/xfs_refcount.c index 64b910caafaa..607fd25fda56 100644 --- a/fs/xfs/libxfs/xfs_refcount.c +++ b/fs/xfs/libxfs/xfs_refcount.c @@ -1766,13 +1766,16 @@ xfs_refcount_recover_cow_leftovers( return error; } -/* Is there a record covering a given extent? */ +/* + * Scan part of the keyspace of the refcount records and tell us if the area + * has no records, is fully mapped by records, or is partially filled. + */ int -xfs_refcount_has_record( +xfs_refcount_scan_keyfill( struct xfs_btree_cur *cur, xfs_agblock_t bno, xfs_extlen_t len, - bool *exists) + enum xfs_btree_keyfill *outcome) { union xfs_btree_irec low; union xfs_btree_irec high; @@ -1782,7 +1785,7 @@ xfs_refcount_has_record( memset(&high, 0xFF, sizeof(high)); high.rc.rc_startblock = bno + len - 1; - return xfs_btree_has_record(cur, &low, &high, exists); + return xfs_btree_scan_keyfill(cur, &low, &high, outcome); } int __init diff --git a/fs/xfs/libxfs/xfs_refcount.h b/fs/xfs/libxfs/xfs_refcount.h index e8b322de7f3d..14b8edc289fa 100644 --- a/fs/xfs/libxfs/xfs_refcount.h +++ b/fs/xfs/libxfs/xfs_refcount.h @@ -78,8 +78,9 @@ extern int xfs_refcount_recover_cow_leftovers(struct xfs_mount *mp, */ #define XFS_REFCOUNT_ITEM_OVERHEAD 32 -extern int xfs_refcount_has_record(struct xfs_btree_cur *cur, - xfs_agblock_t bno, xfs_extlen_t len, bool *exists); +extern int xfs_refcount_scan_keyfill(struct xfs_btree_cur *cur, + xfs_agblock_t bno, xfs_extlen_t len, + enum xfs_btree_keyfill *outcome); union xfs_btree_rec; extern void xfs_refcount_btrec_to_irec(const union xfs_btree_rec *rec, struct xfs_refcount_irec *irec); diff --git a/fs/xfs/libxfs/xfs_refcount_btree.c b/fs/xfs/libxfs/xfs_refcount_btree.c index 316c1ec0c3c2..f7982b2ecc49 100644 --- a/fs/xfs/libxfs/xfs_refcount_btree.c +++ b/fs/xfs/libxfs/xfs_refcount_btree.c @@ -290,6 +290,18 @@ xfs_refcountbt_recs_inorder( be32_to_cpu(r2->refc.rc_startblock); } +STATIC bool +xfs_refcountbt_has_key_gap( + struct xfs_btree_cur *cur, + const union xfs_btree_key *key1, + const union xfs_btree_key *key2) +{ + xfs_agblock_t next; + + next = be32_to_cpu(key1->refc.rc_startblock) + 1; + return next != be32_to_cpu(key2->refc.rc_startblock); +} + static const struct xfs_btree_ops xfs_refcountbt_ops = { .rec_len = sizeof(struct xfs_refcount_rec), .key_len = sizeof(struct xfs_refcount_key), @@ -309,6 +321,7 @@ static const struct xfs_btree_ops xfs_refcountbt_ops = { .diff_two_keys = xfs_refcountbt_diff_two_keys, .keys_inorder = xfs_refcountbt_keys_inorder, .recs_inorder = xfs_refcountbt_recs_inorder, + .has_key_gap = xfs_refcountbt_has_key_gap, }; /* diff --git a/fs/xfs/libxfs/xfs_rmap.c b/fs/xfs/libxfs/xfs_rmap.c index 094dfc897ebc..08d47cbf4697 100644 --- a/fs/xfs/libxfs/xfs_rmap.c +++ b/fs/xfs/libxfs/xfs_rmap.c @@ -2671,13 +2671,17 @@ xfs_rmap_compare( return 0; } -/* Is there a record covering a given extent? */ +/* + * Scan the physical storage part of the keyspace of the reverse mapping index + * and tell us if the area has no records, is fully mapped by records, or is + * partially filled. + */ int -xfs_rmap_has_record( +xfs_rmap_scan_keyfill( struct xfs_btree_cur *cur, xfs_agblock_t bno, xfs_extlen_t len, - bool *exists) + enum xfs_btree_keyfill *outcome) { union xfs_btree_irec low; union xfs_btree_irec high; @@ -2687,7 +2691,7 @@ xfs_rmap_has_record( memset(&high, 0xFF, sizeof(high)); high.r.rm_startblock = bno + len - 1; - return xfs_btree_has_record(cur, &low, &high, exists); + return xfs_btree_scan_keyfill(cur, &low, &high, outcome); } /* diff --git a/fs/xfs/libxfs/xfs_rmap.h b/fs/xfs/libxfs/xfs_rmap.h index 54741a591a17..263a2dd09216 100644 --- a/fs/xfs/libxfs/xfs_rmap.h +++ b/fs/xfs/libxfs/xfs_rmap.h @@ -192,8 +192,8 @@ int xfs_rmap_compare(const struct xfs_rmap_irec *a, union xfs_btree_rec; int xfs_rmap_btrec_to_irec(const union xfs_btree_rec *rec, struct xfs_rmap_irec *irec); -int xfs_rmap_has_record(struct xfs_btree_cur *cur, xfs_agblock_t bno, - xfs_extlen_t len, bool *exists); +int xfs_rmap_scan_keyfill(struct xfs_btree_cur *cur, xfs_agblock_t bno, + xfs_extlen_t len, enum xfs_btree_keyfill *outcome); int xfs_rmap_record_exists(struct xfs_btree_cur *cur, xfs_agblock_t bno, xfs_extlen_t len, const struct xfs_owner_info *oinfo, bool *has_rmap); diff --git a/fs/xfs/libxfs/xfs_rmap_btree.c b/fs/xfs/libxfs/xfs_rmap_btree.c index e2e1f68cedf5..d64143a842ce 100644 --- a/fs/xfs/libxfs/xfs_rmap_btree.c +++ b/fs/xfs/libxfs/xfs_rmap_btree.c @@ -433,6 +433,18 @@ xfs_rmapbt_recs_inorder( return 0; } +STATIC bool +xfs_rmapbt_has_key_gap( + struct xfs_btree_cur *cur, + const union xfs_btree_key *key1, + const union xfs_btree_key *key2) +{ + xfs_agblock_t next; + + next = be32_to_cpu(key1->rmap.rm_startblock) + 1; + return next != be32_to_cpu(key2->rmap.rm_startblock); +} + static const struct xfs_btree_ops xfs_rmapbt_ops = { .rec_len = sizeof(struct xfs_rmap_rec), .key_len = 2 * sizeof(struct xfs_rmap_key), @@ -452,6 +464,7 @@ static const struct xfs_btree_ops xfs_rmapbt_ops = { .diff_two_keys = xfs_rmapbt_diff_two_keys, .keys_inorder = xfs_rmapbt_keys_inorder, .recs_inorder = xfs_rmapbt_recs_inorder, + .has_key_gap = xfs_rmapbt_has_key_gap, }; static struct xfs_btree_cur * diff --git a/fs/xfs/libxfs/xfs_types.h b/fs/xfs/libxfs/xfs_types.h index a6b7d98cf68f..d63637a3b873 100644 --- a/fs/xfs/libxfs/xfs_types.h +++ b/fs/xfs/libxfs/xfs_types.h @@ -174,6 +174,18 @@ enum xfs_ag_resv_type { XFS_AG_RESV_RMAPBT, }; +/* Results of scanning a btree keyspace to check occupancy. */ +enum xfs_btree_keyfill { + /* None of the keyspace maps to records. */ + XFS_BTREE_KEYFILL_EMPTY = 0, + + /* Some, but not all, of the keyspace maps to records. */ + XFS_BTREE_KEYFILL_SPARSE, + + /* The entire keyspace maps to records. */ + XFS_BTREE_KEYFILL_FULL, +}; + /* * Type verifier functions */ diff --git a/fs/xfs/scrub/alloc.c b/fs/xfs/scrub/alloc.c index 4d9ccc15b048..d8f2ba7efa22 100644 --- a/fs/xfs/scrub/alloc.c +++ b/fs/xfs/scrub/alloc.c @@ -146,15 +146,15 @@ xchk_xref_is_used_space( xfs_agblock_t agbno, xfs_extlen_t len) { - bool is_freesp; + enum xfs_btree_keyfill keyfill; int error; if (!sc->sa.bno_cur || xchk_skip_xref(sc->sm)) return; - error = xfs_alloc_has_record(sc->sa.bno_cur, agbno, len, &is_freesp); + error = xfs_alloc_scan_keyfill(sc->sa.bno_cur, agbno, len, &keyfill); if (!xchk_should_check_xref(sc, &error, &sc->sa.bno_cur)) return; - if (is_freesp) + if (keyfill != XFS_BTREE_KEYFILL_EMPTY) xchk_btree_xref_set_corrupt(sc, sc->sa.bno_cur, 0); } diff --git a/fs/xfs/scrub/refcount.c b/fs/xfs/scrub/refcount.c index 4e70cd821b62..bfd48aaceb82 100644 --- a/fs/xfs/scrub/refcount.c +++ b/fs/xfs/scrub/refcount.c @@ -475,15 +475,16 @@ xchk_xref_is_not_shared( xfs_agblock_t agbno, xfs_extlen_t len) { - bool shared; + enum xfs_btree_keyfill keyfill; int error; if (!sc->sa.refc_cur || xchk_skip_xref(sc->sm)) return; - error = xfs_refcount_has_record(sc->sa.refc_cur, agbno, len, &shared); + error = xfs_refcount_scan_keyfill(sc->sa.refc_cur, agbno, len, + &keyfill); if (!xchk_should_check_xref(sc, &error, &sc->sa.refc_cur)) return; - if (shared) + if (keyfill != XFS_BTREE_KEYFILL_EMPTY) xchk_btree_xref_set_corrupt(sc, sc->sa.refc_cur, 0); } diff --git a/fs/xfs/scrub/rmap.c b/fs/xfs/scrub/rmap.c index afc4f840b6bc..6525202c6a8a 100644 --- a/fs/xfs/scrub/rmap.c +++ b/fs/xfs/scrub/rmap.c @@ -224,15 +224,15 @@ xchk_xref_has_no_owner( xfs_agblock_t bno, xfs_extlen_t len) { - bool has_rmap; + enum xfs_btree_keyfill keyfill; int error; if (!sc->sa.rmap_cur || xchk_skip_xref(sc->sm)) return; - error = xfs_rmap_has_record(sc->sa.rmap_cur, bno, len, &has_rmap); + error = xfs_rmap_scan_keyfill(sc->sa.rmap_cur, bno, len, &keyfill); if (!xchk_should_check_xref(sc, &error, &sc->sa.rmap_cur)) return; - if (has_rmap) + if (keyfill != XFS_BTREE_KEYFILL_EMPTY) xchk_btree_xref_set_corrupt(sc, sc->sa.rmap_cur, 0); } From patchwork Sun Oct 2 18:20:16 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Darrick J. Wong" X-Patchwork-Id: 12996957 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 85507C433FE for ; Sun, 2 Oct 2022 18:32:36 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230087AbiJBScf (ORCPT ); Sun, 2 Oct 2022 14:32:35 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34456 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230084AbiJBScd (ORCPT ); Sun, 2 Oct 2022 14:32:33 -0400 Received: from dfw.source.kernel.org (dfw.source.kernel.org [IPv6:2604:1380:4641:c500::1]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 31BDD3C15F for ; Sun, 2 Oct 2022 11:32:33 -0700 (PDT) Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dfw.source.kernel.org (Postfix) with ESMTPS id C3AD160EDB for ; Sun, 2 Oct 2022 18:32:32 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 2E294C433D6; Sun, 2 Oct 2022 18:32:32 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1664735552; bh=GL6wUJ0pndQzymSba/vqNX+sy7EKRYfc4bgD8NpXYAc=; h=Subject:From:To:Cc:Date:In-Reply-To:References:From; b=ffBQtkoDjzMVX9Kj2pF5KjytYiX3ydePY8UigQrD+RMpu+ORQncFuZ4tMSiHOyexF YkW/os8b57EBdNsS7bz1paodrTyJnC0kaFLe5VPY64e/oNAOeKEdipgKOBziyccSMd FxWn+noGtJac1EED+PNuuwsDWtUFGxwNp65odNJVe48bPEI9T062GaOSNyqGJhX+S0 JyCRfVxRYgNte4lXvot7mfC54ej/cBlYJlNmmHK8hRhZ2Zr3KcqZ/3/IADE128YzGd ontoIGd/FensdCR66LzjU5uTzLYJVwUGzHO4FnF6XZROcwQ1/tyokNQSsMUDXjVnID NK8ZL51ZjijLA== Subject: [PATCH 2/5] xfs: refactor converting btree irec to btree key From: "Darrick J. Wong" To: djwong@kernel.org Cc: linux-xfs@vger.kernel.org Date: Sun, 02 Oct 2022 11:20:16 -0700 Message-ID: <166473481613.1084209.14289552157471603973.stgit@magnolia> In-Reply-To: <166473481572.1084209.5434516873607335909.stgit@magnolia> References: <166473481572.1084209.5434516873607335909.stgit@magnolia> User-Agent: StGit/0.19 MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-xfs@vger.kernel.org From: Darrick J. Wong We keep doing these conversions to support btree queries, so refactor this into a helper. Signed-off-by: Darrick J. Wong Reviewed-by: Dave Chinner --- fs/xfs/libxfs/xfs_btree.c | 33 +++++++++++++++++---------------- 1 file changed, 17 insertions(+), 16 deletions(-) diff --git a/fs/xfs/libxfs/xfs_btree.c b/fs/xfs/libxfs/xfs_btree.c index 5710d3ee582a..edea6db8d8e4 100644 --- a/fs/xfs/libxfs/xfs_btree.c +++ b/fs/xfs/libxfs/xfs_btree.c @@ -4918,6 +4918,19 @@ xfs_btree_overlapped_query_range( return error; } +static inline void +xfs_btree_key_from_irec( + struct xfs_btree_cur *cur, + union xfs_btree_key *key, + const union xfs_btree_irec *irec) +{ + union xfs_btree_rec rec; + + cur->bc_rec = *irec; + cur->bc_ops->init_rec_from_cur(cur, &rec); + cur->bc_ops->init_key_from_rec(key, &rec); +} + /* * Query a btree for all records overlapping a given interval of keys. The * supplied function will be called with each record found; return one of the @@ -4932,18 +4945,12 @@ xfs_btree_query_range( xfs_btree_query_range_fn fn, void *priv) { - union xfs_btree_rec rec; union xfs_btree_key low_key; union xfs_btree_key high_key; /* Find the keys of both ends of the interval. */ - cur->bc_rec = *high_rec; - cur->bc_ops->init_rec_from_cur(cur, &rec); - cur->bc_ops->init_key_from_rec(&high_key, &rec); - - cur->bc_rec = *low_rec; - cur->bc_ops->init_rec_from_cur(cur, &rec); - cur->bc_ops->init_key_from_rec(&low_key, &rec); + xfs_btree_key_from_irec(cur, &high_key, high_rec); + xfs_btree_key_from_irec(cur, &low_key, low_rec); /* Enforce low key < high key. */ if (cur->bc_ops->diff_two_keys(cur, &low_key, &high_key) > 0) @@ -5069,20 +5076,14 @@ xfs_btree_scan_keyfill( struct xfs_btree_scan_keyfill info = { .outcome = XFS_BTREE_KEYFILL_EMPTY, }; - union xfs_btree_rec rec; int64_t res; int error; if (!cur->bc_ops->has_key_gap) return -EOPNOTSUPP; - cur->bc_rec = *low; - cur->bc_ops->init_rec_from_cur(cur, &rec); - cur->bc_ops->init_key_from_rec(&info.start_key, &rec); - - cur->bc_rec = *high; - cur->bc_ops->init_rec_from_cur(cur, &rec); - cur->bc_ops->init_key_from_rec(&info.end_key, &rec); + xfs_btree_key_from_irec(cur, &info.start_key, low); + xfs_btree_key_from_irec(cur, &info.end_key, high); error = xfs_btree_query_range(cur, low, high, xfs_btree_scan_keyfill_helper, &info); From patchwork Sun Oct 2 18:20:16 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Darrick J. Wong" X-Patchwork-Id: 12996958 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 6107CC433F5 for ; Sun, 2 Oct 2022 18:32:50 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230091AbiJBSct (ORCPT ); Sun, 2 Oct 2022 14:32:49 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34570 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230092AbiJBScs (ORCPT ); Sun, 2 Oct 2022 14:32:48 -0400 Received: from sin.source.kernel.org (sin.source.kernel.org [145.40.73.55]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 457223C171 for ; Sun, 2 Oct 2022 11:32:46 -0700 (PDT) Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by sin.source.kernel.org (Postfix) with ESMTPS id 7E31ACE0A4A for ; Sun, 2 Oct 2022 18:32:44 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id B2C61C433D6; Sun, 2 Oct 2022 18:32:42 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1664735562; bh=iwjzVtXnPEOWjcmgJutIABkLQzUhP3JgwiK6IM9PORw=; h=Subject:From:To:Cc:Date:In-Reply-To:References:From; b=V1td0/I8kH2TJl+/bQeOyuTOZNDVX0xWAHFsIEB0Q72+nn+/sTUVTyHOVS7ft6U6A YM4XsQnx0V3jxhuHnjTvRjhCi+m1Ke/RlpLZfMneGAwqGeO0F2y8exPh2kLSeWkfaO 0v/qnLSJJd0oIhca1ICU2+9QjCc2YxTztRPFnrlTgY9lo1YP/zZwQ1tCTpsRs4Fc41 K4QVoZpCGP3K4er8QzA8movu8hQTSdp7t3UIdqaPd7pRHK23eIHDK1lbhX55bI+ngR ED1GdGyQeqTw18XHuJF6B3Xk4Y9dPXA9uICj6dxIx0LsSplz7oIC0q1N+0389w6EyF JeU2sQcZVKv7A== Subject: [PATCH 3/5] xfs: mask key comparisons for keyspace fill scans From: "Darrick J. Wong" To: djwong@kernel.org Cc: linux-xfs@vger.kernel.org Date: Sun, 02 Oct 2022 11:20:16 -0700 Message-ID: <166473481626.1084209.13610255473278160434.stgit@magnolia> In-Reply-To: <166473481572.1084209.5434516873607335909.stgit@magnolia> References: <166473481572.1084209.5434516873607335909.stgit@magnolia> User-Agent: StGit/0.19 MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-xfs@vger.kernel.org From: Darrick J. Wong For keyspace fullness scans, we want to be able to mask off the parts of the key that we don't care about. For most btree types we /do/ want the full keyspace, but for checking that a given space usage also has a full complement of rmapbt records (even if different/multiple owners) we need this masking so that we only track sparseness of rm_startblock, not the whole keyspace (which is extremely sparse). Signed-off-by: Darrick J. Wong --- fs/xfs/libxfs/xfs_alloc.c | 2 +- fs/xfs/libxfs/xfs_alloc_btree.c | 5 +++- fs/xfs/libxfs/xfs_bmap_btree.c | 5 +++- fs/xfs/libxfs/xfs_btree.c | 41 +++++++++++++++++++++++++++---- fs/xfs/libxfs/xfs_btree.h | 10 +++++++- fs/xfs/libxfs/xfs_ialloc_btree.c | 7 ++++- fs/xfs/libxfs/xfs_refcount.c | 2 +- fs/xfs/libxfs/xfs_refcount_btree.c | 5 +++- fs/xfs/libxfs/xfs_rmap.c | 7 +++++ fs/xfs/libxfs/xfs_rmap_btree.c | 48 +++++++++++++++++++++++++++++++++--- 10 files changed, 114 insertions(+), 18 deletions(-) diff --git a/fs/xfs/libxfs/xfs_alloc.c b/fs/xfs/libxfs/xfs_alloc.c index f0c92093db0a..0ce1f914f7cc 100644 --- a/fs/xfs/libxfs/xfs_alloc.c +++ b/fs/xfs/libxfs/xfs_alloc.c @@ -3517,7 +3517,7 @@ xfs_alloc_scan_keyfill( memset(&high, 0xFF, sizeof(high)); high.a.ar_startblock = bno + len - 1; - return xfs_btree_scan_keyfill(cur, &low, &high, outcome); + return xfs_btree_scan_keyfill(cur, &low, &high, NULL, outcome); } /* diff --git a/fs/xfs/libxfs/xfs_alloc_btree.c b/fs/xfs/libxfs/xfs_alloc_btree.c index 916d278204f5..4a69d767a32b 100644 --- a/fs/xfs/libxfs/xfs_alloc_btree.c +++ b/fs/xfs/libxfs/xfs_alloc_btree.c @@ -427,10 +427,13 @@ STATIC bool xfs_allocbt_has_key_gap( struct xfs_btree_cur *cur, const union xfs_btree_key *key1, - const union xfs_btree_key *key2) + const union xfs_btree_key *key2, + const union xfs_btree_key *mask) { xfs_agblock_t next; + ASSERT(!mask || mask->alloc.ar_startblock); + next = be32_to_cpu(key1->alloc.ar_startblock) + 1; return next != be32_to_cpu(key2->alloc.ar_startblock); } diff --git a/fs/xfs/libxfs/xfs_bmap_btree.c b/fs/xfs/libxfs/xfs_bmap_btree.c index d1225b957649..81433a027912 100644 --- a/fs/xfs/libxfs/xfs_bmap_btree.c +++ b/fs/xfs/libxfs/xfs_bmap_btree.c @@ -522,10 +522,13 @@ STATIC bool xfs_bmbt_has_key_gap( struct xfs_btree_cur *cur, const union xfs_btree_key *key1, - const union xfs_btree_key *key2) + const union xfs_btree_key *key2, + const union xfs_btree_key *mask) { xfs_fileoff_t next; + ASSERT(!mask || mask->bmbt.br_startoff); + next = be64_to_cpu(key1->bmbt.br_startoff) + 1; return next != be64_to_cpu(key2->bmbt.br_startoff); } diff --git a/fs/xfs/libxfs/xfs_btree.c b/fs/xfs/libxfs/xfs_btree.c index edea6db8d8e4..6fbce2f3c17e 100644 --- a/fs/xfs/libxfs/xfs_btree.c +++ b/fs/xfs/libxfs/xfs_btree.c @@ -5020,12 +5020,33 @@ struct xfs_btree_scan_keyfill { union xfs_btree_key start_key; union xfs_btree_key end_key; + /* Mask for key comparisons, if desired. */ + union xfs_btree_key *key_mask; + /* Highest record key we've seen so far. */ union xfs_btree_key high_key; enum xfs_btree_keyfill outcome; }; +STATIC int64_t +xfs_btree_diff_two_masked_keys( + struct xfs_btree_cur *cur, + const union xfs_btree_key *key1, + const union xfs_btree_key *key2, + const union xfs_btree_key *mask) +{ + union xfs_btree_key mk1, mk2; + + if (likely(!mask)) + return cur->bc_ops->diff_two_keys(cur, key1, key2); + + cur->bc_ops->mask_key(cur, &mk1, key1, mask); + cur->bc_ops->mask_key(cur, &mk2, key2, mask); + + return cur->bc_ops->diff_two_keys(cur, &mk1, &mk2); +} + STATIC int xfs_btree_scan_keyfill_helper( struct xfs_btree_cur *cur, @@ -5043,19 +5064,22 @@ xfs_btree_scan_keyfill_helper( info->outcome = XFS_BTREE_KEYFILL_SPARSE; /* Bail if the first record starts after the start key. */ - res = cur->bc_ops->diff_two_keys(cur, &info->start_key, - &rec_key); + res = xfs_btree_diff_two_masked_keys(cur, &info->start_key, + &rec_key, info->key_mask); if (res < 0) return -ECANCELED; } else { /* Bail if there's a gap with the previous record. */ - if (cur->bc_ops->has_key_gap(cur, &info->high_key, &rec_key)) + if (cur->bc_ops->has_key_gap(cur, &info->high_key, &rec_key, + info->key_mask)) return -ECANCELED; } /* If the current record is higher than what we've seen, remember it. */ cur->bc_ops->init_high_key_from_rec(&rec_high_key, rec); - res = cur->bc_ops->diff_two_keys(cur, &rec_high_key, &info->high_key); + + res = xfs_btree_diff_two_masked_keys(cur, &rec_high_key, + &info->high_key, info->key_mask); if (res > 0) info->high_key = rec_high_key; /* struct copy */ @@ -5071,11 +5095,13 @@ xfs_btree_scan_keyfill( struct xfs_btree_cur *cur, const union xfs_btree_irec *low, const union xfs_btree_irec *high, + const union xfs_btree_irec *mask, enum xfs_btree_keyfill *outcome) { struct xfs_btree_scan_keyfill info = { .outcome = XFS_BTREE_KEYFILL_EMPTY, }; + union xfs_btree_key key_mask; int64_t res; int error; @@ -5084,6 +5110,10 @@ xfs_btree_scan_keyfill( xfs_btree_key_from_irec(cur, &info.start_key, low); xfs_btree_key_from_irec(cur, &info.end_key, high); + if (mask) { + xfs_btree_key_from_irec(cur, &key_mask, mask); + info.key_mask = &key_mask; + } error = xfs_btree_query_range(cur, low, high, xfs_btree_scan_keyfill_helper, &info); @@ -5096,7 +5126,8 @@ xfs_btree_scan_keyfill( goto out; /* Did the record set go at least as far as the end? */ - res = cur->bc_ops->diff_two_keys(cur, &info.high_key, &info.end_key); + res = xfs_btree_diff_two_masked_keys(cur, &info.high_key, + &info.end_key, info.key_mask); if (res >= 0) info.outcome = XFS_BTREE_KEYFILL_FULL; diff --git a/fs/xfs/libxfs/xfs_btree.h b/fs/xfs/libxfs/xfs_btree.h index 58a05f0d1f1b..99baa8283049 100644 --- a/fs/xfs/libxfs/xfs_btree.h +++ b/fs/xfs/libxfs/xfs_btree.h @@ -158,10 +158,17 @@ struct xfs_btree_ops { const union xfs_btree_rec *r1, const union xfs_btree_rec *r2); + /* mask a key for us */ + void (*mask_key)(struct xfs_btree_cur *cur, + union xfs_btree_key *out_key, + const union xfs_btree_key *in_key, + const union xfs_btree_key *mask); + /* decide if there's a gap in the keyspace between two keys */ bool (*has_key_gap)(struct xfs_btree_cur *cur, const union xfs_btree_key *key1, - const union xfs_btree_key *key2); + const union xfs_btree_key *key2, + const union xfs_btree_key *mask); }; /* @@ -552,6 +559,7 @@ typedef bool (*xfs_btree_key_gap_fn)(struct xfs_btree_cur *cur, int xfs_btree_scan_keyfill(struct xfs_btree_cur *cur, const union xfs_btree_irec *low, const union xfs_btree_irec *high, + const union xfs_btree_irec *mask, enum xfs_btree_keyfill *outcome); bool xfs_btree_has_more_records(struct xfs_btree_cur *cur); diff --git a/fs/xfs/libxfs/xfs_ialloc_btree.c b/fs/xfs/libxfs/xfs_ialloc_btree.c index fd48b95b4f4e..d429ca8d9dd8 100644 --- a/fs/xfs/libxfs/xfs_ialloc_btree.c +++ b/fs/xfs/libxfs/xfs_ialloc_btree.c @@ -384,11 +384,14 @@ STATIC bool xfs_inobt_has_key_gap( struct xfs_btree_cur *cur, const union xfs_btree_key *key1, - const union xfs_btree_key *key2) + const union xfs_btree_key *key2, + const union xfs_btree_key *mask) { xfs_agino_t next; - next = be32_to_cpu(key1->inobt.ir_startino) + XFS_INODES_PER_CHUNK; + ASSERT(!mask || mask->inobt.ir_startino); + + next = be32_to_cpu(key1->inobt.ir_startino) + 1; return next != be32_to_cpu(key2->inobt.ir_startino); } diff --git a/fs/xfs/libxfs/xfs_refcount.c b/fs/xfs/libxfs/xfs_refcount.c index 607fd25fda56..3ce77c9d2504 100644 --- a/fs/xfs/libxfs/xfs_refcount.c +++ b/fs/xfs/libxfs/xfs_refcount.c @@ -1785,7 +1785,7 @@ xfs_refcount_scan_keyfill( memset(&high, 0xFF, sizeof(high)); high.rc.rc_startblock = bno + len - 1; - return xfs_btree_scan_keyfill(cur, &low, &high, outcome); + return xfs_btree_scan_keyfill(cur, &low, &high, NULL, outcome); } int __init diff --git a/fs/xfs/libxfs/xfs_refcount_btree.c b/fs/xfs/libxfs/xfs_refcount_btree.c index f7982b2ecc49..301d036f7081 100644 --- a/fs/xfs/libxfs/xfs_refcount_btree.c +++ b/fs/xfs/libxfs/xfs_refcount_btree.c @@ -294,10 +294,13 @@ STATIC bool xfs_refcountbt_has_key_gap( struct xfs_btree_cur *cur, const union xfs_btree_key *key1, - const union xfs_btree_key *key2) + const union xfs_btree_key *key2, + const union xfs_btree_key *mask) { xfs_agblock_t next; + ASSERT(!mask || mask->refc.rc_startblock); + next = be32_to_cpu(key1->refc.rc_startblock) + 1; return next != be32_to_cpu(key2->refc.rc_startblock); } diff --git a/fs/xfs/libxfs/xfs_rmap.c b/fs/xfs/libxfs/xfs_rmap.c index 08d47cbf4697..4c123b6dd080 100644 --- a/fs/xfs/libxfs/xfs_rmap.c +++ b/fs/xfs/libxfs/xfs_rmap.c @@ -2685,13 +2685,18 @@ xfs_rmap_scan_keyfill( { union xfs_btree_irec low; union xfs_btree_irec high; + union xfs_btree_irec mask; + + /* Only care about space scans here */ + memset(&mask, 0, sizeof(low)); + memset(&mask.r.rm_startblock, 0xFF, sizeof(mask.r.rm_startblock)); memset(&low, 0, sizeof(low)); low.r.rm_startblock = bno; memset(&high, 0xFF, sizeof(high)); high.r.rm_startblock = bno + len - 1; - return xfs_btree_scan_keyfill(cur, &low, &high, outcome); + return xfs_btree_scan_keyfill(cur, &low, &high, &mask, outcome); } /* diff --git a/fs/xfs/libxfs/xfs_rmap_btree.c b/fs/xfs/libxfs/xfs_rmap_btree.c index d64143a842ce..9ca60f709c4b 100644 --- a/fs/xfs/libxfs/xfs_rmap_btree.c +++ b/fs/xfs/libxfs/xfs_rmap_btree.c @@ -433,16 +433,55 @@ xfs_rmapbt_recs_inorder( return 0; } +STATIC void +xfs_rmapbt_mask_key( + struct xfs_btree_cur *cur, + union xfs_btree_key *out_key, + const union xfs_btree_key *in_key, + const union xfs_btree_key *mask) +{ + memset(out_key, 0, sizeof(union xfs_btree_key)); + + if (mask->rmap.rm_startblock) + out_key->rmap.rm_startblock = in_key->rmap.rm_startblock; + if (mask->rmap.rm_owner) + out_key->rmap.rm_owner = in_key->rmap.rm_owner; + if (mask->rmap.rm_offset) + out_key->rmap.rm_offset = in_key->rmap.rm_offset; +} + STATIC bool xfs_rmapbt_has_key_gap( struct xfs_btree_cur *cur, const union xfs_btree_key *key1, - const union xfs_btree_key *key2) + const union xfs_btree_key *key2, + const union xfs_btree_key *mask) { - xfs_agblock_t next; + bool reflink = xfs_has_reflink(cur->bc_mp); + uint64_t x, y; - next = be32_to_cpu(key1->rmap.rm_startblock) + 1; - return next != be32_to_cpu(key2->rmap.rm_startblock); + if (mask->rmap.rm_offset) { + x = be64_to_cpu(key1->rmap.rm_offset) + 1; + y = be64_to_cpu(key2->rmap.rm_offset); + if ((reflink && x < y) || (!reflink && x != y)) + return true; + } + + if (mask->rmap.rm_owner) { + x = be64_to_cpu(key1->rmap.rm_owner) + 1; + y = be64_to_cpu(key2->rmap.rm_owner); + if ((reflink && x < y) || (!reflink && x != y)) + return true; + } + + if (mask->rmap.rm_startblock) { + x = be32_to_cpu(key1->rmap.rm_startblock) + 1; + y = be32_to_cpu(key2->rmap.rm_startblock); + if ((reflink && x < y) || (!reflink && x != y)) + return true; + } + + return false; } static const struct xfs_btree_ops xfs_rmapbt_ops = { @@ -465,6 +504,7 @@ static const struct xfs_btree_ops xfs_rmapbt_ops = { .keys_inorder = xfs_rmapbt_keys_inorder, .recs_inorder = xfs_rmapbt_recs_inorder, .has_key_gap = xfs_rmapbt_has_key_gap, + .mask_key = xfs_rmapbt_mask_key, }; static struct xfs_btree_cur * From patchwork Sun Oct 2 18:20:16 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Darrick J. Wong" X-Patchwork-Id: 12996959 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 17A86C433FE for ; Sun, 2 Oct 2022 18:33:00 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230088AbiJBSc6 (ORCPT ); Sun, 2 Oct 2022 14:32:58 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34622 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230084AbiJBSc5 (ORCPT ); Sun, 2 Oct 2022 14:32:57 -0400 Received: from ams.source.kernel.org (ams.source.kernel.org [IPv6:2604:1380:4601:e00::1]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 4D0B63C164 for ; Sun, 2 Oct 2022 11:32:56 -0700 (PDT) Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ams.source.kernel.org (Postfix) with ESMTPS id 97E78B80D82 for ; Sun, 2 Oct 2022 18:32:54 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 48F87C433C1; Sun, 2 Oct 2022 18:32:53 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1664735573; bh=taSlhEAeoNuhUbIbjwNe7S+YDu0JssDhAMPBUVUX/dY=; h=Subject:From:To:Cc:Date:In-Reply-To:References:From; b=lZHshC6/v+RgnUw0ml4+bQVU4oOilgmplwgwOa3InHiR/5HSHosny0HoAYl28Comb s+8fXbZo8FkmQWXs8MvNkKQ+G116wNGkPlJgx39557rSwzM/eqVEWh6xx3/YMC7maC I01aYkSHCRDDngSVrmktYd0hDgOmMr6dSYebe74WZEdaZ5QhzI6q2/OuR2NKrPkhzc kJrKPkJs2K2lZVq5UVMjszG6sJvUEjd3AJhGMSYUVGvRaTWbuXXyHziscbdb/euUtX 0lxfwGoPA8nsXVYnHRZfRvvEaudOFnOEwxl4WK/sGFIglK+2cTOhxm4weYs3sHWOtm EVidry1zuEH4A== Subject: [PATCH 4/5] xfs: check the reference counts of gaps in the refcount btree From: "Darrick J. Wong" To: djwong@kernel.org Cc: linux-xfs@vger.kernel.org Date: Sun, 02 Oct 2022 11:20:16 -0700 Message-ID: <166473481642.1084209.18220457727847413785.stgit@magnolia> In-Reply-To: <166473481572.1084209.5434516873607335909.stgit@magnolia> References: <166473481572.1084209.5434516873607335909.stgit@magnolia> User-Agent: StGit/0.19 MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-xfs@vger.kernel.org From: Darrick J. Wong Gaps in the reference count btree are also significant -- for these regions, there must not be any overlapping reverse mappings. We don't currently check this, so make the refcount scrubber more complete. Signed-off-by: Darrick J. Wong Reviewed-by: Dave Chinner --- fs/xfs/scrub/refcount.c | 84 ++++++++++++++++++++++++++++++++++++++++++++--- 1 file changed, 79 insertions(+), 5 deletions(-) diff --git a/fs/xfs/scrub/refcount.c b/fs/xfs/scrub/refcount.c index bfd48aaceb82..d97e7e372b9c 100644 --- a/fs/xfs/scrub/refcount.c +++ b/fs/xfs/scrub/refcount.c @@ -332,14 +332,69 @@ xchk_refcountbt_xref( xchk_refcountbt_xref_rmap(sc, agbno, len, refcount); } +struct xchk_refcbt_records { + /* The next AG block where we aren't expecting shared extents. */ + xfs_agblock_t next_unshared_agbno; + + /* Number of CoW blocks we expect. */ + xfs_agblock_t cow_blocks; +}; + +STATIC int +xchk_refcountbt_rmap_check_gap( + struct xfs_btree_cur *cur, + const struct xfs_rmap_irec *rec, + void *priv) +{ + xfs_agblock_t *next_bno = priv; + + if (*next_bno != NULLAGBLOCK && rec->rm_startblock < *next_bno) + return -ECANCELED; + + *next_bno = rec->rm_startblock + rec->rm_blockcount; + return 0; +} + +/* + * Make sure that a gap in the reference count records does not correspond to + * overlapping records (i.e. shared extents) in the reverse mappings. + */ +static inline void +xchk_refcountbt_xref_gaps( + struct xfs_scrub *sc, + struct xchk_refcbt_records *rrc, + xfs_agblock_t bno) +{ + struct xfs_rmap_irec low; + struct xfs_rmap_irec high; + xfs_agblock_t next_bno = NULLAGBLOCK; + int error; + + if (bno <= rrc->next_unshared_agbno || !sc->sa.rmap_cur || + xchk_skip_xref(sc->sm)) + return; + + memset(&low, 0, sizeof(low)); + low.rm_startblock = rrc->next_unshared_agbno; + memset(&high, 0xFF, sizeof(high)); + high.rm_startblock = bno - 1; + + error = xfs_rmap_query_range(sc->sa.rmap_cur, &low, &high, + xchk_refcountbt_rmap_check_gap, &next_bno); + if (error == -ECANCELED) + xchk_btree_xref_set_corrupt(sc, sc->sa.rmap_cur, 0); + else + xchk_should_check_xref(sc, &error, &sc->sa.rmap_cur); +} + /* Scrub a refcountbt record. */ STATIC int xchk_refcountbt_rec( struct xchk_btree *bs, const union xfs_btree_rec *rec) { - xfs_agblock_t *cow_blocks = bs->private; struct xfs_perag *pag = bs->cur->bc_ag.pag; + struct xchk_refcbt_records *rrc = bs->private; xfs_agblock_t bno; xfs_extlen_t len; xfs_nlink_t refcount; @@ -354,7 +409,7 @@ xchk_refcountbt_rec( if ((refcount == 1 && !has_cowflag) || (refcount != 1 && has_cowflag)) xchk_btree_set_corrupt(bs->sc, bs->cur, 0); if (has_cowflag) - (*cow_blocks) += len; + rrc->cow_blocks += len; /* Check the extent. */ bno &= ~XFS_REFC_COW_START; @@ -368,6 +423,16 @@ xchk_refcountbt_rec( xchk_refcountbt_xref(bs->sc, bno, len, refcount); + /* + * If this is a record for a shared extent, check that all blocks + * between the previous record and this one have at most one reverse + * mapping. + */ + if (!has_cowflag) { + xchk_refcountbt_xref_gaps(bs->sc, rrc, bno); + rrc->next_unshared_agbno = bno + len; + } + return 0; } @@ -409,15 +474,24 @@ int xchk_refcountbt( struct xfs_scrub *sc) { - xfs_agblock_t cow_blocks = 0; + struct xchk_refcbt_records rrc = { + .cow_blocks = 0, + .next_unshared_agbno = 0, + }; int error; error = xchk_btree(sc, sc->sa.refc_cur, xchk_refcountbt_rec, - &XFS_RMAP_OINFO_REFC, &cow_blocks); + &XFS_RMAP_OINFO_REFC, &rrc); if (error) return error; - xchk_refcount_xref_rmap(sc, cow_blocks); + /* + * Check that all blocks between the last refcount > 1 record and the + * end of the AG have at most one reverse mapping. + */ + xchk_refcountbt_xref_gaps(sc, &rrc, sc->mp->m_sb.sb_agblocks); + + xchk_refcount_xref_rmap(sc, rrc.cow_blocks); return 0; } From patchwork Sun Oct 2 18:20:16 2022 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Darrick J. Wong" X-Patchwork-Id: 12996960 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id 95891C433FE for ; Sun, 2 Oct 2022 18:33:07 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S230089AbiJBSdG (ORCPT ); Sun, 2 Oct 2022 14:33:06 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:34656 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S230084AbiJBSdG (ORCPT ); Sun, 2 Oct 2022 14:33:06 -0400 Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id EB5C73C164 for ; Sun, 2 Oct 2022 11:33:04 -0700 (PDT) Received: from smtp.kernel.org (relay.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by dfw.source.kernel.org (Postfix) with ESMTPS id 74AA760F06 for ; Sun, 2 Oct 2022 18:33:04 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id D1EF0C433C1; Sun, 2 Oct 2022 18:33:03 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1664735583; bh=9LC0Q+6q/Ui9YuTSEdv7h1fks63FG3O5KK4KLnD+bzM=; h=Subject:From:To:Cc:Date:In-Reply-To:References:From; b=bMJ0xUGbjOUHIh/6cSWh4q+rnMXweDuXoAqONSFKeG2foiDrxidcgQU9p0bPxOR8U OEl8ne53Tuvi2sXs6xIiS07gWE7aSoEH21nTUODsyoa9V8P2NmxxttZMmFXtZvkoRD 18M7TAaB97d+STMusqqszCLFIJnacjayw2X3lKpXNuay3NqnqKQc0P2rZnWHzRvAyf bBaZnopGZye1Hc2kBkSjCZtTqENFW/SbYerC2bRrrPnh5CwdKRCKQ1q0eH8Hf6jT4i llR1F1W/zGgEJNdahQvUgXE2ur0rslJoCkqpAFfdPWpYZuVRD77yQ+qlF3Drk2Uar/ P5xDbZLBrn1Mg== Subject: [PATCH 5/5] xfs: ensure that all metadata and data blocks are not cow staging extents From: "Darrick J. Wong" To: djwong@kernel.org Cc: linux-xfs@vger.kernel.org Date: Sun, 02 Oct 2022 11:20:16 -0700 Message-ID: <166473481655.1084209.12908049694500649697.stgit@magnolia> In-Reply-To: <166473481572.1084209.5434516873607335909.stgit@magnolia> References: <166473481572.1084209.5434516873607335909.stgit@magnolia> User-Agent: StGit/0.19 MIME-Version: 1.0 Precedence: bulk List-ID: X-Mailing-List: linux-xfs@vger.kernel.org From: Darrick J. Wong Make sure that all filesystem metadata blocks and file data blocks are not also marked as CoW staging extents. The extra checking added here was inspired by an actual VM host filesystem corruption incident due to bugs in the CoW handling of 4.x kernels. Signed-off-by: Darrick J. Wong Reviewed-by: Dave Chinner --- fs/xfs/scrub/agheader.c | 5 +++++ fs/xfs/scrub/alloc.c | 1 + fs/xfs/scrub/bmap.c | 11 ++++++++--- fs/xfs/scrub/ialloc.c | 2 +- fs/xfs/scrub/inode.c | 1 + fs/xfs/scrub/refcount.c | 21 +++++++++++++++++++++ fs/xfs/scrub/scrub.h | 2 ++ 7 files changed, 39 insertions(+), 4 deletions(-) diff --git a/fs/xfs/scrub/agheader.c b/fs/xfs/scrub/agheader.c index 3dd9151a20ad..520ec054e4a6 100644 --- a/fs/xfs/scrub/agheader.c +++ b/fs/xfs/scrub/agheader.c @@ -53,6 +53,7 @@ xchk_superblock_xref( xchk_xref_is_not_inode_chunk(sc, agbno, 1); xchk_xref_is_owned_by(sc, agbno, 1, &XFS_RMAP_OINFO_FS); xchk_xref_is_not_shared(sc, agbno, 1); + xchk_xref_is_not_cow_staging(sc, agbno, 1); /* scrub teardown will take care of sc->sa for us */ } @@ -517,6 +518,7 @@ xchk_agf_xref( xchk_xref_is_owned_by(sc, agbno, 1, &XFS_RMAP_OINFO_FS); xchk_agf_xref_btreeblks(sc); xchk_xref_is_not_shared(sc, agbno, 1); + xchk_xref_is_not_cow_staging(sc, agbno, 1); xchk_agf_xref_refcblks(sc); /* scrub teardown will take care of sc->sa for us */ @@ -644,6 +646,7 @@ xchk_agfl_block_xref( xchk_xref_is_not_inode_chunk(sc, agbno, 1); xchk_xref_is_owned_by(sc, agbno, 1, &XFS_RMAP_OINFO_AG); xchk_xref_is_not_shared(sc, agbno, 1); + xchk_xref_is_not_cow_staging(sc, agbno, 1); } /* Scrub an AGFL block. */ @@ -700,6 +703,7 @@ xchk_agfl_xref( xchk_xref_is_not_inode_chunk(sc, agbno, 1); xchk_xref_is_owned_by(sc, agbno, 1, &XFS_RMAP_OINFO_FS); xchk_xref_is_not_shared(sc, agbno, 1); + xchk_xref_is_not_cow_staging(sc, agbno, 1); /* * Scrub teardown will take care of sc->sa for us. Leave sc->sa @@ -855,6 +859,7 @@ xchk_agi_xref( xchk_agi_xref_icounts(sc); xchk_xref_is_owned_by(sc, agbno, 1, &XFS_RMAP_OINFO_FS); xchk_xref_is_not_shared(sc, agbno, 1); + xchk_xref_is_not_cow_staging(sc, agbno, 1); xchk_agi_xref_fiblocks(sc); /* scrub teardown will take care of sc->sa for us */ diff --git a/fs/xfs/scrub/alloc.c b/fs/xfs/scrub/alloc.c index d8f2ba7efa22..0cd20d998368 100644 --- a/fs/xfs/scrub/alloc.c +++ b/fs/xfs/scrub/alloc.c @@ -88,6 +88,7 @@ xchk_allocbt_xref( xchk_xref_is_not_inode_chunk(sc, agbno, len); xchk_xref_has_no_owner(sc, agbno, len); xchk_xref_is_not_shared(sc, agbno, len); + xchk_xref_is_not_cow_staging(sc, agbno, len); } /* Scrub a bnobt/cntbt record. */ diff --git a/fs/xfs/scrub/bmap.c b/fs/xfs/scrub/bmap.c index 5c4b25585b8c..1e4813c82cc5 100644 --- a/fs/xfs/scrub/bmap.c +++ b/fs/xfs/scrub/bmap.c @@ -328,12 +328,17 @@ xchk_bmap_iextent_xref( xchk_bmap_xref_rmap(info, irec, agbno); switch (info->whichfork) { case XFS_DATA_FORK: - if (xfs_is_reflink_inode(info->sc->ip)) - break; - fallthrough; + if (!xfs_is_reflink_inode(info->sc->ip)) + xchk_xref_is_not_shared(info->sc, agbno, + irec->br_blockcount); + xchk_xref_is_not_cow_staging(info->sc, agbno, + irec->br_blockcount); + break; case XFS_ATTR_FORK: xchk_xref_is_not_shared(info->sc, agbno, irec->br_blockcount); + xchk_xref_is_not_cow_staging(info->sc, agbno, + irec->br_blockcount); break; case XFS_COW_FORK: xchk_xref_is_cow_staging(info->sc, agbno, diff --git a/fs/xfs/scrub/ialloc.c b/fs/xfs/scrub/ialloc.c index 0b27c3520b74..efe346ddd1b7 100644 --- a/fs/xfs/scrub/ialloc.c +++ b/fs/xfs/scrub/ialloc.c @@ -116,7 +116,7 @@ xchk_iallocbt_chunk( xchk_btree_set_corrupt(bs->sc, bs->cur, 0); xchk_iallocbt_chunk_xref(bs->sc, irec, agino, bno, len); - + xchk_xref_is_not_cow_staging(bs->sc, bno, len); return true; } diff --git a/fs/xfs/scrub/inode.c b/fs/xfs/scrub/inode.c index 998bf06d2347..a68ba8684465 100644 --- a/fs/xfs/scrub/inode.c +++ b/fs/xfs/scrub/inode.c @@ -558,6 +558,7 @@ xchk_inode_xref( xchk_inode_xref_finobt(sc, ino); xchk_xref_is_owned_by(sc, agbno, 1, &XFS_RMAP_OINFO_INODES); xchk_xref_is_not_shared(sc, agbno, 1); + xchk_xref_is_not_cow_staging(sc, agbno, 1); xchk_inode_xref_bmap(sc, dip); out_free: diff --git a/fs/xfs/scrub/refcount.c b/fs/xfs/scrub/refcount.c index d97e7e372b9c..2009efea923c 100644 --- a/fs/xfs/scrub/refcount.c +++ b/fs/xfs/scrub/refcount.c @@ -562,3 +562,24 @@ xchk_xref_is_not_shared( if (keyfill != XFS_BTREE_KEYFILL_EMPTY) xchk_btree_xref_set_corrupt(sc, sc->sa.refc_cur, 0); } + +/* xref check that the extent is not being used for CoW staging. */ +void +xchk_xref_is_not_cow_staging( + struct xfs_scrub *sc, + xfs_agblock_t agbno, + xfs_extlen_t len) +{ + enum xfs_btree_keyfill keyfill; + int error; + + if (!sc->sa.refc_cur || xchk_skip_xref(sc->sm)) + return; + + error = xfs_refcount_scan_keyfill(sc->sa.refc_cur, agbno + + XFS_REFC_COW_START, len, &keyfill); + if (!xchk_should_check_xref(sc, &error, &sc->sa.refc_cur)) + return; + if (keyfill != XFS_BTREE_KEYFILL_EMPTY) + xchk_btree_xref_set_corrupt(sc, sc->sa.refc_cur, 0); +} diff --git a/fs/xfs/scrub/scrub.h b/fs/xfs/scrub/scrub.h index 85c055c2ddc5..a331838e22ff 100644 --- a/fs/xfs/scrub/scrub.h +++ b/fs/xfs/scrub/scrub.h @@ -166,6 +166,8 @@ void xchk_xref_is_cow_staging(struct xfs_scrub *sc, xfs_agblock_t bno, xfs_extlen_t len); void xchk_xref_is_not_shared(struct xfs_scrub *sc, xfs_agblock_t bno, xfs_extlen_t len); +void xchk_xref_is_not_cow_staging(struct xfs_scrub *sc, xfs_agblock_t bno, + xfs_extlen_t len); #ifdef CONFIG_XFS_RT void xchk_xref_is_used_rt_space(struct xfs_scrub *sc, xfs_rtblock_t rtbno, xfs_extlen_t len);