[HN Gopher] Surelock: Deadlock-Free Mutexes for Rust
___________________________________________________________________
Surelock: Deadlock-Free Mutexes for Rust
Author : codetheweb
Score : 149 points
Date : 2026-04-08 17:36 UTC (3 days ago)
(HTM) web link (notes.brooklynzelenka.com)
(TXT) w3m dump (notes.brooklynzelenka.com)
| eru wrote:
| I agree with the author: it's a shame that TVars aren't catching
| on in more languages. They are a great idea from the database
| world, that we could use in the rest of computing, too.
| embedding-shape wrote:
| The entire programming (or even computing) ecosystem suffers
| from this issue where very useful ideas don't always propagate
| across domains even though they just make a whole lot of sense.
| I'm not sure if it's because they truly wouldn't work out in
| practice, or if it's just a discovery/communication thing.
|
| One thing that I think do affect things, is that language
| design discussions tend to be concentrated into their own
| communities based on the programming language itself, rather
| than one "programming language discussions" place where
| everyone can easier cross-pollinate ideas across languages.
| Luckily, there are some individuals who move between
| communities without effort, which does lead to a bit of ideas
| making it across, but it feels like we're missing out on so
| much evolution and ideas from various languages across the
| ecosystem.
| eru wrote:
| > Luckily, there are some individuals who move between
| communities without effort, [...]
|
| Oh, many of these travelers spend a lot of effort!
| 01HNNWZ0MV43FF wrote:
| It's discovery and communication. Public education for adults
| is way under-appreciated in many many scopes.
| twoodfin wrote:
| The canonical industrial explanation "why not" is probably this
| 2010 piece from Joe Duffy @ Microsoft:
|
| http://joeduffyblog.com/2010/01/03/a-brief-retrospective-on-...
| vlovich123 wrote:
| I don't think we read the same thing.
|
| > Models can be pulled along other axes, however, such as
| whether memory locations must be tagged in order to be used
| in a transaction or not, etc. Haskell requires this tagging
| (via TVars) so that side-effects are evident in the type
| system as with any other kind of monad. We quickly settled on
| unbounded transactions.
|
| Snip
|
| > In hindsight, this was a critical decision that had far-
| reaching implications. And to be honest, I now frequently
| doubt that it was the right call. We had our hearts in the
| right places, and the entire industry was trekking down the
| same path at the same time (with the notable exception of
| Haskell)
|
| So basically not that TM isn't workable, but unbounded TM is
| likely a fool's errand but Haskell's is bounded TM that
| requires explicit annotation of memory that will participate
| in atomicity.
| senderista wrote:
| Having worked a bit on a hobby STM in C++ (spun out of a DB
| startup) I would have to agree. Fully transparent STM that
| depends on a "sufficiently smart compiler" for an
| imperative language with unrestricted side effects is
| hopeless. But I do think that a much humbler version of STM
| is feasible for C++ or Rust, requiring much more explicit
| cooperation from the programmer. I haven't worked on this
| for 3 years but hope to revisit it someday.
| jandrewrogers wrote:
| The cross-fertilization of ideas across computer science
| domains is more limited than I think people assume. Databases
| are just one area that contains a lot of good ideas that never
| seem to leak into other parts of the software world.
|
| Supercomputing is another domain that has deep insights into
| scalable systems that is famously so insular that ideas rarely
| cross over into mainstream scalable systems. My detour through
| supercomputing probably added as much to my database design
| knowledge as anything I actually did in databases.
| hackingonempty wrote:
| It is a big reason why I picked Scala3/Zio over Rust for my
| most recent project.
| mamcx wrote:
| Well, what means to support, truly, TVars?
|
| Is easy, or hard?
|
| Demand a new paradigm at large, or is only a inconvenience in
| the few places is used?
|
| Because if the answer is "turns the language into Haskell" then
| is a big NOPE!
| senderista wrote:
| Intel, MSFT, IBM spent billions from about 2005-2015 trying to
| make this happen and failed miserably.
|
| https://dl.acm.org/doi/10.1145/1400214.1400228
| cptroot wrote:
| I appreciate that this appears to be an incremental improvement
| on Fuschia's tree_lock, with the sharp edges sanded off. Good
| work! I hope I won't have to use it :p
| jcalvinowens wrote:
| 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 global
| lock then a per-item lock serves no purpose...), aren't you
| begging for priority inversions by acquiring the big global lock
| before you acquire the item lock?
|
| My only gripe is missing the obvious opportunity for Ferengi
| memes ("rules of acquisition") :D :D
| vlovich123 wrote:
| There's no global lock. There's a linear MutexKey<N> that a
| lock of Level >= N has to be acquired with. Aquiring it
| consumes MutexKey<N> and hands you back MutexKey<Level+1> 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't have the right level.
| jcalvinowens wrote:
| 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(); <--- Spins waiting for T1
|
| ...and now any other thread that needs big_lock() spins
| waiting for T2 to release it, but T2 is spinning waiting for
| T1 to release the (presumably less critical) small lock.
|
| If small_lock is never ever acquired without acquiring
| big_lock first, small_lock serves no purpose and should be
| deleted from the program.
| bonzini wrote:
| Usually a global lock is a lock that is taken outside all
| others and is taken for large parts of the runtime (or
| even, everywhere the thread isn't waiting on a condition
| variable, file descriptor and the like).
|
| Mutex::new(AppConfig::default()) might very well be a
| small, leaf mutex.
| vlovich123 wrote:
| 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.
| jcalvinowens wrote:
| No, the entire point of what I was saying is that
| big_lock and little_lock are at two different levels.
| gpm wrote:
| > 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.
| airstrike wrote:
| I'd read this, but I can't stomach this ChatGPT voice. It's
| absolutely grating.
| PaulDavisThe1st wrote:
| So tired of this sort of comment. LLMs are trained using
| (primarily, generally) online material. It sounds like online
| humans, in aggregate, plus or minus a bit of policy on the part
| of the model builders.
| CyberDildonics wrote:
| They write like the worst possible person. It's terrible and
| obnoxious, there is no reason to put up with it.
| IshKebab wrote:
| > It sounds like online humans, in aggregate
|
| That's exactly the problem. It sounds like _one_ aggregate
| person. It 's quite unpleasant to read the same turns of
| phrase again and again and again, especially when it means
| that the author copped out of writing it themselves.
|
| In fairness I think in this case they mostly did write it
| themselves.
| altairprime wrote:
| > _So tired of this sort of comment._
|
| Email the mods about it rather than replying, subject
| "Accusation of AI in FP comment" or whatever. It's a
| guidelines violation to make the accusation in a comment
| rather than to them by email, and they have tools to deal
| with it!
| slopinthebag wrote:
| Nobody is making an accusation of an AI comment - people
| are pointing out that the article is at least partially AI
| generate, which does not go against any HN guidelines, and
| neither does complaining about those comments.
| slopinthebag wrote:
| Except _nobody_ writes like the aggregate, hence why it 's so
| jarring.
|
| The closest actually human style to LLM writing is obnoxious
| marketing speak. So that also sucks.
|
| So many people who are not great writers lean on LLMs to
| write, but aren't good enough to see how bad it is. They
| should be criticised for this. Either use them and be good
| enough to make it read as human, or just don't use them. No
| free lunch.
| Groxx wrote:
| tbh I'm not getting GPT-voice from this
| ericb wrote:
| I'm not either. If this was GPT-voice, I'd be happy. It's
| concise, technical, with good emphasis but no drama or AI
| tropes.
| IshKebab wrote:
| It's there in places ("The honest answer is...") but I think
| most of this is human written. They probably started with an
| AI draft I'd guess.
| macintux wrote:
| > Please don't post shallow dismissals, especially of other
| people's work. A good critical comment teaches us something.
| expede wrote:
| 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!
| vlovich123 wrote:
| I feel like Fuschia's DAG approach can still be made compile time
| lock free by either disallowing holding locks from different
| branches or requiring an ordering when that does happen to
| prevent cycles (ie you can't acquire them independently, you have
| to acquire all independent branches as a single group.
| 0x1ceb00da wrote:
| What is the "graph" view on the right side?
| Groxx wrote:
| > _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 to build one at compile time? Static levels
| seem like they won't let you share code without level-
| collaboration, so that might be kinda important for larger-scale
| use.
|
| I don't know enough about Rust's type system to know if that's
| possible though. Feels like it's pushing into "maybe" territory,
| like maybe not with just linear types but what about proc macros?
|
| I can definitely see why it's easier to build this way though,
| and for some contexts that limitation seems entirely fine. Neat
| library, and nice post :)
| expede wrote:
| (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).
| electromech wrote:
| I'm intrigued! I was fighting deadlocks in some Java code this
| week, and I'm working on a Rust project to maybe replace some of
| that.
|
| One thing I didn't see in the post or the repo: does this work
| with async code?
|
| I couldn't find the "search" button on Codeberg, and
| tests/integration.rs didn't have any async.
|
| For embedded, I have had my eye on https://github.com/embassy-
| rs/embassy (which has an async runtime for embedded) and would
| love a nice locking crate to go with it.
| cbarrick wrote:
| IIUC, this crate has similar restrictions to the std Mutex. So
| it depends on what you mean by "work with async code."
|
| First, lock acquisition seems to be a blocking method. And I
| don't see a `try_lock` method, so the naive pattern of spinning
| on `try_lock` and yielding on failure won't work. It'll still
| work in an async function, you'll just block the executor if
| the lock is contested and be sad.
|
| Second, the key and guard types are not Send, otherwise it
| would be possible to send a key of a lower level to a thread
| that has already acquired a lock of a higher level, allowing
| deadlocks. (Or to pass a mutex guard of a higher level to a
| thread that has a key of a lower level.)
|
| Therefore, holding a lock or a key across an await point makes
| your Future not Send.
|
| Technically, this is fine. Nothing about Rust async in general
| requires that your Futures are Send. But in practice, most of
| the popular async runtimes require this. So if you want to use
| this with Tokio, for example, then you have to design your
| system to not hold locks or keys across await points.
|
| This first restriction seems like it could be improved with the
| addition of an `AsyncLockable` trait. But the second
| restriction seems to me to be fundamental to the design.
| mplanchard wrote:
| Just wanted to add to your great summary a link to tokio's
| docs on which kind of mutex to use, which seem applicable to
| the mutex in TFA as well: https://docs.rs/tokio/latest/tokio/
| sync/struct.Mutex.html#wh...
|
| Also to note, regarding "future not send," that, in tokio
| codebases where the general expectation is that futures will
| be Send, enabling the clippy lint "future_not_send" is
| extremely helpful in avoiding these kinds of issues and also
| in keeping the error localized to the offending function,
| rather than it being miles away somewhere it happens to be
| getting indirectly spawned or whatever: https://rust-
| lang.github.io/rust-clippy/stable/index.html?se...
| rowanG077 wrote:
| That's pretty awesome. Dead locks are extremely tough to debug.
| There are even cases where I saw behavior in code that might have
| been a dead lock. I never found out though.
| EffCompute wrote:
| I really agree with jandrewrogers' point about the insularity of
| the database domain. While working on a custom C++ engine to
| handle 10M vectors in minimal RAM, I've noticed that many
| 'mainstream' concurrency patterns simply don't scale when cache-
| locality is your primary bottleneck.
|
| In the DB world, we often trade complex locking for deterministic
| ordering or latch-free structures, but translating those to
| general-purpose app code (like what this Rust crate tries to do)
| is where the friction happens. It's great to see more 'DB-style'
| rigour (like total ordering for locks) making its way into
| library design.
| lifis wrote:
| 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 level all you need to do is
| check for equal consecutive addresses after sorting, which is
| trivial.
|
| Overall it seems like the authors are weirdly both quite
| competent and very incompetent. This is typical of LLMs, but it
| doesn't seem ZlLM-made.
| Guvante wrote:
| Don't address introduce ambiguous locking order across
| attempts?
|
| While not obviously problematic, that seems weird enough you
| would need to validate that it is explicitly safe.
| gsliepen wrote:
| What about mutexes living in shared memory, and each process
| having a different address mapping?
| loeg wrote:
| 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.
| drzaiusx11 wrote:
| 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.
| forrestthewoods wrote:
| 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 feels to me like it's inducing bad design patterns. So it
| feels like it's wandering down the wrong path.
| wrs wrote:
| 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...
| forrestthewoods wrote:
| I'm aware.
|
| I'd be curious to hear the authors reason to not prefer a
| LockSet everywhere.
| accelbred wrote:
| 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.
___________________________________________________________________
(page generated 2026-04-11 23:00 UTC)