A Concurrent Affair

Ok, I guess that was my sleep tonight.

I discovered that instrumenting rt.jar for thread checking is actually blowing the default-sized heap, so I quickly wrote a SoftHashMap that uses SoftReferences the garbage collector is free to evict.

I also did some analysis on the caching of class and method annotations:

ThreadChecker Cache Info:
Class cache 85499/13225, method cache 24748/111845 (hits/misses)

That means it definitely works, there’s no error. It works very well for classes (86%), probably because it is looking for the same classes very often (Object, d’uh), but it’s working pretty badly for methods (18%).

I don’t know off hand how I can improve the latter. I could perhaps scan all methods when I have a class file open. I think I’ll look at my second suggestion, temporary directories, first, though.

Here are my current Java API annotations, both in XML form:

and in a more human-readable form after being processed by the XMLAnnotToText tool:

class javax.swing.plaf.TextUI {

	@OnlyRunBy(@ThreadDesc(eventthread="true"))
	java.awt.Rectangle modelToView(javax.swing.text.JTextComponent a, int b);

	@OnlyRunBy(@ThreadDesc(eventthread="true"))
	java.awt.Rectangle modelToView(javax.swing.text.JTextComponent a, int b,
	   javax.swing.text.Position$Bias c);
}

class javax.swing.text.DefaultCaret {

	@OnlyRunBy(@ThreadDesc(eventthread="true"))
	void repaintNewCaret();

	@OnlyRunBy(@ThreadDesc(eventthread=".*"))
	void repaint();
}

class javax.swing.text.JTextComponent {

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void replaceSelection(java.lang.String a);

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void setText(java.lang.String a);
}

class javax.swing.text.Document {

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void render(java.lang.Runnable a);
}

class javax.swing.text.PlainDocument {

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void insertString(int a, java.lang.String b, javax.swing.text.AttributeSet c);
}

class javax.swing.text.DefaultStyledDocument {

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void insert(int a, javax.swing.text.DefaultStyledDocument$ElementSpec[] b);

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void setLogicalStyle(int a, javax.swing.text.Style b);

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void setCharacterAttributes(int a, int b, javax.swing.text.AttributeSet c, boolean d);

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void setParagraphAttributes(int a, int b, javax.swing.text.AttributeSet c, boolean d);
}

class javax.swing.text.StyleContext {

	@OnlyRunBy(@ThreadDesc(name=".*"))
	javax.swing.text.AttributeSet addAttribute(javax.swing.text.AttributeSet a,
	  java.lang.Object b, java.langObject c);

	@OnlyRunBy(@ThreadDesc(name=".*"))
	javax.swing.text.AttributeSet addAttributes(javax.swing.text.AttributeSet a,
	  javax.swing.text.AttributeSet b);

	@OnlyRunBy(@ThreadDesc(name=".*"))
	javax.swing.text.AttributeSet removeAttribute(javax.swing.text.AttributeSet a,
	  java.lang.Object b);

	@OnlyRunBy(@ThreadDesc(name=".*"))
	javax.swing.text.AttributeSet removeAttributes(javax.swing.text.AttributeSet a,
	  java.util.Enumeration b);

	@OnlyRunBy(@ThreadDesc(name=".*"))
	javax.swing.text.AttributeSet removeAttributes(javax.swing.text.AttributeSet a,
	  javax.swing.text.AttributeSet b);

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void reclaim(javax.swing.text.AttributeSet a);
}

class javax.swing.text.html.HTMLEditorKit$Parser {

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void parse(java.io.Reader a, javax.swing.text.html.HTMLEditorKit$
	  ParserCallback b, boolean c);
}

class javax.swing.undo.UndoManager {

	@OnlyRunBy(@ThreadDesc(name=".*"))
	boolean addEdit(javax.swing.undo.UndoableEdit a);

	@OnlyRunBy(@ThreadDesc(name=".*"))
	boolean canRedo();

	@OnlyRunBy(@ThreadDesc(name=".*"))
	boolean canUndo();

	@OnlyRunBy(@ThreadDesc(name=".*"))
	boolean canUndoOrRedo();

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void discardAllEdits();

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void end();

	@OnlyRunBy(@ThreadDesc(name=".*"))
	int getLimit();

	@OnlyRunBy(@ThreadDesc(name=".*"))
	java.lang.String getRedoPresentationName();

	@OnlyRunBy(@ThreadDesc(name=".*"))
	java.lang.String getUndoPresentationName();

	@OnlyRunBy(@ThreadDesc(name=".*"))
	java.lang.String getUndoOrRedoPresentationName();

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void redo();

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void setLimit(int a);

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void undo();

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void undoOrRedo();
}

class javax.swing.JComponent {

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void revalidate();
}

