A Concurrent Affair

I couldn’t do a whole lot to figure out if String and Object are being used for synchronized blocks in the Java API, as stated before that would be too much work that is too tangential to my project.

What I could figure out quite easily, though, is if the Java API makes use of new Object(). I just scanned for a call to Object.<init>() except for at the beginning of a constructors (if a constructor makes that call at the beginning, then it’s a super() call). Since you can’t do a lot with an object created with new Object() except for synchronization (it provides the methods clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, and wait), I can assume that these instances are being used in synchronized blocks.

Quite a few locations popped up. Another reason why I cannot safely ignore Object.

The last few days, I was looking into whether we could just ditch support for String and Object. To find out if we can, I first scanned for synchronized methods, and then started looking at synchronized blocks.

Unfortunately, after putting in some work to simulate the types of values on the stack and in local variables, I realized that I have to keep track of the types in fields as well. Finding out if any of the synchronized blocks use the monitors of the String and Object classes essentially amounts to performing type unification on the entire Java API and user application. I’m not willing to do that. It seems too ancillary to my project.

Now I’m thinking about how to subclass String and Object while hiding it from instanceof and reflection.

I’m trying to find out whether Object and String are used in synchronization operations in rt.jar. The good news is that neither of them contains synchronized methods. Of course, both can still be used in monitorenter/monitorexit instructions.

That’s a bit harder to find out. I’ll have to scan through all of rt.jar and find out what’s on the top of the stack when these instructions are executed. Depending on how general I want to make this, I can either trust that javac will always encode a synchronized block in the same way (dup; astore\_?; monitorenter; ...; aload\_?; monitorexit), or I have to simulate the stack and local variables.

Even then, I can’t really find out if the runtime type of an object is Object or String or a subclass. All I can find out is whether the upper bound happens to be one of those classes. While subclasses of String are rare, I’m absolutely sure there are functions that accept an Object and then perform a synchronization operation on them.

In those cases, I could add a runtime check and throw an exception, or I could try to perform some very expensive flow analysis. I have no idea how to do the latter, though. I’ll think about it, but maybe doing the class substitution (ProperObject, etc.) is actually easier to do…

When I talked to Corky, my advisor, today, I found out that you may actually have plain Object instances, and that they are actually used frequently too for the purpose of synchronization. That means I do have to be able to treat Object just like the other classes too. Now I have problems with both Object and String.

Fortunately, we came up with two ways to proceed: The first one is easier but less general and satisfying. We could just punt and decide to not support Object and String right now. This is not entirely unreasonable. Using strings as synchronization events is something neither of us has ever seen, and any class can be substituted in place of Object for synchronization purposes.

The other idea is to dynamically rewrite uses of Object and String to make use of added subclasses ProperObject and ProperString which just extend the original classes with the required field. In general, this isn’t hard to do, but any kind of reflection or instanceof done on these objects might be lead astray. I have to think about how to handle this the best way. So far, I haven’t cared a lot about reflection, though. The fields and methods that I add and rename, of course, have to be hidden as well.

Right now, though, I’m very happy to again find a path ahead of me. Dead ends suck.

For the last few hours I’ve been trying to find out which classes behave like java.lang.Object, i.e. which cannot be amended by a field. When I do not attempt to add fields to all of java.lang.*, it seems to work, but there are 230 classes in that package, and of course I want to treat as many of these classes just like the rest. I hope I don’t have to exclude too many classes.

Update

It seems like excluding java.lang.Object and — interestingly enough — java.lang.String is enough. I’m not worried about Object, as I mentioned before nothing is ever just an Object. But how am I supposed to handle strings?

I’ve begun working on my alternative approach. If I can’t add fields to java.lang.Object, I’ll just add them to all direct subclasses. Once this is done, all objects will have the fields since nothing is ever just an Object.

First I scan through all files, and if they are subclassing java.lang.Object, I add the field for the object ID. This ID has to be initialized once and only once, though, which has to happen in the constructors. This is complicated by the fact that one constructor may call another:

public class ThisCtorTest {
public ThisCtorTest() {
System.out.println("ThisCtorTest()");
}
public ThisCtorTest(int i) {
this();
System.out.println("ThisCtorTest("+i+")");
}
}

Here, a call to ThisCtorTest(int i) will also invoke ThisCtorTest(). If the initialization code is added to both constructors, it would be run twice.

Conceptually, the constructors (their name in the class files is <init>) form a call graph:

I only add the initialization code to constructors that are sinks, that don’t call any other constructors. In this example, these constructors are <init>\_0 and <init>\_2. Calls to <init>\_1 and <init>\_3 both invoke <init>\_0 and thus execute the initialization code.

If I decide to initialize the field, this code will be inserted:

aload\_0
getstatic (nextObjectID)
dup2
lconst\_1
ladd
putstatic (nextObjectID)
putfield (objectID)

which corresponds to the Java code

objectID = nextObjectID++;

I may have to make this section synchronized.

Of course, nothing is so simple with the JVM that it could work right away, now is it? :(

Java is being bitch about adding and initializing fields in Object. But why should these things be easy anyway? It’s a frickin’ field, after all… I’m going to bed.

Update

Argh… I woke up and realized I may have to make the field transient so that it doesn’t get serialized. Nope. Wasn’t it. Having my hopes crushed is so heart-breaking.

Update

Ok… apparently it just isn’t possible to add fields to java.lang.Object. I guess now my alternative strategy is to add a field to every class that extends java.lang.Object. Weee!

I decided to take care of another item on my to-do list, item 3: I added the current thread to the Object.* events. That was necessary to accurately update the display in the thread monitor.

Now I’ll start my attempts at a more compact representation. I think I’ll try to add a static instance counter to SyncPointRecorder, which will get incremented during every instantiation of an object. This number will serve as a quasi-unique identifier in Object.

I first considered adding another identifier like that to the Thread class, but I don’t think this is necessary. I’ll use the object ID as thread ID as well. That means threads won’t have consecutive IDs, but that doesn’t really matter.

As to the format… It will be an array of primitive data. I need to store the type of event, which could currently be a byte, and up to three longs (object ID, thread ID, timeout). It would be the easiest to just use four longs (32 bytes), but that would sometimes be a waste of 23 bytes compared to using a byte for the event type and just as many longs as necessary.

So I guess I’ll use a byte array and do some bit math on the longs. The actual format of the even in the byte array will be dependent on the event type.

Could it really be so simple? After I found out that programs seem to work if I exclude the SynchronizedMethodToBlock instrumentation strategy, I spent days looking over its source code. There wasn’t a whole lot, but I knew the code had to be directly or indirectly responsible. It had to be a somewhat subtle issue, since it didn’t occur all the time.

One of the things that happens most rarely, probably, is that an exception has to unwind the stack yet execute the finally handler that I add to unlock the monitor. And it seems like this is where the problem actually was. I had adjusted the maximum stack size field to be at least one, since I need one stack slot for the aload\_0; monitorenter/monitorexit sequence. However, in the finally handler, one slot is already occupied by the Throwable instance that was thrown. The object whose monitor to be unlocked is a second item on the stack.

I enlarged the stack to at least two, and now it seems to work! I closed item 9 in my to-do list. I also took care of item 5, removing the events for (static) synchronized methods, which was trivial. Since synchronized methods get turned into regular methods with a synchronized blocks, only events for synchronized blocks are generated at this point.

At the Java PLT meeting today, we discussed several aspects of my project. Corky agreed that events before and after the slave’s main method can be ignored. He also said that class loading can almost be viewed as an atomic step. It should be acceptable to ignore events that happen inside the class loader, but the static initialization of a class must be observable.

I’ll first try to use a “do not record” flag per thread to ignore events, as discussed previously. Filtering out the events in the master should be possible too. Corky expected that shipping the bytes of the classes to the master using ClassFileLoadHook on every class load would be too expensive.

The HotSpot error that I’m currently having goes away if I don’t run the SynchronizedMethodToBlockInstrumentationStrategy. Without it, I was able to run a small GUI program. It was veeeery slow, though. Right now, the maximum event list size is relatively small: It can store only 512 events. Once the list is full, the slave initiates a push. I can enlarge that list, but I definitely have to make sure that master pull also works, i.e. that the master can pull at any time as well. That was the original design, but I haven’t checked lately if it still works.

I’ll also have to create a more compact representation. I have no idea how large the footprint of the list is right now, but it might be gigantic. What I really need to store in there is a unique thread ID, a unique object ID if it operates on some object (e.g. claiming its lock), and maybe some additional primitive data (e.g. timeouts). That should only take up a few bytes, and primitive data should suffice. That would allow for a faster data transfer and a more efficient garbage collection.

But before I can improve that, I’ll have to take another look at SynchronizedMethodToBlockInstrumentationStrategy X(

Update

Well, master pull doesn’t crash, but it seems to slow things down quite a bit. I’ll have to look into that too.

Another idea worth considering is completely moving the instrumenting class loader out of the slave VM. The Java VM Tool Interface (JVMTI) has a ClassFileLoadHook that provides the raw byte array just before the class is loaded. This should yield the best mapping between original and instrumented classes, just as good as offline instrumentation since the slave VM doesn’t do anything it doesn’t do with the original files.

The only problem right now is that this hook is only available in JVMTI, which is a native C language interface. It’s not available in JDI. There is a new addition to the Java 5.0 API, java.lang.instrument which may be able to do the same, but I haven’t looked at it yet and I don’t know how it influences the VM it’s running in.

I’ve been sick for a while, so I haven’t done very much. I fixed a few small bugs, though, and ran some tests.

One test involved finding out if the class loader can be run in parallel to other Java code. It is fairly clear that this has to be possible, but I still wanted to know this for sure. The answer, of course, is “yes, it can run in parallel”. That, of course, means that the class loader can modify thread timing. Our class loader and the entire framework should be invisible, though.

Right now I’m trying to figure out how much of an impact that has. The changes to the class files themselves are relatively small, so they don’t matter at a larger scale. The order of two instructions in threads might change, but it doesn’t have any effect on atomic blocks. Once I get rid of all the other problems that are still there (\*puke\*), I should be safe with classes instrumented offline.

Online instrumentation should produce identical files (it does) and identical events (it doesn’t). There are actually two problems:

1. A short stub program (CUnitRun) has to be run to install the custom class loader. This program already generates events that do not appear if the program is run by itself.
2. The instrumenting class loader will intervene whenever a class needs to be loaded. While the classes of the class loader itself have been instrumented in a way so that they do not generate events, they make use of Java API classes that do generate events.

It probably makes sense to ignore any events that occur before the slave’s main method is entered or after it has been exited. The programmer doesn’t have any influence on them, and they may be assumed to be correct. In the case of the CUnitRun stub program, the events generated therein are ignored as well. It’s the main method of the actual slave program that counts.

Removing the events generated by the class loader is much more difficult. Right now I’m thinking about setting a “do not record” flag when the class loader is entered, and resetting it when it is exited. That would prevent the API classes used in the class loader from recording events. This flag must be set on a per-thread basis: Only events occurring in the thread that currently runs the class loader should be ignored. I really have to stress that because it just occurred to me :)

I’m not exactly sure how this needs to work with other class loaders that the instrumenting class loader needs to cooperate with, but that’s a topic for a more thorough inquiry anyway. I also do not know how it must work with Java’s default class loader, though. Without the instrumenting class loader, the Java class loader probably does generate events. With the instrumenting class loader, most or even all events may be removed. For a first shot, it might be ok to also exclude class loaders and assume them to be correct, though.

Update

I’ve been thinking about the “do not record” flag a bit more. It would have to be implemented in a way that’s thread-safe and that doesn’t disturb the rest of the system, i.e. it should probably has to be lockfree. That’s going to be hard. Another option is to not filter them out in the slave but in the master. To do that, the slave would have to enqueue additional “thread x entered class loader” and “thread x exited class loader” events. This should involve less logic on the slave side.

I solved the problem of “uninstrumenting” calls to Thread.* methods with a very high degree of code reuse: I applied the same instrumentor that changes calls to original an Object.wait method to the wrapper method Object.wait$$$Wrapper$$$, except this time the roles are reversed: It changes calls to the wrapper method Thread.start into calls to the original method Thread.start$$$Old$$$.

Now code that was previously only used for global instrumentation is also used for local instrumentation, albeit only in the case where it needs to be “globally undone”. That might make it a bit more confusing, but generally it was the right thing to do. There wasn’t any point in rewriting what’s already there.

P.S.: Maybe locally vs. globally isn’t the right terminology. Locally vs. non-locally? Ugh…

For some strange reason, which probably was a search path difference between my machines, I ran into a problem with incorrect line number information yesterday, but at first only on my work machine. When instrumenting java.lang.Thread.start(), the instrumentor lamented about a program counter (PC) value that was out of range. For a very short method, it was asking for a PC of 7, and several other values, up to 43 or so. Of course, they didn’t exist, so the instrumentor failed.

The problem was that the original method, which did have PCs up into that range, was replaced by a much shorter wrapper, but the line number information was kept around. I had thought of that problem, and code was there, but it didn’t work. I was comparing instances and not names (pretty much == vs. .equals()). I don’t know why it never got tested up to this point. Anyway, this is fixed now.

I also realized that I’ll probably have to instrument a few of my system classes, like InstrumentingClassLoader, in a different way. Their code should be invisible to the monitor, so no synchronization points should be queued up whule they are executing. However, some methods in java.lang.Thread are renamed and replaced by wrapper methods that also make the necessary calls to produce synchronization points.

Let’s look at the different events and the way they are instrumented. There are events generated by methods that get instrumented locally — there’s no effect on the callers:

Then there are events that need to be instrumented globally — the callers call a different method because the method cannot be renamed:

And then there are the remaining events:

The last group of instrumentations shouldn’t happen for my system classes, period. The second group can also just be left out. That means the classes call the original methods and no synchronization points will be generated — just what I want. The first group, however, causes problems: If I carry out the instrumentation as with other classes, then the wrapper methods will be called and synchronization points will be queued up. I also can’t leave away the instrumentation since it’s local; the instrumentation only happens inside the callee.

This means that for the events in the first group, I’ll have to create a special instrumentor that will “undo” the instrumentation just for a select few classes.

I think I found the reason for the hanging slave programs. It wasn’t an interaction between my modifications and JPDA, it was just an interaction between JPDA’s lack of straight-forwardness and my lack of intelligence. There existed a code path in the portion of code that read the slave’s list in which not all threads were resumed again. After a while, that could lead to all threads being suspended.

I also implemented the slave push technique. It seems nice so far and is definitely the right way to approach this, but it is less predictable for me. I’m still playing with it.

Now that I have left one problem behind me and have opened two new arenas, I’m running into another one of my beloved HotSpot errors:

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

No clue yet what this is, but I’m working on it.

Over the last few days, I added a somewhat large number of bugfixes. The dependency fixpoint actually wasn’t complete (annotations weren’t included), and the MonitorCallInstrumentationStrategy sometimes added constant pool entries for a method with an empty string as name and descriptor. I also changed the transfer process of the synchronization point list from an item-by-item style to a (hopefully faster) whole-list access.

During my meeting with Corky today, he suggested using a slave-push architecture: When the list is full on the slave side, the slave causes the master to transfer and reset the list. That should solve some of the balancing issues about the list size. I’ll also try to use a more compact representation of the data in the list.

I’m not sure that these changes will fix the hang problem, though.