Surelock: Ensuring Deadlock-Free Mutex Usage in Rust

Deadlocks are a notorious problem in concurrent programming, often lurking undetected until they cause a system to freeze unexpectedly. At Fission, we humorously equated mutexes with deadlocks, highlighting their potential pitfalls. While Rust excels at catching data races at compile time, it offers little help with deadlocks, leaving developers to rely on careful coding and external tools. However, being careful doesn't scale well, and that's where Surelock comes in.

Surelock is a library designed to prevent deadlocks in Rust by breaking one of the Coffman Conditions—circular wait—through two complementary mechanisms: LockSet and Level<N>. LockSet ensures that same-level locks are acquired atomically in a deterministic order, while Level<N> enforces compile-time ordering for cross-level locks. This approach guarantees that if your code compiles, it won't deadlock, eliminating runtime panics on the lock path.

The library is built around the concept of a MutexKey, a linear scope token that manages lock acquisitions. When you call .lock(), the key is consumed and a new one is returned, keeping track of what has been locked. This ensures that the compiler can verify the safety of lock acquisitions without global analysis or runtime tracking.

Surelock's design draws inspiration from prior libraries like happylock and lock_tree. Happylock introduced the idea of capability tokens and sorted multi-lock acquisition, while lock_tree provided compile-time lock ordering. Surelock extends these ideas by allowing incremental lock acquisition and enforcing a strict total order on locks, which prevents deadlocks that could occur with a DAG-based approach.

The library is no_std compatible and requires no runtime dependencies, making it suitable for embedded systems where deadlock freedom is crucial. It also provides an escape hatch for situations where rules need to be broken, allowing developers to use unchecked locks with clear visibility in the codebase.

Surelock aims to make deadlock prevention ergonomic and intuitive, leveraging Rust's type system to make the correct usage easy and incorrect usage a compile-time error. The library is available on Codeberg and crates.io, and feedback from embedded and no_std users is particularly welcome.