AsyncQueue can hit a deadlock waiting for Cancellation to complete

[adrianvmsft]

Bug description

AsyncQueue tries to handle the ThreadingTools.ICancellationNotification.OnCanceled notification and tries to FreeCanceledDequeuers however that hits a lock because there is another thread, that has already entered the lock that is waiting for the Cancellation to complete

Repro steps

This issue gets hit randomly by the WebForms/ManagedLangs_CS_DDRIT

Thread 0:
14 010fce50 5cfea25c clr!JITutil_MonReliableEnter+0xb5 [f:\dd\ndp\clr\src\vm\jithelpers.cpp @ 4835] 
15 010fce84 5cff324a Microsoft_VisualStudio_Threading_ni!Microsoft.VisualStudio.Threading.AsyncQueue`1[[System.__Canon, mscorlib]].FreeCanceledDequeuers()+0x3c​
16 010fcea8 5cff9601 Microsoft_VisualStudio_Threading_ni!Microsoft.VisualStudio.Threading.AsyncQueue`1[[System.__Canon, mscorlib]].Microsoft.VisualStudio.Threading.ThreadingTools.ICancellationNotification.OnCanceled()+0xa​
17 010fcea8 721b7abf Microsoft_VisualStudio_Threading_ni!Microsoft.VisualStudio.Threading.ThreadingTools+<>c__10`1[[System.__Canon, mscorlib]].<AttachCancellation>b__10_0(System.Object)+0x91​
18 010fcf10 72162ea5 mscorlib_ni!System.Threading.CancellationCallbackInfo.ExecutionContextCallback(System.Object)+0x1f​
19 010fcf10 72162db6 mscorlib_ni!System.Threading.ExecutionContext.RunInternal(System.Threading.ExecutionContext, System.Threading.ContextCallback, System.Object, Boolean)+0xe5​
1a 010fcf24 72162d71 mscorlib_ni!System.Threading.ExecutionContext.Run(System.Threading.ExecutionContext, System.Threading.ContextCallback, System.Object, Boolean)+0x16​
1b 010fcf40 721b7a55 mscorlib_ni!System.Threading.ExecutionContext.Run(System.Threading.ExecutionContext, System.Threading.ContextCallback, System.Object)+0x41​
1c 010fcf5c 721b344b mscorlib_ni!System.Threading.CancellationCallbackInfo.ExecuteCallback()+0x51​
1d 010fcf6c 72148f71 mscorlib_ni!System.Threading.CancellationTokenSource.CancellationCallbackCoreWork(System.Threading.CancellationCallbackCoreWorkArguments)+0x2b​
1e 010fcfd4 72148e6a mscorlib_ni!System.Threading.CancellationTokenSource.ExecuteCallbackHandlers(Boolean)+0x101​
1f 010fcfe8 5d843f84 mscorlib_ni!System.Threading.CancellationTokenSource.NotifyCancellation(Boolean)+0x5a​
*** WARNING: Unable to verify checksum for Microsoft.VisualStudio.Shell.UI.Internal.ni.dll​
*** ERROR: Module load completed but symbols could not be loaded for Microsoft.VisualStudio.Shell.UI.Internal.ni.dll​
20 010fd00c 5d843ddb Microsoft_VisualStudio_Shell_UI_Internal_ni!Microsoft.VisualStudio.OperationProgress.OperationProgressStageUpdater.Dispose()+0x34​
21 010fd02c 5d84f96c Microsoft_VisualStudio_Shell_UI_Internal_ni!Microsoft.VisualStudio.OperationProgress.OperationProgressStage.EndStage(Boolean)+0x17​
22 010fd048 5d8334f8 Microsoft_VisualStudio_Shell_UI_Internal_ni!Microsoft.VisualStudio.OperationProgress.OperationProgressStage.CheckAllAccessDone()+0x8c​
23 010fd074 5d83346c Microsoft_VisualStudio_Shell_UI_Internal_ni!Microsoft.VisualStudio.OperationProgress.OperationProgressStage.StageAccessPropertyChanged(System.Object, System.ComponentModel.PropertyChangedEventArgs)+0x78​
24 010fd0e0 5d84f84e Microsoft_VisualStudio_Shell_UI_Internal_ni!Microsoft.VisualStudio.OperationProgress.OperationProgressStageAccess.NotifyPropertyChanged(System.String)+0x30​
25 010fd0e0 58b14dd8 Microsoft_VisualStudio_Shell_UI_Internal_ni!Microsoft.VisualStudio.OperationProgress.OperationProgressStageAccess.Dispose()+0x126​

Thread 17:
09 0db9e480 72d89b65 mscorlib_ni!System.Threading.CancellationTokenSource.WaitForCallbackToComplete(System.Threading.CancellationCallbackInfo)+0x21
0a 0db9e494 5cff96ad mscorlib_ni!System.Threading.CancellationTokenRegistration.Dispose()+0xc48e25​
0b 0db9e4b8 721c3348 Microsoft_VisualStudio_Threading_ni!Microsoft.VisualStudio.Threading.ThreadingTools+<>c__10`1[[System.__Canon, mscorlib]].<AttachCancellation>b__10_1(System.Threading.Tasks.Task`1<System.__Canon>, System.Object)+0x8d​
0c 0db9e4d0 72145c50 mscorlib_ni!System.Threading.Tasks.ContinuationTaskFromResultTask`1[[System.__Canon, mscorlib]].InnerInvoke()+0x78​
0d 0db9e4f4 7214607a mscorlib_ni!System.Threading.Tasks.Task.Execute()+0x30​
0e 0db9e55c 72162ea5 mscorlib_ni!System.Threading.Tasks.Task.ExecutionContextCallback(System.Object)+0x1a​
0f 0db9e55c 72162db6 mscorlib_ni!System.Threading.ExecutionContext.RunInternal(System.Threading.ExecutionContext, System.Threading.ContextCallback, System.Object, Boolean)+0xe5​
10 0db9e570 72145ef8 mscorlib_ni!System.Threading.ExecutionContext.Run(System.Threading.ExecutionContext, System.Threading.ContextCallback, System.Object, Boolean)+0x16​
11 0db9e5dc 72145e02 mscorlib_ni!System.Threading.Tasks.Task.ExecuteWithThreadLocal(System.Threading.Tasks.Task ByRef)+0xd8​
12 0db9e5ec 721b7282 mscorlib_ni!System.Threading.Tasks.Task.ExecuteEntry(Boolean)+0xb2​
13 0db9e614 721b2ce5 mscorlib_ni!System.Threading.Tasks.ThreadPoolTaskScheduler.TryExecuteTaskInline(System.Threading.Tasks.Task, Boolean)+0x32​
14 0db9e658 721b7100 mscorlib_ni!System.Threading.Tasks.TaskScheduler.TryRunInline(System.Threading.Tasks.Task, Boolean)+0x155​
15 0db9e6a0 721b5803 mscorlib_ni!System.Threading.Tasks.TaskContinuation.InlineIfPossibleOrElseQueue(System.Threading.Tasks.Task, Boolean)+0x50​
16 0db9e6c8 72146b78 mscorlib_ni!System.Threading.Tasks.StandardTaskContinuation.Run(System.Threading.Tasks.Task, Boolean)+0xc3​
17 0db9e6f0 7214867b mscorlib_ni!System.Threading.Tasks.Task.ContinueWithCore(System.Threading.Tasks.Task, System.Threading.Tasks.TaskScheduler, System.Threading.CancellationToken, System.Threading.Tasks.TaskContinuationOptions)+0xf8​
18 0db9e720 721485a7 mscorlib_ni!System.Threading.Tasks.Task`1[[System.__Canon, mscorlib]].ContinueWith(System.Action`2<System.Threading.Tasks.Task`1<System.__Canon>,System.Object>, System.Object, System.Threading.Tasks.TaskScheduler, System.Threading.CancellationToken, System.Threading.Tasks.TaskContinuationOptions, System.Threading.StackCrawlMark ByRef)+0xcb​
19 0db9e740 5cff8842 mscorlib_ni!System.Threading.Tasks.Task`1[[System.__Canon, mscorlib]].ContinueWith(System.Action`2<System.Threading.Tasks.Task`1<System.__Canon>,System.Object>, System.Object, System.Threading.CancellationToken, System.Threading.Tasks.TaskContinuationOptions, System.Threading.Tasks.TaskScheduler)+0x27​
1a 0db9e798 5cff3160 Microsoft_VisualStudio_Threading_ni!Microsoft.VisualStudio.Threading.ThreadingTools.AttachCancellation[[Microsoft.VisualStudio.PlatformUI.UIContextRules.AutoLoadManagerService+AutoLoadRequest, Microsoft.VisualStudio.Shell.UI.Internal]](System.Threading.Tasks.TaskCompletionSource`1<AutoLoadRequest>, System.Threading.CancellationToken, ICancellationNotification)+0xff80bb0e​
1b 0db9e7d8 5d832a1c Microsoft_VisualStudio_Threading_ni!Microsoft.VisualStudio.Threading.AsyncQueue`1[[System.__Canon, mscorlib]].DequeueAsync(System.Threading.CancellationToken)+0x190​
1c 0db9e870 721417e9 Microsoft_VisualStudio_Shell_UI_Internal_ni!Microsoft.VisualStudio.OperationProgress.OperationProgressStageUpdater+<RecalculateDisplay>d__9.MoveNext()+0x22c​

Expected behavior

No deadlock

Actual behavior

Deadlock

• Version used: Recent Visual Studio 16.0
• Application (if applicable):

Additional context

For more details (including .dmp) please see internal bug 771346

[AArnott]

Thanks for the analysis, @adrianvmsft. I've reduced the above callstacks to this:

Thread 1 stack:

(waiting for SyncRoot lock)
AsyncQueue.FreeCanceledDequeuers
AsyncQueue.OnCanceled
ThreadingTools.AttachCancellation+Register delegate
Cancel the CancellationToken passed to DequeueAsync on another thread

Thread 2 stack:

CancellationTokenSource.WaitForCallbackToComplete
CancellationTokenRegistration.Dispose
ThreadingTools.AttachCancellation+ContinueWith delegate
(TPL inlines continuation because antecedent was already completed)
Task.ContinueWith
ThreadingTools.AttachCancellation
AsyncQueue.DequeueAsync(CancellationToken)

Thread 2 has the lock held by DequeueAsync, and is waiting for thread 1 to return from its cancellation notification.
Thread 1 is processing cancellation and is waiting on the lock.

[AArnott]

I was able to reproduce the hang with a test that I controlled timing for in the debugger.