Type
Text
Type
Thesis
Advisor
Scott Stoller | Zadok, Erez | Rob Johnson.
Date
2010-05-01
Keywords
Data Race, GCC Plug-ins, Kernel, Linux, Lockset, Race Detection | Computer Science
Department
Department of Computer Science
Language
en_US
Source
This work is sponsored by the Stony Brook University Graduate School in compliance with the requirements for completion of degree.
Identifier
http://hdl.handle.net/11401/70982
Publisher
The Graduate School, Stony Brook University: Stony Brook, NY.
Format
application/pdf
Abstract
Although sophisticated runtime bug detection tools exist to root outall kinds of concurrency problems, the data they need is often notaccessible at the kernel level; examining every potentially concurrentmemory access for a system as central as a kernel is not feasible.This thesis shows our runtime analysis system Redflag whichbrings these essential tools to the Linux kernel.Redflag has three components: custom GCC plug-ins for inkernel instrumentation, a logging system to record instrumentedpoints, and at its core, an improved Lockset algorithm for the Linuxkernel.We used GCC plug-ins to instrument read and writes to global memorylocations, memory allocations, and locks---including seldom-addressedlocking primitives like RCU's Our fast logging system can log any eventcaught by instrumentation. The logging system is also optimized usingzero-copy I/O in the kernel, and variousin-kernel optimizations for improved performance.We customized the classic Lockset algorithm to prune false positivescaused by subtle kernel synchronization. We present a number oftechniques we applied to improve the accuracy of our analysis We tested our system onseveral file systems including Wrapfs, Btrfs, and the kernel's VFS layerand found 2 real races and several benign races. We also injected data races in thekernel and our system was able to detect them accurately. Redflag'sfalse 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 runand use. Redflag can help kernel developers in finding data races inthe Linux kernel, and is easily applicable to other operating systemsand asynchronous systems as well.
Recommended Citation
Duggal, Abhinav, "Stopping Data Races Using Redflag" (2010). Stony Brook Theses and Dissertations Collection, 2006-2020 (closed to submissions). 190.
https://commons.library.stonybrook.edu/stony-brook-theses-and-dissertations-collection/190