[mono] Deadlock on TypeInitializationLock in mono_runtime_class_init_full

[uweigand]

We've seen a deadlock in roslyn when performing a source-build of rc2 natively on ppc64le (using the Mono runtime). In a nutshell, it seems the logic behind this block code code in mono_runtime_class_init_full is not thread-safe:

                /* see if the thread doing the initialization is already blocked on this thread */
                gboolean is_blocked = TRUE;
                blocked = GUINT_TO_POINTER (MONO_NATIVE_THREAD_ID_TO_UINT (lock->initializing_tid));
                while ((pending_lock = (TypeInitializationLock*) g_hash_table_lookup (blocked_thread_hash, blocked))) {
                        if (mono_native_thread_id_equals (pending_lock->initializing_tid, tid)) {
                                if (!pending_lock->done) {
                                        mono_type_initialization_unlock ();
                                        goto return_true;
                                } else {
                                        /* the thread doing the initialization is blocked on this thread,
                                           but on a lock that has already been freed. It just hasn't got
                                           time to awake */
                                        is_blocked = FALSE;
                                        break;
                                }
                        }
                        blocked = GUINT_TO_POINTER (MONO_NATIVE_THREAD_ID_TO_UINT (pending_lock->initializing_tid));
                }

To trigger the race, it is necessary that two threads each are in mono_runtime_class_init_full twice. This can happen since mono_runtime_class_init_full performs mono_runtime_try_invoke, which executes some unknown managed code, which in turn can trigger a recursive mono_runtime_class_init_full call. If both threads try to initialize the same two classes X and Y, but in reverse order (i.e. thread A accesses Y in the .cctor of X while thread B accesses X in the .cctor of Y), we may end up in a deadlock.

To trigger the deadlock, it seems that a third class Z also has to be involved. That can lead to erroneous logic in the code above: Assume thread A is working both on X and (recursively) Z, and after Z is done tries to work on Y. But thread B has already started working on Y and is now recursively blocked on Z before then also requiring X. Since thread A sees that thread B is blocked on Z, which it itself has already completed, the code above triggers:

                                        /* the thread doing the initialization is blocked on this thread,
                                           but on a lock that has already been freed. It just hasn't got
                                           time to awake */

However, while it is true that thread B will indeed get woken up from Z's lock, that does not mean it will successfully complete initialization of Y as the Y's .cctor also needs X - where thread B will get again blocked on thread A after all.

In the example we're seeing, those nested initializations happen on various instantiations of Microsoft.CodeAnalysis.VisualBasic.Symbols.OverrideHidingHelper, which has this .cctor:

        Shared Sub New()
            OverrideHidingHelper(Of MethodSymbol).s_runtimeSignatureComparer = MethodSignatureComparer.RuntimeMethodSignatureComparer
            OverrideHidingHelper(Of PropertySymbol).s_runtimeSignatureComparer = PropertySignatureComparer.RuntimePropertySignatureComparer
            OverrideHidingHelper(Of EventSymbol).s_runtimeSignatureComparer = EventSignatureComparer.RuntimeEventSignatureComparer
        End Sub

A detailed timeline for a possible deadlock is as follows. (I cannot guarantee that this timeline is exacty what happened since I can only examine the deadlocked state. But it is a possibility how we could have gotten there.)

