Article

Efficient and precise datarace detection for multithreaded object-oriented programs

Authors:

Jong-Deok Choi,

Alexey Loginov,

Robert O'Callahan,

Manu SridharanAuthors Info & Claims

PLDI '02: Proceedings of the ACM SIGPLAN 2002 conference on Programming language design and implementation

Pages 258 - 269

https://doi.org/10.1145/512529.512560

Published: 17 May 2002 Publication History

Abstract

We present a novel approach to dynamic datarace detection for multithreaded object-oriented programs. Past techniques for on-the-fly datarace detection either sacrificed precision for performance, leading to many false positive datarace reports, or maintained precision but incurred significant overheads in the range of 3x to 30x. In contrast, our approach results in very few false positives and runtime overhead in the 13% to 42% range, making it both efficient and precise. This performance improvement is the result of a unique combination of complementary static and dynamic optimization techniques.

References

[1]

A. Aiken and D. Gay. Barrier inference. In Proceedings of the 25th Symposium on Principles of Programming Languages (POPL), pages 342--354, January 1998

Digital Library

[2]

B. Alpern, et.al. The Jalapeño virtual machine. IBM Systems Journal, 39(1), 2000

Digital Library

[3]

D. F. Bacon, R. E. Strom, and A. Tarafdar. Guava: A dialect of java without data races. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, 2000

Digital Library

[4]

B. Blanchet. Escape analysis for object oriented languages: Application to Java. In Proceedings of ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, Denver, Colorado, November 1999

Digital Library

[5]

J. Bodga and U. Hölzle. Removing unnecessay synchronization in Java. In Proceedings of ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, Denver, Colorado, November 1999

Digital Library

[6]

C. Boyapati and M. Rinard. A parameterized type system for race-free java programs. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, 2001

Digital Library

[7]

M. Burke, P. Carini, J.-D. Choi, and M. Hind. Flow-insensitive interprocedural alias analysis in the presence of pointers. In 7th International Workshop on Languages and Compilers for Parallel Computing, 1994. Extended version published as Research Report RC 19546, IBM T. J. Watson Research Center, September, 1994

Digital Library

[8]

G.-I. Cheng, M. Feng, C. E. Leiserson, K. H. Randall, and A. F. Stark. Detecting data races in Cilk programs that use locks. Proceedings of the Tenth Annual ACM Symposium on Parallel Algorithms and Architectures, 1998

Digital Library

[9]

J.-D. Choi, B. Alpern, T. Ngo, M. Sridharan, and J. Vlissides. A perturbation-free replay platform for cross-optimized multithreaded applications. In Proceedings of the 15th IEEE International Parallel & Distributed Processing Symposium, April 2001

Digital Library

[10]

J.-D. Choi, M. Gupta, M. Serrano, V. C. Sreedhar, and S. Midkiff. Escape analysis for Java. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, pages 1--19, 1999

Digital Library

[11]

J.-D. Choi, A. Loginov, and V. Sarkar. Static datarace analysis for multithreaded object-oriented programs. Technical report, IBM Research, 2001. Report RC22146; www.research.ibm.com/jalapeno/dejavu/

[12]

J.-D. Choi and S. L. Min. Race frontier: Reproducing data races in parallel-program debugging. In Proceedings of Third ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, April 1991

Digital Library

[13]

M. Christiaens and K. De Bosschere. TRaDe, a topological approach to on-the-fly race detection in java programs. Proceedings of the Java Virtual Machine Rsearch and Technology Symposium (JVM'01), April 2001

Digital Library

[14]

A. Dinning and E. Schonberg. Detecting access anomalies in programs with critical sections. Proceedings of the ACM/ONR Workshop on Parallel and Distributed Debugging, published in ACM SIGPLAN Notices, 26(12):85--96, 1991

Digital Library

[15]

C. Flanagan and S. N. Freund. Type-based race detection for java. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 219--232, June 2000

Digital Library

[16]

E. Fredkin. Trie memory. Communications of the ACM, 3(9):490--499, September 1960

Digital Library

[17]

KL Group, 260 King Street East, Toronto, Ontario, Canada. Getting Started with JProbe

[18]

Kuck & Associates, Inc., 1906 Fox Drive, Champaign, IL 61820-7345, USA. AssureJ User's Manual, 2.0 Edition, March 1999

[19]

S. L. Min and J.-D. Choi. An efficient cache-based access anomaly detection scheme. In Proceedings of 4th International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS), April 1991

