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

Darrick J. Wong
2020-06-08T16:52:30Z

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?

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

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 */
>
> /*
> --
> 2.20.1
>