On 2024-03-17 09:33:18, Darrick J. Wong wrote:
> From: Darrick J. Wong <djwong@xxxxxxxxxx>
>
> I was exploring the fsverity metadata with xfs_db after creating a 220MB
> verity file, and I noticed the following in the debugger output:
>
> entries[0-75] = [hashval,nameidx,incomplete,root,secure,local,parent,verity]
> 0:[0,4076,0,0,0,0,0,1]
> 1:[0,1472,0,0,0,1,0,1]
> 2:[0x800,4056,0,0,0,0,0,1]
> 3:[0x800,4036,0,0,0,0,0,1]
> ...
> 72:[0x12000,2716,0,0,0,0,0,1]
> 73:[0x12000,2696,0,0,0,0,0,1]
> 74:[0x12800,2676,0,0,0,0,0,1]
> 75:[0x12800,2656,0,0,0,0,0,1]
> ...
> nvlist[0].merkle_off = 0x18000
> nvlist[1].merkle_off = 0
> nvlist[2].merkle_off = 0x19000
> nvlist[3].merkle_off = 0x1000
> ...
> nvlist[71].merkle_off = 0x5b000
> nvlist[72].merkle_off = 0x44000
> nvlist[73].merkle_off = 0x5c000
> nvlist[74].merkle_off = 0x45000
> nvlist[75].merkle_off = 0x5d000
>
> Within just this attr leaf block, there are 76 attr entries, but only 38
> distinct hash values. There are 415 merkle tree blocks for this file,
> but we already have hash collisions. This isn't good performance from
> the standard da hash function because we're mostly shifting and rolling
> zeroes around.
>
> However, we don't even have to do that much work -- the merkle tree
> block keys are themslves u64 values. Truncate that value to 32 bits
> (the size of xfs_dahash_t) and use that for the hash. We won't have any
> collisions between merkle tree blocks until that tree grows to 2^32nd
> blocks. On a 4k block filesystem, we won't hit that unless the file
> contains more than 2^49 bytes, assuming sha256.
>
> As a side effect, the keys for merkle tree blocks get written out in
> roughly sequential order, though I didn't observe any change in
> performance.
>
> Signed-off-by: Darrick J. Wong <djwong@xxxxxxxxxx>
Looks good to me:
Reviewed-by: Andrey Albershteyn <aalbersh@xxxxxxxxxx>
> ---
> fs/xfs/libxfs/xfs_attr.c | 7 +++++++
> fs/xfs/libxfs/xfs_da_format.h | 2 ++
> 2 files changed, 9 insertions(+)
>
>
> diff --git a/fs/xfs/libxfs/xfs_attr.c b/fs/xfs/libxfs/xfs_attr.c
> index b1fa45197eac..7c0f006f972a 100644
> --- a/fs/xfs/libxfs/xfs_attr.c
> +++ b/fs/xfs/libxfs/xfs_attr.c
> @@ -245,6 +245,13 @@ xfs_attr_hashname(
> const uint8_t *name,
> unsigned int namelen)
> {
> + if ((attr_flags & XFS_ATTR_VERITY) &&
> + namelen == sizeof(struct xfs_verity_merkle_key)) {
> + uint64_t off = xfs_verity_merkle_key_from_disk(name);
> +
> + return off >> XFS_VERITY_MIN_MERKLE_BLOCKLOG;
> + }
> +
> return xfs_da_hashname(name, namelen);
> }
>
> diff --git a/fs/xfs/libxfs/xfs_da_format.h b/fs/xfs/libxfs/xfs_da_format.h
> index e4aa7c9a0ccb..58887a1c65fe 100644
> --- a/fs/xfs/libxfs/xfs_da_format.h
> +++ b/fs/xfs/libxfs/xfs_da_format.h
> @@ -946,4 +946,6 @@ xfs_verity_merkle_key_from_disk(
> #define XFS_VERITY_DESCRIPTOR_NAME "vdesc"
> #define XFS_VERITY_DESCRIPTOR_NAME_LEN (sizeof(XFS_VERITY_DESCRIPTOR_NAME) - 1)
>
> +#define XFS_VERITY_MIN_MERKLE_BLOCKLOG (10)
> +
> #endif /* __XFS_DA_FORMAT_H__ */
>
--
- Andrey
