Top

International Journal of Parallel Programming

Published in:

04-06-2018

AdaptiveLock: Efficient Hybrid Data Race Detection Based on Real-World Locking Patterns

Authors: Misun Yu, Joon-Sang Lee, Doo-Hwan Bae

Published in: International Journal of Parallel Programming | Issue 5-6/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Among the various types of concurrency bugs, the data race is one of the primary causes of other concurrency bugs. Thus, it is important to detect as many data races as possible during the development step of multithreaded programs. A hybrid data race detection technique that uses the Lockset algorithm and happens-before relation, can detect actually occurred and hidden data races in one execution trace. However, high runtime slowdown obstructs the frequent use of hybrid detectors. In this paper, we empirically demonstrate that most data race bugs are caused by the absence of a lock, and that multiple locks are rarely involved in a data race bug in the real world. Thus, we propose a fast hybrid detection algorithm that does not introduce additional false positives and false negatives to the current hybrid detectors. The suggested algorithm replaces the lock-set intersection by a simple comparison operation that focuses on exploring data-race-prone locking patterns. The experimental results indicate that the proposed algorithm detects the same data races as Multilock-HB, which is the most accurate hybrid detector, with a 1.18\(\times \) slowdown of FastTrack for eight large-scale benchmark programs.

previous article An Analytical Evaluation of Data Dependence Analysis Techniques

next article OpenMP Parallelization Strategies for a Discontinuous Galerkin Solver

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

https://github.com/misunyu/data_race_bugs/

http://fsl.cs.illinois.edu/rvpredict/

Bachmann, A., Bird, C., Rahman, F., Devanbu, P., Bernstein, A.: The missing links: bugs and bug-fix commits. In: Proceedings of the 18th ACM SIGSOFT International Symposium on Foundations of Software Engineering, pp. 97–106 (2010)

Biswas, S., Zhang, M., Bond, M.D., Lucia, B.: Valor: efficient, software-only region conflict exceptions. In: Proceedings of the 2015 ACM SIGPLAN International Conference on Object-Oriented Programming, Systems, Languages, and Applications, pp. 241–259 (2015)

Blackburn, S.M., Garner, R., Hoffmann, C., Khang, A.M., McKinley, K.S., Bentzur, R., Diwan, A., Feinberg, D., Frampton, D., Guyer, S.Z., Hirzel, M., Hosking, A., Jump, M., Lee, H., Moss, J.E.B., Phansalkar, A., Stefanović, D., VanDrunen, T., von Dincklage, D., Wiedermann, B.: The DaCapo benchmarks: Java benchmarking development and analysis. In: Proceedings of the 21st Annual ACM SIGPLAN Conference on Object-Oriented Programming Systems, Languages, and Applications, pp. 169–190 (2006)

Bond, M.D., Coons, K.E., McKinley, K.S.: PACER: Proportional detection of data races. In: Proceedings of the 31st ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 255–268 (2010)

Cai, Y., Cao, L.: Effective and precise dynamic detection of hidden races for java programs. In: Proceedings of the 10th Joint Meeting on Foundations of Software Engineering, pp. 450–461 (2015)

Cai, Y., Chan, W.: LOFT: Redundant synchronization event removal for data race detection. In: Proceedings of the 22nd IEEE International Symposium on Software Reliability Engineering, pp. 160–169. IEEE (2011)

Effinger-Dean, L., Lucia, B., Ceze, L., Grossman, D., Boehm, H.J.: IFRit: Interference-free regions for dynamic data-race detection. In: Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications, pp. 467–484 (2012)

Eslamimehr, M., Palsberg, J.: Race directed scheduling of concurrent programs. In: Proceedings of the 19th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 301–314 (2014)

Flanagan, C., Freund, S.N.: FastTrack: Efficient and precise dynamic race detection. In: Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 121–133 (2009)

10.

Flanagan, C., Freund, S.N.: The RoadRunner dynamic analysis framework for concurrent programs. In: Proceedings of the 9th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering, pp. 1–8 (2010)

11.

Flanagan, C., Freund, S.N.: Redcard: Redundant check elimination for dynamic race detectors. In: Proceedings of the European Conference on Object-Oriented Programming, pp. 255–280. Springer (2013)

