Say goodbye to awful concurrency bugs -- Showcase of MulticoreSDK on Derby

In my last blog, I illustrate one of the notorious concurrency bugs – deadlocks, and how to find them without reproducing the deadlock using MulticoreSDK. The sample I gave was the classic dining philosophers problem. To verify how effective the tool is, I am thinking that MulticoreSDK should be applied to real-world applications to find real deadlocks.

Finally I found one real deadlock case reported in Derby, an open source relational database implemented in Java. Then this real deadlock case becomes one of our benchmarks to verify effectiveness of MulticoreSDK deadlock detector.

I downloaded the driver program BlobDeadlock.java and the buggy Derby version. Apply MulticoreSDK in the deadlock case with following steps,

1. Download MulticoreSDK from its website, and install it following the user manual. Suppose MulticoreSDK is extracted under {msdk-cmd}.
   
2. Open KingProperties file in props folder, set preference targetClasses = org/apache/derby to instrument and monitor all classes in Derby.
   
3. Compile the driver program,

$ mkdir bin && javac -d bin BlobDeadlock.java

4. Run the driver program with MulticoreSDK (no real deadlock occurs in execution)

$ java -Dcontest.preferences={msdk-cmd}/prop/KingProperties -javaagent:{msdk-cmd}/lib/ConTest.jar -cp .:bin:derby.jar BlobDeadlock

5. Run post analysis against trace file,

$ java -ea -cp ConTest.jar com.ibm.contest.lock_dis_checker.Main .

Surprisingly, the post analysis found no deadlock cycle. I first checked the trace file generated in step 4 and threaddump.txt indicates where the deadlock happens. According to threaddump.txt file, one of the two threads involved in the deadlock is waiting to acquire lock at java.util.Observable.deleteObserver(Observable.java:78). I realize that in step 2, we didn't specify to instrument Java core classes, such as java.util.Observable, etc. So the locks taken in Observable class were not traced in file. Perhaps it's the root cause why MulticoreSDK doesn't report the deadlock in Derby.

Following additional steps are taken to instrument class Observable,

1. Open KingProperties file in props folder, set preference targetClasses = java/util/Observable.
   
2. Instrument class Observable offline, since JVM doesn't give you a chance to instrument preloaded Java core classes in runtime,

$ java -cp {msdk-cmd}/lib/ConTest.jar:{$JAVA_HOME/jre/lib} com.ibm.contest.instrumentation.Instrument java.util.jar

After that, apply MulticoreSDK in the deadlock case again from step 2 above. The deadlock analysis result is shown below,

Listing 1. Potential Deadlocks Results from Derby

Deadlock Cycle 1: [666, 315] #315->#666 #666->#315 edge #315->#666 consists of: Thread [java.lang.Thread@1909682643]: lock taken at [java/util/Observable.java:78 deleteObserver(java.util.Observer) org.apache.derby.impl.store.raw.data.BaseContainerHandle@840] inside a different lock taken at [org/apache/derby/impl/store/raw/data/BasePage.java:1720 releaseExclusive() org.apache.derby.impl.store.raw.data.StoredPage@487] edge #666->#315 consists of: Thread [java.lang.Thread@1915449899]: lock taken at [org/apache/derby/impl/store/raw/data/BasePage.java:1334 isLatched() org.apache.derby.impl.store.raw.data.StoredPage@487] inside a different lock taken at [org/apache/derby/impl/store/raw/data/BaseContainerHandle.java:408 close() org.apache.derby.impl.store.raw.data.BaseContainerHandle@840] ===================================================

Now MulticoreSDK successfully reports the same deadlock to the real deadlock case despite that the deadlock doesn't surface once in my execution :)

MulticoreSDK Tool Link

http://www.alphaworks.ibm.com/tech/msdk

Performance of Amino Queue

Now we got the performance result of Amino Queue in an 8-core X86 machine which is running Linux and IBM JDK v6. We compared the performance of Amino's LockFreeQueue and java.util.concurrent.ConcurrentLinkedQueue. Both of the two queues used lock-free algorithm. Amino queue's algorithm comes from the brilliant paper "An Optimistic Approach to Lock-Free FIFO Queues" of Edya Ladan-Mozes and Nir Shavit. Result of the micro-benchmark shows Amino queue has some advantage:


