Efficient Timestamping for Sampling-Based Race Detection
Minjian Zhang, Daniel Wee Soong Lim, Mosaad Al Thokair, Umang Mathur, Mahesh Viswanathan
Abstract
Dynamic race detection based on the happens before (HB) partial order has now become the de facto approach to quickly identify data races in multi-threaded software. Most practical implementations for detecting these races use timestamps to infer causality between events and detect races based on these timestamps. Such an algorithm updates timestamps (stored in vector clocks) at every event in the execution, and is known to induce excessive overhead. Random sampling has emerged as a promising algorithmic paradigm to offset this overhead. It offers the promise of making sound race detection scalable. In this work we consider the task of designing an efficient sampling based race detector with low overhead for timestamping when the number of sampled events is much smaller than the total events in an execution. To solve this problem, we propose (1) a new notion of freshness timestamp , (2) a new data structure to store timestamps, and (3) an algorithm that uses a combination of them to reduce the cost of timestamping in sampling based race detection. Further, we prove that our algorithm is close to optimal — the number of vector clock traversals is bounded by the number of sampled events and number of threads, and further, on any given dynamic execution, the cost of timestamping due to our algorithm is close to the amount of work any timestamping-based algorithm must perform on that execution, that is it is instance optimal. Our evaluation on real world benchmarks demonstrates the effectiveness of our proposed algorithm over prior timestamping algorithms that are agnostic to sampling.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
1 top-tier paper has cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- The Complexity of Dynamic Data Race Prediction cites Fast, sound, and effectively complete dynamic race prediction
- SmartTrack: efficient predictive race detection cites Fast, sound, and effectively complete dynamic race prediction
- Optimal prediction of synchronization-preserving races cites The Complexity of Dynamic Data Race Prediction
- Optimal prediction of synchronization-preserving races cites Fast, sound, and effectively complete dynamic race prediction
- Optimal prediction of synchronization-preserving races cites SmartTrack: efficient predictive race detection
Cited by top-tier papers1
Builds on16
- Truly stateless, optimal dynamic partial order reductionMichalis Kokologiannakis, Iason Marmanis, Vladimir Gladstein, Viktor VafeiadisPOPL 2022 · 46 citations
- Fast, sound, and effectively complete dynamic race predictionAndreas PavlogiannisPOPL 2020 · 46 citations
- Optimal prediction of synchronization-preserving racesUmang Mathur, Andreas Pavlogiannis, Mahesh ViswanathanPOPL 2021 · 36 citations
- SmartTrack: efficient predictive race detectionJake Roemer, Kaan Genç, Michael D. BondPLDI 2020 · 28 citations
- The Complexity of Dynamic Data Race PredictionUmang Mathur, Andreas Pavlogiannis, Mahesh ViswanathanLICS 2020 · 27 citations
Related papers
- Dynamic Race Detection with O(1) SamplesMosaad Al Thokair, Minjian Zhang, Umang Mathur, Mahesh ViswanathanPOPL 2023 · 9 citations
- A tree clock data structure for causal orderings in concurrent executionsUmang Mathur, Andreas Pavlogiannis, Hünkar Can Tunç, Mahesh ViswanathanASPLOS 2022 · 10 citations
- Optimistic Prediction of Synchronization-Reversal Data RacesZheng Shi, Umang Mathur, Andreas PavlogiannisICSE 2024 · 8 citations
- Detecting concurrency vulnerabilities based on partial orders of memory and thread eventsKunpeng Yu, Chenxu Wang, Yan Cai, Xiapu Luo et al.FSE 2021 · 9 citations
- NodeRT: Detecting Races in Node.js Applications PracticallyJingyao Zhou, Lei Xu, Gongzheng Lu, Weifeng Zhang et al.ISSTA 2023 · 1 citation
