1 .. SPDX-License-Identifier: GPL-2.0
2 .. Copyright (C) 2022, Google LLC.
3
4 ===============================
5 Kernel Memory Sanitizer (KMSAN)
6 ===============================
7
8 KMSAN is a dynamic error detector aimed at fin
9 values. It is based on compiler instrumentatio
10 userspace `MemorySanitizer tool`_.
11
12 An important note is that KMSAN is not intende
13 drastically increases kernel memory footprint
14
15 Usage
16 =====
17
18 Building the kernel
19 -------------------
20
21 In order to build a kernel with KMSAN you will
22 Please refer to `LLVM documentation`_ for the
23
24 Now configure and build the kernel with CONFIG
25
26 Example report
27 --------------
28
29 Here is an example of a KMSAN report::
30
31 ============================================
32 BUG: KMSAN: uninit-value in test_uninit_kmsa
33 test_uninit_kmsan_check_memory+0x1be/0x380
34 kunit_run_case_internal lib/kunit/test.c:33
35 kunit_try_run_case+0x206/0x420 lib/kunit/te
36 kunit_generic_run_threadfn_adapter+0x6d/0xc
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/k
42 test_uninit_kmsan_check_memory+0x1a2/0x380
43 kunit_run_case_internal lib/kunit/test.c:33
44 kunit_try_run_case+0x206/0x420 lib/kunit/te
45 kunit_generic_run_threadfn_adapter+0x6d/0xc
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/k
51 test_uninit_kmsan_check_memory+0x1a2/0x380
52
53 Bytes 4-7 of 8 are uninitialized
54 Memory access of size 8 starts at ffff888083
55
56 CPU: 0 PID: 6731 Comm: kunit_try_catch Taint
57 Hardware name: QEMU Standard PC (i440FX + PI
58 ============================================
59
60 The report says that the local variable ``unin
61 ``do_uninit_local_array()``. The third stack t
62 where this variable was created.
63
64 The first stack trace shows where the uninit v
65 ``test_uninit_kmsan_check_memory()``). The too
66 uninitialized in the local variable, as well a
67 copied to another memory location before use.
68
69 A use of uninitialized value ``v`` is reported
70
71 - in a condition, e.g. ``if (v) { ... }``;
72 - in an indexing or pointer dereferencing, e.
73 - when it is copied to userspace or hardware,
74 - when it is passed as an argument to a funct
75 ``CONFIG_KMSAN_CHECK_PARAM_RETVAL`` is enab
76
77 The mentioned cases (apart from copying data t
78 a security issue) are considered undefined beh
79 of view.
80
81 Disabling the instrumentation
82 -----------------------------
83
84 A function can be marked with ``__no_kmsan_che
85 ignore uninitialized values in that function a
86 As a result, the user will not get KMSAN repor
87
88 Another function attribute supported by KMSAN
89 Applying this attribute to a function will res
90 it, which can be helpful if we do not want the
91 low-level code (e.g. that marked with ``noinst
92 ``__no_sanitize_memory``).
93
94 This however comes at a cost: stack allocation
95 incorrect shadow/origin values, likely leading
96 called from non-instrumented code may also rec
97 parameters.
98
99 As a rule of thumb, avoid using ``__no_sanitiz
100
101 It is also possible to disable KMSAN for a sin
102
103 KMSAN_SANITIZE_main.o := n
104
105 or for the whole directory::
106
107 KMSAN_SANITIZE := n
108
109 in the Makefile. Think of this as applying ``_
110 function in the file or directory. Most users
111 their code gets broken by KMSAN (e.g. runs at
112
113 KMSAN checks can also be temporarily disabled
114 ``kmsan_disable_current()`` and ``kmsan_enable
115 ``kmsan_enable_current()`` call must be preced
116 ``kmsan_disable_current()`` call; these call p
117 be careful with these calls, keeping the regio
118 ways to disable instrumentation, where possibl
119
120 Support
121 =======
122
123 In order for KMSAN to work the kernel must be
124 the only compiler that has KMSAN support. The
125 based on the userspace `MemorySanitizer tool`_
126
127 The runtime library only supports x86_64 at th
128
129 How KMSAN works
130 ===============
131
132 KMSAN shadow memory
133 -------------------
134
135 KMSAN associates a metadata byte (also called
136 kernel memory. A bit in the shadow byte is set
137 kernel memory byte is uninitialized. Marking t
138 setting its shadow bytes to ``0xff``) is calle
139 initialized (setting the shadow bytes to ``0x0
140
141 When a new variable is allocated on the stack,
142 instrumentation code inserted by the compiler
143 that is immediately initialized). Any new heap
144 ``__GFP_ZERO`` is also poisoned.
145
146 Compiler instrumentation also tracks the shado
147 the code. When needed, instrumentation code in
148 ``mm/kmsan/`` to persist shadow values.
149
150 The shadow value of a basic or compound type i
151 length. When a constant value is written into
152 When a value is read from memory, its shadow m
153 propagated into all the operations which use t
154 that takes one or more values the compiler gen
155 shadow of the result depending on those values
156
157 Example::
158
159 int a = 0xff; // i.e. 0x000000ff
160 int b;
161 int c = a | b;
162
163 In this case the shadow of ``a`` is ``0``, sha
164 shadow of ``c`` is ``0xffffff00``. This means
165 ``c`` are uninitialized, while the lower byte
166
167 Origin tracking
168 ---------------
169
170 Every four bytes of kernel memory also have a
171 This origin describes the point in program exe
172 value was created. Every origin is associated
173 stack (for heap-allocated memory), or the func
174 variable (for locals).
175
176 When an uninitialized variable is allocated on
177 value is created, and that variable's origin i
178 value is read from memory, its origin is also
179 shadow. For every instruction that takes one o
180 result is one of the origins corresponding to
181 If a poisoned value is written into memory, it
182 corresponding storage as well.
183
184 Example 1::
185
186 int a = 42;
187 int b;
188 int c = a + b;
189
190 In this case the origin of ``b`` is generated
191 stored to the origin of ``c`` right before the
192 memory.
193
194 Several variables may share the same origin ad
195 same four-byte chunk. In this case every write
196 origin for all of them. We have to sacrifice p
197 storing origins for individual bits (and even
198
199 Example 2::
200
201 int combine(short a, short b) {
202 union ret_t {
203 int i;
204 short s[2];
205 } ret;
206 ret.s[0] = a;
207 ret.s[1] = b;
208 return ret.i;
209 }
210
211 If ``a`` is initialized and ``b`` is not, the
212 0xffff0000, and the origin of the result would
213 ``ret.s[0]`` would have the same origin, but i
214 that variable is initialized.
215
216 If both function arguments are uninitialized,
217 argument is preserved.
218
219 Origin chaining
220 ~~~~~~~~~~~~~~~
221
222 To ease debugging, KMSAN creates a new origin
223 uninitialized value to memory. The new origin
224 and the previous origin the value had. This ma
225 consumption, so we limit the length of origin
226
227 Clang instrumentation API
228 -------------------------
229
230 Clang instrumentation pass inserts calls to fu
231 ``mm/kmsan/nstrumentation.c`` into the kernel
232
233 Shadow manipulation
234 ~~~~~~~~~~~~~~~~~~~
235
236 For every memory access the compiler emits a c
237 pair of pointers to the shadow and origin addr
238
239 typedef struct {
240 void *shadow, *origin;
241 } shadow_origin_ptr_t
242
243 shadow_origin_ptr_t __msan_metadata_ptr_for_
244 shadow_origin_ptr_t __msan_metadata_ptr_for_
245 shadow_origin_ptr_t __msan_metadata_ptr_for_
246 shadow_origin_ptr_t __msan_metadata_ptr_for_
247
248 The function name depends on the memory access
249
250 The compiler makes sure that for every loaded
251 values are read from memory. When a value is s
252 origin are also stored using the metadata poin
253
254 Handling locals
255 ~~~~~~~~~~~~~~~
256
257 A special function is used to create a new ori
258 set the origin of that variable to that value:
259
260 void __msan_poison_alloca(void *addr, uintpt
261
262 Access to per-task data
263 ~~~~~~~~~~~~~~~~~~~~~~~
264
265 At the beginning of every instrumented functio
266 ``__msan_get_context_state()``::
267
268 kmsan_context_state *__msan_get_context_stat
269
270 ``kmsan_context_state`` is declared in ``inclu
271
272 struct kmsan_context_state {
273 char param_tls[KMSAN_PARAM_SIZE];
274 char retval_tls[KMSAN_RETVAL_SIZE];
275 char va_arg_tls[KMSAN_PARAM_SIZE];
276 char va_arg_origin_tls[KMSAN_PARAM_SIZE];
277 u64 va_arg_overflow_size_tls;
278 char param_origin_tls[KMSAN_PARAM_SIZE];
279 depot_stack_handle_t retval_origin_tls;
280 };
281
282 This structure is used by KMSAN to pass parame
283 instrumented functions (unless the parameters
284 ``CONFIG_KMSAN_CHECK_PARAM_RETVAL``).
285
286 Passing uninitialized values to functions
287 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
288
289 Clang's MemorySanitizer instrumentation has an
290 ``-fsanitize-memory-param-retval``, which make
291 parameters passed by value, as well as functio
292
293 The option is controlled by ``CONFIG_KMSAN_CHE
294 enabled by default to let KMSAN report uniniti
295 Please refer to the `LKML discussion`_ for mor
296
297 Because of the way the checks are implemented
298 parameters marked as ``noundef``), not all par
299 checked, so we cannot give up the metadata sto
300
301 String functions
302 ~~~~~~~~~~~~~~~~
303
304 The compiler replaces calls to ``memcpy()``/``
305 following functions. These functions are also
306 initialized or copied, making sure shadow and
307 with the data::
308
309 void *__msan_memcpy(void *dst, void *src, ui
310 void *__msan_memmove(void *dst, void *src, u
311 void *__msan_memset(void *dst, int c, uintpt
312
313 Error reporting
314 ~~~~~~~~~~~~~~~
315
316 For each use of a value the compiler emits a s
317 ``__msan_warning()`` in the case that value is
318
319 void __msan_warning(u32 origin)
320
321 ``__msan_warning()`` causes KMSAN runtime to p
322
323 Inline assembly instrumentation
324 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
325
326 KMSAN instruments every inline assembly output
327
328 void __msan_instrument_asm_store(void *addr,
329
330 , which unpoisons the memory region.
331
332 This approach may mask certain errors, but it
333 false positives in bitwise operations, atomics
334
335 Sometimes the pointers passed into inline asse
336 In such cases they are ignored at runtime.
337
338
339 Runtime library
340 ---------------
341
342 The code is located in ``mm/kmsan/``.
343
344 Per-task KMSAN state
345 ~~~~~~~~~~~~~~~~~~~~
346
347 Every task_struct has an associated KMSAN task
348 context (see above) and a per-task counter dis
349
350 struct kmsan_context {
351 ...
352 unsigned int depth;
353 struct kmsan_context_state cstate;
354 ...
355 }
356
357 struct task_struct {
358 ...
359 struct kmsan_context kmsan;
360 ...
361 }
362
363 KMSAN contexts
364 ~~~~~~~~~~~~~~
365
366 When running in a kernel task context, KMSAN u
367 hold the metadata for function parameters and
368
369 But in the case the kernel is running in the i
370 where ``current`` is unavailable, KMSAN switch
371
372 DEFINE_PER_CPU(struct kmsan_ctx, kmsan_percp
373
374 Metadata allocation
375 ~~~~~~~~~~~~~~~~~~~
376
377 There are several places in the kernel for whi
378
379 1. Each ``struct page`` instance contains two
380 origin pages::
381
382 struct page {
383 ...
384 struct page *shadow, *origin;
385 ...
386 };
387
388 At boot-time, the kernel allocates shadow and
389 kernel page. This is done quite late, when the
390 fragmented, so normal data pages may arbitrari
391 pages.
392
393 This means that in general for two contiguous
394 pages may not be contiguous. Consequently, if
395 boundary of a memory block, accesses to shadow
396 corrupt other pages or read incorrect values f
397
398 In practice, contiguous memory pages returned
399 call will have contiguous metadata, whereas if
400 different allocations their metadata pages can
401
402 For the kernel data (``.data``, ``.bss`` etc.)
403 there also are no guarantees on metadata conti
404
405 In the case ``__msan_metadata_ptr_for_XXX_YYY(
406 pages with non-contiguous metadata, it returns
407
408 char dummy_load_page[PAGE_SIZE] __attribute_
409 char dummy_store_page[PAGE_SIZE] __attribute
410
411 ``dummy_load_page`` is zero-initialized, so re
412 All stores to ``dummy_store_page`` are ignored
413
414 2. For vmalloc memory and modules, there is a
415 range, its shadow and origin. KMSAN reduces th
416 the first quarter available to ``vmalloc()``.
417 area contains shadow memory for the first quar
418 origins. A small part of the fourth quarter co
419 kernel modules. Please refer to ``arch/x86/inc
420 more details.
421
422 When an array of pages is mapped into a contig
423 shadow and origin pages are similarly mapped i
424
425 References
426 ==========
427
428 E. Stepanov, K. Serebryany. `MemorySanitizer:
429 memory use in C++
430 <https://static.googleusercontent.com/media/re
431 In Proceedings of CGO 2015.
432
433 .. _MemorySanitizer tool: https://clang.llvm.o
434 .. _LLVM documentation: https://llvm.org/docs/
435 .. _LKML discussion: https://lore.kernel.org/a
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.