395 lines · c
1// SPDX-License-Identifier: GPL-2.02/*3 * KMSAN runtime library.4 *5 * Copyright (C) 2017-2022 Google LLC6 * 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 is36 * 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(ctx, 0, sizeof(*ctx));46 kmsan_internal_unpoison_memory(info, sizeof(*info), 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, 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, -1, 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, 0, 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(entries, KMSAN_STACK_DEPTH, 0);74 75 /* Don't sleep. */76 flags &= ~(__GFP_DIRECT_RECLAIM | __GFP_KSWAPD_RECLAIM);77 78 handle = stack_depot_save(entries, nr_entries, flags);79 return stack_depot_set_extra_bits(handle, 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(dst, 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 return135 * NULL, but we don't want to lose the previous136 * origin value.137 */138 new_origin = kmsan_internal_chain_origin(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 and160 * the chain depth.161 */162 BUILD_BUG_ON(163 (1 << STACK_DEPOT_EXTRA_BITS) <= (KMSAN_MAX_ORIGIN_DEPTH << 1));164 165 extra_bits = stack_depot_get_extra_bits(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 padding172 * are copied around many times. Origin chains for such structures are173 * 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, 0);183 entries[2] = id;184 /*185 * @entries is a local var in non-instrumented code, so KMSAN does not186 * know it is initialized. Explicitly unpoison it to avoid false187 * positives when stack_depot_save() passes it to instrumented code.188 */189 kmsan_internal_unpoison_memory(entries, sizeof(entries), 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 shadow206 * 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(shadow_start, b, 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 the230 * 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(vaddr) &&243 !kmsan_internal_is_module_addr(vaddr))244 return NULL;245 page = vmalloc_to_page(vaddr);246 if (pfn_valid(page_to_pfn(page)))247 return page;248 else249 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 uninitialized274 * bytes before, report them.275 */276 if (cur_origin) {277 kmsan_enter_runtime();278 kmsan_report(cur_origin, addr, size,279 cur_off_start, pos - 1, user_addr,280 reason);281 kmsan_leave_runtime();282 }283 cur_origin = 0;284 cur_off_start = -1;285 pos += chunk_size;286 continue;287 }288 for (int i = 0; i < chunk_size; i++) {289 if (!shadow[i]) {290 /*291 * This byte is unpoisoned. If there were292 * poisoned bytes before, report them.293 */294 if (cur_origin) {295 kmsan_enter_runtime();296 kmsan_report(cur_origin, addr, size,297 cur_off_start, pos + i - 1,298 user_addr, reason);299 kmsan_leave_runtime();300 }301 cur_origin = 0;302 cur_off_start = -1;303 continue;304 }305 origin = kmsan_get_metadata((void *)(addr64 + pos + i),306 KMSAN_META_ORIGIN);307 KMSAN_WARN_ON(!origin);308 new_origin = *origin;309 /*310 * Encountered new origin - report the previous311 * uninitialized range.312 */313 if (cur_origin != new_origin) {314 if (cur_origin) {315 kmsan_enter_runtime();316 kmsan_report(cur_origin, addr, size,317 cur_off_start, pos + i - 1,318 user_addr, reason);319 kmsan_leave_runtime();320 }321 cur_origin = new_origin;322 cur_off_start = pos + i;323 }324 }325 pos += chunk_size;326 }327 KMSAN_WARN_ON(pos != size);328 if (cur_origin) {329 kmsan_enter_runtime();330 kmsan_report(cur_origin, addr, size, cur_off_start, pos - 1,331 user_addr, reason);332 kmsan_leave_runtime();333 }334}335 336bool kmsan_metadata_is_contiguous(void *addr, size_t size)337{338 char *cur_shadow = NULL, *next_shadow = NULL, *cur_origin = NULL,339 *next_origin = NULL;340 u64 cur_addr = (u64)addr, next_addr = cur_addr + PAGE_SIZE;341 depot_stack_handle_t *origin_p;342 bool all_untracked = false;343 344 if (!size)345 return true;346 347 /* The whole range belongs to the same page. */348 if (ALIGN_DOWN(cur_addr + size - 1, PAGE_SIZE) ==349 ALIGN_DOWN(cur_addr, PAGE_SIZE))350 return true;351 352 cur_shadow = kmsan_get_metadata((void *)cur_addr, /*is_origin*/ false);353 if (!cur_shadow)354 all_untracked = true;355 cur_origin = kmsan_get_metadata((void *)cur_addr, /*is_origin*/ true);356 if (all_untracked && cur_origin)357 goto report;358 359 for (; next_addr < (u64)addr + size;360 cur_addr = next_addr, cur_shadow = next_shadow,361 cur_origin = next_origin, next_addr += PAGE_SIZE) {362 next_shadow = kmsan_get_metadata((void *)next_addr, false);363 next_origin = kmsan_get_metadata((void *)next_addr, true);364 if (all_untracked) {365 if (next_shadow || next_origin)366 goto report;367 if (!next_shadow && !next_origin)368 continue;369 }370 if (((u64)cur_shadow == ((u64)next_shadow - PAGE_SIZE)) &&371 ((u64)cur_origin == ((u64)next_origin - PAGE_SIZE)))372 continue;373 goto report;374 }375 return true;376 377report:378 pr_err("%s: attempting to access two shadow page ranges.\n", __func__);379 pr_err("Access of size %ld at %px.\n", size, addr);380 pr_err("Addresses belonging to different ranges: %px and %px\n",381 (void *)cur_addr, (void *)next_addr);382 pr_err("page[0].shadow: %px, page[1].shadow: %px\n", cur_shadow,383 next_shadow);384 pr_err("page[0].origin: %px, page[1].origin: %px\n", cur_origin,385 next_origin);386 origin_p = kmsan_get_metadata(addr, KMSAN_META_ORIGIN);387 if (origin_p) {388 pr_err("Origin: %08x\n", *origin_p);389 kmsan_print_origin(*origin_p);390 } else {391 pr_err("Origin: unavailable\n");392 }393 return false;394}395