[PATCH] fs-verity: implement readahead for FS_IOC_ENABLE_VERITY

[PATCH] fs-verity: implement readahead for FS_IOC_ENABLE_VERITY

[Eric Biggers]

From: Eric Biggers <ebiggers@google.com>

When it builds the first level of the Merkle tree, FS_IOC_ENABLE_VERITY
sequentially reads each page of the file using read_mapping_page().
This works fine if the file's data is already in pagecache, which should
normally be the case, since this ioctl is normally used immediately
after writing out the file.

But in any other case this implementation performs very poorly, since
only one page is read at a time.

Fix this by implementing readahead using the functions from
mm/readahead.c.

This improves performance in the uncached case by about 20x, as seen in
the following benchmarks done on a 250MB file (on x86_64 with SHA-NI):

    FS_IOC_ENABLE_VERITY uncached (before) 3.299s
    FS_IOC_ENABLE_VERITY uncached (after)  0.160s
    FS_IOC_ENABLE_VERITY cached            0.147s
    sha256sum uncached                     0.191s
    sha256sum cached                       0.145s

Note: we could instead switch to kernel_read().  But that would mean
we'd no longer be hashing the data directly from the pagecache, which is
a nice optimization of its own.  And using kernel_read() would require
allocating another temporary buffer, hashing the data and tree pages
separately, and explicitly zero-padding the last page -- so it wouldn't
really be any simpler than direct pagecache access, at least for now.

Signed-off-by: Eric Biggers <ebiggers@google.com>
---
 fs/verity/enable.c | 46 ++++++++++++++++++++++++++++++++++++++++------
 1 file changed, 40 insertions(+), 6 deletions(-)

diff --git a/fs/verity/enable.c b/fs/verity/enable.c
index eabc6ac19906..f7eaffa60196 100644
--- a/fs/verity/enable.c
+++ b/fs/verity/enable.c
@@ -13,14 +13,44 @@
 #include <linux/sched/signal.h>
 #include <linux/uaccess.h>
 
