Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Reentrance deadlock #13

Open
matthew-a-thomas opened this issue Jun 26, 2022 · 2 comments
Open

Reentrance deadlock #13

matthew-a-thomas opened this issue Jun 26, 2022 · 2 comments

Comments

@matthew-a-thomas
Copy link

This code deadlocks:

https://dotnetfiddle.net/CkK674

Actually that test has been a challenge for every single async lock I currently know of, so I made my own async lock that passes. I'm not trying to plug for my own stuff on your GitHub, I'm just trying to show that it is possible and offer some direction toward a fix. Let me know if you'd like to discuss how my async lock works.

@mqudsi
Copy link
Member

mqudsi commented Jun 26, 2022

Hi Matthew,

Thanks for sharing that test case; it's a very interesting code sample.

Before we can say whether or not the test passes we would have to agree on its behavior, in particular, we'd have to agree on what constitutes a reentrant call and what doesn't.

I'm not sure that the second place you acquire the lock (where you have it annotated as "The lock is reentrant") should be considered a reentrant call. If you are using Task.Run(), I don't think it's unreasonable to consider this to be a "fork" in the async stack, since multiple calls to Task.Run() can be made in parallel without awaiting one or the other to finish. It would be dangerous to allow the mutex lock to simply go through since you would effectively have multiple (async) threads of execution running in parallel, each allowed to bypass the lock altogether.

A typical reentrance-friendly mutex allows bypassing the lock the second time on recursion/reentrance because it's guaranteed that it's the same calling context and there's no other competing activity in parallel.

So here you effectively have a typical deadlock scenario where thread A acquires the lock and waits for thread B to return, but thread B waits for the same lock before it can start its work.

If there's something I'm misunderstanding about the test case, please do clarify! I'm not trying to shut down this issue by any means and am happy to discuss this further.

@matthew-a-thomas
Copy link
Author

matthew-a-thomas commented Jun 26, 2022

Thanks for your reply, @mqudsi.

I'm glad you find it to be an interesting test case. Like I said that test has been a challenge for async locks in general.

It would be dangerous to allow the mutex lock to simply go through since you would effectively have multiple (async) threads of execution running in parallel, each allowed to bypass the lock altogether.

I think the danger which you say could hypothetically happen, does in fact happen with Flettu:

https://dotnetfiddle.net/o0c7j7

Sometimes Flettu gives a semaphore count exception. Other times the test code outputs "Not okay". Just run it a few times and you'll see what I mean.

I'm not picking on Flettu. I'm just trying to make sure we're understanding each other: is the "Not okay" case with Flettu the same danger that you're talking about?

If so, I agree that the danger is definitely real :)

But I'll also point out again that my own async lock passes this test (see second link in the OP). So the danger is avoidable. My async lock ensures that "there's no other competing activity in parallel".

I'm underscoring that the danger is avoidable because your reply uses that danger as the support to question whether the test should be considered reentrant, and to question whether "reentrance" (or whatever you call it) of this kind should be allowed.

And with that danger out of the way, I see no reason to call this test anything other than reentrant.

Of course it's not synchronously reentrant. And the kind of asynchronous "fork" that you're talking about which gives rise to the danger you mention is exactly the reason that some. people say reentrant async locks are impossible. It comes down to getting three things simultaneously:

  • Asynchronicity
  • Reentrance
  • Mutual exclusion

I think the second thing without the third thing comprises the danger you cite. And I think they are also viewed as fundamentally incompatible by other people.

But we both know they're wrong. It is possible to get all three of those at the same time :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

2 participants