Add KernelMemorySanitizer infrastructure

KernelMemorySanitizer (KMSAN) is a detector of errors related to uses of uninitialized memory. It relies on compile-time Clang instrumentation (similar to MSan in the userspace:
https://clang.llvm.org/docs/MemorySanitizer.html)
and tracks the state of every bit of kernel memory, being able to report an error if uninitialized value is used in a condition, dereferenced or copied to userspace, USB or network.

KMSAN has reported more than 200 bugs in the past two years, most of them with the help of syzkaller (http://syzkaller.appspot.com).

The proposed patchset contains KMSAN runtime implementation together with small changes to other subsystems needed to make KMSAN work. The latter changes fall into several categories:
- nice-to-have features that are independent from KMSAN but simplify its implementation (stackdepot changes, CONFIG_GENERIC_CSUM etc.);
- Kconfig changes that prohibit options incompatible with KMSAN;
- calls to KMSAN runtime functions that help KMSAN do the bookkeeping (e.g. tell it to allocate, copy or delete the metadata);
- calls to KMSAN runtime functions that tell KMSAN to check memory escaping the kernel for uninitialized values. These are required to increase the number of true positive error reports;
- calls to runtime functions that tell KMSAN to ignore certain memory ranges to avoid false negative reports. Most certainly there can be better ways to deal with every such report.

This patchset allows one to boot and run a defconfig+KMSAN kernel on a QEMU without known major false positives. It however doesn't guarantee there are no false positives in drivers of certain devices or less tested subsystems, although KMSAN is actively tested on syzbot with quite a rich config.

One may find it handy to review these patches in Gerrit:
https://linux-review.googlesource.com/c/linux/kernel/git/torvalds/linux/+/1081
I've ensured the Change-Id: tags stay away from commit descriptions.

The patchset was generated relative to mmotm
(v5.6-rc7-mmots-2020-03-23-22-35).

Several points worth a separate discussion:
1. Right now KMSAN assumes that contiguous physical pages cannot be accessed as such, unless they were allocated together by a single alloc_pages() call. Some kernel code however does so, which may break under KMSAN. Two possible solutions to this problem are:
A. Allocate shadow and origin pages at fixed offset from the kernel page.
This is what we already do for vmalloc, but not for page_alloc(), as it turned out to be quite hard.
Ideas on how to implement this approach are still welcome, because it'll simplify the rest of the KMSAN runtime a lot.
B. Make all accesses touching non-contiguous pages access dummy shadow
pages instead, so that such accesses don't produce any uninitialized values.
This is quite controversial, as it may prevent true positives from being reported.

2. checkpatch.pl complains a lot about the use of BUG_ON in KMSAN source. I don't have a strong opinion on this, but KMSAN is a debugging tool, so any runtime invariant violation in it renders the tool useless. Therefore it doesn't make much sense to not terminate after a bug in KMSAN.

There has been a suggestion to disable KMSAN gracefully instead of panicking. The downside of doing so is that users may gain a false sense of memory safety if they don't notice that the tool has shut down.

3. objtool complains a lot about calls to KMSAN runtime with UACCESS enabled.
None of these functions is expected to touch userspace memory, but they can be called in the uaccess context, as the compiler adds them to every memory access.
Turns out it's not enough to just whitelist KMSAN interface functions in tools/objtool/check.c, as they are viral: after whitelisting them I get warnings about their callees.
On the other hand, it's unacceptable to call user_access_save()/user_access_restore() inside these functions, as this slows down the whole runtime heavily.
Perhaps this problem can be solved on objtool side, as the mentioned reports aren't errors per se.

Alexander Potapenko (38):
stackdepot: reserve 5 extra bits in depot_stack_handle_t
kmsan: add ReST documentation
kmsan: gfp: introduce __GFP_NO_KMSAN_SHADOW
kmsan: introduce __no_sanitize_memory and __SANITIZE_MEMORY__
kmsan: reduce vmalloc space
kmsan: add KMSAN runtime core
kmsan: KMSAN compiler API implementation
kmsan: add KMSAN hooks for kernel subsystems
kmsan: stackdepot: don't allocate KMSAN metadata for stackdepot
kmsan: define READ_ONCE_NOCHECK()
kmsan: make READ_ONCE_TASK_STACK() return initialized values
kmsan: x86: sync metadata pages on page fault
kmsan: add tests for KMSAN
crypto: kmsan: disable accelerated configs under KMSAN
kmsan: x86: disable UNWINDER_ORC under KMSAN
kmsan: x86/asm: softirq: add KMSAN IRQ entry hooks
kmsan: disable KMSAN instrumentation for certain kernel parts
kmsan: mm: call KMSAN hooks from SLUB code
kmsan: mm: maintain KMSAN metadata for page operations
kmsan: handle memory sent to/from USB
kmsan: handle task creation and exiting
kmsan: net: check the value of skb before sending it to the network
kmsan: printk: treat the result of vscnprintf() as initialized
kmsan: disable instrumentation of certain functions
kmsan: unpoison |tlb| in arch_tlb_gather_mmu()
kmsan: use __msan_ string functions where possible.
kmsan: hooks for copy_to_user() and friends
kmsan: init: call KMSAN initialization routines
kmsan: enable KMSAN builds
kmsan: handle /dev/[u]random
kmsan: virtio: check/unpoison scatterlist in vring_map_one_sg()
kmsan: disable strscpy() optimization under KMSAN
kmsan: add iomap support
kmsan: dma: unpoison memory mapped by dma_direct_map_page()
kmsan: disable physical page merging in biovec
x86: kasan: kmsan: support CONFIG_GENERIC_CSUM on x86, enable it for
KASAN/KMSAN
kmsan: x86/uprobes: unpoison regs in arch_uprobe_exception_notify()
kmsan: block: skip bio block merging logic for KMSAN

To: Alexander Potapenko <[email protected]>
Cc: Alexander Viro <[email protected]>
Cc: Andreas Dilger <[email protected]>
Cc: Andrew Morton <[email protected]>
Cc: Andrey Konovalov <[email protected]>
Cc: Andrey Ryabinin <[email protected]>
Cc: Andy Lutomirski <[email protected]>
Cc: Ard Biesheuvel <[email protected]>
Cc: Arnd Bergmann <[email protected]>
Cc: Christoph Hellwig <[email protected]>
Cc: Christoph Hellwig <[email protected]>
Cc: Darrick J. Wong <[email protected]>
Cc: "David S. Miller" <[email protected]>
Cc: Dmitry Torokhov <[email protected]>
Cc: Dmitry Vyukov <[email protected]>
Cc: Eric Biggers <[email protected]>
Cc: Eric Dumazet <[email protected]>
Cc: Eric Van Hensbergen <[email protected]>
Cc: Greg Kroah-Hartman <[email protected]>
Cc: Harry Wentland <[email protected]>
Cc: Herbert Xu <[email protected]>
Cc: Ilya Leoshkevich <[email protected]>
Cc: Ingo Molnar <[email protected]>
Cc: Jason Wang <[email protected]>
Cc: Jens Axboe <[email protected]>
Cc: Marek Szyprowski <[email protected]>
Cc: Marco Elver <[email protected]>
Cc: Mark Rutland <[email protected]>
Cc: Martin K. Petersen <[email protected]>
Cc: Martin Schwidefsky <[email protected]>
Cc: Matthew Wilcox <[email protected]>
Cc: "Michael S. Tsirkin" <[email protected]>
Cc: Michal Simek <[email protected]>
Cc: Petr Mladek <[email protected]>
Cc: Qian Cai <[email protected]>
Cc: Randy Dunlap <[email protected]>
Cc: Robin Murphy <[email protected]>
Cc: Sergey Senozhatsky <[email protected]>
Cc: Steven Rostedt <[email protected]>
Cc: Takashi Iwai <[email protected]>
Cc: "Theodore Ts'o" <[email protected]>
Cc: Thomas Gleixner <[email protected]>
Cc: Vasily Gorbik <[email protected]>
Cc: Vegard Nossum <[email protected]>
Cc: Wolfram Sang <[email protected]>
Cc: [email protected]

 Documentation/dev-tools/index.rst             |   1 +
 Documentation/dev-tools/kmsan.rst             | 424 ++++++++++++++
 Makefile                                      |   3 +-
 arch/x86/Kconfig                              |   5 +
 arch/x86/Kconfig.debug                        |   3 +
 arch/x86/boot/Makefile                        |   1 +
 arch/x86/boot/compressed/Makefile             |   2 +
 arch/x86/boot/compressed/misc.h               |   1 +
 arch/x86/entry/common.c                       |   2 +
 arch/x86/entry/entry_64.S                     |  16 +
 arch/x86/entry/vdso/Makefile                  |   3 +
 arch/x86/include/asm/checksum.h               |  10 +-
 arch/x86/include/asm/irq_regs.h               |   2 +
 arch/x86/include/asm/kmsan.h                  |  93 +++
 arch/x86/include/asm/page_64.h                |  13 +
 arch/x86/include/asm/pgtable_64_types.h       |  15 +
 arch/x86/include/asm/string_64.h              |  23 +-
 arch/x86/include/asm/syscall_wrapper.h        |   2 +
 arch/x86/include/asm/uaccess.h                |  10 +
 arch/x86/include/asm/unwind.h                 |  10 +-
 arch/x86/kernel/Makefile                      |   4 +
 arch/x86/kernel/apic/apic.c                   |   3 +
 arch/x86/kernel/cpu/Makefile                  |   1 +
 arch/x86/kernel/dumpstack_64.c                |   5 +
 arch/x86/kernel/process_64.c                  |   5 +
 arch/x86/kernel/traps.c                       |  13 +-
 arch/x86/kernel/uprobes.c                     |   7 +-
 arch/x86/lib/Makefile                         |   2 +
 arch/x86/mm/Makefile                          |   3 +
 arch/x86/mm/fault.c                           |  20 +
 arch/x86/mm/ioremap.c                         |   3 +
 arch/x86/realmode/rm/Makefile                 |   1 +
 block/bio.c                                   |   2 +
 block/blk.h                                   |   7 +
 crypto/Kconfig                                |  30 +
 drivers/char/random.c                         |   6 +
 drivers/firmware/efi/libstub/Makefile         |   1 +
 .../firmware/efi/libstub/efi-stub-helper.c    |   5 +
 drivers/firmware/efi/libstub/tpm.c            |   5 +
 drivers/usb/core/urb.c                        |   2 +
 drivers/virtio/virtio_ring.c                  |  10 +-
 include/asm-generic/cacheflush.h              |   7 +-
 include/asm-generic/uaccess.h                 |  12 +-
 include/linux/compiler-clang.h                |   7 +
 include/linux/compiler-gcc.h                  |   5 +
 include/linux/compiler.h                      |  14 +-
 include/linux/gfp.h                           |   4 +-
 include/linux/highmem.h                       |   3 +
 include/linux/kmsan-checks.h                  | 127 ++++
 include/linux/kmsan.h                         | 335 +++++++++++
 include/linux/mm_types.h                      |   9 +
 include/linux/sched.h                         |   5 +
 include/linux/stackdepot.h                    |   8 +
 include/linux/string.h                        |   2 +
 include/linux/uaccess.h                       |  34 +-
 init/main.c                                   |   3 +
 kernel/Makefile                               |   1 +
 kernel/dma/direct.c                           |   1 +
 kernel/exit.c                                 |   2 +
 kernel/fork.c                                 |   2 +
 kernel/kthread.c                              |   2 +
 kernel/locking/Makefile                       |   4 +
 kernel/printk/printk.c                        |   6 +
 kernel/sched/core.c                           |  22 +
 kernel/softirq.c                              |   5 +
 lib/Kconfig.debug                             |   2 +
 lib/Kconfig.kmsan                             |  22 +
 lib/Makefile                                  |   3 +
 lib/iomap.c                                   |  40 ++
 lib/ioremap.c                                 |   5 +
 lib/iov_iter.c                                |  14 +-
 lib/stackdepot.c                              |  26 +-
 lib/string.c                                  |   8 +
 lib/test_kmsan.c                              | 229 ++++++++
 lib/usercopy.c                                |   8 +-
 mm/Makefile                                   |   1 +
 mm/gup.c                                      |   3 +
 mm/kmsan/Makefile                             |  11 +
 mm/kmsan/kmsan.c                              | 547 ++++++++++++++++++
 mm/kmsan/kmsan.h                              | 161 ++++++
 mm/kmsan/kmsan_entry.c                        |  38 ++
 mm/kmsan/kmsan_hooks.c                        | 416 +++++++++++++
 mm/kmsan/kmsan_init.c                         |  79 +++
 mm/kmsan/kmsan_instr.c                        | 229 ++++++++
 mm/kmsan/kmsan_report.c                       | 143 +++++
 mm/kmsan/kmsan_shadow.c                       | 456 +++++++++++++++
 mm/kmsan/kmsan_shadow.h                       |  30 +
 mm/memory.c                                   |   2 +
 mm/mmu_gather.c                               |  10 +
 mm/page_alloc.c                               |  17 +
 mm/slub.c                                     |  29 +-
 mm/vmalloc.c                                  |  24 +-
 net/sched/sch_generic.c                       |   2 +
 scripts/Makefile.kmsan                        |  12 +
 scripts/Makefile.lib                          |   6 +
 95 files changed, 3926 insertions(+), 41 deletions(-)
 create mode 100644 Documentation/dev-tools/kmsan.rst
 create mode 100644 arch/x86/include/asm/kmsan.h
 create mode 100644 include/linux/kmsan-checks.h
 create mode 100644 include/linux/kmsan.h
 create mode 100644 lib/Kconfig.kmsan
 create mode 100644 lib/test_kmsan.c
 create mode 100644 mm/kmsan/Makefile
 create mode 100644 mm/kmsan/kmsan.c
 create mode 100644 mm/kmsan/kmsan.h
 create mode 100644 mm/kmsan/kmsan_entry.c
 create mode 100644 mm/kmsan/kmsan_hooks.c
 create mode 100644 mm/kmsan/kmsan_init.c
 create mode 100644 mm/kmsan/kmsan_instr.c
 create mode 100644 mm/kmsan/kmsan_report.c
 create mode 100644 mm/kmsan/kmsan_shadow.c
 create mode 100644 mm/kmsan/kmsan_shadow.h
 create mode 100644 scripts/Makefile.kmsan

2.25.1.696.g5e7596f4ac-goog