Wrapping reentrant call in a loop causes deadlock

[alekw911]

I have taken the sample from the "AsyncLock usage example" section of the documentation and added a for loop around the inner reentrant call and observed a deadlock occur

This is the sample code I used

using NeoSmart.AsyncLock;
using System.Threading.Tasks;
using System;
using System.Threading;

public class AsyncLockTest
{
    static async Task Main(string[] args)
    {
        new AsyncLockTest().Test();
        Thread.Sleep(Timeout.Infinite);
    }
    AsyncLock _lock = new AsyncLock();

    void Test()
    {
        // The code below will be run immediately (likely in a new thread)
        Task.Run(async () =>
        {
            // A first call to LockAsync() will obtain the lock without blocking
            using (await _lock.LockAsync())
            {
                // A second call to LockAsync() will be recognized as being
                // reentrant and permitted to go through without blocking.

                for(int i=0;i<100;++i)
                {
                    Console.WriteLine($"Starting iteration {i} from {Thread.CurrentThread.ManagedThreadId}");
                    using (await _lock.LockAsync())
                    {
                        Console.WriteLine($"Obtained lock for iteration {i} from {Thread.CurrentThread.ManagedThreadId}");
                        // We now exclusively hold the lock for 1 minute
                        await Task.Delay(TimeSpan.FromMilliseconds(1));
                        Console.WriteLine($"Finished work for iteration {i} from {Thread.CurrentThread.ManagedThreadId}");
                    }
                    Console.WriteLine($"Released lock for iteration {i} from {Thread.CurrentThread.ManagedThreadId}");
                }
            }
        }).Wait(TimeSpan.FromSeconds(30));

        // This call to obtain the lock is made synchronously from the main thread.
        // It will, however, block until the asynchronous code which obtained the lock
        // above finishes.
        using (_lock.Lock())
        {
            // Now we have obtained exclusive access.
            // <Safely perform non-thread-safe operation safely here>
        }
    }
}

[alekw911]

Additional information:
Trying with values of 1 and 2 in the for loop for(int i=0;i<3;++i) works fine
But when the iteration count is 3 or higher it deadlocks

Same is observed running with .net Framework 4.8 and .net Core 6.0

[mqudsi]

This is an interesting bug report, thank you for filing it. Did you run into this in the real world and then reproduce it w/ a modification to the example code?

I imagine .NET is starting new background threads to service the requests because too many tasks are being spun up, but this will need a lot of digging (and might not be solvable).

[alekw911]

Yes it was first discovered when looking into a bug in our application
Then a simpler console app was made to try to determine if it could be reproduced in a context unrelated to the application

[PolarGoose]

I have looked into this issue.
The simplified reproduction scenario from @alekw911:

using NeoSmart.AsyncLock;
namespace LockTest;
internal class Program
{
    static async Task Main(string[] args)
    {
        var _lock = new AsyncLock();
        Log($"Obtain the lock before entering the for loop");
        using (await _lock.LockAsync())
        {
            for (int i = 0; i < 100; ++i)
            {
                Log(i, "Try to obtain the lock");
                using (await _lock.LockAsync()) // <--------- The deadlock happens here at some iteration
                {
                    Log(i, "Obtained the lock. Start waiting for 1ms");
                    await Task.Delay(TimeSpan.FromMilliseconds(1));
                    Log(i, "Waiting finished.");
                }
                Log(i, "Lock released");
            }
            Log("The loop finished successfully. Release the lock");
        }
        Log("The lock is completely released. Exit the main method");
    }

    static void Log(string msg)
    {
        Console.WriteLine($"[ThreadId={Thread.CurrentThread.ManagedThreadId,-2}] {msg}");
    }

    static void Log(int iteration, string msg)
    {
        Console.WriteLine($"[i={iteration,-2},ThreadId={Thread.CurrentThread.ManagedThreadId,-2}] {msg}");
    }
}

It indeed deadlocks in 100% of cases:

[ThreadId=1 ] Obtain the lock before entering the for loop
[i=0 ,ThreadId=1 ] Try to obtain the lock
[i=0 ,ThreadId=1 ] Obtained the lock. Start waiting for 1ms
[i=0 ,ThreadId=6 ] Waiting finished.
[i=0 ,ThreadId=6 ] Lock released
[i=1 ,ThreadId=6 ] Try to obtain the lock
[i=1 ,ThreadId=6 ] Obtained the lock. Start waiting for 1ms
[i=1 ,ThreadId=10] Waiting finished.
[i=1 ,ThreadId=10] Lock released
[i=2 ,ThreadId=10] Try to obtain the lock

