Andrey Konovalov edited this page May 28, 2018 · 43 revisions

KernelThreadSanitizer (KTSan)

Overview

A dynamic data race error detector for Linux kernel.

Right now an early prototype based on Linux kernel 4.2 is available. The development is on hold, but will be resumed at some point.

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.

# TODO: update to GCC 5.2
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 linux-libc-dev linux-libc-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

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

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; apt-get -y install curl tar gcc make sysbench time"
sudo chroot wheezy /bin/bash -c "mkdir -p ~; cd ~/; wget https://github.com/kernelslacker/trinity/archive/v1.5.tar.gz -O trinity-1.5.tar.gz; tar -xf trinity-1.5.tar.gz"
sudo chroot wheezy /bin/bash -c "cd ~/trinity-1.5 ; ./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 "cp /tmp/ktsan/tools/perf/perf /usr/bin/"
rm -r wheezy/tmp/ktsan

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

# 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

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

cp wheezy.img wheezy-dirty.img

Run QEMU:

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"\
  -enable-kvm \
  -pidfile vm_pid \
  > vm_log &

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

To stop QEMU:

kill $(cat vm_pid)

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.
Clone this wiki locally
You can’t perform that action at this time.
You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session.
Press h to open a hovercard with more details.