[linux-block.git] / mm / kmsan / core.c

// SPDX-License-Identifier: GPL-2.0
/*
 * KMSAN runtime library.
 *
 * Copyright (C) 2017-2022 Google LLC
 * Author: Alexander Potapenko <glider@google.com>
 *
 */

#include <asm/page.h>
#include <linux/compiler.h>
#include <linux/export.h>
#include <linux/highmem.h>
#include <linux/interrupt.h>
#include <linux/kernel.h>
#include <linux/kmsan_types.h>
#include <linux/memory.h>
#include <linux/mm.h>
#include <linux/mm_types.h>
#include <linux/mmzone.h>
#include <linux/percpu-defs.h>
#include <linux/preempt.h>
#include <linux/slab.h>
#include <linux/stackdepot.h>
#include <linux/stacktrace.h>
#include <linux/types.h>
#include <linux/vmalloc.h>

#include "../slab.h"
#include "kmsan.h"

bool kmsan_enabled __read_mostly;

/*
 * Per-CPU KMSAN context to be used in interrupts, where current->kmsan is
 * unavaliable.
 */
DEFINE_PER_CPU(struct kmsan_ctx, kmsan_percpu_ctx);

void kmsan_internal_task_create(struct task_struct *task)
{
	struct kmsan_ctx *ctx = &task->kmsan_ctx;
	struct thread_info *info = current_thread_info();

	__memset(ctx, 0, sizeof(*ctx));
	ctx->allow_reporting = true;
	kmsan_internal_unpoison_memory(info, sizeof(*info), false);
}

void kmsan_internal_poison_memory(void *address, size_t size, gfp_t flags,
				  unsigned int poison_flags)
{
	u32 extra_bits =
		kmsan_extra_bits(/*depth*/ 0, poison_flags & KMSAN_POISON_FREE);
	bool checked = poison_flags & KMSAN_POISON_CHECK;
	depot_stack_handle_t handle;

	handle = kmsan_save_stack_with_flags(flags, extra_bits);
	kmsan_internal_set_shadow_origin(address, size, -1, handle, checked);
}

void kmsan_internal_unpoison_memory(void *address, size_t size, bool checked)
{
	kmsan_internal_set_shadow_origin(address, size, 0, 0, checked);
}

depot_stack_handle_t kmsan_save_stack_with_flags(gfp_t flags,
						 unsigned int extra)
{
	unsigned long entries[KMSAN_STACK_DEPTH];
	unsigned int nr_entries;
	depot_stack_handle_t handle;

	nr_entries = stack_trace_save(entries, KMSAN_STACK_DEPTH, 0);

	/* Don't sleep. */
	flags &= ~__GFP_DIRECT_RECLAIM;

	handle = __stack_depot_save(entries, nr_entries, flags, true);
	return stack_depot_set_extra_bits(handle, extra);
}

