skip to main content
10.1145/2814270.2814292acmconferencesArticle/Chapter ViewAbstractPublication PagessplashConference Proceedingsconference-collections
research-article

Valor: efficient, software-only region conflict exceptions

Published: 23 October 2015 Publication History

Abstract

Data races complicate programming language semantics, and a data race is often a bug. Existing techniques detect data races and define their semantics by detecting conflicts between synchronization-free regions (SFRs). However, such techniques either modify hardware or slow programs dramatically, preventing always-on use today. This paper describes Valor, a sound, precise, software-only region conflict detection analysis that achieves high performance by eliminating the costly analysis on each read operation that prior approaches require. Valor instead logs a region's reads and lazily detects conflicts for logged reads when the region ends. As a comparison, we have also developed FastRCD, a conflict detector that leverages the epoch optimization strategy of the FastTrack data race detector. We evaluate Valor, FastRCD, and FastTrack, showing that Valor dramatically outperforms FastRCD and FastTrack. Valor is the first region conflict detector to provide strong semantic guarantees for racy program executions with under 2X slowdown. Overall, Valor advances the state of the art in always-on support for strong behavioral guarantees for data races.

Supplementary Material

Auxiliary Archive (p241-biswas-s.zip)
This is the accompanying artifact for the paper "Valor: Efficient, Software-Only Region Conflict Exceptions". The artifact includes the following: a) a VM which contains an environment setup for quickly evaluating the ideas and the implementations presented in the paper, b) a patch on top of Jikes RVM 3.1.3 which can be used instead of the VM to extend the implementations, c) brief documentation on how to use the VM and the patch.

References