The key idea behind the new algorithm is a novel way of replacing the singly-linked list of Michael and Scott, whose pointers are inserted using a costly compare-and-swap (CAS) operation, by an optimistic doubly-linked list, whose pointers are updated using a simple store, yet can be fixed if a bad ordering of events causes them to be inconsistent.

Performance of Amino Stack

In Amino library, stack is the simplest and yet the most useful component. According to our performance test, Amino's stack is far more faster than a lock-protected stack. Today I rerun the performance test on a 8-core X86-64 machine and result is as shown in below diagrams:










In the performance test, the 1st step is warm-up with 8 threads. That's the reason that first column of every bar charts has a label of "8". After that, we increase the thread number from "1" to "128". The test complete in 1,039.557 second.

The code (Apache license) of LockFreeStack can be downloaded at Amino's SF.net SVN

MTRAT helps opensource projects find concurrent errors

Developing, testing, and debugging multithreaded programs are still very difficult; it is all too easy to create concurrent programs that appear to work, but fail when it matters most: in production, under heavy load. The most common parallel errors are data race and deadlock. These errors are typically harmful and hard to locate. Multi-Thread Run-time Analysis Tool(MTRAT) is a tool that detects and analyzes potential data race and deadlock conditions that might occur in multithreaded Java programs.

Apache FtpServer is a popular open source Java FTP server. In order to handle multiple requests at the same time, threading and concurrency are introduced in FtpServer core and its dependent library MINA, a network application framework. Let's exploit MTRAT on FtpServer to see what happens and apply MTRAT in FtpServer is easy(my operating system is Linux, so this showcase is done under Linux).

1. Download MTRAT from its webiste http://www.alphaworks.ibm.com/tech/mtrat, and configure it following the user manual. Suppose mtrat is extracted under ~/MTRAT.
   
2. The FtpServer startup script file ftpd.sh locates under bin folder, open ftpd.sh and find "$JAVACMD" -classpath "$FTPD_CLASSPATH" $MAIN_CLASS $@ in last few lines, this command is for invoking FtpServer application. Comment this line with heading "#" and add one statement to replace "$JAVACMD" with "mtrat" like this,
   ~/MTRAT/mtrat/mtrat -x java.*:sun.*:javax.*:com.*:org.eclipse.*
   :org.apache.xerces.*:org.apache.lucene.* -Dcom.ibm.mtrat.dbg.cl=false -Dcom.ibm.mtrat.novolatile=true -Dcom.ibm.mtrat.threadcache=true -Dcom.ibm.mtrat.osm=true -classpath "$FTPD_CLASSPATH" $MAIN_CLASS $@
   #"$JAVACMD" -classpath "$FTPD_CLASSPATH" $MAIN_CLASS $@
   
3. Save ftpd.sh and run it.
   

After Ftpserver launches with MTRAT, we open two new consoles and login as admin and anonymous respectively, then admin uploads a file to ftpserver while anonymous download a file from ftpserver. You will see data races are reported in Ftpserver console.