/* Copy the metadata following the memmove() behavior. */
void kmsan_internal_memmove_metadata(void *dst, void *src, size_t n)
{
	depot_stack_handle_t old_origin = 0, new_origin = 0;
	int src_slots, dst_slots, i, iter, step, skip_bits;
	depot_stack_handle_t *origin_src, *origin_dst;
	void *shadow_src, *shadow_dst;
	u32 *align_shadow_src, shadow;
	bool backwards;

	shadow_dst = kmsan_get_metadata(dst, KMSAN_META_SHADOW);
	if (!shadow_dst)
		return;
	KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(dst, n));

	shadow_src = kmsan_get_metadata(src, KMSAN_META_SHADOW);
	if (!shadow_src) {
		/*
		 * @src is untracked: zero out destination shadow, ignore the
		 * origins, we're done.
		 */
		__memset(shadow_dst, 0, n);
		return;
	}
	KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(src, n));

	__memmove(shadow_dst, shadow_src, n);

	origin_dst = kmsan_get_metadata(dst, KMSAN_META_ORIGIN);
	origin_src = kmsan_get_metadata(src, KMSAN_META_ORIGIN);
	KMSAN_WARN_ON(!origin_dst || !origin_src);
	src_slots = (ALIGN((u64)src + n, KMSAN_ORIGIN_SIZE) -
		     ALIGN_DOWN((u64)src, KMSAN_ORIGIN_SIZE)) /
		    KMSAN_ORIGIN_SIZE;
	dst_slots = (ALIGN((u64)dst + n, KMSAN_ORIGIN_SIZE) -
		     ALIGN_DOWN((u64)dst, KMSAN_ORIGIN_SIZE)) /
		    KMSAN_ORIGIN_SIZE;
	KMSAN_WARN_ON((src_slots < 1) || (dst_slots < 1));
	KMSAN_WARN_ON((src_slots - dst_slots > 1) ||
		      (dst_slots - src_slots < -1));

	backwards = dst > src;
	i = backwards ? min(src_slots, dst_slots) - 1 : 0;
	iter = backwards ? -1 : 1;

	align_shadow_src =
		(u32 *)ALIGN_DOWN((u64)shadow_src, KMSAN_ORIGIN_SIZE);
	for (step = 0; step < min(src_slots, dst_slots); step++, i += iter) {
		KMSAN_WARN_ON(i < 0);
		shadow = align_shadow_src[i];
		if (i == 0) {
			/*
			 * If @src isn't aligned on KMSAN_ORIGIN_SIZE, don't
			 * look at the first @src % KMSAN_ORIGIN_SIZE bytes
			 * of the first shadow slot.
			 */
			skip_bits = ((u64)src % KMSAN_ORIGIN_SIZE) * 8;
			shadow = (shadow >> skip_bits) << skip_bits;
		}
		if (i == src_slots - 1) {
			/*
			 * If @src + n isn't aligned on
			 * KMSAN_ORIGIN_SIZE, don't look at the last
			 * (@src + n) % KMSAN_ORIGIN_SIZE bytes of the
			 * last shadow slot.
			 */
			skip_bits = (((u64)src + n) % KMSAN_ORIGIN_SIZE) * 8;
			shadow = (shadow << skip_bits) >> skip_bits;
		}
		/*
		 * Overwrite the origin only if the corresponding
		 * shadow is nonempty.
		 */
		if (origin_src[i] && (origin_src[i] != old_origin) && shadow) {
			old_origin = origin_src[i];
			new_origin = kmsan_internal_chain_origin(old_origin);
			/*
			 * kmsan_internal_chain_origin() may return
			 * NULL, but we don't want to lose the previous
			 * origin value.
			 */
			if (!new_origin)
				new_origin = old_origin;
		}
		if (shadow)
			origin_dst[i] = new_origin;
		else
			origin_dst[i] = 0;
	}
	/*
	 * If dst_slots is greater than src_slots (i.e.
	 * dst_slots == src_slots + 1), there is an extra origin slot at the
	 * beginning or end of the destination buffer, for which we take the
	 * origin from the previous slot.
	 * This is only done if the part of the source shadow corresponding to
	 * slot is non-zero.
	 *
	 * E.g. if we copy 8 aligned bytes that are marked as uninitialized
	 * and have origins o111 and o222, to an unaligned buffer with offset 1,
	 * these two origins are copied to three origin slots, so one of then
	 * needs to be duplicated, depending on the copy direction (@backwards)
	 *
	 *   src shadow: |uuuu|uuuu|....|
	 *   src origin: |o111|o222|....|
	 *
	 * backwards = 0:
	 *   dst shadow: |.uuu|uuuu|u...|
	 *   dst origin: |....|o111|o222| - fill the empty slot with o111
	 * backwards = 1:
	 *   dst shadow: |.uuu|uuuu|u...|
	 *   dst origin: |o111|o222|....| - fill the empty slot with o222
	 */
	if (src_slots < dst_slots) {
		if (backwards) {
			shadow = align_shadow_src[src_slots - 1];
			skip_bits = (((u64)dst + n) % KMSAN_ORIGIN_SIZE) * 8;
			shadow = (shadow << skip_bits) >> skip_bits;
			if (shadow)
				/* src_slots > 0, therefore dst_slots is at least 2 */
				origin_dst[dst_slots - 1] =
					origin_dst[dst_slots - 2];
		} else {
			shadow = align_shadow_src[0];
			skip_bits = ((u64)dst % KMSAN_ORIGIN_SIZE) * 8;
			shadow = (shadow >> skip_bits) << skip_bits;
			if (shadow)
				origin_dst[0] = origin_dst[1];
		}
	}
}

