[PATCH RFC 0/2] kcov: collect early boot coverage of init_task

[Yunseong Kim <yunseong.kim@est.tech>]

This RFC adds a way to collect KCOV coverage of the boot path, from
right after early parameter parsing in start_kernel() up to
rest_init(), and to read it back from userspace after boot.

Motivation
==========

1. The boot path depends heavily on the configuration

Reviewing the boot path by reading the code is hard, even if you stop
at rest_init(). start_kernel() looks like a flat list of calls, but
what runs below it depends on the kernel configuration, the
architecture, the firmware, the command line, static keys and
alternatives. Many of the calls are empty stubs in one configuration
and large subsystems in another, and a lot of the work happens in
inline helpers in headers.

Even the top-level files are full of configuration branches.
init/main.c has 13 lines with #ifdef CONFIG_*/IS_ENABLED(CONFIG_*),
mm/mm_init.c has 34 and arch/x86/kernel/setup.c has 36, and each
branch leads into code with its own branches. Some examples from the
x86_64 test setup described below:

  - Without KCOV_INSTRUMENT_NOISY, a boot records 17.3M basic block
    executions before rest_init(). 10.4M of them (60%) come from the
    step where arch_cpu_finalize_init() applies the alternatives. With
    the retpoline and rethunk mitigations enabled, that is mostly
    apply_retpolines(), apply_returns() and the x86 instruction
    decoder they use (93% of the step in the NOISY=y boot below).
    apply_retpolines() and apply_returns() are empty stubs unless
    MITIGATION_RETPOLINE/MITIGATION_RETHUNK are set.
  - The tracing options (FUNCTION_TRACER, EVENT_TRACING,
    FTRACE_SYSCALLS) add another 6.0M executions (35%) in ftrace_init()
    and trace_init(), which set up the ftrace call sites, the trace
    events and the syscall metadata.
  - Of the 11,131 distinct PCs executed (with KCOV_INSTRUMENT_NOISY),
    544 are in tracing code, which only runs with the tracing options,
    and 500 are in ACPI code, which depends on CONFIG_ACPI and on the
    firmware providing ACPI tables.

In total, the part of start_kernel() between parse_early_param() and
rest_init() executes 11,131 distinct PCs in 1,529 functions spread
over 568 source files (10,877 source lines). 131 of those files are
under arch/x86 and 109 are headers in include/linux. A different
.config, CPU or firmware gives a different set, and reading the source
cannot tell you which set your kernel runs. You have to work it out
again for every configuration.

2. Early ftrace does not show the code that actually runs

The function tracer is the usual tool for looking at early boot, but
it cannot answer "which code ran":

  - It starts late. Boot-time function tracing (ftrace=function)
    begins in tracer_alloc_buffers(), called from early_trace_init().
    Nothing before that point can be traced: setup_arch(),
    setup_per_cpu_areas(), and mm_core_init() with
    build_all_zonelists(), memblock_free_all() and the slab and
    vmalloc setup. (This series does not cover setup_arch() yet
    either, see the limitations below.) Even inside the window this
    series covers, 2,758 of the 11,131 distinct PCs (25%) are first
    reached before early_trace_init().

  - It works at function granularity. It records that a function was
    entered, not which branches inside it were taken. Those branches
    are exactly where the configuration and the hardware differences
    show up.

  - It does not see inlined code. 1,739 of the functions executed
    during this window were only ever executed inlined, and 4,912 of
    the 11,131 PCs (44%) are in inlined code. None of this has an
    fentry call site.

  - Large parts of the kernel are built without ftrace hooks. lib/
    and kernel/trace/ remove CC_FLAGS_FTRACE for the whole directory,
    and kernel/, mm/, lib/, init/, arch/x86/ and drivers/acpi/ have
    55 more per-object CFLAGS_REMOVE lines doing the same. Early KCOV
    covers 30 files in lib/ alone.

  - Its buffer is sized for events, not for loops. The ring buffer
    defaults to 1,441,792 bytes per CPU (TRACE_BUF_SIZE_DEFAULT) in
    overwrite mode. With boot loops calling the same functions
    millions of times, the earliest events are overwritten unless
    trace_buf_size= is raised a lot.

ftrace remains the right tool for timing and call order. Early KCOV
answers a different question: which basic blocks ran, in which order
they were first reached, including inlined and non-traceable code,
starting before the tracing infrastructure exists.

3. A learning and review tool

With this series the executed path becomes a concrete, ordered list
that can be resolved with addr2line against vmlinux and read next to
the source, for exactly the configuration and machine being booted.
This is useful for people learning the kernel, and for reviewers who
want to check which code a boot-time change really affects. That use
stands on its own: even if this is not accepted upstream, I intend to
keep it as a learning tool.

