LitmusKt is a litmus testing tool for Kotlin. Litmus tests are small concurrent programs exposing various relaxed behaviors, arising due to compiler or hardware optimizations (for example, instruction reordering).
This project is in an experimental stage of the development. The tool's API is unstable and might be a subject to a further change.
Simply clone the project and run ./gradlew build
.
Note that for Kotlin/JVM this project relies on jcstress.
The entry point is the CLI tool residing in :cli
subproject. You can use the --help
flag to find the details about
the CLI, but most basic example requires two settings:
- Choose a runner with
-r
option - After the options are specified, choose the tests to run using regex patterns
Create an executable and run it:
./gradlew :cli:linkReleaseExecutableLinuxX64
./build/bin/linuxX64/releaseExecutable/cli.kexe -r pthread 'StoreBuffering.*'
Depending on what you need, you can:
- Switch between
debug
andrelease
(which, among other things, toggles the-opt
compiler flag) - Specify the platform (
linuxX64
/macosX64
/macosArm64
)
Simply run the project with Gradle:
./gradlew :cli:jvmRun --args="-r jcstress -j '-m sanity' 'StoreBuffering.*'"
A single litmus test consists of the following parts:
- a state shared between threads;
- code for each thread;
- an outcome — a certain value which is the result of running the test;
- a specification listing accepted and forbidden outcomes
The tool runs litmus tests with various parameters, using the standard techniques also employed by other tools, like herdtools/litmus7 and JCStress.
The tool allocates a batch of shared state instances and runs the threads on one state instance after another, occasionally synchronizing threads with barriers. After all threads finish running, states are converted into outcomes, and the same outcomes are counted. The end result is the list of all different observed outcomes, their frequencies and their types (accepted, interesting or forbidden).
Here is an example of the LitmusKt
test:
class StoreBufferingState(
var x: Int = 0,
var y: Int = 0,
var r1: Int = 0,
var r2: Int = 0,
)
val StoreBuffering = litmusTest(::StoreBufferingState) {
thread {
x = 1
r1 = y
}
thread {
y = 1
r2 = x
}
outcome {
r1 to r2
}
spec {
accept(listOf(0 to 1, 1 to 0, 1 to 1))
interesting(listOf(0 to 0))
}
}
And here is an example of the tool's output:
outcome | type | count | frequency
---------------------------------------------
[1, 0] | ACCEPTED | 6298680 | 48.451%
[0, 1] | ACCEPTED | 6291034 | 48.392%
[0, 0] | INTERESTING | 405062 | 3.1158%
[1, 1] | ACCEPTED | 5224 | 0.0401%
Let us describe the litmus test's declaration.
- As a first argument
litmusTest
takes a function producing the shared state instance. - The second argument is DSL builder lambda, setting up the litmus test.
thread { ... }
lambdas set up the code run in different threads of the litmus tests — these lambdas take shared state instance as a receiver.outcome { ... }
lambda sets up the outcome of a test obtained after all threads have run — these lambdas also take shared state instance as a receiver.- the
spec { ... }
lambda classifies the outcomes into acceptable, interesting, and forbidden categories.
Here are a few additional convenient features.
- Classes implementing
LitmusAutoOutcome
interface set up an outcome automatically. There are a few predefined subclasses of this interface. For example, the classLitmusIIOutcome
withII
standing for "int, int" expects two integers as an outcome. This class have two fieldsvar r1: Int
andvar r2: Int
. These fields should be set inside litmus test's threads, and then they will be automatically used to form an outcome. - Additionally, if the state implements
LitmusAutoOutcome
, you can use a shorter syntax for declaring accepted / interesting / forbidden outcomes. For example, forLitmusIIOutcome
you can useaccept(r1: Int, r2: Int)
to add(r1, r2)
as an accepted outcome. - Finally,
LitmusAutoOutcome
is considerably more performant than manually creating any extra outcome object. It is therefore strongly advised to use this interface at all times. - Since each test usually has its own specific state, it is quite useful to use anonymous classes for them.
Using these features, the test from above can be shortened as follows:
val StoreBuffering: LitmusTest<*> = litmusTest({
object : LitmusIIOutcome() {
var x = 0
var y = 0
}
}) {
thread {
x = 1
r1 = y
}
thread {
y = 1
r2 = x
}
spec {
accept(0, 1)
accept(1, 0)
accept(1, 1)
interesting(0, 0)
}
}
Litmus tests are run with a LitmusRunner
. This interface has several running functions:
runTests(tests, params, timeLimit)
runs severaltests
one after another, each with the givenparams
, optionally repeating each test for the duration oftimeLimit
.runSingleTestParallel(test, params, timeLimit = 0, instances = ...)
runs a single test in parallelinstances
, with the givenparams
and optionally repeating fortimeLimit
. The default value forinstances
is#{of cpu cores} / #{of threads in test}
.
The following implementations of LitmusRunner
are available:
- For native:
WorkerRunner
: based on K/NWorker
APIPthreadRunner
: based on C interop pthread API
- For JVM:
JvmThreadRunner
: a simple runner based on Java threadsJCStressRunner
: a special runner that delegates to JCStress. Note that many ofLitmusRunner
parameters are not applicable to JCStress. Furthermore, there are JCStress-exclusive options as well.
There is a number of parameters that can be varied between test runs. Their influence on the results can change drastically depending on the particular test, hardware, and so on.
AffinityMap
: bindings from thread to CPU cores. Obtained throughAffinityManager
, which is available fromgetAffinityManager()
top-level function.syncEvery
: the number of tests between barrier synchronizations. Practice shows that on Native the reasonable range is somewhere in the range from 10 to 100, while on JVM it works best in the range from 1000 to 10000. This highly depends on the particular test.Barrier
: can be either Kotlin-implemented (KNativeSpinBarrier
) or C-implemented (CinteropSpinBarrier
). C-implemented might yield better results. On JVM, useJvmSpinBarrier
in favor ofJvmCyclicBarrier
.
Common practice is to iterate through different parameter bundles and aggregate the results across them.
- Function
variateParameters()
takes the cross-product of all passed parameters (hence uselistOf(null)
instead ofemptyList()
for unused arguments). - For results aggregation, use
List<LitmusResult>.mergeResults()
. - You can also use
LitmusResult.generateTable()
to format the results into a human-readable table.
The project consists of several subprojects:
:core
contains the core infrastructure such asLitmusTest
andLitmusRunner
interfaces, etc.:testsuite
contains the litmus tests themselves.:codegen
uses KSP to collect all tests from:testsuite
.:jcstress-wrapper
contains the code to convertLitmusTest
-s into JCStress-compatible Java wrappers.:cli
is a user-friendly entry point.
- If you decide to add some litmus tests, and you wish for them to be registered in the CLI, you must put them into
:testsuite
subproject. Use the existing tests as reference for the proper test structure. - Setting thread affinity is not supported on macOS yet. As such,
getAffinityManager()
returnsnull
on macOS. - It is possible to run the tests with
@Test
annotation. However, the tests are run in debug mode by thekotlinx.test
framework. Running litmus tests in the debug mode can affect their results, potentially hiding some relaxed behaviors. - In practice, all cases of currently found relaxed behaviors can be consistently found in under a minute of running.
- Avoid creating unnecessary objects inside threads, especially if they get shared. This not only significantly slows down the performance, but can also introduce unexpected relaxed behaviors.
- The tool currently doesn't address the false sharing problem. It has been shown to be fairly significant, but we looked for a solution and found none good enough. This problem can be resolved with a
@Contended
-like annotation in Kotlin, which does not yet exist. - When writing tests with
LitmusAutoOutcome
, it is possible to achieve a post-processing step similar to JCStress@Arbiter
. To do that, you can write your code in theoutcome{}
section, and then returnthis
from it. An example can be found in the WordTearing test.