]>
Commit | Line | Data |
---|---|---|
8a1d0f9c EB |
1 | // SPDX-License-Identifier: GPL-2.0 |
2 | /* | |
3 | * fs/verity/verify.c: 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, | |
fd39073d EB |
87 | struct ahash_request *req, struct page *data_page, |
88 | unsigned long level0_ra_pages) | |
8a1d0f9c EB |
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 | ||
fd39073d EB |
121 | hpage = inode->i_sb->s_vop->read_merkle_tree_page(inode, hindex, |
122 | level == 0 ? level0_ra_pages : 0); | |
8a1d0f9c EB |
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 | * | |
183 | * Verify a page that has just been read from a verity file. The page must be a | |
184 | * pagecache page that is still locked and not yet uptodate. | |
185 | * | |
186 | * Return: true if the page is valid, else false. | |
187 | */ | |
188 | bool fsverity_verify_page(struct page *page) | |
189 | { | |
190 | struct inode *inode = page->mapping->host; | |
191 | const struct fsverity_info *vi = inode->i_verity_info; | |
192 | struct ahash_request *req; | |
193 | bool valid; | |
194 | ||
439bea10 EB |
195 | /* This allocation never fails, since it's mempool-backed. */ |
196 | req = fsverity_alloc_hash_request(vi->tree_params.hash_alg, GFP_NOFS); | |
8a1d0f9c | 197 | |
fd39073d | 198 | valid = verify_page(inode, vi, req, page, 0); |
8a1d0f9c | 199 | |
439bea10 | 200 | fsverity_free_hash_request(vi->tree_params.hash_alg, req); |
8a1d0f9c EB |
201 | |
202 | return valid; | |
203 | } | |
204 | EXPORT_SYMBOL_GPL(fsverity_verify_page); | |
205 | ||
206 | #ifdef CONFIG_BLOCK | |
207 | /** | |
208 | * fsverity_verify_bio() - verify a 'read' bio that has just completed | |
209 | * | |
210 | * Verify a set of pages that have just been read from a verity file. The pages | |
211 | * must be pagecache pages that are still locked and not yet uptodate. Pages | |
212 | * that fail verification are set to the Error state. Verification is skipped | |
213 | * for pages already in the Error state, e.g. due to fscrypt decryption failure. | |
214 | * | |
215 | * This is a helper function for use by the ->readpages() method of filesystems | |
216 | * that issue bios to read data directly into the page cache. Filesystems that | |
217 | * populate the page cache without issuing bios (e.g. non block-based | |
218 | * filesystems) must instead call fsverity_verify_page() directly on each page. | |
219 | * All filesystems must also call fsverity_verify_page() on holes. | |
220 | */ | |
221 | void fsverity_verify_bio(struct bio *bio) | |
222 | { | |
223 | struct inode *inode = bio_first_page_all(bio)->mapping->host; | |
224 | const struct fsverity_info *vi = inode->i_verity_info; | |
fd39073d | 225 | const struct merkle_tree_params *params = &vi->tree_params; |
8a1d0f9c EB |
226 | struct ahash_request *req; |
227 | struct bio_vec *bv; | |
228 | struct bvec_iter_all iter_all; | |
fd39073d | 229 | unsigned long max_ra_pages = 0; |
8a1d0f9c | 230 | |
439bea10 EB |
231 | /* This allocation never fails, since it's mempool-backed. */ |
232 | req = fsverity_alloc_hash_request(params->hash_alg, GFP_NOFS); | |
8a1d0f9c | 233 | |
fd39073d EB |
234 | if (bio->bi_opf & REQ_RAHEAD) { |
235 | /* | |
236 | * If this bio is for data readahead, then we also do readahead | |
237 | * of the first (largest) level of the Merkle tree. Namely, | |
238 | * when a Merkle tree page is read, we also try to piggy-back on | |
239 | * some additional pages -- up to 1/4 the number of data pages. | |
240 | * | |
241 | * This improves sequential read performance, as it greatly | |
242 | * reduces the number of I/O requests made to the Merkle tree. | |
243 | */ | |
244 | bio_for_each_segment_all(bv, bio, iter_all) | |
245 | max_ra_pages++; | |
246 | max_ra_pages /= 4; | |
247 | } | |
248 | ||
8a1d0f9c EB |
249 | bio_for_each_segment_all(bv, bio, iter_all) { |
250 | struct page *page = bv->bv_page; | |
fd39073d EB |
251 | unsigned long level0_index = page->index >> params->log_arity; |
252 | unsigned long level0_ra_pages = | |
253 | min(max_ra_pages, params->level0_blocks - level0_index); | |
8a1d0f9c | 254 | |
fd39073d EB |
255 | if (!PageError(page) && |
256 | !verify_page(inode, vi, req, page, level0_ra_pages)) | |
8a1d0f9c EB |
257 | SetPageError(page); |
258 | } | |
259 | ||
439bea10 | 260 | fsverity_free_hash_request(params->hash_alg, req); |
8a1d0f9c EB |
261 | } |
262 | EXPORT_SYMBOL_GPL(fsverity_verify_bio); | |
263 | #endif /* CONFIG_BLOCK */ | |
264 | ||
265 | /** | |
266 | * fsverity_enqueue_verify_work() - enqueue work on the fs-verity workqueue | |
267 | * | |
268 | * Enqueue verification work for asynchronous processing. | |
269 | */ | |
270 | void fsverity_enqueue_verify_work(struct work_struct *work) | |
271 | { | |
272 | queue_work(fsverity_read_workqueue, work); | |
273 | } | |
274 | EXPORT_SYMBOL_GPL(fsverity_enqueue_verify_work); | |
275 | ||
276 | int __init fsverity_init_workqueue(void) | |
277 | { | |
278 | /* | |
279 | * Use an unbound workqueue to allow bios to be verified in parallel | |
280 | * even when they happen to complete on the same CPU. This sacrifices | |
281 | * locality, but it's worthwhile since hashing is CPU-intensive. | |
282 | * | |
283 | * Also use a high-priority workqueue to prioritize verification work, | |
284 | * which blocks reads from completing, over regular application tasks. | |
285 | */ | |
286 | fsverity_read_workqueue = alloc_workqueue("fsverity_read_queue", | |
287 | WQ_UNBOUND | WQ_HIGHPRI, | |
288 | num_online_cpus()); | |
289 | if (!fsverity_read_workqueue) | |
290 | return -ENOMEM; | |
291 | return 0; | |
292 | } | |
432434c9 EB |
293 | |
294 | void __init fsverity_exit_workqueue(void) | |
295 | { | |
296 | destroy_workqueue(fsverity_read_workqueue); | |
297 | fsverity_read_workqueue = NULL; | |
298 | } |