depot_stack_handle_t kmsan_internal_chain_origin(depot_stack_handle_t id)
{
	unsigned long entries[3];
	u32 extra_bits;
	int depth;
	bool uaf;
	depot_stack_handle_t handle;

	if (!id)
		return id;
	/*
	 * Make sure we have enough spare bits in @id to hold the UAF bit and
	 * the chain depth.
	 */
	BUILD_BUG_ON(
		(1 << STACK_DEPOT_EXTRA_BITS) <= (KMSAN_MAX_ORIGIN_DEPTH << 1));

	extra_bits = stack_depot_get_extra_bits(id);
	depth = kmsan_depth_from_eb(extra_bits);
	uaf = kmsan_uaf_from_eb(extra_bits);

	/*
	 * Stop chaining origins once the depth reached KMSAN_MAX_ORIGIN_DEPTH.
	 * This mostly happens in the case structures with uninitialized padding
	 * are copied around many times. Origin chains for such structures are
	 * usually periodic, and it does not make sense to fully store them.
	 */
	if (depth == KMSAN_MAX_ORIGIN_DEPTH)
		return id;

	depth++;
	extra_bits = kmsan_extra_bits(depth, uaf);

	entries[0] = KMSAN_CHAIN_MAGIC_ORIGIN;
	entries[1] = kmsan_save_stack_with_flags(GFP_ATOMIC, 0);
	entries[2] = id;
	/*
	 * @entries is a local var in non-instrumented code, so KMSAN does not
	 * know it is initialized. Explicitly unpoison it to avoid false
	 * positives when __stack_depot_save() passes it to instrumented code.
	 */
	kmsan_internal_unpoison_memory(entries, sizeof(entries), false);
	handle = __stack_depot_save(entries, ARRAY_SIZE(entries), GFP_ATOMIC,
				    true);
	return stack_depot_set_extra_bits(handle, extra_bits);
}

void kmsan_internal_set_shadow_origin(void *addr, size_t size, int b,
				      u32 origin, bool checked)
{
	u64 address = (u64)addr;
	void *shadow_start;
	u32 *origin_start;
	size_t pad = 0;

	KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(addr, size));
	shadow_start = kmsan_get_metadata(addr, KMSAN_META_SHADOW);
	if (!shadow_start) {
		/*
		 * kmsan_metadata_is_contiguous() is true, so either all shadow
		 * and origin pages are NULL, or all are non-NULL.
		 */
		if (checked) {
			pr_err("%s: not memsetting %ld bytes starting at %px, because the shadow is NULL\n",
			       __func__, size, addr);
			KMSAN_WARN_ON(true);
		}
		return;
	}
	__memset(shadow_start, b, size);

	if (!IS_ALIGNED(address, KMSAN_ORIGIN_SIZE)) {
		pad = address % KMSAN_ORIGIN_SIZE;
		address -= pad;
		size += pad;
	}
	size = ALIGN(size, KMSAN_ORIGIN_SIZE);
	origin_start =
		(u32 *)kmsan_get_metadata((void *)address, KMSAN_META_ORIGIN);

	for (int i = 0; i < size / KMSAN_ORIGIN_SIZE; i++)
		origin_start[i] = origin;
}

struct page *kmsan_vmalloc_to_page_or_null(void *vaddr)
{
	struct page *page;

	if (!kmsan_internal_is_vmalloc_addr(vaddr) &&
	    !kmsan_internal_is_module_addr(vaddr))
		return NULL;
	page = vmalloc_to_page(vaddr);
	if (pfn_valid(page_to_pfn(page)))
		return page;
	else
		return NULL;
}

