fs/verity/verify.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * Data verification functions, i.e. hooks for ->readahead()
0004  *
0005  * Copyright 2019 Google LLC
0006  */
0007
0008 #include "fsverity_private.h"
0009
0010 #include <crypto/hash.h>
0011 #include <linux/bio.h>
0012 #include <linux/ratelimit.h>
0013
0014 static struct workqueue_struct *fsverity_read_workqueue;
0015
0016 /**
0017  * hash_at_level() - compute the location of the block's hash at the given level
0018  *
0019  * @params: (in) the Merkle tree parameters
0020  * @dindex: (in) the index of the data block being verified
0021  * @level:  (in) the level of hash we want (0 is leaf level)
0022  * @hindex: (out) the index of the hash block containing the wanted hash
0023  * @hoffset:    (out) the byte offset to the wanted hash within the hash block
0024  */
0025 static void hash_at_level(const struct merkle_tree_params *params,
0026               pgoff_t dindex, unsigned int level, pgoff_t *hindex,
0027               unsigned int *hoffset)
0028 {
0029     pgoff_t position;
0030
0031     /* Offset of the hash within the level's region, in hashes */
0032     position = dindex >> (level * params->log_arity);
0033
0034     /* Index of the hash block in the tree overall */
0035     *hindex = params->level_start[level] + (position >> params->log_arity);
0036
0037     /* Offset of the wanted hash (in bytes) within the hash block */
0038     *hoffset = (position & ((1 << params->log_arity) - 1)) <<
0039            (params->log_blocksize - params->log_arity);
0040 }
0041
0042 /* Extract a hash from a hash page */
0043 static void extract_hash(struct page *hpage, unsigned int hoffset,
0044              unsigned int hsize, u8 *out)
0045 {
0046     void *virt = kmap_atomic(hpage);
0047
0048     memcpy(out, virt + hoffset, hsize);
0049     kunmap_atomic(virt);
0050 }
0051
0052 static inline int cmp_hashes(const struct fsverity_info *vi,
0053                  const u8 *want_hash, const u8 *real_hash,
0054                  pgoff_t index, int level)
0055 {
0056     const unsigned int hsize = vi->tree_params.digest_size;
0057
0058     if (memcmp(want_hash, real_hash, hsize) == 0)
0059         return 0;
0060
0061     fsverity_err(vi->inode,
0062              "FILE CORRUPTED! index=%lu, level=%d, want_hash=%s:%*phN, real_hash=%s:%*phN",
0063              index, level,
0064              vi->tree_params.hash_alg->name, hsize, want_hash,
0065              vi->tree_params.hash_alg->name, hsize, real_hash);
0066     return -EBADMSG;
0067 }
0068
0069 /*
0070  * Verify a single data page against the file's Merkle tree.
0071  *
0072  * In principle, we need to verify the entire path to the root node.  However,
0073  * for efficiency the filesystem may cache the hash pages.  Therefore we need
0074  * only ascend the tree until an already-verified page is seen, as indicated by
0075  * the PageChecked bit being set; then verify the path to that page.
0076  *
0077  * This code currently only supports the case where the verity block size is
0078  * equal to PAGE_SIZE.  Doing otherwise would be possible but tricky, since we
0079  * wouldn't be able to use the PageChecked bit.
0080  *
0081  * Note that multiple processes may race to verify a hash page and mark it
0082  * Checked, but it doesn't matter; the result will be the same either way.
0083  *
0084  * Return: true if the page is valid, else false.
0085  */
0086 static bool verify_page(struct inode *inode, const struct fsverity_info *vi,
0087             struct ahash_request *req, struct page *data_page,
0088             unsigned long level0_ra_pages)
0089 {
0090     const struct merkle_tree_params *params = &vi->tree_params;
0091     const unsigned int hsize = params->digest_size;
0092     const pgoff_t index = data_page->index;
0093     int level;
0094     u8 _want_hash[FS_VERITY_MAX_DIGEST_SIZE];
0095     const u8 *want_hash;
0096     u8 real_hash[FS_VERITY_MAX_DIGEST_SIZE];
0097     struct page *hpages[FS_VERITY_MAX_LEVELS];
0098     unsigned int hoffsets[FS_VERITY_MAX_LEVELS];
0099     int err;
0100
0101     if (WARN_ON_ONCE(!PageLocked(data_page) || PageUptodate(data_page)))
0102         return false;
0103
0104     pr_debug_ratelimited("Verifying data page %lu...\n", index);
0105
0106     /*
0107      * Starting at the leaf level, ascend the tree saving hash pages along
0108      * the way until we find a verified hash page, indicated by PageChecked;
0109      * or until we reach the root.
0110      */
0111     for (level = 0; level < params->num_levels; level++) {
0112         pgoff_t hindex;
0113         unsigned int hoffset;
0114         struct page *hpage;
0115
0116         hash_at_level(params, index, level, &hindex, &hoffset);
0117
0118         pr_debug_ratelimited("Level %d: hindex=%lu, hoffset=%u\n",
0119                      level, hindex, hoffset);
0120
0121         hpage = inode->i_sb->s_vop->read_merkle_tree_page(inode, hindex,
0122                 level == 0 ? level0_ra_pages : 0);
0123         if (IS_ERR(hpage)) {
0124             err = PTR_ERR(hpage);
0125             fsverity_err(inode,
0126                      "Error %d reading Merkle tree page %lu",
0127                      err, hindex);
0128             goto out;
0129         }
0130
0131         if (PageChecked(hpage)) {
0132             extract_hash(hpage, hoffset, hsize, _want_hash);
0133             want_hash = _want_hash;
0134             put_page(hpage);
0135             pr_debug_ratelimited("Hash page already checked, want %s:%*phN\n",
0136                          params->hash_alg->name,
0137                          hsize, want_hash);
0138             goto descend;
0139         }
0140         pr_debug_ratelimited("Hash page not yet checked\n");
0141         hpages[level] = hpage;
0142         hoffsets[level] = hoffset;
0143     }
0144
0145     want_hash = vi->root_hash;
0146     pr_debug("Want root hash: %s:%*phN\n",
0147          params->hash_alg->name, hsize, want_hash);
0148 descend:
0149     /* Descend the tree verifying hash pages */
0150     for (; level > 0; level--) {
0151         struct page *hpage = hpages[level - 1];
0152         unsigned int hoffset = hoffsets[level - 1];
0153
0154         err = fsverity_hash_page(params, inode, req, hpage, real_hash);
0155         if (err)
0156             goto out;
0157         err = cmp_hashes(vi, want_hash, real_hash, index, level - 1);
0158         if (err)
0159             goto out;
0160         SetPageChecked(hpage);
0161         extract_hash(hpage, hoffset, hsize, _want_hash);
0162         want_hash = _want_hash;
0163         put_page(hpage);
0164         pr_debug("Verified hash page at level %d, now want %s:%*phN\n",
0165              level - 1, params->hash_alg->name, hsize, want_hash);
0166     }
0167
0168     /* Finally, verify the data page */
0169     err = fsverity_hash_page(params, inode, req, data_page, real_hash);
0170     if (err)
0171         goto out;
0172     err = cmp_hashes(vi, want_hash, real_hash, index, -1);
0173 out:
0174     for (; level > 0; level--)
0175         put_page(hpages[level - 1]);
0176
0177     return err == 0;
0178 }
0179
0180 /**
0181  * fsverity_verify_page() - verify a data page
0182  * @page: the page to verity
0183  *
0184  * Verify a page that has just been read from a verity file.  The page must be a
0185  * pagecache page that is still locked and not yet uptodate.
0186  *
0187  * Return: true if the page is valid, else false.
0188  */
0189 bool fsverity_verify_page(struct page *page)
0190 {
0191     struct inode *inode = page->mapping->host;
0192     const struct fsverity_info *vi = inode->i_verity_info;
0193     struct ahash_request *req;
0194     bool valid;
0195
0196     /* This allocation never fails, since it's mempool-backed. */
0197     req = fsverity_alloc_hash_request(vi->tree_params.hash_alg, GFP_NOFS);
0198
0199     valid = verify_page(inode, vi, req, page, 0);
0200
0201     fsverity_free_hash_request(vi->tree_params.hash_alg, req);
0202
0203     return valid;
0204 }
0205 EXPORT_SYMBOL_GPL(fsverity_verify_page);
0206
0207 #ifdef CONFIG_BLOCK
0208 /**
0209  * fsverity_verify_bio() - verify a 'read' bio that has just completed
0210  * @bio: the bio to verify
0211  *
0212  * Verify a set of pages that have just been read from a verity file.  The pages
0213  * must be pagecache pages that are still locked and not yet uptodate.  Pages
0214  * that fail verification are set to the Error state.  Verification is skipped
0215  * for pages already in the Error state, e.g. due to fscrypt decryption failure.
0216  *
0217  * This is a helper function for use by the ->readahead() method of filesystems
0218  * that issue bios to read data directly into the page cache.  Filesystems that
0219  * populate the page cache without issuing bios (e.g. non block-based
0220  * filesystems) must instead call fsverity_verify_page() directly on each page.
0221  * All filesystems must also call fsverity_verify_page() on holes.
0222  */
0223 void fsverity_verify_bio(struct bio *bio)
0224 {
0225     struct inode *inode = bio_first_page_all(bio)->mapping->host;
0226     const struct fsverity_info *vi = inode->i_verity_info;
0227     const struct merkle_tree_params *params = &vi->tree_params;
0228     struct ahash_request *req;
0229     struct bio_vec *bv;
0230     struct bvec_iter_all iter_all;
0231     unsigned long max_ra_pages = 0;
0232
0233     /* This allocation never fails, since it's mempool-backed. */
0234     req = fsverity_alloc_hash_request(params->hash_alg, GFP_NOFS);
0235
0236     if (bio->bi_opf & REQ_RAHEAD) {
0237         /*
0238          * If this bio is for data readahead, then we also do readahead
0239          * of the first (largest) level of the Merkle tree.  Namely,
0240          * when a Merkle tree page is read, we also try to piggy-back on
0241          * some additional pages -- up to 1/4 the number of data pages.
0242          *
0243          * This improves sequential read performance, as it greatly
0244          * reduces the number of I/O requests made to the Merkle tree.
0245          */
0246         bio_for_each_segment_all(bv, bio, iter_all)
0247             max_ra_pages++;
0248         max_ra_pages /= 4;
0249     }
0250
0251     bio_for_each_segment_all(bv, bio, iter_all) {
0252         struct page *page = bv->bv_page;
0253         unsigned long level0_index = page->index >> params->log_arity;
0254         unsigned long level0_ra_pages =
0255             min(max_ra_pages, params->level0_blocks - level0_index);
0256
0257         if (!PageError(page) &&
0258             !verify_page(inode, vi, req, page, level0_ra_pages))
0259             SetPageError(page);
0260     }
0261
0262     fsverity_free_hash_request(params->hash_alg, req);
0263 }
0264 EXPORT_SYMBOL_GPL(fsverity_verify_bio);
0265 #endif /* CONFIG_BLOCK */
0266
0267 /**
0268  * fsverity_enqueue_verify_work() - enqueue work on the fs-verity workqueue
0269  * @work: the work to enqueue
0270  *
0271  * Enqueue verification work for asynchronous processing.
0272  */
0273 void fsverity_enqueue_verify_work(struct work_struct *work)
0274 {
0275     queue_work(fsverity_read_workqueue, work);
0276 }
0277 EXPORT_SYMBOL_GPL(fsverity_enqueue_verify_work);
0278
0279 int __init fsverity_init_workqueue(void)
0280 {
0281     /*
0282      * Use an unbound workqueue to allow bios to be verified in parallel
0283      * even when they happen to complete on the same CPU.  This sacrifices
0284      * locality, but it's worthwhile since hashing is CPU-intensive.
0285      *
0286      * Also use a high-priority workqueue to prioritize verification work,
0287      * which blocks reads from completing, over regular application tasks.
0288      */
0289     fsverity_read_workqueue = alloc_workqueue("fsverity_read_queue",
0290                           WQ_UNBOUND | WQ_HIGHPRI,
0291                           num_online_cpus());
0292     if (!fsverity_read_workqueue)
0293         return -ENOMEM;
0294     return 0;
0295 }
0296
0297 void __init fsverity_exit_workqueue(void)
0298 {
0299     destroy_workqueue(fsverity_read_workqueue);
0300     fsverity_read_workqueue = NULL;
0301 }