We submit two data race bugs found by MTRAT, one is in FtpServer([#FTPSERVER-122]Data races are found in FtpStatisticsImpl) while the other is in MINA([#DIRMINA-651]Data Race in org.apache.mina.core.session.AbstractIoSession), and attach the data race report generated by MTRAT.

Positive feedback is received from the Apache community, these two data race bugs are confirmed by the community leader and [#DIRMINA-651] is committed to be fixed in MINA 2.0.0-RC1 while [#FTPSERVER-122] will be fixed after component refactor.

1. "Thanks a lot for the analysis! The reason why I did not fix the race conditions already is that I'm planning to bring FtpServers statistics handling more in line with MINA.
   Anyways, I would much appreciate further analysis on the source code, especially after the statistics implementation is updated."
   -- Niklas Gustavsson
   
2. "Some of these races are in the idle time checking, which is a core functionality in MINA of course. Those we have to fix."
   -- Niklas Gustavsson
   

In addition to data race bugs found in FtpServer, Bug 45608 in Tomcat is confirmed by community too. MTRAT is proven to be practical for real-world application and useful for parallel program developers.

Multi-threaded Runtime Analysis Tool Link

http://www.alphaworks.ibm.com/tech/mtrat

Parallel Patterns for C++ Programmer

In Amino project, we've created several experimental parallel patterns in C++. There are already advanced parallel patterns for Java programmers, such as Fork/Join from Doug Lea. But things are so ready for C++ world.

Under the current release of Amino library project, we have created three parallelized version of existing patterns from STL. The method signature is very close to the original one:

1. Foreach



Pattern Usage	Computing Kernel
vector<int> dataV; ThreadPoolExecutor exec; for_each(exec, 2, dataV.begin(), dataV.end(), sum); exec.shutdown(); exec.waitTermination();	void sum (int n) { result += n; }



2. Transform



Pattern Usage	Computing Kernel
UnaryFunc<int> uf; vector<int> dataV; int i = 0; for ( ; i1); } ThreadPoolExecutor exec; // change each elemet to its twice transform(exec, 2, dataV.begin(), dataV.end(), dataV.begin(), uf); exec.shutdown(); exec.waitTermination();	template<typename ParaType> class UnaryFunc { public: ParaType operator()(ParaType element) { return 2 * element; } };



3. Accumulate



Pattern Usage	Computing Kernel
vector<int> dataV; // Test the function 1 int result = accumulate<int>::iterator, int, ThreadPoolExecutor>(exec, 2, dataV.begin(), dataV.end()); exec.shutdown(); exec.waitTermination();	template<typename ParaType> class UnaryFunc { public: ParaType operator()(ParaType element) { return 2 * element; } };

Please note these patterns are in pretty early stage. The performance is still ridiculous now. Please let us know your opinion about the API design. And contributions are always welcome!

Extending JUnit for Testing Parallel Application

As multi-core becomes main stream, it seems inevitable we finally need to do unit tests in parallel. In order to create a parallel test case, developers need to control the mess of multiple threads themselves, which is not interesting and error-prone. Additionally, if exceptions are thrown from child threads, JUnit will silently ignore them.

Here I gave an example on how our JUnit extension works for a parallel data structure.

@RunWith(Parallelized.class)

@ParallelSetting(threadNumber = { 1, 2, 4, 8 })

public class TestThreaded {

Set strSet;

@Before

public void setUp() {

strSet = new LockFreeSet();

}

@Test

public void doNothing() {

}

@InitFor("testThread")

public void putSomeData(int size){

strSet.add("putSomeData");

}

@Threaded

public void testThread(int rank, int size) {

strSet.add("abcde" + rank);

}

@CheckFor("testThread")

public void checkResult(int size) {

assertEquals(size+1, strSet.size());

}

public static void main(String[] args) {

for (int i = 0; i < 10; i++)

JUnitCore.runClasses(TestThreaded.class);

}

}

The explanation of annotations are listed here:

Name	Annotation Argument	Arguments of annotated method	Comments
@ParallelSetting	We can specify number of threads as a named argument “threadNumber”		This annotation can be used to specify parallel settings for whole test case.
@InitFor	One string argument to specify which method to help	Annotated method should have one int type argument to accept number of threads used by this running.	It's used to mark setup method for multi-threaded test. Please note this is different as @Before since it only works for one test.
@Threaded	No argument	Two arguments should be used. One for thread number, and one for rank of current thread.	Methods marked with @Threaded will be executed by multiple thread.
@CheckFor	One string argument to specify which method to check correctness	Annotated method should have one int type argument to accept number of threads used by this running.	It's used to mark a method, which has duty to check the result of execution of @Threaded test case.

Now we can test our components in parallel without pain:


Reference

• Download Amino JUnit Extension (Apache License v2) from our SourceForge site and try it. Your feedback is welcome!
• Junit version 4.3 and above.