fs/verity/verify.c

   1 // SPDX-License-Identifier: GPL-2.0
   2 /*
   3  * Data verification functions, i.e. hooks for ->readahead()
   4  *
   5  * Copyright 2019 Google LLC
   6  */
   7
   8 #include "fsverity_private.h"
   9
  10 #include <crypto/hash.h>
  11 #include <linux/bio.h>
  12 #include <linux/ratelimit.h>
  13
  14 static struct workqueue_struct *fsverity_read_workqueue;
  15
  16 /**
  17  * hash_at_level() - compute the location of the block's hash at the given level
  18  *
  19  * @params:     (in) the Merkle tree parameters
  20  * @dindex:     (in) the index of the data block being verified
  21  * @level:      (in) the level of hash we want (0 is leaf level)
  22  * @hindex:     (out) the index of the hash block containing the wanted hash
  23  * @hoffset:    (out) the byte offset to the wanted hash within the hash block
  24  */
  25 static void hash_at_level(const struct merkle_tree_params *params,
  26                           pgoff_t dindex, unsigned int level, pgoff_t *hindex,
  27                           unsigned int *hoffset)
  28 {
  29         pgoff_t position;
  30
  31         /* Offset of the hash within the level's region, in hashes */
  32         position = dindex >> (level * params->log_arity);
  33
  34         /* Index of the hash block in the tree overall */
  35         *hindex = params->level_start[level] + (position >> params->log_arity);
  36
  37         /* Offset of the wanted hash (in bytes) within the hash block */
  38         *hoffset = (position & ((1 << params->log_arity) - 1)) <<
  39                    (params->log_blocksize - params->log_arity);
  40 }
  41
  42 static inline int cmp_hashes(const struct fsverity_info *vi,
  43                              const u8 *want_hash, const u8 *real_hash,
  44                              pgoff_t index, int level)
  45 {
  46         const unsigned int hsize = vi->tree_params.digest_size;
  47
  48         if (memcmp(want_hash, real_hash, hsize) == 0)
  49                 return 0;
  50
  51         fsverity_err(vi->inode,
  52                      "FILE CORRUPTED! index=%lu, level=%d, want_hash=%s:%*phN, real_hash=%s:%*phN",
  53                      index, level,
  54                      vi->tree_params.hash_alg->name, hsize, want_hash,
  55                      vi->tree_params.hash_alg->name, hsize, real_hash);
  56         return -EBADMSG;
  57 }
  58
  59 /*
  60  * Verify a single data page against the file's Merkle tree.
  61  *
  62  * In principle, we need to verify the entire path to the root node.  However,
  63  * for efficiency the filesystem may cache the hash pages.  Therefore we need
  64  * only ascend the tree until an already-verified page is seen, as indicated by
  65  * the PageChecked bit being set; then verify the path to that page.
  66  *
  67  * This code currently only supports the case where the verity block size is
  68  * equal to PAGE_SIZE.  Doing otherwise would be possible but tricky, since we
  69  * wouldn't be able to use the PageChecked bit.
  70  *
  71  * Note that multiple processes may race to verify a hash page and mark it
  72  * Checked, but it doesn't matter; the result will be the same either way.
  73  *
  74  * Return: true if the page is valid, else false.
  75  */
  76 static bool verify_page(struct inode *inode, const struct fsverity_info *vi,
  77                         struct ahash_request *req, struct page *data_page,
  78                         unsigned long level0_ra_pages)
  79 {
  80         const struct merkle_tree_params *params = &vi->tree_params;
  81         const unsigned int hsize = params->digest_size;
  82         const pgoff_t index = data_page->index;
  83         int level;
  84         u8 _want_hash[FS_VERITY_MAX_DIGEST_SIZE];
  85         const u8 *want_hash;
  86         u8 real_hash[FS_VERITY_MAX_DIGEST_SIZE];
  87         struct page *hpages[FS_VERITY_MAX_LEVELS];
  88         unsigned int hoffsets[FS_VERITY_MAX_LEVELS];
  89         int err;
  90
  91         if (WARN_ON_ONCE(!PageLocked(data_page) || PageUptodate(data_page)))
  92                 return false;
  93
  94         pr_debug_ratelimited("Verifying data page %lu...\n", index);
  95
  96         /*
  97          * Starting at the leaf level, ascend the tree saving hash pages along
  98          * the way until we find a verified hash page, indicated by PageChecked;
  99          * or until we reach the root.
 100          */
 101         for (level = 0; level < params->num_levels; level++) {
 102                 pgoff_t hindex;
 103                 unsigned int hoffset;
 104                 struct page *hpage;
 105
 106                 hash_at_level(params, index, level, &hindex, &hoffset);
 107
 108                 pr_debug_ratelimited("Level %d: hindex=%lu, hoffset=%u\n",
 109                                      level, hindex, hoffset);
 110
 111                 hpage = inode->i_sb->s_vop->read_merkle_tree_page(inode, hindex,
 112                                 level == 0 ? level0_ra_pages : 0);
 113                 if (IS_ERR(hpage)) {
 114                         err = PTR_ERR(hpage);
 115                         fsverity_err(inode,
 116                                      "Error %d reading Merkle tree page %lu",
 117                                      err, hindex);
 118                         goto out;
 119                 }
 120
 121                 if (PageChecked(hpage)) {
 122                         memcpy_from_page(_want_hash, hpage, hoffset, hsize);
 123                         want_hash = _want_hash;
 124                         put_page(hpage);
 125                         pr_debug_ratelimited("Hash page already checked, want %s:%*phN\n",
 126                                              params->hash_alg->name,
 127                                              hsize, want_hash);
 128                         goto descend;
 129                 }
 130                 pr_debug_ratelimited("Hash page not yet checked\n");
 131                 hpages[level] = hpage;
 132                 hoffsets[level] = hoffset;
 133         }
 134
 135         want_hash = vi->root_hash;
 136         pr_debug("Want root hash: %s:%*phN\n",
 137                  params->hash_alg->name, hsize, want_hash);
 138 descend:
 139         /* Descend the tree verifying hash pages */
 140         for (; level > 0; level--) {
 141                 struct page *hpage = hpages[level - 1];
 142                 unsigned int hoffset = hoffsets[level - 1];
 143
 144                 err = fsverity_hash_page(params, inode, req, hpage, real_hash);
 145                 if (err)
 146                         goto out;
 147                 err = cmp_hashes(vi, want_hash, real_hash, index, level - 1);
 148                 if (err)
 149                         goto out;
 150                 SetPageChecked(hpage);
 151                 memcpy_from_page(_want_hash, hpage, hoffset, hsize);
 152                 want_hash = _want_hash;
 153                 put_page(hpage);
 154                 pr_debug("Verified hash page at level %d, now want %s:%*phN\n",
 155                          level - 1, params->hash_alg->name, hsize, want_hash);
 156         }
 157
 158         /* Finally, verify the data page */
 159         err = fsverity_hash_page(params, inode, req, data_page, real_hash);
 160         if (err)
 161                 goto out;
 162         err = cmp_hashes(vi, want_hash, real_hash, index, -1);
 163 out:
 164         for (; level > 0; level--)
 165                 put_page(hpages[level - 1]);
 166
 167         return err == 0;
 168 }
 169
 170 /**
 171  * fsverity_verify_page() - verify a data page
 172  * @page: the page to verity
 173  *
 174  * Verify a page that has just been read from a verity file.  The page must be a
 175  * pagecache page that is still locked and not yet uptodate.
 176  *
 177  * Return: true if the page is valid, else false.
 178  */
 179 bool fsverity_verify_page(struct page *page)
 180 {
 181         struct inode *inode = page->mapping->host;
 182         const struct fsverity_info *vi = inode->i_verity_info;
 183         struct ahash_request *req;
 184         bool valid;
 185
 186         /* This allocation never fails, since it's mempool-backed. */
 187         req = fsverity_alloc_hash_request(vi->tree_params.hash_alg, GFP_NOFS);
 188
 189         valid = verify_page(inode, vi, req, page, 0);
 190
 191         fsverity_free_hash_request(vi->tree_params.hash_alg, req);
 192
 193         return valid;
 194 }
 195 EXPORT_SYMBOL_GPL(fsverity_verify_page);
 196
 197 #ifdef CONFIG_BLOCK
 198 /**
 199  * fsverity_verify_bio() - verify a 'read' bio that has just completed
 200  * @bio: the bio to verify
 201  *
 202  * Verify a set of pages that have just been read from a verity file.  The pages
 203  * must be pagecache pages that are still locked and not yet uptodate.  Pages
 204  * that fail verification are set to the Error state.  Verification is skipped
 205  * for pages already in the Error state, e.g. due to fscrypt decryption failure.
 206  *
 207  * This is a helper function for use by the ->readahead() method of filesystems
 208  * that issue bios to read data directly into the page cache.  Filesystems that
 209  * populate the page cache without issuing bios (e.g. non block-based
 210  * filesystems) must instead call fsverity_verify_page() directly on each page.
 211  * All filesystems must also call fsverity_verify_page() on holes.
 212  */
 213 void fsverity_verify_bio(struct bio *bio)
 214 {
 215         struct inode *inode = bio_first_page_all(bio)->mapping->host;
 216         const struct fsverity_info *vi = inode->i_verity_info;
 217         const struct merkle_tree_params *params = &vi->tree_params;
 218         struct ahash_request *req;
 219         struct bio_vec *bv;
 220         struct bvec_iter_all iter_all;
 221         unsigned long max_ra_pages = 0;
 222
 223         /* This allocation never fails, since it's mempool-backed. */
 224         req = fsverity_alloc_hash_request(params->hash_alg, GFP_NOFS);
 225
 226         if (bio->bi_opf & REQ_RAHEAD) {
 227                 /*
 228                  * If this bio is for data readahead, then we also do readahead
 229                  * of the first (largest) level of the Merkle tree.  Namely,
 230                  * when a Merkle tree page is read, we also try to piggy-back on
 231                  * some additional pages -- up to 1/4 the number of data pages.
 232                  *
 233                  * This improves sequential read performance, as it greatly
 234                  * reduces the number of I/O requests made to the Merkle tree.
 235                  */
 236                 bio_for_each_segment_all(bv, bio, iter_all)
 237                         max_ra_pages++;
 238                 max_ra_pages /= 4;
 239         }
 240
 241         bio_for_each_segment_all(bv, bio, iter_all) {
 242                 struct page *page = bv->bv_page;
 243                 unsigned long level0_index = page->index >> params->log_arity;
 244                 unsigned long level0_ra_pages =
 245                         min(max_ra_pages, params->level0_blocks - level0_index);
 246
 247                 if (!PageError(page) &&
 248                     !verify_page(inode, vi, req, page, level0_ra_pages))
 249                         SetPageError(page);
 250         }
 251
 252         fsverity_free_hash_request(params->hash_alg, req);
 253 }
 254 EXPORT_SYMBOL_GPL(fsverity_verify_bio);
 255 #endif /* CONFIG_BLOCK */
 256
 257 /**
 258  * fsverity_enqueue_verify_work() - enqueue work on the fs-verity workqueue
 259  * @work: the work to enqueue
 260  *
 261  * Enqueue verification work for asynchronous processing.
 262  */
 263 void fsverity_enqueue_verify_work(struct work_struct *work)
 264 {
 265         queue_work(fsverity_read_workqueue, work);
 266 }
 267 EXPORT_SYMBOL_GPL(fsverity_enqueue_verify_work);
 268
 269 int __init fsverity_init_workqueue(void)
 270 {
 271         /*
 272          * Use a high-priority workqueue to prioritize verification work, which
 273          * blocks reads from completing, over regular application tasks.
 274          *
 275          * For performance reasons, don't use an unbound workqueue.  Using an
 276          * unbound workqueue for crypto operations causes excessive scheduler
 277          * latency on ARM64.
 278          */
 279         fsverity_read_workqueue = alloc_workqueue("fsverity_read_queue",
 280                                                   WQ_HIGHPRI,
 281                                                   num_online_cpus());
 282         if (!fsverity_read_workqueue)
 283                 return -ENOMEM;
 284         return 0;
 285 }
 286
 287 void __init fsverity_exit_workqueue(void)
 288 {
 289         destroy_workqueue(fsverity_read_workqueue);
 290         fsverity_read_workqueue = NULL;
 291 }