A Concurrent Affair

This morning — silently typing in bed ;) — I wrapped up some work on the SetConstantsStrategy. There are still a few limitations, but for what I’m using it, I think it’s reasonable: It only works on static fields, so I only have to deal with the one <clinit> method, not with a varying number of constructors. It works both for final and non-final fields, but they have to be initialized with a simple value. It cannot be a method call, and it shouldn’t be in a static initializer block with some complicated if-then-else stuff. I only scan through the <clinit> code for the first putstatic referring to the field. Then I check that the preceeding instruction is one that simply loads a value, not one that makes a method call or performs arithmetic. Then I remove that instruction and replace it with one that loads the new data. For setting the probability of a yield to different values from 0.0 to 1.0 or enabling and disabling things by changing a boolean, this is good enough.

I also added boolean flags to control if the yields and delays at different places are actually enabled: Now I can independently control them at

• before a Thread.start
• before a Thread.exit
• before a Thread.run
• before a Thread.join
• before an Object.notify
• after an Object.notify
• before an Object.wait
• after an Object.wait
• before a monitorenter
• after a monitorenter or monitorexit

I did this because Corky and I agreed that I was placing random delays in too many places, and at least I believe there is some kind of balance between delays at different synchronization points. Switching these on and off could give me a chance of exploring the interactions and finding that balance.

When I finished adding the flags, it occurred to me that maybe I shouldn’t have used one probability for all of the yields and then boolean flags for kind of insertion point; maybe I should have used probabilities for each of them. But for now, I’ll go with this implementation. Just to show some useless detail again, here are the command line arguments that I currently have in the instr.setconstants.xml file:

<args line="-force -nobackup
-X set-const=edu.rice.cs.cunit.SyncPointBuffer::RANDOM_YIELD_PROB:=1
-X set-const=edu.rice.cs.cunit.SyncPointBuffer::RANDOM_YIELD_THREAD_START:=false
-X set-const=edu.rice.cs.cunit.SyncPointBuffer::RANDOM_YIELD_THREAD_EXIT:=false
-X set-const=edu.rice.cs.cunit.SyncPointBuffer::RANDOM_YIELD_THREAD_RUN:=false
-X set-const=edu.rice.cs.cunit.SyncPointBuffer::RANDOM_YIELD_THREAD_JOIN:=false
-X set-const=edu.rice.cs.cunit.SyncPointBuffer::RANDOM_YIELD_PRE_NOTIFY:=false
-X set-const=edu.rice.cs.cunit.SyncPointBuffer::RANDOM_YIELD_POST_NOTIFY:=false
-X set-const=edu.rice.cs.cunit.SyncPointBuffer::RANDOM_YIELD_PRE_WAIT:=false
-X set-const=edu.rice.cs.cunit.SyncPointBuffer::RANDOM_YIELD_POST_WAIT:=false
-X set-const=edu.rice.cs.cunit.SyncPointBuffer::RANDOM_YIELD_PRE_MONITOR:=false
-X set-const=edu.rice.cs.cunit.SyncPointBuffer::RANDOM_YIELD_POST_MONITOR:=false"/>

It overrides all the yield flags and the probability. The -force flag is there to allow instrumentation of already instrumented files.

Now we’re off to a Christmas party at Dr. Nguyen’s house. Thanks for the invitation!

This week, I’ve successfully tackled the problem with the parameter lists in the reflection-based Thread Checker. Ironically, the parameter names are available when I do my own thing, but when I’m using Java’s convenient, built-in reflection API, the names are pieces of information I cannot get.

So my first step was to enhance the @PredicateLink‘s method attribute. It is now possible to specify the order of the parameters by listing the parameter names in parentheses, e.g. method="myMethod(param1,param2,param3)". The first parameter of type Object, used to pass the value of this if possible, is ignored in this list.

After that was done, I could have rewritten all the method attributes for the annotations. But I realized that I do have the required information when I’m processing the class files, and I need to do that briefly even for the reflection-based Thread Checker. So after the manual process worked, I added an automatic updating function that changed a method attribute without parameters (old format) to a method attribute with parameters (new format). Now all the old annotations work with both Thread Checkers. One problem solved, quite elegantly I think; I just still think it’s ironic that I can’t get the parameter names using reflection…

