Stopping data races using Redflag

Abstract

Although sophisticated runtime bug detection tools exist to root out all kinds of concurrency problems, the data they need is often not accessible at the kernel level; examining every potentially concurrent memory access for a system as central as a kernel is not feasible.

This thesis shows our runtime analysis system Redflag which brings these essential tools to the Linux kernel. Redflag has three components: custom GCC plug-ins for in kernel instrumentation, a logging system to record instrumented points, and at its core, an improved Lockset algorithm for the Linux kernel.

We used GCC plug-ins to instrument read and writes to global memory locations, memory allocations, and locks—including seldom-addressed locking primitives like RCU’s. Our fast logging system can log any event caught by instrumentation. The logging system is also optimized using zero-copy I/O in the kernel, and various in-kernel optimizations for improved performance.

We customized the classic Lockset algorithm to prune false positives caused by subtle kernel synchronization. We present a number of techniques we applied to improve the accuracy of our analysis. We tested our system on several file systems including Wrapfs, Btrfs, and the kernel’s VFS layer and found 2 real races and several benign races. We also injected data races in the kernel and our system was able to detect them accurately. Redflag’s false positive rates are very low for most of the file systems.

Our system is versatile using a small automation language to make it easy to run and use. Redflag can help kernel developers in finding data races in the Linux kernel, and is easily applicable to other operating systems and asynchronous systems as well.