class javax.swing.JTextArea {

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void append(java.lang.String a);

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void insert(java.lang.String a, int b);

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void replaceRange(java.lang.String a, int b, int c);
}

class javax.swing.JTextPane {

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void insertComponent(java.awt.Component a);

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void insertIcon(javax.swing.Icon a);

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void setLogicalStyle(javax.swing.text.Style a);

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void setCharacterAttributes(javax.swing.text.AttributeSet a, boolean b);

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void setParagraphAttributes(javax.swing.text.AttributeSet a, boolean b);
}

class java.awt.Component {

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void repaint();

	@OnlyRunBy(@ThreadDesc(name=".*"))
	void invalidate();
}

I spent a few hours going over the list of methods that were supposedly thread-safe and also searched through the API source. I now have an XML annotation file that describes the methods that are supposedly safe to run by any thread.

When I was done with creating that XML file by hand, I looked at it and realized that — without some graphical tool — it was pretty hard to get a quick overview of what classes and methods were affected. The XML format is easy to create, read, and use in the program, but the packages are nested, so it’s hard to consider classes in isolation.

I decided to write a tool that converts an XML annotation file (which I can automatically create from annotated class files, as mentioned before) to a more human-readable format, something like an abbreviated, abstract Java file.

While doing that I realized that my XML file format was ambiguous. If you recall, my file format used to look like this:

It was “concutest/threadcheck” followed by packages, then the class name, and then <class> and <method> tags. There’s no way that a <class> tag could be mistaken for a package or a class name, since class is a keyword; but method isn’t! So it’s not immediately clear if a <method> tag describes a package or class or indeed a method.

I changed the format and put the <method> tags inside the <class> tag. That means now there is a <class> tag even if there aren’t any class-level annotations if there are annotated methods.

The XML annotations above now look like this:

I had to change all the strategies and the XML annotation files that I had already written, of course.

Now that I have created a list of methods that are safe to be run by any thread, I can start on marking many, many classes and methods as unsafe for execution outside the event thread. That should hopefully make things with DrJava more interesting. So far, I discovered nothing serious, even though I haven’t run the unit tests yet. If I don’t find anything, that’s great, it means DrJava is a solid piece of software. But it would be nice to demonstrate my tools on some buggy programs too…

I slightly extended the strategy that adds the thread checks: It’s now able to handle an arbitrary number of XML annotation files. That way I can keep the annotations for the Java API separate from anything else. The instrumentation is running now, and it’s taking a while. I’ve noticed that already when I was instrumenting the drjava-15.jar file. The frequent checks for superclasses and interfaces seem to get very slow whenever jar files are involved.

There are two things that I need to check:

1. Is caching of class and method annotations working? What kinds of hit and miss rates am I getting?
2. Should I unpack jar files into a temporary directory, work with them as loose class files there, and then pack them back together at the end? That could potentially speed processing up a lot, if the space is available.

This was a productive night of work, now it’s Labor Day and I should work on sleeping for a bit.

Annotating a method with @OnlyRunBy(@ThreadDesc(name=".*")) works to override all other, more narrow annotations and allow all threads to run, as expected. It looks pretty cumbersome, though, and doesn’t allow me to generate adequate warnings.

I think I should introduce a @OnlyRunBy(@ThreadDesc(anyThread=true)) annotation. If such an annotation is found, then the entire @OnlyRunBy can be removed, but warnings should be emited that a superclass annotation overrides subclass annotations: It’s a just another subtyping violation.

Actually… I guess it’s the same as having no annotation at all. So in principle I could just not annotate these methods. It may still be easier to annotate an entire class as @OnlyRunBy(@ThreadDesc(eventThread=true)) and then have @OnlyRunBy(@ThreadDesc(anyThread=true)) annotations for a few methods.

I need to think about this for a while…

I’m getting more and more the feeling that annotating the Java API side, primarily Swing, will be more important and hopefully produce more results than just annotating the DrJava side. I’ve collected a small number of methods alreaydy by grepping the Java API source, but picking the methods this way is extremely cumbersome, both because it requires reading a lot of code and because writing the method signatures by hand actually isn’t all that easy:

I think I may after all write a GUI tool, a class file browser, that scans the classpath and then allows you to click your way through the packages, classes and methods and attach annotations. I had that idea before, but I just didn’t get to it and then thought maybe it wasn’t necessary.

I’ve also browsed the web and tried to find references for what is and what isn’t allowed with Swing. It’s sad that there isn’t too much that really seems authorative, and the comments in the API source are more than sparse either. Here’s what I’ve found, in no particular order, sometimes with quotes, emphasis by me:

• Threads and Swing
  

  Once a Swing component has been realized, all code that might affect or depend on the state of that component should be executed in the event-dispatching thread.

  The single-thread rule: Realized means that the component’s paint() method has been or might be called. A Swing component that’s a top-level window is realized by having one of these methods invoked on it: setVisible(true), show(), or (this might surprise you) pack(). Once a window is realized, all components that it contains are realized. Another way to realize a component is to add it to a container that’s already realized.

  Comment: I guess that means I could add a flag or poll some methods when I’m doing the @OnlyRunBy(@ThreadDesc(eventThread=true)) check. But as explained farther below, Sun now recommends doing all GUI construction in the event thread using invokeAndWait.

  Exceptions to the rule: A few methods are thread-safe: In the Swing API documentation, thread-safe methods are marked with this text: This method is thread safe, although most Swing methods are not.

  Comment: I’ll have to grep for that. I tried, but it’s not spelled the same way in all instances. Anyway, these methods will probably be pretty rare.

  An application’s GUI can often be constructed and shown in the main thread.

  Comment: Again, Sun now recommends doing all GUI construction in the event thread using invokeAndWait, so I guess this is out-dated.

  The following JComponent methods are safe to call from any thread: repaint(), revalidate(), and invalidate(). The repaint() and revalidate() methods queue requests for the event-dispatching thread to call paint() and validate(), respectively. The invalidate() method just marks a component and all of its direct ancestors as requiring validation.

  Listener lists can be modified from any thread: It’s always safe to call the addListenerTypeListener() and removeListenerTypeListener() methods. The add/remove operations have no effect on an event dispatch that’s under way.

  Comment: Nice. I have to test it, but I should be able to annotate these methods with @OnlyRunBy(@ThreadDesc(name=".*")) and therefore allow all threads to call them. It should override more restrictive annotations. Other articles mention a few more methods.

• The Last Word in Swing Threads
  

  Swing’s single-thread rule says that Swing components can only be accessed by a single thread. This rule applies to both gets and sets, and the single thread is known as the event-dispatch thread.

  Comment: Gets for some primitive data might actually be safe, but for references it’s definitely unsafe.

  Swing components will generally not comply with the single-thread rule unless all their events are sent and received on the event-dispatch thread. For example, property-change events should be sent on the event-dispatch thread, and model-change events should be received on the event-dispatch thread.

  For model-based components such as JTable and JTree, the single-thread rule implies that the model itself can only be accessed by the event-dispatch thread.

  Comment: Somehow I thought that model code could be accessed outside the event thread. It’s good to know that this is not the case. I wonder where that will draw the boundary in DrJava.

• Painting in AWT and Swing
  

  It is not recommended that programs invoke paint() directly.

  Programs should not invoke this method [paintImmediately()] directly unless there is a valid need for real-time painting.

  Comment: That implies they should only be run by the event thread.

  The program invokes repaint() on the component, which registers an asynchronous request to the AWT that this component needs to be repainted. The AWT causes the event dispatching thread to invoke update() on the component. NOTE: If multiple calls to repaint() occur on a component before the initial repaint request is processed, the multiple requests may be collapsed into a single call to update().

  Comment: That explains why repaint(), etc. is safe.

• Concurrency In Swing Text
  

  The primary form of concurrency support in the text package is designed to support building and maintenance (also called mutations) of the document model on a separate thread from the event dispatching thread. A concurrent application will typically interact with the model and have no direct interest in the GUI.

  Comment: So the models of text components can be accessed from outside the event thread, but those of JTable and JTree can’t? I’ll have to check that more closely, but I guess this was what I remembered.

  The most time-consuming part of laying out a large box is calculating preferred sizes for the children, and then waiting for the actual layout that the children perform. If these two operations are performed synchronously, it may even turn out that a lot of this work is useless.

  Comment: It seems like text components use additional “layout threads”. May they access methods that can only be run by the event thread?

• Swing : Java Glossary
  

  There are a few exceptions to the general rule of having to invoke Swing methods from the EventDispatchThread, most notably it is safe to call to the following methods from any thread:
  Component.repaint
JComponent.revalidate
JEditorPane.replaceSelection
JTextArea.append
JTextArea.insert
JTextArea.replaceRange
JTextComponent.replaceSelection
JTextComponent.setText
JTextPane.insertIcon
JTextPane.insertLogicalStyle
JTextPane.setCharacterAttributes
JTextPane.setParagraphAttributes
PlainDocument.setText

  Comment: I need to check that these are actually correct. Also, Component.invalidate was missing from this list.

• How to Use Threads
  

  We used to say that you could create the GUI on the main thread as long as you didn’t modify components that had already been realized. […] To avoid the possibility of thread problems, we recommend that you use invokeLater to create the GUI on the event-dispatching thread for all new applications.

  Comment: That means I will not write a special case for access to event thread-only methods if the components haven’t been realized yet.

