Skip to content

Latest commit

 

History

History
378 lines (277 loc) · 11.6 KB

measure-kernel-mcdc.md

File metadata and controls

378 lines (277 loc) · 11.6 KB

Measure Linux Kernel's MC/DC

Note

The following instructions use LLVM >= 19 and patch >= v0.5. The differences between LLVM 18 and >= 19 can be found here.

0. Prerequisites

  • The following instructions are tested with:

    • Architecture: x86_64
    • Distro: Ubuntu 22.04 and Debian trixie/sid
    • Host kernel version: 5.15.0-86-generic

    Other settings (e.g. Arm) can possibly work, but they are not fully tested.

  • Larger than 24G of main memory is recommended for successfully linking the kernel image.

  • If we don't plan to build LLVM from source, please reserve ~15G of disk space; otherwise reserve ~20G.

1. Install dependencies

# For building LLVM from source (optional)
sudo apt-get install cmake ninja-build mold

# For building the kernel
sudo apt-get install git bc libncurses-dev wget busybox \
    libssl-dev libelf-dev dwarves flex bison build-essential

# For booting the kernel
sudo apt-get install qemu-system-x86

2. Pull the source code and apply patches

cd /path/to/our/workdir
export MCDC_HOME=$(realpath .)

# This meta repository
git clone https://github.com/xlab-uiuc/linux-mcdc.git --branch llvm-trunk
# LLVM if we want to build it from source (optional)
git clone https://github.com/llvm/llvm-project.git --branch main --depth 5
# Linux kernel
git clone https://git.kernel.org/pub/scm/linux/kernel/git/stable/linux.git --branch v5.15.153 --depth 5

# Apply kernel patches
cd $MCDC_HOME/linux
git apply $MCDC_HOME/linux-mcdc/patches/v0.6/0001-llvm-cov-add-Clang-s-Source-based-Code-Coverage-supp.patch
git apply $MCDC_HOME/linux-mcdc/patches/v0.6/0002-kbuild-llvm-cov-disable-instrumentation-in-odd-or-se.patch
git apply $MCDC_HOME/linux-mcdc/patches/v0.6/0003-llvm-cov-add-Clang-s-MC-DC-support.patch
git apply $MCDC_HOME/linux-mcdc/patches/v0.6/0004-kbuild-llvm-cov-disable-instrumentation-in-odd-or-se.patch

3. Get LLVM

We can either

Build from source

cd $MCDC_HOME/llvm-project
$MCDC_HOME/linux-mcdc/scripts/build-llvm.sh

After the build script finishes, set $PATH up:

export PATH="$MCDC_HOME/llvm-project/build/bin:$PATH"

Install nightly packages

The essential steps are described below. For more information about these nightly packages, visit https://apt.llvm.org/.

Get the installation script:

cd /tmp
wget https://apt.llvm.org/llvm.sh
chmod +x llvm.sh

Install LLVM 20:

sudo ./llvm.sh 20

After installation, set $PATH up:

export PATH="/usr/lib/llvm-20/bin:$PATH"

4. Build the kernel

cd $MCDC_HOME/linux
make LLVM=1 defconfig

Starting with the default configuration, let's further enable the following groups of options:

  1. Features used by our QEMU wrapper script. E.g. 9p for easily moving data to/from the virtual machine.

    ./scripts/config -e CONFIG_9P_FS_POSIX_ACL
./scripts/config -e CONFIG_9P_FS
./scripts/config -e CONFIG_NET_9P_VIRTIO
./scripts/config -e CONFIG_NET_9P
./scripts/config -e CONFIG_PCI
./scripts/config -e CONFIG_VIRTIO_PCI
./scripts/config -e CONFIG_OVERLAY_FS
./scripts/config -e CONFIG_DEBUG_FS
./scripts/config -e CONFIG_CONFIGFS_FS
./scripts/config -e CONFIG_MAGIC_SYSRQ
make LLVM=1 olddefconfig

  2. Enable KUnit tests

    ./scripts/config -e CONFIG_KUNIT
