Engineering

The Lock Nobody Held: Deadlocking a Tokio Mutex Without Holding a Lock

By Samyak Sarnayak

The Issue

The reproducer demonstrates a deadlock scenario with one tokio mutex being used by 4 workers concurrently. There's a special PausableFuture that stops polling the inner future when it receives a signal. The code uses the current_thread flavour of tokio, which is single-threaded, though similar behavior occurs with multi-threaded runtimes.

When run, the output shows:

main acquired the lock
main released the lock
worker 0: acquired lock
worker 0: released lock
worker 0: done
worker 1: DEADLOCKED
worker 2: DEADLOCKED
worker 3: DEADLOCKED
main acquired the lock
main released the lock
worker 0: acquired lock
worker 0: released lock
worker 0: done
worker 1: DEADLOCKED
worker 2: DEADLOCKED
worker 3: DEADLOCKED
main acquired the lock
main released the lock
worker 0: acquired lock
worker 0: released lock
worker 0: done
worker 1: DEADLOCKED
worker 2: DEADLOCKED
worker 3: DEADLOCKED
main acquired the lock
main released the lock
worker 0: acquired lock
worker 0: released lock
worker 0: done
worker 1: DEADLOCKED
worker 2: DEADLOCKED
worker 3: DEADLOCKED

Both main and worker 0 have released their locks, yet other workers remain deadlocked despite no one holding the mutex.

Coffman conditions

Deadlocks typically require all four Coffman conditions to be met:

  1. Mutual exclusion: Only one process uses one resource at a time—satisfied by mutex definition.

  2. Hold and wait: One process holds a resource while waiting for another—not satisfied with only one mutex.

  3. No pre-emption: Resources must be voluntarily released—satisfied for mutex locks.

  4. Circular wait: Processes wait in a cycle—not satisfied as all workers wait for the same resource.

Since two conditions aren't met, traditional analysis suggests no deadlock should occur. Understanding Rust futures and tokio internals reveals the actual problem.

A short primer to async in Rust

Rust futures

Unlike async primitives in some languages, futures in Rust are lazy and perform no computation unless polled. The Future trait's poll method returns either Poll::Ready(_) with a return value or Poll::Pending indicating incompletion. Busy polling would be inefficient for network calls or mutex waits, so Rust uses wakers. When a future returns Poll::Pending, it registers a waker that fires once the condition is satisfied.

This design makes cancellation straightforward: dropping a future cancels it immediately.

Mutexes

Rust offers two primary mutex implementations:

  • std::sync::Mutex: A blocking mutex from the standard library. If contended, it blocks the current OS thread. Best for synchronous code; only safe in async when the guard won't be held across .await.

  • tokio::sync::Mutex: An async-aware mutex where acquiring it is lock().await. When contended, it yields instead of blocking an executor thread. Its core feature is that the guard can be held across .await points.

What causes the deadlock?

Tokio's mutex uses a custom semaphore storing a queue of waiters. For a mutex, the semaphore stores one permit. When a future finds no available permits, it gets added to the queue with a waker. Once a future releases a permit, the semaphore consults the queue and wakes one waiting future.

The sequence proceeds as follows:

  • When main acquires the lock, semaphore permits drop to 0.

  • Workers trying to poll the lock see no available permits and get added to the waiters list. Each future's waker is registered in the semaphore waiter.

  • When main releases the lock, it releases the semaphore permit and wakes the last (oldest) waiter.

  • Worker 0's future gets woken, acquires the permit and mutex guard, completes its task, and releases the mutex.

  • Worker 1's future gets woken next. However, its stopped flag is set to true. PausableFuture returns Poll::Pending when stopped, so the inner future—which holds the semaphore permit—never gets polled.

  • The permit is held forever. It can only be released if the future is polled or dropped.

The core issue is that PausableFuture violated the waker contract. "Calling wake() will result in at least one poll of the future that registered the waker." Tokio's semaphore assumes this is true; PausableFuture breaks it by returning Poll::Pending without polling its inner future.

"Pausing" a future resembles cancelling it, except the inner future is never dropped, preventing cleanup. When a future containing a semaphore permit is dropped, the permit releases. If PausableFuture dropped its inner future when self.stopped became true, it would work correctly.

So what about the Coffman conditions?

Acquiring the permit equates to acquiring the lock. Although the future never logged this, it technically holds the permit and thus the lock. The logs were misleading.

This is not actually a deadlock at all—rather, one process holds the lock forever without releasing it.

Practical Fixes

Fix 1: Don't pause futures that use a tokio mutex; stop them at safe boundaries

If a future might touch tokio::sync::Mutex, don't pause it at arbitrary points.

Instead:

  • Let futures run to completion.

  • If it's a stream, let it run until it yields the next item or result, then pause or cancel.

  • Drop the future to cancel it instead of pausing, assuming the future is cancel safe.

For the reproducer, PausableFuture is the problem. Either always poll it or drop the inner future once paused.

Fix 2: Prefer std::sync::Mutex by refactoring critical sections to avoid .await

Ask yourself: do you actually need to hold a lock across an .await?

std::sync::Mutex avoids this issue by not creating intermediate states where a mutex lock is provided but the thread cannot take it. Either the thread is blocked or has the lock. Restructuring critical sections to avoid await while holding the lock sidesteps this entire class of problems. This can be done by replacing the tokio mutex with std::sync::Mutex plus a signaling primitive like tokio::sync::Notify. Notify::notify_waiters wakes all waiting futures, not just the oldest waiter, preventing one unused permit from blocking others.

Takeaway

A tokio mutex isn't a drop-in async version of a std mutex. The waiter queue is part of the correctness story and can turn unpolled futures into what looks like a deadlock. If you need tokio::sync::Mutex, use it deliberately: minimize contention, and design cancellation or pause so tasks stop at safe boundaries.

When writing a wrapper future or stream, remember the waker contract. When a future registers a waker and it fires, the runtime polls the outermost future, eventually polling the wrapper. If your future swallows the poll without forwarding it, you'll encounter the same class of problems. Either forward every poll to the inner future or drop the inner future for cleanup. There is no safe middle ground.