After that, I added a few more common annotation, e.g. the @Not... flavors for all the @Only... annotations I have, and I added @Any and @None annotations for all of those common annotations, which are @Combine-style annotations that combine using or and and, respectively.

I also separated out the classes that belong just to the annotations, and not to the framework involved in rewriting the bytecode, and put those classes in a separate tclib.jar file. When compiling, only those files are necessary. The full tcrt.lib is only necessary to do the bytecode rewriting and run the Thread Checker. I think separating the two sets of classes was a good idea, because now it is possible to ship a much lighter 34 kB tclib.jar (47 class files) with applications that use it, like DrJava, and only distribute the 734 kB tcrt.jar (617 class files) when the debugging capability is needed.

Mea culpa, though: I still haven’t written more documentation, I still haven’t extended Concutest-JUnit, I still haven’t collected more performance data, and I feel I’m a little behind on my grading (even though the other TAs haven’t done more either). Tomorrow (read: today) I’ll probably hold my last regularly scheduled office hours. Things are moving ahead, albeit slowly.

During the last couple of days I added what thought were the last major features missing in the Thread Checker: It can now import <predicate>– and <combine>-style annotations from XML files, and I’m getting subtyping warnings for predicate annotations, both offline and on-the-fly.

However… Now I’m noticing a problem that I was aware of, but just didn’t consider serious: In the reflection-based Thread Checker, I can’t associate arguments with parameter names, and the order in which the parameters are reported is undefined. Using the code that I’ve written, the @OnlyThreadWithName(value="foo", regex=false) annotation requires a predicate public static boolean check(Object thisO, boolean regex, String value). I wrote it the other way around, with the String in the middle.

With the offline instrumentor, I have the variable names, so I can still match the values correctly, even if the order isn’t right. But using reflection, I don’t have the names… At least not using the normal API. I guess I could get them somehow, but that would mix the blend of my code to inspect class files and reflection. But that’s probably what I need to do.

I’m still trying to figure out if some invariant annotations should be inherited from subclass to superclass, i.e. in the opposite direction of regular inheritance and the way annotations are inherited now.

Let’s assume that I do this. @NotThreadWithName is an invariant that makes a precondition stricter, so it will be inherited in the regular way; its behavior is covariant, even though I’m not sure if that’s the right word for it.

@OnlyThreadWithName, I believe, is an invariant that should make the precondition less strict, at least when there are several of them, because my intuition is that users want to combine them using or: It just doesn’t make sense to combine them using and. So let’s assume that I inherit @OnlyThreadWithName from subclass to superclass, i.e. in the opposite direction, or contravariantly.

What does that mean? And does it make sense? Consider the following program with annotations:
class Super {
void foo() { }

void wibble() { }
}

Here are the invariants end up getting applied for each method:

• Super:
  • foo(): None.
  • fee(): May only be run by threads with name “aux”.
  • wibble(): May only be run by threads with name “aux”.
• Mid:
  • foo(): May not be run by threads with name “main”.
  • fee(): May only be run by threads with name “aux”.
  • wibble(): May not be run by threads with name “main”. May only be run by threads with name “aux”.
• Sub:
  • foo(): May not be run by threads with name “main”.
  • fee(): None.
  • wibble(): May not be run by threads with name “main”.

The biggest question here is probably how the invariants for Mid.wibble() should be combined. If they are combined using and, then the only thread allowed to run has the name “aux” (not “main” and “aux”); if they are combined using or, then all thread names except for “main” are allowed (not “main” or “aux”). If the names “main” and “aux” are changed so that they are identical, then the possible results are even more nonsensical: No threads at all, or all threads allowed.

I think my intuition about combining annotations that relax the invariants using or was wrong. It should always be and. If a programmer wants to use or, that can be achieved with a little bit more code using a @Combine-style annotation.

Perhaps another idea to investigate would be that of allowing necessary and sufficient predicates: A necessary predicate must be fulfilled for a method to be executed without warnings, but it is not enough by itself; if another predicate fails, a warning is generated. On the other hand, when a sufficient predicate is fulfilled, other predicates may fail, and still no warning is generated. That is a similar notion than combining using and and or, but perhaps more precise. Right now, I don’t see a need for this, though.