The code locks the mutex in one thread and unlocks it in another.
This happens because using await doesn't guarantee that the subsequent code will execute on the same thread.
Therefore, in such case NeoSmart.AsyncLock starts working as a non-reentrant lock - basically a functional equivalent of SemaphoreSlim.

This behavior explains why SemaphoreSlim doesn't support reentrancy. It's also the reason C# doesn't allow you to use the async keyword inside the lock statement, as shown below:

lock (obj)
{
    await Task.Delay(TimeSpan.FromMilliseconds(1));
}

There is a very nice discussion on StackOverflow that provides a lot of details why such deadlocks happen.

What's more concerning is that even this basic code is expected to fail:

using (await _lock.LockAsync())
{
    using (await _lock.LockAsync()) // <--- Deadlock is supposed to happen here,
                                    // because it is not guranteed that this line
                                    // will be executed in the same thread that
                                    // holds the lock.
    {

    }
}

Conclusion

• It is impossible to properly implement Asynchronous Reentrant lock in C#. There is a very good article about it Reentrant Async Lock is Impossible in C# and a discussion on Reddit
• NeoSmart.AsyncLock primitive shouldn't promise reentrancy when a user uses it with the async keyword.

[mqudsi]

I'm not relying on the task being dispatched on the same thread to enable reentrance, though. I'm using the extremely poorly documented AsyncLocal (combined with traditional same-thread detection, but that's mostly for when using AsyncLock in non-async contexts), which should be able to detect this, but it's extremely tricky.

The biggest issue is that AsyncLocal<T> doesn't really kick in when an async operation is dispatched, only when it is awaited.

AsyncLock/AsyncLock/AsyncLock.cs

Lines 26 to 32 in 0649d71

	// An AsyncLocal<T> is not really the task-based equivalent to a ThreadLocal<T>, in that
	// it does not track the async flow (as the documentation describes) but rather it is
	// associated with a stack snapshot. Mutation of the AsyncLocal in an await call does
	// not change the value observed by the parent when the call returns, so if you want to
	// use it as a persistent async flow identifier, the value needs to be set at the outer-
	// most level and never touched internally.
	private static readonly AsyncLocal<long> _asyncId = new AsyncLocal<long>();

[PolarGoose]

@mqudsi,

I'm not relying on the task being dispatched on the same thread to enable reentrance

Sorry, my bad.
However, as far as I understood, the article Reentrant Async Lock is Impossible in C# paragraph ExecutionContext describes why using AsyncLocal primitive doesn't solve the problem of reentrancy.

[mitja-p]

@alekw911 how did you fix this for your app?

[PolarGoose]

@alekw911 how did you fix this for your app?

Hello @mitja-p,
I'm not the author of this issue, but it seems that there is no fix, as I described in my previous message

What is your use case? Why do you need an async reentrant lock?

[IvanGit]

Hello! What about this async reentrant lock implementation? .NET Fiddle link

[PolarGoose]

@IvanGit,

Ok, so you are asking about the usage of ReentrantAsyncLock.
I have rewritten my reproduction scenario using it. This issue isn't reproduced using this class.

internal class Program
{
    static async Task Main(string[] args)
    {
        var asyncLock = new ReentrantAsyncLock();
        Log($"Obtain the lock before entering the for loop");
        await asyncLock.AcquireAsync(async () =>
        {
            Log($"Enter the for loop");
            for (int i = 0; i < 100; ++i)
            {
                await asyncLock.AcquireAsync(async () =>
                {
                    Log(i, "Obtained the lock. Start waiting for 1ms");
                    await Task.Delay(TimeSpan.FromMilliseconds(1));
                    Log(i, "Waiting finished.");
                });
            }
        });
    }

    static void Log(string msg)
    {
        Console.WriteLine($"[ThreadId={Thread.CurrentThread.ManagedThreadId,-2}] {msg}");
    }

    static void Log(int iteration, string msg)
    {
        Console.WriteLine($"[i={iteration,-2},ThreadId={Thread.CurrentThread.ManagedThreadId,-2}] {msg}");
    }
}

[PolarGoose]

@IvanGit,

Oh, by the way, I noticed you are a creator of NuExt.System
Respect for making such a complex library work.

[alekw911]

Oh cool a different implementation, I had ended up using: https://github.com/microsoft/vs-threading/blob/main/src/Microsoft.VisualStudio.Threading/ReentrantSemaphore.cs