Asynchronous version of AutoResetEvent

Question

This is my second attempt to create asynchronous version of AutoResetEvent. At first I tried to make it completely lock-less, but it turned out to be impossible. This implementation contains a lock however the lock isn't an instance wide:

/// <summary>
///     Asynchronous version of <see cref="AutoResetEvent" />
/// </summary>
public sealed class AutoResetEventAsync {
    private static readonly Task<bool> Completed = Task.FromResult(true);

    private readonly ConcurrentQueue<TaskCompletionSource<bool>> handlers =
        new ConcurrentQueue<TaskCompletionSource<bool>>();

    private int isSet;

    /// <summary>
    ///     Initializes a new instance of the <see cref="AutoResetEventAsync" /> class with a Boolean value indicating whether to set the intial state to signaled.
    /// </summary>
    /// <param name="initialState">true to set the initial state signaled; false to set the initial state to nonsignaled.</param>
    public AutoResetEventAsync(bool initialState) {
        this.isSet = initialState ? 1 : 0;
    }

    /// <summary>
    ///     Sets the state of the event to signaled, allowing one waiting continuation to proceed.
    /// </summary>
    public void Set() {
        if (!this.TrySet())
            return;

        TaskCompletionSource<bool> handler;

        // Notify first alive handler
        while (this.handlers.TryDequeue(out handler))
            if (CheckIfAlive(handler)) // Flag check
                lock (handler) {
                    if (!CheckIfAlive(handler))
                        continue;

                    if (this.TryReset())
                        handler.SetResult(true);
                    else
                        this.handlers.Enqueue(handler);

                    break;
                }
    }

    /// <summary>
    ///     Try to switch the state to signaled from not signaled
    /// </summary>
    /// <returns>
    ///     true if suceeded, false if failed
    /// </returns>
    private bool TrySet() {
        return Interlocked.CompareExchange(ref this.isSet, 1, 0) == 0;
    }

    /// <summary>
    ///     Waits for a signal asynchronously
    /// </summary>
    public Task WaitAsync() {
        return this.WaitAsync(CancellationToken.None);
    }

    /// <summary>
    ///     Waits for a signal asynchronously
    /// </summary>
    /// <param name="cancellationToken">
    ///     A <see cref="P:System.Threading.Tasks.TaskFactory.CancellationToken" /> to observe while waiting for a signal.
    /// </param>
    /// <exception cref="OperationCanceledException">
    ///     The <paramref name="cancellationToken" /> was canceled.
    /// </exception>
    public Task WaitAsync(CancellationToken cancellationToken) {
        // Short path
        if (this.TryReset())
            return Completed;

        cancellationToken.ThrowIfCancellationRequested();

        // Wait for a signal
        var handler = new TaskCompletionSource<bool>(false);

        this.handlers.Enqueue(handler);

        if (CheckIfAlive(handler)) // Flag check
            lock (handler)
                if (CheckIfAlive(handler) && this.TryReset()) {
                    handler.SetResult(true);
                    return handler.Task;
                }

        cancellationToken.Register(() => {
            if (CheckIfAlive(handler)) // Flag check
                lock (handler)
                    if (CheckIfAlive(handler))
                        handler.SetCanceled();
        });

        return handler.Task;
    }

    private static bool CheckIfAlive(TaskCompletionSource<bool> handler) {
        return handler.Task.Status == TaskStatus.WaitingForActivation;
    }

    private bool TryReset() {
        return Interlocked.CompareExchange(ref this.isSet, 0, 1) == 1;
    }
}

Any suggestions?

Answer 1

At first I tried to make it completely lock-less, but it turned out to be impossible. This implementation contains a lock however the lock isn't an instance wide.

It may shock you to hear that lock-free code may be slower than code using locking.

Lock-free code is usually longer and is definitely much more complex. You should not attempt to write lock-free code until you fully understand the .NET memory model. Joe Duffy's book would be a good starting point after reading those articles. I would say you are ready to write lock-free code when you can describe why double-checked locking is broken in Java and correctly answer this question: is it also broken in C#?

