Deadlocks are one of the most notorious concurrency bugs, and significant research has focused on detecting them efficiently. Dynamic predictive analyses work by observing concurrent executions, and reason about alternative interleavings that can witness concurrency bugs. Such techniques offer scalability and sound bug reports, and have emerged as an effective approach for concurrency bug detection, such as data races. Effective dynamic deadlock prediction, however, has proven a challenging task, as no deadlock predictor currently meets the requirements of soundness, high-precision, and efficiency.
In this paper, we first formally establish that this tradeoff is unavoidable, by showing that (a) sound and complete deadlock prediction is intractable, in general, and (b) even the seemingly simpler task of determining the presence of potential deadlocks, which often serve as unsound witnesses for actual predictable deadlocks, is intractable. The main contribution of this work is a new class of predictable deadlocks, called sync(hronization)-preserving deadlocks. Informally, these are deadlocks that can be predicted by reordering the observed execution while preserving the relative order of conflicting critical sections. We present two algorithms for sound deadlock prediction based on this notion. Our first algorithm SPDOffline detects all sync-preserving deadlocks, with running time that is linear per abstract deadlock pattern, a novel notion also introduced in this work. Our second algorithm SPDOnline predicts all sync-preserving deadlocks that involve two threads in a strictly online fashion, runs in overall linear time, and is better suited for a runtime monitoring setting.
We implemented both our algorithms and evaluated their ability to perform offline and online deadlock-prediction on a large dataset of standard benchmarks. Our results indicate that our new notion of sync-preserving deadlocks is highly effective, as (i) it can characterize the vast majority of deadlocks and (ii) it can be detected using an online, sound, complete and highly efficient algorithm.
Tue 20 JunDisplayed time zone: Eastern Time (US & Canada) change
13:40 - 15:40 | PLDI: Analysis & OptimizationsPLDI Research Papers at Cypress 2 Chair(s): Fredrik Kjolstad Stanford University | ||
13:40 20mTalk | Collecting Cyclic Garbage across Foreign Function Interfaces: Who Takes the Last Piece of Cake? PLDI Research Papers Tetsuro Yamazaki University of Tokyo, Tomoki Nakamaru University of Tokyo, Ryota Shioya University of Tokyo, Tomoharu Ugawa University of Tokyo, Shigeru Chiba The University of Tokyo DOI | ||
14:00 20mTalk | Modular Hardware Design with Timeline Types PLDI Research Papers Rachit Nigam Cornell University, Pedro Henrique Azevedo de Amorim Cornell University, Adrian Sampson Cornell University DOI Pre-print | ||
14:20 20mTalk | Efficient Parallel Functional Programming with Effects PLDI Research Papers Jatin Arora Carnegie Mellon University, Sam Westrick Carnegie Mellon University, Umut A. Acar Carnegie Mellon University DOI | ||
14:40 20mTalk | Better Defunctionalization through Lambda Set Specialization PLDI Research Papers William Brandon MIT CSAIL, Benjamin Driscoll Stanford University, Wilson Berkow UC Berkeley, Frank Dai UC Berkeley, Mae Milano University of California at Berkeley DOI | ||
15:00 20mTalk | Sound Dynamic Deadlock Prediction in Linear Time PLDI Research Papers Hünkar Can Tunç Aarhus University, Umang Mathur National University of Singapore, Andreas Pavlogiannis Aarhus University, Mahesh Viswanathan University of Illinois at Urbana-Champaign DOI Pre-print | ||
15:20 20mTalk | Context Sensitivity without Contexts: A Cut-Shortcut Approach to Fast and Precise Pointer Analysis PLDI Research Papers Wenjie Ma Nanjing University, Shengyuan Yang Nanjing University, Tian Tan Nanjing University, Xiaoxing Ma Nanjing University, Chang Xu Nanjing University, Yue Li Nanjing University DOI Pre-print | ||
