Structuring shared state so it cannot deadlock

You have now wedged a program on purpose and unwedged it. That experience is the point of this article: deadlock is not something you debug your way out of after the fact. By the time it happens in production you have a process that is alive, responsive to nothing, and holding no evidence — no panic, no log line, no stack unless you thought to attach a debugger to the right box before it was restarted.

So it has to be designed out. Every rule below is one a reviewer can apply to a diff without running anything.

1. Establish a global lock order and never violate it

If a thread can hold lock A while asking for lock B, and another can hold B while asking for A, you have a cycle and eventually you will sit in it. Impose a total order on your locks and require every acquisition sequence to be increasing in that order. No cycle is then constructible.

What to order by, in decreasing order of how much you will like it later:

• an index — Vec<Mutex<T>> locked by ascending index (the transfers problem);
• a documented hierarchy — “config before session before connection”, written down next to the type definitions, not in someone’s head;
• an address — comparing Arc::as_ptr values. It works and it is total, but it is opaque at the call site and it makes reviews harder. Use it when nothing better exists.

The rule you want in the review checklist is blunt: a function that acquires two locks must make the order obvious on the page. If you cannot see it, it is not enforced.

2. Never call unknown code while holding a lock

This is the rule people break without noticing, because the call does not look like a call into someone else’s code.

fn record<T: Display>(log: &Mutex<Vec<String>>, item: &T) {
    let mut g = log.lock().unwrap();
    g.push(format!("{item}"));    // <- arbitrary user code, under our lock
}

T: Display means any fmt implementation the caller chose. It may lock something. It may lock this mutex, through some path you cannot see, and Mutex is not reentrant, so that is an immediate self-deadlock. It may panic, poisoning the lock.

The same hazard hides in every callback, every trait method on a generic parameter, every Drop impl of a value dropped inside the critical section, and every observer you invoke while holding state. Generic code is where it bites hardest, because the code you are calling has not been written yet.

Do the unknown work first, then take the lock only to publish the result:

let line = format!("{item}");            // outside
log.lock().unwrap().push(line);          // inside, and bounded

3. Keep critical sections small — but not smaller than one invariant

The first half is standard: hold the lock for as few instructions as you can, and never across I/O or join().

The second half is where careful people go wrong. Splitting one logical operation across two acquisitions is how you get the lost update:

let current = *counter.lock().unwrap();       // read, release
*counter.lock().unwrap() = current + 1;       // re-acquire, write

Two threads interleave between the release and the re-acquire and one increment vanishes. No deadlock, no panic, no data race — just a wrong number under load, which is worse because it is not reproducible.

The rule that reconciles both halves: the critical section is exactly the span over which the invariant is broken. Not longer, and never shorter.

💡if let Some(x) = *m.lock().unwrap() { .. } else { m.lock().unwrap(); } deadlocked before Rust 2024 and does not now. Does that make it safe to write? click to reveal

It compiles and runs correctly under edition 2024, which is what this course’s grader uses — the 2024 if let temporary rescoping genuinely fixed that deadlock class, and it is a good concrete argument for editions.

It is still not code to write, for two reasons.

match was not rescoped. match *m.lock().unwrap() { .. } holds the guard for the entire match, in 2024 exactly as in 2021. The asymmetry is now the live trap, and a reader scanning for “lock inside a scrutinee” has to know which construct they are looking at.

Edition is per-crate. A dependency compiled under 2021 has the old behaviour, and code moves between crates.

Bind the guard to a name, do the work, and let it drop where you can see it. Depending on scrutinee temporary lifetimes is depending on a rule most readers of your code cannot state.

4. Prefer try_lock + retry when you cannot impose an order

Sometimes the order genuinely is not available — the locks come from different subsystems, or which ones you need is data-dependent.

loop {
    let a = first.lock().unwrap();
    if let Ok(b) = second.try_lock() {
        do_work(&a, &b);
        break;
    }
    // release everything and start over
}

try_lock returns immediately with Err(TryLockError::WouldBlock) instead of waiting, so the cycle never forms — you back out rather than block. The price is livelock: two threads can retry in lockstep forever, each politely giving way. Real implementations add randomised backoff, and at that point you should ask whether the design that made ordering impossible is the actual problem.

5. Shard before you optimise the lock

When one lock is a bottleneck, the first instinct is a “faster” lock. Usually the answer is fewer threads wanting the same lock:

struct Sharded<T> { shards: Vec<Mutex<T>> }
// index by hash(key) % shards.len()

Contention falls by roughly the shard count, for no change in semantics per key. This is what dashmap is.

With one caveat that belongs in the same breath: sharding multiplies the lock-ordering hazard. An operation touching two keys now touches two locks, and you are back to rule 1 — lock shards in ascending index order, always.

6. Best of all: have no shared state

Every rule above is overhead you pay for sharing. The operations that have no lock order to get wrong are the ones with no locks:

• partition the input and give each thread a disjoint slice (thread::scope, chunks_mut);
• give the state a single owner and send it messages;
• accumulate per-thread and merge once at the end.

When you find yourself designing a lock hierarchy, it is worth one honest minute asking whether the sharing was necessary at all. Often the shared structure exists because it was convenient at the time, not because two threads genuinely need to see each other’s writes.

What std does not give you

Say this out loud so nobody discovers it under pressure:

• no reentrant mutex. Locking twice on one thread is unspecified and in practice hangs. There is no ReentrantMutex in the public API.
• no lock hierarchy checker. Nothing verifies your documented order.
• no deadlock detector. No watchdog, no cycle detection, no timeout by default. parking_lot has an optional deadlock_detection feature that reports cycles after they form; it is worth knowing about and it is not prevention.
• no lint of any kind. rustc and clippy have nothing to say about lock ordering. The lock-ordering problem in this track compiles clean under clippy -D warnings and then hangs forever.

Rust’s guarantee is precise and it is worth stating precisely: safe Rust eliminates data races. It does not eliminate deadlocks, livelocks, lost updates, or any other logic error about when things happen. Knowing exactly where the guarantee stops is what separates using the language from believing the marketing.