[1]
M. Abadi, C. Flanagan, and S. N. Freund. Types for Safe Locking: Static Race Detection for Java. TOPLAS, 28(2):207–255, 2006.
[2]
S. V. Adve and H.-J. Boehm. Memory Models: A Case for Rethinking Parallel Languages and Hardware. CACM, 53:90–101, 2010.
[3]
S. V. Adve and M. D. Hill. Weak Ordering—A New Definition. In ISCA, pages 2–14, 1990.
[4]
S. V. Adve, M. D. Hill, B. P. Miller, and R. H. B. Netzer. Detecting Data Races on Weak Memory Systems. In ISCA, pages 234–243, 1991.
[5]
W. Ahn, S. Qi, M. Nicolaides, J. Torrellas, J.-W. Lee, X. Fang, S. Midkiff, and D. Wong. BulkCompiler: High-performance Sequential Consistency through Cooperative Compiler and Hardware Support. In MICRO, pages 133–144, 2009.
[6]
B. Alpern, S. Augart, S. M. Blackburn, M. Butrico, A. Cocchi, P. Cheng, J. Dolby, S. Fink, D. Grove, M. Hind, K. S. McKinley, M. Mergen, J. E. B. Moss, T. Ngo, and V. Sarkar. The Jikes Research Virtual Machine Project: Building an Open-Source Research Community. IBM Systems Journal, 44:399–417, 2005.
[7]
E. D. Berger, T. Yang, T. Liu, and G. Novark. Grace: Safe Multithreaded Programming for C/C++. In OOPSLA, pages 81–96, 2009.
[8]
S. M. Blackburn, R. Garner, C. Hoffman, A. M. Khan, K. S. McKinley, R. Bentzur, A. Diwan, D. Feinberg, D. Frampton, S. Z. Guyer, M. Hirzel, A. Hosking, M. Jump, H. Lee, J. E. B. Moss, A. Phansalkar, D. Stefanovi´c, T. VanDrunen, D. von Dincklage, and B. Wiedermann. The DaCapo Benchmarks: Java Benchmarking Development and Analysis. In OOPSLA, pages 169–190, 2006.
[9]
R. L. Bocchino, Jr., V. S. Adve, S. V. Adve, and M. Snir. Parallel Programming Must Be Deterministic by Default. In HotPar, pages 4–9, 2009.
[10]
H.-J. Boehm. How to miscompile programs with “benign” data races. In HotPar, 2011.
[11]
H.-J. Boehm. Position paper: Nondeterminism is Unavoidable, but Data Races are Pure Evil. In RACES, pages 9–14, 2012.
[12]
H.-J. Boehm and S. V. Adve. Foundations of the C++ Concurrency Memory Model. In PLDI, pages 68–78, 2008.
[13]
H.-J. Boehm and B. Demsky. Outlawing Ghosts: Avoiding Out-of-thinair Results. In MSPC, pages 7:1–7:6, 2014.
[14]
M. D. Bond, K. E. Coons, and K. S. McKinley. Pacer: Proportional Detection of Data Races. In PLDI, pages 255–268, 2010.
[15]
M. D. Bond, M. Kulkarni, M. Cao, M. Zhang, M. Fathi Salmi, S. Biswas, A. Sengupta, and J. Huang. Octet: Capturing and Controlling Cross-Thread Dependences Efficiently. In OOPSLA, pages 693–712, 2013.
[16]
C. Boyapati, R. Lee, and M. Rinard. Ownership Types for Safe Programming: Preventing Data Races and Deadlocks. In OOPSLA, pages 211–230, 2002.
[17]
J. Burnim, K. Sen, and C. Stergiou. Testing Concurrent Programs on Relaxed Memory Models. In ISSTA, pages 122–132, 2011.
[18]
L. Ceze, J. Devietti, B. Lucia, and S. Qadeer. A Case for System Support for Concurrency Exceptions. In HotPar, 2009.
[19]
J.-D. Choi, K. Lee, A. Loginov, R. O’Callahan, V. Sarkar, and M. Sridharan. Efficient and Precise Datarace Detection for Multithreaded Object-Oriented Programs. In PLDI, pages 258–269, 2002.
[20]
L. Dalessandro and M. L. Scott. Sandboxing Transactional Memory. In PACT, pages 171–180, 2012.
[21]
J. Devietti, B. P. Wood, K. Strauss, L. Ceze, D. Grossman, and S. Qadeer. RADISH: Always-On Sound and Complete Race Detection in Software and Hardware. In ISCA, pages 201–212, 2012.
[22]
K. Du Bois, J. B. Sartor, S. Eyerman, and L. Eeckhout. Bottle Graphs: Visualizing Scalability Bottlenecks in Multi-threaded Applications. In OOPSLA, pages 355–372, 2013.
[23]
L. Effinger-Dean, B. Lucia, L. Ceze, D. Grossman, and H.-J. Boehm. IFRit: Interference-Free Regions for Dynamic Data-Race Detection. In OOPSLA, pages 467–484, 2012.
[24]
T. Elmas, S. Qadeer, and S. Tasiran. Goldilocks: A Race and Transaction-Aware Java Runtime. In PLDI, pages 245–255, 2007.
[25]
D. Engler and K. Ashcraft. RacerX: Effective, Static Detection of Race Conditions and Deadlocks. In SOSP, pages 237–252, 2003.
[26]
J. Erickson, M. Musuvathi, S. Burckhardt, and K. Olynyk. Effective Data-Race Detection for the Kernel. In OSDI, pages 1–16, 2010.
[27]
C. Flanagan and S. N. Freund. FastTrack: Efficient and Precise Dynamic Race Detection. In PLDI, pages 121–133, 2009.
[28]
C. Flanagan and S. N. Freund. Adversarial Memory For Detecting Destructive Races. In PLDI, pages 244–254, 2010.
[29]
C. Flanagan and S. N. Freund. The RoadRunner Dynamic Analysis Framework for Concurrent Programs. In PASTE, pages 1–8, 2010.
[30]
C. Flanagan and S. N. Freund. RedCard: Redundant Check Elimination for Dynamic Race Detectors. In ECOOP, pages 255–280, 2013.
[31]
S. N. Freund, 2015. Personal communication.
[32]
S. Gupta, F. Sultan, S. Cadambi, F. Ivanˇci´c, and M. Rötteler. Using Hardware Transactional Memory for Data Race Detection. In IPDPS, pages 1–11, 2009.
[33]
T. Harris and K. Fraser. Language Support for Lightweight Transactions. In OOPSLA, pages 388–402, 2003.
[34]
T. Harris, J. Larus, and R. Rajwar. Transactional Memory. Morgan and Claypool Publishers, 2nd edition, 2010.
[35]
T. Harris, M. Plesko, A. Shinnar, and D. Tarditi. Optimizing Memory Transactions. In PLDI, pages 14–25, 2006.
[36]
B. Kasikci, C. Zamfir, and G. Candea. Data Races vs. Data Race Bugs: Telling the Difference with Portend. In ASPLOS, pages 185–198, 2012.
[37]
B. Kasikci, C. Zamfir, and G. Candea. RaceMob: Crowdsourced Data Race Detection. In SOSP, pages 406–422, 2013.
[38]
L. Lamport. Time, Clocks, and the Ordering of Events in a Distributed System. CACM, 21(7):558–565, 1978.
[39]
L. Lamport. How to Make a Multiprocessor Computer That Correctly Executes Multiprocess Programs. IEEE Computer, 28:690–691, 1979.
[40]
D. Lee, P. M. Chen, J. Flinn, and S. Narayanasamy. Chimera: Hybrid Program Analysis for Determinism. In PLDI, pages 463–474, 2012.
[41]
T. Lindholm and F. Yellin. The Java Virtual Machine Specification. Prentice Hall PTR, 2nd edition, 1999.
[42]
S. Lu, S. Park, E. Seo, and Y. Zhou. Learning from Mistakes: A Comprehensive Study on Real World Concurrency Bug Characteristics. In ASPLOS, pages 329–339, 2008.
[43]
B. Lucia and L. Ceze. Data Provenance Tracking for Concurrent Programs. In CGO, pages 146–156, 2015.
[44]
B. Lucia, L. Ceze, K. Strauss, S. Qadeer, and H.-J. Boehm. Conflict Exceptions: Simplifying Concurrent Language Semantics with Precise Hardware Exceptions for Data-Races. In ISCA, pages 210–221, 2010.
[45]
J. Manson, W. Pugh, and S. V. Adve. The Java Memory Model. In POPL, pages 378–391, 2005.
[46]
D. Marino, M. Musuvathi, and S. Narayanasamy. LiteRace: Effective Sampling for Lightweight Data-Race Detection. In PLDI, pages 134– 143, 2009.
[47]
D. Marino, A. Singh, T. Millstein, M. Musuvathi, and S. Narayanasamy. DRFx: A Simple and Efficient Memory Model for Concurrent Programming Languages. In PLDI, pages 351–362, 2010.
[48]
H. S. Matar, I. Kuru, S. Tasiran, and R. Dementiev. Accelerating Precise Race Detection Using Commercially-Available Hardware Transactional Memory Support. In WoDet, 2014.
[49]
A. Muzahid, D. Suárez, S. Qi, and J. Torrellas. SigRace: Signature-Based Data Race Detection. In ISCA, pages 337–348, 2009.
[50]
M. Naik and A. Aiken. Conditional Must Not Aliasing for Static Race Detection. In POPL, pages 327–338, 2007.
[51]
M. Naik, A. Aiken, and J. Whaley. Effective Static Race Detection for Java. In PLDI, pages 308–319, 2006.
[52]
S. Narayanasamy, Z. Wang, J. Tigani, A. Edwards, and B. Calder. Automatically Classifying Benign and Harmful Data Races Using Replay Analysis. In PLDI, pages 22–31, 2007.
[53]
R. O’Callahan and J.-D. Choi. Hybrid Dynamic Data Race Detection. In PPoPP, pages 167–178, 2003.
[54]
J. Ouyang, P. M. Chen, J. Flinn, and S. Narayanasamy. ...and region serializability for all. In HotPar, 2013.
[55]
E. Pozniansky and A. Schuster. MultiRace: Efficient On-the-Fly Data Race Detection in Multithreaded C++ Programs. CCPE, 19(3):327– 340, 2007.
[56]
P. Pratikakis, J. S. Foster, and M. Hicks. LOCKSMITH: Context-Sensitive Correlation Analysis for Race Detection. In PLDI, pages 320–331, 2006.
[57]
S. Rajamani, G. Ramalingam, V. P. Ranganath, and K. Vaswani. ISOLATOR: Dynamically Ensuring Isolation in Concurrent Programs. In ASPLOS, pages 181–192, 2009.
[58]
P. Ratanaworabhan, M. Burtscher, D. Kirovski, B. Zorn, R. Nagpal, and K. Pattabiraman. Detecting and Tolerating Asymmetric Races. In PPoPP, pages 173–184, 2009.
[59]
M. C. Rinard and M. S. Lam. The Design, Implementation, and Evaluation of Jade. TOPLAS, 20:483–545, 1998.
[60]
C. G. Ritson and F. R. Barnes. An Evaluation of Intel’s Restricted Transactional Memory for CPAs. In CPA, pages 271–292, 2013.
[61]
B. Saha, A.-R. Adl-Tabatabai, R. L. Hudson, C. C. Minh, and B. Hertzberg. McRT-STM: A High Performance Software Transactional Memory System for a Multi-Core Runtime. In PPoPP, pages 187–197, 2006.
[62]
S. Savage, M. Burrows, G. Nelson, P. Sobalvarro, and T. Anderson. Eraser: A Dynamic Data Race Detector for Multi-Threaded Programs. In SOSP, pages 27–37, 1997.
[63]
C. Segulja and T. S. Abdelrahman. Clean: A Race Detector with Cleaner Semantics. In ISCA, pages 401–413, 2015.
[64]
A. Sengupta, S. Biswas, M. Zhang, M. D. Bond, and M. Kulkarni. Hybrid Static–Dynamic Analysis for Statically Bounded Region Serializability. In ASPLOS, pages 561–575, 2015.
[65]
A. Singh, D. Marino, S. Narayanasamy, T. Millstein, and M. Musuvathi. Efficient Processor Support for DRFx, a Memory Model with Exceptions. In ASPLOS, pages 53–66, 2011.
[66]
U.S.–Canada Power System Outage Task Force. Final Report on the August 14th Blackout in the United States and Canada. Technical report, Department of Energy, 2004.
[67]
C. von Praun and T. R. Gross. Object Race Detection. In OOPSLA, pages 70–82, 2001.
[68]
C. von Praun and T. R. Gross. Static Conflict Analysis for Multi-Threaded Object-Oriented Programs. In PLDI, pages 115–128, 2003.
[69]
J. W. Voung, R. Jhala, and S. Lerner. RELAY: Static Race Detection on Millions of Lines of Code. In ESEC/FSE, pages 205–214, 2007.
[70]
J. Ševˇcík and D. Aspinall. On Validity of Program Transformations in the Java Memory Model. In ECOOP, pages 27–51, 2008.
[71]
J. Wilcox, P. Finch, C. Flanagan, and S. N. Freund. Array Shadow State Compression for Precise Dynamic Race Detection. Technical Report CSTR-201510, Williams College, 2015.
[72]
B. P. Wood, L. Ceze, and D. Grossman. Low-Level Detection of Language-Level Data Races with LARD. In ASPLOS, pages 671–686, 2014.
[73]
R. M. Yoo, C. J. Hughes, K. Lai, and R. Rajwar. Performance Evaluation of Intel Transactional Synchronization Extensions for High-Performance Computing. In SC, pages 19:1–19:11, 2013.
[74]
P. Zhou, R. Teodorescu, and Y. Zhou. HARD: Hardware-Assisted Lockset-based Race Detection. In HPCA, pages 121–132, 2007.

