Re: [PATCH V8 15/19] xfs: Directory's data fork extent counter can never overflow

[Chandan Babu R <chandan.babu@oracle.com>]

On 01 Apr 2022 at 06:57, Dave Chinner wrote:
> On Tue, Mar 29, 2022 at 08:43:33PM -0700, Darrick J. Wong wrote:
>> But then the second question is: what's the maximum height of a dabtree
>> that indexes an xattr structure?  I don't think there's any maximum
>> limit within XFS on the number of attrs you can set on a file, is there?
>
> Nope. But the attr btree is a different beast to the dirv2
> structure - it's a hashed index btree with the xattr records in the
> leaf, it's not an index of a fixed max size external data structure.
>
>> At least until you hit the iext_max_count check.  I think the VFS
>> institutes its own limit of 64k for the llistxattr buffer, but that's
>> about all I can think of.
>
>
>> I suppose right now the xattr structure can't grow larger than 2^(16+21)
>> blocks in size, which is 2^49 bytes, but that's a mix of attr leaves and
>> dabtree blocks, unlike directories, right?
>
> Yes. ALso remote xattr blocks, which aren't stored in the dabtree
> at all, but are indexed by the attr fork BMBT address space.
>
> So I think for XFS_DA_NODE_MAXDEPTH = 5, the xattr tree with a 4kB
> block size (minimum allowed, IIRC), we can index approximately
> (500^4) individual xattrs in the btree index (assuming 4 levels of
> index and 1 level of leaf nodes containing xattrs).
>
> My math calculates that to be about 62.5 billion xattrs before we
> run out of index space in a 5 level tree with a 4kB block size.
> Hence I suspect we'll run out of attr fork extents even on a 32 bit
> extent count before we run out of xattr index space.
>
> Also, 62.5 billion xattrs is more links than we can have to a single
> inode (4billion), so we're not going to exhaust the xattr index
> space just with parent pointers...
>

Attr dabtree blocks can be of 1k block size. My analysis of dabtree w.r.t
parent pointers had led me to this,

An inode could have 2^32 hard links with each link having 255 byte sized name.

- Size of one xattr
  Name length + Value length = 16 + 255 = 271 bytes
  16 comes from the size of the following structure,
      struct xfs_parent_name_rec {
      	__be64  p_ino;
      	__be32  p_gen;
      	__be32  p_diroffset;
      };

- sizeof(xfs_attr_leaf_hdr_t) = 32
- sizeof(xfs_attr_leaf_entry_t) = 8
- Number of entries in a 1k leaf block
  (1024 - sizeof(xfs_attr_leaf_hdr_t)) / (8 + 271)
  = (1024 - 32) / 279 = 992 / 279
  = floor(3.55)
  = 3

- Nr leaves = (2^32 / 3) * 3 (magicpct) = ~4.3 billion
- Nr entries per node
  = (1024 - sizeof(struct xfs_da3_node_hdr)) / sizeof(struct xfs_da_node_entry)
  = (1024 - 64) / 8
  = 120 entries

- Nr entries at level (n - 1) = 4.3 billion / 120 = 36 million
- Nr entries at level (n - 2) = 36 million / 120 = 300k
- Nr entries at level (n - 3) = 300k / 120 = 2.5k
- Nr entries at level (n - 4) = 2.5k / 120 = 20
- Nr entries at level (n - 5) = 20 / 120 = 1

Hence with 1024 block size, we could require 1 leaf level and 5 non-leaf
levels. This breaches the maximum height (i.e. XFS_DA_NODE_MAXDEPTH) allowed
for a dabtree.

>> > immediately how many blocks can be in the XFS_DIR2_LEAF_SPACE
>> > segement....
>> > 
>> > We also know the maximum number of individual directory blocks in
>> > the 32GB segment (fixed at 32GB / dir block size), so the free space
>> > array is also a fixed size at (32GB / dir block size / free space
>> > entries per block).
>> > 
>> > It's easy to just use (96GB / block size) and that will catch most
>> > corruptions with no risk of a false positive detection, but we could
>> > quite easily refine this to something like:
>> > 
>> > data	(32GB +				
>> > leaf	 btree blocks(XFS_DA_NODE_MAXDEPTH) +
>> > freesp	 (32GB / free space records per block))
>> > frags					/ filesystem block size
>> 
>> I think we ought to do a more careful study of XFS_DA_NODE_MAXDEPTH,
>
> *nod*
>
> ISTR that Chandan had already done some of this when he
> characterised the attr fork btree behaviour w.r.t. suitabililty for
> large numbers of parent pointers before starting this extent count
> work.
>

Sorry, I had forgotten about that. I searched through my notes and found that
we had reached the same conclusion w.r.t 4k block size. But with 1k block size,
we could breach the limit set by XFS_DA_NODE_MAXDEPTH.

-- 
chandan