Home

Kernel Thread Sanitizer (KTSAN)

This page is about the KTSAN happens-before data-race detector. For an alternative approach using watchpoints, see Kernel Concurrency Sanitizer (KCSAN).

Overview

A dynamic data race error detector for Linux kernel.

An early prototype based on Linux kernel 4.2 is available. The development is on hold, but will be resumed at some point. A rebase onto Linux kernel 4.20 by @anatol can be found here.

More extensive documentation can be found here.

The list of found bugs is available here.

Other random reports produced by the tool can be found here. Some of them might be false positive.

To symbolize the reports you can use our symbolizer script. The example of usage can be found on kasan homepage.

All the documentation below is written with the old 4.2 version in mind.

Building And Running

Kernel

Build kernel with ktsan:

git clone https://github.com/google/ktsan.git
cd ktsan/
make defconfig
make kvmconfig
scripts/config -e KTSAN -e SLAB -d SLUB -e DEBUG_INFO
yes '' | make oldconfig
make -j64 LOCALVERSION=-tsan

Install QEMU:

sudo apt-get install kvm qemu-kvm

Create a minimal Debian-wheezy image:

# Enable promptless ssh to the machine for root with RSA keys
mkdir debian-stable
sudo debootstrap --include=openssh-server stable debian-stable
sudo sed -i '/^root/ { s/:x:/::/ }' debian-stable/etc/passwd
sudo mkdir debian-stable/root/.ssh/
mkdir ssh
ssh-keygen -f ssh/id_rsa -t rsa -N ''
cat ssh/id_rsa.pub | sudo tee debian-stable/root/.ssh/authorized_keys

# Download and install trinity
sudo chroot debian-stable /bin/bash -c "apt-get update; apt-get -y install curl tar gcc make sysbench time"
sudo chroot debian-stable /bin/bash -c "mkdir -p ~; cd ~/; wget https://github.com/kernelslacker/trinity/archive/v1.9.tar.gz -O trinity-1.9.tar.gz; tar -xf trinity-1.9.tar.gz"
sudo chroot debian-stable /bin/bash -c "cd ~/trinity-1.9 ; ./configure ; make -j16 ; make install"

# Build and install perf
cp -r $KTSAN debian-stable/tmp/
sudo chroot debian-stable /bin/bash -c "apt-get install -y flex bison python-dev libelf-dev libunwind7-dev libaudit-dev libslang2-dev libperl-dev binutils-dev liblzma-dev libnuma-dev"
sudo chroot debian-stable /bin/bash -c "cd /tmp/ktsan/tools/perf/; make"
sudo chroot debian-stable /bin/bash -c "cp /tmp/ktsan/tools/perf/perf /usr/bin/"
rm -r debian-stable/tmp/ktsan

# Install other packages you might need
sudo chroot debian-stable /bin/bash -c "apt-get install -y git vim screen usbutils"

# Build a disk image 
sudo virt-make-fs --format=qcow2 --size=+200M debian-stable rootfs.img

Make a copy of the original image (the image file will be modified by QEMU):

cp rootfs.img rootfs-dirty.img

Run QEMU:

qemu-system-x86_64 \
  -drive file=rootfs-dirty.img,index=0 \
  -m 20G -smp 4 \
  -net user,hostfwd=tcp::10022-:22 -net nic \
  -nographic \
  -kernel arch/x86/boot/bzImage -append "console=ttyS0 root=/dev/sda rw debug earlyprintk=serial slub_debug=QUZ"\
  -enable-kvm -cpu host

# Note: on CentOS: -net nic,vlan=0,model=e1000

To stop QEMU press Ctrl+A then X

To run Trinity:

ssh -i ssh/id_rsa -p 10022 -o "StrictHostKeyChecking no" root@localhost "trinity --dangerous -q -m -C 16"

Other

Rebasing on a new kernel release

Right now there are two branches with KTSAN-related changes: tsan and tsan-fixes. The tsan-fixes branch only contains fixes to the upstream kernel. The tsan branch contains both, KTSAN changes and fixes from tsan-fixes.

When rebasing KTSAN on a new kernel release, do the following:

1. Pull changes from upstream master to local master.
2. Rebase tsan-fixes on top of master.
3. Rebase tsan on top of master leaving out the commits that are in tsan-fixes.
4. Merge tsan-fixes into tsan.
5. Push master, tsan and tsan-fixes to origin.

It's possible to automate step 3 using this script:

# When on tsan branch:
GIT_SEQUENCE_EDITOR=./magic.py git rebase -i master

Some implementation ideas

• Make some internal structures per CPU instead of per thread (VC cache, what else?). VCs themselves stay per thread.
• Monitor some kernel thread scheduler events (thread execution started/stopped on CPU).
• Disable interrupts during TSan events (kernel scheduler events, synchronization events) (CLI, STI).
• Use 4 bytes per slot: 1 for thread id, 2 for clock, 1 for everything else (flags, ...).
• Different threads might have the same thread id (only 256 different values available).
• When clock overflows it is possible to change thread id and connect "old" and "new" threads with a happens-before relation.
• Find races in both kmalloc and vmalloc ranges.
• Use two-level shadow memory mapping scheme for now.
• Do a flush when we run out of clocks. The flush might work as follows. There is a global epoch variable which is increased during each flush. Each thread have a local epoch variable. When a thread is starting it will flush itself if the thread local epoch is less than the global one.