Home

KernelThreadSanitizer (KTSan)

Overview

A dynamic data race error detector for Linux kernel. Currently in development.

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.

Building And Running

GCC

Since ktsan uses compiler instrumentation, a custom GCC is required. You can get the gcc patch here.

svn checkout svn://gcc.gnu.org/svn/gcc/trunk $GCC_KTSAN
cd $GCC_KTSAN
svn up -r 227162
patch -p0 -i gcc_ktsan.patch 
mkdir build
mkdir install
cd build/
sudo apt-get install flex bison libc6-dev libc6-dev-i386 libgmp3-dev libmpfr-dev libmpc-dev
../configure --enable-languages=c,c++ --disable-bootstrap --enable-checking=no --with-gnu-as --with-gnu-ld --with-ld=/usr/bin/ld.bfd --prefix=$GCC_KTSAN/install/
make -j64
make install

Kernel

There are two ways to try out ktsan: use QEMU or use VirtualBox and Vagrant.

QEMU

Build kernel with ktsan:

git clone https://github.com/google/ktsan.git
cd ktsan/
make defconfig
make kvmconfig
# Edit .config to set CONFIG_KTSAN=y
# Edit .config to unset CONFIG_SLUB and set CONFIG_SLAB=y
# Edit .config to set CONFIG_DEBUG_INFO=y
make oldconfig
make CC='$GCC_KTSAN/install/bin/gcc' -j64 LOCALVERSION=-tsan

mkdir -p mod_install && rm -rf mod_install/*
INSTALL_MOD_PATH=mod_install make CC='$GCC_KTSAN/install/bin/gcc' -j64 modules_install LOCALVERSION=-tsan
chmod -R a+rwx mod_install

Install QEMU:

sudo apt-get install kvm qemu-kvm

Create a minimal Debian-wheezy image:

mkdir wheezy
sudo debootstrap --include=openssh-server wheezy wheezy

# Enable promptless ssh to the machine for root with RSA keys
sudo sed -i '/^root/ { s/:x:/::/ }' wheezy/etc/passwd
echo 'V0:23:respawn:/sbin/getty 115200 hvc0' | sudo tee -a wheezy/etc/inittab
printf '\nauto eth0\niface eth0 inet dhcp\n' | sudo tee -a wheezy/etc/network/interfaces
sudo mkdir wheezy/root/.ssh/
mkdir ssh
ssh-keygen -f ssh/id_rsa -t rsa -N ''
cat ssh/id_rsa.pub | sudo tee wheezy/root/.ssh/authorized_keys

# Download and install trinity
sudo chroot wheezy /bin/bash -c "apt-get update; ( yes | apt-get install curl tar gcc make sysbench time )"
sudo chroot wheezy /bin/bash -c "mkdir -p ~; cd ~/ ; curl http://codemonkey.org.uk/projects/trinity/trinity-1.4.tar.xz -o trinity-1.4.tar.xz ; tar -xf trinity-1.4.tar.xz"
sudo chroot wheezy /bin/bash -c "cd ~/trinity-1.4 ; ./configure.sh ; make -j16 ; make install"

# Build and install perf
cp -r $KTSAN wheezy/tmp/
sudo chroot wheezy /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 wheezy /bin/bash -c "cd /tmp/ktsan/tools/perf/; make"
sudo chroot wheezy /bin/bash -c "cd /tmp/ktsan/tools/perf/; make install"
rm -r wheezy/tmp/ktsan

# Build a disk image 
dd if=/dev/zero of=wheezy.img bs=1M seek=1024 count=1
mkfs.ext4 -F wheezy.img
sudo mkdir -p /mnt/wheezy
sudo mount -o loop wheezy.img /mnt/wheezy
sudo cp -a wheezy/. /mnt/wheezy/.
sudo umount /mnt/wheezy

To run the kernel you need to make a copy of the image file you created (the image file will be modified when QEMU is ran, so the easiest way to restore to the initial state is to keep the original image):

cp wheezy.img wheezy-dirty.img
qemu-system-x86_64 \
  -hda wheezy-dirty.img \
  -m 20G -smp 4 \
  -net user,hostfwd=tcp::10022-:22 -net nic \
  -nographic \
  -kernel arch/x86/boot/bzImage -append "console=ttyS0 root=/dev/sda debug earlyprintk=serial slub_debug=QUZ"\
  -virtfs local,id=r,path=mod_install,security_model=none,writeout=immediate,mount_tag=mount_host \
  -enable-kvm \
  -pidfile vm_pid \
  > vm_log &

To stop QEMU:

kill $(cat vm_pid)

VirtualBox and Vagrant

Warning: these instructions might be outdated.

Build kernel deb packages with ktsan enabled:

git clone https://github.com/google/ktsan.git ktsan
svn checkout http://address-sanitizer.googlecode.com/svn/trunk/vagrant_kasan vagrant
cp vagrant/kernel_config ktsan/.config
cd ktsan/
make oldconfig  # select KTSAN option
make CC='$GCC_KTSAN/install/bin/gcc' -j64 deb-pkg LOCALVERSION=-tsan

The deb packages will appear in the ktsan parent directory.

To use the current non-stable development version, checkout tsan-dev branch instead.

Install VirtualBox and Vagrant. It's better to download newer versions from their official sites other than use the ones from the apt repository. These instructions were written for VirtualBox 4.3.16 and Vagrant 1.6.5.

Copy new kernel to vagrant:

cd vagrant/
vagrant up
vagrant ssh-config > ssh_config
scp -F ./ssh_config linux-* default:/home/vagrant/
vagrant ssh -c "sudo dpkg -i linux-headers-3.16.0-tsan_3.16.0-tsan-2_amd64.deb && sudo dpkg -i linux-libc-dev_3.16.0-tsan-2_amd64.deb && sudo dpkg -i linux-image-3.16.0-tsan_3.16.0-tsan-2_amd64.deb"
vagrant reload

Details

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.

TODO

• Handle more synchronization primitives
  • spinlock (done)
  • rwlock (done)
  • sema (via spinlocks)
  • rwsem (done)
  • completion (via spinlocks)
  • mutex (done)
  • ww_mutex?
  • atomics (done)
  • atomics + memory barriers
  • atomic bitops (done)
  • thread start/join (via spinlocks and completions)
  • rcu, rcu_bh, rcu_sched (done)
  • srcu
  • bit_lock (via bitops)
• Intercept memcpy and friends
• Support non SMP build with ktsan
• Fix false negatives in tests
• Handle events from interrupts (started in tsan-dev branch)
• Use READ_ONCE/ASSIGN_ONCE to fix races instead of atomics (https://lkml.org/lkml/2014/12/3/890)