4. Coverage-guided fuzzing of boot-time input

A lot of input is parsed while the kernel boots: the command line and
early parameters, bootconfig, ACPI tables, the e820 map, the device
tree. For confidential guests (TDX, SEV-SNP) much of it is provided by
an untrusted host. KCOV cannot give coverage feedback for any of this
today, since collection only starts once userspace opens
/sys/kernel/debug/kcov. A fuzzer that boots a VM with mutated inputs
could use the early coverage as its feedback signal.

5. Comparing boots

Diffing the coverage of two boots shows how two configurations,
command lines, CPUs or kernel versions take different paths, and the
first-hit order shows where they diverge.

What the series does
====================

Patch 1/2: kcov: collect early boot coverage of init_task

  a) Collection, behind the new CONFIG_EARLY_KCOV (default n)

  - early_kcov_init() is called right after parse_early_param() in
    start_kernel(). It allocates a buffer with memblock_alloc(),
    attaches it to init_task and enables KCOV_MODE_TRACE_PC. The size
    defaults to CONFIG_EARLY_KCOV_SIZE_MB (256) and can be changed with
    early_kcov_size=; 0 disables the collection. The memparse() result
    is range checked as a 64-bit value before it is narrowed.
  - early_kcov_stop() (__init) is the first statement of rest_init().
    It disables collection and detaches the buffer from init_task.
  - A late_initcall frees the unused tail of the buffer and creates
    /sys/kernel/debug/early_kcov (0600). It uses the regular KCOV
    layout: word 0 is the number of PCs, then the PCs. They are
    canonicalized (KASLR offset removed) like other KCOV data, so they
    match vmlinux directly. The tail is freed there rather than in
    rest_init() because memblock memory can only be returned once
    deferred struct page init has completed. If the file cannot be
    created, the whole buffer is freed.
  - Writing to the file removes it and frees the rest of the buffer.
    I would have liked "rm" for this, but debugfs directories have no
    ->unlink. The removal runs from a work item, because
    debugfs_remove() waits for the write to return. Readers holding an
    open file descriptor get an error afterwards.
  - __sanitizer_cov_trace_pc() is not changed, so KCOV users that do
    not enable CONFIG_EARLY_KCOV are not affected.

  b) CONFIG_KCOV_INSTRUMENT_NOISY (depends on CONFIG_EARLY_KCOV)

  Many objects are built with KCOV_INSTRUMENT := n because their
  coverage is not a function of syscall inputs: the scheduler, RCU,
  locking, the page and slab allocators, parts of lib/, stack
  unwinding. That is the right choice for fuzzing, but for the boot
  path it hides sched_init(), build_all_zonelists() and much of mm
  setup.

  The new option makes those sites instrumented. The sites use a new
  kbuild helper,

      KCOV_INSTRUMENT_foo.o := $(kcov-noisy)

  which expands to "n" unless the option is set. Only sites whose
  comment says they were excluded for noise are converted. Sites
  excluded because instrumentation is unsafe are left alone: kcov.o,
  kernel/entry, head64, x86 cpu/common.o, tlb.c and mem_encrypt*.c,
  stackdepot, and the KASAN/KMSAN/KCSAN runtimes. This patch converts
  the generic sites. With the option off, the build is unchanged: no
  object was recompiled, and page_alloc.o, rcu/tree.o and string.o
  have no coverage callbacks.

  c) Documentation

  early_kcov_size= is documented in kernel-parameters.txt, and
  Documentation/dev-tools/kcov.rst gets an "Early boot coverage"
  section: configuration, the covered window, the file format, how to
  decode it with addr2line against vmlinux, how to release it, and the
  kcov-noisy convention.

Patch 2/2: x86/kcov: allow instrumenting noisy objects for early boot
coverage

  Converts the x86 sites excluded only for noise: apic/, delay.o, and
  the stacktrace, dumpstack and unwinder objects. The objects excluded
  because the kernel hangs or does not boot when they are instrumented
  (head64.o, cpu/common.o, perf_event.o, tlb.c, mem_encrypt*.c,
  pgprot.c) stay excluded, as do machine_kexec_64.o and physaddr.o
  (kexec invalidates the GS base). Other architectures are not
  converted, since x86 is what I could test.

Measurements
============

Test setup: x86_64 QEMU guest under virtme-ng, 4 vCPUs in 2 NUMA
nodes, GCC 16.2, the virtme-ng default config plus the options below,
on the base commit given at the end. The config has FUNCTION_TRACER,
the retpoline/rethunk mitigations and X86_FRED enabled. Each boot used
early_kcov_size=512M so that nothing was truncated.

  NOISY  RAM   PCs recorded  buffer used  distinct PCs
  -----  ----  ------------  -----------  ------------
  n      2G       17.3M       132 MiB          8,837
  n      4G       17.4M       133 MiB          8,864
  n      8G       17.5M       133 MiB          8,861
  y      2G       31.6M       241 MiB         11,131
  y      4G       34.8M       265 MiB         11,194
  y      8G       41.2M       314 MiB         11,169

