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:

quoted

On Tue, Oct 12, 2021 at 04:33:50PM -0700, Darrick J. Wong wrote:

quoted

--- 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.

quoted

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...

quoted

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. :)

quoted

quoted

--- 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