Say goodbye to awful concurrency bugs -- Showcase of MTRAT on Tomcat

Multicore hardware trend drives more and more program archtects and progreammers take the double-edged sward -- parallel program, even it has been very notorious for its non-determined bugs, such race condition and deadlock, however mostly their injuries were beaten black and blue by this double-edged sward. What should and could we do? MTRAT might be one of the live-saving straw.

Today, I will show how do we use MTRAT to find concurrency defects in Tomcat, and hope this tool and article could comfort ones heart if he/she has been hurt by concurrency bugs a lot.

In one word, MTRAT instrument java classes when they are loaded by JVM, and runtime analysis engine is running during the program's execution. Once it finds some potential problems, it will report them with sufficient information, such as thread backtrace, class name, object id, etc.

Now, let us start the journey of MTRAT on Tomcat (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.
2. Start tomcat.
   [qiyao@mtrat-test:~/SourceCode/apache-tomcat-6.0.16]$ ./bin/startup.sh
3. check java process of tomcat, record the process information of tomcat java process.
   [qiyao@mtrat-test:~/SourceCode/apache-tomcat-6.0.16]$ ps -elf | grep tomcat
   0 S qiyao 7415 1 4 81 0 - 143807 stext 11:13 pts/1 00:00:10 /opt/ibm-java-i386-60/bin/java -Djava.util.logging.manager=org.apache.juli.ClassLoaderLogManager -Djava.util.logging.config.file=/home/qiyao/SourceCode/apache-tomcat-6.0.16/conf/logging.properties -Djava.endorsed.dirs=/home/qiyao/SourceCode/apache-tomcat-6.0.16/endorsed -classpath :/home/qiyao/SourceCode/apache-tomcat-6.0.16/bin/bootstrap.jar -Dcatalina.base=/home/qiyao/SourceCode/apache-tomcat-6.0.16 -Dcatalina.home=/home/qiyao/SourceCode/apache-tomcat-6.0.16 -Djava.io.tmpdir=/home/qiyao/SourceCode/apache-tomcat-6.0.16/temp org.apache.catalina.startup.Bootstrap start
   
   
4. stop tomcat,
   [qiyao@mtrat-test:~/SourceCode/apache-tomcat-6.0.16]$ ./bin/shutdown.sh
   
   
5. Replace java with mtrat in process command line, and run it,
   ~/MTRAT/mtrat/mtrat -x java.*:com.*:sun.*:org.apache.xerces.*:javax.managment.* -Djava.util.logging.manager=org.apache.juli.ClassLoaderLogManager -Djava.util.logging.config.file=/home/qiyao/SourceCode/apache-tomcat-6.0.16/conf/logging.properties -Djava.endorsed.dirs=/home/qiyao/SourceCode/apache-tomcat-6.0.16/endorsed -classpath :/home/qiyao/SourceCode/apache-tomcat-6.0.16/bin/bootstrap.jar -Dcatalina.base=/home/qiyao/SourceCode/apache-tomcat-6.0.16 -Dcatalina.home=/home/qiyao/SourceCode/apache-tomcat-6.0.16 -Djava.io.tmpdir=/home/qiyao/SourceCode/apache-tomcat-6.0.16/temp org.apache.catalina.startup.Bootstrap start
6. Access tomcat via browser and click examples shipped in tomcat, then you will see some data races are report in console,

Actually, user could deploy some applications to tomcat, and drive http requests to tomcat. Then, MTRAT could find more potential race conditions. In our experiments, we find some potential race conditions in tomcat 6.0.16, and one of them has been confirmed by tomcat commnity. See bug 45608

ANN: Concurrent Building Blocks: 0.3.2 released!

The Amino team is pleased to announce a new release of Concurrent
Building Blocks (Apache License v2).

(1) News in this release:
- Fix existing bugs
- Improved performance of C++ components
- A new bounded queue in Java
- Better makefile scripts

(2)The primary goal is to develop concurrent Java/C++ libraries that
can be used by programmers. Components are grouped into four
categories:
- Data Structures
- Parallel Patterns
- Parallel functions
- Atomics and STM

(3) Links
- Download and learn more from http://amino-cbbs.sourceforge.net/
- Discussion: https://groups.google.com/group/aminoprj
- Project Blog: http://aminoprj.blogspot.com/
- SourceForge: https://sourceforge.net/projects/amino-cbbs/
- Issue Tracker: https://sourceforge.net/tracker2/?group_id=209259
Your feedbacks are welcome!

Amino Team

Find parallel errors using MTRAT

Multicore architectures have become very popular. To take full advantage of such processor architectures, developers have to introduce parallelism in their software. Developing parallel software is hard and error prone. The most common parallel errors are data race and deadlock. When these errors occur, they are typically hard to locate. The Amino: Multi-threaded Runtime Analysis Tool (MTRAT) for Java can be used by developers to find these hard-to-find bugs.

Here I give two examples on how MTRAT finds data race and deadlock errors in parallel programs.

Data race occurs when two threads access the same memory location with no ordering constraints enforced between the accesses, where at least one of these accesses is a "write”. The Java sample below has potential data race. Class Value declares an integer field “x”, a synchronization method “add” to get x value and modify its value, a non-synchronization method “get” to return x value. We construct class Task by two Value instance and start two Task thread in main function. Run sample.DataRace with MTRAT, we can check potential data races in program runtime.

MTRAT detection result shows below. One data race is found by MTRAT, and it is reported with class fields, threads which access this field, and stack back trace information. This Read/Write data race happens on field x class sample/Value because two Task threads will visit instance v1 and v2, but add and get method in class Value are not protected by a same lock.

Run MTRAT in eclipse:

A deadlock is a situation in which two or more competing actions are waiting for the other to finish, so that neither ever does. Both situations are destructive and are common when building multi-threaded programs. The Java sample below has potential deadlock. In method harness2 of class Deadlock, two instances of StringBuffer L1 and L2 are created as parameters of class T3 constructor. In method run of class T3, thread will acquire two object locks sequentially, and then release them in opposite order. Since L1 and L2 are passed to t1 and t2 in opposite order, two threads will acquire two locks in opposite order, deadlock occurs. Run sample.Deadlock with MTRAT, we can check potential deadlocks in program runtime.

Run MTRAT in command line:

Run MTRAT in eclipse:

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.
  

Concurrent Building Blocks --- Overview

Overall Goals

---

The primary goal of the Amino open source software project is to develop concurrent libraries
or building blocks that can be used by programmers. These building blocks share the following
properties:

1)High-performance and good scalability