• Multithreaded Swing Applications
  

  If you modify Swing component data from any thread other than the event dispatching thread, you must take precautions to ensure data integrity. An exception to this rule is the setText method on a JTextComponent or any of its subclasses, or any Swing component method whose documentation explicitly states it is thread safe.

  Comment: Interesting… Have to check that and may mark them as @OnlyRunBy(@ThreadDesc(name=".*")).

As a summary, I can probably say that most of Swing should be event thread-only, except for the few methods mentioned in the list below. Text models may be ok to be called from outside the event thread, but JTable and JTree models are not. And Sun has made my life a little bit easier by retracting their statement that a GUI can be constructed in the main thread as long as it hasn’t been realized.

Component.repaint
Container.invalidate
JComponent.revalidate
JEditorPane.replaceSelection
JTextArea.append
JTextArea.insert
JTextArea.replaceRange
JTextComponent.replaceSelection
JTextComponent.setText
JTextPane.insertComponent
JTextPane.insertIcon
JTextPane.setLogicalStyle
JTextPane.setCharacterAttributes
JTextPane.setParagraphAttributes
DefaultStyledDocument.setLogicalStyle
PlainDocument.setText

The comments for DefaultMutableTreeNode indeed say it’s not thread-safe. However, this does not really mean that it should only be accessed by the event thread; there just has to be additional synchronization in place. Can I check for that — without using full-scale Eraser? Should I force access from within the event thread?

* This is not a thread safe class.If you intend to use
* a DefaultMutableTreeNode (or a tree of TreeNodes) in more than one thread, you
* need to do your own synchronizing. A good convention to adopt is
* synchronizing on the root node of a tree.

Many methods on the text model side do state they are thread-safe. Some inner classes in javax.swing.text.html.StyleSheet, however, explicitly state they are not thread-safe. Again, the above applies: Running outside the event-thread is ok, as long as there is additional synchronization.

I’m wondering whether I should warn about unnecessary annotations, e.g. if a method is annotated, but the supermethod is, too. It’s not strictly necessary, but it may be a good idea for clarity and conciseness. Then again, it’s additional documentation.

I’m also thinking that perhaps I should do some static checking when certain thread properties are known for a method. The main method could, for example, be annotated with @RunsThread(@ThreadDesc(name="main", group="main", id=1, eventThread=false)). Other threads could run it too, but this is definitely one possibility. When a call is made to a method annotated with @NotRunBy that matches this description or @OnlyRunBy that doesn’t match this description, a static error could be generated.

There are several cases when you either cannot put annotations in the source code to make the thread checker work: Either you decide you do not want to pollute the source with the annotations (even though I see them more as enhanced documentation), or you do not have the source to begin with. The latter is sort of the case with the Java Standard API. The source is there, but I do not want to recompile it.

For these cases, I have developed an XML format that allows the developer to specify the threads allowed or not allowed to run certain methods or classes in an external file. It’s based on the XML configuration library that I wrote a while ago. Consider the file below:

This XML file expresses the same checks as the annotations in the Java file here:

...
@OnlyRunBy(@ThreadDesc(name="childclass1"),
@ThreadDesc(group="childclassgroup1"),
@ThreadDesc(id=1001),
@ThreadDesc(eventThread=true))
@NotRunBy(@ThreadDesc(name="childclass2"),
@ThreadDesc(group="childclassgroup2"),
@ThreadDesc(id=1002))
public class ThreadCheckSample4 ... {

@OnlyRunBy(@ThreadDesc(name="childclass-method1"))
@NotRunBy(@ThreadDesc(name="childclass-method2"))
public void run() { ... }
}

The rationale for this design was the paths I use to access nodes in the XML. The path to get to the <ThreadCheckSample4> node, for example, is concutest.threadcheck.sample.threadCheck.ThreadCheckSample4, so if you ignore the initial concutest.threadcheck, which designates the project and sub-project, then that’s exactly the fully-qualified class name, so look-up is trivial.

Then there is a <class> tag that can contain any number of nested <name>, <group>, <id> and <eventThread> tags that correspond to the @ThreadDesc annotations. A type attribute chooses between @OnlyRunBy and @NotRunBy, and a value attribute actually contains the thread description.

For methods, there can be any number of <method> nodes. Which method they describe is chosen by the sig attribute that contains a concatenated method name and descriptor. The rest is the same as for the <class> node.

What I need now is an easy way to generate these XML files, perhaps by using some sort of class/jar file browser, and generally an easier way to perform the instrumentation so I can release the thread checker independently from the rest of the framework.

Now that I have a list of methods that are deemed save, I can start marking many, many classes and methods as unsafe to be executed outside the event thread. That’s when things will actually get interesting. And I also need to run the DrJava unit test suite. In normal operation and without Swing annotated, I didn’t find a serious problem in DrJava yet. That’s good, of course. It may stay that way. But it would also be kind of nice to show my tools on buggy programs…

