I have a crate that setups up cross-thread channels via thread_local and lazy_static. Shuttle reports a spurious deadlock, however, because it only frees the thread_local value for threads when they actually exit and not when they "exit" the thread scheduler (such as hitting the end of shuttle::check_random(|| { })) - I am using the thread_local Drop impl causing the last sender of a channel to go away to unblock another thread's receiver, so the other thread can exit once there are no more clients. Because thread_locals don't drop, the sender is never removed, and so the receiver is reported as a deadlock, despite this not being possible in normal operations.

I have a manual workaround, where I just RefCell::take() the channel at the end of my shuttle tests in order to manually drop the sender, but it would be nice to not need this (and it took me more than a little while to figure out what exactly was going on and realize the problem, which may hit other people).

Without try_lock it was easier to justify context switches, because acquire was a right mover (we only needed a context switch before) and release was a left mover (we only needed a context switch after). However, with try_lock that is not the case anymore. This commit argues why we need a context switch at the end of lock and try_lock (both in the success and failure case), and why we do not need a context switch at the beginning of try_lock and MutexGuard::drop.

By submitting this pull request, I confirm that my contribution is made under the terms of the Apache 2.0 license.

Just a couple of small things: removing the Debug bound from the Scheduler trait, and removing some clippy allows that are now fixed upstream.

By submitting this pull request, I confirm that my contribution is made under the terms of the Apache 2.0 license.

Currently, if code tries to re-acquire a lock it already holds, it correctly panics but with an unhelpful error message about Shuttle's internals. Instead, let's provide a nicer error message about why the calling code is buggy.

This came up while trying out the super neat example from a fasterthanlime blog post, which Shuttle has no trouble finding the deadlock in, but wasn't giving a helpful error message for.

By submitting this pull request, I confirm that my contribution is made under the terms of the Apache 2.0 license.

Hi, first of all, thanks for the great project!

I try to use shuttle in one of my projects and it failed to resolve dependencies. The reason is that the version on crates.io pins its dependencies on minor versions. I noticed that it was fixed in this commit, but the code is not released to crates.io.

Is it possible to release a new minor version to reflect the changes made to shuttle since last release?

This is to match the standard library, which doesn't require the contents of a lock to be Sized.

By submitting this pull request, I confirm that my contribution is made under the terms of the Apache 2.0 license.

It's possible for a task's waker to be invoked in the middle of a call to that task's poll by the executor. We had accounted for that possibility if the task called its own waker, but that's not good enough: the waker can escape to other threads that can invoke it before poll finishes (e.g., if the task blocks to acquire a lock).

This change fixes the waker behavior by clarifying the semantics of a call to wake: a task whose waker is invoked should not be blocked when it next returns Pending to the executor, and should be woken if that has already happened. To do this, we introduce a new Sleeping state for tasks, that has the same semantics as Blocked but that is recognized by waker invocations, which will only unblock a task in Sleeping state. This also removes the special case "woken by self" behavior -- being woken by any thread should be enough to trigger this sleep logic.

By submitting this pull request, I confirm that my contribution is made under the terms of the Apache 2.0 license.

When an async task's JoinHandle is dropped, we mark the task as dropped. Dropped tasks are not allowed to force a deadlock, meaning that execution can end successfully when all tasks are either finished or dropped. At the same time, dropped tasks should still be runnable by the executor so long as some non-dropped task has not finished.

By submitting this pull request, I confirm that my contribution is made under the terms of the Apache 2.0 license.

Double panics are a common problem in concurrent Rust code. For example, a thread might panic while holding a lock, and then need to acquire that lock again during stack unwinding, but the lock is already poisoned. In these cases, Shuttle currently can't print the schedule that led to the original panic, because the double panic aborts the process before our catch_unwind has a chance to run.

This change adds a new panic hook that gets a chance to run before the double panic happens. We use this hook to print the schedule, so that even if we double panic in future at least the user gets some output they can use to reproduce the problem. There's some trickiness here (outlined in a module comment for failure.rs) around running different panic handlers at different times, which makes the code a little more complex than I would have hoped, but it gets the job done.

By submitting this pull request, I confirm that my contribution is made under the terms of the Apache 2.0 license.

