A Concurrent Affair

I’ve decided that this is too important to postpone, so I’m actually playing around with code. I’m trying to leverage as much of the code that is already there, though, so I’ve changed the format of the XML concurrency definition a bit:

I’m using the <threadcheck:def> node to designate a concurrency definition. It differs from <threadcheck> and other configuration file nodes, but makes it still apparent that these definitions are part of the Thread Checker. I guess I could have moved a lot more around, but this seems to be the easiest option to create mutually compatible and interchangeable XML files.

I think I’ll also name the annotation first, with the limitation that each definition can only have one annotation, and then list the methods and classes as individual tags, with their names stored in attributes.

I just contemplated one of the basic problems of concurrent programming: The “contours” of the concurrent program, the different threads, usually don’t conform to the “contours” of the object-oriented programming language. There may be one class, and a hierarchy underneath it, and a second class with its hierarchy, but threads can and often do cut completely across object-oriented boundaries. That’s why it’s so hard to separate things out and specify what should only be run in one thread.

My project can definitely help. However, I just realized that there might be a specialization of my work that can help even better: In addition to providing a class definition, like Java already does, and perhaps adding thread annotations to it, I can provide a concurrency definition that specifies what gets executed in what thread. It’s basically an inverted XML file that I have used so far.

The XML files so far were based on the packages and classes, just like class definitions. A concurrency definition would do it the other way around, it would be based on the invariants and list packages and classes.

Consider, for example, the following XML file from this post, which specifies simple invariants:

The concurrency definition as an XML file would look like this:

It merely lists all the invariants, and then the classes and methods that belong to it. That way, there should be a clear delineation between what is part of one thread (or rather: one invariant) and what isn’t. This would be in addition to the class definitions. Of course, internally, these XML files would be translated into the regular annotations.

I’m intrigued. The question now is whether I’m gonna interrupt my writing to program this.

I’ve finished entering the hand-written comments now — a total of 105, if I’m not mistaken — and am preparing to print them out again. Kind of ironic. But I think that’s the best way to remind me of them.

With the comments, I’m close to 110,000 words.

Over the last few days I’ve been pretty much floored with what seems to be a viral infection. I was at first worried that it might be bacterial when I noticed a change of color, but Dr. Jenkins disagreed, and told me to continue to do what I’ve done the last five days: Lay low, drink lots of fluids, take some Robotussin and some Mutrinex. Grrreat. By down I’m really sick of oozing from so many places.

I’ve taken the time to re-read my entire blog and mark things that are important or need clarification. Printed out in 12 point font font, my blog is 159 pages long and contains roughly 104,000 words. I find that rather satisfactory and surprising. When I went through it, I found many things that I had forgotten, but that were important to mention, but also many open leads.

Today I tried to digitize the comments, i.e. add them to the blog, but it’s taking it’s time. Maybe I should have done it that way right away, but last Saturday, when I did most of the work, I didn’t want to take a laptop with me when I was eating my strawberries at the cafe.

I think it’ll take another day to get the remaining comments into the blog. But I’m just having trouble staying up for too long, working, and doing my every-day-chores like cleaning, shopping, and laundry. At least the last two are done for now. I think now I’ll watch a movie and fall asleep.

Just like most of the ad-hoc dynamic tools I’m developing, the test to ensure “forced joins” does not guarantee that the test is actually correctly written: Threads can be spawned and the main thread does not join them again, but this goes undetected because every time the tests are run, the spawned threads coincidentally happened to terminate before the test ended. The test just catches a badly written test that does not join with spawned threads if this situation actually occurs.

How can I improve the framework’s ability to detect bad tests? How can I detect the lack of joins even if spawned threads always end before the test ends? I think I need to make the check bi-directional: In addition to making the main thread check if there are still spawned threads alive, spawned threads need to check that the main thread joined with them. The problem is that a spawned thread may die before the main thread reaches the join statement, which then just acts as a no-op, so I can’t perform this check at the time the thread dies, because it may be a premature indictment. Too bad, that would have been easy to do…

I guess I should change Thread.start so that it registers the thread in a list, change Thread.join to remove the thread from the list, and then check that the list is empty at the time the test ends. This, of course, doesn’t guarantee that all bad tests are spotted either: It could just coincidentally happen that in the schedule that is executed, the threads that don’t have a join statement aren’t started.

Another low-tech solution that’s not quite as thorough would be to delay thread death for a second or so, so it’s similar to the idea of inserting random delays at synchronization points. If a thread dies later than usual and there’s no join statement, it becomes more likely that the test ends before the thread is dead, and my current check would report the thread as still alive.

Without exhaustive static analysis or execution of all possible schedules, our original scheduled-replay approach, I can’t deterministically conclude that a test is actually successful and correctly written. I can only increase the likelihood that bad tests are caught.

I still believe doing this is worthwhile. The problem with both of these approaches is that I have to modify methods in the java.lang.Thread class. That’s easy for me to do, but it also means that the rt.jar file has to be changed (I may get away with just putting the changed Thread class file in a jar file and putting it at the front of the boot classpath, but there were some limitations to that; I’ll have to check if this is indeed possible), and Corky and I both wanted to limit the changes to JUnit to regular Java, without messing with the runtime. Since instrumenting the rt.jar file consumes both time and disk space, these improved “forced join” checks will probably be an optional enhancement.

I have now changed the versions 4.1 and 4.2 of Concutest-JUnit so that, in the case of a timeout, @After methods are executed before the check for spawned auxiliary threads is done. This now allows the JUnit’s own TimeoutTest to run smoothly.