I’ve extended the strategy that adds thread checks a little: It can now handle an arbitrary number of XML annotation files, separated by the "path.separator". That way I can create a dedicated file just for the Java runtime.

The instrumentation is running now and I’m taking a blogging break, and it’s taking a while… I noticed that when instrumenting the drjava-15.jar file already. It seems like the frequent queries for superclasses and superinterfaces take a long time whenever jar files are involved.

So there are two things that I need to check:

1. Does caching of class and method annotations work? What kind of cache efficiency am I getting?
2. Should I create a temporary directory, unpack a jar file, work with loose class files, then pack them up again and delete the directory?

This was a good night’s work on the eve of labor day, but I should seriously work on sleeping soon.

I must admit I haven’t been able to do as much as I had hoped during the last two days, but I did experiment with a new, more flexible format for the annotations. It’s a bit more verbose, but it essentially gives me what I had wanted (see end of this posting).

The preferred (and most future-proof) way of specifying threads now uses the value element, an array of @ThreadDesc annotations. The choice of value as name has the advantage that the programmer can drop the value= part if only the value element is assigned to. The @ThreadDesc annotation now contains the four elements name, id, group and eventThread (notice singular form on the first three), but only one of the four may be used at the same time, i.e. @ThreadDesc(name="foo") and @ThreadDesc(id=5) are legal, but @ThreadDesc(name="foo",id=5) is not.

The old elements of @NotRunBy and @OnlyRunBy, i.e. threadNames, threadIds, threadGroups and eventThread are still available and can be mixed with the new value element in any way, as long as anything regarding the event thread is not specified more than once, like in the following (illegal) annotation: @OnlyRunBy(eventThread=true, value=@ThreadDesc(eventThread=true)).

Here are some examples of the new style:

@NotRunBy({@ThreadDesc(name="bar"), @ThreadDesc(id=1)})
@NotRunBy({@ThreadDesc(name="main"), @ThreadDesc(name="fum")})
@OnlyRunBy(@ThreadDesc(eventThread=true))
@OnlyRunBy(value={@ThreadDesc(name="main3"), @ThreadDesc(group="foo")},
threadGroups={"bar"}, threadIds={3, 4})

The major advantage is that I can add additional elements to the @ThreadDesc annotation, such as conditionals as discussed previously.

I also changed the way class-level annotations affect methods and floowed Corky’s advice: An annotation on a class, from now on only influences methods that were defined by that class, or are going to be defined in subclasses. Let’s look at a quick example:

abstract class Base {
@OnlyRunBy(eventThread=true)
public abstract void run();
public abstract void doSomething();
}
public boolean equals(Object other) { ... }

In this class only the run method is annotated (and all methods in subclasses); >doSomething is not annotated.

Let’s look at a subclass:

@OnlyRunBy(eventThread=true)
class Sub extends Base {
public void run() { ... }
public void doSomething() { ... }
public abstract void doSomethingElse() { ... }
}

Here, we have a class-level annotation: In my initial version, this annotation would have applied to all three methods in the Sub class; however, that caused a lot of warnings if subtyping was taken seriously. Now the annotation only applies to the doSomethingElse method, because both run and doSomething were already defined in the Base class. The Sub.run method nonetheless is annotated to allow only the event thread to run since Base.run is annotated with @OnlyRunBy(eventThread=true) and that applies to all subclasses as well.

I mentioned earlier that the checker currently generates a lot of warnings, many of which seem unnecessary. When I change the checker to match Corky’s suggestion, that will reduce the number of warnings, but there could potentially still be a lot.

I do filter out multiple warnings that are exactly the same, and I also remove warnings that concern an individual method if the entire class is affected. For efficiency reasons, I also don’t match a thread name or group name against the same regular expression twice. What I don’t do, and I guess that deserves to be mentioned, is see if matching a thread name or group name against a particular regular expression R1 is unnecessary because the language accepted by R1 is already a subset of the language accepted by a second regular expression R2.

While determining whether the language of one regular expression is the subset of another is decidable, I don’t think this is necessary here. I don’t think Java’s builtin java.util.regex package can do minimization or compare regular expressions somehow. It’s theoretically interesting but practically probably rather irrelevant.

Thinking about this got me wondering whether creating one long regular expression for all the @OnlyRunBy thread names or group names is more efficient than what I do right now. If I have the annotation @OnlyRunBy(threadNames={"foo","bar"}), I could just match the thread name against the regular expression "(foo)|(bar)"… I have a feeling that’s better. I’m gonna try that now.

Update

No, using one single long regular expression apparently is not good. I ran the following method 1,000,000 times with the old system (preparing a list of regexes with a call per pattern, then checking it with another call) and the new system (statically preparing one long regex, then making one call to check it):

