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 
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. */
kmsan_internal_memmove_metadata(void * dst,void * src,size_t n)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 
kmsan_internal_chain_origin(depot_stack_handle_t id)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 
kmsan_internal_set_shadow_origin(void * addr,size_t size,int b,u32 origin,bool checked)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 
kmsan_vmalloc_to_page_or_null(void * vaddr)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 
kmsan_internal_check_memory(void * addr,size_t size,const void * user_addr,int reason)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 
kmsan_metadata_is_contiguous(void * addr,size_t size)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 }
451