12.

Huang, J., Meredith, P.O., Rosu, G.: Maximal sound predictive race detection with control flow abstraction. In: Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 337–348 (2014)

13.

Islam, M.M., Muzahid, A.: Characterizing real world bugs causing sequential consistency violations. In: Proceedings of the 5th USENIX Workshop on Hot Topics in Parallelism (2013)

14.

Lamport, L.: Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21(7), 558–565 (1978)CrossRef

15.

Lin, Y., Dig, D.: CHECK-THEN-ACT misuse of Java concurrent collections. In: Proceedings of the 6th IEEE International Conference on Software Testing, Verification and Validation, pp. 164–173 (2013)

16.

Lu, S., Park, S., Seo, E., Zhou, Y.: Learning from mistakes: a comprehensive study on real world concurrency bug characteristics. In: Proceedings of the 13th International Conference on Architectural Support for Programming Languages and Operating Systems, pp. 329–339 (2008)

17.

Manson, J., Pugh, W., Adve, S.V.: The Java memory model. In: Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 378–391 (2005)

18.

Mattern, F.: Virtual time and global states of distributed systems. In: Proceedings of International Workshop on Parallel and Distributed Algorithms, pp. 215–226 (1988)

19.

Metzger, M., Tian, X., Tedeschi, W.: User-guided dynamic data race detection. Int. J. Parallel Program. 43(2), 159–179 (2015)CrossRef

20.

Musuvathi, M., Qadeer, S., Ball, T., Basler, G., Nainar, P.A., Neamtiu, I.: Finding and reproducing heisenbugs in concurrent programs. In: Proceedings of the 8th USENIX Conference on Operating Systems Design and Implementation, pp. 267–280 (2008)

21.

Naik, M., Aiken, A., Whaley, J.: Effective static race detection for java. In: Proceedings of the 27th ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 308–319 (2006)

22.

Netzer, R.H.B., Miller, B.P.: What are race conditions? Some issues and formalizations. ACM Lett. Program. Lang. Syst. 1(1), 74–88 (1992)CrossRef

23.

O’Callahan, R., Choi, J.D.: Hybrid dynamic data race detection. In: Proceedings of the 9th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 167–178 (2003)

24.

Park, C.S., Sen, K.: Randomized active atomicity violation detection in concurrent programs. In: Proceedings of the 16th ACM SIGSOFT International Symposium on Foundations of software engineering, pp. 135–145 (2008)

25.

Park, J., Kim, M., Bae, D.H.: An empirical study of supplementary patches in open source projects. Empir. Softw. Eng. 22(1), 436–473 (2016)CrossRef

26.

Pozniansky, E., Schuster, A.: Efficient on-the-fly data race detection in multithreaded C++ programs. In: Proceedings of the 9th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, pp. 179–190 (2003)

27.

Pozniansky, E., Schuster, A.: MultiRace: efficient on-the-fly data race detection in multithreaded C++ programs: research articles. Concurr. Comput. Pract. Exp. 19(3), 327–340 (2007)CrossRef

28.

Qi, S., Muzahid, A.A., Ahn, W., Torrellas, J.: Dynamically detecting and tolerating if-condition data races. In: Proceedings of the 20th IEEE International Symposium on High Performance Computer Architecture, pp. 120–131 (2014)

29.

Radoi, C., Dig, D.: Practical static race detection for java parallel loops. In: Proceedings of the 2013 International Symposium on Software Testing and Analysis, pp. 178–190 (2013)

30.

Radoi, C., Dig, D.: Effective techniques for static race detection in java parallel loops. ACM Trans. Softw. Eng. Methodol. 24(4), 24:1–24:30 (2015)CrossRef

31.

Ray, B., Posnett, D., Filkov, V., Devanbu, P.: A large scale study of programming languages and code quality in Github. In: Proceedings of the 22nd ACM SIGSOFT International Symposium on Foundations of Software Engineering, pp. 155–165 (2014)

32.

Savage, S., Burrows, M., Nelson, G., Sobalvarro, P., Anderson, T.: Eraser: a dynamic data race detector for multithreaded programs. ACM Trans. Comput. Syst. 15(4), 391–411 (1997)CrossRef

33.

Sen, K.: Race directed random testing of concurrent programs. In: Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 11–21 (2008)

34.

Serebryany, K., Iskhodzhanov, T.: ThreadSanitizer: data race detection in practice. In: Proceedings of the Workshop on Binary Instrumentation and Applications, pp. 62–71 (2009)

35.

Smaragdakis, Y.e.a.: Sound predictive race detection in polynomial time. In: Proceedings of the 39th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 387–400 (2012)

36.

Song, Y.W., Lee, Y.H.: Efficient data race detection for C/C++ programs using dynamic granularity. In: Proceedings of the 28th IEEE International Parallel and Distributed Processing Symposium, pp. 679–688 (2014)

37.

Voung, J.W., Jhala, R., Lerner, S.: RELAY: static race detection on millions of lines of code. In: Proceedings of the 6th Joint Meeting of the European Software Engineering Conference and the ACM SIGSOFT Symposium on The Foundations of Software Engineering, pp. 205–214 (2007)

38.

Xie, X., Xue, J.: Acculock: Accurate and efficient detection of data races. In: Proceedings of the 9th Annual IEEE/ACM International Symposium on Code Generation and Optimization, pp. 201–212 (2011)

39.

Xie, X., Xue, J., Zhang, J.: Acculock: accurate and efficient detection of data races. Softw. Pract. Exp. 43(5), 543–576 (2013)CrossRef

40.

Yin, Z., Yuan, D., Zhou, Y., Pasupathy, S., Bairavasundaram, L.: How do fixes become bugs? In: Proceedings of the 19th ACM SIGSOFT Symposium and the 13th European Conference on Foundations of Software Engineering, pp. 26–36 (2011)

41.

Yu, J., Narayanasamy, S., Pereira, C., Pokam, G.: Maple: a coverage-driven testing tool for multithreaded programs. In: Proceedings of the ACM International Conference on Object Oriented Programming Systems Languages and Applications, pp. 485–502 (2012)

42.

Yu, M., Bae, D.H.: SimpleLock+: fast and accurate hybrid data race detection. Comput. J. 59(6), 793–809 (2016)CrossRef

43.

Yu, M., Ma, Y.S., Bae, D.H.: Characterizing non-deadlock concurrency bug fixes in open-source Java programs. In: Proceedings of the 31th ACM/SIGAPP Symposium on Applied Computing, pp. 1534–1537 (2016)

44.

Yu, M., Yoo, S.K., Bae, D.H.: SimpleLock: fast and accurate hybrid data race detector. In: Proceedings of the 15th International Conference on Parallel and Distributed Computing, Applications and Technologies, pp. 50–56 (2013)

45.

Yu, Y., Rodeheffer, T., Chen, W.: RaceTrack: efficient detection of data race conditions via adaptive tracking. In: Proceedings of the 10th ACM Symposium on Operating Systems Principles, pp. 221–234 (2005)

46.

Zhai, K., Xu, B., Chan, W.K., Tse, T.H.: CARISMA: a context-sensitive approach to race-condition sample-instance selection for multithreaded applications. In: Proceedings of the 21st International Symposium on Software Testing and Analysis, pp. 221–231 (2012)

Title: AdaptiveLock: Efficient Hybrid Data Race Detection Based on Real-World Locking Patterns
Authors: Misun Yu
Joon-Sang Lee
Doo-Hwan Bae
Publication date: 04-06-2018
Publisher: Springer US
Published in: International Journal of Parallel Programming / Issue 5-6/2019
Print ISSN: 0885-7458
Electronic ISSN: 1573-7640
DOI: https://doi.org/10.1007/s10766-018-0579-5

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Other articles of this Issue 5-6/2019

Efficient Methods for Trace Analysis Parallelization

MapReduce Data Skewness Handling: A Systematic Literature Review

Tracing and Profiling Machine Learning Dataflow Applications on GPU

Editor’s Note: Special Issue on High-Level Languages and Frameworks for High-Performance Computing

PolyJIT: Polyhedral Optimization Just in Time

An Analytical Evaluation of Data Dependence Analysis Techniques

Premium Partner