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
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.
...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.
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.
If big lock and little lock are at different levels you won’t have a key at the appropriate level to create an inversion by trying to acquire in the first place.
T2 might “spin” waiting for small lock but assuming small lock is released at some point you’ve not got a deadlock (and by construction it’s impossible for small lock to have it’s release blocked on the acquisition of a lock that depends on big_lock).
That’s the whole point of having a level to the locks and to the key that you have to give up to acquire that lock.
Your terminology is also off. Mutexes are not implemented through spin locks. It’s an atomic operation and when lock acquisition fails you call futex_lock (or whatever your OS api is) to have the thread be put to sleep until the lock is acquired.
I think what they're trying to say is that sure it's deadlock-free but it might be sacrificing performance.
T2 sits there waiting for small_lock to be available while holding big_lock for a long time.
This bit:
> ...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.
Which of course leads to conversations like can big_lock be an RWLock, ArcSwap or such.
This reply is word salad that completely fails to engage with anything I've actually said to you... please don't waste my time with more LLM generated comments.
None of it is LLM generated. You seem to fundamentally not understand how the system outlined in the blog post works and how it prevents deadlocks by construction (ie it’s impossible to write any program that deadlocks if the only mutexes used are from this library). You also seem to lack the appropriate terminology to describe what your concern is and use terminology in a way that belies either ignorance or fundamental misunderstanding of what words mean. So you lash out claiming my 100% human written comment is LLM as a way to distract from said ignorance.
I’ve tried to illuminate your ignorance for you but unfortunately I can’t do your thinking for you.
What I can do is recommend you try to write out the scenario you believe can create a deadlock and maybe then you’ll understand why it’s not possible and maybe my words will make a little bit more sense. If alternatively you succeed you can open an issue on the author’s open source library and create a blog post explaining their mistake. But until then you’re just unhappy you don’t understand and aren’t doing any being willful to remain uninformed.
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.
> 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.
Agreed! But if you can reverse the acquire order, you can structure the function scopes such that you don't need the explicit unlock() calls, which is a bit nicer IMHO.
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.
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.
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.
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.
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.
I've had this thought myself too. Going off on a slight tangent: I think there's also loads of useful stuff in domains like either of these which maps amazingly well to AI agent system design, but there's such a huge discrepancy between the knowledge bases of the fields that no benefit ever really surfaces.
(Speaking from the perspective of someone who simultaneously loves high-performance compute and agentic AI haha)
> 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.
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.
Haskell still needs TVar and it’s not an imperative language with unrestricted side effects. I think it’s bounded vs unbounded. Side effects make it more complicated perhaps but it sounds like even in a JIT language you could have done it.
It's possible (I've done it) in C++ but there are huge footguns that I'm still ambivalent about. I agree that the bounded/unbounded distinction is the key: data must explicitly be tagged as transactional. One of the benefits of bootstrapping an STM from an existing DB as I did is that this explicitness is already present.
I think it is pretty sad how there are so many modern programming languages coming out that fail to actually do something novel.
The primary advantage of a new programming language is that there is no legacy code to be compatible with. The software ergonomics space has been thoroughly explored, but restricting programs to subsets with useful properties is still an untapped field. It's seen that way because professional programmers are not used to dealing with restrictions to expressive freedom. New languages are supposed to increase freedom.
The vast majority of new programming languages would benefit from the main language being as restricted as possible and then require you to opt into the features selectively.
> The primary advantage of a new programming language is that there is no legacy code to be compatible with.
Depends a lot on what you are doing. Clojure and Scala were new languages, but they had a lot of legacy code to stay compatible with. C++ falls in a similar camp.
Well, in a sense other languages opt-in to TM code by interfacing with a relational database. Similar to how in Haskell you put TVar in front of the relevant bits to opt-in.
In Haskell it's just more economic and better integrated with the rest of the language and its typesystem.
Well, Haskell is a big language with lots of different aspects.
To nicely support TVars, it's good if your language can differentiate between pure code and code with side-effects. Haskell's type system is one way to get there; but eg something like Rust could probably also be coerced to do something appropriate.
Apart from that, you probably don't even need static typing to make it work well enough (though it probably helps). You definitely don't need laziness or Haskell's love of making up new operators or significant whitespace.
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
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.
> Overall it seems like the authors are weirdly both quite competent and very incompetent
This is an unusually hostile take.
The authors comment about address instability is only a minor point in the article:
> happylock also sorts locks by memory address, which is not stable across Vec reallocations or moves.
…specifically with regard to happylock, which has a bunch of commentary on it (1) around the design.
You're asserting this is a problem that doesn't exist in general, or specifically saying the author doesn't know what they're talking about with regard to happylock and vecs?
Anyway, saying they're not competent feels like a childish slap.
This is a well written article about a well written library.
Its easy to make a comment like this without doing any research or actually understanding whats been done, responding to the title instead of the article.
Specifically in this regard, why do you believe the approach taken here to overcome the limitations of happylock has not been done correctly?
> Also the fact that it doesn't detect locking the same mutex twice
Reentrant mutexes https://en.wikipedia.org/wiki/Reentrant_mutex need interior mutability in Rust, i.e. you'd need something like ReentrantMutex<RefCell<T>>. You can't just lock the mutex and get a &mut T out of it, because then locking the mutex again would get you a second &mut T which would violate Rust's no-aliasing semantics for &mut. The Rust standard library AIUI does not provide this yet.
If I need to grab 100 locks, they are all moving around a lot, but I've got the first 10, will the order be the same for someome trying to get the same 100? Eg maybe someone swaps two that neither of us has grabbed yet.
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.
That's an easy answer, but multi-process mutexes are supported on Linux (and perhaps other OSes as well), and it would be nice if this could also be safely handled by something like Surelock. If it would, then it couldn't rely on VM addresses to order locks.
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.
I have anecdata from my gamedev work that people tend to make mistakes when threads are pinned to some CPUs. Normally, when only time is a variable people can understand what can happen in their code. What confuses them is that space where those threads execute can be already taken. If a thread that should make whole system progress fails to grab a time slice these deadlocks are hard to reason about. Granted that lock ordering is the basic technique and if system did not had it all bets are off.
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.
(Author here) it depends on your use case. If you need to incrementally acquire locks, then levels are helpful -- you can't do that with LockSets on their own. A place where this comes up is if you need to read a value out of one lock, and pick what to lock next based on that without releasing the first one, and then modify both. Of course you should think twice when doing this but when you need it, you REALLY need it.
Opting out of lock levels was a design goal. By default all locks are are Level1, so the level can be omitted thanks to the default type parameter filling it in for you. Levels have no runtime cost, so sidestepping them is free. This lets you live in an atomic-locks only world if you want, and if you later find that you need incremental locks, you can add more levels at that time :)
[EDIT: fixing autocorrect typos when I got back to my laptop]
>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 :)
(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).
I can definitely believe explicit levels has more actionable errors. Type-shenaniganry without identifiable names can be pretty awful to unravel.
On that note though, I haven't found a whole lot of documentation or blog posts around trying to make better errors in macros or other compile-time checks. Have you looked at that/do you know of any decent detailed sources? I haven't looked too hard yet, but also I just don't have any good place to start, and Google's kind of garbage at the moment.
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.
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.
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...
> I was fighting deadlocks in some Java code this week
Why? You have java.util.concurrent; you should never see a deadlock. You might see a performance degradation or maybe even livelock, but that's very, very, very rare.
What abjectly idiotic thing is in your Java codebase such that you have deadlocks?
I must've been a lucky one. I develop software since 80s. Went from directly entering machine codes and up to enterprise middleware, backends and various device control and multimedia game like systems. In all my life I've only had a single case of deadlock. But it cost me more than 24 hours no sleep marathon trying to nail it down. It was related to communication between my custom Directshow filters and threads in a main software.
How do you statically guarantee the order of lock acquisition for a thread? I think either you have simple enough control flow that it is somehow entirely visible to the compiler or you need to embed the order into the type system like this approach does.
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.
If you can get a stack trace of the process it is usually pretty easy to figure you will see two or more threads waiting on different futexes. I would say async deadlocks are far trickier to debug - task a sends a message to task b and task b sends a message to task a. Both tasks wait on processing further messages until the other side replies to their message. At the end of the day you need strict ordering of who is allowed to call into the other and block.
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!
I use em dashes a lot and I'm chronically online, so that defense doesn't apply here.
It's things like "perfectly invisible in code review, happy to pass CI a thousand times, then lock your system up at 3am under a request pattern that no one anticipated." which are a dead tell it was written by ChatGPT
I'll bet you 2 beers the LLM you used to proofread the post was indeed ChatGPT.
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.
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.
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.
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!
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.
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
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.
In the example it seems pretty clear to me that:
...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
...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.
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.
No, the entire point of what I was saying is that big_lock and little_lock are at two different levels.
If big lock and little lock are at different levels you won’t have a key at the appropriate level to create an inversion by trying to acquire in the first place.
T2 might “spin” waiting for small lock but assuming small lock is released at some point you’ve not got a deadlock (and by construction it’s impossible for small lock to have it’s release blocked on the acquisition of a lock that depends on big_lock).
That’s the whole point of having a level to the locks and to the key that you have to give up to acquire that lock.
Your terminology is also off. Mutexes are not implemented through spin locks. It’s an atomic operation and when lock acquisition fails you call futex_lock (or whatever your OS api is) to have the thread be put to sleep until the lock is acquired.
I think what they're trying to say is that sure it's deadlock-free but it might be sacrificing performance.
T2 sits there waiting for small_lock to be available while holding big_lock for a long time.
This bit:
> ...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.
Which of course leads to conversations like can big_lock be an RWLock, ArcSwap or such.
This reply is word salad that completely fails to engage with anything I've actually said to you... please don't waste my time with more LLM generated comments.
None of it is LLM generated. You seem to fundamentally not understand how the system outlined in the blog post works and how it prevents deadlocks by construction (ie it’s impossible to write any program that deadlocks if the only mutexes used are from this library). You also seem to lack the appropriate terminology to describe what your concern is and use terminology in a way that belies either ignorance or fundamental misunderstanding of what words mean. So you lash out claiming my 100% human written comment is LLM as a way to distract from said ignorance.
I’ve tried to illuminate your ignorance for you but unfortunately I can’t do your thinking for you.
What I can do is recommend you try to write out the scenario you believe can create a deadlock and maybe then you’ll understand why it’s not possible and maybe my words will make a little bit more sense. If alternatively you succeed you can open an issue on the author’s open source library and create a blog post explaining their mistake. But until then you’re just unhappy you don’t understand and aren’t doing any being willful to remain uninformed.
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.
> 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".
You could certainly have a global lock at the top-most level, but you're not required to. The example is just an example.
> 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
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.Agreed! But if you can reverse the acquire order, you can structure the function scopes such that you don't need the explicit unlock() calls, which is a bit nicer IMHO.
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.
An example of this is Linux adopting wait-die locks:
https://docs.kernel.org/locking/ww-mutex-design.html
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.
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.
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.
> Luckily, there are some individuals who move between communities without effort, [...]
Oh, many of these travelers spend a lot of effort!
It's discovery and communication. Public education for adults is way under-appreciated in many many scopes.
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.
I've had this thought myself too. Going off on a slight tangent: I think there's also loads of useful stuff in domains like either of these which maps amazingly well to AI agent system design, but there's such a huge discrepancy between the knowledge bases of the fields that no benefit ever really surfaces.
(Speaking from the perspective of someone who simultaneously loves high-performance compute and agentic AI haha)
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-...
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.
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.
Haskell still needs TVar and it’s not an imperative language with unrestricted side effects. I think it’s bounded vs unbounded. Side effects make it more complicated perhaps but it sounds like even in a JIT language you could have done it.
It's possible (I've done it) in C++ but there are huge footguns that I'm still ambivalent about. I agree that the bounded/unbounded distinction is the key: data must explicitly be tagged as transactional. One of the benefits of bootstrapping an STM from an existing DB as I did is that this explicitness is already present.
> unbounded TM is likely a fool’s errand
It's the whole language, not just the TM code. Other languages have no way of opting out of the TM code, whereas Haskell does.
I think it is pretty sad how there are so many modern programming languages coming out that fail to actually do something novel.
The primary advantage of a new programming language is that there is no legacy code to be compatible with. The software ergonomics space has been thoroughly explored, but restricting programs to subsets with useful properties is still an untapped field. It's seen that way because professional programmers are not used to dealing with restrictions to expressive freedom. New languages are supposed to increase freedom.
The vast majority of new programming languages would benefit from the main language being as restricted as possible and then require you to opt into the features selectively.
> The primary advantage of a new programming language is that there is no legacy code to be compatible with.
Depends a lot on what you are doing. Clojure and Scala were new languages, but they had a lot of legacy code to stay compatible with. C++ falls in a similar camp.
Well, in a sense other languages opt-in to TM code by interfacing with a relational database. Similar to how in Haskell you put TVar in front of the relevant bits to opt-in.
In Haskell it's just more economic and better integrated with the rest of the language and its typesystem.
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
It is a big reason why I picked Scala3/Zio over Rust for my most recent project.
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!
Here is a C++ STM based on the Haskell STM API:
https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n44...
Well, Haskell is a big language with lots of different aspects.
To nicely support TVars, it's good if your language can differentiate between pure code and code with side-effects. Haskell's type system is one way to get there; but eg something like Rust could probably also be coerced to do something appropriate.
Apart from that, you probably don't even need static typing to make it work well enough (though it probably helps). You definitely don't need laziness or Haskell's love of making up new operators or significant whitespace.
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
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.
> Overall it seems like the authors are weirdly both quite competent and very incompetent
This is an unusually hostile take.
The authors comment about address instability is only a minor point in the article:
> happylock also sorts locks by memory address, which is not stable across Vec reallocations or moves.
…specifically with regard to happylock, which has a bunch of commentary on it (1) around the design.
You're asserting this is a problem that doesn't exist in general, or specifically saying the author doesn't know what they're talking about with regard to happylock and vecs?
Anyway, saying they're not competent feels like a childish slap.
This is a well written article about a well written library.
Its easy to make a comment like this without doing any research or actually understanding whats been done, responding to the title instead of the article.
Specifically in this regard, why do you believe the approach taken here to overcome the limitations of happylock has not been done correctly?
(1) - https://github.com/botahamec/happylock
A HN comment cherry-picking a sentence? No way!
> Also the fact that it doesn't detect locking the same mutex twice
Reentrant mutexes https://en.wikipedia.org/wiki/Reentrant_mutex need interior mutability in Rust, i.e. you'd need something like ReentrantMutex<RefCell<T>>. You can't just lock the mutex and get a &mut T out of it, because then locking the mutex again would get you a second &mut T which would violate Rust's no-aliasing semantics for &mut. The Rust standard library AIUI does not provide this yet.
> Also the fact that it doesn't detect locking the same mutex twice makes no sense
This was prevented on Apr 6:
https://codeberg.org/expede/surelock/commit/4f86b1ea58c7d19a...
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.
If I need to grab 100 locks, they are all moving around a lot, but I've got the first 10, will the order be the same for someome trying to get the same 100? Eg maybe someone swaps two that neither of us has grabbed yet.
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.
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.
That's an easy answer, but multi-process mutexes are supported on Linux (and perhaps other OSes as well), and it would be nice if this could also be safely handled by something like Surelock. If it would, then it couldn't rely on VM addresses to order locks.
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.
Putting timeouts on things that used to deadlock upgrades you to the next level of hell: livelocks.
I have anecdata from my gamedev work that people tend to make mistakes when threads are pinned to some CPUs. Normally, when only time is a variable people can understand what can happen in their code. What confuses them is that space where those threads execute can be already taken. If a thread that should make whole system progress fails to grab a time slice these deadlocks are hard to reason about. Granted that lock ordering is the basic technique and if system did not had it all bets are off.
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.
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.
(Author here) it depends on your use case. If you need to incrementally acquire locks, then levels are helpful -- you can't do that with LockSets on their own. A place where this comes up is if you need to read a value out of one lock, and pick what to lock next based on that without releasing the first one, and then modify both. Of course you should think twice when doing this but when you need it, you REALLY need it.
Opting out of lock levels was a design goal. By default all locks are are Level1, so the level can be omitted thanks to the default type parameter filling it in for you. Levels have no runtime cost, so sidestepping them is free. This lets you live in an atomic-locks only world if you want, and if you later find that you need incremental locks, you can add more levels at that time :)
[EDIT: fixing autocorrect typos when I got back to my laptop]
Interesting example. Thanks for reply!
>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 :)
(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).
I can definitely believe explicit levels has more actionable errors. Type-shenaniganry without identifiable names can be pretty awful to unravel.
On that note though, I haven't found a whole lot of documentation or blog posts around trying to make better errors in macros or other compile-time checks. Have you looked at that/do you know of any decent detailed sources? I haven't looked too hard yet, but also I just don't have any good place to start, and Google's kind of garbage at the moment.
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.
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.
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...
> I was fighting deadlocks in some Java code this week
Why? You have java.util.concurrent; you should never see a deadlock. You might see a performance degradation or maybe even livelock, but that's very, very, very rare.
What abjectly idiotic thing is in your Java codebase such that you have deadlocks?
I must've been a lucky one. I develop software since 80s. Went from directly entering machine codes and up to enterprise middleware, backends and various device control and multimedia game like systems. In all my life I've only had a single case of deadlock. But it cost me more than 24 hours no sleep marathon trying to nail it down. It was related to communication between my custom Directshow filters and threads in a main software.
I'm not a rust expert, but couldn't this be solved like memory safety? A few checks here and there.
How do you statically guarantee the order of lock acquisition for a thread? I think either you have simple enough control flow that it is somehow entirely visible to the compiler or you need to embed the order into the type system like this approach does.
What is the "graph" view on the right side?
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.
If you can get a stack trace of the process it is usually pretty easy to figure you will see two or more threads waiting on different futexes. I would say async deadlocks are far trickier to debug - task a sends a message to task b and task b sends a message to task a. Both tasks wait on processing further messages until the other side replies to their message. At the end of the day you need strict ordering of who is allowed to call into the other and block.
[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!
I use em dashes a lot and I'm chronically online, so that defense doesn't apply here.
It's things like "perfectly invisible in code review, happy to pass CI a thousand times, then lock your system up at 3am under a request pattern that no one anticipated." which are a dead tell it was written by ChatGPT
I'll bet you 2 beers the LLM you used to proofread the post was indeed ChatGPT.
Then you owe me two beers; I use Opus
tbh I'm not getting GPT-voice from this
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.
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.
[dead]
[dead]
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.
> 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.
They write like the worst possible person. It's terrible and obnoxious, there is no reason to put up with it.
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.
> 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!
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.
> Please don't post shallow dismissals, especially of other people's work. A good critical comment teaches us something.