Twist 🧵

He must look to meet whatever events his own fate and the stern Klothes twisted into his thread of destiny when he entered the world and his mother bore him.

– Homer 🏛, Odyssey 7.193 (trans. Walter Shewring)

Systematic concurrency testing for modern C++

Keywords: fault injection, deterministic simulation, stateless model checking

Documentation

Guide (ru)

Simulation

Demo

• (entry) mutex_lock_order – simple deadlock with 2 threads and 2 mutexes, exhaustive search with DFS scheduler
• (medium) bounded_queue – bounded blocking queue, Random scheduler
• (expert) pthread_cond – missed wake-up in pthread_cond_wait, PCT scheduler
• and more...

Features

• Determinism
  • Scheduling
  • Randomness
  • Time
  • Memory (in isolation mode)
    • stable addresses across runs for
      • new allocations,
      • thread stacks,
      • static [thread-local] variables
    • content of dynamic allocations and thread stacks
• Customizable schedulers
  • Coop – cooperative scheduler for manual simulation
  • Random – randomized fair scheduler
    • randomized run queue
    • randomized wait queues in futex / synchronization primitives
    • spurious wake-ups and atomic::compare_exchange_weak / mutex::try_lock failures
  • PCT – A Randomized Scheduler with Probabilistic Guarantees of Finding Bugs
  • DFS – exhaustive depth-first search
    • TLA⁺-like branching twist::assist::Choice and bool twist::test::body::Either()
    • max_preempts bound
    • max_steps bound
    • non-terminating tests support (while (true))
  • Recorder / Replay
• Checks
  • Assertions (TWIST_ASSERT)
  • Synchronization
    • Global deadlock detection
    • Happens-before tracking, precise data race detection (with twist::assist::Shared<T> annotations)
      • std::atomic_thread_fence support
      • malloc support
  • Memory
    • Leaks (automatic),
    • Double-free (automatic),
    • Heap-use-after-free (with twist::assist::MemoryAccess or twist::assist::Ptr<T>)
  • Determinism
  • Compatibility with UndefinedBehaviourSanitizer
• Simulator
  • Drop-in replacements for std synchronization primitives
  • futex
  • Spurious wake-ups for futex and std::condition_variable, spurious failures for std::mutex::try_lock and std::atomic<T>::compare_exchange_weak
  • Static {global, local} [thread-local] variables and class members
  • std::this_thread::sleep_{for, until} and std::condition_variable::wait_{for, until} with time compression
  • std::thread::detach support for background threads
  • User context switching support

How to use

• #include <atomic> → #include <twist/ed/std/atomic.hpp>
• std::atomic<T> → twist::ed::std::atomic<T>

Twist-ed SpinLock

#include <twist/ed/std/atomic.hpp>
#include <twist/ed/wait/spin.hpp>

class SpinLock {
 public:
  void Lock() {
    // Execution backend-aware backoff for busy waiting
    twist::ed::SpinWait spin_wait;
    
    while (locked_.exchange(true)) {  // <- Faults injected here
      spin_wait();  // ~ spin_wait.Spin();
    }
  }

  void Unlock() {
    locked_.store(false);  // <- Faults injected here
  }

 private:
  // Drop-in replacement for std::atomic<T>
  twist::ed::std::atomic<bool> locked_{false};
};

Examples

• futex – twist::ed::futex::Wait
• spin – twist::ed::SpinWait
• chrono – twist::ed::std::this_thread::sleep_for / time compression
• static – static {global, local} variables, static class members
• thread_local – static thread-local variables
• assist – twist::assist::
• trace – twist::trace::

Standard library support

twist/ed/std/, namespace twist::ed::std::

• atomic<T>, atomic_flag (atomic.hpp)
• mutex, timed_mutex (mutex.hpp)
• shared_mutex (shared_mutex.hpp)
• condition_variable (condition_variable.hpp)
• thread (thread.hpp)
• this_thread:: (thread.hpp)
  • yield
  • sleep_for, sleep_until
  • get_id
• random_device (random.hpp)
• chrono:: (chrono.hpp)
  • system_clock
  • steady_clock
  • high_resolution_clock

Installation

FetchContent

# https://cmake.org/cmake/help/latest/module/FetchContent.html
include(FetchContent)

FetchContent_Declare(
        twist
        GIT_REPOSITORY https://gitlab.com/Lipovsky/twist.git
        GIT_TAG master
)
FetchContent_MakeAvailable(twist)

add_executable(my_test main.cpp)
target_link_libraries(my_test PRIVATE twist)

CMake Options

• TWIST_ED_ATOMIC_WAIT – Support {atomic, atomic_flag}::wait (ON / OFF)
• TWIST_ED_SURE – Support for Sure

Runtime

• TWIST_FAULTY – Fault injection (ON / OFF)
  • TWIST_FAULT_PLACEMENT – Where to inject faults: BEFORE (default) sync operation / AFTER / BOTH sides
• TWIST_SIM – Deterministic simulation (ON / OFF)
  • TWIST_SIM_ISOLATION – User memory isolation (ON / OFF)
  • TWIST_SIM_DEBUG – Debug information for pretty stack traces (ON – binutils-dev package required / OFF)