Message ID | 171069246517.2684506.8560170754721057486.stgit@frogsfrogsfrogs (mailing list archive) |
---|---|
State | Superseded |
Headers | show |
Series | [01/40] fsverity: remove hash page spin lock | expand |
On 2024-03-17 09:33:18, Darrick J. Wong wrote: > From: Darrick J. Wong <djwong@kernel.org> > > 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@kernel.org> Looks good to me: Reviewed-by: Andrey Albershteyn <aalbersh@redhat.com> > --- > 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__ */ >
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__ */