Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Surelock: Deadlock-Free Mutexes for Rust

notes.brooklynzelenka.com

Post reply on HN
Print view View original

51–60 of 90 posts

Re: Surelock: Deadlock-Free Mutexes for Rust

#51

Post by jcalvinowens »

vlovich123 wrote: post #47
jcalvinowens wrote: post #19

Earlier quoted context omitted.

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

Mutex::new creates a lock, it doesn’t acquire one. Look at the API - if big_lock and small_lock are at the same level, you would need to acquire the lock simultaneously for both locks which is accomplished within the library by sorting* the locks and then acquiring. If you fail to acquire small_lock, big lock isn’t held (it’s an all or nothing situation). This exact scenario is explained in the link by the way. You c…

No, the entire point of what I was saying is that big_lock and little_lock are at two different levels.

Re: Surelock: Deadlock-Free Mutexes for Rust

#52

Post by senderista »

eru wrote: post #2

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.

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

Re: Surelock: Deadlock-Free Mutexes for Rust

#53

Post by senderista »

vlovich123 wrote: post #15
twoodfin wrote: post #9

Earlier quoted context omitted.

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 fa…

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.

Re: Surelock: Deadlock-Free Mutexes for Rust

#54

Post by vlovich123 »

jcalvinowens wrote: post #51
vlovich123 wrote: post #47

Earlier quoted context omitted.

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 c…

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.

Re: Surelock: Deadlock-Free Mutexes for Rust

#55

Post by Seattle3503 »

Guvante wrote: post #28
lifis wrote: post #27

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

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.

Re: Surelock: Deadlock-Free Mutexes for Rust

#56

Post by expede »

forrestthewoods wrote: post #49
wrs wrote: post #45

Earlier quoted context omitted.

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]

Re: Surelock: Deadlock-Free Mutexes for Rust

#57

Post by airstrike »

expede wrote: post #46
airstrike wrote: post #7

[flagged]

Author here! This post was human written, LLM proofread, and edited a couple times as folks pointed out broken links and minor errors when it was posted to r/rust a few days ago. As someone mentioned lower in the thread, there's a form of what is sometimes called Bay Area Standard that both very online humans and LLMs have absorbed. I find it FASCINATING that we're in an era where we have to prove our humanity, and t…

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.

Re: Surelock: Deadlock-Free Mutexes for Rust

#58

Post by [deleted] »

vlovich123 wrote: post #54
jcalvinowens wrote: post #51

Earlier quoted context omitted.

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…

[deleted]

Re: Surelock: Deadlock-Free Mutexes for Rust

#59

Post by vlovich123 »

senderista wrote: post #53
vlovich123 wrote: post #15

Earlier quoted context omitted.

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 fa…

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…

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.

Re: Surelock: Deadlock-Free Mutexes for Rust

#60

Post by FpUser »

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.
Post reply on HN