Deterministic parallel execution of native threads

[kmcallister]

Bergan, Anderson, Devietti, Ceze & Grossman. (2010). CoreDet: a compiler and runtime system for deterministic multithreaded execution. ACM SIGARCH Computer Architecture News 38(1), pp. 53-64.

The applications include:

• Deterministic execution during debugging
• Manipulating thread scheduling to uncover concurrency bugs. This would be very powerful combined with coverage-based adaptive fuzzing.

The system described in the paper uses alternating stages of parallel and serial execution, each bounded in time. In the simplest execution model, inter-thread communication blocks until serial mode. They also describe how to optimize this using approaches similar to cache coherence.

Their implementation uses an LLVM pass to instrument each access to possibly-shared memory. In Rust it should suffice to instrument std::sync::atomic or the equivalent LLVM intrinsics. From §7.3:

for data race free programs, deterministic synchronization is sufficient for full determinism

The LLVM pass injects other code to handle calls to external libraries (which may have uninstrumented data races), and to provide deterministic, bounded time quanta during execution. rr uses hardware performance counters for the latter purpose, which would be an interesting variation to explore.

[naturallymitchell]

See https://github.com/rust-lang/rfcs/issues/819 for Rust-native tools to handle this.