Thread A                                             Thread B

  mono_runtime_class_init_full (MonoVTable X)          mono_runtime_class_init_full (MonoVTable Y)
   mono_type_initialization_lock
   lookup X in type_initialization_hash: n/a
   allocate TypeInitializationLock LX
   insert into type_initialization_hash: X -> LX
   mono_type_initialization_unlock
                                                         mono_type_initialization_lock
                                                         lookup Y in type_initialization_hash: n/a
                                                         allocate TypeInitializationLock LY
                                                         insert into type_initialization_hash: Y -> LY
                                                         mono_type_initialization_unlock

   mono_runtime_try_invoke (X .cctor)                    mono_runtime_try_invoke (Y .cctor)
     ... managed code ...                                   ... managed code ...
     mono_runtime_class_init_full (MonoVTable Z)            mono_runtime_class_init_full (MonoVTable Z)
       mono_type_initialization_lock
       lookup Z in type_initialization_hash: n/a
       allocate TypeInitializionLock LZ
       insert into type_initialization_hash: Z -> LZ
       mono_type_initialization_unlock
                                                              mono_type_initialization_lock
                                                              lookup Z in type_initialization_hash: LZ
                                                              LZ->initializing_tid is thread A
                                                              lookup A in blocked_thread_hash: n/a
                                                              insert into blocked_thread_hash: B -> LZ
                                                              mono_type_initialization_unlock
                                                              wait on LZ
       [... complete initialization of Z ...]
       LZ->done = TRUE;
       wakeup waiters on LZ
     mono_runtime_class_init_full (MonoVTable Z) returns
     ... managed code ...
     mono_runtime_class_init_full (MonoVTable Y)
       mono_type_initialization_lock
       lookup Y in type_initialization_hash: LY
       LY->initializing_tid is thread B
       lookup B in blocked_thread_hash: LZ
       LZ->initializing_tid is thread A
       LZ->done is TRUE
         /* the thread doing the initialization is blocked on this thread,
            but on a lock that has already been freed. It just hasn't got
            time to awake */
       mono_type_initialization_unlock
       wait on LY
                                                              wakeup from LZ
                                                              mono_type_initialization_lock
                                                              remove from blocked_thread_hash: B-> LZ
                                                              remove from type_initialization_hash: Z -> LZ
                                                              mono_type_initialization_unlock
                                                            mono_runtime_class_init_full (MonoVTable Z) returns
                                                            ... managed code ...
                                                            mono_runtime_class_init_full (MonoVTable X)
                                                              mono_type_initialization_lock
                                                              lookup X in type_initialization_hash: LX
                                                              LX->initializing_tid is thread A
                                                              lookup A in blocked_thread_hash: n/a
                                                              insert into blocked_thread_hash: B -> LX
                                                              mono_type_initialization_unlock
                                                              wait on LX

CC - @directhex @lambdageek @vargaz @akoeplinger
FYI - @giritrivedi @alhad-deshpande @janani66 @omajid @tmds

[lambdageek]

Here's a self-contained repro that hangs after a few runs:

using System;
using System.Runtime.CompilerServices;
using System.Threading;


public class X {
        public static X Singleton = new();
        public static void Create() {
        }
        
        private X() {
            Z.Singleton.Ping("X");
            Y.Singleton?.Pong();
        }

        public void Pong() => Coordinator.Ping("x");
}

public class Y {
        public static Y Singleton = new();
        public static void Create() {
                
        }
        private Y() {
            Z.Singleton.Ping("Y");
            X.Singleton?.Pong();
        }

        public void Pong() => Coordinator.Ping("y");
}

public class Z {
        public static Z Singleton = new();

        public void Ping(string s) { Coordinator.Ping(s); }
        
}

public class Coordinator {
        private class SettingsClass {
                public bool XThenY { get; init; }
                public SettingsClass() {}
        }
        
        private static int s_NextPing;
        private static readonly string[] Pings = new string[12];

        public static void Ping(string s) {
                int idx = Interlocked.Increment(ref s_NextPing);
                idx--;
                Pings[2*idx] = s;
                Pings[2*idx+1] = $"{Thread.CurrentThread.ManagedThreadId}";
        }

        public static Coordinator CreateThread(bool xThenY)
        {
                var settings = new SettingsClass { XThenY = xThenY };
                return new Coordinator(settings);
        }

        public readonly Thread Thread;
        private static readonly Barrier s_barrier = new (3);

        private Coordinator(SettingsClass settings) {
                var t = new Thread((initState) => {
                        var sets = (SettingsClass)initState;
                        Log("started");
                        NextPhase();
                        Log("racing");
                        DoConstructions(sets.XThenY);
                        NextPhase();
                        Log("done");
                });
                Thread = t;
                t.Start(settings);
        }

        public static void NextPhase() { s_barrier.SignalAndWait(); }

        [MethodImpl(MethodImplOptions.NoInlining)]
        public static void DoConstructions(bool xThenY)
        {
                if (xThenY) {
                        XCreate();
                } else {
                        YCreate();
                }
        }

        [MethodImpl(MethodImplOptions.NoInlining)]
        private static void XCreate() {
                var _ = X.Singleton;
        }

        [MethodImpl(MethodImplOptions.NoInlining)]
        private static void YCreate() {
                var _ = Y.Singleton;
        }

        public static void Log(string msg)
        {
                Console.WriteLine ($"{Thread.CurrentThread.ManagedThreadId}: {msg}");
        }

