fsverity PAGE_SIZE constraints

fsverity PAGE_SIZE constraints

[Jes Sorensen]

Hi,

I am working on adding fsverity support to RPM and I am hitting a tricky
problem. I am see this with RPM, but it really isn't specific to RPM,
and will apply to any method for distribution signatures.

fsverity is currently hard-wiring the Merkle tree block size to
PAGE_SIZE. This is problematic for a number of reasons, in particular on
architectures that can be configured with different page sizes, such as
ARM, as well as the case where someone generates a shared 'common'
package to be used cross architectures (noarch package in RPM terms).

For a package manager to be able to create a generic package with
signatures, it basically has to build a signature for every supported
page size of the target architecture.

Chris Mason is working on adding fsverity support to btrfs, and I
understand he is supporting 4K as the default Merkle tree block size,
independent of the PAGE_SIZE.

Would it be feasible to make ext4 and other file systems support 4K for
non 4K page sized systems and make that a general recommendation going
forward?

Thoughts?

Thanks,
Jes

Re: fsverity PAGE_SIZE constraints

[Eric Biggers]

On Mon, Jun 01, 2020 at 04:13:45PM -0400, Jes Sorensen wrote:
> Hi,
> 
> I am working on adding fsverity support to RPM and I am hitting a tricky
> problem. I am see this with RPM, but it really isn't specific to RPM,
> and will apply to any method for distribution signatures.
> 
> fsverity is currently hard-wiring the Merkle tree block size to
> PAGE_SIZE. This is problematic for a number of reasons, in particular on
> architectures that can be configured with different page sizes, such as
> ARM, as well as the case where someone generates a shared 'common'
> package to be used cross architectures (noarch package in RPM terms).
> 
> For a package manager to be able to create a generic package with
> signatures, it basically has to build a signature for every supported
> page size of the target architecture.
> 
> Chris Mason is working on adding fsverity support to btrfs, and I
> understand he is supporting 4K as the default Merkle tree block size,
> independent of the PAGE_SIZE.
> 
> Would it be feasible to make ext4 and other file systems support 4K for
> non 4K page sized systems and make that a general recommendation going
> forward?
> 

It's possible, but it will be a little difficult.  We made a similar
simplification for ext4 encryption initially, and it took a long time to remove
it.  (ext4 encryption was first supported in Linux v4.1.  ext4 encryption didn't
support block_size != PAGE_SIZE until Linux v5.5, following work by
Chandan Rajendra and myself.)

Fixing this would require a number of different changes:

- Updating fscrypt_verify_bio() and fsverity_verity_page() to iterate through
  all data blocks in each page, and to handle sub-page Merkle tree blocks

- Defining a mechanism other than PageChecked to mark Merkle tree blocks as
  verified.  E.g., allocating an in-memory bitmap as part of the struct
  fsverity_info.  This should also be optional, in the sense that we shouldn't
  use the memory for it when it's not needed.

- Supporting fs-verity in block_read_full_page() in fs/buffer.c.

There may be other changes needed too; those are just the obvious ones.

Is this something that you or Chris is interested in working on?

- Eric

Re: fsverity PAGE_SIZE constraints

[Chris Mason]

On 1 Jun 2020, at 16:36, Eric Biggers wrote:

> On Mon, Jun 01, 2020 at 04:13:45PM -0400, Jes Sorensen wrote:
>> Hi,
>>
>> I am working on adding fsverity support to RPM and I am hitting a 
>> tricky
>> problem. I am see this with RPM, but it really isn't specific to RPM,
>> and will apply to any method for distribution signatures.
>>
>> fsverity is currently hard-wiring the Merkle tree block size to
>> PAGE_SIZE. This is problematic for a number of reasons, in particular 
>> on
>> architectures that can be configured with different page sizes, such 
>> as
>> ARM, as well as the case where someone generates a shared 'common'
>> package to be used cross architectures (noarch package in RPM terms).
>>
>> For a package manager to be able to create a generic package with
>> signatures, it basically has to build a signature for every supported
>> page size of the target architecture.
>>
>> Chris Mason is working on adding fsverity support to btrfs, and I
>> understand he is supporting 4K as the default Merkle tree block size,
>> independent of the PAGE_SIZE.
>>
>> Would it be feasible to make ext4 and other file systems support 4K 
>> for
>> non 4K page sized systems and make that a general recommendation 
>> going
>> forward?
>>
>
> It's possible, but it will be a little difficult.  We made a similar
> simplification for ext4 encryption initially, and it took a long time 
> to remove
> it.  (ext4 encryption was first supported in Linux v4.1.  ext4 
> encryption didn't
> support block_size != PAGE_SIZE until Linux v5.5, following work by
> Chandan Rajendra and myself.)
>
> Fixing this would require a number of different changes:
>
> - Updating fscrypt_verify_bio() and fsverity_verity_page() to iterate 
> through
>   all data blocks in each page, and to handle sub-page Merkle tree 
> blocks
>
> - Defining a mechanism other than PageChecked to mark Merkle tree 
> blocks as
>   verified.  E.g., allocating an in-memory bitmap as part of the 
> struct
>   fsverity_info.  This should also be optional, in the sense that we 
> shouldn't
>   use the memory for it when it's not needed.
>
> - Supporting fs-verity in block_read_full_page() in fs/buffer.c.
>
> There may be other changes needed too; those are just the obvious 
> ones.
>
> Is this something that you or Chris is interested in working on?