Without the noisy objects the volume barely depends on the amount of
memory. With them it grows by about 1.6M PCs per GiB, from freeing
pages to the buddy allocator. The 256 MiB default holds a full
boot without the noisy objects, and with them up to about 2G of RAM.
When the buffer is too small, the remaining PCs are dropped and the
log says "buffer full, coverage truncated".

Where the executions go, attributed to the start_kernel() call that
was running (NOISY=y, 2G, 31.6M executions in total):

  executions       share  new distinct PCs  start_kernel() step
  ----------       -----  ----------------  -------------------
  14.3M            45.3%         603        trace_init()
  11.1M            35.2%       1,091        calibrate_delay() and
                                            arch_cpu_finalize_init()
   3.0M             9.4%       1,466        mm_core_init()
   2.7M             8.6%         254        ftrace_init()
   0.2M             0.5%         493        pr_info() in early_kcov_init()
   0.07M            0.2%       1,690        acpi_early_init()
   0.05M            0.2%         862        vfs_caches_init()

arch_cpu_finalize_init() is in arch/x86/kernel/cpu/common.c, which is
not instrumented, so its alternatives patching is counted together
with calibrate_delay(), the call before it. With the noisy objects,
the lib/string.c helpers (strstr(), strncmp(), memcmp(), strcmp())
are 73% of trace_init(). Going from 2G to 8G adds 9.6M executions,
96% of them in __free_pages_ok() and __free_pages_core(). The steps
with few executions are often the ones that reach the most new code:
acpi_early_init() is 0.2% of the executions but 15% of the distinct
PCs.

How to reproduce
================

The essential commands, from a tree with the series applied and no
.config. virtme-ng adds what it needs to boot, including
CONFIG_DEBUG_INFO_DWARF_TOOLCHAIN_DEFAULT=y for addr2line.

  # Build
  vng --build --configitem CONFIG_KCOV=y \
      --configitem CONFIG_KCOV_INSTRUMENT_ALL=y \
      --configitem CONFIG_EARLY_KCOV=y \
      --configitem CONFIG_KCOV_INSTRUMENT_NOISY=y \
      --configitem CONFIG_DEBUG_FS=y --configitem CONFIG_NUMA=y

  # Boot with 2 NUMA nodes, save the coverage in the current directory
  # and release the kernel buffer. --rw gives the guest write access to
  # the host file system, which is how the file reaches the host.
  vng -r arch/x86/boot/bzImage --rw --user root --cpus 4 --memory 2G \
      --numa 1G,cpus=0-1 --numa 1G,cpus=2-3 \
      --exec 'dmesg | grep kcov:;
              cat /sys/kernel/debug/early_kcov > early_kcov.raw;
              echo 1 > /sys/kernel/debug/early_kcov'

  # Resolve the distinct PCs
  od -An -v -t x8 -w8 -j8 early_kcov.raw | awk '{ print "0x" $1 }' |
      sort -u | addr2line -f -e vmlinux

The helper script I used to build, boot, measure and decode (it
produced the tables above with "measure" and "decode --stats") is not
part of the series. It is available at:

  https://gist.github.com/yskzalloc/44d2e20b48f4971fd4ab91756369b526