This change adds support for tracking causality among thread operations. We do this in the standard way, by associating a vector clock with each thread. The i'th element of a thread's vector clock denotes its knowledge of the clock of thread i. Clocks are partially ordered using a pointwise ordering <. The main property we want is that for any pair of events p, q: (p causally precedes q) iff (clock at p < clock at q).

We update the code for thread spawn and join, as well as the various synchronization objects (Atomics, Barriers, CondVars, Mutexes, RwLocks and mpsc channels) to track causality by updating vector clocks appropriately.

This change does not currently properly track causality for async interactions; those will be done in a subsequent PR.

By submitting this pull request, I confirm that my contribution is made under the terms of the Apache 2.0 license.

Tasks that implement busy-wait loops or other infinite loops are a fairness issue for schedulers like PCT, which will run a thread indefinitely until it blocks. This change makes both sync and async versions of yield_now act as a hint to the scheduler that the current task should be deprioritized. Only the PCT scheduler acts on this hint, by moving the current task to the lowest priority. We could also make the DFS scheduler react to this hint by not allowing it to re-schedule the current task immediately, but that would be unsound.

By submitting this pull request, I confirm that my contribution is made under the terms of the Apache 2.0 license.

The implementation of abort in #87 as detaching the task does not seem right, because detached tasks may still continue to run. Consider the following test, which should not fail but currently does.

#[test]
fn join_handle_abort_bug() {
    check_dfs(
        || {
            let (sender, receiver) = futures::channel::oneshot::channel();
            let t = future::spawn({
                async move {
                    receiver.await.unwrap();
                    panic!("should not get here");
                }
            });
            t.abort();
            sender.send(()).unwrap();
            shuttle::thread::yield_now();
        },
        None,
    );
}

(The yield_now is needed because otherwise the main task would immediately finish, in which case also the execution finishes because there are no attached tasks left.)

We need a way to actually cancel a task, which drops its continuation and returns a JoinError indicating cancellation.

I have a shuttle test for a crate I wrote. It occasionally hits a deadlock that shuttle reports via hitting "exceeded max_steps bound ". It gives a (very big) failing schedule that I should pass to replay in order to reproduce the issue.

The problems are two fold:

1. replay_from_file can't load the outputted schedule string, always panicking with "invalid schedule"
2. ~~reducing the max_steps via a custom Config.max_steps so that the schedule is able to be embedded as an argument to replay directly ends with shuttle erroring out with "expected context switch but next schedule step is random choice".~~

This unfortunately makes shuttle kind of useless for trying to fix this bug, since I can't exercise the reported deadlock to try and debug it under gdb or something to get a stacktrace of the stuck thread.

My application mutates global states (e.g., allocators, buffer pools) and may benefit from testing with separate processes. I'm wondering if it's possible for the shuttle to support fork mode. The first step could be making the PortfolioRunner run in different processes.

Already a TODO in code: https://github.com/awslabs/shuttle/blob/4a00174db03b2ef9dc4a1e0707b94827bac15f7a/src/thread.rs#L173 This would help making shuttle::thread to be an in-place substitute to std::thread.

Shuttle complains that this test deadlocks, but in reality it doesn't:

#[test]
fn wait_timeout_deadlock() {
    check_dfs(
        || {
            let lock = Arc::new(Mutex::new(false));
            let cond = Arc::new(Condvar::new());

            let guard = lock.lock().unwrap();
            let (_guard, result) = cond.wait_timeout(guard, Duration::from_secs(1)).unwrap();
            assert!(result.timed_out());
        },
        None,
    )
}

The problem is that, while wait_timeout temporarily blocks the thread, it's not permanent, and so shouldn't count as deadlock.

We already knew that our modeling of wait_timeout wasn't complete because it doesn't test the timeout case, but this test shows the effects of such incompleteness—spurious failures.

We need to have a better notion of "blocked but can be unblocked". One cheap-ish idea would be for wait_timeout to spawn another (internal to Shuttle) "thread" that, when executed, causes the thread blocked in wait_timeout to unblock and return timeout. This would let the scheduler "naturally" decide when to trigger a timeout rather than us having to build any fancy time handling into the scheduler itself.

Added a DeterminismCheckScheduler to check functions for determinism by recording runnable tasks at each step and comparing on future iterations of the scheduler. Wraps an inner scheduler, which can be Random, RoundRobin, or PCT. Added unit tests as well.

By submitting this pull request, I confirm that my contribution is made under the terms of the Apache 2.0 license.