To test our ideas in practice, we implemented the TRaDe method in an existing JVM. We selected the Sun JVM 1.2.1 on Solaris. This JVM comes equipped with a just in time compiler (JIT). A JIT is used to compile bytecodes to machine instructions on-the-fly so as to accelerate the execution of a Java program. We decided to turn the JIT compiler off to simplify our coding. This way, the JVM just uses an interpreter loop, executing the bytecodes one by one. Our techniques should be readily transferable to JIT compilers.
Our first step was to instrument all the synchronisation primitives of Java using vector clocks as described in Section 2. Vector clocks have a serious drawback: they contain as many components as there are threads in the program. This means that if we are dealing for example with an FTP-server which creates a thread for every file request it receives, the size of the vector clock grows without bounds. We have implemented an advanced version of vector clocks that can dynamically grow and shrink as threads are created and destroyed without losing accuracy while doing data race detection and with little overhead involved called `accordion clocks'. The exact approach we took is beyond the scope of this article.
The next step was to instrument every object with a minimal data structure that allows TRaDe to be used. The basic idea can be seen in Figure 8. When objects are created using new, newarray, anewarray or multianewarray, they are extended with a data structure consisting of 20 extra bytes.
It consists of 2 parts. The first is the thread identification number (TID). In this field, the TID of the thread that created this object is stored or, when the object becomes global and is reachable by several threads, -1 is stored. The second part consists of link fields that will be used to link a much larger data structure for full data race detection only if the object becomes global.
An object can contain several fields that can be written or read (#fields). If we instrument a new global object, each field must have its specific data structure that maintains its access history. This data structure contains: a description (description) of the field being accessed (its name, type info, ...) and links to information about the read and write operations that involved this field. For each read and write operation we store the location in the code where the operation occurred (a class, a member function and a JVM program counter) and a vector clock indicating `when' the operation occurred.
Figure 8: Full instrumentation of an object for data race detection
Using this data structure, the instructions aastore, putfield and putstatic are instrumented. We will explain what happens for aastore. A similar procedure is followed for putfield and putstatic.
Suppose the bytecode aastore stores a reference, R, into an array, referred to by reference A. There are 2 possibilities:
If the object referred to by R becomes global, we recursively check all its children. Each child that is not yet global is made global. Here we must pay attention to stack overflow when recursively marking a deep data structure as global.
The actual race detection consists of instrumentation added to the 20 bytecodes which read or write to an object as follows. Each time such a bytecode is executed, we check whether it affects a global object. If not, we don't have to do anything; races are impossible. If we are dealing with a global object, we can access the extra data structures and verify using the vector clocks whether this new instruction represents a data race. If so, we flag this to the user. Then we update the access history with the new location of this instruction and the new vector clock indicating when the instruction occurred.