A Concurrent Affair

Earlier I hypothesized that incorrect line number information might be the cause of the stack frame crashes. I just spend about half an hour comparing the line number information in instrumented and non-instrumented class files to see if I updated the line number information incorrectly.

Unfortunately, I haven’t found anything. In all the classes I’ve looked at, the old and new line numbers point to the same opcode, modulo insertions, of course. I’m happy that I apparently did a good job when I wrote the code, but I’d much rather be disappointed by myself and now know how to fix the problem than to have no clue at all now.

Back to square one regarding this issue. Of course, it could also be some special case that I have not considered yet. Fortunately, I can continue working on other things.

I was just thinking about the representation again. I think the representation with the two hash maps is right, but now I’m worried about inconsistencies between the data I keep and the data I get from JPDA. Right now, I update my data in the hash maps. Maybe I should always replace my data with fresh, guaranteed-to-be-accurate data from JPDA whenever I get it. I think for now I’ll just add a few assertions to find out if inconsistencies occur.

While I was mulling this over, I had an idea why getting the stack frames of the threads may crash the VM after I’ve added in instrumentation of synchronized blocks: Whenever I instrument synchronized blocks, I change bytecode in a lot of places. Maybe I change the line number information that goes along with the bytecode incorrectly? I know that I do attempt to change it, but I should definitely go over it again.

After getting several things to work in the early morning ours yesterday, I’ve been cleaning a few things up in the thread monitor source. One thing I’m working on is the unification of the data representation.

Since I want as little interaction between the master and the slave as possible and since I want to avoid JPDA’s idiosyncracies regarding access and thread state — and also for pure ease of use (accessing remote data using JPDA is more than cumbersome) , I am duplicating some of the data structures and translating the data I get from JPDA mirrors.

There are basically two separate lists: a list of threads, and a list of locks (Java calls then monitors; so far, I have chosen to call them locks in order to avoid confusion between these monitors and my monitors — ThreadMonitor, ObjectMonitor, SynchronizedMonitor; I should probably do a thorough renaming of all the terms to get my terms in line with the rest of the world).

An entry in the thread list contains a list of owned locks and a reference to the currently contested lock. An entry in the lock list contains a list of waiting threads and a reference to the owning thread. It’s something like this (pseudocode):

class ThreadInfo {
List ownedLocks;
LockInfo contestedLock;
}

class LockInfo {
List waitingThreads;
ThreadInfo owningThread;
}

Now, when I change a value in one of the locks, for example, that change needs to be reflected in all the thread entries that somehow contain that lock, either as owned or as contested lock.

Right now, I’m going through the entries and I update them, but I’m not convinced I actually keep all of them up-to-date. I also think this might get complicated later. Conceptually, the thread and lock information should be singletons per unique ID, so maybe I should actually model it that way: The actual entries are stored in hash maps indexed by the unique ID, and the entries only store unique IDs that serve as indices into the hash maps:

class ThreadInfo {
List ownedLockIds;
Long contestedLockId;
}

HashMap threads;
HashMap locks;

Of course, this makes lookups a bit more tedious. You absolutely have to keep track of both lists separately, even if you don’t really care all that much for data consistency. A hybrid approach would be to store the thread and lock information in a hashmap, and also store copies in the entries but allow them to be out-of-date. Access to up-to-date information can be obtained through the hash map and the unique ID stored in the entry to be looked up:

class ThreadInfo {
List ownedLocks;
LockInfo contestedLock;
}

HashMap threads;
HashMap locks;

This approach tries to get the best of both worlds, but it incurs higher memory use and is possibly more confusing because there is more than one way to do something.

Any thoughts?

Update

I’ve decided to go with a variant of the second model. There’s just less that can go wrong with this implementation. I have changed the lists to sets, though. Each id should be present only once, so a set is a more natural representation here. The data structure now looks like this:

class ThreadInfo {
Set ownedLockIds;
Long contestedLockId;
}

HashMap threads;
HashMap locks;

The last day has been frustrating again. Whenever I instrument the runtime for synchronized blocks, I’m getting the VM error I’ve mentioned earlier, but only when the thread monitor is attached. If I let the program run unmonitored, it works. If a runtime is used without instrumentation for synchronized blocks, it works even with monitor attached.

That seems to indicate that there’s some interaction between the synchronized blocks and the way JPDA attaches to the slave VM that I don’t understand and that’s not documented. I’ve spent hours commenting out one thing or another, experimenting with the order of things to figure out what exactly makes the slave VM hiccup.

I still haven’t been able to figure it out, but it has something to do with suspending and resuming the execution of the slave VM. Grr.

Update