The covariant and contravariant inheritance of annotations could be interesting and I have a better idea of how to implement it, but without a connection to the idea of restricting or relaxing preconditions, I don’t quite see a consistent, compelling theory developing. The custom predicates make the theory a little bit wobbly anyway. Also, right now I can’t come up with a situation in software engineering that would require contravariant propagation of annotations.

So, right now it seems like I’ll just add subtyping warnings for predicate annotations, and I noticed I have to do XML import for predicate annotations, and that’s it.

I just looked at the subtyping warnings generated from the normal @OnlyRunBy (before-predicate) annotations, and they definitely a bit weird. Not necessarily wrong, but perhaps not what I really want.

Let’s assume there are three classes, Super, which is extended by Mid, which is extended by Sub. Super has an @OnlyRunBy annotation, which affects all methods in all three classes. Sub has an @OnlyRunBy that affects only its own new method, fum(). The method Sub.bar() also has a @OnlyRunBy annotation.

@OnlyRunBy(@ThreadDesc(name="main"))
class Super {
public void foo() { }
}

@OnlyRunBy(@ThreadDesc(name="another"))
class Sub extends Mid {
public void fum() { }
@OnlyRunBy(@ThreadDesc(name="auxiliary"))
public void bar() { }
}

Super.foo() may only be run by the “main” thread. The same applied to Mid.bar(): It may only be run by the “main” thread.

Now it gets weird: Sub.fum() may only be run by a thread whose name is both “main” and “another”. That’s probably not what the programmer intended… The programmer might have wanted to relax the requirement and allow the threads “main” or “another”.

And now we currently get a subtyping warning: Sub.bar() may only be run by a thread whose name is both “main” and “auxiliary”, and here the method in the subclass has stricter prerequisites than the method in the superclass, so a subtyping warning is generated.

Technically, with my current implementation of combining the annotations using and, the warning is correct. However, my contention is that someone using @OnlyRunBy probably wants to relax the prerequisites, and that would mean adding @OnlyRunBy in subclasses is ok. What should generate a warning is if an @OnlyRunBy annotation in a subclass is present, but it is somehow removed in a superclass. That’s not how my current system works. Subclasses and methods in subclasses get annotations from superclasses and methods in superclasses, but not the other way around.

What would probably be the right thing is this:

• Annotations that restrict preconditions should be passed on from superclass to subclass, and if a subclass introduces a stricter precondition that the superclass doesn’t have, a warning should be generated.
• Annotatons that relax preconditions should be passed from subclass to superclass, and if a superclass has such a relaxed precondition that the subclass does not have, a warning should be generated.

That means that restricting annotations should be covariant, and relaxing annotations should be contravariant. If the annotations are found in a different way, that’s an error in the threading discipline.

Unfortunately, I don’t really know how to write this. How do I decide what gets combined using and (restricting) and what using or (relaxing)? With the user-written predicate annotations, I can’t assume which behavior is wanted because I can’t possibly figure out if a user-written Java method serving as predicate makes the preconditions stricter or more relaxed, so the user would have to pick covariant or contravariant behavior when writing the annotation. That’s not hard, but again, right now I don’t know how to combine them.

I’ll have to talk to Corky if my intuition here is right and if that should go into my current code (which would cause quite a delay), if that should just go as theory into my thesis, or if I’m completely on the wrong path here.

I don’t think I am, though, because these warnings provide static checks for the maintenance of a threading discipline in the use of extensible libraries, something that I consider one of the greatest, if not the greatest, current challenge in software engineering.

So, what’s left to do? Lots, of course. Mainly, I have to run benchmarks and prepare different versions of DrJava for comparison. But on a shorter term, what’s left to develop?

Yesterday I noticed that I actually do not perform any subtyping warnings on predicate checks (@PredicateLink– and @Combine-style annotations). I probably did this because it’s not exactly clear which predicates are equivalent and which aren’t, so there may be a lot of false positives. I also noticed that I’m doing subtyping warnings on @OnlyRunBy annotations, even though I’ve really only worked out a subtyping relation for @NotRunBy annotations.

