Cited By
View all- 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
Characterizing real world bugs causing sequential consistency violations
Abstract
With the ubiquitous availability of parallel architectures, the burden falls on programmers' shoulders to write correct parallel programs that have high performance and portability across different systems. One of the major issues that complicates this task is the intricacies involved with the underlying memory consistency models. Sequential Consistency (SC) is the simplest and most intuitive memory model. Therefore, programmers usually assume SC for writing parallel programs. However, various concurrency bugs can lead to violations of SC. These subtle bugs make the program difficult to reason about and virtually always lead to incorrectness. This paper provides the first (to the best of our knowledge) comprehensive characteristics study of SC violation bugs that appear in real world codebases.
We have carefully examined pattern, manifestation, effect, and fix strategy of 20 SC violation bugs. These bugs have been selected from randomly chosen 127 concurrency bugs from a variety of open source programs and libraries (e.g. Mozilla, Apache, MySQL, Gcc, Cilk, Java, and Splash2). Our study reveals interesting findings and provides useful guidance for future research in this area. References
References
[1]
BURCKHARDT, S., ALUR, R., AND MARTIN, M. M. K. Checkfence: checking consistency of concurrent data types on relaxed memory models. In Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation (New York, NY, USA, 2007), PLDI '07, ACM, pp. 12-21.
[2]
BURCKHARDT, S., AND MUSUVATHI, M. Effective program verification for relaxed memory models. In CAV (Jul 2008).
[3]
BURNIM, J., SEN, K., AND STERGIOU, C. Sound and complete monitoring of sequential consistency for relaxed memory models. In Proceedings of the 17th international conference on Tools and algorithms for the construction and analysis of systems: part of the joint European conferences on theory and practice of software (Berlin, Heidelberg, 2011), TACAS'11/ETAPS'11, Springer-Verlag, pp. 11-25.
[4]
DUAN, Y., FENG, X., WANG, L., ZHANG, C., AND YEW, P.-C. Detecting and eliminating potential violations of sequential consistency for concurrent c/c++ programs. In Proceedings of the 7th annual IEEE/ACM International Symposium on Code Generation and Optimization (Washington, DC, USA, 2009), CGO '09, IEEE Computer Society, pp. 25-34.
[5]
FANG, X., LEE, J., AND MIDKIFF, S. P. Automatic fence insertion for shared memory multiprocessing. In Proceedings of the 17th annual international conference on Supercomputing (New York, NY, USA, 2003), ICS '03, ACM, pp. 285-294.
[6]
GHARACHORLOO, K., AND GIBBONS, P. B. Detecting violations of sequential consistency. In Proceedings of the third annual ACM symposium on Parallel algorithms and architectures (New York, NY, USA, 1991), SPAA '91, ACM, pp. 316-326.
[7]
GHARACHORLOO, K., LENOSKI, D., LAUDON, J., GIBBONS, P., GUPTA, A., AND HENNESSY, J. Memory consistency and event ordering in scalable shared-memory multiprocessors. In Proceedings of the 17th annual international symposium on Computer Architecture (New York, NY, USA, 1990), ISCA '90, ACM, pp. 15-26.
[8]
KRISHNAMURTHY, A., AND YELICK, K. Analyses and optimizations for shared address space programs. Journal of Parallel and Distributed Computing 38, 2 (Nov. 1996), 130-144.
[9]
LAMPORT, L. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computer 28, 9 (Sept. 1979), 690-691.
[10]
LEE, J., AND PADUA, D. A. Hiding relaxed memory consistency with a compiler. IEEE Transactions on Computer 50, 8 (Aug. 2001), 824-833.
[11]
LIN, C., NAGARAJAN, V., AND GUPTA, R. Efficient sequential consistency using conditional fences. In Proceedings of the 19th international conference on Parallel architectures and compilation techniques (New York, NY, USA, 2010), PACT '10, ACM, pp. 295-306.
[12]
LU, S., ET AL. Learning from mistakes: A comprehensive study on real world concurrency bug characteristics. In ASPLOS (Mar 2008).
[13]
LUCIA, B., CEZE, L., STRAUSS, K., QADEER, S., AND BOEHM, H.-J. Conflict exceptions: simplifying concurrent language semantics with precise hardware exceptions for data-races. In Proceedings of the 37th annual international symposium on Computer architecture (New York, NY, USA, 2010), ISCA '10, ACM, pp. 210-221.
[14]
MARINO, D., SINGH, A., MILLSTEIN, T., MUSUVATHI, M., AND NARAYANASAMY, S. DRFx: a simple and efficient memory model for concurrent programming languages. In Proceedings of the 2010 ACM SIGPLAN conference on Programming language design and implementation (New York, NY, USA, 2010), PLDI '10, ACM, pp. 351-362.
[15]
MAY, C., SILHA, E., SIMPSON, R., AND WARREN, H. The PowerPC Architecture: A Specication for a New Family of RISC Processors. Morgan Kaufmann Publishers, Inc, 1994.
[16]
MUZAHID, A., QI, S., AND TORRELLAS, J. Vulcan: Hardware support for detecting sequential consistency violations in programs dynamically. In Proceedings of the 45th annual ACM/IEEE international symposium on Microarchitecture (December 2012), MICRO '12.
[17]
NETHERCOTE, N., AND SEWARD, J. Valgrind: a framework for heavyweight dynamic binary instrumentation. In Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation (New York, NY, USA, 2007), PLDI '07, ACM, pp. 89-100.
[18]
QIAN, X., SAHELICES, B., TORRELLAS, J., AND QIAN, D. Volition: Precise and Scalable Sequential Consistency Violation Detection. In Proceedings of the 18th international conference on Architectural support for programming languages and operating systems (March 2013), ASPLOS '13.
[19]
SCHMIDT, D. C., AND HARRISON, T. Double-checked locking: An optimization pattern for efficiently initializing and accessing thread-safe objects. In Conf. on Patt. Lang. of Prog. (1996).
[20]
SHASHA, D., AND SNIR, M. Efficient and correct execution of parallel programs that share memory. ACM Transactions on Programming Languages and Systems 10, 2 (Apr. 1988), 282- 312.
[21]
SURA, Z., FANG, X., WONG, C.-L., MIDKIFF, S. P., LEE, J., AND PADUA, D. Compiler techniques for high performance sequentially consistent java programs. In Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming (New York, NY, USA, 2005), PPoPP '05, ACM, pp. 2-13.
[22]
YUAN, D., PARK, S., AND ZHOU, Y. Characterizing logging practices in open-source software. In Proceedings of the 2012 International Conference on Software Engineering (Piscataway, NJ, USA, 2012), ICSE 2012, IEEE Press, pp. 102-112.
- Characterizing real world bugs causing sequential consistency violations
Recommendations
Characterizing duplicate bugs: Perceptions of practitioners and an empirical analysis
AbstractBug handling is an essential part of the software development process. Ideally, in a bug‐tracking system, bugs are reported, fixed, verified, and closed. In some cases, bugs have to be reopened mostly due to an incorrect fix. However, instead of ...
Our study investigates the difference between unique and duplicate bugs and further categorizes duplicates into Master‐Unresolved (Category‐1) and Missed‐Reopen (Category‐2) bugs. Through investigation of bug reports, we found that duplicates are up to ...
Understanding and detecting real-world performance bugs
PLDI '12: Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and ImplementationDevelopers frequently use inefficient code sequences that could be fixed by simple patches. These inefficient code sequences can cause significant performance degradation and resource waste, referred to as performance bugs. Meager increases in single ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Sponsors
- SIGMETRICS: ACM Special Interest Group on Measurement and Evaluation
- SIGPLAN: ACM Special Interest Group on Programming Languages
- SIGOPS: ACM Special Interest Group on Operating Systems
- SIGSOFT: ACM Special Interest Group on Software Engineering
- SIGARCH: ACM Special Interest Group on Computer Architecture
Publisher
USENIX Association
United States
Publication History
Published: 24 June 2013
Check for updates
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 06 Jan 2025
Other Metrics
Citations
Cited By
View all- 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