But back to the point: lock-free code is easily slower than regular locking in this instance because lock-free code is only faster when there's a lot of contention. When you're writing async-compatible primitives, any locks you take are only going to last for the synchronous portion of that method call - an extremely short time. So, unless you have literally hundreds of different threads all calling Set or WaitAsync on the same instance at the same time, you won't have a problem. In other words, async primitives kind of "lift" you to a higher level of scheduling - you actually build your own queue of waiters. And any lock you have isn't going to affect the real contention, which will be represented by that queue.

So, on with the actual code review...

As @svick correctly pointed out, you have a (benign) race condition in your code that may cause starvation, when your Set chooses to re-enqueue a TCS. You are also holding onto resources longer than necessary by keeping "dead" TCS instances in your queue. Remember that each TCS has a Task along with all its continuations, and any local variables captured by their lambdas, etc.

But that's not a deal-breaker, it's just somewhat unfair (starvation) and inefficient (holding references). There's a more sinister and subtle problem with this implementation.

You are calling back to end-user code while holding a lock. This is violating one of the central laws of multithreaded programming. Whenever you do this, there is a possibility of deadlock.

It's very subtle because the callback is not obvious, but it's there in both Set and Reset: SetResult and SetCanceled both (synchronously) invoke any task continuations that were scheduled with the ExecuteSynchronously flag.

Answer 2

Your new code seems thread-safe to me. Though there are some small issues:

lock (handler)

I think that you should use braces after lock/if/while whenever the following statement is more than a single line, even if the language doesn't require it. It makes it simpler to see where does which block end.

if (CheckIfAlive(handler)) // Flag check
    lock (handler)
        if (CheckIfAlive(handler) && this.TryReset()) {
            handler.SetResult(true);
            return handler.Task;
        }

I don't see any reason to perform this check here again. TryReset() was already checked just a few quick lines before.

if (CheckIfAlive(handler)) // Flag check
    lock (handler)
        if (CheckIfAlive(handler))

Double checked locking is a dangerous practice, because it's hard to get right. I think your usage of it here is correct, but I would still avoid using it, unless you know the small performance gain will actually make a difference for you.

if (CheckIfAlive(handler))
    handler.SetCanceled();

Instead of calling CheckIfAlive() all over the place, you could use the Try* methods instead.

if (this.TryReset())
    handler.SetResult(true);
else
    this.handlers.Enqueue(handler);

Primitives like AutoResetEvent usually don't guarantee strict FIFO ordering. But I think they should guarantee at least some amount of fairness. With your implementation, it's not that unlikely that an item will never be processed (because it's constantly being moved to the back of the queue) even while others are being processed normally. I think you should think about whether this is a problem for you or not.

Answer 3

The code does a lot of cancellationToken.Register() calls without ever unregistering.

I'd create an inner class

private class Handler
{
   /// <summary>
   /// Gets or sets the task completion source.
   /// </summary>
   public TaskCompletionSource<bool> TaskCompletionSource { get; set; }

   /// <summary>
   /// Gets or sets the cancellation token registration.
   /// </summary>
   public CancellationTokenRegistration CancellationTokenRegistration { get; set; }
}

and set that as what the ConcurrentQueue holds. Then, go

var handler = new Handler { TaskCompletionSource = new TaskCompletionSource<bool>(false) };

and a few lines down from there:

lock (handler)
{
    handler.CancellationTokenRegistration = cancellationToken.Register(
        () =>
            {
                if (CheckIfAlive(handler.TaskCompletionSource)) // Flag check
                {
                    lock (handler)
                    {
                        if (CheckIfAlive(handler.TaskCompletionSource))
                        {
                            handler.TaskCompletionSource.SetCanceled();
                        }
                    }
                }
            });
}

Finally, sprinkle handler.CancellationTokenRegistration.Dispose(); lines where ever the dequeued handler gets used and not requeued (no need to check for null, it is a struct).