Digital Library

[20]

R. H. Netzer and B. P. Miller. What are race conditions? some issues and formalizations. ACM Letters on Programming Languages and Systems, 1(1):74--88, Mar. 1992

Digital Library

[21]

C. v. Praun and T. Gross. Object race detection. In ACM Conference on Object-Oriented Programming Systems, Languages, and Applications, 2001

Digital Library

[22]

B. Richards and J. R. Larus. Protocol-based data-race detection. In Proceedings of the ACM SIGMETRICS Symposium on Parallel and Distributed Tools, pages 40--47, August 1998

Digital Library

[23]

E. Ruf. Effective synchronzation removal for Java. In SIGPLAN 2000 Conference on Programming Language Design and Implementation, pages 208--218, 2000

Digital Library

[24]

S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. E. Anderson. Eraser: A dynamic data race detector for multi-threaded programs. ACM Transactions on Computer Systems, 15(4):391--411, 1997

Digital Library

[25]

E. Schonberg. On-The-Fly detection of access anomalies. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pages 285--297, June 1989

Digital Library

[26]

B. Steensgaard. Points-to analysis in almost linear time. In In Proceedings of the Twentythird Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL), pages 32--41, January 1996

Digital Library

[27]

N. Sterling. Warlock: A static data race analysis tool. In USENIX Winter Technical Conference, pages 97--106, 1993

Cited By

Anand AAdithya SRustagi SSeth PSundaresan VMaier DNandivada VThakur M(2024)Optimistic Stack Allocation and Dynamic Heapification for Managed RuntimesProceedings of the ACM on Programming Languages10.1145/36563898:PLDI(296-319)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656389
Sun XGupta RBond MLee JPayer H(2024)SSRD: Shapes and Summaries for Race Detection in Concurrent Data StructuresProceedings of the 2024 ACM SIGPLAN International Symposium on Memory Management10.1145/3652024.3665505(68-81)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3652024.3665505
Guo YZhu SCai YHe LZhang JRoychoudhury APaiva AAbreu RStorey M(2024)Reorder Pointer Flow in Sound Concurrency Bug PredictionProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3623300(1-13)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3623300
Show More Cited By

Index Terms

Efficient and precise datarace detection for multithreaded object-oriented programs
1. Computing methodologies
  1. Concurrent computing methodologies
    1. Concurrent programming languages
2. Software and its engineering
  1. Software creation and management
    1. Software verification and validation
      1. Software defect analysis
        Software testing and debugging
  2. Software notations and tools
    1. General programming languages
      1. Language types
        Concurrent programming languages
        Object oriented languages

Recommendations

Efficient and precise datarace detection for multithreaded object-oriented programs

We present a novel approach to dynamic datarace detection for multithreaded object-oriented programs. Past techniques for on-the-fly datarace detection either sacrificed precision for performance, leading to many false positive datarace reports, or ...
On-the-fly race detection in multi-threaded programs
PADTAD '08: Proceedings of the 6th workshop on Parallel and distributed systems: testing, analysis, and debugging

Multi-core chips enable parallel processing for general purpose applications. Unfortunately, parallel programs may contain synchronization defects. Such defects are difficult to detect due to nondeterministic interleavings of parallel threads. Current ...
Fault detection in multi-threaded c++ server applications
PPoPP '07: Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming

This paper describes experiments with the freely available tool Helgrind, results obtained by using it for debugging a server application comprising 500 kLOC. We present improvements to the run time analysis of C++ programs that result in a dramatic ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PLDI '02: Proceedings of the ACM SIGPLAN 2002 conference on Programming language design and implementation

June 2002

338 pages

ISBN:1581134630

DOI:10.1145/512529