Cited By

View all
  • (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
  • (2024)Over-Synchronization in GPU Programs2024 57th IEEE/ACM International Symposium on Microarchitecture (MICRO)10.1109/MICRO61859.2024.00064(795-809)Online publication date: 2-Nov-2024
  • (2023)Davida: A Decentralization Approach to Localizing Transaction Sequences for Debugging Transactional Atomicity ViolationsIEEE Transactions on Reliability10.1109/TR.2022.317668072:2(808-826)Online publication date: Jun-2023
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences
OOPSLA 2015: Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications
October 2015
953 pages
ISBN:9781450336895
DOI:10.1145/2814270
  • cover image ACM SIGPLAN Notices
    ACM SIGPLAN Notices  Volume 50, Issue 10
    OOPSLA '15
    October 2015
    953 pages
    ISSN:0362-1340
    EISSN:1558-1160
    DOI:10.1145/2858965
    • Editor:
    • Andy Gill
    Issue’s Table of Contents
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 the author(s) 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 23 October 2015

Permissions

Request permissions for this article.

Check for updates

Badges

  • Distinguished Paper

Author Tags

  1. conflict exceptions
  2. data races
  3. dynamic analysis
  4. region serializability

Qualifiers

  • Research-article

Conference

SPLASH '15
Sponsor:

Acceptance Rates

Overall Acceptance Rate 268 of 1,244 submissions, 22%

Upcoming Conference

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)7
  • Downloads (Last 6 weeks)1
