Re: [PATCH 5/7] xfs: Use 2^27 as the maximum number of directory extents

[Chandan Babu R <chandanrlinux@gmail.com>]

On Monday 8 June 2020 10:22:17 PM IST Darrick J. Wong wrote:
> On Sat, Jun 06, 2020 at 01:57:43PM +0530, Chandan Babu R wrote:
> > The maximum number of extents that can be used by a directory can be
> > calculated as shown below. (FS block size is assumed to be 512 bytes
> > since the smallest allowed block size can create a BMBT of maximum
> > possible height).
> > 
> > Maximum number of extents in data space =
> > XFS_DIR2_SPACE_SIZE / 2^9 = 32GiB / 2^9 = 2^26.
> > 
> > Maximum number (theoretically) of extents in leaf space =
> > 32GiB / 2^9 = 2^26.
> 
> Hm.  The leaf hash entries are 8 bytes long, whereas I think directory
> entries occupy at least 16 bytes.  Is there a situation where the number
> of dir leaf/dabtree blocks can actually hit the 32G section size limit?

I don't think so. The 2^26 extents above was a theoretical limit. I wanted to
prove that even with the theoretical limit, the maximum number of extents used
by a directory is much less than 2^47 extents.

> 
> > Maximum number of entries in a free space index block
> > = (512 - (sizeof struct xfs_dir3_free_hdr)) / (sizeof struct
> >                                                xfs_dir2_data_off_t)
> > = (512 - 64) / 2 = 224
> > 
> > Maximum number of extents in free space index =
> > (Maximum number of extents in data segment) / 224 =
> > 2^26 / 224 = ~2^18
> > 
> > Maximum number of extents in a directory =
> > Maximum number of extents in data space +
> > Maximum number of extents in leaf space +
> > Maximum number of extents in free space index =
> > 2^26 + 2^26 + 2^18 = ~2^27
> 
> I calculated the exact expression here, and got:
> 
> 2^26 + 2^26 + (2^26/224) = 134,517,321
> 
> This requires 28 bits of space, doesn't it?

You are right.

Log_2(134,517,321) returns 27.003. Since I had assumed a theoretical maximum
for the "leaf space extent count", I had rounded it down to 27 bits. I will
change this to 28 bits.

> 
> Granted I bet the leaf section won't come within 300,000 nextents of the
> 2^26 you've assumed for it, so I suspect that in real world scenarios,
> 27 bits is enough.  But if you're anticipating a totally full leaf
> section under extreme fragmentation, then MAXDIREXTNUM ought to be able
> to handle that.
> 
> (Assuming I did any of that math correctly. ;))
> 
> --D
> 
> > 
> > This commit defines the macro MAXDIREXTNUM to have the value 2^27 and
> > this in turn is used in calculating the maximum height of a directory
> > BMBT.
> > 
> > Signed-off-by: Chandan Babu R <chandanrlinux@gmail.com>
> > ---
> >  fs/xfs/libxfs/xfs_bmap.c  | 2 +-
> >  fs/xfs/libxfs/xfs_types.h | 1 +
> >  2 files changed, 2 insertions(+), 1 deletion(-)
> > 
> > diff --git a/fs/xfs/libxfs/xfs_bmap.c b/fs/xfs/libxfs/xfs_bmap.c
> > index 8b0029b3cecf..f75b70ae7b1f 100644
> > --- a/fs/xfs/libxfs/xfs_bmap.c
> > +++ b/fs/xfs/libxfs/xfs_bmap.c
> > @@ -81,7 +81,7 @@ xfs_bmap_compute_maxlevels(
> >  	if (whichfork == XFS_DATA_FORK) {
> >  		sz = XFS_BMDR_SPACE_CALC(MINDBTPTRS);
> >  		if (dir_bmbt)
> > -			maxleafents = MAXEXTNUM;
> > +			maxleafents = MAXDIREXTNUM;
> >  		else
> >  			maxleafents = MAXEXTNUM;
> >  	} else {
> > diff --git a/fs/xfs/libxfs/xfs_types.h b/fs/xfs/libxfs/xfs_types.h
> > index 397d94775440..0a3041ad5bec 100644
> > --- a/fs/xfs/libxfs/xfs_types.h
> > +++ b/fs/xfs/libxfs/xfs_types.h
> > @@ -60,6 +60,7 @@ typedef void *		xfs_failaddr_t;
> >   */
> >  #define	MAXEXTLEN	((xfs_extlen_t)0x001fffff)	/* 21 bits */
> >  #define	MAXEXTNUM	((xfs_extnum_t)0x7fffffff)	/* signed int */
> > +#define	MAXDIREXTNUM	((xfs_extnum_t)0x7ffffff)	/* 27 bits */
> >  #define	MAXAEXTNUM	((xfs_aextnum_t)0x7fff)		/* signed short */
> >  
> >  /*
> 


-- 
chandan