1.. SPDX-License-Identifier: GPL-2.0 2.. Copyright (C) 2022, Google LLC. 3 4=================================== 5The Kernel Memory Sanitizer (KMSAN) 6=================================== 7 8KMSAN is a dynamic error detector aimed at finding uses of uninitialized 9values. It is based on compiler instrumentation, and is quite similar to the 10userspace `MemorySanitizer tool`_. 11 12An important note is that KMSAN is not intended for production use, because it 13drastically increases kernel memory footprint and slows the whole system down. 14 15Usage 16===== 17 18Building the kernel 19------------------- 20 21In order to build a kernel with KMSAN you will need a fresh Clang (14.0.6+). 22Please refer to `LLVM documentation`_ for the instructions on how to build Clang. 23 24Now configure and build the kernel with CONFIG_KMSAN enabled. 25 26Example report 27-------------- 28 29Here is an example of a KMSAN report:: 30 31 ===================================================== 32 BUG: KMSAN: uninit-value in test_uninit_kmsan_check_memory+0x1be/0x380 [kmsan_test] 33 test_uninit_kmsan_check_memory+0x1be/0x380 mm/kmsan/kmsan_test.c:273 34 kunit_run_case_internal lib/kunit/test.c:333 35 kunit_try_run_case+0x206/0x420 lib/kunit/test.c:374 36 kunit_generic_run_threadfn_adapter+0x6d/0xc0 lib/kunit/try-catch.c:28 37 kthread+0x721/0x850 kernel/kthread.c:327 38 ret_from_fork+0x1f/0x30 ??:? 39 40 Uninit was stored to memory at: 41 do_uninit_local_array+0xfa/0x110 mm/kmsan/kmsan_test.c:260 42 test_uninit_kmsan_check_memory+0x1a2/0x380 mm/kmsan/kmsan_test.c:271 43 kunit_run_case_internal lib/kunit/test.c:333 44 kunit_try_run_case+0x206/0x420 lib/kunit/test.c:374 45 kunit_generic_run_threadfn_adapter+0x6d/0xc0 lib/kunit/try-catch.c:28 46 kthread+0x721/0x850 kernel/kthread.c:327 47 ret_from_fork+0x1f/0x30 ??:? 48 49 Local variable uninit created at: 50 do_uninit_local_array+0x4a/0x110 mm/kmsan/kmsan_test.c:256 51 test_uninit_kmsan_check_memory+0x1a2/0x380 mm/kmsan/kmsan_test.c:271 52 53 Bytes 4-7 of 8 are uninitialized 54 Memory access of size 8 starts at ffff888083fe3da0 55 56 CPU: 0 PID: 6731 Comm: kunit_try_catch Tainted: G B E 5.16.0-rc3+ #104 57 Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-2 04/01/2014 58 ===================================================== 59 60The report says that the local variable ``uninit`` was created uninitialized in 61``do_uninit_local_array()``. The third stack trace corresponds to the place 62where this variable was created. 63 64The first stack trace shows where the uninit value was used (in 65``test_uninit_kmsan_check_memory()``). The tool shows the bytes which were left 66uninitialized in the local variable, as well as the stack where the value was 67copied to another memory location before use. 68 69A use of uninitialized value ``v`` is reported by KMSAN in the following cases: 70 71 - in a condition, e.g. ``if (v) { ... }``; 72 - in an indexing or pointer dereferencing, e.g. ``array[v]`` or ``*v``; 73 - when it is copied to userspace or hardware, e.g. ``copy_to_user(..., &v, ...)``; 74 - when it is passed as an argument to a function, and 75 ``CONFIG_KMSAN_CHECK_PARAM_RETVAL`` is enabled (see below). 76 77The mentioned cases (apart from copying data to userspace or hardware, which is 78a security issue) are considered undefined behavior from the C11 Standard point 79of view. 80 81Disabling the instrumentation 82----------------------------- 83 84A function can be marked with ``__no_kmsan_checks``. Doing so makes KMSAN 85ignore uninitialized values in that function and mark its output as initialized. 86As a result, the user will not get KMSAN reports related to that function. 87 88Another function attribute supported by KMSAN is ``__no_sanitize_memory``. 89Applying this attribute to a function will result in KMSAN not instrumenting 90it, which can be helpful if we do not want the compiler to interfere with some 91low-level code (e.g. that marked with ``noinstr`` which implicitly adds 92``__no_sanitize_memory``). 93 94This however comes at a cost: stack allocations from such functions will have 95incorrect shadow/origin values, likely leading to false positives. Functions 96called from non-instrumented code may also receive incorrect metadata for their 97parameters. 98 99As a rule of thumb, avoid using ``__no_sanitize_memory`` explicitly. 100 101It is also possible to disable KMSAN for a single file (e.g. main.o):: 102 103 KMSAN_SANITIZE_main.o := n 104 105or for the whole directory:: 106 107 KMSAN_SANITIZE := n 108 109in the Makefile. Think of this as applying ``__no_sanitize_memory`` to every 110function in the file or directory. Most users won't need KMSAN_SANITIZE, unless 111their code gets broken by KMSAN (e.g. runs at early boot time). 112 113Support 114======= 115 116In order for KMSAN to work the kernel must be built with Clang, which so far is 117the only compiler that has KMSAN support. The kernel instrumentation pass is 118based on the userspace `MemorySanitizer tool`_. 119 120The runtime library only supports x86_64 at the moment. 121 122How KMSAN works 123=============== 124 125KMSAN shadow memory 126------------------- 127 128KMSAN associates a metadata byte (also called shadow byte) with every byte of 129kernel memory. A bit in the shadow byte is set iff the corresponding bit of the 130kernel memory byte is uninitialized. Marking the memory uninitialized (i.e. 131setting its shadow bytes to ``0xff``) is called poisoning, marking it 132initialized (setting the shadow bytes to ``0x00``) is called unpoisoning. 133 134When a new variable is allocated on the stack, it is poisoned by default by 135instrumentation code inserted by the compiler (unless it is a stack variable 136that is immediately initialized). Any new heap allocation done without 137``__GFP_ZERO`` is also poisoned. 138 139Compiler instrumentation also tracks the shadow values as they are used along 140the code. When needed, instrumentation code invokes the runtime library in 141``mm/kmsan/`` to persist shadow values. 142 143The shadow value of a basic or compound type is an array of bytes of the same 144length. When a constant value is written into memory, that memory is unpoisoned. 145When a value is read from memory, its shadow memory is also obtained and 146propagated into all the operations which use that value. For every instruction 147that takes one or more values the compiler generates code that calculates the 148shadow of the result depending on those values and their shadows. 149 150Example:: 151 152 int a = 0xff; // i.e. 0x000000ff 153 int b; 154 int c = a | b; 155 156In this case the shadow of ``a`` is ``0``, shadow of ``b`` is ``0xffffffff``, 157shadow of ``c`` is ``0xffffff00``. This means that the upper three bytes of 158``c`` are uninitialized, while the lower byte is initialized. 159 160Origin tracking 161--------------- 162 163Every four bytes of kernel memory also have a so-called origin mapped to them. 164This origin describes the point in program execution at which the uninitialized 165value was created. Every origin is associated with either the full allocation 166stack (for heap-allocated memory), or the function containing the uninitialized 167variable (for locals). 168 169When an uninitialized variable is allocated on stack or heap, a new origin 170value is created, and that variable's origin is filled with that value. When a 171value is read from memory, its origin is also read and kept together with the 172shadow. For every instruction that takes one or more values, the origin of the 173result is one of the origins corresponding to any of the uninitialized inputs. 174If a poisoned value is written into memory, its origin is written to the 175corresponding storage as well. 176 177Example 1:: 178 179 int a = 42; 180 int b; 181 int c = a + b; 182 183In this case the origin of ``b`` is generated upon function entry, and is 184stored to the origin of ``c`` right before the addition result is written into 185memory. 186 187Several variables may share the same origin address, if they are stored in the 188same four-byte chunk. In this case every write to either variable updates the 189origin for all of them. We have to sacrifice precision in this case, because 190storing origins for individual bits (and even bytes) would be too costly. 191 192Example 2:: 193 194 int combine(short a, short b) { 195 union ret_t { 196 int i; 197 short s[2]; 198 } ret; 199 ret.s[0] = a; 200 ret.s[1] = b; 201 return ret.i; 202 } 203 204If ``a`` is initialized and ``b`` is not, the shadow of the result would be 2050xffff0000, and the origin of the result would be the origin of ``b``. 206``ret.s[0]`` would have the same origin, but it will never be used, because 207that variable is initialized. 208 209If both function arguments are uninitialized, only the origin of the second 210argument is preserved. 211 212Origin chaining 213~~~~~~~~~~~~~~~ 214 215To ease debugging, KMSAN creates a new origin for every store of an 216uninitialized value to memory. The new origin references both its creation stack 217and the previous origin the value had. This may cause increased memory 218consumption, so we limit the length of origin chains in the runtime. 219 220Clang instrumentation API 221------------------------- 222 223Clang instrumentation pass inserts calls to functions defined in 224``mm/kmsan/nstrumentation.c`` into the kernel code. 225 226Shadow manipulation 227~~~~~~~~~~~~~~~~~~~ 228 229For every memory access the compiler emits a call to a function that returns a 230pair of pointers to the shadow and origin addresses of the given memory:: 231 232 typedef struct { 233 void *shadow, *origin; 234 } shadow_origin_ptr_t 235 236 shadow_origin_ptr_t __msan_metadata_ptr_for_load_{1,2,4,8}(void *addr) 237 shadow_origin_ptr_t __msan_metadata_ptr_for_store_{1,2,4,8}(void *addr) 238 shadow_origin_ptr_t __msan_metadata_ptr_for_load_n(void *addr, uintptr_t size) 239 shadow_origin_ptr_t __msan_metadata_ptr_for_store_n(void *addr, uintptr_t size) 240 241The function name depends on the memory access size. 242 243The compiler makes sure that for every loaded value its shadow and origin 244values are read from memory. When a value is stored to memory, its shadow and 245origin are also stored using the metadata pointers. 246 247Handling locals 248~~~~~~~~~~~~~~~ 249 250A special function is used to create a new origin value for a local variable and 251set the origin of that variable to that value:: 252 253 void __msan_poison_alloca(void *addr, uintptr_t size, char *descr) 254 255Access to per-task data 256~~~~~~~~~~~~~~~~~~~~~~~ 257 258At the beginning of every instrumented function KMSAN inserts a call to 259``__msan_get_context_state()``:: 260 261 kmsan_context_state *__msan_get_context_state(void) 262 263``kmsan_context_state`` is declared in ``include/linux/kmsan.h``:: 264 265 struct kmsan_context_state { 266 char param_tls[KMSAN_PARAM_SIZE]; 267 char retval_tls[KMSAN_RETVAL_SIZE]; 268 char va_arg_tls[KMSAN_PARAM_SIZE]; 269 char va_arg_origin_tls[KMSAN_PARAM_SIZE]; 270 u64 va_arg_overflow_size_tls; 271 char param_origin_tls[KMSAN_PARAM_SIZE]; 272 depot_stack_handle_t retval_origin_tls; 273 }; 274 275This structure is used by KMSAN to pass parameter shadows and origins between 276instrumented functions (unless the parameters are checked immediately by 277``CONFIG_KMSAN_CHECK_PARAM_RETVAL``). 278 279Passing uninitialized values to functions 280~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 281 282Clang's MemorySanitizer instrumentation has an option, 283``-fsanitize-memory-param-retval``, which makes the compiler check function 284parameters passed by value, as well as function return values. 285 286The option is controlled by ``CONFIG_KMSAN_CHECK_PARAM_RETVAL``, which is 287enabled by default to let KMSAN report uninitialized values earlier. 288Please refer to the `LKML discussion`_ for more details. 289 290Because of the way the checks are implemented in LLVM (they are only applied to 291parameters marked as ``noundef``), not all parameters are guaranteed to be 292checked, so we cannot give up the metadata storage in ``kmsan_context_state``. 293 294String functions 295~~~~~~~~~~~~~~~~ 296 297The compiler replaces calls to ``memcpy()``/``memmove()``/``memset()`` with the 298following functions. These functions are also called when data structures are 299initialized or copied, making sure shadow and origin values are copied alongside 300with the data:: 301 302 void *__msan_memcpy(void *dst, void *src, uintptr_t n) 303 void *__msan_memmove(void *dst, void *src, uintptr_t n) 304 void *__msan_memset(void *dst, int c, uintptr_t n) 305 306Error reporting 307~~~~~~~~~~~~~~~ 308 309For each use of a value the compiler emits a shadow check that calls 310``__msan_warning()`` in the case that value is poisoned:: 311 312 void __msan_warning(u32 origin) 313 314``__msan_warning()`` causes KMSAN runtime to print an error report. 315 316Inline assembly instrumentation 317~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 318 319KMSAN instruments every inline assembly output with a call to:: 320 321 void __msan_instrument_asm_store(void *addr, uintptr_t size) 322 323, which unpoisons the memory region. 324 325This approach may mask certain errors, but it also helps to avoid a lot of 326false positives in bitwise operations, atomics etc. 327 328Sometimes the pointers passed into inline assembly do not point to valid memory. 329In such cases they are ignored at runtime. 330 331 332Runtime library 333--------------- 334 335The code is located in ``mm/kmsan/``. 336 337Per-task KMSAN state 338~~~~~~~~~~~~~~~~~~~~ 339 340Every task_struct has an associated KMSAN task state that holds the KMSAN 341context (see above) and a per-task flag disallowing KMSAN reports:: 342 343 struct kmsan_context { 344 ... 345 bool allow_reporting; 346 struct kmsan_context_state cstate; 347 ... 348 } 349 350 struct task_struct { 351 ... 352 struct kmsan_context kmsan; 353 ... 354 } 355 356KMSAN contexts 357~~~~~~~~~~~~~~ 358 359When running in a kernel task context, KMSAN uses ``current->kmsan.cstate`` to 360hold the metadata for function parameters and return values. 361 362But in the case the kernel is running in the interrupt, softirq or NMI context, 363where ``current`` is unavailable, KMSAN switches to per-cpu interrupt state:: 364 365 DEFINE_PER_CPU(struct kmsan_ctx, kmsan_percpu_ctx); 366 367Metadata allocation 368~~~~~~~~~~~~~~~~~~~ 369 370There are several places in the kernel for which the metadata is stored. 371 3721. Each ``struct page`` instance contains two pointers to its shadow and 373origin pages:: 374 375 struct page { 376 ... 377 struct page *shadow, *origin; 378 ... 379 }; 380 381At boot-time, the kernel allocates shadow and origin pages for every available 382kernel page. This is done quite late, when the kernel address space is already 383fragmented, so normal data pages may arbitrarily interleave with the metadata 384pages. 385 386This means that in general for two contiguous memory pages their shadow/origin 387pages may not be contiguous. Consequently, if a memory access crosses the 388boundary of a memory block, accesses to shadow/origin memory may potentially 389corrupt other pages or read incorrect values from them. 390 391In practice, contiguous memory pages returned by the same ``alloc_pages()`` 392call will have contiguous metadata, whereas if these pages belong to two 393different allocations their metadata pages can be fragmented. 394 395For the kernel data (``.data``, ``.bss`` etc.) and percpu memory regions 396there also are no guarantees on metadata contiguity. 397 398In the case ``__msan_metadata_ptr_for_XXX_YYY()`` hits the border between two 399pages with non-contiguous metadata, it returns pointers to fake shadow/origin regions:: 400 401 char dummy_load_page[PAGE_SIZE] __attribute__((aligned(PAGE_SIZE))); 402 char dummy_store_page[PAGE_SIZE] __attribute__((aligned(PAGE_SIZE))); 403 404``dummy_load_page`` is zero-initialized, so reads from it always yield zeroes. 405All stores to ``dummy_store_page`` are ignored. 406 4072. For vmalloc memory and modules, there is a direct mapping between the memory 408range, its shadow and origin. KMSAN reduces the vmalloc area by 3/4, making only 409the first quarter available to ``vmalloc()``. The second quarter of the vmalloc 410area contains shadow memory for the first quarter, the third one holds the 411origins. A small part of the fourth quarter contains shadow and origins for the 412kernel modules. Please refer to ``arch/x86/include/asm/pgtable_64_types.h`` for 413more details. 414 415When an array of pages is mapped into a contiguous virtual memory space, their 416shadow and origin pages are similarly mapped into contiguous regions. 417 418References 419========== 420 421E. Stepanov, K. Serebryany. `MemorySanitizer: fast detector of uninitialized 422memory use in C++ 423<https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/43308.pdf>`_. 424In Proceedings of CGO 2015. 425 426.. _MemorySanitizer tool: https://clang.llvm.org/docs/MemorySanitizer.html 427.. _LLVM documentation: https://llvm.org/docs/GettingStarted.html 428.. _LKML discussion: https://lore.kernel.org/all/20220614144853.3693273-1-glider@google.com/ 429