        public static void Main()
        {
                Console.WriteLine($"prepared for {Pings.Length} pings");
                Log("-- starting");
                var c1 = CreateThread(xThenY: true);
                var c2 = CreateThread(xThenY: false);
                Log("-- created all");
                NextPhase();
                Log("-- racing");
                NextPhase();
                Log("-- done");
                c1.Thread.Join();
                c2.Thread.Join();
                Log("-- all done");
                int i = 0;
                foreach (var p in Pings) {
                        if (p != null) {
                                Console.WriteLine($"ping {i}: {p}");
                        }
                        i++;
                }
        }
}

<Project Sdk="Microsoft.NET.Sdk">

  <PropertyGroup>
    <OutputType>Exe</OutputType>
    <TargetFramework>net8.0</TargetFramework>
    <ImplicitUsings>enable</ImplicitUsings>
    <Nullable>enable</Nullable>
  </PropertyGroup>

  <PropertyGroup>
      <UseMonoRuntime>true</UseMonoRuntime>
      <SelfContained>true</SelfContained>
  </PropertyGroup>
</Project>

[lambdageek]

stack traces

  thread #6, name = 'tid_1003'
    frame #0: 0x000000018ea560ac libsystem_kernel.dylib`__psynch_cvwait + 8
    frame #1: 0x000000018ea935fc libsystem_pthread.dylib`_pthread_cond_wait + 1228
    frame #2: 0x0000000103569f6c libcoreclr.dylib`mono_runtime_class_init_full [inlined] mono_os_cond_wait(cond=0x00006000027540d0, mutex=0x0000600002754090) at mono-os-mutex.h:219:8 [opt]
    frame #3: 0x0000000103569f60 libcoreclr.dylib`mono_runtime_class_init_full at mono-coop-mutex.h:91:2 [opt]
    frame #4: 0x0000000103569f50 libcoreclr.dylib`mono_runtime_class_init_full(vtable=0x000000014da47ef8, error=0x000000014d0a1710) at object.c:609:4 [opt]
    frame #5: 0x0000000103371a28 libcoreclr.dylib`mono_method_to_ir(cfg=, method=, start_bblock=0x000000014d051d60, end_bblock=0x000000014d051ea0, return_var=0x0000000000000000, inline_args=, inline_offset=0, is_virtual_call=) at method-to-ir.c:10245:13 [opt]
    frame #6: 0x000000010334941c libcoreclr.dylib`mini_method_compile(method=, opts=374417919, flags=JIT_FLAG_RUN_CCTORS, parts=0, aot_method_index=-1) at mini.c:3498:2 [opt]
    frame #7: 0x000000010334bdf0 libcoreclr.dylib`mono_jit_compile_method_inner(method=0x000000013d00dd90, opt=, error=0x000000016da75900) at mini.c:4132:8 [opt]
    frame #8: 0x0000000103350a4c libcoreclr.dylib`jit_compile_method_with_opt [inlined] mono_jit_compile_method_with_opt(method=0x000000013d00dd90, opt=, jit_only=, error=) at mini-runtime.c:2813:10 [opt]
    frame #9: 0x000000010334fff0 libcoreclr.dylib`jit_compile_method_with_opt [inlined] jit_compile_method_with_opt_cb(arg=) at mini-runtime.c:2868:17 [opt]
    frame #10: 0x000000010334ffe4 libcoreclr.dylib`jit_compile_method_with_opt(params=0x000000016da757e0) at mini-runtime.c:2884:2 [opt]
    frame #11: 0x000000010334fe28 libcoreclr.dylib`mono_jit_compile_method(method=0x000000013d00dd90, error=0x000000016da75900) at mini-runtime.c:2903:9 [opt]
    frame #12: 0x00000001033ecb48 libcoreclr.dylib`common_call_trampoline(regs=, code=, m=0x000000013d00dd90, vt=0x0000000000000000, vtable_slot=, error=0x000000016da75900) at mini-trampolines.c:628:27 [opt]
    frame #13: 0x00000001033ec6b4 libcoreclr.dylib`mono_magic_trampoline(regs=0x000000016da75990, code="\xa1\U0000000f@\xf9", arg=0x000000013d00dd90, tramp=) at mini-trampolines.c:769:8 [opt]
    frame #14: 0x0000000102af0304
    frame #15: 0x0000000102e3b654
    frame #16: 0x0000000102c86b18
    frame #17: 0x0000000103354f38 libcoreclr.dylib`mono_jit_runtime_invoke(method=, obj=, params=, exc=, error=) at mini-runtime.c:3681:12 [opt]
    frame #18: 0x000000010356a810 libcoreclr.dylib`mono_runtime_try_invoke [inlined] do_runtime_invoke(method=0x000000013d00dd68, obj=0x0000000000000000, params=0x0000000000000000, exc=0x000000016da75d98, error=0x000000014d036110) at object.c:2542:11 [opt]
    frame #19: 0x000000010356a7d4 libcoreclr.dylib`mono_runtime_try_invoke(method=0x000000013d00dd68, obj=0x0000000000000000, params=0x0000000000000000, exc=0x000000016da75d98, error=0x000000014d036110) at object.c:2699:9 [opt]
    frame #20: 0x0000000103569dd4 libcoreclr.dylib`mono_runtime_class_init_full(vtable=0x000000014da48000, error=0x000000014d036110) at object.c:541:3 [opt]
    frame #21: 0x0000000103371a28 libcoreclr.dylib`mono_method_to_ir(cfg=, method=, start_bblock=0x000000014d04fba0, end_bblock=0x000000014d04fce0, return_var=0x0000000000000000, inline_args=, inline_offset=0, is_virtual_call=) at method-to-ir.c:10245:13 [opt]
    frame #22: 0x000000010334941c libcoreclr.dylib`mini_method_compile(method=, opts=374417919, flags=JIT_FLAG_RUN_CCTORS, parts=0, aot_method_index=-1) at mini.c:3498:2 [opt]
    frame #23: 0x000000010334bdf0 libcoreclr.dylib`mono_jit_compile_method_inner(method=0x000000014d8f4f08, opt=, error=0x000000016da76a50) at mini.c:4132:8 [opt]
    frame #24: 0x0000000103350a4c libcoreclr.dylib`jit_compile_method_with_opt [inlined] mono_jit_compile_method_with_opt(method=0x000000014d8f4f08, opt=, jit_only=, error=) at mini-runtime.c:2813:10 [opt]
    frame #25: 0x000000010334fff0 libcoreclr.dylib`jit_compile_method_with_opt [inlined] jit_compile_method_with_opt_cb(arg=) at mini-runtime.c:2868:17 [opt]
    frame #26: 0x000000010334ffe4 libcoreclr.dylib`jit_compile_method_with_opt(params=0x000000016da76930) at mini-runtime.c:2884:2 [opt]
    frame #27: 0x000000010334fe28 libcoreclr.dylib`mono_jit_compile_method(method=0x000000014d8f4f08, error=0x000000016da76a50) at mini-runtime.c:2903:9 [opt]
    frame #28: 0x00000001033ecb48 libcoreclr.dylib`common_call_trampoline(regs=, code=, m=0x000000014d8f4f08, vt=0x0000000000000000, vtable_slot=, error=0x000000016da76a50) at mini-trampolines.c:628:27 [opt]
    frame #29: 0x00000001033ec6b4 libcoreclr.dylib`mono_magic_trampoline(regs=0x000000016da76ae0, code="\U00000002", arg=0x000000014d8f4f08, tramp=) at mini-trampolines.c:769:8 [opt]
    frame #30: 0x0000000102af0304
    frame #31: 0x0000000102e3b23c
    frame #32: 0x0000000102de392c
    frame #33: 0x0000000102de35ec
    frame #34: 0x0000000102c9d248
    frame #35: 0x0000000103354f38 libcoreclr.dylib`mono_jit_runtime_invoke(method=, obj=, params=, exc=, error=) at mini-runtime.c:3681:12 [opt]
    frame #36: 0x0000000103569920 libcoreclr.dylib`mono_runtime_invoke_checked [inlined] do_runtime_invoke(method=0x000000014d055758, obj=0x000000010380f760, params=0x0000000000000000, exc=0x0000000000000000, error=0x000000016da76f30) at object.c:2542:11 [opt]
    frame #37: 0x00000001035698e4 libcoreclr.dylib`mono_runtime_invoke_checked(method=0x000000014d055758, obj=0x000000010380f760, params=0x0000000000000000, error=0x000000016da76f30) at object.c:2758:9 [opt]
    frame #38: 0x0000000103583530 libcoreclr.dylib`start_wrapper at threads.c:1213:3 [opt]
    frame #39: 0x0000000103583324 libcoreclr.dylib`start_wrapper(data=) at threads.c:1271:8 [opt]
    frame #40: 0x000000018ea93034 libsystem_pthread.dylib`_pthread_start + 136
  thread #7, name = 'tid_1203'
    frame #0: 0x000000018ea560ac libsystem_kernel.dylib`__psynch_cvwait + 8
    frame #1: 0x000000018ea935fc libsystem_pthread.dylib`_pthread_cond_wait + 1228
    frame #2: 0x0000000103569f6c libcoreclr.dylib`mono_runtime_class_init_full [inlined] mono_os_cond_wait(cond=0x000060000275c450, mutex=0x000060000275c410) at mono-os-mutex.h:219:8 [opt]
    frame #3: 0x0000000103569f60 libcoreclr.dylib`mono_runtime_class_init_full at mono-coop-mutex.h:91:2 [opt]
    frame #4: 0x0000000103569f50 libcoreclr.dylib`mono_runtime_class_init_full(vtable=0x000000014da48000, error=0x000000013d00bb10) at object.c:609:4 [opt]
    frame #5: 0x0000000103371a28 libcoreclr.dylib`mono_method_to_ir(cfg=, method=, start_bblock=0x000000013d00c160, end_bblock=0x000000013d00c2a0, return_var=0x0000000000000000, inline_args=, inline_offset=0, is_virtual_call=) at method-to-ir.c:10245:13 [opt]
    frame #6: 0x000000010334941c libcoreclr.dylib`mini_method_compile(method=, opts=374417919, flags=JIT_FLAG_RUN_CCTORS, parts=0, aot_method_index=-1) at mini.c:3498:2 [opt]
    frame #7: 0x000000010334bdf0 libcoreclr.dylib`mono_jit_compile_method_inner(method=0x000000013d00dc28, opt=, error=0x000000016dc81900) at mini.c:4132:8 [opt]
    frame #8: 0x0000000103350a4c libcoreclr.dylib`jit_compile_method_with_opt [inlined] mono_jit_compile_method_with_opt(method=0x000000013d00dc28, opt=, jit_only=, error=) at mini-runtime.c:2813:10 [opt]
    frame #9: 0x000000010334fff0 libcoreclr.dylib`jit_compile_method_with_opt [inlined] jit_compile_method_with_opt_cb(arg=) at mini-runtime.c:2868:17 [opt]
    frame #10: 0x000000010334ffe4 libcoreclr.dylib`jit_compile_method_with_opt(params=0x000000016dc817e0) at mini-runtime.c:2884:2 [opt]
    frame #11: 0x000000010334fe28 libcoreclr.dylib`mono_jit_compile_method(method=0x000000013d00dc28, error=0x000000016dc81900) at mini-runtime.c:2903:9 [opt]
    frame #12: 0x00000001033ecb48 libcoreclr.dylib`common_call_trampoline(regs=, code=, m=0x000000013d00dc28, vt=0x0000000000000000, vtable_slot=, error=0x000000016dc81900) at mini-trampolines.c:628:27 [opt]
    frame #13: 0x00000001033ec6b4 libcoreclr.dylib`mono_magic_trampoline(regs=0x000000016dc81990, code="\xa1\U0000000f@\xf9", arg=0x000000013d00dc28, tramp=) at mini-trampolines.c:769:8 [opt]
    frame #14: 0x0000000102af0304
    frame #15: 0x0000000102e3b57c
    frame #16: 0x0000000102c86b18
    frame #17: 0x0000000103354f38 libcoreclr.dylib`mono_jit_runtime_invoke(method=, obj=, params=, exc=, error=) at mini-runtime.c:3681:12 [opt]
    frame #18: 0x000000010356a810 libcoreclr.dylib`mono_runtime_try_invoke [inlined] do_runtime_invoke(method=0x000000014d8f5070, obj=0x0000000000000000, params=0x0000000000000000, exc=0x000000016dc81d98, error=0x000000014d05b710) at object.c:2542:11 [opt]
    frame #19: 0x000000010356a7d4 libcoreclr.dylib`mono_runtime_try_invoke(method=0x000000014d8f5070, obj=0x0000000000000000, params=0x0000000000000000, exc=0x000000016dc81d98, error=0x000000014d05b710) at object.c:2699:9 [opt]
    frame #20: 0x0000000103569dd4 libcoreclr.dylib`mono_runtime_class_init_full(vtable=0x000000014da47ef8, error=0x000000014d05b710) at object.c:541:3 [opt]
    frame #21: 0x0000000103371a28 libcoreclr.dylib`mono_method_to_ir(cfg=, method=, start_bblock=0x000000014d049ba0, end_bblock=0x000000014d049ce0, return_var=0x0000000000000000, inline_args=, inline_offset=0, is_virtual_call=) at method-to-ir.c:10245:13 [opt]
    frame #22: 0x000000010334941c libcoreclr.dylib`mini_method_compile(method=, opts=374417919, flags=JIT_FLAG_RUN_CCTORS, parts=0, aot_method_index=-1) at mini.c:3498:2 [opt]
    frame #23: 0x000000010334bdf0 libcoreclr.dylib`mono_jit_compile_method_inner(method=0x000000014d8f4f30, opt=, error=0x000000016dc82a50) at mini.c:4132:8 [opt]
    frame #24: 0x0000000103350a4c libcoreclr.dylib`jit_compile_method_with_opt [inlined] mono_jit_compile_method_with_opt(method=0x000000014d8f4f30, opt=, jit_only=, error=) at mini-runtime.c:2813:10 [opt]
    frame #25: 0x000000010334fff0 libcoreclr.dylib`jit_compile_method_with_opt [inlined] jit_compile_method_with_opt_cb(arg=) at mini-runtime.c:2868:17 [opt]
    frame #26: 0x000000010334ffe4 libcoreclr.dylib`jit_compile_method_with_opt(params=0x000000016dc82930) at mini-runtime.c:2884:2 [opt]
    frame #27: 0x000000010334fe28 libcoreclr.dylib`mono_jit_compile_method(method=0x000000014d8f4f30, error=0x000000016dc82a50) at mini-runtime.c:2903:9 [opt]
    frame #28: 0x00000001033ecb48 libcoreclr.dylib`common_call_trampoline(regs=, code=, m=0x000000014d8f4f30, vt=0x0000000000000000, vtable_slot=, error=0x000000016dc82a50) at mini-trampolines.c:628:27 [opt]
    frame #29: 0x00000001033ec6b4 libcoreclr.dylib`mono_magic_trampoline(regs=0x000000016dc82ae0, code="\xbf\U00000003", arg=0x000000014d8f4f30, tramp=) at mini-trampolines.c:769:8 [opt]
    frame #30: 0x0000000102af0304
    frame #31: 0x0000000102e3b244
    frame #32: 0x0000000102de392c
    frame #33: 0x0000000102de35ec
    frame #34: 0x0000000102c9d248
    frame #35: 0x0000000103354f38 libcoreclr.dylib`mono_jit_runtime_invoke(method=, obj=, params=, exc=, error=) at mini-runtime.c:3681:12 [opt]
    frame #36: 0x0000000103569920 libcoreclr.dylib`mono_runtime_invoke_checked [inlined] do_runtime_invoke(method=0x000000014d055758, obj=0x000000010380f9b0, params=0x0000000000000000, exc=0x0000000000000000, error=0x000000016dc82f30) at object.c:2542:11 [opt]
    frame #37: 0x00000001035698e4 libcoreclr.dylib`mono_runtime_invoke_checked(method=0x000000014d055758, obj=0x000000010380f9b0, params=0x0000000000000000, error=0x000000016dc82f30) at object.c:2758:9 [opt]
    frame #38: 0x0000000103583530 libcoreclr.dylib`start_wrapper at threads.c:1213:3 [opt]
    frame #39: 0x0000000103583324 libcoreclr.dylib`start_wrapper(data=) at threads.c:1271:8 [opt]
    frame #40: 0x000000018ea93034 libsystem_pthread.dylib`_pthread_start + 136