General Chair:
Jens Knoop
Universität Dortmund, Germany
,
Program Chair:
Laurie J. Hendren
McGill University, Canada

ACM SIGPLAN Notices Volume 37, Issue 5
May 2002
326 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/543552
Issue’s Table of Contents

Copyright © 2002 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 May 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PLDI02

Sponsor:

SIGPLAN

PLDI02: ACM SIGPLAN 2002 Conference on Programming Language Design and Implementation

June 17 - 19, 2002

Berlin, Germany

Acceptance Rates

PLDI '02 Paper Acceptance Rate 28 of 169 submissions, 17%;

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

361
Total Citations
View Citations
1,641
Total Downloads

Downloads (Last 12 months)24
Downloads (Last 6 weeks)4

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Anand AAdithya SRustagi SSeth PSundaresan VMaier DNandivada VThakur M(2024)Optimistic Stack Allocation and Dynamic Heapification for Managed RuntimesProceedings of the ACM on Programming Languages10.1145/36563898:PLDI(296-319)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656389
Sun XGupta RBond MLee JPayer H(2024)SSRD: Shapes and Summaries for Race Detection in Concurrent Data StructuresProceedings of the 2024 ACM SIGPLAN International Symposium on Memory Management10.1145/3652024.3665505(68-81)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3652024.3665505
Guo YZhu SCai YHe LZhang JRoychoudhury APaiva AAbreu RStorey M(2024)Reorder Pointer Flow in Sound Concurrency Bug PredictionProceedings of the IEEE/ACM 46th International Conference on Software Engineering10.1145/3597503.3623300(1-13)Online publication date: 20-May-2024
https://dl.acm.org/doi/10.1145/3597503.3623300
Chen SLin ZZhang YCalandrino JTroncoso C(2023)Controlled data races in enclavesProceedings of the 32nd USENIX Conference on Security Symposium10.5555/3620237.3620465(4069-4086)Online publication date: 9-Aug-2023
https://dl.acm.org/doi/10.5555/3620237.3620465
Thokair MZhang MMathur UViswanathan M(2023)Dynamic Race Detection with O(1) SamplesProceedings of the ACM on Programming Languages10.1145/35712387:POPL(1308-1337)Online publication date: 11-Jan-2023
https://dl.acm.org/doi/10.1145/3571238
Shahare VChabbi MHegde NAgrawal KShun J(2023)Protecting Locks Against Unbalanced Unlock()Proceedings of the 35th ACM Symposium on Parallelism in Algorithms and Architectures10.1145/3558481.3591091(199-211)Online publication date: 17-Jun-2023
https://dl.acm.org/doi/10.1145/3558481.3591091
Lepers BGiet JZwaenepoel WLawall JFedorova ANarayanan DDi Luna GQuerzoni L(2023)OFence: Pairing Barriers to Find Concurrency Bugs in the Linux KernelProceedings of the Eighteenth European Conference on Computer Systems10.1145/3552326.3567504(33-45)Online publication date: 8-May-2023
https://dl.acm.org/doi/10.1145/3552326.3567504
Rahman SLi CShi AGrundy J(2023)TSVD4J: Thread-Safety Violation Detection for JavaProceedings of the 45th International Conference on Software Engineering: Companion Proceedings10.1109/ICSE-Companion58688.2023.00029(78-82)Online publication date: 14-May-2023
https://dl.acm.org/doi/10.1109/ICSE-Companion58688.2023.00029
Bai JChen QJiang ZLawall JHu S(2022)Hybrid Static-Dynamic Analysis of Data Races Caused by Inconsistent Locking Discipline in Device DriversIEEE Transactions on Software Engineering10.1109/TSE.2021.3138735(1-1)Online publication date: 2022
https://doi.org/10.1109/TSE.2021.3138735
Gong SAltinbüken DFonseca PManiatis P(2021)SnowboardProceedings of the ACM SIGOPS 28th Symposium on Operating Systems Principles10.1145/3477132.3483549(66-83)Online publication date: 26-Oct-2021
https://dl.acm.org/doi/10.1145/3477132.3483549
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents