Understanding and identifying latent data races cross-thread interleaving

Abstract

Data races are ubiquitous in multi-threaded applications, but they are by no means easy to detect. One of the most important reasons is the complexity of thread interleavings. A volume of research has been devoted to the interleaving-insensitive detection. However, all the previous work focuses on the uniform detection (unknown to the characteristics of thread interleavings), thereby making the detection defective in either reporting false positives or suffering from prohibitive overhead. To cope with the problem above, we propose an efficient, precise, and sound step-by-step resolution based on the characteristics of thread interleavings. We first try to tease apart the categories of thread interleavings from the several typical sources arising from the lock synchronizations. We then conduct a brief study and find a new and complex pattern the previous work cannot detect. It is also revealed that the simple pattern with the majority of thread interleavings can be resolved by a simple processing to achieve a big profit for the previous reordering-based design. Our final experimental results demonstrate the effectiveness of our empiricism-based approach, and show that 51.0% of execution time and 52.3% of trace size arising from the stateof-the-art reordering technique can be saved through a quick filtering of the simple pattern with a negligible (4.45%) performance overhead introduced on-the-fly.

Keywords

data race / happens-before / thread interleaving

References

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

[2] Bond M D, Coons K E, McKinley K S. Pacer: proportional detection of data races. In: Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 2010, 255―268

[3] Flanagan C, Freund S N. FastTrack: efficient and precise dynamic race detection. In: Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 2009, 121―133

[4] Narayanasamy S, Wang Z, Tigani J, Edwards A, Calder B. Automatically classifying benign and harmful data races using replay analysis. In: Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 2007, 22―31

[5] Leslie L. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM, 1978, 21(7): 558―565

[6] Chen F, Roşu G. Parametric and sliced causality. In: Proceedings of the 19th International Conference on Computer Aided Verification. 2007, 240―253

[7] Smaragdakis Y, Evans J, Sadowski C, Yi J, Flanagan C. Sound predictive race detection in polynomial time. In: Proceedings of the 39th annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. 2012, 387―400

[8] Savage S, Burrows M, Nelson G, Sobalvarro P, Anderson T. Eraser: a dynamic data race detector for multithreaded programs. ACM Transactions on Computer Systems, 1997, 15(4): 391―411

[9] Serebryany K, Iskhodzhanov T. ThreadSanitizer: data race detection in practice. In: Proceedings of the Workshop on Binary Instrumentation and Applications. 2009, 62―71

[10] Jannesari A, Kaibin B, Pankratius V, Tichy W F. Helgrind+: an efficient dynamic race detector. In: Proceedings of the IEEE International Symposium on Parallel Distributed Processing. 2009, 1―13

[11] Xie X, Xue J. Acculock: accurate and efficient detection of data races. In: Proceedings of the IEEE/ACM International Symposium on Code Generation and Optimization. 2011, 201―212

[12] Zheng L, Liao X, He B, Wu S, Jin H. On performance debugging of unnecessary lock contentions on multicore processors: a replay-based approach. In: Proceedings of the IEEE/ACM International Symposium on Code Generation and Optimization. 2015, 56―67

[13] Nethercote N, Seward J. How to shadow every byte of memory used by a program. In: Proceedings of the 3rd International Conference on Virtual Execution Environments. 2007, 65―74

[14] Kyu Cho H, Wang Y, Liao H, Kelly T, Lafortune S, Mahlke S. Practical lock/unlock pairing for concurrent programs. In: Proceedings of the IEEE/ACM International Symposium on Code Generation and Optimization. 2013, 1―12

[15] 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. 2008, 329―339

[16] 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 Symposium on the Foundations of Software Engineering. 2007, 205―214

[17] Engler D, Ashcraft K. RacerX: effective, static detection of race conditions and deadlocks. In: Proceedings of the 19th ACM Symposium on Operating Systems Principles. 2003, 237―252

[18] Marino D, Musuvathi M, Narayanasamy S. LiteRace: effective sampling for lightweight data-race detection. In: Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation. 2009, 134―143

[19] Patil H, Pereira C, Stallcup M, Lueck G, Cownie J. PinPlay: a framework for deterministic replay and reproducible analysis of parallel programs. In: Proceedings of the IEEE/ACMInternational Symposium on Code Generation and Optimization. 2010, 2―11

RIGHTS & PERMISSIONS

2014 Higher Education Press and Springer-Verlag Berlin Heidelberg