Commit | Line | Data |
---|---|---|
f80be457 AP |
1 | // SPDX-License-Identifier: GPL-2.0 |
2 | /* | |
3 | * KMSAN runtime library. | |
4 | * | |
5 | * Copyright (C) 2017-2022 Google LLC | |
6 | * Author: Alexander Potapenko <glider@google.com> | |
7 | * | |
8 | */ | |
9 | ||
10 | #include <asm/page.h> | |
11 | #include <linux/compiler.h> | |
12 | #include <linux/export.h> | |
13 | #include <linux/highmem.h> | |
14 | #include <linux/interrupt.h> | |
15 | #include <linux/kernel.h> | |
16 | #include <linux/kmsan_types.h> | |
17 | #include <linux/memory.h> | |
18 | #include <linux/mm.h> | |
19 | #include <linux/mm_types.h> | |
20 | #include <linux/mmzone.h> | |
21 | #include <linux/percpu-defs.h> | |
22 | #include <linux/preempt.h> | |
23 | #include <linux/slab.h> | |
24 | #include <linux/stackdepot.h> | |
25 | #include <linux/stacktrace.h> | |
26 | #include <linux/types.h> | |
27 | #include <linux/vmalloc.h> | |
28 | ||
29 | #include "../slab.h" | |
30 | #include "kmsan.h" | |
31 | ||
32 | bool kmsan_enabled __read_mostly; | |
33 | ||
34 | /* | |
35 | * Per-CPU KMSAN context to be used in interrupts, where current->kmsan is | |
36 | * unavaliable. | |
37 | */ | |
38 | DEFINE_PER_CPU(struct kmsan_ctx, kmsan_percpu_ctx); | |
39 | ||
40 | void kmsan_internal_poison_memory(void *address, size_t size, gfp_t flags, | |
41 | unsigned int poison_flags) | |
42 | { | |
43 | u32 extra_bits = | |
44 | kmsan_extra_bits(/*depth*/ 0, poison_flags & KMSAN_POISON_FREE); | |
45 | bool checked = poison_flags & KMSAN_POISON_CHECK; | |
46 | depot_stack_handle_t handle; | |
47 | ||
48 | handle = kmsan_save_stack_with_flags(flags, extra_bits); | |
49 | kmsan_internal_set_shadow_origin(address, size, -1, handle, checked); | |
50 | } | |
51 | ||
52 | void kmsan_internal_unpoison_memory(void *address, size_t size, bool checked) | |
53 | { | |
54 | kmsan_internal_set_shadow_origin(address, size, 0, 0, checked); | |
55 | } | |
56 | ||
57 | depot_stack_handle_t kmsan_save_stack_with_flags(gfp_t flags, | |
58 | unsigned int extra) | |
59 | { | |
60 | unsigned long entries[KMSAN_STACK_DEPTH]; | |
61 | unsigned int nr_entries; | |
62 | ||
63 | nr_entries = stack_trace_save(entries, KMSAN_STACK_DEPTH, 0); | |
64 | ||
65 | /* Don't sleep (see might_sleep_if() in __alloc_pages_nodemask()). */ | |
66 | flags &= ~__GFP_DIRECT_RECLAIM; | |
67 | ||
68 | return __stack_depot_save(entries, nr_entries, extra, flags, true); | |
69 | } | |
70 | ||
71 | /* Copy the metadata following the memmove() behavior. */ | |
72 | void kmsan_internal_memmove_metadata(void *dst, void *src, size_t n) | |
73 | { | |
74 | depot_stack_handle_t old_origin = 0, new_origin = 0; | |
75 | int src_slots, dst_slots, i, iter, step, skip_bits; | |
76 | depot_stack_handle_t *origin_src, *origin_dst; | |
77 | void *shadow_src, *shadow_dst; | |
78 | u32 *align_shadow_src, shadow; | |
79 | bool backwards; | |
80 | ||
81 | shadow_dst = kmsan_get_metadata(dst, KMSAN_META_SHADOW); | |
82 | if (!shadow_dst) | |
83 | return; | |
84 | KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(dst, n)); | |
85 | ||
86 | shadow_src = kmsan_get_metadata(src, KMSAN_META_SHADOW); | |
87 | if (!shadow_src) { | |
88 | /* | |
89 | * @src is untracked: zero out destination shadow, ignore the | |
90 | * origins, we're done. | |
91 | */ | |
92 | __memset(shadow_dst, 0, n); | |
93 | return; | |
94 | } | |
95 | KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(src, n)); | |
96 | ||
97 | __memmove(shadow_dst, shadow_src, n); | |
98 | ||
99 | origin_dst = kmsan_get_metadata(dst, KMSAN_META_ORIGIN); | |
100 | origin_src = kmsan_get_metadata(src, KMSAN_META_ORIGIN); | |
101 | KMSAN_WARN_ON(!origin_dst || !origin_src); | |
102 | src_slots = (ALIGN((u64)src + n, KMSAN_ORIGIN_SIZE) - | |
103 | ALIGN_DOWN((u64)src, KMSAN_ORIGIN_SIZE)) / | |
104 | KMSAN_ORIGIN_SIZE; | |
105 | dst_slots = (ALIGN((u64)dst + n, KMSAN_ORIGIN_SIZE) - | |
106 | ALIGN_DOWN((u64)dst, KMSAN_ORIGIN_SIZE)) / | |
107 | KMSAN_ORIGIN_SIZE; | |
108 | KMSAN_WARN_ON((src_slots < 1) || (dst_slots < 1)); | |
109 | KMSAN_WARN_ON((src_slots - dst_slots > 1) || | |
110 | (dst_slots - src_slots < -1)); | |
111 | ||
112 | backwards = dst > src; | |
113 | i = backwards ? min(src_slots, dst_slots) - 1 : 0; | |
114 | iter = backwards ? -1 : 1; | |
115 | ||
116 | align_shadow_src = | |
117 | (u32 *)ALIGN_DOWN((u64)shadow_src, KMSAN_ORIGIN_SIZE); | |
118 | for (step = 0; step < min(src_slots, dst_slots); step++, i += iter) { | |
119 | KMSAN_WARN_ON(i < 0); | |
120 | shadow = align_shadow_src[i]; | |
121 | if (i == 0) { | |
122 | /* | |
123 | * If @src isn't aligned on KMSAN_ORIGIN_SIZE, don't | |
124 | * look at the first @src % KMSAN_ORIGIN_SIZE bytes | |
125 | * of the first shadow slot. | |
126 | */ | |
127 | skip_bits = ((u64)src % KMSAN_ORIGIN_SIZE) * 8; | |
128 | shadow = (shadow >> skip_bits) << skip_bits; | |
129 | } | |
130 | if (i == src_slots - 1) { | |
131 | /* | |
132 | * If @src + n isn't aligned on | |
133 | * KMSAN_ORIGIN_SIZE, don't look at the last | |
134 | * (@src + n) % KMSAN_ORIGIN_SIZE bytes of the | |
135 | * last shadow slot. | |
136 | */ | |
137 | skip_bits = (((u64)src + n) % KMSAN_ORIGIN_SIZE) * 8; | |
138 | shadow = (shadow << skip_bits) >> skip_bits; | |
139 | } | |
140 | /* | |
141 | * Overwrite the origin only if the corresponding | |
142 | * shadow is nonempty. | |
143 | */ | |
144 | if (origin_src[i] && (origin_src[i] != old_origin) && shadow) { | |
145 | old_origin = origin_src[i]; | |
146 | new_origin = kmsan_internal_chain_origin(old_origin); | |
147 | /* | |
148 | * kmsan_internal_chain_origin() may return | |
149 | * NULL, but we don't want to lose the previous | |
150 | * origin value. | |
151 | */ | |
152 | if (!new_origin) | |
153 | new_origin = old_origin; | |
154 | } | |
155 | if (shadow) | |
156 | origin_dst[i] = new_origin; | |
157 | else | |
158 | origin_dst[i] = 0; | |
159 | } | |
160 | /* | |
161 | * If dst_slots is greater than src_slots (i.e. | |
162 | * dst_slots == src_slots + 1), there is an extra origin slot at the | |
163 | * beginning or end of the destination buffer, for which we take the | |
164 | * origin from the previous slot. | |
165 | * This is only done if the part of the source shadow corresponding to | |
166 | * slot is non-zero. | |
167 | * | |
168 | * E.g. if we copy 8 aligned bytes that are marked as uninitialized | |
169 | * and have origins o111 and o222, to an unaligned buffer with offset 1, | |
170 | * these two origins are copied to three origin slots, so one of then | |
171 | * needs to be duplicated, depending on the copy direction (@backwards) | |
172 | * | |
173 | * src shadow: |uuuu|uuuu|....| | |
174 | * src origin: |o111|o222|....| | |
175 | * | |
176 | * backwards = 0: | |
177 | * dst shadow: |.uuu|uuuu|u...| | |
178 | * dst origin: |....|o111|o222| - fill the empty slot with o111 | |
179 | * backwards = 1: | |
180 | * dst shadow: |.uuu|uuuu|u...| | |
181 | * dst origin: |o111|o222|....| - fill the empty slot with o222 | |
182 | */ | |
183 | if (src_slots < dst_slots) { | |
184 | if (backwards) { | |
185 | shadow = align_shadow_src[src_slots - 1]; | |
186 | skip_bits = (((u64)dst + n) % KMSAN_ORIGIN_SIZE) * 8; | |
187 | shadow = (shadow << skip_bits) >> skip_bits; | |
188 | if (shadow) | |
189 | /* src_slots > 0, therefore dst_slots is at least 2 */ | |
190 | origin_dst[dst_slots - 1] = | |
191 | origin_dst[dst_slots - 2]; | |
192 | } else { | |
193 | shadow = align_shadow_src[0]; | |
194 | skip_bits = ((u64)dst % KMSAN_ORIGIN_SIZE) * 8; | |
195 | shadow = (shadow >> skip_bits) << skip_bits; | |
196 | if (shadow) | |
197 | origin_dst[0] = origin_dst[1]; | |
198 | } | |
199 | } | |
200 | } | |
201 | ||
202 | depot_stack_handle_t kmsan_internal_chain_origin(depot_stack_handle_t id) | |
203 | { | |
204 | unsigned long entries[3]; | |
205 | u32 extra_bits; | |
206 | int depth; | |
207 | bool uaf; | |
208 | ||
209 | if (!id) | |
210 | return id; | |
211 | /* | |
212 | * Make sure we have enough spare bits in @id to hold the UAF bit and | |
213 | * the chain depth. | |
214 | */ | |
215 | BUILD_BUG_ON( | |
216 | (1 << STACK_DEPOT_EXTRA_BITS) <= (KMSAN_MAX_ORIGIN_DEPTH << 1)); | |
217 | ||
218 | extra_bits = stack_depot_get_extra_bits(id); | |
219 | depth = kmsan_depth_from_eb(extra_bits); | |
220 | uaf = kmsan_uaf_from_eb(extra_bits); | |
221 | ||
222 | /* | |
223 | * Stop chaining origins once the depth reached KMSAN_MAX_ORIGIN_DEPTH. | |
224 | * This mostly happens in the case structures with uninitialized padding | |
225 | * are copied around many times. Origin chains for such structures are | |
226 | * usually periodic, and it does not make sense to fully store them. | |
227 | */ | |
228 | if (depth == KMSAN_MAX_ORIGIN_DEPTH) | |
229 | return id; | |
230 | ||
231 | depth++; | |
232 | extra_bits = kmsan_extra_bits(depth, uaf); | |
233 | ||
234 | entries[0] = KMSAN_CHAIN_MAGIC_ORIGIN; | |
235 | entries[1] = kmsan_save_stack_with_flags(GFP_ATOMIC, 0); | |
236 | entries[2] = id; | |
237 | /* | |
238 | * @entries is a local var in non-instrumented code, so KMSAN does not | |
239 | * know it is initialized. Explicitly unpoison it to avoid false | |
240 | * positives when __stack_depot_save() passes it to instrumented code. | |
241 | */ | |
242 | kmsan_internal_unpoison_memory(entries, sizeof(entries), false); | |
243 | return __stack_depot_save(entries, ARRAY_SIZE(entries), extra_bits, | |
244 | GFP_ATOMIC, true); | |
245 | } | |
246 | ||
247 | void kmsan_internal_set_shadow_origin(void *addr, size_t size, int b, | |
248 | u32 origin, bool checked) | |
249 | { | |
250 | u64 address = (u64)addr; | |
251 | void *shadow_start; | |
252 | u32 *origin_start; | |
253 | size_t pad = 0; | |
254 | ||
255 | KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(addr, size)); | |
256 | shadow_start = kmsan_get_metadata(addr, KMSAN_META_SHADOW); | |
257 | if (!shadow_start) { | |
258 | /* | |
259 | * kmsan_metadata_is_contiguous() is true, so either all shadow | |
260 | * and origin pages are NULL, or all are non-NULL. | |
261 | */ | |
262 | if (checked) { | |
263 | pr_err("%s: not memsetting %ld bytes starting at %px, because the shadow is NULL\n", | |
264 | __func__, size, addr); | |
265 | KMSAN_WARN_ON(true); | |
266 | } | |
267 | return; | |
268 | } | |
269 | __memset(shadow_start, b, size); | |
270 | ||
271 | if (!IS_ALIGNED(address, KMSAN_ORIGIN_SIZE)) { | |
272 | pad = address % KMSAN_ORIGIN_SIZE; | |
273 | address -= pad; | |
274 | size += pad; | |
275 | } | |
276 | size = ALIGN(size, KMSAN_ORIGIN_SIZE); | |
277 | origin_start = | |
278 | (u32 *)kmsan_get_metadata((void *)address, KMSAN_META_ORIGIN); | |
279 | ||
280 | for (int i = 0; i < size / KMSAN_ORIGIN_SIZE; i++) | |
281 | origin_start[i] = origin; | |
282 | } | |
283 | ||
284 | struct page *kmsan_vmalloc_to_page_or_null(void *vaddr) | |
285 | { | |
286 | struct page *page; | |
287 | ||
288 | if (!kmsan_internal_is_vmalloc_addr(vaddr) && | |
289 | !kmsan_internal_is_module_addr(vaddr)) | |
290 | return NULL; | |
291 | page = vmalloc_to_page(vaddr); | |
292 | if (pfn_valid(page_to_pfn(page))) | |
293 | return page; | |
294 | else | |
295 | return NULL; | |
296 | } | |
297 | ||
298 | void kmsan_internal_check_memory(void *addr, size_t size, const void *user_addr, | |
299 | int reason) | |
300 | { | |
301 | depot_stack_handle_t cur_origin = 0, new_origin = 0; | |
302 | unsigned long addr64 = (unsigned long)addr; | |
303 | depot_stack_handle_t *origin = NULL; | |
304 | unsigned char *shadow = NULL; | |
305 | int cur_off_start = -1; | |
306 | int chunk_size; | |
307 | size_t pos = 0; | |
308 | ||
309 | if (!size) | |
310 | return; | |
311 | KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(addr, size)); | |
312 | while (pos < size) { | |
313 | chunk_size = min(size - pos, | |
314 | PAGE_SIZE - ((addr64 + pos) % PAGE_SIZE)); | |
315 | shadow = kmsan_get_metadata((void *)(addr64 + pos), | |
316 | KMSAN_META_SHADOW); | |
317 | if (!shadow) { | |
318 | /* | |
319 | * This page is untracked. If there were uninitialized | |
320 | * bytes before, report them. | |
321 | */ | |
322 | if (cur_origin) { | |
323 | kmsan_enter_runtime(); | |
324 | kmsan_report(cur_origin, addr, size, | |
325 | cur_off_start, pos - 1, user_addr, | |
326 | reason); | |
327 | kmsan_leave_runtime(); | |
328 | } | |
329 | cur_origin = 0; | |
330 | cur_off_start = -1; | |
331 | pos += chunk_size; | |
332 | continue; | |
333 | } | |
334 | for (int i = 0; i < chunk_size; i++) { | |
335 | if (!shadow[i]) { | |
336 | /* | |
337 | * This byte is unpoisoned. If there were | |
338 | * poisoned bytes before, report them. | |
339 | */ | |
340 | if (cur_origin) { | |
341 | kmsan_enter_runtime(); | |
342 | kmsan_report(cur_origin, addr, size, | |
343 | cur_off_start, pos + i - 1, | |
344 | user_addr, reason); | |
345 | kmsan_leave_runtime(); | |
346 | } | |
347 | cur_origin = 0; | |
348 | cur_off_start = -1; | |
349 | continue; | |
350 | } | |
351 | origin = kmsan_get_metadata((void *)(addr64 + pos + i), | |
352 | KMSAN_META_ORIGIN); | |
353 | KMSAN_WARN_ON(!origin); | |
354 | new_origin = *origin; | |
355 | /* | |
356 | * Encountered new origin - report the previous | |
357 | * uninitialized range. | |
358 | */ | |
359 | if (cur_origin != new_origin) { | |
360 | if (cur_origin) { | |
361 | kmsan_enter_runtime(); | |
362 | kmsan_report(cur_origin, addr, size, | |
363 | cur_off_start, pos + i - 1, | |
364 | user_addr, reason); | |
365 | kmsan_leave_runtime(); | |
366 | } | |
367 | cur_origin = new_origin; | |
368 | cur_off_start = pos + i; | |
369 | } | |
370 | } | |
371 | pos += chunk_size; | |
372 | } | |
373 | KMSAN_WARN_ON(pos != size); | |
374 | if (cur_origin) { | |
375 | kmsan_enter_runtime(); | |
376 | kmsan_report(cur_origin, addr, size, cur_off_start, pos - 1, | |
377 | user_addr, reason); | |
378 | kmsan_leave_runtime(); | |
379 | } | |
380 | } | |
381 | ||
382 | bool kmsan_metadata_is_contiguous(void *addr, size_t size) | |
383 | { | |
384 | char *cur_shadow = NULL, *next_shadow = NULL, *cur_origin = NULL, | |
385 | *next_origin = NULL; | |
386 | u64 cur_addr = (u64)addr, next_addr = cur_addr + PAGE_SIZE; | |
387 | depot_stack_handle_t *origin_p; | |
388 | bool all_untracked = false; | |
389 | ||
390 | if (!size) | |
391 | return true; | |
392 | ||
393 | /* The whole range belongs to the same page. */ | |
394 | if (ALIGN_DOWN(cur_addr + size - 1, PAGE_SIZE) == | |
395 | ALIGN_DOWN(cur_addr, PAGE_SIZE)) | |
396 | return true; | |
397 | ||
398 | cur_shadow = kmsan_get_metadata((void *)cur_addr, /*is_origin*/ false); | |
399 | if (!cur_shadow) | |
400 | all_untracked = true; | |
401 | cur_origin = kmsan_get_metadata((void *)cur_addr, /*is_origin*/ true); | |
402 | if (all_untracked && cur_origin) | |
403 | goto report; | |
404 | ||
405 | for (; next_addr < (u64)addr + size; | |
406 | cur_addr = next_addr, cur_shadow = next_shadow, | |
407 | cur_origin = next_origin, next_addr += PAGE_SIZE) { | |
408 | next_shadow = kmsan_get_metadata((void *)next_addr, false); | |
409 | next_origin = kmsan_get_metadata((void *)next_addr, true); | |
410 | if (all_untracked) { | |
411 | if (next_shadow || next_origin) | |
412 | goto report; | |
413 | if (!next_shadow && !next_origin) | |
414 | continue; | |
415 | } | |
416 | if (((u64)cur_shadow == ((u64)next_shadow - PAGE_SIZE)) && | |
417 | ((u64)cur_origin == ((u64)next_origin - PAGE_SIZE))) | |
418 | continue; | |
419 | goto report; | |
420 | } | |
421 | return true; | |
422 | ||
423 | report: | |
424 | pr_err("%s: attempting to access two shadow page ranges.\n", __func__); | |
425 | pr_err("Access of size %ld at %px.\n", size, addr); | |
426 | pr_err("Addresses belonging to different ranges: %px and %px\n", | |
427 | (void *)cur_addr, (void *)next_addr); | |
428 | pr_err("page[0].shadow: %px, page[1].shadow: %px\n", cur_shadow, | |
429 | next_shadow); | |
430 | pr_err("page[0].origin: %px, page[1].origin: %px\n", cur_origin, | |
431 | next_origin); | |
432 | origin_p = kmsan_get_metadata(addr, KMSAN_META_ORIGIN); | |
433 | if (origin_p) { | |
434 | pr_err("Origin: %08x\n", *origin_p); | |
435 | kmsan_print_origin(*origin_p); | |
436 | } else { | |
437 | pr_err("Origin: unavailable\n"); | |
438 | } | |
439 | return false; | |
440 | } |