A Concurrent Affair

Now that I’m adding the InstrumentingClassLoader to the runtime to load and instrument classes on the fly, additional classes need to go into the rt.jar file, and it quickly becomes confusing which ones to include. The custom class loader references nearly the entire runtime portion of the project, but not the JPDA monitor.

I still didn’t want to draw the line by hand and risk a mistake. Well, I did and failed. Practically, all classes that get referenced in the class I am running need to be available in rt.jar, and all the classes that get referenced in them, and so on. Conceptually, this is the least class dependency fixpoint.

Now I wrote a tool, edu.rice.cs.cunit.DependencyFixPoint, that lists all the classes in that fixpoint, starting with any number of classes. The files can be output as file names and piped into jar to create an archive of just the files necessary. Now everything is automated and exactly the right files get added to the runtime.

I’ve also fixed a bug related to the Instrumentation attribute. Until tonight, I never had the case where the string “Instrumentation” was already present in the class file, and it worked because a new item was added to the constant pool. Tonight, I instrumented InstrumentingClassLoader.class, which already contains the string “Instrumentation”, so it is supposed to reuse it. That’s where it failed. Fixed.

And I’ve noticed that I actually don’t need to include the monitor.jar file (which I now renamed cunitrt.jar) separately on the boot class path. I merge it into the rt.jar already.

Update

I just found another problem. The way I changed the automation, now all the files added to the rt.jar got instrumented. Of course, SyncPointRecorder still contains that little comment “do not instrument”, which now got ignored. Infinite recursion generally isn’t a good thing.

Now you can add the @DoNotInstrument annotation to a class to prevent it from getting instrumented. Both the offline FileInstrumenter and the on the fly InstrumentingClassLoader obey the annotation.

Again, since I’m stuck, I looked for different work that needed to be done and found the InstrumentingClassLoader. For some reason, it wouldn’t quite work anymore. It said something about an illegal method name sleep<Wrapper>. I checked the file, everything seemed as always. In fact, when I instrumented the file offline, everything worked to the extent it was working before.

I’ve been tinkering with the class loader in general, making several other improvements, and don’t have it working yet, but it seems like Sun changed the behavior of java.lang.ClassLoader in one of the Java 1.5.0 updates (currently, I have the 1.5.0_04 version installed). Before, ClassLoader would accept method names that include characters like < and >, even though they couldn’t be generated by Java programs. That’s exactly why I chose them. If classes are not loaded and instrumented on the fly, Java still has this behavior. But if a custom class loader is used now, these method names are being rejected.

I’ve changed my naming scheme to $$$Wrapper$$$ and $$$Old$$$. The triple-$ is to avoid problems with James Sasitorn’s NexGen. I’ll still have to have a chat with him to make sure there won’t be any clashes. Testing both custom class loaders together will be interesting too.

Because I was stuck with the hanging slave, I took a look at the InstrumentingClassLoader again. It’s a custom class loader that rewrites class files as they are loaded during runtime.

I abandoned working on that a while ago when I ran into problems with mutually recursive references. Somehow, my class loader got confused when it was loading a class A that referenced a class B that, directly or indirectly, referenced A again… Instead, I resorted to offline instrumentation using FileInstrumentor. That makes more sense with the giant rt.jar anyway. There’s no reason to instrument those classes all over again.

I haven’t tested it a lot yet, but at least it seems to integrate well with the launcher and the JPDA monitor. Now I have a lot more files that should not be instrumented, though, that need to be included in the bootclasspath and loaded.

I felt like adding a string mask to exclude them wasn’t flexible enough, so I introduced a custom attribute called “Instrumentation”. If a file has been instrumented already, that attribute is added to the class file. The attribute data is a string of the instrumentor class names, separated by semicolon. Currently, the following string is generated:

"edu.rice.cs.cunit.instrumentors.MethodHashTableInstrumentationStrategy;
edu.rice.cs.cunit.instrumentors.ThreadInstrumentationStrategy;
edu.rice.cs.cunit.instrumentors.SleepYieldCallInstrumentationStrategy;
edu.rice.cs.cunit.instrumentors.SleepYieldInstrumentationStrategy;
edu.rice.cs.cunit.instrumentors.ObjectCallInstrumentationStrategy;
edu.rice.cs.cunit.instrumentors.ObjectInstrumentationStrategy;
edu.rice.cs.cunit.instrumentors.SynchronizedMethodToBlockInstrumentationStrategy;
edu.rice.cs.cunit.instrumentors.SynchronizedBlockInstrumentationStrategy"

