MuScaT: Multithreaded Scala Testing Framework
A lightweight library for unit testing concurrent programs written in Scala
Muscat provides APIs to test your concurrent code under multiple interleavings of shared operations executed by concurrent threads.
The code for the threads, inputs, and assertions to be tested have to be provided by the user much like a unit testing framework. Muscat can systematically explore multiple interleavings between selected operations, marked by
users, when they are executed concurrently by multiple threads.
It can explore interleavings even in the presence of synchronization primitives:
Muscat presents an interleaved execution trace for failed test cases, and
can detect and report deadlocks that happen at runtime.
This library is primarly intented to be used for testing small pieces of concurrent code. It was able to explore several tens of thousands of interleavings per second on such programs. In principle, Muscat could be used to test arbitrary Scala programs, provided the configuration parameters are set sufficiently high.
You can find some small illustrative example and a test suite here:
src/test/scala/ch/epfl/lara/concprog/SimpleCounterSuite.Scala. The example presents a simple concurrent program that implements the
compareAndSet operation using the
synchronized construct. It illustrates how to write unit tests using APIs provided by Muscat.
To run the example and test Muscat code do:
To use Muscat into other projects, do:
and import the jar file generated in the
Below we present an overview of how to use Muscat.
For a more detailed description and technical details see the whitepaper, which appeared in
Creating Testable Classes and Marking Atomic Operations
Muscat can be used to test programs that access or synchronize on objects shared across multiple threads.
To be able to test with Muscat, the shared classes must extend a library trait and should wrap their atomic operations within a library construct
Below we illustate it on a simple example. (You may want to follow the below described design pattern as it restricts the overheads of scheduling to the unit tests, isolating them from the normal workflow).
class Base be the class that is accessible by multiple threads and needs to be tested in a concurrent setting.
class Base could be a concurrent queue or list.
class Baseextend (or implement) the trait
ch.epfl.lara.concprog.instrumentation.monitors.Monitor. Now the
notifyAllmethods invoked on instances of
class Basecan be instrumented by the APIs provided by Muscat. Also, make sure that every indivisible operation such as read/write of a shared mutable field that may run concurrently is a separate (protected) overridable method of the class. Example:
To create a schedulable version of
class Base, create a
class Derivedwhich does the following:
extends class Base
- accept one extra parameter
- extends one of the available monitors in the package
SchedulableMonitor- This monitors the behavior of the synchronization primitives
SchedulableMonitor with LockFreeMonitor- This makes synchronization primitives throw an exception, and is meant to test lock-free data structures.
import scheduler._at the start of
- overrides or defines the indivisible operations from
class Basewrapping the indivisible operations with
exec. The construct
exechas the following signature:
exec(operation)(msgA, Some(res => msgB))where
operationis a call-by-name parameter that is indivisible operation,
msgAis the message that is logged before the operation, and
msgBis the message to log after the operation, which can refer to the result
resof the computation. Example:
Now the methods of
class Derivedcan be tested by Muscat on multiple interleavings of the shared operations marked with
execas described shortly. Note that operations marked with
execneed not necessarily be a read/write of a field but instead marks the granularity of an indivisible operations. Any context-switches within these operations are not explored by Muscat.
Writing Unit Tests
You may have a look at the first three test cases in the file
Muscat provides two functions
testSequential to test single-threaded (or sequential) behavior, and
test multi-threaded (or concurrent) behavior.
ch.epfl.lara.concprog.instrumentation.TestHelper._. takes one argument: a lamdba from a
Schedulerto the the code that needs to be tested. The code can access any data structure or methods defined in the program. However, when it accesses
Schedulableclasses such as
class Derivedits operations will be systematicaly interleaved. Note that the
Schedulerargument of the lambda shall be passed to the constructor of
class Derived, which requires a scheduler. The code should return a
(Boolean, String)pair where the
Booleanindicates if the test succeeded, and the
Stringis displayed if the test failed. The operation has a default timeout, which can be adjusted by the user.
testManySchedulesis available in
ch.epfl.lara.concprog.instrumentation.TestHelper._. It requires
- The number
nof threads to run in parallel.
- A lambda from
Schedulerto a pair consisting of:
- A list of
nlambdas accepting no argument and performing some operations. Each lamdba corresponds to the code that would be executed by the threads
- A lambda to which the result of the
nthreads (encoded as a
List[Any]) would be fed. The lambda should return a pair
(Boolean, String)where the
Booleanindicates if the test succeeded, and the
Stringis displayed if the test failed. Note that the code executed by threads can also manipulate other mutable state if necessary that is not wrapped inside
exec. For instance, to track values other than those that are returned. The tool cannot detect bugs resulting because of such mutable states.
- A list of
The exploration of interleavings can be configured using the following parameters found in the file
contextSwitchBound: Maximum number of context-switches possible in the schedules generated for testing
readWritesPerThread: Maximum number of
execoperations that can be performed by the threads. If more operations are performed by the threads, they would not be tested for multiple interleavings.
noOfSchedules: Maximum number of schedules or interleavings to test. The interleavings are uniformly randomly sampled by default.
testTimeout: The time out for a unit test in seconds. A test is considered to have failed if it exceeds the time out.
scheduleTimeout: The time out for a single interleaving. The interleaving is considered buggy and reported to the user if it exceeds this timeout.
How to add a custom line in the concurrent trace?
If you need to debug code with complex logic and want to add more statements, you can do the following:
class Baseabstract and add the following to it: (You may want to do this only during testing, and restore
Baseback to its original form)
def scheduler: Scheduler lazy val ss = scheduler import ss._
class Baseis never instantiated, only
class Derivedis. You just made the scheduler passed to
Derivedavailable to class Base.
Everywhere you need to add a log line, just do:
log("Your log line.")
It will be prefixed with the thread number in the buggy trace.
Can I find more examples on how to use the code?
Yes please have a look at the file
SimpleCounterSuite.scala and especially the interlock test.
The file has buggy and non-buggy implementations of lock-free and blocking programs
and some examples for how to test them.
Also, the whitepaper illustrates the system a producer-consumer example.
Please feel free to contact us if you are intersted in using the library and need some help in getting started.
- Ravichandhran Madhavan, Github username: ravimad, [kmrc87 at gmail dot com]
- Mikael Mayer, Github username: MikaelMayer