-static int build_merkle_tree_level(struct inode *inode, unsigned int level,
+/*
+ * Read a file data page for Merkle tree construction.  Do aggressive readahead,
+ * since we're sequentially reading the entire file.
+ */
+static struct page *read_file_data_page(struct inode *inode,
+					struct file_ra_state *ra,
+					struct file *filp,
+					pgoff_t index,
+					pgoff_t num_pages_in_file)
+{
+	struct page *page;
+
+	page = find_get_page(inode->i_mapping, index);
+	if (!page || !PageUptodate(page)) {
+		if (page)
+			put_page(page);
+		page_cache_sync_readahead(inode->i_mapping, ra, filp,
+					  index, num_pages_in_file - index);
+		page = read_mapping_page(inode->i_mapping, index, NULL);
+		if (IS_ERR(page))
+			return page;
+	}
+	if (PageReadahead(page))
+		page_cache_async_readahead(inode->i_mapping, ra, filp, page,
+					   index, num_pages_in_file - index);
+	return page;
+}
+
+static int build_merkle_tree_level(struct file *filp, unsigned int level,
 				   u64 num_blocks_to_hash,
 				   const struct merkle_tree_params *params,
 				   u8 *pending_hashes,
 				   struct ahash_request *req)
 {
+	struct inode *inode = file_inode(filp);
 	const struct fsverity_operations *vops = inode->i_sb->s_vop;
 	unsigned int pending_size = 0;
+	struct file_ra_state ra = { 0 };
 	u64 dst_block_num;
 	u64 i;
 	int err;
@@ -36,6 +66,8 @@ static int build_merkle_tree_level(struct inode *inode, unsigned int level,
 		dst_block_num = 0; /* unused */
 	}
 
+	file_ra_state_init(&ra, inode->i_mapping);
+
 	for (i = 0; i < num_blocks_to_hash; i++) {
 		struct page *src_page;
 
@@ -45,7 +77,8 @@ static int build_merkle_tree_level(struct inode *inode, unsigned int level,
 
 		if (level == 0) {
 			/* Leaf: hashing a data block */
-			src_page = read_mapping_page(inode->i_mapping, i, NULL);
+			src_page = read_file_data_page(inode, &ra, filp, i,
+						       num_blocks_to_hash);
 			if (IS_ERR(src_page)) {
 				err = PTR_ERR(src_page);
 				fsverity_err(inode,
@@ -103,17 +136,18 @@ static int build_merkle_tree_level(struct inode *inode, unsigned int level,
 }
 
 /*
- * Build the Merkle tree for the given inode using the given parameters, and
+ * Build the Merkle tree for the given file using the given parameters, and
  * return the root hash in @root_hash.
  *
  * The tree is written to a filesystem-specific location as determined by the
  * ->write_merkle_tree_block() method.  However, the blocks that comprise the
  * tree are the same for all filesystems.
  */
-static int build_merkle_tree(struct inode *inode,
+static int build_merkle_tree(struct file *filp,
 			     const struct merkle_tree_params *params,
 			     u8 *root_hash)
 {
+	struct inode *inode = file_inode(filp);
 	u8 *pending_hashes;
 	struct ahash_request *req;
 	u64 blocks;
@@ -139,7 +173,7 @@ static int build_merkle_tree(struct inode *inode,
 	blocks = (inode->i_size + params->block_size - 1) >>
 		 params->log_blocksize;
 	for (level = 0; level <= params->num_levels; level++) {
-		err = build_merkle_tree_level(inode, level, blocks, params,
+		err = build_merkle_tree_level(filp, level, blocks, params,
 					      pending_hashes, req);
 		if (err)
 			goto out;
@@ -227,7 +261,7 @@ static int enable_verity(struct file *filp,
 	 */
 	pr_debug("Building Merkle tree...\n");
 	BUILD_BUG_ON(sizeof(desc->root_hash) < FS_VERITY_MAX_DIGEST_SIZE);
-	err = build_merkle_tree(inode, &params, desc->root_hash);
+	err = build_merkle_tree(filp, &params, desc->root_hash);
 	if (err) {
 		fsverity_err(inode, "Error %d building Merkle tree", err);
 		goto rollback;
-- 
2.24.0

Re: [PATCH] fs-verity: implement readahead for FS_IOC_ENABLE_VERITY

[Vyacheslav Dubeyko]

On Tue, 2019-12-03 at 11:30 -0800, Eric Biggers wrote:
> From: Eric Biggers <ebiggers@google.com>
> 
> When it builds the first level of the Merkle tree,
> FS_IOC_ENABLE_VERITY
> sequentially reads each page of the file using read_mapping_page().
> This works fine if the file's data is already in pagecache, which
> should
> normally be the case, since this ioctl is normally used immediately
> after writing out the file.
> 
> But in any other case this implementation performs very poorly, since
> only one page is read at a time.
> 
> Fix this by implementing readahead using the functions from
> mm/readahead.c.
> 
> This improves performance in the uncached case by about 20x, as seen
> in
> the following benchmarks done on a 250MB file (on x86_64 with SHA-
> NI):
> 
>     FS_IOC_ENABLE_VERITY uncached (before) 3.299s
>     FS_IOC_ENABLE_VERITY uncached (after)  0.160s
>     FS_IOC_ENABLE_VERITY cached            0.147s
>     sha256sum uncached                     0.191s
>     sha256sum cached                       0.145s
> 
> Note: we could instead switch to kernel_read().  But that would mean
> we'd no longer be hashing the data directly from the pagecache, which
> is
> a nice optimization of its own.  And using kernel_read() would
> require
> allocating another temporary buffer, hashing the data and tree pages
> separately, and explicitly zero-padding the last page -- so it
> wouldn't
> really be any simpler than direct pagecache access, at least for now.
> 
> Signed-off-by: Eric Biggers <ebiggers@google.com>
> ---
>  fs/verity/enable.c | 46 ++++++++++++++++++++++++++++++++++++++++--
> ----
>  1 file changed, 40 insertions(+), 6 deletions(-)
> 
> diff --git a/fs/verity/enable.c b/fs/verity/enable.c
> index eabc6ac19906..f7eaffa60196 100644
> --- a/fs/verity/enable.c
> +++ b/fs/verity/enable.c
> @@ -13,14 +13,44 @@
>  #include <linux/sched/signal.h>
>  #include <linux/uaccess.h>
>  
> -static int build_merkle_tree_level(struct inode *inode, unsigned int
> level,
> +/*
> + * Read a file data page for Merkle tree construction.  Do
> aggressive readahead,
> + * since we're sequentially reading the entire file.
> + */
> +static struct page *read_file_data_page(struct inode *inode,
> +					struct file_ra_state *ra,
> +					struct file *filp,
> +					pgoff_t index,
> +					pgoff_t num_pages_in_file)
> +{
> +	struct page *page;
> +
> +	page = find_get_page(inode->i_mapping, index);
> +	if (!page || !PageUptodate(page)) {
> +		if (page)
> +			put_page(page);


It looks like that there is not necessary check here. If we have NULL
pointer on page then we will not enter inside. But if we have valid
pointer on page then we have double check inside. Am I correct? 


> +		page_cache_sync_readahead(inode->i_mapping, ra, filp,
> +					  index, num_pages_in_file -
> index);
> +		page = read_mapping_page(inode->i_mapping, index,
> NULL);
> +		if (IS_ERR(page))
> +			return page;

Could we recieve the NULL pointer here? Is callee ready to process theNULL return value? 

Thanks,
Viacheslav Dubeyko.

Re: [PATCH] fs-verity: implement readahead for FS_IOC_ENABLE_VERITY

[Eric Biggers]

On Wed, Dec 04, 2019 at 10:53:50AM +0300, Vyacheslav Dubeyko wrote:
> > diff --git a/fs/verity/enable.c b/fs/verity/enable.c
> > index eabc6ac19906..f7eaffa60196 100644
> > --- a/fs/verity/enable.c
> > +++ b/fs/verity/enable.c
> > @@ -13,14 +13,44 @@
> >  #include <linux/sched/signal.h>
> >  #include <linux/uaccess.h>
> >  
> > -static int build_merkle_tree_level(struct inode *inode, unsigned int
> > level,
> > +/*
> > + * Read a file data page for Merkle tree construction.  Do
> > aggressive readahead,
> > + * since we're sequentially reading the entire file.
> > + */
> > +static struct page *read_file_data_page(struct inode *inode,
> > +					struct file_ra_state *ra,
> > +					struct file *filp,
> > +					pgoff_t index,
> > +					pgoff_t num_pages_in_file)
> > +{
> > +	struct page *page;
> > +
> > +	page = find_get_page(inode->i_mapping, index);
> > +	if (!page || !PageUptodate(page)) {
> > +		if (page)
> > +			put_page(page);
> 
> 
> It looks like that there is not necessary check here. If we have NULL
> pointer on page then we will not enter inside. But if we have valid
> pointer on page then we have double check inside. Am I correct? 
> 

I'm not sure what you mean.  This code does the page_cache_sync_readahead() and
read_mapping_page() if either the page is not in the pagecache at all *or* is
not up to date.  I know this is slightly different logic than
generic_file_buffered_read() uses, and is suboptimal since the use of
read_mapping_page() causes a redundant pagecache lookup.  But we don't need to
squeeze out every possible bit of performance here.

Hmm, maybe it should only call page_cache_sync_readahead() when page == NULL
though.  I'll check the readahead code again.

> 
> > +		page_cache_sync_readahead(inode->i_mapping, ra, filp,
> > +					  index, num_pages_in_file -
> > index);
> > +		page = read_mapping_page(inode->i_mapping, index,
> > NULL);
> > +		if (IS_ERR(page))
> > +			return page;
> 
> Could we recieve the NULL pointer here? Is callee ready to process theNULL return value? 
> 

No, read_mapping_page() returns either a valid page or an ERR_PTR().

- Eric