Re-entrant Async Lock

[timcassell]

I'm contemplating adding a ReentrantAsyncLock, which is much more complex than a non-re-entrant AsyncLock. An article discussing the difficulties of implementing a general-purpose re-entrant async lock: https://itnext.io/reentrant-recursive-async-lock-is-impossible-in-c-e9593f4aa38a.

An example of a re-entrant async lock: https://github.com/matthew-a-thomas/cs-reentrant-async-lock. This one takes advantage of the fact that Tasks capture the SynchronizationContext for each await (unless overridden with .ConfigureAwait(false)). That means it won't work with ProtoPromise because we explicitly do not capture the SynchronizationContext by default, for performance reasons (though, doing so can be forced via the .WaitAsync() API). Also, the author explicitly mentions that it does not support switching context inside the lock body, as that will break the mutual exclusion.

I think that ProtoPromise can have a re-entrant async lock with Promise cooperation. The way this will work is logically straight-forward: the lock can be "owned" by a single executing promise at a time, and when that executing promise awaits another promise, the ownership can transfer to the awaited promise to unlock the re-entrant aspect of it, then ownership transfers back when the lock is exited.

Re-entrant children promises are determined when they are awaited, not when they are called.

Example:

ReentrantAsyncLock _asyncLock = new ReentrantAsyncLock();

async Promise MainAsync()
{
    using (await _asyncLock.LockAsync())
    {
        var childPromise = ChildAsync(delay: TimeSpan.FromMilliseconds(100));
        await Task.Delay(TimeSpan.FromMilliseconds(101)).ConfigureAwait(false);
        
        NonThreadSafe();
        
        await childPromise;
    }
}
  
async Promise ChildAsync(TimeSpan delay)  
{
    await Task.Delay(delay).ConfigureAwait(false);
    
    using (await _asyncLock.LockAsync())
    {
        NonThreadSafe();
    }
}

