surelock

Deadlock-freedom for Rust

CI License no_std

Surelock prevents deadlocks by breaking the circular-wait Coffman condition (1971) via two complementary mechanisms:

Every lock call is infallible or doesn't compile. No Result, no Option, no panic on any lock acquisition path.

Quick Start

usesurelock::{key_handle::KeyHandle,mutex::Mutex};letcounter: Mutex<u32>=Mutex::new(0);letmuthandle=KeyHandle::claim();handle.scope(|key|{let(mutguard,_key)=key.lock(&counter);*guard+=1;});

Type Lifecycle

┌ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ┐
│ Explicit multi-core
 │
│ Locksmith
 (forge) │ ┌ ─ ─ ─ ─ ─ ─ ─ ┐
│ │ │ std (default)
 ▼ │ │
│ KeyVoucher │ KeyHandle
 (deliver) │ (claim) │
└ ─ ─ ─ ─ ┼ ─ ─ ─ ─ ─ ┘ └ ─ ─ ─ ┼ ─ ─ ─ ┘
 │ │
 └────────────┬──────────┘
 │
 ▼
 MutexKey
 (scope)
 │
 ├───▶ MutexGuard(s)
 │ (access)
 ▼
 MutexKey
 (subscope)
 │
 ├───▶ MutexGuard(s)
 │ (access)
 ▼
 ...

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:

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

usesurelock::mutex::Mutex;// Default level (Level<0>), default backend (StdMutex)
letconfig: Mutex<u32>=Mutex::new(10);// Auto-incrementing level via new_higher
letaccount=Mutex::new_higher(20u32,&config);// Level<1>
lettxn=Mutex::new_higher(30u32,&account);// Level<2>
// Siblings share a level
letacct_a=Mutex::new_higher(1u32,&config);// Level<1>
letacct_b=Mutex::new_higher(2u32,&config);// Level<1>
// Multi-parent
letreconciler=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:

usesurelock::{level::NewHigher,mutex::Mutex};letconfig: Mutex<u32>=Mutex::new(10);letaccount=config.new_higher(20u32);// Level<1>
lettxn=account.new_higher(30u32);// Level<2>

Specify just the level to use the default backend: Mutex<u32, Level<3>>.

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

usesurelock::{key_handle::KeyHandle,mutex::Mutex};letmuthandle=KeyHandle::claim();handle.scope(|key|{letm: 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:

usesurelock::{key::lock_scope,mutex::Mutex};letcounter: Mutex<u32>=Mutex::new(0);lock_scope(|key|{let(mutguard,_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:

[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

Modules

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.

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.