Re: [PATCH 2/2] xfs: Extend xattr extent counter to 32-bits

[Chandan Rajendra <chandan@linux.ibm.com>]

[-- Attachment #1: Type: text/plain, Size: 8595 bytes --]

On Monday, April 27, 2020 3:38 AM Dave Chinner wrote: 
> On Sat, Apr 25, 2020 at 05:37:39PM +0530, Chandan Rajendra wrote:
> > On Thursday, April 23, 2020 4:00 AM Dave Chinner wrote: 
> > > On Wed, Apr 22, 2020 at 03:08:00PM +0530, Chandan Rajendra wrote:
> > > > Attr bmbt tree height (MINABTPTRS == 2)
> > > > |-------+------------------------+-------------------------|
> > > > | Level | Number of nodes/leaves |           Total Nr recs |
> > > > |       |                        | (nr nodes/leaves * 125) |
> > > > |-------+------------------------+-------------------------|
> > > > |     0 |                      1 |                       2 |
> > > > |     1 |                      2 |                     250 |
> > > > |     2 |                    250 |                   31250 |
> > > > |     3 |                  31250 |                 3906250 |
> > > > |     4 |                3906250 |               488281250 |
> > > > |     5 |              488281250 |             61035156250 |
> > > > |-------+------------------------+-------------------------|
> > > > 
> > > > For xattr extents, (2 ** 32) - 1 = 4294967295 (~ 4 billion extents). So this
> > > > will cause the corresponding bmbt's maximum height to go from 3 to 5.
> > > > This probably won't cause any regression.
> > > 
> > > We already have the XFS_DA_NODE_MAXDEPTH set to 5, so changing the
> > > attr fork extent count makes no difference to the attribute fork
> > > bmbt reservations. i.e. the bmbt reservations are defined by the
> > > dabtree structure limits, not the maximum extent count the fork can
> > > hold.
> > 
> > I think the dabtree structure limits is because of the following ...
> > 
> > How many levels of dabtree would be needed to hold ~100 million xattrs?
> > - name len = 16 bytes
> >          struct xfs_parent_name_rec {
> >                __be64  p_ino;
> >                __be32  p_gen;
> >                __be32  p_diroffset;
> >        };
> >   i.e. 64 + 32 + 32 = 128 bits = 16 bytes;
> > - Value len = file name length = Assume ~40 bytes
> 
> That's quite long for a file name, but lets run with it...
> 
> > - Formula for number of node entries (used in column 3 in the table given
> >   below) at any level of the dabtree,
> >   nr_blocks * ((block size - sizeof(struct xfs_da3_node_hdr)) / sizeof(struct
> >   xfs_da_node_entry))
> >   i.e. nr_blocks * ((block size - 64) / 8)
> > - Formula for number of leaf entries (used in column 4 in the table given
> >   below),
> >   (block size - sizeof(xfs_attr_leaf_hdr_t)) /
> >   (sizeof(xfs_attr_leaf_entry_t) + valuelen + namelen + nameval)
> >   i.e. nr_blocks * ((block size - 32) / (8 + 2 + 1 + 16 + 40))
> > 
> > Here I have assumed block size to be 4k.
> > 
> > |-------+------------------+--------------------------+--------------------------|
> > | Level | Number of blocks | Number of entries (node) | Number of entries (leaf) |
> > |-------+------------------+--------------------------+--------------------------|
> > |     0 |              1.0 |                      5e2 |                    6.1e1 |
> > |     1 |              5e2 |                    2.5e5 |                    3.0e4 |
> > |     2 |            2.5e5 |                    1.3e8 |                    1.5e7 |
> > |     3 |            1.3e8 |                   6.6e10 |                    7.9e9 |
> > |-------+------------------+--------------------------+--------------------------|
> 
> I'm not sure what this table actually represents.
> 
> > 
> > Hence we would need a tree of height 3.
> > Total number of blocks = 1 + 5e2 + 2.5e5 + 1.3e8 = ~1.3e8
> 
> 130 million blocks to hold 100 million xattrs? That doesn't pass the
> smell test.
> 
> I think you are trying to do these calculations from the wrong
> direction.

You are right. Btrees grow in height by adding a new root
node. Hence the btree space usage should be calculated in bottom-to-top
direction.

> Calculate the number of leaf blocks needed to hold the
> xattr data first, then work out the height of the pointer tree from
> that. e.g:
> 
> If we need 100m xattrs, we need this many 100% full 4k blocks to
> hold them all:
> 
> blocks	= 100m / entries per leaf
> 	= 100m / 61
> 	= 1.64m
> 
> and if we assume 37% for the least populated (because magic
> split/merge number), multiply by 3, so blocks ~= 5m for 100m xattrs
> in 4k blocks.
> 
> That makes a lot more sense. Now the tree itself:
> 
> ptrs per node ^ N = 5m
> ptrs per node ^ (N-1) = 5m / 500 = 10k
> ptrs per node ^ (N-2) = 10k / 500 = 200
> ptrs per node ^ (N-3) = 200 / 500 = 1
> 
> So, N-3 = level 0, so we've got a tree of height 4 for 100m xattrs,
> and the pointer tree requires ~12000 blocks which is noise compared
> to the number of leaf blocks...
> 
> As for the bmbt, we've got ~5m extents worst case, which is
> 
> ptrs per node ^ N = 5m
> ptrs per node ^ (N-1) = 5m / 125 = 40k
> ptrs per node ^ (N-2) = 40k / 125 = 320
> ptrs per node ^ (N-3) = 320 / 125 = 3
> 
> As 3 bmbt records should fit in the inode fork, we'd only need a 4
> level bmbt tree to hold this, too. It's at the lower limit of a 4
> level tree, but 100m xattrs is the extreme case we are talking about
> here...
> 
> FWIW, repeat this with a directory data segment size of 32GB w/ 40
> byte names, and the numbers aren't much different to a worst case
> xattr tree of this shape. You'll see the reason for the dabtree
> height being limited to 5, and that neither the directory structure
> nor the xattr structure is anywhere near the 2^32 bit extent count
> limit...

Directory segment size is 32 GB                                                                                                                                  
  - Number of directory entries required for indexing 32GiB.
    - 32GiB is divided into 4k data blocks. 
    - Number of 4k blocks = 32GB / 4k = 8M
    - Each 4k data block has,
      - struct xfs_dir3_data_hdr = 64 bytes
      - struct xfs_dir2_data_entry = 12 bytes (metadata) + 40 bytes (name)
                                   = 52 bytes
      - Number of 'struct xfs_dir2_data_entry' in a 4k block
        (4096 - 64) / 52 = 78
    - Number of 'struct xfs_dir2_data_entry' in 32-GiB space
      8m * 78 = 654m
  - Contents of a single dabtree leaf
    - struct xfs_dir3_leaf_hdr = 64 bytes
    - struct xfs_dir2_leaf_entry = 8 bytes
    - Number of 'struct xfs_dir2_leaf_entry' = (4096 - 64) / 8 = 504
    - 37% of 504 = 186 entries
  - Contents of a single dabtree node
    - struct xfs_da3_node_hdr = 64 bytes
    - struct xfs_da_node_entry = 8 bytes
    - Number of 'struct xfs_da_node_entry' = (4096 - 64) / 8 = 504
  - Nr leaves
    Level (N) = 654m / 186 = 3m leaves
    Level (N-1) = 3m / 504 = 6k
    Level (N-2) = 6k / 504 = 12
    Level (N-3) = 12 / 504 = 1
    Dabtree having 4 levels is sufficient.

Hence a dabtree with 5 levels should be more than enough to index a 32GiB
directory segment containing directory entries with even shorter names.

Even with 5m extents (used in xattr tree example above) consumed by a da
btree, this is still much less than the limit imposed by 2^32 (i.e. ~4
billion) extents.

Hence the actual log space consumed for logging bmbt blocks is limited by the
height of da btree.

My experiment with changing the values of MAXEXTNUM and MAXAEXTNUM to 2^47 and
2^32 respectively, gave me the following results,
- For 1k block size, bmbt tree height increased by 3.
- For 4k block size, bmbt tree height increased by 2.

This happens because xfs_bmap_compute_maxlevels() calculates the BMBT tree
height by assuming that there will be MAXEXTNUM/MAXAEXTNUM worth of leaf
entries in the worst case.

For Attr fork Bmbt , Do you think the calculation should be changed to
consider the number of extents occupied by a dabtree holding > 100 million
xattrs?

The new increase in Bmbt height in turn causes the static reservation values
to increase. In the worst case, the maximum increase observed was 118k bytes
(4k block size, reflink=0, tr_rename).

The experiment was executed after applying "xfsprogs: Fix log reservation
calculation for xattr insert operation" patch
(https://lore.kernel.org/linux-xfs/20200404085229.2034-2-chandanrlinux@gmail.com/)

I am attaching the output of "xfs_db -c logres <dev>" executed on the
following configurations of the XFS filesystem.
- -b size=1k -m reflink=0
- -b size=1k -m rmapbt=1reflink=1
- -b size=4k -m reflink=0
- -b size=4k -m rmapbt=1reflink=1
- -b size=1k -m crc=0
- -b size=4k -m crc=0

I will go through the code which calculates the log reservations of the
entries which have a drastic increase in their values.

-- 
chandan

[-- Attachment #2: xfs-db-logres.tar.gz --]
[-- Type: application/x-compressed-tar, Size: 1564 bytes --]