verify.c 9.6 KB

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