@OnlyRunBy(threadNames={"main","main2","main3","main4","main5"})
public static void allowed() {
}

The new system with the more complex regex was on average about five times slower.

Good, I didn’t oversleep again. I just talked to Corky about the dynamic thread checker again. Here’s what he suggested:

• Annotations at class level, e.g. @OnlyRunBy(...) class Foo { ... } should not apply to all the methods in the class, but only to those methods that are introduced by the class or by one of its subclasses. That would probably avoid a lot of the warnings that I’m generating right now, and if you really want to annotate a method somewhere where it was not introduced, you can still do that using a method annotation.
• Certain AWT/Swing methods are always safe, e.g. java.awt.Component.repaint. If I’m only using method annotations, then these methods just would not be annotated, but if I’m using class annotations, then I may have to have a method annotation that overrides the class annotation. I think I’ll ignore this for now.
• AWT/Swing components are probably safe as long as they or any of their subcomponents aren’t “live” yet. He mentioned that methods such as setVisible and pack make an object “live”, but I have to find a more accurate description. Another question is how do I determine that a component is still safe? Do I add a special element to the annotations, e.g. @OnlyRunBy(eventThread=true, AWTsafe=true), or do I go for more general conditions, like @OnlyRunBy(eventThread=true, condition="!isVisible()"). The latter would, of course, be much more difficult, so at least initially I’m opting for the former. But how do I implement that? Do I add a flag to the class and then set it in one of the methods that make an object “live”?
  

  Update: Actually, Sun doesn’t recommend this practice anymore. I found that out while searching the web for texts on Swing and concurrency. So maybe I can save myself the effort. I’ll have to talk to Corky and find out if he really wants this.

• Even on the view side of AWT/Swing, many objects are probably safe, as long as what they’re doing is volatile, i.e. other threads get to see the effects immediately, and as long as they don’t export an object with mutable state. How do I determine that? Well, I don’t know…

Corky really stressed that we should avoid generating many false positives. That’s what he disliked about the static tools that exist, like FindBugs. After writing more unit tests for the instrumentation strategy I’ll start with annotating DrJava’s codebase and from there work my way into the Java API if I have to.

I think I may want a more flexible format of annotations, though. It’s a little problematic that I cannot use the same annotation class on a class or method twice. I would just like the following format much better:

@OnlyRunBy(eventThread=true)
@OnlyRunBy(threadName="helper")
...

If I can specify each allowed or disallowed thread one by one, then it’s much easier to modify just one of them, e.g. by somehow making it conditional:

// running by event thread is always safe
@OnlyRunBy(eventThread=true)
// running by "helper" is safe as long as not "live"
@OnlyRunBy(threadName="helper" AWTsafe=true) ...

Maybe I’ll have to rethink my annotation format…

Today was pretty much a repeat from yesterday: I fixed (or at least worked on) another DrJava bug and made improvements to my dynamic thread checker. Unfortunately, the bug fix did not make it into our new new stable release anymore. I also couldn’t reproduce the “Unsupported major.minor version” error, but that may even be a good thing.

I was a little bit late to our research meeting, but when I talked about the thread checker, Corky agreed that annotations on superclasses or methods in superclasses should be considered in subclasses as well. He also said I could go ahead and use DrJava as test codebase. We didn’t talk very much, but when I mentioned the warnings that should be raised when a subclass has an annotation but a superclass does not, he suggested that perhaps an annotation should only be allowed where a method is first introduced, and not in a subclass or implementing class.

We both agreed that this might not be practical, though: Often programmers implement Standard Java API interfaces, like ActionListener, and then they would not be able to annotate those implementing classes.

I still need to do a little more testing and write unit tests, but I did write the code tonight that checks superclasses and interfaces for annotations as well. The code for subtyping warnings is there too, but it generates a lot of warnings… More than may be useful. They currently look like this:

ThreadCheckTest has @NotRunBy thread name 'foo' but java.lang.Object does not
ThreadCheckTest3 has @OnlyRunBy thread name 'main2' but java.lang.Object does not
ThreadCheckTest4.run()V has @NotRunBy thread name 'childclass-method2' but ThreadCheckTest4SuperClass.run()V does not

I think I may want to exclude java.lang.Object from this. And perhaps even more.

This sort of brings up the topic of instrumenting library code. There are probably a lot of AWT/Swing methods that should only be executed by the event thread, for example, but how do I instrument them? The source has been released, but I don’t think I actually want to compile it.

So what I have in mind now is an external text or XML file that just contains location-annotation pairs so the programmer can tell the instrumentor to attach a @OnlyRunBy(eventThread=true) to java.swing.text.Document or a @NotRunBy(threadName="main") to java.lang.Runtime.exit(I)V.

