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
32bool kmsan_enabled __read_mostly;
33
34/*
35 * Per-CPU KMSAN context to be used in interrupts, where current->kmsan is
36 * unavaliable.
37 */
38DEFINE_PER_CPU(struct kmsan_ctx, kmsan_percpu_ctx);
39
40void 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(s: ctx, c: 0, n: sizeof(*ctx));
46 kmsan_internal_unpoison_memory(address: info, size: sizeof(*info), checked: false);
47}
48
49void kmsan_internal_poison_memory(void *address, size_t size, gfp_t flags,
50 unsigned int poison_flags)
51{
52 u32 extra_bits =
53 kmsan_extra_bits(/*depth*/ 0, uaf: poison_flags & KMSAN_POISON_FREE);
54 bool checked = poison_flags & KMSAN_POISON_CHECK;
55 depot_stack_handle_t handle;
56
57 handle = kmsan_save_stack_with_flags(flags, extra_bits);
58 kmsan_internal_set_shadow_origin(address, size, b: -1, origin: handle, checked);
59}
60
61void kmsan_internal_unpoison_memory(void *address, size_t size, bool checked)
62{
63 kmsan_internal_set_shadow_origin(address, size, b: 0, origin: 0, checked);
64}
65
66depot_stack_handle_t kmsan_save_stack_with_flags(gfp_t flags,
67 unsigned int extra)
68{
69 unsigned long entries[KMSAN_STACK_DEPTH];
70 unsigned int nr_entries;
71 depot_stack_handle_t handle;
72
73 nr_entries = stack_trace_save(store: entries, KMSAN_STACK_DEPTH, skipnr: 0);
74
75 /* Don't sleep. */
76 flags &= ~(__GFP_DIRECT_RECLAIM | __GFP_KSWAPD_RECLAIM);
77
78 handle = stack_depot_save(entries, nr_entries, alloc_flags: flags);
79 return stack_depot_set_extra_bits(handle, extra_bits: extra);
80}
81
82/* Copy the metadata following the memmove() behavior. */
83void kmsan_internal_memmove_metadata(void *dst, void *src, size_t n)
84{
85 depot_stack_handle_t prev_old_origin = 0, prev_new_origin = 0;
86 int i, iter, step, src_off, dst_off, oiter_src, oiter_dst;
87 depot_stack_handle_t old_origin = 0, new_origin = 0;
88 depot_stack_handle_t *origin_src, *origin_dst;
89 u8 *shadow_src, *shadow_dst;
90 u32 *align_shadow_dst;
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 align_shadow_dst =
98 (u32 *)ALIGN_DOWN((u64)shadow_dst, KMSAN_ORIGIN_SIZE);
99
100 shadow_src = kmsan_get_metadata(src, KMSAN_META_SHADOW);
101 if (!shadow_src) {
102 /* @src is untracked: mark @dst as initialized. */
103 kmsan_internal_unpoison_memory(address: dst, size: n, /*checked*/ false);
104 return;
105 }
106 KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(src, n));
107
108 origin_dst = kmsan_get_metadata(dst, KMSAN_META_ORIGIN);
109 origin_src = kmsan_get_metadata(src, KMSAN_META_ORIGIN);
110 KMSAN_WARN_ON(!origin_dst || !origin_src);
111
112 backwards = dst > src;
113 step = backwards ? -1 : 1;
114 iter = backwards ? n - 1 : 0;
115 src_off = (u64)src % KMSAN_ORIGIN_SIZE;
116 dst_off = (u64)dst % KMSAN_ORIGIN_SIZE;
117
118 /* Copy shadow bytes one by one, updating the origins if necessary. */
119 for (i = 0; i < n; i++, iter += step) {
120 oiter_src = (iter + src_off) / KMSAN_ORIGIN_SIZE;
121 oiter_dst = (iter + dst_off) / KMSAN_ORIGIN_SIZE;
122 if (!shadow_src[iter]) {
123 shadow_dst[iter] = 0;
124 if (!align_shadow_dst[oiter_dst])
125 origin_dst[oiter_dst] = 0;
126 continue;
127 }
128 shadow_dst[iter] = shadow_src[iter];
129 old_origin = origin_src[oiter_src];
130 if (old_origin == prev_old_origin)
131 new_origin = prev_new_origin;
132 else {
133 /*
134 * kmsan_internal_chain_origin() may return
135 * NULL, but we don't want to lose the previous
136 * origin value.
137 */
138 new_origin = kmsan_internal_chain_origin(id: old_origin);
139 if (!new_origin)
140 new_origin = old_origin;
141 }
142 origin_dst[oiter_dst] = new_origin;
143 prev_new_origin = new_origin;
144 prev_old_origin = old_origin;
145 }
146}
147
148depot_stack_handle_t kmsan_internal_chain_origin(depot_stack_handle_t id)
149{
150 unsigned long entries[3];
151 u32 extra_bits;
152 int depth;
153 bool uaf;
154 depot_stack_handle_t handle;
155
156 if (!id)
157 return id;
158 /*
159 * Make sure we have enough spare bits in @id to hold the UAF bit and
160 * the chain depth.
161 */
162 BUILD_BUG_ON((1 << STACK_DEPOT_EXTRA_BITS) <=
163 (KMSAN_MAX_ORIGIN_DEPTH << 1));
164
165 extra_bits = stack_depot_get_extra_bits(handle: id);
166 depth = kmsan_depth_from_eb(extra_bits);
167 uaf = kmsan_uaf_from_eb(extra_bits);
168
169 /*
170 * Stop chaining origins once the depth reached KMSAN_MAX_ORIGIN_DEPTH.
171 * This mostly happens in the case structures with uninitialized padding
172 * are copied around many times. Origin chains for such structures are
173 * usually periodic, and it does not make sense to fully store them.
174 */
175 if (depth == KMSAN_MAX_ORIGIN_DEPTH)
176 return id;
177
178 depth++;
179 extra_bits = kmsan_extra_bits(depth, uaf);
180
181 entries[0] = KMSAN_CHAIN_MAGIC_ORIGIN;
182 entries[1] = kmsan_save_stack_with_flags(__GFP_HIGH, extra: 0);
183 entries[2] = id;
184 /*
185 * @entries is a local var in non-instrumented code, so KMSAN does not
186 * know it is initialized. Explicitly unpoison it to avoid false
187 * positives when stack_depot_save() passes it to instrumented code.
188 */
189 kmsan_internal_unpoison_memory(address: entries, size: sizeof(entries), checked: false);
190 handle = stack_depot_save(entries, ARRAY_SIZE(entries), __GFP_HIGH);
191 return stack_depot_set_extra_bits(handle, extra_bits);
192}
193
194void kmsan_internal_set_shadow_origin(void *addr, size_t size, int b,
195 u32 origin, bool checked)
196{
197 u64 address = (u64)addr;
198 u32 *shadow_start, *origin_start;
199 size_t pad = 0;
200
201 KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(addr, size));
202 shadow_start = kmsan_get_metadata(addr, KMSAN_META_SHADOW);
203 if (!shadow_start) {
204 /*
205 * kmsan_metadata_is_contiguous() is true, so either all shadow
206 * and origin pages are NULL, or all are non-NULL.
207 */
208 if (checked) {
209 pr_err("%s: not memsetting %ld bytes starting at %px, because the shadow is NULL\n",
210 __func__, size, addr);
211 KMSAN_WARN_ON(true);
212 }
213 return;
214 }
215 __memset(s: shadow_start, c: b, n: size);
216
217 if (!IS_ALIGNED(address, KMSAN_ORIGIN_SIZE)) {
218 pad = address % KMSAN_ORIGIN_SIZE;
219 address -= pad;
220 size += pad;
221 }
222 size = ALIGN(size, KMSAN_ORIGIN_SIZE);
223 origin_start =
224 (u32 *)kmsan_get_metadata((void *)address, KMSAN_META_ORIGIN);
225
226 /*
227 * If the new origin is non-zero, assume that the shadow byte is also non-zero,
228 * and unconditionally overwrite the old origin slot.
229 * If the new origin is zero, overwrite the old origin slot iff the
230 * corresponding shadow slot is zero.
231 */
232 for (int i = 0; i < size / KMSAN_ORIGIN_SIZE; i++) {
233 if (origin || !shadow_start[i])
234 origin_start[i] = origin;
235 }
236}
237
238struct page *kmsan_vmalloc_to_page_or_null(void *vaddr)
239{
240 struct page *page;
241
242 if (!kmsan_internal_is_vmalloc_addr(addr: vaddr) &&
243 !kmsan_internal_is_module_addr(vaddr))
244 return NULL;
245 page = vmalloc_to_page(addr: vaddr);
246 if (pfn_valid(page_to_pfn(page)))
247 return page;
248 else
249 return NULL;
250}
251
252void kmsan_internal_check_memory(void *addr, size_t size,
253 const void __user *user_addr, int reason)
254{
255 depot_stack_handle_t cur_origin = 0, new_origin = 0;
256 unsigned long addr64 = (unsigned long)addr;
257 depot_stack_handle_t *origin = NULL;
258 unsigned char *shadow = NULL;
259 int cur_off_start = -1;
260 int chunk_size;
261 size_t pos = 0;
262
263 if (!size)
264 return;
265 KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(addr, size));
266 while (pos < size) {
267 chunk_size = min(size - pos,
268 PAGE_SIZE - ((addr64 + pos) % PAGE_SIZE));
269 shadow = kmsan_get_metadata((void *)(addr64 + pos),
270 KMSAN_META_SHADOW);
271 if (!shadow) {
272 /*
273 * This page is untracked. If there were uninitialized
274 * bytes before, report them.
275 */
276 if (cur_origin) {
277 kmsan_report(origin: cur_origin, address: addr, size,
278 off_first: cur_off_start, off_last: pos - 1, user_addr,
279 reason);
280 }
281 cur_origin = 0;
282 cur_off_start = -1;
283 pos += chunk_size;
284 continue;
285 }
286 for (int i = 0; i < chunk_size; i++) {
287 if (!shadow[i]) {
288 /*
289 * This byte is unpoisoned. If there were
290 * poisoned bytes before, report them.
291 */
292 if (cur_origin) {
293 kmsan_report(origin: cur_origin, address: addr, size,
294 off_first: cur_off_start, off_last: pos + i - 1,
295 user_addr, reason);
296 }
297 cur_origin = 0;
298 cur_off_start = -1;
299 continue;
300 }
301 origin = kmsan_get_metadata((void *)(addr64 + pos + i),
302 KMSAN_META_ORIGIN);
303 KMSAN_WARN_ON(!origin);
304 new_origin = *origin;
305 /*
306 * Encountered new origin - report the previous
307 * uninitialized range.
308 */
309 if (cur_origin != new_origin) {
310 if (cur_origin) {
311 kmsan_report(origin: cur_origin, address: addr, size,
312 off_first: cur_off_start, off_last: pos + i - 1,
313 user_addr, reason);
314 }
315 cur_origin = new_origin;
316 cur_off_start = pos + i;
317 }
318 }
319 pos += chunk_size;
320 }
321 KMSAN_WARN_ON(pos != size);
322 if (cur_origin) {
323 kmsan_report(origin: cur_origin, address: addr, size, off_first: cur_off_start, off_last: pos - 1,
324 user_addr, reason);
325 }
326}
327
328bool kmsan_metadata_is_contiguous(void *addr, size_t size)
329{
330 char *cur_shadow = NULL, *next_shadow = NULL, *cur_origin = NULL,
331 *next_origin = NULL;
332 u64 cur_addr = (u64)addr, next_addr = cur_addr + PAGE_SIZE;
333 depot_stack_handle_t *origin_p;
334 bool all_untracked = false;
335
336 if (!size)
337 return true;
338
339 /* The whole range belongs to the same page. */
340 if (ALIGN_DOWN(cur_addr + size - 1, PAGE_SIZE) ==
341 ALIGN_DOWN(cur_addr, PAGE_SIZE))
342 return true;
343
344 cur_shadow = kmsan_get_metadata((void *)cur_addr, /*is_origin*/ false);
345 if (!cur_shadow)
346 all_untracked = true;
347 cur_origin = kmsan_get_metadata((void *)cur_addr, /*is_origin*/ true);
348 if (all_untracked && cur_origin)
349 goto report;
350
351 for (; next_addr < (u64)addr + size;
352 cur_addr = next_addr, cur_shadow = next_shadow,
353 cur_origin = next_origin, next_addr += PAGE_SIZE) {
354 next_shadow = kmsan_get_metadata((void *)next_addr, false);
355 next_origin = kmsan_get_metadata((void *)next_addr, true);
356 if (all_untracked) {
357 if (next_shadow || next_origin)
358 goto report;
359 if (!next_shadow && !next_origin)
360 continue;
361 }
362 if (((u64)cur_shadow == ((u64)next_shadow - PAGE_SIZE)) &&
363 ((u64)cur_origin == ((u64)next_origin - PAGE_SIZE)))
364 continue;
365 goto report;
366 }
367 return true;
368
369report:
370 pr_err("%s: attempting to access two shadow page ranges.\n", __func__);
371 pr_err("Access of size %ld at %px.\n", size, addr);
372 pr_err("Addresses belonging to different ranges: %px and %px\n",
373 (void *)cur_addr, (void *)next_addr);
374 pr_err("page[0].shadow: %px, page[1].shadow: %px\n", cur_shadow,
375 next_shadow);
376 pr_err("page[0].origin: %px, page[1].origin: %px\n", cur_origin,
377 next_origin);
378 origin_p = kmsan_get_metadata(addr, KMSAN_META_ORIGIN);
379 if (origin_p) {
380 pr_err("Origin: %08x\n", *origin_p);
381 kmsan_print_origin(origin: *origin_p);
382 } else {
383 pr_err("Origin: unavailable\n");
384 }
385 return false;
386}
387

source code of linux/mm/kmsan/core.c