AsyncClock
Authors:
Open Access
- 4 April 2017
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM SIGPLAN Notices
- Vol. 52 (4) , 193-205
Abstract
Asynchronous programming model is commonly used in mobile systems and Web 2.0 environments. Asynchronous race detectors use algorithms that are an order of magnitude performance and space inefficient compared to conventional data race detectors. We solve this problem by identifying and addressing two important problems in reasoning about causality between asynchronous events. Unlike conventional signal-wait operations, establishing causal order between two asynchronous events is fundamentally more challenging as there is no common handle they operate on. We propose a new primitive named AsyncClock that addresses this problem by explicitly tracking causally preceding events, and show that AsyncClock can handle a wide variety of asynchronous causality models. We also address the important scalability problem of efficiently identifying heirless events whose metadata can be reclaimed. We built the first single-pass, non-graph-based Android race detector using our algorithm and applied it to find errors in 20 popular applications. Our tool incurs about 6x performance overhead, which is several times more efficient than the state-of-the-art solution. It also scales well with the execution length. We used our tool to find 147 previously unknown harmful races.Keywords
Funding Information
- MARCO/DARPA (C-FAR)
- NSF (CCF 1527301, CAREER 1149773)
- Intel
This publication has 13 references indexed in Scilit:
- Scalable race detection for Android applications2015
- Race detection for Android applications2014
- Effective race detection for event-driven programs2013
- Race detection for web applications2012
- RELAY2007
- RacerX2003
- Accordion Clocks: Logical Clocks for Data Race Detection2001
- Optimal tracing and replay for debugging shared-memory parallel programs1993
- Detecting data races on weak memory systemsACM SIGARCH Computer Architecture News, 1991
- A compression technique to materialize transitive closureACM Transactions on Database Systems, 1990