I think I am going to reexamine the behavior of @OnlyRunBy annotation subtyping, and then provide a way to choose either one (or neither) for the predicate annotations. I really believe the static subtyping warnings are important, as they statically point out misunderstandings in the threading discipline.

I also need to provide a way to set timeouts for Concutest-JUnit and to relax the threads that have to have died by the end of the test. In some (many?) cases, my current checks are too stringent.

@Combine-style annotations now also work using reflection. That means the process of processing the class files is a lot less costly (in one example 16.5 seconds for reflection and 26.1 seconds for my original approach of rewritten bytecode), but the runtime performance might be degraded due to the use of reflection. However, at least so far I don’t see this degradation: With reflection one particular test takes 1.5 seconds, and with rewritten bytecode it takes 1.4 seconds. The reflection-based code was also a lot easier to write and offers better diagnostics, so maybe I was wrong about how heavy reflection really is. I’ll still need to run more tests that last longer, though.

I corrected a bug in the source code and uncorrected a bug in my mind (see last post). Then I write a lot more code that allows me to treat @PredicateLink– and @Combine-style annotations using reflection. Some things are actually REALLY nice: If I want to print out the annotation class and all the member-value pairs, I simply call the annotations’s ToString method.

It looks like it can now do @PredicateLink-style annotations. The strategy, however, is a lot more limited than the one I am using with bytecode rewriting. When rewriting bytecode, I have both the names of the name and types of the parameters in the predicate method, but all I have here at runtime, using Java’s reflection API, is two lists of types. As soon as one type does not match the type in the other list, I give up and tell the programmer how to change the annotation or predicate method.

That stuff seems to work now. May the Sugar Plum Fairy take me back to my bed across the Lemonade Sea now.

I’ve been wanting to write a reflection-based Thread Checker for a while already, mainly because I think many people will ask me: “Java provides a reflection API. Why didn’t you use it? It’s so much simpler than rewriting bytecode!”

I originally concurred that it would be easier to write, but I still think it will not perform as well as rewritten bytecode. But the proof is in the pudding, of course, as they say, so I had to write this reflection-based version. I’ve been laboring on this now for most of today, and I did start already a few days back, and it turns out to be pretty hard. It’s not trivial to find out where a method was first introduced. I’ve decided to follow the general outline of what I did with the bytecode-rewriting strategy.

I think I should have the code for the @PredicateLink-style annotations now, even though it is much more limited than the code I wrote for rewriting class files: Here, the parameters in the predicate method have to have the same order as the members of the annotation, and that order seems to be undefined. Yes. One of my favorite words. I also haven’t tested the reflection-based code for @PredicateLink-style annotations yet.

The code for @Combine-style annotations should actually be easier and faster than the rewritten bytecode (or at least faster than the first run, when the rewriting happens; I predict caching of the rewritten class files will again kill reflection on subsequent runs).

I fixed a bug that dealt with determining if class-level annotations should apply to a method. It was rather confusing. If a method was already introduced in an interface, then a class-level annotation on the class that implements that interface should not have any effect, but I did something wrong here.

This has cast some doubt on what I’ve been doing with class-level annotations in general, because when I ask for class-level annotations, I still recur into the superclasses and implemented interfaces, and right now, I don’t think I should be doing that. I’ll examine that closer tonight or tomorrow. (Update: No, what I was doing is right. If a class has an annotation, then all methods introduced in that class or in subclasses get the annotation; therefore, recurring up makes sense.)

Right now, Diana and I are going to the Houston Ballet to see “Nutcracker”. Even though I hate to admit it, I guess the Christmas season actually does begin on the day after Thanksgiving. Why would we watch “Nutcracker” otherwise? ;-)

I rewrote a few parts of the Thread Checker, mainly in the areas that instrument classes on-the-fly and in the strategy for automatically generating predicate methods for @Combine-style annotations.

Now making backups and saving annotated class files works as expected. I also require a directory to be on the classpath, but only if @Combine-style annotations are used. The caching works very well if the classes involved in rewriting are all regular files and not in jar files: Running the TCSample4 test the first time with on-the-fly instrumentation takes about 33 seconds, the second time it doesn’t even take 2 seconds.