In this example, when ChildAsync tries to enter the lock, it will block, even though it was called by the owner of the lock. The MainAsync will complete the NonThreadSafe() method, then when it awaits the childPromise, the ChildAsync promise will become the new owner of the lock, and the lock will be re-entered. Then NonThreadSafe() will run in ChildAsync (notice how it does not race with the call in MainAsync). When ChildAsync exits the lock, the ownership transfers back to the parent. The ChildAsync may attempt to re-enter the lock again after it exited, and that will work just fine, it will transfer lock ownership back to itself. (To see why it doesn't retain ownership until it is complete, see the next example).

Example 2:

ReentrantAsyncLock _asyncLock = new ReentrantAsyncLock();

async Promise MainAsync()
{
    using (await _asyncLock.LockAsync())
    {
        var childPromise = Promise.ParallelFor(0, 10, (i, token) =>
        {
            return ChildAsync(delay: TimeSpan.FromMilliseconds(100));
        });
        await Task.Delay(TimeSpan.FromMilliseconds(101)).ConfigureAwait(false);
        
        NonThreadSafe();
        
        await childPromise;
    }
}
  
async Promise ChildAsync(TimeSpan delay)  
{
    await Task.Delay(delay).ConfigureAwait(false);
    
    using (await _asyncLock.LockAsync())
    {
        NonThreadSafe();
    }
    
    LongRunning();
    
    using (await _asyncLock.LockAsync())
    {
        NonThreadSafe2();
    }
}

This time we have 10 parallel promises running concurrently, all attempting to take the lock, as well as the parent promise that has the lock. Just as the previous case, all child locks will block until the childPromise is awaited. But instead of all of the child parallel promises gaining ownership of the lock, causing a race between each other, only one promise will gain ownership of the lock at a time. When the promise that entered the lock releases it, ownership goes to one of the other parallel promises. If the same promise tries to re-enter the lock again, it will enter the lock queue and have to wait until the other promises release the lock. This way the lock is more concurrent than if the ownership is held until the parallel child promise is complete (it doesn't hold the lock for too long). When all parallel child promises have exited the lock, then the ownership transfers back to the parent. And the process repeats if they try to re-enter the lock again.

---

Pros:

• We get a re-entrant async lock with real mutual exclusion.
• Context switching is supported inside the lock body.

Cons:

• Requires cooperation from Promises, likely will slow down general Promise execution.
• This will only work with Promises, it won't work with Tasks or any other custom task-like type.
• Synchronous locking cannot be safely supported (since the child promise blocks until it is awaited, it would cause a deadlock).

@matthew-a-thomas I'm curious if you have any thoughts on this. What do you think of this approach, and are there any edge cases I missed?

[timcassell]

One thing I missed is, what if you await with cancelation?

await childPromise.WaitAsync(cancelationToken);

If the token is canceled while the lock is still held by a child, what happens? Usually, this would immediately throw and execution could continue in the parent. But that would break mutual exclusion, allowing concurrent calls to happen in 2 places.

I think this is another place where the promise has to cooperate with the lock, and wait until the lock is exited from any children before throwing/continuing.

[matthew-a-thomas]

Is there anything special about the child task/promise/future being created inside the guarded section of the locks in your examples? To put it a different way, what would you expect to happen with this code?

ReentrantAsyncLock _asyncLock = new ReentrantAsyncLock();

async Promise MainAsync()
{
  var child = ChildAsync();
  using (await _asyncLock.LockAsync())
  {
    await child;
  }
}

async Promise ChildAsync()
{
  await Task.Delay(TimeSpan.FromSeconds(1));
  using (await _asyncLock.LockAsync())
  {}
}

[timcassell]

With my implementation idea, there is no difference. That would do the same thing as the first example, it would be determined to be a child for reentrance at the await point. The lock would block until it is awaited. (In that particular case it wouldn't block at all thanks to the wait before entering the lock, though.)

[timcassell]

Actually, there would be a difference there... Without the task delay, the child would obtain the lock before the parent. Then the parent would block while the child has the lock. If the child exited the lock to allow the parent to await it, then tried to enter the lock again, it would be a reentrance.

Kind of a weird flow, but it wouldn't break mutual exclusion.

[matthew-a-thomas]

I think your idea of evaluating reentrance when awaiting is interesting. With a custom SynchronizationContext you only get to touch the continuations once they're ready to execute (perhaps long after an await keyword). But with a custom async method builder (implied by the custom awaitable type that your example methods are returning) you additionally get to touch continuations at the await points. Very interesting...

The downside that I'm seeing with that is the same downside that you pointed out: if you need that superpower, you only get it with the one magic custom async method builder... you don't get it when the method returns a Task or any other awaitable type.

But... what if the async lock's API was a little different. What if the guarded section was a delegate instead of a using block? For example:

... _asyncLock = ...;

async Task MainAsync()
{
  await _asyncLock.UseAsync(async () =>
  {
    DoNonThreadSafeStuff();
    await ChildAsync();
  });
}

async Task ChildAsync()
{
  await _asyncLock.UseAsync(async () =>
  {
    DoNonThreadSafeStuff();
  }); 
}

...and here's the signature of the UseAsync method:

public Task UseAsync(Func<Promise> guardedSection);
//                        ^^^^^^^ This is the secret sauce
//     ^^^^ I suppose any awaitable type will do here

I haven't tried turning this into code, but perhaps that would make it a little more natural for people to use your magic async method builder. They'll just create a delegate with the async keyword as I've shown above, which will feel very familiar to anyone who has used Func<Task>, and the compiler will know to wire things up using your magic async method builder.

[timcassell]

That's an interesting idea, but it wouldn't work. The only reason my idea could work with promises is because internally it is just an object tree. At await points, the child tree is wired up to the parent tree to become a larger tree (unlike some libraries that only hook up callbacks). Once the async Task is introduced, it breaks the tree. I have no way of knowing if a promise was awaited in that task, so I can't determine if the lock should allow the reentrance.

In fact, I don't even know if it was a task that was awaited, it could be any awaitable, and all I can do is hook up the completion callback. Unfortunately, that means the delegate approach doesn't do anything better than the disposable approach.

That's the biggest negative of this approach.

[matthew-a-thomas]

One final thought for my evening: I think no matter how the async lock is implemented, you're not going to be able to entirely escape the switching context problem.

For example:

async Promise MainAsync()
{
  using (await _asyncLock.LockAsync())
  {
    await Task.Run(async () =>
    {
      using (await _asyncLock.LockAsync())
      {
        // #1
      }
      await Task.Delay(1).ConfigureAwait(false);
      using (await _asyncLock.LockAsync())
      {
        // #2
      }
    });
  }
}

I can imagine how reentrance into guarded section # 1 would be allowed. Of course this example is feeding a Func<Task> to Task.Run, and we don't have any special abilities with regard to fiddling with continuations there. I believe the only option would be to rely on ExecutionContext flowing something (in an AsyncLocal) into the Task.Run delegate that says to the lock that it's okay to enter guarded section # 1.

But what about guarded section # 2? That flowing context will have been lost by the .ConfigureAwait(false). I believe it would deadlock trying to enter guarded section # 2.

Assuming that's the case, I would like to ask why it's important to be able to use .ConfigureAwait(false) within the guarded section?

[matthew-a-thomas]

Thank you for pointing out the tree-like structure of Promise, and for clarifying that you only intend to support the lock within such trees. That has helped me to better understand your focus.

With those things in mind I think your idea is feasible. I think I agree with you that the idea is conceptually simple—I can kind of feel the concept of a reentrant async lock arising out of a few simple rules applied to a tree.

You've given me an idea about regular Tasks. I'll let you know what I find when I'm done, just don't wait on me because I'm not sure when I'll get to try it out.

[timcassell]

You've given me an idea about regular Tasks. I'll let you know what I find when I'm done, just don't wait on me because I'm not sure when I'll get to try it out.

Well, now you've got me curious! Care to share the idea in its unrefined state?

[matthew-a-thomas]

Sure! But warning: it's very unrefined.

What if we could view "regular" async/await code (as in code using .Net's Task) as a similar sort of tree, and what if an async lock had the ability to put on those glasses anytime it needs to make a decision about reentrance?

Terribly powerful things are possible with reflection. And you can make reflection be very fast.

I'm imagining something entirely different than relying on the proper flow of ExecutionContext. I just don't know yet what that something will be. Perhaps reflection into the private fields of Task? Or into .Net's async method builder for that type? I really don't know.

And if times are desperate enough, did you know you can use very unsafe code to overwrite CLR's method descriptors to make any calls to DoSomething() actually go to DoSomethingElse()? And you can even do that with constructors?? And even on framework types???

I warned you!

[timcassell]

Sure! But warning: it's very unrefined.

What if we could view "regular" async/await code (as in code using .Net's Task) as a similar sort of tree, and what if an async lock had the ability to put on those glasses anytime it needs to make a decision about reentrance?

I'm listening...

Terribly powerful things are possible with reflection. And you can make reflection be very fast.

Keep in mind that compiled expressions are not available in AOT. .Net 8 is planning on having faster reflection by default.

I'm imagining something entirely different than relying on the proper flow of ExecutionContext. I just don't know yet what that something will be. Perhaps reflection into the private fields of Task? Or into .Net's async method builder for that type? I really don't know.

Interesting, whether or not it will work depends entirely on how the Tasks are implemented. And that has changed over the years. Specialized code may have to be written depending on the framework version (if you want to support multiple framework versions).

And if times are desperate enough, did you know you can use very unsafe code to overwrite CLR's method descriptors to make any calls to DoSomething() actually go to DoSomethingElse()? And you can even do that with constructors?? And even on framework types???

Are you talking about IL weaving? Actually, that sounds even more advanced than IL weaving. I am unaware of how to hijack BCL types like that. But that actually sounds like the most feasible way to get it to work, by hijacking the AsyncTaskMethodBuilder and building a tree ourselves.

[Edit] Of course, then there's the problem of C#10 added the ability for users to override the async method builder themselves...

I warned you!

😝

[matthew-a-thomas]

Yes, caveats and landmines abound!

If you want to learn more about method descriptors, here are some good starting points:

• https://github.com/dotnet/runtime/blob/main/docs/design/coreclr/botr/method-descriptor.md
• https://www.google.com/search?q=c%23+replace+method+at+runtime

I think the cost of such an approach would be incredibly high. But this is R&D, not accounting!

[timcassell]

After some more thought, I think it's too easy to break, so it's not worth the effort. Even a method as simple as this would break the tree:

public Promise Func()
{
    var deferred = Promise.NewDeferred();
    Func2()
        .ContinueWith(resultContainer =>
        {
            if (resultContainer.State == Promise.State.Resolved)
                deferred.Resolve();
            else if (resultContainer.State == Promise.State.Rejected)
                deferred.Reject(resultContainer.RejectReason);
            else
                deferred.Cancel();
        })
        .Forget();
    return deferred.Promise;
}