On Wednesday, April 29, 2020 9:05 PM Chandan Rajendra wrote:
> 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@xxxxxxxxx/)
>
> 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.
>
The highest increase (i.e. an increase of 118k) in log reservation was
associated with the rename operation,
STATIC uint
xfs_calc_rename_reservation(
struct xfs_mount *mp)
{
return XFS_DQUOT_LOGRES(mp) +
max((xfs_calc_inode_res(mp, 4) +
xfs_calc_buf_res(2 * XFS_DIROP_LOG_COUNT(mp),
XFS_FSB_TO_B(mp, 1))),
(xfs_calc_buf_res(7, mp->m_sb.sb_sectsize) +
xfs_calc_buf_res(xfs_allocfree_log_count(mp, 3),
XFS_FSB_TO_B(mp, 1))));
}
The first argument to max() contributes the highest value.
xfs_calc_inode_res(mp, 4) + xfs_calc_buf_res(2 * XFS_DIROP_LOG_COUNT(mp),XFS_FSB_TO_B(mp, 1))
The inode reservation part is a constant.
The number of blocks computed by the second operand of the '+' operator is,
2 * ((XFS_DA_NODE_MAXDEPTH + 2) + ((XFS_DA_NODE_MAXDEPTH + 2) * (bmbt_height - 1)))
= 2 * ((5 + 2) + ((5 + 2) * (bmbt_height - 1)))
When bmbt height is 5 (i.e. when using the original 2^31 extent count limit) this
evaluates to,
2 * ((5 + 2) + ((5 + 2) * (5 - 1)))
= 70 blocks
When bmbt height is 7 (i.e. when using the original 2^47 extent count limit) this
evaluates to,
2 * ((5 + 2) + ((5 + 2) * (7 - 1)))
= 98 blocks
However, I don't see any extraneous space reserved by the above calculation
that could be removed. Also, IMHO an increase by 118k is most likely not going
to introduce any bugs. I will execute xfstests to make sure that no
regressions get added.
--
chandan
