Do upgradable reads block plain reads?

[matklad]

Hi! I see a behavior which I think does not match the docs, so either the docs are unclear, or there's a bug.

Here's the code that shows the behavior:

https://github.com/matklad/parking-lot-deadlock/blob/95989b3da40ed42e1ed7acba829d20b8b4319845/src/main.rs

If I run the code on my machine (linux, x86_64), I get a deadlock after a couple of hundred iterations.

I would expect that this program never deadlocks though, because, from my reading of the upgradable_read docs it follows that a read can never be blocked by a not-upgraded upgradable_read.

[matklad]

Downstream issue: salsa-rs/salsa#74.

[Amanieu]

I reproduced it with 2 threads upgrading. So what seems to have happened is this:

1. Thread A acquires and upgradable lock.
2. Thread B tries to acquire an upgradable lock, and blocks. This is normal since you can only have 1 upgradable lock at any time.
3. Thread C tries to acquire a read lock, and blocks because there is already another thread blocked waiting for a lock.

[matklad]

@Amanieu and 3 is a bug, right?

[Amanieu]

... probably. The rwlock was originally written as a task-fair rwlock, where a reader will block if there is an existing writer blocked on it. This helps prevent writer starvation. The problem is that this code was not revisited when upgradable locks were implemented.

[nikomatsakis]

Just for the record, I think I sidestepped the problem by not using upgradable reads in this particular path -- though this sounds like a pretty general flaw for upgradable reads, so maybe we should just not be using them?

[nikomatsakis]

There is one other path that still does but I could easily remove it

[nikomatsakis]

Well I suppose that there is no problem so long as Thread 1 doesn't wind up blocked on Thread 3, right @Amanieu ?

[nikomatsakis]

I opened salsa-rs/salsa#75 but maybe it is not necessary

[matklad]

Here's a slight variation of the deadlock:

matklad/parking-lot-deadlock@12945a9

Here, threads repeatedly upgrade_read/write/read the lock. What is interesting is that writers and upgraders deadlock against each other, without busy-waiting which was used in the first example.

[matklad]

Note that samples use parking-lot 0.6.*. I've checked the last one with 0.7.0, and it still deadlocks.

[Amanieu]

Ugh, upgradable locks are a pain to get right...

Your new deadlock is an actual bug, which should be fixed by 5977113.

The first one is more of a design flaw in the current rwlock implementation, where an upgradable read can in some cases block a normal read.

[Amanieu]

Also, fun fact, the bug is in the unlock path for normal reads. If you remove the assert from your example then the bug doesn't trigger.

[matklad]

Also, fun fact, the bug is in the unlock path for normal reads. If you remove the assert from your example then the bug doesn't trigger.

Yeah, I've noticed that, that's why assert is in there! Should have added this bit of info to the original comment.

Looks like salsa + rust-analyzer combo is a good stress test for parking lot! :)