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.
|Commitee:||Johnson, Rob, Stoller, Scott|
|School:||State University of New York at Stony Brook|
|School Location:||United States -- New York|
|Source:||MAI 48/06M, Masters Abstracts International|
|Keywords:||Data race, GCC plug-ins, Kernel, Linux, Locksets, Race detection|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be