blob: 1842472d3eb70b36ab2e2935c2e7a2075beb81bc [file] [view]
# Standalone Cassandra Simulator
A self-contained deterministic concurrency simulator extracted from the Apache Cassandra test
infrastructure. User code running inside `sim.simulate(...)` executes under a single-threaded
scheduler; all calls that might cause threads to interleave differently (like parks, waits,
volatile/atomic writes, signals/monitors) are intercepted and turned into scheduler decisions.
CAUTION: highly experimental! Simulator was extracted from Cassandra codebase with help of
a coding agent. Even though this was done with a lot of human handholding, I still can not
vouch for this as if it was my own code).
## Quick start
```java
try (Simulator sim = new Simulator(42L, "com/example/")) {
sim.simulate((SerializableRunnable) () -> {
CountDownLatch latch = new CountDownLatch(1);
new Thread(() -> latch.await()).start();
latch.countDown();
});
}
```
## Debug park capture
Pass `captureParks = true` and the internal-name prefix of classes to transform to record the call site at which
each simulated thread parks. The site is included in every action description printed by the
scheduler, making it easy to follow which line of user code caused a thread to pause.
```java
try (Simulator sim = new Simulator(420L, 0f, /*captureParks*/ true, "com/example/")) {
sim.simulate((SerializableRunnable) () -> {
CountDownLatch latch = new CountDownLatch(1);
CountDownLatch done = new CountDownLatch(1);
new Thread(() -> {
try { latch.await(); }
catch (InterruptedException e) { Thread.currentThread().interrupt(); return; }
done.countDown();
}, "waiter").start();
new Thread(() -> latch.countDown(), "decrementer").start();
try { done.await(); }
catch (InterruptedException e) { Thread.currentThread().interrupt(); }
});
}
```
Scheduler output:
```
[t]Thread[thread-0]
[t]Invoke Thread[waiter,5,sim-420] with Thread[sim-420_waiter:1,5,sim-420]
[t]Invoke Thread[decrementer,5,sim-420] with Thread[sim-420_decrementer:1,5,sim-420]
[tw]Wakeup Thread[sim-420_waiter:1,5,sim-420] parkedAt[org.apache.cassandra.simulator_test.CountDownLatchSimTest.lambda$countDownLatchWakesWaiter$0(CountDownLatchSimTest.java:52)]
[tw]Wakeup Thread[sim-420_thread-0:1,5,sim-420] parkedAt[org.apache.cassandra.simulator_test.CountDownLatchSimTest.lambda$countDownLatchWakesWaiter$81c80a4a$1(CountDownLatchSimTest.java:60)]
```
Reading the output:
| Part | Meaning |
|---|---|
| `[t]` / `[tw]` | Action modifier flags — `t` = `START_THREAD`, `w` = `WAKE_UP_THREAD` |
| `Thread[thread-0]` | The root body thread starting up |
| `Invoke … with Thread[sim-420_waiter:1,5,sim-420]` | A new `InterceptibleThread` is being started; the name encodes `<group>_<name>:<node>,<priority>,<group>` |
| `Wakeup Thread[sim-420_waiter:1,5,sim-420]` | The scheduler is about to unpark this thread |
| `parkedAt[…]` | First non-simulator stack frame captured when the thread parked — the exact user-code line that called `await()` or `park()` |
Two transformation mechanisms work together to cover all call sites:
- **`InstanceClassLoader`** loads application classes through an ASM transformer that rewrites
call sites before the class is defined. JDK classes, the simulator framework
(`org.apache.cassandra.simulator.context.*`), and logging classes are excluded — they are
delegated to `sharedClassLoader` and reach the JVM unmodified.
- **Java agent (`InterceptAgent`, `-javaagent:simulator-asm.jar`)** uses the `Instrumentation`
API to rewrite call sites inside JDK classes that `InstanceClassLoader` cannot reach: the
`java.util.concurrent.locks.*` family (AQS, `ReentrantLock`, …), `java.lang.Object`,
`java.util.Random`, `ThreadLocalRandom`, and `ConcurrentHashMap`.
## Concepts
A simulation runs an **`ActionPlan`** — a set of initial **`Action`s** whose transitive
consequences drive the simulation forward. Each `Action` represents one discrete unit of
simulation work; executing it yields zero or more child/continuation `Action`s. The simulation
completes once all transitive consequences of the initial actions have completed.
Execution order is controlled by an **`ActionSchedule`** together with a
**`RunnableActionScheduler`** (which ready action runs next) and a
**`FutureActionScheduler`** (actions deferred to a future simulated time).
Most non-trivial actions derive from **`SimulatedAction`**, which runs on an
**`InterceptibleThread`** — a thread whose blocking calls have been replaced by scheduler
decisions. A threaded action simultaneously represents the initial synchronous step of an
execution context *and* any future continuations of that context; when a thread blocks (e.g.
enters an unbounded wait), the action has no ready consequences until another action wakes it.
Actions carry **`Modifier`** options that control behaviour — applied to the action itself,
transitively to all descendants, or filtered to specific consequence verbs. **`OrderOn`**
constraints enforce sequential ordering or rate limits among groups of actions, supporting
both executor-service simulation and correctness constraints (e.g. where a parent action's
children must occur in strict order).
Collectively the simulator controls: monitors, `LockSupport`, blocking data structures,
threads and executors, random number generation, and time.
## Terminology
- `Interceptible*` — an entity that can be intercepted. `InterceptibleThread` is a thread the simulator is able to pause. It's the subject of interception.
- `Intercepting*` — the mechanism that does the intercepting. `InterceptingMonitors` intercepts `synchronized`/`wait`/`notify`. `InterceptingExecutor` intercepts task submission. These are the active interception components.
- `Intercepted*` — an event that has been intercepted and is now sitting in the scheduler queue. `InterceptedWait` is a wait that was pulled out of its thread and handed to the simulator to schedule. It's the result of interception.
- `Instrumented*` — a abstraction wired up to the simulator. `InstrumentedSemaphore` implements Cassandra's Semaphore interface and routes its waits through the simulator. `InstrumentedCountDownLatch` implements Cassandra's CountDownLatch.
## Runtime activation conditions
The bytecode transformer rewrites call sites, but each stub performs runtime checks before
activating the simulator path. A JDK call is only intercepted when **all** of the following
hold:
1. **Calling thread is an `InterceptibleThread`.** Threads created outside the simulator (plain
`new Thread(...)` never passed through `startThread()`) are not `InterceptibleThread`
instances; every stub detects this and falls through to the real JDK method.
2. **Thread is actively intercepting (`interceptor != null`).** Between the moment a simulated
thread finishes its current action and the moment the scheduler re-dispatches it, the
`interceptor` field is `null`. `park*` / `wait*` stubs check `isIntercepting()` and fall
through when it is false.
3. **For `unpark`: the target thread must also be an `InterceptibleThread`.** If either the
calling thread or the thread being unparked is a plain OS thread, `LockSupport.unpark()` is
called directly.
When any condition fails the stub delegates to the real JDK method unchanged, so code paths that
happen to run on non-simulated threads continue to work normally even inside instrumented classes.
---
## What is instrumented
**`InstanceClassLoader` scope** — application code loaded by `sim.simulate()` and any class whose
package matches the `GLOBAL_METHODS` or `MONITORS` patterns:
`org.apache.cassandra.**` (excluding `org.apache.cassandra.simulator.**`) and `accord.**`.
**Agent scope** — JDK classes listed above: `java.util.concurrent.locks.*` (call sites to
`LockSupport.park*`), `java.lang.Object` (`hashCode` → deterministic id), `java.util.Random` /
`ThreadLocalRandom` (deterministic seeds), and `ConcurrentHashMap` (deterministic probing).
### Thread creation
| Call site | Redirected to |
|---|---|
| `new Thread(...).start()` | `InterceptorOfGlobalMethods$Global.startThread()` — scheduled as a simulator action |
### JDK synchronizers and constructor redirects
JDK synchronizers built on `AbstractQueuedSynchronizer`, including `CountDownLatch`, retain their
JDK implementations. The agent instruments AQS calls to `LockSupport.park/unpark`, bringing their
blocking and wakeup behavior under scheduler control. A caller can opt into a specialized latch
with `sim.intercept(CountDownLatch.class, Replacement.class)`.
The remaining default constructor redirects are:
| Original | Simulator replacement |
|---|---|
| `new ConcurrentHashMap(...)` | `InterceptibleConcurrentHashMap` (deterministic hash codes) |
| `new IdentityHashMap(...)` | `InterceptedIdentityHashMap` (deterministic hash codes) |
### Cassandra concurrent-utility factories (integration-test examples)
The integration-test module (`integration-test/src/main`) includes Cassandra-style
concurrent-utility interfaces with `@Intercept`-annotated factory methods. These are
registered at test setup via `sim.intercept(Interface.class, Impl.class)` — they are
**not** built-in simulator defaults:
| Original | Simulator replacement |
|---|---|
| `WaitQueue.newWaitQueue()` | `InstrumentedWaitQueue` |
| `CassandraCountDownLatch.newCountDownLatch(n)` | `InterceptingAwaitable.InterceptingCountDownLatch` |
| `Condition.newOneTimeCondition()` | `InterceptingAwaitable.InterceptingCondition` |
| `Semaphore.newSemaphore(n)` / `newFairSemaphore(n)` | `InstrumentedSemaphore` |
### Executor factories
All zero- and single-int-arg `Executors` factory methods are redirected by default.
Tasks submitted to the returned executor run on `InterceptibleThread` instances under
scheduler control:
| Original | Simulator replacement |
|---|---|
| `Executors.newSingleThreadExecutor()` | `InterceptingExecutorFactory.pooled(name, 1)` |
| `Executors.newFixedThreadPool(int)` | `InterceptingExecutorFactory.pooled(name, n)` |
| `Executors.newCachedThreadPool()` | `InterceptingExecutorFactory.sequential(name)` |
| `Executors.newScheduledThreadPool(int)` | `InterceptingExecutorFactory.sequential(name)` |
| `Executors.newSingleThreadScheduledExecutor()` | `InterceptingExecutorFactory.sequential(name)` |
Pool size is irrelevant to the simulator's serial scheduler; `newCachedThreadPool` and
the two scheduled variants map to a sequential executor.
`ThreadFactory`-overload variants are also redirected; the supplied factory is silently
dropped because the intercepting executor always creates `InterceptibleThread` instances.
### LockSupport (all variants)
`LockSupport.park*` and `unpark` call sites are redirected to `InterceptorOfSystemMethods$Global`
in **both** transformation paths:
- Call sites in application code — rewritten by `InstanceClassLoader` / `GlobalMethodTransformer`
- Call sites inside `java.util.concurrent.locks.*` (e.g. AQS) — rewritten by the Java agent
Covered variants:
- `park()`, `park(Object blocker)`
- `parkNanos(long)`, `parkNanos(Object blocker, long nanos)`
- `parkUntil(long)`, `parkUntil(Object blocker, long millis)`
- `unpark(Thread)`
### Monitor and Object wait/notify
For classes with the `MONITORS` flag, every `synchronized` block entry and exit is intercepted,
giving the scheduler an opportunity to switch threads. Inside those blocks:
- `Object.wait()`, `wait(long)`, `wait(long, int)` — intercepted
- `Object.notify()`, `notifyAll()` — intercepted
### Thread sleep and timed waits
| Original | Notes |
|---|---|
| `Thread.sleep(long)` / `Thread.sleep(long, int)` | Redirected to simulated sleep |
| `TimeUnit.sleep(long)` | Redirected to simulated sleep |
| `Clock.waitUntil(long)`, `Awaitable$SyncAwaitable.waitUntil(long)` | Redirected |
| `com.google.common.util.concurrent.Uninterruptibles.sleepUninterruptibly(...)` | Redirected |
### Time sources
| Original | Condition | Notes |
|---|---|---|
| `System.nanoTime()` | `SYSTEM_CLOCK` flag | Returns simulated time |
| `System.currentTimeMillis()` | `SYSTEM_CLOCK` flag | Returns simulated time |
| `TimeUtils.timestampMicros()` | `GLOBAL_CLOCK` flag | Returns monotonically-increasing simulated micros |
### Determinism helpers
| Original | Notes |
|---|---|
| `System.identityHashCode(Object)` | Returns a deterministic per-object id assigned by the simulator |
| `UUID.randomUUID()` | Returns a deterministic UUID from the simulator's random source |
| `ThreadLocalRandom.getProbe()` / `advanceProbe()` / `localInit()` | Stubbed/redirected for determinism inside `ConcurrentHashMap` |
### Future.get()
`Future.get()` call sites inside instrumented code are redirected to
`InterceptorOfGlobalMethods$Global.futureGet()`, which spin-polls `future.isDone()` and
yields to the scheduler via `parkNanos(1000L)` between attempts. This works for any
`Future` implementation — the future itself does not need to be simulation-aware.
The timed variant `Future.get(long, TimeUnit)` is also redirected; it uses simulated
time for the deadline check.
---
## What is NOT instrumented
- **Most JDK internals** — only `java.util.concurrent.locks.*`, `java.lang.Object`,
`java.util.Random`, `ThreadLocalRandom`, and `ConcurrentHashMap` are rewritten by the agent.
All other JDK classes are untouched.
- **Code in `org.apache.cassandra.simulator.*`** (excluding `simulator.test`) — the simulator
infrastructure itself is excluded from transformation to avoid infinite recursion.
- **Any class not matching the `GLOBAL_METHODS` / `MONITORS` patterns** — third-party libraries
(other than `accord.*` and `io.netty.util.concurrent.FastThreadLocal`) are not instrumented.
---
## Architecture overview
```
-javaagent:simulator-asm.jar (InterceptAgent)
└── Instrumentation API — rewrites at class-load time:
java.util.concurrent.locks.* → LockSupport call sites redirected
java.lang.Object → hashCode → deterministic id
java.util.Random / ThreadLocalRandom → deterministic seeds
ConcurrentHashMap → deterministic probing
sim.simulate(body)
└── InstanceClassLoader (loads + ASM-transforms application classes)
├── GlobalMethodTransformer (rewrites call sites listed above)
└── InterceptClasses (decides which flags apply per class)
InterceptorOfGlobalMethods$Global (static dispatch, called by transformed code)
└── InterceptingGlobalMethods (concrete implementation wired to the scheduler)
├── InterceptingExecutorFactory (creates InterceptibleThread-backed executors)
└── InterceptingMonitors (synchronized / park / wait handling)
ActionSchedule (cooperative scheduler; runs one action at a time)
└── RunnableActionScheduler (Sequential for deterministic tests; RandomUniform for fuzzing)
```
## Building and testing
```
./gradlew :simulator-core:test
```
Tests require JDK 17 (JDK 21 support is in progress — `ShadowingTransformer` strips
`ACC_FINAL` from shadow subclasses to handle classes that became `final` in JDK 21).