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 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); 80 return stack_depot_set_extra_bits(handle, extra); 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 prev_old_origin = 0, prev_new_origin = 0; 87 int i, iter, step, src_off, dst_off, oiter_src, oiter_dst; 88 depot_stack_handle_t old_origin = 0, new_origin = 0; 89 depot_stack_handle_t *origin_src, *origin_dst; 90 u8 *shadow_src, *shadow_dst; 91 u32 *align_shadow_dst; 92 bool backwards; 93 94 shadow_dst = kmsan_get_metadata(dst, KMSAN_META_SHADOW); 95 if (!shadow_dst) 96 return; 97 KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(dst, n)); 98 align_shadow_dst = 99 (u32 *)ALIGN_DOWN((u64)shadow_dst, KMSAN_ORIGIN_SIZE); 100 101 shadow_src = kmsan_get_metadata(src, KMSAN_META_SHADOW); 102 if (!shadow_src) { 103 /* @src is untracked: mark @dst as initialized. */ 104 kmsan_internal_unpoison_memory(dst, n, /*checked*/ false); 105 return; 106 } 107 KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(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 113 backwards = dst > src; 114 step = backwards ? -1 : 1; 115 iter = backwards ? n - 1 : 0; 116 src_off = (u64)src % KMSAN_ORIGIN_SIZE; 117 dst_off = (u64)dst % KMSAN_ORIGIN_SIZE; 118 119 /* Copy shadow bytes one by one, updating the origins if necessary. */ 120 for (i = 0; i < n; i++, iter += step) { 121 oiter_src = (iter + src_off) / KMSAN_ORIGIN_SIZE; 122 oiter_dst = (iter + dst_off) / KMSAN_ORIGIN_SIZE; 123 if (!shadow_src[iter]) { 124 shadow_dst[iter] = 0; 125 if (!align_shadow_dst[oiter_dst]) 126 origin_dst[oiter_dst] = 0; 127 continue; 128 } 129 shadow_dst[iter] = shadow_src[iter]; 130 old_origin = origin_src[oiter_src]; 131 if (old_origin == prev_old_origin) 132 new_origin = prev_new_origin; 133 else { 134 /* 135 * kmsan_internal_chain_origin() may return 136 * NULL, but we don't want to lose the previous 137 * origin value. 138 */ 139 new_origin = kmsan_internal_chain_origin(old_origin); 140 if (!new_origin) 141 new_origin = old_origin; 142 } 143 origin_dst[oiter_dst] = new_origin; 144 prev_new_origin = new_origin; 145 prev_old_origin = old_origin; 146 } 147 } 148 149 depot_stack_handle_t kmsan_internal_chain_origin(depot_stack_handle_t id) 150 { 151 unsigned long entries[3]; 152 u32 extra_bits; 153 int depth; 154 bool uaf; 155 depot_stack_handle_t handle; 156 157 if (!id) 158 return id; 159 /* 160 * Make sure we have enough spare bits in @id to hold the UAF bit and 161 * the chain depth. 162 */ 163 BUILD_BUG_ON( 164 (1 << STACK_DEPOT_EXTRA_BITS) <= (KMSAN_MAX_ORIGIN_DEPTH << 1)); 165 166 extra_bits = stack_depot_get_extra_bits(id); 167 depth = kmsan_depth_from_eb(extra_bits); 168 uaf = kmsan_uaf_from_eb(extra_bits); 169 170 /* 171 * Stop chaining origins once the depth reached KMSAN_MAX_ORIGIN_DEPTH. 172 * This mostly happens in the case structures with uninitialized padding 173 * are copied around many times. Origin chains for such structures are 174 * usually periodic, and it does not make sense to fully store them. 175 */ 176 if (depth == KMSAN_MAX_ORIGIN_DEPTH) 177 return id; 178 179 depth++; 180 extra_bits = kmsan_extra_bits(depth, uaf); 181 182 entries[0] = KMSAN_CHAIN_MAGIC_ORIGIN; 183 entries[1] = kmsan_save_stack_with_flags(__GFP_HIGH, 0); 184 entries[2] = id; 185 /* 186 * @entries is a local var in non-instrumented code, so KMSAN does not 187 * know it is initialized. Explicitly unpoison it to avoid false 188 * positives when stack_depot_save() passes it to instrumented code. 189 */ 190 kmsan_internal_unpoison_memory(entries, sizeof(entries), false); 191 handle = stack_depot_save(entries, ARRAY_SIZE(entries), __GFP_HIGH); 192 return stack_depot_set_extra_bits(handle, extra_bits); 193 } 194 195 void kmsan_internal_set_shadow_origin(void *addr, size_t size, int b, 196 u32 origin, bool checked) 197 { 198 u64 address = (u64)addr; 199 u32 *shadow_start, *origin_start; 200 size_t pad = 0; 201 202 KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(addr, size)); 203 shadow_start = kmsan_get_metadata(addr, KMSAN_META_SHADOW); 204 if (!shadow_start) { 205 /* 206 * kmsan_metadata_is_contiguous() is true, so either all shadow 207 * and origin pages are NULL, or all are non-NULL. 208 */ 209 if (checked) { 210 pr_err("%s: not memsetting %ld bytes starting at %px, because the shadow is NULL\n", 211 __func__, size, addr); 212 KMSAN_WARN_ON(true); 213 } 214 return; 215 } 216 __memset(shadow_start, b, size); 217 218 if (!IS_ALIGNED(address, KMSAN_ORIGIN_SIZE)) { 219 pad = address % KMSAN_ORIGIN_SIZE; 220 address -= pad; 221 size += pad; 222 } 223 size = ALIGN(size, KMSAN_ORIGIN_SIZE); 224 origin_start = 225 (u32 *)kmsan_get_metadata((void *)address, KMSAN_META_ORIGIN); 226 227 /* 228 * If the new origin is non-zero, assume that the shadow byte is also non-zero, 229 * and unconditionally overwrite the old origin slot. 230 * If the new origin is zero, overwrite the old origin slot iff the 231 * corresponding shadow slot is zero. 232 */ 233 for (int i = 0; i < size / KMSAN_ORIGIN_SIZE; i++) { 234 if (origin || !shadow_start[i]) 235 origin_start[i] = origin; 236 } 237 } 238 239 struct page *kmsan_vmalloc_to_page_or_null(void *vaddr) 240 { 241 struct page *page; 242 243 if (!kmsan_internal_is_vmalloc_addr(vaddr) && 244 !kmsan_internal_is_module_addr(vaddr)) 245 return NULL; 246 page = vmalloc_to_page(vaddr); 247 if (pfn_valid(page_to_pfn(page))) 248 return page; 249 else 250 return NULL; 251 } 252 253 void kmsan_internal_check_memory(void *addr, size_t size, const void *user_addr, 254 int reason) 255 { 256 depot_stack_handle_t cur_origin = 0, new_origin = 0; 257 unsigned long addr64 = (unsigned long)addr; 258 depot_stack_handle_t *origin = NULL; 259 unsigned char *shadow = NULL; 260 int cur_off_start = -1; 261 int chunk_size; 262 size_t pos = 0; 263 264 if (!size) 265 return; 266 KMSAN_WARN_ON(!kmsan_metadata_is_contiguous(addr, size)); 267 while (pos < size) { 268 chunk_size = min(size - pos, 269 PAGE_SIZE - ((addr64 + pos) % PAGE_SIZE)); 270 shadow = kmsan_get_metadata((void *)(addr64 + pos), 271 KMSAN_META_SHADOW); 272 if (!shadow) { 273 /* 274 * This page is untracked. If there were uninitialized 275 * bytes before, report them. 276 */ 277 if (cur_origin) { 278 kmsan_enter_runtime(); 279 kmsan_report(cur_origin, addr, size, 280 cur_off_start, pos - 1, user_addr, 281 reason); 282 kmsan_leave_runtime(); 283 } 284 cur_origin = 0; 285 cur_off_start = -1; 286 pos += chunk_size; 287 continue; 288 } 289 for (int i = 0; i < chunk_size; i++) { 290 if (!shadow[i]) { 291 /* 292 * This byte is unpoisoned. If there were 293 * poisoned bytes before, report them. 294 */ 295 if (cur_origin) { 296 kmsan_enter_runtime(); 297 kmsan_report(cur_origin, addr, size, 298 cur_off_start, pos + i - 1, 299 user_addr, reason); 300 kmsan_leave_runtime(); 301 } 302 cur_origin = 0; 303 cur_off_start = -1; 304 continue; 305 } 306 origin = kmsan_get_metadata((void *)(addr64 + pos + i), 307 KMSAN_META_ORIGIN); 308 KMSAN_WARN_ON(!origin); 309 new_origin = *origin; 310 /* 311 * Encountered new origin - report the previous 312 * uninitialized range. 313 */ 314 if (cur_origin != new_origin) { 315 if (cur_origin) { 316 kmsan_enter_runtime(); 317 kmsan_report(cur_origin, addr, size, 318 cur_off_start, pos + i - 1, 319 user_addr, reason); 320 kmsan_leave_runtime(); 321 } 322 cur_origin = new_origin; 323 cur_off_start = pos + i; 324 } 325 } 326 pos += chunk_size; 327 } 328 KMSAN_WARN_ON(pos != size); 329 if (cur_origin) { 330 kmsan_enter_runtime(); 331 kmsan_report(cur_origin, addr, size, cur_off_start, pos - 1, 332 user_addr, reason); 333 kmsan_leave_runtime(); 334 } 335 } 336 337 bool kmsan_metadata_is_contiguous(void *addr, size_t size) 338 { 339 char *cur_shadow = NULL, *next_shadow = NULL, *cur_origin = NULL, 340 *next_origin = NULL; 341 u64 cur_addr = (u64)addr, next_addr = cur_addr + PAGE_SIZE; 342 depot_stack_handle_t *origin_p; 343 bool all_untracked = false; 344 345 if (!size) 346 return true; 347 348 /* The whole range belongs to the same page. */ 349 if (ALIGN_DOWN(cur_addr + size - 1, PAGE_SIZE) == 350 ALIGN_DOWN(cur_addr, PAGE_SIZE)) 351 return true; 352 353 cur_shadow = kmsan_get_metadata((void *)cur_addr, /*is_origin*/ false); 354 if (!cur_shadow) 355 all_untracked = true; 356 cur_origin = kmsan_get_metadata((void *)cur_addr, /*is_origin*/ true); 357 if (all_untracked && cur_origin) 358 goto report; 359 360 for (; next_addr < (u64)addr + size; 361 cur_addr = next_addr, cur_shadow = next_shadow, 362 cur_origin = next_origin, next_addr += PAGE_SIZE) { 363 next_shadow = kmsan_get_metadata((void *)next_addr, false); 364 next_origin = kmsan_get_metadata((void *)next_addr, true); 365 if (all_untracked) { 366 if (next_shadow || next_origin) 367 goto report; 368 if (!next_shadow && !next_origin) 369 continue; 370 } 371 if (((u64)cur_shadow == ((u64)next_shadow - PAGE_SIZE)) && 372 ((u64)cur_origin == ((u64)next_origin - PAGE_SIZE))) 373 continue; 374 goto report; 375 } 376 return true; 377 378 report: 379 pr_err("%s: attempting to access two shadow page ranges.\n", __func__); 380 pr_err("Access of size %ld at %px.\n", size, addr); 381 pr_err("Addresses belonging to different ranges: %px and %px\n", 382 (void *)cur_addr, (void *)next_addr); 383 pr_err("page[0].shadow: %px, page[1].shadow: %px\n", cur_shadow, 384 next_shadow); 385 pr_err("page[0].origin: %px, page[1].origin: %px\n", cur_origin, 386 next_origin); 387 origin_p = kmsan_get_metadata(addr, KMSAN_META_ORIGIN); 388 if (origin_p) { 389 pr_err("Origin: %08x\n", *origin_p); 390 kmsan_print_origin(*origin_p); 391 } else { 392 pr_err("Origin: unavailable\n"); 393 } 394 return false; 395 } 396