Compact Object IDs Again

I have begun to reimplement the deadlock detector using the compact scheme. I already had such a system a long time ago, but that was with the fat objects, not with the compact array. For this to work with the compact scheme, I have to assign a unique ID to each object, and I’ve tried that before and run into nothing but trouble.

I think I’ve finally figured out how to solve this problem at least for a substantial subset of the classes: Instead of adding a field to java.lang.Object, I add a method public long $$$getObjectID$$$() that by default returns -1, meaning “object ID not available”. All subclasses of Object (except for java.lang.String, for which adding a field also didn’t work) then add the long $$$objectID$$$ field, initialize it in their constructors, and override the method to return the value.

So far, this seems to work for a lot of classes. So far, I haven’t checked the numbers or actually tried to detect a deadlock, but at least I’m getting numbers that seem sensible. I’m getting a few zeros in constructors, but that is to be expected, because there are monitorenter instructions before the object ID gets assigned. I’m getting -1 for Strings and plain Objects, but curiously also for a class’ java.lang.Class instance (e.g. synchronized(Integer.class) { }) and arrays (e.g. Integer[] ia = new Integer[5]; synchronized(ia) { }).

The following Java program

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class ObjectIDTest {
    public static void main(String[] args) {
        // string array
        synchronized(args) { }
        // integer array
        Integer[] ia = new Integer[5];
        synchronized(ia) { }
        // class
        synchronized(ObjectIDTest.class) { }
        // plain object
        Object o = new Object();
        synchronized(o) { }
        // subclass of Object
        Integer i = new Integer(5);
        Integer j = new Integer(6);
        synchronized(i) {
            synchronized(j) { }
        }
    }
}

generates the following trace, starting from where it enters the main method:

0 1 // 000030e4 0003 0001        357 sun.misc.Launcher$AppClassLoader.loadClass(Ljava/lang
0 2 // 000030e4 0003 0052        357 sun.misc.Launcher$AppClassLoader.loadClass(Ljava/lang
0 1 // 000031d7 0002 0003         -1 ObjectIDTest.main([Ljava/lang/String;)V PC=3
0 2 // 000031d7 0002 002d         -1 ObjectIDTest.main([Ljava/lang/String;)V PC=45
0 1 // 000030e4 0003 0001        357 sun.misc.Launcher$AppClassLoader.loadClass(Ljava/lang
0 2 // 000030e4 0003 0052        357 sun.misc.Launcher$AppClassLoader.loadClass(Ljava/lang
0 1 // 000031d7 0002 0058         -1 ObjectIDTest.main([Ljava/lang/String;)V PC=88
0 2 // 000031d7 0002 0082         -1 ObjectIDTest.main([Ljava/lang/String;)V PC=130
0 1 // 000031d7 0002 00aa          0 ObjectIDTest.main([Ljava/lang/String;)V PC=170
0 2 // 000031d7 0002 00d4          0 ObjectIDTest.main([Ljava/lang/String;)V PC=212
0 1 // 000031d7 0002 0104         -1 ObjectIDTest.main([Ljava/lang/String;)V PC=260
0 2 // 000031d7 0002 012e         -1 ObjectIDTest.main([Ljava/lang/String;)V PC=302
0 1 // 00003187 0001 0003          0 java.lang.Number.()V PC=3
0 2 // 00003187 0001 003c          0 java.lang.Number.()V PC=60
0 1 // 00003187 0001 0003          0 java.lang.Number.()V PC=3
0 2 // 00003187 0001 003c          0 java.lang.Number.()V PC=60
0 1 // 000031d7 0002 016b        543 ObjectIDTest.main([Ljava/lang/String;)V PC=363
0 1 // 000031d7 0002 0187        544 ObjectIDTest.main([Ljava/lang/String;)V PC=391
0 2 // 000031d7 0002 01b2        544 ObjectIDTest.main([Ljava/lang/String;)V PC=434
0 2 // 000031d7 0002 01ec        543 ObjectIDTest.main([Ljava/lang/String;)V PC=492
0 4 // 000031aa 0015 0032         -1 java.lang.Thread.exit()V PC=50

The new thing here now is the 6th column of numbers, the one after the wide space and before the class name: It displays the object ID.

The AppClassLoader instance has object ID 357, and it occurs multiple times, indicating that the same instance is used. The object ID now also allows me to match monitorenter and monitorexit instructions more easily. The first two, for example, belong together since they both have object ID 357.

The next two lines with -1 as object ID correspond to the synchronization on the array of String. Then the class loader is invoked again, probably for the Integer class. The next two object IDs of -1 correspond to the Integer array. As stated before, array objects apparently don’t give me object IDs because they somehow don’t overload the $$$getObjectID$$$ method, and therefore the original method in java.lang.Object is executed. Off hand, I don’t even know what class in the rt.jar file is used for array instances. It might be built-in, in which case I can’t do much except try some magic in java.lang.Object‘s default implementation of the method.

The next two lines with zero as object ID corresponds to the synchronization on a class’ Class instance, in this case ObjectIDTest.class. Clearly the $$$getObjectID$$$ method is overridden here because the object ID is not -1. However, the constructor has not been executed and no value has been assigned to the object’s $$$objectID$$$ field. 0 is just the default value that Java puts in a long variable. I have written my program so that valid object IDs start at 1. I might be able to write a special implementation of $$$getObjectID$$$ just for java.lang.Class here.

The next two lines with -1 are using a plain java.lang.Object for synchronization, so the default implementation is invoked directly. No surprise here.

The four next lines with zeros occur in the constructors of the java.lang.Integer class, apparently before the object ID has been assigned.

The next four lines finally are the juicy ones that I have wanted: Two nested synchronized blocks, locking two different Integer instances created back to back. You can see that they have object IDs that are neither -1 nor zero, differ by just one and are nested. Nice.

I’ll have to look at how to deal with these special cases of zeros and -1s and also look at Strings again. Maybe I can get it to work now. Maybe there’s even some general workaround that I could put in the java.lang.Object.$$$getObjectID$$$ method. But even if I can’t, this should cover a major portion of the classes programs actually use, and many of the uses that aren’t covered can probably be easily substituted with something that is.

Share

About Mathias

Software development engineer. Principal developer of DrJava. Recent Ph.D. graduate from the Department of Computer Science at Rice University.
This entry was posted in Concurrent Unit Testing. Bookmark the permalink.

Leave a Reply