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