From: Dave Chinner <david@fromorbit.com>
To: "Darrick J. Wong" <djwong@kernel.org>
Cc: linux-xfs@vger.kernel.org, chandan.babu@oracle.com, hch@lst.de
Subject: Re: [PATCH 14/15] xfs: compute absolute maximum nlevels for each btree type
Date: Thu, 14 Oct 2021 10:48:58 +1100 [thread overview]
Message-ID: <20211013234858.GL2361455@dread.disaster.area> (raw)
In-Reply-To: <20211013213633.GZ24307@magnolia>
On Wed, Oct 13, 2021 at 02:36:33PM -0700, Darrick J. Wong wrote:
> On Wed, Oct 13, 2021 at 06:57:43PM +1100, Dave Chinner wrote:
> > On Tue, Oct 12, 2021 at 04:33:50PM -0700, Darrick J. Wong wrote:
> > > --- a/fs/xfs/libxfs/xfs_alloc_btree.c
> > > +++ b/fs/xfs/libxfs/xfs_alloc_btree.c
> > > @@ -582,6 +582,19 @@ xfs_allocbt_maxrecs(
> > > return blocklen / (sizeof(xfs_alloc_key_t) + sizeof(xfs_alloc_ptr_t));
> > > }
> > >
> > > +/* Compute the max possible height of the maximally sized free space btree. */
> > > +unsigned int
> > > +xfs_allocbt_absolute_maxlevels(void)
> > > +{
> > > + unsigned int minrecs[2];
> > > +
> > > + xfs_btree_absolute_minrecs(minrecs, 0, sizeof(xfs_alloc_rec_t),
> > > + sizeof(xfs_alloc_key_t) + sizeof(xfs_alloc_ptr_t));
> > > +
> > > + return xfs_btree_compute_maxlevels(minrecs,
> > > + (XFS_MAX_AG_BLOCKS + 1) / 2);
> > > +}
> >
> > Hmmmm. This is kinds messy. I'd prefer we share code with the
> > xfs_allocbt_maxrecs() function that do this. Not sure "absolute" is
> > the right word, either. It's more a function of the on-disk format
> > maximum, not an "absolute" thing.
>
> <nod> I'm not passionate about the name one way or the other.
>
> > I mean, we know that the worst case is going to be for each btree
> > type - we don't need to pass in XFS_BTREE_CRC_BLOCKS or
> > XFS_BTREE_LONG_PTRS to generic code for it to branch multiple times
> > to be generic.
>
> Yeah, that function was a conditional mess. I like...
>
> > Instead:
> >
> > static inline int
> > xfs_allocbt_block_maxrecs(
> > int blocklen,
> > int 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.
> > */
> > int
> > xfs_allocbt_maxrecs(
> > struct xfs_mount *mp,
> > int blocklen,
> > int leaf)
> > {
> > blocklen -= XFS_ALLOC_BLOCK_LEN(mp);
> > return xfs_allobt_block_maxrecs(blocklen, leaf);
> > }
> >
> > xfs_allocbt_maxlevels_ondisk()
> > {
> > unsigned int minrecs[2];
> >
> > minrecs[0] = xfs_allocbt_block_maxrecs(
> > XFS_MIN_BLOCKSIZE - XFS_BTREE_SBLOCK_LEN, true) / 2;
> > minrecs[1] = xfs_allocbt_block_maxrecs(
> > XFS_MIN_BLOCKSIZE - XFS_BTREE_SBLOCK_LEN, false) / 2;
>
> ...this a lot better since one doesn't have to switch back and forth
> between source files to figure out how the computation works.
>
> However, I want to propose a possibly pedantic addition to the blocksize
> computation for btrees. We want to compute the maximum btree height
> that we're ever going to see, which means that we are modeling a btree
> with the minimum possible fanout factor. That means the smallest btree
> nodes possible, and half full.
>
> min V5 blocksize: 1024 bytes
> V5 btree short header: 56 bytes
> min V5 btree record area: 968 bytes
>
> min V4 blocksize: 512 bytes
> V4 btree short header: 16 bytes
> min V4 btree record area: 496 bytes
>
> In other words, the bit above for the allocbt ought to be:
>
> blocklen = min(XFS_MIN_BLOCKSIZE - XFS_BTREE_SBLOCK_LEN,
> XFS_MIN_CRC_BLOCKSIZE - XFS_BTREE_SBLOCK_CRC_LEN);
>
> Which is very pedantic, since the whole expression /always/ evalulates
> to 496. IIRC the kernel has enough macro soup to resolve that into a
> constant expression so it shouldn't cost us anything.
Yup, good idea, I'm happy with that - now the code documents the
on-disk format calculation exactly in a single location. :)
> > > --- a/fs/xfs/libxfs/xfs_ialloc.c
> > > +++ b/fs/xfs/libxfs/xfs_ialloc.c
> > > @@ -2793,6 +2793,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_inobt_absolute_maxlevels());
> > >
> > > /*
> > > * Set the maximum inode count for this filesystem, being careful not
> > > diff --git a/fs/xfs/libxfs/xfs_ialloc_btree.c b/fs/xfs/libxfs/xfs_ialloc_btree.c
> > > index 3a5a24648b87..2e3dd1d798bd 100644
> > > --- a/fs/xfs/libxfs/xfs_ialloc_btree.c
> > > +++ b/fs/xfs/libxfs/xfs_ialloc_btree.c
> > > @@ -542,6 +542,25 @@ xfs_inobt_maxrecs(
> > > return blocklen / (sizeof(xfs_inobt_key_t) + sizeof(xfs_inobt_ptr_t));
> > > }
> > >
> > > +/* Compute the max possible height of the maximally sized inode btree. */
> > > +unsigned int
> > > +xfs_inobt_absolute_maxlevels(void)
> > > +{
> > > + unsigned int minrecs[2];
> > > + unsigned long long max_ag_inodes;
> > > +
> > > + /*
> > > + * For the absolute maximum, pretend that we can fill an entire AG
> > > + * completely full of inodes except for the AG headers.
> > > + */
> > > + max_ag_inodes = (XFS_MAX_AG_BYTES - (4 * BBSIZE)) / XFS_DINODE_MIN_SIZE;
> > > +
> > > + xfs_btree_absolute_minrecs(minrecs, 0, sizeof(xfs_inobt_rec_t),
> > > + sizeof(xfs_inobt_key_t) + sizeof(xfs_inobt_ptr_t));
> > > +
> > > + return xfs_btree_compute_maxlevels(minrecs, max_ag_inodes);
> > > +}
> >
> > We've got two different inobt max levels on disk. The inobt which has v4
> > limits, whilst the finobt that has v5 limits...
>
> <nod> I'll make it return the larger of the two heights, though the
> inode btree is always going to win due to its smaller minimum block size.
Yup, I expect so, but it would be good to make it explicit :)
Cheers,
Dave.
--
Dave Chinner
david@fromorbit.com
next prev parent reply other threads:[~2021-10-13 23:49 UTC|newest]
Thread overview: 41+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-10-12 23:32 [PATCHSET v3 00/15] xfs: support dynamic btree cursor height Darrick J. Wong
2021-10-12 23:32 ` [PATCH 01/15] xfs: remove xfs_btree_cur.bc_blocklog Darrick J. Wong
2021-10-13 0:56 ` Dave Chinner
2021-10-12 23:32 ` [PATCH 02/15] xfs: reduce the size of nr_ops for refcount btree cursors Darrick J. Wong
2021-10-13 0:57 ` Dave Chinner
2021-10-12 23:32 ` [PATCH 03/15] xfs: don't track firstrec/firstkey separately in xchk_btree Darrick J. Wong
2021-10-13 1:02 ` Dave Chinner
2021-10-12 23:32 ` [PATCH 04/15] xfs: dynamically allocate btree scrub context structure Darrick J. Wong
2021-10-13 4:57 ` Dave Chinner
2021-10-13 16:29 ` Darrick J. Wong
2021-10-12 23:33 ` [PATCH 05/15] xfs: support dynamic btree cursor heights Darrick J. Wong
2021-10-13 5:31 ` Dave Chinner
2021-10-13 16:52 ` Darrick J. Wong
2021-10-13 21:14 ` Dave Chinner
2021-10-12 23:33 ` [PATCH 06/15] xfs: rearrange xfs_btree_cur fields for better packing Darrick J. Wong
2021-10-13 5:34 ` Dave Chinner
2021-10-12 23:33 ` [PATCH 07/15] xfs: refactor btree cursor allocation function Darrick J. Wong
2021-10-13 5:34 ` Dave Chinner
2021-10-12 23:33 ` [PATCH 08/15] xfs: encode the max btree height in the cursor Darrick J. Wong
2021-10-13 5:38 ` Dave Chinner
2021-10-12 23:33 ` [PATCH 09/15] xfs: dynamically allocate cursors based on maxlevels Darrick J. Wong
2021-10-13 5:40 ` Dave Chinner
2021-10-13 16:55 ` Darrick J. Wong
2021-10-12 23:33 ` [PATCH 10/15] xfs: compute actual maximum btree height for critical reservation calculation Darrick J. Wong
2021-10-13 5:49 ` Dave Chinner
2021-10-13 17:07 ` Darrick J. Wong
2021-10-13 20:18 ` Dave Chinner
2021-10-12 23:33 ` [PATCH 11/15] xfs: compute the maximum height of the rmap btree when reflink enabled Darrick J. Wong
2021-10-13 7:25 ` Dave Chinner
2021-10-13 17:47 ` Darrick J. Wong
2021-10-12 23:33 ` [PATCH 12/15] xfs: kill XFS_BTREE_MAXLEVELS Darrick J. Wong
2021-10-13 7:25 ` Dave Chinner
2021-10-12 23:33 ` [PATCH 13/15] xfs: widen btree maxlevels computation to handle 64-bit record counts Darrick J. Wong
2021-10-13 7:28 ` Dave Chinner
2021-10-12 23:33 ` [PATCH 14/15] xfs: compute absolute maximum nlevels for each btree type Darrick J. Wong
2021-10-13 7:57 ` Dave Chinner
2021-10-13 21:36 ` Darrick J. Wong
2021-10-13 23:48 ` Dave Chinner [this message]
2021-10-12 23:33 ` [PATCH 15/15] xfs: use separate btree cursor cache " Darrick J. Wong
2021-10-13 8:01 ` Dave Chinner
2021-10-13 21:42 ` Darrick J. Wong
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20211013234858.GL2361455@dread.disaster.area \
--to=david@fromorbit.com \
--cc=chandan.babu@oracle.com \
--cc=djwong@kernel.org \
--cc=hch@lst.de \
--cc=linux-xfs@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).