Content
What is Thrille?
Thrille is a framework for building analyses for multithreaded C/C++ programs on Linux. At its core, Thrille uses dynamic library interposition to intercept and modify synchronization calls to the Pthread library and other system libraries. We use the LLVM compiler to track a program's memory accesses.
Thrille was built to support our trace simplification work that appeared in FSE10. However, many interesting analyses can be reasonably built on top of the Thrille core. We are releasing our code in the hopes of making head-to-head comparisons easier and to allow other researchers to skip some of the grunt work of implementing a multithreaded analysis.
Thrille Status
Thrille is under active development as of 1/15/2011.
Getting the Code
Thrille is hosted as an open source project on Github.
If you are interested in cloning the project to try out or modify Thrille, use the following command:
git clone git://github.com/nicholasjalbert/Thrille.git
The top level README is fairly extensive and walks through setup as well as a few examples.
Mailing List
Please send general questions/comments/suggestions to the Thrille mailing list so they can be archived for posterity:
thrille-support@googlegroups.com
Feel free join the group or browse the archives here.
FAQ
Does Thrille work on Mac OS X?
No! Macs use a slightly different dynamic linking and shared library system that breaks Thrille. The required changes may just be cosmetic but I haven't yet had time (or inclination) to investigate a fix.
Where can I get the benchmarks described in your paper?
Benchmarks are included in the code package described in Getting the Code. Remember that the majority of the bugs were hand-seeded so be careful when drawing conclusions about "real" concurrency bugs if you are just looking at these benchmarks.
Can I use Thrille on [insert arbitrary program here]?
It depends on what you want to do. First, does the program use Pthreads for multithreading? If not, you will likely have to add tracking for more synchronization functions to Thrille's core.
If your program does use Pthreads, there are still some caveats. Tools like model checkers, deterministic record and replay systems, and Tinertia expect that all non-determinism aside from the thread schedule is controlled. This assumption is valid for the included benchmarks. This assumption is not valid for general programs.
For the benchmarks included with Thrille, it was sufficient to fix input files and parameters, deterministically seed random number generators, and add a bit of determinism to memory allocation. In general, you may have to contend with timing issue (e.g. RDTSC instructions), networking issues, and non-deterministic OS constructs among other things. While these are not insurmountable technical hurdles, Thrille is not yet robust enough to properly handle all this in general programs.
However, some tools don't need these kinds of deterministic guarantees and can be robustly implemented in the current Thrille framework. For example, a simple race directed random tester is fairly straightforward to implement.
What can you tell me about the CHESS implementation?
The CHESS implementation is a basic implementation of the algorithm described in Musuvathi and Qadeer's"Iterative Context Bounding for Systematic Testing of Multithreaded Programs. Notably there is no partial order reduction included in the implementation. There is a fair scheduler to ensure the model checking will terminate on all the included benchmarks.
How do you uniquely identify scheduling points?
For the model checking and Tinertia implementations we just use the PC of the instruction at which we are scheduling. This is sufficient as we guarantee a determinisitic environment for our benchmarks and that only one thread executes at a time.
How do you guarantee atomicity between instrumentation and execution of memory instructions?
For the model checking and Tinertia implementations this was not a concern as the serializer tool guarantees only one thread executes at a time.
In general, if you are writing an analysis that allows the program to run in parallel then this could become a concern. The LLVM pass only instruments before memory read and writes. Thus, the following situation could occur: Thread 1 could execute the instrumentation before instruction A, then Thread 2 executes instrumentation and a conflicting instruction B, and finally Thread 1 will execute instruction A. Thus, your analysis will see that Thread 1 executed A before Thread 2 executed B, but in reality the reverse occurred.
A fix is currently in progress--we will provide handles to instrument both "before" and "after" memory accesses. In this case, if atomicity of instrumentation and instruction execution matters, you can grab a global lock, do your instrumentation, execute the instruction, then release the lock in the "after" handle.