Unfortunately, when the files are in a jar file, caching the rewritten class files is not very effective: The first run takes about 31 seconds, and the second still 30 seconds. The problem obviously is that generating the code isn’t the expensive part, but examining the class files to figure out what code to generate or check if it has already been generated.

I could write some kind of caching for jar files or write out the information obtained into some kind of file, and then on the second run first consult that file, in the hopes of being able to skip the expensive examination phase, but it just doesn’t seem like that is so essential to the project. There are other, more important things to figure out, so my suggestion right now is just this: Keep the files that are involved in rewriting outside of jars.

Yesterday, I made the first version of the Thread Checker available on the Concutest website. It is just one jar file, tcrt.jar, that contains both the classes for the annotations and the classes for rewriting class files (on-the-fly and offline) to check the invariants. I think in the future, I will separate this into two archives in order to keep the jar file with the annotations, the one that will have to be linked with user programs, as small as possible.

I also didn’t post any instructions yet. There are many examples available in this blog (e.g. here, here, here, here, here, and here), but no description on how to invoke the Thread Checker for on-the-fly instrumentation or how to rewrite the class files offline. I still have to do that.

I also realized that I need to check how the features of making backups, saving the instrumented version of a class, and writing auto-generated class files for @Combine-style annotations behave when the source class file is in a jar file. I think for the first two, backups and writing to disk, I will simply not perform these tasks if the class came from a jar file. I don’t want to rewrite the entire jar file; if caching or backups are important, then the jar file should be instrumented offline.

The auto-generated class files are more difficult to handle: I think I will have to stipulate that there needs to be at least one directory on the class path, and auto-generated class files will be placed there unless some other directory is specified. Another, perhaps better, possibility would be to try to load the automatically generated class files immediately from a byte array instead of first writing it to disk. That would allow classpaths that do not have any directories in them, but of course, it also disables caching.

I also need to continue the work on the reflection-based predicate Thread Checker. My intuition tells me that it will in general be slower than the thread checks done by rewriting bytecode, but the delay of auto-generating the class files may go away. I definitely need to have this as a comparison.

I’ve thought about my problem from the last post a bit, and I have decided that the current situation actually isn’t so bad. I went with an approach that’s similar to the 2nd option that I have described, but a bit more permissive.

The class containing a predicate method should be public if it is a top-level class, and public static if it is a nested class. If it is a nested class, then all of its enclosing classes must also fulfill these criteria. This makes a method accessible from any static context, anywhere. However, when a violation is detected, I only issue a detailed warning. I opted for a warning instead of aborting the instrumentation process because in many cases, the programs still work for some reason if the instrumentation is done offline. Only in on-the-fly instrumentation are these warnings important.

I have now implemented the code for issuing these warnings and have also created a simpler TCRun class that makes it very easy for the user to run programs with on-the-fly Thread Checker instrumentation.

Now I should do some more tests with @Combine-style annotations, and then I need to package the Thread Checker conveniently, write documentation and release it. Yay!

Update

Another thing I should do is check if classes have already been auto-generated during previous on-the-fly runs. The auto-generation for @Combine-style annotations can take a while, so it would be highly desirable to reuse already existing classes.

After some experimentation, I have realized that while I can access all the classes in any package, regardless of whether they are private or package-private using reflection, I cannot do that using regular calls. There doesn’t seem to be a central feature that disables that check all together.

Now, I wanted to write a purely reflection-based checker anyway, but I also wanted to get the bytecode-based version to work. Now I have to think hard what to do. One option, of course, would be to detect the use of a predicate method that cannot be called from the call site. Whether that is possible or not can only be found out once I examine the call site, so in the case of on-the-fly instrumentation, that would boil down to an exception, just like now.

A second approach would be to stipulate that the predicate method must be in a class that’s accessible from anywhere, i.e. either in a public top-level class, or in a public static nested class. The classes containing the predicates cannot be private, protected, package-private or non-static inner classes. Assuming this stance would allow me to do a robust analysis at the time I’m checking the annotations, and I can reject annotations that might lead to problems at call sites later.

The third and most complicated way is to add relay methods in a place that has access to and can call the original predicate method that should be called. These relay methods must then satisfy the criteria from the second approach. Where exactly I would put these methods, I don’t know… I think I’ll try to sleep over it, even though I just got up again at 2 AM to work on this…