# surelock > Deadlock-freedom for Rust [![CI](https://ci.hel.subduction.keyhive.org/api/badges/expede/surelock/status.svg)](https://ci.hel.subduction.keyhive.org/repos/expede/surelock) [![License](https://img.shields.io/badge/license-MIT%2FApache--2.0-blue)](LICENSE-MIT) [![no_std](https://img.shields.io/badge/no__std-compatible-green)](https://docs.rs/surelock) Surelock prevents deadlocks by breaking the _circular-wait_ [Coffman condition][coffman] (1971) via two complementary mechanisms: | Mechanism | Granularity | Acquisition | Enforcement | Description | |------------|-------------|-------------|-----------------|------------------------------------------------------------------| | `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 = Mutex::new(0); let mut handle = KeyHandle::claim(); handle.scope(|key| { let (mut guard, _key) = key.lock(&counter); *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) ▼ ... ``` | Type | Role | Created by | |--------------|-------------------------------------------|-----------------------------------------------------| | `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` 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 = 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 = 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>`. ### Key Patterns ```rust // Enter a scope handle.scope(|key| { /* ... */ }); // Lock (single mutex or LockSet, guards returned) 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 let (result, key) = key.subscope(|inner_key| { /* ... */ }); ``` ## Scope Entry Two ways to enter a lock scope: **`KeyHandle`** (recommended) -- static nesting prevention via `&mut self`. Works on all targets including `no_std`: ```rust use surelock::{key_handle::KeyHandle, mutex::Mutex}; let mut handle = KeyHandle::claim(); handle.scope(|key| { let m: Mutex = Mutex::new(42); let (val, _key) = key.lock_with(&m, |g| *g); assert_eq!(val, 42); }); // Sequential scopes are fine handle.scope(|key| { /* fresh key */ }); // Nesting is a compile error: // handle.scope(|key1| { // handle.scope(|key2| { ... }); // ^^^^ error: already mutably borrowed // }); ``` **`lock_scope` / `try_lock_scope`** (`std`-only) -- ambient convenience with runtime nesting check: ```rust use surelock::{key::lock_scope, mutex::Mutex}; let counter: Mutex = 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` 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 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 | Feature | Default | Description | |--------------------|---------|-------------------------------------------------------------------------| | `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 | Module | Key Types | Description | |---------------|--------------------------------------------|-----------------------------------------| | `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`, `IsLevel`, `LockAfter`, `Base` | Numbered levels, ordering traits | | `locksmith` | `Locksmith` | Factory for `KeyVoucher`s | | `mutex` | `Mutex`, `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` 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