Re: [PATCH 10/13] fsverity: pass the zero-hash value to the implementation

["Darrick J. Wong" <djwong@kernel.org>]

On Wed, Apr 24, 2024 at 08:59:41PM +0000, Eric Biggers wrote:
> On Wed, Apr 24, 2024 at 01:23:48PM -0700, Darrick J. Wong wrote:
> > > > How about "the hash of an i_blocksize-sized buffer of zeroes" for all
> > > > three?
> > > 
> > > It's the Merkle tree block size, not the filesystem block size.  Or did you
> > > actually intend for this to use the filesystem block size?
> > 
> > I actually did intend for this to be the fs block size, not the merkle
> > tree block size.  It's the bottom level that I care about shrinking.
> > Let's say that data[0-B] are the data blocks:
> > 
> > root
> >  +-internal0
> >  |   +-leaf0
> >  |   |   +-data0
> >  |   |   +-data1
> >  |   |   `-data2
> >  |   `-leaf1
> >  |       +-data3
> >  |       +-data4
> >  |       `-data5
> >  `-internal1
> >      +-leaf2
> >      |   +-data6
> >      |   +-data7
> >      |   `-data8
> >      `-leaf3
> >          +-data9
> >          +-dataA
> >          `-dataB
> > 
> > (thanks to https://arthursonzogni.com/Diagon/#Tree )
> > 
> > If data[3-5] are completely zeroes (unwritten blocks, sparse holes,
> > etc.) then I want to skip writing leaf1 of the merkle tree to disk.
> > 
> > If it happens that the hashes of leaf[0-1] match hash(data3) then it's
> > frosting on top (as it were) that we can also skip internal0.  However,
> > the merkle tree has a high fanout factor (4096/32==128 in the common
> > case), so I care /much/ less about eliding those levels.
> > 
> > > In struct merkle_tree_params, the "block size" is always the Merkle tree block
> > > size, so the type of block size seems clear in that context.  My complaint was
> > > just that it used the term "data block" to mean a block that is not necessarily
> > > a file contents block (which is what "data block" means elsewhere).
> > 
> > Hm.  Given the confusion, would it help if I said that zero_digest
> > should only be used to elide leaf nodes of the merkle tree that hash the
> > contents of file content blocks?  Or is "the hash of an
> > i_blocksize-sized buffer of zeroes" sufficient?
> > 
> > What do you think of the commit message saying:
> > 
> > "Compute the hash of one filesystem block's worth of zeroes.  Any merkle
> > tree leaf block containing only this hash can be elided at write time,
> > and its contents synthesized at read time.
> > 
> > "Let's pretend that there's a file containing six data blocks and whose
> > merkle tree looks roughly like this:
> > 
> > root
> >  +--leaf0
> >  |   +--data0
> >  |   +--data1
> >  |   `--data2
> >  `--leaf1
> >      +--data3
> >      +--data4
> >      `--data5
> > 
> > "If data[0-2] are sparse holes, then leaf0 will contain a repeating
> > sequence of @zero_digest.  Therefore, leaf0 need not be written to disk
> > because its contents can be synthesized."
> 
> It sounds like you're assuming that the file data is always hashed in filesystem
> block sized units.

Ohh!  Yes, I was making that assumption, and now I double-checked
enable.c and see this:

	/* Hash each data block, also hashing the tree blocks as they fill up */
	for (offset = 0; offset < data_size; offset += params->block_size) {
		ssize_t bytes_read;
		loff_t pos = offset;

		buffers[-1].filled = min_t(u64, params->block_size,
					   data_size - offset);
		bytes_read = __kernel_read(filp, buffers[-1].data,
					   buffers[-1].filled, &pos);

So yes, you're right, @zero_digest is a the hash of a *merkle tree
block-sized* buffer of zeroes.  And if ->write_merkle_tree_block sees
that the block is a repeating sequence of @zero_digest, it can skip
writing that block to disk, no matter where that block happens to be in
the tree.

> block sized units.  That's not how it works.  The block size that's selected for
> fsverity (which is a power of 2 between 1024 and min(fs_block_size, PAGE_SIZE),
> inclusively) is used for both the data blocks and the Merkle tree blocks.
> 
> This is intentional, so that people can e.g. calculate the fsverity digest of a
> file using a 4K block size, and deploy the file to both filesystems that use a
> 4K filesystem block size and filesystems that use a 16K filesystem block size,
> and get the same fsverity file digest each time.

Aha, yes, that makes more sense.  I had wondered if people actually
copied merkle tree data between filesystems.

> I've considered offering the ability to configure the data block size separately
> from the Merkle tree block size, like what dm-verity does.  This hasn't seemed
> useful, though.  And in any case, it should not be tied to the FS block size.
> 
> A better way to think about things might be that the Merkle tree actually
> *includes* the data, as opposed to being separate from it.  In this respect,
> it's natural that the Merkle tree parameters including block size, hash
> algorithm, and salt apply both to blocks that contain file data and to blocks
> that contain hashes.  In general, all the fsverity code and documentation
> probably needs to be clearer about whether, when referring to the Merkle tree,
> it means just the hash blocks, or if it means the conceptual full tree that
> includes the file's data.

Yes, that clears things right up.  Thank you for correcting me. :)

--D

> - Eric
>