./scripts/config -e CONFIG_KUNIT_ALL_TESTS
make LLVM=1 olddefconfig

  3. Enable MC/DC.

    ./scripts/config -e CONFIG_LLVM_COV_KERNEL
./scripts/config -e CONFIG_LLVM_COV_KERNEL_MCDC
./scripts/config --set-val LLVM_COV_KERNEL_MCDC_MAX_CONDITIONS 44
make LLVM=1 olddefconfig

    They are the options added by our kernel patch. In menuconfig mode, they are located under path -> "General architecture-dependent options" -> "Clang's source-based kernel coverage measurement (EXPERIMENTAL)" where we can find more detailed explanation for each.

    About LLVM_COV_KERNEL_MCDC_MAX_CONDITIONS and its value, please refer to this issue.

With all the configuration done, let's build the kernel.

make LLVM=1 -j$(nproc)

Note

At this stage we will see many warnings and the process will slow down near the end of building (LD, KSYMS etc).

This is expected. The warnings are due to two limitations of the current MC/DC implementation in Clang. Extra overhead is brought by code instrumentation (counters, bitmaps, MOV and ADD instructions to increment the counters), and coverage mapping in order to associate such information with the actual source code locations. Together they lead to larger binary size and longer linking time.

5. Boot the kernel and collect coverage

Boot the kernel using our QEMU wrapper script:

cd $MCDC_HOME/linux
$MCDC_HOME/linux-mcdc/scripts/q

(In case we have trouble booting: exit QEMU by first pressing Ctrl+A and then pressing X, check whether this post can solve the problem. If not, please open an Issue.)

If all goes well, during the booting process, KUnit tests will also be executed since we've enabled relevant options earlier. The results are printed to the kernel log in TAP format, like below:

[    4.524452]     # Subtest: qos-kunit-test
[    4.524453]     1..3
[    4.525259]     ok 1 - freq_qos_test_min
[    4.525750]     ok 2 - freq_qos_test_maxdef
[    4.526547]     ok 3 - freq_qos_test_readd
[    4.527282] # qos-kunit-test: pass:3 fail:0 skip:0 total:3
[    4.528000] # Totals: pass:3 fail:0 skip:0 total:3
[    4.528954] ok 17 - qos-kunit-test

Now we should have entered an interactive shell of the guest machine.

# (guest)
uname -a

The hostname part should be "guest", as specified here. The kernel version should be 5.15.153.

Let's inspect the directory added to debugfs by our patch:

# (guest)
ls /sys/kernel/debug/llvm-cov

which should contain two pseudo files: profraw and reset.

  • Writing to reset will clear the in-memory counters and bitmaps.
  • Reading profraw will serialize the in-memory counters and bitmaps in a proper format that is recognized by LLVM tools.

Let's copy the profile to current directory, which is shared with host directory $MCDC_HOME/linux through 9p, so that we can access the same file outside VM and complete the remaining steps on the host machine.

# (guest)
cp /sys/kernel/debug/llvm-cov/profraw .

Press Ctrl+D to exit the VM. We will get back to $MCDC_HOME/linux of the host and should have had a copy of profraw there.

# (host)
file profraw

The result should be:

profraw: LLVM raw profile data, version 10

Now we can analyze the profile and generate coverage reports in a similar way to what we would do to user space programs, as if vmlinux is the "executable":

mkdir -p $MCDC_HOME/analysis
mv profraw $MCDC_HOME/analysis
cd $MCDC_HOME/analysis

llvm-profdata merge profraw -o profdata
llvm-cov show --show-mcdc                                                      \
              --show-mcdc-summary                                              \
              --show-region-summary=false                                      \
              --show-branch-summary=false                                      \
              --format=html                                                    \
              -show-directory-coverage                                         \
              -output-dir=html-coverage-reports                                \
              -instr-profile profdata                                          \
              $MCDC_HOME/linux/vmlinux

The results will be put under $MCDC_HOME/analysis/html-coverage-reports.

Troubleshooting

For any trouble, feel free to open an Issue.

To assure ourselves nothing goes fundamentally wrong in the middle, we can also go to the "Code" view of this page, search for "Sanity check" hidden in comments and follow the instructions there.