Surelock: Deadlock-Free Mutexes for Rust • Hacker News Board

Re: Surelock: Deadlock-Free Mutexes for Rust

#41

Post by gsliepen » Sat, Apr 11, 2026, 8:05 PM UTC

lifis wrote: post #27

I can't understand why address instability is a problem: if a Mutex is moved, then it can't be locked (because you need to hold a borrow while locked, which impedes moving), so using addresses is perfectly fine and there is absolutely no need to use IDs. Also the fact that it doesn't detect locking the same mutex twice makes no sense: a static order obviously detects that and when locking multiple mutexes at the same…

What about mutexes living in shared memory, and each process having a different address mapping?

Re: Surelock: Deadlock-Free Mutexes for Rust

#42

Post by loeg » Sat, Apr 11, 2026, 8:10 PM UTC

gsliepen wrote: post #41

lifis wrote: post #27

I can't understand why address instability is a problem: if a Mutex is moved, then it can't be locked (because you need to hold a borrow while locked, which impedes moving), so using addresses is perfectly fine and there is absolutely no need to use IDs. Also the fact that it doesn't detect locking the same mutex twice makes no sense: a static order obviously detects that and when locking multiple mutexes at the same…

What about mutexes living in shared memory, and each process having a different address mapping?

All bets go out the window with adversarial multi-process shared memory mutexes. The other process may not even be running the same locking code.

Re: Surelock: Deadlock-Free Mutexes for Rust

#43

Post by drzaiusx11 » Sat, Apr 11, 2026, 8:17 PM UTC

lifis wrote: post #27

I can't understand why address instability is a problem: if a Mutex is moved, then it can't be locked (because you need to hold a borrow while locked, which impedes moving), so using addresses is perfectly fine and there is absolutely no need to use IDs. Also the fact that it doesn't detect locking the same mutex twice makes no sense: a static order obviously detects that and when locking multiple mutexes at the same…

Doesn't multiple lock support then not make it a mutex anymore? I thought that becomes a monitor lock instead? I forget how standardized the terminology is though, there may be leeway in the mutex definition already.

Re: Surelock: Deadlock-Free Mutexes for Rust

#44

Post by accelbred » Sat, Apr 11, 2026, 8:19 PM UTC

Most of the deadlocks I've faced are with different proccesses/devices both waiting on reads from each end of a socket/uart/etc. I've taken to putting timeouts on read calls, though then you have to deal with legitimate long request cycles timing out.

Re: Surelock: Deadlock-Free Mutexes for Rust

#45

Post by wrs » Sat, Apr 11, 2026, 8:20 PM UTC

forrestthewoods wrote: post #37

Hrm. I'm not immediately impressed by the "Level " construct. That feels like a lot of new cognitive burden. It's also not at all obvious to me that multiple levels of mutex is a common pattern? I'm not sure I've ever encountered a situation where locking Account also and always requires locking Config? Heaven help you if you have 3 or more levels. I dunno. I appreciate the opposition to "just be careful". But this f…

Lock ordering is indeed a common pattern to avoid deadlocks. I learned it in school in the 80's and MIT teaches it today. [0]

[0] https://web.mit.edu/6.005/www/fa15/classes/23-locks/#deadloc...

Re: Surelock: Deadlock-Free Mutexes for Rust

#46

Post by expede » Sat, Apr 11, 2026, 9:19 PM UTC

airstrike wrote: post #7

[flagged]

Author here! This post was human written, LLM proofread, and edited a couple times as folks pointed out broken links and minor errors when it was posted to r/rust a few days ago. As someone mentioned lower in the thread, there's a form of what is sometimes called Bay Area Standard that both very online humans and LLMs have absorbed. I find it FASCINATING that we're in an era where we have to prove our humanity, and the downstream behaviours of things like killing em-dash use in response are interesting to watch in real time. I've made the same mistake, so it's honestly difficult to tell!

Re: Surelock: Deadlock-Free Mutexes for Rust

#47

Post by vlovich123 » Sat, Apr 11, 2026, 9:20 PM UTC

jcalvinowens wrote: post #19

vlovich123 wrote: post #10

Earlier quoted context omitted.

There’s no global lock. There’s a linear MutexKey that a lock of Level >= N has to be acquired with. Aquiring it consumes MutexKey and hands you back MutexKey where Level is the N of the level you’re locking. There’s no priority inversion possible because locks can only ever be held in decreasing orders of priority - you can’t acquire a low priority lock and then a high priority lock since your remaining MutexKey won…

