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