Home

ThreadSanitizer for Linux kernel

Overview

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

More extensive documentation is available here.

Some reports produced by the tool can be found here. There might be false positive reports.

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

Building And Running

Building 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 218317
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

TODO

VirtualBox and Vagrant

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)