code:
.. highlight:: none

Debugging kernel and modules via gdb
====================================

The kernel debugger kgdb, hypervisors like QEMU or JTAG-based hardware
interfaces allow to debug the Linux kernel and its modules during runtime
using gdb. Gdb comes with a powerful scripting interface for python. The
kernel provides a collection of helper scripts that can simplify typical
kernel debugging steps. This is a short tutorial about how to enable and use
them. It focuses on QEMU/KVM virtual machines as target, but the examples can
be transferred to the other gdb stubs as well.

Requirements
------------

- gdb 7.2+ (recommended: 7.4+) with python support enabled (typically true
  for distributions)

Setup
-----

- Create a virtual Linux machine for QEMU/KVM (see www.linux-kvm.org and
  www.qemu.org for more details). For cross-development,
  https://landley.net/aboriginal/bin keeps a pool of machine images and
  toolchains that can be helpful to start from.

- Build the kernel with CONFIG_GDB_SCRIPTS enabled, but leave
  CONFIG_DEBUG_INFO_REDUCED off. If your architecture supports
  CONFIG_FRAME_POINTER, keep it enabled.

- Install that kernel on the guest, turn off KASLR if necessary by adding
  "nokaslr" to the kernel command line.
  Alternatively, QEMU allows to boot the kernel directly using -kernel,
  -append, -initrd command line switches. This is generally only useful if
  you do not depend on modules. See QEMU documentation for more details on
  this mode. In this case, you should build the kernel with
  CONFIG_RANDOMIZE_BASE disabled if the architecture supports KASLR.

- Enable the gdb stub of QEMU/KVM, either

    - at VM startup time by appending "-s" to the QEMU command line

  or

    - during runtime by issuing "gdbserver" from the QEMU monitor
      console

- cd /path/to/linux-build

- Start gdb: gdb vmlinux

  Note: Some distros may restrict auto-loading of gdb scripts to known safe
  directories. In case gdb reports to refuse loading vmlinux-gdb.py, add::

    add-auto-load-safe-path /path/to/linux-build

  to ~/.gdbinit. See gdb help for more details.

- Attach to the booted guest::

    (gdb) target remote :1234

Examples of using the Linux-provided gdb helpers
------------------------------------------------

- Load module (and main kernel) symbols::

    (gdb) lx-symbols
    loading vmlinux
    scanning for modules in /home/user/linux/build
    loading @0xffffffffa0020000: /home/user/linux/build/net/netfilter/xt_tcpudp.ko
    loading @0xffffffffa0016000: /home/user/linux/build/net/netfilter/xt_pkttype.ko
    loading @0xffffffffa0002000: /home/user/linux/build/net/netfilter/xt_limit.ko
    loading @0xffffffffa00ca000: /home/user/linux/build/net/packet/af_packet.ko
    loading @0xffffffffa003c000: /home/user/linux/build/fs/fuse/fuse.ko
    ...
    loading @0xffffffffa0000000: /home/user/linux/build/drivers/ata/ata_generic.ko

- Set a breakpoint on some not yet loaded module function, e.g.::

    (gdb) b btrfs_init_sysfs
    Function "btrfs_init_sysfs" not defined.
    Make breakpoint pending on future shared library load? (y or [n]) y
    Breakpoint 1 (btrfs_init_sysfs) pending.

- Continue the target::

    (gdb) c

- Load the module on the target and watch the symbols being loaded as well as
  the breakpoint hit::

    loading @0xffffffffa0034000: /home/user/linux/build/lib/libcrc32c.ko
    loading @0xffffffffa0050000: /home/user/linux/build/lib/lzo/lzo_compress.ko
    loading @0xffffffffa006e000: /home/user/linux/build/lib/zlib_deflate/zlib_deflate.ko
    loading @0xffffffffa01b1000: /home/user/linux/build/fs/btrfs/btrfs.ko

    Breakpoint 1, btrfs_init_sysfs () at /home/user/linux/fs/btrfs/sysfs.c:36
    36              btrfs_kset = kset_create_and_add("btrfs", NULL, fs_kobj);