Testing
=======

  - Booted with and without NUMA, 1G to 8G of RAM, with buffers from
    8M to 512M, with early_kcov_size=0 (disabled) and with
    early_kcov_size=64G (rejected as out of range, "Malformed early
    option", default kept).
  - The last recorded PC is in rest_init() (init/main.c:745), and
    nothing from kernel_init() or the initcalls shows up.
  - After writing to /sys/kernel/debug/early_kcov the file is gone, the
    log shows "Freeing early boot coverage memory: 235932K", and a read
    on a file descriptor opened before the release fails.
  - Normal KCOV from userspace still works after boot with the noisy
    objects instrumented, and no warnings show up in the log.
  - Builds with CONFIG_EARLY_KCOV=n and with CONFIG_KCOV=n. The changed
    C files build without warnings at W=1, and checkpatch is clean
    apart from the missing Signed-off-by in my local tree. I could not
    build the HTML documentation (no Sphinx here).

Limitations and planned extensions
==================================

Collection currently covers parse_early_param() to rest_init(). Two
extensions would make it much more useful:

1. Start at the top of start_kernel()

   setup_arch() runs before collection starts and is not covered,
   though it holds the most firmware-facing code. On x86 it calls
   e820__memory_setup(), parse_early_param() (so the generic call in
   start_kernel() does nothing there), e820__memblock_setup(),
   acpi_boot_table_init(), early_acpi_boot_init(), initmem_init(),
   which does NUMA discovery, and acpi_boot_init(). For the fuzzing use
   case, this is the code that matters most.

   memblock is not usable until e820__memblock_setup(), so starting
   earlier needs statically allocated __initdata storage, and a full
   trace does not fit in any reasonable static buffer. Collection also
   needs current and the per-CPU preempt count to be valid. That holds
   at the top of start_kernel() on x86, but has to be checked on other
   architectures. Code that runs before start_kernel() (head64,
   startup) is already built with KCOV_INSTRUMENT := n.

2. Continue past rest_init()

   After rest_init(), pid 1 runs kernel_init() -> kernel_init_freeable():
   workqueue_init(), do_pre_smp_initcalls(), smp_init(),
   sched_init_smp(), page_alloc_init_late(), then do_basic_setup() ->
   driver_init() and do_initcalls(), until free_initmem() and
   run_init_process(). Driver probing and most device/firmware input
   handling happen here.

   pid 1 is created by kernel_clone() in rest_init(), and
   kcov_task_init() resets the child's KCOV state, so the buffer would
   have to be handed over to pid 1 explicitly. Work done in other
   threads (kthreadd, kworkers for async probing, the deferred page
   init threads, per-CPU threads) is not covered by per-task KCOV.
   That would need remote coverage (kcov_remote_start()) at the
   relevant points, or a boot-only global mode. I would like advice on
   which is acceptable.

Other limits:

  - The data can only be read after a successful boot. If boot fails,
    it is only reachable from a crash dump or a debugger.
  - Interrupt entry code that runs before the hardirq count is raised
    (for example the x86 FRED system vector wrappers) is recorded as
    if init_task executed it, and such a PC can occasionally be
    overwritten by the interrupted task. This is the existing KCOV
    behaviour and is described in kcov.rst.
  - Functions marked noinstr are never covered.
  - Only x86_64 has been tested.

Changes since the previous internal version
===========================================

  - Added CONFIG_EARLY_KCOV; the feature was on for every KCOV kernel.
  - Dropped the "unique" mode that recorded each PC only once. It
    needed a bitmap check in __sanitizer_cov_trace_pc() and loses the
    execution order and repetition that a trace gives, which GCOV
    already covers for "what ran". __sanitizer_cov_trace_pc() is now
    unchanged.
  - CONFIG_KCOV_INSTRUMENT_NOISY now depends on CONFIG_EARLY_KCOV.
  - Writing to /sys/kernel/debug/early_kcov releases the buffer.
  - early_kcov_size= is range checked before narrowing (32-bit),
    early_kcov_stop() is __init, the documentation describes the
    covered window accurately, and kcov.rst documents the interface.

Questions
=========

1. Is early boot coverage something kernel/kcov.c should carry, or is
   it better kept out of tree?

2. Is a write to the debugfs file an acceptable way to release the
   buffer, or would you prefer a different interface?

3. Is the kcov-noisy helper the right way to opt in, or would you
   prefer a different mechanism? The subsystem maintainers of the
   converted Makefiles would be Cc'ed on a non-RFC posting.

4. Is there interest in the two extensions above, in particular for
   fuzzing boot-time input?

Signed-off-by: Yunseong Kim <yunseong.kim@est.tech>
---
Yunseong Kim (2):
      kcov: collect early boot coverage of init_task
      x86/kcov: allow instrumenting noisy objects for early boot coverage

 Documentation/admin-guide/kernel-parameters.txt |  17 +++
 Documentation/dev-tools/kcov.rst                |  60 ++++++++
 arch/x86/kernel/Makefile                        |  12 +-
 arch/x86/kernel/apic/Makefile                   |   2 +-
 arch/x86/lib/Makefile                           |   2 +-
 include/linux/kcov.h                            |  13 ++
 init/main.c                                     |   4 +
 kernel/Makefile                                 |   6 +-
 kernel/kcov.c                                   | 184 ++++++++++++++++++++++++
 kernel/locking/Makefile                         |   2 +-
 kernel/module/Makefile                          |   2 +-
 kernel/rcu/Makefile                             |   2 +-
 kernel/sched/Makefile                           |   2 +-
 lib/Kconfig.debug                               |  45 ++++++
 lib/Makefile                                    |  14 +-
 mm/Makefile                                     |  20 +--
 scripts/Kbuild.include                          |   6 +
 17 files changed, 361 insertions(+), 32 deletions(-)
---
base-commit: d135ab453a7400a34930bdda1ef4bdc8acfac80e
change-id: 20261027-early-kcov-0f5f370b4bed

Best regards,
--  
Yunseong Kim <yunseong.kim@est.tech>