[31/48] xfs: compute absolute maximum nlevels for each btree type

Message ID	164263836283.865554.12835070575139510285.stgit@magnolia (mailing list archive)
State	Accepted
Headers	show Return-Path: <linux-xfs-owner@kernel.org> Subject: [PATCH 31/48] xfs: compute absolute maximum nlevels for each btree type From: "Darrick J. Wong" <djwong@kernel.org> To: sandeen@sandeen.net, djwong@kernel.org Cc: Dave Chinner <dchinner@redhat.com>, linux-xfs@vger.kernel.org Date: Wed, 19 Jan 2022 16:26:02 -0800 Message-ID: <164263836283.865554.12835070575139510285.stgit@magnolia> In-Reply-To: <164263819185.865554.6000499997543946756.stgit@magnolia> References: <164263819185.865554.6000499997543946756.stgit@magnolia> User-Agent: StGit/0.19 MIME-Version: 1.0 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: 7bit Precedence: bulk
Series	xfsprogs: sync libxfs with 5.16 \| expand [PATCHSET,00/48] xfsprogs: sync libxfs with 5.16 [01/48] xfs: formalize the process of holding onto resources across a defer roll [02/48] xfs: port the defer ops capture and continue to resource capture [03/48] xfs: fix maxlevels comparisons in the btree staging code [04/48] xfs: remove xfs_btree_cur_t typedef [05/48] xfs: check that bc_nlevels never overflows [06/48] xfs: remove the xfs_dinode_t typedef [07/48] xfs: remove the xfs_dsb_t typedef [08/48] xfs: remove the xfs_dqblk_t typedef [09/48] xfs: fold perag loop iteration logic into helper function [10/48] xfs: rename the next_agno perag iteration variable [11/48] xfs: terminate perag iteration reliably on agcount [12/48] xfs: fix perag reference leak on iteration race with growfs [13/48] xfs: remove xfs_btree_cur.bc_blocklog [14/48] xfs: reduce the size of nr_ops for refcount btree cursors [15/48] xfs: prepare xfs_btree_cur for dynamic cursor heights [16/48] xfs: rearrange xfs_btree_cur fields for better packing [17/48] xfs: refactor btree cursor allocation function [18/48] xfs: encode the max btree height in the cursor [19/48] xfs: dynamically allocate cursors based on maxlevels [20/48] xfs: rename m_ag_maxlevels to m_allocbt_maxlevels [21/48] xfs: compute maximum AG btree height for critical reservation calculation [22/48] xfs: clean up xfs_btree_{calc_size,compute_maxlevels} [23/48] xfs: compute the maximum height of the rmap btree when reflink enabled [24/48] xfs_db: fix metadump level comparisons [25/48] xfs_db: warn about suspicious finobt trees when metadumping [26/48] xfs_db: stop using XFS_BTREE_MAXLEVELS [27/48] xfs_repair: fix AG header btree level comparisons [28/48] xfs_repair: warn about suspicious btree levels in AG headers [29/48] xfs_repair: stop using XFS_BTREE_MAXLEVELS [30/48] xfs: kill XFS_BTREE_MAXLEVELS [31/48] xfs: compute absolute maximum nlevels for each btree type [32/48] xfs: use separate btree cursor cache for each btree type [33/48] xfs_db: support computing btheight for all cursor types [34/48] xfs_db: report absolute maxlevels for each btree type [35/48] libxfs: remove kmem_zone_destroy [36/48] libxfs: remove kmem_zone_init [37/48] xfs: remove kmem_zone typedef [38/48] xfs: rename _zone variables to _cache [39/48] libxfs: rename all the other _zone variables to _cache [40/48] libxfs: change zone to cache for all kmem functions [41/48] xfs: compact deferred intent item structures [42/48] xfs: create slab caches for frequently-used deferred items [43/48] xfs: rename xfs_bmap_add_free to xfs_free_extent_later [44/48] xfs: reduce the size of struct xfs_extent_free_item [45/48] xfs: remove unused parameter from refcount code [46/48] xfs: use swap() to make dabtree code cleaner [47/48] xfs: Fix the free logic of state in xfs_attr_node_hasname [48/48] libxfs: remove kernel stubs from xfs_shared.h

