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
kmsan_internal_task_create(struct task_struct * task)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
kmsan_internal_poison_memory(void * address,size_t size,gfp_t flags,unsigned int poison_flags)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
kmsan_internal_unpoison_memory(void * address,size_t size,bool checked)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
kmsan_save_stack_with_flags(gfp_t flags,unsigned int extra)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 depot_stack_handle_t handle;
73
74 nr_entries = stack_trace_save(entries, KMSAN_STACK_DEPTH, 0);
75
76 /* Don't sleep. */
77 flags &= ~(__GFP_DIRECT_RECLAIM | __GFP_KSWAPD_RECLAIM);
78
79 handle = __stack_depot_save(entries, nr_entries, flags, true);
80 return stack_depot_set_extra_bits(handle, extra);
81 }
82
83 /* Copy the metadata following the memmove() behavior. */
kmsan_internal_memmove_metadata(void * dst,void * src,size_t n)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
kmsan_internal_chain_origin(depot_stack_handle_t id)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;
220 depot_stack_handle_t handle;
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;
248 entries[1] = kmsan_save_stack_with_flags(__GFP_HIGH, 0);
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);
256 handle = __stack_depot_save(entries, ARRAY_SIZE(entries), __GFP_HIGH,
257 true);
258 return stack_depot_set_extra_bits(handle, extra_bits);
259 }
260
kmsan_internal_set_shadow_origin(void * addr,size_t size,int b,u32 origin,bool checked)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
kmsan_vmalloc_to_page_or_null(void * vaddr)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
kmsan_internal_check_memory(void * addr,size_t size,const void * user_addr,int reason)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
kmsan_metadata_is_contiguous(void * addr,size_t size)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 }
455