- Dump the log buffer of the target kernel::

    (gdb) lx-dmesg
    [     0.000000] Initializing cgroup subsys cpuset
    [     0.000000] Initializing cgroup subsys cpu
    [     0.000000] Linux version 3.8.0-rc4-dbg+ (...
    [     0.000000] Command line: root=/dev/sda2 resume=/dev/sda1 vga=0x314
    [     0.000000] e820: BIOS-provided physical RAM map:
    [     0.000000] BIOS-e820: [mem 0x0000000000000000-0x000000000009fbff] usable
    [     0.000000] BIOS-e820: [mem 0x000000000009fc00-0x000000000009ffff] reserved
    ....

- Examine fields of the current task struct(supported by x86 and arm64 only)::

    (gdb) p $lx_current().pid
    $1 = 4998
    (gdb) p $lx_current().comm
    $2 = "modprobe\000\000\000\000\000\000\000"

- Make use of the per-cpu function for the current or a specified CPU::

    (gdb) p $lx_per_cpu("runqueues").nr_running
    $3 = 1
    (gdb) p $lx_per_cpu("runqueues", 2).nr_running
    $4 = 0

- Dig into hrtimers using the container_of helper::

    (gdb) set $next = $lx_per_cpu("hrtimer_bases").clock_base[0].active.next
    (gdb) p *$container_of($next, "struct hrtimer", "node")
    $5 = {
      node = {
        node = {
          __rb_parent_color = 18446612133355256072,
          rb_right = 0x0 <irq_stack_union>,
          rb_left = 0x0 <irq_stack_union>
        },
        expires = {
          tv64 = 1835268000000
        }
      },
      _softexpires = {
        tv64 = 1835268000000
      },
      function = 0xffffffff81078232 <tick_sched_timer>,
      base = 0xffff88003fd0d6f0,
      state = 1,
      start_pid = 0,
      start_site = 0xffffffff81055c1f <hrtimer_start_range_ns+20>,
      start_comm = "swapper/2\000\000\000\000\000\000"
    }

List of commands and functions
------------------------------

The number of commands and convenience functions may evolve over the time,
this is just a snapshot of the initial version::

 (gdb) apropos lx
 function lx_current -- Return current task
 function lx_module -- Find module by name and return the module variable
 function lx_per_cpu -- Return per-cpu variable
 function lx_task_by_pid -- Find Linux task by PID and return the task_struct variable
 function lx_thread_info -- Calculate Linux thread_info from task variable
 lx-dmesg -- Print Linux kernel log buffer
 lx-lsmod -- List currently loaded modules
 lx-symbols -- (Re-)load symbols of Linux kernel and currently loaded modules

Detailed help can be obtained via "help <command-name>" for commands and "help
function <function-name>" for convenience functions.


code:
================================
Development tools for the kernel
================================

This document is a collection of documents about development tools that can
be used to work on the kernel. For now, the documents have been pulled
together without any significant effort to integrate them into a coherent
whole; patches welcome!

A brief overview of testing-specific tools can be found in
Documentation/dev-tools/testing-overview.rst

.. class:: toc-title

	   Table of contents

.. toctree::
   :maxdepth: 2

   testing-overview
   checkpatch
   coccinelle
   sparse
   kcov
   gcov
   kasan
   kmsan
   ubsan
   kmemleak
   kcsan
   kfence
   gdb-kernel-debugging
   kgdb
   kselftest
   kunit/index
   ktap

.. only::  subproject and html

   Indices
   =======

   * :ref:`genindex`

repo_name: angery/linux


code:
The Kernel Address Sanitizer (KASAN)
====================================

Overview
--------

Kernel Address Sanitizer (KASAN) is a dynamic memory safety error detector
designed to find out-of-bounds and use-after-free bugs.

KASAN has three modes:

1. Generic KASAN
2. Software Tag-Based KASAN
3. Hardware Tag-Based KASAN

Generic KASAN, enabled with CONFIG_KASAN_GENERIC, is the mode intended for
debugging, similar to userspace ASan. This mode is supported on many CPU
architectures, but it has significant performance and memory overheads.

Software Tag-Based KASAN or SW_TAGS KASAN, enabled with CONFIG_KASAN_SW_TAGS,
can be used for both debugging and dogfood testing, similar to userspace HWASan.
This mode is only supported for arm64, but its moderate memory overhead allows
using it for testing on memory-restricted devices with real workloads.

Hardware Tag-Based KASAN or HW_TAGS KASAN, enabled with CONFIG_KASAN_HW_TAGS,
is the mode intended to be used as an in-field memory bug detector or as a
security mitigation. This mode only works on arm64 CPUs that support MTE
(Memory Tagging Extension), but it has low memory and performance overheads and
thus can be used in production.

For details about the memory and performance impact of each KASAN mode, see the
descriptions of the corresponding Kconfig options.

The Generic and the Software Tag-Based modes are commonly referred to as the
software modes. The Software Tag-Based and the Hardware Tag-Based modes are
referred to as the tag-based modes.

Support
-------

Architectures
~~~~~~~~~~~~~

Generic KASAN is supported on x86_64, arm, arm64, powerpc, riscv, s390, and
xtensa, and the tag-based KASAN modes are supported only on arm64.

Compilers
~~~~~~~~~

Software KASAN modes use compile-time instrumentation to insert validity checks
before every memory access and thus require a compiler version that provides
support for that. The Hardware Tag-Based mode relies on hardware to perform
these checks but still requires a compiler version that supports the memory
tagging instructions.

Generic KASAN requires GCC version 8.3.0 or later
or any Clang version supported by the kernel.

Software Tag-Based KASAN requires GCC 11+
or any Clang version supported by the kernel.

Hardware Tag-Based KASAN requires GCC 10+ or Clang 12+.

Memory types
~~~~~~~~~~~~

Generic KASAN supports finding bugs in all of slab, page_alloc, vmap, vmalloc,
stack, and global memory.

Software Tag-Based KASAN supports slab, page_alloc, vmalloc, and stack memory.

Hardware Tag-Based KASAN supports slab, page_alloc, and non-executable vmalloc
memory.

For slab, both software KASAN modes support SLUB and SLAB allocators, while
Hardware Tag-Based KASAN only supports SLUB.

Usage
-----

To enable KASAN, configure the kernel with::

	  CONFIG_KASAN=y

and choose between ``CONFIG_KASAN_GENERIC`` (to enable Generic KASAN),
``CONFIG_KASAN_SW_TAGS`` (to enable Software Tag-Based KASAN), and
``CONFIG_KASAN_HW_TAGS`` (to enable Hardware Tag-Based KASAN).

For the software modes, also choose between ``CONFIG_KASAN_OUTLINE`` and
``CONFIG_KASAN_INLINE``. Outline and inline are compiler instrumentation types.
The former produces a smaller binary while the latter is up to 2 times faster.

To include alloc and free stack traces of affected slab objects into reports,
enable ``CONFIG_STACKTRACE``. To include alloc and free stack traces of affected
physical pages, enable ``CONFIG_PAGE_OWNER`` and boot with ``page_owner=on``.

Boot parameters
~~~~~~~~~~~~~~~

KASAN is affected by the generic ``panic_on_warn`` command line parameter.
When it is enabled, KASAN panics the kernel after printing a bug report.

By default, KASAN prints a bug report only for the first invalid memory access.
With ``kasan_multi_shot``, KASAN prints a report on every invalid access. This
effectively disables ``panic_on_warn`` for KASAN reports.

Alternatively, independent of ``panic_on_warn``, the ``kasan.fault=`` boot
parameter can be used to control panic and reporting behaviour:

- ``kasan.fault=report`` or ``=panic`` controls whether to only print a KASAN
  report or also panic the kernel (default: ``report``). The panic happens even
  if ``kasan_multi_shot`` is enabled.

Software and Hardware Tag-Based KASAN modes (see the section about various
modes below) support altering stack trace collection behavior:

- ``kasan.stacktrace=off`` or ``=on`` disables or enables alloc and free stack
  traces collection (default: ``on``).
- ``kasan.stack_ring_size=<number of entries>`` specifies the number of entries
  in the stack ring (default: ``32768``).

Hardware Tag-Based KASAN mode is intended for use in production as a security
mitigation. Therefore, it supports additional boot parameters that allow
disabling KASAN altogether or controlling its features:

- ``kasan=off`` or ``=on`` controls whether KASAN is enabled (default: ``on``).

- ``kasan.mode=sync``, ``=async`` or ``=asymm`` controls whether KASAN
  is configured in synchronous, asynchronous or asymmetric mode of
  execution (default: ``sync``).
  Synchronous mode: a bad access is detected immediately when a tag
  check fault occurs.
  Asynchronous mode: a bad access detection is delayed. When a tag check
  fault occurs, the information is stored in hardware (in the TFSR_EL1
  register for arm64). The kernel periodically checks the hardware and
  only reports tag faults during these checks.
  Asymmetric mode: a bad access is detected synchronously on reads and
  asynchronously on writes.

- ``kasan.vmalloc=off`` or ``=on`` disables or enables tagging of vmalloc
  allocations (default: ``on``).

Error reports
~~~~~~~~~~~~~

A typical KASAN report looks like this::

    ==================================================================
    BUG: KASAN: slab-out-of-bounds in kmalloc_oob_right+0xa8/0xbc [test_kasan]
    Write of size 1 at addr ffff8801f44ec37b by task insmod/2760

    CPU: 1 PID: 2760 Comm: insmod Not tainted 4.19.0-rc3+ #698
    Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.10.2-1 04/01/2014
    Call Trace:
     dump_stack+0x94/0xd8
     print_address_description+0x73/0x280
     kasan_report+0x144/0x187
     __asan_report_store1_noabort+0x17/0x20
     kmalloc_oob_right+0xa8/0xbc [test_kasan]
     kmalloc_tests_init+0x16/0x700 [test_kasan]
     do_one_initcall+0xa5/0x3ae
     do_init_module+0x1b6/0x547
     load_module+0x75df/0x8070
     __do_sys_init_module+0x1c6/0x200
     __x64_sys_init_module+0x6e/0xb0
     do_syscall_64+0x9f/0x2c0
     entry_SYSCALL_64_after_hwframe+0x44/0xa9
    RIP: 0033:0x7f96443109da
    RSP: 002b:00007ffcf0b51b08 EFLAGS: 00000202 ORIG_RAX: 00000000000000af
    RAX: ffffffffffffffda RBX: 000055dc3ee521a0 RCX: 00007f96443109da
    RDX: 00007f96445cff88 RSI: 0000000000057a50 RDI: 00007f9644992000
    RBP: 000055dc3ee510b0 R08: 0000000000000003 R09: 0000000000000000
    R10: 00007f964430cd0a R11: 0000000000000202 R12: 00007f96445cff88
    R13: 000055dc3ee51090 R14: 0000000000000000 R15: 0000000000000000

    Allocated by task 2760:
     save_stack+0x43/0xd0
     kasan_kmalloc+0xa7/0xd0
     kmem_cache_alloc_trace+0xe1/0x1b0
     kmalloc_oob_right+0x56/0xbc [test_kasan]
     kmalloc_tests_init+0x16/0x700 [test_kasan]
     do_one_initcall+0xa5/0x3ae
     do_init_module+0x1b6/0x547
     load_module+0x75df/0x8070
     __do_sys_init_module+0x1c6/0x200
     __x64_sys_init_module+0x6e/0xb0
     do_syscall_64+0x9f/0x2c0
     entry_SYSCALL_64_after_hwframe+0x44/0xa9

    Freed by task 815:
     save_stack+0x43/0xd0
     __kasan_slab_free+0x135/0x190
     kasan_slab_free+0xe/0x10
     kfree+0x93/0x1a0
     umh_complete+0x6a/0xa0
     call_usermodehelper_exec_async+0x4c3/0x640
     ret_from_fork+0x35/0x40

    The buggy address belongs to the object at ffff8801f44ec300
     which belongs to the cache kmalloc-128 of size 128
    The buggy address is located 123 bytes inside of
     128-byte region [ffff8801f44ec300, ffff8801f44ec380)
    The buggy address belongs to the page:
    page:ffffea0007d13b00 count:1 mapcount:0 mapping:ffff8801f7001640 index:0x0
    flags: 0x200000000000100(slab)
    raw: 0200000000000100 ffffea0007d11dc0 0000001a0000001a ffff8801f7001640
    raw: 0000000000000000 0000000080150015 00000001ffffffff 0000000000000000
    page dumped because: kasan: bad access detected

    Memory state around the buggy address:
     ffff8801f44ec200: fc fc fc fc fc fc fc fc fb fb fb fb fb fb fb fb
     ffff8801f44ec280: fb fb fb fb fb fb fb fb fc fc fc fc fc fc fc fc
    >ffff8801f44ec300: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 03
                                                                    ^
     ffff8801f44ec380: fc fc fc fc fc fc fc fc fb fb fb fb fb fb fb fb
     ffff8801f44ec400: fb fb fb fb fb fb fb fb fc fc fc fc fc fc fc fc
    ==================================================================

The report header summarizes what kind of bug happened and what kind of access
caused it. It is followed by a stack trace of the bad access, a stack trace of
where the accessed memory was allocated (in case a slab object was accessed),
and a stack trace of where the object was freed (in case of a use-after-free
bug report). Next comes a description of the accessed slab object and the
information about the accessed memory page.

In the end, the report shows the memory state around the accessed address.
Internally, KASAN tracks memory state separately for each memory granule, which
is either 8 or 16 aligned bytes depending on KASAN mode. Each number in the
memory state section of the report shows the state of one of the memory
granules that surround the accessed address.

For Generic KASAN, the size of each memory granule is 8. The state of each
granule is encoded in one shadow byte. Those 8 bytes can be accessible,
partially accessible, freed, or be a part of a redzone. KASAN uses the following
encoding for each shadow byte: 00 means that all 8 bytes of the corresponding
memory region are accessible; number N (1 <= N <= 7) means that the first N
bytes are accessible, and other (8 - N) bytes are not; any negative value
indicates that the entire 8-byte word is inaccessible. KASAN uses different
negative values to distinguish between different kinds of inaccessible memory
like redzones or freed memory (see mm/kasan/kasan.h).

In the report above, the arrow points to the shadow byte ``03``, which means
that the accessed address is partially accessible.

For tag-based KASAN modes, this last report section shows the memory tags around
the accessed address (see the `Implementation details`_ section).

Note that KASAN bug titles (like ``slab-out-of-bounds`` or ``use-after-free``)
are best-effort: KASAN prints the most probable bug type based on the limited
information it has. The actual type of the bug might be different.

Generic KASAN also reports up to two auxiliary call stack traces. These stack
traces point to places in code that interacted with the object but that are not
directly present in the bad access stack trace. Currently, this includes
call_rcu() and workqueue queuing.

Implementation details
----------------------

Generic KASAN
~~~~~~~~~~~~~

Software KASAN modes use shadow memory to record whether each byte of memory is
safe to access and use compile-time instrumentation to insert shadow memory
checks before each memory access.

Generic KASAN dedicates 1/8th of kernel memory to its shadow memory (16TB
to cover 128TB on x86_64) and uses direct mapping with a scale and offset to
translate a memory address to its corresponding shadow address.

Here is the function which translates an address to its corresponding shadow
address::

    static inline void *kasan_mem_to_shadow(const void *addr)
    {
	return (void *)((unsigned long)addr >> KASAN_SHADOW_SCALE_SHIFT)
		+ KASAN_SHADOW_OFFSET;
    }

where ``KASAN_SHADOW_SCALE_SHIFT = 3``.

Compile-time instrumentation is used to insert memory access checks. Compiler
inserts function calls (``__asan_load*(addr)``, ``__asan_store*(addr)``) before
each memory access of size 1, 2, 4, 8, or 16. These functions check whether
memory accesses are valid or not by checking corresponding shadow memory.

With inline instrumentation, instead of making function calls, the compiler
directly inserts the code to check shadow memory. This option significantly
enlarges the kernel, but it gives an x1.1-x2 performance boost over the
outline-instrumented kernel.

Generic KASAN is the only mode that delays the reuse of freed objects via
quarantine (see mm/kasan/quarantine.c for implementation).

Software Tag-Based KASAN
~~~~~~~~~~~~~~~~~~~~~~~~

Software Tag-Based KASAN uses a software memory tagging approach to checking
access validity. It is currently only implemented for the arm64 architecture.

Software Tag-Based KASAN uses the Top Byte Ignore (TBI) feature of arm64 CPUs
to store a pointer tag in the top byte of kernel pointers. It uses shadow memory
to store memory tags associated with each 16-byte memory cell (therefore, it
dedicates 1/16th of the kernel memory for shadow memory).

On each memory allocation, Software Tag-Based KASAN generates a random tag, tags
the allocated memory with this tag, and embeds the same tag into the returned
pointer.

Software Tag-Based KASAN uses compile-time instrumentation to insert checks
before each memory access. These checks make sure that the tag of the memory
that is being accessed is equal to the tag of the pointer that is used to access
this memory. In case of a tag mismatch, Software Tag-Based KASAN prints a bug
report.

Software Tag-Based KASAN also has two instrumentation modes (outline, which
emits callbacks to check memory accesses; and inline, which performs the shadow
memory checks inline). With outline instrumentation mode, a bug report is
printed from the function that performs the access check. With inline
instrumentation, a ``brk`` instruction is emitted by the compiler, and a
dedicated ``brk`` handler is used to print bug reports.

Software Tag-Based KASAN uses 0xFF as a match-all pointer tag (accesses through
pointers with the 0xFF pointer tag are not checked). The value 0xFE is currently
reserved to tag freed memory regions.

Hardware Tag-Based KASAN
~~~~~~~~~~~~~~~~~~~~~~~~

Hardware Tag-Based KASAN is similar to the software mode in concept but uses
hardware memory tagging support instead of compiler instrumentation and
shadow memory.

Hardware Tag-Based KASAN is currently only implemented for arm64 architecture
and based on both arm64 Memory Tagging Extension (MTE) introduced in ARMv8.5
Instruction Set Architecture and Top Byte Ignore (TBI).

Special arm64 instructions are used to assign memory tags for each allocation.
Same tags are assigned to pointers to those allocations. On every memory
access, hardware makes sure that the tag of the memory that is being accessed is
equal to the tag of the pointer that is used to access this memory. In case of a
tag mismatch, a fault is generated, and a report is printed.

Hardware Tag-Based KASAN uses 0xFF as a match-all pointer tag (accesses through
pointers with the 0xFF pointer tag are not checked). The value 0xFE is currently
reserved to tag freed memory regions.

If the hardware does not support MTE (pre ARMv8.5), Hardware Tag-Based KASAN
will not be enabled. In this case, all KASAN boot parameters are ignored.

Note that enabling CONFIG_KASAN_HW_TAGS always results in in-kernel TBI being
enabled. Even when ``kasan.mode=off`` is provided or when the hardware does not
support MTE (but supports TBI).

Hardware Tag-Based KASAN only reports the first found bug. After that, MTE tag
checking gets disabled.

Shadow memory
-------------

The contents of this section are only applicable to software KASAN modes.

The kernel maps memory in several different parts of the address space.
The range of kernel virtual addresses is large: there is not enough real
memory to support a real shadow region for every address that could be
accessed by the kernel. Therefore, KASAN only maps real shadow for certain
parts of the address space.

Default behaviour
~~~~~~~~~~~~~~~~~

By default, architectures only map real memory over the shadow region
for the linear mapping (and potentially other small areas). For all
other areas - such as vmalloc and vmemmap space - a single read-only
page is mapped over the shadow area. This read-only shadow page
declares all memory accesses as permitted.

This presents a problem for modules: they do not live in the linear
mapping but in a dedicated module space. By hooking into the module
allocator, KASAN temporarily maps real shadow memory to cover them.
This allows detection of invalid accesses to module globals, for example.

This also creates an incompatibility with ``VMAP_STACK``: if the stack
lives in vmalloc space, it will be shadowed by the read-only page, and
the kernel will fault when trying to set up the shadow data for stack
variables.

CONFIG_KASAN_VMALLOC
~~~~~~~~~~~~~~~~~~~~

With ``CONFIG_KASAN_VMALLOC``, KASAN can cover vmalloc space at the
cost of greater memory usage. Currently, this is supported on x86,
arm64, riscv, s390, and powerpc.

This works by hooking into vmalloc and vmap and dynamically
allocating real shadow memory to back the mappings.

Most mappings in vmalloc space are small, requiring less than a full
page of shadow space. Allocating a full shadow page per mapping would
therefore be wasteful. Furthermore, to ensure that different mappings
use different shadow pages, mappings would have to be aligned to
``KASAN_GRANULE_SIZE * PAGE_SIZE``.

Instead, KASAN shares backing space across multiple mappings. It allocates
a backing page when a mapping in vmalloc space uses a particular page
of the shadow region. This page can be shared by other vmalloc
mappings later on.

KASAN hooks into the vmap infrastructure to lazily clean up unused shadow
memory.

To avoid the difficulties around swapping mappings around, KASAN expects
that the part of the shadow region that covers the vmalloc space will
not be covered by the early shadow page but will be left unmapped.
This will require changes in arch-specific code.

This allows ``VMAP_STACK`` support on x86 and can simplify support of
architectures that do not have a fixed module region.

For developers
--------------

Ignoring accesses
~~~~~~~~~~~~~~~~~

Software KASAN modes use compiler instrumentation to insert validity checks.
Such instrumentation might be incompatible with some parts of the kernel, and
therefore needs to be disabled.

Other parts of the kernel might access metadata for allocated objects.
Normally, KASAN detects and reports such accesses, but in some cases (e.g.,
in memory allocators), these accesses are valid.

For software KASAN modes, to disable instrumentation for a specific file or
directory, add a ``KASAN_SANITIZE`` annotation to the respective kernel
Makefile:

- For a single file (e.g., main.o)::

    KASAN_SANITIZE_main.o := n

- For all files in one directory::

    KASAN_SANITIZE := n

For software KASAN modes, to disable instrumentation on a per-function basis,
use the KASAN-specific ``__no_sanitize_address`` function attribute or the
generic ``noinstr`` one.

Note that disabling compiler instrumentation (either on a per-file or a
per-function basis) makes KASAN ignore the accesses that happen directly in
that code for software KASAN modes. It does not help when the accesses happen
indirectly (through calls to instrumented functions) or with Hardware
Tag-Based KASAN, which does not use compiler instrumentation.

For software KASAN modes, to disable KASAN reports in a part of the kernel code
for the current task, annotate this part of the code with a
``kasan_disable_current()``/``kasan_enable_current()`` section. This also
disables the reports for indirect accesses that happen through function calls.

For tag-based KASAN modes, to disable access checking, use
``kasan_reset_tag()`` or ``page_kasan_tag_reset()``. Note that temporarily
disabling access checking via ``page_kasan_tag_reset()`` requires saving and
restoring the per-page KASAN tag via ``page_kasan_tag``/``page_kasan_tag_set``.

Tests
~~~~~

There are KASAN tests that allow verifying that KASAN works and can detect
certain types of memory corruptions. The tests consist of two parts:

1. Tests that are integrated with the KUnit Test Framework. Enabled with
``CONFIG_KASAN_KUNIT_TEST``. These tests can be run and partially verified
automatically in a few different ways; see the instructions below.

2. Tests that are currently incompatible with KUnit. Enabled with
``CONFIG_KASAN_MODULE_TEST`` and can only be run as a module. These tests can
only be verified manually by loading the kernel module and inspecting the
kernel log for KASAN reports.

Each KUnit-compatible KASAN test prints one of multiple KASAN reports if an
error is detected. Then the test prints its number and status.

When a test passes::

        ok 28 - kmalloc_double_kzfree

When a test fails due to a failed ``kmalloc``::

        # kmalloc_large_oob_right: ASSERTION FAILED at lib/test_kasan.c:163
        Expected ptr is not null, but is
        not ok 4 - kmalloc_large_oob_right

When a test fails due to a missing KASAN report::

        # kmalloc_double_kzfree: EXPECTATION FAILED at lib/test_kasan.c:974
        KASAN failure expected in "kfree_sensitive(ptr)", but none occurred
        not ok 44 - kmalloc_double_kzfree

At the end the cumulative status of all KASAN tests is printed. On success::

        ok 1 - kasan

Or, if one of the tests failed::

        not ok 1 - kasan

There are a few ways to run KUnit-compatible KASAN tests.

1. Loadable module

   With ``CONFIG_KUNIT`` enabled, KASAN-KUnit tests can be built as a loadable
   module and run by loading ``test_kasan.ko`` with ``insmod`` or ``modprobe``.

2. Built-In

   With ``CONFIG_KUNIT`` built-in, KASAN-KUnit tests can be built-in as well.
   In this case, the tests will run at boot as a late-init call.

3. Using kunit_tool

   With ``CONFIG_KUNIT`` and ``CONFIG_KASAN_KUNIT_TEST`` built-in, it is also
   possible to use ``kunit_tool`` to see the results of KUnit tests in a more
   readable way. This will not print the KASAN reports of the tests that passed.
   See `KUnit documentation <https://www.kernel.org/doc/html/latest/dev-tools/kunit/index.html>`_
   for more up-to-date information on ``kunit_tool``.

.. _KUnit: https://www.kernel.org/doc/html/latest/dev-tools/kunit/index.html


code:
kcov: code coverage for fuzzing
===============================

kcov exposes kernel code coverage information in a form suitable for coverage-
guided fuzzing (randomized testing). Coverage data of a running kernel is
exported via the "kcov" debugfs file. Coverage collection is enabled on a task
basis, and thus it can capture precise coverage of a single system call.

Note that kcov does not aim to collect as much coverage as possible. It aims
to collect more or less stable coverage that is function of syscall inputs.
To achieve this goal it does not collect coverage in soft/hard interrupts
and instrumentation of some inherently non-deterministic parts of kernel is
disabled (e.g. scheduler, locking).

kcov is also able to collect comparison operands from the instrumented code
(this feature currently requires that the kernel is compiled with clang).

Prerequisites
-------------

Configure the kernel with::

        CONFIG_KCOV=y

CONFIG_KCOV requires gcc 6.1.0 or later.

If the comparison operands need to be collected, set::

	CONFIG_KCOV_ENABLE_COMPARISONS=y

Profiling data will only become accessible once debugfs has been mounted::

        mount -t debugfs none /sys/kernel/debug

Coverage collection
-------------------

The following program demonstrates coverage collection from within a test
program using kcov:

.. code-block:: c

    #include <stdio.h>
    #include <stddef.h>
    #include <stdint.h>
    #include <stdlib.h>
    #include <sys/types.h>
    #include <sys/stat.h>
    #include <sys/ioctl.h>
    #include <sys/mman.h>
    #include <unistd.h>
    #include <fcntl.h>
    #include <linux/types.h>

    #define KCOV_INIT_TRACE			_IOR('c', 1, unsigned long)
    #define KCOV_ENABLE			_IO('c', 100)
    #define KCOV_DISABLE			_IO('c', 101)
    #define COVER_SIZE			(64<<10)

    #define KCOV_TRACE_PC  0
    #define KCOV_TRACE_CMP 1

    int main(int argc, char **argv)
    {
	int fd;
	unsigned long *cover, n, i;

	/* A single fd descriptor allows coverage collection on a single
	 * thread.
	 */
	fd = open("/sys/kernel/debug/kcov", O_RDWR);
	if (fd == -1)
		perror("open"), exit(1);
	/* Setup trace mode and trace size. */
	if (ioctl(fd, KCOV_INIT_TRACE, COVER_SIZE))
		perror("ioctl"), exit(1);
	/* Mmap buffer shared between kernel- and user-space. */
	cover = (unsigned long*)mmap(NULL, COVER_SIZE * sizeof(unsigned long),
				     PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
	if ((void*)cover == MAP_FAILED)
		perror("mmap"), exit(1);
	/* Enable coverage collection on the current thread. */
	if (ioctl(fd, KCOV_ENABLE, KCOV_TRACE_PC))
		perror("ioctl"), exit(1);
	/* Reset coverage from the tail of the ioctl() call. */
	__atomic_store_n(&cover[0], 0, __ATOMIC_RELAXED);
	/* That's the target syscal call. */
	read(-1, NULL, 0);
	/* Read number of PCs collected. */
	n = __atomic_load_n(&cover[0], __ATOMIC_RELAXED);
	for (i = 0; i < n; i++)
		printf("0x%lx\n", cover[i + 1]);
	/* Disable coverage collection for the current thread. After this call
	 * coverage can be enabled for a different thread.
	 */
	if (ioctl(fd, KCOV_DISABLE, 0))
		perror("ioctl"), exit(1);
	/* Free resources. */
	if (munmap(cover, COVER_SIZE * sizeof(unsigned long)))
		perror("munmap"), exit(1);
	if (close(fd))
		perror("close"), exit(1);
	return 0;
    }

After piping through addr2line output of the program looks as follows::

    SyS_read
    fs/read_write.c:562
    __fdget_pos
    fs/file.c:774
    __fget_light
    fs/file.c:746
    __fget_light
    fs/file.c:750
    __fget_light
    fs/file.c:760
    __fdget_pos
    fs/file.c:784
    SyS_read
    fs/read_write.c:562

If a program needs to collect coverage from several threads (independently),
it needs to open /sys/kernel/debug/kcov in each thread separately.

The interface is fine-grained to allow efficient forking of test processes.
That is, a parent process opens /sys/kernel/debug/kcov, enables trace mode,
mmaps coverage buffer and then forks child processes in a loop. Child processes
only need to enable coverage (disable happens automatically on thread end).

Comparison operands collection
------------------------------

Comparison operands collection is similar to coverage collection:

.. code-block:: c

    /* Same includes and defines as above. */

    /* Number of 64-bit words per record. */
    #define KCOV_WORDS_PER_CMP 4

    /*
     * The format for the types of collected comparisons.
     *
     * Bit 0 shows whether one of the arguments is a compile-time constant.
     * Bits 1 & 2 contain log2 of the argument size, up to 8 bytes.
     */

    #define KCOV_CMP_CONST          (1 << 0)
    #define KCOV_CMP_SIZE(n)        ((n) << 1)
    #define KCOV_CMP_MASK           KCOV_CMP_SIZE(3)

    int main(int argc, char **argv)
    {
	int fd;
	uint64_t *cover, type, arg1, arg2, is_const, size;
	unsigned long n, i;

	fd = open("/sys/kernel/debug/kcov", O_RDWR);
	if (fd == -1)
		perror("open"), exit(1);
	if (ioctl(fd, KCOV_INIT_TRACE, COVER_SIZE))
		perror("ioctl"), exit(1);
	/*
	* Note that the buffer pointer is of type uint64_t*, because all
	* the comparison operands are promoted to uint64_t.
	*/
	cover = (uint64_t *)mmap(NULL, COVER_SIZE * sizeof(unsigned long),
				     PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
	if ((void*)cover == MAP_FAILED)
		perror("mmap"), exit(1);
	/* Note KCOV_TRACE_CMP instead of KCOV_TRACE_PC. */
	if (ioctl(fd, KCOV_ENABLE, KCOV_TRACE_CMP))
		perror("ioctl"), exit(1);
	__atomic_store_n(&cover[0], 0, __ATOMIC_RELAXED);
	read(-1, NULL, 0);
	/* Read number of comparisons collected. */
	n = __atomic_load_n(&cover[0], __ATOMIC_RELAXED);
	for (i = 0; i < n; i++) {
		uint64_t ip;

		type = cover[i * KCOV_WORDS_PER_CMP + 1];
		/* arg1 and arg2 - operands of the comparison. */
		arg1 = cover[i * KCOV_WORDS_PER_CMP + 2];
		arg2 = cover[i * KCOV_WORDS_PER_CMP + 3];
		/* ip - caller address. */
		ip = cover[i * KCOV_WORDS_PER_CMP + 4];
		/* size of the operands. */
		size = 1 << ((type & KCOV_CMP_MASK) >> 1);
		/* is_const - true if either operand is a compile-time constant.*/
		is_const = type & KCOV_CMP_CONST;
		printf("ip: 0x%lx type: 0x%lx, arg1: 0x%lx, arg2: 0x%lx, "
			"size: %lu, %s\n",
			ip, type, arg1, arg2, size,
		is_const ? "const" : "non-const");
	}
	if (ioctl(fd, KCOV_DISABLE, 0))
		perror("ioctl"), exit(1);
	/* Free resources. */
	if (munmap(cover, COVER_SIZE * sizeof(unsigned long)))
		perror("munmap"), exit(1);
	if (close(fd))
		perror("close"), exit(1);
	return 0;
    }

Note that the kcov modes (coverage collection or comparison operands) are
mutually exclusive.

Remote coverage collection
--------------------------

With KCOV_ENABLE coverage is collected only for syscalls that are issued
from the current process. With KCOV_REMOTE_ENABLE it's possible to collect
coverage for arbitrary parts of the kernel code, provided that those parts
are annotated with kcov_remote_start()/kcov_remote_stop().

This allows to collect coverage from two types of kernel background
threads: the global ones, that are spawned during kernel boot in a limited
number of instances (e.g. one USB hub_event() worker thread is spawned per
USB HCD); and the local ones, that are spawned when a user interacts with
some kernel interface (e.g. vhost workers); as well as from soft
interrupts.

To enable collecting coverage from a global background thread or from a
softirq, a unique global handle must be assigned and passed to the
corresponding kcov_remote_start() call. Then a userspace process can pass
a list of such handles to the KCOV_REMOTE_ENABLE ioctl in the handles
array field of the kcov_remote_arg struct. This will attach the used kcov
device to the code sections, that are referenced by those handles.

Since there might be many local background threads spawned from different
userspace processes, we can't use a single global handle per annotation.
Instead, the userspace process passes a non-zero handle through the
common_handle field of the kcov_remote_arg struct. This common handle gets
saved to the kcov_handle field in the current task_struct and needs to be
passed to the newly spawned threads via custom annotations. Those threads
should in turn be annotated with kcov_remote_start()/kcov_remote_stop().

Internally kcov stores handles as u64 integers. The top byte of a handle
is used to denote the id of a subsystem that this handle belongs to, and
the lower 4 bytes are used to denote the id of a thread instance within
that subsystem. A reserved value 0 is used as a subsystem id for common
handles as they don't belong to a particular subsystem. The bytes 4-7 are
currently reserved and must be zero. In the future the number of bytes
used for the subsystem or handle ids might be increased.

When a particular userspace process collects coverage via a common
handle, kcov will collect coverage for each code section that is annotated
to use the common handle obtained as kcov_handle from the current
task_struct. However non common handles allow to collect coverage
selectively from different subsystems.

.. code-block:: c

    /* Same includes and defines as above. */

    struct kcov_remote_arg {
	__u32		trace_mode;
	__u32		area_size;
	__u32		num_handles;
	__aligned_u64	common_handle;
	__aligned_u64	handles[0];
    };

    #define KCOV_INIT_TRACE			_IOR('c', 1, unsigned long)
    #define KCOV_DISABLE			_IO('c', 101)
    #define KCOV_REMOTE_ENABLE		_IOW('c', 102, struct kcov_remote_arg)

    #define COVER_SIZE	(64 << 10)

    #define KCOV_TRACE_PC	0

    #define KCOV_SUBSYSTEM_COMMON	(0x00ull << 56)
    #define KCOV_SUBSYSTEM_USB	(0x01ull << 56)

    #define KCOV_SUBSYSTEM_MASK	(0xffull << 56)
    #define KCOV_INSTANCE_MASK	(0xffffffffull)

    static inline __u64 kcov_remote_handle(__u64 subsys, __u64 inst)
    {
	if (subsys & ~KCOV_SUBSYSTEM_MASK || inst & ~KCOV_INSTANCE_MASK)
		return 0;
	return subsys | inst;
    }

    #define KCOV_COMMON_ID	0x42
    #define KCOV_USB_BUS_NUM	1

    int main(int argc, char **argv)
    {
	int fd;
	unsigned long *cover, n, i;
	struct kcov_remote_arg *arg;

	fd = open("/sys/kernel/debug/kcov", O_RDWR);
	if (fd == -1)
		perror("open"), exit(1);
	if (ioctl(fd, KCOV_INIT_TRACE, COVER_SIZE))
		perror("ioctl"), exit(1);
	cover = (unsigned long*)mmap(NULL, COVER_SIZE * sizeof(unsigned long),
				     PROT_READ | PROT_WRITE, MAP_SHARED, fd, 0);
	if ((void*)cover == MAP_FAILED)
		perror("mmap"), exit(1);

	/* Enable coverage collection via common handle and from USB bus #1. */
	arg = calloc(1, sizeof(*arg) + sizeof(uint64_t));
	if (!arg)
		perror("calloc"), exit(1);
	arg->trace_mode = KCOV_TRACE_PC;
	arg->area_size = COVER_SIZE;
	arg->num_handles = 1;
	arg->common_handle = kcov_remote_handle(KCOV_SUBSYSTEM_COMMON,
							KCOV_COMMON_ID);
	arg->handles[0] = kcov_remote_handle(KCOV_SUBSYSTEM_USB,
						KCOV_USB_BUS_NUM);
	if (ioctl(fd, KCOV_REMOTE_ENABLE, arg))
		perror("ioctl"), free(arg), exit(1);
	free(arg);

	/*
	 * Here the user needs to trigger execution of a kernel code section
	 * that is either annotated with the common handle, or to trigger some
	 * activity on USB bus #1.
	 */
	sleep(2);

	n = __atomic_load_n(&cover[0], __ATOMIC_RELAXED);
	for (i = 0; i < n; i++)
		printf("0x%lx\n", cover[i + 1]);
	if (ioctl(fd, KCOV_DISABLE, 0))
		perror("ioctl"), exit(1);
	if (munmap(cover, COVER_SIZE * sizeof(unsigned long)))
		perror("munmap"), exit(1);
	if (close(fd))
		perror("close"), exit(1);
	return 0;
    }


code:
.. SPDX-License-Identifier: GPL-2.0
.. Copyright (C) 2019, Google LLC.

The Kernel Concurrency Sanitizer (KCSAN)
========================================

The Kernel Concurrency Sanitizer (KCSAN) is a dynamic race detector, which
relies on compile-time instrumentation, and uses a watchpoint-based sampling
approach to detect races. KCSAN's primary purpose is to detect `data races`_.

Usage
-----

KCSAN is supported by both GCC and Clang. With GCC we require version 11 or
later, and with Clang also require version 11 or later.

To enable KCSAN configure the kernel with::

    CONFIG_KCSAN = y

KCSAN provides several other configuration options to customize behaviour (see
the respective help text in ``lib/Kconfig.kcsan`` for more info).

Error reports
~~~~~~~~~~~~~

A typical data race report looks like this::

    ==================================================================
    BUG: KCSAN: data-race in test_kernel_read / test_kernel_write

    write to 0xffffffffc009a628 of 8 bytes by task 487 on cpu 0:
     test_kernel_write+0x1d/0x30
     access_thread+0x89/0xd0
     kthread+0x23e/0x260
     ret_from_fork+0x22/0x30

    read to 0xffffffffc009a628 of 8 bytes by task 488 on cpu 6:
     test_kernel_read+0x10/0x20
     access_thread+0x89/0xd0
     kthread+0x23e/0x260
     ret_from_fork+0x22/0x30

    value changed: 0x00000000000009a6 -> 0x00000000000009b2

    Reported by Kernel Concurrency Sanitizer on:
    CPU: 6 PID: 488 Comm: access_thread Not tainted 5.12.0-rc2+ #1
    Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-2 04/01/2014
    ==================================================================

The header of the report provides a short summary of the functions involved in
the race. It is followed by the access types and stack traces of the 2 threads
involved in the data race. If KCSAN also observed a value change, the observed
old value and new value are shown on the "value changed" line respectively.

The other less common type of data race report looks like this::

    ==================================================================
    BUG: KCSAN: data-race in test_kernel_rmw_array+0x71/0xd0

    race at unknown origin, with read to 0xffffffffc009bdb0 of 8 bytes by task 515 on cpu 2:
     test_kernel_rmw_array+0x71/0xd0
     access_thread+0x89/0xd0
     kthread+0x23e/0x260
     ret_from_fork+0x22/0x30

    value changed: 0x0000000000002328 -> 0x0000000000002329

    Reported by Kernel Concurrency Sanitizer on:
    CPU: 2 PID: 515 Comm: access_thread Not tainted 5.12.0-rc2+ #1
    Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-2 04/01/2014
    ==================================================================

This report is generated where it was not possible to determine the other
racing thread, but a race was inferred due to the data value of the watched
memory location having changed. These reports always show a "value changed"
line. A common reason for reports of this type are missing instrumentation in
the racing thread, but could also occur due to e.g. DMA accesses. Such reports
are shown only if ``CONFIG_KCSAN_REPORT_RACE_UNKNOWN_ORIGIN=y``, which is
enabled by default.

Selective analysis
~~~~~~~~~~~~~~~~~~

It may be desirable to disable data race detection for specific accesses,
functions, compilation units, or entire subsystems.  For static blacklisting,
the below options are available:

* KCSAN understands the ``data_race(expr)`` annotation, which tells KCSAN that
  any data races due to accesses in ``expr`` should be ignored and resulting
  behaviour when encountering a data race is deemed safe.  Please see
  `"Marking Shared-Memory Accesses" in the LKMM`_ for more information.

* Disabling data race detection for entire functions can be accomplished by
  using the function attribute ``__no_kcsan``::

    __no_kcsan
    void foo(void) {
        ...

  To dynamically limit for which functions to generate reports, see the
  `DebugFS interface`_ blacklist/whitelist feature.

* To disable data race detection for a particular compilation unit, add to the
  ``Makefile``::

    KCSAN_SANITIZE_file.o := n

* To disable data race detection for all compilation units listed in a
  ``Makefile``, add to the respective ``Makefile``::

    KCSAN_SANITIZE := n

.. _"Marking Shared-Memory Accesses" in the LKMM: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/tools/memory-model/Documentation/access-marking.txt

Furthermore, it is possible to tell KCSAN to show or hide entire classes of
data races, depending on preferences. These can be changed via the following
Kconfig options:

* ``CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY``: If enabled and a conflicting write
  is observed via a watchpoint, but the data value of the memory location was
  observed to remain unchanged, do not report the data race.

* ``CONFIG_KCSAN_ASSUME_PLAIN_WRITES_ATOMIC``: Assume that plain aligned writes
  up to word size are atomic by default. Assumes that such writes are not
  subject to unsafe compiler optimizations resulting in data races. The option
  causes KCSAN to not report data races due to conflicts where the only plain
  accesses are aligned writes up to word size.

* ``CONFIG_KCSAN_PERMISSIVE``: Enable additional permissive rules to ignore
  certain classes of common data races. Unlike the above, the rules are more
  complex involving value-change patterns, access type, and address. This
  option depends on ``CONFIG_KCSAN_REPORT_VALUE_CHANGE_ONLY=y``. For details
  please see the ``kernel/kcsan/permissive.h``. Testers and maintainers that
  only focus on reports from specific subsystems and not the whole kernel are
  recommended to disable this option.

To use the strictest possible rules, select ``CONFIG_KCSAN_STRICT=y``, which
configures KCSAN to follow the Linux-kernel memory consistency model (LKMM) as
closely as possible.

DebugFS interface
~~~~~~~~~~~~~~~~~

The file ``/sys/kernel/debug/kcsan`` provides the following interface:

* Reading ``/sys/kernel/debug/kcsan`` returns various runtime statistics.

* Writing ``on`` or ``off`` to ``/sys/kernel/debug/kcsan`` allows turning KCSAN
  on or off, respectively.

* Writing ``!some_func_name`` to ``/sys/kernel/debug/kcsan`` adds
  ``some_func_name`` to the report filter list, which (by default) blacklists
  reporting data races where either one of the top stackframes are a function
  in the list.

* Writing either ``blacklist`` or ``whitelist`` to ``/sys/kernel/debug/kcsan``
  changes the report filtering behaviour. For example, the blacklist feature
  can be used to silence frequently occurring data races; the whitelist feature
  can help with reproduction and testing of fixes.

Tuning performance
~~~~~~~~~~~~~~~~~~

Core parameters that affect KCSAN's overall performance and bug detection
ability are exposed as kernel command-line arguments whose defaults can also be
changed via the corresponding Kconfig options.

* ``kcsan.skip_watch`` (``CONFIG_KCSAN_SKIP_WATCH``): Number of per-CPU memory
  operations to skip, before another watchpoint is set up. Setting up
  watchpoints more frequently will result in the likelihood of races to be
  observed to increase. This parameter has the most significant impact on
  overall system performance and race detection ability.

* ``kcsan.udelay_task`` (``CONFIG_KCSAN_UDELAY_TASK``): For tasks, the
  microsecond delay to stall execution after a watchpoint has been set up.
  Larger values result in the window in which we may observe a race to
  increase.

* ``kcsan.udelay_interrupt`` (``CONFIG_KCSAN_UDELAY_INTERRUPT``): For
  interrupts, the microsecond delay to stall execution after a watchpoint has
  been set up. Interrupts have tighter latency requirements, and their delay
  should generally be smaller than the one chosen for tasks.

They may be tweaked at runtime via ``/sys/module/kcsan/parameters/``.

Data Races
----------

In an execution, two memory accesses form a *data race* if they *conflict*,
they happen concurrently in different threads, and at least one of them is a
*plain access*; they *conflict* if both access the same memory location, and at
least one is a write. For a more thorough discussion and definition, see `"Plain
Accesses and Data Races" in the LKMM`_.

.. _"Plain Accesses and Data Races" in the LKMM: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/tools/memory-model/Documentation/explanation.txt#n1922

Relationship with the Linux-Kernel Memory Consistency Model (LKMM)
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

The LKMM defines the propagation and ordering rules of various memory
operations, which gives developers the ability to reason about concurrent code.
Ultimately this allows to determine the possible executions of concurrent code,
and if that code is free from data races.

KCSAN is aware of *marked atomic operations* (``READ_ONCE``, ``WRITE_ONCE``,
``atomic_*``, etc.), and a subset of ordering guarantees implied by memory
barriers. With ``CONFIG_KCSAN_WEAK_MEMORY=y``, KCSAN models load or store
buffering, and can detect missing ``smp_mb()``, ``smp_wmb()``, ``smp_rmb()``,
``smp_store_release()``, and all ``atomic_*`` operations with equivalent
implied barriers.

Note, KCSAN will not report all data races due to missing memory ordering,
specifically where a memory barrier would be required to prohibit subsequent
memory operation from reordering before the barrier. Developers should
therefore carefully consider the required memory ordering requirements that
remain unchecked.

Race Detection Beyond Data Races
--------------------------------

For code with complex concurrency design, race-condition bugs may not always
manifest as data races. Race conditions occur if concurrently executing
operations result in unexpected system behaviour. On the other hand, data races
are defined at the C-language level. The following macros can be used to check
properties of concurrent code where bugs would not manifest as data races.

.. kernel-doc:: include/linux/kcsan-checks.h
    :functions: ASSERT_EXCLUSIVE_WRITER ASSERT_EXCLUSIVE_WRITER_SCOPED
                ASSERT_EXCLUSIVE_ACCESS ASSERT_EXCLUSIVE_ACCESS_SCOPED
                ASSERT_EXCLUSIVE_BITS

Implementation Details
----------------------

KCSAN relies on observing that two accesses happen concurrently. Crucially, we
want to (a) increase the chances of observing races (especially for races that
manifest rarely), and (b) be able to actually observe them. We can accomplish
(a) by injecting various delays, and (b) by using address watchpoints (or
breakpoints).

If we deliberately stall a memory access, while we have a watchpoint for its
address set up, and then observe the watchpoint to fire, two accesses to the
same address just raced. Using hardware watchpoints, this is the approach taken
in `DataCollider
<http://usenix.org/legacy/events/osdi10/tech/full_papers/Erickson.pdf>`_.
Unlike DataCollider, KCSAN does not use hardware watchpoints, but instead
relies on compiler instrumentation and "soft watchpoints".

In KCSAN, watchpoints are implemented using an efficient encoding that stores
access type, size, and address in a long; the benefits of using "soft
watchpoints" are portability and greater flexibility. KCSAN then relies on the
compiler instrumenting plain accesses. For each instrumented plain access:

1. Check if a matching watchpoint exists; if yes, and at least one access is a
   write, then we encountered a racing access.

2. Periodically, if no matching watchpoint exists, set up a watchpoint and
   stall for a small randomized delay.

3. Also check the data value before the delay, and re-check the data value
   after delay; if the values mismatch, we infer a race of unknown origin.

To detect data races between plain and marked accesses, KCSAN also annotates
marked accesses, but only to check if a watchpoint exists; i.e. KCSAN never
sets up a watchpoint on marked accesses. By never setting up watchpoints for
marked operations, if all accesses to a variable that is accessed concurrently
are properly marked, KCSAN will never trigger a watchpoint and therefore never
report the accesses.

Modeling Weak Memory
~~~~~~~~~~~~~~~~~~~~

KCSAN's approach to detecting data races due to missing memory barriers is
based on modeling access reordering (with ``CONFIG_KCSAN_WEAK_MEMORY=y``).
Each plain memory access for which a watchpoint is set up, is also selected for
simulated reordering within the scope of its function (at most 1 in-flight
access).

Once an access has been selected for reordering, it is checked along every
other access until the end of the function scope. If an appropriate memory
barrier is encountered, the access will no longer be considered for simulated
reordering.

When the result of a memory operation should be ordered by a barrier, KCSAN can
then detect data races where the conflict only occurs as a result of a missing
barrier. Consider the example::

    int x, flag;
    void T1(void)
    {
        x = 1;                  // data race!
        WRITE_ONCE(flag, 1);    // correct: smp_store_release(&flag, 1)
    }
    void T2(void)
    {
        while (!READ_ONCE(flag));   // correct: smp_load_acquire(&flag)
        ... = x;                    // data race!
    }

When weak memory modeling is enabled, KCSAN can consider ``x`` in ``T1`` for
simulated reordering. After the write of ``flag``, ``x`` is again checked for
concurrent accesses: because ``T2`` is able to proceed after the write of
``flag``, a data race is detected. With the correct barriers in place, ``x``
would not be considered for reordering after the proper release of ``flag``,
and no data race would be detected.

Deliberate trade-offs in complexity but also practical limitations mean only a
subset of data races due to missing memory barriers can be detected. With
currently available compiler support, the implementation is limited to modeling
the effects of "buffering" (delaying accesses), since the runtime cannot
"prefetch" accesses. Also recall that watchpoints are only set up for plain
accesses, and the only access type for which KCSAN simulates reordering. This
means reordering of marked accesses is not modeled.

A consequence of the above is that acquire operations do not require barrier
instrumentation (no prefetching). Furthermore, marked accesses introducing
address or control dependencies do not require special handling (the marked
access cannot be reordered, later dependent accesses cannot be prefetched).

Key Properties
~~~~~~~~~~~~~~

1. **Memory Overhead:**  The overall memory overhead is only a few MiB
   depending on configuration. The current implementation uses a small array of
   longs to encode watchpoint information, which is negligible.

2. **Performance Overhead:** KCSAN's runtime aims to be minimal, using an
   efficient watchpoint encoding that does not require acquiring any shared
   locks in the fast-path. For kernel boot on a system with 8 CPUs:

   - 5.0x slow-down with the default KCSAN config;
   - 2.8x slow-down from runtime fast-path overhead only (set very large
     ``KCSAN_SKIP_WATCH`` and unset ``KCSAN_SKIP_WATCH_RANDOMIZE``).

3. **Annotation Overheads:** Minimal annotations are required outside the KCSAN
   runtime. As a result, maintenance overheads are minimal as the kernel
   evolves.

4. **Detects Racy Writes from Devices:** Due to checking data values upon
   setting up watchpoints, racy writes from devices can also be detected.

5. **Memory Ordering:** KCSAN is aware of only a subset of LKMM ordering rules;
   this may result in missed data races (false negatives).

6. **Analysis Accuracy:** For observed executions, due to using a sampling
   strategy, the analysis is *unsound* (false negatives possible), but aims to
   be complete (no false positives).

Alternatives Considered
-----------------------

An alternative data race detection approach for the kernel can be found in the
`Kernel Thread Sanitizer (KTSAN) <https://github.com/google/ktsan/wiki>`_.
KTSAN is a happens-before data race detector, which explicitly establishes the
happens-before order between memory operations, which can then be used to
determine data races as defined in `Data Races`_.

To build a correct happens-before relation, KTSAN must be aware of all ordering
rules of the LKMM and synchronization primitives. Unfortunately, any omission
leads to large numbers of false positives, which is especially detrimental in
the context of the kernel which includes numerous custom synchronization
mechanisms. To track the happens-before relation, KTSAN's implementation
requires metadata for each memory location (shadow memory), which for each page
corresponds to 4 pages of shadow memory, and can translate into overhead of
tens of GiB on a large system.


code:
.. SPDX-License-Identifier: GPL-2.0
.. Copyright (C) 2020, Google LLC.

Kernel Electric-Fence (KFENCE)
==============================

Kernel Electric-Fence (KFENCE) is a low-overhead sampling-based memory safety
error detector. KFENCE detects heap out-of-bounds access, use-after-free, and
invalid-free errors.

KFENCE is designed to be enabled in production kernels, and has near zero
performance overhead. Compared to KASAN, KFENCE trades performance for
precision. The main motivation behind KFENCE's design, is that with enough
total uptime KFENCE will detect bugs in code paths not typically exercised by
non-production test workloads. One way to quickly achieve a large enough total
uptime is when the tool is deployed across a large fleet of machines.

Usage
-----

To enable KFENCE, configure the kernel with::

    CONFIG_KFENCE=y

To build a kernel with KFENCE support, but disabled by default (to enable, set
``kfence.sample_interval`` to non-zero value), configure the kernel with::

    CONFIG_KFENCE=y
    CONFIG_KFENCE_SAMPLE_INTERVAL=0

KFENCE provides several other configuration options to customize behaviour (see
the respective help text in ``lib/Kconfig.kfence`` for more info).

Tuning performance
~~~~~~~~~~~~~~~~~~

The most important parameter is KFENCE's sample interval, which can be set via
the kernel boot parameter ``kfence.sample_interval`` in milliseconds. The
sample interval determines the frequency with which heap allocations will be
guarded by KFENCE. The default is configurable via the Kconfig option
``CONFIG_KFENCE_SAMPLE_INTERVAL``. Setting ``kfence.sample_interval=0``
disables KFENCE.

The sample interval controls a timer that sets up KFENCE allocations. By
default, to keep the real sample interval predictable, the normal timer also
causes CPU wake-ups when the system is completely idle. This may be undesirable
on power-constrained systems. The boot parameter ``kfence.deferrable=1``
instead switches to a "deferrable" timer which does not force CPU wake-ups on
idle systems, at the risk of unpredictable sample intervals. The default is
configurable via the Kconfig option ``CONFIG_KFENCE_DEFERRABLE``.

.. warning::
   The KUnit test suite is very likely to fail when using a deferrable timer
   since it currently causes very unpredictable sample intervals.

The KFENCE memory pool is of fixed size, and if the pool is exhausted, no
further KFENCE allocations occur. With ``CONFIG_KFENCE_NUM_OBJECTS`` (default
255), the number of available guarded objects can be controlled. Each object
requires 2 pages, one for the object itself and the other one used as a guard
page; object pages are interleaved with guard pages, and every object page is
therefore surrounded by two guard pages.

The total memory dedicated to the KFENCE memory pool can be computed as::

    ( #objects + 1 ) * 2 * PAGE_SIZE

Using the default config, and assuming a page size of 4 KiB, results in
dedicating 2 MiB to the KFENCE memory pool.

Note: On architectures that support huge pages, KFENCE will ensure that the
pool is using pages of size ``PAGE_SIZE``. This will result in additional page
tables being allocated.

Error reports
~~~~~~~~~~~~~

A typical out-of-bounds access looks like this::

    ==================================================================
    BUG: KFENCE: out-of-bounds read in test_out_of_bounds_read+0xa6/0x234

    Out-of-bounds read at 0xffff8c3f2e291fff (1B left of kfence-#72):
     test_out_of_bounds_read+0xa6/0x234
     kunit_try_run_case+0x61/0xa0
     kunit_generic_run_threadfn_adapter+0x16/0x30
     kthread+0x176/0x1b0
     ret_from_fork+0x22/0x30

    kfence-#72: 0xffff8c3f2e292000-0xffff8c3f2e29201f, size=32, cache=kmalloc-32

    allocated by task 484 on cpu 0 at 32.919330s:
     test_alloc+0xfe/0x738
     test_out_of_bounds_read+0x9b/0x234
     kunit_try_run_case+0x61/0xa0
     kunit_generic_run_threadfn_adapter+0x16/0x30
     kthread+0x176/0x1b0
     ret_from_fork+0x22/0x30

    CPU: 0 PID: 484 Comm: kunit_try_catch Not tainted 5.13.0-rc3+ #7
    Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-2 04/01/2014
    ==================================================================

The header of the report provides a short summary of the function involved in
the access. It is followed by more detailed information about the access and
its origin. Note that, real kernel addresses are only shown when using the
kernel command line option ``no_hash_pointers``.

Use-after-free accesses are reported as::

    ==================================================================
    BUG: KFENCE: use-after-free read in test_use_after_free_read+0xb3/0x143

    Use-after-free read at 0xffff8c3f2e2a0000 (in kfence-#79):
     test_use_after_free_read+0xb3/0x143
     kunit_try_run_case+0x61/0xa0
     kunit_generic_run_threadfn_adapter+0x16/0x30
     kthread+0x176/0x1b0
     ret_from_fork+0x22/0x30

    kfence-#79: 0xffff8c3f2e2a0000-0xffff8c3f2e2a001f, size=32, cache=kmalloc-32

    allocated by task 488 on cpu 2 at 33.871326s:
     test_alloc+0xfe/0x738
     test_use_after_free_read+0x76/0x143
     kunit_try_run_case+0x61/0xa0
     kunit_generic_run_threadfn_adapter+0x16/0x30
     kthread+0x176/0x1b0
     ret_from_fork+0x22/0x30

    freed by task 488 on cpu 2 at 33.871358s:
     test_use_after_free_read+0xa8/0x143
     kunit_try_run_case+0x61/0xa0
     kunit_generic_run_threadfn_adapter+0x16/0x30
     kthread+0x176/0x1b0
     ret_from_fork+0x22/0x30

    CPU: 2 PID: 488 Comm: kunit_try_catch Tainted: G    B             5.13.0-rc3+ #7
    Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-2 04/01/2014
    ==================================================================

KFENCE also reports on invalid frees, such as double-frees::

    ==================================================================
    BUG: KFENCE: invalid free in test_double_free+0xdc/0x171

    Invalid free of 0xffff8c3f2e2a4000 (in kfence-#81):
     test_double_free+0xdc/0x171
     kunit_try_run_case+0x61/0xa0
     kunit_generic_run_threadfn_adapter+0x16/0x30
     kthread+0x176/0x1b0
     ret_from_fork+0x22/0x30

    kfence-#81: 0xffff8c3f2e2a4000-0xffff8c3f2e2a401f, size=32, cache=kmalloc-32

    allocated by task 490 on cpu 1 at 34.175321s:
     test_alloc+0xfe/0x738
     test_double_free+0x76/0x171
     kunit_try_run_case+0x61/0xa0
     kunit_generic_run_threadfn_adapter+0x16/0x30
     kthread+0x176/0x1b0
     ret_from_fork+0x22/0x30

    freed by task 490 on cpu 1 at 34.175348s:
     test_double_free+0xa8/0x171
     kunit_try_run_case+0x61/0xa0
     kunit_generic_run_threadfn_adapter+0x16/0x30
     kthread+0x176/0x1b0
     ret_from_fork+0x22/0x30

    CPU: 1 PID: 490 Comm: kunit_try_catch Tainted: G    B             5.13.0-rc3+ #7
    Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-2 04/01/2014
    ==================================================================

KFENCE also uses pattern-based redzones on the other side of an object's guard
page, to detect out-of-bounds writes on the unprotected side of the object.
These are reported on frees::

    ==================================================================
    BUG: KFENCE: memory corruption in test_kmalloc_aligned_oob_write+0xef/0x184

    Corrupted memory at 0xffff8c3f2e33aff9 [ 0xac . . . . . . ] (in kfence-#156):
     test_kmalloc_aligned_oob_write+0xef/0x184
     kunit_try_run_case+0x61/0xa0
     kunit_generic_run_threadfn_adapter+0x16/0x30
     kthread+0x176/0x1b0
     ret_from_fork+0x22/0x30

    kfence-#156: 0xffff8c3f2e33afb0-0xffff8c3f2e33aff8, size=73, cache=kmalloc-96

    allocated by task 502 on cpu 7 at 42.159302s:
     test_alloc+0xfe/0x738
     test_kmalloc_aligned_oob_write+0x57/0x184
     kunit_try_run_case+0x61/0xa0
     kunit_generic_run_threadfn_adapter+0x16/0x30
     kthread+0x176/0x1b0
     ret_from_fork+0x22/0x30

    CPU: 7 PID: 502 Comm: kunit_try_catch Tainted: G    B             5.13.0-rc3+ #7
    Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.14.0-2 04/01/2014
    ==================================================================

For such errors, the address where the corruption occurred as well as the
invalidly written bytes (offset from the address) are shown; in this
representation, '.' denote untouched bytes. In the example above ``0xac`` is
the value written to the invalid address at offset 0, and the remaining '.'
denote that no following bytes have been touched. Note that, real values are
only shown if the kernel was booted with ``no_hash_pointers``; to avoid
information disclosure otherwise, '!' is used instead to denote invalidly
written bytes.

And finally, KFENCE may also report on invalid accesses to any protected page
where it was not possible to determine an associated object, e.g. if adjacent
object pages had not yet been allocated::

    ==================================================================
    BUG: KFENCE: invalid read in test_invalid_access+0x26/0xe0

    Invalid read at 0xffffffffb670b00a:
     test_invalid_access+0x26/0xe0
     kunit_try_run_case+0x51/0x85
     kunit_generic_run_threadfn_adapter+0x16/0x30
     kthread+0x137/0x160
     ret_from_fork+0x22/0x30

    CPU: 4 PID: 124 Comm: kunit_try_catch Tainted: G        W         5.8.0-rc6+ #7
    Hardware name: QEMU Standard PC (i440FX + PIIX, 1996), BIOS 1.13.0-1 04/01/2014
    ==================================================================

DebugFS interface
~~~~~~~~~~~~~~~~~

Some debugging information is exposed via debugfs:

* The file ``/sys/kernel/debug/kfence/stats`` provides runtime statistics.

* The file ``/sys/kernel/debug/kfence/objects`` provides a list of objects
  allocated via KFENCE, including those already freed but protected.

Implementation Details
----------------------

Guarded allocations are set up based on the sample interval. After expiration
of the sample interval, the next allocation through the main allocator (SLAB or
SLUB) returns a guarded allocation from the KFENCE object pool (allocation
sizes up to PAGE_SIZE are supported). At this point, the timer is reset, and
the next allocation is set up after the expiration of the interval.

When using ``CONFIG_KFENCE_STATIC_KEYS=y``, KFENCE allocations are "gated"
through the main allocator's fast-path by relying on static branches via the
static keys infrastructure. The static branch is toggled to redirect the
allocation to KFENCE. Depending on sample interval, target workloads, and
system architecture, this may perform better than the simple dynamic branch.
Careful benchmarking is recommended.

KFENCE objects each reside on a dedicated page, at either the left or right
page boundaries selected at random. The pages to the left and right of the
object page are "guard pages", whose attributes are changed to a protected
state, and cause page faults on any attempted access. Such page faults are then
intercepted by KFENCE, which handles the fault gracefully by reporting an
out-of-bounds access, and marking the page as accessible so that the faulting
code can (wrongly) continue executing (set ``panic_on_warn`` to panic instead).

To detect out-of-bounds writes to memory within the object's page itself,
KFENCE also uses pattern-based redzones. For each object page, a redzone is set
up for all non-object memory. For typical alignments, the redzone is only
required on the unguarded side of an object. Because KFENCE must honor the
cache's requested alignment, special alignments may result in unprotected gaps
on either side of an object, all of which are redzoned.

The following figure illustrates the page layout::

    ---+-----------+-----------+-----------+-----------+-----------+---
       | xxxxxxxxx | O :       | xxxxxxxxx |       : O | xxxxxxxxx |
       | xxxxxxxxx | B :       | xxxxxxxxx |       : B | xxxxxxxxx |
       | x GUARD x | J : RED-  | x GUARD x | RED-  : J | x GUARD x |
       | xxxxxxxxx | E :  ZONE | xxxxxxxxx |  ZONE : E | xxxxxxxxx |
       | xxxxxxxxx | C :       | xxxxxxxxx |       : C | xxxxxxxxx |
       | xxxxxxxxx | T :       | xxxxxxxxx |       : T | xxxxxxxxx |
    ---+-----------+-----------+-----------+-----------+-----------+---

Upon deallocation of a KFENCE object, the object's page is again protected and
the object is marked as freed. Any further access to the object causes a fault
and KFENCE reports a use-after-free access. Freed objects are inserted at the
tail of KFENCE's freelist, so that the least recently freed objects are reused
first, and the chances of detecting use-after-frees of recently freed objects
is increased.

If pool utilization reaches 75% (default) or above, to reduce the risk of the
pool eventually being fully occupied by allocated objects yet ensure diverse
coverage of allocations, KFENCE limits currently covered allocations of the
same source from further filling up the pool. The "source" of an allocation is
based on its partial allocation stack trace. A side-effect is that this also
limits frequent long-lived allocations (e.g. pagecache) of the same source
filling up the pool permanently, which is the most common risk for the pool
becoming full and the sampled allocation rate dropping to zero. The threshold
at which to start limiting currently covered allocations can be configured via
the boot parameter ``kfence.skip_covered_thresh`` (pool usage%).

Interface
---------

The following describes the functions which are used by allocators as well as
page handling code to set up and deal with KFENCE allocations.

.. kernel-doc:: include/linux/kfence.h
   :functions: is_kfence_address
               kfence_shutdown_cache
               kfence_alloc kfence_free __kfence_free
               kfence_ksize kfence_object_start
               kfence_handle_page_fault

Related Tools
-------------

In userspace, a similar approach is taken by `GWP-ASan
<http://llvm.org/docs/GwpAsan.html>`_. GWP-ASan also relies on guard pages and
a sampling strategy to detect memory unsafety bugs at scale. KFENCE's design is
directly influenced by GWP-ASan, and can be seen as its kernel sibling. Another
similar but non-sampling approach, that also inspired the name "KFENCE", can be
found in the userspace `Electric Fence Malloc Debugger
<https://linux.die.net/man/3/efence>`_.

In the kernel, several tools exist to debug memory access errors, and in
particular KASAN can detect all bug classes that KFENCE can detect. While KASAN
is more precise, relying on compiler instrumentation, this comes at a
performance cost.

It is worth highlighting that KASAN and KFENCE are complementary, with
different target environments. For instance, KASAN is the better debugging-aid,
where test cases or reproducers exists: due to the lower chance to detect the
error, it would require more effort using KFENCE to debug. Deployments at scale
that cannot afford to enable KASAN, however, would benefit from using KFENCE to
discover bugs due to code paths not exercised by test cases or fuzzers.