From: Andrey Albershteyn <aalbersh@redhat.com>
To: "Darrick J. Wong" <djwong@kernel.org>
Cc: ebiggers@kernel.org, linux-fsdevel@vger.kernel.org,
fsverity@lists.linux.dev, linux-xfs@vger.kernel.org
Subject: Re: [PATCH 38/40] xfs: use merkle tree offset as attr hash
Date: Mon, 18 Mar 2024 18:55:39 +0100 [thread overview]
Message-ID: <tbqzcbhc267i6be5suodaqdxbdtdettd7jb442dvgiugbeoxsm@rkzvxzj7ca63> (raw)
In-Reply-To: <171069246517.2684506.8560170754721057486.stgit@frogsfrogsfrogs>
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__ */
>
--
- Andrey
next prev parent reply other threads:[~2024-03-18 17:55 UTC|newest]
Thread overview: 92+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-03-17 16:19 [PATCHBOMB v5.3] fs-verity support for XFS Darrick J. Wong
2024-03-17 16:22 ` [PATCHSET " Darrick J. Wong
2024-03-17 16:23 ` [PATCH 01/40] fsverity: remove hash page spin lock Darrick J. Wong
2024-03-17 16:23 ` [PATCH 02/40] xfs: add parent pointer support to attribute code Darrick J. Wong
2024-03-17 16:24 ` [PATCH 03/40] xfs: define parent pointer ondisk extended attribute format Darrick J. Wong
2024-03-17 16:24 ` [PATCH 04/40] xfs: add parent pointer validator functions Darrick J. Wong
2024-03-17 16:24 ` [PATCH 05/40] fs: add FS_XFLAG_VERITY for verity files Darrick J. Wong
2024-03-17 16:24 ` [PATCH 06/40] fsverity: pass tree_blocksize to end_enable_verity() Darrick J. Wong
2024-03-17 16:25 ` [PATCH 07/40] fsverity: support block-based Merkle tree caching Darrick J. Wong
2024-03-17 16:25 ` [PATCH 08/40] fsverity: add per-sb workqueue for post read processing Darrick J. Wong
2024-03-17 16:25 ` [PATCH 09/40] fsverity: add tracepoints Darrick J. Wong
2024-03-17 16:26 ` [PATCH 10/40] fsverity: fix "support block-based Merkle tree caching" Darrick J. Wong
2024-03-17 16:26 ` [PATCH 11/40] fsverity: send the level of the merkle tree block to ->read_merkle_tree_block Darrick J. Wong
2024-03-17 16:26 ` [PATCH 12/40] fsverity: pass the new tree size and block size to ->begin_enable_verity Darrick J. Wong
2024-03-17 16:26 ` [PATCH 13/40] fsverity: expose merkle tree geometry to callers Darrick J. Wong
2024-03-17 16:27 ` [PATCH 14/40] fsverity: rely on cached block callers to retain verified state Darrick J. Wong
2024-03-17 16:27 ` [PATCH 15/40] fsverity: box up the write_merkle_tree_block parameters too Darrick J. Wong
2024-03-17 16:27 ` [PATCH 16/40] fsverity: pass the zero-hash value to the implementation Darrick J. Wong
2024-03-18 16:38 ` Eric Biggers
2024-03-18 21:04 ` Darrick J. Wong
2024-03-17 16:27 ` [PATCH 17/40] fsverity: report validation errors back to the filesystem Darrick J. Wong
2024-03-17 16:28 ` [PATCH 18/40] iomap: integrate fs-verity verification into iomap's read path Darrick J. Wong
2024-03-17 16:28 ` [PATCH 19/40] xfs: add attribute type for fs-verity Darrick J. Wong
2024-03-17 16:28 ` [PATCH 20/40] xfs: add fs-verity ro-compat flag Darrick J. Wong
2024-03-17 16:28 ` [PATCH 21/40] xfs: add inode on-disk VERITY flag Darrick J. Wong
2024-03-17 16:29 ` [PATCH 22/40] xfs: initialize fs-verity on file open and cleanup on inode destruction Darrick J. Wong
2024-03-17 16:29 ` [PATCH 23/40] xfs: don't allow to enable DAX on fs-verity sealed inode Darrick J. Wong
2024-03-17 16:29 ` [PATCH 24/40] xfs: disable direct read path for fs-verity files Darrick J. Wong
2024-03-18 19:48 ` Andrey Albershteyn
2024-03-19 21:17 ` Darrick J. Wong
2024-03-17 16:29 ` [PATCH 25/40] xfs: widen flags argument to the xfs_iflags_* helpers Darrick J. Wong
2024-03-17 16:30 ` [PATCH 26/40] xfs: add fs-verity support Darrick J. Wong
2024-03-18 1:43 ` Christoph Hellwig
2024-03-18 4:34 ` Darrick J. Wong
2024-03-18 4:39 ` Christoph Hellwig
2024-03-18 4:56 ` Darrick J. Wong
2024-03-17 16:30 ` [PATCH 27/40] xfs: create a per-mount shrinker for verity inodes merkle tree blocks Darrick J. Wong
2024-03-17 16:30 ` [PATCH 28/40] xfs: create an icache tag for files with cached " Darrick J. Wong
2024-03-17 16:30 ` [PATCH 29/40] xfs: shrink verity blob cache Darrick J. Wong
2024-03-17 16:31 ` [PATCH 30/40] xfs: clean up stale fsverity metadata before starting Darrick J. Wong
2024-03-18 17:50 ` Andrey Albershteyn
2024-03-17 16:31 ` [PATCH 31/40] xfs: better reporting and error handling in xfs_drop_merkle_tree Darrick J. Wong
2024-03-18 17:51 ` Andrey Albershteyn
2024-03-17 16:31 ` [PATCH 32/40] xfs: make scrub aware of verity dinode flag Darrick J. Wong
2024-03-17 16:32 ` [PATCH 33/40] xfs: add fs-verity ioctls Darrick J. Wong
2024-03-17 16:32 ` [PATCH 34/40] xfs: advertise fs-verity being available on filesystem Darrick J. Wong
2024-03-17 16:32 ` [PATCH 35/40] xfs: teach online repair to evaluate fsverity xattrs Darrick J. Wong
2024-03-18 17:34 ` Andrey Albershteyn
2024-03-19 21:27 ` Darrick J. Wong
2024-03-17 16:32 ` [PATCH 36/40] xfs: don't store trailing zeroes of merkle tree blocks Darrick J. Wong
2024-03-18 17:52 ` Andrey Albershteyn
2024-03-17 16:33 ` [PATCH 37/40] xfs: create separate name hash function for xattrs Darrick J. Wong
2024-03-18 17:53 ` Andrey Albershteyn
2024-03-17 16:33 ` [PATCH 38/40] xfs: use merkle tree offset as attr hash Darrick J. Wong
2024-03-18 17:55 ` Andrey Albershteyn [this message]
2024-03-17 16:33 ` [PATCH 39/40] xfs: don't bother storing merkle tree blocks for zeroed data blocks Darrick J. Wong
2024-03-18 17:56 ` Andrey Albershteyn
2024-03-17 16:33 ` [PATCH 40/40] xfs: enable ro-compat fs-verity flag Darrick J. Wong
2024-03-18 16:35 ` [PATCHSET v5.3] fs-verity support for XFS Eric Biggers
2024-03-19 22:07 ` Darrick J. Wong
2024-03-19 23:21 ` Darrick J. Wong
2024-03-20 10:16 ` Andrey Albershteyn
2024-03-20 15:11 ` Darrick J. Wong
2024-03-17 16:23 ` Darrick J. Wong
2024-03-17 16:34 ` [PATCH 01/20] xfsprogs: add parent pointer support to attribute code Darrick J. Wong
2024-03-17 16:34 ` [PATCH 02/20] xfsprogs: define parent pointer xattr format Darrick J. Wong
2024-03-17 16:34 ` [PATCH 03/20] xfsprogs: Add xfs_verify_pptr Darrick J. Wong
2024-03-17 16:34 ` [PATCH 04/20] fs: add FS_XFLAG_VERITY for verity files Darrick J. Wong
2024-03-17 16:35 ` [PATCH 05/20] xfs: add attribute type for fs-verity Darrick J. Wong
2024-03-17 16:35 ` [PATCH 06/20] xfs: add fs-verity ro-compat flag Darrick J. Wong
2024-03-17 16:35 ` [PATCH 07/20] xfs: add inode on-disk VERITY flag Darrick J. Wong
2024-03-17 16:35 ` [PATCH 08/20] xfs: add fs-verity support Darrick J. Wong
2024-03-17 16:36 ` [PATCH 09/20] xfs: advertise fs-verity being available on filesystem Darrick J. Wong
2024-03-17 16:36 ` [PATCH 10/20] xfs: create separate name hash function for xattrs Darrick J. Wong
2024-03-17 16:36 ` [PATCH 11/20] xfs: use merkle tree offset as attr hash Darrick J. Wong
2024-03-17 16:36 ` [PATCH 12/20] xfs: enable ro-compat fs-verity flag Darrick J. Wong
2024-03-17 16:37 ` [PATCH 13/20] libfrog: add fsverity to xfs_report_geom output Darrick J. Wong
2024-03-17 16:37 ` [PATCH 14/20] xfs_db: introduce attr_modify command Darrick J. Wong
2024-03-17 16:37 ` [PATCH 15/20] xfs_db: make attr_set/remove/modify be able to handle fs-verity attrs Darrick J. Wong
2024-03-17 16:37 ` [PATCH 16/20] man: document attr_modify command Darrick J. Wong
2024-03-17 16:38 ` [PATCH 17/20] xfs_db: dump verity features and metadata Darrick J. Wong
2024-03-17 16:38 ` [PATCH 18/20] xfs_db: dump merkle tree data Darrick J. Wong
2024-03-17 16:38 ` [PATCH 19/20] xfs_repair: junk fsverity xattrs when unnecessary Darrick J. Wong
2024-03-17 16:39 ` [PATCH 20/20] mkfs.xfs: add verity parameter Darrick J. Wong
2024-03-17 16:23 ` [PATCHSET v5.3] fstests: fs-verity support for XFS Darrick J. Wong
2024-03-17 16:39 ` [PATCH 1/3] common/verity: enable fsverity " Darrick J. Wong
2024-03-17 16:39 ` [PATCH 2/3] xfs/{021,122}: adapt to fsverity xattrs Darrick J. Wong
2024-03-19 14:59 ` Andrey Albershteyn
2024-03-19 19:25 ` Darrick J. Wong
2024-03-17 16:39 ` [PATCH 3/3] common/populate: add verity files to populate xfs images Darrick J. Wong
2024-03-18 1:39 ` [PATCHBOMB v5.3] fs-verity support for XFS Christoph Hellwig
2024-03-18 4:30 ` Darrick J. Wong
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=tbqzcbhc267i6be5suodaqdxbdtdettd7jb442dvgiugbeoxsm@rkzvxzj7ca63 \
--to=aalbersh@redhat.com \
--cc=djwong@kernel.org \
--cc=ebiggers@kernel.org \
--cc=fsverity@lists.linux.dev \
--cc=linux-fsdevel@vger.kernel.org \
--cc=linux-xfs@vger.kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).