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(ctx, 0, sizeof(*ctx)); 46 ctx->allow_reporting = true; 47 kmsan_internal_unpoison_memory(info, sizeof(*info), false); 48} 49 50void 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 62void 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 67depot_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. */ 84void 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 214depot_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 261void 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 298struct 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 312void 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 396bool 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 437report: 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