# surelock
> Deadlock-freedom for Rust
[](https://ci.hel.subduction.keyhive.org/repos/expede/surelock)
[](LICENSE-MIT)
[](https://docs.rs/surelock)
Surelock prevents deadlocks by breaking the _circular-wait_ [Coffman condition][coffman] (1971) via two complementary mechanisms:
| `LockSet` | Fine | Atomic | By construction | Multiple locks acquired at once, sorted by monotonic `LockId` |
| Levels | Coarse | Incremental | Compile-time | `LockAfter` trait bounds on a consumed-and-re-emitted `MutexKey` |
Every lock call is infallible or doesn't compile. No `Result`, no `Option`, no panic on any lock acquisition path.
## Quick Start
```rust
use surelock::{key_handle::KeyHandle, mutex::Mutex};
let counter: Mutex<u32> = Mutex::new(0);
let mut handle = KeyHandle::claim();
*guard += 1;
});
```
## Type Lifecycle
```text
┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐
│ Explicit multi-core
│
│ Locksmith
(forge) │ ┌ ─ ─ ─ ─ ─ ─ ─ ┐
│ │ │ std (default)
▼ │ │
│ KeyVoucher │ KeyHandle
(deliver) │ (claim) │
└ ─ ─ ─ ─ ┼ ─ ─ ─ ─ ─ ┘ └ ─ ─ ─ ┼ ─ ─ ─ ┘
│ │
└────────────┬──────────┘
│
▼
MutexKey
(scope)
│
├───▶ MutexGuard(s)
│ (access)
▼
MutexKey
(subscope)
│
├───▶ MutexGuard(s)
│ (access)
▼
...
```
| `Locksmith` | Factory, issues vouchers (singleton) | `Locksmith::new(limit)` |
| `KeyVoucher` | Transferable token (`Send`) | `Locksmith::issue()` |
| `KeyHandle` | Per-thread scope creator (`!Send`) | `KeyHandle::claim()` or `KeyVoucher::redeem()` |
| `MutexKey` | Per-scope lock token, consumed/re-emitted | `handle.scope(\|key\| ...)` |
| `MutexGuard` | RAII access to protected data | `key.lock()` or `key.lock_with()` |
## How It Works
### `LockSet`: Fine-Grained, Implicitly Runtime Sorted
When you need multiple locks at the _same level_, `LockSet` handles it. Each `Mutex` gets a unique, monotonic `LockId` at creation. `LockSet` pre-sorts by these IDs and acquires in that order, every time. The below is an exaggerated timeline to help explain how these locks work:
```text
Thread A Thread B
│ │
▼ ▼
LockSet::new((&acct_1, &acct_2)) LockSet::new((&acct_2, &acct_1))
│ │
▼ ▼
sorted: [acct_1, acct_2] sorted: [acct_1, acct_2]
│ │
├─ takes acct_1 lock │
│ ├─ waits for acct_1 lock
├─ takes acct_2 lock │
│ │
~~~~~~~~~~~~~~~~~~~~~~~TIME PASSES~~~~~~~~~~~~~~~~~~~~~~~
│ │
├─ release acct_2 │
│ │ (still waiting for lock 1 first)
├─ release acct_1 │
│ ├─ takes acct_1 lock
│ ├─ takes acct_2 lock
│ │
▼ ▼
OK OK (no cycle possible)
```
### Levels: Coarse-Grained, Compile-Time Ordered
Use `Level<N>` types with semantic aliases:
```rust
use surelock::level::Level;
type Config = Level<0>;
type Account = Level<1>;
type Transaction = Level<2>;
```
The `MutexKey` tracks which level you've reached, and the compiler rejects backwards acquisition.
### Mutex Construction
```rust
use surelock::mutex::Mutex;
// Default level (Level<0>), default backend (StdMutex)
let config: Mutex<u32> = Mutex::new(10);
// Auto-incrementing level via new_higher
let account = Mutex::new_higher(20u32, &config); // Level<1>
let txn = Mutex::new_higher(30u32, &account); // Level<2>
// Siblings share a level
let acct_a = Mutex::new_higher(1u32, &config); // Level<1>
let acct_b = Mutex::new_higher(2u32, &config); // Level<1>
// Multi-parent
let reconciler = Mutex::new_higher(0u32, (&acct_a, &txn));
// max(Level<1>, Level<2>) + 1 = Level<3>
```
Method syntax is also available via the [`NewHigher`] trait -- especially
useful with `Arc` and custom backends where the backend is inherited
from the parent:
```rust
use surelock::{level::NewHigher, mutex::Mutex};
let config: Mutex<u32> = Mutex::new(10);
let account = config.new_higher(20u32); // Level<1>
let txn = account.new_higher(30u32); // Level<2>
```
Specify just the level to use the default backend: `Mutex<u32, Level<3>>`.
### Key Patterns
```rust
// Enter a scope
let (guard, key) = key.lock(&mutex);
let ((ga, gb), key) = key.lock(&set);
// Lock with closure (one-shot, sorts inline)
let (val, key) = key.lock_with(&mutex, |guard| *guard);
// Nested sub-scope
```rust
use surelock::{key::lock_scope, mutex::Mutex};
let counter: Mutex<u32> = Mutex::new(0);
lock_scope(|key| {
let (mut guard, _key) = key.lock(&counter);
*guard += 1;
});
```
> [!WARNING]
> `lock_scope` / `try_lock_scope` are only available with the `std` feature. On `no_std`, use `KeyHandle` for static nesting prevention. See the crate documentation for details.
## Backend Agnostic
`Mutex<T, Lvl, R>` is generic over any `RawMutex` implementation. `Lvl` defaults to `Level<0>` (= `Base`) and `R` defaults to `StdMutex` on `std`:
```toml
[dependencies]
# std users (default -- Mutex<u32> just works)
surelock = "0.1"
# lock_api users (parking_lot, spin, etc.)
surelock = { version = "0.1", features = ["lock-api"] }
parking_lot = "0.12"
# no_std users
surelock = { version = "0.1", default-features = false, features = ["lock-api"] }
spin = { version = "0.9", features = ["lock_api", "spin_mutex"] }
```
## Feature Flags
| `std` | yes | `StdMutex` default backend, `thread_local!` scope check |
| `atomic-u64` | yes | Use `AtomicU64` for `LockId` (default `AtomicU32` otherwise) |
| `lock-api` | no | Blanket `RawMutex` impl for any `lock_api::RawMutex` backend |
| `escape-hatch` | no | `Mutex::unchecked_lock()` -- std-like direct lock |
| `portable-atomic` | no | Use `portable-atomic` for all atomics |
| `critical-section` | no | Enable CAS emulation via `critical-section` (implies `portable-atomic`) |
| `cortex-m` | no | Convenience: enables `critical-section` for Cortex-M targets |
| `levels-32` | no | Extend numbered levels from 16 to 32 |
| `levels-64` | no | Extend numbered levels from 16 to 64 |
## Modules
| `acquirable` | `Acquirable` | Internal trait + impls (single, tuples) |
| `id` | `LockId` | Monotonic global counter |
| `key` | `MutexKey`, `lock_scope`, `try_lock_scope` | Scope token, ambient entry points |
| `key_handle` | `KeyHandle` | Per-thread scope capability |
| `key_voucher` | `KeyVoucher` | Transferable token (`Send`) |
| `level` | `Level<N>`, `IsLevel`, `LockAfter`, `Base` | Numbered levels, ordering traits |
| `locksmith` | `Locksmith` | Factory for `KeyVoucher`s |
| `mutex` | `Mutex<T, Lvl, R>`, `MutexGuard` | Deadlock-free mutex, RAII guard |
| `raw_mutex` | `RawMutex`, `StdMutex` | Backend trait, `lock_api` adapter |
| `set` | `LockSet` | Pre-sorted lock collection |
## Prior Art
Surelock builds on ideas from two libraries:
- [`happylock`][happylock] (`botahamec`, CC0-1.0) -- Introduced the `LockCollection` pattern: a capability token (`ThreadKey`) combined with sorted multi-lock acquisition. Surelock borrows this pattern, replacing address-based ordering with a stable monotonic `LockId` counter (addresses are unstable across moves and `Vec` reallocations), dropping the `std` requirement, and removing `unsafe` from the public API.
- [`lock_tree`][lock_tree] (Google Fuchsia, BSD) -- Introduced `LockAfter<A>` traits for compile-time ordering of lock _categories_, enforced via witness-token consumption. Surelock extends this with same-level multi-lock via `LockSet` (which `lock_tree` cannot do) and makes levels opt-in with a `Base` default.
Neither library alone covers both safe dynamic multi-lock _and_ safe incremental locking. The combination -- with stable IDs and `no_std` throughout -- is surelock's contribution.
Also informed by:
- [`tracing-mutex`][tracing_mutex] -- Runtime deadlock _detection_ via dependency graph tracking.
- [`ordered-locks`][ordered_locks] -- Compile-time ordering with a fixed set of 5 levels.
Grounded in Coffman, Elphick, and Shoshani's classic [System Deadlocks][coffman_paper] (1971).
For detailed comparisons, see [design/comparison/happylock.md](design/comparison/happylock.md) and [design/comparison/lock_tree.md](design/comparison/lock_tree.md).
## Design Documents
The [design/](design/) directory contains architecture documentation, design rationale, and detailed comparisons with prior art.
## License
Licensed under either of
- [Apache License, Version 2.0](LICENSE-APACHE)
- [MIT License](LICENSE-MIT)
at your option.
[coffman]: https://en.wikipedia.org/wiki/Deadlock_(computer_science)
[coffman_paper]: https://uobdv.github.io/Design-Verification/Supplementary/System_Deadlocks-Four_necessary_and_sufficient_conditions_for_deadlock.pdf
[happylock]: https://crates.io/crates/happylock
[lock_api]: https://docs.rs/lock_api
[lock_tree]: https://crates.io/crates/lock_tree
[ordered_locks]: https://crates.io/crates/ordered-locks
[tracing_mutex]: https://crates.io/crates/tracing-mutex