Incremental Data Race Detection

When two threads access a shared memory that at least one access is the write and the two accesses have no happens-before relation, the data race happens. Data race is serious programming error. Furthermore, programs with data races are notoriously difficult to debug and understand because they can exhibit different behaviors with the same inputs. So it is widely recognized that tools for automatic detection of potential data races can be valuable. As the first language that supports multi-thread programming in language level, Java is broadly used. So researching the program analysis and optimization on Java concurrent programs is very important and significative.This paper researches the data race detection technologies for Java programs. Based on the researches about the existing static and dynamic race detection algorithms, a new precise and efficient algorithm on incrementally detecting potential data races in Java multithreaded programs is presented. This paper mainly depicts and discusses the following works:1. Puts forward an incremental data race detection algorithm framework based on Just-in-time (JIT) compiler, which combines the lockset-based detection and happens-before-based detection. It has either the unlimited program scale advantage of the static analysis or the high precision advantage of the dynamic analysis. The framework includes intra- and inter-method algorithms.2. Base on the incremental race detection framework, the algorithm in turn does intra-method analysis on every method compiled by JIT compiler only once and collects their summaries independent of the context and dynamically builds and maintains the multithreaded call graph. The method summary includes objects field-reference relations, access events, the unanalyzed callsites and the start/join thread relations et al. The inter-method analysis is based on the method summaries collected in the intra-method analysis. Dynamically building and maintaining the multi-thread call graph reduces the space cost and can analyze the Java programs which are"open world"programs because of dynamic class load.3. Based on the method summaries, the context-sensitive inter-thread analysis is proposed to incrementally compute potential race information and output them in time. Not only does the algorithm analyze each method only once but also it analyzes each call site only once. If only all call sites of a method are analyzed, the method can be combined wihe its caller.4. Based on the framework and algorithm, we have implemented the analysis in the open source Java SE Harmony. By testing with several benchmarks, such as SPECjbb2005, in the JVM with the race detection pass, the experimental results show that the race detection pass has the similar precision with O'Callahan and Choi's algorithm on dynamic race detection, and only consumes 2%~4% of the total compilation time and has not additional run time overhead.