[lambdageek]

I'm not sure what is the best thing to do here. it is tempting to say that when Thread A does "wait on LY" at that point things have gone wrong: thread A is waiting on a lock without being in the blocked_thread_hash. But I'm not sure when exactly we should be inserting it.

It seems like we need to know that while B is currently working on Z it is also working on Y. So maybe we need to detect that we're recursively in mono_class_init_full and chain the type initialization locks somehow? This seems like a very complicated solution.

I think the next step here is to go look at CoreCLR and see what they do to break class init cycles

[lambdageek]

NativeAOT's approach is here:

runtime/src/coreclr/nativeaot/System.Private.CoreLib/src/System/Runtime/CompilerServices/ClassConstructorRunner.cs

Line 135 in 3a97c68

private static unsafe bool DeadlockAwareAcquire(CctorHandle cctor, StaticClassConstructionContext* pContext)

it's interesting that they actually don't use unbounded waits. they repeatedly try to detect cycles and return early, but if they don't detect a cycle they try to give the current thread more time to acquire the initialization lock, rather than using some kind of signaling scheme to wake up blocked threads.

[lambdageek]

CoreCLR implementation is not as self contained, but it is in MethodTable::DoRunClassInitThrowing()

runtime/src/coreclr/vm/methodtable.cpp