In the example it seems pretty clear to me that: Mutex::new(AppConfig::default()); ...is meant to be acquiring a mutex protecting some global config object, yes? That's what I'm calling a "global lock". > There’s no priority inversion possible because locks can only ever be held in decreasing orders of priority T1 T2 -- -- small_lock(); big_lock(); small_lock(); ...and now any other thread that needs big_lock() spins…

Mutex::new creates a lock, it doesn’t acquire one.

Look at the API - if big_lock and small_lock are at the same level, you would need to acquire the lock simultaneously for both locks which is accomplished within the library by sorting* the locks and then acquiring. If you fail to acquire small_lock, big lock isn’t held (it’s an all or nothing situation). This exact scenario is explained in the link by the way. You can’t bypass the “acquire simultaneously” api because you only have a key for one level

Your terminology is also off. A lock around a configuration is typically called a fine grained lock unless you’re holding that lock for large swathes of program. Global as it refers to locking doesn’t refer to visibility of the lock or that it does mutual exclusion. For example, a lock on a database that only allows one thread into a hot path operation at a time is a global lock.

* sorting is done based on global construction order grabbed at construction - there’s a singleton atomic that hands out IDs for each mutex.

Re: Surelock: Deadlock-Free Mutexes for Rust

#48

Post by gpm » Sat, Apr 11, 2026, 9:25 PM UTC

jcalvinowens wrote: post #6

The Level abstraction is a really neat way to have your cake and eat it too: you only need a consistent arbitrary order to avoid deadlocks, but the order can have performance consequences when some locks are more coarse than others. But the example seems backwards to me: unless every callsite that locks any item always locks the big global lock first (probably not true, because if you serialize all item access on a g…

> unless every callsite that locks any item always locks the big global lock first (probably not true, because if you serialize all item access on a global lock then a per-item lock serves no purpose...)

A pattern I've definitely both seen and used is

    let guard1 = datastructure_containing_the_whole_world.lock();
    let guard2 = guard1.subset_of_that_datastructure.lock();
    guard1.unlock();
    // Do expensive work
    guard2.unlock();

Which works to parallelize work so long as guard2 isn't contended... and at least ensures correctness and forward progress the rest of the time.

Re: Surelock: Deadlock-Free Mutexes for Rust

#49

Post by forrestthewoods » Sat, Apr 11, 2026, 9:34 PM UTC

wrs wrote: post #45

forrestthewoods wrote: post #37

Hrm. I'm not immediately impressed by the "Level " construct. That feels like a lot of new cognitive burden. It's also not at all obvious to me that multiple levels of mutex is a common pattern? I'm not sure I've ever encountered a situation where locking Account also and always requires locking Config? Heaven help you if you have 3 or more levels. I dunno. I appreciate the opposition to "just be careful". But this f…

Lock ordering is indeed a common pattern to avoid deadlocks. I learned it in school in the 80's and MIT teaches it today. [0] [0] https://web.mit.edu/6.005/www/fa15/classes/23-locks/#deadloc...

I'm aware.

I'd be curious to hear the authors reason to not prefer a LockSet everywhere.

Re: Surelock: Deadlock-Free Mutexes for Rust

#50

Post by expede » Sat, Apr 11, 2026, 9:39 PM UTC

Groxx wrote: post #14

> Why a Total Order, Not a DAG? > This is a deliberate design decision. lock_tree uses a DAG, which lets you declare that branches A and B are independent — neither needs to come before the other. Sounds great, but it has a subtle problem: if thread 1 acquires A then B, and thread 2 acquires B then A, and both orderings are valid in the DAG, you have a deadlock that the compiler happily approved. Would it be possible…

(Author here). Early in development I did exactly this with a macro. It was confusing when you wanted to refactor the code to change lock orders, harder to make clear error messages, and so on. Forcing the user to assign in a level means that it's clear(er?) to users what's happening, we don't need fancy (and difficult to debug) macro magic, and users can still do the linearisation themselves. That's the HOPE at least.

IMO compile time locking levels should be preferred whenever possible... but the biggest problem with compile time levels is that they, well, check at compile time. If you need to make mutexes at runtime (eg mange exclusive access to documents uploaded to a server by users) then you need to be able to safely acquire those too (provided in surelock with LockSet).