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 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 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; 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. */ 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 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 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 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 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 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