Line 4476 in 5f653dd

if (pLock.DeadlockAwareAcquire())

it's a bit hard to follow what is going on, but the deadlock detection is in DeadlockAwareLock::TryBeginEnterLock

runtime/src/coreclr/vm/threads.cpp

Line 8019 in 5f653dd

BOOL DeadlockAwareLock::TryBeginEnterLock()

this does do wait an unbounded amount of time but it doesn't give the initializing thread the responsibility to wake anyone that is waiting - it seems to just rely on the critical section to let in one thread at a time.

---

I think what I'm concluding is that mono's

					/* the thread doing the initialization is blocked on this thread,
					   but on a lock that has already been freed. It just hasn't got
					   time to awake */

case is an optimization that we can leave out: if we detect a deadlock, even if pending_lock->done == TRUE we should just return true instead of trying to give the blocked thread time to wake up and signal us. (But I'm very much uncertain that this is the right idea. And also I'm not certain it will actually solve the problem).

@uweigand @vargaz what do you think?

[lambdageek]

Thinking about this more, I think what I am planning to do is to replace the loop with untimed condvar wait by a single timed wait and if it times out, restart from the beginning (ie: re-evaluate the deadlock). That is replace this:

runtime/src/mono/mono/metadata/object.c

Lines 606 to 609 in e355697

	mono_type_init_lock (lock);
	while (!lock->done)
	mono_coop_cond_wait (&lock->cond, &lock->mutex);
	mono_type_init_unlock (lock);