diff --git a/libxfs/xfs_alloc.c b/libxfs/xfs_alloc.c index e20d8fb7..7d304160 100644 --- a/libxfs/xfs_alloc.c +++ b/libxfs/xfs_alloc.c @@ -2194,6 +2194,7 @@ xfs_alloc_compute_maxlevels( { mp->m_alloc_maxlevels = xfs_btree_compute_maxlevels(mp->m_alloc_mnr, (mp->m_sb.sb_agblocks + 1) / 2); + ASSERT(mp->m_alloc_maxlevels <= xfs_allocbt_maxlevels_ondisk()); } /* diff --git a/libxfs/xfs_alloc_btree.c b/libxfs/xfs_alloc_btree.c index d752500b..6de3af37 100644 --- a/libxfs/xfs_alloc_btree.c +++ b/libxfs/xfs_alloc_btree.c @@ -564,6 +564,17 @@ xfs_allocbt_commit_staged_btree( } } +/* Calculate number of records in an alloc btree block. */ +static inline unsigned int +xfs_allocbt_block_maxrecs( + unsigned int blocklen, + bool leaf) +{ + if (leaf) + return blocklen / sizeof(xfs_alloc_rec_t); + return blocklen / (sizeof(xfs_alloc_key_t) + sizeof(xfs_alloc_ptr_t)); +} + /* * Calculate number of records in an alloc btree block. */ @@ -574,10 +585,26 @@ xfs_allocbt_maxrecs( int leaf) { blocklen -= XFS_ALLOC_BLOCK_LEN(mp); + return xfs_allocbt_block_maxrecs(blocklen, leaf); +} - if (leaf) - return blocklen / sizeof(xfs_alloc_rec_t); - return blocklen / (sizeof(xfs_alloc_key_t) + sizeof(xfs_alloc_ptr_t)); +/* Free space btrees are at their largest when every other block is free. */ +#define XFS_MAX_FREESP_RECORDS ((XFS_MAX_AG_BLOCKS + 1) / 2) + +/* Compute the max possible height for free space btrees. */ +unsigned int +xfs_allocbt_maxlevels_ondisk(void) +{ + unsigned int minrecs[2]; + unsigned int blocklen; + + blocklen = min(XFS_MIN_BLOCKSIZE - XFS_BTREE_SBLOCK_LEN, + XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN); + + minrecs[0] = xfs_allocbt_block_maxrecs(blocklen, true) / 2; + minrecs[1] = xfs_allocbt_block_maxrecs(blocklen, false) / 2; + + return xfs_btree_compute_maxlevels(minrecs, XFS_MAX_FREESP_RECORDS); } /* Calculate the freespace btree size for some records. */ diff --git a/libxfs/xfs_alloc_btree.h b/libxfs/xfs_alloc_btree.h index 2f6b816a..c715bee5 100644 --- a/libxfs/xfs_alloc_btree.h +++ b/libxfs/xfs_alloc_btree.h @@ -60,4 +60,6 @@ extern xfs_extlen_t xfs_allocbt_calc_size(struct xfs_mount *mp, void xfs_allocbt_commit_staged_btree(struct xfs_btree_cur *cur, struct xfs_trans *tp, struct xfs_buf *agbp); +unsigned int xfs_allocbt_maxlevels_ondisk(void); + #endif /* __XFS_ALLOC_BTREE_H__ */ diff --git a/libxfs/xfs_bmap.c b/libxfs/xfs_bmap.c index 3b8b1b61..bc8a2033 100644 --- a/libxfs/xfs_bmap.c +++ b/libxfs/xfs_bmap.c @@ -86,6 +86,7 @@ xfs_bmap_compute_maxlevels( maxblocks = (maxblocks + minnoderecs - 1) / minnoderecs; } mp->m_bm_maxlevels[whichfork] = level; + ASSERT(mp->m_bm_maxlevels[whichfork] <= xfs_bmbt_maxlevels_ondisk()); } unsigned int diff --git a/libxfs/xfs_bmap_btree.c b/libxfs/xfs_bmap_btree.c index 9e2263ed..85faea1d 100644 --- a/libxfs/xfs_bmap_btree.c +++ b/libxfs/xfs_bmap_btree.c @@ -569,6 +569,17 @@ xfs_bmbt_init_cursor( return cur; } +/* Calculate number of records in a block mapping btree block. */ +static inline unsigned int +xfs_bmbt_block_maxrecs( + unsigned int blocklen, + bool leaf) +{ + if (leaf) + return blocklen / sizeof(xfs_bmbt_rec_t); + return blocklen / (sizeof(xfs_bmbt_key_t) + sizeof(xfs_bmbt_ptr_t)); +} + /* * Calculate number of records in a bmap btree block. */ @@ -579,10 +590,24 @@ xfs_bmbt_maxrecs( int leaf) { blocklen -= XFS_BMBT_BLOCK_LEN(mp); + return xfs_bmbt_block_maxrecs(blocklen, leaf); +} - if (leaf) - return blocklen / sizeof(xfs_bmbt_rec_t); - return blocklen / (sizeof(xfs_bmbt_key_t) + sizeof(xfs_bmbt_ptr_t)); +/* Compute the max possible height for block mapping btrees. */ +unsigned int +xfs_bmbt_maxlevels_ondisk(void) +{ + unsigned int minrecs[2]; + unsigned int blocklen; + + blocklen = min(XFS_MIN_BLOCKSIZE - XFS_BTREE_SBLOCK_LEN, + XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN); + + minrecs[0] = xfs_bmbt_block_maxrecs(blocklen, true) / 2; + minrecs[1] = xfs_bmbt_block_maxrecs(blocklen, false) / 2; + + /* One extra level for the inode root. */ + return xfs_btree_compute_maxlevels(minrecs, MAXEXTNUM) + 1; } /* diff --git a/libxfs/xfs_bmap_btree.h b/libxfs/xfs_bmap_btree.h index 729e3bc5..2a1c9e60 100644 --- a/libxfs/xfs_bmap_btree.h +++ b/libxfs/xfs_bmap_btree.h @@ -110,4 +110,6 @@ extern struct xfs_btree_cur *xfs_bmbt_init_cursor(struct xfs_mount *, extern unsigned long long xfs_bmbt_calc_size(struct xfs_mount *mp, unsigned long long len); +unsigned int xfs_bmbt_maxlevels_ondisk(void); + #endif /* __XFS_BMAP_BTREE_H__ */ diff --git a/libxfs/xfs_fs.h b/libxfs/xfs_fs.h index bde2b4c6..c43877c8 100644 --- a/libxfs/xfs_fs.h +++ b/libxfs/xfs_fs.h @@ -268,6 +268,8 @@ typedef struct xfs_fsop_resblks { */ #define XFS_MIN_AG_BYTES (1ULL << 24) /* 16 MB */ #define XFS_MAX_AG_BYTES (1ULL << 40) /* 1 TB */ +#define XFS_MAX_AG_BLOCKS (XFS_MAX_AG_BYTES / XFS_MIN_BLOCKSIZE) +#define XFS_MAX_CRC_AG_BLOCKS (XFS_MAX_AG_BYTES / XFS_MIN_CRC_BLOCKSIZE) /* keep the maximum size under 2^31 by a small amount */ #define XFS_MAX_LOG_BYTES \ diff --git a/libxfs/xfs_ialloc.c b/libxfs/xfs_ialloc.c index 3b96e828..b18ddc4e 100644 --- a/libxfs/xfs_ialloc.c +++ b/libxfs/xfs_ialloc.c @@ -2788,6 +2788,7 @@ xfs_ialloc_setup_geometry( inodes = (1LL << XFS_INO_AGINO_BITS(mp)) >> XFS_INODES_PER_CHUNK_LOG; igeo->inobt_maxlevels = xfs_btree_compute_maxlevels(igeo->inobt_mnr, inodes); + ASSERT(igeo->inobt_maxlevels <= xfs_iallocbt_maxlevels_ondisk()); /* * Set the maximum inode count for this filesystem, being careful not diff --git a/libxfs/xfs_ialloc_btree.c b/libxfs/xfs_ialloc_btree.c index be0918b7..30b1abe9 100644 --- a/libxfs/xfs_ialloc_btree.c +++ b/libxfs/xfs_ialloc_btree.c @@ -525,6 +525,17 @@ xfs_inobt_commit_staged_btree( } } +/* Calculate number of records in an inode btree block. */ +static inline unsigned int +xfs_inobt_block_maxrecs( + unsigned int blocklen, + bool leaf) +{ + if (leaf) + return blocklen / sizeof(xfs_inobt_rec_t); + return blocklen / (sizeof(xfs_inobt_key_t) + sizeof(xfs_inobt_ptr_t)); +} + /* * Calculate number of records in an inobt btree block. */ @@ -535,10 +546,54 @@ xfs_inobt_maxrecs( int leaf) { blocklen -= XFS_INOBT_BLOCK_LEN(mp); + return xfs_inobt_block_maxrecs(blocklen, leaf); +} - if (leaf) - return blocklen / sizeof(xfs_inobt_rec_t); - return blocklen / (sizeof(xfs_inobt_key_t) + sizeof(xfs_inobt_ptr_t)); +/* + * Maximum number of inode btree records per AG. Pretend that we can fill an + * entire AG completely full of inodes except for the AG headers. + */ +#define XFS_MAX_INODE_RECORDS \ + ((XFS_MAX_AG_BYTES - (4 * BBSIZE)) / XFS_DINODE_MIN_SIZE) / \ + XFS_INODES_PER_CHUNK + +/* Compute the max possible height for the inode btree. */ +static inline unsigned int +xfs_inobt_maxlevels_ondisk(void) +{ + unsigned int minrecs[2]; + unsigned int blocklen; + + blocklen = min(XFS_MIN_BLOCKSIZE - XFS_BTREE_SBLOCK_LEN, + XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN); + + minrecs[0] = xfs_inobt_block_maxrecs(blocklen, true) / 2; + minrecs[1] = xfs_inobt_block_maxrecs(blocklen, false) / 2; + + return xfs_btree_compute_maxlevels(minrecs, XFS_MAX_INODE_RECORDS); +} + +/* Compute the max possible height for the free inode btree. */ +static inline unsigned int +xfs_finobt_maxlevels_ondisk(void) +{ + unsigned int minrecs[2]; + unsigned int blocklen; + + blocklen = XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN; + + minrecs[0] = xfs_inobt_block_maxrecs(blocklen, true) / 2; + minrecs[1] = xfs_inobt_block_maxrecs(blocklen, false) / 2; + + return xfs_btree_compute_maxlevels(minrecs, XFS_MAX_INODE_RECORDS); +} + +/* Compute the max possible height for either inode btree. */ +unsigned int +xfs_iallocbt_maxlevels_ondisk(void) +{ + return max(xfs_inobt_maxlevels_ondisk(), + xfs_finobt_maxlevels_ondisk()); } /* diff --git a/libxfs/xfs_ialloc_btree.h b/libxfs/xfs_ialloc_btree.h index 8a322d40..6d3e4a33 100644 --- a/libxfs/xfs_ialloc_btree.h +++ b/libxfs/xfs_ialloc_btree.h @@ -75,4 +75,6 @@ int xfs_inobt_cur(struct xfs_mount *mp, struct xfs_trans *tp, void xfs_inobt_commit_staged_btree(struct xfs_btree_cur *cur, struct xfs_trans *tp, struct xfs_buf *agbp); +unsigned int xfs_iallocbt_maxlevels_ondisk(void); + #endif /* __XFS_IALLOC_BTREE_H__ */ diff --git a/libxfs/xfs_refcount_btree.c b/libxfs/xfs_refcount_btree.c index 6a716924..1d7b2d7c 100644 --- a/libxfs/xfs_refcount_btree.c +++ b/libxfs/xfs_refcount_btree.c @@ -392,29 +392,58 @@ xfs_refcountbt_commit_staged_btree( xfs_btree_commit_afakeroot(cur, tp, agbp, &xfs_refcountbt_ops); } -/* - * Calculate the number of records in a refcount btree block. - */ -int -xfs_refcountbt_maxrecs( - int blocklen, +/* Calculate number of records in a refcount btree block. */ +static inline unsigned int +xfs_refcountbt_block_maxrecs( + unsigned int blocklen, bool leaf) { - blocklen -= XFS_REFCOUNT_BLOCK_LEN; - if (leaf) return blocklen / sizeof(struct xfs_refcount_rec); return blocklen / (sizeof(struct xfs_refcount_key) + sizeof(xfs_refcount_ptr_t)); } +/* + * Calculate the number of records in a refcount btree block. + */ +int +xfs_refcountbt_maxrecs( + int blocklen, + bool leaf) +{ + blocklen -= XFS_REFCOUNT_BLOCK_LEN; + return xfs_refcountbt_block_maxrecs(blocklen, leaf); +} + +/* Compute the max possible height of the maximally sized refcount btree. */ +unsigned int +xfs_refcountbt_maxlevels_ondisk(void) +{ + unsigned int minrecs[2]; + unsigned int blocklen; + + blocklen = XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN; + + minrecs[0] = xfs_refcountbt_block_maxrecs(blocklen, true) / 2; + minrecs[1] = xfs_refcountbt_block_maxrecs(blocklen, false) / 2; + + return xfs_btree_compute_maxlevels(minrecs, XFS_MAX_CRC_AG_BLOCKS); +} + /* Compute the maximum height of a refcount btree. */ void xfs_refcountbt_compute_maxlevels( struct xfs_mount *mp) { + if (!xfs_has_reflink(mp)) { + mp->m_refc_maxlevels = 0; + return; + } + mp->m_refc_maxlevels = xfs_btree_compute_maxlevels( mp->m_refc_mnr, mp->m_sb.sb_agblocks); + ASSERT(mp->m_refc_maxlevels <= xfs_refcountbt_maxlevels_ondisk()); } /* Calculate the refcount btree size for some records. */ diff --git a/libxfs/xfs_refcount_btree.h b/libxfs/xfs_refcount_btree.h index bd9ed9e1..d7f7c89c 100644 --- a/libxfs/xfs_refcount_btree.h +++ b/libxfs/xfs_refcount_btree.h @@ -65,4 +65,6 @@ extern int xfs_refcountbt_calc_reserves(struct xfs_mount *mp, void xfs_refcountbt_commit_staged_btree(struct xfs_btree_cur *cur, struct xfs_trans *tp, struct xfs_buf *agbp); +unsigned int xfs_refcountbt_maxlevels_ondisk(void); + #endif /* __XFS_REFCOUNT_BTREE_H__ */ diff --git a/libxfs/xfs_rmap_btree.c b/libxfs/xfs_rmap_btree.c index eeaa1e28..eb3ef409 100644 --- a/libxfs/xfs_rmap_btree.c +++ b/libxfs/xfs_rmap_btree.c @@ -517,6 +517,18 @@ xfs_rmapbt_commit_staged_btree( xfs_btree_commit_afakeroot(cur, tp, agbp, &xfs_rmapbt_ops); } +/* Calculate number of records in a reverse mapping btree block. */ +static inline unsigned int +xfs_rmapbt_block_maxrecs( + unsigned int blocklen, + bool leaf) +{ + if (leaf) + return blocklen / sizeof(struct xfs_rmap_rec); + return blocklen / + (2 * sizeof(struct xfs_rmap_key) + sizeof(xfs_rmap_ptr_t)); +} + /* * Calculate number of records in an rmap btree block. */ @@ -526,11 +538,33 @@ xfs_rmapbt_maxrecs( int leaf) { blocklen -= XFS_RMAP_BLOCK_LEN; + return xfs_rmapbt_block_maxrecs(blocklen, leaf); +} - if (leaf) - return blocklen / sizeof(struct xfs_rmap_rec); - return blocklen / - (2 * sizeof(struct xfs_rmap_key) + sizeof(xfs_rmap_ptr_t)); +/* Compute the max possible height for reverse mapping btrees. */ +unsigned int +xfs_rmapbt_maxlevels_ondisk(void) +{ + unsigned int minrecs[2]; + unsigned int blocklen; + + blocklen = XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN; + + minrecs[0] = xfs_rmapbt_block_maxrecs(blocklen, true) / 2; + minrecs[1] = xfs_rmapbt_block_maxrecs(blocklen, false) / 2; + + /* + * Compute the asymptotic maxlevels for an rmapbt on any reflink fs. + * + * On a reflink filesystem, each AG block can have up to 2^32 (per the + * refcount record format) owners, which means that theoretically we + * could face up to 2^64 rmap records. However, we're likely to run + * out of blocks in the AG long before that happens, which means that + * we must compute the max height based on what the btree will look + * like if it consumes almost all the blocks in the AG due to maximal + * sharing factor. + */ + return xfs_btree_space_to_height(minrecs, XFS_MAX_CRC_AG_BLOCKS); } /* Compute the maximum height of an rmap btree. */ @@ -567,6 +601,7 @@ xfs_rmapbt_compute_maxlevels( mp->m_rmap_maxlevels = xfs_btree_compute_maxlevels( mp->m_rmap_mnr, mp->m_sb.sb_agblocks); } + ASSERT(mp->m_rmap_maxlevels <= xfs_rmapbt_maxlevels_ondisk()); } /* Calculate the refcount btree size for some records. */ diff --git a/libxfs/xfs_rmap_btree.h b/libxfs/xfs_rmap_btree.h index f2eee657..e9778b62 100644 --- a/libxfs/xfs_rmap_btree.h +++ b/libxfs/xfs_rmap_btree.h @@ -59,4 +59,6 @@ extern xfs_extlen_t xfs_rmapbt_max_size(struct xfs_mount *mp, extern int xfs_rmapbt_calc_reserves(struct xfs_mount *mp, struct xfs_trans *tp, struct xfs_perag *pag, xfs_extlen_t *ask, xfs_extlen_t *used); +unsigned int xfs_rmapbt_maxlevels_ondisk(void); + #endif /* __XFS_RMAP_BTREE_H__ */

[31/48] xfs: compute absolute maximum nlevels for each btree type

Commit Message

Patch