I’m excited to see the thread checker grow and to apply it to DrJava. I may actually have some statistical and benchmarking data soon. All right, it’s nearly 5 AM again, and I think I should try to sleep (but not oversleep) again.

I found another kind of concurrency problem that can easily be caught using the random delays, and it’s a very common one: It’s an atomicity violation caused when the result of one synchronized method is used as input for another synchronized method, but the whole thing isn’t part of a synchronized block. The example the DrJava developers at Rice are most familiar with is the following:

public synchronized int getLength() { ... }
public synchronized void remove(int offs, int len) { ... }
...
remove(getLength()-1, 1);

The code is supposed to remove the last character of the document. Both methods are synchronized, the two calls are not atomic, i.e. the thread may get preempted after the call to getLength, another thread may change the document and its length, and then the original thread resumes with an incorrect length, removing either a character that’s not the last or accessing out of bounds.

If at least one method of such a two-call process is synchronized, then a delay will get inserted between the two methods, and that greatly increases the probability that preemption and corruption will occur and a unit test detects it. I’m in the process of writing a concise demonstration.

I also came up with an improvement of detecting “doomed waits” that I need to put in writing right now: Regardless of whether I decrement and increment the “running threads” (maybe “live threads” is a better name”) variable at monitorenter opcodes and use that to determine whether concurrency exists, I should keep a second “running threads” variable that does get decremented before a monitorenter and incremented after it.

This “running threads” variable is then only used to determine “doomed waits” and deadlocks: If a call to a wait is made, and only one user thread is running, regardless of how many are alive, then the wait is doomed and an exception is thrown. This situation could arise if the thread that should send the notification is involved in a deadlock.

There is a small problem, though: Unless I keep track of which locks a thread owns (strategy 3), the “running threads” variable will be decremented before a monitorenter even if the thread already owns that lock and thus does not get blocked. If the variable gets decremented, and then a task switch occurs to a thread that calls wait, then that wait could erroneously be declared as “doomed”.

The solution to this problem that I came up with while napping this morning after my all-nighter is this: Don’t immediately declare a “doomed wait“, but instead set a “progress made” flag to false and wait a few milliseconds. If a thread passes through its monitorenter — and therefore wasn’t blocked — it increments the “running threads” variable and sets the “progress made” flag to true. When the original thread resumes, it checks if the “progress made” flag is still false and only then declares the wait as “doomed”.

I need to get to campus now so I can perhaps discuss a few ideas with Corky.

I made a small change to my random delay code to improve how tests with “doomed waits” are being dealt with: Instead of just calling SyncPointBuffer.randomDelay, before a wait I now make a call to SyncPointBuffer.delayObjectWait. This method first checks if there’s only one user thread alive, and if that’s the case, throws an error. Here’s the output of such an execution:

$ ant run-delay -Dtest-class-name=SyncProblem3
Buildfile: build.xml

run-delay:
     [echo] Test name = SyncProblem3
     [java] .Main thread starting worker thread...
     [java] Main thread started worker thread...
     [java] Worker thread running
     [java] Main thread waits...
     [java] Worker thread calling notify
     [java] E
     [java] Time: 3.328
     [java] There was 1 error:
     [java] 1) testNotifyTooEarly(SyncProblem3)java.lang.AssertionError:
              Call to Object.wait with only one user thread alive (_runningThreads==3)
     [java]     at edu.rice.cs.cunit.SyncPointBuffer.delayObjectWait
                   (SyncPointBuffer.java:825)
     [java]     at SyncProblem3.testNotifyTooEarly
                   (SyncProblem3.java:42)
     [java]     at sun.reflect.NativeMethodAccessorImpl.invoke0
                   (Native Method)
     [java]     at sun.reflect.NativeMethodAccessorImpl.invoke
                   (NativeMethodAccessorImpl.java:39)
     [java]     at sun.reflect.DelegatingMethodAccessorImpl.invoke
                   (DelegatingMethodAccessorImpl.java:25)

     [java] FAILURES!!!
     [java] Tests run: 1,  Failures: 0,  Errors: 1


BUILD FAILED
R:\Concutest\ClassLoader\build.xml:722: Java returned: 1

Total time: 4 seconds

But like I’ve written in an update to an earlier post, my tests indicate that a wait without timeout should be broken down into a series of wait calls with timeouts and interspersed checks of the number of living threads. There is a chance that — because we’re dealing with concurrency here — the second-to-last thread has not died at the time the check is made, but then dies before wait is called.

To make this change, I have to write my own version of Object.wait and replace calls to it with calls to my own version. I’ve done that before already, so it shouldn’t be difficult.