void kmsan_internal_check_memory(void *addr, size_t size, const void *user_addr,
				 int reason)
{
	depot_stack_handle_t cur_origin = 0, new_origin = 0;
	unsigned long addr64 = (unsigned long)addr;
	depot_stack_handle_t *origin = NULL;
	unsigned char *shadow = NULL;
	int cur_off_start = -1;
	int chunk_size;
	size_t pos = 0;

	if (!size)
		return;
	KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(addr, size));
	while (pos < size) {
		chunk_size = min(size - pos,
				 PAGE_SIZE - ((addr64 + pos) % PAGE_SIZE));
		shadow = kmsan_get_metadata((void *)(addr64 + pos),
					    KMSAN_META_SHADOW);
		if (!shadow) {
			/*
			 * This page is untracked. If there were uninitialized
			 * bytes before, report them.
			 */
			if (cur_origin) {
				kmsan_enter_runtime();
				kmsan_report(cur_origin, addr, size,
					     cur_off_start, pos - 1, user_addr,
					     reason);
				kmsan_leave_runtime();
			}
			cur_origin = 0;
			cur_off_start = -1;
			pos += chunk_size;
			continue;
		}
		for (int i = 0; i < chunk_size; i++) {
			if (!shadow[i]) {
				/*
				 * This byte is unpoisoned. If there were
				 * poisoned bytes before, report them.
				 */
				if (cur_origin) {
					kmsan_enter_runtime();
					kmsan_report(cur_origin, addr, size,
						     cur_off_start, pos + i - 1,
						     user_addr, reason);
					kmsan_leave_runtime();
				}
				cur_origin = 0;
				cur_off_start = -1;
				continue;
			}
			origin = kmsan_get_metadata((void *)(addr64 + pos + i),
						    KMSAN_META_ORIGIN);
			KMSAN_WARN_ON(!origin);
			new_origin = *origin;
			/*
			 * Encountered new origin - report the previous
			 * uninitialized range.
			 */
			if (cur_origin != new_origin) {
				if (cur_origin) {
					kmsan_enter_runtime();
					kmsan_report(cur_origin, addr, size,
						     cur_off_start, pos + i - 1,
						     user_addr, reason);
					kmsan_leave_runtime();
				}
				cur_origin = new_origin;
				cur_off_start = pos + i;
			}
		}
		pos += chunk_size;
	}
	KMSAN_WARN_ON(pos != size);
	if (cur_origin) {
		kmsan_enter_runtime();
		kmsan_report(cur_origin, addr, size, cur_off_start, pos - 1,
			     user_addr, reason);
		kmsan_leave_runtime();
	}
}

bool kmsan_metadata_is_contiguous(void *addr, size_t size)
{
	char *cur_shadow = NULL, *next_shadow = NULL, *cur_origin = NULL,
	     *next_origin = NULL;
	u64 cur_addr = (u64)addr, next_addr = cur_addr + PAGE_SIZE;
	depot_stack_handle_t *origin_p;
	bool all_untracked = false;

	if (!size)
		return true;

	/* The whole range belongs to the same page. */
	if (ALIGN_DOWN(cur_addr + size - 1, PAGE_SIZE) ==
	    ALIGN_DOWN(cur_addr, PAGE_SIZE))
		return true;

	cur_shadow = kmsan_get_metadata((void *)cur_addr, /*is_origin*/ false);
	if (!cur_shadow)
		all_untracked = true;
	cur_origin = kmsan_get_metadata((void *)cur_addr, /*is_origin*/ true);
	if (all_untracked && cur_origin)
		goto report;

	for (; next_addr < (u64)addr + size;
	     cur_addr = next_addr, cur_shadow = next_shadow,
	     cur_origin = next_origin, next_addr += PAGE_SIZE) {
		next_shadow = kmsan_get_metadata((void *)next_addr, false);
		next_origin = kmsan_get_metadata((void *)next_addr, true);
		if (all_untracked) {
			if (next_shadow || next_origin)
				goto report;
			if (!next_shadow && !next_origin)
				continue;
		}
		if (((u64)cur_shadow == ((u64)next_shadow - PAGE_SIZE)) &&
		    ((u64)cur_origin == ((u64)next_origin - PAGE_SIZE)))
			continue;
		goto report;
	}
	return true;

report:
	pr_err("%s: attempting to access two shadow page ranges.\n", __func__);
	pr_err("Access of size %ld at %px.\n", size, addr);
	pr_err("Addresses belonging to different ranges: %px and %px\n",
	       (void *)cur_addr, (void *)next_addr);
	pr_err("page[0].shadow: %px, page[1].shadow: %px\n", cur_shadow,
	       next_shadow);
	pr_err("page[0].origin: %px, page[1].origin: %px\n", cur_origin,
	       next_origin);
	origin_p = kmsan_get_metadata(addr, KMSAN_META_ORIGIN);
	if (origin_p) {
		pr_err("Origin: %08x\n", *origin_p);
		kmsan_print_origin(*origin_p);
	} else {
		pr_err("Origin: unavailable\n");
	}
	return false;
}
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. */
f80be457 AP	77	flags &= ~__GFP_DIRECT_RECLAIM;
f80be457 AP	78
36aa1e67 AK	79	handle = __stack_depot_save(entries, nr_entries, flags, true);
36aa1e67 AK	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;
	248	entries[1] = kmsan_save_stack_with_flags(GFP_ATOMIC, 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);
36aa1e67 AK	256	handle = __stack_depot_save(entries, ARRAY_SIZE(entries), GFP_ATOMIC,
	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	}