Write a Blog >>
SPLASH 2017
Sun 22 - Fri 27 October 2017 Vancouver, Canada
Wed 25 Oct 2017 15:52 - 16:15 at Regency C - Dynamic Analysis Chair(s): Jonathan Aldrich

This paper presents Fast Instrumentation Bias (FIB), a sound and complete dynamic data race detection algorithm that improves performance by reducing or eliminating the costs of enforcing analysis atomicity. In addition to checking for errors in target programs, dynamic data race detectors must introduce synchronization to guard against \emph{metadata races} that may corrupt analysis state and compromise soundness or completeness. Pessimistic analysis synchronization can account for non-trivial parts of a data-race detector's performance overhead.

The core contribution of FIB is a novel cooperative ownership-based synchronization protocol whose states and transitions are derived purely from preexisting analysis metadata and logic in a standard data race detection algorithm. By exploiting work already done by the analysis or target program, FIB ensures atomicity of dynamic analysis actions with zero additional time or space cost in the common case. Analysis of temporally thread-local or read-shared accesses completes safely with no synchronization. Uncommon write-sharing transitions require synchronous cross-thread coordination to ensure common cases may proceed synchronization-free.

We implemented FIB in the Jikes RVM Java virtual machine. Experimental evaluation shows that FIB eliminates nearly all instrumentation atomicity costs on benchmarks where data often experience windows of (even temporary) thread-local access. Adaptive extensions to the ownership policy effectively eliminate high coordination costs of the core ownership protocol on benchmarks with high rates of serialized sharing. FIB outperforms a naive pessimistic synchronization scheme by 21% on average. Compared to a tuned optimistic metadata synchronization scheme based on conventional fine-grained atomic compare-and-swap operations, FIB is competitive overall, and up to 9% faster on some benchmarks. Overall, FIB effectively exploits latent analysis and program invariants to bring strong integrity guarantees to an otherwise unsynchronized data race detection algorithm at minimal cost.