Reflects downloads up to 15 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (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
  • (2024)Over-Synchronization in GPU Programs2024 57th IEEE/ACM International Symposium on Microarchitecture (MICRO)10.1109/MICRO61859.2024.00064(795-809)Online publication date: 2-Nov-2024
  • (2023)Davida: A Decentralization Approach to Localizing Transaction Sequences for Debugging Transactional Atomicity ViolationsIEEE Transactions on Reliability10.1109/TR.2022.317668072:2(808-826)Online publication date: Jun-2023
  • (2022)A study of real-world data races in GolangProceedings of the 43rd ACM SIGPLAN International Conference on Programming Language Design and Implementation10.1145/3519939.3523720(474-489)Online publication date: 9-Jun-2022
  • (2021)Safe-by-default Concurrency for Modern Programming LanguagesACM Transactions on Programming Languages and Systems10.1145/346220643:3(1-50)Online publication date: 3-Sep-2021
  • (2021)Kard: lightweight data race detection with per-thread memory protectionProceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3445814.3446727(647-660)Online publication date: 19-Apr-2021
  • (2019)Accelerating sequential consistency for Java with speculative compilationProceedings of the 40th ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3314221.3314611(16-30)Online publication date: 8-Jun-2019
  • (2019)Rethinking Support for Region Conflict Exceptions2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS)10.1109/IPDPS.2019.00116(1095-1106)Online publication date: May-2019
  • (2018)High-coverage, unbounded sound predictive race detectionACM SIGPLAN Notices10.1145/3296979.319238553:4(374-389)Online publication date: 11-Jun-2018
  • (2018)Persistency for synchronization-free regionsACM SIGPLAN Notices10.1145/3296979.319236753:4(46-61)Online publication date: 11-Jun-2018
  • Show More Cited By

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media