lifis24 minutes ago
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.
Guvante16 minutes ago
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.
jcalvinowens2 hours ago
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
vlovich1232 hours ago
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.
jcalvinowensan hour ago
In the example it seems pretty clear to me that:
Mutex::new(AppConfig::default());
> 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
If small_lock() is never ever acquired without acquiring big_lock() first, small_lock serves no purpose and should be deleted from the program.
bonzinian hour ago
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.
vlovich1232 hours ago
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.
EffCompute39 minutes ago
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.
Groxx2 hours ago
>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 :)
electromechan hour ago
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.
cbarrick4 minutes ago
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.
cptroot3 hours ago
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
eru3 hours ago
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-shape3 hours ago
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.
eru2 hours ago
> Luckily, there are some individuals who move between communities without effort, [...]
Oh, many of these travelers spend a lot of effort!
01HNNWZ0MV43FF2 hours ago
It's discovery and communication. Public education for adults is way under-appreciated in many many scopes.
jandrewrogersan hour ago
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.
hackingonempty38 minutes ago
It is a big reason why I picked Scala3/Zio over Rust for my most recent project.
twoodfin2 hours ago
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-...
vlovich1232 hours ago
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.
airstrike2 hours ago
I'd read this, but I can't stomach this ChatGPT voice. It's absolutely grating.
Groxxan hour ago
tbh I'm not getting GPT-voice from this
IshKebab3 minutes ago
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.
ericban hour ago
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.
LtdJorge32 minutes ago
[dead]
PaulDavisThe1st2 hours ago
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.
altairprime2 minutes ago
[delayed]
IshKebab6 minutes ago
> 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.
CyberDildonics2 hours ago
They write like the worst possible person. It's terrible and obnoxious, there is no reason to put up with it.
0x1ceb00da2 hours ago
What is the "graph" view on the right side?
rowanG077an hour ago
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.