surelock

Deadlock-freedom for Rust

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

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

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:

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

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

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:

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

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