This test is a testament to the confused state that unit testing of concurrent programs currently is in. The original TimeoutTest starts a test that enters an infinite loop and therefore violates the timeout constraint set. The test fails, TimeoutTest registers the failure, and therefore declares itself to have been passed successfully. This is good, because it demonstrates that time limits for tests work. But in the background, the test with the infinite loop continues to run… and run… and run… and it never finishes. It in fact prevents the Java VM from terminating. And that’s considered a success? It’s ironic that TimeoutTest itself is an example of a badly written concurrent unit test, one that spawns a thread and declares success before the spawned thread has ended.

I have now modified the test to include an @After method that sets a flag and therefore causes the (not-so-infinite-anymore) loop to exit. Without this, my Concutest-JUnit would have declared the test a failure because it concluded before all its spawned threads had died.

I’ve been working a bit more on Concutest-JUnit. Even though I thought I was done, when I ran the tests on different machines, I was still getting errors. Clearly, there were timing problems. I think I got to the root of the problem: Sometimes the main thread continued before the test thread had written the uncaught exception to a field, so success was assumed. I switched the architecture of the “old” style to wait/notify as well.

Then I noticed that in some cases, I was calling notify too early. I called it before I actually threw the exception, so the same problem described above could occur. I rearranged the code everywhere, both in the “old” style and the “new” style portions. I did some refactoring too to improve code reuse.

Now I’m running into another problem: In the “old” 3.8.2-style, where methods are prefixed with “test“, I run the tearDown method before I check if threads are still alive. This allows tearDown to end the “infinite” loop in TimeoutTest. In the “new” 4.0-style code, methods tagged with the @After annotation, the equivalents to tearDown methods, aren’t run until after the check is made if threads are still alive (or more precisely: it’s not guaranteed that they are run before), so an @After method is not always able to kill the “infinite” loop.

What’s the right behavior here? Unfortunately, I’m thinking that tearDown and @After methods are still part of the test, as they perform necessary clean-up. So I guess I’ll have to do some pretty complicated restructuring in the “new” style portion of the code. Or maybe I’ll postpone that for now and accept that there’s a difference in the way “old” and “new” tests behave.

I just quickly moved over the changes from my 4.0-based source to the JUnit 3.8.2 source. I found that, when being restricted to the Java 1.4 API, debugging information is a lot harder to get. I can’t find stack traces of the threads involved, for example.

When I ran the DrJava unit test suite with the modified version of JUnit 3.8.2, I got these results:

Testsuite: edu.rice.cs.drjava.model.GlobalModelJUnitTest
Tests run: 14, Failures: 1, Errors: 0, Time elapsed: 18.958 sec

Testcase: testJUnitAllWithErrors
(edu.rice.cs.drjava.model.GlobalModelJUnitTest):
FAILED
junit.framework.AssertionFailedError:
test case has one error reported expected:
<2> but was:<1>


Testsuite: edu.rice.cs.drjava.model.MultiThreadedTestCaseTest
Tests run: 1, Failures: 1, Errors: 0, Time elapsed: 0.011 sec

Testcase: testUncaught
(edu.rice.cs.drjava.model.MultiThreadedTestCaseTest):
FAILED
junit.framework.AssertionFailedError:
expected:<1> but was:<0>


Testsuite: edu.rice.cs.drjava.model.junit.JUnitErrorModelTest
Tests run: 4, Failures: 1, Errors: 1, Time elapsed: 6.293 sec

Testcase: testErrorsArrayInOrder
(edu.rice.cs.drjava.model.junit.JUnitErrorModelTest):
FAILED
junit.framework.AssertionFailedError:
the test results should have one error and one failure 1 expected:
<2> but was:<1>


Testcase: testVerifyErrorHandledCorrectly
(edu.rice.cs.drjava.model.junit.JUnitErrorModelTest):
Caused an ERROR
edu.rice.cs.util.UnexpectedException: java.lang.InterruptedException


Testsuite: edu.rice.cs.drjava.model.repl.InteractionsModelTest
Tests run: 10, Failures: 0, Errors: 1, Time elapsed: 1.486 sec

Testcase: testInterpretCurrentInteractionWithIncompleteInput
(edu.rice.cs.drjava.model.repl.InteractionsModelTest):
Caused an ERROR
junit.framework.TestCase$MultithreadedTestError:
The test did not perform a join on all spawned threads.


Testsuite: edu.rice.cs.drjava.ui.InteractionsPaneTest
Tests run: 14, Failures: 0, Errors: 1, Time elapsed: 4.876 sec

Testcase: testPromptListClearedOnReset
(edu.rice.cs.drjava.ui.InteractionsPaneTest):
Caused an ERROR
junit.framework.TestCase$MultithreadedTestError:
The test did not perform a join on all spawned threads.


Testsuite: edu.rice.cs.util.CompletionMonitorTest
Tests run: 2, Failures: 0, Errors: 1, Time elapsed: 0.061 sec

Testcase: testDegenerateSignal
(edu.rice.cs.util.CompletionMonitorTest):
Caused an ERROR
junit.framework.TestCase$MultithreadedTestError:
The test did not perform a join on all spawned threads.


Testsuite: edu.rice.cs.util.ReaderWriterLockTest
Tests run: 7, Failures: 0, Errors: 1, Time elapsed: 0.138 sec

Testcase: testMultipleReaders
(edu.rice.cs.util.ReaderWriterLockTest):
Caused an ERROR
junit.framework.TestCase$MultithreadedTestError:
The test did not perform a join on all spawned threads.

This already looks a lot better than the weird RMI “unmarshall” exceptions. It looks like we have three failed tests due to wrong counts, one due to an InterruptedException, and a whole four tests with bad join policies.

I’ll look at it more in the morning. I don’t really like this 3.8.2 system. It constrains me too much. I want something 5.0, with annotations, so I’ll have to see if I can rewrite DrJava or bring the missing files back to JUnit4.