The Deadlock Empire: An Interactive Guide to Locks • Hacker News Board

Re: The Deadlock Empire: An Interactive Guide to Locks

#41

Post by jstimpfle » Wed, Jul 10, 2024, 9:56 AM UTC

YZF wrote: post #39

jstimpfle wrote: post #22

Earlier quoted context omitted.

That sounds good in principle but is it practical? As long as you have something to do while holding the lock, chances are that implementing that something requires calling a function. That or code duplication.

In my experience it is practical. Let's say you have a shared linked list, you take the lock in your insert function, you insert an item, you give the lock back. No function calls. Code that looks like what you describe, "implementing something that requires calling a function", tends to deadlock or be wrong. A really smart guy I worked with wrote some database driver that looked like that, it worked, except when it…

> you take the lock in your insert function, you insert an item, you give the lock back

yeah but what if "you insert an item" is literally hundreds of lines, and there are 3 layers of api functions below you? What if you need to to take other locks for example to apply backpressure / flush out data on the layers below?

> Code that looks like what you describe, "implementing something that requires calling a function", tends to deadlock or be wrong

It happens. What you do is you work hard until it's fixed.

I've digged into the filesystem layer of Linux for a while. Going through all the locking rules and making sure your fs is in line with them, that's not a lot of fun. Maybe you should tell the Linux filesystem people how to do it instead?

https://docs.kernel.org/filesystems/locking.html

> Even if the code is initially correct, inevitably someone will refactor it without realizing a lock is taken and break it.

Yup, and if there's a practical means to improve the situation with static type systems that is a net benefit, I'm all for it.

Re: The Deadlock Empire: An Interactive Guide to Locks

#42

Post by tomcam » Wed, Jul 10, 2024, 2:46 PM UTC

zbentley wrote: post #27

mrkeen wrote: post #26

Earlier quoted context omitted.

In the mainstream languages, synchronisation seems to be a means (locking code) to an end (locking data). The programmer usually does not care that only one thread can enter a method at a time - that's just the 'how'. The 'why' is that the programmer wants to reason about reads and writes in a multithreaded environment as easily as one would do in a single-threaded environment. Compare lock management to memory manag…

Channel-based programming, perhaps? From Go style to Erlang shared-nothing, those approaches offer some of the properties you’re looking for. Or maybe the holy grail hasn’t been created yet in this category: a compiler that can transform arbitrary computations or expressions of computational goals into their maximally parallel form, where locks etc. are compiler output artifacts a la assembly instructions rather than…

> Or maybe the holy grail hasn’t been created yet in this category: a compiler that can transform arbitrary computations or expressions of computational goals into their maximally parallel form…

I am not an expert at concurrency, so forgive my ignorance. If such a compiler existed, wouldn’t its purpose be defeated by external code? As in, someone provides a library whose concurrency properties are unknown.

Re: The Deadlock Empire: An Interactive Guide to Locks

#43

Post by gs17 » Wed, Jul 10, 2024, 3:55 PM UTC

It would be pretty cool to see the reverse of this too, where you get handed code and the evil scheduler is some AI actively trying to break your code, so you need to fix it (with limited tools, likely something block-based). Obviously that's a lot harder to develop, but it could be a very interesting challenge.

Re: The Deadlock Empire: An Interactive Guide to Locks

#44

Post by YZF » Wed, Jul 10, 2024, 11:06 PM UTC

jstimpfle wrote: post #41

YZF wrote: post #39

Earlier quoted context omitted.

In my experience it is practical. Let's say you have a shared linked list, you take the lock in your insert function, you insert an item, you give the lock back. No function calls. Code that looks like what you describe, "implementing something that requires calling a function", tends to deadlock or be wrong. A really smart guy I worked with wrote some database driver that looked like that, it worked, except when it…

> you take the lock in your insert function, you insert an item, you give the lock back yeah but what if "you insert an item" is literally hundreds of lines, and there are 3 layers of api functions below you? What if you need to to take other locks for example to apply backpressure / flush out data on the layers below? > Code that looks like what you describe, "implementing something that requires calling a function"…

> yeah but what if "you insert an item" is literally hundreds of lines, and there are 3 layers of api functions below you? What if you need to to take other locks for example to apply backpressure / flush out data on the layers below?

Well- that's what software engineering is about. If insert an item to a shared data structure is hundreds of lines of code I'd say there's something very wrong. You shouldn't need to take another lock to create backpressure, e.g. look at Go's concurrency model.

I think it's a bad pattern as a rule. There are always situations where you break rules. My tip was for most of the situations where you don't do that and most of the people that shouldn't do that. If you know what you're doing, you understand concurrency very well and synchronization very well, then you probably don't need this tip. You can be a very smart and experienced developer and easily create stuff with rare deadlocks that's almost impossible to debug if you're not careful. I've fixed these sorts of issues in multiple code bases.

I've never worked on the Linux filesystem so I'm not going to tell them what to do. We'll have to assume the people working on that know what they're doing, otherwise it'd be a bit scary. Given that we don't see the Linux filesystem deadlocking - probably ok.

EDIT: I've given this rule to many junior/intermediate engineers and I've used it myself so I would say it is applicable to almost any situations where you need to use locking. It results in code is thread safe and simply can't deadlock. This other deadlocking code base I worked on would have been much cleaner if this rule was applied, and it could have been applied, and then it wouldn't deadlock once a year at one random customer site and take their system down. Again, like anything software, sometimes you do things differently in different situations, but maybe the generalization of the rule is you don't just sprinkle locks willy-nilly all over the place, you need to somehow rationalize/codify how the locks and structures work together in a way that guarantees no corner cases will lead to issues. And sure at the "expert" level there are many more patterns for certain situations.