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 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’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.
I can’t tell what they’re trying to say and it seemed to primarily be about priority inversion which is precisely impossible in the scheme outlined. This isn’t sacrificing any performance vs any other locking mechanism.
> Which of course leads to conversations like can big_lock be an RWLock, ArcSwap or such.
I’m not sure what you’re trying to say. This blog post is about a mutex type that is guaranteed to not dead lock.
And again, OP is horribly wrong on the terminology - there’s no spinning in any sane system. You ask the kernel to acquire the mutex for you if you fail and the kernel just puts your thread to sleep until the lock can be acquired. So all threads are guaranteed to be making forward progress. The ideal granularity of the locks themselves is completely irrelevant - that’s a domain-specific decision.
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.
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.
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.
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.
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.
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.
>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 :)
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.
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.
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.
84 comments
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 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.
> 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.
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.
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.
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.
> Which of course leads to conversations like can big_lock be an RWLock, ArcSwap or such.
I’m not sure what you’re trying to say. This blog post is about a mutex type that is guaranteed to not dead lock.
And again, OP is horribly wrong on the terminology - there’s no spinning in any sane system. You ask the kernel to acquire the mutex for you if you fail and the kernel just puts your thread to sleep until the lock can be acquired. So all threads are guaranteed to be making forward progress. The ideal granularity of the locks themselves is completely irrelevant - that’s a domain-specific decision.
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.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.
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.
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.
>
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 :)
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.