~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

TOMOYO Linux Cross Reference
Linux/fs/verity/verify.c

Version: ~ [ linux-6.4-rc3 ] ~ [ linux-6.3.4 ] ~ [ linux-6.2.16 ] ~ [ linux-6.1.30 ] ~ [ linux-6.0.19 ] ~ [ linux-5.19.17 ] ~ [ linux-5.18.19 ] ~ [ linux-5.17.15 ] ~ [ linux-5.16.20 ] ~ [ linux-5.15.113 ] ~ [ linux-5.14.21 ] ~ [ linux-5.13.19 ] ~ [ linux-5.12.19 ] ~ [ linux-5.11.22 ] ~ [ linux-5.10.180 ] ~ [ linux-5.9.16 ] ~ [ linux-5.8.18 ] ~ [ linux-5.7.19 ] ~ [ linux-5.6.19 ] ~ [ linux-5.5.19 ] ~ [ linux-5.4.243 ] ~ [ linux-5.3.18 ] ~ [ linux-5.2.21 ] ~ [ linux-5.1.21 ] ~ [ linux-5.0.21 ] ~ [ linux-4.20.17 ] ~ [ linux-4.19.283 ] ~ [ linux-4.18.20 ] ~ [ linux-4.17.19 ] ~ [ linux-4.16.18 ] ~ [ linux-4.15.18 ] ~ [ linux-4.14.315 ] ~ [ linux-4.13.16 ] ~ [ linux-4.12.14 ] ~ [ linux-4.11.12 ] ~ [ linux-4.10.17 ] ~ [ linux-4.9.337 ] ~ [ linux-4.4.302 ] ~ [ linux-3.10.108 ] ~ [ linux-2.6.32.71 ] ~ [ linux-2.6.0 ] ~ [ linux-2.4.37.11 ] ~ [ unix-v6-master ] ~ [ ccs-tools-1.8.9 ] ~ [ policy-sample ] ~
Architecture: ~ [ i386 ] ~ [ alpha ] ~ [ m68k ] ~ [ mips ] ~ [ ppc ] ~ [ sparc ] ~ [ sparc64 ] ~

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

~ [ source navigation ] ~ [ diff markup ] ~ [ identifier search ] ~

kernel.org | git.kernel.org | LWN.net | Project Home | Wiki (Japanese) | Wiki (English) | SVN repository | Mail admin

Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.

osdn.jp