Apparently the problem is caused by reading out the stack frames of the threads. Why this happens is a mysterium to me. It used to work before, when the runtime was not instrumented for synchronized blocks.

This might give me a chance to continue working, though. The stack frames aren’t necessary for the concurrent unit testing project, they would have been neat for a thread monitor, though.

All the work today made me realize that all the variables I am accessing from the thread monitor should probably be volatile. I am worried that the HotSpot VM decides to optimize and drop fields that I need. That also means writing my own data structure implementation for the synchronization point list, something that makes sense anyway. An automatically resizing ring buffer could be useful.

Also, my new PC should be ready for pickup tomorrow. Unfortunately, I haven’t found anyone who can take me there tomorrow afternoon yet. A trusted friend volunteered her lunch break on Friday already, though. Thank you :)

I’m running tests again that use a Java runtime in which synchronized blocks have been instrumented with logging calls. This is pretty much the minimum capability I need. Georges does it too.

I’m getting both a HotSpot Virtual Machine error and an exception in the JPDA thread monitor I wrote:

# An unexpected error has been detected by HotSpot Virtual Machine:
#
#  EXCEPTION_ACCESS_VIOLATION (0xc0000005) at pc=0x6d728200, pid=5864, tid=5844
# V  [jvm.dll+0xe8200]

I don’t know if the two have anything to do with each other, but the exception I got in the thread monitor is due to a null reference where I’m expecting a ThreadReference. This means a synchronized block entry has been logged but Thread.currentThread() returns null. Fantastic. Again I’m finding I’m doing things too early during VM initialization.

I think it will be very hard to distinguish at instrumentation time which places cause this behavior. That means I probably have to instrument them all and decide at runtime. Now, there are two options: I can ignore the event, which is probably ok since the Java VM clearly hasn’t been set up completely yet; or I can report and special-case it, which might get hairy on the thread monitor side.

Update

I’ve started to go the special-case route (I’m trying to be thorough: if something can be reported, it should be — it can always be ignored later), and I’ve noticed that the HotSpot VM error only seems to occur when the JPDA thread monitor is attached. If I run the slave program without the monitor, the log functions do get called, but no error occurs. Quite peculiar.

The paper I read also uses a different approach for instrumenting Object.∗. I chose to add a wrapper that logs and forwards, and then to change all calls to Object.∗ to point to Object.∗<Wrapper>.

The advantage of that is that only the bytecode size of the Object class increases. The other classes have to be touched, but it’s just a change in the reference. Unfortunately, it also means that I need to touch Java’s private parts.

Georges, et al chose to leave the Object.∗ methods unchanged and then add the logging calls at every call site. That increases the bytecode size of all classes, but it might be easier to do.

I’ll give it a shot.

I’ve described already why instrumenting synchronized methods is an instrumentation with global effects: We need a “try to enter” logging call before the lock is claimed, and Java synchronized methods automatically do that, so the logging call needs to happen at the call site before the call is made.

Corky, my advisor, pointed towards an interesting 2004 paper on JaRec by Georges, et al. The implementation shares many aspect with the approach we are following and I’ll have to study it more closely, but one interesting idea I could glean from it already was a way to make instrumenting synchronized methods have only local effect:

A synchronized method

synchronized T foo(T0 t0, T1 t1, ...) {
S
}

is transformed into an unsynchronized method and a synchronized block, which can then later be instrumented in the usual manner:

T foo(T0 t0, T1 t1, ...) {
synchronized(this) {
S
}
}

For a static synchronized method, instead of this‘s lock, the lock of the class object is claimed. On a Java bytecode level, case has to be taken that the lock is released properly in case of exceptions, since this now has to be handled manually.

I don’t know why I didn’t test this way myself in the first place. I can only assume I wasn’t sure about the precise semantics of synchronized methods at the time. Also, this scheme won’t work for synchronized native methods. They will still have to be handled with the wrapper approach, incurring global effects.

This is nonetheless a very interesting approach that I will have to inspect. On the one hand, it reduces the absolute number of changes that have to be made (by making the instrumentation have only local effects), on the other hand, it changes the number of ways in which class files need to be changed (by transforming synchronized methods to the canonical case of a synchronized block).

Unfortunately, the test I just ran showed me I still have problems instrumenting classes deep inside the runtime.

In general, the instrumentations I’m doing can be grouped into two categories: Those that only require local modification of a class file, and those that require changes to all the other class files that use it as well.

Instrumentations with Local Effects

The first case is a lot easier to handle. Instrumenting Thread.* (except for sleep and yield) and instrumenting synchronized blocks belongs here. As mentioned already, in the former case I just rename the old method and substitute a new method that logs and forwards. Because this method has the same name, the classes that use the method will never know anything changed. In the latter case, I just insert log calls before and after the MONITORENTER and before the MONITOREXIT opcodes. This only affects the code locally.

