linux-stable.git/fs/verity, branch linux-6.3.y Linux kernel stable tree fsverity: explicitly check for buffer overflow in build_merkle_tree() 2023-04-30T23:32:25+00:00 Eric Biggers ebiggers@google.com 2023-03-28T04:15:05+00:00 2cea6915004e77cdb80240206eeb5f2051e5c4ef commit 39049b69ec9fc125fa1f314165dcc86f72cb72ec upstream. The new Merkle tree construction algorithm is a bit fragile in that it may overflow the 'root_hash' array if the tree actually generated does not match the calculated tree parameters. This should never happen unless there is a filesystem bug that allows the file size to change despite deny_write_access(), or a bug in the Merkle tree logic itself. Regardless, it's fairly easy to check for buffer overflow here, so let's do so. This is a robustness improvement only; this case is not currently known to be reachable. I've added a Fixes tag anyway, since I recommend that this be included in kernels that have the mentioned commit. Fixes: 56124d6c87fd ("fsverity: support enabling with tree block size < PAGE_SIZE") Cc: stable@vger.kernel.org Link: https://lore.kernel.org/r/20230328041505.110162-1-ebiggers@kernel.org Signed-off-by: Eric Biggers <ebiggers@google.com> Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org> 
commit 39049b69ec9fc125fa1f314165dcc86f72cb72ec upstream.

The new Merkle tree construction algorithm is a bit fragile in that it
may overflow the 'root_hash' array if the tree actually generated does
not match the calculated tree parameters.

This should never happen unless there is a filesystem bug that allows
the file size to change despite deny_write_access(), or a bug in the
Merkle tree logic itself.  Regardless, it's fairly easy to check for
buffer overflow here, so let's do so.

This is a robustness improvement only; this case is not currently known
to be reachable.  I've added a Fixes tag anyway, since I recommend that
this be included in kernels that have the mentioned commit.

Fixes: 56124d6c87fd ("fsverity: support enabling with tree block size < PAGE_SIZE")
Cc: stable@vger.kernel.org
Link: https://lore.kernel.org/r/20230328041505.110162-1-ebiggers@kernel.org
Signed-off-by: Eric Biggers <ebiggers@google.com>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
fsverity: reject FS_IOC_ENABLE_VERITY on mode 3 fds 2023-04-30T23:32:25+00:00 Eric Biggers ebiggers@google.com 2023-04-06T21:31:11+00:00 85c039cff3c359967cafe90443c02321e950b216 commit 04839139213cf60d4c5fc792214a08830e294ff8 upstream. Commit 56124d6c87fd ("fsverity: support enabling with tree block size < PAGE_SIZE") changed FS_IOC_ENABLE_VERITY to use __kernel_read() to read the file's data, instead of direct pagecache accesses. An unintended consequence of this is that the 'WARN_ON_ONCE(!(file->f_mode & FMODE_READ))' in __kernel_read() became reachable by fuzz tests. This happens if FS_IOC_ENABLE_VERITY is called on a fd opened with access mode 3, which means "ioctl access only". Arguably, FS_IOC_ENABLE_VERITY should work on ioctl-only fds. But ioctl-only fds are a weird Linux extension that is rarely used and that few people even know about. (The documentation for FS_IOC_ENABLE_VERITY even specifically says it requires O_RDONLY.) It's probably not worthwhile to make the ioctl internally open a new fd just to handle this case. Thus, just reject the ioctl on such fds for now. Fixes: 56124d6c87fd ("fsverity: support enabling with tree block size < PAGE_SIZE") Reported-by: syzbot+51177e4144d764827c45@syzkaller.appspotmail.com Link: https://syzkaller.appspot.com/bug?id=2281afcbbfa8fdb92f9887479cc0e4180f1c6b28 Cc: stable@vger.kernel.org Link: https://lore.kernel.org/r/20230406215106.235829-1-ebiggers@kernel.org Reviewed-by: Christoph Hellwig <hch@lst.de> Reviewed-by: Christian Brauner <brauner@kernel.org> Signed-off-by: Eric Biggers <ebiggers@google.com> Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org> 
commit 04839139213cf60d4c5fc792214a08830e294ff8 upstream.

