surelock #

Deadlock-freedom for Rust

Surelock prevents deadlocks by breaking the circular-wait Coffman condition (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 #

use surelock::{key_handle::KeyHandle, mutex::Mutex};

let counter: Mutex<u32> = Mutex::new(0);

let mut handle = KeyHandle::claim();
handle.scope(|key| {
    let (mut guard, _key) = key.lock(&counter);
    *guard += 1;
});

For everyday use, use surelock::prelude::*; pulls in the common types, traits, and entry points (locks, KeyHandle, LockSet, levels, the NewHigher traits, and — on std — lock_scope), so you don't need to import from each module individually.

Type Lifecycle #

┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐
│ 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:

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:

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 #

use surelock::mutex::Mutex;

// Default level (Level<0>), default backend (StdMutex)
let config: Mutex<u32> = Mutex::new(10);

// `new` is generic over level + backend, and those defaults are only
// applied when the type is named -- not in positions like `Arc::new(...)`,
// which fail with `error[E0283]`. Name the type (the compiler suggests
// the turbofish), or annotate the binding:
use std::sync::Arc;
let shared = Arc::new(Mutex::<u32>::new(0));         // turbofish
let owned: Arc<Mutex<u32>> = Arc::new(Mutex::new(0)); // or annotate

// 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:

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>>.

Reader-Writer Locks #

RwLock<T, Lvl, R> participates in the same LockId-sorted ordering as Mutex and the same compile-time Level system. Mode is chosen at the call site:

use surelock::{
    key_handle::KeyHandle,
    rw_lock::{ReadLock, RwLock, WriteLock},
    set::LockSet,
};

let cache: RwLock<u32> = RwLock::new(0);

let mut handle = KeyHandle::claim();

// Single-lock convenience methods.
handle.scope(|key| {
    let (val, _key) = key.read(&cache);
    assert_eq!(*val, 0);
});
handle.scope(|key| {
    let (mut val, _key) = key.write(&cache);
    *val = 42;
});

// `ReadLock` / `WriteLock` wrappers let one `LockSet` mix modes.
let a: RwLock<u32> = RwLock::new(1);
let b: RwLock<u32> = RwLock::new(0);
let set = LockSet::new((ReadLock(&a), WriteLock(&b)));
handle.scope(|key| {
    let ((ra, mut wb), _key) = key.lock(&set);
    *wb = *ra + 10;
});

RwLocks and Mutexes share the global LockId counter, so a single LockSet can hold both:

let set = LockSet::new((&mtx, ReadLock(&rwlock)));

Non-Blocking Acquisition #

When you must not stall (real-time paths, poll-don't-wait loops, work stealing), the try_* methods acquire without blocking. On success you get the guard plus a key advanced to the lock's level; on contention you get the original key back, unchanged, so you can retry or do other work:

use surelock::{key::lock_scope, mutex::Mutex};

let queue: Mutex<u32> = Mutex::new(0);

lock_scope(|key| {
    match key.try_lock(&queue) {
        Ok((mut guard, _key)) => *guard += 1, // acquired
        Err(_key) => { /* busy -- retry, or do other work */ }
    }
});

try_read / try_write are the RwLock counterparts, and try_lock_set acquires a whole LockSet all-or-nothing (if any lock is contended, none is left held):

use surelock::{key::lock_scope, mutex::Mutex, set::LockSet};

let a: Mutex<u32> = Mutex::new(1);
let b: Mutex<u32> = Mutex::new(2);
let set = LockSet::new((&a, &b));

lock_scope(|key| {
    match key.try_lock_set(&set) {
        Ok(((ga, gb), _key)) => assert_eq!(*ga + *gb, 3),
        Err(_key) => { /* at least one lock was busy; none held */ }
    }
});

Key Patterns #

// 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);

// Reader-writer lock convenience methods
let (read_guard, key) = key.read(&rwlock);
let (write_guard, key) = key.write(&rwlock);

// 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:

use surelock::{key_handle::KeyHandle, mutex::Mutex};

let mut handle = KeyHandle::claim();

handle.scope(|key| {
    let m: Mutex<u32> = 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:

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;
});

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:

[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 #

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<N>, IsLevel, LockAfter, Base	Numbered levels, ordering traits
locksmith	Locksmith	Factory for KeyVouchers
mutex	Mutex<T, Lvl, R>, MutexGuard	Deadlock-free mutex, RAII guard
mutex::raw	RawMutex, StdMutex	Mutex backend trait, lock_api adapter
rw_lock	RwLock<T, Lvl, R>, ReadLock, WriteLock	Deadlock-free rwlock + mode wrappers
rw_lock::guard	RwLockReadGuard, RwLockWriteGuard	RAII guards (shared / exclusive)
rw_lock::raw	RawRwLock, StdRwLock	RwLock backend trait, lock_api adapter
set	LockSet	Pre-sorted lock collection

Prior Art #

Surelock builds on ideas from two libraries:

• 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 (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 -- Runtime deadlock detection via dependency graph tracking.
• ordered-locks -- Compile-time ordering with a fixed set of 5 levels.

Grounded in Coffman, Elphick, and Shoshani's classic System Deadlocks (1971).

For detailed comparisons, see design/comparison/happylock.md and design/comparison/lock_tree.md.

Examples #

Runnable examples live in examples/:

Example	What it shows
quickstart	Smallest possible surelock program — single mutex, single counter.
bank_transfers	Classic deadlock case made deadlock-free via LockSet.
rwlock_cache	Read-heavy cache: many readers, one writer.
tiered_levels	Compile-time level ordering with semantic type aliases.
mixed_lockset	Mutex + RwLock reader + RwLock writer in one LockSet.
error_handling	Walks every typed-error path and recovers from each.
multi_core	Locksmith + KeyVoucher to distribute lock scope capability to N workers.

Run any of them with cargo run --example <name> (add --release for the contention demos).

Design Documents #

The design/ directory contains architecture documentation, design rationale, and detailed comparisons with prior art.

License #

Licensed under either of

• Apache License, Version 2.0
• MIT License

at your option.