I have to admit, though, that this situation has so far been hard to coerce with random delays, and even then it only works on a small scale: If there are several other threads running in the background, e.g. a GUI event thread, then the thread count will not drop sufficiently. For the GUI event thread, I can probably modify the minimum number, but if there are additional user threads alive, then the “doomed wait” will not be detected.

I’ve just finished the last instrumentor to delays to programs. That means my instrumentation is currently inserting delays before

• monitorenter
• Object.wait
• Object.notify
• Object.notifyAll
• Thread.join
• Thread.exit

and delays after

• monitorenter
• monitorexit
• Object.wait
• Thread.join
• Thread.start
• Thread.run

After I added delays before and after calls to Object.wait, though, the test case with the early notification wasn’t hanging anymore. I think because now I have delays in all the important places, on average the delays often balance out and preserve the original order.

I think what I want to do is try to skew the schedule maximally in one way and then in the other, e.g. first put delays on wait but not on notify, then in another run do it the other way around.

The following of those relationships come to mind:

• Object.wait vs. Object.notify, Object.notifyAll
• Thread.run vs. Thread.join
• Thread.run vs. Thread.start
• Thread.exit vs. Thread.start

There are many combinations here, especially since some of these sync points may have delays before and after them. I definitely need to investigate the relationships more closely… when I’m more awake.

Update

Another idea instead of random delays are calls to Thread.yield that occur randomly.

The first problem that execution with random delays can catch is a temporal dependency: Thread 1 expects that thread 2 has finished performing a task, but this is not enforced through synchronization.

My girlfriend asked if I could detect the exact opposite: What if thread 1 expects that thread 2 has not finished performing some task, but it actually has? This is probably another common problem, especially with novices. It gets particularly bad if it involves wait and notify, and one thread is waiting for another thread’s notification, but that notification was done before the first thread was ready for it. Here’s an example:

import junit.framework.TestCase;
/**
* A multithreaded test case exhibiting a problem with synchronization:
* One thread is waiting for another thread's notify, but that notify
* has already occurred.
* @author Mathias Ricken
*/
public class SyncProblem3 extends TestCase {
public void testNotifyTooEarly() {
final Character signal = new Character('x');
Thread worker = new Thread(new Runnable() {
public void run() {
System.out.println("Worker thread running");
try { Thread.sleep(2000); }
catch(InterruptedException e) { /* ignore */ }

try { Thread.sleep(3000); }
catch(InterruptedException e) { /* ignore */ }
System.out.println("Worker thread done");
}
});
System.out.println("Main thread starting worker thread...");
worker.start();
System.out.println("Main thread started worker thread...");
try {
synchronized(signal) {
System.out.println("Main thread waits...");
signal.wait();
System.out.println("Main thread woken up");
}
}
catch(InterruptedException e) { /* ignore */ }
System.out.println("Main thread done");
}
}

Here, the calls to Thread.sleep simulate performing some computation, of course. Under normal circumstances, the worker thread will call signal.notify() long after the main thread has reached signal.wait(), so the main thread gets woken up.

If, however, the main thread for some reason takes longer than usual to get to signal.wait(), then the notification may be lost. The correct way of doing this, of course, is to include a flag that’s protected by the lock of the same object that is being used for signaling: The flag is initially false, gets set to true before the call to notify, and wait is only called if the flag is still false.

...
public class SyncProblem3 extends TestCase {
boolean flag = false;
public void testNotifyTooEarly() {
...
Thread worker = new Thread(new Runnable() {
public void run() {
...
synchronized(signal) {
flag = true;
signal.notify();
}
...
}
});
...
try {
synchronized(signal) {
if (!flag) {
signal.wait();
}
}
}
...
}
}

Note that if the notify is reached first and the notification is lost, then this unit test does not fail but hangs. For this reason, any unit test should have a timeout set, and if the test has not finished executing after the specified time has run out, the test should be considered a failure. An examination of the thread stacks would then show that one of the threads had made a call to Object.wait.

There are probably more elegant ways of doing this. Two things come to my mind right now:

• The test could be run with a different version of Object.wait that includes a timeout. If the time is exceeded, it throws an exception, forcing the test to fail.

  The problem again is the choice of the timeout length. Some tests could potentially run for a very long time and then succeed, and that is the expected behavior.

  The most flexible thing to do is to set the timeout length in an annotation, the way JUnit 4.0 already does it:

  @Test(timeout = 60L) void testNotifyTooEarly() ...

• In some cases, it may be possible to detect that a thread cannot be woken up again, either because there are no other user threads left alive, or because there is a deadlock. The first case is easy to check just before the call to Object.notify (Update: My tests indicate that a wait without timeout should be broken down into a series of waits with timeouts and interspersed checks of the number of living threads); the second case would require the deadlock detector.

I’m confident I can provide a system that’s useful here, too. And I’m glad I have a smart girlfriend.