On the btrfs side, I’m storing the fsverity data in the btree, so 
I’m merkle block size agnostic.  Since our rollout is going to be x86, 
we’ll end up using the 4k size internally for the current code base.

My recommendation to simplify the merkle tree code would be to just put 
it in slab objects instead pages and leverage recent MM changes to make 
reclaim work well.  There’s probably still more to do on that front, 
but it’s a long standing todo item for Josef to shift the btrfs 
metadata out of the page cache, where we have exactly the same problems 
for exactly the same reasons.

-chris

Re: fsverity PAGE_SIZE constraints

[Eric Biggers]

On Tue, Jun 02, 2020 at 11:49:36AM -0400, Chris Mason wrote:
> On the btrfs side, I’m storing the fsverity data in the btree, so I’m merkle
> block size agnostic.  Since our rollout is going to be x86, we’ll end up
> using the 4k size internally for the current code base.
> 
> My recommendation to simplify the merkle tree code would be to just put it
> in slab objects instead pages and leverage recent MM changes to make reclaim
> work well.  There’s probably still more to do on that front, but it’s a long
> standing todo item for Josef to shift the btrfs metadata out of the page
> cache, where we have exactly the same problems for exactly the same reasons.

Do you have an idea for how to do that without introducing much extra overhead
to ext4 and f2fs with Merkle tree block size == PAGE_SIZE?  Currently they just
cache the Merkle tree pages in the inode's page cache.  We don't *have* to do it
that way, but anything that adds additional overhead (e.g. reading data into
pagecache, then copying it into slab allocations, then freeing the pagecache
pages) would be undesirable.  We need to keep the overhead minimal.

- Eric

Re: fsverity PAGE_SIZE constraints

[Chris Mason]

On 2 Jun 2020, at 17:50, Eric Biggers wrote:

> On Tue, Jun 02, 2020 at 11:49:36AM -0400, Chris Mason wrote:
>> On the btrfs side, I’m storing the fsverity data in the btree, so 
>> I’m merkle
>> block size agnostic.  Since our rollout is going to be x86, we’ll 
>> end up
>> using the 4k size internally for the current code base.
>>
>> My recommendation to simplify the merkle tree code would be to just 
>> put it
>> in slab objects instead pages and leverage recent MM changes to make 
>> reclaim
>> work well.  There’s probably still more to do on that front, but 
>> it’s a long
>> standing todo item for Josef to shift the btrfs metadata out of the 
>> page
>> cache, where we have exactly the same problems for exactly the same 
>> reasons.
>
> Do you have an idea for how to do that without introducing much extra 
> overhead
> to ext4 and f2fs with Merkle tree block size == PAGE_SIZE?  Currently 
> they just
> cache the Merkle tree pages in the inode's page cache.  We don't 
> *have* to do it
> that way, but anything that adds additional overhead (e.g. reading 
> data into
> pagecache, then copying it into slab allocations, then freeing the 
> pagecache
> pages) would be undesirable.  We need to keep the overhead minimal.

You can do the IO directly into the slab pages, so there won’t be 
extra copies, but there would be some extra code for ext4/f2fs because 
you’ve been reusing the existing readpages machinery.  I’d start 
with the copies into slab just because all the complexity is in reclaim, 
and adding FS helpers for file IO into specific pages is pretty well 
understood.

Slab reclaim is a little clunky in comparison to the page cache.  But, 
it does give you the chance to do merkle aware reclaim, pitching the 
blocks that are the least expensive to reread from an CPU/IO POV.  It 
also gives you the chance to strongly prefer not pitching any merkle 
pages at all, which might be useful to help limit the cost of thrashing 
in low memory situations.

-chris