Instrumentations with Global Effects

Unfortunately, there are other events that need to be monitored. Object.*, Thread.sleep and Thread.yield, for example, are native methods and cannot be renamed. For these methods, I introduce an additonal wrapper method that does the logging and forwarding. Then I need to scan through all other files and make calls to the original method point to the wrapper method.

Synchronized methods automatically claim a lock, there’s no opcode that I can look for, so the “trying to enter” event must actually be handled at the call site, as opposed to inside the method. That means I need to go through all files and insert “trying to enter” log calls before calls to synchronized methods. That, of course, also means that I have to know what methods are synchronized in the first place.

In synchronized native methods, I can’t insert the “entered” log call, so I need to follow a wrapper approach, just like with the Object.* methods.

Results

The upshot of instrumentation with global effects is that you cannot perform all instrumentations on just a few classes in isolation. If you instrument Object.*, Thread.sleep, Thread.yield, or synchronized methods in one class, you have to make corresponding changes in all classes that use it.

Since I’ve run into trouble instrumenting the entire Java runtime, we’ve been considering not instrumenting all portions of it and maybe leaving large portions of java.lang.* uninstrumented. Of course, the Thread and Object classes have to be instrumented, but others could be left out.

With global effects, though, an arbitrarily partial instrumentation might not be possible. It seems like we need to instrument at least something akin to the smallest transitive closure of classes. Fortunately, the way I have global-effect instrumentations set up right now, a program should work even if it is not instrumented correctly. An uninstrumented class would just call the original method, not the wrapper. The program couldn’t be monitored correctly, but it would at least work.

That doesn’t seem like a very helpful thing, since we really need complete information about all the events, but depending on the semantic model we use, it might save the day: If we assume that certain portions of the runtime are thread-safe, then we can safely lose some or all synchronization information about that portion.

Earlier I was wondering how to distinguish between classes I needed to instrument and those that are in the runtime and thus assumed to have been instrumented correctly already. This is easier than I thought: If a file cannot be loaded through some other means, there is a special method findSystemClass to load system classes. I’ll only instrument classes loaded through other means, e.g. directly from a class file. A “do not instrument” annotation might still be useful, though.

I’ve already mentioned that the JPDA monitor reads and clears a list mainainted in the slave. Reading isn’t the problem, but clearing is a bit tricky. If the monitor just had to read, then hardly any synchronization were necessary (well, I’d have to write my own version of ArrayList. I looked at its source and noticed that ArrayList increments the size first, then puts the entry in. It would be cleaner the other way around).

The monitor needs to clear the list too, though, and that is a write access. This is a recipe for a race condition. If the monitor clears the list after the slave has determined where it needs to put the new event but before the slave has actually put the event into the list, the slave will experience a NullPointerException (the monitor resets the list to null. I couldn’t find a way to create a new ArrayList).

It is somewhat ironic: A synchronization bug, in a program that is supposed to fight synchronization bugs.

I’ve devised two strategies to prevent this problem:

1. Whenever the slave adds an event, it grabs a lock (using a synchronized method). The monitor can check if that lock is held by a thread and postpone checking the list until the thread has finished adding the event. This can somewhat easily be done using a “method exit event” from JPDA. The advantage is low memory use and an immediate update right when the slave is done. I’m afraid that enabling and disabling this JPDA event will be too slow.
2. Another strategy is to just not clear the list if the lock is held. In that case, the monitor remembers how many entries in the list it has already seen. The next time around, only new events will be processed. Eventually (hopefully?), the lock will not be held, and the list can be cleared. The advantage here is no added cost, but at least theoretically, the list can grow without bound.

Of course, both methods can be combined, with 1. providing a low-memory fall-back for 2. Right now I have implemented option 1, and at least in simple tests it seems fast enough, so I’m not writing 2. yet.

However, I’d like to test this on a larger program, and that large program is DrJava, of course. To efficiently do that, I’ll need to dust off and modify the custom class loader again, so that’s what I’ll probably do next.

Running a program will mean running the monitor with the slave as a parameter. The boot classpath for the slave also has to be changed so that it includes the instrumented runtime files and several monitor classes (the SyncPointRecorder class, for example). The monitor then loads the slave, and the class loader instruments all user classes.

Since I don’t want to instrument classes again that have already been instrumented (that would wreak havoc; foo<Wrapper> methods would call themselves, etc.), I’ll have to figure out how to distinguish user classes from runtime classes, or better: instrumented classes from uninstrumented ones. Maybe I can use Java annotations for that?