Commit 56124d6c87fd ("fsverity: support enabling with tree block size <
PAGE_SIZE") changed FS_IOC_ENABLE_VERITY to use __kernel_read() to read
the file's data, instead of direct pagecache accesses.

An unintended consequence of this is that the
'WARN_ON_ONCE(!(file->f_mode & FMODE_READ))' in __kernel_read() became
reachable by fuzz tests.  This happens if FS_IOC_ENABLE_VERITY is called
on a fd opened with access mode 3, which means "ioctl access only".

Arguably, FS_IOC_ENABLE_VERITY should work on ioctl-only fds.  But
ioctl-only fds are a weird Linux extension that is rarely used and that
few people even know about.  (The documentation for FS_IOC_ENABLE_VERITY
even specifically says it requires O_RDONLY.)  It's probably not
worthwhile to make the ioctl internally open a new fd just to handle
this case.  Thus, just reject the ioctl on such fds for now.

Fixes: 56124d6c87fd ("fsverity: support enabling with tree block size < PAGE_SIZE")
Reported-by: syzbot+51177e4144d764827c45@syzkaller.appspotmail.com
Link: https://syzkaller.appspot.com/bug?id=2281afcbbfa8fdb92f9887479cc0e4180f1c6b28
Cc: stable@vger.kernel.org
Link: https://lore.kernel.org/r/20230406215106.235829-1-ebiggers@kernel.org
Reviewed-by: Christoph Hellwig <hch@lst.de>
Reviewed-by: Christian Brauner <brauner@kernel.org>
Signed-off-by: Eric Biggers <ebiggers@google.com>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
fsverity: don't drop pagecache at end of FS_IOC_ENABLE_VERITY 2023-03-16T05:50:41+00:00 Eric Biggers ebiggers@google.com 2023-03-14T23:31:32+00:00 a075bacde257f755bea0e53400c9f1cdd1b8e8e6 The full pagecache drop at the end of FS_IOC_ENABLE_VERITY is causing performance problems and is hindering adoption of fsverity. It was intended to solve a race condition where unverified pages might be left in the pagecache. But actually it doesn't solve it fully. Since the incomplete solution for this race condition has too much performance impact for it to be worth it, let's remove it for now. Fixes: 3fda4c617e84 ("fs-verity: implement FS_IOC_ENABLE_VERITY ioctl") Cc: stable@vger.kernel.org Reviewed-by: Victor Hsieh <victorhsieh@google.com> Link: https://lore.kernel.org/r/20230314235332.50270-1-ebiggers@kernel.org Signed-off-by: Eric Biggers <ebiggers@google.com> 
The full pagecache drop at the end of FS_IOC_ENABLE_VERITY is causing
performance problems and is hindering adoption of fsverity.  It was
intended to solve a race condition where unverified pages might be left
in the pagecache.  But actually it doesn't solve it fully.

Since the incomplete solution for this race condition has too much
performance impact for it to be worth it, let's remove it for now.

Fixes: 3fda4c617e84 ("fs-verity: implement FS_IOC_ENABLE_VERITY ioctl")
Cc: stable@vger.kernel.org
Reviewed-by: Victor Hsieh <victorhsieh@google.com>
Link: https://lore.kernel.org/r/20230314235332.50270-1-ebiggers@kernel.org
Signed-off-by: Eric Biggers <ebiggers@google.com>
fsverity: Remove WQ_UNBOUND from fsverity read workqueue 2023-03-14T23:16:36+00:00 Nathan Huckleberry nhuck@google.com 2023-03-10T19:33:25+00:00 f959325e6ac3f499450088b8d9c626d1177be160 WQ_UNBOUND causes significant scheduler latency on ARM64/Android. This is problematic for latency sensitive workloads, like I/O post-processing. Removing WQ_UNBOUND gives a 96% reduction in fsverity workqueue related scheduler latency and improves app cold startup times by ~30ms. WQ_UNBOUND was also removed from the dm-verity workqueue for the same reason [1]. This code was tested by running Android app startup benchmarks and measuring how long the fsverity workqueue spent in the runnable state. Before Total workqueue scheduler latency: 553800us After Total workqueue scheduler latency: 18962us [1]: https://lore.kernel.org/all/20230202012348.885402-1-nhuck@google.com/ Signed-off-by: Nathan Huckleberry <nhuck@google.com> Fixes: 8a1d0f9cacc9 ("fs-verity: add data verification hooks for ->readpages()") Cc: stable@vger.kernel.org Link: https://lore.kernel.org/r/20230310193325.620493-1-nhuck@google.com Signed-off-by: Eric Biggers <ebiggers@google.com> 
WQ_UNBOUND causes significant scheduler latency on ARM64/Android.  This
is problematic for latency sensitive workloads, like I/O
post-processing.

Removing WQ_UNBOUND gives a 96% reduction in fsverity workqueue related
scheduler latency and improves app cold startup times by ~30ms.
WQ_UNBOUND was also removed from the dm-verity workqueue for the same
reason [1].

This code was tested by running Android app startup benchmarks and
measuring how long the fsverity workqueue spent in the runnable state.

Before
Total workqueue scheduler latency: 553800us
After
Total workqueue scheduler latency: 18962us

[1]: https://lore.kernel.org/all/20230202012348.885402-1-nhuck@google.com/

Signed-off-by: Nathan Huckleberry <nhuck@google.com>
Fixes: 8a1d0f9cacc9 ("fs-verity: add data verification hooks for ->readpages()")
Cc: stable@vger.kernel.org
Link: https://lore.kernel.org/r/20230310193325.620493-1-nhuck@google.com
Signed-off-by: Eric Biggers <ebiggers@google.com>
fsverity: support verifying data from large folios 2023-01-27T22:46:31+00:00 Eric Biggers ebiggers@google.com 2023-01-27T22:15:29+00:00 5d0f0e57ed900917836385527ce5b122fa1425a3 Try to make fs/verity/verify.c aware of large folios. This includes making fsverity_verify_bio() support the case where the bio contains large folios, and adding a function fsverity_verify_folio() which is the equivalent of fsverity_verify_page(). There's no way to actually test this with large folios yet, but I've tested that this doesn't cause any regressions. Signed-off-by: Eric Biggers <ebiggers@google.com> Link: https://lore.kernel.org/r/20230127221529.299560-1-ebiggers@kernel.org 
Try to make fs/verity/verify.c aware of large folios.  This includes
making fsverity_verify_bio() support the case where the bio contains
large folios, and adding a function fsverity_verify_folio() which is the
equivalent of fsverity_verify_page().

There's no way to actually test this with large folios yet, but I've
tested that this doesn't cause any regressions.

Signed-off-by: Eric Biggers <ebiggers@google.com>
Link: https://lore.kernel.org/r/20230127221529.299560-1-ebiggers@kernel.org
fsverity: support enabling with tree block size < PAGE_SIZE 2023-01-10T03:06:06+00:00 Eric Biggers ebiggers@google.com 2022-12-23T20:36:34+00:00 56124d6c87fd749477425110d2564166621a89c4 Make FS_IOC_ENABLE_VERITY support values of fsverity_enable_arg::block_size other than PAGE_SIZE. To make this possible, rework build_merkle_tree(), which was reading data and hash pages from the file and assuming that they were the same thing as "blocks". For reading the data blocks, just replace the direct pagecache access with __kernel_read(), to naturally read one block at a time. (A disadvantage of the above is that we lose the two optimizations of hashing the pagecache pages in-place and forcing the maximum readahead. That shouldn't be very important, though.) The hash block reads are a bit more difficult to handle, as the only way to do them is through fsverity_operations::read_merkle_tree_page(). Instead, let's switch to the single-pass tree construction algorithm that fsverity-utils uses. This eliminates the need to read back any hash blocks while the tree is being built, at the small cost of an extra block-sized memory buffer per Merkle tree level. This is probably what I should have done originally. Taken together, the above two changes result in page-size independent code that is also a bit simpler than what we had before. Signed-off-by: Eric Biggers <ebiggers@google.com> Reviewed-by: Andrey Albershteyn <aalbersh@redhat.com> Tested-by: Ojaswin Mujoo <ojaswin@linux.ibm.com> Link: https://lore.kernel.org/r/20221223203638.41293-8-ebiggers@kernel.org 
Make FS_IOC_ENABLE_VERITY support values of
fsverity_enable_arg::block_size other than PAGE_SIZE.

To make this possible, rework build_merkle_tree(), which was reading
data and hash pages from the file and assuming that they were the same
thing as "blocks".

For reading the data blocks, just replace the direct pagecache access
with __kernel_read(), to naturally read one block at a time.

(A disadvantage of the above is that we lose the two optimizations of
hashing the pagecache pages in-place and forcing the maximum readahead.
That shouldn't be very important, though.)

The hash block reads are a bit more difficult to handle, as the only way
to do them is through fsverity_operations::read_merkle_tree_page().

Instead, let's switch to the single-pass tree construction algorithm
that fsverity-utils uses.  This eliminates the need to read back any
hash blocks while the tree is being built, at the small cost of an extra
block-sized memory buffer per Merkle tree level.  This is probably what
I should have done originally.

Taken together, the above two changes result in page-size independent
code that is also a bit simpler than what we had before.

Signed-off-by: Eric Biggers <ebiggers@google.com>
Reviewed-by: Andrey Albershteyn <aalbersh@redhat.com>
Tested-by: Ojaswin Mujoo <ojaswin@linux.ibm.com>
Link: https://lore.kernel.org/r/20221223203638.41293-8-ebiggers@kernel.org
fsverity: support verification with tree block size < PAGE_SIZE 2023-01-10T03:06:03+00:00 Eric Biggers ebiggers@google.com 2022-12-23T20:36:33+00:00 5306892a50bf4cd4cc945bad286c7c950078d65e Add support for verifying data from verity files whose Merkle tree block size is less than the page size. The main use case for this is to allow a single Merkle tree block size to be used across all systems, so that only one set of fsverity file digests and signatures is needed. To do this, eliminate various assumptions that the Merkle tree block size and the page size are the same: - Make fsverity_verify_page() a wrapper around a new function fsverity_verify_blocks() which verifies one or more blocks in a page. - When a Merkle tree block is needed, get the corresponding page and only verify and use the needed portion. (The Merkle tree continues to be read and cached in page-sized chunks; that doesn't need to change.) - When the Merkle tree block size and page size differ, use a bitmap fsverity_info::hash_block_verified to keep track of which Merkle tree blocks have been verified, as PageChecked cannot be used directly. Signed-off-by: Eric Biggers <ebiggers@google.com> Reviewed-by: Andrey Albershteyn <aalbersh@redhat.com> Tested-by: Ojaswin Mujoo <ojaswin@linux.ibm.com> Link: https://lore.kernel.org/r/20221223203638.41293-7-ebiggers@kernel.org 
Add support for verifying data from verity files whose Merkle tree block
size is less than the page size.  The main use case for this is to allow
a single Merkle tree block size to be used across all systems, so that
only one set of fsverity file digests and signatures is needed.

To do this, eliminate various assumptions that the Merkle tree block
size and the page size are the same:

- Make fsverity_verify_page() a wrapper around a new function
  fsverity_verify_blocks() which verifies one or more blocks in a page.

- When a Merkle tree block is needed, get the corresponding page and
  only verify and use the needed portion.  (The Merkle tree continues to
  be read and cached in page-sized chunks; that doesn't need to change.)

- When the Merkle tree block size and page size differ, use a bitmap
  fsverity_info::hash_block_verified to keep track of which Merkle tree
  blocks have been verified, as PageChecked cannot be used directly.

Signed-off-by: Eric Biggers <ebiggers@google.com>
Reviewed-by: Andrey Albershteyn <aalbersh@redhat.com>
Tested-by: Ojaswin Mujoo <ojaswin@linux.ibm.com>
Link: https://lore.kernel.org/r/20221223203638.41293-7-ebiggers@kernel.org
fsverity: replace fsverity_hash_page() with fsverity_hash_block() 2023-01-10T03:06:01+00:00 Eric Biggers ebiggers@google.com 2022-12-23T20:36:32+00:00 f45555bf23cfc6bf0f0239de321221b1b81817ab In preparation for allowing the Merkle tree block size to differ from PAGE_SIZE, replace fsverity_hash_page() with fsverity_hash_block(). The new function is similar to the old one, but it operates on the block at the given offset in the page instead of on the full page. (For now, all callers still pass a full page.) Signed-off-by: Eric Biggers <ebiggers@google.com> Reviewed-by: Andrey Albershteyn <aalbersh@redhat.com> Tested-by: Ojaswin Mujoo <ojaswin@linux.ibm.com> Link: https://lore.kernel.org/r/20221223203638.41293-6-ebiggers@kernel.org 
In preparation for allowing the Merkle tree block size to differ from
PAGE_SIZE, replace fsverity_hash_page() with fsverity_hash_block().  The
new function is similar to the old one, but it operates on the block at
the given offset in the page instead of on the full page.

(For now, all callers still pass a full page.)

Signed-off-by: Eric Biggers <ebiggers@google.com>
Reviewed-by: Andrey Albershteyn <aalbersh@redhat.com>
Tested-by: Ojaswin Mujoo <ojaswin@linux.ibm.com>
Link: https://lore.kernel.org/r/20221223203638.41293-6-ebiggers@kernel.org
fsverity: use EFBIG for file too large to enable verity 2023-01-10T03:05:59+00:00 Eric Biggers ebiggers@google.com 2022-12-23T20:36:31+00:00 55eed69cc8fd88272860b3409ac83e191330d370 Currently, there is an implementation limit where files can't have more than 8 Merkle tree levels. With SHA-256 and 4K blocks, this limit is never reached, since a file would need to be larger than 2**64 bytes to need 9 levels. However, with SHA-512, 9 levels are needed for files larger than about 1.15 EB, which is possible on btrfs. Therefore, this limit technically became reachable when btrfs added fsverity support. Meanwhile, support for merkle_tree_block_size < PAGE_SIZE will introduce another implementation limit on file size, resulting from the use of an in-memory bitmap to track which Merkle tree blocks have been verified. In any case, currently FS_IOC_ENABLE_VERITY fails with EINVAL when the file is too large. This is undocumented, and also ambiguous since EINVAL can mean other things too. Let's change the error code to EFBIG, which is much clearer, and document it. Signed-off-by: Eric Biggers <ebiggers@google.com> Reviewed-by: Andrey Albershteyn <aalbersh@redhat.com> Tested-by: Ojaswin Mujoo <ojaswin@linux.ibm.com> Link: https://lore.kernel.org/r/20221223203638.41293-5-ebiggers@kernel.org 
Currently, there is an implementation limit where files can't have more
than 8 Merkle tree levels.  With SHA-256 and 4K blocks, this limit is
never reached, since a file would need to be larger than 2**64 bytes to
need 9 levels.  However, with SHA-512, 9 levels are needed for files
larger than about 1.15 EB, which is possible on btrfs.  Therefore, this
limit technically became reachable when btrfs added fsverity support.

Meanwhile, support for merkle_tree_block_size < PAGE_SIZE will introduce
another implementation limit on file size, resulting from the use of an
in-memory bitmap to track which Merkle tree blocks have been verified.

In any case, currently FS_IOC_ENABLE_VERITY fails with EINVAL when the
file is too large.  This is undocumented, and also ambiguous since
EINVAL can mean other things too.  Let's change the error code to EFBIG,
which is much clearer, and document it.

Signed-off-by: Eric Biggers <ebiggers@google.com>
Reviewed-by: Andrey Albershteyn <aalbersh@redhat.com>
Tested-by: Ojaswin Mujoo <ojaswin@linux.ibm.com>
Link: https://lore.kernel.org/r/20221223203638.41293-5-ebiggers@kernel.org
fsverity: store log2(digest_size) precomputed 2023-01-10T03:05:56+00:00 Eric Biggers ebiggers@google.com 2022-12-23T20:36:30+00:00 579a12f78d889339488175cd9f353dba2bb8d047 Add log_digestsize to struct merkle_tree_params so that it can be used in verify.c. Also save memory by using u8 for all the log_* fields. Signed-off-by: Eric Biggers <ebiggers@google.com> Reviewed-by: Andrey Albershteyn <aalbersh@redhat.com> Tested-by: Ojaswin Mujoo <ojaswin@linux.ibm.com> Link: https://lore.kernel.org/r/20221223203638.41293-4-ebiggers@kernel.org 
Add log_digestsize to struct merkle_tree_params so that it can be used
in verify.c.  Also save memory by using u8 for all the log_* fields.

Signed-off-by: Eric Biggers <ebiggers@google.com>
Reviewed-by: Andrey Albershteyn <aalbersh@redhat.com>
Tested-by: Ojaswin Mujoo <ojaswin@linux.ibm.com>
Link: https://lore.kernel.org/r/20221223203638.41293-4-ebiggers@kernel.org