Here’s an email that I just sent to my advisor:
Hi Corky:
I wanted to give you an update on where we are with the concurrent unit testing project so it will be easier for you to ask the right questions in the next few days.
I have written a two-VM system using JPDA. The master VM is a GUI program that consists of a launcher and a monitor. The launcher allows the user to define, save, and reload settings and specify which program should be debugged. When the user presses the “Run” button, the monitor is started. The monitor sets up the best possible JPDA connection (memory transfer on Windows, sockets on others) and starts the program to be debugged in the slave VM.
To generate synchronization events, the Java API (rt.jar) and the user program need to be modified in a procedure that I have called instrumentation. This inserts the necessary Java bytecode to emit the synchronization events before and after synchronized blocks, synchronized methods, thread starts, etc. The Java API needs to be instrumented off-line. It only makes sense to provide a separate tool for doing this, though, since the classes in the Java API do not change; therefore, the rt.jar should only be instrumented once. User code can either be instrumented off-line as well or be instrumented as it is loaded using a custom class loader.
The slave VM contains a buffer to store the synchronization events as they come up. Whenever the buffer is full, it notifies the master VM that the buffer needs to be read and emptied. In effect, the slave “pushes” the data over. The master VM can also perform a “pull”, either timed or user-initiated. This way, the master VM can obtain up-to-date data even if the debugged program doesn’t generate a lot of events and thet buffer does not fill up. A “pull” may temporarily fail if the slave VM is in the process of adding to the buffer, but the master VM is written in a way to automatically try to do the “pull” again once the slave VM is done working with the buffer.
By buffering the synchronization events, we reduce the number of times the slave VM has to be suspended, data be transferred, and the slave VM be resumed. All these operations carry significant overhead, so the execution time is reduced by an order of magnitude. A 1024-element buffer allows the program to run about 40 times faster than it would with a naive implementation that uses JPDA to suspend, process, and resume the slave VM at every synchronization point.
Right now, the synchronization events stored in the buffer are still heavy-weight Java classes. This incurs both large memory requirements and longer transfer times. Using these events, we have implemented a deadlock detection system and the beginnings of a schedule recorder. The format of the schedule recorder is not very concise and easy to manage yet, though; right now, it is just a human-readable text file that names the thread, type of event, and objects involved in the synchronization events.
We are in the process of converting the synchronization events to a light-weight binary format that just uses primitive data. Such an array would a lot smaller, faster to transfer, and much friendlier to the garbage collector, even though we would not lose any information we need. In effect, we need a unique thread ID, the encoding of the type of the event, and perhaps a unique ID for the object involved in the event. The unique ID is necessary for deadlock detection, but not neccessary for schedule recording.
The problem I’m facing right now is that it is not as easy as it seems to introduce the necessary fields in all the Java classes. A unique ID for all objects should conceptually be added to the java.lang.Object class, but this class cannot be freely modified. I’m trying to provide a substitute class that essentially acts as a decorator to java.lang.Object and that can be used in place of the original class. The same may have to be done for java.lang.String, which is another class that cannot be modified. The substitution can be done automatically; for all other classes, I have already done this.
I also still need to exclude synchronization events before the beginning and after the end of the main method in the debugged program, as well as those generated if the custom class loader is used. So far I have focused more on the off-line approach because it allows me to focus on the separate things that give me trouble (rewriting, buffering and processing events) in isolation.
Once I have solved the problem of introducing additional fields to all classes, I can change the format of the event buffer to the more concise, binary format. This should make the program run a lot faster. Right now, there is still a very significant impact. I have been able to run GUI programs, but they behave very sluggishly.
These additional fields need to be introduced to implement “Lamport clocks”. During each synchronization event, the clocks of all involved objects are set to max\(clock\_1, clock\_2, …, clock\_n)+1. This way, if two threads involve the same object in a synchronization, the Lamport clocks can be used to establish a relative ordering of the events: The event with the smaller clock value happened first. These computations should be reasonably cheap since they will be inserted during instrumentation and may even be JIT-compiled.
It’s a little bit frustrating how rarely the obvious solution, like adding a field to java.lang.Object, works with the JVM: In this particular example, I first tried that, then tried to write the decorator class that can be substituted for Object, but this class needs to override final methods in Object. To allow for that, I tried to remove the final flag in java.lang.Object, but then the JVM died with a native code exception. I’ll have to use a technique that I’ve used in other places before now. which involves changing all the calls to thehse final methods to first call a method with a different name, which then delegates to the original, final method.
I feel like the JPDA implementation is a lot more stable than the one-VM implementation we were still working with in the Spring.
If you have questions or comments, I’d love to hear them.
–Mathias