by

		mono_type_init_lock (lock);
		if (!lock->done) {
			int timeout_ms = 500;
			int wait_result = mono_coop_cond_timedwait (&lock->cond, &lock->mutex, timeout_ms);
			if (wait_result == -1) {
				/* timed out - go around again from the beginning.  If we got here
				 * from the "is_blocked = FALSE" case, above (another thread was
				 * blocked on the current thread, but on a lock that was already
				 * done but it didn't get to wake up yet), then it might still be
				 * the case that the current thread cannot proceed even if the other
				 * thread got to wake up - there might be a new deadlock.  We need
				 * to re-evaluate.
				 *
				 * This can happen if two threads A and B need to call the cctors
                                 * for classes X and Y but in opposite orders, and also call a cctor
                                 * for a third class Z.  (That is thread A wants to init: X, Z, Y;
                                 * thread B wants to init: Y, Z, X.)  In that case, if B is waiting
                                 * for A to finish initializing Z, and A (the current thread )
                                 * already finished Z and wants to init Y. In A, control will come
                                 * here with "lock" being Y's lock.  But we will time out because B
                                 * will see that A is responsible for initializing X and will also
                                 * block.  So A is waiting for B to finish Y and B is waiting for A
                                 * to finish X.  So the fact that A allowed B to wait for Z to
                                 * finish didn't actually let us make progress.  Thread A must go
                                 * around to the top once more and try to init Y - and detect that
                                 * there is now a deadlock between X and Y.
				 */
				mono_type_init_unlock (lock);
				// clean up blocked thread hash and lock refcount.
				mono_type_initialization_lock ();
				g_hash_table_remove (blocked_thread_hash, GUINT_TO_POINTER (tid));
				gboolean deleted = unref_type_lock (lock);
				if (deleted)
					g_hash_table_remove (type_initialization_hash, vtable);
				mono_type_initialization_unlock ();
				goto retry_top;
			} else if (wait_result == 0) {
				/* success.. we were signaled that the other thread is done.  Proceed */
			} else {
				g_error ("unexpected return value %d from mono_coop_cond_timedwait", wait_result);
			}
		}
		mono_type_init_unlock (lock);
		g_assert (lock->done);