From patchwork Fri Dec 30 22:17:52 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: 13085088 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 E7F0CC4332F for ; Sat, 31 Dec 2022 00:16:44 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S235794AbiLaAQn (ORCPT ); Fri, 30 Dec 2022 19:16:43 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56060 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S235764AbiLaAQl (ORCPT ); Fri, 30 Dec 2022 19:16:41 -0500 Received: from sin.source.kernel.org (sin.source.kernel.org [145.40.73.55]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 13149E0C6 for ; Fri, 30 Dec 2022 16:16:41 -0800 (PST) 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 7EE11CE1A90 for ; Sat, 31 Dec 2022 00:16:39 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id BABBAC433F0; Sat, 31 Dec 2022 00:16:37 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1672445797; bh=LxOBbYJ58hvIEeCc2oxpgh6b7ZK6cVSuPM6VqKghquo=; h=Subject:From:To:Cc:Date:In-Reply-To:References:From; b=O8vV7YPSlb7nY/tNnt8yuRQ5/shEr9KoS9yscb3qTCnpw2yMa4qnok3BVPqVCfUUh JieFp6KE5+ez5SewpVtXlconpftchV2d9xI19A9wfdWy5q0zgpsdEdCn5gXU3JpFMk vq2K1hOIxOscCGJzW3JRuB0I98o5vI4VMJhlLhKq3I3qDYLX8hBzatZ2E/RAI1GqyK suEjLyuntAfP5W2fJHavHWmiqADaG3cmQfW4O4cBwbshiXG9vJxzJCNBhNX/TsuQB0 8aKGFm4veVd2dadNhCgFTkkwJeQ7wN0N5LkFDMvjNIvR2u5i9Fp88Zc21+5v2FTu4j J/VY1cMocj7Rw== Subject: [PATCH 1/5] xfs: define an in-memory btree for storing refcount bag info From: "Darrick J. Wong" To: cem@kernel.org, djwong@kernel.org Cc: linux-xfs@vger.kernel.org Date: Fri, 30 Dec 2022 14:17:52 -0800 Message-ID: <167243867261.712955.1612864255541727420.stgit@magnolia> In-Reply-To: <167243867247.712955.4006304832992035940.stgit@magnolia> References: <167243867247.712955.4006304832992035940.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 Create a new in-memory btree type so that we can store refcount bag info in a much more memory-efficient format. Signed-off-by: Darrick J. Wong --- libxfs/xfs_btree.c | 3 +++ libxfs/xfs_btree.h | 1 + libxfs/xfs_shared.h | 1 + libxfs/xfs_types.h | 6 ++++-- 4 files changed, 9 insertions(+), 2 deletions(-) diff --git a/libxfs/xfs_btree.c b/libxfs/xfs_btree.c index 8c7f51f4195..b89e8ce7797 100644 --- a/libxfs/xfs_btree.c +++ b/libxfs/xfs_btree.c @@ -1370,6 +1370,9 @@ xfs_btree_set_refs( case XFS_BTNUM_REFC: xfs_buf_set_ref(bp, XFS_REFC_BTREE_REF); break; + case XFS_BTNUM_RCBAG: + xfs_buf_set_ref(bp, XFS_RCBAG_BTREE_REF); + break; default: ASSERT(0); } diff --git a/libxfs/xfs_btree.h b/libxfs/xfs_btree.h index 7c2ff1a02dd..c795dd8ee84 100644 --- a/libxfs/xfs_btree.h +++ b/libxfs/xfs_btree.h @@ -62,6 +62,7 @@ union xfs_btree_rec { #define XFS_BTNUM_FINO ((xfs_btnum_t)XFS_BTNUM_FINOi) #define XFS_BTNUM_RMAP ((xfs_btnum_t)XFS_BTNUM_RMAPi) #define XFS_BTNUM_REFC ((xfs_btnum_t)XFS_BTNUM_REFCi) +#define XFS_BTNUM_RCBAG ((xfs_btnum_t)XFS_BTNUM_RCBAGi) struct xfs_btree_ops; uint32_t xfs_btree_magic(struct xfs_mount *mp, const struct xfs_btree_ops *ops); diff --git a/libxfs/xfs_shared.h b/libxfs/xfs_shared.h index d1b3f210326..eaabfa52eda 100644 --- a/libxfs/xfs_shared.h +++ b/libxfs/xfs_shared.h @@ -128,6 +128,7 @@ void xfs_log_get_max_trans_res(struct xfs_mount *mp, #define XFS_ATTR_BTREE_REF 1 #define XFS_DQUOT_REF 1 #define XFS_REFC_BTREE_REF 1 +#define XFS_RCBAG_BTREE_REF 1 #define XFS_SSB_REF 0 /* diff --git a/libxfs/xfs_types.h b/libxfs/xfs_types.h index c2868e8b6a1..9a4019f23dd 100644 --- a/libxfs/xfs_types.h +++ b/libxfs/xfs_types.h @@ -116,7 +116,8 @@ typedef enum { */ typedef enum { XFS_BTNUM_BNOi, XFS_BTNUM_CNTi, XFS_BTNUM_RMAPi, XFS_BTNUM_BMAPi, - XFS_BTNUM_INOi, XFS_BTNUM_FINOi, XFS_BTNUM_REFCi, XFS_BTNUM_MAX + XFS_BTNUM_INOi, XFS_BTNUM_FINOi, XFS_BTNUM_REFCi, XFS_BTNUM_RCBAGi, + XFS_BTNUM_MAX } xfs_btnum_t; #define XFS_BTNUM_STRINGS \ @@ -126,7 +127,8 @@ typedef enum { { XFS_BTNUM_BMAPi, "bmbt" }, \ { XFS_BTNUM_INOi, "inobt" }, \ { XFS_BTNUM_FINOi, "finobt" }, \ - { XFS_BTNUM_REFCi, "refcbt" } + { XFS_BTNUM_REFCi, "refcbt" }, \ + { XFS_BTNUM_RCBAGi, "rcbagbt" } struct xfs_name { const unsigned char *name; From patchwork Fri Dec 30 22:17:52 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: 13085089 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 81B7AC4332F for ; Sat, 31 Dec 2022 00:17:13 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S235764AbiLaARM (ORCPT ); Fri, 30 Dec 2022 19:17:12 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56176 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S235899AbiLaAQ5 (ORCPT ); Fri, 30 Dec 2022 19:16:57 -0500 Received: from ams.source.kernel.org (ams.source.kernel.org [IPv6:2604:1380:4601:e00::1]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id E84CCE0D8 for ; Fri, 30 Dec 2022 16:16:55 -0800 (PST) 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 8723CB81E65 for ; Sat, 31 Dec 2022 00:16:54 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 47F6AC433EF; Sat, 31 Dec 2022 00:16:53 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1672445813; bh=oZpSNjQtQogkJeOe4slVHSPl+iok0PJ28vPUcvkoC2E=; h=Subject:From:To:Cc:Date:In-Reply-To:References:From; b=T+CU1G9t2zfx0Ijb0tt0gaQ+RCIvRE1XfIIP0yeoE4Nzd4FINilUfMm2ozd9Bpbti yUuscgVV8rpb1C9SY649VhDvDexQaU6k83lwb0V+XljQC0Pu5q+tQKJA6Y85Iwszep e4MpW8UQED5mn/aL/eCZB2K070wrvhx+7tGKR8tmURKlUThrnVSmtfV+mIjLgUZ0y8 RxqMcSxZQ/Xboei04OMZ1W20r9CeybXW9LIinGUpCmMAcHuhDJu2ThLczadmgnwDYy b7OUw8Vl3A5+UJBvIoTWWuf8x/aih0vOhXE6q+Rff+P02O/uruLxtzHcQwqb/NLFm/ iY+Ns2P3oLhqg== Subject: [PATCH 2/5] xfs_repair: define an in-memory btree for storing refcount bag info From: "Darrick J. Wong" To: cem@kernel.org, djwong@kernel.org Cc: linux-xfs@vger.kernel.org Date: Fri, 30 Dec 2022 14:17:52 -0800 Message-ID: <167243867273.712955.95429914256475046.stgit@magnolia> In-Reply-To: <167243867247.712955.4006304832992035940.stgit@magnolia> References: <167243867247.712955.4006304832992035940.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 Create a new in-memory btree type so that we can store refcount bag info in a much more memory-efficient format. Signed-off-by: Darrick J. Wong --- libxfs/libxfs_api_defs.h | 3 repair/Makefile | 2 repair/rcbag_btree.c | 335 ++++++++++++++++++++++++++++++++++++++++++++++ repair/rcbag_btree.h | 71 ++++++++++ 4 files changed, 411 insertions(+) create mode 100644 repair/rcbag_btree.c create mode 100644 repair/rcbag_btree.h diff --git a/libxfs/libxfs_api_defs.h b/libxfs/libxfs_api_defs.h index a03cef515a2..df614182b7b 100644 --- a/libxfs/libxfs_api_defs.h +++ b/libxfs/libxfs_api_defs.h @@ -55,6 +55,7 @@ #define xfs_btree_bload libxfs_btree_bload #define xfs_btree_bload_compute_geometry libxfs_btree_bload_compute_geometry +#define xfs_btree_calc_size libxfs_btree_calc_size #define xfs_btree_decrement libxfs_btree_decrement #define xfs_btree_del_cursor libxfs_btree_del_cursor #define xfs_btree_get_block libxfs_btree_get_block @@ -62,8 +63,10 @@ #define xfs_btree_has_more_records libxfs_btree_has_more_records #define xfs_btree_increment libxfs_btree_increment #define xfs_btree_init_block libxfs_btree_init_block +#define xfs_btree_mem_head_nlevels libxfs_btree_mem_head_nlevels #define xfs_btree_mem_head_read_buf libxfs_btree_mem_head_read_buf #define xfs_btree_rec_addr libxfs_btree_rec_addr +#define xfs_btree_space_to_height libxfs_btree_space_to_height #define xfs_btree_visit_blocks libxfs_btree_visit_blocks #define xfs_buf_delwri_submit libxfs_buf_delwri_submit #define xfs_buf_get libxfs_buf_get diff --git a/repair/Makefile b/repair/Makefile index e5014deb0ce..5ea8d9618e7 100644 --- a/repair/Makefile +++ b/repair/Makefile @@ -28,6 +28,7 @@ HFILES = \ progress.h \ protos.h \ quotacheck.h \ + rcbag_btree.h \ rmap.h \ rt.h \ scan.h \ @@ -64,6 +65,7 @@ CFILES = \ prefetch.c \ progress.c \ quotacheck.c \ + rcbag_btree.c \ rmap.c \ rt.c \ sb.c \ diff --git a/repair/rcbag_btree.c b/repair/rcbag_btree.c new file mode 100644 index 00000000000..c86189806c8 --- /dev/null +++ b/repair/rcbag_btree.c @@ -0,0 +1,335 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/* + * Copyright (C) 2022 Oracle. All Rights Reserved. + * Author: Darrick J. Wong + */ +#include "libxfs.h" +#include "btree.h" +#include "err_protos.h" +#include "libxlog.h" +#include "incore.h" +#include "globals.h" +#include "dinode.h" +#include "slab.h" +#include "libfrog/bitmap.h" +#include "libxfs/xfile.h" +#include "libxfs/xfbtree.h" +#include "libxfs/xfs_btree_mem.h" +#include "rcbag_btree.h" + +static struct kmem_cache *rcbagbt_cur_cache; + +STATIC void +rcbagbt_init_key_from_rec( + union xfs_btree_key *key, + const union xfs_btree_rec *rec) +{ + struct rcbag_key *bag_key = (struct rcbag_key *)key; + const struct rcbag_rec *bag_rec = (const struct rcbag_rec *)rec; + + BUILD_BUG_ON(sizeof(struct rcbag_key) > sizeof(union xfs_btree_key)); + BUILD_BUG_ON(sizeof(struct rcbag_rec) > sizeof(union xfs_btree_rec)); + + bag_key->rbg_startblock = bag_rec->rbg_startblock; + bag_key->rbg_blockcount = bag_rec->rbg_blockcount; + bag_key->rbg_ino = bag_rec->rbg_ino; +} + +STATIC void +rcbagbt_init_rec_from_cur( + struct xfs_btree_cur *cur, + union xfs_btree_rec *rec) +{ + struct rcbag_rec *bag_rec = (struct rcbag_rec *)rec; + struct rcbag_rec *bag_irec = (struct rcbag_rec *)&cur->bc_rec; + + bag_rec->rbg_startblock = bag_irec->rbg_startblock; + bag_rec->rbg_blockcount = bag_irec->rbg_blockcount; + bag_rec->rbg_ino = bag_irec->rbg_ino; + bag_rec->rbg_refcount = bag_irec->rbg_refcount; +} + +STATIC int64_t +rcbagbt_key_diff( + struct xfs_btree_cur *cur, + const union xfs_btree_key *key) +{ + struct rcbag_rec *rec = (struct rcbag_rec *)&cur->bc_rec; + const struct rcbag_key *kp = (const struct rcbag_key *)key; + + if (kp->rbg_startblock > rec->rbg_startblock) + return 1; + if (kp->rbg_startblock < rec->rbg_startblock) + return -1; + + if (kp->rbg_blockcount > rec->rbg_blockcount) + return 1; + if (kp->rbg_blockcount < rec->rbg_blockcount) + return -1; + + if (kp->rbg_ino > rec->rbg_ino) + return 1; + if (kp->rbg_ino < rec->rbg_ino) + return -1; + + return 0; +} + +STATIC int64_t +rcbagbt_diff_two_keys( + struct xfs_btree_cur *cur, + const union xfs_btree_key *k1, + const union xfs_btree_key *k2, + const union xfs_btree_key *mask) +{ + const struct rcbag_key *kp1 = (const struct rcbag_key *)k1; + const struct rcbag_key *kp2 = (const struct rcbag_key *)k2; + + ASSERT(mask == NULL); + + if (kp1->rbg_startblock > kp2->rbg_startblock) + return 1; + if (kp1->rbg_startblock < kp2->rbg_startblock) + return -1; + + if (kp1->rbg_blockcount > kp2->rbg_blockcount) + return 1; + if (kp1->rbg_blockcount < kp2->rbg_blockcount) + return -1; + + if (kp1->rbg_ino > kp2->rbg_ino) + return 1; + if (kp1->rbg_ino < kp2->rbg_ino) + return -1; + + return 0; +} + +STATIC int +rcbagbt_keys_inorder( + struct xfs_btree_cur *cur, + const union xfs_btree_key *k1, + const union xfs_btree_key *k2) +{ + const struct rcbag_key *kp1 = (const struct rcbag_key *)k1; + const struct rcbag_key *kp2 = (const struct rcbag_key *)k2; + + if (kp1->rbg_startblock > kp2->rbg_startblock) + return 0; + if (kp1->rbg_startblock < kp2->rbg_startblock) + return 1; + + if (kp1->rbg_blockcount > kp2->rbg_blockcount) + return 0; + if (kp1->rbg_blockcount < kp2->rbg_blockcount) + return 1; + + if (kp1->rbg_ino > kp2->rbg_ino) + return 0; + if (kp1->rbg_ino < kp2->rbg_ino) + return 1; + + return 0; +} + +STATIC int +rcbagbt_recs_inorder( + struct xfs_btree_cur *cur, + const union xfs_btree_rec *r1, + const union xfs_btree_rec *r2) +{ + const struct rcbag_rec *rp1 = (const struct rcbag_rec *)r1; + const struct rcbag_rec *rp2 = (const struct rcbag_rec *)r2; + + if (rp1->rbg_startblock > rp2->rbg_startblock) + return 0; + if (rp1->rbg_startblock < rp2->rbg_startblock) + return 1; + + if (rp1->rbg_blockcount > rp2->rbg_blockcount) + return 0; + if (rp1->rbg_blockcount < rp2->rbg_blockcount) + return 1; + + if (rp1->rbg_ino > rp2->rbg_ino) + return 0; + if (rp1->rbg_ino < rp2->rbg_ino) + return 1; + + return 0; +} + +static xfs_failaddr_t +rcbagbt_verify( + struct xfs_buf *bp) +{ + struct xfs_mount *mp = bp->b_mount; + struct xfs_btree_block *block = XFS_BUF_TO_BLOCK(bp); + xfs_failaddr_t fa; + unsigned int level; + + if (!xfs_verify_magic(bp, block->bb_magic)) + return __this_address; + + fa = xfs_btree_lblock_v5hdr_verify(bp, XFS_RMAP_OWN_UNKNOWN); + if (fa) + return fa; + + level = be16_to_cpu(block->bb_level); + if (level >= rcbagbt_maxlevels_possible()) + return __this_address; + + return xfbtree_lblock_verify(bp, + rcbagbt_maxrecs(mp, xfo_to_b(1), level == 0)); +} + +static void +rcbagbt_rw_verify( + struct xfs_buf *bp) +{ + xfs_failaddr_t fa = rcbagbt_verify(bp); + + if (fa) + do_error(_("refcount bag btree block 0x%llx corrupted at %p\n"), + (unsigned long long)xfs_buf_daddr(bp), fa); +} + +/* skip crc checks on in-memory btrees to save time */ +static const struct xfs_buf_ops rcbagbt_mem_buf_ops = { + .name = "rcbagbt_mem", + .magic = { 0, cpu_to_be32(RCBAG_MAGIC) }, + .verify_read = rcbagbt_rw_verify, + .verify_write = rcbagbt_rw_verify, + .verify_struct = rcbagbt_verify, +}; + +static const struct xfs_btree_ops rcbagbt_mem_ops = { + .rec_len = sizeof(struct rcbag_rec), + .key_len = sizeof(struct rcbag_key), + .geom_flags = XFS_BTREE_CRC_BLOCKS | XFS_BTREE_LONG_PTRS | + XFS_BTREE_IN_MEMORY, + + .dup_cursor = xfbtree_dup_cursor, + .set_root = xfbtree_set_root, + .alloc_block = xfbtree_alloc_block, + .free_block = xfbtree_free_block, + .get_minrecs = xfbtree_get_minrecs, + .get_maxrecs = xfbtree_get_maxrecs, + .init_key_from_rec = rcbagbt_init_key_from_rec, + .init_rec_from_cur = rcbagbt_init_rec_from_cur, + .init_ptr_from_cur = xfbtree_init_ptr_from_cur, + .key_diff = rcbagbt_key_diff, + .buf_ops = &rcbagbt_mem_buf_ops, + .diff_two_keys = rcbagbt_diff_two_keys, + .keys_inorder = rcbagbt_keys_inorder, + .recs_inorder = rcbagbt_recs_inorder, +}; + +/* Create a cursor for an in-memory btree. */ +struct xfs_btree_cur * +rcbagbt_mem_cursor( + struct xfs_mount *mp, + struct xfs_trans *tp, + struct xfs_buf *head_bp, + struct xfbtree *xfbtree) +{ + struct xfs_btree_cur *cur; + + cur = xfs_btree_alloc_cursor(mp, tp, XFS_BTNUM_RCBAG, &rcbagbt_mem_ops, + rcbagbt_maxlevels_possible(), rcbagbt_cur_cache); + + cur->bc_mem.xfbtree = xfbtree; + cur->bc_mem.head_bp = head_bp; + cur->bc_nlevels = libxfs_btree_mem_head_nlevels(head_bp); + return cur; +} + +/* Create an in-memory refcount bag btree. */ +int +rcbagbt_mem_create( + struct xfs_mount *mp, + struct xfs_buftarg *target, + struct xfbtree **xfbtreep) +{ + struct xfbtree_config cfg = { + .btree_ops = &rcbagbt_mem_ops, + .target = target, + }; + + return -xfbtree_create(mp, &cfg, xfbtreep); +} + +/* Calculate number of records in a refcount bag btree block. */ +static inline unsigned int +rcbagbt_block_maxrecs( + unsigned int blocklen, + bool leaf) +{ + if (leaf) + return blocklen / sizeof(struct rcbag_rec); + return blocklen / + (sizeof(struct rcbag_key) + sizeof(rcbag_ptr_t)); +} + +/* + * Calculate number of records in an refcount bag btree block. + */ +unsigned int +rcbagbt_maxrecs( + struct xfs_mount *mp, + unsigned int blocklen, + bool leaf) +{ + blocklen -= RCBAG_BLOCK_LEN; + return rcbagbt_block_maxrecs(blocklen, leaf); +} + +#define RCBAGBT_INIT_MINRECS(minrecs) \ + do { \ + unsigned int blocklen; \ + \ + blocklen = getpagesize() - XFS_BTREE_LBLOCK_CRC_LEN; \ + \ + minrecs[0] = rcbagbt_block_maxrecs(blocklen, true) / 2; \ + minrecs[1] = rcbagbt_block_maxrecs(blocklen, false) / 2; \ + } while (0) + +/* Compute the max possible height for refcount bag btrees. */ +unsigned int +rcbagbt_maxlevels_possible(void) +{ + unsigned int minrecs[2]; + + RCBAGBT_INIT_MINRECS(minrecs); + return libxfs_btree_space_to_height(minrecs, ULLONG_MAX); +} + +/* Calculate the refcount bag btree size for some records. */ +unsigned long long +rcbagbt_calc_size( + unsigned long long nr_records) +{ + unsigned int minrecs[2]; + + RCBAGBT_INIT_MINRECS(minrecs); + return libxfs_btree_calc_size(minrecs, nr_records); +} + +int __init +rcbagbt_init_cur_cache(void) +{ + rcbagbt_cur_cache = kmem_cache_create("rcbagbt_cur", + xfs_btree_cur_sizeof(rcbagbt_maxlevels_possible()), + 0, 0, NULL); + + if (!rcbagbt_cur_cache) + return ENOMEM; + return 0; +} + +void +rcbagbt_destroy_cur_cache(void) +{ + kmem_cache_destroy(rcbagbt_cur_cache); + rcbagbt_cur_cache = NULL; +} diff --git a/repair/rcbag_btree.h b/repair/rcbag_btree.h new file mode 100644 index 00000000000..21329153baf --- /dev/null +++ b/repair/rcbag_btree.h @@ -0,0 +1,71 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/* + * Copyright (C) 2022 Oracle. All Rights Reserved. + * Author: Darrick J. Wong + */ +#ifndef __RCBAG_BTREE_H__ +#define __RCBAG_BTREE_H__ + +struct xfs_buf; +struct xfs_btree_cur; +struct xfs_mount; + +#define RCBAG_MAGIC 0x74826671 /* 'JRBG' */ + +struct rcbag_key { + uint32_t rbg_startblock; + uint32_t rbg_blockcount; + uint64_t rbg_ino; +}; + +struct rcbag_rec { + uint32_t rbg_startblock; + uint32_t rbg_blockcount; + uint64_t rbg_ino; + uint64_t rbg_refcount; +}; + +typedef __be64 rcbag_ptr_t; + +/* reflinks only exist on crc enabled filesystems */ +#define RCBAG_BLOCK_LEN XFS_BTREE_LBLOCK_CRC_LEN + +/* + * Record, key, and pointer address macros for btree blocks. + * + * (note that some of these may appear unused, but they are used in userspace) + */ +#define RCBAG_REC_ADDR(block, index) \ + ((struct rcbag_rec *) \ + ((char *)(block) + RCBAG_BLOCK_LEN + \ + (((index) - 1) * sizeof(struct rcbag_rec)))) + +#define RCBAG_KEY_ADDR(block, index) \ + ((struct rcbag_key *) \ + ((char *)(block) + RCBAG_BLOCK_LEN + \ + ((index) - 1) * sizeof(struct rcbag_key))) + +#define RCBAG_PTR_ADDR(block, index, maxrecs) \ + ((rcbag_ptr_t *) \ + ((char *)(block) + RCBAG_BLOCK_LEN + \ + (maxrecs) * sizeof(struct rcbag_key) + \ + ((index) - 1) * sizeof(rcbag_ptr_t))) + +unsigned int rcbagbt_maxrecs(struct xfs_mount *mp, unsigned int blocklen, + bool leaf); + +unsigned long long rcbagbt_calc_size(unsigned long long nr_records); + +unsigned int rcbagbt_maxlevels_possible(void); + +int __init rcbagbt_init_cur_cache(void); +void rcbagbt_destroy_cur_cache(void); + +struct xfbtree; +struct xfs_btree_cur *rcbagbt_mem_cursor(struct xfs_mount *mp, + struct xfs_trans *tp, struct xfs_buf *head_bp, + struct xfbtree *xfbtree); +int rcbagbt_mem_create(struct xfs_mount *mp, struct xfs_buftarg *target, + struct xfbtree **xfbtreep); + +#endif /* __RCBAG_BTREE_H__ */ From patchwork Fri Dec 30 22:17:52 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: 13085090 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 2CD5FC3DA7C for ; Sat, 31 Dec 2022 00:17:14 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S235880AbiLaARN (ORCPT ); Fri, 30 Dec 2022 19:17:13 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56242 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S235952AbiLaARL (ORCPT ); Fri, 30 Dec 2022 19:17:11 -0500 Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 15C9BE0D8 for ; Fri, 30 Dec 2022 16:17:10 -0800 (PST) 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 76E0F61D04 for ; Sat, 31 Dec 2022 00:17:09 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id CF8E3C433D2; Sat, 31 Dec 2022 00:17:08 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1672445828; bh=EtUw+YoFm42sbe8L6vnQo59vLWNjd6xt34Gef27kgO4=; h=Subject:From:To:Cc:Date:In-Reply-To:References:From; b=pqpNrpXMsvEVSDnHfF1krk3jrrcbxv0lVqQ/I7bUZK8qQ/15dNdkpDYoc3nSrIeWB 18h7s1dfhXkrqsfqE42Qf0rmaelZfsDpkAN/jYA5IbQT1orc3OWvhWQA0LNLhKJjmq 0WAK0Vh46VnJY28cmyvydew6qbJ4KdW/A+m7l+jE5znH9k2E9f07GuMlOAQb1Oa+Th KiJCvg6lHb7H62tPNZ+XYIdmtYZRzqmx14P8cHtrDYyeO+Egm8/4/3omc+2/Mm10T4 EZAJRgN3iQgJLzB8zkNL5mJk74xdbSjfW5l9UgHBx4ZQpGRaUr0CwLui8H/iFY5np8 lnHxEw4biXTmQ== Subject: [PATCH 3/5] xfs_repair: create refcount bag From: "Darrick J. Wong" To: cem@kernel.org, djwong@kernel.org Cc: linux-xfs@vger.kernel.org Date: Fri, 30 Dec 2022 14:17:52 -0800 Message-ID: <167243867284.712955.10005379733633399092.stgit@magnolia> In-Reply-To: <167243867247.712955.4006304832992035940.stgit@magnolia> References: <167243867247.712955.4006304832992035940.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 Create a bag structure for refcount information that uses the refcount bag btree defined in the previous patch. Signed-off-by: Darrick J. Wong --- libxfs/libxfs_api_defs.h | 5 + repair/Makefile | 2 repair/rcbag.c | 404 ++++++++++++++++++++++++++++++++++++++++++++++ repair/rcbag.h | 33 ++++ repair/rcbag_btree.c | 59 +++++++ repair/rcbag_btree.h | 7 + 6 files changed, 510 insertions(+) create mode 100644 repair/rcbag.c create mode 100644 repair/rcbag.h diff --git a/libxfs/libxfs_api_defs.h b/libxfs/libxfs_api_defs.h index df614182b7b..aa71914af97 100644 --- a/libxfs/libxfs_api_defs.h +++ b/libxfs/libxfs_api_defs.h @@ -58,14 +58,19 @@ #define xfs_btree_calc_size libxfs_btree_calc_size #define xfs_btree_decrement libxfs_btree_decrement #define xfs_btree_del_cursor libxfs_btree_del_cursor +#define xfs_btree_delete libxfs_btree_delete #define xfs_btree_get_block libxfs_btree_get_block +#define xfs_btree_get_rec libxfs_btree_get_rec #define xfs_btree_goto_left_edge libxfs_btree_goto_left_edge #define xfs_btree_has_more_records libxfs_btree_has_more_records #define xfs_btree_increment libxfs_btree_increment #define xfs_btree_init_block libxfs_btree_init_block +#define xfs_btree_insert libxfs_btree_insert +#define xfs_btree_lookup libxfs_btree_lookup #define xfs_btree_mem_head_nlevels libxfs_btree_mem_head_nlevels #define xfs_btree_mem_head_read_buf libxfs_btree_mem_head_read_buf #define xfs_btree_rec_addr libxfs_btree_rec_addr +#define xfs_btree_update libxfs_btree_update #define xfs_btree_space_to_height libxfs_btree_space_to_height #define xfs_btree_visit_blocks libxfs_btree_visit_blocks #define xfs_buf_delwri_submit libxfs_buf_delwri_submit diff --git a/repair/Makefile b/repair/Makefile index 5ea8d9618e7..250c86cca2d 100644 --- a/repair/Makefile +++ b/repair/Makefile @@ -29,6 +29,7 @@ HFILES = \ protos.h \ quotacheck.h \ rcbag_btree.h \ + rcbag.h \ rmap.h \ rt.h \ scan.h \ @@ -66,6 +67,7 @@ CFILES = \ progress.c \ quotacheck.c \ rcbag_btree.c \ + rcbag.c \ rmap.c \ rt.c \ sb.c \ diff --git a/repair/rcbag.c b/repair/rcbag.c new file mode 100644 index 00000000000..04958cba460 --- /dev/null +++ b/repair/rcbag.c @@ -0,0 +1,404 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/* + * Copyright (C) 2022 Oracle. All Rights Reserved. + * Author: Darrick J. Wong + */ +#include "libxfs.h" +#include "btree.h" +#include "err_protos.h" +#include "libxlog.h" +#include "incore.h" +#include "globals.h" +#include "dinode.h" +#include "slab.h" +#include "libfrog/bitmap.h" +#include "libxfs/xfile.h" +#include "libxfs/xfbtree.h" +#include "libxfs/xfs_btree_mem.h" +#include "rcbag_btree.h" +#include "rcbag.h" + +struct rcbag { + struct xfs_mount *mp; + struct xfbtree *xfbtree; + uint64_t nr_items; +}; + +int +rcbag_init( + struct xfs_mount *mp, + uint64_t max_rmaps, + struct rcbag **bagp) +{ + struct xfile *xfile; + struct xfs_buftarg *target; + struct rcbag *bag; + unsigned long long maxbytes; + int error; + + bag = malloc(sizeof(struct rcbag)); + if (!bag) + return ENOMEM; + + bag->nr_items = 0; + bag->mp = mp; + + /* Need to save space for the head block */ + maxbytes = (1 + rcbagbt_calc_size(max_rmaps)) * getpagesize(); + error = -xfile_create(mp, maxbytes, "refcount bag", &xfile); + if (error) + goto out_bag; + + error = -libxfs_alloc_memory_buftarg(mp, xfile, &target); + if (error) + goto out_xfile; + + error = rcbagbt_mem_create(mp, target, &bag->xfbtree); + if (error) + goto out_buftarg; + + *bagp = bag; + return 0; + +out_buftarg: + libxfs_buftarg_free(target); +out_xfile: + xfile_destroy(xfile); +out_bag: + free(bag); + return error; +} + +void +rcbag_free( + struct rcbag **bagp) +{ + struct rcbag *bag = *bagp; + struct xfile *xfile; + struct xfs_buftarg *target; + + target = bag->xfbtree->target; + xfile = target->bt_xfile; + + xfbtree_destroy(bag->xfbtree); + libxfs_buftarg_free(target); + xfile_destroy(xfile); + + free(bag); + *bagp = NULL; +} + +/* Track an rmap in the refcount bag. */ +void +rcbag_add( + struct rcbag *bag, + const struct xfs_rmap_irec *rmap) +{ + struct rcbag_rec bagrec; + struct xfs_mount *mp = bag->mp; + struct xfs_trans *tp; + struct xfs_buf *head_bp; + struct xfs_btree_cur *cur; + int has; + int error; + + error = -libxfs_trans_alloc_empty(mp, &tp); + if (error) + do_error(_("allocating tx for refcount bag update\n")); + + error = -xfbtree_head_read_buf(bag->xfbtree, tp, &head_bp); + if (error) + do_error(_("reading refcount bag header\n")); + + cur = rcbagbt_mem_cursor(mp, tp, head_bp, bag->xfbtree); + error = rcbagbt_lookup_eq(cur, rmap, &has); + if (error) + do_error(_("looking up refcount bag records\n")); + + if (has) { + error = rcbagbt_get_rec(cur, &bagrec, &has); + if (error || !has) + do_error(_("reading refcount bag records\n")); + + bagrec.rbg_refcount++; + error = rcbagbt_update(cur, &bagrec); + if (error) + do_error(_("updating refcount bag record\n")); + } else { + bagrec.rbg_startblock = rmap->rm_startblock; + bagrec.rbg_blockcount = rmap->rm_blockcount; + bagrec.rbg_ino = rmap->rm_owner; + bagrec.rbg_refcount = 1; + + error = rcbagbt_insert(cur, &bagrec, &has); + if (error || !has) + do_error(_("adding refcount bag record, err %d\n"), + error); + } + + libxfs_btree_del_cursor(cur, error); + libxfs_trans_brelse(tp, head_bp); + + error = -xfbtree_trans_commit(bag->xfbtree, tp); + if (error) + do_error(_("committing refcount bag record\n")); + + libxfs_trans_cancel(tp); + bag->nr_items++; +} + +uint64_t +rcbag_count( + const struct rcbag *rcbag) +{ + return rcbag->nr_items; +} + +#define BAGREC_NEXT(r) ((r)->rbg_startblock + (r)->rbg_blockcount) + +/* + * Find the next block where the refcount changes, given the next rmap we + * looked at and the ones we're already tracking. + */ +void +rcbag_next_edge( + struct rcbag *bag, + const struct xfs_rmap_irec *next_rmap, + bool next_valid, + uint32_t *next_bnop) +{ + struct rcbag_rec bagrec; + struct xfs_mount *mp = bag->mp; + struct xfs_buf *head_bp; + struct xfs_btree_cur *cur; + uint32_t next_bno = NULLAGBLOCK; + int has; + int error; + + if (next_valid) + next_bno = next_rmap->rm_startblock; + + error = -xfbtree_head_read_buf(bag->xfbtree, NULL, &head_bp); + if (error) + do_error(_("reading refcount bag header\n")); + + cur = rcbagbt_mem_cursor(mp, NULL, head_bp, bag->xfbtree); + error = -libxfs_btree_goto_left_edge(cur); + if (error) + do_error(_("seeking refcount bag btree cursor\n")); + + while (true) { + error = -libxfs_btree_increment(cur, 0, &has); + if (error) + do_error(_("incrementing refcount bag btree cursor\n")); + if (!has) + break; + + error = rcbagbt_get_rec(cur, &bagrec, &has); + if (error) + do_error(_("reading refcount bag btree record\n")); + if (!has) + do_error(_("refcount bag btree record disappeared?\n")); + + next_bno = min(next_bno, BAGREC_NEXT(&bagrec)); + } + + /* + * We should have found /something/ because either next_rrm is the next + * interesting rmap to look at after emitting this refcount extent, or + * there are other rmaps in rmap_bag contributing to the current + * sharing count. But if something is seriously wrong, bail out. + */ + if (next_bno == NULLAGBLOCK) + do_error(_("next refcount bag edge not found?\n")); + + *next_bnop = next_bno; + + libxfs_btree_del_cursor(cur, error); + libxfs_trans_brelse(NULL, head_bp); +} + +/* Pop all refcount bag records that end at next_bno */ +void +rcbag_remove_ending_at( + struct rcbag *bag, + uint32_t next_bno) +{ + struct rcbag_rec bagrec; + struct xfs_mount *mp = bag->mp; + struct xfs_trans *tp; + struct xfs_buf *head_bp; + struct xfs_btree_cur *cur; + int has; + int error; + + error = -libxfs_trans_alloc_empty(mp, &tp); + if (error) + do_error(_("allocating tx for refcount bag update\n")); + + error = -xfbtree_head_read_buf(bag->xfbtree, tp, &head_bp); + if (error) + do_error(_("reading refcount bag header\n")); + + /* go to the right edge of the tree */ + cur = rcbagbt_mem_cursor(mp, tp, head_bp, bag->xfbtree); + memset(&cur->bc_rec, 0xFF, sizeof(cur->bc_rec)); + error = -libxfs_btree_lookup(cur, XFS_LOOKUP_GE, &has); + if (error) + do_error(_("seeking refcount bag btree cursor\n")); + + while (true) { + error = -libxfs_btree_decrement(cur, 0, &has); + if (error) + do_error(_("decrementing refcount bag btree cursor\n")); + if (!has) + break; + + error = rcbagbt_get_rec(cur, &bagrec, &has); + if (error) + do_error(_("reading refcount bag btree record\n")); + if (!has) + do_error(_("refcount bag btree record disappeared?\n")); + + if (BAGREC_NEXT(&bagrec) != next_bno) + continue; + + error = -libxfs_btree_delete(cur, &has); + if (error) + do_error(_("deleting refcount bag btree record, err %d\n"), + error); + if (!has) + do_error(_("couldn't delete refcount bag record?\n")); + + bag->nr_items -= bagrec.rbg_refcount; + } + + libxfs_btree_del_cursor(cur, error); + libxfs_trans_brelse(tp, head_bp); + + error = -xfbtree_trans_commit(bag->xfbtree, tp); + if (error) + do_error(_("committing refcount bag deletions\n")); + + libxfs_trans_cancel(tp); +} + +/* Prepare to iterate the shared inodes tracked by the refcount bag. */ +void +rcbag_ino_iter_start( + struct rcbag *bag, + struct rcbag_iter *iter) +{ + struct xfs_mount *mp = bag->mp; + int error; + + memset(iter, 0, sizeof(struct rcbag_iter)); + + if (bag->nr_items < 2) + return; + + error = -xfbtree_head_read_buf(bag->xfbtree, NULL, &iter->head_bp); + if (error) + do_error(_("reading refcount bag header\n")); + + iter->cur = rcbagbt_mem_cursor(mp, NULL, iter->head_bp, bag->xfbtree); + error = -libxfs_btree_goto_left_edge(iter->cur); + if (error) + do_error(_("seeking refcount bag btree cursor\n")); +} + +/* Tear down an iteration. */ +void +rcbag_ino_iter_stop( + struct rcbag *bag, + struct rcbag_iter *iter) +{ + if (iter->cur) + libxfs_btree_del_cursor(iter->cur, XFS_BTREE_NOERROR); + if (iter->head_bp) + libxfs_trans_brelse(NULL, iter->head_bp); + iter->cur = NULL; + iter->head_bp = NULL; +} + +/* + * Walk all the shared inodes tracked by the refcount bag. Returns 1 when + * returning a valid iter.ino, and 0 if iteration has completed. The iter + * should be initialized to zeroes before the first call. + */ +int +rcbag_ino_iter( + struct rcbag *bag, + struct rcbag_iter *iter) +{ + struct rcbag_rec bagrec; + int has; + int error; + + if (bag->nr_items < 2) + return 0; + + do { + error = -libxfs_btree_increment(iter->cur, 0, &has); + if (error) + do_error(_("incrementing refcount bag btree cursor\n")); + if (!has) + return 0; + + error = rcbagbt_get_rec(iter->cur, &bagrec, &has); + if (error) + do_error(_("reading refcount bag btree record\n")); + if (!has) + do_error(_("refcount bag btree record disappeared?\n")); + } while (iter->ino == bagrec.rbg_ino); + + iter->ino = bagrec.rbg_ino; + return 1; +} + +/* Dump the rcbag. */ +void +rcbag_dump( + struct rcbag *bag) +{ + struct rcbag_rec bagrec; + struct xfs_mount *mp = bag->mp; + struct xfs_buf *head_bp; + struct xfs_btree_cur *cur; + unsigned long long nr = 0; + int has; + int error; + + error = -xfbtree_head_read_buf(bag->xfbtree, NULL, &head_bp); + if (error) + do_error(_("reading refcount bag header\n")); + + cur = rcbagbt_mem_cursor(mp, NULL, head_bp, bag->xfbtree); + error = -libxfs_btree_goto_left_edge(cur); + if (error) + do_error(_("seeking refcount bag btree cursor\n")); + + while (true) { + error = -libxfs_btree_increment(cur, 0, &has); + if (error) + do_error(_("incrementing refcount bag btree cursor\n")); + if (!has) + break; + + error = rcbagbt_get_rec(cur, &bagrec, &has); + if (error) + do_error(_("reading refcount bag btree record\n")); + if (!has) + do_error(_("refcount bag btree record disappeared?\n")); + + printf("[%llu]: bno 0x%x fsbcount 0x%x ino 0x%llx refcount 0x%llx\n", + nr++, + (unsigned int)bagrec.rbg_startblock, + (unsigned int)bagrec.rbg_blockcount, + (unsigned long long)bagrec.rbg_ino, + (unsigned long long)bagrec.rbg_refcount); + } + + libxfs_btree_del_cursor(cur, error); + libxfs_trans_brelse(NULL, head_bp); +} diff --git a/repair/rcbag.h b/repair/rcbag.h new file mode 100644 index 00000000000..04f9b5b403e --- /dev/null +++ b/repair/rcbag.h @@ -0,0 +1,33 @@ +// SPDX-License-Identifier: GPL-2.0-or-later +/* + * Copyright (C) 2022 Oracle. All Rights Reserved. + * Author: Darrick J. Wong + */ +#ifndef __RCBAG_H__ +#define __RCBAG_H__ + +struct xfs_mount; +struct rcbag; + +int rcbag_init(struct xfs_mount *mp, uint64_t max_rmaps, struct rcbag **bagp); +void rcbag_free(struct rcbag **bagp); +void rcbag_add(struct rcbag *bag, const struct xfs_rmap_irec *rmap); +uint64_t rcbag_count(const struct rcbag *bag); + +void rcbag_next_edge(struct rcbag *bag, const struct xfs_rmap_irec *next_rmap, + bool next_valid, uint32_t *next_bnop); +void rcbag_remove_ending_at(struct rcbag *bag, uint32_t next_bno); + +struct rcbag_iter { + struct xfs_buf *head_bp; + struct xfs_btree_cur *cur; + uint64_t ino; +}; + +void rcbag_ino_iter_start(struct rcbag *bag, struct rcbag_iter *iter); +void rcbag_ino_iter_stop(struct rcbag *bag, struct rcbag_iter *iter); +int rcbag_ino_iter(struct rcbag *bag, struct rcbag_iter *iter); + +void rcbag_dump(struct rcbag *bag); + +#endif /* __RCBAG_H__ */ diff --git a/repair/rcbag_btree.c b/repair/rcbag_btree.c index c86189806c8..13676463f7c 100644 --- a/repair/rcbag_btree.c +++ b/repair/rcbag_btree.c @@ -333,3 +333,62 @@ rcbagbt_destroy_cur_cache(void) kmem_cache_destroy(rcbagbt_cur_cache); rcbagbt_cur_cache = NULL; } + +/* Look up the refcount bag record corresponding to this reverse mapping. */ +int +rcbagbt_lookup_eq( + struct xfs_btree_cur *cur, + const struct xfs_rmap_irec *rmap, + int *success) +{ + struct rcbag_rec *rec = (struct rcbag_rec *)&cur->bc_rec; + + rec->rbg_startblock = rmap->rm_startblock; + rec->rbg_blockcount = rmap->rm_blockcount; + rec->rbg_ino = rmap->rm_owner; + + return -libxfs_btree_lookup(cur, XFS_LOOKUP_EQ, success); +} + +/* Get the data from the pointed-to record. */ +int +rcbagbt_get_rec( + struct xfs_btree_cur *cur, + struct rcbag_rec *rec, + int *has) +{ + union xfs_btree_rec *btrec; + int error; + + error = -libxfs_btree_get_rec(cur, &btrec, has); + if (error || !(*has)) + return error; + + memcpy(rec, btrec, sizeof(struct rcbag_rec)); + return 0; +} + +/* Update the record referred to by cur to the value given. */ +int +rcbagbt_update( + struct xfs_btree_cur *cur, + const struct rcbag_rec *rec) +{ + union xfs_btree_rec btrec; + + memcpy(&btrec, rec, sizeof(struct rcbag_rec)); + return -libxfs_btree_update(cur, &btrec); +} + +/* Update the record referred to by cur to the value given. */ +int +rcbagbt_insert( + struct xfs_btree_cur *cur, + const struct rcbag_rec *rec, + int *success) +{ + struct rcbag_rec *btrec = (struct rcbag_rec *)&cur->bc_rec; + + memcpy(btrec, rec, sizeof(struct rcbag_rec)); + return -libxfs_btree_insert(cur, success); +} diff --git a/repair/rcbag_btree.h b/repair/rcbag_btree.h index 21329153baf..fcbc4171369 100644 --- a/repair/rcbag_btree.h +++ b/repair/rcbag_btree.h @@ -68,4 +68,11 @@ struct xfs_btree_cur *rcbagbt_mem_cursor(struct xfs_mount *mp, int rcbagbt_mem_create(struct xfs_mount *mp, struct xfs_buftarg *target, struct xfbtree **xfbtreep); +int rcbagbt_lookup_eq(struct xfs_btree_cur *cur, + const struct xfs_rmap_irec *rmap, int *success); +int rcbagbt_get_rec(struct xfs_btree_cur *cur, struct rcbag_rec *rec, int *has); +int rcbagbt_update(struct xfs_btree_cur *cur, const struct rcbag_rec *rec); +int rcbagbt_insert(struct xfs_btree_cur *cur, const struct rcbag_rec *rec, + int *success); + #endif /* __RCBAG_BTREE_H__ */ From patchwork Fri Dec 30 22:17:52 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: 13085091 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 4FC2AC4332F for ; Sat, 31 Dec 2022 00:17:28 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S235883AbiLaAR1 (ORCPT ); Fri, 30 Dec 2022 19:17:27 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56344 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S235885AbiLaAR0 (ORCPT ); Fri, 30 Dec 2022 19:17:26 -0500 Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 81672E0C6 for ; Fri, 30 Dec 2022 16:17:25 -0800 (PST) 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 1E1A561D06 for ; Sat, 31 Dec 2022 00:17:25 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 7D5E0C433EF; Sat, 31 Dec 2022 00:17:24 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1672445844; bh=MjXg0MWGmO22DNSTvJq1elvyTWprFM5Qkyuet8YHsAI=; h=Subject:From:To:Cc:Date:In-Reply-To:References:From; b=CtFAfaDIJEFYc8OhkoSt+utnZYH4pfw/cd2Usu3J8ZRAIMaKBLP4QwWZdWNgYjcxU MACoCG2WHQHuh3Sd7ktReE1s93Xv4Bwm9hWd6+0p3rspbrJuleh18KqR7AWJtPwx77 cgO/KpQYSejmX0aHq6gF1acAJdT0jx7YBB6BhEu0IPNBlo8DTeVLT3JRwG9JX94K8s 9rYmAJrxEnBggSIyI+WZW/Fgdwix8iRKo6Bwb9yozFmH9TDxDk7z2RZrucG3nBeZSa mPo9y7HIf/ogy2Y+EF6TNY8AqYKhxQJwbx3AVexd+Y6h1RaPXHvojxrED4foPy82sZ 8kUDu85FWGgVQ== Subject: [PATCH 4/5] xfs_repair: port to the new refcount bag structure From: "Darrick J. Wong" To: cem@kernel.org, djwong@kernel.org Cc: linux-xfs@vger.kernel.org Date: Fri, 30 Dec 2022 14:17:52 -0800 Message-ID: <167243867296.712955.11117252350666704044.stgit@magnolia> In-Reply-To: <167243867247.712955.4006304832992035940.stgit@magnolia> References: <167243867247.712955.4006304832992035940.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 Port the refcount record generating code to use the new refcount bag data structure. Signed-off-by: Darrick J. Wong --- repair/rmap.c | 152 +++++++++++++++------------------------------------ repair/xfs_repair.c | 6 ++ 2 files changed, 52 insertions(+), 106 deletions(-) diff --git a/repair/rmap.c b/repair/rmap.c index e598dd9c9b8..ef1a599162b 100644 --- a/repair/rmap.c +++ b/repair/rmap.c @@ -15,6 +15,7 @@ #include "libfrog/bitmap.h" #include "libxfs/xfile.h" #include "libxfs/xfbtree.h" +#include "rcbag.h" #undef RMAP_DEBUG @@ -762,35 +763,32 @@ rmap_dump( * reflink inode flag, if the stack depth is greater than 1. */ static void -mark_inode_rl( +mark_reflink_inodes( struct xfs_mount *mp, - struct xfs_bag *rmaps) + struct rcbag *rcstack) { - struct rmap_for_refcount *rfr; + struct rcbag_iter rciter; struct ino_tree_node *irec; - int off; - uint64_t idx; - if (bag_count(rmaps) < 2) - return; - - /* Reflink flag accounting */ - foreach_bag_ptr(rmaps, idx, rfr) { + rcbag_ino_iter_start(rcstack, &rciter); + while (rcbag_ino_iter(rcstack, &rciter) == 1) { xfs_agnumber_t agno; xfs_agino_t agino; + int off; - ASSERT(!XFS_RMAP_NON_INODE_OWNER(rfr->rm_owner)); + ASSERT(!XFS_RMAP_NON_INODE_OWNER(rciter.ino)); - agno = XFS_INO_TO_AGNO(mp, rfr->rm_owner); - agino = XFS_INO_TO_AGINO(mp, rfr->rm_owner); + agno = XFS_INO_TO_AGNO(mp, rciter.ino); + agino = XFS_INO_TO_AGINO(mp, rciter.ino); pthread_mutex_lock(&ag_locks[agno].lock); irec = find_inode_rec(mp, agno, agino); - off = get_inode_offset(mp, rfr->rm_owner, irec); + off = get_inode_offset(mp, rciter.ino, irec); /* lock here because we might go outside this ag */ set_inode_is_rl(irec, off); pthread_mutex_unlock(&ag_locks[agno].lock); } + rcbag_ino_iter_stop(rcstack, &rciter); } /* @@ -826,8 +824,6 @@ refcount_emit( _("Insufficient memory while recreating refcount tree.")); } -#define RMAP_NEXT(r) ((r)->rm_startblock + (r)->rm_blockcount) - /* Decide if an rmap could describe a shared extent. */ static inline bool rmap_shareable( @@ -887,40 +883,6 @@ refcount_walk_rmaps( return 0; } -/* - * Find the next block where the refcount changes, given the next rmap we - * looked at and the ones we're already tracking. - */ -static inline int -next_refcount_edge( - struct xfs_bag *stack_top, - struct xfs_rmap_irec *next_rmap, - bool next_valid, - xfs_agblock_t *nbnop) -{ - struct rmap_for_refcount *rfr; - uint64_t idx; - xfs_agblock_t nbno = NULLAGBLOCK; - - if (next_valid) - nbno = next_rmap->rm_startblock; - - foreach_bag_ptr(stack_top, idx, rfr) - nbno = min(nbno, RMAP_NEXT(rfr)); - - /* - * We should have found /something/ because either next_rrm is the next - * interesting rmap to look at after emitting this refcount extent, or - * there are other rmaps in rmap_bag contributing to the current - * sharing count. But if something is seriously wrong, bail out. - */ - if (nbno == NULLAGBLOCK) - return EFSCORRUPTED; - - *nbnop = nbno; - return 0; -} - /* * Walk forward through the rmap btree to collect all rmaps starting at * @bno in @rmap_bag. These represent the file(s) that share ownership of @@ -930,28 +892,19 @@ next_refcount_edge( static int refcount_push_rmaps_at( struct rmap_mem_cur *rmcur, - xfs_agnumber_t agno, - struct xfs_bag *stack_top, + struct rcbag *stack, xfs_agblock_t bno, - struct xfs_rmap_irec *irec, + struct xfs_rmap_irec *rmap, bool *have, const char *tag) { int have_gt; int error; - while (*have && irec->rm_startblock == bno) { - struct rmap_for_refcount rfr = { - .rm_startblock = irec->rm_startblock, - .rm_blockcount = irec->rm_blockcount, - .rm_owner = irec->rm_owner, - }; + while (*have && rmap->rm_startblock == bno) { + rcbag_add(stack, rmap); - rmap_dump(tag, agno, &rfr); - error = bag_add(stack_top, &rfr); - if (error) - return error; - error = refcount_walk_rmaps(rmcur->mcur, irec, have); + error = refcount_walk_rmaps(rmcur->mcur, rmap, have); if (error) return error; } @@ -971,15 +924,14 @@ refcount_push_rmaps_at( */ int compute_refcounts( - struct xfs_mount *mp, + struct xfs_mount *mp, xfs_agnumber_t agno) { + struct rcbag *rcstack; struct rmap_mem_cur rmcur; - struct xfs_rmap_irec irec; - struct xfs_bag *stack_top = NULL; - struct rmap_for_refcount *rfr; - uint64_t idx; - uint64_t old_stack_nr; + struct xfs_rmap_irec rmap; + uint64_t nr_rmaps; + uint64_t old_stack_height; xfs_agblock_t sbno; /* first bno of this rmap set */ xfs_agblock_t cbno; /* first bno of this refcount set */ xfs_agblock_t nbno; /* next bno where rmap set changes */ @@ -991,11 +943,13 @@ compute_refcounts( if (ag_rmaps[agno].ar_xfbtree == NULL) return 0; + nr_rmaps = rmap_record_count(mp, agno); + error = rmap_init_mem_cursor(mp, NULL, agno, &rmcur); if (error) return error; - error = init_bag(&stack_top, sizeof(struct rmap_for_refcount)); + error = rcbag_init(mp, nr_rmaps, &rcstack); if (error) goto out_cur; @@ -1008,86 +962,72 @@ compute_refcounts( /* Process reverse mappings into refcount data. */ while (libxfs_btree_has_more_records(rmcur.mcur)) { /* Push all rmaps with pblk == sbno onto the stack */ - error = refcount_walk_rmaps(rmcur.mcur, &irec, &have); + error = refcount_walk_rmaps(rmcur.mcur, &rmap, &have); if (error) goto out_bag; if (!have) break; - sbno = cbno = irec.rm_startblock; - error = refcount_push_rmaps_at(&rmcur, agno, stack_top, sbno, - &irec, &have, "push0"); + sbno = cbno = rmap.rm_startblock; + error = refcount_push_rmaps_at(&rmcur, rcstack, sbno, &rmap, + &have, "push0"); if (error) goto out_bag; - mark_inode_rl(mp, stack_top); + mark_reflink_inodes(mp, rcstack); /* Set nbno to the bno of the next refcount change */ - error = next_refcount_edge(stack_top, &irec, have, &nbno); - if (error) - goto out_bag; + rcbag_next_edge(rcstack, &rmap, have, &nbno); /* Emit reverse mappings, if needed */ ASSERT(nbno > sbno); - old_stack_nr = bag_count(stack_top); + old_stack_height = rcbag_count(rcstack); /* While stack isn't empty... */ - while (bag_count(stack_top)) { + while (rcbag_count(rcstack) > 0) { /* Pop all rmaps that end at nbno */ - foreach_bag_ptr_reverse(stack_top, idx, rfr) { - if (RMAP_NEXT(rfr) != nbno) - continue; - rmap_dump("pop", agno, rfr); - error = bag_remove(stack_top, idx); - if (error) - goto out_bag; - } + rcbag_remove_ending_at(rcstack, nbno); /* Push array items that start at nbno */ - error = refcount_walk_rmaps(rmcur.mcur, &irec, &have); + error = refcount_walk_rmaps(rmcur.mcur, &rmap, &have); if (error) goto out_bag; if (have) { - error = refcount_push_rmaps_at(&rmcur, agno, - stack_top, nbno, &irec, &have, - "push1"); + error = refcount_push_rmaps_at(&rmcur, rcstack, + nbno, &rmap, &have, "push1"); if (error) goto out_bag; } - mark_inode_rl(mp, stack_top); + mark_reflink_inodes(mp, rcstack); /* Emit refcount if necessary */ ASSERT(nbno > cbno); - if (bag_count(stack_top) != old_stack_nr) { - if (old_stack_nr > 1) { + if (rcbag_count(rcstack) != old_stack_height) { + if (old_stack_height > 1) { refcount_emit(mp, agno, cbno, - nbno - cbno, - old_stack_nr); + nbno - cbno, + old_stack_height); } cbno = nbno; } /* Stack empty, go find the next rmap */ - if (bag_count(stack_top) == 0) + if (rcbag_count(rcstack) == 0) break; - old_stack_nr = bag_count(stack_top); + old_stack_height = rcbag_count(rcstack); sbno = nbno; /* Set nbno to the bno of the next refcount change */ - error = next_refcount_edge(stack_top, &irec, have, - &nbno); - if (error) - goto out_bag; + rcbag_next_edge(rcstack, &rmap, have, &nbno); /* Emit reverse mappings, if needed */ ASSERT(nbno > sbno); } } out_bag: - free_bag(&stack_top); + rcbag_free(&rcstack); out_cur: rmap_free_mem_cursor(NULL, &rmcur, error); return error; } -#undef RMAP_NEXT static int count_btree_records( diff --git a/repair/xfs_repair.c b/repair/xfs_repair.c index 251a46d11fe..8e62533ac53 100644 --- a/repair/xfs_repair.c +++ b/repair/xfs_repair.c @@ -26,6 +26,7 @@ #include "libfrog/platform.h" #include "bulkload.h" #include "quotacheck.h" +#include "rcbag_btree.h" /* * option tables for getsubopt calls @@ -1247,6 +1248,10 @@ main(int argc, char **argv) phase3(mp, phase2_threads); phase_end(mp, 3); + error = rcbagbt_init_cur_cache(); + if (error) + do_error(_("could not allocate btree cursor memory\n")); + phase4(mp); phase_end(mp, 4); @@ -1259,6 +1264,7 @@ main(int argc, char **argv) phase5(mp); } phase_end(mp, 5); + rcbagbt_destroy_cur_cache(); /* * Done with the block usage maps, toss them... From patchwork Fri Dec 30 22:17:53 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: 13085092 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 CBCE3C4332F for ; Sat, 31 Dec 2022 00:17:43 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S235892AbiLaARm (ORCPT ); Fri, 30 Dec 2022 19:17:42 -0500 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:56450 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S235893AbiLaARl (ORCPT ); Fri, 30 Dec 2022 19:17:41 -0500 Received: from dfw.source.kernel.org (dfw.source.kernel.org [139.178.84.217]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 1E9FC1261F for ; Fri, 30 Dec 2022 16:17:41 -0800 (PST) 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 ADC4D61D08 for ; Sat, 31 Dec 2022 00:17:40 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id 11A72C433D2; Sat, 31 Dec 2022 00:17:40 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1672445860; bh=57BjpEo7wTZTHd2JrdpSJSaAekL/R1qn6C51RUWP8z4=; h=Subject:From:To:Cc:Date:In-Reply-To:References:From; b=KF6rwzi7l+P2yoRPefz74OnsgAc/2RJmRsXdJ/x9Sime1eEMMMuBg1zP3lbUydFZy qSdcbkmV5UZRr9tgJfNhRtChKBgzJnGjJMcd7/n0czMR5aVC+or0HQBoGf5vF6cl1T 4CPrOUhtNzNixgEayDShUhAnI8BHPD9PbHFMoyE2pI35xi9q2M1RA0I/m8ICcZdjJ0 mHShIRHF+v+lYSijVCfOvWv62XLlkgPYP6uPHj6bC4PgQwqBJG6Uh98Eb07D2/StYH 081BiORHKZSNQiJZoWNDcoWTMTUC1l7lpMQ9KdTGjVS5gbCo8V5DJ3V4roXMfH4WEU exjh3tfiZgDlw== Subject: [PATCH 5/5] xfs_repair: remove the old bag implementation From: "Darrick J. Wong" To: cem@kernel.org, djwong@kernel.org Cc: linux-xfs@vger.kernel.org Date: Fri, 30 Dec 2022 14:17:53 -0800 Message-ID: <167243867310.712955.11202535687694387202.stgit@magnolia> In-Reply-To: <167243867247.712955.4006304832992035940.stgit@magnolia> References: <167243867247.712955.4006304832992035940.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 Remove the old bag implementation. Signed-off-by: Darrick J. Wong --- repair/rmap.c | 7 --- repair/slab.c | 130 --------------------------------------------------------- repair/slab.h | 19 -------- 3 files changed, 156 deletions(-) diff --git a/repair/rmap.c b/repair/rmap.c index ef1a599162b..f8294cc3e13 100644 --- a/repair/rmap.c +++ b/repair/rmap.c @@ -34,13 +34,6 @@ struct xfs_ag_rmap { struct xfs_slab *ar_refcount_items; /* refcount items, p4-5 */ }; -/* Only the parts of struct xfs_rmap_irec that we need to compute refcounts. */ -struct rmap_for_refcount { - xfs_agblock_t rm_startblock; - xfs_extlen_t rm_blockcount; - uint64_t rm_owner; -}; - static struct xfs_ag_rmap *ag_rmaps; bool rmapbt_suspect; static bool refcbt_suspect; diff --git a/repair/slab.c b/repair/slab.c index 44ca0468eda..a0114ac2373 100644 --- a/repair/slab.c +++ b/repair/slab.c @@ -77,28 +77,6 @@ struct xfs_slab_cursor { struct xfs_slab_hdr_cursor hcur[0]; /* per-slab cursors */ }; -/* - * Bags -- each bag is an array of record items; when a bag fills up, we resize - * it and hope we don't run out of memory. - */ -#define MIN_BAG_SIZE 4096 -struct xfs_bag { - uint64_t bg_nr; /* number of pointers */ - uint64_t bg_inuse; /* number of slots in use */ - char *bg_items; /* pointer to block of items */ - size_t bg_item_sz; /* size of each item */ -}; - -static inline void *bag_ptr(struct xfs_bag *bag, uint64_t idx) -{ - return &bag->bg_items[bag->bg_item_sz * idx]; -} - -static inline void *bag_end(struct xfs_bag *bag) -{ - return bag_ptr(bag, bag->bg_nr); -} - /* * Create a slab to hold some objects of a particular size. */ @@ -386,111 +364,3 @@ slab_count( { return slab->s_nr_items; } - -/* - * Create a bag to point to some objects. - */ -int -init_bag( - struct xfs_bag **bag, - size_t item_sz) -{ - struct xfs_bag *ptr; - - ptr = calloc(1, sizeof(struct xfs_bag)); - if (!ptr) - return -ENOMEM; - ptr->bg_item_sz = item_sz; - ptr->bg_items = calloc(MIN_BAG_SIZE, item_sz); - if (!ptr->bg_items) { - free(ptr); - return -ENOMEM; - } - ptr->bg_nr = MIN_BAG_SIZE; - *bag = ptr; - return 0; -} - -/* - * Free a bag of pointers. - */ -void -free_bag( - struct xfs_bag **bag) -{ - struct xfs_bag *ptr; - - ptr = *bag; - if (!ptr) - return; - free(ptr->bg_items); - free(ptr); - *bag = NULL; -} - -/* - * Add an object to the pointer bag. - */ -int -bag_add( - struct xfs_bag *bag, - void *ptr) -{ - void *p, *x; - - p = bag_ptr(bag, bag->bg_inuse); - if (p == bag_end(bag)) { - /* No free space, alloc more pointers */ - uint64_t nr; - - nr = bag->bg_nr * 2; - x = realloc(bag->bg_items, nr * bag->bg_item_sz); - if (!x) - return -ENOMEM; - bag->bg_items = x; - memset(bag_end(bag), 0, bag->bg_nr * bag->bg_item_sz); - bag->bg_nr = nr; - p = bag_ptr(bag, bag->bg_inuse); - } - memcpy(p, ptr, bag->bg_item_sz); - bag->bg_inuse++; - return 0; -} - -/* - * Remove a pointer from a bag. - */ -int -bag_remove( - struct xfs_bag *bag, - uint64_t nr) -{ - ASSERT(nr < bag->bg_inuse); - memmove(bag_ptr(bag, nr), bag_ptr(bag, nr + 1), - (bag->bg_inuse - nr - 1) * bag->bg_item_sz); - bag->bg_inuse--; - return 0; -} - -/* - * Return the number of items in a bag. - */ -uint64_t -bag_count( - struct xfs_bag *bag) -{ - return bag->bg_inuse; -} - -/* - * Return the nth item in a bag. - */ -void * -bag_item( - struct xfs_bag *bag, - uint64_t nr) -{ - if (nr >= bag->bg_inuse) - return NULL; - return bag_ptr(bag, nr); -} diff --git a/repair/slab.h b/repair/slab.h index 019b169024d..77fb32163d5 100644 --- a/repair/slab.h +++ b/repair/slab.h @@ -26,23 +26,4 @@ void *peek_slab_cursor(struct xfs_slab_cursor *cur); void advance_slab_cursor(struct xfs_slab_cursor *cur); void *pop_slab_cursor(struct xfs_slab_cursor *cur); -struct xfs_bag; - -int init_bag(struct xfs_bag **bagp, size_t itemsz); -void free_bag(struct xfs_bag **bagp); -int bag_add(struct xfs_bag *bag, void *item); -int bag_remove(struct xfs_bag *bag, uint64_t idx); -uint64_t bag_count(struct xfs_bag *bag); -void *bag_item(struct xfs_bag *bag, uint64_t idx); - -#define foreach_bag_ptr(bag, idx, ptr) \ - for ((idx) = 0, (ptr) = bag_item((bag), (idx)); \ - (idx) < bag_count(bag); \ - (idx)++, (ptr) = bag_item((bag), (idx))) - -#define foreach_bag_ptr_reverse(bag, idx, ptr) \ - for ((idx) = bag_count(bag) - 1, (ptr) = bag_item((bag), (idx)); \ - (ptr) != NULL; \ - (idx)--, (ptr) = bag_item((bag), (idx))) - #endif /* SLAB_H_ */