If a class just shouldn’t be instrumented, then that attribute is added with an empty string. A class is only instrumented if the “Instrumentation” attribute is not present yet. After that, it is added with the proper string.

I’m running a few dumb divide-and-conquer tests to find out why the code is blocking (that’s generally how debugging this stuff works). Initially, I commented out everything in SyncPointRecorder.add(), and not surprisingly, everything worked. I wasn’t getting any data, of course, but the slave didn’t hang.

Now I commented out just the statement that adds the synchronization point to the list:

public static synchronized void add(ISyncPoint sp) {
if (_syncPoints==null) {
_syncPoints = new ArrayList();
}
// _syncPoints.add(sp);
}

Interestingly enough, now it hangs. I guess now I’ll venture into ArrayList to look for a reason.

Update

The constructor of ArrayList doesn’t seem to do anything but a new Object[10], so there isn’t a lot of interesting stuff to see. I wrote a quick hack to see if array allocation is the problem and replaced the ArrayList with a biiiig array (and assume that it never fills up, or I’d lose lots of data). The JPDA monitor reads out the array and resets the write index to 0.

public class SyncPointRecorder {
private static final int SIZE = 2 << 12; private static volatile ISyncPoint[] _syncPoints = new ISyncPoint[SIZE]; private static volatile int _index = 0; public static synchronized void add(ISyncPoint sp) { _syncPoints[_index] = sp; // hangs here _index = (_index + 1) & (SIZE-1); } }

However, that's not the issue either. Now the program hangs in line 6. What can go wrong in assigning a reference to an array entry? Huhumm...

I’ve added some diagnostic tools to the JPDA monitor to analyze why and in what way the slave gets stuck. I’ve added counters that display successful updates, delayed updates, and the number of synchronization points in the slave list at the time of the last update attempt.

There are three scenarios:

1. If everything is going well, then the successful updates counter keeps incrementing, and the synchronization point counter displays the number of points transferred during each update.
2. If the JPDA monitor cannot update because the slave just always happens to be in SyncPoint.add(), but the program is actually advancing, then the delayed updates counter keeps incrementing, and the synchronization point counter keeps on incrementing as well, as the list does not get emptied.
3. If the JPDA monitor cannot update because the slave is stuck in one and the same call to SyncPoint.add(), then the delayed updates counter keeps incrementing, but the counter for the synchronization points remains unchanged. That’s because more update attempts are made and get delayed, but no more synchronization points are added.

What I observe happening sometimes (very often, unfortunately), is the last behavior. That means that the slave program is actually stuck in the same call to SyncPointRecorder.add(). There’s no other way. If it moved out of that call but not into another call, it would exhibit the first behavior. If it moved out of the call and into another call, it would be the second.

I have no idea, though, why it gets stuck. Take a look at the source code in the previous posting. I don’t see any reason.

I’ve also noticed that every once in a while I still get a HotSpot VM error:

#
# An unexpected error has been detected by HotSpot Virtual Machine:
#
#  EXCEPTION_ACCESS_VIOLATION (0xc0000005) at pc=0x6d72b030, pid=3980, tid=2848
#
# Java VM: Java HotSpot(TM) Client VM (1.5.0_04-b05 mixed mode)
# Problematic frame:
# V  [jvm.dll+0xeb030]

Again, no clue about that. And I have a NullPointerException in the deadlock detection after I do a manual update of the threads in the slave VM, but that’s probably just an oversight.

During the night I meditated over the question of how to insert the header code for synchronized methods changed to synchronized blocks correctly. In the case I was considering, it was obvious that the instructions needed to be inserted before the instruction that was originally first, and that references to that instruction had to be relocated to still point to it. However, I wasn’t sure if that was always true, and I didn’t know if the exit code before ?return opcodes was correct.

I’m now pretty sure that in all cases, the header code needs to be inserted before the first opcode, and that references need to be relocated. Here’s my reasoning: Before, grabbing the lock was implicitly done by the JVM. Now, the method does it itself, but there’s no reason it should ever be done again. For the remainder of the method, it should still be as implicit as possible.

I also believe that the exit code should be inserted in the place of ?return opcodes, and references to it not be relocated. That’s what I was doing already. Again, my reasoning is that things need to still appear implicit to the rest of the method, and that means in this case the exit code needs to be executed whenever the method returns, so jumps should not go to the ?return instruction itself, but to the beginning of the exit code that precedes it.

I changed the instrumentor accordingly, and now the programs load and run. That’s good.

But when they’re running in the JPDA monitor, quite often they hang. I don’t know why. I keep getting the message “slave VM in edu.rice.cs.cunit.tm.syncPoints.SyncPointRecorder.add. postponing update”. I put that message there. I know when it’s supposed to occur. It just doesn’t make sense to me. I’ve also seen this behavior more often on the computer at work than at home.

Whenever the JPDA monitor is trying to make an update, i.e. read and clear the list the slave maintains, it checks if the slave is just in the process of adding to that list. If that’s the case, it postpones the update. If it went ahead and cleared the list, a race condition could cause the slave to throw a NullPointerException. However, the function is so short, I don’t know why it would be spending so much time in it. I also don’t know if it’s not returning or just calling it so often and at such a high frequency that it appears stuck in there.

Here’s the code for SyncPointRecorder:

/**
* Class that records synchronization points.
*
* @author Mathias Ricken
*/
@IncludeInRuntime
public class SyncPointRecorder {
/**
* List of synchronization points.
*/
private static volatile ArrayList _syncPoints =
new ArrayList();

/**
* Adds a synchronization point to the list.
* Note: This method has to be synchronized,
* but it may NOT be instrumented as such!
* An infinite recursion would be the result.
* The monitor application has to check that
* no thread is currently holding the lock on
* SyncPointerRecorder.class.
* Only then may it clear the list.
* @param sp synchronization point to add.
*/
public static synchronized void add(ISyncPoint sp) {
if (_syncPoints==null) {
_syncPoints = new ArrayList();
}
_syncPoints.add(sp);
}
}

This isn’t an optimal solution, but it should work. It might make sense to change this to a custom data structure, maybe a resizeable ring buffer, but I don’t think that’s what’s causing the program to hang.

I have the frightening feeling that completeness and robustness are inversely proportional, with a very disadvantageous proportionality constant…

I just expanded the method to block instrumentation to the entire runtime, and unfortunately I’m getting an java.lang.IllegalMonitorStateException at sun.misc.URLClassPath.getLoader(Unknown Source). So something’s still wrong… :(

Fortunately, the source code in question has been released under the JRL, so now I’m doing a “Java source” vs. “uninstrumented” vs. “instrumented synchronized blocks” vs. “synchronized methods converted to blocks and instrumented synchronized blocks” comparison… that’ll be fun.

Update

By stepping through the bytecode of the fully instrumented getLoader method I’ve found at least one thing that’s wrong. Since the actual code is released under the JRL, I’ll show simplified code here. The method contains a while loop that begins at line 1, and a continue statement:

synchronized void getLoader() {
while(<1st condition>) {
...
if (<2nd condition>) continue;
...
}
...
}

In bytecode, it looks roughly like this:


if??? 12
...

if??? 8
// 2nd condition met!
goto 1 // goto top of while loop
// 2nd condition not met!
...
goto 1 // goto top of while loop

// code after while loop
...

This got instrumented and turned into bytecode similar to this:

aload\_0
invokestatic (SynchronizedMonitor.tryEnterBlock)
aload\_0
monitorenter
aload\_0
invokestatic (SynchronizedMonitor.enterBlock)

if??? 18
...

if??? 14
// 2nd condition met!
goto 1 // goto top of while loop
// 2nd condition not met!
...
goto 1 // goto top of while loop

// code after while loop
...
aload\_0
invokestatic (SynchronizedMonitor.leaveBlock)
aload\_0
monitorexit
return

// exception handler for all exceptions
aload\_0
invokestatic (SynchronizedMonitor.leaveBlock)
aload\_0
monitorexit
athrow // rethrow


The problem is the goto 1. When the code loops, the aload\_0; invokestatic; aload_0; monitorenter; aload\_0 invokestatic code is executed again. I don't know if that's what's causing the exception, but it's definitely wrong. It's quite clear that the goto must be to the line after this code. It's not clear to me yet if that's always the case, though.