2)Portable across various platforms (hardware/OS)

3)Consistent programming idioms (with differences in expression of APIs as necessary) across Java,
C/C++ and other popular programming languages.

4)Exploitation of the latest multicore processors and systems

5)Tested for performance and correctness at scale

There is no restriction about the type of concurrent components one can contribute to the project as
long as they are shown to be useful in building real applications. However, we do plan to focus the
project in four specific ways at least at the outset.

1)Initial focus will be on components which run on shared memory systems.

2)There is a bias toward working on components which are very broadly usable.

3)We plan to focus on Java and C/C++.

4)At the outset, we expect the platform to be x86/Linux.

Initial Goals

---

The initial set of building blocks can be grouped into 4 categories

1)Data Structures: A set of lockfree collection classes. Since these datastructures were developed
using lockfree algorithms, they enjoy some of the basic lockfree properties like, immunity from different
types of deadlocks, immunity for priority inversion, etc.

2)Patterns and Scheduling Algorithms: Most application parallelization efforts follow one or more of
a number of well known parallel computation patterns. We provide a set of patterns that developers can
directly leverage to build parallel applications. The patterns we propose to provide will include (but
not limited to): Master-Worker, Map-reduce, Divide and conquer, Pipeline, etc. We also plan to provide
a set of schedulers. The schedulers can be used in conjunction with the patterns classes.

3)Parallel implementations of general-purpose functions: Example of functions to include, but not limited to:
a)String, Sequence and Array functions: Sort, Search, Merge, Rank, Compare, Reverse, Shuffle, Rotate, Median, etc.
b)Tree and Graph functions: Connected Components, Spanning Trees, Shortest Path, Graph Coloring, etc.

4) Atomics, STM, etc.
a)Deliver a C++ implementation of atomics. This implementation will be based on the draft of the C++
standards definition of the interface for atomics.
b)Deliver an open, flexible implementation of Software Transactional Memory.