Surelock: Deadlock-Free Mutexes for Rust

Surelock is a new Rust library designed to eliminate deadlocks at compile time by breaking the circular wait condition. It uses a unique dual-mechanism approach involving LockSets and hierarchical levels to ensure safety without runtime overhead.

NOTE

I hate deadlocks. Maybe you do too. Back at Fission, whenever someone would suggest a mutex we’d start a chant of “I say mutex, you say deadlock: Mutex! DEADLOCK! Mutex! DEADLOCK!“. Deadlocks lurk — perfectly invisible in code review, happy to pass CI a thousand times, then lock your system up at 3am under a request pattern that no one anticipated.

They have their own tradeoffs, but I miss TVar

s from Haskell. AFAICT there’s no way to do proper TVar

s in languages that have no way to enforce purity. We “should” prefer lock-free programming, but mutexes are very common in the Rust standard style. I often hear that actors eliminate deadlocks, but as someone who’s written her fair share of Elixir, this is 100% a lie (though they are less frequent).

Rust famously catches data races at compile time, but for deadlocks? You get a Mutex

, a pat on the back, and “good luck, babe”. There are some tools that help analyze your code that are fairly good, but I want feedback during development. I’ve been thinking about a better approach to this problem for a while, looked at a bunch of other attempts and have come up with what I hope is a decent ergonomic balance that covers many common use cases in Rust: surelock, a deadlock-freedom library. If your code compiles, it doesn’t deadlock. No Result

, no Option

, no runtime panic on the lock path. Every acquisition is either proven safe by the compiler or rejected at build time1.

WARNING

This is a pre-release. I think the core design is solid, but I wouldn’t be surprised if there are rough edges. Feedback and contributions welcome!

TL;DR

Deadlocks happen when all four Coffman Conditions occur simultaneously - Surelock breaks one of them — circular wait— using two complementary mechanisms - Same-level locks are acquired atomically in a deterministic order ( LockSet

) - Cross-level locks are acquired incrementally with compile-time ordering enforcement ( Level<N>

) - The entire public API is safe — unsafe

is confined to the raw mutex internals no_std

compatible, zero required runtime dependencies2

Why Not Just Be Careful?

The honest answer is that being careful doesn’t scale. It’s easy to shoot yourself in the foot while composing code. But wait, isn’t this the kind of thing that Rust us supposed to help us with? The borrow checker catches data races at compile time — why shouldn’t we expect the same for deadlocks?

The fundamental problem is well-understood. Coffman et al. identified four necessary conditions for deadlock back in 1971:

| Condition | Meaning | |---|---| | Mutual exclusion | At least one resource is held exclusively | | Hold and wait | A thread holds one lock while waiting for another | | No preemption | Locks can’t be forcibly taken away | | Circular wait | A cycle exists in the wait-for graph |

Break any one of these, and deadlocks become impossible. Mutual exclusion is the whole point of a mutex. Preemption introduces its own class of bugs. That leaves hold-and-wait and circular wait.

QUOTE

A language that doesn’t affect the way you think about programming is not worth knowing.

― Alan Perlis

We identified the solution space over 50 years ago(!). It’s a thorny enough problem that we have no single agreed solution, and yet mutexes are sufficiently useful that we still use them. This suggests that until something comes along that completely replaces mutexes, we’re in the domain of improving the ergonomics for using mutexes safely.

Only rarely do safety techniques exactly match safe use. Type systems somewhat famously either allow some unsound behaviour, or rule out legitimate use (sometimes both) — hence all of the effort going into making fancier type systems that can more directly match all safe uses while ruling out unsafe ones. The trick is in lining those up as closely as possible while introducing the easiest model to work with: minimal ceremony and/or easy to reason about. I would argue that we want our tools to help us to think about the problem.

The Key Metaphor

Surelock is built around a physical-world analogy: to interact with locks, you need a key. in our case, we’re going to keep that key while the mutex is in use. You only get that key back when you unlock it.

We call this a MutexKey

— a linear3 scope token. You get one when you enter a locking scope. When you call .lock()

, the key is consumed and a new one is returned alongside the guard. The new key carries a type-level record of what you’ve already locked, so the compiler knows what you’re still allowed to acquire. Try to go backwards and the code doesn’t compile.

💡 This is the core trick: by making the key a move-only value that threads through every acquisition, we get a compile-time witness of the current lock state. No global analysis, no runtime tracking — just the type checker doing what it does best.

This analogy only goes so far: MutexKey

actually grants you the ability to lock multiple mutexes together atomically. Locks in surelock may be grouped into levels to enable incremental acquisition, and locking returns an attenuated key that can lock fewer levels.

Prior Art

Two existing libraries informed the design, and I want to give them proper credit.

happylock

by botahamec introduced the key insight that a capability token combined with sorted multi-lock acquisition can prevent deadlocks. Surelock borrows this pattern directly.

Where the approaches diverge: happylock

breaks the hold-and-wait condition. When you lock through the collection, your key is consumed — you can’t go acquire more locks at all until it’s released. This is safe, but it means you MUST acquire all of your locks at once. You can’t do things like “lock the config, read which account to update, then lock that account”. In concurrent systems that need incremental acquisition, this is a real limitation — when you need incremental locks, you really need incremental locks.

happylock

also sorts locks by memory address, which is not stable across Vec

reallocations or moves. The library goes to some length to maintain address stability with unsafe

(Box::leak

, transmute

), and that unsafety propagates to the public API.

lock_tree

from Google’s Fuchsia project introduced compile-time lock ordering via a LockAfter

trait. Declare that level A comes before level B, and the compiler rejects any code that tries to acquire them in the wrong order.

Surelock extends this in a few ways: same-level multi-lock (which lock_tree

can’t express), per-instance level assignment via new_higher

, and scope-uniqueness enforcement. Surelock also deliberately drops lock_tree

’s DAG-based ordering in favour of a strict total order — more on why below.

The Dual Mechanism Design

Surelock uses two mechanisms that cover complementary cases. Neither overlaps with the other:

| Mechanism | When | Acquisition | Enforcement | |---|---|---|---| LockSet | Multiple locks at the same level | Atomic (all-or-nothing) | Runtime sort by stable ID | Levels (Level<N> ) | Locks at different levels | Incremental | Compile-time trait bounds |

Same Level: `LockSet`

Every Mutex

gets a unique, monotonically-increasing LockId

from a global AtomicU64

counter at creation time. The ID lives inside the mutex and moves with it — no address stability needed.

When you need multiple locks at the same level, LockSet

pre-sorts them by ID at construction time. Two threads requesting the same locks in opposite order both sort to the same acquisition order. No cycle can form.